ExtentMap.C

Go to the documentation of this file.

/* The ExtentMap class. This class is similar std::map<rose_addr_t,rose_addr_t> where the two addresses are the starting
 * offset and size.  The main difference is that if two adjacent extents are added to the map they will be condensed into a
 * single extent.  This class is used to keep track of what parts of a binary file have been parsed, and is also used to
 * manage string table free lists, among other things. */

#include "sage3basic.h"

char
ExtentMap::category(const Extent &a, const Extent &b)
{
    if (a.relaxed_first()==b.relaxed_first() && a.size()==b.size())
        return 'C';
    if (a.relaxed_first()+a.size() <= b.relaxed_first())
        return 'L';
    if (a.relaxed_first() >= b.relaxed_first()+b.size())
        return 'R';
    if (a.relaxed_first() <= b.relaxed_first() && a.relaxed_first()+a.size() >= b.relaxed_first()+b.size())
        return 'O';
    if (a.relaxed_first() >= b.relaxed_first() && a.relaxed_first()+a.size() <= b.relaxed_first()+b.size())
        return 'I';
    if (a.relaxed_first() <= b.relaxed_first()) /*already know a.first+a.size > b.first*/
        return 'B';
    return 'E';
}

Extent
ExtentMap::allocate_best_fit(rose_addr_t size)
{
    iterator found = best_fit(size, begin());
    if (found==end())
        throw std::bad_alloc();
    Extent retval(found->first.first(), size);
    erase(retval);
    return retval;
}

Extent
ExtentMap::allocate_first_fit(rose_addr_t size)
{
    iterator found = first_fit(size, begin());
    if (found==end())
        throw std::bad_alloc();
    Extent retval(found->first.first(), size);
    erase(retval);
    return retval;
}

void
ExtentMap::allocate_at(const Extent &request)
{
    ROSE_ASSERT(subtract_from(request).size()==0); /*entire request should be on free list*/
    erase(request);
}

#if 0 /* NOT NEEDED BY ANYTHING? [RPM 2011-10-18] */

void
ExtentMap::precipitate(rose_addr_t reagent)
{
    abort(); // NOT IMPLEMENTED
    ExtentMap result;
    for (iterator i=begin(); i!=end(); /*void*/) {
        ExtentPair left = *i++;
        for (/*void*/; i!=end() && left.first+left.second+reagent >= i->first; i++)
            left.second = (i->first + i->second) - left.first;
        result.insert(left);
    }
    *this = result;
}
#endif

#if 0 /* NOT NEEDED BY ANYTHING? [RPM 2011-10-18] */

ExtentPair
ExtentMap::find_address(rose_addr_t addr) const
{
    const_iterator i = upper_bound(addr);
    RangeMapType::const_iterator i2 = ranges.find(addr);
    if (i==begin()) {
        assert(i2==ranges.end());
        throw std::bad_alloc();
    }
    --i;
    if (i->first+i->second <= addr) {
        assert(i2==ranges.end());
        throw std::bad_alloc();
    }

    assert(i->first==i2->first.begin);
    assert(i->second==i2->first.size);
    return *i;
}
#endif

#if 0 /* NOT NEEDED BY ANYTHING? [RPM 2011-10-18] */

bool
ExtentMap::exists_all(ExtentPair what) const
{
    while (what.second>0) {
        try {
            ExtentPair found = find_address(what.first);
            assert(found.second > 0);
            assert(found.first <= what.first);
            assert(what.first <= found.first + found.second);
            rose_addr_t nfound = std::min(what.second, found.second-(what.first-found.first));
            what.first = found.first + found.second;
            what.second -= nfound;
        } catch (const std::bad_alloc&) { // thrown by find_address()
            assert(!ranges.contains(RangeType(what.first, what.second)));
            return false;
        }
    }
    assert(ranges.contains(RangeType(what.first, what.second)));
    return true;
}
#endif

void
ExtentMap::dump_extents(std::ostream &o, const std::string &prefix, const std::string &label) const
{
    using namespace StringUtility;
    size_t idx=0;
    for (const_iterator i=begin(); i!=end(); ++i, ++idx) {
        o <<prefix <<(label.empty()?std::string("Extent"):label) <<"[" <<idx <<"]"
          <<" = offset " <<unsignedToHex(i->first.first())
          <<" for " <<unsignedToHex(i->first.size()) <<(1==i->first.size()?" byte":" bytes")
          <<" ending at " <<unsignedToHex(i->first.first() + i->first.size()) <<"\n";
    }
}
    

void
ExtentMap::dump_extents(FILE *f, const char *prefix, const char *label, bool pad) const
{
    char p[4096];
    size_t idx=0;
    for (const_iterator i=begin(); i!=end(); ++i, ++idx) {
        if (!label) label = "Extent";
        sprintf(p, "%s%s[%zd]", prefix, label, idx);
        int w = pad ? std::max(1, DUMP_FIELD_WIDTH-(int)strlen(p)) : 1;
        fprintf(f, "%s%-*s = offset 0x%08"PRIx64" (%"PRIu64"),"
                " for 0x%08"PRIx64" (%"PRIu64") byte%s,"
                " ending at 0x%08"PRIx64" (%"PRIu64")\n",
                p, w, "", i->first.first(), i->first.first(),
                i->first.size(), i->first.size(), 1==i->first.size()?"":"s", 
                i->first.first()+i->first.size(), i->first.first()+i->first.size());
    }
}