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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
#ifndef CHEESEMAP
#define CHEESEMAP
////////////////////////////////
// options and includes
//
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#include CM_OPT_ASSERT_PATH
#ifndef assert
#error "assert is not defined"
#endif
typedef uintptr_t group_t;
typedef group_t bitmask_t;
enum {
CM_GROUP_SIZE = sizeof(group_t),
};
////////////////////////////////
// cheesemap callback functions
//
typedef uint64_t cm_hash_t;
/* memory methods */
typedef void* (*cm_malloc_fn)(uintptr_t size, uintptr_t alignment,
uint8_t* user);
typedef void (*cm_free_fn)(void* ptr, uint8_t* user);
/* hash and compare methods */
typedef cm_hash_t (*cm_hash_fn)(const uint8_t* key, uint8_t* user);
typedef bool (*cm_compare_fn)(const uint8_t* key1, const uint8_t* key2,
uint8_t* user);
////////////////////////////////
// callback methods needed by cheesemap
//
struct cheesemap_fns {
uint8_t *mem_usr, *map_usr;
cm_malloc_fn malloc;
cm_free_fn free;
cm_hash_fn hash;
cm_compare_fn compare;
};
////////////////////////////////
// raw cheesemap implementation
//
// layout:
// [entries...][control bits...][mirror first CM_GROUP_SIZE bits]
enum {
CM_INITIAL_CAPACITY = CM_GROUP_SIZE,
// -1 as i8, all bits set, top bit = 1
CM_CTRL_EMPTY = 0xFF, // 0b1111_1111
// -128 as i8, top bit = 1
CM_CTRL_DELETED = 0x80, // 0b1000_0000
// FULL entries have top bit = 0, lower 7 bits are H2 hash
CM_H2_MASK = 0x7F, // 0b0111_1111
// Mask to get bottom bit
CM_CTRL_END = 0x01, // 0b0000_0001
CM_FP_SIZE = 7
};
static inline uintptr_t cm_h1(cm_hash_t hash) {
return (uintptr_t)(hash >> CM_FP_SIZE);
}
static inline uint8_t cm_h2(cm_hash_t hash) {
uintptr_t top = hash >> (sizeof(cm_hash_t) * CHAR_BIT - CM_FP_SIZE);
return (uint8_t)(top & CM_H2_MASK);
}
extern const uint8_t CM_CTRL_STATIC_EMPTY[CM_GROUP_SIZE];
struct cheesemap_raw {
// number of buckets as mask
uintptr_t bucket_mask;
// number of entries in the map
uintptr_t count;
// number of entry left until resize
uintptr_t growth_left;
// pointer to the control bytes
uint8_t* ctrl;
};
#define cm_raw_new() \
((struct cheesemap_raw){.ctrl = (uint8_t*)CM_CTRL_STATIC_EMPTY})
bool cm_raw_insert(struct cheesemap_raw* map, const struct cheesemap_fns* fns,
uintptr_t key_size, const uint8_t* key, uintptr_t value_size,
const uint8_t* value);
void cm_raw_drop(struct cheesemap_raw* map, uintptr_t key_size,
uintptr_t value_size, const struct cheesemap_fns* fns);
////////////////////////////////
// cheesemap implementation
//
struct cheesemap {
uintptr_t key_size, value_size;
struct cheesemap_fns fns;
struct cheesemap_raw raw;
};
void cm_new(struct cheesemap* map, uintptr_t key_size, uintptr_t value_size,
uint8_t* mem_usr, cm_malloc_fn malloc, cm_free_fn free,
uint8_t* map_usr, cm_hash_fn hash, cm_compare_fn compare);
static inline void cm_drop(struct cheesemap* map) {
assert(map != NULL);
cm_raw_drop(&map->raw, map->key_size, map->value_size, &map->fns);
memset(map, 0, sizeof(*map));
}
#endif
|
