1 #ifndef NALL_VECTOR_HPP 2 #define NALL_VECTOR_HPP 3 4 #include <new> 5 #include <nall/algorithm.hpp> 6 #include <nall/bit.hpp> 7 #include <nall/utility.hpp> 8 9 namespace nall { 10 //linear_vector 11 //memory: O(capacity * 2) 12 // 13 //linear_vector uses placement new + manual destructor calls to create a 14 //contiguous block of memory for all objects. accessing individual elements 15 //is fast, though resizing the array incurs significant overhead. 16 //reserve() overhead is reduced from quadratic time to amortized constant time 17 //by resizing twice as much as requested. 18 // 19 //if objects hold memory address references to themselves (introspection), a 20 //valid copy constructor will be needed to keep pointers valid. 21 22 template<typename T> class linear_vector : noncopyable { 23 protected: 24 T *pool; 25 unsigned poolsize, objectsize; 26 27 public: size() const28 unsigned size() const { return objectsize; } capacity() const29 unsigned capacity() const { return poolsize; } 30 reset()31 void reset() { 32 if(pool) { 33 for(unsigned i = 0; i < objectsize; i++) pool[i].~T(); 34 free(pool); 35 } 36 pool = 0; 37 poolsize = 0; 38 objectsize = 0; 39 } 40 reserve(unsigned newsize)41 void reserve(unsigned newsize) { 42 newsize = bit::round(newsize); //round to nearest power of two (for amortized growth) 43 44 T *poolcopy = (T*)malloc(newsize * sizeof(T)); 45 for(unsigned i = 0; i < min(objectsize, newsize); i++) new(poolcopy + i) T(pool[i]); 46 for(unsigned i = 0; i < objectsize; i++) pool[i].~T(); 47 free(pool); 48 pool = poolcopy; 49 poolsize = newsize; 50 objectsize = min(objectsize, newsize); 51 } 52 resize(unsigned newsize)53 void resize(unsigned newsize) { 54 if(newsize > poolsize) reserve(newsize); 55 56 if(newsize < objectsize) { 57 //vector is shrinking; destroy excess objects 58 for(unsigned i = newsize; i < objectsize; i++) pool[i].~T(); 59 } else if(newsize > objectsize) { 60 //vector is expanding; allocate new objects 61 for(unsigned i = objectsize; i < newsize; i++) new(pool + i) T; 62 } 63 64 objectsize = newsize; 65 } 66 add(const T data)67 void add(const T data) { 68 if(objectsize + 1 > poolsize) reserve(objectsize + 1); 69 new(pool + objectsize++) T(data); 70 } 71 operator [](unsigned index)72 inline T& operator[](unsigned index) { 73 if(index >= objectsize) resize(index + 1); 74 return pool[index]; 75 } 76 operator [](unsigned index) const77 inline const T& operator[](unsigned index) const { 78 if(index >= objectsize) throw "vector[] out of bounds"; 79 return pool[index]; 80 } 81 linear_vector()82 linear_vector() : pool(0), poolsize(0), objectsize(0) {} ~linear_vector()83 ~linear_vector() { reset(); } 84 }; 85 86 //pointer_vector 87 //memory: O(1) 88 // 89 //pointer_vector keeps an array of pointers to each vector object. this adds 90 //significant overhead to individual accesses, but allows for optimal memory 91 //utilization. 92 // 93 //by guaranteeing that the base memory address of each objects never changes, 94 //this avoids the need for an object to have a valid copy constructor. 95 96 template<typename T> class pointer_vector : noncopyable { 97 protected: 98 T **pool; 99 unsigned poolsize, objectsize; 100 101 public: size() const102 unsigned size() const { return objectsize; } capacity() const103 unsigned capacity() const { return poolsize; } 104 reset()105 void reset() { 106 if(pool) { 107 for(unsigned i = 0; i < objectsize; i++) { if(pool[i]) delete pool[i]; } 108 free(pool); 109 } 110 pool = 0; 111 poolsize = 0; 112 objectsize = 0; 113 } 114 reserve(unsigned newsize)115 void reserve(unsigned newsize) { 116 newsize = bit::round(newsize); //round to nearest power of two (for amortized growth) 117 118 for(unsigned i = newsize; i < objectsize; i++) { 119 if(pool[i]) { delete pool[i]; pool[i] = 0; } 120 } 121 122 pool = (T**)realloc(pool, newsize * sizeof(T*)); 123 for(unsigned i = poolsize; i < newsize; i++) pool[i] = 0; 124 poolsize = newsize; 125 objectsize = min(objectsize, newsize); 126 } 127 resize(unsigned newsize)128 void resize(unsigned newsize) { 129 if(newsize > poolsize) reserve(newsize); 130 131 for(unsigned i = newsize; i < objectsize; i++) { 132 if(pool[i]) { delete pool[i]; pool[i] = 0; } 133 } 134 135 objectsize = newsize; 136 } 137 add(const T data)138 void add(const T data) { 139 if(objectsize + 1 > poolsize) reserve(objectsize + 1); 140 pool[objectsize++] = new T(data); 141 } 142 operator [](unsigned index)143 inline T& operator[](unsigned index) { 144 if(index >= objectsize) resize(index + 1); 145 if(!pool[index]) pool[index] = new T; 146 return *pool[index]; 147 } 148 operator [](unsigned index) const149 inline const T& operator[](unsigned index) const { 150 if(index >= objectsize || !pool[index]) throw "vector[] out of bounds"; 151 return *pool[index]; 152 } 153 pointer_vector()154 pointer_vector() : pool(0), poolsize(0), objectsize(0) {} ~pointer_vector()155 ~pointer_vector() { reset(); } 156 }; 157 158 //default vector type 159 template<typename T> class vector : public linear_vector<T> {}; 160 } 161 162 #endif 163