mail-tree-redblack.c revision 6403608174a11d00ad94bccb1dfb84e2ce720357
/*
Redblack balanced tree algorithm, http://libredblack.sourceforge.net/
Copyright (C) Damian Ivereigh 2000
Modified to be suitable for mmap()ing and for IMAP server
Copyright (C) Timo Sirainen 2002
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version. See the file COPYING for details.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU Lesser General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
#include "lib.h"
#include "mail-index.h"
#include "mail-tree.h"
/* #define DEBUG_TREE */
#ifndef DEBUG_TREE
#endif
/* Dummy (sentinel) node, so that we can make X->left->up = X
** We then use this instead of NULL to mean the top or bottom
** end of the rb tree. It is a black node.
*/
#define RBNULL 0
/*
** OK here we go, the balanced tree stuff. The algorithm is the
** by Cormen, Leiserson & Rivest. Maybe one of these days I will
** fully understand all this stuff.
**
** 1) Every node is either red or black (color is RED or BLACK)
** 2) A leaf (RBNULL pointer) is considered black
** 3) If a node is red then its children are black
** 4) Every path from a node to a leaf contains the same no
** of black nodes
**
** 3) & 4) above guarantee that the longest path (alternating
** red and black nodes) is only twice as long as the shortest
** path (all black nodes). Thus the tree remains fairly balanced.
*/
static unsigned int
{
unsigned int x;
/* use the nodes in the middle of the file */
return x;
}
/* use nodes at the end of file */
if (!_mail_tree_grow(tree))
return RBNULL;
}
sizeof(MailTreeNode) - 1;
}
static void
{
}
/*
** Rotate our tree thus:-
**
** X rb_left_rotate(X)---> Y
** / \ / \
** A Y <---rb_right_rotate(Y) X C
** / \ / \
** B C A B
**
** N.B. This does not change the ordering.
**
** We assume that neither X or Y is NULL
**
** Node count changes:
** X += C+1 X -= C+1
** Y -= A+1 Y += A+1
*/
static void
{
/* Turn Y's left subtree into X's right subtree (move B) */
/* If B is not null, set it's parent to be X */
/* Set Y's parent to be what X's parent was */
/* if X was the root */
} else {
/* Set X's parent's left or right pointer to be Y */
else
}
/* Put X on Y's left */
/* Set X's parent to be Y */
/* Update node counts */
}
static void
{
/* Turn X's right subtree into Y's left subtree (move B) */
/* If B is not null, set it's parent to be Y */
/* Set X's parent to be what Y's parent was */
/* if Y was the root */
else {
/* Set Y's parent's left or right pointer to be X */
else
}
/* Put Y on X's right */
/* Set Y's parent to be X */
/* Update node counts */
}
/* Return index to the smallest key greater than x
*/
static unsigned int
{
unsigned int y;
/* If right is not NULL then go right one and
** then keep going left until we find a node with
** no left pointer.
*/
} else {
/* Go up the tree until we get to a node that is on the
** left of its parent (or the root) and then return the
** parent.
*/
x = y;
}
}
return y;
}
/* Restore the reb-black properties after insert */
static int
{
unsigned int x, y, x_up_up;
/* color this new node red */
/* Having added a red node, we must now walk back up the tree balancing
** it, by a series of rotations and changing of colors
*/
x = z;
/* While we are not at the top and our parent node is red
** N.B. Since the root node is garanteed black, then we
** are also going to stop if we are the child of the root
*/
/* if our parent is on the left side of our grandparent */
/* get the right side of our grandparent (uncle?) */
/* make our parent black */
/* make our uncle black */
/* make our grandparent red */
/* now consider our grandparent */
x = x_up_up;
} else {
/* if we are on the right side of our parent */
/* Move up to our parent */
rb_left_rotate(tree, x);
}
/* make our parent black */
/* make our grandparent red */
/* right rotate our grandparent */
}
} else {
/* everything here is the same as above, but
** exchanging left for right
*/
x = x_up_up;
} else {
rb_right_rotate(tree, x);
}
}
}
}
/* Set the root node black */
return z;
}
/* Restore the reb-black properties after a delete */
static void
{
unsigned int w;
}
} else {
rb_right_rotate(tree, w);
}
}
} else {
}
} else {
rb_left_rotate(tree, w);
}
}
}
}
}
/*
** case 1 - only one child:
**
** Z --> Y
** /
** Y
**
** Node count changes:
** parents -= 1
**
** case 2 - right child has no left child:
**
** Z Y
** / \ / \
** A Y --> A X
** \
** X
**
** Node count changes:
** parents -= 1
** Y = Z-1
**
** case 3 - right child has left child:
**
** Z Y
** / \ / \
** A B --> A B
** / /
** .. ..
** / /
** Y X
** \
** X
**
** Node count changes:
** parents -= 1
** Y = Z-1
** B .. X.up -= 1 (NOTE: X may not exist)
*/
/* Delete the node z, and free up the space
*/
static void
{
unsigned int x, y, b;
y = z;
b = RBNULL;
} else {
y = rb_successor(tree, z);
b = RBNULL;
else
}
else
/* this may modify RBNULL, which IMHO is a bit nasty,
but rb_delete_fix() requires it to work properly. */
} else {
else
}
if (y != z) {
}
if (b != RBNULL) {
/* case 3 updates */
while (b != x) {
node[b].node_count--;
}
}
while (z != RBNULL) {
node[z].node_count--;
}
rb_delete_fix(tree, x);
}
#ifdef DEBUG_TREE
int
{
i_error("Children of red node not both black, x=%u", x);
return -1;
}
}
i_error("x->left->up != x, x=%u", x);
return -1;
}
return -1;
}
i_error("x->right->up != x, x=%u", x);
return -1;
}
return -1;
}
return 0;
}
{
if (x == RBNULL)
return 1;
return -1;
i_error("Black count not equal on left & right, x=%u", x);
return -1;
}
nleft++;
return nleft;
}
{
if (x == RBNULL)
return 0;
return -1;
i_error("Invalid node count, x=%u, %d+%d+1 != %u",
return -1;
}
}
{
if (x != RBNULL) {
n++;
i_error("Tree: %*s %u: left=%u, right=%u, color=%s, nodes=%u, key=%u",
}
}
int
{
unsigned int root;
return 0;
i_error("Root up pointer not RBNULL");
return 1;
}
return 1;
}
return -1;
}
return -1;
}
return 0;
}
#endif
unsigned int first_uid,
unsigned int last_uid)
{
unsigned int x, y, seq;
*seq_r = 0;
y = RBNULL; /* points to the parent of x */
/* walk x down the tree */
seq = 0;
while (x != RBNULL) {
y = x;
else {
else {
/* found it */
}
}
}
/* get the next key, make sure it's in range */
x = y;
else
x = rb_successor(tree, y);
x = RBNULL;
else
}
}
{
unsigned int x, upleft_nodes, left_nodes;
/* walk x down the tree */
seq--;
upleft_nodes = left_nodes = 0;
while (x != RBNULL) {
if (seq < left_nodes)
else if (seq > left_nodes) {
} else {
/* found it */
}
}
return (unsigned int)-1;
}
{
unsigned int x, z;
/* we'll always insert to right side of the tree */
if (x != RBNULL) {
}
"UID to be inserted isn't higher than existing "
return FALSE;
}
return FALSE;
/* rb_alloc() may change mmap base */
if (x == RBNULL)
else {
else
}
node[x].node_count++;
rb_insert_fix(tree, z);
return TRUE;
}
{
unsigned int x;
while (x != RBNULL) {
else {
/* found it */
return TRUE;
}
}
uid);
return FALSE;
}
{
unsigned int x;
while (x != RBNULL) {
else {
/* found it */
break;
}
}
}