|
Packit |
875988 |
/*
|
|
Packit |
875988 |
* Tree search generalized from Knuth (6.2.2) Algorithm T just like
|
|
Packit |
875988 |
* the AT&T man page says.
|
|
Packit |
875988 |
*
|
|
Packit |
875988 |
* The node_t structure is for internal use only, lint doesn't grok it.
|
|
Packit |
875988 |
*
|
|
Packit |
875988 |
* Written by reading the System V Interface Definition, not the code.
|
|
Packit |
875988 |
*
|
|
Packit |
875988 |
* Totally public domain.
|
|
Packit |
875988 |
*/
|
|
Packit |
875988 |
|
|
Packit |
875988 |
#include "tsearch.h"
|
|
Packit |
875988 |
#include <stdlib.h>
|
|
Packit |
875988 |
|
|
Packit |
875988 |
|
|
Packit |
875988 |
typedef struct node
|
|
Packit |
875988 |
{
|
|
Packit |
875988 |
const void *key;
|
|
Packit |
875988 |
struct node *llink;
|
|
Packit |
875988 |
struct node *rlink;
|
|
Packit |
875988 |
} node_t;
|
|
Packit |
875988 |
|
|
Packit |
875988 |
|
|
Packit |
875988 |
/* $NetBSD: tsearch.c,v 1.5 2005/11/29 03:12:00 christos Exp $ */
|
|
Packit |
875988 |
/* find or insert datum into search tree */
|
|
Packit |
875988 |
void *
|
|
Packit |
875988 |
tsearch (const void *vkey, /* key to be located */
|
|
Packit |
875988 |
void **vrootp, /* address of tree root */
|
|
Packit |
875988 |
int (*compar)(const void *, const void *))
|
|
Packit |
875988 |
{
|
|
Packit |
875988 |
node_t *q;
|
|
Packit |
875988 |
node_t **rootp = (node_t **)vrootp;
|
|
Packit |
875988 |
|
|
Packit |
875988 |
if (NULL == rootp)
|
|
Packit |
875988 |
return NULL;
|
|
Packit |
875988 |
|
|
Packit |
875988 |
while (*rootp != NULL)
|
|
Packit |
875988 |
{ /* Knuth's T1: */
|
|
Packit |
875988 |
int r;
|
|
Packit |
875988 |
|
|
Packit |
875988 |
if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
|
|
Packit |
875988 |
return *rootp; /* we found it! */
|
|
Packit |
875988 |
|
|
Packit |
875988 |
rootp = (r < 0) ?
|
|
Packit |
875988 |
&(*rootp)->llink : /* T3: follow left branch */
|
|
Packit |
875988 |
&(*rootp)->rlink; /* T4: follow right branch */
|
|
Packit |
875988 |
}
|
|
Packit |
875988 |
|
|
Packit |
875988 |
q = malloc (sizeof(node_t)); /* T5: key not found */
|
|
Packit |
875988 |
if (q)
|
|
Packit |
875988 |
{ /* make new node */
|
|
Packit |
875988 |
*rootp = q; /* link new node to old */
|
|
Packit |
875988 |
q->key = vkey; /* initialize new node */
|
|
Packit |
875988 |
q->llink = q->rlink = NULL;
|
|
Packit |
875988 |
}
|
|
Packit |
875988 |
return q;
|
|
Packit |
875988 |
}
|
|
Packit |
875988 |
|
|
Packit |
875988 |
|
|
Packit |
875988 |
/* $NetBSD: tfind.c,v 1.5 2005/03/23 08:16:53 kleink Exp $ */
|
|
Packit |
875988 |
/* find a node, or return NULL */
|
|
Packit |
875988 |
void *
|
|
Packit |
875988 |
tfind (const void *vkey, /* key to be found */
|
|
Packit |
875988 |
void * const *vrootp, /* address of the tree root */
|
|
Packit |
875988 |
int (*compar)(const void *, const void *))
|
|
Packit |
875988 |
{
|
|
Packit |
875988 |
node_t * const *rootp = (node_t * const*)vrootp;
|
|
Packit |
875988 |
|
|
Packit |
875988 |
if (NULL == rootp)
|
|
Packit |
875988 |
return NULL;
|
|
Packit |
875988 |
|
|
Packit |
875988 |
while (*rootp != NULL)
|
|
Packit |
875988 |
{ /* T1: */
|
|
Packit |
875988 |
int r;
|
|
Packit |
875988 |
|
|
Packit |
875988 |
if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
|
|
Packit |
875988 |
return *rootp; /* key found */
|
|
Packit |
875988 |
rootp = (r < 0) ?
|
|
Packit |
875988 |
&(*rootp)->llink : /* T3: follow left branch */
|
|
Packit |
875988 |
&(*rootp)->rlink; /* T4: follow right branch */
|
|
Packit |
875988 |
}
|
|
Packit |
875988 |
return NULL;
|
|
Packit |
875988 |
}
|
|
Packit |
875988 |
|
|
Packit |
875988 |
|
|
Packit |
875988 |
/* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */
|
|
Packit |
875988 |
/*
|
|
Packit |
875988 |
* delete node with given key
|
|
Packit |
875988 |
*
|
|
Packit |
875988 |
* vkey: key to be deleted
|
|
Packit |
875988 |
* vrootp: address of the root of the tree
|
|
Packit |
875988 |
* compar: function to carry out node comparisons
|
|
Packit |
875988 |
*/
|
|
Packit |
875988 |
void *
|
|
Packit |
875988 |
tdelete (const void * __restrict vkey,
|
|
Packit |
875988 |
void ** __restrict vrootp,
|
|
Packit |
875988 |
int (*compar)(const void *, const void *))
|
|
Packit |
875988 |
{
|
|
Packit |
875988 |
node_t **rootp = (node_t **)vrootp;
|
|
Packit |
875988 |
node_t *p;
|
|
Packit |
875988 |
node_t *q;
|
|
Packit |
875988 |
node_t *r;
|
|
Packit |
875988 |
int cmp;
|
|
Packit |
875988 |
|
|
Packit |
875988 |
if (rootp == NULL || (p = *rootp) == NULL)
|
|
Packit |
875988 |
return NULL;
|
|
Packit |
875988 |
|
|
Packit |
875988 |
while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0)
|
|
Packit |
875988 |
{
|
|
Packit |
875988 |
p = *rootp;
|
|
Packit |
875988 |
rootp = (cmp < 0) ?
|
|
Packit |
875988 |
&(*rootp)->llink : /* follow llink branch */
|
|
Packit |
875988 |
&(*rootp)->rlink; /* follow rlink branch */
|
|
Packit |
875988 |
if (*rootp == NULL)
|
|
Packit |
875988 |
return NULL; /* key not found */
|
|
Packit |
875988 |
}
|
|
Packit |
875988 |
r = (*rootp)->rlink; /* D1: */
|
|
Packit |
875988 |
if ((q = (*rootp)->llink) == NULL) /* Left NULL? */
|
|
Packit |
875988 |
{
|
|
Packit |
875988 |
q = r;
|
|
Packit |
875988 |
}
|
|
Packit |
875988 |
else if (r != NULL)
|
|
Packit |
875988 |
{ /* Right link is NULL? */
|
|
Packit |
875988 |
if (r->llink == NULL)
|
|
Packit |
875988 |
{ /* D2: Find successor */
|
|
Packit |
875988 |
r->llink = q;
|
|
Packit |
875988 |
q = r;
|
|
Packit |
875988 |
}
|
|
Packit |
875988 |
else
|
|
Packit |
875988 |
{ /* D3: Find NULL link */
|
|
Packit |
875988 |
for (q = r->llink; q->llink != NULL; q = r->llink)
|
|
Packit |
875988 |
r = q;
|
|
Packit |
875988 |
r->llink = q->rlink;
|
|
Packit |
875988 |
q->llink = (*rootp)->llink;
|
|
Packit |
875988 |
q->rlink = (*rootp)->rlink;
|
|
Packit |
875988 |
}
|
|
Packit |
875988 |
}
|
|
Packit |
875988 |
free(*rootp); /* D4: Free node */
|
|
Packit |
875988 |
*rootp = q; /* link parent to new node */
|
|
Packit |
875988 |
return p;
|
|
Packit |
875988 |
}
|
|
Packit |
875988 |
|
|
Packit |
875988 |
/* end of tsearch.c */
|