Debian Codegraph @

src/misc/aatree.c

raw
1 /* ______ ___ ___
2 * /\ _ \ /\_ \ /\_ \
3 * \ \ \L\ \\//\ \ \//\ \ __ __ _ __ ___
4 * \ \ __ \ \ \ \ \ \ \ /'__`\ /'_ `\/\`'__\/ __`\
5 * \ \ \/\ \ \_\ \_ \_\ \_/\ __//\ \L\ \ \ \//\ \L\ \
6 * \ \_\ \_\/\____\/\____\ \____\ \____ \ \_\\ \____/
7 * \/_/\/_/\/____/\/____/\/____/\/___L\ \/_/ \/___/
8 * /\____/
9 * \_/__/
10 *
11 * AA tree, a type of self-balancing search tree.
12 *
13 * By Peter Wang.
14 */
15
16 /* prettier */
17 #define _AL_AATREE Aatree
18
19 #include "allegro5/allegro.h"
20 #include "allegro5/internal/aintern_aatree.h"
21
22 struct DelInfo
23 {
24 const void *key;
25 _al_cmp_t compare;
26 Aatree *last;
27 Aatree *deleted;
28 };
29
30 static Aatree nil = { 0, &nil, &nil, NULL, NULL };
31
32 static Aatree *skew(Aatree *T)
33 {
34 if (T == &nil)
35 return T;
36 if (T->left->level == T->level) {
37 Aatree *L = T->left;
38 T->left = L->right;
39 L->right = T;
40 return L;
41 }
42 return T;
43 }
44
45 static Aatree *split(Aatree *T)
46 {
47 if (T == &nil)
48 return T;
49 if (T->level == T->right->right->level) {
50 Aatree *R = T->right;
51 T->right = R->left;
52 R->left = T;
53 R->level = R->level + 1;
54 return R;
55 }
56 return T;
57 }
58
59 static Aatree *singleton(const void *key, void *value)
60 {
61 Aatree *T = al_malloc(sizeof(Aatree));
62 T->level = 1;
63 T->left = &nil;
64 T->right = &nil;
65 T->key = key;
66 T->value = value;
67 return T;
68 }
69
70 static Aatree *doinsert(Aatree *T, const void *key, void *value,
71 _al_cmp_t compare)
72 {
73 int cmp;
74 if (T == &nil) {
75 return singleton(key, value);
76 }
77 cmp = compare(key, T->key);
78 if (cmp < 0) {
79 T->left = doinsert(T->left, key, value, compare);
80 }
81 else if (cmp > 0) {
82 T->right = doinsert(T->right, key, value, compare);
83 }
84 else {
85 /* Already exists. We don't yet return any indication of this. */
86 return T;
87 }
88 T = skew(T);
89 T = split(T);
90 return T;
91 }
92
93 Aatree *_al_aa_insert(Aatree *T, const void *key, void *value,
94 _al_cmp_t compare)
95 {
96 if (T == NULL)
97 T = &nil;
98 return doinsert(T, key, value, compare);
99 }
100
101 void *_al_aa_search(const Aatree *T, const void *key, _al_cmp_t compare)
102 {
103 if (T == NULL)
104 return NULL;
105 while (T != &nil) {
106 int cmp = compare(key, T->key);
107 if (cmp == 0)
108 return T->value;
109 T = (cmp < 0) ? T->left : T->right;
110 }
111 return NULL;
112 }
113
114 static Aatree *dodelete(struct DelInfo *info, Aatree *T, void **ret_value)
115 {
116 if (T == &nil)
117 return T;
118
119 /* Search down the tree and set pointers last and deleted. */
120 info->last = T;
121 if (info->compare(info->key, T->key) < 0) {
122 T->left = dodelete(info, T->left, ret_value);
123 }
124 else {
125 info->deleted = T;
126 T->right = dodelete(info, T->right, ret_value);
127 }
128
129 /* At the bottom of the tree we remove the element if it is present. */
130 if (T == info->last &&
131 info->deleted != &nil &&
132 info->compare(info->key, info->deleted->key) == 0)
133 {
134 Aatree *right = T->right;
135 *ret_value = info->deleted->value;
136 info->deleted->key = T->key;
137 info->deleted->value = T->value;
138 info->deleted = &nil;
139 al_free(T);
140 return right;
141 }
142
143 /* On the way back, we rebalance. */
144 if (T->left->level < T->level - 1
145 || T->right->level < T->level - 1)
146 {
147 T->level--;
148 if (T->right->level > T->level) {
149 T->right->level = T->level;
150 }
151 T = skew(T);
152 T->right = skew(T->right);
153 T->right->right = skew(T->right->right);
154 T = split(T);
155 T->right = split(T->right);
156 }
157 return T;
158 }
159
160 /* ret_value is only set if the item was found and deleted.
161 * The caller should set it to some distinct value, e.g. NULL,
162 * to detect if no item was found.
163 */
164 Aatree *_al_aa_delete(Aatree *T, const void *key, _al_cmp_t compare,
165 void **ret_value)
166 {
167 struct DelInfo info;
168 info.key = key;
169 info.compare = compare;
170 info.last = &nil;
171 info.deleted = &nil;
172
173 if (T) {
174 T = dodelete(&info, T, ret_value);
175 if (T == &nil)
176 T = NULL;
177 }
178 return T;
179 }
180
181 void _al_aa_free(Aatree *T)
182 {
183 if (T && T != &nil) {
184 _al_aa_free(T->left);
185 _al_aa_free(T->right);
186 al_free(T);
187 }
188 }
189
190 /* vim: set sts=3 sw=3 et: */