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