silo/masstree/masstree_insert.hh

   1 /* Masstree
   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
   5  *
   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
  14  * is legally binding.
  15  */
  16 #ifndef MASSTREE_INSERT_HH
  17 #define MASSTREE_INSERT_HH
  18 #include "masstree_get.hh"
  19 #include "masstree_split.hh"
  20 namespace Masstree {
  21
  22 template <typename P>
  23 bool tcursor<P>::find_insert(threadinfo& ti)
  24 {
  25     find_locked(ti);
  26     original_n_ = n_;
  27     original_v_ = n_->full_unlocked_version_value();
  28
  29     // maybe we found it
  30     if (state_)
  31         return true;
  32
  33     // otherwise mark as inserted but not present
  34     state_ = 2;
  35
  36     // maybe we need a new layer
  37     if (kx_.p >= 0)
  38         return make_new_layer(ti);
  39
  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);
  43         n_->mark_insert();
  44         n_->modstate_ = leaf<P>::modstate_insert;
  45     }
  46
  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);
  53             return false;
  54         }
  55     }
  56
  57     // otherwise must split
  58     return make_split(ti);
  59 }
  60
  61 template <typename P>
  62 bool tcursor<P>::make_new_layer(threadinfo& ti) {
  63     key_type oka(n_->ksuf(kx_.p));
  64     ka_.shift();
  65     int kcmp = oka.compare(ka_);
  66
  67     // Create a twig of nodes until the suffixes diverge
  68     leaf_type* twig_head = n_;
  69     leaf_type* twig_tail = n_;
  70     while (kcmp == 0) {
  71         leaf_type* nl = leaf_type::make_root(0, twig_tail, ti);
  72         nl->assign_initialize_for_layer(0, oka);
  73         if (twig_head != n_)
  74             twig_tail->lv_[0] = nl;
  75         else
  76             twig_head = nl;
  77         nl->permutation_ = permuter_type::make_sorted(1);
  78         twig_tail = nl;
  79         new_nodes_.emplace_back(nl, nl->full_unlocked_version_value());
  80         oka.shift();
  81         ka_.shift();
  82         kcmp = oka.compare(ka_);
  83     }
  84
  85     // Estimate how much space will be required for keysuffixes
  86     size_t ksufsize;
  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);
  91     else
  92         ksufsize = 0;
  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));
  98     if (kcmp < 0)
  99         nl->permutation_ = permuter_type::make_sorted(1);
 100     else {
 101         permuter_type permnl = permuter_type::make_sorted(2);
 102         permnl.remove_to_back(0);
 103         nl->permutation_ = permnl.value();
 104     }
 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
 111     // retry.
 112     n_->mark_insert();
 113     fence();
 114     if (twig_tail != n_)
 115         twig_tail->lv_[0] = nl;
 116     if (twig_head != n_)
 117         n_->lv_[kx_.p] = twig_head;
 118     else
 119         n_->lv_[kx_.p] = nl;
 120     n_->keylenx_[kx_.p] = n_->layer_keylenx;
 121     updated_v_ = n_->full_unlocked_version_value();
 122     n_->unlock();
 123     n_ = nl;
 124     kx_.i = kx_.p = kcmp < 0;
 125     return false;
 126 }
 127
 128 template <typename P>
 129 void tcursor<P>::finish_insert()
 130 {
 131     permuter_type perm(n_->permutation_);
 132     masstree_invariant(perm.back() == kx_.p);
 133     perm.insert_from_back(kx_.i);
 134     fence();
 135     n_->permutation_ = perm.value();
 136 }
 137
 138 template <typename P>
 139 inline void tcursor<P>::finish(int state, threadinfo& ti)
 140 {
 141     if (state < 0 && state_ == 1) {
 142         if (finish_remove(ti))
 143             return;
 144     } else if (state > 0 && state_ == 2)
 145         finish_insert();
 146     // we finally know this!
 147     if (n_ == original_n_)
 148         updated_v_ = n_->full_unlocked_version_value();
 149     else
 150         new_nodes_.emplace_back(n_, n_->full_unlocked_version_value());
 151     n_->unlock();
 152 }
 153
 154 template <typename P> template <typename F>
 155 inline int basic_table<P>::modify(Str key, F& f, threadinfo& ti)
 156 {
 157     tcursor<P> lp(*this, key);
 158     bool found = lp.find_locked(ti);
 159     int answer;
 160     if (found)
 161         answer = f(key, true, lp.value(), ti, lp.node_timestamp());
 162     else
 163         answer = 0;
 164     lp.finish(answer, ti);
 165     return answer;
 166 }
 167
 168 template <typename P> template <typename F>
 169 inline int basic_table<P>::modify_insert(Str key, F& f, threadinfo& ti)
 170 {
 171     tcursor<P> lp(*this, key);
 172     bool found = lp.find_insert(ti);
 173     if (!found)
 174         ti.advance_timestamp(lp.node_timestamp());
 175     int answer = f(key, found, lp.value(), ti, lp.node_timestamp());
 176     lp.finish(answer, ti);
 177     return answer;
 178 }
 179
 180 } // namespace Masstree
 181 #endif