Actual source code: hashmap.h
petsc-3.13.6 2020-09-29
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: .seealso: PetscHMapT, PetscHMapTCreate()
24: M*/
26: /*S
27: PetscHMapT - Hash table map
29: Synopsis:
30: typedef khash_t(HMapT) *PetscHMapT;
32: Level: developer
34: .seealso: PETSC_HASH_MAP(), PetscHMapTCreate()
35: S*/
37: /*MC
38: PetscHMapTCreate - Create a hash table
40: Synopsis:
41: #include <petsc/private/hashmap.h>
42: PetscErrorCode PetscHMapTCreate(PetscHMapT *ht)
44: Output Parameter:
45: . ht - The hash table
47: Level: developer
49: .seealso: PetscHMapTDestroy()
50: M*/
52: /*MC
53: PetscHMapTDestroy - Destroy a hash table
55: Synopsis:
56: #include <petsc/private/hashmap.h>
57: PetscErrorCode PetscHMapTDestroy(PetscHMapT *ht)
59: Input Parameter:
60: . ht - The hash table
62: Level: developer
64: .seealso: PetscHMapTCreate()
65: M*/
67: /*MC
68: PetscHMapTReset - Reset a hash table
70: Synopsis:
71: #include <petsc/private/hashmap.h>
72: PetscErrorCode PetscHMapTReset(PetscHMapT ht)
74: Input Parameter:
75: . ht - The hash table
77: Level: developer
79: .seealso: PetscHMapTClear()
80: M*/
82: /*MC
83: PetscHMapTDuplicate - Duplicate a hash table
85: Synopsis:
86: #include <petsc/private/hashmap.h>
87: PetscErrorCode PetscHMapTDuplicate(PetscHMapT ht,PetscHMapT *hd)
89: Input Parameter:
90: . ht - The source hash table
92: Output Parameter:
93: . ht - The duplicated hash table
95: Level: developer
97: .seealso: PetscHMapTCreate()
98: M*/
100: /*MC
101: PetscHMapTClear - Clear a hash table
103: Synopsis:
104: #include <petsc/private/hashmap.h>
105: PetscErrorCode PetscHMapTClear(PetscHMapT ht)
107: Input Parameter:
108: . ht - The hash table
110: Level: developer
112: .seealso: PetscHMapTReset()
113: M*/
115: /*MC
116: PetscHMapTResize - Set the number of buckets in a hash table
118: Synopsis:
119: #include <petsc/private/hashmap.h>
120: PetscErrorCode PetscHMapTResize(PetscHMapT ht,PetscInt nb)
122: Input Parameters:
123: + ht - The hash table
124: - nb - The number of buckets
126: Level: developer
128: .seealso: PetscHMapTCreate()
129: M*/
131: /*MC
132: PetscHMapTGetSize - Get the number of entries in a hash table
134: Synopsis:
135: #include <petsc/private/hashmap.h>
136: PetscErrorCode PetscHMapTGetSize(PetscHMapT ht,PetscInt *n)
138: Input Parameter:
139: . ht - The hash table
141: Output Parameter:
142: . n - The number of entries
144: Level: developer
146: .seealso: PetscHMapTResize()
147: M*/
149: /*MC
150: PetscHMapTGetCapacity - Get the current size of the array in the hash table
152: Synopsis:
153: #include <petsc/private/hashmap.h>
154: PetscErrorCode PetscHMapTGetCapacity(PetscHMapT ht,PetscInt *n)
156: Input Parameter:
157: . ht - The hash table
159: Output Parameter:
160: . n - The capacity
162: Level: developer
164: .seealso: PetscHMapTResize(), PetscHMapTGetSize()
165: M*/
167: /*MC
168: PetscHMapTHas - Query for a key in the hash table
170: Synopsis:
171: #include <petsc/private/hashmap.h>
172: PetscErrorCode PetscHMapTHas(PetscHMapT ht,KeyType key,PetscBool *has)
174: Input Parameters:
175: + ht - The hash table
176: - key - The key
178: Output Parameter:
179: . has - Boolean indicating whether key is in the hash table
181: Level: developer
183: .seealso: PetscHMapTGet(), PetscHMapTSet(), PetscHMapTFind()
184: M*/
186: /*MC
187: PetscHMapTGet - Get the value for a key in the hash table
189: Synopsis:
190: #include <petsc/private/hashmap.h>
191: PetscErrorCode PetscHMapTGet(PetscHMapT ht,KeyType key,ValType *val)
193: Input Parameters:
194: + ht - The hash table
195: - key - The key
197: Output Parameter:
198: . val - The value
200: Level: developer
202: .seealso: PetscHMapTSet(), PetscHMapTIterGet()
203: M*/
205: /*MC
206: PetscHMapTSet - Set a (key,value) entry in the hash table
208: Synopsis:
209: #include <petsc/private/hashmap.h>
210: PetscErrorCode PetscHMapTSet(PetscHMapT ht,KeyType key,ValType val)
212: Input Parameters:
213: + ht - The hash table
214: . key - The key
215: - val - The value
217: Level: developer
219: .seealso: PetscHMapTGet(), PetscHMapTIterSet()
220: M*/
222: /*MC
223: PetscHMapTDel - Remove a key and its value from the hash table
225: Synopsis:
226: #include <petsc/private/hashmap.h>
227: PetscErrorCode PetscHMapTDel(PetscHMapT ht,KeyType key)
229: Input Parameters:
230: + ht - The hash table
231: - key - The key
233: Level: developer
235: .seealso: PetscHMapTHas(), PetscHMapTIterDel()
236: M*/
238: /*MC
239: PetscHMapTQuerySet - Query and set a (key,value) entry in the hash table
241: Synopsis:
242: #include <petsc/private/hashmap.h>
243: PetscErrorCode PetscHMapTQuerySet(PetscHMapT ht,KeyType key,ValType val,PetscBool *missing)
245: Input Parameters:
246: + ht - The hash table
247: . key - The key
248: - val - The value
250: Output Parameter:
251: . missing - Boolean indicating whether the key was missing
253: Level: developer
255: .seealso: PetscHMapTQueryDel(), PetscHMapTSet()
256: M*/
258: /*MC
259: PetscHMapTQueryDel - Query and remove a (key,value) entry from the hash table
261: Synopsis:
262: #include <petsc/private/hashmap.h>
263: PetscErrorCode PetscHMapTQueryDel(PetscHMapT ht,KeyType key,PetscBool *present)
265: Input Parameters:
266: + ht - The hash table
267: - key - The key
269: Output Parameter:
270: . present - Boolean indicating whether the key was present
272: Level: developer
274: .seealso: PetscHMapTQuerySet(), PetscHMapTDel()
275: M*/
277: /*MC
278: PetscHMapTFind - Query for key in the hash table
280: Synopsis:
281: #include <petsc/private/hashmap.h>
282: PetscErrorCode PetscHMapTFind(PetscHMapT ht,KeyType key,PetscHashIter *iter,PetscBool *found)
284: Input Parameters:
285: + ht - The hash table
286: - key - The key
288: Output Parameter:
289: + iter - Iterator referencing the value for key
290: - found - Boolean indicating whether the key was present
292: Level: developer
294: .seealso: PetscHMapTIterGet(), PetscHMapTIterDel()
295: M*/
297: /*MC
298: PetscHMapTPut - Set a key in the hash table
300: Synopsis:
301: #include <petsc/private/hashmap.h>
302: PetscErrorCode PetscHMapTPut(PetscHMapT ht,KeyType key,PetscHashIter *iter,PetscBool *missing)
304: Input Parameters:
305: + ht - The hash table
306: - key - The key
308: Output Parameter:
309: + iter - Iterator referencing the value for key
310: - missing - Boolean indicating whether the key was missing
312: Level: developer
314: .seealso: PetscHMapTIterSet(), PetscHMapTQuerySet(), PetscHMapTSet()
315: M*/
317: /*MC
318: PetscHMapTIterGet - Get the value referenced by an iterator in the hash table
320: Synopsis:
321: #include <petsc/private/hashmap.h>
322: PetscErrorCode PetscHMapTIterGet(PetscHMapT ht,PetscHashIter iter,ValType *val)
324: Input Parameters:
325: + ht - The hash table
326: - iter - The iterator
328: Output Parameter:
329: . val - The value
331: Level: developer
333: .seealso: PetscHMapTFind(), PetscHMapTGet()
334: M*/
336: /*MC
337: PetscHMapTIterSet - Set the value referenced by an iterator in the hash
339: Synopsis:
340: #include <petsc/private/hashmap.h>
341: PetscErrorCode PetscHMapTIterSet(PetscHMapT ht,PetscHashIter iter,ValType val)
343: Input Parameters:
344: + ht - The hash table
345: . iter - The iterator
346: - val - The value
348: Level: developer
350: .seealso: PetscHMapTPut(), PetscHMapTQuerySet(), PetscHMapTSet()
351: M*/
353: /*MC
354: PetscHMapTIterDel - Remove the (key,value) referenced by an iterator from the hash table
356: Synopsis:
357: #include <petsc/private/hashmap.h>
358: PetscErrorCode PetscHMapTIterDel(PetscHMapT ht,PetscHashIter iter)
360: Input Parameters:
361: + ht - The hash table
362: - iter - The iterator
364: Level: developer
366: .seealso: PetscHMapTFind(), PetscHMapTQueryDel(), PetscHMapTDel()
367: M*/
369: /*MC
370: PetscHMapTGetKeys - Get all keys from a hash table
372: Synopsis:
373: #include <petsc/private/hashmap.h>
374: PetscErrorCode PetscHMapTGetKeys(PetscHMapT ht,PetscInt *off,KeyType array[])
376: Input Parameters:
377: + ht - The hash table
378: . off - Input offset in array (usually zero)
379: - array - Array where to put hash table keys into
381: Output Parameter:
382: + off - Output offset in array (output offset = input offset + hash table size)
383: - array - Array filled with the hash table keys
385: Level: developer
387: .seealso: PetscHSetTGetSize(), PetscHMapTGetVals()
388: M*/
390: /*MC
391: PetscHMapTGetVals - Get all values from a hash table
393: Synopsis:
394: #include <petsc/private/hashmap.h>
395: PetscErrorCode PetscHMapTGetVals(PetscHMapT ht,PetscInt *off,ValType array[])
397: Input Parameters:
398: + ht - The hash table
399: . off - Input offset in array (usually zero)
400: - array - Array where to put hash table values into
402: Output Parameter:
403: + off - Output offset in array (output offset = input offset + hash table size)
404: - array - Array filled with the hash table values
406: Level: developer
408: .seealso: PetscHSetTGetSize(), PetscHMapTGetKeys()
409: M*/
411: /*MC
412: PetscHMapTGetPairs - Get all (key,value) pairs from a hash table
414: Synopsis:
415: #include <petsc/private/hashmap.h>
416: PetscErrorCode PetscHMapTGetPairs(PetscHMapT ht,PetscInt *off,KeyType karray[],ValType varray[])
418: Input Parameters:
419: + ht - The hash table
420: . off - Input offset in array (usually zero)
421: - karray - Array where to put hash table keys into
422: - varray - Array where to put hash table values into
424: Output Parameter:
425: + off - Output offset in array (output offset = input offset + hash table size)
426: - karray - Array filled with the hash table keys
427: - varray - Array filled with the hash table values
429: Level: developer
431: .seealso: PetscHSetTGetSize(), PetscHMapTGetKeys(), PetscHMapTGetVals()
432: M*/
434: #define PETSC_HASH_MAP(HashT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue) \
435: \
436: KHASH_INIT(HashT, KeyType, ValType, 1, HashFunc, EqualFunc) \
437: \
438: typedef khash_t(HashT) *Petsc##HashT; \
439: \
440: PETSC_STATIC_INLINE PETSC_UNUSED \
441: PetscErrorCode Petsc##HashT##Create(Petsc##HashT *ht) \
442: { \
445: *ht = kh_init(HashT); \
446: PetscHashAssert(*ht!=NULL); \
447: return(0); \
448: } \
449: \
450: PETSC_STATIC_INLINE PETSC_UNUSED \
451: PetscErrorCode Petsc##HashT##Destroy(Petsc##HashT *ht) \
452: { \
455: if (!*ht) return(0); \
456: kh_destroy(HashT,*ht); *ht = NULL; \
457: return(0); \
458: } \
459: \
460: PETSC_STATIC_INLINE PETSC_UNUSED \
461: PetscErrorCode Petsc##HashT##Reset(Petsc##HashT ht) \
462: { \
465: kh_reset(HashT,ht); \
466: return(0); \
467: } \
468: \
469: PETSC_STATIC_INLINE PETSC_UNUSED \
470: PetscErrorCode Petsc##HashT##Duplicate(Petsc##HashT ht,Petsc##HashT *hd) \
471: { \
472: int ret; \
473: KeyType key; \
474: ValType val; \
478: *hd = kh_init(HashT); \
479: PetscHashAssert(*hd!=NULL); \
480: ret = kh_resize(HashT,*hd,kh_size(ht)); \
481: PetscHashAssert(ret==0); \
482: kh_foreach(ht,key,val,{ khiter_t i; \
483: i = kh_put(HashT,*hd,key,&ret); \
484: PetscHashAssert(ret>=0); \
485: kh_val(*hd,i) = val;}) \
486: return(0); \
487: } \
488: \
489: PETSC_STATIC_INLINE PETSC_UNUSED \
490: PetscErrorCode Petsc##HashT##Clear(Petsc##HashT ht) \
491: { \
494: kh_clear(HashT,ht); \
495: return(0); \
496: } \
497: \
498: PETSC_STATIC_INLINE PETSC_UNUSED \
499: PetscErrorCode Petsc##HashT##Resize(Petsc##HashT ht,PetscInt nb) \
500: { \
501: int ret; \
504: ret = kh_resize(HashT,ht,(khint_t)nb); \
505: PetscHashAssert(ret>=0); \
506: return(0); \
507: } \
508: \
509: PETSC_STATIC_INLINE PETSC_UNUSED \
510: PetscErrorCode Petsc##HashT##GetSize(Petsc##HashT ht,PetscInt *n) \
511: { \
515: *n = (PetscInt)kh_size(ht); \
516: return(0); \
517: } \
518: \
519: PETSC_STATIC_INLINE PETSC_UNUSED \
520: PetscErrorCode Petsc##HashT##GetCapacity(Petsc##HashT ht,PetscInt *n) \
521: { \
525: *n = (PetscInt)kh_n_buckets(ht); \
526: return(0); \
527: } \
528: \
529: PETSC_STATIC_INLINE PETSC_UNUSED \
530: PetscErrorCode Petsc##HashT##Has(Petsc##HashT ht,KeyType key,PetscBool *has) \
531: { \
532: khiter_t iter; \
536: iter = kh_get(HashT,ht,key); \
537: *has = (iter != kh_end(ht)) ? PETSC_TRUE : PETSC_FALSE; \
538: return(0); \
539: } \
540: \
541: PETSC_STATIC_INLINE PETSC_UNUSED \
542: PetscErrorCode Petsc##HashT##Get(Petsc##HashT ht,KeyType key,ValType *val) \
543: { \
544: khiter_t iter; \
548: iter = kh_get(HashT,ht,key); \
549: *val = (iter != kh_end(ht)) ? kh_val(ht,iter) : (DefaultValue); \
550: return(0); \
551: } \
552: \
553: PETSC_STATIC_INLINE PETSC_UNUSED \
554: PetscErrorCode Petsc##HashT##Set(Petsc##HashT ht,KeyType key,ValType val) \
555: { \
556: int ret; \
557: khiter_t iter; \
560: iter = kh_put(HashT,ht,key,&ret); \
561: PetscHashAssert(ret>=0); \
562: kh_val(ht,iter) = val; \
563: return(0); \
564: } \
565: \
566: PETSC_STATIC_INLINE PETSC_UNUSED \
567: PetscErrorCode Petsc##HashT##Del(Petsc##HashT ht,KeyType key) \
568: { \
569: khiter_t iter; \
572: iter = kh_get(HashT,ht,key); \
573: kh_del(HashT,ht,iter); \
574: return(0); \
575: } \
576: \
577: PETSC_STATIC_INLINE PETSC_UNUSED \
578: PetscErrorCode Petsc##HashT##QuerySet(Petsc##HashT ht,KeyType key,ValType val,PetscBool *missing) \
579: { \
580: int ret; \
581: khiter_t iter; \
585: iter = kh_put(HashT,ht,key,&ret); \
586: PetscHashAssert(ret>=0); \
587: kh_val(ht,iter) = val; \
588: *missing = ret ? PETSC_TRUE : PETSC_FALSE; \
589: return(0); \
590: } \
591: \
592: PETSC_STATIC_INLINE PETSC_UNUSED \
593: PetscErrorCode Petsc##HashT##QueryDel(Petsc##HashT ht,KeyType key,PetscBool *present) \
594: { \
595: khiter_t iter; \
599: iter = kh_get(HashT,ht,key); \
600: if (iter != kh_end(ht)) { \
601: kh_del(HashT,ht,iter); \
602: *present = PETSC_TRUE; \
603: } else { \
604: *present = PETSC_FALSE; \
605: } \
606: return(0); \
607: } \
608: \
609: PETSC_STATIC_INLINE PETSC_UNUSED \
610: PetscErrorCode Petsc##HashT##Find(Petsc##HashT ht,KeyType key,PetscHashIter *iter,PetscBool *found) \
611: \
612: { \
617: *iter = kh_get(HashT,ht,key); \
618: *found = (*iter != kh_end(ht)) ? PETSC_TRUE : PETSC_FALSE; \
619: return(0); \
620: } \
621: \
622: PETSC_STATIC_INLINE PETSC_UNUSED \
623: PetscErrorCode Petsc##HashT##Put(Petsc##HashT ht,KeyType key,PetscHashIter *iter,PetscBool *missing) \
624: { \
625: int ret; \
630: *iter = kh_put(HashT,ht,key,&ret); \
631: PetscHashAssert(ret>=0); \
632: *missing = ret ? PETSC_TRUE : PETSC_FALSE; \
633: return(0); \
634: } \
635: \
636: PETSC_STATIC_INLINE PETSC_UNUSED \
637: PetscErrorCode Petsc##HashT##IterGet(Petsc##HashT ht,PetscHashIter iter,ValType *val) \
638: { \
642: *val = PetscLikely(iter < kh_end(ht) && kh_exist(ht,iter)) ? kh_val(ht,iter) : (DefaultValue); \
643: return(0); \
644: } \
645: \
646: PETSC_STATIC_INLINE PETSC_UNUSED \
647: PetscErrorCode Petsc##HashT##IterSet(Petsc##HashT ht,PetscHashIter iter,ValType val) \
648: { \
651: if (PetscLikely(iter < kh_end(ht) && kh_exist(ht,iter))) kh_val(ht,iter) = val; \
652: return(0); \
653: } \
654: \
655: PETSC_STATIC_INLINE PETSC_UNUSED \
656: PetscErrorCode Petsc##HashT##IterDel(Petsc##HashT ht,PetscHashIter iter) \
657: { \
660: if (PetscLikely(iter < kh_end(ht))) kh_del(HashT,ht,iter); \
661: return(0); \
662: } \
663: \
664: PETSC_STATIC_INLINE PETSC_UNUSED \
665: PetscErrorCode Petsc##HashT##GetKeys(Petsc##HashT ht,PetscInt *off,KeyType array[]) \
666: { \
667: KeyType key; \
668: PetscInt pos; \
672: pos = *off; \
673: kh_foreach_key(ht,key,array[pos++] = key); \
674: *off = pos; \
675: return(0); \
676: } \
677: \
678: PETSC_STATIC_INLINE PETSC_UNUSED \
679: PetscErrorCode Petsc##HashT##GetVals(Petsc##HashT ht,PetscInt *off,ValType array[]) \
680: { \
681: ValType val; \
682: PetscInt pos; \
686: pos = *off; \
687: kh_foreach_value(ht,val,array[pos++] = val); \
688: *off = pos; \
689: return(0); \
690: } \
691: \
692: \
693: PETSC_STATIC_INLINE PETSC_UNUSED \
694: PetscErrorCode Petsc##HashT##GetPairs(Petsc##HashT ht,PetscInt *off,KeyType karray[],ValType varray[]) \
695: { \
696: ValType val; \
697: KeyType key; \
698: PetscInt pos; \
702: pos = *off; \
703: kh_foreach(ht,key,val, \
704: { karray[pos] = key; \
705: varray[pos++] = val;}) \
706: *off = pos; \
707: return(0); \
708: } \
710: #endif /* PETSC_HASHMAP_H */