Lines Matching refs:b_node
1801 * old data or set b_node->b_end.
1802 * @b_node: the maple_big_node
1805 static inline void mab_shift_right(struct maple_big_node *b_node,
1808 unsigned long size = b_node->b_end * sizeof(unsigned long);
1810 memmove(b_node->pivot + shift, b_node->pivot, size);
1811 memmove(b_node->slot + shift, b_node->slot, size);
1812 if (b_node->type == maple_arange_64)
1813 memmove(b_node->gap + shift, b_node->gap, size);
1818 * @b_node: the maple_big_node that contains the data.
1819 * @size: the amount of data in the b_node
1825 static inline bool mab_middle_node(struct maple_big_node *b_node, int split,
1828 unsigned char size = b_node->b_end;
1833 if (!b_node->slot[split] && (size >= 2 * slot_count - 1))
1841 * @b_node: the maple_big_node with the data
1847 static inline int mab_no_null_split(struct maple_big_node *b_node,
1850 if (!b_node->slot[split]) {
1856 (b_node->b_end - split) > (mt_min_slots[b_node->type]))
1935 * and set @b_node->b_end to the next free slot.
1939 * @b_node: The maple_big_node to place the data
1943 unsigned char mas_end, struct maple_big_node *b_node,
1957 b_node->pivot[j] = pivots[i++];
1965 b_node->pivot[j] = pivots[i];
1966 if (unlikely(!b_node->pivot[j]))
1969 if (unlikely(mas->max == b_node->pivot[j]))
1974 b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt);
1977 b_node->b_end = ++j;
1980 memcpy(b_node->slot + mab_start, slots + mas_start, sizeof(void *) * j);
1983 memcpy(b_node->gap + mab_start, gaps + mas_start,
2017 * @b_node: the maple_big_node that has the data
2018 * @mab_start: the start location in @b_node.
2019 * @mab_end: The end location in @b_node (inclusively)
2022 static inline void mab_mas_cp(struct maple_big_node *b_node,
2042 pivots[j++] = b_node->pivot[i++];
2043 } while (i <= mab_end && likely(b_node->pivot[i]));
2045 memcpy(slots, b_node->slot + mab_start,
2049 mas->max = b_node->pivot[i - 1];
2058 gaps[--j] = b_node->gap[--i];
2093 * mas_store_b_node() - Store an @entry into the b_node while also copying the
2096 * @b_node: the maple_big_node to fill with data
2099 * Return: The actual end of the data stored in @b_node
2102 struct maple_big_node *b_node, unsigned char offset_end)
2110 b_node->type = wr_mas->type;
2115 mas_mab_cp(mas, 0, slot - 1, b_node, 0);
2116 b_end = b_node->b_end;
2117 piv = b_node->pivot[b_end - 1];
2123 b_node->slot[b_end] = wr_mas->content;
2125 b_node->gap[b_end] = mas->index - 1 - piv;
2126 b_node->pivot[b_end++] = mas->index - 1;
2131 b_node->slot[b_end] = wr_mas->entry;
2132 b_node->pivot[b_end] = mas->last;
2142 mas_bulk_rebalance(mas, b_node->b_end, wr_mas->type);
2148 b_node->slot[++b_end] = wr_mas->content;
2150 b_node->gap[b_end] = piv - mas->last + 1;
2151 b_node->pivot[b_end] = piv;
2159 mas_mab_cp(mas, slot, wr_mas->node_end + 1, b_node, ++b_end);
2160 b_node->b_end--;
2164 b_node->b_end = b_end;
2375 * @b_node: the maple_big_node with the type encoding.
2383 *mas_new_ma_node(struct ma_state *mas, struct maple_big_node *b_node)
2385 return mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), b_node->type);
2392 * @b_node: the node which contains the data.
2401 struct maple_big_node *b_node, struct maple_enode **left,
2406 unsigned char slot_count = mt_slots[b_node->type];
2408 *left = mas_new_ma_node(mas, b_node);
2413 if (b_node->b_end < slot_count) {
2414 split = b_node->b_end;
2416 split = mab_calc_split(mas, b_node, mid_split, min);
2417 *right = mas_new_ma_node(mas, b_node);
2421 *middle = mas_new_ma_node(mas, b_node);
2428 * mab_set_b_end() - Add entry to b_node at b_node->b_end and increment the end
2430 * @b_node - the big node to add the entry
2434 static inline void mab_set_b_end(struct maple_big_node *b_node,
2441 b_node->slot[b_node->b_end] = entry;
2443 b_node->gap[b_node->b_end] = mas_max_gap(mas);
2444 b_node->pivot[b_node->b_end++] = mas->max;
2852 * is hit. First @b_node is split into two entries which are inserted into the
2853 * next iteration of the loop. @b_node is returned populated with the final
2861 * Return: the number of elements in b_node during the last loop.
2985 * @b_node: The big maple node.
2990 * Return: the number of elements in b_node during the last loop.
2993 struct maple_big_node *b_node)
2997 unsigned char shift, b_end = ++b_node->b_end;
3019 mast.bn = b_node;
3025 mas_mab_cp(&r_mas, 0, mt_slot_count(r_mas.node), b_node, b_end);
3030 mab_shift_right(b_node, shift);
3032 mas_mab_cp(&l_mas, 0, shift - 1, b_node, 0);
3033 b_node->b_end = shift + b_end;
3345 * @b_node: The maple big node
3348 static int mas_split(struct ma_state *mas, struct maple_big_node *b_node)
3388 mast.bn = b_node;
3391 if (mt_slots[b_node->type] > b_node->b_end) {
3397 l_mas.node = mas_new_ma_node(mas, b_node);
3398 r_mas.node = mas_new_ma_node(mas, b_node);
3414 split = mab_calc_split(mas, b_node, &mid_split, prev_l_mas.min);
3464 * @b_node: The maple big node
3468 struct maple_big_node *b_node, unsigned char end)
3472 unsigned char b_end = b_node->b_end;
3473 enum maple_type b_type = b_node->type;
3479 return mas_rebalance(wr_mas->mas, b_node);
3482 return mas_split(wr_mas->mas, b_node);
3484 if (mas_reuse_node(wr_mas, b_node, end))
3494 mab_mas_cp(b_node, 0, b_end, wr_mas->mas, false);
3825 struct maple_big_node b_node;
3892 memset(&b_node, 0, sizeof(struct maple_big_node));
3893 /* Copy l_mas and store the value in b_node. */
3894 mas_store_b_node(&l_wr_mas, &b_node, l_wr_mas.node_end);
3895 /* Copy r_mas into b_node. */
3898 &b_node, b_node.b_end + 1);
3900 b_node.b_end++;
3905 mast.bn = &b_node;
4193 struct maple_big_node b_node;
4196 memset(&b_node, 0, sizeof(struct maple_big_node));
4197 mas_store_b_node(wr_mas, &b_node, wr_mas->offset_end);
4198 mas_commit_b_node(wr_mas, &b_node, wr_mas->node_end);