diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/rbtree.c | 33 | ||||
| -rw-r--r-- | lib/rbtree.h | 4 | ||||
| -rw-r--r-- | lib/virtterm.c | 9 |
3 files changed, 34 insertions, 12 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c index dc9caf1..a63df4d 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -1,4 +1,6 @@ #include "rbtree.h" +#include "api/error.h" +#include "errno.h" static inline int s_direction(const struct rbtree_node *node) @@ -26,10 +28,27 @@ s_rotate(struct rbtree_node *sub, int dir) return new_root; } -void -rbtree_insert(struct rbtree_node *root, struct rbtree_node *node) +struct rbtree_node * +rbtree_search(struct rbtree_node *parent, intmax_t key) { - struct rbtree_node *parent = root; + errno = 0; + intmax_t parent_key = parent->get_key(parent); + if(parent_key == key) return parent; + int searchdir = parent_key < key; + if(parent->children[searchdir]) + return rbtree_search(parent->children[searchdir], key); + + errno = ENOTFOUND; + return 0; +} + +struct rbtree_node * +rbtree_insert(struct rbtree_node *parent, struct rbtree_node *node) +{ + node->color = 1; + if(parent == 0) return node; + + //Seek to the correct b-tree leaf. int direction; while(1) { direction = parent->get_key(parent) < node->get_key(node); @@ -37,20 +56,19 @@ rbtree_insert(struct rbtree_node *root, struct rbtree_node *node) parent = parent->children[direction]; } - node->color = 1; parent->children[direction] = node; node->parent = parent; //Rebalance the tree do { //Tree is already balanced, return - if(parent->color == 0) return; + if(parent->color == 0) return parent; struct rbtree_node *gparent = parent->parent; //Parent is the root node, set parent to black. if(!gparent) { parent->color = 0; - return; + return parent; } direction = s_direction(parent); @@ -68,7 +86,7 @@ rbtree_insert(struct rbtree_node *root, struct rbtree_node *node) s_rotate(gparent, 1-direction); parent->color = 0; gparent->color = 1; - return; + return parent; } //Both the parent and uncle are red. Push up the red and iterate up. @@ -79,6 +97,7 @@ rbtree_insert(struct rbtree_node *root, struct rbtree_node *node) } while((parent = node->parent)); //Tree is balanced now. + return parent; } diff --git a/lib/rbtree.h b/lib/rbtree.h index 22c44f8..1187e5c 100644 --- a/lib/rbtree.h +++ b/lib/rbtree.h @@ -12,6 +12,8 @@ struct rbtree_node intmax_t (*get_key)(struct rbtree_node*); }; -void rbtree_insert(struct rbtree_node *parent, struct rbtree_node *node); +struct rbtree_node *rbtree_search(struct rbtree_node *parent, intmax_t key); + +struct rbtree_node *rbtree_insert(struct rbtree_node *parent, struct rbtree_node *node); #endif diff --git a/lib/virtterm.c b/lib/virtterm.c index 8518530..ce759be 100644 --- a/lib/virtterm.c +++ b/lib/virtterm.c @@ -5,6 +5,7 @@ #include "proc/init.h" #include "jove.h" #include "hal/framebuffer.h" +#include "sys/objdir.h" #include "lib/printf.h" #include "lib/psf.h" #include "lib/string.h" @@ -86,7 +87,7 @@ vt_init() return; } - jove_owned_obj_t *initrd_obj = objdir_getlocal(_rootdir_obj, ROOTDIR_INITRD_I); + jove_owned_obj_t *initrd_obj = objdir_getlocal(_rootdir_obj, INIT_ROOTDIR_INITRD_I); if(obj_gettype(initrd_obj) != JOVE_OBJ_OBJDIR) { kprintf("Initrd is not present. VTT is disabled.\n"); obj_release(initrd_obj); @@ -110,16 +111,16 @@ vt_init() return; } - s_init_vtty.fb_obj = ROOTDIR_FRAMEBUFFER_I; + s_init_vtty.fb_obj = INIT_ROOTDIR_FRAMEBUFFER_I; s_init_vtty.cursor_fg = 0x00FFFFFF; { - jove_owned_obj_t *fb_obj = objdir_getlocal(_rootdir_obj, ROOTDIR_FRAMEBUFFER_I); + jove_owned_obj_t *fb_obj = objdir_getlocal(_rootdir_obj, INIT_ROOTDIR_FRAMEBUFFER_I); s_init_vtty.width = fb_width(fb_obj) / 9; s_init_vtty.height = fb_height(fb_obj) / s_font->char_height; obj_release(fb_obj); - jove_owned_obj_t *vt_obj = objdir_getlocal(_rootdir_obj, ROOTDIR_VIRTTERM_I); + jove_owned_obj_t *vt_obj = objdir_getlocal(_rootdir_obj, INIT_ROOTDIR_VIRTTERM_I); obj_settype(vt_obj, JOVE_OBJ_VIRTTERM); obj_setvalue(vt_obj, (uintmax_t)&s_init_vtty); obj_release(vt_obj); |