"Fossies" - the Fresh Open Source Software Archive

Member "xdelta3-3.1.0/cpp-btree/safe_btree.h" (26 Sep 2015, 12569 Bytes) of package /linux/misc/xdelta3-3.1.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "safe_btree.h" see the Fossies "Dox" file reference documentation.

    1 // Copyright 2013 Google Inc. All Rights Reserved.
    2 //
    3 // Licensed under the Apache License, Version 2.0 (the "License");
    4 // you may not use this file except in compliance with the License.
    5 // You may obtain a copy of the License at
    6 //
    7 //     http://www.apache.org/licenses/LICENSE-2.0
    8 //
    9 // Unless required by applicable law or agreed to in writing, software
   10 // distributed under the License is distributed on an "AS IS" BASIS,
   11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   12 // See the License for the specific language governing permissions and
   13 // limitations under the License.
   14 //
   15 // A safe_btree<> wraps around a btree<> and removes the caveat that insertion
   16 // and deletion invalidate iterators. A safe_btree<> maintains a generation
   17 // number that is incremented on every mutation. A safe_btree<>::iterator keeps
   18 // a pointer to the safe_btree<> it came from, the generation of the tree when
   19 // it was last validated and the key the underlying btree<>::iterator points
   20 // to. If an iterator is accessed and its generation differs from the tree
   21 // generation it is revalidated.
   22 //
   23 // References and pointers returned by safe_btree iterators are not safe.
   24 //
   25 // See the incorrect usage examples mentioned in safe_btree_set.h and
   26 // safe_btree_map.h.
   27 
   28 #ifndef UTIL_BTREE_SAFE_BTREE_H__
   29 #define UTIL_BTREE_SAFE_BTREE_H__
   30 
   31 #include <stddef.h>
   32 #include <iosfwd>
   33 #include <utility>
   34 
   35 #include "btree.h"
   36 
   37 namespace btree {
   38 
   39 template <typename Tree, typename Iterator>
   40 class safe_btree_iterator {
   41  public:
   42   typedef typename Iterator::key_type key_type;
   43   typedef typename Iterator::value_type value_type;
   44   typedef typename Iterator::size_type size_type;
   45   typedef typename Iterator::difference_type difference_type;
   46   typedef typename Iterator::pointer pointer;
   47   typedef typename Iterator::reference reference;
   48   typedef typename Iterator::const_pointer const_pointer;
   49   typedef typename Iterator::const_reference const_reference;
   50   typedef typename Iterator::iterator_category iterator_category;
   51   typedef typename Tree::iterator iterator;
   52   typedef typename Tree::const_iterator const_iterator;
   53   typedef safe_btree_iterator<Tree, Iterator> self_type;
   54 
   55   void update() const {
   56     if (iter_ != tree_->internal_btree()->end()) {
   57       // A positive generation indicates a valid key.
   58       generation_ = tree_->generation();
   59       key_ = iter_.key();
   60     } else {
   61       // Use a negative generation to indicate iter_ points to end().
   62       generation_ = -tree_->generation();
   63     }
   64   }
   65 
   66  public:
   67   safe_btree_iterator()
   68       : generation_(0),
   69         key_(),
   70         iter_(),
   71         tree_(NULL) {
   72   }
   73   safe_btree_iterator(const iterator &x)
   74       : generation_(x.generation()),
   75         key_(x.key()),
   76         iter_(x.iter()),
   77         tree_(x.tree()) {
   78   }
   79   safe_btree_iterator(Tree *tree, const Iterator &iter)
   80       : generation_(),
   81         key_(),
   82         iter_(iter),
   83         tree_(tree) {
   84     update();
   85   }
   86 
   87   Tree* tree() const { return tree_; }
   88   int64_t generation() const { return generation_; }
   89 
   90   Iterator* mutable_iter() const {
   91     if (generation_ != tree_->generation()) {
   92       if (generation_ > 0) {
   93         // This does the wrong thing for a multi{set,map}. If my iter was
   94         // pointing to the 2nd of 2 values with the same key, then this will
   95         // reset it to point to the first. This is why we don't provide a
   96         // safe_btree_multi{set,map}.
   97         iter_ = tree_->internal_btree()->lower_bound(key_);
   98         update();
   99       } else if (-generation_ != tree_->generation()) {
  100         iter_ = tree_->internal_btree()->end();
  101         generation_ = -tree_->generation();
  102       }
  103     }
  104     return &iter_;
  105   }
  106   const Iterator& iter() const {
  107     return *mutable_iter();
  108   }
  109 
  110   // Equality/inequality operators.
  111   bool operator==(const const_iterator &x) const {
  112     return iter() == x.iter();
  113   }
  114   bool operator!=(const const_iterator &x) const {
  115     return iter() != x.iter();
  116   }
  117 
  118   // Accessors for the key/value the iterator is pointing at.
  119   const key_type& key() const {
  120     return key_;
  121   }
  122   // This reference value is potentially invalidated by any non-const
  123   // method on the tree; it is NOT safe.
  124   reference operator*() const {
  125     assert(generation_ > 0);
  126     return iter().operator*();
  127   }
  128   // This pointer value is potentially invalidated by any non-const
  129   // method on the tree; it is NOT safe.
  130   pointer operator->() const {
  131     assert(generation_ > 0);
  132     return iter().operator->();
  133   }
  134 
  135   // Increment/decrement operators.
  136   self_type& operator++() {
  137     ++(*mutable_iter());
  138     update();
  139     return *this;
  140   }
  141   self_type& operator--() {
  142     --(*mutable_iter());
  143     update();
  144     return *this;
  145   }
  146   self_type operator++(int) {
  147     self_type tmp = *this;
  148     ++*this;
  149     return tmp;
  150   }
  151   self_type operator--(int) {
  152     self_type tmp = *this;
  153     --*this;
  154     return tmp;
  155   }
  156 
  157  private:
  158   // The generation of the tree when "iter" was updated.
  159   mutable int64_t generation_;
  160   // The key the iterator points to.
  161   mutable key_type key_;
  162   // The underlying iterator.
  163   mutable Iterator iter_;
  164   // The tree the iterator is associated with.
  165   Tree *tree_;
  166 };
  167 
  168 template <typename Params>
  169 class safe_btree {
  170   typedef safe_btree<Params> self_type;
  171 
  172   typedef btree<Params> btree_type;
  173   typedef typename btree_type::iterator tree_iterator;
  174   typedef typename btree_type::const_iterator tree_const_iterator;
  175 
  176  public:
  177   typedef typename btree_type::params_type params_type;
  178   typedef typename btree_type::key_type key_type;
  179   typedef typename btree_type::data_type data_type;
  180   typedef typename btree_type::mapped_type mapped_type;
  181   typedef typename btree_type::value_type value_type;
  182   typedef typename btree_type::key_compare key_compare;
  183   typedef typename btree_type::allocator_type allocator_type;
  184   typedef typename btree_type::pointer pointer;
  185   typedef typename btree_type::const_pointer const_pointer;
  186   typedef typename btree_type::reference reference;
  187   typedef typename btree_type::const_reference const_reference;
  188   typedef typename btree_type::size_type size_type;
  189   typedef typename btree_type::difference_type difference_type;
  190   typedef safe_btree_iterator<self_type, tree_iterator> iterator;
  191   typedef safe_btree_iterator<
  192     const self_type, tree_const_iterator> const_iterator;
  193   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  194   typedef std::reverse_iterator<iterator> reverse_iterator;
  195 
  196  public:
  197   // Default constructor.
  198   safe_btree(const key_compare &comp, const allocator_type &alloc)
  199       : tree_(comp, alloc),
  200         generation_(1) {
  201   }
  202 
  203   // Copy constructor.
  204   safe_btree(const self_type &x)
  205       : tree_(x.tree_),
  206         generation_(1) {
  207   }
  208 
  209   iterator begin() {
  210     return iterator(this, tree_.begin());
  211   }
  212   const_iterator begin() const {
  213     return const_iterator(this, tree_.begin());
  214   }
  215   iterator end() {
  216     return iterator(this, tree_.end());
  217   }
  218   const_iterator end() const {
  219     return const_iterator(this, tree_.end());
  220   }
  221   reverse_iterator rbegin() {
  222     return reverse_iterator(end());
  223   }
  224   const_reverse_iterator rbegin() const {
  225     return const_reverse_iterator(end());
  226   }
  227   reverse_iterator rend() {
  228     return reverse_iterator(begin());
  229   }
  230   const_reverse_iterator rend() const {
  231     return const_reverse_iterator(begin());
  232   }
  233 
  234   // Lookup routines.
  235   iterator lower_bound(const key_type &key) {
  236     return iterator(this, tree_.lower_bound(key));
  237   }
  238   const_iterator lower_bound(const key_type &key) const {
  239     return const_iterator(this, tree_.lower_bound(key));
  240   }
  241   iterator upper_bound(const key_type &key) {
  242     return iterator(this, tree_.upper_bound(key));
  243   }
  244   const_iterator upper_bound(const key_type &key) const {
  245     return const_iterator(this, tree_.upper_bound(key));
  246   }
  247   std::pair<iterator, iterator> equal_range(const key_type &key) {
  248     std::pair<tree_iterator, tree_iterator> p = tree_.equal_range(key);
  249     return std::make_pair(iterator(this, p.first),
  250                      iterator(this, p.second));
  251   }
  252   std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const {
  253     std::pair<tree_const_iterator, tree_const_iterator> p = tree_.equal_range(key);
  254     return std::make_pair(const_iterator(this, p.first),
  255                      const_iterator(this, p.second));
  256   }
  257   iterator find_unique(const key_type &key) {
  258     return iterator(this, tree_.find_unique(key));
  259   }
  260   const_iterator find_unique(const key_type &key) const {
  261     return const_iterator(this, tree_.find_unique(key));
  262   }
  263   iterator find_multi(const key_type &key) {
  264     return iterator(this, tree_.find_multi(key));
  265   }
  266   const_iterator find_multi(const key_type &key) const {
  267     return const_iterator(this, tree_.find_multi(key));
  268   }
  269   size_type count_unique(const key_type &key) const {
  270     return tree_.count_unique(key);
  271   }
  272   size_type count_multi(const key_type &key) const {
  273     return tree_.count_multi(key);
  274   }
  275 
  276   // Insertion routines.
  277   template <typename ValuePointer>
  278   std::pair<iterator, bool> insert_unique(const key_type &key, ValuePointer value) {
  279     std::pair<tree_iterator, bool> p = tree_.insert_unique(key, value);
  280     generation_ += p.second;
  281     return std::make_pair(iterator(this, p.first), p.second);
  282   }
  283   std::pair<iterator, bool> insert_unique(const value_type &v) {
  284     std::pair<tree_iterator, bool> p = tree_.insert_unique(v);
  285     generation_ += p.second;
  286     return std::make_pair(iterator(this, p.first), p.second);
  287   }
  288   iterator insert_unique(iterator position, const value_type &v) {
  289     tree_iterator tree_pos = position.iter();
  290     ++generation_;
  291     return iterator(this, tree_.insert_unique(tree_pos, v));
  292   }
  293   template <typename InputIterator>
  294   void insert_unique(InputIterator b, InputIterator e) {
  295     for (; b != e; ++b) {
  296       insert_unique(*b);
  297     }
  298   }
  299   iterator insert_multi(const value_type &v) {
  300     ++generation_;
  301     return iterator(this, tree_.insert_multi(v));
  302   }
  303   iterator insert_multi(iterator position, const value_type &v) {
  304     tree_iterator tree_pos = position.iter();
  305     ++generation_;
  306     return iterator(this, tree_.insert_multi(tree_pos, v));
  307   }
  308   template <typename InputIterator>
  309   void insert_multi(InputIterator b, InputIterator e) {
  310     for (; b != e; ++b) {
  311       insert_multi(*b);
  312     }
  313   }
  314   self_type& operator=(const self_type &x) {
  315     if (&x == this) {
  316       // Don't copy onto ourselves.
  317       return *this;
  318     }
  319     ++generation_;
  320     tree_ = x.tree_;
  321     return *this;
  322   }
  323 
  324   // Deletion routines.
  325   void erase(const iterator &begin, const iterator &end) {
  326     tree_.erase(begin.iter(), end.iter());
  327     ++generation_;
  328   }
  329   // Erase the specified iterator from the btree. The iterator must be valid
  330   // (i.e. not equal to end()).  Return an iterator pointing to the node after
  331   // the one that was erased (or end() if none exists).
  332   iterator erase(iterator iter) {
  333     tree_iterator res = tree_.erase(iter.iter());
  334     ++generation_;
  335     return iterator(this, res);
  336   }
  337   int erase_unique(const key_type &key) {
  338     int res = tree_.erase_unique(key);
  339     generation_ += res;
  340     return res;
  341   }
  342   int erase_multi(const key_type &key) {
  343     int res = tree_.erase_multi(key);
  344     generation_ += res;
  345     return res;
  346   }
  347 
  348   // Access to the underlying btree.
  349   btree_type* internal_btree() { return &tree_; }
  350   const btree_type* internal_btree() const { return &tree_; }
  351 
  352   // Utility routines.
  353   void clear() {
  354     ++generation_;
  355     tree_.clear();
  356   }
  357   void swap(self_type &x) {
  358     ++generation_;
  359     ++x.generation_;
  360     tree_.swap(x.tree_);
  361   }
  362   void dump(std::ostream &os) const {
  363     tree_.dump(os);
  364   }
  365   void verify() const {
  366     tree_.verify();
  367   }
  368   int64_t generation() const {
  369     return generation_;
  370   }
  371   key_compare key_comp() const { return tree_.key_comp(); }
  372 
  373   // Size routines.
  374   size_type size() const { return tree_.size(); }
  375   size_type max_size() const { return tree_.max_size(); }
  376   bool empty() const { return tree_.empty(); }
  377   size_type height() const { return tree_.height(); }
  378   size_type internal_nodes() const { return tree_.internal_nodes(); }
  379   size_type leaf_nodes() const { return tree_.leaf_nodes(); }
  380   size_type nodes() const { return tree_.nodes(); }
  381   size_type bytes_used() const { return tree_.bytes_used(); }
  382   static double average_bytes_per_value() {
  383     return btree_type::average_bytes_per_value();
  384   }
  385   double fullness() const { return tree_.fullness(); }
  386   double overhead() const { return tree_.overhead(); }
  387 
  388  private:
  389   btree_type tree_;
  390   int64_t generation_;
  391 };
  392 
  393 }  // namespace btree
  394 
  395 #endif  // UTIL_BTREE_SAFE_BTREE_H__