#include <config.h>
#include "roken.h"
#include "search.h"
#include <stdlib.h>
typedef struct node {
char *key;
struct node *llink, *rlink;
} node_t;
#ifndef __DECONST
#define __DECONST(type, var) ((type)(uintptr_t)(const void *)(var))
#endif
ROKEN_LIB_FUNCTION void *
rk_tsearch(const void *vkey, void **vrootp,
int (*compar)(const void *, const void *))
{
node_t *q;
node_t **rootp = (node_t **)vrootp;
if (rootp == NULL)
return NULL;
while (*rootp != NULL) {
int r;
if ((r = (*compar)(vkey, (*rootp)->key)) == 0)
return *rootp;
rootp = (r < 0) ?
&(*rootp)->llink :
&(*rootp)->rlink;
}
q = malloc(sizeof(node_t));
if (q != 0) {
*rootp = q;
q->key = __DECONST(void *, vkey);
q->llink = q->rlink = NULL;
}
return q;
}
static void
trecurse(const node_t *root, void (*action)(const void *, VISIT, int),
int level)
{
if (root->llink == NULL && root->rlink == NULL)
(*action)(root, leaf, level);
else {
(*action)(root, preorder, level);
if (root->llink != NULL)
trecurse(root->llink, action, level + 1);
(*action)(root, postorder, level);
if (root->rlink != NULL)
trecurse(root->rlink, action, level + 1);
(*action)(root, endorder, level);
}
}
ROKEN_LIB_FUNCTION void
rk_twalk(const void *vroot,
void (*action)(const void *, VISIT, int))
{
if (vroot != NULL && action != NULL)
trecurse(vroot, action, 0);
}
ROKEN_LIB_FUNCTION void *
rk_tdelete(const void * vkey, void ** vrootp,
int (*compar)(const void *, const void *))
{
node_t **rootp = (node_t **)vrootp;
node_t *p, *q, *r;
int cmp;
if (rootp == NULL || (p = *rootp) == NULL)
return NULL;
while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) {
p = *rootp;
rootp = (cmp < 0) ?
&(*rootp)->llink :
&(*rootp)->rlink;
if (*rootp == NULL)
return NULL;
}
r = (*rootp)->rlink;
if ((q = (*rootp)->llink) == NULL)
q = r;
else if (r != NULL) {
if (r->llink == NULL) {
r->llink = q;
q = r;
} else {
for (q = r->llink; q->llink != NULL; q = r->llink)
r = q;
r->llink = q->rlink;
q->llink = (*rootp)->llink;
q->rlink = (*rootp)->rlink;
}
}
free(*rootp);
*rootp = q;
return p;
}
ROKEN_LIB_FUNCTION void *
rk_tfind(const void *vkey, void * const *vrootp,
int (*compar)(const void *, const void *))
{
node_t **rootp = (node_t **)vrootp;
if (rootp == NULL)
return NULL;
while (*rootp != NULL) {
int r;
if ((r = (*compar)(vkey, (*rootp)->key)) == 0)
return *rootp;
rootp = (r < 0) ?
&(*rootp)->llink :
&(*rootp)->rlink;
}
return NULL;
}