1 #ifndef _NDB_TXN_BTREE_H_
2 #define _NDB_TXN_BTREE_H_
4 #include "base_txn_btree.h"
7 extern void txn_btree_test();
12 inline ALWAYS_INLINE const std::string &
13 operator()(const std::string &s)
18 inline ALWAYS_INLINE lcdf::Str operator()(lcdf::Str s) {
26 constexpr key_writer(const std::string *k)
29 template <typename StringAllocator>
30 inline const std::string *
31 fully_materialize(bool stable_input, StringAllocator &sa)
33 if (stable_input || !k)
35 std::string * const ret = sa();
36 ret->assign(k->data(), k->size());
44 // does not bother to interpret the bytes from a record
45 class single_value_reader {
47 typedef std::string value_type;
49 constexpr single_value_reader(std::string *px, size_t max_bytes_read)
50 : px(px), max_bytes_read(max_bytes_read) {}
52 template <typename StringAllocator>
54 operator()(const uint8_t *data, size_t sz, StringAllocator &sa)
56 const size_t readsz = std::min(sz, max_bytes_read);
57 px->assign((const char *) data, readsz);
67 inline const std::string &
73 template <typename StringAllocator>
75 dup(const std::string &vdup, StringAllocator &sa)
82 size_t max_bytes_read;
87 typedef std::string value_type;
89 constexpr value_reader(size_t max_bytes_read)
90 : px(nullptr), max_bytes_read(max_bytes_read) {}
92 template <typename StringAllocator>
94 operator()(const uint8_t *data, size_t sz, StringAllocator &sa)
97 const size_t readsz = std::min(sz, max_bytes_read);
98 px->assign((const char *) data, readsz);
108 inline const std::string &
114 template <typename StringAllocator>
116 dup(const std::string &vdup, StringAllocator &sa)
124 size_t max_bytes_read;
129 constexpr value_writer(const std::string *v) : v(v) {}
131 compute_needed(const uint8_t *buf, size_t sz)
133 return v ? v->size() : 0;
135 template <typename StringAllocator>
136 inline const std::string *
137 fully_materialize(bool stable_input, StringAllocator &sa)
139 if (stable_input || !v)
141 std::string * const ret = sa();
142 ret->assign(v->data(), v->size());
146 // input [buf, buf+sz) is old value
148 operator()(uint8_t *buf, size_t sz)
152 NDB_MEMCPY(buf, v->data(), v->size());
155 const std::string *v;
159 tuple_writer(dbtuple::TupleWriterMode mode, const void *v, uint8_t *p, size_t sz)
161 const std::string * const vx = reinterpret_cast<const std::string *>(v);
163 case dbtuple::TUPLE_WRITER_NEEDS_OLD_VALUE:
165 case dbtuple::TUPLE_WRITER_COMPUTE_NEEDED:
166 case dbtuple::TUPLE_WRITER_COMPUTE_DELTA_NEEDED:
168 case dbtuple::TUPLE_WRITER_DO_WRITE:
169 case dbtuple::TUPLE_WRITER_DO_DELTA_WRITE:
170 NDB_MEMCPY(p, vx->data(), vx->size());
173 ALWAYS_ASSERT(false);
177 typedef std::string Key;
178 typedef key_reader KeyReader;
179 typedef key_writer KeyWriter;
180 typedef std::string Value;
181 typedef single_value_reader SingleValueReader;
182 typedef value_reader ValueReader;
183 typedef value_writer ValueWriter;
187 * This class implements a serializable, multi-version b-tree
189 * It presents mostly same interface as the underlying concurrent b-tree,
190 * but the interface is serializable. The main interface differences are,
191 * insert() and put() do not return a boolean value to indicate whether or not
192 * they caused the tree to mutate
194 * A txn_btree does not allow keys to map to NULL records, even though the
195 * underlying concurrent btree does- this simplifies some of the book-keeping
196 * Additionally, keys cannot map to zero length records.
198 * Note that the txn_btree *manages* the memory of both keys and values internally.
199 * See the specific notes on search()/insert() about memory ownership
201 template <template <typename> class Transaction>
202 class txn_btree : public base_txn_btree<Transaction, txn_btree_> {
203 typedef base_txn_btree<Transaction, txn_btree_> super_type;
206 //template <typename Traits>
207 //struct transaction {
208 // typedef Transaction<txn_btree_, Traits> type;
211 //template <typename Traits>
212 // using transaction = Transaction<txn_btree_, Traits>;
214 typedef typename super_type::string_type string_type;
215 typedef typename super_type::keystring_type keystring_type;
216 typedef typename super_type::size_type size_type;
218 typedef txn_btree_::Key key_type;
219 typedef txn_btree_::Value value_type;
220 typedef txn_btree_::KeyReader key_reader_type;
221 typedef txn_btree_::KeyWriter key_writer_type;
222 typedef txn_btree_::SingleValueReader single_value_reader_type;
223 typedef txn_btree_::ValueReader value_reader_type;
224 typedef txn_btree_::ValueWriter value_writer_type;
226 struct search_range_callback {
228 virtual ~search_range_callback() {}
229 virtual bool invoke(const keystring_type &k, const string_type &v) = 0;
234 template <typename T>
235 class type_callback_wrapper : public search_range_callback {
237 constexpr type_callback_wrapper(T *callback)
238 : callback(callback) {}
240 invoke(const keystring_type &k, const string_type &v)
242 return callback->operator()(k, v);
248 static inline ALWAYS_INLINE string_type
249 to_string_type(const varkey &k)
251 return string_type((const char *) k.data(), k.size());
254 template <typename Traits>
255 static inline const std::string *
256 stablize(Transaction<Traits> &t, const std::string &s)
258 if (Traits::stable_input_memory)
260 std::string * const px = t.string_allocator()();
265 template <typename Traits>
266 static inline const std::string *
267 stablize(Transaction<Traits> &t, const uint8_t *p, size_t sz)
271 std::string * const px = t.string_allocator()();
272 px->assign((const char *) p, sz);
276 template <typename Traits>
277 static inline const std::string *
278 stablize(Transaction<Traits> &t, const varkey &k)
280 return stablize(t, k.data(), k.size());
285 txn_btree(size_type value_size_hint = 128,
286 bool mostly_append = false,
287 const std::string &name = "<unknown>")
288 : super_type(value_size_hint, mostly_append, name)
291 template <typename Traits>
293 search(Transaction<Traits> &t,
296 size_t max_bytes_read = string_type::npos)
298 return search(t, to_string_type(k), v, max_bytes_read);
301 // either returns false or v is set to not-empty with value
302 // precondition: max_bytes_read > 0
303 template <typename Traits>
305 search(Transaction<Traits> &t,
308 size_type max_bytes_read = string_type::npos)
310 single_value_reader_type r(&v, max_bytes_read);
311 return this->do_search(t, k, r);
314 template <typename Traits>
316 search_range_call(Transaction<Traits> &t,
317 const key_type &lower,
318 const key_type *upper,
319 search_range_callback &callback,
320 size_type max_bytes_read = string_type::npos)
323 value_reader_type vr(max_bytes_read);
324 this->do_search_range_call(t, lower, upper, callback, kr, vr);
327 template <typename Traits>
329 rsearch_range_call(Transaction<Traits> &t,
330 const key_type &upper,
331 const key_type *lower,
332 search_range_callback &callback,
333 size_type max_bytes_read = string_type::npos)
336 value_reader_type vr(max_bytes_read);
337 this->do_rsearch_range_call(t, upper, lower, callback, kr, vr);
340 template <typename Traits>
342 search_range_call(Transaction<Traits> &t,
345 search_range_callback &callback,
346 size_type max_bytes_read = string_type::npos)
350 u = to_string_type(*upper);
351 search_range_call(t, to_string_type(lower),
352 upper ? &u : nullptr, callback, max_bytes_read);
355 template <typename Traits>
357 rsearch_range_call(Transaction<Traits> &t,
360 search_range_callback &callback,
361 size_type max_bytes_read = string_type::npos)
365 l = to_string_type(*lower);
366 rsearch_range_call(t, to_string_type(upper),
367 lower ? &l : nullptr, callback, max_bytes_read);
370 template <typename Traits, typename T>
372 search_range(Transaction<Traits> &t,
373 const key_type &lower,
374 const key_type *upper,
376 size_type max_bytes_read = string_type::npos)
378 type_callback_wrapper<T> w(&callback);
379 search_range_call(t, lower, upper, w, max_bytes_read);
382 template <typename Traits, typename T>
384 search_range(Transaction<Traits> &t,
388 size_type max_bytes_read = string_type::npos)
392 u = to_string_type(*upper);
393 search_range(t, to_string_type(lower),
394 upper ? &u : nullptr, callback, max_bytes_read);
397 template <typename Traits>
399 put(Transaction<Traits> &t, const key_type &k, const value_type &v)
401 INVARIANT(!v.empty());
403 t, stablize(t, k), stablize(t, v),
404 txn_btree_::tuple_writer, false);
407 template <typename Traits>
409 put(Transaction<Traits> &t, const varkey &k, const value_type &v)
411 INVARIANT(!v.empty());
413 t, stablize(t, k), stablize(t, v),
414 txn_btree_::tuple_writer, false);
417 template <typename Traits>
419 insert(Transaction<Traits> &t, const key_type &k, const value_type &v)
421 INVARIANT(!v.empty());
423 t, stablize(t, k), stablize(t, v),
424 txn_btree_::tuple_writer, true);
427 // insert() methods below are for legacy use
429 template <typename Traits>
431 insert(Transaction<Traits> &t, const key_type &k, const uint8_t *v, size_type sz)
436 t, stablize(t, k), stablize(t, v, sz),
437 txn_btree_::tuple_writer, true);
440 template <typename Traits>
442 insert(Transaction<Traits> &t, const varkey &k, const uint8_t *v, size_type sz)
447 t, stablize(t, k), stablize(t, v, sz),
448 txn_btree_::tuple_writer, true);
451 template <typename Traits, typename T>
453 insert_object(Transaction<Traits> &t, const varkey &k, const T &obj)
455 insert(t, k, (const uint8_t *) &obj, sizeof(obj));
458 template <typename Traits, typename T>
460 insert_object(Transaction<Traits> &t, const key_type &k, const T &obj)
462 insert(t, k, (const uint8_t *) &obj, sizeof(obj));
465 template <typename Traits>
467 remove(Transaction<Traits> &t, const key_type &k)
469 this->do_tree_put(t, stablize(t, k), nullptr, txn_btree_::tuple_writer, false);
472 template <typename Traits>
474 remove(Transaction<Traits> &t, const varkey &k)
476 this->do_tree_put(t, stablize(t, k), nullptr, txn_btree_::tuple_writer, false);
483 #endif /* _NDB_TXN_BTREE_H_ */