Actual source code: hashmap.h
1: #ifndef PETSC_HASHMAP_H
2: #define PETSC_HASHMAP_H
4: #include <petsc/private/hashtable.h>
6: /* SUBMANSEC = Sys */
8: /*MC
9: PETSC_HASH_MAP - Instantiate a PETSc hash table map type
11: Synopsis:
12: #include <petsc/private/hashmap.h>
13: PETSC_HASH_MAP(HMapT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue)
15: Input Parameters:
16: + HMapT - The hash table map type name suffix
17: . KeyType - The type of keys
18: . ValType - The type of values
19: . HashFunc - Routine or function-like macro computing hash values from keys
20: . EqualFunc - Routine or function-like macro computing whether two values are equal
21: - DefaultValue - Default value to use for queries in case of missing keys
23: Level: developer
25: .seealso: `PetscHMapT`, `PetscHMapTCreate()`
26: M*/
28: /*S
29: PetscHMapT - Hash table map
31: Synopsis:
32: typedef khash_t(HMapT) *PetscHMapT;
34: Level: developer
36: .seealso: `PETSC_HASH_MAP()`, `PetscHMapTCreate()`
37: S*/
39: /*MC
40: PetscHMapTCreate - Create a hash table
42: Synopsis:
43: #include <petsc/private/hashmap.h>
44: PetscErrorCode PetscHMapTCreate(PetscHMapT *ht)
46: Output Parameter:
47: . ht - The hash table
49: Level: developer
51: .seealso: `PetscHMapTDestroy()`
52: M*/
54: /*MC
55: PetscHMapTDestroy - Destroy a hash table
57: Synopsis:
58: #include <petsc/private/hashmap.h>
59: PetscErrorCode PetscHMapTDestroy(PetscHMapT *ht)
61: Input Parameter:
62: . ht - The hash table
64: Level: developer
66: .seealso: `PetscHMapTCreate()`
67: M*/
69: /*MC
70: PetscHMapTReset - Reset a hash table
72: Synopsis:
73: #include <petsc/private/hashmap.h>
74: PetscErrorCode PetscHMapTReset(PetscHMapT ht)
76: Input Parameter:
77: . ht - The hash table
79: Level: developer
81: .seealso: `PetscHMapTClear()`
82: M*/
84: /*MC
85: PetscHMapTDuplicate - Duplicate a hash table
87: Synopsis:
88: #include <petsc/private/hashmap.h>
89: PetscErrorCode PetscHMapTDuplicate(PetscHMapT ht,PetscHMapT *hd)
91: Input Parameter:
92: . ht - The source hash table
94: Output Parameter:
95: . ht - The duplicated hash table
97: Level: developer
99: .seealso: `PetscHMapTCreate()`
100: M*/
102: /*MC
103: PetscHMapTClear - Clear a hash table
105: Synopsis:
106: #include <petsc/private/hashmap.h>
107: PetscErrorCode PetscHMapTClear(PetscHMapT ht)
109: Input Parameter:
110: . ht - The hash table
112: Level: developer
114: .seealso: `PetscHMapTReset()`
115: M*/
117: /*MC
118: PetscHMapTResize - Set the number of buckets in a hash table
120: Synopsis:
121: #include <petsc/private/hashmap.h>
122: PetscErrorCode PetscHMapTResize(PetscHMapT ht,PetscInt nb)
124: Input Parameters:
125: + ht - The hash table
126: - nb - The number of buckets
128: Level: developer
130: .seealso: `PetscHMapTCreate()`
131: M*/
133: /*MC
134: PetscHMapTGetSize - Get the number of entries in a hash table
136: Synopsis:
137: #include <petsc/private/hashmap.h>
138: PetscErrorCode PetscHMapTGetSize(PetscHMapT ht,PetscInt *n)
140: Input Parameter:
141: . ht - The hash table
143: Output Parameter:
144: . n - The number of entries
146: Level: developer
148: .seealso: `PetscHMapTResize()`
149: M*/
151: /*MC
152: PetscHMapTGetCapacity - Get the current size of the array in the hash table
154: Synopsis:
155: #include <petsc/private/hashmap.h>
156: PetscErrorCode PetscHMapTGetCapacity(PetscHMapT ht,PetscInt *n)
158: Input Parameter:
159: . ht - The hash table
161: Output Parameter:
162: . n - The capacity
164: Level: developer
166: .seealso: `PetscHMapTResize()`, `PetscHMapTGetSize()`
167: M*/
169: /*MC
170: PetscHMapTHas - Query for a key in the hash table
172: Synopsis:
173: #include <petsc/private/hashmap.h>
174: PetscErrorCode PetscHMapTHas(PetscHMapT ht,KeyType key,PetscBool *has)
176: Input Parameters:
177: + ht - The hash table
178: - key - The key
180: Output Parameter:
181: . has - Boolean indicating whether key is in the hash table
183: Level: developer
185: .seealso: `PetscHMapTGet()`, `PetscHMapTSet()`, `PetscHMapTFind()`
186: M*/
188: /*MC
189: PetscHMapTGet - Get the value for a key in the hash table
191: Synopsis:
192: #include <petsc/private/hashmap.h>
193: PetscErrorCode PetscHMapTGet(PetscHMapT ht,KeyType key,ValType *val)
195: Input Parameters:
196: + ht - The hash table
197: - key - The key
199: Output Parameter:
200: . val - The value
202: Level: developer
204: .seealso: `PetscHMapTSet()`, `PetscHMapTIterGet()`
205: M*/
207: /*MC
208: PetscHMapTSet - Set a (key,value) entry in the hash table
210: Synopsis:
211: #include <petsc/private/hashmap.h>
212: PetscErrorCode PetscHMapTSet(PetscHMapT ht,KeyType key,ValType val)
214: Input Parameters:
215: + ht - The hash table
216: . key - The key
217: - val - The value
219: Level: developer
221: .seealso: `PetscHMapTGet()`, `PetscHMapTIterSet()`
222: M*/
224: /*MC
225: PetscHMapTDel - Remove a key and its value from the hash table
227: Synopsis:
228: #include <petsc/private/hashmap.h>
229: PetscErrorCode PetscHMapTDel(PetscHMapT ht,KeyType key)
231: Input Parameters:
232: + ht - The hash table
233: - key - The key
235: Level: developer
237: .seealso: `PetscHMapTHas()`, `PetscHMapTIterDel()`
238: M*/
240: /*MC
241: PetscHMapTQuerySet - Query and set a (key,value) entry in the hash table
243: Synopsis:
244: #include <petsc/private/hashmap.h>
245: PetscErrorCode PetscHMapTQuerySet(PetscHMapT ht,KeyType key,ValType val,PetscBool *missing)
247: Input Parameters:
248: + ht - The hash table
249: . key - The key
250: - val - The value
252: Output Parameter:
253: . missing - Boolean indicating whether the key was missing
255: Level: developer
257: .seealso: `PetscHMapTQueryDel()`, `PetscHMapTSet()`
258: M*/
260: /*MC
261: PetscHMapTQueryDel - Query and remove a (key,value) entry from the hash table
263: Synopsis:
264: #include <petsc/private/hashmap.h>
265: PetscErrorCode PetscHMapTQueryDel(PetscHMapT ht,KeyType key,PetscBool *present)
267: Input Parameters:
268: + ht - The hash table
269: - key - The key
271: Output Parameter:
272: . present - Boolean indicating whether the key was present
274: Level: developer
276: .seealso: `PetscHMapTQuerySet()`, `PetscHMapTDel()`
277: M*/
279: /*MC
280: PetscHMapTFind - Query for key in the hash table
282: Synopsis:
283: #include <petsc/private/hashmap.h>
284: PetscErrorCode PetscHMapTFind(PetscHMapT ht,KeyType key,PetscHashIter *iter,PetscBool *found)
286: Input Parameters:
287: + ht - The hash table
288: - key - The key
290: Output Parameters:
291: + iter - Iterator referencing the value for key
292: - found - Boolean indicating whether the key was present
294: Level: developer
296: .seealso: `PetscHMapTIterGet()`, `PetscHMapTIterDel()`
297: M*/
299: /*MC
300: PetscHMapTPut - Set a key in the hash table
302: Synopsis:
303: #include <petsc/private/hashmap.h>
304: PetscErrorCode PetscHMapTPut(PetscHMapT ht,KeyType key,PetscHashIter *iter,PetscBool *missing)
306: Input Parameters:
307: + ht - The hash table
308: - key - The key
310: Output Parameters:
311: + iter - Iterator referencing the value for key
312: - missing - Boolean indicating whether the key was missing
314: Level: developer
316: .seealso: `PetscHMapTIterSet()`, `PetscHMapTQuerySet()`, `PetscHMapTSet()`
317: M*/
319: /*MC
320: PetscHMapTIterGet - Get the value referenced by an iterator in the hash table
322: Synopsis:
323: #include <petsc/private/hashmap.h>
324: PetscErrorCode PetscHMapTIterGet(PetscHMapT ht,PetscHashIter iter,ValType *val)
326: Input Parameters:
327: + ht - The hash table
328: - iter - The iterator
330: Output Parameter:
331: . val - The value
333: Level: developer
335: .seealso: `PetscHMapTFind()`, `PetscHMapTGet()`
336: M*/
338: /*MC
339: PetscHMapTIterSet - Set the value referenced by an iterator in the hash
341: Synopsis:
342: #include <petsc/private/hashmap.h>
343: PetscErrorCode PetscHMapTIterSet(PetscHMapT ht,PetscHashIter iter,ValType val)
345: Input Parameters:
346: + ht - The hash table
347: . iter - The iterator
348: - val - The value
350: Level: developer
352: .seealso: `PetscHMapTPut()`, `PetscHMapTQuerySet()`, `PetscHMapTSet()`
353: M*/
355: /*MC
356: PetscHMapTIterDel - Remove the (key,value) referenced by an iterator from the hash table
358: Synopsis:
359: #include <petsc/private/hashmap.h>
360: PetscErrorCode PetscHMapTIterDel(PetscHMapT ht,PetscHashIter iter)
362: Input Parameters:
363: + ht - The hash table
364: - iter - The iterator
366: Level: developer
368: .seealso: `PetscHMapTFind()`, `PetscHMapTQueryDel()`, `PetscHMapTDel()`
369: M*/
371: /*MC
372: PetscHMapTGetKeys - Get all keys from a hash table
374: Synopsis:
375: #include <petsc/private/hashmap.h>
376: PetscErrorCode PetscHMapTGetKeys(PetscHMapT ht,PetscInt *off,KeyType array[])
378: Input Parameters:
379: + ht - The hash table
380: . off - Input offset in array (usually zero)
381: - array - Array where to put hash table keys into
383: Output Parameters:
384: + off - Output offset in array (output offset = input offset + hash table size)
385: - array - Array filled with the hash table keys
387: Level: developer
389: .seealso: `PetscHSetTGetSize()`, `PetscHMapTGetVals()`
390: M*/
392: /*MC
393: PetscHMapTGetVals - Get all values from a hash table
395: Synopsis:
396: #include <petsc/private/hashmap.h>
397: PetscErrorCode PetscHMapTGetVals(PetscHMapT ht,PetscInt *off,ValType array[])
399: Input Parameters:
400: + ht - The hash table
401: . off - Input offset in array (usually zero)
402: - array - Array where to put hash table values into
404: Output Parameters:
405: + off - Output offset in array (output offset = input offset + hash table size)
406: - array - Array filled with the hash table values
408: Level: developer
410: .seealso: `PetscHSetTGetSize()`, `PetscHMapTGetKeys()`
411: M*/
413: /*MC
414: PetscHMapTGetPairs - Get all (key,value) pairs from a hash table
416: Synopsis:
417: #include <petsc/private/hashmap.h>
418: PetscErrorCode PetscHMapTGetPairs(PetscHMapT ht,PetscInt *off,KeyType karray[],ValType varray[])
420: Input Parameters:
421: + ht - The hash table
422: . off - Input offset in array (usually zero)
423: - karray - Array where to put hash table keys into
424: - varray - Array where to put hash table values into
426: Output Parameters:
427: + off - Output offset in array (output offset = input offset + hash table size)
428: - karray - Array filled with the hash table keys
429: - varray - Array filled with the hash table values
431: Level: developer
433: .seealso: `PetscHSetTGetSize()`, `PetscHMapTGetKeys()`, `PetscHMapTGetVals()`
434: M*/
436: #define PETSC_HASH_MAP(HashT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue) \
437: \
438: KHASH_INIT(HashT, KeyType, ValType, 1, HashFunc, EqualFunc) \
439: \
440: typedef khash_t(HashT) *Petsc##HashT; \
441: \
442: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Create(Petsc##HashT *ht) \
443: { \
445: *ht = kh_init(HashT); \
446: PetscHashAssert(*ht != NULL); \
447: return 0; \
448: } \
449: \
450: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Destroy(Petsc##HashT *ht) \
451: { \
453: if (!*ht) return 0; \
454: kh_destroy(HashT, *ht); \
455: *ht = NULL; \
456: return 0; \
457: } \
458: \
459: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Reset(Petsc##HashT ht) \
460: { \
462: kh_reset(HashT, ht); \
463: return 0; \
464: } \
465: \
466: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Duplicate(Petsc##HashT ht, Petsc##HashT *hd) \
467: { \
468: int ret; \
469: KeyType key; \
470: ValType val; \
473: *hd = kh_init(HashT); \
474: PetscHashAssert(*hd != NULL); \
475: ret = kh_resize(HashT, *hd, kh_size(ht)); \
476: PetscHashAssert(ret == 0); \
477: kh_foreach(ht, key, val, { \
478: khiter_t i; \
479: i = kh_put(HashT, *hd, key, &ret); \
480: PetscHashAssert(ret >= 0); \
481: kh_val(*hd, i) = val; \
482: }) return 0; \
483: } \
484: \
485: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Clear(Petsc##HashT ht) \
486: { \
488: kh_clear(HashT, ht); \
489: return 0; \
490: } \
491: \
492: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Resize(Petsc##HashT ht, PetscInt nb) \
493: { \
494: int ret; \
496: ret = kh_resize(HashT, ht, (khint_t)nb); \
497: PetscHashAssert(ret >= 0); \
498: return 0; \
499: } \
500: \
501: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetSize(Petsc##HashT ht, PetscInt *n) \
502: { \
505: *n = (PetscInt)kh_size(ht); \
506: return 0; \
507: } \
508: \
509: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetCapacity(Petsc##HashT ht, PetscInt *n) \
510: { \
513: *n = (PetscInt)kh_n_buckets(ht); \
514: return 0; \
515: } \
516: \
517: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Has(Petsc##HashT ht, KeyType key, PetscBool *has) \
518: { \
519: khiter_t iter; \
523: iter = kh_get(HashT, ht, key); \
524: *has = (iter != kh_end(ht)) ? PETSC_TRUE : PETSC_FALSE; \
525: return 0; \
526: } \
527: \
528: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Get(Petsc##HashT ht, KeyType key, ValType *val) \
529: { \
530: khiter_t iter; \
534: iter = kh_get(HashT, ht, key); \
535: *val = (iter != kh_end(ht)) ? kh_val(ht, iter) : (DefaultValue); \
536: return 0; \
537: } \
538: \
539: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Set(Petsc##HashT ht, KeyType key, ValType val) \
540: { \
541: int ret; \
542: khiter_t iter; \
545: iter = kh_put(HashT, ht, key, &ret); \
546: PetscHashAssert(ret >= 0); \
547: kh_val(ht, iter) = val; \
548: return 0; \
549: } \
550: \
551: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Del(Petsc##HashT ht, KeyType key) \
552: { \
553: khiter_t iter; \
556: iter = kh_get(HashT, ht, key); \
557: kh_del(HashT, ht, iter); \
558: return 0; \
559: } \
560: \
561: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##QuerySet(Petsc##HashT ht, KeyType key, ValType val, PetscBool *missing) \
562: { \
563: int ret; \
564: khiter_t iter; \
568: iter = kh_put(HashT, ht, key, &ret); \
569: PetscHashAssert(ret >= 0); \
570: kh_val(ht, iter) = val; \
571: *missing = ret ? PETSC_TRUE : PETSC_FALSE; \
572: return 0; \
573: } \
574: \
575: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##QueryDel(Petsc##HashT ht, KeyType key, PetscBool *present) \
576: { \
577: khiter_t iter; \
581: iter = kh_get(HashT, ht, key); \
582: if (iter != kh_end(ht)) { \
583: kh_del(HashT, ht, iter); \
584: *present = PETSC_TRUE; \
585: } else { \
586: *present = PETSC_FALSE; \
587: } \
588: return 0; \
589: } \
590: \
591: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Find(Petsc##HashT ht, KeyType key, PetscHashIter *iter, PetscBool *found) \
592: \
593: { \
598: *iter = kh_get(HashT, ht, key); \
599: *found = (*iter != kh_end(ht)) ? PETSC_TRUE : PETSC_FALSE; \
600: return 0; \
601: } \
602: \
603: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Put(Petsc##HashT ht, KeyType key, PetscHashIter *iter, PetscBool *missing) \
604: { \
605: int ret; \
610: *iter = kh_put(HashT, ht, key, &ret); \
611: PetscHashAssert(ret >= 0); \
612: *missing = ret ? PETSC_TRUE : PETSC_FALSE; \
613: return 0; \
614: } \
615: \
616: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterGet(Petsc##HashT ht, PetscHashIter iter, ValType *val) \
617: { \
621: *val = PetscLikely(iter < kh_end(ht) && kh_exist(ht, iter)) ? kh_val(ht, iter) : (DefaultValue); \
622: return 0; \
623: } \
624: \
625: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterSet(Petsc##HashT ht, PetscHashIter iter, ValType val) \
626: { \
629: if (PetscLikely(iter < kh_end(ht) && kh_exist(ht, iter))) kh_val(ht, iter) = val; \
630: return 0; \
631: } \
632: \
633: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterDel(Petsc##HashT ht, PetscHashIter iter) \
634: { \
637: if (PetscLikely(iter < kh_end(ht))) kh_del(HashT, ht, iter); \
638: return 0; \
639: } \
640: \
641: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetKeys(Petsc##HashT ht, PetscInt *off, KeyType array[]) \
642: { \
643: KeyType key; \
644: PetscInt pos; \
647: pos = *off; \
648: kh_foreach_key(ht, key, array[pos++] = key); \
649: *off = pos; \
650: return 0; \
651: } \
652: \
653: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetVals(Petsc##HashT ht, PetscInt *off, ValType array[]) \
654: { \
655: ValType val; \
656: PetscInt pos; \
659: pos = *off; \
660: kh_foreach_value(ht, val, array[pos++] = val); \
661: *off = pos; \
662: return 0; \
663: } \
664: \
665: static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetPairs(Petsc##HashT ht, PetscInt *off, KeyType karray[], ValType varray[]) \
666: { \
667: ValType val; \
668: KeyType key; \
669: PetscInt pos; \
672: pos = *off; \
673: kh_foreach(ht, key, val, { \
674: karray[pos] = key; \
675: varray[pos++] = val; \
676: }) *off = pos; \
677: return 0; \
678: }
680: #endif /* PETSC_HASHMAP_H */