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