diff options
Diffstat (limited to 'mcastseed/lib')
| -rw-r--r-- | mcastseed/lib/Makefile.am | 93 | ||||
| -rw-r--r-- | mcastseed/lib/gl_anyrbtree_list1.h | 76 | ||||
| -rw-r--r-- | mcastseed/lib/gl_anyrbtree_list2.h | 1028 | ||||
| -rw-r--r-- | mcastseed/lib/gl_anytree_list1.h | 41 | ||||
| -rw-r--r-- | mcastseed/lib/gl_anytree_list2.h | 940 | ||||
| -rw-r--r-- | mcastseed/lib/gl_list.c | 3 | ||||
| -rw-r--r-- | mcastseed/lib/gl_list.h | 841 | ||||
| -rw-r--r-- | mcastseed/lib/gl_rbtree_list.c | 102 | ||||
| -rw-r--r-- | mcastseed/lib/gl_rbtree_list.h | 34 | ||||
| -rw-r--r-- | mcastseed/lib/stdbool.in.h | 132 |
10 files changed, 0 insertions, 3290 deletions
diff --git a/mcastseed/lib/Makefile.am b/mcastseed/lib/Makefile.am deleted file mode 100644 index 38faabe..0000000 --- a/mcastseed/lib/Makefile.am +++ /dev/null @@ -1,93 +0,0 @@ -## 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/mcastseed/lib/gl_anyrbtree_list1.h b/mcastseed/lib/gl_anyrbtree_list1.h deleted file mode 100644 index 0ae0715..0000000 --- a/mcastseed/lib/gl_anyrbtree_list1.h +++ /dev/null @@ -1,76 +0,0 @@ -/* Sequential list data type implemented by a binary tree. - Copyright (C) 2006, 2009-2016 Free Software Foundation, Inc. - Written by Bruno Haible <bruno@clisp.org>, 2006. - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 3 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. */ - -/* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */ - -/* A red-black tree is a binary tree where every node is colored black or - red such that - 1. The root is black. - 2. No red node has a red parent. - Or equivalently: No red node has a red child. - 3. All paths from the root down to any NULL endpoint contain the same - number of black nodes. - Let's call this the "black-height" bh of the tree. It follows that every - such path contains exactly bh black and between 0 and bh red nodes. (The - extreme cases are a path containing only black nodes, and a path colored - alternately black-red-black-red-...-black-red.) The height of the tree - therefore is >= bh, <= 2*bh. - */ - -/* -------------------------- gl_list_t Data Type -------------------------- */ - -/* Color of a node. */ -typedef enum color { BLACK, RED } color_t; - -/* Concrete list node implementation, valid for this file only. */ -struct gl_list_node_impl -{ -#if WITH_HASHTABLE - struct gl_hash_entry h; /* hash table entry fields; must be first */ -#endif - struct gl_list_node_impl *left; /* left branch, or NULL */ - struct gl_list_node_impl *right; /* right branch, or NULL */ - /* Parent pointer, or NULL. The parent pointer is not needed for most - operations. It is needed so that a gl_list_node_t can be returned - without memory allocation, on which the functions gl_list_remove_node, - gl_list_add_before, gl_list_add_after can be implemented. */ - struct gl_list_node_impl *parent; - color_t color; /* node's color */ - size_t branch_size; /* number of nodes in this branch, - = branchsize(left)+branchsize(right)+1 */ - const void *value; -}; - -/* Concrete gl_list_impl type, valid for this file only. */ -struct gl_list_impl -{ - struct gl_list_impl_base base; -#if WITH_HASHTABLE - /* A hash table: managed as an array of collision lists. */ - struct gl_hash_entry **table; - size_t table_size; -#endif - struct gl_list_node_impl *root; /* root node or NULL */ -}; - -/* A red-black tree of height h has a black-height bh >= ceil(h/2) and - therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree - of height h >= 117 would have at least 2^59 - 1 elements, and because even - on 64-bit machines, - sizeof (gl_list_node_impl) * (2^59 - 1) > 2^64 - this would exceed the address space of the machine. */ -#define MAXHEIGHT 116 diff --git a/mcastseed/lib/gl_anyrbtree_list2.h b/mcastseed/lib/gl_anyrbtree_list2.h deleted file mode 100644 index a0e2e43..0000000 --- a/mcastseed/lib/gl_anyrbtree_list2.h +++ /dev/null @@ -1,1028 +0,0 @@ -/* 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/mcastseed/lib/gl_anytree_list1.h b/mcastseed/lib/gl_anytree_list1.h deleted file mode 100644 index 675f107..0000000 --- a/mcastseed/lib/gl_anytree_list1.h +++ /dev/null @@ -1,41 +0,0 @@ -/* Sequential list data type implemented by a binary tree. - Copyright (C) 2006, 2009-2016 Free Software Foundation, Inc. - Written by Bruno Haible <bruno@clisp.org>, 2006. - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 3 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. */ - -/* Common code of gl_avltree_list.c, gl_rbtree_list.c, - gl_avltreehash_list.c, gl_rbtreehash_list.c. */ - -/* An item on the stack used for iterating across the elements. */ -typedef struct -{ - gl_list_node_t node; - size_t rightp; -} iterstack_item_t; - -/* A stack used for iterating across the elements. */ -typedef iterstack_item_t iterstack_t[MAXHEIGHT]; - -/* Free a non-empty subtree recursively. - This function is recursive and therefore not very fast. */ -static void -free_subtree (gl_list_node_t node) -{ - if (node->left != NULL) - free_subtree (node->left); - if (node->right != NULL) - free_subtree (node->right); - free (node); -} diff --git a/mcastseed/lib/gl_anytree_list2.h b/mcastseed/lib/gl_anytree_list2.h deleted file mode 100644 index 7e6fe45..0000000 --- a/mcastseed/lib/gl_anytree_list2.h +++ /dev/null @@ -1,940 +0,0 @@ -/* Sequential list data type implemented by a binary tree. - Copyright (C) 2006-2016 Free Software Foundation, Inc. - Written by Bruno Haible <bruno@clisp.org>, 2006. - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 3 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. */ - -/* Common code of gl_avltree_list.c, gl_rbtree_list.c, - gl_avltreehash_list.c, gl_rbtreehash_list.c. */ - -static gl_list_t -gl_tree_nx_create_empty (gl_list_implementation_t implementation, - gl_listelement_equals_fn equals_fn, - gl_listelement_hashcode_fn hashcode_fn, - gl_listelement_dispose_fn dispose_fn, - bool allow_duplicates) -{ - struct gl_list_impl *list = (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); - - if (list == NULL) - return NULL; - - list->base.vtable = implementation; - list->base.equals_fn = equals_fn; - list->base.hashcode_fn = hashcode_fn; - list->base.dispose_fn = dispose_fn; - list->base.allow_duplicates = allow_duplicates; -#if WITH_HASHTABLE - list->table_size = 11; - list->table = - (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t)); - if (list->table == NULL) - goto fail; -#endif - list->root = NULL; - - return list; - -#if WITH_HASHTABLE - fail: - free (list); - return NULL; -#endif -} - -static size_t -gl_tree_size (gl_list_t list) -{ - return (list->root != NULL ? list->root->branch_size : 0); -} - -static const void * -gl_tree_node_value (gl_list_t list, gl_list_node_t node) -{ - return node->value; -} - -static int -gl_tree_node_nx_set_value (gl_list_t list, gl_list_node_t node, const void *elt) -{ -#if WITH_HASHTABLE - if (elt != node->value) - { - size_t new_hashcode = - (list->base.hashcode_fn != NULL - ? list->base.hashcode_fn (elt) - : (size_t)(uintptr_t) elt); - - if (new_hashcode != node->h.hashcode) - { - remove_from_bucket (list, node); - node->value = elt; - node->h.hashcode = new_hashcode; - if (add_to_bucket (list, node) < 0) - { - /* Out of memory. We removed node from a bucket but cannot add - it to another bucket. In order to avoid inconsistencies, we - must remove node entirely from the list. */ - gl_tree_remove_node_from_tree (list, node); - free (node); - return -1; - } - } - else - node->value = elt; - } -#else - node->value = elt; -#endif - return 0; -} - -static gl_list_node_t _GL_ATTRIBUTE_PURE -gl_tree_next_node (gl_list_t list, gl_list_node_t node) -{ - if (node->right != NULL) - { - node = node->right; - while (node->left != NULL) - node = node->left; - } - else - { - while (node->parent != NULL && node->parent->right == node) - node = node->parent; - node = node->parent; - } - return node; -} - -static gl_list_node_t _GL_ATTRIBUTE_PURE -gl_tree_previous_node (gl_list_t list, gl_list_node_t node) -{ - if (node->left != NULL) - { - node = node->left; - while (node->right != NULL) - node = node->right; - } - else - { - while (node->parent != NULL && node->parent->left == node) - node = node->parent; - node = node->parent; - } - return node; -} - -/* Return the node at the given position < gl_tree_size (list). */ -static gl_list_node_t _GL_ATTRIBUTE_PURE -node_at (gl_list_node_t root, size_t position) -{ - /* Here we know that root != NULL. */ - gl_list_node_t node = root; - - for (;;) - { - if (node->left != NULL) - { - if (position < node->left->branch_size) - { - node = node->left; - continue; - } - position -= node->left->branch_size; - } - if (position == 0) - break; - position--; - node = node->right; - } - return node; -} - -static const void * _GL_ATTRIBUTE_PURE -gl_tree_get_at (gl_list_t list, size_t position) -{ - gl_list_node_t node = list->root; - - if (!(node != NULL && position < node->branch_size)) - /* Invalid argument. */ - abort (); - node = node_at (node, position); - return node->value; -} - -static gl_list_node_t -gl_tree_nx_set_at (gl_list_t list, size_t position, const void *elt) -{ - gl_list_node_t node = list->root; - - if (!(node != NULL && position < node->branch_size)) - /* Invalid argument. */ - abort (); - node = node_at (node, position); -#if WITH_HASHTABLE - if (elt != node->value) - { - size_t new_hashcode = - (list->base.hashcode_fn != NULL - ? list->base.hashcode_fn (elt) - : (size_t)(uintptr_t) elt); - - if (new_hashcode != node->h.hashcode) - { - remove_from_bucket (list, node); - node->value = elt; - node->h.hashcode = new_hashcode; - if (add_to_bucket (list, node) < 0) - { - /* Out of memory. We removed node from a bucket but cannot add - it to another bucket. In order to avoid inconsistencies, we - must remove node entirely from the list. */ - gl_tree_remove_node_from_tree (list, node); - free (node); - return NULL; - } - } - else - node->value = elt; - } -#else - node->value = elt; -#endif - return node; -} - -#if !WITH_HASHTABLE - -static gl_list_node_t -gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index, - const void *elt) -{ - if (!(start_index <= end_index - && end_index <= (list->root != NULL ? list->root->branch_size : 0))) - /* Invalid arguments. */ - abort (); - { - gl_listelement_equals_fn equals = list->base.equals_fn; - /* Iterate across all elements. */ - gl_list_node_t node = list->root; - iterstack_t stack; - iterstack_item_t *stack_ptr = &stack[0]; - size_t index = 0; - - if (start_index == 0) - { - /* Consider all elements. */ - for (;;) - { - /* Descend on left branch. */ - for (;;) - { - if (node == NULL) - break; - stack_ptr->node = node; - stack_ptr->rightp = 0; - node = node->left; - stack_ptr++; - } - /* Climb up again. */ - for (;;) - { - if (stack_ptr == &stack[0]) - return NULL; - stack_ptr--; - if (!stack_ptr->rightp) - break; - } - node = stack_ptr->node; - /* Test against current element. */ - if (equals != NULL ? equals (elt, node->value) : elt == node->value) - return node; - index++; - if (index >= end_index) - return NULL; - /* Descend on right branch. */ - stack_ptr->rightp = 1; - node = node->right; - stack_ptr++; - } - } - else - { - /* Consider only elements at indices >= start_index. - In this case, rightp contains the difference between the start_index - for the parent node and the one for the child node (0 when the child - node is the parent's left child, > 0 when the child is the parent's - right child). */ - for (;;) - { - /* Descend on left branch. */ - for (;;) - { - if (node == NULL) - break; - if (node->branch_size <= start_index) - break; - stack_ptr->node = node; - stack_ptr->rightp = 0; - node = node->left; - stack_ptr++; - } - /* Climb up again. */ - for (;;) - { - if (stack_ptr == &stack[0]) - return NULL; - stack_ptr--; - if (!stack_ptr->rightp) - break; - start_index += stack_ptr->rightp; - } - node = stack_ptr->node; - { - size_t left_branch_size1 = - (node->left != NULL ? node->left->branch_size : 0) + 1; - if (start_index < left_branch_size1) - { - /* Test against current element. */ - if (equals != NULL ? equals (elt, node->value) : elt == node->value) - return node; - /* Now that we have considered all indices < left_branch_size1, - we can increment start_index. */ - start_index = left_branch_size1; - } - index++; - if (index >= end_index) - return NULL; - /* Descend on right branch. */ - start_index -= left_branch_size1; - stack_ptr->rightp = left_branch_size1; - } - node = node->right; - stack_ptr++; - } - } - } -} - -static size_t -gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, - const void *elt) -{ - if (!(start_index <= end_index - && end_index <= (list->root != NULL ? list->root->branch_size : 0))) - /* Invalid arguments. */ - abort (); - { - gl_listelement_equals_fn equals = list->base.equals_fn; - /* Iterate across all elements. */ - gl_list_node_t node = list->root; - iterstack_t stack; - iterstack_item_t *stack_ptr = &stack[0]; - size_t index = 0; - - if (start_index == 0) - { - /* Consider all elements. */ - for (;;) - { - /* Descend on left branch. */ - for (;;) - { - if (node == NULL) - break; - stack_ptr->node = node; - stack_ptr->rightp = 0; - node = node->left; - stack_ptr++; - } - /* Climb up again. */ - for (;;) - { - if (stack_ptr == &stack[0]) - return (size_t)(-1); - stack_ptr--; - if (!stack_ptr->rightp) - break; - } - node = stack_ptr->node; - /* Test against current element. */ - if (equals != NULL ? equals (elt, node->value) : elt == node->value) - return index; - index++; - if (index >= end_index) - return (size_t)(-1); - /* Descend on right branch. */ - stack_ptr->rightp = 1; - node = node->right; - stack_ptr++; - } - } - else - { - /* Consider only elements at indices >= start_index. - In this case, rightp contains the difference between the start_index - for the parent node and the one for the child node (0 when the child - node is the parent's left child, > 0 when the child is the parent's - right child). */ - for (;;) - { - /* Descend on left branch. */ - for (;;) - { - if (node == NULL) - break; - if (node->branch_size <= start_index) - break; - stack_ptr->node = node; - stack_ptr->rightp = 0; - node = node->left; - stack_ptr++; - } - /* Climb up again. */ - for (;;) - { - if (stack_ptr == &stack[0]) - return (size_t)(-1); - stack_ptr--; - if (!stack_ptr->rightp) - break; - start_index += stack_ptr->rightp; - } - node = stack_ptr->node; - { - size_t left_branch_size1 = - (node->left != NULL ? node->left->branch_size : 0) + 1; - if (start_index < left_branch_size1) - { - /* Test against current element. */ - if (equals != NULL ? equals (elt, node->value) : elt == node->value) - return index; - /* Now that we have considered all indices < left_branch_size1, - we can increment start_index. */ - start_index = left_branch_size1; - } - index++; - if (index >= end_index) - return (size_t)(-1); - /* Descend on right branch. */ - start_index -= left_branch_size1; - stack_ptr->rightp = left_branch_size1; - } - node = node->right; - stack_ptr++; - } - } - } -} - -#endif - -static gl_list_node_t -gl_tree_nx_add_at (gl_list_t list, size_t position, const void *elt) -{ - size_t count = (list->root != NULL ? list->root->branch_size : 0); - - if (!(position <= count)) - /* Invalid argument. */ - abort (); - if (position == count) - return gl_tree_nx_add_last (list, elt); - else - return gl_tree_nx_add_before (list, node_at (list->root, position), elt); -} - -static bool -gl_tree_remove_node (gl_list_t list, gl_list_node_t node) -{ -#if WITH_HASHTABLE - /* Remove node from the hash table. - Note that this is only possible _before_ the node is removed from the - tree structure, because remove_from_bucket() uses node_position(). */ - remove_from_bucket (list, node); -#endif - - gl_tree_remove_node_from_tree (list, node); - - if (list->base.dispose_fn != NULL) - list->base.dispose_fn (node->value); - free (node); - return true; -} - -static bool -gl_tree_remove_at (gl_list_t list, size_t position) -{ - gl_list_node_t node = list->root; - - if (!(node != NULL && position < node->branch_size)) - /* Invalid argument. */ - abort (); - node = node_at (node, position); - return gl_tree_remove_node (list, node); -} - -static bool -gl_tree_remove (gl_list_t list, const void *elt) -{ - if (list->root != NULL) - { - gl_list_node_t node = - gl_tree_search_from_to (list, 0, list->root->branch_size, elt); - - if (node != NULL) - return gl_tree_remove_node (list, node); - } - return false; -} - -#if !WITH_HASHTABLE - -static void -gl_tree_list_free (gl_list_t list) -{ - /* Iterate across all elements in post-order. */ - gl_list_node_t node = list->root; - iterstack_t stack; - iterstack_item_t *stack_ptr = &stack[0]; - - for (;;) - { - /* Descend on left branch. */ - for (;;) - { - if (node == NULL) - break; - stack_ptr->node = node; - stack_ptr->rightp = false; - node = node->left; - stack_ptr++; - } - /* Climb up again. */ - for (;;) - { - if (stack_ptr == &stack[0]) - goto done_iterate; - stack_ptr--; - node = stack_ptr->node; - if (!stack_ptr->rightp) - break; - /* Free the current node. */ - if (list->base.dispose_fn != NULL) - list->base.dispose_fn (node->value); - free (node); - } - /* Descend on right branch. */ - stack_ptr->rightp = true; - node = node->right; - stack_ptr++; - } - done_iterate: - free (list); -} - -#endif - -/* --------------------- gl_list_iterator_t Data Type --------------------- */ - -static gl_list_iterator_t -gl_tree_iterator (gl_list_t list) -{ - gl_list_iterator_t result; - gl_list_node_t node; - - result.vtable = list->base.vtable; - result.list = list; - /* Start node is the leftmost node. */ - node = list->root; - if (node != NULL) - while (node->left != NULL) - node = node->left; - result.p = node; - /* End point is past the rightmost node. */ - result.q = NULL; -#if defined GCC_LINT || defined lint - result.i = 0; - result.j = 0; - result.count = 0; -#endif - - return result; -} - -static gl_list_iterator_t -gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index) -{ - size_t count = (list->root != NULL ? list->root->branch_size : 0); - gl_list_iterator_t result; - - if (!(start_index <= end_index && end_index <= count)) - /* Invalid arguments. */ - abort (); - result.vtable = list->base.vtable; - result.list = list; - /* Start node is the node at position start_index. */ - result.p = (start_index < count ? node_at (list->root, start_index) : NULL); - /* End point is the node at position end_index. */ - result.q = (end_index < count ? node_at (list->root, end_index) : NULL); -#if defined GCC_LINT || defined lint - result.i = 0; - result.j = 0; - result.count = 0; -#endif - - return result; -} - -static bool -gl_tree_iterator_next (gl_list_iterator_t *iterator, - const void **eltp, gl_list_node_t *nodep) -{ - if (iterator->p != iterator->q) - { - gl_list_node_t node = (gl_list_node_t) iterator->p; - *eltp = node->value; - if (nodep != NULL) - *nodep = node; - /* Advance to the next node. */ - if (node->right != NULL) - { - node = node->right; - while (node->left != NULL) - node = node->left; - } - else - { - while (node->parent != NULL && node->parent->right == node) - node = node->parent; - node = node->parent; - } - iterator->p = node; - return true; - } - else - return false; -} - -static void -gl_tree_iterator_free (gl_list_iterator_t *iterator) -{ -} - -/* ---------------------- Sorted gl_list_t Data Type ---------------------- */ - -static gl_list_node_t -gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, - const void *elt) -{ - gl_list_node_t node; - - for (node = list->root; node != NULL; ) - { - int cmp = compar (node->value, elt); - - if (cmp < 0) - node = node->right; - else if (cmp > 0) - node = node->left; - else /* cmp == 0 */ - { - /* We have an element equal to ELT. But we need the leftmost such - element. */ - gl_list_node_t found = node; - node = node->left; - for (; node != NULL; ) - { - int cmp2 = compar (node->value, elt); - - if (cmp2 < 0) - node = node->right; - else if (cmp2 > 0) - /* The list was not sorted. */ - abort (); - else /* cmp2 == 0 */ - { - found = node; - node = node->left; - } - } - return found; - } - } - return NULL; -} - -static gl_list_node_t -gl_tree_sortedlist_search_from_to (gl_list_t list, - gl_listelement_compar_fn compar, - size_t low, size_t high, - const void *elt) -{ - gl_list_node_t node; - - if (!(low <= high - && high <= (list->root != NULL ? list->root->branch_size : 0))) - /* Invalid arguments. */ - abort (); - - for (node = list->root; node != NULL; ) - { - size_t left_branch_size = - (node->left != NULL ? node->left->branch_size : 0); - - if (low > left_branch_size) - { - low -= left_branch_size + 1; - high -= left_branch_size + 1; - node = node->right; - } - else if (high <= left_branch_size) - node = node->left; - else - { - /* Here low <= left_branch_size < high. */ - int cmp = compar (node->value, elt); - - if (cmp < 0) - { - low = 0; - high -= left_branch_size + 1; - node = node->right; - } - else if (cmp > 0) - node = node->left; - else /* cmp == 0 */ - { - /* We have an element equal to ELT. But we need the leftmost - such element. */ - gl_list_node_t found = node; - node = node->left; - for (; node != NULL; ) - { - size_t left_branch_size2 = - (node->left != NULL ? node->left->branch_size : 0); - - if (low > left_branch_size2) - { - low -= left_branch_size2 + 1; - node = node->right; - } - else - { - /* Here low <= left_branch_size2. */ - int cmp2 = compar (node->value, elt); - - if (cmp2 < 0) - { - low = 0; - node = node->right; - } - else if (cmp2 > 0) - /* The list was not sorted. */ - abort (); - else /* cmp2 == 0 */ - { - found = node; - node = node->left; - } - } - } - return found; - } - } - } - return NULL; -} - -static size_t -gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, - const void *elt) -{ - gl_list_node_t node; - size_t position; - - for (node = list->root, position = 0; node != NULL; ) - { - int cmp = compar (node->value, elt); - - if (cmp < 0) - { - if (node->left != NULL) - position += node->left->branch_size; - position++; - node = node->right; - } - else if (cmp > 0) - node = node->left; - else /* cmp == 0 */ - { - /* We have an element equal to ELT. But we need the leftmost such - element. */ - size_t found_position = - position + (node->left != NULL ? node->left->branch_size : 0); - node = node->left; - for (; node != NULL; ) - { - int cmp2 = compar (node->value, elt); - - if (cmp2 < 0) - { - if (node->left != NULL) - position += node->left->branch_size; - position++; - node = node->right; - } - else if (cmp2 > 0) - /* The list was not sorted. */ - abort (); - else /* cmp2 == 0 */ - { - found_position = - position - + (node->left != NULL ? node->left->branch_size : 0); - node = node->left; - } - } - return found_position; - } - } - return (size_t)(-1); -} - -static size_t -gl_tree_sortedlist_indexof_from_to (gl_list_t list, - gl_listelement_compar_fn compar, - size_t low, size_t high, - const void *elt) -{ - gl_list_node_t node; - size_t position; - - if (!(low <= high - && high <= (list->root != NULL ? list->root->branch_size : 0))) - /* Invalid arguments. */ - abort (); - - for (node = list->root, position = 0; node != NULL; ) - { - size_t left_branch_size = - (node->left != NULL ? node->left->branch_size : 0); - - if (low > left_branch_size) - { - low -= left_branch_size + 1; - high -= left_branch_size + 1; - position += left_branch_size + 1; - node = node->right; - } - else if (high <= left_branch_size) - node = node->left; - else - { - /* Here low <= left_branch_size < high. */ - int cmp = compar (node->value, elt); - - if (cmp < 0) - { - low = 0; - high -= left_branch_size + 1; - position += left_branch_size + 1; - node = node->right; - } - else if (cmp > 0) - node = node->left; - else /* cmp == 0 */ - { - /* We have an element equal to ELT. But we need the leftmost - such element. */ - size_t found_position = - position + (node->left != NULL ? node->left->branch_size : 0); - node = node->left; - for (; node != NULL; ) - { - size_t left_branch_size2 = - (node->left != NULL ? node->left->branch_size : 0); - - if (low > left_branch_size2) - { - low -= left_branch_size2 + 1; - node = node->right; - } - else - { - /* Here low <= left_branch_size2. */ - int cmp2 = compar (node->value, elt); - - if (cmp2 < 0) - { - position += left_branch_size2 + 1; - node = node->right; - } - else if (cmp2 > 0) - /* The list was not sorted. */ - abort (); - else /* cmp2 == 0 */ - { - found_position = position + left_branch_size2; - node = node->left; - } - } - } - return found_position; - } - } - } - return (size_t)(-1); -} - -static gl_list_node_t -gl_tree_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, - const void *elt) -{ - gl_list_node_t node = list->root; - - if (node == NULL) - return gl_tree_nx_add_first (list, elt); - - for (;;) - { - int cmp = compar (node->value, elt); - - if (cmp < 0) - { - if (node->right == NULL) - return gl_tree_nx_add_after (list, node, elt); - node = node->right; - } - else if (cmp > 0) - { - if (node->left == NULL) - return gl_tree_nx_add_before (list, node, elt); - node = node->left; - } - else /* cmp == 0 */ - return gl_tree_nx_add_before (list, node, elt); - } -} - -static bool -gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, - const void *elt) -{ - gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt); - if (node != NULL) - return gl_tree_remove_node (list, node); - else - return false; -} diff --git a/mcastseed/lib/gl_list.c b/mcastseed/lib/gl_list.c deleted file mode 100644 index 8793298..0000000 --- a/mcastseed/lib/gl_list.c +++ /dev/null @@ -1,3 +0,0 @@ -#include <config.h> -#define GL_LIST_INLINE _GL_EXTERN_INLINE -#include "gl_list.h" diff --git a/mcastseed/lib/gl_list.h b/mcastseed/lib/gl_list.h deleted file mode 100644 index c9d05b0..0000000 --- a/mcastseed/lib/gl_list.h +++ /dev/null @@ -1,841 +0,0 @@ -/* Abstract sequential list data type. -*- coding: utf-8 -*- - Copyright (C) 2006-2016 Free Software Foundation, Inc. - Written by Bruno Haible <bruno@clisp.org>, 2006. - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 3 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. */ - -#ifndef _GL_LIST_H -#define _GL_LIST_H - -#include <stdbool.h> -#include <stddef.h> - -#ifndef _GL_INLINE_HEADER_BEGIN - #error "Please include config.h first." -#endif -_GL_INLINE_HEADER_BEGIN -#ifndef GL_LIST_INLINE -# define GL_LIST_INLINE _GL_INLINE -#endif - -#ifdef __cplusplus -extern "C" { -#endif - - -/* gl_list is an abstract list data type. It can contain any number of - objects ('void *' or 'const void *' pointers) in any given order. - Duplicates are allowed, but can optionally be forbidden. - - There are several implementations of this list datatype, optimized for - different operations or for memory. You can start using the simplest list - implementation, GL_ARRAY_LIST, and switch to a different implementation - later, when you realize which operations are performed the most frequently. - The API of the different implementations is exactly the same; when - switching to a different implementation, you only have to change the - gl_list_create call. - - The implementations are: - GL_ARRAY_LIST a growable array - GL_CARRAY_LIST a growable circular array - GL_LINKED_LIST a linked list - GL_AVLTREE_LIST a binary tree (AVL tree) - GL_RBTREE_LIST a binary tree (red-black tree) - GL_LINKEDHASH_LIST a hash table with a linked list - GL_AVLTREEHASH_LIST a hash table with a binary tree (AVL tree) - GL_RBTREEHASH_LIST a hash table with a binary tree (red-black tree) - - The memory consumption is asymptotically the same: O(1) for every object - in the list. When looking more closely at the average memory consumed - for an object, GL_ARRAY_LIST is the most compact representation, and - GL_LINKEDHASH_LIST and GL_TREEHASH_LIST need more memory. - - The guaranteed average performance of the operations is, for a list of - n elements: - - Operation ARRAY LINKED TREE LINKEDHASH TREEHASH - CARRAY with|without with|without - duplicates duplicates - - gl_list_size O(1) O(1) O(1) O(1) O(1) - gl_list_node_value O(1) O(1) O(1) O(1) O(1) - gl_list_node_set_value O(1) O(1) O(1) O(1) O((log n)²)/O(1) - gl_list_next_node O(1) O(1) O(log n) O(1) O(log n) - gl_list_previous_node O(1) O(1) O(log n) O(1) O(log n) - gl_list_get_at O(1) O(n) O(log n) O(n) O(log n) - gl_list_set_at O(1) O(n) O(log n) O(n) O((log n)²)/O(log n) - gl_list_search O(n) O(n) O(n) O(n)/O(1) O(log n)/O(1) - gl_list_search_from O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n) - gl_list_search_from_to O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n) - gl_list_indexof O(n) O(n) O(n) O(n) O(log n) - gl_list_indexof_from O(n) O(n) O(n) O(n) O((log n)²)/O(log n) - gl_list_indexof_from_to O(n) O(n) O(n) O(n) O((log n)²)/O(log n) - gl_list_add_first O(n)/O(1) O(1) O(log n) O(1) O((log n)²)/O(log n) - gl_list_add_last O(1) O(1) O(log n) O(1) O((log n)²)/O(log n) - gl_list_add_before O(n) O(1) O(log n) O(1) O((log n)²)/O(log n) - gl_list_add_after O(n) O(1) O(log n) O(1) O((log n)²)/O(log n) - gl_list_add_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) - gl_list_remove_node O(n) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n) - gl_list_remove_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) - gl_list_remove O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n) - gl_list_iterator O(1) O(1) O(log n) O(1) O(log n) - gl_list_iterator_from_to O(1) O(n) O(log n) O(n) O(log n) - gl_list_iterator_next O(1) O(1) O(log n) O(1) O(log n) - gl_sortedlist_search O(log n) O(n) O(log n) O(n) O(log n) - gl_sortedlist_search_from O(log n) O(n) O(log n) O(n) O(log n) - gl_sortedlist_indexof O(log n) O(n) O(log n) O(n) O(log n) - gl_sortedlist_indexof_fro O(log n) O(n) O(log n) O(n) O(log n) - gl_sortedlist_add O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) - gl_sortedlist_remove O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) - */ - -/* -------------------------- gl_list_t Data Type -------------------------- */ - -/* Type of function used to compare two elements. - NULL denotes pointer comparison. */ -typedef bool (*gl_listelement_equals_fn) (const void *elt1, const void *elt2); - -/* Type of function used to compute a hash code. - NULL denotes a function that depends only on the pointer itself. */ -typedef size_t (*gl_listelement_hashcode_fn) (const void *elt); - -/* Type of function used to dispose an element once it's removed from a list. - NULL denotes a no-op. */ -typedef void (*gl_listelement_dispose_fn) (const void *elt); - -struct gl_list_impl; -/* Type representing an entire list. */ -typedef struct gl_list_impl * gl_list_t; - -struct gl_list_node_impl; -/* Type representing the position of an element in the list, in a way that - is more adapted to the list implementation than a plain index. - Note: It is invalidated by insertions and removals! */ -typedef struct gl_list_node_impl * gl_list_node_t; - -struct gl_list_implementation; -/* Type representing a list datatype implementation. */ -typedef const struct gl_list_implementation * gl_list_implementation_t; - -#if 0 /* Unless otherwise specified, these are defined inline below. */ - -/* Create an empty list. - IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST, - GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST, - GL_RBTREEHASH_LIST. - EQUALS_FN is an element comparison function or NULL. - HASHCODE_FN is an element hash code function or NULL. - DISPOSE_FN is an element disposal function or NULL. - ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in - the list. The implementation may verify this at runtime. */ -/* declared in gl_xlist.h */ -extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation, - gl_listelement_equals_fn equals_fn, - gl_listelement_hashcode_fn hashcode_fn, - gl_listelement_dispose_fn dispose_fn, - bool allow_duplicates); -/* Likewise. Return NULL upon out-of-memory. */ -extern gl_list_t gl_list_nx_create_empty (gl_list_implementation_t implementation, - gl_listelement_equals_fn equals_fn, - gl_listelement_hashcode_fn hashcode_fn, - gl_listelement_dispose_fn dispose_fn, - bool allow_duplicates); - -/* Create a list with given contents. - IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST, - GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST, - GL_RBTREEHASH_LIST. - EQUALS_FN is an element comparison function or NULL. - HASHCODE_FN is an element hash code function or NULL. - DISPOSE_FN is an element disposal function or NULL. - ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in - the list. The implementation may verify this at runtime. - COUNT is the number of initial elements. - CONTENTS[0..COUNT-1] is the initial contents. */ -/* declared in gl_xlist.h */ -extern gl_list_t gl_list_create (gl_list_implementation_t implementation, - gl_listelement_equals_fn equals_fn, - gl_listelement_hashcode_fn hashcode_fn, - gl_listelement_dispose_fn dispose_fn, - bool allow_duplicates, - size_t count, const void **contents); -/* Likewise. Return NULL upon out-of-memory. */ -extern gl_list_t gl_list_nx_create (gl_list_implementation_t implementation, - gl_listelement_equals_fn equals_fn, - gl_listelement_hashcode_fn hashcode_fn, - gl_listelement_dispose_fn dispose_fn, - bool allow_duplicates, - size_t count, const void **contents); - -/* Return the current number of elements in a list. */ -extern size_t gl_list_size (gl_list_t list); - -/* Return the element value represented by a list node. */ -extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node); - -/* Replace the element value represented by a list node. */ -/* declared in gl_xlist.h */ -extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node, - const void *elt); -/* Likewise. Return 0 upon success, -1 upon out-of-memory. */ -extern int gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node, - const void *elt) -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif - ; - -/* Return the node immediately after the given node in the list, or NULL - if the given node is the last (rightmost) one in the list. */ -extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node); - -/* Return the node immediately before the given node in the list, or NULL - if the given node is the first (leftmost) one in the list. */ -extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node); - -/* Return the element at a given position in the list. - POSITION must be >= 0 and < gl_list_size (list). */ -extern const void * gl_list_get_at (gl_list_t list, size_t position); - -/* Replace the element at a given position in the list. - POSITION must be >= 0 and < gl_list_size (list). - Return its node. */ -/* declared in gl_xlist.h */ -extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position, - const void *elt); -/* Likewise. Return NULL upon out-of-memory. */ -extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position, - const void *elt) -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif - ; - -/* Search whether an element is already in the list. - Return its node if found, or NULL if not present in the list. */ -extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt); - -/* Search whether an element is already in the list, - at a position >= START_INDEX. - Return its node if found, or NULL if not present in the list. */ -extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index, - const void *elt); - -/* Search whether an element is already in the list, - at a position >= START_INDEX and < END_INDEX. - Return its node if found, or NULL if not present in the list. */ -extern gl_list_node_t gl_list_search_from_to (gl_list_t list, - size_t start_index, - size_t end_index, - const void *elt); - -/* Search whether an element is already in the list. - Return its position if found, or (size_t)(-1) if not present in the list. */ -extern size_t gl_list_indexof (gl_list_t list, const void *elt); - -/* Search whether an element is already in the list, - at a position >= START_INDEX. - Return its position if found, or (size_t)(-1) if not present in the list. */ -extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index, - const void *elt); - -/* Search whether an element is already in the list, - at a position >= START_INDEX and < END_INDEX. - Return its position if found, or (size_t)(-1) if not present in the list. */ -extern size_t gl_list_indexof_from_to (gl_list_t list, - size_t start_index, size_t end_index, - const void *elt); - -/* Add an element as the first element of the list. - Return its node. */ -/* declared in gl_xlist.h */ -extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt); -/* Likewise. Return NULL upon out-of-memory. */ -extern gl_list_node_t gl_list_nx_add_first (gl_list_t list, const void *elt) -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif - ; - -/* Add an element as the last element of the list. - Return its node. */ -/* declared in gl_xlist.h */ -extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt); -/* Likewise. Return NULL upon out-of-memory. */ -extern gl_list_node_t gl_list_nx_add_last (gl_list_t list, const void *elt) -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif - ; - -/* Add an element before a given element node of the list. - Return its node. */ -/* declared in gl_xlist.h */ -extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node, - const void *elt); -/* Likewise. Return NULL upon out-of-memory. */ -extern gl_list_node_t gl_list_nx_add_before (gl_list_t list, - gl_list_node_t node, - const void *elt) -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif - ; - -/* Add an element after a given element node of the list. - Return its node. */ -/* declared in gl_xlist.h */ -extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node, - const void *elt); -/* Likewise. Return NULL upon out-of-memory. */ -extern gl_list_node_t gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, - const void *elt) -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif - ; - -/* Add an element at a given position in the list. - POSITION must be >= 0 and <= gl_list_size (list). */ -/* declared in gl_xlist.h */ -extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position, - const void *elt); -/* Likewise. Return NULL upon out-of-memory. */ -extern gl_list_node_t gl_list_nx_add_at (gl_list_t list, size_t position, - const void *elt) -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif - ; - -/* Remove an element from the list. - Return true. */ -extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node); - -/* Remove an element at a given position from the list. - POSITION must be >= 0 and < gl_list_size (list). - Return true. */ -extern bool gl_list_remove_at (gl_list_t list, size_t position); - -/* Search and remove an element from the list. - Return true if it was found and removed. */ -extern bool gl_list_remove (gl_list_t list, const void *elt); - -/* Free an entire list. - (But this call does not free the elements of the list.) */ -extern void gl_list_free (gl_list_t list); - -#endif /* End of inline and gl_xlist.h-defined functions. */ - -/* --------------------- gl_list_iterator_t Data Type --------------------- */ - -/* Functions for iterating through a list. */ - -/* Type of an iterator that traverses a list. - This is a fixed-size struct, so that creation of an iterator doesn't need - memory allocation on the heap. */ -typedef struct -{ - /* For fast dispatch of gl_list_iterator_next. */ - const struct gl_list_implementation *vtable; - /* For detecting whether the last returned element was removed. */ - gl_list_t list; - size_t count; - /* Other, implementation-private fields. */ - void *p; void *q; - size_t i; size_t j; -} gl_list_iterator_t; - -#if 0 /* These are defined inline below. */ - -/* Create an iterator traversing a list. - The list contents must not be modified while the iterator is in use, - except for replacing or removing the last returned element. */ -extern gl_list_iterator_t gl_list_iterator (gl_list_t list); - -/* Create an iterator traversing the element with indices i, - start_index <= i < end_index, of a list. - The list contents must not be modified while the iterator is in use, - except for replacing or removing the last returned element. */ -extern gl_list_iterator_t gl_list_iterator_from_to (gl_list_t list, - size_t start_index, - size_t end_index); - -/* If there is a next element, store the next element in *ELTP, store its - node in *NODEP if NODEP is non-NULL, advance the iterator and return true. - Otherwise, return false. */ -extern bool gl_list_iterator_next (gl_list_iterator_t *iterator, - const void **eltp, gl_list_node_t *nodep); - -/* Free an iterator. */ -extern void gl_list_iterator_free (gl_list_iterator_t *iterator); - -#endif /* End of inline functions. */ - -/* ---------------------- Sorted gl_list_t Data Type ---------------------- */ - -/* The following functions are for lists without duplicates where the - order is given by a sort criterion. */ - -/* Type of function used to compare two elements. Same as for qsort(). - NULL denotes pointer comparison. */ -typedef int (*gl_listelement_compar_fn) (const void *elt1, const void *elt2); - -#if 0 /* Unless otherwise specified, these are defined inline below. */ - -/* Search whether an element is already in the list. - The list is assumed to be sorted with COMPAR. - Return its node if found, or NULL if not present in the list. - If the list contains several copies of ELT, the node of the leftmost one is - returned. */ -extern gl_list_node_t gl_sortedlist_search (gl_list_t list, - gl_listelement_compar_fn compar, - const void *elt); - -/* Search whether an element is already in the list. - The list is assumed to be sorted with COMPAR. - Only list elements with indices >= START_INDEX and < END_INDEX are - considered; the implementation uses these bounds to minimize the number - of COMPAR invocations. - Return its node if found, or NULL if not present in the list. - If the list contains several copies of ELT, the node of the leftmost one is - returned. */ -extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list, - gl_listelement_compar_fn compar, - size_t start_index, - size_t end_index, - const void *elt); - -/* Search whether an element is already in the list. - The list is assumed to be sorted with COMPAR. - Return its position if found, or (size_t)(-1) if not present in the list. - If the list contains several copies of ELT, the position of the leftmost one - is returned. */ -extern size_t gl_sortedlist_indexof (gl_list_t list, - gl_listelement_compar_fn compar, - const void *elt); - -/* Search whether an element is already in the list. - The list is assumed to be sorted with COMPAR. - Only list elements with indices >= START_INDEX and < END_INDEX are - considered; the implementation uses these bounds to minimize the number - of COMPAR invocations. - Return its position if found, or (size_t)(-1) if not present in the list. - If the list contains several copies of ELT, the position of the leftmost one - is returned. */ -extern size_t gl_sortedlist_indexof_from_to (gl_list_t list, - gl_listelement_compar_fn compar, - size_t start_index, - size_t end_index, - const void *elt); - -/* Add an element at the appropriate position in the list. - The list is assumed to be sorted with COMPAR. - Return its node. */ -/* declared in gl_xlist.h */ -extern gl_list_node_t gl_sortedlist_add (gl_list_t list, - gl_listelement_compar_fn compar, - const void *elt); -/* Likewise. Return NULL upon out-of-memory. */ -extern gl_list_node_t gl_sortedlist_nx_add (gl_list_t list, - gl_listelement_compar_fn compar, - const void *elt) -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif - ; - -/* Search and remove an element from the list. - The list is assumed to be sorted with COMPAR. - Return true if it was found and removed. - If the list contains several copies of ELT, only the leftmost one is - removed. */ -extern bool gl_sortedlist_remove (gl_list_t list, - gl_listelement_compar_fn compar, - const void *elt); - -#endif /* End of inline and gl_xlist.h-defined functions. */ - -/* ------------------------ Implementation Details ------------------------ */ - -struct gl_list_implementation -{ - /* gl_list_t functions. */ - gl_list_t (*nx_create_empty) (gl_list_implementation_t implementation, - gl_listelement_equals_fn equals_fn, - gl_listelement_hashcode_fn hashcode_fn, - gl_listelement_dispose_fn dispose_fn, - bool allow_duplicates); - gl_list_t (*nx_create) (gl_list_implementation_t implementation, - gl_listelement_equals_fn equals_fn, - gl_listelement_hashcode_fn hashcode_fn, - gl_listelement_dispose_fn dispose_fn, - bool allow_duplicates, - size_t count, const void **contents); - size_t (*size) (gl_list_t list); - const void * (*node_value) (gl_list_t list, gl_list_node_t node); - int (*node_nx_set_value) (gl_list_t list, gl_list_node_t node, - const void *elt); - gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node); - gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node); - const void * (*get_at) (gl_list_t list, size_t position); - gl_list_node_t (*nx_set_at) (gl_list_t list, size_t position, - const void *elt); - gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index, - size_t end_index, const void *elt); - size_t (*indexof_from_to) (gl_list_t list, size_t start_index, - size_t end_index, const void *elt); - gl_list_node_t (*nx_add_first) (gl_list_t list, const void *elt); - gl_list_node_t (*nx_add_last) (gl_list_t list, const void *elt); - gl_list_node_t (*nx_add_before) (gl_list_t list, gl_list_node_t node, - const void *elt); - gl_list_node_t (*nx_add_after) (gl_list_t list, gl_list_node_t node, - const void *elt); - gl_list_node_t (*nx_add_at) (gl_list_t list, size_t position, - const void *elt); - bool (*remove_node) (gl_list_t list, gl_list_node_t node); - bool (*remove_at) (gl_list_t list, size_t position); - bool (*remove_elt) (gl_list_t list, const void *elt); - void (*list_free) (gl_list_t list); - /* gl_list_iterator_t functions. */ - gl_list_iterator_t (*iterator) (gl_list_t list); - gl_list_iterator_t (*iterator_from_to) (gl_list_t list, - size_t start_index, - size_t end_index); - bool (*iterator_next) (gl_list_iterator_t *iterator, - const void **eltp, gl_list_node_t *nodep); - void (*iterator_free) (gl_list_iterator_t *iterator); - /* Sorted gl_list_t functions. */ - gl_list_node_t (*sortedlist_search) (gl_list_t list, - gl_listelement_compar_fn compar, - const void *elt); - gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list, - gl_listelement_compar_fn compar, - size_t start_index, - size_t end_index, - const void *elt); - size_t (*sortedlist_indexof) (gl_list_t list, - gl_listelement_compar_fn compar, - const void *elt); - size_t (*sortedlist_indexof_from_to) (gl_list_t list, - gl_listelement_compar_fn compar, - size_t start_index, size_t end_index, - const void *elt); - gl_list_node_t (*sortedlist_nx_add) (gl_list_t list, - gl_listelement_compar_fn compar, - const void *elt); - bool (*sortedlist_remove) (gl_list_t list, - gl_listelement_compar_fn compar, - const void *elt); -}; - -struct gl_list_impl_base -{ - const struct gl_list_implementation *vtable; - gl_listelement_equals_fn equals_fn; - gl_listelement_hashcode_fn hashcode_fn; - gl_listelement_dispose_fn dispose_fn; - bool allow_duplicates; -}; - -/* Define all functions of this file as accesses to the - struct gl_list_implementation. */ - -GL_LIST_INLINE gl_list_t -gl_list_nx_create_empty (gl_list_implementation_t implementation, - gl_listelement_equals_fn equals_fn, - gl_listelement_hashcode_fn hashcode_fn, - gl_listelement_dispose_fn dispose_fn, - bool allow_duplicates) -{ - return implementation->nx_create_empty (implementation, equals_fn, - hashcode_fn, dispose_fn, - allow_duplicates); -} - -GL_LIST_INLINE gl_list_t -gl_list_nx_create (gl_list_implementation_t implementation, - gl_listelement_equals_fn equals_fn, - gl_listelement_hashcode_fn hashcode_fn, - gl_listelement_dispose_fn dispose_fn, - bool allow_duplicates, - size_t count, const void **contents) -{ - return implementation->nx_create (implementation, equals_fn, hashcode_fn, - dispose_fn, allow_duplicates, count, - contents); -} - -GL_LIST_INLINE size_t -gl_list_size (gl_list_t list) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->size (list); -} - -GL_LIST_INLINE const void * -gl_list_node_value (gl_list_t list, gl_list_node_t node) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->node_value (list, node); -} - -GL_LIST_INLINE int -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif -gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node, - const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->node_nx_set_value (list, node, elt); -} - -GL_LIST_INLINE gl_list_node_t -gl_list_next_node (gl_list_t list, gl_list_node_t node) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->next_node (list, node); -} - -GL_LIST_INLINE gl_list_node_t -gl_list_previous_node (gl_list_t list, gl_list_node_t node) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->previous_node (list, node); -} - -GL_LIST_INLINE const void * -gl_list_get_at (gl_list_t list, size_t position) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->get_at (list, position); -} - -GL_LIST_INLINE gl_list_node_t -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif -gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->nx_set_at (list, position, elt); -} - -GL_LIST_INLINE gl_list_node_t -gl_list_search (gl_list_t list, const void *elt) -{ - size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list); - return ((const struct gl_list_impl_base *) list)->vtable - ->search_from_to (list, 0, size, elt); -} - -GL_LIST_INLINE gl_list_node_t -gl_list_search_from (gl_list_t list, size_t start_index, const void *elt) -{ - size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list); - return ((const struct gl_list_impl_base *) list)->vtable - ->search_from_to (list, start_index, size, elt); -} - -GL_LIST_INLINE gl_list_node_t -gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index, - const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->search_from_to (list, start_index, end_index, elt); -} - -GL_LIST_INLINE size_t -gl_list_indexof (gl_list_t list, const void *elt) -{ - size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list); - return ((const struct gl_list_impl_base *) list)->vtable - ->indexof_from_to (list, 0, size, elt); -} - -GL_LIST_INLINE size_t -gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt) -{ - size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list); - return ((const struct gl_list_impl_base *) list)->vtable - ->indexof_from_to (list, start_index, size, elt); -} - -GL_LIST_INLINE size_t -gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, - const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->indexof_from_to (list, start_index, end_index, elt); -} - -GL_LIST_INLINE gl_list_node_t -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif -gl_list_nx_add_first (gl_list_t list, const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->nx_add_first (list, elt); -} - -GL_LIST_INLINE gl_list_node_t -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif -gl_list_nx_add_last (gl_list_t list, const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->nx_add_last (list, elt); -} - -GL_LIST_INLINE gl_list_node_t -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif -gl_list_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->nx_add_before (list, node, elt); -} - -GL_LIST_INLINE gl_list_node_t -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif -gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->nx_add_after (list, node, elt); -} - -GL_LIST_INLINE gl_list_node_t -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif -gl_list_nx_add_at (gl_list_t list, size_t position, const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->nx_add_at (list, position, elt); -} - -GL_LIST_INLINE bool -gl_list_remove_node (gl_list_t list, gl_list_node_t node) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->remove_node (list, node); -} - -GL_LIST_INLINE bool -gl_list_remove_at (gl_list_t list, size_t position) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->remove_at (list, position); -} - -GL_LIST_INLINE bool -gl_list_remove (gl_list_t list, const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->remove_elt (list, elt); -} - -GL_LIST_INLINE void -gl_list_free (gl_list_t list) -{ - ((const struct gl_list_impl_base *) list)->vtable->list_free (list); -} - -GL_LIST_INLINE gl_list_iterator_t -gl_list_iterator (gl_list_t list) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->iterator (list); -} - -GL_LIST_INLINE gl_list_iterator_t -gl_list_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->iterator_from_to (list, start_index, end_index); -} - -GL_LIST_INLINE bool -gl_list_iterator_next (gl_list_iterator_t *iterator, - const void **eltp, gl_list_node_t *nodep) -{ - return iterator->vtable->iterator_next (iterator, eltp, nodep); -} - -GL_LIST_INLINE void -gl_list_iterator_free (gl_list_iterator_t *iterator) -{ - iterator->vtable->iterator_free (iterator); -} - -GL_LIST_INLINE gl_list_node_t -gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->sortedlist_search (list, compar, elt); -} - -GL_LIST_INLINE gl_list_node_t -gl_sortedlist_search_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->sortedlist_search_from_to (list, compar, start_index, end_index, - elt); -} - -GL_LIST_INLINE size_t -gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->sortedlist_indexof (list, compar, elt); -} - -GL_LIST_INLINE size_t -gl_sortedlist_indexof_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->sortedlist_indexof_from_to (list, compar, start_index, end_index, - elt); -} - -GL_LIST_INLINE gl_list_node_t -#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) - __attribute__ ((__warn_unused_result__)) -#endif -gl_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->sortedlist_nx_add (list, compar, elt); -} - -GL_LIST_INLINE bool -gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) -{ - return ((const struct gl_list_impl_base *) list)->vtable - ->sortedlist_remove (list, compar, elt); -} - -#ifdef __cplusplus -} -#endif - -_GL_INLINE_HEADER_END - -#endif /* _GL_LIST_H */ diff --git a/mcastseed/lib/gl_rbtree_list.c b/mcastseed/lib/gl_rbtree_list.c deleted file mode 100644 index 5d621f1..0000000 --- a/mcastseed/lib/gl_rbtree_list.c +++ /dev/null @@ -1,102 +0,0 @@ -/* Sequential list data type implemented by a binary tree. - Copyright (C) 2006, 2008-2016 Free Software Foundation, Inc. - Written by Bruno Haible <bruno@clisp.org>, 2006. - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 3 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program. If not, see <http://www.gnu.org/licenses/>. */ - -#include <config.h> - -/* Specification. */ -#include "gl_rbtree_list.h" - -#include <stdlib.h> - -/* -------------------------- gl_list_t Data Type -------------------------- */ - -/* Generic red-black tree code. */ -#include "gl_anyrbtree_list1.h" - -/* Generic binary tree code. */ -#include "gl_anytree_list1.h" - -/* Generic red-black tree code. */ -#include "gl_anyrbtree_list2.h" - -/* Generic binary tree code. */ -#include "gl_anytree_list2.h" - -/* For debugging. */ -static unsigned int -check_invariants (gl_list_node_t node, gl_list_node_t parent) -{ - unsigned int left_blackheight = - (node->left != NULL ? check_invariants (node->left, node) : 0); - unsigned int right_blackheight = - (node->right != NULL ? check_invariants (node->right, node) : 0); - - if (!(node->parent == parent)) - abort (); - if (!(node->branch_size - == (node->left != NULL ? node->left->branch_size : 0) - + 1 + (node->right != NULL ? node->right->branch_size : 0))) - abort (); - if (!(node->color == BLACK || node->color == RED)) - abort (); - if (parent == NULL && !(node->color == BLACK)) - abort (); - if (!(left_blackheight == right_blackheight)) - abort (); - - return left_blackheight + (node->color == BLACK ? 1 : 0); -} -void -gl_rbtree_list_check_invariants (gl_list_t list) -{ - if (list->root != NULL) - check_invariants (list->root, NULL); -} - -const struct gl_list_implementation gl_rbtree_list_implementation = - { - gl_tree_nx_create_empty, - gl_tree_nx_create, - gl_tree_size, - gl_tree_node_value, - gl_tree_node_nx_set_value, - gl_tree_next_node, - gl_tree_previous_node, - gl_tree_get_at, - gl_tree_nx_set_at, - gl_tree_search_from_to, - gl_tree_indexof_from_to, - gl_tree_nx_add_first, - gl_tree_nx_add_last, - gl_tree_nx_add_before, - gl_tree_nx_add_after, - gl_tree_nx_add_at, - gl_tree_remove_node, - gl_tree_remove_at, - gl_tree_remove, - gl_tree_list_free, - gl_tree_iterator, - gl_tree_iterator_from_to, - gl_tree_iterator_next, - gl_tree_iterator_free, - gl_tree_sortedlist_search, - gl_tree_sortedlist_search_from_to, - gl_tree_sortedlist_indexof, - gl_tree_sortedlist_indexof_from_to, - gl_tree_sortedlist_nx_add, - gl_tree_sortedlist_remove - }; diff --git a/mcastseed/lib/gl_rbtree_list.h b/mcastseed/lib/gl_rbtree_list.h deleted file mode 100644 index 8cb9d11..0000000 --- a/mcastseed/lib/gl_rbtree_list.h +++ /dev/null @@ -1,34 +0,0 @@ -/* 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/mcastseed/lib/stdbool.in.h b/mcastseed/lib/stdbool.in.h deleted file mode 100644 index 7ecf203..0000000 --- a/mcastseed/lib/stdbool.in.h +++ /dev/null @@ -1,132 +0,0 @@ -/* 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 */ |