1/*
2 * Copyright 2014 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 SkTInternalSList_DEFINED
9#define SkTInternalSList_DEFINED
10
11#include "SkTInternalLList.h" // for SkPtrWrapper
12
13/**
14 * This macro creates the methods required by the SkTInternalSList class.
15 * It should be instantiated in the private block of the class you want to put
16 * into an SkTInternalSList.
17 * For most use cases you should use SK_DECLARE_INTERNAL_SLIST_INTERFACE and not
18 * this macro. If you care about the field name, or want to re-use an existing
19 * field, then you can use this macro to declare the methods pointing to a
20 * specific field.
21 * Unlike SK_DECLARE_INTERNAL_SLIST_INTERFACE this does not declare the field
22 * itself.
23 * It also makes SkTInternalSList<ClassName> a friend to give it access to the
24 * methods.
25 */
26#define SK_DECLARE_INTERNAL_SLIST_ADAPTER(ClassName, field)     \
27    ClassName* getSListNext() {                                 \
28        return this->field;                                     \
29    }                                                           \
30    void setSListNext(ClassName* next) {                        \
31        this->field = next;                                     \
32    }                                                           \
33    friend class SkTInternalSList<ClassName>
34
35/**
36 * This macro declares an fSListNext that auto initializes to NULL and then
37 * uses SK_DECLARE_INTERNAL_SLIST_ADAPTER to add the methods needed by
38 * SkTInternalSList.
39 * It should be instantiated in the private block of the class you want to put
40 * into an SkTInternalSList.
41 */
42#define SK_DECLARE_INTERNAL_SLIST_INTERFACE(ClassName)          \
43    SK_DECLARE_INTERNAL_SLIST_ADAPTER(ClassName, fSListNext);   \
44    SkPtrWrapper<ClassName> fSListNext
45
46/**
47 * An implementation of an intrusive singly linked list.
48 * The type T must have a methods getSListNext and setSListNext that are visible
49 * to the list. The easiest way to do this is with
50 * SK_DECLARE_INTERNAL_SLIST_INTERFACE.
51 * The list does not maintain ownership of any of its elements, or ever delete
52 * them.
53 */
54template<typename T> class SkTInternalSList {
55public:
56    SkTInternalSList() : fHead(NULL), fCount(0) {}
57
58    /**
59     * Push an item onto the head of the list.
60     * This method is *not* thread safe.
61     */
62    void push(T* entry) {
63        SkASSERT(entry->getSListNext() == NULL);
64        entry->setSListNext(fHead);
65        fHead = entry;
66        ++fCount;
67    }
68
69    /**
70     * Takes all the items from another list and pushes them into this list.
71     * No ordering guarantees are made, the other list will be emptied.
72     * This method is *not* thread safe.
73     */
74    void pushAll(SkTInternalSList<T>* other) {
75        if (this->isEmpty()) {
76            this->swap(other);
77            return;
78        }
79        while (!other->isEmpty()) {
80            this->push(other->pop());
81        }
82    }
83
84    /**
85     * Pop an item from the head of the list.
86     * Returns NULL if the list is empty.
87     * This method is *not* thread safe.
88     */
89    T* pop() {
90        if (NULL == fHead) {
91            return NULL;
92        }
93        T* result = fHead;
94        fHead = result->getSListNext();
95        result->setSListNext(NULL);
96        --fCount;
97        return result;
98    }
99
100    T* head() const {
101        return fHead;
102    }
103
104    /**
105     * Returns true if the list has no elements.
106     */
107    bool isEmpty() const {
108        return NULL == fHead;
109    }
110
111    /**
112     * Swaps the contents of this list with another one.
113     * This method is *not* thread safe.
114     */
115    void swap(SkTInternalSList<T>* other) {
116        SkTSwap(fHead, other->fHead);
117        SkTSwap(fCount, other->fCount);
118    }
119
120    /**
121     * Returns the count of elements in the list.
122     */
123    int getCount() const {
124        return fCount;
125    }
126private:
127    T* fHead;
128    int fCount;
129};
130
131
132#endif
133