SkDeque Class Reference

#include <SkDeque.h>

Classes
struct	Block
class	F2BIter
class	Iter

Public Member Functions
	SkDeque (size_t elemSize, int allocCount=1)
	SkDeque (size_t elemSize, void *storage, size_t storageSize, int allocCount=1)
	~SkDeque ()
bool	empty () const
int	count () const
size_t	elemSize () const
const void *	front () const
const void *	back () const
void *	front ()
void *	back ()
void *	push_front ()
void *	push_back ()
void	pop_front ()
void	pop_back ()

Friends
class	DequeUnitTestHelper

Detailed Description

Definition at line 28 of file SkDeque.h.

Constructor & Destructor Documentation

SkDeque() [1/2]

SkDeque::SkDeque ( size_t  elemSize, int  allocCount = 1  )

explicit

elemSize specifies the size of each individual element in the deque allocCount specifies how many elements are to be allocated as a block

Definition at line 31 of file SkDeque.cpp.

        : fElemSize(elemSize)
        , fInitialStorage(nullptr)
        , fCount(0)
        , fAllocCount(allocCount) {
    SkASSERT(allocCount >= 1);
    fFrontBlock = fBackBlock = nullptr;
    fFront = fBack = nullptr;
}

SkDeque() [2/2]

SkDeque::SkDeque	(	size_t	elemSize,
		void *	storage,
		size_t	storageSize,
		int	allocCount = 1
	)

Definition at line 41 of file SkDeque.cpp.

        : fElemSize(elemSize)
        , fInitialStorage(storage)
        , fCount(0)
        , fAllocCount(allocCount) {
    SkASSERT(storageSize == 0 || storage != nullptr);
    SkASSERT(allocCount >= 1);
 
    if (storageSize >= sizeof(Block) + elemSize) {
        fFrontBlock = (Block*)storage;
        fFrontBlock->init(storageSize);
    } else {
        fFrontBlock = nullptr;
    }
    fBackBlock = fFrontBlock;
    fFront = fBack = nullptr;
}

~SkDeque()

SkDeque::~SkDeque

(

)

Definition at line 59 of file SkDeque.cpp.

                  {
    Block* head = fFrontBlock;
    Block* initialHead = (Block*)fInitialStorage;
 
    while (head) {
        Block* next = head->fNext;
        if (head != initialHead) {
            this->freeBlock(head);
        }
        head = next;
    }
}

Member Function Documentation

back() [1/2]

void * SkDeque::back ( )

inline

Definition at line 46 of file SkDeque.h.

{ return fBack; }

back() [2/2]

const void * SkDeque::back ( ) const

inline

Definition at line 43 of file SkDeque.h.

{ return fBack; }

count()

int SkDeque::count ( ) const

inline

Definition at line 39 of file SkDeque.h.

{ return fCount; }

elemSize()

size_t SkDeque::elemSize ( ) const

inline

Definition at line 40 of file SkDeque.h.

{ return fElemSize; }

empty()

bool SkDeque::empty ( ) const

inline

Definition at line 38 of file SkDeque.h.

{ return 0 == fCount; }

front() [1/2]

void * SkDeque::front ( )

inline

Definition at line 45 of file SkDeque.h.

{ return fFront; }

front() [2/2]

const void * SkDeque::front ( ) const

inline

Definition at line 42 of file SkDeque.h.

{ return fFront; }

pop_back()

void SkDeque::pop_back

(

)

Definition at line 187 of file SkDeque.cpp.

                       {
    SkASSERT(fCount > 0);
    fCount -= 1;
 
    Block* last = fBackBlock;
 
    SkASSERT(last != nullptr);
 
    if (last->fEnd == nullptr) {  // we were marked empty from before
        last = last->fPrev;
        SkASSERT(last != nullptr);  // else we popped too far
        last->fNext = nullptr;
        this->freeBlock(fBackBlock);
        fBackBlock = last;
    }
 
    char* end = last->fEnd - fElemSize;
    SkASSERT(end >= last->fBegin);
 
    if (end > last->fBegin) {
        last->fEnd = end;
        SkASSERT(last->fEnd);
        fBack = last->fEnd - fElemSize;
    } else {
        last->fBegin = last->fEnd = nullptr;    // mark as empty
        if (nullptr == last->fPrev) {
            fFront = fBack = nullptr;
        } else {
            SkASSERT(last->fPrev->fEnd);
            fBack = last->fPrev->fEnd - fElemSize;
        }
    }
}

pop_front()

void SkDeque::pop_front

(

)

Definition at line 153 of file SkDeque.cpp.

                        {
    SkASSERT(fCount > 0);
    fCount -= 1;
 
    Block*  first = fFrontBlock;
 
    SkASSERT(first != nullptr);
 
    if (first->fBegin == nullptr) {  // we were marked empty from before
        first = first->fNext;
        SkASSERT(first != nullptr);    // else we popped too far
        first->fPrev = nullptr;
        this->freeBlock(fFrontBlock);
        fFrontBlock = first;
    }
 
    char* begin = first->fBegin + fElemSize;
    SkASSERT(begin <= first->fEnd);
 
    if (begin < fFrontBlock->fEnd) {
        first->fBegin = begin;
        SkASSERT(first->fBegin);
        fFront = first->fBegin;
    } else {
        first->fBegin = first->fEnd = nullptr;  // mark as empty
        if (nullptr == first->fNext) {
            fFront = fBack = nullptr;
        } else {
            SkASSERT(first->fNext->fBegin);
            fFront = first->fNext->fBegin;
        }
    }
}

push_back()

void * SkDeque::push_back

(

)

Definition at line 112 of file SkDeque.cpp.

                         {
    fCount += 1;
 
    if (nullptr == fBackBlock) {
        fBackBlock = this->allocateBlock(fAllocCount);
        fFrontBlock = fBackBlock; // update our linklist
    }
 
    Block*  last = fBackBlock;
    char*   end;
 
    if (nullptr == last->fBegin) {
    INIT_CHUNK:
        last->fBegin = last->start();
        end = last->fBegin + fElemSize;
    } else {
        end = last->fEnd + fElemSize;
        if (end > last->fStop) {  // no more room in this chunk
            // should we alloc more as we accumulate more elements?
            last = this->allocateBlock(fAllocCount);
            last->fPrev = fBackBlock;
            fBackBlock->fNext = last;
            fBackBlock = last;
            goto INIT_CHUNK;
        }
    }
 
    last->fEnd = end;
    end -= fElemSize;
 
    if (nullptr == fBack) {
        SkASSERT(nullptr == fFront);
        fFront = fBack = end;
    } else {
        SkASSERT(fFront);
        fBack = end;
    }
 
    return end;
}

push_front()

void * SkDeque::push_front

(

)

push_front and push_back return a pointer to the memory space for the new element

Definition at line 72 of file SkDeque.cpp.

                          {
    fCount += 1;
 
    if (nullptr == fFrontBlock) {
        fFrontBlock = this->allocateBlock(fAllocCount);
        fBackBlock = fFrontBlock;     // update our linklist
    }
 
    Block*  first = fFrontBlock;
    char*   begin;
 
    if (nullptr == first->fBegin) {
    INIT_CHUNK:
        first->fEnd = first->fStop;
        begin = first->fStop - fElemSize;
    } else {
        begin = first->fBegin - fElemSize;
        if (begin < first->start()) {    // no more room in this chunk
            // should we alloc more as we accumulate more elements?
            first = this->allocateBlock(fAllocCount);
            first->fNext = fFrontBlock;
            fFrontBlock->fPrev = first;
            fFrontBlock = first;
            goto INIT_CHUNK;
        }
    }
 
    first->fBegin = begin;
 
    if (nullptr == fFront) {
        SkASSERT(nullptr == fBack);
        fFront = fBack = begin;
    } else {
        SkASSERT(fBack);
        fFront = begin;
    }
 
    return begin;
}

Friends And Related Function Documentation

DequeUnitTestHelper

friend class DequeUnitTestHelper

friend

Definition at line 113 of file SkDeque.h.

---

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

• third_party/skia/include/private/base/SkDeque.h
• third_party/skia/src/base/SkDeque.cpp