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