444 lines
12 KiB
C
Executable File
444 lines
12 KiB
C
Executable File
/* Ordered set data type implemented by a binary tree.
|
|
Copyright (C) 2006-2007, 2009-2024 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_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_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 *) 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;
|
|
|
|
return set;
|
|
}
|
|
|
|
static size_t _GL_ATTRIBUTE_PURE
|
|
gl_tree_size (gl_oset_t set)
|
|
{
|
|
return set->count;
|
|
}
|
|
|
|
/* Returns the next node in the tree, or NULL if there is none. */
|
|
static inline gl_oset_node_t _GL_ATTRIBUTE_PURE
|
|
gl_tree_next_node (gl_oset_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;
|
|
}
|
|
|
|
/* Returns the previous node in the tree, or NULL if there is none. */
|
|
static inline gl_oset_node_t _GL_ATTRIBUTE_PURE
|
|
gl_tree_prev_node (gl_oset_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 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 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 >= THRESHOLD. 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;
|
|
}
|
|
|
|
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 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)
|
|
{
|
|
if (gl_tree_nx_add_first (set, elt) == NULL)
|
|
return -1;
|
|
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)
|
|
{
|
|
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)
|
|
{
|
|
if (gl_tree_nx_add_before (set, node, elt) == NULL)
|
|
return -1;
|
|
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 int
|
|
gl_tree_update (gl_oset_t set, const void *elt,
|
|
void (*action) (const void * /*elt*/, void * /*action_data*/),
|
|
void *action_data)
|
|
{
|
|
/* Like gl_tree_remove, action (...), gl_tree_nx_add, except that we don't
|
|
actually remove ELT. */
|
|
/* Remember the old node. Don't free it. */
|
|
gl_oset_node_t old_node = gl_tree_search_node (set, elt);
|
|
/* Invoke ACTION. */
|
|
action (elt, action_data);
|
|
/* Determine where to put the node now. */
|
|
if (old_node != NULL)
|
|
{
|
|
if (set->count > 1)
|
|
{
|
|
gl_setelement_compar_fn compar = set->base.compar_fn;
|
|
|
|
gl_oset_node_t prev_node = gl_tree_prev_node (old_node);
|
|
gl_oset_node_t next_node = gl_tree_next_node (old_node);
|
|
if (!(compar != NULL
|
|
? (prev_node == NULL || compar (prev_node->value, elt) < 0)
|
|
&& (next_node == NULL || compar (next_node->value, elt) > 0)
|
|
: (prev_node == NULL || prev_node->value < elt)
|
|
&& (next_node == NULL || next_node->value > elt)))
|
|
{
|
|
/* old_node needs to move in the tree. */
|
|
gl_oset_node_t node;
|
|
|
|
/* Remove the node from the tree. Don't free it. */
|
|
gl_tree_remove_node_no_free (set, old_node);
|
|
|
|
node = set->root;
|
|
|
|
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_node_after (set, node, old_node);
|
|
return true;
|
|
}
|
|
node = node->right;
|
|
}
|
|
else if (cmp > 0)
|
|
{
|
|
if (node->left == NULL)
|
|
{
|
|
gl_tree_add_node_before (set, node, old_node);
|
|
return true;
|
|
}
|
|
node = node->left;
|
|
}
|
|
else /* cmp == 0 */
|
|
{
|
|
/* Two elements are the same. */
|
|
NODE_PAYLOAD_DISPOSE (set, old_node)
|
|
free (old_node);
|
|
return -1;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
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. */
|
|
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;
|
|
stack_ptr++;
|
|
}
|
|
done_iterate:
|
|
free (set);
|
|
}
|
|
|
|
/* --------------------- gl_oset_iterator_t Data Type --------------------- */
|
|
|
|
static gl_oset_iterator_t _GL_ATTRIBUTE_PURE
|
|
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;
|
|
#if defined GCC_LINT || defined lint
|
|
result.i = 0;
|
|
result.j = 0;
|
|
result.count = 0;
|
|
#endif
|
|
|
|
return result;
|
|
}
|
|
|
|
static gl_oset_iterator_t
|
|
gl_tree_iterator_atleast (gl_oset_t set,
|
|
gl_setelement_threshold_fn threshold_fn,
|
|
const void *threshold)
|
|
{
|
|
gl_oset_iterator_t result;
|
|
gl_oset_node_t node;
|
|
|
|
result.vtable = set->base.vtable;
|
|
result.set = set;
|
|
/* 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
|
|
|
|
for (node = set->root; node != NULL; )
|
|
{
|
|
if (! threshold_fn (node->value, threshold))
|
|
node = node->right;
|
|
else
|
|
{
|
|
/* We have an element >= THRESHOLD. 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;
|
|
}
|
|
}
|
|
result.p = found;
|
|
return result;
|
|
}
|
|
}
|
|
result.p = 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. */
|
|
node = gl_tree_next_node (node);
|
|
iterator->p = node;
|
|
return true;
|
|
}
|
|
else
|
|
return false;
|
|
}
|
|
|
|
static void
|
|
gl_tree_iterator_free (_GL_ATTRIBUTE_MAYBE_UNUSED gl_oset_iterator_t *iterator)
|
|
{
|
|
}
|