1 //===-- RangeMap.h ----------------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef liblldb_RangeMap_h_
11 #define liblldb_RangeMap_h_
15 #include "lldb/lldb-private.h"
16 #include "llvm/ADT/SmallVector.h"
18 // Uncomment to make sure all Range objects are sorted when needed
19 //#define ASSERT_RANGEMAP_ARE_SORTED
21 namespace lldb_private {
24 //----------------------------------------------------------------------
25 // Templatized classes for dealing with generic ranges and also
26 // collections of ranges, or collections of ranges that have associated
28 //----------------------------------------------------------------------
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>
49 Range (BaseType b, SizeType s) :
56 Clear (BaseType b = 0)
62 // Set the start value for the range, and keep the same size
70 SetRangeBase (BaseType b)
76 Slide (BaseType slide)
88 SetRangeEnd (BaseType end)
103 SetByteSize (SizeType s)
115 Contains (BaseType r) const
117 return (GetRangeBase() <= r) && (r < GetRangeEnd());
121 ContainsEndInclusive (BaseType r) const
123 return (GetRangeBase() <= r) && (r <= GetRangeEnd());
127 Contains (const Range& range) const
129 return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd());
133 Overlap (const Range &rhs) const
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);
144 operator < (const Range &rhs) const
146 if (base == rhs.base)
147 return size < rhs.size;
148 return base < rhs.base;
152 operator == (const Range &rhs) const
154 return base == rhs.base && size == rhs.size;
158 operator != (const Range &rhs) const
160 return base != rhs.base || size != rhs.size;
164 //----------------------------------------------------------------------
165 // A range array class where you get to define the type of the ranges
166 // that the collection contains.
167 //----------------------------------------------------------------------
169 template <typename B, typename S, unsigned N>
175 typedef Range<B,S> Entry;
176 typedef llvm::SmallVector<Entry, N> Collection;
188 Append (const Entry &entry)
190 m_entries.push_back (entry);
194 RemoveEntrtAtIndex (uint32_t idx)
196 if (idx < m_entries.size())
198 m_entries.erase (m_entries.begin() + idx);
207 if (m_entries.size() > 1)
208 std::stable_sort (m_entries.begin(), m_entries.end());
211 #ifdef ASSERT_RANGEMAP_ARE_SORTED
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++)
220 if (prev != end && *pos < *prev)
227 CombineConsecutiveRanges ()
229 #ifdef ASSERT_RANGEMAP_ARE_SORTED
232 // Can't combine if ranges if we have zero or one range
233 if (m_entries.size() > 1)
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++)
244 if (prev != end && prev->Overlap(*pos))
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.
255 Collection minimal_ranges;
256 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
258 if (prev != end && prev->Overlap(*pos))
259 minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
261 minimal_ranges.push_back (*pos);
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);
273 GetMinRangeBase (BaseType fail_value) const
275 #ifdef ASSERT_RANGEMAP_ARE_SORTED
278 if (m_entries.empty())
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();
286 GetMaxRangeEnd (BaseType fail_value) const
288 #ifdef ASSERT_RANGEMAP_ARE_SORTED
291 if (m_entries.empty())
293 // m_entries must be sorted, so if we aren't empty, we grab the
295 return m_entries.back().GetRangeEnd();
299 Slide (BaseType slide)
301 typename Collection::iterator pos, end;
302 for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
315 return m_entries.empty();
321 return m_entries.size();
325 GetEntryAtIndex (size_t i) const
327 if (i<m_entries.size())
328 return &m_entries[i];
332 // Clients must ensure that "i" is a valid index prior to calling this function
334 GetEntryRef (size_t i) const
342 if (m_entries.empty())
344 return &m_entries.back();
350 if (m_entries.empty())
352 return &m_entries.back();
356 BaseLessThan (const Entry& lhs, const Entry& rhs)
358 return lhs.GetRangeBase() < rhs.GetRangeBase();
362 FindEntryIndexThatContains (B addr) const
364 #ifdef ASSERT_RANGEMAP_ARE_SORTED
367 if (!m_entries.empty())
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);
374 if (pos != end && pos->Contains(addr))
376 return std::distance (begin, pos);
378 else if (pos != begin)
381 if (pos->Contains(addr))
382 return std::distance (begin, pos);
389 FindEntryThatContains (B addr) const
391 #ifdef ASSERT_RANGEMAP_ARE_SORTED
394 if (!m_entries.empty())
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);
401 if (pos != end && pos->Contains(addr))
405 else if (pos != begin)
408 if (pos->Contains(addr))
418 FindEntryThatContains (const Entry &range) const
420 #ifdef ASSERT_RANGEMAP_ARE_SORTED
423 if (!m_entries.empty())
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);
429 if (pos != end && pos->Contains(range))
433 else if (pos != begin)
436 if (pos->Contains(range))
446 Collection m_entries;
449 template <typename B, typename S>
455 typedef Range<B,S> Entry;
456 typedef std::vector<Entry> Collection;
468 Append (const Entry &entry)
470 m_entries.push_back (entry);
474 RemoveEntrtAtIndex (uint32_t idx)
476 if (idx < m_entries.size())
478 m_entries.erase (m_entries.begin() + idx);
487 if (m_entries.size() > 1)
488 std::stable_sort (m_entries.begin(), m_entries.end());
491 #ifdef ASSERT_RANGEMAP_ARE_SORTED
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++)
500 if (prev != end && *pos < *prev)
507 CombineConsecutiveRanges ()
509 #ifdef ASSERT_RANGEMAP_ARE_SORTED
512 // Can't combine if ranges if we have zero or one range
513 if (m_entries.size() > 1)
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++)
524 if (prev != end && prev->Overlap(*pos))
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.
535 Collection minimal_ranges;
536 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
538 if (prev != end && prev->Overlap(*pos))
539 minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
541 minimal_ranges.push_back (*pos);
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);
553 GetMinRangeBase (BaseType fail_value) const
555 #ifdef ASSERT_RANGEMAP_ARE_SORTED
558 if (m_entries.empty())
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();
566 GetMaxRangeEnd (BaseType fail_value) const
568 #ifdef ASSERT_RANGEMAP_ARE_SORTED
571 if (m_entries.empty())
573 // m_entries must be sorted, so if we aren't empty, we grab the
575 return m_entries.back().GetRangeEnd();
579 Slide (BaseType slide)
581 typename Collection::iterator pos, end;
582 for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
593 Reserve (typename Collection::size_type size)
595 m_entries.reserve (size);
601 return m_entries.empty();
607 return m_entries.size();
611 GetEntryAtIndex (size_t i) const
613 if (i<m_entries.size())
614 return &m_entries[i];
618 // Clients must ensure that "i" is a valid index prior to calling this function
620 GetEntryRef (size_t i) const
628 if (m_entries.empty())
630 return &m_entries.back();
636 if (m_entries.empty())
638 return &m_entries.back();
642 BaseLessThan (const Entry& lhs, const Entry& rhs)
644 return lhs.GetRangeBase() < rhs.GetRangeBase();
648 FindEntryIndexThatContains (B addr) const
650 #ifdef ASSERT_RANGEMAP_ARE_SORTED
653 if (!m_entries.empty())
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);
660 if (pos != end && pos->Contains(addr))
662 return std::distance (begin, pos);
664 else if (pos != begin)
667 if (pos->Contains(addr))
668 return std::distance (begin, pos);
675 FindEntryThatContains (B addr) const
677 #ifdef ASSERT_RANGEMAP_ARE_SORTED
680 if (!m_entries.empty())
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);
687 if (pos != end && pos->Contains(addr))
691 else if (pos != begin)
694 if (pos->Contains(addr))
704 FindEntryThatContains (const Entry &range) const
706 #ifdef ASSERT_RANGEMAP_ARE_SORTED
709 if (!m_entries.empty())
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);
715 if (pos != end && pos->Contains(range))
719 else if (pos != begin)
722 if (pos->Contains(range))
732 Collection m_entries;
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>
753 RangeData (B base, S size) :
754 Range<B,S> (base, size),
759 RangeData (B base, S size, DataType d) :
760 Range<B,S> (base, size),
766 operator < (const RangeData &rhs) const
768 if (this->base == rhs.base)
770 if (this->size == rhs.size)
771 return this->data < rhs.data;
773 return this->size < rhs.size;
775 return this->base < rhs.base;
779 operator == (const RangeData &rhs) const
781 return this->GetRangeBase() == rhs.GetRangeBase() &&
782 this->GetByteSize() == rhs.GetByteSize() &&
783 this->data == rhs.data;
787 operator != (const RangeData &rhs) const
789 return this->GetRangeBase() != rhs.GetRangeBase() ||
790 this->GetByteSize() != rhs.GetByteSize() ||
791 this->data != rhs.data;
795 template <typename B, typename S, typename T, unsigned N>
799 typedef RangeData<B,S,T> Entry;
800 typedef llvm::SmallVector<Entry, N> Collection;
812 Append (const Entry &entry)
814 m_entries.push_back (entry);
820 if (m_entries.size() > 1)
821 std::stable_sort (m_entries.begin(), m_entries.end());
824 #ifdef ASSERT_RANGEMAP_ARE_SORTED
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++)
833 if (prev != end && *pos < *prev)
841 CombineConsecutiveEntriesWithEqualData ()
843 #ifdef ASSERT_RANGEMAP_ARE_SORTED
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++)
854 if (prev != end && prev->data == pos->data)
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.
865 Collection minimal_ranges;
866 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
868 if (prev != end && prev->data == pos->data)
869 minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd());
871 minimal_ranges.push_back (*pos);
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);
889 return m_entries.empty();
895 return m_entries.size();
899 GetEntryAtIndex (size_t i) const
901 if (i<m_entries.size())
902 return &m_entries[i];
906 // Clients must ensure that "i" is a valid index prior to calling this function
908 GetEntryRef (size_t i) const
914 BaseLessThan (const Entry& lhs, const Entry& rhs)
916 return lhs.GetRangeBase() < rhs.GetRangeBase();
920 FindEntryIndexThatContains (B addr) const
922 #ifdef ASSERT_RANGEMAP_ARE_SORTED
925 if ( !m_entries.empty() )
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);
932 if (pos != end && pos->Contains(addr))
934 return std::distance (begin, pos);
936 else if (pos != begin)
939 if (pos->Contains(addr))
940 return std::distance (begin, pos);
947 FindEntryThatContains (B addr)
949 #ifdef ASSERT_RANGEMAP_ARE_SORTED
952 if ( !m_entries.empty() )
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);
961 if (pos != end && pos->Contains(addr))
965 else if (pos != begin)
968 if (pos->Contains(addr))
977 FindEntryThatContains (B addr) const
979 #ifdef ASSERT_RANGEMAP_ARE_SORTED
982 if ( !m_entries.empty() )
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);
991 if (pos != end && pos->Contains(addr))
995 else if (pos != begin)
998 if (pos->Contains(addr))
1008 FindEntryThatContains (const Entry &range) const
1010 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1011 assert (IsSorted());
1013 if ( !m_entries.empty() )
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);
1019 if (pos != end && pos->Contains(range))
1023 else if (pos != begin)
1026 if (pos->Contains(range))
1038 if (!m_entries.empty())
1039 return &m_entries.back();
1046 if (!m_entries.empty())
1047 return &m_entries.back();
1052 Collection m_entries;
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
1061 typedef RangeData<B,S,T> Entry;
1062 typedef std::vector<Entry> Collection;
1073 Append (const Entry &entry)
1075 m_entries.push_back (entry);
1081 if (m_entries.size() > 1)
1082 std::stable_sort (m_entries.begin(), m_entries.end());
1085 #ifdef ASSERT_RANGEMAP_ARE_SORTED
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++)
1094 if (prev != end && *pos < *prev)
1102 CombineConsecutiveEntriesWithEqualData ()
1104 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1105 assert (IsSorted());
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++)
1115 if (prev != end && prev->data == pos->data)
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.
1126 Collection minimal_ranges;
1127 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
1129 if (prev != end && prev->data == pos->data)
1130 minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd());
1132 minimal_ranges.push_back (*pos);
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);
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
1144 CalculateSizesOfZeroByteSizeRanges ()
1146 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1147 assert (IsSorted());
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)
1154 if (pos->GetByteSize() == 0)
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)
1162 auto next_base = next->GetRangeBase();
1163 if (next_base > curr_base)
1165 pos->SetByteSize (next_base - curr_base);
1181 Reserve (typename Collection::size_type size)
1183 m_entries.resize (size);
1189 return m_entries.empty();
1195 return m_entries.size();
1199 GetEntryAtIndex (size_t i) const
1201 if (i<m_entries.size())
1202 return &m_entries[i];
1206 // Clients must ensure that "i" is a valid index prior to calling this function
1208 GetEntryRef (size_t i) const
1210 return m_entries[i];
1214 BaseLessThan (const Entry& lhs, const Entry& rhs)
1216 return lhs.GetRangeBase() < rhs.GetRangeBase();
1220 FindEntryIndexThatContains (B addr) const
1222 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1223 assert (IsSorted());
1225 if ( !m_entries.empty() )
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);
1232 while(pos != begin && pos[-1].Contains(addr))
1235 if (pos != end && pos->Contains(addr))
1236 return std::distance (begin, pos);
1242 FindEntryThatContains (B addr)
1244 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1245 assert (IsSorted());
1247 if ( !m_entries.empty() )
1250 entry.SetRangeBase(addr);
1251 entry.SetByteSize(1);
1252 typename Collection::iterator begin = m_entries.begin();
1253 typename Collection::iterator end = m_entries.end();
1254 typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1256 while(pos != begin && pos[-1].Contains(addr))
1259 if (pos != end && pos->Contains(addr))
1265 FindEntryThatContains (B addr) const
1267 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1268 assert (IsSorted());
1270 if ( !m_entries.empty() )
1273 entry.SetRangeBase(addr);
1274 entry.SetByteSize(1);
1275 typename Collection::const_iterator begin = m_entries.begin();
1276 typename Collection::const_iterator end = m_entries.end();
1277 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1279 while(pos != begin && pos[-1].Contains(addr))
1282 if (pos != end && pos->Contains(addr))
1289 FindEntryThatContains (const Entry &range) const
1291 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1292 assert (IsSorted());
1294 if ( !m_entries.empty() )
1296 typename Collection::const_iterator begin = m_entries.begin();
1297 typename Collection::const_iterator end = m_entries.end();
1298 typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
1300 while(pos != begin && pos[-1].Contains(range))
1303 if (pos != end && pos->Contains(range))
1312 if (!m_entries.empty())
1313 return &m_entries.back();
1320 if (!m_entries.empty())
1321 return &m_entries.back();
1326 Collection m_entries;
1330 //----------------------------------------------------------------------
1331 // A simple range with data class where you get to define the type of
1332 // the range base "B", the type used for the range byte size "S", and
1333 // the type for the associated data "T".
1334 //----------------------------------------------------------------------
1335 template <typename B, typename T>
1350 AddressData (B a, DataType d) :
1357 operator < (const AddressData &rhs) const
1359 if (this->addr == rhs.addr)
1360 return this->data < rhs.data;
1361 return this->addr < rhs.addr;
1365 operator == (const AddressData &rhs) const
1367 return this->addr == rhs.addr &&
1368 this->data == rhs.data;
1372 operator != (const AddressData &rhs) const
1374 return this->addr != rhs.addr ||
1375 this->data == rhs.data;
1380 template <typename B, typename T, unsigned N>
1381 class AddressDataArray
1384 typedef AddressData<B,T> Entry;
1385 typedef llvm::SmallVector<Entry, N> Collection;
1397 Append (const Entry &entry)
1399 m_entries.push_back (entry);
1405 if (m_entries.size() > 1)
1406 std::stable_sort (m_entries.begin(), m_entries.end());
1409 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1413 typename Collection::const_iterator pos, end, prev;
1414 // First we determine if we can combine any of the Entry objects so we
1415 // don't end up allocating and making a new collection for no reason
1416 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
1418 if (prev != end && *pos < *prev)
1434 return m_entries.empty();
1440 return m_entries.size();
1444 GetEntryAtIndex (size_t i) const
1446 if (i<m_entries.size())
1447 return &m_entries[i];
1451 // Clients must ensure that "i" is a valid index prior to calling this function
1453 GetEntryRef (size_t i) const
1455 return m_entries[i];
1459 BaseLessThan (const Entry& lhs, const Entry& rhs)
1461 return lhs.addr < rhs.addr;
1465 FindEntry (B addr, bool exact_match_only)
1467 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1468 assert (IsSorted());
1470 if ( !m_entries.empty() )
1474 typename Collection::iterator begin = m_entries.begin();
1475 typename Collection::iterator end = m_entries.end();
1476 typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1478 while(pos != begin && pos[-1].addr == addr)
1483 if (pos->addr == addr || !exact_match_only)
1491 FindNextEntry (const Entry *entry)
1493 if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end())
1501 if (!m_entries.empty())
1502 return &m_entries.back();
1509 if (!m_entries.empty())
1510 return &m_entries.back();
1515 Collection m_entries;
1518 } // namespace lldb_private
1520 #endif // liblldb_RangeMap_h_