hbmap.h

   1 #ifndef HBMAP_H
   2 #define HBMAP_H
   3
   4 /* this is a hashmap using a fixed number of buckets,
   5    which in turn are of type bmap. this combines the advantages of both
   6    approaches.
   7    limitations: max no of buckets and items per bucket is 2^32-1 each.
   8    speed is almost identical to khash with small number of items per
   9    bucket. with 100.000 items it's about 15% slower.
  10
  11    unlike bmap, _find(), insert(), etc return an iterator instead of indices.
  12    the iterator needs to be used for e.g. _getkey(), etc.
  13 */
  14
  15 #include "bmap.h"
  16 #include <stdint.h>
  17 #include <stddef.h>
  18 #include <stdlib.h>
  19 #include <unistd.h> /* ssize_t */
  20
  21 #ifndef ARRAY_SIZE
  22 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
  23 #endif
  24
  25 typedef uint64_t hbmap_iter;
  26
  27 #define hbmap_impl(NAME, KEYTYPE, VALTYPE, NUMBUCKETS) \
  28 struct NAME { \
  29         unsigned (*hash_func)(const KEYTYPE); \
  30         union { \
  31                 hbmap_iter it; \
  32         } tmp; \
  33         bmap_impl(, KEYTYPE, VALTYPE) buckets[NUMBUCKETS]; \
  34 }
  35
  36 #define hbmap(KEYTYPE, VALTYPE, NUMBUCKETS) \
  37         hbmap_impl(, KEYTYPE, VALTYPE, NUMBUCKETS)
  38
  39 #define hbmap_decl(ID, KEYTYPE, VALTYPE, NUMBUCKETS) \
  40         hbmap_impl(hbmap_ ## ID, KEYTYPE, VALTYPE, NUMBUCKETS)
  41
  42 #define hbmap_proto(NUMBUCKETS) \
  43         hbmap_impl(, void*, void*, NUMBUCKETS)
  44
  45 #define hbmap_getbucketcount(X) ARRAY_SIZE((X)->buckets)
  46
  47 #define hbmap_struct_size_impl(NUMBUCKETS) ( \
  48         offsetof(hbmap_proto(1), buckets) + \
  49         NUMBUCKETS * sizeof(bmap_proto) \
  50         )
  51
  52 #define hbmap_init_impl(X, COMPAREFUNC, HASHFUNC, NUMBUCKETS) do{\
  53         memset(X, 0, hbmap_struct_size_impl(NUMBUCKETS)); \
  54         ((hbmap_proto(1)*)(void*)(X))->hash_func = (void*)HASHFUNC; \
  55         bmap_proto *p = (void*)(&((hbmap_proto(1)*)(void*)(X))->buckets[0]); \
  56         size_t i; for(i=0; i<NUMBUCKETS; ++i) \
  57                 p[i].compare = COMPAREFUNC; \
  58         } while(0)
  59
  60 /* initialization */
  61 /* bmap_compare_func is a typical compare function used for qsort, etc such as strcmp
  62  */
  63
  64 #define hbmap_init(X, COMPAREFUNC, HASHFUNC) \
  65         hbmap_init_impl(X, COMPAREFUNC, HASHFUNC, hbmap_getbucketcount(X))
  66
  67 static inline void* hbmap_new(bmap_compare_func fn, void* hash_func, size_t numbuckets) {
  68         void *nyu = malloc(hbmap_struct_size_impl(numbuckets));
  69         if(nyu) hbmap_init_impl(nyu, fn, hash_func, numbuckets);
  70         return nyu;
  71 }
  72
  73 /* destruction */
  74 /* freeflags:
  75   0: free only internal mem
  76   1: 0+free all keys,
  77   2: 0+free all values,
  78   3: 0+free both
  79 */
  80 #define hbmap_fini(X, FREEFLAGS) do { \
  81         size_t i; for(i=0; i < hbmap_getbucketcount(X); ++i) \
  82                 { bmap_fini(&(X)->buckets[i], FREEFLAGS); } \
  83 } while(0)
  84
  85 /* internal stuff needed for iterator impl */
  86
  87 #define hbmap_iter_bucket(I) ( (I) >> 32)
  88 #define hbmap_iter_index(I)  ( (I) & 0xffffffff )
  89 #define hbmap_iter_makebucket(I) ( (I) << 32)
  90
  91 #define hbmap_iter_bucket_valid(X, ITER, NUMBUCKETS) ( \
  92         hbmap_iter_bucket(ITER) < NUMBUCKETS )
  93 #define hbmap_iter_index_valid(X, ITER) ( \
  94         hbmap_iter_index(ITER) < bmap_getsize(& \
  95         (((bmap_proto *)( \
  96         (void*)(&((hbmap_proto(1)*)(void*)(X))->buckets[0]) \
  97         ))[hbmap_iter_bucket(ITER)]) \
  98         ))
  99
 100 #define hbmap_iter_valid(X, ITER) (\
 101         hbmap_iter_bucket_valid(X, ITER, hbmap_getbucketcount(X)) && \
 102         hbmap_iter_index_valid(X, ITER))
 103
 104 #define hbmap_next_step(X, ITER) ( \
 105         hbmap_iter_index_valid(X, (ITER)+1) ? (ITER)+1 : \
 106         hbmap_iter_makebucket(hbmap_iter_bucket(ITER)+1) \
 107         )
 108
 109 static hbmap_iter hbmap_next_valid_impl(void *h, hbmap_iter iter, size_t nbucks) {
 110         do iter = hbmap_next_step(h, iter);
 111         while(hbmap_iter_bucket_valid(h, iter, nbucks) && !hbmap_iter_index_valid(h, iter));
 112         return iter;
 113 }
 114
 115 /* public API continues */
 116
 117 /* note that if you use foreach to delete items, the iterator isn't aware of that
 118    and will skip over the next item. you need to use something like:
 119    hbmap_foreach(map, i) { while(hbmap_iter_index_valid(map, i)) hbmap_delete(map, i); }
 120 */
 121 #define hbmap_foreach(X, ITER_VAR) \
 122         for(ITER_VAR = hbmap_iter_valid(X, (hbmap_iter)0) ? 0 \
 123         : hbmap_next_valid_impl(X, 0, hbmap_getbucketcount(X)); \
 124                 hbmap_iter_valid(X, ITER_VAR); \
 125                 ITER_VAR = hbmap_next_valid_impl(X, ITER_VAR, hbmap_getbucketcount(X)))
 126
 127 #define hbmap_getkey(X, ITER) \
 128         bmap_getkey(&(X)->buckets[hbmap_iter_bucket(ITER)], hbmap_iter_index(ITER))
 129
 130 #define hbmap_getval(X, ITER) \
 131         bmap_getval(&(X)->buckets[hbmap_iter_bucket(ITER)], hbmap_iter_index(ITER))
 132
 133 #define hbmap_setvalue(X, VAL, ITER) \
 134         bmap_setvalue(&(X)->buckets[hbmap_iter_bucket(ITER)], VAL, hbmap_iter_index(ITER))
 135
 136 #define hbmap_getkeysize(X) (bmap_getkeysize(&(X)->buckets[0]))
 137 #define hbmap_getvalsize(X) (bmap_getvalsize(&(X)->buckets[0]))
 138
 139 #define hbmap_buckindex_impl(X, KEY) \
 140         ( (X)->hash_func(KEY) % hbmap_getbucketcount(X) )
 141
 142 #define hbmap_find(X, KEY) ( \
 143         ( (X)->tmp.it = hbmap_iter_makebucket(hbmap_buckindex_impl(X, KEY) ) ), \
 144         ((X)->tmp.it |= (int64_t) bmap_find(&(X)->buckets[ hbmap_iter_bucket((X)->tmp.it) ], KEY)), \
 145         (X)->tmp.it)
 146
 147 #define hbmap_contains(X, KEY) (hbmap_find(X, KEY) != (hbmap_iter)-1)
 148
 149 /* unlike hbmap_getkey/val with index, this returns a pointer-to-item, or NULL */
 150 #define hbmap_get(X, KEY) ( \
 151         ( hbmap_find(X, KEY) == (hbmap_iter) -1 ) ? 0 : &hbmap_getval(X, (X)->tmp.it) \
 152         )
 153
 154 /* same as hbmap_insert, but inserts blindly without checking for existing items.
 155    this is faster and can be used when it's impossible that duplicate
 156    items are added */
 157 #define hbmap_insert_nocheck(X, KEY, VAL) ( \
 158         ( (X)->tmp.it = hbmap_iter_makebucket(hbmap_buckindex_impl(X, KEY) ) ), \
 159         ((X)->tmp.it |= (int64_t) bmap_insert_nocheck(&(X)->buckets[hbmap_iter_bucket((X)->tmp.it)], KEY, VAL)), \
 160         (X)->tmp.it)
 161
 162 /* insert item into mapping, overwriting existing items with the same key */
 163 /* return index of new item, or -1. overwrites existing items. */
 164 #define hbmap_insert(X, KEY, VAL) ( \
 165                 ( hbmap_find(X, KEY) == (hbmap_iter) -1 ) ? hbmap_insert_nocheck(X, KEY, VAL) : \
 166                 ( hbmap_setvalue(X, VAL, (X)->tmp.it), (X)->tmp.it ) \
 167         )
 168
 169 #define hbmap_delete(X, ITER) ( \
 170         bmap_delete(&(X)->buckets[hbmap_iter_bucket(ITER)], hbmap_iter_index(ITER)), 1)
 171
 172 #endif