include/linux/assoc_array_priv.h

   1 /* SPDX-License-Identifier: GPL-2.0-or-later */
   2 /* Private definitions for the generic associative array implementation.
   3  *
   4  * See Documentation/core-api/assoc_array.rst for information.
   5  *
   6  * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved.
   7  * Written by David Howells (dhowells@redhat.com)
   8  */
   9
  10 #ifndef _LINUX_ASSOC_ARRAY_PRIV_H
  11 #define _LINUX_ASSOC_ARRAY_PRIV_H
  12
  13 #ifdef CONFIG_ASSOCIATIVE_ARRAY
  14
  15 #include <linux/assoc_array.h>
  16
  17 #define ASSOC_ARRAY_FAN_OUT             16      /* Number of slots per node */
  18 #define ASSOC_ARRAY_FAN_MASK            (ASSOC_ARRAY_FAN_OUT - 1)
  19 #define ASSOC_ARRAY_LEVEL_STEP          (ilog2(ASSOC_ARRAY_FAN_OUT))
  20 #define ASSOC_ARRAY_LEVEL_STEP_MASK     (ASSOC_ARRAY_LEVEL_STEP - 1)
  21 #define ASSOC_ARRAY_KEY_CHUNK_MASK      (ASSOC_ARRAY_KEY_CHUNK_SIZE - 1)
  22 #define ASSOC_ARRAY_KEY_CHUNK_SHIFT     (ilog2(BITS_PER_LONG))
  23
  24 /*
  25  * Undefined type representing a pointer with type information in the bottom
  26  * two bits.
  27  */
  28 struct assoc_array_ptr;
  29
  30 /*
  31  * An N-way node in the tree.
  32  *
  33  * Each slot contains one of four things:
  34  *
  35  *      (1) Nothing (NULL).
  36  *
  37  *      (2) A leaf object (pointer types 0).
  38  *
  39  *      (3) A next-level node (pointer type 1, subtype 0).
  40  *
  41  *      (4) A shortcut (pointer type 1, subtype 1).
  42  *
  43  * The tree is optimised for search-by-ID, but permits reasonable iteration
  44  * also.
  45  *
  46  * The tree is navigated by constructing an index key consisting of an array of
  47  * segments, where each segment is ilog2(ASSOC_ARRAY_FAN_OUT) bits in size.
  48  *
  49  * The segments correspond to levels of the tree (the first segment is used at
  50  * level 0, the second at level 1, etc.).
  51  */
  52 struct assoc_array_node {
  53         struct assoc_array_ptr  *back_pointer;
  54         u8                      parent_slot;
  55         struct assoc_array_ptr  *slots[ASSOC_ARRAY_FAN_OUT];
  56         unsigned long           nr_leaves_on_branch;
  57 };
  58
  59 /*
  60  * A shortcut through the index space out to where a collection of nodes/leaves
  61  * with the same IDs live.
  62  */
  63 struct assoc_array_shortcut {
  64         struct assoc_array_ptr  *back_pointer;
  65         int                     parent_slot;
  66         int                     skip_to_level;
  67         struct assoc_array_ptr  *next_node;
  68         unsigned long           index_key[];
  69 };
  70
  71 /*
  72  * Preallocation cache.
  73  */
  74 struct assoc_array_edit {
  75         struct rcu_head                 rcu;
  76         struct assoc_array              *array;
  77         const struct assoc_array_ops    *ops;
  78         const struct assoc_array_ops    *ops_for_excised_subtree;
  79         struct assoc_array_ptr          *leaf;
  80         struct assoc_array_ptr          **leaf_p;
  81         struct assoc_array_ptr          *dead_leaf;
  82         struct assoc_array_ptr          *new_meta[3];
  83         struct assoc_array_ptr          *excised_meta[1];
  84         struct assoc_array_ptr          *excised_subtree;
  85         struct assoc_array_ptr          **set_backpointers[ASSOC_ARRAY_FAN_OUT];
  86         struct assoc_array_ptr          *set_backpointers_to;
  87         struct assoc_array_node         *adjust_count_on;
  88         long                            adjust_count_by;
  89         struct {
  90                 struct assoc_array_ptr  **ptr;
  91                 struct assoc_array_ptr  *to;
  92         } set[2];
  93         struct {
  94                 u8                      *p;
  95                 u8                      to;
  96         } set_parent_slot[1];
  97         u8                              segment_cache[ASSOC_ARRAY_FAN_OUT + 1];
  98 };
  99
 100 /*
 101  * Internal tree member pointers are marked in the bottom one or two bits to
 102  * indicate what type they are so that we don't have to look behind every
 103  * pointer to see what it points to.
 104  *
 105  * We provide functions to test type annotations and to create and translate
 106  * the annotated pointers.
 107  */
 108 #define ASSOC_ARRAY_PTR_TYPE_MASK 0x1UL
 109 #define ASSOC_ARRAY_PTR_LEAF_TYPE 0x0UL /* Points to leaf (or nowhere) */
 110 #define ASSOC_ARRAY_PTR_META_TYPE 0x1UL /* Points to node or shortcut */
 111 #define ASSOC_ARRAY_PTR_SUBTYPE_MASK    0x2UL
 112 #define ASSOC_ARRAY_PTR_NODE_SUBTYPE    0x0UL
 113 #define ASSOC_ARRAY_PTR_SHORTCUT_SUBTYPE 0x2UL
 114
 115 static inline bool assoc_array_ptr_is_meta(const struct assoc_array_ptr *x)
 116 {
 117         return (unsigned long)x & ASSOC_ARRAY_PTR_TYPE_MASK;
 118 }
 119 static inline bool assoc_array_ptr_is_leaf(const struct assoc_array_ptr *x)
 120 {
 121         return !assoc_array_ptr_is_meta(x);
 122 }
 123 static inline bool assoc_array_ptr_is_shortcut(const struct assoc_array_ptr *x)
 124 {
 125         return (unsigned long)x & ASSOC_ARRAY_PTR_SUBTYPE_MASK;
 126 }
 127 static inline bool assoc_array_ptr_is_node(const struct assoc_array_ptr *x)
 128 {
 129         return !assoc_array_ptr_is_shortcut(x);
 130 }
 131
 132 static inline void *assoc_array_ptr_to_leaf(const struct assoc_array_ptr *x)
 133 {
 134         return (void *)((unsigned long)x & ~ASSOC_ARRAY_PTR_TYPE_MASK);
 135 }
 136
 137 static inline
 138 unsigned long __assoc_array_ptr_to_meta(const struct assoc_array_ptr *x)
 139 {
 140         return (unsigned long)x &
 141                 ~(ASSOC_ARRAY_PTR_SUBTYPE_MASK | ASSOC_ARRAY_PTR_TYPE_MASK);
 142 }
 143 static inline
 144 struct assoc_array_node *assoc_array_ptr_to_node(const struct assoc_array_ptr *x)
 145 {
 146         return (struct assoc_array_node *)__assoc_array_ptr_to_meta(x);
 147 }
 148 static inline
 149 struct assoc_array_shortcut *assoc_array_ptr_to_shortcut(const struct assoc_array_ptr *x)
 150 {
 151         return (struct assoc_array_shortcut *)__assoc_array_ptr_to_meta(x);
 152 }
 153
 154 static inline
 155 struct assoc_array_ptr *__assoc_array_x_to_ptr(const void *p, unsigned long t)
 156 {
 157         return (struct assoc_array_ptr *)((unsigned long)p | t);
 158 }
 159 static inline
 160 struct assoc_array_ptr *assoc_array_leaf_to_ptr(const void *p)
 161 {
 162         return __assoc_array_x_to_ptr(p, ASSOC_ARRAY_PTR_LEAF_TYPE);
 163 }
 164 static inline
 165 struct assoc_array_ptr *assoc_array_node_to_ptr(const struct assoc_array_node *p)
 166 {
 167         return __assoc_array_x_to_ptr(
 168                 p, ASSOC_ARRAY_PTR_META_TYPE | ASSOC_ARRAY_PTR_NODE_SUBTYPE);
 169 }
 170 static inline
 171 struct assoc_array_ptr *assoc_array_shortcut_to_ptr(const struct assoc_array_shortcut *p)
 172 {
 173         return __assoc_array_x_to_ptr(
 174                 p, ASSOC_ARRAY_PTR_META_TYPE | ASSOC_ARRAY_PTR_SHORTCUT_SUBTYPE);
 175 }
 176
 177 #endif /* CONFIG_ASSOCIATIVE_ARRAY */
 178 #endif /* _LINUX_ASSOC_ARRAY_PRIV_H */