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