Change to the linux kernel coding style
[wmaker-crm.git] / WINGs / bagtree.c
bloba37c2d48b0c97acc39afb9dddf771830300630fc
2 #include <stdlib.h>
3 #include <string.h>
5 #include "WUtil.h"
7 typedef struct W_Node {
8 struct W_Node *parent;
9 struct W_Node *left;
10 struct W_Node *right;
11 int color;
13 void *data;
14 int index;
15 } W_Node;
17 typedef struct W_Bag {
18 W_Node *root;
20 W_Node *nil; /* sentinel */
22 int count;
24 void (*destructor) (void *item);
25 } W_Bag;
27 #define IS_LEFT(node) (node == node->parent->left)
28 #define IS_RIGHT(node) (node == node->parent->right)
30 static void leftRotate(W_Bag * tree, W_Node * node)
31 {
32 W_Node *node2;
34 node2 = node->right;
35 node->right = node2->left;
37 node2->left->parent = node;
39 node2->parent = node->parent;
41 if (node->parent == tree->nil) {
42 tree->root = node2;
43 } else {
44 if (IS_LEFT(node)) {
45 node->parent->left = node2;
46 } else {
47 node->parent->right = node2;
48 }
49 }
50 node2->left = node;
51 node->parent = node2;
52 }
54 static void rightRotate(W_Bag * tree, W_Node * node)
55 {
56 W_Node *node2;
58 node2 = node->left;
59 node->left = node2->right;
61 node2->right->parent = node;
63 node2->parent = node->parent;
65 if (node->parent == tree->nil) {
66 tree->root = node2;
67 } else {
68 if (IS_LEFT(node)) {
69 node->parent->left = node2;
70 } else {
71 node->parent->right = node2;
72 }
73 }
74 node2->right = node;
75 node->parent = node2;
76 }
78 static void treeInsert(W_Bag * tree, W_Node * node)
79 {
80 W_Node *y = tree->nil;
81 W_Node *x = tree->root;
83 while (x != tree->nil) {
84 y = x;
85 if (node->index <= x->index)
86 x = x->left;
87 else
88 x = x->right;
89 }
90 node->parent = y;
91 if (y == tree->nil)
92 tree->root = node;
93 else if (node->index <= y->index)
94 y->left = node;
95 else
96 y->right = node;
97 }
99 static void rbTreeInsert(W_Bag * tree, W_Node * node)
101 W_Node *y;
103 treeInsert(tree, node);
105 node->color = 'R';
107 while (node != tree->root && node->parent->color == 'R') {
108 if (IS_LEFT(node->parent)) {
109 y = node->parent->parent->right;
111 if (y->color == 'R') {
113 node->parent->color = 'B';
114 y->color = 'B';
115 node->parent->parent->color = 'R';
116 node = node->parent->parent;
118 } else {
119 if (IS_RIGHT(node)) {
120 node = node->parent;
121 leftRotate(tree, node);
123 node->parent->color = 'B';
124 node->parent->parent->color = 'R';
125 rightRotate(tree, node->parent->parent);
127 } else {
128 y = node->parent->parent->left;
130 if (y->color == 'R') {
132 node->parent->color = 'B';
133 y->color = 'B';
134 node->parent->parent->color = 'R';
135 node = node->parent->parent;
137 } else {
138 if (IS_LEFT(node)) {
139 node = node->parent;
140 rightRotate(tree, node);
142 node->parent->color = 'B';
143 node->parent->parent->color = 'R';
144 leftRotate(tree, node->parent->parent);
148 tree->root->color = 'B';
151 static void rbDeleteFixup(W_Bag * tree, W_Node * node)
153 W_Node *w;
155 while (node != tree->root && node->color == 'B') {
156 if (IS_LEFT(node)) {
157 w = node->parent->right;
158 if (w->color == 'R') {
159 w->color = 'B';
160 node->parent->color = 'R';
161 leftRotate(tree, node->parent);
162 w = node->parent->right;
164 if (w->left->color == 'B' && w->right->color == 'B') {
165 w->color = 'R';
166 node = node->parent;
167 } else {
168 if (w->right->color == 'B') {
169 w->left->color = 'B';
170 w->color = 'R';
171 rightRotate(tree, w);
172 w = node->parent->right;
174 w->color = node->parent->color;
175 node->parent->color = 'B';
176 w->right->color = 'B';
177 leftRotate(tree, node->parent);
178 node = tree->root;
180 } else {
181 w = node->parent->left;
182 if (w->color == 'R') {
183 w->color = 'B';
184 node->parent->color = 'R';
185 rightRotate(tree, node->parent);
186 w = node->parent->left;
188 if (w->left->color == 'B' && w->right->color == 'B') {
189 w->color = 'R';
190 node = node->parent;
191 } else {
192 if (w->left->color == 'B') {
193 w->right->color = 'B';
194 w->color = 'R';
195 leftRotate(tree, w);
196 w = node->parent->left;
198 w->color = node->parent->color;
199 node->parent->color = 'B';
200 w->left->color = 'B';
201 rightRotate(tree, node->parent);
202 node = tree->root;
206 node->color = 'B';
210 static W_Node *treeMinimum(W_Node * node, W_Node * nil)
212 while (node->left != nil)
213 node = node->left;
214 return node;
217 static W_Node *treeMaximum(W_Node * node, W_Node * nil)
219 while (node->right != nil)
220 node = node->right;
221 return node;
224 static W_Node *treeSuccessor(W_Node * node, W_Node * nil)
226 W_Node *y;
228 if (node->right != nil) {
229 return treeMinimum(node->right, nil);
231 y = node->parent;
232 while (y != nil && node == y->right) {
233 node = y;
234 y = y->parent;
236 return y;
239 static W_Node *treePredecessor(W_Node * node, W_Node * nil)
241 W_Node *y;
243 if (node->left != nil) {
244 return treeMaximum(node->left, nil);
246 y = node->parent;
247 while (y != nil && node == y->left) {
248 node = y;
249 y = y->parent;
251 return y;
254 static W_Node *rbTreeDelete(W_Bag * tree, W_Node * node)
256 W_Node *nil = tree->nil;
257 W_Node *x, *y;
259 if (node->left == nil || node->right == nil) {
260 y = node;
261 } else {
262 y = treeSuccessor(node, nil);
265 if (y->left != nil) {
266 x = y->left;
267 } else {
268 x = y->right;
271 x->parent = y->parent;
273 if (y->parent == nil) {
274 tree->root = x;
275 } else {
276 if (IS_LEFT(y)) {
277 y->parent->left = x;
278 } else {
279 y->parent->right = x;
282 if (y != node) {
283 node->index = y->index;
284 node->data = y->data;
286 if (y->color == 'B') {
287 rbDeleteFixup(tree, x);
290 return y;
293 static W_Node *treeSearch(W_Node * root, W_Node * nil, int index)
295 if (root == nil || root->index == index) {
296 return root;
299 if (index < root->index) {
300 return treeSearch(root->left, nil, index);
301 } else {
302 return treeSearch(root->right, nil, index);
306 static W_Node *treeFind(W_Node * root, W_Node * nil, void *data)
308 W_Node *tmp;
310 if (root == nil || root->data == data)
311 return root;
313 tmp = treeFind(root->left, nil, data);
314 if (tmp != nil)
315 return tmp;
317 tmp = treeFind(root->right, nil, data);
319 return tmp;
322 #if 0
323 static char buf[512];
325 static void printNodes(W_Node * node, W_Node * nil, int depth)
327 if (node == nil) {
328 return;
331 printNodes(node->left, nil, depth + 1);
333 memset(buf, ' ', depth * 2);
334 buf[depth * 2] = 0;
335 if (IS_LEFT(node))
336 printf("%s/(%2i\n", buf, node->index);
337 else
338 printf("%s\\(%2i\n", buf, node->index);
340 printNodes(node->right, nil, depth + 1);
343 void PrintTree(WMBag * bag)
345 W_TreeBag *tree = (W_TreeBag *) bag->data;
347 printNodes(tree->root, tree->nil, 0);
349 #endif
351 WMBag *WMCreateTreeBag(void)
353 return WMCreateTreeBagWithDestructor(NULL);
356 WMBag *WMCreateTreeBagWithDestructor(WMFreeDataProc * destructor)
358 WMBag *bag;
360 bag = wmalloc(sizeof(WMBag));
362 memset(bag, 0, sizeof(WMBag));
364 bag->nil = wmalloc(sizeof(W_Node));
365 memset(bag->nil, 0, sizeof(W_Node));
366 bag->nil->left = bag->nil->right = bag->nil->parent = bag->nil;
367 bag->nil->index = WBNotFound;
369 bag->root = bag->nil;
371 bag->destructor = destructor;
373 return bag;
376 int WMGetBagItemCount(WMBag * self)
378 return self->count;
381 void WMAppendBag(WMBag * self, WMBag * bag)
383 WMBagIterator ptr;
384 void *data;
386 for (data = WMBagFirst(bag, &ptr); data != NULL; data = WMBagNext(bag, &ptr)) {
387 WMPutInBag(self, data);
391 void WMPutInBag(WMBag * self, void *item)
393 W_Node *ptr;
395 ptr = wmalloc(sizeof(W_Node));
397 ptr->data = item;
398 ptr->index = self->count;
399 ptr->left = self->nil;
400 ptr->right = self->nil;
401 ptr->parent = self->nil;
403 rbTreeInsert(self, ptr);
405 self->count++;
408 void WMInsertInBag(WMBag * self, int index, void *item)
410 W_Node *ptr;
412 ptr = wmalloc(sizeof(W_Node));
414 ptr->data = item;
415 ptr->index = index;
416 ptr->left = self->nil;
417 ptr->right = self->nil;
418 ptr->parent = self->nil;
420 rbTreeInsert(self, ptr);
422 while ((ptr = treeSuccessor(ptr, self->nil)) != self->nil) {
423 ptr->index++;
426 self->count++;
429 int WMRemoveFromBag(WMBag * self, void *item)
431 W_Node *ptr = treeFind(self->root, self->nil, item);
433 if (ptr != self->nil) {
434 W_Node *tmp;
436 self->count--;
438 tmp = treeSuccessor(ptr, self->nil);
439 while (tmp != self->nil) {
440 tmp->index--;
441 tmp = treeSuccessor(tmp, self->nil);
444 ptr = rbTreeDelete(self, ptr);
445 if (self->destructor)
446 self->destructor(ptr->data);
447 wfree(ptr);
449 return 1;
450 } else {
451 return 0;
455 int WMEraseFromBag(WMBag * self, int index)
457 W_Node *ptr = treeSearch(self->root, self->nil, index);
459 if (ptr != self->nil) {
461 self->count--;
463 ptr = rbTreeDelete(self, ptr);
464 if (self->destructor)
465 self->destructor(ptr->data);
466 wfree(ptr);
468 wassertrv(self->count == 0 || self->root->index >= 0, 1);
470 return 1;
471 } else {
472 return 0;
476 int WMDeleteFromBag(WMBag * self, int index)
478 W_Node *ptr = treeSearch(self->root, self->nil, index);
480 if (ptr != self->nil) {
481 W_Node *tmp;
483 self->count--;
485 tmp = treeSuccessor(ptr, self->nil);
486 while (tmp != self->nil) {
487 tmp->index--;
488 tmp = treeSuccessor(tmp, self->nil);
491 ptr = rbTreeDelete(self, ptr);
492 if (self->destructor)
493 self->destructor(ptr->data);
494 wfree(ptr);
496 wassertrv(self->count == 0 || self->root->index >= 0, 1);
498 return 1;
499 } else {
500 return 0;
504 void *WMGetFromBag(WMBag * self, int index)
506 W_Node *node;
508 node = treeSearch(self->root, self->nil, index);
509 if (node != self->nil)
510 return node->data;
511 else
512 return NULL;
515 int WMGetFirstInBag(WMBag * self, void *item)
517 W_Node *node;
519 node = treeFind(self->root, self->nil, item);
520 if (node != self->nil)
521 return node->index;
522 else
523 return WBNotFound;
526 static int treeCount(W_Node * root, W_Node * nil, void *item)
528 int count = 0;
530 if (root == nil)
531 return 0;
533 if (root->data == item)
534 count++;
536 if (root->left != nil)
537 count += treeCount(root->left, nil, item);
539 if (root->right != nil)
540 count += treeCount(root->right, nil, item);
542 return count;
545 int WMCountInBag(WMBag * self, void *item)
547 return treeCount(self->root, self->nil, item);
550 void *WMReplaceInBag(WMBag * self, int index, void *item)
552 W_Node *ptr = treeSearch(self->root, self->nil, index);
553 void *old = NULL;
555 if (item == NULL) {
556 self->count--;
557 ptr = rbTreeDelete(self, ptr);
558 if (self->destructor)
559 self->destructor(ptr->data);
560 wfree(ptr);
561 } else if (ptr != self->nil) {
562 old = ptr->data;
563 ptr->data = item;
564 } else {
565 W_Node *ptr;
567 ptr = wmalloc(sizeof(W_Node));
569 ptr->data = item;
570 ptr->index = index;
571 ptr->left = self->nil;
572 ptr->right = self->nil;
573 ptr->parent = self->nil;
575 rbTreeInsert(self, ptr);
577 self->count++;
580 return old;
583 void WMSortBag(WMBag * self, WMCompareDataProc * comparer)
585 void **items;
586 W_Node *tmp;
587 int i;
589 if (self->count == 0)
590 return;
592 items = wmalloc(sizeof(void *) * self->count);
593 i = 0;
595 tmp = treeMinimum(self->root, self->nil);
596 while (tmp != self->nil) {
597 items[i++] = tmp->data;
598 tmp = treeSuccessor(tmp, self->nil);
601 qsort(&items[0], self->count, sizeof(void *), comparer);
603 i = 0;
604 tmp = treeMinimum(self->root, self->nil);
605 while (tmp != self->nil) {
606 tmp->index = i;
607 tmp->data = items[i++];
608 tmp = treeSuccessor(tmp, self->nil);
611 wfree(items);
614 static void deleteTree(WMBag * self, W_Node * node)
616 if (node == self->nil)
617 return;
619 deleteTree(self, node->left);
621 if (self->destructor)
622 self->destructor(node->data);
624 deleteTree(self, node->right);
626 wfree(node);
629 void WMEmptyBag(WMBag * self)
631 deleteTree(self, self->root);
632 self->root = self->nil;
633 self->count = 0;
636 void WMFreeBag(WMBag * self)
638 WMEmptyBag(self);
639 wfree(self->nil);
640 wfree(self);
643 static void mapTree(W_Bag * tree, W_Node * node, void (*function) (void *, void *), void *data)
645 if (node == tree->nil)
646 return;
648 mapTree(tree, node->left, function, data);
650 (*function) (node->data, data);
652 mapTree(tree, node->right, function, data);
655 void WMMapBag(WMBag * self, void (*function) (void *, void *), void *data)
657 mapTree(self, self->root, function, data);
660 static int findInTree(W_Bag * tree, W_Node * node, WMMatchDataProc * function, void *cdata)
662 int index;
664 if (node == tree->nil)
665 return WBNotFound;
667 index = findInTree(tree, node->left, function, cdata);
668 if (index != WBNotFound)
669 return index;
671 if ((*function) (node->data, cdata)) {
672 return node->index;
675 return findInTree(tree, node->right, function, cdata);
678 int WMFindInBag(WMBag * self, WMMatchDataProc * match, void *cdata)
680 return findInTree(self, self->root, match, cdata);
683 void *WMBagFirst(WMBag * self, WMBagIterator * ptr)
685 W_Node *node;
687 node = treeMinimum(self->root, self->nil);
689 if (node == self->nil) {
690 *ptr = NULL;
691 return NULL;
692 } else {
693 *ptr = node;
694 return node->data;
698 void *WMBagLast(WMBag * self, WMBagIterator * ptr)
701 W_Node *node;
703 node = treeMaximum(self->root, self->nil);
705 if (node == self->nil) {
706 *ptr = NULL;
707 return NULL;
708 } else {
709 *ptr = node;
710 return node->data;
714 void *WMBagNext(WMBag * self, WMBagIterator * ptr)
716 W_Node *node;
718 if (*ptr == NULL)
719 return NULL;
721 node = treeSuccessor(*ptr, self->nil);
723 if (node == self->nil) {
724 *ptr = NULL;
725 return NULL;
726 } else {
727 *ptr = node;
728 return node->data;
732 void *WMBagPrevious(WMBag * self, WMBagIterator * ptr)
734 W_Node *node;
736 if (*ptr == NULL)
737 return NULL;
739 node = treePredecessor(*ptr, self->nil);
741 if (node == self->nil) {
742 *ptr = NULL;
743 return NULL;
744 } else {
745 *ptr = node;
746 return node->data;
750 void *WMBagIteratorAtIndex(WMBag * self, int index, WMBagIterator * ptr)
752 W_Node *node;
754 node = treeSearch(self->root, self->nil, index);
756 if (node == self->nil) {
757 *ptr = NULL;
758 return NULL;
759 } else {
760 *ptr = node;
761 return node->data;
765 int WMBagIndexForIterator(WMBag * bag, WMBagIterator ptr)
767 return ((W_Node *) ptr)->index;