1 #ifndef ANDROID_RENDERSCRIPT_LIST_H
2 #define ANDROID_RENDERSCRIPT_LIST_H
3 
4 namespace android {
5 namespace renderscript {
6 
7 namespace {
8 
9 constexpr size_t BUFFER_SIZE = 64;
10 
11 }  // anonymous namespace
12 
13 template <class T>
14 class List {
15 private:
16     class LinkedBuffer {
17     public:
LinkedBuffer()18         LinkedBuffer() : next(nullptr) {}
19 
20         union {
21             char raw[BUFFER_SIZE - sizeof(LinkedBuffer*)];
22             T typed;
23         } data;
24         LinkedBuffer* next;
25     };
26 
27 public:
28     class iterator;
29 
List()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>
List(InputIterator first,InputIterator last)38     List(InputIterator first, InputIterator last) : List() {
39         for (InputIterator it = first; it != last; ++it) {
40             push_back(*it);
41         }
42     }
43 
~List()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 
push_back(const T & value)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:
iterator(const List * list_)95         explicit iterator(const List* list_) : list(list_) {}
iterator(const List * list_,LinkedBuffer * buffer_,T * p_)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 
begin()105     const iterator& begin() const { return beginIterator; }
106 
end()107     iterator end() const { return iterator(this, currentBuffer, current); }
108 
empty()109     bool empty() const { return current == first; }
110 
front()111     T& front() const { return *const_cast<T*>(first); }
112 
back()113     T& back() const { return *last; }
114 
size()115     size_t size() const { return _size; }
116 
117 private:
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