summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/phash.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/vppinfra/phash.h')
-rw-r--r--src/vppinfra/phash.h194
1 files changed, 0 insertions, 194 deletions
diff --git a/src/vppinfra/phash.h b/src/vppinfra/phash.h
deleted file mode 100644
index 3dc59c724f7..00000000000
--- a/src/vppinfra/phash.h
+++ /dev/null
@@ -1,194 +0,0 @@
-/*
- * Copyright (c) 2015 Cisco and/or its affiliates.
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at:
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-/*
- Copyright (c) 2005 Eliot Dresselhaus
-
- Permission is hereby granted, free of charge, to any person obtaining
- a copy of this software and associated documentation files (the
- "Software"), to deal in the Software without restriction, including
- without limitation the rights to use, copy, modify, merge, publish,
- distribute, sublicense, and/or sell copies of the Software, and to
- permit persons to whom the Software is furnished to do so, subject to
- the following conditions:
-
- The above copyright notice and this permission notice shall be
- included in all copies or substantial portions of the Software.
-
- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
- MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
- NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
- LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
- OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
- WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-*/
-
-#ifndef included_phash_h
-#define included_phash_h
-
-#include <vppinfra/hash.h> /* for Bob's mixing functions */
-
-typedef struct
-{
- /* Maybe either pointer to vector or inline word. */
- uword key;
-
- /* Hash code (A, B). */
- u32 a, b;
-} phash_key_t;
-
-/* Table indexed by B. */
-typedef struct
-{
- /* Vector of key indices with this same value of B. */
- u32 *keys;
-
- /* hash=a^tabb[b].val_b */
- u32 val_b;
-
- /* High watermark of who has visited this map node. */
- u32 water_b;
-} phash_tabb_t;
-
-always_inline void
-phash_tabb_free (phash_tabb_t * b)
-{
- vec_free (b->keys);
- b->val_b = b->water_b = 0;
-}
-
-typedef struct
-{
- /* b that currently occupies this hash */
- u32 b_q;
-
- /* Queue position of parent that could use this hash. */
- u32 parent_q;
-
- /* What to change parent tab[b] to use this hash. */
- u32 newval_q;
-
- /* Original value of tab[b]. */
- u32 oldval_q;
-} phash_tabq_t;
-
-typedef struct
-{
- u8 a_bits, b_bits, s_bits, a_shift;
- u32 b_mask;
- u32 *tab;
- u32 *scramble;
-
- /* Seed value for hash mixer. */
- u64 hash_seed;
-
- u32 flags;
-
- /* Key functions want 64 bit keys.
- Use hash_mix64 rather than hash_mix32. */
-#define PHASH_FLAG_MIX64 (1 << 0)
-#define PHASH_FLAG_MIX32 (0 << 0)
-
- /* When b_bits is large enough (>= 12) we scramble. */
-#define PHASH_FLAG_USE_SCRAMBLE (1 << 1)
-
- /* Slow mode gives smaller tables but at the expense of more run time. */
-#define PHASH_FLAG_SLOW_MODE (0 << 2)
-#define PHASH_FLAG_FAST_MODE (1 << 2)
-
- /* Generate minimal perfect hash instead of perfect hash. */
-#define PHASH_FLAG_NON_MINIMAL (0 << 3)
-#define PHASH_FLAG_MINIMAL (1 << 3)
-
- /* vec_len (keys) for minimal hash;
- 1 << s_bits for non-minimal hash. */
- u32 hash_max;
-
- /* Vector of keys. */
- phash_key_t *keys;
-
- /* Used by callbacks to identify keys. */
- void *private;
-
- /* Key comparison callback. */
- int (*key_is_equal) (void *private, uword key1, uword key2);
-
- /* Callback to reduce single key -> hash seeds. */
- void (*key_seed1) (void *private, uword key, void *seed);
-
- /* Callback to reduce two key2 -> hash seeds. */
- void (*key_seed2) (void *private, uword key1, uword key2, void *seed);
-
- /* Stuff used to compute perfect hash. */
- u32 random_seed;
-
- /* Stuff indexed by B. */
- phash_tabb_t *tabb;
-
- /* Table of B ordered by number of keys in tabb[b]. */
- u32 *tabb_sort;
-
- /* Unique key (or ~0 if none) for a given hash
- H = A ^ scramble[tab[B].val_b]. */
- u32 *tabh;
-
- /* Stuff indexed by q. */
- phash_tabq_t *tabq;
-
- /* Stats. */
- u32 n_seed_trials, n_perfect_calls;
-} phash_main_t;
-
-always_inline void
-phash_main_free_working_memory (phash_main_t * pm)
-{
- vec_free (pm->tabb);
- vec_free (pm->tabq);
- vec_free (pm->tabh);
- vec_free (pm->tabb_sort);
- if (!(pm->flags & PHASH_FLAG_USE_SCRAMBLE))
- vec_free (pm->scramble);
-}
-
-always_inline void
-phash_main_free (phash_main_t * pm)
-{
- phash_main_free_working_memory (pm);
- vec_free (pm->tab);
- vec_free (pm->keys);
- clib_memset (pm, 0, sizeof (pm[0]));
-}
-
-/* Slow hash computation for general keys. */
-uword phash_hash_slow (phash_main_t * pm, uword key);
-
-/* Main routine to compute perfect hash. */
-clib_error_t *phash_find_perfect_hash (phash_main_t * pm);
-
-/* Validates that hash is indeed perfect. */
-clib_error_t *phash_validate (phash_main_t * pm);
-
-/* Unit test. */
-int phash_test_main (unformat_input_t * input);
-
-#endif /* included_phash_h */
-
-/*
- * fd.io coding-style-patch-verification: ON
- *
- * Local Variables:
- * eval: (c-set-style "gnu")
- * End:
- */