1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License, Version 1.0 only
6  * (the "License").  You may not use this file except in compliance
7  * with the License.
8  *
9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10  * or http://www.opensolaris.org/os/licensing.
11  * See the License for the specific language governing permissions
12  * and limitations under the License.
13  *
14  * When distributing Covered Code, include this CDDL HEADER in each
15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16  * If applicable, add the following below this CDDL HEADER, with the
17  * fields enclosed by brackets "[]" replaced with your own identifying
18  * information: Portions Copyright [yyyy] [name of copyright owner]
19  *
20  * CDDL HEADER END
21  */
22 /*
23  * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  */
26 
27 /*
28  * Binary tree access. The routines contained in this file are:
29  *  slp_tsearch
30  *  slp_tfind
31  *  slp_twalk
32  *
33  * These have the same interfaces as tsearch(3C), tfind(3C), and
34  * twalk(3C), with two important distinctions:
35  * - libc twalk is inadequate, since it doesn't allow the caller to pass
36  *   cookies into the action function (prohibiting thread-safe usage).
37  *   slp_twalk allows cookies.
38  * - libc tsearch and tfind *always* lock access to the tree. This can
39  *   be inefficient when it isn't necessary to lock the tree in order
40  *   to ensure thread-safety. It is the responsibility of the caller to
41  *   ensure that slp_tsearch and slp_tfind are safe for concurrent access.
42  *
43  * It is possible for this implementation to degenerate into a
44  * linked-list algorithm with certain inputs. If this proves to be
45  * a problem in practice, these routines can be optimized by balancing
46  * the trees.
47  */
48 
49 #include <stdio.h>
50 #include <stdlib.h>
51 #include <slp-internal.h>
52 
53 struct node { char *key; struct node *llink, *rlink; };
54 typedef struct node NODE;
55 
slp_twalk(void * r,void (* action)(void *,VISIT,int,void *),int level,void * cookie)56 void slp_twalk(void *r,
57 		void (*action)(void *, VISIT, int, void *),
58 		int level, void *cookie) {
59 	NODE *root = (NODE *) r;
60 	if (root->llink == NULL && root->rlink == NULL)
61 		(*action)(root, leaf, level, cookie);
62 	else {
63 		(*action)(root, preorder, level, cookie);
64 		if (root->llink != NULL)
65 			slp_twalk(root->llink, action, level + 1, cookie);
66 		(*action)(root, postorder, level, cookie);
67 		if (root->rlink != NULL)
68 			slp_twalk(root->rlink, action, level + 1, cookie);
69 		(*action)(root, endorder, level, cookie);
70 	}
71 }
72 
73 /* Find or insert key into search tree */
slp_tsearch(const void * ky,void ** rtp,int (* compar)())74 void *slp_tsearch(const void *ky, void **rtp, int (* compar)()) {
75 	char *key = (char *)ky;
76 	NODE **rootp = (NODE **)rtp;
77 	NODE *q;	/* New node if key not found */
78 
79 	if (rootp == NULL)
80 		return (NULL);
81 	while (*rootp != NULL) {			/* T1: */
82 		int r = (*compar)(key, (*rootp)->key);	/* T2: */
83 		if (r == 0)
84 			return ((void *)*rootp);	/* Key found */
85 		rootp = (r < 0) ?
86 		    &(*rootp)->llink :		/* T3: Take left branch */
87 		    &(*rootp)->rlink;		/* T4: Take right branch */
88 	}
89 	q = (NODE *) malloc(sizeof (NODE));	/* T5: Not found */
90 	if (q != NULL) {			/* Allocate new node */
91 		*rootp = q;			/* Link new node to old */
92 		q->key = key;			/* Initialize new node */
93 		q->llink = q->rlink = NULL;
94 	}
95 	return ((void *)q);
96 }
97 
slp_tfind(const void * ky,void * const * rtp,int (* compar)(const void *,const void *))98 void *slp_tfind(const void *ky, void *const *rtp,
99 		int (*compar)(const void *, const void *)) {
100 	void *key = (char *)ky;
101 	NODE **rootp = (NODE **)rtp;
102 	if (rootp == NULL)
103 		return (NULL);
104 	while (*rootp != NULL) {			/* T1: */
105 		int r = (*compar)(key, (*rootp)->key);	/* T2: */
106 		if (r == 0)
107 			return ((void *)*rootp);	/* Key found */
108 		rootp = (r < 0) ?
109 		    &(*rootp)->llink :		/* T3: Take left branch */
110 		    &(*rootp)->rlink;		/* T4: Take right branch */
111 	}
112 	return (NULL);
113 }
114