From 3589a8a7bc99cdec5f68ce72f70bc5d1c4258faf Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Mon, 17 Jul 2006 11:27:35 +0000 Subject: [PATCH] Common code of several ordered list implementations. --- lib/gl_anytree_oset.h | 248 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 248 insertions(+) create mode 100644 lib/gl_anytree_oset.h diff --git a/lib/gl_anytree_oset.h b/lib/gl_anytree_oset.h new file mode 100644 index 0000000000..84286bdd80 --- /dev/null +++ b/lib/gl_anytree_oset.h @@ -0,0 +1,248 @@ +/* Ordered set data type implemented by a binary tree. + Copyright (C) 2006 Free Software Foundation, Inc. + Written by Bruno Haible , 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 2, 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, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +/* Common code of gl_avltree_oset.c and gl_rbtree_oset.c. */ + +/* An item on the stack used for iterating across the elements. */ +typedef struct +{ + gl_oset_node_t node; + bool rightp; +} iterstack_item_t; + +/* A stack used for iterating across the elements. */ +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) +{ + struct gl_oset_impl *set = + (struct gl_oset_impl *) xmalloc (sizeof (struct gl_oset_impl)); + + set->base.vtable = implementation; + set->base.compar_fn = compar_fn; + set->root = NULL; + set->count = 0; + + return set; +} + +static size_t +gl_tree_size (gl_oset_t set) +{ + return set->count; +} + +static bool +gl_tree_search (gl_oset_t set, const void *elt) +{ + gl_setelement_compar_fn compar = set->base.compar_fn; + gl_oset_node_t node; + + for (node = set->root; node != NULL; ) + { + int cmp = (compar != NULL + ? compar (node->value, elt) + : (node->value > elt ? 1 : + node->value < elt ? -1 : 0)); + + if (cmp < 0) + node = node->right; + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + /* We have an element equal to ELT. */ + return true; + } + return false; +} + +static gl_oset_node_t +gl_tree_search_node (gl_oset_t set, const void *elt) +{ + gl_setelement_compar_fn compar = set->base.compar_fn; + gl_oset_node_t node; + + for (node = set->root; node != NULL; ) + { + int cmp = (compar != NULL + ? compar (node->value, elt) + : (node->value > elt ? 1 : + node->value < elt ? -1 : 0)); + + if (cmp < 0) + node = node->right; + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + /* We have an element equal to ELT. */ + return node; + } + return NULL; +} + +static bool +gl_tree_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); + return true; + } + + compar = set->base.compar_fn; + + for (;;) + { + int cmp = (compar != NULL + ? 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; + } + else if (cmp > 0) + { + if (node->left == NULL) + { + gl_tree_add_before (set, node, elt); + return true; + } + node = node->left; + } + else /* cmp == 0 */ + return false; + } +} + +static bool +gl_tree_remove (gl_oset_t set, const void *elt) +{ + gl_oset_node_t node = gl_tree_search_node (set, elt); + + if (node != NULL) + return gl_tree_remove_node (set, node); + else + return false; +} + +static void +gl_tree_oset_free (gl_oset_t set) +{ + /* Iterate across all elements in post-order. */ + gl_oset_node_t node = set->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. */ + free (node); + } + /* Descend on right branch. */ + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; + } + done_iterate: + free (set); +} + +/* --------------------- gl_oset_iterator_t Data Type --------------------- */ + +static gl_oset_iterator_t +gl_tree_iterator (gl_oset_t set) +{ + gl_oset_iterator_t result; + gl_oset_node_t node; + + result.vtable = set->base.vtable; + result.set = set; + /* Start node is the leftmost node. */ + node = set->root; + if (node != NULL) + while (node->left != NULL) + node = node->left; + result.p = node; + /* End point is past the rightmost node. */ + result.q = NULL; + + return result; +} + +static bool +gl_tree_iterator_next (gl_oset_iterator_t *iterator, const void **eltp) +{ + if (iterator->p != iterator->q) + { + gl_oset_node_t node = (gl_oset_node_t) iterator->p; + *eltp = node->value; + /* 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_oset_iterator_t *iterator) +{ +} -- 2.30.2