1#ifndef ANDROID_RENDERSCRIPT_LIST_H
2#define ANDROID_RENDERSCRIPT_LIST_H
3
4namespace android {
5namespace renderscript {
6
7namespace {
8
9constexpr size_t BUFFER_SIZE = 64;
10
11}  // anonymous namespace
12
13template <class T>
14class List {
15private:
16    class LinkedBuffer {
17    public:
18        LinkedBuffer() : next(nullptr) {}
19
20        union {
21            char raw[BUFFER_SIZE - sizeof(LinkedBuffer*)];
22            T typed;
23        } data;
24        LinkedBuffer* next;
25    };
26
27public:
28    class iterator;
29
30    List() : last(nullptr), first(&firstBuffer.data.typed),
31             beginIterator(this, &firstBuffer, const_cast<T*>(first)),
32             _size(0) {
33        current = const_cast<T*>(first);
34        currentBuffer = &firstBuffer;
35    }
36
37    template <class InputIterator>
38    List(InputIterator first, InputIterator last) : List() {
39        for (InputIterator it = first; it != last; ++it) {
40            push_back(*it);
41        }
42    }
43
44    ~List() {
45        LinkedBuffer* p = firstBuffer.next;
46        LinkedBuffer* next;
47        while (p != nullptr) {
48            next = p->next;
49            delete p;
50            p = next;
51        }
52    }
53
54    void push_back(const T& value) {
55        last = current;
56        *current++ = value;
57        _size++;
58        if ((void*)current >= (void*)&currentBuffer->next) {
59            LinkedBuffer* newBuffer = new LinkedBuffer();
60            currentBuffer->next = newBuffer;
61            currentBuffer = newBuffer;
62            current = &currentBuffer->data.typed;
63        }
64    }
65
66    class iterator {
67        friend class List;
68    public:
69        iterator& operator++() {
70            p++;
71            if ((void*)p >= (void*)&buffer->next) {
72                buffer = buffer->next;
73                if (buffer != nullptr) {
74                    p = &buffer->data.typed;
75                } else {
76                    p = nullptr;
77                }
78            }
79            return *this;
80        }
81
82        bool operator==(const iterator& other) const {
83            return p == other.p && buffer == other.buffer && list == other.list;
84        }
85
86        bool operator!=(const iterator& other) const {
87            return p != other.p || buffer != other.buffer || list != other.list;
88        }
89
90        const T& operator*() const { return *p; }
91
92        T* operator->() { return p; }
93
94    protected:
95        iterator(const List* list_) : list(list_) {}
96        iterator(const List* list_, LinkedBuffer* buffer_, T* p_) :
97            p(p_), buffer(buffer_), list(list_) {}
98
99    private:
100        T* p;
101        LinkedBuffer* buffer;
102        const List* list;
103    };
104
105    const iterator& begin() const { return beginIterator; }
106
107    iterator end() const { return iterator(this, currentBuffer, current); }
108
109    bool empty() const { return current == first; }
110
111    T& front() const { return *const_cast<T*>(first); }
112
113    T& back() const { return *last; }
114
115    size_t size() const { return _size; }
116
117private:
118    T* current;
119    T* last;
120    LinkedBuffer* currentBuffer;
121    LinkedBuffer firstBuffer;
122    const T* first;
123    const iterator beginIterator;
124    size_t _size;
125};
126
127}  // namespace renderscript
128}  // namespace android
129
130#endif  //  ANDROID_RENDERSCRIPT_LIST_H
131