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