contrib/llvm-project/lldb/include/lldb/Core/UniqueCStringMap.h

   1 //===-- UniqueCStringMap.h --------------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef liblldb_UniqueCStringMap_h_
  10 #define liblldb_UniqueCStringMap_h_
  11
  12 #include <algorithm>
  13 #include <vector>
  14
  15 #include "lldb/Utility/ConstString.h"
  16 #include "lldb/Utility/RegularExpression.h"
  17
  18 namespace lldb_private {
  19
  20 // Templatized uniqued string map.
  21 //
  22 // This map is useful for mapping unique C string names to values of type T.
  23 // Each "const char *" name added must be unique for a given
  24 // C string value. ConstString::GetCString() can provide such strings.
  25 // Any other string table that has guaranteed unique values can also be used.
  26 template <typename T> class UniqueCStringMap {
  27 public:
  28   struct Entry {
  29     Entry(ConstString cstr, const T &v) : cstring(cstr), value(v) {}
  30
  31     ConstString cstring;
  32     T value;
  33   };
  34
  35   // Call this function multiple times to add a bunch of entries to this map,
  36   // then later call UniqueCStringMap<T>::Sort() before doing any searches by
  37   // name.
  38   void Append(ConstString unique_cstr, const T &value) {
  39     m_map.push_back(typename UniqueCStringMap<T>::Entry(unique_cstr, value));
  40   }
  41
  42   void Append(const Entry &e) { m_map.push_back(e); }
  43
  44   void Clear() { m_map.clear(); }
  45
  46   // Get an entries by index in a variety of forms.
  47   //
  48   // The caller is responsible for ensuring that the collection does not change
  49   // during while using the returned values.
  50   bool GetValueAtIndex(uint32_t idx, T &value) const {
  51     if (idx < m_map.size()) {
  52       value = m_map[idx].value;
  53       return true;
  54     }
  55     return false;
  56   }
  57
  58   ConstString GetCStringAtIndexUnchecked(uint32_t idx) const {
  59     return m_map[idx].cstring;
  60   }
  61
  62   // Use this function if you have simple types in your map that you can easily
  63   // copy when accessing values by index.
  64   T GetValueAtIndexUnchecked(uint32_t idx) const { return m_map[idx].value; }
  65
  66   // Use this function if you have complex types in your map that you don't
  67   // want to copy when accessing values by index.
  68   const T &GetValueRefAtIndexUnchecked(uint32_t idx) const {
  69     return m_map[idx].value;
  70   }
  71
  72   ConstString GetCStringAtIndex(uint32_t idx) const {
  73     return ((idx < m_map.size()) ? m_map[idx].cstring : ConstString());
  74   }
  75
  76   // Find the value for the unique string in the map.
  77   //
  78   // Return the value for \a unique_cstr if one is found, return \a fail_value
  79   // otherwise. This method works well for simple type
  80   // T values and only if there is a sensible failure value that can
  81   // be returned and that won't match any existing values.
  82   T Find(ConstString unique_cstr, T fail_value) const {
  83     auto pos = llvm::lower_bound(m_map, unique_cstr, Compare());
  84     if (pos != m_map.end() && pos->cstring == unique_cstr)
  85       return pos->value;
  86     return fail_value;
  87   }
  88
  89   // Get a pointer to the first entry that matches "name". nullptr will be
  90   // returned if there is no entry that matches "name".
  91   //
  92   // The caller is responsible for ensuring that the collection does not change
  93   // during while using the returned pointer.
  94   const Entry *FindFirstValueForName(ConstString unique_cstr) const {
  95     auto pos = llvm::lower_bound(m_map, unique_cstr, Compare());
  96     if (pos != m_map.end() && pos->cstring == unique_cstr)
  97       return &(*pos);
  98     return nullptr;
  99   }
 100
 101   // Get a pointer to the next entry that matches "name" from a previously
 102   // returned Entry pointer. nullptr will be returned if there is no subsequent
 103   // entry that matches "name".
 104   //
 105   // The caller is responsible for ensuring that the collection does not change
 106   // during while using the returned pointer.
 107   const Entry *FindNextValueForName(const Entry *entry_ptr) const {
 108     if (!m_map.empty()) {
 109       const Entry *first_entry = &m_map[0];
 110       const Entry *after_last_entry = first_entry + m_map.size();
 111       const Entry *next_entry = entry_ptr + 1;
 112       if (first_entry <= next_entry && next_entry < after_last_entry) {
 113         if (next_entry->cstring == entry_ptr->cstring)
 114           return next_entry;
 115       }
 116     }
 117     return nullptr;
 118   }
 119
 120   size_t GetValues(ConstString unique_cstr, std::vector<T> &values) const {
 121     const size_t start_size = values.size();
 122
 123     for (const Entry &entry : llvm::make_range(std::equal_range(
 124              m_map.begin(), m_map.end(), unique_cstr, Compare())))
 125       values.push_back(entry.value);
 126
 127     return values.size() - start_size;
 128   }
 129
 130   size_t GetValues(const RegularExpression &regex,
 131                    std::vector<T> &values) const {
 132     const size_t start_size = values.size();
 133
 134     const_iterator pos, end = m_map.end();
 135     for (pos = m_map.begin(); pos != end; ++pos) {
 136       if (regex.Execute(pos->cstring.GetCString()))
 137         values.push_back(pos->value);
 138     }
 139
 140     return values.size() - start_size;
 141   }
 142
 143   // Get the total number of entries in this map.
 144   size_t GetSize() const { return m_map.size(); }
 145
 146   // Returns true if this map is empty.
 147   bool IsEmpty() const { return m_map.empty(); }
 148
 149   // Reserve memory for at least "n" entries in the map. This is useful to call
 150   // when you know you will be adding a lot of entries using
 151   // UniqueCStringMap::Append() (which should be followed by a call to
 152   // UniqueCStringMap::Sort()) or to UniqueCStringMap::Insert().
 153   void Reserve(size_t n) { m_map.reserve(n); }
 154
 155   // Sort the unsorted contents in this map. A typical code flow would be:
 156   // size_t approximate_num_entries = ....
 157   // UniqueCStringMap<uint32_t> my_map;
 158   // my_map.Reserve (approximate_num_entries);
 159   // for (...)
 160   // {
 161   //      my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...)));
 162   // }
 163   // my_map.Sort();
 164   void Sort() { llvm::sort(m_map.begin(), m_map.end(), Compare()); }
 165
 166   // Since we are using a vector to contain our items it will always double its
 167   // memory consumption as things are added to the vector, so if you intend to
 168   // keep a UniqueCStringMap around and have a lot of entries in the map, you
 169   // will want to call this function to create a new vector and copy _only_ the
 170   // exact size needed as part of the finalization of the string map.
 171   void SizeToFit() {
 172     if (m_map.size() < m_map.capacity()) {
 173       collection temp(m_map.begin(), m_map.end());
 174       m_map.swap(temp);
 175     }
 176   }
 177
 178 protected:
 179   struct Compare {
 180     bool operator()(const Entry &lhs, const Entry &rhs) {
 181       return operator()(lhs.cstring, rhs.cstring);
 182     }
 183
 184     bool operator()(const Entry &lhs, ConstString rhs) {
 185       return operator()(lhs.cstring, rhs);
 186     }
 187
 188     bool operator()(ConstString lhs, const Entry &rhs) {
 189       return operator()(lhs, rhs.cstring);
 190     }
 191
 192     // This is only for uniqueness, not lexicographical ordering, so we can
 193     // just compare pointers. *However*, comparing pointers from different
 194     // allocations is UB, so we need compare their integral values instead.
 195     bool operator()(ConstString lhs, ConstString rhs) {
 196       return uintptr_t(lhs.GetCString()) < uintptr_t(rhs.GetCString());
 197     }
 198   };
 199   typedef std::vector<Entry> collection;
 200   typedef typename collection::iterator iterator;
 201   typedef typename collection::const_iterator const_iterator;
 202   collection m_map;
 203 };
 204
 205 } // namespace lldb_private
 206
 207 #endif // liblldb_UniqueCStringMap_h_