diff options
Diffstat (limited to 'mcastseed/lib/gl_anytree_list2.h')
| -rw-r--r-- | mcastseed/lib/gl_anytree_list2.h | 940 |
1 files changed, 0 insertions, 940 deletions
diff --git a/mcastseed/lib/gl_anytree_list2.h b/mcastseed/lib/gl_anytree_list2.h deleted file mode 100644 index 7e6fe45..0000000 --- a/mcastseed/lib/gl_anytree_list2.h +++ /dev/null @@ -1,940 +0,0 @@ -/* Sequential list data type implemented by a binary tree. - Copyright (C) 2006-2016 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 <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_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; -} - -/* Return 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; -} |