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
66void *
67tdelete(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