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