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