include/linux/assoc_array_priv.h

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