X-Git-Url: https://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_anylinked_list2.h;h=bc551edd6bd9509c8ce7775f56fd8f09d3653bc9;hb=fca2f939ea0d8831cd89f89df4b52a9a47c210f2;hp=8368f276edda2daef6a933c3f89b5304205096f2;hpb=407400d9367b16a628b57b2d9b8565bb5a08ffae;p=gnulib.git

diff --git a/lib/gl_anylinked_list2.h b/lib/gl_anylinked_list2.h
index 8368f276e..bc551edd6 100644
--- a/lib/gl_anylinked_list2.h
+++ b/lib/gl_anylinked_list2.h
@@ -906,6 +906,54 @@ gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
   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 @@ gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
   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)