1 #include <private/epoll_inner.h>
2 #include "k_api.h"
3 #include <k_rbtree.h>
4
5
rbr_find(struct k_rbtree_root_t * root,int fd)6 epoll_item_t *rbr_find(struct k_rbtree_root_t *root, int fd)
7 {
8 struct k_rbtree_node_t *rbtnode = root->rbt_node;
9
10 while (rbtnode != NULL) {
11
12 epoll_item_t *mynode = k_rbtree_entry(rbtnode, epoll_item_t, tree_node);
13 if (mynode == NULL) {
14 return NULL;
15 }
16 if (fd < mynode->fd) {
17 rbtnode = rbtnode->rbt_left;
18 } else if (fd > mynode->fd) {
19 rbtnode = rbtnode->rbt_right;
20 } else {
21 return mynode;
22 }
23 }
24
25 return NULL;
26 }
27
rbt_insert(struct k_rbtree_root_t * root,epoll_item_t * item)28 int rbt_insert(struct k_rbtree_root_t *root, epoll_item_t *item)
29 {
30 struct k_rbtree_node_t **tmp = &(root->rbt_node), *parent = NULL;
31
32 /* Figure out where to put new node */
33 while (*tmp) {
34 epoll_item_t *my = k_rbtree_entry(*tmp, epoll_item_t, tree_node);
35 if (my == NULL) {
36 return -1;
37 }
38 parent = *tmp;
39 if (item->fd <= my->fd) {
40 tmp = &((*tmp)->rbt_left);
41 } else if (item->fd > my->fd) {
42 tmp = &((*tmp)->rbt_right);
43 } else {
44 return -1;
45 }
46 }
47
48 /* Add new node and rebalance tree. */
49 k_rbtree_link_node(&item->tree_node, parent, tmp);
50 k_rbtree_insert_color(&item->tree_node, root);
51
52 return 0;
53 }
54
rbt_delete(struct k_rbtree_root_t * root,int fd)55 int rbt_delete(struct k_rbtree_root_t *root, int fd)
56 {
57 epoll_item_t *mynode;
58
59 if ((mynode = rbr_find(root, fd)) == NULL) {
60 return -1;
61 }
62
63 k_rbtree_erase(&mynode->tree_node, root);
64 free(mynode);
65 return 0;
66 }
67