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