CFx SDK Documentation 2024 SP0
Loading...
Searching...
No Matches
OdLinkedArray.h
Go to the documentation of this file.
1// FELIX_CHANGE_BEGIN file was take from ODA gitlab repository https://gitlab.opendesign.com/
3// Copyright (C) 2002-2022, Open Design Alliance (the "Alliance").
4// All rights reserved.
5//
6// This software and its documentation and related materials are owned by
7// the Alliance. The software may only be incorporated into application
8// programs owned by members of the Alliance, subject to a signed
9// Membership Agreement and Supplemental Software License Agreement with the
10// Alliance. The structure and organization of this software are the valuable
11// trade secrets of the Alliance and its suppliers. The software is also
12// protected by copyright law and international treaty provisions. Application
13// programs incorporating this software must include the following statement
14// with their copyright notices:
15//
16// This application incorporates Open Design Alliance software pursuant to a license
17// agreement with Open Design Alliance.
18// Open Design Alliance Copyright (C) 2002-2022 by Open Design Alliance.
19// All rights reserved.
20//
21// By use of this software, its documentation or related materials, you
22// acknowledge and accept the above terms.
24#ifndef ODLINKEDARRAY_H_INCLUDED
25#define ODLINKEDARRAY_H_INCLUDED
26#include "OdArray.h" // to use allocators
38template <class T, class A = OdObjectsAllocator<T> >
40{
41public:
42 typedef typename A::size_type size_type;
43private:
44 class PAGE
45 {
46 public:
47 PAGE* _next;
48 PAGE* _prev;
49 size_type _size;
50 // Page allocation/deallocation
51 //
52 static PAGE* allocate(size_type pageSize)
53 {
54 PAGE* page = (PAGE*)::odrxAlloc(sizeof(PAGE) + pageSize * sizeof(T));
55 if (!page)
56 throw OdError(eOutOfMemory);
57 page->_prev = 0;
58 page->_next = 0;
59 page->_size = 0;
60 return page;
61 }
62 void release()
63 {
64 A::destroyRange(items(), _size);
65 ::odrxFree(this);
66 }
67 // Access to items on page
68 //
69 T& at(size_type index)
70 {
71 assertValid(index);
72 return *(items(index));
73 }
74 const T& at(size_type index) const
75 {
76 assertValid(index);
77 return *(items(index));
78 }
79 // Add items to page
80 //
81 size_type append(const T& value)
82 {
83 A::copyConstruct(items(_size), value);
84 return ++_size;
85 }
86 size_type insertAt(size_type i, const T& value)
87 {
88 size_type moved = _size - i;
89 ODA_ASSERT(moved<=_size);
90 A::copyAssignRange(items(i+1), items(i), moved);
91 A::copyConstruct(items(i), value);
92 return ++_size;
93 }
94 void resize(size_type newSize, const T& value)
95 {
96 ODA_ASSERT(newSize>_size);
97 A::copyConstructFill(items(_size), newSize-_size, value);
98 _size = newSize;
99 }
100 void resize(size_type newSize)
101 {
102 if(newSize>_size) {
103 A::defaultConstructFill(items(_size), newSize-_size);
104 _size = newSize;
105 }
106 else {
107 A::destroyRange(items(0), _size - newSize);
108 _size = newSize;
109 }
110 }
111 void moveFrom(PAGE* src, size_type start)
112 {
113 ODA_ASSERT(src && (this!=src));
114 ODA_ASSERT(start && start<src->_size);
115 A::copyAssignRangeDisjoint(items(_size), src->items(), start);
116 _size += start;
117 src->_size -= start;
118 A::copyAssignRange(src->items(), src->items(start), src->_size);
119 }
120 void remove(size_type i)
121 {
122 A::destroyRange(items(i), 1);
123 --_size;
124 if ( i < _size )
125 A::copyAssignRange(items(i), items(i+1), _size - i);
126 }
127 void removeLast()
128 {
129 A::destroyRange(items(_size--), 1);
130 }
131 private:
132 T* items(size_type i = 0)
133 {
134 return (T*)((OdUInt8*)this + sizeof(PAGE)) + i;
135 }
136 void assertValid(size_type index) const
137 {
138 if (index >= _size)
139 {
140 ODA_FAIL();
141 throw OdError(eInvalidIndex);
142 }
143 }
144 };
145private:
146 // Add/insert new page
147 //
148 PAGE* addPage()
149 {
150 PAGE* page = PAGE::allocate(_pageSize);
151 if (!_last)
152 {
153 ODA_ASSERT(!_first);
154 _first = page;
155 _last = page;
156 }
157 else
158 {
159 ODA_ASSERT(_first);
160 _last->_next = page;
161 page->_prev = _last;
162 _last = page;
163 }
164 ++_pageNums;
165 return page;
166 }
167 PAGE* insertPage(PAGE* prev)
168 {
169 PAGE* page = PAGE::allocate(_pageSize);
170 if (!_first)
171 {
172 ODA_ASSERT(!prev && !_last);
173 _first = page;
174 _last = page;
175 }
176 else if (!prev)
177 {
178 ODA_ASSERT(_first && _last);
179 _first->_prev = page;
180 page->_next = _first;
181 _first = page;
182 }
183 else
184 {
185 ODA_ASSERT(_first && _last);
186 if (prev == _last)
187 {
188 _last = page;
189 }
190 else
191 {
192 ODA_ASSERT(prev->_next);
193 prev->_next->_prev = page;
194 page->_next = prev->_next;
195 }
196 prev->_next = page;
197 page->_prev = prev;
198 }
199 ++_pageNums;
200 return page;
201 }
202 PAGE* _first;
203 PAGE* _last;
204 size_type _pageNums;
205 size_type _pageSize;
206 size_type _itemNums;
207private:
208 // Prohibit usage
210 OdLinkedArray& operator = (const OdLinkedArray&);
211
212 // Construction/destruction
213 //
214public:
219 OdLinkedArray(OdUInt32 pageSize = 0x10)
220 : _first(0)
221 , _last(0)
222 , _pageNums(0)
223 , _pageSize(pageSize)
224 , _itemNums(0)
225 {
226 if (pageSize == 0) {
227 // throwing an exception from the failed constructor is the standard way of saying to user that
228 // this object is unusable, for more info see https://isocpp.org/wiki/faq/exceptions#ctors-can-throw
229 throw OdError(eInvalidInput);
230 }
231 }
232 //DOM-IGNORE-BEGIN
234 {
235 clear();
236 }
242 //DOM-IGNORE-END
246 void clear()
247 {
248 PAGE *next, *curr = _first;
249 while (curr)
250 {
251 next = curr->_next;
252 curr->release();
253 curr = next;
254 }
255 _first = 0;
256 _last = 0;
257 _pageNums = 0;
258 _itemNums = 0;
259 }
264 {
265 if (_itemNums == 0)
266 {
267 ODA_FAIL();
268 return T();
269 }
270 T data = _last->at(_last->_size - 1);
271 --_itemNums;
272 _last->removeLast();
273 if (!_last->_size)
274 {
275 --_pageNums;
276 PAGE* p = _last->_prev;
277 _last->release();
278 _last = p;
279 if (!_last)
280 _first = 0;
281 else
282 _last->_next = 0;
283 }
284 return data;
285 }
286 //DOM-IGNORE-BEGIN
287 class const_iterator : public std::iterator<std::bidirectional_iterator_tag, T, void>
288 {
289 public:
291 : _page(0)
292 , _ind(0) {}
293 const T& operator*() const
294 {
295 return _page->at(_ind);
296 }
297 operator const T*() const {
298 return &_page->at(_ind);
299 }
300 const T* operator->() const
301 {
302 return &**this;
303 }
305 {
306 next();
307 return *this;
308 }
310 {
311 const_iterator tmp = *this;
312 ++*this;
313 return tmp;
314 }
316 {
317 prev();
318 return *this;
319 }
321 {
322 const_iterator tmp = *this;
323 --*this;
324 return tmp;
325 }
327 seek(n);
328 return *this;
329 }
331 seek(-n);
332 return *this;
333 }
334 bool operator==(const const_iterator& it) const
335 {
336 return (_page == it._page && _ind == it._ind);
337 }
338 bool operator!=(const const_iterator& it) const
339 {
340 return (!(*this == it));
341 }
342 bool done() const
343 {
344 return (!_page || (_ind >= _page->_size/* && !_page->_next*/));
345 }
346 protected:
348 : _page(page)
349 , _ind(ind) {}
350 void seek(int n) {
351 if(n > 0)
352 next(n);
353 else
354 prev(-n);
355 }
356 void next(int n=1)
357 {
358 if (!_page)
359 {
360 ODA_FAIL();
361 return;
362 }
363 _ind += n;
364 while (_page && _page->_next && _ind>=_page->_size)
365 {
366 _ind -= _page->_size;
367 _page = _page->_next;
368 }
369 }
370 void prev(int n=1)
371 {
372 if (!_page)
373 {
374 ODA_FAIL();
375 return;
376 }
377 while (_page && _page->_prev && _ind < (unsigned)n) {
378 _page = _page->_prev;
379 _ind += _page->_size;
380 }
381 _ind -= n;
382 }
384 unsigned _ind;
385 friend class OdLinkedArray<T,A>;
386 };
388 {
389 public:
391 T& operator*() const
392 {
393 return this->_page->at(this->_ind);
394 }
395 operator T*() {
396 return &(this->_page->at(this->_ind));
397 }
399 return &**this;
400 }
402 {
403 this->next();
404 return *this;
405 }
407 {
408 iterator tmp = *this;
409 ++*this;
410 return tmp;
411 }
413 this->seek(n);
414 return *this;
415 }
417 this->seek(-n);
418 return *this;
419 }
421 {
422 this->prev();
423 return *this;
424 }
426 {
427 iterator tmp = *this;
428 --*this;
429 return tmp;
430 }
431 private:
432 iterator(OD_TYPENAME2 OD_LINKEDARRAY_SCOPE PAGE* page, unsigned ind = 0)
433 : const_iterator(page, ind) {}
434 friend class OdLinkedArray<T, A>;
435 };
436 //DOM-IGNORE-END
441 {
442 return iterator(_first, 0);
443 }
448 {
449 return const_iterator(_first, 0);
450 }
455 {
456 return iterator(_last, (_last ? _last->_size : 0));
457 }
462 {
463 return const_iterator(_last, (_last ? _last->_size : 0));
464 }
471 iterator find(const T& val)
472 {
473 iterator it = begin(),
474 endIt = end();
475 while (it != endIt && *it != val)
476 {
477 ++it;
478 }
479 return it;
480 }
487 const_iterator find(const T& val) const
488 {
489 const_iterator it = begin(),
490 endIt = end();
491 while (it != endIt && *it != val)
492 {
493 ++it;
494 }
495 return it;
496 }
501 bool contains(const T& val) const
502 {
503 const_iterator it = find(val);
504 return !it.done();
505 }
510 void resize(size_type newSize)
511 {
512 int d = newSize - size();
513 if (d > 0)
514 {
515 if (_last) {
516 // fill last existed page
517 int d0;
518 if(_last->_size < _pageSize) {
519 d0 = odmin(d, (int)(_pageSize - _last->_size));
520 _last->resize(_last->_size + d0);
521 d -= d0;
522 }
523 // reuse clear pages
524 while (d && _last->_next) {
525 _last = _last->_next;
526 ODA_ASSERT(_last->_size==0);
527 d0 = odmin(d, (int)_pageSize);
528 _last->resize(d0);
529 d -= d0;
530 }
531 }
532 // add new full pages
533 while (d>=(int)_pageSize)
534 {
535 addPage()->resize(_pageSize);
536 d -= _pageSize;
537 }
538 // add new partial page
539 if (d>0)
540 {
541 addPage()->resize(d);
542 }
543 _itemNums = newSize;
544 }
545 else if (d < 0)
546 {
547 while ((size_type)-d >= _last->_size) {
548 d += _last->_size;
549 PAGE* pToRemove = _last;
550 _last = _last->_prev;
551 pToRemove->release();
552 --_pageNums;
553 if (_last)
554 _last->_next = NULL;
555 else
556 {
557 _first = NULL;
558 break;
559 }
560 }
561 if (-d > 0) {
562 d += _last->_size;
563 _last->resize(d);
564 }
565 _itemNums = newSize;
566 }
567 }
573 iterator insert(iterator before, const T& val = T())
574 {
575 if (before.done())
576 {
577 append(val);
578 before = end();
579 --before;
580 }
581 else
582 {
583 size_type curInd = before._ind;
584 PAGE* curPage = before._page;
585 ODA_ASSERT(curPage);
586 if (curPage->_size < _pageSize)
587 {
588 curPage->insertAt(curInd, val); // there is free space in current page
589 }
590 else
591 {
592 PAGE* prevPage = curPage->_prev;
593 if (!prevPage || (prevPage->_size + curInd) >= _pageSize)
594 {
595 prevPage = insertPage(prevPage); // there is not enough free space in previous page
596 }
597 if (curInd)
598 {
599 prevPage->moveFrom(curPage, curInd); // move part of data to previous page
600 }
601 ODA_ASSERT(prevPage);
602 prevPage->append(val);
603 before = iterator(prevPage, prevPage->_size-1);
604 }
605 ++_itemNums;
606 }
607 return before;
608 }
614 {
615 size_type curInd = at._ind;
616 PAGE* curPage = at._page;
617 if (curPage == _last && curInd == (_last->_size - 1))
618 return removeLast();
619 T data = curPage->at(curInd);
620 if (curPage->_size == 1) // removing last page item
621 {
622 if (curPage->_prev)
623 curPage->_prev->_next = curPage->_next;
624 else
625 this->_first = curPage->_next;
626 if (curPage->_next)
627 curPage->_next->_prev = curPage->_prev;
628 curPage->release();
629 --this->_pageNums;
630 }
631 else
632 {
633 curPage->remove(curInd);
634 }
635 --this->_itemNums;
636 return data;
637 }
641 void append(const T& value)
642 {
643 if (_last && _last->_size < _pageSize)
644 {
645 _last->append(value);
646 }
647 else
648 {
649 addPage()->append(value);
650 }
651 ++_itemNums;
652 }
657 resize(size()+1);
658 return --end();
659 }
663 T& first() {
664 return *begin();
665 }
669 const T& first() const {
670 return *begin();
671 }
675 T& last() {
676 return *(--end());
677 }
681 const T& last() const {
682 return *(--end());
683 }
687 bool empty() const {
688 return size()==0;
689 }
694 {
695#ifdef _DEBUG
696 size_type itemNums = 0,
697 pageNums = 0;
698 PAGE* page = _first;
699 while (page)
700 {
701 ++pageNums;
702 itemNums += page->_size;
703 page = page->_next;
704 }
705 ODA_ASSERT(_itemNums == itemNums);
706 ODA_ASSERT(_pageNums == pageNums);
707#endif
708 return _itemNums;
709 }
713 void freeExtra() {
714 if (_last) {
715 PAGE *curr = _last->_next;
716 _last->_next = 0;
717 while (curr) {
718 PAGE *tmp = curr;
719 ODA_ASSERT(curr->_size == 0);
720 curr->release();
721 curr = tmp;
722 }
723 }
724 }
725};
726#endif // ODLINKEDARRAY_H_INCLUDED
727// FELIX_CHANGE_END file was take from ODA gitlab repository https://gitlab.opendesign.com/
#define ODA_ASSERT(exp)
Definition: DebugStuff.h:57
#define ODA_FAIL()
Definition: DebugStuff.h:88
ALLOCDLL_EXPORT void * odrxAlloc(size_t nBytes)
ALLOCDLL_EXPORT void odrxFree(void *pMemBlock)
#define OD_TYPENAME2
Definition: OdPlatform.h:635
#define odmin(X, Y)
Definition: OdPlatform.h:34
#define OD_LINKEDARRAY_SCOPE
Definition: OdPlatform.h:651
unsigned int OdUInt32
unsigned char OdUInt8
bool operator==(const const_iterator &it) const
const_iterator & operator++()
const_iterator operator-=(int n)
bool operator!=(const const_iterator &it) const
OD_TYPENAME2 OD_LINKEDARRAY_SCOPE PAGE * _page
const_iterator(OD_TYPENAME2 OD_LINKEDARRAY_SCOPE PAGE *page, unsigned ind=0)
const_iterator operator++(int)
const_iterator & operator--()
const T * operator->() const
const_iterator operator--(int)
const_iterator operator+=(int n)
iterator operator++(int)
iterator operator--(int)
iterator operator-=(int n)
iterator operator+=(int n)
void reserve(size_type)
iterator find(const T &val)
void append(const T &value)
const_iterator find(const T &val) const
iterator insert(iterator before, const T &val=T())
iterator begin()
const T & first() const
const T & last() const
bool contains(const T &val) const
T remove(iterator at)
A::size_type size_type
Definition: OdLinkedArray.h:42
void resize(size_type newSize)
iterator end()
const_iterator begin() const
const_iterator end() const
bool empty() const
OdLinkedArray(OdUInt32 pageSize=0x10)
iterator append()
size_type size() const
GLint GLenum GLsizei GLsizei GLint GLsizei const void * data
Definition: gles2_ext.h:110
GLuint index
Definition: gles2_ext.h:265
GLsizei const GLfloat * value
Definition: gles2_ext.h:302