Line data Source code
1 : /*
2 : * Copyright (c) 2015 Cisco and/or its affiliates.
3 : * Licensed under the Apache License, Version 2.0 (the "License");
4 : * you may not use this file except in compliance with the License.
5 : * You may obtain a copy of the License at:
6 : *
7 : * http://www.apache.org/licenses/LICENSE-2.0
8 : *
9 : * Unless required by applicable law or agreed to in writing, software
10 : * distributed under the License is distributed on an "AS IS" BASIS,
11 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : * See the License for the specific language governing permissions and
13 : * limitations under the License.
14 : */
15 : /*
16 : Copyright (c) 2005 Eliot Dresselhaus
17 :
18 : Permission is hereby granted, free of charge, to any person obtaining
19 : a copy of this software and associated documentation files (the
20 : "Software"), to deal in the Software without restriction, including
21 : without limitation the rights to use, copy, modify, merge, publish,
22 : distribute, sublicense, and/or sell copies of the Software, and to
23 : permit persons to whom the Software is furnished to do so, subject to
24 : the following conditions:
25 :
26 : The above copyright notice and this permission notice shall be
27 : included in all copies or substantial portions of the Software.
28 :
29 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30 : EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31 : MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32 : NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33 : LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34 : OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35 : WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36 : */
37 :
38 : #ifndef included_sparse_vec_h
39 : #define included_sparse_vec_h
40 :
41 : #include <vppinfra/clib.h>
42 : #include <vppinfra/vec.h>
43 :
44 : /* Sparsely indexed vectors. Basic idea taken from Hacker's delight.
45 : Eliot added ranges. */
46 : typedef struct
47 : {
48 : /* Bitmap one for each sparse index. */
49 : uword *is_member_bitmap;
50 :
51 : /* member_counts[i] = total number of members with j < i. */
52 : u16 *member_counts;
53 :
54 : #define SPARSE_VEC_IS_RANGE (1 << 0)
55 : #define SPARSE_VEC_IS_VALID_RANGE (1 << 1)
56 : u8 *range_flags;
57 : } sparse_vec_header_t;
58 :
59 : always_inline sparse_vec_header_t *
60 7679204 : sparse_vec_header (void *v)
61 : {
62 7679204 : return vec_header (v);
63 : }
64 :
65 : /* Index 0 is always used to mark indices that are not valid in
66 : sparse vector. For example, you look up V[0x1234] and 0x1234 is not
67 : known you'll get 0 back as an index. */
68 : #define SPARSE_VEC_INVALID_INDEX (0)
69 :
70 : always_inline void *
71 4695 : sparse_vec_new (uword elt_bytes, uword sparse_index_bits)
72 : {
73 : void *v;
74 : sparse_vec_header_t *h;
75 : word n;
76 4695 : vec_attr_t va = { .elt_sz = elt_bytes, .hdr_sz = sizeof (h[0]) };
77 :
78 4695 : ASSERT (sparse_index_bits <= 16);
79 :
80 4695 : v = _vec_alloc_internal (/* data bytes */ 8, &va);
81 :
82 : /* Make space for invalid entry (entry 0). */
83 4692 : _vec_set_len (v, 1, elt_bytes);
84 :
85 4694 : h = sparse_vec_header (v);
86 :
87 4694 : n = sparse_index_bits - min_log2 (BITS (uword));
88 4695 : if (n < 0)
89 0 : n = 0;
90 4695 : n = 1ULL << n;
91 4695 : vec_resize (h->is_member_bitmap, n);
92 4695 : vec_resize (h->member_counts, n);
93 :
94 4695 : return v;
95 : }
96 :
97 : always_inline uword
98 7578357 : sparse_vec_index_internal (void *v,
99 : uword sparse_index,
100 : uword maybe_range, u32 * insert)
101 : {
102 : sparse_vec_header_t *h;
103 : uword i, b, d, w;
104 : u8 is_member;
105 :
106 7578357 : h = sparse_vec_header (v);
107 7578357 : i = sparse_index / BITS (h->is_member_bitmap[0]);
108 7578357 : b = sparse_index % BITS (h->is_member_bitmap[0]);
109 :
110 7578357 : ASSERT (i < vec_len (h->is_member_bitmap));
111 7578357 : ASSERT (i < vec_len (h->member_counts));
112 :
113 7578357 : w = h->is_member_bitmap[i];
114 :
115 : /* count_trailing_zeros(0) == 0, take care of that case */
116 7578357 : if (PREDICT_FALSE (maybe_range == 0 && insert == 0 && w == 0))
117 6487784 : return 0;
118 :
119 1090573 : if (PREDICT_TRUE (maybe_range == 0 && insert == 0 &&
120 : count_trailing_zeros (w) == b))
121 20766 : return h->member_counts[i] + 1;
122 :
123 1069806 : d = h->member_counts[i] + count_set_bits (w & ((1ULL << b) - 1));
124 1069806 : is_member = (w & (1ULL << b)) != 0;
125 :
126 1069806 : if (maybe_range)
127 : {
128 0 : u8 r = h->range_flags[d];
129 : u8 is_range, is_valid_range;
130 :
131 0 : is_range = maybe_range & (r & SPARSE_VEC_IS_RANGE);
132 0 : is_valid_range = (r & SPARSE_VEC_IS_VALID_RANGE) != 0;
133 :
134 0 : is_member = is_range ? is_valid_range : is_member;
135 : }
136 :
137 1069806 : if (insert)
138 : {
139 18800 : *insert = !is_member;
140 18800 : if (!is_member)
141 : {
142 : uword j;
143 17613 : w |= 1ULL << b;
144 17613 : h->is_member_bitmap[i] = w;
145 10938737 : for (j = i + 1; j < vec_len (h->member_counts); j++)
146 10921118 : h->member_counts[j] += 1;
147 : }
148 :
149 18800 : return 1 + d;
150 : }
151 :
152 1051006 : d = is_member ? d : 0;
153 :
154 1051006 : return is_member + d;
155 : }
156 :
157 : always_inline uword
158 7559557 : sparse_vec_index (void *v, uword sparse_index)
159 : {
160 7559557 : return sparse_vec_index_internal (v, sparse_index,
161 : /* maybe range */ 0,
162 : /* insert? */ 0);
163 : }
164 :
165 : always_inline void
166 95927 : sparse_vec_index2 (void *v,
167 : u32 si0, u32 si1, u32 * i0_return, u32 * i1_return)
168 : {
169 : sparse_vec_header_t *h;
170 : uword b0, b1, w0, w1, v0, v1;
171 : u32 i0, i1, d0, d1;
172 : u8 is_member0, is_member1;
173 :
174 95927 : h = sparse_vec_header (v);
175 :
176 95927 : i0 = si0 / BITS (h->is_member_bitmap[0]);
177 95927 : i1 = si1 / BITS (h->is_member_bitmap[0]);
178 :
179 95927 : b0 = si0 % BITS (h->is_member_bitmap[0]);
180 95927 : b1 = si1 % BITS (h->is_member_bitmap[0]);
181 :
182 95927 : ASSERT (i0 < vec_len (h->is_member_bitmap));
183 95927 : ASSERT (i1 < vec_len (h->is_member_bitmap));
184 :
185 95927 : ASSERT (i0 < vec_len (h->member_counts));
186 95927 : ASSERT (i1 < vec_len (h->member_counts));
187 :
188 95927 : w0 = h->is_member_bitmap[i0];
189 95927 : w1 = h->is_member_bitmap[i1];
190 :
191 95927 : if (PREDICT_TRUE ((count_trailing_zeros (w0) == b0) +
192 : (count_trailing_zeros (w1) == b1) == 2))
193 : {
194 8525 : *i0_return = h->member_counts[i0] + 1;
195 8525 : *i1_return = h->member_counts[i1] + 1;
196 8525 : return;
197 : }
198 :
199 87402 : v0 = w0 & ((1ULL << b0) - 1);
200 87402 : v1 = w1 & ((1ULL << b1) - 1);
201 :
202 : /* Speculate that masks will have zero or one bits set. */
203 87402 : d0 = h->member_counts[i0] + (v0 != 0);
204 87402 : d1 = h->member_counts[i1] + (v1 != 0);
205 :
206 : /* Validate speculation. */
207 87402 : if (PREDICT_FALSE (!is_pow2 (v0) || !is_pow2 (v1)))
208 : {
209 21817 : d0 += count_set_bits (v0) - (v0 != 0);
210 21817 : d1 += count_set_bits (v1) - (v1 != 0);
211 : }
212 :
213 87402 : is_member0 = (w0 & (1ULL << b0)) != 0;
214 87402 : is_member1 = (w1 & (1ULL << b1)) != 0;
215 :
216 87402 : d0 = is_member0 ? d0 : 0;
217 87402 : d1 = is_member1 ? d1 : 0;
218 :
219 87402 : *i0_return = is_member0 + d0;
220 87402 : *i1_return = is_member1 + d1;
221 : }
222 :
223 : #define sparse_vec_free(V) \
224 : do \
225 : { \
226 : if (V) \
227 : { \
228 : sparse_vec_header_t *_h = sparse_vec_header (V); \
229 : vec_free (_h->is_member_bitmap); \
230 : vec_free (_h->member_counts); \
231 : clib_mem_free (_h); \
232 : V = 0; \
233 : } \
234 : } \
235 : while (0)
236 :
237 : #define sparse_vec_elt_at_index(v,i) \
238 : vec_elt_at_index ((v), sparse_vec_index ((v), (i)))
239 :
240 : #define sparse_vec_validate(v,i) \
241 : ({ \
242 : uword _i; \
243 : u32 _insert; \
244 : \
245 : if (! (v)) \
246 : (v) = sparse_vec_new (sizeof ((v)[0]), BITS (u16)); \
247 : \
248 : _i = sparse_vec_index_internal ((v), (i), \
249 : /* maybe range */ 0, \
250 : /* insert? */ &_insert); \
251 : if (_insert) \
252 : vec_insert_ha ((v), 1, _i, \
253 : /* header size */ sizeof (sparse_vec_header_t), \
254 : /* align */ 0); \
255 : \
256 : /* Invalid index is 0. */ \
257 : ASSERT (_i > 0); \
258 : \
259 : (v) + _i; \
260 : })
261 :
262 : #endif /* included_sparse_vec_h */
263 :
264 : /*
265 : * fd.io coding-style-patch-verification: ON
266 : *
267 : * Local Variables:
268 : * eval: (c-set-style "gnu")
269 : * End:
270 : */
|
