diff options
Diffstat (limited to 'mcastseed')
| -rw-r--r-- | mcastseed/lib/Makefile.am | 14 | ||||
| -rw-r--r-- | mcastseed/lib/gl_anyrbtree_list1.h | 76 | ||||
| -rw-r--r-- | mcastseed/lib/gl_anyrbtree_list2.h (renamed from mcastseed/lib/gl_rbtree_oset.c) | 672 | ||||
| -rw-r--r-- | mcastseed/lib/gl_anytree_list1.h | 41 | ||||
| -rw-r--r-- | mcastseed/lib/gl_anytree_list2.h | 940 | ||||
| -rw-r--r-- | mcastseed/lib/gl_anytree_oset.h | 297 | ||||
| -rw-r--r-- | mcastseed/lib/gl_list.c | 3 | ||||
| -rw-r--r-- | mcastseed/lib/gl_list.h | 841 | ||||
| -rw-r--r-- | mcastseed/lib/gl_oset.c | 3 | ||||
| -rw-r--r-- | mcastseed/lib/gl_oset.h | 293 | ||||
| -rw-r--r-- | mcastseed/lib/gl_rbtree_list.c | 102 | ||||
| -rw-r--r-- | mcastseed/lib/gl_rbtree_list.h (renamed from mcastseed/lib/gl_rbtree_oset.h) | 14 | ||||
| -rw-r--r-- | mcastseed/m4/gnulib-cache.m4 | 4 | ||||
| -rw-r--r-- | mcastseed/m4/gnulib-comp.m4 | 18 | ||||
| -rw-r--r-- | mcastseed/m4/onceonly.m4 | 104 |
15 files changed, 2472 insertions, 950 deletions
diff --git a/mcastseed/lib/Makefile.am b/mcastseed/lib/Makefile.am index 17e7205..38faabe 100644 --- a/mcastseed/lib/Makefile.am +++ b/mcastseed/lib/Makefile.am @@ -21,7 +21,7 @@ # the same distribution terms as the rest of that program. # # Generated by gnulib-tool. -# Reproduce by: gnulib-tool --import --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --tests-base=tests --aux-dir=. --no-conditional-dependencies --no-libtool --macro-prefix=gl rbtree-oset +# Reproduce by: gnulib-tool --import --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --tests-base=tests --aux-dir=. --no-conditional-dependencies --no-libtool --macro-prefix=gl rbtree-list AUTOMAKE_OPTIONS = 1.9.6 gnits @@ -48,17 +48,17 @@ libgnu_a_LIBADD = $(gl_LIBOBJS) libgnu_a_DEPENDENCIES = $(gl_LIBOBJS) EXTRA_libgnu_a_SOURCES = -## begin gnulib module oset +## begin gnulib module list -libgnu_a_SOURCES += gl_oset.h gl_oset.c +libgnu_a_SOURCES += gl_list.h gl_list.c -## end gnulib module oset +## end gnulib module list -## begin gnulib module rbtree-oset +## begin gnulib module rbtree-list -libgnu_a_SOURCES += gl_rbtree_oset.h gl_rbtree_oset.c gl_anytree_oset.h +libgnu_a_SOURCES += gl_rbtree_list.h gl_rbtree_list.c gl_anyrbtree_list1.h gl_anyrbtree_list2.h gl_anytree_list1.h gl_anytree_list2.h -## end gnulib module rbtree-oset +## end gnulib module rbtree-list ## begin gnulib module stdbool diff --git a/mcastseed/lib/gl_anyrbtree_list1.h b/mcastseed/lib/gl_anyrbtree_list1.h new file mode 100644 index 0000000..0ae0715 --- /dev/null +++ b/mcastseed/lib/gl_anyrbtree_list1.h @@ -0,0 +1,76 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006, 2009-2016 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + 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 General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +/* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */ + +/* A red-black tree is a binary tree where every node is colored black or + red such that + 1. The root is black. + 2. No red node has a red parent. + Or equivalently: No red node has a red child. + 3. All paths from the root down to any NULL endpoint contain the same + number of black nodes. + Let's call this the "black-height" bh of the tree. It follows that every + such path contains exactly bh black and between 0 and bh red nodes. (The + extreme cases are a path containing only black nodes, and a path colored + alternately black-red-black-red-...-black-red.) The height of the tree + therefore is >= bh, <= 2*bh. + */ + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +/* Color of a node. */ +typedef enum color { BLACK, RED } color_t; + +/* Concrete list node implementation, valid for this file only. */ +struct gl_list_node_impl +{ +#if WITH_HASHTABLE + struct gl_hash_entry h; /* hash table entry fields; must be first */ +#endif + struct gl_list_node_impl *left; /* left branch, or NULL */ + struct gl_list_node_impl *right; /* right branch, or NULL */ + /* Parent pointer, or NULL. The parent pointer is not needed for most + operations. It is needed so that a gl_list_node_t can be returned + without memory allocation, on which the functions gl_list_remove_node, + gl_list_add_before, gl_list_add_after can be implemented. */ + struct gl_list_node_impl *parent; + color_t color; /* node's color */ + size_t branch_size; /* number of nodes in this branch, + = branchsize(left)+branchsize(right)+1 */ + const void *value; +}; + +/* Concrete gl_list_impl type, valid for this file only. */ +struct gl_list_impl +{ + struct gl_list_impl_base base; +#if WITH_HASHTABLE + /* A hash table: managed as an array of collision lists. */ + struct gl_hash_entry **table; + size_t table_size; +#endif + struct gl_list_node_impl *root; /* root node or NULL */ +}; + +/* A red-black tree of height h has a black-height bh >= ceil(h/2) and + therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree + of height h >= 117 would have at least 2^59 - 1 elements, and because even + on 64-bit machines, + sizeof (gl_list_node_impl) * (2^59 - 1) > 2^64 + this would exceed the address space of the machine. */ +#define MAXHEIGHT 116 diff --git a/mcastseed/lib/gl_rbtree_oset.c b/mcastseed/lib/gl_anyrbtree_list2.h index 615b9ae..a0e2e43 100644 --- a/mcastseed/lib/gl_rbtree_oset.c +++ b/mcastseed/lib/gl_anyrbtree_list2.h @@ -1,4 +1,4 @@ -/* Ordered set data type implemented by a binary tree. +/* Sequential list data type implemented by a binary tree. Copyright (C) 2006-2007, 2009-2016 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. @@ -15,62 +15,143 @@ You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#include <config.h> +/* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */ -/* Specification. */ -#include "gl_rbtree_oset.h" +/* -------------------------- gl_list_t Data Type -------------------------- */ -#include <stdlib.h> +/* Create a subtree for count >= 1 elements. + Its black-height bh is passed as argument, with + 2^bh - 1 <= count <= 2^(bh+1) - 1. bh == 0 implies count == 1. + Its height is h where 2^(h-1) <= count <= 2^h - 1. + Return NULL upon out-of-memory. */ +static gl_list_node_t +create_subtree_with_contents (unsigned int bh, + size_t count, const void **contents) +{ + size_t half1 = (count - 1) / 2; + size_t half2 = count / 2; + /* Note: half1 + half2 = count - 1. */ + gl_list_node_t node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + if (node == NULL) + return NULL; + + if (half1 > 0) + { + /* half1 > 0 implies count > 1, implies bh >= 1, implies + 2^(bh-1) - 1 <= half1 <= 2^bh - 1. */ + node->left = + create_subtree_with_contents (bh - 1, half1, contents); + if (node->left == NULL) + goto fail1; + node->left->parent = node; + } + else + node->left = NULL; + + node->value = contents[half1]; + + if (half2 > 0) + { + /* half2 > 0 implies count > 1, implies bh >= 1, implies + 2^(bh-1) - 1 <= half2 <= 2^bh - 1. */ + node->right = + create_subtree_with_contents (bh - 1, half2, contents + half1 + 1); + if (node->right == NULL) + goto fail2; + node->right->parent = node; + } + else + node->right = NULL; -/* A red-black tree is a binary tree where every node is colored black or - red such that - 1. The root is black. - 2. No red node has a red parent. - Or equivalently: No red node has a red child. - 3. All paths from the root down to any NULL endpoint contain the same - number of black nodes. - Let's call this the "black-height" bh of the tree. It follows that every - such path contains exactly bh black and between 0 and bh red nodes. (The - extreme cases are a path containing only black nodes, and a path colored - alternately black-red-black-red-...-black-red.) The height of the tree - therefore is >= bh, <= 2*bh. - */ + node->color = (bh == 0 ? RED : BLACK); -/* -------------------------- gl_oset_t Data Type -------------------------- */ + node->branch_size = count; -/* Color of a node. */ -typedef enum color { BLACK, RED } color_t; + return node; -/* Tree node implementation, valid for this file only. */ -struct gl_oset_node_impl -{ - struct gl_oset_node_impl *left; /* left branch, or NULL */ - struct gl_oset_node_impl *right; /* right branch, or NULL */ - /* Parent pointer, or NULL. The parent pointer is not needed for most - operations. It is needed so that a gl_oset_node_t can be returned - without memory allocation, on which the functions gl_oset_remove_node, - gl_oset_add_before, gl_oset_add_after can be implemented. */ - struct gl_oset_node_impl *parent; - color_t color; /* node's color */ - const void *value; -}; -typedef struct gl_oset_node_impl * gl_oset_node_t; - -/* Concrete gl_oset_impl type, valid for this file only. */ -struct gl_oset_impl + fail2: + if (node->left != NULL) + free_subtree (node->left); + fail1: + free (node); + return NULL; +} + +static gl_list_t +gl_tree_nx_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents) { - struct gl_oset_impl_base base; - struct gl_oset_node_impl *root; /* root node or NULL */ - size_t count; /* number of nodes */ -}; - -/* A red-black tree of height h has a black-height bh >= ceil(h/2) and - therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree - of height h >= 117 would have at least 2^59 - 1 elements, and because even - on 64-bit machines, - sizeof (gl_oset_node_impl) * (2^59 - 1) > 2^64 - this would exceed the address space of the machine. */ -#define MAXHEIGHT 116 + struct gl_list_impl *list = + (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); + + if (list == NULL) + return NULL; + + list->base.vtable = implementation; + list->base.equals_fn = equals_fn; + list->base.hashcode_fn = hashcode_fn; + list->base.dispose_fn = dispose_fn; + list->base.allow_duplicates = allow_duplicates; +#if WITH_HASHTABLE + { + size_t estimate = xsum (count, count / 2); /* 1.5 * count */ + if (estimate < 10) + estimate = 10; + list->table_size = next_prime (estimate); + if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t)))) + goto fail1; + list->table = + (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t)); + if (list->table == NULL) + goto fail1; + } +#endif + if (count > 0) + { + /* Assuming 2^bh - 1 <= count <= 2^(bh+1) - 2, we create a tree whose + upper bh levels are black, and only the partially present lowest + level is red. */ + unsigned int bh; + { + size_t n; + for (n = count + 1, bh = 0; n > 1; n = n >> 1) + bh++; + } + + list->root = create_subtree_with_contents (bh, count, contents); + if (list->root == NULL) + goto fail2; + list->root->parent = NULL; + +#if WITH_HASHTABLE + /* Now that the tree is built, node_position() works. Now we can + add the nodes to the hash table. */ + if (add_nodes_to_buckets (list) < 0) + goto fail3; +#endif + } + else + list->root = NULL; + + return list; + +#if WITH_HASHTABLE + fail3: + free_subtree (list->root); +#endif + fail2: +#if WITH_HASHTABLE + free (list->table); + fail1: +#endif + free (list); + return NULL; +} /* Rotate left a subtree. @@ -82,10 +163,12 @@ struct gl_oset_impl Change the tree structure, update the branch sizes. The caller must update the colors and register D as child of its parent. */ -static gl_oset_node_t -rotate_left (gl_oset_node_t b_node, gl_oset_node_t d_node) +static gl_list_node_t +rotate_left (gl_list_node_t b_node, gl_list_node_t d_node) { - gl_oset_node_t c_node = d_node->left; + gl_list_node_t a_node = b_node->left; + gl_list_node_t c_node = d_node->left; + gl_list_node_t e_node = d_node->right; b_node->right = c_node; d_node->left = b_node; @@ -95,6 +178,12 @@ rotate_left (gl_oset_node_t b_node, gl_oset_node_t d_node) if (c_node != NULL) c_node->parent = b_node; + b_node->branch_size = + (a_node != NULL ? a_node->branch_size : 0) + + 1 + (c_node != NULL ? c_node->branch_size : 0); + d_node->branch_size = + b_node->branch_size + 1 + (e_node != NULL ? e_node->branch_size : 0); + return d_node; } @@ -108,10 +197,12 @@ rotate_left (gl_oset_node_t b_node, gl_oset_node_t d_node) Change the tree structure, update the branch sizes. The caller must update the colors and register B as child of its parent. */ -static gl_oset_node_t -rotate_right (gl_oset_node_t b_node, gl_oset_node_t d_node) +static gl_list_node_t +rotate_right (gl_list_node_t b_node, gl_list_node_t d_node) { - gl_oset_node_t c_node = b_node->right; + gl_list_node_t a_node = b_node->left; + gl_list_node_t c_node = b_node->right; + gl_list_node_t e_node = d_node->right; d_node->left = c_node; b_node->right = d_node; @@ -121,6 +212,12 @@ rotate_right (gl_oset_node_t b_node, gl_oset_node_t d_node) if (c_node != NULL) c_node->parent = d_node; + d_node->branch_size = + (c_node != NULL ? c_node->branch_size : 0) + + 1 + (e_node != NULL ? e_node->branch_size : 0); + b_node->branch_size = + (a_node != NULL ? a_node->branch_size : 0) + 1 + d_node->branch_size; + return b_node; } @@ -128,15 +225,15 @@ rotate_right (gl_oset_node_t b_node, gl_oset_node_t d_node) Also assigns node->color. parent is the given node's parent, known to be non-NULL. */ static void -rebalance_after_add (gl_oset_t set, gl_oset_node_t node, gl_oset_node_t parent) +rebalance_after_add (gl_list_t list, gl_list_node_t node, gl_list_node_t parent) { for (;;) { /* At this point, parent = node->parent != NULL. Think of node->color being RED (although node->color is not yet assigned.) */ - gl_oset_node_t grandparent; - gl_oset_node_t uncle; + gl_list_node_t grandparent; + gl_list_node_t uncle; if (parent->color == BLACK) { @@ -171,10 +268,10 @@ rebalance_after_add (gl_oset_t set, gl_oset_node_t node, gl_oset_node_t parent) to be RED too. In this case, recoloring is not sufficient. Need to perform one or two rotations. */ - gl_oset_node_t *grandparentp; + gl_list_node_t *grandparentp; if (grandparent->parent == NULL) - grandparentp = &set->root; + grandparentp = &list->root; else if (grandparent->parent->left == grandparent) grandparentp = &grandparent->parent->left; else if (grandparent->parent->right == grandparent) @@ -253,7 +350,7 @@ rebalance_after_add (gl_oset_t set, gl_oset_node_t node, gl_oset_node_t parent) a black node was removed. CHILD is also black, or NULL. (CHILD can also be NULL. But PARENT is non-NULL.) */ static void -rebalance_after_remove (gl_oset_t set, gl_oset_node_t child, gl_oset_node_t parent) +rebalance_after_remove (gl_list_t list, gl_list_node_t child, gl_list_node_t parent) { for (;;) { @@ -261,10 +358,10 @@ rebalance_after_remove (gl_oset_t set, gl_oset_node_t child, gl_oset_node_t pare To make up, either look for a possibility to turn a RED to a BLACK node, or try to reduce the black-height tree of CHILD's sibling subtree as well. */ - gl_oset_node_t *parentp; + gl_list_node_t *parentp; if (parent->parent == NULL) - parentp = &set->root; + parentp = &list->root; else if (parent->parent->left == parent) parentp = &parent->parent->left; else if (parent->parent->right == parent) @@ -274,7 +371,7 @@ rebalance_after_remove (gl_oset_t set, gl_oset_node_t child, gl_oset_node_t pare if (parent->left == child) { - gl_oset_node_t sibling = parent->right; + gl_list_node_t sibling = parent->right; /* sibling's black-height is >= 1. In particular, sibling != NULL. @@ -396,7 +493,7 @@ rebalance_after_remove (gl_oset_t set, gl_oset_node_t child, gl_oset_node_t pare } else if (parent->right == child) { - gl_oset_node_t sibling = parent->left; + gl_list_node_t sibling = parent->left; /* sibling's black-height is >= 1. In particular, sibling != NULL. @@ -535,118 +632,15 @@ rebalance_after_remove (gl_oset_t set, gl_oset_node_t child, gl_oset_node_t pare } } -static gl_oset_node_t -gl_tree_nx_add_first (gl_oset_t set, const void *elt) -{ - /* Create new node. */ - gl_oset_node_t new_node = - (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl)); - - if (new_node == NULL) - return NULL; - - new_node->left = NULL; - new_node->right = NULL; - new_node->value = elt; - - /* Add it to the tree. */ - if (set->root == NULL) - { - new_node->color = BLACK; - set->root = new_node; - new_node->parent = NULL; - } - else - { - gl_oset_node_t node; - - for (node = set->root; node->left != NULL; ) - node = node->left; - - node->left = new_node; - new_node->parent = node; - - /* Color and rebalance. */ - rebalance_after_add (set, new_node, node); - } - - set->count++; - return new_node; -} - -static gl_oset_node_t -gl_tree_nx_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt) -{ - /* Create new node. */ - gl_oset_node_t new_node = - (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl)); - - if (new_node == NULL) - return NULL; - - new_node->left = NULL; - new_node->right = NULL; - new_node->value = elt; - - /* Add it to the tree. */ - if (node->left == NULL) - node->left = new_node; - else - { - for (node = node->left; node->right != NULL; ) - node = node->right; - node->right = new_node; - } - new_node->parent = node; - - /* Color and rebalance. */ - rebalance_after_add (set, new_node, node); - - set->count++; - return new_node; -} - -static gl_oset_node_t -gl_tree_nx_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt) -{ - /* Create new node. */ - gl_oset_node_t new_node = - (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl)); - - if (new_node == NULL) - return NULL; - - new_node->left = NULL; - new_node->right = NULL; - new_node->value = elt; - - /* Add it to the tree. */ - if (node->right == NULL) - node->right = new_node; - else - { - for (node = node->right; node->left != NULL; ) - node = node->left; - node->left = new_node; - } - new_node->parent = node; - - /* Color and rebalance. */ - rebalance_after_add (set, new_node, node); - - set->count++; - return new_node; -} - -static bool -gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node) +static void +gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node) { - gl_oset_node_t parent = node->parent; + gl_list_node_t parent = node->parent; if (node->left == NULL) { /* Replace node with node->right. */ - gl_oset_node_t child = node->right; + gl_list_node_t child = node->right; if (child != NULL) { @@ -656,7 +650,7 @@ gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node) child->color = BLACK; } if (parent == NULL) - set->root = child; + list->root = child; else { if (parent->left == node) @@ -664,8 +658,16 @@ gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node) else /* parent->right == node */ parent->right = child; + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = parent; p != NULL; p = p->parent) + p->branch_size--; + } + if (child == NULL && node->color == BLACK) - rebalance_after_remove (set, child, parent); + rebalance_after_remove (list, child, parent); } } else if (node->right == NULL) @@ -673,28 +675,36 @@ gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node) /* It is not absolutely necessary to treat this case. But the more general case below is more complicated, hence slower. */ /* Replace node with node->left. */ - gl_oset_node_t child = node->left; + gl_list_node_t child = node->left; child->parent = parent; /* Since node->right == NULL, child must be RED and of height 1, hence node must have been BLACK. Recolor the child. */ child->color = BLACK; if (parent == NULL) - set->root = child; + list->root = child; else { if (parent->left == node) parent->left = child; else /* parent->right == node */ parent->right = child; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = parent; p != NULL; p = p->parent) + p->branch_size--; + } } } else { /* Replace node with the rightmost element of the node->left subtree. */ - gl_oset_node_t subst; - gl_oset_node_t subst_parent; - gl_oset_node_t child; + gl_list_node_t subst; + gl_list_node_t subst_parent; + gl_list_node_t child; color_t removed_color; for (subst = node->left; subst->right != NULL; ) @@ -724,6 +734,14 @@ gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node) subst_parent->right = child; } + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = subst_parent; p != NULL; p = p->parent) + p->branch_size--; + } + /* Copy subst into node's position. (This is safer than to copy subst's value into node, keep node in place, and free subst.) */ @@ -735,9 +753,10 @@ gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node) subst->right = node->right; subst->right->parent = subst; subst->color = node->color; + subst->branch_size = node->branch_size; subst->parent = parent; if (parent == NULL) - set->root = subst; + list->root = subst; else if (parent->left == node) parent->left = subst; else /* parent->right == node */ @@ -752,63 +771,258 @@ gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node) /* Rebalancing starts at child's parent, that is subst_parent - except when subst_parent == node. In this case, we need to use its replacement, subst. */ - rebalance_after_remove (set, child, + rebalance_after_remove (list, child, subst_parent != node ? subst_parent : subst); } } - - set->count--; - if (set->base.dispose_fn != NULL) - set->base.dispose_fn (node->value); - free (node); - return true; } -/* Generic binary tree code. */ -#include "gl_anytree_oset.h" +static gl_list_node_t +gl_tree_nx_add_first (gl_list_t list, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); -/* For debugging. */ -static unsigned int -check_invariants (gl_oset_node_t node, gl_oset_node_t parent, size_t *counterp) + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->branch_size = 1; + new_node->value = elt; +#if WITH_HASHTABLE + new_node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (new_node->value) + : (size_t)(uintptr_t) new_node->value); +#endif + + /* Add it to the tree. */ + if (list->root == NULL) + { + new_node->color = BLACK; + list->root = new_node; + new_node->parent = NULL; + } + else + { + gl_list_node_t node; + + for (node = list->root; node->left != NULL; ) + node = node->left; + + node->left = new_node; + new_node->parent = node; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = node; p != NULL; p = p->parent) + p->branch_size++; + } + + /* Color and rebalance. */ + rebalance_after_add (list, new_node, node); + } + +#if WITH_HASHTABLE + /* Add node to the hash table. + Note that this is only possible _after_ the node has been added to the + tree structure, because add_to_bucket() uses node_position(). */ + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_tree_nx_add_last (gl_list_t list, const void *elt) { - unsigned int left_blackheight = - (node->left != NULL ? check_invariants (node->left, node, counterp) : 0); - unsigned int right_blackheight = - (node->right != NULL ? check_invariants (node->right, node, counterp) : 0); - - if (!(node->parent == parent)) - abort (); - if (!(node->color == BLACK || node->color == RED)) - abort (); - if (parent == NULL && !(node->color == BLACK)) - abort (); - if (!(left_blackheight == right_blackheight)) - abort (); - - (*counterp)++; - - return left_blackheight + (node->color == BLACK ? 1 : 0); + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->branch_size = 1; + new_node->value = elt; +#if WITH_HASHTABLE + new_node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (new_node->value) + : (size_t)(uintptr_t) new_node->value); +#endif + + /* Add it to the tree. */ + if (list->root == NULL) + { + new_node->color = BLACK; + list->root = new_node; + new_node->parent = NULL; + } + else + { + gl_list_node_t node; + + for (node = list->root; node->right != NULL; ) + node = node->right; + + node->right = new_node; + new_node->parent = node; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = node; p != NULL; p = p->parent) + p->branch_size++; + } + + /* Color and rebalance. */ + rebalance_after_add (list, new_node, node); + } + +#if WITH_HASHTABLE + /* Add node to the hash table. + Note that this is only possible _after_ the node has been added to the + tree structure, because add_to_bucket() uses node_position(). */ + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } + hash_resize_after_add (list); +#endif + + return new_node; } -void -gl_rbtree_oset_check_invariants (gl_oset_t set) + +static gl_list_node_t +gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) { - size_t counter = 0; - if (set->root != NULL) - check_invariants (set->root, NULL, &counter); - if (!(set->count == counter)) - abort (); + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->branch_size = 1; + new_node->value = elt; +#if WITH_HASHTABLE + new_node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (new_node->value) + : (size_t)(uintptr_t) new_node->value); +#endif + + /* Add it to the tree. */ + if (node->left == NULL) + node->left = new_node; + else + { + for (node = node->left; node->right != NULL; ) + node = node->right; + node->right = new_node; + } + new_node->parent = node; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = node; p != NULL; p = p->parent) + p->branch_size++; + } + + /* Color and rebalance. */ + rebalance_after_add (list, new_node, node); + +#if WITH_HASHTABLE + /* Add node to the hash table. + Note that this is only possible _after_ the node has been added to the + tree structure, because add_to_bucket() uses node_position(). */ + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } + hash_resize_after_add (list); +#endif + + return new_node; } -const struct gl_oset_implementation gl_rbtree_oset_implementation = +static gl_list_node_t +gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->branch_size = 1; + new_node->value = elt; +#if WITH_HASHTABLE + new_node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (new_node->value) + : (size_t)(uintptr_t) new_node->value); +#endif + + /* Add it to the tree. */ + if (node->right == NULL) + node->right = new_node; + else + { + for (node = node->right; node->left != NULL; ) + node = node->left; + node->left = new_node; + } + new_node->parent = node; + + /* Update branch_size fields of the parent nodes. */ { - gl_tree_nx_create_empty, - gl_tree_size, - gl_tree_search, - gl_tree_search_atleast, - gl_tree_nx_add, - gl_tree_remove, - gl_tree_oset_free, - gl_tree_iterator, - gl_tree_iterator_next, - gl_tree_iterator_free - }; + gl_list_node_t p; + + for (p = node; p != NULL; p = p->parent) + p->branch_size++; + } + + /* Color and rebalance. */ + rebalance_after_add (list, new_node, node); + +#if WITH_HASHTABLE + /* Add node to the hash table. + Note that this is only possible _after_ the node has been added to the + tree structure, because add_to_bucket() uses node_position(). */ + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } + hash_resize_after_add (list); +#endif + + return new_node; +} diff --git a/mcastseed/lib/gl_anytree_list1.h b/mcastseed/lib/gl_anytree_list1.h new file mode 100644 index 0000000..675f107 --- /dev/null +++ b/mcastseed/lib/gl_anytree_list1.h @@ -0,0 +1,41 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006, 2009-2016 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + 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 General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +/* Common code of gl_avltree_list.c, gl_rbtree_list.c, + gl_avltreehash_list.c, gl_rbtreehash_list.c. */ + +/* An item on the stack used for iterating across the elements. */ +typedef struct +{ + gl_list_node_t node; + size_t rightp; +} iterstack_item_t; + +/* A stack used for iterating across the elements. */ +typedef iterstack_item_t iterstack_t[MAXHEIGHT]; + +/* Free a non-empty subtree recursively. + This function is recursive and therefore not very fast. */ +static void +free_subtree (gl_list_node_t node) +{ + if (node->left != NULL) + free_subtree (node->left); + if (node->right != NULL) + free_subtree (node->right); + free (node); +} diff --git a/mcastseed/lib/gl_anytree_list2.h b/mcastseed/lib/gl_anytree_list2.h new file mode 100644 index 0000000..7e6fe45 --- /dev/null +++ b/mcastseed/lib/gl_anytree_list2.h @@ -0,0 +1,940 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006-2016 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + 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 General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +/* Common code of gl_avltree_list.c, gl_rbtree_list.c, + gl_avltreehash_list.c, gl_rbtreehash_list.c. */ + +static gl_list_t +gl_tree_nx_create_empty (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates) +{ + struct gl_list_impl *list = (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); + + if (list == NULL) + return NULL; + + list->base.vtable = implementation; + list->base.equals_fn = equals_fn; + list->base.hashcode_fn = hashcode_fn; + list->base.dispose_fn = dispose_fn; + list->base.allow_duplicates = allow_duplicates; +#if WITH_HASHTABLE + list->table_size = 11; + list->table = + (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t)); + if (list->table == NULL) + goto fail; +#endif + list->root = NULL; + + return list; + +#if WITH_HASHTABLE + fail: + free (list); + return NULL; +#endif +} + +static size_t +gl_tree_size (gl_list_t list) +{ + return (list->root != NULL ? list->root->branch_size : 0); +} + +static const void * +gl_tree_node_value (gl_list_t list, gl_list_node_t node) +{ + return node->value; +} + +static int +gl_tree_node_nx_set_value (gl_list_t list, gl_list_node_t node, const void *elt) +{ +#if WITH_HASHTABLE + if (elt != node->value) + { + size_t new_hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + + if (new_hashcode != node->h.hashcode) + { + remove_from_bucket (list, node); + node->value = elt; + node->h.hashcode = new_hashcode; + if (add_to_bucket (list, node) < 0) + { + /* Out of memory. We removed node from a bucket but cannot add + it to another bucket. In order to avoid inconsistencies, we + must remove node entirely from the list. */ + gl_tree_remove_node_from_tree (list, node); + free (node); + return -1; + } + } + else + node->value = elt; + } +#else + node->value = elt; +#endif + return 0; +} + +static gl_list_node_t _GL_ATTRIBUTE_PURE +gl_tree_next_node (gl_list_t list, gl_list_node_t node) +{ + if (node->right != NULL) + { + node = node->right; + while (node->left != NULL) + node = node->left; + } + else + { + while (node->parent != NULL && node->parent->right == node) + node = node->parent; + node = node->parent; + } + return node; +} + +static gl_list_node_t _GL_ATTRIBUTE_PURE +gl_tree_previous_node (gl_list_t list, gl_list_node_t node) +{ + if (node->left != NULL) + { + node = node->left; + while (node->right != NULL) + node = node->right; + } + else + { + while (node->parent != NULL && node->parent->left == node) + node = node->parent; + node = node->parent; + } + return node; +} + +/* Return the node at the given position < gl_tree_size (list). */ +static gl_list_node_t _GL_ATTRIBUTE_PURE +node_at (gl_list_node_t root, size_t position) +{ + /* Here we know that root != NULL. */ + gl_list_node_t node = root; + + for (;;) + { + if (node->left != NULL) + { + if (position < node->left->branch_size) + { + node = node->left; + continue; + } + position -= node->left->branch_size; + } + if (position == 0) + break; + position--; + node = node->right; + } + return node; +} + +static const void * _GL_ATTRIBUTE_PURE +gl_tree_get_at (gl_list_t list, size_t position) +{ + gl_list_node_t node = list->root; + + if (!(node != NULL && position < node->branch_size)) + /* Invalid argument. */ + abort (); + node = node_at (node, position); + return node->value; +} + +static gl_list_node_t +gl_tree_nx_set_at (gl_list_t list, size_t position, const void *elt) +{ + gl_list_node_t node = list->root; + + if (!(node != NULL && position < node->branch_size)) + /* Invalid argument. */ + abort (); + node = node_at (node, position); +#if WITH_HASHTABLE + if (elt != node->value) + { + size_t new_hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + + if (new_hashcode != node->h.hashcode) + { + remove_from_bucket (list, node); + node->value = elt; + node->h.hashcode = new_hashcode; + if (add_to_bucket (list, node) < 0) + { + /* Out of memory. We removed node from a bucket but cannot add + it to another bucket. In order to avoid inconsistencies, we + must remove node entirely from the list. */ + gl_tree_remove_node_from_tree (list, node); + free (node); + return NULL; + } + } + else + node->value = elt; + } +#else + node->value = elt; +#endif + return node; +} + +#if !WITH_HASHTABLE + +static gl_list_node_t +gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index, + const void *elt) +{ + if (!(start_index <= end_index + && end_index <= (list->root != NULL ? list->root->branch_size : 0))) + /* Invalid arguments. */ + abort (); + { + gl_listelement_equals_fn equals = list->base.equals_fn; + /* Iterate across all elements. */ + gl_list_node_t node = list->root; + iterstack_t stack; + iterstack_item_t *stack_ptr = &stack[0]; + size_t index = 0; + + if (start_index == 0) + { + /* Consider all elements. */ + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + stack_ptr->node = node; + stack_ptr->rightp = 0; + node = node->left; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + return NULL; + stack_ptr--; + if (!stack_ptr->rightp) + break; + } + node = stack_ptr->node; + /* Test against current element. */ + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + return node; + index++; + if (index >= end_index) + return NULL; + /* Descend on right branch. */ + stack_ptr->rightp = 1; + node = node->right; + stack_ptr++; + } + } + else + { + /* Consider only elements at indices >= start_index. + In this case, rightp contains the difference between the start_index + for the parent node and the one for the child node (0 when the child + node is the parent's left child, > 0 when the child is the parent's + right child). */ + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + if (node->branch_size <= start_index) + break; + stack_ptr->node = node; + stack_ptr->rightp = 0; + node = node->left; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + return NULL; + stack_ptr--; + if (!stack_ptr->rightp) + break; + start_index += stack_ptr->rightp; + } + node = stack_ptr->node; + { + size_t left_branch_size1 = + (node->left != NULL ? node->left->branch_size : 0) + 1; + if (start_index < left_branch_size1) + { + /* Test against current element. */ + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + return node; + /* Now that we have considered all indices < left_branch_size1, + we can increment start_index. */ + start_index = left_branch_size1; + } + index++; + if (index >= end_index) + return NULL; + /* Descend on right branch. */ + start_index -= left_branch_size1; + stack_ptr->rightp = left_branch_size1; + } + node = node->right; + stack_ptr++; + } + } + } +} + +static size_t +gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, + const void *elt) +{ + if (!(start_index <= end_index + && end_index <= (list->root != NULL ? list->root->branch_size : 0))) + /* Invalid arguments. */ + abort (); + { + gl_listelement_equals_fn equals = list->base.equals_fn; + /* Iterate across all elements. */ + gl_list_node_t node = list->root; + iterstack_t stack; + iterstack_item_t *stack_ptr = &stack[0]; + size_t index = 0; + + if (start_index == 0) + { + /* Consider all elements. */ + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + stack_ptr->node = node; + stack_ptr->rightp = 0; + node = node->left; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + return (size_t)(-1); + stack_ptr--; + if (!stack_ptr->rightp) + break; + } + node = stack_ptr->node; + /* Test against current element. */ + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + return index; + index++; + if (index >= end_index) + return (size_t)(-1); + /* Descend on right branch. */ + stack_ptr->rightp = 1; + node = node->right; + stack_ptr++; + } + } + else + { + /* Consider only elements at indices >= start_index. + In this case, rightp contains the difference between the start_index + for the parent node and the one for the child node (0 when the child + node is the parent's left child, > 0 when the child is the parent's + right child). */ + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + if (node->branch_size <= start_index) + break; + stack_ptr->node = node; + stack_ptr->rightp = 0; + node = node->left; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + return (size_t)(-1); + stack_ptr--; + if (!stack_ptr->rightp) + break; + start_index += stack_ptr->rightp; + } + node = stack_ptr->node; + { + size_t left_branch_size1 = + (node->left != NULL ? node->left->branch_size : 0) + 1; + if (start_index < left_branch_size1) + { + /* Test against current element. */ + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + return index; + /* Now that we have considered all indices < left_branch_size1, + we can increment start_index. */ + start_index = left_branch_size1; + } + index++; + if (index >= end_index) + return (size_t)(-1); + /* Descend on right branch. */ + start_index -= left_branch_size1; + stack_ptr->rightp = left_branch_size1; + } + node = node->right; + stack_ptr++; + } + } + } +} + +#endif + +static gl_list_node_t +gl_tree_nx_add_at (gl_list_t list, size_t position, const void *elt) +{ + size_t count = (list->root != NULL ? list->root->branch_size : 0); + + if (!(position <= count)) + /* Invalid argument. */ + abort (); + if (position == count) + return gl_tree_nx_add_last (list, elt); + else + return gl_tree_nx_add_before (list, node_at (list->root, position), elt); +} + +static bool +gl_tree_remove_node (gl_list_t list, gl_list_node_t node) +{ +#if WITH_HASHTABLE + /* Remove node from the hash table. + Note that this is only possible _before_ the node is removed from the + tree structure, because remove_from_bucket() uses node_position(). */ + remove_from_bucket (list, node); +#endif + + gl_tree_remove_node_from_tree (list, node); + + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (node->value); + free (node); + return true; +} + +static bool +gl_tree_remove_at (gl_list_t list, size_t position) +{ + gl_list_node_t node = list->root; + + if (!(node != NULL && position < node->branch_size)) + /* Invalid argument. */ + abort (); + node = node_at (node, position); + return gl_tree_remove_node (list, node); +} + +static bool +gl_tree_remove (gl_list_t list, const void *elt) +{ + if (list->root != NULL) + { + gl_list_node_t node = + gl_tree_search_from_to (list, 0, list->root->branch_size, elt); + + if (node != NULL) + return gl_tree_remove_node (list, node); + } + return false; +} + +#if !WITH_HASHTABLE + +static void +gl_tree_list_free (gl_list_t list) +{ + /* Iterate across all elements in post-order. */ + gl_list_node_t node = list->root; + iterstack_t stack; + iterstack_item_t *stack_ptr = &stack[0]; + + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + stack_ptr->node = node; + stack_ptr->rightp = false; + node = node->left; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + goto done_iterate; + stack_ptr--; + node = stack_ptr->node; + if (!stack_ptr->rightp) + break; + /* Free the current node. */ + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (node->value); + free (node); + } + /* Descend on right branch. */ + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; + } + done_iterate: + free (list); +} + +#endif + +/* --------------------- gl_list_iterator_t Data Type --------------------- */ + +static gl_list_iterator_t +gl_tree_iterator (gl_list_t list) +{ + gl_list_iterator_t result; + gl_list_node_t node; + + result.vtable = list->base.vtable; + result.list = list; + /* Start node is the leftmost node. */ + node = list->root; + if (node != NULL) + while (node->left != NULL) + node = node->left; + result.p = node; + /* End point is past the rightmost node. */ + result.q = NULL; +#if defined GCC_LINT || defined lint + result.i = 0; + result.j = 0; + result.count = 0; +#endif + + return result; +} + +static gl_list_iterator_t +gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index) +{ + size_t count = (list->root != NULL ? list->root->branch_size : 0); + gl_list_iterator_t result; + + if (!(start_index <= end_index && end_index <= count)) + /* Invalid arguments. */ + abort (); + result.vtable = list->base.vtable; + result.list = list; + /* Start node is the node at position start_index. */ + result.p = (start_index < count ? node_at (list->root, start_index) : NULL); + /* End point is the node at position end_index. */ + result.q = (end_index < count ? node_at (list->root, end_index) : NULL); +#if defined GCC_LINT || defined lint + result.i = 0; + result.j = 0; + result.count = 0; +#endif + + return result; +} + +static bool +gl_tree_iterator_next (gl_list_iterator_t *iterator, + const void **eltp, gl_list_node_t *nodep) +{ + if (iterator->p != iterator->q) + { + gl_list_node_t node = (gl_list_node_t) iterator->p; + *eltp = node->value; + if (nodep != NULL) + *nodep = node; + /* Advance to the next node. */ + if (node->right != NULL) + { + node = node->right; + while (node->left != NULL) + node = node->left; + } + else + { + while (node->parent != NULL && node->parent->right == node) + node = node->parent; + node = node->parent; + } + iterator->p = node; + return true; + } + else + return false; +} + +static void +gl_tree_iterator_free (gl_list_iterator_t *iterator) +{ +} + +/* ---------------------- Sorted gl_list_t Data Type ---------------------- */ + +static gl_list_node_t +gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node; + + for (node = list->root; node != NULL; ) + { + int cmp = compar (node->value, elt); + + if (cmp < 0) + node = node->right; + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + { + /* We have an element equal to ELT. But we need the leftmost such + element. */ + gl_list_node_t found = node; + node = node->left; + for (; node != NULL; ) + { + int cmp2 = compar (node->value, elt); + + if (cmp2 < 0) + node = node->right; + else if (cmp2 > 0) + /* The list was not sorted. */ + abort (); + else /* cmp2 == 0 */ + { + found = node; + node = node->left; + } + } + return found; + } + } + return NULL; +} + +static gl_list_node_t +gl_tree_sortedlist_search_from_to (gl_list_t list, + gl_listelement_compar_fn compar, + size_t low, size_t high, + const void *elt) +{ + gl_list_node_t node; + + if (!(low <= high + && high <= (list->root != NULL ? list->root->branch_size : 0))) + /* Invalid arguments. */ + abort (); + + for (node = list->root; node != NULL; ) + { + size_t left_branch_size = + (node->left != NULL ? node->left->branch_size : 0); + + if (low > left_branch_size) + { + low -= left_branch_size + 1; + high -= left_branch_size + 1; + node = node->right; + } + else if (high <= left_branch_size) + node = node->left; + else + { + /* Here low <= left_branch_size < high. */ + int cmp = compar (node->value, elt); + + if (cmp < 0) + { + low = 0; + high -= left_branch_size + 1; + node = node->right; + } + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + { + /* We have an element equal to ELT. But we need the leftmost + such element. */ + gl_list_node_t found = node; + node = node->left; + for (; node != NULL; ) + { + size_t left_branch_size2 = + (node->left != NULL ? node->left->branch_size : 0); + + if (low > left_branch_size2) + { + low -= left_branch_size2 + 1; + node = node->right; + } + else + { + /* Here low <= left_branch_size2. */ + int cmp2 = compar (node->value, elt); + + if (cmp2 < 0) + { + low = 0; + node = node->right; + } + else if (cmp2 > 0) + /* The list was not sorted. */ + abort (); + else /* cmp2 == 0 */ + { + found = node; + node = node->left; + } + } + } + return found; + } + } + } + return NULL; +} + +static size_t +gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node; + size_t position; + + for (node = list->root, position = 0; node != NULL; ) + { + int cmp = compar (node->value, elt); + + if (cmp < 0) + { + if (node->left != NULL) + position += node->left->branch_size; + position++; + node = node->right; + } + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + { + /* We have an element equal to ELT. But we need the leftmost such + element. */ + size_t found_position = + position + (node->left != NULL ? node->left->branch_size : 0); + node = node->left; + for (; node != NULL; ) + { + int cmp2 = compar (node->value, elt); + + if (cmp2 < 0) + { + if (node->left != NULL) + position += node->left->branch_size; + position++; + node = node->right; + } + else if (cmp2 > 0) + /* The list was not sorted. */ + abort (); + else /* cmp2 == 0 */ + { + found_position = + position + + (node->left != NULL ? node->left->branch_size : 0); + node = node->left; + } + } + return found_position; + } + } + return (size_t)(-1); +} + +static size_t +gl_tree_sortedlist_indexof_from_to (gl_list_t list, + gl_listelement_compar_fn compar, + size_t low, size_t high, + const void *elt) +{ + gl_list_node_t node; + size_t position; + + if (!(low <= high + && high <= (list->root != NULL ? list->root->branch_size : 0))) + /* Invalid arguments. */ + abort (); + + for (node = list->root, position = 0; node != NULL; ) + { + size_t left_branch_size = + (node->left != NULL ? node->left->branch_size : 0); + + if (low > left_branch_size) + { + low -= left_branch_size + 1; + high -= left_branch_size + 1; + position += left_branch_size + 1; + node = node->right; + } + else if (high <= left_branch_size) + node = node->left; + else + { + /* Here low <= left_branch_size < high. */ + int cmp = compar (node->value, elt); + + if (cmp < 0) + { + low = 0; + high -= left_branch_size + 1; + position += left_branch_size + 1; + node = node->right; + } + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + { + /* We have an element equal to ELT. But we need the leftmost + such element. */ + size_t found_position = + position + (node->left != NULL ? node->left->branch_size : 0); + node = node->left; + for (; node != NULL; ) + { + size_t left_branch_size2 = + (node->left != NULL ? node->left->branch_size : 0); + + if (low > left_branch_size2) + { + low -= left_branch_size2 + 1; + node = node->right; + } + else + { + /* Here low <= left_branch_size2. */ + int cmp2 = compar (node->value, elt); + + if (cmp2 < 0) + { + position += left_branch_size2 + 1; + node = node->right; + } + else if (cmp2 > 0) + /* The list was not sorted. */ + abort (); + else /* cmp2 == 0 */ + { + found_position = position + left_branch_size2; + node = node->left; + } + } + } + return found_position; + } + } + } + return (size_t)(-1); +} + +static gl_list_node_t +gl_tree_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node = list->root; + + if (node == NULL) + return gl_tree_nx_add_first (list, elt); + + for (;;) + { + int cmp = compar (node->value, elt); + + if (cmp < 0) + { + if (node->right == NULL) + return gl_tree_nx_add_after (list, node, elt); + node = node->right; + } + else if (cmp > 0) + { + if (node->left == NULL) + return gl_tree_nx_add_before (list, node, elt); + node = node->left; + } + else /* cmp == 0 */ + return gl_tree_nx_add_before (list, node, elt); + } +} + +static bool +gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt); + if (node != NULL) + return gl_tree_remove_node (list, node); + else + return false; +} diff --git a/mcastseed/lib/gl_anytree_oset.h b/mcastseed/lib/gl_anytree_oset.h deleted file mode 100644 index 127f4e3..0000000 --- a/mcastseed/lib/gl_anytree_oset.h +++ /dev/null @@ -1,297 +0,0 @@ -/* Ordered set data type implemented by a binary tree. - Copyright (C) 2006-2007, 2009-2016 Free Software Foundation, Inc. - Written by Bruno Haible <bruno@clisp.org>, 2006. - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 3 of the License, or - (at your option) any later version. - - 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 General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. */ - -/* Common code of gl_avltree_oset.c and gl_rbtree_oset.c. */ - -/* An item on the stack used for iterating across the elements. */ -typedef struct -{ - gl_oset_node_t node; - bool rightp; -} iterstack_item_t; - -/* A stack used for iterating across the elements. */ -typedef iterstack_item_t iterstack_t[MAXHEIGHT]; - -static gl_oset_t -gl_tree_nx_create_empty (gl_oset_implementation_t implementation, - gl_setelement_compar_fn compar_fn, - gl_setelement_dispose_fn dispose_fn) -{ - struct gl_oset_impl *set = - (struct gl_oset_impl *) malloc (sizeof (struct gl_oset_impl)); - - if (set == NULL) - return NULL; - - set->base.vtable = implementation; - set->base.compar_fn = compar_fn; - set->base.dispose_fn = dispose_fn; - set->root = NULL; - set->count = 0; - - return set; -} - -static size_t -gl_tree_size (gl_oset_t set) -{ - return set->count; -} - -static bool -gl_tree_search (gl_oset_t set, const void *elt) -{ - gl_setelement_compar_fn compar = set->base.compar_fn; - gl_oset_node_t node; - - for (node = set->root; node != NULL; ) - { - int cmp = (compar != NULL - ? compar (node->value, elt) - : (node->value > elt ? 1 : - node->value < elt ? -1 : 0)); - - if (cmp < 0) - node = node->right; - else if (cmp > 0) - node = node->left; - else /* cmp == 0 */ - /* We have an element equal to ELT. */ - return true; - } - return false; -} - -static bool -gl_tree_search_atleast (gl_oset_t set, - gl_setelement_threshold_fn threshold_fn, - const void *threshold, - const void **eltp) -{ - gl_oset_node_t node; - - for (node = set->root; node != NULL; ) - { - if (! threshold_fn (node->value, threshold)) - node = node->right; - else - { - /* We have an element >= VALUE. But we need the leftmost such - element. */ - gl_oset_node_t found = node; - node = node->left; - for (; node != NULL; ) - { - if (! threshold_fn (node->value, threshold)) - node = node->right; - else - { - found = node; - node = node->left; - } - } - *eltp = found->value; - return true; - } - } - return false; -} - -static gl_oset_node_t -gl_tree_search_node (gl_oset_t set, const void *elt) -{ - gl_setelement_compar_fn compar = set->base.compar_fn; - gl_oset_node_t node; - - for (node = set->root; node != NULL; ) - { - int cmp = (compar != NULL - ? compar (node->value, elt) - : (node->value > elt ? 1 : - node->value < elt ? -1 : 0)); - - if (cmp < 0) - node = node->right; - else if (cmp > 0) - node = node->left; - else /* cmp == 0 */ - /* We have an element equal to ELT. */ - return node; - } - return NULL; -} - -static int -gl_tree_nx_add (gl_oset_t set, const void *elt) -{ - gl_setelement_compar_fn compar; - gl_oset_node_t node = set->root; - - if (node == NULL) - { - if (gl_tree_nx_add_first (set, elt) == NULL) - return -1; - return true; - } - - compar = set->base.compar_fn; - - for (;;) - { - int cmp = (compar != NULL - ? compar (node->value, elt) - : (node->value > elt ? 1 : - node->value < elt ? -1 : 0)); - - if (cmp < 0) - { - if (node->right == NULL) - { - if (gl_tree_nx_add_after (set, node, elt) == NULL) - return -1; - return true; - } - node = node->right; - } - else if (cmp > 0) - { - if (node->left == NULL) - { - if (gl_tree_nx_add_before (set, node, elt) == NULL) - return -1; - return true; - } - node = node->left; - } - else /* cmp == 0 */ - return false; - } -} - -static bool -gl_tree_remove (gl_oset_t set, const void *elt) -{ - gl_oset_node_t node = gl_tree_search_node (set, elt); - - if (node != NULL) - return gl_tree_remove_node (set, node); - else - return false; -} - -static void -gl_tree_oset_free (gl_oset_t set) -{ - /* Iterate across all elements in post-order. */ - gl_oset_node_t node = set->root; - iterstack_t stack; - iterstack_item_t *stack_ptr = &stack[0]; - - for (;;) - { - /* Descend on left branch. */ - for (;;) - { - if (node == NULL) - break; - stack_ptr->node = node; - stack_ptr->rightp = false; - node = node->left; - stack_ptr++; - } - /* Climb up again. */ - for (;;) - { - if (stack_ptr == &stack[0]) - goto done_iterate; - stack_ptr--; - node = stack_ptr->node; - if (!stack_ptr->rightp) - break; - /* Free the current node. */ - if (set->base.dispose_fn != NULL) - set->base.dispose_fn (node->value); - free (node); - } - /* Descend on right branch. */ - stack_ptr->rightp = true; - node = node->right; - stack_ptr++; - } - done_iterate: - free (set); -} - -/* --------------------- gl_oset_iterator_t Data Type --------------------- */ - -static gl_oset_iterator_t -gl_tree_iterator (gl_oset_t set) -{ - gl_oset_iterator_t result; - gl_oset_node_t node; - - result.vtable = set->base.vtable; - result.set = set; - /* Start node is the leftmost node. */ - node = set->root; - if (node != NULL) - while (node->left != NULL) - node = node->left; - result.p = node; - /* End point is past the rightmost node. */ - result.q = NULL; -#if defined GCC_LINT || defined lint - result.i = 0; - result.j = 0; - result.count = 0; -#endif - - return result; -} - -static bool -gl_tree_iterator_next (gl_oset_iterator_t *iterator, const void **eltp) -{ - if (iterator->p != iterator->q) - { - gl_oset_node_t node = (gl_oset_node_t) iterator->p; - *eltp = node->value; - /* Advance to the next node. */ - if (node->right != NULL) - { - node = node->right; - while (node->left != NULL) - node = node->left; - } - else - { - while (node->parent != NULL && node->parent->right == node) - node = node->parent; - node = node->parent; - } - iterator->p = node; - return true; - } - else - return false; -} - -static void -gl_tree_iterator_free (gl_oset_iterator_t *iterator) -{ -} diff --git a/mcastseed/lib/gl_list.c b/mcastseed/lib/gl_list.c new file mode 100644 index 0000000..8793298 --- /dev/null +++ b/mcastseed/lib/gl_list.c @@ -0,0 +1,3 @@ +#include <config.h> +#define GL_LIST_INLINE _GL_EXTERN_INLINE +#include "gl_list.h" diff --git a/mcastseed/lib/gl_list.h b/mcastseed/lib/gl_list.h new file mode 100644 index 0000000..c9d05b0 --- /dev/null +++ b/mcastseed/lib/gl_list.h @@ -0,0 +1,841 @@ +/* Abstract sequential list data type. -*- coding: utf-8 -*- + Copyright (C) 2006-2016 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + 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 General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +#ifndef _GL_LIST_H +#define _GL_LIST_H + +#include <stdbool.h> +#include <stddef.h> + +#ifndef _GL_INLINE_HEADER_BEGIN + #error "Please include config.h first." +#endif +_GL_INLINE_HEADER_BEGIN +#ifndef GL_LIST_INLINE +# define GL_LIST_INLINE _GL_INLINE +#endif + +#ifdef __cplusplus +extern "C" { +#endif + + +/* gl_list is an abstract list data type. It can contain any number of + objects ('void *' or 'const void *' pointers) in any given order. + Duplicates are allowed, but can optionally be forbidden. + + There are several implementations of this list datatype, optimized for + different operations or for memory. You can start using the simplest list + implementation, GL_ARRAY_LIST, and switch to a different implementation + later, when you realize which operations are performed the most frequently. + The API of the different implementations is exactly the same; when + switching to a different implementation, you only have to change the + gl_list_create call. + + The implementations are: + GL_ARRAY_LIST a growable array + GL_CARRAY_LIST a growable circular array + GL_LINKED_LIST a linked list + GL_AVLTREE_LIST a binary tree (AVL tree) + GL_RBTREE_LIST a binary tree (red-black tree) + GL_LINKEDHASH_LIST a hash table with a linked list + GL_AVLTREEHASH_LIST a hash table with a binary tree (AVL tree) + GL_RBTREEHASH_LIST a hash table with a binary tree (red-black tree) + + The memory consumption is asymptotically the same: O(1) for every object + in the list. When looking more closely at the average memory consumed + for an object, GL_ARRAY_LIST is the most compact representation, and + GL_LINKEDHASH_LIST and GL_TREEHASH_LIST need more memory. + + The guaranteed average performance of the operations is, for a list of + n elements: + + Operation ARRAY LINKED TREE LINKEDHASH TREEHASH + CARRAY with|without with|without + duplicates duplicates + + gl_list_size O(1) O(1) O(1) O(1) O(1) + gl_list_node_value O(1) O(1) O(1) O(1) O(1) + gl_list_node_set_value O(1) O(1) O(1) O(1) O((log n)²)/O(1) + gl_list_next_node O(1) O(1) O(log n) O(1) O(log n) + gl_list_previous_node O(1) O(1) O(log n) O(1) O(log n) + gl_list_get_at O(1) O(n) O(log n) O(n) O(log n) + gl_list_set_at O(1) O(n) O(log n) O(n) O((log n)²)/O(log n) + gl_list_search O(n) O(n) O(n) O(n)/O(1) O(log n)/O(1) + gl_list_search_from O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n) + gl_list_search_from_to O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n) + gl_list_indexof O(n) O(n) O(n) O(n) O(log n) + gl_list_indexof_from O(n) O(n) O(n) O(n) O((log n)²)/O(log n) + gl_list_indexof_from_to O(n) O(n) O(n) O(n) O((log n)²)/O(log n) + gl_list_add_first O(n)/O(1) O(1) O(log n) O(1) O((log n)²)/O(log n) + gl_list_add_last O(1) O(1) O(log n) O(1) O((log n)²)/O(log n) + gl_list_add_before O(n) O(1) O(log n) O(1) O((log n)²)/O(log n) + gl_list_add_after O(n) O(1) O(log n) O(1) O((log n)²)/O(log n) + gl_list_add_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) + gl_list_remove_node O(n) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n) + gl_list_remove_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) + gl_list_remove O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n) + gl_list_iterator O(1) O(1) O(log n) O(1) O(log n) + gl_list_iterator_from_to O(1) O(n) O(log n) O(n) O(log n) + gl_list_iterator_next O(1) O(1) O(log n) O(1) O(log n) + gl_sortedlist_search O(log n) O(n) O(log n) O(n) O(log n) + gl_sortedlist_search_from O(log n) O(n) O(log n) O(n) O(log n) + gl_sortedlist_indexof O(log n) O(n) O(log n) O(n) O(log n) + gl_sortedlist_indexof_fro O(log n) O(n) O(log n) O(n) O(log n) + gl_sortedlist_add O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) + gl_sortedlist_remove O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) + */ + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +/* Type of function used to compare two elements. + NULL denotes pointer comparison. */ +typedef bool (*gl_listelement_equals_fn) (const void *elt1, const void *elt2); + +/* Type of function used to compute a hash code. + NULL denotes a function that depends only on the pointer itself. */ +typedef size_t (*gl_listelement_hashcode_fn) (const void *elt); + +/* Type of function used to dispose an element once it's removed from a list. + NULL denotes a no-op. */ +typedef void (*gl_listelement_dispose_fn) (const void *elt); + +struct gl_list_impl; +/* Type representing an entire list. */ +typedef struct gl_list_impl * gl_list_t; + +struct gl_list_node_impl; +/* Type representing the position of an element in the list, in a way that + is more adapted to the list implementation than a plain index. + Note: It is invalidated by insertions and removals! */ +typedef struct gl_list_node_impl * gl_list_node_t; + +struct gl_list_implementation; +/* Type representing a list datatype implementation. */ +typedef const struct gl_list_implementation * gl_list_implementation_t; + +#if 0 /* Unless otherwise specified, these are defined inline below. */ + +/* Create an empty list. + IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST, + GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST, + GL_RBTREEHASH_LIST. + EQUALS_FN is an element comparison function or NULL. + HASHCODE_FN is an element hash code function or NULL. + DISPOSE_FN is an element disposal function or NULL. + ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in + the list. The implementation may verify this at runtime. */ +/* declared in gl_xlist.h */ +extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_t gl_list_nx_create_empty (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates); + +/* Create a list with given contents. + IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST, + GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST, + GL_RBTREEHASH_LIST. + EQUALS_FN is an element comparison function or NULL. + HASHCODE_FN is an element hash code function or NULL. + DISPOSE_FN is an element disposal function or NULL. + ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in + the list. The implementation may verify this at runtime. + COUNT is the number of initial elements. + CONTENTS[0..COUNT-1] is the initial contents. */ +/* declared in gl_xlist.h */ +extern gl_list_t gl_list_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_t gl_list_nx_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents); + +/* Return the current number of elements in a list. */ +extern size_t gl_list_size (gl_list_t list); + +/* Return the element value represented by a list node. */ +extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node); + +/* Replace the element value represented by a list node. */ +/* declared in gl_xlist.h */ +extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node, + const void *elt); +/* Likewise. Return 0 upon success, -1 upon out-of-memory. */ +extern int gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Return the node immediately after the given node in the list, or NULL + if the given node is the last (rightmost) one in the list. */ +extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node); + +/* Return the node immediately before the given node in the list, or NULL + if the given node is the first (leftmost) one in the list. */ +extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node); + +/* Return the element at a given position in the list. + POSITION must be >= 0 and < gl_list_size (list). */ +extern const void * gl_list_get_at (gl_list_t list, size_t position); + +/* Replace the element at a given position in the list. + POSITION must be >= 0 and < gl_list_size (list). + Return its node. */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position, + const void *elt); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Search whether an element is already in the list. + Return its node if found, or NULL if not present in the list. */ +extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt); + +/* Search whether an element is already in the list, + at a position >= START_INDEX. + Return its node if found, or NULL if not present in the list. */ +extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index, + const void *elt); + +/* Search whether an element is already in the list, + at a position >= START_INDEX and < END_INDEX. + Return its node if found, or NULL if not present in the list. */ +extern gl_list_node_t gl_list_search_from_to (gl_list_t list, + size_t start_index, + size_t end_index, + const void *elt); + +/* Search whether an element is already in the list. + Return its position if found, or (size_t)(-1) if not present in the list. */ +extern size_t gl_list_indexof (gl_list_t list, const void *elt); + +/* Search whether an element is already in the list, + at a position >= START_INDEX. + Return its position if found, or (size_t)(-1) if not present in the list. */ +extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index, + const void *elt); + +/* Search whether an element is already in the list, + at a position >= START_INDEX and < END_INDEX. + Return its position if found, or (size_t)(-1) if not present in the list. */ +extern size_t gl_list_indexof_from_to (gl_list_t list, + size_t start_index, size_t end_index, + const void *elt); + +/* Add an element as the first element of the list. + Return its node. */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_add_first (gl_list_t list, const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Add an element as the last element of the list. + Return its node. */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_add_last (gl_list_t list, const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Add an element before a given element node of the list. + Return its node. */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node, + const void *elt); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_add_before (gl_list_t list, + gl_list_node_t node, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Add an element after a given element node of the list. + Return its node. */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node, + const void *elt); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Add an element at a given position in the list. + POSITION must be >= 0 and <= gl_list_size (list). */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position, + const void *elt); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_add_at (gl_list_t list, size_t position, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Remove an element from the list. + Return true. */ +extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node); + +/* Remove an element at a given position from the list. + POSITION must be >= 0 and < gl_list_size (list). + Return true. */ +extern bool gl_list_remove_at (gl_list_t list, size_t position); + +/* Search and remove an element from the list. + Return true if it was found and removed. */ +extern bool gl_list_remove (gl_list_t list, const void *elt); + +/* Free an entire list. + (But this call does not free the elements of the list.) */ +extern void gl_list_free (gl_list_t list); + +#endif /* End of inline and gl_xlist.h-defined functions. */ + +/* --------------------- gl_list_iterator_t Data Type --------------------- */ + +/* Functions for iterating through a list. */ + +/* Type of an iterator that traverses a list. + This is a fixed-size struct, so that creation of an iterator doesn't need + memory allocation on the heap. */ +typedef struct +{ + /* For fast dispatch of gl_list_iterator_next. */ + const struct gl_list_implementation *vtable; + /* For detecting whether the last returned element was removed. */ + gl_list_t list; + size_t count; + /* Other, implementation-private fields. */ + void *p; void *q; + size_t i; size_t j; +} gl_list_iterator_t; + +#if 0 /* These are defined inline below. */ + +/* Create an iterator traversing a list. + The list contents must not be modified while the iterator is in use, + except for replacing or removing the last returned element. */ +extern gl_list_iterator_t gl_list_iterator (gl_list_t list); + +/* Create an iterator traversing the element with indices i, + start_index <= i < end_index, of a list. + The list contents must not be modified while the iterator is in use, + except for replacing or removing the last returned element. */ +extern gl_list_iterator_t gl_list_iterator_from_to (gl_list_t list, + size_t start_index, + size_t end_index); + +/* If there is a next element, store the next element in *ELTP, store its + node in *NODEP if NODEP is non-NULL, advance the iterator and return true. + Otherwise, return false. */ +extern bool gl_list_iterator_next (gl_list_iterator_t *iterator, + const void **eltp, gl_list_node_t *nodep); + +/* Free an iterator. */ +extern void gl_list_iterator_free (gl_list_iterator_t *iterator); + +#endif /* End of inline functions. */ + +/* ---------------------- Sorted gl_list_t Data Type ---------------------- */ + +/* The following functions are for lists without duplicates where the + order is given by a sort criterion. */ + +/* Type of function used to compare two elements. Same as for qsort(). + NULL denotes pointer comparison. */ +typedef int (*gl_listelement_compar_fn) (const void *elt1, const void *elt2); + +#if 0 /* Unless otherwise specified, these are defined inline below. */ + +/* Search whether an element is already in the list. + The list is assumed to be sorted with COMPAR. + Return its node if found, or NULL if not present in the list. + If the list contains several copies of ELT, the node of the leftmost one is + returned. */ +extern gl_list_node_t gl_sortedlist_search (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); + +/* Search whether an element is already in the list. + The list is assumed to be sorted with COMPAR. + Only list elements with indices >= START_INDEX and < END_INDEX are + considered; the implementation uses these bounds to minimize the number + of COMPAR invocations. + Return its node if found, or NULL if not present in the list. + If the list contains several copies of ELT, the node of the leftmost one is + returned. */ +extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list, + gl_listelement_compar_fn compar, + size_t start_index, + size_t end_index, + const void *elt); + +/* Search whether an element is already in the list. + The list is assumed to be sorted with COMPAR. + Return its position if found, or (size_t)(-1) if not present in the list. + If the list contains several copies of ELT, the position of the leftmost one + is returned. */ +extern size_t gl_sortedlist_indexof (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); + +/* Search whether an element is already in the list. + The list is assumed to be sorted with COMPAR. + Only list elements with indices >= START_INDEX and < END_INDEX are + considered; the implementation uses these bounds to minimize the number + of COMPAR invocations. + Return its position if found, or (size_t)(-1) if not present in the list. + If the list contains several copies of ELT, the position of the leftmost one + is returned. */ +extern size_t gl_sortedlist_indexof_from_to (gl_list_t list, + gl_listelement_compar_fn compar, + size_t start_index, + size_t end_index, + const void *elt); + +/* Add an element at the appropriate position in the list. + The list is assumed to be sorted with COMPAR. + Return its node. */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_sortedlist_add (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_sortedlist_nx_add (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Search and remove an element from the list. + The list is assumed to be sorted with COMPAR. + Return true if it was found and removed. + If the list contains several copies of ELT, only the leftmost one is + removed. */ +extern bool gl_sortedlist_remove (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); + +#endif /* End of inline and gl_xlist.h-defined functions. */ + +/* ------------------------ Implementation Details ------------------------ */ + +struct gl_list_implementation +{ + /* gl_list_t functions. */ + gl_list_t (*nx_create_empty) (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates); + gl_list_t (*nx_create) (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents); + size_t (*size) (gl_list_t list); + const void * (*node_value) (gl_list_t list, gl_list_node_t node); + int (*node_nx_set_value) (gl_list_t list, gl_list_node_t node, + const void *elt); + gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node); + gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node); + const void * (*get_at) (gl_list_t list, size_t position); + gl_list_node_t (*nx_set_at) (gl_list_t list, size_t position, + const void *elt); + gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index, + size_t end_index, const void *elt); + size_t (*indexof_from_to) (gl_list_t list, size_t start_index, + size_t end_index, const void *elt); + gl_list_node_t (*nx_add_first) (gl_list_t list, const void *elt); + gl_list_node_t (*nx_add_last) (gl_list_t list, const void *elt); + gl_list_node_t (*nx_add_before) (gl_list_t list, gl_list_node_t node, + const void *elt); + gl_list_node_t (*nx_add_after) (gl_list_t list, gl_list_node_t node, + const void *elt); + gl_list_node_t (*nx_add_at) (gl_list_t list, size_t position, + const void *elt); + bool (*remove_node) (gl_list_t list, gl_list_node_t node); + bool (*remove_at) (gl_list_t list, size_t position); + bool (*remove_elt) (gl_list_t list, const void *elt); + void (*list_free) (gl_list_t list); + /* gl_list_iterator_t functions. */ + gl_list_iterator_t (*iterator) (gl_list_t list); + gl_list_iterator_t (*iterator_from_to) (gl_list_t list, + size_t start_index, + size_t end_index); + bool (*iterator_next) (gl_list_iterator_t *iterator, + const void **eltp, gl_list_node_t *nodep); + void (*iterator_free) (gl_list_iterator_t *iterator); + /* Sorted gl_list_t functions. */ + gl_list_node_t (*sortedlist_search) (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); + gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list, + gl_listelement_compar_fn compar, + size_t start_index, + size_t end_index, + const void *elt); + size_t (*sortedlist_indexof) (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); + size_t (*sortedlist_indexof_from_to) (gl_list_t list, + gl_listelement_compar_fn compar, + size_t start_index, size_t end_index, + const void *elt); + gl_list_node_t (*sortedlist_nx_add) (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); + bool (*sortedlist_remove) (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); +}; + +struct gl_list_impl_base +{ + const struct gl_list_implementation *vtable; + gl_listelement_equals_fn equals_fn; + gl_listelement_hashcode_fn hashcode_fn; + gl_listelement_dispose_fn dispose_fn; + bool allow_duplicates; +}; + +/* Define all functions of this file as accesses to the + struct gl_list_implementation. */ + +GL_LIST_INLINE gl_list_t +gl_list_nx_create_empty (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates) +{ + return implementation->nx_create_empty (implementation, equals_fn, + hashcode_fn, dispose_fn, + allow_duplicates); +} + +GL_LIST_INLINE gl_list_t +gl_list_nx_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents) +{ + return implementation->nx_create (implementation, equals_fn, hashcode_fn, + dispose_fn, allow_duplicates, count, + contents); +} + +GL_LIST_INLINE size_t +gl_list_size (gl_list_t list) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->size (list); +} + +GL_LIST_INLINE const void * +gl_list_node_value (gl_list_t list, gl_list_node_t node) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->node_value (list, node); +} + +GL_LIST_INLINE int +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node, + const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->node_nx_set_value (list, node, elt); +} + +GL_LIST_INLINE gl_list_node_t +gl_list_next_node (gl_list_t list, gl_list_node_t node) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->next_node (list, node); +} + +GL_LIST_INLINE gl_list_node_t +gl_list_previous_node (gl_list_t list, gl_list_node_t node) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->previous_node (list, node); +} + +GL_LIST_INLINE const void * +gl_list_get_at (gl_list_t list, size_t position) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->get_at (list, position); +} + +GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->nx_set_at (list, position, elt); +} + +GL_LIST_INLINE gl_list_node_t +gl_list_search (gl_list_t list, const void *elt) +{ + size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list); + return ((const struct gl_list_impl_base *) list)->vtable + ->search_from_to (list, 0, size, elt); +} + +GL_LIST_INLINE gl_list_node_t +gl_list_search_from (gl_list_t list, size_t start_index, const void *elt) +{ + size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list); + return ((const struct gl_list_impl_base *) list)->vtable + ->search_from_to (list, start_index, size, elt); +} + +GL_LIST_INLINE gl_list_node_t +gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index, + const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->search_from_to (list, start_index, end_index, elt); +} + +GL_LIST_INLINE size_t +gl_list_indexof (gl_list_t list, const void *elt) +{ + size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list); + return ((const struct gl_list_impl_base *) list)->vtable + ->indexof_from_to (list, 0, size, elt); +} + +GL_LIST_INLINE size_t +gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt) +{ + size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list); + return ((const struct gl_list_impl_base *) list)->vtable + ->indexof_from_to (list, start_index, size, elt); +} + +GL_LIST_INLINE size_t +gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, + const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->indexof_from_to (list, start_index, end_index, elt); +} + +GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_nx_add_first (gl_list_t list, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->nx_add_first (list, elt); +} + +GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_nx_add_last (gl_list_t list, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->nx_add_last (list, elt); +} + +GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->nx_add_before (list, node, elt); +} + +GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->nx_add_after (list, node, elt); +} + +GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_nx_add_at (gl_list_t list, size_t position, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->nx_add_at (list, position, elt); +} + +GL_LIST_INLINE bool +gl_list_remove_node (gl_list_t list, gl_list_node_t node) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->remove_node (list, node); +} + +GL_LIST_INLINE bool +gl_list_remove_at (gl_list_t list, size_t position) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->remove_at (list, position); +} + +GL_LIST_INLINE bool +gl_list_remove (gl_list_t list, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->remove_elt (list, elt); +} + +GL_LIST_INLINE void +gl_list_free (gl_list_t list) +{ + ((const struct gl_list_impl_base *) list)->vtable->list_free (list); +} + +GL_LIST_INLINE gl_list_iterator_t +gl_list_iterator (gl_list_t list) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->iterator (list); +} + +GL_LIST_INLINE gl_list_iterator_t +gl_list_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->iterator_from_to (list, start_index, end_index); +} + +GL_LIST_INLINE bool +gl_list_iterator_next (gl_list_iterator_t *iterator, + const void **eltp, gl_list_node_t *nodep) +{ + return iterator->vtable->iterator_next (iterator, eltp, nodep); +} + +GL_LIST_INLINE void +gl_list_iterator_free (gl_list_iterator_t *iterator) +{ + iterator->vtable->iterator_free (iterator); +} + +GL_LIST_INLINE gl_list_node_t +gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->sortedlist_search (list, compar, elt); +} + +GL_LIST_INLINE gl_list_node_t +gl_sortedlist_search_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->sortedlist_search_from_to (list, compar, start_index, end_index, + elt); +} + +GL_LIST_INLINE size_t +gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->sortedlist_indexof (list, compar, elt); +} + +GL_LIST_INLINE size_t +gl_sortedlist_indexof_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->sortedlist_indexof_from_to (list, compar, start_index, end_index, + elt); +} + +GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->sortedlist_nx_add (list, compar, elt); +} + +GL_LIST_INLINE bool +gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->sortedlist_remove (list, compar, elt); +} + +#ifdef __cplusplus +} +#endif + +_GL_INLINE_HEADER_END + +#endif /* _GL_LIST_H */ diff --git a/mcastseed/lib/gl_oset.c b/mcastseed/lib/gl_oset.c deleted file mode 100644 index 21f731a..0000000 --- a/mcastseed/lib/gl_oset.c +++ /dev/null @@ -1,3 +0,0 @@ -#include <config.h> -#define GL_OSET_INLINE _GL_EXTERN_INLINE -#include "gl_oset.h" diff --git a/mcastseed/lib/gl_oset.h b/mcastseed/lib/gl_oset.h deleted file mode 100644 index ffca315..0000000 --- a/mcastseed/lib/gl_oset.h +++ /dev/null @@ -1,293 +0,0 @@ -/* Abstract ordered set data type. - Copyright (C) 2006-2007, 2009-2016 Free Software Foundation, Inc. - Written by Bruno Haible <bruno@clisp.org>, 2006. - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 3 of the License, or - (at your option) any later version. - - 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 General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. */ - -#ifndef _GL_OSET_H -#define _GL_OSET_H - -#include <stdbool.h> -#include <stddef.h> - -#ifndef _GL_INLINE_HEADER_BEGIN - #error "Please include config.h first." -#endif -_GL_INLINE_HEADER_BEGIN -#ifndef GL_OSET_INLINE -# define GL_OSET_INLINE _GL_INLINE -#endif - -#ifdef __cplusplus -extern "C" { -#endif - - -/* gl_oset is an abstract ordered set data type. It can contain any number - of objects ('void *' or 'const void *' pointers) in the order of a given - comparator function. Duplicates (in the sense of the comparator) are - forbidden. - - There are several implementations of this ordered set datatype, optimized - for different operations or for memory. You can start using the simplest - ordered set implementation, GL_ARRAY_OSET, and switch to a different - implementation later, when you realize which operations are performed - the most frequently. The API of the different implementations is exactly - the same; when switching to a different implementation, you only have to - change the gl_oset_create call. - - The implementations are: - GL_ARRAY_OSET a growable array - GL_AVLTREE_OSET a binary tree (AVL tree) - GL_RBTREE_OSET a binary tree (red-black tree) - - The memory consumption is asymptotically the same: O(1) for every object - in the set. When looking more closely at the average memory consumed - for an object, GL_ARRAY_OSET is the most compact representation, and - GL_AVLTREE_OSET, GL_RBTREE_OSET need more memory. - - The guaranteed average performance of the operations is, for a set of - n elements: - - Operation ARRAY TREE - - gl_oset_size O(1) O(1) - gl_oset_add O(n) O(log n) - gl_oset_remove O(n) O(log n) - gl_oset_search O(log n) O(log n) - gl_oset_search_atleast O(log n) O(log n) - gl_oset_iterator O(1) O(log n) - gl_oset_iterator_next O(1) O(log n) - */ - -/* -------------------------- gl_oset_t Data Type -------------------------- */ - -/* Type of function used to compare two elements. Same as for qsort(). - NULL denotes pointer comparison. */ -typedef int (*gl_setelement_compar_fn) (const void *elt1, const void *elt2); - -/* Type of function used to dispose an element once it's removed from a set. - NULL denotes a no-op. */ -typedef void (*gl_setelement_dispose_fn) (const void *elt); - -/* Type of function used to compare an element with a threshold. - Return true if the element is greater or equal than the threshold. */ -typedef bool (*gl_setelement_threshold_fn) (const void *elt, const void *threshold); - -struct gl_oset_impl; -/* Type representing an entire ordered set. */ -typedef struct gl_oset_impl * gl_oset_t; - -struct gl_oset_implementation; -/* Type representing a ordered set datatype implementation. */ -typedef const struct gl_oset_implementation * gl_oset_implementation_t; - -#if 0 /* Unless otherwise specified, these are defined inline below. */ - -/* Create an empty set. - IMPLEMENTATION is one of GL_ARRAY_OSET, GL_AVLTREE_OSET, GL_RBTREE_OSET. - COMPAR_FN is an element comparison function or NULL. - DISPOSE_FN is an element disposal function or NULL. */ -/* declared in gl_xoset.h */ -extern gl_oset_t gl_oset_create_empty (gl_oset_implementation_t implementation, - gl_setelement_compar_fn compar_fn, - gl_setelement_dispose_fn dispose_fn); -/* Likewise. Return NULL upon out-of-memory. */ -extern gl_oset_t gl_oset_nx_create_empty (gl_oset_implementation_t implementation, - gl_setelement_compar_fn compar_fn, - gl_setelement_dispose_fn dispose_fn); - -/* Return the current number of elements in an ordered set. */ -extern size_t gl_oset_size (gl_oset_t set); - -/* Search whether an element is already in the ordered set. - Return true if found, or false if not present in the set. */ -extern bool gl_oset_search (gl_oset_t set, const void *elt); - -/* Search the least element in the ordered set that compares greater or equal - to the given THRESHOLD. The representation of the THRESHOLD is defined - by the THRESHOLD_FN. - Return true and store the found element in *ELTP if found, otherwise return - false. */ -extern bool gl_oset_search_atleast (gl_oset_t set, - gl_setelement_threshold_fn threshold_fn, - const void *threshold, - const void **eltp); - -/* Add an element to an ordered set. - Return true if it was not already in the set and added, false otherwise. */ -/* declared in gl_xoset.h */ -extern bool gl_oset_add (gl_oset_t set, const void *elt); -/* Likewise. Return -1 upon out-of-memory. */ -extern int gl_oset_nx_add (gl_oset_t set, const void *elt) -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif - ; - -/* Remove an element from an ordered set. - Return true if it was found and removed. */ -extern bool gl_oset_remove (gl_oset_t set, const void *elt); - -/* Free an entire ordered set. - (But this call does not free the elements of the set.) */ -extern void gl_oset_free (gl_oset_t set); - -#endif /* End of inline and gl_xlist.h-defined functions. */ - -/* --------------------- gl_oset_iterator_t Data Type --------------------- */ - -/* Functions for iterating through an ordered set. */ - -/* Type of an iterator that traverses an ordered set. - This is a fixed-size struct, so that creation of an iterator doesn't need - memory allocation on the heap. */ -typedef struct -{ - /* For fast dispatch of gl_oset_iterator_next. */ - const struct gl_oset_implementation *vtable; - /* For detecting whether the last returned element was removed. */ - gl_oset_t set; - size_t count; - /* Other, implementation-private fields. */ - void *p; void *q; - size_t i; size_t j; -} gl_oset_iterator_t; - -#if 0 /* These are defined inline below. */ - -/* Create an iterator traversing an ordered set. - The set's contents must not be modified while the iterator is in use, - except for removing the last returned element. */ -extern gl_oset_iterator_t gl_oset_iterator (gl_oset_t set); - -/* If there is a next element, store the next element in *ELTP, advance the - iterator and return true. Otherwise, return false. */ -extern bool gl_oset_iterator_next (gl_oset_iterator_t *iterator, - const void **eltp); - -/* Free an iterator. */ -extern void gl_oset_iterator_free (gl_oset_iterator_t *iterator); - -#endif /* End of inline functions. */ - -/* ------------------------ Implementation Details ------------------------ */ - -struct gl_oset_implementation -{ - /* gl_oset_t functions. */ - gl_oset_t (*nx_create_empty) (gl_oset_implementation_t implementation, - gl_setelement_compar_fn compar_fn, - gl_setelement_dispose_fn dispose_fn); - size_t (*size) (gl_oset_t set); - bool (*search) (gl_oset_t set, const void *elt); - bool (*search_atleast) (gl_oset_t set, - gl_setelement_threshold_fn threshold_fn, - const void *threshold, const void **eltp); - int (*nx_add) (gl_oset_t set, const void *elt); - bool (*remove_elt) (gl_oset_t set, const void *elt); - void (*oset_free) (gl_oset_t set); - /* gl_oset_iterator_t functions. */ - gl_oset_iterator_t (*iterator) (gl_oset_t set); - bool (*iterator_next) (gl_oset_iterator_t *iterator, const void **eltp); - void (*iterator_free) (gl_oset_iterator_t *iterator); -}; - -struct gl_oset_impl_base -{ - const struct gl_oset_implementation *vtable; - gl_setelement_compar_fn compar_fn; - gl_setelement_dispose_fn dispose_fn; -}; - -/* Define all functions of this file as accesses to the - struct gl_oset_implementation. */ - -GL_OSET_INLINE gl_oset_t -gl_oset_nx_create_empty (gl_oset_implementation_t implementation, - gl_setelement_compar_fn compar_fn, - gl_setelement_dispose_fn dispose_fn) -{ - return implementation->nx_create_empty (implementation, compar_fn, - dispose_fn); -} - -GL_OSET_INLINE size_t -gl_oset_size (gl_oset_t set) -{ - return ((const struct gl_oset_impl_base *) set)->vtable->size (set); -} - -GL_OSET_INLINE bool -gl_oset_search (gl_oset_t set, const void *elt) -{ - return ((const struct gl_oset_impl_base *) set)->vtable->search (set, elt); -} - -GL_OSET_INLINE bool -gl_oset_search_atleast (gl_oset_t set, - gl_setelement_threshold_fn threshold_fn, - const void *threshold, const void **eltp) -{ - return ((const struct gl_oset_impl_base *) set)->vtable - ->search_atleast (set, threshold_fn, threshold, eltp); -} - -GL_OSET_INLINE int -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif -gl_oset_nx_add (gl_oset_t set, const void *elt) -{ - return ((const struct gl_oset_impl_base *) set)->vtable->nx_add (set, elt); -} - -GL_OSET_INLINE bool -gl_oset_remove (gl_oset_t set, const void *elt) -{ - return ((const struct gl_oset_impl_base *) set)->vtable - ->remove_elt (set, elt); -} - -GL_OSET_INLINE void -gl_oset_free (gl_oset_t set) -{ - ((const struct gl_oset_impl_base *) set)->vtable->oset_free (set); -} - -GL_OSET_INLINE gl_oset_iterator_t -gl_oset_iterator (gl_oset_t set) -{ - return ((const struct gl_oset_impl_base *) set)->vtable->iterator (set); -} - -GL_OSET_INLINE bool -gl_oset_iterator_next (gl_oset_iterator_t *iterator, const void **eltp) -{ - return iterator->vtable->iterator_next (iterator, eltp); -} - -GL_OSET_INLINE void -gl_oset_iterator_free (gl_oset_iterator_t *iterator) -{ - iterator->vtable->iterator_free (iterator); -} - -#ifdef __cplusplus -} -#endif - -_GL_INLINE_HEADER_END - -#endif /* _GL_OSET_H */ diff --git a/mcastseed/lib/gl_rbtree_list.c b/mcastseed/lib/gl_rbtree_list.c new file mode 100644 index 0000000..5d621f1 --- /dev/null +++ b/mcastseed/lib/gl_rbtree_list.c @@ -0,0 +1,102 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006, 2008-2016 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + 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 General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +#include <config.h> + +/* Specification. */ +#include "gl_rbtree_list.h" + +#include <stdlib.h> + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +/* Generic red-black tree code. */ +#include "gl_anyrbtree_list1.h" + +/* Generic binary tree code. */ +#include "gl_anytree_list1.h" + +/* Generic red-black tree code. */ +#include "gl_anyrbtree_list2.h" + +/* Generic binary tree code. */ +#include "gl_anytree_list2.h" + +/* For debugging. */ +static unsigned int +check_invariants (gl_list_node_t node, gl_list_node_t parent) +{ + unsigned int left_blackheight = + (node->left != NULL ? check_invariants (node->left, node) : 0); + unsigned int right_blackheight = + (node->right != NULL ? check_invariants (node->right, node) : 0); + + if (!(node->parent == parent)) + abort (); + if (!(node->branch_size + == (node->left != NULL ? node->left->branch_size : 0) + + 1 + (node->right != NULL ? node->right->branch_size : 0))) + abort (); + if (!(node->color == BLACK || node->color == RED)) + abort (); + if (parent == NULL && !(node->color == BLACK)) + abort (); + if (!(left_blackheight == right_blackheight)) + abort (); + + return left_blackheight + (node->color == BLACK ? 1 : 0); +} +void +gl_rbtree_list_check_invariants (gl_list_t list) +{ + if (list->root != NULL) + check_invariants (list->root, NULL); +} + +const struct gl_list_implementation gl_rbtree_list_implementation = + { + gl_tree_nx_create_empty, + gl_tree_nx_create, + gl_tree_size, + gl_tree_node_value, + gl_tree_node_nx_set_value, + gl_tree_next_node, + gl_tree_previous_node, + gl_tree_get_at, + gl_tree_nx_set_at, + gl_tree_search_from_to, + gl_tree_indexof_from_to, + gl_tree_nx_add_first, + gl_tree_nx_add_last, + gl_tree_nx_add_before, + gl_tree_nx_add_after, + gl_tree_nx_add_at, + gl_tree_remove_node, + gl_tree_remove_at, + gl_tree_remove, + gl_tree_list_free, + gl_tree_iterator, + gl_tree_iterator_from_to, + gl_tree_iterator_next, + gl_tree_iterator_free, + gl_tree_sortedlist_search, + gl_tree_sortedlist_search_from_to, + gl_tree_sortedlist_indexof, + gl_tree_sortedlist_indexof_from_to, + gl_tree_sortedlist_nx_add, + gl_tree_sortedlist_remove + }; diff --git a/mcastseed/lib/gl_rbtree_oset.h b/mcastseed/lib/gl_rbtree_list.h index 850e8b4..8cb9d11 100644 --- a/mcastseed/lib/gl_rbtree_oset.h +++ b/mcastseed/lib/gl_rbtree_list.h @@ -1,4 +1,4 @@ -/* Ordered set data type implemented by a binary tree. +/* Sequential list data type implemented by a binary tree. Copyright (C) 2006, 2009-2016 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2006. @@ -15,20 +15,20 @@ You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef _GL_RBTREE_OSET_H -#define _GL_RBTREE_OSET_H +#ifndef _GL_RBTREE_LIST_H +#define _GL_RBTREE_LIST_H -#include "gl_oset.h" +#include "gl_list.h" #ifdef __cplusplus extern "C" { #endif -extern const struct gl_oset_implementation gl_rbtree_oset_implementation; -#define GL_RBTREE_OSET &gl_rbtree_oset_implementation +extern const struct gl_list_implementation gl_rbtree_list_implementation; +#define GL_RBTREE_LIST &gl_rbtree_list_implementation #ifdef __cplusplus } #endif -#endif /* _GL_RBTREE_OSET_H */ +#endif /* _GL_RBTREE_LIST_H */ diff --git a/mcastseed/m4/gnulib-cache.m4 b/mcastseed/m4/gnulib-cache.m4 index ec5cc21..d75ad4f 100644 --- a/mcastseed/m4/gnulib-cache.m4 +++ b/mcastseed/m4/gnulib-cache.m4 @@ -27,12 +27,12 @@ # Specification in the form of a command-line invocation: -# gnulib-tool --import --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --tests-base=tests --aux-dir=. --no-conditional-dependencies --no-libtool --macro-prefix=gl rbtree-oset +# gnulib-tool --import --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --tests-base=tests --aux-dir=. --no-conditional-dependencies --no-libtool --macro-prefix=gl rbtree-list # Specification in the form of a few gnulib-tool.m4 macro invocations: gl_LOCAL_DIR([]) gl_MODULES([ - rbtree-oset + rbtree-list ]) gl_AVOID([]) gl_SOURCE_BASE([lib]) diff --git a/mcastseed/m4/gnulib-comp.m4 b/mcastseed/m4/gnulib-comp.m4 index 136b568..b809eea 100644 --- a/mcastseed/m4/gnulib-comp.m4 +++ b/mcastseed/m4/gnulib-comp.m4 @@ -42,8 +42,8 @@ AC_DEFUN([gl_EARLY], AC_REQUIRE([gl_PROG_AR_RANLIB]) # Code from module extern-inline: - # Code from module oset: - # Code from module rbtree-oset: + # Code from module list: + # Code from module rbtree-list: # Code from module stdbool: ]) @@ -205,15 +205,17 @@ AC_DEFUN([gltests_LIBSOURCES], [ # This macro records the list of files which have been installed by # gnulib-tool and may be removed by future gnulib-tool invocations. AC_DEFUN([gl_FILE_LIST], [ - lib/gl_anytree_oset.h - lib/gl_oset.c - lib/gl_oset.h - lib/gl_rbtree_oset.c - lib/gl_rbtree_oset.h + lib/gl_anyrbtree_list1.h + lib/gl_anyrbtree_list2.h + lib/gl_anytree_list1.h + lib/gl_anytree_list2.h + lib/gl_list.c + lib/gl_list.h + lib/gl_rbtree_list.c + lib/gl_rbtree_list.h lib/stdbool.in.h m4/00gnulib.m4 m4/extern-inline.m4 m4/gnulib-common.m4 - m4/onceonly.m4 m4/stdbool.m4 ]) diff --git a/mcastseed/m4/onceonly.m4 b/mcastseed/m4/onceonly.m4 deleted file mode 100644 index c0c9e2c..0000000 --- a/mcastseed/m4/onceonly.m4 +++ /dev/null @@ -1,104 +0,0 @@ -# onceonly.m4 serial 9 -dnl Copyright (C) 2002-2003, 2005-2006, 2008-2016 Free Software Foundation, -dnl Inc. -dnl -dnl This file is free software; you can redistribute it and/or modify -dnl it under the terms of the GNU General Public License as published by -dnl the Free Software Foundation; either version 3 of the License, or -dnl (at your option) any later version. -dnl -dnl This file is distributed in the hope that it will be useful, -dnl but WITHOUT ANY WARRANTY; without even the implied warranty of -dnl MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -dnl GNU General Public License for more details. -dnl -dnl You should have received a copy of the GNU General Public License -dnl along with this file. If not, see <http://www.gnu.org/licenses/>. -dnl -dnl As a special exception to the GNU General Public License, -dnl this file may be distributed as part of a program -dnl that contains a configuration script generated by Autoconf, under -dnl the same distribution terms as the rest of that program. - -dnl This file defines some "once only" variants of standard autoconf macros. -dnl AC_CHECK_HEADERS_ONCE like AC_CHECK_HEADERS -dnl AC_CHECK_FUNCS_ONCE like AC_CHECK_FUNCS -dnl AC_CHECK_DECLS_ONCE like AC_CHECK_DECLS -dnl AC_REQUIRE([AC_FUNC_STRCOLL]) like AC_FUNC_STRCOLL -dnl The advantage is that the check for each of the headers/functions/decls -dnl will be put only once into the 'configure' file. It keeps the size of -dnl the 'configure' file down, and avoids redundant output when 'configure' -dnl is run. -dnl The drawback is that the checks cannot be conditionalized. If you write -dnl if some_condition; then gl_CHECK_HEADERS(stdlib.h); fi -dnl inside an AC_DEFUNed function, the gl_CHECK_HEADERS macro call expands to -dnl empty, and the check will be inserted before the body of the AC_DEFUNed -dnl function. - -dnl The original code implemented AC_CHECK_HEADERS_ONCE and AC_CHECK_FUNCS_ONCE -dnl in terms of AC_DEFUN and AC_REQUIRE. This implementation uses diversions to -dnl named sections DEFAULTS and INIT_PREPARE in order to check all requested -dnl headers at once, thus reducing the size of 'configure'. It is known to work -dnl with autoconf 2.57..2.62 at least . The size reduction is ca. 9%. - -dnl Autoconf version 2.59 plus gnulib is required; this file is not needed -dnl with Autoconf 2.60 or greater. But note that autoconf's implementation of -dnl AC_CHECK_DECLS_ONCE expects a comma-separated list of symbols as first -dnl argument! -AC_PREREQ([2.59]) - -# AC_CHECK_HEADERS_ONCE(HEADER1 HEADER2 ...) is a once-only variant of -# AC_CHECK_HEADERS(HEADER1 HEADER2 ...). -AC_DEFUN([AC_CHECK_HEADERS_ONCE], [ - : - m4_foreach_w([gl_HEADER_NAME], [$1], [ - AC_DEFUN([gl_CHECK_HEADER_]m4_quote(m4_translit(gl_HEADER_NAME, - [./-], [___])), [ - m4_divert_text([INIT_PREPARE], - [gl_header_list="$gl_header_list gl_HEADER_NAME"]) - gl_HEADERS_EXPANSION - AH_TEMPLATE(AS_TR_CPP([HAVE_]m4_defn([gl_HEADER_NAME])), - [Define to 1 if you have the <]m4_defn([gl_HEADER_NAME])[> header file.]) - ]) - AC_REQUIRE([gl_CHECK_HEADER_]m4_quote(m4_translit(gl_HEADER_NAME, - [./-], [___]))) - ]) -]) -m4_define([gl_HEADERS_EXPANSION], [ - m4_divert_text([DEFAULTS], [gl_header_list=]) - AC_CHECK_HEADERS([$gl_header_list]) - m4_define([gl_HEADERS_EXPANSION], []) -]) - -# AC_CHECK_FUNCS_ONCE(FUNC1 FUNC2 ...) is a once-only variant of -# AC_CHECK_FUNCS(FUNC1 FUNC2 ...). -AC_DEFUN([AC_CHECK_FUNCS_ONCE], [ - : - m4_foreach_w([gl_FUNC_NAME], [$1], [ - AC_DEFUN([gl_CHECK_FUNC_]m4_defn([gl_FUNC_NAME]), [ - m4_divert_text([INIT_PREPARE], - [gl_func_list="$gl_func_list gl_FUNC_NAME"]) - gl_FUNCS_EXPANSION - AH_TEMPLATE(AS_TR_CPP([HAVE_]m4_defn([gl_FUNC_NAME])), - [Define to 1 if you have the ']m4_defn([gl_FUNC_NAME])[' function.]) - ]) - AC_REQUIRE([gl_CHECK_FUNC_]m4_defn([gl_FUNC_NAME])) - ]) -]) -m4_define([gl_FUNCS_EXPANSION], [ - m4_divert_text([DEFAULTS], [gl_func_list=]) - AC_CHECK_FUNCS([$gl_func_list]) - m4_define([gl_FUNCS_EXPANSION], []) -]) - -# AC_CHECK_DECLS_ONCE(DECL1 DECL2 ...) is a once-only variant of -# AC_CHECK_DECLS(DECL1, DECL2, ...). -AC_DEFUN([AC_CHECK_DECLS_ONCE], [ - : - m4_foreach_w([gl_DECL_NAME], [$1], [ - AC_DEFUN([gl_CHECK_DECL_]m4_defn([gl_DECL_NAME]), [ - AC_CHECK_DECLS(m4_defn([gl_DECL_NAME])) - ]) - AC_REQUIRE([gl_CHECK_DECL_]m4_defn([gl_DECL_NAME])) - ]) -]) |