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