ROSE  0.9.9.109
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 namespace Sawyer {
31 namespace Container {
32 
33 template<class AddressMap>
35  typedef typename AddressMap::NodeIterator NodeIterator;
37 };
38 
39 template<class AddressMap>
43 };
44 
46 typedef unsigned MatchFlags;
47 static const MatchFlags MATCH_BACKWARD = 0x00000001;
48 static const MatchFlags MATCH_CONTIGUOUS = 0x00000002;
49 static const MatchFlags MATCH_NONCONTIGUOUS = 0x00000004;
50 static const MatchFlags MATCH_WHOLE = 0x00000008;
54 template<class A, class T>
56 public:
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 
75 template<typename AddressMap>
77 public:
78  typedef typename AddressMap::Address Address;
79  typedef typename AddressMap::Value Value;
81 private:
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
95 public:
98  : map_(map), never_(false), maxSize_(size_t(-1)), singleSegment_(false), requiredAccess_(0), prohibitedAccess_(0) {}
99 
100  // Implicitly construct constraints for a const AddressMap from a non-const address map.
101  operator AddressMapConstraints<const AddressMap>() const {
103  if (neverMatches())
104  cc = cc.none();
105  if (isAnchored()) {
106  if (anchored().isSingleton()) {
107  cc = cc.at(anchored().least());
108  } else {
109  cc = cc.at(anchored());
110  }
111  }
112  if (least())
113  cc = cc.atOrAfter(*least());
114  if (greatest())
115  cc = cc.atOrBefore(*greatest());
116  cc = cc.limit(limit());
117  if (isSingleSegment())
118  cc = cc.singleSegment();
119  cc = cc.require(required());
120  cc = cc.prohibit(prohibited());
121  cc = cc.substr(substr());
122  cc = cc.segmentPredicates(segmentPredicates());
123  return cc;
124  }
125 
127  void print(std::ostream &out) const {
128  out <<"{map=" <<map_;
129  if (never_)
130  out <<", never";
131  if (least_)
132  out <<", least=" <<*least_;
133  if (greatest_)
134  out <<", greatest=" <<*greatest_;
135  if (anchored_) {
136  out <<", anchored=";
137  AddressInterval a = *anchored_;
138  if (a.isEmpty()) {
139  out <<"empty";
140  } else if (a.least()==a.greatest()) {
141  out <<a.least();
142  } else {
143  out <<"{" <<a.least() <<".." <<a.greatest() <<"}";
144  }
145  }
146  if (maxSize_ != size_t(-1))
147  out <<", limit=" <<maxSize_;
148  if (singleSegment_)
149  out <<", single-segment";
150  if (requiredAccess_!=0) {
151  out <<", required="
152  <<((requiredAccess_ & Access::READABLE) ? "r" : "")
153  <<((requiredAccess_ & Access::WRITABLE) ? "w" : "")
154  <<((requiredAccess_ & Access::EXECUTABLE) ? "x" : "")
155  <<((requiredAccess_ & Access::IMMUTABLE) ? "i" : "");
156  unsigned other = requiredAccess_ & ~(Access::READABLE|Access::WRITABLE|Access::EXECUTABLE|Access::IMMUTABLE);
157  if (other)
158  out <<"+0x" <<BitVector(8*sizeof requiredAccess_).fromInteger(other).toHex();
159  }
160  if (prohibitedAccess_!=0) {
161  out <<", required="
162  <<((prohibitedAccess_ & Access::READABLE) ? "r" : "")
163  <<((prohibitedAccess_ & Access::WRITABLE) ? "w" : "")
164  <<((prohibitedAccess_ & Access::EXECUTABLE) ? "x" : "")
165  <<((prohibitedAccess_ & Access::IMMUTABLE) ? "i" : "");
166  unsigned other = prohibitedAccess_ & ~(Access::READABLE|Access::WRITABLE|Access::EXECUTABLE|Access::IMMUTABLE);
167  if (other)
168  out <<"+0x" <<BitVector(8*sizeof prohibitedAccess_).fromInteger(other).toHex();
169  }
170  if (!nameSubstring_.empty()) {
171  out <<", substr=\"";
172  BOOST_FOREACH (char ch, nameSubstring_) {
173  switch (ch) {
174  case '\a': out <<"\\a"; break;
175  case '\b': out <<"\\b"; break;
176  case '\t': out <<"\\t"; break;
177  case '\n': out <<"\\n"; break;
178  case '\v': out <<"\\v"; break;
179  case '\f': out <<"\\f"; break;
180  case '\r': out <<"\\r"; break;
181  case '\"': out <<"\\\""; break;
182  case '\\': out <<"\\\\"; break;
183  default:
184  if (isprint(ch)) {
185  out <<ch;
186  } else {
187  char buf[8];
188  sprintf(buf, "\\%03o", (unsigned)(unsigned char)ch);
189  out <<buf;
190  }
191  break;
192  }
193  }
194  }
195  if (!segmentPredicates_.isEmpty())
196  out <<", user-def";
197  out <<"}";
198  }
199 
201  friend std::ostream& operator<<(std::ostream &out, const AddressMapConstraints &x) {
202  x.print(out);
203  return out;
204  }
205 
207  // Constraint modifiers
208 public:
210  AddressMapConstraints require(unsigned bits) const {
211  AddressMapConstraints retval = *this;
212  retval.requiredAccess_ |= bits;
213  return retval;
214  }
215 
217  AddressMapConstraints prohibit(unsigned bits) const {
218  AddressMapConstraints retval = *this;
219  retval.prohibitedAccess_ |= bits;
220  return retval;
221  }
222 
224  AddressMapConstraints access(unsigned bits) const {
225  return require(bits).prohibit(~bits);
226  }
227 
229  AddressMapConstraints substr(const std::string &s) const {
230  ASSERT_require(nameSubstring_.empty() || nameSubstring_==s);// substring conjunction not supported
231  AddressMapConstraints retval = *this;
232  retval.nameSubstring_ = s;
233  return retval;
234  }
235 
238  return *this;
239  }
240 
243  AddressMapConstraints retval = *this;
244  retval.never_ = true;
245  return retval;
246  }
247 
249  AddressMapConstraints at(Address x) const {
250  AddressMapConstraints retval = *this;
251  retval.anchored_ = anchored_ ? *anchored_ & AddressInterval(x) : AddressInterval(x);
252  return retval.anchored_->isEmpty() ? retval.none() : retval;
253  }
254 
257  AddressMapConstraints retval = *this;
258  retval.anchored_ = anchored_ ? *anchored_ & x : x;
259  return retval.anchored_->isEmpty() ? retval.none() : retval.atOrAfter(x.least()).atOrBefore(x.greatest());
260  }
261 
263  AddressMapConstraints limit(size_t x) const {
264  AddressMapConstraints retval = *this;
265  retval.maxSize_ = std::min(maxSize_, x);
266  return 0 == retval.maxSize_ ? retval.none() : retval;
267  }
268 
271  AddressMapConstraints retval = *this;
272  if (least_) {
273  retval.least_ = std::max(*least_, least);
274  } else {
275  retval.least_ = least;
276  }
277  if (greatest_ && *greatest_ < *retval.least_)
278  retval.none();
279  return retval;
280  }
281 
284  AddressMapConstraints retval = *this;
285  if (greatest_) {
286  retval.greatest_ = std::min(*greatest_, greatest);
287  } else {
288  retval.greatest_ = greatest;
289  }
290  if (least_ && *least_ > *retval.greatest_)
291  retval.none();
292  return retval;
293  }
294 
297  return x.isEmpty() ? none() : atOrAfter(x.least()).atOrBefore(x.greatest());
298  }
299 
301  AddressMapConstraints within(Address lo, Address hi) const {
302  return lo<=hi ? within(Sawyer::Container::Interval<Address>::hull(lo, hi)) : none();
303  }
304 
306  AddressMapConstraints baseSize(Address base, Address size) const {
307  return size>0 ? atOrAfter(base).atOrBefore(base+size-1) : none();
308  }
309 
311  AddressMapConstraints after(Address x) const {
312  return x==boost::integer_traits<Address>::const_max ? none() : atOrAfter(x+1);
313  }
314 
316  AddressMapConstraints before(Address x) const {
317  return x==boost::integer_traits<Address>::const_min ? none() : atOrBefore(x-1);
318  }
319 
322  AddressMapConstraints retval = *this;
323  retval.singleSegment_ = true;
324  return retval;
325  }
326 
329  if (!p)
330  return none();
331  AddressMapConstraints retval = *this;
332  retval.segmentPredicates_.append(p);
333  return retval;
334  }
335 
337  AddressMapConstraints retval = *this;
338  retval.segmentPredicates_.append(predicates);
339  return retval;
340  }
341 
343  // Constraint queries
344 public:
346  unsigned required() const {
347  return requiredAccess_;
348  }
349 
351  unsigned prohibited() const {
352  return prohibitedAccess_;
353  }
354 
356  const std::string& substr() const {
357  return nameSubstring_;
358  }
359 
363  bool neverMatches() const {
364  return never_;
365  }
366 
368  bool isAnchored() const {
369  return anchored_;
370  }
371 
376  AddressInterval anchored() const {
377  ASSERT_require(isAnchored());
378  return *anchored_;
379  }
380 
382  size_t limit() const {
383  return maxSize_;
384  }
385 
388  const Optional<Address>& least() const {
389  return least_;
390  }
391 
394  const Optional<Address>& greatest() const {
395  return greatest_;
396  }
397 
399  bool isSingleSegment() const {
400  return singleSegment_;
401  }
402 
405  return segmentPredicates_;
406  }
407 
409  AddressMap* map() const {
410  return map_;
411  }
412 
416  return (!never_ &&
417  (requiredAccess_ || prohibitedAccess_ || !nameSubstring_.empty() || maxSize_!=size_t(-1) ||
418  singleSegment_ || !segmentPredicates_.isEmpty()));
419  }
420 
424  AddressMapConstraints c(map_);
425  c.least_ = least_;
426  c.greatest_ = greatest_;
427  c.anchored_ = anchored_;
428  c.maxSize_ = maxSize_;
429  return c;
430  }
431 
433  // Methods that directly call the AddressMap
434 public:
435  boost::iterator_range<typename AddressMapTraits<AddressMap>::NodeIterator>
436  nodes(MatchFlags flags=0) const {
437  return map_->nodes(*this, flags);
438  }
439 
440  boost::iterator_range<typename AddressMapTraits<AddressMap>::SegmentIterator>
441  segments(MatchFlags flags=0) const {
442  return map_->segments(*this, flags);
443  }
444 
445  Optional<typename AddressMap::Address>
446  next(MatchFlags flags=0) const {
447  return map_->next(*this, flags);
448  }
449 
451  available(MatchFlags flags=0) const {
452  return map_->available(*this, flags);
453  }
454 
455  bool
456  exists(MatchFlags flags=0) const {
457  return map_->exists(*this, flags);
458  }
459 
460  typename AddressMapTraits<AddressMap>::NodeIterator
461  findNode(MatchFlags flags=0) const {
462  return map_->findNode(*this, flags);
463  }
464 
465  template<typename Functor>
466  void
467  traverse(Functor &functor, MatchFlags flags=0) const {
468  return map_->traverse(functor, *this, flags);
469  }
470  void
471  traverse(typename AddressMap::Visitor &visitor, MatchFlags flags=0) const {
472  return map_->template traverse<typename AddressMap::Visitor>(visitor, *this, flags);
473  }
474 
476  read(typename AddressMap::Value *buf /*out*/, MatchFlags flags=0) const {
477  return map_->read(buf, *this, flags);
478  }
479 
481  read(std::vector<typename AddressMap::Value> &buf /*out*/,
482  MatchFlags flags=0) const {
483  return map_->read(buf, *this, flags);
484  }
485 
487  write(const typename AddressMap::Value *buf, MatchFlags flags=0) const {
488  return map_->write(buf, *this, flags);
489  }
490 
492  write(const std::vector<typename AddressMap::Value> &buf, MatchFlags flags=0) {
493  return map_->write(buf, *this, flags);
494  }
495 
496  void
497  prune(MatchFlags flags=0) const {
498  return map_->prune(*this, flags);
499  }
500 
501  void
502  keep(MatchFlags flags=0) const {
503  return map_->keep(*this, flags);
504  }
505 
506  void
507  changeAccess(unsigned requiredAccess, unsigned prohibitedAccess, MatchFlags flags=0) const {
508  return map_->changeAccess(requiredAccess, prohibitedAccess, *this, flags);
509  }
510 };
511 
513 // Implementation details
515 namespace AddressMapImpl {
516 
517 // Used internally to split and merge segments
518 template<class A, class T>
520 public:
521  typedef A Address;
522  typedef T Value;
524 
525 private:
526  friend class boost::serialization::access;
527 
528  template<class S>
529  void serialize(S&, const unsigned /*version*/) {
530  // no data to serialize here
531  }
532 
533 public:
534  bool merge(const Sawyer::Container::Interval<Address> &leftInterval, Segment &leftSegment,
535  const Sawyer::Container::Interval<Address> &rightInterval, Segment &rightSegment) {
536  ASSERT_forbid(leftInterval.isEmpty());
537  ASSERT_always_forbid(rightInterval.isEmpty()); // so rightInterval is always used
538  ASSERT_require(leftInterval.greatest() + 1 == rightInterval.least());
539  return (leftSegment.accessibility() == rightSegment.accessibility() &&
540  leftSegment.name() == rightSegment.name() &&
541  leftSegment.buffer() == rightSegment.buffer() &&
542  leftSegment.offset() + leftInterval.size() == rightSegment.offset());
543  }
544 
545  Segment split(const Sawyer::Container::Interval<Address> &interval, Segment &segment, Address splitPoint) {
546  ASSERT_forbid(interval.isEmpty());
547  ASSERT_require(interval.isContaining(splitPoint));
548  Segment right = segment;
549  right.offset(segment.offset() + splitPoint - interval.least());
550  return right;
551  }
552 
553  void truncate(const Sawyer::Container::Interval<Address> &interval, Segment &/*segment*/, Address splitPoint) {
554  ASSERT_always_forbid(interval.isEmpty()); // so interval is always used
555  ASSERT_always_require(interval.isContaining(splitPoint)); // ditto for splitPoint
556  }
557 };
558 
559 // The results for matching constraints
560 template<class AddressMap>
562  typedef typename AddressMap::Address Address;
565  boost::iterator_range<NodeIterator> nodes_;
566 };
567 
568 // Finds the minimum possible address and node iterator for the specified constraints in this map and returns that
569 // iterator. Returns the end iterator if the constraints match no address. If a non-end iterator is returned then minAddr
570 // is adjusted to be the minimum address that satisfies the constraint (it will be an address within the returned node, but
571 // not necessarily the least address for the node). If useAnchor is set and the constraints specify an anchor, then the
572 // anchor address must be present in the map and satisfy any address constraints that might also be present.
573 template<class AddressMap>
575 constraintLowerBound(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, bool useAnchor,
576  typename AddressMap::Address &minAddr) {
577  typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
578  if (amap.isEmpty() || c.neverMatches())
579  return amap.nodes().end();
580 
581  if (useAnchor && c.isAnchored()) { // forward matching if useAnchor is set
582  if ((c.least() && *c.least() > c.anchored().least()) || (c.greatest() && *c.greatest() < c.anchored().greatest()))
583  return amap.nodes().end(); // anchor is outside of allowed interval
584  Iterator lb = amap.lowerBound(c.anchored().least());
585  if (lb==amap.nodes().end() || c.anchored().least() < lb->key().least())
586  return amap.nodes().end(); // anchor is not present in this map
587  minAddr = c.anchored().least();
588  return lb;
589  }
590 
591  if (c.least()) {
592  Iterator lb = amap.lowerBound(*c.least());
593  if (lb==amap.nodes().end())
594  return lb; // least is above all segments
595  minAddr = std::max(*c.least(), lb->key().least());
596  return lb;
597  }
598 
599  Iterator lb = amap.nodes().begin();
600  if (lb!=amap.nodes().end())
601  minAddr = lb->key().least();
602  return lb;
603 }
604 
605 // Finds the maximum possible address and node for the specified constraints in this map, and returns an iterator to the
606 // following node. Returns the begin iterator if the constraints match no address. If a non-begin iterator is returned
607 // then maxAddr is adjusted to be the maximum address that satisfies the constraint (it will be an address that belongs to
608 // the node immediately prior to the one pointed to by the returned iterator, but not necessarily the greatest address for
609 // that node). If useAnchor is set and the constraints specify an anchor, then the anchor address must be present in the
610 // map and satisfy any address constraints that might also be present.
611 template<class AddressMap>
612 typename AddressMapTraits<AddressMap>::NodeIterator
613 constraintUpperBound(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, bool useAnchor,
614  typename AddressMap::Address &maxAddr) {
615  typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
616  if (amap.isEmpty() || c.neverMatches())
617  return amap.nodes().begin();
618 
619  if (useAnchor && c.isAnchored()) { // backward matching if useAnchor is set
620  if ((c.least() && *c.least() > c.anchored().least()) || (c.greatest() && *c.greatest() < c.anchored().greatest()))
621  return amap.nodes().begin(); // anchor is outside allowed interval
622  Iterator ub = amap.findPrior(c.anchored().greatest());
623  if (ub==amap.nodes().end() || c.anchored().greatest() > ub->key().greatest())
624  return amap.nodes().begin(); // anchor is not present in this map
625  maxAddr = c.anchored().greatest();
626  return ++ub; // return node after the one containing the anchor
627  }
628 
629  if (c.greatest()) {
630  Iterator ub = amap.findPrior(*c.greatest());
631  if (ub==amap.nodes().end())
632  return amap.nodes().begin(); // greatest is below all segments
633  maxAddr = std::min(ub->key().greatest(), *c.greatest());
634  return ++ub; // return node after the one containing the maximum
635  }
636 
637  maxAddr = amap.hull().greatest();
638  return amap.nodes().end();
639 }
640 
641 // Returns true if the segment satisfies the non-address constraints in c.
642 template<class AddressMap>
643 bool
644 isSatisfied(const typename AddressMap::Node &node, const AddressMapConstraints<AddressMap> &c) {
645  typedef typename AddressMap::Address Address;
646  typedef typename AddressMap::Value Value;
647  typedef typename AddressMap::Segment Segment;
648  const Segment &segment = node.value();
649  if (!segment.isAccessible(c.required(), c.prohibited()))
650  return false; // wrong segment permissions
651  if (!boost::contains(segment.name(), c.substr()))
652  return false; // wrong segment name
653  if (!c.segmentPredicates().apply(true, typename SegmentPredicate<Address, Value>::Args(node.key(), node.value())))
654  return false; // user-supplied predicates failed
655  return true;
656 }
657 
658 // Matches constraints against contiguous addresses in a forward direction.
659 template<class AddressMap>
660 MatchedConstraints<AddressMap>
661 matchForward(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, MatchFlags flags) {
662  typedef typename AddressMap::Address Address;
663  typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
664  MatchedConstraints<AddressMap> retval;
665  retval.nodes_ = boost::iterator_range<Iterator>(amap.nodes().end(), amap.nodes().end());
666  if (c.neverMatches() || amap.isEmpty())
667  return retval;
668 
669  // Find a lower bound for the minimum address
670  Address minAddr = 0;
671  Iterator begin = constraintLowerBound(amap, c, true, minAddr /*out*/);
672  if (begin == amap.nodes().end())
673  return retval;
674 
675  // Find an upper bound for the maximum address.
676  Address maxAddr = 0;
677  Iterator end = constraintUpperBound(amap, c, false, maxAddr /*out*/);
678  if (end==amap.nodes().begin())
679  return retval;
680 
681  // Advance the lower-bound until it satisfies the other (non-address) constraints
682  while (begin!=end && !isSatisfied(*begin, c)) {
683  if (c.isAnchored())
684  return retval; // match is anchored to minAddr
685  ++begin;
686  }
687  if (begin==end)
688  return retval;
689  minAddr = std::max(minAddr, begin->key().least());
690 
691  // Iterate forward until the constraints are no longer satisfied
692  if ((flags & MATCH_CONTIGUOUS)!=0 || c.hasNonAddressConstraints()) {
693  Address addr = minAddr;
694  Iterator iter = begin;
695  size_t nElmtsFound = 0;
696  for (/*void*/; iter!=end; ++iter) {
697  if (iter!=begin) { // already tested the first node above
698  if (c.isSingleSegment())
699  break; // we crossed a segment boundary
700  if ((flags & MATCH_CONTIGUOUS)!=0 && addr+1 != iter->key().least())
701  break; // gap between segments
702  if (!isSatisfied(*iter, c)) {
703  if ((flags & MATCH_WHOLE)!=0)
704  return retval; // match is anchored to maxAddr
705  break; // segment does not satisfy constraints
706  }
707  }
708  size_t nElmtsHere = iter->key().greatest() + 1 - std::max(minAddr, iter->key().least());
709  if (nElmtsFound + nElmtsHere >= c.limit()) {
710  size_t nNeed = c.limit() - nElmtsFound;
711  addr = std::max(minAddr, iter->key().least()) + nNeed - 1;
712  ++iter;
713  break; // too many values
714  }
715  addr = iter->key().greatest();
716  nElmtsFound += nElmtsHere;
717  }
718  end = iter;
719  maxAddr = std::min(maxAddr, addr);
720  }
721 
722  // Build the result
723  retval.interval_ = Sawyer::Container::Interval<Address>::hull(minAddr, maxAddr);
724  retval.nodes_ = boost::iterator_range<Iterator>(begin, end);
725  return retval;
726 }
727 
728 // Matches constraints against contiguous addresses in a backward direction.
729 template<class AddressMap>
730 MatchedConstraints<AddressMap>
731 matchBackward(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, MatchFlags flags) {
732  typedef typename AddressMap::Address Address;
733  typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
734  MatchedConstraints<AddressMap> retval;
735  retval.nodes_ = boost::iterator_range<Iterator>(amap.nodes().end(), amap.nodes().end());
736  if (c.neverMatches() || amap.isEmpty())
737  return retval;
738 
739  // Find a lower bound for the minimum address
740  Address minAddr = 0;
741  Iterator begin = constraintLowerBound(amap, c, false, minAddr /*out*/);
742  if (begin == amap.nodes().end())
743  return retval;
744 
745  // Find an upper bound for the maximum address.
746  Address maxAddr = 0;
747  Iterator end = constraintUpperBound(amap, c, true, maxAddr /*out*/);
748  if (end==amap.nodes().begin())
749  return retval;
750 
751  // Decrement the upper bound until constraints are met. End always points to one-past the last matching node.
752  while (end!=begin) {
753  Iterator prev = end; --prev;
754  if (isSatisfied(*prev, c)) {
755  maxAddr = std::min(maxAddr, prev->key().greatest());
756  break;
757  }
758  if (c.isAnchored())
759  return retval; // match is anchored to maxAddr
760  end = prev;
761  }
762  if (end==begin)
763  return retval;
764 
765  // Iterate backward until the constraints are no longer satisfied. Within the loop, iter always points to on-past the
766  // node in question. When the loop exits, iter points to the first node satisfying constraints.
767  if ((flags & MATCH_CONTIGUOUS)!=0 || c.hasNonAddressConstraints()) {
768  Address addr = maxAddr;
769  Iterator iter = end;
770  size_t nElmtsFound = 0;
771  for (/*void*/; iter!=begin; --iter) {
772  Iterator prev = iter; --prev; // prev points to the node in question
773  if (iter!=end) { // already tested last node above
774  if (c.isSingleSegment())
775  break; // we crossed a segment boundary
776  if ((flags & MATCH_CONTIGUOUS)!=0 && prev->key().greatest()+1 != addr)
777  break; // gap between segments
778  if (!isSatisfied(*prev, c)) {
779  if ((flags & MATCH_WHOLE)!=0)
780  return retval; // match is anchored to minAddr
781  break; // segment does not satisfy constraints
782  }
783  }
784  size_t nElmtsHere = std::min(maxAddr, prev->key().greatest()) - prev->key().least() + 1;
785  if (nElmtsFound + nElmtsHere >= c.limit()) {
786  size_t nNeed = c.limit() - nElmtsFound;
787  addr = std::min(maxAddr, prev->key().greatest()) - nNeed + 1;
788  iter = prev;
789  break;
790  }
791  addr = prev->key().least();
792  nElmtsFound += nElmtsHere;
793  }
794  begin = iter; // iter points to first matching node
795  minAddr = std::max(minAddr, addr);
796  }
797 
798  // Build the result
799  retval.interval_ = Sawyer::Container::Interval<Address>::hull(minAddr, maxAddr);
800  retval.nodes_ = boost::iterator_range<Iterator>(begin, end);
801  return retval;
802 }
803 
804 // Match constraints forward or backward
805 template<class AddressMap>
806 MatchedConstraints<AddressMap>
807 matchConstraints(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, MatchFlags flags) {
808  if ((flags & MATCH_BACKWARD) != 0)
809  return matchBackward(amap, c, flags);
810  return matchForward(amap, c, flags);
811 }
812 
813 } // namespace
814 
815 
970 template<class A, class T = boost::uint8_t>
971 class AddressMap: public IntervalMap<Interval<A>, AddressSegment<A, T>, AddressMapImpl::SegmentMergePolicy<A, T> > {
972  // "Interval" is qualified to work around bug in Microsoft compilers. See doxygen note above.
974 
975 public:
976  typedef A Address;
977  typedef T Value;
978  typedef AddressSegment<A, T> Segment;
980  typedef typename Super::Node Node;
987 private:
988  friend class boost::serialization::access;
989 
990  template<class S>
991  void serialize(S &s, const unsigned /*version*/) {
992  s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Super);
993  }
994 
995 public:
998 
1014  AddressMap(const AddressMap &other, bool copyOnWrite=false): Super(other) {
1015  if (copyOnWrite) {
1016  BOOST_FOREACH (Segment &segment, this->values()) {
1017  if (const typename Buffer::Ptr &buffer = segment.buffer())
1018  buffer->copyOnWrite(true);
1019  }
1020  }
1021  }
1022 
1030  }
1033  }
1043  }
1046  }
1057  }
1059  return AddressMapConstraints<AddressMap>(this).access(x);
1060  }
1068  AddressMapConstraints<const AddressMap> substr(const std::string &x) const {
1070  }
1072  return AddressMapConstraints<AddressMap>(this).substr(x);
1073  }
1084  }
1086  return AddressMapConstraints<AddressMap>(this).at(x);
1087  }
1111  }
1113  return AddressMapConstraints<AddressMap>(this).at(x);
1114  }
1125  }
1127  return AddressMapConstraints<AddressMap>(this).limit(x);
1128  }
1138  }
1141  }
1151  }
1154  }
1164  }
1166  return AddressMapConstraints<AddressMap>(this).within(x);
1167  }
1175  AddressMapConstraints<const AddressMap> within(Address x, Address y) const {
1177  }
1179  return AddressMapConstraints<AddressMap>(this).within(x, y);
1180  }
1189  return AddressMapConstraints<const AddressMap>(this).baseSize(base, size);
1190  }
1192  return AddressMapConstraints<AddressMap>(this).baseSize(base, size);
1193  }
1203  }
1205  return AddressMapConstraints<AddressMap>(this).after(x);
1206  }
1216  }
1218  return AddressMapConstraints<AddressMap>(this).before(x);
1219  }
1229  }
1232  }
1242  }
1245  }
1255  }
1257  return AddressMapConstraints<AddressMap>(this);
1258  }
1268  }
1270  return AddressMapConstraints<AddressMap>(this).none();
1271  }
1281  void checkConsistency() const {
1282  BOOST_FOREACH (const Node &node, nodes()) {
1283  const Sawyer::Container::Interval<Address> &interval = node.key();
1284  const Segment &segment = node.value();
1285  if (segment.buffer()==NULL) {
1286  throw std::runtime_error("AddressMap null buffer for interval [" +
1287  boost::lexical_cast<std::string>(interval.least()) +
1288  "," + boost::lexical_cast<std::string>(interval.greatest()) + "]");
1289  }
1290  Address bufAvail = segment.buffer()->available(segment.offset());
1291  if (bufAvail < interval.size()) {
1292  throw std::runtime_error("AddressMap segment at [" + boost::lexical_cast<std::string>(interval.least()) +
1293  "," + boost::lexical_cast<std::string>(interval.greatest()) + "] points to only " +
1294  boost::lexical_cast<std::string>(bufAvail) + (1==bufAvail?" value":" values") +
1295  " but the interval size is " + boost::lexical_cast<std::string>(interval.size()));
1296  }
1297  }
1298  }
1299 
1306  Address nSegments() const { return this->nIntervals(); }
1307 
1313  boost::iterator_range<SegmentIterator> segments() { return this->values(); }
1314  boost::iterator_range<ConstSegmentIterator> segments() const { return this->values(); }
1315 
1336  boost::iterator_range<ConstSegmentIterator>
1337  segments(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1338  using namespace AddressMapImpl;
1339  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1340  flags |= MATCH_CONTIGUOUS;
1341  MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
1342  return boost::iterator_range<ConstSegmentIterator>(m.nodes_.begin(), m.nodes_.end());
1343  }
1344 
1345  boost::iterator_range<SegmentIterator>
1346  segments(const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1347  using namespace AddressMapImpl;
1348  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1349  flags |= MATCH_CONTIGUOUS;
1350  MatchedConstraints<AddressMap> m = matchConstraints(*this, c, flags);
1351  return boost::iterator_range<SegmentIterator>(m.nodes_);
1352  }
1361  boost::iterator_range<NodeIterator> nodes() { return Super::nodes(); }
1362  boost::iterator_range<ConstNodeIterator> nodes() const { return Super::nodes(); }
1384  boost::iterator_range<ConstNodeIterator>
1385  nodes(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1386  using namespace AddressMapImpl;
1387  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1388  flags |= MATCH_CONTIGUOUS;
1389  MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
1390  return m.nodes_;
1391  }
1392 
1393  boost::iterator_range<NodeIterator>
1394  nodes(const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1395  using namespace AddressMapImpl;
1396  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1397  flags |= MATCH_CONTIGUOUS;
1398  MatchedConstraints<AddressMap> m = matchConstraints(*this, c, flags);
1399  return m.nodes_;
1400  }
1441  next(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1442  using namespace AddressMapImpl;
1443  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1444  flags |= MATCH_CONTIGUOUS;
1445  MatchedConstraints<const AddressMap> m = matchConstraints(*this, c.limit(1), flags);
1446  return m.interval_.isEmpty() ? Optional<Address>() : Optional<Address>(m.interval_.least());
1447  }
1448 
1455  available(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1456  using namespace AddressMapImpl;
1457  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1458  flags |= MATCH_CONTIGUOUS;
1459  return matchConstraints(*this, c, flags).interval_;
1460  }
1461 
1471  bool exists(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1472  return next(c, flags);
1473  }
1474 
1480  ConstNodeIterator findNode(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1481  return nodes(c.limit(1), flags).begin();
1482  }
1483  NodeIterator findNode(const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1484  return nodes(c.limit(1), flags).begin();
1485  }
1496  unmapped(Address boundary, MatchFlags flags=0) const {
1497  return (flags & MATCH_BACKWARD) != 0 ? this->lastUnmapped(boundary) : this->firstUnmapped(boundary);
1498  }
1499 
1509  findFreeSpace(size_t nValues, size_t alignment=1,
1511  MatchFlags flags=0) const {
1513  ASSERT_forbid2(nValues == 0, "cannot determine if this is an overflow or intentional");
1514 
1515  if (restriction.isEmpty())
1516  return Nothing();
1517 
1518  if (0 == (flags & MATCH_BACKWARD)) {
1519  Address minAddr = restriction.least();
1520  while (minAddr <= restriction.greatest()) {
1521  Sawyer::Container::Interval<Address> interval = unmapped(minAddr, 0 /*forward*/);
1522  if (interval.isEmpty())
1523  return Nothing();
1524  minAddr = alignUp(interval.least(), alignment);
1525  Address maxAddr = minAddr + (nValues-1);
1526  if ((nValues <= interval.size() || 0==interval.size()/*overflow*/) &&
1527  minAddr >= interval.least()/*overflow*/ && maxAddr >= interval.least()/*overflow*/ &&
1528  maxAddr <= interval.greatest()) {
1529  return minAddr;
1530  }
1531  if (interval.greatest() == whole.greatest())
1532  return Nothing(); // to avoid overflow in next statement
1533  minAddr = interval.greatest() + 1;
1534  }
1535  return Nothing();
1536  }
1537 
1538  ASSERT_require((flags & MATCH_BACKWARD) != 0);
1539  Address maxAddr = restriction.greatest();
1540  while (maxAddr >= restriction.least()) {
1541  Sawyer::Container::Interval<Address> interval = unmapped(maxAddr, MATCH_BACKWARD);
1542  if (interval.isEmpty())
1543  return Nothing();
1544  Address minAddr = alignDown(interval.greatest() - (nValues-1), alignment);
1545  maxAddr = minAddr + (nValues-1);
1546  if ((nValues <= interval.size() || 0==interval.size()/*overflow*/) &&
1547  minAddr >= interval.least()/*overflow*/ && maxAddr >= interval.least()/*overflow*/ &&
1548  maxAddr <= interval.greatest()) {
1549  return minAddr;
1550  }
1551  if (interval.least() == whole.least())
1552  return Nothing(); // to avoid overflow in next statement
1553  maxAddr = interval.least() - 1;
1554  }
1555  return Nothing();
1556  }
1557 
1559  class Visitor {
1560  public:
1561  virtual ~Visitor() {}
1562  virtual bool operator()(const AddressMap&, const Sawyer::Container::Interval<Address>&) = 0;
1563  };
1564 
1588  template<typename Functor>
1589  void traverse(Functor &functor, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1590  using namespace AddressMapImpl;
1591  MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
1592  BOOST_FOREACH (const Node &node, m.nodes_) {
1593  Sawyer::Container::Interval<Address> part = m.interval_ & node.key();
1594  if (!functor(*this, part))
1595  return;
1596  }
1597  return;
1598  }
1599  template<typename Functor>
1600  void traverse(Functor &functor, const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1601  using namespace AddressMapImpl;
1602  MatchedConstraints<AddressMap> m = matchConstraints(*this, c, flags);
1603  BOOST_FOREACH (const Node &node, m.nodes_) {
1604  Sawyer::Container::Interval<Address> part = m.interval_ & node.key();
1605  if (!functor(*this, part))
1606  return;
1607  }
1608  return;
1609  }
1610  void traverse(Visitor &visitor, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1611  traverse<Visitor>(visitor, c, flags);
1612  }
1613  void traverse(Visitor &visitor, const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1614  traverse<Visitor>(visitor, c, flags);
1615  }
1657  read(Value *buf /*out*/, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1658  using namespace AddressMapImpl;
1659  ASSERT_require2(0 == (flags & MATCH_NONCONTIGUOUS), "only contiguous addresses can be read");
1660  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1661  flags |= MATCH_CONTIGUOUS;
1662  MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
1663  if (buf) {
1664  BOOST_FOREACH (const Node &node, m.nodes_) {
1665  Sawyer::Container::Interval<Address> part = m.interval_ & node.key(); // part of segment to read
1666  ASSERT_forbid(part.isEmpty());
1667  Address bufferOffset = part.least() - node.key().least() + node.value().offset();
1668  Address nValues = node.value().buffer()->read(buf, bufferOffset, part.size());
1669  if (nValues != part.size()) {
1670  checkConsistency();
1671  ASSERT_not_reachable("something is wrong with the memory map");
1672  }
1673  buf += nValues;
1674  }
1675  }
1676  return m.interval_;
1677  }
1678 
1680  read(std::vector<Value> &buf /*out*/, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
1681  return buf.empty() ? Sawyer::Container::Interval<Address>() : read(&buf[0], c.limit(buf.size()), flags);
1682  }
1718  write(const Value *buf, const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1719  using namespace AddressMapImpl;
1720  ASSERT_require2(0 == (flags & MATCH_NONCONTIGUOUS), "only contiguous addresses can be written");
1721  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1722  flags |= MATCH_CONTIGUOUS;
1723  MatchedConstraints<AddressMap> m = matchConstraints(*this, c.prohibit(Access::IMMUTABLE), flags);
1724  if (buf) {
1725  BOOST_FOREACH (Node &node, m.nodes_) {
1726  Segment &segment = node.value();
1727  Sawyer::Container::Interval<Address> part = m.interval_ & node.key(); // part of segment to write
1728  ASSERT_forbid(part.isEmpty());
1729  typename Buffer::Ptr buffer = segment.buffer();
1730  ASSERT_not_null(buffer);
1731 
1732  if (buffer->copyOnWrite()) {
1733  typename Buffer::Ptr newBuffer = buffer->copy(); // copyOnWrite is cleared in newBuffer
1734  ASSERT_not_null(newBuffer);
1735  for (NodeIterator iter=this->lowerBound(node.key().least()); iter!=nodes().end(); ++iter) {
1736  if (iter->value().buffer() == buffer)
1737  iter->value().buffer(newBuffer);
1738  }
1739  buffer = newBuffer;
1740  }
1741 
1742  Address bufferOffset = part.least() - node.key().least() + segment.offset();
1743  Address nValues = buffer->write(buf, bufferOffset, part.size());
1744  if (nValues != part.size()) {
1745  checkConsistency();
1746  ASSERT_not_reachable("something is wrong with the memory map");
1747  }
1748  buf += nValues;
1749  }
1750  }
1751  return m.interval_;
1752  }
1753 
1755  write(const std::vector<Value> &buf, const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1756  return buf.empty() ? Sawyer::Container::Interval<Address>() : write(&buf[0], c.limit(buf.size()), flags);
1757  }
1772  void prune(const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1773  using namespace AddressMapImpl;
1775  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1776  flags |= MATCH_NONCONTIGUOUS;
1777  MatchedConstraints<AddressMap> m = matchConstraints(*this, c.addressConstraints(), flags);
1778  BOOST_FOREACH (const Node &node, m.nodes_) {
1779  if (isSatisfied(node, c))
1780  toErase.insert(node.key() & m.interval_);
1781  }
1782  BOOST_FOREACH (const Sawyer::Container::Interval<Address> &interval, toErase.intervals())
1783  this->erase(interval);
1784  }
1785 
1799  void keep(const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
1800  using namespace AddressMapImpl;
1801  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1802  flags |= MATCH_NONCONTIGUOUS;
1804  MatchedConstraints<AddressMap> m = matchConstraints(*this, c.addressConstraints(), flags);
1805  BOOST_FOREACH (const Node &node, m.nodes_) {
1806  if (isSatisfied(node, c))
1807  toKeep.insert(node.key() & m.interval_);
1808  }
1809  toKeep.invert();
1810  BOOST_FOREACH (const Sawyer::Container::Interval<Address> &interval, toKeep.intervals())
1811  this->erase(interval);
1812  }
1813 
1833  void changeAccess(unsigned requiredAccess, unsigned prohibitedAccess, const AddressMapConstraints<AddressMap> &c,
1834  MatchFlags flags=0) {
1835  using namespace AddressMapImpl;
1836  if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1837  flags |= MATCH_NONCONTIGUOUS;
1838  typedef std::pair<Sawyer::Container::Interval<Address>, Segment> ISPair;
1839  std::vector<ISPair> newSegments;
1840  MatchedConstraints<AddressMap> m = matchConstraints(*this, c.addressConstraints(), flags);
1841  BOOST_FOREACH (Node &node, m.nodes_) {
1842  Segment &segment = node.value();
1843  if (isSatisfied(node, c)) {
1844  unsigned newAccess = (segment.accessibility() | requiredAccess) & ~prohibitedAccess;
1845  Sawyer::Container::Interval<Address> toChange = node.key() & m.interval_;
1846  if (toChange == node.key()) { // all addresses in segment are selected; change segment in place
1847  segment.accessibility(newAccess);
1848  } else { // insert a new segment, replacing part of the existing one
1849  Segment newSegment(segment);
1850  newSegment.accessibility(newAccess);
1851  newSegment.offset(segment.offset() + toChange.least() - node.key().least());
1852  newSegments.push_back(ISPair(toChange, newSegment));
1853  }
1854  }
1855  }
1856  BOOST_FOREACH (const ISPair &pair, newSegments)
1857  this->insert(pair.first, pair.second);
1858  }
1859 
1860 private:
1861  // Increment x if necessary so it is aligned.
1862  static Address alignUp(Address x, Address alignment) {
1863  return alignment>0 && x%alignment!=0 ? ((x+alignment-1)/alignment)*alignment : x;
1864  }
1865 
1866  static Address alignDown(Address x, Address alignment) {
1867  return alignment>0 && x%alignment!=0 ? (x/alignment)*alignment : x;
1868  }
1869 };
1870 
1871 } // namespace
1872 } // namespace
1873 
1874 #endif
Base class for testing segment constraints.
Definition: AddressMap.h:55
unsigned required() const
Accessibility bits that are required to be set.
Definition: AddressMap.h:346
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:46
AddressMapConstraints< const AddressMap > substr(const std::string &x) const
Constraint: segment name substring.
Definition: AddressMap.h:1068
NodeIterator findNode(const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Find node containing address.
Definition: AddressMap.h:1483
boost::iterator_range< NodeIterator > nodes(const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Nodes that overlap with constraints.
Definition: AddressMap.h:1394
const Optional< Address > & least() const
Least possible address.
Definition: AddressMap.h:388
AddressMapConstraints limit(size_t x) const
Limit matching length.
Definition: AddressMap.h:263
AddressMapConstraints at(Address x) const
Anchor at a certain address.
Definition: AddressMap.h:249
A Address
Type for addresses.
Definition: AddressMap.h:976
AddressMapConstraints< const AddressMap > access(unsigned x) const
Constraint: required and prohibited access bits.
Definition: AddressMap.h:1055
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:1126
Optional< Address > next(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Minimum or maximum address that satisfies constraints.
Definition: AddressMap.h:1441
Value size() const
Size of interval.
Definition: Interval.h:257
AddressMapConstraints singleSegment() const
Limit matching to single segment.
Definition: AddressMap.h:321
AddressMapConstraints addressConstraints() const
Construct new constraints from existing address constraints.
Definition: AddressMap.h:423
bool neverMatches() const
Returns true if the constraint is not allowed to match anything.
Definition: AddressMap.h:363
AddressMapConstraints< const AddressMap > singleSegment() const
Constraint: single segment.
Definition: AddressMap.h:1227
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:983
Value & value()
Value part of key/value node.
Definition: Sawyer/Map.h:103
AddressMapConstraints< AddressMap > atOrAfter(Address x)
Constraint: address lower bound.
Definition: AddressMap.h:1139
void prune(const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Prune away addresses that match constraints.
Definition: AddressMap.h:1772
Base class for traversals.
Definition: AddressMap.h:1559
AddressMapConstraints< AddressMap > segmentPredicate(SegmentPredicate< Address, Value > *p)
Constraint: arbitrary segment constraint.
Definition: AddressMap.h:1243
AddressMapConstraints substr(const std::string &s) const
Require certain segment names.
Definition: AddressMap.h:229
T Value
Type of data stored in the address space.
Definition: AddressMap.h:977
boost::iterator_range< SegmentIterator > segments()
Iterator range for all segments.
Definition: AddressMap.h:1313
AddressMapConstraints segmentPredicate(SegmentPredicate< Address, Value > *p) const
Limit segments.
Definition: AddressMap.h:328
AddressMapConstraints< const AddressMap > at(Address x) const
Constraint: anchor point.
Definition: AddressMap.h:1082
AddressMapConstraints< AddressMap > access(unsigned x)
Constraint: required and prohibited access bits.
Definition: AddressMap.h:1058
AddressMapConstraints< const AddressMap > before(Address x) const
Constraint: address upper bound.
Definition: AddressMap.h:1214
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:1362
AddressMapConstraints any() const
No constraints.
Definition: AddressMap.h:237
Buffer< A, T >::Ptr buffer() const
Property: buffer.
boost::iterator_range< ConstSegmentIterator > segments() const
Iterator range for all segments.
Definition: AddressMap.h:1314
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:1755
AddressMapConstraints< const AddressMap > prohibit(unsigned x) const
Constraint: prohibited access bits.
Definition: AddressMap.h:1041
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:1217
AddressSegment< A, T > Segment
Type of segments stored by this map.
Definition: AddressMap.h:978
AddressMapConstraints< const AddressMap > atOrBefore(Address x) const
Constraint: address upper bound.
Definition: AddressMap.h:1149
Super::ValueIterator SegmentIterator
Iterates over segments in the map.
Definition: AddressMap.h:981
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:1509
AddressMapConstraints< AddressMap > singleSegment()
Constraint: single segment.
Definition: AddressMap.h:1230
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:394
void traverse(Visitor &visitor, const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Invoke a function on each address interval.
Definition: AddressMap.h:1613
AddressMapConstraints< const AddressMap > require(unsigned x) const
Constraint: required access bits.
Definition: AddressMap.h:1028
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:296
boost::iterator_range< ConstSegmentIterator > segments(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Segments that overlap with constraints.
Definition: AddressMap.h:1337
void insert(const Interval2 &interval)
Insert specified values.
Definition: IntervalSet.h:532
Super::ConstValueIterator ConstSegmentIterator
Iterators over segments in the map.
Definition: AddressMap.h:982
Reference-counting smart pointer.
Definition: SharedPointer.h:34
BitVector & fromInteger(const BitRange &range, boost::uint64_t value)
Obtain bits from an integer.
Definition: BitVector.h:1180
Name space for the entire library.
Definition: Access.h:11
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:137
Sawyer::Container::Interval< Address > write(const Value *buf, const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Writes data from the supplied buffer.
Definition: AddressMap.h:1718
AddressInterval anchored() const
Returns the anchor points.
Definition: AddressMap.h:376
AddressMapConstraints< AddressMap > require(unsigned x)
Constraint: required access bits.
Definition: AddressMap.h:1031
bool exists(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Determines if an address exists with the specified constraints.
Definition: AddressMap.h:1471
const std::string & substr() const
Section name substring.
Definition: AddressMap.h:356
friend std::ostream & operator<<(std::ostream &out, const AddressMapConstraints &x)
Print constraints in a human readable form.
Definition: AddressMap.h:201
AddressMapConstraints< AddressMap > baseSize(Address base, Address size)
Constraint: address lower and upper bounds.
Definition: AddressMap.h:1191
void traverse(Functor &functor, const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Invoke a function on each address interval.
Definition: AddressMap.h:1589
void checkConsistency() const
Check map consistency.
Definition: AddressMap.h:1281
AddressMapConstraints< AddressMap > within(Address x, Address y)
Constraint: address lower and upper bounds.
Definition: AddressMap.h:1178
const Callbacks< SegmentPredicate< Address, Value > * > segmentPredicates() const
Returns the segment predicates.
Definition: AddressMap.h:404
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:1657
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:1165
AddressMapConstraints atOrAfter(Address least) const
Limit addresses.
Definition: AddressMap.h:270
unsigned accessibility() const
Property: access rights.
AddressMapConstraints< const AddressMap > any() const
Constraint: matches anything.
Definition: AddressMap.h:1253
AddressMapConstraints none() const
Constraints that match nothing.
Definition: AddressMap.h:242
Bidirectional iterator over values.
Definition: Sawyer/Map.h:188
AddressMapConstraints within(Address lo, Address hi) const
Limit addresses.
Definition: AddressMap.h:301
AddressMapConstraints< const AddressMap > baseSize(Address base, Address size) const
Constraint: address lower and upper bounds.
Definition: AddressMap.h:1188
AddressMapConstraints< AddressMap > atOrBefore(Address x)
Constraint: address upper bound.
Definition: AddressMap.h:1152
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:351
A mapping from address space to values.
Definition: AddressMap.h:971
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:1112
AddressMapConstraints access(unsigned bits) const
Require and prohibit certain access permissions.
Definition: AddressMap.h:224
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:980
ConstNodeIterator findNode(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Find node containing address.
Definition: AddressMap.h:1480
AddressMapConstraints< AddressMap > after(Address x)
Constraint: address lower bound.
Definition: AddressMap.h:1204
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:1680
void changeAccess(unsigned requiredAccess, unsigned prohibitedAccess, const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Change access bits for addresses that match constraints.
Definition: AddressMap.h:1833
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:409
size_t limit() const
Size limit.
Definition: AddressMap.h:382
AddressMapConstraints< const AddressMap > within(const Sawyer::Container::Interval< Address > &x) const
Constraint: address lower and upper bounds.
Definition: AddressMap.h:1162
bool isAnchored() const
Determines whether constraints are anchored to an address.
Definition: AddressMap.h:368
AddressMapConstraints after(Address x) const
Limit addresses.
Definition: AddressMap.h:311
AddressMapConstraints require(unsigned bits) const
Require certain access permissions.
Definition: AddressMap.h:210
const Key & key() const
Key part of key/value node.
Definition: Sawyer/Map.h:96
AddressMapConstraints< const AddressMap > segmentPredicate(SegmentPredicate< Address, Value > *p) const
Constraint: arbitrary segment constraint.
Definition: AddressMap.h:1240
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:217
Bidirectional iterator over values.
Definition: Sawyer/Map.h:202
Sawyer::Container::Interval< Address > unmapped(Address boundary, MatchFlags flags=0) const
Find unmapped interval.
Definition: AddressMap.h:1496
Constraints are used to select addresses from a memory map.
Definition: AddressMap.h:76
AddressMapConstraints before(Address x) const
Limit addreses.
Definition: AddressMap.h:316
AddressMapConstraints baseSize(Address base, Address size) const
Limit addresses.
Definition: AddressMap.h:306
AddressMapConstraints< AddressMap > none()
Constraint: matches nothing.
Definition: AddressMap.h:1269
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:97
bool isSingleSegment() const
Returns true if the single-segment constraint is set.
Definition: AddressMap.h:399
Super::ConstNodeIterator ConstNodeIterator
Iterates over address interval/segment pairs in the map.
Definition: AddressMap.h:985
A offset() const
Property: buffer offset.
boost::iterator_range< NodeIterator > nodes()
Iterator range for nodes.
Definition: AddressMap.h:1361
AddressMapConstraints atOrBefore(Address greatest) const
Limit addresses.
Definition: AddressMap.h:283
Super::NodeIterator NodeIterator
Iterates over address interval, segment pairs in the map.
Definition: AddressMap.h:984
AddressMapConstraints< AddressMap > substr(const std::string &x)
Constraint: segment name substring.
Definition: AddressMap.h:1071
AddressMapConstraints< const AddressMap > atOrAfter(Address x) const
Constraint: address lower bound.
Definition: AddressMap.h:1136
void keep(const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Keep only addresses that match constraints.
Definition: AddressMap.h:1799
Sawyer::Container::Interval< Address > available(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Adress interval that satisfies constraints.
Definition: AddressMap.h:1455
Bidirectional iterator over keys.
Definition: Sawyer/Map.h:173
AddressMapConstraints< const AddressMap > at(const Sawyer::Container::Interval< Address > &x) const
Constraint: anchored interval.
Definition: AddressMap.h:1109
bool hasNonAddressConstraints() const
Determines whether non-address constraints are present.
Definition: AddressMap.h:415
AddressMapConstraints< const AddressMap > after(Address x) const
Constraint: address lower bound.
Definition: AddressMap.h:1201
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:256
AddressMapConstraints< const AddressMap > none() const
Constraint: matches nothing.
Definition: AddressMap.h:1266
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:1600
AddressMapConstraints< const AddressMap > within(Address x, Address y) const
Constraint: address lower and upper bounds.
Definition: AddressMap.h:1175
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:1123
Address nSegments() const
Number of segments contained in the map.
Definition: AddressMap.h:1306
void print(std::ostream &out) const
Print constraints in a human readable form.
Definition: AddressMap.h:127
void traverse(Visitor &visitor, const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Invoke a function on each address interval.
Definition: AddressMap.h:1610
AddressMapConstraints< AddressMap > any()
Constraint: matches anything.
Definition: AddressMap.h:1256
AddressMapConstraints< AddressMap > prohibit(unsigned x)
Constraint: prohibited access bits.
Definition: AddressMap.h:1044
boost::iterator_range< SegmentIterator > segments(const AddressMapConstraints< AddressMap > &c, MatchFlags flags=0)
Iterator range for all segments.
Definition: AddressMap.h:1346
AddressMapConstraints< AddressMap > at(Address x)
Constraint: anchor point.
Definition: AddressMap.h:1085
std::string toHex(const BitRange &range) const
Convert to a hexadecimal string.
Definition: BitVector.h:1123
boost::iterator_range< ConstNodeIterator > nodes(const AddressMapConstraints< const AddressMap > &c, MatchFlags flags=0) const
Nodes that overlap with constraints.
Definition: AddressMap.h:1385
Type for stored nodes.
Definition: Sawyer/Map.h:87
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:154
AddressMap(const AddressMap &other, bool copyOnWrite=false)
Copy constructor.
Definition: AddressMap.h:1014
AddressMap()
Constructs an empty address map.
Definition: AddressMap.h:997