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-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 : #include <vppinfra/hash.h>
39 : #include <vppinfra/error.h>
40 : #include <vppinfra/mem.h>
41 : #include <vppinfra/byte_order.h> /* for clib_arch_is_big_endian */
42 :
43 : always_inline void
44 236149 : zero_pair (hash_t * h, hash_pair_t * p)
45 : {
46 236149 : clib_memset (p, 0, hash_pair_bytes (h));
47 236149 : }
48 :
49 : always_inline void
50 50884100 : init_pair (hash_t * h, hash_pair_t * p)
51 : {
52 50884100 : clib_memset (p->value, ~0, hash_value_bytes (h));
53 50884100 : }
54 :
55 : always_inline hash_pair_union_t *
56 1528260000 : get_pair (void *v, uword i)
57 : {
58 1528260000 : hash_t *h = hash_header (v);
59 : hash_pair_t *p;
60 1528260000 : ASSERT (i < vec_len (v));
61 1528260000 : p = v;
62 1528260000 : p += i << h->log2_pair_size;
63 1528260000 : return (hash_pair_union_t *) p;
64 : }
65 :
66 : always_inline void
67 272295000 : set_is_user (void *v, uword i, uword is_user)
68 : {
69 272295000 : hash_t *h = hash_header (v);
70 272295000 : uword i0 = i / BITS (h->is_user[0]);
71 272295000 : uword i1 = (uword) 1 << (i % BITS (h->is_user[0]));
72 272295000 : if (is_user)
73 228692000 : h->is_user[i0] |= i1;
74 : else
75 43602700 : h->is_user[i0] &= ~i1;
76 272295000 : }
77 :
78 : static u8 *hash_format_pair_default (u8 * s, va_list * args);
79 :
80 : __clib_export uword
81 509073000 : hash_memory (void *p, word n_bytes, uword state)
82 : {
83 509073000 : uword last[3] = {};
84 509073000 : uwordu *q = p;
85 : u64 a, b, c, n;
86 :
87 509073000 : a = b = (uword_bits == 64) ? 0x9e3779b97f4a7c13LL : 0x9e3779b9;
88 509073000 : c = state;
89 509073000 : n = n_bytes;
90 :
91 764070000 : while (n >= 3 * sizeof (uword))
92 : {
93 254997000 : a += q[0];
94 254997000 : b += q[1];
95 254997000 : c += q[2];
96 254997000 : hash_mix (a, b, c);
97 254997000 : n -= 3 * sizeof (uword);
98 254997000 : q += 3;
99 : }
100 :
101 509073000 : c += n_bytes;
102 :
103 509073000 : if (n > 0)
104 : {
105 490996000 : clib_memcpy_fast (&last, q, n);
106 490996000 : a += last[0];
107 490996000 : b += last[1];
108 490996000 : c += last[2];
109 : }
110 :
111 509073000 : hash_mix (a, b, c);
112 :
113 509073000 : return c;
114 : }
115 :
116 : always_inline uword
117 771661000 : hash_uword (uword x)
118 : {
119 : uword a, b, c;
120 :
121 771661000 : a = b = (uword_bits == 64) ? 0x9e3779b97f4a7c13LL : 0x9e3779b9;
122 771661000 : c = 0;
123 771661000 : a += x;
124 771661000 : hash_mix (a, b, c);
125 771661000 : return c;
126 : }
127 :
128 : /* Call sum function. Hash code will be sum function value
129 : modulo the prime length of the hash table. */
130 : always_inline uword
131 1280700000 : key_sum (hash_t * h, uword key)
132 : {
133 : uword sum;
134 2561400000 : switch (pointer_to_uword ((void *) h->key_sum))
135 : {
136 771661000 : case KEY_FUNC_NONE:
137 771661000 : sum = hash_uword (key);
138 771661000 : break;
139 :
140 0 : case KEY_FUNC_POINTER_UWORD:
141 0 : sum = hash_uword (*uword_to_pointer (key, uword *));
142 0 : break;
143 :
144 0 : case KEY_FUNC_POINTER_U32:
145 0 : sum = hash_uword (*uword_to_pointer (key, u32 *));
146 0 : break;
147 :
148 500003000 : case KEY_FUNC_STRING:
149 500003000 : sum = string_key_sum (h, key);
150 500003000 : break;
151 :
152 0 : case KEY_FUNC_MEM:
153 0 : sum = mem_key_sum (h, key);
154 0 : break;
155 :
156 9039090 : default:
157 9039090 : sum = h->key_sum (h, key);
158 9039100 : break;
159 : }
160 :
161 1280700000 : return sum;
162 : }
163 :
164 : always_inline uword
165 1312720000 : key_equal1 (hash_t * h, uword key1, uword key2, uword e)
166 : {
167 2625440000 : switch (pointer_to_uword ((void *) h->key_equal))
168 : {
169 1008180000 : case KEY_FUNC_NONE:
170 1008180000 : break;
171 :
172 0 : case KEY_FUNC_POINTER_UWORD:
173 0 : e =
174 0 : *uword_to_pointer (key1, uword *) == *uword_to_pointer (key2,
175 : uword *);
176 0 : break;
177 :
178 0 : case KEY_FUNC_POINTER_U32:
179 0 : e = *uword_to_pointer (key1, u32 *) == *uword_to_pointer (key2, u32 *);
180 0 : break;
181 :
182 297435000 : case KEY_FUNC_STRING:
183 297435000 : e = string_key_equal (h, key1, key2);
184 297435000 : break;
185 :
186 0 : case KEY_FUNC_MEM:
187 0 : e = mem_key_equal (h, key1, key2);
188 0 : break;
189 :
190 7106190 : default:
191 7106190 : e = h->key_equal (h, key1, key2);
192 7106200 : break;
193 : }
194 1312720000 : return e;
195 : }
196 :
197 : /* Compares two keys: returns 1 if equal, 0 if not. */
198 : always_inline uword
199 1312720000 : key_equal (hash_t * h, uword key1, uword key2)
200 : {
201 1312720000 : uword e = key1 == key2;
202 1312720000 : if (CLIB_DEBUG > 0 && key1 == key2)
203 986892000 : ASSERT (key_equal1 (h, key1, key2, e));
204 1312720000 : if (!e)
205 325828000 : e = key_equal1 (h, key1, key2, e);
206 1312720000 : return e;
207 : }
208 :
209 : static hash_pair_union_t *
210 404137000 : get_indirect (void *v, hash_pair_indirect_t * pi, uword key)
211 : {
212 404137000 : hash_t *h = hash_header (v);
213 : hash_pair_t *p0, *p1;
214 :
215 404137000 : p0 = p1 = pi->pairs;
216 404137000 : if (h->log2_pair_size > 0)
217 403807000 : p1 = hash_forward (h, p0, indirect_pair_get_len (pi));
218 : else
219 330805 : p1 += vec_len (p0);
220 :
221 678886000 : while (p0 < p1)
222 : {
223 664819000 : if (key_equal (h, p0->key, key))
224 390070000 : return (hash_pair_union_t *) p0;
225 274749000 : p0 = hash_forward1 (h, p0);
226 : }
227 :
228 14067100 : return (hash_pair_union_t *) 0;
229 : }
230 :
231 : static hash_pair_union_t *
232 43370900 : set_indirect_is_user (void *v, uword i, hash_pair_union_t * p, uword key)
233 : {
234 43370900 : hash_t *h = hash_header (v);
235 : hash_pair_t *q;
236 43370900 : hash_pair_indirect_t *pi = &p->indirect;
237 43370900 : uword log2_bytes = 0;
238 :
239 43370900 : if (h->log2_pair_size == 0)
240 134582 : q = vec_new (hash_pair_t, 2);
241 : else
242 : {
243 43236300 : log2_bytes = 1 + hash_pair_log2_bytes (h);
244 43236300 : q = clib_mem_alloc (1ULL << log2_bytes);
245 : }
246 43370900 : clib_memcpy_fast (q, &p->direct, hash_pair_bytes (h));
247 :
248 43370900 : pi->pairs = q;
249 43370900 : if (h->log2_pair_size > 0)
250 43236300 : indirect_pair_set (pi, log2_bytes, 2);
251 :
252 43370900 : set_is_user (v, i, 0);
253 :
254 : /* First element is used by existing pair, second will be used by caller. */
255 43370900 : q = hash_forward1 (h, q);
256 43370900 : q->key = key;
257 43370900 : init_pair (h, q);
258 43370900 : return (hash_pair_union_t *) q;
259 : }
260 :
261 : static hash_pair_union_t *
262 214806000 : set_indirect (void *v, hash_pair_indirect_t * pi, uword key,
263 : uword * found_key)
264 : {
265 214806000 : hash_t *h = hash_header (v);
266 : hash_pair_t *new_pair;
267 : hash_pair_union_t *q;
268 :
269 214806000 : q = get_indirect (v, pi, key);
270 214806000 : if (q)
271 : {
272 207293000 : *found_key = 1;
273 207293000 : return q;
274 : }
275 :
276 7513200 : if (h->log2_pair_size == 0)
277 32369 : vec_add2 (pi->pairs, new_pair, 1);
278 : else
279 : {
280 : uword len, new_len, log2_bytes;
281 :
282 7480830 : len = indirect_pair_get_len (pi);
283 7480830 : log2_bytes = indirect_pair_get_log2_bytes (pi);
284 :
285 7480830 : new_len = len + 1;
286 7480830 : if (new_len * hash_pair_bytes (h) > (1ULL << log2_bytes))
287 : {
288 6674670 : pi->pairs = clib_mem_realloc (pi->pairs, 1ULL << (log2_bytes + 1));
289 6674670 : log2_bytes++;
290 : }
291 :
292 7480830 : indirect_pair_set (pi, log2_bytes, new_len);
293 7480830 : new_pair = pi->pairs + (len << h->log2_pair_size);
294 : }
295 7513200 : new_pair->key = key;
296 7513200 : init_pair (h, new_pair);
297 7513200 : *found_key = 0;
298 7513200 : return (hash_pair_union_t *) new_pair;
299 : }
300 :
301 : static void
302 34276 : unset_indirect (void *v, uword i, hash_pair_t * q)
303 : {
304 34276 : hash_t *h = hash_header (v);
305 34276 : hash_pair_union_t *p = get_pair (v, i);
306 : hash_pair_t *e;
307 34276 : hash_pair_indirect_t *pi = &p->indirect;
308 : uword len, is_vec;
309 :
310 34276 : is_vec = h->log2_pair_size == 0;
311 :
312 34276 : ASSERT (!hash_is_user (v, i));
313 34276 : len = is_vec ? vec_len (pi->pairs) : indirect_pair_get_len (pi);
314 34276 : e = hash_forward (h, pi->pairs, len - 1);
315 34276 : ASSERT (q >= pi->pairs && q <= e);
316 :
317 : /* We have two or fewer pairs and we are delete one pair.
318 : Make indirect pointer direct and free indirect memory. */
319 34276 : if (len <= 2)
320 : {
321 28059 : hash_pair_t *r = pi->pairs;
322 :
323 28059 : if (len == 2)
324 : {
325 28059 : clib_memcpy_fast (p, q == r ? hash_forward1 (h, r) : r,
326 : hash_pair_bytes (h));
327 28059 : set_is_user (v, i, 1);
328 : }
329 : else
330 0 : zero_pair (h, &p->direct);
331 :
332 28059 : if (is_vec)
333 0 : vec_free (r);
334 28059 : else if (r)
335 28059 : clib_mem_free (r);
336 : }
337 : else
338 : {
339 : /* If deleting a pair we need to keep non-null pairs together. */
340 6217 : if (q < e)
341 1900 : clib_memcpy_fast (q, e, hash_pair_bytes (h));
342 : else
343 4317 : zero_pair (h, q);
344 6217 : if (is_vec)
345 0 : vec_dec_len (pi->pairs, 1);
346 : else
347 6217 : indirect_pair_set (pi, indirect_pair_get_log2_bytes (pi), len - 1);
348 : }
349 34276 : }
350 :
351 : enum lookup_opcode
352 : {
353 : GET = 1,
354 : SET = 2,
355 : UNSET = 3,
356 : };
357 :
358 : static hash_pair_t *
359 1280700000 : lookup (void *v, uword key, enum lookup_opcode op,
360 : void *new_value, void *old_value)
361 : {
362 1280700000 : hash_t *h = hash_header (v);
363 1280700000 : hash_pair_union_t *p = 0;
364 1280700000 : uword found_key = 0;
365 : uword value_bytes;
366 : uword i;
367 :
368 1280700000 : if (!v)
369 0 : return 0;
370 :
371 1280700000 : i = key_sum (h, key) & (_vec_len (v) - 1);
372 1280700000 : p = get_pair (v, i);
373 1280700000 : value_bytes = hash_value_bytes (h);
374 :
375 1280700000 : if (hash_is_user (v, i))
376 : {
377 647901000 : found_key = key_equal (h, p->direct.key, key);
378 647901000 : if (found_key)
379 : {
380 602407000 : if (op == UNSET)
381 : {
382 231832 : set_is_user (v, i, 0);
383 231832 : if (old_value && value_bytes)
384 256 : clib_memcpy_fast (old_value, p->direct.value, value_bytes);
385 231832 : zero_pair (h, &p->direct);
386 : }
387 : }
388 : else
389 : {
390 45494700 : if (op == SET)
391 43370900 : p = set_indirect_is_user (v, i, p, key);
392 : else
393 2123730 : p = 0;
394 : }
395 : }
396 : else
397 : {
398 632801000 : hash_pair_indirect_t *pi = &p->indirect;
399 :
400 632801000 : if (op == SET)
401 : {
402 443470000 : if (!pi->pairs)
403 : {
404 228664000 : p->direct.key = key;
405 228664000 : set_is_user (v, i, 1);
406 : }
407 : else
408 214806000 : p = set_indirect (v, pi, key, &found_key);
409 : }
410 : else
411 : {
412 189331000 : p = get_indirect (v, pi, key);
413 189331000 : found_key = p != 0;
414 189331000 : if (found_key && op == UNSET)
415 : {
416 34276 : if (old_value && value_bytes)
417 0 : clib_memcpy_fast (old_value, &p->direct.value, value_bytes);
418 :
419 34276 : unset_indirect (v, i, &p->direct);
420 :
421 : /* Nullify p (since it's just been deleted).
422 : Otherwise we might be tempted to play with it. */
423 34276 : p = 0;
424 : }
425 : }
426 : }
427 :
428 1280700000 : if (op == SET && p != 0 && value_bytes)
429 : {
430 : /* Save away old value for caller. */
431 879307000 : if (old_value && found_key)
432 0 : clib_memcpy_fast (old_value, &p->direct.value, value_bytes);
433 879307000 : clib_memcpy_fast (&p->direct.value, new_value, value_bytes);
434 : }
435 :
436 1280700000 : if (op == SET)
437 879963000 : h->elts += !found_key;
438 1280700000 : if (op == UNSET)
439 266246 : h->elts -= found_key;
440 :
441 1280700000 : return &p->direct;
442 : }
443 :
444 : /* Fetch value of key. */
445 : __clib_export uword *
446 399464000 : _hash_get (void *v, uword key)
447 : {
448 399464000 : hash_t *h = hash_header (v);
449 : hash_pair_t *p;
450 :
451 : /* Don't even search table if its empty. */
452 399464000 : if (!v || h->elts == 0)
453 1585680 : return 0;
454 :
455 397878000 : p = lookup (v, key, GET, 0, 0);
456 397878000 : if (!p)
457 6211430 : return 0;
458 391667000 : if (h->log2_pair_size == 0)
459 591375 : return &p->key;
460 : else
461 391075000 : return &p->value[0];
462 : }
463 :
464 : __clib_export hash_pair_t *
465 2595650 : _hash_get_pair (void *v, uword key)
466 : {
467 2595650 : return lookup (v, key, GET, 0, 0);
468 : }
469 :
470 : __clib_export hash_pair_t *
471 0 : hash_next (void *v, hash_next_t *hn)
472 : {
473 0 : hash_t *h = hash_header (v);
474 : hash_pair_t *p;
475 :
476 : while (1)
477 : {
478 0 : if (hn->i == 0 && hn->j == 0)
479 : {
480 : /* Save flags. */
481 0 : hn->f = h->flags;
482 :
483 : /* Prevent others from re-sizing hash table. */
484 0 : h->flags |=
485 : (HASH_FLAG_NO_AUTO_GROW
486 : | HASH_FLAG_NO_AUTO_SHRINK | HASH_FLAG_HASH_NEXT_IN_PROGRESS);
487 : }
488 0 : else if (hn->i >= hash_capacity (v))
489 : {
490 : /* Restore flags. */
491 0 : h->flags = hn->f;
492 0 : clib_memset (hn, 0, sizeof (hn[0]));
493 0 : return 0;
494 : }
495 :
496 0 : p = hash_forward (h, v, hn->i);
497 0 : if (hash_is_user (v, hn->i))
498 : {
499 0 : hn->i++;
500 0 : return p;
501 : }
502 : else
503 : {
504 0 : hash_pair_indirect_t *pi = (void *) p;
505 : uword n;
506 :
507 0 : if (h->log2_pair_size > 0)
508 0 : n = indirect_pair_get_len (pi);
509 : else
510 0 : n = vec_len (pi->pairs);
511 :
512 0 : if (hn->j >= n)
513 : {
514 0 : hn->i++;
515 0 : hn->j = 0;
516 : }
517 : else
518 0 : return hash_forward (h, pi->pairs, hn->j++);
519 : }
520 : }
521 : }
522 :
523 : /* Remove key from table. */
524 : __clib_export void *
525 266307 : _hash_unset (void *v, uword key, void *old_value)
526 : {
527 : hash_t *h;
528 :
529 266307 : if (!v)
530 61 : return v;
531 :
532 266246 : (void) lookup (v, key, UNSET, 0, old_value);
533 :
534 266246 : h = hash_header (v);
535 266246 : if (!(h->flags & HASH_FLAG_NO_AUTO_SHRINK))
536 : {
537 : /* Resize when 1/4 full. */
538 243141 : if (h->elts > 32 && 4 * (h->elts + 1) < vec_len (v))
539 97 : v = hash_resize (v, vec_len (v) / 2);
540 : }
541 :
542 266246 : return v;
543 : }
544 :
545 : __clib_export void *
546 1283150 : _hash_create (uword elts, hash_t * h_user)
547 : {
548 : hash_t *h;
549 : uword log2_pair_size;
550 : void *v;
551 1283150 : vec_attr_t va = { .hdr_sz = sizeof (h[0]), .align = sizeof (hash_pair_t) };
552 :
553 : /* Size of hash is power of 2 >= ELTS and larger than
554 : number of bits in is_user bitmap elements. */
555 1283150 : elts = clib_max (elts, BITS (h->is_user[0]));
556 1283150 : elts = 1ULL << max_log2 (elts);
557 :
558 1283150 : log2_pair_size = 1;
559 1283150 : if (h_user)
560 1283150 : log2_pair_size = h_user->log2_pair_size;
561 :
562 1283150 : va.elt_sz = (1 << log2_pair_size) * sizeof (hash_pair_t),
563 1283150 : v = _vec_alloc_internal (elts, &va);
564 1283150 : h = hash_header (v);
565 :
566 1283150 : if (h_user)
567 : {
568 1283150 : h[0] = h_user[0];
569 1283150 : h->is_user = 0;
570 : }
571 :
572 1283150 : vec_validate_aligned (
573 : h->is_user, ((elts / BITS (h->is_user[0])) * sizeof (h->is_user[0])) - 1,
574 : CLIB_CACHE_LINE_BYTES);
575 1283150 : h->log2_pair_size = log2_pair_size;
576 1283150 : h->elts = 0;
577 :
578 : /* Default flags to never shrinking hash tables.
579 : Shrinking tables can cause "jackpot" cases. */
580 1283150 : if (!h_user)
581 0 : h->flags = HASH_FLAG_NO_AUTO_SHRINK;
582 :
583 1283150 : if (!h->format_pair)
584 : {
585 922659 : h->format_pair = hash_format_pair_default;
586 922659 : h->format_pair_arg = 0;
587 : }
588 :
589 1283150 : return v;
590 : }
591 :
592 : __clib_export void *
593 330901 : _hash_free (void *v)
594 : {
595 330901 : hash_t *h = hash_header (v);
596 : hash_pair_union_t *p;
597 : uword i;
598 :
599 330901 : if (!v)
600 32791 : return v;
601 :
602 : /* We zero all freed memory in case user would be tempted to use it. */
603 331184000 : for (i = 0; i < hash_capacity (v); i++)
604 : {
605 330886000 : if (hash_is_user (v, i))
606 83365100 : continue;
607 247520000 : p = get_pair (v, i);
608 247520000 : if (h->log2_pair_size == 0)
609 345263 : vec_free (p->indirect.pairs);
610 247175000 : else if (p->indirect.pairs)
611 22762000 : clib_mem_free (p->indirect.pairs);
612 : }
613 :
614 298109 : vec_free (h->is_user);
615 298110 : vec_free_header (h);
616 :
617 298110 : return 0;
618 : }
619 :
620 : static void *
621 101578 : hash_resize_internal (void *old, uword new_size, uword free_old)
622 : {
623 : void *new;
624 : hash_pair_t *p;
625 :
626 101578 : new = 0;
627 101578 : if (new_size > 0)
628 : {
629 101578 : hash_t *h = old ? hash_header (old) : 0;
630 101578 : new = _hash_create (new_size, h);
631 : /* *INDENT-OFF* */
632 60415600 : hash_foreach_pair (p, old, {
633 : new = _hash_set3 (new, p->key, &p->value[0], 0);
634 : });
635 : /* *INDENT-ON* */
636 : }
637 :
638 101578 : if (free_old)
639 101578 : hash_free (old);
640 101578 : return new;
641 : }
642 :
643 : __clib_export void *
644 101578 : hash_resize (void *old, uword new_size)
645 : {
646 101578 : return hash_resize_internal (old, new_size, 1);
647 : }
648 :
649 : __clib_export void *
650 0 : hash_dup (void *old)
651 : {
652 0 : return hash_resize_internal (old, vec_len (old), 0);
653 : }
654 :
655 : __clib_export void *
656 879963000 : _hash_set3 (void *v, uword key, void *value, void *old_value)
657 : {
658 : hash_t *h;
659 :
660 879963000 : if (!v)
661 473629 : v = hash_create (0, sizeof (uword));
662 :
663 879963000 : h = hash_header (v);
664 879963000 : (void) lookup (v, key, SET, value, old_value);
665 :
666 879963000 : if (!(h->flags & HASH_FLAG_NO_AUTO_GROW))
667 : {
668 : /* Resize when 3/4 full. */
669 879963000 : if (4 * (h->elts + 1) > 3 * vec_len (v))
670 101481 : v = hash_resize (v, 2 * vec_len (v));
671 : }
672 :
673 879963000 : return v;
674 : }
675 :
676 : __clib_export uword
677 8537830 : vec_key_sum (hash_t * h, uword key)
678 : {
679 8537830 : void *v = uword_to_pointer (key, void *);
680 8537830 : return hash_memory (v, vec_len (v) * h->user, 0);
681 : }
682 :
683 : __clib_export uword
684 6852290 : vec_key_equal (hash_t * h, uword key1, uword key2)
685 : {
686 6852290 : void *v1 = uword_to_pointer (key1, void *);
687 6852290 : void *v2 = uword_to_pointer (key2, void *);
688 6852290 : uword l1 = vec_len (v1);
689 6852290 : uword l2 = vec_len (v2);
690 6852290 : return l1 == l2 && 0 == memcmp (v1, v2, l1 * h->user);
691 : }
692 :
693 : __clib_export u8 *
694 0 : vec_key_format_pair (u8 * s, va_list * args)
695 : {
696 0 : void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
697 0 : void *v = va_arg (*args, void *);
698 0 : hash_pair_t *p = va_arg (*args, hash_pair_t *);
699 0 : hash_t *h = hash_header (v);
700 0 : void *u = uword_to_pointer (p->key, void *);
701 : int i;
702 :
703 0 : switch (h->user)
704 : {
705 0 : case 1:
706 0 : s = format (s, "%v", u);
707 0 : break;
708 :
709 0 : case 2:
710 : {
711 0 : u16 *w = u;
712 0 : for (i = 0; i < vec_len (w); i++)
713 0 : s = format (s, "0x%x, ", w[i]);
714 0 : break;
715 : }
716 :
717 0 : case 4:
718 : {
719 0 : u32 *w = u;
720 0 : for (i = 0; i < vec_len (w); i++)
721 0 : s = format (s, "0x%x, ", w[i]);
722 0 : break;
723 : }
724 :
725 0 : case 8:
726 : {
727 0 : u64 *w = u;
728 0 : for (i = 0; i < vec_len (w); i++)
729 0 : s = format (s, "0x%Lx, ", w[i]);
730 0 : break;
731 : }
732 :
733 0 : default:
734 0 : s = format (s, "0x%U", format_hex_bytes, u, vec_len (u) * h->user);
735 0 : break;
736 : }
737 :
738 0 : if (hash_value_bytes (h) > 0)
739 0 : s = format (s, " -> 0x%wx", p->value[0]);
740 :
741 0 : return s;
742 : }
743 :
744 : __clib_export uword
745 343816 : mem_key_sum (hash_t * h, uword key)
746 : {
747 343816 : uword *v = uword_to_pointer (key, void *);
748 343816 : return hash_memory (v, h->user, 0);
749 : }
750 :
751 : __clib_export uword
752 192077 : mem_key_equal (hash_t * h, uword key1, uword key2)
753 : {
754 192077 : void *v1 = uword_to_pointer (key1, void *);
755 192077 : void *v2 = uword_to_pointer (key2, void *);
756 192077 : return v1 && v2 && 0 == memcmp (v1, v2, h->user);
757 : }
758 :
759 : uword
760 500003000 : string_key_sum (hash_t * h, uword key)
761 : {
762 500003000 : char *v = uword_to_pointer (key, char *);
763 500003000 : return hash_memory (v, strlen (v), 0);
764 : }
765 :
766 : uword
767 297435000 : string_key_equal (hash_t * h, uword key1, uword key2)
768 : {
769 297435000 : void *v1 = uword_to_pointer (key1, void *);
770 297435000 : void *v2 = uword_to_pointer (key2, void *);
771 297435000 : return v1 && v2 && 0 == strcmp (v1, v2);
772 : }
773 :
774 : u8 *
775 0 : string_key_format_pair (u8 * s, va_list * args)
776 : {
777 0 : void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
778 0 : void *v = va_arg (*args, void *);
779 0 : hash_pair_t *p = va_arg (*args, hash_pair_t *);
780 0 : hash_t *h = hash_header (v);
781 0 : void *u = uword_to_pointer (p->key, void *);
782 :
783 0 : s = format (s, "%s", u);
784 :
785 0 : if (hash_value_bytes (h) > 0)
786 : s =
787 0 : format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
788 : hash_value_bytes (h));
789 :
790 0 : return s;
791 : }
792 :
793 : static u8 *
794 0 : hash_format_pair_default (u8 * s, va_list * args)
795 : {
796 0 : void *CLIB_UNUSED (user_arg) = va_arg (*args, void *);
797 0 : void *v = va_arg (*args, void *);
798 0 : hash_pair_t *p = va_arg (*args, hash_pair_t *);
799 0 : hash_t *h = hash_header (v);
800 :
801 0 : s = format (s, "0x%08x", p->key);
802 0 : if (hash_value_bytes (h) > 0)
803 : s =
804 0 : format (s, " -> 0x%8U", format_hex_bytes, &p->value[0],
805 : hash_value_bytes (h));
806 0 : return s;
807 : }
808 :
809 : __clib_export uword
810 2 : hash_bytes (void *v)
811 : {
812 : uword i, bytes;
813 2 : hash_t *h = hash_header (v);
814 :
815 2 : if (!v)
816 0 : return 0;
817 :
818 2 : bytes = vec_mem_size (v);
819 :
820 130 : for (i = 0; i < hash_capacity (v); i++)
821 : {
822 128 : if (!hash_is_user (v, i))
823 : {
824 125 : hash_pair_union_t *p = get_pair (v, i);
825 125 : if (h->log2_pair_size > 0)
826 125 : bytes += 1 << indirect_pair_get_log2_bytes (&p->indirect);
827 : else
828 0 : bytes += vec_mem_size (p->indirect.pairs);
829 : }
830 : }
831 2 : return bytes;
832 : }
833 :
834 : __clib_export u8 *
835 0 : format_hash (u8 *s, va_list *va)
836 : {
837 0 : void *v = va_arg (*va, void *);
838 0 : int verbose = va_arg (*va, int);
839 : hash_pair_t *p;
840 0 : hash_t *h = hash_header (v);
841 : uword i;
842 :
843 0 : s = format (s, "hash %p, %wd elts, capacity %wd, %wd bytes used,\n",
844 : v, hash_elts (v), hash_capacity (v), hash_bytes (v));
845 :
846 : {
847 0 : uword *occupancy = 0;
848 :
849 : /* Count number of buckets with each occupancy. */
850 0 : for (i = 0; i < hash_capacity (v); i++)
851 : {
852 : uword j;
853 :
854 0 : if (hash_is_user (v, i))
855 : {
856 0 : j = 1;
857 : }
858 : else
859 : {
860 0 : hash_pair_union_t *p = get_pair (v, i);
861 0 : if (h->log2_pair_size > 0)
862 0 : j = indirect_pair_get_len (&p->indirect);
863 : else
864 0 : j = vec_len (p->indirect.pairs);
865 : }
866 :
867 0 : vec_validate (occupancy, j);
868 0 : occupancy[j]++;
869 : }
870 :
871 0 : s = format (s, " profile ");
872 0 : for (i = 0; i < vec_len (occupancy); i++)
873 0 : s = format (s, "%wd%c", occupancy[i],
874 0 : i + 1 == vec_len (occupancy) ? '\n' : ' ');
875 :
876 0 : s = format (s, " lookup # of compares: ");
877 0 : for (i = 1; i < vec_len (occupancy); i++)
878 0 : s = format (s, "%wd: .%03d%c", i,
879 0 : (1000 * i * occupancy[i]) / hash_elts (v),
880 0 : i + 1 == vec_len (occupancy) ? '\n' : ' ');
881 :
882 0 : vec_free (occupancy);
883 : }
884 :
885 0 : if (verbose)
886 : {
887 : /* *INDENT-OFF* */
888 0 : hash_foreach_pair (p, v, {
889 : s = format (s, " %U\n", h->format_pair, h->format_pair_arg, v, p);
890 : });
891 : /* *INDENT-ON* */
892 : }
893 :
894 0 : return s;
895 : }
896 :
897 : static uword
898 232432 : unformat_hash_string_internal (unformat_input_t * input,
899 : va_list * va, int is_vec)
900 : {
901 232432 : uword *hash = va_arg (*va, uword *);
902 232432 : int *result = va_arg (*va, int *);
903 232432 : u8 *string = 0;
904 : uword *p;
905 :
906 232432 : if (!unformat (input, is_vec ? "%v%_" : "%s%_", &string))
907 2288 : return 0;
908 :
909 460288 : p = hash_get_mem (hash, string);
910 230144 : if (p)
911 109732 : *result = *p;
912 :
913 230144 : vec_free (string);
914 230144 : return p ? 1 : 0;
915 : }
916 :
917 : __clib_export uword
918 232432 : unformat_hash_vec_string (unformat_input_t * input, va_list * va)
919 : {
920 232432 : return unformat_hash_string_internal (input, va, /* is_vec */ 1);
921 : }
922 :
923 : __clib_export uword
924 0 : unformat_hash_string (unformat_input_t * input, va_list * va)
925 : {
926 0 : return unformat_hash_string_internal (input, va, /* is_vec */ 0);
927 : }
928 :
929 : __clib_export clib_error_t *
930 0 : hash_validate (void *v)
931 : {
932 0 : hash_t *h = hash_header (v);
933 : uword i, j;
934 0 : uword *keys = 0;
935 0 : clib_error_t *error = 0;
936 :
937 : #define CHECK(x) if ((error = ERROR_ASSERT (x))) goto done;
938 :
939 0 : for (i = 0; i < hash_capacity (v); i++)
940 : {
941 0 : hash_pair_union_t *pu = get_pair (v, i);
942 :
943 0 : if (hash_is_user (v, i))
944 : {
945 0 : CHECK (pu->direct.key != 0);
946 0 : vec_add1 (keys, pu->direct.key);
947 : }
948 : else
949 : {
950 : hash_pair_t *p;
951 0 : hash_pair_indirect_t *pi = &pu->indirect;
952 : uword n;
953 :
954 0 : n = h->log2_pair_size > 0
955 0 : ? indirect_pair_get_len (pi) : vec_len (pi->pairs);
956 :
957 0 : for (p = pi->pairs; n-- > 0; p = hash_forward1 (h, p))
958 : {
959 : /* Assert key uniqueness. */
960 0 : for (j = 0; j < vec_len (keys); j++)
961 0 : CHECK (keys[j] != p->key);
962 0 : vec_add1 (keys, p->key);
963 : }
964 : }
965 : }
966 :
967 0 : CHECK (vec_len (keys) == h->elts);
968 :
969 0 : vec_free (keys);
970 0 : done:
971 0 : return error;
972 : }
973 :
974 : /*
975 : * fd.io coding-style-patch-verification: ON
976 : *
977 : * Local Variables:
978 : * eval: (c-set-style "gnu")
979 : * End:
980 : */
|
