1 /*- 2 * Copyright (c) 2015 Nuxi, https://nuxi.nl/ 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 14 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 16 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 17 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 18 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 19 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 20 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 21 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 22 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 23 * SUCH DAMAGE. 24 */ 25 26 #include <sys/cdefs.h> 27 __FBSDID("$FreeBSD$"); 28 29 #define _SEARCH_PRIVATE 30 #include <search.h> 31 #include <stdlib.h> 32 33 #include "tsearch_path.h" 34 35 void * 36 tsearch(const void *key, void **rootp, 37 int (*compar)(const void *, const void *)) 38 { 39 struct path path; 40 node_t *root, **base, **leaf, *result, *n, *x, *y, *z; 41 int cmp; 42 43 /* POSIX requires that tsearch() returns NULL if rootp is NULL. */ 44 if (rootp == NULL) 45 return (NULL); 46 root = *rootp; 47 48 /* 49 * Find the leaf where the new key needs to be inserted. Return 50 * if we've found an existing entry. Keep track of the path that 51 * is taken to get to the node, as we will need it to adjust the 52 * balances. 53 */ 54 path_init(&path); 55 base = &root; 56 leaf = &root; 57 while (*leaf != NULL) { 58 if ((*leaf)->balance != 0) { 59 /* 60 * If we reach a node that has a non-zero 61 * balance on the way, we know that we won't 62 * need to perform any rotations above this 63 * point. In this case rotations are always 64 * capable of keeping the subtree in balance. 65 * Make this the base node and reset the path. 66 */ 67 base = leaf; 68 path_init(&path); 69 } 70 cmp = compar(key, (*leaf)->key); 71 if (cmp < 0) { 72 path_taking_left(&path); 73 leaf = &(*leaf)->llink; 74 } else if (cmp > 0) { 75 path_taking_right(&path); 76 leaf = &(*leaf)->rlink; 77 } else { 78 return (&(*leaf)->key); 79 } 80 } 81 82 /* Did not find a matching key in the tree. Insert a new node. */ 83 result = *leaf = malloc(sizeof(**leaf)); 84 if (result == NULL) 85 return (NULL); 86 result->key = (void *)key; 87 result->llink = NULL; 88 result->rlink = NULL; 89 result->balance = 0; 90 91 /* 92 * Walk along the same path a second time and adjust the 93 * balances. Except for the first node, all of these nodes must 94 * have a balance of zero, meaning that these nodes will not get 95 * out of balance. 96 */ 97 for (n = *base; n != *leaf;) { 98 if (path_took_left(&path)) { 99 n->balance += 1; 100 n = n->llink; 101 } else { 102 n->balance -= 1; 103 n = n->rlink; 104 } 105 } 106 107 /* 108 * Adjusting the balances may have pushed the balance of the 109 * base node out of range. Perform a rotation to bring the 110 * balance back in range. 111 */ 112 x = *base; 113 if (x->balance > 1) { 114 y = x->llink; 115 if (y->balance < 0) { 116 /* 117 * Left-right case. 118 * 119 * x 120 * / \ z 121 * y D / \ 122 * / \ --> y x 123 * A z /| |\ 124 * / \ A B C D 125 * B C 126 */ 127 z = y->rlink; 128 y->rlink = z->llink; 129 z->llink = y; 130 x->llink = z->rlink; 131 z->rlink = x; 132 *base = z; 133 134 x->balance = z->balance > 0 ? -1 : 0; 135 y->balance = z->balance < 0 ? 1 : 0; 136 z->balance = 0; 137 } else { 138 /* 139 * Left-left case. 140 * 141 * x y 142 * / \ / \ 143 * y C --> A x 144 * / \ / \ 145 * A B B C 146 */ 147 x->llink = y->rlink; 148 y->rlink = x; 149 *base = y; 150 151 x->balance = 0; 152 y->balance = 0; 153 } 154 } else if (x->balance < -1) { 155 y = x->rlink; 156 if (y->balance > 0) { 157 /* 158 * Right-left case. 159 * 160 * x 161 * / \ z 162 * A y / \ 163 * / \ --> x y 164 * z D /| |\ 165 * / \ A B C D 166 * B C 167 */ 168 node_t *z = y->llink; 169 x->rlink = z->llink; 170 z->llink = x; 171 y->llink = z->rlink; 172 z->rlink = y; 173 *base = z; 174 175 x->balance = z->balance < 0 ? 1 : 0; 176 y->balance = z->balance > 0 ? -1 : 0; 177 z->balance = 0; 178 } else { 179 /* 180 * Right-right case. 181 * 182 * x y 183 * / \ / \ 184 * A y --> x C 185 * / \ / \ 186 * B C A B 187 */ 188 x->rlink = y->llink; 189 y->llink = x; 190 *base = y; 191 192 x->balance = 0; 193 y->balance = 0; 194 } 195 } 196 197 /* Return the new entry. */ 198 *rootp = root; 199 return (&result->key); 200 } 201