X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_anytree_list2.h;h=70e59a58c356b424922579280ac5b815ffce495b;hb=1276a2c5f24c0c932426aca9c899fa524d2443f2;hp=d2ff90081ca66ef43fcd1929b96a992f16e27eac;hpb=fca2f939ea0d8831cd89f89df4b52a9a47c210f2;p=gnulib.git

diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h
index d2ff90081..70e59a58c 100644
--- a/lib/gl_anytree_list2.h
+++ b/lib/gl_anytree_list2.h
@@ -1,11 +1,11 @@
 /* Sequential list data type implemented by a binary tree.
-   Copyright (C) 2006 Free Software Foundation, Inc.
+   Copyright (C) 2006-2014 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2006.
 
-   This program is free software; you can redistribute it and/or modify
+   This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
-   the Free Software Foundation; either version 2, or (at your option)
-   any later version.
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
 
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ -13,33 +13,44 @@
    GNU General Public License for more details.
 
    You should have received a copy of the GNU General Public License
-   along with this program; if not, write to the Free Software Foundation,
-   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
 
 /* Common code of gl_avltree_list.c, gl_rbtree_list.c,
                   gl_avltreehash_list.c, gl_rbtreehash_list.c.  */
 
 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,
-		      bool allow_duplicates)
+gl_tree_nx_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 = (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
+
+  if (list == NULL)
+    return NULL;
 
   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));
+    (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
+  if (list->table == NULL)
+    goto fail;
 #endif
   list->root = NULL;
 
   return list;
+
+#if WITH_HASHTABLE
+ fail:
+  free (list);
+  return NULL;
+#endif
 }
 
 static size_t
@@ -54,6 +65,41 @@ gl_tree_node_value (gl_list_t list, gl_list_node_t node)
   return node->value;
 }
 
+static int
+gl_tree_node_nx_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+#if WITH_HASHTABLE
+  if (elt != node->value)
+    {
+      size_t new_hashcode =
+        (list->base.hashcode_fn != NULL
+         ? list->base.hashcode_fn (elt)
+         : (size_t)(uintptr_t) elt);
+
+      if (new_hashcode != node->h.hashcode)
+        {
+          remove_from_bucket (list, node);
+          node->value = elt;
+          node->h.hashcode = new_hashcode;
+          if (add_to_bucket (list, node) < 0)
+            {
+              /* Out of memory.  We removed node from a bucket but cannot add
+                 it to another bucket.  In order to avoid inconsistencies, we
+                 must remove node entirely from the list.  */
+              gl_tree_remove_node_from_tree (list, node);
+              free (node);
+              return -1;
+            }
+        }
+      else
+        node->value = elt;
+    }
+#else
+  node->value = elt;
+#endif
+  return 0;
+}
+
 static gl_list_node_t
 gl_tree_next_node (gl_list_t list, gl_list_node_t node)
 {
@@ -61,12 +107,12 @@ gl_tree_next_node (gl_list_t list, gl_list_node_t node)
     {
       node = node->right;
       while (node->left != NULL)
-	node = node->left;
+        node = node->left;
     }
   else
     {
       while (node->parent != NULL && node->parent->right == node)
-	node = node->parent;
+        node = node->parent;
       node = node->parent;
     }
   return node;
@@ -79,19 +125,19 @@ gl_tree_previous_node (gl_list_t list, gl_list_node_t node)
     {
       node = node->left;
       while (node->right != NULL)
-	node = node->right;
+        node = node->right;
     }
   else
     {
       while (node->parent != NULL && node->parent->left == node)
-	node = node->parent;
+        node = node->parent;
       node = node->parent;
     }
   return node;
 }
 
 /* Return the node at the given position < gl_tree_size (list).  */
-static inline gl_list_node_t
+static gl_list_node_t
 node_at (gl_list_node_t root, size_t position)
 {
   /* Here we know that root != NULL.  */
@@ -100,16 +146,16 @@ node_at (gl_list_node_t root, size_t position)
   for (;;)
     {
       if (node->left != NULL)
-	{
-	  if (position < node->left->branch_size)
-	    {
-	      node = node->left;
-	      continue;
-	    }
-	  position -= node->left->branch_size;
-	}
+        {
+          if (position < node->left->branch_size)
+            {
+              node = node->left;
+              continue;
+            }
+          position -= node->left->branch_size;
+        }
       if (position == 0)
-	break;
+        break;
       position--;
       node = node->right;
     }
@@ -129,7 +175,7 @@ gl_tree_get_at (gl_list_t list, size_t position)
 }
 
 static gl_list_node_t
-gl_tree_set_at (gl_list_t list, size_t position, const void *elt)
+gl_tree_nx_set_at (gl_list_t list, size_t position, const void *elt)
 {
   gl_list_node_t node = list->root;
 
@@ -141,19 +187,27 @@ gl_tree_set_at (gl_list_t list, size_t position, const void *elt)
   if (elt != node->value)
     {
       size_t new_hashcode =
-	(list->base.hashcode_fn != NULL
-	 ? list->base.hashcode_fn (elt)
-	 : (size_t)(uintptr_t) elt);
+        (list->base.hashcode_fn != NULL
+         ? list->base.hashcode_fn (elt)
+         : (size_t)(uintptr_t) elt);
 
       if (new_hashcode != node->h.hashcode)
-	{
-	  remove_from_bucket (list, node);
-	  node->value = elt;
-	  node->h.hashcode = new_hashcode;
-	  add_to_bucket (list, node);
-	}
+        {
+          remove_from_bucket (list, node);
+          node->value = elt;
+          node->h.hashcode = new_hashcode;
+          if (add_to_bucket (list, node) < 0)
+            {
+              /* Out of memory.  We removed node from a bucket but cannot add
+                 it to another bucket.  In order to avoid inconsistencies, we
+                 must remove node entirely from the list.  */
+              gl_tree_remove_node_from_tree (list, node);
+              free (node);
+              return NULL;
+            }
+        }
       else
-	node->value = elt;
+        node->value = elt;
     }
 #else
   node->value = elt;
@@ -165,10 +219,10 @@ gl_tree_set_at (gl_list_t list, size_t position, const void *elt)
 
 static gl_list_node_t
 gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
-			const void *elt)
+                        const void *elt)
 {
   if (!(start_index <= end_index
-	&& end_index <= (list->root != NULL ? list->root->branch_size : 0)))
+        && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
     /* Invalid arguments.  */
     abort ();
   {
@@ -181,105 +235,105 @@ gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 
     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++;
-	  }
+        /* 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++;
-	  }
+        /* 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_from_to (gl_list_t list, size_t start_index, size_t end_index,
-			 const void *elt)
+                         const void *elt)
 {
   if (!(start_index <= end_index
-	&& end_index <= (list->root != NULL ? list->root->branch_size : 0)))
+        && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
     /* Invalid arguments.  */
     abort ();
   {
@@ -292,95 +346,95 @@ gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 
     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++;
-	  }
+        /* 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++;
-	  }
+        /* 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++;
+          }
       }
   }
 }
@@ -388,7 +442,7 @@ gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 #endif
 
 static gl_list_node_t
-gl_tree_add_at (gl_list_t list, size_t position, const void *elt)
+gl_tree_nx_add_at (gl_list_t list, size_t position, const void *elt)
 {
   size_t count = (list->root != NULL ? list->root->branch_size : 0);
 
@@ -396,9 +450,27 @@ gl_tree_add_at (gl_list_t list, size_t position, const void *elt)
     /* Invalid argument.  */
     abort ();
   if (position == count)
-    return gl_tree_add_last (list, elt);
+    return gl_tree_nx_add_last (list, elt);
   else
-    return gl_tree_add_before (list, node_at (list->root, position), elt);
+    return gl_tree_nx_add_before (list, node_at (list->root, position), elt);
+}
+
+static bool
+gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
+{
+#if WITH_HASHTABLE
+  /* Remove node from the hash table.
+     Note that this is only possible _before_ the node is removed from the
+     tree structure, because remove_from_bucket() uses node_position().  */
+  remove_from_bucket (list, node);
+#endif
+
+  gl_tree_remove_node_from_tree (list, node);
+
+  if (list->base.dispose_fn != NULL)
+    list->base.dispose_fn (node->value);
+  free (node);
+  return true;
 }
 
 static bool
@@ -419,10 +491,10 @@ gl_tree_remove (gl_list_t list, const void *elt)
   if (list->root != NULL)
     {
       gl_list_node_t node =
-	gl_tree_search_from_to (list, 0, list->root->branch_size, elt);
+        gl_tree_search_from_to (list, 0, list->root->branch_size, elt);
 
       if (node != NULL)
-	return gl_tree_remove_node (list, node);
+        return gl_tree_remove_node (list, node);
     }
   return false;
 }
@@ -441,26 +513,28 @@ gl_tree_list_free (gl_list_t list)
     {
       /* Descend on left branch.  */
       for (;;)
-	{
-	  if (node == NULL)
-	    break;
-	  stack_ptr->node = node;
-	  stack_ptr->rightp = false;
-	  node = node->left;
-	  stack_ptr++;
-	}
+        {
+          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])
-	    goto done_iterate;
-	  stack_ptr--;
-	  node = stack_ptr->node;
-	  if (!stack_ptr->rightp)
-	    break;
-	  /* Free the current node.  */
-	  free (node);
-	}
+        {
+          if (stack_ptr == &stack[0])
+            goto done_iterate;
+          stack_ptr--;
+          node = stack_ptr->node;
+          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.  */
       stack_ptr->rightp = true;
       node = node->right;
@@ -525,27 +599,27 @@ gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 
 static bool
 gl_tree_iterator_next (gl_list_iterator_t *iterator,
-		       const void **eltp, gl_list_node_t *nodep)
+                       const void **eltp, gl_list_node_t *nodep)
 {
   if (iterator->p != iterator->q)
     {
       gl_list_node_t node = (gl_list_node_t) iterator->p;
       *eltp = node->value;
       if (nodep != NULL)
-	*nodep = node;
+        *nodep = node;
       /* Advance to the next node.  */
       if (node->right != NULL)
-	{
-	  node = node->right;
-	  while (node->left != NULL)
-	    node = node->left;
-	}
+        {
+          node = node->right;
+          while (node->left != NULL)
+            node = node->left;
+        }
       else
-	{
-	  while (node->parent != NULL && node->parent->right == node)
-	    node = node->parent;
-	  node = node->parent;
-	}
+        {
+          while (node->parent != NULL && node->parent->right == node)
+            node = node->parent;
+          node = node->parent;
+        }
       iterator->p = node;
       return true;
     }
@@ -562,7 +636,7 @@ gl_tree_iterator_free (gl_list_iterator_t *iterator)
 
 static gl_list_node_t
 gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
-			   const void *elt)
+                           const void *elt)
 {
   gl_list_node_t node;
 
@@ -571,121 +645,121 @@ gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
       int cmp = compar (node->value, elt);
 
       if (cmp < 0)
-	node = node->right;
+        node = node->right;
       else if (cmp > 0)
-	node = node->left;
+        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; )
-	    {
-	      int cmp2 = compar (node->value, elt);
-
-	      if (cmp2 < 0)
-		node = node->right;
-	      else if (cmp2 > 0)
-		/* The list was not sorted.  */
-		abort ();
-	      else /* cmp2 == 0 */
-		{
-		  found = node;
-		  node = node->left;
-		}
-	    }
-	  return found;
-	}
+        {
+          /* 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; )
+            {
+              int cmp2 = compar (node->value, elt);
+
+              if (cmp2 < 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 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_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)))
+        && 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);
+        (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;
-	}
+        {
+          low -= left_branch_size + 1;
+          high -= left_branch_size + 1;
+          node = node->right;
+        }
       else if (high <= left_branch_size)
-	node = node->left;
+        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;
-	    }
-	}
+        {
+          /* 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)
+                            const void *elt)
 {
   gl_list_node_t node;
   size_t position;
@@ -695,168 +769,168 @@ gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
       int cmp = compar (node->value, elt);
 
       if (cmp < 0)
-	{
-	  if (node->left != NULL)
-	    position += node->left->branch_size;
-	  position++;
-	  node = node->right;
-	}
+        {
+          if (node->left != NULL)
+            position += node->left->branch_size;
+          position++;
+          node = node->right;
+        }
       else if (cmp > 0)
-	node = node->left;
+        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; )
-	    {
-	      int cmp2 = compar (node->value, elt);
-
-	      if (cmp2 < 0)
-		{
-		  if (node->left != NULL)
-		    position += node->left->branch_size;
-		  position++;
-		  node = node->right;
-		}
-	      else if (cmp2 > 0)
-		/* The list was not sorted.  */
-		abort ();
-	      else /* cmp2 == 0 */
-		{
-		  found_position =
-		    position
-		    + (node->left != NULL ? node->left->branch_size : 0);
-		  node = node->left;
-		}
-	    }
-	  return found_position;
-	}
+        {
+          /* 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; )
+            {
+              int cmp2 = compar (node->value, elt);
+
+              if (cmp2 < 0)
+                {
+                  if (node->left != NULL)
+                    position += node->left->branch_size;
+                  position++;
+                  node = node->right;
+                }
+              else if (cmp2 > 0)
+                /* The list was not sorted.  */
+                abort ();
+              else /* cmp2 == 0 */
+                {
+                  found_position =
+                    position
+                    + (node->left != NULL ? node->left->branch_size : 0);
+                  node = node->left;
+                }
+            }
+          return found_position;
+        }
     }
   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_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)))
+        && 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);
+        (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;
-	}
+        {
+          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;
+        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;
-	    }
-	}
+        {
+          /* 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)
+gl_tree_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
+                           const void *elt)
 {
   gl_list_node_t node = list->root;
 
   if (node == NULL)
-    return gl_tree_add_first (list, elt);
+    return gl_tree_nx_add_first (list, elt);
 
   for (;;)
     {
       int cmp = compar (node->value, elt);
 
       if (cmp < 0)
-	{
-	  if (node->right == NULL)
-	    return gl_tree_add_after (list, node, elt);
-	  node = node->right;
-	}
+        {
+          if (node->right == NULL)
+            return gl_tree_nx_add_after (list, node, elt);
+          node = node->right;
+        }
       else if (cmp > 0)
-	{
-	  if (node->left == NULL)
-	    return gl_tree_add_before (list, node, elt);
-	  node = node->left;
-	}
+        {
+          if (node->left == NULL)
+            return gl_tree_nx_add_before (list, node, elt);
+          node = node->left;
+        }
       else /* cmp == 0 */
-	return gl_tree_add_before (list, node, elt);
+        return gl_tree_nx_add_before (list, node, elt);
     }
 }
 
 static bool
 gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
-			   const void *elt)
+                           const void *elt)
 {
   gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
   if (node != NULL)