src/leveldb/util/hash.cc

   1 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   4
   5 #include <string.h>
   6 #include "util/coding.h"
   7 #include "util/hash.h"
   8
   9 // The FALLTHROUGH_INTENDED macro can be used to annotate implicit fall-through
  10 // between switch labels. The real definition should be provided externally.
  11 // This one is a fallback version for unsupported compilers.
  12 #ifndef FALLTHROUGH_INTENDED
  13 #define FALLTHROUGH_INTENDED do { } while (0)
  14 #endif
  15
  16 namespace leveldb {
  17
  18 uint32_t Hash(const char* data, size_t n, uint32_t seed) {
  19   // Similar to murmur hash
  20   const uint32_t m = 0xc6a4a793;
  21   const uint32_t r = 24;
  22   const char* limit = data + n;
  23   uint32_t h = seed ^ (n * m);
  24
  25   // Pick up four bytes at a time
  26   while (data + 4 <= limit) {
  27     uint32_t w = DecodeFixed32(data);
  28     data += 4;
  29     h += w;
  30     h *= m;
  31     h ^= (h >> 16);
  32   }
  33
  34   // Pick up remaining bytes
  35   switch (limit - data) {
  36     case 3:
  37       h += data[2] << 16;
  38       FALLTHROUGH_INTENDED;
  39     case 2:
  40       h += data[1] << 8;
  41       FALLTHROUGH_INTENDED;
  42     case 1:
  43       h += data[0];
  44       h *= m;
  45       h ^= (h >> r);
  46       break;
  47   }
  48   return h;
  49 }
  50
  51
  52 }  // namespace leveldb