changeset 7410:9704ff2cbdfe

Add bounded list search operations.
author Bruno Haible <bruno@clisp.org>
date Fri, 06 Oct 2006 12:06:07 +0000
parents 830788a4cbd4
children 67235cf9199a
files lib/ChangeLog lib/gl_anylinked_list2.h lib/gl_anytree_list2.h lib/gl_array_list.c lib/gl_avltree_list.c lib/gl_avltreehash_list.c lib/gl_carray_list.c lib/gl_linked_list.c lib/gl_linkedhash_list.c lib/gl_list.c lib/gl_list.h lib/gl_rbtree_list.c lib/gl_rbtreehash_list.c
diffstat 13 files changed, 442 insertions(+), 18 deletions(-) [+]
line wrap: on
line diff
--- a/lib/ChangeLog
+++ b/lib/ChangeLog
@@ -1,3 +1,32 @@
+2006-10-03  Bruno Haible
+
+	* gl_list.h (gl_sortedlist_search_from_to,
+	gl_sortedlist_indexof_from_to): New declarations.
+	(gl_list_implementation): New fields sortedlist_search_from_to,
+	sortedlist_indexof_from_to.
+	(gl_sortedlist_search_from_to, gl_sortedlist_indexof_from_to): New
+	inline functions.
+	* gl_list.c (gl_sortedlist_search_from_to,
+	gl_sortedlist_indexof_from_to): New functions.
+	* gl_array_list.c (gl_array_sortedlist_indexof_from_to): New function.
+	(gl_array_sortedlist_indexof, gl_array_sortedlist_search): Use it.
+	(gl_array_sortedlist_search_from_to): New function.
+	(gl_array_list_implementation): Update.
+	* gl_carray_list.c (gl_carray_sortedlist_indexof_from_to): New function.
+	(gl_carray_sortedlist_indexof, gl_carray_sortedlist_search): Use it.
+	(gl_carray_sortedlist_search_from_to): New function.
+	(gl_carray_list_implementation): Update.
+	* gl_anylinked_list2.h (gl_linked_sortedlist_search_from_to,
+	gl_linked_sortedlist_indexof_from_to): New functions.
+	* gl_linked_list.c (gl_linked_list_implementation): Update.
+	* gl_linkedhash_list.c (gl_linkedhash_list_implementation): Update.
+	* gl_anytree_list2.h (gl_tree_sortedlist_search_from_to,
+	gl_tree_sortedlist_indexof_from_to): New functions.
+	* gl_avltree_list.c (gl_avltree_list_implementation): Update.
+	* gl_avltreehash_list.c (gl_avltreehash_list_implementation): Update.
+	* gl_rbtree_list.c (gl_rbtree_list_implementation): Update.
+	* gl_rbtreehash_list.c (gl_avltreehash_list_implementation): Update.
+
 2006-10-05  Paul Eggert  <eggert@cs.ucla.edu>
 
 	Fix some Darwin-7.9.0 porting problems reported by Bruno Haible in
--- a/lib/gl_anylinked_list2.h
+++ b/lib/gl_anylinked_list2.h
@@ -906,6 +906,54 @@
   return NULL;
 }
 
+static gl_list_node_t
+gl_linked_sortedlist_search_from_to (gl_list_t list,
+				     gl_listelement_compar_fn compar,
+				     size_t low, size_t high,
+				     const void *elt)
+{
+  size_t count = list->count;
+
+  if (!(low <= high && high <= list->count))
+    /* Invalid arguments.  */
+    abort ();
+
+  high -= low;
+  if (high > 0)
+    {
+      /* Here we know low < count.  */
+      size_t position = low;
+      gl_list_node_t node;
+
+      if (position <= ((count - 1) / 2))
+	{
+	  node = list->root.next;
+	  for (; position > 0; position--)
+	    node = node->next;
+	}
+      else
+	{
+	  position = count - 1 - position;
+	  node = list->root.prev;
+	  for (; position > 0; position--)
+	    node = node->prev;
+	}
+
+      do
+	{
+	  int cmp = compar (node->value, elt);
+
+	  if (cmp > 0)
+	    break;
+	  if (cmp == 0)
+	    return node;
+	  node = node->next;
+	}
+      while (--high > 0);
+    }
+  return NULL;
+}
+
 static size_t
 gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 			      const void *elt)
@@ -927,6 +975,56 @@
   return (size_t)(-1);
 }
 
+static size_t
+gl_linked_sortedlist_indexof_from_to (gl_list_t list,
+				      gl_listelement_compar_fn compar,
+				      size_t low, size_t high,
+				      const void *elt)
+{
+  size_t count = list->count;
+
+  if (!(low <= high && high <= list->count))
+    /* Invalid arguments.  */
+    abort ();
+
+  high -= low;
+  if (high > 0)
+    {
+      /* Here we know low < count.  */
+      size_t index = low;
+      size_t position = low;
+      gl_list_node_t node;
+
+      if (position <= ((count - 1) / 2))
+	{
+	  node = list->root.next;
+	  for (; position > 0; position--)
+	    node = node->next;
+	}
+      else
+	{
+	  position = count - 1 - position;
+	  node = list->root.prev;
+	  for (; position > 0; position--)
+	    node = node->prev;
+	}
+
+      do
+	{
+	  int cmp = compar (node->value, elt);
+
+	  if (cmp > 0)
+	    break;
+	  if (cmp == 0)
+	    return index;
+	  node = node->next;
+	  index++;
+	}
+      while (--high > 0);
+    }
+  return (size_t)(-1);
+}
+
 static gl_list_node_t
 gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
 			  const void *elt)
--- a/lib/gl_anytree_list2.h
+++ b/lib/gl_anytree_list2.h
@@ -601,6 +601,88 @@
   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 +738,92 @@
   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)
--- a/lib/gl_array_list.c
+++ b/lib/gl_array_list.c
@@ -466,16 +466,16 @@
 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 
 static size_t
-gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
-			     const void *elt)
+gl_array_sortedlist_indexof_from_to (gl_list_t list,
+				     gl_listelement_compar_fn compar,
+				     size_t low, size_t high,
+				     const void *elt)
 {
-  size_t count = list->count;
-
-  if (count > 0)
+  if (!(low <= high && high <= list->count))
+    /* Invalid arguments.  */
+    abort ();
+  if (low < high)
     {
-      size_t low = 0;
-      size_t high = count;
-
       /* At each loop iteration, low < high; for indices < low the values
 	 are smaller than ELT; for indices >= high the values are greater
 	 than ELT.  So, if the element occurs in the list, it is at
@@ -524,11 +524,31 @@
   return (size_t)(-1);
 }
 
+static size_t
+gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
+			     const void *elt)
+{
+  return gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count,
+					      elt);
+}
+
+static gl_list_node_t
+gl_array_sortedlist_search_from_to (gl_list_t list,
+				    gl_listelement_compar_fn compar,
+				    size_t low, size_t high,
+				    const void *elt)
+{
+  size_t index =
+    gl_array_sortedlist_indexof_from_to (list, compar, low, high, elt);
+  return INDEX_TO_NODE (index);
+}
+
 static gl_list_node_t
 gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 			    const void *elt)
 {
-  size_t index = gl_array_sortedlist_indexof (list, compar, elt);
+  size_t index =
+    gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
   return INDEX_TO_NODE (index);
 }
 
@@ -598,7 +618,9 @@
     gl_array_iterator_next,
     gl_array_iterator_free,
     gl_array_sortedlist_search,
+    gl_array_sortedlist_search_from_to,
     gl_array_sortedlist_indexof,
+    gl_array_sortedlist_indexof_from_to,
     gl_array_sortedlist_add,
     gl_array_sortedlist_remove
   };
--- a/lib/gl_avltree_list.c
+++ b/lib/gl_avltree_list.c
@@ -91,7 +91,9 @@
     gl_tree_iterator_next,
     gl_tree_iterator_free,
     gl_tree_sortedlist_search,
+    gl_tree_sortedlist_search_from_to,
     gl_tree_sortedlist_indexof,
+    gl_tree_sortedlist_indexof_from_to,
     gl_tree_sortedlist_add,
     gl_tree_sortedlist_remove
   };
--- a/lib/gl_avltreehash_list.c
+++ b/lib/gl_avltreehash_list.c
@@ -120,7 +120,9 @@
     gl_tree_iterator_next,
     gl_tree_iterator_free,
     gl_tree_sortedlist_search,
+    gl_tree_sortedlist_search_from_to,
     gl_tree_sortedlist_indexof,
+    gl_tree_sortedlist_indexof_from_to,
     gl_tree_sortedlist_add,
     gl_tree_sortedlist_remove
   };
--- a/lib/gl_carray_list.c
+++ b/lib/gl_carray_list.c
@@ -610,16 +610,16 @@
 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 
 static size_t
-gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
-			      const void *elt)
+gl_carray_sortedlist_indexof_from_to (gl_list_t list,
+				      gl_listelement_compar_fn compar,
+				      size_t low, size_t high,
+				      const void *elt)
 {
-  size_t count = list->count;
-
-  if (count > 0)
+  if (!(low <= high && high <= list->count))
+    /* Invalid arguments.  */
+    abort ();
+  if (low < high)
     {
-      size_t low = 0;
-      size_t high = count;
-
       /* At each loop iteration, low < high; for indices < low the values
 	 are smaller than ELT; for indices >= high the values are greater
 	 than ELT.  So, if the element occurs in the list, it is at
@@ -682,11 +682,31 @@
   return (size_t)(-1);
 }
 
+static size_t
+gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
+			      const void *elt)
+{
+  return gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count,
+					       elt);
+}
+
+static gl_list_node_t
+gl_carray_sortedlist_search_from_to (gl_list_t list,
+				     gl_listelement_compar_fn compar,
+				     size_t low, size_t high,
+				     const void *elt)
+{
+  size_t index =
+    gl_carray_sortedlist_indexof_from_to (list, compar, low, high, elt);
+  return INDEX_TO_NODE (index);
+}
+
 static gl_list_node_t
 gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 			     const void *elt)
 {
-  size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
+  size_t index =
+    gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
   return INDEX_TO_NODE (index);
 }
 
@@ -763,7 +783,9 @@
     gl_carray_iterator_next,
     gl_carray_iterator_free,
     gl_carray_sortedlist_search,
+    gl_carray_sortedlist_search_from_to,
     gl_carray_sortedlist_indexof,
+    gl_carray_sortedlist_indexof_from_to,
     gl_carray_sortedlist_add,
     gl_carray_sortedlist_remove
   };
--- a/lib/gl_linked_list.c
+++ b/lib/gl_linked_list.c
@@ -58,7 +58,9 @@
     gl_linked_iterator_next,
     gl_linked_iterator_free,
     gl_linked_sortedlist_search,
+    gl_linked_sortedlist_search_from_to,
     gl_linked_sortedlist_indexof,
+    gl_linked_sortedlist_indexof_from_to,
     gl_linked_sortedlist_add,
     gl_linked_sortedlist_remove
   };
--- a/lib/gl_linkedhash_list.c
+++ b/lib/gl_linkedhash_list.c
@@ -115,7 +115,9 @@
     gl_linked_iterator_next,
     gl_linked_iterator_free,
     gl_linked_sortedlist_search,
+    gl_linked_sortedlist_search_from_to,
     gl_linked_sortedlist_indexof,
+    gl_linked_sortedlist_indexof_from_to,
     gl_linked_sortedlist_add,
     gl_linked_sortedlist_remove
   };
--- a/lib/gl_list.c
+++ b/lib/gl_list.c
@@ -232,6 +232,14 @@
 	 ->sortedlist_search (list, compar, elt);
 }
 
+gl_list_node_t
+gl_sortedlist_search_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
+{
+  return ((const struct gl_list_impl_base *) list)->vtable
+	 ->sortedlist_search_from_to (list, compar, start_index, end_index,
+				      elt);
+}
+
 size_t
 gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 {
@@ -239,6 +247,14 @@
 	 ->sortedlist_indexof (list, compar, elt);
 }
 
+size_t
+gl_sortedlist_indexof_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
+{
+  return ((const struct gl_list_impl_base *) list)->vtable
+	 ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
+				       elt);
+}
+
 gl_list_node_t
 gl_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
 {
--- a/lib/gl_list.h
+++ b/lib/gl_list.h
@@ -85,7 +85,9 @@
    gl_list_iterator_from_to    O(1)     O(n)   O(log n)    O(n)       O(log n)
    gl_list_iterator_next       O(1)     O(1)   O(log n)    O(1)       O(log n)
    gl_sortedlist_search      O(log n)   O(n)   O(log n)    O(n)       O(log n)
+   gl_sortedlist_search_from O(log n)   O(n)   O(log n)    O(n)       O(log n)
    gl_sortedlist_indexof     O(log n)   O(n)   O(log n)    O(n)       O(log n)
+   gl_sortedlist_indexof_fro O(log n)   O(n)   O(log n)    O(n)       O(log n)
    gl_sortedlist_add           O(n)     O(n)   O(log n)    O(n)    O((log n)²)/O(log n)
    gl_sortedlist_remove        O(n)     O(n)   O(log n)    O(n)    O((log n)²)/O(log n)
  */
@@ -303,6 +305,20 @@
 
 /* Search whether an element is already in the list.
    The list is assumed to be sorted with COMPAR.
+   Only list elements with indices >= START_INDEX and < END_INDEX are
+   considered; the implementation uses these bounds to minimize the number
+   of COMPAR invocations.
+   Return its node if found, or NULL if not present in the list.
+   If the list contains several copies of ELT, the node of the leftmost one is
+   returned.  */
+extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list,
+						    gl_listelement_compar_fn compar,
+						    size_t start_index,
+						    size_t end_index,
+						    const void *elt);
+
+/* Search whether an element is already in the list.
+   The list is assumed to be sorted with COMPAR.
    Return its position if found, or (size_t)(-1) if not present in the list.
    If the list contains several copies of ELT, the position of the leftmost one
    is returned.  */
@@ -310,6 +326,20 @@
 				     gl_listelement_compar_fn compar,
 				     const void *elt);
 
+/* Search whether an element is already in the list.
+   The list is assumed to be sorted with COMPAR.
+   Only list elements with indices >= START_INDEX and < END_INDEX are
+   considered; the implementation uses these bounds to minimize the number
+   of COMPAR invocations.
+   Return its position if found, or (size_t)(-1) if not present in the list.
+   If the list contains several copies of ELT, the position of the leftmost one
+   is returned.  */
+extern size_t gl_sortedlist_indexof_from_to (gl_list_t list,
+					     gl_listelement_compar_fn compar,
+					     size_t start_index,
+					     size_t end_index,
+					     const void *elt);
+
 /* Add an element at the appropriate position in the list.
    The list is assumed to be sorted with COMPAR.
    Return its node.  */
@@ -374,9 +404,18 @@
   gl_list_node_t (*sortedlist_search) (gl_list_t list,
 				       gl_listelement_compar_fn compar,
 				       const void *elt);
+  gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list,
+					       gl_listelement_compar_fn compar,
+					       size_t start_index,
+					       size_t end_index,
+					       const void *elt);
   size_t (*sortedlist_indexof) (gl_list_t list,
 				gl_listelement_compar_fn compar,
 				const void *elt);
+  size_t (*sortedlist_indexof_from_to) (gl_list_t list,
+					gl_listelement_compar_fn compar,
+					size_t start_index, size_t end_index,
+					const void *elt);
   gl_list_node_t (*sortedlist_add) (gl_list_t list,
 				    gl_listelement_compar_fn compar,
 				    const void *elt);
@@ -634,6 +673,15 @@
 	 ->sortedlist_search (list, compar, elt);
 }
 
+# define gl_sortedlist_search_from_to gl_sortedlist_search_from_to_inline
+static inline gl_list_node_t
+gl_sortedlist_search_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
+{
+  return ((const struct gl_list_impl_base *) list)->vtable
+	 ->sortedlist_search_from_to (list, compar, start_index, end_index,
+				      elt);
+}
+
 # define gl_sortedlist_indexof gl_sortedlist_indexof_inline
 static inline size_t
 gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
@@ -642,6 +690,15 @@
 	 ->sortedlist_indexof (list, compar, elt);
 }
 
+# define gl_sortedlist_indexof_from_to gl_sortedlist_indexof_from_to_inline
+static inline size_t
+gl_sortedlist_indexof_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
+{
+  return ((const struct gl_list_impl_base *) list)->vtable
+	 ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
+				       elt);
+}
+
 # define gl_sortedlist_add gl_sortedlist_add_inline
 static inline gl_list_node_t
 gl_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
--- a/lib/gl_rbtree_list.c
+++ b/lib/gl_rbtree_list.c
@@ -92,7 +92,9 @@
     gl_tree_iterator_next,
     gl_tree_iterator_free,
     gl_tree_sortedlist_search,
+    gl_tree_sortedlist_search_from_to,
     gl_tree_sortedlist_indexof,
+    gl_tree_sortedlist_indexof_from_to,
     gl_tree_sortedlist_add,
     gl_tree_sortedlist_remove
   };
--- a/lib/gl_rbtreehash_list.c
+++ b/lib/gl_rbtreehash_list.c
@@ -121,7 +121,9 @@
     gl_tree_iterator_next,
     gl_tree_iterator_free,
     gl_tree_sortedlist_search,
+    gl_tree_sortedlist_search_from_to,
     gl_tree_sortedlist_indexof,
+    gl_tree_sortedlist_indexof_from_to,
     gl_tree_sortedlist_add,
     gl_tree_sortedlist_remove
   };