mariadb-columnstore-engine/utils/joiner/btree_container.h

// Copyright 2013 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#pragma once

#include <iosfwd>
#include <utility>

#include "btree.h"

namespace btree
{
// A common base class for btree_set, btree_map, btree_multiset and
// btree_multimap.
template <typename Tree>
class btree_container
{
  typedef btree_container<Tree> self_type;

 public:
  typedef typename Tree::params_type params_type;
  typedef typename Tree::key_type key_type;
  typedef typename Tree::value_type value_type;
  typedef typename Tree::key_compare key_compare;
  typedef typename Tree::allocator_type allocator_type;
  typedef typename Tree::pointer pointer;
  typedef typename Tree::const_pointer const_pointer;
  typedef typename Tree::reference reference;
  typedef typename Tree::const_reference const_reference;
  typedef typename Tree::size_type size_type;
  typedef typename Tree::difference_type difference_type;
  typedef typename Tree::iterator iterator;
  typedef typename Tree::const_iterator const_iterator;
  typedef typename Tree::reverse_iterator reverse_iterator;
  typedef typename Tree::const_reverse_iterator const_reverse_iterator;

 public:
  // Default constructor.
  btree_container(const key_compare& comp, const allocator_type& alloc) : tree_(comp, alloc)
  {
  }

  // Copy constructor.
  btree_container(const self_type& x) : tree_(x.tree_)
  {
  }

  // Iterator routines.
  iterator begin()
  {
    return tree_.begin();
  }
  const_iterator begin() const
  {
    return tree_.begin();
  }
  iterator end()
  {
    return tree_.end();
  }
  const_iterator end() const
  {
    return tree_.end();
  }
  reverse_iterator rbegin()
  {
    return tree_.rbegin();
  }
  const_reverse_iterator rbegin() const
  {
    return tree_.rbegin();
  }
  reverse_iterator rend()
  {
    return tree_.rend();
  }
  const_reverse_iterator rend() const
  {
    return tree_.rend();
  }

  // Lookup routines.
  iterator lower_bound(const key_type& key)
  {
    return tree_.lower_bound(key);
  }
  const_iterator lower_bound(const key_type& key) const
  {
    return tree_.lower_bound(key);
  }
  iterator upper_bound(const key_type& key)
  {
    return tree_.upper_bound(key);
  }
  const_iterator upper_bound(const key_type& key) const
  {
    return tree_.upper_bound(key);
  }
  std::pair<iterator, iterator> equal_range(const key_type& key)
  {
    return tree_.equal_range(key);
  }
  std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
  {
    return tree_.equal_range(key);
  }

  // Utility routines.
  void clear()
  {
    tree_.clear();
  }
  void swap(self_type& x)
  {
    tree_.swap(x.tree_);
  }
  void dump(std::ostream& os) const
  {
    tree_.dump(os);
  }
  void verify() const
  {
    tree_.verify();
  }

  // Size routines.
  size_type size() const
  {
    return tree_.size();
  }
  size_type max_size() const
  {
    return tree_.max_size();
  }
  bool empty() const
  {
    return tree_.empty();
  }
  size_type height() const
  {
    return tree_.height();
  }
  size_type internal_nodes() const
  {
    return tree_.internal_nodes();
  }
  size_type leaf_nodes() const
  {
    return tree_.leaf_nodes();
  }
  size_type nodes() const
  {
    return tree_.nodes();
  }
  size_type bytes_used() const
  {
    return tree_.bytes_used();
  }
  static double average_bytes_per_value()
  {
    return Tree::average_bytes_per_value();
  }
  double fullness() const
  {
    return tree_.fullness();
  }
  double overhead() const
  {
    return tree_.overhead();
  }

  bool operator==(const self_type& x) const
  {
    if (size() != x.size())
    {
      return false;
    }

    for (const_iterator i = begin(), xi = x.begin(); i != end(); ++i, ++xi)
    {
      if (*i != *xi)
      {
        return false;
      }
    }

    return true;
  }

  bool operator!=(const self_type& other) const
  {
    return !operator==(other);
  }

 protected:
  Tree tree_;
};

template <typename T>
inline std::ostream& operator<<(std::ostream& os, const btree_container<T>& b)
{
  b.dump(os);
  return os;
}

// A common base class for btree_set and safe_btree_set.
template <typename Tree>
class btree_unique_container : public btree_container<Tree>
{
  typedef btree_unique_container<Tree> self_type;
  typedef btree_container<Tree> super_type;

 public:
  typedef typename Tree::key_type key_type;
  typedef typename Tree::value_type value_type;
  typedef typename Tree::size_type size_type;
  typedef typename Tree::key_compare key_compare;
  typedef typename Tree::allocator_type allocator_type;
  typedef typename Tree::iterator iterator;
  typedef typename Tree::const_iterator const_iterator;

 public:
  // Default constructor.
  btree_unique_container(const key_compare& comp = key_compare(),
                         const allocator_type& alloc = allocator_type())
   : super_type(comp, alloc)
  {
  }

  // Copy constructor.
  btree_unique_container(const self_type& x) : super_type(x)
  {
  }

  // Range constructor.
  template <class InputIterator>
  btree_unique_container(InputIterator b, InputIterator e, const key_compare& comp = key_compare(),
                         const allocator_type& alloc = allocator_type())
   : super_type(comp, alloc)
  {
    insert(b, e);
  }

  // Lookup routines.
  iterator find(const key_type& key)
  {
    return this->tree_.find_unique(key);
  }
  const_iterator find(const key_type& key) const
  {
    return this->tree_.find_unique(key);
  }
  size_type count(const key_type& key) const
  {
    return this->tree_.count_unique(key);
  }

  // Insertion routines.
  std::pair<iterator, bool> insert(const value_type& x)
  {
    return this->tree_.insert_unique(x);
  }
  iterator insert(iterator position, const value_type& x)
  {
    return this->tree_.insert_unique(position, x);
  }
  template <typename InputIterator>
  void insert(InputIterator b, InputIterator e)
  {
    this->tree_.insert_unique(b, e);
  }

  // Deletion routines.
  int erase(const key_type& key)
  {
    return this->tree_.erase_unique(key);
  }
  // Erase the specified iterator from the btree. The iterator must be valid
  // (i.e. not equal to end()).  Return an iterator pointing to the node after
  // the one that was erased (or end() if none exists).
  iterator erase(const iterator& iter)
  {
    return this->tree_.erase(iter);
  }
  void erase(const iterator& first, const iterator& last)
  {
    this->tree_.erase(first, last);
  }
};

// A common base class for btree_map and safe_btree_map.
template <typename Tree>
class btree_map_container : public btree_unique_container<Tree>
{
  typedef btree_map_container<Tree> self_type;
  typedef btree_unique_container<Tree> super_type;

 public:
  typedef typename Tree::key_type key_type;
  typedef typename Tree::data_type data_type;
  typedef typename Tree::value_type value_type;
  typedef typename Tree::mapped_type mapped_type;
  typedef typename Tree::key_compare key_compare;
  typedef typename Tree::allocator_type allocator_type;

 private:
  // A pointer-like object which only generates its value when
  // dereferenced. Used by operator[] to avoid constructing an empty data_type
  // if the key already exists in the map.
  struct generate_value
  {
    generate_value(const key_type& k) : key(k)
    {
    }
    value_type operator*() const
    {
      return std::make_pair(key, data_type());
    }
    const key_type& key;
  };

 public:
  // Default constructor.
  btree_map_container(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())
   : super_type(comp, alloc)
  {
  }

  // Copy constructor.
  btree_map_container(const self_type& x) : super_type(x)
  {
  }

  // Range constructor.
  template <class InputIterator>
  btree_map_container(InputIterator b, InputIterator e, const key_compare& comp = key_compare(),
                      const allocator_type& alloc = allocator_type())
   : super_type(b, e, comp, alloc)
  {
  }

  // Insertion routines.
  data_type& operator[](const key_type& key)
  {
    return this->tree_.insert_unique(key, generate_value(key)).first->second;
  }
};

// A common base class for btree_multiset and btree_multimap.
template <typename Tree>
class btree_multi_container : public btree_container<Tree>
{
  typedef btree_multi_container<Tree> self_type;
  typedef btree_container<Tree> super_type;

 public:
  typedef typename Tree::key_type key_type;
  typedef typename Tree::value_type value_type;
  typedef typename Tree::size_type size_type;
  typedef typename Tree::key_compare key_compare;
  typedef typename Tree::allocator_type allocator_type;
  typedef typename Tree::iterator iterator;
  typedef typename Tree::const_iterator const_iterator;

 public:
  // Default constructor.
  btree_multi_container(const key_compare& comp = key_compare(),
                        const allocator_type& alloc = allocator_type())
   : super_type(comp, alloc)
  {
  }

  // Copy constructor.
  btree_multi_container(const self_type& x) : super_type(x)
  {
  }

  // Range constructor.
  template <class InputIterator>
  btree_multi_container(InputIterator b, InputIterator e, const key_compare& comp = key_compare(),
                        const allocator_type& alloc = allocator_type())
   : super_type(comp, alloc)
  {
    insert(b, e);
  }

  // Lookup routines.
  iterator find(const key_type& key)
  {
    return this->tree_.find_multi(key);
  }
  const_iterator find(const key_type& key) const
  {
    return this->tree_.find_multi(key);
  }
  size_type count(const key_type& key) const
  {
    return this->tree_.count_multi(key);
  }

  // Insertion routines.
  iterator insert(const value_type& x)
  {
    return this->tree_.insert_multi(x);
  }
  iterator insert(iterator position, const value_type& x)
  {
    return this->tree_.insert_multi(position, x);
  }
  template <typename InputIterator>
  void insert(InputIterator b, InputIterator e)
  {
    this->tree_.insert_multi(b, e);
  }

  // Deletion routines.
  int erase(const key_type& key)
  {
    return this->tree_.erase_multi(key);
  }
  // Erase the specified iterator from the btree. The iterator must be valid
  // (i.e. not equal to end()).  Return an iterator pointing to the node after
  // the one that was erased (or end() if none exists).
  iterator erase(const iterator& iter)
  {
    return this->tree_.erase(iter);
  }
  void erase(const iterator& first, const iterator& last)
  {
    this->tree_.erase(first, last);
  }
};

}  // namespace btree