/* Sequential list data type implemented by a binary tree.
- Copyright (C) 2006 Free Software Foundation, Inc.
+ Copyright (C) 2006-2011 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
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
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)
{
{
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;
{
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;
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;
}
}
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;
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;
#if !WITH_HASHTABLE
static gl_list_node_t
-gl_tree_search (gl_list_t list, const void *elt)
+gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
+ const void *elt)
{
- gl_listelement_equals_fn equals = list->base.equals_fn;
- /* Iterate across all elements. */
- gl_list_node_t node = list->root;
- iterstack_t stack;
- iterstack_item_t *stack_ptr = &stack[0];
-
- for (;;)
- {
- /* Descend on left branch. */
- for (;;)
- {
- 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])
- 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;
- /* Descend on right branch. */
- stack_ptr->rightp = true;
- node = node->right;
- stack_ptr++;
- }
+ if (!(start_index <= end_index
+ && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
+ /* Invalid arguments. */
+ abort ();
+ {
+ gl_listelement_equals_fn equals = list->base.equals_fn;
+ /* Iterate across all elements. */
+ gl_list_node_t node = list->root;
+ iterstack_t stack;
+ iterstack_item_t *stack_ptr = &stack[0];
+ size_t index = 0;
+
+ 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++;
+ }
+ }
+ 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++;
+ }
+ }
+ }
}
static size_t
-gl_tree_indexof (gl_list_t list, const void *elt)
+gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
+ const void *elt)
{
- gl_listelement_equals_fn equals = list->base.equals_fn;
- /* Iterate across all elements. */
- gl_list_node_t node = list->root;
- iterstack_t stack;
- iterstack_item_t *stack_ptr = &stack[0];
- size_t index = 0;
-
- for (;;)
- {
- /* Descend on left branch. */
- for (;;)
- {
- 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])
- 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++;
- /* Descend on right branch. */
- stack_ptr->rightp = true;
- node = node->right;
- stack_ptr++;
- }
+ if (!(start_index <= end_index
+ && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
+ /* Invalid arguments. */
+ abort ();
+ {
+ gl_listelement_equals_fn equals = list->base.equals_fn;
+ /* Iterate across all elements. */
+ gl_list_node_t node = list->root;
+ iterstack_t stack;
+ iterstack_item_t *stack_ptr = &stack[0];
+ size_t index = 0;
+
+ 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++;
+ }
+ }
+ 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++;
+ }
+ }
+ }
}
#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);
/* 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
static bool
gl_tree_remove (gl_list_t list, const void *elt)
{
- gl_list_node_t node = gl_tree_search (list, elt);
+ if (list->root != NULL)
+ {
+ gl_list_node_t node =
+ gl_tree_search_from_to (list, 0, list->root->branch_size, elt);
- if (node != NULL)
- return gl_tree_remove_node (list, node);
- else
- return false;
+ if (node != NULL)
+ return gl_tree_remove_node (list, node);
+ }
+ return false;
}
#if !WITH_HASHTABLE
{
/* 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;
result.p = node;
/* End point is past the rightmost node. */
result.q = NULL;
+#ifdef lint
+ result.i = 0;
+ result.j = 0;
+ result.count = 0;
+#endif
return result;
}
result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
/* End point is the node at position end_index. */
result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
+#ifdef lint
+ result.i = 0;
+ result.j = 0;
+ result.count = 0;
+#endif
return result;
}
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;
}
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;
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_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)
+ const void *elt)
{
gl_list_node_t node;
size_t position;
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_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)
+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)