xpcom/ds/PerfectHash.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /* Helper routines for perfecthash.py.  Not to be used directly. */
   8
   9 #ifndef mozilla_PerfectHash_h
  10 #define mozilla_PerfectHash_h
  11
  12 #include <type_traits>
  13
  14 namespace mozilla {
  15 namespace perfecthash {
  16
  17 // 32-bit FNV offset basis and prime value.
  18 // NOTE: Must match values in |perfecthash.py|
  19 constexpr uint32_t FNV_OFFSET_BASIS = 0x811C9DC5;
  20 constexpr uint32_t FNV_PRIME = 16777619;
  21
  22 /**
  23  * Basic FNV hasher function used by perfecthash. Generic over the unit type.
  24  */
  25 template <typename C>
  26 inline uint32_t Hash(uint32_t aBasis, const C* aKey, size_t aLen) {
  27   for (size_t i = 0; i < aLen; ++i) {
  28     aBasis =
  29         (aBasis ^ static_cast<std::make_unsigned_t<C>>(aKey[i])) * FNV_PRIME;
  30   }
  31   return aBasis;
  32 }
  33
  34 /**
  35  * Helper method for getting the index from a perfect hash.
  36  * Called by code generated from |perfecthash.py|.
  37  */
  38 template <typename C, typename Base, size_t NBases, typename Entry,
  39           size_t NEntries>
  40 inline const Entry& Lookup(const C* aKey, size_t aLen,
  41                            const Base (&aTable)[NBases],
  42                            const Entry (&aEntries)[NEntries]) {
  43   uint32_t basis = aTable[Hash(FNV_OFFSET_BASIS, aKey, aLen) % NBases];
  44   return aEntries[Hash(basis, aKey, aLen) % NEntries];
  45 }
  46
  47 }  // namespace perfecthash
  48 }  // namespace mozilla
  49
  50 #endif  // !defined(mozilla_PerfectHash_h)