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                 :             : namespace leveldb {
      12                 :             : 
      13                 :     4419758 : uint32_t Hash(const char* data, size_t n, uint32_t seed) {
      14                 :             :   // Similar to murmur hash
      15                 :     4419758 :   const uint32_t m = 0xc6a4a793;
      16                 :     4419758 :   const uint32_t r = 24;
      17                 :     4419758 :   const char* limit = data + n;
      18                 :     4419758 :   uint32_t h = seed ^ (n * m);
      19                 :             : 
      20                 :             :   // Pick up four bytes at a time
      21         [ +  + ]:    28470249 :   while (limit - data >= 4) {
      22                 :    24050491 :     uint32_t w = DecodeFixed32(data);
      23                 :    24050491 :     data += 4;
      24                 :    24050491 :     h += w;
      25                 :    24050491 :     h *= m;
      26                 :    24050491 :     h ^= (h >> 16);
      27                 :             :   }
      28                 :             : 
      29                 :             :   // Pick up remaining bytes
      30   [ +  +  +  + ]:     4419758 :   switch (limit - data) {
      31                 :      266260 :     case 3:
      32                 :      266260 :       h += static_cast<uint8_t>(data[2]) << 16;
      33                 :      724425 :       [[fallthrough]];
      34                 :      724425 :     case 2:
      35                 :      724425 :       h += static_cast<uint8_t>(data[1]) << 8;
      36                 :      903959 :       [[fallthrough]];
      37                 :      903959 :     case 1:
      38                 :      903959 :       h += static_cast<uint8_t>(data[0]);
      39                 :      903959 :       h *= m;
      40                 :      903959 :       h ^= (h >> r);
      41                 :      903959 :       break;
      42                 :             :   }
      43                 :     4419758 :   return h;
      44                 :             : }
      45                 :             : 
      46                 :             : }  // namespace leveldb