Change to the linux kernel coding style
[wmaker-crm.git] / WINGs / bagtree.c
1
2 #include <stdlib.h>
3 #include <string.h>
4
5 #include "WUtil.h"
6
7 typedef struct W_Node {
8 struct W_Node *parent;
9 struct W_Node *left;
10 struct W_Node *right;
11 int color;
12
13 void *data;
14 int index;
15 } W_Node;
16
17 typedef struct W_Bag {
18 W_Node *root;
19
20 W_Node *nil; /* sentinel */
21
22 int count;
23
24 void (*destructor) (void *item);
25 } W_Bag;
26
27 #define IS_LEFT(node) (node == node->parent->left)
28 #define IS_RIGHT(node) (node == node->parent->right)
29
30 static void leftRotate(W_Bag * tree, W_Node * node)
31 {
32 W_Node *node2;
33
34 node2 = node->right;
35 node->right = node2->left;
36
37 node2->left->parent = node;
38
39 node2->parent = node->parent;
40
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 }
53
54 static void rightRotate(W_Bag * tree, W_Node * node)
55 {
56 W_Node *node2;
57
58 node2 = node->left;
59 node->left = node2->right;
60
61 node2->right->parent = node;
62
63 node2->parent = node->parent;
64
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 }
77
78 static void treeInsert(W_Bag * tree, W_Node * node)
79 {
80 W_Node *y = tree->nil;
81 W_Node *x = tree->root;
82
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 }
98
99 static void rbTreeInsert(W_Bag * tree, W_Node * node)
100 {
101 W_Node *y;
102
103 treeInsert(tree, node);
104
105 node->color = 'R';
106
107 while (node != tree->root && node->parent->color == 'R') {
108 if (IS_LEFT(node->parent)) {
109 y = node->parent->parent->right;
110
111 if (y->color == 'R') {
112
113 node->parent->color = 'B';
114 y->color = 'B';
115 node->parent->parent->color = 'R';
116 node = node->parent->parent;
117
118 } else {
119 if (IS_RIGHT(node)) {
120 node = node->parent;
121 leftRotate(tree, node);
122 }
123 node->parent->color = 'B';
124 node->parent->parent->color = 'R';
125 rightRotate(tree, node->parent->parent);
126 }
127 } else {
128 y = node->parent->parent->left;
129
130 if (y->color == 'R') {
131
132 node->parent->color = 'B';
133 y->color = 'B';
134 node->parent->parent->color = 'R';
135 node = node->parent->parent;
136
137 } else {
138 if (IS_LEFT(node)) {
139 node = node->parent;
140 rightRotate(tree, node);
141 }
142 node->parent->color = 'B';
143 node->parent->parent->color = 'R';
144 leftRotate(tree, node->parent->parent);
145 }
146 }
147 }
148 tree->root->color = 'B';
149 }
150
151 static void rbDeleteFixup(W_Bag * tree, W_Node * node)
152 {
153 W_Node *w;
154
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;
163 }
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;
173 }
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;
179 }
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;
187 }
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;
197 }
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;
203 }
204 }
205 }
206 node->color = 'B';
207
208 }
209
210 static W_Node *treeMinimum(W_Node * node, W_Node * nil)
211 {
212 while (node->left != nil)
213 node = node->left;
214 return node;
215 }
216
217 static W_Node *treeMaximum(W_Node * node, W_Node * nil)
218 {
219 while (node->right != nil)
220 node = node->right;
221 return node;
222 }
223
224 static W_Node *treeSuccessor(W_Node * node, W_Node * nil)
225 {
226 W_Node *y;
227
228 if (node->right != nil) {
229 return treeMinimum(node->right, nil);
230 }
231 y = node->parent;
232 while (y != nil && node == y->right) {
233 node = y;
234 y = y->parent;
235 }
236 return y;
237 }
238
239 static W_Node *treePredecessor(W_Node * node, W_Node * nil)
240 {
241 W_Node *y;
242
243 if (node->left != nil) {
244 return treeMaximum(node->left, nil);
245 }
246 y = node->parent;
247 while (y != nil && node == y->left) {
248 node = y;
249 y = y->parent;
250 }
251 return y;
252 }
253
254 static W_Node *rbTreeDelete(W_Bag * tree, W_Node * node)
255 {
256 W_Node *nil = tree->nil;
257 W_Node *x, *y;
258
259 if (node->left == nil || node->right == nil) {
260 y = node;
261 } else {
262 y = treeSuccessor(node, nil);
263 }
264
265 if (y->left != nil) {
266 x = y->left;
267 } else {
268 x = y->right;
269 }
270
271 x->parent = y->parent;
272
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;
280 }
281 }
282 if (y != node) {
283 node->index = y->index;
284 node->data = y->data;
285 }
286 if (y->color == 'B') {
287 rbDeleteFixup(tree, x);
288 }
289
290 return y;
291 }
292
293 static W_Node *treeSearch(W_Node * root, W_Node * nil, int index)
294 {
295 if (root == nil || root->index == index) {
296 return root;
297 }
298
299 if (index < root->index) {
300 return treeSearch(root->left, nil, index);
301 } else {
302 return treeSearch(root->right, nil, index);
303 }
304 }
305
306 static W_Node *treeFind(W_Node * root, W_Node * nil, void *data)
307 {
308 W_Node *tmp;
309
310 if (root == nil || root->data == data)
311 return root;
312
313 tmp = treeFind(root->left, nil, data);
314 if (tmp != nil)
315 return tmp;
316
317 tmp = treeFind(root->right, nil, data);
318
319 return tmp;
320 }
321
322 #if 0
323 static char buf[512];
324
325 static void printNodes(W_Node * node, W_Node * nil, int depth)
326 {
327 if (node == nil) {
328 return;
329 }
330
331 printNodes(node->left, nil, depth + 1);
332
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);
339
340 printNodes(node->right, nil, depth + 1);
341 }
342
343 void PrintTree(WMBag * bag)
344 {
345 W_TreeBag *tree = (W_TreeBag *) bag->data;
346
347 printNodes(tree->root, tree->nil, 0);
348 }
349 #endif
350
351 WMBag *WMCreateTreeBag(void)
352 {
353 return WMCreateTreeBagWithDestructor(NULL);
354 }
355
356 WMBag *WMCreateTreeBagWithDestructor(WMFreeDataProc * destructor)
357 {
358 WMBag *bag;
359
360 bag = wmalloc(sizeof(WMBag));
361
362 memset(bag, 0, sizeof(WMBag));
363
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;
368
369 bag->root = bag->nil;
370
371 bag->destructor = destructor;
372
373 return bag;
374 }
375
376 int WMGetBagItemCount(WMBag * self)
377 {
378 return self->count;
379 }
380
381 void WMAppendBag(WMBag * self, WMBag * bag)
382 {
383 WMBagIterator ptr;
384 void *data;
385
386 for (data = WMBagFirst(bag, &ptr); data != NULL; data = WMBagNext(bag, &ptr)) {
387 WMPutInBag(self, data);
388 }
389 }
390
391 void WMPutInBag(WMBag * self, void *item)
392 {
393 W_Node *ptr;
394
395 ptr = wmalloc(sizeof(W_Node));
396
397 ptr->data = item;
398 ptr->index = self->count;
399 ptr->left = self->nil;
400 ptr->right = self->nil;
401 ptr->parent = self->nil;
402
403 rbTreeInsert(self, ptr);
404
405 self->count++;
406 }
407
408 void WMInsertInBag(WMBag * self, int index, void *item)
409 {
410 W_Node *ptr;
411
412 ptr = wmalloc(sizeof(W_Node));
413
414 ptr->data = item;
415 ptr->index = index;
416 ptr->left = self->nil;
417 ptr->right = self->nil;
418 ptr->parent = self->nil;
419
420 rbTreeInsert(self, ptr);
421
422 while ((ptr = treeSuccessor(ptr, self->nil)) != self->nil) {
423 ptr->index++;
424 }
425
426 self->count++;
427 }
428
429 int WMRemoveFromBag(WMBag * self, void *item)
430 {
431 W_Node *ptr = treeFind(self->root, self->nil, item);
432
433 if (ptr != self->nil) {
434 W_Node *tmp;
435
436 self->count--;
437
438 tmp = treeSuccessor(ptr, self->nil);
439 while (tmp != self->nil) {
440 tmp->index--;
441 tmp = treeSuccessor(tmp, self->nil);
442 }
443
444 ptr = rbTreeDelete(self, ptr);
445 if (self->destructor)
446 self->destructor(ptr->data);
447 wfree(ptr);
448
449 return 1;
450 } else {
451 return 0;
452 }
453 }
454
455 int WMEraseFromBag(WMBag * self, int index)
456 {
457 W_Node *ptr = treeSearch(self->root, self->nil, index);
458
459 if (ptr != self->nil) {
460
461 self->count--;
462
463 ptr = rbTreeDelete(self, ptr);
464 if (self->destructor)
465 self->destructor(ptr->data);
466 wfree(ptr);
467
468 wassertrv(self->count == 0 || self->root->index >= 0, 1);
469
470 return 1;
471 } else {
472 return 0;
473 }
474 }
475
476 int WMDeleteFromBag(WMBag * self, int index)
477 {
478 W_Node *ptr = treeSearch(self->root, self->nil, index);
479
480 if (ptr != self->nil) {
481 W_Node *tmp;
482
483 self->count--;
484
485 tmp = treeSuccessor(ptr, self->nil);
486 while (tmp != self->nil) {
487 tmp->index--;
488 tmp = treeSuccessor(tmp, self->nil);
489 }
490
491 ptr = rbTreeDelete(self, ptr);
492 if (self->destructor)
493 self->destructor(ptr->data);
494 wfree(ptr);
495
496 wassertrv(self->count == 0 || self->root->index >= 0, 1);
497
498 return 1;
499 } else {
500 return 0;
501 }
502 }
503
504 void *WMGetFromBag(WMBag * self, int index)
505 {
506 W_Node *node;
507
508 node = treeSearch(self->root, self->nil, index);
509 if (node != self->nil)
510 return node->data;
511 else
512 return NULL;
513 }
514
515 int WMGetFirstInBag(WMBag * self, void *item)
516 {
517 W_Node *node;
518
519 node = treeFind(self->root, self->nil, item);
520 if (node != self->nil)
521 return node->index;
522 else
523 return WBNotFound;
524 }
525
526 static int treeCount(W_Node * root, W_Node * nil, void *item)
527 {
528 int count = 0;
529
530 if (root == nil)
531 return 0;
532
533 if (root->data == item)
534 count++;
535
536 if (root->left != nil)
537 count += treeCount(root->left, nil, item);
538
539 if (root->right != nil)
540 count += treeCount(root->right, nil, item);
541
542 return count;
543 }
544
545 int WMCountInBag(WMBag * self, void *item)
546 {
547 return treeCount(self->root, self->nil, item);
548 }
549
550 void *WMReplaceInBag(WMBag * self, int index, void *item)
551 {
552 W_Node *ptr = treeSearch(self->root, self->nil, index);
553 void *old = NULL;
554
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;
566
567 ptr = wmalloc(sizeof(W_Node));
568
569 ptr->data = item;
570 ptr->index = index;
571 ptr->left = self->nil;
572 ptr->right = self->nil;
573 ptr->parent = self->nil;
574
575 rbTreeInsert(self, ptr);
576
577 self->count++;
578 }
579
580 return old;
581 }
582
583 void WMSortBag(WMBag * self, WMCompareDataProc * comparer)
584 {
585 void **items;
586 W_Node *tmp;
587 int i;
588
589 if (self->count == 0)
590 return;
591
592 items = wmalloc(sizeof(void *) * self->count);
593 i = 0;
594
595 tmp = treeMinimum(self->root, self->nil);
596 while (tmp != self->nil) {
597 items[i++] = tmp->data;
598 tmp = treeSuccessor(tmp, self->nil);
599 }
600
601 qsort(&items[0], self->count, sizeof(void *), comparer);
602
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);
609 }
610
611 wfree(items);
612 }
613
614 static void deleteTree(WMBag * self, W_Node * node)
615 {
616 if (node == self->nil)
617 return;
618
619 deleteTree(self, node->left);
620
621 if (self->destructor)
622 self->destructor(node->data);
623
624 deleteTree(self, node->right);
625
626 wfree(node);
627 }
628
629 void WMEmptyBag(WMBag * self)
630 {
631 deleteTree(self, self->root);
632 self->root = self->nil;
633 self->count = 0;
634 }
635
636 void WMFreeBag(WMBag * self)
637 {
638 WMEmptyBag(self);
639 wfree(self->nil);
640 wfree(self);
641 }
642
643 static void mapTree(W_Bag * tree, W_Node * node, void (*function) (void *, void *), void *data)
644 {
645 if (node == tree->nil)
646 return;
647
648 mapTree(tree, node->left, function, data);
649
650 (*function) (node->data, data);
651
652 mapTree(tree, node->right, function, data);
653 }
654
655 void WMMapBag(WMBag * self, void (*function) (void *, void *), void *data)
656 {
657 mapTree(self, self->root, function, data);
658 }
659
660 static int findInTree(W_Bag * tree, W_Node * node, WMMatchDataProc * function, void *cdata)
661 {
662 int index;
663
664 if (node == tree->nil)
665 return WBNotFound;
666
667 index = findInTree(tree, node->left, function, cdata);
668 if (index != WBNotFound)
669 return index;
670
671 if ((*function) (node->data, cdata)) {
672 return node->index;
673 }
674
675 return findInTree(tree, node->right, function, cdata);
676 }
677
678 int WMFindInBag(WMBag * self, WMMatchDataProc * match, void *cdata)
679 {
680 return findInTree(self, self->root, match, cdata);
681 }
682
683 void *WMBagFirst(WMBag * self, WMBagIterator * ptr)
684 {
685 W_Node *node;
686
687 node = treeMinimum(self->root, self->nil);
688
689 if (node == self->nil) {
690 *ptr = NULL;
691 return NULL;
692 } else {
693 *ptr = node;
694 return node->data;
695 }
696 }
697
698 void *WMBagLast(WMBag * self, WMBagIterator * ptr)
699 {
700
701 W_Node *node;
702
703 node = treeMaximum(self->root, self->nil);
704
705 if (node == self->nil) {
706 *ptr = NULL;
707 return NULL;
708 } else {
709 *ptr = node;
710 return node->data;
711 }
712 }
713
714 void *WMBagNext(WMBag * self, WMBagIterator * ptr)
715 {
716 W_Node *node;
717
718 if (*ptr == NULL)
719 return NULL;
720
721 node = treeSuccessor(*ptr, self->nil);
722
723 if (node == self->nil) {
724 *ptr = NULL;
725 return NULL;
726 } else {
727 *ptr = node;
728 return node->data;
729 }
730 }
731
732 void *WMBagPrevious(WMBag * self, WMBagIterator * ptr)
733 {
734 W_Node *node;
735
736 if (*ptr == NULL)
737 return NULL;
738
739 node = treePredecessor(*ptr, self->nil);
740
741 if (node == self->nil) {
742 *ptr = NULL;
743 return NULL;
744 } else {
745 *ptr = node;
746 return node->data;
747 }
748 }
749
750 void *WMBagIteratorAtIndex(WMBag * self, int index, WMBagIterator * ptr)
751 {
752 W_Node *node;
753
754 node = treeSearch(self->root, self->nil, index);
755
756 if (node == self->nil) {
757 *ptr = NULL;
758 return NULL;
759 } else {
760 *ptr = node;
761 return node->data;
762 }
763 }
764
765 int WMBagIndexForIterator(WMBag * bag, WMBagIterator ptr)
766 {
767 return ((W_Node *) ptr)->index;
768 }