AddressMap.h

// WARNING: Changes to this file must be contributed back to Sawyer or else they will
//          be clobbered by the next update from Sawyer.  The Sawyer repository is at
//          https://github.com/matzke1/sawyer.




#ifndef Sawyer_AddressMap_H
#define Sawyer_AddressMap_H

#include <Sawyer/Access.h>
#include <Sawyer/AddressSegment.h>
#include <Sawyer/Assert.h>
#include <Sawyer/BitVector.h>
#include <Sawyer/Callbacks.h>
#include <Sawyer/Interval.h>
#include <Sawyer/IntervalMap.h>
#include <Sawyer/IntervalSet.h>
#include <Sawyer/Sawyer.h>

#include <boost/algorithm/string/predicate.hpp>
#include <boost/cstdint.hpp>
#include <boost/foreach.hpp>
#include <boost/integer_traits.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/serialization/access.hpp>
#include <boost/serialization/base_object.hpp>
#include <boost/serialization/nvp.hpp>

#if __cplusplus >= 201103L
#include <type_traits>
#endif

namespace Sawyer {
namespace Container {

template<class AddressMap>
struct AddressMapTraits {
    typedef typename AddressMap::NodeIterator NodeIterator;
    typedef typename AddressMap::SegmentIterator SegmentIterator;
};

template<class AddressMap>
struct AddressMapTraits<const AddressMap> {
    typedef typename AddressMap::ConstNodeIterator NodeIterator;
    typedef typename AddressMap::ConstSegmentIterator SegmentIterator;
};

typedef unsigned MatchFlags;
static const MatchFlags MATCH_BACKWARD      = 0x00000001; 
static const MatchFlags MATCH_CONTIGUOUS    = 0x00000002; 
static const MatchFlags MATCH_NONCONTIGUOUS = 0x00000004; 
static const MatchFlags MATCH_WHOLE         = 0x00000008; 
template<class A, class T>
class SegmentPredicate {
public:
    struct Args {
        const Sawyer::Container::Interval<A> &interval;
        const AddressSegment<A, T> &segment;
        Args(const Sawyer::Container::Interval<A> &interval, const AddressSegment<A, T> &segment)
            : interval(interval), segment(segment) {}
    };

    virtual ~SegmentPredicate() {}
    virtual bool operator()(bool chain, const Args &) = 0;
};

template<typename AddressMap>
class AddressMapConstraints {
public:
    typedef typename AddressMap::Address Address;
    typedef typename AddressMap::Value Value;
    typedef Sawyer::Container::Interval<Address> AddressInterval;
private:
    AddressMap *map_;                                   // AddressMap<> to which these constraints are bound
    bool never_;                                        // never match anything (e.g., when least_ > greatest_)
    // address constraints
    Optional<Address> least_;                           // least possible valid address
    Optional<Address> greatest_;                        // greatest possible valid address
    Optional<AddressInterval> anchored_;                // anchored least or greatest depending on direction
    // constraints requiring iteration
    size_t maxSize_;                                    // result size is limited
    bool singleSegment_;                                // do not cross a segment boundary
    unsigned requiredAccess_;                           // access bits that must be set in the segment
    unsigned prohibitedAccess_;                         // access bits that must be clear in the segment
    std::string nameSubstring_;                         // segment name must contain substring
    Callbacks<SegmentPredicate<Address, Value>*> segmentPredicates_; // user-supplied segment predicates
public:
    AddressMapConstraints(AddressMap *map)
        : map_(map), never_(false), maxSize_(size_t(-1)), singleSegment_(false), requiredAccess_(0), prohibitedAccess_(0) {}

#if __cplusplus >= 201103L
    // Implicitly construct constraints for a const AddressMap from a non-const address map. The dummy U parameter is to force
    // type deduction to be delayed to the point where this function is instantiated.
    template<typename U = AddressMap, typename = typename std::enable_if<!std::is_const<U>::value, void>::type>
    operator AddressMapConstraints<const U>() const {
        AddressMapConstraints<const AddressMap> cc(map_);
        if (neverMatches())
            cc = cc.none();
        if (isAnchored()) {
            if (anchored().isSingleton()) {
                cc = cc.at(anchored().least());
            } else {
                cc = cc.at(anchored());
            }
        }
        if (least())
            cc = cc.atOrAfter(*least());
        if (greatest())
            cc = cc.atOrBefore(*greatest());
        cc = cc.limit(limit());
        if (isSingleSegment())
            cc = cc.singleSegment();
        cc = cc.require(required());
        cc = cc.prohibit(prohibited());
        cc = cc.substr(substr());
        cc = cc.segmentPredicates(segmentPredicates());
        return cc;
    }
#else
    operator AddressMapConstraints<const AddressMap>() const {
        AddressMapConstraints<const AddressMap> cc(map_);
        if (neverMatches())
            cc = cc.none();
        if (isAnchored()) {
            if (anchored().isSingleton()) {
                cc = cc.at(anchored().least());
            } else {
                cc = cc.at(anchored());
            }
        }
        if (least())
            cc = cc.atOrAfter(*least());
        if (greatest())
            cc = cc.atOrBefore(*greatest());
        cc = cc.limit(limit());
        if (isSingleSegment())
            cc = cc.singleSegment();
        cc = cc.require(required());
        cc = cc.prohibit(prohibited());
        cc = cc.substr(substr());
        cc = cc.segmentPredicates(segmentPredicates());
        return cc;
    }
#endif

    void print(std::ostream &out) const {
        out <<"{map=" <<map_;
        if (never_)
            out <<", never";
        if (least_)
            out <<", least=" <<*least_;
        if (greatest_)
            out <<", greatest=" <<*greatest_;
        if (anchored_) {
            out <<", anchored=";
            AddressInterval a = *anchored_;
            if (a.isEmpty()) {
                out <<"empty";
            } else if (a.least()==a.greatest()) {
                out <<a.least();
            } else {
                out <<"{" <<a.least() <<".." <<a.greatest() <<"}";
            }
        }
        if (maxSize_ != size_t(-1))
            out <<", limit=" <<maxSize_;
        if (singleSegment_)
            out <<", single-segment";
        if (requiredAccess_!=0) {
            out <<", required="
                <<((requiredAccess_ & Access::READABLE) ? "r" : "")
                <<((requiredAccess_ & Access::WRITABLE) ? "w" : "")
                <<((requiredAccess_ & Access::EXECUTABLE) ? "x" : "")
                <<((requiredAccess_ & Access::IMMUTABLE) ? "i" : "");
            unsigned other = requiredAccess_ & ~(Access::READABLE|Access::WRITABLE|Access::EXECUTABLE|Access::IMMUTABLE);
            if (other)
                out <<"+0x" <<BitVector(8*sizeof requiredAccess_).fromInteger(other).toHex();
        }
        if (prohibitedAccess_!=0) {
            out <<", required="
                <<((prohibitedAccess_ & Access::READABLE) ? "r" : "")
                <<((prohibitedAccess_ & Access::WRITABLE) ? "w" : "")
                <<((prohibitedAccess_ & Access::EXECUTABLE) ? "x" : "")
                <<((prohibitedAccess_ & Access::IMMUTABLE) ? "i" : "");
            unsigned other = prohibitedAccess_ & ~(Access::READABLE|Access::WRITABLE|Access::EXECUTABLE|Access::IMMUTABLE);
            if (other)
                out <<"+0x" <<BitVector(8*sizeof prohibitedAccess_).fromInteger(other).toHex();
        }
        if (!nameSubstring_.empty()) {
            out <<", substr=\"";
            BOOST_FOREACH (char ch, nameSubstring_) {
                switch (ch) {
                    case '\a': out <<"\\a"; break;
                    case '\b': out <<"\\b"; break;
                    case '\t': out <<"\\t"; break;
                    case '\n': out <<"\\n"; break;
                    case '\v': out <<"\\v"; break;
                    case '\f': out <<"\\f"; break;
                    case '\r': out <<"\\r"; break;
                    case '\"': out <<"\\\""; break;
                    case '\\': out <<"\\\\"; break;
                    default:
                        if (isprint(ch)) {
                            out <<ch;
                        } else {
                            char buf[8];
                            sprintf(buf, "\\%03o", (unsigned)(unsigned char)ch);
                            out <<buf;
                        }
                        break;
                }
            }
        }
        if (!segmentPredicates_.isEmpty())
            out <<", user-def";
        out <<"}";
    }

    friend std::ostream& operator<<(std::ostream &out, const AddressMapConstraints &x) {
        x.print(out);
        return out;
    }
    
    // Constraint modifiers
public:
    AddressMapConstraints require(unsigned bits) const {
        AddressMapConstraints retval = *this;
        retval.requiredAccess_ |= bits;
        return retval;
    }

    AddressMapConstraints prohibit(unsigned bits) const {
        AddressMapConstraints retval = *this;
        retval.prohibitedAccess_ |= bits;
        return retval;
    }

    AddressMapConstraints access(unsigned bits) const {
        return require(bits).prohibit(~bits);
    }

    AddressMapConstraints substr(const std::string &s) const {
        ASSERT_require(nameSubstring_.empty() || nameSubstring_==s);// substring conjunction not supported
        AddressMapConstraints retval = *this;
        retval.nameSubstring_ = s;
        return retval;
    }

    AddressMapConstraints any() const {
        return *this;
    }

    AddressMapConstraints none() const {
        AddressMapConstraints retval = *this;
        retval.never_ = true;
        return retval;
    }

    AddressMapConstraints at(Address x) const {
        AddressMapConstraints retval = *this;
        retval.anchored_ = anchored_ ? *anchored_ & AddressInterval(x) : AddressInterval(x);
        return retval.anchored_->isEmpty() ? retval.none() : retval;
    }

    AddressMapConstraints at(const Sawyer::Container::Interval<Address> &x) const {
        AddressMapConstraints retval = *this;
        retval.anchored_ = anchored_ ? *anchored_ & x : x;
        return retval.anchored_->isEmpty() ? retval.none() : retval.atOrAfter(x.least()).atOrBefore(x.greatest());
    }

    AddressMapConstraints limit(size_t x) const {
        AddressMapConstraints retval = *this;
        retval.maxSize_ = std::min(maxSize_, x);
        return 0 == retval.maxSize_ ? retval.none() : retval;
    }

    AddressMapConstraints atOrAfter(Address least) const {
        AddressMapConstraints retval = *this;
        if (least_) {
            retval.least_ = std::max(*least_, least);
        } else {
            retval.least_ = least;
        }
        if (greatest_ && *greatest_ < *retval.least_)
            retval.none();
        return retval;
    }

    AddressMapConstraints atOrBefore(Address greatest) const {
        AddressMapConstraints retval = *this;
        if (greatest_) {
            retval.greatest_ = std::min(*greatest_, greatest);
        } else {
            retval.greatest_ = greatest;
        }
        if (least_ && *least_ > *retval.greatest_)
            retval.none();
        return retval;
    }

    AddressMapConstraints within(const Sawyer::Container::Interval<Address> &x) const {
        return x.isEmpty() ? none() : atOrAfter(x.least()).atOrBefore(x.greatest());
    }

    AddressMapConstraints within(Address lo, Address hi) const {
        return lo<=hi ? within(Sawyer::Container::Interval<Address>::hull(lo, hi)) : none();
    }

    AddressMapConstraints baseSize(Address base, Address size) const {
        return size>0 ? atOrAfter(base).atOrBefore(base+size-1) : none();
    }

    AddressMapConstraints after(Address x) const {
        return x==boost::integer_traits<Address>::const_max ? none() : atOrAfter(x+1);
    }

    AddressMapConstraints before(Address x) const {
        return x==boost::integer_traits<Address>::const_min ? none() : atOrBefore(x-1);
    }

    AddressMapConstraints singleSegment() const {
        AddressMapConstraints retval = *this;
        retval.singleSegment_ = true;
        return retval;
    }

    AddressMapConstraints segmentPredicate(SegmentPredicate<Address, Value> *p) const {
        if (!p)
            return none();
        AddressMapConstraints retval = *this;
        retval.segmentPredicates_.append(p);
        return retval;
    }

    AddressMapConstraints segmentPredicates(const Callbacks<SegmentPredicate<Address, Value>*> &predicates) const {
        AddressMapConstraints retval = *this;
        retval.segmentPredicates_.append(predicates);
        return retval;
    }
    
    // Constraint queries
public:
    unsigned required() const {
        return requiredAccess_;
    }

    unsigned prohibited() const {
        return prohibitedAccess_;
    }

    const std::string& substr() const {
        return nameSubstring_;
    }

    bool neverMatches() const {
        return never_;
    }

    bool isAnchored() const {
        return anchored_;
    }

    AddressInterval anchored() const {
        ASSERT_require(isAnchored());
        return *anchored_;
    }

    size_t limit() const {
        return maxSize_;
    }

    const Optional<Address>& least() const {
        return least_;
    }

    const Optional<Address>& greatest() const {
        return greatest_;
    }

    bool isSingleSegment() const {
        return singleSegment_;
    }

    const Callbacks<SegmentPredicate<Address, Value>*> segmentPredicates() const {
        return segmentPredicates_;
    }

    AddressMap* map() const {
        return map_;
    }

    bool hasNonAddressConstraints() const {
        return (!never_ &&
                (requiredAccess_ || prohibitedAccess_ || !nameSubstring_.empty() || maxSize_!=size_t(-1) ||
                 singleSegment_ || !segmentPredicates_.isEmpty()));
    }

    AddressMapConstraints addressConstraints() const {
        AddressMapConstraints c(map_);
        c.least_ = least_;
        c.greatest_ = greatest_;
        c.anchored_ = anchored_;
        c.maxSize_ = maxSize_;
        return c;
    }

    // Methods that directly call the AddressMap
public:
    boost::iterator_range<typename AddressMapTraits<AddressMap>::NodeIterator>
    nodes(MatchFlags flags=0) const {
        return map_->nodes(*this, flags);
    }

    boost::iterator_range<typename AddressMapTraits<AddressMap>::SegmentIterator>
    segments(MatchFlags flags=0) const {
        return map_->segments(*this, flags);
    }

    Optional<typename AddressMap::Address>
    next(MatchFlags flags=0) const {
        return map_->next(*this, flags);
    }

    Sawyer::Container::Interval<Address>
    available(MatchFlags flags=0) const {
        return map_->available(*this, flags);
    }

    bool
    exists(MatchFlags flags=0) const {
        return map_->exists(*this, flags);
    }

    typename AddressMapTraits<AddressMap>::NodeIterator
    findNode(MatchFlags flags=0) const {
        return map_->findNode(*this, flags);
    }

    template<typename Functor>
    void
    traverse(Functor &functor, MatchFlags flags=0) const {
        return map_->traverse(functor, *this, flags);
    }
    void
    traverse(typename AddressMap::Visitor &visitor, MatchFlags flags=0) const {
        return map_->template traverse<typename AddressMap::Visitor>(visitor, *this, flags);
    }
    
    Sawyer::Container::Interval<Address>
    read(typename AddressMap::Value *buf /*out*/, MatchFlags flags=0) const {
        return map_->read(buf, *this, flags);
    }

    Sawyer::Container::Interval<Address>
    read(std::vector<typename AddressMap::Value> &buf /*out*/,
         MatchFlags flags=0) const {
        return map_->read(buf, *this, flags);
    }

    Sawyer::Container::Interval<Address>
    write(const typename AddressMap::Value *buf, MatchFlags flags=0) const {
        return map_->write(buf, *this, flags);
    }

    Sawyer::Container::Interval<Address>
    write(const std::vector<typename AddressMap::Value> &buf, MatchFlags flags=0) {
        return map_->write(buf, *this, flags);
    }
    
    void
    prune(MatchFlags flags=0) const {
        return map_->prune(*this, flags);
    }

    void
    keep(MatchFlags flags=0) const {
        return map_->keep(*this, flags);
    }

    void
    changeAccess(unsigned requiredAccess, unsigned prohibitedAccess, MatchFlags flags=0) const {
        return map_->changeAccess(requiredAccess, prohibitedAccess, *this, flags);
    }
};

//                                      Implementation details
namespace AddressMapImpl {

// Used internally to split and merge segments
template<class A, class T>
class SegmentMergePolicy {
public:
    typedef A Address;
    typedef T Value;
    typedef AddressSegment<A, T> Segment;

private:
    friend class boost::serialization::access;

    template<class S>
    void serialize(S&, const unsigned /*version*/) {
        // no data to serialize here
    }

public:
    bool merge(const Sawyer::Container::Interval<Address> &leftInterval, Segment &leftSegment,
               const Sawyer::Container::Interval<Address> &rightInterval, Segment &rightSegment) {
        ASSERT_forbid(leftInterval.isEmpty());
        ASSERT_always_forbid(rightInterval.isEmpty()); // so rightInterval is always used
        ASSERT_require(leftInterval.greatest() + 1 == rightInterval.least());
        return (leftSegment.accessibility() == rightSegment.accessibility() &&
                leftSegment.name() == rightSegment.name() &&
                leftSegment.buffer() == rightSegment.buffer() &&
                leftSegment.offset() + leftInterval.size() == rightSegment.offset());
    }

    Segment split(const Sawyer::Container::Interval<Address> &interval, Segment &segment, Address splitPoint) {
        ASSERT_forbid(interval.isEmpty());
        ASSERT_require(interval.contains(splitPoint));
        Segment right = segment;
        right.offset(segment.offset() + splitPoint - interval.least());
        return right;
    }

    void truncate(const Sawyer::Container::Interval<Address> &interval, Segment &/*segment*/, Address splitPoint) {
        ASSERT_always_forbid(interval.isEmpty()); // so interval is always used
        ASSERT_always_require(interval.contains(splitPoint)); // ditto for splitPoint
    }
};

// The results for matching constraints
template<class AddressMap>
struct MatchedConstraints {
    typedef typename AddressMap::Address Address;
    Sawyer::Container::Interval<Address> interval_;
    typedef typename AddressMapTraits<AddressMap>::NodeIterator NodeIterator;
    boost::iterator_range<NodeIterator> nodes_;
};

// Finds the minimum possible address and node iterator for the specified constraints in this map and returns that
// iterator.  Returns the end iterator if the constraints match no address.  If a non-end iterator is returned then minAddr
// is adjusted to be the minimum address that satisfies the constraint (it will be an address within the returned node, but
// not necessarily the least address for the node).  If useAnchor is set and the constraints specify an anchor, then the
// anchor address must be present in the map and satisfy any address constraints that might also be present.
template<class AddressMap>
typename AddressMapTraits<AddressMap>::NodeIterator
constraintLowerBound(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, bool useAnchor,
                     typename AddressMap::Address &minAddr) {
    typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
    if (amap.isEmpty() || c.neverMatches())
        return amap.nodes().end();

    if (useAnchor && c.isAnchored()) {                  // forward matching if useAnchor is set
        if ((c.least() && *c.least() > c.anchored().least()) || (c.greatest() && *c.greatest() < c.anchored().greatest()))
            return amap.nodes().end();                  // anchor is outside of allowed interval
        Iterator lb = amap.lowerBound(c.anchored().least());
        if (lb==amap.nodes().end() || c.anchored().least() < lb->key().least())
            return amap.nodes().end();                  // anchor is not present in this map
        minAddr = c.anchored().least();
        return lb;
    }

    if (c.least()) {
        Iterator lb = amap.lowerBound(*c.least());
        if (lb==amap.nodes().end())
            return lb;                                  // least is above all segments
        minAddr = std::max(*c.least(), lb->key().least());
        return lb;
    }

    Iterator lb = amap.nodes().begin();
    if (lb!=amap.nodes().end())
        minAddr = lb->key().least();
    return lb;
}

// Finds the maximum possible address and node for the specified constraints in this map, and returns an iterator to the
// following node.  Returns the begin iterator if the constraints match no address.  If a non-begin iterator is returned
// then maxAddr is adjusted to be the maximum address that satisfies the constraint (it will be an address that belongs to
// the node immediately prior to the one pointed to by the returned iterator, but not necessarily the greatest address for
// that node).  If useAnchor is set and the constraints specify an anchor, then the anchor address must be present in the
// map and satisfy any address constraints that might also be present.
template<class AddressMap>
typename AddressMapTraits<AddressMap>::NodeIterator
constraintUpperBound(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, bool useAnchor,
                     typename AddressMap::Address &maxAddr) {
    typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
    if (amap.isEmpty() || c.neverMatches())
        return amap.nodes().begin();

    if (useAnchor && c.isAnchored()) {                  // backward matching if useAnchor is set
        if ((c.least() && *c.least() > c.anchored().least()) || (c.greatest() && *c.greatest() < c.anchored().greatest()))
            return amap.nodes().begin();                // anchor is outside allowed interval
        Iterator ub = amap.findPrior(c.anchored().greatest());
        if (ub==amap.nodes().end() || c.anchored().greatest() > ub->key().greatest())
            return amap.nodes().begin();                // anchor is not present in this map
        maxAddr = c.anchored().greatest();
        return ++ub;                                    // return node after the one containing the anchor
    }

    if (c.greatest()) {
        Iterator ub = amap.findPrior(*c.greatest());
        if (ub==amap.nodes().end())
            return amap.nodes().begin();            // greatest is below all segments
        maxAddr = std::min(ub->key().greatest(), *c.greatest());
        return ++ub;                                // return node after the one containing the maximum
    }

    maxAddr = amap.hull().greatest();
    return amap.nodes().end();
}

// Returns true if the segment satisfies the non-address constraints in c.
template<class AddressMap>
bool
isSatisfied(const typename AddressMap::Node &node, const AddressMapConstraints<AddressMap> &c) {
    typedef typename AddressMap::Address Address;
    typedef typename AddressMap::Value Value;
    typedef typename AddressMap::Segment Segment;
    const Segment &segment = node.value();
    if (!segment.isAccessible(c.required(), c.prohibited()))
        return false;                               // wrong segment permissions
    if (!boost::contains(segment.name(), c.substr()))
        return false;                               // wrong segment name
    if (!c.segmentPredicates().apply(true, typename SegmentPredicate<Address, Value>::Args(node.key(), node.value())))
        return false;                               // user-supplied predicates failed
    return true;
}

// Matches constraints against contiguous addresses in a forward direction.
template<class AddressMap>
MatchedConstraints<AddressMap>
matchForward(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, MatchFlags flags) {
    typedef typename AddressMap::Address Address;
    typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
    MatchedConstraints<AddressMap> retval;
    retval.nodes_ = boost::iterator_range<Iterator>(amap.nodes().end(), amap.nodes().end());
    if (c.neverMatches() || amap.isEmpty())
        return retval;

    // Find a lower bound for the minimum address
    Address minAddr = 0;
    Iterator begin = constraintLowerBound(amap, c, true, minAddr /*out*/);
    if (begin == amap.nodes().end())
        return retval;

    // Find an upper bound for the maximum address.
    Address maxAddr = 0;
    Iterator end = constraintUpperBound(amap, c, false, maxAddr /*out*/);
    if (end==amap.nodes().begin())
        return retval;

    // Advance the lower-bound until it satisfies the other (non-address) constraints
    while (begin!=end && !isSatisfied(*begin, c)) {
        if (c.isAnchored())
            return retval;                          // match is anchored to minAddr
        ++begin;
    }
    if (begin==end)
        return retval;
    minAddr = std::max(minAddr, begin->key().least());

    // Iterate forward until the constraints are no longer satisfied
    if ((flags & MATCH_CONTIGUOUS)!=0 || c.hasNonAddressConstraints()) {
        Address addr = minAddr;
        Iterator iter = begin;
        size_t nElmtsFound = 0;
        for (/*void*/; iter!=end; ++iter) {
            if (iter!=begin) {                      // already tested the first node above
                if (c.isSingleSegment())
                    break;                          // we crossed a segment boundary
                if ((flags & MATCH_CONTIGUOUS)!=0 && addr+1 != iter->key().least())
                    break;                          // gap between segments
                if (!isSatisfied(*iter, c)) {
                    if ((flags & MATCH_WHOLE)!=0)
                        return retval;              // match is anchored to maxAddr
                    break;                          // segment does not satisfy constraints
                }
            }
            size_t nElmtsHere = iter->key().greatest() + 1 - std::max(minAddr, iter->key().least());
            if (nElmtsFound + nElmtsHere >= c.limit()) {
                size_t nNeed = c.limit() - nElmtsFound;
                addr = std::max(minAddr, iter->key().least()) + nNeed - 1;
                ++iter;
                break;                              // too many values
            }
            addr = iter->key().greatest();
            nElmtsFound += nElmtsHere;
        }
        end = iter;
        maxAddr = std::min(maxAddr, addr);
    }

    // Build the result
    retval.interval_ = Sawyer::Container::Interval<Address>::hull(minAddr, maxAddr);
    retval.nodes_ = boost::iterator_range<Iterator>(begin, end);
    return retval;
}

// Matches constraints against contiguous addresses in a backward direction.
template<class AddressMap>
MatchedConstraints<AddressMap>
matchBackward(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, MatchFlags flags) {
    typedef typename AddressMap::Address Address;
    typedef typename AddressMapTraits<AddressMap>::NodeIterator Iterator;
    MatchedConstraints<AddressMap> retval;
    retval.nodes_ = boost::iterator_range<Iterator>(amap.nodes().end(), amap.nodes().end());
    if (c.neverMatches() || amap.isEmpty())
        return retval;

    // Find a lower bound for the minimum address
    Address minAddr = 0;
    Iterator begin = constraintLowerBound(amap, c, false, minAddr /*out*/);
    if (begin == amap.nodes().end())
        return retval;

    // Find an upper bound for the maximum address.
    Address maxAddr = 0;
    Iterator end = constraintUpperBound(amap, c, true, maxAddr /*out*/);
    if (end==amap.nodes().begin())
        return retval;

    // Decrement the upper bound until constraints are met. End always points to one-past the last matching node.
    while (end!=begin) {
        Iterator prev = end; --prev;
        if (isSatisfied(*prev, c)) {
            maxAddr = std::min(maxAddr, prev->key().greatest());
            break;
        }
        if (c.isAnchored())
            return retval;                          // match is anchored to maxAddr
        end = prev;
    }
    if (end==begin)
        return retval;

    // Iterate backward until the constraints are no longer satisfied. Within the loop, iter always points to on-past the
    // node in question.  When the loop exits, iter points to the first node satisfying constraints.
    if ((flags & MATCH_CONTIGUOUS)!=0 || c.hasNonAddressConstraints()) {
        Address addr = maxAddr;
        Iterator iter = end;
        size_t nElmtsFound = 0;
        for (/*void*/; iter!=begin; --iter) {
            Iterator prev = iter; --prev;           // prev points to the node in question
            if (iter!=end) {                        // already tested last node above
                if (c.isSingleSegment())
                    break;                          // we crossed a segment boundary
                if ((flags & MATCH_CONTIGUOUS)!=0 && prev->key().greatest()+1 != addr)
                    break;                          // gap between segments
                if (!isSatisfied(*prev, c)) {
                    if ((flags & MATCH_WHOLE)!=0)
                        return retval;              // match is anchored to minAddr
                    break;                          // segment does not satisfy constraints
                }
            }
            size_t nElmtsHere = std::min(maxAddr, prev->key().greatest()) - prev->key().least() + 1;
            if (nElmtsFound + nElmtsHere >= c.limit()) {
                size_t nNeed = c.limit() - nElmtsFound;
                addr = std::min(maxAddr, prev->key().greatest()) - nNeed + 1;
                iter = prev;
                break;
            }
            addr = prev->key().least();
            nElmtsFound += nElmtsHere;
        }
        begin = iter;                               // iter points to first matching node
        minAddr = std::max(minAddr, addr);
    }

    // Build the result
    retval.interval_ = Sawyer::Container::Interval<Address>::hull(minAddr, maxAddr);
    retval.nodes_ = boost::iterator_range<Iterator>(begin, end);
    return retval;
}

// Match constraints forward or backward
template<class AddressMap>
MatchedConstraints<AddressMap>
matchConstraints(AddressMap &amap, const AddressMapConstraints<AddressMap> &c, MatchFlags flags) {
    if ((flags & MATCH_BACKWARD) != 0)
        return matchBackward(amap, c, flags);
    return matchForward(amap, c, flags);
}

} // namespace


template<class A, class T = boost::uint8_t>
class AddressMap: public IntervalMap<Interval<A>, AddressSegment<A, T>, AddressMapImpl::SegmentMergePolicy<A, T> > {
    // "Interval" is qualified to work around bug in Microsoft compilers. See doxygen note above.
    typedef IntervalMap<Sawyer::Container::Interval<A>, AddressSegment<A, T>, AddressMapImpl::SegmentMergePolicy<A, T> > Super;

public:
    typedef A Address;                                  
    typedef T Value;                                    
    typedef AddressSegment<A, T> Segment;               
    typedef Sawyer::Container::Buffer<Address, Value> Buffer;
    typedef typename Super::Node Node;                  
    typedef typename Super::ValueIterator SegmentIterator; 
    typedef typename Super::ConstValueIterator ConstSegmentIterator; 
    typedef typename Super::ConstIntervalIterator ConstIntervalIterator; 
    typedef typename Super::NodeIterator NodeIterator;  
    typedef typename Super::ConstNodeIterator ConstNodeIterator; 
private:
    friend class boost::serialization::access;

    template<class S>
    void serialize(S &s, const unsigned /*version*/) {
        s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Super);
    }

public:
    AddressMap() {}

    AddressMap(const AddressMap &other, bool copyOnWrite=false): Super(other) {
        if (copyOnWrite) {
            BOOST_FOREACH (Segment &segment, this->values()) {
                if (const typename Buffer::Ptr &buffer = segment.buffer())
                    buffer->copyOnWrite(true);
            }
        }
    }

    AddressMapConstraints<const AddressMap> require(unsigned x) const {
        return AddressMapConstraints<const AddressMap>(this).require(x);
    }
    AddressMapConstraints<AddressMap> require(unsigned x) {
        return AddressMapConstraints<AddressMap>(this).require(x);
    }
    AddressMapConstraints<const AddressMap> prohibit(unsigned x) const {
        return AddressMapConstraints<const AddressMap>(this).prohibit(x);
    }
    AddressMapConstraints<AddressMap> prohibit(unsigned x) {
        return AddressMapConstraints<AddressMap>(this).prohibit(x);
    }
    AddressMapConstraints<const AddressMap> access(unsigned x) const {
        return AddressMapConstraints<const AddressMap>(this).access(x);
    }
    AddressMapConstraints<AddressMap> access(unsigned x) {
        return AddressMapConstraints<AddressMap>(this).access(x);
    }
    AddressMapConstraints<const AddressMap> substr(const std::string &x) const {
        return AddressMapConstraints<const AddressMap>(this).substr(x);
    }
    AddressMapConstraints<AddressMap> substr(const std::string &x) {
        return AddressMapConstraints<AddressMap>(this).substr(x);
    }
    AddressMapConstraints<const AddressMap> at(Address x) const {
        return AddressMapConstraints<const AddressMap>(this).at(x);
    }
    AddressMapConstraints<AddressMap> at(Address x) {
        return AddressMapConstraints<AddressMap>(this).at(x);
    }
    AddressMapConstraints<const AddressMap> at(const Sawyer::Container::Interval<Address> &x) const {
        return AddressMapConstraints<const AddressMap>(this).at(x);
    }
    AddressMapConstraints<AddressMap> at(const Sawyer::Container::Interval<Address> &x) {
        return AddressMapConstraints<AddressMap>(this).at(x);
    }
    AddressMapConstraints<const AddressMap> limit(size_t x) const {
        return AddressMapConstraints<const AddressMap>(this).limit(x);
    }
    AddressMapConstraints<AddressMap> limit(size_t x) {
        return AddressMapConstraints<AddressMap>(this).limit(x);
    }
    AddressMapConstraints<const AddressMap> atOrAfter(Address x) const {
        return AddressMapConstraints<const AddressMap>(this).atOrAfter(x);
    }
    AddressMapConstraints<AddressMap> atOrAfter(Address x) {
        return AddressMapConstraints<AddressMap>(this).atOrAfter(x);
    }
    AddressMapConstraints<const AddressMap> atOrBefore(Address x) const {
        return AddressMapConstraints<const AddressMap>(this).atOrBefore(x);
    }
    AddressMapConstraints<AddressMap> atOrBefore(Address x) {
        return AddressMapConstraints<AddressMap>(this).atOrBefore(x);
    }
    AddressMapConstraints<const AddressMap> within(const Sawyer::Container::Interval<Address> &x) const {
        return AddressMapConstraints<const AddressMap>(this).within(x);
    }
    AddressMapConstraints<AddressMap> within(const Sawyer::Container::Interval<Address> &x) {
        return AddressMapConstraints<AddressMap>(this).within(x);
    }
    AddressMapConstraints<const AddressMap> within(Address x, Address y) const {
        return AddressMapConstraints<const AddressMap>(this).within(x, y);
    }
    AddressMapConstraints<AddressMap> within(Address x, Address y) {
        return AddressMapConstraints<AddressMap>(this).within(x, y);
    }
    AddressMapConstraints<const AddressMap> baseSize(Address base, Address size) const {
        return AddressMapConstraints<const AddressMap>(this).baseSize(base, size);
    }
    AddressMapConstraints<AddressMap> baseSize(Address base, Address size) {
        return AddressMapConstraints<AddressMap>(this).baseSize(base, size);
    }
    AddressMapConstraints<const AddressMap> after(Address x) const {
        return AddressMapConstraints<const AddressMap>(this).after(x);
    }
    AddressMapConstraints<AddressMap> after(Address x) {
        return AddressMapConstraints<AddressMap>(this).after(x);
    }
    AddressMapConstraints<const AddressMap> before(Address x) const {
        return AddressMapConstraints<const AddressMap>(this).before(x);
    }
    AddressMapConstraints<AddressMap> before(Address x) {
        return AddressMapConstraints<AddressMap>(this).before(x);
    }
    AddressMapConstraints<const AddressMap> singleSegment() const {
        return AddressMapConstraints<const AddressMap>(this).singleSegment();
    }
    AddressMapConstraints<AddressMap> singleSegment() {
        return AddressMapConstraints<AddressMap>(this).singleSegment();
    }
    AddressMapConstraints<const AddressMap> segmentPredicate(SegmentPredicate<Address, Value> *p) const {
        return AddressMapConstraints<const AddressMap>(this).segmentPredicate(p);
    }
    AddressMapConstraints<AddressMap> segmentPredicate(SegmentPredicate<Address, Value> *p) {
        return AddressMapConstraints<AddressMap>(this).segmentPredicate(p);
    }
    AddressMapConstraints<const AddressMap> any() const {
        return AddressMapConstraints<const AddressMap>(this);
    }
    AddressMapConstraints<AddressMap> any() {
        return AddressMapConstraints<AddressMap>(this);
    }
    AddressMapConstraints<const AddressMap> none() const {
        return AddressMapConstraints<const AddressMap>(this).none();
    }
    AddressMapConstraints<AddressMap> none() {
        return AddressMapConstraints<AddressMap>(this).none();
    }
    void checkConsistency() const {
        BOOST_FOREACH (const Node &node, nodes()) {
            const Sawyer::Container::Interval<Address> &interval = node.key();
            const Segment &segment = node.value();
            if (segment.buffer()==NULL) {
                throw std::runtime_error("AddressMap null buffer for interval [" +
                                         boost::lexical_cast<std::string>(interval.least()) +
                                         "," + boost::lexical_cast<std::string>(interval.greatest()) + "]");
            }
            Address bufAvail = segment.buffer()->available(segment.offset());
            if (bufAvail < interval.size()) {
                throw std::runtime_error("AddressMap segment at [" + boost::lexical_cast<std::string>(interval.least()) +
                                         "," + boost::lexical_cast<std::string>(interval.greatest()) + "] points to only " +
                                         boost::lexical_cast<std::string>(bufAvail) + (1==bufAvail?" value":" values") +
                                         " but the interval size is " + boost::lexical_cast<std::string>(interval.size()));
            }
        }
    }
    
    Address nSegments() const { return this->nIntervals(); }

    boost::iterator_range<SegmentIterator> segments() { return this->values(); }
    boost::iterator_range<ConstSegmentIterator> segments() const { return this->values(); }

    boost::iterator_range<ConstSegmentIterator>
    segments(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
        using namespace AddressMapImpl;
        if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
            flags |= MATCH_CONTIGUOUS;
        MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
        return boost::iterator_range<ConstSegmentIterator>(m.nodes_.begin(), m.nodes_.end());
    }

    boost::iterator_range<SegmentIterator>
    segments(const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
        using namespace AddressMapImpl;
        if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
            flags |= MATCH_CONTIGUOUS;
        MatchedConstraints<AddressMap> m = matchConstraints(*this, c, flags);
        return boost::iterator_range<SegmentIterator>(m.nodes_);
    }
    boost::iterator_range<NodeIterator> nodes() { return Super::nodes(); }
    boost::iterator_range<ConstNodeIterator> nodes() const { return Super::nodes(); }
    boost::iterator_range<ConstNodeIterator>
    nodes(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
        using namespace AddressMapImpl;
        if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
            flags |= MATCH_CONTIGUOUS;
        MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
        return m.nodes_;
    }

    boost::iterator_range<NodeIterator>
    nodes(const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
        using namespace AddressMapImpl;
        if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
            flags |= MATCH_CONTIGUOUS;
        MatchedConstraints<AddressMap> m = matchConstraints(*this, c, flags);
        return m.nodes_;
    }
    Optional<Address>
    next(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
        using namespace AddressMapImpl;
        if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
            flags |= MATCH_CONTIGUOUS;
        MatchedConstraints<const AddressMap> m = matchConstraints(*this, c.limit(1), flags);
        return m.interval_.isEmpty() ? Optional<Address>() : Optional<Address>(m.interval_.least());
    }

    Sawyer::Container::Interval<Address>
    available(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
        using namespace AddressMapImpl;
        if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
            flags |= MATCH_CONTIGUOUS;
        return matchConstraints(*this, c, flags).interval_;
    }

    bool exists(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
        return next(c, flags);
    }

    ConstNodeIterator findNode(const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
        return nodes(c.limit(1), flags).begin();
    }
    NodeIterator findNode(const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
        return nodes(c.limit(1), flags).begin();
    }
    Sawyer::Container::Interval<Address>
    unmapped(Address boundary, MatchFlags flags=0) const {
        return (flags & MATCH_BACKWARD) != 0 ? this->lastUnmapped(boundary) : this->firstUnmapped(boundary);
    }

    Optional<Address>
    findFreeSpace(size_t nValues, size_t alignment=1,
                  Sawyer::Container::Interval<Address> restriction = Sawyer::Container::Interval<Address>::whole(),
                  MatchFlags flags=0) const {
        static const Sawyer::Container::Interval<Address> whole = Sawyer::Container::Interval<Address>::whole();
        ASSERT_forbid2(nValues == 0, "cannot determine if this is an overflow or intentional");

        if (restriction.isEmpty())
            return Nothing();

        if (0 == (flags & MATCH_BACKWARD)) {
            Address minAddr = restriction.least();
            while (minAddr <= restriction.greatest()) {
                Sawyer::Container::Interval<Address> interval = unmapped(minAddr, 0 /*forward*/);
                if (interval.isEmpty())
                    return Nothing();
                minAddr = alignUp(interval.least(), alignment);
                Address maxAddr = minAddr + (nValues-1);
                if ((nValues <= interval.size() || 0==interval.size()/*overflow*/) &&
                    minAddr >= interval.least()/*overflow*/ && maxAddr >= interval.least()/*overflow*/ &&
                    maxAddr <= interval.greatest() &&
                    maxAddr <= restriction.greatest()) {
                    return minAddr;
                }
                if (interval.greatest() == whole.greatest())
                    return Nothing();                   // to avoid overflow in next statement
                minAddr = interval.greatest() + 1;
            }
            return Nothing();
        }

        ASSERT_require((flags & MATCH_BACKWARD) != 0);
        Address maxAddr = restriction.greatest();
        while (maxAddr >= restriction.least()) {
            Sawyer::Container::Interval<Address> interval = unmapped(maxAddr, MATCH_BACKWARD);
            if (interval.isEmpty())
                return Nothing();
            Address minAddr = alignDown(interval.greatest() - (nValues-1), alignment);
            maxAddr = minAddr + (nValues-1);
            if ((nValues <= interval.size() || 0==interval.size()/*overflow*/) &&
                minAddr >= interval.least()/*overflow*/ && maxAddr >= interval.least()/*overflow*/ &&
                maxAddr <= interval.greatest() &&
                minAddr >= restriction.least()) {
                return minAddr;
            }
            if (interval.least() == whole.least())
                return Nothing();                       // to avoid overflow in next statement
            maxAddr = interval.least() - 1;
        }
        return Nothing();
    }

    class Visitor {
    public:
        virtual ~Visitor() {}
        virtual bool operator()(const AddressMap&, const Sawyer::Container::Interval<Address>&) = 0;
    };

    template<typename Functor>
    void traverse(Functor &functor, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
        using namespace AddressMapImpl;
        MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
        BOOST_FOREACH (const Node &node, m.nodes_) {
            Sawyer::Container::Interval<Address> part = m.interval_ & node.key();
            if (!functor(*this, part))
                return;
        }
        return;
    }
    template<typename Functor>
    void traverse(Functor &functor, const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
        using namespace AddressMapImpl;
        MatchedConstraints<AddressMap> m = matchConstraints(*this, c, flags);
        BOOST_FOREACH (const Node &node, m.nodes_) {
            Sawyer::Container::Interval<Address> part = m.interval_ & node.key();
            if (!functor(*this, part))
                return;
        }
        return;
    }
    void traverse(Visitor &visitor, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
        traverse<Visitor>(visitor, c, flags);
    }
    void traverse(Visitor &visitor, const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
        traverse<Visitor>(visitor, c, flags);
    }
    Sawyer::Container::Interval<Address>
    read(Value *buf /*out*/, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
        using namespace AddressMapImpl;
        ASSERT_require2(0 == (flags & MATCH_NONCONTIGUOUS), "only contiguous addresses can be read");
        if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
            flags |= MATCH_CONTIGUOUS;
        MatchedConstraints<const AddressMap> m = matchConstraints(*this, c, flags);
        if (buf) {
            BOOST_FOREACH (const Node &node, m.nodes_) {
                Sawyer::Container::Interval<Address> part = m.interval_ & node.key(); // part of segment to read
                ASSERT_forbid(part.isEmpty());
                Address bufferOffset = part.least() - node.key().least() + node.value().offset();
                Address nValues = node.value().buffer()->read(buf, bufferOffset, part.size());
                if (nValues != part.size()) {
                    checkConsistency();
                    ASSERT_not_reachable("something is wrong with the memory map");
                }
                buf += nValues;
            }
        }
        return m.interval_;
    }

    Sawyer::Container::Interval<Address>
    read(std::vector<Value> &buf /*out*/, const AddressMapConstraints<const AddressMap> &c, MatchFlags flags=0) const {
        return buf.empty() ? Sawyer::Container::Interval<Address>() : read(&buf[0], c.limit(buf.size()), flags);
    }
    Sawyer::Container::Interval<Address>
    write(const Value *buf, const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
        using namespace AddressMapImpl;
        ASSERT_require2(0 == (flags & MATCH_NONCONTIGUOUS), "only contiguous addresses can be written");
        if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
            flags |= MATCH_CONTIGUOUS;
        MatchedConstraints<AddressMap> m = matchConstraints(*this, c.prohibit(Access::IMMUTABLE), flags);
        if (buf) {
            BOOST_FOREACH (Node &node, m.nodes_) {
                Segment &segment = node.value();
                Sawyer::Container::Interval<Address> part = m.interval_ & node.key(); // part of segment to write
                ASSERT_forbid(part.isEmpty());
                typename Buffer::Ptr buffer = segment.buffer();
                ASSERT_not_null(buffer);

                if (buffer->copyOnWrite()) {
                    typename Buffer::Ptr newBuffer = buffer->copy(); // copyOnWrite is cleared in newBuffer
                    ASSERT_not_null(newBuffer);
                    for (NodeIterator iter=this->lowerBound(node.key().least()); iter!=nodes().end(); ++iter) {
                        if (iter->value().buffer() == buffer)
                            iter->value().buffer(newBuffer);
                    }
                    buffer = newBuffer;
                }

                Address bufferOffset = part.least() - node.key().least() + segment.offset();
                Address nValues = buffer->write(buf, bufferOffset, part.size());
                if (nValues != part.size()) {
                    checkConsistency();
                    ASSERT_not_reachable("something is wrong with the memory map");
                }
                buf += nValues;
            }
        }
        return m.interval_;
    }

    Sawyer::Container::Interval<Address>
    write(const std::vector<Value> &buf, const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
        return buf.empty() ? Sawyer::Container::Interval<Address>() : write(&buf[0], c.limit(buf.size()), flags);
    }
    void prune(const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
        using namespace AddressMapImpl;
        IntervalSet<Sawyer::Container::Interval<Address> > toErase;
        if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
            flags |= MATCH_NONCONTIGUOUS;
        MatchedConstraints<AddressMap> m = matchConstraints(*this, c.addressConstraints(), flags);
        BOOST_FOREACH (const Node &node, m.nodes_) {
            if (isSatisfied(node, c))
                toErase.insert(node.key() & m.interval_);
        }
        BOOST_FOREACH (const Sawyer::Container::Interval<Address> &interval, toErase.intervals())
            this->erase(interval);
    }

    void keep(const AddressMapConstraints<AddressMap> &c, MatchFlags flags=0) {
        using namespace AddressMapImpl;
        if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
            flags |= MATCH_NONCONTIGUOUS;
        IntervalSet<Sawyer::Container::Interval<Address> > toKeep;
        MatchedConstraints<AddressMap> m = matchConstraints(*this, c.addressConstraints(), flags);
        BOOST_FOREACH (const Node &node, m.nodes_) {
            if (isSatisfied(node, c))
                toKeep.insert(node.key() & m.interval_);
        }
        toKeep.invert();
        BOOST_FOREACH (const Sawyer::Container::Interval<Address> &interval, toKeep.intervals())
            this->erase(interval);
    }

    void changeAccess(unsigned requiredAccess, unsigned prohibitedAccess, const AddressMapConstraints<AddressMap> &c,
                      MatchFlags flags=0) {
        using namespace AddressMapImpl;
        if (0==(flags & (MATCH_CONTIGUOUS|MATCH_NONCONTIGUOUS)))
            flags |= MATCH_NONCONTIGUOUS;
        typedef std::pair<Sawyer::Container::Interval<Address>, Segment> ISPair;
        std::vector<ISPair> newSegments;
        MatchedConstraints<AddressMap> m = matchConstraints(*this, c.addressConstraints(), flags);
        BOOST_FOREACH (Node &node, m.nodes_) {
            Segment &segment = node.value();
            if (isSatisfied(node, c)) {
                unsigned newAccess = (segment.accessibility() | requiredAccess) & ~prohibitedAccess;
                Sawyer::Container::Interval<Address> toChange = node.key() & m.interval_;
                if (toChange == node.key()) {           // all addresses in segment are selected; change segment in place
                    segment.accessibility(newAccess);
                } else {                                // insert a new segment, replacing part of the existing one
                    Segment newSegment(segment);
                    newSegment.accessibility(newAccess);
                    newSegment.offset(segment.offset() + toChange.least() - node.key().least());
                    newSegments.push_back(ISPair(toChange, newSegment));
                }
            }
        }
        BOOST_FOREACH (const ISPair &pair, newSegments)
            this->insert(pair.first, pair.second);
    }
    
private:
    // Increment x if necessary so it is aligned.
    static Address alignUp(Address x, Address alignment) {
        return alignment>0 && x%alignment!=0 ? ((x+alignment-1)/alignment)*alignment : x;
    }

    static Address alignDown(Address x, Address alignment) {
        return alignment>0 && x%alignment!=0 ? (x/alignment)*alignment : x;
    }
};

} // namespace
} // namespace

#endif