1 #pragma once 2 3 #include <petsc/private/hashtable.h> 4 5 /* MANSEC = Sys */ 6 /* SUBMANSEC = PetscH */ 7 8 /*MC 9 PETSC_HASH_MAP - Instantiate a PETSc hash table map type 10 11 Synopsis: 12 #include <petsc/private/hashmap.h> 13 PETSC_HASH_MAP(HMapT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue) 14 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 22 23 Level: developer 24 25 Note: 26 This code uses the standalone and portable C language khash software <https://github.com/attractivechaos/klib> 27 28 Developer Note: 29 Each time this macro is used to create a new hash map type, the make rule for allmanpages in $PETSC_DIR/makefile should 30 be updated to cause the automatic generation of appropriate manual pages for that type. The manual pages 31 are generated from the templated version of the documentation in include/petsc/private/hashmap.txt. 32 33 .seealso: `PETSC_HASH_MAP_DECL()`, `PetscHMapI`, `PetscHMapICreate()`, `PetscHMapIJ`, 34 `PetscHMapIJCreate()`, `PETSC_HASH_SET()` 35 M*/ 36 37 #define PETSC_HASH_MAP_DECL(HashT, KeyType, ValType) \ 38 typedef kh_##HashT##_t *Petsc##HashT; \ 39 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Create(Petsc##HashT *); \ 40 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##CreateWithSize(PetscInt, Petsc##HashT *); \ 41 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Destroy(Petsc##HashT *); \ 42 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Reset(Petsc##HashT); \ 43 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Duplicate(Petsc##HashT, Petsc##HashT *); \ 44 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Clear(Petsc##HashT); \ 45 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Resize(Petsc##HashT, PetscInt); \ 46 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetSize(Petsc##HashT, PetscInt *); \ 47 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetCapacity(Petsc##HashT, PetscInt *); \ 48 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Has(Petsc##HashT, KeyType, PetscBool *); \ 49 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Get(Petsc##HashT, KeyType, ValType *); \ 50 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetWithDefault(Petsc##HashT, KeyType, ValType, ValType *); \ 51 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Set(Petsc##HashT, KeyType, ValType); \ 52 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Del(Petsc##HashT, KeyType); \ 53 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##QuerySet(Petsc##HashT, KeyType, ValType, PetscBool *); \ 54 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##QueryDel(Petsc##HashT, KeyType, PetscBool *); \ 55 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Find(Petsc##HashT, KeyType, PetscHashIter *, PetscBool *); \ 56 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Put(Petsc##HashT, KeyType, PetscHashIter *, PetscBool *); \ 57 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterGet(Petsc##HashT, PetscHashIter, ValType *); \ 58 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterSet(Petsc##HashT, PetscHashIter, ValType); \ 59 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterDel(Petsc##HashT, PetscHashIter); \ 60 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetKeys(Petsc##HashT, PetscInt *, KeyType[]); \ 61 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetVals(Petsc##HashT, PetscInt *, ValType[]); \ 62 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetPairs(Petsc##HashT, PetscInt *, KeyType[], ValType[]) 63 64 #define PETSC_HASH_MAP(HashT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue) \ 65 \ 66 KHASH_INIT(HashT, KeyType, ValType, 1, HashFunc, EqualFunc) \ 67 PETSC_HASH_MAP_DECL(HashT, KeyType, ValType); \ 68 \ 69 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Create(Petsc##HashT *ht) \ 70 { \ 71 PetscFunctionBegin; \ 72 PetscAssertPointer(ht, 1); \ 73 *ht = kh_init(HashT); \ 74 PetscHashAssert(*ht != NULL); \ 75 PetscFunctionReturn(PETSC_SUCCESS); \ 76 } \ 77 \ 78 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##CreateWithSize(PetscInt n, Petsc##HashT *ht) \ 79 { \ 80 PetscFunctionBegin; \ 81 PetscAssert(n >= 0, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Hash table size %" PetscInt_FMT " must be >= 0", n); \ 82 PetscAssertPointer(ht, 2); \ 83 PetscCall(Petsc##HashT##Create(ht)); \ 84 if (n) PetscCall(Petsc##HashT##Resize(*ht, n)); \ 85 PetscFunctionReturn(PETSC_SUCCESS); \ 86 } \ 87 \ 88 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Destroy(Petsc##HashT *ht) \ 89 { \ 90 PetscFunctionBegin; \ 91 PetscAssertPointer(ht, 1); \ 92 if (!*ht) PetscFunctionReturn(PETSC_SUCCESS); \ 93 kh_destroy(HashT, *ht); \ 94 *ht = NULL; \ 95 PetscFunctionReturn(PETSC_SUCCESS); \ 96 } \ 97 \ 98 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Reset(Petsc##HashT ht) \ 99 { \ 100 PetscFunctionBegin; \ 101 PetscAssertPointer(ht, 1); \ 102 kh_reset(HashT, ht); \ 103 PetscFunctionReturn(PETSC_SUCCESS); \ 104 } \ 105 \ 106 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Duplicate(Petsc##HashT ht, Petsc##HashT *hd) \ 107 { \ 108 int ret; \ 109 KeyType key; \ 110 ValType val; \ 111 PetscFunctionBegin; \ 112 PetscAssertPointer(ht, 1); \ 113 PetscAssertPointer(hd, 2); \ 114 *hd = kh_init(HashT); \ 115 PetscHashAssert(*hd != NULL); \ 116 ret = kh_resize(HashT, *hd, kh_size(ht)); \ 117 PetscHashAssert(ret == 0); \ 118 kh_foreach(ht, key, val, { \ 119 khiter_t i; \ 120 i = kh_put(HashT, *hd, key, &ret); \ 121 PetscHashAssert(ret >= 0); \ 122 kh_val(*hd, i) = val; \ 123 }) PetscFunctionReturn(PETSC_SUCCESS); \ 124 } \ 125 \ 126 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Clear(Petsc##HashT ht) \ 127 { \ 128 PetscFunctionBegin; \ 129 PetscAssertPointer(ht, 1); \ 130 kh_clear(HashT, ht); \ 131 PetscFunctionReturn(PETSC_SUCCESS); \ 132 } \ 133 \ 134 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Resize(Petsc##HashT ht, PetscInt nb) \ 135 { \ 136 int ret; \ 137 PetscFunctionBegin; \ 138 PetscAssertPointer(ht, 1); \ 139 ret = kh_resize(HashT, ht, (khint_t)nb); \ 140 PetscHashAssert(ret >= 0); \ 141 PetscFunctionReturn(PETSC_SUCCESS); \ 142 } \ 143 \ 144 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetSize(Petsc##HashT ht, PetscInt *n) \ 145 { \ 146 PetscFunctionBegin; \ 147 PetscAssertPointer(ht, 1); \ 148 PetscAssertPointer(n, 2); \ 149 *n = (PetscInt)kh_size(ht); \ 150 PetscFunctionReturn(PETSC_SUCCESS); \ 151 } \ 152 \ 153 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetCapacity(Petsc##HashT ht, PetscInt *n) \ 154 { \ 155 PetscFunctionBegin; \ 156 PetscAssertPointer(ht, 1); \ 157 PetscAssertPointer(n, 2); \ 158 *n = (PetscInt)kh_n_buckets(ht); \ 159 PetscFunctionReturn(PETSC_SUCCESS); \ 160 } \ 161 \ 162 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Has(Petsc##HashT ht, KeyType key, PetscBool *has) \ 163 { \ 164 khiter_t iter; \ 165 PetscFunctionBeginHot; \ 166 PetscAssertPointer(ht, 1); \ 167 PetscAssertPointer(has, 3); \ 168 iter = kh_get(HashT, ht, key); \ 169 *has = (iter != kh_end(ht)) ? PETSC_TRUE : PETSC_FALSE; \ 170 PetscFunctionReturn(PETSC_SUCCESS); \ 171 } \ 172 \ 173 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Get(Petsc##HashT ht, KeyType key, ValType *val) \ 174 { \ 175 khiter_t iter; \ 176 PetscFunctionBeginHot; \ 177 PetscAssertPointer(ht, 1); \ 178 PetscAssertPointer(val, 3); \ 179 iter = kh_get(HashT, ht, key); \ 180 *val = (iter != kh_end(ht)) ? kh_val(ht, iter) : (DefaultValue); \ 181 PetscFunctionReturn(PETSC_SUCCESS); \ 182 } \ 183 \ 184 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetWithDefault(Petsc##HashT ht, KeyType key, ValType default_val, ValType *val) \ 185 { \ 186 PetscHashIter it = 0; \ 187 PetscBool found = PETSC_FALSE; \ 188 \ 189 PetscFunctionBeginHot; \ 190 PetscAssertPointer(ht, 1); \ 191 PetscAssertPointer(val, 4); \ 192 PetscCall(Petsc##HashT##Find(ht, key, &it, &found)); \ 193 if (found) { \ 194 PetscHashIterGetVal(ht, it, *val); \ 195 } else { \ 196 *val = default_val; \ 197 } \ 198 PetscFunctionReturn(PETSC_SUCCESS); \ 199 } \ 200 \ 201 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Set(Petsc##HashT ht, KeyType key, ValType val) \ 202 { \ 203 int ret; \ 204 khiter_t iter; \ 205 PetscFunctionBeginHot; \ 206 PetscAssertPointer(ht, 1); \ 207 iter = kh_put(HashT, ht, key, &ret); \ 208 PetscHashAssert(ret >= 0); \ 209 kh_val(ht, iter) = val; \ 210 PetscFunctionReturn(PETSC_SUCCESS); \ 211 } \ 212 \ 213 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Del(Petsc##HashT ht, KeyType key) \ 214 { \ 215 khiter_t iter; \ 216 PetscFunctionBeginHot; \ 217 PetscAssertPointer(ht, 1); \ 218 iter = kh_get(HashT, ht, key); \ 219 kh_del(HashT, ht, iter); \ 220 PetscFunctionReturn(PETSC_SUCCESS); \ 221 } \ 222 \ 223 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##QuerySet(Petsc##HashT ht, KeyType key, ValType val, PetscBool *missing) \ 224 { \ 225 int ret; \ 226 khiter_t iter; \ 227 PetscFunctionBeginHot; \ 228 PetscAssertPointer(ht, 1); \ 229 PetscAssertPointer(missing, 3); \ 230 iter = kh_put(HashT, ht, key, &ret); \ 231 PetscHashAssert(ret >= 0); \ 232 kh_val(ht, iter) = val; \ 233 *missing = ret ? PETSC_TRUE : PETSC_FALSE; \ 234 PetscFunctionReturn(PETSC_SUCCESS); \ 235 } \ 236 \ 237 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##QueryDel(Petsc##HashT ht, KeyType key, PetscBool *present) \ 238 { \ 239 khiter_t iter; \ 240 PetscFunctionBeginHot; \ 241 PetscAssertPointer(ht, 1); \ 242 PetscAssertPointer(present, 3); \ 243 iter = kh_get(HashT, ht, key); \ 244 if (iter != kh_end(ht)) { \ 245 kh_del(HashT, ht, iter); \ 246 *present = PETSC_TRUE; \ 247 } else { \ 248 *present = PETSC_FALSE; \ 249 } \ 250 PetscFunctionReturn(PETSC_SUCCESS); \ 251 } \ 252 \ 253 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Find(Petsc##HashT ht, KeyType key, PetscHashIter *iter, PetscBool *found) \ 254 \ 255 { \ 256 PetscFunctionBeginHot; \ 257 PetscAssertPointer(ht, 1); \ 258 PetscAssertPointer(iter, 2); \ 259 PetscAssertPointer(found, 3); \ 260 *iter = kh_get(HashT, ht, key); \ 261 *found = (*iter != kh_end(ht)) ? PETSC_TRUE : PETSC_FALSE; \ 262 PetscFunctionReturn(PETSC_SUCCESS); \ 263 } \ 264 \ 265 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##Put(Petsc##HashT ht, KeyType key, PetscHashIter *iter, PetscBool *missing) \ 266 { \ 267 int ret; \ 268 PetscFunctionBeginHot; \ 269 PetscAssertPointer(ht, 1); \ 270 PetscAssertPointer(iter, 2); \ 271 PetscAssertPointer(missing, 3); \ 272 *iter = kh_put(HashT, ht, key, &ret); \ 273 PetscHashAssert(ret >= 0); \ 274 *missing = ret ? PETSC_TRUE : PETSC_FALSE; \ 275 PetscFunctionReturn(PETSC_SUCCESS); \ 276 } \ 277 \ 278 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterGet(Petsc##HashT ht, PetscHashIter iter, ValType *val) \ 279 { \ 280 PetscFunctionBeginHot; \ 281 PetscAssertPointer(ht, 1); \ 282 PetscAssertPointer(val, 3); \ 283 *val = PetscLikely(iter < kh_end(ht) && kh_exist(ht, iter)) ? kh_val(ht, iter) : (DefaultValue); \ 284 PetscFunctionReturn(PETSC_SUCCESS); \ 285 } \ 286 \ 287 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterSet(Petsc##HashT ht, PetscHashIter iter, ValType val) \ 288 { \ 289 PetscFunctionBeginHot; \ 290 PetscAssertPointer(ht, 1); \ 291 if (PetscLikely(iter < kh_end(ht) && kh_exist(ht, iter))) kh_val(ht, iter) = val; \ 292 PetscFunctionReturn(PETSC_SUCCESS); \ 293 } \ 294 \ 295 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##IterDel(Petsc##HashT ht, PetscHashIter iter) \ 296 { \ 297 PetscFunctionBeginHot; \ 298 PetscAssertPointer(ht, 1); \ 299 if (PetscLikely(iter < kh_end(ht))) kh_del(HashT, ht, iter); \ 300 PetscFunctionReturn(PETSC_SUCCESS); \ 301 } \ 302 \ 303 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetKeys(Petsc##HashT ht, PetscInt *off, KeyType array[]) \ 304 { \ 305 KeyType key; \ 306 PetscInt pos; \ 307 PetscFunctionBegin; \ 308 PetscAssertPointer(ht, 1); \ 309 PetscAssertPointer(off, 2); \ 310 pos = *off; \ 311 kh_foreach_key(ht, key, array[pos++] = key); \ 312 *off = pos; \ 313 PetscFunctionReturn(PETSC_SUCCESS); \ 314 } \ 315 \ 316 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetVals(Petsc##HashT ht, PetscInt *off, ValType array[]) \ 317 { \ 318 ValType val; \ 319 PetscInt pos; \ 320 PetscFunctionBegin; \ 321 PetscAssertPointer(ht, 1); \ 322 PetscAssertPointer(off, 2); \ 323 pos = *off; \ 324 kh_foreach_value(ht, val, array[pos++] = val); \ 325 *off = pos; \ 326 PetscFunctionReturn(PETSC_SUCCESS); \ 327 } \ 328 \ 329 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##GetPairs(Petsc##HashT ht, PetscInt *off, KeyType karray[], ValType varray[]) \ 330 { \ 331 ValType val; \ 332 KeyType key; \ 333 PetscInt pos; \ 334 PetscFunctionBegin; \ 335 PetscAssertPointer(ht, 1); \ 336 PetscAssertPointer(off, 2); \ 337 pos = *off; \ 338 kh_foreach(ht, key, val, { \ 339 karray[pos] = key; \ 340 varray[pos++] = val; \ 341 }) *off = pos; \ 342 PetscFunctionReturn(PETSC_SUCCESS); \ 343 } 344 345 #define PETSC_HASH_MAP_EXTENDED_DECL(HashT, KeyType, ValType) static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##SetWithMode(Petsc##HashT, KeyType, ValType, InsertMode) 346 347 #define PETSC_HASH_MAP_EXTENDED(HashT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue) \ 348 PETSC_HASH_MAP(HashT, KeyType, ValType, HashFunc, EqualFunc, DefaultValue) \ 349 \ 350 PETSC_HASH_MAP_EXTENDED_DECL(HashT, KeyType, ValType); \ 351 \ 352 static inline PETSC_UNUSED PetscErrorCode Petsc##HashT##SetWithMode(Petsc##HashT ht, KeyType key, ValType val, InsertMode mode) \ 353 { \ 354 PetscHashIter it = 0; \ 355 PetscBool missing = PETSC_FALSE; \ 356 \ 357 PetscFunctionBeginHot; \ 358 PetscAssertPointer(ht, 1); \ 359 PetscCall(Petsc##HashT##Put(ht, key, &it, &missing)); \ 360 if (!missing) { \ 361 ValType cur_val; \ 362 \ 363 PetscHashIterGetVal(ht, it, cur_val); \ 364 switch (mode) { \ 365 case INSERT_VALUES: \ 366 break; \ 367 case ADD_VALUES: \ 368 val += cur_val; \ 369 break; \ 370 case MAX_VALUES: \ 371 val = PetscMax(cur_val, val); \ 372 break; \ 373 case MIN_VALUES: \ 374 val = PetscMin(cur_val, val); \ 375 break; \ 376 case NOT_SET_VALUES: /* fallthrough */ \ 377 case INSERT_ALL_VALUES: /* fallthrough */ \ 378 case ADD_ALL_VALUES: /* fallthrough */ \ 379 case INSERT_BC_VALUES: /* fallthrough */ \ 380 case ADD_BC_VALUES: /* fallthrough */ \ 381 default: \ 382 SETERRQ(PETSC_COMM_SELF, PETSC_ERR_SUP, "Unsupported InsertMode %d", (int)mode); \ 383 } \ 384 } \ 385 PetscCall(Petsc##HashT##IterSet(ht, it, val)); \ 386 PetscFunctionReturn(PETSC_SUCCESS); \ 387 } 388