hash_id.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_HASH_ID_HPP_
#define FOEDUS_STORAGE_HASH_HASH_ID_HPP_
#include <stdint.h>

#include <iosfwd>

#include "foedus/cxx11.hpp"
#include "foedus/storage/storage_id.hpp"

namespace foedus {
namespace storage {
namespace hash {

const uint16_t kHashIntermediatePageHeaderSize  = 64;

const uint8_t kHashIntermediatePageFanout      =
  (kPageSize - kHashIntermediatePageHeaderSize) / sizeof(DualPagePointer);

inline uint64_t fanout_power(uint8_t exponent) {
  uint64_t ret = 1U;
  for (uint8_t i = 0; i < exponent; ++i) {
    ret *= kHashIntermediatePageFanout;
  }
  return ret;
}

const uint64_t kFanout64 = kHashIntermediatePageFanout;
const uint64_t kHashMaxBins[] = {
  1ULL,
  kFanout64,
  kFanout64 * kFanout64,
  kFanout64 * kFanout64 * kFanout64,
  kFanout64 * kFanout64 * kFanout64 * kFanout64,
  kFanout64 * kFanout64 * kFanout64 * kFanout64 * kFanout64,
  kFanout64 * kFanout64 * kFanout64 * kFanout64 * kFanout64 * kFanout64,
  kFanout64 * kFanout64 * kFanout64 * kFanout64 * kFanout64 * kFanout64 * kFanout64,
  kFanout64 * kFanout64 * kFanout64 * kFanout64 * kFanout64 * kFanout64 * kFanout64 * kFanout64,
};

inline uint8_t bins_to_level(uint64_t bins) {
  uint8_t level;
  for (level = 1U; kHashMaxBins[level] < bins; ++level) {
    continue;
  }
  return level;
}

const uint8_t kHashMaxLevels = 8;

const uint16_t kHashDataPageHeaderSize  = 128;

const uint16_t kHashDataPageDataSize  = kPageSize - kHashDataPageHeaderSize;

typedef uint64_t HashValue;

typedef uint64_t HashBin;

const uint8_t kHashMinBinBits = 7U;

const uint8_t kHashMaxBinBits = 48U;

const HashBin kInvalidHashBin = 1ULL << kHashMaxBinBits;

struct HashBinRange {
  HashBinRange() : begin_(0), end_(0) {}
  HashBinRange(HashBin begin, HashBin end) : begin_(begin), end_(end) {}

  bool    contains(HashBin hash) const { return hash >= begin_ && hash < end_; }
  bool    contains(const HashBinRange& other) const {
    return begin_ <= other.begin_ && end_ >= other.end_;
  }
  bool    operator==(const HashBinRange& other) const {
    return begin_ == other.begin_ && end_ == other.end_;
  }
  bool    operator!=(const HashBinRange& other) const { return !(this->operator==(other)); }

  uint64_t length() const { return end_ - begin_; }

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

  HashBin begin_;
  HashBin end_;
};

typedef uint16_t DataPageSlotIndex;
const DataPageSlotIndex kSlotNotFound = 0xFFFFU;

typedef uint16_t KeyLength;

typedef uint16_t PayloadLength;

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