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 posix_tnode * 36 tsearch(const void *key, posix_tnode **rootp, 37 int (*compar)(const void *, const void *)) 38 { 39 struct path path; 40 posix_tnode **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 47 /* 48 * Find the leaf where the new key needs to be inserted. Return 49 * if we've found an existing entry. Keep track of the path that 50 * is taken to get to the node, as we will need it to adjust the 51 * balances. 52 */ 53 path_init(&path); 54 leaf = rootp; 55 while (*leaf != NULL) { 56 if ((*leaf)->balance != 0) { 57 /* 58 * If we reach a node that has a non-zero 59 * balance on the way, we know that we won't 60 * need to perform any rotations above this 61 * point. In this case rotations are always 62 * capable of keeping the subtree in balance. 63 * Make this the root node and reset the path. 64 */ 65 rootp = leaf; 66 path_init(&path); 67 } 68 cmp = compar(key, (*leaf)->key); 69 if (cmp < 0) { 70 path_taking_left(&path); 71 leaf = &(*leaf)->llink; 72 } else if (cmp > 0) { 73 path_taking_right(&path); 74 leaf = &(*leaf)->rlink; 75 } else { 76 return (*leaf); 77 } 78 } 79 80 /* Did not find a matching key in the tree. Insert a new node. */ 81 result = *leaf = malloc(sizeof(**leaf)); 82 if (result == NULL) 83 return (NULL); 84 result->key = (void *)key; 85 result->llink = NULL; 86 result->rlink = NULL; 87 result->balance = 0; 88 89 /* 90 * Walk along the same path a second time and adjust the 91 * balances. Except for the first node, all of these nodes must 92 * have a balance of zero, meaning that these nodes will not get 93 * out of balance. 94 */ 95 for (n = *rootp; n != *leaf;) { 96 if (path_took_left(&path)) { 97 n->balance += 1; 98 n = n->llink; 99 } else { 100 n->balance -= 1; 101 n = n->rlink; 102 } 103 } 104 105 /* 106 * Adjusting the balances may have pushed the balance of the 107 * root node out of range. Perform a rotation to bring the 108 * balance back in range. 109 */ 110 x = *rootp; 111 if (x->balance > 1) { 112 y = x->llink; 113 if (y->balance < 0) { 114 /* 115 * Left-right case. 116 * 117 * x 118 * / \ z 119 * y D / \ 120 * / \ --> y x 121 * A z /| |\ 122 * / \ A B C D 123 * B C 124 */ 125 z = y->rlink; 126 y->rlink = z->llink; 127 z->llink = y; 128 x->llink = z->rlink; 129 z->rlink = x; 130 *rootp = z; 131 132 x->balance = z->balance > 0 ? -1 : 0; 133 y->balance = z->balance < 0 ? 1 : 0; 134 z->balance = 0; 135 } else { 136 /* 137 * Left-left case. 138 * 139 * x y 140 * / \ / \ 141 * y C --> A x 142 * / \ / \ 143 * A B B C 144 */ 145 x->llink = y->rlink; 146 y->rlink = x; 147 *rootp = y; 148 149 x->balance = 0; 150 y->balance = 0; 151 } 152 } else if (x->balance < -1) { 153 y = x->rlink; 154 if (y->balance > 0) { 155 /* 156 * Right-left case. 157 * 158 * x 159 * / \ z 160 * A y / \ 161 * / \ --> x y 162 * z D /| |\ 163 * / \ A B C D 164 * B C 165 */ 166 posix_tnode *z = y->llink; 167 x->rlink = z->llink; 168 z->llink = x; 169 y->llink = z->rlink; 170 z->rlink = y; 171 *rootp = z; 172 173 x->balance = z->balance < 0 ? 1 : 0; 174 y->balance = z->balance > 0 ? -1 : 0; 175 z->balance = 0; 176 } else { 177 /* 178 * Right-right case. 179 * 180 * x y 181 * / \ / \ 182 * A y --> x C 183 * / \ / \ 184 * B C A B 185 */ 186 x->rlink = y->llink; 187 y->llink = x; 188 *rootp = y; 189 190 x->balance = 0; 191 y->balance = 0; 192 } 193 } 194 195 /* Return the new entry. */ 196 return (result); 197 } 198