Importing gnulib module gl_rbtree_oset and deps

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 */