/[cvs]/eggdrop1.9/src/egglib/avl.c
ViewVC logotype

Contents of /eggdrop1.9/src/egglib/avl.c

Parent Directory Parent Directory | Revision Log Revision Log | View Revision Graph Revision Graph


Revision 1.2 - (show annotations) (download) (as text)
Sun Oct 28 13:30:34 2001 UTC (17 years, 11 months ago) by ite
Branch: MAIN
CVS Tags: HEAD
Changes since 1.1: +0 -0 lines
File MIME type: text/x-chdr
FILE REMOVED
Renamed src/adns, src/compat, src/egglib to lib/adns, lib/compat, lib/egglib respectively.

1 /* See header file avl.h for licensing info. */
2
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include "mempool.h"
6 #include "avl.h"
7
8 static mempool_t *avl_node_mempool;
9
10 #define NEW_NODE ((avl_node_t *)mempool_get_chunk(avl_node_mempool));
11
12 avl_tree_t *avl_create(avl_tree_t * tree, avl_comparison_func cmp, void *param)
13 {
14 avl_tree_t *mytree;
15
16 /* See if mempool needs to be initialized. */
17 if (!avl_node_mempool) {
18 avl_node_mempool = mempool_create(NULL, 10, sizeof(avl_node_t));
19 }
20
21 if (tree) mytree = tree;
22 else mytree = (avl_tree_t *) malloc(sizeof(*tree));
23
24 mytree->root.link[0] = NULL;
25 mytree->root.link[1] = NULL;
26 mytree->cmp = cmp;
27 mytree->count = 0;
28 mytree->param = param;
29
30 return (mytree);
31 }
32
33 /* Destroy tree TREE. Function FREE_FUNC is called for every node in
34 the tree as it is destroyed.
35
36 Do not attempt to reuse the tree after it has been freed. Create a
37 new one. */
38 void avl_destroy(avl_tree_t * tree, avl_node_func free_func)
39 {
40 /* Uses Knuth's Algorithm 2.3.1T as modified in exercise 13 (postorder traversal). */
41
42 /* T1. */
43 avl_node_t *an[AVL_MAX_HEIGHT]; /* Stack A: nodes. */
44 char ab[AVL_MAX_HEIGHT]; /* Stack A: bits. */
45 int ap = 0; /* Stack A: height. */
46 avl_node_t *p = tree->root.link[0];
47
48 for (;;) {
49 /* T2. */
50 while (p != NULL) {
51 /* T3. */
52 ab[ap] = 0;
53 an[ap++] = p;
54 p = p->link[0];
55 }
56
57 /* T4. */
58 for (;;) {
59 if (ap == 0) goto done;
60
61 p = an[--ap];
62 if (ab[ap] == 0) {
63 ab[ap++] = 1;
64 p = p->link[1];
65 break;
66 }
67
68 if (free_func) free_func(p->data, tree->param);
69 mempool_free_chunk(avl_node_mempool, p);
70 }
71 }
72
73 done:
74 free(tree);
75 }
76
77 /* avl_destroy() with FREE_FUNC hardcoded as free(). */
78 void avl_free(avl_tree_t * tree)
79 {
80 avl_destroy(tree, (avl_node_func) free);
81 }
82
83 /* Return the number of nodes in TREE. */
84 int avl_count(const avl_tree_t * tree)
85 {
86 return tree->count;
87 }
88
89 void avl_walk(const avl_tree_t * tree, avl_node_func walk_func, void *param)
90 {
91 /* Uses Knuth's algorithm 2.3.1T (inorder traversal). */
92
93 /* T1. */
94 const avl_node_t *an[AVL_MAX_HEIGHT]; /* Stack A: nodes. */
95 const avl_node_t **ap = an; /* Stack A: stack pointer. */
96 const avl_node_t *p = tree->root.link[0];
97
98 for (;;) {
99 /* T2. */
100 while (p != NULL) {
101 /* T3. */
102 *ap++ = p;
103 p = p->link[0];
104 }
105
106 /* T4. */
107 if (ap == an) return;
108 p = *--ap;
109
110 /* T5. */
111 walk_func(p->data, param);
112 p = p->link[1];
113 }
114 }
115
116 /* Each call to this function for a given TREE and TRAV return the
117 next item in the tree in inorder. Initialize the first element of
118 TRAV (init) to 0 before calling the first time. Returns NULL when
119 out of elements. */
120 void *avl_traverse(const avl_tree_t * tree, avl_traverser_t * trav)
121 {
122
123 /* Uses Knuth's algorithm 2.3.1T (inorder traversal). */
124 if (trav->init == 0) {
125 /* T1. */
126 trav->init = 1;
127 trav->nstack = 0;
128 trav->p = tree->root.link[0];
129 }
130 else trav->p = trav->p->link[1]; /* T5. */
131
132 /* T2. */
133 while (trav->p != NULL) {
134 /* T3. */
135 trav->stack[trav->nstack++] = trav->p;
136 trav->p = trav->p->link[0];
137 }
138
139 /* T4. */
140 if (trav->nstack == 0) {
141 trav->init = 0;
142 return NULL;
143 }
144 trav->p = trav->stack[--trav->nstack];
145
146 /* T5. */
147 return trav->p->data;
148 }
149
150 /* Search TREE for an item matching ITEM. If found, returns a pointer
151 to the address of the item. If none is found, ITEM is inserted
152 into the tree, and a pointer to the address of ITEM is returned.
153 In either case, the pointer returned can be changed by the caller,
154 or the returned data item can be directly edited, but the key data
155 in the item must not be changed. */
156 void **avl_probe(avl_tree_t * tree, void *item)
157 {
158 /* Uses Knuth's Algorithm 6.2.3A (balanced tree search and
159 insertion), but caches results of comparisons. In empirical
160 tests this eliminates about 25% of the comparisons seen under
161 random insertions. */
162
163 /* A1. */
164 avl_node_t *t;
165 avl_node_t *s, *p, *q, *r;
166
167 t = &tree->root;
168 s = p = t->link[0];
169
170 if (s == NULL) {
171 tree->count++;
172 q = t->link[0] = NEW_NODE;
173 q->data = item;
174 q->link[0] = q->link[1] = NULL;
175 q->bal = 0;
176 return &q->data;
177 }
178
179 for (;;) {
180 /* A2. */
181 int diff = tree->cmp(item, p->data, tree->param);
182
183 /* A3. */
184 if (diff < 0) {
185 p->cache = 0;
186 q = p->link[0];
187 if (q == NULL) {
188 p->link[0] = q = NEW_NODE;
189 break;
190 }
191 }
192 /* A4. */
193 else if (diff > 0) {
194 p->cache = 1;
195 q = p->link[1];
196 if (q == NULL) {
197 p->link[1] = q = NEW_NODE;
198 break;
199 }
200 }
201 else /* A2. */
202 return &p->data;
203
204 /* A3, A4. */
205 if (q->bal != 0) t = p, s = q;
206 p = q;
207 }
208
209 /* A5. */
210 tree->count++;
211 q->data = item;
212 q->link[0] = q->link[1] = NULL;
213 q->bal = 0;
214
215 /* A6. */
216 r = p = s->link[(int)s->cache];
217 while (p != q) {
218 p->bal = p->cache * 2 - 1;
219 p = p->link[(int)p->cache];
220 }
221
222 /* A7. */
223 if (s->cache == 0) {
224 /* a = -1. */
225 if (s->bal == 0) {
226 s->bal = -1;
227 return &q->data;
228 }
229 else if (s->bal == +1) {
230 s->bal = 0;
231 return &q->data;
232 }
233
234 if (r->bal == -1) {
235 /* A8. */
236 p = r;
237 s->link[0] = r->link[1];
238 r->link[1] = s;
239 s->bal = r->bal = 0;
240 }
241 else {
242 /* A9. */
243 p = r->link[1];
244 r->link[1] = p->link[0];
245 p->link[0] = r;
246 s->link[0] = p->link[1];
247 p->link[1] = s;
248 if (p->bal == -1) s->bal = 1, r->bal = 0;
249 else if (p->bal == 0) s->bal = r->bal = 0;
250 else s->bal = 0, r->bal = -1;
251 p->bal = 0;
252 }
253 }
254 else {
255 /* a == +1. */
256 if (s->bal == 0) {
257 s->bal = 1;
258 return &q->data;
259 }
260 else if (s->bal == -1) {
261 s->bal = 0;
262 return &q->data;
263 }
264
265 if (r->bal == +1) {
266 /* A8. */
267 p = r;
268 s->link[1] = r->link[0];
269 r->link[0] = s;
270 s->bal = r->bal = 0;
271 }
272 else {
273 /* A9. */
274 p = r->link[0];
275 r->link[0] = p->link[1];
276 p->link[1] = r;
277 s->link[1] = p->link[0];
278 p->link[0] = s;
279 if (p->bal == +1) s->bal = -1, r->bal = 0;
280 else if (p->bal == 0) s->bal = r->bal = 0;
281 else s->bal = 0, r->bal = 1;
282 p->bal = 0;
283 }
284 }
285
286 /* A10. */
287 if (t != &tree->root && s == t->link[1]) t->link[1] = p;
288 else t->link[0] = p;
289
290 return &q->data;
291 }
292
293 /* Search TREE for an item matching ITEM, and return it if found. */
294 void *avl_find(const avl_tree_t * tree, const void *item)
295 {
296 const avl_node_t *p;
297
298 for (p = tree->root.link[0]; p;) {
299 int diff = tree->cmp(item, p->data, tree->param);
300
301 if (diff < 0) p = p->link[0];
302 else if (diff > 0) p = p->link[1];
303 else return p->data;
304 }
305
306 return NULL;
307 }
308
309 /* Search TREE for an item close to the value of ITEM, and return it.
310 This function will return a null pointer only if TREE is empty. */
311 void *avl_find_close(const avl_tree_t * tree, const void *item)
312 {
313 const avl_node_t *p;
314
315 p = tree->root.link[0];
316 if (p == NULL) return NULL;
317
318 for (;;) {
319 int diff = tree->cmp(item, p->data, tree->param);
320 int t;
321
322 if (diff < 0) t = 0;
323 else if (diff > 0) t = 1;
324 else return p->data;
325
326 if (p->link[t]) p = p->link[t];
327 else return p->data;
328 }
329 }
330
331 /* Searches AVL tree TREE for an item matching ITEM. If found, the
332 item is removed from the tree and the actual item found is returned
333 to the caller. If no item matching ITEM exists in the tree,
334 returns NULL. */
335 void *avl_delete(avl_tree_t * tree, const void *item)
336 {
337 /* Uses my Algorithm D, which can be found at
338 http://www.msu.edu/user/pfaffben/avl. Algorithm D is based on
339 Knuth's Algorithm 6.2.2D (Tree deletion) and 6.2.3A (Balanced
340 tree search and insertion), as well as the notes on pages 465-466
341 of Vol. 3. */
342
343 /* D1. */
344 avl_node_t *pa[AVL_MAX_HEIGHT]; /* Stack P: Nodes. */
345 char a[AVL_MAX_HEIGHT]; /* Stack P: Bits. */
346 int k = 1; /* Stack P: Pointer. */
347
348 avl_node_t **q;
349 avl_node_t *p;
350
351 a[0] = 0;
352 pa[0] = &tree->root;
353 p = tree->root.link[0];
354 for (;;) {
355 /* D2. */
356 int diff;
357
358 if (p == NULL) return NULL;
359
360 diff = tree->cmp(item, p->data, tree->param);
361 if (diff == 0) break;
362
363 /* D3, D4. */
364 pa[k] = p;
365 if (diff < 0) {
366 p = p->link[0];
367 a[k] = 0;
368 }
369 else if (diff > 0) {
370 p = p->link[1];
371 a[k] = 1;
372 }
373 k++;
374 }
375 tree->count--;
376
377 item = p->data;
378
379 /* D5. */
380 q = &pa[k - 1]->link[(int)a[k - 1]];
381 if (p->link[1] == NULL) {
382 *q = p->link[0];
383 if (*q) (*q)->bal = 0;
384 }
385 else {
386 /* D6. */
387 avl_node_t *r = p->link[1];
388 if (r->link[0] == NULL) {
389 r->link[0] = p->link[0];
390 *q = r;
391 r->bal = p->bal;
392 a[k] = 1;
393 pa[k++] = r;
394 }
395 else {
396 /* D7. */
397 avl_node_t *s = r->link[0];
398 int l = k++;
399
400 a[k] = 0;
401 pa[k++] = r;
402
403 /* D8. */
404 while (s->link[0] != NULL) {
405 r = s;
406 s = r->link[0];
407 a[k] = 0;
408 pa[k++] = r;
409 }
410
411 /* D9. */
412 a[l] = 1;
413 pa[l] = s;
414 s->link[0] = p->link[0];
415 r->link[0] = s->link[1];
416 s->link[1] = p->link[1];
417 s->bal = p->bal;
418 *q = s;
419 }
420 }
421
422 mempool_free_chunk(avl_node_mempool, p);
423
424 /* D10. */
425 while (--k) {
426 avl_node_t *s = pa[k], *r;
427
428 if (a[k] == 0) {
429 /* D10. */
430 if (s->bal == -1) {
431 s->bal = 0;
432 continue;
433 }
434 else if (s->bal == 0) {
435 s->bal = 1;
436 break;
437 }
438
439 r = s->link[1];
440
441 if (r->bal == 0) {
442 /* D11. */
443 s->link[1] = r->link[0];
444 r->link[0] = s;
445 r->bal = -1;
446 pa[k - 1]->link[(int)a[k - 1]] = r;
447 break;
448 }
449 else if (r->bal == +1) {
450 /* D12. */
451 s->link[1] = r->link[0];
452 r->link[0] = s;
453 s->bal = r->bal = 0;
454 pa[k - 1]->link[(int)a[k - 1]] = r;
455 }
456 else {
457 /* D13. */
458 p = r->link[0];
459 r->link[0] = p->link[1];
460 p->link[1] = r;
461 s->link[1] = p->link[0];
462 p->link[0] = s;
463 if (p->bal == +1) s->bal = -1, r->bal = 0;
464 else if (p->bal == 0) s->bal = r->bal = 0;
465 else s->bal = 0, r->bal = +1;
466 p->bal = 0;
467 pa[k - 1]->link[(int)a[k - 1]] = p;
468 }
469 }
470 else {
471
472 /* D10. */
473 if (s->bal == +1) {
474 s->bal = 0;
475 continue;
476 }
477 else if (s->bal == 0) {
478 s->bal = -1;
479 break;
480 }
481
482 r = s->link[0];
483
484 if (r == NULL || r->bal == 0) {
485 /* D11. */
486 s->link[0] = r->link[1];
487 r->link[1] = s;
488 r->bal = 1;
489 pa[k - 1]->link[(int)a[k - 1]] = r;
490 break;
491 }
492 else if (r->bal == -1) {
493 /* D12. */
494 s->link[0] = r->link[1];
495 r->link[1] = s;
496 s->bal = r->bal = 0;
497 pa[k - 1]->link[(int)a[k - 1]] = r;
498 }
499 else if (r->bal == +1) {
500 /* D13. */
501 p = r->link[1];
502 r->link[1] = p->link[0];
503 p->link[0] = r;
504 s->link[0] = p->link[1];
505 p->link[1] = s;
506 if (p->bal == -1) s->bal = 1, r->bal = 0;
507 else if (p->bal == 0) s->bal = r->bal = 0;
508 else s->bal = 0, r->bal = -1;
509 p->bal = 0;
510 pa[k - 1]->link[(int)a[k - 1]] = p;
511 }
512 }
513 }
514
515 return (void *)item;
516 }
517
518 /* Inserts ITEM into TREE. Returns NULL if the item was inserted,
519 otherwise a pointer to the duplicate item. */
520 void *avl_insert(avl_tree_t * tree, void *item)
521 {
522 void **p;
523
524 p = avl_probe(tree, item);
525 return (*p == item) ? NULL : *p;
526 }
527
528 /* If ITEM does not exist in TREE, inserts it and returns NULL. If a
529 matching item does exist, it is replaced by ITEM and the item
530 replaced is returned. The caller is responsible for freeing the
531 item returned. */
532 void *avl_replace(avl_tree_t * tree, void *item)
533 {
534 void **p;
535
536 p = avl_probe(tree, item);
537 if (*p == item) return NULL;
538 else {
539 void *r = *p;
540 *p = item;
541 return r;
542 }
543 }

webmaster@eggheads.org
ViewVC Help
Powered by ViewVC 1.1.23