tsearch.c revision 308090 
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: stable/11/lib/libc/stdlib/tsearch.c 308090 2016-10-29 14:41:22Z ed $");
28
29#define	_SEARCH_PRIVATE
30#include <search.h>
31#include <stdlib.h>
32
33#include "tsearch_path.h"
34
35posix_tnode *
36tsearch(const void *key, posix_tnode **rootp,
37    int (*compar)(const void *, const void *))
38{
39	struct path path;
40	posix_tnode **leaf, *result, *n, *x, *y, *z;
41	int cmp;
42
43	/* POSIX requires that tsearch() returns NULL if rootp is NULL. */
44	if (rootp == NULL)
45		return (NULL);
46
47	/*
48	 * Find the leaf where the new key needs to be inserted. Return
49	 * if we've found an existing entry. Keep track of the path that
50	 * is taken to get to the node, as we will need it to adjust the
51	 * balances.
52	*/
53	path_init(&path);
54	leaf = rootp;
55	while (*leaf != NULL) {
56		if ((*leaf)->balance != 0) {
57			/*
58			 * If we reach a node that has a non-zero
59			 * balance on the way, we know that we won't
60			 * need to perform any rotations above this
61			 * point. In this case rotations are always
62			 * capable of keeping the subtree in balance.
63			 * Make this the root node and reset the path.
64			 */
65			rootp = leaf;
66			path_init(&path);
67		}
68		cmp = compar(key, (*leaf)->key);
69		if (cmp < 0) {
70			path_taking_left(&path);
71			leaf = &(*leaf)->llink;
72		} else if (cmp > 0) {
73			path_taking_right(&path);
74			leaf = &(*leaf)->rlink;
75		} else {
76			return (*leaf);
77		}
78	}
79
80	/* Did not find a matching key in the tree. Insert a new node. */
81	result = *leaf = malloc(sizeof(**leaf));
82	if (result == NULL)
83		return (NULL);
84	result->key = (void *)key;
85	result->llink = NULL;
86	result->rlink = NULL;
87	result->balance = 0;
88
89	/*
90	 * Walk along the same path a second time and adjust the
91	 * balances. Except for the first node, all of these nodes must
92	 * have a balance of zero, meaning that these nodes will not get
93	 * out of balance.
94	*/
95	for (n = *rootp; n != *leaf;) {
96		if (path_took_left(&path)) {
97			n->balance += 1;
98			n = n->llink;
99		} else {
100			n->balance -= 1;
101			n = n->rlink;
102		}
103	}
104
105	/*
106	 * Adjusting the balances may have pushed the balance of the
107	 * root node out of range. Perform a rotation to bring the
108	 * balance back in range.
109	 */
110	x = *rootp;
111	if (x->balance > 1) {
112		y = x->llink;
113		if (y->balance < 0) {
114			/*
115			 * Left-right case.
116			 *
117			 *         x
118			 *        / \            z
119			 *       y   D          / \
120			 *      / \     -->    y   x
121			 *     A   z          /|   |\
122			 *        / \        A B   C D
123			 *       B   C
124			 */
125			z = y->rlink;
126			y->rlink = z->llink;
127			z->llink = y;
128			x->llink = z->rlink;
129			z->rlink = x;
130			*rootp = z;
131
132			x->balance = z->balance > 0 ? -1 : 0;
133			y->balance = z->balance < 0 ? 1 : 0;
134			z->balance = 0;
135		} else {
136			/*
137			 * Left-left case.
138			 *
139			 *        x           y
140			 *       / \         / \
141			 *      y   C  -->  A   x
142			 *     / \             / \
143			 *    A   B           B   C
144			 */
145			x->llink = y->rlink;
146			y->rlink = x;
147			*rootp = y;
148
149			x->balance = 0;
150			y->balance = 0;
151		}
152	} else if (x->balance < -1) {
153		y = x->rlink;
154		if (y->balance > 0) {
155			/*
156			 * Right-left case.
157			 *
158			 *       x
159			 *      / \              z
160			 *     A   y            / \
161			 *        / \   -->    x   y
162			 *       z   D        /|   |\
163			 *      / \          A B   C D
164			 *     B   C
165			 */
166			posix_tnode *z = y->llink;
167			x->rlink = z->llink;
168			z->llink = x;
169			y->llink = z->rlink;
170			z->rlink = y;
171			*rootp = z;
172
173			x->balance = z->balance < 0 ? 1 : 0;
174			y->balance = z->balance > 0 ? -1 : 0;
175			z->balance = 0;
176		} else {
177			/*
178			 * Right-right case.
179			 *
180			 *       x               y
181			 *      / \             / \
182			 *     A   y    -->    x   C
183			 *        / \         / \
184			 *       B   C       A   B
185			 */
186			x->rlink = y->llink;
187			y->llink = x;
188			*rootp = y;
189
190			x->balance = 0;
191			y->balance = 0;
192		}
193	}
194
195	/* Return the new entry. */
196	return (result);
197}
198