1949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org/* 2949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Copyright 2014 Google Inc. 3949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * 4949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Use of this source code is governed by a BSD-style license that can be 5949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * found in the LICENSE file. 6949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 7949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 8949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org#ifndef SkTInternalSList_DEFINED 9949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org#define SkTInternalSList_DEFINED 10949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 11949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org#include "SkTInternalLList.h" // for SkPtrWrapper 12949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 13949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org/** 14949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * This macro creates the methods required by the SkTInternalSList class. 15949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * It should be instantiated in the private block of the class you want to put 16949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * into an SkTInternalSList. 17949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * For most use cases you should use SK_DECLARE_INTERNAL_SLIST_INTERFACE and not 18949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * this macro. If you care about the field name, or want to re-use an existing 19949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * field, then you can use this macro to declare the methods pointing to a 20949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * specific field. 21949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Unlike SK_DECLARE_INTERNAL_SLIST_INTERFACE this does not declare the field 22949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * itself. 23949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * It also makes SkTInternalSList<ClassName> a friend to give it access to the 24949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * methods. 25949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 26949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org#define SK_DECLARE_INTERNAL_SLIST_ADAPTER(ClassName, field) \ 27949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org ClassName* getSListNext() { \ 28949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org return this->field; \ 29949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } \ 30949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org void setSListNext(ClassName* next) { \ 31949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org this->field = next; \ 32949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } \ 33949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org friend class SkTInternalSList<ClassName> 34949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 35949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org/** 36949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * This macro declares an fSListNext that auto initializes to NULL and then 37949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * uses SK_DECLARE_INTERNAL_SLIST_ADAPTER to add the methods needed by 38949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * SkTInternalSList. 39949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * It should be instantiated in the private block of the class you want to put 40949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * into an SkTInternalSList. 41949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 42949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org#define SK_DECLARE_INTERNAL_SLIST_INTERFACE(ClassName) \ 43949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SK_DECLARE_INTERNAL_SLIST_ADAPTER(ClassName, fSListNext); \ 44949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkPtrWrapper<ClassName> fSListNext 45949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 46949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org/** 47949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * An implementation of an intrusive singly linked list. 48949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * The type T must have a methods getSListNext and setSListNext that are visible 49949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * to the list. The easiest way to do this is with 50949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * SK_DECLARE_INTERNAL_SLIST_INTERFACE. 51949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * The list does not maintain ownership of any of its elements, or ever delete 52949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * them. 53949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 54949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.orgtemplate<typename T> class SkTInternalSList { 55949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.orgpublic: 56949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkTInternalSList() : fHead(NULL), fCount(0) {} 57949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 58949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org /** 59949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Push an item onto the head of the list. 60949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * This method is *not* thread safe. 61949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 62949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org void push(T* entry) { 63949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkASSERT(entry->getSListNext() == NULL); 64949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org entry->setSListNext(fHead); 65949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org fHead = entry; 66949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org ++fCount; 67949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 68949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 69949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org /** 70949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Takes all the items from another list and pushes them into this list. 71949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * No ordering guarantees are made, the other list will be emptied. 72949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * This method is *not* thread safe. 73949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 74949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org void pushAll(SkTInternalSList<T>* other) { 75949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org if (this->isEmpty()) { 76949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org this->swap(other); 77949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org return; 78949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 79949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org while (!other->isEmpty()) { 80949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org this->push(other->pop()); 81949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 82949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 83949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 84949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org /** 85949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Pop an item from the head of the list. 86949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Returns NULL if the list is empty. 87949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * This method is *not* thread safe. 88949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 89949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org T* pop() { 90949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org if (NULL == fHead) { 91949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org return NULL; 92949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 93949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org T* result = fHead; 94949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org fHead = result->getSListNext(); 95949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org result->setSListNext(NULL); 96949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org --fCount; 97949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org return result; 98949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 99949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 100949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org T* head() const { 101949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org return fHead; 102949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 103949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 104949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org /** 105949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Returns true if the list has no elements. 106949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 107949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org bool isEmpty() const { 108949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org return NULL == fHead; 109949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 110949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 111949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org /** 112949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Swaps the contents of this list with another one. 113949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * This method is *not* thread safe. 114949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 115949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org void swap(SkTInternalSList<T>* other) { 116949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkTSwap(fHead, other->fHead); 117949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org SkTSwap(fCount, other->fCount); 118949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 119949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 120949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org /** 121949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org * Returns the count of elements in the list. 122949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org */ 123949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org int getCount() const { 124949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org return fCount; 125949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org } 126949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.orgprivate: 127949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org T* fHead; 128949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org int fCount; 129949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org}; 130949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 131949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org 132949b9986de23993f163a324a1234547dd2d09be7commit-bot@chromium.org#endif 133