l4/pkg/cxx/lib/tl/include/avl_map

   1 // vi:ft=cpp
   2 /**
   3  * \file
   4  * \brief AVL map
   5  */
   6 /*
   7  * (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>
   8  *     economic rights: Technische Universität Dresden (Germany)
   9  *
  10  * This file is part of TUD:OS and distributed under the terms of the
  11  * GNU General Public License 2.
  12  * Please see the COPYING-GPL-2 file for details.
  13  *
  14  * As a special exception, you may use this file as part of a free software
  15  * library without restriction.  Specifically, if other files instantiate
  16  * templates or use macros or inline functions from this file, or you compile
  17  * this file and link it with other files to produce an executable, this
  18  * file does not by itself cause the resulting executable to be covered by
  19  * the GNU General Public License.  This exception does not however
  20  * invalidate any other reasons why the executable file might be covered by
  21  * the GNU General Public License.
  22  */
  23
  24 #pragma once
  25
  26 #include <l4/cxx/std_alloc>
  27 #include <l4/cxx/std_ops>
  28 #include <l4/cxx/pair>
  29 #include <l4/cxx/avl_set>
  30
  31 namespace cxx {
  32
  33 /**
  34  * \ingroup cxx_api
  35  * \brief AVL tree based associative container.
  36  * \param Key Type of the key values.
  37  * \param Data Type of the data values.
  38  * \param Compare Type comparison functor for the key values.
  39  * \param Alloc Type of the allocator used for the nodes.
  40  */
  41 template< typename Key, typename Data,
  42   template<typename A> class Compare = Lt_functor,
  43   template<typename B> class Alloc = New_allocator >
  44 class Avl_map : public Avl_set<Pair<Key, Data>,
  45   Pair_first_compare< Compare<Key>, Pair<Key, Data> >,
  46   Alloc>
  47 {
  48 private:
  49   typedef Pair<Key, Data> Local_item_type;
  50   typedef Pair_first_compare< Compare<Key>, Local_item_type > Local_compare;
  51   typedef Avl_set<Local_item_type, Local_compare, Alloc> Base_type;
  52
  53 public:
  54   /// Type of the comparison functor.
  55   typedef Compare<Key> Key_compare;
  56   /// Type of the key values.
  57   typedef Key Key_type;
  58   /// Type of the data values.
  59   typedef Data Data_type;
  60   /// Return type for find.
  61   typedef typename Base_type::Node Node;
  62   /// Type of the allocator
  63   typedef typename Base_type::Node_allocator Node_allocator;
  64
  65   typedef typename Base_type::Iterator Iterator;
  66   typedef typename Base_type::Iterator iterator;
  67   typedef typename Base_type::Const_iterator Const_iterator;
  68   typedef typename Base_type::Const_iterator const_iterator;
  69   typedef typename Base_type::Rev_iterator Rev_iterator;
  70   typedef typename Base_type::Rev_iterator reverse_iterator;
  71   typedef typename Base_type::Const_rev_iterator Const_rev_iterator;
  72   typedef typename Base_type::Const_rev_iterator const_reverse_iterator;
  73
  74   /**
  75    * \brief Create an empty AVL-tree based map.
  76    * \param comp The comparison functor.
  77    * \param alloc The node allocator.
  78    */
  79   Avl_map(Node_allocator const &alloc = Node_allocator())
  80     : Base_type(alloc)
  81   {}
  82
  83   /**
  84    * \brief Insert a <key, data> pair into the map.
  85    * \param key The key value.
  86    * \param data The data value to insert.
  87    */
  88   cxx::Pair<Iterator, int> insert(Key_type const &key, Data_type const &data)
  89   { return Base_type::insert(Pair<Key_type, Data_type>(key, data)); }
  90
  91   /**
  92    * \brief Find a <key, data> pair for a given key.
  93    * \param key The key value to use for the lookup.
  94    */
  95   Node find_node(Key_type const &key) const
  96   { return Base_type::find_node(Local_item_type(key, Data_type())); }
  97
  98   /**
  99    * \brief Find the first node greater or equal to \a key.
 100    * \param key the key to look for.
 101    * \return The first node greater or equal to \a key.
 102    */
 103   Node lower_bound_node(Key_type const &key) const
 104   { return Base_type::lower_bound_node(Local_item_type(key, Data_type())); }
 105
 106   /**
 107    * \brief Find a <key, data> pair for a given key.
 108    * \param key The key value to use for the lookup.
 109    */
 110   Iterator find(Key_type const &key) const
 111   { return Base_type::find(Local_item_type(key, Data_type())); }
 112
 113   /**
 114    * \brief Remove the <key, data> pair for the given key.
 115    * \param key The key value of the pair that shall be removed.
 116    */
 117   int remove(Key_type const &key)
 118   { return Base_type::remove(Local_item_type(key, Data_type())); }
 119
 120   /**
 121    * \brief Removed the element \a key.
 122    * \see remove()
 123    */
 124   int erase(Key_type const &key)
 125   { return remove(key); }
 126
 127   /**
 128    * \brief Get the data for the given key.
 129    * \param key The key value to use for lookup.
 130    * \pre A <key, data> pair for the given key value must exist.
 131    */
 132   Data_type const &operator [] (Key_type const &key) const
 133   { return find_node(key)->second; }
 134
 135   /**
 136    * \brief Get the data for the given key.
 137    * \param key The key value to use for lookup.
 138    * \pre A <key, data> pair for the given key value must exist.
 139    */
 140   Data_type &operator [] (Key_type const &key)
 141   {
 142     Node n = find_node(key);
 143     if (n)
 144       return const_cast<Data_type&>(n->second);
 145     else
 146       return insert(key, Data_type()).first->second;
 147   }
 148 };
 149
 150 }
 151