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