MEDIUM: ebtree: only consider the branches matching the scope in lookups
Now when looking up a node via eb32sc_first(), eb32sc_next(), and
eb32sc_lookup_ge(), we only focus on the branches matching the requested
scope. The code must be careful to miss no branch. It changes a little
bit from the previous one because the scope stored on the intermediary
nodes is not exact (since we don't propagate upwards during deletion),
so in case a lookup fails, we have to walk up and pick the next matching
entry.
diff --git a/ebtree/eb32sctree.c b/ebtree/eb32sctree.c
index 96281cf..559c6a6 100644
--- a/ebtree/eb32sctree.c
+++ b/ebtree/eb32sctree.c
@@ -226,6 +226,7 @@
REGPRM2 struct eb32sc_node *eb32sc_lookup_ge(struct eb_root *root, u32 x, unsigned long scope)
{
struct eb32sc_node *node;
+ struct eb_root *curr;
eb_troot_t *troot;
troot = root->b[EB_LEFT];
@@ -240,7 +241,7 @@
*/
node = container_of(eb_untag(troot, EB_LEAF),
struct eb32sc_node, node.branches);
- if (node->key >= x)
+ if ((node->leaf_s & scope) && node->key >= x)
return node;
/* return next */
troot = node->node.leaf_p;
@@ -258,15 +259,10 @@
* next node without first trying to escape from the
* tree.
*/
- if (node->key >= x) {
- troot = node->node.branches.b[EB_LEFT];
- while (eb_gettag(troot) != EB_LEAF)
- troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
- return container_of(eb_untag(troot, EB_LEAF),
- struct eb32sc_node, node.branches);
- }
- /* return next */
- troot = node->node.node_p;
+ if ((node->node_s & scope) && node->key >= x)
+ troot = eb_dotag(&node->node.branches, EB_LEFT);
+ else
+ troot = node->node.node_p;
break;
}
@@ -275,15 +271,10 @@
* large and we need to get its lowest value, or it is too
* small, and we need to get the next value.
*/
- if ((node->key >> node->node.bit) > (x >> node->node.bit)) {
- troot = node->node.branches.b[EB_LEFT];
- return eb32sc_walk_down(troot, EB_LEFT, scope);
- }
-
- /* Further values will be too low here, so return the next
- * unique node (if it exists).
- */
- troot = node->node.node_p;
+ if ((node->node_s & scope) && (node->key >> node->node.bit) > (x >> node->node.bit))
+ troot = eb_dotag(&node->node.branches, EB_LEFT);
+ else
+ troot = node->node.node_p;
break;
}
troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
@@ -293,16 +284,43 @@
* current one which is not below. <troot> is already initialised
* to the parent's branches.
*/
- while (eb_gettag(troot) != EB_LEFT)
- /* Walking up from right branch, so we cannot be below root */
- troot = (eb_root_to_node(eb_untag(troot, EB_RGHT)))->node_p;
+ for (node = NULL; !node; troot = eb_root_to_node(curr)->node_p) {
+ if (eb_gettag(troot) != EB_LEFT) {
+ curr = eb_untag(troot, EB_RGHT);
+ continue;
+ }
- /* Note that <troot> cannot be NULL at this stage */
- troot = (eb_untag(troot, EB_LEFT))->b[EB_RGHT];
- if (eb_clrtag(troot) == NULL)
- return NULL;
+ /* troot points to the branch location we're attached to by the
+ * left above, set curr to the corresponding eb_root.
+ */
+ curr = eb_untag(troot, EB_LEFT);
+
+ /* and go down by the right, but stop at the root */
+ troot = curr->b[EB_RGHT];
+ if (!eb_clrtag(troot))
+ break;
- return eb32sc_walk_down(troot, EB_LEFT, scope);
+ node = eb32sc_walk_down_left(troot, scope);
+ }
+ return node;
+ //while (1) {
+ // while (eb_gettag(troot) != EB_LEFT)
+ // /* Walking up from right branch, so we cannot be below root */
+ // troot = (eb_root_to_node(eb_untag(troot, EB_RGHT)))->node_p;
+ //
+ // /* Note that <t> cannot be NULL at this stage */
+ // root = eb_untag(troot, EB_LEFT);
+ // troot = root->b[EB_RGHT];
+ // if (eb_clrtag(troot) == NULL)
+ // return NULL;
+ //
+ // /* we can't be below the root here */
+ // node = eb32sc_walk_down_left(troot, scope);
+ // if (node)
+ // return node;
+ // /* not found below, this means we have to go up */
+ // troot = eb_root_to_node(root)->node_p;
+ //}
}
/* Removes a leaf node from the tree if it was still in it. Marks the node
diff --git a/ebtree/eb32sctree.h b/ebtree/eb32sctree.h
index df97353..2999252 100644
--- a/ebtree/eb32sctree.h
+++ b/ebtree/eb32sctree.h
@@ -58,42 +58,67 @@
REGPRM2 struct eb32sc_node *eb32sc_insert(struct eb_root *root, struct eb32sc_node *new, unsigned long scope);
void eb32sc_delete(struct eb32sc_node *node);
-/* Walks down starting at root pointer <start>, and always walking on side
- * <side>. It either returns the node hosting the first leaf on that side,
- * or NULL if no leaf is found. <start> may either be NULL or a branch pointer.
- * The pointer to the leaf (or NULL) is returned.
+/* Walks down left starting at root pointer <start>, and follow the leftmost
+ * branch whose scope matches <scope>. It either returns the node hosting the
+ * first leaf on that side, or NULL if no leaf is found. <start> may either be
+ * NULL or a branch pointer. The pointer to the leaf (or NULL) is returned.
*/
-static inline struct eb32sc_node *eb32sc_walk_down(eb_troot_t *start, unsigned int side, unsigned long scope)
+static inline struct eb32sc_node *eb32sc_walk_down_left(eb_troot_t *start, unsigned long scope)
{
- /* A NULL pointer on an empty tree root will be returned as-is */
- while (eb_gettag(start) == EB_NODE)
- start = (eb_untag(start, EB_NODE))->b[side];
- /* NULL is left untouched (root==eb_node, EB_LEAF==0) */
- return eb32sc_entry(eb_root_to_node(eb_untag(start, EB_LEAF)), struct eb32sc_node, node);
+ struct eb_root *root;
+ struct eb_node *node;
+
+ if (unlikely(!start))
+ return NULL;
+
+ while (eb_gettag(start) == EB_NODE) {
+ root = eb_untag(start, EB_NODE);
+ node = eb_root_to_node(root);
+
+ start = node->branches.b[EB_LEFT];
+ if (!(container_of(node, struct eb32sc_node, node)->node_s & scope))
+ start = node->branches.b[EB_RGHT];
+ }
+
+ /* now we have a leaf */
+ node = eb_root_to_node(eb_untag(start, EB_LEAF));
+ if (!(eb32sc_entry(node, struct eb32sc_node, node)->leaf_s & scope))
+ return NULL;
+
+ return eb32sc_entry(node, struct eb32sc_node, node);
}
/* Return next node in the tree, or NULL if none */
static inline struct eb32sc_node *eb32sc_next(struct eb32sc_node *eb32, unsigned long scope)
{
+ struct eb_root *root;
struct eb_node *node = &eb32->node;
eb_troot_t *t = node->leaf_p;
- while (eb_gettag(t) != EB_LEFT)
- /* Walking up from right branch, so we cannot be below root */
- t = (eb_root_to_node(eb_untag(t, EB_RGHT)))->node_p;
+ while (1) {
+ while (eb_gettag(t) != EB_LEFT)
+ /* Walking up from right branch, so we cannot be below root */
+ t = (eb_root_to_node(eb_untag(t, EB_RGHT)))->node_p;
- /* Note that <t> cannot be NULL at this stage */
- t = (eb_untag(t, EB_LEFT))->b[EB_RGHT];
- if (eb_clrtag(t) == NULL)
- return NULL;
+ /* Note that <t> cannot be NULL at this stage */
+ root = eb_untag(t, EB_LEFT);
+ t = root->b[EB_RGHT];
+ if (eb_clrtag(t) == NULL)
+ return NULL;
- return eb32sc_walk_down(t, EB_LEFT, scope);
+ /* we can't be below the root here */
+ eb32 = eb32sc_walk_down_left(t, scope);
+ if (eb32)
+ return eb32;
+ /* not found below, this means we have to go up */
+ t = eb_root_to_node(root)->node_p;
+ }
}
/* Return leftmost node in the tree, or NULL if none */
static inline struct eb32sc_node *eb32sc_first(struct eb_root *root, unsigned long scope)
{
- return eb32sc_walk_down(root->b[0], EB_LEFT, scope);
+ return eb32sc_walk_down_left(root->b[0], scope);
}
#endif /* _EB32SC_TREE_H */