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());
132 // Returns true if the two ranges adjoing or intersect
134 DoesAdjoinOrIntersect (const Range &rhs) const
136 const BaseType lhs_base = this->GetRangeBase();
137 const BaseType rhs_base = rhs.GetRangeBase();
138 const BaseType lhs_end = this->GetRangeEnd();
139 const BaseType rhs_end = rhs.GetRangeEnd();
140 bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base);
144 // Returns true if the two ranges intersect
146 DoesIntersect (const Range &rhs) const
148 const BaseType lhs_base = this->GetRangeBase();
149 const BaseType rhs_base = rhs.GetRangeBase();
150 const BaseType lhs_end = this->GetRangeEnd();
151 const BaseType rhs_end = rhs.GetRangeEnd();
152 bool result = (lhs_base < rhs_end) && (lhs_end > rhs_base);
157 operator < (const Range &rhs) const
159 if (base == rhs.base)
160 return size < rhs.size;
161 return base < rhs.base;
165 operator == (const Range &rhs) const
167 return base == rhs.base && size == rhs.size;
171 operator != (const Range &rhs) const
173 return base != rhs.base || size != rhs.size;
177 //----------------------------------------------------------------------
178 // A range array class where you get to define the type of the ranges
179 // that the collection contains.
180 //----------------------------------------------------------------------
182 template <typename B, typename S, unsigned N>
188 typedef Range<B,S> Entry;
189 typedef llvm::SmallVector<Entry, N> Collection;
201 Append (const Entry &entry)
203 m_entries.push_back (entry);
207 RemoveEntrtAtIndex (uint32_t idx)
209 if (idx < m_entries.size())
211 m_entries.erase (m_entries.begin() + idx);
220 if (m_entries.size() > 1)
221 std::stable_sort (m_entries.begin(), m_entries.end());
224 #ifdef ASSERT_RANGEMAP_ARE_SORTED
228 typename Collection::const_iterator pos, end, prev;
229 // First we determine if we can combine any of the Entry objects so we
230 // don't end up allocating and making a new collection for no reason
231 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
233 if (prev != end && *pos < *prev)
240 CombineConsecutiveRanges ()
242 #ifdef ASSERT_RANGEMAP_ARE_SORTED
245 // Can't combine if ranges if we have zero or one range
246 if (m_entries.size() > 1)
248 // The list should be sorted prior to calling this function
249 typename Collection::iterator pos;
250 typename Collection::iterator end;
251 typename Collection::iterator prev;
252 bool can_combine = false;
253 // First we determine if we can combine any of the Entry objects so we
254 // don't end up allocating and making a new collection for no reason
255 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
257 if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
264 // We we can combine at least one entry, then we make a new collection
265 // and populate it accordingly, and then swap it into place.
268 Collection minimal_ranges;
269 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
271 if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
272 minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
274 minimal_ranges.push_back (*pos);
276 // Use the swap technique in case our new vector is much smaller.
277 // We must swap when using the STL because std::vector objects never
278 // release or reduce the memory once it has been allocated/reserved.
279 m_entries.swap (minimal_ranges);
286 GetMinRangeBase (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
294 // first range's base
295 return m_entries.front().GetRangeBase();
299 GetMaxRangeEnd (BaseType fail_value) const
301 #ifdef ASSERT_RANGEMAP_ARE_SORTED
304 if (m_entries.empty())
306 // m_entries must be sorted, so if we aren't empty, we grab the
308 return m_entries.back().GetRangeEnd();
312 Slide (BaseType slide)
314 typename Collection::iterator pos, end;
315 for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
328 return m_entries.empty();
334 return m_entries.size();
338 GetEntryAtIndex (size_t i) const
340 if (i<m_entries.size())
341 return &m_entries[i];
345 // Clients must ensure that "i" is a valid index prior to calling this function
347 GetEntryRef (size_t i) const
355 if (m_entries.empty())
357 return &m_entries.back();
363 if (m_entries.empty())
365 return &m_entries.back();
369 BaseLessThan (const Entry& lhs, const Entry& rhs)
371 return lhs.GetRangeBase() < rhs.GetRangeBase();
375 FindEntryIndexThatContains (B addr) const
377 #ifdef ASSERT_RANGEMAP_ARE_SORTED
380 if (!m_entries.empty())
382 Entry entry (addr, 1);
383 typename Collection::const_iterator begin = m_entries.begin();
384 typename Collection::const_iterator end = m_entries.end();
385 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
387 if (pos != end && pos->Contains(addr))
389 return std::distance (begin, pos);
391 else if (pos != begin)
394 if (pos->Contains(addr))
395 return std::distance (begin, pos);
402 FindEntryThatContains (B addr) const
404 #ifdef ASSERT_RANGEMAP_ARE_SORTED
407 if (!m_entries.empty())
409 Entry entry (addr, 1);
410 typename Collection::const_iterator begin = m_entries.begin();
411 typename Collection::const_iterator end = m_entries.end();
412 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
414 if (pos != end && pos->Contains(addr))
418 else if (pos != begin)
421 if (pos->Contains(addr))
431 FindEntryThatContains (const Entry &range) const
433 #ifdef ASSERT_RANGEMAP_ARE_SORTED
436 if (!m_entries.empty())
438 typename Collection::const_iterator begin = m_entries.begin();
439 typename Collection::const_iterator end = m_entries.end();
440 typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
442 if (pos != end && pos->Contains(range))
446 else if (pos != begin)
449 if (pos->Contains(range))
459 Collection m_entries;
462 template <typename B, typename S>
468 typedef Range<B,S> Entry;
469 typedef std::vector<Entry> Collection;
481 Append (const Entry &entry)
483 m_entries.push_back (entry);
487 RemoveEntrtAtIndex (uint32_t idx)
489 if (idx < m_entries.size())
491 m_entries.erase (m_entries.begin() + idx);
500 if (m_entries.size() > 1)
501 std::stable_sort (m_entries.begin(), m_entries.end());
504 #ifdef ASSERT_RANGEMAP_ARE_SORTED
508 typename Collection::const_iterator pos, end, prev;
509 // First we determine if we can combine any of the Entry objects so we
510 // don't end up allocating and making a new collection for no reason
511 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
513 if (prev != end && *pos < *prev)
520 CombineConsecutiveRanges ()
522 #ifdef ASSERT_RANGEMAP_ARE_SORTED
525 // Can't combine if ranges if we have zero or one range
526 if (m_entries.size() > 1)
528 // The list should be sorted prior to calling this function
529 typename Collection::iterator pos;
530 typename Collection::iterator end;
531 typename Collection::iterator prev;
532 bool can_combine = false;
533 // First we determine if we can combine any of the Entry objects so we
534 // don't end up allocating and making a new collection for no reason
535 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
537 if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
544 // We we can combine at least one entry, then we make a new collection
545 // and populate it accordingly, and then swap it into place.
548 Collection minimal_ranges;
549 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
551 if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
552 minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
554 minimal_ranges.push_back (*pos);
556 // Use the swap technique in case our new vector is much smaller.
557 // We must swap when using the STL because std::vector objects never
558 // release or reduce the memory once it has been allocated/reserved.
559 m_entries.swap (minimal_ranges);
566 GetMinRangeBase (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
574 // first range's base
575 return m_entries.front().GetRangeBase();
579 GetMaxRangeEnd (BaseType fail_value) const
581 #ifdef ASSERT_RANGEMAP_ARE_SORTED
584 if (m_entries.empty())
586 // m_entries must be sorted, so if we aren't empty, we grab the
588 return m_entries.back().GetRangeEnd();
592 Slide (BaseType slide)
594 typename Collection::iterator pos, end;
595 for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
606 Reserve (typename Collection::size_type size)
608 m_entries.reserve (size);
614 return m_entries.empty();
620 return m_entries.size();
624 GetEntryAtIndex (size_t i) const
626 if (i<m_entries.size())
627 return &m_entries[i];
631 // Clients must ensure that "i" is a valid index prior to calling this function
633 GetEntryRef (size_t i) const
641 if (m_entries.empty())
643 return &m_entries.back();
649 if (m_entries.empty())
651 return &m_entries.back();
655 BaseLessThan (const Entry& lhs, const Entry& rhs)
657 return lhs.GetRangeBase() < rhs.GetRangeBase();
661 FindEntryIndexThatContains (B addr) const
663 #ifdef ASSERT_RANGEMAP_ARE_SORTED
666 if (!m_entries.empty())
668 Entry entry (addr, 1);
669 typename Collection::const_iterator begin = m_entries.begin();
670 typename Collection::const_iterator end = m_entries.end();
671 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
673 if (pos != end && pos->Contains(addr))
675 return std::distance (begin, pos);
677 else if (pos != begin)
680 if (pos->Contains(addr))
681 return std::distance (begin, pos);
688 FindEntryThatContains (B addr) const
690 #ifdef ASSERT_RANGEMAP_ARE_SORTED
693 if (!m_entries.empty())
695 Entry entry (addr, 1);
696 typename Collection::const_iterator begin = m_entries.begin();
697 typename Collection::const_iterator end = m_entries.end();
698 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
700 if (pos != end && pos->Contains(addr))
704 else if (pos != begin)
707 if (pos->Contains(addr))
717 FindEntryThatContains (const Entry &range) const
719 #ifdef ASSERT_RANGEMAP_ARE_SORTED
722 if (!m_entries.empty())
724 typename Collection::const_iterator begin = m_entries.begin();
725 typename Collection::const_iterator end = m_entries.end();
726 typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
728 if (pos != end && pos->Contains(range))
732 else if (pos != begin)
735 if (pos->Contains(range))
745 Collection m_entries;
748 //----------------------------------------------------------------------
749 // A simple range with data class where you get to define the type of
750 // the range base "B", the type used for the range byte size "S", and
751 // the type for the associated data "T".
752 //----------------------------------------------------------------------
753 template <typename B, typename S, typename T>
754 struct RangeData : public Range<B,S>
766 RangeData (B base, S size) :
767 Range<B,S> (base, size),
772 RangeData (B base, S size, DataType d) :
773 Range<B,S> (base, size),
779 operator < (const RangeData &rhs) const
781 if (this->base == rhs.base)
783 if (this->size == rhs.size)
784 return this->data < rhs.data;
786 return this->size < rhs.size;
788 return this->base < rhs.base;
792 operator == (const RangeData &rhs) const
794 return this->GetRangeBase() == rhs.GetRangeBase() &&
795 this->GetByteSize() == rhs.GetByteSize() &&
796 this->data == rhs.data;
800 operator != (const RangeData &rhs) const
802 return this->GetRangeBase() != rhs.GetRangeBase() ||
803 this->GetByteSize() != rhs.GetByteSize() ||
804 this->data != rhs.data;
808 template <typename B, typename S, typename T, unsigned N>
812 typedef RangeData<B,S,T> Entry;
813 typedef llvm::SmallVector<Entry, N> Collection;
825 Append (const Entry &entry)
827 m_entries.push_back (entry);
833 if (m_entries.size() > 1)
834 std::stable_sort (m_entries.begin(), m_entries.end());
837 #ifdef ASSERT_RANGEMAP_ARE_SORTED
841 typename Collection::const_iterator pos, end, prev;
842 // First we determine if we can combine any of the Entry objects so we
843 // don't end up allocating and making a new collection for no reason
844 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
846 if (prev != end && *pos < *prev)
854 CombineConsecutiveEntriesWithEqualData ()
856 #ifdef ASSERT_RANGEMAP_ARE_SORTED
859 typename Collection::iterator pos;
860 typename Collection::iterator end;
861 typename Collection::iterator prev;
862 bool can_combine = false;
863 // First we determine if we can combine any of the Entry objects so we
864 // don't end up allocating and making a new collection for no reason
865 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
867 if (prev != end && prev->data == pos->data)
874 // We we can combine at least one entry, then we make a new collection
875 // and populate it accordingly, and then swap it into place.
878 Collection minimal_ranges;
879 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
881 if (prev != end && prev->data == pos->data)
882 minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd());
884 minimal_ranges.push_back (*pos);
886 // Use the swap technique in case our new vector is much smaller.
887 // We must swap when using the STL because std::vector objects never
888 // release or reduce the memory once it has been allocated/reserved.
889 m_entries.swap (minimal_ranges);
902 return m_entries.empty();
908 return m_entries.size();
912 GetEntryAtIndex (size_t i) const
914 if (i<m_entries.size())
915 return &m_entries[i];
919 // Clients must ensure that "i" is a valid index prior to calling this function
921 GetEntryRef (size_t i) const
927 BaseLessThan (const Entry& lhs, const Entry& rhs)
929 return lhs.GetRangeBase() < rhs.GetRangeBase();
933 FindEntryIndexThatContains (B addr) const
935 #ifdef ASSERT_RANGEMAP_ARE_SORTED
938 if ( !m_entries.empty() )
940 Entry entry (addr, 1);
941 typename Collection::const_iterator begin = m_entries.begin();
942 typename Collection::const_iterator end = m_entries.end();
943 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
945 if (pos != end && pos->Contains(addr))
947 return std::distance (begin, pos);
949 else if (pos != begin)
952 if (pos->Contains(addr))
953 return std::distance (begin, pos);
960 FindEntryThatContains (B addr)
962 #ifdef ASSERT_RANGEMAP_ARE_SORTED
965 if ( !m_entries.empty() )
968 entry.SetRangeBase(addr);
969 entry.SetByteSize(1);
970 typename Collection::iterator begin = m_entries.begin();
971 typename Collection::iterator end = m_entries.end();
972 typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
974 if (pos != end && pos->Contains(addr))
978 else if (pos != begin)
981 if (pos->Contains(addr))
990 FindEntryThatContains (B addr) const
992 #ifdef ASSERT_RANGEMAP_ARE_SORTED
995 if ( !m_entries.empty() )
998 entry.SetRangeBase(addr);
999 entry.SetByteSize(1);
1000 typename Collection::const_iterator begin = m_entries.begin();
1001 typename Collection::const_iterator end = m_entries.end();
1002 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1004 if (pos != end && pos->Contains(addr))
1008 else if (pos != begin)
1011 if (pos->Contains(addr))
1021 FindEntryThatContains (const Entry &range) const
1023 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1024 assert (IsSorted());
1026 if ( !m_entries.empty() )
1028 typename Collection::const_iterator begin = m_entries.begin();
1029 typename Collection::const_iterator end = m_entries.end();
1030 typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
1032 if (pos != end && pos->Contains(range))
1036 else if (pos != begin)
1039 if (pos->Contains(range))
1051 if (!m_entries.empty())
1052 return &m_entries.back();
1059 if (!m_entries.empty())
1060 return &m_entries.back();
1065 Collection m_entries;
1068 // Same as RangeDataArray, but uses std::vector as to not
1069 // require static storage of N items in the class itself
1070 template <typename B, typename S, typename T>
1071 class RangeDataVector
1074 typedef RangeData<B,S,T> Entry;
1075 typedef std::vector<Entry> Collection;
1086 Append (const Entry &entry)
1088 m_entries.push_back (entry);
1094 if (m_entries.size() > 1)
1095 std::stable_sort (m_entries.begin(), m_entries.end());
1098 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1102 typename Collection::const_iterator pos, end, prev;
1103 // First we determine if we can combine any of the Entry objects so we
1104 // don't end up allocating and making a new collection for no reason
1105 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
1107 if (prev != end && *pos < *prev)
1115 CombineConsecutiveEntriesWithEqualData ()
1117 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1118 assert (IsSorted());
1120 typename Collection::iterator pos;
1121 typename Collection::iterator end;
1122 typename Collection::iterator prev;
1123 bool can_combine = false;
1124 // First we determine if we can combine any of the Entry objects so we
1125 // don't end up allocating and making a new collection for no reason
1126 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
1128 if (prev != end && prev->data == pos->data)
1135 // We we can combine at least one entry, then we make a new collection
1136 // and populate it accordingly, and then swap it into place.
1139 Collection minimal_ranges;
1140 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
1142 if (prev != end && prev->data == pos->data)
1143 minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd());
1145 minimal_ranges.push_back (*pos);
1147 // Use the swap technique in case our new vector is much smaller.
1148 // We must swap when using the STL because std::vector objects never
1149 // release or reduce the memory once it has been allocated/reserved.
1150 m_entries.swap (minimal_ranges);
1154 // Calculate the byte size of ranges with zero byte sizes by finding
1155 // the next entry with a base address > the current base address
1157 CalculateSizesOfZeroByteSizeRanges ()
1159 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1160 assert (IsSorted());
1162 typename Collection::iterator pos;
1163 typename Collection::iterator end;
1164 typename Collection::iterator next;
1165 for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
1167 if (pos->GetByteSize() == 0)
1169 // Watch out for multiple entries with same address and make sure
1170 // we find an entry that is greater than the current base address
1171 // before we use that for the size
1172 auto curr_base = pos->GetRangeBase();
1173 for (next = pos + 1; next != end; ++next)
1175 auto next_base = next->GetRangeBase();
1176 if (next_base > curr_base)
1178 pos->SetByteSize (next_base - curr_base);
1194 Reserve (typename Collection::size_type size)
1196 m_entries.resize (size);
1202 return m_entries.empty();
1208 return m_entries.size();
1212 GetEntryAtIndex (size_t i) const
1214 if (i<m_entries.size())
1215 return &m_entries[i];
1219 // Clients must ensure that "i" is a valid index prior to calling this function
1221 GetEntryRef (size_t i) const
1223 return m_entries[i];
1227 BaseLessThan (const Entry& lhs, const Entry& rhs)
1229 return lhs.GetRangeBase() < rhs.GetRangeBase();
1233 FindEntryIndexThatContains (B addr) const
1235 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1236 assert (IsSorted());
1238 if ( !m_entries.empty() )
1240 Entry entry (addr, 1);
1241 typename Collection::const_iterator begin = m_entries.begin();
1242 typename Collection::const_iterator end = m_entries.end();
1243 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1245 while(pos != begin && pos[-1].Contains(addr))
1248 if (pos != end && pos->Contains(addr))
1249 return std::distance (begin, pos);
1255 FindEntryThatContains (B addr)
1257 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1258 assert (IsSorted());
1260 if ( !m_entries.empty() )
1263 entry.SetRangeBase(addr);
1264 entry.SetByteSize(1);
1265 typename Collection::iterator begin = m_entries.begin();
1266 typename Collection::iterator end = m_entries.end();
1267 typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1269 while(pos != begin && pos[-1].Contains(addr))
1272 if (pos != end && pos->Contains(addr))
1278 FindEntryThatContains (B addr) const
1280 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1281 assert (IsSorted());
1283 if ( !m_entries.empty() )
1286 entry.SetRangeBase(addr);
1287 entry.SetByteSize(1);
1288 typename Collection::const_iterator begin = m_entries.begin();
1289 typename Collection::const_iterator end = m_entries.end();
1290 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1292 while(pos != begin && pos[-1].Contains(addr))
1295 if (pos != end && pos->Contains(addr))
1302 FindEntryThatContains (const Entry &range) const
1304 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1305 assert (IsSorted());
1307 if ( !m_entries.empty() )
1309 typename Collection::const_iterator begin = m_entries.begin();
1310 typename Collection::const_iterator end = m_entries.end();
1311 typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
1313 while(pos != begin && pos[-1].Contains(range))
1316 if (pos != end && pos->Contains(range))
1325 if (!m_entries.empty())
1326 return &m_entries.back();
1333 if (!m_entries.empty())
1334 return &m_entries.back();
1339 Collection m_entries;
1343 //----------------------------------------------------------------------
1344 // A simple range with data class where you get to define the type of
1345 // the range base "B", the type used for the range byte size "S", and
1346 // the type for the associated data "T".
1347 //----------------------------------------------------------------------
1348 template <typename B, typename T>
1363 AddressData (B a, DataType d) :
1370 operator < (const AddressData &rhs) const
1372 if (this->addr == rhs.addr)
1373 return this->data < rhs.data;
1374 return this->addr < rhs.addr;
1378 operator == (const AddressData &rhs) const
1380 return this->addr == rhs.addr &&
1381 this->data == rhs.data;
1385 operator != (const AddressData &rhs) const
1387 return this->addr != rhs.addr ||
1388 this->data == rhs.data;
1393 template <typename B, typename T, unsigned N>
1394 class AddressDataArray
1397 typedef AddressData<B,T> Entry;
1398 typedef llvm::SmallVector<Entry, N> Collection;
1410 Append (const Entry &entry)
1412 m_entries.push_back (entry);
1418 if (m_entries.size() > 1)
1419 std::stable_sort (m_entries.begin(), m_entries.end());
1422 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1426 typename Collection::const_iterator pos, end, prev;
1427 // First we determine if we can combine any of the Entry objects so we
1428 // don't end up allocating and making a new collection for no reason
1429 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
1431 if (prev != end && *pos < *prev)
1447 return m_entries.empty();
1453 return m_entries.size();
1457 GetEntryAtIndex (size_t i) const
1459 if (i<m_entries.size())
1460 return &m_entries[i];
1464 // Clients must ensure that "i" is a valid index prior to calling this function
1466 GetEntryRef (size_t i) const
1468 return m_entries[i];
1472 BaseLessThan (const Entry& lhs, const Entry& rhs)
1474 return lhs.addr < rhs.addr;
1478 FindEntry (B addr, bool exact_match_only)
1480 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1481 assert (IsSorted());
1483 if ( !m_entries.empty() )
1487 typename Collection::iterator begin = m_entries.begin();
1488 typename Collection::iterator end = m_entries.end();
1489 typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1491 while(pos != begin && pos[-1].addr == addr)
1496 if (pos->addr == addr || !exact_match_only)
1504 FindNextEntry (const Entry *entry)
1506 if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end())
1514 if (!m_entries.empty())
1515 return &m_entries.back();
1522 if (!m_entries.empty())
1523 return &m_entries.back();
1528 Collection m_entries;
1531 } // namespace lldb_private
1533 #endif // liblldb_RangeMap_h_