From e6e1dea68807c24dce01e77fbfb706e3f0d4ce35 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 17 Jul 2020 16:43:57 -0400 Subject: [PATCH] maple_tree: Comments comments comments. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 185 +++++++++++++++++++++++++++++------------------ 1 file changed, 116 insertions(+), 69 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 3e93f13c90f2..668f2cb80477 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -240,19 +240,16 @@ static inline struct maple_enode *mt_mk_node(const struct maple_node *node, return (void *)((unsigned long)node | (type << 3) | 4); } -static inline -void *mte_mk_root(const struct maple_enode *node) +static inline void *mte_mk_root(const struct maple_enode *node) { return (void *)((unsigned long)node | 2); } -static inline -void *mte_safe_root(const struct maple_enode *node) +static inline void *mte_safe_root(const struct maple_enode *node) { return (void *)((unsigned long)node & ~2); } -static inline -void mte_set_full(const struct maple_enode *node) +static inline void mte_set_full(const struct maple_enode *node) { node = (void *)((unsigned long)node | 4); } @@ -651,13 +648,10 @@ void mte_destroy_walk(struct maple_enode *mn, struct maple_tree *mtree) } /** Private - * mt_dead_list_add() - Add a @dead_node to the @tail of a list of dead nodes. - * @tail may be modified to point to @dead_node if @tail is full. + * matadd() - Add a @dead_enode to the ma_topiary of a list of dead nodes. * - * @mtree - the tree which contains the node to be marked ad dead. - * @tail - the tail of the dead list - * @dead_node - the node to be marked as dead and added to the tail of the list - * (or to become the tail node of the list) + * @mat - the ma_topiary, a linked list of dead nodes. + * @dead_enode - the node to be marked as dead and added to the tail of the list */ static inline void mat_add(struct ma_topiary *mat, struct maple_enode *dead_enode) @@ -674,10 +668,11 @@ static inline void mat_add(struct ma_topiary *mat, mat->tail = dead_enode; } /** Private - * mt_dead_list_free() - Free all nodes in a dead list. + * mat_free() - Free all nodes in a dead list. * - * @mtree - the tree which contains the nodes that will be freed. - * @head - the start of the list of dead nodes to be freed. + * @mat - the ma_topiary linked list of dead nodes to free. + * @recursive - specifies if this sub-tree is to be freed or just the single + * node. */ static inline void mat_free(struct ma_topiary *mat, bool recursive) { @@ -1080,10 +1075,13 @@ done: return entry; } -/* Private +/** Private * mas_data_end() - Find the end of the data (slot). Sets the value of the * last pivot to @last_piv. * + * @mas - the maple state + * @type - the type of maple node + * @last_piv - the final pivot in this node. */ static inline unsigned char _mas_data_end(const struct ma_state *mas, const enum maple_type type, unsigned long *last_piv) @@ -1112,7 +1110,11 @@ static inline unsigned char mas_data_end(const struct ma_state *mas) unsigned long l; return _mas_data_end(mas, mte_node_type(mas->node), &l); } - +/** Private + * mas_leaf_max_gap() - Returns the largest gap in a leaf node + * + * @mas - the maple state + */ static inline unsigned long mas_leaf_max_gap(struct ma_state *mas) { enum maple_type mt = mte_node_type(mas->node); @@ -1163,8 +1165,10 @@ done: return max_gap; } -static inline unsigned long mas_max_gap(struct ma_state *mas, - unsigned char *slot) +/** Private + * mas_max_gap() - find the largest gap in a non-leaf node and set the slot. + */ +static inline unsigned long mas_max_gap(struct ma_state *mas) { unsigned long max_gap = 0; unsigned char i; @@ -1173,26 +1177,22 @@ static inline unsigned long mas_max_gap(struct ma_state *mas, unsigned long gap; gap = mte_get_gap(mas->node, i); - if (gap > max_gap) { - *slot = i; + if (gap > max_gap) max_gap = gap; - } } 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); + return mas_max_gap(mas); } static inline void mas_parent_gap(struct ma_state *mas, unsigned char slot, - unsigned long new, bool force) + unsigned long new) { - unsigned char max_slot = 0; unsigned long old_max_gap; /* Don't mess with mas state, use a new state */ @@ -1202,11 +1202,11 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char slot, ascend: /* Go to the parent node. */ mas_ascend(&gaps); - old_max_gap = mas_max_gap(&gaps, &max_slot); + old_max_gap = mas_max_gap(&gaps); mte_set_gap(gaps.node, slot, new); - new = mas_max_gap(&gaps, &slot); + new = mas_max_gap(&gaps); - if (!force && new == old_max_gap) + if (new == old_max_gap) return; if (mte_is_root(gaps.node)) @@ -1216,32 +1216,33 @@ ascend: goto ascend; } /* Private + * mas_update_gap() - Update a nodes gaps and propagate up if necessary. * - * mas_update_gap() - Update a nodes gaps and propagate up if necessary or - * force by setting @force to true. + * @mas - the maple state. */ -static inline void mas_update_gap(struct ma_state *mas, bool force) +static inline void mas_update_gap(struct ma_state *mas) { unsigned char pslot; unsigned long p_gap, max_gap = 0; - unsigned char slot = 0; - /* Get the largest gap in mas->node */ + if (!mt_is_alloc(mas->tree)) + return; + if (mte_is_root(mas->node)) return; if (mte_is_leaf(mas->node)) max_gap = mas_leaf_max_gap(mas); else - max_gap = mas_max_gap(mas, &slot); + max_gap = mas_max_gap(mas); /* Get the gap reported in the parent */ pslot = mte_parent_slot(mas->node); p_gap = ma_get_gap(mte_parent(mas->node), pslot, mas_parent_enum(mas, mas->node)); - if (force || p_gap != max_gap) - mas_parent_gap(mas, pslot, max_gap, force); + if (p_gap != max_gap) + mas_parent_gap(mas, pslot, max_gap); } @@ -1260,11 +1261,10 @@ static inline unsigned long mas_first_node(struct ma_state *mas, { int slot = mas_get_slot(mas) - 1; unsigned char count = mt_slot_count(mas->node); - unsigned long min = mas->min; + unsigned long pivot, min = mas->min; while (++slot < count) { struct maple_enode *mn; - unsigned long pivot; pivot = mas_get_safe_pivot(mas, slot); if (pivot > limit) @@ -1291,12 +1291,12 @@ no_entry: mas->node = MAS_NONE; return mas->max; } -/* Private - * - * Returns the pivot which points to the entry with the lowest index. - * @mas slot is set to the entry location. - * @limit is the maximum index to check. +/** Private + * mas_first_entry() - * Returns the pivot which points to the entry with the + * lowest index. * + * @mas: the maple state. + * @limit: the maximum index to check. */ static inline unsigned long mas_first_entry(struct ma_state *mas, unsigned long limit) @@ -1322,8 +1322,13 @@ static inline unsigned long mas_first_entry(struct ma_state *mas, } } - - +/** Private + * mas_adopt_children() - Set the parent pointer of all nodes in @parent to + * @parent with the slot encoded. + * + * @mas - the maple state (for the tree) + * @parent - the maple encoded node containing the children. + */ static inline void mas_adopt_children(struct ma_state *mas, struct maple_enode *parent) { @@ -1343,13 +1348,14 @@ static inline void mas_adopt_children(struct ma_state *mas, mte_set_parent(child, parent, slot); } } -/* Private + +/** Private * mas_replace() - Replace a maple node in the tree with mas->node. Uses the * parent encoding to locate the maple node in the tree. * * @mas - the ma_state to use for operations. - * @advanced - boolean to free/adopt (false) or leave the node as is (true) - * + * @advanced - boolean to adopt the child nodes and free the old node (false) or + * leave the node (true) and handle the adoption and free elsewhere. */ static inline void mas_replace(struct ma_state *mas, bool advanced) { @@ -1389,7 +1395,12 @@ static inline void mas_replace(struct ma_state *mas, bool advanced) } } - +/** Private + * mas_check_split_parent() - Check to see if this node has the correct parent + * set or not. + * @mas - the maple state + * @slot - the slot to examine. + */ static inline struct maple_enode *mas_check_split_parent(struct ma_state *mas, unsigned char slot) { @@ -1431,22 +1442,38 @@ static inline struct maple_enode *mas_find_r_split(struct ma_state *mas) } while (!en && i--); return en; } - +/** Private + * mab_shift_right() - Shift the data in mab right. Note, does not clean out the + * old data or set b_node->b_end. + * + * @b_node: the maple_big_node + * @shift: the shift count + */ static inline void mab_shift_right(struct maple_big_node *b_node, - unsigned char shift, bool alloc) + unsigned char shift) { unsigned char b_end = b_node->b_end - 1; do { b_node->pivot[b_end + shift] = b_node->pivot[b_end]; b_node->slot[b_end + shift] = b_node->slot[b_end]; - if (alloc) - b_node->gap[b_end + shift] = b_node->gap[b_end]; + b_node->gap[b_end + shift] = b_node->gap[b_end]; } while (b_end--); } -static inline bool mab_middle_node(struct maple_big_node *b_node, int size, - int split, unsigned char slot_cnt) +/** Private + * mab_middle_node() - Check if a middle node is needed (unlikely) + * + * @b_node: the maple_big_node that contains the data. + * @size: the amount of data in the b_node + * @split: the potential split location + * @slot_cnt: the size that can be stored in a single node being considered. + * Returns: true if a middle node is required. + */ +static inline bool mab_middle_node(struct maple_big_node *b_node, int split, + unsigned char slot_cnt) { + unsigned char size = b_node->b_end; + if (size >= 2 * slot_cnt) return true; @@ -1455,7 +1482,14 @@ static inline bool mab_middle_node(struct maple_big_node *b_node, int size, return false; } - +/** Private + * mab_no_null_split() - ensure the split doesn't fall on a NULL + * + * @b_node: the maple_big_node with the data + * @split: the suggested split location + * @slot_cnt: the number of slots in the node being considered. + * Returns the split location. + */ static inline int mab_no_null_split(struct maple_big_node *b_node, unsigned char split, unsigned char slot_cnt) { @@ -1467,6 +1501,15 @@ static inline int mab_no_null_split(struct maple_big_node *b_node, } return split; } + +/** Private + * mab_calc_split() - Calculate the split location and if there needs to be two + * splits. + * + * @b_node: The maple_big_node with the data + * @mid_split: The second split, if required. 0 otherwise. + * Returns: The first split location. + */ static inline int mab_calc_split(struct maple_big_node *b_node, unsigned char *mid_split) { @@ -1474,7 +1517,7 @@ static inline int mab_calc_split(struct maple_big_node *b_node, unsigned char slot_cnt = mt_slots[b_node->type]; if (ma_is_leaf(b_node->type) && - mab_middle_node(b_node, b_node->b_end, split, slot_cnt)) { + mab_middle_node(b_node, split, slot_cnt)) { split = b_node->b_end / 3; *mid_split = split * 2; } else { @@ -1500,7 +1543,16 @@ static inline int mab_calc_split(struct maple_big_node *b_node, return split; } -/* +/** Private + * mas_mab_cp() - Copy data from a maple state inclusively to a maple_big_node + * and set @b_node->b_end to the next free slot. + * + * @mas: The maple state + * @mas_start: The starting slot to copy + * @mas_end: The end slot to copy (inclusively) + * @b_node: The maple_big_node to place the data + * @mab_start: The starting location in maple_big_node to store the data. + * * Note, mas_end is inclusive */ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, @@ -1738,8 +1790,7 @@ static inline bool mast_rebalance_from_siblings(struct maple_subtree_state *mast unsigned char b_end = mast->bn->b_end; end = mas_data_end(mast->orig_l); // shift mast->bn by prev size - mab_shift_right(mast->bn, end + 1, - (mt_is_alloc(mast->l->tree) ? true : false)); + mab_shift_right(mast->bn, end + 1); // copy in prev. mas_mab_cp(mast->orig_l, 0, end, mast->bn, 0); mat_add(mast->free, left); @@ -1797,8 +1848,7 @@ static inline bool mast_rebalance_from_cousins(struct maple_subtree_state *mast) end = mas_data_end(mast->orig_l); b_end = mast->bn->b_end; // shift mast->bn - mab_shift_right(mast->bn, end + 1, - (mt_is_alloc(mast->l->tree) ? true : false)); + mab_shift_right(mast->bn, end + 1); // copy in prev. mas_mab_cp(mast->orig_l, 0, end, mast->bn, 0); mast->l->min = mast->orig_l->min; @@ -1969,8 +2019,7 @@ static inline void mas_wmb_replace(struct ma_state *mas, if (mte_is_leaf(mas->node)) return; - if (mt_is_alloc(mas->tree)) - mas_update_gap(mas, false); + mas_update_gap(mas); } static inline bool mast_new_root(struct maple_subtree_state *mast, struct ma_state *mas) @@ -2210,8 +2259,7 @@ static inline int mas_rebalance(struct ma_state *mas, unsigned char shift, b_end = b_node->b_end; mas_prev_sibling(&l_mas); shift = mas_data_end(&l_mas) + 1; - mab_shift_right(b_node, shift, - (mt_is_alloc(mas->tree) ? true : false)); + mab_shift_right(b_node, shift); mas_mab_cp(&l_mas, 0, shift - 1, b_node, 0); b_node->b_end = shift + b_end; l_mas.index = l_mas.last = l_mas.min; @@ -2364,8 +2412,7 @@ static inline int mas_commit_b_node(struct ma_state *mas, mab_mas_cp(b_node, 0, b_node->b_end, mas, 0); mas_replace(mas, false); - if (mt_is_alloc(mas->tree)) - mas_update_gap(mas, false); + mas_update_gap(mas); return 2; } -- 2.50.1