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
69void *
70tdelete(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