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