Lines Matching defs:node
8 struct bintree_node *node;
13 node = subroot;
14 while (node->bl_left)
15 node = node->bl_left;
16 return node;
22 struct bintree_node *node;
25 node = subroot;
26 while (node->bl_right)
27 node = node->bl_right;
28 return node;
35 struct bintree_node *node;
37 node = tree->root;
39 while (node)
42 cmp = (*tree->cmp) (node->data, data);
44 cmp = (node->data - data);
50 node = node->bl_left;
52 node = node->bl_right;
55 if (node)
56 return node->data;
64 struct bintree_node *node;
65 node = bintree_lookup_node_min (tree->root);
66 if (node == NULL)
68 return node->data;
74 struct bintree_node *node;
75 node = bintree_lookup_node_max (tree->root);
76 if (node == NULL)
78 return node->data;
85 struct bintree_node *node, *parent;
87 node = tree->root;
90 while (node)
93 cmp = (*tree->cmp) (node->data, data);
95 cmp = (node->data - data);
100 parent = node;
102 node = node->bl_left;
104 node = node->bl_right;
107 if (node)
110 node = malloc (sizeof (struct bintree_node));
111 memset (node, 0, sizeof (struct bintree_node));
112 node->tree = tree;
113 node->data = data;
117 node->parent = parent;
122 node->parent_link = BL_LEFT;
123 parent->bl_left = node;
127 node->parent_link = BL_RIGHT;
128 parent->bl_right = node;
132 tree->root = node;
139 bintree_remove_nochild (struct bintree_node *node)
141 assert (node->bl_left == NULL && node->bl_right == NULL);
143 if (node->parent == NULL)
144 node->tree->root = NULL;
146 node->parent->link[node->parent_link] = NULL;
150 bintree_remove_onechild (struct bintree_node *node)
152 assert ((node->bl_left == NULL && node->bl_right != NULL) ||
153 (node->bl_left != NULL && node->bl_right == NULL));
155 if (node->bl_left)
157 if (node->parent == NULL)
159 node->tree->root = node->bl_left;
160 node->bl_left->parent = NULL;
164 node->parent->link[node->parent_link] = node->bl_left;
165 node->bl_left->parent = node->parent;
166 node->bl_left->parent_link = node->parent_link;
169 else if (node->bl_right)
171 if (node->parent == NULL)
173 node->tree->root = node->bl_right;
174 node->bl_right->parent = NULL;
178 node->parent->link[node->parent_link] = node->bl_right;
179 node->bl_right->parent = node->parent;
180 node->bl_right->parent_link = node->parent_link;
191 struct bintree_node *node;
193 node = tree->root;
195 while (node)
198 cmp = (*tree->cmp) (node->data, data);
200 cmp = (node->data - data);
206 node = node->bl_left;
208 node = node->bl_right;
211 if (node == NULL)
214 if (node->bl_left == NULL && node->bl_right == NULL)
216 bintree_remove_nochild (node);
217 free (node);
222 if ((node->bl_left == NULL && node->bl_right != NULL) ||
223 (node->bl_left != NULL && node->bl_right == NULL))
225 bintree_remove_onechild (node);
226 free (node);
231 if (node->bl_left != NULL && node->bl_right != NULL)
235 /* find successor of the removing node */
236 successor = bintree_lookup_node_min (node->bl_right);
244 /* swap removing node with successor */
245 successor->parent = node->parent;
246 successor->parent_link = node->parent_link;
247 successor->bl_left = node->bl_left;
248 successor->bl_right = node->bl_right;
250 /* if the successor was the node->bl_right itself,
251 bintree_remove_**child may touch node->bl_right,
263 free (node);
275 bintree_head (struct bintree *tree, struct bintree_node *node)
282 node->parent = NULL;
283 node->bl_left = NULL;
284 node->bl_right = NULL;
285 node->data = NULL;
289 node->tree = head->tree;
290 node->parent = head->parent;
291 node->parent_link = head->parent_link;
292 node->bl_left = head->bl_left;
293 node->bl_right = head->bl_right;
294 node->data = head->data;
298 bintree_end (struct bintree_node *node)
300 if (node->parent || node->bl_left || node->bl_right || node->data)
305 #define GOTO_PROCED_SUBTREE_TOP(node) \
306 while (node->parent && node->parent->bl_right && \
307 node->parent->bl_right->data == node->data) \
309 node->data = node->parent->data; \
310 node->bl_left = node->parent->bl_left; \
311 node->bl_right = node->parent->bl_right; \
312 node->parent_link = node->parent->parent_link; \
313 node->parent = node->parent->parent; \
317 bintree_next (struct bintree_node *node)
321 /* if node have just been removed, current point should have just been
324 if (node->parent == NULL)
326 if (node->tree->root == NULL)
328 assert (node->tree->count == 0);
329 node->parent = NULL;
330 node->bl_left = NULL;
331 node->bl_right = NULL;
332 node->data = NULL;
335 else if (node->tree->root->data != node->data)
336 next = node->tree->root;
338 else if (node->parent->link[node->parent_link] == NULL)
340 if (node->parent_link == BL_LEFT)
341 next = node->parent;
344 GOTO_PROCED_SUBTREE_TOP (node);
345 next = node->parent;
348 else if (node->parent->link[node->parent_link]->data != node->data)
349 next = node->parent->link[node->parent_link];
353 if (node->bl_right)
354 next = bintree_lookup_node_min (node->bl_right);
357 GOTO_PROCED_SUBTREE_TOP (node);
358 next = node->parent;
364 node->tree = next->tree;
365 node->parent = next->parent;
366 node->parent_link = next->parent_link;
367 node->bl_left = next->bl_left;
368 node->bl_right = next->bl_right;
369 node->data = next->data;
373 node->parent = NULL;
374 node->bl_left = NULL;
375 node->bl_right = NULL;
376 node->data = NULL;
394 struct bintree_node node;
396 for (bintree_head (tree, &node); ! bintree_end (&node);
397 bintree_next (&node))
398 bintree_remove (node.data, tree);