1bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com/* 2bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com * Copyright 2012 Google Inc. 3bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com * 4bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com * Use of this source code is governed by a BSD-style license that can be 5bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com * found in the LICENSE file. 6bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com */ 7bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 84c2443e36fdc6c095b17e90baa4a2f26a6f00b08bsalomon@google.com#ifndef SkTLList_DEFINED 94c2443e36fdc6c095b17e90baa4a2f26a6f00b08bsalomon@google.com#define SkTLList_DEFINED 104c2443e36fdc6c095b17e90baa4a2f26a6f00b08bsalomon@google.com 11bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#include "SkTInternalLList.h" 12bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#include "SkTemplates.h" 13bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 14dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.comtemplate <typename T> class SkTLList; 15dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.comtemplate <typename T> 16dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.cominline void* operator new(size_t, SkTLList<T>* list, 17dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com typename SkTLList<T>::Placement placement, 18dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com const typename SkTLList<T>::Iter& location); 19dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 20bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com/** Doubly-linked list of objects. The objects' lifetimes are controlled by the list. I.e. the 21bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com the list creates the objects and they are deleted upon removal. This class block-allocates 22dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com space for entries based on a param passed to the constructor. 23dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 24dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com Elements of the list can be constructed in place using the following macros: 25dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args) 26dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args) 27dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com where list is a SkTLList<type_name>*, location is an iterator, and args is the paren-surrounded 28dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com constructor arguments for type_name. These macros behave like addBefore() and addAfter(). 29dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com*/ 30bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.comtemplate <typename T> 31e3beb6bd7de7fa211681abbb0be58e80b19885e0commit-bot@chromium.orgclass SkTLList : SkNoncopyable { 32bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.comprivate: 33bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com struct Block; 34bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com struct Node { 35bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com char fObj[sizeof(T)]; 36bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SK_DECLARE_INTERNAL_LLIST_INTERFACE(Node); 37bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Block* fBlock; // owning block. 38bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com }; 39bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com typedef SkTInternalLList<Node> NodeList; 40bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 41bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.compublic: 42dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 43dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com class Iter; 44dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 45bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com /** allocCnt is the number of objects to allocate as a group. In the worst case fragmentation 46bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com each object is using the space required for allocCnt unfragmented objects. */ 47bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkTLList(int allocCnt = 1) : fCount(0), fAllocCnt(allocCnt) { 48bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(allocCnt > 0); 49bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->validate(); 50bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 51bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 52bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ~SkTLList() { 53bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->validate(); 54bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com typename NodeList::Iter iter; 55bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Node* node = iter.init(fList, Iter::kHead_IterStart); 5649f085dddff10473b6ebf832a974288300224e60bsalomon while (node) { 57dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com SkTCast<T*>(node->fObj)->~T(); 58bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Block* block = node->fBlock; 59bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com node = iter.next(); 60bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com if (0 == --block->fNodesInUse) { 61bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com for (int i = 0; i < fAllocCnt; ++i) { 62bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com block->fNodes[i].~Node(); 63bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 64bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com sk_free(block); 65bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 66bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 67bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 68e659c2e820de0b8d12d81247ed4430022ded0a90skia.committer@gmail.com 69c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com T* addToHead(const T& t) { 70bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->validate(); 71bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Node* node = this->createNode(); 72bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com fList.addToHead(node); 73bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkNEW_PLACEMENT_ARGS(node->fObj, T, (t)); 74bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->validate(); 75c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com return reinterpret_cast<T*>(node->fObj); 76bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 77bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 78b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org T* addToHead() { 79b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org this->validate(); 80b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org Node* node = this->createNode(); 81b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org fList.addToHead(node); 82b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org SkNEW_PLACEMENT(node->fObj, T); 83b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org this->validate(); 84b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org return reinterpret_cast<T*>(node->fObj); 85b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org } 86b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org 87c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com T* addToTail(const T& t) { 88bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->validate(); 89bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Node* node = this->createNode(); 90bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com fList.addToTail(node); 91bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkNEW_PLACEMENT_ARGS(node->fObj, T, (t)); 92bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->validate(); 93c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com return reinterpret_cast<T*>(node->fObj); 94bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 95bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 96b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org T* addToTail() { 97b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org this->validate(); 98b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org Node* node = this->createNode(); 99b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org fList.addToTail(node); 100b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org SkNEW_PLACEMENT(node->fObj, T); 101b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org this->validate(); 102b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org return reinterpret_cast<T*>(node->fObj); 103b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org } 104b511be5a9b6bf194062b79206ac1ec0204aed8eecommit-bot@chromium.org 105dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com /** Adds a new element to the list before the location indicated by the iterator. If the 106dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com iterator refers to a NULL location then the new element is added at the tail */ 107c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com T* addBefore(const T& t, const Iter& location) { 108c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com return SkNEW_PLACEMENT_ARGS(this->internalAddBefore(location), T, (t)); 109dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com } 110dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 111dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com /** Adds a new element to the list after the location indicated by the iterator. If the 112dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com iterator refers to a NULL location then the new element is added at the head */ 113c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com T* addAfter(const T& t, const Iter& location) { 114c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com return SkNEW_PLACEMENT_ARGS(this->internalAddAfter(location), T, (t)); 115dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com } 116dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 117dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com /** Convenience methods for getting an iterator initialized to the head/tail of the list. */ 118dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com Iter headIter() const { return Iter(*this, Iter::kHead_IterStart); } 119dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com Iter tailIter() const { return Iter(*this, Iter::kTail_IterStart); } 120dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 1214c2443e36fdc6c095b17e90baa4a2f26a6f00b08bsalomon@google.com T* head() { return Iter(*this, Iter::kHead_IterStart).get(); } 1224c2443e36fdc6c095b17e90baa4a2f26a6f00b08bsalomon@google.com T* tail() { return Iter(*this, Iter::kTail_IterStart).get(); } 1234c2443e36fdc6c095b17e90baa4a2f26a6f00b08bsalomon@google.com const T* head() const { return Iter(*this, Iter::kHead_IterStart).get(); } 1244c2443e36fdc6c095b17e90baa4a2f26a6f00b08bsalomon@google.com const T* tail() const { return Iter(*this, Iter::kTail_IterStart).get(); } 1254c2443e36fdc6c095b17e90baa4a2f26a6f00b08bsalomon@google.com 126bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com void popHead() { 127bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->validate(); 128bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Node* node = fList.head(); 12949f085dddff10473b6ebf832a974288300224e60bsalomon if (node) { 130bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->removeNode(node); 131bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 132bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->validate(); 133bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 134bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 135bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com void popTail() { 136bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->validate(); 137bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Node* node = fList.head(); 13849f085dddff10473b6ebf832a974288300224e60bsalomon if (node) { 139bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->removeNode(node); 140bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 141bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->validate(); 142bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 143bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 144bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com void remove(T* t) { 145bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->validate(); 146bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Node* node = reinterpret_cast<Node*>(t); 147bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(reinterpret_cast<T*>(node->fObj) == t); 148bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->removeNode(node); 149bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->validate(); 150bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 151bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 152bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com void reset() { 153bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->validate(); 154bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Iter iter(*this, Iter::kHead_IterStart); 155bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com while (iter.get()) { 156bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Iter next = iter; 157bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com next.next(); 158bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->remove(iter.get()); 159bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com iter = next; 160bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 161bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(0 == fCount); 162bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->validate(); 163bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 164bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 165bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com int count() const { return fCount; } 166bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com bool isEmpty() const { this->validate(); return 0 == fCount; } 167bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 168bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com bool operator== (const SkTLList& list) const { 169bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com if (this == &list) { 170bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com return true; 171bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 172bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com if (fCount != list.fCount) { 173bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com return false; 174bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 175bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com for (Iter a(*this, Iter::kHead_IterStart), b(list, Iter::kHead_IterStart); 176bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com a.get(); 177bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com a.next(), b.next()) { 17849f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(b.get()); // already checked that counts match. 179bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com if (!(*a.get() == *b.get())) { 180bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com return false; 181bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 182bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 183bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com return true; 184bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 185bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com bool operator!= (const SkTLList& list) const { return !(*this == list); } 186bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 187bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com /** The iterator becomes invalid if the element it refers to is removed from the list. */ 188bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com class Iter : private NodeList::Iter { 189bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com private: 190bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com typedef typename NodeList::Iter INHERITED; 191bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 192bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com public: 193bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com typedef typename INHERITED::IterStart IterStart; 194bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com //!< Start the iterator at the head of the list. 195bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com static const IterStart kHead_IterStart = INHERITED::kHead_IterStart; 196bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com //!< Start the iterator at the tail of the list. 197bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com static const IterStart kTail_IterStart = INHERITED::kTail_IterStart; 198bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 199bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Iter() {} 200bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 2014ebe3821888d550d8a8b89341ec251ba942f0225bsalomon@google.com Iter(const SkTLList& list, IterStart start = kHead_IterStart) { 202bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com INHERITED::init(list.fList, start); 203bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 204bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 2054ebe3821888d550d8a8b89341ec251ba942f0225bsalomon@google.com T* init(const SkTLList& list, IterStart start = kHead_IterStart) { 206bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com return this->nodeToObj(INHERITED::init(list.fList, start)); 207bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 208bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 209bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com T* get() { return this->nodeToObj(INHERITED::get()); } 210bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 211bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com T* next() { return this->nodeToObj(INHERITED::next()); } 212bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 213bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com T* prev() { return this->nodeToObj(INHERITED::prev()); } 214bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 215bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Iter& operator= (const Iter& iter) { INHERITED::operator=(iter); return *this; } 216bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 217bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com private: 218dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com friend class SkTLList; 219dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com Node* getNode() { return INHERITED::get(); } 220dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 221bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com T* nodeToObj(Node* node) { 22249f085dddff10473b6ebf832a974288300224e60bsalomon if (node) { 223bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com return reinterpret_cast<T*>(node->fObj); 224bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } else { 225bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com return NULL; 226bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 227bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 228bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com }; 229bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 230dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com // For use with operator new 231dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com enum Placement { 232dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com kBefore_Placement, 233dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com kAfter_Placement, 234dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com }; 235dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 236bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.comprivate: 237bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com struct Block { 238bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com int fNodesInUse; 239bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Node fNodes[1]; 240bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com }; 241bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 242bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com size_t blockSize() const { return sizeof(Block) + sizeof(Node) * (fAllocCnt-1); } 243bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 244bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Node* createNode() { 245bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Node* node = fFreeList.head(); 24649f085dddff10473b6ebf832a974288300224e60bsalomon if (node) { 247bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com fFreeList.remove(node); 248bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ++node->fBlock->fNodesInUse; 249bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } else { 250bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Block* block = reinterpret_cast<Block*>(sk_malloc_flags(this->blockSize(), 0)); 251bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com node = &block->fNodes[0]; 252bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkNEW_PLACEMENT(node, Node); 253bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com node->fBlock = block; 254bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com block->fNodesInUse = 1; 255bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com for (int i = 1; i < fAllocCnt; ++i) { 256bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkNEW_PLACEMENT(block->fNodes + i, Node); 257bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com fFreeList.addToHead(block->fNodes + i); 258bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com block->fNodes[i].fBlock = block; 259bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 260bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 261bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ++fCount; 262bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com return node; 263bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 264bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 265bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com void removeNode(Node* node) { 26649f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(node); 267bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com fList.remove(node); 268dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com SkTCast<T*>(node->fObj)->~T(); 269bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com if (0 == --node->fBlock->fNodesInUse) { 270bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Block* block = node->fBlock; 271bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com for (int i = 0; i < fAllocCnt; ++i) { 272bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com if (block->fNodes + i != node) { 273bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com fFreeList.remove(block->fNodes + i); 274bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 275bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com block->fNodes[i].~Node(); 276bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 277bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com sk_free(block); 278bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } else { 279bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com fFreeList.addToHead(node); 280bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 281bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com --fCount; 282bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com this->validate(); 283bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 284bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 285bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com void validate() const { 286bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#ifdef SK_DEBUG 287bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT((0 == fCount) == fList.isEmpty()); 288bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT((0 != fCount) || fFreeList.isEmpty()); 289bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 290bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com fList.validate(); 291bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com fFreeList.validate(); 292bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com typename NodeList::Iter iter; 293bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Node* freeNode = iter.init(fFreeList, Iter::kHead_IterStart); 294bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com while (freeNode) { 295bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(fFreeList.isInList(freeNode)); 296bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Block* block = freeNode->fBlock; 297bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(block->fNodesInUse > 0 && block->fNodesInUse < fAllocCnt); 298bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 299bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com int activeCnt = 0; 300bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com int freeCnt = 0; 301bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com for (int i = 0; i < fAllocCnt; ++i) { 302bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com bool free = fFreeList.isInList(block->fNodes + i); 303bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com bool active = fList.isInList(block->fNodes + i); 304bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(free != active); 305bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com activeCnt += active; 306bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com freeCnt += free; 307bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 308bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(activeCnt == block->fNodesInUse); 309bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com freeNode = iter.next(); 310bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 311bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 312bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com int count = 0; 313bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Node* activeNode = iter.init(fList, Iter::kHead_IterStart); 314bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com while (activeNode) { 315bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com ++count; 316bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(fList.isInList(activeNode)); 317bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com Block* block = activeNode->fBlock; 318bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(block->fNodesInUse > 0 && block->fNodesInUse <= fAllocCnt); 319bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 320bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com int activeCnt = 0; 321bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com int freeCnt = 0; 322bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com for (int i = 0; i < fAllocCnt; ++i) { 323bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com bool free = fFreeList.isInList(block->fNodes + i); 324bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com bool active = fList.isInList(block->fNodes + i); 325bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(free != active); 326bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com activeCnt += active; 327bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com freeCnt += free; 328bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 329bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(activeCnt == block->fNodesInUse); 330bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com activeNode = iter.next(); 331bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 332bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com SkASSERT(count == fCount); 333bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com#endif 334bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com } 335bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com 336dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com // Support in-place initializing of objects inserted into the list via operator new. 337dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com friend void* operator new<T>(size_t, 338dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com SkTLList* list, 339dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com Placement placement, 340dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com const Iter& location); 341dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 342dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 343dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com // Helpers that insert the node and returns a pointer to where the new object should be init'ed. 344dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com void* internalAddBefore(Iter location) { 345dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com this->validate(); 346dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com Node* node = this->createNode(); 347dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com fList.addBefore(node, location.getNode()); 348dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com this->validate(); 349dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com return node->fObj; 350dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com } 351dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 352dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com void* internalAddAfter(Iter location) { 353dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com this->validate(); 354dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com Node* node = this->createNode(); 355dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com fList.addAfter(node, location.getNode()); 356dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com this->validate(); 357dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com return node->fObj; 358dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com } 359dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 360bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com NodeList fList; 361bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com NodeList fFreeList; 362bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com int fCount; 363bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com int fAllocCnt; 364dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 365bbe52908a23d5eada9a0e5c58e620b35a2770c10bsalomon@google.com}; 366dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 367dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com// Use the below macros rather than calling this directly 368dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.comtemplate <typename T> 369dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.comvoid *operator new(size_t, SkTLList<T>* list, 370dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com typename SkTLList<T>::Placement placement, 371dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com const typename SkTLList<T>::Iter& location) { 37249f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(list); 373dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com if (SkTLList<T>::kBefore_Placement == placement) { 374dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com return list->internalAddBefore(location); 375dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com } else { 376dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com return list->internalAddAfter(location); 377dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com } 378dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com} 379dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 3808958dc949ea9f716c46b3ca98d341f775835296dbsalomon@google.com// Skia doesn't use C++ exceptions but it may be compiled with them enabled. Having an op delete 3818958dc949ea9f716c46b3ca98d341f775835296dbsalomon@google.com// to match the op new silences warnings about missing op delete when a constructor throws an 3828958dc949ea9f716c46b3ca98d341f775835296dbsalomon@google.com// exception. 3838958dc949ea9f716c46b3ca98d341f775835296dbsalomon@google.comtemplate <typename T> 3848958dc949ea9f716c46b3ca98d341f775835296dbsalomon@google.comvoid operator delete(void*, 3858958dc949ea9f716c46b3ca98d341f775835296dbsalomon@google.com SkTLList<T>*, 3868958dc949ea9f716c46b3ca98d341f775835296dbsalomon@google.com typename SkTLList<T>::Placement, 3878958dc949ea9f716c46b3ca98d341f775835296dbsalomon@google.com const typename SkTLList<T>::Iter&) { 3888958dc949ea9f716c46b3ca98d341f775835296dbsalomon@google.com SK_CRASH(); 3898958dc949ea9f716c46b3ca98d341f775835296dbsalomon@google.com} 3908958dc949ea9f716c46b3ca98d341f775835296dbsalomon@google.com 391dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com#define SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args) \ 3928182fa0cac76e7e6d583aebba060229230516887bsalomon@google.com (new ((list), SkTLList< type_name >::kBefore_Placement, (location)) type_name args) 393dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com 394dd3f7a9efefc486833d564527367155eb93691d4bsalomon@google.com#define SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args) \ 3958182fa0cac76e7e6d583aebba060229230516887bsalomon@google.com (new ((list), SkTLList< type_name >::kAfter_Placement, (location)) type_name args) 3968182fa0cac76e7e6d583aebba060229230516887bsalomon@google.com 3978182fa0cac76e7e6d583aebba060229230516887bsalomon@google.com#define SkNEW_INSERT_AT_LLIST_HEAD(list, type_name, args) \ 3988182fa0cac76e7e6d583aebba060229230516887bsalomon@google.com SkNEW_INSERT_IN_LLIST_BEFORE((list), (list)->headIter(), type_name, args) 3998182fa0cac76e7e6d583aebba060229230516887bsalomon@google.com 4008182fa0cac76e7e6d583aebba060229230516887bsalomon@google.com#define SkNEW_INSERT_AT_LLIST_TAIL(list, type_name, args) \ 401ebce0301082cda9dc3e3298f6db91d46fe66298bbsalomon@google.com SkNEW_INSERT_IN_LLIST_AFTER((list), (list)->tailIter(), type_name, args) 402ebce0301082cda9dc3e3298f6db91d46fe66298bbsalomon@google.com 4034c2443e36fdc6c095b17e90baa4a2f26a6f00b08bsalomon@google.com#endif 404