Actual source code: hashmap.h

      1: #pragma once

      3: #include <petsc/private/hashtable.h>

      5: /* SUBMANSEC = PetscH */

      7: /*MC
      8:   PETSC_HASH_MAP - Instantiate a PETSc hash table map type

     10:   Synopsis:
     11: #include <petsc/private/hashmap.h>
     12:   PETSC_HASH_MAP(HMapT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue)

     14:   Input Parameters:
     15: + HMapT - The hash table map type name suffix
     16: . KeyType - The type of keys
     17: . ValType - The type of values
     18: . HashFunc - Routine or function-like macro computing hash values from keys
     19: . EqualFunc - Routine or function-like macro computing whether two values are equal
     20: - DefaultValue - Default value to use for queries in case of missing keys

     22:   Level: developer

     24:   Note:
     25:   This code uses the standalone and portable C language khash software <https://github.com/attractivechaos/klib>

     27:   Developer Note:
     28:   Each time this macro is used to create a new hash map type, the make rule for allmanpages in $PETSC_DIR/makefile should
     29:   be updated to cause the automatic generation of appropriate manual pages for that type. The manual pages
     30:   are generated from the templated version of the documentation in include/petsc/private/hashmap.txt.

     32: .seealso: `PETSC_HASH_MAP_DECL()`, `PetscHMapI`, `PetscHMapICreate()`, `PetscHMapIJ`,
     33: `PetscHMapIJCreate()`, `PETSC_HASH_SET()`
     34: M*/

     36: #define PETSC_HASH_MAP_DECL(HashT, KeyType, ValType) \
     37:   typedef kh_##HashT##_t                   *Petsc##HashT; \
     38:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Create(Petsc##HashT *); \
     39:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##CreateWithSize(PetscInt, Petsc##HashT *); \
     40:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Destroy(Petsc##HashT *); \
     41:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Reset(Petsc##HashT); \
     42:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Duplicate(Petsc##HashT, Petsc##HashT *); \
     43:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Clear(Petsc##HashT); \
     44:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Resize(Petsc##HashT, PetscInt); \
     45:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetSize(Petsc##HashT, PetscInt *); \
     46:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetCapacity(Petsc##HashT, PetscInt *); \
     47:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Has(Petsc##HashT, KeyType, PetscBool *); \
     48:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Get(Petsc##HashT, KeyType, ValType *); \
     49:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetWithDefault(Petsc##HashT, KeyType, ValType, ValType *); \
     50:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Set(Petsc##HashT, KeyType, ValType); \
     51:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Del(Petsc##HashT, KeyType); \
     52:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##QuerySet(Petsc##HashT, KeyType, ValType, PetscBool *); \
     53:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##QueryDel(Petsc##HashT, KeyType, PetscBool *); \
     54:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Find(Petsc##HashT, KeyType, PetscHashIter *, PetscBool *); \
     55:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Put(Petsc##HashT, KeyType, PetscHashIter *, PetscBool *); \
     56:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterGet(Petsc##HashT, PetscHashIter, ValType *); \
     57:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterSet(Petsc##HashT, PetscHashIter, ValType); \
     58:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterDel(Petsc##HashT, PetscHashIter); \
     59:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetKeys(Petsc##HashT, PetscInt *, KeyType[]); \
     60:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetVals(Petsc##HashT, PetscInt *, ValType[]); \
     61:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetPairs(Petsc##HashT, PetscInt *, KeyType[], ValType[])

     63: #define PETSC_HASH_MAP(HashT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue) \
     64: \
     65:   KHASH_INIT(HashT, KeyType, ValType, 1, HashFunc, EqualFunc) \
     66:   PETSC_HASH_MAP_DECL(HashT, KeyType, ValType); \
     67: \
     68:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Create(Petsc##HashT *ht) \
     69:   { \
     70:     PetscFunctionBegin; \
     71:     PetscAssertPointer(ht, 1); \
     72:     *ht = kh_init(HashT); \
     73:     PetscHashAssert(*ht != NULL); \
     74:     PetscFunctionReturn(PETSC_SUCCESS); \
     75:   } \
     76: \
     77:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##CreateWithSize(PetscInt n, Petsc##HashT *ht) \
     78:   { \
     79:     PetscFunctionBegin; \
     80:     PetscAssert(n >= 0, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Hash table size %" PetscInt_FMT " must be >= 0", n); \
     81:     PetscAssertPointer(ht, 2); \
     82:     PetscCall(Petsc##HashT##Create(ht)); \
     83:     if (n) PetscCall(Petsc##HashT##Resize(*ht, n)); \
     84:     PetscFunctionReturn(PETSC_SUCCESS); \
     85:   } \
     86: \
     87:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Destroy(Petsc##HashT *ht) \
     88:   { \
     89:     PetscFunctionBegin; \
     90:     PetscAssertPointer(ht, 1); \
     91:     if (!*ht) PetscFunctionReturn(PETSC_SUCCESS); \
     92:     kh_destroy(HashT, *ht); \
     93:     *ht = NULL; \
     94:     PetscFunctionReturn(PETSC_SUCCESS); \
     95:   } \
     96: \
     97:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Reset(Petsc##HashT ht) \
     98:   { \
     99:     PetscFunctionBegin; \
    100:     PetscAssertPointer(ht, 1); \
    101:     kh_reset(HashT, ht); \
    102:     PetscFunctionReturn(PETSC_SUCCESS); \
    103:   } \
    104: \
    105:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Duplicate(Petsc##HashT ht, Petsc##HashT *hd) \
    106:   { \
    107:     int     ret; \
    108:     KeyType key; \
    109:     ValType val; \
    110:     PetscFunctionBegin; \
    111:     PetscAssertPointer(ht, 1); \
    112:     PetscAssertPointer(hd, 2); \
    113:     *hd = kh_init(HashT); \
    114:     PetscHashAssert(*hd != NULL); \
    115:     ret = kh_resize(HashT, *hd, kh_size(ht)); \
    116:     PetscHashAssert(ret == 0); \
    117:     kh_foreach(ht, key, val, { \
    118:       khiter_t i; \
    119:       i = kh_put(HashT, *hd, key, &ret); \
    120:       PetscHashAssert(ret >= 0); \
    121:       kh_val(*hd, i) = val; \
    122:     }) PetscFunctionReturn(PETSC_SUCCESS); \
    123:   } \
    124: \
    125:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Clear(Petsc##HashT ht) \
    126:   { \
    127:     PetscFunctionBegin; \
    128:     PetscAssertPointer(ht, 1); \
    129:     kh_clear(HashT, ht); \
    130:     PetscFunctionReturn(PETSC_SUCCESS); \
    131:   } \
    132: \
    133:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Resize(Petsc##HashT ht, PetscInt nb) \
    134:   { \
    135:     int ret; \
    136:     PetscFunctionBegin; \
    137:     PetscAssertPointer(ht, 1); \
    138:     ret = kh_resize(HashT, ht, (khint_t)nb); \
    139:     PetscHashAssert(ret >= 0); \
    140:     PetscFunctionReturn(PETSC_SUCCESS); \
    141:   } \
    142: \
    143:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetSize(Petsc##HashT ht, PetscInt *n) \
    144:   { \
    145:     PetscFunctionBegin; \
    146:     PetscAssertPointer(ht, 1); \
    147:     PetscAssertPointer(n, 2); \
    148:     *n = (PetscInt)kh_size(ht); \
    149:     PetscFunctionReturn(PETSC_SUCCESS); \
    150:   } \
    151: \
    152:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetCapacity(Petsc##HashT ht, PetscInt *n) \
    153:   { \
    154:     PetscFunctionBegin; \
    155:     PetscAssertPointer(ht, 1); \
    156:     PetscAssertPointer(n, 2); \
    157:     *n = (PetscInt)kh_n_buckets(ht); \
    158:     PetscFunctionReturn(PETSC_SUCCESS); \
    159:   } \
    160: \
    161:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Has(Petsc##HashT ht, KeyType key, PetscBool *has) \
    162:   { \
    163:     khiter_t iter; \
    164:     PetscFunctionBeginHot; \
    165:     PetscAssertPointer(ht, 1); \
    166:     PetscAssertPointer(has, 3); \
    167:     iter = kh_get(HashT, ht, key); \
    168:     *has = (iter != kh_end(ht)) ? PETSC_TRUE : PETSC_FALSE; \
    169:     PetscFunctionReturn(PETSC_SUCCESS); \
    170:   } \
    171: \
    172:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Get(Petsc##HashT ht, KeyType key, ValType *val) \
    173:   { \
    174:     khiter_t iter; \
    175:     PetscFunctionBeginHot; \
    176:     PetscAssertPointer(ht, 1); \
    177:     PetscAssertPointer(val, 3); \
    178:     iter = kh_get(HashT, ht, key); \
    179:     *val = (iter != kh_end(ht)) ? kh_val(ht, iter) : (DefaultValue); \
    180:     PetscFunctionReturn(PETSC_SUCCESS); \
    181:   } \
    182: \
    183:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetWithDefault(Petsc##HashT ht, KeyType key, ValType default_val, ValType *val) \
    184:   { \
    185:     PetscHashIter it    = 0; \
    186:     PetscBool     found = PETSC_FALSE; \
    187: \
    188:     PetscFunctionBeginHot; \
    189:     PetscAssertPointer(ht, 1); \
    190:     PetscAssertPointer(val, 4); \
    191:     PetscCall(Petsc##HashT##Find(ht, key, &it, &found)); \
    192:     if (found) { \
    193:       PetscHashIterGetVal(ht, it, *val); \
    194:     } else { \
    195:       *val = default_val; \
    196:     } \
    197:     PetscFunctionReturn(PETSC_SUCCESS); \
    198:   } \
    199: \
    200:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Set(Petsc##HashT ht, KeyType key, ValType val) \
    201:   { \
    202:     int      ret; \
    203:     khiter_t iter; \
    204:     PetscFunctionBeginHot; \
    205:     PetscAssertPointer(ht, 1); \
    206:     iter = kh_put(HashT, ht, key, &ret); \
    207:     PetscHashAssert(ret >= 0); \
    208:     kh_val(ht, iter) = val; \
    209:     PetscFunctionReturn(PETSC_SUCCESS); \
    210:   } \
    211: \
    212:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Del(Petsc##HashT ht, KeyType key) \
    213:   { \
    214:     khiter_t iter; \
    215:     PetscFunctionBeginHot; \
    216:     PetscAssertPointer(ht, 1); \
    217:     iter = kh_get(HashT, ht, key); \
    218:     kh_del(HashT, ht, iter); \
    219:     PetscFunctionReturn(PETSC_SUCCESS); \
    220:   } \
    221: \
    222:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##QuerySet(Petsc##HashT ht, KeyType key, ValType val, PetscBool *missing) \
    223:   { \
    224:     int      ret; \
    225:     khiter_t iter; \
    226:     PetscFunctionBeginHot; \
    227:     PetscAssertPointer(ht, 1); \
    228:     PetscAssertPointer(missing, 3); \
    229:     iter = kh_put(HashT, ht, key, &ret); \
    230:     PetscHashAssert(ret >= 0); \
    231:     kh_val(ht, iter) = val; \
    232:     *missing         = ret ? PETSC_TRUE : PETSC_FALSE; \
    233:     PetscFunctionReturn(PETSC_SUCCESS); \
    234:   } \
    235: \
    236:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##QueryDel(Petsc##HashT ht, KeyType key, PetscBool *present) \
    237:   { \
    238:     khiter_t iter; \
    239:     PetscFunctionBeginHot; \
    240:     PetscAssertPointer(ht, 1); \
    241:     PetscAssertPointer(present, 3); \
    242:     iter = kh_get(HashT, ht, key); \
    243:     if (iter != kh_end(ht)) { \
    244:       kh_del(HashT, ht, iter); \
    245:       *present = PETSC_TRUE; \
    246:     } else { \
    247:       *present = PETSC_FALSE; \
    248:     } \
    249:     PetscFunctionReturn(PETSC_SUCCESS); \
    250:   } \
    251: \
    252:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Find(Petsc##HashT ht, KeyType key, PetscHashIter *iter, PetscBool *found) \
    253: \
    254:   { \
    255:     PetscFunctionBeginHot; \
    256:     PetscAssertPointer(ht, 1); \
    257:     PetscAssertPointer(iter, 2); \
    258:     PetscAssertPointer(found, 3); \
    259:     *iter  = kh_get(HashT, ht, key); \
    260:     *found = (*iter != kh_end(ht)) ? PETSC_TRUE : PETSC_FALSE; \
    261:     PetscFunctionReturn(PETSC_SUCCESS); \
    262:   } \
    263: \
    264:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Put(Petsc##HashT ht, KeyType key, PetscHashIter *iter, PetscBool *missing) \
    265:   { \
    266:     int ret; \
    267:     PetscFunctionBeginHot; \
    268:     PetscAssertPointer(ht, 1); \
    269:     PetscAssertPointer(iter, 2); \
    270:     PetscAssertPointer(missing, 3); \
    271:     *iter = kh_put(HashT, ht, key, &ret); \
    272:     PetscHashAssert(ret >= 0); \
    273:     *missing = ret ? PETSC_TRUE : PETSC_FALSE; \
    274:     PetscFunctionReturn(PETSC_SUCCESS); \
    275:   } \
    276: \
    277:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterGet(Petsc##HashT ht, PetscHashIter iter, ValType *val) \
    278:   { \
    279:     PetscFunctionBeginHot; \
    280:     PetscAssertPointer(ht, 1); \
    281:     PetscAssertPointer(val, 3); \
    282:     *val = PetscLikely(iter < kh_end(ht) && kh_exist(ht, iter)) ? kh_val(ht, iter) : (DefaultValue); \
    283:     PetscFunctionReturn(PETSC_SUCCESS); \
    284:   } \
    285: \
    286:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterSet(Petsc##HashT ht, PetscHashIter iter, ValType val) \
    287:   { \
    288:     PetscFunctionBeginHot; \
    289:     PetscAssertPointer(ht, 1); \
    290:     if (PetscLikely(iter < kh_end(ht) && kh_exist(ht, iter))) kh_val(ht, iter) = val; \
    291:     PetscFunctionReturn(PETSC_SUCCESS); \
    292:   } \
    293: \
    294:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterDel(Petsc##HashT ht, PetscHashIter iter) \
    295:   { \
    296:     PetscFunctionBeginHot; \
    297:     PetscAssertPointer(ht, 1); \
    298:     if (PetscLikely(iter < kh_end(ht))) kh_del(HashT, ht, iter); \
    299:     PetscFunctionReturn(PETSC_SUCCESS); \
    300:   } \
    301: \
    302:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetKeys(Petsc##HashT ht, PetscInt *off, KeyType array[]) \
    303:   { \
    304:     KeyType  key; \
    305:     PetscInt pos; \
    306:     PetscFunctionBegin; \
    307:     PetscAssertPointer(ht, 1); \
    308:     PetscAssertPointer(off, 2); \
    309:     pos = *off; \
    310:     kh_foreach_key(ht, key, array[pos++] = key); \
    311:     *off = pos; \
    312:     PetscFunctionReturn(PETSC_SUCCESS); \
    313:   } \
    314: \
    315:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetVals(Petsc##HashT ht, PetscInt *off, ValType array[]) \
    316:   { \
    317:     ValType  val; \
    318:     PetscInt pos; \
    319:     PetscFunctionBegin; \
    320:     PetscAssertPointer(ht, 1); \
    321:     PetscAssertPointer(off, 2); \
    322:     pos = *off; \
    323:     kh_foreach_value(ht, val, array[pos++] = val); \
    324:     *off = pos; \
    325:     PetscFunctionReturn(PETSC_SUCCESS); \
    326:   } \
    327: \
    328:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetPairs(Petsc##HashT ht, PetscInt *off, KeyType karray[], ValType varray[]) \
    329:   { \
    330:     ValType  val; \
    331:     KeyType  key; \
    332:     PetscInt pos; \
    333:     PetscFunctionBegin; \
    334:     PetscAssertPointer(ht, 1); \
    335:     PetscAssertPointer(off, 2); \
    336:     pos     = *off; \
    337:     kh_foreach(ht, key, val, { \
    338:       karray[pos]   = key; \
    339:       varray[pos++] = val; \
    340:     }) *off = pos; \
    341:     PetscFunctionReturn(PETSC_SUCCESS); \
    342:   }

    344: #define PETSC_HASH_MAP_EXTENDED_DECL(HashT, KeyType, ValType) static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##SetWithMode(Petsc##HashT, KeyType, ValType, InsertMode)

    346: #define PETSC_HASH_MAP_EXTENDED(HashT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue) \
    347:   PETSC_HASH_MAP(HashT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue) \
    348: \
    349:   PETSC_HASH_MAP_EXTENDED_DECL(HashT, KeyType, ValType); \
    350: \
    351:   static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##SetWithMode(Petsc##HashT ht, KeyType key, ValType val, InsertMode mode) \
    352:   { \
    353:     PetscHashIter it      = 0; \
    354:     PetscBool     missing = PETSC_FALSE; \
    355: \
    356:     PetscFunctionBeginHot; \
    357:     PetscAssertPointer(ht, 1); \
    358:     PetscCall(Petsc##HashT##Put(ht, key, &it, &missing)); \
    359:     if (!missing) { \
    360:       ValType cur_val; \
    361: \
    362:       PetscHashIterGetVal(ht, it, cur_val); \
    363:       switch (mode) { \
    364:       case INSERT_VALUES: \
    365:         break; \
    366:       case ADD_VALUES: \
    367:         val += cur_val; \
    368:         break; \
    369:       case MAX_VALUES: \
    370:         val = PetscMax(cur_val, val); \
    371:         break; \
    372:       case MIN_VALUES: \
    373:         val = PetscMin(cur_val, val); \
    374:         break; \
    375:       case NOT_SET_VALUES:    /* fallthrough */ \
    376:       case INSERT_ALL_VALUES: /* fallthrough */ \
    377:       case ADD_ALL_VALUES:    /* fallthrough */ \
    378:       case INSERT_BC_VALUES:  /* fallthrough */ \
    379:       case ADD_BC_VALUES:     /* fallthrough */ \
    380:       default: \
    381:         SETERRQ(PETSC_COMM_SELF, PETSC_ERR_SUP, "Unsupported InsertMode %d", (int)mode); \
    382:       } \
    383:     } \
    384:     PetscCall(Petsc##HashT##IterSet(ht, it, val)); \
    385:     PetscFunctionReturn(PETSC_SUCCESS); \
    386:   }