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 #pragma ident	"%Z%%M%	%I%	%E% SMI"
28 
29 /*
30  * Binary tree access. The routines contained in this file are:
31  *  slp_tsearch
32  *  slp_tfind
33  *  slp_twalk
34  *
35  * These have the same interfaces as tsearch(3C), tfind(3C), and
36  * twalk(3C), with two important distinctions:
37  * - libc twalk is inadequate, since it doesn't allow the caller to pass
38  *   cookies into the action function (prohibiting thread-safe usage).
39  *   slp_twalk allows cookies.
40  * - libc tsearch and tfind *always* lock access to the tree. This can
41  *   be inefficient when it isn't necessary to lock the tree in order
42  *   to ensure thread-safety. It is the responsibility of the caller to
43  *   ensure that slp_tsearch and slp_tfind are safe for concurrent access.
44  *
45  * It is possible for this implementation to degenerate into a
46  * linked-list algorithm with certain inputs. If this proves to be
47  * a problem in practice, these routines can be optimized by balancing
48  * the trees.
49  */
50 
51 #include <stdio.h>
52 #include <stdlib.h>
53 #include <slp-internal.h>
54 
55 struct node { char *key; struct node *llink, *rlink; };
56 typedef struct node NODE;
57 
slp_twalk(void * r,void (* action)(void *,VISIT,int,void *),int level,void * cookie)58 void slp_twalk(void *r,
59 		void (*action)(void *, VISIT, int, void *),
60 		int level, void *cookie) {
61 	NODE *root = (NODE *) r;
62 	if (root->llink == NULL && root->rlink == NULL)
63 		(*action)(root, leaf, level, cookie);
64 	else {
65 		(*action)(root, preorder, level, cookie);
66 		if (root->llink != NULL)
67 			slp_twalk(root->llink, action, level + 1, cookie);
68 		(*action)(root, postorder, level, cookie);
69 		if (root->rlink != NULL)
70 			slp_twalk(root->rlink, action, level + 1, cookie);
71 		(*action)(root, endorder, level, cookie);
72 	}
73 }
74 
75 /* Find or insert key into search tree */
slp_tsearch(const void * ky,void ** rtp,int (* compar)())76 void *slp_tsearch(const void *ky, void **rtp, int (* compar)()) {
77 	char *key = (char *)ky;
78 	NODE **rootp = (NODE **)rtp;
79 	NODE *q;	/* New node if key not found */
80 
81 	if (rootp == NULL)
82 		return (NULL);
83 	while (*rootp != NULL) {			/* T1: */
84 		int r = (*compar)(key, (*rootp)->key);	/* T2: */
85 		if (r == 0)
86 			return ((void *)*rootp);	/* Key found */
87 		rootp = (r < 0) ?
88 		    &(*rootp)->llink :		/* T3: Take left branch */
89 		    &(*rootp)->rlink;		/* T4: Take right branch */
90 	}
91 	q = (NODE *) malloc(sizeof (NODE));	/* T5: Not found */
92 	if (q != NULL) {			/* Allocate new node */
93 		*rootp = q;			/* Link new node to old */
94 		q->key = key;			/* Initialize new node */
95 		q->llink = q->rlink = NULL;
96 	}
97 	return ((void *)q);
98 }
99 
slp_tfind(const void * ky,void * const * rtp,int (* compar)(const void *,const void *))100 void *slp_tfind(const void *ky, void *const *rtp,
101 		int (*compar)(const void *, const void *)) {
102 	void *key = (char *)ky;
103 	NODE **rootp = (NODE **)rtp;
104 	if (rootp == NULL)
105 		return (NULL);
106 	while (*rootp != NULL) {			/* T1: */
107 		int r = (*compar)(key, (*rootp)->key);	/* T2: */
108 		if (r == 0)
109 			return ((void *)*rootp);	/* Key found */
110 		rootp = (r < 0) ?
111 		    &(*rootp)->llink :		/* T3: Take left branch */
112 		    &(*rootp)->rlink;		/* T4: Take right branch */
113 	}
114 	return (NULL);
115 }
116