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) 2001, 2002, 2003 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_clib_vec_bootstrap_h
39 : #define included_clib_vec_bootstrap_h
40 :
41 : /** \file
42 : Vector bootstrap header file
43 : */
44 :
45 : /* Bootstrap include so that #include <vppinfra/mem.h> can include e.g.
46 : <vppinfra/mheap.h> which depends on <vppinfra/vec.h>. */
47 :
48 : /** \brief vector header structure
49 :
50 : Bookkeeping header preceding vector elements in memory.
51 : User header information may preceed standard vec header.
52 : If you change u32 len -> u64 len, single vectors can
53 : exceed 2**32 elements. Clib heaps are vectors. */
54 :
55 : typedef struct
56 : {
57 : u32 len; /**< Number of elements in vector (NOT its allocated length). */
58 : u8 hdr_size; /**< header size divided by VEC_MIN_ALIGN */
59 : u8 log2_align : 7; /**< data alignment */
60 : u8 default_heap : 1; /**< vector uses default heap */
61 : u8 grow_elts; /**< number of elts vector can grow without realloc */
62 : u8 vpad[1]; /**< pad to 8 bytes */
63 : u8 vector_data[0]; /**< Vector data . */
64 : } vec_header_t;
65 :
66 : #define VEC_MIN_ALIGN 8
67 :
68 : /** \brief Find the vector header
69 :
70 : Given the user's pointer to a vector, find the corresponding
71 : vector header
72 :
73 : @param v pointer to a vector
74 : @return pointer to the vector's vector_header_t
75 : */
76 : #define _vec_find(v) ((vec_header_t *) (v) - 1)
77 : #define _vec_heap(v) (((void **) (_vec_find (v)))[-1])
78 :
79 : always_inline uword __vec_align (uword data_align, uword configuered_align);
80 : always_inline uword __vec_elt_sz (uword elt_sz, int is_void);
81 :
82 : #define _vec_round_size(s) \
83 : (((s) + sizeof (uword) - 1) &~ (sizeof (uword) - 1))
84 : #define _vec_is_void(P) \
85 : __builtin_types_compatible_p (__typeof__ ((P)[0]), void)
86 : #define _vec_elt_sz(V) __vec_elt_sz (sizeof ((V)[0]), _vec_is_void (V))
87 : #define _vec_align(V, A) __vec_align (__alignof__((V)[0]), A)
88 :
89 : always_inline __clib_nosanitize_addr uword
90 13168479911 : vec_get_header_size (void *v)
91 : {
92 13168479911 : uword header_size = _vec_find (v)->hdr_size * VEC_MIN_ALIGN;
93 13168479911 : return header_size;
94 : }
95 :
96 : /** \brief Find a user vector header
97 :
98 : Finds the user header of a vector with unspecified alignment given
99 : the user pointer to the vector.
100 : */
101 :
102 : always_inline void *
103 10307114093 : vec_header (void *v)
104 : {
105 10307114093 : return v ? v - vec_get_header_size (v) : 0;
106 : }
107 :
108 : /** \brief Find the end of user vector header
109 :
110 : Finds the end of the user header of a vector with unspecified
111 : alignment given the user pointer to the vector.
112 : */
113 :
114 : always_inline void *
115 : vec_header_end (void *v)
116 : {
117 : return v + vec_get_header_size (v);
118 : }
119 :
120 : /** \brief Number of elements in vector (rvalue-only, NULL tolerant)
121 :
122 : vec_len (v) checks for NULL, but cannot be used as an lvalue.
123 : If in doubt, use vec_len...
124 : */
125 :
126 : static_always_inline u32
127 76656412995 : __vec_len (void *v)
128 : {
129 76656412995 : return _vec_find (v)->len;
130 : }
131 :
132 : #define _vec_len(v) __vec_len ((void *) (v))
133 : #define vec_len(v) ((v) ? _vec_len(v) : 0)
134 :
135 : u32 vec_len_not_inline (void *v);
136 :
137 : /** \brief Number of data bytes in vector. */
138 :
139 : #define vec_bytes(v) (vec_len (v) * sizeof (v[0]))
140 :
141 : /**
142 : * Return size of memory allocated for the vector
143 : *
144 : * @param v vector
145 : * @return memory size allocated for the vector
146 : */
147 :
148 : uword vec_mem_size (void *v);
149 :
150 : /**
151 : * Number of elements that can fit into generic vector
152 : *
153 : * @param v vector
154 : * @param b extra header bytes
155 : * @return number of elements that can fit into vector
156 : */
157 :
158 : always_inline uword
159 1486058919 : vec_max_bytes (void *v)
160 : {
161 1486058919 : return v ? vec_mem_size (v) - vec_get_header_size (v) : 0;
162 : }
163 :
164 : always_inline uword
165 1486061724 : _vec_max_len (void *v, uword elt_sz)
166 : {
167 1486061724 : return vec_max_bytes (v) / elt_sz;
168 : }
169 :
170 : #define vec_max_len(v) _vec_max_len (v, _vec_elt_sz (v))
171 :
172 : static_always_inline void
173 1624357163 : _vec_set_grow_elts (void *v, uword n_elts)
174 : {
175 1624357163 : uword max = pow2_mask (BITS (_vec_find (0)->grow_elts));
176 :
177 1624120433 : if (PREDICT_FALSE (n_elts > max))
178 106130586 : n_elts = max;
179 :
180 1624120433 : _vec_find (v)->grow_elts = n_elts;
181 1624120433 : }
182 :
183 : always_inline void
184 1485321365 : _vec_set_len (void *v, uword len, uword elt_sz)
185 : {
186 1485321365 : ASSERT (v);
187 1485321365 : ASSERT (len <= _vec_max_len (v, elt_sz));
188 1484945082 : uword old_len = _vec_len (v);
189 1484757658 : uword grow_elts = _vec_find (v)->grow_elts;
190 :
191 1484757658 : if (len > old_len)
192 496682928 : clib_mem_unpoison (v + old_len * elt_sz, (len - old_len) * elt_sz);
193 988075801 : else if (len < old_len)
194 74059196 : clib_mem_poison (v + len * elt_sz, (old_len - len) * elt_sz);
195 :
196 1484756054 : _vec_set_grow_elts (v, old_len + grow_elts - len);
197 1484497140 : _vec_find (v)->len = len;
198 1484497140 : }
199 :
200 : #define vec_set_len(v, l) _vec_set_len ((void *) v, l, _vec_elt_sz (v))
201 : #define vec_inc_len(v, l) vec_set_len (v, _vec_len (v) + (l))
202 : #define vec_dec_len(v, l) vec_set_len (v, _vec_len (v) - (l))
203 :
204 : /** \brief Reset vector length to zero
205 : NULL-pointer tolerant
206 : */
207 : #define vec_reset_length(v) do { if (v) vec_set_len (v, 0); } while (0)
208 :
209 : /** \brief End (last data address) of vector. */
210 : #define vec_end(v) ((v) + vec_len (v))
211 :
212 : /** \brief True if given pointer is within given vector. */
213 : #define vec_is_member(v,e) ((e) >= (v) && (e) < vec_end (v))
214 :
215 : /** \brief Get vector value at index i checking that i is in bounds. */
216 : #define vec_elt_at_index(v,i) \
217 : ({ \
218 : ASSERT ((i) < vec_len (v)); \
219 : (v) + (i); \
220 : })
221 :
222 : /** \brief Get vector value at index i */
223 : #define vec_elt(v,i) (vec_elt_at_index(v,i))[0]
224 :
225 : /** \brief Vector iterator */
226 : #define vec_foreach(var,vec) for (var = (vec); var < vec_end (vec); var++)
227 :
228 : /** \brief Vector iterator (reverse) */
229 : #define vec_foreach_backwards(var, vec) \
230 : if (vec) \
231 : for (var = vec_end (vec) - 1; var >= (vec); var--)
232 :
233 : /** \brief Iterate over vector indices. */
234 : #define vec_foreach_index(var,v) for ((var) = 0; (var) < vec_len (v); (var)++)
235 :
236 : /** \brief Iterate over vector indices (reverse). */
237 : #define vec_foreach_index_backwards(var, v) \
238 : if (v) \
239 : for ((var) = vec_len ((v)) - 1; (var) >= 0; (var)--)
240 :
241 : #define vec_foreach_pointer(e, v) \
242 : for (typeof (**v) **__ep = (v), *(e) = *__ep; __ep - (v) < vec_len (v); \
243 : __ep++, (e) = *__ep)
244 :
245 : #endif /* included_clib_vec_bootstrap_h */
246 :
247 : /*
248 : * fd.io coding-style-patch-verification: ON
249 : *
250 : * Local Variables:
251 : * eval: (c-set-style "gnu")
252 : * End:
253 : */
|
