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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
#ifndef ART_ART_H
#define ART_ART_H
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
/*
* This file contains an implementation of an Adaptive Radix Tree as described
* in https://db.in.tum.de/~leis/papers/ART.pdf.
*
* The ART contains the keys in _byte lexographical_ order.
*
* Other features:
* * Fixed 48 bit key length: all keys are assumed to be be 48 bits in size.
* This allows us to put the key and key prefixes directly in nodes, reducing
* indirection at no additional memory overhead.
* * Key compression: the only inner nodes created are at points where key
* chunks _differ_. This means that if there are two entries with different
* high 48 bits, then there is only one inner node containing the common key
* prefix, and two leaves.
* * Intrusive leaves: the leaf struct is included in user values. This removes
* a layer of indirection.
*/
// Fixed length of keys in the ART. All keys are assumed to be of this length.
#define ART_KEY_BYTES 6
#ifdef __cplusplus
extern "C" {
namespace roaring {
namespace internal {
#endif
typedef uint8_t art_key_chunk_t;
typedef struct art_node_s art_node_t;
/**
* Wrapper to allow an empty tree.
*/
typedef struct art_s {
art_node_t *root;
} art_t;
/**
* Values inserted into the tree have to be cast-able to art_val_t. This
* improves performance by reducing indirection.
*
* NOTE: Value pointers must be unique! This is because each value struct
* contains the key corresponding to the value.
*/
typedef struct art_val_s {
art_key_chunk_t key[ART_KEY_BYTES];
} art_val_t;
/**
* Compares two keys, returns their relative order:
* * Key 1 < key 2: returns a negative value
* * Key 1 == key 2: returns 0
* * Key 1 > key 2: returns a positive value
*/
int art_compare_keys(const art_key_chunk_t key1[],
const art_key_chunk_t key2[]);
/**
* Inserts the given key and value.
*/
void art_insert(art_t *art, const art_key_chunk_t *key, art_val_t *val);
/**
* Returns the value erased, NULL if not found.
*/
art_val_t *art_erase(art_t *art, const art_key_chunk_t *key);
/**
* Returns the value associated with the given key, NULL if not found.
*/
art_val_t *art_find(const art_t *art, const art_key_chunk_t *key);
/**
* Returns true if the ART is empty.
*/
bool art_is_empty(const art_t *art);
/**
* Frees the nodes of the ART except the values, which the user is expected to
* free.
*/
void art_free(art_t *art);
/**
* Returns the size in bytes of the ART. Includes size of pointers to values,
* but not the values themselves.
*/
size_t art_size_in_bytes(const art_t *art);
/**
* Prints the ART using printf, useful for debugging.
*/
void art_printf(const art_t *art);
/**
* Callback for validating the value stored in a leaf.
*
* Should return true if the value is valid, false otherwise
* If false is returned, `*reason` should be set to a static string describing
* the reason for the failure.
*/
typedef bool (*art_validate_cb_t)(const art_val_t *val, const char **reason);
/**
* Validate the ART tree, ensuring it is internally consistent.
*/
bool art_internal_validate(const art_t *art, const char **reason,
art_validate_cb_t validate_cb);
/**
* ART-internal iterator bookkeeping. Users should treat this as an opaque type.
*/
typedef struct art_iterator_frame_s {
art_node_t *node;
uint8_t index_in_node;
} art_iterator_frame_t;
/**
* Users should only access `key` and `value` in iterators. The iterator is
* valid when `value != NULL`.
*/
typedef struct art_iterator_s {
art_key_chunk_t key[ART_KEY_BYTES];
art_val_t *value;
uint8_t depth; // Key depth
uint8_t frame; // Node depth
// State for each node in the ART the iterator has travelled from the root.
// This is `ART_KEY_BYTES + 1` because it includes state for the leaf too.
art_iterator_frame_t frames[ART_KEY_BYTES + 1];
} art_iterator_t;
/**
* Creates an iterator initialzed to the first or last entry in the ART,
* depending on `first`. The iterator is not valid if there are no entries in
* the ART.
*/
art_iterator_t art_init_iterator(const art_t *art, bool first);
/**
* Returns an initialized iterator positioned at a key equal to or greater than
* the given key, if it exists.
*/
art_iterator_t art_lower_bound(const art_t *art, const art_key_chunk_t *key);
/**
* Returns an initialized iterator positioned at a key greater than the given
* key, if it exists.
*/
art_iterator_t art_upper_bound(const art_t *art, const art_key_chunk_t *key);
/**
* The following iterator movement functions return true if a new entry was
* encountered.
*/
bool art_iterator_move(art_iterator_t *iterator, bool forward);
bool art_iterator_next(art_iterator_t *iterator);
bool art_iterator_prev(art_iterator_t *iterator);
/**
* Moves the iterator forward to a key equal to or greater than the given key.
*/
bool art_iterator_lower_bound(art_iterator_t *iterator,
const art_key_chunk_t *key);
/**
* Insert the value and positions the iterator at the key.
*/
void art_iterator_insert(art_t *art, art_iterator_t *iterator,
const art_key_chunk_t *key, art_val_t *val);
/**
* Erase the value pointed at by the iterator. Moves the iterator to the next
* leaf. Returns the value erased or NULL if nothing was erased.
*/
art_val_t *art_iterator_erase(art_t *art, art_iterator_t *iterator);
#ifdef __cplusplus
} // extern "C"
} // namespace roaring
} // namespace internal
#endif
#endif
|
