1/* @title: Treap (Randomized Binary Search Tree) */
2#pragma once
3#include <container_of.h>
4#include <stdbool.h>
5#include <stddef.h>
6#include <stdint.h>
7
8struct treap_node {
9 uint32_t priority;
10 struct treap_node *left;
11 struct treap_node *right;
12 struct treap_node *parent;
13};
14
15struct treap_node_ops {
16 int (*cmp)(const struct treap_node *a, const struct treap_node *b);
17 int (*cmp_key)(const struct treap_node *node, const void *key);
18};
19
20struct treap_tree {
21 struct treap_node *root;
22 const struct treap_node_ops *ops;
23};
24
25#define TREAP_NODE_INIT(prio) \
26 (struct treap_node) { \
27 .priority = (prio), .left = NULL, .right = NULL, .parent = NULL \
28 }
29
30static inline void treap_init_node(struct treap_node *n, uint32_t priority) {
31 n->priority = priority;
32 n->left = n->right = n->parent = NULL;
33}
34
35static inline bool treap_tree_empty(const struct treap_tree *tree) {
36 return tree->root == NULL;
37}
38
39void treap_tree_init(struct treap_tree *tree, const struct treap_node_ops *ops);
40
41void treap_insert(struct treap_tree *tree, struct treap_node *node);
42
43void treap_remove(struct treap_tree *tree, struct treap_node *node);
44
45struct treap_node *treap_find(const struct treap_tree *tree, const void *key);
46
47struct treap_node *treap_first(const struct treap_tree *tree);
48struct treap_node *treap_last(const struct treap_tree *tree);
49struct treap_node *treap_next(const struct treap_node *node);
50struct treap_node *treap_prev(const struct treap_node *node);
51
52#define treap_entry(ptr, type, member) container_of(ptr, type, member)
53
54#define treap_for_each(pos, tree) \
55 for ((pos) = treap_first(tree); (pos); (pos) = treap_next(pos))
56
57#define treap_for_each_safe(pos, n, tree) \
58 for ((pos) = treap_first(tree), (n) = (pos) ? treap_next(pos) : NULL; \
59 (pos); (pos) = (n), (n) = (pos) ? treap_next(pos) : NULL)
60
61#define treap_for_each_entry(pos, tree, member) \
62 for (typeof(treap_first(tree)) __n = treap_first(tree); \
63 __n != NULL && \
64 (((pos) = treap_entry(__n, typeof(*(pos)), member)), true); \
65 __n = treap_next(__n))
66
67#define treap_for_each_entry_safe(pos, tmp, tree, member) \
68 for (typeof(treap_first(tree)) __n = treap_first(tree), __nx = NULL; \
69 __n != NULL && \
70 (((pos) = treap_entry(__n, typeof(*(pos)), member)), \
71 (__nx = treap_next(__n)), \
72 ((tmp) = __nx ? treap_entry(__nx, typeof(*(tmp)), member) : NULL), \
73 true); \
74 __n = __nx)
75
76#define treap_for_each_reverse(pos, tree) \
77 for ((pos) = treap_last(tree); (pos); (pos) = treap_prev(pos))
78
79#define treap_for_each_safe_reverse(pos, n, tree) \
80 for ((pos) = treap_last(tree), (n) = (pos) ? treap_prev(pos) : NULL; \
81 (pos); (pos) = (n), (n) = (pos) ? treap_prev(pos) : NULL)
82
83#define treap_for_each_entry_reverse(pos, tree, member) \
84 for (typeof(treap_last(tree)) __n = treap_last(tree); \
85 __n != NULL && \
86 (((pos) = treap_entry(__n, typeof(*(pos)), member)), true); \
87 __n = treap_prev(__n))
88
89#define treap_for_each_entry_safe_reverse(pos, tmp, tree, member) \
90 for (typeof(treap_last(tree)) __n = treap_last(tree), __nx = NULL; \
91 __n != NULL && \
92 (((pos) = treap_entry(__n, typeof(*(pos)), member)), \
93 (__nx = treap_prev(__n)), \
94 ((tmp) = __nx ? treap_entry(__nx, typeof(*(tmp)), member) : NULL), \
95 true); \
96 __n = __nx)
97