|
Packit |
6c4009 |
/* Copyright (C) 1995-2018 Free Software Foundation, Inc.
|
|
Packit |
6c4009 |
This file is part of the GNU C Library.
|
|
Packit |
6c4009 |
Contributed by Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>, 1997.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
The GNU C Library is free software; you can redistribute it and/or
|
|
Packit |
6c4009 |
modify it under the terms of the GNU Lesser General Public
|
|
Packit |
6c4009 |
License as published by the Free Software Foundation; either
|
|
Packit |
6c4009 |
version 2.1 of the License, or (at your option) any later version.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
The GNU C Library is distributed in the hope that it will be useful,
|
|
Packit |
6c4009 |
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit |
6c4009 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
Packit |
6c4009 |
Lesser General Public License for more details.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
You should have received a copy of the GNU Lesser General Public
|
|
Packit |
6c4009 |
License along with the GNU C Library; if not, see
|
|
Packit |
6c4009 |
<http://www.gnu.org/licenses/>. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Tree search for red/black trees.
|
|
Packit |
6c4009 |
The algorithm for adding nodes is taken from one of the many "Algorithms"
|
|
Packit |
6c4009 |
books by Robert Sedgewick, although the implementation differs.
|
|
Packit |
6c4009 |
The algorithm for deleting nodes can probably be found in a book named
|
|
Packit |
6c4009 |
"Introduction to Algorithms" by Cormen/Leiserson/Rivest. At least that's
|
|
Packit |
6c4009 |
the book that my professor took most algorithms from during the "Data
|
|
Packit |
6c4009 |
Structures" course...
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
Totally public domain. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Red/black trees are binary trees in which the edges are colored either red
|
|
Packit |
6c4009 |
or black. They have the following properties:
|
|
Packit |
6c4009 |
1. The number of black edges on every path from the root to a leaf is
|
|
Packit |
6c4009 |
constant.
|
|
Packit |
6c4009 |
2. No two red edges are adjacent.
|
|
Packit |
6c4009 |
Therefore there is an upper bound on the length of every path, it's
|
|
Packit |
6c4009 |
O(log n) where n is the number of nodes in the tree. No path can be longer
|
|
Packit |
6c4009 |
than 1+2*P where P is the length of the shortest path in the tree.
|
|
Packit |
6c4009 |
Useful for the implementation:
|
|
Packit |
6c4009 |
3. If one of the children of a node is NULL, then the other one is red
|
|
Packit |
6c4009 |
(if it exists).
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
In the implementation, not the edges are colored, but the nodes. The color
|
|
Packit |
6c4009 |
interpreted as the color of the edge leading to this node. The color is
|
|
Packit |
6c4009 |
meaningless for the root node, but we color the root node black for
|
|
Packit |
6c4009 |
convenience. All added nodes are red initially.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
Adding to a red/black tree is rather easy. The right place is searched
|
|
Packit |
6c4009 |
with a usual binary tree search. Additionally, whenever a node N is
|
|
Packit |
6c4009 |
reached that has two red successors, the successors are colored black and
|
|
Packit |
6c4009 |
the node itself colored red. This moves red edges up the tree where they
|
|
Packit |
6c4009 |
pose less of a problem once we get to really insert the new node. Changing
|
|
Packit |
6c4009 |
N's color to red may violate rule 2, however, so rotations may become
|
|
Packit |
6c4009 |
necessary to restore the invariants. Adding a new red leaf may violate
|
|
Packit |
6c4009 |
the same rule, so afterwards an additional check is run and the tree
|
|
Packit |
6c4009 |
possibly rotated.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
Deleting is hairy. There are mainly two nodes involved: the node to be
|
|
Packit |
6c4009 |
deleted (n1), and another node that is to be unchained from the tree (n2).
|
|
Packit |
6c4009 |
If n1 has a successor (the node with a smallest key that is larger than
|
|
Packit |
6c4009 |
n1), then the successor becomes n2 and its contents are copied into n1,
|
|
Packit |
6c4009 |
otherwise n1 becomes n2.
|
|
Packit |
6c4009 |
Unchaining a node may violate rule 1: if n2 is black, one subtree is
|
|
Packit |
6c4009 |
missing one black edge afterwards. The algorithm must try to move this
|
|
Packit |
6c4009 |
error upwards towards the root, so that the subtree that does not have
|
|
Packit |
6c4009 |
enough black edges becomes the whole tree. Once that happens, the error
|
|
Packit |
6c4009 |
has disappeared. It may not be necessary to go all the way up, since it
|
|
Packit |
6c4009 |
is possible that rotations and recoloring can fix the error before that.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
Although the deletion algorithm must walk upwards through the tree, we
|
|
Packit |
6c4009 |
do not store parent pointers in the nodes. Instead, delete allocates a
|
|
Packit |
6c4009 |
small array of parent pointers and fills it while descending the tree.
|
|
Packit |
6c4009 |
Since we know that the length of a path is O(log n), where n is the number
|
|
Packit |
6c4009 |
of nodes, this is likely to use less memory. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Tree rotations look like this:
|
|
Packit |
6c4009 |
A C
|
|
Packit |
6c4009 |
/ \ / \
|
|
Packit |
6c4009 |
B C A G
|
|
Packit |
6c4009 |
/ \ / \ --> / \
|
|
Packit |
6c4009 |
D E F G B F
|
|
Packit |
6c4009 |
/ \
|
|
Packit |
6c4009 |
D E
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
In this case, A has been rotated left. This preserves the ordering of the
|
|
Packit |
6c4009 |
binary tree. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#include <assert.h>
|
|
Packit |
6c4009 |
#include <stdalign.h>
|
|
Packit |
6c4009 |
#include <stddef.h>
|
|
Packit |
6c4009 |
#include <stdlib.h>
|
|
Packit |
6c4009 |
#include <string.h>
|
|
Packit |
6c4009 |
#include <search.h>
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Assume malloc returns naturally aligned (alignof (max_align_t))
|
|
Packit |
6c4009 |
pointers so we can use the low bits to store some extra info. This
|
|
Packit |
6c4009 |
works for the left/right node pointers since they are not user
|
|
Packit |
6c4009 |
visible and always allocated by malloc. The user provides the key
|
|
Packit |
6c4009 |
pointer and so that can point anywhere and doesn't have to be
|
|
Packit |
6c4009 |
aligned. */
|
|
Packit |
6c4009 |
#define USE_MALLOC_LOW_BIT 1
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifndef USE_MALLOC_LOW_BIT
|
|
Packit |
6c4009 |
typedef struct node_t
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Callers expect this to be the first element in the structure - do not
|
|
Packit |
6c4009 |
move! */
|
|
Packit |
6c4009 |
const void *key;
|
|
Packit |
6c4009 |
struct node_t *left_node;
|
|
Packit |
6c4009 |
struct node_t *right_node;
|
|
Packit |
6c4009 |
unsigned int is_red:1;
|
|
Packit |
6c4009 |
} *node;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#define RED(N) (N)->is_red
|
|
Packit |
6c4009 |
#define SETRED(N) (N)->is_red = 1
|
|
Packit |
6c4009 |
#define SETBLACK(N) (N)->is_red = 0
|
|
Packit |
6c4009 |
#define SETNODEPTR(NP,P) (*NP) = (P)
|
|
Packit |
6c4009 |
#define LEFT(N) (N)->left_node
|
|
Packit |
6c4009 |
#define LEFTPTR(N) (&(N)->left_node)
|
|
Packit |
6c4009 |
#define SETLEFT(N,L) (N)->left_node = (L)
|
|
Packit |
6c4009 |
#define RIGHT(N) (N)->right_node
|
|
Packit |
6c4009 |
#define RIGHTPTR(N) (&(N)->right_node)
|
|
Packit |
6c4009 |
#define SETRIGHT(N,R) (N)->right_node = (R)
|
|
Packit |
6c4009 |
#define DEREFNODEPTR(NP) (*(NP))
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#else /* USE_MALLOC_LOW_BIT */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
typedef struct node_t
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Callers expect this to be the first element in the structure - do not
|
|
Packit |
6c4009 |
move! */
|
|
Packit |
6c4009 |
const void *key;
|
|
Packit |
6c4009 |
uintptr_t left_node; /* Includes whether the node is red in low-bit. */
|
|
Packit |
6c4009 |
uintptr_t right_node;
|
|
Packit |
6c4009 |
} *node;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#define RED(N) (node)((N)->left_node & ((uintptr_t) 0x1))
|
|
Packit |
6c4009 |
#define SETRED(N) (N)->left_node |= ((uintptr_t) 0x1)
|
|
Packit |
6c4009 |
#define SETBLACK(N) (N)->left_node &= ~((uintptr_t) 0x1)
|
|
Packit |
6c4009 |
#define SETNODEPTR(NP,P) (*NP) = (node)((((uintptr_t)(*NP)) \
|
|
Packit |
6c4009 |
& (uintptr_t) 0x1) | (uintptr_t)(P))
|
|
Packit |
6c4009 |
#define LEFT(N) (node)((N)->left_node & ~((uintptr_t) 0x1))
|
|
Packit |
6c4009 |
#define LEFTPTR(N) (node *)(&(N)->left_node)
|
|
Packit |
6c4009 |
#define SETLEFT(N,L) (N)->left_node = (((N)->left_node & (uintptr_t) 0x1) \
|
|
Packit |
6c4009 |
| (uintptr_t)(L))
|
|
Packit |
6c4009 |
#define RIGHT(N) (node)((N)->right_node)
|
|
Packit |
6c4009 |
#define RIGHTPTR(N) (node *)(&(N)->right_node)
|
|
Packit |
6c4009 |
#define SETRIGHT(N,R) (N)->right_node = (uintptr_t)(R)
|
|
Packit |
6c4009 |
#define DEREFNODEPTR(NP) (node)((uintptr_t)(*(NP)) & ~((uintptr_t) 0x1))
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#endif /* USE_MALLOC_LOW_BIT */
|
|
Packit |
6c4009 |
typedef const struct node_t *const_node;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#undef DEBUGGING
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifdef DEBUGGING
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Routines to check tree invariants. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#define CHECK_TREE(a) check_tree(a)
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
static void
|
|
Packit |
6c4009 |
check_tree_recurse (node p, int d_sofar, int d_total)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
if (p == NULL)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
assert (d_sofar == d_total);
|
|
Packit |
6c4009 |
return;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
check_tree_recurse (LEFT(p), d_sofar + (LEFT(p) && !RED(LEFT(p))),
|
|
Packit |
6c4009 |
d_total);
|
|
Packit |
6c4009 |
check_tree_recurse (RIGHT(p), d_sofar + (RIGHT(p) && !RED(RIGHT(p))),
|
|
Packit |
6c4009 |
d_total);
|
|
Packit |
6c4009 |
if (LEFT(p))
|
|
Packit |
6c4009 |
assert (!(RED(LEFT(p)) && RED(p)));
|
|
Packit |
6c4009 |
if (RIGHT(p))
|
|
Packit |
6c4009 |
assert (!(RED(RIGHT(p)) && RED(p)));
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
static void
|
|
Packit |
6c4009 |
check_tree (node root)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
int cnt = 0;
|
|
Packit |
6c4009 |
node p;
|
|
Packit |
6c4009 |
if (root == NULL)
|
|
Packit |
6c4009 |
return;
|
|
Packit |
6c4009 |
SETBLACK(root);
|
|
Packit |
6c4009 |
for(p = LEFT(root); p; p = LEFT(p))
|
|
Packit |
6c4009 |
cnt += !RED(p);
|
|
Packit |
6c4009 |
check_tree_recurse (root, 0, cnt);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#else
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#define CHECK_TREE(a)
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Possibly "split" a node with two red successors, and/or fix up two red
|
|
Packit |
6c4009 |
edges in a row. ROOTP is a pointer to the lowest node we visited, PARENTP
|
|
Packit |
6c4009 |
and GPARENTP pointers to its parent/grandparent. P_R and GP_R contain the
|
|
Packit |
6c4009 |
comparison values that determined which way was taken in the tree to reach
|
|
Packit |
6c4009 |
ROOTP. MODE is 1 if we need not do the split, but must check for two red
|
|
Packit |
6c4009 |
edges between GPARENTP and ROOTP. */
|
|
Packit |
6c4009 |
static void
|
|
Packit |
6c4009 |
maybe_split_for_insert (node *rootp, node *parentp, node *gparentp,
|
|
Packit |
6c4009 |
int p_r, int gp_r, int mode)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
node root = DEREFNODEPTR(rootp);
|
|
Packit |
6c4009 |
node *rp, *lp;
|
|
Packit |
6c4009 |
node rpn, lpn;
|
|
Packit |
6c4009 |
rp = RIGHTPTR(root);
|
|
Packit |
6c4009 |
rpn = RIGHT(root);
|
|
Packit |
6c4009 |
lp = LEFTPTR(root);
|
|
Packit |
6c4009 |
lpn = LEFT(root);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* See if we have to split this node (both successors red). */
|
|
Packit |
6c4009 |
if (mode == 1
|
|
Packit |
6c4009 |
|| ((rpn) != NULL && (lpn) != NULL && RED(rpn) && RED(lpn)))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* This node becomes red, its successors black. */
|
|
Packit |
6c4009 |
SETRED(root);
|
|
Packit |
6c4009 |
if (rpn)
|
|
Packit |
6c4009 |
SETBLACK(rpn);
|
|
Packit |
6c4009 |
if (lpn)
|
|
Packit |
6c4009 |
SETBLACK(lpn);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* If the parent of this node is also red, we have to do
|
|
Packit |
6c4009 |
rotations. */
|
|
Packit |
6c4009 |
if (parentp != NULL && RED(DEREFNODEPTR(parentp)))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
node gp = DEREFNODEPTR(gparentp);
|
|
Packit |
6c4009 |
node p = DEREFNODEPTR(parentp);
|
|
Packit |
6c4009 |
/* There are two main cases:
|
|
Packit |
6c4009 |
1. The edge types (left or right) of the two red edges differ.
|
|
Packit |
6c4009 |
2. Both red edges are of the same type.
|
|
Packit |
6c4009 |
There exist two symmetries of each case, so there is a total of
|
|
Packit |
6c4009 |
4 cases. */
|
|
Packit |
6c4009 |
if ((p_r > 0) != (gp_r > 0))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Put the child at the top of the tree, with its parent
|
|
Packit |
6c4009 |
and grandparent as successors. */
|
|
Packit |
6c4009 |
SETRED(p);
|
|
Packit |
6c4009 |
SETRED(gp);
|
|
Packit |
6c4009 |
SETBLACK(root);
|
|
Packit |
6c4009 |
if (p_r < 0)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Child is left of parent. */
|
|
Packit |
6c4009 |
SETLEFT(p,rpn);
|
|
Packit |
6c4009 |
SETNODEPTR(rp,p);
|
|
Packit |
6c4009 |
SETRIGHT(gp,lpn);
|
|
Packit |
6c4009 |
SETNODEPTR(lp,gp);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Child is right of parent. */
|
|
Packit |
6c4009 |
SETRIGHT(p,lpn);
|
|
Packit |
6c4009 |
SETNODEPTR(lp,p);
|
|
Packit |
6c4009 |
SETLEFT(gp,rpn);
|
|
Packit |
6c4009 |
SETNODEPTR(rp,gp);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
SETNODEPTR(gparentp,root);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
SETNODEPTR(gparentp,p);
|
|
Packit |
6c4009 |
/* Parent becomes the top of the tree, grandparent and
|
|
Packit |
6c4009 |
child are its successors. */
|
|
Packit |
6c4009 |
SETBLACK(p);
|
|
Packit |
6c4009 |
SETRED(gp);
|
|
Packit |
6c4009 |
if (p_r < 0)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Left edges. */
|
|
Packit |
6c4009 |
SETLEFT(gp,RIGHT(p));
|
|
Packit |
6c4009 |
SETRIGHT(p,gp);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Right edges. */
|
|
Packit |
6c4009 |
SETRIGHT(gp,LEFT(p));
|
|
Packit |
6c4009 |
SETLEFT(p,gp);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Find or insert datum into search tree.
|
|
Packit |
6c4009 |
KEY is the key to be located, ROOTP is the address of tree root,
|
|
Packit |
6c4009 |
COMPAR the ordering function. */
|
|
Packit |
6c4009 |
void *
|
|
Packit |
6c4009 |
__tsearch (const void *key, void **vrootp, __compar_fn_t compar)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
node q, root;
|
|
Packit |
6c4009 |
node *parentp = NULL, *gparentp = NULL;
|
|
Packit |
6c4009 |
node *rootp = (node *) vrootp;
|
|
Packit |
6c4009 |
node *nextp;
|
|
Packit |
6c4009 |
int r = 0, p_r = 0, gp_r = 0; /* No they might not, Mr Compiler. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifdef USE_MALLOC_LOW_BIT
|
|
Packit |
6c4009 |
static_assert (alignof (max_align_t) > 1, "malloc must return aligned ptrs");
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (rootp == NULL)
|
|
Packit |
6c4009 |
return NULL;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* This saves some additional tests below. */
|
|
Packit |
6c4009 |
root = DEREFNODEPTR(rootp);
|
|
Packit |
6c4009 |
if (root != NULL)
|
|
Packit |
6c4009 |
SETBLACK(root);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
CHECK_TREE (root);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
nextp = rootp;
|
|
Packit |
6c4009 |
while (DEREFNODEPTR(nextp) != NULL)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
root = DEREFNODEPTR(rootp);
|
|
Packit |
6c4009 |
r = (*compar) (key, root->key);
|
|
Packit |
6c4009 |
if (r == 0)
|
|
Packit |
6c4009 |
return root;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
maybe_split_for_insert (rootp, parentp, gparentp, p_r, gp_r, 0);
|
|
Packit |
6c4009 |
/* If that did any rotations, parentp and gparentp are now garbage.
|
|
Packit |
6c4009 |
That doesn't matter, because the values they contain are never
|
|
Packit |
6c4009 |
used again in that case. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
nextp = r < 0 ? LEFTPTR(root) : RIGHTPTR(root);
|
|
Packit |
6c4009 |
if (DEREFNODEPTR(nextp) == NULL)
|
|
Packit |
6c4009 |
break;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
gparentp = parentp;
|
|
Packit |
6c4009 |
parentp = rootp;
|
|
Packit |
6c4009 |
rootp = nextp;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
gp_r = p_r;
|
|
Packit |
6c4009 |
p_r = r;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
q = (struct node_t *) malloc (sizeof (struct node_t));
|
|
Packit |
6c4009 |
if (q != NULL)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Make sure the malloc implementation returns naturally aligned
|
|
Packit |
6c4009 |
memory blocks when expected. Or at least even pointers, so we
|
|
Packit |
6c4009 |
can use the low bit as red/black flag. Even though we have a
|
|
Packit |
6c4009 |
static_assert to make sure alignof (max_align_t) > 1 there could
|
|
Packit |
6c4009 |
be an interposed malloc implementation that might cause havoc by
|
|
Packit |
6c4009 |
not obeying the malloc contract. */
|
|
Packit |
6c4009 |
#ifdef USE_MALLOC_LOW_BIT
|
|
Packit |
6c4009 |
assert (((uintptr_t) q & (uintptr_t) 0x1) == 0);
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
SETNODEPTR(nextp,q); /* link new node to old */
|
|
Packit |
6c4009 |
q->key = key; /* initialize new node */
|
|
Packit |
6c4009 |
SETRED(q);
|
|
Packit |
6c4009 |
SETLEFT(q,NULL);
|
|
Packit |
6c4009 |
SETRIGHT(q,NULL);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (nextp != rootp)
|
|
Packit |
6c4009 |
/* There may be two red edges in a row now, which we must avoid by
|
|
Packit |
6c4009 |
rotating the tree. */
|
|
Packit |
6c4009 |
maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
return q;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
libc_hidden_def (__tsearch)
|
|
Packit |
6c4009 |
weak_alias (__tsearch, tsearch)
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Find datum in search tree.
|
|
Packit |
6c4009 |
KEY is the key to be located, ROOTP is the address of tree root,
|
|
Packit |
6c4009 |
COMPAR the ordering function. */
|
|
Packit |
6c4009 |
void *
|
|
Packit |
6c4009 |
__tfind (const void *key, void *const *vrootp, __compar_fn_t compar)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
node root;
|
|
Packit |
6c4009 |
node *rootp = (node *) vrootp;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (rootp == NULL)
|
|
Packit |
6c4009 |
return NULL;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
root = DEREFNODEPTR(rootp);
|
|
Packit |
6c4009 |
CHECK_TREE (root);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
while (DEREFNODEPTR(rootp) != NULL)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
root = DEREFNODEPTR(rootp);
|
|
Packit |
6c4009 |
int r;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
r = (*compar) (key, root->key);
|
|
Packit |
6c4009 |
if (r == 0)
|
|
Packit |
6c4009 |
return root;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
rootp = r < 0 ? LEFTPTR(root) : RIGHTPTR(root);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
return NULL;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
libc_hidden_def (__tfind)
|
|
Packit |
6c4009 |
weak_alias (__tfind, tfind)
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Delete node with given key.
|
|
Packit |
6c4009 |
KEY is the key to be deleted, ROOTP is the address of the root of tree,
|
|
Packit |
6c4009 |
COMPAR the comparison function. */
|
|
Packit |
6c4009 |
void *
|
|
Packit |
6c4009 |
__tdelete (const void *key, void **vrootp, __compar_fn_t compar)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
node p, q, r, retval;
|
|
Packit |
6c4009 |
int cmp;
|
|
Packit |
6c4009 |
node *rootp = (node *) vrootp;
|
|
Packit |
6c4009 |
node root, unchained;
|
|
Packit |
6c4009 |
/* Stack of nodes so we remember the parents without recursion. It's
|
|
Packit |
6c4009 |
_very_ unlikely that there are paths longer than 40 nodes. The tree
|
|
Packit |
6c4009 |
would need to have around 250.000 nodes. */
|
|
Packit |
6c4009 |
int stacksize = 40;
|
|
Packit |
6c4009 |
int sp = 0;
|
|
Packit |
6c4009 |
node **nodestack = alloca (sizeof (node *) * stacksize);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (rootp == NULL)
|
|
Packit |
6c4009 |
return NULL;
|
|
Packit |
6c4009 |
p = DEREFNODEPTR(rootp);
|
|
Packit |
6c4009 |
if (p == NULL)
|
|
Packit |
6c4009 |
return NULL;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
CHECK_TREE (p);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
root = DEREFNODEPTR(rootp);
|
|
Packit |
6c4009 |
while ((cmp = (*compar) (key, root->key)) != 0)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
if (sp == stacksize)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
node **newstack;
|
|
Packit |
6c4009 |
stacksize += 20;
|
|
Packit |
6c4009 |
newstack = alloca (sizeof (node *) * stacksize);
|
|
Packit |
6c4009 |
nodestack = memcpy (newstack, nodestack, sp * sizeof (node *));
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
nodestack[sp++] = rootp;
|
|
Packit |
6c4009 |
p = DEREFNODEPTR(rootp);
|
|
Packit |
6c4009 |
if (cmp < 0)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
rootp = LEFTPTR(p);
|
|
Packit |
6c4009 |
root = LEFT(p);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
rootp = RIGHTPTR(p);
|
|
Packit |
6c4009 |
root = RIGHT(p);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
if (root == NULL)
|
|
Packit |
6c4009 |
return NULL;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* This is bogus if the node to be deleted is the root... this routine
|
|
Packit |
6c4009 |
really should return an integer with 0 for success, -1 for failure
|
|
Packit |
6c4009 |
and errno = ESRCH or something. */
|
|
Packit |
6c4009 |
retval = p;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* We don't unchain the node we want to delete. Instead, we overwrite
|
|
Packit |
6c4009 |
it with its successor and unchain the successor. If there is no
|
|
Packit |
6c4009 |
successor, we really unchain the node to be deleted. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
root = DEREFNODEPTR(rootp);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
r = RIGHT(root);
|
|
Packit |
6c4009 |
q = LEFT(root);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (q == NULL || r == NULL)
|
|
Packit |
6c4009 |
unchained = root;
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
node *parentp = rootp, *up = RIGHTPTR(root);
|
|
Packit |
6c4009 |
node upn;
|
|
Packit |
6c4009 |
for (;;)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
if (sp == stacksize)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
node **newstack;
|
|
Packit |
6c4009 |
stacksize += 20;
|
|
Packit |
6c4009 |
newstack = alloca (sizeof (node *) * stacksize);
|
|
Packit |
6c4009 |
nodestack = memcpy (newstack, nodestack, sp * sizeof (node *));
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
nodestack[sp++] = parentp;
|
|
Packit |
6c4009 |
parentp = up;
|
|
Packit |
6c4009 |
upn = DEREFNODEPTR(up);
|
|
Packit |
6c4009 |
if (LEFT(upn) == NULL)
|
|
Packit |
6c4009 |
break;
|
|
Packit |
6c4009 |
up = LEFTPTR(upn);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
unchained = DEREFNODEPTR(up);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* We know that either the left or right successor of UNCHAINED is NULL.
|
|
Packit |
6c4009 |
R becomes the other one, it is chained into the parent of UNCHAINED. */
|
|
Packit |
6c4009 |
r = LEFT(unchained);
|
|
Packit |
6c4009 |
if (r == NULL)
|
|
Packit |
6c4009 |
r = RIGHT(unchained);
|
|
Packit |
6c4009 |
if (sp == 0)
|
|
Packit |
6c4009 |
SETNODEPTR(rootp,r);
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
q = DEREFNODEPTR(nodestack[sp-1]);
|
|
Packit |
6c4009 |
if (unchained == RIGHT(q))
|
|
Packit |
6c4009 |
SETRIGHT(q,r);
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
SETLEFT(q,r);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (unchained != root)
|
|
Packit |
6c4009 |
root->key = unchained->key;
|
|
Packit |
6c4009 |
if (!RED(unchained))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Now we lost a black edge, which means that the number of black
|
|
Packit |
6c4009 |
edges on every path is no longer constant. We must balance the
|
|
Packit |
6c4009 |
tree. */
|
|
Packit |
6c4009 |
/* NODESTACK now contains all parents of R. R is likely to be NULL
|
|
Packit |
6c4009 |
in the first iteration. */
|
|
Packit |
6c4009 |
/* NULL nodes are considered black throughout - this is necessary for
|
|
Packit |
6c4009 |
correctness. */
|
|
Packit |
6c4009 |
while (sp > 0 && (r == NULL || !RED(r)))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
node *pp = nodestack[sp - 1];
|
|
Packit |
6c4009 |
p = DEREFNODEPTR(pp);
|
|
Packit |
6c4009 |
/* Two symmetric cases. */
|
|
Packit |
6c4009 |
if (r == LEFT(p))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Q is R's brother, P is R's parent. The subtree with root
|
|
Packit |
6c4009 |
R has one black edge less than the subtree with root Q. */
|
|
Packit |
6c4009 |
q = RIGHT(p);
|
|
Packit |
6c4009 |
if (RED(q))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* If Q is red, we know that P is black. We rotate P left
|
|
Packit |
6c4009 |
so that Q becomes the top node in the tree, with P below
|
|
Packit |
6c4009 |
it. P is colored red, Q is colored black.
|
|
Packit |
6c4009 |
This action does not change the black edge count for any
|
|
Packit |
6c4009 |
leaf in the tree, but we will be able to recognize one
|
|
Packit |
6c4009 |
of the following situations, which all require that Q
|
|
Packit |
6c4009 |
is black. */
|
|
Packit |
6c4009 |
SETBLACK(q);
|
|
Packit |
6c4009 |
SETRED(p);
|
|
Packit |
6c4009 |
/* Left rotate p. */
|
|
Packit |
6c4009 |
SETRIGHT(p,LEFT(q));
|
|
Packit |
6c4009 |
SETLEFT(q,p);
|
|
Packit |
6c4009 |
SETNODEPTR(pp,q);
|
|
Packit |
6c4009 |
/* Make sure pp is right if the case below tries to use
|
|
Packit |
6c4009 |
it. */
|
|
Packit |
6c4009 |
nodestack[sp++] = pp = LEFTPTR(q);
|
|
Packit |
6c4009 |
q = RIGHT(p);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
/* We know that Q can't be NULL here. We also know that Q is
|
|
Packit |
6c4009 |
black. */
|
|
Packit |
6c4009 |
if ((LEFT(q) == NULL || !RED(LEFT(q)))
|
|
Packit |
6c4009 |
&& (RIGHT(q) == NULL || !RED(RIGHT(q))))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Q has two black successors. We can simply color Q red.
|
|
Packit |
6c4009 |
The whole subtree with root P is now missing one black
|
|
Packit |
6c4009 |
edge. Note that this action can temporarily make the
|
|
Packit |
6c4009 |
tree invalid (if P is red). But we will exit the loop
|
|
Packit |
6c4009 |
in that case and set P black, which both makes the tree
|
|
Packit |
6c4009 |
valid and also makes the black edge count come out
|
|
Packit |
6c4009 |
right. If P is black, we are at least one step closer
|
|
Packit |
6c4009 |
to the root and we'll try again the next iteration. */
|
|
Packit |
6c4009 |
SETRED(q);
|
|
Packit |
6c4009 |
r = p;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Q is black, one of Q's successors is red. We can
|
|
Packit |
6c4009 |
repair the tree with one operation and will exit the
|
|
Packit |
6c4009 |
loop afterwards. */
|
|
Packit |
6c4009 |
if (RIGHT(q) == NULL || !RED(RIGHT(q)))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* The left one is red. We perform the same action as
|
|
Packit |
6c4009 |
in maybe_split_for_insert where two red edges are
|
|
Packit |
6c4009 |
adjacent but point in different directions:
|
|
Packit |
6c4009 |
Q's left successor (let's call it Q2) becomes the
|
|
Packit |
6c4009 |
top of the subtree we are looking at, its parent (Q)
|
|
Packit |
6c4009 |
and grandparent (P) become its successors. The former
|
|
Packit |
6c4009 |
successors of Q2 are placed below P and Q.
|
|
Packit |
6c4009 |
P becomes black, and Q2 gets the color that P had.
|
|
Packit |
6c4009 |
This changes the black edge count only for node R and
|
|
Packit |
6c4009 |
its successors. */
|
|
Packit |
6c4009 |
node q2 = LEFT(q);
|
|
Packit |
6c4009 |
if (RED(p))
|
|
Packit |
6c4009 |
SETRED(q2);
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
SETBLACK(q2);
|
|
Packit |
6c4009 |
SETRIGHT(p,LEFT(q2));
|
|
Packit |
6c4009 |
SETLEFT(q,RIGHT(q2));
|
|
Packit |
6c4009 |
SETRIGHT(q2,q);
|
|
Packit |
6c4009 |
SETLEFT(q2,p);
|
|
Packit |
6c4009 |
SETNODEPTR(pp,q2);
|
|
Packit |
6c4009 |
SETBLACK(p);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* It's the right one. Rotate P left. P becomes black,
|
|
Packit |
6c4009 |
and Q gets the color that P had. Q's right successor
|
|
Packit |
6c4009 |
also becomes black. This changes the black edge
|
|
Packit |
6c4009 |
count only for node R and its successors. */
|
|
Packit |
6c4009 |
if (RED(p))
|
|
Packit |
6c4009 |
SETRED(q);
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
SETBLACK(q);
|
|
Packit |
6c4009 |
SETBLACK(p);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
SETBLACK(RIGHT(q));
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* left rotate p */
|
|
Packit |
6c4009 |
SETRIGHT(p,LEFT(q));
|
|
Packit |
6c4009 |
SETLEFT(q,p);
|
|
Packit |
6c4009 |
SETNODEPTR(pp,q);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* We're done. */
|
|
Packit |
6c4009 |
sp = 1;
|
|
Packit |
6c4009 |
r = NULL;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Comments: see above. */
|
|
Packit |
6c4009 |
q = LEFT(p);
|
|
Packit |
6c4009 |
if (RED(q))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
SETBLACK(q);
|
|
Packit |
6c4009 |
SETRED(p);
|
|
Packit |
6c4009 |
SETLEFT(p,RIGHT(q));
|
|
Packit |
6c4009 |
SETRIGHT(q,p);
|
|
Packit |
6c4009 |
SETNODEPTR(pp,q);
|
|
Packit |
6c4009 |
nodestack[sp++] = pp = RIGHTPTR(q);
|
|
Packit |
6c4009 |
q = LEFT(p);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
if ((RIGHT(q) == NULL || !RED(RIGHT(q)))
|
|
Packit |
6c4009 |
&& (LEFT(q) == NULL || !RED(LEFT(q))))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
SETRED(q);
|
|
Packit |
6c4009 |
r = p;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
if (LEFT(q) == NULL || !RED(LEFT(q)))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
node q2 = RIGHT(q);
|
|
Packit |
6c4009 |
if (RED(p))
|
|
Packit |
6c4009 |
SETRED(q2);
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
SETBLACK(q2);
|
|
Packit |
6c4009 |
SETLEFT(p,RIGHT(q2));
|
|
Packit |
6c4009 |
SETRIGHT(q,LEFT(q2));
|
|
Packit |
6c4009 |
SETLEFT(q2,q);
|
|
Packit |
6c4009 |
SETRIGHT(q2,p);
|
|
Packit |
6c4009 |
SETNODEPTR(pp,q2);
|
|
Packit |
6c4009 |
SETBLACK(p);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
if (RED(p))
|
|
Packit |
6c4009 |
SETRED(q);
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
SETBLACK(q);
|
|
Packit |
6c4009 |
SETBLACK(p);
|
|
Packit |
6c4009 |
SETBLACK(LEFT(q));
|
|
Packit |
6c4009 |
SETLEFT(p,RIGHT(q));
|
|
Packit |
6c4009 |
SETRIGHT(q,p);
|
|
Packit |
6c4009 |
SETNODEPTR(pp,q);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
sp = 1;
|
|
Packit |
6c4009 |
r = NULL;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
--sp;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
if (r != NULL)
|
|
Packit |
6c4009 |
SETBLACK(r);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
free (unchained);
|
|
Packit |
6c4009 |
return retval;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
libc_hidden_def (__tdelete)
|
|
Packit |
6c4009 |
weak_alias (__tdelete, tdelete)
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Walk the nodes of a tree.
|
|
Packit |
6c4009 |
ROOT is the root of the tree to be walked, ACTION the function to be
|
|
Packit |
6c4009 |
called at each node. LEVEL is the level of ROOT in the whole tree. */
|
|
Packit |
6c4009 |
static void
|
|
Packit |
6c4009 |
trecurse (const void *vroot, __action_fn_t action, int level)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
const_node root = (const_node) vroot;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (LEFT(root) == NULL && RIGHT(root) == NULL)
|
|
Packit |
6c4009 |
(*action) (root, leaf, level);
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
(*action) (root, preorder, level);
|
|
Packit |
6c4009 |
if (LEFT(root) != NULL)
|
|
Packit |
6c4009 |
trecurse (LEFT(root), action, level + 1);
|
|
Packit |
6c4009 |
(*action) (root, postorder, level);
|
|
Packit |
6c4009 |
if (RIGHT(root) != NULL)
|
|
Packit |
6c4009 |
trecurse (RIGHT(root), action, level + 1);
|
|
Packit |
6c4009 |
(*action) (root, endorder, level);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Walk the nodes of a tree.
|
|
Packit |
6c4009 |
ROOT is the root of the tree to be walked, ACTION the function to be
|
|
Packit |
6c4009 |
called at each node. */
|
|
Packit |
6c4009 |
void
|
|
Packit |
6c4009 |
__twalk (const void *vroot, __action_fn_t action)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
const_node root = (const_node) vroot;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
CHECK_TREE ((node) root);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (root != NULL && action != NULL)
|
|
Packit |
6c4009 |
trecurse (root, action, 0);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
libc_hidden_def (__twalk)
|
|
Packit |
6c4009 |
weak_alias (__twalk, twalk)
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* The standardized functions miss an important functionality: the
|
|
Packit |
6c4009 |
tree cannot be removed easily. We provide a function to do this. */
|
|
Packit |
6c4009 |
static void
|
|
Packit |
6c4009 |
tdestroy_recurse (node root, __free_fn_t freefct)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
if (LEFT(root) != NULL)
|
|
Packit |
6c4009 |
tdestroy_recurse (LEFT(root), freefct);
|
|
Packit |
6c4009 |
if (RIGHT(root) != NULL)
|
|
Packit |
6c4009 |
tdestroy_recurse (RIGHT(root), freefct);
|
|
Packit |
6c4009 |
(*freefct) ((void *) root->key);
|
|
Packit |
6c4009 |
/* Free the node itself. */
|
|
Packit |
6c4009 |
free (root);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
void
|
|
Packit |
6c4009 |
__tdestroy (void *vroot, __free_fn_t freefct)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
node root = (node) vroot;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
CHECK_TREE (root);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
if (root != NULL)
|
|
Packit |
6c4009 |
tdestroy_recurse (root, freefct);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
libc_hidden_def (__tdestroy)
|
|
Packit |
6c4009 |
weak_alias (__tdestroy, tdestroy)
|