diff options
| -rw-r--r-- | kern/rbtree.c | 47 | ||||
| -rw-r--r-- | kern/rbtree.h | 20 | ||||
| -rw-r--r-- | kern/rbtree_i.h | 6 |
3 files changed, 60 insertions, 13 deletions
diff --git a/kern/rbtree.c b/kern/rbtree.c index adce033..95873b9 100644 --- a/kern/rbtree.c +++ b/kern/rbtree.c @@ -26,7 +26,7 @@ /* * Return the index of a node in the children array of its parent. * - * The parent parameter must not be null, and must be the parent of the + * The parent parameter must not be NULL, and must be the parent of the * given node. */ static inline int @@ -175,7 +175,7 @@ void rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent, int index, struct rbtree_node *node) { - struct rbtree_node *grand_parent, *uncle, *tmp; + struct rbtree_node *grand_parent, *uncle; int left, right; assert(rbtree_node_check_alignment(parent)); @@ -226,9 +226,7 @@ rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent, */ if (parent->children[right] == node) { rbtree_rotate(tree, parent, left); - tmp = node; - node = parent; - parent = tmp; + parent = node; } /* @@ -244,6 +242,40 @@ rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent, assert(rbtree_node_is_black(tree->root)); } +void * +rbtree_replace_slot(struct rbtree *tree, rbtree_slot_t slot, + struct rbtree_node *node) +{ + struct rbtree_node *parent, *prev; + int index; + + parent = rbtree_slot_parent(slot); + + if (!parent) { + prev = tree->root; + tree->root = node; + } else { + index = rbtree_slot_index(slot); + assert(rbtree_check_index(index)); + prev = parent->children[index]; + parent->children[index] = node; + } + + assert(prev); + *node = *prev; + + for (size_t i = 0; i < ARRAY_SIZE(node->children); i++) { + if (!node->children[i]) { + continue; + } + + + rbtree_node_set_parent(node->children[i], node); + } + + return prev; +} + void rbtree_remove(struct rbtree *tree, struct rbtree_node *node) { @@ -321,7 +353,7 @@ rbtree_remove(struct rbtree *tree, struct rbtree_node *node) /* * The node has been removed, update the colors. The child pointer can - * be null, in which case it is considered a black leaf. + * be NULL, in which case it is considered a black leaf. */ update_color: if (color == RBTREE_COLOR_RED) { @@ -354,6 +386,8 @@ update_color: brother = parent->children[right]; } + assert(brother != NULL); + /* * Brother has no red child. Recolor and repeat at parent. */ @@ -383,6 +417,7 @@ update_color: * (we already know brother is black), set brother's right child black, * rotate left at parent and leave. */ + assert(brother->children[right] != NULL); rbtree_node_set_color(brother, rbtree_node_color(parent)); rbtree_node_set_black(parent); rbtree_node_set_black(brother->children[right]); diff --git a/kern/rbtree.h b/kern/rbtree.h index 3de240b..e805bd9 100644 --- a/kern/rbtree.h +++ b/kern/rbtree.h @@ -48,6 +48,11 @@ struct rbtree; */ typedef uintptr_t rbtree_slot_t; +/* + * Static tree initializer. + */ +#define RBTREE_INITIALIZER { NULL } + #include <kern/rbtree_i.h> /* @@ -209,7 +214,7 @@ MACRO_END * * This macro essentially acts as rbtree_lookup() but in addition to a node, * it also returns a slot, which identifies an insertion point in the tree. - * If the returned node is null, the slot can be used by rbtree_insert_slot() + * If the returned node is NULL, the slot can be used by rbtree_insert_slot() * to insert without the overhead of an additional lookup. * * The constraints that apply to the key parameter are the same as for @@ -247,7 +252,7 @@ MACRO_END * obtain the insertion point with a standard lookup. The insertion point * is obtained by calling rbtree_lookup_slot(). In addition, the new node * must not compare equal to an existing node in the tree (i.e. the slot - * must denote a null node). + * must denote a NULL node). */ static inline void rbtree_insert_slot(struct rbtree *tree, rbtree_slot_t slot, @@ -262,11 +267,18 @@ rbtree_insert_slot(struct rbtree *tree, rbtree_slot_t slot, } /* + * Replace a node at an insertion point in a tree. + * + * The given node must compare strictly equal to the previous node, + * which is returned on completion. + */ +void * rbtree_replace_slot(struct rbtree *tree, rbtree_slot_t slot, + struct rbtree_node *node); + +/* * Remove a node from a tree. * * After completion, the node is stale. - * - * TODO rbtree_replace. */ void rbtree_remove(struct rbtree *tree, struct rbtree_node *node); diff --git a/kern/rbtree_i.h b/kern/rbtree_i.h index 944148e..973899b 100644 --- a/kern/rbtree_i.h +++ b/kern/rbtree_i.h @@ -54,7 +54,7 @@ struct rbtree { * Masks applied on the parent member of a node to obtain either the * color or the parent address. */ -#define RBTREE_COLOR_MASK ((uintptr_t)1) +#define RBTREE_COLOR_MASK ((uintptr_t)0x1) #define RBTREE_PARENT_MASK (~(uintptr_t)0x3) /* @@ -67,7 +67,7 @@ struct rbtree { * Masks applied on slots to obtain either the child index or the parent * address. */ -#define RBTREE_SLOT_INDEX_MASK ((uintptr_t)0x1) +#define RBTREE_SLOT_INDEX_MASK 0x1UL #define RBTREE_SLOT_PARENT_MASK (~RBTREE_SLOT_INDEX_MASK) /* @@ -142,7 +142,7 @@ rbtree_slot_index(rbtree_slot_t slot) * Insert a node in a tree, rebalancing it if necessary. * * The index parameter is the index in the children array of the parent where - * the new node is to be inserted. It is ignored if the parent is null. + * the new node is to be inserted. It is ignored if the parent is NULL. * * This function is intended to be used by the rbtree_insert() macro only. */ |