--- a/lib/ChangeLog
+++ b/lib/ChangeLog
@@ -1,3 +1,51 @@
+2006-10-03  Bruno Haible  <bruno@clisp.org>
+
+	* gl_list.h (gl_list_search_from, gl_list_search_from_to,
+	gl_list_indexof_from, gl_list_indexof_from_to): New declarations.
+	(struct gl_list_implementation): Add fields search_from_to,
+	indexof_from_to. Remove fields search, indexof.
+	(gl_list_search): Use the search_from_to method.
+	(gl_list_search_from, gl_list_search_from_to): New functions.
+	(gl_list_indexof): Use the indexof_from_to method.
+	(gl_list_indexof_from, gl_list_indexof_from_to): New functions.
+	* gl_list.c (gl_list_search): Use the search_from_to method.
+	(gl_list_search_from, gl_list_search_from_to): New functions.
+	(gl_list_indexof): Use the indexof_from_to method.
+	(gl_list_indexof_from, gl_list_indexof_from_to): New functions.
+	* gl_array_list.c (gl_array_indexof_from_to): Renamed from
+	gl_array_indexof. Add start_index, end_index arguments.
+	(gl_array_search_from_to): Renamed from gl_array_search. Add
+	start_index, end_index arguments.
+	(gl_array_remove, gl_array_list_implementation): Update.
+	* gl_carray_list.c (gl_carray_indexof_from_to): Renamed from
+	gl_carray_indexof. Add start_index, end_index arguments.
+	(gl_carray_search_from_to): Renamed from gl_carray_search. Add
+	start_index, end_index arguments.
+	(gl_carray_remove, gl_carray_list_implementation): Update.
+	* gl_anylinked_list2.h (gl_linked_search_from_to): Renamed from
+	gl_linked_search. Add start_index, end_index arguments.
+	(gl_linked_indexof_from_to): Renamed from gl_linked_indexof. Add
+	start_index, end_index arguments.
+	(gl_linked_remove): Update.
+	* gl_linked_list.c (gl_linked_list_implementation): Update.
+	* gl_linkedhash_list.c (gl_linkedhash_list_implementation): Update.
+	* gl_anytree_list1.h (iterstack_item_t): Change type of 'rightp' field
+	to 'size_t'.
+	* gl_anytree_list2.h (gl_tree_search_from_to): Renamed from
+	gl_tree_search. Add start_index, end_index arguments.
+	(gl_tree_indexof_from_to): Renamed from gl_tree_indexof. Add
+	start_index, end_index arguments.
+	(gl_tree_remove): Update.
+	* gl_avltree_list.c (gl_avltree_list_implementation): Update.
+	* gl_rbtree_list.c (gl_rbtree_list_implementation): Update.
+	* gl_anytreehash_list1.h (compare_position_threshold): New function.
+	* gl_anytreehash_list2.h (gl_tree_search_from_to): Renamed from
+	gl_tree_search. Add start_index, end_index arguments.
+	(gl_tree_indexof_from_to): Renamed from gl_tree_indexof. Add
+	start_index, end_index arguments.
+	* gl_avltreehash_list.c (gl_avltreehash_list_implementation): Update.
+	* gl_rbtreehash_list.c (gl_rbtreehash_list_implementation): Update.
+
 2006-10-04  Bruno Haible  <bruno@clisp.org>
 
 	* fatal-signal.c (fatal_signals) [WOE32]: Add the SIGBREAK signal.

--- a/lib/gl_anylinked_list2.h
+++ b/lib/gl_anylinked_list2.h
@@ -215,196 +215,283 @@
 }
 
 static gl_list_node_t
-gl_linked_search (gl_list_t list, const void *elt)
+gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
+			  const void *elt)
 {
+  size_t count = list->count;
+
+  if (!(start_index <= end_index && end_index <= count))
+    /* Invalid arguments.  */
+    abort ();
+  {
 #if WITH_HASHTABLE
-  size_t hashcode =
-    (list->base.hashcode_fn != NULL
-     ? list->base.hashcode_fn (elt)
-     : (size_t)(uintptr_t) elt);
-  size_t index = hashcode % list->table_size;
-  gl_listelement_equals_fn equals = list->base.equals_fn;
+    size_t hashcode =
+      (list->base.hashcode_fn != NULL
+       ? list->base.hashcode_fn (elt)
+       : (size_t)(uintptr_t) elt);
+    size_t index = hashcode % list->table_size;
+    gl_listelement_equals_fn equals = list->base.equals_fn;
 
-  if (!list->base.allow_duplicates)
-    {
-      /* Look for the first match in the hash bucket.  */
-      gl_list_node_t node;
+    if (!list->base.allow_duplicates)
+      {
+	/* Look for the first match in the hash bucket.  */
+	gl_list_node_t found = NULL;
+	gl_list_node_t node;
 
-      for (node = (gl_list_node_t) list->table[index];
-	   node != NULL;
-	   node = (gl_list_node_t) node->h.hash_next)
-	if (node->h.hashcode == hashcode
-	    && (equals != NULL
-		? equals (elt, node->value)
-		: elt == node->value))
-	  return node;
-      return NULL;
-    }
-  else
-    {
-      /* Look whether there is more than one match in the hash bucket.  */
-      bool multiple_matches = false;
-      gl_list_node_t first_match = NULL;
-      gl_list_node_t node;
-
-      for (node = (gl_list_node_t) list->table[index];
-	   node != NULL;
-	   node = (gl_list_node_t) node->h.hash_next)
-	if (node->h.hashcode == hashcode
-	    && (equals != NULL
-		? equals (elt, node->value)
-		: elt == node->value))
+	for (node = (gl_list_node_t) list->table[index];
+	     node != NULL;
+	     node = (gl_list_node_t) node->h.hash_next)
+	  if (node->h.hashcode == hashcode
+	      && (equals != NULL
+		  ? equals (elt, node->value)
+		  : elt == node->value))
+	    {
+	      found = node;
+	      break;
+	    }
+	if (start_index > 0)
+	  /* Look whether found's index is < start_index.  */
+	  for (node = list->root.next; ; node = node->next)
+	    {
+	      if (node == found)
+		return NULL;
+	      if (--start_index == 0)
+		break;
+	    }
+	if (end_index < count)
+	  /* Look whether found's index is >= end_index.  */
 	  {
-	    if (first_match == NULL)
-	      first_match = node;
-	    else
+	    end_index = count - end_index;
+	    for (node = list->root.prev; ; node = node->prev)
 	      {
-		multiple_matches = true;
-		break;
+		if (node == found)
+		  return NULL;
+		if (--end_index == 0)
+		  break;
 	      }
 	  }
-      if (!multiple_matches)
-	return first_match;
-      else
-	{
-	  /* We need the match with the smallest index.  But we don't have
-	     a fast mapping node -> index.  So we have to walk the list.  */
-	  for (node = list->root.next; node != &list->root; node = node->next)
-	    if (node->h.hashcode == hashcode
-		&& (equals != NULL
-		    ? equals (elt, node->value)
-		    : elt == node->value))
-	      return node;
-	  /* We know there are at least two matches.  */
-	  abort ();
-	}
-    }
+	return found;
+      }
+    else
+      {
+	/* Look whether there is more than one match in the hash bucket.  */
+	bool multiple_matches = false;
+	gl_list_node_t first_match = NULL;
+	gl_list_node_t node;
+
+	for (node = (gl_list_node_t) list->table[index];
+	     node != NULL;
+	     node = (gl_list_node_t) node->h.hash_next)
+	  if (node->h.hashcode == hashcode
+	      && (equals != NULL
+		  ? equals (elt, node->value)
+		  : elt == node->value))
+	    {
+	      if (first_match == NULL)
+		first_match = node;
+	      else
+		{
+		  multiple_matches = true;
+		  break;
+		}
+	    }
+	if (multiple_matches)
+	  {
+	    /* We need the match with the smallest index.  But we don't have
+	       a fast mapping node -> index.  So we have to walk the list.  */
+	    end_index -= start_index;
+	    node = list->root.next;
+	    for (; start_index > 0; start_index--)
+	      node = node->next;
+
+	    for (;
+		 end_index > 0;
+		 node = node->next, end_index--)
+	      if (node->h.hashcode == hashcode
+		  && (equals != NULL
+		      ? equals (elt, node->value)
+		      : elt == node->value))
+		return node;
+	    /* The matches must have all been at indices < start_index or
+	       >= end_index.  */
+	    return NULL;
+	  }
+	else
+	  {
+	    if (start_index > 0)
+	      /* Look whether first_match's index is < start_index.  */
+	      for (node = list->root.next; node != &list->root; node = node->next)
+		{
+		  if (node == first_match)
+		    return NULL;
+		  if (--start_index == 0)
+		    break;
+		}
+	    if (end_index < list->count)
+	      /* Look whether first_match's index is >= end_index.  */
+	      {
+		end_index = list->count - end_index;
+		for (node = list->root.prev; ; node = node->prev)
+		  {
+		    if (node == first_match)
+		      return NULL;
+		    if (--end_index == 0)
+		      break;
+		  }
+	      }
+	    return first_match;
+	  }
+      }
 #else
-  gl_listelement_equals_fn equals = list->base.equals_fn;
-  gl_list_node_t node;
+    gl_listelement_equals_fn equals = list->base.equals_fn;
+    gl_list_node_t node = list->root.next;
+
+    end_index -= start_index;
+    for (; start_index > 0; start_index--)
+      node = node->next;
 
-  if (equals != NULL)
-    {
-      for (node = list->root.next; node != &list->root; node = node->next)
-	if (equals (elt, node->value))
-	  return node;
-    }
-  else
-    {
-      for (node = list->root.next; node != &list->root; node = node->next)
-	if (elt == node->value)
-	  return node;
-    }
-  return NULL;
+    if (equals != NULL)
+      {
+	for (; end_index > 0; node = node->next, end_index--)
+	  if (equals (elt, node->value))
+	    return node;
+      }
+    else
+      {
+	for (; end_index > 0; node = node->next, end_index--)
+	  if (elt == node->value)
+	    return node;
+      }
+    return NULL;
 #endif
+  }
 }
 
 static size_t
-gl_linked_indexof (gl_list_t list, const void *elt)
+gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
+			   const void *elt)
 {
+  size_t count = list->count;
+
+  if (!(start_index <= end_index && end_index <= count))
+    /* Invalid arguments.  */
+    abort ();
+  {
 #if WITH_HASHTABLE
-  /* Here the hash table doesn't help much.  It only allows us to minimize
-     the number of equals() calls, by looking up first the node and then
-     its index.  */
-  size_t hashcode =
-    (list->base.hashcode_fn != NULL
-     ? list->base.hashcode_fn (elt)
-     : (size_t)(uintptr_t) elt);
-  size_t index = hashcode % list->table_size;
-  gl_listelement_equals_fn equals = list->base.equals_fn;
-  gl_list_node_t node;
+    /* Here the hash table doesn't help much.  It only allows us to minimize
+       the number of equals() calls, by looking up first the node and then
+       its index.  */
+    size_t hashcode =
+      (list->base.hashcode_fn != NULL
+       ? list->base.hashcode_fn (elt)
+       : (size_t)(uintptr_t) elt);
+    size_t index = hashcode % list->table_size;
+    gl_listelement_equals_fn equals = list->base.equals_fn;
+    gl_list_node_t node;
 
-  /* First step: Look up the node.  */
-  if (!list->base.allow_duplicates)
-    {
-      /* Look for the first match in the hash bucket.  */
-      for (node = (gl_list_node_t) list->table[index];
-	   node != NULL;
-	   node = (gl_list_node_t) node->h.hash_next)
-	if (node->h.hashcode == hashcode
-	    && (equals != NULL
-		? equals (elt, node->value)
-		: elt == node->value))
-	  break;
-    }
-  else
-    {
-      /* Look whether there is more than one match in the hash bucket.  */
-      bool multiple_matches = false;
-      gl_list_node_t first_match = NULL;
+    /* First step: Look up the node.  */
+    if (!list->base.allow_duplicates)
+      {
+	/* Look for the first match in the hash bucket.  */
+	for (node = (gl_list_node_t) list->table[index];
+	     node != NULL;
+	     node = (gl_list_node_t) node->h.hash_next)
+	  if (node->h.hashcode == hashcode
+	      && (equals != NULL
+		  ? equals (elt, node->value)
+		  : elt == node->value))
+	    break;
+      }
+    else
+      {
+	/* Look whether there is more than one match in the hash bucket.  */
+	bool multiple_matches = false;
+	gl_list_node_t first_match = NULL;
 
-      for (node = (gl_list_node_t) list->table[index];
-	   node != NULL;
-	   node = (gl_list_node_t) node->h.hash_next)
-	if (node->h.hashcode == hashcode
-	    && (equals != NULL
-		? equals (elt, node->value)
-		: elt == node->value))
+	for (node = (gl_list_node_t) list->table[index];
+	     node != NULL;
+	     node = (gl_list_node_t) node->h.hash_next)
+	  if (node->h.hashcode == hashcode
+	      && (equals != NULL
+		  ? equals (elt, node->value)
+		  : elt == node->value))
+	    {
+	      if (first_match == NULL)
+		first_match = node;
+	      else
+		{
+		  multiple_matches = true;
+		  break;
+		}
+	    }
+	if (multiple_matches)
 	  {
-	    if (first_match == NULL)
-	      first_match = node;
-	    else
-	      {
-		multiple_matches = true;
-		break;
-	      }
+	    /* We need the match with the smallest index.  But we don't have
+	       a fast mapping node -> index.  So we have to walk the list.  */
+	    size_t index;
+
+	    index = start_index;
+	    node = list->root.next;
+	    for (; start_index > 0; start_index--)
+	      node = node->next;
+
+	    for (;
+		 index < end_index;
+		 node = node->next, index++)
+	      if (node->h.hashcode == hashcode
+		  && (equals != NULL
+		      ? equals (elt, node->value)
+		      : elt == node->value))
+		return index;
+	    /* The matches must have all been at indices < start_index or
+	       >= end_index.  */
+	    return (size_t)(-1);
 	  }
-      if (multiple_matches)
-	{
-	  /* We need the match with the smallest index.  But we don't have
-	     a fast mapping node -> index.  So we have to walk the list.  */
-	  size_t index;
+	node = first_match;
+      }
+
+    /* Second step: Look up the index of the node.  */
+    if (node == NULL)
+      return (size_t)(-1);
+    else
+      {
+	size_t index = 0;
 
-	  for (node = list->root.next, index = 0;
-	       node != &list->root;
-	       node = node->next, index++)
-	    if (node->h.hashcode == hashcode
-		&& (equals != NULL
-		    ? equals (elt, node->value)
-		    : elt == node->value))
-	      return index;
-	  /* We know there are at least two matches.  */
-	  abort ();
-	}
-      node = first_match;
-    }
+	for (; node->prev != &list->root; node = node->prev)
+	  index++;
 
-  /* Second step: Look up the index of the node.  */
-  if (node == NULL)
-    return (size_t)(-1);
-  else
-    {
-      size_t index = 0;
+	if (index >= start_index && index < end_index)
+	  return index;
+	else
+	  return (size_t)(-1);
+      }
+#else
+    gl_listelement_equals_fn equals = list->base.equals_fn;
+    size_t index = start_index;
+    gl_list_node_t node = list->root.next;
 
-      for (; node->prev != &list->root; node = node->prev)
-	index++;
-
-      return index;
-    }
-#else
-  gl_listelement_equals_fn equals = list->base.equals_fn;
-  gl_list_node_t node;
+    for (; start_index > 0; start_index--)
+      node = node->next;
 
-  if (equals != NULL)
-    {
-      size_t index;
-      for (node = list->root.next, index = 0;
-	   node != &list->root;
-	   node = node->next, index++)
-	if (equals (elt, node->value))
-	  return index;
-    }
-  else
-    {
-      size_t index;
-      for (node = list->root.next, index = 0;
-	   node != &list->root;
-	   node = node->next, index++)
-	if (elt == node->value)
-	  return index;
-    }
-  return (size_t)(-1);
+    if (equals != NULL)
+      {
+	for (;
+	     index < end_index;
+	     node = node->next, index++)
+	  if (equals (elt, node->value))
+	    return index;
+      }
+    else
+      {
+	for (;
+	     index < end_index;
+	     node = node->next, index++)
+	  if (elt == node->value)
+	    return index;
+      }
+    return (size_t)(-1);
 #endif
+  }
 }
 
 static gl_list_node_t
@@ -661,7 +748,7 @@
 static bool
 gl_linked_remove (gl_list_t list, const void *elt)
 {
-  gl_list_node_t node = gl_linked_search (list, elt);
+  gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt);
 
   if (node != NULL)
     return gl_linked_remove_node (list, node);

--- a/lib/gl_anytree_list1.h
+++ b/lib/gl_anytree_list1.h
@@ -23,7 +23,7 @@
 typedef struct
 {
   gl_list_node_t node;
-  bool rightp;
+  size_t rightp;
 } iterstack_item_t;
 
 /* A stack used for iterating across the elements.  */

--- a/lib/gl_anytree_list2.h
+++ b/lib/gl_anytree_list2.h
@@ -164,87 +164,225 @@
 #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];
+  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;
 
-  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 == 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;
+  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;
 
-  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 == 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 +416,15 @@
 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

--- a/lib/gl_anytreehash_list1.h
+++ b/lib/gl_anytreehash_list1.h
@@ -78,6 +78,15 @@
 	  position1 < position2 ? -1 : 0);
 }
 
+/* Compares a node's position in the tree with a given threshold.  */
+static bool
+compare_position_threshold (const void *x, const void *threshold)
+{
+  gl_list_node_t node = (gl_list_node_t) x;
+  size_t position = node_position (node);
+  return (position >= (uintptr_t)threshold);
+}
+
 /* Return the first element of a non-empty ordered set of nodes.  */
 static inline gl_list_node_t
 gl_oset_first (gl_oset_t set)

--- a/lib/gl_anytreehash_list2.h
+++ b/lib/gl_anytreehash_list2.h
@@ -19,61 +19,121 @@
 /* Common code of gl_avltreehash_list.c and gl_rbtreehash_list.c.  */
 
 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)
 {
-  size_t hashcode =
-    (list->base.hashcode_fn != NULL
-     ? list->base.hashcode_fn (elt)
-     : (size_t)(uintptr_t) elt);
-  size_t index = hashcode % list->table_size;
-  gl_listelement_equals_fn equals = list->base.equals_fn;
-  gl_hash_entry_t entry;
+  if (!(start_index <= end_index
+	&& end_index <= (list->root != NULL ? list->root->branch_size : 0)))
+    /* Invalid arguments.  */
+    abort ();
+  {
+    size_t hashcode =
+      (list->base.hashcode_fn != NULL
+       ? list->base.hashcode_fn (elt)
+       : (size_t)(uintptr_t) elt);
+    size_t index = hashcode % list->table_size;
+    gl_listelement_equals_fn equals = list->base.equals_fn;
+    gl_hash_entry_t entry;
 
-  if (list->base.allow_duplicates)
-    {
-      for (entry = list->table[index]; entry != NULL; entry = entry->hash_next)
-	if (entry->hashcode == hashcode)
-	  {
-	    if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
-	      {
-		/* An entry representing multiple nodes.  */
-		gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
-		/* Only the first node is interesting.  */
-		gl_list_node_t node = gl_oset_first (nodes);
-		if (equals != NULL ? equals (elt, node->value) : elt == node->value)
-		  /* All nodes in the entry are equal to the given ELT.
-		     But we have to return only the one at the minimal position,
-		     and this is the first one in the ordered set.  */
-		  return node;
-	      }
-	    else
-	      {
-		/* An entry representing a single node.  */
-		gl_list_node_t node = (struct gl_list_node_impl *) entry;
-		if (equals != NULL ? equals (elt, node->value) : elt == node->value)
-		  return node;
-	      }
-	  }
-    }
-  else
-    {
-      /* If no duplicates are allowed, multiple nodes are not needed.  */
-      for (entry = list->table[index]; entry != NULL; entry = entry->hash_next)
-	if (entry->hashcode == hashcode)
-	  {
-	    gl_list_node_t node = (struct gl_list_node_impl *) entry;
-	    if (equals != NULL ? equals (elt, node->value) : elt == node->value)
-	      return node;
-	  }
-    }
+    if (list->base.allow_duplicates)
+      {
+	for (entry = list->table[index]; entry != NULL; entry = entry->hash_next)
+	  if (entry->hashcode == hashcode)
+	    {
+	      if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
+		{
+		  /* An entry representing multiple nodes.  */
+		  gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
+		  /* The first node is interesting.  */
+		  gl_list_node_t node = gl_oset_first (nodes);
+		  if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+		    {
+		      /* All nodes in the entry are equal to the given ELT.  */
+		      if (start_index == 0)
+			{
+			  /* We have to return only the one at the minimal
+			     position, and this is the first one in the ordered
+			     set.  */
+			  if (end_index == list->root->branch_size
+			      || node_position (node) < end_index)
+			    return node;
+			}
+		      else
+			{
+			  /* We have to return only the one at the minimal
+			     position >= start_index.  */
+			  const void *elt;
+			  if (gl_oset_search_atleast (nodes,
+						      compare_position_threshold,
+						      (void *)(uintptr_t)start_index,
+						      &elt))
+			    {
+			      node = (gl_list_node_t) elt;
+			      if (end_index == list->root->branch_size
+				  || node_position (node) < end_index)
+				return node;
+			    }
+			}
+		      break;
+		    }
+		}
+	      else
+		{
+		  /* An entry representing a single node.  */
+		  gl_list_node_t node = (struct gl_list_node_impl *) entry;
+		  if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+		    {
+		      bool position_in_bounds;
+		      if (start_index == 0 && end_index == list->root->branch_size)
+			position_in_bounds = true;
+		      else
+			{
+			  size_t position = node_position (node);
+			  position_in_bounds =
+			    (position >= start_index && position < end_index);
+			}
+		      if (position_in_bounds)
+			return node;
+		      break;
+		    }
+		}
+	    }
+      }
+    else
+      {
+	/* If no duplicates are allowed, multiple nodes are not needed.  */
+	for (entry = list->table[index]; entry != NULL; entry = entry->hash_next)
+	  if (entry->hashcode == hashcode)
+	    {
+	      gl_list_node_t node = (struct gl_list_node_impl *) entry;
+	      if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+		{
+		  bool position_in_bounds;
+		  if (start_index == 0 && end_index == list->root->branch_size)
+		    position_in_bounds = true;
+		  else
+		    {
+		      size_t position = node_position (node);
+		      position_in_bounds =
+			(position >= start_index && position < end_index);
+		    }
+		  if (position_in_bounds)
+		    return node;
+		  break;
+		}
+	    }
+      }
 
-  return NULL;
+    return NULL;
+  }
 }
 
 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_list_node_t node = gl_tree_search (list, elt);
+  gl_list_node_t node =
+    gl_tree_search_from_to (list, start_index, end_index, elt);
 
   if (node != NULL)
     return node_position (node);

--- a/lib/gl_array_list.c
+++ b/lib/gl_array_list.c
@@ -167,22 +167,28 @@
 }
 
 static size_t
-gl_array_indexof (gl_list_t list, const void *elt)
+gl_array_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
+			  const void *elt)
 {
   size_t count = list->count;
-  if (count > 0)
+
+  if (!(start_index <= end_index && end_index <= count))
+    /* Invalid arguments.  */
+    abort ();
+
+  if (start_index < end_index)
     {
       gl_listelement_equals_fn equals = list->base.equals_fn;
       if (equals != NULL)
 	{
 	  size_t i;
 
-	  for (i = 0;;)
+	  for (i = start_index;;)
 	    {
 	      if (equals (elt, list->elements[i]))
 		return i;
 	      i++;
-	      if (i == count)
+	      if (i == end_index)
 		break;
 	    }
 	}
@@ -190,12 +196,12 @@
 	{
 	  size_t i;
 
-	  for (i = 0;;)
+	  for (i = start_index;;)
 	    {
 	      if (elt == list->elements[i])
 		return i;
 	      i++;
-	      if (i == count)
+	      if (i == end_index)
 		break;
 	    }
 	}
@@ -204,9 +210,10 @@
 }
 
 static gl_list_node_t
-gl_array_search (gl_list_t list, const void *elt)
+gl_array_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
+			 const void *elt)
 {
-  size_t index = gl_array_indexof (list, elt);
+  size_t index = gl_array_indexof_from_to (list, start_index, end_index, elt);
   return INDEX_TO_NODE (index);
 }
 
@@ -367,7 +374,7 @@
 static bool
 gl_array_remove (gl_list_t list, const void *elt)
 {
-  size_t position = gl_array_indexof (list, elt);
+  size_t position = gl_array_indexof_from_to (list, 0, list->count, elt);
   if (position == (size_t)(-1))
     return false;
   else
@@ -575,8 +582,8 @@
     gl_array_previous_node,
     gl_array_get_at,
     gl_array_set_at,
-    gl_array_search,
-    gl_array_indexof,
+    gl_array_search_from_to,
+    gl_array_indexof_from_to,
     gl_array_add_first,
     gl_array_add_last,
     gl_array_add_before,

--- a/lib/gl_avltree_list.c
+++ b/lib/gl_avltree_list.c
@@ -75,8 +75,8 @@
     gl_tree_previous_node,
     gl_tree_get_at,
     gl_tree_set_at,
-    gl_tree_search,
-    gl_tree_indexof,
+    gl_tree_search_from_to,
+    gl_tree_indexof_from_to,
     gl_tree_add_first,
     gl_tree_add_last,
     gl_tree_add_before,

--- a/lib/gl_avltreehash_list.c
+++ b/lib/gl_avltreehash_list.c
@@ -104,8 +104,8 @@
     gl_tree_previous_node,
     gl_tree_get_at,
     gl_tree_set_at,
-    gl_tree_search,
-    gl_tree_indexof,
+    gl_tree_search_from_to,
+    gl_tree_indexof_from_to,
     gl_tree_add_first,
     gl_tree_add_last,
     gl_tree_add_before,

--- a/lib/gl_carray_list.c
+++ b/lib/gl_carray_list.c
@@ -185,16 +185,22 @@
 }
 
 static size_t
-gl_carray_indexof (gl_list_t list, const void *elt)
+gl_carray_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
+			   const void *elt)
 {
   size_t count = list->count;
-  if (count > 0)
+
+  if (!(start_index <= end_index && end_index <= count))
+    /* Invalid arguments.  */
+    abort ();
+
+  if (start_index < end_index)
     {
       gl_listelement_equals_fn equals = list->base.equals_fn;
       size_t allocated = list->allocated;
       size_t i_end;
 
-      i_end = list->offset + list->count;
+      i_end = list->offset + end_index;
       if (i_end >= allocated)
 	i_end -= allocated;
 
@@ -202,7 +208,11 @@
 	{
 	  size_t i;
 
-	  for (i = list->offset;;)
+	  i = list->offset + start_index;
+	  if (i >= allocated) /* can only happen if start_index > 0 */
+	    i -= allocated;
+
+	  for (;;)
 	    {
 	      if (equals (elt, list->elements[i]))
 		return (i >= list->offset ? i : i + allocated) - list->offset;
@@ -217,7 +227,11 @@
 	{
 	  size_t i;
 
-	  for (i = list->offset;;)
+	  i = list->offset + start_index;
+	  if (i >= allocated) /* can only happen if start_index > 0 */
+	    i -= allocated;
+
+	  for (;;)
 	    {
 	      if (elt == list->elements[i])
 		return (i >= list->offset ? i : i + allocated) - list->offset;
@@ -233,9 +247,10 @@
 }
 
 static gl_list_node_t
-gl_carray_search (gl_list_t list, const void *elt)
+gl_carray_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
+			  const void *elt)
 {
-  size_t index = gl_carray_indexof (list, elt);
+  size_t index = gl_carray_indexof_from_to (list, start_index, end_index, elt);
   return INDEX_TO_NODE (index);
 }
 
@@ -501,7 +516,7 @@
 static bool
 gl_carray_remove (gl_list_t list, const void *elt)
 {
-  size_t position = gl_carray_indexof (list, elt);
+  size_t position = gl_carray_indexof_from_to (list, 0, list->count, elt);
   if (position == (size_t)(-1))
     return false;
   else
@@ -732,8 +747,8 @@
     gl_carray_previous_node,
     gl_carray_get_at,
     gl_carray_set_at,
-    gl_carray_search,
-    gl_carray_indexof,
+    gl_carray_search_from_to,
+    gl_carray_indexof_from_to,
     gl_carray_add_first,
     gl_carray_add_last,
     gl_carray_add_before,

--- a/lib/gl_linked_list.c
+++ b/lib/gl_linked_list.c
@@ -42,8 +42,8 @@
     gl_linked_previous_node,
     gl_linked_get_at,
     gl_linked_set_at,
-    gl_linked_search,
-    gl_linked_indexof,
+    gl_linked_search_from_to,
+    gl_linked_indexof_from_to,
     gl_linked_add_first,
     gl_linked_add_last,
     gl_linked_add_before,

--- a/lib/gl_linkedhash_list.c
+++ b/lib/gl_linkedhash_list.c
@@ -99,8 +99,8 @@
     gl_linked_previous_node,
     gl_linked_get_at,
     gl_linked_set_at,
-    gl_linked_search,
-    gl_linked_indexof,
+    gl_linked_search_from_to,
+    gl_linked_indexof_from_to,
     gl_linked_add_first,
     gl_linked_add_last,
     gl_linked_add_before,

--- a/lib/gl_list.c
+++ b/lib/gl_list.c
@@ -93,15 +93,47 @@
 gl_list_node_t
 gl_list_search (gl_list_t list, const void *elt)
 {
+  size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
   return ((const struct gl_list_impl_base *) list)->vtable
-	 ->search (list, elt);
+	 ->search_from_to (list, 0, size, elt);
+}
+
+gl_list_node_t
+gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
+{
+  size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
+  return ((const struct gl_list_impl_base *) list)->vtable
+	 ->search_from_to (list, start_index, size, elt);
+}
+
+gl_list_node_t
+gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index, const void *elt)
+{
+  return ((const struct gl_list_impl_base *) list)->vtable
+	 ->search_from_to (list, start_index, end_index, elt);
 }
 
 size_t
 gl_list_indexof (gl_list_t list, const void *elt)
 {
+  size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
   return ((const struct gl_list_impl_base *) list)->vtable
-	 ->indexof (list, elt);
+	 ->indexof_from_to (list, 0, size, elt);
+}
+
+size_t
+gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
+{
+  size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
+  return ((const struct gl_list_impl_base *) list)->vtable
+	 ->indexof_from_to (list, start_index, size, elt);
+}
+
+size_t
+gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, const void *elt)
+{
+  return ((const struct gl_list_impl_base *) list)->vtable
+	 ->indexof_from_to (list, start_index, end_index, elt);
 }
 
 gl_list_node_t

--- a/lib/gl_list.h
+++ b/lib/gl_list.h
@@ -68,7 +68,11 @@
    gl_list_get_at              O(1)     O(n)   O(log n)    O(n)       O(log n)
    gl_list_set_at              O(1)     O(n)   O(log n)    O(n)    O((log n)²)/O(log n)
    gl_list_search              O(n)     O(n)     O(n)    O(n)/O(1)    O(log n)/O(1)
+   gl_list_search_from         O(n)     O(n)     O(n)    O(n)/O(1) O((log n)²)/O(log n)
+   gl_list_search_from_to      O(n)     O(n)     O(n)    O(n)/O(1) O((log n)²)/O(log n)
    gl_list_indexof             O(n)     O(n)     O(n)      O(n)       O(log n)
+   gl_list_indexof_from        O(n)     O(n)     O(n)      O(n)    O((log n)²)/O(log n)
+   gl_list_indexof_from_to     O(n)     O(n)     O(n)      O(n)    O((log n)²)/O(log n)
    gl_list_add_first         O(n)/O(1)  O(1)   O(log n)    O(1)    O((log n)²)/O(log n)
    gl_list_add_last            O(1)     O(1)   O(log n)    O(1)    O((log n)²)/O(log n)
    gl_list_add_before          O(n)     O(1)   O(log n)    O(1)    O((log n)²)/O(log n)
@@ -167,10 +171,37 @@
    Return its node if found, or NULL if not present in the list.  */
 extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt);
 
+/* Search whether an element is already in the list,
+   at a position >= START_INDEX.
+   Return its node if found, or NULL if not present in the list.  */
+extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index,
+					   const void *elt);
+
+/* Search whether an element is already in the list,
+   at a position >= START_INDEX and < END_INDEX.
+   Return its node if found, or NULL if not present in the list.  */
+extern gl_list_node_t gl_list_search_from_to (gl_list_t list,
+					      size_t start_index,
+					      size_t end_index,
+					      const void *elt);
+
 /* Search whether an element is already in the list.
    Return its position if found, or (size_t)(-1) if not present in the list.  */
 extern size_t gl_list_indexof (gl_list_t list, const void *elt);
 
+/* Search whether an element is already in the list,
+   at a position >= START_INDEX.
+   Return its position if found, or (size_t)(-1) if not present in the list.  */
+extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index,
+				    const void *elt);
+
+/* Search whether an element is already in the list,
+   at a position >= START_INDEX and < END_INDEX.
+   Return its position if found, or (size_t)(-1) if not present in the list.  */
+extern size_t gl_list_indexof_from_to (gl_list_t list,
+				       size_t start_index, size_t end_index,
+				       const void *elt);
+
 /* Add an element as the first element of the list.
    Return its node.  */
 extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt);
@@ -315,8 +346,10 @@
   gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node);
   const void * (*get_at) (gl_list_t list, size_t position);
   gl_list_node_t (*set_at) (gl_list_t list, size_t position, const void *elt);
-  gl_list_node_t (*search) (gl_list_t list, const void *elt);
-  size_t (*indexof) (gl_list_t list, const void *elt);
+  gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index,
+				    size_t end_index, const void *elt);
+  size_t (*indexof_from_to) (gl_list_t list, size_t start_index,
+			     size_t end_index, const void *elt);
   gl_list_node_t (*add_first) (gl_list_t list, const void *elt);
   gl_list_node_t (*add_last) (gl_list_t list, const void *elt);
   gl_list_node_t (*add_before) (gl_list_t list, gl_list_node_t node,
@@ -441,16 +474,54 @@
 static inline gl_list_node_t
 gl_list_search (gl_list_t list, const void *elt)
 {
+  size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
   return ((const struct gl_list_impl_base *) list)->vtable
-	 ->search (list, elt);
+	 ->search_from_to (list, 0, size, elt);
+}
+
+# define gl_list_search_from gl_list_search_from_inline
+static inline gl_list_node_t
+gl_list_search_from (gl_list_t list, size_t start_index, const void *elt)
+{
+  size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
+  return ((const struct gl_list_impl_base *) list)->vtable
+	 ->search_from_to (list, start_index, size, elt);
+}
+
+# define gl_list_search_from_to gl_list_search_from_to_inline
+static inline gl_list_node_t
+gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
+			const void *elt)
+{
+  return ((const struct gl_list_impl_base *) list)->vtable
+	 ->search_from_to (list, start_index, end_index, elt);
 }
 
 # define gl_list_indexof gl_list_indexof_inline
 static inline size_t
 gl_list_indexof (gl_list_t list, const void *elt)
 {
+  size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
   return ((const struct gl_list_impl_base *) list)->vtable
-	 ->indexof (list, elt);
+	 ->indexof_from_to (list, 0, size, elt);
+}
+
+# define gl_list_indexof_from gl_list_indexof_from_inline
+static inline size_t
+gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt)
+{
+  size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list);
+  return ((const struct gl_list_impl_base *) list)->vtable
+	 ->indexof_from_to (list, start_index, size, elt);
+}
+
+# define gl_list_indexof_from_to gl_list_indexof_from_to_inline
+static inline size_t
+gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
+			 const void *elt)
+{
+  return ((const struct gl_list_impl_base *) list)->vtable
+	 ->indexof_from_to (list, start_index, end_index, elt);
 }
 
 # define gl_list_add_first gl_list_add_first_inline

--- a/lib/gl_rbtree_list.c
+++ b/lib/gl_rbtree_list.c
@@ -76,8 +76,8 @@
     gl_tree_previous_node,
     gl_tree_get_at,
     gl_tree_set_at,
-    gl_tree_search,
-    gl_tree_indexof,
+    gl_tree_search_from_to,
+    gl_tree_indexof_from_to,
     gl_tree_add_first,
     gl_tree_add_last,
     gl_tree_add_before,

--- a/lib/gl_rbtreehash_list.c
+++ b/lib/gl_rbtreehash_list.c
@@ -105,8 +105,8 @@
     gl_tree_previous_node,
     gl_tree_get_at,
     gl_tree_set_at,
-    gl_tree_search,
-    gl_tree_indexof,
+    gl_tree_search_from_to,
+    gl_tree_indexof_from_to,
     gl_tree_add_first,
     gl_tree_add_last,
     gl_tree_add_before,