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 *
tdelete(const void * restrict key,posix_tnode ** restrict rootp,int (* compar)(const void *,const 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