+struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key)
+{
+ int tree_depth, level;
+ struct cds_ja_inode_flag *node_flag, *cur_node_depth[JA_MAX_DEPTH];
+ struct cds_hlist_head head = { NULL };
+
+ if (caa_unlikely(key > ja->key_max || !key))
+ return head;
+
+ memset(cur_node_depth, 0, sizeof(cur_node_depth));
+ 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 head;
+
+ 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_node_depth[level] = node_flag;
+ dbg_printf("cds_ja_lookup 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. */
+ head.next = (struct cds_hlist_node *) node_flag;
+ return head;
+ }
+
+ /*
+ * Find highest value left of current node.
+ * Current node is cur_node_depth[level].
+ * Start at current level. If we cannot find any key left of
+ * ours, go one level up, seek highest value left of current
+ * (recursively), and when we find one, get the rightmost child
+ * of its rightmost child (recursively).
+ */
+ 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_left(cur_node_depth[level - 1],
+ iter_key);
+ /* If found left sibling, find rightmost child. */
+ if (ja_node_ptr(node_flag))
+ break;
+ }
+
+ if (!level) {
+ /* Reached the root and could not find a left sibling. */
+ return head;
+ }
+
+ level++;
+ /* Find rightmost child of rightmost child (recursively). */
+ for (; level < tree_depth; level++) {
+ node_flag = ja_node_get_rightmost(node_flag);
+ /* If found left sibling, find rightmost child. */
+ if (!ja_node_ptr(node_flag))
+ 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;
+ }
+
+ /* No match */
+ return head;
+}
+