1// vi:set ft=cpp: -*- Mode: C++ -*-
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
31namespace cxx {
32namespace Bits {
33
34/// Key-getter for Avl_map
35template<typename KEY_TYPE>
36struct Avl_map_get_key
37{
38  typedef KEY_TYPE Key_type;
39  template<typename NODE>
40  static Key_type const &key_of(NODE const *n)
41  { return n->item.first; }
42};
43}
44
45/**
46 * AVL tree based associative container.
47 *
48 * \tparam KEY_TYPE   Type of the key values.
49 * \tparam DATA_TYPE  Type of the data values.
50 * \tparam COMPARE    Type comparison functor for the key values.
51 * \tparam ALLOC      Type of the allocator used for the nodes.
52 */
53template< typename KEY_TYPE, typename DATA_TYPE,
54  template<typename A> class COMPARE = Lt_functor,
55  template<typename B> class ALLOC = New_allocator >
56class Avl_map :
57  public Bits::Base_avl_set<Pair<KEY_TYPE, DATA_TYPE>,
58                            COMPARE<KEY_TYPE>, ALLOC,
59                            Bits::Avl_map_get_key<KEY_TYPE> >
60{
61private:
62  typedef Pair<KEY_TYPE, DATA_TYPE> Local_item_type;
63  typedef Bits::Base_avl_set<Local_item_type, COMPARE<KEY_TYPE>, ALLOC,
64                             Bits::Avl_map_get_key<KEY_TYPE> > Base_type;
65
66public:
67  /// Type of the comparison functor.
68  typedef COMPARE<KEY_TYPE> Key_compare;
69  /// Type of the key values.
70  typedef KEY_TYPE Key_type;
71  /// Type of the data values.
72  typedef DATA_TYPE Data_type;
73  /// Return type for find.
74  typedef typename Base_type::Node Node;
75  /// Type of the allocator
76  typedef typename Base_type::Node_allocator Node_allocator;
77
78  typedef typename Base_type::Iterator Iterator;
79  typedef typename Base_type::Iterator iterator;
80  typedef typename Base_type::Const_iterator Const_iterator;
81  typedef typename Base_type::Const_iterator const_iterator;
82  typedef typename Base_type::Rev_iterator Rev_iterator;
83  typedef typename Base_type::Rev_iterator reverse_iterator;
84  typedef typename Base_type::Const_rev_iterator Const_rev_iterator;
85  typedef typename Base_type::Const_rev_iterator const_reverse_iterator;
86
87  /**
88   * \brief Create an empty AVL-tree based map.
89   * \param alloc The node allocator.
90   */
91  Avl_map(Node_allocator const &alloc = Node_allocator())
92    : Base_type(alloc)
93  {}
94
95  /**
96   * Insert a <key, data> pair into the map.
97   *
98   * \param key   The key value.
99   * \param data  The data value to insert.
100   *
101   * \return A pair of iterator (`first`) and return value (`second`).
102   *         `second` will be 0 if the element was inserted into the set
103   *         and `-#E_exist` if the key was already in the set and the
104   *         set was therefore not updated.
105   *         In both cases, `first` contains an iterator that points to
106   *         the element.
107   *         `second` may also be `-#E_nomem` when memory for the new node
108   *         could not be allocated. `first` is then invalid.
109   */
110  cxx::Pair<Iterator, int> insert(Key_type const &key, Data_type const &data)
111  { return Base_type::insert(Pair<Key_type, Data_type>(key, data)); }
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 this->find_node(key)->second; }
120
121  /**
122   * Get or insert data for the given key.
123   *
124   * \param key The key value to use for lookup.
125   *
126   * \return If the item already exists, a reference to the data item.
127   *         Otherwise a new data item is default-constructed and inserted
128   *         under the given key before a reference is returned.
129   */
130  Data_type &operator [] (Key_type const &key)
131  {
132    Node n = this->find_node(key);
133    if (n)
134      return const_cast<Data_type&>(n->second);
135    else
136      return insert(key, Data_type()).first->second;
137  }
138};
139
140}
141
142