DialogF.c- DialogF.h
- Makefile.common
- Makefile.dependencies
- check_lin_tif
- clearcase.c
- clearcase.h
- colorchooser.c
- colorchooser.h
- dragAndDrop.c
- dragAndDrop.h
- ec_glob.c
- ec_glob.h
- fileUtils.c
- fileUtils.h
- filedialog.c
- filedialog.h
- fontsel.c
- fontsel.h
- getfiles.c
- getfiles.h
- libxattr.c
- libxattr.h
- managedList.c
- managedList.h
- misc.c
- misc.h
- motif.c
- motif.h
- nedit_malloc.c
- nedit_malloc.h
- pathutils.c
- pathutils.h
- prefFile.c
- prefFile.h
- printUtils.c
- printUtils.h
- rbTree.c
- rbTree.h
- refString.c
- refString.h
- system.h
- textfield.c
- textfield.h
- textfieldP.h
- utils.c
- utils.h
- xdnd.c
- xdnd.h
1 /*******************************************************************************
2 * *
3 * rbTree.c -- Nirvana editor red-black balanced binary tree *
4 * *
5 * Copyright (C) 2001 Mark Edel *
6 * *
7 * This is free software; you can redistribute it and/or modify it under the *
8 * terms of the GNU General Public License as published by the Free Software *
9 * Foundation; either version 2 of the License, or (at your option) any later *
10 * version. *
11 * *
12 * This software is distributed in the hope that it will be useful, but WITHOUT *
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or *
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License *
15 * for more details. *
16 * *
17 * You should have received a copy of the GNU General Public License along with *
18 * software; if not, write to the Free Software Foundation, Inc., 59 Temple *
19 * Place, Suite 330, Boston, MA 02111-1307 USA *
20 * *
21 * Nirvana Text Editor *
22 * July, 1993 *
23 * *
24 * Written by Mark Edel *
25 * *
26 *******************************************************************************/
27
28 /*
29 ** rbTree is a red-black balanced binary tree
30 ** the base node holds the leftmost, rightmost and root pointers
31 ** and a node count
32 */
33
34 #ifdef HAVE_CONFIG_H
35 #include "../config.h"
36 #endif
37
38 #include "rbTree.h"
39 #include "../util/nedit_malloc.h"
40
41 #include <stdlib.h>
42 #include <string.h>
43 /*#define RBTREE_TEST_CODE*/
44 #ifdef RBTREE_TEST_CODE
45 #include <stdio.h>
46 #endif
47
48 #ifdef HAVE_DEBUG_H
49 #include "../debug.h"
50 #endif
51
52
53 #define rbTreeNodeRed 0
54 #define rbTreeNodeBlack 1
55
56 /*
57 ** rotate a node left
58 */
59 static void rotateLeft(rbTreeNode *x, rbTreeNode **root)
60 {
61 rbTreeNode *y = x->right;
62 x->right = y->left;
63 if (y->left != NULL) {
64 y->left->parent = x;
65 }
66 y->parent = x->parent;
67
68 if (x == *root) {
69 *root = y;
70 }
71 else if (x == x->parent->left) {
72 x->parent->left = y;
73 }
74 else {
75 x->parent->right = y;
76 }
77 y->left = x;
78 x->parent = y;
79 }
80
81 /*
82 ** rotate a node right
83 */
84 static void rotateRight(rbTreeNode *x, rbTreeNode **root)
85 {
86 rbTreeNode *y = x->left;
87 x->left = y->right;
88 if (y->right != NULL) {
89 y->right->parent = x;
90 }
91 y->parent = x->parent;
92
93 if (x == *root) {
94 *root = y;
95 }
96 else if (x == x->parent->right) {
97 x->parent->right = y;
98 }
99 else {
100 x->parent->left = y;
101 }
102 y->right = x;
103 x->parent = y;
104 }
105
106 /*
107 ** balance tree after an insert of node x
108 */
109 static void insertBalance(rbTreeNode *x, rbTreeNode **root)
110 {
111 x->color = rbTreeNodeRed;
112 while (x != *root && x->parent->color == rbTreeNodeRed) {
113 if (x->parent == x->parent->parent->left) {
114 rbTreeNode *y = x->parent->parent->right;
115 if (y && y->color == rbTreeNodeRed) {
116 x->parent->color = rbTreeNodeBlack;
117 y->color = rbTreeNodeBlack;
118 x->parent->parent->color = rbTreeNodeRed;
119 x = x->parent->parent;
120 }
121 else {
122 if (x == x->parent->right) {
123 x = x->parent;
124 rotateLeft(x, root);
125 }
126 x->parent->color = rbTreeNodeBlack;
127 x->parent->parent->color = rbTreeNodeRed;
128 rotateRight(x->parent->parent, root);
129 }
130 }
131 else {
132 rbTreeNode *y = x->parent->parent->left;
133 if (y && y->color == rbTreeNodeRed) {
134 x->parent->color = rbTreeNodeBlack;
135 y->color = rbTreeNodeBlack;
136 x->parent->parent->color = rbTreeNodeRed;
137 x = x->parent->parent;
138 }
139 else {
140 if (x == x->parent->left) {
141 x = x->parent;
142 rotateRight(x, root);
143 }
144 x->parent->color = rbTreeNodeBlack;
145 x->parent->parent->color = rbTreeNodeRed;
146 rotateLeft(x->parent->parent, root);
147 }
148 }
149 }
150 (*root)->color = rbTreeNodeBlack;
151 }
152
153 /*
154 ** returns the leftmost node (the beginning of the sorted list)
155 */
156 rbTreeNode *rbTreeBegin(rbTreeNode *base)
157 {
158 return(base->left);
159 }
160
161 /*
162 ** returns the rightmost node (the end of the sorted list)
163 */
164 rbTreeNode *rbTreeReverseBegin(rbTreeNode *base)
165 {
166 return(base->right);
167 }
168
169 /*
170 ** search for a node and return it's pointer, NULL if not found
171 */
172 rbTreeNode *rbTreeFind(rbTreeNode *base, rbTreeNode *searchNode,
173 rbTreeCompareNodeCB compareRecords)
174 {
175 rbTreeNode *foundNode = NULL;
176 rbTreeNode *current = base->parent;
177 while(current != NULL) {
178 int compareResult = compareRecords(searchNode, current);
179
180 if (compareResult < 0) {
181 current = current->left;
182 }
183 else if (compareResult > 0) {
184 current = current->right;
185 }
186 else {
187 foundNode = current;
188 current = NULL;
189 }
190 }
191 return(foundNode);
192 }
193
194 /*
195 ** insert a node into the tree and rebalance it
196 ** if a duplicate is found copy the new data over it
197 ** returns the new node
198 */
199 rbTreeNode *rbTreeInsert(rbTreeNode *base, rbTreeNode *searchNode,
200 rbTreeCompareNodeCB compareRecords,
201 rbTreeAllocateNodeCB allocateNode,
202 rbTreeCopyToNodeCB copyToNode)
203 {
204 rbTreeNode *current, *parent, *x;
205 int fromLeft = 0, foundMatch = 0;
206
207 current = base->parent;
208 parent = NULL;
209 x = NULL;
210 while(current != NULL) {
211 int compareResult = compareRecords(searchNode, current);
212
213 if (compareResult < 0) {
214 parent = current;
215 current = current->left;
216 fromLeft = 1;
217 }
218 else if (compareResult > 0) {
219 parent = current;
220 current = current->right;
221 fromLeft = 0;
222 }
223 else {
224 x = current;
225 if (!copyToNode(x, searchNode)) {
226 x = NULL;
227 }
228 current = NULL;
229 foundMatch = 1;
230 }
231 }
232
233 if (!foundMatch) {
234 x = allocateNode(searchNode);
235 if (x) {
236 x->parent = parent;
237 x->left = NULL;
238 x->right = NULL;
239 x->color = rbTreeNodeRed;
240
241 if (parent) {
242 if (fromLeft) {
243 parent->left = x;
244 }
245 else {
246 parent->right = x;
247 }
248 }
249 else {
250 base->parent = x;
251 }
252 ++(base->color);
253 if (x->parent == base->left && (x->parent == NULL || x->parent->left == x)) {
254 base->left = x;
255 }
256 if (x->parent == base->right && (x->parent == NULL || x->parent->right == x)) {
257 base->right = x;
258 }
259 insertBalance(x, &base->parent);
260 }
261 }
262 return(x);
263 }
264
265 /*
266 ** unlink a node from the tree and rebalance it.
267 ** returns the removed node pointer
268 */
269 rbTreeNode *rbTreeUnlinkNode(rbTreeNode *base, rbTreeNode *z)
270 {
271 int swapColor;
272 rbTreeNode *x, *y, *x_parent;
273
274 y = z;
275 if (y->left == NULL) {
276 x = y->right;
277 if (y == base->left) {
278 base->left = rbTreeNext(y);
279 }
280 }
281 else {
282 if (y->right == NULL) {
283 x = y->left;
284 if (y == base->right) {
285 base->right = rbTreePrevious(y);
286 }
287 }
288 else {
289 y = y->right;
290 while (y->left != NULL) {
291 y = y->left;
292 }
293 x = y->right;
294 }
295 }
296 if (y != z) {
297 z->left->parent = y;
298 y->left = z->left;
299 if (y != z->right) {
300 x_parent = y->parent;
301 if (x != NULL) {
302 x->parent = y->parent;
303 }
304 y->parent->left = x;
305 y->right = z->right;
306 z->right->parent = y;
307 }
308 else {
309 x_parent = y;
310 }
311 if (base->parent == z) {
312 base->parent = y;
313 }
314 else if (z->parent->left == z) {
315 z->parent->left = y;
316 }
317 else {
318 z->parent->right = y;
319 }
320 y->parent = z->parent;
321
322 swapColor = y->color;
323 y->color = z->color;
324 z->color = swapColor;
325
326 y = z;
327 }
328 else {
329 x_parent = y->parent;
330 if (x != NULL) {
331 x->parent = y->parent;
332 }
333 if (base->parent == z) {
334 base->parent = x;
335 }
336 else {
337 if (z->parent->left == z) {
338 z->parent->left = x;
339 }
340 else {
341 z->parent->right = x;
342 }
343 }
344 }
345
346 --(base->color);
347
348 if (y->color != rbTreeNodeRed) {
349 while (x != base->parent && (x == NULL || x->color == rbTreeNodeBlack)) {
350 if (x == x_parent->left) {
351 rbTreeNode *w = x_parent->right;
352 if (w->color == rbTreeNodeRed) {
353 w->color = rbTreeNodeBlack;
354 x_parent->color = rbTreeNodeRed;
355 rotateLeft(x_parent, &base->parent);
356 w = x_parent->right;
357 }
358 if ((w->left == NULL ||
359 w->left->color == rbTreeNodeBlack) &&
360 (w->right == NULL ||
361 w->right->color == rbTreeNodeBlack)) {
362
363 w->color = rbTreeNodeRed;
364 x = x_parent;
365 x_parent = x_parent->parent;
366 } else {
367 if (w->right == NULL ||
368 w->right->color == rbTreeNodeBlack) {
369
370 if (w->left) {
371 w->left->color = rbTreeNodeBlack;
372 }
373 w->color = rbTreeNodeRed;
374 rotateRight(w, &base->parent);
375 w = x_parent->right;
376 }
377 w->color = x_parent->color;
378 x_parent->color = rbTreeNodeBlack;
379 if (w->right) {
380 w->right->color = rbTreeNodeBlack;
381 }
382 rotateLeft(x_parent, &base->parent);
383 break;
384 }
385 }
386 else {
387 rbTreeNode *w = x_parent->left;
388 if (w->color == rbTreeNodeRed) {
389 w->color = rbTreeNodeBlack;
390 x_parent->color = rbTreeNodeRed;
391 rotateRight(x_parent, &base->parent);
392 w = x_parent->left;
393 }
394 if ((w->right == NULL ||
395 w->right->color == rbTreeNodeBlack) &&
396 (w->left == NULL ||
397 w->left->color == rbTreeNodeBlack)) {
398
399 w->color = rbTreeNodeRed;
400 x = x_parent;
401 x_parent = x_parent->parent;
402 }
403 else {
404 if (w->left == NULL ||
405 w->left->color == rbTreeNodeBlack) {
406
407 if (w->right) {
408 w->right->color = rbTreeNodeBlack;
409 }
410 w->color = rbTreeNodeRed;
411 rotateLeft(w, &base->parent);
412 w = x_parent->left;
413 }
414 w->color = x_parent->color;
415 x_parent->color = rbTreeNodeBlack;
416 if (w->left) {
417 w->left->color = rbTreeNodeBlack;
418 }
419 rotateRight(x_parent, &base->parent);
420 break;
421 }
422 }
423 }
424 if (x) {
425 x->color = rbTreeNodeBlack;
426 }
427 }
428 return(y);
429 }
430
431 /*
432 ** delete an already found node and dispose it
433 */
434 void rbTreeDeleteNode(rbTreeNode *base, rbTreeNode *foundNode,
435 rbTreeDisposeNodeCB disposeNode)
436 {
437 disposeNode(rbTreeUnlinkNode(base, foundNode));
438 }
439
440 /*
441 ** search for a node and remove it from the tree
442 ** disposing the removed node
443 ** returns 1 if a node was found, otherwise 0
444 */
445 int rbTreeDelete(rbTreeNode *base, rbTreeNode *searchNode,
446 rbTreeCompareNodeCB compareRecords,
447 rbTreeDisposeNodeCB disposeNode)
448 {
449 int foundNode = 0;
450 rbTreeNode *z;
451
452 z = rbTreeFind(base, searchNode, compareRecords);
453 if (z != NULL) {
454 rbTreeDeleteNode(base, z, disposeNode);
455 foundNode = 1;
456 }
457 return(foundNode);
458 }
459
460 /*
461 ** move an iterator foreward one element
462 ** note that a valid pointer must be passed,
463 ** passing NULL will result in unpredictable results
464 */
465 rbTreeNode *rbTreeNext(rbTreeNode *x)
466 {
467 if (x->right != NULL) {
468 x = x->right;
469 while (x->left != NULL) {
470 x = x->left;
471 }
472 }
473 else {
474 rbTreeNode *fromX;
475 do {
476 fromX = x;
477 x = x->parent;
478 } while (x && fromX == x->right);
479 }
480 return(x);
481 }
482
483 /*
484 ** move an iterator back one element
485 ** note that a valid pointer must be passed,
486 ** passing NULL will result in unpredictable results
487 */
488 rbTreeNode *rbTreePrevious(rbTreeNode *x)
489 {
490 if (x->left != NULL) {
491 x = x->left;
492 while (x->right != NULL) {
493 x = x->right;
494 }
495 }
496 else {
497 rbTreeNode *fromX;
498 do {
499 fromX = x;
500 x = x->parent;
501 } while (x && fromX == x->left);
502 }
503 return(x);
504 }
505
506 /*
507 ** returns the number of real data nodes in the tree, not counting
508 ** the base node since it contains no data
509 */
510 int rbTreeSize(rbTreeNode *base)
511 {
512 return(base->color);
513 }
514
515 /*
516 ** Allocate a new red-black tree using an empty node to hold pointers
517 */
518 rbTreeNode *rbTreeNew(rbTreeAllocateEmptyNodeCB allocateEmptyNode)
519 {
520 rbTreeNode *rootStorage = allocateEmptyNode();
521 if (rootStorage) {
522 rootStorage->left = NULL; /* leftmost node */
523 rootStorage->right = NULL; /* rightmost node */
524 rootStorage->parent = NULL; /* root node */
525 rootStorage->color = 0; /* node count */
526 }
527 return(rootStorage);
528 }
529
530 /*
531 ** iterate through all nodes, unlinking and disposing them
532 ** extra effort is made to maintain all links, the size, and
533 ** leftmost/rightmost pointers, so that the tree can be dumped
534 ** when debugging problems. We could probably ifdef some of this
535 ** since it goes unused most of the time
536 ** the tree is not kept balanced since all nodes will be removed
537 */
538 void rbTreeDispose(rbTreeNode *base, rbTreeDisposeNodeCB disposeNode)
539 {
540 rbTreeNode *iter = rbTreeBegin(base);
541 while (iter != NULL) {
542 rbTreeNode *nextIter = rbTreeNext(iter);
543
544 if (iter->parent) {
545 if (iter->parent->left == iter) {
546 iter->parent->left = iter->right;
547 }
548 else {
549 iter->parent->right = iter->right;
550 }
551 }
552 if (iter->right != NULL) {
553 iter->right->parent = iter->parent;
554 }
555 base->left = nextIter;
556 if (base->right == iter) {
557 base->right = NULL;
558 }
559 --(base->color);
560 if (base->parent == iter) {
561 base->parent = nextIter;
562 }
563 disposeNode(iter);
564
565 iter = nextIter;
566 }
567 disposeNode(base);
568 }
569
570 #ifdef RBTREE_TEST_CODE
571 /* ================================================================== */
572
573 /*
574 ** code to test basic stuff of tree routines
575 */
576
577 typedef struct TestNode {
578 rbTreeNode nodePointers; /* MUST BE FIRST MEMBER */
579 char *str;
580 char *key;
581 } TestNode;
582
583
584 static int rbTreeCompareNode_TestNode(rbTreeNode *left, rbTreeNode *right)
585 {
586 return(strcmp(((TestNode *)left)->key, ((TestNode *)right)->key));
587 }
588
589 static rbTreeNode *rbTreeAllocateNode_TestNode(rbTreeNode *src)
590 {
591 TestNode *newNode = NEditMalloc(sizeof(TestNode));
592 if (newNode) {
593 newNode->str = NEditMalloc(strlen(((TestNode *)src)->str) + 1);
594 if (newNode->str) {
595 strcpy(newNode->str, ((TestNode *)src)->str);
596
597 newNode->key = NEditMalloc(strlen(((TestNode *)src)->key) + 1);
598 if (newNode->key) {
599 strcpy(newNode->key, ((TestNode *)src)->key);
600 }
601 else {
602 NEditFree(newNode->str);
603 newNode->str = NULL;
604
605 NEditFree(newNode);
606 newNode = NULL;
607 }
608 }
609 else {
610 NEditFree(newNode);
611 newNode = NULL;
612 }
613 }
614 return((rbTreeNode *)newNode);
615 }
616
617 rbTreeNode *rbTreeAllocateEmptyNodeCB_TestNode(void)
618 {
619 TestNode *newNode = NEditMalloc(sizeof(TestNode));
620 if (newNode) {
621 newNode->str = NULL;
622 newNode->key = NULL;
623 }
624 return((rbTreeNode *)newNode);
625 }
626
627 static void rbTreeDisposeNode_TestNode(rbTreeNode *src)
628 {
629 if (src) {
630 if (((TestNode *)src)->str) {
631 NEditFree(((TestNode *)src)->str);
632 ((TestNode *)src)->str = NULL;
633 }
634 if (((TestNode *)src)->key) {
635 NEditFree(((TestNode *)src)->key);
636 ((TestNode *)src)->key = NULL;
637 }
638 src->left = (void *)-1;
639 src->right = (void *)-1;
640 src->parent = (void *)-1;
641 src->color = rbTreeNodeBlack;
642
643 NEditFree(src);
644 }
645 }
646
647 static int rbTreeCopyToNode_TestNode(rbTreeNode *dst, rbTreeNode *src)
648 {
649 TestNode newValues;
650 int copiedOK = 0;
651
652 newValues.str = NEditMalloc(strlen(((TestNode *)src)->str) + 1);
653 if (newValues.str) {
654 strcpy(newValues.str, ((TestNode *)src)->str);
655
656 newValues.key = NEditMalloc(strlen(((TestNode *)src)->key) + 1);
657 if (newValues.key) {
658 strcpy(newValues.key, ((TestNode *)src)->key);
659
660 ((TestNode *)dst)->str = newValues.str;
661 ((TestNode *)dst)->key = newValues.key;
662 copiedOK = 1;
663 }
664 else {
665 NEditFree(newValues.str);
666 newValues.str = NULL;
667 }
668 }
669 return(copiedOK);
670 }
671
672 static void DumpTree(rbTreeNode *base)
673 {
674 rbTreeNode *newNode;
675
676 newNode = rbTreeBegin(base);
677 while (newNode != NULL) {
678 rbTreeNode *nextNode = rbTreeNext(newNode);
679
680 printf("[%s] = \"%s\"\n", ((TestNode *)newNode)->key, ((TestNode *)newNode)->str);
681 printf("[%x] l[%x] r[%x] p[%x] <%s>\n", (int)newNode, (int)newNode->left, (int)newNode->right, (int)newNode->parent, ((newNode->color == rbTreeNodeBlack)?"Black":"Red"));
682
683 newNode = nextNode;
684 }
685 }
686
687 int main(int argc, char **argv)
688 {
689 rbTreeNode *base, *newNode;
690 TestNode searchNode;
691 char tmpkey[20], tmpValue[40];
692 int i;
693
694 searchNode.key = tmpkey;
695 searchNode.str = tmpValue;
696
697 base = rbTreeNew(rbTreeAllocateEmptyNodeCB_TestNode);
698 if (!base) {
699 printf("Failed New!!!\n");
700 exit(1);
701 }
702 for (i = 0; i < 100; ++i) {
703 sprintf(tmpkey, "%d", i);
704 sprintf(tmpValue, "<%d>", i * i);
705
706 newNode = rbTreeInsert(base, (rbTreeNode *)&searchNode,
707 rbTreeCompareNode_TestNode,
708 rbTreeAllocateNode_TestNode,
709 rbTreeCopyToNode_TestNode);
710 if (!newNode) {
711 printf("Failed!!!\n");
712 exit(1);
713 }
714 }
715
716 newNode = rbTreeBegin(base);
717 while (newNode != NULL) {
718 rbTreeNode *nextNode = rbTreeNext(newNode);
719
720 printf("[%s] = \"%s\"\n", ((TestNode *)newNode)->key, ((TestNode *)newNode)->str);
721
722 if (strlen(((TestNode *)newNode)->str) < 7) {
723 int didDelete;
724
725 printf("Deleting [%s]\n", ((TestNode *)newNode)->key);
726 didDelete = rbTreeDelete(base, newNode,
727 rbTreeCompareNode_TestNode, rbTreeDisposeNode_TestNode);
728 printf("delete result = %d\n", didDelete);
729 }
730
731 newNode = nextNode;
732 }
733
734 printf("Tree Size = %d\n", rbTreeSize(base));
735 printf("\n++++++++++++++++\n");
736 DumpTree(base);
737 printf("\n++++++++++++++++\n");
738
739 rbTreeDispose(base, rbTreeDisposeNode_TestNode);
740
741 printf("\nDone.\n");
742 return(0);
743 }
744 #endif
745