silo/masstree/value_versioned_array.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 VALUE_VERSIONED_ARRAY_HH
  17 #define VALUE_VERSIONED_ARRAY_HH
  18 #include "compiler.hh"
  19 #include "value_array.hh"
  20
  21 struct rowversion {
  22     rowversion() {
  23         v_.u = 0;
  24     }
  25     bool dirty() {
  26         return v_.dirty;
  27     }
  28     void setdirty() {
  29         v_.u = v_.u | 0x80000000;
  30     }
  31     void clear() {
  32         v_.u = v_.u & 0x7fffffff;
  33     }
  34     void clearandbump() {
  35         v_.u = (v_.u + 1) & 0x7fffffff;
  36     }
  37     rowversion stable() const {
  38         value_t x = v_;
  39         while (x.dirty) {
  40             relax_fence();
  41             x = v_;
  42         }
  43         acquire_fence();
  44         return x;
  45     }
  46     bool has_changed(rowversion x) const {
  47         fence();
  48         return x.v_.ctr != v_.ctr;
  49     }
  50   private:
  51     union value_t {
  52         struct {
  53             uint32_t ctr:31;
  54             uint32_t dirty:1;
  55         };
  56         uint32_t u;
  57     };
  58     value_t v_;
  59
  60     rowversion(value_t v)
  61         : v_(v) {
  62     }
  63
  64 };
  65
  66 class value_versioned_array {
  67   public:
  68     typedef value_array::index_type index_type;
  69     static const char *name() { return "ArrayVersion"; }
  70
  71     typedef lcdf::Json Json;
  72
  73     inline value_versioned_array();
  74
  75     inline kvtimestamp_t timestamp() const;
  76     inline int ncol() const;
  77     inline Str col(int i) const;
  78
  79     void deallocate(threadinfo &ti);
  80     void deallocate_rcu(threadinfo &ti);
  81
  82     void snapshot(value_versioned_array*& storage,
  83                   const std::vector<index_type>& f, threadinfo& ti) const;
  84
  85     value_versioned_array* update(const Json* first, const Json* last,
  86                                   kvtimestamp_t ts, threadinfo& ti,
  87                                   bool always_copy = false);
  88     static value_versioned_array* create(const Json* first, const Json* last,
  89                                          kvtimestamp_t ts, threadinfo& ti);
  90     static value_versioned_array* create1(Str value, kvtimestamp_t ts, threadinfo& ti);
  91     inline void deallocate_rcu_after_update(const Json* first, const Json* last, threadinfo& ti);
  92     inline void deallocate_after_failed_update(const Json* first, const Json* last, threadinfo& ti);
  93
  94     template <typename PARSER>
  95     static value_versioned_array* checkpoint_read(PARSER& par, kvtimestamp_t ts,
  96                                                   threadinfo& ti);
  97     template <typename UNPARSER>
  98     void checkpoint_write(UNPARSER& unpar) const;
  99
 100     void print(FILE *f, const char *prefix, int indent, Str key,
 101                kvtimestamp_t initial_ts, const char *suffix = "") {
 102         kvtimestamp_t adj_ts = timestamp_sub(ts_, initial_ts);
 103         fprintf(f, "%s%*s%.*s = ### @" PRIKVTSPARTS "%s\n", prefix, indent, "",
 104                 key.len, key.s, KVTS_HIGHPART(adj_ts), KVTS_LOWPART(adj_ts), suffix);
 105     }
 106
 107   private:
 108     kvtimestamp_t ts_;
 109     rowversion ver_;
 110     short ncol_;
 111     short ncol_cap_;
 112     lcdf::inline_string* cols_[0];
 113
 114     static inline size_t shallow_size(int ncol);
 115     inline size_t shallow_size() const;
 116     static value_versioned_array* make_sized_row(int ncol, kvtimestamp_t ts, threadinfo& ti);
 117 };
 118
 119 template <>
 120 struct query_helper<value_versioned_array> {
 121     value_versioned_array* snapshot_;
 122
 123     query_helper()
 124         : snapshot_() {
 125     }
 126     inline const value_versioned_array* snapshot(const value_versioned_array* row,
 127                                                  const std::vector<value_versioned_array::index_type>& f,
 128                                                  threadinfo& ti) {
 129         row->snapshot(snapshot_, f, ti);
 130         return snapshot_;
 131     }
 132 };
 133
 134 inline value_versioned_array::value_versioned_array()
 135     : ts_(0), ncol_(0), ncol_cap_(0) {
 136 }
 137
 138 inline kvtimestamp_t value_versioned_array::timestamp() const {
 139     return ts_;
 140 }
 141
 142 inline int value_versioned_array::ncol() const {
 143     return ncol_;
 144 }
 145
 146 inline Str value_versioned_array::col(int i) const {
 147     if (unsigned(i) < unsigned(ncol_) && cols_[i])
 148         return Str(cols_[i]->s, cols_[i]->len);
 149     else
 150         return Str();
 151 }
 152
 153 inline size_t value_versioned_array::shallow_size(int ncol) {
 154     return sizeof(value_versioned_array) + ncol * sizeof(lcdf::inline_string*);
 155 }
 156
 157 inline size_t value_versioned_array::shallow_size() const {
 158     return shallow_size(ncol_);
 159 }
 160
 161 inline value_versioned_array* value_versioned_array::create(const Json* first, const Json* last, kvtimestamp_t ts, threadinfo& ti) {
 162     value_versioned_array empty;
 163     return empty.update(first, last, ts, ti, true);
 164 }
 165
 166 inline value_versioned_array* value_versioned_array::create1(Str value, kvtimestamp_t ts, threadinfo& ti) {
 167     value_versioned_array* row = (value_versioned_array*) ti.allocate(shallow_size(1), memtag_value);
 168     row->ts_ = ts;
 169     row->ver_ = rowversion();
 170     row->ncol_ = row->ncol_cap_ = 1;
 171     row->cols_[0] = value_array::make_column(value, ti);
 172     return row;
 173 }
 174
 175 inline void value_versioned_array::deallocate_rcu_after_update(const Json*, const Json*, threadinfo& ti) {
 176     ti.deallocate_rcu(this, shallow_size(), memtag_value);
 177 }
 178
 179 inline void value_versioned_array::deallocate_after_failed_update(const Json*, const Json*, threadinfo&) {
 180     always_assert(0);
 181 }
 182
 183 template <typename PARSER>
 184 value_versioned_array*
 185 value_versioned_array::checkpoint_read(PARSER& par, kvtimestamp_t ts,
 186                                        threadinfo& ti) {
 187     unsigned ncol;
 188     par.read_array_header(ncol);
 189     value_versioned_array* row = make_sized_row(ncol, ts, ti);
 190     Str col;
 191     for (unsigned i = 0; i != ncol; i++) {
 192         par >> col;
 193         row->cols_[i] = value_array::make_column(col, ti);
 194     }
 195     return row;
 196 }
 197
 198 template <typename UNPARSER>
 199 void value_versioned_array::checkpoint_write(UNPARSER& unpar) const {
 200     unpar.write_array_header(ncol_);
 201     for (short i = 0; i != ncol_; ++i)
 202         unpar << col(i);
 203 }
 204
 205 #endif