compiler2/map.hh

   1 /******************************************************************************
   2  * Copyright (c) 2000-2016 Ericsson Telecom AB
   3  * All rights reserved. This program and the accompanying materials
   4  * are made available under the terms of the Eclipse Public License v1.0
   5  * which accompanies this distribution, and is available at
   6  * http://www.eclipse.org/legal/epl-v10.html
   7  *
   8  * Contributors:
   9  *   Balasko, Jeno
  10  *   Delic, Adam
  11  *   Forstner, Matyas
  12  *   Gecse, Roland
  13  *   Koppany, Csaba
  14  *   Raduly, Csaba
  15  *   Szabados, Kristof
  16  *   Szabo, Janos Zoltan – initial implementation
  17  *
  18  ******************************************************************************/
  19 #ifndef _Common_map_HH
  20 #define _Common_map_HH
  21
  22 #include "error.h"
  23 #include "../common/dbgnew.hh"
  24
  25 /**
  26  * This container associates a \e key with its elements, and is
  27  * optimized to access the elements referenced by their keys.
  28  * The keys -- in contrast with the elements -- are owned by
  29  * the container. The keys in this container are unique.
  30  *
  31  * Accessing an element by its key has logarithmic cost.
  32  * Adding or removing an element has linear cost (proportional to the number
  33  * of elements in the map).
  34  * \pre
  35  * \arg The type of the key (<em>T_key</em>) must be a type which has
  36  * equality operator (==)  and less-than operator (<). Other
  37  * comparison operators are not assumed.
  38  * \arg \a T_key must have copy constructor and destructor.
  39  * \arg See also
  40  * \ref container_concepts "General rules and concepts about containers".
  41  *
  42  * There is a possibility to iterate through all
  43  * elements using integral indices. This index of an element can
  44  * change when inserting/deleting other elements. Accessing elements
  45  * by this integral index is not cost-optimal.
  46  *
  47  * \ingroup containers
  48  */
  49 template<class T_key, class T>
  50 class map {
  51
  52 private:
  53
  54   struct map_struct {
  55     T_key   key;
  56     T      *dat;
  57     map_struct(const T_key& p_key, T *p_dat)
  58       : key(p_key), dat(p_dat) { }
  59     map_struct(const map_struct& other)
  60     : key(other.key), dat(other.dat) {}
  61   private:
  62     map_struct& operator=(const map_struct& other);
  63   };
  64
  65   size_t num_m; ///< Number of elements (size)
  66   size_t max_m; ///< Available storage (capacity)
  67   /// Cache for the last search result.
  68   /// This will remember the index of the element last searched for;
  69   /// thus after checking the existence of the item, reaching it
  70   /// won't be logarithmical but constant
  71   mutable size_t last_searched_key;
  72   /// Array of pointers to map data. It is kept sorted (ascending) by keys.
  73   map_struct **m_ptr;
  74
  75   static const size_t initial_size = 1, increment_factor = 2;
  76
  77   /** Copy constructor: DO NOT IMPLEMENT! */
  78   map(const map&);
  79   /** Copy assignment: DO NOT IMPLEMENT! */
  80   map& operator=(const map&);
  81
  82 public:
  83
  84   static const size_t max_map_length = -1;
  85
  86   /** Creates an empty map. */
  87   map() : num_m(0), max_m(0), last_searched_key(0), m_ptr(NULL) { }
  88
  89   /** Deallocates its memory, including the keys.
  90    * If the container is not empty, FATAL_ERROR occurs,
  91    * so before destructing, clear() must be invoked explicitly.
  92    */
  93   ~map() {
  94     if (num_m > 0) FATAL_ERROR("map:~map(): map is not empty");
  95     Free(m_ptr);
  96   }
  97
  98   /** Returns the number of elements in the container. */
  99   size_t size() const { return num_m; }
 100
 101   /** Returns true if the container has no elements. */
 102   bool empty() const { return num_m == 0; }
 103
 104   /** Erases the entire container. */
 105   void clear() {
 106     for (size_t r = 0; r < num_m; r++) delete m_ptr[r];
 107     num_m = 0;
 108     last_searched_key = 0;
 109   }
 110
 111   /** Adds the elem \a T identified by \a key to the container.
 112    * If an element with the given key already exists, FATAL_ERROR occurs. */
 113   void add(const T_key& key, T *elem) {
 114     size_t l = 0;
 115     if (num_m > 0) {
 116       size_t r = num_m - 1;
 117       while (l < r) { // binary search
 118         size_t m = l + (r - l) / 2;
 119         if (m_ptr[m]->key < key) l = m + 1;
 120         else r = m;
 121       }
 122       if (m_ptr[l]->key < key) l++;
 123       else if (m_ptr[l]->key == key)
 124         FATAL_ERROR("map::add(): key already exists");
 125       if (num_m >= max_m) {
 126         // Array is full
 127         if (num_m > max_m) FATAL_ERROR("map::add(): num_m > max_m");
 128         if (max_m <= max_map_length / increment_factor)
 129           max_m *= increment_factor; // room for doubling
 130         else if (max_m < max_map_length) max_m = max_map_length;
 131         else FATAL_ERROR("map::add(): cannot enlarge map");
 132         m_ptr = static_cast<map_struct**>
 133           (Realloc(m_ptr, max_m * sizeof(*m_ptr)));
 134       }
 135       memmove(m_ptr + l + 1, m_ptr + l, (num_m - l) * sizeof(*m_ptr));
 136     } else if (m_ptr == NULL) {
 137       max_m = initial_size;
 138       m_ptr = static_cast<map_struct**>(Malloc(initial_size * sizeof(*m_ptr)));
 139     }
 140     m_ptr[l] = new map_struct(key, elem);
 141     num_m++;
 142     last_searched_key = num_m;
 143   }
 144
 145   /** Returns the index of k within *m_ptr[] or num_m if key was not found */
 146   size_t find_key(const T_key& k) const {
 147     if (last_searched_key < num_m && m_ptr[last_searched_key]->key == k)
 148       return last_searched_key;
 149     else if (num_m == 0) return 0;
 150     size_t l = 0, r = num_m - 1;
 151     while (l < r) {
 152       size_t m = l + (r - l) / 2;
 153       if (m_ptr[m]->key < k) l = m + 1;
 154       else r = m;
 155     }
 156     if (m_ptr[l]->key == k) last_searched_key = l;
 157     else last_searched_key = num_m;
 158     return last_searched_key;
 159   }
 160
 161   /** Erases the element identified by \a key. If no such element,
 162    * then silently ignores the request. */
 163   void erase(const T_key& key) {
 164     size_t n = find_key(key);
 165     if (n < num_m) {
 166       delete m_ptr[n];
 167       num_m--;
 168       memmove(m_ptr + n, m_ptr + n + 1, (num_m - n) * sizeof(*m_ptr));
 169       last_searched_key = num_m;
 170     }
 171   }
 172
 173   /** Returns true if an element with the given \a key
 174    * already exists. */
 175   bool has_key(const T_key& key) const {
 176     return find_key(key) < num_m;
 177   }
 178
 179   /** Returns the copy of the key contained in the map.
 180    *
 181    * The copy of the key may be longer-lived than the argument.
 182    * They are otherwise identical (operator== would return true).
 183    *
 184    * @param \a key
 185    * @return copy of \a key contained in the map
 186    * @pre key must exist in the map
 187    */
 188   const T_key& get_key(const T_key& key) const {
 189     size_t n = find_key(key);
 190     if (n >= num_m) FATAL_ERROR("map::get_key() const: key not found");
 191     return m_ptr[n]->key;
 192   }
 193
 194   /** Returns the element identified by \a key.
 195    * If no such element, then a FATAL_ERROR occurs. */
 196   T *operator[](const T_key& key) const {
 197     size_t n = find_key(key);
 198     if (n >= num_m) FATAL_ERROR("map::operator[]() const: key not found");
 199     return m_ptr[n]->dat;
 200   }
 201
 202   /** Returns the element identified by \a key.
 203    * If no such element, then a FATAL_ERROR occurs.
 204    * \note This member can not be used to add new elements to
 205    * the collection.
 206    */
 207   T*& operator[](const T_key& key) {
 208     size_t n = find_key(key);
 209     if (n >= num_m) FATAL_ERROR("map::operator[]() const: key not found");
 210     return m_ptr[n]->dat;
 211   }
 212
 213   /** Returns the <em>n</em>th element. This is used to iterate through
 214    * the ordered list of elements. Elements are ordered by their keys.
 215    * If \a n >= size(), then a FATAL_ERROR occurs.
 216    * The key of the element is accessible via get_nth_key(). */
 217   T *get_nth_elem(size_t n) const {
 218     if (n >= num_m) FATAL_ERROR("map::get_nth_elem() const: index overflow");
 219     /* do not break the previous line, suncc doesn't like it... */
 220     return m_ptr[n]->dat;
 221   }
 222
 223   /** Returns the <em>n</em>th element. This is used to iterate through
 224    * the elements. If \a n >= size(), then a FATAL_ERROR occurs.
 225    * The key of the element is accessible via get_nth_key(). */
 226   T*& get_nth_elem(size_t n) {
 227     if (n >= num_m) FATAL_ERROR("map::get_nth_elem(): index overflow");
 228     return m_ptr[n]->dat;
 229   }
 230
 231   /** Returns the key of the <em>n</em>th element.
 232    * This is used to iterate through the keys of elements.
 233    * If \a n >= size(), then a FATAL_ERROR occurs.
 234    * \note There is only \c const version of this member. If you
 235    * want to modify the key of an element, you have to erase it from
 236    * the container, then add with the new key.
 237    */
 238   const T_key& get_nth_key(size_t n) const {
 239     if (n >= num_m) FATAL_ERROR("map::get_nth_key() const: index overflow");
 240     return m_ptr[n]->key;
 241   }
 242 };
 243
 244 #endif // _Common_map_HH