| /* Sequential list data type implemented by a binary tree. |
| Copyright (C) 2006-2020 Free Software Foundation, Inc. |
| Written by Bruno Haible <bruno@clisp.org>, 2006. |
| |
| 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 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 |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 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, see <https://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_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 *) 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 *) 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 |
| gl_tree_size (gl_list_t list) |
| { |
| return (list->root != NULL ? list->root->branch_size : 0); |
| } |
| |
| static const void * |
| 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_ATTRIBUTE_PURE |
| gl_tree_next_node (gl_list_t list, gl_list_node_t node) |
| { |
| if (node->right != NULL) |
| { |
| 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; |
| } |
| return node; |
| } |
| |
| static gl_list_node_t _GL_ATTRIBUTE_PURE |
| gl_tree_previous_node (gl_list_t list, gl_list_node_t node) |
| { |
| if (node->left != NULL) |
| { |
| node = node->left; |
| while (node->right != NULL) |
| node = node->right; |
| } |
| else |
| { |
| while (node->parent != NULL && node->parent->left == node) |
| node = node->parent; |
| node = node->parent; |
| } |
| return node; |
| } |
| |
| /* Returns the node at the given position < gl_tree_size (list). */ |
| static gl_list_node_t _GL_ATTRIBUTE_PURE |
| node_at (gl_list_node_t root, size_t position) |
| { |
| /* Here we know that root != NULL. */ |
| gl_list_node_t node = root; |
| |
| for (;;) |
| { |
| if (node->left != NULL) |
| { |
| if (position < node->left->branch_size) |
| { |
| node = node->left; |
| continue; |
| } |
| position -= node->left->branch_size; |
| } |
| if (position == 0) |
| break; |
| position--; |
| node = node->right; |
| } |
| return node; |
| } |
| |
| static const void * _GL_ATTRIBUTE_PURE |
| gl_tree_get_at (gl_list_t list, size_t position) |
| { |
| gl_list_node_t node = list->root; |
| |
| if (!(node != NULL && position < node->branch_size)) |
| /* Invalid argument. */ |
| abort (); |
| node = node_at (node, position); |
| return node->value; |
| } |
| |
| static gl_list_node_t |
| gl_tree_nx_set_at (gl_list_t list, size_t position, const void *elt) |
| { |
| gl_list_node_t node = list->root; |
| |
| if (!(node != NULL && position < node->branch_size)) |
| /* Invalid argument. */ |
| abort (); |
| node = node_at (node, position); |
| #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 NULL; |
| } |
| } |
| else |
| node->value = elt; |
| } |
| #else |
| node->value = elt; |
| #endif |
| return node; |
| } |
| |
| #if !WITH_HASHTABLE |
| |
| 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) |
| { |
| 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_from_to (gl_list_t list, size_t start_index, size_t end_index, |
| const void *elt) |
| { |
| 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_nx_add_at (gl_list_t list, size_t position, const void *elt) |
| { |
| size_t count = (list->root != NULL ? list->root->branch_size : 0); |
| |
| if (!(position <= count)) |
| /* Invalid argument. */ |
| abort (); |
| if (position == count) |
| return gl_tree_nx_add_last (list, elt); |
| else |
| 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 |
| gl_tree_remove_at (gl_list_t list, size_t position) |
| { |
| gl_list_node_t node = list->root; |
| |
| if (!(node != NULL && position < node->branch_size)) |
| /* Invalid argument. */ |
| abort (); |
| node = node_at (node, position); |
| return gl_tree_remove_node (list, node); |
| } |
| |
| static bool |
| 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); |
| |
| if (node != NULL) |
| return gl_tree_remove_node (list, node); |
| } |
| return false; |
| } |
| |
| #if !WITH_HASHTABLE |
| |
| static void |
| gl_tree_list_free (gl_list_t list) |
| { |
| /* Iterate across all elements in post-order. */ |
| 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]) |
| 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; |
| stack_ptr++; |
| } |
| done_iterate: |
| free (list); |
| } |
| |
| #endif |
| |
| /* --------------------- gl_list_iterator_t Data Type --------------------- */ |
| |
| static gl_list_iterator_t |
| gl_tree_iterator (gl_list_t list) |
| { |
| gl_list_iterator_t result; |
| gl_list_node_t node; |
| |
| result.vtable = list->base.vtable; |
| result.list = list; |
| /* Start node is the leftmost node. */ |
| node = list->root; |
| if (node != NULL) |
| while (node->left != NULL) |
| node = node->left; |
| result.p = node; |
| /* End point is past the rightmost node. */ |
| result.q = NULL; |
| #if defined GCC_LINT || defined lint |
| result.i = 0; |
| result.j = 0; |
| result.count = 0; |
| #endif |
| |
| return result; |
| } |
| |
| static gl_list_iterator_t |
| gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index) |
| { |
| size_t count = (list->root != NULL ? list->root->branch_size : 0); |
| gl_list_iterator_t result; |
| |
| if (!(start_index <= end_index && end_index <= count)) |
| /* Invalid arguments. */ |
| abort (); |
| result.vtable = list->base.vtable; |
| result.list = list; |
| /* Start node is the node at position start_index. */ |
| 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); |
| #if defined GCC_LINT || defined 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) |
| { |
| if (iterator->p != iterator->q) |
| { |
| gl_list_node_t node = (gl_list_node_t) iterator->p; |
| *eltp = node->value; |
| if (nodep != NULL) |
| *nodep = node; |
| /* Advance to the next node. */ |
| if (node->right != NULL) |
| { |
| 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; |
| } |
| iterator->p = node; |
| return true; |
| } |
| else |
| return false; |
| } |
| |
| static void |
| gl_tree_iterator_free (gl_list_iterator_t *iterator) |
| { |
| } |
| |
| /* ---------------------- Sorted gl_list_t Data Type ---------------------- */ |
| |
| static gl_list_node_t |
| gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, |
| const void *elt) |
| { |
| gl_list_node_t node; |
| |
| for (node = list->root; node != NULL; ) |
| { |
| int cmp = compar (node->value, elt); |
| |
| if (cmp < 0) |
| 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; ) |
| { |
| 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) |
| { |
| gl_list_node_t node; |
| size_t position; |
| |
| for (node = list->root, position = 0; node != NULL; ) |
| { |
| int cmp = compar (node->value, elt); |
| |
| if (cmp < 0) |
| { |
| if (node->left != NULL) |
| position += node->left->branch_size; |
| position++; |
| 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; ) |
| { |
| 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_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_nx_add_first (list, elt); |
| |
| for (;;) |
| { |
| int cmp = compar (node->value, elt); |
| |
| if (cmp < 0) |
| { |
| 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_nx_add_before (list, node, elt); |
| node = node->left; |
| } |
| else /* cmp == 0 */ |
| 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) |
| { |
| gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt); |
| if (node != NULL) |
| return gl_tree_remove_node (list, node); |
| else |
| return false; |
| } |
