SkTInternalLList.h 7.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302
  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 SkTInternalLList_DEFINED
  8. #define SkTInternalLList_DEFINED
  9. #include "include/core/SkTypes.h"
  10. /**
  11. * This macro creates the member variables required by the SkTInternalLList class. It should be
  12. * placed in the private section of any class that will be stored in a double linked list.
  13. */
  14. #define SK_DECLARE_INTERNAL_LLIST_INTERFACE(ClassName) \
  15. friend class SkTInternalLList<ClassName>; \
  16. /* back pointer to the owning list - for debugging */ \
  17. SkDEBUGCODE(SkTInternalLList<ClassName>* fList = nullptr;) \
  18. ClassName* fPrev = nullptr; \
  19. ClassName* fNext = nullptr
  20. /**
  21. * This class implements a templated internal doubly linked list data structure.
  22. */
  23. template <class T> class SkTInternalLList {
  24. public:
  25. SkTInternalLList() {}
  26. void reset() {
  27. fHead = nullptr;
  28. fTail = nullptr;
  29. }
  30. void remove(T* entry) {
  31. SkASSERT(fHead && fTail);
  32. SkASSERT(this->isInList(entry));
  33. T* prev = entry->fPrev;
  34. T* next = entry->fNext;
  35. if (prev) {
  36. prev->fNext = next;
  37. } else {
  38. fHead = next;
  39. }
  40. if (next) {
  41. next->fPrev = prev;
  42. } else {
  43. fTail = prev;
  44. }
  45. entry->fPrev = nullptr;
  46. entry->fNext = nullptr;
  47. #ifdef SK_DEBUG
  48. entry->fList = nullptr;
  49. #endif
  50. }
  51. void addToHead(T* entry) {
  52. SkASSERT(nullptr == entry->fPrev && nullptr == entry->fNext);
  53. SkASSERT(nullptr == entry->fList);
  54. entry->fPrev = nullptr;
  55. entry->fNext = fHead;
  56. if (fHead) {
  57. fHead->fPrev = entry;
  58. }
  59. fHead = entry;
  60. if (nullptr == fTail) {
  61. fTail = entry;
  62. }
  63. #ifdef SK_DEBUG
  64. entry->fList = this;
  65. #endif
  66. }
  67. void addToTail(T* entry) {
  68. SkASSERT(nullptr == entry->fPrev && nullptr == entry->fNext);
  69. SkASSERT(nullptr == entry->fList);
  70. entry->fPrev = fTail;
  71. entry->fNext = nullptr;
  72. if (fTail) {
  73. fTail->fNext = entry;
  74. }
  75. fTail = entry;
  76. if (nullptr == fHead) {
  77. fHead = entry;
  78. }
  79. #ifdef SK_DEBUG
  80. entry->fList = this;
  81. #endif
  82. }
  83. /**
  84. * Inserts a new list entry before an existing list entry. The new entry must not already be
  85. * a member of this or any other list. If existingEntry is NULL then the new entry is added
  86. * at the tail.
  87. */
  88. void addBefore(T* newEntry, T* existingEntry) {
  89. SkASSERT(newEntry);
  90. if (nullptr == existingEntry) {
  91. this->addToTail(newEntry);
  92. return;
  93. }
  94. SkASSERT(this->isInList(existingEntry));
  95. newEntry->fNext = existingEntry;
  96. T* prev = existingEntry->fPrev;
  97. existingEntry->fPrev = newEntry;
  98. newEntry->fPrev = prev;
  99. if (nullptr == prev) {
  100. SkASSERT(fHead == existingEntry);
  101. fHead = newEntry;
  102. } else {
  103. prev->fNext = newEntry;
  104. }
  105. #ifdef SK_DEBUG
  106. newEntry->fList = this;
  107. #endif
  108. }
  109. /**
  110. * Inserts a new list entry after an existing list entry. The new entry must not already be
  111. * a member of this or any other list. If existingEntry is NULL then the new entry is added
  112. * at the head.
  113. */
  114. void addAfter(T* newEntry, T* existingEntry) {
  115. SkASSERT(newEntry);
  116. if (nullptr == existingEntry) {
  117. this->addToHead(newEntry);
  118. return;
  119. }
  120. SkASSERT(this->isInList(existingEntry));
  121. newEntry->fPrev = existingEntry;
  122. T* next = existingEntry->fNext;
  123. existingEntry->fNext = newEntry;
  124. newEntry->fNext = next;
  125. if (nullptr == next) {
  126. SkASSERT(fTail == existingEntry);
  127. fTail = newEntry;
  128. } else {
  129. next->fPrev = newEntry;
  130. }
  131. #ifdef SK_DEBUG
  132. newEntry->fList = this;
  133. #endif
  134. }
  135. void concat(SkTInternalLList&& list) {
  136. if (list.isEmpty()) {
  137. return;
  138. }
  139. list.fHead->fPrev = fTail;
  140. if (!fHead) {
  141. SkASSERT(!list.fHead->fPrev);
  142. fHead = list.fHead;
  143. } else {
  144. SkASSERT(fTail);
  145. fTail->fNext = list.fHead;
  146. }
  147. fTail = list.fTail;
  148. #ifdef SK_DEBUG
  149. for (T* node = list.fHead; node; node = node->fNext) {
  150. SkASSERT(node->fList == &list);
  151. node->fList = this;
  152. }
  153. #endif
  154. list.fHead = list.fTail = nullptr;
  155. }
  156. bool isEmpty() const {
  157. SkASSERT(SkToBool(fHead) == SkToBool(fTail));
  158. return !fHead;
  159. }
  160. T* head() { return fHead; }
  161. T* tail() { return fTail; }
  162. class Iter {
  163. public:
  164. enum IterStart {
  165. kHead_IterStart,
  166. kTail_IterStart
  167. };
  168. Iter() : fCurr(nullptr) {}
  169. Iter(const Iter& iter) : fCurr(iter.fCurr) {}
  170. Iter& operator= (const Iter& iter) { fCurr = iter.fCurr; return *this; }
  171. T* init(const SkTInternalLList& list, IterStart startLoc) {
  172. if (kHead_IterStart == startLoc) {
  173. fCurr = list.fHead;
  174. } else {
  175. SkASSERT(kTail_IterStart == startLoc);
  176. fCurr = list.fTail;
  177. }
  178. return fCurr;
  179. }
  180. T* get() { return fCurr; }
  181. /**
  182. * Return the next/previous element in the list or NULL if at the end.
  183. */
  184. T* next() {
  185. if (nullptr == fCurr) {
  186. return nullptr;
  187. }
  188. fCurr = fCurr->fNext;
  189. return fCurr;
  190. }
  191. T* prev() {
  192. if (nullptr == fCurr) {
  193. return nullptr;
  194. }
  195. fCurr = fCurr->fPrev;
  196. return fCurr;
  197. }
  198. /**
  199. * C++11 range-for interface.
  200. */
  201. bool operator!=(const Iter& that) { return fCurr != that.fCurr; }
  202. T* operator*() { return this->get(); }
  203. void operator++() { this->next(); }
  204. private:
  205. T* fCurr;
  206. };
  207. Iter begin() const {
  208. Iter iter;
  209. iter.init(*this, Iter::kHead_IterStart);
  210. return iter;
  211. }
  212. Iter end() const { return Iter(); }
  213. #ifdef SK_DEBUG
  214. void validate() const {
  215. SkASSERT(!fHead == !fTail);
  216. Iter iter;
  217. for (T* item = iter.init(*this, Iter::kHead_IterStart); item; item = iter.next()) {
  218. SkASSERT(this->isInList(item));
  219. if (nullptr == item->fPrev) {
  220. SkASSERT(fHead == item);
  221. } else {
  222. SkASSERT(item->fPrev->fNext == item);
  223. }
  224. if (nullptr == item->fNext) {
  225. SkASSERT(fTail == item);
  226. } else {
  227. SkASSERT(item->fNext->fPrev == item);
  228. }
  229. }
  230. }
  231. /**
  232. * Debugging-only method that uses the list back pointer to check if 'entry' is indeed in 'this'
  233. * list.
  234. */
  235. bool isInList(const T* entry) const {
  236. return entry->fList == this;
  237. }
  238. /**
  239. * Debugging-only method that laboriously counts the list entries.
  240. */
  241. int countEntries() const {
  242. int count = 0;
  243. for (T* entry = fHead; entry; entry = entry->fNext) {
  244. ++count;
  245. }
  246. return count;
  247. }
  248. #endif // SK_DEBUG
  249. private:
  250. T* fHead = nullptr;
  251. T* fTail = nullptr;
  252. SkTInternalLList(const SkTInternalLList&) = delete;
  253. SkTInternalLList& operator=(const SkTInternalLList&) = delete;
  254. };
  255. #endif