Commit | Line | Data |
---|---|---|
b4d0d230 | 1 | /* SPDX-License-Identifier: GPL-2.0-or-later */ |
3cb98950 DH |
2 | /* Private definitions for the generic associative array implementation. |
3 | * | |
5fb94e9c | 4 | * See Documentation/core-api/assoc_array.rst for information. |
3cb98950 DH |
5 | * |
6 | * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved. | |
7 | * Written by David Howells (dhowells@redhat.com) | |
3cb98950 DH |
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 */ |