masstree_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_MASSTREE_MASSTREE_ID_HPP_
#define FOEDUS_STORAGE_MASSTREE_MASSTREE_ID_HPP_

#include <stdint.h>

#include <cstring>
#include <limits>

#include "foedus/compiler.hpp"
#include "foedus/assorted/endianness.hpp"
#include "foedus/storage/storage_id.hpp"

namespace foedus {
namespace storage {
namespace masstree {
typedef uint8_t Layer;

const Layer kMaxLayer = 63U;

typedef uint8_t InLayerLevel;

const InLayerLevel kMaxSaneInLayerLevel = 15U;

typedef uint16_t KeyLength;

const KeyLength kMaxKeyLength = 1024U;

const KeyLength kInitiallyNextLayer = 0xFFFFU;

typedef uint16_t PayloadLength;

const PayloadLength kMaxPayloadLength = 1024U;

typedef uint16_t DataOffset;

typedef uint16_t SlotIndex;

typedef uint64_t KeySlice;

const uint64_t kSliceLen = sizeof(KeySlice);

// infimum can be simply 0 because low-fence is inclusive.
const KeySlice kInfimumSlice = 0;
// Be aware that this might be used as a valid key slice of \e a record.
// Instead, as a fence, this is always used as a supremum.
// So, for a record key, sanity check is "slice < high_fence || (slice==high_fence==supremum)"
// For a fence, sanity check is "slice < high_fence"
const KeySlice kSupremumSlice = 0xFFFFFFFFFFFFFFFFULL;

const uint32_t kCommonPageHeaderSize = 80U;

const uint32_t kBorderPageAdditionalHeaderSize = 8U;

const uint32_t kBorderPageSlotSize = 32U;

const SlotIndex kBorderPageMaxSlots
  = (kPageSize - kCommonPageHeaderSize - kBorderPageAdditionalHeaderSize)
    / (kBorderPageSlotSize + sizeof(KeySlice));

const uint32_t kBorderPageDataPartSize
  = kPageSize
    - kCommonPageHeaderSize
    - kBorderPageAdditionalHeaderSize
    - kBorderPageMaxSlots * sizeof(KeySlice);

const DataOffset kBorderPageDataPartOffset
  = kCommonPageHeaderSize
  + 8U  // next_offset_, consecutive_inserts_, dummy_
  + kBorderPageMaxSlots * sizeof(KeySlice);  // slices_

template<typename T>
inline KeySlice normalize_primitive(T value) {
  if (std::numeric_limits<T>::is_signed) {
    return static_cast<uint64_t>(value) - (1ULL << 63);
  } else {
    return static_cast<uint64_t>(value);
  }
}

template<typename T>
inline T denormalize_primitive(KeySlice value) {
  if (std::numeric_limits<T>::is_signed) {
    return static_cast<T>(value - (1ULL << 63));
  } else {
    return static_cast<T>(value);
  }
}

inline KeySlice normalize_be_bytes_full_aligned(const void* be_bytes) {
  // then efficient.
  return assorted::read_bigendian<uint64_t>(be_bytes);
}

inline KeySlice normalize_be_bytes_full(const void* be_bytes) {
  // otherwise we have to copy to an aligned local variable first
  uint64_t tmp;  // 8-byte stack variable is guaranteed to be 8-byte aligned. at least in GCC.
  std::memcpy(&tmp, be_bytes, 8);
  return assorted::read_bigendian<uint64_t>(&tmp);
}

inline KeySlice normalize_be_bytes_fragment(const void* be_bytes, uint32_t length) {
  if (length >= 8) {
    return normalize_be_bytes_full(be_bytes);
  }
  uint64_t tmp = 0;
  std::memcpy(&tmp, be_bytes, length);
  return assorted::read_bigendian<uint64_t>(&tmp);
}

inline KeySlice slice_key(const void* be_bytes, KeyLength slice_length) {
  if (slice_length >= sizeof(KeySlice)) {
    return normalize_be_bytes_full(be_bytes);
  } else {
    return normalize_be_bytes_fragment(be_bytes, slice_length);
  }
}

inline KeySlice slice_layer(const void* be_bytes, KeyLength key_length, Layer current_layer) {
  const KeyLength skipped = current_layer * sizeof(KeySlice);
  const KeyLength remainder_length = key_length - skipped;
  const char* casted = reinterpret_cast<const char*>(be_bytes);
  if (remainder_length >= sizeof(KeySlice)) {
    return normalize_be_bytes_full(casted + skipped);
  } else {
    return normalize_be_bytes_fragment(casted + skipped, remainder_length);
  }
}

inline uint16_t count_common_slices(const void* left, const void* right, uint16_t max_slices) {
  const uint64_t* left_casted = reinterpret_cast<const uint64_t*>(ASSUME_ALIGNED(left, 8));
  const uint64_t* right_casted = reinterpret_cast<const uint64_t*>(ASSUME_ALIGNED(right, 8));
  for (uint16_t slices = 0; slices < max_slices; ++slices) {
    if (left_casted[slices] != right_casted[slices]) {
      return slices;
    }
  }
  return max_slices;
}

inline bool is_key_aligned_and_zero_padded(const char* key, KeyLength key_length) {
  uintptr_t int_address = reinterpret_cast<uintptr_t>(key);
  if (int_address % 8 != 0) {
    return false;
  }
  if (key_length % 8 != 0) {
    uint16_t paddings = 8 - (key_length % 8);
    for (uint16_t i = 0; i < paddings; ++i) {
      if (key[key_length + i] != 0) {
        return false;
      }
    }
  }
  return true;
}

}  // namespace masstree
}  // namespace storage
}  // namespace foedus
#endif  // FOEDUS_STORAGE_MASSTREE_MASSTREE_ID_HPP_