Actual source code: hashmap.h
petsc-3.11.4 2019-09-28
1: #if !defined(PETSC_HASHMAP_H)
2: #define PETSC_HASHMAP_H
4: #include <petsc/private/hashtable.h>
6: /*MC
7: PETSC_HASH_MAP - Instantiate a PETSc hash table map type
9: Synopsis:
10: #include <petsc/private/hashmap.h>
11: PETSC_HASH_MAP(HMapT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue)
13: Input Parameters:
14: + HMapT - The hash table map type name suffix
15: . KeyType - The type of keys
16: . ValType - The type of values
17: . HashFunc - Routine or function-like macro computing hash values from keys
18: . EqualFunc - Routine or function-like macro computing whether two values are equal
19: - DefaultValue - Default value to use for queries in case of missing keys
21: Level: developer
23: Concepts: hash table, map
25: .keywords: hash table, map
26: .seealso: PetscHMapT, PetscHMapTCreate()
27: M*/
29: /*S
30: PetscHMapT - Hash table map
32: Synopsis:
33: typedef khash_t(HMapT) *PetscHMapT;
35: Level: developer
37: Concepts: hash table, map
39: .keywords: hash table, map
40: .seealso: PETSC_HASH_MAP(), PetscHMapTCreate()
41: S*/
43: /*MC
44: PetscHMapTCreate - Create a hash table
46: Synopsis:
47: #include <petsc/private/hashmap.h>
48: PetscErrorCode PetscHMapTCreate(PetscHMapT *ht)
50: Output Parameter:
51: . ht - The hash table
53: Level: developer
55: Concepts: hash table, map
57: .keywords: hash table, map, create
58: .seealso: PetscHMapTDestroy()
59: M*/
61: /*MC
62: PetscHMapTDestroy - Destroy a hash table
64: Synopsis:
65: #include <petsc/private/hashmap.h>
66: PetscErrorCode PetscHMapTDestroy(PetscHMapT *ht)
68: Input Parameter:
69: . ht - The hash table
71: Level: developer
73: Concepts: hash table, map
75: .keywords: hash table, map, destroy
76: .seealso: PetscHMapTCreate()
77: M*/
79: /*MC
80: PetscHMapTReset - Reset a hash table
82: Synopsis:
83: #include <petsc/private/hashmap.h>
84: PetscErrorCode PetscHMapTReset(PetscHMapT ht)
86: Input Parameter:
87: . ht - The hash table
89: Level: developer
91: Concepts: hash table, map
93: .keywords: hash table, map, reset
94: .seealso: PetscHMapTClear()
95: M*/
97: /*MC
98: PetscHMapTDuplicate - Duplicate a hash table
100: Synopsis:
101: #include <petsc/private/hashmap.h>
102: PetscErrorCode PetscHMapTDuplicate(PetscHMapT ht,PetscHMapT *hd)
104: Input Parameter:
105: . ht - The source hash table
107: Output Parameter:
108: . ht - The duplicated hash table
110: Level: developer
112: Concepts: hash table, map
114: .keywords: hash table, map, duplicate
115: .seealso: PetscHMapTCreate()
116: M*/
118: /*MC
119: PetscHMapTClear - Clear a hash table
121: Synopsis:
122: #include <petsc/private/hashmap.h>
123: PetscErrorCode PetscHMapTClear(PetscHMapT ht)
125: Input Parameter:
126: . ht - The hash table
128: Level: developer
130: Concepts: hash table, map
132: .keywords: hash table, map, reset
133: .seealso: PetscHMapTReset()
134: M*/
136: /*MC
137: PetscHMapTResize - Set the number of buckets in a hash table
139: Synopsis:
140: #include <petsc/private/hashmap.h>
141: PetscErrorCode PetscHMapTResize(PetscHMapT ht,PetscInt nb)
143: Input Parameters:
144: + ht - The hash table
145: - nb - The number of buckets
147: Level: developer
149: Concepts: hash table, map
151: .seealso: PetscHMapTCreate()
152: M*/
154: /*MC
155: PetscHMapTGetSize - Get the number of entries in a hash table
157: Synopsis:
158: #include <petsc/private/hashmap.h>
159: PetscErrorCode PetscHMapTGetSize(PetscHMapT ht,PetscInt *n)
161: Input Parameter:
162: . ht - The hash table
164: Output Parameter:
165: . n - The number of entries
167: Level: developer
169: Concepts: hash table, map
171: .keywords: hash table, map, resize
172: .seealso: PetscHMapTResize()
173: M*/
175: /*MC
176: PetscHMapTHas - Query for a key in the hash table
178: Synopsis:
179: #include <petsc/private/hashmap.h>
180: PetscErrorCode PetscHMapTHas(PetscHMapT ht,KeyType key,PetscBool *has)
182: Input Parameters:
183: + ht - The hash table
184: - key - The key
186: Output Parameter:
187: . has - Boolean indicating whether key is in the hash table
189: Level: developer
191: Concepts: hash table, map
193: .keywords: hash table, map, query
194: .seealso: PetscHMapTGet(), PetscHMapTSet(), PetscHMapTFind()
195: M*/
197: /*MC
198: PetscHMapTGet - Get the value for a key in the hash table
200: Synopsis:
201: #include <petsc/private/hashmap.h>
202: PetscErrorCode PetscHMapTGet(PetscHMapT ht,KeyType key,ValType *val)
204: Input Parameters:
205: + ht - The hash table
206: - key - The key
208: Output Parameter:
209: . val - The value
211: Level: developer
213: Concepts: hash table, map
215: .keywords: hash table, map, get
216: .seealso: PetscHMapTSet(), PetscHMapTIterGet()
217: M*/
219: /*MC
220: PetscHMapTSet - Set a (key,value) entry in the hash table
222: Synopsis:
223: #include <petsc/private/hashmap.h>
224: PetscErrorCode PetscHMapTSet(PetscHMapT ht,KeyType key,ValType val)
226: Input Parameters:
227: + ht - The hash table
228: . key - The key
229: - val - The value
231: Level: developer
233: Concepts: hash table, map
235: .keywords: hash table, map, set
236: .seealso: PetscHMapTGet(), PetscHMapTIterSet()
237: M*/
239: /*MC
240: PetscHMapTDel - Remove a key and its value from the hash table
242: Synopsis:
243: #include <petsc/private/hashmap.h>
244: PetscErrorCode PetscHMapTDel(PetscHMapT ht,KeyType key)
246: Input Parameters:
247: + ht - The hash table
248: - key - The key
250: Level: developer
252: Concepts: hash table, map
254: .keywords: hash table, map, del
255: .seealso: PetscHMapTHas(), PetscHMapTIterDel()
256: M*/
258: /*MC
259: PetscHMapTQuerySet - Query and set a (key,value) entry in the hash table
261: Synopsis:
262: #include <petsc/private/hashmap.h>
263: PetscErrorCode PetscHMapTQuerySet(PetscHMapT ht,KeyType key,ValType val,PetscBool *missing)
265: Input Parameters:
266: + ht - The hash table
267: . key - The key
268: - val - The value
270: Output Parameter:
271: . missing - Boolean indicating whether the key was missing
273: Level: developer
275: Concepts: hash table, map
277: .keywords: hash table, map, query, set
278: .seealso: PetscHMapTQueryDel(), PetscHMapTSet()
279: M*/
281: /*MC
282: PetscHMapTQueryDel - Query and remove a (key,value) entry from the hash table
284: Synopsis:
285: #include <petsc/private/hashmap.h>
286: PetscErrorCode PetscHMapTQueryDel(PetscHMapT ht,KeyType key,PetscBool *present)
288: Input Parameters:
289: + ht - The hash table
290: - key - The key
292: Output Parameter:
293: . present - Boolean indicating whether the key was present
295: Level: developer
297: Concepts: hash table, map
299: .keywords: hash table, map, query, del
300: .seealso: PetscHMapTQuerySet(), PetscHMapTDel()
301: M*/
303: /*MC
304: PetscHMapTFind - Query for key in the hash table
306: Synopsis:
307: #include <petsc/private/hashmap.h>
308: PetscErrorCode PetscHMapTFind(PetscHMapT ht,KeyType key,PetscHashIter *iter,PetscBool *found)
310: Input Parameters:
311: + ht - The hash table
312: - key - The key
314: Output Parameter:
315: + iter - Iterator referencing the value for key
316: - found - Boolean indicating whether the key was present
318: Level: developer
320: Concepts: hash table, map
322: .keywords: hash table, map, iterator, find
323: .seealso: PetscHMapTIterGet(), PetscHMapTIterDel()
324: M*/
326: /*MC
327: PetscHMapTPut - Set a key in the hash table
329: Synopsis:
330: #include <petsc/private/hashmap.h>
331: PetscErrorCode PetscHMapTPut(PetscHMapT ht,KeyType key,PetscHashIter *iter,PetscBool *missing)
333: Input Parameters:
334: + ht - The hash table
335: - key - The key
337: Output Parameter:
338: + iter - Iterator referencing the value for key
339: - missing - Boolean indicating whether the key was missing
341: Level: developer
343: Concepts: hash table, map
345: .keywords: hash table, map, iterator, put
346: .seealso: PetscHMapTIterSet(), PetscHMapTQuerySet(), PetscHMapTSet()
347: M*/
349: /*MC
350: PetscHMapTIterGet - Get the value referenced by an iterator in the hash table
352: Synopsis:
353: #include <petsc/private/hashmap.h>
354: PetscErrorCode PetscHMapTIterGet(PetscHMapT ht,PetscHashIter iter,ValType *val)
356: Input Parameters:
357: + ht - The hash table
358: - iter - The iterator
360: Output Parameter:
361: . val - The value
363: Level: developer
365: Concepts: hash table, map
367: .keywords: hash table, map, iterator, get
368: .seealso: PetscHMapTFind(), PetscHMapTGet()
369: M*/
371: /*MC
372: PetscHMapTIterSet - Set the value referenced by an iterator in the hash
374: Synopsis:
375: #include <petsc/private/hashmap.h>
376: PetscErrorCode PetscHMapTIterSet(PetscHMapT ht,PetscHashIter iter,ValType val)
378: Input Parameters:
379: + ht - The hash table
380: . iter - The iterator
381: - val - The value
383: Level: developer
385: Concepts: hash table, map
387: .keywords: hash table, map, iterator, set
388: .seealso: PetscHMapTPut(), PetscHMapTQuerySet(), PetscHMapTSet()
389: M*/
391: /*MC
392: PetscHMapTIterDel - Remove the (key,value) referenced by an iterator from the hash table
394: Synopsis:
395: #include <petsc/private/hashmap.h>
396: PetscErrorCode PetscHMapTIterDel(PetscHMapT ht,PetscHashIter iter)
398: Input Parameters:
399: + ht - The hash table
400: - iter - The iterator
402: Level: developer
404: Concepts: hash table, map
406: .keywords: hash table, map, iterator, del
407: .seealso: PetscHMapTFind(), PetscHMapTQueryDel(), PetscHMapTDel()
408: M*/
410: /*MC
411: PetscHMapTGetKeys - Get all keys from a hash table
413: Synopsis:
414: #include <petsc/private/hashmap.h>
415: PetscErrorCode PetscHMapTGetKeys(PetscHMapT ht,PetscInt *off,KeyType array[])
417: Input Parameters:
418: + ht - The hash table
419: . off - Input offset in array (usually zero)
420: - array - Array where to put hash table keys into
422: Output Parameter:
423: + off - Output offset in array (output offset = input offset + hash table size)
424: - array - Array filled with the hash table keys
426: Level: developer
428: Concepts: hash table, map
430: .keywords: hash table, map, array
431: .seealso: PetscHSetTGetSize(), PetscHMapTGetVals()
432: M*/
434: /*MC
435: PetscHMapTGetVals - Get all values from a hash table
437: Synopsis:
438: #include <petsc/private/hashmap.h>
439: PetscErrorCode PetscHMapTGetVals(PetscHMapT ht,PetscInt *off,ValType array[])
441: Input Parameters:
442: + ht - The hash table
443: . off - Input offset in array (usually zero)
444: - array - Array where to put hash table values into
446: Output Parameter:
447: + off - Output offset in array (output offset = input offset + hash table size)
448: - array - Array filled with the hash table values
450: Level: developer
452: Concepts: hash table, map
454: .keywords: hash table, map, array
455: .seealso: PetscHSetTGetSize(), PetscHMapTGetKeys()
456: M*/
458: #define PETSC_HASH_MAP(HashT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue) \
459: \
460: KHASH_INIT(HashT, KeyType, ValType, 1, HashFunc, EqualFunc) \
461: \
462: typedef khash_t(HashT) *Petsc##HashT; \
463: \
464: PETSC_STATIC_INLINE PETSC_UNUSED \
465: PetscErrorCode Petsc##HashT##Create(Petsc##HashT *ht) \
466: { \
469: *ht = kh_init(HashT); \
470: PetscHashAssert(*ht!=NULL); \
471: return(0); \
472: } \
473: \
474: PETSC_STATIC_INLINE PETSC_UNUSED \
475: PetscErrorCode Petsc##HashT##Destroy(Petsc##HashT *ht) \
476: { \
479: if (!*ht) return(0); \
480: kh_destroy(HashT,*ht); *ht = NULL; \
481: return(0); \
482: } \
483: \
484: PETSC_STATIC_INLINE PETSC_UNUSED \
485: PetscErrorCode Petsc##HashT##Reset(Petsc##HashT ht) \
486: { \
489: kh_reset(HashT,ht); \
490: return(0); \
491: } \
492: \
493: PETSC_STATIC_INLINE PETSC_UNUSED \
494: PetscErrorCode Petsc##HashT##Duplicate(Petsc##HashT ht,Petsc##HashT *hd) \
495: { \
496: int ret; \
497: KeyType key; \
498: ValType val; \
502: *hd = kh_init(HashT); \
503: PetscHashAssert(*hd!=NULL); \
504: ret = kh_resize(HashT,*hd,kh_size(ht)); \
505: PetscHashAssert(ret==0); \
506: kh_foreach(ht,key,val,{ khiter_t i; \
507: i = kh_put(HashT,*hd,key,&ret); \
508: PetscHashAssert(ret>=0); \
509: kh_val(*hd,i) = val;}) \
510: return(0); \
511: } \
512: \
513: PETSC_STATIC_INLINE PETSC_UNUSED \
514: PetscErrorCode Petsc##HashT##Clear(Petsc##HashT ht) \
515: { \
518: kh_clear(HashT,ht); \
519: return(0); \
520: } \
521: \
522: PETSC_STATIC_INLINE PETSC_UNUSED \
523: PetscErrorCode Petsc##HashT##Resize(Petsc##HashT ht,PetscInt nb) \
524: { \
525: int ret; \
528: ret = kh_resize(HashT,ht,(khint_t)nb); \
529: PetscHashAssert(ret>=0); \
530: return(0); \
531: } \
532: \
533: PETSC_STATIC_INLINE PETSC_UNUSED \
534: PetscErrorCode Petsc##HashT##GetSize(Petsc##HashT ht,PetscInt *n) \
535: { \
539: *n = (PetscInt)kh_size(ht); \
540: return(0); \
541: } \
542: \
543: PETSC_STATIC_INLINE PETSC_UNUSED \
544: PetscErrorCode Petsc##HashT##Has(Petsc##HashT ht,KeyType key,PetscBool *has) \
545: { \
546: khiter_t iter; \
550: iter = kh_get(HashT,ht,key); \
551: *has = (iter != kh_end(ht)) ? PETSC_TRUE : PETSC_FALSE; \
552: return(0); \
553: } \
554: \
555: PETSC_STATIC_INLINE PETSC_UNUSED \
556: PetscErrorCode Petsc##HashT##Get(Petsc##HashT ht,KeyType key,ValType *val) \
557: { \
558: khiter_t iter; \
562: iter = kh_get(HashT,ht,key); \
563: *val = (iter != kh_end(ht)) ? kh_val(ht,iter) : (DefaultValue); \
564: return(0); \
565: } \
566: \
567: PETSC_STATIC_INLINE PETSC_UNUSED \
568: PetscErrorCode Petsc##HashT##Set(Petsc##HashT ht,KeyType key,ValType val) \
569: { \
570: int ret; \
571: khiter_t iter; \
574: iter = kh_put(HashT,ht,key,&ret); \
575: PetscHashAssert(ret>=0); \
576: kh_val(ht,iter) = val; \
577: return(0); \
578: } \
579: \
580: PETSC_STATIC_INLINE PETSC_UNUSED \
581: PetscErrorCode Petsc##HashT##Del(Petsc##HashT ht,KeyType key) \
582: { \
583: khiter_t iter; \
586: iter = kh_get(HashT,ht,key); \
587: kh_del(HashT,ht,iter); \
588: return(0); \
589: } \
590: \
591: PETSC_STATIC_INLINE PETSC_UNUSED \
592: PetscErrorCode Petsc##HashT##QuerySet(Petsc##HashT ht,KeyType key,ValType val,PetscBool *missing) \
593: { \
594: int ret; \
595: khiter_t iter; \
599: iter = kh_put(HashT,ht,key,&ret); \
600: PetscHashAssert(ret>=0); \
601: kh_val(ht,iter) = val; \
602: *missing = ret ? PETSC_TRUE : PETSC_FALSE; \
603: return(0); \
604: } \
605: \
606: PETSC_STATIC_INLINE PETSC_UNUSED \
607: PetscErrorCode Petsc##HashT##QueryDel(Petsc##HashT ht,KeyType key,PetscBool *present) \
608: { \
609: khiter_t iter; \
613: iter = kh_get(HashT,ht,key); \
614: if (iter != kh_end(ht)) { \
615: kh_del(HashT,ht,iter); \
616: *present = PETSC_TRUE; \
617: } else { \
618: *present = PETSC_FALSE; \
619: } \
620: return(0); \
621: } \
622: \
623: PETSC_STATIC_INLINE PETSC_UNUSED \
624: PetscErrorCode Petsc##HashT##Find(Petsc##HashT ht,KeyType key,PetscHashIter *iter,PetscBool *found) \
625: \
626: { \
631: *iter = kh_get(HashT,ht,key); \
632: *found = (*iter != kh_end(ht)) ? PETSC_TRUE : PETSC_FALSE; \
633: return(0); \
634: } \
635: \
636: PETSC_STATIC_INLINE PETSC_UNUSED \
637: PetscErrorCode Petsc##HashT##Put(Petsc##HashT ht,KeyType key,PetscHashIter *iter,PetscBool *missing) \
638: { \
639: int ret; \
644: *iter = kh_put(HashT,ht,key,&ret); \
645: PetscHashAssert(ret>=0); \
646: *missing = ret ? PETSC_TRUE : PETSC_FALSE; \
647: return(0); \
648: } \
649: \
650: PETSC_STATIC_INLINE PETSC_UNUSED \
651: PetscErrorCode Petsc##HashT##IterGet(Petsc##HashT ht,PetscHashIter iter,ValType *val) \
652: { \
656: *val = PetscLikely(iter < kh_end(ht) && kh_exist(ht,iter)) ? kh_val(ht,iter) : (DefaultValue); \
657: return(0); \
658: } \
659: \
660: PETSC_STATIC_INLINE PETSC_UNUSED \
661: PetscErrorCode Petsc##HashT##IterSet(Petsc##HashT ht,PetscHashIter iter,ValType val) \
662: { \
665: if (PetscLikely(iter < kh_end(ht) && kh_exist(ht,iter))) kh_val(ht,iter) = val; \
666: return(0); \
667: } \
668: \
669: PETSC_STATIC_INLINE PETSC_UNUSED \
670: PetscErrorCode Petsc##HashT##IterDel(Petsc##HashT ht,PetscHashIter iter) \
671: { \
674: if (PetscLikely(iter < kh_end(ht))) kh_del(HashT,ht,iter); \
675: return(0); \
676: } \
677: \
678: PETSC_STATIC_INLINE PETSC_UNUSED \
679: PetscErrorCode Petsc##HashT##GetKeys(Petsc##HashT ht,PetscInt *off,KeyType array[]) \
680: { \
681: KeyType key; \
682: PetscInt pos; \
686: pos = *off; \
687: kh_foreach_key(ht,key,array[pos++] = key); \
688: *off = pos; \
689: return(0); \
690: } \
691: \
692: PETSC_STATIC_INLINE PETSC_UNUSED \
693: PetscErrorCode Petsc##HashT##GetVals(Petsc##HashT ht,PetscInt *off,ValType array[]) \
694: { \
695: ValType val; \
696: PetscInt pos; \
700: pos = *off; \
701: kh_foreach_value(ht,val,array[pos++] = val); \
702: *off = pos; \
703: return(0); \
704: } \
706: #endif /* PETSC_HASHMAP_H */