From 670f8e3e8003f42ee73967c33b60b5365191a9b6 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 1 Feb 2019 13:00:47 -0500 Subject: [PATCH] maple_tree: Fix root bit & parent type. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 34 ++++++++++++++++++++++------------ 1 file changed, 22 insertions(+), 12 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 05db6c45c34a..05035db5facd 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -69,18 +69,29 @@ static inline struct maple_node *mt_to_node(const void *entry) static inline void *mt_mk_node(const struct maple_node *node, enum maple_type type) { - return (void *)((unsigned long)node | (type << 3)); + return (void *)((unsigned long)node | (type << 3) | 4); } -static inline struct maple_node *mt_safe_root(const void *entry) +static inline +void *mt_mk_root(const struct maple_node *node) +{ + return (void *)((unsigned long)node | 2); +} +static inline +void *mt_safe_root(const struct maple_node *node) +{ + return (void *)((unsigned long)node & ~2); +} +static inline +void *mt_is_full(const struct maple_node *node) { - return (struct maple_node *)((unsigned long)entry & ~2); + return (void *)((unsigned long)node & ~4); } static inline -void *mt_mk_root(const struct maple_node *node) +void mt_set_full(const struct maple_node *node) { - return (void *)((unsigned long)node | 2); + node = (void *)((unsigned long)node | 4); } static inline bool mas_is_err(struct ma_state *mas) @@ -146,8 +157,6 @@ static inline void mt_set_parent(struct maple_node *node, static inline unsigned int mt_parent_shift(unsigned long parent) { - if (parent & 1) - return 0; // Root. if (!(parent & 2)) return 2; // maple_range_16 return 3; @@ -158,8 +167,8 @@ static inline unsigned int mt_parent_slot(struct maple_node *node) unsigned long val = (unsigned long) mt_to_node(node)->parent; unsigned long slot_shift = mt_parent_shift(val); - if (!slot_shift) - return 0; + if (val & 1) + return 0; // Root. return (val & bitmask) >> slot_shift; } @@ -169,7 +178,7 @@ static inline enum maple_type mt_parent_type(struct maple_node *node) unsigned long parent = (unsigned long) mt_to_node(node)->parent; unsigned long slot_shift = mt_parent_shift(parent); - parent &= (1 << (slot_shift + 1)) - 1; + parent &= (1 << slot_shift ) - 1; switch (parent) { case 6: return maple_range_64; @@ -390,6 +399,7 @@ static void *mas_start(struct ma_state *mas) } else { entry = mt_safe_root(entry); } + } else { entry = mas->node; } @@ -584,7 +594,7 @@ static int ma_split(struct ma_state *mas, unsigned char slot, enum maple_type ptype; // parent type. unsigned long pivot; - if (ma_is_root(full)) { + if (ma_is_root(mas->node)) { old_parent = full; ptype = maple_range_64; p_slot = 0; @@ -714,7 +724,7 @@ static int _ma_insert(struct ma_state *mas, void *entry, unsigned char slot) if (mas->index && min != mas->index - 1) n_end++; - if (n_end > MAPLE_RANGE64_SLOTS -1) { + if (n_end > MAPLE_RANGE64_SLOTS - 1) { unsigned char split = ma_split(mas, slot, o_end); if (mas_is_err(mas)) return 0; -- 2.50.1