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