map.h (1996B)
1 STATIC void h48map_create(h48map_t [static 1], uint64_t, uint64_t); 2 STATIC void h48map_clear(h48map_t [static 1]); 3 STATIC void h48map_destroy(h48map_t [static 1]); 4 STATIC uint64_t h48map_lookup(h48map_t [static 1], uint64_t); 5 STATIC void h48map_insertmin(h48map_t [static 1], uint64_t, uint64_t); 6 STATIC uint64_t h48map_value(h48map_t [static 1], uint64_t); 7 STATIC kvpair_t h48map_nextkvpair(h48map_t [static 1], uint64_t [static 1]); 8 9 STATIC void 10 h48map_create(h48map_t map[static 1], uint64_t capacity, uint64_t randomizer) 11 { 12 map->capacity = capacity; 13 map->randomizer = randomizer; 14 15 map->table = malloc(map->capacity * sizeof(int64_t)); 16 h48map_clear(map); 17 } 18 19 STATIC void 20 h48map_clear(h48map_t map[static 1]) 21 { 22 memset(map->table, 0xFF, map->capacity * sizeof(uint64_t)); 23 map->n = 0; 24 } 25 26 STATIC void 27 h48map_destroy(h48map_t map[static 1]) 28 { 29 free(map->table); 30 } 31 32 STATIC_INLINE uint64_t 33 h48map_lookup(h48map_t map[static 1], uint64_t x) 34 { 35 uint64_t hash, i; 36 37 hash = ((x % map->capacity) * map->randomizer) % map->capacity; 38 for (i = hash; 39 map->table[i] != MAP_UNSET && (map->table[i] & MAP_KEYMASK) != x; 40 i = (i+1) % map->capacity 41 ) ; 42 43 return i; 44 } 45 46 STATIC_INLINE void 47 h48map_insertmin(h48map_t map[static 1], uint64_t key, uint64_t val) 48 { 49 uint64_t i, oldval, min; 50 51 i = h48map_lookup(map, key); 52 oldval = map->table[i] >> MAP_KEYSHIFT; 53 min = MIN(val, oldval); 54 55 map->n += map->table[i] == MAP_UNSET; 56 map->table[i] = (key & MAP_KEYMASK) | (min << MAP_KEYSHIFT); 57 } 58 59 STATIC_INLINE uint64_t 60 h48map_value(h48map_t map[static 1], uint64_t key) 61 { 62 return map->table[h48map_lookup(map, key)] >> MAP_KEYSHIFT; 63 } 64 65 STATIC kvpair_t 66 h48map_nextkvpair(h48map_t map[static 1], uint64_t p[static 1]) 67 { 68 kvpair_t kv; 69 uint64_t pair; 70 71 kv.key = MAP_KEYMASK; 72 kv.val = MAP_UNSET_VAL; 73 74 for ( ; *p < map->capacity; (*p)++) { 75 if (map->table[*p] != MAP_UNSET) { 76 pair = map->table[(*p)++]; 77 kv.key = pair & MAP_KEYMASK; 78 kv.val = pair >> MAP_KEYSHIFT; 79 return kv; 80 } 81 } 82 83 return kv; 84 }