From 0839b0a556b681ec9ff680afcfcba4ac1cef44f9 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Wed, 14 Aug 2019 13:30:36 -0400 Subject: [PATCH] maple_tree: Add layout comments to header. Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 39 +++++++++++++++++++++++++++++++++++--- 1 file changed, 36 insertions(+), 3 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 9e5956511cf8..ff2bfb7ed318 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -43,9 +43,42 @@ typedef struct maple_enode *maple_enode; // encoded node. typedef struct maple_pnode *maple_pnode; // parent node. -/* - * We can be more cache-efficient if we interleave pivots and slots. - * Code will be more complex, though. + + +/** + * maple_tree node explained + * + * Each node type has a number of slots for entries and a number of slots for + * pivots. In the case of dense nodes, the pivots are implied by the position + * and are simply the slot index + the minimum of the node. + * + * In regular B-Tree terms, pivots are called keys. The term pivot is used to + * indicate that the tree is specifying ranges, Pivots may appear in the + * subtree with an entry attached to the value where as keys are unique to a + * specific position of a B-tree. Pivot values are inclusive of the slot with + * the same index. + * + * + * The following illustrates the layout of a range64 nodes slots and pivots. + * + * _________________________________ + * Slots -> | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | + * ┬ ┬ ┬ ┬ ┬ ┬ ┬ ┬ ┬ + * │ │ │ │ │ │ │ │ └─ Implied maximum + * │ │ │ │ │ │ │ └─ Pivot 6 + * │ │ │ │ │ │ └─ Pivot 5 + * │ │ │ │ │ └─ Pivot 4 + * │ │ │ │ └─ Pivot 3 + * │ │ │ └─ Pivot 2 + * │ │ └─ Pivot 1 + * │ └─ Pivot 0 + * └─ Implied minimum + * + * Slot contents: + * Internal (non-leaf) nodes contain pointers to other nodes. + * Leaf nodes contain entries. + * + * */ struct maple_range_64 { struct maple_pnode *parent; -- 2.50.1