1 /* 2 * Copyright 2011-2018 Blender Foundation 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef __UTIL_ARRAY_H__ 18 #define __UTIL_ARRAY_H__ 19 20 #include <cassert> 21 #include <cstring> 22 23 #include "util/util_aligned_malloc.h" 24 #include "util/util_guarded_allocator.h" 25 #include "util/util_types.h" 26 #include "util/util_vector.h" 27 28 CCL_NAMESPACE_BEGIN 29 30 /* Simplified version of vector, serving multiple purposes: 31 * - somewhat faster in that it does not clear memory on resize/alloc, 32 * this was actually showing up in profiles quite significantly. it 33 * also does not run any constructors/destructors 34 * - if this is used, we are not tempted to use inefficient operations 35 * - aligned allocation for CPU native data types */ 36 37 template<typename T, size_t alignment = MIN_ALIGNMENT_CPU_DATA_TYPES> class array { 38 public: array()39 array() : data_(NULL), datasize_(0), capacity_(0) 40 { 41 } 42 array(size_t newsize)43 explicit array(size_t newsize) 44 { 45 if (newsize == 0) { 46 data_ = NULL; 47 datasize_ = 0; 48 capacity_ = 0; 49 } 50 else { 51 data_ = mem_allocate(newsize); 52 datasize_ = newsize; 53 capacity_ = datasize_; 54 } 55 } 56 array(const array & from)57 array(const array &from) 58 { 59 if (from.datasize_ == 0) { 60 data_ = NULL; 61 datasize_ = 0; 62 capacity_ = 0; 63 } 64 else { 65 data_ = mem_allocate(from.datasize_); 66 if (from.datasize_ > 0) { 67 memcpy(data_, from.data_, from.datasize_ * sizeof(T)); 68 } 69 datasize_ = from.datasize_; 70 capacity_ = datasize_; 71 } 72 } 73 74 array &operator=(const array &from) 75 { 76 if (this != &from) { 77 resize(from.size()); 78 if (datasize_ > 0) { 79 memcpy((void *)data_, from.data_, datasize_ * sizeof(T)); 80 } 81 } 82 83 return *this; 84 } 85 86 array &operator=(const vector<T> &from) 87 { 88 resize(from.size()); 89 90 if (from.size() > 0 && datasize_ > 0) { 91 memcpy(data_, &from[0], datasize_ * sizeof(T)); 92 } 93 94 return *this; 95 } 96 ~array()97 ~array() 98 { 99 mem_free(data_, capacity_); 100 } 101 102 bool operator==(const array<T> &other) const 103 { 104 if (datasize_ != other.datasize_) { 105 return false; 106 } 107 if (datasize_ == 0) { 108 return true; 109 } 110 111 return memcmp(data_, other.data_, datasize_ * sizeof(T)) == 0; 112 } 113 114 bool operator!=(const array<T> &other) const 115 { 116 return !(*this == other); 117 } 118 steal_data(array & from)119 void steal_data(array &from) 120 { 121 if (this != &from) { 122 clear(); 123 124 data_ = from.data_; 125 datasize_ = from.datasize_; 126 capacity_ = from.capacity_; 127 128 from.data_ = NULL; 129 from.datasize_ = 0; 130 from.capacity_ = 0; 131 } 132 } 133 steal_pointer()134 T *steal_pointer() 135 { 136 T *ptr = data_; 137 data_ = NULL; 138 clear(); 139 return ptr; 140 } 141 resize(size_t newsize)142 T *resize(size_t newsize) 143 { 144 if (newsize == 0) { 145 clear(); 146 } 147 else if (newsize != datasize_) { 148 if (newsize > capacity_) { 149 T *newdata = mem_allocate(newsize); 150 if (newdata == NULL) { 151 /* Allocation failed, likely out of memory. */ 152 clear(); 153 return NULL; 154 } 155 else if (data_ != NULL) { 156 memcpy( 157 (void *)newdata, data_, ((datasize_ < newsize) ? datasize_ : newsize) * sizeof(T)); 158 mem_free(data_, capacity_); 159 } 160 data_ = newdata; 161 capacity_ = newsize; 162 } 163 datasize_ = newsize; 164 } 165 return data_; 166 } 167 resize(size_t newsize,const T & value)168 T *resize(size_t newsize, const T &value) 169 { 170 size_t oldsize = size(); 171 resize(newsize); 172 173 for (size_t i = oldsize; i < size(); i++) { 174 data_[i] = value; 175 } 176 177 return data_; 178 } 179 clear()180 void clear() 181 { 182 if (data_ != NULL) { 183 mem_free(data_, capacity_); 184 data_ = NULL; 185 } 186 datasize_ = 0; 187 capacity_ = 0; 188 } 189 empty()190 size_t empty() const 191 { 192 return datasize_ == 0; 193 } 194 size()195 size_t size() const 196 { 197 return datasize_; 198 } 199 data()200 T *data() 201 { 202 return data_; 203 } 204 data()205 const T *data() const 206 { 207 return data_; 208 } 209 210 T &operator[](size_t i) const 211 { 212 assert(i < datasize_); 213 return data_[i]; 214 } 215 reserve(size_t newcapacity)216 void reserve(size_t newcapacity) 217 { 218 if (newcapacity > capacity_) { 219 T *newdata = mem_allocate(newcapacity); 220 if (data_ != NULL) { 221 memcpy(newdata, data_, ((datasize_ < newcapacity) ? datasize_ : newcapacity) * sizeof(T)); 222 mem_free(data_, capacity_); 223 } 224 data_ = newdata; 225 capacity_ = newcapacity; 226 } 227 } 228 capacity()229 size_t capacity() const 230 { 231 return capacity_; 232 } 233 234 // do not use this method unless you are sure the code is not performance critical push_back_slow(const T & t)235 void push_back_slow(const T &t) 236 { 237 if (capacity_ == datasize_) { 238 reserve(datasize_ == 0 ? 1 : (size_t)((datasize_ + 1) * 1.2)); 239 } 240 241 data_[datasize_++] = t; 242 } 243 push_back_reserved(const T & t)244 void push_back_reserved(const T &t) 245 { 246 assert(datasize_ < capacity_); 247 push_back_slow(t); 248 } 249 append(const array<T> & from)250 void append(const array<T> &from) 251 { 252 if (from.size()) { 253 size_t old_size = size(); 254 resize(old_size + from.size()); 255 memcpy(data_ + old_size, from.data(), sizeof(T) * from.size()); 256 } 257 } 258 259 protected: mem_allocate(size_t N)260 inline T *mem_allocate(size_t N) 261 { 262 if (N == 0) { 263 return NULL; 264 } 265 T *mem = (T *)util_aligned_malloc(sizeof(T) * N, alignment); 266 if (mem != NULL) { 267 util_guarded_mem_alloc(sizeof(T) * N); 268 } 269 else { 270 throw std::bad_alloc(); 271 } 272 return mem; 273 } 274 mem_free(T * mem,size_t N)275 inline void mem_free(T *mem, size_t N) 276 { 277 if (mem != NULL) { 278 util_guarded_mem_free(sizeof(T) * N); 279 util_aligned_free(mem); 280 } 281 } 282 283 T *data_; 284 size_t datasize_; 285 size_t capacity_; 286 }; 287 288 CCL_NAMESPACE_END 289 290 #endif /* __UTIL_ARRAY_H__ */ 291