nostrdb

an unfairly fast embedded nostr database backed by lmdb
git clone git://jb55.com/nostrdb
Log | Files | Refs | Submodules | README | LICENSE

refmap.c (7228B)


      1 /*
      2  * Optional file that can be included in runtime library to support DAG
      3  * cloning with the builder and may also be used for custom purposes
      4  * standalone. See also comments in `flatcc/flatcc_builder.h`.
      5  *
      6  * Note that dynamic construction takes place and that large offset
      7  * vectors might consume significant space if there are not many shared
      8  * references. In the basic use case no allocation takes place because a
      9  * few references can be held using only a small stack allocated hash
     10  * table.
     11  */
     12 
     13 #include <stdlib.h>
     14 #include <string.h>
     15 
     16 #include "flatcc/flatcc_rtconfig.h"
     17 #include "flatcc/flatcc_refmap.h"
     18 #include "flatcc/flatcc_alloc.h"
     19 #include "flatcc/flatcc_assert.h"
     20 
     21 #define _flatcc_refmap_calloc FLATCC_CALLOC
     22 #define _flatcc_refmap_free FLATCC_FREE
     23 
     24 /* Can be used as a primitive defense against collision attacks. */
     25 #ifdef FLATCC_HASH_SEED
     26 #define _flatcc_refmap_seed FLATCC_HASH_SEED
     27 #else
     28 #define _flatcc_refmap_seed 0x2f693b52
     29 #endif
     30 
     31 static inline size_t _flatcc_refmap_above_load_factor(size_t count, size_t buckets)
     32 {
     33     static const size_t d = 256;
     34     static const size_t n = (size_t)((FLATCC_REFMAP_LOAD_FACTOR) * 256.0f);
     35 
     36     return count >= buckets * n / d;
     37 }
     38 
     39 #define _flatcc_refmap_probe(k, i, N) ((k + i) & N)
     40 
     41 void flatcc_refmap_clear(flatcc_refmap_t *refmap)
     42 {
     43     if (refmap->table && refmap->table != refmap->min_table) {
     44         _flatcc_refmap_free(refmap->table);
     45     }
     46     flatcc_refmap_init(refmap);
     47 }
     48 
     49 static inline size_t _flatcc_refmap_hash(const void *src)
     50 {
     51     /* MurmurHash3 64-bit finalizer */
     52     uint64_t x;
     53 
     54     x = (uint64_t)((size_t)src) ^ _flatcc_refmap_seed;
     55 
     56     x ^= x >> 33;
     57     x *= 0xff51afd7ed558ccdULL;
     58     x ^= x >> 33;
     59     x *= 0xc4ceb9fe1a85ec53ULL;
     60     x ^= x >> 33;
     61     return (size_t)x;
     62 }
     63 
     64 void flatcc_refmap_reset(flatcc_refmap_t *refmap)
     65 {
     66     if (refmap->count) {
     67         memset(refmap->table, 0, sizeof(refmap->table[0]) * refmap->buckets);
     68     }
     69     refmap->count = 0;
     70 }
     71 
     72 /*
     73  * Technically resize also supports shrinking which may be useful for
     74  * adapations, but the current hash table never deletes individual items.
     75  */
     76 int flatcc_refmap_resize(flatcc_refmap_t *refmap, size_t count)
     77 {
     78     const size_t min_buckets = sizeof(refmap->min_table) / sizeof(refmap->min_table[0]);
     79 
     80     size_t i;
     81     size_t buckets;
     82     size_t buckets_old;
     83     struct flatcc_refmap_item *T_old;
     84 
     85     if (count < refmap->count) {
     86         count = refmap->count;
     87     }
     88     buckets = min_buckets;
     89 
     90     while (_flatcc_refmap_above_load_factor(count, buckets)) {
     91         buckets *= 2;
     92     }
     93     if (refmap->buckets == buckets) {
     94         return 0;
     95     }
     96     T_old = refmap->table;
     97     buckets_old = refmap->buckets;
     98     if (buckets == min_buckets) {
     99         memset(refmap->min_table, 0, sizeof(refmap->min_table));
    100         refmap->table = refmap->min_table;
    101     } else {
    102         refmap->table = _flatcc_refmap_calloc(buckets, sizeof(refmap->table[0]));
    103         if (refmap->table == 0) {
    104             refmap->table = T_old;
    105             FLATCC_ASSERT(0); /* out of memory */
    106             return -1;
    107         }
    108     }
    109     refmap->buckets = buckets;
    110     refmap->count = 0;
    111     for (i = 0; i < buckets_old; ++i) {
    112         if (T_old[i].src) {
    113             flatcc_refmap_insert(refmap, T_old[i].src, T_old[i].ref);
    114         }
    115     }
    116     if (T_old && T_old != refmap->min_table) {
    117         _flatcc_refmap_free(T_old);
    118     }
    119     return 0;
    120 }
    121 
    122 flatcc_refmap_ref_t flatcc_refmap_insert(flatcc_refmap_t *refmap, const void *src, flatcc_refmap_ref_t ref)
    123 {
    124     struct flatcc_refmap_item *T;
    125     size_t N, i, j, k;
    126 
    127     if (src == 0) return ref;
    128     if (_flatcc_refmap_above_load_factor(refmap->count, refmap->buckets)) {
    129         if (flatcc_refmap_resize(refmap, refmap->count * 2)) {
    130             return flatcc_refmap_not_found; /* alloc failed */
    131         }
    132     }
    133     T = refmap->table;
    134     N = refmap->buckets - 1;
    135     k = _flatcc_refmap_hash(src);
    136     i = 0;
    137     j = _flatcc_refmap_probe(k, i, N);
    138     while (T[j].src) {
    139         if (T[j].src == src) {
    140             return T[j].ref = ref;
    141         }
    142         ++i;
    143         j = _flatcc_refmap_probe(k, i, N);
    144     }
    145     ++refmap->count;
    146     T[j].src = src;
    147     return T[j].ref = ref;
    148 }
    149 
    150 flatcc_refmap_ref_t flatcc_refmap_find(flatcc_refmap_t *refmap, const void *src)
    151 {
    152     struct flatcc_refmap_item *T;
    153     size_t N, i, j, k;
    154 
    155     if (refmap->count == 0) {
    156         return flatcc_refmap_not_found;
    157     }
    158     T = refmap->table;
    159     N = refmap->buckets - 1;
    160     k = _flatcc_refmap_hash(src);
    161     i = 0;
    162     j = _flatcc_refmap_probe(k, i, N);
    163     while (T[j].src) {
    164         if (T[j].src == src) return T[j].ref;
    165         ++i;
    166         j = _flatcc_refmap_probe(k, i, N);
    167     }
    168     return flatcc_refmap_not_found;
    169 }
    170 
    171 /*
    172  * To run test from project root:
    173  *
    174  *  cc -D FLATCC_REFMAP_TEST -I include src/runtime/refmap.c -o test_refmap && ./test_refmap
    175  *
    176  */
    177 #ifdef FLATCC_REFMAP_TEST
    178 
    179 #include <stdio.h>
    180 
    181 #ifndef FLATCC_REFMAP_H
    182 #include "flatcc/flatcc_refmap.h"
    183 #endif
    184 
    185 #define test(x) do { if (!(x)) { fprintf(stderr, "%02d: refmap test failed\n", __LINE__); exit(-1); } } while (0)
    186 #define test_start() fprintf(stderr, "starting refmap test ...\n")
    187 #define test_ok() fprintf(stderr, "refmap test succeeded\n")
    188 
    189 int main()
    190 {
    191     int i;
    192     int data[1000];
    193     int a = 1;
    194     int b = 2;
    195     int c = 3;
    196     flatcc_refmap_t refmap;
    197 
    198     flatcc_refmap_init(&refmap);
    199 
    200     test(flatcc_refmap_find(&refmap, &a) == flatcc_refmap_not_found);
    201     test(flatcc_refmap_find(&refmap, &b) == flatcc_refmap_not_found);
    202     test(flatcc_refmap_find(&refmap, &c) == flatcc_refmap_not_found);
    203     test(flatcc_refmap_find(&refmap, 0) == flatcc_refmap_not_found);
    204     test(flatcc_refmap_find(&refmap, &a) == 0);
    205 
    206     test(flatcc_refmap_insert(&refmap, &a, 42) == 42);
    207     test(flatcc_refmap_find(&refmap, &a) == 42);
    208     test(flatcc_refmap_find(&refmap, &b) == flatcc_refmap_not_found);
    209     test(flatcc_refmap_find(&refmap, &c) == flatcc_refmap_not_found);
    210     test(flatcc_refmap_insert(&refmap, &a, 42) == 42);
    211     test(flatcc_refmap_find(&refmap, &a) == 42);
    212     test(refmap.count == 1);
    213     test(flatcc_refmap_insert(&refmap, &a, 43) == 43);
    214     test(flatcc_refmap_find(&refmap, &a) == 43);
    215     test(refmap.count == 1);
    216     test(flatcc_refmap_insert(&refmap, &b, -10) == -10);
    217     test(flatcc_refmap_insert(&refmap, &c, 100) == 100);
    218     test(refmap.count == 3);
    219     test(flatcc_refmap_find(&refmap, &a) == 43);
    220     test(flatcc_refmap_find(&refmap, &b) == -10);
    221     test(flatcc_refmap_find(&refmap, &c) == 100);
    222 
    223     test(flatcc_refmap_insert(&refmap, 0, 1000) == 1000);
    224     test(flatcc_refmap_find(&refmap, 0) == 0);
    225     test(refmap.count == 3);
    226 
    227     test(flatcc_refmap_insert(&refmap, &b, 0) == 0);
    228     test(flatcc_refmap_find(&refmap, &b) == 0);
    229     test(refmap.count == 3);
    230 
    231     flatcc_refmap_reset(&refmap);
    232     test(refmap.count == 0);
    233     test(refmap.buckets > 0);
    234     for (i = 0; i < 1000; ++i) {
    235         test(flatcc_refmap_insert(&refmap, data + i, i + 42) == i + 42);
    236     }
    237     test(refmap.count == 1000);
    238     for (i = 0; i < 1000; ++i) {
    239         test(flatcc_refmap_find(&refmap, data + i) == i + 42);
    240     }
    241     flatcc_refmap_clear(&refmap);
    242     test(refmap.count == 0);
    243     test(refmap.buckets == 0);
    244     test_ok();
    245     return 0;
    246 }
    247 
    248 #endif /* FLATCC_REFMAP_TEST */