X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_anytree_oset.h;h=c0a0a2f9efb166bc0b68e3b9e0b074a8587cb94d;hb=79a3d2d10ebf29fb4e73716ae1b72fc5d20486a5;hp=84286bdd809eb1eda8012c5409d041e2161cd942;hpb=3589a8a7bc99cdec5f68ce72f70bc5d1c4258faf;p=gnulib.git diff --git a/lib/gl_anytree_oset.h b/lib/gl_anytree_oset.h index 84286bdd8..c0a0a2f9e 100644 --- a/lib/gl_anytree_oset.h +++ b/lib/gl_anytree_oset.h @@ -1,11 +1,11 @@ /* Ordered set data type implemented by a binary tree. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006-2007, 2009-2011 Free Software Foundation, Inc. Written by Bruno Haible , 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 . */ /* Common code of gl_avltree_oset.c and gl_rbtree_oset.c. */ @@ -29,14 +28,19 @@ typedef struct typedef iterstack_item_t iterstack_t[MAXHEIGHT]; static gl_oset_t -gl_tree_create_empty (gl_oset_implementation_t implementation, - gl_setelement_compar_fn compar_fn) +gl_tree_nx_create_empty (gl_oset_implementation_t implementation, + gl_setelement_compar_fn compar_fn, + gl_setelement_dispose_fn dispose_fn) { struct gl_oset_impl *set = - (struct gl_oset_impl *) xmalloc (sizeof (struct gl_oset_impl)); + (struct gl_oset_impl *) malloc (sizeof (struct gl_oset_impl)); + + if (set == NULL) + return NULL; set->base.vtable = implementation; set->base.compar_fn = compar_fn; + set->base.dispose_fn = dispose_fn; set->root = NULL; set->count = 0; @@ -58,17 +62,52 @@ gl_tree_search (gl_oset_t set, const void *elt) for (node = set->root; node != NULL; ) { int cmp = (compar != NULL - ? compar (node->value, elt) - : (node->value > elt ? 1 : - node->value < elt ? -1 : 0)); + ? compar (node->value, elt) + : (node->value > elt ? 1 : + node->value < elt ? -1 : 0)); 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. */ - return true; + /* We have an element equal to ELT. */ + return true; + } + return false; +} + +static bool +gl_tree_search_atleast (gl_oset_t set, + gl_setelement_threshold_fn threshold_fn, + const void *threshold, + const void **eltp) +{ + gl_oset_node_t node; + + for (node = set->root; node != NULL; ) + { + if (! threshold_fn (node->value, threshold)) + node = node->right; + else + { + /* We have an element >= VALUE. But we need the leftmost such + element. */ + gl_oset_node_t found = node; + node = node->left; + for (; node != NULL; ) + { + if (! threshold_fn (node->value, threshold)) + node = node->right; + else + { + found = node; + node = node->left; + } + } + *eltp = found->value; + return true; + } } return false; } @@ -82,30 +121,31 @@ gl_tree_search_node (gl_oset_t set, const void *elt) for (node = set->root; node != NULL; ) { int cmp = (compar != NULL - ? compar (node->value, elt) - : (node->value > elt ? 1 : - node->value < elt ? -1 : 0)); + ? compar (node->value, elt) + : (node->value > elt ? 1 : + node->value < elt ? -1 : 0)); 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. */ - return node; + /* We have an element equal to ELT. */ + return node; } return NULL; } -static bool -gl_tree_add (gl_oset_t set, const void *elt) +static int +gl_tree_nx_add (gl_oset_t set, const void *elt) { gl_setelement_compar_fn compar; gl_oset_node_t node = set->root; if (node == NULL) { - gl_tree_add_first (set, elt); + if (gl_tree_nx_add_first (set, elt) == NULL) + return -1; return true; } @@ -114,30 +154,32 @@ gl_tree_add (gl_oset_t set, const void *elt) for (;;) { int cmp = (compar != NULL - ? compar (node->value, elt) - : (node->value > elt ? 1 : - node->value < elt ? -1 : 0)); + ? compar (node->value, elt) + : (node->value > elt ? 1 : + node->value < elt ? -1 : 0)); if (cmp < 0) - { - if (node->right == NULL) - { - gl_tree_add_after (set, node, elt); - return true; - } - node = node->right; - } + { + if (node->right == NULL) + { + if (gl_tree_nx_add_after (set, node, elt) == NULL) + return -1; + return true; + } + node = node->right; + } else if (cmp > 0) - { - if (node->left == NULL) - { - gl_tree_add_before (set, node, elt); - return true; - } - node = node->left; - } + { + if (node->left == NULL) + { + if (gl_tree_nx_add_before (set, node, elt) == NULL) + return -1; + return true; + } + node = node->left; + } else /* cmp == 0 */ - return false; + return false; } } @@ -164,26 +206,28 @@ gl_tree_oset_free (gl_oset_t set) { /* 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 (set->base.dispose_fn != NULL) + set->base.dispose_fn (node->value); + free (node); + } /* Descend on right branch. */ stack_ptr->rightp = true; node = node->right; @@ -211,6 +255,11 @@ gl_tree_iterator (gl_oset_t set) 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; } @@ -224,17 +273,17 @@ gl_tree_iterator_next (gl_oset_iterator_t *iterator, const void **eltp) *eltp = node->value; /* 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; }