X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_anytreehash_list1.h;h=95dade95c7215b6fb63881c9dcd86e966a04eb16;hb=ec560ef5cab3aec7a68fb2da6b2dbbbd7415caf1;hp=7f38180c9ce1e65263fd331c95dcac8e526de11d;hpb=0a51cf1590113188ff1dc78dc79d2924c262a865;p=gnulib.git

diff --git a/lib/gl_anytreehash_list1.h b/lib/gl_anytreehash_list1.h
index 7f38180c9..95dade95c 100644
--- a/lib/gl_anytreehash_list1.h
+++ b/lib/gl_anytreehash_list1.h
@@ -1,11 +1,11 @@
 /* Sequential list data type implemented by a hash table with 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
+   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,8 +13,7 @@
    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_avltreehash_list.c and gl_rbtreehash_list.c.  */
 
@@ -78,6 +77,15 @@ compare_by_position (const void *x1, const void *x2)
 	  position1 < position2 ? -1 : 0);
 }
 
+/* Compares a node's position in the tree with a given threshold.  */
+static bool
+compare_position_threshold (const void *x, const void *threshold)
+{
+  gl_list_node_t node = (gl_list_node_t) x;
+  size_t position = node_position (node);
+  return (position >= (uintptr_t)threshold);
+}
+
 /* Return the first element of a non-empty ordered set of nodes.  */
 static inline gl_list_node_t
 gl_oset_first (gl_oset_t set)
@@ -100,7 +108,7 @@ gl_oset_first (gl_oset_t set)
 static void
 add_to_bucket (gl_list_t list, gl_list_node_t new_node)
 {
-  size_t index = new_node->h.hashcode % list->table_size;
+  size_t bucket = new_node->h.hashcode % list->table_size;
 
   /* If no duplicates are allowed, multiple nodes are not needed.  */
   if (list->base.allow_duplicates)
@@ -110,7 +118,7 @@ add_to_bucket (gl_list_t list, gl_list_node_t new_node)
       gl_listelement_equals_fn equals = list->base.equals_fn;
       gl_hash_entry_t *entryp;
 
-      for (entryp = &list->table[index]; *entryp != NULL; entryp = &(*entryp)->hash_next)
+      for (entryp = &list->table[bucket]; *entryp != NULL; entryp = &(*entryp)->hash_next)
 	{
 	  gl_hash_entry_t entry = *entryp;
 
@@ -143,13 +151,12 @@ add_to_bucket (gl_list_t list, gl_list_node_t new_node)
 
 		      nodes =
 			gl_oset_create_empty (OSET_TREE_FLAVOR,
-					      compare_by_position);
+					      compare_by_position, NULL);
 
 		      gl_oset_add (nodes, node);
 		      gl_oset_add (nodes, new_node);
 
-		      multi_entry =
-			(struct gl_multiple_nodes *) xmalloc (sizeof (struct gl_multiple_nodes));
+		      multi_entry = XMALLOC (struct gl_multiple_nodes);
 		      multi_entry->h.hash_next = entry->hash_next;
 		      multi_entry->h.hashcode = entry->hashcode;
 		      multi_entry->magic = MULTIPLE_NODES_MAGIC;
@@ -162,8 +169,8 @@ add_to_bucket (gl_list_t list, gl_list_node_t new_node)
 	}
     }
   /* If no duplicates are allowed, multiple nodes are not needed.  */
-  new_node->h.hash_next = list->table[index];
-  list->table[index] = &new_node->h;
+  new_node->h.hash_next = list->table[bucket];
+  list->table[bucket] = &new_node->h;
 }
 
 /* Remove a node from the hash table structure.
@@ -175,7 +182,7 @@ add_to_bucket (gl_list_t list, gl_list_node_t new_node)
 static void
 remove_from_bucket (gl_list_t list, gl_list_node_t old_node)
 {
-  size_t index = old_node->h.hashcode % list->table_size;
+  size_t bucket = old_node->h.hashcode % list->table_size;
 
   if (list->base.allow_duplicates)
     {
@@ -184,7 +191,7 @@ remove_from_bucket (gl_list_t list, gl_list_node_t old_node)
       gl_listelement_equals_fn equals = list->base.equals_fn;
       gl_hash_entry_t *entryp;
 
-      for (entryp = &list->table[index]; ; entryp = &(*entryp)->hash_next)
+      for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next)
 	{
 	  gl_hash_entry_t entry = *entryp;
 
@@ -230,7 +237,7 @@ remove_from_bucket (gl_list_t list, gl_list_node_t old_node)
       /* If no duplicates are allowed, multiple nodes are not needed.  */
       gl_hash_entry_t *entryp;
 
-      for (entryp = &list->table[index]; ; entryp = &(*entryp)->hash_next)
+      for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next)
 	{
 	  if (*entryp == &old_node->h)
 	    {