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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
#define MAP_UNSET UINT64_C(0xFFFFFFFFFFFFFFFF)
#define MAP_KEYMASK UINT64_C(0xFFFFFFFFFF)
#define MAP_KEYSHIFT UINT64_C(40)
#define MAP_UNSET_VAL (MAP_UNSET >> MAP_KEYSHIFT)
typedef struct {
uint64_t n;
uint64_t capacity;
uint64_t randomizer;
uint64_t *table;
} h48map_t;
typedef struct {
uint64_t key;
uint64_t val;
} kvpair_t;
_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;
DBG_ASSERT(*p < map->capacity, kv,
"Error looping over map: given index %" PRIu64 " is out of "
"range [0,%" PRIu64 "]", *p, map->capacity);
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;
}
|
