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
|
#ifndef CHEESEMAP
#define CHEESEMAP
////////////////////////////////
// options and includes
//
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#include CM_OPT_ASSERT_PATH
#ifndef assert
#error "assert is not defined"
#endif
enum {
CM_GROUP_SIZE = 8,
};
////////////////////////////////
// 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,
CM_CTRL_EMPTY = 0x80,
CM_CTRL_DELETED = 0xFE,
CM_H2_MASK = 0x7F,
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) {
return (uint8_t)(hash & CM_H2_MASK);
}
struct cheesemap_raw {
// mask of the capacity
uintptr_t cap_mask;
// number of entries in the map
uintptr_t entry_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){0})
void cm_raw_drop(struct cheesemap_raw* map, uintptr_t entry_size,
struct cheesemap_fns* fns);
////////////////////////////////
// cheesemap implementation
//
struct cheesemap {
uintptr_t entry_size;
struct cheesemap_fns fns;
struct cheesemap_raw raw;
};
void cm_new(struct cheesemap* map, uintptr_t entry_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->entry_size, &map->fns);
memset(map, 0, sizeof(*map));
}
#endif
|
