Mercurial > dovecot > original-hg > dovecot-1.2

comparison src/lib-index/mail-tree-redblack.c @ 903:fd8888f6f037 HEAD

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Naming style changes, finally got tired of most of the typedefs. Also the previous enum -> macro change reverted so that we don't use the highest bit anymore, that's incompatible with old indexes so they will be rebuilt.
author Timo Sirainen <tss@iki.fi>
date Sun, 05 Jan 2003 15:09:51 +0200
parents 41dde6822eea
children e291bf36d57f
comparison
equal deleted inserted replaced
902:5043e48c022f 903:fd8888f6f037
82 ** red and black nodes) is only twice as long as the shortest 82 ** red and black nodes) is only twice as long as the shortest
83 ** path (all black nodes). Thus the tree remains fairly balanced. 83 ** path (all black nodes). Thus the tree remains fairly balanced.
84 */ 84 */
85 85
86 static unsigned int 86 static unsigned int
87 rb_alloc(MailTree *tree) 87 rb_alloc(struct mail_tree *tree)
88 { 88 {
89 unsigned int x; 89 unsigned int x;
90 90
91 if (tree->mmap_used_length == tree->mmap_full_length) { 91 if (tree->mmap_used_length == tree->mmap_full_length) {
92 if (!_mail_tree_grow(tree)) 92 if (!_mail_tree_grow(tree))
93 return RBNULL; 93 return RBNULL;
94 } 94 }
95 95
96 i_assert(tree->header->used_file_size == tree->mmap_used_length); 96 i_assert(tree->header->used_file_size == tree->mmap_used_length);
97 i_assert(tree->mmap_used_length + sizeof(MailTreeNode) <= 97 i_assert(tree->mmap_used_length + sizeof(struct mail_tree_node) <=
98 tree->mmap_full_length); 98 tree->mmap_full_length);
99 99
100 x = (tree->mmap_used_length - sizeof(MailTreeHeader)) / 100 x = (tree->mmap_used_length - sizeof(struct mail_tree_header)) /
101 sizeof(MailTreeNode); 101 sizeof(struct mail_tree_node);
102 102
103 tree->header->used_file_size += sizeof(MailTreeNode); 103 tree->header->used_file_size += sizeof(struct mail_tree_node);
104 tree->mmap_used_length += sizeof(MailTreeNode); 104 tree->mmap_used_length += sizeof(struct mail_tree_node);
105 105
106 memset(&tree->node_base[x], 0, sizeof(MailTreeNode)); 106 memset(&tree->node_base[x], 0, sizeof(struct mail_tree_node));
107 return x; 107 return x;
108 } 108 }
109 109
110 static void 110 static void
111 rb_move(MailTree *tree, unsigned int src, unsigned int dest) 111 rb_move(struct mail_tree *tree, unsigned int src, unsigned int dest)
112 { 112 {
113 MailTreeNode *node = tree->node_base; 113 struct mail_tree_node *node = tree->node_base;
114 114
115 /* update parent */ 115 /* update parent */
116 if (node[src].up != RBNULL) { 116 if (node[src].up != RBNULL) {
117 if (node[node[src].up].left == src) 117 if (node[node[src].up].left == src)
118 node[node[src].up].left = dest; 118 node[node[src].up].left = dest;
128 128
129 /* update root */ 129 /* update root */
130 if (tree->header->root == src) 130 if (tree->header->root == src)
131 tree->header->root = dest; 131 tree->header->root = dest;
132 132
133 memcpy(&node[dest], &node[src], sizeof(MailTreeNode)); 133 memcpy(&node[dest], &node[src], sizeof(struct mail_tree_node));
134 memset(&node[src], 0, sizeof(MailTreeNode)); 134 memset(&node[src], 0, sizeof(struct mail_tree_node));
135 } 135 }
136 136
137 static void 137 static void
138 rb_free(MailTree *tree, unsigned int x) 138 rb_free(struct mail_tree *tree, unsigned int x)
139 { 139 {
140 unsigned int last; 140 unsigned int last;
141 141
142 i_assert(tree->mmap_used_length >= 142 i_assert(tree->mmap_used_length >=
143 sizeof(MailTreeHeader) + sizeof(MailTreeNode)); 143 sizeof(struct mail_tree_header) +
144 sizeof(struct mail_tree_node));
144 145
145 /* get index to last used record */ 146 /* get index to last used record */
146 last = (tree->mmap_used_length - sizeof(MailTreeHeader)) / 147 last = (tree->mmap_used_length - sizeof(struct mail_tree_header)) /
147 sizeof(MailTreeNode) - 1; 148 sizeof(struct mail_tree_node) - 1;
148 149
149 if (last != x) { 150 if (last != x) {
150 /* move it over the one we want free'd */ 151 /* move it over the one we want free'd */
151 rb_move(tree, last, x); 152 rb_move(tree, last, x);
152 } 153 }
153 154
154 /* mark the moved node unused */ 155 /* mark the moved node unused */
155 tree->mmap_used_length -= sizeof(MailTreeNode); 156 tree->mmap_used_length -= sizeof(struct mail_tree_node);
156 tree->header->used_file_size -= sizeof(MailTreeNode); 157 tree->header->used_file_size -= sizeof(struct mail_tree_node);
157 158
158 _mail_tree_truncate(tree); 159 _mail_tree_truncate(tree);
159 } 160 }
160 161
161 /* 162 /*
175 ** X += C+1 X -= C+1 176 ** X += C+1 X -= C+1
176 ** Y -= A+1 Y += A+1 177 ** Y -= A+1 Y += A+1
177 */ 178 */
178 179
179 static void 180 static void
180 rb_left_rotate(MailTree *tree, unsigned int x) 181 rb_left_rotate(struct mail_tree *tree, unsigned int x)
181 { 182 {
182 MailTreeNode *node = tree->node_base; 183 struct mail_tree_node *node = tree->node_base;
183 unsigned int y, a_nodes, c_nodes; 184 unsigned int y, a_nodes, c_nodes;
184 185
185 i_assert(x != RBNULL); 186 i_assert(x != RBNULL);
186 i_assert(node[x].right != RBNULL); 187 i_assert(node[x].right != RBNULL);
187 188
220 NODE_COUNT_ADD(node[x], -(c_nodes+1)); 221 NODE_COUNT_ADD(node[x], -(c_nodes+1));
221 NODE_COUNT_ADD(node[y], a_nodes+1); 222 NODE_COUNT_ADD(node[y], a_nodes+1);
222 } 223 }
223 224
224 static void 225 static void
225 rb_right_rotate(MailTree *tree, unsigned int y) 226 rb_right_rotate(struct mail_tree *tree, unsigned int y)
226 { 227 {
227 MailTreeNode *node = tree->node_base; 228 struct mail_tree_node *node = tree->node_base;
228 unsigned int x, a_nodes, c_nodes; 229 unsigned int x, a_nodes, c_nodes;
229 230
230 i_assert(y != RBNULL); 231 i_assert(y != RBNULL);
231 i_assert(node[y].left != RBNULL); 232 i_assert(node[y].left != RBNULL);
232 233
267 } 268 }
268 269
269 /* Return index to the smallest key greater than x 270 /* Return index to the smallest key greater than x
270 */ 271 */
271 static unsigned int 272 static unsigned int
272 rb_successor(MailTree *tree, unsigned int x) 273 rb_successor(struct mail_tree *tree, unsigned int x)
273 { 274 {
274 MailTreeNode *node = tree->node_base; 275 struct mail_tree_node *node = tree->node_base;
275 unsigned int y; 276 unsigned int y;
276 277
277 if (node[x].right != RBNULL) { 278 if (node[x].right != RBNULL) {
278 /* If right is not NULL then go right one and 279 /* If right is not NULL then go right one and
279 ** then keep going left until we find a node with 280 ** then keep going left until we find a node with
297 return y; 298 return y;
298 } 299 }
299 300
300 /* Restore the reb-black properties after insert */ 301 /* Restore the reb-black properties after insert */
301 static int 302 static int
302 rb_insert_fix(MailTree *tree, unsigned int z) 303 rb_insert_fix(struct mail_tree *tree, unsigned int z)
303 { 304 {
304 MailTreeNode *node = tree->node_base; 305 struct mail_tree_node *node = tree->node_base;
305 unsigned int x, y, x_up_up; 306 unsigned int x, y, x_up_up;
306 307
307 /* color this new node red */ 308 /* color this new node red */
308 NODE_SET_RED(node[z]); 309 NODE_SET_RED(node[z]);
309 310
378 return z; 379 return z;
379 } 380 }
380 381
381 /* Restore the reb-black properties after a delete */ 382 /* Restore the reb-black properties after a delete */
382 static void 383 static void
383 rb_delete_fix(MailTree *tree, unsigned int x) 384 rb_delete_fix(struct mail_tree *tree, unsigned int x)
384 { 385 {
385 MailTreeNode *node = tree->node_base; 386 struct mail_tree_node *node = tree->node_base;
386 unsigned int w; 387 unsigned int w;
387 388
388 while (x != tree->header->root && IS_NODE_BLACK(node[x])) { 389 while (x != tree->header->root && IS_NODE_BLACK(node[x])) {
389 if (x == node[node[x].up].left) { 390 if (x == node[node[x].up].left) {
390 w = node[node[x].up].right; 391 w = node[node[x].up].right;
488 */ 489 */
489 490
490 /* Delete the node z, and free up the space 491 /* Delete the node z, and free up the space
491 */ 492 */
492 static void 493 static void
493 rb_delete(MailTree *tree, unsigned int z) 494 rb_delete(struct mail_tree *tree, unsigned int z)
494 { 495 {
495 MailTreeNode *node = tree->node_base; 496 struct mail_tree_node *node = tree->node_base;
496 unsigned int x, y, b; 497 unsigned int x, y, b;
497 498
498 if (node[z].left == RBNULL || node[z].right == RBNULL) { 499 if (node[z].left == RBNULL || node[z].right == RBNULL) {
499 y = z; 500 y = z;
500 b = RBNULL; 501 b = RBNULL;
548 rb_free(tree, y); 549 rb_free(tree, y);
549 } 550 }
550 551
551 #ifdef DEBUG_TREE 552 #ifdef DEBUG_TREE
552 int 553 int
553 rb_check1(MailTree *tree, unsigned int x) 554 rb_check1(struct mail_tree *tree, unsigned int x)
554 { 555 {
555 MailTreeNode *node = tree->node_base; 556 struct mail_tree_node *node = tree->node_base;
556 557
557 if (IS_NODE_RED(node[x])) { 558 if (IS_NODE_RED(node[x])) {
558 if (!IS_NODE_BLACK(node[node[x].left]) || 559 if (!IS_NODE_BLACK(node[node[x].left]) ||
559 !IS_NODE_BLACK(node[node[x].right])) { 560 !IS_NODE_BLACK(node[node[x].right])) {
560 i_error("Children of red node not both black, x=%u", x); 561 i_error("Children of red node not both black, x=%u", x);
583 } 584 }
584 585
585 return 0; 586 return 0;
586 } 587 }
587 588
588 int count_black(MailTree *tree, unsigned int x) 589 int count_black(struct mail_tree *tree, unsigned int x)
589 { 590 {
590 MailTreeNode *node = tree->node_base; 591 struct mail_tree_node *node = tree->node_base;
591 int nleft, nright; 592 int nleft, nright;
592 593
593 if (x == RBNULL) 594 if (x == RBNULL)
594 return 1; 595 return 1;
595 596
608 nleft++; 609 nleft++;
609 610
610 return nleft; 611 return nleft;
611 } 612 }
612 613
613 int count_nodes(MailTree *tree, unsigned int x) 614 int count_nodes(struct mail_tree *tree, unsigned int x)
614 { 615 {
615 MailTreeNode *node = tree->node_base; 616 struct mail_tree_node *node = tree->node_base;
616 int nleft, nright; 617 int nleft, nright;
617 618
618 if (x == RBNULL) 619 if (x == RBNULL)
619 return 0; 620 return 0;
620 621
631 } 632 }
632 633
633 return nleft+nright+1; 634 return nleft+nright+1;
634 } 635 }
635 636
636 void dumptree(MailTree *tree, unsigned int x, int n) 637 void dumptree(struct mail_tree *tree, unsigned int x, int n)
637 { 638 {
638 MailTreeNode *node = tree->node_base; 639 struct mail_tree_node *node = tree->node_base;
639 640
640 if (x != RBNULL) { 641 if (x != RBNULL) {
641 n++; 642 n++;
642 i_error("Tree: %*s %u: left=%u, right=%u, color=%s, " 643 i_error("Tree: %*s %u: left=%u, right=%u, color=%s, "
643 "nodes=%u, key=%u", 644 "nodes=%u, key=%u",
649 dumptree(tree, node[x].right, n); 650 dumptree(tree, node[x].right, n);
650 } 651 }
651 } 652 }
652 653
653 int 654 int
654 rb_check(MailTree *tree) 655 rb_check(struct mail_tree *tree)
655 { 656 {
656 MailTreeNode *node = tree->node_base; 657 struct mail_tree_node *node = tree->node_base;
657 unsigned int root; 658 unsigned int root;
658 659
659 root = tree->header->root; 660 root = tree->header->root;
660 if (root == RBNULL) 661 if (root == RBNULL)
661 return 0; 662 return 0;
683 684
684 return 0; 685 return 0;
685 } 686 }
686 #endif 687 #endif
687 688
688 unsigned int mail_tree_lookup_uid_range(MailTree *tree, unsigned int *seq_r, 689 unsigned int mail_tree_lookup_uid_range(struct mail_tree *tree,
690 unsigned int *seq_r,
689 unsigned int first_uid, 691 unsigned int first_uid,
690 unsigned int last_uid) 692 unsigned int last_uid)
691 { 693 {
692 MailTreeNode *node; 694 struct mail_tree_node *node;
693 unsigned int x, y, seq; 695 unsigned int x, y, seq;
694 696
695 i_assert(first_uid > 0 && last_uid > 0); 697 i_assert(first_uid > 0 && last_uid > 0);
696 i_assert(first_uid <= last_uid); 698 i_assert(first_uid <= last_uid);
697 i_assert(tree->index->lock_type != MAIL_LOCK_UNLOCK); 699 i_assert(tree->index->lock_type != MAIL_LOCK_UNLOCK);
744 } 746 }
745 747
746 return x == RBNULL ? (unsigned int)-1 : node[x].value; 748 return x == RBNULL ? (unsigned int)-1 : node[x].value;
747 } 749 }
748 750
749 unsigned int mail_tree_lookup_sequence(MailTree *tree, unsigned int seq) 751 unsigned int mail_tree_lookup_sequence(struct mail_tree *tree, unsigned int seq)
750 { 752 {
751 MailTreeNode *node; 753 struct mail_tree_node *node;
752 unsigned int x, upleft_nodes, left_nodes; 754 unsigned int x, upleft_nodes, left_nodes;
753 755
754 i_assert(seq != 0); 756 i_assert(seq != 0);
755 i_assert(tree->index->lock_type != MAIL_LOCK_UNLOCK); 757 i_assert(tree->index->lock_type != MAIL_LOCK_UNLOCK);
756 758
780 } 782 }
781 783
782 return (unsigned int)-1; 784 return (unsigned int)-1;
783 } 785 }
784 786
785 int mail_tree_insert(MailTree *tree, unsigned int uid, unsigned int index) 787 int mail_tree_insert(struct mail_tree *tree,
786 { 788 unsigned int uid, unsigned int index)
787 MailTreeNode *node; 789 {
790 struct mail_tree_node *node;
788 unsigned int x, z; 791 unsigned int x, z;
789 792
790 i_assert(uid != 0); 793 i_assert(uid != 0);
791 i_assert(tree->index->lock_type == MAIL_LOCK_EXCLUSIVE); 794 i_assert(tree->index->lock_type == MAIL_LOCK_EXCLUSIVE);
792 795
839 842
840 tree->modified = TRUE; 843 tree->modified = TRUE;
841 return TRUE; 844 return TRUE;
842 } 845 }
843 846
844 int mail_tree_update(MailTree *tree, unsigned int uid, unsigned int index) 847 int mail_tree_update(struct mail_tree *tree,
845 { 848 unsigned int uid, unsigned int index)
846 MailTreeNode *node; 849 {
850 struct mail_tree_node *node;
847 unsigned int x; 851 unsigned int x;
848 852
849 i_assert(uid != 0); 853 i_assert(uid != 0);
850 i_assert(tree->index->lock_type == MAIL_LOCK_EXCLUSIVE); 854 i_assert(tree->index->lock_type == MAIL_LOCK_EXCLUSIVE);
851 855
873 _mail_tree_set_corrupted(tree, "Tried to update nonexisting UID %u", 877 _mail_tree_set_corrupted(tree, "Tried to update nonexisting UID %u",
874 uid); 878 uid);
875 return FALSE; 879 return FALSE;
876 } 880 }
877 881
878 void mail_tree_delete(MailTree *tree, unsigned int uid) 882 void mail_tree_delete(struct mail_tree *tree, unsigned int uid)
879 { 883 {
880 MailTreeNode *node; 884 struct mail_tree_node *node;
881 unsigned int x; 885 unsigned int x;
882 886
883 i_assert(uid != 0); 887 i_assert(uid != 0);
884 i_assert(tree->index->lock_type == MAIL_LOCK_EXCLUSIVE); 888 i_assert(tree->index->lock_type == MAIL_LOCK_EXCLUSIVE);
885 889