Line data    Source code

       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       64826 : uint32_t Hash(const char* data, size_t n, uint32_t seed) {
      19             :   // Similar to murmur hash
      20       64826 :   const uint32_t m = 0xc6a4a793;
      21       64826 :   const uint32_t r = 24;
      22       64826 :   const char* limit = data + n;
      23       64826 :   uint32_t h = seed ^ (n * m);
      24             : 
      25             :   // Pick up four bytes at a time
      26      488582 :   while (data + 4 <= limit) {
      27      358930 :     uint32_t w = DecodeFixed32(data);
      28      358930 :     data += 4;
      29      358930 :     h += w;
      30      358930 :     h *= m;
      31      358930 :     h ^= (h >> 16);
      32             :   }
      33             : 
      34             :   // Pick up remaining bytes
      35       64826 :   switch (limit - data) {
      36             :     case 3:
      37         106 :       h += static_cast<unsigned char>(data[2]) << 16;
      38             :       FALLTHROUGH_INTENDED;
      39             :     case 2:
      40         163 :       h += static_cast<unsigned char>(data[1]) << 8;
      41             :       FALLTHROUGH_INTENDED;
      42             :     case 1:
      43       35127 :       h += static_cast<unsigned char>(data[0]);
      44       35127 :       h *= m;
      45       35127 :       h ^= (h >> r);
      46       35127 :       break;
      47             :   }
      48       64826 :   return h;
      49             : }
      50             : 
      51             : 
      52             : }  // namespace leveldb