2 * Eddie Kohler, Yandong Mao, Robert Morris
3 * Copyright (c) 2012-2014 President and Fellows of Harvard College
4 * Copyright (c) 2012-2014 Massachusetts Institute of Technology
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, subject to the conditions
9 * listed in the Masstree LICENSE file. These conditions include: you must
10 * preserve this copyright notice, and you cannot mention the copyright
11 * holders in advertising related to the Software without their permission.
12 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
13 * notice is a summary of the Masstree LICENSE file; the license in that file
16 #ifndef MASSTREE_INSERT_HH
17 #define MASSTREE_INSERT_HH
18 #include "masstree_get.hh"
19 #include "masstree_split.hh"
23 bool tcursor<P>::find_insert(threadinfo& ti)
27 original_v_ = n_->full_unlocked_version_value();
33 // otherwise mark as inserted but not present
36 // maybe we need a new layer
38 return make_new_layer(ti);
40 // mark insertion if we are changing modification state
41 if (unlikely(n_->modstate_ != leaf<P>::modstate_insert)) {
42 masstree_invariant(n_->modstate_ == leaf<P>::modstate_remove);
44 n_->modstate_ = leaf<P>::modstate_insert;
47 // try inserting into this node
48 if (n_->size() < n_->width) {
49 kx_.p = permuter_type(n_->permutation_).back();
50 // don't inappropriately reuse position 0, which holds the ikey_bound
51 if (likely(kx_.p != 0) || !n_->prev_ || n_->ikey_bound() == ka_.ikey()) {
52 n_->assign(kx_.p, ka_, ti);
57 // otherwise must split
58 return make_split(ti);
62 bool tcursor<P>::make_new_layer(threadinfo& ti) {
63 key_type oka(n_->ksuf(kx_.p));
65 int kcmp = oka.compare(ka_);
67 // Create a twig of nodes until the suffixes diverge
68 leaf_type* twig_head = n_;
69 leaf_type* twig_tail = n_;
71 leaf_type* nl = leaf_type::make_root(0, twig_tail, ti);
72 nl->assign_initialize_for_layer(0, oka);
74 twig_tail->lv_[0] = nl;
77 nl->permutation_ = permuter_type::make_sorted(1);
79 new_nodes_.emplace_back(nl, nl->full_unlocked_version_value());
82 kcmp = oka.compare(ka_);
85 // Estimate how much space will be required for keysuffixes
87 if (ka_.has_suffix() || oka.has_suffix())
88 ksufsize = (std::max(0, ka_.suffix_length())
89 + std::max(0, oka.suffix_length())) * (n_->width / 2)
90 + n_->iksuf_[0].overhead(n_->width);
93 leaf_type *nl = leaf_type::make_root(ksufsize, twig_tail, ti);
94 nl->assign_initialize(0, kcmp < 0 ? oka : ka_, ti);
95 nl->assign_initialize(1, kcmp < 0 ? ka_ : oka, ti);
96 nl->lv_[kcmp > 0] = n_->lv_[kx_.p];
97 nl->lock(*nl, ti.lock_fence(tc_leaf_lock));
99 nl->permutation_ = permuter_type::make_sorted(1);
101 permuter_type permnl = permuter_type::make_sorted(2);
102 permnl.remove_to_back(0);
103 nl->permutation_ = permnl.value();
105 // In a prior version, recursive tree levels and true values were
106 // differentiated by a bit in the leafvalue. But this constrains the
107 // values users could assign for true values. So now we use bits in
108 // the key length, and changing a leafvalue from true value to
109 // recursive tree requires two writes. How to make this work in the
110 // face of concurrent lockless readers? Mark insertion so they
115 twig_tail->lv_[0] = nl;
117 n_->lv_[kx_.p] = twig_head;
120 n_->keylenx_[kx_.p] = n_->layer_keylenx;
121 updated_v_ = n_->full_unlocked_version_value();
124 kx_.i = kx_.p = kcmp < 0;
128 template <typename P>
129 void tcursor<P>::finish_insert()
131 permuter_type perm(n_->permutation_);
132 masstree_invariant(perm.back() == kx_.p);
133 perm.insert_from_back(kx_.i);
135 n_->permutation_ = perm.value();
138 template <typename P>
139 inline void tcursor<P>::finish(int state, threadinfo& ti)
141 if (state < 0 && state_ == 1) {
142 if (finish_remove(ti))
144 } else if (state > 0 && state_ == 2)
146 // we finally know this!
147 if (n_ == original_n_)
148 updated_v_ = n_->full_unlocked_version_value();
150 new_nodes_.emplace_back(n_, n_->full_unlocked_version_value());
154 template <typename P> template <typename F>
155 inline int basic_table<P>::modify(Str key, F& f, threadinfo& ti)
157 tcursor<P> lp(*this, key);
158 bool found = lp.find_locked(ti);
161 answer = f(key, true, lp.value(), ti, lp.node_timestamp());
164 lp.finish(answer, ti);
168 template <typename P> template <typename F>
169 inline int basic_table<P>::modify_insert(Str key, F& f, threadinfo& ti)
171 tcursor<P> lp(*this, key);
172 bool found = lp.find_insert(ti);
174 ti.advance_timestamp(lp.node_timestamp());
175 int answer = f(key, found, lp.value(), ti, lp.node_timestamp());
176 lp.finish(answer, ti);
180 } // namespace Masstree