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