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 path_taking_right(&path); \ 66 leaf = &(*leaf)->rlink; \ 67 } while (0) 68 69 void * 70 tdelete(const void *restrict key, void **restrict rootp, 71 int (*compar)(const void *, const void *)) 72 { 73 struct path path; 74 node_t *root, **base, **leaf, *old, **n, *x, *y, *z; 75 void *result; 76 int cmp; 77 78 /* POSIX requires that tdelete() returns NULL if rootp is NULL. */ 79 if (rootp == NULL) 80 return (NULL); 81 root = *rootp; 82 83 /* 84 * Find the leaf that needs to be removed. Return if we cannot 85 * find an existing entry. Keep track of the path that is taken 86 * to get to the node, as we will need it to adjust the 87 * balances. 88 */ 89 result = (void *)1; 90 path_init(&path); 91 base = &root; 92 leaf = &root; 93 for (;;) { 94 if (*leaf == NULL) 95 return (NULL); 96 cmp = compar(key, (*leaf)->key); 97 if (cmp < 0) { 98 result = &(*leaf)->key; 99 GO_LEFT(); 100 } else if (cmp > 0) { 101 result = &(*leaf)->key; 102 GO_RIGHT(); 103 } else { 104 break; 105 } 106 } 107 108 /* Found a matching key in the tree. Remove the node. */ 109 if ((*leaf)->llink == NULL) { 110 /* Node has no left children. Replace by its right subtree. */ 111 old = *leaf; 112 *leaf = old->rlink; 113 free(old); 114 } else { 115 /* 116 * Node has left children. Replace this node's key by 117 * its predecessor's and remove that node instead. 118 */ 119 void **keyp = &(*leaf)->key; 120 GO_LEFT(); 121 while ((*leaf)->rlink != NULL) 122 GO_RIGHT(); 123 old = *leaf; 124 *keyp = old->key; 125 *leaf = old->llink; 126 free(old); 127 } 128 129 /* 130 * Walk along the same path a second time and adjust the 131 * balances. Though this code looks similar to the rebalancing 132 * performed in tsearch(), it is not identical. We now also need 133 * to consider the case of outward imbalance in the right-right 134 * and left-left case that only exists when deleting. Hence the 135 * duplication of code. 136 */ 137 for (n = base; n != leaf;) { 138 if (path_took_left(&path)) { 139 x = *n; 140 if (x->balance < 0) { 141 y = x->rlink; 142 if (y->balance > 0) { 143 /* Right-left case. */ 144 z = y->llink; 145 x->rlink = z->llink; 146 z->llink = x; 147 y->llink = z->rlink; 148 z->rlink = y; 149 *n = z; 150 151 x->balance = z->balance < 0 ? 1 : 0; 152 y->balance = z->balance > 0 ? -1 : 0; 153 z->balance = 0; 154 } else { 155 /* Right-right case. */ 156 x->rlink = y->llink; 157 y->llink = x; 158 *n = y; 159 160 if (y->balance < 0) { 161 x->balance = 0; 162 y->balance = 0; 163 } else { 164 x->balance = -1; 165 y->balance = 1; 166 } 167 } 168 } else { 169 --x->balance; 170 } 171 n = &x->llink; 172 } else { 173 x = *n; 174 if (x->balance > 0) { 175 y = x->llink; 176 if (y->balance < 0) { 177 /* Left-right case. */ 178 z = y->rlink; 179 y->rlink = z->llink; 180 z->llink = y; 181 x->llink = z->rlink; 182 z->rlink = x; 183 *n = z; 184 185 x->balance = z->balance > 0 ? -1 : 0; 186 y->balance = z->balance < 0 ? 1 : 0; 187 z->balance = 0; 188 } else { 189 /* Left-left case. */ 190 x->llink = y->rlink; 191 y->rlink = x; 192 *n = y; 193 194 if (y->balance > 0) { 195 x->balance = 0; 196 y->balance = 0; 197 } else { 198 x->balance = 1; 199 y->balance = -1; 200 } 201 } 202 } else { 203 ++x->balance; 204 } 205 n = &x->rlink; 206 } 207 } 208 209 /* Return the parent of the old entry. */ 210 *rootp = root; 211 return (result); 212 } 213