1 /*
2 * mpatrol
3 * A library for controlling and tracing dynamic memory allocations.
4 * Copyright (C) 1997-2002 Graeme S. Roy <graeme.roy@analog.com>
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Library General Public License for more details.
15 *
16 * You should have received a copy of the GNU Library General Public
17 * License along with this library; if not, write to the Free
18 * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
19 * MA 02111-1307, USA.
20 */
21
22
23 /*
24 * Binary search trees. This implementation is based upon the red-black
25 * tree data structures and algorithms described in Introduction to
26 * Algorithms, First Edition by Cormen, Leiserson and Rivest (The MIT Press,
27 * 1990, ISBN 0-262-03141-8).
28 */
29
30
31 #include "tree.h"
32
33
34 #if MP_IDENT_SUPPORT
35 #ident "$Id: tree.c,v 1.7 2002/01/08 20:13:59 graeme Exp $"
36 #else /* MP_IDENT_SUPPORT */
37 static MP_CONST MP_VOLATILE char *tree_id = "$Id: tree.c,v 1.7 2002/01/08 20:13:59 graeme Exp $";
38 #endif /* MP_IDENT_SUPPORT */
39
40
41 #ifdef __cplusplus
42 extern "C"
43 {
44 #endif /* __cplusplus */
45
46
47 /* Initialise the fields of a tree root so that the tree becomes empty.
48 * Note the sentinel leaf node which is used to make tree manipulation
49 * easier and is pointed to by all real leaf nodes.
50 */
51
52 MP_GLOBAL
53 void
__mp_newtree(treeroot * t)54 __mp_newtree(treeroot *t)
55 {
56 t->root = &t->null;
57 t->null.parent = t->null.left = t->null.right = NULL;
58 t->null.key = t->null.flag = 0;
59 t->size = 0;
60 }
61
62
63 /* Perform a left rotation of a subtree in order to preserve inorder key
64 * ordering.
65 */
66
67 static
68 void
rotateleft(treeroot * t,treenode * l)69 rotateleft(treeroot *t, treenode *l)
70 {
71 treenode *r;
72
73 if ((r = l->right) == NULL)
74 return;
75 if ((l->right = r->left)->left)
76 r->left->parent = l;
77 if ((r->parent = l->parent) == NULL)
78 t->root = r;
79 else if (l == l->parent->left)
80 l->parent->left = r;
81 else
82 l->parent->right = r;
83 r->left = l;
84 l->parent = r;
85 }
86
87
88 /* Perform a right rotation of a subtree in order to preserve inorder key
89 * ordering.
90 */
91
92 static
93 void
rotateright(treeroot * t,treenode * r)94 rotateright(treeroot *t, treenode *r)
95 {
96 treenode *l;
97
98 if ((l = r->left) == NULL)
99 return;
100 if ((r->left = l->right)->right)
101 l->right->parent = r;
102 if ((l->parent = r->parent) == NULL)
103 t->root = l;
104 else if (r == r->parent->left)
105 r->parent->left = l;
106 else
107 r->parent->right = l;
108 l->right = r;
109 r->parent = l;
110 }
111
112
113 /* Insert a new tree node with a specific key into a tree, possibly
114 * restructuring the tree in order to preserve the red-black property and
115 * keep it properly balanced.
116 */
117
118 MP_GLOBAL
119 void
__mp_treeinsert(treeroot * t,treenode * n,unsigned long k)120 __mp_treeinsert(treeroot *t, treenode *n, unsigned long k)
121 {
122 treenode *a, *b;
123
124 if (n == &t->null)
125 return;
126 a = t->root;
127 b = NULL;
128 while (a->left)
129 {
130 b = a;
131 if (k < a->key)
132 a = a->left;
133 else
134 a = a->right;
135 }
136 n->parent = b;
137 n->left = &t->null;
138 n->right = &t->null;
139 n->key = k;
140 n->flag = 1;
141 if (b == NULL)
142 t->root = n;
143 else if (k < b->key)
144 b->left = n;
145 else
146 b->right = n;
147 while ((n != t->root) && n->parent->flag)
148 if (n->parent == n->parent->parent->left)
149 if ((a = n->parent->parent->right)->flag)
150 {
151 a->flag = 0;
152 n->parent->flag = 0;
153 n = n->parent->parent;
154 n->flag = 1;
155 }
156 else
157 {
158 if (n == n->parent->right)
159 {
160 n = n->parent;
161 rotateleft(t, n);
162 }
163 n->parent->flag = 0;
164 n->parent->parent->flag = 1;
165 rotateright(t, n->parent->parent);
166 }
167 else
168 if ((a = n->parent->parent->left)->flag)
169 {
170 a->flag = 0;
171 n->parent->flag = 0;
172 n = n->parent->parent;
173 n->flag = 1;
174 }
175 else
176 {
177 if (n == n->parent->left)
178 {
179 n = n->parent;
180 rotateright(t, n);
181 }
182 n->parent->flag = 0;
183 n->parent->parent->flag = 1;
184 rotateleft(t, n->parent->parent);
185 }
186 t->root->flag = 0;
187 t->size++;
188 }
189
190
191 /* Remove an existing tree node from a tree, possibly restructuring the
192 * tree in order to preserve the red-black property and keep it properly
193 * balanced.
194 */
195
196 MP_GLOBAL
197 void
__mp_treeremove(treeroot * t,treenode * n)198 __mp_treeremove(treeroot *t, treenode *n)
199 {
200 treenode *a, *b;
201 char f;
202
203 if (n == &t->null)
204 return;
205 if ((n->left->left == NULL) || (n->right->right == NULL))
206 b = n;
207 else
208 b = __mp_successor(n);
209 if (b->left->left)
210 a = b->left;
211 else
212 a = b->right;
213 if ((a->parent = b->parent) == NULL)
214 t->root = a;
215 else if (b == b->parent->left)
216 b->parent->left = a;
217 else
218 b->parent->right = a;
219 f = b->flag;
220 if (b != n)
221 {
222 if ((b->parent = n->parent) == NULL)
223 t->root = b;
224 else if (n == n->parent->left)
225 n->parent->left = b;
226 else
227 n->parent->right = b;
228 if ((b->left = n->left)->left)
229 n->left->parent = b;
230 if ((b->right = n->right)->right)
231 n->right->parent = b;
232 if (a->parent == n)
233 a->parent = b;
234 b->flag = n->flag;
235 }
236 if (f == 0)
237 {
238 while ((a != t->root) && !a->flag)
239 if (a == a->parent->left)
240 {
241 if ((b = a->parent->right)->flag)
242 {
243 b->flag = 0;
244 a->parent->flag = 1;
245 rotateleft(t, a->parent);
246 b = a->parent->right;
247 }
248 if (!b->left->flag && !b->right->flag)
249 {
250 b->flag = 1;
251 a = a->parent;
252 }
253 else
254 {
255 if (!b->right->flag)
256 {
257 b->flag = 1;
258 b->left->flag = 0;
259 rotateright(t, b);
260 b = a->parent->right;
261 }
262 b->flag = a->parent->flag;
263 a->parent->flag = 0;
264 b->right->flag = 0;
265 rotateleft(t, a->parent);
266 a = t->root;
267 }
268 }
269 else
270 {
271 if ((b = a->parent->left)->flag)
272 {
273 b->flag = 0;
274 a->parent->flag = 1;
275 rotateright(t, a->parent);
276 b = a->parent->left;
277 }
278 if (!b->left->flag && !b->right->flag)
279 {
280 b->flag = 1;
281 a = a->parent;
282 }
283 else
284 {
285 if (!b->left->flag)
286 {
287 b->flag = 1;
288 b->right->flag = 0;
289 rotateleft(t, b);
290 b = a->parent->left;
291 }
292 b->flag = a->parent->flag;
293 a->parent->flag = 0;
294 b->left->flag = 0;
295 rotateright(t, a->parent);
296 a = t->root;
297 }
298 }
299 a->flag = 0;
300 }
301 t->null.parent = NULL;
302 t->size--;
303 }
304
305
306 /* Search a subtree for a node with an exact match for a given key,
307 * or return NULL if no such node exists.
308 */
309
310 MP_GLOBAL
311 treenode *
__mp_search(treenode * n,unsigned long k)312 __mp_search(treenode *n, unsigned long k)
313 {
314 while (n->left && (k != n->key))
315 if (k < n->key)
316 n = n->left;
317 else
318 n = n->right;
319 if (n->left)
320 return n;
321 return NULL;
322 }
323
324
325 /* Search a subtree for a node with the highest key not greater than the
326 * given key, or return NULL if no such node exists.
327 */
328
329 MP_GLOBAL
330 treenode *
__mp_searchlower(treenode * n,unsigned long k)331 __mp_searchlower(treenode *n, unsigned long k)
332 {
333 treenode *a;
334
335 a = n;
336 while (n->left && (k != n->key))
337 {
338 a = n;
339 if (k < n->key)
340 n = n->left;
341 else
342 n = n->right;
343 }
344 if (n->left)
345 return n;
346 if (a->left && (k > a->key))
347 return a;
348 return __mp_predecessor(a);
349 }
350
351
352 /* Search a subtree for a node with the lowest key not less than the
353 * given key, or return NULL if no such node exists.
354 */
355
356 MP_GLOBAL
357 treenode *
__mp_searchhigher(treenode * n,unsigned long k)358 __mp_searchhigher(treenode *n, unsigned long k)
359 {
360 treenode *a;
361
362 a = n;
363 while (n->right && (k != n->key))
364 {
365 a = n;
366 if (k < n->key)
367 n = n->left;
368 else
369 n = n->right;
370 }
371 if (n->right)
372 return n;
373 if (a->right && (k < a->key))
374 return a;
375 return __mp_successor(a);
376 }
377
378
379 /* Return the leftmost node of a subtree.
380 */
381
382 MP_GLOBAL
383 treenode *
__mp_minimum(treenode * n)384 __mp_minimum(treenode *n)
385 {
386 treenode *a;
387
388 if (n->left == NULL)
389 return NULL;
390 while ((a = n->left)->left)
391 n = a;
392 return n;
393 }
394
395
396 /* Return the rightmost node of a subtree.
397 */
398
399 MP_GLOBAL
400 treenode *
__mp_maximum(treenode * n)401 __mp_maximum(treenode *n)
402 {
403 treenode *a;
404
405 if (n->right == NULL)
406 return NULL;
407 while ((a = n->right)->right)
408 n = a;
409 return n;
410 }
411
412
413 /* Return the predecessor node of a given node, or NULL if no such
414 * node exists.
415 */
416
417 MP_GLOBAL
418 treenode *
__mp_predecessor(treenode * n)419 __mp_predecessor(treenode *n)
420 {
421 treenode *a;
422
423 if (n->left == NULL)
424 return NULL;
425 if (n->left->left)
426 return __mp_maximum(n->left);
427 a = n->parent;
428 while ((a != NULL) && (n == a->left))
429 {
430 n = a;
431 a = a->parent;
432 }
433 return a;
434 }
435
436
437 /* Return the successor node of a given node, or NULL if no such
438 * node exists.
439 */
440
441 MP_GLOBAL
442 treenode *
__mp_successor(treenode * n)443 __mp_successor(treenode *n)
444 {
445 treenode *a;
446
447 if (n->right == NULL)
448 return NULL;
449 if (n->right->right)
450 return __mp_minimum(n->right);
451 a = n->parent;
452 while ((a != NULL) && (n == a->right))
453 {
454 n = a;
455 a = a->parent;
456 }
457 return a;
458 }
459
460
461 #ifdef __cplusplus
462 }
463 #endif /* __cplusplus */
464