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