RangeMap.h revision 61aca5dd78f07de66e997d41af521ab9d8c16b89 
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 "lldb/lldb-private.h"
14#include <vector>
15
16namespace lldb_private {
17
18    //----------------------------------------------------------------------
19    // Templatized classes for dealing with generic ranges and also
20    // collections of ranges, or collections of ranges that have associated
21    // data.
22    //----------------------------------------------------------------------
23
24    //----------------------------------------------------------------------
25    // A simple range class where you get to define the type of the range
26    // base "B", and the type used for the range byte size "S".
27    //----------------------------------------------------------------------
28    template <typename B, typename S>
29    struct Range
30    {
31        typedef B BaseType;
32        typedef S SizeType;
33
34        BaseType base;
35        SizeType size;
36
37        Range () :
38            base (0),
39            size (0)
40        {
41        }
42
43        Range (BaseType b, SizeType s) :
44            base (b),
45            size (s)
46        {
47        }
48
49        // Set the start value for the range, and keep the same size
50        BaseType
51        GetRangeBase () const
52        {
53            return base;
54        }
55
56        void
57        SetRangeBase (BaseType b)
58        {
59            base = b;
60        }
61
62        BaseType
63        GetRangeEnd () const
64        {
65            return base + size;
66        }
67
68        void
69        SetRangeEnd (BaseType end)
70        {
71            if (end > base)
72                size = end - base;
73            else
74                size = 0;
75        }
76
77        SizeType
78        GetByteSize () const
79        {
80            return size;
81        }
82
83        void
84        SetByteSize (SizeType s)
85        {
86            size = s;
87        }
88
89        bool
90        IsValid() const
91        {
92            return size > 0;
93        }
94
95        bool
96        Contains (BaseType r) const
97        {
98            return (GetRangeBase() <= r) && (r < GetRangeEnd());
99        }
100
101        bool
102        ContainsEndInclusive (BaseType r) const
103        {
104            return (GetRangeBase() <= r) && (r <= GetRangeEnd());
105        }
106
107        bool
108        Contains (const Range& range) const
109        {
110            return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd());
111        }
112
113        bool
114        operator < (const Range &rhs)
115        {
116            if (base == rhs.base)
117                return size < rhs.size;
118            return base < rhs.base;
119        }
120
121        bool
122        operator == (const Range &rhs)
123        {
124            return base == rhs.base && size == rhs.size;
125        }
126
127        bool
128        operator != (const Range &rhs)
129        {
130            return  base != rhs.base || size != rhs.size;
131        }
132    };
133
134    //----------------------------------------------------------------------
135    // A range array class where you get to define the type of the ranges
136    // that the collection contains.
137    //----------------------------------------------------------------------
138
139    template <typename B, typename S>
140    class RangeArray
141    {
142        typedef Range<B,S> Entry;
143
144        RangeArray ()
145        {
146        }
147
148        ~RangeArray()
149        {
150        }
151
152        void
153        Append (const Entry &entry)
154        {
155            m_entries.push_back (entry);
156        }
157
158        void
159        Sort ()
160        {
161            if (m_entries.size() > 1)
162                std::stable_sort (m_entries.begin(), m_entries.end());
163        }
164
165        void
166        CombineConsecutiveEntriesWithEqualData ()
167        {
168            typename std::vector<Entry>::iterator pos;
169            typename std::vector<Entry>::iterator end;
170            typename std::vector<Entry>::iterator prev;
171            bool can_combine = false;
172            // First we determine if we can combine any of the Entry objects so we
173            // don't end up allocating and making a new collection for no reason
174            for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
175            {
176                if (prev != end && prev->data == pos->data)
177                {
178                    can_combine = true;
179                    break;
180                }
181            }
182
183            // We we can combine at least one entry, then we make a new collection
184            // and populate it accordingly, and then swap it into place.
185            if (can_combine)
186            {
187                std::vector<Entry> minimal_ranges;
188                for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
189                {
190                    if (prev != end && prev->data == pos->data)
191                        minimal_ranges.back().range.SetEnd (pos->range.GetRangeEnd());
192                    else
193                        minimal_ranges.push_back (*pos);
194                }
195                // Use the swap technique in case our new vector is much smaller.
196                // We must swap when using the STL because std::vector objects never
197                // release or reduce the memory once it has been allocated/reserved.
198                m_entries.swap (minimal_ranges);
199            }
200        }
201
202        void
203        Clear ()
204        {
205            m_entries.clear();
206        }
207
208        bool
209        IsEmpty () const
210        {
211            return m_entries.empty();
212        }
213
214        size_t
215        GetNumEntries () const
216        {
217            return m_entries.size();
218        }
219
220        const Entry *
221        GetEntryAtIndex (uint32_t i) const
222        {
223            if (i<m_entries.size())
224                return &m_entries[i];
225            return NULL;
226        }
227
228        static bool
229        BaseLessThan (const Entry& lhs, const Entry& rhs)
230        {
231            return lhs.GetRangeBase() < rhs.GetRangeBase();
232        }
233
234        const Entry *
235        FindEntryThatContains (B addr) const
236        {
237            if ( !m_entries.empty() )
238            {
239                Entry entry (addr, 1);
240                typename std::vector<Entry>::const_iterator begin = m_entries.begin();
241                typename std::vector<Entry>::const_iterator end = m_entries.end();
242                typename std::vector<Entry>::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
243
244                if (pos != end && pos->Contains(addr))
245                {
246                    return &(*pos);
247                }
248                else if (pos != begin)
249                {
250                    --pos;
251                    if (pos->Contains(addr))
252                    {
253                        return &(*pos);
254                    }
255                }
256            }
257            return NULL;
258        }
259
260    protected:
261        std::vector<Entry> m_entries;
262    };
263
264    //----------------------------------------------------------------------
265    // A simple range  with data class where you get to define the type of
266    // the range base "B", the type used for the range byte size "S", and
267    // the type for the associated data "T".
268    //----------------------------------------------------------------------
269    template <typename B, typename S, typename T>
270    struct RangeData : public Range<B,S>
271    {
272        typedef T DataType;
273
274        DataType data;
275
276        RangeData () :
277            Range<B,S> (),
278            data ()
279        {
280        }
281
282        RangeData (B base, S size, DataType d) :
283            Range<B,S> (base, size),
284            data (d)
285        {
286        }
287
288        bool
289        operator < (const RangeData &rhs) const
290        {
291            if (this->base == rhs.base)
292            {
293                if (this->size == rhs.size)
294                    return this->data < rhs.data;
295                else
296                    return this->size < rhs.size;
297            }
298            return this->base < rhs.base;
299        }
300
301        bool
302        operator == (const RangeData &rhs) const
303        {
304            return this->GetRangeBase() == rhs.GetRangeBase() &&
305                   this->GetByteSize() == rhs.GetByteSize() &&
306                   this->data      == rhs.data;
307        }
308
309        bool
310        operator != (const RangeData &rhs) const
311        {
312            return this->GetRangeBase() != rhs.GetRangeBase() ||
313                   this->GetByteSize() != rhs.GetByteSize() ||
314                   this->data      != rhs.data;
315        }
316    };
317
318    template <typename B, typename S, typename T>
319    class RangeDataArray
320    {
321    public:
322        typedef RangeData<B,S,T> Entry;
323
324        RangeDataArray ()
325        {
326        }
327
328        ~RangeDataArray()
329        {
330        }
331
332        void
333        Append (const Entry &entry)
334        {
335            m_entries.push_back (entry);
336        }
337
338        void
339        Sort ()
340        {
341            if (m_entries.size() > 1)
342                std::stable_sort (m_entries.begin(), m_entries.end());
343        }
344
345        void
346        CombineConsecutiveEntriesWithEqualData ()
347        {
348            typename std::vector<Entry>::iterator pos;
349            typename std::vector<Entry>::iterator end;
350            typename std::vector<Entry>::iterator prev;
351            bool can_combine = false;
352            // First we determine if we can combine any of the Entry objects so we
353            // don't end up allocating and making a new collection for no reason
354            for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
355            {
356                if (prev != end && prev->data == pos->data)
357                {
358                    can_combine = true;
359                    break;
360                }
361            }
362
363            // We we can combine at least one entry, then we make a new collection
364            // and populate it accordingly, and then swap it into place.
365            if (can_combine)
366            {
367                std::vector<Entry> minimal_ranges;
368                for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
369                {
370                    if (prev != end && prev->data == pos->data)
371                        minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd());
372                    else
373                        minimal_ranges.push_back (*pos);
374                }
375                // Use the swap technique in case our new vector is much smaller.
376                // We must swap when using the STL because std::vector objects never
377                // release or reduce the memory once it has been allocated/reserved.
378                m_entries.swap (minimal_ranges);
379            }
380        }
381
382        void
383        Clear ()
384        {
385            m_entries.clear();
386        }
387
388        bool
389        IsEmpty () const
390        {
391            return m_entries.empty();
392        }
393
394        size_t
395        GetNumEntries () const
396        {
397            return m_entries.size();
398        }
399
400        const Entry *
401        GetEntryAtIndex (uint32_t i) const
402        {
403            if (i<m_entries.size())
404                return &m_entries[i];
405            return NULL;
406        }
407
408        static bool
409        BaseLessThan (const Entry& lhs, const Entry& rhs)
410        {
411            return lhs.GetRangeBase() < rhs.GetRangeBase();
412        }
413
414        const Entry *
415        FindEntryThatContains (B addr) const
416        {
417            if ( !m_entries.empty() )
418            {
419                Entry entry;
420                entry.SetRangeBase(addr);
421                entry.SetByteSize(1);
422                typename std::vector<Entry>::const_iterator begin = m_entries.begin();
423                typename std::vector<Entry>::const_iterator end = m_entries.end();
424                typename std::vector<Entry>::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
425
426                if (pos != end && pos->Contains(addr))
427                {
428                    return &(*pos);
429                }
430                else if (pos != begin)
431                {
432                    --pos;
433                    if (pos->Contains(addr))
434                    {
435                        return &(*pos);
436                    }
437                }
438            }
439            return NULL;
440        }
441
442    protected:
443        std::vector<Entry> m_entries;
444    };
445
446} // namespace lldb_private
447
448#endif  // liblldb_RangeMap_h_
449