1 /*-
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37 	posix_tnode **leaf, *result, *n, *x, *y, *z;  in tsearch()  local
53 		if ((*leaf)->balance != 0) {  in tsearch()
55 			 * If we reach a node that has a non-zero  in tsearch()
65 		cmp = compar(key, (*leaf)->key);  in tsearch()
68 			leaf = &(*leaf)->llink;  in tsearch()
71 			leaf = &(*leaf)->rlink;  in tsearch()
77 	/* Did not find a matching key in the tree. Insert a new node. */  in tsearch()
81 	result->key = (void *)key;  in tsearch()
82 	result->llink = NULL;  in tsearch()
83 	result->rlink = NULL;  in tsearch()
84 	result->balance = 0;  in tsearch()
87 	 * Walk along the same path a second time and adjust the  in tsearch()
89 	 * have a balance of zero, meaning that these nodes will not get  in tsearch()
94 			n->balance += 1;  in tsearch()
95 			n = n->llink;  in tsearch()
97 			n->balance -= 1;  in tsearch()
98 			n = n->rlink;  in tsearch()
104 	 * root node out of range. Perform a rotation to bring the  in tsearch()
108 	if (x->balance > 1) {  in tsearch()
109 		y = x->llink;  in tsearch()
110 		if (y->balance < 0) {  in tsearch()
112 			 * Left-right case.  in tsearch()
115 			 *        / \            z  in tsearch()
117 			 *      / \     -->    y   x  in tsearch()
118 			 *     A   z          /|   |\  in tsearch()
119 			 *        / \        A B   C D  in tsearch()
122 			z = y->rlink;  in tsearch()
123 			y->rlink = z->llink;  in tsearch()
124 			z->llink = y;  in tsearch()
125 			x->llink = z->rlink;  in tsearch()
126 			z->rlink = x;  in tsearch()
127 			*rootp = z;  in tsearch()
129 			x->balance = z->balance > 0 ? -1 : 0;  in tsearch()
130 			y->balance = z->balance < 0 ? 1 : 0;  in tsearch()
131 			z->balance = 0;  in tsearch()
134 			 * Left-left case.  in tsearch()
138 			 *      y   C  -->  A   x  in tsearch()
140 			 *    A   B           B   C  in tsearch()
142 			x->llink = y->rlink;  in tsearch()
143 			y->rlink = x;  in tsearch()
146 			x->balance = 0;  in tsearch()
147 			y->balance = 0;  in tsearch()
149 	} else if (x->balance < -1) {  in tsearch()
150 		y = x->rlink;  in tsearch()
151 		if (y->balance > 0) {  in tsearch()
153 			 * Right-left case.  in tsearch()
156 			 *      / \              z  in tsearch()
157 			 *     A   y            / \  in tsearch()
158 			 *        / \   -->    x   y  in tsearch()
159 			 *       z   D        /|   |\  in tsearch()
160 			 *      / \          A B   C D  in tsearch()
163 			posix_tnode *z = y->llink;  in tsearch()  local
164 			x->rlink = z->llink;  in tsearch()
165 			z->llink = x;  in tsearch()
166 			y->llink = z->rlink;  in tsearch()
167 			z->rlink = y;  in tsearch()
168 			*rootp = z;  in tsearch()
170 			x->balance = z->balance < 0 ? 1 : 0;  in tsearch()
171 			y->balance = z->balance > 0 ? -1 : 0;  in tsearch()
172 			z->balance = 0;  in tsearch()
175 			 * Right-right case.  in tsearch()
179 			 *     A   y    -->    x   C  in tsearch()
181 			 *       B   C       A   B  in tsearch()
183 			x->rlink = y->llink;  in tsearch()
184 			y->llink = x;  in tsearch()
187 			x->balance = 0;  in tsearch()
188 			y->balance = 0;  in tsearch()