Lines Matching refs:node
30 static void freeNode(AvlNode *node);
32 static AvlNode *lookup(const struct stree *avl, AvlNode *node, const struct sm_state *sm);
41 static bool checkBalances(AvlNode *node, int *height);
43 static size_t countNode(AvlNode *node);
154 AvlNode *node = NULL; in avl_remove() local
164 remove_sm(*avl, &(*avl)->root, sm, &node); in avl_remove()
169 if (node == NULL) { in avl_remove()
172 free(node); in avl_remove()
179 AvlNode *node = malloc(sizeof(*node)); in mkNode() local
181 assert(node != NULL); in mkNode()
183 node->sm = sm; in mkNode()
184 node->lr[0] = NULL; in mkNode()
185 node->lr[1] = NULL; in mkNode()
186 node->balance = 0; in mkNode()
187 return node; in mkNode()
190 static void freeNode(AvlNode *node) in freeNode() argument
192 if (node) { in freeNode()
193 freeNode(node->lr[0]); in freeNode()
194 freeNode(node->lr[1]); in freeNode()
195 free(node); in freeNode()
199 static AvlNode *lookup(const struct stree *avl, AvlNode *node, const struct sm_state *sm) in lookup() argument
203 if (node == NULL) in lookup()
206 cmp = cmp_tracker(sm, node->sm); in lookup()
209 return lookup(avl, node->lr[0], sm); in lookup()
211 return lookup(avl, node->lr[1], sm); in lookup()
212 return node; in lookup()
227 AvlNode *node = *p; in insert_sm() local
228 int cmp = cmp_tracker(sm, node->sm); in insert_sm()
231 node->sm = sm; in insert_sm()
235 if (!insert_sm(avl, &node->lr[side(cmp)], sm)) in insert_sm()
255 AvlNode *node = *p; in remove_sm() local
256 int cmp = cmp_tracker(sm, node->sm); in remove_sm()
259 *ret = node; in remove_sm()
262 if (node->lr[0] != NULL && node->lr[1] != NULL) { in remove_sm()
269 side = node->balance <= 0 ? 0 : 1; in remove_sm()
271 shrunk = removeExtremum(&node->lr[side], 1 - side, &replacement); in remove_sm()
273 replacement->lr[0] = node->lr[0]; in remove_sm()
274 replacement->lr[1] = node->lr[1]; in remove_sm()
275 replacement->balance = node->balance; in remove_sm()
287 if (node->lr[0] != NULL) in remove_sm()
288 *p = node->lr[0]; in remove_sm()
290 *p = node->lr[1]; in remove_sm()
295 if (!remove_sm(avl, &node->lr[side(cmp)], sm, ret)) in remove_sm()
315 AvlNode *node = *p; in removeExtremum() local
317 if (node->lr[side] == NULL) { in removeExtremum()
318 *ret = node; in removeExtremum()
319 *p = node->lr[1 - side]; in removeExtremum()
323 if (!removeExtremum(&node->lr[side], side, ret)) in removeExtremum()
357 AvlNode *node = *p, in balance() local
358 *child = node->lr[side]; in balance()
364 node->lr[side] = child->lr[opposite]; in balance()
365 child->lr[opposite] = node; in balance()
369 node->balance = -child->balance; in balance()
375 node->lr[side] = grandchild->lr[opposite]; in balance()
378 grandchild->lr[opposite] = node; in balance()
381 node->balance = 0; in balance()
385 node->balance = -bal; in balance()
405 static bool checkBalances(AvlNode *node, int *height) in checkBalances() argument
407 if (node) { in checkBalances()
410 if (!checkBalances(node->lr[0], &h0)) in checkBalances()
412 if (!checkBalances(node->lr[1], &h1)) in checkBalances()
415 if (node->balance != h1 - h0 || node->balance < -1 || node->balance > 1) in checkBalances()
442 static size_t countNode(AvlNode *node) in countNode() argument
444 if (node) in countNode()
445 return 1 + countNode(node->lr[0]) + countNode(node->lr[1]); in countNode()
455 AvlNode *node; in avl_iter_begin() local
462 iter->node = NULL; in avl_iter_begin()
465 node = avl->root; in avl_iter_begin()
467 while (node->lr[dir] != NULL) { in avl_iter_begin()
468 iter->stack[iter->stack_index++] = node; in avl_iter_begin()
469 node = node->lr[dir]; in avl_iter_begin()
472 iter->sm = (struct sm_state *) node->sm; in avl_iter_begin()
473 iter->node = node; in avl_iter_begin()
478 AvlNode *node = iter->node; in avl_iter_next() local
481 if (node == NULL) in avl_iter_next()
484 node = node->lr[1 - dir]; in avl_iter_next()
485 if (node != NULL) { in avl_iter_next()
486 while (node->lr[dir] != NULL) { in avl_iter_next()
487 iter->stack[iter->stack_index++] = node; in avl_iter_next()
488 node = node->lr[dir]; in avl_iter_next()
491 node = iter->stack[--iter->stack_index]; in avl_iter_next()
494 iter->node = NULL; in avl_iter_next()
498 iter->node = node; in avl_iter_next()
499 iter->sm = (struct sm_state *) node->sm; in avl_iter_next()