hash_hashinate.hpp

Go to the documentation of this file.

/*
 * Copyright (c) 2014-2015, Hewlett-Packard Development Company, LP.
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 2 of the License, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
 * more details. You should have received a copy of the GNU General Public
 * License along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 *
 * HP designates this particular file as subject to the "Classpath" exception
 * as provided by HP in the LICENSE.txt file that accompanied this code.
 */
#ifndef FOEDUS_STORAGE_HASH_HASHINATE_HPP_
#define FOEDUS_STORAGE_HASH_HASHINATE_HPP_

#include <stdint.h>

#include <cstring>
#include <iosfwd>

#include "foedus/compiler.hpp"
#include "foedus/cxx11.hpp"
#include "foedus/storage/hash/fwd.hpp"
#include "foedus/storage/hash/hash_id.hpp"

namespace foedus {
namespace storage {
namespace hash {

const uint64_t kXxhashKeySeed = 0x3f119e0435262a17ULL;

HashValue hashinate(const void *key, uint16_t key_length);

template <typename T>
HashValue hashinate(T key);

const uint16_t kHashDataPageBloomFilterBytes = 64;

const uint16_t kHashDataPageBloomFilterBits = kHashDataPageBloomFilterBytes * 8;

const uint8_t kHashDataPageBloomFilterIndexSize = 9U;

CXX11_STATIC_ASSERT(
  kHashDataPageBloomFilterBits == (1U << kHashDataPageBloomFilterIndexSize),
  "If you change the size of bloom filter, change kHashDataPageBloomFilterIndexSize accordingly.");

const HashValue kHashDataPageBloomFilterIndexMask = (1U << kHashDataPageBloomFilterIndexSize) - 1U;

const uint8_t kHashDataPageBloomFilterHashes = 3;

struct BloomFilterFingerprint {
  uint16_t indexes_[kHashDataPageBloomFilterHashes];

  bool operator==(const BloomFilterFingerprint& other) const {
    for (uint8_t k = 0; k < kHashDataPageBloomFilterHashes; ++k) {
      if (indexes_[k] != other.indexes_[k]) {
        return false;
      }
    }
    return true;
  }
  bool operator!=(const BloomFilterFingerprint& other) const {
    return !(operator==(other));
  }
  friend std::ostream& operator<<(std::ostream& o, const BloomFilterFingerprint& v);
};

struct DataPageBloomFilter CXX11_FINAL {
  uint8_t values_[kHashDataPageBloomFilterBytes];

  void clear() {
    std::memset(values_, 0, sizeof(values_));
  }

  inline bool contains(const BloomFilterFingerprint& fingerprint) const ALWAYS_INLINE {
    for (uint8_t k = 0; k < kHashDataPageBloomFilterHashes; ++k) {
      ASSERT_ND(fingerprint.indexes_[k] < kHashDataPageBloomFilterBits);
      uint8_t byte_index = fingerprint.indexes_[k] / 8U;
      uint8_t bit_index = fingerprint.indexes_[k] % 8U;
      if ((values_[byte_index] & (1U << bit_index)) == 0) {
        return false;
      }
    }
    return true;
  }

  inline void add(const BloomFilterFingerprint& fingerprint) ALWAYS_INLINE {
    for (uint8_t k = 0; k < kHashDataPageBloomFilterHashes; ++k) {
      ASSERT_ND(fingerprint.indexes_[k] < kHashDataPageBloomFilterBits);
      uint8_t byte_index = fingerprint.indexes_[k] / 8U;
      uint8_t bit_index = fingerprint.indexes_[k] % 8U;
      values_[byte_index] |= (1U << bit_index);
    }
  }

  static BloomFilterFingerprint extract_fingerprint(HashValue fullhash) {
    BloomFilterFingerprint ret;
    for (uint8_t k = 0; k < kHashDataPageBloomFilterHashes; ++k) {
      uint64_t index = fullhash >> (k * kHashDataPageBloomFilterIndexSize);
      // as kHashDataPageBloomFilterBits is power of 2, this is a bit simpler, but not much.
      ret.indexes_[k] = index & kHashDataPageBloomFilterIndexMask;
    }
    return ret;
  }

  friend std::ostream& operator<<(std::ostream& o, const DataPageBloomFilter& v);
};

union IntermediateRoute {
  uint64_t word;
  uint8_t route[8];

  bool operator==(const IntermediateRoute& rhs) const { return word == rhs.word; }
  bool operator!=(const IntermediateRoute& rhs) const { return word != rhs.word; }
  bool operator<(const IntermediateRoute& rhs) const {
    for (uint16_t i = 1; i <= 8U; ++i) {
      // compare the higher level first. if the machine is big-endian, we can just compare word.
      // but, this method is not used in performance-sensitive place, so let's be explicit.
      if (route[8U - i] != rhs.route[8U - i]) {
        return route[8U - i] < rhs.route[8U - i];
      }
    }
    return false;
  }
  bool operator<=(const IntermediateRoute& rhs) const { return *this == rhs || *this < rhs; }
  friend std::ostream& operator<<(std::ostream& o, const IntermediateRoute& v);

  HashBin convert_back() const {
    HashBin bin = 0;
    for (uint8_t level = 0; level < kHashMaxLevels; ++level) {
      bin += route[level] * kHashMaxBins[level];
    }
    return bin;
  }

  static IntermediateRoute construct(HashBin bin) {
    IntermediateRoute ret;
    ret.word = 0;
    uint8_t level = 0;
    HashBin remaining = bin;
    while (remaining > 0) {
      // in hash, fanout is always fixed, so no need for pre-calculated const_div. compiler does it.
      ret.route[level] = remaining % kHashIntermediatePageFanout;
      remaining /= kHashIntermediatePageFanout;
      ++level;
      ASSERT_ND(level < 8U);
    }

    ASSERT_ND(ret.convert_back() == bin);
    return ret;
  }
};

}  // namespace hash
}  // namespace storage
}  // namespace foedus
#endif  // FOEDUS_STORAGE_HASH_HASHINATE_HPP_