1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
/* SPDX-License-Identifier: GPL-3.0-or-later */
/* Copyright 2021 - 2022, Kim Kuparinen < kimi.h.kuparinen@gmail.com > */
#ifndef SP_TREE_H
#define SP_TREE_H
/**
* @file sp_tree.h
* sp_trees, a type of binary search trees.
*/
#include <apos/types.h>
/**
* Get root of tree from \ref sp_root.
*
* @param r Instance of \ref sp_root.
* @return Actual root of tree.
*/
#define sp_root(r) ((r)->sp_r)
/**
* Get left node.
*
* @param n Node to read.
* @return Left node of read node.
* \see sp_right().
*/
#define sp_left(n) ((n)->left)
/**
* Get right node.
*
* @param n Node to read.
* @return Right node of read node.
* \see sp_left().
*/
#define sp_right(n) ((n)->right)
/**
* Get parent of right node.
* In most situations should point back towards the node it started from, but
* when in the middle of updating the tree it might temporarily point somewhere else.
*
* @param n Node to read.
* @return Parent of right node of read node.
* \see sp_lparen().
*/
#define sp_rparen(n) (sp_right(n)->parent)
/**
* Get parent of left node.
*
* @param n Node to read.
* @return Parent of left node of read node.
* \see sp_rparen().
*/
#define sp_lparen(n) (sp_left(n)->parent)
/**
* Get parent of node.
*
* @param n Node to read.
* @return Parent of read node.
*/
#define sp_paren(n) ((n)->parent)
/**
* Get grandparent (parent of parent) of node.
*
* @param n Node to read.
* @return Grandparent of read node.
* \see sp_has_gparen().
*/
#define sp_gparen(n) ((n)->parent->parent)
/** Check if node has grandparent.
*
* @param n Node to read.
* @return Non-zero if node has grandparent, \c 0 otherwise.
* \see sp_gparen().
*/
#define sp_has_gparen(n) (sp_paren(n) && sp_gparen(n))
/** Tree node.
* Embed this structure in structures you want to build a tree of.
* \see common/mem_region.c, for example.
*/
struct sp_node {
/** Hint. Approximate maximum tree height up to the current node. */
int_fast16_t hint;
/** Lefthand node. */
struct sp_node *left;
/** Righthand node. */
struct sp_node *right;
/** Parent node. Technically speaking not necessary, but in this case I
* went with time over space. */
struct sp_node *parent;
};
/** Convenience structure for trees. */
struct sp_root {
/** Pointer to actual root of tree. */
struct sp_node *sp_r;
};
/** Which side of the parent node a new node should be inserted to. */
enum sp_dir {
/** Left side. */
LEFT,
/** Right side. */
RIGHT
};
/**
* Get first, leftmost node under specified node.
*
* @param n Node to start with.
* @return Leftmost node under \c n, or \c n if there are none.
*/
struct sp_node *sp_first(struct sp_node *n);
/**
* Get last, rightmost node under specified node.
*
* @param n Node to start with.
* @return Rightmost node under \c n, or \c n if there are none.
*/
struct sp_node *sp_last(struct sp_node *n);
/**
* Insert new node into tree.
* Does not allocate any memory.
*
* @param root Root of tree.
* @param p Parent of new node.
* @param n New node.
* @param d Which side of the parent node the new node should be on.
*/
void sp_insert(struct sp_node **root, struct sp_node *p, struct sp_node *n,
enum sp_dir d);
/**
* Remove node from tree.
* Does not free any memory.
*
* @param root Root of tree.
* @param n Node to remove.
*/
void sp_remove(struct sp_node **root, struct sp_node *n);
#endif /* SP_TREE_H */
|
