text: 
  /*
   * Copyright 2006 The Android Open Source Project
   *
   * Use of this source code is governed by a BSD-style license that can be
   * found in the LICENSE file.
   */
  
  
  #include "SkDeque.h"
  
  struct SkDeque::Block {
      Block*  fNext;
      Block*  fPrev;
      char*   fBegin; // start of used section in this chunk
      char*   fEnd;   // end of used section in this chunk
      char*   fStop;  // end of the allocated chunk
  
      char*       start() { return (char*)(this + 1); }
      const char* start() const { return (const char*)(this + 1); }
  
      void init(size_t size) {
          fNext   = fPrev = NULL;
          fBegin  = fEnd = NULL;
          fStop   = (char*)this + size;
      }
  };
  
  SkDeque::SkDeque(size_t elemSize, int allocCount)
          : fElemSize(elemSize)
          , fInitialStorage(NULL)
          , fCount(0)
          , fAllocCount(allocCount) {
      SkASSERT(allocCount >= 1);
      fFrontBlock = fBackBlock = NULL;
      fFront = fBack = NULL;
  }
  
  SkDeque::SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount)
          : fElemSize(elemSize)
          , fInitialStorage(storage)
          , fCount(0)
          , fAllocCount(allocCount) {
      SkASSERT(storageSize == 0 || storage != NULL);
      SkASSERT(allocCount >= 1);
  
      if (storageSize >= sizeof(Block) + elemSize) {
          fFrontBlock = (Block*)storage;
          fFrontBlock->init(storageSize);
      } else {
          fFrontBlock = NULL;
      }
      fBackBlock = fFrontBlock;
      fFront = fBack = NULL;
  }
  
  SkDeque::~SkDeque() {
      Block* head = fFrontBlock;
      Block* initialHead = (Block*)fInitialStorage;
  
      while (head) {
          Block* next = head->fNext;
          if (head != initialHead) {
              this->freeBlock(head);
          }
          head = next;
      }
  }
  
  void* SkDeque::push_front() {
      fCount += 1;
  
      if (NULL == fFrontBlock) {
          fFrontBlock = this->allocateBlock(fAllocCount);
          fBackBlock = fFrontBlock;     // update our linklist
      }
  
      Block*  first = fFrontBlock;
      char*   begin;
  
      if (NULL == 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 (NULL == fFront) {
          SkASSERT(NULL == fBack);
          fFront = fBack = begin;
      } else {
          SkASSERT(NULL != fBack);
          fFront = begin;
      }
  
      return begin;
  }
  
  void* SkDeque::push_back() {
      fCount += 1;
  
      if (NULL == fBackBlock) {
          fBackBlock = this->allocateBlock(fAllocCount);
          fFrontBlock = fBackBlock; // update our linklist
      }
  
      Block*  last = fBackBlock;
      char*   end;
  
      if (NULL == 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 (NULL == fBack) {
          SkASSERT(NULL == fFront);
          fFront = fBack = end;
      } else {
          SkASSERT(NULL != fFront);
          fBack = end;
      }
  
      return end;
  }
  
  void SkDeque::pop_front() {
      SkASSERT(fCount > 0);
      fCount -= 1;
  
      Block*  first = fFrontBlock;
  
      SkASSERT(first != NULL);
  
      if (first->fBegin == NULL) {  // we were marked empty from before
          first = first->fNext;
          first->fPrev = NULL;
          this->freeBlock(fFrontBlock);
          fFrontBlock = first;
          SkASSERT(first != NULL);    // else we popped too far
      }
  
      char* begin = first->fBegin + fElemSize;
      SkASSERT(begin <= first->fEnd);
  
      if (begin < fFrontBlock->fEnd) {
          first->fBegin = begin;
          SkASSERT(NULL != first->fBegin);
          fFront = first->fBegin;
      } else {
          first->fBegin = first->fEnd = NULL;  // mark as empty
          if (NULL == first->fNext) {
              fFront = fBack = NULL;
          } else {
              SkASSERT(NULL != first->fNext->fBegin);
              fFront = first->fNext->fBegin;
          }
      }
  }
  
  void SkDeque::pop_back() {
      SkASSERT(fCount > 0);
      fCount -= 1;
  
      Block* last = fBackBlock;
  
      SkASSERT(last != NULL);
  
      if (last->fEnd == NULL) {  // we were marked empty from before
          last = last->fPrev;
          last->fNext = NULL;
          this->freeBlock(fBackBlock);
          fBackBlock = last;
          SkASSERT(last != NULL);  // else we popped too far
      }
  
      char* end = last->fEnd - fElemSize;
      SkASSERT(end >= last->fBegin);
  
      if (end > last->fBegin) {
          last->fEnd = end;
          SkASSERT(NULL != last->fEnd);
          fBack = last->fEnd - fElemSize;
      } else {
          last->fBegin = last->fEnd = NULL;    // mark as empty
          if (NULL == last->fPrev) {
              fFront = fBack = NULL;
          } else {
              SkASSERT(NULL != last->fPrev->fEnd);
              fBack = last->fPrev->fEnd - fElemSize;
          }
      }
  }
  
  int SkDeque::numBlocksAllocated() const {
      int numBlocks = 0;
  
      for (const Block* temp = fFrontBlock; temp; temp = temp->fNext) {
          ++numBlocks;
      }
  
      return numBlocks;
  }
  
  SkDeque::Block* SkDeque::allocateBlock(int allocCount) {
      Block* newBlock = (Block*)sk_malloc_throw(sizeof(Block) + allocCount * fElemSize);
      newBlock->init(sizeof(Block) + allocCount * fElemSize);
      return newBlock;
  }
  
  void SkDeque::freeBlock(Block* block) {
      sk_free(block);
  }
  
  ///////////////////////////////////////////////////////////////////////////////
  
  SkDeque::Iter::Iter() : fCurBlock(NULL), fPos(NULL), fElemSize(0) {}
  
  SkDeque::Iter::Iter(const SkDeque& d, IterStart startLoc) {
      this->reset(d, startLoc);
  }
  
  // Due to how reset and next work, next actually returns the current element
  // pointed to by fPos and then updates fPos to point to the next one.
  void* SkDeque::Iter::next() {
      char* pos = fPos;
  
      if (pos) {   // if we were valid, try to move to the next setting
          char* next = pos + fElemSize;
          SkASSERT(next <= fCurBlock->fEnd);
          if (next == fCurBlock->fEnd) { // exhausted this chunk, move to next
              do {
                  fCurBlock = fCurBlock->fNext;
              } while (fCurBlock != NULL && fCurBlock->fBegin == NULL);
              next = fCurBlock ? fCurBlock->fBegin : NULL;
          }
          fPos = next;
      }
      return pos;
  }
  
  // Like next, prev actually returns the current element pointed to by fPos and
  // then makes fPos point to the previous element.
  void* SkDeque::Iter::prev() {
      char* pos = fPos;
  
      if (pos) {   // if we were valid, try to move to the prior setting
          char* prev = pos - fElemSize;
          SkASSERT(prev >= fCurBlock->fBegin - fElemSize);
          if (prev < fCurBlock->fBegin) { // exhausted this chunk, move to prior
              do {
                  fCurBlock = fCurBlock->fPrev;
              } while (fCurBlock != NULL && fCurBlock->fEnd == NULL);
              prev = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL;
          }
          fPos = prev;
      }
      return pos;
  }
  
  // reset works by skipping through the spare blocks at the start (or end)
  // of the doubly linked list until a non-empty one is found. The fPos
  // member is then set to the first (or last) element in the block. If
  // there are no elements in the deque both fCurBlock and fPos will come
  // out of this routine NULL.
  void SkDeque::Iter::reset(const SkDeque& d, IterStart startLoc) {
      fElemSize = d.fElemSize;
  
      if (kFront_IterStart == startLoc) {
          // initialize the iterator to start at the front
          fCurBlock = d.fFrontBlock;
          while (NULL != fCurBlock && NULL == fCurBlock->fBegin) {
              fCurBlock = fCurBlock->fNext;
          }
          fPos = fCurBlock ? fCurBlock->fBegin : NULL;
      } else {
          // initialize the iterator to start at the back
          fCurBlock = d.fBackBlock;
          while (NULL != fCurBlock && NULL == fCurBlock->fEnd) {
              fCurBlock = fCurBlock->fPrev;
          }
          fPos = fCurBlock ? fCurBlock->fEnd - fElemSize : NULL;
      }
  }
  