From 18095edd87128a2b7bd716bfb68cff4b1c79e735 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 7 Apr 2025 22:02:54 -0400 Subject: [PATCH] Revert "remove dead code" This reverts commit b3062ee59ae87e44f81fd309b79c8fbf5660f2db. --- lib/maple_tree.c | 299 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 299 insertions(+) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index e7df50bc0703..65fbb23faac4 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3567,6 +3567,143 @@ void mas_wr_ascend_init(struct ma_state *mas, struct ma_node_info *ni) ni->insert_off = mas->offset; } +#if 0 +static void mas_wr_rebalance_nodes( + struct ma_node_info *l_src, + struct ma_node_info *r_src, + struct ma_node_info *left, + struct ma_node_info *right, + bool left_store, + unsigned char split, + struct ma_node_part *ma_part, + unsigned char mas_off, + unsigned char new_end + ) +{ + unsigned char l_end, r_end; + + /* + * l_src, ma_part, and r_src will be split between the new left and + * right nodes. Depending on where the split and the store offset + * (mas_off) falls within the data will determine where the new data + * will end up in the new nodes (left and right). + * + * This is further complicated by the insert potentially spanning the + * nodes and the left node ending on a NULL. If left does end in null, + * then the data is shifted forward one (if possible), or back one. + * Shifting back means copying the data to the right node. Shifting + * forward is complicated by a potential insert splitting the nodes, + * which means the new data going to the left will have to come from the + * ma_part. This is all taken care of in mas_wr_split_no_null(). + */ + + l_end = l_src->end; + r_end = r_src->end; + if (left_store) { /* Store is targeting l_src */ + printk("%s %d\n", __func__, __LINE__); + if (mas_off <= split) { /* Store will end up in left */ + printk("%s %d\n", __func__, __LINE__); + if (mas_off) + mni_cp(l_src, left, mas_off); + + ma_part->dst_max_off = split; + mni_insert_part(ma_part, left); + l_src->offset+= ma_part->skip; + printk("%d\n", __LINE__); + + printk("\tright min %lu left max %lu\n", right->min, left->max); + if (left->offset <= split) + mni_cp(l_src, left, split - left->offset + 1); + + printk("\tright min %lu left max %lu\n", right->min, left->max); + mas_wr_split_no_null(l_src, left, right, + r_end + new_end + 1, ma_part); + right->min = left->max + 1; + printk("\tright min %lu left max %lu\n", right->min, left->max); + if (ma_part->unfinished) + mni_insert_part(ma_part, right); + + if (l_end >= l_src->offset) + mni_cp(l_src, right, l_end - l_src->offset + 1); + + } else { /* Store will end up in right */ + printk("%s %d\n", __func__, __LINE__); + mni_cp(l_src, left, split + 1); + mas_wr_split_no_null(l_src, left, right, + r_end + new_end + 1, ma_part); + right->min = left->max + 1; + mni_cp(l_src, right, mas_off - l_src->offset); + mni_insert_part(ma_part, right); + //printk("%d\n", __LINE__); + l_src->offset+= ma_part->skip; + if (l_end >= l_src->offset) + mni_cp(l_src, right, l_end - l_src->offset + 1); + } + + mni_cp(r_src, right, r_end + 1); + } else { /* Store is targeting r_src */ + printk("%s %d\n", __func__, __LINE__); + if (split <= l_end) { /* Store will end up in right */ + printk("%s %d\n", __func__, __LINE__); + mni_cp(l_src, left, split + 1); + mas_wr_split_no_null(l_src, left, right, + l_end + new_end + 1, ma_part); + + mni_cp(l_src, right, l_end - l_src->offset + 1); + right->min = left->max + 1; + mni_cp(r_src, right, mas_off); + mni_insert_part(ma_part, right); + //printk("%d\n", __LINE__); + r_src->offset+= ma_part->skip; + if (r_src->offset <= r_end) + mni_cp(r_src, right, r_end - r_src->offset + 1); + + } else { /* Store will end up in left */ + unsigned char r_split; + + printk("%s %d\n", __func__, __LINE__); + r_split = split - l_end - 1; + mni_cp(l_src, left, l_end + 1); + if (mas_off <= r_split) { + if (mas_off) + mni_cp(r_src, left, mas_off); + ma_part->dst_max_off = split; + mni_insert_part(ma_part, left); + //printk("%d\n", __LINE__); + r_src->offset+= ma_part->skip; + if (r_src->offset < r_split) + mni_cp(r_src, left, + r_split - r_src->offset); + + mas_wr_split_no_null(r_src, left, right, + l_end + new_end + 1, + ma_part); + + if (ma_part->unfinished) + mni_insert_part(ma_part, right); + + right->min = left->max + 1; + } else { + mni_cp(r_src, left, r_split + 1); + mas_wr_split_no_null(r_src, left, right, + l_end + new_end + 1, + ma_part); + right->min = left->max + 1; + if (mas_off > r_src->offset) + mni_cp(r_src, right, + mas_off - r_src->offset); + mni_insert_part(ma_part, right); + //printk("%d\n", __LINE__); + r_src->offset+= ma_part->skip; + } + + if (r_src->offset <= r_end) + mni_cp(r_src, right, r_end - r_src->offset + 1); + } + } +} +#endif + /* * Assemble all the states into the dst within those states * @@ -3881,6 +4018,168 @@ try_right: return true; } +#if 0 +/* + * There is insufficient data in the node after a store. + * This rebalance will succeed, not like the split variant that will attempt + * to rebalance. + * + * Rebalance leaves + * Continue upwards until parent is sufficient, or root is reached. If root + * has a single child, replace root with new root. + */ +static void mas_wr_rebalance(struct ma_wr_state *wr_mas) +{ + struct ma_state *mas = wr_mas->mas; + struct ma_node_state src, parent, l_src, r_src; + struct ma_node_info src_info; + struct ma_node_state left, right; + struct ma_node_part ma_part; + unsigned char total, split, height; + unsigned char insert; + + trace_ma_op(__func__, mas); + mt_dump(mas->tree, mt_dump_dec); + height = mas_mt_height(mas); + mns_mas_init(&src, &src_info, mas); + mns_node_part_leaf_init(&ma_part, wr_mas, &src); + /* Total will lack sibling data until the sibling is known */ + printk("end %p %u\n", mas->node, mas->end); + total = mas->end + ma_part.size - ma_part.skip - 1; + printk("%p will have %u in the end\n", mas->node, total); + printk("Skip %u\n", ma_part.skip); + // Skipping is causing a copy beyond the end of the src. + + printk("Rebalance %p %lu-%lu", mas->node, mas->index, mas->last); + + insert = mas->offset; + printk("Write to node at %u\n", insert); + while (mas->depth) { + bool l_store; + + mas_wr_ascend_init(mas, &parent); + printk("Ascend to parent %p\n", parent.node); + printk("offset of child is %u\n", mas->offset); + mas->depth--; + parent.insert = mas->offset; + printk("parent insert is %u\n", parent.insert); + + if (parent.insert < parent.end) { + /* Pull data from r_src */ + printk("Pull from right\n"); + mns_pmns_init(&r_src, &parent, mas->offset + 1, mas->tree); + mns_set_end(&r_src); + printk("right is %p %lu-%lu\n", r_src.node, r_src.min, r_src.max); + l_src = src; + l_src.insert = insert; + total += r_src.end; + l_store = true; + } else { + /* Pull data from l_src */ + printk("Pull from left\n"); + mns_pmns_init(&l_src, &parent, mas->offset - 1, mas->tree); + printk("left is %p\n", l_src.node); + r_src = src; + r_src.insert = insert; + mns_set_end(&l_src); + total += l_src.end; + l_store = false; + parent.insert--; + } + + printk("\tNew total will be %u\n", total); + mni_node_init(&left, mas_pop_node(mas), l_src.type); + /* + * Two possibilities: + * 1. keep two nodes if possible and limit ripple + * 2. make one node if possible and limit memory use + * + * Case 1: + * Left takes data from right. + * Fill left up to split from l_src and ma_part - Func_1 + * Fill left up from l_src remainder - Func_2 + * Fill left up to split from right. - Func_2 + * fill right with remainder of right. - Func_2 + * + * Right takes data from left + * Copy left to new left up to split - Func_2 + * Fill right with remainder of left - Func_2 + * Fill right from old right or ma_part - Func_1 + */ + if ((total > 2 * mt_min_slots[l_src.type] ) || + ma_is_root(parent.node)) { + struct ma_node_state new_parent; + + printk("Rebalance\n"); + /* + * Rebalance between nodes is possible, so the + * operation stops early. + */ + + mni_node_init(&right, mas_pop_node(mas), r_src.type); + printk("new right will be %p\n", right.node); + split = mas_wr_rebalance_calc(total, l_src.type); + printk("split is %u\n", split); + left.min = l_src.min; + mas_wr_rebalance_nodes(&l_src, &r_src, &left, &right, + l_store, split, &ma_part, + insert, total); + + mni_finalise(&left); + mni_finalise(&right); + mni_node_part_init(&ma_part, &left, &right); + ma_part.skip = 2; + mas_wr_converged(&parent, &new_parent, &ma_part, mas); + src.enode = parent.enode; + mas->node = new_parent.enode; + mas->depth = height; + printk("Height is %u\n", mas->depth); + break; + } + + printk("consume\n"); + /* Reduce two nodes into one */ + if (l_store) { + if (l_src.insert) + mni_cp(&l_src, &left, l_src.insert); + mni_insert_part(&ma_part, &left); + l_src.offset += ma_part.skip; + if (l_src.offset <= l_src.end) + mni_cp(&l_src, &left, + l_src.end - l_src.offset + 1); + mni_cp(&r_src, &left, r_src.end); + + } else { + mni_cp(&l_src, &left, l_src.end); + if (r_src.insert) + mni_cp(&r_src, &left, r_src.insert); + mni_insert_part(&ma_part, &left); + r_src.offset += ma_part.skip; + if (r_src.offset <= r_src.end) + mni_cp(&r_src, &left, + r_src.end - r_src.offset + 1); + } + left.node->parent = l_src.node->parent; + mni_finalise(&left); + if (mte_is_root(parent.enode)) { + /* Height reduction */ + if (mas->depth) + mas->depth = --height; + else + mas->depth = height; + + mas_set_height(mas); + break; + } + } + + + mas_wmb_replace(mas, parent.enode); + mtree_range_walk(mas); + mt_dump(mas->tree, mt_dump_dec); +} +#endif + /* * There is not enough room to contain the store in one node. */ -- 2.49.0