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, type, member, tree) \
62 for (pos = splay_entry(splay_first(tree), type, member); \
63 (pos) != NULL && &pos->member != NULL; \
64 pos = splay_entry(splay_next(&pos->member), type, member))
65
66#define splay_for_each_entry_safe(pos, tmp, type, member, tree) \
67 for (pos = splay_entry(splay_first(tree), type, member), \
68 tmp = (pos) ? splay_entry(splay_next(&pos->member), type, member) \
69 : NULL; \
70 (pos) != NULL && &pos->member != NULL; pos = tmp, \
71 tmp = (pos) ? splay_entry(splay_next(&pos->member), type, member) \
72 : NULL)
73
74#define splay_for_each_reverse(pos, tree) \
75 for ((pos) = splay_last(tree); (pos); (pos) = splay_prev(pos))
76
77#define splay_for_each_safe_reverse(pos, n, tree) \
78 for ((pos) = splay_last(tree), (n) = (pos) ? splay_prev(pos) : NULL; \
79 (pos); (pos) = (n), (n) = (pos) ? splay_prev(pos) : NULL)
80
81#define splay_for_each_entry_reverse(pos, type, member, tree) \
82 for (pos = splay_entry(splay_last(tree), type, member); \
83 (pos) != NULL && &pos->member != NULL; \
84 pos = splay_entry(splay_prev(&pos->member), type, member))
85
86#define splay_for_each_entry_safe_reverse(pos, tmp, type, member, tree) \
87 for (pos = splay_entry(splay_last(tree), type, member), \
88 tmp = (pos) ? splay_entry(splay_prev(&pos->member), type, member) \
89 : NULL; \
90 (pos) != NULL && &pos->member != NULL; pos = tmp, \
91 tmp = (pos) ? splay_entry(splay_prev(&pos->member), type, member) \
92 : NULL)
93