1 // The MIT License (MIT) 2 // 3 // Copyright (c) 2015 Sergey Makeev, Vadim Slyusarev 4 // 5 // Permission is hereby granted, free of charge, to any person obtaining a copy 6 // of this software and associated documentation files (the "Software"), to deal 7 // in the Software without restriction, including without limitation the rights 8 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 9 // copies of the Software, and to permit persons to whom the Software is 10 // furnished to do so, subject to the following conditions: 11 // 12 // The above copyright notice and this permission notice shall be included in 13 // all copies or substantial portions of the Software. 14 // 15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 18 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 20 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 21 // THE SOFTWARE. 22 23 #pragma once 24 25 #ifndef __MT_STACK__ 26 #define __MT_STACK__ 27 28 #include <array> 29 #include <limits> 30 31 namespace MT 32 { 33 static const int32 invalidStackId = 0; 34 static const int32 invalidStorageId = 0; 35 36 37 // 38 // Scope descriptor 39 // 40 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 41 class ScopeDesc 42 { 43 protected: 44 45 //descriptor name 46 const char* name; 47 48 //descriptor declaration file/line 49 const char* file; 50 int32 line; 51 52 public: 53 54 ScopeDesc(const char* srcFile, int32 srcLine, const char* scopeName) 55 : name(scopeName) 56 , file(srcFile) 57 , line(srcLine) 58 { 59 } 60 61 const char* GetSourceFile() const 62 { 63 return file; 64 } 65 66 int32 GetSourceLine() const 67 { 68 return line; 69 } 70 71 const char* GetName() const 72 { 73 return name; 74 } 75 76 77 }; 78 79 80 // 81 // Scope stack entry 82 // 83 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 84 class ScopeStackEntry 85 { 86 int32 parentIndex; 87 int32 descIndex; 88 89 public: 90 91 ScopeStackEntry(int32 _parentIndex, int32 _descIndex) 92 : parentIndex(_parentIndex) 93 , descIndex(_descIndex) 94 { 95 } 96 97 #ifdef _DEBUG 98 ~ScopeStackEntry() 99 { 100 parentIndex = std::numeric_limits<int32>::lowest(); 101 descIndex = std::numeric_limits<int32>::lowest(); 102 } 103 #endif 104 105 int32 GetParentId() const 106 { 107 return parentIndex; 108 } 109 110 int32 GetDescriptionId() const 111 { 112 return descIndex; 113 } 114 115 116 }; 117 118 119 // 120 // Persistent scope descriptor storage 121 // 122 // persistent storage used to store scope descriptors 123 // descriptors lifetime is equal to the storage lifetime 124 // 125 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 126 template<typename T, uint32 capacity> 127 class PersistentScopeDescriptorStorage 128 { 129 MT::AtomicInt32 top; 130 byte rawMemory[ capacity * sizeof(T) ]; 131 132 T* AllocObject(int32 & id) 133 { 134 //new element index 135 int32 index = top.IncFetch() - 1; 136 MT_VERIFY(index < (int32)capacity, "Area allocator is full. Can't allocate more memory.", return nullptr); 137 138 //get memory for object 139 T* pObject = (T*)&rawMemory[index * sizeof(T)]; 140 141 id = (index + 1); 142 143 return pObject; 144 } 145 146 147 public: 148 149 PersistentScopeDescriptorStorage() 150 { 151 static_assert(std::is_base_of<MT::ScopeDesc, T>::value, "Type must be derived from MT::ScopeDesc"); 152 top.Store(0); 153 } 154 155 ~PersistentScopeDescriptorStorage() 156 { 157 int32 count = top.Store(0); 158 for (int32 i = 0; i < count; i++) 159 { 160 T* pObject = (T*)&rawMemory[i * sizeof(T)]; 161 MT_UNUSED(pObject); 162 pObject->~T(); 163 } 164 } 165 166 int32 Alloc(const char* srcFile, int32 srcLine, const char* scopeName) 167 { 168 int32 id; 169 T* pObject = AllocObject(id); 170 if (pObject == nullptr) 171 return invalidStorageId; 172 173 //placement ctor 174 new(pObject) T(srcFile, srcLine, scopeName); 175 176 return id; 177 } 178 179 template<typename T1> 180 int32 Alloc(const char* srcFile, int32 srcLine, const char* scopeName, const T1 & p1) 181 { 182 int32 id; 183 T* pObject = AllocObject(id); 184 if (pObject == nullptr) 185 return invalidStorageId; 186 187 //placement ctor 188 new(pObject) T(srcFile, srcLine, scopeName, p1); 189 return id; 190 } 191 192 template<typename T1, typename T2> 193 int32 Alloc(const char* srcFile, int32 srcLine, const char* scopeName, const T1 & p1, const T1 & p2) 194 { 195 int32 id; 196 T* pObject = AllocObject(id); 197 if (pObject == nullptr) 198 return invalidStorageId; 199 200 //placement ctor 201 new(pObject) T(srcFile, srcLine, scopeName, p1, p2); 202 return id; 203 } 204 205 template<typename T1, typename T2> 206 int32 Alloc(const char* srcFile, int32 srcLine, const char* scopeName, const T1 & p1, const T1 & p2, const T1 & p3) 207 { 208 int32 id; 209 T* pObject = AllocObject(id); 210 if (pObject == nullptr) 211 return invalidStorageId; 212 213 //placement ctor 214 new(pObject) T(srcFile, srcLine, scopeName, p1, p2, p3); 215 return id; 216 } 217 218 219 220 221 T* Get(int32 id) 222 { 223 MT_VERIFY(id > invalidStorageId, "Invalid ID", return nullptr ); 224 MT_VERIFY(id <= top.Load(), "Invalid ID", return nullptr ); 225 226 int32 index = ( id - 1); 227 T* pObject = (T*)&rawMemory[index * sizeof(T)]; 228 229 return pObject; 230 } 231 232 }; 233 234 235 // 236 // Weak scope stack 237 // 238 // Weak stack, which means that any data from the stack become invalid after stack entry is popped from stack 239 // Weak stack uses a small amount of memory, but in the case of deferred use the stack entires you must copy this entries to extend lifetime. 240 // 241 // Well suited as asset/resource names stack. 242 // 243 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 244 template<typename T, uint32 capacity> 245 class WeakScopeStack 246 { 247 volatile int32 top; 248 byte rawMemory[ capacity * sizeof(T) ]; 249 250 T* IndexToObject(int32 index) 251 { 252 T* pObject = (T*)&rawMemory[ index * sizeof(T) ]; 253 return pObject; 254 } 255 256 257 T* AllocObject() 258 { 259 int32 index = top; 260 MT_VERIFY(index < (int32)capacity, "Stack allocator overflow. Can't allocate more memory.", return nullptr); 261 top++; 262 T* pObject = IndexToObject(index); 263 return pObject; 264 } 265 266 public: 267 268 WeakScopeStack() 269 { 270 static_assert(std::is_base_of<MT::ScopeStackEntry, T>::value, "Type must be derived from MT::ScopeStackEntry"); 271 top = invalidStackId; 272 } 273 274 ~WeakScopeStack() 275 { 276 for(int32 i = 0; i < top; i++) 277 { 278 T* pObject = IndexToObject(i); 279 MT_UNUSED(pObject); 280 pObject->~T(); 281 } 282 top = 0; 283 } 284 285 286 T* Get(int32 id) 287 { 288 MT_VERIFY(id > invalidStackId, "Invalid id", return nullptr); 289 int32 index = (id - 1); 290 return IndexToObject(index); 291 } 292 293 int32 Top() 294 { 295 int32 id = top; 296 return id; 297 } 298 299 void Pop() 300 { 301 top--; 302 int32 index = top; 303 MT_ASSERT(index >= 0, "Stack already empty. Invalid call."); 304 T* pObject = IndexToObject(index); 305 MT_UNUSED(pObject); 306 pObject->~T(); 307 } 308 309 T* Push() 310 { 311 T* pObject = AllocObject(); 312 new(pObject) T(); 313 return pObject; 314 } 315 316 template<typename T1> 317 T* Push(const T1 & p1) 318 { 319 T* pObject = AllocObject(); 320 new(pObject) T(p1); 321 return pObject; 322 } 323 324 template<typename T1, typename T2> 325 T* Push(const T1 & p1, const T2 & p2) 326 { 327 T* pObject = AllocObject(); 328 new(pObject) T(p1, p2); 329 return pObject; 330 } 331 332 template<typename T1, typename T2, typename T3> 333 T* Push(const T1 & p1, const T2 & p2, const T3 & p3) 334 { 335 T* pObject = AllocObject(); 336 new(pObject) T(p1, p2, p3); 337 return pObject; 338 } 339 340 template<typename T1, typename T2, typename T3, typename T4> 341 T* Push(const T1 & p1, const T2 & p2, const T3 & p3, const T4 & p4) 342 { 343 T* pObject = AllocObject(); 344 new(pObject) T(p1, p2, p3, p4); 345 return pObject; 346 } 347 }; 348 349 350 // 351 // Strong scope stack 352 // 353 // Strong stack, which means that any data from the stack is always valid, until you call Reset(); 354 // Strong stack uses a lot of memory, but in the case of deferred use of stack entires you can store single pointer to current stack entry. 355 // 356 // Well suited as CPU profiler timings stack. 357 // 358 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 359 template<typename T, uint32 capacity> 360 class StrongScopeStack 361 { 362 volatile int32 count; 363 364 volatile int32 top; 365 366 //max stack deep 367 std::array<int32, 256> stackId; 368 369 byte rawMemory[ capacity * sizeof(T) ]; 370 371 T* IndexToObject(int32 index) 372 { 373 T* pObject = (T*)&rawMemory[ index * sizeof(T) ]; 374 return pObject; 375 } 376 377 378 T* AllocObject() 379 { 380 int32 stackIndex = top; 381 MT_VERIFY(stackIndex < (int32)stackId.size(), "Stack is too deep.", return nullptr); 382 top++; 383 384 int32 index = count; 385 MT_VERIFY(index < (int32)capacity, "Stack allocator overflow. Can't allocate more memory.", return nullptr); 386 count++; 387 T* pObject = IndexToObject(index); 388 389 stackId[stackIndex] = (index + 1); 390 391 return pObject; 392 } 393 394 395 public: 396 397 StrongScopeStack() 398 { 399 static_assert(std::is_base_of<MT::ScopeStackEntry, T>::value, "Type must be derived from MT::ScopeStackEntry"); 400 top = invalidStackId; 401 count = 0; 402 } 403 404 ~StrongScopeStack() 405 { 406 Reset(); 407 } 408 409 T* Get(int32 id) 410 { 411 MT_VERIFY(id > invalidStackId, "Invalid id", return nullptr); 412 int32 index = (id - 1); 413 return IndexToObject(index); 414 } 415 416 int32 Top() 417 { 418 if (top == invalidStackId) 419 { 420 return invalidStackId; 421 } 422 423 return stackId[top - 1]; 424 } 425 426 void Pop() 427 { 428 top--; 429 int32 index = top; 430 MT_ASSERT(index >= 0, "Stack already empty. Invalid call."); 431 432 stackId[index] = 0; 433 } 434 435 436 T* Push() 437 { 438 T* pObject = AllocObject(); 439 new(pObject) T(); 440 return pObject; 441 } 442 443 template<typename T1, typename T2> 444 T* Push(T1 p1, T2 p2) 445 { 446 T* pObject = AllocObject(); 447 new(pObject) T(p1, p2); 448 return pObject; 449 } 450 451 template<typename T1, typename T2, typename T3> 452 T* Push(T1 p1, T2 p2, T3 p3) 453 { 454 T* pObject = AllocObject(); 455 new(pObject) T(p1, p2, p3); 456 return pObject; 457 } 458 459 template<typename T1, typename T2, typename T3, typename T4> 460 T* Push(T1 p1, T2 p2, T3 p3, T4 p4) 461 { 462 T* pObject = AllocObject(); 463 new(pObject) T(p1, p2, p3, p4); 464 return pObject; 465 } 466 467 468 void Reset() 469 { 470 for(int32 i = 0; i < count; i++) 471 { 472 T* pObject = IndexToObject(i); 473 MT_UNUSED(pObject); 474 pObject->~T(); 475 } 476 477 #ifdef _DEBUG 478 int32 stackIdCount = (int32)stackId.size(); 479 for(int32 i = 0; i < stackIdCount; i++) 480 { 481 stackId[i] = std::numeric_limits<int32>::lowest(); 482 } 483 #endif 484 count = 0; 485 top = invalidStackId; 486 } 487 488 }; 489 490 } //MT namespace 491 492 493 #define SCOPE_CONCAT_IMPL(x, y) x##y 494 #define SCOPE_CONCAT(x, y) SCOPE_CONCAT_IMPL(x, y) 495 496 #define DECLARE_SCOPE_DESCRIPTOR_IMPL_PRE( file, line, name, storagePointer, resultID ) \ 497 const int32 scope_notInitialized = 0; \ 498 const int32 scope_notYetInitialized = -1; \ 499 \ 500 static MT::AtomicInt32Base SCOPE_CONCAT(scope_descriptorIndex_, line) = { scope_notInitialized }; \ 501 static_assert(std::is_pod<MT::AtomicInt32Base>::value == true, "AtomicInt32Base type should be POD, to be placed in bss/data section"); \ 502 \ 503 int32 SCOPE_CONCAT(scope_descId_, line) = scope_notInitialized; \ 504 \ 505 int32 SCOPE_CONCAT(scope_state_, line) = SCOPE_CONCAT(scope_descriptorIndex_, line).CompareAndSwap(scope_notInitialized, scope_notYetInitialized); \ 506 switch(SCOPE_CONCAT(scope_state_, line)) \ 507 { \ 508 /* first time here, need to allocate descriptor*/ \ 509 case scope_notInitialized: \ 510 { \ 511 MT_ASSERT( storagePointer != nullptr, "Scopes storage pointer was not initialized!"); \ 512 513 514 515 #define DECLARE_SCOPE_DESCRIPTOR_IMPL_POST( file, line, name, storagePointer, resultID ) \ 516 SCOPE_CONCAT(scope_descriptorIndex_, line).Store( SCOPE_CONCAT(scope_descId_, line) ); \ 517 break; \ 518 } \ 519 \ 520 /* allocation in progress */ \ 521 /* wait until the allocation is finished */ \ 522 case scope_notYetInitialized: \ 523 { \ 524 for(;;) \ 525 { \ 526 SCOPE_CONCAT(scope_descId_, line) = SCOPE_CONCAT(scope_descriptorIndex_, line).Load(); \ 527 if (SCOPE_CONCAT(scope_descId_, line) != scope_notYetInitialized) \ 528 { \ 529 break; \ 530 } \ 531 MT::YieldCpu(); \ 532 } \ 533 break; \ 534 } \ 535 /* description already allocated */ \ 536 default: \ 537 { \ 538 SCOPE_CONCAT(scope_descId_, line) = SCOPE_CONCAT(scope_state_, line); \ 539 break; \ 540 } \ 541 } \ 542 resultID = SCOPE_CONCAT(scope_descId_, line); 543 544 545 546 547 #define DECLARE_SCOPE_DESCRIPTOR_IMPL( file, line, name, storagePointer, resultID ) \ 548 DECLARE_SCOPE_DESCRIPTOR_IMPL_PRE(file, line, name, storagePointer, resultID); \ 549 SCOPE_CONCAT(scope_descId_, line) = storagePointer -> Alloc(file, line, name); \ 550 DECLARE_SCOPE_DESCRIPTOR_IMPL_POST(file, line, name, storagePointer, resultID); \ 551 552 553 #define DECLARE_SCOPE_DESCRIPTOR_IMPL1( file, line, name, storagePointer, resultID, param1) \ 554 DECLARE_SCOPE_DESCRIPTOR_IMPL_PRE(file, line, name, storagePointer, resultID); \ 555 SCOPE_CONCAT(scope_descId_, line) = storagePointer -> Alloc(file, line, name, param1); \ 556 DECLARE_SCOPE_DESCRIPTOR_IMPL_POST(file, line, name, storagePointer, resultID); \ 557 558 #define DECLARE_SCOPE_DESCRIPTOR_IMPL2( file, line, name, storagePointer, resultID, param1, param2) \ 559 DECLARE_SCOPE_DESCRIPTOR_IMPL_PRE(file, line, name, storagePointer, resultID); \ 560 SCOPE_CONCAT(scope_descId_, line) = storagePointer -> Alloc(file, line, name, param1, param2); \ 561 DECLARE_SCOPE_DESCRIPTOR_IMPL_POST(file, line, name, storagePointer, resultID); \ 562 563 564 565 // declare scope descriptor for current scope. 566 #define DECLARE_SCOPE_DESCRIPTOR(name, storagePointer, resultID) DECLARE_SCOPE_DESCRIPTOR_IMPL(__FILE__, __LINE__, name, storagePointer, resultID) 567 568 #define DECLARE_SCOPE_DESCRIPTOR1(name, storagePointer, resultID, param1) DECLARE_SCOPE_DESCRIPTOR_IMPL1(__FILE__, __LINE__, name, storagePointer, resultID, param1) 569 570 #define DECLARE_SCOPE_DESCRIPTOR2(name, storagePointer, resultID, param1, param2) DECLARE_SCOPE_DESCRIPTOR_IMPL2(__FILE__, __LINE__, name, storagePointer, resultID, param1, param2) 571 572 // push new stack entry to stack 573 #define SCOPE_STACK_PUSH(scopeDescriptorId, stackPointer) \ 574 MT_ASSERT(stackPointer != nullptr, "Stack pointer is not initialized for current thread."); \ 575 int32 scope_stackParentId = stackPointer -> Top(); \ 576 MT_ASSERT(scope_stackParentId >= 0, "Invalid parent ID"); \ 577 stackPointer -> Push(scope_stackParentId, scopeDescriptorId); \ 578 579 580 // push new stack entry to stack 581 #define SCOPE_STACK_PUSH1(scopeDescriptorId, param1, stackPointer) \ 582 MT_ASSERT(stackPointer != nullptr, "Stack pointer is not initialized for current thread."); \ 583 int32 scope_stackParentId = stackPointer -> Top(); \ 584 MT_ASSERT(scope_stackParentId >= 0, "Invalid parent ID"); \ 585 stackPointer -> Push(scope_stackParentId, scopeDescriptorId, param1); \ 586 587 // push new stack entry to stack 588 #define SCOPE_STACK_PUSH2(scopeDescriptorId, param1, param2, stackPointer) \ 589 MT_ASSERT(stackPointer != nullptr, "Stack pointer is not initialized for current thread."); \ 590 int32 scope_stackParentId = stackPointer -> Top(); \ 591 MT_ASSERT(scope_stackParentId >= 0, "Invalid parent ID"); \ 592 stackPointer -> Push(scope_stackParentId, scopeDescriptorId, param1, param2); \ 593 594 595 // pop from the stack 596 #define SCOPE_STACK_POP(stackPointer) \ 597 MT_ASSERT(stackPointer != nullptr, "Stack pointer is not initialized for current thread."); \ 598 stackPointer -> Pop(); \ 599 600 // get top of the stack 601 #define SCOPE_STACK_TOP(stackPointer) \ 602 stackPointer -> Get( stackPointer -> Top() ) 603 604 605 #define SCOPE_STACK_GET_PARENT(stackEntry, stackPointer) \ 606 (stackEntry -> GetParentId() == MT::invalidStackId) ? nullptr : stackPointer -> Get( stackEntry -> GetParentId() ) 607 608 609 610 611 #endif