masstree_split_impl.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_SPLIT_IMPL_HPP_
#define FOEDUS_STORAGE_MASSTREE_MASSTREE_SPLIT_IMPL_HPP_

#include "foedus/error_code.hpp"
#include "foedus/storage/storage_id.hpp"
#include "foedus/storage/masstree/fwd.hpp"
#include "foedus/storage/masstree/masstree_id.hpp"
#include "foedus/thread/fwd.hpp"
#include "foedus/xct/sysxct_functor.hpp"
#include "foedus/xct/xct_id.hpp"

namespace foedus {
namespace storage {
namespace masstree {

struct SplitBorder final : public xct::SysxctFunctor {
  thread::Thread* const       context_;
  MasstreeBorderPage* const   target_;
  const KeySlice              trigger_;
  const bool                  disable_no_record_split_;
  const bool                  piggyback_reserve_;
  const KeyLength             piggyback_remainder_length_;
  const PayloadLength         piggyback_payload_count_;
  const void*                 piggyback_suffix_;

  SplitBorder(
    thread::Thread* context,
    MasstreeBorderPage* target,
    KeySlice trigger,
    bool disable_no_record_split = false,
    bool            piggyback_reserve = false,
    KeyLength       piggyback_remainder_length = 0,
    PayloadLength   piggyback_payload_count = 0,
    const void*     piggyback_suffix = nullptr)
    : xct::SysxctFunctor(),
      context_(context),
      target_(target),
      trigger_(trigger),
      disable_no_record_split_(disable_no_record_split),
      piggyback_reserve_(piggyback_reserve),
      piggyback_remainder_length_(piggyback_remainder_length),
      piggyback_payload_count_(piggyback_payload_count),
      piggyback_suffix_(piggyback_suffix) {
  }
  virtual ErrorCode run(xct::SysxctWorkspace* sysxct_workspace) override;

  struct SplitStrategy {
    bool no_record_split_;
    SlotIndex original_key_count_;
    KeySlice smallest_slice_;
    KeySlice largest_slice_;
    KeySlice mid_slice_;
  };

  void decide_strategy(SplitStrategy* out) const;

  ErrorCode lock_existing_records(xct::SysxctWorkspace* sysxct_workspace);

  void migrate_records(
    KeySlice inclusive_from,
    KeySlice inclusive_to,
    MasstreeBorderPage* dest) const;
};


struct SplitIntermediate final : public xct::SysxctFunctor {
  thread::Thread* const       context_;
  MasstreeIntermediatePage* const target_;

  MasstreePage* const         piggyback_adopt_child_;

  SplitIntermediate(
    thread::Thread* context,
    MasstreeIntermediatePage* target,
    MasstreePage* piggyback_adopt_child = nullptr)
    : xct::SysxctFunctor(),
      context_(context),
      target_(target),
      piggyback_adopt_child_(piggyback_adopt_child) {
  }

  virtual ErrorCode run(xct::SysxctWorkspace* sysxct_workspace) override;

  void split_impl_no_error(
    thread::GrabFreeVolatilePagesScope* free_pages);

  struct SplitStrategy {
    enum Constants {
      kMaxSeparators = 170,  // must be larger than kMaxIntermediatePointers
    };
    KeySlice separators_[kMaxSeparators];  // ->1360
    DualPagePointer pointers_[kMaxSeparators];  // -> 4080
    KeySlice mid_separator_;  // -> 4088
    uint16_t total_separator_count_;  // -> 4090
    uint16_t mid_index_;  // -> 4092

    bool      compact_adopt_;   // -> 4093
    char      dummy_[3];        // -> 4096
  };

  void decide_strategy(SplitStrategy* out) const;

  void migrate_pointers(
    const SplitStrategy& strategy,
    uint16_t from,
    uint16_t to,
    KeySlice expected_last_separator,
    MasstreeIntermediatePage* dest) const;
};

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