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