RNBO: common/RNBO_List.h Source File

 #ifndef _RNBO_LIST_H_
 #define _RNBO_LIST_H_
  
 #include "RNBO_Types.h"
 #include "RNBO_Platform.h"
  
 #ifdef RNBO_NOSTL
 #include "RNBO_UniquePtr.h"
 #else
 #include <memory>
 #endif // RNBO_NOSTL
  
 #ifndef RNBO_FIXEDLISTSIZE
 #define RNBO_FIXEDLISTSIZE 0
 #endif
  
 namespace RNBO {
  
     template<class T, size_t N> class array;
  
     static const size_t listChunkSize = 8;
  
     template<typename T, size_t FIXED = RNBO_FIXEDLISTSIZE> class listbase {
     public:
  
         listbase()
         : length(0, *this)
         , _values(nullptr)
         , _allocatedLength(FIXED)
         {
             allocate(length, false);
         }
  
         template<typename... Ts> listbase(Ts ... args)
         : length(sizeof...(args), *this)
         , _values(nullptr)
         , _allocatedLength(FIXED)
         {
             allocate(length, false);
             T listValues[sizeof...(args)] = {static_cast<T>(args)...};
             size_t i = 0;
             if (FIXED) {
                 for (; i < length && i < FIXED; i++) {
                     _stackValues[i] = listValues[i];
                 }
             }
             for (; i < length; i++) {
                 _values[i] = listValues[i];
             }
         }
  
         // declaration of array constructor, definition is in RNBO_Array.h
         template<typename TA, size_t NA>
         listbase(const array<TA, NA>& arr);
         
         template<typename T1, size_t N1> listbase(const listbase<T1, N1>& l)
         : length(l.length, *this)
         , _values(nullptr)
         , _allocatedLength(FIXED)
         {
             allocate(length, false);
             size_t i = 0;
             if (FIXED) {
                 for (; i < length; i++) {
                     _stackValues[i] = l[i];
                 }
             }
             for (; i < length; i++) {
                 _values[i] = l[i];
             }
         }
  
         listbase(const listbase &l)
         : length(l.length, *this)
         , _values(nullptr)
         , _allocatedLength(FIXED)
         {
             allocate(length, false);
             size_t i = 0;
             if (FIXED) {
                 for (; i < length; i++) {
                     _stackValues[i] = l[i];
                 }
             }
             for (; i < length; i++) {
                 _values[i] = l[i];
             }
         }
  
         listbase(listbase&& l)
         : length(l.length, *this)
         , _values(l._values)
         , _allocatedLength(l._allocatedLength)
         {
             l._allocatedLength = 0;
             l._values = nullptr;
         }
  
  
         ~listbase()
         {
             if (_values) {
                 Platform::free(_values);
                 _values = nullptr;
             }
         }
  
         T& operator[](size_t i) {
             if (i >= length) {
                 Platform::errorOrDefault(RuntimeError::OutOfRange, "list index out of range", false /*unused*/);
                 _dummy = static_cast<T>(0);
                 return _dummy;
             }
             if (FIXED) {
                 if (i < FIXED) return _stackValues[i];
                 else return _values[i - FIXED];
             }
             else
                 return _values[i];
         }
  
         T operator[](size_t i) const {
             if (i >= length) {
                 return Platform::errorOrDefault(RuntimeError::OutOfRange, "list index out of range", (T)0);
             }
             if (FIXED) {
                 if (i < FIXED) return _stackValues[i];
                 else return _values[i - FIXED];
             }
             else
                 return _values[i];
         }
  
         listbase* operator->() {
             return this;
         }
  
         const listbase* operator->() const {
             return this;
         }
  
         listbase& operator=(const listbase& l)
         {
             if (&l != this) {
                 length = l.length;
                 allocate(length, false);
                 size_t i = 0;
                 if (FIXED) {
                     for (; i < length; i++) {
                         _stackValues[i] = l[i];
                     }
                 }
                 for (; i < length; i++) {
                     _values[i] = l[i];
                 }
             }
             return *this;
         }
  
         template<size_t N1> listbase<T>& operator=(const listbase<T, N1>& l)
         {
             length = l.length;
             allocate(length, false);
             size_t i = 0;
             if (FIXED) {
                 for (; i < length; i++) {
                     _stackValues[i] = l[i];
                 }
             }
             for (; i < length; i++) {
                 _values[i] = l[i];
             }
             
             return *this;
         }
  
         void push(T item) {
             allocate(length + 1, true);
             if (FIXED && length < FIXED) _stackValues[length] = item;
             else _values[length - FIXED] = item;
             length++;
         }
  
         T pop() {
             T tmp = 0;
             if (length > 0) {
                 size_t lastIndex = length - 1;
                 if (FIXED && lastIndex < FIXED) tmp = _stackValues[lastIndex];
                 else tmp = _values[lastIndex - FIXED];
                 length--;
             }
             return tmp;
         }
  
         T shift() {
             if (length == 0) {
                 return Platform::errorOrDefault(RuntimeError::OutOfRange, "cannot shift out of empty list", 0);
             }
             T tmp;
             if (FIXED) {
                 tmp = _stackValues[0];
                 Platform::memmove(_stackValues, _stackValues + 1, (FIXED - 1) * sizeof(T));
                 if (length > FIXED && _values) {
                     _stackValues[FIXED - 1] = _values[0];
                     Platform::memmove(_values, _values + 1, (length - FIXED - 1) * sizeof(T));
                 }
             }
             else {
                 tmp = _values[0];
                 Platform::memmove(_values, _values + 1, (length - 1) * sizeof(T));
             }
             length--;
             return tmp;
         }
  
         listbase concat(T item) const {
             listbase tmp(*this);
             tmp.push(item);
             return tmp;
         }
  
         listbase concat(const listbase& item) const {
             listbase tmp(*this);
             tmp.allocate(tmp.length + item.length, true);
             for (size_t i = 0; i < item.length; i++) {
                 if (FIXED) {
                     tmp.length++;
                     tmp[tmp.length - 1] = item[i];
                 }
                 else {
                     tmp._values[tmp.length] = item[i];
                     tmp.length++;
                 }
             }
  
             return tmp;
         }
  
         listbase& fill(T value, size_t start = 0, size_t end = 0)
         {
             if (end == 0) end = length;
             allocate(end, true);
             if (end > length) length = end;
             for (size_t i = start; i < end; i++) {
                 if (FIXED) {
                     (*this)[i] = value;
                 }
                 else {
                     _values[i] = value;
                 }
             }
  
             return *this;
         }
  
         template<typename... Ts> void unshift(Ts ... args) {
             splice(0, 0, args...);
         }
  
         template<typename... Ts> listbase<T> splice(Int start, size_t deleteCount, Ts ... args)
         {
             if (start < 0) start += length;
             if (start < 0) start = 0;
             size_t iStart = (size_t)start;
             if (iStart >= length) {
                 deleteCount = 0;
                 iStart = length;
             }
  
             if (iStart + deleteCount > length) deleteCount = length - iStart;
  
             const size_t addLength = sizeof...(args);
             const long diff = (long)(addLength - deleteCount);
  
             listbase<T> deletedItems;
             deletedItems.allocate(deleteCount, false);
             for (size_t i = 0; i < deleteCount; i++) {
                 if (FIXED) {
                     T val = (*this)[iStart + i];
                     deletedItems.push(val);
                 }
                 else {
                     deletedItems.push(_values[iStart + i]);
                 }
             }
  
             long newLength = (long)(length) + diff;
             if (newLength <= 0) {
                 length = 0;
                 return deletedItems;
             }
  
             allocate(static_cast<size_t>(newLength), true);
  
             if (diff < 0) {
                 RNBO_ASSERT(start - diff >= 0)
                 for (long i = (long)start - diff; i < (long)length; i++) {
                     RNBO_ASSERT(i + diff >= 0)
                     if (FIXED) {
                         (*this)[(size_t)(i + diff)] = (*this)[(size_t)i];
                     }
                     else {
                         _values[i + diff] = _values[i];
                     }
                 }
             } else if (diff > 0) {
                 for (long i = (long)(length - 1); i >= (long)start; i--) {
                     RNBO_ASSERT(i + diff >= 0)
                     if (FIXED) {
                         (*this)[(size_t)(i + diff)] = (*this)[(size_t)i];
                     }
                     else {
                         _values[i + diff] = _values[i];
                     }
                 }
             }
  
             // since allocating an array of 0 length is invalid, we always allocate at least length 1
             T addValues[(sizeof...(args)) + 1] = {static_cast<T>(args)...};
             RNBO_ASSERT(start >= 0)
             for (size_t i = 0; i < addLength; i++) {
                 if (FIXED) {
                     (*this)[i + (size_t)start] = addValues[i];
                 }
                 else {
                     _values[i + (size_t)start] = addValues[i];
                 }
             }
  
             length = static_cast<size_t>(newLength);
  
             return deletedItems;
         }
  
         listbase slice(int start = 0, int end = 0) const {
             listbase tmp;
             int ilen = static_cast<int>(this->length);
  
             //negative is offset from end
             if (start < 0) {
                 start = ilen + start;
                 if (start < 0) {
                     start = 0;
                 }
             }
  
             //offset from end
             if (end <= 0) {
                 end = ilen + end;
             }
  
             //bounds check
             if (start >= ilen || ilen == 0) {
                 return tmp;
             }
             if (end > ilen) {
                 end = ilen;
             }
  
             //allocate and copy
             tmp.allocate(static_cast<size_t>(end - start), false);
             for (int i = start; i < end; i++) {
                 if (FIXED) {
                     tmp.length++;
                     tmp[tmp.length - 1] = (*this)[i];
                 }
                 else {
                     tmp._values[tmp.length] = _values[i];
                     tmp.length++;
                 }
             }
  
             return tmp;
         }
  
         bool includes(T value, int fromIndex = 0) const {
             if (fromIndex < 0) {
                 fromIndex = int(length) + fromIndex;
                 if (fromIndex < 0) fromIndex = 0;
             }
  
             for (size_t i = size_t(fromIndex); i < length; i++) {
                 if (FIXED) {
                     if ((*this)[i] == value) return true;
                 }
                 else {
                     if (_values[i] == value) return true;
                 }
             }
  
             return false;
         }
  
         int indexOf(T value, int fromIndex = 0) const {
             if (fromIndex < 0) {
                 fromIndex = int(length) + fromIndex;
                 if (fromIndex < 0) fromIndex = 0;
             }
  
             for (size_t i = size_t(fromIndex); i < length; i++) {
                 if (FIXED) {
                     if ((*this)[i] == value) return (int)i;
                 }
                 else {
                     if (_values[i] == value) return (int)i;
                 }
             }
  
             return -1;
         }
  
         listbase& reverse() {
             size_t len2 = length >> 1;
  
             for (size_t i = 0; i < len2; ++i) {
                 if (FIXED) {
                     T tmp = (*this)[i];
                     size_t target = length - i - 1;
                     (*this)[i] = (*this)[target];
                     (*this)[target] = tmp;
  
                 }
                 else {
                     T tmp = _values[i];
                     size_t target = length - i - 1;
                     _values[i] = _values[target];
                     _values[target] = tmp;
                 }
             }
  
             return *this;
         }
  
         void reserve(size_t size) {
             allocate(size, true);
         }
  
     protected:
  
         class ListLengthWrapper {
         public:
             ListLengthWrapper(size_t l, listbase& owner)
             : _length(l)
             , _owner(owner)
             {}
  
             ListLengthWrapper(const ListLengthWrapper& l) = delete;
             ListLengthWrapper(ListLengthWrapper& l) = delete;
  
             operator size_t() const {
                 return _length;
             }
  
             ListLengthWrapper& operator=(size_t l) {
                 _length = l;
                 if (_length < 0) _length = 0;
                 _owner->checkLength();
                 return *this;
             }
  
             ListLengthWrapper& operator=(const ListLengthWrapper& l) {
                 _length = l._length;
                 _owner->checkLength();
                 return *this;
             }
  
             void operator++() {
                 _length = _length + 1;
                 _owner->checkLength();
             }
  
             void operator--() {
                 _length = _length - 1;
                 if (_length < 0) _length = 0;
                 _owner->checkLength();
             }
  
             void operator++(int) {
                 _length = _length + 1;
                 _owner->checkLength();
             }
  
             void operator--(int) {
                 _length = _length - 1;
                 if (_length < 0) _length = 0;
                 _owner->checkLength();
             }
  
         private:
             size_t _length = 0;
             listbase& _owner;
         };
  
     public:
         ListLengthWrapper   length = 0;
  
         T* inner() const { return _values; }
  
     protected:
  
         void checkLength() {
             allocate(length, true);
         }
  
         void allocate(size_t size, bool keepValues)
         {
             if (size > _allocatedLength) {
                 T *old_values = _values;
  
                 auto sizeToAllocate = size - FIXED;
                 auto lengthToAllocate = listChunkSize + (size_t(sizeToAllocate/listChunkSize)) * listChunkSize;
                 _values = (T*) Platform::calloc(lengthToAllocate, sizeof(T));
                 _allocatedLength = FIXED + lengthToAllocate;
  
                 if (keepValues && old_values) {
                     Platform::memcpy(_values, old_values, (length - FIXED) * sizeof(T));
                 }
  
                 if (old_values) {
                     Platform::free(old_values);
                 }
             }
         }
  
         T*  _values;
         T   _stackValues[FIXED + 1];
  
         size_t  _allocatedLength;
  
         T _dummy = {};
     };
  
     using list = listbase<number>;
     using indexlist = listbase<Index>;
     using intlist = listbase<int>;
  
     ATTRIBUTE_UNUSED 
     static list listWithSize(size_t n) { list l; l.length = n; return l; }
     ATTRIBUTE_UNUSED 
     static list intlistWithSize(size_t n) { intlist l; l.length = n; return l; }
     ATTRIBUTE_UNUSED 
     static list indexlistWithSize(size_t n) { indexlist l; l.length = n; return l; }
  
     class ListNum {
     public:
         ListNum()
         : _val()
         {}
  
         ListNum(number val)
         : _val(val)
         {}
  
         ListNum(list val)
         : _val(val)
         {}
  
         operator number() const { return _val.length > 0 ? _val[0] : 0; }
         operator list() const { return _val; }
  
         number operator[](size_t i) const {
             return _val[i];
         }
  
         list& operator->() {
             return _val;
         }
  
         const list& operator->() const {
             return _val;
         }
  
     private:
         list _val;
     };
  
 #ifdef RNBO_NOSTL
     using UniqueListPtr = UniquePtr<list>;
 #else
     using UniqueListPtr = std::unique_ptr<listbase<number>>;
 #endif // RNBO_NOSTL
  
 } // namespace RNBO
  
 #endif // #ifndef _RNBO_LIST_H_
C++ Guides

RNBO: common/RNBO_List.h Source File
