Actual source code: hashmap.h
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 Parameters:
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 Parameters:
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 Parameters:
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 Parameters:
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 Parameters:
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: static inline PETSC_UNUSED \
441: PetscErrorCode Petsc##HashT##Create(Petsc##HashT *ht) \
442: { \
444: *ht = kh_init(HashT); \
445: PetscHashAssert(*ht!=NULL); \
446: return 0; \
447: } \
448: \
449: static inline PETSC_UNUSED \
450: PetscErrorCode Petsc##HashT##Destroy(Petsc##HashT *ht) \
451: { \
453: if (!*ht) return 0; \
454: kh_destroy(HashT,*ht); *ht = NULL; \
455: return 0; \
456: } \
457: \
458: static inline PETSC_UNUSED \
459: PetscErrorCode Petsc##HashT##Reset(Petsc##HashT ht) \
460: { \
462: kh_reset(HashT,ht); \
463: return 0; \
464: } \
465: \
466: static inline PETSC_UNUSED \
467: PetscErrorCode Petsc##HashT##Duplicate(Petsc##HashT ht,Petsc##HashT *hd) \
468: { \
469: int ret; \
470: KeyType key; \
471: ValType val; \
474: *hd = kh_init(HashT); \
475: PetscHashAssert(*hd!=NULL); \
476: ret = kh_resize(HashT,*hd,kh_size(ht)); \
477: PetscHashAssert(ret==0); \
478: kh_foreach(ht,key,val,{ 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 \
486: PetscErrorCode Petsc##HashT##Clear(Petsc##HashT ht) \
487: { \
489: kh_clear(HashT,ht); \
490: return 0; \
491: } \
492: \
493: static inline PETSC_UNUSED \
494: PetscErrorCode Petsc##HashT##Resize(Petsc##HashT ht,PetscInt nb) \
495: { \
496: int ret; \
498: ret = kh_resize(HashT,ht,(khint_t)nb); \
499: PetscHashAssert(ret>=0); \
500: return 0; \
501: } \
502: \
503: static inline PETSC_UNUSED \
504: PetscErrorCode Petsc##HashT##GetSize(Petsc##HashT ht,PetscInt *n) \
505: { \
508: *n = (PetscInt)kh_size(ht); \
509: return 0; \
510: } \
511: \
512: static inline PETSC_UNUSED \
513: PetscErrorCode Petsc##HashT##GetCapacity(Petsc##HashT ht,PetscInt *n) \
514: { \
517: *n = (PetscInt)kh_n_buckets(ht); \
518: return 0; \
519: } \
520: \
521: static inline PETSC_UNUSED \
522: PetscErrorCode Petsc##HashT##Has(Petsc##HashT ht,KeyType key,PetscBool *has) \
523: { \
524: khiter_t iter; \
528: iter = kh_get(HashT,ht,key); \
529: *has = (iter != kh_end(ht)) ? PETSC_TRUE : PETSC_FALSE; \
530: return 0; \
531: } \
532: \
533: static inline PETSC_UNUSED \
534: PetscErrorCode Petsc##HashT##Get(Petsc##HashT ht,KeyType key,ValType *val) \
535: { \
536: khiter_t iter; \
540: iter = kh_get(HashT,ht,key); \
541: *val = (iter != kh_end(ht)) ? kh_val(ht,iter) : (DefaultValue); \
542: return 0; \
543: } \
544: \
545: static inline PETSC_UNUSED \
546: PetscErrorCode Petsc##HashT##Set(Petsc##HashT ht,KeyType key,ValType val) \
547: { \
548: int ret; \
549: khiter_t iter; \
552: iter = kh_put(HashT,ht,key,&ret); \
553: PetscHashAssert(ret>=0); \
554: kh_val(ht,iter) = val; \
555: return 0; \
556: } \
557: \
558: static inline PETSC_UNUSED \
559: PetscErrorCode Petsc##HashT##Del(Petsc##HashT ht,KeyType key) \
560: { \
561: khiter_t iter; \
564: iter = kh_get(HashT,ht,key); \
565: kh_del(HashT,ht,iter); \
566: return 0; \
567: } \
568: \
569: static inline PETSC_UNUSED \
570: PetscErrorCode Petsc##HashT##QuerySet(Petsc##HashT ht,KeyType key,ValType val,PetscBool *missing) \
571: { \
572: int ret; \
573: khiter_t iter; \
577: iter = kh_put(HashT,ht,key,&ret); \
578: PetscHashAssert(ret>=0); \
579: kh_val(ht,iter) = val; \
580: *missing = ret ? PETSC_TRUE : PETSC_FALSE; \
581: return 0; \
582: } \
583: \
584: static inline PETSC_UNUSED \
585: PetscErrorCode Petsc##HashT##QueryDel(Petsc##HashT ht,KeyType key,PetscBool *present) \
586: { \
587: khiter_t iter; \
591: iter = kh_get(HashT,ht,key); \
592: if (iter != kh_end(ht)) { \
593: kh_del(HashT,ht,iter); \
594: *present = PETSC_TRUE; \
595: } else { \
596: *present = PETSC_FALSE; \
597: } \
598: return 0; \
599: } \
600: \
601: static inline PETSC_UNUSED \
602: PetscErrorCode Petsc##HashT##Find(Petsc##HashT ht,KeyType key,PetscHashIter *iter,PetscBool *found) \
603: \
604: { \
609: *iter = kh_get(HashT,ht,key); \
610: *found = (*iter != kh_end(ht)) ? PETSC_TRUE : PETSC_FALSE; \
611: return 0; \
612: } \
613: \
614: static inline PETSC_UNUSED \
615: PetscErrorCode Petsc##HashT##Put(Petsc##HashT ht,KeyType key,PetscHashIter *iter,PetscBool *missing) \
616: { \
617: int ret; \
622: *iter = kh_put(HashT,ht,key,&ret); \
623: PetscHashAssert(ret>=0); \
624: *missing = ret ? PETSC_TRUE : PETSC_FALSE; \
625: return 0; \
626: } \
627: \
628: static inline PETSC_UNUSED \
629: PetscErrorCode Petsc##HashT##IterGet(Petsc##HashT ht,PetscHashIter iter,ValType *val) \
630: { \
634: *val = PetscLikely(iter < kh_end(ht) && kh_exist(ht,iter)) ? kh_val(ht,iter) : (DefaultValue); \
635: return 0; \
636: } \
637: \
638: static inline PETSC_UNUSED \
639: PetscErrorCode Petsc##HashT##IterSet(Petsc##HashT ht,PetscHashIter iter,ValType val) \
640: { \
643: if (PetscLikely(iter < kh_end(ht) && kh_exist(ht,iter))) kh_val(ht,iter) = val; \
644: return 0; \
645: } \
646: \
647: static inline PETSC_UNUSED \
648: PetscErrorCode Petsc##HashT##IterDel(Petsc##HashT ht,PetscHashIter iter) \
649: { \
652: if (PetscLikely(iter < kh_end(ht))) kh_del(HashT,ht,iter); \
653: return 0; \
654: } \
655: \
656: static inline PETSC_UNUSED \
657: PetscErrorCode Petsc##HashT##GetKeys(Petsc##HashT ht,PetscInt *off,KeyType array[]) \
658: { \
659: KeyType key; \
660: PetscInt pos; \
663: pos = *off; \
664: kh_foreach_key(ht,key,array[pos++] = key); \
665: *off = pos; \
666: return 0; \
667: } \
668: \
669: static inline PETSC_UNUSED \
670: PetscErrorCode Petsc##HashT##GetVals(Petsc##HashT ht,PetscInt *off,ValType array[]) \
671: { \
672: ValType val; \
673: PetscInt pos; \
676: pos = *off; \
677: kh_foreach_value(ht,val,array[pos++] = val); \
678: *off = pos; \
679: return 0; \
680: } \
681: \
682: \
683: static inline PETSC_UNUSED \
684: PetscErrorCode Petsc##HashT##GetPairs(Petsc##HashT ht,PetscInt *off,KeyType karray[],ValType varray[]) \
685: { \
686: ValType val; \
687: KeyType key; \
688: PetscInt pos; \
691: pos = *off; \
692: kh_foreach(ht,key,val, \
693: { karray[pos] = key; \
694: varray[pos++] = val;}) \
695: *off = pos; \
696: return 0; \
697: } \
699: #endif /* PETSC_HASHMAP_H */