X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_anytree_list2.h;h=fba2845fad0bde7ff6e842e460daaf00b242f4bd;hb=bbdcfead98c6d3536215c3f0f603e4f92a28d26b;hp=19ecae5f706d2ee1aa1e5196b740dd00491cbc7b;hpb=0a51cf1590113188ff1dc78dc79d2924c262a865;p=gnulib.git

diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h
index 19ecae5f7..fba2845fa 100644
--- a/lib/gl_anytree_list2.h
+++ b/lib/gl_anytree_list2.h
@@ -25,8 +25,7 @@ gl_tree_create_empty (gl_list_implementation_t implementation,
 		      gl_listelement_hashcode_fn hashcode_fn,
 		      bool allow_duplicates)
 {
-  struct gl_list_impl *list =
-    (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
+  struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
 
   list->base.vtable = implementation;
   list->base.equals_fn = equals_fn;
@@ -34,8 +33,7 @@ gl_tree_create_empty (gl_list_implementation_t implementation,
   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));
+  list->table = XCALLOC (list->table_size, gl_hash_entry_t);
 #endif
   list->root = NULL;
 
@@ -164,87 +162,225 @@ gl_tree_set_at (gl_list_t list, size_t position, const void *elt)
 #if !WITH_HASHTABLE
 
 static gl_list_node_t
-gl_tree_search (gl_list_t list, const void *elt)
+gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
+			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++;
-    }
+  if (!(start_index <= end_index
+	&& end_index <= (list->root != NULL ? list->root->branch_size : 0)))
+    /* Invalid arguments.  */
+    abort ();
+  {
+    gl_listelement_equals_fn equals = list->base.equals_fn;
+    /* Iterate across all elements.  */
+    gl_list_node_t node = list->root;
+    iterstack_t stack;
+    iterstack_item_t *stack_ptr = &stack[0];
+    size_t index = 0;
+
+    if (start_index == 0)
+      {
+	/* Consider all elements.  */
+	for (;;)
+	  {
+	    /* Descend on left branch.  */
+	    for (;;)
+	      {
+		if (node == NULL)
+		  break;
+		stack_ptr->node = node;
+		stack_ptr->rightp = 0;
+		node = node->left;
+		stack_ptr++;
+	      }
+	    /* Climb up again.  */
+	    for (;;)
+	      {
+		if (stack_ptr == &stack[0])
+		  return NULL;
+		stack_ptr--;
+		if (!stack_ptr->rightp)
+		  break;
+	      }
+	    node = stack_ptr->node;
+	    /* Test against current element.  */
+	    if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+	      return node;
+	    index++;
+	    if (index >= end_index)
+	      return NULL;
+	    /* Descend on right branch.  */
+	    stack_ptr->rightp = 1;
+	    node = node->right;
+	    stack_ptr++;
+	  }
+      }
+    else
+      {
+	/* Consider only elements at indices >= start_index.
+	   In this case, rightp contains the difference between the start_index
+	   for the parent node and the one for the child node (0 when the child
+	   node is the parent's left child, > 0 when the child is the parent's
+	   right child).  */
+	for (;;)
+	  {
+	    /* Descend on left branch.  */
+	    for (;;)
+	      {
+		if (node == NULL)
+		  break;
+		if (node->branch_size <= start_index)
+		  break;
+		stack_ptr->node = node;
+		stack_ptr->rightp = 0;
+		node = node->left;
+		stack_ptr++;
+	      }
+	    /* Climb up again.  */
+	    for (;;)
+	      {
+		if (stack_ptr == &stack[0])
+		  return NULL;
+		stack_ptr--;
+		if (!stack_ptr->rightp)
+		  break;
+		start_index += stack_ptr->rightp;
+	      }
+	    node = stack_ptr->node;
+	    {
+	      size_t left_branch_size1 =
+		(node->left != NULL ? node->left->branch_size : 0) + 1;
+	      if (start_index < left_branch_size1)
+		{
+		  /* Test against current element.  */
+		  if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+		    return node;
+		  /* Now that we have considered all indices < left_branch_size1,
+		     we can increment start_index.  */
+		  start_index = left_branch_size1;
+		}
+	      index++;
+	      if (index >= end_index)
+		return NULL;
+	      /* Descend on right branch.  */
+	      start_index -= left_branch_size1;
+	      stack_ptr->rightp = left_branch_size1;
+	    }
+	    node = node->right;
+	    stack_ptr++;
+	  }
+      }
+  }
 }
 
 static size_t
-gl_tree_indexof (gl_list_t list, const void *elt)
+gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
+			 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++;
-    }
+  if (!(start_index <= end_index
+	&& end_index <= (list->root != NULL ? list->root->branch_size : 0)))
+    /* Invalid arguments.  */
+    abort ();
+  {
+    gl_listelement_equals_fn equals = list->base.equals_fn;
+    /* Iterate across all elements.  */
+    gl_list_node_t node = list->root;
+    iterstack_t stack;
+    iterstack_item_t *stack_ptr = &stack[0];
+    size_t index = 0;
+
+    if (start_index == 0)
+      {
+	/* Consider all elements.  */
+	for (;;)
+	  {
+	    /* Descend on left branch.  */
+	    for (;;)
+	      {
+		if (node == NULL)
+		  break;
+		stack_ptr->node = node;
+		stack_ptr->rightp = 0;
+		node = node->left;
+		stack_ptr++;
+	      }
+	    /* Climb up again.  */
+	    for (;;)
+	      {
+		if (stack_ptr == &stack[0])
+		  return (size_t)(-1);
+		stack_ptr--;
+		if (!stack_ptr->rightp)
+		  break;
+	      }
+	    node = stack_ptr->node;
+	    /* Test against current element.  */
+	    if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+	      return index;
+	    index++;
+	    if (index >= end_index)
+	      return (size_t)(-1);
+	    /* Descend on right branch.  */
+	    stack_ptr->rightp = 1;
+	    node = node->right;
+	    stack_ptr++;
+	  }
+      }
+    else
+      {
+	/* Consider only elements at indices >= start_index.
+	   In this case, rightp contains the difference between the start_index
+	   for the parent node and the one for the child node (0 when the child
+	   node is the parent's left child, > 0 when the child is the parent's
+	   right child).  */
+	for (;;)
+	  {
+	    /* Descend on left branch.  */
+	    for (;;)
+	      {
+		if (node == NULL)
+		  break;
+		if (node->branch_size <= start_index)
+		  break;
+		stack_ptr->node = node;
+		stack_ptr->rightp = 0;
+		node = node->left;
+		stack_ptr++;
+	      }
+	    /* Climb up again.  */
+	    for (;;)
+	      {
+		if (stack_ptr == &stack[0])
+		  return (size_t)(-1);
+		stack_ptr--;
+		if (!stack_ptr->rightp)
+		  break;
+		start_index += stack_ptr->rightp;
+	      }
+	    node = stack_ptr->node;
+	    {
+	      size_t left_branch_size1 =
+		(node->left != NULL ? node->left->branch_size : 0) + 1;
+	      if (start_index < left_branch_size1)
+		{
+		  /* Test against current element.  */
+		  if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+		    return index;
+		  /* Now that we have considered all indices < left_branch_size1,
+		     we can increment start_index.  */
+		  start_index = left_branch_size1;
+		}
+	      index++;
+	      if (index >= end_index)
+		return (size_t)(-1);
+	      /* Descend on right branch.  */
+	      start_index -= left_branch_size1;
+	      stack_ptr->rightp = left_branch_size1;
+	    }
+	    node = node->right;
+	    stack_ptr++;
+	  }
+      }
+  }
 }
 
 #endif
@@ -278,12 +414,15 @@ gl_tree_remove_at (gl_list_t list, size_t position)
 static bool
 gl_tree_remove (gl_list_t list, const void *elt)
 {
-  gl_list_node_t node = gl_tree_search (list, elt);
+  if (list->root != NULL)
+    {
+      gl_list_node_t node =
+	gl_tree_search_from_to (list, 0, list->root->branch_size, elt);
 
-  if (node != NULL)
-    return gl_tree_remove_node (list, node);
-  else
-    return false;
+      if (node != NULL)
+	return gl_tree_remove_node (list, node);
+    }
+  return false;
 }
 
 #if !WITH_HASHTABLE
@@ -349,6 +488,11 @@ gl_tree_iterator (gl_list_t list)
   result.p = node;
   /* End point is past the rightmost node.  */
   result.q = NULL;
+#ifdef lint
+  result.i = 0;
+  result.j = 0;
+  result.count = 0;
+#endif
 
   return result;
 }
@@ -368,6 +512,11 @@ gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_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);
+#ifdef lint
+  result.i = 0;
+  result.j = 0;
+  result.count = 0;
+#endif
 
   return result;
 }
@@ -450,6 +599,88 @@ gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
   return NULL;
 }
 
+static gl_list_node_t
+gl_tree_sortedlist_search_from_to (gl_list_t list,
+				   gl_listelement_compar_fn compar,
+				   size_t low, size_t high,
+				   const void *elt)
+{
+  gl_list_node_t node;
+
+  if (!(low <= high
+	&& high <= (list->root != NULL ? list->root->branch_size : 0)))
+    /* Invalid arguments.  */
+    abort ();
+
+  for (node = list->root; node != NULL; )
+    {
+      size_t left_branch_size =
+	(node->left != NULL ? node->left->branch_size : 0);
+
+      if (low > left_branch_size)
+	{
+	  low -= left_branch_size + 1;
+	  high -= left_branch_size + 1;
+	  node = node->right;
+	}
+      else if (high <= left_branch_size)
+	node = node->left;
+      else
+	{
+	  /* Here low <= left_branch_size < high.  */
+	  int cmp = compar (node->value, elt);
+
+	  if (cmp < 0)
+	    {
+	      low = 0;
+	      high -= left_branch_size + 1;
+	      node = node->right;
+	    }
+	  else if (cmp > 0)
+	    node = node->left;
+	  else /* cmp == 0 */
+	    {
+	      /* We have an element equal to ELT.  But we need the leftmost
+		 such element.  */
+	      gl_list_node_t found = node;
+	      node = node->left;
+	      for (; node != NULL; )
+		{
+		  size_t left_branch_size2 =
+		    (node->left != NULL ? node->left->branch_size : 0);
+
+		  if (low > left_branch_size2)
+		    {
+		      low -= left_branch_size2 + 1;
+		      node = node->right;
+		    }
+		  else
+		    {
+		      /* Here low <= left_branch_size2.  */
+		      int cmp2 = compar (node->value, elt);
+
+		      if (cmp2 < 0)
+			{
+			  low = 0;
+			  node = node->right;
+			}
+		      else if (cmp2 > 0)
+			/* The list was not sorted.  */
+			abort ();
+		      else /* cmp2 == 0 */
+			{
+			  found = node;
+			  node = node->left;
+			}
+		    }
+		}
+	      return found;
+	    }
+	}
+    }
+  return NULL;
+}
+
 static size_t
 gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 			    const void *elt)
@@ -505,6 +736,92 @@ gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
   return (size_t)(-1);
 }
 
+static size_t
+gl_tree_sortedlist_indexof_from_to (gl_list_t list,
+				    gl_listelement_compar_fn compar,
+				    size_t low, size_t high,
+				    const void *elt)
+{
+  gl_list_node_t node;
+  size_t position;
+
+  if (!(low <= high
+	&& high <= (list->root != NULL ? list->root->branch_size : 0)))
+    /* Invalid arguments.  */
+    abort ();
+
+  for (node = list->root, position = 0; node != NULL; )
+    {
+      size_t left_branch_size =
+	(node->left != NULL ? node->left->branch_size : 0);
+
+      if (low > left_branch_size)
+	{
+	  low -= left_branch_size + 1;
+	  high -= left_branch_size + 1;
+	  position += left_branch_size + 1;
+	  node = node->right;
+	}
+      else if (high <= left_branch_size)
+	node = node->left;
+      else
+	{
+	  /* Here low <= left_branch_size < high.  */
+	  int cmp = compar (node->value, elt);
+
+	  if (cmp < 0)
+	    {
+	      low = 0;
+	      high -= left_branch_size + 1;
+	      position += left_branch_size + 1;
+	      node = node->right;
+	    }
+	  else if (cmp > 0)
+	    node = node->left;
+	  else /* cmp == 0 */
+	    {
+	      /* We have an element equal to ELT.  But we need the leftmost
+		 such element.  */
+	      size_t found_position =
+		position + (node->left != NULL ? node->left->branch_size : 0);
+	      node = node->left;
+	      for (; node != NULL; )
+		{
+		  size_t left_branch_size2 =
+		    (node->left != NULL ? node->left->branch_size : 0);
+
+		  if (low > left_branch_size2)
+		    {
+		      low -= left_branch_size2 + 1;
+		      node = node->right;
+		    }
+		  else
+		    {
+		      /* Here low <= left_branch_size2.  */
+		      int cmp2 = compar (node->value, elt);
+
+		      if (cmp2 < 0)
+			{
+			  position += left_branch_size2 + 1;
+			  node = node->right;
+			}
+		      else if (cmp2 > 0)
+			/* The list was not sorted.  */
+			abort ();
+		      else /* cmp2 == 0 */
+			{
+			  found_position = position + left_branch_size2;
+			  node = node->left;
+			}
+		    }
+		}
+	      return found_position;
+	    }
+	}
+    }
+  return (size_t)(-1);
+}
+
 static gl_list_node_t
 gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
 			const void *elt)