Lines Matching refs:node
25 static lv_rb_node_t * rb_find_leaf_parent(lv_rb_t * tree, lv_rb_node_t * node);
26 static void rb_right_rotate(lv_rb_t * tree, lv_rb_node_t * node);
27 static void rb_left_rotate(lv_rb_t * tree, lv_rb_node_t * node);
28 static void rb_insert_color(lv_rb_t * tree, lv_rb_node_t * node);
73 lv_rb_node_t * node = lv_rb_find(tree, key); in lv_rb_insert() local
74 if(node) return node; in lv_rb_insert()
76 node = rb_create_node(tree); in lv_rb_insert()
77 if(node == NULL) return NULL; in lv_rb_insert()
80 tree->root = node; in lv_rb_insert()
81 node->parent = NULL; in lv_rb_insert()
82 node->color = LV_RB_COLOR_BLACK; in lv_rb_insert()
83 return node; in lv_rb_insert()
87 void * new_data = node->data; in lv_rb_insert()
88 node->data = key; in lv_rb_insert()
89 lv_rb_node_t * parent = rb_find_leaf_parent(tree, node); in lv_rb_insert()
91 node->parent = parent; in lv_rb_insert()
92 node->color = LV_RB_COLOR_RED; in lv_rb_insert()
94 if(tree->compare(key, parent->data) < 0) parent->left = node; in lv_rb_insert()
95 else parent->right = node; in lv_rb_insert()
97 rb_insert_color(tree, node); in lv_rb_insert()
99 node->data = new_data; in lv_rb_insert()
100 return node; in lv_rb_insert()
129 void * lv_rb_remove_node(lv_rb_t * tree, lv_rb_node_t * node) in lv_rb_remove_node() argument
135 if(node->left != NULL && node->right != NULL) { in lv_rb_remove_node()
136 lv_rb_node_t * replace = node; in lv_rb_remove_node()
139 if(node->parent != NULL) { in lv_rb_remove_node()
140 if(node->parent->left == node) { in lv_rb_remove_node()
141 node->parent->left = replace; in lv_rb_remove_node()
144 node->parent->right = replace; in lv_rb_remove_node()
155 if(parent == node) { in lv_rb_remove_node()
163 replace->right = node->right; in lv_rb_remove_node()
164 node->right->parent = replace; in lv_rb_remove_node()
167 replace->parent = node->parent; in lv_rb_remove_node()
168 replace->color = node->color; in lv_rb_remove_node()
169 replace->left = node->left; in lv_rb_remove_node()
170 node->left->parent = replace; in lv_rb_remove_node()
176 void * data = node->data; in lv_rb_remove_node()
177 lv_free(node); in lv_rb_remove_node()
181 child = node->right != NULL ? node->right : node->left; in lv_rb_remove_node()
182 parent = node->parent; in lv_rb_remove_node()
183 color = node->color; in lv_rb_remove_node()
190 if(parent->left == node) { in lv_rb_remove_node()
205 void * data = node->data; in lv_rb_remove_node()
206 lv_free(node); in lv_rb_remove_node()
217 lv_rb_node_t * node = lv_rb_find(tree, key); in lv_rb_remove() local
218 LV_ASSERT_NULL(node); in lv_rb_remove()
219 if(node == NULL) { in lv_rb_remove()
224 return lv_rb_remove_node(tree, node); in lv_rb_remove()
227 bool lv_rb_drop_node(lv_rb_t * tree, lv_rb_node_t * node) in lv_rb_drop_node() argument
234 void * data = lv_rb_remove_node(tree, node); in lv_rb_drop_node()
265 lv_rb_node_t * node = tree->root; in lv_rb_destroy() local
268 while(node != NULL) { in lv_rb_destroy()
269 if(node->left != NULL) { in lv_rb_destroy()
270 node = node->left; in lv_rb_destroy()
272 else if(node->right != NULL) { in lv_rb_destroy()
273 node = node->right; in lv_rb_destroy()
276 parent = node->parent; in lv_rb_destroy()
278 if(parent->left == node) { in lv_rb_destroy()
285 lv_free(node->data); in lv_rb_destroy()
286 lv_free(node); in lv_rb_destroy()
287 node = parent; in lv_rb_destroy()
311 lv_rb_node_t * lv_rb_minimum_from(lv_rb_node_t * node) in lv_rb_minimum_from() argument
313 while(node->left != NULL) { in lv_rb_minimum_from()
314 node = node->left; in lv_rb_minimum_from()
317 return node; in lv_rb_minimum_from()
320 lv_rb_node_t * lv_rb_maximum_from(lv_rb_node_t * node) in lv_rb_maximum_from() argument
322 while(node->right != NULL) { in lv_rb_maximum_from()
323 node = node->right; in lv_rb_maximum_from()
326 return node; in lv_rb_maximum_from()
335 lv_rb_node_t * node = lv_malloc_zeroed(sizeof(lv_rb_node_t)); in rb_create_node() local
336 LV_ASSERT_MALLOC(node); in rb_create_node()
337 if(node == NULL) { in rb_create_node()
341 node->data = lv_malloc_zeroed(tree->size); in rb_create_node()
342 LV_ASSERT_MALLOC(node->data); in rb_create_node()
343 if(node->data == NULL) { in rb_create_node()
344 lv_free(node); in rb_create_node()
348 node->color = LV_RB_COLOR_RED; in rb_create_node()
349 node->left = NULL; in rb_create_node()
350 node->right = NULL; in rb_create_node()
352 return node; in rb_create_node()
355 static lv_rb_node_t * rb_find_leaf_parent(lv_rb_t * tree, lv_rb_node_t * node) in rb_find_leaf_parent() argument
363 if(tree->compare(node->data, current->data) < 0) { in rb_find_leaf_parent()
374 static void rb_right_rotate(lv_rb_t * tree, lv_rb_node_t * node) in rb_right_rotate() argument
376 lv_rb_node_t * left = node->left; in rb_right_rotate()
377 node->left = left->right; in rb_right_rotate()
380 left->right->parent = node; in rb_right_rotate()
383 left->parent = node->parent; in rb_right_rotate()
385 if(node->parent == NULL) { in rb_right_rotate()
388 else if(node == node->parent->right) { in rb_right_rotate()
389 node->parent->right = left; in rb_right_rotate()
392 node->parent->left = left; in rb_right_rotate()
395 left->right = node; in rb_right_rotate()
396 node->parent = left; in rb_right_rotate()
399 static void rb_left_rotate(lv_rb_t * tree, lv_rb_node_t * node) in rb_left_rotate() argument
401 lv_rb_node_t * right = node->right; in rb_left_rotate()
402 node->right = right->left; in rb_left_rotate()
405 right->left->parent = node; in rb_left_rotate()
408 right->parent = node->parent; in rb_left_rotate()
410 if(node->parent == NULL) { in rb_left_rotate()
413 else if(node == node->parent->left) { in rb_left_rotate()
414 node->parent->left = right; in rb_left_rotate()
417 node->parent->right = right; in rb_left_rotate()
420 right->left = node; in rb_left_rotate()
421 node->parent = right; in rb_left_rotate()
424 static void rb_insert_color(lv_rb_t * tree, lv_rb_node_t * node) in rb_insert_color() argument
429 while((parent = node->parent) && parent->color == LV_RB_COLOR_RED) { in rb_insert_color()
439 node = gparent; in rb_insert_color()
444 if(parent->right == node) { in rb_insert_color()
448 parent = node; in rb_insert_color()
449 node = tmp; in rb_insert_color()
463 node = gparent; in rb_insert_color()
468 if(parent->left == node) { in rb_insert_color()
472 parent = node; in rb_insert_color()
473 node = tmp; in rb_insert_color()