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