//===-- 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; } // 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_