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*)¤tBuffer->next) { 59 LinkedBuffer* newBuffer = new LinkedBuffer(); 60 currentBuffer->next = newBuffer; 61 currentBuffer = newBuffer; 62 current = ¤tBuffer->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