SkTLList.h 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354
  1. /*
  2. * Copyright 2012 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #ifndef SkTLList_DEFINED
  8. #define SkTLList_DEFINED
  9. #include "include/core/SkTypes.h"
  10. #include "include/private/SkMalloc.h"
  11. #include "include/private/SkTemplates.h"
  12. #include "src/core/SkTInternalLList.h"
  13. #include <new>
  14. #include <utility>
  15. /** Doubly-linked list of objects. The objects' lifetimes are controlled by the list. I.e. the
  16. the list creates the objects and they are deleted upon removal. This class block-allocates
  17. space for entries based on a param passed to the constructor.
  18. Elements of the list can be constructed in place using the following macros:
  19. SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args)
  20. SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args)
  21. where list is a SkTLList<type_name>*, location is an iterator, and args is the paren-surrounded
  22. constructor arguments for type_name. These macros behave like addBefore() and addAfter().
  23. allocCnt is the number of objects to allocate as a group. In the worst case fragmentation
  24. each object is using the space required for allocCnt unfragmented objects.
  25. */
  26. template <typename T, unsigned int N> class SkTLList {
  27. private:
  28. struct Block;
  29. struct Node {
  30. SkAlignedSTStorage<1, T> fObj;
  31. SK_DECLARE_INTERNAL_LLIST_INTERFACE(Node);
  32. Block* fBlock; // owning block.
  33. };
  34. typedef SkTInternalLList<Node> NodeList;
  35. public:
  36. class Iter;
  37. // Having fCount initialized to -1 indicates that the first time we attempt to grab a free node
  38. // all the nodes in the pre-allocated first block need to be inserted into the free list. This
  39. // allows us to skip that loop in instances when the list is never populated.
  40. SkTLList() : fCount(-1) {}
  41. ~SkTLList() {
  42. this->validate();
  43. typename NodeList::Iter iter;
  44. Node* node = iter.init(fList, Iter::kHead_IterStart);
  45. while (node) {
  46. reinterpret_cast<T*>(node->fObj.get())->~T();
  47. Block* block = node->fBlock;
  48. node = iter.next();
  49. if (0 == --block->fNodesInUse) {
  50. for (unsigned int i = 0; i < N; ++i) {
  51. block->fNodes[i].~Node();
  52. }
  53. if (block != &fFirstBlock) {
  54. sk_free(block);
  55. }
  56. }
  57. }
  58. }
  59. /** Adds a new element to the list at the head. */
  60. template <typename... Args> T* addToHead(Args&&... args) {
  61. this->validate();
  62. Node* node = this->createNode();
  63. fList.addToHead(node);
  64. this->validate();
  65. return new (node->fObj.get()) T(std::forward<Args>(args)...);
  66. }
  67. /** Adds a new element to the list at the tail. */
  68. template <typename... Args> T* addToTail(Args&&... args) {
  69. this->validate();
  70. Node* node = this->createNode();
  71. fList.addToTail(node);
  72. this->validate();
  73. return new (node->fObj.get()) T(std::forward<Args>(args)...);
  74. }
  75. /** Adds a new element to the list before the location indicated by the iterator. If the
  76. iterator refers to a nullptr location then the new element is added at the tail */
  77. template <typename... Args> T* addBefore(Iter location, Args&&... args) {
  78. this->validate();
  79. Node* node = this->createNode();
  80. fList.addBefore(node, location.getNode());
  81. this->validate();
  82. return new (node->fObj.get()) T(std::forward<Args>(args)...);
  83. }
  84. /** Adds a new element to the list after the location indicated by the iterator. If the
  85. iterator refers to a nullptr location then the new element is added at the head */
  86. template <typename... Args> T* addAfter(Iter location, Args&&... args) {
  87. this->validate();
  88. Node* node = this->createNode();
  89. fList.addAfter(node, location.getNode());
  90. this->validate();
  91. return new (node->fObj.get()) T(std::forward<Args>(args)...);
  92. }
  93. /** Convenience methods for getting an iterator initialized to the head/tail of the list. */
  94. Iter headIter() const { return Iter(*this, Iter::kHead_IterStart); }
  95. Iter tailIter() const { return Iter(*this, Iter::kTail_IterStart); }
  96. T* head() { return Iter(*this, Iter::kHead_IterStart).get(); }
  97. T* tail() { return Iter(*this, Iter::kTail_IterStart).get(); }
  98. const T* head() const { return Iter(*this, Iter::kHead_IterStart).get(); }
  99. const T* tail() const { return Iter(*this, Iter::kTail_IterStart).get(); }
  100. void popHead() {
  101. this->validate();
  102. Node* node = fList.head();
  103. if (node) {
  104. this->removeNode(node);
  105. }
  106. this->validate();
  107. }
  108. void popTail() {
  109. this->validate();
  110. Node* node = fList.head();
  111. if (node) {
  112. this->removeNode(node);
  113. }
  114. this->validate();
  115. }
  116. void remove(T* t) {
  117. this->validate();
  118. Node* node = reinterpret_cast<Node*>(t);
  119. SkASSERT(reinterpret_cast<T*>(node->fObj.get()) == t);
  120. this->removeNode(node);
  121. this->validate();
  122. }
  123. void reset() {
  124. this->validate();
  125. Iter iter(*this, Iter::kHead_IterStart);
  126. while (iter.get()) {
  127. Iter next = iter;
  128. next.next();
  129. this->remove(iter.get());
  130. iter = next;
  131. }
  132. SkASSERT(0 == fCount || -1 == fCount);
  133. this->validate();
  134. }
  135. int count() const { return SkTMax(fCount ,0); }
  136. bool isEmpty() const { this->validate(); return 0 == fCount || -1 == fCount; }
  137. bool operator== (const SkTLList& list) const {
  138. if (this == &list) {
  139. return true;
  140. }
  141. // Call count() rather than use fCount because an empty list may have fCount = 0 or -1.
  142. if (this->count() != list.count()) {
  143. return false;
  144. }
  145. for (Iter a(*this, Iter::kHead_IterStart), b(list, Iter::kHead_IterStart);
  146. a.get();
  147. a.next(), b.next()) {
  148. SkASSERT(b.get()); // already checked that counts match.
  149. if (!(*a.get() == *b.get())) {
  150. return false;
  151. }
  152. }
  153. return true;
  154. }
  155. bool operator!= (const SkTLList& list) const { return !(*this == list); }
  156. /** The iterator becomes invalid if the element it refers to is removed from the list. */
  157. class Iter : private NodeList::Iter {
  158. private:
  159. typedef typename NodeList::Iter INHERITED;
  160. public:
  161. typedef typename INHERITED::IterStart IterStart;
  162. //!< Start the iterator at the head of the list.
  163. static const IterStart kHead_IterStart = INHERITED::kHead_IterStart;
  164. //!< Start the iterator at the tail of the list.
  165. static const IterStart kTail_IterStart = INHERITED::kTail_IterStart;
  166. Iter() {}
  167. Iter(const SkTLList& list, IterStart start = kHead_IterStart) {
  168. INHERITED::init(list.fList, start);
  169. }
  170. T* init(const SkTLList& list, IterStart start = kHead_IterStart) {
  171. return this->nodeToObj(INHERITED::init(list.fList, start));
  172. }
  173. T* get() { return this->nodeToObj(INHERITED::get()); }
  174. T* next() { return this->nodeToObj(INHERITED::next()); }
  175. T* prev() { return this->nodeToObj(INHERITED::prev()); }
  176. Iter& operator= (const Iter& iter) { INHERITED::operator=(iter); return *this; }
  177. private:
  178. friend class SkTLList;
  179. Node* getNode() { return INHERITED::get(); }
  180. T* nodeToObj(Node* node) {
  181. if (node) {
  182. return reinterpret_cast<T*>(node->fObj.get());
  183. } else {
  184. return nullptr;
  185. }
  186. }
  187. };
  188. private:
  189. struct Block {
  190. int fNodesInUse;
  191. Node fNodes[N];
  192. };
  193. void delayedInit() {
  194. SkASSERT(-1 == fCount);
  195. fFirstBlock.fNodesInUse = 0;
  196. for (unsigned int i = 0; i < N; ++i) {
  197. fFreeList.addToHead(fFirstBlock.fNodes + i);
  198. fFirstBlock.fNodes[i].fBlock = &fFirstBlock;
  199. }
  200. fCount = 0;
  201. this->validate();
  202. }
  203. Node* createNode() {
  204. if (-1 == fCount) {
  205. this->delayedInit();
  206. }
  207. Node* node = fFreeList.head();
  208. if (node) {
  209. fFreeList.remove(node);
  210. ++node->fBlock->fNodesInUse;
  211. } else {
  212. // Should not get here when count == 0 because we always have the preallocated first
  213. // block.
  214. SkASSERT(fCount > 0);
  215. Block* block = reinterpret_cast<Block*>(sk_malloc_throw(sizeof(Block)));
  216. node = &block->fNodes[0];
  217. new (node) Node;
  218. node->fBlock = block;
  219. block->fNodesInUse = 1;
  220. for (unsigned int i = 1; i < N; ++i) {
  221. new (block->fNodes + i) Node;
  222. fFreeList.addToHead(block->fNodes + i);
  223. block->fNodes[i].fBlock = block;
  224. }
  225. }
  226. ++fCount;
  227. return node;
  228. }
  229. void removeNode(Node* node) {
  230. SkASSERT(node);
  231. fList.remove(node);
  232. reinterpret_cast<T*>(node->fObj.get())->~T();
  233. Block* block = node->fBlock;
  234. // Don't ever elease the first block, just add its nodes to the free list
  235. if (0 == --block->fNodesInUse && block != &fFirstBlock) {
  236. for (unsigned int i = 0; i < N; ++i) {
  237. if (block->fNodes + i != node) {
  238. fFreeList.remove(block->fNodes + i);
  239. }
  240. block->fNodes[i].~Node();
  241. }
  242. sk_free(block);
  243. } else {
  244. fFreeList.addToHead(node);
  245. }
  246. --fCount;
  247. this->validate();
  248. }
  249. void validate() const {
  250. #ifdef SK_DEBUG
  251. bool isEmpty = false;
  252. if (-1 == fCount) {
  253. // We should not yet have initialized the free list.
  254. SkASSERT(fFreeList.isEmpty());
  255. isEmpty = true;
  256. } else if (0 == fCount) {
  257. // Should only have the nodes from the first block in the free list.
  258. SkASSERT(fFreeList.countEntries() == N);
  259. isEmpty = true;
  260. }
  261. SkASSERT(isEmpty == fList.isEmpty());
  262. fList.validate();
  263. fFreeList.validate();
  264. typename NodeList::Iter iter;
  265. Node* freeNode = iter.init(fFreeList, Iter::kHead_IterStart);
  266. while (freeNode) {
  267. SkASSERT(fFreeList.isInList(freeNode));
  268. Block* block = freeNode->fBlock;
  269. // Only the first block is allowed to have all its nodes in the free list.
  270. SkASSERT(block->fNodesInUse > 0 || block == &fFirstBlock);
  271. SkASSERT((unsigned)block->fNodesInUse < N);
  272. int activeCnt = 0;
  273. int freeCnt = 0;
  274. for (unsigned int i = 0; i < N; ++i) {
  275. bool free = fFreeList.isInList(block->fNodes + i);
  276. bool active = fList.isInList(block->fNodes + i);
  277. SkASSERT(free != active);
  278. activeCnt += active;
  279. freeCnt += free;
  280. }
  281. SkASSERT(activeCnt == block->fNodesInUse);
  282. freeNode = iter.next();
  283. }
  284. int count = 0;
  285. Node* activeNode = iter.init(fList, Iter::kHead_IterStart);
  286. while (activeNode) {
  287. ++count;
  288. SkASSERT(fList.isInList(activeNode));
  289. Block* block = activeNode->fBlock;
  290. SkASSERT(block->fNodesInUse > 0 && (unsigned)block->fNodesInUse <= N);
  291. int activeCnt = 0;
  292. int freeCnt = 0;
  293. for (unsigned int i = 0; i < N; ++i) {
  294. bool free = fFreeList.isInList(block->fNodes + i);
  295. bool active = fList.isInList(block->fNodes + i);
  296. SkASSERT(free != active);
  297. activeCnt += active;
  298. freeCnt += free;
  299. }
  300. SkASSERT(activeCnt == block->fNodesInUse);
  301. activeNode = iter.next();
  302. }
  303. SkASSERT(count == fCount || (0 == count && -1 == fCount));
  304. #endif
  305. }
  306. NodeList fList;
  307. NodeList fFreeList;
  308. Block fFirstBlock;
  309. int fCount;
  310. SkTLList(const SkTLList&) = delete;
  311. SkTLList& operator=(const SkTLList&) = delete;
  312. };
  313. #endif