ovr_sdk

annotate LibOVR/Src/Kernel/OVR_Array.h @ 0:1b39a1b46319

find changesets by author, revision, files, or words in the commit message
initial 0.4.4
author John Tsiombikas <nuclear@member.fsf.org>
date Wed, 14 Jan 2015 06:51:16 +0200
parents
children
rev   line source
nuclear@0 1 /************************************************************************************
nuclear@0 2
nuclear@0 3 PublicHeader: OVR_Kernel.h
nuclear@0 4 Filename : OVR_Array.h
nuclear@0 5 Content : Template implementation for Array
nuclear@0 6 Created : September 19, 2012
nuclear@0 7 Notes :
nuclear@0 8
nuclear@0 9 Copyright : Copyright 2014 Oculus VR, LLC All Rights reserved.
nuclear@0 10
nuclear@0 11 Licensed under the Oculus VR Rift SDK License Version 3.2 (the "License");
nuclear@0 12 you may not use the Oculus VR Rift SDK except in compliance with the License,
nuclear@0 13 which is provided at the time of installation or download, or which
nuclear@0 14 otherwise accompanies this software in either electronic or hard copy form.
nuclear@0 15
nuclear@0 16 You may obtain a copy of the License at
nuclear@0 17
nuclear@0 18 http://www.oculusvr.com/licenses/LICENSE-3.2
nuclear@0 19
nuclear@0 20 Unless required by applicable law or agreed to in writing, the Oculus VR SDK
nuclear@0 21 distributed under the License is distributed on an "AS IS" BASIS,
nuclear@0 22 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
nuclear@0 23 See the License for the specific language governing permissions and
nuclear@0 24 limitations under the License.
nuclear@0 25
nuclear@0 26 ************************************************************************************/
nuclear@0 27
nuclear@0 28 #ifndef OVR_Array_h
nuclear@0 29 #define OVR_Array_h
nuclear@0 30
nuclear@0 31 #include "OVR_ContainerAllocator.h"
nuclear@0 32
nuclear@0 33 namespace OVR {
nuclear@0 34
nuclear@0 35 //-----------------------------------------------------------------------------------
nuclear@0 36 // ***** ArrayDefaultPolicy
nuclear@0 37 //
nuclear@0 38 // Default resize behavior. No minimal capacity, Granularity=4,
nuclear@0 39 // Shrinking as needed. ArrayConstPolicy actually is the same as
nuclear@0 40 // ArrayDefaultPolicy, but parametrized with constants.
nuclear@0 41 // This struct is used only in order to reduce the template "matroska".
nuclear@0 42 struct ArrayDefaultPolicy
nuclear@0 43 {
nuclear@0 44 ArrayDefaultPolicy() : Capacity(0) {}
nuclear@0 45 ArrayDefaultPolicy(const ArrayDefaultPolicy&) : Capacity(0) {}
nuclear@0 46
nuclear@0 47 size_t GetMinCapacity() const { return 0; }
nuclear@0 48 size_t GetGranularity() const { return 4; }
nuclear@0 49 bool NeverShrinking() const { return 0; }
nuclear@0 50
nuclear@0 51 size_t GetCapacity() const { return Capacity; }
nuclear@0 52 void SetCapacity(size_t capacity) { Capacity = capacity; }
nuclear@0 53 private:
nuclear@0 54 size_t Capacity;
nuclear@0 55 };
nuclear@0 56
nuclear@0 57
nuclear@0 58 //-----------------------------------------------------------------------------------
nuclear@0 59 // ***** ArrayConstPolicy
nuclear@0 60 //
nuclear@0 61 // Statically parametrized resizing behavior:
nuclear@0 62 // MinCapacity, Granularity, and Shrinking flag.
nuclear@0 63 template<int MinCapacity=0, int Granularity=4, bool NeverShrink=false>
nuclear@0 64 struct ArrayConstPolicy
nuclear@0 65 {
nuclear@0 66 typedef ArrayConstPolicy<MinCapacity, Granularity, NeverShrink> SelfType;
nuclear@0 67
nuclear@0 68 ArrayConstPolicy() : Capacity(0) {}
nuclear@0 69 ArrayConstPolicy(const SelfType&) : Capacity(0) {}
nuclear@0 70
nuclear@0 71 size_t GetMinCapacity() const { return MinCapacity; }
nuclear@0 72 size_t GetGranularity() const { return Granularity; }
nuclear@0 73 bool NeverShrinking() const { return NeverShrink; }
nuclear@0 74
nuclear@0 75 size_t GetCapacity() const { return Capacity; }
nuclear@0 76 void SetCapacity(size_t capacity) { Capacity = capacity; }
nuclear@0 77 private:
nuclear@0 78 size_t Capacity;
nuclear@0 79 };
nuclear@0 80
nuclear@0 81 //-----------------------------------------------------------------------------------
nuclear@0 82 // ***** ArrayDataBase
nuclear@0 83 //
nuclear@0 84 // Basic operations with array data: Reserve, Resize, Free, ArrayPolicy.
nuclear@0 85 // For internal use only: ArrayData,ArrayDataCC and others.
nuclear@0 86 template<class T, class Allocator, class SizePolicy>
nuclear@0 87 struct ArrayDataBase
nuclear@0 88 {
nuclear@0 89 typedef T ValueType;
nuclear@0 90 typedef Allocator AllocatorType;
nuclear@0 91 typedef SizePolicy SizePolicyType;
nuclear@0 92 typedef ArrayDataBase<T, Allocator, SizePolicy> SelfType;
nuclear@0 93
nuclear@0 94 ArrayDataBase()
nuclear@0 95 : Data(0), Size(0), Policy() {}
nuclear@0 96
nuclear@0 97 ArrayDataBase(const SizePolicy& p)
nuclear@0 98 : Data(0), Size(0), Policy(p) {}
nuclear@0 99
nuclear@0 100 ~ArrayDataBase()
nuclear@0 101 {
nuclear@0 102 Allocator::DestructArray(Data, Size);
nuclear@0 103 Allocator::Free(Data);
nuclear@0 104 }
nuclear@0 105
nuclear@0 106 size_t GetCapacity() const
nuclear@0 107 {
nuclear@0 108 return Policy.GetCapacity();
nuclear@0 109 }
nuclear@0 110
nuclear@0 111 void ClearAndRelease()
nuclear@0 112 {
nuclear@0 113 Allocator::DestructArray(Data, Size);
nuclear@0 114 Allocator::Free(Data);
nuclear@0 115 Data = 0;
nuclear@0 116 Size = 0;
nuclear@0 117 Policy.SetCapacity(0);
nuclear@0 118 }
nuclear@0 119
nuclear@0 120 void Reserve(size_t newCapacity)
nuclear@0 121 {
nuclear@0 122 if (Policy.NeverShrinking() && newCapacity < GetCapacity())
nuclear@0 123 return;
nuclear@0 124
nuclear@0 125 if (newCapacity < Policy.GetMinCapacity())
nuclear@0 126 newCapacity = Policy.GetMinCapacity();
nuclear@0 127
nuclear@0 128 // Resize the buffer.
nuclear@0 129 if (newCapacity == 0)
nuclear@0 130 {
nuclear@0 131 if (Data)
nuclear@0 132 {
nuclear@0 133 Allocator::Free(Data);
nuclear@0 134 Data = 0;
nuclear@0 135 }
nuclear@0 136 Policy.SetCapacity(0);
nuclear@0 137 }
nuclear@0 138 else
nuclear@0 139 {
nuclear@0 140 size_t gran = Policy.GetGranularity();
nuclear@0 141 newCapacity = (newCapacity + gran - 1) / gran * gran;
nuclear@0 142 if (Data)
nuclear@0 143 {
nuclear@0 144 if (Allocator::IsMovable())
nuclear@0 145 {
nuclear@0 146 Data = (T*)Allocator::Realloc(Data, sizeof(T) * newCapacity);
nuclear@0 147 }
nuclear@0 148 else
nuclear@0 149 {
nuclear@0 150 T* newData = (T*)Allocator::Alloc(sizeof(T) * newCapacity);
nuclear@0 151 size_t i, s;
nuclear@0 152 s = (Size < newCapacity) ? Size : newCapacity;
nuclear@0 153 for (i = 0; i < s; ++i)
nuclear@0 154 {
nuclear@0 155 Allocator::Construct(&newData[i], Data[i]);
nuclear@0 156 Allocator::Destruct(&Data[i]);
nuclear@0 157 }
nuclear@0 158 for (i = s; i < Size; ++i)
nuclear@0 159 {
nuclear@0 160 Allocator::Destruct(&Data[i]);
nuclear@0 161 }
nuclear@0 162 Allocator::Free(Data);
nuclear@0 163 Data = newData;
nuclear@0 164 }
nuclear@0 165 }
nuclear@0 166 else
nuclear@0 167 {
nuclear@0 168 Data = (T*)Allocator::Alloc(sizeof(T) * newCapacity);
nuclear@0 169 //memset(Buffer, 0, (sizeof(ValueType) * newSize)); // Do we need this?
nuclear@0 170 }
nuclear@0 171 Policy.SetCapacity(newCapacity);
nuclear@0 172 // OVR_ASSERT(Data); // need to throw (or something) on alloc failure!
nuclear@0 173 }
nuclear@0 174 }
nuclear@0 175
nuclear@0 176 // This version of Resize DOES NOT construct the elements.
nuclear@0 177 // It's done to optimize PushBack, which uses a copy constructor
nuclear@0 178 // instead of the default constructor and assignment
nuclear@0 179 void ResizeNoConstruct(size_t newSize)
nuclear@0 180 {
nuclear@0 181 size_t oldSize = Size;
nuclear@0 182
nuclear@0 183 if (newSize < oldSize)
nuclear@0 184 {
nuclear@0 185 Allocator::DestructArray(Data + newSize, oldSize - newSize);
nuclear@0 186 if (newSize < (Policy.GetCapacity() >> 1))
nuclear@0 187 {
nuclear@0 188 Reserve(newSize);
nuclear@0 189 }
nuclear@0 190 }
nuclear@0 191 else if(newSize >= Policy.GetCapacity())
nuclear@0 192 {
nuclear@0 193 Reserve(newSize + (newSize >> 2));
nuclear@0 194 }
nuclear@0 195 //! IMPORTANT to modify Size only after Reserve completes, because garbage collectable
nuclear@0 196 // array may use this array and may traverse it during Reserve (in the case, if
nuclear@0 197 // collection occurs because of heap limit exceeded).
nuclear@0 198 Size = newSize;
nuclear@0 199 }
nuclear@0 200
nuclear@0 201 ValueType* Data;
nuclear@0 202 size_t Size;
nuclear@0 203 SizePolicy Policy;
nuclear@0 204 };
nuclear@0 205
nuclear@0 206
nuclear@0 207
nuclear@0 208 //-----------------------------------------------------------------------------------
nuclear@0 209 // ***** ArrayData
nuclear@0 210 //
nuclear@0 211 // General purpose array data.
nuclear@0 212 // For internal use only in Array, ArrayLH, ArrayPOD and so on.
nuclear@0 213 template<class T, class Allocator, class SizePolicy>
nuclear@0 214 struct ArrayData : ArrayDataBase<T, Allocator, SizePolicy>
nuclear@0 215 {
nuclear@0 216 typedef T ValueType;
nuclear@0 217 typedef Allocator AllocatorType;
nuclear@0 218 typedef SizePolicy SizePolicyType;
nuclear@0 219 typedef ArrayDataBase<T, Allocator, SizePolicy> BaseType;
nuclear@0 220 typedef ArrayData <T, Allocator, SizePolicy> SelfType;
nuclear@0 221
nuclear@0 222 ArrayData()
nuclear@0 223 : BaseType() { }
nuclear@0 224
nuclear@0 225 ArrayData(size_t size)
nuclear@0 226 : BaseType() { Resize(size); }
nuclear@0 227
nuclear@0 228 ArrayData(const SelfType& a)
nuclear@0 229 : BaseType(a.Policy) { Append(a.Data, a.Size); }
nuclear@0 230
nuclear@0 231
nuclear@0 232 void Resize(size_t newSize)
nuclear@0 233 {
nuclear@0 234 size_t oldSize = this->Size;
nuclear@0 235 BaseType::ResizeNoConstruct(newSize);
nuclear@0 236 if(newSize > oldSize)
nuclear@0 237 Allocator::ConstructArray(this->Data + oldSize, newSize - oldSize);
nuclear@0 238 }
nuclear@0 239
nuclear@0 240 void PushBack(const ValueType& val)
nuclear@0 241 {
nuclear@0 242 BaseType::ResizeNoConstruct(this->Size + 1);
nuclear@0 243 OVR_ASSERT(this->Data != NULL);
nuclear@0 244 Allocator::Construct(this->Data + this->Size - 1, val);
nuclear@0 245 }
nuclear@0 246
nuclear@0 247 template<class S>
nuclear@0 248 void PushBackAlt(const S& val)
nuclear@0 249 {
nuclear@0 250 BaseType::ResizeNoConstruct(this->Size + 1);
nuclear@0 251 Allocator::ConstructAlt(this->Data + this->Size - 1, val);
nuclear@0 252 }
nuclear@0 253
nuclear@0 254 // Append the given data to the array.
nuclear@0 255 void Append(const ValueType other[], size_t count)
nuclear@0 256 {
nuclear@0 257 if (count)
nuclear@0 258 {
nuclear@0 259 size_t oldSize = this->Size;
nuclear@0 260 BaseType::ResizeNoConstruct(this->Size + count);
nuclear@0 261 Allocator::ConstructArray(this->Data + oldSize, count, other);
nuclear@0 262 }
nuclear@0 263 }
nuclear@0 264 };
nuclear@0 265
nuclear@0 266
nuclear@0 267
nuclear@0 268 //-----------------------------------------------------------------------------------
nuclear@0 269 // ***** ArrayDataCC
nuclear@0 270 //
nuclear@0 271 // A modification of ArrayData that always copy-constructs new elements
nuclear@0 272 // using a specified DefaultValue. For internal use only in ArrayCC.
nuclear@0 273 template<class T, class Allocator, class SizePolicy>
nuclear@0 274 struct ArrayDataCC : ArrayDataBase<T, Allocator, SizePolicy>
nuclear@0 275 {
nuclear@0 276 typedef T ValueType;
nuclear@0 277 typedef Allocator AllocatorType;
nuclear@0 278 typedef SizePolicy SizePolicyType;
nuclear@0 279 typedef ArrayDataBase<T, Allocator, SizePolicy> BaseType;
nuclear@0 280 typedef ArrayDataCC <T, Allocator, SizePolicy> SelfType;
nuclear@0 281
nuclear@0 282 ArrayDataCC(const ValueType& defval)
nuclear@0 283 : BaseType(), DefaultValue(defval) { }
nuclear@0 284
nuclear@0 285 ArrayDataCC(const ValueType& defval, size_t size)
nuclear@0 286 : BaseType(), DefaultValue(defval) { Resize(size); }
nuclear@0 287
nuclear@0 288 ArrayDataCC(const SelfType& a)
nuclear@0 289 : BaseType(a.Policy), DefaultValue(a.DefaultValue) { Append(a.Data, a.Size); }
nuclear@0 290
nuclear@0 291
nuclear@0 292 void Resize(size_t newSize)
nuclear@0 293 {
nuclear@0 294 size_t oldSize = this->Size;
nuclear@0 295 BaseType::ResizeNoConstruct(newSize);
nuclear@0 296 if(newSize > oldSize)
nuclear@0 297 Allocator::ConstructArray(this->Data + oldSize, newSize - oldSize, DefaultValue);
nuclear@0 298 }
nuclear@0 299
nuclear@0 300 void PushBack(const ValueType& val)
nuclear@0 301 {
nuclear@0 302 BaseType::ResizeNoConstruct(this->Size + 1);
nuclear@0 303 Allocator::Construct(this->Data + this->Size - 1, val);
nuclear@0 304 }
nuclear@0 305
nuclear@0 306 template<class S>
nuclear@0 307 void PushBackAlt(const S& val)
nuclear@0 308 {
nuclear@0 309 BaseType::ResizeNoConstruct(this->Size + 1);
nuclear@0 310 Allocator::ConstructAlt(this->Data + this->Size - 1, val);
nuclear@0 311 }
nuclear@0 312
nuclear@0 313 // Append the given data to the array.
nuclear@0 314 void Append(const ValueType other[], size_t count)
nuclear@0 315 {
nuclear@0 316 if (count)
nuclear@0 317 {
nuclear@0 318 size_t oldSize = this->Size;
nuclear@0 319 BaseType::ResizeNoConstruct(this->Size + count);
nuclear@0 320 Allocator::ConstructArray(this->Data + oldSize, count, other);
nuclear@0 321 }
nuclear@0 322 }
nuclear@0 323
nuclear@0 324 ValueType DefaultValue;
nuclear@0 325 };
nuclear@0 326
nuclear@0 327
nuclear@0 328
nuclear@0 329
nuclear@0 330
nuclear@0 331 //-----------------------------------------------------------------------------------
nuclear@0 332 // ***** ArrayBase
nuclear@0 333 //
nuclear@0 334 // Resizable array. The behavior can be POD (suffix _POD) and
nuclear@0 335 // Movable (no suffix) depending on the allocator policy.
nuclear@0 336 // In case of _POD the constructors and destructors are not called.
nuclear@0 337 //
nuclear@0 338 // Arrays can't handle non-movable objects! Don't put anything in here
nuclear@0 339 // that can't be moved around by bitwise copy.
nuclear@0 340 //
nuclear@0 341 // The addresses of elements are not persistent! Don't keep the address
nuclear@0 342 // of an element; the array contents will move around as it gets resized.
nuclear@0 343 template<class ArrayData>
nuclear@0 344 class ArrayBase
nuclear@0 345 {
nuclear@0 346 public:
nuclear@0 347 typedef typename ArrayData::ValueType ValueType;
nuclear@0 348 typedef typename ArrayData::AllocatorType AllocatorType;
nuclear@0 349 typedef typename ArrayData::SizePolicyType SizePolicyType;
nuclear@0 350 typedef ArrayBase<ArrayData> SelfType;
nuclear@0 351
nuclear@0 352
nuclear@0 353 #undef new
nuclear@0 354 OVR_MEMORY_REDEFINE_NEW(ArrayBase)
nuclear@0 355 // Redefine operator 'new' if necessary.
nuclear@0 356 #if defined(OVR_DEFINE_NEW)
nuclear@0 357 #define new OVR_DEFINE_NEW
nuclear@0 358 #endif
nuclear@0 359
nuclear@0 360
nuclear@0 361 ArrayBase()
nuclear@0 362 : Data() {}
nuclear@0 363 ArrayBase(size_t size)
nuclear@0 364 : Data(size) {}
nuclear@0 365 ArrayBase(const SelfType& a)
nuclear@0 366 : Data(a.Data) {}
nuclear@0 367
nuclear@0 368 ArrayBase(const ValueType& defval)
nuclear@0 369 : Data(defval) {}
nuclear@0 370 ArrayBase(const ValueType& defval, size_t size)
nuclear@0 371 : Data(defval, size) {}
nuclear@0 372
nuclear@0 373 SizePolicyType* GetSizePolicy() const { return Data.Policy; }
nuclear@0 374 void SetSizePolicy(const SizePolicyType& p) { Data.Policy = p; }
nuclear@0 375
nuclear@0 376 bool NeverShrinking()const { return Data.Policy.NeverShrinking(); }
nuclear@0 377 size_t GetSize() const { return Data.Size; }
nuclear@0 378 int GetSizeI() const { return (int)Data.Size; }
nuclear@0 379 bool IsEmpty() const { return Data.Size == 0; }
nuclear@0 380 size_t GetCapacity() const { return Data.GetCapacity(); }
nuclear@0 381 size_t GetNumBytes() const { return Data.GetCapacity() * sizeof(ValueType); }
nuclear@0 382
nuclear@0 383 void ClearAndRelease() { Data.ClearAndRelease(); }
nuclear@0 384 void Clear() { Data.Resize(0); }
nuclear@0 385 void Resize(size_t newSize) { Data.Resize(newSize); }
nuclear@0 386
nuclear@0 387 // Reserve can only increase the capacity
nuclear@0 388 void Reserve(size_t newCapacity)
nuclear@0 389 {
nuclear@0 390 if (newCapacity > Data.GetCapacity())
nuclear@0 391 Data.Reserve(newCapacity);
nuclear@0 392 }
nuclear@0 393
nuclear@0 394 // Basic access.
nuclear@0 395 ValueType& At(size_t index)
nuclear@0 396 {
nuclear@0 397 OVR_ASSERT((Data.Data) && (index < Data.Size)); // Asserting that Data.Data is valid helps static analysis tools.
nuclear@0 398 return Data.Data[index];
nuclear@0 399 }
nuclear@0 400 const ValueType& At(size_t index) const
nuclear@0 401 {
nuclear@0 402 OVR_ASSERT((Data.Data) && (index < Data.Size));
nuclear@0 403 return Data.Data[index];
nuclear@0 404 }
nuclear@0 405
nuclear@0 406 ValueType ValueAt(size_t index) const
nuclear@0 407 {
nuclear@0 408 OVR_ASSERT((Data.Data) && (index < Data.Size));
nuclear@0 409 return Data.Data[index];
nuclear@0 410 }
nuclear@0 411
nuclear@0 412 // Basic access.
nuclear@0 413 ValueType& operator [] (size_t index)
nuclear@0 414 {
nuclear@0 415 OVR_ASSERT((Data.Data) && (index < Data.Size));
nuclear@0 416 return Data.Data[index];
nuclear@0 417 }
nuclear@0 418 const ValueType& operator [] (size_t index) const
nuclear@0 419 {
nuclear@0 420 OVR_ASSERT((Data.Data) && (index < Data.Size));
nuclear@0 421 return Data.Data[index];
nuclear@0 422 }
nuclear@0 423
nuclear@0 424 // Raw pointer to the data. Use with caution!
nuclear@0 425 const ValueType* GetDataPtr() const { return Data.Data; }
nuclear@0 426 ValueType* GetDataPtr() { return Data.Data; }
nuclear@0 427
nuclear@0 428 // Insert the given element at the end of the array.
nuclear@0 429 void PushBack(const ValueType& val)
nuclear@0 430 {
nuclear@0 431 // DO NOT pass elements of your own vector into
nuclear@0 432 // push_back()! Since we're using references,
nuclear@0 433 // resize() may munge the element storage!
nuclear@0 434 // OVR_ASSERT(&val < &Buffer[0] || &val > &Buffer[BufferSize]);
nuclear@0 435 Data.PushBack(val);
nuclear@0 436 }
nuclear@0 437
nuclear@0 438 template<class S>
nuclear@0 439 void PushBackAlt(const S& val)
nuclear@0 440 {
nuclear@0 441 Data.PushBackAlt(val);
nuclear@0 442 }
nuclear@0 443
nuclear@0 444 // Remove the last element.
nuclear@0 445 void PopBack(size_t count = 1)
nuclear@0 446 {
nuclear@0 447 OVR_ASSERT(Data.Size >= count);
nuclear@0 448 Data.Resize(Data.Size - count);
nuclear@0 449 }
nuclear@0 450
nuclear@0 451 ValueType& PushDefault()
nuclear@0 452 {
nuclear@0 453 Data.PushBack(ValueType());
nuclear@0 454 return Back();
nuclear@0 455 }
nuclear@0 456
nuclear@0 457 ValueType Pop()
nuclear@0 458 {
nuclear@0 459 OVR_ASSERT((Data.Data) && (Data.Size > 0));
nuclear@0 460 ValueType t = Back();
nuclear@0 461 PopBack();
nuclear@0 462 return t;
nuclear@0 463 }
nuclear@0 464
nuclear@0 465
nuclear@0 466 // Access the first element.
nuclear@0 467 ValueType& Front() { return At(0); }
nuclear@0 468 const ValueType& Front() const { return At(0); }
nuclear@0 469
nuclear@0 470 // Access the last element.
nuclear@0 471 ValueType& Back() { return At(Data.Size - 1); }
nuclear@0 472 const ValueType& Back() const { return At(Data.Size - 1); }
nuclear@0 473
nuclear@0 474 // Array copy. Copies the contents of a into this array.
nuclear@0 475 const SelfType& operator = (const SelfType& a)
nuclear@0 476 {
nuclear@0 477 Resize(a.GetSize());
nuclear@0 478 OVR_ASSERT((Data.Data != NULL) || (Data.Size == 0));
nuclear@0 479 for (size_t i = 0; i < Data.Size; i++) {
nuclear@0 480 *(Data.Data + i) = a[i];
nuclear@0 481 }
nuclear@0 482 return *this;
nuclear@0 483 }
nuclear@0 484
nuclear@0 485 // Removing multiple elements from the array.
nuclear@0 486 void RemoveMultipleAt(size_t index, size_t num)
nuclear@0 487 {
nuclear@0 488 OVR_ASSERT(index + num <= Data.Size);
nuclear@0 489 if (Data.Size == num)
nuclear@0 490 {
nuclear@0 491 Clear();
nuclear@0 492 }
nuclear@0 493 else
nuclear@0 494 {
nuclear@0 495 AllocatorType::DestructArray(Data.Data + index, num);
nuclear@0 496 AllocatorType::CopyArrayForward(
nuclear@0 497 Data.Data + index,
nuclear@0 498 Data.Data + index + num,
nuclear@0 499 Data.Size - num - index);
nuclear@0 500 Data.Size -= num;
nuclear@0 501 }
nuclear@0 502 }
nuclear@0 503
nuclear@0 504 // Removing an element from the array is an expensive operation!
nuclear@0 505 // It compacts only after removing the last element.
nuclear@0 506 // If order of elements in the array is not important then use
nuclear@0 507 // RemoveAtUnordered, that could be much faster than the regular
nuclear@0 508 // RemoveAt.
nuclear@0 509 void RemoveAt(size_t index)
nuclear@0 510 {
nuclear@0 511 OVR_ASSERT((Data.Data) && (index < Data.Size));
nuclear@0 512 if (Data.Size == 1)
nuclear@0 513 {
nuclear@0 514 Clear();
nuclear@0 515 }
nuclear@0 516 else
nuclear@0 517 {
nuclear@0 518 AllocatorType::Destruct(Data.Data + index);
nuclear@0 519 AllocatorType::CopyArrayForward(
nuclear@0 520 Data.Data + index,
nuclear@0 521 Data.Data + index + 1,
nuclear@0 522 Data.Size - 1 - index);
nuclear@0 523 --Data.Size;
nuclear@0 524 }
nuclear@0 525 }
nuclear@0 526
nuclear@0 527 // Removes an element from the array without respecting of original order of
nuclear@0 528 // elements for better performance. Do not use on array where order of elements
nuclear@0 529 // is important, otherwise use it instead of regular RemoveAt().
nuclear@0 530 void RemoveAtUnordered(size_t index)
nuclear@0 531 {
nuclear@0 532 OVR_ASSERT((Data.Data) && (index < Data.Size));
nuclear@0 533 if (Data.Size == 1)
nuclear@0 534 {
nuclear@0 535 Clear();
nuclear@0 536 }
nuclear@0 537 else
nuclear@0 538 {
nuclear@0 539 // copy the last element into the 'index' position
nuclear@0 540 // and decrement the size (instead of moving all elements
nuclear@0 541 // in [index + 1 .. size - 1] range).
nuclear@0 542 const size_t lastElemIndex = Data.Size - 1;
nuclear@0 543 if (index < lastElemIndex)
nuclear@0 544 {
nuclear@0 545 AllocatorType::Destruct(Data.Data + index);
nuclear@0 546 AllocatorType::Construct(Data.Data + index, Data.Data[lastElemIndex]);
nuclear@0 547 }
nuclear@0 548 AllocatorType::Destruct(Data.Data + lastElemIndex);
nuclear@0 549 --Data.Size;
nuclear@0 550 }
nuclear@0 551 }
nuclear@0 552
nuclear@0 553 // Insert the given object at the given index shifting all the elements up.
nuclear@0 554 void InsertAt(size_t index, const ValueType& val = ValueType())
nuclear@0 555 {
nuclear@0 556 OVR_ASSERT(index <= Data.Size);
nuclear@0 557
nuclear@0 558 Data.Resize(Data.Size + 1);
nuclear@0 559 if (index < Data.Size - 1)
nuclear@0 560 {
nuclear@0 561 AllocatorType::CopyArrayBackward(
nuclear@0 562 Data.Data + index + 1,
nuclear@0 563 Data.Data + index,
nuclear@0 564 Data.Size - 1 - index);
nuclear@0 565 }
nuclear@0 566 AllocatorType::Construct(Data.Data + index, val);
nuclear@0 567 }
nuclear@0 568
nuclear@0 569 // Insert the given object at the given index shifting all the elements up.
nuclear@0 570 void InsertMultipleAt(size_t index, size_t num, const ValueType& val = ValueType())
nuclear@0 571 {
nuclear@0 572 OVR_ASSERT(index <= Data.Size);
nuclear@0 573
nuclear@0 574 Data.Resize(Data.Size + num);
nuclear@0 575 if (index < Data.Size - num)
nuclear@0 576 {
nuclear@0 577 AllocatorType::CopyArrayBackward(
nuclear@0 578 Data.Data + index + num,
nuclear@0 579 Data.Data + index,
nuclear@0 580 Data.Size - num - index);
nuclear@0 581 }
nuclear@0 582 for (size_t i = 0; i < num; ++i)
nuclear@0 583 AllocatorType::Construct(Data.Data + index + i, val);
nuclear@0 584 }
nuclear@0 585
nuclear@0 586 // Append the given data to the array.
nuclear@0 587 void Append(const SelfType& other)
nuclear@0 588 {
nuclear@0 589 Append(other.Data.Data, other.GetSize());
nuclear@0 590 }
nuclear@0 591
nuclear@0 592 // Append the given data to the array.
nuclear@0 593 void Append(const ValueType other[], size_t count)
nuclear@0 594 {
nuclear@0 595 Data.Append(other, count);
nuclear@0 596 }
nuclear@0 597
nuclear@0 598 class Iterator
nuclear@0 599 {
nuclear@0 600 SelfType* pArray;
nuclear@0 601 intptr_t CurIndex;
nuclear@0 602
nuclear@0 603 public:
nuclear@0 604 Iterator() : pArray(0), CurIndex(-1) {}
nuclear@0 605 Iterator(SelfType* parr, intptr_t idx = 0) : pArray(parr), CurIndex(idx) {}
nuclear@0 606
nuclear@0 607 bool operator==(const Iterator& it) const { return pArray == it.pArray && CurIndex == it.CurIndex; }
nuclear@0 608 bool operator!=(const Iterator& it) const { return pArray != it.pArray || CurIndex != it.CurIndex; }
nuclear@0 609
nuclear@0 610 Iterator& operator++()
nuclear@0 611 {
nuclear@0 612 if (pArray)
nuclear@0 613 {
nuclear@0 614 if (CurIndex < (intptr_t)pArray->GetSize())
nuclear@0 615 ++CurIndex;
nuclear@0 616 }
nuclear@0 617 return *this;
nuclear@0 618 }
nuclear@0 619 Iterator operator++(int)
nuclear@0 620 {
nuclear@0 621 Iterator it(*this);
nuclear@0 622 operator++();
nuclear@0 623 return it;
nuclear@0 624 }
nuclear@0 625 Iterator& operator--()
nuclear@0 626 {
nuclear@0 627 if (pArray)
nuclear@0 628 {
nuclear@0 629 if (CurIndex >= 0)
nuclear@0 630 --CurIndex;
nuclear@0 631 }
nuclear@0 632 return *this;
nuclear@0 633 }
nuclear@0 634 Iterator operator--(int)
nuclear@0 635 {
nuclear@0 636 Iterator it(*this);
nuclear@0 637 operator--();
nuclear@0 638 return it;
nuclear@0 639 }
nuclear@0 640 Iterator operator+(int delta) const
nuclear@0 641 {
nuclear@0 642 return Iterator(pArray, CurIndex + delta);
nuclear@0 643 }
nuclear@0 644 Iterator operator-(int delta) const
nuclear@0 645 {
nuclear@0 646 return Iterator(pArray, CurIndex - delta);
nuclear@0 647 }
nuclear@0 648 intptr_t operator-(const Iterator& right) const
nuclear@0 649 {
nuclear@0 650 OVR_ASSERT(pArray == right.pArray);
nuclear@0 651 return CurIndex - right.CurIndex;
nuclear@0 652 }
nuclear@0 653 ValueType& operator*() const { OVR_ASSERT(pArray); return (*pArray)[CurIndex]; }
nuclear@0 654 ValueType* operator->() const { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
nuclear@0 655 ValueType* GetPtr() const { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
nuclear@0 656
nuclear@0 657 bool IsFinished() const { return !pArray || CurIndex < 0 || CurIndex >= (int)pArray->GetSize(); }
nuclear@0 658
nuclear@0 659 void Remove()
nuclear@0 660 {
nuclear@0 661 if (!IsFinished())
nuclear@0 662 pArray->RemoveAt(CurIndex);
nuclear@0 663 }
nuclear@0 664
nuclear@0 665 intptr_t GetIndex() const { return CurIndex; }
nuclear@0 666 };
nuclear@0 667
nuclear@0 668 Iterator Begin() { return Iterator(this); }
nuclear@0 669 Iterator End() { return Iterator(this, (intptr_t)GetSize()); }
nuclear@0 670 Iterator Last() { return Iterator(this, (intptr_t)GetSize() - 1); }
nuclear@0 671
nuclear@0 672 class ConstIterator
nuclear@0 673 {
nuclear@0 674 const SelfType* pArray;
nuclear@0 675 intptr_t CurIndex;
nuclear@0 676
nuclear@0 677 public:
nuclear@0 678 ConstIterator() : pArray(0), CurIndex(-1) {}
nuclear@0 679 ConstIterator(const SelfType* parr, intptr_t idx = 0) : pArray(parr), CurIndex(idx) {}
nuclear@0 680
nuclear@0 681 bool operator==(const ConstIterator& it) const { return pArray == it.pArray && CurIndex == it.CurIndex; }
nuclear@0 682 bool operator!=(const ConstIterator& it) const { return pArray != it.pArray || CurIndex != it.CurIndex; }
nuclear@0 683
nuclear@0 684 ConstIterator& operator++()
nuclear@0 685 {
nuclear@0 686 if (pArray)
nuclear@0 687 {
nuclear@0 688 if (CurIndex < (int)pArray->GetSize())
nuclear@0 689 ++CurIndex;
nuclear@0 690 }
nuclear@0 691 return *this;
nuclear@0 692 }
nuclear@0 693 ConstIterator operator++(int)
nuclear@0 694 {
nuclear@0 695 ConstIterator it(*this);
nuclear@0 696 operator++();
nuclear@0 697 return it;
nuclear@0 698 }
nuclear@0 699 ConstIterator& operator--()
nuclear@0 700 {
nuclear@0 701 if (pArray)
nuclear@0 702 {
nuclear@0 703 if (CurIndex >= 0)
nuclear@0 704 --CurIndex;
nuclear@0 705 }
nuclear@0 706 return *this;
nuclear@0 707 }
nuclear@0 708 ConstIterator operator--(int)
nuclear@0 709 {
nuclear@0 710 ConstIterator it(*this);
nuclear@0 711 operator--();
nuclear@0 712 return it;
nuclear@0 713 }
nuclear@0 714 ConstIterator operator+(int delta) const
nuclear@0 715 {
nuclear@0 716 return ConstIterator(pArray, CurIndex + delta);
nuclear@0 717 }
nuclear@0 718 ConstIterator operator-(int delta) const
nuclear@0 719 {
nuclear@0 720 return ConstIterator(pArray, CurIndex - delta);
nuclear@0 721 }
nuclear@0 722 intptr_t operator-(const ConstIterator& right) const
nuclear@0 723 {
nuclear@0 724 OVR_ASSERT(pArray == right.pArray);
nuclear@0 725 return CurIndex - right.CurIndex;
nuclear@0 726 }
nuclear@0 727 const ValueType& operator*() const { OVR_ASSERT(pArray); return (*pArray)[CurIndex]; }
nuclear@0 728 const ValueType* operator->() const { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
nuclear@0 729 const ValueType* GetPtr() const { OVR_ASSERT(pArray); return &(*pArray)[CurIndex]; }
nuclear@0 730
nuclear@0 731 bool IsFinished() const { return !pArray || CurIndex < 0 || CurIndex >= (int)pArray->GetSize(); }
nuclear@0 732
nuclear@0 733 intptr_t GetIndex() const { return CurIndex; }
nuclear@0 734 };
nuclear@0 735 ConstIterator Begin() const { return ConstIterator(this); }
nuclear@0 736 ConstIterator End() const { return ConstIterator(this, (intptr_t)GetSize()); }
nuclear@0 737 ConstIterator Last() const { return ConstIterator(this, (intptr_t)GetSize() - 1); }
nuclear@0 738
nuclear@0 739 protected:
nuclear@0 740 ArrayData Data;
nuclear@0 741 };
nuclear@0 742
nuclear@0 743
nuclear@0 744
nuclear@0 745 //-----------------------------------------------------------------------------------
nuclear@0 746 // ***** Array
nuclear@0 747 //
nuclear@0 748 // General purpose array for movable objects that require explicit
nuclear@0 749 // construction/destruction.
nuclear@0 750 template<class T, class SizePolicy=ArrayDefaultPolicy>
nuclear@0 751 class Array : public ArrayBase<ArrayData<T, ContainerAllocator<T>, SizePolicy> >
nuclear@0 752 {
nuclear@0 753 public:
nuclear@0 754 typedef T ValueType;
nuclear@0 755 typedef ContainerAllocator<T> AllocatorType;
nuclear@0 756 typedef SizePolicy SizePolicyType;
nuclear@0 757 typedef Array<T, SizePolicy> SelfType;
nuclear@0 758 typedef ArrayBase<ArrayData<T, ContainerAllocator<T>, SizePolicy> > BaseType;
nuclear@0 759
nuclear@0 760 Array() : BaseType() {}
nuclear@0 761 Array(size_t size) : BaseType(size) {}
nuclear@0 762 Array(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
nuclear@0 763 Array(const SelfType& a) : BaseType(a) {}
nuclear@0 764 const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
nuclear@0 765 };
nuclear@0 766
nuclear@0 767 // ***** ArrayPOD
nuclear@0 768 //
nuclear@0 769 // General purpose array for movable objects that DOES NOT require
nuclear@0 770 // construction/destruction. Constructors and destructors are not called!
nuclear@0 771 // Global heap is in use.
nuclear@0 772 template<class T, class SizePolicy=ArrayDefaultPolicy>
nuclear@0 773 class ArrayPOD : public ArrayBase<ArrayData<T, ContainerAllocator_POD<T>, SizePolicy> >
nuclear@0 774 {
nuclear@0 775 public:
nuclear@0 776 typedef T ValueType;
nuclear@0 777 typedef ContainerAllocator_POD<T> AllocatorType;
nuclear@0 778 typedef SizePolicy SizePolicyType;
nuclear@0 779 typedef ArrayPOD<T, SizePolicy> SelfType;
nuclear@0 780 typedef ArrayBase<ArrayData<T, ContainerAllocator_POD<T>, SizePolicy> > BaseType;
nuclear@0 781
nuclear@0 782 ArrayPOD() : BaseType() {}
nuclear@0 783 ArrayPOD(size_t size) : BaseType(size) {}
nuclear@0 784 ArrayPOD(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
nuclear@0 785 ArrayPOD(const SelfType& a) : BaseType(a) {}
nuclear@0 786 const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
nuclear@0 787 };
nuclear@0 788
nuclear@0 789
nuclear@0 790 // ***** ArrayCPP
nuclear@0 791 //
nuclear@0 792 // General purpose, fully C++ compliant array. Can be used with non-movable data.
nuclear@0 793 // Global heap is in use.
nuclear@0 794 template<class T, class SizePolicy=ArrayDefaultPolicy>
nuclear@0 795 class ArrayCPP : public ArrayBase<ArrayData<T, ContainerAllocator_CPP<T>, SizePolicy> >
nuclear@0 796 {
nuclear@0 797 public:
nuclear@0 798 typedef T ValueType;
nuclear@0 799 typedef ContainerAllocator_CPP<T> AllocatorType;
nuclear@0 800 typedef SizePolicy SizePolicyType;
nuclear@0 801 typedef ArrayCPP<T, SizePolicy> SelfType;
nuclear@0 802 typedef ArrayBase<ArrayData<T, ContainerAllocator_CPP<T>, SizePolicy> > BaseType;
nuclear@0 803
nuclear@0 804 ArrayCPP() : BaseType() {}
nuclear@0 805 ArrayCPP(size_t size) : BaseType(size) {}
nuclear@0 806 ArrayCPP(const SizePolicyType& p) : BaseType() { SetSizePolicy(p); }
nuclear@0 807 ArrayCPP(const SelfType& a) : BaseType(a) {}
nuclear@0 808 const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
nuclear@0 809 };
nuclear@0 810
nuclear@0 811
nuclear@0 812 // ***** ArrayCC
nuclear@0 813 //
nuclear@0 814 // A modification of the array that uses the given default value to
nuclear@0 815 // construct the elements. The constructors and destructors are
nuclear@0 816 // properly called, the objects must be movable.
nuclear@0 817
nuclear@0 818 template<class T, class SizePolicy=ArrayDefaultPolicy>
nuclear@0 819 class ArrayCC : public ArrayBase<ArrayDataCC<T, ContainerAllocator<T>, SizePolicy> >
nuclear@0 820 {
nuclear@0 821 public:
nuclear@0 822 typedef T ValueType;
nuclear@0 823 typedef ContainerAllocator<T> AllocatorType;
nuclear@0 824 typedef SizePolicy SizePolicyType;
nuclear@0 825 typedef ArrayCC<T, SizePolicy> SelfType;
nuclear@0 826 typedef ArrayBase<ArrayDataCC<T, ContainerAllocator<T>, SizePolicy> > BaseType;
nuclear@0 827
nuclear@0 828 ArrayCC(const ValueType& defval) : BaseType(defval) {}
nuclear@0 829 ArrayCC(const ValueType& defval, size_t size) : BaseType(defval, size) {}
nuclear@0 830 ArrayCC(const ValueType& defval, const SizePolicyType& p) : BaseType(defval) { SetSizePolicy(p); }
nuclear@0 831 ArrayCC(const SelfType& a) : BaseType(a) {}
nuclear@0 832 const SelfType& operator=(const SelfType& a) { BaseType::operator=(a); return *this; }
nuclear@0 833 };
nuclear@0 834
nuclear@0 835 } // OVR
nuclear@0 836
nuclear@0 837 #endif