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

diff --git a/lib/gl_anylinked_list2.h b/lib/gl_anylinked_list2.h
index d2fb08974..bc551edd6 100644
--- a/lib/gl_anylinked_list2.h
+++ b/lib/gl_anylinked_list2.h
@@ -18,6 +18,23 @@
 
 /* Common code of gl_linked_list.c and gl_linkedhash_list.c.  */
 
+/* If the symbol SIGNAL_SAFE_LIST is defined, the code is compiled in such
+   a way that a gl_list_t data structure may be used from within a signal
+   handler.  The operations allowed in the signal handler are:
+     gl_list_iterator, gl_list_iterator_next, gl_list_iterator_free.
+   The list and node fields that are therefore accessed from the signal handler
+   are:
+     list->root, node->next, node->value.
+   We are careful to make modifications to these fields only in an order
+   that maintains the consistency of the list data structure at any moment,
+   and we use 'volatile' assignments to prevent the compiler from reordering
+   such assignments.  */
+#ifdef SIGNAL_SAFE_LIST
+# define ASYNCSAFE(type) *(volatile type *)&
+#else
+# define ASYNCSAFE(type)
+#endif
+
 /* -------------------------- gl_list_t Data Type -------------------------- */
 
 static gl_list_t
@@ -198,196 +215,283 @@ gl_linked_set_at (gl_list_t list, size_t position, const void *elt)
 }
 
 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)
 {
-#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;
-
-  if (!list->base.allow_duplicates)
-    {
-      /* Look for the first match in the hash bucket.  */
-      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;
+  size_t count = list->count;
 
-      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 (!(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;
+
+    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))
+	    {
+	      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;
-
-  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;
+    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 (; 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)
 {
-#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;
+  size_t count = list->count;
 
-  /* 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))
+  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;
+
+    /* 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))
+	    {
+	      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;
-
-	  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;
-    }
+	node = first_match;
+      }
 
-  /* Second step: Look up the index of the node.  */
-  if (node == NULL)
-    return (size_t)(-1);
-  else
-    {
-      size_t index = 0;
+    /* Second step: Look up the index of the node.  */
+    if (node == NULL)
+      return (size_t)(-1);
+    else
+      {
+	size_t index = 0;
 
-      for (; node->prev != &list->root; node = node->prev)
-	index++;
+	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;
-
-  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)
+	if (index >= start_index && index < end_index)
 	  return index;
-    }
-  return (size_t)(-1);
+	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 (; start_index > 0; start_index--)
+      node = node->next;
+
+    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
@@ -396,7 +500,7 @@ gl_linked_add_first (gl_list_t list, const void *elt)
   gl_list_node_t node =
     (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
 
-  node->value = elt;
+  ASYNCSAFE(const void *) node->value = elt;
 #if WITH_HASHTABLE
   node->h.hashcode =
     (list->base.hashcode_fn != NULL
@@ -409,9 +513,9 @@ gl_linked_add_first (gl_list_t list, const void *elt)
 
   /* Add node to the list.  */
   node->prev = &list->root;
-  node->next = list->root.next;
+  ASYNCSAFE(gl_list_node_t) node->next = list->root.next;
   node->next->prev = node;
-  list->root.next = node;
+  ASYNCSAFE(gl_list_node_t) list->root.next = node;
   list->count++;
 
 #if WITH_HASHTABLE
@@ -427,7 +531,7 @@ gl_linked_add_last (gl_list_t list, const void *elt)
   gl_list_node_t node =
     (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
 
-  node->value = elt;
+  ASYNCSAFE(const void *) node->value = elt;
 #if WITH_HASHTABLE
   node->h.hashcode =
     (list->base.hashcode_fn != NULL
@@ -439,9 +543,9 @@ gl_linked_add_last (gl_list_t list, const void *elt)
 #endif
 
   /* Add node to the list.  */
-  node->next = &list->root;
+  ASYNCSAFE(gl_list_node_t) node->next = &list->root;
   node->prev = list->root.prev;
-  node->prev->next = node;
+  ASYNCSAFE(gl_list_node_t) node->prev->next = node;
   list->root.prev = node;
   list->count++;
 
@@ -458,7 +562,7 @@ gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
   gl_list_node_t new_node =
     (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
 
-  new_node->value = elt;
+  ASYNCSAFE(const void *) new_node->value = elt;
 #if WITH_HASHTABLE
   new_node->h.hashcode =
     (list->base.hashcode_fn != NULL
@@ -470,9 +574,9 @@ gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 #endif
 
   /* Add new_node to the list.  */
-  new_node->next = node;
+  ASYNCSAFE(gl_list_node_t) new_node->next = node;
   new_node->prev = node->prev;
-  new_node->prev->next = new_node;
+  ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
   node->prev = new_node;
   list->count++;
 
@@ -489,7 +593,7 @@ gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
   gl_list_node_t new_node =
     (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
 
-  new_node->value = elt;
+  ASYNCSAFE(const void *) new_node->value = elt;
 #if WITH_HASHTABLE
   new_node->h.hashcode =
     (list->base.hashcode_fn != NULL
@@ -502,9 +606,9 @@ gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 
   /* Add new_node to the list.  */
   new_node->prev = node;
-  new_node->next = node->next;
+  ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
   new_node->next->prev = new_node;
-  node->next = new_node;
+  ASYNCSAFE(gl_list_node_t) node->next = new_node;
   list->count++;
 
 #if WITH_HASHTABLE
@@ -526,7 +630,7 @@ gl_linked_add_at (gl_list_t list, size_t position, const void *elt)
 
   new_node =
     (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
-  new_node->value = elt;
+  ASYNCSAFE(const void *) new_node->value = elt;
 #if WITH_HASHTABLE
   new_node->h.hashcode =
     (list->base.hashcode_fn != NULL
@@ -546,9 +650,9 @@ gl_linked_add_at (gl_list_t list, size_t position, const void *elt)
       for (; position > 0; position--)
 	node = node->next;
       new_node->prev = node;
-      new_node->next = node->next;
+      ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
       new_node->next->prev = new_node;
-      node->next = new_node;
+      ASYNCSAFE(gl_list_node_t) node->next = new_node;
     }
   else
     {
@@ -558,9 +662,9 @@ gl_linked_add_at (gl_list_t list, size_t position, const void *elt)
       node = &list->root;
       for (; position > 0; position--)
 	node = node->prev;
-      new_node->next = node;
+      ASYNCSAFE(gl_list_node_t) new_node->next = node;
       new_node->prev = node->prev;
-      new_node->prev->next = new_node;
+      ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
       node->prev = new_node;
     }
   list->count++;
@@ -587,7 +691,7 @@ gl_linked_remove_node (gl_list_t list, gl_list_node_t node)
   prev = node->prev;
   next = node->next;
 
-  prev->next = next;
+  ASYNCSAFE(gl_list_node_t) prev->next = next;
   next->prev = prev;
   list->count--;
 
@@ -615,7 +719,7 @@ gl_linked_remove_at (gl_list_t list, size_t position)
 	node = node->next;
       removed_node = node->next;
       after_removed = node->next->next;
-      node->next = after_removed;
+      ASYNCSAFE(gl_list_node_t) node->next = after_removed;
       after_removed->prev = node;
     }
   else
@@ -630,7 +734,7 @@ gl_linked_remove_at (gl_list_t list, size_t position)
       removed_node = node->prev;
       before_removed = node->prev->prev;
       node->prev = before_removed;
-      before_removed->next = node;
+      ASYNCSAFE(gl_list_node_t) before_removed->next = node;
     }
 #if WITH_HASHTABLE
   remove_from_bucket (list, removed_node);
@@ -644,7 +748,7 @@ gl_linked_remove_at (gl_list_t list, size_t position)
 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);
@@ -680,6 +784,11 @@ gl_linked_iterator (gl_list_t list)
   result.list = list;
   result.p = list->root.next;
   result.q = &list->root;
+#ifdef lint
+  result.i = 0;
+  result.j = 0;
+  result.count = 0;
+#endif
 
   return result;
 }
@@ -746,6 +855,12 @@ gl_linked_iterator_from_to (gl_list_t list,
       result.q = node;
     }
 
+#ifdef lint
+  result.i = 0;
+  result.j = 0;
+  result.count = 0;
+#endif
+
   return result;
 }
 
@@ -791,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)
@@ -812,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)