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 <fbui...@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 <fbui...@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 -- To UNSUBSCRIBE, email to debian-bugs-dist-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org
