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 */