dovecot/original-hg/dovecot-1.2: src/lib-index/mail-tree-redblack.c annotate

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

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

rev	line source
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	1 /*
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	2 Redblack balanced tree algorithm, http://libredblack.sourceforge.net/
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	3 Copyright (C) Damian Ivereigh 2000
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	4
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	5 Modified to be suitable for mmap()ing and for IMAP server
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	6 Copyright (C) Timo Sirainen 2002
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	7
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	8 This program is free software; you can redistribute it and/or modify
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	9 it under the terms of the GNU Lesser General Public License as published by
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	10 the Free Software Foundation; either version 2.1 of the License, or
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	11 (at your option) any later version. See the file COPYING for details.
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	12
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	13 This program is distributed in the hope that it will be useful,
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	14 but WITHOUT ANY WARRANTY; without even the implied warranty of
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	16 GNU General Public License for more details.
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	17
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	18 You should have received a copy of the GNU Lesser General Public License
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	19 along with this program; if not, write to the Free Software
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	20 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
496 fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	21 */
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	22
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	23 /* NOTE: currently this code doesn't do any bounds checkings. I'm not sure
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	24 if I should even bother, the code would just get uglier and slower. */
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	25
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	26 #include "lib.h"
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	27 #include "mail-index.h"
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	28 #include "mail-tree.h"
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	29
360 d57e5037db2c guess it works now, debugging disabled now. Timo Sirainen <tss@iki.fi> parents: 359 diff changeset	30 /* #define DEBUG_TREE */
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	31
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	32 #ifndef DEBUG_TREE
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	33 # define rb_check(tree)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	34 #endif
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	35
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	36 /* Dummy (sentinel) node, so that we can make X->left->up = X
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	37 ** We then use this instead of NULL to mean the top or bottom
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	38 ** end of the rb tree. It is a black node.
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	39 */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	40 #define RBNULL 0
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	41
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	42 /* If highest bit in node_count is set, the node is red. */
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	43 #define RED_MASK (1 << (SIZEOF_INT*CHAR_BIT-1))
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	44
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	45 #define IS_NODE_BLACK(node) \
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	46 (((node).node_count & RED_MASK) == 0)
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	47 #define IS_NODE_RED(node) \
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	48 (((node).node_count & RED_MASK) != 0)
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	49
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	50 #define NODE_SET_BLACK(node) \
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	51 STMT_START { (node).node_count &= ~RED_MASK; } STMT_END
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	52 #define NODE_SET_RED(node) \
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	53 STMT_START { (node).node_count \|= RED_MASK; } STMT_END
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	54
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	55 #define NODE_COPY_COLOR(dest, src) \
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	56 STMT_START { \
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	57 if (((src).node_count & RED_MASK) != \
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	58 ((dest).node_count & RED_MASK)) \
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	59 (dest).node_count ^= RED_MASK; \
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	60 } STMT_END
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	61
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	62 #define NODE_COUNT(node) \
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	63 ((node).node_count & ~RED_MASK)
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	64
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	65 #define NODE_COUNT_ADD(node, count) \
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	66 STMT_START { (node).node_count += (count); } STMT_END
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	67
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	68 /*
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	69 ** OK here we go, the balanced tree stuff. The algorithm is the
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	70 ** fairly standard red/black taken from "Introduction to Algorithms"
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	71 ** by Cormen, Leiserson & Rivest. Maybe one of these days I will
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	72 ** fully understand all this stuff.
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	73 **
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	74 ** Basically a red/black balanced tree has the following properties:-
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	75 ** 1) Every node is either red or black (color is RED or BLACK)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	76 ** 2) A leaf (RBNULL pointer) is considered black
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	77 ** 3) If a node is red then its children are black
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	78 ** 4) Every path from a node to a leaf contains the same no
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	79 ** of black nodes
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	80 **
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	81 ** 3) & 4) above guarantee that the longest path (alternating
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	82 ** red and black nodes) is only twice as long as the shortest
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	83 ** path (all black nodes). Thus the tree remains fairly balanced.
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	84 */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	85
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	86 static unsigned int
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	87 rb_alloc(struct mail_tree *tree)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	88 {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	89 unsigned int x;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	90
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	91 if (tree->mmap_used_length == tree->mmap_full_length) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	92 if (!_mail_tree_grow(tree))
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	93 return RBNULL;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	94 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	95
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	96 i_assert(tree->header->used_file_size == tree->mmap_used_length);
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	97 i_assert(tree->mmap_used_length + sizeof(struct mail_tree_node) <=
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	98 tree->mmap_full_length);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	99
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	100 x = (tree->mmap_used_length - sizeof(struct mail_tree_header)) /
fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	101 sizeof(struct mail_tree_node);
496 fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	102
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	103 tree->header->used_file_size += sizeof(struct mail_tree_node);
fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	104 tree->mmap_used_length += sizeof(struct mail_tree_node);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	105
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	106 memset(&tree->node_base[x], 0, sizeof(struct mail_tree_node));
496 fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	107 return x;
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	108 }
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	109
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	110 static void
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	111 rb_move(struct mail_tree *tree, unsigned int src, unsigned int dest)
496 fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	112 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	113 struct mail_tree_node *node = tree->node_base;
496 fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	114
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	115 /* update parent */
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	116 if (node[src].up != RBNULL) {
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	117 if (node[node[src].up].left == src)
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	118 node[node[src].up].left = dest;
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	119 else if (node[node[src].up].right == src)
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	120 node[node[src].up].right = dest;
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	121 }
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	122
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	123 /* update children */
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	124 if (node[src].left != RBNULL)
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	125 node[node[src].left].up = dest;
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	126 if (node[src].right != RBNULL)
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	127 node[node[src].right].up = dest;
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	128
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	129 /* update root */
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	130 if (tree->header->root == src)
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	131 tree->header->root = dest;
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	132
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	133 memcpy(&node[dest], &node[src], sizeof(struct mail_tree_node));
fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	134 memset(&node[src], 0, sizeof(struct mail_tree_node));
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	135 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	136
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	137 static void
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	138 rb_free(struct mail_tree *tree, unsigned int x)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	139 {
496 fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	140 unsigned int last;
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	141
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	142 i_assert(tree->mmap_used_length >=
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	143 sizeof(struct mail_tree_header) +
fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	144 sizeof(struct mail_tree_node));
496 fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	145
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	146 /* get index to last used record */
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	147 last = (tree->mmap_used_length - sizeof(struct mail_tree_header)) /
fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	148 sizeof(struct mail_tree_node) - 1;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	149
496 fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	150 if (last != x) {
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	151 /* move it over the one we want free'd */
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	152 rb_move(tree, last, x);
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	153 }
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	154
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	155 /* mark the moved node unused */
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	156 tree->mmap_used_length -= sizeof(struct mail_tree_node);
fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	157 tree->header->used_file_size -= sizeof(struct mail_tree_node);
496 fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	158
fef80ac4fb09 Instead of keeping "unused nodes" list in tree file, just move the last node Timo Sirainen <tss@iki.fi> parents: 488 diff changeset	159 _mail_tree_truncate(tree);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	160 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	161
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	162 /*
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	163 ** Rotate our tree thus:-
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	164 **
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	165 ** X rb_left_rotate(X)---> Y
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	166 ** / \ / \
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	167 ** A Y <---rb_right_rotate(Y) X C
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	168 ** / \ / \
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	169 ** B C A B
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	170 **
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	171 ** N.B. This does not change the ordering.
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	172 **
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	173 ** We assume that neither X or Y is NULL
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	174 **
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	175 ** Node count changes:
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	176 ** X += C+1 X -= C+1
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	177 ** Y -= A+1 Y += A+1
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	178 */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	179
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	180 static void
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	181 rb_left_rotate(struct mail_tree *tree, unsigned int x)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	182 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	183 struct mail_tree_node *node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	184 unsigned int y, a_nodes, c_nodes;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	185
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	186 i_assert(x != RBNULL);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	187 i_assert(node[x].right != RBNULL);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	188
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	189 y = node[x].right;
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	190 a_nodes = NODE_COUNT(node[node[x].left]);
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	191 c_nodes = NODE_COUNT(node[node[y].right]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	192
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	193 /* Turn Y's left subtree into X's right subtree (move B) */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	194 node[x].right = node[y].left;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	195
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	196 /* If B is not null, set it's parent to be X */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	197 if (node[y].left != RBNULL)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	198 node[node[y].left].up = x;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	199
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	200 /* Set Y's parent to be what X's parent was */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	201 node[y].up = node[x].up;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	202
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	203 /* if X was the root */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	204 if (node[x].up == RBNULL) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	205 tree->header->root = y;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	206 } else {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	207 /* Set X's parent's left or right pointer to be Y */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	208 if (x == node[node[x].up].left)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	209 node[node[x].up].left = y;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	210 else
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	211 node[node[x].up].right = y;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	212 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	213
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	214 /* Put X on Y's left */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	215 node[y].left = x;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	216
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	217 /* Set X's parent to be Y */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	218 node[x].up = y;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	219
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	220 /* Update node counts */
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	221 NODE_COUNT_ADD(node[x], -(c_nodes+1));
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	222 NODE_COUNT_ADD(node[y], a_nodes+1);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	223 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	224
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	225 static void
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	226 rb_right_rotate(struct mail_tree *tree, unsigned int y)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	227 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	228 struct mail_tree_node *node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	229 unsigned int x, a_nodes, c_nodes;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	230
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	231 i_assert(y != RBNULL);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	232 i_assert(node[y].left != RBNULL);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	233
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	234 x = node[y].left;
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	235 a_nodes = NODE_COUNT(node[node[x].left]);
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	236 c_nodes = NODE_COUNT(node[node[y].right]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	237
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	238 /* Turn X's right subtree into Y's left subtree (move B) */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	239 node[y].left = node[x].right;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	240
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	241 /* If B is not null, set it's parent to be Y */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	242 if (node[x].right != RBNULL)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	243 node[node[x].right].up = y;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	244
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	245 /* Set X's parent to be what Y's parent was */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	246 node[x].up = node[y].up;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	247
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	248 /* if Y was the root */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	249 if (node[y].up == RBNULL)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	250 tree->header->root = x;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	251 else {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	252 /* Set Y's parent's left or right pointer to be X */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	253 if (y == node[node[y].up].left)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	254 node[node[y].up].left = x;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	255 else
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	256 node[node[y].up].right = x;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	257 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	258
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	259 /* Put Y on X's right */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	260 node[x].right = y;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	261
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	262 /* Set Y's parent to be X */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	263 node[y].up = x;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	264
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	265 /* Update node counts */
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	266 NODE_COUNT_ADD(node[x], c_nodes+1);
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	267 NODE_COUNT_ADD(node[y], -(a_nodes+1));
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	268 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	269
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	270 /* Return index to the smallest key greater than x
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	271 */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	272 static unsigned int
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	273 rb_successor(struct mail_tree *tree, unsigned int x)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	274 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	275 struct mail_tree_node *node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	276 unsigned int y;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	277
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	278 if (node[x].right != RBNULL) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	279 /* If right is not NULL then go right one and
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	280 ** then keep going left until we find a node with
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	281 ** no left pointer.
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	282 */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	283 y = node[x].right;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	284 while (node[y].left != RBNULL)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	285 y = node[y].left;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	286 } else {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	287 /* Go up the tree until we get to a node that is on the
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	288 ** left of its parent (or the root) and then return the
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	289 ** parent.
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	290 */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	291 y = node[x].up;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	292 while (y != RBNULL && x == node[y].right) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	293 x = y;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	294 y = node[y].up;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	295 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	296 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	297
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	298 return y;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	299 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	300
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	301 /* Restore the reb-black properties after insert */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	302 static int
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	303 rb_insert_fix(struct mail_tree *tree, unsigned int z)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	304 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	305 struct mail_tree_node *node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	306 unsigned int x, y, x_up_up;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	307
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	308 /* color this new node red */
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	309 NODE_SET_RED(node[z]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	310
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	311 /* Having added a red node, we must now walk back up the tree balancing
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	312 ** it, by a series of rotations and changing of colors
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	313 */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	314 x = z;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	315
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	316 /* While we are not at the top and our parent node is red
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	317 ** N.B. Since the root node is garanteed black, then we
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	318 ** are also going to stop if we are the child of the root
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	319 */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	320
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	321 while (x != tree->header->root && IS_NODE_RED(node[node[x].up])) {
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	322 /* if our parent is on the left side of our grandparent */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	323 x_up_up = node[node[x].up].up;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	324 if (node[x].up == node[x_up_up].left) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	325 /* get the right side of our grandparent (uncle?) */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	326 y = node[x_up_up].right;
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	327 if (IS_NODE_RED(node[y])) {
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	328 /* make our parent black */
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	329 NODE_SET_BLACK(node[node[x].up]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	330 /* make our uncle black */
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	331 NODE_SET_BLACK(node[y]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	332 /* make our grandparent red */
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	333 NODE_SET_RED(node[x_up_up]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	334
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	335 /* now consider our grandparent */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	336 x = x_up_up;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	337 } else {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	338 /* if we are on the right side of our parent */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	339 if (x == node[node[x].up].right) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	340 /* Move up to our parent */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	341 x = node[x].up;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	342 rb_left_rotate(tree, x);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	343 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	344
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	345 /* make our parent black */
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	346 NODE_SET_BLACK(node[node[x].up]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	347 /* make our grandparent red */
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	348 NODE_SET_RED(node[x_up_up]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	349 /* right rotate our grandparent */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	350 rb_right_rotate(tree, x_up_up);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	351 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	352 } else {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	353 /* everything here is the same as above, but
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	354 ** exchanging left for right
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	355 */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	356
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	357 y = node[x_up_up].left;
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	358 if (IS_NODE_RED(node[y])) {
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	359 NODE_SET_BLACK(node[node[x].up]);
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	360 NODE_SET_BLACK(node[y]);
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	361 NODE_SET_RED(node[x_up_up]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	362
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	363 x = x_up_up;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	364 } else {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	365 if (x == node[node[x].up].left) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	366 x = node[x].up;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	367 rb_right_rotate(tree, x);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	368 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	369
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	370 NODE_SET_BLACK(node[node[x].up]);
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	371 NODE_SET_RED(node[x_up_up]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	372 rb_left_rotate(tree, x_up_up);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	373 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	374 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	375 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	376
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	377 /* Set the root node black */
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	378 NODE_SET_BLACK(node[tree->header->root]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	379 return z;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	380 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	381
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	382 /* Restore the reb-black properties after a delete */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	383 static void
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	384 rb_delete_fix(struct mail_tree *tree, unsigned int x)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	385 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	386 struct mail_tree_node *node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	387 unsigned int w;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	388
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	389 while (x != tree->header->root && IS_NODE_BLACK(node[x])) {
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	390 if (x == node[node[x].up].left) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	391 w = node[node[x].up].right;
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	392 if (IS_NODE_RED(node[w])) {
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	393 NODE_SET_BLACK(node[w]);
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	394 NODE_SET_RED(node[node[x].up]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	395 rb_left_rotate(tree, node[x].up);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	396 w = node[node[x].up].right;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	397 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	398
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	399 if (IS_NODE_BLACK(node[node[w].left]) &&
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	400 IS_NODE_BLACK(node[node[w].right])) {
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	401 NODE_SET_RED(node[w]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	402 x = node[x].up;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	403 } else {
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	404 if (IS_NODE_BLACK(node[node[w].right])) {
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	405 NODE_SET_BLACK(node[node[w].left]);
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	406 NODE_SET_RED(node[w]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	407 rb_right_rotate(tree, w);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	408 w = node[node[x].up].right;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	409 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	410
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	411
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	412 NODE_COPY_COLOR(node[w], node[node[x].up]);
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	413 NODE_SET_BLACK(node[node[x].up]);
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	414 NODE_SET_BLACK(node[node[w].right]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	415 rb_left_rotate(tree, node[x].up);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	416 x = tree->header->root;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	417 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	418 } else {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	419 w = node[node[x].up].left;
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	420 if (IS_NODE_RED(node[w])) {
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	421 NODE_SET_BLACK(node[w]);
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	422 NODE_SET_RED(node[node[x].up]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	423 rb_right_rotate(tree, node[x].up);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	424 w = node[node[x].up].left;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	425 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	426
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	427 if (IS_NODE_BLACK(node[node[w].right]) &&
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	428 IS_NODE_BLACK(node[node[w].left])) {
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	429 NODE_SET_RED(node[w]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	430 x = node[x].up;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	431 } else {
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	432 if (IS_NODE_BLACK(node[node[w].left])) {
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	433 NODE_SET_BLACK(node[node[w].right]);
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	434 NODE_SET_RED(node[w]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	435 rb_left_rotate(tree, w);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	436 w = node[node[x].up].left;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	437 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	438
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	439 NODE_COPY_COLOR(node[w], node[node[x].up]);
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	440 NODE_SET_BLACK(node[node[x].up]);
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	441 NODE_SET_BLACK(node[node[w].left]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	442 rb_right_rotate(tree, node[x].up);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	443 x = tree->header->root;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	444 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	445 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	446 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	447
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	448 NODE_SET_BLACK(node[x]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	449 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	450
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	451 /*
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	452 ** case 1 - only one child:
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	453 **
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	454 ** Z --> Y
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	455 ** /
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	456 ** Y
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	457 **
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	458 ** Node count changes:
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	459 ** parents -= 1
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	460 **
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	461 ** case 2 - right child has no left child:
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	462 **
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	463 ** Z Y
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	464 ** / \ / \
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	465 ** A Y --> A X
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	466 ** \
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	467 ** X
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	468 **
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	469 ** Node count changes:
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	470 ** parents -= 1
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	471 ** Y = Z-1
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	472 **
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	473 ** case 3 - right child has left child:
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	474 **
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	475 ** Z Y
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	476 ** / \ / \
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	477 ** A B --> A B
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	478 ** / /
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	479 ** .. ..
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	480 ** / /
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	481 ** Y X
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	482 ** \
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	483 ** X
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	484 **
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	485 ** Node count changes:
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	486 ** parents -= 1
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	487 ** Y = Z-1
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	488 ** B .. X.up -= 1 (NOTE: X may not exist)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	489 */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	490
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	491 /* Delete the node z, and free up the space
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	492 */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	493 static void
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	494 rb_delete(struct mail_tree *tree, unsigned int z)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	495 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	496 struct mail_tree_node *node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	497 unsigned int x, y, b;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	498
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	499 if (node[z].left == RBNULL \|\| node[z].right == RBNULL) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	500 y = z;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	501 b = RBNULL;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	502 } else {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	503 y = rb_successor(tree, z);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	504 if (y == node[z].right)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	505 b = RBNULL;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	506 else
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	507 b = node[z].right;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	508 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	509
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	510 if (node[y].left != RBNULL)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	511 x = node[y].left;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	512 else
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	513 x = node[y].right;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	514
359 9fd132e47845 bugfixes Timo Sirainen <tss@iki.fi> parents: 357 diff changeset	515 /* this may modify RBNULL, which IMHO is a bit nasty,
9fd132e47845 bugfixes Timo Sirainen <tss@iki.fi> parents: 357 diff changeset	516 but rb_delete_fix() requires it to work properly. */
9fd132e47845 bugfixes Timo Sirainen <tss@iki.fi> parents: 357 diff changeset	517 node[x].up = node[y].up;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	518
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	519 if (node[y].up == RBNULL) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	520 tree->header->root = x;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	521 } else {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	522 if (y == node[node[y].up].left)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	523 node[node[y].up].left = x;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	524 else
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	525 node[node[y].up].right = x;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	526 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	527
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	528 if (y != z) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	529 node[z].key = node[y].key;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	530 node[z].value = node[y].value;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	531 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	532
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	533 if (b != RBNULL) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	534 /* case 3 updates */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	535 while (b != x) {
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	536 NODE_COUNT_ADD(node[b], -1);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	537 b = node[b].left;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	538 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	539 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	540
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	541 while (z != RBNULL) {
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	542 NODE_COUNT_ADD(node[z], -1);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	543 z = node[z].up;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	544 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	545
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	546 if (IS_NODE_BLACK(node[y]))
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	547 rb_delete_fix(tree, x);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	548
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	549 rb_free(tree, y);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	550 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	551
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	552 #ifdef DEBUG_TREE
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	553 int
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	554 rb_check1(struct mail_tree *tree, unsigned int x)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	555 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	556 struct mail_tree_node *node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	557
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	558 if (IS_NODE_RED(node[x])) {
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	559 if (!IS_NODE_BLACK(node[node[x].left]) \|\|
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	560 !IS_NODE_BLACK(node[node[x].right])) {
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	561 i_error("Children of red node not both black, x=%u", x);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	562 return -1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	563 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	564 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	565
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	566 if (node[x].left != RBNULL) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	567 if (node[node[x].left].up != x) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	568 i_error("x->left->up != x, x=%u", x);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	569 return -1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	570 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	571
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	572 if (rb_check1(tree, node[x].left))
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	573 return -1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	574 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	575
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	576 if (node[x].right != RBNULL) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	577 if (node[node[x].right].up != x) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	578 i_error("x->right->up != x, x=%u", x);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	579 return -1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	580 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	581
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	582 if (rb_check1(tree, node[x].right))
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	583 return -1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	584 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	585
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	586 return 0;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	587 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	588
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	589 int count_black(struct mail_tree *tree, unsigned int x)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	590 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	591 struct mail_tree_node *node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	592 int nleft, nright;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	593
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	594 if (x == RBNULL)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	595 return 1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	596
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	597 nleft = count_black(tree, node[x].left);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	598 nright = count_black(tree, node[x].right);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	599
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	600 if (nleft == -1 \|\| nright == -1)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	601 return -1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	602
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	603 if (nleft != nright) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	604 i_error("Black count not equal on left & right, x=%u", x);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	605 return -1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	606 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	607
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	608 if (IS_NODE_BLACK(node[x]))
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	609 nleft++;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	610
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	611 return nleft;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	612 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	613
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	614 int count_nodes(struct mail_tree *tree, unsigned int x)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	615 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	616 struct mail_tree_node *node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	617 int nleft, nright;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	618
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	619 if (x == RBNULL)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	620 return 0;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	621
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	622 nleft = count_nodes(tree, node[x].left);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	623 nright = count_nodes(tree, node[x].right);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	624
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	625 if (nleft == -1 \|\| nright == -1)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	626 return -1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	627
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	628 if (nleft+nright+1 != (int)NODE_COUNT(node[x])) {
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	629 i_error("Invalid node count, x=%u, %d+%d+1 != %u",
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	630 x, nleft, nright, NODE_COUNT(node[x]));
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	631 return -1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	632 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	633
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	634 return nleft+nright+1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	635 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	636
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	637 void dumptree(struct mail_tree *tree, unsigned int x, int n)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	638 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	639 struct mail_tree_node *node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	640
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	641 if (x != RBNULL) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	642 n++;
799 41dde6822eea Try not to split strings to multiple lines from the middle of human readable Timo Sirainen <tss@iki.fi> parents: 539 diff changeset	643 i_error("Tree: %*s %u: left=%u, right=%u, color=%s, "
41dde6822eea Try not to split strings to multiple lines from the middle of human readable Timo Sirainen <tss@iki.fi> parents: 539 diff changeset	644 "nodes=%u, key=%u",
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	645 n, "", x, node[x].left, node[x].right,
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	646 IS_NODE_BLACK(node[x]) ? "BLACK" : "RED",
a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	647 NODE_COUNT(node[x]), node[x].key);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	648
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	649 dumptree(tree, node[x].left, n);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	650 dumptree(tree, node[x].right, n);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	651 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	652 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	653
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	654 int
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	655 rb_check(struct mail_tree *tree)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	656 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	657 struct mail_tree_node *node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	658 unsigned int root;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	659
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	660 root = tree->header->root;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	661 if (root == RBNULL)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	662 return 0;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	663
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	664 if (node[root].up != RBNULL) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	665 i_error("Root up pointer not RBNULL");
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	666 dumptree(tree, root, 0);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	667 return 1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	668 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	669
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	670 if (rb_check1(tree, root)) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	671 dumptree(tree, root, 0);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	672 return 1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	673 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	674
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	675 if (count_black(tree, root) == -1) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	676 dumptree(tree, root, 0);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	677 return -1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	678 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	679
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	680 if (count_nodes(tree, root) == -1) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	681 dumptree(tree, root, 0);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	682 return -1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	683 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	684
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	685 return 0;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	686 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	687 #endif
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	688
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	689 unsigned int mail_tree_lookup_uid_range(struct mail_tree *tree,
fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	690 unsigned int *seq_r,
389 60040a9d243f ioloop_create() takes now pool-parameter. io_buffer_create_mmaped() takes Timo Sirainen <tss@iki.fi> parents: 380 diff changeset	691 unsigned int first_uid,
60040a9d243f ioloop_create() takes now pool-parameter. io_buffer_create_mmaped() takes Timo Sirainen <tss@iki.fi> parents: 380 diff changeset	692 unsigned int last_uid)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	693 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	694 struct mail_tree_node *node;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	695 unsigned int x, y, seq;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	696
393 f09e67287f7d whops, update tree and modifylog with correct uid instead of 0. added extra Timo Sirainen <tss@iki.fi> parents: 389 diff changeset	697 i_assert(first_uid > 0 && last_uid > 0);
f09e67287f7d whops, update tree and modifylog with correct uid instead of 0. added extra Timo Sirainen <tss@iki.fi> parents: 389 diff changeset	698 i_assert(first_uid <= last_uid);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	699 i_assert(tree->index->lock_type != MAIL_LOCK_UNLOCK);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	700
488 48728d36513a Use fdatasync() instead of fsync() where possible. msync() all files first, Timo Sirainen <tss@iki.fi> parents: 453 diff changeset	701 if (!_mail_tree_mmap_update(tree, FALSE))
48728d36513a Use fdatasync() instead of fsync() where possible. msync() all files first, Timo Sirainen <tss@iki.fi> parents: 453 diff changeset	702 return (unsigned int)-1;
48728d36513a Use fdatasync() instead of fsync() where possible. msync() all files first, Timo Sirainen <tss@iki.fi> parents: 453 diff changeset	703
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	704 rb_check(tree);
512 41133ae3feb6 and correct a stupid copy&paste-bug Timo Sirainen <tss@iki.fi> parents: 511 diff changeset	705 node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	706
453 0f6fd6802265 Modify log now stores the changes in ranges, so store 1:100 doesn't Timo Sirainen <tss@iki.fi> parents: 393 diff changeset	707 if (seq_r != NULL)
0f6fd6802265 Modify log now stores the changes in ranges, so store 1:100 doesn't Timo Sirainen <tss@iki.fi> parents: 393 diff changeset	708 *seq_r = 0;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	709
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	710 y = RBNULL; /* points to the parent of x */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	711 x = tree->header->root;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	712
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	713 /* walk x down the tree */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	714 seq = 0;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	715 while (x != RBNULL) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	716 y = x;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	717
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	718 if (first_uid < node[x].key)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	719 x = node[x].left;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	720 else {
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	721 seq += NODE_COUNT(node[node[x].left])+1;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	722 if (first_uid > node[x].key)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	723 x = node[x].right;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	724 else {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	725 /* found it */
453 0f6fd6802265 Modify log now stores the changes in ranges, so store 1:100 doesn't Timo Sirainen <tss@iki.fi> parents: 393 diff changeset	726 if (seq_r != NULL)
0f6fd6802265 Modify log now stores the changes in ranges, so store 1:100 doesn't Timo Sirainen <tss@iki.fi> parents: 393 diff changeset	727 *seq_r = seq;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	728 return node[x].value;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	729 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	730 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	731 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	732
393 f09e67287f7d whops, update tree and modifylog with correct uid instead of 0. added extra Timo Sirainen <tss@iki.fi> parents: 389 diff changeset	733 if (first_uid != last_uid) {
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	734 /* get the next key, make sure it's in range */
379 b319eb0fc181 mail_tree_lookup_uid_range() still buggy if first_uid wasn't found. Timo Sirainen <tss@iki.fi> parents: 378 diff changeset	735 if (node[y].key > first_uid)
b319eb0fc181 mail_tree_lookup_uid_range() still buggy if first_uid wasn't found. Timo Sirainen <tss@iki.fi> parents: 378 diff changeset	736 x = y;
b319eb0fc181 mail_tree_lookup_uid_range() still buggy if first_uid wasn't found. Timo Sirainen <tss@iki.fi> parents: 378 diff changeset	737 else
b319eb0fc181 mail_tree_lookup_uid_range() still buggy if first_uid wasn't found. Timo Sirainen <tss@iki.fi> parents: 378 diff changeset	738 x = rb_successor(tree, y);
b319eb0fc181 mail_tree_lookup_uid_range() still buggy if first_uid wasn't found. Timo Sirainen <tss@iki.fi> parents: 378 diff changeset	739
378 225d515edaa1 sequence number still wasn't right always Timo Sirainen <tss@iki.fi> parents: 375 diff changeset	740 if (node[x].key > last_uid)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	741 x = RBNULL;
453 0f6fd6802265 Modify log now stores the changes in ranges, so store 1:100 doesn't Timo Sirainen <tss@iki.fi> parents: 393 diff changeset	742 else {
0f6fd6802265 Modify log now stores the changes in ranges, so store 1:100 doesn't Timo Sirainen <tss@iki.fi> parents: 393 diff changeset	743 if (seq_r != NULL)
0f6fd6802265 Modify log now stores the changes in ranges, so store 1:100 doesn't Timo Sirainen <tss@iki.fi> parents: 393 diff changeset	744 *seq_r = seq+1;
0f6fd6802265 Modify log now stores the changes in ranges, so store 1:100 doesn't Timo Sirainen <tss@iki.fi> parents: 393 diff changeset	745 }
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	746 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	747
389 60040a9d243f ioloop_create() takes now pool-parameter. io_buffer_create_mmaped() takes Timo Sirainen <tss@iki.fi> parents: 380 diff changeset	748 return x == RBNULL ? (unsigned int)-1 : node[x].value;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	749 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	750
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	751 unsigned int mail_tree_lookup_sequence(struct mail_tree *tree, unsigned int seq)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	752 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	753 struct mail_tree_node *node;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	754 unsigned int x, upleft_nodes, left_nodes;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	755
393 f09e67287f7d whops, update tree and modifylog with correct uid instead of 0. added extra Timo Sirainen <tss@iki.fi> parents: 389 diff changeset	756 i_assert(seq != 0);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	757 i_assert(tree->index->lock_type != MAIL_LOCK_UNLOCK);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	758
488 48728d36513a Use fdatasync() instead of fsync() where possible. msync() all files first, Timo Sirainen <tss@iki.fi> parents: 453 diff changeset	759 if (!_mail_tree_mmap_update(tree, FALSE))
48728d36513a Use fdatasync() instead of fsync() where possible. msync() all files first, Timo Sirainen <tss@iki.fi> parents: 453 diff changeset	760 return (unsigned int)-1;
48728d36513a Use fdatasync() instead of fsync() where possible. msync() all files first, Timo Sirainen <tss@iki.fi> parents: 453 diff changeset	761
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	762 rb_check(tree);
511 10d6c1cb6511 Set node variable after mmap updating which may change it.. Timo Sirainen <tss@iki.fi> parents: 498 diff changeset	763 node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	764
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	765 x = tree->header->root;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	766
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	767 /* walk x down the tree */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	768 seq--;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	769 upleft_nodes = left_nodes = 0;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	770 while (x != RBNULL) {
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	771 left_nodes = upleft_nodes + NODE_COUNT(node[node[x].left]);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	772
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	773 if (seq < left_nodes)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	774 x = node[x].left;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	775 else if (seq > left_nodes) {
359 9fd132e47845 bugfixes Timo Sirainen <tss@iki.fi> parents: 357 diff changeset	776 upleft_nodes = left_nodes+1;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	777 x = node[x].right;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	778 } else {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	779 /* found it */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	780 return node[x].value;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	781 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	782 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	783
389 60040a9d243f ioloop_create() takes now pool-parameter. io_buffer_create_mmaped() takes Timo Sirainen <tss@iki.fi> parents: 380 diff changeset	784 return (unsigned int)-1;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	785 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	786
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	787 int mail_tree_insert(struct mail_tree *tree,
fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	788 unsigned int uid, unsigned int index)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	789 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	790 struct mail_tree_node *node;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	791 unsigned int x, z;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	792
393 f09e67287f7d whops, update tree and modifylog with correct uid instead of 0. added extra Timo Sirainen <tss@iki.fi> parents: 389 diff changeset	793 i_assert(uid != 0);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	794 i_assert(tree->index->lock_type == MAIL_LOCK_EXCLUSIVE);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	795
488 48728d36513a Use fdatasync() instead of fsync() where possible. msync() all files first, Timo Sirainen <tss@iki.fi> parents: 453 diff changeset	796 if (!_mail_tree_mmap_update(tree, FALSE))
48728d36513a Use fdatasync() instead of fsync() where possible. msync() all files first, Timo Sirainen <tss@iki.fi> parents: 453 diff changeset	797 return FALSE;
48728d36513a Use fdatasync() instead of fsync() where possible. msync() all files first, Timo Sirainen <tss@iki.fi> parents: 453 diff changeset	798
511 10d6c1cb6511 Set node variable after mmap updating which may change it.. Timo Sirainen <tss@iki.fi> parents: 498 diff changeset	799 node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	800
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	801 /* we'll always insert to right side of the tree */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	802 x = tree->header->root;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	803 if (x != RBNULL) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	804 while (node[x].right != RBNULL)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	805 x = node[x].right;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	806 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	807
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	808 if (node[x].key >= uid) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	809 _mail_tree_set_corrupted(tree,
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	810 "UID to be inserted isn't higher than existing "
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	811 "(%u <= %u)", uid, node[x].key);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	812 return FALSE;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	813 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	814
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	815 if ((z = rb_alloc(tree)) == RBNULL)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	816 return FALSE;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	817
356 a39343e9e197 crashfix when growing tree file size Timo Sirainen <tss@iki.fi> parents: 355 diff changeset	818 /* rb_alloc() may change mmap base */
a39343e9e197 crashfix when growing tree file size Timo Sirainen <tss@iki.fi> parents: 355 diff changeset	819 node = tree->node_base;
a39343e9e197 crashfix when growing tree file size Timo Sirainen <tss@iki.fi> parents: 355 diff changeset	820
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	821 node[z].key = uid;
389 60040a9d243f ioloop_create() takes now pool-parameter. io_buffer_create_mmaped() takes Timo Sirainen <tss@iki.fi> parents: 380 diff changeset	822 node[z].value = index;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	823 node[z].up = x;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	824 node[z].node_count = 1;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	825 node[z].left = RBNULL;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	826 node[z].right = RBNULL;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	827
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	828 if (x == RBNULL)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	829 tree->header->root = z;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	830 else {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	831 if (node[z].key < node[x].key)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	832 node[x].left = z;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	833 else
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	834 node[x].right = z;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	835 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	836
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	837 for (; x != RBNULL; x = node[x].up)
539 a182d31b46cd node color needs only one bit, not a full 32bit integer. so moved it to Timo Sirainen <tss@iki.fi> parents: 512 diff changeset	838 NODE_COUNT_ADD(node[x], 1);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	839
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	840 rb_insert_fix(tree, z);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	841 rb_check(tree);
511 10d6c1cb6511 Set node variable after mmap updating which may change it.. Timo Sirainen <tss@iki.fi> parents: 498 diff changeset	842
10d6c1cb6511 Set node variable after mmap updating which may change it.. Timo Sirainen <tss@iki.fi> parents: 498 diff changeset	843 tree->modified = TRUE;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	844 return TRUE;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	845 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	846
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	847 int mail_tree_update(struct mail_tree *tree,
fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	848 unsigned int uid, unsigned int index)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	849 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	850 struct mail_tree_node *node;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	851 unsigned int x;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	852
393 f09e67287f7d whops, update tree and modifylog with correct uid instead of 0. added extra Timo Sirainen <tss@iki.fi> parents: 389 diff changeset	853 i_assert(uid != 0);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	854 i_assert(tree->index->lock_type == MAIL_LOCK_EXCLUSIVE);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	855
488 48728d36513a Use fdatasync() instead of fsync() where possible. msync() all files first, Timo Sirainen <tss@iki.fi> parents: 453 diff changeset	856 if (!_mail_tree_mmap_update(tree, FALSE))
48728d36513a Use fdatasync() instead of fsync() where possible. msync() all files first, Timo Sirainen <tss@iki.fi> parents: 453 diff changeset	857 return FALSE;
48728d36513a Use fdatasync() instead of fsync() where possible. msync() all files first, Timo Sirainen <tss@iki.fi> parents: 453 diff changeset	858
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	859 rb_check(tree);
511 10d6c1cb6511 Set node variable after mmap updating which may change it.. Timo Sirainen <tss@iki.fi> parents: 498 diff changeset	860 node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	861
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	862 tree->modified = TRUE;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	863
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	864 x = tree->header->root;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	865 while (x != RBNULL) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	866 if (uid < node[x].key)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	867 x = node[x].left;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	868 else if (uid > node[x].key)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	869 x = node[x].right;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	870 else {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	871 /* found it */
389 60040a9d243f ioloop_create() takes now pool-parameter. io_buffer_create_mmaped() takes Timo Sirainen <tss@iki.fi> parents: 380 diff changeset	872 node[x].value = index;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	873 return TRUE;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	874 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	875 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	876
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	877 _mail_tree_set_corrupted(tree, "Tried to update nonexisting UID %u",
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	878 uid);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	879 return FALSE;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	880 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	881
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	882 void mail_tree_delete(struct mail_tree *tree, unsigned int uid)
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	883 {
903 fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the Timo Sirainen <tss@iki.fi> parents: 799 diff changeset	884 struct mail_tree_node *node;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	885 unsigned int x;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	886
393 f09e67287f7d whops, update tree and modifylog with correct uid instead of 0. added extra Timo Sirainen <tss@iki.fi> parents: 389 diff changeset	887 i_assert(uid != 0);
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	888 i_assert(tree->index->lock_type == MAIL_LOCK_EXCLUSIVE);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	889
488 48728d36513a Use fdatasync() instead of fsync() where possible. msync() all files first, Timo Sirainen <tss@iki.fi> parents: 453 diff changeset	890 if (!_mail_tree_mmap_update(tree, FALSE))
48728d36513a Use fdatasync() instead of fsync() where possible. msync() all files first, Timo Sirainen <tss@iki.fi> parents: 453 diff changeset	891 return;
48728d36513a Use fdatasync() instead of fsync() where possible. msync() all files first, Timo Sirainen <tss@iki.fi> parents: 453 diff changeset	892
511 10d6c1cb6511 Set node variable after mmap updating which may change it.. Timo Sirainen <tss@iki.fi> parents: 498 diff changeset	893 node = tree->node_base;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	894
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	895 x = tree->header->root;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	896 while (x != RBNULL) {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	897 if (uid < node[x].key)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	898 x = node[x].left;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	899 else if (uid > node[x].key)
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	900 x = node[x].right;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	901 else {
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	902 /* found it */
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	903 rb_delete(tree, x);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	904 rb_check(tree);
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	905 break;
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	906 }
0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	907 }
511 10d6c1cb6511 Set node variable after mmap updating which may change it.. Timo Sirainen <tss@iki.fi> parents: 498 diff changeset	908
10d6c1cb6511 Set node variable after mmap updating which may change it.. Timo Sirainen <tss@iki.fi> parents: 498 diff changeset	909 tree->modified = TRUE;
355 0dc59fd3faed First version of binary tree file, still some locking issues while opening Timo Sirainen <tss@iki.fi> parents: diff changeset	910 }

Mercurial > dovecot > original-hg > dovecot-1.2

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