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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 Copyright (c) 2005 Eliot Dresselhaus
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:
26 The above copyright notice and this permission notice shall be
27 included in all copies or substantial portions of the Software.
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.
38 /* This is all stolen from Bob Jenkins and reworked for clib. Thanks
39 once again Bob for the great work. */
42 ------------------------------------------------------------------------------
43 perfect.c: code to generate code for a hash for perfect hashing.
44 (c) Bob Jenkins, September 1996, December 1999
45 You may use this code in any way you wish, and it is free. No warranty.
46 I hereby place this in the public domain.
47 Source is http://burtleburtle.net/bob/c/perfect.c
49 This generates a minimal perfect hash function. That means, given a
50 set of n keys, this determines a hash function that maps each of
51 those keys into a value in 0..n-1 with no collisions.
53 The perfect hash function first uses a normal hash function on the key
54 to determine (a,b) such that the pair (a,b) is distinct for all
55 keys, then it computes a^scramble[tab[b]] to get the final perfect hash.
56 tab[] is an array of 1-byte values and scramble[] is a 256-term array of
57 2-byte or 4-byte values. If there are n keys, the length of tab[] is a
58 power of two between n/3 and n.
60 I found the idea of computing distinct (a,b) values in "Practical minimal
61 perfect hash functions for large databases", Fox, Heath, Chen, and Daoud,
62 Communications of the ACM, January 1992. They found the idea in Chichelli
63 (CACM Jan 1980). Beyond that, our methods differ.
65 The key is hashed to a pair (a,b) where a in 0..*alen*-1 and b in
66 0..*blen*-1. A fast hash function determines both a and b
67 simultaneously. Any decent hash function is likely to produce
68 hashes so that (a,b) is distinct for all pairs. I try the hash
69 using different values of *salt* until all pairs are distinct.
71 The final hash is (a XOR scramble[tab[b]]). *scramble* is a
72 predetermined mapping of 0..255 into 0..smax-1. *tab* is an
73 array that we fill in in such a way as to make the hash perfect.
75 First we fill in all values of *tab* that are used by more than one
76 key. We try all possible values for each position until one works.
78 This leaves m unmapped keys and m values that something could hash to.
79 If you treat unmapped keys as lefthand nodes and unused hash values
80 as righthand nodes, and draw a line connecting each key to each hash
81 value it could map to, you get a bipartite graph. We attempt to
82 find a perfect matching in this graph. If we succeed, we have
83 determined a perfect hash for the whole set of keys.
85 *scramble* is used because (a^tab[i]) clusters keys around *a*.
86 ------------------------------------------------------------------------------
89 #include <vppinfra/bitmap.h>
90 #include <vppinfra/format.h>
91 #include <vppinfra/phash.h>
92 #include <vppinfra/random.h>
94 static void init_keys_direct_u32 (phash_main_t * pm)
96 int n_keys_left, b_mask, a_shift;
100 seed = pm->hash_seed;
101 b_mask = (1 << pm->b_bits) - 1;
102 a_shift = BITS (seed) - pm->a_bits;
105 n_keys_left = vec_len (pm->keys);
107 while (n_keys_left >= 2)
114 x0 += (u32) k[0].key;
115 x1 += (u32) k[1].key;
117 hash_mix32 (x0, y0, z0);
118 hash_mix32 (x1, y1, z1);
120 k[0].b = z0 & b_mask;
121 k[1].b = z1 & b_mask;
122 k[0].a = z0 >> a_shift;
123 k[1].a = z1 >> a_shift;
124 if (PREDICT_FALSE (a_shift >= BITS (z0)))
131 if (n_keys_left >= 1)
138 hash_mix32 (x0, y0, z0);
140 k[0].b = z0 & b_mask;
141 k[0].a = z0 >> a_shift;
142 if (PREDICT_FALSE (a_shift >= BITS (z0)))
150 static void init_keys_direct_u64 (phash_main_t * pm)
152 int n_keys_left, b_mask, a_shift;
156 seed = pm->hash_seed;
157 b_mask = (1 << pm->b_bits) - 1;
158 a_shift = BITS (seed) - pm->a_bits;
161 n_keys_left = vec_len (pm->keys);
163 while (n_keys_left >= 2)
170 x0 += (u64) k[0].key;
171 x1 += (u64) k[1].key;
173 hash_mix64 (x0, y0, z0);
174 hash_mix64 (x1, y1, z1);
176 k[0].b = z0 & b_mask;
177 k[1].b = z1 & b_mask;
178 k[0].a = z0 >> a_shift;
179 k[1].a = z1 >> a_shift;
180 if (PREDICT_FALSE (a_shift >= BITS (z0)))
187 if (n_keys_left >= 1)
194 hash_mix64 (x0, y0, z0);
196 k[0].b = z0 & b_mask;
197 k[0].a = z0 >> a_shift;
198 if (PREDICT_FALSE (a_shift >= BITS (z0)))
206 static void init_keys_indirect_u32 (phash_main_t * pm)
208 int n_keys_left, b_mask, a_shift;
212 seed = pm->hash_seed;
213 b_mask = (1 << pm->b_bits) - 1;
214 a_shift = BITS (seed) - pm->a_bits;
217 n_keys_left = vec_len (pm->keys);
219 while (n_keys_left >= 2)
225 pm->key_seed2 (pm->private, k[0].key, k[1].key, &xyz);
229 x0 += xyz[0]; y0 += xyz[1]; z0 += xyz[2];
230 x1 += xyz[3]; y1 += xyz[4]; z1 += xyz[5];
232 hash_mix32 (x0, y0, z0);
233 hash_mix32 (x1, y1, z1);
235 k[0].b = z0 & b_mask;
236 k[1].b = z1 & b_mask;
237 k[0].a = z0 >> a_shift;
238 k[1].a = z1 >> a_shift;
239 if (PREDICT_FALSE (a_shift >= BITS (z0)))
246 if (n_keys_left >= 1)
251 pm->key_seed1 (pm->private, k[0].key, &xyz);
254 x0 += xyz[0]; y0 += xyz[1]; z0 += xyz[2];
256 hash_mix32 (x0, y0, z0);
258 k[0].b = z0 & b_mask;
259 k[0].a = z0 >> a_shift;
260 if (PREDICT_FALSE (a_shift >= BITS (z0)))
268 static void init_keys_indirect_u64 (phash_main_t * pm)
270 int n_keys_left, b_mask, a_shift;
274 seed = pm->hash_seed;
275 b_mask = (1 << pm->b_bits) - 1;
276 a_shift = BITS (seed) - pm->a_bits;
279 n_keys_left = vec_len (pm->keys);
281 while (n_keys_left >= 2)
287 pm->key_seed2 (pm->private, k[0].key, k[1].key, &xyz);
291 x0 += xyz[0]; y0 += xyz[1]; z0 += xyz[2];
292 x1 += xyz[3]; y1 += xyz[4]; z1 += xyz[5];
294 hash_mix64 (x0, y0, z0);
295 hash_mix64 (x1, y1, z1);
297 k[0].b = z0 & b_mask;
298 k[1].b = z1 & b_mask;
299 k[0].a = z0 >> a_shift;
300 k[1].a = z1 >> a_shift;
301 if (PREDICT_FALSE (a_shift >= BITS (z0)))
308 if (n_keys_left >= 1)
313 pm->key_seed1 (pm->private, k[0].key, &xyz);
316 x0 += xyz[0]; y0 += xyz[1]; z0 += xyz[2];
318 hash_mix64 (x0, y0, z0);
320 k[0].b = z0 & b_mask;
321 k[0].a = z0 >> a_shift;
322 if (PREDICT_FALSE (a_shift >= BITS (z0)))
331 * insert keys into table according to key->b
332 * check if the initial hash might work
334 static int init_tabb (phash_main_t * pm)
338 phash_key_t * k, * l;
342 if (pm->flags & PHASH_FLAG_MIX64)
343 init_keys_indirect_u64 (pm);
345 init_keys_indirect_u32 (pm);
349 if (pm->flags & PHASH_FLAG_MIX64)
350 init_keys_direct_u64 (pm);
352 init_keys_direct_u32 (pm);
356 vec_resize (pm->tabb, 1 << pm->b_bits);
358 vec_foreach (tb, pm->tabb)
359 phash_tabb_free (tb);
361 /* Two keys with the same (a,b) guarantees a collision */
363 vec_foreach (k, pm->keys)
367 tb = pm->tabb + k->b;
369 for (i = 0; i < vec_len (ki); i++)
371 l = pm->keys + ki[i];
374 /* Given keys are supposed to be unique. */
376 && pm->key_is_equal (pm->private, l->key, k->key))
377 clib_error ("duplicate keys");
383 vec_add1 (tb->keys, k - pm->keys);
387 return no_collisions;
390 /* Try to apply an augmenting list */
391 static int apply (phash_main_t * pm, u32 tail, u32 rollback)
395 phash_tabq_t * q_child, * q_parent;
396 u32 ki, i, hash, child, parent;
397 u32 stabb; /* scramble[tab[b]] */
402 /* Walk from child to parent until root is reached. */
403 for (child = tail - 1; child; child = parent)
405 q_child = &pm->tabq[child];
406 parent = q_child->parent_q;
407 q_parent = &pm->tabq[parent];
409 /* find parent's list of siblings */
410 ASSERT (q_parent->b_q < vec_len (pm->tabb));
411 pb = pm->tabb + q_parent->b_q;
413 /* erase old hash values */
414 stabb = pm->scramble[pb->val_b];
415 for (i = 0; i < vec_len (pb->keys); i++)
421 /* Erase hash for all of child's siblings. */
422 if (ki == pm->tabh[hash])
426 /* change pb->val_b, which will change the hashes of all parent siblings */
427 pb->val_b = rollback ? q_child->oldval_q : q_child->newval_q;
429 /* set new hash values */
430 stabb = pm->scramble[pb->val_b];
431 for (i = 0; i < vec_len (pb->keys); i++)
439 if (parent == 0) continue; /* root never had a hash */
441 else if (pm->tabh[hash] != ~0)
443 /* Very rare case: roll back any changes. */
444 apply (pm, tail, /* rollback changes */ 1);
458 -------------------------------------------------------------------------------
459 augment(): Add item to the mapping.
461 Construct a spanning tree of *b*s with *item* as root, where each
462 parent can have all its hashes changed (by some new val_b) with
463 at most one collision, and each child is the b of that collision.
465 I got this from Tarjan's "Data Structures and Network Algorithms". The
466 path from *item* to a *b* that can be remapped with no collision is
467 an "augmenting path". Change values of tab[b] along the path so that
468 the unmapped key gets mapped and the unused hash value gets used.
470 Assuming 1 key per b, if m out of n hash values are still unused,
471 you should expect the transitive closure to cover n/m nodes before
472 an unused node is found. Sum(i=1..n)(n/i) is about nlogn, so expect
473 this approach to take about nlogn time to map all single-key b's.
474 -------------------------------------------------------------------------------
476 high_water: a value higher than any now in tabb[].water_b.
478 static int augment (phash_main_t * pm, u32 b_root, u32 high_water)
480 u32 q; /* current position walking through the queue */
481 u32 tail; /* tail of the queue. 0 is the head of the queue. */
482 phash_tabb_t * tb_parent, * tb_child, * tb_hit;
483 phash_key_t * k_parent, * k_child;
484 u32 v, v_limit; /* possible value for myb->val_b */
487 v_limit = 1 << ((pm->flags & PHASH_FLAG_USE_SCRAMBLE) ? pm->s_bits : BITS (u8));
489 /* Initialize the root of the spanning tree. */
490 pm->tabq[0].b_q = b_root;
493 /* construct the spanning tree by walking the queue, add children to tail */
494 for (q = 0; q < tail; q++)
496 if ((pm->flags & PHASH_FLAG_FAST_MODE)
497 && ! (pm->flags & PHASH_FLAG_MINIMAL)
499 break; /* don't do transitive closure */
501 tb_parent = pm->tabb + pm->tabq[q].b_q; /* the b for this node */
503 for (v = 0; v < v_limit; v++)
507 for (i = 0; i < vec_len (tb_parent->keys); i++)
509 ki = tb_parent->keys[i];
510 k_parent = pm->keys + ki;
512 hash = k_parent->a ^ pm->scramble[v];
513 if (hash >= pm->hash_max)
514 goto try_next_v; /* hash code out of bounds => we can't use this v */
520 k_child = pm->keys + ki;
521 tb_hit = pm->tabb + k_child->b;
525 /* Hit at most one child b. */
526 if (tb_child == tb_hit)
531 /* Remember this as child b. */
533 if (tb_hit->water_b == high_water)
534 goto try_next_v; /* already explored */
538 /* tb_parent with v has either one or zero collisions. */
540 /* add childb to the queue of reachable things */
542 tb_child->water_b = high_water;
543 pm->tabq[tail].b_q = tb_child ? tb_child - pm->tabb : ~0;
544 pm->tabq[tail].newval_q = v; /* how to make parent (myb) use this hash */
545 pm->tabq[tail].oldval_q = tb_parent->val_b; /* need this for rollback */
546 pm->tabq[tail].parent_q = q;
549 /* Found a v with no collisions? */
552 /* Try to apply the augmenting path. */
553 if (apply (pm, tail, /* rollback */ 0))
554 return 1; /* success, item was added to the perfect hash */
555 --tail; /* don't know how to handle such a child! */
566 static phash_tabb_t * sort_tabb;
568 static int phash_tabb_compare (void *a1, void *a2)
572 phash_tabb_t * tb1, * tb2;
574 tb1 = sort_tabb + b1[0];
575 tb2 = sort_tabb + b2[0];
577 return ((int) vec_len (tb2->keys) - (int) vec_len(tb1->keys));
580 /* find a mapping that makes this a perfect hash */
581 static int perfect (phash_main_t * pm)
585 /* clear any state from previous attempts */
586 if (vec_bytes(pm->tabh))
587 memset (pm->tabh, ~0, vec_bytes (pm->tabh));
589 vec_validate (pm->tabb_sort, vec_len (pm->tabb) - 1);
590 for (i = 0; i < vec_len (pm->tabb_sort); i++)
591 pm->tabb_sort[i] = i;
593 sort_tabb = pm->tabb;
595 vec_sort_with_function (pm->tabb_sort, phash_tabb_compare);
597 /* In descending order by number of keys, map all *b*s */
598 for (i = 0; i < vec_len (pm->tabb_sort); i++)
600 if (! augment(pm, pm->tabb_sort[i], i + 1))
604 /* Success! We found a perfect hash of all keys into 0..nkeys-1. */
610 * Find initial a_bits = log2 (a_max), b_bits = log2 (b_max).
611 * Initial a_max and b_max values were found empirically. Some factors:
613 * If s_max<256 there is no scramble, so tab[b] needs to cover 0..s_max-1.
615 * a_max and b_max must be powers of 2 because the values in 0..a_max-1 and
616 * 0..b_max-1 are produced by applying a bitmask to the initial hash function.
618 * a_max must be less than s_max, in fact less than n_keys, because otherwise
619 * there would often be no i such that a^scramble[i] is in 0..n_keys-1 for
620 * all the *a*s associated with a given *b*, so there would be no legal
621 * value to assign to tab[b]. This only matters when we're doing a minimal
624 * It takes around 800 trials to find distinct (a,b) with nkey=s_max*(5/8)
625 * and a_max*b_max = s_max*s_max/32.
627 * Values of b_max less than s_max/4 never work, and s_max/2 always works.
629 * We want b_max as small as possible because it is the number of bytes in
630 * the huge array we must create for the perfect hash.
632 * When nkey <= s_max*(5/8), b_max=s_max/4 works much more often with
633 * a_max=s_max/8 than with a_max=s_max/4. Above s_max*(5/8), b_max=s_max/4
634 * doesn't seem to care whether a_max=s_max/8 or a_max=s_max/4. I think it
635 * has something to do with 5/8 = 1/8 * 5. For example examine 80000,
636 * 85000, and 90000 keys with different values of a_max. This only matters
637 * if we're doing a minimal perfect hash.
639 * When a_max*b_max <= 1<<U32BITS, the initial hash must produce one integer.
640 * Bigger than that it must produce two integers, which increases the
641 * cost of the hash per character hashed.
643 static void guess_initial_parameters (phash_main_t * pm)
645 u32 s_bits, s_max, a_max, b_max, n_keys;
646 int is_minimal, is_fast_mode;
647 const u32 b_max_use_scramble_threshold = 4096;
649 is_minimal = (pm->flags & PHASH_FLAG_MINIMAL) != 0;
650 is_fast_mode = (pm->flags & PHASH_FLAG_FAST_MODE) != 0;
652 n_keys = vec_len (pm->keys);
653 s_bits = max_log2 (n_keys);
664 case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8:
665 a_max = is_minimal ? s_max / 2 : s_max;
668 case 9: case 10: case 11: case 12: case 13:
669 case 14: case 15: case 16: case 17:
675 else if (s_max/4 < b_max_use_scramble_threshold)
677 if (n_keys <= s_max*0.52)
678 a_max = b_max = s_max/8;
680 a_max = b_max = s_max/4;
684 a_max = ((n_keys <= s_max*(5.0/8.0)) ? s_max/8 :
685 (n_keys <= s_max*(3.0/4.0)) ? s_max/4 : s_max/2);
686 b_max = s_max/4; /* always give the small size a shot */
691 a_max = b_max = s_max/2;
694 a_max = s_max/8; /* never require the multiword hash */
695 b_max = (n_keys <= s_max*(5.0/8.0)) ? s_max/4 : s_max/2;
700 a_max = (n_keys <= s_max*(5.0/8.0)) ? s_max/8 : s_max/2;
701 b_max = (n_keys <= s_max*(5.0/8.0)) ? s_max/4 : s_max/2;
704 /* Just find a hash as quick as possible.
705 We'll be thrashing virtual memory at this size. */
706 a_max = b_max = s_max/2;
712 /* Non-minimal perfect hash. */
713 if (is_fast_mode && n_keys > s_max*0.8)
719 if (s_max/4 <= (1 << 14))
720 b_max = ((n_keys <= s_max*0.56) ? s_max/32 :
721 (n_keys <= s_max*0.74) ? s_max/16 : s_max/8);
723 b_max = ((n_keys <= s_max*0.6) ? s_max/16 :
724 (n_keys <= s_max*0.8) ? s_max/8 : s_max/4);
726 if (is_fast_mode && b_max < s_max/8)
729 if (a_max < 1) a_max = 1;
730 if (b_max < 1) b_max = 1;
733 ASSERT (s_max == (1 << s_bits));
734 ASSERT (is_pow2 (a_max));
735 ASSERT (is_pow2 (b_max));
737 pm->a_bits = min_log2 (a_max);
738 pm->b_bits = min_log2 (b_max);
739 if (b_max >= b_max_use_scramble_threshold)
740 pm->flags |= PHASH_FLAG_USE_SCRAMBLE;
743 /* compute p(x), where p is a permutation of 0..(1<<nbits)-1 */
744 /* permute(0)=0. This is intended and useful. */
745 always_inline u32 scramble_permute (u32 x, u32 nbits)
748 int mask = (1 << nbits) - 1;
749 int const2 = 1+nbits/2;
750 int const3 = 1+nbits/3;
751 int const4 = 1+nbits/4;
752 int const5 = 1+nbits/5;
753 for (i = 0; i < 20; i++)
755 x = (x + (x << const2)) & mask;
756 x = (x ^ (x >> const3));
757 x = (x + (x << const4)) & mask;
758 x = (x ^ (x >> const5));
763 /* initialize scramble[] with distinct random values in 0..smax-1 */
764 static void scramble_init (phash_main_t * pm)
768 /* fill scramble[] with distinct random integers in 0..smax-1 */
769 vec_validate (pm->scramble, (1 << (pm->s_bits < 8 ? 8 : pm->s_bits)) - 1);
770 for (i = 0; i < vec_len (pm->scramble); i++)
771 pm->scramble[i] = scramble_permute (i, pm->s_bits);
774 /* Try to find a perfect hash function. */
776 phash_find_perfect_hash (phash_main_t * pm)
778 clib_error_t * error = 0;
779 u32 max_a_bits, n_tries_this_a_b, want_minimal;
781 /* guess initial values for s_max, a_max and b_max */
782 guess_initial_parameters (pm);
784 want_minimal = pm->flags & PHASH_FLAG_MINIMAL;
788 pm->a_bits = pm->s_bits;
790 max_a_bits = pm->s_bits - want_minimal;
794 pm->hash_max = want_minimal ? vec_len (pm->keys) : (1 << pm->s_bits);
798 /* Allocate working memory. */
800 vec_validate_init_empty (pm->tabh, pm->hash_max - 1, ~0);
802 vec_validate (pm->tabq, 1 << pm->b_bits);
804 /* Actually find the perfect hash */
805 n_tries_this_a_b = 0;
808 /* Choose random hash seeds until keys become unique. */
809 pm->hash_seed = random_u64 (&pm->random_seed);
813 /* Found unique (A, B). */
815 /* Hash may already be perfect. */
819 pm->n_perfect_calls++;
826 /* Keep trying with different seed value. */
828 if (n_tries_this_a_b < 2048)
831 /* Try to put more bits in (A,B) to make distinct (A,B) more likely */
832 if (pm->a_bits < max_a_bits)
834 else if (pm->b_bits < pm->s_bits)
837 vec_resize (pm->tabb, vec_len (pm->tabb));
838 vec_resize (pm->tabq, vec_len (pm->tabq));
843 /* Can't increase (A, B) any more, so try increasing S. */
849 /* Construct mapping table for hash lookups. */
854 pm->a_shift = ((pm->flags & PHASH_FLAG_MIX64) ? 64 : 32) - pm->a_bits;
855 pm->b_mask = (1 << pm->b_bits) - 1;
857 vec_resize (pm->tab, vec_len (pm->tabb));
858 for (b = 0; b < vec_len (pm->tabb); b++)
860 v = pm->tabb[b].val_b;
862 /* Apply scramble now for small enough value of b_bits. */
863 if (! (pm->flags & PHASH_FLAG_USE_SCRAMBLE))
870 /* Free working memory. */
871 phash_main_free_working_memory (pm);
876 /* Slow hash computation for general keys. */
877 uword phash_hash_slow (phash_main_t * pm, uword key)
881 if (pm->flags & PHASH_FLAG_MIX64)
885 x0 = y0 = z0 = pm->hash_seed;
890 pm->key_seed1 (pm->private, key, &xyz);
891 x0 += xyz[0]; y0 += xyz[1]; z0 += xyz[2];
896 hash_mix64 (x0, y0, z0);
898 a = z0 >> pm->a_shift;
905 x0 = y0 = z0 = pm->hash_seed;
910 pm->key_seed1 (pm->private, key, &xyz);
911 x0 += xyz[0]; y0 += xyz[1]; z0 += xyz[2];
916 hash_mix32 (x0, y0, z0);
918 a = z0 >> pm->a_shift;
923 if (pm->flags & PHASH_FLAG_USE_SCRAMBLE)
928 /* Verify that perfect hash is perfect. */
930 phash_validate (phash_main_t * pm)
933 uword * unique_bitmap = 0;
934 clib_error_t * error = 0;
936 vec_foreach (k, pm->keys)
938 uword h = phash_hash_slow (pm, k->key);
940 if (h >= pm->hash_max)
942 error = clib_error_return (0, "hash out of range %wd", h);
946 if (clib_bitmap_get (unique_bitmap, h))
948 error = clib_error_return (0, "hash non-unique");
952 unique_bitmap = clib_bitmap_ori (unique_bitmap, h);
956 clib_bitmap_free (unique_bitmap);