lkml.org 
[lkml]   [2021]   [May]   [14]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH 26/94] Maple Tree: Add new data structure
On Wed, Apr 28, 2021 at 03:36:02PM +0000, Liam Howlett wrote:

> +/*
> + * Special values for ma_state.node.
> + * MAS_START means we have not searched the tree.
> + * MAS_ROOT means we have searched the tree and the entry we found lives in
> + * the root of the tree (ie it has index 0, length 1 and is the only entry in
> + * the tree).
> + * MAS_NONE means we have searched the tree and there is no node in the
> + * tree for this entry. For example, we searched for index 1 in an empty
> + * tree. Or we have a tree which points to a full leaf node and we
> + * searched for an entry which is larger than can be contained in that
> + * leaf node.
> + * MA_ERROR represents an errno. After dropping the lock and attempting
> + * to resolve the error, the walk would have to be restarted from the
> + * top of the tree as the tree may have been modified.
> + */
> +#define MAS_START ((struct maple_enode *)1UL)
> +#define MAS_ROOT ((struct maple_enode *)5UL)
> +#define MAS_NONE ((struct maple_enode *)9UL)
> +#define MA_ERROR(err) \
> + ((struct maple_enode *)(((unsigned long)err << 2) | 2UL))
> +

> +static inline enum maple_type mte_node_type(const struct maple_enode *entry)
> +{
> + return ((unsigned long)entry >> 3) & 15;
> +}

> +static inline struct maple_node *mte_to_node(const struct maple_enode *entry)
> +{
> + return (struct maple_node *)((unsigned long)entry & ~127);
> +}

> +static inline struct maple_topiary *mte_to_mat(const struct maple_enode *entry)
> +{
> + return (struct maple_topiary *)((unsigned long)entry & ~127);
> +}

Can we please write masks as hex, also do they want a pretty name?


This has more magic mask values, proper names might be good:

> +static inline void mte_set_parent(struct maple_enode *enode,
> + const struct maple_enode *parent,
> + unsigned char slot)
> +{
> + unsigned long bitmask = 0x78;
> + unsigned long val = (unsigned long) parent;
> + unsigned long type = 0;
> +
> + switch (mte_node_type(parent)) {
> + case maple_range_64:
> + case maple_arange_64:
> + type = 6;
> + break;
> + default:
> + break;
> + }
> +
> + val &= ~bitmask; // Remove any old slot number.
> + val |= (slot << MAPLE_PARENT_SHIFT); // Set the slot.
> + val |= type;
> + mte_to_node(enode)->parent = ma_parent_ptr(val);
> +}

> +static inline unsigned int mte_parent_slot(const struct maple_enode *enode)
> +{
> + unsigned long bitmask = 0x7C;
> + unsigned long val = (unsigned long) mte_to_node(enode)->parent;
> +
> + if (val & 1)
> + return 0; // Root.
> +
> + return (val & bitmask) >> MAPLE_PARENT_SHIFT;

7c is 1111100, but then you're shifting out the one bit that makes the
difference from the above magic 0x78. What gives?

> +}

\
 
 \ /
  Last update: 2021-05-14 13:15    [W:0.441 / U:1.104 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site