ROSE  0.11.28.0
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://github.com/matzke1/sawyer.
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/foreach.hpp>
24 #include <boost/integer_traits.hpp>
25 #include <boost/lexical_cast.hpp>
26 #include <boost/serialization/access.hpp>
27 #include <boost/serialization/base_object.hpp>
28 #include <boost/serialization/nvp.hpp>
29 
30 #if __cplusplus >= 201103L
31 #include <type_traits>
32 #endif
33 
34 namespace Sawyer {
35 namespace Container {
36 
37 template<class AddressMap>
39  typedef typename AddressMap::NodeIterator NodeIterator;
41 };
42 
43 template<class AddressMap>
47 };
48 
50 typedef unsigned MatchFlags;
51 static const MatchFlags MATCH_BACKWARD = 0x00000001;
52 static const MatchFlags MATCH_CONTIGUOUS = 0x00000002;
53 static const MatchFlags MATCH_NONCONTIGUOUS = 0x00000004;
54 static const MatchFlags MATCH_WHOLE = 0x00000008;
58 template<class A, class T>
60 public:
61  struct Args {
62  const Sawyer::Container::Interval<A> &interval;
63  const AddressSegment<A, T> &segment;
64  Args(const Sawyer::Container::Interval<A> &interval, const AddressSegment<A, T> &segment)
65  : interval(interval), segment(segment) {}
66  };
67 
68  virtual ~SegmentPredicate() {}
69  virtual bool operator()(bool chain, const Args &) = 0;
70 };
71 
79 template<typename AddressMap>
81 public:
82  typedef typename AddressMap::Address Address;
83  typedef typename AddressMap::Value Value;
85 private:
86  AddressMap *map_; // AddressMap<> to which these constraints are bound
87  bool never_; // never match anything (e.g., when least_ > greatest_)
88  // address constraints
89  Optional<Address> least_; // least possible valid address
90  Optional<Address> greatest_; // greatest possible valid address
91  Optional<AddressInterval> anchored_; // anchored least or greatest depending on direction
92  // constraints requiring iteration
93  size_t maxSize_; // result size is limited
94  bool singleSegment_; // do not cross a segment boundary
95  unsigned requiredAccess_; // access bits that must be set in the segment
96  unsigned prohibitedAccess_; // access bits that must be clear in the segment
97  std::string nameSubstring_; // segment name must contain substring
98  Callbacks<SegmentPredicate<Address, Value>*> segmentPredicates_; // user-supplied segment predicates
99 public:
102  : map_(map), never_(false), maxSize_(size_t(-1)), singleSegment_(false), requiredAccess_(0), prohibitedAccess_(0) {}
103 
104 #if __cplusplus >= 201103L
105  // Implicitly construct constraints for a const AddressMap from a non-const address map. The dummy U parameter is to force
106  // type deduction to be delayed to the point where this function is instantiated.
107  template<typename U = AddressMap, typename = typename std::enable_if<!std::is_const<U>::value, void>::type>
108  operator AddressMapConstraints<const U>() const {
110  if (neverMatches())
111  cc = cc.none();
112  if (isAnchored()) {
113  if (anchored().isSingleton()) {
114  cc = cc.at(anchored().least());
115  } else {
116  cc = cc.at(anchored());
117  }
118  }
119  if (least())
120  cc = cc.atOrAfter(*least());
121  if (greatest())
122  cc = cc.atOrBefore(*greatest());
123  cc = cc.limit(limit());
124  if (isSingleSegment())
125  cc = cc.singleSegment();
126  cc = cc.require(required());
127  cc = cc.prohibit(prohibited());
128  cc = cc.substr(substr());
129  cc = cc.segmentPredicates(segmentPredicates());
130  return cc;
131  }
132 #else
133  operator AddressMapConstraints<const AddressMap>() const {
134  AddressMapConstraints<const AddressMap> cc(map_);
135  if (neverMatches())
136  cc = cc.none();
137  if (isAnchored()) {
138  if (anchored().isSingleton()) {
139  cc = cc.at(anchored().least());
140  } else {
141  cc = cc.at(anchored());
142  }
143  }
144  if (least())
145  cc = cc.atOrAfter(*least());
146  if (greatest())
147  cc = cc.atOrBefore(*greatest());
148  cc = cc.limit(limit());
149  if (isSingleSegment())
150  cc = cc.singleSegment();
151  cc = cc.require(required());
152  cc = cc.prohibit(prohibited());
153  cc = cc.substr(substr());
154  cc = cc.segmentPredicates(segmentPredicates());
155  return cc;
156  }
157 #endif
158 
160  void print(std::ostream &out) const {
161  out <<"{map=" <<map_;
162  if (never_)
163  out <<", never";
164  if (least_)
165  out <<", least=" <<*least_;
166  if (greatest_)
167  out <<", greatest=" <<*greatest_;
168  if (anchored_) {
169  out <<", anchored=";
170  AddressInterval a = *anchored_;
171  if (a.isEmpty()) {
172  out <<"empty";
173  } else if (a.least()==a.greatest()) {
174  out <<a.least();
175  } else {
176  out <<"{" <<a.least() <<".." <<a.greatest() <<"}";
177  }
178  }
179  if (maxSize_ != size_t(-1))
180  out <<", limit=" <<maxSize_;
181  if (singleSegment_)
182  out <<", single-segment";
183  if (requiredAccess_!=0) {
184  out <<", required="
185  <<((requiredAccess_ & Access::READABLE) ? "r" : "")
186  <<((requiredAccess_ & Access::WRITABLE) ? "w" : "")
187  <<((requiredAccess_ & Access::EXECUTABLE) ? "x" : "")
188  <<((requiredAccess_ & Access::IMMUTABLE) ? "i" : "");
189  unsigned other = requiredAccess_ & ~(Access::READABLE|Access::WRITABLE|Access::EXECUTABLE|Access::IMMUTABLE);
190  if (other)
191  out <<"+0x" <<BitVector(8*sizeof requiredAccess_).fromInteger(other).toHex();
192  }
193  if (prohibitedAccess_!=0) {
194  out <<", required="
195  <<((prohibitedAccess_ & Access::READABLE) ? "r" : "")
196  <<((prohibitedAccess_ & Access::WRITABLE) ? "w" : "")
197  <<((prohibitedAccess_ & Access::EXECUTABLE) ? "x" : "")
198  <<((prohibitedAccess_ & Access::IMMUTABLE) ? "i" : "");
199  unsigned other = prohibitedAccess_ & ~(Access::READABLE|Access::WRITABLE|Access::EXECUTABLE|Access::IMMUTABLE);
200  if (other)
201  out <<"+0x" <<BitVector(8*sizeof prohibitedAccess_).fromInteger(other).toHex();
202  }
203  if (!nameSubstring_.empty()) {
204  out <<", substr=\"";
205  BOOST_FOREACH (char ch, nameSubstring_) {
206  switch (ch) {
207  case '\a': out <<"\\a"; break;
208  case '\b': out <<"\\b"; break;
209  case '\t': out <<"\\t"; break;
210  case '\n': out <<"\\n"; break;
211  case '\v': out <<"\\v"; break;
212  case '\f': out <<"\\f"; break;
213  case '\r': out <<"\\r"; break;
214  case '\"': out <<"\\\""; break;
215  case '\\': out <<"\\\\"; break;
216  default:
217  if (isprint(ch)) {
218  out <<ch;
219  } else {
220  char buf[8];
221  sprintf(buf, "\\%03o", (unsigned)(unsigned char)ch);
222  out <<buf;
223  }
224  break;
225  }
226  }
227  }
228  if (!segmentPredicates_.isEmpty())
229  out <<", user-def";
230  out <<"}";
231  }
232 
234  friend std::ostream& operator<<(std::ostream &out, const AddressMapConstraints &x) {
235  x.print(out);
236  return out;
237  }
238 
240  // Constraint modifiers
241 public:
243  AddressMapConstraints require(unsigned bits) const {
244  AddressMapConstraints retval = *this;
245  retval.requiredAccess_ |= bits;
246  return retval;
247  }
248 
250  AddressMapConstraints prohibit(unsigned bits) const {
251  AddressMapConstraints retval = *this;
252  retval.prohibitedAccess_ |= bits;
253  return retval;
254  }
255 
257  AddressMapConstraints access(unsigned bits) const {
258  return require(bits).prohibit(~bits);
259  }
260 
262  AddressMapConstraints substr(const std::string &s) const {
263  ASSERT_require(nameSubstring_.empty() || nameSubstring_==s);// substring conjunction not supported
264  AddressMapConstraints retval = *this;
265  retval.nameSubstring_ = s;
266  return retval;
267  }
268 
271  return *this;
272  }
273 
276  AddressMapConstraints retval = *this;
277  retval.never_ = true;
278  return retval;
279  }
280 
282  AddressMapConstraints at(Address x) const {
283  AddressMapConstraints retval = *this;
284  retval.anchored_ = anchored_ ? *anchored_ & AddressInterval(x) : AddressInterval(x);
285  return retval.anchored_->isEmpty() ? retval.none() : retval;
286  }
287 
290  AddressMapConstraints retval = *this;
291  retval.anchored_ = anchored_ ? *anchored_ & x : x;
292  return retval.anchored_->isEmpty() ? retval.none() : retval.atOrAfter(x.least()).atOrBefore(x.greatest());
293  }
294 
296  AddressMapConstraints limit(size_t x) const {
297  AddressMapConstraints retval = *this;
298  retval.maxSize_ = std::min(maxSize_, x);
299  return 0 == retval.maxSize_ ? retval.none() : retval;
300  }
301 
304  AddressMapConstraints retval = *this;
305  if (least_) {
306  retval.least_ = std::max(*least_, least);
307  } else {
308  retval.least_ = least;
309  }
310  if (greatest_ && *greatest_ < *retval.least_)
311  retval.none();
312  return retval;
313  }
314 
317  AddressMapConstraints retval = *this;
318  if (greatest_) {
319  retval.greatest_ = std::min(*greatest_, greatest);
320  } else {
321  retval.greatest_ = greatest;
322  }
323  if (least_ && *least_ > *retval.greatest_)
324  retval.none();
325  return retval;
326  }
327 
330  return x.isEmpty() ? none() : atOrAfter(x.least()).atOrBefore(x.greatest());
331  }
332 
334  AddressMapConstraints within(Address lo, Address hi) const {
335  return lo<=hi ? within(Sawyer::Container::Interval<Address>::hull(lo, hi)) : none();
336  }
337 
339  AddressMapConstraints baseSize(Address base, Address size) const {
340  return size>0 ? atOrAfter(base).atOrBefore(base+size-1) : none();
341  }
342 
344  AddressMapConstraints after(Address x) const {
345  return x==boost::integer_traits<Address>::const_max ? none() : atOrAfter(x+1);
346  }
347 
349  AddressMapConstraints before(Address x) const {
350  return x==boost::integer_traits<Address>::const_min ? none() : atOrBefore(x-1);
351  }
352 
355  AddressMapConstraints retval = *this;
356  retval.singleSegment_ = true;
357  return retval;
358  }
359 
362  if (!p)
363  return none();
364  AddressMapConstraints retval = *this;
365  retval.segmentPredicates_.append(p);
366  return retval;
367  }
368 
370  AddressMapConstraints retval = *this;
371  retval.segmentPredicates_.append(predicates);
372  return retval;
373  }
374 
376  // Constraint queries
377 public:
379  unsigned required() const {
380  return requiredAccess_;
381  }
382 
384  unsigned prohibited() const {
385  return prohibitedAccess_;
386  }
387 
389  const std::string& substr() const {
390  return nameSubstring_;
391  }
392 
396  bool neverMatches() const {
397  return never_;
398  }
399 
401  bool isAnchored() const {
402  return anchored_;
403  }
404 
409  AddressInterval anchored() const {
410  ASSERT_require(isAnchored());
411  return *anchored_;
412  }
413 
415  size_t limit() const {
416  return maxSize_;
417  }
418 
421  const Optional<Address>& least() const {
422  return least_;
423  }
424 
427  const Optional<Address>& greatest() const {
428  return greatest_;
429  }
430 
432  bool isSingleSegment() const {
433  return singleSegment_;
434  }
435 
438  return segmentPredicates_;
439  }
440 
442  AddressMap* map() const {
443  return map_;
444  }
445 
449  return (!never_ &&
450  (requiredAccess_ || prohibitedAccess_ || !nameSubstring_.empty() || maxSize_!=size_t(-1) ||
451  singleSegment_ || !segmentPredicates_.isEmpty()));
452  }
453 
457  AddressMapConstraints c(map_);
458  c.least_ = least_;
459  c.greatest_ = greatest_;
460  c.anchored_ = anchored_;
461  c.maxSize_ = maxSize_;
462  return c;
463  }
464 
466  // Methods that directly call the AddressMap
467 public:
468  boost::iterator_range<typename AddressMapTraits<AddressMap>::NodeIterator>
469  nodes(MatchFlags flags=0) const {
470  return map_->nodes(*this, flags);
471  }
472 
473  boost::iterator_range<typename AddressMapTraits<AddressMap>::SegmentIterator>
474  segments(MatchFlags flags=0) const {
475  return map_->segments(*this, flags);
476  }
477 
478  Optional<typename AddressMap::Address>
479  next(MatchFlags flags=0) const {
480  return map_->next(*this, flags);
481  }
482 
484  available(MatchFlags flags=0) const {
485  return map_->available(*this, flags);
486  }
487 
488  bool
489  exists(MatchFlags flags=0) const {
490  return map_->exists(*this, flags);
491  }
492 
493  typename AddressMapTraits<AddressMap>::NodeIterator
494  findNode(MatchFlags flags=0) const {
495  return map_->findNode(*this, flags);
496  }
497 
498  template<typename Functor>
499  void
500  traverse(Functor &functor, MatchFlags flags=0) const {
501  return map_->traverse(functor, *this, flags);
502  }
503  void
504  traverse(typename AddressMap::Visitor &visitor, MatchFlags flags=0) const {
505  return map_->template traverse<typename AddressMap::Visitor>(visitor, *this, flags);
506  }
507 
509  read(typename AddressMap::Value *buf /*out*/, MatchFlags flags=0) const {
510  return map_->read(buf, *this, flags);
511  }
512 
514  read(std::vector<typename AddressMap::Value> &buf /*out*/,
515  MatchFlags flags=0) const {
516  return map_->read(buf, *this, flags);
517  }
518 
520  write(const typename AddressMap::Value *buf, MatchFlags flags=0) const {
521  return map_->write(buf, *this, flags);
522  }
523 
525  write(const std::vector<typename AddressMap::Value> &buf, MatchFlags flags=0) {
526  return map_->write(buf, *this, flags);
527  }
528 
529  void
530  prune(MatchFlags flags=0) const {
531  return map_->prune(*this, flags);
532  }
533 
534  void
535  keep(MatchFlags flags=0) const {
536  return map_->keep(*this, flags);
537  }
538 
539  void
540  changeAccess(unsigned requiredAccess, unsigned prohibitedAccess, MatchFlags flags=0) const {
541  return map_->changeAccess(requiredAccess, prohibitedAccess, *this, flags);
542  }
543 };
544 
546 // Implementation details
548 namespace AddressMapImpl {
549 
550 // Used internally to split and merge segments
551 template<class A, class T>
553 public:
554  typedef A Address;
555  typedef T Value;
557 
558 private:
559  friend class boost::serialization::access;
560 
561  template<class S>
562  void serialize(S&, const unsigned /*version*/) {
563  // no data to serialize here
564  }
565 
566 public:
567  bool merge(const Sawyer::Container::Interval<Address> &leftInterval, Segment &leftSegment,
568  const Sawyer::Container::Interval<Address> &rightInterval, Segment &rightSegment) {
569  ASSERT_forbid(leftInterval.isEmpty());
570  ASSERT_always_forbid(rightInterval.isEmpty()); // so rightInterval is always used
571  ASSERT_require(leftInterval.greatest() + 1 == rightInterval.least());
572  return (leftSegment.accessibility() == rightSegment.accessibility() &&
573  leftSegment.name() == rightSegment.name() &&
574  leftSegment.buffer() == rightSegment.buffer() &&
575  leftSegment.offset() + leftInterval.size() == rightSegment.offset());
576  }
577 
578  Segment split(const Sawyer::Container::Interval<Address> &interval, Segment &segment, Address splitPoint) {
579  ASSERT_forbid(interval.isEmpty());
580  ASSERT_require(interval.isContaining(splitPoint));
581  Segment right = segment;
582  right.offset(segment.offset() + splitPoint - interval.least());
583  return right;
584  }
585 
586  void truncate(const Sawyer::Container::Interval<Address> &interval, Segment &/*segment*/, Address splitPoint) {
587  ASSERT_always_forbid(interval.isEmpty()); // so interval is always used
588  ASSERT_always_require(interval.isContaining(splitPoint)); // ditto for splitPoint
589  }
590 };
591 
592 // The results for matching constraints
593 template<class AddressMap>
595  typedef typename AddressMap::Address Address;
598  boost::iterator_range<NodeIterator> nodes_;
599 };
600 
601 // Finds the minimum possible address and node iterator for the specified constraints in this map and returns that
602 // iterator. Returns the end iterator if the constraints match no address. If a non-end iterator is returned then minAddr
603 // is adjusted to be the minimum address that satisfies the constraint (it will be an address within the returned node, but
604 // not necessarily the least address for the node). If useAnchor is set and the constraints specify an anchor, then the
605 // anchor address must be present in the map and satisfy any address constraints that might also be present.
606 template<class AddressMap>
608 constraintLowerBound(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, bool useAnchor,
609  typename AddressMap::Address &minAddr) {
610  typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
611  if (amap.isEmpty() || c.neverMatches())
612  return amap.nodes().end();
613 
614  if (useAnchor && c.isAnchored()) { // forward matching if useAnchor is set
615  if ((c.least() && *c.least() > c.anchored().least()) || (c.greatest() && *c.greatest() < c.anchored().greatest()))
616  return amap.nodes().end(); // anchor is outside of allowed interval
617  Iterator lb = amap.lowerBound(c.anchored().least());
618  if (lb==amap.nodes().end() || c.anchored().least() < lb->key().least())
619  return amap.nodes().end(); // anchor is not present in this map
620  minAddr = c.anchored().least();
621  return lb;
622  }
623 
624  if (c.least()) {
625  Iterator lb = amap.lowerBound(*c.least());
626  if (lb==amap.nodes().end())
627  return lb; // least is above all segments
628  minAddr = std::max(*c.least(), lb->key().least());
629  return lb;
630  }
631 
632  Iterator lb = amap.nodes().begin();
633  if (lb!=amap.nodes().end())
634  minAddr = lb->key().least();
635  return lb;
636 }
637 
638 // Finds the maximum possible address and node for the specified constraints in this map, and returns an iterator to the
639 // following node. Returns the begin iterator if the constraints match no address. If a non-begin iterator is returned
640 // then maxAddr is adjusted to be the maximum address that satisfies the constraint (it will be an address that belongs to
641 // the node immediately prior to the one pointed to by the returned iterator, but not necessarily the greatest address for
642 // that node). If useAnchor is set and the constraints specify an anchor, then the anchor address must be present in the
643 // map and satisfy any address constraints that might also be present.
644 template<class AddressMap>
645 typename AddressMapTraits<AddressMap>::NodeIterator
646 constraintUpperBound(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, bool useAnchor,
647  typename AddressMap::Address &maxAddr) {
648  typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
649  if (amap.isEmpty() || c.neverMatches())
650  return amap.nodes().begin();
651 
652  if (useAnchor && c.isAnchored()) { // backward matching if useAnchor is set
653  if ((c.least() && *c.least() > c.anchored().least()) || (c.greatest() && *c.greatest() < c.anchored().greatest()))
654  return amap.nodes().begin(); // anchor is outside allowed interval
655  Iterator ub = amap.findPrior(c.anchored().greatest());
656  if (ub==amap.nodes().end() || c.anchored().greatest() > ub->key().greatest())
657  return amap.nodes().begin(); // anchor is not present in this map
658  maxAddr = c.anchored().greatest();
659  return ++ub; // return node after the one containing the anchor
660  }
661 
662  if (c.greatest()) {
663  Iterator ub = amap.findPrior(*c.greatest());
664  if (ub==amap.nodes().end())
665  return amap.nodes().begin(); // greatest is below all segments
666  maxAddr = std::min(ub->key().greatest(), *c.greatest());
667  return ++ub; // return node after the one containing the maximum
668  }
669 
670  maxAddr = amap.hull().greatest();
671  return amap.nodes().end();
672 }
673 
674 // Returns true if the segment satisfies the non-address constraints in c.
675 template<class AddressMap>
676 bool
677 isSatisfied(const typename AddressMap::Node &node, const AddressMapConstraints<AddressMap> &c) {
678  typedef typename AddressMap::Address Address;
679  typedef typename AddressMap::Value Value;
680  typedef typename AddressMap::Segment Segment;
681  const Segment &segment = node.value();
682  if (!segment.isAccessible(c.required(), c.prohibited()))
683  return false; // wrong segment permissions
684  if (!boost::contains(segment.name(), c.substr()))
685  return false; // wrong segment name
686  if (!c.segmentPredicates().apply(true, typename SegmentPredicate<Address, Value>::Args(node.key(), node.value())))
687  return false; // user-supplied predicates failed
688  return true;
689 }
690 
691 // Matches constraints against contiguous addresses in a forward direction.
692 template<class AddressMap>
693 MatchedConstraints<AddressMap>
694 matchForward(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, MatchFlags flags) {
695  typedef typename AddressMap::Address Address;
696  typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
697  MatchedConstraints<AddressMap> retval;
698  retval.nodes_ = boost::iterator_range<Iterator>(amap.nodes().end(), amap.nodes().end());
699  if (c.neverMatches() || amap.isEmpty())
700  return retval;
701 
702  // Find a lower bound for the minimum address
703  Address minAddr = 0;
704  Iterator begin = constraintLowerBound(amap, c, true, minAddr /*out*/);
705  if (begin == amap.nodes().end())
706  return retval;
707 
708  // Find an upper bound for the maximum address.
709  Address maxAddr = 0;
710  Iterator end = constraintUpperBound(amap, c, false, maxAddr /*out*/);
711  if (end==amap.nodes().begin())
712  return retval;
713 
714  // Advance the lower-bound until it satisfies the other (non-address) constraints
715  while (begin!=end && !isSatisfied(*begin, c)) {
716  if (c.isAnchored())
717  return retval; // match is anchored to minAddr
718  ++begin;
719  }
720  if (begin==end)
721  return retval;
722  minAddr = std::max(minAddr, begin->key().least());
723 
724  // Iterate forward until the constraints are no longer satisfied
725  if ((flags & MATCH_CONTIGUOUS)!=0 || c.hasNonAddressConstraints()) {
726  Address addr = minAddr;
727  Iterator iter = begin;
728  size_t nElmtsFound = 0;
729  for (/*void*/; iter!=end; ++iter) {
730  if (iter!=begin) { // already tested the first node above
731  if (c.isSingleSegment())
732  break; // we crossed a segment boundary
733  if ((flags & MATCH_CONTIGUOUS)!=0 && addr+1 != iter->key().least())
734  break; // gap between segments
735  if (!isSatisfied(*iter, c)) {
736  if ((flags & MATCH_WHOLE)!=0)
737  return retval; // match is anchored to maxAddr
738  break; // segment does not satisfy constraints
739  }
740  }
741  size_t nElmtsHere = iter->key().greatest() + 1 - std::max(minAddr, iter->key().least());
742  if (nElmtsFound + nElmtsHere >= c.limit()) {
743  size_t nNeed = c.limit() - nElmtsFound;
744  addr = std::max(minAddr, iter->key().least()) + nNeed - 1;
745  ++iter;
746  break; // too many values
747  }
748  addr = iter->key().greatest();
749  nElmtsFound += nElmtsHere;
750  }
751  end = iter;
752  maxAddr = std::min(maxAddr, addr);
753  }
754 
755  // Build the result
756  retval.interval_ = Sawyer::Container::Interval<Address>::hull(minAddr, maxAddr);
757  retval.nodes_ = boost::iterator_range<Iterator>(begin, end);
758  return retval;
759 }
760 
761 // Matches constraints against contiguous addresses in a backward direction.
762 template<class AddressMap>
763 MatchedConstraints<AddressMap>
764 matchBackward(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, MatchFlags flags) {
765  typedef typename AddressMap::Address Address;
766  typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
767  MatchedConstraints<AddressMap> retval;
768  retval.nodes_ = boost::iterator_range<Iterator>(amap.nodes().end(), amap.nodes().end());
769  if (c.neverMatches() || amap.isEmpty())
770  return retval;
771 
772  // Find a lower bound for the minimum address
773  Address minAddr = 0;
774  Iterator begin = constraintLowerBound(amap, c, false, minAddr /*out*/);
775  if (begin == amap.nodes().end())
776  return retval;
777 
778  // Find an upper bound for the maximum address.
779  Address maxAddr = 0;
780  Iterator end = constraintUpperBound(amap, c, true, maxAddr /*out*/);
781  if (end==amap.nodes().begin())
782  return retval;
783 
784  // Decrement the upper bound until constraints are met. End always points to one-past the last matching node.
785  while (end!=begin) {
786  Iterator prev = end; --prev;
787  if (isSatisfied(*prev, c)) {
788  maxAddr = std::min(maxAddr, prev->key().greatest());
789  break;
790  }
791  if (c.isAnchored())
792  return retval; // match is anchored to maxAddr
793  end = prev;
794  }
795  if (end==begin)
796  return retval;
797 
798  // Iterate backward until the constraints are no longer satisfied. Within the loop, iter always points to on-past the
799  // node in question. When the loop exits, iter points to the first node satisfying constraints.
800  if ((flags & MATCH_CONTIGUOUS)!=0 || c.hasNonAddressConstraints()) {
801  Address addr = maxAddr;
802  Iterator iter = end;
803  size_t nElmtsFound = 0;
804  for (/*void*/; iter!=begin; --iter) {
805  Iterator prev = iter; --prev; // prev points to the node in question
806  if (iter!=end) { // already tested last node above
807  if (c.isSingleSegment())
808  break; // we crossed a segment boundary
809  if ((flags & MATCH_CONTIGUOUS)!=0 && prev->key().greatest()+1 != addr)
810  break; // gap between segments
811  if (!isSatisfied(*prev, c)) {
812  if ((flags & MATCH_WHOLE)!=0)
813  return retval; // match is anchored to minAddr
814  break; // segment does not satisfy constraints
815  }
816  }
817  size_t nElmtsHere = std::min(maxAddr, prev->key().greatest()) - prev->key().least() + 1;
818  if (nElmtsFound + nElmtsHere >= c.limit()) {
819  size_t nNeed = c.limit() - nElmtsFound;
820  addr = std::min(maxAddr, prev->key().greatest()) - nNeed + 1;
821  iter = prev;
822  break;
823  }
824  addr = prev->key().least();
825  nElmtsFound += nElmtsHere;
826  }
827  begin = iter; // iter points to first matching node
828  minAddr = std::max(minAddr, addr);
829  }
830 
831  // Build the result
832  retval.interval_ = Sawyer::Container::Interval<Address>::hull(minAddr, maxAddr);
833  retval.nodes_ = boost::iterator_range<Iterator>(begin, end);
834  return retval;
835 }
836 
837 // Match constraints forward or backward
838 template<class AddressMap>
839 MatchedConstraints<AddressMap>
840 matchConstraints(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, MatchFlags flags) {
841  if ((flags & MATCH_BACKWARD) != 0)
842  return matchBackward(amap, c, flags);
843  return matchForward(amap, c, flags);
844 }
845 
846 } // namespace
847 
848 
1003 template<class A, class T = boost::uint8_t>
1004 class AddressMap: public IntervalMap<Interval<A>, AddressSegment<A, T>, AddressMapImpl::SegmentMergePolicy<A, T> > {
1005  // "Interval" is qualified to work around bug in Microsoft compilers. See doxygen note above.
1007 
1008 public:
1009  typedef A Address;
1010  typedef T Value;
1011  typedef AddressSegment<A, T> Segment;
1013  typedef typename Super::Node Node;
1020 private:
1021  friend class boost::serialization::access;
1022 
1023  template<class S>
1024  void serialize(S &s, const unsigned /*version*/) {
1025  s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Super);
1026  }
1027 
1028 public:
1031 
1047  AddressMap(const AddressMap &other, bool copyOnWrite=false): Super(other) {
1048  if (copyOnWrite) {
1049  BOOST_FOREACH (Segment &segment, this->values()) {
1050  if (const typename Buffer::Ptr &buffer = segment.buffer())
1051  buffer->copyOnWrite(true);
1052  }
1053  }
1054  }
1055 
1063  }
1066  }
1076  }
1079  }
1090  }
1092  return AddressMapConstraints<AddressMap>(this).access(x);
1093  }
1101  AddressMapConstraints<const AddressMap> substr(const std::string &x) const {
1103  }
1105  return AddressMapConstraints<AddressMap>(this).substr(x);
1106  }
1117  }
1119  return AddressMapConstraints<AddressMap>(this).at(x);
1120  }
1144  }
1146  return AddressMapConstraints<AddressMap>(this).at(x);
1147  }
1158  }
1160  return AddressMapConstraints<AddressMap>(this).limit(x);
1161  }
1171  }
1174  }
1184  }
1187  }
1197  }
1199  return AddressMapConstraints<AddressMap>(this).within(x);
1200  }
1208  AddressMapConstraints<const AddressMap> within(Address x, Address y) const {
1210  }
1212  return AddressMapConstraints<AddressMap>(this).within(x, y);
1213  }
1222  return AddressMapConstraints<const AddressMap>(this).baseSize(base, size);
1223  }
1225  return AddressMapConstraints<AddressMap>(this).baseSize(base, size);
1226  }
1236  }
1238  return AddressMapConstraints<AddressMap>(this).after(x);
1239  }
1249  }
1251  return AddressMapConstraints<AddressMap>(this).before(x);
1252  }
1262  }
1265  }
1275  }
1278  }
1288  }
1290  return AddressMapConstraints<AddressMap>(this);
1291  }
1301  }
1303  return AddressMapConstraints<AddressMap>(this).none();
1304  }
1314  void checkConsistency() const {
1315  BOOST_FOREACH (const Node &node, nodes()) {
1316  const Sawyer::Container::Interval<Address> &interval = node.key();
1317  const Segment &segment = node.value();
1318  if (segment.buffer()==NULL) {
1319  throw std::runtime_error("AddressMap null buffer for interval [" +
1320  boost::lexical_cast<std::string>(interval.least()) +
1321  "," + boost::lexical_cast<std::string>(interval.greatest()) + "]");
1322  }
1323  Address bufAvail = segment.buffer()->available(segment.offset());
1324  if (bufAvail < interval.size()) {
1325  throw std::runtime_error("AddressMap segment at [" + boost::lexical_cast<std::string>(interval.least()) +
1326  "," + boost::lexical_cast<std::string>(interval.greatest()) + "] points to only " +
1327  boost::lexical_cast<std::string>(bufAvail) + (1==bufAvail?" value":" values") +
1328  " but the interval size is " + boost::lexical_cast<std::string>(interval.size()));
1329  }
1330  }
1331  }
1332 
1339  Address nSegments() const { return this->nIntervals(); }
1340 
1346  boost::iterator_range<SegmentIterator> segments() { return this->values(); }
1347  boost::iterator_range<ConstSegmentIterator> segments() const { return this->values(); }
1348 
1369  boost::iterator_range<ConstSegmentIterator>
1370  segments(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1371  using namespace AddressMapImpl;
1372  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1373  flags |= MATCH_CONTIGUOUS;
1374  MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
1375  return boost::iterator_range<ConstSegmentIterator>(m.nodes_.begin(), m.nodes_.end());
1376  }
1377 
1378  boost::iterator_range<SegmentIterator>
1379  segments(const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1380  using namespace AddressMapImpl;
1381  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1382  flags |= MATCH_CONTIGUOUS;
1383  MatchedConstraints<AddressMap> m = matchConstraints(*this, c, flags);
1384  return boost::iterator_range<SegmentIterator>(m.nodes_);
1385  }
1394  boost::iterator_range<NodeIterator> nodes() { return Super::nodes(); }
1395  boost::iterator_range<ConstNodeIterator> nodes() const { return Super::nodes(); }
1417  boost::iterator_range<ConstNodeIterator>
1418  nodes(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1419  using namespace AddressMapImpl;
1420  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1421  flags |= MATCH_CONTIGUOUS;
1422  MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
1423  return m.nodes_;
1424  }
1425 
1426  boost::iterator_range<NodeIterator>
1427  nodes(const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1428  using namespace AddressMapImpl;
1429  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1430  flags |= MATCH_CONTIGUOUS;
1431  MatchedConstraints<AddressMap> m = matchConstraints(*this, c, flags);
1432  return m.nodes_;
1433  }
1474  next(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1475  using namespace AddressMapImpl;
1476  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1477  flags |= MATCH_CONTIGUOUS;
1478  MatchedConstraints<const AddressMap> m = matchConstraints(*this, c.limit(1), flags);
1479  return m.interval_.isEmpty() ? Optional<Address>() : Optional<Address>(m.interval_.least());
1480  }
1481 
1488  available(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1489  using namespace AddressMapImpl;
1490  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1491  flags |= MATCH_CONTIGUOUS;
1492  return matchConstraints(*this, c, flags).interval_;
1493  }
1494 
1504  bool exists(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1505  return next(c, flags);
1506  }
1507 
1513  ConstNodeIterator findNode(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1514  return nodes(c.limit(1), flags).begin();
1515  }
1516  NodeIterator findNode(const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1517  return nodes(c.limit(1), flags).begin();
1518  }
1529  unmapped(Address boundary, MatchFlags flags=0) const {
1530  return (flags & MATCH_BACKWARD) != 0 ? this->lastUnmapped(boundary) : this->firstUnmapped(boundary);
1531  }
1532 
1542  findFreeSpace(size_t nValues, size_t alignment=1,
1544  MatchFlags flags=0) const {
1546  ASSERT_forbid2(nValues == 0, "cannot determine if this is an overflow or intentional");
1547 
1548  if (restriction.isEmpty())
1549  return Nothing();
1550 
1551  if (0 == (flags & MATCH_BACKWARD)) {
1552  Address minAddr = restriction.least();
1553  while (minAddr <= restriction.greatest()) {
1554  Sawyer::Container::Interval<Address> interval = unmapped(minAddr, 0 /*forward*/);
1555  if (interval.isEmpty())
1556  return Nothing();
1557  minAddr = alignUp(interval.least(), alignment);
1558  Address maxAddr = minAddr + (nValues-1);
1559  if ((nValues <= interval.size() || 0==interval.size()/*overflow*/) &&
1560  minAddr >= interval.least()/*overflow*/ && maxAddr >= interval.least()/*overflow*/ &&
1561  maxAddr <= interval.greatest()) {
1562  return minAddr;
1563  }
1564  if (interval.greatest() == whole.greatest())
1565  return Nothing(); // to avoid overflow in next statement
1566  minAddr = interval.greatest() + 1;
1567  }
1568  return Nothing();
1569  }
1570 
1571  ASSERT_require((flags & MATCH_BACKWARD) != 0);
1572  Address maxAddr = restriction.greatest();
1573  while (maxAddr >= restriction.least()) {
1574  Sawyer::Container::Interval<Address> interval = unmapped(maxAddr, MATCH_BACKWARD);
1575  if (interval.isEmpty())
1576  return Nothing();
1577  Address minAddr = alignDown(interval.greatest() - (nValues-1), alignment);
1578  maxAddr = minAddr + (nValues-1);
1579  if ((nValues <= interval.size() || 0==interval.size()/*overflow*/) &&
1580  minAddr >= interval.least()/*overflow*/ && maxAddr >= interval.least()/*overflow*/ &&
1581  maxAddr <= interval.greatest()) {
1582  return minAddr;
1583  }
1584  if (interval.least() == whole.least())
1585  return Nothing(); // to avoid overflow in next statement
1586  maxAddr = interval.least() - 1;
1587  }
1588  return Nothing();
1589  }
1590 
1592  class Visitor {
1593  public:
1594  virtual ~Visitor() {}
1595  virtual bool operator()(const AddressMap&, const Sawyer::Container::Interval<Address>&) = 0;
1596  };
1597 
1621  template<typename Functor>
1622  void traverse(Functor &functor, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1623  using namespace AddressMapImpl;
1624  MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
1625  BOOST_FOREACH (const Node &node, m.nodes_) {
1626  Sawyer::Container::Interval<Address> part = m.interval_ & node.key();
1627  if (!functor(*this, part))
1628  return;
1629  }
1630  return;
1631  }
1632  template<typename Functor>
1633  void traverse(Functor &functor, const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1634  using namespace AddressMapImpl;
1635  MatchedConstraints<AddressMap> m = matchConstraints(*this, c, flags);
1636  BOOST_FOREACH (const Node &node, m.nodes_) {
1637  Sawyer::Container::Interval<Address> part = m.interval_ & node.key();
1638  if (!functor(*this, part))
1639  return;
1640  }
1641  return;
1642  }
1643  void traverse(Visitor &visitor, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1644  traverse<Visitor>(visitor, c, flags);
1645  }
1646  void traverse(Visitor &visitor, const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1647  traverse<Visitor>(visitor, c, flags);
1648  }
1690  read(Value *buf /*out*/, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1691  using namespace AddressMapImpl;
1692  ASSERT_require2(0 == (flags & MATCH_NONCONTIGUOUS), "only contiguous addresses can be read");
1693  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1694  flags |= MATCH_CONTIGUOUS;
1695  MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
1696  if (buf) {
1697  BOOST_FOREACH (const Node &node, m.nodes_) {
1698  Sawyer::Container::Interval<Address> part = m.interval_ & node.key(); // part of segment to read
1699  ASSERT_forbid(part.isEmpty());
1700  Address bufferOffset = part.least() - node.key().least() + node.value().offset();
1701  Address nValues = node.value().buffer()->read(buf, bufferOffset, part.size());
1702  if (nValues != part.size()) {
1703  checkConsistency();
1704  ASSERT_not_reachable("something is wrong with the memory map");
1705  }
1706  buf += nValues;
1707  }
1708  }
1709  return m.interval_;
1710  }
1711 
1713  read(std::vector<Value> &buf /*out*/, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1714  return buf.empty() ? Sawyer::Container::Interval<Address>() : read(&buf[0], c.limit(buf.size()), flags);
1715  }
1751  write(const Value *buf, const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1752  using namespace AddressMapImpl;
1753  ASSERT_require2(0 == (flags & MATCH_NONCONTIGUOUS), "only contiguous addresses can be written");
1754  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1755  flags |= MATCH_CONTIGUOUS;
1756  MatchedConstraints<AddressMap> m = matchConstraints(*this, c.prohibit(Access::IMMUTABLE), flags);
1757  if (buf) {
1758  BOOST_FOREACH (Node &node, m.nodes_) {
1759  Segment &segment = node.value();
1760  Sawyer::Container::Interval<Address> part = m.interval_ & node.key(); // part of segment to write
1761  ASSERT_forbid(part.isEmpty());
1762  typename Buffer::Ptr buffer = segment.buffer();
1763  ASSERT_not_null(buffer);
1764 
1765  if (buffer->copyOnWrite()) {
1766  typename Buffer::Ptr newBuffer = buffer->copy(); // copyOnWrite is cleared in newBuffer
1767  ASSERT_not_null(newBuffer);
1768  for (NodeIterator iter=this->lowerBound(node.key().least()); iter!=nodes().end(); ++iter) {
1769  if (iter->value().buffer() == buffer)
1770  iter->value().buffer(newBuffer);
1771  }
1772  buffer = newBuffer;
1773  }
1774 
1775  Address bufferOffset = part.least() - node.key().least() + segment.offset();
1776  Address nValues = buffer->write(buf, bufferOffset, part.size());
1777  if (nValues != part.size()) {
1778  checkConsistency();
1779  ASSERT_not_reachable("something is wrong with the memory map");
1780  }
1781  buf += nValues;
1782  }
1783  }
1784  return m.interval_;
1785  }
1786 
1788  write(const std::vector<Value> &buf, const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1789  return buf.empty() ? Sawyer::Container::Interval<Address>() : write(&buf[0], c.limit(buf.size()), flags);
1790  }
1805  void prune(const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1806  using namespace AddressMapImpl;
1808  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1809  flags |= MATCH_NONCONTIGUOUS;
1810  MatchedConstraints<AddressMap> m = matchConstraints(*this, c.addressConstraints(), flags);
1811  BOOST_FOREACH (const Node &node, m.nodes_) {
1812  if (isSatisfied(node, c))
1813  toErase.insert(node.key() & m.interval_);
1814  }
1815  BOOST_FOREACH (const Sawyer::Container::Interval<Address> &interval, toErase.intervals())
1816  this->erase(interval);
1817  }
1818 
1832  void keep(const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1833  using namespace AddressMapImpl;
1834  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1835  flags |= MATCH_NONCONTIGUOUS;
1837  MatchedConstraints<AddressMap> m = matchConstraints(*this, c.addressConstraints(), flags);
1838  BOOST_FOREACH (const Node &node, m.nodes_) {
1839  if (isSatisfied(node, c))
1840  toKeep.insert(node.key() & m.interval_);
1841  }
1842  toKeep.invert();
1843  BOOST_FOREACH (const Sawyer::Container::Interval<Address> &interval, toKeep.intervals())
1844  this->erase(interval);
1845  }
1846 
1866  void changeAccess(unsigned requiredAccess, unsigned prohibitedAccess, const AddressMapConstraints<AddressMap> &c,
1867  MatchFlags flags=0) {
1868  using namespace AddressMapImpl;
1869  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1870  flags |= MATCH_NONCONTIGUOUS;
1871  typedef std::pair<Sawyer::Container::Interval<Address>, Segment> ISPair;
1872  std::vector<ISPair> newSegments;
1873  MatchedConstraints<AddressMap> m = matchConstraints(*this, c.addressConstraints(), flags);
1874  BOOST_FOREACH (Node &node, m.nodes_) {
1875  Segment &segment = node.value();
1876  if (isSatisfied(node, c)) {
1877  unsigned newAccess = (segment.accessibility() | requiredAccess) & ~prohibitedAccess;
1878  Sawyer::Container::Interval<Address> toChange = node.key() & m.interval_;
1879  if (toChange == node.key()) { // all addresses in segment are selected; change segment in place
1880  segment.accessibility(newAccess);
1881  } else { // insert a new segment, replacing part of the existing one
1882  Segment newSegment(segment);
1883  newSegment.accessibility(newAccess);
1884  newSegment.offset(segment.offset() + toChange.least() - node.key().least());
1885  newSegments.push_back(ISPair(toChange, newSegment));
1886  }
1887  }
1888  }
1889  BOOST_FOREACH (const ISPair &pair, newSegments)
1890  this->insert(pair.first, pair.second);
1891  }
1892 
1893 private:
1894  // Increment x if necessary so it is aligned.
1895  static Address alignUp(Address x, Address alignment) {
1896  return alignment>0 && x%alignment!=0 ? ((x+alignment-1)/alignment)*alignment : x;
1897  }
1898 
1899  static Address alignDown(Address x, Address alignment) {
1900  return alignment>0 && x%alignment!=0 ? (x/alignment)*alignment : x;
1901  }
1902 };
1903 
1904 } // namespace
1905 } // namespace
1906 
1907 #endif
Base class for testing segment constraints.
Definition: AddressMap.h:59
unsigned required() const
Accessibility bits that are required to be set.
Definition: AddressMap.h:379
Interval lastUnmapped(typename Interval::Value maxAddr) const
Find the last unmapped region.
Definition: IntervalMap.h:564
unsigned MatchFlags
Flags for matching constraints.
Definition: AddressMap.h:50
AddressMapConstraints< const AddressMap > substr(const std::string &x) const
Constraint: segment name substring.
Definition: AddressMap.h:1101
NodeIterator findNode(const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Find node containing address.
Definition: AddressMap.h:1516
boost::iterator_range< NodeIterator > nodes(const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Nodes that overlap with constraints.
Definition: AddressMap.h:1427
const Optional< Address > & least() const
Least possible address.
Definition: AddressMap.h:421
AddressMapConstraints limit(size_t x) const
Limit matching length.
Definition: AddressMap.h:296
AddressMapConstraints at(Address x) const
Anchor at a certain address.
Definition: AddressMap.h:282
A Address
Type for addresses.
Definition: AddressMap.h:1009
AddressMapConstraints< const AddressMap > access(unsigned x) const
Constraint: required and prohibited access bits.
Definition: AddressMap.h:1088
An associative container whose keys are non-overlapping intervals.
Definition: IntervalMap.h:171
AddressMapConstraints< AddressMap > limit(size_t x)
Constraint: limit matched size.
Definition: AddressMap.h:1159
Optional< Address > next(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Minimum or maximum address that satisfies constraints.
Definition: AddressMap.h:1474
Value size() const
Size of interval.
Definition: Interval.h:257
AddressMapConstraints singleSegment() const
Limit matching to single segment.
Definition: AddressMap.h:354
AddressMapConstraints addressConstraints() const
Construct new constraints from existing address constraints.
Definition: AddressMap.h:456
bool neverMatches() const
Returns true if the constraint is not allowed to match anything.
Definition: AddressMap.h:396
AddressMapConstraints< const AddressMap > singleSegment() const
Constraint: single segment.
Definition: AddressMap.h:1260
bool isEmpty() const
True if interval is empty.
Definition: Interval.h:197
Super::ConstIntervalIterator ConstIntervalIterator
Iterates over address intervals in the map.
Definition: AddressMap.h:1016
Value & value()
Value part of key/value node.
Definition: Sawyer/Map.h:105
AddressMapConstraints< AddressMap > atOrAfter(Address x)
Constraint: address lower bound.
Definition: AddressMap.h:1172
void prune(const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Prune away addresses that match constraints.
Definition: AddressMap.h:1805
Base class for traversals.
Definition: AddressMap.h:1592
AddressMapConstraints< AddressMap > segmentPredicate(SegmentPredicate< Address, Value > *p)
Constraint: arbitrary segment constraint.
Definition: AddressMap.h:1276
AddressMapConstraints substr(const std::string &s) const
Require certain segment names.
Definition: AddressMap.h:262
T Value
Type of data stored in the address space.
Definition: AddressMap.h:1010
boost::iterator_range< SegmentIterator > segments()
Iterator range for all segments.
Definition: AddressMap.h:1346
AddressMapConstraints segmentPredicate(SegmentPredicate< Address, Value > *p) const
Limit segments.
Definition: AddressMap.h:361
AddressMapConstraints< const AddressMap > at(Address x) const
Constraint: anchor point.
Definition: AddressMap.h:1115
AddressMapConstraints< AddressMap > access(unsigned x)
Constraint: required and prohibited access bits.
Definition: AddressMap.h:1091
AddressMapConstraints< const AddressMap > before(Address x) const
Constraint: address upper bound.
Definition: AddressMap.h:1247
virtual Address available(Address address) const =0
Distance to end of buffer.
boost::iterator_range< ConstNodeIterator > nodes() const
Iterator range for nodes.
Definition: AddressMap.h:1395
AddressMapConstraints any() const
No constraints.
Definition: AddressMap.h:270
Buffer< A, T >::Ptr buffer() const
Property: buffer.
boost::iterator_range< ConstSegmentIterator > segments() const
Iterator range for all segments.
Definition: AddressMap.h:1347
Sawyer::Container::Interval< Address > write(const std::vector< Value > &buf, const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Writes data from the supplied buffer.
Definition: AddressMap.h:1788
AddressMapConstraints< const AddressMap > prohibit(unsigned x) const
Constraint: prohibited access bits.
Definition: AddressMap.h:1074
bool isContaining(const Interval &other) const
Containment predicate.
Definition: Interval.h:216
A homogeneous interval of an address space.
AddressMapConstraints< AddressMap > before(Address x)
Constraint: address upper bound.
Definition: AddressMap.h:1250
AddressSegment< A, T > Segment
Type of segments stored by this map.
Definition: AddressMap.h:1011
AddressMapConstraints< const AddressMap > atOrBefore(Address x) const
Constraint: address upper bound.
Definition: AddressMap.h:1182
Super::ValueIterator SegmentIterator
Iterates over segments in the map.
Definition: AddressMap.h:1014
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.
Definition: AddressMap.h:1542
AddressMapConstraints< AddressMap > singleSegment()
Constraint: single segment.
Definition: AddressMap.h:1263
Interval::Value size() const
Returns the number of values represented by this container.
Definition: IntervalMap.h:681
bool isEmpty() const
Determine if the container is empty.
Definition: IntervalMap.h:665
const Optional< Address > & greatest() const
Greatest possible address.
Definition: AddressMap.h:427
void traverse(Visitor &visitor, const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Invoke a function on each address interval.
Definition: AddressMap.h:1646
AddressMapConstraints< const AddressMap > require(unsigned x) const
Constraint: required access bits.
Definition: AddressMap.h:1061
A container holding a set of values.
Definition: IntervalSet.h:55
AddressMapConstraints within(const Sawyer::Container::Interval< Address > &x) const
Limit addresses.
Definition: AddressMap.h:329
boost::iterator_range< ConstSegmentIterator > segments(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Segments that overlap with constraints.
Definition: AddressMap.h:1370
void insert(const Interval2 &interval)
Insert specified values.
Definition: IntervalSet.h:532
Super::ConstValueIterator ConstSegmentIterator
Iterators over segments in the map.
Definition: AddressMap.h:1015
Reference-counting intrusive smart pointer.
Definition: SharedPointer.h:68
BitVector & fromInteger(const BitRange &range, boost::uint64_t value)
Obtain bits from an integer.
Definition: BitVector.h:1306
Name space for the entire library.
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:157
Sawyer::Container::Interval< Address > write(const Value *buf, const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Writes data from the supplied buffer.
Definition: AddressMap.h:1751
AddressInterval anchored() const
Returns the anchor points.
Definition: AddressMap.h:409
AddressMapConstraints< AddressMap > require(unsigned x)
Constraint: required access bits.
Definition: AddressMap.h:1064
bool exists(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Determines if an address exists with the specified constraints.
Definition: AddressMap.h:1504
const std::string & substr() const
Section name substring.
Definition: AddressMap.h:389
friend std::ostream & operator<<(std::ostream &out, const AddressMapConstraints &x)
Print constraints in a human readable form.
Definition: AddressMap.h:234
AddressMapConstraints< AddressMap > baseSize(Address base, Address size)
Constraint: address lower and upper bounds.
Definition: AddressMap.h:1224
void traverse(Functor &functor, const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Invoke a function on each address interval.
Definition: AddressMap.h:1622
void checkConsistency() const
Check map consistency.
Definition: AddressMap.h:1314
AddressMapConstraints< AddressMap > within(Address x, Address y)
Constraint: address lower and upper bounds.
Definition: AddressMap.h:1211
const Callbacks< SegmentPredicate< Address, Value > * > segmentPredicates() const
Returns the segment predicates.
Definition: AddressMap.h:437
T least() const
Returns lower limit.
Definition: Interval.h:185
Sawyer::Container::Interval< Address > read(Value *buf, const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Reads data into the supplied buffer.
Definition: AddressMap.h:1690
const std::string & name() const
Property: name.
AddressMapConstraints< AddressMap > within(const Sawyer::Container::Interval< Address > &x)
Constraint: address lower and upper bounds.
Definition: AddressMap.h:1198
AddressMapConstraints atOrAfter(Address least) const
Limit addresses.
Definition: AddressMap.h:303
unsigned accessibility() const
Property: access rights.
AddressMapConstraints< const AddressMap > any() const
Constraint: matches anything.
Definition: AddressMap.h:1286
AddressMapConstraints none() const
Constraints that match nothing.
Definition: AddressMap.h:275
Bidirectional iterator over values.
Definition: Sawyer/Map.h:232
AddressMapConstraints within(Address lo, Address hi) const
Limit addresses.
Definition: AddressMap.h:334
AddressMapConstraints< const AddressMap > baseSize(Address base, Address size) const
Constraint: address lower and upper bounds.
Definition: AddressMap.h:1221
AddressMapConstraints< AddressMap > atOrBefore(Address x)
Constraint: address upper bound.
Definition: AddressMap.h:1185
void insert(Interval key, Value value, bool makeHole=true)
Insert a key/value pair.
Definition: IntervalMap.h:838
unsigned prohibited() const
Accessibility bits that are required to be clear.
Definition: AddressMap.h:384
A mapping from address space to values.
Definition: AddressMap.h:1004
static Interval whole()
Construct an interval that covers the entire domain.
Definition: Interval.h:167
AddressMapConstraints< AddressMap > at(const Sawyer::Container::Interval< Address > &x)
Constraint: anchored interval.
Definition: AddressMap.h:1145
AddressMapConstraints access(unsigned bits) const
Require and prohibit certain access permissions.
Definition: AddressMap.h:257
static Interval hull(T v1, T v2)
Construct an interval from two endpoints.
Definition: Interval.h:150
Super::Node Node
Storage node containing interval/segment pair.
Definition: AddressMap.h:1013
ConstNodeIterator findNode(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Find node containing address.
Definition: AddressMap.h:1513
AddressMapConstraints< AddressMap > after(Address x)
Constraint: address lower bound.
Definition: AddressMap.h:1237
Sawyer::Container::Interval< Address > read(std::vector< Value > &buf, const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Reads data into the supplied buffer.
Definition: AddressMap.h:1713
void changeAccess(unsigned requiredAccess, unsigned prohibitedAccess, const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Change access bits for addresses that match constraints.
Definition: AddressMap.h:1866
Base class for all buffers.
Definition: Buffer.h:25
AddressMap * map() const
Returns a pointer to the memory map for this constraint object.
Definition: AddressMap.h:442
size_t limit() const
Size limit.
Definition: AddressMap.h:415
AddressMapConstraints< const AddressMap > within(const Sawyer::Container::Interval< Address > &x) const
Constraint: address lower and upper bounds.
Definition: AddressMap.h:1195
bool isAnchored() const
Determines whether constraints are anchored to an address.
Definition: AddressMap.h:401
AddressMapConstraints after(Address x) const
Limit addresses.
Definition: AddressMap.h:344
AddressMapConstraints require(unsigned bits) const
Require certain access permissions.
Definition: AddressMap.h:243
const Key & key() const
Key part of key/value node.
Definition: Sawyer/Map.h:98
AddressMapConstraints< const AddressMap > segmentPredicate(SegmentPredicate< Address, Value > *p) const
Constraint: arbitrary segment constraint.
Definition: AddressMap.h:1273
boost::iterator_range< NodeIterator > nodes()
Iterators for traversing nodes.
Definition: IntervalMap.h:283
AddressMapConstraints prohibit(unsigned bits) const
Prohibit certain access permissions.
Definition: AddressMap.h:250
Bidirectional iterator over values.
Definition: Sawyer/Map.h:254
Sawyer::Container::Interval< Address > unmapped(Address boundary, MatchFlags flags=0) const
Find unmapped interval.
Definition: AddressMap.h:1529
Constraints are used to select addresses from a memory map.
Definition: AddressMap.h:80
AddressMapConstraints before(Address x) const
Limit addreses.
Definition: AddressMap.h:349
AddressMapConstraints baseSize(Address base, Address size) const
Limit addresses.
Definition: AddressMap.h:339
AddressMapConstraints< AddressMap > none()
Constraint: matches nothing.
Definition: AddressMap.h:1302
boost::iterator_range< ConstIntervalIterator > intervals() const
Iterator range for all intervals actually stored by this set.
Definition: IntervalSet.h:225
AddressMapConstraints(AddressMap *map)
Construct a constraint that matches everything.
Definition: AddressMap.h:101
bool isSingleSegment() const
Returns true if the single-segment constraint is set.
Definition: AddressMap.h:432
Super::ConstNodeIterator ConstNodeIterator
Iterates over address interval/segment pairs in the map.
Definition: AddressMap.h:1018
A offset() const
Property: buffer offset.
boost::iterator_range< NodeIterator > nodes()
Iterator range for nodes.
Definition: AddressMap.h:1394
AddressMapConstraints atOrBefore(Address greatest) const
Limit addresses.
Definition: AddressMap.h:316
Super::NodeIterator NodeIterator
Iterates over address interval, segment pairs in the map.
Definition: AddressMap.h:1017
AddressMapConstraints< AddressMap > substr(const std::string &x)
Constraint: segment name substring.
Definition: AddressMap.h:1104
AddressMapConstraints< const AddressMap > atOrAfter(Address x) const
Constraint: address lower bound.
Definition: AddressMap.h:1169
void keep(const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Keep only addresses that match constraints.
Definition: AddressMap.h:1832
Sawyer::Container::Interval< Address > available(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Adress interval that satisfies constraints.
Definition: AddressMap.h:1488
Bidirectional iterator over keys.
Definition: Sawyer/Map.h:207
AddressMapConstraints< const AddressMap > at(const Sawyer::Container::Interval< Address > &x) const
Constraint: anchored interval.
Definition: AddressMap.h:1142
bool hasNonAddressConstraints() const
Determines whether non-address constraints are present.
Definition: AddressMap.h:448
AddressMapConstraints< const AddressMap > after(Address x) const
Constraint: address lower bound.
Definition: AddressMap.h:1234
NodeIterator lowerBound(const typename Interval::Value &scalar)
Find the first node whose interval ends at or above the specified scalar key.
Definition: IntervalMap.h:308
AddressMapConstraints at(const Sawyer::Container::Interval< Address > &x) const
Anchor at a certain interval.
Definition: AddressMap.h:289
AddressMapConstraints< const AddressMap > none() const
Constraint: matches nothing.
Definition: AddressMap.h:1299
Represents no value.
Definition: Optional.h:32
T greatest() const
Returns upper limit.
Definition: Interval.h:191
void traverse(Functor &functor, const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Invoke a function on each address interval.
Definition: AddressMap.h:1633
AddressMapConstraints< const AddressMap > within(Address x, Address y) const
Constraint: address lower and upper bounds.
Definition: AddressMap.h:1208
Interval firstUnmapped(typename Interval::Value minAddr) const
Find the first unmapped region.
Definition: IntervalMap.h:546
AddressMapConstraints< const AddressMap > limit(size_t x) const
Constraint: limit matched size.
Definition: AddressMap.h:1156
Address nSegments() const
Number of segments contained in the map.
Definition: AddressMap.h:1339
void print(std::ostream &out) const
Print constraints in a human readable form.
Definition: AddressMap.h:160
void traverse(Visitor &visitor, const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Invoke a function on each address interval.
Definition: AddressMap.h:1643
AddressMapConstraints< AddressMap > any()
Constraint: matches anything.
Definition: AddressMap.h:1289
AddressMapConstraints< AddressMap > prohibit(unsigned x)
Constraint: prohibited access bits.
Definition: AddressMap.h:1077
boost::iterator_range< SegmentIterator > segments(const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Iterator range for all segments.
Definition: AddressMap.h:1379
AddressMapConstraints< AddressMap > at(Address x)
Constraint: anchor point.
Definition: AddressMap.h:1118
std::string toHex(const BitRange &range) const
Convert to a hexadecimal string.
Definition: BitVector.h:1249
boost::iterator_range< ConstNodeIterator > nodes(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Nodes that overlap with constraints.
Definition: AddressMap.h:1418
Type for stored nodes.
Definition: Sawyer/Map.h:89
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:180
AddressMap(const AddressMap &other, bool copyOnWrite=false)
Copy constructor.
Definition: AddressMap.h:1047
AddressMap()
Constructs an empty address map.
Definition: AddressMap.h:1030