X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;ds=sidebyside;f=lib%2Fgl_anytree_list2.h;h=fba2845fad0bde7ff6e842e460daaf00b242f4bd;hb=c68c756f05b4d51ffa5a12b391ff996990deee14;hp=00b285bdca3f4e315aa057145e4fc4df8cfa786d;hpb=407400d9367b16a628b57b2d9b8565bb5a08ffae;p=gnulib.git

diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h
index 00b285bdc..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;
 
@@ -601,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)
@@ -656,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)