1257663e753af15633e48c7b00eb7b5880168090bGreg Clayton//===-- RangeMap.h ----------------------------------------------*- C++ -*-===//
2257663e753af15633e48c7b00eb7b5880168090bGreg Clayton//
3257663e753af15633e48c7b00eb7b5880168090bGreg Clayton//                     The LLVM Compiler Infrastructure
4257663e753af15633e48c7b00eb7b5880168090bGreg Clayton//
5257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// This file is distributed under the University of Illinois Open Source
6257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// License. See LICENSE.TXT for details.
7257663e753af15633e48c7b00eb7b5880168090bGreg Clayton//
8257663e753af15633e48c7b00eb7b5880168090bGreg Clayton//===----------------------------------------------------------------------===//
9257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
10257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#ifndef liblldb_RangeMap_h_
11257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#define liblldb_RangeMap_h_
12257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
13464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#include <vector>
14464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton
15257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#include "lldb/lldb-private.h"
16be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton#include "llvm/ADT/SmallVector.h"
17257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
18c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton// Uncomment to make sure all Range objects are sorted when needed
19c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton//#define ASSERT_RANGEMAP_ARE_SORTED
20c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton
21257663e753af15633e48c7b00eb7b5880168090bGreg Claytonnamespace lldb_private {
22257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
234aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton
2461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    //----------------------------------------------------------------------
254aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton    // Templatized classes for dealing with generic ranges and also
2661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    // collections of ranges, or collections of ranges that have associated
2761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    // data.
2861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    //----------------------------------------------------------------------
2961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
3061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    //----------------------------------------------------------------------
3161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    // A simple range class where you get to define the type of the range
3261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    // base "B", and the type used for the range byte size "S".
3361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    //----------------------------------------------------------------------
3461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    template <typename B, typename S>
35257663e753af15633e48c7b00eb7b5880168090bGreg Clayton    struct Range
36257663e753af15633e48c7b00eb7b5880168090bGreg Clayton    {
3761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        typedef B BaseType;
3861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        typedef S SizeType;
3961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
4061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        BaseType base;
4161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        SizeType size;
42257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
43257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        Range () :
44257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            base (0),
45257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            size (0)
46257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
47257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
48257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
4961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        Range (BaseType b, SizeType s) :
50257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            base (b),
51257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            size (s)
52257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
53257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
54257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
55bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        void
56bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        Clear (BaseType b = 0)
57bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        {
58bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            base = b;
59bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            size = 0;
60bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        }
61bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton
62257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        // Set the start value for the range, and keep the same size
6361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        BaseType
6461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        GetRangeBase () const
65257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
66257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            return base;
67257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
68257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
69257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        void
7061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        SetRangeBase (BaseType b)
71257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
72257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            base = b;
73257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
74257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
75bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        void
76bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        Slide (BaseType slide)
77bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        {
78bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            base += slide;
79bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        }
80bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton
8161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        BaseType
8261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        GetRangeEnd () const
83257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
84257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            return base + size;
85257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
86257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
87257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        void
8861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        SetRangeEnd (BaseType end)
89257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
90257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            if (end > base)
91257663e753af15633e48c7b00eb7b5880168090bGreg Clayton                size = end - base;
92257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            else
93257663e753af15633e48c7b00eb7b5880168090bGreg Clayton                size = 0;
94257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
95257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
9661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        SizeType
9761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        GetByteSize () const
98257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
99257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            return size;
100257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
101257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
102257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        void
10361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        SetByteSize (SizeType s)
104257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
105257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            size = s;
106257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
107257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
108257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        bool
109257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        IsValid() const
110257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
111257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            return size > 0;
112257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
113257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
114257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        bool
11561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        Contains (BaseType r) const
116257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
11761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            return (GetRangeBase() <= r) && (r < GetRangeEnd());
118257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
119257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
120257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        bool
12161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        ContainsEndInclusive (BaseType r) const
122257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
12361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            return (GetRangeBase() <= r) && (r <= GetRangeEnd());
124257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
125257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
126257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        bool
127257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        Contains (const Range& range) const
128257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
12961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd());
130257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
131257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
132257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        bool
133bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        Overlap (const Range &rhs) const
134bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        {
135bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            const BaseType lhs_base = this->GetRangeBase();
136bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            const BaseType rhs_base = rhs.GetRangeBase();
137bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            const BaseType lhs_end = this->GetRangeEnd();
138bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            const BaseType rhs_end = rhs.GetRangeEnd();
139bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base);
140bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            return result;
141bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        }
142bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton
143bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        bool
144bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        operator < (const Range &rhs) const
145257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
146257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            if (base == rhs.base)
147257663e753af15633e48c7b00eb7b5880168090bGreg Clayton                return size < rhs.size;
148257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            return base < rhs.base;
149257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
150257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
151257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        bool
152bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        operator == (const Range &rhs) const
153257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
154257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            return base == rhs.base && size == rhs.size;
155257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
156257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
157257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        bool
158bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        operator != (const Range &rhs) const
159257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
160257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            return  base != rhs.base || size != rhs.size;
161257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
162257663e753af15633e48c7b00eb7b5880168090bGreg Clayton    };
16361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
16461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    //----------------------------------------------------------------------
16561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    // A range array class where you get to define the type of the ranges
16661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    // that the collection contains.
16761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    //----------------------------------------------------------------------
168257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
169be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton    template <typename B, typename S, unsigned N>
17061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    class RangeArray
171257663e753af15633e48c7b00eb7b5880168090bGreg Clayton    {
172bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton    public:
173bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        typedef B BaseType;
174bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        typedef S SizeType;
17561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        typedef Range<B,S> Entry;
176be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton        typedef llvm::SmallVector<Entry, N> Collection;
17761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
178bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        RangeArray () :
179bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            m_entries ()
18061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        {
18161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        }
18261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
18361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        ~RangeArray()
18461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        {
18561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        }
18661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
18761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        void
18861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        Append (const Entry &entry)
18961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        {
19061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            m_entries.push_back (entry);
19161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        }
19261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
193761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton        bool
194761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton        RemoveEntrtAtIndex (uint32_t idx)
195761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton        {
196761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton            if (idx < m_entries.size())
197761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton            {
198761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton                m_entries.erase (m_entries.begin() + idx);
199761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton                return true;
200761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton            }
201761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton            return false;
202761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton        }
203761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton
20461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        void
20561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        Sort ()
20661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        {
20761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            if (m_entries.size() > 1)
20861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                std::stable_sort (m_entries.begin(), m_entries.end());
20961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        }
21061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
211c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED
212c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton        bool
213c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton        IsSorted () const
214c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton        {
215be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton            typename Collection::const_iterator pos, end, prev;
216c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            // First we determine if we can combine any of the Entry objects so we
217c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            // don't end up allocating and making a new collection for no reason
218c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
219c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            {
220c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton                if (prev != end && *pos < *prev)
221c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton                    return false;
222c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            }
223c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            return true;
224c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton        }
225c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif
22661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        void
227bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        CombineConsecutiveRanges ()
22861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        {
229c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED
230c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            assert (IsSorted());
231c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif
232bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            // Can't combine if ranges if we have zero or one range
233bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            if (m_entries.size() > 1)
23461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            {
235bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                // The list should be sorted prior to calling this function
236be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton                typename Collection::iterator pos;
237be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton                typename Collection::iterator end;
238be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton                typename Collection::iterator prev;
239bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                bool can_combine = false;
240bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                // First we determine if we can combine any of the Entry objects so we
241bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                // don't end up allocating and making a new collection for no reason
242bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
24361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                {
244bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    if (prev != end && prev->Overlap(*pos))
245bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    {
246bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                        can_combine = true;
247bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                        break;
248bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    }
24961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                }
250bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton
251bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                // We we can combine at least one entry, then we make a new collection
252bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                // and populate it accordingly, and then swap it into place.
253bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                if (can_combine)
25461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                {
255be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton                    Collection minimal_ranges;
256bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
257bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    {
258bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                        if (prev != end && prev->Overlap(*pos))
259bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                            minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
260bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                        else
261bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                            minimal_ranges.push_back (*pos);
262bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    }
263bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    // Use the swap technique in case our new vector is much smaller.
264bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    // We must swap when using the STL because std::vector objects never
265bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    // release or reduce the memory once it has been allocated/reserved.
266bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    m_entries.swap (minimal_ranges);
26761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                }
26861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            }
26961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        }
270bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton
271bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton
272bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        BaseType
273bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        GetMinRangeBase (BaseType fail_value) const
274bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        {
275c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED
276c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            assert (IsSorted());
277c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif
278bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            if (m_entries.empty())
279bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                return fail_value;
280bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            // m_entries must be sorted, so if we aren't empty, we grab the
281bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            // first range's base
282bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            return m_entries.front().GetRangeBase();
283bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        }
284bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton
285bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        BaseType
286bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        GetMaxRangeEnd (BaseType fail_value) const
287bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        {
288c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED
289c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            assert (IsSorted());
290c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif
291bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            if (m_entries.empty())
292bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                return fail_value;
293bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            // m_entries must be sorted, so if we aren't empty, we grab the
294bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            // last range's end
295bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            return m_entries.back().GetRangeEnd();
296bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        }
297bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton
298bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        void
299bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        Slide (BaseType slide)
300bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        {
301be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton            typename Collection::iterator pos, end;
302bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
303bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                pos->Slide (slide);
304bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        }
30561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
30661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        void
30761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        Clear ()
30861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        {
30961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            m_entries.clear();
31061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        }
31161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
31261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        bool
31361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        IsEmpty () const
31461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        {
31561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            return m_entries.empty();
31661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        }
31761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
31861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        size_t
319bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        GetSize () const
32061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        {
32161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            return m_entries.size();
32261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        }
32361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
32461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        const Entry *
325bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        GetEntryAtIndex (size_t i) const
32661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        {
32761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            if (i<m_entries.size())
32861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                return &m_entries[i];
32961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            return NULL;
33061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        }
33161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
332bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        // Clients must ensure that "i" is a valid index prior to calling this function
333bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        const Entry &
334bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        GetEntryRef (size_t i) const
335bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        {
336bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            return m_entries[i];
337bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        }
338bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton
3394aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton        Entry *
3404aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton        Back()
3414aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton        {
3424aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton            if (m_entries.empty())
3434aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton                return NULL;
3444aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton            return &m_entries.back();
3454aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton        }
3464aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton
3474aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton        const Entry *
3484aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton        Back() const
3494aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton        {
3504aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton            if (m_entries.empty())
3514aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton                return NULL;
3524aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton            return &m_entries.back();
3534aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton        }
3544aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton
35561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        static bool
35661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        BaseLessThan (const Entry& lhs, const Entry& rhs)
35761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        {
35861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            return lhs.GetRangeBase() < rhs.GetRangeBase();
35961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        }
36061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
361bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        uint32_t
362bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        FindEntryIndexThatContains (B addr) const
363bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        {
364c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED
365c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            assert (IsSorted());
366c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif
367c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            if (!m_entries.empty())
368bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            {
369bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                Entry entry (addr, 1);
370be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton                typename Collection::const_iterator begin = m_entries.begin();
371be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton                typename Collection::const_iterator end = m_entries.end();
372be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton                typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
373bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton
374bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                if (pos != end && pos->Contains(addr))
375bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                {
376bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    return std::distance (begin, pos);
377bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                }
378bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                else if (pos != begin)
379bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                {
380bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    --pos;
381bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    if (pos->Contains(addr))
382bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                        return std::distance (begin, pos);
383bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                }
384bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            }
385bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            return UINT32_MAX;
386bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        }
387bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton
38861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        const Entry *
38961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        FindEntryThatContains (B addr) const
39061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        {
391c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED
392c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            assert (IsSorted());
393c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif
394c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            if (!m_entries.empty())
39561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            {
39661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                Entry entry (addr, 1);
397be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton                typename Collection::const_iterator begin = m_entries.begin();
398be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton                typename Collection::const_iterator end = m_entries.end();
399be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton                typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
40061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
40161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                if (pos != end && pos->Contains(addr))
40261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                {
40361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                    return &(*pos);
40461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                }
40561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                else if (pos != begin)
40661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                {
40761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                    --pos;
40861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                    if (pos->Contains(addr))
40961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                    {
41061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                        return &(*pos);
41161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                    }
41261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                }
41361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            }
41461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            return NULL;
41561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        }
416bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton
417bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        const Entry *
418bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        FindEntryThatContains (const Entry &range) const
419bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        {
420c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED
421c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            assert (IsSorted());
422c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif
423c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            if (!m_entries.empty())
424bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            {
425be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton                typename Collection::const_iterator begin = m_entries.begin();
426be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton                typename Collection::const_iterator end = m_entries.end();
427be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton                typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
428bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton
429bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                if (pos != end && pos->Contains(range))
430bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                {
431bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    return &(*pos);
432bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                }
433bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                else if (pos != begin)
434bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                {
435bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    --pos;
436bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    if (pos->Contains(range))
437bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    {
438bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                        return &(*pos);
439bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                    }
440bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton                }
441bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            }
442bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton            return NULL;
443bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton        }
444bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton
44561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    protected:
446be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton        Collection m_entries;
44761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    };
448257663e753af15633e48c7b00eb7b5880168090bGreg Clayton
449464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton    template <typename B, typename S>
450464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton    class RangeVector
45161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton    {
452464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton    public:
453464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton        typedef B BaseType;
454464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton        typedef S SizeType;
455464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton        typedef Range<B,S> Entry;
456464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton        typedef std::vector<Entry> Collection;
45761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
458464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton        RangeVector () :
459464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton            m_entries ()
460257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
461257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
46261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
463464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton        ~RangeVector()
464257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
465257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
46661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
467464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton        void
468464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton        Append (const Entry &entry)
469257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        {
470464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton            m_entries.push_back (entry);
471257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        }
47261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
473257663e753af15633e48c7b00eb7b5880168090bGreg Clayton        bool
474464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton        RemoveEntrtAtIndex (uint32_t idx)
47561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        {
476464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton            if (idx < m_entries.size())
477464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton            {
478464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                m_entries.erase (m_entries.begin() + idx);
479464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                return true;
480464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton            }
481464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton            return false;
48261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        }
48361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton
48461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        void
48561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        Sort ()
48661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        {
48761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton            if (m_entries.size() > 1)
48861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                std::stable_sort (m_entries.begin(), m_entries.end());
48961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        }
490464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton
491c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED
492c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton        bool
493c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton        IsSorted () const
494c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton        {
495be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton            typename Collection::const_iterator pos, end, prev;
496c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            // First we determine if we can combine any of the Entry objects so we
497c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            // don't end up allocating and making a new collection for no reason
498c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
499c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            {
500c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton                if (prev != end && *pos < *prev)
501c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton                    return false;
502c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            }
503c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            return true;
504c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton        }
505c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif
50661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        void
507464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton        CombineConsecutiveRanges ()
50861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        {
509c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED
510c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton            assert (IsSorted());
511c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif
512464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton            // Can't combine if ranges if we have zero or one range
513464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton            if (m_entries.size() > 1)
514257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            {
515464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                // The list should be sorted prior to calling this function
516464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                typename Collection::iterator pos;
517464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                typename Collection::iterator end;
518464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                typename Collection::iterator prev;
519464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                bool can_combine = false;
520464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                // First we determine if we can combine any of the Entry objects so we
521464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                // don't end up allocating and making a new collection for no reason
522464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
52361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                {
524464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                    if (prev != end && prev->Overlap(*pos))
525464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                    {
526464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                        can_combine = true;
527464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                        break;
528464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                    }
52961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                }
530464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton
531464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                // We we can combine at least one entry, then we make a new collection
532464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                // and populate it accordingly, and then swap it into place.
533464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                if (can_combine)
53461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                {
535464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                    Collection minimal_ranges;
536464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                    for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
537464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                    {
538464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                        if (prev != end && prev->Overlap(*pos))
539464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                            minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
540464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                        else
541464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                            minimal_ranges.push_back (*pos);
542464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                    }
543464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                    // Use the swap technique in case our new vector is much smaller.
544464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                    // We must swap when using the STL because std::vector objects never
545464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                    // release or reduce the memory once it has been allocated/reserved.
546464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton                    m_entries.swap (minimal_ranges);
54761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton                }
548257663e753af15633e48c7b00eb7b5880168090bGreg Clayton            }
54961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton        }
550464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton
551464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton
552464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton        BaseType
553464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton        GetMinRangeBase (BaseType fail_value) const
554464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton        {
555464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED
556