diff options
| -rw-r--r-- | mcastseed/lib/gl_anytree_oset.h | 297 | ||||
| -rw-r--r-- | mcastseed/lib/gl_oset.c | 3 | ||||
| -rw-r--r-- | mcastseed/lib/gl_oset.h | 293 | ||||
| -rw-r--r-- | mcastseed/lib/gl_rbtree_oset.c | 814 | ||||
| -rw-r--r-- | mcastseed/lib/gl_rbtree_oset.h | 34 | ||||
| -rw-r--r-- | mcastseed/lib/stdbool.in.h | 132 |
6 files changed, 1573 insertions, 0 deletions
diff --git a/mcastseed/lib/gl_anytree_oset.h b/mcastseed/lib/gl_anytree_oset.h new file mode 100644 index 0000000..127f4e3 --- /dev/null +++ b/mcastseed/lib/gl_anytree_oset.h @@ -0,0 +1,297 @@ +/* Ordered set data type implemented by a binary tree. + Copyright (C) 2006-2007, 2009-2016 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +/* Common code of gl_avltree_oset.c and gl_rbtree_oset.c. */ + +/* An item on the stack used for iterating across the elements. */ +typedef struct +{ + gl_oset_node_t node; + bool rightp; +} iterstack_item_t; + +/* A stack used for iterating across the elements. */ +typedef iterstack_item_t iterstack_t[MAXHEIGHT]; + +static gl_oset_t +gl_tree_nx_create_empty (gl_oset_implementation_t implementation, + gl_setelement_compar_fn compar_fn, + gl_setelement_dispose_fn dispose_fn) +{ + struct gl_oset_impl *set = + (struct gl_oset_impl *) malloc (sizeof (struct gl_oset_impl)); + + if (set == NULL) + return NULL; + + set->base.vtable = implementation; + set->base.compar_fn = compar_fn; + set->base.dispose_fn = dispose_fn; + set->root = NULL; + set->count = 0; + + return set; +} + +static size_t +gl_tree_size (gl_oset_t set) +{ + return set->count; +} + +static bool +gl_tree_search (gl_oset_t set, const void *elt) +{ + gl_setelement_compar_fn compar = set->base.compar_fn; + gl_oset_node_t node; + + for (node = set->root; node != NULL; ) + { + int cmp = (compar != NULL + ? compar (node->value, elt) + : (node->value > elt ? 1 : + node->value < elt ? -1 : 0)); + + if (cmp < 0) + node = node->right; + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + /* We have an element equal to ELT. */ + return true; + } + return false; +} + +static bool +gl_tree_search_atleast (gl_oset_t set, + gl_setelement_threshold_fn threshold_fn, + const void *threshold, + const void **eltp) +{ + gl_oset_node_t node; + + for (node = set->root; node != NULL; ) + { + if (! threshold_fn (node->value, threshold)) + node = node->right; + else + { + /* We have an element >= VALUE. But we need the leftmost such + element. */ + gl_oset_node_t found = node; + node = node->left; + for (; node != NULL; ) + { + if (! threshold_fn (node->value, threshold)) + node = node->right; + else + { + found = node; + node = node->left; + } + } + *eltp = found->value; + return true; + } + } + return false; +} + +static gl_oset_node_t +gl_tree_search_node (gl_oset_t set, const void *elt) +{ + gl_setelement_compar_fn compar = set->base.compar_fn; + gl_oset_node_t node; + + for (node = set->root; node != NULL; ) + { + int cmp = (compar != NULL + ? compar (node->value, elt) + : (node->value > elt ? 1 : + node->value < elt ? -1 : 0)); + + if (cmp < 0) + node = node->right; + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + /* We have an element equal to ELT. */ + return node; + } + return NULL; +} + +static int +gl_tree_nx_add (gl_oset_t set, const void *elt) +{ + gl_setelement_compar_fn compar; + gl_oset_node_t node = set->root; + + if (node == NULL) + { + if (gl_tree_nx_add_first (set, elt) == NULL) + return -1; + return true; + } + + compar = set->base.compar_fn; + + for (;;) + { + int cmp = (compar != NULL + ? compar (node->value, elt) + : (node->value > elt ? 1 : + node->value < elt ? -1 : 0)); + + if (cmp < 0) + { + if (node->right == NULL) + { + if (gl_tree_nx_add_after (set, node, elt) == NULL) + return -1; + return true; + } + node = node->right; + } + else if (cmp > 0) + { + if (node->left == NULL) + { + if (gl_tree_nx_add_before (set, node, elt) == NULL) + return -1; + return true; + } + node = node->left; + } + else /* cmp == 0 */ + return false; + } +} + +static bool +gl_tree_remove (gl_oset_t set, const void *elt) +{ + gl_oset_node_t node = gl_tree_search_node (set, elt); + + if (node != NULL) + return gl_tree_remove_node (set, node); + else + return false; +} + +static void +gl_tree_oset_free (gl_oset_t set) +{ + /* Iterate across all elements in post-order. */ + gl_oset_node_t node = set->root; + iterstack_t stack; + iterstack_item_t *stack_ptr = &stack[0]; + + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + stack_ptr->node = node; + stack_ptr->rightp = false; + node = node->left; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + goto done_iterate; + stack_ptr--; + node = stack_ptr->node; + if (!stack_ptr->rightp) + break; + /* Free the current node. */ + if (set->base.dispose_fn != NULL) + set->base.dispose_fn (node->value); + free (node); + } + /* Descend on right branch. */ + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; + } + done_iterate: + free (set); +} + +/* --------------------- gl_oset_iterator_t Data Type --------------------- */ + +static gl_oset_iterator_t +gl_tree_iterator (gl_oset_t set) +{ + gl_oset_iterator_t result; + gl_oset_node_t node; + + result.vtable = set->base.vtable; + result.set = set; + /* Start node is the leftmost node. */ + node = set->root; + if (node != NULL) + while (node->left != NULL) + node = node->left; + result.p = node; + /* End point is past the rightmost node. */ + result.q = NULL; +#if defined GCC_LINT || defined lint + result.i = 0; + result.j = 0; + result.count = 0; +#endif + + return result; +} + +static bool +gl_tree_iterator_next (gl_oset_iterator_t *iterator, const void **eltp) +{ + if (iterator->p != iterator->q) + { + gl_oset_node_t node = (gl_oset_node_t) iterator->p; + *eltp = node->value; + /* Advance to the next node. */ + if (node->right != NULL) + { + node = node->right; + while (node->left != NULL) + node = node->left; + } + else + { + while (node->parent != NULL && node->parent->right == node) + node = node->parent; + node = node->parent; + } + iterator->p = node; + return true; + } + else + return false; +} + +static void +gl_tree_iterator_free (gl_oset_iterator_t *iterator) +{ +} diff --git a/mcastseed/lib/gl_oset.c b/mcastseed/lib/gl_oset.c new file mode 100644 index 0000000..21f731a --- /dev/null +++ b/mcastseed/lib/gl_oset.c @@ -0,0 +1,3 @@ +#include <config.h> +#define GL_OSET_INLINE _GL_EXTERN_INLINE +#include "gl_oset.h" diff --git a/mcastseed/lib/gl_oset.h b/mcastseed/lib/gl_oset.h new file mode 100644 index 0000000..ffca315 --- /dev/null +++ b/mcastseed/lib/gl_oset.h @@ -0,0 +1,293 @@ +/* Abstract ordered set data type. + Copyright (C) 2006-2007, 2009-2016 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +#ifndef _GL_OSET_H +#define _GL_OSET_H + +#include <stdbool.h> +#include <stddef.h> + +#ifndef _GL_INLINE_HEADER_BEGIN + #error "Please include config.h first." +#endif +_GL_INLINE_HEADER_BEGIN +#ifndef GL_OSET_INLINE +# define GL_OSET_INLINE _GL_INLINE +#endif + +#ifdef __cplusplus +extern "C" { +#endif + + +/* gl_oset is an abstract ordered set data type. It can contain any number + of objects ('void *' or 'const void *' pointers) in the order of a given + comparator function. Duplicates (in the sense of the comparator) are + forbidden. + + There are several implementations of this ordered set datatype, optimized + for different operations or for memory. You can start using the simplest + ordered set implementation, GL_ARRAY_OSET, and switch to a different + implementation later, when you realize which operations are performed + the most frequently. The API of the different implementations is exactly + the same; when switching to a different implementation, you only have to + change the gl_oset_create call. + + The implementations are: + GL_ARRAY_OSET a growable array + GL_AVLTREE_OSET a binary tree (AVL tree) + GL_RBTREE_OSET a binary tree (red-black tree) + + The memory consumption is asymptotically the same: O(1) for every object + in the set. When looking more closely at the average memory consumed + for an object, GL_ARRAY_OSET is the most compact representation, and + GL_AVLTREE_OSET, GL_RBTREE_OSET need more memory. + + The guaranteed average performance of the operations is, for a set of + n elements: + + Operation ARRAY TREE + + gl_oset_size O(1) O(1) + gl_oset_add O(n) O(log n) + gl_oset_remove O(n) O(log n) + gl_oset_search O(log n) O(log n) + gl_oset_search_atleast O(log n) O(log n) + gl_oset_iterator O(1) O(log n) + gl_oset_iterator_next O(1) O(log n) + */ + +/* -------------------------- gl_oset_t Data Type -------------------------- */ + +/* Type of function used to compare two elements. Same as for qsort(). + NULL denotes pointer comparison. */ +typedef int (*gl_setelement_compar_fn) (const void *elt1, const void *elt2); + +/* Type of function used to dispose an element once it's removed from a set. + NULL denotes a no-op. */ +typedef void (*gl_setelement_dispose_fn) (const void *elt); + +/* Type of function used to compare an element with a threshold. + Return true if the element is greater or equal than the threshold. */ +typedef bool (*gl_setelement_threshold_fn) (const void *elt, const void *threshold); + +struct gl_oset_impl; +/* Type representing an entire ordered set. */ +typedef struct gl_oset_impl * gl_oset_t; + +struct gl_oset_implementation; +/* Type representing a ordered set datatype implementation. */ +typedef const struct gl_oset_implementation * gl_oset_implementation_t; + +#if 0 /* Unless otherwise specified, these are defined inline below. */ + +/* Create an empty set. + IMPLEMENTATION is one of GL_ARRAY_OSET, GL_AVLTREE_OSET, GL_RBTREE_OSET. + COMPAR_FN is an element comparison function or NULL. + DISPOSE_FN is an element disposal function or NULL. */ +/* declared in gl_xoset.h */ +extern gl_oset_t gl_oset_create_empty (gl_oset_implementation_t implementation, + gl_setelement_compar_fn compar_fn, + gl_setelement_dispose_fn dispose_fn); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_oset_t gl_oset_nx_create_empty (gl_oset_implementation_t implementation, + gl_setelement_compar_fn compar_fn, + gl_setelement_dispose_fn dispose_fn); + +/* Return the current number of elements in an ordered set. */ +extern size_t gl_oset_size (gl_oset_t set); + +/* Search whether an element is already in the ordered set. + Return true if found, or false if not present in the set. */ +extern bool gl_oset_search (gl_oset_t set, const void *elt); + +/* Search the least element in the ordered set that compares greater or equal + to the given THRESHOLD. The representation of the THRESHOLD is defined + by the THRESHOLD_FN. + Return true and store the found element in *ELTP if found, otherwise return + false. */ +extern bool gl_oset_search_atleast (gl_oset_t set, + gl_setelement_threshold_fn threshold_fn, + const void *threshold, + const void **eltp); + +/* Add an element to an ordered set. + Return true if it was not already in the set and added, false otherwise. */ +/* declared in gl_xoset.h */ +extern bool gl_oset_add (gl_oset_t set, const void *elt); +/* Likewise. Return -1 upon out-of-memory. */ +extern int gl_oset_nx_add (gl_oset_t set, const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Remove an element from an ordered set. + Return true if it was found and removed. */ +extern bool gl_oset_remove (gl_oset_t set, const void *elt); + +/* Free an entire ordered set. + (But this call does not free the elements of the set.) */ +extern void gl_oset_free (gl_oset_t set); + +#endif /* End of inline and gl_xlist.h-defined functions. */ + +/* --------------------- gl_oset_iterator_t Data Type --------------------- */ + +/* Functions for iterating through an ordered set. */ + +/* Type of an iterator that traverses an ordered set. + This is a fixed-size struct, so that creation of an iterator doesn't need + memory allocation on the heap. */ +typedef struct +{ + /* For fast dispatch of gl_oset_iterator_next. */ + const struct gl_oset_implementation *vtable; + /* For detecting whether the last returned element was removed. */ + gl_oset_t set; + size_t count; + /* Other, implementation-private fields. */ + void *p; void *q; + size_t i; size_t j; +} gl_oset_iterator_t; + +#if 0 /* These are defined inline below. */ + +/* Create an iterator traversing an ordered set. + The set's contents must not be modified while the iterator is in use, + except for removing the last returned element. */ +extern gl_oset_iterator_t gl_oset_iterator (gl_oset_t set); + +/* If there is a next element, store the next element in *ELTP, advance the + iterator and return true. Otherwise, return false. */ +extern bool gl_oset_iterator_next (gl_oset_iterator_t *iterator, + const void **eltp); + +/* Free an iterator. */ +extern void gl_oset_iterator_free (gl_oset_iterator_t *iterator); + +#endif /* End of inline functions. */ + +/* ------------------------ Implementation Details ------------------------ */ + +struct gl_oset_implementation +{ + /* gl_oset_t functions. */ + gl_oset_t (*nx_create_empty) (gl_oset_implementation_t implementation, + gl_setelement_compar_fn compar_fn, + gl_setelement_dispose_fn dispose_fn); + size_t (*size) (gl_oset_t set); + bool (*search) (gl_oset_t set, const void *elt); + bool (*search_atleast) (gl_oset_t set, + gl_setelement_threshold_fn threshold_fn, + const void *threshold, const void **eltp); + int (*nx_add) (gl_oset_t set, const void *elt); + bool (*remove_elt) (gl_oset_t set, const void *elt); + void (*oset_free) (gl_oset_t set); + /* gl_oset_iterator_t functions. */ + gl_oset_iterator_t (*iterator) (gl_oset_t set); + bool (*iterator_next) (gl_oset_iterator_t *iterator, const void **eltp); + void (*iterator_free) (gl_oset_iterator_t *iterator); +}; + +struct gl_oset_impl_base +{ + const struct gl_oset_implementation *vtable; + gl_setelement_compar_fn compar_fn; + gl_setelement_dispose_fn dispose_fn; +}; + +/* Define all functions of this file as accesses to the + struct gl_oset_implementation. */ + +GL_OSET_INLINE gl_oset_t +gl_oset_nx_create_empty (gl_oset_implementation_t implementation, + gl_setelement_compar_fn compar_fn, + gl_setelement_dispose_fn dispose_fn) +{ + return implementation->nx_create_empty (implementation, compar_fn, + dispose_fn); +} + +GL_OSET_INLINE size_t +gl_oset_size (gl_oset_t set) +{ + return ((const struct gl_oset_impl_base *) set)->vtable->size (set); +} + +GL_OSET_INLINE bool +gl_oset_search (gl_oset_t set, const void *elt) +{ + return ((const struct gl_oset_impl_base *) set)->vtable->search (set, elt); +} + +GL_OSET_INLINE bool +gl_oset_search_atleast (gl_oset_t set, + gl_setelement_threshold_fn threshold_fn, + const void *threshold, const void **eltp) +{ + return ((const struct gl_oset_impl_base *) set)->vtable + ->search_atleast (set, threshold_fn, threshold, eltp); +} + +GL_OSET_INLINE int +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_oset_nx_add (gl_oset_t set, const void *elt) +{ + return ((const struct gl_oset_impl_base *) set)->vtable->nx_add (set, elt); +} + +GL_OSET_INLINE bool +gl_oset_remove (gl_oset_t set, const void *elt) +{ + return ((const struct gl_oset_impl_base *) set)->vtable + ->remove_elt (set, elt); +} + +GL_OSET_INLINE void +gl_oset_free (gl_oset_t set) +{ + ((const struct gl_oset_impl_base *) set)->vtable->oset_free (set); +} + +GL_OSET_INLINE gl_oset_iterator_t +gl_oset_iterator (gl_oset_t set) +{ + return ((const struct gl_oset_impl_base *) set)->vtable->iterator (set); +} + +GL_OSET_INLINE bool +gl_oset_iterator_next (gl_oset_iterator_t *iterator, const void **eltp) +{ + return iterator->vtable->iterator_next (iterator, eltp); +} + +GL_OSET_INLINE void +gl_oset_iterator_free (gl_oset_iterator_t *iterator) +{ + iterator->vtable->iterator_free (iterator); +} + +#ifdef __cplusplus +} +#endif + +_GL_INLINE_HEADER_END + +#endif /* _GL_OSET_H */ diff --git a/mcastseed/lib/gl_rbtree_oset.c b/mcastseed/lib/gl_rbtree_oset.c new file mode 100644 index 0000000..615b9ae --- /dev/null +++ b/mcastseed/lib/gl_rbtree_oset.c @@ -0,0 +1,814 @@ +/* Ordered set data type implemented by a binary tree. + Copyright (C) 2006-2007, 2009-2016 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +#include <config.h> + +/* Specification. */ +#include "gl_rbtree_oset.h" + +#include <stdlib.h> + +/* 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_oset_t Data Type -------------------------- */ + +/* Color of a node. */ +typedef enum color { BLACK, RED } color_t; + +/* Tree node implementation, valid for this file only. */ +struct gl_oset_node_impl +{ + struct gl_oset_node_impl *left; /* left branch, or NULL */ + struct gl_oset_node_impl *right; /* right branch, or NULL */ + /* Parent pointer, or NULL. The parent pointer is not needed for most + operations. It is needed so that a gl_oset_node_t can be returned + without memory allocation, on which the functions gl_oset_remove_node, + gl_oset_add_before, gl_oset_add_after can be implemented. */ + struct gl_oset_node_impl *parent; + color_t color; /* node's color */ + const void *value; +}; +typedef struct gl_oset_node_impl * gl_oset_node_t; + +/* Concrete gl_oset_impl type, valid for this file only. */ +struct gl_oset_impl +{ + struct gl_oset_impl_base base; + struct gl_oset_node_impl *root; /* root node or NULL */ + size_t count; /* number of nodes */ +}; + +/* A red-black tree of height h has a black-height bh >= ceil(h/2) and + therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree + of height h >= 117 would have at least 2^59 - 1 elements, and because even + on 64-bit machines, + sizeof (gl_oset_node_impl) * (2^59 - 1) > 2^64 + this would exceed the address space of the machine. */ +#define MAXHEIGHT 116 + +/* 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_oset_node_t +rotate_left (gl_oset_node_t b_node, gl_oset_node_t d_node) +{ + gl_oset_node_t c_node = d_node->left; + + 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; + + 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_oset_node_t +rotate_right (gl_oset_node_t b_node, gl_oset_node_t d_node) +{ + gl_oset_node_t c_node = b_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; + + 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_oset_t set, gl_oset_node_t node, gl_oset_node_t parent) +{ + for (;;) + { + /* At this point, parent = node->parent != NULL. + Think of node->color being RED (although node->color is not yet + assigned.) */ + gl_oset_node_t grandparent; + gl_oset_node_t uncle; + + 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_oset_node_t *grandparentp; + + if (grandparent->parent == NULL) + grandparentp = &set->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_oset_t set, gl_oset_node_t child, gl_oset_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_oset_node_t *parentp; + + if (parent->parent == NULL) + parentp = &set->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_oset_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_oset_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 gl_oset_node_t +gl_tree_nx_add_first (gl_oset_t set, const void *elt) +{ + /* Create new node. */ + gl_oset_node_t new_node = + (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl)); + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->value = elt; + + /* Add it to the tree. */ + if (set->root == NULL) + { + new_node->color = BLACK; + set->root = new_node; + new_node->parent = NULL; + } + else + { + gl_oset_node_t node; + + for (node = set->root; node->left != NULL; ) + node = node->left; + + node->left = new_node; + new_node->parent = node; + + /* Color and rebalance. */ + rebalance_after_add (set, new_node, node); + } + + set->count++; + return new_node; +} + +static gl_oset_node_t +gl_tree_nx_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt) +{ + /* Create new node. */ + gl_oset_node_t new_node = + (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl)); + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->value = elt; + + /* Add it to the tree. */ + if (node->left == NULL) + node->left = new_node; + else + { + for (node = node->left; node->right != NULL; ) + node = node->right; + node->right = new_node; + } + new_node->parent = node; + + /* Color and rebalance. */ + rebalance_after_add (set, new_node, node); + + set->count++; + return new_node; +} + +static gl_oset_node_t +gl_tree_nx_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt) +{ + /* Create new node. */ + gl_oset_node_t new_node = + (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl)); + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->value = elt; + + /* Add it to the tree. */ + if (node->right == NULL) + node->right = new_node; + else + { + for (node = node->right; node->left != NULL; ) + node = node->left; + node->left = new_node; + } + new_node->parent = node; + + /* Color and rebalance. */ + rebalance_after_add (set, new_node, node); + + set->count++; + return new_node; +} + +static bool +gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node) +{ + gl_oset_node_t parent = node->parent; + + if (node->left == NULL) + { + /* Replace node with node->right. */ + gl_oset_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) + set->root = child; + else + { + if (parent->left == node) + parent->left = child; + else /* parent->right == node */ + parent->right = child; + + if (child == NULL && node->color == BLACK) + rebalance_after_remove (set, 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_oset_node_t child = node->left; + + child->parent = parent; + /* Since node->right == NULL, child must be RED and of height 1, + hence node must have been BLACK. Recolor the child. */ + child->color = BLACK; + if (parent == NULL) + set->root = child; + else + { + if (parent->left == node) + parent->left = child; + else /* parent->right == node */ + parent->right = child; + } + } + else + { + /* Replace node with the rightmost element of the node->left subtree. */ + gl_oset_node_t subst; + gl_oset_node_t subst_parent; + gl_oset_node_t child; + 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; + } + + /* 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->parent = parent; + if (parent == NULL) + set->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 (set, child, + subst_parent != node ? subst_parent : subst); + } + } + + set->count--; + if (set->base.dispose_fn != NULL) + set->base.dispose_fn (node->value); + free (node); + return true; +} + +/* Generic binary tree code. */ +#include "gl_anytree_oset.h" + +/* For debugging. */ +static unsigned int +check_invariants (gl_oset_node_t node, gl_oset_node_t parent, size_t *counterp) +{ + unsigned int left_blackheight = + (node->left != NULL ? check_invariants (node->left, node, counterp) : 0); + unsigned int right_blackheight = + (node->right != NULL ? check_invariants (node->right, node, counterp) : 0); + + if (!(node->parent == parent)) + abort (); + if (!(node->color == BLACK || node->color == RED)) + abort (); + if (parent == NULL && !(node->color == BLACK)) + abort (); + if (!(left_blackheight == right_blackheight)) + abort (); + + (*counterp)++; + + return left_blackheight + (node->color == BLACK ? 1 : 0); +} +void +gl_rbtree_oset_check_invariants (gl_oset_t set) +{ + size_t counter = 0; + if (set->root != NULL) + check_invariants (set->root, NULL, &counter); + if (!(set->count == counter)) + abort (); +} + +const struct gl_oset_implementation gl_rbtree_oset_implementation = + { + gl_tree_nx_create_empty, + gl_tree_size, + gl_tree_search, + gl_tree_search_atleast, + gl_tree_nx_add, + gl_tree_remove, + gl_tree_oset_free, + gl_tree_iterator, + gl_tree_iterator_next, + gl_tree_iterator_free + }; diff --git a/mcastseed/lib/gl_rbtree_oset.h b/mcastseed/lib/gl_rbtree_oset.h new file mode 100644 index 0000000..850e8b4 --- /dev/null +++ b/mcastseed/lib/gl_rbtree_oset.h @@ -0,0 +1,34 @@ +/* Ordered set 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_OSET_H +#define _GL_RBTREE_OSET_H + +#include "gl_oset.h" + +#ifdef __cplusplus +extern "C" { +#endif + +extern const struct gl_oset_implementation gl_rbtree_oset_implementation; +#define GL_RBTREE_OSET &gl_rbtree_oset_implementation + +#ifdef __cplusplus +} +#endif + +#endif /* _GL_RBTREE_OSET_H */ diff --git a/mcastseed/lib/stdbool.in.h b/mcastseed/lib/stdbool.in.h new file mode 100644 index 0000000..7ecf203 --- /dev/null +++ b/mcastseed/lib/stdbool.in.h @@ -0,0 +1,132 @@ +/* Copyright (C) 2001-2003, 2006-2016 Free Software Foundation, Inc. + Written by Bruno Haible <haible@clisp.cons.org>, 2001. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3, or (at your option) + any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, see <http://www.gnu.org/licenses/>. */ + +#ifndef _GL_STDBOOL_H +#define _GL_STDBOOL_H + +/* ISO C 99 <stdbool.h> for platforms that lack it. */ + +/* Usage suggestions: + + Programs that use <stdbool.h> should be aware of some limitations + and standards compliance issues. + + Standards compliance: + + - <stdbool.h> must be #included before 'bool', 'false', 'true' + can be used. + + - You cannot assume that sizeof (bool) == 1. + + - Programs should not undefine the macros bool, true, and false, + as C99 lists that as an "obsolescent feature". + + Limitations of this substitute, when used in a C89 environment: + + - <stdbool.h> must be #included before the '_Bool' type can be used. + + - You cannot assume that _Bool is a typedef; it might be a macro. + + - Bit-fields of type 'bool' are not supported. Portable code + should use 'unsigned int foo : 1;' rather than 'bool foo : 1;'. + + - In C99, casts and automatic conversions to '_Bool' or 'bool' are + performed in such a way that every nonzero value gets converted + to 'true', and zero gets converted to 'false'. This doesn't work + with this substitute. With this substitute, only the values 0 and 1 + give the expected result when converted to _Bool' or 'bool'. + + - C99 allows the use of (_Bool)0.0 in constant expressions, but + this substitute cannot always provide this property. + + Also, it is suggested that programs use 'bool' rather than '_Bool'; + this isn't required, but 'bool' is more common. */ + + +/* 7.16. Boolean type and values */ + +/* BeOS <sys/socket.h> already #defines false 0, true 1. We use the same + definitions below, but temporarily we have to #undef them. */ +#if defined __BEOS__ && !defined __HAIKU__ +# include <OS.h> /* defines bool but not _Bool */ +# undef false +# undef true +#endif + +#ifdef __cplusplus +# define _Bool bool +# define bool bool +#else +# if defined __BEOS__ && !defined __HAIKU__ + /* A compiler known to have 'bool'. */ + /* If the compiler already has both 'bool' and '_Bool', we can assume they + are the same types. */ +# if !@HAVE__BOOL@ +typedef bool _Bool; +# endif +# else +# if !defined __GNUC__ + /* If @HAVE__BOOL@: + Some HP-UX cc and AIX IBM C compiler versions have compiler bugs when + the built-in _Bool type is used. See + http://gcc.gnu.org/ml/gcc-patches/2003-12/msg02303.html + http://lists.gnu.org/archive/html/bug-coreutils/2005-11/msg00161.html + http://lists.gnu.org/archive/html/bug-coreutils/2005-10/msg00086.html + Similar bugs are likely with other compilers as well; this file + wouldn't be used if <stdbool.h> was working. + So we override the _Bool type. + If !@HAVE__BOOL@: + Need to define _Bool ourselves. As 'signed char' or as an enum type? + Use of a typedef, with SunPRO C, leads to a stupid + "warning: _Bool is a keyword in ISO C99". + Use of an enum type, with IRIX cc, leads to a stupid + "warning(1185): enumerated type mixed with another type". + Even the existence of an enum type, without a typedef, + "Invalid enumerator. (badenum)" with HP-UX cc on Tru64. + The only benefit of the enum, debuggability, is not important + with these compilers. So use 'signed char' and no enum. */ +# define _Bool signed char +# else + /* With this compiler, trust the _Bool type if the compiler has it. */ +# if !@HAVE__BOOL@ + /* For the sake of symbolic names in gdb, define true and false as + enum constants, not only as macros. + It is tempting to write + typedef enum { false = 0, true = 1 } _Bool; + so that gdb prints values of type 'bool' symbolically. But then + values of type '_Bool' might promote to 'int' or 'unsigned int' + (see ISO C 99 6.7.2.2.(4)); however, '_Bool' must promote to 'int' + (see ISO C 99 6.3.1.1.(2)). So add a negative value to the + enum; this ensures that '_Bool' promotes to 'int'. */ +typedef enum { _Bool_must_promote_to_int = -1, false = 0, true = 1 } _Bool; +# endif +# endif +# endif +# define bool _Bool +#endif + +/* The other macros must be usable in preprocessor directives. */ +#ifdef __cplusplus +# define false false +# define true true +#else +# define false 0 +# define true 1 +#endif + +#define __bool_true_false_are_defined 1 + +#endif /* _GL_STDBOOL_H */ |