Actual source code: hashmap.h

petsc-3.11.3 2019-06-26
Report Typos and Errors
  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 */