1/* Rax -- A radix tree implementation.
2 *
3 * Copyright (c) 2017-2018, Salvatore Sanfilippo <antirez at gmail dot com>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * * Redistributions of source code must retain the above copyright notice,
10 * this list of conditions and the following disclaimer.
11 * * Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * * Neither the name of Redis nor the names of its contributors may be used
15 * to endorse or promote products derived from this software without
16 * specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 * POSSIBILITY OF SUCH DAMAGE.
29 */
30
31#ifndef RAX_H
32#define RAX_H
33
34#include <stdint.h>
35
36/* Representation of a radix tree as implemented in this file, that contains
37 * the strings "foo", "foobar" and "footer" after the insertion of each
38 * word. When the node represents a key inside the radix tree, we write it
39 * between [], otherwise it is written between ().
40 *
41 * This is the vanilla representation:
42 *
43 * (f) ""
44 * \
45 * (o) "f"
46 * \
47 * (o) "fo"
48 * \
49 * [t b] "foo"
50 * / \
51 * "foot" (e) (a) "foob"
52 * / \
53 * "foote" (r) (r) "fooba"
54 * / \
55 * "footer" [] [] "foobar"
56 *
57 * However, this implementation implements a very common optimization where
58 * successive nodes having a single child are "compressed" into the node
59 * itself as a string of characters, each representing a next-level child,
60 * and only the link to the node representing the last character node is
61 * provided inside the representation. So the above representation is turned
62 * into:
63 *
64 * ["foo"] ""
65 * |
66 * [t b] "foo"
67 * / \
68 * "foot" ("er") ("ar") "foob"
69 * / \
70 * "footer" [] [] "foobar"
71 *
72 * However this optimization makes the implementation a bit more complex.
73 * For instance if a key "first" is added in the above radix tree, a
74 * "node splitting" operation is needed, since the "foo" prefix is no longer
75 * composed of nodes having a single child one after the other. This is the
76 * above tree and the resulting node splitting after this event happens:
77 *
78 *
79 * (f) ""
80 * /
81 * (i o) "f"
82 * / \
83 * "firs" ("rst") (o) "fo"
84 * / \
85 * "first" [] [t b] "foo"
86 * / \
87 * "foot" ("er") ("ar") "foob"
88 * / \
89 * "footer" [] [] "foobar"
90 *
91 * Similarly after deletion, if a new chain of nodes having a single child
92 * is created (the chain must also not include nodes that represent keys),
93 * it must be compressed back into a single node.
94 *
95 */
96
97#define RAX_NODE_MAX_SIZE ((1<<29)-1)
98typedef struct raxNode {
99 uint32_t iskey:1; /* Does this node contain a key? */
100 uint32_t isnull:1; /* Associated value is NULL (don't store it). */
101 uint32_t iscompr:1; /* Node is compressed. */
102 uint32_t size:29; /* Number of children, or compressed string len. */
103 /* Data layout is as follows:
104 *
105 * If node is not compressed we have 'size' bytes, one for each children
106 * character, and 'size' raxNode pointers, point to each child node.
107 * Note how the character is not stored in the children but in the
108 * edge of the parents:
109 *
110 * [header iscompr=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?)
111 *
112 * if node is compressed (iscompr bit is 1) the node has 1 children.
113 * In that case the 'size' bytes of the string stored immediately at
114 * the start of the data section, represent a sequence of successive
115 * nodes linked one after the other, for which only the last one in
116 * the sequence is actually represented as a node, and pointed to by
117 * the current compressed node.
118 *
119 * [header iscompr=1][xyz][z-ptr](value-ptr?)
120 *
121 * Both compressed and not compressed nodes can represent a key
122 * with associated data in the radix tree at any level (not just terminal
123 * nodes).
124 *
125 * If the node has an associated key (iskey=1) and is not NULL
126 * (isnull=0), then after the raxNode pointers pointing to the
127 * children, an additional value pointer is present (as you can see
128 * in the representation above as "value-ptr" field).
129 */
130 unsigned char data[];
131} raxNode;
132
133typedef struct rax {
134 raxNode *head;
135 uint64_t numele;
136 uint64_t numnodes;
137} rax;
138
139/* Stack data structure used by raxLowWalk() in order to, optionally, return
140 * a list of parent nodes to the caller. The nodes do not have a "parent"
141 * field for space concerns, so we use the auxiliary stack when needed. */
142#define RAX_STACK_STATIC_ITEMS 32
143typedef struct raxStack {
144 void **stack; /* Points to static_items or an heap allocated array. */
145 size_t items, maxitems; /* Number of items contained and total space. */
146 /* Up to RAXSTACK_STACK_ITEMS items we avoid to allocate on the heap
147 * and use this static array of pointers instead. */
148 void *static_items[RAX_STACK_STATIC_ITEMS];
149 int oom; /* True if pushing into this stack failed for OOM at some point. */
150} raxStack;
151
152/* Optional callback used for iterators and be notified on each rax node,
153 * including nodes not representing keys. If the callback returns true
154 * the callback changed the node pointer in the iterator structure, and the
155 * iterator implementation will have to replace the pointer in the radix tree
156 * internals. This allows the callback to reallocate the node to perform
157 * very special operations, normally not needed by normal applications.
158 *
159 * This callback is used to perform very low level analysis of the radix tree
160 * structure, scanning each possible node (but the root node), or in order to
161 * reallocate the nodes to reduce the allocation fragmentation (this is the
162 * Redis application for this callback).
163 *
164 * This is currently only supported in forward iterations (raxNext) */
165typedef int (*raxNodeCallback)(raxNode **noderef);
166
167/* Radix tree iterator state is encapsulated into this data structure. */
168#define RAX_ITER_STATIC_LEN 128
169#define RAX_ITER_JUST_SEEKED (1<<0) /* Iterator was just seeked. Return current
170 element for the first iteration and
171 clear the flag. */
172#define RAX_ITER_EOF (1<<1) /* End of iteration reached. */
173#define RAX_ITER_SAFE (1<<2) /* Safe iterator, allows operations while
174 iterating. But it is slower. */
175typedef struct raxIterator {
176 int flags;
177 rax *rt; /* Radix tree we are iterating. */
178 unsigned char *key; /* The current string. */
179 void *data; /* Data associated to this key. */
180 size_t key_len; /* Current key length. */
181 size_t key_max; /* Max key len the current key buffer can hold. */
182 unsigned char key_static_string[RAX_ITER_STATIC_LEN];
183 raxNode *node; /* Current node. Only for unsafe iteration. */
184 raxStack stack; /* Stack used for unsafe iteration. */
185 raxNodeCallback node_cb; /* Optional node callback. Normally set to NULL. */
186} raxIterator;
187
188/* A special pointer returned for not found items. */
189extern void *raxNotFound;
190
191/* Exported API. */
192rax *raxNew(void);
193int raxInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old);
194int raxTryInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old);
195int raxRemove(rax *rax, unsigned char *s, size_t len, void **old);
196void *raxFind(rax *rax, unsigned char *s, size_t len);
197void raxFree(rax *rax);
198void raxFreeWithCallback(rax *rax, void (*free_callback)(void*));
199void raxStart(raxIterator *it, rax *rt);
200int raxSeek(raxIterator *it, const char *op, unsigned char *ele, size_t len);
201int raxNext(raxIterator *it);
202int raxPrev(raxIterator *it);
203int raxRandomWalk(raxIterator *it, size_t steps);
204int raxCompare(raxIterator *iter, const char *op, unsigned char *key, size_t key_len);
205void raxStop(raxIterator *it);
206int raxEOF(raxIterator *it);
207void raxShow(rax *rax);
208uint64_t raxSize(rax *rax);
209unsigned long raxTouch(raxNode *n);
210void raxSetDebugMsg(int onoff);
211
212/* Internal API. May be used by the node callback in order to access rax nodes
213 * in a low level way, so this function is exported as well. */
214void raxSetData(raxNode *n, void *data);
215
216#endif
217