+ }
+
+ switch (type->nr_pool_order) {
+ case 1:
+ {
+ unsigned long bitsel, index;
+
+ bitsel = ja_node_pool_1d_bitsel(node_flag);
+ assert(bitsel < CHAR_BIT);
+ index = ((unsigned long) n >> bitsel) & type->nr_pool_order;
+ linear = (struct cds_ja_inode *) &node->u.data[index << type->pool_size_order];
+ break;
+ }
+ case 2:
+ {
+ unsigned long bitsel[2], index[2], rindex;
+
+ ja_node_pool_2d_bitsel(node_flag, bitsel);
+ assert(bitsel[0] < CHAR_BIT);
+ assert(bitsel[1] < CHAR_BIT);
+ index[0] = ((unsigned long) n >> bitsel[0]) & 0x1;
+ index[0] <<= 1;
+ index[1] = ((unsigned long) n >> bitsel[1]) & 0x1;
+ rindex = index[0] | index[1];
+ linear = (struct cds_ja_inode *) &node->u.data[rindex << type->pool_size_order];
+ break;
+ }
+ default:
+ linear = NULL;
+ assert(0);
+ }
+
+ return ja_linear_node_clear_ptr(type, linear, shadow_node, node_flag_ptr);
+}
+
+static
+int ja_pigeon_node_clear_ptr(const struct cds_ja_type *type,
+ struct cds_ja_inode *node,
+ struct cds_ja_shadow_node *shadow_node,
+ struct cds_ja_inode_flag **node_flag_ptr)
+{
+ assert(type->type_class == RCU_JA_PIGEON);
+
+ if (shadow_node->fallback_removal_count) {
+ shadow_node->fallback_removal_count--;
+ } else {
+ /* We should try recompacting the node */
+ if (shadow_node->nr_child <= type->min_child)
+ return -EFBIG;
+ }
+ dbg_printf("ja_pigeon_node_clear_ptr: clearing ptr: %p\n", *node_flag_ptr);
+ rcu_assign_pointer(*node_flag_ptr, NULL);
+ shadow_node->nr_child--;
+ return 0;
+}
+
+/*
+ * _ja_node_clear_ptr: clear ptr item within a node. Return an error
+ * (negative error value) if it is not found (-ENOENT).
+ */
+static
+int _ja_node_clear_ptr(const struct cds_ja_type *type,
+ struct cds_ja_inode *node,
+ struct cds_ja_inode_flag *node_flag,
+ struct cds_ja_shadow_node *shadow_node,
+ struct cds_ja_inode_flag **node_flag_ptr,
+ uint8_t n)
+{
+ switch (type->type_class) {
+ case RCU_JA_LINEAR:
+ return ja_linear_node_clear_ptr(type, node, shadow_node, node_flag_ptr);
+ case RCU_JA_POOL:
+ return ja_pool_node_clear_ptr(type, node, node_flag, shadow_node, node_flag_ptr, n);
+ case RCU_JA_PIGEON:
+ return ja_pigeon_node_clear_ptr(type, node, shadow_node, node_flag_ptr);
+ case RCU_JA_NULL:
+ return -ENOENT;
+ default:
+ assert(0);
+ return -EINVAL;
+ }
+
+ return 0;
+}
+
+/*
+ * Calculate bit distribution. Returns the bit (0 to 7) that splits the
+ * distribution in two sub-distributions containing as much elements one
+ * compared to the other.
+ */
+static
+unsigned int ja_node_sum_distribution_1d(enum ja_recompact mode,
+ struct cds_ja *ja,
+ unsigned int type_index,
+ const struct cds_ja_type *type,
+ struct cds_ja_inode *node,
+ struct cds_ja_shadow_node *shadow_node,
+ uint8_t n,
+ struct cds_ja_inode_flag *child_node_flag,
+ struct cds_ja_inode_flag **nullify_node_flag_ptr)
+{
+ uint8_t nr_one[JA_BITS_PER_BYTE];
+ unsigned int bitsel = 0, bit_i, overall_best_distance = UINT_MAX;
+ unsigned int distrib_nr_child = 0;
+
+ memset(nr_one, 0, sizeof(nr_one));
+
+ switch (type->type_class) {
+ case RCU_JA_LINEAR:
+ {
+ uint8_t nr_child =
+ ja_linear_node_get_nr_child(type, node);
+ unsigned int i;
+
+ for (i = 0; i < nr_child; i++) {
+ struct cds_ja_inode_flag *iter;
+ uint8_t v;
+
+ ja_linear_node_get_ith_pos(type, node, i, &v, &iter);
+ 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++) {
+ if (v & (1U << bit_i))
+ nr_one[bit_i]++;
+ }
+ distrib_nr_child++;
+ }
+ break;
+ }
+ case RCU_JA_POOL:
+ {
+ unsigned int pool_nr;
+
+ for (pool_nr = 0; pool_nr < (1U << type->nr_pool_order); pool_nr++) {
+ struct cds_ja_inode *pool =
+ ja_pool_node_get_ith_pool(type,
+ node, pool_nr);
+ uint8_t nr_child =
+ ja_linear_node_get_nr_child(type, pool);
+ unsigned int j;
+
+ for (j = 0; j < nr_child; j++) {
+ struct cds_ja_inode_flag *iter;
+ uint8_t v;
+
+ ja_linear_node_get_ith_pos(type, pool,
+ j, &v, &iter);
+ 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++) {
+ if (v & (1U << bit_i))
+ nr_one[bit_i]++;
+ }
+ distrib_nr_child++;
+ }
+ }
+ break;
+ }
+ case RCU_JA_PIGEON:
+ {
+ unsigned int i;
+
+ 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++) {
+ if (i & (1U << bit_i))
+ nr_one[bit_i]++;
+ }
+ 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++) {
+ if (n & (1U << bit_i))
+ nr_one[bit_i]++;
+ }
+ distrib_nr_child++;
+ }
+
+ /*
+ * The best bit selector is that for which the number of ones is
+ * closest to half of the number of children in the
+ * distribution. We calculate the distance using the double of
+ * the sub-distribution sizes to eliminate truncation error.
+ */
+ for (bit_i = 0; bit_i < JA_BITS_PER_BYTE; bit_i++) {
+ unsigned int distance_to_best;
+
+ distance_to_best = abs_int((nr_one[bit_i] << 1U) - distrib_nr_child);
+ if (distance_to_best < overall_best_distance) {
+ overall_best_distance = distance_to_best;
+ bitsel = bit_i;
+ }
+ }
+ dbg_printf("1 dimension pool bit selection: (%u)\n", bitsel);
+ return bitsel;
+}
+
+/*
+ * Calculate bit distribution in two dimensions. Returns the two bits
+ * (each 0 to 7) that splits the distribution in four sub-distributions
+ * containing as much elements one compared to the other.
+ */
+static
+void ja_node_sum_distribution_2d(enum ja_recompact mode,
+ struct cds_ja *ja,
+ unsigned int type_index,
+ const struct cds_ja_type *type,
+ struct cds_ja_inode *node,
+ struct cds_ja_shadow_node *shadow_node,
+ uint8_t n,
+ struct cds_ja_inode_flag *child_node_flag,
+ struct cds_ja_inode_flag **nullify_node_flag_ptr,
+ unsigned int *_bitsel)
+{
+ uint8_t nr_2d_11[JA_BITS_PER_BYTE][JA_BITS_PER_BYTE],
+ nr_2d_10[JA_BITS_PER_BYTE][JA_BITS_PER_BYTE],
+ nr_2d_01[JA_BITS_PER_BYTE][JA_BITS_PER_BYTE],
+ nr_2d_00[JA_BITS_PER_BYTE][JA_BITS_PER_BYTE];
+ unsigned int bitsel[2] = { 0, 1 };
+ unsigned int bit_i, bit_j;
+ int overall_best_distance = INT_MAX;
+ unsigned int distrib_nr_child = 0;
+
+ memset(nr_2d_11, 0, sizeof(nr_2d_11));
+ memset(nr_2d_10, 0, sizeof(nr_2d_10));
+ memset(nr_2d_01, 0, sizeof(nr_2d_01));
+ memset(nr_2d_00, 0, sizeof(nr_2d_00));
+
+ switch (type->type_class) {
+ case RCU_JA_LINEAR:
+ {
+ uint8_t nr_child =
+ ja_linear_node_get_nr_child(type, node);
+ unsigned int i;
+
+ for (i = 0; i < nr_child; i++) {
+ struct cds_ja_inode_flag *iter;
+ uint8_t v;
+
+ ja_linear_node_get_ith_pos(type, node, i, &v, &iter);
+ 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 ((v & (1U << bit_i)) && (v & (1U << bit_j))) {
+ nr_2d_11[bit_i][bit_j]++;
+ }
+ if ((v & (1U << bit_i)) && !(v & (1U << bit_j))) {
+ nr_2d_10[bit_i][bit_j]++;
+ }
+ if (!(v & (1U << bit_i)) && (v & (1U << bit_j))) {
+ nr_2d_01[bit_i][bit_j]++;
+ }
+ if (!(v & (1U << bit_i)) && !(v & (1U << bit_j))) {
+ nr_2d_00[bit_i][bit_j]++;
+ }
+ }
+ }
+ distrib_nr_child++;
+ }
+ break;
+ }
+ case RCU_JA_POOL:
+ {
+ unsigned int pool_nr;
+
+ for (pool_nr = 0; pool_nr < (1U << type->nr_pool_order); pool_nr++) {
+ struct cds_ja_inode *pool =
+ ja_pool_node_get_ith_pool(type,
+ node, pool_nr);
+ uint8_t nr_child =
+ ja_linear_node_get_nr_child(type, pool);
+ unsigned int j;
+
+ for (j = 0; j < nr_child; j++) {
+ struct cds_ja_inode_flag *iter;
+ uint8_t v;
+
+ ja_linear_node_get_ith_pos(type, pool,
+ j, &v, &iter);
+ 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 ((v & (1U << bit_i)) && (v & (1U << bit_j))) {
+ nr_2d_11[bit_i][bit_j]++;
+ }
+ if ((v & (1U << bit_i)) && !(v & (1U << bit_j))) {
+ nr_2d_10[bit_i][bit_j]++;
+ }
+ if (!(v & (1U << bit_i)) && (v & (1U << bit_j))) {
+ nr_2d_01[bit_i][bit_j]++;
+ }
+ if (!(v & (1U << bit_i)) && !(v & (1U << bit_j))) {
+ nr_2d_00[bit_i][bit_j]++;
+ }
+ }
+ }
+ distrib_nr_child++;
+ }
+ }
+ break;
+ }
+ case RCU_JA_PIGEON:
+ {
+ unsigned int i;
+
+ 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)) && (i & (1U << bit_j))) {
+ nr_2d_11[bit_i][bit_j]++;
+ }
+ if ((i & (1U << bit_i)) && !(i & (1U << bit_j))) {
+ nr_2d_10[bit_i][bit_j]++;
+ }
+ if (!(i & (1U << bit_i)) && (i & (1U << bit_j))) {
+ nr_2d_01[bit_i][bit_j]++;
+ }
+ if (!(i & (1U << bit_i)) && !(i & (1U << bit_j))) {
+ 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)) && (n & (1U << bit_j))) {
+ nr_2d_11[bit_i][bit_j]++;
+ }
+ if ((n & (1U << bit_i)) && !(n & (1U << bit_j))) {
+ nr_2d_10[bit_i][bit_j]++;
+ }
+ if (!(n & (1U << bit_i)) && (n & (1U << bit_j))) {
+ nr_2d_01[bit_i][bit_j]++;
+ }
+ if (!(n & (1U << bit_i)) && !(n & (1U << bit_j))) {
+ nr_2d_00[bit_i][bit_j]++;
+ }
+ }