refmap.c (7193B)
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_rtconfig.h" 17 #include "flatcc_refmap.h" 18 #include "flatcc_alloc.h" 19 #include "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_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 */