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