[PATCH] convert file_info from singlely-linked list to rbtree
now filenames are sorted via tree-sort to increase determinism in builds
lookup (was only used in check_conffiles()) is now O(log(n)) instead
of O(n)
The license of libtree is a bit funny: _Library_ GPL _2_ (which doesn't exist)
I have asked upstream for clarification on this:
https://github.com/fbuihuu/libtree/issues/7
---
dpkg-deb/Makefile.am | 1 +
dpkg-deb/build.c | 110 ++++++------
dpkg-deb/libtree.h | 218 +++++++++++++++++++++++
dpkg-deb/rb.c | 485 +++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 760 insertions(+), 54 deletions(-)
create mode 100644 dpkg-deb/libtree.h
create mode 100644 dpkg-deb/rb.c
diff --git a/dpkg-deb/Makefile.am b/dpkg-deb/Makefile.am
index 6b66d3e..772c8c0 100644
--- a/dpkg-deb/Makefile.am
+++ b/dpkg-deb/Makefile.am
@@ -12,6 +12,7 @@ bin_PROGRAMS = dpkg-deb
dpkg_deb_SOURCES = \
dpkg-deb.h \
+ rb.c \
build.c \
extract.c \
info.c \
diff --git a/dpkg-deb/build.c b/dpkg-deb/build.c
index 348e01e..061a237 100644
--- a/dpkg-deb/build.c
+++ b/dpkg-deb/build.c
@@ -52,12 +52,13 @@
#include <dpkg/options.h>
#include "dpkg-deb.h"
+#include "libtree.h"
/**
* Simple structure to store information about a file.
*/
struct file_info {
- struct file_info *next;
+ struct rbtree_node node;
struct stat st;
char *fn;
};
@@ -69,11 +70,16 @@ file_info_new(const char *filename)
fi = m_malloc(sizeof(*fi));
fi->fn = m_strdup(filename);
- fi->next = NULL;
+ /* fi->node uninitilized */
return fi;
}
+/**
+ * Frees a file_info struct
+ *
+ * does NOT remove it from the rbtree, as this is used during rbtree destruction
+ */
static void
file_info_free(struct file_info *fi)
{
@@ -82,13 +88,14 @@ file_info_free(struct file_info *fi)
}
static struct file_info *
-file_info_find_name(struct file_info *list, const char *filename)
+file_info_find_name(struct rbtree *tree, const char *filename)
{
- struct file_info *node;
+ struct file_info fi;
+ struct rbtree_node *r;
- for (node = list; node; node = node->next)
- if (strcmp(node->fn, filename) == 0)
- return node;
+ fi.fn = (char *)filename;
+ if (r = rbtree_lookup(&fi.node, tree))
+ return rbtree_container_of(r, struct file_info, node);
return NULL;
}
@@ -132,39 +139,29 @@ file_info_get(const char *root, int fd)
return fi;
}
-/**
- * Add a new file_info struct to a single linked list of file_info structs.
- *
- * We perform a slight optimization to work around a ‘feature’ in tar: tar
- * always recurses into subdirectories if you list a subdirectory. So if an
- * entry is added and the previous entry in the list is its subdirectory we
- * remove the subdirectory.
- *
- * After a file_info struct is added to a list it may no longer be freed, we
- * assume full responsibility for its memory.
- */
-static void
-file_info_list_append(struct file_info **head, struct file_info **tail,
- struct file_info *fi)
+rbtree_cmp_fn_t file_info_compare(const struct rbtree_node *a, const struct rbtree_node *b);
+rbtree_cmp_fn_t
+file_info_compare(const struct rbtree_node *a, const struct rbtree_node *b)
{
- if (*head == NULL)
- *head = *tail = fi;
- else
- *tail = (*tail)->next =fi;
+ struct file_info *p = rbtree_container_of(a, struct file_info, node);
+ struct file_info *q = rbtree_container_of(b, struct file_info, node);
+
+ return strcmp(p->fn, q->fn);
}
+
/**
- * Free the memory for all entries in a list of file_info structs.
+ * Free the memory for all entries in a rbtree of file_info structs when passed
+ * the root node: (struct rbtree).root
*/
static void
-file_info_list_free(struct file_info *fi)
+file_info_tree_free(struct rbtree_node *node)
{
- while (fi) {
- struct file_info *fl;
-
- fl=fi; fi=fi->next;
- file_info_free(fl);
- }
+ if (node->left)
+ file_info_tree_free(node->left);
+ if (node->right)
+ file_info_tree_free(node->right);
+ file_info_free(rbtree_container_of(node, struct file_info, node));
}
static const char *const maintainerscripts[] = {
@@ -225,8 +222,8 @@ check_conffiles(const char *dir)
FILE *cf;
struct varbuf controlfile = VARBUF_INIT;
char conffilename[MAXCONFFILENAME + 1];
- struct file_info *conffiles_head = NULL;
- struct file_info *conffiles_tail = NULL;
+ struct file_info *conffile = NULL;
+ struct rbtree conffiles;
varbuf_printf(&controlfile, "%s/%s/%s", dir, BUILDCONTROLDIR, CONFFILESFILE);
@@ -256,6 +253,7 @@ check_conffiles(const char *dir)
continue;
}
+ rbtree_init(&conffiles, file_info_compare, 0);
conffilename[n - 1] = '\0';
varbuf_reset(&controlfile);
varbuf_printf(&controlfile, "%s/%s", dir, conffilename);
@@ -271,17 +269,15 @@ check_conffiles(const char *dir)
warning(_("conffile '%s' is not a plain file"), conffilename);
}
- if (file_info_find_name(conffiles_head, conffilename)) {
- warning(_("conffile name '%s' is duplicated"), conffilename);
- } else {
- struct file_info *conffile;
-
+ if (file_info_find_name(&conffiles, conffilename))
+ warning(_("conffile name '%s' is duplicated"), conffilename
+ else {
conffile = file_info_new(conffilename);
- file_info_list_append(&conffiles_head, &conffiles_tail, conffile);
+ rbtree_insert(&conffile->node, &conffiles);
}
}
-
- file_info_list_free(conffiles_head);
+ if (conffiles.root)
+ file_info_tree_free(conffiles.root);
varbuf_destroy(&controlfile);
if (ferror(cf))
@@ -396,8 +392,8 @@ do_build(const char *const *argv)
int p1[2], p2[2], p3[2], gzfd;
pid_t c1,c2,c3;
struct file_info *fi;
- struct file_info *symlist = NULL;
- struct file_info *symlist_end = NULL;
+ struct rbtree list;
+ struct rbtree symlist;
/* Decode our arguments. */
dir = *argv++;
@@ -575,24 +571,30 @@ do_build(const char *const *argv)
close(p3[1]);
/* We need to reorder the files so we can make sure that symlinks
* will not appear before their target. */
+ rbtree_init( &list, file_info_compare, 0);
+ rbtree_init(&symlist, file_info_compare, 0);
while ((fi = file_info_get(dir, p3[0])) != NULL)
if (S_ISLNK(fi->st.st_mode))
- file_info_list_append(&symlist, &symlist_end, fi);
- else {
- if (fd_write(p1[1], fi->fn, strlen(fi->fn) + 1) < 0)
- ohshite(_("failed to write filename to tar pipe (%s)"),
- _("data member"));
- file_info_free(fi);
- }
+ rbtree_insert(&fi->node, &symlist);
+ else
+ rbtree_insert(&fi->node, &list);
close(p3[0]);
subproc_wait_check(c3, "find", 0);
- for (fi= symlist;fi;fi= fi->next)
+ for (fi= rbtree_container_of(rbtree_first( &list), struct file_info, node);fi;
+ fi= rbtree_container_of(rbtree_next(&fi->node), struct file_info, node))
+ if (fd_write(p1[1], fi->fn, strlen(fi->fn) + 1) < 0)
+ ohshite(_("failed to write filename to tar pipe (%s)"), _("data member"));
+ for (fi= rbtree_container_of(rbtree_first(&symlist), struct file_info, node);fi;
+ fi= rbtree_container_of(rbtree_next(&fi->node), struct file_info, node))
if (fd_write(p1[1], fi->fn, strlen(fi->fn) + 1) < 0)
ohshite(_("failed to write filename to tar pipe (%s)"), _("data member"));
/* All done, clean up wait for tar and gzip to finish their job. */
close(p1[1]);
- file_info_list_free(symlist);
+ if (list.root)
+ file_info_tree_free( list.root);
+ if (symlist.root)
+ file_info_tree_free(symlist.root);
subproc_wait_check(c2, _("<compress> from tar -cf"), 0);
subproc_wait_check(c1, "tar -cf", 0);
/* Okay, we have data.tar as well now, add it to the ar wrapper. */
diff --git a/dpkg-deb/libtree.h b/dpkg-deb/libtree.h
new file mode 100644
index 0000000..cd47913
--- /dev/null
+++ b/dpkg-deb/libtree.h
@@ -0,0 +1,218 @@
+/*
+ * libtree.h - this file is part of Libtree.
+ *
+ * Copyright (C) 2010 Franck Bui-Huu <fbuihuu@gmail.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * as published by the Free Software Foundation; version 2 of the
+ * License.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
+ * USA
+ */
+#ifndef _LIBTREE_H
+#define _LIBTREE_H
+
+#include <stdint.h>
+#include <stddef.h>
+
+/*
+ * The definition has been stolen from the Linux kernel.
+ */
+#ifdef __GNUC__
+# define bstree_container_of(node, type, member) ({ \
+ const struct bstree_node *__mptr = (node); \
+ (type *)( (char *)__mptr - offsetof(type,member) );})
+# define rbtree_container_of(node, type, member) ({ \
+ const struct rbtree_node *__mptr = (node); \
+ (type *)( (char *)__mptr - offsetof(type,member) );})
+# define avltree_container_of(node, type, member) ({ \
+ const struct avltree_node *__mptr = (node); \
+ (type *)( (char *)__mptr - offsetof(type,member) );})
+# define splaytree_container_of(node, type, member) ({ \
+ const struct splaytree_node *__mptr = (node); \
+ (type *)( (char *)__mptr - offsetof(type,member) );})
+#else
+# define bstree_container_of(node, type, member) \
+ ((type *)((char *)(node) - offsetof(type, member)))
+# define rbtree_container_of(node, type, member) \
+ ((type *)((char *)(node) - offsetof(type, member)))
+# define avltree_container_of(node, type, member) \
+ ((type *)((char *)(node) - offsetof(type, member)))
+# define splaytree_container_of(node, type, member) \
+ ((type *)((char *)(node) - offsetof(type, member)))
+#endif /* __GNUC__ */
+
+/*
+ * Threaded binary search tree
+ */
+#ifdef UINTPTR_MAX
+
+struct bstree_node {
+ uintptr_t left, right;
+} __attribute__((aligned(2)));
+
+#else
+
+struct bstree_node {
+ struct bstree_node *left, *right;
+ unsigned left_is_thread:1;
+ unsigned right_is_thread:1;
+};
+
+#endif /* UINTPTR_MAX */
+
+typedef int (*bstree_cmp_fn_t)(const struct bstree_node *, const struct bstree_node *);
+
+struct bstree {
+ struct bstree_node *root;
+ bstree_cmp_fn_t cmp_fn;
+ struct bstree_node *first, *last;
+ uint64_t reserved[4];
+};
+
+struct bstree_node *bstree_first(const struct bstree *tree);
+struct bstree_node *bstree_last(const struct bstree *tree);
+struct bstree_node *bstree_next(const struct bstree_node *node);
+struct bstree_node *bstree_prev(const struct bstree_node *node);
+
+struct bstree_node *bstree_lookup(const struct bstree_node *key, const struct bstree *tree);
+struct bstree_node *bstree_insert(struct bstree_node *node, struct bstree *tree);
+void bstree_remove(struct bstree_node *node, struct bstree *tree);
+void bstree_replace(struct bstree_node *old, struct bstree_node *node, struct bstree *tree);
+int bstree_init(struct bstree *tree, bstree_cmp_fn_t cmp, unsigned long flags);
+
+/*
+ * Red-black tree
+ */
+enum rb_color {
+ RB_BLACK,
+ RB_RED,
+};
+
+#ifdef UINTPTR_MAX
+
+struct rbtree_node {
+ struct rbtree_node *left, *right;
+ uintptr_t parent;
+} __attribute__((aligned(2)));
+
+#else
+
+struct rbtree_node {
+ struct rbtree_node *left, *right;
+ struct rbtree_node *parent;
+ enum rb_color color;
+};
+
+#endif /* UINTPTR_MAX */
+
+typedef int (*rbtree_cmp_fn_t)(const struct rbtree_node *, const struct rbtree_node *);
+
+struct rbtree {
+ struct rbtree_node *root;
+ rbtree_cmp_fn_t cmp_fn;
+ struct rbtree_node *first, *last;
+ uint64_t reserved[4];
+};
+
+struct rbtree_node *rbtree_first(const struct rbtree *tree);
+struct rbtree_node *rbtree_last(const struct rbtree *tree);
+struct rbtree_node *rbtree_next(const struct rbtree_node *node);
+struct rbtree_node *rbtree_prev(const struct rbtree_node *node);
+
+struct rbtree_node *rbtree_lookup(const struct rbtree_node *key, const struct rbtree *tree);
+struct rbtree_node *rbtree_insert(struct rbtree_node *node, struct rbtree *tree);
+void rbtree_remove(struct rbtree_node *node, struct rbtree *tree);
+void rbtree_replace(struct rbtree_node *old, struct rbtree_node *node, struct rbtree *tree);
+int rbtree_init(struct rbtree *tree, rbtree_cmp_fn_t cmp, unsigned long flags);
+
+/*
+ * AVL tree
+ */
+#if defined UINTPTR_MAX && UINTPTR_MAX == UINT64_MAX
+
+struct avltree_node {
+ struct avltree_node *left, *right;
+ uintptr_t parent; /* balance factor [0:4] */
+} __attribute__((aligned(8)));
+
+#else
+
+struct avltree_node {
+ struct avltree_node *left, *right;
+ struct avltree_node *parent;
+ signed balance:3; /* balance factor [-2:+2] */
+};
+
+#endif
+
+typedef int (*avltree_cmp_fn_t)(const struct avltree_node *, const struct avltree_node *);
+
+struct avltree {
+ struct avltree_node *root;
+ avltree_cmp_fn_t cmp_fn;
+ int height;
+ struct avltree_node *first, *last;
+ uint64_t reserved[4];
+};
+
+struct avltree_node *avltree_first(const struct avltree *tree);
+struct avltree_node *avltree_last(const struct avltree *tree);
+struct avltree_node *avltree_next(const struct avltree_node *node);
+struct avltree_node *avltree_prev(const struct avltree_node *node);
+
+struct avltree_node *avltree_lookup(const struct avltree_node *key, const struct avltree *tree);
+struct avltree_node *avltree_insert(struct avltree_node *node, struct avltree *tree);
+void avltree_remove(struct avltree_node *node, struct avltree *tree);
+void avltree_replace(struct avltree_node *old, struct avltree_node *node, struct avltree *tree);
+int avltree_init(struct avltree *tree, avltree_cmp_fn_t cmp, unsigned long flags);
+
+/*
+ * Splay tree
+ */
+#ifdef UINTPTR_MAX
+
+struct splaytree_node {
+ uintptr_t left, right;
+} __attribute__((aligned(2)));
+
+#else
+
+struct splaytree_node {
+ struct splaytree_node *left, *right;
+ unsigned left_is_thread:1;
+ unsigned right_is_thread:1;
+};
+
+#endif
+
+typedef int (*splaytree_cmp_fn_t)(const struct splaytree_node *, const struct splaytree_node *);
+
+struct splaytree {
+ struct splaytree_node *root;
+ struct splaytree_node *first, *last;
+ splaytree_cmp_fn_t cmp_fn;
+ uint64_t reserved[4];
+};
+
+struct splaytree_node *splaytree_first(const struct splaytree *tree);
+struct splaytree_node *splaytree_last(const struct splaytree *tree);
+struct splaytree_node *splaytree_next(const struct splaytree_node *node);
+struct splaytree_node *splaytree_prev(const struct splaytree_node *node);
+
+struct splaytree_node *splaytree_lookup(const struct splaytree_node *key, struct splaytree *tree);
+struct splaytree_node *splaytree_insert( struct splaytree_node *node, struct splaytree *tree);
+void splaytree_remove(struct splaytree_node *node, struct splaytree *tree);
+void splaytree_replace(struct splaytree_node *old, struct splaytree_node *node, struct splaytree *tree);
+int splaytree_init(struct splaytree *tree, splaytree_cmp_fn_t cmp, unsigned long flags);
+
+#endif /* _LIBTREE_H */
diff --git a/dpkg-deb/rb.c b/dpkg-deb/rb.c
new file mode 100644
index 0000000..f2fc365
--- /dev/null
+++ b/dpkg-deb/rb.c
@@ -0,0 +1,485 @@
+/*
+ * rbtree - Implements a red-black tree with parent pointers.
+ *
+ * Copyright (C) 2010 Franck Bui-Huu <fbuihuu@gmail.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * as published by the Free Software Foundation; version 2 of the
+ * License.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
+ * USA
+ */
+
+/*
+ * For recall a red-black tree has the following properties:
+ *
+ * 1. All nodes are either BLACK or RED
+ * 2. Leafs are BLACK
+ * 3. A RED node has BLACK children only
+ * 4. Path from a node to any leafs has the same number of BLACK nodes.
+ *
+ */
+#include "libtree.h"
+
+/*
+ * Some helpers
+ */
+#ifdef UINTPTR_MAX
+
+static inline enum rb_color get_color(const struct rbtree_node *node)
+{
+ return node->parent & 1;
+}
+
+static inline void set_color(enum rb_color color, struct rbtree_node *node)
+{
+ node->parent = (node->parent & ~1UL) | color;
+}
+
+static inline struct rbtree_node *get_parent(const struct rbtree_node *node)
+{
+ return (struct rbtree_node *)(node->parent & ~1UL);
+}
+
+static inline void set_parent(struct rbtree_node *parent, struct rbtree_node *node)
+{
+ node->parent = (uintptr_t)parent | (node->parent & 1);
+}
+
+#else
+
+static inline enum rb_color get_color(const struct rbtree_node *node)
+{
+ return node->color;
+}
+
+static inline void set_color(enum rb_color color, struct rbtree_node *node)
+{
+ node->color = color;
+}
+
+static inline struct rbtree_node *get_parent(const struct rbtree_node *node)
+{
+ return node->parent;
+}
+
+static inline void set_parent(struct rbtree_node *parent, struct rbtree_node *node)
+{
+ node->parent = parent;
+}
+
+#endif /* UINTPTR_MAX */
+
+static inline int is_root(struct rbtree_node *node)
+{
+ return get_parent(node) == NULL;
+}
+
+static inline int is_black(struct rbtree_node *node)
+{
+ return get_color(node) == RB_BLACK;
+}
+
+static inline int is_red(struct rbtree_node *node)
+{
+ return !is_black(node);
+}
+
+/*
+ * Iterators
+ */
+static inline struct rbtree_node *get_first(struct rbtree_node *node)
+{
+ while (node->left)
+ node = node->left;
+ return node;
+}
+
+static inline struct rbtree_node *get_last(struct rbtree_node *node)
+{
+ while (node->right)
+ node = node->right;
+ return node;
+}
+
+struct rbtree_node *rbtree_first(const struct rbtree *tree)
+{
+ return tree->first;
+}
+
+struct rbtree_node *rbtree_last(const struct rbtree *tree)
+{
+ return tree->last;
+}
+
+struct rbtree_node *rbtree_next(const struct rbtree_node *node)
+{
+ struct rbtree_node *parent;
+
+ if (node->right)
+ return get_first(node->right);
+
+ while ((parent = get_parent(node)) && parent->right == node)
+ node = parent;
+ return parent;
+}
+
+struct rbtree_node *rbtree_prev(const struct rbtree_node *node)
+{
+ struct rbtree_node *parent;
+
+ if (node->left)
+ return get_last(node->left);
+
+ while ((parent = get_parent(node)) && parent->left == node)
+ node = parent;
+ return parent;
+}
+
+/*
+ * 'pparent' and 'is_left' are only used for insertions. Normally GCC
+ * will notice this and get rid of them for lookups.
+ */
+static inline struct rbtree_node *do_lookup(const struct rbtree_node *key,
+ const struct rbtree *tree,
+ struct rbtree_node **pparent,
+ int *is_left)
+{
+ struct rbtree_node *node = tree->root;
+
+ *pparent = NULL;
+ *is_left = 0;
+
+ while (node) {
+ int res = tree->cmp_fn(node, key);
+ if (res == 0)
+ return node;
+ *pparent = node;
+ if ((*is_left = res > 0))
+ node = node->left;
+ else
+ node = node->right;
+ }
+ return NULL;
+}
+
+/*
+ * Rotate operations (They preserve the binary search tree property,
+ * assuming that the keys are unique).
+ */
+static void rotate_left(struct rbtree_node *node, struct rbtree *tree)
+{
+ struct rbtree_node *p = node;
+ struct rbtree_node *q = node->right; /* can't be NULL */
+ struct rbtree_node *parent = get_parent(p);
+
+ if (!is_root(p)) {
+ if (parent->left == p)
+ parent->left = q;
+ else
+ parent->right = q;
+ } else
+ tree->root = q;
+ set_parent(parent, q);
+ set_parent(q, p);
+
+ p->right = q->left;
+ if (p->right)
+ set_parent(p, p->right);
+ q->left = p;
+}
+
+static void rotate_right(struct rbtree_node *node, struct rbtree *tree)
+{
+ struct rbtree_node *p = node;
+ struct rbtree_node *q = node->left; /* can't be NULL */
+ struct rbtree_node *parent = get_parent(p);
+
+ if (!is_root(p)) {
+ if (parent->left == p)
+ parent->left = q;
+ else
+ parent->right = q;
+ } else
+ tree->root = q;
+ set_parent(parent, q);
+ set_parent(q, p);
+
+ p->left = q->right;
+ if (p->left)
+ set_parent(p, p->left);
+ q->right = p;
+}
+
+struct rbtree_node *rbtree_lookup(const struct rbtree_node *key,
+ const struct rbtree *tree)
+{
+ struct rbtree_node *parent;
+ int is_left;
+
+ return do_lookup(key, tree, &parent, &is_left);
+}
+
+static void set_child(struct rbtree_node *child, struct rbtree_node *node, int left)
+{
+ if (left)
+ node->left = child;
+ else
+ node->right = child;
+}
+
+struct rbtree_node *rbtree_insert(struct rbtree_node *node, struct rbtree *tree)
+{
+ struct rbtree_node *key, *parent;
+ int is_left;
+
+ key = do_lookup(node, tree, &parent, &is_left);
+ if (key)
+ return key;
+
+ node->left = NULL;
+ node->right = NULL;
+ set_color(RB_RED, node);
+ set_parent(parent, node);
+
+ if (parent) {
+ if (is_left) {
+ if (parent == tree->first)
+ tree->first = node;
+ } else {
+ if (parent == tree->last)
+ tree->last = node;
+ }
+ set_child(node, parent, is_left);
+ } else {
+ tree->root = node;
+ tree->first = node;
+ tree->last = node;
+ }
+
+ /*
+ * Fixup the modified tree by recoloring nodes and performing
+ * rotations (2 at most) hence the red-black tree properties are
+ * preserved.
+ */
+ while ((parent = get_parent(node)) && is_red(parent)) {
+ struct rbtree_node *grandpa = get_parent(parent);
+
+ if (parent == grandpa->left) {
+ struct rbtree_node *uncle = grandpa->right;
+
+ if (uncle && is_red(uncle)) {
+ set_color(RB_BLACK, parent);
+ set_color(RB_BLACK, uncle);
+ set_color(RB_RED, grandpa);
+ node = grandpa;
+ } else {
+ if (node == parent->right) {
+ rotate_left(parent, tree);
+ node = parent;
+ parent = get_parent(node);
+ }
+ set_color(RB_BLACK, parent);
+ set_color(RB_RED, grandpa);
+ rotate_right(grandpa, tree);
+ }
+ } else {
+ struct rbtree_node *uncle = grandpa->left;
+
+ if (uncle && is_red(uncle)) {
+ set_color(RB_BLACK, parent);
+ set_color(RB_BLACK, uncle);
+ set_color(RB_RED, grandpa);
+ node = grandpa;
+ } else {
+ if (node == parent->left) {
+ rotate_right(parent, tree);
+ node = parent;
+ parent = get_parent(node);
+ }
+ set_color(RB_BLACK, parent);
+ set_color(RB_RED, grandpa);
+ rotate_left(grandpa, tree);
+ }
+ }
+ }
+ set_color(RB_BLACK, tree->root);
+ return NULL;
+}
+
+void rbtree_remove(struct rbtree_node *node, struct rbtree *tree)
+{
+ struct rbtree_node *parent = get_parent(node);
+ struct rbtree_node *left = node->left;
+ struct rbtree_node *right = node->right;
+ struct rbtree_node *next;
+ enum rb_color color;
+
+ if (node == tree->first)
+ tree->first = rbtree_next(node);
+ if (node == tree->last)
+ tree->last = rbtree_prev(node);
+
+ if (!left)
+ next = right;
+ else if (!right)
+ next = left;
+ else
+ next = get_first(right);
+
+ if (parent)
+ set_child(next, parent, parent->left == node);
+ else
+ tree->root = next;
+
+ if (left && right) {
+ color = get_color(next);
+ set_color(get_color(node), next);
+
+ next->left = left;
+ set_parent(next, left);
+
+ if (next != right) {
+ parent = get_parent(next);
+ set_parent(get_parent(node), next);
+
+ node = next->right;
+ parent->left = node;
+
+ next->right = right;
+ set_parent(next, right);
+ } else {
+ set_parent(parent, next);
+ parent = next;
+ node = next->right;
+ }
+ } else {
+ color = get_color(node);
+ node = next;
+ }
+ /*
+ * 'node' is now the sole successor's child and 'parent' its
+ * new parent (since the successor can have been moved).
+ */
+ if (node)
+ set_parent(parent, node);
+
+ /*
+ * The 'easy' cases.
+ */
+ if (color == RB_RED)
+ return;
+ if (node && is_red(node)) {
+ set_color(RB_BLACK, node);
+ return;
+ }
+
+ do {
+ if (node == tree->root)
+ break;
+
+ if (node == parent->left) {
+ struct rbtree_node *sibling = parent->right;
+
+ if (is_red(sibling)) {
+ set_color(RB_BLACK, sibling);
+ set_color(RB_RED, parent);
+ rotate_left(parent, tree);
+ sibling = parent->right;
+ }
+ if ((!sibling->left || is_black(sibling->left)) &&
+ (!sibling->right || is_black(sibling->right))) {
+ set_color(RB_RED, sibling);
+ node = parent;
+ parent = get_parent(parent);
+ continue;
+ }
+ if (!sibling->right || is_black(sibling->right)) {
+ set_color(RB_BLACK, sibling->left);
+ set_color(RB_RED, sibling);
+ rotate_right(sibling, tree);
+ sibling = parent->right;
+ }
+ set_color(get_color(parent), sibling);
+ set_color(RB_BLACK, parent);
+ set_color(RB_BLACK, sibling->right);
+ rotate_left(parent, tree);
+ node = tree->root;
+ break;
+ } else {
+ struct rbtree_node *sibling = parent->left;
+
+ if (is_red(sibling)) {
+ set_color(RB_BLACK, sibling);
+ set_color(RB_RED, parent);
+ rotate_right(parent, tree);
+ sibling = parent->left;
+ }
+ if ((!sibling->left || is_black(sibling->left)) &&
+ (!sibling->right || is_black(sibling->right))) {
+ set_color(RB_RED, sibling);
+ node = parent;
+ parent = get_parent(parent);
+ continue;
+ }
+ if (!sibling->left || is_black(sibling->left)) {
+ set_color(RB_BLACK, sibling->right);
+ set_color(RB_RED, sibling);
+ rotate_left(sibling, tree);
+ sibling = parent->left;
+ }
+ set_color(get_color(parent), sibling);
+ set_color(RB_BLACK, parent);
+ set_color(RB_BLACK, sibling->left);
+ rotate_right(parent, tree);
+ node = tree->root;
+ break;
+ }
+ } while (is_black(node));
+
+ if (node)
+ set_color(RB_BLACK, node);
+}
+
+void rbtree_replace(struct rbtree_node *old, struct rbtree_node *new,
+ struct rbtree *tree)
+{
+ struct rbtree_node *parent = get_parent(old);
+
+ if (parent)
+ set_child(new, parent, parent->left == old);
+ else
+ tree->root = new;
+
+ if (old->left)
+ set_parent(new, old->left);
+ if (old->right)
+ set_parent(new, old->right);
+
+ if (tree->first == old)
+ tree->first = new;
+ if (tree->last == old)
+ tree->last = new;
+
+ *new = *old;
+}
+
+int rbtree_init(struct rbtree *tree, rbtree_cmp_fn_t fn, unsigned long flags)
+{
+ if (flags)
+ return -1;
+ tree->root = NULL;
+ tree->cmp_fn = fn;
+ tree->first = NULL;
+ tree->last = NULL;
+ return 0;
+}
--
1.8.4.rc3
Reply to: