+ return (struct cds_ja_node *) node_flag;
+}
+
+static
+struct cds_ja_node *cds_ja_lookup_inequality(struct cds_ja *ja, uint64_t key,
+ uint64_t *result_key, enum ja_lookup_inequality mode)
+{
+ int tree_depth, level;
+ struct cds_ja_inode_flag *node_flag, *cur_node_depth[JA_MAX_DEPTH];
+ uint8_t cur_key[JA_MAX_DEPTH];
+ uint64_t _result_key = 0;
+ enum ja_direction dir;
+
+ switch (mode) {
+ case JA_LOOKUP_BE:
+ if (caa_unlikely(key > ja->key_max || key == 0))
+ return NULL;
+ break;
+ case JA_LOOKUP_AE:
+ if (caa_unlikely(key >= ja->key_max))
+ return NULL;
+ break;
+ default:
+ return NULL;
+ }
+
+ memset(cur_node_depth, 0, sizeof(cur_node_depth));
+ memset(cur_key, 0, sizeof(cur_key));
+ tree_depth = ja->tree_depth;
+ node_flag = rcu_dereference(ja->root);
+ cur_node_depth[0] = node_flag;
+
+ /* level 0: root node */
+ if (!ja_node_ptr(node_flag))
+ return NULL;
+
+ for (level = 1; level < tree_depth; level++) {
+ uint8_t iter_key;
+
+ iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - level - 1)));
+ node_flag = ja_node_get_nth(node_flag, NULL, iter_key);
+ if (!ja_node_ptr(node_flag))
+ break;
+ cur_key[level - 1] = iter_key;
+ cur_node_depth[level] = node_flag;
+ dbg_printf("cds_ja_lookup_inequality iter key lookup %u finds node_flag %p\n",
+ (unsigned int) iter_key, node_flag);
+ }
+
+ if (level == tree_depth) {
+ /* Last level lookup succeded. We got an equal match. */
+ if (result_key)
+ *result_key = key;
+ return (struct cds_ja_node *) node_flag;
+ }
+
+ /*
+ * Find highest value left/right of current node.
+ * Current node is cur_node_depth[level].
+ * Start at current level. If we cannot find any key left/right
+ * of ours, go one level up, seek highest value left/right of
+ * current (recursively), and when we find one, get the
+ * rightmost/leftmost child of its rightmost/leftmost child
+ * (recursively).
+ */
+ switch (mode) {
+ case JA_LOOKUP_BE:
+ dir = JA_LEFT;
+ break;
+ case JA_LOOKUP_AE:
+ dir = JA_RIGHT;
+ break;
+ default:
+ assert(0);
+ }
+ for (; level > 0; level--) {
+ uint8_t iter_key;
+
+ iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - level - 1)));
+ node_flag = ja_node_get_leftright(cur_node_depth[level - 1],
+ iter_key, &cur_key[level - 1], dir);
+ dbg_printf("cds_ja_lookup_inequality find sibling from %u at %u finds node_flag %p\n",
+ (unsigned int) iter_key, (unsigned int) cur_key[level - 1],
+ node_flag);
+ /* If found left/right sibling, find rightmost/leftmost child. */
+ if (ja_node_ptr(node_flag))
+ break;
+ }
+
+ if (!level) {
+ /* Reached the root and could not find a left/right sibling. */
+ return NULL;
+ }
+
+ level++;
+
+ /*
+ * From this point, we are guaranteed to be able to find a
+ * "below than"/"above than" match. ja_attach_node() and
+ * ja_detach_node() both guarantee that it is not possible for a
+ * lookup to reach a dead-end.
+ */
+
+ /*
+ * Find rightmost/leftmost child of rightmost/leftmost child
+ * (recursively).
+ */
+ switch (mode) {
+ case JA_LOOKUP_BE:
+ dir = JA_RIGHTMOST;
+ break;
+ case JA_LOOKUP_AE:
+ dir = JA_LEFTMOST;
+ break;
+ default:
+ assert(0);
+ }
+ for (; level < tree_depth; level++) {
+ node_flag = ja_node_get_minmax(node_flag, &cur_key[level - 1], dir);
+ dbg_printf("cds_ja_lookup_inequality find minmax at %u finds node_flag %p\n",
+ (unsigned int) cur_key[level - 1],
+ node_flag);
+ if (!ja_node_ptr(node_flag))
+ break;
+ }
+
+ assert(level == tree_depth);
+
+ if (result_key) {
+ for (level = 1; level < tree_depth; level++) {
+ _result_key |= ((uint64_t) cur_key[level - 1])
+ << (JA_BITS_PER_BYTE * (tree_depth - level - 1));
+ }
+ *result_key = _result_key;
+ }
+ return (struct cds_ja_node *) node_flag;
+}
+
+struct cds_ja_node *cds_ja_lookup_below_equal(struct cds_ja *ja,
+ uint64_t key, uint64_t *result_key)
+{
+ dbg_printf("cds_ja_lookup_below_equal key %" PRIu64 "\n", key);
+ return cds_ja_lookup_inequality(ja, key, result_key, JA_LOOKUP_BE);
+}
+
+struct cds_ja_node *cds_ja_lookup_above_equal(struct cds_ja *ja,
+ uint64_t key, uint64_t *result_key)
+{
+ dbg_printf("cds_ja_lookup_above_equal key %" PRIu64 "\n", key);
+ return cds_ja_lookup_inequality(ja, key, result_key, JA_LOOKUP_AE);