+ assert(mode == JA_RECOMPACT_DEL);
+ for (i = 0; i < JA_ENTRY_PER_NODE; i++) {
+ struct cds_ja_inode_flag *iter;
+
+ iter = ja_pigeon_node_get_ith_pos(type, node, i);
+ if (!iter)
+ continue;
+ if (mode == JA_RECOMPACT_DEL && *nullify_node_flag_ptr == iter)
+ continue;
+ for (bit_i = 0; bit_i < JA_BITS_PER_BYTE; bit_i++) {
+ for (bit_j = 0; bit_j < bit_i; bit_j++) {
+ if (i & (1U << bit_i)) {
+ if (i & (1U << bit_j)) {
+ nr_2d_11[bit_i][bit_j]++;
+ } else {
+ nr_2d_10[bit_i][bit_j]++;
+ }
+ } else {
+ if (i & (1U << bit_j)) {
+ nr_2d_01[bit_i][bit_j]++;
+ } else {
+ nr_2d_00[bit_i][bit_j]++;
+ }
+ }
+ }
+ }
+ distrib_nr_child++;
+ }
+ break;
+ }
+ case RCU_JA_NULL:
+ assert(mode == JA_RECOMPACT_ADD_NEXT);
+ break;
+ default:
+ assert(0);
+ break;
+ }
+
+ if (mode == JA_RECOMPACT_ADD_NEXT || mode == JA_RECOMPACT_ADD_SAME) {
+ for (bit_i = 0; bit_i < JA_BITS_PER_BYTE; bit_i++) {
+ for (bit_j = 0; bit_j < bit_i; bit_j++) {
+ if (n & (1U << bit_i)) {
+ if (n & (1U << bit_j)) {
+ nr_2d_11[bit_i][bit_j]++;
+ } else {
+ nr_2d_10[bit_i][bit_j]++;
+ }
+ } else {
+ if (n & (1U << bit_j)) {
+ nr_2d_01[bit_i][bit_j]++;
+ } else {
+ nr_2d_00[bit_i][bit_j]++;
+ }
+ }
+ }
+ }
+ distrib_nr_child++;
+ }
+
+ /*
+ * The best bit selector is that for which the number of nodes
+ * in each sub-class is closest to one-fourth of the number of
+ * children in the distribution. We calculate the distance using
+ * 4 times the size of the sub-distribution to eliminate
+ * truncation error.
+ */
+ for (bit_i = 0; bit_i < JA_BITS_PER_BYTE; bit_i++) {
+ for (bit_j = 0; bit_j < bit_i; bit_j++) {
+ int distance_to_best[4];
+
+ distance_to_best[0] = ((unsigned int) nr_2d_11[bit_i][bit_j] << 2U) - distrib_nr_child;
+ distance_to_best[1] = ((unsigned int) nr_2d_10[bit_i][bit_j] << 2U) - distrib_nr_child;
+ distance_to_best[2] = ((unsigned int) nr_2d_01[bit_i][bit_j] << 2U) - distrib_nr_child;
+ distance_to_best[3] = ((unsigned int) nr_2d_00[bit_i][bit_j] << 2U) - distrib_nr_child;
+
+ /* Consider worse distance above best */
+ if (distance_to_best[1] > 0 && distance_to_best[1] > distance_to_best[0])
+ distance_to_best[0] = distance_to_best[1];
+ if (distance_to_best[2] > 0 && distance_to_best[2] > distance_to_best[0])
+ distance_to_best[0] = distance_to_best[2];
+ if (distance_to_best[3] > 0 && distance_to_best[3] > distance_to_best[0])
+ distance_to_best[0] = distance_to_best[3];
+
+ /*
+ * If our worse distance is better than overall,
+ * we become new best candidate.
+ */
+ if (distance_to_best[0] < overall_best_distance) {
+ overall_best_distance = distance_to_best[0];
+ bitsel[0] = bit_i;
+ bitsel[1] = bit_j;
+ }
+ }
+ }
+
+ dbg_printf("2 dimensions pool bit selection: (%u,%u)\n", bitsel[0], bitsel[1]);
+
+ /* Return our bit selection */
+ _bitsel[0] = bitsel[0];
+ _bitsel[1] = bitsel[1];
+}
+
+static
+unsigned int find_nearest_type_index(unsigned int type_index,
+ unsigned int nr_nodes)
+{
+ const struct cds_ja_type *type;
+
+ assert(type_index != NODE_INDEX_NULL);
+ if (nr_nodes == 0)
+ return NODE_INDEX_NULL;
+ for (;;) {
+ type = &ja_types[type_index];
+ if (nr_nodes < type->min_child)
+ type_index--;
+ else if (nr_nodes > type->max_child)
+ type_index++;
+ else
+ break;
+ }
+ return type_index;
+}
+
+/*
+ * ja_node_recompact_add: recompact a node, adding a new child.
+ * Return 0 on success, -EAGAIN if need to retry, or other negative
+ * error value otherwise.
+ */
+static
+int ja_node_recompact(enum ja_recompact mode,
+ struct cds_ja *ja,
+ unsigned int old_type_index,
+ const struct cds_ja_type *old_type,
+ struct cds_ja_inode *old_node,
+ struct cds_ja_shadow_node *shadow_node,
+ struct cds_ja_inode_flag **old_node_flag_ptr, uint8_t n,
+ struct cds_ja_inode_flag *child_node_flag,
+ struct cds_ja_inode_flag **nullify_node_flag_ptr,
+ int level)
+{
+ unsigned int new_type_index;
+ struct cds_ja_inode *new_node;
+ struct cds_ja_shadow_node *new_shadow_node = NULL;
+ const struct cds_ja_type *new_type;
+ struct cds_ja_inode_flag *new_node_flag, *old_node_flag;
+ int ret;
+ int fallback = 0;
+
+ old_node_flag = *old_node_flag_ptr;
+
+ /*
+ * Need to find nearest type index even for ADD_SAME, because
+ * this recompaction, when applied to linear nodes, will garbage
+ * collect dummy (NULL) entries, and can therefore cause a few
+ * linear representations to be skipped.
+ */
+ switch (mode) {
+ case JA_RECOMPACT_ADD_SAME:
+ new_type_index = find_nearest_type_index(old_type_index,
+ shadow_node->nr_child + 1);
+ dbg_printf("Recompact for node with %u children\n",
+ shadow_node->nr_child + 1);
+ break;
+ case JA_RECOMPACT_ADD_NEXT:
+ if (!shadow_node || old_type_index == NODE_INDEX_NULL) {
+ new_type_index = 0;
+ dbg_printf("Recompact for NULL\n");
+ } else {
+ new_type_index = find_nearest_type_index(old_type_index,
+ shadow_node->nr_child + 1);
+ dbg_printf("Recompact for node with %u children\n",
+ shadow_node->nr_child + 1);
+ }
+ break;
+ case JA_RECOMPACT_DEL:
+ new_type_index = find_nearest_type_index(old_type_index,
+ shadow_node->nr_child - 1);
+ dbg_printf("Recompact for node with %u children\n",
+ shadow_node->nr_child - 1);
+ break;
+ default:
+ assert(0);
+ }
+
+retry: /* for fallback */
+ dbg_printf("Recompact from type %d to type %d\n",
+ old_type_index, new_type_index);
+ new_type = &ja_types[new_type_index];
+ if (new_type_index != NODE_INDEX_NULL) {
+ new_node = alloc_cds_ja_node(ja, new_type);