ROSE 0.11.145.147
AddressMap.h
1// WARNING: Changes to this file must be contributed back to Sawyer or else they will
2// be clobbered by the next update from Sawyer. The Sawyer repository is at
3// https://gitlab.com/charger7534/sawyer.git.
4
5
6
7
8#ifndef Sawyer_AddressMap_H
9#define Sawyer_AddressMap_H
10
11#include <Sawyer/Access.h>
12#include <Sawyer/AddressSegment.h>
13#include <Sawyer/Assert.h>
14#include <Sawyer/BitVector.h>
15#include <Sawyer/Callbacks.h>
16#include <Sawyer/Interval.h>
17#include <Sawyer/IntervalMap.h>
18#include <Sawyer/IntervalSet.h>
19#include <Sawyer/Sawyer.h>
20
21#include <boost/algorithm/string/predicate.hpp>
22#include <boost/cstdint.hpp>
23#include <boost/integer_traits.hpp>
24#include <boost/lexical_cast.hpp>
25
26#if __cplusplus >= 201103L
27#include <type_traits>
28#endif
29
30namespace Sawyer {
31namespace Container {
32
33template<class AddressMap>
38
39template<class AddressMap>
44
46typedef unsigned MatchFlags;
47static const MatchFlags MATCH_BACKWARD = 0x00000001;
48static const MatchFlags MATCH_CONTIGUOUS = 0x00000002;
49static const MatchFlags MATCH_NONCONTIGUOUS = 0x00000004;
50static const MatchFlags MATCH_WHOLE = 0x00000008;
54template<class A, class T>
56public:
57 struct Args {
58 const Sawyer::Container::Interval<A> &interval;
59 const AddressSegment<A, T> &segment;
60 Args(const Sawyer::Container::Interval<A> &interval, const AddressSegment<A, T> &segment)
61 : interval(interval), segment(segment) {}
62 };
63
64 virtual ~SegmentPredicate() {}
65 virtual bool operator()(bool chain, const Args &) = 0;
66};
67
75template<typename AddressMap>
77public:
78 typedef typename AddressMap::Address Address;
79 typedef typename AddressMap::Value Value;
81private:
82 AddressMap *map_; // AddressMap<> to which these constraints are bound
83 bool never_; // never match anything (e.g., when least_ > greatest_)
84 // address constraints
85 Optional<Address> least_; // least possible valid address
86 Optional<Address> greatest_; // greatest possible valid address
87 Optional<AddressInterval> anchored_; // anchored least or greatest depending on direction
88 // constraints requiring iteration
89 size_t maxSize_; // result size is limited
90 bool singleSegment_; // do not cross a segment boundary
91 unsigned requiredAccess_; // access bits that must be set in the segment
92 unsigned prohibitedAccess_; // access bits that must be clear in the segment
93 std::string nameSubstring_; // segment name must contain substring
94 Callbacks<SegmentPredicate<Address, Value>*> segmentPredicates_; // user-supplied segment predicates
95public:
98 : map_(map), never_(false), maxSize_(size_t(-1)), singleSegment_(false), requiredAccess_(0), prohibitedAccess_(0) {}
99
100#if __cplusplus >= 201103L
101 // Implicitly construct constraints for a const AddressMap from a non-const address map. The dummy U parameter is to force
102 // type deduction to be delayed to the point where this function is instantiated.
104 operator AddressMapConstraints<const U>() const {
106 if (neverMatches())
107 cc = cc.none();
108 if (isAnchored()) {
109 if (anchored().isSingleton()) {
110 cc = cc.at(anchored().least());
111 } else {
112 cc = cc.at(anchored());
113 }
114 }
115 if (least())
116 cc = cc.atOrAfter(*least());
117 if (greatest())
118 cc = cc.atOrBefore(*greatest());
119 cc = cc.limit(limit());
120 if (isSingleSegment())
121 cc = cc.singleSegment();
122 cc = cc.require(required());
124 cc = cc.substr(substr());
125 cc = cc.segmentPredicates(segmentPredicates());
126 return cc;
127 }
128#else
131 if (neverMatches())
132 cc = cc.none();
133 if (isAnchored()) {
134 if (anchored().isSingleton()) {
135 cc = cc.at(anchored().least());
136 } else {
137 cc = cc.at(anchored());
138 }
139 }
140 if (least())
141 cc = cc.atOrAfter(*least());
142 if (greatest())
143 cc = cc.atOrBefore(*greatest());
144 cc = cc.limit(limit());
145 if (isSingleSegment())
146 cc = cc.singleSegment();
147 cc = cc.require(required());
149 cc = cc.substr(substr());
150 cc = cc.segmentPredicates(segmentPredicates());
151 return cc;
152 }
153#endif
154
156 void print(std::ostream &out) const {
157 out <<"{map=" <<map_;
158 if (never_)
159 out <<", never";
160 if (least_)
161 out <<", least=" <<*least_;
162 if (greatest_)
163 out <<", greatest=" <<*greatest_;
164 if (anchored_) {
165 out <<", anchored=";
166 AddressInterval a = *anchored_;
167 if (a.isEmpty()) {
168 out <<"empty";
169 } else if (a.least()==a.greatest()) {
170 out <<a.least();
171 } else {
172 out <<"{" <<a.least() <<".." <<a.greatest() <<"}";
173 }
174 }
175 if (maxSize_ != size_t(-1))
176 out <<", limit=" <<maxSize_;
177 if (singleSegment_)
178 out <<", single-segment";
179 if (requiredAccess_!=0) {
180 out <<", required="
181 <<((requiredAccess_ & Access::READABLE) ? "r" : "")
182 <<((requiredAccess_ & Access::WRITABLE) ? "w" : "")
183 <<((requiredAccess_ & Access::EXECUTABLE) ? "x" : "")
184 <<((requiredAccess_ & Access::IMMUTABLE) ? "i" : "");
185 unsigned other = requiredAccess_ & ~(Access::READABLE|Access::WRITABLE|Access::EXECUTABLE|Access::IMMUTABLE);
186 if (other)
187 out <<"+0x" <<BitVector(8*sizeof requiredAccess_).fromInteger(other).toHex();
188 }
189 if (prohibitedAccess_!=0) {
190 out <<", required="
191 <<((prohibitedAccess_ & Access::READABLE) ? "r" : "")
192 <<((prohibitedAccess_ & Access::WRITABLE) ? "w" : "")
193 <<((prohibitedAccess_ & Access::EXECUTABLE) ? "x" : "")
194 <<((prohibitedAccess_ & Access::IMMUTABLE) ? "i" : "");
195 unsigned other = prohibitedAccess_ & ~(Access::READABLE|Access::WRITABLE|Access::EXECUTABLE|Access::IMMUTABLE);
196 if (other)
197 out <<"+0x" <<BitVector(8*sizeof prohibitedAccess_).fromInteger(other).toHex();
198 }
199 if (!nameSubstring_.empty()) {
200 out <<", substr=\"";
201 for (char ch: nameSubstring_) {
202 switch (ch) {
203 case '\a': out <<"\\a"; break;
204 case '\b': out <<"\\b"; break;
205 case '\t': out <<"\\t"; break;
206 case '\n': out <<"\\n"; break;
207 case '\v': out <<"\\v"; break;
208 case '\f': out <<"\\f"; break;
209 case '\r': out <<"\\r"; break;
210 case '\"': out <<"\\\""; break;
211 case '\\': out <<"\\\\"; break;
212 default:
213 if (isprint(ch)) {
214 out <<ch;
215 } else {
216 char buf[8];
217 snprintf(buf, sizeof(buf), "\\%03o", (unsigned)(unsigned char)ch);
218 out <<buf;
219 }
220 break;
221 }
222 }
223 }
224 if (!segmentPredicates_.isEmpty())
225 out <<", user-def";
226 out <<"}";
227 }
228
230 friend std::ostream& operator<<(std::ostream &out, const AddressMapConstraints &x) {
231 x.print(out);
232 return out;
233 }
234
236 // Constraint modifiers
237public:
239 AddressMapConstraints require(unsigned bits) const {
241 retval.requiredAccess_ |= bits;
242 return retval;
243 }
244
246 AddressMapConstraints prohibit(unsigned bits) const {
248 retval.prohibitedAccess_ |= bits;
249 return retval;
250 }
251
253 AddressMapConstraints access(unsigned bits) const {
254 return require(bits).prohibit(~bits);
255 }
256
258 AddressMapConstraints substr(const std::string &s) const {
259 ASSERT_require(nameSubstring_.empty() || nameSubstring_==s);// substring conjunction not supported
261 retval.nameSubstring_ = s;
262 return retval;
263 }
264
267 return *this;
268 }
269
273 retval.never_ = true;
274 return retval;
275 }
276
278 AddressMapConstraints at(Address x) const {
280 retval.anchored_ = anchored_ ? *anchored_ & AddressInterval(x) : AddressInterval(x);
281 return retval.anchored_->isEmpty() ? retval.none() : retval;
282 }
283
287 retval.anchored_ = anchored_ ? *anchored_ & x : x;
288 return retval.anchored_->isEmpty() ? retval.none() : retval.atOrAfter(x.least()).atOrBefore(x.greatest());
289 }
290
292 AddressMapConstraints limit(size_t x) const {
294 retval.maxSize_ = std::min(maxSize_, x);
295 return 0 == retval.maxSize_ ? retval.none() : retval;
296 }
297
301 if (least_) {
302 retval.least_ = std::max(*least_, least);
303 } else {
304 retval.least_ = least;
305 }
306 if (greatest_ && *greatest_ < *retval.least_)
307 retval.none();
308 return retval;
309 }
310
314 if (greatest_) {
315 retval.greatest_ = std::min(*greatest_, greatest);
316 } else {
317 retval.greatest_ = greatest;
318 }
319 if (least_ && *least_ > *retval.greatest_)
320 retval.none();
321 return retval;
322 }
323
328
330 AddressMapConstraints within(Address lo, Address hi) const {
331 return lo<=hi ? within(Sawyer::Container::Interval<Address>::hull(lo, hi)) : none();
332 }
333
335 AddressMapConstraints baseSize(Address base, Address size) const {
336 return size>0 ? atOrAfter(base).atOrBefore(base+size-1) : none();
337 }
338
340 AddressMapConstraints after(Address x) const {
341 return x==boost::integer_traits<Address>::const_max ? none() : atOrAfter(x+1);
342 }
343
345 AddressMapConstraints before(Address x) const {
346 return x==boost::integer_traits<Address>::const_min ? none() : atOrBefore(x-1);
347 }
348
352 retval.singleSegment_ = true;
353 return retval;
354 }
355
358 if (!p)
359 return none();
361 retval.segmentPredicates_.append(p);
362 return retval;
363 }
364
367 retval.segmentPredicates_.append(predicates);
368 return retval;
369 }
370
372 // Constraint queries
373public:
375 unsigned required() const {
376 return requiredAccess_;
377 }
378
380 unsigned prohibited() const {
381 return prohibitedAccess_;
382 }
383
385 const std::string& substr() const {
386 return nameSubstring_;
387 }
388
392 bool neverMatches() const {
393 return never_;
394 }
395
397 bool isAnchored() const {
398 return anchored_;
399 }
400
406 ASSERT_require(isAnchored());
407 return *anchored_;
408 }
409
411 size_t limit() const {
412 return maxSize_;
413 }
414
417 const Optional<Address>& least() const {
418 return least_;
419 }
420
424 return greatest_;
425 }
426
428 bool isSingleSegment() const {
429 return singleSegment_;
430 }
431
434 return segmentPredicates_;
435 }
436
438 AddressMap* map() const {
439 return map_;
440 }
441
445 return (!never_ &&
446 (requiredAccess_ || prohibitedAccess_ || !nameSubstring_.empty() || maxSize_!=size_t(-1) ||
447 singleSegment_ || !segmentPredicates_.isEmpty()));
448 }
449
453 AddressMapConstraints c(map_);
454 c.least_ = least_;
455 c.greatest_ = greatest_;
456 c.anchored_ = anchored_;
457 c.maxSize_ = maxSize_;
458 return c;
459 }
460
462 // Methods that directly call the AddressMap
463public:
464 boost::iterator_range<typename AddressMapTraits<AddressMap>::NodeIterator>
465 nodes(MatchFlags flags=0) const {
466 return map_->nodes(*this, flags);
467 }
468
469 boost::iterator_range<typename AddressMapTraits<AddressMap>::SegmentIterator>
470 segments(MatchFlags flags=0) const {
471 return map_->segments(*this, flags);
472 }
473
475 next(MatchFlags flags=0) const {
476 return map_->next(*this, flags);
477 }
478
480 available(MatchFlags flags=0) const {
481 return map_->available(*this, flags);
482 }
483
484 bool
485 exists(MatchFlags flags=0) const {
486 return map_->exists(*this, flags);
487 }
488
489 typename AddressMapTraits<AddressMap>::NodeIterator
490 findNode(MatchFlags flags=0) const {
491 return map_->findNode(*this, flags);
492 }
493
494 template<typename Functor>
495 void
496 traverse(Functor &functor, MatchFlags flags=0) const {
497 return map_->traverse(functor, *this, flags);
498 }
499 void
500 traverse(typename AddressMap::Visitor &visitor, MatchFlags flags=0) const {
501 return map_->template traverse<typename AddressMap::Visitor>(visitor, *this, flags);
502 }
503
505 read(typename AddressMap::Value *buf /*out*/, MatchFlags flags=0) const {
506 return map_->read(buf, *this, flags);
507 }
508
510 read(std::vector<typename AddressMap::Value> &buf /*out*/,
511 MatchFlags flags=0) const {
512 return map_->read(buf, *this, flags);
513 }
514
516 write(const typename AddressMap::Value *buf, MatchFlags flags=0) const {
517 return map_->write(buf, *this, flags);
518 }
519
521 write(const std::vector<typename AddressMap::Value> &buf, MatchFlags flags=0) {
522 return map_->write(buf, *this, flags);
523 }
524
525 void
526 prune(MatchFlags flags=0) const {
527 return map_->prune(*this, flags);
528 }
529
530 void
531 keep(MatchFlags flags=0) const {
532 return map_->keep(*this, flags);
533 }
534
535 void
536 changeAccess(unsigned requiredAccess, unsigned prohibitedAccess, MatchFlags flags=0) const {
537 return map_->changeAccess(requiredAccess, prohibitedAccess, *this, flags);
538 }
539};
540
542// Implementation details
544namespace AddressMapImpl {
545
546// Used internally to split and merge segments
547template<class A, class T>
549public:
550 typedef A Address;
551 typedef T Value;
553
554#ifdef SAWYER_HAVE_CEREAL
555private:
556 friend class cereal::access;
557
558 template<class Archive>
559 void CEREAL_SERIALIZE_FUNCTION_NAME(Archive&) {
560 // no data to serialize here
561 }
562#endif
563
564#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
565private:
566 friend class boost::serialization::access;
567
568 template<class S>
569 void serialize(S&, const unsigned /*version*/) {
570 // no data to serialize here
571 }
572#endif
573
574public:
575 bool merge(const Sawyer::Container::Interval<Address> &leftInterval, Segment &leftSegment,
576 const Sawyer::Container::Interval<Address> &rightInterval, Segment &rightSegment) {
577 ASSERT_forbid(leftInterval.isEmpty());
578 ASSERT_always_forbid(rightInterval.isEmpty()); // so rightInterval is always used
579 ASSERT_require(leftInterval.greatest() + 1 == rightInterval.least());
580 return (leftSegment.accessibility() == rightSegment.accessibility() &&
581 leftSegment.name() == rightSegment.name() &&
582 leftSegment.buffer() == rightSegment.buffer() &&
583 leftSegment.offset() + leftInterval.size() == rightSegment.offset());
584 }
585
586 Segment split(const Sawyer::Container::Interval<Address> &interval, Segment &segment, Address splitPoint) {
587 ASSERT_forbid(interval.isEmpty());
588 ASSERT_require(interval.contains(splitPoint));
589 Segment right = segment;
590 right.offset(segment.offset() + splitPoint - interval.least());
591 return right;
592 }
593
594 void truncate(const Sawyer::Container::Interval<Address> &interval, Segment &/*segment*/, Address splitPoint) {
595 ASSERT_always_forbid(interval.isEmpty()); // so interval is always used
596 ASSERT_always_require(interval.contains(splitPoint)); // ditto for splitPoint
597 }
598};
599
600// The results for matching constraints
601template<class AddressMap>
603 typedef typename AddressMap::Address Address;
606 boost::iterator_range<NodeIterator> nodes_;
607};
608
609// Finds the minimum possible address and node iterator for the specified constraints in this map and returns that
610// iterator. Returns the end iterator if the constraints match no address. If a non-end iterator is returned then minAddr
611// is adjusted to be the minimum address that satisfies the constraint (it will be an address within the returned node, but
612// not necessarily the least address for the node). If useAnchor is set and the constraints specify an anchor, then the
613// anchor address must be present in the map and satisfy any address constraints that might also be present.
614template<class AddressMap>
616constraintLowerBound(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, bool useAnchor,
617 typename AddressMap::Address &minAddr) {
618 typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
619 if (amap.isEmpty() || c.neverMatches())
620 return amap.nodes().end();
621
622 if (useAnchor && c.isAnchored()) { // forward matching if useAnchor is set
623 if ((c.least() && *c.least() > c.anchored().least()) || (c.greatest() && *c.greatest() < c.anchored().greatest()))
624 return amap.nodes().end(); // anchor is outside of allowed interval
625 Iterator lb = amap.lowerBound(c.anchored().least());
626 if (lb==amap.nodes().end() || c.anchored().least() < lb->key().least())
627 return amap.nodes().end(); // anchor is not present in this map
628 minAddr = c.anchored().least();
629 return lb;
630 }
631
632 if (c.least()) {
633 Iterator lb = amap.lowerBound(*c.least());
634 if (lb==amap.nodes().end())
635 return lb; // least is above all segments
636 minAddr = std::max(*c.least(), lb->key().least());
637 return lb;
638 }
639
640 Iterator lb = amap.nodes().begin();
641 if (lb!=amap.nodes().end())
642 minAddr = lb->key().least();
643 return lb;
644}
645
646// Finds the maximum possible address and node for the specified constraints in this map, and returns an iterator to the
647// following node. Returns the begin iterator if the constraints match no address. If a non-begin iterator is returned
648// then maxAddr is adjusted to be the maximum address that satisfies the constraint (it will be an address that belongs to
649// the node immediately prior to the one pointed to by the returned iterator, but not necessarily the greatest address for
650// that node). If useAnchor is set and the constraints specify an anchor, then the anchor address must be present in the
651// map and satisfy any address constraints that might also be present.
652template<class AddressMap>
653typename AddressMapTraits<AddressMap>::NodeIterator
654constraintUpperBound(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, bool useAnchor,
655 typename AddressMap::Address &maxAddr) {
656 typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
657 if (amap.isEmpty() || c.neverMatches())
658 return amap.nodes().begin();
659
660 if (useAnchor && c.isAnchored()) { // backward matching if useAnchor is set
661 if ((c.least() && *c.least() > c.anchored().least()) || (c.greatest() && *c.greatest() < c.anchored().greatest()))
662 return amap.nodes().begin(); // anchor is outside allowed interval
663 Iterator ub = amap.findPrior(c.anchored().greatest());
664 if (ub==amap.nodes().end() || c.anchored().greatest() > ub->key().greatest())
665 return amap.nodes().begin(); // anchor is not present in this map
666 maxAddr = c.anchored().greatest();
667 return ++ub; // return node after the one containing the anchor
668 }
669
670 if (c.greatest()) {
671 Iterator ub = amap.findPrior(*c.greatest());
672 if (ub==amap.nodes().end())
673 return amap.nodes().begin(); // greatest is below all segments
674 maxAddr = std::min(ub->key().greatest(), *c.greatest());
675 return ++ub; // return node after the one containing the maximum
676 }
677
678 maxAddr = amap.hull().greatest();
679 return amap.nodes().end();
680}
681
682// Returns true if the segment satisfies the non-address constraints in c.
683template<class AddressMap>
684bool
685isSatisfied(const typename AddressMap::Node &node, const AddressMapConstraints<AddressMap> &c) {
686 typedef typename AddressMap::Address Address;
687 typedef typename AddressMap::Value Value;
688 typedef typename AddressMap::Segment Segment;
689 const Segment &segment = node.value();
690 if (!segment.isAccessible(c.required(), c.prohibited()))
691 return false; // wrong segment permissions
692 if (!boost::contains(segment.name(), c.substr()))
693 return false; // wrong segment name
694 if (!c.segmentPredicates().apply(true, typename SegmentPredicate<Address, Value>::Args(node.key(), node.value())))
695 return false; // user-supplied predicates failed
696 return true;
697}
698
699// Matches constraints against contiguous addresses in a forward direction.
700template<class AddressMap>
701MatchedConstraints<AddressMap>
702matchForward(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, MatchFlags flags) {
703 typedef typename AddressMap::Address Address;
704 typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
705 MatchedConstraints<AddressMap> retval;
706 retval.nodes_ = boost::iterator_range<Iterator>(amap.nodes().end(), amap.nodes().end());
707 if (c.neverMatches() || amap.isEmpty())
708 return retval;
709
710 // Find a lower bound for the minimum address
711 Address minAddr = 0;
712 Iterator begin = constraintLowerBound(amap, c, true, minAddr /*out*/);
713 if (begin == amap.nodes().end())
714 return retval;
715
716 // Find an upper bound for the maximum address.
717 Address maxAddr = 0;
718 Iterator end = constraintUpperBound(amap, c, false, maxAddr /*out*/);
719 if (end==amap.nodes().begin())
720 return retval;
721
722 // Advance the lower-bound until it satisfies the other (non-address) constraints
723 while (begin!=end && !isSatisfied(*begin, c)) {
724 if (c.isAnchored())
725 return retval; // match is anchored to minAddr
726 ++begin;
727 }
728 if (begin==end)
729 return retval;
730 minAddr = std::max(minAddr, begin->key().least());
731
732 // Iterate forward until the constraints are no longer satisfied
733 if ((flags & MATCH_CONTIGUOUS)!=0 || c.hasNonAddressConstraints()) {
734 Address addr = minAddr;
735 Iterator iter = begin;
736 size_t nElmtsFound = 0;
737 for (/*void*/; iter!=end; ++iter) {
738 if (iter!=begin) { // already tested the first node above
739 if (c.isSingleSegment())
740 break; // we crossed a segment boundary
741 if ((flags & MATCH_CONTIGUOUS)!=0 && addr+1 != iter->key().least())
742 break; // gap between segments
743 if (!isSatisfied(*iter, c)) {
744 if ((flags & MATCH_WHOLE)!=0)
745 return retval; // match is anchored to maxAddr
746 break; // segment does not satisfy constraints
747 }
748 }
749 size_t nElmtsHere = iter->key().greatest() + 1 - std::max(minAddr, iter->key().least());
750 if (nElmtsFound + nElmtsHere >= c.limit()) {
751 size_t nNeed = c.limit() - nElmtsFound;
752 addr = std::max(minAddr, iter->key().least()) + nNeed - 1;
753 ++iter;
754 break; // too many values
755 }
756 addr = iter->key().greatest();
757 nElmtsFound += nElmtsHere;
758 }
759 end = iter;
760 maxAddr = std::min(maxAddr, addr);
761 }
762
763 // Build the result
764 retval.interval_ = Sawyer::Container::Interval<Address>::hull(minAddr, maxAddr);
765 retval.nodes_ = boost::iterator_range<Iterator>(begin, end);
766 return retval;
767}
768
769// Matches constraints against contiguous addresses in a backward direction.
770template<class AddressMap>
771MatchedConstraints<AddressMap>
772matchBackward(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, MatchFlags flags) {
773 typedef typename AddressMap::Address Address;
774 typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
775 MatchedConstraints<AddressMap> retval;
776 retval.nodes_ = boost::iterator_range<Iterator>(amap.nodes().end(), amap.nodes().end());
777 if (c.neverMatches() || amap.isEmpty())
778 return retval;
779
780 // Find a lower bound for the minimum address
781 Address minAddr = 0;
782 Iterator begin = constraintLowerBound(amap, c, false, minAddr /*out*/);
783 if (begin == amap.nodes().end())
784 return retval;
785
786 // Find an upper bound for the maximum address.
787 Address maxAddr = 0;
788 Iterator end = constraintUpperBound(amap, c, true, maxAddr /*out*/);
789 if (end==amap.nodes().begin())
790 return retval;
791
792 // Decrement the upper bound until constraints are met. End always points to one-past the last matching node.
793 while (end!=begin) {
794 Iterator prev = end; --prev;
795 if (isSatisfied(*prev, c)) {
796 maxAddr = std::min(maxAddr, prev->key().greatest());
797 break;
798 }
799 if (c.isAnchored())
800 return retval; // match is anchored to maxAddr
801 end = prev;
802 }
803 if (end==begin)
804 return retval;
805
806 // Iterate backward until the constraints are no longer satisfied. Within the loop, iter always points to on-past the
807 // node in question. When the loop exits, iter points to the first node satisfying constraints.
808 if ((flags & MATCH_CONTIGUOUS)!=0 || c.hasNonAddressConstraints()) {
809 Address addr = maxAddr;
810 Iterator iter = end;
811 size_t nElmtsFound = 0;
812 for (/*void*/; iter!=begin; --iter) {
813 Iterator prev = iter; --prev; // prev points to the node in question
814 if (iter!=end) { // already tested last node above
815 if (c.isSingleSegment())
816 break; // we crossed a segment boundary
817 if ((flags & MATCH_CONTIGUOUS)!=0 && prev->key().greatest()+1 != addr)
818 break; // gap between segments
819 if (!isSatisfied(*prev, c)) {
820 if ((flags & MATCH_WHOLE)!=0)
821 return retval; // match is anchored to minAddr
822 break; // segment does not satisfy constraints
823 }
824 }
825 size_t nElmtsHere = std::min(maxAddr, prev->key().greatest()) - prev->key().least() + 1;
826 if (nElmtsFound + nElmtsHere >= c.limit()) {
827 size_t nNeed = c.limit() - nElmtsFound;
828 addr = std::min(maxAddr, prev->key().greatest()) - nNeed + 1;
829 iter = prev;
830 break;
831 }
832 addr = prev->key().least();
833 nElmtsFound += nElmtsHere;
834 }
835 begin = iter; // iter points to first matching node
836 minAddr = std::max(minAddr, addr);
837 }
838
839 // Build the result
840 retval.interval_ = Sawyer::Container::Interval<Address>::hull(minAddr, maxAddr);
841 retval.nodes_ = boost::iterator_range<Iterator>(begin, end);
842 return retval;
843}
844
845// Match constraints forward or backward
846template<class AddressMap>
847MatchedConstraints<AddressMap>
848matchConstraints(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, MatchFlags flags) {
849 if ((flags & MATCH_BACKWARD) != 0)
850 return matchBackward(amap, c, flags);
851 return matchForward(amap, c, flags);
852}
853
854} // namespace
855
856
1011template<class A, class T = boost::uint8_t>
1012class AddressMap: public IntervalMap<Interval<A>, AddressSegment<A, T>, AddressMapImpl::SegmentMergePolicy<A, T> > {
1013 // "Interval" is qualified to work around bug in Microsoft compilers. See doxygen note above.
1015
1016public:
1017 typedef A Address;
1018 typedef T Value;
1021 typedef typename Super::Node Node;
1028private:
1029 friend class boost::serialization::access;
1030
1031 template<class S>
1032 void serialize(S &s, const unsigned /*version*/) {
1033 s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Super);
1034 }
1035
1036public:
1039
1055 AddressMap(const AddressMap &other, bool copyOnWrite=false): Super(other) {
1056 if (copyOnWrite) {
1057 for (Segment &segment: this->values()) {
1058 if (const typename Buffer::Ptr &buffer = segment.buffer())
1059 buffer->copyOnWrite(true);
1060 }
1061 }
1062 }
1063
1111 }
1114 }
1322 void checkConsistency() const {
1323 for (const Node &node: nodes()) {
1324 const Sawyer::Container::Interval<Address> &interval = node.key();
1325 const Segment &segment = node.value();
1326 if (segment.buffer()==NULL) {
1327 throw std::runtime_error("AddressMap null buffer for interval [" +
1328 boost::lexical_cast<std::string>(interval.least()) +
1329 "," + boost::lexical_cast<std::string>(interval.greatest()) + "]");
1330 }
1331 Address bufAvail = segment.buffer()->available(segment.offset());
1332 if (bufAvail < interval.size()) {
1333 throw std::runtime_error("AddressMap segment at [" + boost::lexical_cast<std::string>(interval.least()) +
1334 "," + boost::lexical_cast<std::string>(interval.greatest()) + "] points to only " +
1335 boost::lexical_cast<std::string>(bufAvail) + (1==bufAvail?" value":" values") +
1336 " but the interval size is " + boost::lexical_cast<std::string>(interval.size()));
1337 }
1338 }
1339 }
1340
1347 Address nSegments() const { return this->nIntervals(); }
1348
1354 boost::iterator_range<SegmentIterator> segments() { return this->values(); }
1355 boost::iterator_range<ConstSegmentIterator> segments() const { return this->values(); }
1356
1377 boost::iterator_range<ConstSegmentIterator>
1379 using namespace AddressMapImpl;
1380 if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1381 flags |= MATCH_CONTIGUOUS;
1382 MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
1383 return boost::iterator_range<ConstSegmentIterator>(m.nodes_.begin(), m.nodes_.end());
1384 }
1385
1386 boost::iterator_range<SegmentIterator>
1388 using namespace AddressMapImpl;
1389 if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1390 flags |= MATCH_CONTIGUOUS;
1391 MatchedConstraints<AddressMap> m = matchConstraints(*this, c, flags);
1392 return boost::iterator_range<SegmentIterator>(m.nodes_);
1393 }
1402 boost::iterator_range<NodeIterator> nodes() { return Super::nodes(); }
1403 boost::iterator_range<ConstNodeIterator> nodes() const { return Super::nodes(); }
1425 boost::iterator_range<ConstNodeIterator>
1427 using namespace AddressMapImpl;
1428 if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1429 flags |= MATCH_CONTIGUOUS;
1430 MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
1431 return m.nodes_;
1432 }
1433
1434 boost::iterator_range<NodeIterator>
1436 using namespace AddressMapImpl;
1437 if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1438 flags |= MATCH_CONTIGUOUS;
1439 MatchedConstraints<AddressMap> m = matchConstraints(*this, c, flags);
1440 return m.nodes_;
1441 }
1483 using namespace AddressMapImpl;
1484 if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1485 flags |= MATCH_CONTIGUOUS;
1486 MatchedConstraints<const AddressMap> m = matchConstraints(*this, c.limit(1), flags);
1487 return m.interval_.isEmpty() ? Optional<Address>() : Optional<Address>(m.interval_.least());
1488 }
1489
1497 using namespace AddressMapImpl;
1498 if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1499 flags |= MATCH_CONTIGUOUS;
1500 return matchConstraints(*this, c, flags).interval_;
1501 }
1502
1513 return next(c, flags);
1514 }
1515
1522 return nodes(c.limit(1), flags).begin();
1523 }
1525 return nodes(c.limit(1), flags).begin();
1526 }
1537 unmapped(Address boundary, MatchFlags flags=0) const {
1538 return (flags & MATCH_BACKWARD) != 0 ? this->lastUnmapped(boundary) : this->firstUnmapped(boundary);
1539 }
1540
1550 findFreeSpace(size_t nValues, size_t alignment=1,
1552 MatchFlags flags=0) const {
1554 ASSERT_forbid2(nValues == 0, "cannot determine if this is an overflow or intentional");
1555
1556 if (restriction.isEmpty())
1557 return Nothing();
1558
1559 if (0 == (flags & MATCH_BACKWARD)) {
1560 Address minAddr = restriction.least();
1561 while (minAddr <= restriction.greatest()) {
1562 Sawyer::Container::Interval<Address> interval = unmapped(minAddr, 0 /*forward*/);
1563 if (interval.isEmpty())
1564 return Nothing();
1565 minAddr = alignUp(interval.least(), alignment);
1566 Address maxAddr = minAddr + (nValues-1);
1567 if ((nValues <= interval.size() || 0==interval.size()/*overflow*/) &&
1568 minAddr >= interval.least()/*overflow*/ && maxAddr >= interval.least()/*overflow*/ &&
1569 maxAddr <= interval.greatest() &&
1570 maxAddr <= restriction.greatest()) {
1571 return minAddr;
1572 }
1573 if (interval.greatest() == whole.greatest())
1574 return Nothing(); // to avoid overflow in next statement
1575 minAddr = interval.greatest() + 1;
1576 }
1577 return Nothing();
1578 }
1579
1580 ASSERT_require((flags & MATCH_BACKWARD) != 0);
1581 Address maxAddr = restriction.greatest();
1582 while (maxAddr >= restriction.least()) {
1583 Sawyer::Container::Interval<Address> interval = unmapped(maxAddr, MATCH_BACKWARD);
1584 if (interval.isEmpty())
1585 return Nothing();
1586 Address minAddr = alignDown(interval.greatest() - (nValues-1), alignment);
1587 maxAddr = minAddr + (nValues-1);
1588 if ((nValues <= interval.size() || 0==interval.size()/*overflow*/) &&
1589 minAddr >= interval.least()/*overflow*/ && maxAddr >= interval.least()/*overflow*/ &&
1590 maxAddr <= interval.greatest() &&
1591 minAddr >= restriction.least()) {
1592 return minAddr;
1593 }
1594 if (interval.least() == whole.least())
1595 return Nothing(); // to avoid overflow in next statement
1596 maxAddr = interval.least() - 1;
1597 }
1598 return Nothing();
1599 }
1600
1602 class Visitor {
1603 public:
1604 virtual ~Visitor() {}
1605 virtual bool operator()(const AddressMap&, const Sawyer::Container::Interval<Address>&) = 0;
1606 };
1607
1631 template<typename Functor>
1632 void traverse(Functor &functor, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1633 using namespace AddressMapImpl;
1634 MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
1635 for (const Node &node: m.nodes_) {
1636 Sawyer::Container::Interval<Address> part = m.interval_ & node.key();
1637 if (!functor(*this, part))
1638 return;
1639 }
1640 return;
1641 }
1642 template<typename Functor>
1643 void traverse(Functor &functor, const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1644 using namespace AddressMapImpl;
1645 MatchedConstraints<AddressMap> m = matchConstraints(*this, c, flags);
1646 for (const Node &node: m.nodes_) {
1647 Sawyer::Container::Interval<Address> part = m.interval_ & node.key();
1648 if (!functor(*this, part))
1649 return;
1650 }
1651 return;
1652 }
1653 void traverse(Visitor &visitor, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1654 traverse<Visitor>(visitor, c, flags);
1655 }
1657 traverse<Visitor>(visitor, c, flags);
1658 }
1700 read(Value *buf /*out*/, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1701 using namespace AddressMapImpl;
1702 ASSERT_require2(0 == (flags & MATCH_NONCONTIGUOUS), "only contiguous addresses can be read");
1703 if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1704 flags |= MATCH_CONTIGUOUS;
1705 MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
1706 if (buf) {
1707 for (const Node &node: m.nodes_) {
1708 Sawyer::Container::Interval<Address> part = m.interval_ & node.key(); // part of segment to read
1709 ASSERT_forbid(part.isEmpty());
1710 Address bufferOffset = part.least() - node.key().least() + node.value().offset();
1711 Address nValues = node.value().buffer()->read(buf, bufferOffset, part.size());
1712 if (nValues != part.size()) {
1714 ASSERT_not_reachable("something is wrong with the memory map");
1715 }
1716 buf += nValues;
1717 }
1718 }
1719 return m.interval_;
1720 }
1721
1723 read(std::vector<Value> &buf /*out*/, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1724 return buf.empty() ? Sawyer::Container::Interval<Address>() : read(&buf[0], c.limit(buf.size()), flags);
1725 }
1762 using namespace AddressMapImpl;
1763 ASSERT_require2(0 == (flags & MATCH_NONCONTIGUOUS), "only contiguous addresses can be written");
1764 if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1765 flags |= MATCH_CONTIGUOUS;
1766 MatchedConstraints<AddressMap> m = matchConstraints(*this, c.prohibit(Access::IMMUTABLE), flags);
1767 if (buf) {
1768 size_t totalWritten = 0;
1769 for (Node &node: m.nodes_) {
1770 Segment &segment = node.value();
1771 Sawyer::Container::Interval<Address> part = m.interval_ & node.key(); // part of segment to write
1772 ASSERT_forbid(part.isEmpty());
1773 typename Buffer::Ptr buffer = segment.buffer();
1774 ASSERT_not_null(buffer);
1775
1776 if (buffer->copyOnWrite()) {
1777 typename Buffer::Ptr newBuffer = buffer->copy(); // copyOnWrite is cleared in newBuffer
1778 ASSERT_not_null(newBuffer);
1779 for (NodeIterator iter=this->lowerBound(node.key().least()); iter!=nodes().end(); ++iter) {
1780 if (iter->value().buffer() == buffer)
1781 iter->value().buffer(newBuffer);
1782 }
1783 buffer = newBuffer;
1784 }
1785
1786 Address bufferOffset = part.least() - node.key().least() + segment.offset();
1787 Address nValues = buffer->write(buf, bufferOffset, part.size());
1788 if (0 == nValues) {
1789 // The underlying buffer is not writable (e.g., it's mmap'd read-only)
1790 return Sawyer::Container::Interval<Address>::baseSize(m.interval_.least(), totalWritten);
1791 } else if (nValues != part.size()) {
1793 ASSERT_not_reachable("something is wrong with the memory map");
1794 } else {
1795 buf += nValues;
1796 totalWritten += nValues;
1797 }
1798 }
1799 }
1800 return m.interval_;
1801 }
1802
1804 write(const std::vector<Value> &buf, const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1805 return buf.empty() ? Sawyer::Container::Interval<Address>() : write(&buf[0], c.limit(buf.size()), flags);
1806 }
1822 using namespace AddressMapImpl;
1824 if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1825 flags |= MATCH_NONCONTIGUOUS;
1826 MatchedConstraints<AddressMap> m = matchConstraints(*this, c.addressConstraints(), flags);
1827 for (const Node &node: m.nodes_) {
1828 if (isSatisfied(node, c))
1829 toErase.insert(node.key() & m.interval_);
1830 }
1831 for (const Sawyer::Container::Interval<Address> &interval: toErase.intervals())
1832 this->erase(interval);
1833 }
1834
1849 using namespace AddressMapImpl;
1850 if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1851 flags |= MATCH_NONCONTIGUOUS;
1853 MatchedConstraints<AddressMap> m = matchConstraints(*this, c.addressConstraints(), flags);
1854 for (const Node &node: m.nodes_) {
1855 if (isSatisfied(node, c))
1856 toKeep.insert(node.key() & m.interval_);
1857 }
1858 toKeep.invert();
1859 for (const Sawyer::Container::Interval<Address> &interval: toKeep.intervals())
1860 this->erase(interval);
1861 }
1862
1882 void changeAccess(unsigned requiredAccess, unsigned prohibitedAccess, const AddressMapConstraints<AddressMap> &c,
1883 MatchFlags flags=0) {
1884 using namespace AddressMapImpl;
1885 if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1886 flags |= MATCH_NONCONTIGUOUS;
1887 typedef std::pair<Sawyer::Container::Interval<Address>, Segment> ISPair;
1888 std::vector<ISPair> newSegments;
1889 MatchedConstraints<AddressMap> m = matchConstraints(*this, c.addressConstraints(), flags);
1890 for (Node &node: m.nodes_) {
1891 Segment &segment = node.value();
1892 if (isSatisfied(node, c)) {
1893 unsigned newAccess = (segment.accessibility() | requiredAccess) & ~prohibitedAccess;
1894 Sawyer::Container::Interval<Address> toChange = node.key() & m.interval_;
1895 if (toChange == node.key()) { // all addresses in segment are selected; change segment in place
1896 segment.accessibility(newAccess);
1897 } else { // insert a new segment, replacing part of the existing one
1898 Segment newSegment(segment);
1899 newSegment.accessibility(newAccess);
1900 newSegment.offset(segment.offset() + toChange.least() - node.key().least());
1901 newSegments.push_back(ISPair(toChange, newSegment));
1902 }
1903 }
1904 }
1905 for (const ISPair &pair: newSegments)
1906 this->insert(pair.first, pair.second);
1907 }
1908
1909private:
1910 // Increment x if necessary so it is aligned.
1911 static Address alignUp(Address x, Address alignment) {
1912 return alignment>0 && x%alignment!=0 ? ((x+alignment-1)/alignment)*alignment : x;
1913 }
1914
1915 static Address alignDown(Address x, Address alignment) {
1916 return alignment>0 && x%alignment!=0 ? (x/alignment)*alignment : x;
1917 }
1918};
1919
1920} // namespace
1921} // namespace
1922
1923#endif
Constraints are used to select addresses from a memory map.
Definition AddressMap.h:76
bool hasNonAddressConstraints() const
Determines whether non-address constraints are present.
Definition AddressMap.h:444
const Optional< Address > & least() const
Least possible address.
Definition AddressMap.h:417
AddressMapConstraints within(const Sawyer::Container::Interval< Address > &x) const
Limit addresses.
Definition AddressMap.h:325
AddressInterval anchored() const
Returns the anchor points.
Definition AddressMap.h:405
AddressMapConstraints limit(size_t x) const
Limit matching length.
Definition AddressMap.h:292
bool isSingleSegment() const
Returns true if the single-segment constraint is set.
Definition AddressMap.h:428
unsigned required() const
Accessibility bits that are required to be set.
Definition AddressMap.h:375
const Optional< Address > & greatest() const
Greatest possible address.
Definition AddressMap.h:423
size_t limit() const
Size limit.
Definition AddressMap.h:411
const std::string & substr() const
Section name substring.
Definition AddressMap.h:385
AddressMapConstraints within(Address lo, Address hi) const
Limit addresses.
Definition AddressMap.h:330
AddressMapConstraints addressConstraints() const
Construct new constraints from existing address constraints.
Definition AddressMap.h:452
unsigned prohibited() const
Accessibility bits that are required to be clear.
Definition AddressMap.h:380
AddressMapConstraints before(Address x) const
Limit addreses.
Definition AddressMap.h:345
void print(std::ostream &out) const
Print constraints in a human readable form.
Definition AddressMap.h:156
AddressMapConstraints singleSegment() const
Limit matching to single segment.
Definition AddressMap.h:350
AddressMapConstraints segmentPredicate(SegmentPredicate< Address, Value > *p) const
Limit segments.
Definition AddressMap.h:357
AddressMapConstraints prohibit(unsigned bits) const
Prohibit certain access permissions.
Definition AddressMap.h:246
const Callbacks< SegmentPredicate< Address, Value > * > segmentPredicates() const
Returns the segment predicates.
Definition AddressMap.h:433
AddressMapConstraints after(Address x) const
Limit addresses.
Definition AddressMap.h:340
AddressMapConstraints substr(const std::string &s) const
Require certain segment names.
Definition AddressMap.h:258
AddressMapConstraints any() const
No constraints.
Definition AddressMap.h:266
bool neverMatches() const
Returns true if the constraint is not allowed to match anything.
Definition AddressMap.h:392
bool isAnchored() const
Determines whether constraints are anchored to an address.
Definition AddressMap.h:397
AddressMapConstraints(AddressMap *map)
Construct a constraint that matches everything.
Definition AddressMap.h:97
AddressMapConstraints require(unsigned bits) const
Require certain access permissions.
Definition AddressMap.h:239
AddressMap * map() const
Returns a pointer to the memory map for this constraint object.
Definition AddressMap.h:438
AddressMapConstraints none() const
Constraints that match nothing.
Definition AddressMap.h:271
AddressMapConstraints atOrBefore(Address greatest) const
Limit addresses.
Definition AddressMap.h:312
AddressMapConstraints atOrAfter(Address least) const
Limit addresses.
Definition AddressMap.h:299
AddressMapConstraints baseSize(Address base, Address size) const
Limit addresses.
Definition AddressMap.h:335
AddressMapConstraints at(Address x) const
Anchor at a certain address.
Definition AddressMap.h:278
friend std::ostream & operator<<(std::ostream &out, const AddressMapConstraints &x)
Print constraints in a human readable form.
Definition AddressMap.h:230
AddressMapConstraints access(unsigned bits) const
Require and prohibit certain access permissions.
Definition AddressMap.h:253
AddressMapConstraints at(const Sawyer::Container::Interval< Address > &x) const
Anchor at a certain interval.
Definition AddressMap.h:285
Base class for traversals.
A mapping from address space to values.
Sawyer::Container::Interval< Address > available(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Adress interval that satisfies constraints.
AddressMapConstraints< const AddressMap > within(const Sawyer::Container::Interval< Address > &x) const
Constraint: address lower and upper bounds.
Optional< Address > findFreeSpace(size_t nValues, size_t alignment=1, Sawyer::Container::Interval< Address > restriction=Sawyer::Container::Interval< Address >::whole(), MatchFlags flags=0) const
Find free space.
boost::iterator_range< SegmentIterator > segments(const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Iterator range for all segments.
Super::ConstIntervalIterator ConstIntervalIterator
Iterates over address intervals in the map.
void traverse(Functor &functor, const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Invoke a function on each address interval.
A Address
Type for addresses.
ConstNodeIterator findNode(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Find node containing address.
AddressMapConstraints< const AddressMap > any() const
Constraint: matches anything.
void changeAccess(unsigned requiredAccess, unsigned prohibitedAccess, const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Change access bits for addresses that match constraints.
NodeIterator findNode(const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Find node containing address.
Sawyer::Container::Interval< Address > write(const std::vector< Value > &buf, const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Writes data from the supplied buffer.
AddressMapConstraints< const AddressMap > before(Address x) const
Constraint: address upper bound.
AddressMap(const AddressMap &other, bool copyOnWrite=false)
Copy constructor.
void checkConsistency() const
Check map consistency.
AddressSegment< A, T > Segment
Type of segments stored by this map.
Sawyer::Container::Interval< Address > read(Value *buf, const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Reads data into the supplied buffer.
AddressMapConstraints< AddressMap > none()
Constraint: matches nothing.
AddressMap()
Constructs an empty address map.
AddressMapConstraints< AddressMap > singleSegment()
Constraint: single segment.
AddressMapConstraints< const AddressMap > prohibit(unsigned x) const
Constraint: prohibited access bits.
AddressMapConstraints< const AddressMap > atOrAfter(Address x) const
Constraint: address lower bound.
AddressMapConstraints< const AddressMap > singleSegment() const
Constraint: single segment.
AddressMapConstraints< AddressMap > substr(const std::string &x)
Constraint: segment name substring.
AddressMapConstraints< const AddressMap > at(const Sawyer::Container::Interval< Address > &x) const
Constraint: anchored interval.
AddressMapConstraints< AddressMap > within(const Sawyer::Container::Interval< Address > &x)
Constraint: address lower and upper bounds.
AddressMapConstraints< AddressMap > within(Address x, Address y)
Constraint: address lower and upper bounds.
AddressMapConstraints< const AddressMap > at(Address x) const
Constraint: anchor point.
AddressMapConstraints< AddressMap > limit(size_t x)
Constraint: limit matched size.
AddressMapConstraints< const AddressMap > none() const
Constraint: matches nothing.
Address nSegments() const
Number of segments contained in the map.
void prune(const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Prune away addresses that match constraints.
void traverse(Visitor &visitor, const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Invoke a function on each address interval.
AddressMapConstraints< const AddressMap > substr(const std::string &x) const
Constraint: segment name substring.
boost::iterator_range< ConstNodeIterator > nodes() const
Iterator range for nodes.
boost::iterator_range< SegmentIterator > segments()
Iterator range for all segments.
AddressMapConstraints< const AddressMap > require(unsigned x) const
Constraint: required access bits.
AddressMapConstraints< AddressMap > require(unsigned x)
Constraint: required access bits.
void traverse(Functor &functor, const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Invoke a function on each address interval.
AddressMapConstraints< AddressMap > at(const Sawyer::Container::Interval< Address > &x)
Constraint: anchored interval.
void traverse(Visitor &visitor, const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Invoke a function on each address interval.
boost::iterator_range< NodeIterator > nodes(const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Nodes that overlap with constraints.
Super::ValueIterator SegmentIterator
Iterates over segments in the map.
AddressMapConstraints< const AddressMap > after(Address x) const
Constraint: address lower bound.
AddressMapConstraints< AddressMap > atOrBefore(Address x)
Constraint: address upper bound.
T Value
Type of data stored in the address space.
Super::ConstValueIterator ConstSegmentIterator
Iterators over segments in the map.
AddressMapConstraints< AddressMap > at(Address x)
Constraint: anchor point.
AddressMapConstraints< AddressMap > prohibit(unsigned x)
Constraint: prohibited access bits.
void keep(const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Keep only addresses that match constraints.
AddressMapConstraints< AddressMap > access(unsigned x)
Constraint: required and prohibited access bits.
AddressMapConstraints< AddressMap > before(Address x)
Constraint: address upper bound.
Super::ConstNodeIterator ConstNodeIterator
Iterates over address interval/segment pairs in the map.
AddressMapConstraints< AddressMap > any()
Constraint: matches anything.
AddressMapConstraints< const AddressMap > limit(size_t x) const
Constraint: limit matched size.
boost::iterator_range< NodeIterator > nodes()
Iterator range for nodes.
Super::NodeIterator NodeIterator
Iterates over address interval, segment pairs in the map.
Sawyer::Container::Interval< Address > unmapped(Address boundary, MatchFlags flags=0) const
Find unmapped interval.
Sawyer::Container::Interval< Address > write(const Value *buf, const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Writes data from the supplied buffer.
AddressMapConstraints< AddressMap > after(Address x)
Constraint: address lower bound.
AddressMapConstraints< AddressMap > segmentPredicate(SegmentPredicate< Address, Value > *p)
Constraint: arbitrary segment constraint.
boost::iterator_range< ConstNodeIterator > nodes(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Nodes that overlap with constraints.
boost::iterator_range< ConstSegmentIterator > segments(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Segments that overlap with constraints.
bool exists(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Determines if an address exists with the specified constraints.
AddressMapConstraints< const AddressMap > atOrBefore(Address x) const
Constraint: address upper bound.
AddressMapConstraints< const AddressMap > access(unsigned x) const
Constraint: required and prohibited access bits.
AddressMapConstraints< const AddressMap > baseSize(Address base, Address size) const
Constraint: address lower and upper bounds.
AddressMapConstraints< const AddressMap > within(Address x, Address y) const
Constraint: address lower and upper bounds.
Sawyer::Container::Interval< Address > read(std::vector< Value > &buf, const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Reads data into the supplied buffer.
AddressMapConstraints< AddressMap > baseSize(Address base, Address size)
Constraint: address lower and upper bounds.
Optional< Address > next(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Minimum or maximum address that satisfies constraints.
Super::Node Node
Storage node containing interval/segment pair.
boost::iterator_range< ConstSegmentIterator > segments() const
Iterator range for all segments.
AddressMapConstraints< AddressMap > atOrAfter(Address x)
Constraint: address lower bound.
AddressMapConstraints< const AddressMap > segmentPredicate(SegmentPredicate< Address, Value > *p) const
Constraint: arbitrary segment constraint.
A homogeneous interval of an address space.
const std::string & name() const
Property: name.
A offset() const
Property: buffer offset.
unsigned accessibility() const
Property: access rights.
Buffer< A, T >::Ptr buffer() const
Property: buffer.
BitVector & fromInteger(const BitRange &range, boost::uint64_t value)
Obtain bits from an integer.
Definition BitVector.h:1340
std::string toHex(const BitRange &range) const
Convert to a hexadecimal string.
Definition BitVector.h:1268
Base class for all buffers.
Definition Buffer.h:23
An associative container whose keys are non-overlapping intervals.
size_t nIntervals() const
Number of nodes in the container.
void insert(Interval key, Value value, bool makeHole=true)
Insert a key/value pair.
Interval firstUnmapped(typename Interval::Value minAddr) const
Find the first unmapped region.
Interval lastUnmapped(typename Interval::Value maxAddr) const
Find the last unmapped region.
boost::iterator_range< NodeIterator > nodes()
Iterators for traversing nodes.
boost::iterator_range< ValueIterator > values()
Iterators for traversing values.
void erase(const Interval &erasure)
Erase the specified interval.
NodeIterator lowerBound(const typename Interval::Value &scalar)
Find the first node whose interval ends at or above the specified scalar key.
bool isEmpty() const
Determine if the container is empty.
Interval::Value size() const
Returns the number of values represented by this container.
A container holding a set of values.
Definition IntervalSet.h:53
void insert(const Interval2 &interval)
Insert specified values.
boost::iterator_range< ConstIntervalIterator > intervals() const
Iterator range for all intervals actually stored by this set.
Range of values delimited by endpoints.
Definition Interval.h:31
T greatest() const
Returns upper limit.
Definition Interval.h:224
static Interval baseSize(T lo, T size)
Construct an interval from one endpoint and a size.
Definition Interval.h:173
static Interval hull(T v1, T v2)
Construct an interval from two endpoints.
Definition Interval.h:162
bool contains(const Interval &other) const
Containment predicate.
Definition Interval.h:257
Value size() const
Size of interval.
Definition Interval.h:302
bool isEmpty() const
True if interval is empty.
Definition Interval.h:230
T least() const
Returns lower limit.
Definition Interval.h:218
static Interval whole()
Construct an interval that covers the entire domain.
Definition Interval.h:191
Bidirectional iterator over keys.
Definition Sawyer/Map.h:243
Bidirectional iterator over key/value nodes.
Definition Sawyer/Map.h:213
Bidirectional iterator over values.
Definition Sawyer/Map.h:296
Bidirectional iterator over key/value nodes.
Definition Sawyer/Map.h:187
Type for stored nodes.
Definition Sawyer/Map.h:107
Bidirectional iterator over values.
Definition Sawyer/Map.h:271
Base class for testing segment constraints.
Definition AddressMap.h:55
Represents no value.
Definition Optional.h:36
Holds a value or nothing.
Definition Optional.h:56
Reference-counting intrusive smart pointer.
std::uint64_t Address
Address.
Definition Address.h:11
unsigned MatchFlags
Flags for matching constraints.
Definition AddressMap.h:46
Sawyer support library.