| /* Sequential list data type implemented by a binary tree. | |
| Copyright (C) 2006-2026 Free Software Foundation, Inc. | |
| Written by Bruno Haible <bruno@clisp.org>, 2006. | |
| This file is free software: you can redistribute it and/or modify | |
| it under the terms of the GNU Lesser General Public License as | |
| published by the Free Software Foundation; either version 2.1 of the | |
| License, or (at your option) any later version. | |
| This file 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 Lesser General Public License for more details. | |
| You should have received a copy of the GNU Lesser 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_ATTRIBUTE_PURE | |
| gl_tree_size (gl_list_t list) | |
| { | |
| return (list->root != NULL ? list->root->branch_size : 0); | |
| } | |
| static const void * _GL_ATTRIBUTE_PURE | |
| gl_tree_node_value (gl_list_t _GL_UNNAMED (list), gl_list_node_t node) | |
| { | |
| return node->value; | |
| } | |
| static int | |
| gl_tree_node_nx_set_value (_GL_ATTRIBUTE_MAYBE_UNUSED 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 _GL_UNNAMED (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 _GL_UNNAMED (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; | |
| } | |
| static gl_list_node_t _GL_ATTRIBUTE_PURE | |
| gl_tree_first_node (gl_list_t list) | |
| { | |
| gl_list_node_t node = list->root; | |
| if (node != NULL) | |
| { | |
| while (node->left != NULL) | |
| node = node->left; | |
| } | |
| return node; | |
| } | |
| static gl_list_node_t _GL_ATTRIBUTE_PURE | |
| gl_tree_last_node (gl_list_t list) | |
| { | |
| gl_list_node_t node = list->root; | |
| if (node != NULL) | |
| { | |
| while (node->right != NULL) | |
| node = node->right; | |
| } | |
| 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_ATTRIBUTE_PURE | |
| 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_ATTRIBUTE_PURE | |
| 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_ATTRIBUTE_PURE | |
| gl_tree_iterator (gl_list_t list) | |
| { | |
| gl_list_iterator_t result; | |
| result.vtable = list->base.vtable; | |
| result.list = list; | |
| { | |
| /* Start node is the leftmost node. */ | |
| gl_list_node_t 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_ATTRIBUTE_PURE | |
| 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 *_GL_UNNAMED (iterator)) | |
| { | |
| } | |
| /* ---------------------- Sorted gl_list_t Data Type ---------------------- */ | |
| static gl_list_node_t _GL_ATTRIBUTE_PURE | |
| gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, | |
| const void *elt) | |
| { | |
| for (gl_list_node_t 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_ATTRIBUTE_PURE | |
| gl_tree_sortedlist_search_from_to (gl_list_t list, | |
| gl_listelement_compar_fn compar, | |
| size_t low, size_t high, | |
| const void *elt) | |
| { | |
| if (!(low <= high | |
| && high <= (list->root != NULL ? list->root->branch_size : 0))) | |
| /* Invalid arguments. */ | |
| abort (); | |
| for (gl_list_node_t 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_ATTRIBUTE_PURE | |
| 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_ATTRIBUTE_PURE | |
| gl_tree_sortedlist_indexof_from_to (gl_list_t list, | |
| gl_listelement_compar_fn compar, | |
| size_t low, size_t high, | |
| const void *elt) | |
| { | |
| if (!(low <= high | |
| && high <= (list->root != NULL ? list->root->branch_size : 0))) | |
| /* Invalid arguments. */ | |
| abort (); | |
| gl_list_node_t node; | |
| size_t position; | |
| 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; | |
| } |