1/* @title: Splay tree */
2#pragma once
3#include <container_of.h>
4#include <stdbool.h>
5#include <stddef.h>
6#include <stdint.h>
7
8struct splay_node {
9 struct splay_node *left;
10 struct splay_node *right;
11 struct splay_node *parent;
12};
13
14struct splay_node_ops {
15 int (*cmp)(const struct splay_node *a, const struct splay_node *b);
16 int (*cmp_key)(const struct splay_node *node, const void *key);
17};
18
19struct splay_tree {
20 struct splay_node *root;
21 const struct splay_node_ops *ops;
22};
23
24#define SPLAY_NODE_INIT \
25 (struct splay_node) { \
26 .left = NULL, .right = NULL, .parent = NULL \
27 }
28
29static inline void splay_init_node(struct splay_node *n) {
30 n->left = n->right = n->parent = NULL;
31}
32
33static inline bool splay_tree_empty(const struct splay_tree *tree) {
34 return tree->root == NULL;
35}
36
37void splay_tree_init(struct splay_tree *tree, const struct splay_node_ops *ops);
38
39void splay(struct splay_tree *tree, struct splay_node *node);
40
41void splay_insert(struct splay_tree *tree, struct splay_node *node);
42
43void splay_remove(struct splay_tree *tree, struct splay_node *node);
44
45struct splay_node *splay_find(struct splay_tree *tree, const void *key);
46
47struct splay_node *splay_first(const struct splay_tree *tree);
48struct splay_node *splay_last(const struct splay_tree *tree);
49struct splay_node *splay_next(const struct splay_node *node);
50struct splay_node *splay_prev(const struct splay_node *node);
51
52#define splay_entry(ptr, type, member) container_of(ptr, type, member)
53
54#define splay_for_each(pos, tree) \
55 for ((pos) = splay_first(tree); (pos); (pos) = splay_next(pos))
56
57#define splay_for_each_safe(pos, n, tree) \
58 for ((pos) = splay_first(tree), (n) = (pos) ? splay_next(pos) : NULL; \
59 (pos); (pos) = (n), (n) = (pos) ? splay_next(pos) : NULL)
60
61#define splay_for_each_entry(pos, tree, member) \
62 for (typeof(splay_first(tree)) __n = splay_first(tree); \
63 __n != NULL && \
64 (((pos) = splay_entry(__n, typeof(*(pos)), member)), true); \
65 __n = splay_next(__n))
66
67#define splay_for_each_entry_safe(pos, tmp, tree, member) \
68 for (typeof(splay_first(tree)) __n = splay_first(tree), __nx = NULL; \
69 __n != NULL && \
70 (((pos) = splay_entry(__n, typeof(*(pos)), member)), \
71 (__nx = splay_next(__n)), \
72 ((tmp) = __nx ? splay_entry(__nx, typeof(*(tmp)), member) : NULL), \
73 true); \
74 __n = __nx)
75
76#define splay_for_each_reverse(pos, tree) \
77 for ((pos) = splay_last(tree); (pos); (pos) = splay_prev(pos))
78
79#define splay_for_each_safe_reverse(pos, n, tree) \
80 for ((pos) = splay_last(tree), (n) = (pos) ? splay_prev(pos) : NULL; \
81 (pos); (pos) = (n), (n) = (pos) ? splay_prev(pos) : NULL)
82
83#define splay_for_each_entry_reverse(pos, tree, member) \
84 for (typeof(splay_last(tree)) __n = splay_last(tree); \
85 __n != NULL && \
86 (((pos) = splay_entry(__n, typeof(*(pos)), member)), true); \
87 __n = splay_prev(__n))
88
89#define splay_for_each_entry_safe_reverse(pos, tmp, tree, member) \
90 for (typeof(splay_last(tree)) __n = splay_last(tree), __nx = NULL; \
91 __n != NULL && \
92 (((pos) = splay_entry(__n, typeof(*(pos)), member)), \
93 (__nx = splay_prev(__n)), \
94 ((tmp) = __nx ? splay_entry(__nx, typeof(*(tmp)), member) : NULL), \
95 true); \
96 __n = __nx)
97