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