+
+/*
+ * ja_node_recompact_add: recompact a node, adding a new child.
+ * TODO: for pool type, take selection bit(s) into account.
+ */
+static
+int ja_node_recompact_add(struct rcu_ja *ja,
+ unsigned int old_type_index,
+ const struct rcu_ja_type *old_type,
+ struct rcu_ja_node *old_node,
+ struct rcu_ja_shadow_node **shadow_node,
+ struct rcu_ja_node_flag **old_node_flag, uint8_t n,
+ struct rcu_ja_node_flag *child_node_flag)
+{
+ unsigned int new_type_index;
+ struct rcu_ja_node *new_node;
+ const struct rcu_ja_type *new_type;
+ struct rcu_ja_node_flag *new_node_flag;
+ int ret;
+
+ if (*shadow_node == NULL) {
+ new_type_index = 0;
+ } else {
+ new_type_index = old_type_index + 1;
+ }
+ new_type = &ja_types[new_type_index];
+ new_node = alloc_rcu_ja_node(new_type);
+ if (!new_node)
+ return -ENOMEM;
+ new_node_flag = ja_node_flag(new_node, new_type_index);
+
+ ret = rcuja_shadow_set(ja->ht, new_node, *shadow_node);
+ if (ret)
+ return ret;
+
+ if (*shadow_node == NULL) {
+ *shadow_node = rcuja_shadow_lookup_lock(ja->ht, new_node);
+ assert(*shadow_node);
+ }
+
+ /*
+ * We need to clear nr_child, because it will be re-incremented
+ * by _ja_node_set_nth().
+ */
+ (*shadow_node)->nr_child = 0;
+
+ assert(old_type->type_class != RCU_JA_PIGEON);
+ switch (old_type->type_class) {
+ case RCU_JA_LINEAR:
+ {
+ uint8_t nr_child =
+ ja_linear_node_get_nr_child(old_type, old_node);
+ unsigned int i;
+
+ for (i = 0; i < nr_child; i++) {
+ struct rcu_ja_node_flag *iter;
+ uint8_t v;
+
+ ja_linear_node_get_ith_pos(old_type, old_node, i, &v, &iter);
+ if (!iter)
+ continue;
+ ret = _ja_node_set_nth(new_type, new_node, *shadow_node,
+ v, iter);
+ assert(!ret);
+ }
+ break;
+ }
+ case RCU_JA_POOL:
+ {
+ unsigned int pool_nr;
+
+ for (pool_nr = 0; pool_nr < (1U << old_type->nr_pool_order); pool_nr++) {
+ struct rcu_ja_node *pool =
+ ja_pool_node_get_ith_pool(old_type,
+ old_node, pool_nr);
+ uint8_t nr_child =
+ ja_linear_node_get_nr_child(old_type, pool);
+ unsigned int j;
+
+ for (j = 0; j < nr_child; j++) {
+ struct rcu_ja_node_flag *iter;
+ uint8_t v;
+
+ ja_linear_node_get_ith_pos(old_type, pool,
+ j, &v, &iter);
+ if (!iter)
+ continue;
+ ret = _ja_node_set_nth(new_type, new_node, *shadow_node,
+ v, iter);
+ assert(!ret);
+ }
+ }
+ break;
+ }
+ case RCU_JA_PIGEON:
+ default:
+ assert(0);
+ return -EINVAL;
+ }
+
+ /* add node */
+ ret = _ja_node_set_nth(new_type, new_node, *shadow_node,
+ n, child_node_flag);
+ assert(!ret);
+ /* Replace the old node with the new recompacted one */
+ rcu_assign_pointer(*old_node_flag, new_node_flag);
+ ret = rcuja_shadow_clear(ja->ht, old_node,
+ RCUJA_SHADOW_CLEAR_FREE_NODE);
+ assert(!ret);
+ return 0;
+}
+
+static
+int ja_node_set_nth(struct rcu_ja *ja,
+ struct rcu_ja_node_flag **node_flag, uint8_t n,
+ struct rcu_ja_node_flag *child_node_flag)
+{
+ int ret;
+ unsigned int type_index;
+ const struct rcu_ja_type *type;
+ struct rcu_ja_node *node;
+ struct rcu_ja_shadow_node *shadow_node = NULL;
+
+ node = ja_node_ptr(*node_flag);
+ type_index = ja_node_type(*node_flag);
+ type = &ja_types[type_index];
+ if (node != NULL) {
+ shadow_node = rcuja_shadow_lookup_lock(ja->ht, node);
+ assert(shadow_node);
+ }
+ ret = _ja_node_set_nth(type, node, shadow_node,
+ n, child_node_flag);
+ if (ret == -ENOSPC) {
+ /* Not enough space in node, need to recompact. */
+ ret = ja_node_recompact_add(ja, type_index, type, node,
+ &shadow_node, node_flag, n, child_node_flag);
+ /* recompact always leave shadow_node locked */
+ }
+ rcuja_shadow_unlock(shadow_node);
+ return ret;
+}