| //===-- 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_ |
| #if defined(__cplusplus) |
| |
| #include <assert.h> |
| #include <algorithm> |
| #include <vector> |
| |
| #include "lldb/Core/RegularExpression.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 () : |
| cstring(NULL), |
| value() |
| { |
| } |
| |
| Entry (const char *cstr) : |
| cstring(cstr), |
| value() |
| { |
| } |
| |
| Entry (const char *cstr, const T&v) : |
| cstring(cstr), |
| value(v) |
| { |
| } |
| |
| bool |
| operator < (const Entry& rhs) const |
| { |
| return cstring < rhs.cstring; |
| } |
| |
| const char* 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 (const char *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 (const char *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; |
| } |
| |
| const char * |
| 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; |
| } |
| |
| const char * |
| GetCStringAtIndex (uint32_t idx) const |
| { |
| if (idx < m_map.size()) |
| return m_map[idx].cstring; |
| return NULL; |
| } |
| |
| //------------------------------------------------------------------ |
| // 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 (const char *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". NULL 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 (const char *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) |
| { |
| const char *pos_cstr = pos->cstring; |
| if (pos_cstr == unique_cstr) |
| return &(*pos); |
| } |
| return NULL; |
| } |
| |
| //------------------------------------------------------------------ |
| // Get a pointer to the next entry that matches "name" from a |
| // previously returned Entry pointer. NULL 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 NULL; |
| } |
| |
| size_t |
| GetValues (const char *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 (const char *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 // #if defined(__cplusplus) |
| #endif // liblldb_UniqueCStringMap_h_ |