Warning: This file is not a C or C++ file. It does not have highlighting.
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 */ |
179 |
Warning: This file is not a C or C++ file. It does not have highlighting.