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