#include <stdlib.h>
#include <string.h>
#include <search.h>
Go to the source code of this file.
Classes 
struct  node_t 
Defines 
#define  CHECK_TREE(a) 
Typedefs 
typedef struct node_t *  node 
typedef struct node_t *  const_node 
Functions 
static void  maybe_split_for_insert (node *rootp, node *parentp, node *gparentp, int p_r, int gp_r, int mode) 
void *  __tsearch (const void *key, void **vrootp, __compar_fn_t compar) 
 weak_alias (__tsearch, tsearch) 
 weak_alias (__tfind, tfind) 
 weak_alias (__tdelete, tdelete) 
void  __twalk (const void *vroot, __action_fn_t action) 
 weak_alias (__twalk, twalk) 
void  __tdestroy (void *vroot, __free_fn_t freefct) 
Class Documentation
Define Documentation
Typedef Documentation
Function Documentation
void __tdestroy 
( 
void * 
vroot, 


__free_fn_t 
freefct 

) 
 
Definition at line 239 of file tsearch.c.
{
node q;
node *parentp = NULL, *gparentp = NULL;
node *rootp = (node *) vrootp;
node *nextp;
int r = 0, p_r = 0, gp_r = 0;
if (rootp == NULL)
return NULL;
if (*rootp != NULL)
(*rootp)>red = 0;
CHECK_TREE (*rootp);
nextp = rootp;
while (*nextp != NULL)
{
node root = *rootp;
r = (*compar) (key, root>key);
if (r == 0)
return root;
maybe_split_for_insert (rootp, parentp, gparentp, p_r, gp_r, 0);
nextp = r < 0 ? &root>left : &root>right;
if (*nextp == NULL)
break;
gparentp = parentp;
parentp = rootp;
rootp = nextp;
gp_r = p_r;
p_r = r;
}
q = (struct node_t *) malloc (sizeof (struct node_t));
if (q != NULL)
{
*nextp = q;
q>key = key;
q>red = 1;
q>left = q>right = NULL;
if (nextp != rootp)
maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1);
}
return q;
}
Definition at line 156 of file tsearch.c.
{
node root = *rootp;
node *rp, *lp;
rp = &(*rootp)>right;
lp = &(*rootp)>left;
if (mode == 1
 ((*rp) != NULL && (*lp) != NULL && (*rp)>red && (*lp)>red))
{
root>red = 1;
if (*rp)
(*rp)>red = 0;
if (*lp)
(*lp)>red = 0;
if (parentp != NULL && (*parentp)>red)
{
node gp = *gparentp;
node p = *parentp;
if ((p_r > 0) != (gp_r > 0))
{
p>red = 1;
gp>red = 1;
root>red = 0;
if (p_r < 0)
{
p>left = *rp;
*rp = p;
gp>right = *lp;
*lp = gp;
}
else
{
p>right = *lp;
*lp = p;
gp>left = *rp;
*rp = gp;
}
*gparentp = root;
}
else
{
*gparentp = *parentp;
p>red = 0;
gp>red = 1;
if (p_r < 0)
{
gp>left = p>right;
p>right = gp;
}
else
{
gp>right = p>left;
p>left = gp;
}
}
}
}
}
Definition at line 329 of file tsearch.c.
{
node p, q, r, retval;
int cmp;
node *rootp = (node *) vrootp;
node root, unchained;
int stacksize = 40;
int sp = 0;
node **nodestack = alloca (sizeof (node *) * stacksize);
if (rootp == NULL)
return NULL;
p = *rootp;
if (p == NULL)
return NULL;
CHECK_TREE (p);
while ((cmp = (*compar) (key, (*rootp)>key)) != 0)
{
if (sp == stacksize)
{
node **newstack;
stacksize += 20;
newstack = alloca (sizeof (node *) * stacksize);
nodestack = memcpy (newstack, nodestack, sp * sizeof (node *));
}
nodestack[sp++] = rootp;
p = *rootp;
rootp = ((cmp < 0)
? &(*rootp)>left
: &(*rootp)>right);
if (*rootp == NULL)
return NULL;
}
retval = p;
root = *rootp;
r = root>right;
q = root>left;
if (q == NULL  r == NULL)
unchained = root;
else
{
node *parent = rootp, *up = &root>right;
for (;;)
{
if (sp == stacksize)
{
node **newstack;
stacksize += 20;
newstack = alloca (sizeof (node *) * stacksize);
nodestack = memcpy (newstack, nodestack, sp * sizeof (node *));
}
nodestack[sp++] = parent;
parent = up;
if ((*up)>left == NULL)
break;
up = &(*up)>left;
}
unchained = *up;
}
r = unchained>left;
if (r == NULL)
r = unchained>right;
if (sp == 0)
*rootp = r;
else
{
q = *nodestack[sp1];
if (unchained == q>right)
q>right = r;
else
q>left = r;
}
if (unchained != root)
root>key = unchained>key;
if (!unchained>red)
{
while (sp > 0 && (r == NULL  !r>red))
{
node *pp = nodestack[sp  1];
p = *pp;
if (r == p>left)
{
q = p>right;
if (q>red)
{
q>red = 0;
p>red = 1;
p>right = q>left;
q>left = p;
*pp = q;
nodestack[sp++] = pp = &q>left;
q = p>right;
}
if ((q>left == NULL  !q>left>red)
&& (q>right == NULL  !q>right>red))
{
q>red = 1;
r = p;
}
else
{
if (q>right == NULL  !q>right>red)
{
node q2 = q>left;
q2>red = p>red;
p>right = q2>left;
q>left = q2>right;
q2>right = q;
q2>left = p;
*pp = q2;
p>red = 0;
}
else
{
q>red = p>red;
p>red = 0;
q>right>red = 0;
p>right = q>left;
q>left = p;
*pp = q;
}
sp = 1;
r = NULL;
}
}
else
{
q = p>left;
if (q>red)
{
q>red = 0;
p>red = 1;
p>left = q>right;
q>right = p;
*pp = q;
nodestack[sp++] = pp = &q>right;
q = p>left;
}
if ((q>right == NULL  !q>right>red)
&& (q>left == NULL  !q>left>red))
{
q>red = 1;
r = p;
}
else
{
if (q>left == NULL  !q>left>red)
{
node q2 = q>right;
q2>red = p>red;
p>left = q2>right;
q>right = q2>left;
q2>left = q;
q2>right = p;
*pp = q2;
p>red = 0;
}
else
{
q>red = p>red;
p>red = 0;
q>left>red = 0;
p>left = q>right;
q>right = p;
*pp = q;
}
sp = 1;
r = NULL;
}
}
sp;
}
if (r != NULL)
r>red = 0;
}
free (unchained);
return retval;
}
Definition at line 589 of file tsearch.c.
{
const_node root = (const_node) vroot;
if (root>left == NULL && root>right == NULL)
(*action) (root, leaf, level);
else
{
(*action) (root, preorder, level);
if (root>left != NULL)
trecurse (root>left, action, level + 1);
(*action) (root, postorder, level);
if (root>right != NULL)
trecurse (root>right, action, level + 1);
(*action) (root, endorder, level);
}
}