Lines Matching refs:nodes
80 /* traverse to left-most child, count black nodes */
95 * 4) Every red node must have two black child nodes
96 * 5) Every path to a leaf contains the same number of black nodes
98 * Note that NULL nodes are considered black, which is why we don't
179 static void shuffle(void **nodes, size_t n_memb) {
185 t = nodes[j];
186 nodes[j] = nodes[i];
187 nodes[i] = t;
193 CRBNode *nodes[256];
198 /* allocate and initialize all nodes */
199 for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
200 nodes[i] = malloc(sizeof(*nodes[i]));
201 assert(nodes[i]);
202 c_rbnode_init(nodes[i]);
205 /* shuffle nodes and validate *empty* tree */
206 shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
210 /* add all nodes and validate after each insertion */
211 for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
212 insert(&t, nodes[i]);
217 /* shuffle nodes again */
218 shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
220 /* remove all nodes (in different order) and validate on each round */
221 for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
222 c_rbtree_remove(&t, nodes[i]);
224 assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
225 c_rbnode_init(nodes[i]);
228 /* shuffle nodes and validate *empty* tree again */
229 shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
233 /* add all nodes again */
234 for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
235 insert(&t, nodes[i]);
240 /* 4 times, remove half of the nodes and add them again */
242 /* shuffle nodes again */
243 shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
245 /* remove half of the nodes */
246 for (i = 0; i < sizeof(nodes) / sizeof(*nodes) / 2; ++i) {
247 c_rbtree_remove(&t, nodes[i]);
249 assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
250 c_rbnode_init(nodes[i]);
254 shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes) / 2);
257 for (i = 0; i < sizeof(nodes) / sizeof(*nodes) / 2; ++i) {
258 insert(&t, nodes[i]);
260 assert(n == sizeof(nodes) / sizeof(*nodes) / 2 + i + 1);
264 /* shuffle nodes again */
265 shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
268 for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
269 c_rbtree_remove(&t, nodes[i]);
271 assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
272 c_rbnode_init(nodes[i]);
275 /* free nodes again */
276 for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
277 free(nodes[i]);
298 Node *nodes[2048];
301 /* allocate and initialize all nodes */
302 for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
303 nodes[i] = malloc(sizeof(*nodes[i]));
304 assert(nodes[i]);
305 nodes[i]->key = i;
306 c_rbnode_init(&nodes[i]->rb);
309 /* shuffle nodes */
310 shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
312 /* add all nodes, and verify that each node is linked */
313 for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
314 assert(!c_rbnode_is_linked(&nodes[i]->rb));
315 assert(!c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
317 slot = c_rbtree_find_slot(&t, compare, (void *)nodes[i]->key, &p);
319 c_rbtree_add(&t, p, slot, &nodes[i]->rb);
321 assert(c_rbnode_is_linked(&nodes[i]->rb));
322 assert(nodes[i] == c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
325 /* shuffle nodes again */
326 shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
328 /* remove all nodes (in different order) */
329 for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
330 assert(c_rbnode_is_linked(&nodes[i]->rb));
331 assert(nodes[i] == c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
333 c_rbtree_remove_init(&t, &nodes[i]->rb);
335 assert(!c_rbnode_is_linked(&nodes[i]->rb));
336 assert(!c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
339 /* free nodes again */
340 for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
341 free(nodes[i]);