2007-02-05 Paolo Bonzini <bonzini@gnu.org>

[gnulib.git] / lib / gl_anylinked_list2.h

diff --git a/lib/gl_anylinked_list2.h b/lib/gl_anylinked_list2.h
index 8368f27..718dfb7 100644 (file)
--- a/lib/gl_anylinked_list2.h
+++ b/lib/gl_anylinked_list2.h
@@ -43,8 +43,7 @@ gl_linked_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;
@@ -52,8 +51,7 @@ gl_linked_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.next = &list->root;
   list->root.prev = &list->root;
@@ -69,8 +67,7 @@ gl_linked_create (gl_list_implementation_t implementation,
                  bool allow_duplicates,
                  size_t count, const void **contents)
 {
-  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);
   gl_list_node_t tail;
 
   list->base.vtable = implementation;
@@ -83,17 +80,14 @@ gl_linked_create (gl_list_implementation_t implementation,
     if (estimate < 10)
       estimate = 10;
     list->table_size = next_prime (estimate);
-    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->count = count;
   tail = &list->root;
   for (; count > 0; contents++, count--)
     {
-      gl_list_node_t node =
-       (struct gl_list_node_impl *)
-       xmalloc (sizeof (struct gl_list_node_impl));
+      gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
 
       node->value = *contents;
 #if WITH_HASHTABLE
@@ -229,7 +223,7 @@ gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
       (list->base.hashcode_fn != NULL
        ? list->base.hashcode_fn (elt)
        : (size_t)(uintptr_t) elt);
-    size_t index = hashcode % list->table_size;
+    size_t bucket = hashcode % list->table_size;
     gl_listelement_equals_fn equals = list->base.equals_fn;
 
     if (!list->base.allow_duplicates)
@@ -238,7 +232,7 @@ gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
        gl_list_node_t found = NULL;
        gl_list_node_t node;
 
-       for (node = (gl_list_node_t) list->table[index];
+       for (node = (gl_list_node_t) list->table[bucket];
             node != NULL;
             node = (gl_list_node_t) node->h.hash_next)
          if (node->h.hashcode == hashcode
@@ -279,7 +273,7 @@ gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
        gl_list_node_t first_match = NULL;
        gl_list_node_t node;
 
-       for (node = (gl_list_node_t) list->table[index];
+       for (node = (gl_list_node_t) list->table[bucket];
             node != NULL;
             node = (gl_list_node_t) node->h.hash_next)
          if (node->h.hashcode == hashcode
@@ -385,7 +379,7 @@ gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
       (list->base.hashcode_fn != NULL
        ? list->base.hashcode_fn (elt)
        : (size_t)(uintptr_t) elt);
-    size_t index = hashcode % list->table_size;
+    size_t bucket = hashcode % list->table_size;
     gl_listelement_equals_fn equals = list->base.equals_fn;
     gl_list_node_t node;
 
@@ -393,7 +387,7 @@ gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
     if (!list->base.allow_duplicates)
       {
        /* Look for the first match in the hash bucket.  */
-       for (node = (gl_list_node_t) list->table[index];
+       for (node = (gl_list_node_t) list->table[bucket];
             node != NULL;
             node = (gl_list_node_t) node->h.hash_next)
          if (node->h.hashcode == hashcode
@@ -408,7 +402,7 @@ gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
        bool multiple_matches = false;
        gl_list_node_t first_match = NULL;
 
-       for (node = (gl_list_node_t) list->table[index];
+       for (node = (gl_list_node_t) list->table[bucket];
             node != NULL;
             node = (gl_list_node_t) node->h.hash_next)
          if (node->h.hashcode == hashcode
@@ -497,8 +491,7 @@ gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 static gl_list_node_t
 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));
+  gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
 
   ASYNCSAFE(const void *) node->value = elt;
 #if WITH_HASHTABLE
@@ -528,8 +521,7 @@ gl_linked_add_first (gl_list_t list, const void *elt)
 static gl_list_node_t
 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));
+  gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
 
   ASYNCSAFE(const void *) node->value = elt;
 #if WITH_HASHTABLE
@@ -559,8 +551,7 @@ gl_linked_add_last (gl_list_t list, const void *elt)
 static gl_list_node_t
 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));
+  gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
 
   ASYNCSAFE(const void *) new_node->value = elt;
 #if WITH_HASHTABLE
@@ -590,8 +581,7 @@ gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 static gl_list_node_t
 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));
+  gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
 
   ASYNCSAFE(const void *) new_node->value = elt;
 #if WITH_HASHTABLE
@@ -628,8 +618,7 @@ gl_linked_add_at (gl_list_t list, size_t position, const void *elt)
     /* Invalid argument.  */
     abort ();
 
-  new_node =
-    (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
+  new_node = XMALLOC (struct gl_list_node_impl);
   ASYNCSAFE(const void *) new_node->value = elt;
 #if WITH_HASHTABLE
   new_node->h.hashcode =
@@ -906,6 +895,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 +964,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)