summaryrefslogtreecommitdiff
path: root/draft/mcastseed/lib
diff options
context:
space:
mode:
authorLudovic Pouzenc <ludovic@pouzenc.fr>2017-05-05 11:28:51 +0200
committerLudovic Pouzenc <ludovic@pouzenc.fr>2017-05-05 11:28:51 +0200
commit604f3d64764270c052cfb43081ec522237bbdb75 (patch)
treeb3db80e35399412693c7a986b3021435b2914fe4 /draft/mcastseed/lib
parentf7f175cb29192682f3ece9479f24a40672a3d74d (diff)
downloadeficast-604f3d64764270c052cfb43081ec522237bbdb75.tar.gz
eficast-604f3d64764270c052cfb43081ec522237bbdb75.tar.bz2
eficast-604f3d64764270c052cfb43081ec522237bbdb75.zip
Massive add for all draft stuff to keep it in sync
Diffstat (limited to 'draft/mcastseed/lib')
-rw-r--r--draft/mcastseed/lib/Makefile.am93
-rw-r--r--draft/mcastseed/lib/gl_anyrbtree_list1.h76
-rw-r--r--draft/mcastseed/lib/gl_anyrbtree_list2.h1028
-rw-r--r--draft/mcastseed/lib/gl_anytree_list1.h41
-rw-r--r--draft/mcastseed/lib/gl_anytree_list2.h940
-rw-r--r--draft/mcastseed/lib/gl_list.c3
-rw-r--r--draft/mcastseed/lib/gl_list.h841
-rw-r--r--draft/mcastseed/lib/gl_rbtree_list.c102
-rw-r--r--draft/mcastseed/lib/gl_rbtree_list.h34
-rw-r--r--draft/mcastseed/lib/stdbool.in.h132
10 files changed, 3290 insertions, 0 deletions
diff --git a/draft/mcastseed/lib/Makefile.am b/draft/mcastseed/lib/Makefile.am
new file mode 100644
index 0000000..38faabe
--- /dev/null
+++ b/draft/mcastseed/lib/Makefile.am
@@ -0,0 +1,93 @@
+## DO NOT EDIT! GENERATED AUTOMATICALLY!
+## Process this file with automake to produce Makefile.in.
+# Copyright (C) 2002-2016 Free Software Foundation, Inc.
+#
+# This file 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 file 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 file. If not, see <http://www.gnu.org/licenses/>.
+#
+# As a special exception to the GNU General Public License,
+# this file may be distributed as part of a program that
+# contains a configuration script generated by Autoconf, under
+# 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-list
+
+AUTOMAKE_OPTIONS = 1.9.6 gnits
+
+SUBDIRS =
+noinst_HEADERS =
+noinst_LIBRARIES =
+noinst_LTLIBRARIES =
+EXTRA_DIST =
+BUILT_SOURCES =
+SUFFIXES =
+MOSTLYCLEANFILES = core *.stackdump
+MOSTLYCLEANDIRS =
+CLEANFILES =
+DISTCLEANFILES =
+MAINTAINERCLEANFILES =
+
+AM_CPPFLAGS =
+AM_CFLAGS =
+
+noinst_LIBRARIES += libgnu.a
+
+libgnu_a_SOURCES =
+libgnu_a_LIBADD = $(gl_LIBOBJS)
+libgnu_a_DEPENDENCIES = $(gl_LIBOBJS)
+EXTRA_libgnu_a_SOURCES =
+
+## begin gnulib module list
+
+libgnu_a_SOURCES += gl_list.h gl_list.c
+
+## end gnulib module list
+
+## begin gnulib module rbtree-list
+
+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-list
+
+## begin gnulib module stdbool
+
+BUILT_SOURCES += $(STDBOOL_H)
+
+# We need the following in order to create <stdbool.h> when the system
+# doesn't have one that works.
+if GL_GENERATE_STDBOOL_H
+stdbool.h: stdbool.in.h $(top_builddir)/config.status
+ $(AM_V_GEN)rm -f $@-t $@ && \
+ { echo '/* DO NOT EDIT! GENERATED AUTOMATICALLY! */'; \
+ sed -e 's/@''HAVE__BOOL''@/$(HAVE__BOOL)/g' < $(srcdir)/stdbool.in.h; \
+ } > $@-t && \
+ mv $@-t $@
+else
+stdbool.h: $(top_builddir)/config.status
+ rm -f $@
+endif
+MOSTLYCLEANFILES += stdbool.h stdbool.h-t
+
+EXTRA_DIST += stdbool.in.h
+
+## end gnulib module stdbool
+
+
+mostlyclean-local: mostlyclean-generic
+ @for dir in '' $(MOSTLYCLEANDIRS); do \
+ if test -n "$$dir" && test -d $$dir; then \
+ echo "rmdir $$dir"; rmdir $$dir; \
+ fi; \
+ done; \
+ :
diff --git a/draft/mcastseed/lib/gl_anyrbtree_list1.h b/draft/mcastseed/lib/gl_anyrbtree_list1.h
new file mode 100644
index 0000000..0ae0715
--- /dev/null
+++ b/draft/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/draft/mcastseed/lib/gl_anyrbtree_list2.h b/draft/mcastseed/lib/gl_anyrbtree_list2.h
new file mode 100644
index 0000000..a0e2e43
--- /dev/null
+++ b/draft/mcastseed/lib/gl_anyrbtree_list2.h
@@ -0,0 +1,1028 @@
+/* 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.
+
+ 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. */
+
+/* -------------------------- gl_list_t Data Type -------------------------- */
+
+/* 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;
+
+ node->color = (bh == 0 ? RED : BLACK);
+
+ node->branch_size = count;
+
+ return node;
+
+ 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_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.
+
+ B D
+ / \ / \
+ A D --> B E
+ / \ / \
+ C E A C
+
+ Change the tree structure, update the branch sizes.
+ The caller must update the colors and register D as child of its parent. */
+static gl_list_node_t
+rotate_left (gl_list_node_t b_node, gl_list_node_t d_node)
+{
+ 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;
+
+ d_node->parent = b_node->parent;
+ b_node->parent = 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;
+}
+
+/* Rotate right a subtree.
+
+ D B
+ / \ / \
+ B E --> A D
+ / \ / \
+ A C C E
+
+ Change the tree structure, update the branch sizes.
+ The caller must update the colors and register B as child of its parent. */
+static gl_list_node_t
+rotate_right (gl_list_node_t b_node, gl_list_node_t d_node)
+{
+ 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;
+
+ b_node->parent = d_node->parent;
+ d_node->parent = b_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;
+}
+
+/* Ensure the tree is balanced, after an insertion operation.
+ Also assigns node->color.
+ parent is the given node's parent, known to be non-NULL. */
+static void
+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_list_node_t grandparent;
+ gl_list_node_t uncle;
+
+ if (parent->color == BLACK)
+ {
+ /* A RED color for node is acceptable. */
+ node->color = RED;
+ return;
+ }
+
+ grandparent = parent->parent;
+ /* Since parent is RED, we know that
+ grandparent is != NULL and colored BLACK. */
+
+ if (grandparent->left == parent)
+ uncle = grandparent->right;
+ else if (grandparent->right == parent)
+ uncle = grandparent->left;
+ else
+ abort ();
+
+ if (uncle != NULL && uncle->color == RED)
+ {
+ /* Change grandparent from BLACK to RED, and
+ change parent and uncle from RED to BLACK.
+ This makes it acceptable for node to be RED. */
+ node->color = RED;
+ parent->color = uncle->color = BLACK;
+ node = grandparent;
+ }
+ else
+ {
+ /* grandparent and uncle are BLACK. parent is RED. node wants
+ to be RED too.
+ In this case, recoloring is not sufficient. Need to perform
+ one or two rotations. */
+ gl_list_node_t *grandparentp;
+
+ if (grandparent->parent == NULL)
+ grandparentp = &list->root;
+ else if (grandparent->parent->left == grandparent)
+ grandparentp = &grandparent->parent->left;
+ else if (grandparent->parent->right == grandparent)
+ grandparentp = &grandparent->parent->right;
+ else
+ abort ();
+
+ if (grandparent->left == parent)
+ {
+ if (parent->right == node)
+ {
+ /* Rotation between node and parent. */
+ grandparent->left = rotate_left (parent, node);
+ node = parent;
+ parent = grandparent->left;
+ }
+ /* grandparent and uncle are BLACK. parent and node want to be
+ RED. parent = grandparent->left. node = parent->left.
+
+ grandparent parent
+ bh+1 bh+1
+ / \ / \
+ parent uncle --> node grandparent
+ bh bh bh bh
+ / \ / \
+ node C C uncle
+ bh bh bh bh
+ */
+ *grandparentp = rotate_right (parent, grandparent);
+ parent->color = BLACK;
+ node->color = grandparent->color = RED;
+ }
+ else /* grandparent->right == parent */
+ {
+ if (parent->left == node)
+ {
+ /* Rotation between node and parent. */
+ grandparent->right = rotate_right (node, parent);
+ node = parent;
+ parent = grandparent->right;
+ }
+ /* grandparent and uncle are BLACK. parent and node want to be
+ RED. parent = grandparent->right. node = parent->right.
+
+ grandparent parent
+ bh+1 bh+1
+ / \ / \
+ uncle parent --> grandparent node
+ bh bh bh bh
+ / \ / \
+ C node uncle C
+ bh bh bh bh
+ */
+ *grandparentp = rotate_left (grandparent, parent);
+ parent->color = BLACK;
+ node->color = grandparent->color = RED;
+ }
+ return;
+ }
+
+ /* Start again with a new (node, parent) pair. */
+ parent = node->parent;
+
+ if (parent == NULL)
+ {
+ /* Change node's color from RED to BLACK. This increases the
+ tree's black-height. */
+ node->color = BLACK;
+ return;
+ }
+ }
+}
+
+/* Ensure the tree is balanced, after a deletion operation.
+ CHILD was a grandchild of PARENT and is now its child. Between them,
+ 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_list_t list, gl_list_node_t child, gl_list_node_t parent)
+{
+ for (;;)
+ {
+ /* At this point, we reduced the black-height of the CHILD subtree by 1.
+ 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_list_node_t *parentp;
+
+ if (parent->parent == NULL)
+ parentp = &list->root;
+ else if (parent->parent->left == parent)
+ parentp = &parent->parent->left;
+ else if (parent->parent->right == parent)
+ parentp = &parent->parent->right;
+ else
+ abort ();
+
+ if (parent->left == child)
+ {
+ gl_list_node_t sibling = parent->right;
+ /* sibling's black-height is >= 1. In particular,
+ sibling != NULL.
+
+ parent
+ / \
+ child sibling
+ bh bh+1
+ */
+
+ if (sibling->color == RED)
+ {
+ /* sibling is RED, hence parent is BLACK and sibling's children
+ are non-NULL and BLACK.
+
+ parent sibling
+ bh+2 bh+2
+ / \ / \
+ child sibling --> parent SR
+ bh bh+1 bh+1 bh+1
+ / \ / \
+ SL SR child SL
+ bh+1 bh+1 bh bh+1
+ */
+ *parentp = rotate_left (parent, sibling);
+ parent->color = RED;
+ sibling->color = BLACK;
+
+ /* Concentrate on the subtree of parent. The new sibling is
+ one of the old sibling's children, and known to be BLACK. */
+ parentp = &sibling->left;
+ sibling = parent->right;
+ }
+ /* Now we know that sibling is BLACK.
+
+ parent
+ / \
+ child sibling
+ bh bh+1
+ */
+ if (sibling->right != NULL && sibling->right->color == RED)
+ {
+ /*
+ parent sibling
+ bh+1|bh+2 bh+1|bh+2
+ / \ / \
+ child sibling --> parent SR
+ bh bh+1 bh+1 bh+1
+ / \ / \
+ SL SR child SL
+ bh bh bh bh
+ */
+ *parentp = rotate_left (parent, sibling);
+ sibling->color = parent->color;
+ parent->color = BLACK;
+ sibling->right->color = BLACK;
+ return;
+ }
+ else if (sibling->left != NULL && sibling->left->color == RED)
+ {
+ /*
+ parent parent
+ bh+1|bh+2 bh+1|bh+2
+ / \ / \
+ child sibling --> child SL
+ bh bh+1 bh bh+1
+ / \ / \
+ SL SR SLL sibling
+ bh bh bh bh
+ / \ / \
+ SLL SLR SLR SR
+ bh bh bh bh
+
+ where SLL, SLR, SR are all black.
+ */
+ parent->right = rotate_right (sibling->left, sibling);
+ /* Change sibling from BLACK to RED and SL from RED to BLACK. */
+ sibling->color = RED;
+ sibling = parent->right;
+ sibling->color = BLACK;
+
+ /* Now do as in the previous case. */
+ *parentp = rotate_left (parent, sibling);
+ sibling->color = parent->color;
+ parent->color = BLACK;
+ sibling->right->color = BLACK;
+ return;
+ }
+ else
+ {
+ if (parent->color == BLACK)
+ {
+ /* Change sibling from BLACK to RED. Then the entire
+ subtree at parent has decreased its black-height.
+ parent parent
+ bh+2 bh+1
+ / \ / \
+ child sibling --> child sibling
+ bh bh+1 bh bh
+ */
+ sibling->color = RED;
+
+ child = parent;
+ }
+ else
+ {
+ /* Change parent from RED to BLACK, but compensate by
+ changing sibling from BLACK to RED.
+ parent parent
+ bh+1 bh+1
+ / \ / \
+ child sibling --> child sibling
+ bh bh+1 bh bh
+ */
+ parent->color = BLACK;
+ sibling->color = RED;
+ return;
+ }
+ }
+ }
+ else if (parent->right == child)
+ {
+ gl_list_node_t sibling = parent->left;
+ /* sibling's black-height is >= 1. In particular,
+ sibling != NULL.
+
+ parent
+ / \
+ sibling child
+ bh+1 bh
+ */
+
+ if (sibling->color == RED)
+ {
+ /* sibling is RED, hence parent is BLACK and sibling's children
+ are non-NULL and BLACK.
+
+ parent sibling
+ bh+2 bh+2
+ / \ / \
+ sibling child --> SR parent
+ bh+1 ch bh+1 bh+1
+ / \ / \
+ SL SR SL child
+ bh+1 bh+1 bh+1 bh
+ */
+ *parentp = rotate_right (sibling, parent);
+ parent->color = RED;
+ sibling->color = BLACK;
+
+ /* Concentrate on the subtree of parent. The new sibling is
+ one of the old sibling's children, and known to be BLACK. */
+ parentp = &sibling->right;
+ sibling = parent->left;
+ }
+ /* Now we know that sibling is BLACK.
+
+ parent
+ / \
+ sibling child
+ bh+1 bh
+ */
+ if (sibling->left != NULL && sibling->left->color == RED)
+ {
+ /*
+ parent sibling
+ bh+1|bh+2 bh+1|bh+2
+ / \ / \
+ sibling child --> SL parent
+ bh+1 bh bh+1 bh+1
+ / \ / \
+ SL SR SR child
+ bh bh bh bh
+ */
+ *parentp = rotate_right (sibling, parent);
+ sibling->color = parent->color;
+ parent->color = BLACK;
+ sibling->left->color = BLACK;
+ return;
+ }
+ else if (sibling->right != NULL && sibling->right->color == RED)
+ {
+ /*
+ parent parent
+ bh+1|bh+2 bh+1|bh+2
+ / \ / \
+ sibling child --> SR child
+ bh+1 bh bh+1 bh
+ / \ / \
+ SL SR sibling SRR
+ bh bh bh bh
+ / \ / \
+ SRL SRR SL SRL
+ bh bh bh bh
+
+ where SL, SRL, SRR are all black.
+ */
+ parent->left = rotate_left (sibling, sibling->right);
+ /* Change sibling from BLACK to RED and SL from RED to BLACK. */
+ sibling->color = RED;
+ sibling = parent->left;
+ sibling->color = BLACK;
+
+ /* Now do as in the previous case. */
+ *parentp = rotate_right (sibling, parent);
+ sibling->color = parent->color;
+ parent->color = BLACK;
+ sibling->left->color = BLACK;
+ return;
+ }
+ else
+ {
+ if (parent->color == BLACK)
+ {
+ /* Change sibling from BLACK to RED. Then the entire
+ subtree at parent has decreased its black-height.
+ parent parent
+ bh+2 bh+1
+ / \ / \
+ sibling child --> sibling child
+ bh+1 bh bh bh
+ */
+ sibling->color = RED;
+
+ child = parent;
+ }
+ else
+ {
+ /* Change parent from RED to BLACK, but compensate by
+ changing sibling from BLACK to RED.
+ parent parent
+ bh+1 bh+1
+ / \ / \
+ sibling child --> sibling child
+ bh+1 bh bh bh
+ */
+ parent->color = BLACK;
+ sibling->color = RED;
+ return;
+ }
+ }
+ }
+ else
+ abort ();
+
+ /* Start again with a new (child, parent) pair. */
+ parent = child->parent;
+
+#if 0 /* Already handled. */
+ if (child != NULL && child->color == RED)
+ {
+ child->color = BLACK;
+ return;
+ }
+#endif
+
+ if (parent == NULL)
+ return;
+ }
+}
+
+static void
+gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node)
+{
+ gl_list_node_t parent = node->parent;
+
+ if (node->left == NULL)
+ {
+ /* Replace node with node->right. */
+ gl_list_node_t child = node->right;
+
+ if (child != NULL)
+ {
+ child->parent = parent;
+ /* Since node->left == NULL, child must be RED and of height 1,
+ hence node must have been BLACK. Recolor the child. */
+ child->color = BLACK;
+ }
+ if (parent == NULL)
+ 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--;
+ }
+
+ if (child == NULL && node->color == BLACK)
+ rebalance_after_remove (list, child, parent);
+ }
+ }
+ else if (node->right == NULL)
+ {
+ /* 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_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)
+ 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_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; )
+ subst = subst->right;
+
+ subst_parent = subst->parent;
+
+ child = subst->left;
+
+ removed_color = subst->color;
+
+ /* The case subst_parent == node is special: If we do nothing special,
+ we get confusion about node->left, subst->left and child->parent.
+ subst_parent == node
+ <==> The 'for' loop above terminated immediately.
+ <==> subst == subst_parent->left
+ [otherwise subst == subst_parent->right]
+ In this case, we would need to first set
+ child->parent = node; node->left = child;
+ and later - when we copy subst into node's position - again
+ child->parent = subst; subst->left = child;
+ Altogether a no-op. */
+ if (subst_parent != node)
+ {
+ if (child != NULL)
+ child->parent = subst_parent;
+ 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.) */
+ if (subst_parent != node)
+ {
+ subst->left = node->left;
+ subst->left->parent = subst;
+ }
+ subst->right = node->right;
+ subst->right->parent = subst;
+ subst->color = node->color;
+ subst->branch_size = node->branch_size;
+ subst->parent = parent;
+ if (parent == NULL)
+ list->root = subst;
+ else if (parent->left == node)
+ parent->left = subst;
+ else /* parent->right == node */
+ parent->right = subst;
+
+ if (removed_color == BLACK)
+ {
+ if (child != NULL && child->color == RED)
+ /* Recolor the child. */
+ child->color = BLACK;
+ else
+ /* 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 (list, child,
+ subst_parent != node ? subst_parent : subst);
+ }
+ }
+}
+
+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));
+
+ 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)
+{
+ /* 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;
+}
+
+static gl_list_node_t
+gl_tree_nx_add_before (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->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;
+}
+
+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_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/draft/mcastseed/lib/gl_anytree_list1.h b/draft/mcastseed/lib/gl_anytree_list1.h
new file mode 100644
index 0000000..675f107
--- /dev/null
+++ b/draft/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/draft/mcastseed/lib/gl_anytree_list2.h b/draft/mcastseed/lib/gl_anytree_list2.h
new file mode 100644
index 0000000..7e6fe45
--- /dev/null
+++ b/draft/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/draft/mcastseed/lib/gl_list.c b/draft/mcastseed/lib/gl_list.c
new file mode 100644
index 0000000..8793298
--- /dev/null
+++ b/draft/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/draft/mcastseed/lib/gl_list.h b/draft/mcastseed/lib/gl_list.h
new file mode 100644
index 0000000..c9d05b0
--- /dev/null
+++ b/draft/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/draft/mcastseed/lib/gl_rbtree_list.c b/draft/mcastseed/lib/gl_rbtree_list.c
new file mode 100644
index 0000000..5d621f1
--- /dev/null
+++ b/draft/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/draft/mcastseed/lib/gl_rbtree_list.h b/draft/mcastseed/lib/gl_rbtree_list.h
new file mode 100644
index 0000000..8cb9d11
--- /dev/null
+++ b/draft/mcastseed/lib/gl_rbtree_list.h
@@ -0,0 +1,34 @@
+/* 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/>. */
+
+#ifndef _GL_RBTREE_LIST_H
+#define _GL_RBTREE_LIST_H
+
+#include "gl_list.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+extern const struct gl_list_implementation gl_rbtree_list_implementation;
+#define GL_RBTREE_LIST &gl_rbtree_list_implementation
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _GL_RBTREE_LIST_H */
diff --git a/draft/mcastseed/lib/stdbool.in.h b/draft/mcastseed/lib/stdbool.in.h
new file mode 100644
index 0000000..7ecf203
--- /dev/null
+++ b/draft/mcastseed/lib/stdbool.in.h
@@ -0,0 +1,132 @@
+/* Copyright (C) 2001-2003, 2006-2016 Free Software Foundation, Inc.
+ Written by Bruno Haible <haible@clisp.cons.org>, 2001.
+
+ 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, 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_STDBOOL_H
+#define _GL_STDBOOL_H
+
+/* ISO C 99 <stdbool.h> for platforms that lack it. */
+
+/* Usage suggestions:
+
+ Programs that use <stdbool.h> should be aware of some limitations
+ and standards compliance issues.
+
+ Standards compliance:
+
+ - <stdbool.h> must be #included before 'bool', 'false', 'true'
+ can be used.
+
+ - You cannot assume that sizeof (bool) == 1.
+
+ - Programs should not undefine the macros bool, true, and false,
+ as C99 lists that as an "obsolescent feature".
+
+ Limitations of this substitute, when used in a C89 environment:
+
+ - <stdbool.h> must be #included before the '_Bool' type can be used.
+
+ - You cannot assume that _Bool is a typedef; it might be a macro.
+
+ - Bit-fields of type 'bool' are not supported. Portable code
+ should use 'unsigned int foo : 1;' rather than 'bool foo : 1;'.
+
+ - In C99, casts and automatic conversions to '_Bool' or 'bool' are
+ performed in such a way that every nonzero value gets converted
+ to 'true', and zero gets converted to 'false'. This doesn't work
+ with this substitute. With this substitute, only the values 0 and 1
+ give the expected result when converted to _Bool' or 'bool'.
+
+ - C99 allows the use of (_Bool)0.0 in constant expressions, but
+ this substitute cannot always provide this property.
+
+ Also, it is suggested that programs use 'bool' rather than '_Bool';
+ this isn't required, but 'bool' is more common. */
+
+
+/* 7.16. Boolean type and values */
+
+/* BeOS <sys/socket.h> already #defines false 0, true 1. We use the same
+ definitions below, but temporarily we have to #undef them. */
+#if defined __BEOS__ && !defined __HAIKU__
+# include <OS.h> /* defines bool but not _Bool */
+# undef false
+# undef true
+#endif
+
+#ifdef __cplusplus
+# define _Bool bool
+# define bool bool
+#else
+# if defined __BEOS__ && !defined __HAIKU__
+ /* A compiler known to have 'bool'. */
+ /* If the compiler already has both 'bool' and '_Bool', we can assume they
+ are the same types. */
+# if !@HAVE__BOOL@
+typedef bool _Bool;
+# endif
+# else
+# if !defined __GNUC__
+ /* If @HAVE__BOOL@:
+ Some HP-UX cc and AIX IBM C compiler versions have compiler bugs when
+ the built-in _Bool type is used. See
+ http://gcc.gnu.org/ml/gcc-patches/2003-12/msg02303.html
+ http://lists.gnu.org/archive/html/bug-coreutils/2005-11/msg00161.html
+ http://lists.gnu.org/archive/html/bug-coreutils/2005-10/msg00086.html
+ Similar bugs are likely with other compilers as well; this file
+ wouldn't be used if <stdbool.h> was working.
+ So we override the _Bool type.
+ If !@HAVE__BOOL@:
+ Need to define _Bool ourselves. As 'signed char' or as an enum type?
+ Use of a typedef, with SunPRO C, leads to a stupid
+ "warning: _Bool is a keyword in ISO C99".
+ Use of an enum type, with IRIX cc, leads to a stupid
+ "warning(1185): enumerated type mixed with another type".
+ Even the existence of an enum type, without a typedef,
+ "Invalid enumerator. (badenum)" with HP-UX cc on Tru64.
+ The only benefit of the enum, debuggability, is not important
+ with these compilers. So use 'signed char' and no enum. */
+# define _Bool signed char
+# else
+ /* With this compiler, trust the _Bool type if the compiler has it. */
+# if !@HAVE__BOOL@
+ /* For the sake of symbolic names in gdb, define true and false as
+ enum constants, not only as macros.
+ It is tempting to write
+ typedef enum { false = 0, true = 1 } _Bool;
+ so that gdb prints values of type 'bool' symbolically. But then
+ values of type '_Bool' might promote to 'int' or 'unsigned int'
+ (see ISO C 99 6.7.2.2.(4)); however, '_Bool' must promote to 'int'
+ (see ISO C 99 6.3.1.1.(2)). So add a negative value to the
+ enum; this ensures that '_Bool' promotes to 'int'. */
+typedef enum { _Bool_must_promote_to_int = -1, false = 0, true = 1 } _Bool;
+# endif
+# endif
+# endif
+# define bool _Bool
+#endif
+
+/* The other macros must be usable in preprocessor directives. */
+#ifdef __cplusplus
+# define false false
+# define true true
+#else
+# define false 0
+# define true 1
+#endif
+
+#define __bool_true_false_are_defined 1
+
+#endif /* _GL_STDBOOL_H */