contrib/llvm/tools/lldb/include/lldb/Core/UniqueCStringMap.h

   1 //===-- UniqueCStringMap.h --------------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef liblldb_UniqueCStringMap_h_
  11 #define liblldb_UniqueCStringMap_h_
  12 #if defined(__cplusplus)
  13
  14 #include <assert.h>
  15 #include <algorithm>
  16 #include <vector>
  17
  18 #include "lldb/Core/RegularExpression.h"
  19
  20 namespace lldb_private {
  21
  22
  23
  24 //----------------------------------------------------------------------
  25 // Templatized uniqued string map.
  26 //
  27 // This map is useful for mapping unique C string names to values of
  28 // type T. Each "const char *" name added must be unique for a given
  29 // C string value. ConstString::GetCString() can provide such strings.
  30 // Any other string table that has guaranteed unique values can also
  31 // be used.
  32 //----------------------------------------------------------------------
  33 template <typename T>
  34 class UniqueCStringMap
  35 {
  36 public:
  37     struct Entry
  38     {
  39         Entry () :
  40             cstring(NULL),
  41             value()
  42         {
  43         }
  44
  45         Entry (const char *cstr) :
  46             cstring(cstr),
  47             value()
  48         {
  49         }
  50
  51         Entry (const char *cstr, const T&v) :
  52             cstring(cstr),
  53             value(v)
  54         {
  55         }
  56
  57         bool
  58         operator < (const Entry& rhs) const
  59         {
  60             return cstring < rhs.cstring;
  61         }
  62
  63         const char* cstring;
  64         T value;
  65     };
  66
  67     //------------------------------------------------------------------
  68     // Call this function multiple times to add a bunch of entries to
  69     // this map, then later call UniqueCStringMap<T>::Sort() before doing
  70     // any searches by name.
  71     //------------------------------------------------------------------
  72     void
  73     Append (const char *unique_cstr, const T& value)
  74     {
  75         m_map.push_back (typename UniqueCStringMap<T>::Entry(unique_cstr, value));
  76     }
  77
  78     void
  79     Append (const Entry &e)
  80     {
  81         m_map.push_back (e);
  82     }
  83
  84     void
  85     Clear ()
  86     {
  87         m_map.clear();
  88     }
  89
  90     //------------------------------------------------------------------
  91     // Call this function to always keep the map sorted when putting
  92     // entries into the map.
  93     //------------------------------------------------------------------
  94     void
  95     Insert (const char *unique_cstr, const T& value)
  96     {
  97         typename UniqueCStringMap<T>::Entry e(unique_cstr, value);
  98         m_map.insert (std::upper_bound (m_map.begin(), m_map.end(), e), e);
  99     }
 100
 101     void
 102     Insert (const Entry &e)
 103     {
 104         m_map.insert (std::upper_bound (m_map.begin(), m_map.end(), e), e);
 105     }
 106
 107     //------------------------------------------------------------------
 108     // Get an entries by index in a variety of forms.
 109     //
 110     // The caller is responsible for ensuring that the collection does
 111     // not change during while using the returned values.
 112     //------------------------------------------------------------------
 113     bool
 114     GetValueAtIndex (uint32_t idx, T &value) const
 115     {
 116         if (idx < m_map.size())
 117         {
 118             value = m_map[idx].value;
 119             return true;
 120         }
 121         return false;
 122     }
 123
 124     const char *
 125     GetCStringAtIndexUnchecked (uint32_t idx) const
 126     {
 127         return m_map[idx].cstring;
 128     }
 129
 130     // Use this function if you have simple types in your map that you
 131     // can easily copy when accessing values by index.
 132     T
 133     GetValueAtIndexUnchecked (uint32_t idx) const
 134     {
 135         return m_map[idx].value;
 136     }
 137
 138     // Use this function if you have complex types in your map that you
 139     // don't want to copy when accessing values by index.
 140     const T &
 141     GetValueRefAtIndexUnchecked (uint32_t idx) const
 142     {
 143         return m_map[idx].value;
 144     }
 145
 146     const char *
 147     GetCStringAtIndex (uint32_t idx) const
 148     {
 149         if (idx < m_map.size())
 150             return m_map[idx].cstring;
 151         return NULL;
 152     }
 153
 154     //------------------------------------------------------------------
 155     // Find the value for the unique string in the map.
 156     //
 157     // Return the value for \a unique_cstr if one is found, return
 158     // \a fail_value otherwise. This method works well for simple type
 159     // T values and only if there is a sensible failure value that can
 160     // be returned and that won't match any existing values.
 161     //------------------------------------------------------------------
 162     T
 163     Find (const char *unique_cstr, T fail_value) const
 164     {
 165         Entry search_entry (unique_cstr);
 166         const_iterator end = m_map.end();
 167         const_iterator pos = std::lower_bound (m_map.begin(), end, search_entry);
 168         if (pos != end)
 169         {
 170             if (pos->cstring == unique_cstr)
 171                 return pos->value;
 172         }
 173         return fail_value;
 174     }
 175     //------------------------------------------------------------------
 176     // Get a pointer to the first entry that matches "name". NULL will
 177     // be returned if there is no entry that matches "name".
 178     //
 179     // The caller is responsible for ensuring that the collection does
 180     // not change during while using the returned pointer.
 181     //------------------------------------------------------------------
 182     const Entry *
 183     FindFirstValueForName (const char *unique_cstr) const
 184     {
 185         Entry search_entry (unique_cstr);
 186         const_iterator end = m_map.end();
 187         const_iterator pos = std::lower_bound (m_map.begin(), end, search_entry);
 188         if (pos != end)
 189         {
 190             const char *pos_cstr = pos->cstring;
 191             if (pos_cstr == unique_cstr)
 192                 return &(*pos);
 193         }
 194         return NULL;
 195     }
 196
 197     //------------------------------------------------------------------
 198     // Get a pointer to the next entry that matches "name" from a
 199     // previously returned Entry pointer. NULL will be returned if there
 200     // is no subsequent entry that matches "name".
 201     //
 202     // The caller is responsible for ensuring that the collection does
 203     // not change during while using the returned pointer.
 204     //------------------------------------------------------------------
 205     const Entry *
 206     FindNextValueForName (const Entry *entry_ptr) const
 207     {
 208         if (!m_map.empty())
 209         {
 210             const Entry *first_entry = &m_map[0];
 211             const Entry *after_last_entry = first_entry + m_map.size();
 212             const Entry *next_entry = entry_ptr + 1;
 213             if (first_entry <= next_entry && next_entry < after_last_entry)
 214             {
 215                 if (next_entry->cstring == entry_ptr->cstring)
 216                     return next_entry;
 217             }
 218         }
 219         return NULL;
 220     }
 221
 222     size_t
 223     GetValues (const char *unique_cstr, std::vector<T> &values) const
 224     {
 225         const size_t start_size = values.size();
 226
 227         Entry search_entry (unique_cstr);
 228         const_iterator pos, end = m_map.end();
 229         for (pos = std::lower_bound (m_map.begin(), end, search_entry); pos != end; ++pos)
 230         {
 231             if (pos->cstring == unique_cstr)
 232                 values.push_back (pos->value);
 233             else
 234                 break;
 235         }
 236
 237         return values.size() - start_size;
 238     }
 239
 240     size_t
 241     GetValues (const RegularExpression& regex, std::vector<T> &values) const
 242     {
 243         const size_t start_size = values.size();
 244
 245         const_iterator pos, end = m_map.end();
 246         for (pos = m_map.begin(); pos != end; ++pos)
 247         {
 248             if (regex.Execute(pos->cstring))
 249                 values.push_back (pos->value);
 250         }
 251
 252         return values.size() - start_size;
 253     }
 254
 255     //------------------------------------------------------------------
 256     // Get the total number of entries in this map.
 257     //------------------------------------------------------------------
 258     size_t
 259     GetSize () const
 260     {
 261         return m_map.size();
 262     }
 263
 264
 265     //------------------------------------------------------------------
 266     // Returns true if this map is empty.
 267     //------------------------------------------------------------------
 268     bool
 269     IsEmpty() const
 270     {
 271         return m_map.empty();
 272     }
 273
 274     //------------------------------------------------------------------
 275     // Reserve memory for at least "n" entries in the map. This is
 276     // useful to call when you know you will be adding a lot of entries
 277     // using UniqueCStringMap::Append() (which should be followed by a
 278     // call to UniqueCStringMap::Sort()) or to UniqueCStringMap::Insert().
 279     //------------------------------------------------------------------
 280     void
 281     Reserve (size_t n)
 282     {
 283         m_map.reserve (n);
 284     }
 285
 286     //------------------------------------------------------------------
 287     // Sort the unsorted contents in this map. A typical code flow would
 288     // be:
 289     // size_t approximate_num_entries = ....
 290     // UniqueCStringMap<uint32_t> my_map;
 291     // my_map.Reserve (approximate_num_entries);
 292     // for (...)
 293     // {
 294     //      my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...)));
 295     // }
 296     // my_map.Sort();
 297     //------------------------------------------------------------------
 298     void
 299     Sort ()
 300     {
 301         std::sort (m_map.begin(), m_map.end());
 302     }
 303
 304     //------------------------------------------------------------------
 305     // Since we are using a vector to contain our items it will always
 306     // double its memory consumption as things are added to the vector,
 307     // so if you intend to keep a UniqueCStringMap around and have
 308     // a lot of entries in the map, you will want to call this function
 309     // to create a new vector and copy _only_ the exact size needed as
 310     // part of the finalization of the string map.
 311     //------------------------------------------------------------------
 312     void
 313     SizeToFit ()
 314     {
 315         if (m_map.size() < m_map.capacity())
 316         {
 317             collection temp (m_map.begin(), m_map.end());
 318             m_map.swap(temp);
 319         }
 320     }
 321
 322     size_t
 323     Erase (const char *unique_cstr)
 324     {
 325         size_t num_removed = 0;
 326         Entry search_entry (unique_cstr);
 327         iterator end = m_map.end();
 328         iterator begin = m_map.begin();
 329         iterator lower_pos = std::lower_bound (begin, end, search_entry);
 330         if (lower_pos != end)
 331         {
 332             if (lower_pos->cstring == unique_cstr)
 333             {
 334                 iterator upper_pos = std::upper_bound (lower_pos, end, search_entry);
 335                 if (lower_pos == upper_pos)
 336                 {
 337                     m_map.erase (lower_pos);
 338                     num_removed = 1;
 339                 }
 340                 else
 341                 {
 342                     num_removed = std::distance (lower_pos, upper_pos);
 343                     m_map.erase (lower_pos, upper_pos);
 344                 }
 345             }
 346         }
 347         return num_removed;
 348     }
 349 protected:
 350     typedef std::vector<Entry> collection;
 351     typedef typename collection::iterator iterator;
 352     typedef typename collection::const_iterator const_iterator;
 353     collection m_map;
 354 };
 355
 356
 357
 358 } // namespace lldb_private
 359
 360 #endif  // #if defined(__cplusplus)
 361 #endif  // liblldb_UniqueCStringMap_h_