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