1179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Copyright (c) 2011 The LevelDB Authors. All rights reserved. 2179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Use of this source code is governed by a BSD-style license that can be 3179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// found in the LICENSE file. See the AUTHORS file for names of contributors. 4179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 5179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include <string.h> 6179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/coding.h" 7179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/hash.h" 8179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 9bbb0263070defe02ffee97b35d0dc31d3f6297a3dgrogan@chromium.org// The FALLTHROUGH_INTENDED macro can be used to annotate implicit fall-through 10bbb0263070defe02ffee97b35d0dc31d3f6297a3dgrogan@chromium.org// between switch labels. The real definition should be provided externally. 11bbb0263070defe02ffee97b35d0dc31d3f6297a3dgrogan@chromium.org// This one is a fallback version for unsupported compilers. 12bbb0263070defe02ffee97b35d0dc31d3f6297a3dgrogan@chromium.org#ifndef FALLTHROUGH_INTENDED 13bbb0263070defe02ffee97b35d0dc31d3f6297a3dgrogan@chromium.org#define FALLTHROUGH_INTENDED do { } while (0) 14bbb0263070defe02ffee97b35d0dc31d3f6297a3dgrogan@chromium.org#endif 15bbb0263070defe02ffee97b35d0dc31d3f6297a3dgrogan@chromium.org 16179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace leveldb { 17179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 18179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orguint32_t Hash(const char* data, size_t n, uint32_t seed) { 19179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Similar to murmur hash 20179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const uint32_t m = 0xc6a4a793; 21179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const uint32_t r = 24; 22179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const char* limit = data + n; 23179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint32_t h = seed ^ (n * m); 24179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 25179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Pick up four bytes at a time 26179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org while (data + 4 <= limit) { 27179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint32_t w = DecodeFixed32(data); 28179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org data += 4; 29179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org h += w; 30179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org h *= m; 31179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org h ^= (h >> 16); 32179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 33179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 34179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Pick up remaining bytes 35179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org switch (limit - data) { 36179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org case 3: 37179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org h += data[2] << 16; 38bbb0263070defe02ffee97b35d0dc31d3f6297a3dgrogan@chromium.org FALLTHROUGH_INTENDED; 39179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org case 2: 40179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org h += data[1] << 8; 41bbb0263070defe02ffee97b35d0dc31d3f6297a3dgrogan@chromium.org FALLTHROUGH_INTENDED; 42179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org case 1: 43179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org h += data[0]; 44179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org h *= m; 45179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org h ^= (h >> r); 46179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org break; 47179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 48179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return h; 49179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 50179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 51179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 5245b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace leveldb 53