+
+ /* Create new branch, starting from bottom */
+ CDS_INIT_HLIST_HEAD(&head);
+ cds_hlist_add_head_rcu(&child_node->list, &head);
+ iter_node_flag = (struct cds_ja_inode_flag *) head.next;
+
+ /* Create shadow node for the leaf node */
+ dbg_printf("leaf shadow node creation\n");
+ iter_shadow_node = rcuja_shadow_set(ja->ht,
+ ja_node_ptr(iter_node_flag), NULL);
+ if (!iter_shadow_node) {
+ ret = -ENOMEM;
+ goto check_error;
+ }
+ created_nodes[nr_created_nodes++] = iter_node_flag;
+
+ for (i = ja->tree_depth - 1; i >= (int) depth; i--) {
+ dbg_printf("branch creation level %d, key %" PRIu64 "\n",
+ i, key >> (JA_BITS_PER_BYTE * (i - 2)));
+ iter_dest_node_flag = NULL;
+ ret = ja_node_set_nth(ja, &iter_dest_node_flag,
+ key >> (JA_BITS_PER_BYTE * (i - 2)),
+ iter_node_flag,
+ NULL);
+ if (ret)
+ goto check_error;
+ created_nodes[nr_created_nodes++] = iter_dest_node_flag;
+ iter_node_flag = iter_dest_node_flag;
+ }
+
+ if (depth > 1) {
+ /* We need to use set_nth on the previous level. */
+ iter_dest_node_flag = node_flag;
+ ret = ja_node_set_nth(ja, &iter_dest_node_flag,
+ key >> (JA_BITS_PER_BYTE * (depth - 2)),
+ iter_node_flag,
+ shadow_node);
+ if (ret)
+ goto check_error;
+ created_nodes[nr_created_nodes++] = iter_dest_node_flag;
+ iter_node_flag = iter_dest_node_flag;
+ }
+
+ /* Publish new branch */
+ dbg_printf("Publish branch %p, replacing %p\n",
+ iter_node_flag, *node_flag_ptr);
+ rcu_assign_pointer(*node_flag_ptr, iter_node_flag);
+
+ /* Success */
+ ret = 0;
+
+check_error:
+ if (ret) {
+ for (i = 0; i < nr_created_nodes; i++) {
+ int tmpret;
+ int flags;
+
+ flags = RCUJA_SHADOW_CLEAR_FREE_LOCK;
+ if (i)
+ flags |= RCUJA_SHADOW_CLEAR_FREE_NODE;
+ tmpret = rcuja_shadow_clear(ja->ht,
+ ja_node_ptr(created_nodes[i]),
+ NULL,
+ flags);
+ assert(!tmpret);
+ }
+ }
+ if (parent_shadow_node)
+ rcuja_shadow_unlock(parent_shadow_node);
+unlock_shadow:
+ if (shadow_node)
+ rcuja_shadow_unlock(shadow_node);
+end:
+ return ret;
+}
+
+/*
+ * Lock the hlist head shadow node mutex, and add node to list of
+ * duplicates. Failure can happen if concurrent removal removes the last
+ * node with same key before we get the lock.
+ * Return 0 on success, negative error value on failure.
+ */
+static
+int ja_chain_node(struct cds_ja *ja,
+ struct cds_hlist_head *head,
+ struct cds_ja_node *node)
+{
+ struct cds_ja_shadow_node *shadow_node;
+
+ shadow_node = rcuja_shadow_lookup_lock(ja->ht,
+ (struct cds_ja_inode *) head);
+ if (!shadow_node)
+ return -ENOENT;
+ cds_hlist_add_head_rcu(&node->list, head);