util/hash.cc

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