24 static lv_rb_node_t * rb_create_node(lv_rb_t * tree);
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);
29 static void rb_delete_color(lv_rb_t * tree, lv_rb_node_t * node1, lv_rb_node_t * node2);
47 bool lv_rb_init(lv_rb_t * tree, lv_rb_compare_t compare, size_t node_size)  in lv_rb_init()  argument
49     LV_ASSERT_NULL(tree);  in lv_rb_init()
53     if(tree == NULL || compare == NULL || node_size == 0) {  in lv_rb_init()
57     lv_memzero(tree, sizeof(lv_rb_t));  in lv_rb_init()
59     tree->root = NULL;  in lv_rb_init()
60     tree->compare = compare;  in lv_rb_init()
61     tree->size = node_size;  in lv_rb_init()
66 lv_rb_node_t * lv_rb_insert(lv_rb_t * tree, void * key)  in lv_rb_insert()  argument
68     LV_ASSERT_NULL(tree);  in lv_rb_insert()
69     if(tree == NULL) {  in lv_rb_insert()
73     lv_rb_node_t * node = lv_rb_find(tree, key);  in lv_rb_insert()
76         node = rb_create_node(tree);  in lv_rb_insert()
79         if(tree->root == NULL) {  in lv_rb_insert()
80             tree->root = node;  in lv_rb_insert()
89     lv_rb_node_t * parent = rb_find_leaf_parent(tree, node);  in lv_rb_insert()
94     if(tree->compare(key, parent->data) < 0) parent->left = node;  in lv_rb_insert()
97     rb_insert_color(tree, node);  in lv_rb_insert()
103 lv_rb_node_t * lv_rb_find(lv_rb_t * tree, const void * key)  in lv_rb_find()  argument
105     LV_ASSERT_NULL(tree);  in lv_rb_find()
106     if(tree == NULL) {  in lv_rb_find()
110     lv_rb_node_t * current = tree->root;  in lv_rb_find()
113         lv_rb_compare_res_t cmp = tree->compare(key, current->data);  in lv_rb_find()
129 void * lv_rb_remove_node(lv_rb_t * tree, lv_rb_node_t * node)  in lv_rb_remove_node()  argument
148             tree->root = replace;  in lv_rb_remove_node()
173             rb_delete_color(tree, child, parent);  in lv_rb_remove_node()
198         tree->root = child;  in lv_rb_remove_node()
202         rb_delete_color(tree, child, parent);  in lv_rb_remove_node()
210 void * lv_rb_remove(lv_rb_t * tree, const void * key)  in lv_rb_remove()  argument
212     LV_ASSERT_NULL(tree);  in lv_rb_remove()
213     if(tree == NULL) {  in lv_rb_remove()
217     lv_rb_node_t * node = lv_rb_find(tree, key);  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
229     LV_ASSERT_NULL(tree);  in lv_rb_drop_node()
230     if(tree == NULL) {  in lv_rb_drop_node()
234     void * data = lv_rb_remove_node(tree, node);  in lv_rb_drop_node()
242 bool lv_rb_drop(lv_rb_t * tree, const void * key)  in lv_rb_drop()  argument
244     LV_ASSERT_NULL(tree);  in lv_rb_drop()
245     if(tree == NULL) {  in lv_rb_drop()
249     void * data = lv_rb_remove(tree, key);  in lv_rb_drop()
257 void lv_rb_destroy(lv_rb_t * tree)  in lv_rb_destroy()  argument
259     LV_ASSERT_NULL(tree);  in lv_rb_destroy()
261     if(tree == NULL) {  in lv_rb_destroy()
265     lv_rb_node_t * node = tree->root;  in lv_rb_destroy()
290     tree->root = NULL;  in lv_rb_destroy()
293 lv_rb_node_t * lv_rb_minimum(lv_rb_t * tree)  in lv_rb_minimum()  argument
295     LV_ASSERT_NULL(tree);  in lv_rb_minimum()
296     if(tree == NULL) {  in lv_rb_minimum()
299     return lv_rb_minimum_from(tree->root);  in lv_rb_minimum()
302 lv_rb_node_t * lv_rb_maximum(lv_rb_t * tree)  in lv_rb_maximum()  argument
304     LV_ASSERT_NULL(tree);  in lv_rb_maximum()
305     if(tree == NULL) {  in lv_rb_maximum()
308     return lv_rb_maximum_from(tree->root);  in lv_rb_maximum()
333 static lv_rb_node_t * rb_create_node(lv_rb_t * tree)  in rb_create_node()  argument
341     node->data = lv_malloc_zeroed(tree->size);  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
357     lv_rb_node_t * current = tree->root;  in rb_find_leaf_parent()
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
386         tree->root = 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
411         tree->root = 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
446                 rb_left_rotate(tree, parent);  in rb_insert_color()
454             rb_right_rotate(tree, gparent);  in rb_insert_color()
470                 rb_right_rotate(tree, parent);  in rb_insert_color()
478             rb_left_rotate(tree, gparent);  in rb_insert_color()
482     tree->root->color = LV_RB_COLOR_BLACK;  in rb_insert_color()
485 static void rb_delete_color(lv_rb_t * tree, lv_rb_node_t * node1, lv_rb_node_t * node2)  in rb_delete_color()  argument
487     LV_ASSERT_NULL(tree);  in rb_delete_color()
488     if(tree == NULL) {  in rb_delete_color()
492     while((node1 == NULL || node1->color == LV_RB_COLOR_BLACK) && node1 != tree->root) {  in rb_delete_color()
498                 rb_left_rotate(tree, node2);  in rb_delete_color()
512                     rb_right_rotate(tree, pNode2);  in rb_delete_color()
518                 rb_left_rotate(tree, node2);  in rb_delete_color()
519                 node1 = tree->root;  in rb_delete_color()
528                 rb_right_rotate(tree, node2);  in rb_delete_color()
542                     rb_left_rotate(tree, pNode2);  in rb_delete_color()
548                 rb_right_rotate(tree, node2);  in rb_delete_color()
549                 node1 = tree->root;  in rb_delete_color()