Home | History | Annotate | Download | only in rs 
      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:
     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 
     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         explicit 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 
    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