rbtree.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	rb_entry
struct	rb_tree

Macros
#define	RB_ENTRY_VALUE(element, type, field)    ((type *)((char *)(element) - offsetof(type, field)))
#define	RB_FLAG_RED   0x1
#define	RB_FOR_EACH(cursor, tree)    for ((cursor) = rb_head((tree)->root); (cursor); (cursor) = rb_next(cursor))
#define	RB_FOR_EACH_ENTRY(elem, tree, type, field)
#define	RB_FOR_EACH_DESTRUCTOR(cursor, cursor2, tree)
#define	RB_FOR_EACH_ENTRY_DESTRUCTOR(elem, elem2, tree, type, field)
#define	wine_rb_entry   rb_entry
#define	wine_rb_tree   rb_tree
#define	wine_rb_init   rb_init
#define	wine_rb_for_each_entry   rb_for_each_entry
#define	wine_rb_destroy   rb_destroy
#define	wine_rb_get   rb_get
#define	wine_rb_put   rb_put
#define	wine_rb_remove   rb_remove
#define	wine_rb_remove_key   rb_remove_key
#define	wine_rb_replace   rb_replace
#define	WINE_RB_ENTRY_VALUE   RB_ENTRY_VALUE
#define	WINE_RB_FOR_EACH_ENTRY   RB_FOR_EACH_ENTRY
#define	WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR   RB_FOR_EACH_ENTRY_DESTRUCTOR

Typedefs
typedef int(*	rb_compare_func_t) (const void *key, const struct rb_entry *entry)
typedef void()	rb_traverse_func_t(struct rb_entry *entry, void *context)

Functions
static int	rb_is_red (struct rb_entry *entry)
static void	rb_rotate_left (struct rb_tree *tree, struct rb_entry *e)
static void	rb_rotate_right (struct rb_tree *tree, struct rb_entry *e)
static void	rb_flip_color (struct rb_entry *entry)
static struct rb_entry *	rb_head (struct rb_entry *iter)
static struct rb_entry *	rb_tail (struct rb_entry *iter)
static struct rb_entry *	rb_next (struct rb_entry *iter)
static struct rb_entry *	rb_prev (struct rb_entry *iter)
static struct rb_entry *	rb_postorder_head (struct rb_entry *iter)
static struct rb_entry *	rb_postorder_next (struct rb_entry *iter)
static void	rb_postorder (struct rb_tree *tree, rb_traverse_func_t *callback, void *context)
static void	rb_init (struct rb_tree *tree, rb_compare_func_t compare)
static void	rb_for_each_entry (struct rb_tree *tree, rb_traverse_func_t *callback, void *context)
static void	rb_destroy (struct rb_tree *tree, rb_traverse_func_t *callback, void *context)
static struct rb_entry *	rb_get (const struct rb_tree *tree, const void *key)
static int	rb_put (struct rb_tree *tree, const void *key, struct rb_entry *entry)
static void	rb_remove (struct rb_tree *tree, struct rb_entry *entry)
static void	rb_remove_key (struct rb_tree *tree, const void *key)
static void	rb_replace (struct rb_tree *tree, struct rb_entry *dst, struct rb_entry *src)

Macro Definition Documentation

RB_ENTRY_VALUE

#define RB_ENTRY_VALUE	(		element,
			type,
			field
	)		((type *)((char *)(element) - offsetof(type, field)))

Definition at line 26 of file rbtree.h.

RB_FLAG_RED

#define RB_FLAG_RED   0x1

Definition at line 47 of file rbtree.h.

RB_FOR_EACH

#define RB_FOR_EACH	(		cursor,
			tree
	)		for ((cursor) = rb_head((tree)->root); (cursor); (cursor) = rb_next(cursor))

Definition at line 144 of file rbtree.h.

RB_FOR_EACH_DESTRUCTOR

#define RB_FOR_EACH_DESTRUCTOR	(		cursor,
			cursor2,
			tree
	)

Value:

    for ((cursor) = rb_postorder_head((tree)->root); \
         (cursor) && (((cursor2) = rb_postorder_next(cursor)) || 1); \
         (cursor) = (cursor2))

Definition at line 154 of file rbtree.h.

RB_FOR_EACH_ENTRY

#define RB_FOR_EACH_ENTRY	(		elem,
			tree,
			type,
			field
	)

Value:

    for ((elem) = RB_ENTRY_VALUE(rb_head((tree)->root), type, field); \
         (elem) != RB_ENTRY_VALUE(0, type, field); \
         (elem) = RB_ENTRY_VALUE(rb_next(&elem->field), type, field))

Definition at line 148 of file rbtree.h.

RB_FOR_EACH_ENTRY_DESTRUCTOR

#define RB_FOR_EACH_ENTRY_DESTRUCTOR	(		elem,
			elem2,
			tree,
			type,
			field
	)

Value:

    for ((elem) = RB_ENTRY_VALUE(rb_postorder_head((tree)->root), type, field); \
         (elem) != RB_ENTRY_VALUE(0, type, field) \
             && (((elem2) = RB_ENTRY_VALUE(rb_postorder_next(&(elem)->field), type, field)) || 1); \
         (elem) = (elem2))

Definition at line 160 of file rbtree.h.

wine_rb_destroy

#define wine_rb_destroy   rb_destroy

Definition at line 408 of file rbtree.h.

wine_rb_entry

#define wine_rb_entry   rb_entry

Definition at line 404 of file rbtree.h.

WINE_RB_ENTRY_VALUE

#define WINE_RB_ENTRY_VALUE   RB_ENTRY_VALUE

Definition at line 414 of file rbtree.h.

wine_rb_for_each_entry

#define wine_rb_for_each_entry   rb_for_each_entry

Definition at line 407 of file rbtree.h.

WINE_RB_FOR_EACH_ENTRY

#define WINE_RB_FOR_EACH_ENTRY   RB_FOR_EACH_ENTRY

Definition at line 415 of file rbtree.h.

WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR

#define WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR   RB_FOR_EACH_ENTRY_DESTRUCTOR

Definition at line 416 of file rbtree.h.

wine_rb_get

#define wine_rb_get   rb_get

Definition at line 409 of file rbtree.h.

wine_rb_init

#define wine_rb_init   rb_init

Definition at line 406 of file rbtree.h.

wine_rb_put

#define wine_rb_put   rb_put

Definition at line 410 of file rbtree.h.

wine_rb_remove

#define wine_rb_remove   rb_remove

Definition at line 411 of file rbtree.h.

wine_rb_remove_key

#define wine_rb_remove_key   rb_remove_key

Definition at line 412 of file rbtree.h.

wine_rb_replace

#define wine_rb_replace   rb_replace

Definition at line 413 of file rbtree.h.

wine_rb_tree

#define wine_rb_tree   rb_tree

Definition at line 405 of file rbtree.h.

Typedef Documentation

rb_compare_func_t

typedef int(* rb_compare_func_t) (const void *key, const struct rb_entry *entry)

Definition at line 37 of file rbtree.h.

rb_traverse_func_t

typedef void() rb_traverse_func_t(struct rb_entry *entry, void *context)

Definition at line 45 of file rbtree.h.

Function Documentation

rb_destroy()

static void rb_destroy ( struct rb_tree *  tree, rb_traverse_func_t *  callback, void *  context  )

inlinestatic

Definition at line 185 of file rbtree.h.

{
    /* Note that we use postorder here because the callback will likely free the entry. */
    if (callback) rb_postorder(tree, callback, context);
    tree->root = NULL;
}

rb_flip_color()

static void rb_flip_color ( struct rb_entry *  entry )

inlinestatic

Definition at line 90 of file rbtree.h.

{
    entry->flags ^= RB_FLAG_RED;
    entry->left->flags ^= RB_FLAG_RED;
    entry->right->flags ^= RB_FLAG_RED;
}

Referenced by rb_put().

rb_for_each_entry()

static void rb_for_each_entry ( struct rb_tree *  tree, rb_traverse_func_t *  callback, void *  context  )

inlinestatic

Definition at line 179 of file rbtree.h.

{
    struct rb_entry *iter;
    RB_FOR_EACH(iter, tree) callback(iter, context);
}

rb_get()

static struct rb_entry * rb_get ( const struct rb_tree *  tree, const void *  key  )

inlinestatic

Definition at line 192 of file rbtree.h.

{
    struct rb_entry *entry = tree->root;
    while (entry)
    {
        int c = tree->compare(key, entry);
        if (!c) return entry;
        entry = c < 0 ? entry->left : entry->right;
    }
    return NULL;
}

Referenced by rb_remove_key().

rb_head()

static struct rb_entry * rb_head ( struct rb_entry *  iter )

inlinestatic

Definition at line 97 of file rbtree.h.

{
    if (!iter) return NULL;
    while (iter->left) iter = iter->left;
    return iter;
}

Referenced by rb_next(), and wrap_marked_paras_dc().

rb_init()

static void rb_init ( struct rb_tree *  tree, rb_compare_func_t  compare  )

inlinestatic

Definition at line 173 of file rbtree.h.

{
    tree->compare = compare;
    tree->root = NULL;
}

rb_is_red()

static int rb_is_red ( struct rb_entry *  entry )

inlinestatic

Definition at line 49 of file rbtree.h.

{
    return entry && (entry->flags & RB_FLAG_RED);
}

rb_next()

static struct rb_entry * rb_next ( struct rb_entry *  iter )

inlinestatic

Definition at line 111 of file rbtree.h.

{
    if (iter->right) return rb_head(iter->right);
    while (iter->parent && iter->parent->right == iter) iter = iter->parent;
    return iter->parent;
}

rb_postorder()

static void rb_postorder ( struct rb_tree *  tree, rb_traverse_func_t *  callback, void *  context  )

inlinestatic

Definition at line 167 of file rbtree.h.

{
    struct rb_entry *iter, *next;
    RB_FOR_EACH_DESTRUCTOR(iter, next, tree) callback(iter, context);
}

Referenced by rb_destroy().

rb_postorder_head()

static struct rb_entry * rb_postorder_head ( struct rb_entry *  iter )

inlinestatic

Definition at line 125 of file rbtree.h.

{
    if (!iter) return NULL;
 
    for (;;) {
        while (iter->left) iter = iter->left;
        if (!iter->right) return iter;
        iter = iter->right;
    }
}

Referenced by rb_postorder_next().

rb_postorder_next()

static struct rb_entry * rb_postorder_next ( struct rb_entry *  iter )

inlinestatic

Definition at line 136 of file rbtree.h.

{
    if (!iter->parent) return NULL;
    if (iter == iter->parent->right || !iter->parent->right) return iter->parent;
    return rb_postorder_head(iter->parent->right);
}

rb_prev()

static struct rb_entry * rb_prev ( struct rb_entry *  iter )

inlinestatic

Definition at line 118 of file rbtree.h.

{
    if (iter->left) return rb_tail(iter->left);
    while (iter->parent && iter->parent->left == iter) iter = iter->parent;
    return iter->parent;
}

rb_put()

static int rb_put ( struct rb_tree *  tree, const void *  key, struct rb_entry *  entry  )

inlinestatic

Definition at line 204 of file rbtree.h.

{
    struct rb_entry **iter = &tree->root, *parent = tree->root;
 
    while (*iter)
    {
        int c;
 
        parent = *iter;
        c = tree->compare(key, parent);
        if (!c) return -1;
        else if (c < 0) iter = &parent->left;
        else iter = &parent->right;
    }
 
    entry->flags = RB_FLAG_RED;
    entry->parent = parent;
    entry->left = NULL;
    entry->right = NULL;
    *iter = entry;
 
    while (rb_is_red(entry->parent))
    {
        if (entry->parent == entry->parent->parent->left)
        {
            if (rb_is_red(entry->parent->parent->right))
            {
                rb_flip_color(entry->parent->parent);
                entry = entry->parent->parent;
            }
            else
            {
                if (entry == entry->parent->right)
                {
                    entry = entry->parent;
                    rb_rotate_left(tree, entry);
                }
                entry->parent->flags &= ~RB_FLAG_RED;
                entry->parent->parent->flags |= RB_FLAG_RED;
                rb_rotate_right(tree, entry->parent->parent);
            }
        }
        else
        {
            if (rb_is_red(entry->parent->parent->left))
            {
                rb_flip_color(entry->parent->parent);
                entry = entry->parent->parent;
            }
            else
            {
                if (entry == entry->parent->left)
                {
                    entry = entry->parent;
                    rb_rotate_right(tree, entry);
                }
                entry->parent->flags &= ~RB_FLAG_RED;
                entry->parent->parent->flags |= RB_FLAG_RED;
                rb_rotate_left(tree, entry->parent->parent);
            }
        }
    }
 
    tree->root->flags &= ~RB_FLAG_RED;
 
    return 0;
}

rb_remove()

static void rb_remove ( struct rb_tree *  tree, struct rb_entry *  entry  )

inlinestatic

Definition at line 272 of file rbtree.h.

{
    struct rb_entry *iter, *child, *parent, *w;
    int need_fixup;
 
    if (entry->right && entry->left)
        for(iter = entry->right; iter->left; iter = iter->left);
    else
        iter = entry;
 
    child = iter->left ? iter->left : iter->right;
 
    if (!iter->parent)
        tree->root = child;
    else if (iter == iter->parent->left)
        iter->parent->left = child;
    else
        iter->parent->right = child;
 
    if (child) child->parent = iter->parent;
    parent = iter->parent;
 
    need_fixup = !rb_is_red(iter);
 
    if (entry != iter)
    {
        *iter = *entry;
        if (!iter->parent)
            tree->root = iter;
        else if (entry == iter->parent->left)
            iter->parent->left = iter;
        else
            iter->parent->right = iter;
 
        if (iter->right) iter->right->parent = iter;
        if (iter->left)  iter->left->parent = iter;
        if (parent == entry) parent = iter;
    }
 
    if (need_fixup)
    {
        while (parent && !rb_is_red(child))
        {
            if (child == parent->left)
            {
                w = parent->right;
                if (rb_is_red(w))
                {
                    w->flags &= ~RB_FLAG_RED;
                    parent->flags |= RB_FLAG_RED;
                    rb_rotate_left(tree, parent);
                    w = parent->right;
                }
                if (rb_is_red(w->left) || rb_is_red(w->right))
                {
                    if (!rb_is_red(w->right))
                    {
                        w->left->flags &= ~RB_FLAG_RED;
                        w->flags |= RB_FLAG_RED;
                        rb_rotate_right(tree, w);
                        w = parent->right;
                    }
                    w->flags = (w->flags & ~RB_FLAG_RED) | (parent->flags & RB_FLAG_RED);
                    parent->flags &= ~RB_FLAG_RED;
                    if (w->right)
                        w->right->flags &= ~RB_FLAG_RED;
                    rb_rotate_left(tree, parent);
                    child = NULL;
                    break;
                }
            }
            else
            {
                w = parent->left;
                if (rb_is_red(w))
                {
                    w->flags &= ~RB_FLAG_RED;
                    parent->flags |= RB_FLAG_RED;
                    rb_rotate_right(tree, parent);
                    w = parent->left;
                }
                if (rb_is_red(w->left) || rb_is_red(w->right))
                {
                    if (!rb_is_red(w->left))
                    {
                        w->right->flags &= ~RB_FLAG_RED;
                        w->flags |= RB_FLAG_RED;
                        rb_rotate_left(tree, w);
                        w = parent->left;
                    }
                    w->flags = (w->flags & ~RB_FLAG_RED) | (parent->flags & RB_FLAG_RED);
                    parent->flags &= ~RB_FLAG_RED;
                    if (w->left)
                        w->left->flags &= ~RB_FLAG_RED;
                    rb_rotate_right(tree, parent);
                    child = NULL;
                    break;
                }
            }
            w->flags |= RB_FLAG_RED;
            child = parent;
            parent = child->parent;
        }
        if (child) child->flags &= ~RB_FLAG_RED;
    }
 
    if (tree->root) tree->root->flags &= ~RB_FLAG_RED;
}

Referenced by rb_remove_key().

rb_remove_key()

static void rb_remove_key ( struct rb_tree *  tree, const void *  key  )

inlinestatic

Definition at line 381 of file rbtree.h.

{
    struct rb_entry *entry = rb_get(tree, key);
    if (entry) rb_remove(tree, entry);
}

rb_replace()

static void rb_replace ( struct rb_tree *  tree, struct rb_entry *  dst, struct rb_entry *  src  )

inlinestatic

Definition at line 387 of file rbtree.h.

{
    if (!(src->parent = dst->parent))
        tree->root = src;
    else if (dst->parent->left == dst)
        dst->parent->left = src;
    else
        dst->parent->right = src;
 
    if ((src->left = dst->left))
        src->left->parent = src;
    if ((src->right = dst->right))
        src->right->parent = src;
    src->flags = dst->flags;
}

rb_rotate_left()

static void rb_rotate_left ( struct rb_tree *  tree, struct rb_entry *  e  )

inlinestatic

Definition at line 54 of file rbtree.h.

{
    struct rb_entry *right = e->right;
 
    if (!e->parent)
        tree->root = right;
    else if (e->parent->left == e)
        e->parent->left = right;
    else
        e->parent->right = right;
 
    e->right = right->left;
    if (e->right) e->right->parent = e;
    right->left = e;
    right->parent = e->parent;
    e->parent = right;
}

Referenced by rb_put(), and rb_remove().

rb_rotate_right()

static void rb_rotate_right ( struct rb_tree *  tree, struct rb_entry *  e  )

inlinestatic

Definition at line 72 of file rbtree.h.

{
    struct rb_entry *left = e->left;
 
    if (!e->parent)
        tree->root = left;
    else if (e->parent->left == e)
        e->parent->left = left;
    else
        e->parent->right = left;
 
    e->left = left->right;
    if (e->left) e->left->parent = e;
    left->right = e;
    left->parent = e->parent;
    e->parent = left;
}

Referenced by rb_put(), and rb_remove().

rb_tail()

static struct rb_entry * rb_tail ( struct rb_entry *  iter )

inlinestatic

Definition at line 104 of file rbtree.h.

{
    if (!iter) return NULL;
    while (iter->right) iter = iter->right;
    return iter;
}

Referenced by rb_prev().