Branch data     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 "util/hash.h"
#       6                 :            : 
#       7                 :            : #include <string.h>
#       8                 :            : 
#       9                 :            : #include "util/coding.h"
#      10                 :            : 
#      11                 :            : // The FALLTHROUGH_INTENDED macro can be used to annotate implicit fall-through
#      12                 :            : // between switch labels. The real definition should be provided externally.
#      13                 :            : // This one is a fallback version for unsupported compilers.
#      14                 :            : #ifndef FALLTHROUGH_INTENDED
#      15                 :            : #define FALLTHROUGH_INTENDED \
#      16                 :            :   do {                       \
#      17                 :            :   } while (0)
#      18                 :            : #endif
#      19                 :            : 
#      20                 :            : namespace leveldb {
#      21                 :            : 
#      22                 :    7074475 : uint32_t Hash(const char* data, size_t n, uint32_t seed) {
#      23                 :            :   // Similar to murmur hash
#      24                 :    7074475 :   const uint32_t m = 0xc6a4a793;
#      25                 :    7074475 :   const uint32_t r = 24;
#      26                 :    7074475 :   const char* limit = data + n;
#      27                 :    7074475 :   uint32_t h = seed ^ (n * m);
#      28                 :            : 
#      29                 :            :   // Pick up four bytes at a time
#      30         [ +  + ]:   45465477 :   while (data + 4 <= limit) {
#      31                 :   38391002 :     uint32_t w = DecodeFixed32(data);
#      32                 :   38391002 :     data += 4;
#      33                 :   38391002 :     h += w;
#      34                 :   38391002 :     h *= m;
#      35                 :   38391002 :     h ^= (h >> 16);
#      36                 :   38391002 :   }
#      37                 :            : 
#      38                 :            :   // Pick up remaining bytes
#      39         [ +  + ]:    7074475 :   switch (limit - data) {
#      40         [ +  + ]:     467086 :     case 3:
#      41                 :     467086 :       h += static_cast<uint8_t>(data[2]) << 16;
#      42                 :     467086 :       FALLTHROUGH_INTENDED;
#      43         [ +  + ]:     860343 :     case 2:
#      44                 :     860343 :       h += static_cast<uint8_t>(data[1]) << 8;
#      45                 :     860343 :       FALLTHROUGH_INTENDED;
#      46         [ +  + ]:     930786 :     case 1:
#      47                 :     930786 :       h += static_cast<uint8_t>(data[0]);
#      48                 :     930786 :       h *= m;
#      49                 :     930786 :       h ^= (h >> r);
#      50                 :     930786 :       break;
#      51                 :    7074475 :   }
#      52                 :    7074492 :   return h;
#      53                 :    7074475 : }
#      54                 :            : 
#      55                 :            : }  // namespace leveldb