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