2007-08-06 Simon Josefsson <simon@josefsson.org>

[gnulib.git] / lib / gl_anytree_list2.h

diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h
index 00b285b..81d2a18 100644 (file)
--- a/lib/gl_anytree_list2.h
+++ b/lib/gl_anytree_list2.h
@@ -1,5 +1,5 @@
 /* Sequential list data type implemented by a binary tree.
-   Copyright (C) 2006 Free Software Foundation, Inc.
+   Copyright (C) 2006-2007 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
    This program is free software; you can redistribute it and/or modify
@@ -23,19 +23,19 @@ static gl_list_t
 gl_tree_create_empty (gl_list_implementation_t implementation,
                      gl_listelement_equals_fn equals_fn,
                      gl_listelement_hashcode_fn hashcode_fn,
+                     gl_listelement_dispose_fn dispose_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;
   list->base.hashcode_fn = hashcode_fn;
+  list->base.dispose_fn = dispose_fn;
   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 = NULL;
 
@@ -459,6 +459,8 @@ gl_tree_list_free (gl_list_t list)
          if (!stack_ptr->rightp)
            break;
          /* Free the current node.  */
+         if (list->base.dispose_fn != NULL)
+           list->base.dispose_fn (node->value);
          free (node);
        }
       /* Descend on right branch.  */
@@ -601,6 +603,88 @@ gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
   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 +740,92 @@ gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
   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)