silo/masstree/masstree.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_HH
  17 #define MASSTREE_HH
  18 #include "compiler.hh"
  19 #include "str.hh"
  20 #include "ksearch.hh"
  21
  22 namespace Masstree {
  23 using lcdf::Str;
  24 using lcdf::String;
  25
  26 template <typename T> class value_print;
  27
  28 template <int LW = 15, int IW = LW> struct nodeparams {
  29     static constexpr int leaf_width = LW;
  30     static constexpr int internode_width = IW;
  31     static constexpr bool concurrent = true;
  32     static constexpr bool prefetch = true;
  33     static constexpr int bound_method = bound_method_binary;
  34     static constexpr int debug_level = 0;
  35     static constexpr bool printable_keys = true;
  36     typedef uint64_t ikey_type;
  37 };
  38
  39 template <int LW, int IW> constexpr int nodeparams<LW, IW>::leaf_width;
  40 template <int LW, int IW> constexpr int nodeparams<LW, IW>::internode_width;
  41 template <int LW, int IW> constexpr int nodeparams<LW, IW>::debug_level;
  42
  43 template <typename P> class node_base;
  44 template <typename P> class leaf;
  45 template <typename P> class internode;
  46 template <typename P> class leafvalue;
  47 template <typename P> class key;
  48 template <typename P> class basic_table;
  49 template <typename P> class unlocked_tcursor;
  50 template <typename P> class tcursor;
  51
  52 template <typename P>
  53 class basic_table {
  54   public:
  55     typedef P param_type;
  56     typedef node_base<P> node_type;
  57     typedef leaf<P> leaf_type;
  58     typedef typename P::value_type value_type;
  59     typedef typename P::threadinfo_type threadinfo;
  60     typedef unlocked_tcursor<P> unlocked_cursor_type;
  61     typedef tcursor<P> cursor_type;
  62
  63     inline basic_table();
  64
  65     void initialize(threadinfo& ti);
  66     void destroy(threadinfo& ti);
  67
  68     inline node_type* root() const;
  69     inline node_type* fix_root();
  70
  71     bool get(Str key, value_type& value, threadinfo& ti) const;
  72
  73     template <typename F>
  74     int scan(Str firstkey, bool matchfirst, F& scanner, threadinfo& ti) const;
  75     template <typename F>
  76     int rscan(Str firstkey, bool matchfirst, F& scanner, threadinfo& ti) const;
  77
  78     template <typename F>
  79     inline int modify(Str key, F& f, threadinfo& ti);
  80     template <typename F>
  81     inline int modify_insert(Str key, F& f, threadinfo& ti);
  82
  83     inline void print(FILE* f = 0, int indent = 0) const;
  84
  85   private:
  86     node_type* root_;
  87
  88     template <typename H, typename F>
  89     int scan(H helper, Str firstkey, bool matchfirst,
  90              F& scanner, threadinfo& ti) const;
  91
  92     friend class unlocked_tcursor<P>;
  93     friend class tcursor<P>;
  94 };
  95
  96 } // namespace Masstree
  97 #endif