1 /* 2 * ListStorage.h 3 * Apto 4 * 5 * Created by David on 3/8/11. 6 * Copyright 2010-2011 David Michael Bryson. All rights reserved. 7 * http://programerror.com/software/apto 8 * 9 * Redistribution and use in source and binary forms, with or without modification, are permitted provided that the 10 * following conditions are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the 13 * following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the 15 * following disclaimer in the documentation and/or other materials provided with the distribution. 16 * 3. Neither the name of David Michael Bryson, nor the names of contributors may be used to endorse or promote 17 * products derived from this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY DAVID MICHAEL BRYSON AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, 20 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 21 * DISCLAIMED. IN NO EVENT SHALL DAVID MICHAEL BRYSON OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 22 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 23 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 24 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE 25 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 * 27 * Authors: David M. Bryson <david@programerror.com> 28 * 29 */ 30 31 #ifndef AptoCoreListStorage_h 32 #define AptoCoreListStorage_h 33 34 #include "apto/core/Array.h" 35 #include "apto/core/Definitions.h" 36 #include "apto/platform/Platform.h" 37 38 #include <cassert> 39 40 41 namespace Apto { 42 43 // List Storage Policies 44 // -------------------------------------------------------------------------------------------------------------- 45 46 template <class T> class DL 47 { 48 public: 49 class EntryHandle; 50 class Iterator; 51 class ConstIterator; 52 53 private: 54 class Node 55 { 56 public: 57 T data; 58 EntryHandle* handle; 59 Node* next; 60 Node* prev; 61 }; 62 63 Node m_root; 64 int m_size; 65 DL(const DL &)66 DL(const DL&) { ; } 67 68 protected: DL()69 DL() : m_size(0) 70 { 71 m_root.next = &m_root; 72 m_root.prev = &m_root; 73 } 74 ~DL()75 ~DL() 76 { 77 // Clear handles and delete nodes 78 Node* cur = &m_root; 79 while (cur->next != &m_root) { 80 Node* next = cur->next; 81 if (cur != &m_root) delete cur; 82 if (next->handle) next->handle->m_node = NULL; 83 cur = next; 84 } 85 } 86 87 DL& operator=(const DL& rhs) 88 { 89 if (this == &rhs) return *this; 90 Clear(); 91 ConstIterator it = rhs.Begin(); 92 while (it.Next()) PushRear(*it.Get()); 93 return *this; 94 } 95 96 GetSize()97 inline int GetSize() const { return m_size; } 98 Clear()99 inline void Clear() 100 { 101 // Clear handles and delete nodes 102 Node* cur = &m_root; 103 while (cur->next != &m_root) { 104 Node* next = cur->next; 105 if (cur != &m_root) delete cur; 106 if (next->handle) next->handle->m_node = NULL; 107 cur = next; 108 } 109 110 m_root.next = &m_root; 111 m_root.prev = &m_root; 112 m_size = 0; 113 } 114 GetFirst()115 inline T& GetFirst() { return m_root.next->data; } GetFirst()116 inline const T& GetFirst() const { return m_root.next->data; } GetLast()117 inline T& GetLast() { return m_root.prev->data; } GetLast()118 inline const T& GetLast() const { return m_root.prev->data; } 119 Pop()120 inline T Pop() { return removeNode(m_root.next); } PopRear()121 inline T PopRear() { return removeNode(m_root.prev); } PopPos(int pos)122 inline T PopPos(int pos) 123 { 124 if (pos >= m_size) return NULL; 125 Node* test_node = m_root.next; 126 for (int i = 0; i < pos; i++) test_node = test_node->next; 127 return removeNode(test_node); 128 } 129 130 131 void Push(const T& val, EntryHandle** handle = NULL) 132 { 133 if (handle) delete *handle; 134 Node* node = new Node; 135 node->data = val; 136 if (handle) { 137 *handle = node->handle = new EntryHandle(this, node); 138 } else { 139 node->handle = NULL; 140 } 141 node->next = m_root.next; 142 node->prev = &m_root; 143 m_root.next->prev = node; 144 m_root.next = node; 145 m_size++; 146 } 147 148 void PushRear(const T& val, EntryHandle** handle = NULL) 149 { 150 if (handle) delete *handle; 151 Node* node = new Node; 152 node->data = val; 153 if (handle) { 154 *handle = node->handle = new EntryHandle(this, node); 155 } else { 156 node->handle = NULL; 157 } 158 node->next = &m_root; 159 node->prev = m_root.prev; 160 m_root.prev->next = node; 161 m_root.prev = node; 162 m_size++; 163 } 164 Remove(const T & value)165 bool Remove(const T& value) 166 { 167 for (Node* cur = &m_root; cur->next != &m_root; cur = cur->next) { 168 if (cur->data == value) { 169 removeNode(cur); 170 return true; 171 } 172 } 173 return false; 174 } 175 Begin()176 Iterator Begin() { return Iterator(this); } Begin()177 ConstIterator Begin() const { return ConstIterator(this); } 178 179 180 private: removeNode(Node * out_node)181 T removeNode(Node* out_node) 182 { 183 // Make sure we're not trying to delete the root node! 184 assert(out_node != &m_root); 185 186 // Save the data and patch up the linked list. 187 T out_data = out_node->data; 188 if (out_node->handle) out_node->handle->m_node = NULL; 189 out_node->prev->next = out_node->next; 190 out_node->next->prev = out_node->prev; 191 delete out_node; 192 193 m_size--; 194 195 return out_data; 196 } 197 198 public: 199 class Iterator 200 { 201 friend class DL<T>; 202 private: 203 DL<T>* m_list; 204 Node* m_cur; 205 206 Iterator(); // @not_implemented 207 Iterator(DL<T> * list)208 Iterator(DL<T>* list) : m_list(list), m_cur(&list->m_root) { ; } 209 210 public: Get()211 inline T* Get() { 212 if (m_cur && m_cur != &m_list->m_root) return &m_cur->data; 213 return NULL; 214 } 215 Next()216 inline T* Next() { 217 if (m_cur) { 218 m_cur = m_cur->next; 219 if (m_cur == &m_list->m_root) { 220 m_cur = NULL; 221 return NULL; 222 } else { 223 return &m_cur->data; 224 } 225 } 226 return NULL; 227 } 228 }; 229 230 class ConstIterator 231 { 232 friend class DL<T>; 233 private: 234 const DL<T>* m_list; 235 const Node* m_cur; 236 237 ConstIterator(); // @not_implemented 238 ConstIterator(const DL<T> * list)239 ConstIterator(const DL<T>* list) : m_list(list), m_cur(&list->m_root) { ; } 240 241 public: Get()242 inline const T* Get() { 243 if (m_cur && m_cur != &m_list->m_root) return &m_cur->data; 244 return NULL; 245 } 246 Next()247 inline const T* Next() { 248 if (m_cur) { 249 m_cur = m_cur->next; 250 if (m_cur == &m_list->m_root) { 251 m_cur = NULL; 252 return NULL; 253 } else { 254 return &m_cur->data; 255 } 256 } 257 return NULL; 258 } 259 }; 260 261 262 class EntryHandle 263 { 264 friend class DL<T>; 265 private: 266 DL<T>* m_list; 267 Node* m_node; 268 269 EntryHandle(); // @not_implemented 270 EntryHandle(const EntryHandle&); // @not_implemented 271 EntryHandle& operator=(const EntryHandle&); // @not_implemented 272 EntryHandle(DL<T> * list,Node * node)273 EntryHandle(DL<T>* list, Node* node) : m_list(list), m_node(node) { ; } 274 275 public: ~EntryHandle()276 ~EntryHandle() { if (m_node) m_node->handle = NULL; } IsValid()277 bool IsValid() const { return (m_node); } Remove()278 void Remove() 279 { 280 if (!m_node) return; 281 m_list->removeNode(m_node); 282 m_node = NULL; 283 } 284 }; 285 286 }; 287 288 289 template <class T> class BufferedDL 290 { 291 public: 292 class EntryHandle; 293 class Iterator; 294 class ConstIterator; 295 296 private: 297 static const int BUFFER_SIZE = 64; 298 299 typedef union { 300 unsigned int index; 301 struct { 302 #if APTO_PLATFORM_LITTLE_ENDIAN 303 unsigned int offset:6; 304 unsigned int num:26; 305 #else 306 unsigned int num:26; 307 unsigned int offset:6; 308 #endif 309 } buffer; 310 } ListIndex; 311 312 class Node 313 { 314 public: 315 T data; 316 EntryHandle* handle; 317 Node* next; 318 Node* prev; 319 }; 320 321 class Buffer 322 { 323 private: 324 Node* m_nodes; 325 326 public: Buffer()327 Buffer() : m_nodes(new Node[BUFFER_SIZE]) { ; } ~Buffer()328 ~Buffer() { delete [] m_nodes; } 329 330 Node& operator[](int idx) { return m_nodes[idx]; } 331 const Node& operator[](int idx) const { return m_nodes[idx]; } 332 }; 333 334 335 Array<Buffer, ManagedPointer> m_bufs; 336 ListIndex m_next; 337 Node m_root; 338 unsigned int m_size; 339 BufferedDL(const BufferedDL &)340 BufferedDL(const BufferedDL&) { ; } 341 342 protected: BufferedDL()343 BufferedDL() : m_size(0) { Clear(); } ~BufferedDL()344 ~BufferedDL() 345 { 346 // Clear handles 347 ListIndex i; 348 for (i.index = 0; i.index < m_size; i.index++) { 349 if (m_bufs[i.buffer.num][i.buffer.offset].handle) { 350 m_bufs[i.buffer.num][i.buffer.offset].handle->m_node = NULL; 351 } 352 } 353 } 354 355 BufferedDL& operator=(const BufferedDL& rhs) 356 { 357 if (this == &rhs) return *this; 358 Clear(); 359 ConstIterator it = rhs.Begin(); 360 while (it.Next()) PushRear(*it.Get()); 361 return *this; 362 } 363 364 GetSize()365 inline int GetSize() const { return m_size; } 366 Clear()367 inline void Clear() 368 { 369 // Clear handles 370 ListIndex i; 371 for (i.index = 0; i.index < m_size; i.index++) { 372 if (m_bufs[i.buffer.num][i.buffer.offset].handle) { 373 m_bufs[i.buffer.num][i.buffer.offset].handle->m_node = NULL; 374 } 375 } 376 377 m_bufs.Resize(1); 378 m_next.index = 0; 379 m_root.next = &m_root; 380 m_root.prev = &m_root; 381 m_size = 0; 382 } 383 GetFirst()384 inline T& GetFirst() { return m_root.next->data; } GetFirst()385 inline const T& GetFirst() const { return m_root.next->data; } GetLast()386 inline T& GetLast() { return m_root.prev->data; } GetLast()387 inline const T& GetLast() const { return m_root.prev->data; } 388 Pop()389 inline T Pop() { return removeNode(m_root.next); } PopRear()390 inline T PopRear() { return removeNode(m_root.prev); } PopPos(int pos)391 inline T PopPos(int pos) 392 { 393 if (pos >= m_size) return NULL; 394 Node* test_node = m_root.next; 395 for (int i = 0; i < pos; i++) test_node = test_node->next; 396 return removeNode(test_node); 397 } 398 399 400 void Push(const T& val, EntryHandle** handle = NULL) 401 { 402 if (handle) delete *handle; 403 Node& node = m_bufs[m_next.buffer.num][m_next.buffer.offset]; 404 node.data = val; 405 if (handle) { 406 node.handle = new EntryHandle(this, &m_bufs[m_next.buffer.num][m_next.buffer.offset]); 407 *handle = node.handle; 408 } else { 409 node.handle = NULL; 410 } 411 node.next = m_root.next; 412 node.prev = &m_root; 413 m_root.next->prev = &node; 414 m_root.next = &node; 415 incSize(); 416 } 417 418 void PushRear(const T& val, EntryHandle** handle = NULL) 419 { 420 if (handle) delete *handle; 421 Node& node = m_bufs[m_next.buffer.num][m_next.buffer.offset]; 422 node.data = val; 423 if (handle) { 424 node.handle = new EntryHandle(this, &m_bufs[m_next.buffer.num][m_next.buffer.offset]); 425 *handle = node.handle; 426 } else { 427 node.handle = NULL; 428 } 429 node.next = &m_root; 430 node.prev = m_root.prev; 431 m_root.prev->next = &node; 432 m_root.prev = &node; 433 incSize(); 434 } 435 Remove(const T & value)436 bool Remove(const T& value) 437 { 438 ListIndex i; 439 for (i.index = 0; i.index < m_size; i.index++) { 440 if (m_bufs[i.buffer.num][i.buffer.offset].data == value) { 441 removeNode(&m_bufs[i.buffer.num][i.buffer.offset]); 442 return true; 443 } 444 } 445 return false; 446 } 447 Begin()448 Iterator Begin() { return Iterator(this); } Begin()449 ConstIterator Begin() const { return ConstIterator(this); } 450 451 452 private: removeNode(Node * out_node)453 T removeNode(Node* out_node) 454 { 455 // Make sure we're not trying to delete the root node! 456 assert(out_node != &m_root); 457 458 // Save the data and patch up the linked list. 459 T out_data = out_node->data; 460 if (out_node->handle) out_node->handle->m_node = NULL; 461 out_node->prev->next = out_node->next; 462 out_node->next->prev = out_node->prev; 463 464 // Clean up now unused data with default (should, for example, force SmartPtr clean up) 465 out_node->data = T(); 466 467 m_next.index--; 468 Node* next_node = &m_bufs[m_next.buffer.num][m_next.buffer.offset]; 469 if (next_node != out_node) { 470 *out_node = *next_node; 471 out_node->next->prev = out_node; 472 out_node->prev->next = out_node; 473 if (out_node->handle) out_node->handle->m_node = out_node; 474 } 475 m_size--; 476 477 if (m_bufs.GetSize() > (m_next.buffer.num + 1) && m_next.buffer.offset < (BUFFER_SIZE - 3)) 478 m_bufs.Resize(m_bufs.GetSize() - 1); 479 480 return out_data; 481 } 482 483 incSize()484 inline void incSize() 485 { 486 m_next.index++; 487 if (m_bufs.GetSize() <= m_next.buffer.num) m_bufs.Resize(m_bufs.GetSize() + 1); 488 m_size++; 489 } 490 491 public: 492 class Iterator 493 { 494 friend class BufferedDL<T>; 495 private: 496 BufferedDL<T>* m_list; 497 Node* m_cur; 498 499 Iterator(); // @not_implemented 500 Iterator(BufferedDL<T> * list)501 Iterator(BufferedDL<T>* list) : m_list(list), m_cur(&list->m_root) { ; } 502 503 public: Get()504 inline T* Get() { 505 if (m_cur && m_cur != &m_list->m_root) return &m_cur->data; 506 return NULL; 507 } 508 Next()509 inline T* Next() { 510 if (m_cur) { 511 m_cur = m_cur->next; 512 if (m_cur == &m_list->m_root) { 513 m_cur = NULL; 514 return NULL; 515 } else { 516 return &m_cur->data; 517 } 518 } 519 return NULL; 520 } 521 }; 522 523 class ConstIterator 524 { 525 friend class BufferedDL<T>; 526 private: 527 const BufferedDL<T>* m_list; 528 const Node* m_cur; 529 530 ConstIterator(); // @not_implemented 531 ConstIterator(const BufferedDL<T> * list)532 ConstIterator(const BufferedDL<T>* list) : m_list(list), m_cur(&list->m_root) { ; } 533 534 public: Get()535 inline const T* Get() { 536 if (m_cur && m_cur != &m_list->m_root) return &m_cur->data; 537 return NULL; 538 } 539 Next()540 inline const T* Next() { 541 if (m_cur) { 542 m_cur = m_cur->next; 543 if (m_cur == &m_list->m_root) { 544 m_cur = NULL; 545 return NULL; 546 } else { 547 return &m_cur->data; 548 } 549 } 550 return NULL; 551 } 552 }; 553 554 555 class EntryHandle 556 { 557 friend class BufferedDL<T>; 558 private: 559 BufferedDL<T>* m_list; 560 Node* m_node; 561 562 EntryHandle(); // @not_implemented 563 EntryHandle(const EntryHandle&); // @not_implemented 564 EntryHandle& operator=(const EntryHandle&); // @not_implemented 565 EntryHandle(BufferedDL<T> * list,Node * node)566 EntryHandle(BufferedDL<T>* list, Node* node) : m_list(list), m_node(node) { ; } 567 568 public: ~EntryHandle()569 ~EntryHandle() { if (m_node) m_node->handle = NULL; } IsValid()570 bool IsValid() const { return (m_node); } Remove()571 void Remove() 572 { 573 if (!m_node) return; 574 m_list->removeNode(m_node); 575 m_node = NULL; 576 } 577 }; 578 579 }; 580 581 582 template <class T> class SparseVector 583 { 584 public: 585 class EntryHandle; 586 class Iterator; 587 class ConstIterator; 588 589 private: 590 static const int SEGMENT_SIZE = 16; 591 592 int m_size; 593 int m_segs; 594 595 struct ListSegment 596 { 597 SparseVector<T>* list; 598 int used; 599 T entries[SEGMENT_SIZE]; 600 ListSegment* prev; 601 ListSegment* next; 602 EntryHandle* handles[SEGMENT_SIZE]; 603 ListSegmentListSegment604 ListSegment() : used(0), next(NULL) { ; } 605 ListSegment(SparseVector<T>* in_list, const T& value, ListSegment* in_next, ListSegment* in_prev = NULL) listListSegment606 : list(in_list), used(1), prev(in_prev), next(in_next) 607 { 608 entries[0] = value; handles[0] = NULL; 609 } 610 }; 611 612 ListSegment* m_head_seg; 613 ListSegment* m_tail_seg; 614 SparseVector(const SparseVector &)615 SparseVector(const SparseVector&) { ; } 616 617 618 protected: SparseVector()619 SparseVector() : m_size(0), m_segs(0), m_head_seg(NULL), m_tail_seg(NULL) { ; } 620 ~SparseVector()621 ~SparseVector() 622 { 623 ListSegment* cur = m_head_seg; 624 while (cur) { 625 // Clear handles 626 for (int i = 0; i < cur->used; i++) if (cur->handles[i]) cur->handles[i]->m_seg = NULL; 627 628 ListSegment* next = cur->next; 629 delete cur; 630 cur = next; 631 } 632 } 633 634 SparseVector& operator=(const SparseVector& rhs) 635 { 636 if (this == &rhs) return *this; 637 // TODO - SparseVector assignment operator is quick-and-dirty - should more efficiently copy over elements 638 Clear(); 639 ConstIterator it = rhs.Begin(); 640 while (it.Next()) PushRear(*it.Get()); 641 return *this; 642 } 643 644 GetSize()645 inline int GetSize() const { return m_size; } 646 Clear()647 void Clear() 648 { 649 ListSegment* cur = m_head_seg; 650 while (cur) { 651 // Clear handles 652 for (int i = 0; i < cur->used; i++) if (cur->handles[i]) cur->handles[i]->m_seg = NULL; 653 654 ListSegment* next = cur->next; 655 delete cur; 656 cur = next; 657 } 658 m_head_seg = NULL; 659 m_tail_seg = NULL; 660 m_size = 0; 661 m_segs = 0; 662 } 663 664 GetFirst()665 inline T& GetFirst() { return m_head_seg->entries[m_head_seg->used - 1]; } GetFirst()666 inline const T& GetFirst() const { return m_head_seg->entries[m_head_seg->used - 1]; } GetLast()667 inline T& GetLast() { return m_tail_seg->entries[0]; } GetLast()668 inline const T& GetLast() const { return m_tail_seg->entries[0]; } 669 670 671 void Push(const T& value, EntryHandle** handle = NULL) 672 { 673 if (handle) delete *handle; 674 if (m_head_seg && m_head_seg->used < SEGMENT_SIZE) { 675 int idx = m_head_seg->used; 676 m_head_seg->used++; 677 m_head_seg->entries[idx] = value; 678 if (handle) { 679 *handle = m_head_seg->handles[idx] = new EntryHandle(m_head_seg, value); 680 } else { 681 m_head_seg->handles[idx] = NULL; 682 } 683 } else { 684 m_head_seg = new ListSegment(this, value, m_head_seg); 685 m_segs++; 686 if (m_head_seg->next) { 687 m_head_seg->next->prev = m_head_seg; 688 } else { 689 m_tail_seg = m_head_seg; 690 } 691 if (handle) *handle = m_head_seg->handles[0] = new EntryHandle(m_head_seg, value); 692 } 693 694 m_size++; 695 } 696 697 void PushRear(const T& value, EntryHandle** handle = NULL) 698 { 699 if (handle) delete *handle; 700 if (m_tail_seg && m_tail_seg->used < SEGMENT_SIZE) { 701 for (int i = m_tail_seg->used; i > 0; i--) m_tail_seg->entries[i] = m_tail_seg->entries[i - 1]; 702 for (int i = m_tail_seg->used; i > 0; i--) m_tail_seg->handles[i] = m_tail_seg->handles[i - 1]; 703 m_tail_seg->entries[0] = value; 704 m_tail_seg->used++; 705 if (handle) { 706 *handle = m_tail_seg->handles[0] = new EntryHandle(m_tail_seg, value); 707 } else { 708 m_tail_seg->handles[0] = NULL; 709 } 710 } else if (m_tail_seg && m_tail_seg->used == SEGMENT_SIZE) { 711 m_tail_seg->next = new ListSegment(this, value, NULL, m_tail_seg); 712 m_segs++; 713 m_tail_seg = m_tail_seg->next; 714 if (handle) *handle = m_tail_seg->handles[0] = new EntryHandle(m_tail_seg, value); 715 } else { 716 m_tail_seg = new ListSegment(this, value, NULL, NULL); 717 m_segs++; 718 m_head_seg = m_tail_seg; 719 if (handle) *handle = m_tail_seg->handles[0] = new EntryHandle(m_tail_seg, value); 720 } 721 722 m_size++; 723 } 724 Pop()725 inline T Pop() 726 { 727 T rval = GetFirst(); 728 removeFromSeg(rval, m_head_seg, m_head_seg->used - 1); 729 return rval; 730 } 731 PopRear()732 T PopRear() 733 { 734 T rval = GetLast(); 735 removeFromSeg(rval, m_tail_seg, 0); 736 return rval; 737 } 738 Remove(const T & value)739 bool Remove(const T& value) 740 { 741 ListSegment* cur = m_head_seg; 742 while (cur) { 743 if (removeFromSeg(value, cur)) return true; 744 cur = cur->next; 745 } 746 return false; 747 } 748 Begin()749 Iterator Begin() { return Iterator(this); } Begin()750 ConstIterator Begin() const { return ConstIterator(this); } 751 752 753 public: GetDataSize()754 int GetDataSize() const { return sizeof(T) * m_size; } GetMemSize()755 int GetMemSize() const { return sizeof(ListSegment) * m_segs; } 756 757 private: 758 bool removeFromSeg(const T& value, ListSegment* cur, int entry_idx = 0) 759 { 760 for (; entry_idx < cur->used; entry_idx++) { 761 if (cur->entries[entry_idx] == value) { 762 cur->used--; 763 if (cur->used == 0) { 764 // Last entry in this segment, remove segment 765 if (cur->prev) cur->prev->next = cur->next; 766 if (cur->next) cur->next->prev = cur->prev; 767 if (cur == m_head_seg) m_head_seg = cur->next; 768 if (cur == m_tail_seg) m_tail_seg = cur->prev; 769 770 m_segs--; 771 if (cur->handles[0]) cur->handles[0]->m_seg = NULL; 772 delete cur; 773 } else if (cur->next && (cur->used + cur->next->used) <= SEGMENT_SIZE) { 774 // Pack the remaining entries in this segment onto the next 775 for (int j = 0; j < entry_idx && j < cur->used; j++) cur->next->entries[cur->next->used + j] = cur->entries[j]; 776 for (int j = entry_idx; j < cur->used; j++) cur->next->entries[cur->next->used + j] = cur->entries[j + 1]; 777 778 // Move and update segment handles associated with moved entries 779 for (int j = 0; j < entry_idx && j < cur->used; j++) { 780 EntryHandle* handle = cur->handles[j]; 781 cur->next->handles[cur->next->used + j] = handle; 782 if (handle) handle->m_seg = cur->next; 783 } 784 if (cur->handles[entry_idx]) cur->handles[entry_idx]->m_seg = NULL; 785 for (int j = entry_idx; j < cur->used; j++) { 786 EntryHandle* handle = cur->handles[j + 1]; 787 cur->next->handles[cur->next->used + j] = handle; 788 if (handle) handle->m_seg = cur->next; 789 } 790 791 // Update used count on packed segment 792 cur->next->used += cur->used; 793 794 // Remove now empty segment 795 if (cur->prev) cur->prev->next = cur->next; 796 if (cur->next) cur->next->prev = cur->prev; 797 if (cur == m_head_seg) m_head_seg = cur->next; 798 m_segs--; 799 delete cur; 800 } else { 801 // Shift remaining entries in this segment 802 for (int j = entry_idx; j < cur->used; j++) cur->entries[j] = cur->entries[j + 1]; 803 if (cur->handles[entry_idx]) cur->handles[entry_idx]->m_seg = NULL; 804 for (int j = entry_idx; j < cur->used; j++) cur->handles[j] = cur->handles[j + 1]; 805 806 // Clean up now unused entry with default (should, for example, force SmartPtr clean up) 807 cur->entries[cur->used] = T(); 808 } 809 810 m_size--; 811 return true; 812 } 813 } 814 return false; 815 } 816 817 818 public: 819 class Iterator 820 { 821 friend class SparseVector<T>; 822 private: 823 SparseVector<T>* m_list; 824 ListSegment* m_cur; 825 int m_pos; 826 827 Iterator(); // @not_implemented 828 Iterator(SparseVector<T> * list)829 Iterator(SparseVector<T>* list) 830 : m_list(list), m_cur(list->m_head_seg), m_pos((list->m_head_seg) ? list->m_head_seg->used : -1) { ; } 831 832 833 public: Get()834 T* Get() { 835 if (m_cur && m_pos >= 0 && m_pos < m_cur->used) { 836 return &m_cur->entries[m_pos]; 837 } 838 return NULL; 839 } 840 Next()841 T* Next() { 842 if (m_cur && m_pos > 0) { 843 m_pos--; 844 return &m_cur->entries[m_pos]; 845 } 846 if (m_cur && m_pos <= 0) { 847 m_cur = m_cur->next; 848 if (m_cur) { 849 m_pos = m_cur->used - 1; 850 return &m_cur->entries[m_pos]; 851 } 852 } 853 return NULL; 854 } 855 }; 856 857 class ConstIterator 858 { 859 friend class SparseVector<T>; 860 private: 861 const SparseVector<T>* m_list; 862 ListSegment* m_cur; 863 int m_pos; 864 865 ConstIterator(); // @not_implemented 866 ConstIterator(const SparseVector<T> * list)867 ConstIterator(const SparseVector<T>* list) 868 : m_list(list), m_cur(list->m_head_seg), m_pos((list->m_head_seg) ? list->m_head_seg->used : -1) { ; } 869 870 public: Get()871 const T* Get() { 872 if (m_cur && m_pos >= 0 && m_pos < m_cur->used) { 873 return &m_cur->entries[m_pos]; 874 } 875 return NULL; 876 } 877 Next()878 const T* Next() { 879 if (m_cur && m_pos > 0) { 880 m_pos--; 881 return &m_cur->entries[m_pos]; 882 } 883 if (m_cur && m_pos <= 0) { 884 m_cur = m_cur->next; 885 if (m_cur) { 886 m_pos = m_cur->used - 1; 887 return &m_cur->entries[m_pos]; 888 } 889 } 890 return NULL; 891 } 892 }; 893 894 895 class EntryHandle 896 { 897 friend class SparseVector<T>; 898 private: 899 ListSegment* m_seg; 900 T m_entry; 901 902 EntryHandle(); // @not_implemented 903 EntryHandle(const EntryHandle&); // @not_implemented 904 EntryHandle& operator=(const EntryHandle&); // @not_implemented 905 EntryHandle(ListSegment * seg,const T & entry)906 EntryHandle(ListSegment* seg, const T& entry) : m_seg(seg), m_entry(entry) { ; } 907 908 public: ~EntryHandle()909 ~EntryHandle() 910 { 911 if (m_seg) { 912 for (int i = 0; i < m_seg->used; i++) { 913 if (m_seg->handles[i] == this) { 914 m_seg->handles[i] = NULL; 915 break; 916 } 917 } 918 } 919 } IsValid()920 bool IsValid() const { return (m_seg); } Remove()921 void Remove() 922 { 923 if (!m_seg) return; 924 m_seg->list->removeFromSeg(m_entry, m_seg); 925 m_seg = NULL; 926 } 927 }; 928 }; 929 930 }; 931 932 #endif 933