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, type, member, tree) \
62 for (pos = treap_entry(treap_first(tree), type, member); \
63 (pos) != NULL && &pos->member != NULL; \
64 pos = treap_entry(treap_next(&pos->member), type, member))
65
66#define treap_for_each_entry_safe(pos, tmp, type, member, tree) \
67 for (pos = treap_entry(treap_first(tree), type, member), \
68 tmp = (pos) ? treap_entry(treap_next(&pos->member), type, member) \
69 : NULL; \
70 (pos) != NULL && &pos->member != NULL; pos = tmp, \
71 tmp = (pos) ? treap_entry(treap_next(&pos->member), type, member) \
72 : NULL)
73
74#define treap_for_each_reverse(pos, tree) \
75 for ((pos) = treap_last(tree); (pos); (pos) = treap_prev(pos))
76
77#define treap_for_each_safe_reverse(pos, n, tree) \
78 for ((pos) = treap_last(tree), (n) = (pos) ? treap_prev(pos) : NULL; \
79 (pos); (pos) = (n), (n) = (pos) ? treap_prev(pos) : NULL)
80
81#define treap_for_each_entry_reverse(pos, type, member, tree) \
82 for (pos = treap_entry(treap_last(tree), type, member); \
83 (pos) != NULL && &pos->member != NULL; \
84 pos = treap_entry(treap_prev(&pos->member), type, member))
85
86#define treap_for_each_entry_safe_reverse(pos, tmp, type, member, tree) \
87 for (pos = treap_entry(treap_last(tree), type, member), \
88 tmp = (pos) ? treap_entry(treap_prev(&pos->member), type, member) \
89 : NULL; \
90 (pos) != NULL && &pos->member != NULL; pos = tmp, \
91 tmp = (pos) ? treap_entry(treap_prev(&pos->member), type, member) \
92 : NULL)
93