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