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