Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * radixtree.h
4 : : * Template for adaptive radix tree.
5 : : *
6 : : * A template to generate an "adaptive radix tree", specialized for value
7 : : * types and for local/shared memory.
8 : : *
9 : : * The concept originates from the paper "The Adaptive Radix Tree: ARTful
10 : : * Indexing for Main-Memory Databases" by Viktor Leis, Alfons Kemper,
11 : : * and Thomas Neumann, 2013.
12 : : *
13 : : * Radix trees have some advantages over hash tables:
14 : : * - The keys are logically ordered, allowing efficient sorted iteration
15 : : * and range queries
16 : : * - Operations using keys that are lexicographically close together
17 : : * will have favorable memory locality
18 : : * - Memory use grows gradually rather than by doubling
19 : : * - The key does not need to be stored with the value, since the key
20 : : * is implicitly contained in the path to the value
21 : : *
22 : : * Some disadvantages are:
23 : : * - Point queries (along with insertion and deletion) are slower than
24 : : * a linear probing hash table as in simplehash.h
25 : : * - Memory usage varies by key distribution, so is difficult to predict
26 : : *
27 : : * A classic radix tree consists of nodes, each containing an array of
28 : : * pointers to child nodes. The size of the array is determined by the
29 : : * "span" of the tree, which is the number of bits of the key used to
30 : : * index into the array. For example, with a span of 6, a "chunk"
31 : : * of 6 bits is extracted from the key at each node traversal, and
32 : : * the arrays thus have a "fanout" of 2^6 or 64 entries. A large span
33 : : * allows a shorter tree, but requires larger arrays that may be mostly
34 : : * wasted space.
35 : : *
36 : : * The key idea of the adaptive radix tree is to choose different
37 : : * data structures based on the number of child nodes. A node will
38 : : * start out small when it is first populated, and when it is full,
39 : : * it is replaced by the next larger size. Conversely, when a node
40 : : * becomes mostly empty, it is replaced by the next smaller node. The
41 : : * bulk of the code complexity in this module stems from this dynamic
42 : : * switching. One mitigating factor is using a span of 8, since bytes
43 : : * are directly addressable.
44 : : *
45 : : * The ART paper mentions three ways to implement leaves:
46 : : *
47 : : * "- Single-value leaves: The values are stored using an addi-
48 : : * tional leaf node type which stores one value.
49 : : * - Multi-value leaves: The values are stored in one of four
50 : : * different leaf node types, which mirror the structure of
51 : : * inner nodes, but contain values instead of pointers.
52 : : * - Combined pointer/value slots: If values fit into point-
53 : : * ers, no separate node types are necessary. Instead, each
54 : : * pointer storage location in an inner node can either
55 : : * store a pointer or a value."
56 : : *
57 : : * We use a form of "combined pointer/value slots", as recommended. Values
58 : : * of size (if fixed at compile time) equal or smaller than the platform's
59 : : * pointer type are stored in the child slots of the last level node,
60 : : * while larger values are the same as "single-value" leaves above. This
61 : : * offers flexibility and efficiency. Variable-length types are currently
62 : : * treated as single-value leaves for simplicity, but future work may
63 : : * allow those to be stored in the child pointer arrays, when they're
64 : : * small enough.
65 : : *
66 : : * There are two other techniques described in the paper that are not
67 : : * impemented here:
68 : : * - path compression "...removes all inner nodes that have only a single child."
69 : : * - lazy path expansion "...inner nodes are only created if they are required
70 : : * to distinguish at least two leaf nodes."
71 : : *
72 : : * We do have a form of "poor man's path compression", however, enabled by
73 : : * only supporting unsigned integer keys (for now assumed to be 64-bit):
74 : : * A tree doesn't contain paths where the highest bytes of all keys are
75 : : * zero. That way, the tree's height adapts to the distribution of keys.
76 : : *
77 : : * To handle concurrency, we use a single reader-writer lock for the
78 : : * radix tree. If concurrent write operations are possible, the tree
79 : : * must be exclusively locked during write operations such as RT_SET()
80 : : * and RT_DELETE(), and share locked during read operations such as
81 : : * RT_FIND() and RT_BEGIN_ITERATE().
82 : : *
83 : : * TODO: The current locking mechanism is not optimized for high
84 : : * concurrency with mixed read-write workloads. In the future it might
85 : : * be worthwhile to replace it with the Optimistic Lock Coupling or
86 : : * ROWEX mentioned in the paper "The ART of Practical Synchronization"
87 : : * by the same authors as the ART paper, 2016.
88 : : *
89 : : * To generate a radix tree and associated functions for a use case
90 : : * several macros have to be #define'ed before this file is included.
91 : : * Including the file #undef's all those, so a new radix tree can be
92 : : * generated afterwards.
93 : : *
94 : : * The relevant parameters are:
95 : : * - RT_PREFIX - prefix for all symbol names generated. A prefix of "foo"
96 : : * will result in radix tree type "foo_radix_tree" and functions like
97 : : * "foo_create"/"foo_free" and so forth.
98 : : * - RT_DECLARE - if defined function prototypes and type declarations are
99 : : * generated
100 : : * - RT_DEFINE - if defined function definitions are generated
101 : : * - RT_SCOPE - in which scope (e.g. extern, static inline) do function
102 : : * declarations reside
103 : : * - RT_VALUE_TYPE - the type of the value.
104 : : * - RT_VARLEN_VALUE_SIZE() - for variable length values, an expression
105 : : * involving a pointer to the value type, to calculate size.
106 : : * NOTE: implies that the value is in fact variable-length,
107 : : * so do not set for fixed-length values.
108 : : * - RT_RUNTIME_EMBEDDABLE_VALUE - for variable length values, allows
109 : : * storing the value in a child pointer slot, rather than as a single-
110 : : * value leaf, if small enough. This requires that the value, when
111 : : * read as a child pointer, can be tagged in the lowest bit.
112 : : *
113 : : * Optional parameters:
114 : : * - RT_SHMEM - if defined, the radix tree is created in the DSA area
115 : : * so that multiple processes can access it simultaneously.
116 : : * - RT_DEBUG - if defined add stats tracking and debugging functions
117 : : *
118 : : * Interface
119 : : * ---------
120 : : *
121 : : * RT_CREATE - Create a new, empty radix tree
122 : : * RT_FREE - Free the radix tree
123 : : * RT_FIND - Lookup the value for a given key
124 : : * RT_SET - Set a key-value pair
125 : : * RT_BEGIN_ITERATE - Begin iterating through all key-value pairs
126 : : * RT_ITERATE_NEXT - Return next key-value pair, if any
127 : : * RT_END_ITERATE - End iteration
128 : : * RT_MEMORY_USAGE - Get the memory as measured by space in memory context blocks
129 : : *
130 : : * Interface for Shared Memory
131 : : * ---------
132 : : *
133 : : * RT_ATTACH - Attach to the radix tree
134 : : * RT_DETACH - Detach from the radix tree
135 : : * RT_LOCK_EXCLUSIVE - Lock the radix tree in exclusive mode
136 : : * RT_LOCK_SHARE - Lock the radix tree in share mode
137 : : * RT_UNLOCK - Unlock the radix tree
138 : : * RT_GET_HANDLE - Return the handle of the radix tree
139 : : *
140 : : * Optional Interface
141 : : * ---------
142 : : *
143 : : * RT_DELETE - Delete a key-value pair. Declared/defined if RT_USE_DELETE is defined
144 : : *
145 : : *
146 : : * Copyright (c) 2024, PostgreSQL Global Development Group
147 : : *
148 : : * IDENTIFICATION
149 : : * src/include/lib/radixtree.h
150 : : *
151 : : *-------------------------------------------------------------------------
152 : : */
153 : :
154 : : #include "postgres.h"
155 : :
156 : : #include "nodes/bitmapset.h"
157 : : #include "port/pg_bitutils.h"
158 : : #include "port/simd.h"
159 : : #include "utils/dsa.h"
160 : : #include "utils/memutils.h"
161 : :
162 : : /* helpers */
163 : : #define RT_MAKE_PREFIX(a) CppConcat(a,_)
164 : : #define RT_MAKE_NAME(name) RT_MAKE_NAME_(RT_MAKE_PREFIX(RT_PREFIX),name)
165 : : #define RT_MAKE_NAME_(a,b) CppConcat(a,b)
166 : : /*
167 : : * stringify a macro constant, from https://gcc.gnu.org/onlinedocs/cpp/Stringizing.html
168 : : */
169 : : #define RT_STR(s) RT_STR_(s)
170 : : #define RT_STR_(s) #s
171 : :
172 : : /* function declarations */
173 : : #define RT_CREATE RT_MAKE_NAME(create)
174 : : #define RT_FREE RT_MAKE_NAME(free)
175 : : #define RT_FIND RT_MAKE_NAME(find)
176 : : #ifdef RT_SHMEM
177 : : #define RT_ATTACH RT_MAKE_NAME(attach)
178 : : #define RT_DETACH RT_MAKE_NAME(detach)
179 : : #define RT_GET_HANDLE RT_MAKE_NAME(get_handle)
180 : : #define RT_LOCK_EXCLUSIVE RT_MAKE_NAME(lock_exclusive)
181 : : #define RT_LOCK_SHARE RT_MAKE_NAME(lock_share)
182 : : #define RT_UNLOCK RT_MAKE_NAME(unlock)
183 : : #endif
184 : : #define RT_SET RT_MAKE_NAME(set)
185 : : #define RT_BEGIN_ITERATE RT_MAKE_NAME(begin_iterate)
186 : : #define RT_ITERATE_NEXT RT_MAKE_NAME(iterate_next)
187 : : #define RT_END_ITERATE RT_MAKE_NAME(end_iterate)
188 : : #ifdef RT_USE_DELETE
189 : : #define RT_DELETE RT_MAKE_NAME(delete)
190 : : #endif
191 : : #define RT_MEMORY_USAGE RT_MAKE_NAME(memory_usage)
192 : : #define RT_DUMP_NODE RT_MAKE_NAME(dump_node)
193 : : #define RT_STATS RT_MAKE_NAME(stats)
194 : :
195 : : /* internal helper functions (no externally visible prototypes) */
196 : : #define RT_CHILDPTR_IS_VALUE RT_MAKE_NAME(childptr_is_value)
197 : : #define RT_VALUE_IS_EMBEDDABLE RT_MAKE_NAME(value_is_embeddable)
198 : : #define RT_GET_SLOT_RECURSIVE RT_MAKE_NAME(get_slot_recursive)
199 : : #define RT_DELETE_RECURSIVE RT_MAKE_NAME(delete_recursive)
200 : : #define RT_ALLOC_NODE RT_MAKE_NAME(alloc_node)
201 : : #define RT_ALLOC_LEAF RT_MAKE_NAME(alloc_leaf)
202 : : #define RT_FREE_NODE RT_MAKE_NAME(free_node)
203 : : #define RT_FREE_LEAF RT_MAKE_NAME(free_leaf)
204 : : #define RT_FREE_RECURSE RT_MAKE_NAME(free_recurse)
205 : : #define RT_EXTEND_UP RT_MAKE_NAME(extend_up)
206 : : #define RT_EXTEND_DOWN RT_MAKE_NAME(extend_down)
207 : : #define RT_COPY_COMMON RT_MAKE_NAME(copy_common)
208 : : #define RT_PTR_SET_LOCAL RT_MAKE_NAME(ptr_set_local)
209 : : #define RT_NODE_16_SEARCH_EQ RT_MAKE_NAME(node_16_search_eq)
210 : : #define RT_NODE_4_GET_INSERTPOS RT_MAKE_NAME(node_4_get_insertpos)
211 : : #define RT_NODE_16_GET_INSERTPOS RT_MAKE_NAME(node_16_get_insertpos)
212 : : #define RT_SHIFT_ARRAYS_FOR_INSERT RT_MAKE_NAME(shift_arrays_for_insert)
213 : : #define RT_SHIFT_ARRAYS_AND_DELETE RT_MAKE_NAME(shift_arrays_and_delete)
214 : : #define RT_COPY_ARRAYS_FOR_INSERT RT_MAKE_NAME(copy_arrays_for_insert)
215 : : #define RT_COPY_ARRAYS_AND_DELETE RT_MAKE_NAME(copy_arrays_and_delete)
216 : : #define RT_NODE_48_IS_CHUNK_USED RT_MAKE_NAME(node_48_is_chunk_used)
217 : : #define RT_NODE_48_GET_CHILD RT_MAKE_NAME(node_48_get_child)
218 : : #define RT_NODE_256_IS_CHUNK_USED RT_MAKE_NAME(node_256_is_chunk_used)
219 : : #define RT_NODE_256_GET_CHILD RT_MAKE_NAME(node_256_get_child)
220 : : #define RT_KEY_GET_SHIFT RT_MAKE_NAME(key_get_shift)
221 : : #define RT_SHIFT_GET_MAX_VAL RT_MAKE_NAME(shift_get_max_val)
222 : : #define RT_NODE_SEARCH RT_MAKE_NAME(node_search)
223 : : #define RT_NODE_DELETE RT_MAKE_NAME(node_delete)
224 : : #define RT_NODE_INSERT RT_MAKE_NAME(node_insert)
225 : : #define RT_ADD_CHILD_4 RT_MAKE_NAME(add_child_4)
226 : : #define RT_ADD_CHILD_16 RT_MAKE_NAME(add_child_16)
227 : : #define RT_ADD_CHILD_48 RT_MAKE_NAME(add_child_48)
228 : : #define RT_ADD_CHILD_256 RT_MAKE_NAME(add_child_256)
229 : : #define RT_GROW_NODE_4 RT_MAKE_NAME(grow_node_4)
230 : : #define RT_GROW_NODE_16 RT_MAKE_NAME(grow_node_16)
231 : : #define RT_GROW_NODE_48 RT_MAKE_NAME(grow_node_48)
232 : : #define RT_REMOVE_CHILD_4 RT_MAKE_NAME(remove_child_4)
233 : : #define RT_REMOVE_CHILD_16 RT_MAKE_NAME(remove_child_16)
234 : : #define RT_REMOVE_CHILD_48 RT_MAKE_NAME(remove_child_48)
235 : : #define RT_REMOVE_CHILD_256 RT_MAKE_NAME(remove_child_256)
236 : : #define RT_SHRINK_NODE_16 RT_MAKE_NAME(shrink_child_16)
237 : : #define RT_SHRINK_NODE_48 RT_MAKE_NAME(shrink_child_48)
238 : : #define RT_SHRINK_NODE_256 RT_MAKE_NAME(shrink_child_256)
239 : : #define RT_NODE_ITERATE_NEXT RT_MAKE_NAME(node_iterate_next)
240 : : #define RT_VERIFY_NODE RT_MAKE_NAME(verify_node)
241 : :
242 : : /* type declarations */
243 : : #define RT_RADIX_TREE RT_MAKE_NAME(radix_tree)
244 : : #define RT_RADIX_TREE_CONTROL RT_MAKE_NAME(radix_tree_control)
245 : : #define RT_ITER RT_MAKE_NAME(iter)
246 : : #ifdef RT_SHMEM
247 : : #define RT_HANDLE RT_MAKE_NAME(handle)
248 : : #endif
249 : : #define RT_NODE RT_MAKE_NAME(node)
250 : : #define RT_CHILD_PTR RT_MAKE_NAME(child_ptr)
251 : : #define RT_NODE_ITER RT_MAKE_NAME(node_iter)
252 : : #define RT_NODE_4 RT_MAKE_NAME(node_4)
253 : : #define RT_NODE_16 RT_MAKE_NAME(node_16)
254 : : #define RT_NODE_48 RT_MAKE_NAME(node_48)
255 : : #define RT_NODE_256 RT_MAKE_NAME(node_256)
256 : : #define RT_SIZE_CLASS RT_MAKE_NAME(size_class)
257 : : #define RT_SIZE_CLASS_ELEM RT_MAKE_NAME(size_class_elem)
258 : : #define RT_SIZE_CLASS_INFO RT_MAKE_NAME(size_class_info)
259 : : #define RT_CLASS_4 RT_MAKE_NAME(class_4)
260 : : #define RT_CLASS_16_LO RT_MAKE_NAME(class_32_min)
261 : : #define RT_CLASS_16_HI RT_MAKE_NAME(class_32_max)
262 : : #define RT_CLASS_48 RT_MAKE_NAME(class_48)
263 : : #define RT_CLASS_256 RT_MAKE_NAME(class_256)
264 : :
265 : : /* generate forward declarations necessary to use the radix tree */
266 : : #ifdef RT_DECLARE
267 : :
268 : : typedef struct RT_RADIX_TREE RT_RADIX_TREE;
269 : : typedef struct RT_ITER RT_ITER;
270 : :
271 : : #ifdef RT_SHMEM
272 : : typedef dsa_pointer RT_HANDLE;
273 : : #endif
274 : :
275 : : #ifdef RT_SHMEM
276 : : RT_SCOPE RT_RADIX_TREE *RT_CREATE(MemoryContext ctx, dsa_area *dsa, int tranche_id);
277 : : RT_SCOPE RT_RADIX_TREE *RT_ATTACH(dsa_area *dsa, dsa_pointer dp);
278 : : RT_SCOPE void RT_DETACH(RT_RADIX_TREE * tree);
279 : : RT_SCOPE RT_HANDLE RT_GET_HANDLE(RT_RADIX_TREE * tree);
280 : : RT_SCOPE void RT_LOCK_EXCLUSIVE(RT_RADIX_TREE * tree);
281 : : RT_SCOPE void RT_LOCK_SHARE(RT_RADIX_TREE * tree);
282 : : RT_SCOPE void RT_UNLOCK(RT_RADIX_TREE * tree);
283 : : #else
284 : : RT_SCOPE RT_RADIX_TREE *RT_CREATE(MemoryContext ctx);
285 : : #endif
286 : : RT_SCOPE void RT_FREE(RT_RADIX_TREE * tree);
287 : :
288 : : RT_SCOPE RT_VALUE_TYPE *RT_FIND(RT_RADIX_TREE * tree, uint64 key);
289 : : RT_SCOPE bool RT_SET(RT_RADIX_TREE * tree, uint64 key, RT_VALUE_TYPE * value_p);
290 : :
291 : : #ifdef RT_USE_DELETE
292 : : RT_SCOPE bool RT_DELETE(RT_RADIX_TREE * tree, uint64 key);
293 : : #endif
294 : :
295 : : RT_SCOPE RT_ITER *RT_BEGIN_ITERATE(RT_RADIX_TREE * tree);
296 : : RT_SCOPE RT_VALUE_TYPE *RT_ITERATE_NEXT(RT_ITER * iter, uint64 *key_p);
297 : : RT_SCOPE void RT_END_ITERATE(RT_ITER * iter);
298 : :
299 : : RT_SCOPE uint64 RT_MEMORY_USAGE(RT_RADIX_TREE * tree);
300 : :
301 : : #ifdef RT_DEBUG
302 : : RT_SCOPE void RT_STATS(RT_RADIX_TREE * tree);
303 : : #endif
304 : :
305 : : #endif /* RT_DECLARE */
306 : :
307 : :
308 : : /* generate implementation of the radix tree */
309 : : #ifdef RT_DEFINE
310 : :
311 : : /* The number of bits encoded in one tree level */
312 : : #define RT_SPAN BITS_PER_BYTE
313 : :
314 : : /*
315 : : * The number of possible partial keys, and thus the maximum number of
316 : : * child pointers, for a node.
317 : : */
318 : : #define RT_NODE_MAX_SLOTS (1 << RT_SPAN)
319 : :
320 : : /* Mask for extracting a chunk from a key */
321 : : #define RT_CHUNK_MASK ((1 << RT_SPAN) - 1)
322 : :
323 : : /* Maximum shift needed to extract a chunk from a key */
324 : : #define RT_MAX_SHIFT RT_KEY_GET_SHIFT(UINT64_MAX)
325 : :
326 : : /* Maximum level a tree can reach for a key */
327 : : #define RT_MAX_LEVEL ((sizeof(uint64) * BITS_PER_BYTE) / RT_SPAN)
328 : :
329 : : /* Get a chunk from the key */
330 : : #define RT_GET_KEY_CHUNK(key, shift) ((uint8) (((key) >> (shift)) & RT_CHUNK_MASK))
331 : :
332 : : /* For accessing bitmaps */
333 : : #define RT_BM_IDX(x) ((x) / BITS_PER_BITMAPWORD)
334 : : #define RT_BM_BIT(x) ((x) % BITS_PER_BITMAPWORD)
335 : :
336 : : /*
337 : : * Node kinds
338 : : *
339 : : * The different node kinds are what make the tree "adaptive".
340 : : *
341 : : * Each node kind is associated with a different datatype and different
342 : : * search/set/delete/iterate algorithms adapted for its size. The largest
343 : : * kind, node256 is basically the same as a traditional radix tree,
344 : : * and would be most wasteful of memory when sparsely populated. The
345 : : * smaller nodes expend some additional CPU time to enable a smaller
346 : : * memory footprint.
347 : : *
348 : : * NOTE: There are 4 node kinds, and this should never be increased,
349 : : * for several reasons:
350 : : * 1. With 5 or more kinds, gcc tends to use a jump table for switch
351 : : * statements.
352 : : * 2. The 4 kinds can be represented with 2 bits, so we have the option
353 : : * in the future to tag the node pointer with the kind, even on
354 : : * platforms with 32-bit pointers. That would touch fewer cache lines
355 : : * during traversal and allow faster recovery from branch mispredicts.
356 : : * 3. We can have multiple size classes per node kind.
357 : : */
358 : : #define RT_NODE_KIND_4 0x00
359 : : #define RT_NODE_KIND_16 0x01
360 : : #define RT_NODE_KIND_48 0x02
361 : : #define RT_NODE_KIND_256 0x03
362 : : #define RT_NODE_KIND_COUNT 4
363 : :
364 : : /*
365 : : * Calculate the slab block size so that we can allocate at least 32 chunks
366 : : * from the block.
367 : : */
368 : : #define RT_SLAB_BLOCK_SIZE(size) \
369 : : Max(SLAB_DEFAULT_BLOCK_SIZE, pg_nextpower2_32(size * 32))
370 : :
371 : : /* Common header for all nodes */
372 : : typedef struct RT_NODE
373 : : {
374 : : /* Node kind, one per search/set algorithm */
375 : : uint8 kind;
376 : :
377 : : /*
378 : : * Max capacity for the current size class. Storing this in the node
379 : : * enables multiple size classes per node kind. uint8 is sufficient for
380 : : * all node kinds, because we only use this number to test if the node
381 : : * needs to grow. Since node256 never needs to grow, we let this overflow
382 : : * to zero.
383 : : */
384 : : uint8 fanout;
385 : :
386 : : /*
387 : : * Number of children. uint8 is sufficient for all node kinds, because
388 : : * nodes shrink when this number gets lower than some thresold. Since
389 : : * node256 cannot possibly have zero children, we let the counter overflow
390 : : * and we interpret zero as "256" for this node kind.
391 : : */
392 : : uint8 count;
393 : : } RT_NODE;
394 : :
395 : :
396 : : /* pointer returned by allocation */
397 : : #ifdef RT_SHMEM
398 : : #define RT_PTR_ALLOC dsa_pointer
399 : : #define RT_INVALID_PTR_ALLOC InvalidDsaPointer
400 : : #define RT_PTR_ALLOC_IS_VALID(ptr) DsaPointerIsValid(ptr)
401 : : #else
402 : : #define RT_PTR_ALLOC RT_NODE *
403 : : #define RT_INVALID_PTR_ALLOC NULL
404 : : #define RT_PTR_ALLOC_IS_VALID(ptr) PointerIsValid(ptr)
405 : : #endif
406 : :
407 : : /*
408 : : * A convenience type used when we need to work with a DSA pointer as well
409 : : * as its local pointer. For local memory, both members are the same, so
410 : : * we use a union.
411 : : */
412 : : #ifdef RT_SHMEM
413 : : typedef struct RT_CHILD_PTR
414 : : #else
415 : : typedef union RT_CHILD_PTR
416 : : #endif
417 : : {
418 : : RT_PTR_ALLOC alloc;
419 : : RT_NODE *local;
420 : : } RT_CHILD_PTR;
421 : :
422 : :
423 : : /*
424 : : * Helper macros and functions for value storage.
425 : : * We either embed values in the child slots of the last level
426 : : * node or store pointers to values to the child slots,
427 : : * depending on the value size.
428 : : */
429 : :
430 : : #ifdef RT_VARLEN_VALUE_SIZE
431 : : #define RT_GET_VALUE_SIZE(v) RT_VARLEN_VALUE_SIZE(v)
432 : : #else
433 : : #define RT_GET_VALUE_SIZE(v) sizeof(RT_VALUE_TYPE)
434 : : #endif
435 : :
436 : : /*
437 : : * Return true if the value can be stored in the child array
438 : : * of the lowest-level node, false otherwise.
439 : : */
440 : : static inline bool
38 john.naylor@postgres 441 :GNC 122664 : RT_VALUE_IS_EMBEDDABLE(RT_VALUE_TYPE * value_p)
442 : : {
443 : : #ifdef RT_VARLEN_VALUE_SIZE
444 : :
445 : : #ifdef RT_RUNTIME_EMBEDDABLE_VALUE
6 446 : 16130 : return RT_GET_VALUE_SIZE(value_p) <= sizeof(RT_PTR_ALLOC);
447 : : #else
448 : : return false;
449 : : #endif
450 : :
451 : : #else
38 452 : 106534 : return RT_GET_VALUE_SIZE(value_p) <= sizeof(RT_PTR_ALLOC);
453 : : #endif
454 : : }
455 : :
456 : : /*
457 : : * Return true if the child pointer contains the value, false
458 : : * if the child pointer is a leaf pointer.
459 : : */
460 : : static inline bool
461 : 4690020 : RT_CHILDPTR_IS_VALUE(RT_PTR_ALLOC child)
462 : : {
463 : : #ifdef RT_VARLEN_VALUE_SIZE
464 : :
465 : : #ifdef RT_RUNTIME_EMBEDDABLE_VALUE
466 : : /* check for pointer tag */
467 : : #ifdef RT_SHMEM
6 468 : 318025 : return child & 1;
469 : : #else
470 : 4079255 : return ((uintptr_t) child) & 1;
471 : : #endif
472 : :
473 : : #else
474 : : return false;
475 : : #endif
476 : :
477 : : #else
38 478 : 292740 : return sizeof(RT_VALUE_TYPE) <= sizeof(RT_PTR_ALLOC);
479 : : #endif
480 : : }
481 : :
482 : : /*
483 : : * Symbols for maximum possible fanout are declared first as they are
484 : : * required to declare each node kind. The declarations of other fanout
485 : : * values are followed as they need the struct sizes of each node kind.
486 : : */
487 : :
488 : : /* max possible key chunks without struct padding */
489 : : #define RT_FANOUT_4_MAX (8 - sizeof(RT_NODE))
490 : :
491 : : /* equal to two 128-bit SIMD registers, regardless of availability */
492 : : #define RT_FANOUT_16_MAX 32
493 : :
494 : : /*
495 : : * This also determines the number of bits necessary for the isset array,
496 : : * so we need to be mindful of the size of bitmapword. Since bitmapword
497 : : * can be 64 bits, the only values that make sense here are 64 and 128.
498 : : * The ART paper uses at most 64 for this node kind, and one advantage
499 : : * for us is that "isset" is a single bitmapword on most platforms,
500 : : * rather than an array, allowing the compiler to get rid of loops.
501 : : */
502 : : #define RT_FANOUT_48_MAX 64
503 : :
504 : : #define RT_FANOUT_256 RT_NODE_MAX_SLOTS
505 : :
506 : : /*
507 : : * Node structs, one for each "kind"
508 : : */
509 : :
510 : : /*
511 : : * node4 and node16 use one array for key chunks and another
512 : : * array of the same length for children. The keys and children
513 : : * are stored at corresponding positions, sorted by chunk.
514 : : */
515 : :
516 : : typedef struct RT_NODE_4
517 : : {
518 : : RT_NODE base;
519 : :
520 : : uint8 chunks[RT_FANOUT_4_MAX];
521 : :
522 : : /* number of children depends on size class */
523 : : RT_PTR_ALLOC children[FLEXIBLE_ARRAY_MEMBER];
524 : : } RT_NODE_4;
525 : :
526 : : typedef struct RT_NODE_16
527 : : {
528 : : RT_NODE base;
529 : :
530 : : uint8 chunks[RT_FANOUT_16_MAX];
531 : :
532 : : /* number of children depends on size class */
533 : : RT_PTR_ALLOC children[FLEXIBLE_ARRAY_MEMBER];
534 : : } RT_NODE_16;
535 : :
536 : : /*
537 : : * node48 uses a 256-element array indexed by key chunks. This array
538 : : * stores indexes into a second array containing the children.
539 : : */
540 : : typedef struct RT_NODE_48
541 : : {
542 : : RT_NODE base;
543 : :
544 : : /* The index of slots for each fanout */
545 : : uint8 slot_idxs[RT_NODE_MAX_SLOTS];
546 : :
547 : : /* Invalid index */
548 : : #define RT_INVALID_SLOT_IDX 0xFF
549 : :
550 : : /* bitmap to track which slots are in use */
551 : : bitmapword isset[RT_BM_IDX(RT_FANOUT_48_MAX)];
552 : :
553 : : /* number of children depends on size class */
554 : : RT_PTR_ALLOC children[FLEXIBLE_ARRAY_MEMBER];
555 : : } RT_NODE_48;
556 : :
557 : : /*
558 : : * node256 is the largest node type. This node has an array of
559 : : * children directly indexed by chunk. Unlike other node kinds,
560 : : * its array size is by definition fixed.
561 : : */
562 : : typedef struct RT_NODE_256
563 : : {
564 : : RT_NODE base;
565 : :
566 : : /* bitmap to track which slots are in use */
567 : : bitmapword isset[RT_BM_IDX(RT_FANOUT_256)];
568 : :
569 : : /* slots for 256 children */
570 : : RT_PTR_ALLOC children[RT_FANOUT_256];
571 : : } RT_NODE_256;
572 : :
573 : : #if defined(RT_SHMEM)
574 : : /*
575 : : * Make sure the all nodes (except for node256) fit neatly into a DSA
576 : : * size class. We assume the RT_FANOUT_4 is in the range where DSA size
577 : : * classes increment by 8 (as of PG17 up to 64 bytes), so we just hard
578 : : * code that one.
579 : : */
580 : :
581 : : #if SIZEOF_DSA_POINTER < 8
582 : : #define RT_FANOUT_16_LO ((96 - offsetof(RT_NODE_16, children)) / sizeof(RT_PTR_ALLOC))
583 : : #define RT_FANOUT_16_HI Min(RT_FANOUT_16_MAX, (160 - offsetof(RT_NODE_16, children)) / sizeof(RT_PTR_ALLOC))
584 : : #define RT_FANOUT_48 Min(RT_FANOUT_48_MAX, (512 - offsetof(RT_NODE_48, children)) / sizeof(RT_PTR_ALLOC))
585 : : #else
586 : : #define RT_FANOUT_16_LO ((160 - offsetof(RT_NODE_16, children)) / sizeof(RT_PTR_ALLOC))
587 : : #define RT_FANOUT_16_HI Min(RT_FANOUT_16_MAX, (320 - offsetof(RT_NODE_16, children)) / sizeof(RT_PTR_ALLOC))
588 : : #define RT_FANOUT_48 Min(RT_FANOUT_48_MAX, (768 - offsetof(RT_NODE_48, children)) / sizeof(RT_PTR_ALLOC))
589 : : #endif /* SIZEOF_DSA_POINTER < 8 */
590 : :
591 : : #else /* ! RT_SHMEM */
592 : :
593 : : /* doesn't really matter, but may as well use the namesake */
594 : : #define RT_FANOUT_16_LO 16
595 : : /* use maximum possible */
596 : : #define RT_FANOUT_16_HI RT_FANOUT_16_MAX
597 : : #define RT_FANOUT_48 RT_FANOUT_48_MAX
598 : :
599 : : #endif /* RT_SHMEM */
600 : :
601 : : /*
602 : : * To save memory in trees with sparse keys, it would make sense to have two
603 : : * size classes for the smallest kind (perhaps a high class of 5 and a low class
604 : : * of 2), but it would be more effective to utilize lazy expansion and
605 : : * path compression.
606 : : */
607 : : #define RT_FANOUT_4 4
608 : :
609 : : StaticAssertDecl(RT_FANOUT_4 <= RT_FANOUT_4_MAX, "watch struct padding");
610 : : StaticAssertDecl(RT_FANOUT_16_LO < RT_FANOUT_16_HI, "LO subclass bigger than HI");
611 : : StaticAssertDecl(RT_FANOUT_48 <= RT_FANOUT_48_MAX, "more slots than isset bits");
612 : :
613 : : /*
614 : : * Node size classes
615 : : *
616 : : * Nodes of different kinds necessarily belong to different size classes.
617 : : * One innovation in our implementation compared to the ART paper is
618 : : * decoupling the notion of size class from kind.
619 : : *
620 : : * The size classes within a given node kind have the same underlying
621 : : * type, but a variable number of children/values. This is possible
622 : : * because each type (except node256) contains metadata that work the
623 : : * same way regardless of how many child slots there are. The nodes
624 : : * can introspect their allocated capacity at runtime.
625 : : */
626 : : typedef enum RT_SIZE_CLASS
627 : : {
628 : : RT_CLASS_4 = 0,
629 : : RT_CLASS_16_LO,
630 : : RT_CLASS_16_HI,
631 : : RT_CLASS_48,
632 : : RT_CLASS_256
633 : : } RT_SIZE_CLASS;
634 : :
635 : : /* Information for each size class */
636 : : typedef struct RT_SIZE_CLASS_ELEM
637 : : {
638 : : const char *name;
639 : : int fanout;
640 : : size_t allocsize;
641 : : } RT_SIZE_CLASS_ELEM;
642 : :
643 : :
644 : : static const RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_INFO[] = {
645 : : [RT_CLASS_4] = {
646 : : .name = RT_STR(RT_PREFIX) "radix_tree node4",
647 : : .fanout = RT_FANOUT_4,
648 : : .allocsize = sizeof(RT_NODE_4) + RT_FANOUT_4 * sizeof(RT_PTR_ALLOC),
649 : : },
650 : : [RT_CLASS_16_LO] = {
651 : : .name = RT_STR(RT_PREFIX) "radix_tree node16_lo",
652 : : .fanout = RT_FANOUT_16_LO,
653 : : .allocsize = sizeof(RT_NODE_16) + RT_FANOUT_16_LO * sizeof(RT_PTR_ALLOC),
654 : : },
655 : : [RT_CLASS_16_HI] = {
656 : : .name = RT_STR(RT_PREFIX) "radix_tree node16_hi",
657 : : .fanout = RT_FANOUT_16_HI,
658 : : .allocsize = sizeof(RT_NODE_16) + RT_FANOUT_16_HI * sizeof(RT_PTR_ALLOC),
659 : : },
660 : : [RT_CLASS_48] = {
661 : : .name = RT_STR(RT_PREFIX) "radix_tree node48",
662 : : .fanout = RT_FANOUT_48,
663 : : .allocsize = sizeof(RT_NODE_48) + RT_FANOUT_48 * sizeof(RT_PTR_ALLOC),
664 : : },
665 : : [RT_CLASS_256] = {
666 : : .name = RT_STR(RT_PREFIX) "radix_tree node256",
667 : : .fanout = RT_FANOUT_256,
668 : : .allocsize = sizeof(RT_NODE_256),
669 : : },
670 : : };
671 : :
672 : : #define RT_NUM_SIZE_CLASSES lengthof(RT_SIZE_CLASS_INFO)
673 : :
674 : : #ifdef RT_SHMEM
675 : : /* A magic value used to identify our radix tree */
676 : : #define RT_RADIX_TREE_MAGIC 0x54A48167
677 : : #endif
678 : :
679 : : /* Contains the actual tree, plus ancillary info */
680 : : typedef struct RT_RADIX_TREE_CONTROL
681 : : {
682 : : #ifdef RT_SHMEM
683 : : RT_HANDLE handle;
684 : : uint32 magic;
685 : : LWLock lock;
686 : : #endif
687 : :
688 : : RT_PTR_ALLOC root;
689 : : uint64 max_val;
690 : : int64 num_keys;
691 : : int start_shift;
692 : :
693 : : /* statistics */
694 : : #ifdef RT_DEBUG
695 : : int64 num_nodes[RT_NUM_SIZE_CLASSES];
696 : : int64 num_leaves;
697 : : #endif
698 : : } RT_RADIX_TREE_CONTROL;
699 : :
700 : : /* Entry point for allocating and accessing the tree */
701 : : struct RT_RADIX_TREE
702 : : {
703 : : MemoryContext context;
704 : :
705 : : /* pointing to either local memory or DSA */
706 : : RT_RADIX_TREE_CONTROL *ctl;
707 : :
708 : : #ifdef RT_SHMEM
709 : : dsa_area *dsa;
710 : : #else
711 : : MemoryContextData *node_slabs[RT_NUM_SIZE_CLASSES];
712 : :
713 : : /* leaf_context is used only for single-value leaves */
714 : : MemoryContextData *leaf_context;
715 : : #endif
716 : : MemoryContextData *iter_context;
717 : : };
718 : :
719 : : /*
720 : : * Iteration support.
721 : : *
722 : : * Iterating over the radix tree produces each key/value pair in ascending
723 : : * order of the key.
724 : : */
725 : :
726 : : /* state for iterating over a single node */
727 : : typedef struct RT_NODE_ITER
728 : : {
729 : : RT_CHILD_PTR node;
730 : :
731 : : /*
732 : : * The next index of the chunk array in RT_NODE_KIND_4 and RT_NODE_KIND_16
733 : : * nodes, or the next chunk in RT_NODE_KIND_48 and RT_NODE_KIND_256 nodes.
734 : : * 0 for the initial value.
735 : : */
736 : : int idx;
737 : : } RT_NODE_ITER;
738 : :
739 : : /* state for iterating over the whole radix tree */
740 : : struct RT_ITER
741 : : {
742 : : RT_RADIX_TREE *tree;
743 : :
744 : : /*
745 : : * A stack to track iteration for each level. Level 0 is the lowest (or
746 : : * leaf) level
747 : : */
748 : : RT_NODE_ITER node_iters[RT_MAX_LEVEL];
749 : : int top_level;
750 : : int cur_level;
751 : :
752 : : /* The key constructed during iteration */
753 : : uint64 key;
754 : : };
755 : :
756 : :
757 : : /* verification (available only in assert-enabled builds) */
758 : : static void RT_VERIFY_NODE(RT_NODE * node);
759 : :
760 : : static inline void
761 : 18418954 : RT_PTR_SET_LOCAL(RT_RADIX_TREE * tree, RT_CHILD_PTR * node)
762 : : {
763 : : #ifdef RT_SHMEM
764 : 858439 : node->local = dsa_get_address(tree->dsa, node->alloc);
765 : : #endif
766 : 18418954 : }
767 : :
768 : : /* Convenience functions for node48 and node256 */
769 : :
770 : : /* Return true if there is an entry for "chunk" */
771 : : static inline bool
772 : 7959388 : RT_NODE_48_IS_CHUNK_USED(RT_NODE_48 * node, uint8 chunk)
773 : : {
774 : 7959388 : return node->slot_idxs[chunk] != RT_INVALID_SLOT_IDX;
775 : : }
776 : :
777 : : static inline RT_PTR_ALLOC *
778 : 512569 : RT_NODE_48_GET_CHILD(RT_NODE_48 * node, uint8 chunk)
779 : : {
780 : 512569 : return &node->children[node->slot_idxs[chunk]];
781 : : }
782 : :
783 : : /* Return true if there is an entry for "chunk" */
784 : : static inline bool
785 : 8515392 : RT_NODE_256_IS_CHUNK_USED(RT_NODE_256 * node, uint8 chunk)
786 : : {
787 : 8515392 : int idx = RT_BM_IDX(chunk);
788 : 8515392 : int bitnum = RT_BM_BIT(chunk);
789 : :
790 : 8515392 : return (node->isset[idx] & ((bitmapword) 1 << bitnum)) != 0;
791 : : }
792 : :
793 : : static inline RT_PTR_ALLOC *
794 : 4196346 : RT_NODE_256_GET_CHILD(RT_NODE_256 * node, uint8 chunk)
795 : : {
796 [ - + ]: 4196346 : Assert(RT_NODE_256_IS_CHUNK_USED(node, chunk));
797 : 4196346 : return &node->children[chunk];
798 : : }
799 : :
800 : : /*
801 : : * Return the smallest shift that will allowing storing the given key.
802 : : */
803 : : static inline int
804 : 84380 : RT_KEY_GET_SHIFT(uint64 key)
805 : : {
806 [ - + ]: 84380 : if (key == 0)
38 john.naylor@postgres 807 :UNC 0 : return 0;
808 : : else
38 john.naylor@postgres 809 :GNC 84380 : return (pg_leftmost_one_pos64(key) / RT_SPAN) * RT_SPAN;
810 : : }
811 : :
812 : : /*
813 : : * Return the max value that can be stored in the tree with the given shift.
814 : : */
815 : : static uint64
816 : 84342 : RT_SHIFT_GET_MAX_VAL(int shift)
817 : : {
818 [ + + ]: 84342 : if (shift == RT_MAX_SHIFT)
819 : 10 : return UINT64_MAX;
820 : : else
821 : 84332 : return (UINT64CONST(1) << (shift + RT_SPAN)) - 1;
822 : : }
823 : :
824 : : /*
825 : : * Allocate a new node with the given node kind and size class.
826 : : */
827 : : static inline RT_CHILD_PTR
828 : 110973 : RT_ALLOC_NODE(RT_RADIX_TREE * tree, const uint8 kind, const RT_SIZE_CLASS size_class)
829 : : {
830 : : RT_CHILD_PTR allocnode;
831 : : RT_NODE *node;
832 : : size_t allocsize;
833 : :
834 : 110973 : allocsize = RT_SIZE_CLASS_INFO[size_class].allocsize;
835 : :
836 : : #ifdef RT_SHMEM
837 : 33 : allocnode.alloc = dsa_allocate(tree->dsa, allocsize);
838 : : #else
839 : 110940 : allocnode.alloc = (RT_PTR_ALLOC) MemoryContextAlloc(tree->node_slabs[size_class],
840 : : allocsize);
841 : : #endif
842 : :
843 : 110973 : RT_PTR_SET_LOCAL(tree, &allocnode);
844 : 110973 : node = allocnode.local;
845 : :
846 : : /* initialize contents */
847 : :
848 : 110973 : memset(node, 0, sizeof(RT_NODE));
849 [ + + + - ]: 110973 : switch (kind)
850 : : {
851 : 108723 : case RT_NODE_KIND_4:
852 : : case RT_NODE_KIND_16:
853 : 108723 : break;
854 : 2164 : case RT_NODE_KIND_48:
855 : : {
856 : 2164 : RT_NODE_48 *n48 = (RT_NODE_48 *) node;
857 : :
858 : 2164 : memset(n48->isset, 0, sizeof(n48->isset));
859 : 2164 : memset(n48->slot_idxs, RT_INVALID_SLOT_IDX, sizeof(n48->slot_idxs));
860 : 2164 : break;
861 : : }
862 : 86 : case RT_NODE_KIND_256:
863 : : {
864 : 86 : RT_NODE_256 *n256 = (RT_NODE_256 *) node;
865 : :
866 : 86 : memset(n256->isset, 0, sizeof(n256->isset));
867 : 86 : break;
868 : : }
38 john.naylor@postgres 869 :UNC 0 : default:
870 : 0 : pg_unreachable();
871 : : }
872 : :
38 john.naylor@postgres 873 :GNC 110973 : node->kind = kind;
874 : :
875 : : /*
876 : : * For node256, this will actually overflow to zero, but that's okay
877 : : * because that node doesn't need to introspect this value.
878 : : */
879 : 110973 : node->fanout = RT_SIZE_CLASS_INFO[size_class].fanout;
880 : :
881 : : #ifdef RT_DEBUG
882 : : /* update the statistics */
883 : 26062 : tree->ctl->num_nodes[size_class]++;
884 : : #endif
885 : :
886 : 110973 : return allocnode;
887 : : }
888 : :
889 : : /*
890 : : * Allocate a new leaf.
891 : : */
892 : : static RT_CHILD_PTR
893 : 14320 : RT_ALLOC_LEAF(RT_RADIX_TREE * tree, size_t allocsize)
894 : : {
895 : : RT_CHILD_PTR leaf;
896 : :
897 : : #ifdef RT_SHMEM
898 : 247 : leaf.alloc = dsa_allocate(tree->dsa, allocsize);
899 : 247 : RT_PTR_SET_LOCAL(tree, &leaf);
900 : : #else
901 : 14073 : leaf.alloc = (RT_PTR_ALLOC) MemoryContextAlloc(tree->leaf_context, allocsize);
902 : : #endif
903 : :
904 : : #ifdef RT_DEBUG
38 john.naylor@postgres 905 :UNC 0 : tree->ctl->num_leaves++;
906 : : #endif
907 : :
38 john.naylor@postgres 908 :GNC 14320 : return leaf;
909 : : }
910 : :
911 : : /*
912 : : * Copy relevant members of the node header.
913 : : * This is a separate function in case other fields are added.
914 : : */
915 : : static inline void
916 : 10924 : RT_COPY_COMMON(RT_CHILD_PTR newnode, RT_CHILD_PTR oldnode)
917 : : {
918 : 10924 : (newnode.local)->count = (oldnode.local)->count;
919 : 10924 : }
920 : :
921 : : /* Free the given node */
922 : : static void
923 : 26644 : RT_FREE_NODE(RT_RADIX_TREE * tree, RT_CHILD_PTR node)
924 : : {
925 : : #ifdef RT_DEBUG
926 : : int i;
927 : :
928 : : /* update the statistics */
929 : :
930 [ + + ]: 40471 : for (i = 0; i < RT_NUM_SIZE_CLASSES; i++)
931 : : {
932 [ + + ]: 40455 : if ((node.local)->fanout == RT_SIZE_CLASS_INFO[i].fanout)
933 : 26014 : break;
934 : : }
935 : :
936 : : /*
937 : : * The fanout of node256 will appear to be zero within the node header
938 : : * because of overflow, so we need an extra check here.
939 : : */
940 [ + + ]: 26030 : if (i == RT_NUM_SIZE_CLASSES)
941 : 16 : i = RT_CLASS_256;
942 : :
943 : 26030 : tree->ctl->num_nodes[i]--;
944 [ - + ]: 26030 : Assert(tree->ctl->num_nodes[i] >= 0);
945 : : #endif
946 : :
947 : : #ifdef RT_SHMEM
948 : 16 : dsa_free(tree->dsa, node.alloc);
949 : : #else
950 : 26628 : pfree(node.alloc);
951 : : #endif
952 : 26644 : }
953 : :
954 : : static inline void
38 john.naylor@postgres 955 :UNC 0 : RT_FREE_LEAF(RT_RADIX_TREE * tree, RT_PTR_ALLOC leaf)
956 : : {
957 [ # # ]: 0 : Assert(leaf != tree->ctl->root);
958 : :
959 : : #ifdef RT_DEBUG
960 : : /* update the statistics */
961 : 0 : tree->ctl->num_leaves--;
962 [ # # ]: 0 : Assert(tree->ctl->num_leaves >= 0);
963 : : #endif
964 : :
965 : : #ifdef RT_SHMEM
966 : 0 : dsa_free(tree->dsa, leaf);
967 : : #else
968 : 0 : pfree(leaf);
969 : : #endif
970 : 0 : }
971 : :
972 : : /***************** SEARCH *****************/
973 : :
974 : : /*
975 : : * Return the address of the child corresponding to "chunk",
976 : : * or NULL if there is no such element.
977 : : */
978 : : static inline RT_PTR_ALLOC *
38 john.naylor@postgres 979 :GNC 2907303 : RT_NODE_16_SEARCH_EQ(RT_NODE_16 * node, uint8 chunk)
980 : : {
981 : 2907303 : int count = node->base.count;
982 : : #ifndef USE_NO_SIMD
983 : : Vector8 spread_chunk;
984 : : Vector8 haystack1;
985 : : Vector8 haystack2;
986 : : Vector8 cmp1;
987 : : Vector8 cmp2;
988 : : uint32 bitfield;
989 : 2907303 : RT_PTR_ALLOC *slot_simd = NULL;
990 : : #endif
991 : :
992 : : #if defined(USE_NO_SIMD) || defined(USE_ASSERT_CHECKING)
993 : 2907303 : RT_PTR_ALLOC *slot = NULL;
994 : :
995 [ + + ]: 17943364 : for (int i = 0; i < count; i++)
996 : : {
997 [ + + ]: 17775124 : if (node->chunks[i] == chunk)
998 : : {
999 : 2739063 : slot = &node->children[i];
1000 : 2739063 : break;
1001 : : }
1002 : : }
1003 : : #endif
1004 : :
1005 : : #ifndef USE_NO_SIMD
1006 : : /* replicate the search key */
1007 : 2907303 : spread_chunk = vector8_broadcast(chunk);
1008 : :
1009 : : /* compare to all 32 keys stored in the node */
1010 : 2907303 : vector8_load(&haystack1, &node->chunks[0]);
1011 : 2907303 : vector8_load(&haystack2, &node->chunks[sizeof(Vector8)]);
1012 : 2907303 : cmp1 = vector8_eq(spread_chunk, haystack1);
1013 : 2907303 : cmp2 = vector8_eq(spread_chunk, haystack2);
1014 : :
1015 : : /* convert comparison to a bitfield */
1016 : 2907303 : bitfield = vector8_highbit_mask(cmp1) | (vector8_highbit_mask(cmp2) << sizeof(Vector8));
1017 : :
1018 : : /* mask off invalid entries */
1019 : 2907303 : bitfield &= ((UINT64CONST(1) << count) - 1);
1020 : :
1021 : : /* convert bitfield to index by counting trailing zeros */
1022 [ + + ]: 2907303 : if (bitfield)
1023 : 2739063 : slot_simd = &node->children[pg_rightmost_one_pos32(bitfield)];
1024 : :
1025 [ - + ]: 2907303 : Assert(slot_simd == slot);
1026 : 2907303 : return slot_simd;
1027 : : #else
1028 : : return slot;
1029 : : #endif
1030 : : }
1031 : :
1032 : : /*
1033 : : * Search for the child pointer corresponding to "key" in the given node.
1034 : : *
1035 : : * Return child if the key is found, otherwise return NULL.
1036 : : */
1037 : : static inline RT_PTR_ALLOC *
1038 : 14030088 : RT_NODE_SEARCH(RT_NODE * node, uint8 chunk)
1039 : : {
1040 : : /* Make sure we already converted to local pointer */
1041 [ - + ]: 14030088 : Assert(node != NULL);
1042 : :
1043 [ + + + + : 14030088 : switch (node->kind)
- ]
1044 : : {
1045 : 6117039 : case RT_NODE_KIND_4:
1046 : : {
1047 : 6117039 : RT_NODE_4 *n4 = (RT_NODE_4 *) node;
1048 : :
1049 [ + + ]: 7690080 : for (int i = 0; i < n4->base.count; i++)
1050 : : {
1051 [ + + ]: 7101499 : if (n4->chunks[i] == chunk)
1052 : 5528458 : return &n4->children[i];
1053 : : }
1054 : 588581 : return NULL;
1055 : : }
1056 : 2907303 : case RT_NODE_KIND_16:
1057 : 2907303 : return RT_NODE_16_SEARCH_EQ((RT_NODE_16 *) node, chunk);
1058 : 710252 : case RT_NODE_KIND_48:
1059 : : {
1060 : 710252 : RT_NODE_48 *n48 = (RT_NODE_48 *) node;
1061 : 710252 : int slotpos = n48->slot_idxs[chunk];
1062 : :
1063 [ + + ]: 710252 : if (slotpos == RT_INVALID_SLOT_IDX)
1064 : 289723 : return NULL;
1065 : :
1066 : 420529 : return RT_NODE_48_GET_CHILD(n48, chunk);
1067 : : }
1068 : 4295494 : case RT_NODE_KIND_256:
1069 : : {
1070 : 4295494 : RT_NODE_256 *n256 = (RT_NODE_256 *) node;
1071 : :
1072 [ + + ]: 4295494 : if (!RT_NODE_256_IS_CHUNK_USED(n256, chunk))
1073 : 124009 : return NULL;
1074 : :
1075 : 4171485 : return RT_NODE_256_GET_CHILD(n256, chunk);
1076 : : }
38 john.naylor@postgres 1077 :UNC 0 : default:
1078 : 0 : pg_unreachable();
1079 : : }
1080 : : }
1081 : :
1082 : : /*
1083 : : * Search the given key in the radix tree. Return the pointer to the value if found,
1084 : : * otherwise return NULL.
1085 : : *
1086 : : * Since the function returns a pointer (to support variable-length values),
1087 : : * the caller is responsible for locking until it's finished with the value.
1088 : : */
1089 : : RT_SCOPE RT_VALUE_TYPE *
38 john.naylor@postgres 1090 :GNC 5539125 : RT_FIND(RT_RADIX_TREE * tree, uint64 key)
1091 : : {
1092 : : RT_CHILD_PTR node;
1093 : 5539125 : RT_PTR_ALLOC *slot = NULL;
1094 : : int shift;
1095 : :
1096 : : #ifdef RT_SHMEM
1097 [ - + ]: 324051 : Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
1098 : : #endif
1099 : :
1100 [ + + ]: 5539125 : if (key > tree->ctl->max_val)
1101 : 1433 : return NULL;
1102 : :
1103 [ - + ]: 5537692 : Assert(RT_PTR_ALLOC_IS_VALID(tree->ctl->root));
1104 : 5537692 : node.alloc = tree->ctl->root;
1105 : 5537692 : shift = tree->ctl->start_shift;
1106 : :
1107 : : /* Descend the tree */
1108 [ + + ]: 17671517 : while (shift >= 0)
1109 : : {
1110 : 13183904 : RT_PTR_SET_LOCAL(tree, &node);
1111 : 13183904 : slot = RT_NODE_SEARCH(node.local, RT_GET_KEY_CHUNK(key, shift));
1112 [ + + ]: 13183904 : if (slot == NULL)
1113 : 1050079 : return NULL;
1114 : :
1115 : 12133825 : node.alloc = *slot;
1116 : 12133825 : shift -= RT_SPAN;
1117 : : }
1118 : :
1119 [ + + ]: 4487613 : if (RT_CHILDPTR_IS_VALUE(*slot))
1120 : 232486 : return (RT_VALUE_TYPE *) slot;
1121 : : else
1122 : : {
1123 : 4255127 : RT_PTR_SET_LOCAL(tree, &node);
1124 : 4255127 : return (RT_VALUE_TYPE *) node.local;
1125 : : }
1126 : : }
1127 : :
1128 : : /***************** INSERTION *****************/
1129 : :
1130 : : #define RT_NODE_MUST_GROW(node) \
1131 : : ((node)->count == (node)->fanout)
1132 : :
1133 : : /*
1134 : : * Return index of the chunk and slot arrays for inserting into the node,
1135 : : * such that the arrays remain ordered.
1136 : : */
1137 : : static inline int
1138 : 10203 : RT_NODE_4_GET_INSERTPOS(RT_NODE_4 * node, uint8 chunk, int count)
1139 : : {
1140 : : int idx;
1141 : :
1142 [ + + ]: 23653 : for (idx = 0; idx < count; idx++)
1143 : : {
1144 [ + + ]: 19102 : if (node->chunks[idx] >= chunk)
1145 : 5652 : break;
1146 : : }
1147 : :
1148 : 10203 : return idx;
1149 : : }
1150 : :
1151 : : /*
1152 : : * Return index of the chunk and slot arrays for inserting into the node,
1153 : : * such that the arrays remain ordered.
1154 : : */
1155 : : static inline int
1156 : 60625 : RT_NODE_16_GET_INSERTPOS(RT_NODE_16 * node, uint8 chunk)
1157 : : {
1158 : 60625 : int count = node->base.count;
1159 : : #if defined(USE_NO_SIMD) || defined(USE_ASSERT_CHECKING)
1160 : : int index;
1161 : : #endif
1162 : :
1163 : : #ifndef USE_NO_SIMD
1164 : : Vector8 spread_chunk;
1165 : : Vector8 haystack1;
1166 : : Vector8 haystack2;
1167 : : Vector8 cmp1;
1168 : : Vector8 cmp2;
1169 : : Vector8 min1;
1170 : : Vector8 min2;
1171 : : uint32 bitfield;
1172 : : int index_simd;
1173 : : #endif
1174 : :
1175 : : /*
1176 : : * First compare the last element. There are two reasons to branch here:
1177 : : *
1178 : : * 1) A realistic pattern is inserting ordered keys. In that case,
1179 : : * non-SIMD platforms must do a linear search to the last chunk to find
1180 : : * the insert position. This will get slower as the node fills up.
1181 : : *
1182 : : * 2) On SIMD platforms, we must branch anyway to make sure we don't bit
1183 : : * scan an empty bitfield. Doing the branch here eliminates some work that
1184 : : * we might otherwise throw away.
1185 : : */
1186 [ - + ]: 60625 : Assert(count > 0);
1187 [ + + ]: 60625 : if (node->chunks[count - 1] < chunk)
1188 : 8375 : return count;
1189 : :
1190 : : #if defined(USE_NO_SIMD) || defined(USE_ASSERT_CHECKING)
1191 : :
1192 [ + - ]: 500189 : for (index = 0; index < count; index++)
1193 : : {
1194 [ + + ]: 500189 : if (node->chunks[index] > chunk)
1195 : 52250 : break;
1196 : : }
1197 : : #endif
1198 : :
1199 : : #ifndef USE_NO_SIMD
1200 : :
1201 : : /*
1202 : : * This is a bit more complicated than RT_NODE_16_SEARCH_EQ(), because no
1203 : : * unsigned uint8 comparison instruction exists, at least for SSE2. So we
1204 : : * need to play some trickery using vector8_min() to effectively get >=.
1205 : : * There'll never be any equal elements in current uses, but that's what
1206 : : * we get here...
1207 : : */
1208 : 52250 : spread_chunk = vector8_broadcast(chunk);
1209 : 52250 : vector8_load(&haystack1, &node->chunks[0]);
1210 : 52250 : vector8_load(&haystack2, &node->chunks[sizeof(Vector8)]);
1211 : 52250 : min1 = vector8_min(spread_chunk, haystack1);
1212 : 52250 : min2 = vector8_min(spread_chunk, haystack2);
1213 : 52250 : cmp1 = vector8_eq(spread_chunk, min1);
1214 : 52250 : cmp2 = vector8_eq(spread_chunk, min2);
1215 : 52250 : bitfield = vector8_highbit_mask(cmp1) | (vector8_highbit_mask(cmp2) << sizeof(Vector8));
1216 : :
1217 [ - + ]: 52250 : Assert((bitfield & ((UINT64CONST(1) << count) - 1)) != 0);
1218 : 52250 : index_simd = pg_rightmost_one_pos32(bitfield);
1219 : :
1220 [ - + ]: 52250 : Assert(index_simd == index);
1221 : 52250 : return index_simd;
1222 : : #else
1223 : : return index;
1224 : : #endif
1225 : : }
1226 : :
1227 : : /* Shift the elements right at "insertpos" by one */
1228 : : static inline void
1229 : 66256 : RT_SHIFT_ARRAYS_FOR_INSERT(uint8 *chunks, RT_PTR_ALLOC * children, int count, int insertpos)
1230 : : {
1231 : : /*
1232 : : * This is basically a memmove, but written in a simple loop for speed on
1233 : : * small inputs.
1234 : : */
1235 [ + + ]: 562418 : for (int i = count - 1; i >= insertpos; i--)
1236 : : {
1237 : : /* workaround for https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101481 */
1238 : : #ifdef __GNUC__
1239 : 496162 : __asm__("");
1240 : : #endif
1241 : 496162 : chunks[i + 1] = chunks[i];
1242 : 496162 : children[i + 1] = children[i];
1243 : : }
1244 : 66256 : }
1245 : :
1246 : : /*
1247 : : * Copy both chunk and slot arrays into the right
1248 : : * place. The caller is responsible for inserting the new element.
1249 : : */
1250 : : static inline void
1251 : 4572 : RT_COPY_ARRAYS_FOR_INSERT(uint8 *dst_chunks, RT_PTR_ALLOC * dst_children,
1252 : : uint8 *src_chunks, RT_PTR_ALLOC * src_children,
1253 : : int count, int insertpos)
1254 : : {
1255 [ + + ]: 49639 : for (int i = 0; i < count; i++)
1256 : : {
1257 : 45067 : int sourceidx = i;
1258 : :
1259 : : /* use a branch-free computation to skip the index of the new element */
1260 : 45067 : int destidx = i + (i >= insertpos);
1261 : :
1262 : 45067 : dst_chunks[destidx] = src_chunks[sourceidx];
1263 : 45067 : dst_children[destidx] = src_children[sourceidx];
1264 : : }
1265 : 4572 : }
1266 : :
1267 : : static inline RT_PTR_ALLOC *
1268 : 11539 : RT_ADD_CHILD_256(RT_RADIX_TREE * tree, RT_CHILD_PTR node, uint8 chunk)
1269 : : {
1270 : 11539 : RT_NODE_256 *n256 = (RT_NODE_256 *) node.local;
1271 : 11539 : int idx = RT_BM_IDX(chunk);
1272 : 11539 : int bitnum = RT_BM_BIT(chunk);
1273 : :
1274 : : /* Mark the slot used for "chunk" */
1275 : 11539 : n256->isset[idx] |= ((bitmapword) 1 << bitnum);
1276 : :
1277 : 11539 : n256->base.count++;
1278 : 11539 : RT_VERIFY_NODE((RT_NODE *) n256);
1279 : :
1280 : 11539 : return RT_NODE_256_GET_CHILD(n256, chunk);
1281 : : }
1282 : :
1283 : : static pg_noinline RT_PTR_ALLOC *
1284 : 86 : RT_GROW_NODE_48(RT_RADIX_TREE * tree, RT_PTR_ALLOC * parent_slot, RT_CHILD_PTR node,
1285 : : uint8 chunk)
1286 : : {
1287 : 86 : RT_NODE_48 *n48 = (RT_NODE_48 *) node.local;
1288 : : RT_CHILD_PTR newnode;
1289 : : RT_NODE_256 *new256;
1290 : 86 : int i = 0;
1291 : :
1292 : : /* initialize new node */
1293 : 86 : newnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_256, RT_CLASS_256);
1294 : 86 : new256 = (RT_NODE_256 *) newnode.local;
1295 : :
1296 : : /* copy over the entries */
1297 : 86 : RT_COPY_COMMON(newnode, node);
1298 [ + + ]: 430 : for (int word_num = 0; word_num < RT_BM_IDX(RT_NODE_MAX_SLOTS); word_num++)
1299 : : {
1300 : 344 : bitmapword bitmap = 0;
1301 : :
1302 : : /*
1303 : : * Bit manipulation is a surprisingly large portion of the overhead in
1304 : : * the naive implementation. Doing stores word-at-a-time removes a lot
1305 : : * of that overhead.
1306 : : */
1307 [ + + ]: 22360 : for (int bit = 0; bit < BITS_PER_BITMAPWORD; bit++)
1308 : : {
1309 : 22016 : uint8 offset = n48->slot_idxs[i];
1310 : :
1311 [ + + ]: 22016 : if (offset != RT_INVALID_SLOT_IDX)
1312 : : {
1313 : 5502 : bitmap |= ((bitmapword) 1 << bit);
1314 : 5502 : new256->children[i] = n48->children[offset];
1315 : : }
1316 : :
1317 : 22016 : i++;
1318 : : }
1319 : :
1320 : 344 : new256->isset[word_num] = bitmap;
1321 : : }
1322 : :
1323 : : /* free old node and update reference in parent */
1324 : 86 : *parent_slot = newnode.alloc;
1325 : 86 : RT_FREE_NODE(tree, node);
1326 : :
1327 : 86 : return RT_ADD_CHILD_256(tree, newnode, chunk);
1328 : : }
1329 : :
1330 : : static inline RT_PTR_ALLOC *
1331 : 26883 : RT_ADD_CHILD_48(RT_RADIX_TREE * tree, RT_CHILD_PTR node, uint8 chunk)
1332 : : {
1333 : 26883 : RT_NODE_48 *n48 = (RT_NODE_48 *) node.local;
1334 : : int insertpos;
1335 : 26883 : int idx = 0;
1336 : : bitmapword w,
1337 : : inverse;
1338 : :
1339 : : /* get the first word with at least one bit not set */
1340 [ + - ]: 26883 : for (int i = 0; i < RT_BM_IDX(RT_FANOUT_48_MAX); i++)
1341 : : {
1342 : 26883 : w = n48->isset[i];
1343 [ + - ]: 26883 : if (w < ~((bitmapword) 0))
1344 : : {
1345 : 26883 : idx = i;
1346 : 26883 : break;
1347 : : }
1348 : : }
1349 : :
1350 : : /* To get the first unset bit in w, get the first set bit in ~w */
1351 : 26883 : inverse = ~w;
1352 : 26883 : insertpos = idx * BITS_PER_BITMAPWORD;
1353 : 26883 : insertpos += bmw_rightmost_one_pos(inverse);
1354 [ - + ]: 26883 : Assert(insertpos < n48->base.fanout);
1355 : :
1356 : : /* mark the slot used by setting the rightmost zero bit */
1357 : 26883 : n48->isset[idx] |= w + 1;
1358 : :
1359 : : /* insert new chunk into place */
1360 : 26883 : n48->slot_idxs[chunk] = insertpos;
1361 : :
1362 : 26883 : n48->base.count++;
1363 : 26883 : RT_VERIFY_NODE((RT_NODE *) n48);
1364 : :
1365 : 26883 : return &n48->children[insertpos];
1366 : : }
1367 : :
1368 : : static pg_noinline RT_PTR_ALLOC *
1369 : 4380 : RT_GROW_NODE_16(RT_RADIX_TREE * tree, RT_PTR_ALLOC * parent_slot, RT_CHILD_PTR node,
1370 : : uint8 chunk)
1371 : : {
1372 : 4380 : RT_NODE_16 *n16 = (RT_NODE_16 *) node.local;
1373 : : int insertpos;
1374 : :
1375 [ + + ]: 4380 : if (n16->base.fanout < RT_FANOUT_16_HI)
1376 : : {
1377 : : RT_CHILD_PTR newnode;
1378 : : RT_NODE_16 *new16;
1379 : :
1380 [ - + ]: 2232 : Assert(n16->base.fanout == RT_FANOUT_16_LO);
1381 : :
1382 : : /* initialize new node */
1383 : 2232 : newnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_16, RT_CLASS_16_HI);
1384 : 2232 : new16 = (RT_NODE_16 *) newnode.local;
1385 : :
1386 : : /* copy over existing entries */
1387 : 2232 : RT_COPY_COMMON(newnode, node);
1388 [ - + ]: 2232 : Assert(n16->base.count == RT_FANOUT_16_LO);
1389 : 2232 : insertpos = RT_NODE_16_GET_INSERTPOS(n16, chunk);
1390 : 2232 : RT_COPY_ARRAYS_FOR_INSERT(new16->chunks, new16->children,
1391 : 2232 : n16->chunks, n16->children,
1392 : : RT_FANOUT_16_LO, insertpos);
1393 : :
1394 : : /* insert new chunk into place */
1395 : 2232 : new16->chunks[insertpos] = chunk;
1396 : :
1397 : 2232 : new16->base.count++;
1398 : 2232 : RT_VERIFY_NODE((RT_NODE *) new16);
1399 : :
1400 : : /* free old node and update references */
1401 : 2232 : RT_FREE_NODE(tree, node);
1402 : 2232 : *parent_slot = newnode.alloc;
1403 : :
1404 : 2232 : return &new16->children[insertpos];
1405 : : }
1406 : : else
1407 : : {
1408 : : RT_CHILD_PTR newnode;
1409 : : RT_NODE_48 *new48;
1410 : : int idx,
1411 : : bit;
1412 : :
1413 [ - + ]: 2148 : Assert(n16->base.fanout == RT_FANOUT_16_HI);
1414 : :
1415 : : /* initialize new node */
1416 : 2148 : newnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_48, RT_CLASS_48);
1417 : 2148 : new48 = (RT_NODE_48 *) newnode.local;
1418 : :
1419 : : /* copy over the entries */
1420 : 2148 : RT_COPY_COMMON(newnode, node);
1421 [ + + ]: 70884 : for (int i = 0; i < RT_FANOUT_16_HI; i++)
1422 : 68736 : new48->slot_idxs[n16->chunks[i]] = i;
1423 : 2148 : memcpy(&new48->children[0], &n16->children[0], RT_FANOUT_16_HI * sizeof(new48->children[0]));
1424 : :
1425 : : /*
1426 : : * Since we just copied a dense array, we can fill "isset" using a
1427 : : * single store, provided the length of that array is at most the
1428 : : * number of bits in a bitmapword.
1429 : : */
1430 : : Assert(RT_FANOUT_16_HI <= BITS_PER_BITMAPWORD);
1431 : 2148 : new48->isset[0] = (bitmapword) (((uint64) 1 << RT_FANOUT_16_HI) - 1);
1432 : :
1433 : : /* put the new child at the end of the copied entries */
1434 : 2148 : insertpos = RT_FANOUT_16_HI;
1435 : 2148 : idx = RT_BM_IDX(insertpos);
1436 : 2148 : bit = RT_BM_BIT(insertpos);
1437 : :
1438 : : /* mark the slot used */
1439 : 2148 : new48->isset[idx] |= ((bitmapword) 1 << bit);
1440 : :
1441 : : /* insert new chunk into place */
1442 : 2148 : new48->slot_idxs[chunk] = insertpos;
1443 : :
1444 : 2148 : new48->base.count++;
1445 : 2148 : RT_VERIFY_NODE((RT_NODE *) new48);
1446 : :
1447 : : /* free old node and update reference in parent */
1448 : 2148 : *parent_slot = newnode.alloc;
1449 : 2148 : RT_FREE_NODE(tree, node);
1450 : :
1451 : 2148 : return &new48->children[insertpos];
1452 : : }
1453 : : }
1454 : :
1455 : : static inline RT_PTR_ALLOC *
1456 : 58393 : RT_ADD_CHILD_16(RT_RADIX_TREE * tree, RT_CHILD_PTR node, uint8 chunk)
1457 : : {
1458 : 58393 : RT_NODE_16 *n16 = (RT_NODE_16 *) node.local;
1459 : 58393 : int insertpos = RT_NODE_16_GET_INSERTPOS(n16, chunk);
1460 : :
1461 : : /* shift chunks and children */
1462 : 58393 : RT_SHIFT_ARRAYS_FOR_INSERT(n16->chunks, n16->children,
1463 : 58393 : n16->base.count, insertpos);
1464 : :
1465 : : /* insert new chunk into place */
1466 : 58393 : n16->chunks[insertpos] = chunk;
1467 : :
1468 : 58393 : n16->base.count++;
1469 : 58393 : RT_VERIFY_NODE((RT_NODE *) n16);
1470 : :
1471 : 58393 : return &n16->children[insertpos];
1472 : : }
1473 : :
1474 : : static pg_noinline RT_PTR_ALLOC *
1475 : 2340 : RT_GROW_NODE_4(RT_RADIX_TREE * tree, RT_PTR_ALLOC * parent_slot, RT_CHILD_PTR node,
1476 : : uint8 chunk)
1477 : : {
1478 : 2340 : RT_NODE_4 *n4 = (RT_NODE_4 *) (node.local);
1479 : : RT_CHILD_PTR newnode;
1480 : : RT_NODE_16 *new16;
1481 : : int insertpos;
1482 : :
1483 : : /* initialize new node */
1484 : 2340 : newnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_16, RT_CLASS_16_LO);
1485 : 2340 : new16 = (RT_NODE_16 *) newnode.local;
1486 : :
1487 : : /* copy over existing entries */
1488 : 2340 : RT_COPY_COMMON(newnode, node);
1489 [ - + ]: 2340 : Assert(n4->base.count == RT_FANOUT_4);
1490 : 2340 : insertpos = RT_NODE_4_GET_INSERTPOS(n4, chunk, RT_FANOUT_4);
1491 : 2340 : RT_COPY_ARRAYS_FOR_INSERT(new16->chunks, new16->children,
1492 : 2340 : n4->chunks, n4->children,
1493 : : RT_FANOUT_4, insertpos);
1494 : :
1495 : : /* insert new chunk into place */
1496 : 2340 : new16->chunks[insertpos] = chunk;
1497 : :
1498 : 2340 : new16->base.count++;
1499 : 2340 : RT_VERIFY_NODE((RT_NODE *) new16);
1500 : :
1501 : : /* free old node and update reference in parent */
1502 : 2340 : *parent_slot = newnode.alloc;
1503 : 2340 : RT_FREE_NODE(tree, node);
1504 : :
1505 : 2340 : return &new16->children[insertpos];
1506 : : }
1507 : :
1508 : : static inline RT_PTR_ALLOC *
1509 : 7863 : RT_ADD_CHILD_4(RT_RADIX_TREE * tree, RT_CHILD_PTR node, uint8 chunk)
1510 : : {
1511 : 7863 : RT_NODE_4 *n4 = (RT_NODE_4 *) (node.local);
1512 : 7863 : int count = n4->base.count;
1513 : 7863 : int insertpos = RT_NODE_4_GET_INSERTPOS(n4, chunk, count);
1514 : :
1515 : : /* shift chunks and children */
1516 : 7863 : RT_SHIFT_ARRAYS_FOR_INSERT(n4->chunks, n4->children,
1517 : : count, insertpos);
1518 : :
1519 : : /* insert new chunk into place */
1520 : 7863 : n4->chunks[insertpos] = chunk;
1521 : :
1522 : 7863 : n4->base.count++;
1523 : 7863 : RT_VERIFY_NODE((RT_NODE *) n4);
1524 : :
1525 : 7863 : return &n4->children[insertpos];
1526 : : }
1527 : :
1528 : : /*
1529 : : * Reserve slot in "node"'s child array. The caller will populate it
1530 : : * with the actual child pointer.
1531 : : *
1532 : : * "parent_slot" is the address of the parent's child pointer to "node".
1533 : : * If the node we're inserting into needs to grow, we update the parent's
1534 : : * child pointer with the pointer to the new larger node.
1535 : : */
1536 : : static inline RT_PTR_ALLOC *
1537 : 111398 : RT_NODE_INSERT(RT_RADIX_TREE * tree, RT_PTR_ALLOC * parent_slot, RT_CHILD_PTR node,
1538 : : uint8 chunk)
1539 : : {
1540 : 111398 : RT_NODE *n = node.local;
1541 : :
1542 [ + + + + : 111398 : switch (n->kind)
- ]
1543 : : {
1544 : 10203 : case RT_NODE_KIND_4:
1545 : : {
1546 [ + + ]: 10203 : if (unlikely(RT_NODE_MUST_GROW(n)))
1547 : 2340 : return RT_GROW_NODE_4(tree, parent_slot, node, chunk);
1548 : :
1549 : 7863 : return RT_ADD_CHILD_4(tree, node, chunk);
1550 : : }
1551 : 62773 : case RT_NODE_KIND_16:
1552 : : {
1553 [ + + ]: 62773 : if (unlikely(RT_NODE_MUST_GROW(n)))
1554 : 4380 : return RT_GROW_NODE_16(tree, parent_slot, node, chunk);
1555 : :
1556 : 58393 : return RT_ADD_CHILD_16(tree, node, chunk);
1557 : : }
1558 : 26969 : case RT_NODE_KIND_48:
1559 : : {
1560 [ + + ]: 26969 : if (unlikely(RT_NODE_MUST_GROW(n)))
1561 : 86 : return RT_GROW_NODE_48(tree, parent_slot, node, chunk);
1562 : :
1563 : 26883 : return RT_ADD_CHILD_48(tree, node, chunk);
1564 : : }
1565 : 11453 : case RT_NODE_KIND_256:
1566 : 11453 : return RT_ADD_CHILD_256(tree, node, chunk);
38 john.naylor@postgres 1567 :UNC 0 : default:
1568 : 0 : pg_unreachable();
1569 : : }
1570 : : }
1571 : :
1572 : : /*
1573 : : * The radix tree doesn't have sufficient height. Put new node(s) on top,
1574 : : * and move the old node below it.
1575 : : */
1576 : : static pg_noinline void
38 john.naylor@postgres 1577 :GNC 25 : RT_EXTEND_UP(RT_RADIX_TREE * tree, uint64 key)
1578 : : {
1579 : 25 : int target_shift = RT_KEY_GET_SHIFT(key);
1580 : 25 : int shift = tree->ctl->start_shift;
1581 : :
1582 [ - + ]: 25 : Assert(shift < target_shift);
1583 : :
1584 : : /* Grow tree upwards until start shift can accomodate the key */
1585 [ + + ]: 80 : while (shift < target_shift)
1586 : : {
1587 : : RT_CHILD_PTR node;
1588 : : RT_NODE_4 *n4;
1589 : :
1590 : 55 : node = RT_ALLOC_NODE(tree, RT_NODE_KIND_4, RT_CLASS_4);
1591 : 55 : n4 = (RT_NODE_4 *) node.local;
1592 : 55 : n4->base.count = 1;
1593 : 55 : n4->chunks[0] = 0;
1594 : 55 : n4->children[0] = tree->ctl->root;
1595 : :
1596 : : /* Update the root */
1597 : 55 : tree->ctl->root = node.alloc;
1598 : :
1599 : 55 : shift += RT_SPAN;
1600 : : }
1601 : :
1602 : 25 : tree->ctl->max_val = RT_SHIFT_GET_MAX_VAL(target_shift);
1603 : 25 : tree->ctl->start_shift = target_shift;
1604 : 25 : }
1605 : :
1606 : : /*
1607 : : * Insert a chain of nodes until we reach the lowest level,
1608 : : * and return the address of a slot to be filled further up
1609 : : * the call stack.
1610 : : */
1611 : : static pg_noinline RT_PTR_ALLOC *
1612 : 4977 : RT_EXTEND_DOWN(RT_RADIX_TREE * tree, RT_PTR_ALLOC * parent_slot, uint64 key, int shift)
1613 : : {
1614 : : RT_CHILD_PTR node,
1615 : : child;
1616 : : RT_NODE_4 *n4;
1617 : :
1618 : : /*
1619 : : * The child pointer of the first node in the chain goes in the
1620 : : * caller-provided slot.
1621 : : */
1622 : 4977 : child = RT_ALLOC_NODE(tree, RT_NODE_KIND_4, RT_CLASS_4);
1623 : 4977 : *parent_slot = child.alloc;
1624 : :
1625 : 4977 : node = child;
1626 : 4977 : shift -= RT_SPAN;
1627 : :
1628 [ + + ]: 15721 : while (shift > 0)
1629 : : {
1630 : 10744 : child = RT_ALLOC_NODE(tree, RT_NODE_KIND_4, RT_CLASS_4);
1631 : :
1632 : : /* We open-code the insertion ourselves, for speed. */
1633 : 10744 : n4 = (RT_NODE_4 *) node.local;
1634 : 10744 : n4->base.count = 1;
1635 : 10744 : n4->chunks[0] = RT_GET_KEY_CHUNK(key, shift);
1636 : 10744 : n4->children[0] = child.alloc;
1637 : :
1638 : 10744 : node = child;
1639 : 10744 : shift -= RT_SPAN;
1640 : : }
20 msawada@postgresql.o 1641 [ - + ]: 4977 : Assert(shift == 0);
1642 : :
1643 : : /* Reserve slot for the value. */
38 john.naylor@postgres 1644 : 4977 : n4 = (RT_NODE_4 *) node.local;
20 msawada@postgresql.o 1645 : 4977 : n4->chunks[0] = RT_GET_KEY_CHUNK(key, 0);
38 john.naylor@postgres 1646 : 4977 : n4->base.count = 1;
1647 : :
1648 : 4977 : return &n4->children[0];
1649 : : }
1650 : :
1651 : : /*
1652 : : * Workhorse for RT_SET
1653 : : *
1654 : : * "parent_slot" is the address of the child pointer we just followed,
1655 : : * in the parent's array of children, needed if inserting into the
1656 : : * current node causes it to grow.
1657 : : */
1658 : : static RT_PTR_ALLOC *
1659 : 431048 : RT_GET_SLOT_RECURSIVE(RT_RADIX_TREE * tree, RT_PTR_ALLOC * parent_slot, uint64 key, int shift, bool *found)
1660 : : {
1661 : : RT_PTR_ALLOC *slot;
1662 : : RT_CHILD_PTR node;
1663 : 431048 : uint8 chunk = RT_GET_KEY_CHUNK(key, shift);
1664 : :
1665 : 431048 : node.alloc = *parent_slot;
1666 : 431048 : RT_PTR_SET_LOCAL(tree, &node);
1667 : 431048 : slot = RT_NODE_SEARCH(node.local, chunk);
1668 : :
1669 [ + + ]: 431048 : if (slot == NULL)
1670 : : {
1671 : 111398 : *found = false;
1672 : :
1673 : : /* reserve slot for the caller to populate */
1674 : :
1675 : 111398 : slot = RT_NODE_INSERT(tree, parent_slot, node, chunk);
1676 : :
1677 [ + + ]: 111398 : if (shift == 0)
1678 : 106434 : return slot;
1679 : : else
1680 : 4964 : return RT_EXTEND_DOWN(tree, slot, key, shift);
1681 : : }
1682 : : else
1683 : : {
1684 [ + + ]: 319650 : if (shift == 0)
1685 : : {
1686 : 11253 : *found = true;
1687 : 11253 : return slot;
1688 : : }
1689 : : else
1690 : 308397 : return RT_GET_SLOT_RECURSIVE(tree, slot, key, shift - RT_SPAN, found);
1691 : : }
1692 : : }
1693 : :
1694 : : /*
1695 : : * Set key to value that value_p points to. If the entry already exists, we
1696 : : * update its value and return true. Returns false if entry doesn't yet exist.
1697 : : *
1698 : : * Taking a lock in exclusive mode is the caller's responsibility.
1699 : : */
1700 : : RT_SCOPE bool
1701 : 122664 : RT_SET(RT_RADIX_TREE * tree, uint64 key, RT_VALUE_TYPE * value_p)
1702 : : {
1703 : : bool found;
1704 : : RT_PTR_ALLOC *slot;
1705 : 122664 : size_t value_sz = RT_GET_VALUE_SIZE(value_p);
1706 : :
1707 : : #ifdef RT_SHMEM
1708 [ - + ]: 249 : Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
1709 : : #endif
1710 : :
1711 [ - + ]: 122664 : Assert(RT_PTR_ALLOC_IS_VALID(tree->ctl->root));
1712 : :
1713 : : /* Extend the tree if necessary */
1714 [ + + ]: 122664 : if (unlikely(key > tree->ctl->max_val))
1715 : : {
1716 [ + + ]: 38 : if (tree->ctl->num_keys == 0)
1717 : : {
1718 : : RT_CHILD_PTR node;
1719 : : RT_NODE_4 *n4;
1720 : 13 : int start_shift = RT_KEY_GET_SHIFT(key);
1721 : :
1722 : : /*
1723 : : * With an empty root node, we don't extend the tree upwards,
1724 : : * since that would result in orphan empty nodes. Instead we open
1725 : : * code inserting into the root node and extend downward from
1726 : : * there.
1727 : : */
1728 : 13 : node.alloc = tree->ctl->root;
1729 : 13 : RT_PTR_SET_LOCAL(tree, &node);
1730 : 13 : n4 = (RT_NODE_4 *) node.local;
1731 : 13 : n4->base.count = 1;
1732 : 13 : n4->chunks[0] = RT_GET_KEY_CHUNK(key, start_shift);
1733 : :
1734 : 13 : slot = RT_EXTEND_DOWN(tree, &n4->children[0], key, start_shift);
1735 : 13 : found = false;
1736 : 13 : tree->ctl->start_shift = start_shift;
1737 : 13 : tree->ctl->max_val = RT_SHIFT_GET_MAX_VAL(start_shift);
1738 : 13 : goto have_slot;
1739 : : }
1740 : : else
1741 : 25 : RT_EXTEND_UP(tree, key);
1742 : : }
1743 : :
1744 : 122651 : slot = RT_GET_SLOT_RECURSIVE(tree, &tree->ctl->root,
1745 : 122651 : key, tree->ctl->start_shift, &found);
1746 : :
1747 : 122664 : have_slot:
1748 [ - + ]: 122664 : Assert(slot != NULL);
1749 : :
1750 [ + + ]: 122664 : if (RT_VALUE_IS_EMBEDDABLE(value_p))
1751 : : {
1752 : : /* store value directly in child pointer slot */
1753 : 108344 : memcpy(slot, value_p, value_sz);
1754 : :
1755 : : #ifdef RT_RUNTIME_EMBEDDABLE_VALUE
1756 : : /* tag child pointer */
1757 : : #ifdef RT_SHMEM
6 1758 : 2 : *slot |= 1;
1759 : : #else
1760 : 1808 : *((uintptr_t *) slot) |= 1;
1761 : : #endif
1762 : : #endif
1763 : : }
1764 : : else
1765 : : {
1766 : : RT_CHILD_PTR leaf;
1767 : :
38 1768 [ - + ]: 14320 : if (found)
1769 : : {
38 john.naylor@postgres 1770 [ # # ]:UNC 0 : Assert(RT_PTR_ALLOC_IS_VALID(*slot));
1771 : 0 : leaf.alloc = *slot;
1772 : 0 : RT_PTR_SET_LOCAL(tree, &leaf);
1773 : :
1774 [ # # ]: 0 : if (RT_GET_VALUE_SIZE((RT_VALUE_TYPE *) leaf.local) != value_sz)
1775 : : {
1776 : : /*
1777 : : * different sizes, so first free the existing leaf before
1778 : : * allocating a new one
1779 : : */
1780 : 0 : RT_FREE_LEAF(tree, *slot);
1781 : 0 : leaf = RT_ALLOC_LEAF(tree, value_sz);
1782 : 0 : *slot = leaf.alloc;
1783 : : }
1784 : : }
1785 : : else
1786 : : {
1787 : : /* allocate new leaf and store it in the child array */
38 john.naylor@postgres 1788 :GNC 14320 : leaf = RT_ALLOC_LEAF(tree, value_sz);
1789 : 14320 : *slot = leaf.alloc;
1790 : : }
1791 : :
1792 : 14320 : memcpy(leaf.local, value_p, value_sz);
1793 : : }
1794 : :
1795 : : /* Update the statistics */
1796 [ + + ]: 122664 : if (!found)
1797 : 111411 : tree->ctl->num_keys++;
1798 : :
1799 : 122664 : return found;
1800 : : }
1801 : :
1802 : : /***************** SETUP / TEARDOWN *****************/
1803 : :
1804 : : /*
1805 : : * Create the radix tree in the given memory context and return it.
1806 : : *
1807 : : * All local memory required for a radix tree is allocated in the given
1808 : : * memory context and its children. Note that RT_FREE() will delete all
1809 : : * allocated space within the given memory context, so the dsa_area should
1810 : : * be created in a different context.
1811 : : */
1812 : : RT_SCOPE RT_RADIX_TREE *
1813 : : #ifdef RT_SHMEM
1814 : 14 : RT_CREATE(MemoryContext ctx, dsa_area *dsa, int tranche_id)
1815 : : #else
1816 : 84259 : RT_CREATE(MemoryContext ctx)
1817 : : #endif
1818 : : {
1819 : : RT_RADIX_TREE *tree;
1820 : : MemoryContext old_ctx;
1821 : : RT_CHILD_PTR rootnode;
1822 : : #ifdef RT_SHMEM
1823 : : dsa_pointer dp;
1824 : : #endif
1825 : :
1826 : 84273 : old_ctx = MemoryContextSwitchTo(ctx);
1827 : :
1828 : 84273 : tree = (RT_RADIX_TREE *) palloc0(sizeof(RT_RADIX_TREE));
1829 : 84273 : tree->context = ctx;
1830 : :
1831 : : /*
1832 : : * Separate context for iteration in case the tree context doesn't support
1833 : : * pfree
1834 : : */
7 1835 : 84273 : tree->iter_context = AllocSetContextCreate(ctx,
1836 : : RT_STR(RT_PREFIX) "radix_tree iter context",
1837 : : ALLOCSET_SMALL_SIZES);
1838 : :
1839 : : #ifdef RT_SHMEM
38 1840 : 14 : tree->dsa = dsa;
1841 : 14 : dp = dsa_allocate0(dsa, sizeof(RT_RADIX_TREE_CONTROL));
1842 : 14 : tree->ctl = (RT_RADIX_TREE_CONTROL *) dsa_get_address(dsa, dp);
1843 : 14 : tree->ctl->handle = dp;
1844 : 14 : tree->ctl->magic = RT_RADIX_TREE_MAGIC;
1845 : 14 : LWLockInitialize(&tree->ctl->lock, tranche_id);
1846 : : #else
1847 : 84259 : tree->ctl = (RT_RADIX_TREE_CONTROL *) palloc0(sizeof(RT_RADIX_TREE_CONTROL));
1848 : :
1849 : : /* Create a slab context for each size class */
1850 [ + + ]: 505554 : for (int i = 0; i < RT_NUM_SIZE_CLASSES; i++)
1851 : : {
1852 : 421295 : RT_SIZE_CLASS_ELEM size_class = RT_SIZE_CLASS_INFO[i];
1853 [ + + ]: 421295 : size_t inner_blocksize = RT_SLAB_BLOCK_SIZE(size_class.allocsize);
1854 : :
1855 : 421295 : tree->node_slabs[i] = SlabContextCreate(ctx,
1856 : : size_class.name,
1857 : : inner_blocksize,
1858 : : size_class.allocsize);
1859 : : }
1860 : :
1861 : : /* By default we use the passed context for leaves. */
1862 : 84259 : tree->leaf_context = tree->context;
1863 : :
1864 : : #ifndef RT_VARLEN_VALUE_SIZE
1865 : :
1866 : : /*
1867 : : * For leaves storing fixed-length values, we use a slab context to avoid
1868 : : * the possibility of space wastage by power-of-2 rounding up.
1869 : : */
1870 : : if (sizeof(RT_VALUE_TYPE) > sizeof(RT_PTR_ALLOC))
1871 : : tree->leaf_context = SlabContextCreate(ctx,
1872 : : RT_STR(RT_PREFIX) "radix_tree leaf contex",
1873 : : RT_SLAB_BLOCK_SIZE(sizeof(RT_VALUE_TYPE)),
1874 : : sizeof(RT_VALUE_TYPE));
1875 : : #endif /* !RT_VARLEN_VALUE_SIZE */
1876 : : #endif /* RT_SHMEM */
1877 : :
1878 : : /* add root node now so that RT_SET can assume it exists */
1879 : 84273 : rootnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_4, RT_CLASS_4);
1880 : 84273 : tree->ctl->root = rootnode.alloc;
1881 : 84273 : tree->ctl->start_shift = 0;
1882 : 84273 : tree->ctl->max_val = RT_SHIFT_GET_MAX_VAL(0);
1883 : :
1884 : 84273 : MemoryContextSwitchTo(old_ctx);
1885 : :
1886 : 84273 : return tree;
1887 : : }
1888 : :
1889 : : #ifdef RT_SHMEM
1890 : : RT_SCOPE RT_RADIX_TREE *
1891 : 16 : RT_ATTACH(dsa_area *dsa, RT_HANDLE handle)
1892 : : {
1893 : : RT_RADIX_TREE *tree;
1894 : : dsa_pointer control;
1895 : :
1896 : 16 : tree = (RT_RADIX_TREE *) palloc0(sizeof(RT_RADIX_TREE));
1897 : :
1898 : : /* Find the control object in shared memory */
1899 : 16 : control = handle;
1900 : :
1901 : 16 : tree->dsa = dsa;
1902 : 16 : tree->ctl = (RT_RADIX_TREE_CONTROL *) dsa_get_address(dsa, control);
1903 [ - + ]: 16 : Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
1904 : :
1905 : 16 : return tree;
1906 : : }
1907 : :
1908 : : RT_SCOPE void
1909 : 16 : RT_DETACH(RT_RADIX_TREE * tree)
1910 : : {
1911 [ - + ]: 16 : Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
1912 : 16 : pfree(tree);
1913 : 16 : }
1914 : :
1915 : : RT_SCOPE RT_HANDLE
1916 : 13 : RT_GET_HANDLE(RT_RADIX_TREE * tree)
1917 : : {
1918 [ - + ]: 13 : Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
1919 : 13 : return tree->ctl->handle;
1920 : : }
1921 : :
1922 : : RT_SCOPE void
1923 : 103 : RT_LOCK_EXCLUSIVE(RT_RADIX_TREE * tree)
1924 : : {
1925 [ - + ]: 103 : Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
1926 : 103 : LWLockAcquire(&tree->ctl->lock, LW_EXCLUSIVE);
1927 : 103 : }
1928 : :
1929 : : RT_SCOPE void
1930 : 210842 : RT_LOCK_SHARE(RT_RADIX_TREE * tree)
1931 : : {
1932 [ - + ]: 210842 : Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
1933 : 210842 : LWLockAcquire(&tree->ctl->lock, LW_SHARED);
1934 : 210842 : }
1935 : :
1936 : : RT_SCOPE void
1937 : 210945 : RT_UNLOCK(RT_RADIX_TREE * tree)
1938 : : {
1939 [ - + ]: 210945 : Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
1940 : 210945 : LWLockRelease(&tree->ctl->lock);
1941 : 210945 : }
1942 : :
1943 : : /*
1944 : : * Recursively free all nodes allocated in the DSA area.
1945 : : */
1946 : : static void
1947 : 17 : RT_FREE_RECURSE(RT_RADIX_TREE * tree, RT_PTR_ALLOC ptr, int shift)
1948 : : {
1949 : : RT_CHILD_PTR node;
1950 : :
1951 : 17 : check_stack_depth();
1952 : :
1953 : 17 : node.alloc = ptr;
1954 : 17 : RT_PTR_SET_LOCAL(tree, &node);
1955 : :
1956 [ + + + + : 17 : switch (node.local->kind)
- ]
1957 : : {
1958 : 11 : case RT_NODE_KIND_4:
1959 : : {
1960 : 11 : RT_NODE_4 *n4 = (RT_NODE_4 *) node.local;
1961 : :
1962 [ + + ]: 16 : for (int i = 0; i < n4->base.count; i++)
1963 : : {
1964 : 5 : RT_PTR_ALLOC child = n4->children[i];
1965 : :
1966 [ + + ]: 5 : if (shift > 0)
1967 : 3 : RT_FREE_RECURSE(tree, child, shift - RT_SPAN);
1968 [ - + ]: 2 : else if (!RT_CHILDPTR_IS_VALUE(child))
38 john.naylor@postgres 1969 :UNC 0 : dsa_free(tree->dsa, child);
1970 : : }
1971 : :
38 john.naylor@postgres 1972 :GNC 11 : break;
1973 : : }
1974 : 2 : case RT_NODE_KIND_16:
1975 : : {
1976 : 2 : RT_NODE_16 *n16 = (RT_NODE_16 *) node.local;
1977 : :
1978 [ + + ]: 37 : for (int i = 0; i < n16->base.count; i++)
1979 : : {
1980 : 35 : RT_PTR_ALLOC child = n16->children[i];
1981 : :
1982 [ - + ]: 35 : if (shift > 0)
38 john.naylor@postgres 1983 :UNC 0 : RT_FREE_RECURSE(tree, child, shift - RT_SPAN);
38 john.naylor@postgres 1984 [ + - ]:GNC 35 : else if (!RT_CHILDPTR_IS_VALUE(child))
1985 : 35 : dsa_free(tree->dsa, child);
1986 : : }
1987 : :
1988 : 2 : break;
1989 : : }
1990 : 3 : case RT_NODE_KIND_48:
1991 : : {
1992 : 3 : RT_NODE_48 *n48 = (RT_NODE_48 *) node.local;
1993 : :
1994 [ + + ]: 771 : for (int i = 0; i < RT_NODE_MAX_SLOTS; i++)
1995 : : {
1996 : : RT_PTR_ALLOC child;
1997 : :
1998 [ + + ]: 768 : if (!RT_NODE_48_IS_CHUNK_USED(n48, i))
1999 : 633 : continue;
2000 : :
2001 : 135 : child = *RT_NODE_48_GET_CHILD(n48, i);
2002 : :
2003 [ - + ]: 135 : if (shift > 0)
38 john.naylor@postgres 2004 :UNC 0 : RT_FREE_RECURSE(tree, child, shift - RT_SPAN);
38 john.naylor@postgres 2005 [ + - ]:GNC 135 : else if (!RT_CHILDPTR_IS_VALUE(child))
2006 : 135 : dsa_free(tree->dsa, child);
2007 : : }
2008 : :
2009 : 3 : break;
2010 : : }
2011 : 1 : case RT_NODE_KIND_256:
2012 : : {
2013 : 1 : RT_NODE_256 *n256 = (RT_NODE_256 *) node.local;
2014 : :
2015 [ + + ]: 257 : for (int i = 0; i < RT_NODE_MAX_SLOTS; i++)
2016 : : {
2017 : : RT_PTR_ALLOC child;
2018 : :
2019 [ + + ]: 256 : if (!RT_NODE_256_IS_CHUNK_USED(n256, i))
2020 : 179 : continue;
2021 : :
2022 : 77 : child = *RT_NODE_256_GET_CHILD(n256, i);
2023 : :
2024 [ - + ]: 77 : if (shift > 0)
38 john.naylor@postgres 2025 :UNC 0 : RT_FREE_RECURSE(tree, child, shift - RT_SPAN);
38 john.naylor@postgres 2026 [ + - ]:GNC 77 : else if (!RT_CHILDPTR_IS_VALUE(child))
2027 : 77 : dsa_free(tree->dsa, child);
2028 : : }
2029 : :
2030 : 1 : break;
2031 : : }
2032 : : }
2033 : :
2034 : : /* Free the inner node */
2035 : 17 : dsa_free(tree->dsa, ptr);
2036 : 17 : }
2037 : : #endif
2038 : :
2039 : : /*
2040 : : * Free the radix tree, including all nodes and leaves.
2041 : : */
2042 : : RT_SCOPE void
2043 : 583 : RT_FREE(RT_RADIX_TREE * tree)
2044 : : {
2045 : : #ifdef RT_SHMEM
2046 [ - + ]: 14 : Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
2047 : :
2048 : : /* Free all memory used for radix tree nodes */
2049 [ - + ]: 14 : Assert(RT_PTR_ALLOC_IS_VALID(tree->ctl->root));
2050 : 14 : RT_FREE_RECURSE(tree, tree->ctl->root, tree->ctl->start_shift);
2051 : :
2052 : : /*
2053 : : * Vandalize the control block to help catch programming error where other
2054 : : * backends access the memory formerly occupied by this radix tree.
2055 : : */
2056 : 14 : tree->ctl->magic = 0;
2057 : 14 : dsa_free(tree->dsa, tree->ctl->handle);
2058 : : #endif
2059 : :
2060 : : /*
2061 : : * Free all space allocated within the tree's context and delete all child
2062 : : * contexts such as those used for nodes.
2063 : : */
2064 : 583 : MemoryContextReset(tree->context);
2065 : 583 : }
2066 : :
2067 : : /***************** ITERATION *****************/
2068 : :
2069 : : /*
2070 : : * Create and return the iterator for the given radix tree.
2071 : : *
2072 : : * Taking a lock in shared mode during the iteration is the caller's
2073 : : * responsibility.
2074 : : */
2075 : : RT_SCOPE RT_ITER *
2076 : 556 : RT_BEGIN_ITERATE(RT_RADIX_TREE * tree)
2077 : : {
2078 : : RT_ITER *iter;
2079 : : RT_CHILD_PTR root;
2080 : :
7 2081 : 556 : iter = (RT_ITER *) MemoryContextAllocZero(tree->iter_context,
2082 : : sizeof(RT_ITER));
38 2083 : 556 : iter->tree = tree;
2084 : :
2085 [ - + ]: 556 : Assert(RT_PTR_ALLOC_IS_VALID(tree->ctl->root));
2086 : 556 : root.alloc = iter->tree->ctl->root;
2087 : 556 : RT_PTR_SET_LOCAL(tree, &root);
2088 : :
2089 : 556 : iter->top_level = iter->tree->ctl->start_shift / RT_SPAN;
2090 : :
2091 : : /* Set the root to start */
2092 : 556 : iter->cur_level = iter->top_level;
2093 : 556 : iter->node_iters[iter->cur_level].node = root;
2094 : 556 : iter->node_iters[iter->cur_level].idx = 0;
2095 : :
2096 : 556 : return iter;
2097 : : }
2098 : :
2099 : : /*
2100 : : * Scan the inner node and return the next child pointer if one exists, otherwise
2101 : : * return NULL.
2102 : : */
2103 : : static inline RT_PTR_ALLOC *
2104 : 127231 : RT_NODE_ITERATE_NEXT(RT_ITER * iter, int level)
2105 : : {
2106 : 127231 : uint8 key_chunk = 0;
2107 : : RT_NODE_ITER *node_iter;
2108 : : RT_CHILD_PTR node;
2109 : 127231 : RT_PTR_ALLOC *slot = NULL;
2110 : :
2111 : : #ifdef RT_SHMEM
2112 [ - + ]: 260 : Assert(iter->tree->ctl->magic == RT_RADIX_TREE_MAGIC);
2113 : : #endif
2114 : :
2115 : 127231 : node_iter = &(iter->node_iters[level]);
2116 : 127231 : node = node_iter->node;
2117 : :
2118 [ - + ]: 127231 : Assert(node.local != NULL);
2119 : :
2120 [ + + + + : 127231 : switch ((node.local)->kind)
- ]
2121 : : {
2122 : 16553 : case RT_NODE_KIND_4:
2123 : : {
2124 : 16553 : RT_NODE_4 *n4 = (RT_NODE_4 *) (node.local);
2125 : :
2126 [ + + ]: 16553 : if (node_iter->idx >= n4->base.count)
2127 : 8104 : return NULL;
2128 : :
2129 : 8449 : slot = &n4->children[node_iter->idx];
2130 : 8449 : key_chunk = n4->chunks[node_iter->idx];
2131 : 8449 : node_iter->idx++;
2132 : 8449 : break;
2133 : : }
2134 : 3405 : case RT_NODE_KIND_16:
2135 : : {
2136 : 3405 : RT_NODE_16 *n16 = (RT_NODE_16 *) (node.local);
2137 : :
2138 [ + + ]: 3405 : if (node_iter->idx >= n16->base.count)
2139 : 171 : return NULL;
2140 : :
2141 : 3234 : slot = &n16->children[node_iter->idx];
2142 : 3234 : key_chunk = n16->chunks[node_iter->idx];
2143 : 3234 : node_iter->idx++;
2144 : 3234 : break;
2145 : : }
2146 : 93960 : case RT_NODE_KIND_48:
2147 : : {
2148 : 93960 : RT_NODE_48 *n48 = (RT_NODE_48 *) (node.local);
2149 : : int chunk;
2150 : :
2151 [ + + ]: 528739 : for (chunk = node_iter->idx; chunk < RT_NODE_MAX_SLOTS; chunk++)
2152 : : {
2153 [ + + ]: 526684 : if (RT_NODE_48_IS_CHUNK_USED(n48, chunk))
2154 : 91905 : break;
2155 : : }
2156 : :
2157 [ + + ]: 93960 : if (chunk >= RT_NODE_MAX_SLOTS)
2158 : 2055 : return NULL;
2159 : :
2160 : 91905 : slot = RT_NODE_48_GET_CHILD(n48, chunk);
2161 : :
2162 : 91905 : key_chunk = chunk;
2163 : 91905 : node_iter->idx = chunk + 1;
2164 : 91905 : break;
2165 : : }
2166 : 13313 : case RT_NODE_KIND_256:
2167 : : {
2168 : 13313 : RT_NODE_256 *n256 = (RT_NODE_256 *) (node.local);
2169 : : int chunk;
2170 : :
2171 [ + + ]: 19268 : for (chunk = node_iter->idx; chunk < RT_NODE_MAX_SLOTS; chunk++)
2172 : : {
2173 [ + + ]: 19200 : if (RT_NODE_256_IS_CHUNK_USED(n256, chunk))
2174 : 13245 : break;
2175 : : }
2176 : :
2177 [ + + ]: 13313 : if (chunk >= RT_NODE_MAX_SLOTS)
2178 : 68 : return NULL;
2179 : :
2180 : 13245 : slot = RT_NODE_256_GET_CHILD(n256, chunk);
2181 : :
2182 : 13245 : key_chunk = chunk;
2183 : 13245 : node_iter->idx = chunk + 1;
2184 : 13245 : break;
2185 : : }
2186 : : }
2187 : :
2188 : : /* Update the key */
2189 : 116833 : iter->key &= ~(((uint64) RT_CHUNK_MASK) << (level * RT_SPAN));
2190 : 116833 : iter->key |= (((uint64) key_chunk) << (level * RT_SPAN));
2191 : :
2192 : 116833 : return slot;
2193 : : }
2194 : :
2195 : : /*
2196 : : * Return pointer to value and set key_p as long as there is a key. Otherwise
2197 : : * return NULL.
2198 : : */
2199 : : RT_SCOPE RT_VALUE_TYPE *
2200 : 107402 : RT_ITERATE_NEXT(RT_ITER * iter, uint64 *key_p)
2201 : : {
2202 : 107402 : RT_PTR_ALLOC *slot = NULL;
2203 : :
2204 [ + + ]: 127756 : while (iter->cur_level <= iter->top_level)
2205 : : {
2206 : : RT_CHILD_PTR node;
2207 : :
2208 : 127231 : slot = RT_NODE_ITERATE_NEXT(iter, iter->cur_level);
2209 : :
2210 [ + + + + ]: 127231 : if (iter->cur_level == 0 && slot != NULL)
2211 : : {
2212 : : /* Found a value at the leaf node */
2213 : 106877 : *key_p = iter->key;
2214 : 106877 : node.alloc = *slot;
2215 : :
2216 [ + + ]: 106877 : if (RT_CHILDPTR_IS_VALUE(*slot))
2217 : 106877 : return (RT_VALUE_TYPE *) slot;
2218 : : else
2219 : : {
2220 : 11977 : RT_PTR_SET_LOCAL(iter->tree, &node);
2221 : 11977 : return (RT_VALUE_TYPE *) node.local;
2222 : : }
2223 : : }
2224 : :
2225 [ + + ]: 20354 : if (slot != NULL)
2226 : : {
2227 : : /* Found the child slot, move down the tree */
2228 : 9956 : node.alloc = *slot;
2229 : 9956 : RT_PTR_SET_LOCAL(iter->tree, &node);
2230 : :
2231 : 9956 : iter->cur_level--;
2232 : 9956 : iter->node_iters[iter->cur_level].node = node;
2233 : 9956 : iter->node_iters[iter->cur_level].idx = 0;
2234 : : }
2235 : : else
2236 : : {
2237 : : /* Not found the child slot, move up the tree */
2238 : 10398 : iter->cur_level++;
2239 : : }
2240 : : }
2241 : :
2242 : : /* We've visited all nodes, so the iteration finished */
2243 : 525 : return NULL;
2244 : : }
2245 : :
2246 : : /*
2247 : : * Terminate the iteration. The caller is responsible for releasing any locks.
2248 : : */
2249 : : RT_SCOPE void
2250 : 556 : RT_END_ITERATE(RT_ITER * iter)
2251 : : {
2252 : 556 : pfree(iter);
2253 : 556 : }
2254 : :
2255 : : /***************** DELETION *****************/
2256 : :
2257 : : #ifdef RT_USE_DELETE
2258 : :
2259 : : /* Delete the element at "deletepos" */
2260 : : static inline void
2261 : 22102 : RT_SHIFT_ARRAYS_AND_DELETE(uint8 *chunks, RT_PTR_ALLOC * children, int count, int deletepos)
2262 : : {
2263 : : /*
2264 : : * This is basically a memmove, but written in a simple loop for speed on
2265 : : * small inputs.
2266 : : */
2267 [ + + ]: 101791 : for (int i = deletepos; i < count - 1; i++)
2268 : : {
2269 : : /* workaround for https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101481 */
2270 : : #ifdef __GNUC__
2271 : 79689 : __asm__("");
2272 : : #endif
2273 : 79689 : chunks[i] = chunks[i + 1];
2274 : 79689 : children[i] = children[i + 1];
2275 : : }
2276 : 22102 : }
2277 : :
2278 : : /*
2279 : : * Copy both chunk and slot arrays into the right
2280 : : * place. The element at "deletepos" is deleted by skipping it.
2281 : : */
2282 : : static inline void
2283 : 2081 : RT_COPY_ARRAYS_AND_DELETE(uint8 *dst_chunks, RT_PTR_ALLOC * dst_children,
2284 : : uint8 *src_chunks, RT_PTR_ALLOC * src_children,
2285 : : int count, int deletepos)
2286 : : {
2287 [ + + ]: 8324 : for (int i = 0; i < count - 1; i++)
2288 : : {
2289 : : /*
2290 : : * use a branch-free computation to skip the index of the deleted
2291 : : * element
2292 : : */
2293 : 6243 : int sourceidx = i + (i >= deletepos);
2294 : 6243 : int destidx = i;
2295 : :
2296 : 6243 : dst_chunks[destidx] = src_chunks[sourceidx];
2297 : 6243 : dst_children[destidx] = src_children[sourceidx];
2298 : : }
2299 : 2081 : }
2300 : :
2301 : : /*
2302 : : * Note: While all node-growing functions are called to perform an insertion
2303 : : * when no more space is available, shrinking is not a hard-and-fast requirement.
2304 : : * When shrinking nodes, we generally wait until the count is about 3/4* of
2305 : : * the next lower node's fanout. This prevents ping-ponging between different
2306 : : * node sizes.
2307 : : *
2308 : : * Some shrinking functions delete first and then shrink, either because we
2309 : : * must or because it's fast and simple that way. Sometimes it's faster to
2310 : : * delete while shrinking.
2311 : : */
2312 : :
2313 : : /*
2314 : : * Move contents of a node256 to a node48. Any deletion should have happened
2315 : : * in the caller.
2316 : : */
2317 : : static void pg_noinline
2318 : 16 : RT_SHRINK_NODE_256(RT_RADIX_TREE * tree, RT_PTR_ALLOC * parent_slot, RT_CHILD_PTR node, uint8 chunk)
2319 : : {
2320 : 16 : RT_NODE_256 *n256 = (RT_NODE_256 *) node.local;
2321 : : RT_CHILD_PTR newnode;
2322 : : RT_NODE_48 *new48;
2323 : 16 : int slot_idx = 0;
2324 : :
2325 : : /* initialize new node */
2326 : 16 : newnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_48, RT_CLASS_48);
2327 : 16 : new48 = (RT_NODE_48 *) newnode.local;
2328 : :
2329 : : /* copy over the entries */
2330 : 16 : RT_COPY_COMMON(newnode, node);
2331 [ + + ]: 4112 : for (int i = 0; i < RT_NODE_MAX_SLOTS; i++)
2332 : : {
2333 [ + + ]: 4096 : if (RT_NODE_256_IS_CHUNK_USED(n256, i))
2334 : : {
2335 : 768 : new48->slot_idxs[i] = slot_idx;
2336 : 768 : new48->children[slot_idx] = n256->children[i];
2337 : 768 : slot_idx++;
2338 : : }
2339 : : }
2340 : :
2341 : : /*
2342 : : * Since we just copied a dense array, we can fill "isset" using a single
2343 : : * store, provided the length of that array is at most the number of bits
2344 : : * in a bitmapword.
2345 : : */
2346 [ - + ]: 16 : Assert(n256->base.count <= BITS_PER_BITMAPWORD);
2347 : 16 : new48->isset[0] = (bitmapword) (((uint64) 1 << n256->base.count) - 1);
2348 : :
2349 : : /* free old node and update reference in parent */
2350 : 16 : *parent_slot = newnode.alloc;
2351 : 16 : RT_FREE_NODE(tree, node);
2352 : 16 : }
2353 : :
2354 : : static inline void
2355 : 4483 : RT_REMOVE_CHILD_256(RT_RADIX_TREE * tree, RT_PTR_ALLOC * parent_slot, RT_CHILD_PTR node, uint8 chunk)
2356 : : {
2357 : : int shrink_threshold;
2358 : 4483 : RT_NODE_256 *n256 = (RT_NODE_256 *) node.local;
2359 : 4483 : int idx = RT_BM_IDX(chunk);
2360 : 4483 : int bitnum = RT_BM_BIT(chunk);
2361 : :
2362 : : /* Mark the slot free for "chunk" */
2363 : 4483 : n256->isset[idx] &= ~((bitmapword) 1 << bitnum);
2364 : :
2365 : 4483 : n256->base.count--;
2366 : :
2367 : : /*
2368 : : * A full node256 will have a count of zero because of overflow, so we
2369 : : * delete first before checking the shrink threshold.
2370 : : */
2371 [ - + ]: 4483 : Assert(n256->base.count > 0);
2372 : :
2373 : : /* This simplifies RT_SHRINK_NODE_256() */
2374 : 4483 : shrink_threshold = BITS_PER_BITMAPWORD;
2375 : 4483 : shrink_threshold = Min(RT_FANOUT_48 / 4 * 3, shrink_threshold);
2376 : :
2377 [ + + ]: 4483 : if (n256->base.count <= shrink_threshold)
2378 : 16 : RT_SHRINK_NODE_256(tree, parent_slot, node, chunk);
2379 : 4483 : }
2380 : :
2381 : : /*
2382 : : * Move contents of a node48 to a node16. Any deletion should have happened
2383 : : * in the caller.
2384 : : */
2385 : : static void pg_noinline
2386 : 2021 : RT_SHRINK_NODE_48(RT_RADIX_TREE * tree, RT_PTR_ALLOC * parent_slot, RT_CHILD_PTR node, uint8 chunk)
2387 : : {
2388 : 2021 : RT_NODE_48 *n48 = (RT_NODE_48 *) (node.local);
2389 : : RT_CHILD_PTR newnode;
2390 : : RT_NODE_16 *new16;
2391 : 2021 : int destidx = 0;
2392 : :
2393 : : /*
2394 : : * Initialize new node. For now we skip the larger node16 size class for
2395 : : * simplicity.
2396 : : */
2397 : 2021 : newnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_16, RT_CLASS_16_LO);
2398 : 2021 : new16 = (RT_NODE_16 *) newnode.local;
2399 : :
2400 : : /* copy over all existing entries */
2401 : 2021 : RT_COPY_COMMON(newnode, node);
2402 [ + + ]: 519397 : for (int chunk = 0; chunk < RT_NODE_MAX_SLOTS; chunk++)
2403 : : {
2404 [ + + ]: 517376 : if (n48->slot_idxs[chunk] != RT_INVALID_SLOT_IDX)
2405 : : {
2406 : 24252 : new16->chunks[destidx] = chunk;
2407 : 24252 : new16->children[destidx] = n48->children[n48->slot_idxs[chunk]];
2408 : 24252 : destidx++;
2409 : : }
2410 : : }
2411 : :
2412 [ - + ]: 2021 : Assert(destidx < new16->base.fanout);
2413 : :
2414 : 2021 : RT_VERIFY_NODE((RT_NODE *) new16);
2415 : :
2416 : : /* free old node and update reference in parent */
2417 : 2021 : *parent_slot = newnode.alloc;
2418 : 2021 : RT_FREE_NODE(tree, node);
2419 : 2021 : }
2420 : :
2421 : : static inline void
2422 : 66584 : RT_REMOVE_CHILD_48(RT_RADIX_TREE * tree, RT_PTR_ALLOC * parent_slot, RT_CHILD_PTR node, uint8 chunk)
2423 : : {
2424 : 66584 : RT_NODE_48 *n48 = (RT_NODE_48 *) node.local;
2425 : 66584 : int deletepos = n48->slot_idxs[chunk];
2426 : :
2427 : : /* For now we skip the larger node16 size class for simplicity */
2428 : 66584 : int shrink_threshold = RT_FANOUT_16_LO / 4 * 3;
2429 : : int idx;
2430 : : int bitnum;
2431 : :
2432 [ - + ]: 66584 : Assert(deletepos != RT_INVALID_SLOT_IDX);
2433 : :
2434 : 66584 : idx = RT_BM_IDX(deletepos);
2435 : 66584 : bitnum = RT_BM_BIT(deletepos);
2436 : 66584 : n48->isset[idx] &= ~((bitmapword) 1 << bitnum);
2437 : 66584 : n48->slot_idxs[chunk] = RT_INVALID_SLOT_IDX;
2438 : :
2439 : 66584 : n48->base.count--;
2440 : :
2441 : : /*
2442 : : * To keep shrinking simple, do it after deleting, which is fast for
2443 : : * node48 anyway.
2444 : : */
2445 [ + + ]: 66584 : if (n48->base.count <= shrink_threshold)
2446 : 2021 : RT_SHRINK_NODE_48(tree, parent_slot, node, chunk);
2447 : 66584 : }
2448 : :
2449 : : /*
2450 : : * Move contents of a node16 to a node4, and delete the one at "deletepos".
2451 : : * By deleting as we move, we can avoid memmove operations in the new
2452 : : * node.
2453 : : */
2454 : : static void pg_noinline
2455 : 2081 : RT_SHRINK_NODE_16(RT_RADIX_TREE * tree, RT_PTR_ALLOC * parent_slot, RT_CHILD_PTR node, uint8 deletepos)
2456 : : {
2457 : 2081 : RT_NODE_16 *n16 = (RT_NODE_16 *) (node.local);
2458 : : RT_CHILD_PTR newnode;
2459 : : RT_NODE_4 *new4;
2460 : :
2461 : : /* initialize new node */
2462 : 2081 : newnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_4, RT_CLASS_4);
2463 : 2081 : new4 = (RT_NODE_4 *) newnode.local;
2464 : :
2465 : : /* copy over existing entries, except for the one at "deletepos" */
2466 : 2081 : RT_COPY_COMMON(newnode, node);
2467 : 2081 : RT_COPY_ARRAYS_AND_DELETE(new4->chunks, new4->children,
2468 : 2081 : n16->chunks, n16->children,
2469 : 2081 : n16->base.count, deletepos);
2470 : :
2471 : 2081 : new4->base.count--;
2472 : 2081 : RT_VERIFY_NODE((RT_NODE *) new4);
2473 : :
2474 : : /* free old node and update reference in parent */
2475 : 2081 : *parent_slot = newnode.alloc;
2476 : 2081 : RT_FREE_NODE(tree, node);
2477 : 2081 : }
2478 : :
2479 : : static inline void
2480 : 20003 : RT_REMOVE_CHILD_16(RT_RADIX_TREE * tree, RT_PTR_ALLOC * parent_slot, RT_CHILD_PTR node, uint8 chunk, RT_PTR_ALLOC * slot)
2481 : : {
2482 : 20003 : RT_NODE_16 *n16 = (RT_NODE_16 *) node.local;
2483 : 20003 : int deletepos = slot - n16->children;
2484 : :
2485 : : /*
2486 : : * When shrinking to node4, 4 is hard-coded. After shrinking, the new node
2487 : : * will end up with 3 elements and 3 is the largest count where linear
2488 : : * search is faster than SIMD, at least on x86-64.
2489 : : */
2490 [ + + ]: 20003 : if (n16->base.count <= 4)
2491 : : {
2492 : 2081 : RT_SHRINK_NODE_16(tree, parent_slot, node, deletepos);
2493 : 2081 : return;
2494 : : }
2495 : :
2496 [ - + ]: 17922 : Assert(deletepos >= 0);
2497 [ - + ]: 17922 : Assert(n16->chunks[deletepos] == chunk);
2498 : :
2499 : 17922 : RT_SHIFT_ARRAYS_AND_DELETE(n16->chunks, n16->children,
2500 : 17922 : n16->base.count, deletepos);
2501 : 17922 : n16->base.count--;
2502 : : }
2503 : :
2504 : : static inline void
2505 : 19931 : RT_REMOVE_CHILD_4(RT_RADIX_TREE * tree, RT_PTR_ALLOC * parent_slot, RT_CHILD_PTR node, uint8 chunk, RT_PTR_ALLOC * slot)
2506 : : {
2507 : 19931 : RT_NODE_4 *n4 = (RT_NODE_4 *) node.local;
2508 : :
2509 [ + + ]: 19931 : if (n4->base.count == 1)
2510 : : {
2511 [ - + ]: 15751 : Assert(n4->chunks[0] == chunk);
2512 : :
2513 : : /*
2514 : : * If we're deleting the last entry from the root child node don't
2515 : : * free it, but mark both the tree and the root child node empty. That
2516 : : * way, RT_SET can assume it exists.
2517 : : */
2518 [ + + ]: 15751 : if (parent_slot == &tree->ctl->root)
2519 : : {
2520 : 31 : n4->base.count = 0;
2521 : 31 : tree->ctl->start_shift = 0;
2522 : 31 : tree->ctl->max_val = RT_SHIFT_GET_MAX_VAL(0);
2523 : : }
2524 : : else
2525 : : {
2526 : : /*
2527 : : * Deleting last entry, so just free the entire node.
2528 : : * RT_DELETE_RECURSIVE has already freed the value and lower-level
2529 : : * children.
2530 : : */
2531 : 15720 : RT_FREE_NODE(tree, node);
2532 : :
2533 : : /*
2534 : : * Also null out the parent's slot -- this tells the next higher
2535 : : * level to delete its child pointer
2536 : : */
2537 : 15720 : *parent_slot = RT_INVALID_PTR_ALLOC;
2538 : : }
2539 : : }
2540 : : else
2541 : : {
16 dgustafsson@postgres 2542 : 4180 : int deletepos = slot - n4->children;
2543 : :
38 john.naylor@postgres 2544 [ - + ]: 4180 : Assert(deletepos >= 0);
2545 [ - + ]: 4180 : Assert(n4->chunks[deletepos] == chunk);
2546 : :
2547 : 4180 : RT_SHIFT_ARRAYS_AND_DELETE(n4->chunks, n4->children,
2548 : 4180 : n4->base.count, deletepos);
2549 : :
2550 : 4180 : n4->base.count--;
2551 : : }
2552 : 19931 : }
2553 : :
2554 : : /*
2555 : : * Search for the child pointer corresponding to "key" in the given node.
2556 : : *
2557 : : * Delete the node and return true if the key is found, otherwise return false.
2558 : : */
2559 : : static inline void
2560 : 111001 : RT_NODE_DELETE(RT_RADIX_TREE * tree, RT_PTR_ALLOC * parent_slot, RT_CHILD_PTR node, uint8 chunk, RT_PTR_ALLOC * slot)
2561 : : {
2562 [ + + + + : 111001 : switch ((node.local)->kind)
- ]
2563 : : {
2564 : 19931 : case RT_NODE_KIND_4:
2565 : : {
2566 : 19931 : RT_REMOVE_CHILD_4(tree, parent_slot, node, chunk, slot);
2567 : 19931 : return;
2568 : : }
2569 : 20003 : case RT_NODE_KIND_16:
2570 : : {
2571 : 20003 : RT_REMOVE_CHILD_16(tree, parent_slot, node, chunk, slot);
2572 : 20003 : return;
2573 : : }
2574 : 66584 : case RT_NODE_KIND_48:
2575 : : {
2576 : 66584 : RT_REMOVE_CHILD_48(tree, parent_slot, node, chunk);
2577 : 66584 : return;
2578 : : }
2579 : 4483 : case RT_NODE_KIND_256:
2580 : : {
2581 : 4483 : RT_REMOVE_CHILD_256(tree, parent_slot, node, chunk);
2582 : 4483 : return;
2583 : : }
38 john.naylor@postgres 2584 :UNC 0 : default:
2585 : 0 : pg_unreachable();
2586 : : }
2587 : : }
2588 : :
2589 : : /* workhorse for RT_DELETE */
2590 : : static bool
38 john.naylor@postgres 2591 :GNC 415136 : RT_DELETE_RECURSIVE(RT_RADIX_TREE * tree, RT_PTR_ALLOC * parent_slot, uint64 key, int shift)
2592 : : {
2593 : : RT_PTR_ALLOC *slot;
2594 : : RT_CHILD_PTR node;
2595 : 415136 : uint8 chunk = RT_GET_KEY_CHUNK(key, shift);
2596 : :
2597 : 415136 : node.alloc = *parent_slot;
2598 : 415136 : RT_PTR_SET_LOCAL(tree, &node);
2599 : 415136 : slot = RT_NODE_SEARCH(node.local, chunk);
2600 : :
2601 [ + + ]: 415136 : if (slot == NULL)
2602 : 9076 : return false;
2603 : :
2604 [ + + ]: 406060 : if (shift == 0)
2605 : : {
2606 [ - + ]: 95281 : if (!RT_CHILDPTR_IS_VALUE(*slot))
38 john.naylor@postgres 2607 :UNC 0 : RT_FREE_LEAF(tree, *slot);
2608 : :
38 john.naylor@postgres 2609 :GNC 95281 : RT_NODE_DELETE(tree, parent_slot, node, chunk, slot);
2610 : 95281 : return true;
2611 : : }
2612 : : else
2613 : : {
2614 : : bool deleted;
2615 : :
2616 : 310779 : deleted = RT_DELETE_RECURSIVE(tree, slot, key, shift - RT_SPAN);
2617 : :
2618 : : /* Child node was freed, so delete its slot now */
2619 [ + + ]: 310779 : if (*slot == RT_INVALID_PTR_ALLOC)
2620 : : {
2621 [ - + ]: 15720 : Assert(deleted);
2622 : 15720 : RT_NODE_DELETE(tree, parent_slot, node, chunk, slot);
2623 : : }
2624 : :
2625 : 310779 : return deleted;
2626 : : }
2627 : : }
2628 : :
2629 : : /*
2630 : : * Delete the given key from the radix tree. If the key is found delete it
2631 : : * and return true, otherwise do nothing and return false.
2632 : : *
2633 : : * Taking a lock in exclusive mode is the caller's responsibility.
2634 : : */
2635 : : RT_SCOPE bool
2636 : 104357 : RT_DELETE(RT_RADIX_TREE * tree, uint64 key)
2637 : : {
2638 : : bool deleted;
2639 : :
2640 : : #ifdef RT_SHMEM
2641 : : Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
2642 : : #endif
2643 : :
2644 [ - + ]: 104357 : if (key > tree->ctl->max_val)
38 john.naylor@postgres 2645 :UNC 0 : return false;
2646 : :
38 john.naylor@postgres 2647 [ - + ]:GNC 104357 : Assert(RT_PTR_ALLOC_IS_VALID(tree->ctl->root));
2648 : 104357 : deleted = RT_DELETE_RECURSIVE(tree, &tree->ctl->root,
2649 : 104357 : key, tree->ctl->start_shift);
2650 : :
2651 : : /* Found the key to delete. Update the statistics */
2652 [ + + ]: 104357 : if (deleted)
2653 : : {
2654 : 95281 : tree->ctl->num_keys--;
2655 [ - + ]: 95281 : Assert(tree->ctl->num_keys >= 0);
2656 : : }
2657 : :
2658 : 104357 : return deleted;
2659 : : }
2660 : :
2661 : : #endif /* USE_RT_DELETE */
2662 : :
2663 : : /***************** UTILITY FUNCTIONS *****************/
2664 : :
2665 : : /*
2666 : : * Return the statistics of the amount of memory used by the radix tree.
2667 : : *
2668 : : * Since dsa_get_total_size() does appropriate locking, the caller doesn't
2669 : : * need to take a lock.
2670 : : */
2671 : : RT_SCOPE uint64
2672 : 342604 : RT_MEMORY_USAGE(RT_RADIX_TREE * tree)
2673 : : {
2674 : 342604 : size_t total = 0;
2675 : :
2676 : : #ifdef RT_SHMEM
2677 [ - + ]: 378 : Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
2678 : 378 : total = dsa_get_total_size(tree->dsa);
2679 : : #else
2680 : 342226 : total = MemoryContextMemAllocated(tree->context, true);
2681 : : #endif
2682 : :
2683 : 342604 : return total;
2684 : : }
2685 : :
2686 : : /*
2687 : : * Perform some sanity checks on the given node.
2688 : : */
2689 : : static void
2690 : 115500 : RT_VERIFY_NODE(RT_NODE * node)
2691 : : {
2692 : : #ifdef USE_ASSERT_CHECKING
2693 : :
2694 [ + + + + : 115500 : switch (node->kind)
- ]
2695 : : {
2696 : 9944 : case RT_NODE_KIND_4:
2697 : : {
2698 : 9944 : RT_NODE_4 *n4 = (RT_NODE_4 *) node;
2699 : :
2700 : : /* RT_DUMP_NODE(node); */
2701 : :
2702 [ + + ]: 28534 : for (int i = 1; i < n4->base.count; i++)
2703 [ - + ]: 18590 : Assert(n4->chunks[i - 1] < n4->chunks[i]);
2704 : :
2705 : 9944 : break;
2706 : : }
2707 : 64986 : case RT_NODE_KIND_16:
2708 : : {
2709 : 64986 : RT_NODE_16 *n16 = (RT_NODE_16 *) node;
2710 : :
2711 : : /* RT_DUMP_NODE(node); */
2712 : :
2713 [ + + ]: 1181463 : for (int i = 1; i < n16->base.count; i++)
2714 [ - + ]: 1116477 : Assert(n16->chunks[i - 1] < n16->chunks[i]);
2715 : :
2716 : 64986 : break;
2717 : : }
2718 : 29031 : case RT_NODE_KIND_48:
2719 : : {
2720 : 29031 : RT_NODE_48 *n48 = (RT_NODE_48 *) node;
2721 : 29031 : int cnt = 0;
2722 : :
2723 : : /* RT_DUMP_NODE(node); */
2724 : :
2725 [ + + ]: 7460967 : for (int i = 0; i < RT_NODE_MAX_SLOTS; i++)
2726 : : {
2727 : 7431936 : uint8 slot = n48->slot_idxs[i];
2728 : 7431936 : int idx = RT_BM_IDX(slot);
2729 : 7431936 : int bitnum = RT_BM_BIT(slot);
2730 : :
2731 [ + + ]: 7431936 : if (!RT_NODE_48_IS_CHUNK_USED(n48, i))
2732 : 6237436 : continue;
2733 : :
2734 : : /* Check if the corresponding slot is used */
2735 [ - + ]: 1194500 : Assert(slot < node->fanout);
2736 [ - + ]: 1194500 : Assert((n48->isset[idx] & ((bitmapword) 1 << bitnum)) != 0);
2737 : :
2738 : 1194500 : cnt++;
2739 : : }
2740 : :
2741 [ - + ]: 29031 : Assert(n48->base.count == cnt);
2742 : :
2743 : 29031 : break;
2744 : : }
2745 : 11539 : case RT_NODE_KIND_256:
2746 : : {
2747 : 11539 : RT_NODE_256 *n256 = (RT_NODE_256 *) node;
2748 : 11539 : int cnt = 0;
2749 : :
2750 : : /* RT_DUMP_NODE(node); */
2751 : :
2752 [ + + ]: 57695 : for (int i = 0; i < RT_BM_IDX(RT_NODE_MAX_SLOTS); i++)
2753 : 46156 : cnt += bmw_popcount(n256->isset[i]);
2754 : :
2755 : : /*
2756 : : * Check if the number of used chunk matches, accounting for
2757 : : * overflow
2758 : : */
2759 [ + + ]: 11539 : if (cnt == RT_FANOUT_256)
2760 [ - + ]: 1566 : Assert(n256->base.count == 0);
2761 : : else
2762 [ - + ]: 9973 : Assert(n256->base.count == cnt);
2763 : :
2764 : 11539 : break;
2765 : : }
2766 : : }
2767 : : #endif
2768 : 115500 : }
2769 : :
2770 : : /***************** DEBUG FUNCTIONS *****************/
2771 : :
2772 : : #ifdef RT_DEBUG
2773 : :
2774 : : /*
2775 : : * Print out tree stats, some of which are only collected in debugging builds.
2776 : : */
2777 : : RT_SCOPE void
2778 : 61 : RT_STATS(RT_RADIX_TREE * tree)
2779 : : {
2780 : 61 : fprintf(stderr, "max_val = " UINT64_FORMAT "\n", tree->ctl->max_val);
2781 : 61 : fprintf(stderr, "num_keys = %lld\n", (long long) tree->ctl->num_keys);
2782 : :
2783 : : #ifdef RT_SHMEM
2784 : : fprintf(stderr, "handle = " DSA_POINTER_FORMAT "\n", tree->ctl->handle);
2785 : : #endif
2786 : :
2787 : 61 : fprintf(stderr, "height = %d", tree->ctl->start_shift / RT_SPAN);
2788 : :
2789 [ + + ]: 366 : for (int i = 0; i < RT_NUM_SIZE_CLASSES; i++)
2790 : : {
2791 : 305 : RT_SIZE_CLASS_ELEM size_class = RT_SIZE_CLASS_INFO[i];
2792 : :
2793 : 305 : fprintf(stderr, ", n%d = %lld", size_class.fanout, (long long) tree->ctl->num_nodes[i]);
2794 : : }
2795 : :
2796 : 61 : fprintf(stderr, ", leaves = %lld", (long long) tree->ctl->num_leaves);
2797 : :
2798 : 61 : fprintf(stderr, "\n");
2799 : 61 : }
2800 : :
2801 : : /*
2802 : : * Print out debugging information about the given node.
2803 : : */
2804 : : static void
2805 : : pg_attribute_unused()
38 john.naylor@postgres 2806 :UNC 0 : RT_DUMP_NODE(RT_NODE * node)
2807 : : {
2808 : : #ifdef RT_SHMEM
2809 : : #define RT_CHILD_PTR_FORMAT DSA_POINTER_FORMAT
2810 : : #else
2811 : : #define RT_CHILD_PTR_FORMAT "%p"
2812 : : #endif
2813 : :
2814 : 0 : fprintf(stderr, "kind %d, fanout %d, count %u\n",
2815 [ # # ]: 0 : (node->kind == RT_NODE_KIND_4) ? 4 :
2816 [ # # ]: 0 : (node->kind == RT_NODE_KIND_16) ? 16 :
2817 [ # # ]: 0 : (node->kind == RT_NODE_KIND_48) ? 48 : 256,
2818 [ # # ]: 0 : node->fanout == 0 ? 256 : node->fanout,
2819 [ # # ]: 0 : node->count == 0 ? 256 : node->count);
2820 : :
2821 [ # # # # : 0 : switch (node->kind)
# ]
2822 : : {
2823 : 0 : case RT_NODE_KIND_4:
2824 : : {
2825 : 0 : RT_NODE_4 *n4 = (RT_NODE_4 *) node;
2826 : :
2827 : 0 : fprintf(stderr, "chunks and slots:\n");
2828 [ # # ]: 0 : for (int i = 0; i < n4->base.count; i++)
2829 : : {
2830 : 0 : fprintf(stderr, " [%d] chunk %x slot " RT_CHILD_PTR_FORMAT "\n",
2831 : 0 : i, n4->chunks[i], n4->children[i]);
2832 : : }
2833 : :
2834 : 0 : break;
2835 : : }
2836 : 0 : case RT_NODE_KIND_16:
2837 : : {
2838 : 0 : RT_NODE_16 *n16 = (RT_NODE_16 *) node;
2839 : :
2840 : 0 : fprintf(stderr, "chunks and slots:\n");
2841 [ # # ]: 0 : for (int i = 0; i < n16->base.count; i++)
2842 : : {
2843 : 0 : fprintf(stderr, " [%d] chunk %x slot " RT_CHILD_PTR_FORMAT "\n",
2844 : 0 : i, n16->chunks[i], n16->children[i]);
2845 : : }
2846 : 0 : break;
2847 : : }
2848 : 0 : case RT_NODE_KIND_48:
2849 : : {
2850 : 0 : RT_NODE_48 *n48 = (RT_NODE_48 *) node;
2851 : 0 : char *sep = "";
2852 : :
2853 : 0 : fprintf(stderr, "slot_idxs: \n");
2854 [ # # ]: 0 : for (int chunk = 0; chunk < RT_NODE_MAX_SLOTS; chunk++)
2855 : : {
2856 [ # # ]: 0 : if (!RT_NODE_48_IS_CHUNK_USED(n48, chunk))
2857 : 0 : continue;
2858 : :
2859 : 0 : fprintf(stderr, " idx[%d] = %d\n",
2860 : 0 : chunk, n48->slot_idxs[chunk]);
2861 : : }
2862 : :
2863 : 0 : fprintf(stderr, "isset-bitmap: ");
2864 [ # # ]: 0 : for (int i = 0; i < (RT_FANOUT_48_MAX / BITS_PER_BYTE); i++)
2865 : : {
2866 : 0 : fprintf(stderr, "%s%x", sep, ((uint8 *) n48->isset)[i]);
2867 : 0 : sep = " ";
2868 : : }
2869 : 0 : fprintf(stderr, "\n");
2870 : :
2871 : 0 : fprintf(stderr, "chunks and slots:\n");
2872 [ # # ]: 0 : for (int chunk = 0; chunk < RT_NODE_MAX_SLOTS; chunk++)
2873 : : {
2874 [ # # ]: 0 : if (!RT_NODE_48_IS_CHUNK_USED(n48, chunk))
2875 : 0 : continue;
2876 : :
2877 : 0 : fprintf(stderr, " chunk %x slot " RT_CHILD_PTR_FORMAT "\n",
2878 : : chunk,
2879 : 0 : *RT_NODE_48_GET_CHILD(n48, chunk));
2880 : : }
2881 : 0 : break;
2882 : : }
2883 : 0 : case RT_NODE_KIND_256:
2884 : : {
2885 : 0 : RT_NODE_256 *n256 = (RT_NODE_256 *) node;
2886 : 0 : char *sep = "";
2887 : :
2888 : 0 : fprintf(stderr, "isset-bitmap: ");
2889 [ # # ]: 0 : for (int i = 0; i < (RT_FANOUT_256 / BITS_PER_BYTE); i++)
2890 : : {
2891 : 0 : fprintf(stderr, "%s%x", sep, ((uint8 *) n256->isset)[i]);
2892 : 0 : sep = " ";
2893 : : }
2894 : 0 : fprintf(stderr, "\n");
2895 : :
2896 : 0 : fprintf(stderr, "chunks and slots:\n");
2897 [ # # ]: 0 : for (int chunk = 0; chunk < RT_NODE_MAX_SLOTS; chunk++)
2898 : : {
2899 [ # # ]: 0 : if (!RT_NODE_256_IS_CHUNK_USED(n256, chunk))
2900 : 0 : continue;
2901 : :
2902 : 0 : fprintf(stderr, " chunk %x slot " RT_CHILD_PTR_FORMAT "\n",
2903 : : chunk,
2904 : 0 : *RT_NODE_256_GET_CHILD(n256, chunk));
2905 : : }
2906 : 0 : break;
2907 : : }
2908 : : }
2909 : 0 : }
2910 : : #endif /* RT_DEBUG */
2911 : :
2912 : : #endif /* RT_DEFINE */
2913 : :
2914 : :
2915 : : /* undefine external parameters, so next radix tree can be defined */
2916 : : #undef RT_PREFIX
2917 : : #undef RT_SCOPE
2918 : : #undef RT_DECLARE
2919 : : #undef RT_DEFINE
2920 : : #undef RT_VALUE_TYPE
2921 : : #undef RT_VARLEN_VALUE_SIZE
2922 : : #undef RT_RUNTIME_EMBEDDABLE_VALUE
2923 : : #undef RT_SHMEM
2924 : : #undef RT_USE_DELETE
2925 : : #undef RT_DEBUG
2926 : :
2927 : : /* locally declared macros */
2928 : : #undef RT_MAKE_PREFIX
2929 : : #undef RT_MAKE_NAME
2930 : : #undef RT_MAKE_NAME_
2931 : : #undef RT_STR
2932 : : #undef RT_STR_
2933 : : #undef RT_SPAN
2934 : : #undef RT_NODE_MAX_SLOTS
2935 : : #undef RT_CHUNK_MASK
2936 : : #undef RT_MAX_SHIFT
2937 : : #undef RT_MAX_LEVEL
2938 : : #undef RT_GET_KEY_CHUNK
2939 : : #undef RT_BM_IDX
2940 : : #undef RT_BM_BIT
2941 : : #undef RT_NODE_MUST_GROW
2942 : : #undef RT_NODE_KIND_COUNT
2943 : : #undef RT_NUM_SIZE_CLASSES
2944 : : #undef RT_INVALID_SLOT_IDX
2945 : : #undef RT_SLAB_BLOCK_SIZE
2946 : : #undef RT_RADIX_TREE_MAGIC
2947 : : #undef RT_CHILD_PTR_FORMAT
2948 : :
2949 : : /* type declarations */
2950 : : #undef RT_RADIX_TREE
2951 : : #undef RT_RADIX_TREE_CONTROL
2952 : : #undef RT_CHILD_PTR
2953 : : #undef RT_PTR_ALLOC
2954 : : #undef RT_INVALID_PTR_ALLOC
2955 : : #undef RT_HANDLE
2956 : : #undef RT_ITER
2957 : : #undef RT_NODE
2958 : : #undef RT_NODE_ITER
2959 : : #undef RT_NODE_KIND_4
2960 : : #undef RT_NODE_KIND_16
2961 : : #undef RT_NODE_KIND_48
2962 : : #undef RT_NODE_KIND_256
2963 : : #undef RT_NODE_4
2964 : : #undef RT_NODE_16
2965 : : #undef RT_NODE_48
2966 : : #undef RT_NODE_256
2967 : : #undef RT_SIZE_CLASS
2968 : : #undef RT_SIZE_CLASS_ELEM
2969 : : #undef RT_SIZE_CLASS_INFO
2970 : : #undef RT_CLASS_4
2971 : : #undef RT_CLASS_16_LO
2972 : : #undef RT_CLASS_16_HI
2973 : : #undef RT_CLASS_48
2974 : : #undef RT_CLASS_256
2975 : : #undef RT_FANOUT_4
2976 : : #undef RT_FANOUT_4_MAX
2977 : : #undef RT_FANOUT_16_LO
2978 : : #undef RT_FANOUT_16_HI
2979 : : #undef RT_FANOUT_16_MAX
2980 : : #undef RT_FANOUT_48
2981 : : #undef RT_FANOUT_48_MAX
2982 : : #undef RT_FANOUT_256
2983 : :
2984 : : /* function declarations */
2985 : : #undef RT_CREATE
2986 : : #undef RT_FREE
2987 : : #undef RT_ATTACH
2988 : : #undef RT_DETACH
2989 : : #undef RT_LOCK_EXCLUSIVE
2990 : : #undef RT_LOCK_SHARE
2991 : : #undef RT_UNLOCK
2992 : : #undef RT_GET_HANDLE
2993 : : #undef RT_FIND
2994 : : #undef RT_SET
2995 : : #undef RT_BEGIN_ITERATE
2996 : : #undef RT_ITERATE_NEXT
2997 : : #undef RT_END_ITERATE
2998 : : #undef RT_USE_DELETE
2999 : : #undef RT_DELETE
3000 : : #undef RT_MEMORY_USAGE
3001 : : #undef RT_DUMP_NODE
3002 : : #undef RT_STATS
3003 : :
3004 : : /* internal helper functions */
3005 : : #undef RT_GET_VALUE_SIZE
3006 : : #undef RT_VALUE_IS_EMBEDDABLE
3007 : : #undef RT_CHILDPTR_IS_VALUE
3008 : : #undef RT_GET_SLOT_RECURSIVE
3009 : : #undef RT_DELETE_RECURSIVE
3010 : : #undef RT_ALLOC_NODE
3011 : : #undef RT_ALLOC_LEAF
3012 : : #undef RT_FREE_NODE
3013 : : #undef RT_FREE_LEAF
3014 : : #undef RT_FREE_RECURSE
3015 : : #undef RT_EXTEND_UP
3016 : : #undef RT_EXTEND_DOWN
3017 : : #undef RT_COPY_COMMON
3018 : : #undef RT_PTR_SET_LOCAL
3019 : : #undef RT_PTR_ALLOC_IS_VALID
3020 : : #undef RT_NODE_16_SEARCH_EQ
3021 : : #undef RT_NODE_4_GET_INSERTPOS
3022 : : #undef RT_NODE_16_GET_INSERTPOS
3023 : : #undef RT_SHIFT_ARRAYS_FOR_INSERT
3024 : : #undef RT_SHIFT_ARRAYS_AND_DELETE
3025 : : #undef RT_COPY_ARRAYS_FOR_INSERT
3026 : : #undef RT_COPY_ARRAYS_AND_DELETE
3027 : : #undef RT_NODE_48_IS_CHUNK_USED
3028 : : #undef RT_NODE_48_GET_CHILD
3029 : : #undef RT_NODE_256_IS_CHUNK_USED
3030 : : #undef RT_NODE_256_GET_CHILD
3031 : : #undef RT_KEY_GET_SHIFT
3032 : : #undef RT_SHIFT_GET_MAX_VAL
3033 : : #undef RT_NODE_SEARCH
3034 : : #undef RT_ADD_CHILD_4
3035 : : #undef RT_ADD_CHILD_16
3036 : : #undef RT_ADD_CHILD_48
3037 : : #undef RT_ADD_CHILD_256
3038 : : #undef RT_GROW_NODE_4
3039 : : #undef RT_GROW_NODE_16
3040 : : #undef RT_GROW_NODE_48
3041 : : #undef RT_REMOVE_CHILD_4
3042 : : #undef RT_REMOVE_CHILD_16
3043 : : #undef RT_REMOVE_CHILD_48
3044 : : #undef RT_REMOVE_CHILD_256
3045 : : #undef RT_SHRINK_NODE_16
3046 : : #undef RT_SHRINK_NODE_48
3047 : : #undef RT_SHRINK_NODE_256
3048 : : #undef RT_NODE_DELETE
3049 : : #undef RT_NODE_INSERT
3050 : : #undef RT_NODE_ITERATE_NEXT
3051 : : #undef RT_VERIFY_NODE
|
