inet::ChunkBuffer Class Reference

This class provides basic functionality for merging large data chunks from out of order smaller data chunks. More...

#include <ChunkBuffer.h>

Inheritance diagram for inet::ChunkBuffer:

Classes
class	Region

Public Member Functions
Constructors, destructors and duplication related functions
	ChunkBuffer (const char *name=nullptr)
	ChunkBuffer (const ChunkBuffer &other)
virtual ChunkBuffer *	dup () const override
Content querying functions
bool	isEmpty () const
	Returns true if the buffer is completely empty. More...
int	getNumRegions () const
	Returns the number non-overlapping, non-connecting but continuous regions. More...
b	getRegionLength (int index) const
	Returns the length of the given region. More...
b	getRegionStartOffset (int index) const
	Returns the start offset of the given region. More...
b	getRegionEndOffset (int index) const
	Returns the end offset of the given region. More...
const Ptr< const Chunk > &	getRegionData (int index) const
	Returns the data of the given region in its current representation. More...
void	replace (b offset, const Ptr< const Chunk > &chunk)
	Replaces the stored data at the provided offset with the data in the chunk. More...
void	clear (b offset, b length)
	Erases the stored data at the provided offset and length. More...
void	clear ()
	Erases all of the stored data. More...
virtual std::string	str () const override
	Returns a human readable string representation. More...

Protected Member Functions
Region *	getRegion (int i) const
void	eraseEmptyRegions (std::vector< Region >::iterator begin, std::vector< Region >::iterator end)
void	sliceRegions (Region &newRegion)
void	mergeRegions (Region &previousRegion, Region &nextRegion)

Protected Attributes
std::vector< Region >	regions
	The list of non-overlapping, non-connecting but continuous regions. More...

Friends
class	ChunkBufferDescriptor
class	ChunkBuffer__RegionDescriptor

Detailed Description

This class provides basic functionality for merging large data chunks from out of order smaller data chunks.

Internally, buffers stores the data in different kind of chunks. See the Chunk class and its subclasses for details. All chunks are immutable in a buffer. Chunks are automatically merged as they are replaced in the buffer, and they are also shared among buffers when duplicating.

In general, this class supports the following operations:

• push at the tail and pop at the head
• query the length
• serialize to and deserialize from a sequence of bits or bytes
• copy to a new queue
• convert to a human readable string

Constructor & Destructor Documentation

ChunkBuffer() [1/2]

inet::ChunkBuffer::ChunkBuffer

(

const char *

name = nullptr

)

                                         :
    cNamedObject(name)
{
}

ChunkBuffer() [2/2]

inet::ChunkBuffer::ChunkBuffer

(

const ChunkBuffer &

other

)

                                                 :
    cNamedObject(other),
    regions(other.regions)
{
}

Member Function Documentation

clear() [1/2]

void inet::ChunkBuffer::clear ( )

inline

Erases all of the stored data.

{ regions.clear(); }

Referenced by inet::ReorderBuffer::popAvailableData().

clear() [2/2]

void inet::ChunkBuffer::clear	(	b	offset,
		b	length
	)

Erases the stored data at the provided offset and length.

{
    CHUNK_CHECK_USAGE(offset >= b(0), "offset is invalid");
    CHUNK_CHECK_USAGE(length >= b(0), "length is invalid");
    for (auto it = regions.begin(); it != regions.end(); it++) {
        auto region = *it;
        if (region.offset == offset && region.data->getChunkLength() == length) {
            regions.erase(it);
            return;
        }
    }
    auto data = makeShared<ByteCountChunk>(length);
    Region clearedRegion(offset, data);
    sliceRegions(clearedRegion);
}

Referenced by inet::tcp::TcpReceiveQueue::init().

dup()

virtual ChunkBuffer* inet::ChunkBuffer::dup ( ) const

inlineoverridevirtual

{ return new ChunkBuffer(*this); }

eraseEmptyRegions()

void inet::ChunkBuffer::eraseEmptyRegions ( std::vector< Region >::iterator  begin, std::vector< Region >::iterator  end  )

protected

{
    // NOTE: begin and end are inclusive
    CHUNK_CHECK_IMPLEMENTATION(begin != regions.end());
    CHUNK_CHECK_IMPLEMENTATION(end != regions.end());
    regions.erase(std::remove_if(begin, end + 1, [] (const Region& region) { return region.data == nullptr; }), end + 1);
}

Referenced by replace().

getNumRegions()

int inet::ChunkBuffer::getNumRegions ( ) const

inline

Returns the number non-overlapping, non-connecting but continuous regions.

{ return regions.size(); }

Referenced by inet::tcp::TcpReceiveQueue::getAmountOfBufferedBytes(), inet::tcp::TcpReceiveQueue::getFirstSeqNo(), inet::tcp::TcpReceiveQueue::getLE(), inet::tcp::TcpReceiveQueue::getQueueLength(), inet::tcp::TcpReceiveQueue::getQueueStatus(), inet::tcp::TcpReceiveQueue::getRE(), inet::tcp::TcpReceiveQueue::insertBytesFromSegment(), and inet::tcp::TcpReceiveQueue::str().

getRegion()

Region* inet::ChunkBuffer::getRegion ( int  i ) const

inlineprotected

{ return const_cast<Region *>(&regions[i]); } // only for class descriptor

getRegionData()

const Ptr<const Chunk>& inet::ChunkBuffer::getRegionData ( int  index ) const

inline

Returns the data of the given region in its current representation.

{ return regions.at(index).data; }

getRegionEndOffset()

b inet::ChunkBuffer::getRegionEndOffset ( int  index ) const

inline

Returns the end offset of the given region.

{ return regions.at(index).getEndOffset(); }

Referenced by inet::tcp::TcpReceiveQueue::getLE(), inet::tcp::TcpReceiveQueue::getRE(), inet::tcp::TcpReceiveQueue::insertBytesFromSegment(), and inet::tcp::TcpReceiveQueue::str().

getRegionLength()

b inet::ChunkBuffer::getRegionLength ( int  index ) const

inline

Returns the length of the given region.

{ return regions.at(index).data->getChunkLength(); }

Referenced by inet::tcp::TcpReceiveQueue::getAmountOfBufferedBytes(), and inet::tcp::TcpReceiveQueue::insertBytesFromSegment().

getRegionStartOffset()

b inet::ChunkBuffer::getRegionStartOffset ( int  index ) const

inline

Returns the start offset of the given region.

{ return regions.at(index).offset; }

Referenced by inet::tcp::TcpReceiveQueue::getFirstSeqNo(), inet::tcp::TcpReceiveQueue::getLE(), inet::tcp::TcpReceiveQueue::getRE(), inet::tcp::TcpReceiveQueue::insertBytesFromSegment(), and inet::tcp::TcpReceiveQueue::str().

isEmpty()

bool inet::ChunkBuffer::isEmpty ( ) const

inline

Returns true if the buffer is completely empty.

{ return regions.empty(); }

Referenced by inet::tcp::TcpReceiveQueue::extractBytesUpTo(), and inet::tcp::TcpReceiveQueue::insertBytesFromSegment().

mergeRegions()

void inet::ChunkBuffer::mergeRegions ( Region &  previousRegion, Region &  nextRegion  )

protected

{
    CHUNK_CHECK_IMPLEMENTATION(previousRegion.data != nullptr);
    CHUNK_CHECK_IMPLEMENTATION(nextRegion.data != nullptr);
    if (previousRegion.getEndOffset() == nextRegion.getStartOffset()) {
        // consecutive regions
        if (previousRegion.data->canInsertAtBack(nextRegion.data)) {
            // merge into previous
            const auto& newData = makeExclusivelyOwnedMutableChunk(previousRegion.data);
            newData->insertAtBack(nextRegion.data);
            newData->markImmutable();
            previousRegion.data = newData->simplify();
            nextRegion.data = nullptr;
        }
        else if (nextRegion.data->canInsertAtFront(previousRegion.data)) {
            // merge into next
            const auto& newData = makeExclusivelyOwnedMutableChunk(nextRegion.data);
            newData->insertAtFront(previousRegion.data);
            newData->markImmutable();
            nextRegion.data = newData->simplify();
            nextRegion.offset = previousRegion.offset;
            previousRegion.data = nullptr;
        }
        else {
            // merge as a sequence
            auto sequenceChunk = makeShared<SequenceChunk>();
            sequenceChunk->insertAtBack(previousRegion.data);
            sequenceChunk->insertAtBack(nextRegion.data);
            sequenceChunk->markImmutable();
            previousRegion.data = sequenceChunk;
            nextRegion.data = nullptr;
        }
    }
}

Referenced by replace().

replace()

void inet::ChunkBuffer::replace	(	b	offset,
		const Ptr< const Chunk > &	chunk
	)

Replaces the stored data at the provided offset with the data in the chunk.

Already existing data gets overwritten, and connecting data gets merged with the provided chunk.

{
    CHUNK_CHECK_USAGE(offset >= b(0), "offset is invalid");
    CHUNK_CHECK_USAGE(chunk != nullptr, "chunk is nullptr");
    CHUNK_CHECK_USAGE(chunk->getChunkLength() > b(0), "chunk is empty");
    constPtrCast<Chunk>(chunk)->markImmutable();
    Region newRegion(offset, chunk);
    sliceRegions(newRegion);
    if (regions.empty())
        regions.push_back(newRegion);
    else if (regions.back().getEndOffset() <= offset) {
        regions.push_back(newRegion);
        mergeRegions(regions[regions.size() - 2], regions[regions.size() - 1]);
        eraseEmptyRegions(regions.end() - 2, regions.end() - 1);
    }
    else if (offset + chunk->getChunkLength() <= regions.front().getStartOffset()) {
        regions.insert(regions.begin(), newRegion);
        mergeRegions(regions[0], regions[1]);
        eraseEmptyRegions(regions.begin(), regions.begin() + 1);
    }
    else {
        auto it = std::upper_bound(regions.begin(), regions.end(), newRegion, Region::compareStartOffset);
        it = regions.insert(it, newRegion);
        auto& previousRegion = *(it - 1);
        auto& region = *it;
        auto& nextRegion = *(it + 1);
        if (it != regions.begin())
            mergeRegions(previousRegion, region);
        if (it + 1 != regions.end())
            mergeRegions(region.data != nullptr ? region : previousRegion, nextRegion);
        eraseEmptyRegions(it != regions.begin() ? it - 1 : it, it + 1 != regions.end() ? it + 1 : it);
    }
}

Referenced by inet::Ipv4FragBuf::addFragment(), inet::Ipv6FragBuf::addFragment(), and inet::tcp::TcpReceiveQueue::insertBytesFromSegment().

sliceRegions()

void inet::ChunkBuffer::sliceRegions ( Region &  newRegion )

protected

{
    if (!regions.empty()) {
        auto lowerit = std::lower_bound(regions.begin(), regions.end(), newRegion, Region::compareStartOffset);
        if (lowerit != regions.begin())
            lowerit--;
        auto upperit = std::upper_bound(regions.begin(), regions.end(), newRegion, Region::compareEndOffset);
        if (upperit != regions.end())
            upperit++;
        for (auto it = lowerit; it < upperit; it++) {
            auto& oldRegion = *it;
            if (newRegion.getEndOffset() <= oldRegion.getStartOffset() || oldRegion.getEndOffset() <= newRegion.getStartOffset())
                // no intersection
                continue;
            else if (newRegion.getStartOffset() <= oldRegion.getStartOffset() && oldRegion.getEndOffset() <= newRegion.getEndOffset()) {
                // new totally covers old
                oldRegion.data = nullptr;
                regions.erase(it--);
                upperit--;
            }
            else if (oldRegion.getStartOffset() < newRegion.getStartOffset() && newRegion.getEndOffset() < oldRegion.getEndOffset()) {
                // new splits old into two parts
                Region previousRegion(oldRegion.getStartOffset(), oldRegion.data->peek(b(0), newRegion.getStartOffset() - oldRegion.getStartOffset()));
                Region nextRegion(newRegion.getEndOffset(), oldRegion.data->peek(newRegion.getEndOffset() - oldRegion.getStartOffset(), oldRegion.getEndOffset() - newRegion.getEndOffset()));
                oldRegion.offset = nextRegion.offset;
                oldRegion.data = nextRegion.data;
                regions.insert(it, previousRegion);
                return;
            }
            else if (oldRegion.getEndOffset() <= newRegion.getEndOffset()) {
                // new cuts end of old
                oldRegion.data = oldRegion.data->peek(b(0), newRegion.getStartOffset() - oldRegion.getStartOffset());
            }
            else if (newRegion.getStartOffset() <= oldRegion.getStartOffset()) {
                // new cuts beginning of old
                oldRegion.data = oldRegion.data->peek(newRegion.getEndOffset() - oldRegion.getStartOffset(), oldRegion.getEndOffset() - newRegion.getEndOffset());
                oldRegion.offset = newRegion.getEndOffset();
            }
            else
                CHUNK_CHECK_IMPLEMENTATION(false);
        }
    }
}

Referenced by clear(), and replace().

str()

std::string inet::ChunkBuffer::str ( ) const

overridevirtual

Returns a human readable string representation.

{
    std::ostringstream os;
    os << "ChunkBuffer, regions = {";
    bool first = true;
    for (auto& region : regions) {
        if (!first)
            os << " | ";
        else
            first = false;
        os << EV_FIELD(offset, region.offset) << ", chunk = ";
        if (region.data == nullptr)
            os << "<nullptr>";
        else
            os << region.data;
    }
    os << "}";
    return os.str();
}

Referenced by inet::operator<<().

Friends And Related Function Documentation

ChunkBuffer__RegionDescriptor

friend class ChunkBuffer__RegionDescriptor

friend

ChunkBufferDescriptor

friend class ChunkBufferDescriptor

friend

Member Data Documentation

regions

std::vector<Region> inet::ChunkBuffer::regions

protected

The list of non-overlapping, non-connecting but continuous regions.

Referenced by clear(), eraseEmptyRegions(), inet::ReorderBuffer::getAvailableDataLength(), inet::ReorderBuffer::popAvailableData(), replace(), sliceRegions(), and str().

---

The documentation for this class was generated from the following files:

• ChunkBuffer.h
• ChunkBuffer.cc