aboutsummaryrefslogtreecommitdiff
path: root/include/lldb/Core/UniqueCStringMap.h
blob: 1475fdaa74d96c809f7dd81bd6cf14e265dab833 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
//===-- UniqueCStringMap.h --------------------------------------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#ifndef liblldb_UniqueCStringMap_h_
#define liblldb_UniqueCStringMap_h_

// C Includes
// C++ Includes
#include <algorithm>
#include <vector>

// Other libraries and framework includes
// Project includes
#include "lldb/Utility/RegularExpression.h"

#include "llvm/ADT/StringRef.h"

namespace lldb_private {

//----------------------------------------------------------------------
// Templatized uniqued string map.
//
// This map is useful for mapping unique C string names to values of
// type T. Each "const char *" name added must be unique for a given
// C string value. ConstString::GetCString() can provide such strings.
// Any other string table that has guaranteed unique values can also
// be used.
//----------------------------------------------------------------------
template <typename T> class UniqueCStringMap {
public:
  struct Entry {
    Entry() {}

    Entry(llvm::StringRef cstr) : cstring(cstr), value() {}

    Entry(llvm::StringRef cstr, const T &v) : cstring(cstr), value(v) {}

    bool operator<(const Entry &rhs) const { return cstring < rhs.cstring; }

    llvm::StringRef cstring;
    T value;
  };

  //------------------------------------------------------------------
  // Call this function multiple times to add a bunch of entries to
  // this map, then later call UniqueCStringMap<T>::Sort() before doing
  // any searches by name.
  //------------------------------------------------------------------
  void Append(llvm::StringRef unique_cstr, const T &value) {
    m_map.push_back(typename UniqueCStringMap<T>::Entry(unique_cstr, value));
  }

  void Append(const Entry &e) { m_map.push_back(e); }

  void Clear() { m_map.clear(); }

  //------------------------------------------------------------------
  // Call this function to always keep the map sorted when putting
  // entries into the map.
  //------------------------------------------------------------------
  void Insert(llvm::StringRef unique_cstr, const T &value) {
    typename UniqueCStringMap<T>::Entry e(unique_cstr, value);
    m_map.insert(std::upper_bound(m_map.begin(), m_map.end(), e), e);
  }

  void Insert(const Entry &e) {
    m_map.insert(std::upper_bound(m_map.begin(), m_map.end(), e), e);
  }

  //------------------------------------------------------------------
  // Get an entries by index in a variety of forms.
  //
  // The caller is responsible for ensuring that the collection does
  // not change during while using the returned values.
  //------------------------------------------------------------------
  bool GetValueAtIndex(uint32_t idx, T &value) const {
    if (idx < m_map.size()) {
      value = m_map[idx].value;
      return true;
    }
    return false;
  }

  llvm::StringRef GetCStringAtIndexUnchecked(uint32_t idx) const {
    return m_map[idx].cstring;
  }

  // Use this function if you have simple types in your map that you
  // can easily copy when accessing values by index.
  T GetValueAtIndexUnchecked(uint32_t idx) const { return m_map[idx].value; }

  // Use this function if you have complex types in your map that you
  // don't want to copy when accessing values by index.
  const T &GetValueRefAtIndexUnchecked(uint32_t idx) const {
    return m_map[idx].value;
  }

  llvm::StringRef GetCStringAtIndex(uint32_t idx) const {
    return ((idx < m_map.size()) ? m_map[idx].cstring : llvm::StringRef());
  }

  //------------------------------------------------------------------
  // Find the value for the unique string in the map.
  //
  // Return the value for \a unique_cstr if one is found, return
  // \a fail_value otherwise. This method works well for simple type
  // T values and only if there is a sensible failure value that can
  // be returned and that won't match any existing values.
  //------------------------------------------------------------------
  T Find(llvm::StringRef unique_cstr, T fail_value) const {
    Entry search_entry(unique_cstr);
    const_iterator end = m_map.end();
    const_iterator pos = std::lower_bound(m_map.begin(), end, search_entry);
    if (pos != end) {
      if (pos->cstring == unique_cstr)
        return pos->value;
    }
    return fail_value;
  }

  //------------------------------------------------------------------
  // Get a pointer to the first entry that matches "name". nullptr will
  // be returned if there is no entry that matches "name".
  //
  // The caller is responsible for ensuring that the collection does
  // not change during while using the returned pointer.
  //------------------------------------------------------------------
  const Entry *FindFirstValueForName(llvm::StringRef unique_cstr) const {
    Entry search_entry(unique_cstr);
    const_iterator end = m_map.end();
    const_iterator pos = std::lower_bound(m_map.begin(), end, search_entry);
    if (pos != end) {
      llvm::StringRef pos_cstr = pos->cstring;
      if (pos_cstr == unique_cstr)
        return &(*pos);
    }
    return nullptr;
  }

  //------------------------------------------------------------------
  // Get a pointer to the next entry that matches "name" from a
  // previously returned Entry pointer. nullptr will be returned if there
  // is no subsequent entry that matches "name".
  //
  // The caller is responsible for ensuring that the collection does
  // not change during while using the returned pointer.
  //------------------------------------------------------------------
  const Entry *FindNextValueForName(const Entry *entry_ptr) const {
    if (!m_map.empty()) {
      const Entry *first_entry = &m_map[0];
      const Entry *after_last_entry = first_entry + m_map.size();
      const Entry *next_entry = entry_ptr + 1;
      if (first_entry <= next_entry && next_entry < after_last_entry) {
        if (next_entry->cstring == entry_ptr->cstring)
          return next_entry;
      }
    }
    return nullptr;
  }

  size_t GetValues(llvm::StringRef unique_cstr, std::vector<T> &values) const {
    const size_t start_size = values.size();

    Entry search_entry(unique_cstr);
    const_iterator pos, end = m_map.end();
    for (pos = std::lower_bound(m_map.begin(), end, search_entry); pos != end;
         ++pos) {
      if (pos->cstring == unique_cstr)
        values.push_back(pos->value);
      else
        break;
    }

    return values.size() - start_size;
  }

  size_t GetValues(const RegularExpression &regex,
                   std::vector<T> &values) const {
    const size_t start_size = values.size();

    const_iterator pos, end = m_map.end();
    for (pos = m_map.begin(); pos != end; ++pos) {
      if (regex.Execute(pos->cstring))
        values.push_back(pos->value);
    }

    return values.size() - start_size;
  }

  //------------------------------------------------------------------
  // Get the total number of entries in this map.
  //------------------------------------------------------------------
  size_t GetSize() const { return m_map.size(); }

  //------------------------------------------------------------------
  // Returns true if this map is empty.
  //------------------------------------------------------------------
  bool IsEmpty() const { return m_map.empty(); }

  //------------------------------------------------------------------
  // Reserve memory for at least "n" entries in the map. This is
  // useful to call when you know you will be adding a lot of entries
  // using UniqueCStringMap::Append() (which should be followed by a
  // call to UniqueCStringMap::Sort()) or to UniqueCStringMap::Insert().
  //------------------------------------------------------------------
  void Reserve(size_t n) { m_map.reserve(n); }

  //------------------------------------------------------------------
  // Sort the unsorted contents in this map. A typical code flow would
  // be:
  // size_t approximate_num_entries = ....
  // UniqueCStringMap<uint32_t> my_map;
  // my_map.Reserve (approximate_num_entries);
  // for (...)
  // {
  //      my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...)));
  // }
  // my_map.Sort();
  //------------------------------------------------------------------
  void Sort() { std::sort(m_map.begin(), m_map.end()); }

  //------------------------------------------------------------------
  // Since we are using a vector to contain our items it will always
  // double its memory consumption as things are added to the vector,
  // so if you intend to keep a UniqueCStringMap around and have
  // a lot of entries in the map, you will want to call this function
  // to create a new vector and copy _only_ the exact size needed as
  // part of the finalization of the string map.
  //------------------------------------------------------------------
  void SizeToFit() {
    if (m_map.size() < m_map.capacity()) {
      collection temp(m_map.begin(), m_map.end());
      m_map.swap(temp);
    }
  }

  size_t Erase(llvm::StringRef unique_cstr) {
    size_t num_removed = 0;
    Entry search_entry(unique_cstr);
    iterator end = m_map.end();
    iterator begin = m_map.begin();
    iterator lower_pos = std::lower_bound(begin, end, search_entry);
    if (lower_pos != end) {
      if (lower_pos->cstring == unique_cstr) {
        iterator upper_pos = std::upper_bound(lower_pos, end, search_entry);
        if (lower_pos == upper_pos) {
          m_map.erase(lower_pos);
          num_removed = 1;
        } else {
          num_removed = std::distance(lower_pos, upper_pos);
          m_map.erase(lower_pos, upper_pos);
        }
      }
    }
    return num_removed;
  }

protected:
  typedef std::vector<Entry> collection;
  typedef typename collection::iterator iterator;
  typedef typename collection::const_iterator const_iterator;
  collection m_map;
};

} // namespace lldb_private

#endif // liblldb_UniqueCStringMap_h_