Debian Codegraph @

libdrgn/binary_search_tree.h

raw
1 // Copyright (c) Meta Platforms, Inc. and affiliates.
2 // SPDX-License-Identifier: LGPL-2.1-or-later
3
4 /**
5 * @file
6 *
7 * Generic binary search trees.
8 *
9 * See @ref BinarySearchTrees.
10 */
11
12 #ifndef DRGN_BINARY_SEARCH_TREE_H
13 #define DRGN_BINARY_SEARCH_TREE_H
14
15 #include <stdbool.h>
16 #include <stddef.h>
17
18 #include "util.h"
19
20 /**
21 * @ingroup Internals
22 *
23 * @defgroup BinarySearchTrees Binary search trees
24 *
25 * Generic binary search trees.
26 *
27 * This implements a self-balancing binary search tree interface. The interface
28 * is generic, strongly typed (entries have a static type, not <tt>void *</tt>),
29 * and doesn't have any function pointer overhead. Currently, only splay trees
30 * are implemented, but this may be extended to support other variants like
31 * red-black trees or AVL trees.
32 *
33 * Entries are allocated separately from this interface. The interface is
34 * intrusive, i.e., entries must embed a @ref binary_tree_node.
35 *
36 * A binary search tree is defined with @ref DEFINE_BINARY_SEARCH_TREE(). Each
37 * generated binary search tree interface is prefixed with a given name; the
38 * interface documented here uses the example name @c binary_search_tree, which
39 * could be generated with this example code:
40 *
41 * @code{.c}
42 * typedef {
43 * ...
44 * struct binary_tree_node node;
45 * } entry_type;
46 * key_type entry_to_key(const entry_type *entry);
47 * int cmp_func(const key_type *a, const key_type *b);
48 * DEFINE_BINARY_SEARCH_TREE(binary_search_tree, entry_type, node, entry_to_key,
49 * cmp_func, splay)
50 * @endcode
51 *
52 * @sa HashTables
53 *
54 * @{
55 */
56
57 #ifdef DOXYGEN
58 /**
59 * @struct binary_search_tree
60 *
61 * Binary search tree instance.
62 *
63 * There are no requirements on how this is allocated; it may be global, on the
64 * stack, allocated by @c malloc(), embedded in another structure, etc.
65 */
66 struct binary_search_tree;
67
68 /**
69 * Binary search tree iterator.
70 *
71 * Several functions return an iterator or take one as an argument. This
72 * iterator has a reference to an entry, which can be @c NULL to indicate that
73 * there is no such entry. It may also contain private bookkeeping which should
74 * not be used.
75 *
76 * An iterator remains valid as long as the entry is not deleted.
77 */
78 struct binary_search_tree_iterator {
79 /** Pointer to the entry. */
80 entry_type *entry;
81 };
82
83 /**
84 * Initialize a @ref binary_search_tree.
85 *
86 * The new tree is empty.
87 */
88 void binary_search_tree_init(struct binary_search_tree *tree);
89
90 /**
91 * Return whether a @ref binary_search_tree has no entries.
92 *
93 * This is O(1).
94 */
95 bool binary_search_tree_empty(struct binary_search_tree *tree);
96
97 /**
98 * Insert an entry in a @ref binary_search_tree.
99 *
100 * If an entry with the same key is already in the tree, the entry is @em not
101 * inserted.
102 *
103 * @param[out] it_ret If not @c NULL, a returned iterator pointing to the newly
104 * inserted entry or the existing entry with the same key.
105 * @return 1 if the entry was inserted, 0 if the key already existed.
106 */
107 int binary_search_tree_insert(struct binary_search_tree *tree,
108 entry_type *entry,
109 struct binary_search_tree_iterator *it_ret);
110
111 /**
112 * Search for an entry in a @ref binary_search_tree.
113 *
114 * This searches for the entry with the given key.
115 *
116 * @return An iterator pointing to the entry with the given key, or an iterator
117 * with <tt>entry == NULL</tt> if the key was not found.
118 */
119 struct binary_search_tree_iterator
120 binary_search_tree_search(struct binary_search_tree *tree, const key_type *key);
121
122 /**
123 * Search for the entry with the greatest key less than or equal to the given
124 * key.
125 */
126 struct binary_search_tree_iterator
127 binary_search_tree_search_le(struct binary_search_tree *tree,
128 const key_type *key);
129
130
131 /**
132 * Delete an entry in a @ref binary_search_tree.
133 *
134 * This deletes the entry with the given key.
135 *
136 * @return @c true if the entry was found and deleted, @c false if not.
137 */
138 bool binary_search_tree_delete(struct binary_search_tree *tree,
139 const key_type *key);
140
141 /**
142 * Delete an entry given by an iterator in a @ref binary_search_tree.
143 *
144 * This deletes the entry pointed to by the iterator.
145 *
146 * @return An iterator pointing to the next entry in the tree. See @ref
147 * binary_search_tree_next().
148 */
149 struct binary_search_tree_iterator
150 binary_search_tree_delete_iterator(struct binary_search_tree *tree,
151 struct binary_search_tree_iterator it);
152
153 /**
154 * Delete an entry in a @ref binary_search_tree.
155 *
156 * @return An iterator pointing to the next entry in the tree. See @ref
157 * binary_search_tree_next().
158 */
159 struct binary_search_tree_iterator
160 binary_search_tree_delete_entry(struct binary_search_tree *tree,
161 entry_type *entry);
162
163 /**
164 * Get an iterator pointing to the first (in-order) entry in a @ref
165 * binary_search_tree.
166 *
167 * The first entry is the one with the lowest key.
168 *
169 * @return An iterator pointing to the first entry, or an iterator with
170 * <tt>entry == NULL</tt> if the tree is empty.
171 */
172 struct binary_search_tree_iterator
173 binary_search_tree_first(struct binary_search_tree *tree);
174
175 /**
176 * Get an iterator pointing to the last (in-order) entry in a @ref
177 * binary_search_tree.
178 *
179 * The last entry is the one with the greatest key.
180 *
181 * @return An iterator pointing to the last entry, or an iterator with
182 * <tt>entry == NULL</tt> if the tree is empty.
183 */
184 struct binary_search_tree_iterator
185 binary_search_tree_last(struct binary_search_tree *tree);
186
187 /**
188 * Get an iterator pointing to the next (in-order) entry in a @ref
189 * binary_search_tree.
190 *
191 * The next entry is the one with the lowest key that is greater than the
192 * current key.
193 *
194 * @return An iterator pointing to the next entry, or an iterator with <tt>entry
195 * == NULL</tt> if there are no more entries.
196 */
197 struct binary_search_tree_iterator
198 binary_search_tree_next(struct binary_search_tree_iterator it);
199
200 /**
201 * Get an iterator pointing to the first post-order entry in a @ref
202 * binary_search_tree.
203 *
204 * The first post-order entry is any entry which is a leaf in the tree.
205 *
206 * This is suitable for visiting all entries in a tree in order to free them:
207 *
208 * @code
209 * struct binary_search_tree_iterator it;
210 *
211 * it = binary_search_tree_first_post_order(tree);
212 * while (it.entry) {
213 * entry_type *entry = it.entry;
214 *
215 * binary_search_tree_next_post_order(&it);
216 * // Advancing the iterator accesses the current entry, so the entry must
217 * // be freed after the iterator has been advanced.
218 * free(entry);
219 * }
220 * @endcode
221 *
222 * @return An iterator pointing to the first entry, or an iterator with
223 * <tt>entry == NULL</tt> if the tree is empty.
224 */
225 struct binary_search_tree_iterator
226 binary_search_tree_first_post_order(struct binary_search_tree *tree);
227
228 /**
229 * Get an iterator pointing to the next post-order entry in a @ref
230 * binary_search_tree.
231 *
232 * The next post-order entry is any unvisited entry whose children have already
233 * been visited.
234 *
235 * @return An iterator pointing to the next entry, or an iterator with <tt>entry
236 * == NULL</tt> if there are no more entries.
237 */
238 struct binary_search_tree_iterator
239 binary_search_tree_next_post_order(struct binary_search_tree_iterator it);
240 #endif
241
242 /**
243 * Node in a binary search tree.
244 *
245 * This structure must be embedded in the entry type of a binary search tree. It
246 * should only be accessed by the binary search tree implementation.
247 */
248 struct binary_tree_node {
249 struct binary_tree_node *parent, *left, *right;
250 };
251
252 struct binary_tree_search_result {
253 struct binary_tree_node **nodep, *parent;
254 };
255
256 /*
257 * Binary search tree variants need to define three functions:
258 *
259 * drgn_##variant##_tree_insert_fixup(root, node, parent) is called after a node
260 * is inserted (as *root, parent->left, or parent->right). It must set the
261 * node's parent pointer and rebalance the tree.
262 *
263 * drgn_##variant##_tree_found(root, node) is called when a duplicate node is
264 * found for an insert operation or when a node is found for a search operation
265 * (but not for a delete operation). It may rebalance the tree or do nothing.
266 *
267 * drgn_##variant##_tree_delete(root, node) must delete the node and rebalance
268 * the tree.
269 */
270
271 void drgn_splay_tree_splay(struct binary_tree_node **root,
272 struct binary_tree_node *node,
273 struct binary_tree_node *parent);
274
275 static inline void drgn_splay_tree_insert_fixup(struct binary_tree_node **root,
276 struct binary_tree_node *node,
277 struct binary_tree_node *parent)
278 {
279 if (parent)
280 drgn_splay_tree_splay(root, node, parent);
281 else
282 node->parent = NULL;
283 }
284
285 static inline void drgn_splay_tree_found(struct binary_tree_node **root,
286 struct binary_tree_node *node)
287 {
288 if (node->parent)
289 drgn_splay_tree_splay(root, node, node->parent);
290 }
291
292 void drgn_splay_tree_delete(struct binary_tree_node **root,
293 struct binary_tree_node *node);
294
295 /**
296 * Define a binary search tree type without defining its functions.
297 *
298 * This is useful when the binary search tree type must be defined in one place
299 * (e.g., a header) but the interface is defined elsewhere (e.g., a source file)
300 * with @ref DEFINE_BINARY_SEARCH_TREE_FUNCTIONS(). Otherwise, just use @ref
301 * DEFINE_BINARY_SEARCH_TREE().
302 *
303 * @sa DEFINE_BINARY_SEARCH_TREE()
304 */
305 #define DEFINE_BINARY_SEARCH_TREE_TYPE(tree, entry_type) \
306 typedef typeof(entry_type) tree##_entry_type; \
307 \
308 struct tree { \
309 struct binary_tree_node *root; \
310 }; \
311 struct DEFINE_BINARY_SEARCH_TREE_needs_semicolon
312
313 /**
314 * Define the functions for a binary search tree.
315 *
316 * The binary search tree type must have already been defined with @ref
317 * DEFINE_BINARY_SEARCH_TREE_TYPE().
318 *
319 * Unless the type and function definitions must be in separate places, use @ref
320 * DEFINE_BINARY_SEARCH_TREE() instead.
321 *
322 * @sa DEFINE_BINARY_SEARCH_TREE()
323 */
324 #define DEFINE_BINARY_SEARCH_TREE_FUNCTIONS(tree, member, entry_to_key, \
325 cmp_func, variant) \
326 typedef typeof(entry_to_key((tree##_entry_type *)0)) tree##_key_type; \
327 \
328 static inline struct binary_tree_node * \
329 tree##_entry_to_node(tree##_entry_type *entry) \
330 { \
331 return &entry->member; \
332 } \
333 \
334 static inline tree##_entry_type * \
335 tree##_node_to_entry(struct binary_tree_node *node) \
336 { \
337 return container_of(node, tree##_entry_type, member); \
338 } \
339 \
340 static inline tree##_key_type \
341 tree##_entry_to_key(const tree##_entry_type *entry) \
342 { \
343 return entry_to_key(entry); \
344 } \
345 \
346 struct tree##_iterator { \
347 tree##_entry_type *entry; \
348 }; \
349 \
350 __attribute__((__unused__)) \
351 static void tree##_init(struct tree *tree) \
352 { \
353 tree->root = NULL; \
354 } \
355 \
356 __attribute__((__unused__)) \
357 static bool tree##_empty(struct tree *tree) \
358 { \
359 return tree->root == NULL; \
360 } \
361 \
362 static inline struct binary_tree_search_result \
363 tree##_search_internal(struct tree *tree, const tree##_key_type *key) \
364 { \
365 struct binary_tree_search_result res = { &tree->root, NULL, }; \
366 \
367 while (*res.nodep) { \
368 tree##_entry_type *other_entry; \
369 tree##_key_type other_key; \
370 int cmp; \
371 \
372 other_entry = tree##_node_to_entry(*res.nodep); \
373 other_key = tree##_entry_to_key(other_entry); \
374 cmp = cmp_func(key, &other_key); \
375 if (cmp < 0) { \
376 res.parent = *res.nodep; \
377 res.nodep = &(*res.nodep)->left; \
378 } else if (cmp > 0) { \
379 res.parent = *res.nodep; \
380 res.nodep = &(*res.nodep)->right; \
381 } else { \
382 break; \
383 } \
384 } \
385 return res; \
386 } \
387 \
388 __attribute__((__unused__)) \
389 static int tree##_insert(struct tree *tree, tree##_entry_type *entry, \
390 struct tree##_iterator *it_ret) \
391 { \
392 tree##_key_type key = tree##_entry_to_key(entry); \
393 struct binary_tree_search_result res; \
394 struct binary_tree_node *node; \
395 \
396 res = tree##_search_internal(tree, &key); \
397 if (*res.nodep) { \
398 if (it_ret) \
399 it_ret->entry = tree##_node_to_entry(*res.nodep); \
400 drgn_##variant##_tree_found(&tree->root, *res.nodep); \
401 return 0; \
402 } \
403 \
404 node = tree##_entry_to_node(entry); \
405 node->left = node->right = NULL; \
406 *res.nodep = node; \
407 drgn_##variant##_tree_insert_fixup(&tree->root, node, res.parent); \
408 return 1; \
409 } \
410 \
411 __attribute__((__unused__)) \
412 static struct tree##_iterator tree##_search(struct tree *tree, \
413 const tree##_key_type *key) \
414 { \
415 struct binary_tree_node *node; \
416 \
417 node = *tree##_search_internal(tree, key).nodep; \
418 if (!node) \
419 return (struct tree##_iterator){}; \
420 drgn_##variant##_tree_found(&tree->root, node); \
421 return (struct tree##_iterator){ tree##_node_to_entry(node), }; \
422 } \
423 \
424 __attribute__((__unused__)) \
425 static struct tree##_iterator tree##_search_le(struct tree *tree, \
426 const tree##_key_type *key) \
427 { \
428 struct binary_tree_node *node = tree->root; \
429 tree##_entry_type *entry = NULL; \
430 \
431 while (node) { \
432 tree##_entry_type *other_entry; \
433 tree##_key_type other_key; \
434 int cmp; \
435 \
436 other_entry = tree##_node_to_entry(node); \
437 other_key = tree##_entry_to_key(other_entry); \
438 cmp = cmp_func(key, &other_key); \
439 if (cmp < 0) { \
440 node = node->left; \
441 } else if (cmp > 0) { \
442 entry = other_entry; \
443 node = node->right; \
444 } else { \
445 entry = other_entry; \
446 break; \
447 } \
448 } \
449 if (entry) \
450 drgn_##variant##_tree_found(&tree->root, \
451 tree##_entry_to_node(entry)); \
452 return (struct tree##_iterator){ entry, }; \
453 } \
454 \
455 __attribute__((__unused__)) \
456 static bool tree##_delete(struct tree *tree, const tree##_key_type *key) \
457 { \
458 struct binary_tree_node *node; \
459 \
460 node = *tree##_search_internal(tree, key).nodep; \
461 if (!node) \
462 return false; \
463 drgn_##variant##_tree_delete(&tree->root, node); \
464 return true; \
465 } \
466 \
467 /* \
468 * We want this inlined so that the whole function call can be optimized away \
469 * if the return value is not used. \
470 */ \
471 __attribute__((__always_inline__)) \
472 static inline struct tree##_iterator \
473 tree##_next_impl(struct tree##_iterator it) \
474 { \
475 struct binary_tree_node *node = tree##_entry_to_node(it.entry); \
476 if (node->right) { \
477 node = node->right; \
478 /* \
479 * This hack (inspired by a similar hack in the F14 hash table \
480 * code) convinces the compiler that the loop always terminates \
481 * (otherwise the counter would overflow, which is undefined \
482 * behavior). \
483 */ \
484 for (long i = 1; i != 0; i++) { \
485 if (!node->left) \
486 break; \
487 node = node->left; \
488 } \
489 return (struct tree##_iterator){ tree##_node_to_entry(node), }; \
490 } \
491 \
492 for (long i = 1; i != 0; i++) { \
493 if (!node->parent || node != node->parent->right) \
494 break; \
495 node = node->parent; \
496 } \
497 if (node->parent) { \
498 return (struct tree##_iterator){ \
499 tree##_node_to_entry(node->parent), \
500 }; \
501 } \
502 return (struct tree##_iterator){}; \
503 } \
504 \
505 __attribute__((__always_inline__)) \
506 static inline struct tree##_iterator \
507 tree##_delete_iterator(struct tree *tree, struct tree##_iterator it) \
508 { \
509 struct binary_tree_node *node; \
510 \
511 node = tree##_entry_to_node(it.entry); \
512 it = tree##_next_impl(it); \
513 drgn_##variant##_tree_delete(&tree->root, node); \
514 return it; \
515 } \
516 \
517 __attribute__((__always_inline__, __unused__)) \
518 static inline struct tree##_iterator \
519 tree##_delete_entry(struct tree *tree, tree##_entry_type *entry) \
520 { \
521 return tree##_delete_iterator(tree, (struct tree##_iterator){ entry }); \
522 } \
523 \
524 __attribute__((__unused__)) \
525 static struct tree##_iterator tree##_first(struct tree *tree) \
526 { \
527 struct binary_tree_node *node = tree->root; \
528 \
529 if (!node) \
530 return (struct tree##_iterator){}; \
531 \
532 while (node->left) \
533 node = node->left; \
534 return (struct tree##_iterator){ tree##_node_to_entry(node), }; \
535 } \
536 \
537 __attribute__((__unused__)) \
538 static struct tree##_iterator tree##_last(struct tree *tree) \
539 { \
540 struct binary_tree_node *node = tree->root; \
541 \
542 if (!node) \
543 return (struct tree##_iterator){}; \
544 \
545 while (node->right) \
546 node = node->right; \
547 return (struct tree##_iterator){ tree##_node_to_entry(node), }; \
548 } \
549 \
550 __attribute__((__unused__)) \
551 static struct tree##_iterator tree##_next(struct tree##_iterator it) \
552 { \
553 return tree##_next_impl(it); \
554 } \
555 \
556 __attribute__((__unused__)) \
557 static struct tree##_iterator tree##_first_post_order(struct tree *tree) \
558 { \
559 struct binary_tree_node *node = tree->root; \
560 \
561 if (!node) \
562 return (struct tree##_iterator){}; \
563 \
564 for (;;) { \
565 if (node->left) { \
566 node = node->left; \
567 } else if (node->right) { \
568 node = node->right; \
569 } else { \
570 return (struct tree##_iterator){ \
571 tree##_node_to_entry(node), \
572 }; \
573 } \
574 \
575 } \
576 } \
577 \
578 __attribute__((__unused__)) \
579 static struct tree##_iterator tree##_next_post_order(struct tree##_iterator it) \
580 { \
581 struct binary_tree_node *node = tree##_entry_to_node(it.entry); \
582 \
583 if (!node->parent) { \
584 return (struct tree##_iterator){}; \
585 } else if (node == node->parent->left && node->parent->right) { \
586 node = node->parent->right; \
587 for (;;) { \
588 if (node->left) { \
589 node = node->left; \
590 } else if (node->right) { \
591 node = node->right; \
592 } else { \
593 return (struct tree##_iterator){ \
594 tree##_node_to_entry(node), \
595 }; \
596 } \
597 } \
598 } else { \
599 return (struct tree##_iterator){ \
600 tree##_node_to_entry(node->parent), \
601 }; \
602 } \
603 } \
604 struct DEFINE_BINARY_SEARCH_TREE_needs_semicolon
605
606 /**
607 * Define a binary search tree interface.
608 *
609 * This macro defines a binary search tree type along with its functions.
610 *
611 * @param[in] tree Name of the type to define. This is prefixed to all of the
612 * types and functions defined for that type.
613 * @param[in] entry_type Type of entries in the tree.
614 * @param[in] member Name of the @ref binary_tree_node member in @p entry_type.
615 * @param[in] entry_to_key Name of function or macro which is passed a <tt>const
616 * entry_type *</tt> and returns the key for that entry. The return type is the
617 * @c key_type of the tree. The passed entry is never @c NULL.
618 * @param[in] cmp_func Comparison function which takes two <tt>const key_type
619 * *</tt> and returns an @c int. The return value must be negative if the first
620 * key is less than the second key, positive if the first key is greater than
621 * the second key, and zero if they are equal.
622 * @param[in] variant The binary search tree implementation to use. Currently
623 * this can only be @c splay.
624 */
625 #define DEFINE_BINARY_SEARCH_TREE(tree, entry_type, member, entry_to_key, \
626 cmp_func, variant) \
627 DEFINE_BINARY_SEARCH_TREE_TYPE(tree, entry_type); \
628 DEFINE_BINARY_SEARCH_TREE_FUNCTIONS(tree, member, entry_to_key, cmp_func, \
629 variant)
630
631 #ifdef DOXYGEN
632 /** Compare two scalar keys. */
633 bool binary_search_tree_scalar_cmp(const T *a, const T *b);
634 #else
635 #define binary_search_tree_scalar_cmp(a, b) ({ \
636 __auto_type _a = *(a); \
637 __auto_type _b = *(b); \
638 \
639 _a < _b ? -1 : _a > _b ? 1 : 0; \
640 })
641 #endif
642
643 /** @} */
644
645 #endif /* DRGN_BINARY_SEARCH_TREE_H */