From 5f66ed8f39c331cbaf4c12642286aa419345e89d Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Wed, 24 Jun 2020 10:13:14 -0400 Subject: [PATCH] wip: pass 747201. Rework some gap stuff. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 115 +++++++++++++++++------------------------------ 1 file changed, 42 insertions(+), 73 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ea43f5591951..53a3b740bab0 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1219,6 +1219,13 @@ static inline unsigned long mas_max_gap(struct ma_state *mas, return max_gap; } +static inline unsigned long mas_find_gap(struct ma_state *mas) +{ + unsigned char slot = 0; + if (mte_is_leaf(mas->node)) + return mas_leaf_max_gap(mas); + return mas_max_gap(mas, &slot); +} static inline void mas_parent_gap(struct ma_state *mas, unsigned char slot, unsigned long new, bool force) { @@ -1457,25 +1464,6 @@ static inline void mas_replace(struct ma_state *mas) _mas_replace(mas, true, false, true); } -static inline void mas_gap_link(struct ma_state *mas, struct maple_enode *parent, - unsigned char slot, unsigned long pivot) -{ - unsigned long gap, max; - unsigned char max_slot; - - max = mas->max; - if (slot) - mas->min = mte_get_pivot(parent, slot - 1) + 1; - - mas->max = pivot; - if (!mte_is_leaf(mas->node)) - gap = mas_max_gap(mas, &max_slot); - else - gap = mas_leaf_max_gap(mas); - - mte_set_gap(parent, slot, gap); - mas->max = max; -} static inline enum maple_type mas_ptype_leaf(struct ma_state *mas) { enum maple_type pt = mte_node_type(mas->node); @@ -1621,7 +1609,7 @@ static inline int mab_mas_cp(struct maple_big_node *b_node, struct ma_state *mas, unsigned char mas_start) { int i, j; - printk("%s: cp %u - %u to mas\n", __func__, mab_start, mab_end - 1); + printk("%s: cp %u - %u to mas %p\n", __func__, mab_start, mab_end - 1, mas_mn(mas)); for (i = mab_start, j = mas_start; i < mab_end; i++, j++) { //printk("i %d end %u\n", i, mab_end); if(j && !b_node->pivot[i]) { @@ -1650,7 +1638,7 @@ static inline int mas_commit_rebalance(struct ma_state *mas, unsigned char new_end) { unsigned char p_end, end = 0, slot_cnt, split, b; - unsigned char slot, l_child = 0, r_child = 0; + unsigned char l_child = 0, r_child = 0; char empty = mas->full_cnt * -1; int height = 0; struct maple_enode *left, *right; @@ -1743,12 +1731,8 @@ static inline int mas_commit_rebalance(struct ma_state *mas, printk("%s: left will have %u - %u\n", __func__, 0, split + 1); mab_mas_cp(b_node, 0, split + 1, &cp, 0); l_piv = cp.max; - if (mt_is_alloc(mas->tree)) { - if (mte_is_leaf(left)) - l_gap = mas_leaf_max_gap(&cp); - else - l_gap = mas_max_gap(&cp, &slot); - } + if (mt_is_alloc(mas->tree)) + l_gap = mas_find_gap(&cp); if (end >= slot_cnt) { right = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), @@ -1756,12 +1740,8 @@ static inline int mas_commit_rebalance(struct ma_state *mas, cp.node = right; printk("%s: right will have %u - %u\n", __func__, split + 1, end + 1); mab_mas_cp(b_node, split + 1, end + 1, &cp, 0); - if (mt_is_alloc(mas->tree)) { - if (mte_is_leaf(right)) - r_gap = mas_leaf_max_gap(&cp); - else - r_gap = mas_max_gap(&cp, &slot); - } + if (mt_is_alloc(mas->tree)) + r_gap = mas_find_gap(&cp); } else { // Totally merged with the left. @@ -1841,7 +1821,8 @@ new_root_node: /* Insert new data */ _mas_replace(mas, false, false, true); - mas_update_gap(mas, false); + if (mt_is_alloc(mas->tree)) + mas_update_gap(mas, false); /* Adoption routine... */ @@ -2023,14 +2004,8 @@ static inline int mas_commit_split(struct ma_state *mas, b_node->pivot[i] = l_mas.max; mas_set_slot(&l_mas, i); if (mt_is_alloc(mas->tree)) { - if (mte_is_leaf(l_mas.node)) { - b_node->gap[i] = mas_leaf_max_gap(&l_mas); - b_node->gap[i + 1] = mas_leaf_max_gap(&r_mas); - } else { - unsigned char slot; - b_node->gap[i] = mas_max_gap(&l_mas, &slot); - b_node->gap[i + 1] = mas_max_gap(&r_mas, &slot); - } + b_node->gap[i] = mas_find_gap(&l_mas); + b_node->gap[i + 1] = mas_find_gap(&r_mas); printk("Setting %p gap to %lu\n", mas_mn(&l_mas), b_node->gap[i]); printk("Setting %p gap to %lu\n", @@ -2067,7 +2042,8 @@ static inline int mas_commit_split(struct ma_state *mas, * children with the correct parent. Once the new children are found, * then set the correct parent in all of of the parent's children. */ - mas_update_gap(mas, false); + if (mt_is_alloc(mas->tree)) + mas_update_gap(mas, false); mt_dump(mas->tree); printk("Start at %p\n", mas_mn(mas)); mas_dup_state(&orig_l_mas, mas); @@ -2147,7 +2123,8 @@ static inline int mas_commit_b_node(struct ma_state *mas, printk("Copy out 0-%u\n", end); mab_mas_cp(b_node, 0, end + 1, mas, 0); _mas_replace(mas, true, false, true); - mas_update_gap(mas, false); + if (mt_is_alloc(mas->tree)) + mas_update_gap(mas, false); return 2; } @@ -2443,7 +2420,6 @@ static inline bool __mas_walk(struct ma_state *mas, unsigned long *range_min, static inline int mas_spanning_store(struct ma_state *mas, void *entry) { unsigned long range_min, range_max; - unsigned long l_gap = 0, r_gap = 0; unsigned char b_end = 0; // big_node end. unsigned char l_slot, r_slot; struct maple_big_node b_node; @@ -2554,16 +2530,26 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) b_node.pivot[b_end++] = mas->last; printk("Set %lu to %p\n", mas->last, entry); } else { - // Not a leaf means new_l_mas goes at l_slot. + // Not a leaf means new l_mas is placed at b_end. b_node.slot[b_end] = l_mas.node; + if(mt_is_alloc(mas->tree)) { + b_node.gap[b_end] = mas_find_gap(&l_mas); + printk("gap %u is %lu\n", b_end, b_node.gap[b_end]); + } b_node.pivot[b_end++] = l_mas.max; if (next) { + // FIXME: What about gap? b_node.slot[b_end] = next; b_node.pivot[b_end++] = r_mas.min - 1; } if (r_mas.node != l_mas.node) { b_node.slot[b_end] = r_mas.node; + if(mt_is_alloc(mas->tree)) { + b_node.gap[b_end] = + mas_find_gap(&r_mas); + printk("gap %u is %lu\n", b_end, b_node.gap[b_end]); + } b_node.pivot[b_end++] = r_mas.max; } } @@ -2713,18 +2699,21 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) memset(&b_node, 0, sizeof(struct maple_big_node)); b_end = mas_mab_cp(&orig_l_mas, 0, l_slot, &b_node, 0); b_node.slot[b_end] = l_mas.node; - printk("Set b_end %u to left %p\n", b_end, l_mas.node); + b_node.gap[b_end] = mas_find_gap(&l_mas); + printk("Set b_end %u to left %p gap %lu\n", b_end, l_mas.node, b_node.gap[b_end]); printk("l_mas.max = %lu\n", l_mas.max); b_node.pivot[b_end++] = l_mas.max; if (next) { b_node.slot[b_end] = next; + // FIXME: Need to find gap. printk("Set b_end %u to next %p\n", b_end, next); b_node.pivot[b_end++] = r_mas.min - 1; } if (l_mas.node != r_mas.node) { b_node.slot[b_end] = r_mas.node; - printk("Set b_end %u to right %p %lu\n", b_end, r_mas.node, r_mas.max); + b_node.gap[b_end] = mas_find_gap(&r_mas); + printk("Set b_end %u to right %p %lu gap %lu\n", b_end, r_mas.node, r_mas.max, b_node.gap[b_end]); b_node.pivot[b_end++] = r_mas.max; } @@ -2774,41 +2763,21 @@ new_root: if (mte_is_leaf(mas->node)) return 1; - if (mt_is_alloc(mas->tree)) { - l_gap = mas_leaf_max_gap(&prev_l_mas); - l_slot = mte_parent_slot(prev_l_mas.node); - r_gap = mas_leaf_max_gap(&prev_r_mas); - r_slot = mte_parent_slot(prev_r_mas.node); - } - do { - mas_dup_state(&l_mas, &prev_l_mas); - mas_dup_state(&r_mas, &prev_r_mas); // Ascend. + printk("Ascend from %p\n", mas_mn(&prev_l_mas)); + printk("Ascend from %p\n", mas_mn(&prev_r_mas)); mas_ascend(&prev_l_mas); mas_ascend(&prev_r_mas); - if (mt_is_alloc(mas->tree)) { - // mas_update_gap and friends (don't recursively do this) - printk("Set gap %p[%u] %lu\n", mas_mn(&prev_l_mas), l_slot, l_gap); - mte_set_gap(prev_l_mas.node, l_slot, l_gap); - l_gap = mas_max_gap(&prev_l_mas, &l_slot); - l_slot = mte_parent_slot(prev_l_mas.node); - - printk("Set gap %p[%u] %lu\n", mas_mn(&prev_r_mas), r_slot, r_gap); - mte_set_gap(prev_r_mas.node, r_slot, r_gap); - r_gap = mas_max_gap(&prev_r_mas, &r_slot); - r_slot = mte_parent_slot(prev_r_mas.node); - } // adopt children of nodes that don't have the correct parent - mas_adopt_children(&l_mas, prev_l_mas.node); - mas_adopt_children(&r_mas, prev_r_mas.node); + mas_adopt_children(&prev_l_mas, prev_l_mas.node); + mas_adopt_children(&prev_r_mas, prev_r_mas.node); } while (prev_l_mas.node != l); - mas_update_gap(&l_mas, false); - if (mt_is_alloc(mas->tree)) mas_update_gap(mas, false); + // Free list of collected nodes. // FIXME -- 2.50.1