1 /* Private definitions for the generic associative array implementation.
3 * See Documentation/core-api/assoc_array.rst for information.
5 * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved.
6 * Written by David Howells (dhowells@redhat.com)
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.
14 #ifndef _LINUX_ASSOC_ARRAY_PRIV_H
15 #define _LINUX_ASSOC_ARRAY_PRIV_H
17 #ifdef CONFIG_ASSOCIATIVE_ARRAY
19 #include <linux/assoc_array.h>
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))
29 * Undefined type representing a pointer with type information in the bottom
32 struct assoc_array_ptr
;
35 * An N-way node in the tree.
37 * Each slot contains one of four things:
41 * (2) A leaf object (pointer types 0).
43 * (3) A next-level node (pointer type 1, subtype 0).
45 * (4) A shortcut (pointer type 1, subtype 1).
47 * The tree is optimised for search-by-ID, but permits reasonable iteration
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.
53 * The segments correspond to levels of the tree (the first segment is used at
54 * level 0, the second at level 1, etc.).
56 struct assoc_array_node
{
57 struct assoc_array_ptr
*back_pointer
;
59 struct assoc_array_ptr
*slots
[ASSOC_ARRAY_FAN_OUT
];
60 unsigned long nr_leaves_on_branch
;
64 * A shortcut through the index space out to where a collection of nodes/leaves
65 * with the same IDs live.
67 struct assoc_array_shortcut
{
68 struct assoc_array_ptr
*back_pointer
;
71 struct assoc_array_ptr
*next_node
;
72 unsigned long index_key
[];
76 * Preallocation cache.
78 struct assoc_array_edit
{
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
;
94 struct assoc_array_ptr
**ptr
;
95 struct assoc_array_ptr
*to
;
100 } set_parent_slot
[1];
101 u8 segment_cache
[ASSOC_ARRAY_FAN_OUT
+ 1];
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.
109 * We provide functions to test type annotations and to create and translate
110 * the annotated pointers.
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
119 static inline bool assoc_array_ptr_is_meta(const struct assoc_array_ptr
*x
)
121 return (unsigned long)x
& ASSOC_ARRAY_PTR_TYPE_MASK
;
123 static inline bool assoc_array_ptr_is_leaf(const struct assoc_array_ptr
*x
)
125 return !assoc_array_ptr_is_meta(x
);
127 static inline bool assoc_array_ptr_is_shortcut(const struct assoc_array_ptr
*x
)
129 return (unsigned long)x
& ASSOC_ARRAY_PTR_SUBTYPE_MASK
;
131 static inline bool assoc_array_ptr_is_node(const struct assoc_array_ptr
*x
)
133 return !assoc_array_ptr_is_shortcut(x
);
136 static inline void *assoc_array_ptr_to_leaf(const struct assoc_array_ptr
*x
)
138 return (void *)((unsigned long)x
& ~ASSOC_ARRAY_PTR_TYPE_MASK
);
142 unsigned long __assoc_array_ptr_to_meta(const struct assoc_array_ptr
*x
)
144 return (unsigned long)x
&
145 ~(ASSOC_ARRAY_PTR_SUBTYPE_MASK
| ASSOC_ARRAY_PTR_TYPE_MASK
);
148 struct assoc_array_node
*assoc_array_ptr_to_node(const struct assoc_array_ptr
*x
)
150 return (struct assoc_array_node
*)__assoc_array_ptr_to_meta(x
);
153 struct assoc_array_shortcut
*assoc_array_ptr_to_shortcut(const struct assoc_array_ptr
*x
)
155 return (struct assoc_array_shortcut
*)__assoc_array_ptr_to_meta(x
);
159 struct assoc_array_ptr
*__assoc_array_x_to_ptr(const void *p
, unsigned long t
)
161 return (struct assoc_array_ptr
*)((unsigned long)p
| t
);
164 struct assoc_array_ptr
*assoc_array_leaf_to_ptr(const void *p
)
166 return __assoc_array_x_to_ptr(p
, ASSOC_ARRAY_PTR_LEAF_TYPE
);
169 struct assoc_array_ptr
*assoc_array_node_to_ptr(const struct assoc_array_node
*p
)
171 return __assoc_array_x_to_ptr(
172 p
, ASSOC_ARRAY_PTR_META_TYPE
| ASSOC_ARRAY_PTR_NODE_SUBTYPE
);
175 struct assoc_array_ptr
*assoc_array_shortcut_to_ptr(const struct assoc_array_shortcut
*p
)
177 return __assoc_array_x_to_ptr(
178 p
, ASSOC_ARRAY_PTR_META_TYPE
| ASSOC_ARRAY_PTR_SHORTCUT_SUBTYPE
);
181 #endif /* CONFIG_ASSOCIATIVE_ARRAY */
182 #endif /* _LINUX_ASSOC_ARRAY_PRIV_H */