1 /* ScummVM - Graphic Adventure Engine 2 * 3 * ScummVM is the legal property of its developers, whose names 4 * are too numerous to list here. Please refer to the COPYRIGHT 5 * file distributed with this source distribution. 6 * 7 * This program is free software; you can redistribute it and/or 8 * modify it under the terms of the GNU General Public License 9 * as published by the Free Software Foundation; either version 2 10 * of the License, or (at your option) any later version. 11 * 12 * This program is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with this program; if not, write to the Free Software 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 20 * 21 */ 22 23 #ifndef COMMON_ARRAY_H 24 #define COMMON_ARRAY_H 25 26 #include "common/scummsys.h" 27 #include "common/algorithm.h" 28 #include "common/textconsole.h" // For error() 29 #include "common/memory.h" 30 31 #ifdef USE_CXX11 32 #include "common/initializer_list.h" 33 #endif 34 35 namespace Common { 36 37 /** 38 * @defgroup common_array Arrays 39 * @ingroup common 40 * 41 * @brief Functions for replacing std arrays. 42 * @{ 43 */ 44 45 /** 46 * This class implements a dynamically sized container, which 47 * can be accessed similarly to a regular C++ array. Accessing 48 * elements is performed in constant time (like with plain arrays). 49 * In addition, you can append, insert, and remove entries (this 50 * is the 'dynamic' part). In general, doing that takes time 51 * proportional to the number of elements in the array. 52 * 53 * The container class closest to this in the C++ standard library is 54 * std::vector. However, there are some differences. 55 */ 56 template<class T> 57 class Array { 58 public: 59 typedef T *iterator; /*!< Array iterator. */ 60 typedef const T *const_iterator; /*!< Const-qualified array iterator. */ 61 62 typedef T value_type; /*!< Value type of the array. */ 63 64 typedef uint size_type; /*!< Size type of the array. */ 65 66 protected: 67 size_type _capacity; /*!< Maximum number of elements the array can hold. */ 68 size_type _size; /*!< How many elements the array holds. */ 69 T *_storage; /*!< Memory used for element storage. */ 70 71 public: Array()72 Array() : _capacity(0), _size(0), _storage(nullptr) {} 73 74 /** 75 * Construct an array with @p count default-inserted instances of @p T. No 76 * copies are made. 77 */ Array(size_type count)78 explicit Array(size_type count) : _size(count) { 79 allocCapacity(count); 80 for (size_type i = 0; i < count; ++i) 81 new ((void *)&_storage[i]) T(); 82 } 83 84 /** 85 * Construct an array with @p count copies of elements with value @p value. 86 */ Array(size_type count,const T & value)87 Array(size_type count, const T &value) : _size(count) { 88 allocCapacity(count); 89 uninitialized_fill_n(_storage, count, value); 90 } 91 92 /** 93 * Construct an array as a copy of the given @p array. 94 */ Array(const Array<T> & array)95 Array(const Array<T> &array) : _capacity(array._size), _size(array._size), _storage(nullptr) { 96 if (array._storage) { 97 allocCapacity(_size); 98 uninitialized_copy(array._storage, array._storage + _size, _storage); 99 } 100 } 101 102 #ifdef USE_CXX11 103 /** 104 * Construct an array as a copy of the given array using the C++11 move semantic. 105 */ Array(Array<T> && old)106 Array(Array<T> &&old) : _capacity(old._capacity), _size(old._size), _storage(old._storage) { 107 old._storage = nullptr; 108 old._capacity = 0; 109 old._size = 0; 110 } 111 112 /** 113 * Construct an array using list initialization. 114 * For example: 115 * @code 116 * Common::Array<int> myArray = {1, 7, 42}; 117 * @endcode 118 * constructs an array with 3 elements whose values are 1, 7, and 42 respectively. 119 * @note 120 * This constructor is only available when C++11 support is enabled. 121 */ Array(std::initializer_list<T> list)122 Array(std::initializer_list<T> list) : _size(list.size()) { 123 allocCapacity(list.size()); 124 if (_storage) 125 Common::uninitialized_copy(list.begin(), list.end(), _storage); 126 } 127 #endif 128 129 /** 130 * Construct an array by copying data from a regular array. 131 */ 132 template<class T2> Array(const T2 * array,size_type n)133 Array(const T2 *array, size_type n) { 134 _size = n; 135 allocCapacity(n); 136 uninitialized_copy(array, array + _size, _storage); 137 } 138 ~Array()139 ~Array() { 140 freeStorage(_storage, _size); 141 _storage = nullptr; 142 _capacity = _size = 0; 143 } 144 145 /** Append an element to the end of the array. */ push_back(const T & element)146 void push_back(const T &element) { 147 if (_size + 1 <= _capacity) 148 new ((void *)&_storage[_size++]) T(element); 149 else 150 insert_aux(end(), &element, &element + 1); 151 } 152 153 /** Append an element to the end of the array. */ push_back(const Array<T> & array)154 void push_back(const Array<T> &array) { 155 if (_size + array.size() <= _capacity) { 156 uninitialized_copy(array.begin(), array.end(), end()); 157 _size += array.size(); 158 } else 159 insert_aux(end(), array.begin(), array.end()); 160 } 161 162 /** Remove the last element of the array. */ pop_back()163 void pop_back() { 164 assert(_size > 0); 165 _size--; 166 // We also need to destroy the last object properly here. 167 _storage[_size].~T(); 168 } 169 170 /** Return a pointer to the underlying memory serving as element storage. */ data()171 const T *data() const { 172 return _storage; 173 } 174 175 /** Return a pointer to the underlying memory serving as element storage. */ data()176 T *data() { 177 return _storage; 178 } 179 180 /** Return a reference to the first element of the array. */ front()181 T &front() { 182 assert(_size > 0); 183 return _storage[0]; 184 } 185 186 /** Return a reference to the first element of the array. */ front()187 const T &front() const { 188 assert(_size > 0); 189 return _storage[0]; 190 } 191 192 /** Return a reference to the last element of the array. */ back()193 T &back() { 194 assert(_size > 0); 195 return _storage[_size-1]; 196 } 197 198 /** Return a reference to the last element of the array. */ back()199 const T &back() const { 200 assert(_size > 0); 201 return _storage[_size-1]; 202 } 203 204 /** Insert an element into the array at the given position. */ insert_at(size_type idx,const T & element)205 void insert_at(size_type idx, const T &element) { 206 assert(idx <= _size); 207 insert_aux(_storage + idx, &element, &element + 1); 208 } 209 210 /** Insert copies of all the elements from the given array into this array at the given position. */ insert_at(size_type idx,const Array<T> & array)211 void insert_at(size_type idx, const Array<T> &array) { 212 assert(idx <= _size); 213 insert_aux(_storage + idx, array.begin(), array.end()); 214 } 215 216 /** 217 * Insert an element before @p pos. 218 */ insert(iterator pos,const T & element)219 void insert(iterator pos, const T &element) { 220 insert_aux(pos, &element, &element + 1); 221 } 222 223 /** Remove an element at the given position from the array and return the value of that element. */ remove_at(size_type idx)224 T remove_at(size_type idx) { 225 assert(idx < _size); 226 T tmp = _storage[idx]; 227 copy(_storage + idx + 1, _storage + _size, _storage + idx); 228 _size--; 229 // We also need to destroy the last object properly here. 230 _storage[_size].~T(); 231 return tmp; 232 } 233 234 // TODO: insert, remove, ... 235 236 /** Return a reference to the element at the given position in the array. */ 237 T &operator[](size_type idx) { 238 assert(idx < _size); 239 return _storage[idx]; 240 } 241 242 /** Return a const reference to the element at the given position in the array. */ 243 const T &operator[](size_type idx) const { 244 assert(idx < _size); 245 return _storage[idx]; 246 } 247 248 /** Assign the given @p array to this array. */ 249 Array<T> &operator=(const Array<T> &array) { 250 if (this == &array) 251 return *this; 252 253 freeStorage(_storage, _size); 254 _size = array._size; 255 allocCapacity(_size); 256 uninitialized_copy(array._storage, array._storage + _size, _storage); 257 258 return *this; 259 } 260 261 #ifdef USE_CXX11 262 /** Assign the given array to this array using the C++11 move semantic. */ 263 Array &operator=(Array<T> &&old) { 264 if (this == &old) 265 return *this; 266 267 freeStorage(_storage, _size); 268 _capacity = old._capacity; 269 _size = old._size; 270 _storage = old._storage; 271 272 old._storage = nullptr; 273 old._capacity = 0; 274 old._size = 0; 275 276 return *this; 277 } 278 #endif 279 280 /** Return the size of the array. */ size()281 size_type size() const { 282 return _size; 283 } 284 285 /** Clear the array of all its elements. */ clear()286 void clear() { 287 freeStorage(_storage, _size); 288 _storage = nullptr; 289 _size = 0; 290 _capacity = 0; 291 } 292 293 /** Erase the element at @p pos position and return an iterator pointing to the next element in the array. */ erase(iterator pos)294 iterator erase(iterator pos) { 295 copy(pos + 1, _storage + _size, pos); 296 _size--; 297 // We also need to destroy the last object properly here. 298 _storage[_size].~T(); 299 return pos; 300 } 301 302 /** Check whether the array is empty. */ empty()303 bool empty() const { 304 return (_size == 0); 305 } 306 307 /** Check whether two arrays are identical. */ 308 bool operator==(const Array<T> &other) const { 309 if (this == &other) 310 return true; 311 if (_size != other._size) 312 return false; 313 for (size_type i = 0; i < _size; ++i) { 314 if (_storage[i] != other._storage[i]) 315 return false; 316 } 317 return true; 318 } 319 320 /** Check if two arrays are different. */ 321 bool operator!=(const Array<T> &other) const { 322 return !(*this == other); 323 } 324 325 /** Return an iterator pointing to the first element in the array. */ begin()326 iterator begin() { 327 return _storage; 328 } 329 330 /** Return an iterator pointing past the last element in the array. */ end()331 iterator end() { 332 return _storage + _size; 333 } 334 335 /** Return a const iterator pointing to the first element in the array. */ begin()336 const_iterator begin() const { 337 return _storage; 338 } 339 340 /** Return a const iterator pointing past the last element in the array. */ end()341 const_iterator end() const { 342 return _storage + _size; 343 } 344 345 /** Reserve enough memory in the array so that it can store at least the given number of elements. 346 * The current content of the array is not modified. 347 */ reserve(size_type newCapacity)348 void reserve(size_type newCapacity) { 349 if (newCapacity <= _capacity) 350 return; 351 352 T *oldStorage = _storage; 353 allocCapacity(newCapacity); 354 355 if (oldStorage) { 356 // Copy old data 357 uninitialized_copy(oldStorage, oldStorage + _size, _storage); 358 freeStorage(oldStorage, _size); 359 } 360 } 361 362 /** Change the size of the array. */ resize(size_type newSize)363 void resize(size_type newSize) { 364 reserve(newSize); 365 for (size_type i = newSize; i < _size; ++i) 366 _storage[i].~T(); 367 for (size_type i = _size; i < newSize; ++i) 368 new ((void *)&_storage[i]) T(); 369 _size = newSize; 370 } 371 372 /** Assign to this array the elements between the given iterators from another array, 373 * from @p first included to @p last excluded. 374 */ assign(const_iterator first,const_iterator last)375 void assign(const_iterator first, const_iterator last) { 376 resize(distance(first, last)); // FIXME: ineffective? 377 T *dst = _storage; 378 while (first != last) 379 *dst++ = *first++; 380 } 381 382 protected: 383 /** Round up capacity to the next power of 2. 384 * A minimal capacity of 8 is used. 385 */ roundUpCapacity(size_type capacity)386 static size_type roundUpCapacity(size_type capacity) { 387 size_type capa = 8; 388 while (capa < capacity) 389 capa <<= 1; 390 return capa; 391 } 392 393 /** Allocate a specific capacity for the array. */ allocCapacity(size_type capacity)394 void allocCapacity(size_type capacity) { 395 _capacity = capacity; 396 if (capacity) { 397 _storage = (T *)malloc(sizeof(T) * capacity); 398 if (!_storage) 399 ::error("Common::Array: failure to allocate %u bytes", capacity * (size_type)sizeof(T)); 400 } else { 401 _storage = nullptr; 402 } 403 } 404 405 /** Free the storage used by the array. */ freeStorage(T * storage,const size_type elements)406 void freeStorage(T *storage, const size_type elements) { 407 for (size_type i = 0; i < elements; ++i) 408 storage[i].~T(); 409 free(storage); 410 } 411 412 /** 413 * Insert a range of elements coming from this or another array. 414 * Unlike std::vector::insert, this method does not accept 415 * arbitrary iterators, mainly because our iterator system is 416 * seriously limited and does not distinguish between input iterators, 417 * output iterators, forward iterators, or random access iterators. 418 * 419 * So, we simply restrict to Array iterators. Extending this to arbitrary 420 * random access iterators would be trivial. 421 * 422 * Moreover, this method does not handle all cases of inserting a subrange 423 * of an array into itself; this is why it is private for now. 424 */ insert_aux(iterator pos,const_iterator first,const_iterator last)425 iterator insert_aux(iterator pos, const_iterator first, const_iterator last) { 426 assert(_storage <= pos && pos <= _storage + _size); 427 assert(first <= last); 428 const size_type n = last - first; 429 if (n) { 430 const size_type idx = pos - _storage; 431 if (_size + n > _capacity || (_storage <= first && first <= _storage + _size)) { 432 T *const oldStorage = _storage; 433 434 // If there is not enough space, allocate more. 435 // Likewise, if this is a self-insert, we allocate new 436 // storage to avoid conflicts. 437 allocCapacity(roundUpCapacity(_size + n)); 438 439 // Copy the data from the old storage till the position where 440 // we insert new data 441 uninitialized_copy(oldStorage, oldStorage + idx, _storage); 442 // Copy the data we insert 443 uninitialized_copy(first, last, _storage + idx); 444 // Afterwards, copy the old data from the position where we 445 // insert. 446 uninitialized_copy(oldStorage + idx, oldStorage + _size, _storage + idx + n); 447 448 freeStorage(oldStorage, _size); 449 } else if (idx + n <= _size) { 450 // Make room for the new elements by shifting back 451 // existing ones. 452 // 1. Move a part of the data to the uninitialized area 453 uninitialized_copy(_storage + _size - n, _storage + _size, _storage + _size); 454 // 2. Move a part of the data to the initialized area 455 copy_backward(pos, _storage + _size - n, _storage + _size); 456 457 // Insert the new elements. 458 copy(first, last, pos); 459 } else { 460 // Copy the old data from the position till the end to the new 461 // place. 462 uninitialized_copy(pos, _storage + _size, _storage + idx + n); 463 464 // Copy a part of the new data to the position inside the 465 // initialized space. 466 copy(first, first + (_size - idx), pos); 467 468 // Copy a part of the new data to the position inside the 469 // uninitialized space. 470 uninitialized_copy(first + (_size - idx), last, _storage + _size); 471 } 472 473 // Finally, update the internal state 474 _size += n; 475 } 476 return pos; 477 } 478 479 }; 480 481 /** 482 * Array with sorted nodes. 483 */ 484 template<class T, typename CompareArgType = const void *> 485 class SortedArray : public Array<T> { 486 public: 487 typedef int (*Comparator)(CompareArgType, CompareArgType); 488 typedef T *iterator; 489 typedef uint size_type; 490 SortedArray(Comparator comparator)491 SortedArray(Comparator comparator) { 492 _comparator = comparator; 493 } 494 495 /** 496 * Insert an element at the sorted position. 497 */ insert(const T & element)498 void insert(const T &element) { 499 if (!this->_size) { 500 this->insert_aux(this->_storage, &element, &element + 1); 501 return; 502 } 503 504 T *where = bsearchMin(element); 505 506 if (where > this->_storage + this->_size) 507 Array<T>::push_back(element); 508 else 509 Array<T>::insert(where, element); 510 } 511 512 private: 513 T &operator[](size_type idx); 514 515 void insert_at(size_type idx, const T &element); 516 517 void insert_at(size_type idx, const Array<T> &array); 518 519 void insert(iterator pos, const T &element); 520 521 void push_back(const T &element); 522 523 void push_back(const Array<T> &array); 524 525 // Based on code Copyright (C) 2008-2009 Ksplice, Inc. 526 // Author: Tim Abbott <tabbott@ksplice.com> 527 // Licensed under GPLv2+ bsearchMin(CompareArgType key)528 T *bsearchMin(CompareArgType key) { 529 uint start_ = 0, end_ = this->_size; 530 int result; 531 532 while (start_ < end_) { 533 uint mid = start_ + (end_ - start_) / 2; 534 535 result = this->_comparator(key, this->_storage[mid]); 536 if (result < 0) 537 end_ = mid; 538 else 539 start_ = mid + 1; 540 } 541 542 return &this->_storage[start_]; 543 } 544 545 Comparator _comparator; 546 }; 547 548 /** @} */ 549 550 } // End of namespace Common 551 552 #endif 553