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
  13 // C Includes
  14 // C++ Includes
  15 #include <algorithm>
  16 #include <vector>
  17
  18 // Other libraries and framework includes
  19 // Project includes
  20 #include "lldb/Utility/ConstString.h"
  21 #include "lldb/Utility/RegularExpression.h"
  22
  23 namespace lldb_private {
  24
  25 //----------------------------------------------------------------------
  26 // Templatized uniqued string map.
  27 //
  28 // This map is useful for mapping unique C string names to values of type T.
  29 // Each "const char *" name added must be unique for a given
  30 // C string value. ConstString::GetCString() can provide such strings.
  31 // Any other string table that has guaranteed unique values can also be used.
  32 //----------------------------------------------------------------------
  33 template <typename T> class UniqueCStringMap {
  34 public:
  35   struct Entry {
  36     Entry() {}
  37
  38     Entry(ConstString cstr) : cstring(cstr), value() {}
  39
  40     Entry(ConstString cstr, const T &v) : cstring(cstr), value(v) {}
  41
  42     // This is only for uniqueness, not lexicographical ordering, so we can
  43     // just compare pointers.
  44     bool operator<(const Entry &rhs) const {
  45       return cstring.GetCString() < rhs.cstring.GetCString();
  46     }
  47
  48     ConstString cstring;
  49     T value;
  50   };
  51
  52   //------------------------------------------------------------------
  53   // Call this function multiple times to add a bunch of entries to this map,
  54   // then later call UniqueCStringMap<T>::Sort() before doing any searches by
  55   // name.
  56   //------------------------------------------------------------------
  57   void Append(ConstString unique_cstr, const T &value) {
  58     m_map.push_back(typename UniqueCStringMap<T>::Entry(unique_cstr, value));
  59   }
  60
  61   void Append(const Entry &e) { m_map.push_back(e); }
  62
  63   void Clear() { m_map.clear(); }
  64
  65   //------------------------------------------------------------------
  66   // Call this function to always keep the map sorted when putting entries into
  67   // the map.
  68   //------------------------------------------------------------------
  69   void Insert(ConstString unique_cstr, const T &value) {
  70     typename UniqueCStringMap<T>::Entry e(unique_cstr, value);
  71     m_map.insert(std::upper_bound(m_map.begin(), m_map.end(), e), e);
  72   }
  73
  74   void Insert(const Entry &e) {
  75     m_map.insert(std::upper_bound(m_map.begin(), m_map.end(), e), e);
  76   }
  77
  78   //------------------------------------------------------------------
  79   // Get an entries by index in a variety of forms.
  80   //
  81   // The caller is responsible for ensuring that the collection does not change
  82   // during while using the returned values.
  83   //------------------------------------------------------------------
  84   bool GetValueAtIndex(uint32_t idx, T &value) const {
  85     if (idx < m_map.size()) {
  86       value = m_map[idx].value;
  87       return true;
  88     }
  89     return false;
  90   }
  91
  92   ConstString GetCStringAtIndexUnchecked(uint32_t idx) const {
  93     return m_map[idx].cstring;
  94   }
  95
  96   // Use this function if you have simple types in your map that you can easily
  97   // copy when accessing values by index.
  98   T GetValueAtIndexUnchecked(uint32_t idx) const { return m_map[idx].value; }
  99
 100   // Use this function if you have complex types in your map that you don't
 101   // want to copy when accessing values by index.
 102   const T &GetValueRefAtIndexUnchecked(uint32_t idx) const {
 103     return m_map[idx].value;
 104   }
 105
 106   ConstString GetCStringAtIndex(uint32_t idx) const {
 107     return ((idx < m_map.size()) ? m_map[idx].cstring : ConstString());
 108   }
 109
 110   //------------------------------------------------------------------
 111   // Find the value for the unique string in the map.
 112   //
 113   // Return the value for \a unique_cstr if one is found, return \a fail_value
 114   // otherwise. This method works well for simple type
 115   // T values and only if there is a sensible failure value that can
 116   // be returned and that won't match any existing values.
 117   //------------------------------------------------------------------
 118   T Find(ConstString unique_cstr, T fail_value) const {
 119     Entry search_entry(unique_cstr);
 120     const_iterator end = m_map.end();
 121     const_iterator pos = std::lower_bound(m_map.begin(), end, search_entry);
 122     if (pos != end) {
 123       if (pos->cstring == unique_cstr)
 124         return pos->value;
 125     }
 126     return fail_value;
 127   }
 128
 129   //------------------------------------------------------------------
 130   // Get a pointer to the first entry that matches "name". nullptr will be
 131   // returned if there is no entry that matches "name".
 132   //
 133   // The caller is responsible for ensuring that the collection does not change
 134   // during while using the returned pointer.
 135   //------------------------------------------------------------------
 136   const Entry *FindFirstValueForName(ConstString unique_cstr) const {
 137     Entry search_entry(unique_cstr);
 138     const_iterator end = m_map.end();
 139     const_iterator pos = std::lower_bound(m_map.begin(), end, search_entry);
 140     if (pos != end && pos->cstring == unique_cstr)
 141       return &(*pos);
 142     return nullptr;
 143   }
 144
 145   //------------------------------------------------------------------
 146   // Get a pointer to the next entry that matches "name" from a previously
 147   // returned Entry pointer. nullptr will be returned if there is no subsequent
 148   // entry that matches "name".
 149   //
 150   // The caller is responsible for ensuring that the collection does not change
 151   // during while using the returned pointer.
 152   //------------------------------------------------------------------
 153   const Entry *FindNextValueForName(const Entry *entry_ptr) const {
 154     if (!m_map.empty()) {
 155       const Entry *first_entry = &m_map[0];
 156       const Entry *after_last_entry = first_entry + m_map.size();
 157       const Entry *next_entry = entry_ptr + 1;
 158       if (first_entry <= next_entry && next_entry < after_last_entry) {
 159         if (next_entry->cstring == entry_ptr->cstring)
 160           return next_entry;
 161       }
 162     }
 163     return nullptr;
 164   }
 165
 166   size_t GetValues(ConstString unique_cstr, std::vector<T> &values) const {
 167     const size_t start_size = values.size();
 168
 169     Entry search_entry(unique_cstr);
 170     const_iterator pos, end = m_map.end();
 171     for (pos = std::lower_bound(m_map.begin(), end, search_entry); pos != end;
 172          ++pos) {
 173       if (pos->cstring == unique_cstr)
 174         values.push_back(pos->value);
 175       else
 176         break;
 177     }
 178
 179     return values.size() - start_size;
 180   }
 181
 182   size_t GetValues(const RegularExpression &regex,
 183                    std::vector<T> &values) const {
 184     const size_t start_size = values.size();
 185
 186     const_iterator pos, end = m_map.end();
 187     for (pos = m_map.begin(); pos != end; ++pos) {
 188       if (regex.Execute(pos->cstring.GetCString()))
 189         values.push_back(pos->value);
 190     }
 191
 192     return values.size() - start_size;
 193   }
 194
 195   //------------------------------------------------------------------
 196   // Get the total number of entries in this map.
 197   //------------------------------------------------------------------
 198   size_t GetSize() const { return m_map.size(); }
 199
 200   //------------------------------------------------------------------
 201   // Returns true if this map is empty.
 202   //------------------------------------------------------------------
 203   bool IsEmpty() const { return m_map.empty(); }
 204
 205   //------------------------------------------------------------------
 206   // Reserve memory for at least "n" entries in the map. This is useful to call
 207   // when you know you will be adding a lot of entries using
 208   // UniqueCStringMap::Append() (which should be followed by a call to
 209   // UniqueCStringMap::Sort()) or to UniqueCStringMap::Insert().
 210   //------------------------------------------------------------------
 211   void Reserve(size_t n) { m_map.reserve(n); }
 212
 213   //------------------------------------------------------------------
 214   // Sort the unsorted contents in this map. A typical code flow would be:
 215   // size_t approximate_num_entries = ....
 216   // UniqueCStringMap<uint32_t> my_map;
 217   // my_map.Reserve (approximate_num_entries);
 218   // for (...)
 219   // {
 220   //      my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...)));
 221   // }
 222   // my_map.Sort();
 223   //------------------------------------------------------------------
 224   void Sort() { std::sort(m_map.begin(), m_map.end()); }
 225
 226   //------------------------------------------------------------------
 227   // Since we are using a vector to contain our items it will always double its
 228   // memory consumption as things are added to the vector, so if you intend to
 229   // keep a UniqueCStringMap around and have a lot of entries in the map, you
 230   // will want to call this function to create a new vector and copy _only_ the
 231   // exact size needed as part of the finalization of the string map.
 232   //------------------------------------------------------------------
 233   void SizeToFit() {
 234     if (m_map.size() < m_map.capacity()) {
 235       collection temp(m_map.begin(), m_map.end());
 236       m_map.swap(temp);
 237     }
 238   }
 239
 240   size_t Erase(ConstString unique_cstr) {
 241     size_t num_removed = 0;
 242     Entry search_entry(unique_cstr);
 243     iterator end = m_map.end();
 244     iterator begin = m_map.begin();
 245     iterator lower_pos = std::lower_bound(begin, end, search_entry);
 246     if (lower_pos != end) {
 247       if (lower_pos->cstring == unique_cstr) {
 248         iterator upper_pos = std::upper_bound(lower_pos, end, search_entry);
 249         if (lower_pos == upper_pos) {
 250           m_map.erase(lower_pos);
 251           num_removed = 1;
 252         } else {
 253           num_removed = std::distance(lower_pos, upper_pos);
 254           m_map.erase(lower_pos, upper_pos);
 255         }
 256       }
 257     }
 258     return num_removed;
 259   }
 260
 261 protected:
 262   typedef std::vector<Entry> collection;
 263   typedef typename collection::iterator iterator;
 264   typedef typename collection::const_iterator const_iterator;
 265   collection m_map;
 266 };
 267
 268 } // namespace lldb_private
 269
 270 #endif // liblldb_UniqueCStringMap_h_