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