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 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 */ 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 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