1//===-- RangeMap.h ----------------------------------------------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef liblldb_RangeMap_h_
11#define liblldb_RangeMap_h_
12
13#include <vector>
14
15#include "lldb/lldb-private.h"
16#include "llvm/ADT/SmallVector.h"
17
18// Uncomment to make sure all Range objects are sorted when needed
19//#define ASSERT_RANGEMAP_ARE_SORTED
20
21namespace lldb_private {
22
23
24    //----------------------------------------------------------------------
25    // Templatized classes for dealing with generic ranges and also
26    // collections of ranges, or collections of ranges that have associated
27    // data.
28    //----------------------------------------------------------------------
29
30    //----------------------------------------------------------------------
31    // A simple range class where you get to define the type of the range
32    // base "B", and the type used for the range byte size "S".
33    //----------------------------------------------------------------------
34    template <typename B, typename S>
35    struct Range
36    {
37        typedef B BaseType;
38        typedef S SizeType;
39
40        BaseType base;
41        SizeType size;
42
43        Range () :
44            base (0),
45            size (0)
46        {
47        }
48
49        Range (BaseType b, SizeType s) :
50            base (b),
51            size (s)
52        {
53        }
54
55        void
56        Clear (BaseType b = 0)
57        {
58            base = b;
59            size = 0;
60        }
61
62        // Set the start value for the range, and keep the same size
63        BaseType
64        GetRangeBase () const
65        {
66            return base;
67        }
68
69        void
70        SetRangeBase (BaseType b)
71        {
72            base = b;
73        }
74
75        void
76        Slide (BaseType slide)
77        {
78            base += slide;
79        }
80
81        BaseType
82        GetRangeEnd () const
83        {
84            return base + size;
85        }
86
87        void
88        SetRangeEnd (BaseType end)
89        {
90            if (end > base)
91                size = end - base;
92            else
93                size = 0;
94        }
95
96        SizeType
97        GetByteSize () const
98        {
99            return size;
100        }
101
102        void
103        SetByteSize (SizeType s)
104        {
105            size = s;
106        }
107
108        bool
109        IsValid() const
110        {
111            return size > 0;
112        }
113
114        bool
115        Contains (BaseType r) const
116        {
117            return (GetRangeBase() <= r) && (r < GetRangeEnd());
118        }
119
120        bool
121        ContainsEndInclusive (BaseType r) const
122        {
123            return (GetRangeBase() <= r) && (r <= GetRangeEnd());
124        }
125
126        bool
127        Contains (const Range& range) const
128        {
129            return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd());
130        }
131
132        bool
133        Overlap (const Range &rhs) const
134        {
135            const BaseType lhs_base = this->GetRangeBase();
136            const BaseType rhs_base = rhs.GetRangeBase();
137            const BaseType lhs_end = this->GetRangeEnd();
138            const BaseType rhs_end = rhs.GetRangeEnd();
139            bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base);
140            return result;
141        }
142
143        bool
144        operator < (const Range &rhs) const
145        {
146            if (base == rhs.base)
147                return size < rhs.size;
148            return base < rhs.base;
149        }
150
151        bool
152        operator == (const Range &rhs) const
153        {
154            return base == rhs.base && size == rhs.size;
155        }
156
157        bool
158        operator != (const Range &rhs) const
159        {
160            return  base != rhs.base || size != rhs.size;
161        }
162    };
163
164    //----------------------------------------------------------------------
165    // A range array class where you get to define the type of the ranges
166    // that the collection contains.
167    //----------------------------------------------------------------------
168
169    template <typename B, typename S, unsigned N>
170    class RangeArray
171    {
172    public:
173        typedef B BaseType;
174        typedef S SizeType;
175        typedef Range<B,S> Entry;
176        typedef llvm::SmallVector<Entry, N> Collection;
177
178        RangeArray () :
179            m_entries ()
180        {
181        }
182
183        ~RangeArray()
184        {
185        }
186
187        void
188        Append (const Entry &entry)
189        {
190            m_entries.push_back (entry);
191        }
192
193        bool
194        RemoveEntrtAtIndex (uint32_t idx)
195        {
196            if (idx < m_entries.size())
197            {
198                m_entries.erase (m_entries.begin() + idx);
199                return true;
200            }
201            return false;
202        }
203
204        void
205        Sort ()
206        {
207            if (m_entries.size() > 1)
208                std::stable_sort (m_entries.begin(), m_entries.end());
209        }
210
211#ifdef ASSERT_RANGEMAP_ARE_SORTED
212        bool
213        IsSorted () const
214        {
215            typename Collection::const_iterator pos, end, prev;
216            // First we determine if we can combine any of the Entry objects so we
217            // don't end up allocating and making a new collection for no reason
218            for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
219            {
220                if (prev != end && *pos < *prev)
221                    return false;
222            }
223            return true;
224        }
225#endif
226        void
227        CombineConsecutiveRanges ()
228        {
229#ifdef ASSERT_RANGEMAP_ARE_SORTED
230            assert (IsSorted());
231#endif
232            // Can't combine if ranges if we have zero or one range
233            if (m_entries.size() > 1)
234            {
235                // The list should be sorted prior to calling this function
236                typename Collection::iterator pos;
237                typename Collection::iterator end;
238                typename Collection::iterator prev;
239                bool can_combine = false;
240                // First we determine if we can combine any of the Entry objects so we
241                // don't end up allocating and making a new collection for no reason
242                for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
243                {
244                    if (prev != end && prev->Overlap(*pos))
245                    {
246                        can_combine = true;
247                        break;
248                    }
249                }
250
251                // We we can combine at least one entry, then we make a new collection
252                // and populate it accordingly, and then swap it into place.
253                if (can_combine)
254                {
255                    Collection minimal_ranges;
256                    for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
257                    {
258                        if (prev != end && prev->Overlap(*pos))
259                            minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
260                        else
261                            minimal_ranges.push_back (*pos);
262                    }
263                    // Use the swap technique in case our new vector is much smaller.
264                    // We must swap when using the STL because std::vector objects never
265                    // release or reduce the memory once it has been allocated/reserved.
266                    m_entries.swap (minimal_ranges);
267                }
268            }
269        }
270
271
272        BaseType
273        GetMinRangeBase (BaseType fail_value) const
274        {
275#ifdef ASSERT_RANGEMAP_ARE_SORTED
276            assert (IsSorted());
277#endif
278            if (m_entries.empty())
279                return fail_value;
280            // m_entries must be sorted, so if we aren't empty, we grab the
281            // first range's base
282            return m_entries.front().GetRangeBase();
283        }
284
285        BaseType
286        GetMaxRangeEnd (BaseType fail_value) const
287        {
288#ifdef ASSERT_RANGEMAP_ARE_SORTED
289            assert (IsSorted());
290#endif
291            if (m_entries.empty())
292                return fail_value;
293            // m_entries must be sorted, so if we aren't empty, we grab the
294            // last range's end
295            return m_entries.back().GetRangeEnd();
296        }
297
298        void
299        Slide (BaseType slide)
300        {
301            typename Collection::iterator pos, end;
302            for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
303                pos->Slide (slide);
304        }
305
306        void
307        Clear ()
308        {
309            m_entries.clear();
310        }
311
312        bool
313        IsEmpty () const
314        {
315            return m_entries.empty();
316        }
317
318        size_t
319        GetSize () const
320        {
321            return m_entries.size();
322        }
323
324        const Entry *
325        GetEntryAtIndex (size_t i) const
326        {
327            if (i<m_entries.size())
328                return &m_entries[i];
329            return NULL;
330        }
331
332        // Clients must ensure that "i" is a valid index prior to calling this function
333        const Entry &
334        GetEntryRef (size_t i) const
335        {
336            return m_entries[i];
337        }
338
339        Entry *
340        Back()
341        {
342            if (m_entries.empty())
343                return NULL;
344            return &m_entries.back();
345        }
346
347        const Entry *
348        Back() const
349        {
350            if (m_entries.empty())
351                return NULL;
352            return &m_entries.back();
353        }
354
355        static bool
356        BaseLessThan (const Entry& lhs, const Entry& rhs)
357        {
358            return lhs.GetRangeBase() < rhs.GetRangeBase();
359        }
360
361        uint32_t
362        FindEntryIndexThatContains (B addr) const
363        {
364#ifdef ASSERT_RANGEMAP_ARE_SORTED
365            assert (IsSorted());
366#endif
367            if (!m_entries.empty())
368            {
369                Entry entry (addr, 1);
370                typename Collection::const_iterator begin = m_entries.begin();
371                typename Collection::const_iterator end = m_entries.end();
372                typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
373
374                if (pos != end && pos->Contains(addr))
375                {
376                    return std::distance (begin, pos);
377                }
378                else if (pos != begin)
379                {
380                    --pos;
381                    if (pos->Contains(addr))
382                        return std::distance (begin, pos);
383                }
384            }
385            return UINT32_MAX;
386        }
387
388        const Entry *
389        FindEntryThatContains (B addr) const
390        {
391#ifdef ASSERT_RANGEMAP_ARE_SORTED
392            assert (IsSorted());
393#endif
394            if (!m_entries.empty())
395            {
396                Entry entry (addr, 1);
397                typename Collection::const_iterator begin = m_entries.begin();
398                typename Collection::const_iterator end = m_entries.end();
399                typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
400
401                if (pos != end && pos->Contains(addr))
402                {
403                    return &(*pos);
404                }
405                else if (pos != begin)
406                {
407                    --pos;
408                    if (pos->Contains(addr))
409                    {
410                        return &(*pos);
411                    }
412                }
413            }
414            return NULL;
415        }
416
417        const Entry *
418        FindEntryThatContains (const Entry &range) const
419        {
420#ifdef ASSERT_RANGEMAP_ARE_SORTED
421            assert (IsSorted());
422#endif
423            if (!m_entries.empty())
424            {
425                typename Collection::const_iterator begin = m_entries.begin();
426                typename Collection::const_iterator end = m_entries.end();
427                typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
428
429                if (pos != end && pos->Contains(range))
430                {
431                    return &(*pos);
432                }
433                else if (pos != begin)
434                {
435                    --pos;
436                    if (pos->Contains(range))
437                    {
438                        return &(*pos);
439                    }
440                }
441            }
442            return NULL;
443        }
444
445    protected:
446        Collection m_entries;
447    };
448
449    template <typename B, typename S>
450    class RangeVector
451    {
452    public:
453        typedef B BaseType;
454        typedef S SizeType;
455        typedef Range<B,S> Entry;
456        typedef std::vector<Entry> Collection;
457
458        RangeVector () :
459            m_entries ()
460        {
461        }
462
463        ~RangeVector()
464        {
465        }
466
467        void
468        Append (const Entry &entry)
469        {
470            m_entries.push_back (entry);
471        }
472
473        bool
474        RemoveEntrtAtIndex (uint32_t idx)
475        {
476            if (idx < m_entries.size())
477            {
478                m_entries.erase (m_entries.begin() + idx);
479                return true;
480            }
481            return false;
482        }
483
484        void
485        Sort ()
486        {
487            if (m_entries.size() > 1)
488                std::stable_sort (m_entries.begin(), m_entries.end());
489        }
490
491#ifdef ASSERT_RANGEMAP_ARE_SORTED
492        bool
493        IsSorted () const
494        {
495            typename Collection::const_iterator pos, end, prev;
496            // First we determine if we can combine any of the Entry objects so we
497            // don't end up allocating and making a new collection for no reason
498            for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
499            {
500                if (prev != end && *pos < *prev)
501                    return false;
502            }
503            return true;
504        }
505#endif
506        void
507        CombineConsecutiveRanges ()
508        {
509#ifdef ASSERT_RANGEMAP_ARE_SORTED
510            assert (IsSorted());
511#endif
512            // Can't combine if ranges if we have zero or one range
513            if (m_entries.size() > 1)
514            {
515                // The list should be sorted prior to calling this function
516                typename Collection::iterator pos;
517                typename Collection::iterator end;
518                typename Collection::iterator prev;
519                bool can_combine = false;
520                // First we determine if we can combine any of the Entry objects so we
521                // don't end up allocating and making a new collection for no reason
522                for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
523                {
524                    if (prev != end && prev->Overlap(*pos))
525                    {
526                        can_combine = true;
527                        break;
528                    }
529                }
530
531                // We we can combine at least one entry, then we make a new collection
532                // and populate it accordingly, and then swap it into place.
533                if (can_combine)
534                {
535                    Collection minimal_ranges;
536                    for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
537                    {
538                        if (prev != end && prev->Overlap(*pos))
539                            minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
540                        else
541                            minimal_ranges.push_back (*pos);
542                    }
543                    // Use the swap technique in case our new vector is much smaller.
544                    // We must swap when using the STL because std::vector objects never
545                    // release or reduce the memory once it has been allocated/reserved.
546                    m_entries.swap (minimal_ranges);
547                }
548            }
549        }
550
551
552        BaseType
553        GetMinRangeBase (BaseType fail_value) const
554        {
555#ifdef ASSERT_RANGEMAP_ARE_SORTED
556            assert (IsSorted());
557#endif
558            if (m_entries.empty())
559                return fail_value;
560            // m_entries must be sorted, so if we aren't empty, we grab the
561            // first range's base
562            return m_entries.front().GetRangeBase();
563        }
564
565        BaseType
566        GetMaxRangeEnd (BaseType fail_value) const
567        {
568#ifdef ASSERT_RANGEMAP_ARE_SORTED
569            assert (IsSorted());
570#endif
571            if (m_entries.empty())
572                return fail_value;
573            // m_entries must be sorted, so if we aren't empty, we grab the
574            // last range's end
575            return m_entries.back().GetRangeEnd();
576        }
577
578        void
579        Slide (BaseType slide)
580        {
581            typename Collection::iterator pos, end;
582            for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
583                pos->Slide (slide);
584        }
585
586        void
587        Clear ()
588        {
589            m_entries.clear();
590        }
591
592        void
593        Reserve (typename Collection::size_type size)
594        {
595            m_entries.resize (size);
596        }
597
598        bool
599        IsEmpty () const
600        {
601            return m_entries.empty();
602        }
603
604        size_t
605        GetSize () const
606        {
607            return m_entries.size();
608        }
609
610        const Entry *
611        GetEntryAtIndex (size_t i) const
612        {
613            if (i<m_entries.size())
614                return &m_entries[i];
615            return NULL;
616        }
617
618        // Clients must ensure that "i" is a valid index prior to calling this function
619        const Entry &
620        GetEntryRef (size_t i) const
621        {
622            return m_entries[i];
623        }
624
625        Entry *
626        Back()
627        {
628            if (m_entries.empty())
629                return NULL;
630            return &m_entries.back();
631        }
632
633        const Entry *
634        Back() const
635        {
636            if (m_entries.empty())
637                return NULL;
638            return &m_entries.back();
639        }
640
641        static bool
642        BaseLessThan (const Entry& lhs, const Entry& rhs)
643        {
644            return lhs.GetRangeBase() < rhs.GetRangeBase();
645        }
646
647        uint32_t
648        FindEntryIndexThatContains (B addr) const
649        {
650#ifdef ASSERT_RANGEMAP_ARE_SORTED
651            assert (IsSorted());
652#endif
653            if (!m_entries.empty())
654            {
655                Entry entry (addr, 1);
656                typename Collection::const_iterator begin = m_entries.begin();
657                typename Collection::const_iterator end = m_entries.end();
658                typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
659
660                if (pos != end && pos->Contains(addr))
661                {
662                    return std::distance (begin, pos);
663                }
664                else if (pos != begin)
665                {
666                    --pos;
667                    if (pos->Contains(addr))
668                        return std::distance (begin, pos);
669                }
670            }
671            return UINT32_MAX;
672        }
673
674        const Entry *
675        FindEntryThatContains (B addr) const
676        {
677#ifdef ASSERT_RANGEMAP_ARE_SORTED
678            assert (IsSorted());
679#endif
680            if (!m_entries.empty())
681            {
682                Entry entry (addr, 1);
683                typename Collection::const_iterator begin = m_entries.begin();
684                typename Collection::const_iterator end = m_entries.end();
685                typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
686
687                if (pos != end && pos->Contains(addr))
688                {
689                    return &(*pos);
690                }
691                else if (pos != begin)
692                {
693                    --pos;
694                    if (pos->Contains(addr))
695                    {
696                        return &(*pos);
697                    }
698                }
699            }
700            return NULL;
701        }
702
703        const Entry *
704        FindEntryThatContains (const Entry &range) const
705        {
706#ifdef ASSERT_RANGEMAP_ARE_SORTED
707            assert (IsSorted());
708#endif
709            if (!m_entries.empty())
710            {
711                typename Collection::const_iterator begin = m_entries.begin();
712                typename Collection::const_iterator end = m_entries.end();
713                typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
714
715                if (pos != end && pos->Contains(range))
716                {
717                    return &(*pos);
718                }
719                else if (pos != begin)
720                {
721                    --pos;
722                    if (pos->Contains(range))
723                    {
724                        return &(*pos);
725                    }
726                }
727            }
728            return NULL;
729        }
730
731    protected:
732        Collection m_entries;
733    };
734
735    //----------------------------------------------------------------------
736    // A simple range  with data class where you get to define the type of
737    // the range base "B", the type used for the range byte size "S", and
738    // the type for the associated data "T".
739    //----------------------------------------------------------------------
740    template <typename B, typename S, typename T>
741    struct RangeData : public Range<B,S>
742    {
743        typedef T DataType;
744
745        DataType data;
746
747        RangeData () :
748            Range<B,S> (),
749            data ()
750        {
751        }
752
753        RangeData (B base, S size) :
754            Range<B,S> (base, size),
755            data ()
756        {
757        }
758
759        RangeData (B base, S size, DataType d) :
760            Range<B,S> (base, size),
761            data (d)
762        {
763        }
764
765        bool
766        operator < (const RangeData &rhs) const
767        {
768            if (this->base == rhs.base)
769            {
770                if (this->size == rhs.size)
771                    return this->data < rhs.data;
772                else
773                    return this->size < rhs.size;
774            }
775            return this->base < rhs.base;
776        }
777
778        bool
779        operator == (const RangeData &rhs) const
780        {
781            return this->GetRangeBase() == rhs.GetRangeBase() &&
782                   this->GetByteSize() == rhs.GetByteSize() &&
783                   this->data      == rhs.data;
784        }
785
786        bool
787        operator != (const RangeData &rhs) const
788        {
789            return this->GetRangeBase() != rhs.GetRangeBase() ||
790                   this->GetByteSize() != rhs.GetByteSize() ||
791                   this->data      != rhs.data;
792        }
793    };
794
795    template <typename B, typename S, typename T, unsigned N>
796    class RangeDataArray
797    {
798    public:
799        typedef RangeData<B,S,T> Entry;
800        typedef llvm::SmallVector<Entry, N> Collection;
801
802
803        RangeDataArray ()
804        {
805        }
806
807        ~RangeDataArray()
808        {
809        }
810
811        void
812        Append (const Entry &entry)
813        {
814            m_entries.push_back (entry);
815        }
816
817        void
818        Sort ()
819        {
820            if (m_entries.size() > 1)
821                std::stable_sort (m_entries.begin(), m_entries.end());
822        }
823
824#ifdef ASSERT_RANGEMAP_ARE_SORTED
825        bool
826        IsSorted () const
827        {
828            typename Collection::const_iterator pos, end, prev;
829            // First we determine if we can combine any of the Entry objects so we
830            // don't end up allocating and making a new collection for no reason
831            for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
832            {
833                if (prev != end && *pos < *prev)
834                    return false;
835            }
836            return true;
837        }
838#endif
839
840        void
841        CombineConsecutiveEntriesWithEqualData ()
842        {
843#ifdef ASSERT_RANGEMAP_ARE_SORTED
844            assert (IsSorted());
845#endif
846            typename Collection::iterator pos;
847            typename Collection::iterator end;
848            typename Collection::iterator prev;
849            bool can_combine = false;
850            // First we determine if we can combine any of the Entry objects so we
851            // don't end up allocating and making a new collection for no reason
852            for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
853            {
854                if (prev != end && prev->data == pos->data)
855                {
856                    can_combine = true;
857                    break;
858                }
859            }
860
861            // We we can combine at least one entry, then we make a new collection
862            // and populate it accordingly, and then swap it into place.
863            if (can_combine)
864            {
865                Collection minimal_ranges;
866                for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
867                {
868                    if (prev != end && prev->data == pos->data)
869                        minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd());
870                    else
871                        minimal_ranges.push_back (*pos);
872                }
873                // Use the swap technique in case our new vector is much smaller.
874                // We must swap when using the STL because std::vector objects never
875                // release or reduce the memory once it has been allocated/reserved.
876                m_entries.swap (minimal_ranges);
877            }
878        }
879
880        void
881        Clear ()
882        {
883            m_entries.clear();
884        }
885
886        bool
887        IsEmpty () const
888        {
889            return m_entries.empty();
890        }
891
892        size_t
893        GetSize () const
894        {
895            return m_entries.size();
896        }
897
898        const Entry *
899        GetEntryAtIndex (size_t i) const
900        {
901            if (i<m_entries.size())
902                return &m_entries[i];
903            return NULL;
904        }
905
906        // Clients must ensure that "i" is a valid index prior to calling this function
907        const Entry &
908        GetEntryRef (size_t i) const
909        {
910            return m_entries[i];
911        }
912
913        static bool
914        BaseLessThan (const Entry& lhs, const Entry& rhs)
915        {
916            return lhs.GetRangeBase() < rhs.GetRangeBase();
917        }
918
919        uint32_t
920        FindEntryIndexThatContains (B addr) const
921        {
922#ifdef ASSERT_RANGEMAP_ARE_SORTED
923            assert (IsSorted());
924#endif
925            if ( !m_entries.empty() )
926            {
927                Entry entry (addr, 1);
928                typename Collection::const_iterator begin = m_entries.begin();
929                typename Collection::const_iterator end = m_entries.end();
930                typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
931
932                if (pos != end && pos->Contains(addr))
933                {
934                    return std::distance (begin, pos);
935                }
936                else if (pos != begin)
937                {
938                    --pos;
939                    if (pos->Contains(addr))
940                        return std::distance (begin, pos);
941                }
942            }
943            return UINT32_MAX;
944        }
945
946        Entry *
947        FindEntryThatContains (B addr)
948        {
949#ifdef ASSERT_RANGEMAP_ARE_SORTED
950            assert (IsSorted());
951#endif
952            if ( !m_entries.empty() )
953            {
954                Entry entry;
955                entry.SetRangeBase(addr);
956                entry.SetByteSize(1);
957                typename Collection::iterator begin = m_entries.begin();
958                typename Collection::iterator end = m_entries.end();
959                typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
960
961                if (pos != end && pos->Contains(addr))
962                {
963                    return &(*pos);
964                }
965                else if (pos != begin)
966                {
967                    --pos;
968                    if (pos->Contains(addr))
969                    {
970                        return &(*pos);
971                    }
972                }
973            }
974            return NULL;
975        }
976        const Entry *
977        FindEntryThatContains (B addr) const
978        {
979#ifdef ASSERT_RANGEMAP_ARE_SORTED
980            assert (IsSorted());
981#endif
982            if ( !m_entries.empty() )
983            {
984                Entry entry;
985                entry.SetRangeBase(addr);
986                entry.SetByteSize(1);
987                typename Collection::const_iterator begin = m_entries.begin();
988                typename Collection::const_iterator end = m_entries.end();
989                typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
990
991                if (pos != end && pos->Contains(addr))
992                {
993                    return &(*pos);
994                }
995                else if (pos != begin)
996                {
997                    --pos;
998                    if (pos->Contains(addr))
999                    {
1000                        return &(*pos);
1001                    }
1002                }
1003            }
1004            return NULL;
1005        }
1006
1007        const Entry *
1008        FindEntryThatContains (const Entry &range) const
1009        {
1010#ifdef ASSERT_RANGEMAP_ARE_SORTED
1011            assert (IsSorted());
1012#endif
1013            if ( !m_entries.empty() )
1014            {
1015                typename Collection::const_iterator begin = m_entries.begin();
1016                typename Collection::const_iterator end = m_entries.end();
1017                typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
1018
1019                if (pos != end && pos->Contains(range))
1020                {
1021                    return &(*pos);
1022                }
1023                else if (pos != begin)
1024                {
1025                    --pos;
1026                    if (pos->Contains(range))
1027                    {
1028                        return &(*pos);
1029                    }
1030                }
1031            }
1032            return NULL;
1033        }
1034
1035        Entry *
1036        Back()
1037        {
1038            if (!m_entries.empty())
1039                return &m_entries.back();
1040            return NULL;
1041        }
1042
1043        const Entry *
1044        Back() const
1045        {
1046            if (!m_entries.empty())
1047                return &m_entries.back();
1048            return NULL;
1049        }
1050
1051    protected:
1052        Collection m_entries;
1053    };
1054
1055    // Same as RangeDataArray, but uses std::vector as to not
1056    // require static storage of N items in the class itself
1057    template <typename B, typename S, typename T>
1058    class RangeDataVector
1059    {
1060    public:
1061        typedef RangeData<B,S,T> Entry;
1062        typedef std::vector<Entry> Collection;
1063
1064        RangeDataVector ()
1065        {
1066        }
1067
1068        ~RangeDataVector()
1069        {
1070        }
1071
1072        void
1073        Append (const Entry &entry)
1074        {
1075            m_entries.push_back (entry);
1076        }
1077
1078        void
1079        Sort ()
1080        {
1081            if (m_entries.size() > 1)
1082                std::stable_sort (m_entries.begin(), m_entries.end());
1083        }
1084
1085#ifdef ASSERT_RANGEMAP_ARE_SORTED
1086        bool
1087        IsSorted () const
1088        {
1089            typename Collection::const_iterator pos, end, prev;
1090            // First we determine if we can combine any of the Entry objects so we
1091            // don't end up allocating and making a new collection for no reason
1092            for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
1093            {
1094                if (prev != end && *pos < *prev)
1095                    return false;
1096            }
1097            return true;
1098        }
1099#endif
1100
1101        void
1102        CombineConsecutiveEntriesWithEqualData ()
1103        {
1104#ifdef ASSERT_RANGEMAP_ARE_SORTED
1105            assert (IsSorted());
1106#endif
1107            typename Collection::iterator pos;
1108            typename Collection::iterator end;
1109            typename Collection::iterator prev;
1110            bool can_combine = false;
1111            // First we determine if we can combine any of the Entry objects so we
1112            // don't end up allocating and making a new collection for no reason
1113            for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
1114            {
1115                if (prev != end && prev->data == pos->data)
1116                {
1117                    can_combine = true;
1118                    break;
1119                }
1120            }
1121
1122            // We we can combine at least one entry, then we make a new collection
1123            // and populate it accordingly, and then swap it into place.
1124            if (can_combine)
1125            {
1126                Collection minimal_ranges;
1127                for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
1128                {
1129                    if (prev != end && prev->data == pos->data)
1130                        minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd());
1131                    else
1132                        minimal_ranges.push_back (*pos);
1133                }
1134                // Use the swap technique in case our new vector is much smaller.
1135                // We must swap when using the STL because std::vector objects never
1136                // release or reduce the memory once it has been allocated/reserved.
1137                m_entries.swap (minimal_ranges);
1138            }
1139        }
1140
1141        // Calculate the byte size of ranges with zero byte sizes by finding
1142        // the next entry with a base address > the current base address
1143        void
1144        CalculateSizesOfZeroByteSizeRanges ()
1145        {
1146#ifdef ASSERT_RANGEMAP_ARE_SORTED
1147            assert (IsSorted());
1148#endif
1149            typename Collection::iterator pos;
1150            typename Collection::iterator end;
1151            typename Collection::iterator next;
1152            for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
1153            {
1154                if (pos->GetByteSize() == 0)
1155                {
1156                    // Watch out for multiple entries with same address and make sure
1157                    // we find an entry that is greater than the current base address
1158                    // before we use that for the size
1159                    auto curr_base = pos->GetRangeBase();
1160                    for (next = pos + 1; next != end; ++next)
1161                    {
1162                        auto next_base = next->GetRangeBase();
1163                        if (next_base > curr_base)
1164                        {
1165                            pos->SetByteSize (next_base - curr_base);
1166                            break;
1167                        }
1168                    }
1169                }
1170            }
1171
1172        }
1173
1174        void
1175        Clear ()
1176        {
1177            m_entries.clear();
1178        }
1179
1180        void
1181        Reserve (typename Collection::size_type size)
1182        {
1183            m_entries.resize (size);
1184        }
1185
1186        bool
1187        IsEmpty () const
1188        {
1189            return m_entries.empty();
1190        }
1191
1192        size_t
1193        GetSize () const
1194        {
1195            return m_entries.size();
1196        }
1197
1198        const Entry *
1199        GetEntryAtIndex (size_t i) const
1200        {
1201            if (i<m_entries.size())
1202                return &m_entries[i];
1203            return NULL;
1204        }
1205
1206        // Clients must ensure that "i" is a valid index prior to calling this function
1207        const Entry &
1208        GetEntryRef (size_t i) const
1209        {
1210            return m_entries[i];
1211        }
1212
1213        static bool
1214        BaseLessThan (const Entry& lhs, const Entry& rhs)
1215        {
1216            return lhs.GetRangeBase() < rhs.GetRangeBase();
1217        }
1218
1219        uint32_t
1220        FindEntryIndexThatContains (B addr) const
1221        {
1222#ifdef ASSERT_RANGEMAP_ARE_SORTED
1223            assert (IsSorted());
1224#endif
1225            if ( !m_entries.empty() )
1226            {
1227                Entry entry (addr, 1);
1228                typename Collection::const_iterator begin = m_entries.begin();
1229                typename Collection::const_iterator end = m_entries.end();
1230                typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1231
1232                if (pos != end && pos->Contains(addr))
1233                {
1234                    return std::distance (begin, pos);
1235                }
1236                else if (pos != begin)
1237                {
1238                    --pos;
1239                    if (pos->Contains(addr))
1240                        return std::distance (begin, pos);
1241                }
1242            }
1243            return UINT32_MAX;
1244        }
1245
1246        Entry *
1247        FindEntryThatContains (B addr)
1248        {
1249#ifdef ASSERT_RANGEMAP_ARE_SORTED
1250            assert (IsSorted());
1251#endif
1252            if ( !m_entries.empty() )
1253            {
1254                Entry entry;
1255                entry.SetRangeBase(addr);
1256                entry.SetByteSize(1);
1257                typename Collection::iterator begin = m_entries.begin();
1258                typename Collection::iterator end = m_entries.end();
1259                typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1260
1261                if (pos != end && pos->Contains(addr))
1262                {
1263                    return &(*pos);
1264                }
1265                else if (pos != begin)
1266                {
1267                    --pos;
1268                    if (pos->Contains(addr))
1269                    {
1270                        return &(*pos);
1271                    }
1272                }
1273            }
1274            return NULL;
1275        }
1276        const Entry *
1277        FindEntryThatContains (B addr) const
1278        {
1279#ifdef ASSERT_RANGEMAP_ARE_SORTED
1280            assert (IsSorted());
1281#endif
1282            if ( !m_entries.empty() )
1283            {
1284                Entry entry;
1285                entry.SetRangeBase(addr);
1286                entry.SetByteSize(1);
1287                typename Collection::const_iterator begin = m_entries.begin();
1288                typename Collection::const_iterator end = m_entries.end();
1289                typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1290
1291                if (pos != end && pos->Contains(addr))
1292                {
1293                    return &(*pos);
1294                }
1295                else if (pos != begin)
1296                {
1297                    --pos;
1298                    if (pos->Contains(addr))
1299                    {
1300                        return &(*pos);
1301                    }
1302                }
1303            }
1304            return NULL;
1305        }
1306
1307        const Entry *
1308        FindEntryThatContains (const Entry &range) const
1309        {
1310#ifdef ASSERT_RANGEMAP_ARE_SORTED
1311            assert (IsSorted());
1312#endif
1313            if ( !m_entries.empty() )
1314            {
1315                typename Collection::const_iterator begin = m_entries.begin();
1316                typename Collection::const_iterator end = m_entries.end();
1317                typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
1318
1319                if (pos != end && pos->Contains(range))
1320                {
1321                    return &(*pos);
1322                }
1323                else if (pos != begin)
1324                {
1325                    --pos;
1326                    if (pos->Contains(range))
1327                    {
1328                        return &(*pos);
1329                    }
1330                }
1331            }
1332            return NULL;
1333        }
1334
1335        Entry *
1336        Back()
1337        {
1338            if (!m_entries.empty())
1339                return &m_entries.back();
1340            return NULL;
1341        }
1342
1343        const Entry *
1344        Back() const
1345        {
1346            if (!m_entries.empty())
1347                return &m_entries.back();
1348            return NULL;
1349        }
1350
1351    protected:
1352        Collection m_entries;
1353    };
1354
1355
1356    //----------------------------------------------------------------------
1357    // A simple range  with data class where you get to define the type of
1358    // the range base "B", the type used for the range byte size "S", and
1359    // the type for the associated data "T".
1360    //----------------------------------------------------------------------
1361    template <typename B, typename T>
1362    struct AddressData
1363    {
1364        typedef B BaseType;
1365        typedef T DataType;
1366
1367        BaseType addr;
1368        DataType data;
1369
1370        AddressData () :
1371            addr (),
1372            data ()
1373        {
1374        }
1375
1376        AddressData (B a, DataType d) :
1377            addr (a),
1378            data (d)
1379        {
1380        }
1381
1382        bool
1383        operator < (const AddressData &rhs) const
1384        {
1385            if (this->addr == rhs.addr)
1386                return this->data < rhs.data;
1387            return this->addr < rhs.addr;
1388        }
1389
1390        bool
1391        operator == (const AddressData &rhs) const
1392        {
1393            return this->addr == rhs.addr &&
1394                   this->data == rhs.data;
1395        }
1396
1397        bool
1398        operator != (const AddressData &rhs) const
1399        {
1400            return this->addr != rhs.addr ||
1401                   this->data == rhs.data;
1402        }
1403    };
1404
1405
1406    template <typename B, typename T, unsigned N>
1407    class AddressDataArray
1408    {
1409    public:
1410        typedef AddressData<B,T> Entry;
1411        typedef llvm::SmallVector<Entry, N> Collection;
1412
1413
1414        AddressDataArray ()
1415        {
1416        }
1417
1418        ~AddressDataArray()
1419        {
1420        }
1421
1422        void
1423        Append (const Entry &entry)
1424        {
1425            m_entries.push_back (entry);
1426        }
1427
1428        void
1429        Sort ()
1430        {
1431            if (m_entries.size() > 1)
1432                std::stable_sort (m_entries.begin(), m_entries.end());
1433        }
1434
1435#ifdef ASSERT_RANGEMAP_ARE_SORTED
1436        bool
1437        IsSorted () const
1438        {
1439            typename Collection::const_iterator pos, end, prev;
1440            // First we determine if we can combine any of the Entry objects so we
1441            // don't end up allocating and making a new collection for no reason
1442            for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
1443            {
1444                if (prev != end && *pos < *prev)
1445                    return false;
1446            }
1447            return true;
1448        }
1449#endif
1450
1451        void
1452        Clear ()
1453        {
1454            m_entries.clear();
1455        }
1456
1457        bool
1458        IsEmpty () const
1459        {
1460            return m_entries.empty();
1461        }
1462
1463        size_t
1464        GetSize () const
1465        {
1466            return m_entries.size();
1467        }
1468
1469        const Entry *
1470        GetEntryAtIndex (size_t i) const
1471        {
1472            if (i<m_entries.size())
1473                return &m_entries[i];
1474            return NULL;
1475        }
1476
1477        // Clients must ensure that "i" is a valid index prior to calling this function
1478        const Entry &
1479        GetEntryRef (size_t i) const
1480        {
1481            return m_entries[i];
1482        }
1483
1484        static bool
1485        BaseLessThan (const Entry& lhs, const Entry& rhs)
1486        {
1487            return lhs.addr < rhs.addr;
1488        }
1489
1490        Entry *
1491        FindEntry (B addr, bool exact_match_only)
1492        {
1493#ifdef ASSERT_RANGEMAP_ARE_SORTED
1494            assert (IsSorted());
1495#endif
1496            if ( !m_entries.empty() )
1497            {
1498                Entry entry;
1499                entry.addr = addr;
1500                typename Collection::iterator begin = m_entries.begin();
1501                typename Collection::iterator end = m_entries.end();
1502                typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1503
1504                if (pos != end)
1505                {
1506                    if (pos->addr == addr || !exact_match_only)
1507                        return &(*pos);
1508                }
1509           }
1510            return NULL;
1511        }
1512
1513        const Entry *
1514        FindNextEntry (const Entry *entry)
1515        {
1516            if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end())
1517                return entry + 1;
1518            return NULL;
1519        }
1520
1521        Entry *
1522        Back()
1523        {
1524            if (!m_entries.empty())
1525                return &m_entries.back();
1526            return NULL;
1527        }
1528
1529        const Entry *
1530        Back() const
1531        {
1532            if (!m_entries.empty())
1533                return &m_entries.back();
1534            return NULL;
1535        }
1536
1537    protected:
1538        Collection m_entries;
1539    };
1540
1541} // namespace lldb_private
1542
1543#endif  // liblldb_RangeMap_h_
1544