Common code several concrete list implementations.

1 files changed, 547 insertions, 0 deletions

diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h
new file mode 100644
index 0000000000..19ecae5f70
--- /dev/null
+++ b/lib/gl_anytree_list2.h
@@ -0,0 +1,547 @@
+/* Sequential list data type implemented by a binary tree.
+   Copyright (C) 2006 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 2, 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, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Common code of gl_avltree_list.c, gl_rbtree_list.c,
+                  gl_avltreehash_list.c, gl_rbtreehash_list.c.  */
+
+static gl_list_t
+gl_tree_create_empty (gl_list_implementation_t implementation,
+		      gl_listelement_equals_fn equals_fn,
+		      gl_listelement_hashcode_fn hashcode_fn,
+		      bool allow_duplicates)
+{
+  struct gl_list_impl *list =
+    (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
+
+  list->base.vtable = implementation;
+  list->base.equals_fn = equals_fn;
+  list->base.hashcode_fn = hashcode_fn;
+  list->base.allow_duplicates = allow_duplicates;
+#if WITH_HASHTABLE
+  list->table_size = 11;
+  list->table =
+    (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
+#endif
+  list->root = NULL;
+
+  return list;
+}
+
+static size_t
+gl_tree_size (gl_list_t list)
+{
+  return (list->root != NULL ? list->root->branch_size : 0);
+}
+
+static const void *
+gl_tree_node_value (gl_list_t list, gl_list_node_t node)
+{
+  return node->value;
+}
+
+static gl_list_node_t
+gl_tree_next_node (gl_list_t list, gl_list_node_t node)
+{
+  if (node->right != NULL)
+    {
+      node = node->right;
+      while (node->left != NULL)
+	node = node->left;
+    }
+  else
+    {
+      while (node->parent != NULL && node->parent->right == node)
+	node = node->parent;
+      node = node->parent;
+    }
+  return node;
+}
+
+static gl_list_node_t
+gl_tree_previous_node (gl_list_t list, gl_list_node_t node)
+{
+  if (node->left != NULL)
+    {
+      node = node->left;
+      while (node->right != NULL)
+	node = node->right;
+    }
+  else
+    {
+      while (node->parent != NULL && node->parent->left == node)
+	node = node->parent;
+      node = node->parent;
+    }
+  return node;
+}
+
+/* Return the node at the given position < gl_tree_size (list).  */
+static inline gl_list_node_t
+node_at (gl_list_node_t root, size_t position)
+{
+  /* Here we know that root != NULL.  */
+  gl_list_node_t node = root;
+
+  for (;;)
+    {
+      if (node->left != NULL)
+	{
+	  if (position < node->left->branch_size)
+	    {
+	      node = node->left;
+	      continue;
+	    }
+	  position -= node->left->branch_size;
+	}
+      if (position == 0)
+	break;
+      position--;
+      node = node->right;
+    }
+  return node;
+}
+
+static const void *
+gl_tree_get_at (gl_list_t list, size_t position)
+{
+  gl_list_node_t node = list->root;
+
+  if (!(node != NULL && position < node->branch_size))
+    /* Invalid argument.  */
+    abort ();
+  node = node_at (node, position);
+  return node->value;
+}
+
+static gl_list_node_t
+gl_tree_set_at (gl_list_t list, size_t position, const void *elt)
+{
+  gl_list_node_t node = list->root;
+
+  if (!(node != NULL && position < node->branch_size))
+    /* Invalid argument.  */
+    abort ();
+  node = node_at (node, position);
+#if WITH_HASHTABLE
+  if (elt != node->value)
+    {
+      size_t new_hashcode =
+	(list->base.hashcode_fn != NULL
+	 ? list->base.hashcode_fn (elt)
+	 : (size_t)(uintptr_t) elt);
+
+      if (new_hashcode != node->h.hashcode)
+	{
+	  remove_from_bucket (list, node);
+	  node->value = elt;
+	  node->h.hashcode = new_hashcode;
+	  add_to_bucket (list, node);
+	}
+      else
+	node->value = elt;
+    }
+#else
+  node->value = elt;
+#endif
+  return node;
+}
+
+#if !WITH_HASHTABLE
+
+static gl_list_node_t
+gl_tree_search (gl_list_t list, const void *elt)
+{
+  gl_listelement_equals_fn equals = list->base.equals_fn;
+  /* Iterate across all elements.  */
+  gl_list_node_t node = list->root;
+  iterstack_t stack;
+  iterstack_item_t *stack_ptr = &stack[0];
+
+  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])
+	    return NULL;
+	  stack_ptr--;
+	  if (!stack_ptr->rightp)
+	    break;
+	}
+      node = stack_ptr->node;
+      /* Test against current element.  */
+      if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+	return node;
+      /* Descend on right branch.  */
+      stack_ptr->rightp = true;
+      node = node->right;
+      stack_ptr++;
+    }
+}
+
+static size_t
+gl_tree_indexof (gl_list_t list, const void *elt)
+{
+  gl_listelement_equals_fn equals = list->base.equals_fn;
+  /* Iterate across all elements.  */
+  gl_list_node_t node = list->root;
+  iterstack_t stack;
+  iterstack_item_t *stack_ptr = &stack[0];
+  size_t index = 0;
+
+  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])
+	    return (size_t)(-1);
+	  stack_ptr--;
+	  if (!stack_ptr->rightp)
+	    break;
+	}
+      node = stack_ptr->node;
+      /* Test against current element.  */
+      if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+	return index;
+      index++;
+      /* Descend on right branch.  */
+      stack_ptr->rightp = true;
+      node = node->right;
+      stack_ptr++;
+    }
+}
+
+#endif
+
+static gl_list_node_t
+gl_tree_add_at (gl_list_t list, size_t position, const void *elt)
+{
+  size_t count = (list->root != NULL ? list->root->branch_size : 0);
+
+  if (!(position <= count))
+    /* Invalid argument.  */
+    abort ();
+  if (position == count)
+    return gl_tree_add_last (list, elt);
+  else
+    return gl_tree_add_before (list, node_at (list->root, position), elt);
+}
+
+static bool
+gl_tree_remove_at (gl_list_t list, size_t position)
+{
+  gl_list_node_t node = list->root;
+
+  if (!(node != NULL && position < node->branch_size))
+    /* Invalid argument.  */
+    abort ();
+  node = node_at (node, position);
+  return gl_tree_remove_node (list, node);
+}
+
+static bool
+gl_tree_remove (gl_list_t list, const void *elt)
+{
+  gl_list_node_t node = gl_tree_search (list, elt);
+
+  if (node != NULL)
+    return gl_tree_remove_node (list, node);
+  else
+    return false;
+}
+
+#if !WITH_HASHTABLE
+
+static void
+gl_tree_list_free (gl_list_t list)
+{
+  /* Iterate across all elements in post-order.  */
+  gl_list_node_t node = list->root;
+  iterstack_t stack;
+  iterstack_item_t *stack_ptr = &stack[0];
+
+  for (;;)
+    {
+      /* Descend on left branch.  */
+      for (;;)
+	{
+	  if (node == NULL)
+	    break;
+	  stack_ptr->node = node;
+	  stack_ptr->rightp = false;
+	  node = node->left;
+	  stack_ptr++;
+	}
+      /* Climb up again.  */
+      for (;;)
+	{
+	  if (stack_ptr == &stack[0])
+	    goto done_iterate;
+	  stack_ptr--;
+	  node = stack_ptr->node;
+	  if (!stack_ptr->rightp)
+	    break;
+	  /* Free the current node.  */
+	  free (node);
+	}
+      /* Descend on right branch.  */
+      stack_ptr->rightp = true;
+      node = node->right;
+      stack_ptr++;
+    }
+ done_iterate:
+  free (list);
+}
+
+#endif
+
+/* --------------------- gl_list_iterator_t Data Type --------------------- */
+
+static gl_list_iterator_t
+gl_tree_iterator (gl_list_t list)
+{
+  gl_list_iterator_t result;
+  gl_list_node_t node;
+
+  result.vtable = list->base.vtable;
+  result.list = list;
+  /* Start node is the leftmost node.  */
+  node = list->root;
+  if (node != NULL)
+    while (node->left != NULL)
+      node = node->left;
+  result.p = node;
+  /* End point is past the rightmost node.  */
+  result.q = NULL;
+
+  return result;
+}
+
+static gl_list_iterator_t
+gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
+{
+  size_t count = (list->root != NULL ? list->root->branch_size : 0);
+  gl_list_iterator_t result;
+
+  if (!(start_index <= end_index && end_index <= count))
+    /* Invalid arguments.  */
+    abort ();
+  result.vtable = list->base.vtable;
+  result.list = list;
+  /* Start node is the node at position start_index.  */
+  result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
+  /* End point is the node at position end_index.  */
+  result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
+
+  return result;
+}
+
+static bool
+gl_tree_iterator_next (gl_list_iterator_t *iterator,
+		       const void **eltp, gl_list_node_t *nodep)
+{
+  if (iterator->p != iterator->q)
+    {
+      gl_list_node_t node = (gl_list_node_t) iterator->p;
+      *eltp = node->value;
+      if (nodep != NULL)
+	*nodep = node;
+      /* Advance to the next node.  */
+      if (node->right != NULL)
+	{
+	  node = node->right;
+	  while (node->left != NULL)
+	    node = node->left;
+	}
+      else
+	{
+	  while (node->parent != NULL && node->parent->right == node)
+	    node = node->parent;
+	  node = node->parent;
+	}
+      iterator->p = node;
+      return true;
+    }
+  else
+    return false;
+}
+
+static void
+gl_tree_iterator_free (gl_list_iterator_t *iterator)
+{
+}
+
+/* ---------------------- Sorted gl_list_t Data Type ---------------------- */
+
+static gl_list_node_t
+gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
+			   const void *elt)
+{
+  gl_list_node_t node;
+
+  for (node = list->root; node != NULL; )
+    {
+      int cmp = compar (node->value, elt);
+
+      if (cmp < 0)
+	node = node->right;
+      else if (cmp > 0)
+	node = node->left;
+      else /* cmp == 0 */
+	{
+	  /* We have an element equal to ELT.  But we need the leftmost such
+	     element.  */
+	  gl_list_node_t found = node;
+	  node = node->left;
+	  for (; node != NULL; )
+	    {
+	      int cmp2 = compar (node->value, elt);
+
+	      if (cmp2 < 0)
+		node = node->right;
+	      else if (cmp2 > 0)
+		/* The list was not sorted.  */
+		abort ();
+	      else /* cmp2 == 0 */
+		{
+		  found = node;
+		  node = node->left;
+		}
+	    }
+	  return found;
+	}
+    }
+  return NULL;
+}
+
+static size_t
+gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
+			    const void *elt)
+{
+  gl_list_node_t node;
+  size_t position;
+
+  for (node = list->root, position = 0; node != NULL; )
+    {
+      int cmp = compar (node->value, elt);
+
+      if (cmp < 0)
+	{
+	  if (node->left != NULL)
+	    position += node->left->branch_size;
+	  position++;
+	  node = node->right;
+	}
+      else if (cmp > 0)
+	node = node->left;
+      else /* cmp == 0 */
+	{
+	  /* We have an element equal to ELT.  But we need the leftmost such
+	     element.  */
+	  size_t found_position =
+	    position + (node->left != NULL ? node->left->branch_size : 0);
+	  node = node->left;
+	  for (; node != NULL; )
+	    {
+	      int cmp2 = compar (node->value, elt);
+
+	      if (cmp2 < 0)
+		{
+		  if (node->left != NULL)
+		    position += node->left->branch_size;
+		  position++;
+		  node = node->right;
+		}
+	      else if (cmp2 > 0)
+		/* The list was not sorted.  */
+		abort ();
+	      else /* cmp2 == 0 */
+		{
+		  found_position =
+		    position
+		    + (node->left != NULL ? node->left->branch_size : 0);
+		  node = node->left;
+		}
+	    }
+	  return found_position;
+	}
+    }
+  return (size_t)(-1);
+}
+
+static gl_list_node_t
+gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
+			const void *elt)
+{
+  gl_list_node_t node = list->root;
+
+  if (node == NULL)
+    return gl_tree_add_first (list, elt);
+
+  for (;;)
+    {
+      int cmp = compar (node->value, elt);
+
+      if (cmp < 0)
+	{
+	  if (node->right == NULL)
+	    return gl_tree_add_after (list, node, elt);
+	  node = node->right;
+	}
+      else if (cmp > 0)
+	{
+	  if (node->left == NULL)
+	    return gl_tree_add_before (list, node, elt);
+	  node = node->left;
+	}
+      else /* cmp == 0 */
+	return gl_tree_add_before (list, node, elt);
+    }
+}
+
+static bool
+gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
+			   const void *elt)
+{
+  gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
+  if (node != NULL)
+    return gl_tree_remove_node (list, node);
+  else
+    return false;
+}