compiler2/map.hh

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