bmap.h

   1 #ifndef BMAP_H
   2 #define BMAP_H
   3
   4 /* this is a map behaving like a hashmap, but it uses binary search
   5    on a sorted list behind the curtains. this allows to find the
   6    required entry very quickly, while avoiding a lot of the complexity
   7    of a hashmap.
   8
   9    for e.g. 10000 array elements, a binary search will only require 12
  10    comparisons, whereas a hashmap needs to compute a hash, then find
  11    a corresponding bucket and iterate over the bucket items, of which
  12    there could be multiple as well. so it shouldn't be much faster,
  13    while having a lot more overhead in code and RAM.
  14
  15    since we use our per-value tglist behind the scenes, which looks
  16    basically like a flat array of the stored items, there's almost
  17    zero memory overhead with our method here.
  18
  19    the slowest part is insertion of the item into the list, which uses
  20    memmove on a single block of memory. this is no problem when the
  21    total number of entries is relatively small.
  22
  23    when comparing to khash, which is known as one of the fastest hashmap
  24    implementations due to usage of macros to generate inlined code,
  25    we reach about 80-75% of its speed with around 1000 items, but only
  26    40% with 3000, 33% with 10000 etc. the more items, the slower it
  27    becomes in comparison.
  28
  29    so for the vast majority of tasks, this implementation provides
  30    speed comparable to the fastest hashmap implementation, while adding
  31    only a few hundred byte to binary size. a size-optimized benchmark
  32    program with bmap is 5.5KB, an equivalent one with kash 9.6KB.
  33
  34    an additional advantage is that the map can be iterated like a
  35    regular array, which is already sorted by key.
  36
  37 */
  38
  39 #include "tglist.h"
  40 #include <stdint.h>
  41 #include <stddef.h>
  42 #include <stdlib.h>
  43 #include <unistd.h> /* ssize_t */
  44
  45 #define bmap_cat(a, b) bmap_cat_impl(a, b)
  46 #define bmap_cat_impl(a, b) a ## b
  47
  48 #ifdef BMAP_USE_TGILIST
  49 #include "tgilist.h"
  50 #define VAL_LIST_TYPE tgilist
  51 #define VAL_LIST_ARGCALL(FN, A, B, C) FN(A, B, C)
  52 #else
  53 #define VAL_LIST_TYPE tglist
  54 #define VAL_LIST_ARGCALL(FN, A, B, C) FN(A, B)
  55 #endif
  56
  57
  58 typedef int (*bmap_compare_func)(const void *, const void *);
  59
  60 #define bmap_impl(NAME, KEYTYPE, VALTYPE) \
  61 struct NAME { \
  62         tglist_impl(, KEYTYPE) keys; \
  63         VAL_LIST_ARGCALL(bmap_cat(VAL_LIST_TYPE, _impl), ,VALTYPE, unsigned) values; \
  64         bmap_compare_func compare; \
  65         union { \
  66                 KEYTYPE* kt; \
  67                 VALTYPE* vt; \
  68                 ssize_t ss; \
  69         } tmp; \
  70 }
  71
  72 #define bmap(KEYTYPE, VALTYPE) bmap_impl(, KEYTYPE, VALTYPE)
  73 #define bmap_decl(ID, KEYTYPE, VALTYPE) bmap_impl(bmap_ ## ID, KEYTYPE, VALTYPE)
  74 #define bmap_proto bmap_impl(, void*, void*)
  75
  76 /* initialization */
  77 /* bmap_compare_func is a typical compare function used for qsort, etc such as strcmp
  78  */
  79 #define bmap_init(X, COMPAREFUNC) do{\
  80         memset(X, 0, sizeof(*(X))); \
  81         (X)->compare = COMPAREFUNC; } while(0)
  82
  83 static inline void* bmap_new(bmap_compare_func fn) {
  84         bmap_proto *nyu = malloc(sizeof(bmap_proto));
  85         if(nyu) bmap_init(nyu, fn);
  86         return nyu;
  87 }
  88
  89 /* destruction */
  90 /* freeflags:
  91   0: free only internal mem
  92   1: 0+free all keys,
  93   2: 0+free all values,
  94   3: 0+free both
  95 */
  96 #define bmap_fini(X, FREEFLAGS) do { \
  97         if(FREEFLAGS & 1) {tglist_free_values(&(X)->keys);} \
  98         if(FREEFLAGS & 2) {bmap_cat(VAL_LIST_TYPE, _free_values)(&(X)->values);} \
  99         tglist_free_items(&(X)->keys); \
 100         bmap_cat(VAL_LIST_TYPE, _free_items)(&(X)->values); \
 101 } while(0)
 102
 103 /* set value when key index is known. returns int 0 on failure, 1 on succ.*/
 104 #define bmap_setvalue(B, VAL, POS) bmap_cat(VAL_LIST_TYPE, _set)(&(B)->values, VAL, POS)
 105
 106 #define bmap_getsize(B) tglist_getsize(&(B)->keys)
 107 #define bmap_getkey(B, X) tglist_get(&(B)->keys, X)
 108 #define bmap_getval(B, X) bmap_cat(VAL_LIST_TYPE, _get)(&(B)->values, X)
 109 #define bmap_getkeysize(B) (tglist_itemsize(&(B)->keys))
 110 #define bmap_getvalsize(B) (bmap_cat(VAL_LIST_TYPE, _itemsize)(&(B)->values))
 111
 112 #define bmap_find(X, KEY) \
 113         ( (X)->tmp.kt = (void*)&(KEY), bmap_find_impl(X, (X)->tmp.kt, bmap_getkeysize(X)) )
 114
 115 #define bmap_contains(B, KEY) (bmap_find(B, KEY) != (ssize_t)-1)
 116
 117 /* unlike bmap_getkey/val with index, this returns a pointer-to-item, or NULL */
 118 #define bmap_get(X, KEY) \
 119         ( (((X)->tmp.kt = (void*)&(KEY)), 1) &&  \
 120         ( (X)->tmp.ss = bmap_find_impl(X, (X)->tmp.kt, bmap_getkeysize(X)) ) == (ssize_t) -1 ? \
 121                 0 : &bmap_getval(X, (X)->tmp.ss) )
 122
 123 /* same as bmap_insert, but inserts blindly without checking for existing items.
 124    this is faster and can be used when it's impossible that duplicate
 125    items are added */
 126 #define bmap_insert_nocheck(X, KEY, VAL) ( \
 127         (  \
 128         (  (X)->tmp.ss = tglist_insert_sorted(&(X)->keys, KEY, (X)->compare) ) \
 129                 == (ssize_t) -1) ? (ssize_t) -1 : ( \
 130                         bmap_cat(VAL_LIST_TYPE, _insert)(&(X)->values, VAL, (X)->tmp.ss) ? (X)->tmp.ss : \
 131                         (  tglist_delete(&(X)->keys, (X)->tmp.ss), (ssize_t) -1  ) \
 132                 ) \
 133         )
 134 /* insert item into mapping, overwriting existing items with the same key */
 135 /* return index of new item, or -1. overwrites existing items. */
 136 // FIXME evaluates KEY twice
 137 #define bmap_insert(X, KEY, VAL) ( \
 138                 ( (X)->tmp.ss = bmap_find(X, KEY) ) \
 139                 == (ssize_t) -1 ? bmap_insert_nocheck(X, KEY, VAL) : \
 140                 bmap_cat(VAL_LIST_TYPE, _set)(&(X)->values, VAL, (X)->tmp.ss), (X)->tmp.ss \
 141         )
 142
 143 #define bmap_delete(X, POS) ( \
 144         (X)->tmp.ss = POS, \
 145         tglist_delete(&(X)->keys, POS), \
 146         bmap_cat(VAL_LIST_TYPE, _delete)(&(X)->values, POS) \
 147         )
 148
 149 static ssize_t bmap_find_impl(void* bm, const void* key, size_t keysize) {
 150         bmap_proto *b = bm;
 151         void *r = bsearch(key, b->keys.items, bmap_getsize(b), keysize, b->compare);
 152         if(!r) return -1;
 153         return ((uintptr_t) r - (uintptr_t) b->keys.items)/keysize;
 154 }
 155
 156 #endif