/*

 * CDDL HEADER START

 *

 * The contents of this file are subject to the terms of the

 *

 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE

 * or http://www.opensolaris.org/os/licensing.

 * See the License for the specific language governing permissions

 * and limitations under the License.

 *

 * When distributing Covered Code, include this CDDL HEADER in each

 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.

 * If applicable, add the following below this CDDL HEADER, with the

 * fields enclosed by brackets "[]" replaced with your own identifying

 * information: Portions Copyright [yyyy] [name of copyright owner]

 *

 * CDDL HEADER END

 */

/*

 * Use is subject to license terms.

 */

/*	Copyright (c) 1988 AT&T	*/

/*	  All Rights Reserved  	*/

/*

 * Tree search algorithm, generalized from Knuth (6.2.2) Algorithm T.

 *

 *

 * The NODE * arguments are declared in the lint files as char *,

 * because the definition of NODE isn't available to the user.

 */

#include "mtlib.h"

#include "libc.h"

#include <sys/types.h>

#include <search.h>

#include <stdlib.h>

#include <thread.h>

#include <synch.h>

typedef struct node { char *key; struct node *llink, *rlink; } NODE;

static void __twalk(NODE *, void (*)(const void *, VISIT, int), int);

/* Find or insert key into search tree */

void *

tsearch(const void *ky, void **rtp, int (*compar)())

{

	char *key = (char *)ky;

	NODE **rootp = (NODE **)rtp;

	NODE *q;	/* New node if key not found */

	if (rootp == NULL)

		return (NULL);

	while (*rootp != NULL) {			/* T1: */

		int r = (*compar)(key, (*rootp)->key);	/* T2: */

		if (r == 0)

			return ((void *)*rootp);	/* Key found */

		rootp = (r < 0) ?

		    &(*rootp)->llink :		/* T3: Take left branch */

		    &(*rootp)->rlink;		/* T4: Take right branch */

	}

	q = lmalloc(sizeof (NODE));		/* T5: Not found */

	if (q != NULL) {			/* Allocate new node */

		*rootp = q;			/* Link new node to old */

		q->key = key;			/* Initialize new node */

		q->llink = q->rlink = NULL;

	}

	return ((void *)q);

}

/* Delete node with key key */

void *

tdelete(const void *ky, void **rtp, int (*compar)())

{

	char *key = (char *)ky;

	NODE **rootp = (NODE **)rtp;

	NODE *p;		/* Parent of node to be deleted */

	NODE *q;	/* Successor node */

	NODE *r;	/* Right son node */

	int ans;		/* Result of comparison */

	if (rootp == NULL || (p = *rootp) == NULL)

		return (NULL);

	while ((ans = (*compar)(key, (*rootp)->key)) != 0) {

		p = *rootp;

		rootp = (ans < 0) ?

		    &(*rootp)->llink :		/* Take left branch */

		    &(*rootp)->rlink;		/* Take right branch */

		if (*rootp == NULL)

			return (NULL);		/* Key not found */

	}

	r = (*rootp)->rlink;			/* D1: */

	if ((q = (*rootp)->llink) == NULL)	/* Llink NULL? */

		q = r;

	else if (r != NULL) {			/* Rlink NULL? */

		if (r->llink == NULL) {		/* D2: Find successor */

			r->llink = q;

			q = r;

		} else {			/* D3: Find NULL link */

			for (q = r->llink; q->llink != NULL; q = r->llink)

				r = q;

			r->llink = q->rlink;

			q->llink = (*rootp)->llink;

			q->rlink = (*rootp)->rlink;

		}

	}

	lfree(*rootp, sizeof (NODE));		/* D4: Free node */

	*rootp = q;			/* Link parent to replacement */

	return ((void *)p);

}

/* Walk the nodes of a tree */

void

twalk(const void *rt,		/* Root of the tree to be walked */

	void (*action)(const void *, VISIT, int))

{

	NODE *root = (NODE *)rt;

	if (root != NULL && action != NULL)

		__twalk(root, action, 0);

}

/* Walk the nodes of a tree */

static void

__twalk(NODE *root,		/* Root of the tree to be walked */

	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)

			__twalk(root->llink, action, level + 1);

		(*action)(root, postorder, level);

		if (root->rlink != NULL)

			__twalk(root->rlink, action, level + 1);

		(*action)(root, endorder, level);

	}

}