8 #ifndef Sawyer_AddressMap_H
9 #define Sawyer_AddressMap_H
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>
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>
30 #if __cplusplus >= 201103L
31 #include <type_traits>
37 template<
class AddressMap>
43 template<
class AddressMap>
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>
65 : interval(interval), segment(segment) {}
69 virtual bool operator()(
bool chain,
const Args &) = 0;
79 template<
typename AddressMap>
95 unsigned requiredAccess_;
96 unsigned prohibitedAccess_;
97 std::string nameSubstring_;
102 : map_(
map), never_(false), maxSize_(size_t(-1)), singleSegment_(false), requiredAccess_(0), prohibitedAccess_(0) {}
104 #if __cplusplus >= 201103L
107 template<typename U = AddressMap, typename = typename std::enable_if<!std::is_const<U>::value,
void>::type>
120 cc = cc.atOrAfter(*
least());
123 cc = cc.limit(
limit());
125 cc = cc.singleSegment();
133 operator AddressMapConstraints<const AddressMap>()
const {
134 AddressMapConstraints<const AddressMap> cc(map_);
145 cc = cc.atOrAfter(*
least());
148 cc = cc.limit(
limit());
150 cc = cc.singleSegment();
160 void print(std::ostream &out)
const {
161 out <<
"{map=" <<map_;
165 out <<
", least=" <<*least_;
167 out <<
", greatest=" <<*greatest_;
179 if (maxSize_ !=
size_t(-1))
180 out <<
", limit=" <<maxSize_;
182 out <<
", single-segment";
183 if (requiredAccess_!=0) {
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);
193 if (prohibitedAccess_!=0) {
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);
203 if (!nameSubstring_.empty()) {
205 BOOST_FOREACH (
char ch, nameSubstring_) {
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;
221 sprintf(buf,
"\\%03o", (
unsigned)(
unsigned char)ch);
228 if (!segmentPredicates_.isEmpty())
245 retval.requiredAccess_ |= bits;
252 retval.prohibitedAccess_ |= bits;
263 ASSERT_require(nameSubstring_.empty() || nameSubstring_==s);
265 retval.nameSubstring_ = s;
277 retval.never_ =
true;
285 return retval.anchored_->isEmpty() ? retval.
none() : retval;
291 retval.anchored_ = anchored_ ? *anchored_ & x : x;
298 retval.maxSize_ = std::min(maxSize_, x);
299 return 0 == retval.maxSize_ ? retval.
none() : retval;
306 retval.least_ = std::max(*least_,
least);
308 retval.least_ =
least;
310 if (greatest_ && *greatest_ < *retval.least_)
319 retval.greatest_ = std::min(*greatest_,
greatest);
323 if (least_ && *least_ > *retval.greatest_)
345 return x==boost::integer_traits<Address>::const_max ?
none() :
atOrAfter(x+1);
350 return x==boost::integer_traits<Address>::const_min ?
none() :
atOrBefore(x-1);
356 retval.singleSegment_ =
true;
365 retval.segmentPredicates_.append(p);
371 retval.segmentPredicates_.append(predicates);
380 return requiredAccess_;
385 return prohibitedAccess_;
390 return nameSubstring_;
433 return singleSegment_;
438 return segmentPredicates_;
450 (requiredAccess_ || prohibitedAccess_ || !nameSubstring_.empty() || maxSize_!=
size_t(-1) ||
451 singleSegment_ || !segmentPredicates_.isEmpty()));
459 c.greatest_ = greatest_;
460 c.anchored_ = anchored_;
461 c.maxSize_ = maxSize_;
468 boost::iterator_range<typename AddressMapTraits<AddressMap>::NodeIterator>
470 return map_->
nodes(*
this, flags);
473 boost::iterator_range<typename AddressMapTraits<AddressMap>::SegmentIterator>
475 return map_->
segments(*
this, flags);
478 Optional<typename AddressMap::Address>
480 return map_->
next(*
this, flags);
490 return map_->
exists(*
this, flags);
493 typename AddressMapTraits<AddressMap>::NodeIterator
495 return map_->
findNode(*
this, flags);
498 template<
typename Functor>
500 traverse(Functor &functor,
MatchFlags flags=0)
const {
501 return map_->
traverse(functor, *
this, flags);
504 traverse(
typename AddressMap::Visitor &visitor,
MatchFlags flags=0)
const {
505 return map_->template traverse<typename AddressMap::Visitor>(visitor, *
this, flags);
510 return map_->
read(buf, *
this, flags);
514 read(std::vector<typename AddressMap::Value> &buf ,
516 return map_->
read(buf, *
this, flags);
521 return map_->
write(buf, *
this, flags);
525 write(
const std::vector<typename AddressMap::Value> &buf,
MatchFlags flags=0) {
526 return map_->
write(buf, *
this, flags);
531 return map_->
prune(*
this, flags);
536 return map_->
keep(*
this, flags);
540 changeAccess(
unsigned requiredAccess,
unsigned prohibitedAccess,
MatchFlags flags=0)
const {
541 return map_->
changeAccess(requiredAccess, prohibitedAccess, *
this, flags);
548 namespace AddressMapImpl {
551 template<
class A,
class T>
559 friend class boost::serialization::access;
562 void serialize(S&,
const unsigned ) {
569 ASSERT_forbid(leftInterval.
isEmpty());
570 ASSERT_always_forbid(rightInterval.
isEmpty());
571 ASSERT_require(leftInterval.
greatest() + 1 == rightInterval.
least());
573 leftSegment.
name() == rightSegment.
name() &&
579 ASSERT_forbid(interval.
isEmpty());
587 ASSERT_always_forbid(interval.
isEmpty());
588 ASSERT_always_require(interval.
isContaining(splitPoint));
593 template<
class AddressMap>
598 boost::iterator_range<NodeIterator> nodes_;
606 template<
class AddressMap>
612 return amap.
nodes().end();
616 return amap.
nodes().end();
619 return amap.
nodes().end();
626 if (lb==amap.
nodes().end())
628 minAddr = std::max(*c.
least(), lb->key().least());
632 Iterator lb = amap.
nodes().begin();
633 if (lb!=amap.
nodes().end())
634 minAddr = lb->key().least();
644 template<
class AddressMap>
645 typename AddressMapTraits<AddressMap>::NodeIterator
646 constraintUpperBound(AddressMap &amap,
const AddressMapConstraints<AddressMap> &c,
bool useAnchor,
648 typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
649 if (amap.isEmpty() || c.neverMatches())
650 return amap.nodes().begin();
652 if (useAnchor && c.isAnchored()) {
653 if ((c.least() && *c.least() > c.anchored().least()) || (c.greatest() && *c.greatest() < c.anchored().greatest()))
654 return amap.nodes().begin();
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();
658 maxAddr = c.anchored().greatest();
663 Iterator ub = amap.findPrior(*c.greatest());
664 if (ub==amap.nodes().end())
665 return amap.nodes().begin();
666 maxAddr = std::min(ub->key().greatest(), *c.greatest());
670 maxAddr = amap.hull().greatest();
671 return amap.nodes().end();
675 template<
class AddressMap>
677 isSatisfied(
const typename AddressMap::Node &node,
const AddressMapConstraints<AddressMap> &c) {
681 const Segment &segment = node.value();
682 if (!segment.isAccessible(c.required(), c.prohibited()))
684 if (!boost::contains(segment.name(), c.substr()))
686 if (!c.segmentPredicates().apply(
true,
typename SegmentPredicate<Address, Value>::Args(node.key(), node.value())))
692 template<
class AddressMap>
693 MatchedConstraints<AddressMap>
694 matchForward(AddressMap &amap,
const AddressMapConstraints<AddressMap> &c,
MatchFlags flags) {
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())
704 Iterator begin = constraintLowerBound(amap, c,
true, minAddr );
705 if (begin == amap.nodes().end())
710 Iterator end = constraintUpperBound(amap, c,
false, maxAddr );
711 if (end==amap.nodes().begin())
715 while (begin!=end && !isSatisfied(*begin, c)) {
722 minAddr = std::max(minAddr, begin->key().least());
725 if ((flags & MATCH_CONTIGUOUS)!=0 || c.hasNonAddressConstraints()) {
726 Address addr = minAddr;
727 Iterator iter = begin;
728 size_t nElmtsFound = 0;
729 for (; iter!=end; ++iter) {
731 if (c.isSingleSegment())
733 if ((flags & MATCH_CONTIGUOUS)!=0 && addr+1 != iter->key().least())
735 if (!isSatisfied(*iter, c)) {
736 if ((flags & MATCH_WHOLE)!=0)
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;
748 addr = iter->key().greatest();
749 nElmtsFound += nElmtsHere;
752 maxAddr = std::min(maxAddr, addr);
757 retval.nodes_ = boost::iterator_range<Iterator>(begin, end);
762 template<
class AddressMap>
763 MatchedConstraints<AddressMap>
764 matchBackward(AddressMap &amap,
const AddressMapConstraints<AddressMap> &c,
MatchFlags flags) {
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())
774 Iterator begin = constraintLowerBound(amap, c,
false, minAddr );
775 if (begin == amap.nodes().end())
780 Iterator end = constraintUpperBound(amap, c,
true, maxAddr );
781 if (end==amap.nodes().begin())
786 Iterator prev = end; --prev;
787 if (isSatisfied(*prev, c)) {
788 maxAddr = std::min(maxAddr, prev->key().greatest());
800 if ((flags & MATCH_CONTIGUOUS)!=0 || c.hasNonAddressConstraints()) {
801 Address addr = maxAddr;
803 size_t nElmtsFound = 0;
804 for (; iter!=begin; --iter) {
805 Iterator prev = iter; --prev;
807 if (c.isSingleSegment())
809 if ((flags & MATCH_CONTIGUOUS)!=0 && prev->key().greatest()+1 != addr)
811 if (!isSatisfied(*prev, c)) {
812 if ((flags & MATCH_WHOLE)!=0)
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;
824 addr = prev->key().least();
825 nElmtsFound += nElmtsHere;
828 minAddr = std::max(minAddr, addr);
833 retval.nodes_ = boost::iterator_range<Iterator>(begin, end);
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);
1003 template<
class A,
class T = boost::u
int8_t>
1021 friend class boost::serialization::access;
1024 void serialize(S &s,
const unsigned ) {
1025 s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(
Super);
1051 buffer->copyOnWrite(
true);
1315 BOOST_FOREACH (
const Node &node,
nodes()) {
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()) +
"]");
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()));
1347 boost::iterator_range<ConstSegmentIterator>
segments()
const {
return this->
values(); }
1369 boost::iterator_range<ConstSegmentIterator>
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());
1378 boost::iterator_range<SegmentIterator>
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_);
1417 boost::iterator_range<ConstNodeIterator>
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);
1426 boost::iterator_range<NodeIterator>
1428 using namespace AddressMapImpl;
1429 if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1430 flags |= MATCH_CONTIGUOUS;
1431 MatchedConstraints<AddressMap> m = matchConstraints(*
this, c, flags);
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);
1489 using namespace AddressMapImpl;
1490 if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
1491 flags |= MATCH_CONTIGUOUS;
1492 return matchConstraints(*
this, c, flags).interval_;
1505 return next(c, flags);
1546 ASSERT_forbid2(nValues == 0,
"cannot determine if this is an overflow or intentional");
1548 if (restriction.isEmpty())
1551 if (0 == (flags & MATCH_BACKWARD)) {
1552 Address minAddr = restriction.least();
1553 while (minAddr <= restriction.greatest()) {
1557 minAddr = alignUp(interval.
least(), alignment);
1558 Address maxAddr = minAddr + (nValues-1);
1559 if ((nValues <= interval.
size() || 0==interval.
size()) &&
1560 minAddr >= interval.
least() && maxAddr >= interval.
least() &&
1571 ASSERT_require((flags & MATCH_BACKWARD) != 0);
1572 Address maxAddr = restriction.greatest();
1573 while (maxAddr >= restriction.least()) {
1577 Address minAddr = alignDown(interval.
greatest() - (nValues-1), alignment);
1578 maxAddr = minAddr + (nValues-1);
1579 if ((nValues <= interval.
size() || 0==interval.
size()) &&
1580 minAddr >= interval.
least() && maxAddr >= interval.
least() &&
1586 maxAddr = interval.
least() - 1;
1621 template<
typename Functor>
1623 using namespace AddressMapImpl;
1624 MatchedConstraints<const AddressMap> m = matchConstraints(*
this, c, flags);
1625 BOOST_FOREACH (
const Node &node, m.nodes_) {
1627 if (!functor(*
this, part))
1632 template<
typename Functor>
1634 using namespace AddressMapImpl;
1635 MatchedConstraints<AddressMap> m = matchConstraints(*
this, c, flags);
1636 BOOST_FOREACH (
const Node &node, m.nodes_) {
1638 if (!functor(*
this, part))
1644 traverse<Visitor>(visitor, c, flags);
1647 traverse<Visitor>(visitor, c, flags);
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);
1697 BOOST_FOREACH (
const Node &node, m.nodes_) {
1699 ASSERT_forbid(part.
isEmpty());
1701 Address nValues = node.
value().buffer()->read(buf, bufferOffset, part.
size());
1702 if (nValues != part.
size()) {
1704 ASSERT_not_reachable(
"something is wrong with the memory map");
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);
1758 BOOST_FOREACH (
Node &node, m.nodes_) {
1761 ASSERT_forbid(part.
isEmpty());
1763 ASSERT_not_null(buffer);
1765 if (buffer->copyOnWrite()) {
1767 ASSERT_not_null(newBuffer);
1769 if (iter->value().buffer() == buffer)
1770 iter->value().buffer(newBuffer);
1776 Address nValues = buffer->write(buf, bufferOffset, part.
size());
1777 if (nValues != part.
size()) {
1779 ASSERT_not_reachable(
"something is wrong with the memory map");
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_);
1816 this->
erase(interval);
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_);
1844 this->
erase(interval);
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_) {
1876 if (isSatisfied(node, c)) {
1877 unsigned newAccess = (segment.
accessibility() | requiredAccess) & ~prohibitedAccess;
1879 if (toChange == node.
key()) {
1885 newSegments.push_back(ISPair(toChange, newSegment));
1889 BOOST_FOREACH (
const ISPair &pair, newSegments)
1890 this->
insert(pair.first, pair.second);
1896 return alignment>0 && x%alignment!=0 ? ((x+alignment-1)/alignment)*alignment : x;
1900 return alignment>0 && x%alignment!=0 ? (x/alignment)*alignment : x;