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 <stdbool.h> 30 #include <stdlib.h> 31 32 #include "tsearch_path.h" 33 34 /* 35 * Makes a step to the left along the binary search tree. This step is 36 * also saved, so it can be replayed while rebalancing. 37 */ 38 #define GO_LEFT() do { \ 39 if ((*leaf)->balance == 0 || \ 40 ((*leaf)->balance < 0 && (*leaf)->rlink->balance == 0)) { \ 41 /* \ 42 * If we reach a node that is balanced, or has a child \ 43 * in the opposite direction that is balanced, we know \ 44 * that we won't need to perform any rotations above \ 45 * this point. In this case rotations are always \ 46 * capable of keeping the subtree in balance. Make \ 47 * this the root node and reset the path. \ 48 */ \ 49 rootp = leaf; \ 50 path_init(&path); \ 51 } \ 52 path_taking_left(&path); \ 53 leaf = &(*leaf)->llink; \ 54 } while (0) 55 56 /* Makes a step to the right along the binary search tree. */ 57 #define GO_RIGHT() do { \ 58 if ((*leaf)->balance == 0 || \ 59 ((*leaf)->balance > 0 && (*leaf)->llink->balance == 0)) { \ 60 rootp = leaf; \ 61 path_init(&path); \ 62 } \ 63 path_taking_right(&path); \ 64 leaf = &(*leaf)->rlink; \ 65 } while (0) 66 67 void * 68 tdelete(const void *restrict key, posix_tnode **restrict rootp, 69 int (*compar)(const void *, const void *)) 70 { 71 struct path path; 72 posix_tnode **leaf, *old, **n, *x, *y, *z, *result; 73 int cmp; 74 75 /* POSIX requires that tdelete() returns NULL if rootp is NULL. */ 76 if (rootp == NULL) 77 return (NULL); 78 79 /* 80 * Find the leaf that needs to be removed. Return if we cannot 81 * find an existing entry. Keep track of the path that is taken 82 * to get to the node, as we will need it to adjust the 83 * balances. 84 */ 85 result = (posix_tnode *)1; 86 path_init(&path); 87 leaf = rootp; 88 for (;;) { 89 if (*leaf == NULL) 90 return (NULL); 91 cmp = compar(key, (*leaf)->key); 92 if (cmp < 0) { 93 result = *leaf; 94 GO_LEFT(); 95 } else if (cmp > 0) { 96 result = *leaf; 97 GO_RIGHT(); 98 } else { 99 break; 100 } 101 } 102 103 /* Found a matching key in the tree. Remove the node. */ 104 if ((*leaf)->llink == NULL) { 105 /* Node has no left children. Replace by its right subtree. */ 106 old = *leaf; 107 *leaf = old->rlink; 108 free(old); 109 } else { 110 /* 111 * Node has left children. Replace this node's key by 112 * its predecessor's and remove that node instead. 113 */ 114 void **keyp = &(*leaf)->key; 115 GO_LEFT(); 116 while ((*leaf)->rlink != NULL) 117 GO_RIGHT(); 118 old = *leaf; 119 *keyp = old->key; 120 *leaf = old->llink; 121 free(old); 122 } 123 124 /* 125 * Walk along the same path a second time and adjust the 126 * balances. Though this code looks similar to the rebalancing 127 * performed in tsearch(), it is not identical. We now also need 128 * to consider the case of outward imbalance in the right-right 129 * and left-left case that only exists when deleting. Hence the 130 * duplication of code. 131 */ 132 for (n = rootp; n != leaf;) { 133 if (path_took_left(&path)) { 134 x = *n; 135 if (x->balance < 0) { 136 y = x->rlink; 137 if (y->balance > 0) { 138 /* Right-left case. */ 139 z = y->llink; 140 x->rlink = z->llink; 141 z->llink = x; 142 y->llink = z->rlink; 143 z->rlink = y; 144 *n = z; 145 146 x->balance = z->balance < 0 ? 1 : 0; 147 y->balance = z->balance > 0 ? -1 : 0; 148 z->balance = 0; 149 } else { 150 /* Right-right case. */ 151 x->rlink = y->llink; 152 y->llink = x; 153 *n = y; 154 155 if (y->balance < 0) { 156 x->balance = 0; 157 y->balance = 0; 158 } else { 159 x->balance = -1; 160 y->balance = 1; 161 } 162 } 163 } else { 164 --x->balance; 165 } 166 n = &x->llink; 167 } else { 168 x = *n; 169 if (x->balance > 0) { 170 y = x->llink; 171 if (y->balance < 0) { 172 /* Left-right case. */ 173 z = y->rlink; 174 y->rlink = z->llink; 175 z->llink = y; 176 x->llink = z->rlink; 177 z->rlink = x; 178 *n = z; 179 180 x->balance = z->balance > 0 ? -1 : 0; 181 y->balance = z->balance < 0 ? 1 : 0; 182 z->balance = 0; 183 } else { 184 /* Left-left case. */ 185 x->llink = y->rlink; 186 y->rlink = x; 187 *n = y; 188 189 if (y->balance > 0) { 190 x->balance = 0; 191 y->balance = 0; 192 } else { 193 x->balance = 1; 194 y->balance = -1; 195 } 196 } 197 } else { 198 ++x->balance; 199 } 200 n = &x->rlink; 201 } 202 } 203 204 /* Return the parent of the old entry. */ 205 return (result); 206 } 207