rcuja: lookup lower equal cannot reach dead-end

[userspace-rcu.git] / rcuja / rcuja.c

diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c
index b9ece1a9e47a2e98e901bc919b5703f91e4391af..74bb3910a384b67cc410ff09a12c953447b3cded 100644 (file)
--- a/rcuja/rcuja.c
+++ b/rcuja/rcuja.c
@@ -34,7 +34,6 @@
 #include <stdint.h>
 
 #include "rcuja-internal.h"
-#include "bitfield.h"
 
 #ifndef abs
 #define abs_int(a)     ((int) (a) > 0 ? (int) (a) : -((int) (a)))
@@ -1800,6 +1799,13 @@ struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key)
        }
 
        level++;
+
+       /*
+        * From this point, we are guaranteed to be able to find a
+        * "lower than" match. ja_detach_node() guarantees that it is
+        * not possible for a lookup to reach a dead-end.
+        */
+
        /* Find rightmost child of rightmost child (recursively). */
        for (; level < tree_depth; level++) {
                node_flag = ja_node_get_rightmost(node_flag);
@@ -1808,13 +1814,9 @@ struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key)
                        break;
        }
 
-       if (level == tree_depth) {
-               /* Last level lookup succeded. We got a "lower than" match. */
-               head.next = (struct cds_hlist_node *) node_flag;
-               return head;
-       }
+       assert(level == tree_depth);
 
-       /* No match */
+       head.next = (struct cds_hlist_node *) node_flag;
        return head;
 }
 
@@ -2144,6 +2146,11 @@ struct cds_ja_node *cds_ja_add_unique(struct cds_ja *ja, uint64_t key,
  * However, when a child is removed from "linear" nodes, its pointer
  * is set to NULL. We therefore check, while holding the locks, if this
  * pointer is NULL, and return -ENOENT to the caller if it is the case.
+ *
+ * ja_detach_node() ensures that a lookup will _never_ see a branch that
+ * leads to a dead-end: when removing branch, it makes sure to perform
+ * the "cut" at the highest node that has only one child, effectively
+ * replacing it with a NULL pointer.
  */
 static
 int ja_detach_node(struct cds_ja *ja,