1 /* $NoKeywords: $ */
2 /*
3 //
4 // Copyright (c) 1993-2012 Robert McNeel & Associates. All rights reserved.
5 // OpenNURBS, Rhinoceros, and Rhino3D are registered trademarks of Robert
6 // McNeel & Associates.
7 //
8 // THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT EXPRESS OR IMPLIED WARRANTY.
9 // ALL IMPLIED WARRANTIES OF FITNESS FOR ANY PARTICULAR PURPOSE AND OF
10 // MERCHANTABILITY ARE HEREBY DISCLAIMED.
11 //
12 // For complete openNURBS copyright information see <http://www.opennurbs.org>.
13 //
14 ////////////////////////////////////////////////////////////////
15 */
16
17 #if !defined(ON_ARRAY_DEFS_INC_)
18 #define ON_ARRAY_DEFS_INC_
19
20 #if defined(ON_COMPILER_MSC)
21
22 // When this file is parsed with /W4 warnings, two bogus warnings
23 // are generated.
24 #pragma warning(push)
25
26 // The ON_ClassArray<T>::DestroyElement template function generates a
27 // C4100: 'x' : unreferenced formal parameter
28 // warning.
29 // This appears to be caused by a bug in the compiler warning code
30 // or the way templates are expanded. This pragma is needed squelch the
31 // bogus warning.
32 #pragma warning(disable:4100)
33
34 // The ON_CompareIncreasing and ON_CompareDecreasing templates generate a
35 // C4211: nonstandard extension used : redefined extern to static
36 // warning. Microsoft's compiler appears to have a little trouble
37 // when static functions are declared before they are defined in a
38 // single .cpp file. This pragma is needed squelch the bogus warning.
39 #pragma warning(disable:4211)
40 #endif
41
42 // The main reason the definitions of the functions for the
43 // ON_SimpleArray and ON_ClassArray templates are in this separate
44 // file is so that the Microsoft developer studio autocomplete
45 // functions will work on these classes.
46 //
47 // This file is included by opennurbs_array.h in the appropriate
48 // spot. If you need the definitions in the file, then you
49 // should include opennurbs_array.h and let it take care of
50 // including this file.
51
52 /////////////////////////////////////////////////////////////////////////////////////
53 // Class ON_SimpleArray<>
54 /////////////////////////////////////////////////////////////////////////////////////
55
56 // construction ////////////////////////////////////////////////////////
57
58 template <class T>
Realloc(T * ptr,int capacity)59 T* ON_SimpleArray<T>::Realloc(T* ptr,int capacity)
60 {
61 return (T*)onrealloc(ptr,capacity*sizeof(T));
62 }
63
64 template <class T>
ON_SimpleArray()65 ON_SimpleArray<T>::ON_SimpleArray()
66 : m_a(0),
67 m_count(0),
68 m_capacity(0)
69 {}
70
71 template <class T>
ON_SimpleArray(int c)72 ON_SimpleArray<T>::ON_SimpleArray( int c )
73 : m_a(0),
74 m_count(0),
75 m_capacity(0)
76 {
77 if ( c > 0 )
78 SetCapacity( c );
79 }
80
81 // Copy constructor
82 template <class T>
ON_SimpleArray(const ON_SimpleArray<T> & src)83 ON_SimpleArray<T>::ON_SimpleArray( const ON_SimpleArray<T>& src )
84 : m_a(0),
85 m_count(0),
86 m_capacity(0)
87 {
88 *this = src; // operator= defined below
89 }
90
91 template <class T>
~ON_SimpleArray()92 ON_SimpleArray<T>::~ON_SimpleArray()
93 {
94 SetCapacity(0);
95 }
96
97 template <class T>
98 ON_SimpleArray<T>& ON_SimpleArray<T>::operator=( const ON_SimpleArray<T>& src )
99 {
100 if( &src != this ) {
101 if ( src.m_count <= 0 ) {
102 m_count = 0;
103 }
104 else {
105 if ( m_capacity < src.m_count ) {
106 SetCapacity( src.m_count );
107 }
108 if ( m_a ) {
109 m_count = src.m_count;
110 memcpy( m_a, src.m_a, m_count*sizeof(T) );
111 }
112 }
113 }
114 return *this;
115 }
116
117 // emergency destroy ///////////////////////////////////////////////////
118
119 template <class T>
EmergencyDestroy(void)120 void ON_SimpleArray<T>::EmergencyDestroy(void)
121 {
122 m_count = 0;
123 m_capacity = 0;
124 m_a = 0;
125 }
126
127 // query ///////////////////////////////////////////////////////////////
128
129 template <class T>
Count()130 int ON_SimpleArray<T>::Count() const
131 {
132 return m_count;
133 }
134
135 template <class T>
UnsignedCount()136 unsigned int ON_SimpleArray<T>::UnsignedCount() const
137 {
138 return ((unsigned int)m_count);
139 }
140
141 template <class T>
Capacity()142 int ON_SimpleArray<T>::Capacity() const
143 {
144 return m_capacity;
145 }
146
147 template <class T>
SizeOfArray()148 unsigned int ON_SimpleArray<T>::SizeOfArray() const
149 {
150 return ((unsigned int)(m_capacity*sizeof(T)));
151 }
152
153 template <class T>
SizeOfElement()154 unsigned int ON_SimpleArray<T>::SizeOfElement() const
155 {
156 return ((unsigned int)(sizeof(T)));
157 }
158
159
160 template <class T>
DataCRC(ON__UINT32 current_remainder)161 ON__UINT32 ON_SimpleArray<T>::DataCRC(ON__UINT32 current_remainder) const
162 {
163 return ON_CRC32(current_remainder,m_count*sizeof(m_a[0]),m_a);
164 }
165
166 template <class T>
167 T& ON_SimpleArray<T>::operator[]( int i )
168 {
169 #if defined(ON_DEBUG)
170 if ( i < 0 || i > m_capacity )
171 {
172 ON_ERROR("ON_SimpleArray[i]: i out of range.");
173 }
174 #endif
175 return m_a[i];
176 }
177
178 template <class T>
179 T& ON_SimpleArray<T>::operator[]( unsigned int i )
180 {
181 #if defined(ON_DEBUG)
182 if ( i > (unsigned int)m_capacity )
183 {
184 ON_ERROR("ON_SimpleArray[i]: i out of range.");
185 }
186 #endif
187 return m_a[i];
188 }
189
190
191 template <class T>
192 T& ON_SimpleArray<T>::operator[]( ON__INT64 i )
193 {
194 #if defined(ON_DEBUG)
195 if ( i < 0 || i > (ON__INT64)m_capacity )
196 {
197 ON_ERROR("ON_SimpleArray[i]: i out of range.");
198 }
199 #endif
200 return m_a[i];
201 }
202
203 template <class T>
204 T& ON_SimpleArray<T>::operator[]( ON__UINT64 i )
205 {
206 #if defined(ON_DEBUG)
207 if ( i > (ON__UINT64)m_capacity )
208 {
209 ON_ERROR("ON_SimpleArray[i]: i out of range.");
210 }
211 #endif
212 return m_a[i];
213 }
214
215 template <class T>
216 const T& ON_SimpleArray<T>::operator[](int i) const
217 {
218 #if defined(ON_DEBUG)
219 if ( i < 0 || i > m_capacity )
220 {
221 ON_ERROR("ON_SimpleArray[i]: i out of range.");
222 }
223 #endif
224 return m_a[i];
225 }
226
227 template <class T>
228 const T& ON_SimpleArray<T>::operator[](unsigned int i) const
229 {
230 #if defined(ON_DEBUG)
231 if ( i > (unsigned int)m_capacity )
232 {
233 ON_ERROR("ON_SimpleArray[i]: i out of range.");
234 }
235 #endif
236 return m_a[i];
237 }
238
239
240 template <class T>
241 const T& ON_SimpleArray<T>::operator[](ON__INT64 i) const
242 {
243 #if defined(ON_DEBUG)
244 if ( i < 0 || i > ((ON__INT64)m_capacity) )
245 {
246 ON_ERROR("ON_SimpleArray[i]: i out of range.");
247 }
248 #endif
249 return m_a[i];
250 }
251
252 template <class T>
253 const T& ON_SimpleArray<T>::operator[](ON__UINT64 i) const
254 {
255 #if defined(ON_DEBUG)
256 if ( i > (ON__UINT64)m_capacity )
257 {
258 ON_ERROR("ON_SimpleArray[i]: i out of range.");
259 }
260 #endif
261 return m_a[i];
262 }
263
264
265 template <class T>
266 ON_SimpleArray<T>::operator T*()
267 {
268 return (m_count > 0) ? m_a : 0;
269 }
270
271 template <class T>
272 ON_SimpleArray<T>::operator const T*() const
273 {
274 return (m_count > 0) ? m_a : 0;
275 }
276
277 template <class T>
Array()278 T* ON_SimpleArray<T>::Array()
279 {
280 return m_a;
281 }
282
283 template <class T>
Array()284 const T* ON_SimpleArray<T>::Array() const
285 {
286 return m_a;
287 }
288
289 template <class T>
KeepArray()290 T* ON_SimpleArray<T>::KeepArray()
291 {
292 T* p = m_a;
293 m_a = 0;
294 m_count = 0;
295 m_capacity = 0;
296 return p;
297 }
298
299 template <class T>
SetArray(T * p)300 void ON_SimpleArray<T>::SetArray(T* p)
301 {
302 if ( m_a && m_a != p )
303 onfree(m_a);
304 m_a = p;
305 }
306
307 template <class T>
SetArray(T * p,int count,int capacity)308 void ON_SimpleArray<T>::SetArray(T* p, int count, int capacity)
309 {
310 if ( m_a && m_a != p )
311 onfree(m_a);
312 m_a = p;
313 m_count = count;
314 m_capacity = capacity;
315 }
316
317 template <class T>
First()318 T* ON_SimpleArray<T>::First()
319 {
320 return (m_count > 0) ? m_a : 0;
321 }
322
323 template <class T>
First()324 const T* ON_SimpleArray<T>::First() const
325 {
326 return (m_count > 0) ? m_a : 0;
327 }
328
329 template <class T>
At(int i)330 T* ON_SimpleArray<T>::At( int i )
331 {
332 return (i >= 0 && i < m_count) ? m_a+i : 0;
333 }
334
335 template <class T>
At(unsigned int i)336 T* ON_SimpleArray<T>::At( unsigned int i )
337 {
338 return (i < (unsigned int)m_count) ? m_a+i : 0;
339 }
340
341 template <class T>
At(int i)342 const T* ON_SimpleArray<T>::At( int i) const
343 {
344 return (i >= 0 && i < m_count) ? m_a+i : 0;
345 }
346
347 template <class T>
At(unsigned int i)348 const T* ON_SimpleArray<T>::At( unsigned int i) const
349 {
350 return (i < (unsigned int)m_count) ? m_a+i : 0;
351 }
352
353 template <class T>
At(ON__INT64 i)354 T* ON_SimpleArray<T>::At( ON__INT64 i )
355 {
356 return (i >= 0 && i < (ON__INT64)m_count) ? m_a+i : 0;
357 }
358
359 template <class T>
At(ON__UINT64 i)360 T* ON_SimpleArray<T>::At( ON__UINT64 i )
361 {
362 return (i < (ON__UINT64)m_count) ? m_a+i : 0;
363 }
364
365 template <class T>
At(ON__INT64 i)366 const T* ON_SimpleArray<T>::At( ON__INT64 i) const
367 {
368 return (i >= 0 && i < (ON__INT64)m_count) ? m_a+i : 0;
369 }
370
371 template <class T>
At(ON__UINT64 i)372 const T* ON_SimpleArray<T>::At( ON__UINT64 i) const
373 {
374 return (i < (ON__UINT64)m_count) ? m_a+i : 0;
375 }
376
377 template <class T>
Last()378 T* ON_SimpleArray<T>::Last()
379 {
380 return (m_count > 0) ? m_a+(m_count-1) : 0;
381 }
382
383 template <class T>
Last()384 const T* ON_SimpleArray<T>::Last() const
385 {
386 return (m_count > 0) ? m_a+(m_count-1) : 0;
387 }
388
389 // array operations ////////////////////////////////////////////////////
390
391 template <class T>
Move(int dest_i,int src_i,int ele_cnt)392 void ON_SimpleArray<T>::Move( int dest_i, int src_i, int ele_cnt )
393 {
394 // private function for moving blocks of array memory
395 // caller is responsible for updating m_count.
396 if ( ele_cnt <= 0 || src_i < 0 || dest_i < 0 || src_i == dest_i ||
397 src_i + ele_cnt > m_count || dest_i > m_count )
398 return;
399
400 int capacity = dest_i + ele_cnt;
401 if ( capacity > m_capacity ) {
402 if ( capacity < 2*m_capacity )
403 capacity = 2*m_capacity;
404 SetCapacity( capacity );
405 }
406
407 memmove( &m_a[dest_i], &m_a[src_i], ele_cnt*sizeof(T) );
408 }
409
410 template <class T>
AppendNew()411 T& ON_SimpleArray<T>::AppendNew()
412 {
413 if ( m_count == m_capacity )
414 {
415 int new_capacity = NewCapacity();
416 Reserve( new_capacity );
417 }
418 memset( &m_a[m_count], 0, sizeof(T) );
419 return m_a[m_count++];
420 }
421
422 template <class T>
Append(const T & x)423 void ON_SimpleArray<T>::Append( const T& x )
424 {
425 if ( m_count == m_capacity )
426 {
427 const int newcapacity = NewCapacity();
428 if (m_a)
429 {
430 const int s = (int)(&x - m_a); // (int) cast is for 64 bit pointers
431 if ( s >= 0 && s < m_capacity )
432 {
433 // 26 Sep 2005 Dale Lear
434 // User passed in an element of the m_a[]
435 // that will get reallocated by the call
436 // to Reserve(newcapacity).
437 T temp; // ON_*Array<> templates do not require robust copy constructor.
438 temp = x; // ON_*Array<> templates require a robust operator=.
439 Reserve( newcapacity );
440 m_a[m_count++] = temp;
441 return;
442 }
443 }
444 Reserve(newcapacity);
445 }
446 m_a[m_count++] = x;
447 }
448
449 template <class T>
Append(int count,const T * p)450 void ON_SimpleArray<T>::Append( int count, const T* p )
451 {
452 if ( count > 0 && p )
453 {
454 if ( count + m_count > m_capacity )
455 {
456 int newcapacity = NewCapacity();
457 if ( newcapacity < count + m_count )
458 newcapacity = count + m_count;
459 Reserve( newcapacity );
460 }
461 memcpy( m_a + m_count, p, count*sizeof(T) );
462 m_count += count;
463 }
464 }
465
466 template <class T>
Insert(int i,const T & x)467 void ON_SimpleArray<T>::Insert( int i, const T& x )
468 {
469 if( i >= 0 && i <= m_count )
470 {
471 if ( m_count == m_capacity )
472 {
473 int newcapacity = NewCapacity();
474 Reserve( newcapacity );
475 }
476 m_count++;
477 Move( i+1, i, static_cast<unsigned int>(m_count)-1-i );
478 m_a[i] = x;
479 }
480 }
481
482 template <class T>
Remove()483 void ON_SimpleArray<T>::Remove()
484 {
485 Remove(m_count-1);
486 }
487
488 template <class T>
Remove(int i)489 void ON_SimpleArray<T>::Remove( int i )
490 {
491 if ( i >= 0 && i < m_count ) {
492 Move( i, i+1, m_count-1-i );
493 m_count--;
494 memset( &m_a[m_count], 0, sizeof(T) );
495 }
496 }
497
498 template <class T>
Empty()499 void ON_SimpleArray<T>::Empty()
500 {
501 if ( m_a )
502 memset( m_a, 0, m_capacity*sizeof(T) );
503 m_count = 0;
504 }
505
506 template <class T>
Reverse()507 void ON_SimpleArray<T>::Reverse()
508 {
509 // NOTE:
510 // If anything in "T" depends on the value of this's address,
511 // then don't call Reverse().
512 T t;
513 int i = 0;
514 int j = m_count-1;
515 for ( /*empty*/; i < j; i++, j-- ) {
516 t = m_a[i];
517 m_a[i] = m_a[j];
518 m_a[j] = t;
519 }
520 }
521
522 template <class T>
Swap(int i,int j)523 void ON_SimpleArray<T>::Swap( int i, int j )
524 {
525 if ( i != j ) {
526 const T t(m_a[i]);
527 m_a[i] = m_a[j];
528 m_a[j] = t;
529 }
530 }
531
532 template <class T>
Search(const T & key)533 int ON_SimpleArray<T>::Search( const T& key ) const
534 {
535 const T* p = &key;
536 for ( int i = 0; i < m_count; i++ ) {
537 if (!memcmp(p,m_a+i,sizeof(T)))
538 return i;
539 }
540 return -1;
541 }
542
543 template <class T>
Search(const T * key,int (* compar)(const T *,const T *))544 int ON_SimpleArray<T>::Search( const T* key, int (*compar)(const T*,const T*) ) const
545 {
546 for ( int i = 0; i < m_count; i++ ) {
547 if (!compar(key,m_a+i))
548 return i;
549 }
550 return -1;
551 }
552
553 template <class T>
BinarySearch(const T * key,int (* compar)(const T *,const T *))554 int ON_SimpleArray<T>::BinarySearch( const T* key, int (*compar)(const T*,const T*) ) const
555 {
556 const T* found = (key&&m_a&&m_count>0)
557 ? (const T*)bsearch( key, m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar )
558 : 0;
559
560 // This worked on a wide range of 32 bit compilers.
561
562 int rc;
563 if ( 0 != found )
564 {
565 // Convert "found" pointer to array index.
566
567 #if defined(ON_COMPILER_MSC1300)
568 rc = ((int)(found - m_a));
569 #elif 8 == ON_SIZEOF_POINTER
570 // In an ideal world, return ((int)(found - m_a)) would work everywhere.
571 // In practice, this should work any 64 bit compiler and we can hope
572 // the optimzer generates efficient code.
573 const ON__UINT64 fptr = (ON__UINT64)found;
574 const ON__UINT64 aptr = (ON__UINT64)m_a;
575 const ON__UINT64 sz = (ON__UINT64)sizeof(T);
576 const ON__UINT64 i = (fptr - aptr)/sz;
577 rc = (int)i;
578 #else
579 // In an ideal world, return ((int)(found - m_a)) would work everywhere.
580 // In practice, this should work any 32 bit compiler and we can hope
581 // the optimzer generates efficient code.
582 const ON__UINT32 fptr = (ON__UINT32)found;
583 const ON__UINT32 aptr = (ON__UINT32)m_a;
584 const ON__UINT32 sz = (ON__UINT32)sizeof(T);
585 const ON__UINT32 i = (fptr - aptr)/sz;
586 rc = (int)i;
587 #endif
588 }
589 else
590 {
591 // "key" not found
592 rc = -1;
593 }
594
595 return rc;
596
597 }
598
599 template <class T>
BinarySearch(const T * key,int (* compar)(const T *,const T *),int count)600 int ON_SimpleArray<T>::BinarySearch( const T* key, int (*compar)(const T*,const T*), int count ) const
601 {
602 if ( count > m_count )
603 count = m_count;
604 if ( count <= 0 )
605 return -1;
606 const T* found = (key&&m_a&&m_count>0)
607 ? (const T*)bsearch( key, m_a, count, sizeof(T), (int(*)(const void*,const void*))compar )
608 : 0;
609
610 // This worked on a wide range of 32 bit compilers.
611
612 int rc;
613 if ( 0 != found )
614 {
615 // Convert "found" pointer to array index.
616
617 #if defined(ON_COMPILER_MSC1300)
618 rc = ((int)(found - m_a));
619 #elif 8 == ON_SIZEOF_POINTER
620 // In an ideal world, return ((int)(found - m_a)) would work everywhere.
621 // In practice, this should work any 64 bit compiler and we can hope
622 // the optimzer generates efficient code.
623 const ON__UINT64 fptr = (ON__UINT64)found;
624 const ON__UINT64 aptr = (ON__UINT64)m_a;
625 const ON__UINT64 sz = (ON__UINT64)sizeof(T);
626 const ON__UINT64 i = (fptr - aptr)/sz;
627 rc = (int)i;
628 #else
629 // In an ideal world, return ((int)(found - m_a)) would work everywhere.
630 // In practice, this should work any 32 bit compiler and we can hope
631 // the optimzer generates efficient code.
632 const ON__UINT32 fptr = (ON__UINT32)found;
633 const ON__UINT32 aptr = (ON__UINT32)m_a;
634 const ON__UINT32 sz = (ON__UINT32)sizeof(T);
635 const ON__UINT32 i = (fptr - aptr)/sz;
636 rc = (int)i;
637 #endif
638 }
639 else
640 {
641 // "key" not found
642 rc = -1;
643 }
644 return rc;
645 }
646
647
648
649 template <class T>
HeapSort(int (* compar)(const T *,const T *))650 bool ON_SimpleArray<T>::HeapSort( int (*compar)(const T*,const T*) )
651 {
652 bool rc = false;
653 if ( m_a && m_count > 0 && compar ) {
654 if ( m_count > 1 )
655 ON_hsort( m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar );
656 rc = true;
657 }
658 return rc;
659 }
660
661 template <class T>
QuickSort(int (* compar)(const T *,const T *))662 bool ON_SimpleArray<T>::QuickSort( int (*compar)(const T*,const T*) )
663 {
664 bool rc = false;
665 if ( m_a && m_count > 0 && compar ) {
666 if ( m_count > 1 )
667 ON_qsort( m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar );
668 rc = true;
669 }
670 return rc;
671 }
672
673 template <class T>
Sort(ON::sort_algorithm sa,int * index,int (* compar)(const T *,const T *))674 bool ON_SimpleArray<T>::Sort( ON::sort_algorithm sa, int* index, int (*compar)(const T*,const T*) ) const
675 {
676 bool rc = false;
677 if ( m_a && m_count > 0 && compar && index ) {
678 if ( m_count > 1 )
679 ON_Sort(sa, index, m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar );
680 else if ( m_count == 1 )
681 index[0] = 0;
682 rc = true;
683 }
684 return rc;
685 }
686
687 template <class T>
Sort(ON::sort_algorithm sa,int * index,int (* compar)(const T *,const T *,void *),void * p)688 bool ON_SimpleArray<T>::Sort( ON::sort_algorithm sa, int* index, int (*compar)(const T*,const T*,void*),void* p ) const
689 {
690 bool rc = false;
691 if ( m_a && m_count > 0 && compar && index ) {
692 if ( m_count > 1 )
693 ON_Sort(sa, index, m_a, m_count, sizeof(T), (int(*)(const void*,const void*,void*))compar, p );
694 else if ( m_count == 1 )
695 index[0] = 0;
696 rc = true;
697 }
698 return rc;
699 }
700
701 template <class T>
Permute(const int * index)702 bool ON_SimpleArray<T>::Permute( const int* index )
703 {
704 bool rc = false;
705 if ( m_a && m_count > 0 && index ) {
706 int i;
707 T* buffer = (T*)onmalloc(m_count*sizeof(buffer[0]));
708 memcpy( buffer, m_a, m_count*sizeof(T) );
709 for (i = 0; i < m_count; i++ )
710 memcpy( m_a+i, buffer+index[i], sizeof(T) ); // must use memcopy and not operator=
711 onfree(buffer);
712 rc = true;
713 }
714 return rc;
715 }
716
717 template <class T>
Zero()718 void ON_SimpleArray<T>::Zero()
719 {
720 if ( m_a && m_capacity > 0 ) {
721 memset( m_a, 0, m_capacity*sizeof(T) );
722 }
723 }
724
725 template <class T>
MemSet(unsigned char value)726 void ON_SimpleArray<T>::MemSet( unsigned char value )
727 {
728 if ( m_a && m_capacity > 0 ) {
729 memset( m_a, value, m_capacity*sizeof(T) );
730 }
731 }
732
733 // memory managment ////////////////////////////////////////////////////
734
735 template <class T>
Reserve(int newcap)736 void ON_SimpleArray<T>::Reserve( int newcap )
737 {
738 if( m_capacity < newcap )
739 SetCapacity( newcap );
740 }
741
742 template <class T>
Shrink()743 void ON_SimpleArray<T>::Shrink()
744 {
745 SetCapacity( m_count );
746 }
747
748 template <class T>
Destroy()749 void ON_SimpleArray<T>::Destroy()
750 {
751 SetCapacity( 0 );
752 }
753
754 // low level memory managment //////////////////////////////////////////
755
756 template <class T>
SetCount(int count)757 void ON_SimpleArray<T>::SetCount( int count )
758 {
759 if ( count >= 0 && count <= m_capacity )
760 m_count = count;
761 }
762
763 template <class T>
SetCapacity(int capacity)764 void ON_SimpleArray<T>::SetCapacity( int capacity )
765 {
766 // sets capacity to input value
767 if ( capacity != m_capacity ) {
768 if( capacity > 0 ) {
769 if ( m_count > capacity )
770 m_count = capacity;
771 // NOTE: Realloc() does an allocation if the first argument is NULL.
772 m_a = Realloc( m_a, capacity );
773 if ( m_a ) {
774 if ( capacity > m_capacity ) {
775 // zero new memory
776 memset( m_a + m_capacity, 0, (capacity-m_capacity)*sizeof(T) );
777 }
778 m_capacity = capacity;
779 }
780 else {
781 // out of memory
782 m_count = m_capacity = 0;
783 }
784 }
785 else if (m_a) {
786 Realloc(m_a,0);
787 m_a = 0;
788 m_count = m_capacity = 0;
789 }
790 }
791 }
792
793 template <class T>
NewCapacity()794 int ON_SimpleArray<T>::NewCapacity() const
795 {
796 // Note:
797 // This code appears in ON_SimpleArray<T>::NewCapacity()
798 // and ON_ClassArray<T>::NewCapacity(). Changes made to
799 // either function should be made to both functions.
800 // Because this code is template code that has to
801 // support dynamic linking and the code is defined
802 // in a header, I'm using copy-and-paste rather
803 // than a static.
804
805 // This function returns 2*m_count unless that will
806 // result in an additional allocation of more than
807 // cap_size bytes. The cap_size concept was added in
808 // January 2010 because some calculations on enormous
809 // models were slightly underestimating the initial
810 // Reserve() size and then wasting gigabytes of memory.
811
812 // cap_size = 128 MB on 32-bit os, 256 MB on 64 bit os
813 const std::size_t cap_size = 32*sizeof(void*)*1024*1024;
814 if (m_count*sizeof(T) <= cap_size || m_count < 8)
815 return ((m_count <= 2) ? 4 : 2*m_count);
816
817 // Growing the array will increase the memory
818 // use by more than cap_size.
819 int delta_count = 8 + cap_size/sizeof(T);
820 if ( delta_count > m_count )
821 delta_count = m_count;
822 return (m_count + delta_count);
823 }
824
825 template <class T>
NewCapacity()826 int ON_ClassArray<T>::NewCapacity() const
827 {
828 // Note:
829 // This code appears in ON_SimpleArray<T>::NewCapacity()
830 // and ON_ClassArray<T>::NewCapacity(). Changes made to
831 // either function should be made to both functions.
832 // Because this code is template code that has to
833 // support dynamic linking and the code is defined
834 // in a header, I'm using copy-and-paste rather
835 // than a static.
836
837 // This function returns 2*m_count unless that will
838 // result in an additional allocation of more than
839 // cap_size bytes. The cap_size concept was added in
840 // January 2010 because some calculations on enormous
841 // models were slightly underestimating the initial
842 // Reserve() size and then wasting gigabytes of memory.
843
844 // cap_size = 128 MB on 32-bit os, 256 MB on 64 bit os
845 const std::size_t cap_size = 32*sizeof(void*)*1024*1024;
846 if (m_count*sizeof(T) <= cap_size || m_count < 8)
847 return ((m_count <= 2) ? 4 : 2*m_count);
848
849 // Growing the array will increase the memory
850 // use by more than cap_size.
851 int delta_count = 8 + cap_size/sizeof(T);
852 if ( delta_count > m_count )
853 delta_count = m_count;
854 return (m_count + delta_count);
855 }
856
857 /////////////////////////////////////////////////////////////////////////////////////
858 // Class ON_ObjectArray<>
859 /////////////////////////////////////////////////////////////////////////////////////
860
861 template <class T>
ON_ObjectArray()862 ON_ObjectArray<T>::ON_ObjectArray()
863 {
864 }
865
866 template <class T>
~ON_ObjectArray()867 ON_ObjectArray<T>::~ON_ObjectArray()
868 {
869 }
870
871 template <class T>
ON_ObjectArray(const ON_ObjectArray<T> & src)872 ON_ObjectArray<T>::ON_ObjectArray( const ON_ObjectArray<T>& src ) : ON_ClassArray<T>(src)
873 {
874 }
875
876 template <class T>
877 ON_ObjectArray<T>& ON_ObjectArray<T>::operator=( const ON_ObjectArray<T>& src)
878 {
879 if( this != &src)
880 {
881 ON_ClassArray<T>::operator =(src);
882 }
883 return *this;
884 }
885
886
887 template <class T>
ON_ObjectArray(int c)888 ON_ObjectArray<T>::ON_ObjectArray( int c )
889 : ON_ClassArray<T>(c)
890 {
891 }
892
893 template <class T>
Realloc(T * ptr,int capacity)894 T* ON_ObjectArray<T>::Realloc(T* ptr,int capacity)
895 {
896 T* reptr = (T*)onrealloc(ptr,capacity*sizeof(T));
897 if ( ptr && reptr && reptr != ptr )
898 {
899 // The "this->" in this->m_count and this->m_a
900 // are needed for gcc 4 to compile.
901 int i;
902 for ( i = 0; i < this->m_count; i++ )
903 {
904 reptr[i].MemoryRelocate();
905 }
906 }
907 return reptr;
908 }
909
910 /////////////////////////////////////////////////////////////////////////////////////
911 // Class ON_ClassArray<>
912 /////////////////////////////////////////////////////////////////////////////////////
913
914
915 // construction ////////////////////////////////////////////////////////
916
917 template <class T>
Realloc(T * ptr,int capacity)918 T* ON_ClassArray<T>::Realloc(T* ptr,int capacity)
919 {
920 return (T*)onrealloc(ptr,capacity*sizeof(T));
921 }
922
923 template <class T>
DataCRC(ON__UINT32 current_remainder)924 ON__UINT32 ON_ObjectArray<T>::DataCRC(ON__UINT32 current_remainder) const
925 {
926 // The "this->" in this->m_count and this->m_a
927 // are needed for gcc 4 to compile.
928 int i;
929 for ( i = 0; i < this->m_count; i++ )
930 {
931 current_remainder = this->m_a[i].DataCRC(current_remainder);
932 }
933 return current_remainder;
934 }
935
936 template <class T>
ON_ClassArray()937 ON_ClassArray<T>::ON_ClassArray()
938 : m_a(0),
939 m_count(0),
940 m_capacity(0)
941 {}
942
943 template <class T>
ON_ClassArray(int c)944 ON_ClassArray<T>::ON_ClassArray( int c )
945 : m_a(0),
946 m_count(0),
947 m_capacity(0)
948 {
949 if ( c > 0 )
950 SetCapacity( c );
951 }
952
953 // Copy constructor
954 template <class T>
ON_ClassArray(const ON_ClassArray<T> & src)955 ON_ClassArray<T>::ON_ClassArray( const ON_ClassArray<T>& src )
956 : m_a(0),
957 m_count(0),
958 m_capacity(0)
959 {
960 *this = src; // operator= defined below
961 }
962
963 template <class T>
~ON_ClassArray()964 ON_ClassArray<T>::~ON_ClassArray()
965 {
966 SetCapacity(0);
967 }
968
969 template <class T>
970 ON_ClassArray<T>& ON_ClassArray<T>::operator=( const ON_ClassArray<T>& src )
971 {
972 int i;
973 if( &src != this ) {
974 if ( src.m_count <= 0 ) {
975 m_count = 0;
976 }
977 else {
978 if ( m_capacity < src.m_count ) {
979 SetCapacity( src.m_count );
980 }
981 if ( m_a ) {
982 m_count = src.m_count;
983 for ( i = 0; i < m_count; i++ ) {
984 m_a[i] = src.m_a[i];
985 }
986 }
987 }
988 }
989 return *this;
990 }
991
992 // emergency destroy ///////////////////////////////////////////////////
993
994 template <class T>
EmergencyDestroy(void)995 void ON_ClassArray<T>::EmergencyDestroy(void)
996 {
997 m_count = 0;
998 m_capacity = 0;
999 m_a = 0;
1000 }
1001
1002 // query ///////////////////////////////////////////////////////////////
1003
1004 template <class T>
Count()1005 int ON_ClassArray<T>::Count() const
1006 {
1007 return m_count;
1008 }
1009
1010 template <class T>
UnsignedCount()1011 unsigned int ON_ClassArray<T>::UnsignedCount() const
1012 {
1013 return ((unsigned int)m_count);
1014 }
1015
1016 template <class T>
Capacity()1017 int ON_ClassArray<T>::Capacity() const
1018 {
1019 return m_capacity;
1020 }
1021
1022 template <class T>
SizeOfArray()1023 unsigned int ON_ClassArray<T>::SizeOfArray() const
1024 {
1025 return ((unsigned int)(m_capacity*sizeof(T)));
1026 }
1027
1028 template <class T>
SizeOfElement()1029 unsigned int ON_ClassArray<T>::SizeOfElement() const
1030 {
1031 return ((unsigned int)(sizeof(T)));
1032 }
1033
1034 template <class T>
1035 T& ON_ClassArray<T>::operator[]( int i )
1036 {
1037 #if defined(ON_DEBUG)
1038 if ( i < 0 || i > m_capacity )
1039 {
1040 ON_ERROR("ON_ClassArray[i]: i out of range.");
1041 }
1042 #endif
1043 return m_a[i];
1044 }
1045
1046
1047 template <class T>
1048 T& ON_ClassArray<T>::operator[]( ON__INT64 i )
1049 {
1050 #if defined(ON_DEBUG)
1051 if ( i < 0 || i > (ON__INT64)m_capacity )
1052 {
1053 ON_ERROR("ON_ClassArray[i]: i out of range.");
1054 }
1055 #endif
1056 return m_a[i];
1057 }
1058
1059 template <class T>
1060 T& ON_ClassArray<T>::operator[]( unsigned int i )
1061 {
1062 #if defined(ON_DEBUG)
1063 if ( i > (unsigned int)m_capacity )
1064 {
1065 ON_ERROR("ON_ClassArray[i]: i out of range.");
1066 }
1067 #endif
1068 return m_a[i];
1069 }
1070
1071 template <class T>
1072 T& ON_ClassArray<T>::operator[]( ON__UINT64 i )
1073 {
1074 #if defined(ON_DEBUG)
1075 if ( i > (ON__UINT64)m_capacity )
1076 {
1077 ON_ERROR("ON_ClassArray[i]: i out of range.");
1078 }
1079 #endif
1080 return m_a[i];
1081 }
1082
1083 template <class T>
1084 const T& ON_ClassArray<T>::operator[](int i) const
1085 {
1086 #if defined(ON_DEBUG)
1087 if ( i < 0 || i > m_capacity )
1088 {
1089 ON_ERROR("ON_ClassArray[i]: i out of range.");
1090 }
1091 #endif
1092 return m_a[i];
1093 }
1094
1095 template <class T>
1096 const T& ON_ClassArray<T>::operator[](ON__INT64 i) const
1097 {
1098 #if defined(ON_DEBUG)
1099 if ( i < 0 || i > (ON__INT64)m_capacity )
1100 {
1101 ON_ERROR("ON_ClassArray[i]: i out of range.");
1102 }
1103 #endif
1104 return m_a[i];
1105 }
1106
1107 template <class T>
1108 const T& ON_ClassArray<T>::operator[](unsigned int i) const
1109 {
1110 #if defined(ON_DEBUG)
1111 if ( i > (unsigned int)m_capacity )
1112 {
1113 ON_ERROR("ON_ClassArray[i]: i out of range.");
1114 }
1115 #endif
1116 return m_a[i];
1117 }
1118
1119 template <class T>
1120 const T& ON_ClassArray<T>::operator[](ON__UINT64 i) const
1121 {
1122 #if defined(ON_DEBUG)
1123 if ( i > (ON__UINT64)m_capacity )
1124 {
1125 ON_ERROR("ON_ClassArray[i]: i out of range.");
1126 }
1127 #endif
1128 return m_a[i];
1129 }
1130
1131 template <class T>
1132 ON_ClassArray<T>::operator T*()
1133 {
1134 return (m_count > 0) ? m_a : 0;
1135 }
1136
1137 template <class T>
1138 ON_ClassArray<T>::operator const T*() const
1139 {
1140 return (m_count > 0) ? m_a : 0;
1141 }
1142
1143 template <class T>
Array()1144 T* ON_ClassArray<T>::Array()
1145 {
1146 return m_a;
1147 }
1148
1149 template <class T>
Array()1150 const T* ON_ClassArray<T>::Array() const
1151 {
1152 return m_a;
1153 }
1154
1155 template <class T>
KeepArray()1156 T* ON_ClassArray<T>::KeepArray()
1157 {
1158 T* p = m_a;
1159 m_a = 0;
1160 m_count = 0;
1161 m_capacity = 0;
1162 return p;
1163 }
1164
1165 template <class T>
SetArray(T * p)1166 void ON_ClassArray<T>::SetArray(T* p)
1167 {
1168 if ( m_a && m_a != p )
1169 Destroy();
1170 m_a = p;
1171 }
1172
1173 template <class T>
SetArray(T * p,int count,int capacity)1174 void ON_ClassArray<T>::SetArray(T* p, int count, int capacity)
1175 {
1176 if ( m_a && m_a != p )
1177 Destroy();
1178 m_a = p;
1179 m_count = count;
1180 m_capacity = capacity;
1181 }
1182
1183 template <class T>
First()1184 T* ON_ClassArray<T>::First()
1185 {
1186 return (m_count > 0) ? m_a : 0;
1187 }
1188
1189 template <class T>
First()1190 const T* ON_ClassArray<T>::First() const
1191 {
1192 return (m_count > 0) ? m_a : 0;
1193 }
1194
1195 template <class T>
At(int i)1196 T* ON_ClassArray<T>::At( int i )
1197 {
1198 return (i >= 0 && i < m_count) ? m_a+i : 0;
1199 }
1200
1201 template <class T>
At(unsigned int i)1202 T* ON_ClassArray<T>::At( unsigned int i )
1203 {
1204 return (i < (unsigned int)m_count) ? m_a+i : 0;
1205 }
1206
1207 template <class T>
At(int i)1208 const T* ON_ClassArray<T>::At( int i) const
1209 {
1210 return (i >= 0 && i < m_count) ? m_a+i : 0;
1211 }
1212
1213 template <class T>
At(unsigned int i)1214 const T* ON_ClassArray<T>::At( unsigned int i) const
1215 {
1216 return (i < (unsigned int)m_count) ? m_a+i : 0;
1217 }
1218
1219
1220 template <class T>
At(ON__INT64 i)1221 T* ON_ClassArray<T>::At( ON__INT64 i )
1222 {
1223 return (i >= 0 && i < (ON__INT64)m_count) ? m_a+i : 0;
1224 }
1225
1226 template <class T>
At(ON__UINT64 i)1227 T* ON_ClassArray<T>::At( ON__UINT64 i )
1228 {
1229 return (i < (ON__UINT64)m_count) ? m_a+i : 0;
1230 }
1231
1232 template <class T>
At(ON__INT64 i)1233 const T* ON_ClassArray<T>::At( ON__INT64 i) const
1234 {
1235 return (i >= 0 && i < (ON__INT64)m_count) ? m_a+i : 0;
1236 }
1237
1238 template <class T>
At(ON__UINT64 i)1239 const T* ON_ClassArray<T>::At( ON__UINT64 i) const
1240 {
1241 return (i < (ON__UINT64)m_count) ? m_a+i : 0;
1242 }
1243
1244
1245 template <class T>
Last()1246 T* ON_ClassArray<T>::Last()
1247 {
1248 return (m_count > 0) ? m_a+(m_count-1) : 0;
1249 }
1250
1251 template <class T>
Last()1252 const T* ON_ClassArray<T>::Last() const
1253 {
1254 return (m_count > 0) ? m_a+(m_count-1) : 0;
1255 }
1256
1257 // array operations ////////////////////////////////////////////////////
1258
1259 template <class T>
Move(int dest_i,int src_i,int ele_cnt)1260 void ON_ClassArray<T>::Move( int dest_i, int src_i, int ele_cnt )
1261 {
1262 // private function for moving blocks of array memory
1263 // caller is responsible for updating m_count and managing
1264 // destruction/creation.
1265 if ( ele_cnt <= 0 || src_i < 0 || dest_i < 0 || src_i == dest_i ||
1266 src_i + ele_cnt > m_count || dest_i > m_count )
1267 return;
1268
1269 int capacity = dest_i + ele_cnt;
1270 if ( capacity > m_capacity ) {
1271 if ( capacity < 2*m_capacity )
1272 capacity = 2*m_capacity;
1273 SetCapacity( capacity );
1274 }
1275
1276 // This call to memmove is ok, even when T is a class with a vtable
1277 // because the it doesn't change the vtable for the class.
1278 // Classes that have back pointers, like ON_UserData, are
1279 // handled elsewhere and cannot be in ON_ClassArray<>s.
1280 memmove( (void*)(&m_a[dest_i]), (const void*)(&m_a[src_i]), ele_cnt*sizeof(T) );
1281 }
1282
1283 template <class T>
ConstructDefaultElement(T * p)1284 void ON_ClassArray<T>::ConstructDefaultElement(T* p)
1285 {
1286 // use placement ( new(std::size_t,void*) ) to construct
1287 // T in supplied memory
1288 new(p) T;
1289 }
1290
1291 template <class T>
DestroyElement(T & x)1292 void ON_ClassArray<T>::DestroyElement(T& x)
1293 {
1294 x.~T();
1295 }
1296
1297 template <class T>
AppendNew()1298 T& ON_ClassArray<T>::AppendNew()
1299 {
1300 if ( m_count == m_capacity )
1301 {
1302 int newcapacity = NewCapacity();
1303 Reserve( newcapacity );
1304 }
1305 else
1306 {
1307 // First destroy what's there ..
1308 DestroyElement(m_a[m_count]);
1309 // and then get a properly initialized element
1310 ConstructDefaultElement(&m_a[m_count]);
1311 }
1312 return m_a[m_count++];
1313 }
1314
1315 template <class T>
Append(const T & x)1316 void ON_ClassArray<T>::Append( const T& x )
1317 {
1318 if ( m_count == m_capacity )
1319 {
1320 const int newcapacity = NewCapacity();
1321 if (m_a)
1322 {
1323 const int s = (int)(&x - m_a); // (int) cast is for 64 bit pointers
1324 if ( s >= 0 && s < m_capacity )
1325 {
1326 // 26 Sep 2005 Dale Lear
1327 // User passed in an element of the m_a[]
1328 // that will get reallocated by the call
1329 // to Reserve(newcapacity).
1330 T temp; // ON_*Array<> templates do not require robust copy constructor.
1331 temp = x; // ON_*Array<> templates require a robust operator=.
1332 Reserve( newcapacity );
1333 m_a[m_count++] = temp;
1334 return;
1335 }
1336 }
1337 Reserve(newcapacity);
1338 }
1339 m_a[m_count++] = x;
1340 }
1341
1342 template <class T>
Append(int count,const T * p)1343 void ON_ClassArray<T>::Append( int count, const T* p )
1344 {
1345 int i;
1346 if ( count > 0 && p )
1347 {
1348 if ( count + m_count > m_capacity )
1349 {
1350 int newcapacity = NewCapacity();
1351 if ( newcapacity < count + m_count )
1352 newcapacity = count + m_count;
1353 Reserve( newcapacity );
1354 }
1355 for ( i = 0; i < count; i++ ) {
1356 m_a[m_count++] = p[i];
1357 }
1358 }
1359 }
1360
1361 // Insert called with a reference uses operator =
1362 template <class T>
Insert(int i,const T & x)1363 void ON_ClassArray<T>::Insert( int i, const T& x )
1364 {
1365 if( i >= 0 && i <= m_count )
1366 {
1367 if ( m_count == m_capacity )
1368 {
1369 int newcapacity = NewCapacity();
1370 Reserve( newcapacity );
1371 }
1372 DestroyElement( m_a[m_count] );
1373 m_count++;
1374 if ( i < m_count-1 ) {
1375 Move( i+1, i, static_cast<unsigned int>(m_count)-1-i );
1376 // This call to memset is ok even when T has a vtable
1377 // because in-place construction is used later.
1378 memset( (void*)(&m_a[i]), 0, sizeof(T) );
1379 ConstructDefaultElement( &m_a[i] );
1380 }
1381 else {
1382 ConstructDefaultElement( &m_a[m_count-1] );
1383 }
1384 m_a[i] = x; // uses T::operator=() to copy x to array
1385 }
1386 }
1387
1388 template <class T>
Remove()1389 void ON_ClassArray<T>::Remove( )
1390 {
1391 Remove(m_count-1);
1392 }
1393
1394 template <class T>
Remove(int i)1395 void ON_ClassArray<T>::Remove( int i )
1396 {
1397 if ( i >= 0 && i < m_count )
1398 {
1399 DestroyElement( m_a[i] );
1400 // This call to memset is ok even when T has a vtable
1401 // because in-place construction is used later.
1402 memset( (void*)(&m_a[i]), 0, sizeof(T) );
1403 Move( i, i+1, m_count-1-i );
1404 // This call to memset is ok even when T has a vtable
1405 // because in-place construction is used later.
1406 memset( (void*)(&m_a[m_count-1]), 0, sizeof(T) );
1407 ConstructDefaultElement(&m_a[m_count-1]);
1408 m_count--;
1409 }
1410 }
1411
1412 template <class T>
Empty()1413 void ON_ClassArray<T>::Empty()
1414 {
1415 int i;
1416 for ( i = m_count-1; i >= 0; i-- ) {
1417 DestroyElement( m_a[i] );
1418 // This call to memset is ok even when T has a vtable
1419 // because in-place construction is used later.
1420 memset( (void*)(&m_a[i]), 0, sizeof(T) );
1421 ConstructDefaultElement( &m_a[i] );
1422 }
1423 m_count = 0;
1424 }
1425
1426 template <class T>
Reverse()1427 void ON_ClassArray<T>::Reverse()
1428 {
1429 // NOTE:
1430 // If anything in "T" depends on the value of this's address,
1431 // then don't call Reverse().
1432 char t[sizeof(T)];
1433 int i = 0;
1434 int j = m_count-1;
1435 for ( /*empty*/; i < j; i++, j-- ) {
1436 memcpy( t, &m_a[i], sizeof(T) );
1437 memcpy( &m_a[i], &m_a[j], sizeof(T) );
1438 memcpy( &m_a[j], t, sizeof(T) );
1439 }
1440 }
1441
1442 template <class T>
Swap(int i,int j)1443 void ON_ClassArray<T>::Swap( int i, int j )
1444 {
1445 if ( i != j && i >= 0 && j >= 0 && i < m_count && j < m_count ) {
1446 char t[sizeof(T)];
1447 memcpy( t, &m_a[i], sizeof(T) );
1448 memcpy( &m_a[i], &m_a[j], sizeof(T) );
1449 memcpy( &m_a[j], t, sizeof(T) );
1450 }
1451 }
1452
1453 template <class T>
Search(const T * key,int (* compar)(const T *,const T *))1454 int ON_ClassArray<T>::Search( const T* key, int (*compar)(const T*,const T*) ) const
1455 {
1456 for ( int i = 0; i < m_count; i++ )
1457 {
1458 if (!compar(key,m_a+i))
1459 return i;
1460 }
1461 return -1;
1462 }
1463
1464 template <class T>
BinarySearch(const T * key,int (* compar)(const T *,const T *))1465 int ON_ClassArray<T>::BinarySearch( const T* key, int (*compar)(const T*,const T*) ) const
1466 {
1467 const T* found = (key&&m_a&&m_count>0) ? (const T*)bsearch( key, m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar ) : 0;
1468 #if defined(ON_COMPILER_MSC1300)
1469 // for 32 and 64 bit compilers - the (int) converts 64 bit std::size_t
1470 return found ? ((int)(found - m_a)) : -1;
1471 #else
1472 // for lamer 64 bit compilers
1473 return found ? ((int)((((ON__UINT64)found) - ((ON__UINT64)m_a))/sizeof(T))) : -1;
1474 #endif
1475 }
1476
1477 template <class T>
BinarySearch(const T * key,int (* compar)(const T *,const T *),int count)1478 int ON_ClassArray<T>::BinarySearch( const T* key, int (*compar)(const T*,const T*), int count ) const
1479 {
1480 if ( count > m_count )
1481 count = m_count;
1482 if ( count <= 0 )
1483 return -1;
1484 const T* found = (key&&m_a&&m_count>0) ? (const T*)bsearch( key, m_a, count, sizeof(T), (int(*)(const void*,const void*))compar ) : 0;
1485 #if defined(ON_COMPILER_MSC1300)
1486 // for 32 and 64 bit compilers - the (int) converts 64 bit std::size_t
1487 return found ? ((int)(found - m_a)) : -1;
1488 #else
1489 // for lamer 64 bit compilers
1490 return found ? ((int)((((ON__UINT64)found) - ((ON__UINT64)m_a))/sizeof(T))) : -1;
1491 #endif
1492 }
1493
1494 template <class T>
HeapSort(int (* compar)(const T *,const T *))1495 bool ON_ClassArray<T>::HeapSort( int (*compar)(const T*,const T*) )
1496 {
1497 bool rc = false;
1498 if ( m_a && m_count > 0 && compar )
1499 {
1500 if ( m_count > 1 )
1501 ON_hsort( m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar );
1502 rc = true;
1503 }
1504 return rc;
1505 }
1506
1507 template <class T>
QuickSort(int (* compar)(const T *,const T *))1508 bool ON_ClassArray<T>::QuickSort( int (*compar)(const T*,const T*) )
1509 {
1510 bool rc = false;
1511 if ( m_a && m_count > 0 && compar )
1512 {
1513 if ( m_count > 1 )
1514 ON_qsort( m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar );
1515 rc = true;
1516 }
1517 return rc;
1518 }
1519
1520
1521
1522 template <class T>
HeapSort(int (* compar)(const T *,const T *))1523 bool ON_ObjectArray<T>::HeapSort( int (*compar)(const T*,const T*) )
1524 {
1525 bool rc = false;
1526 // The "this->" in this->m_count and this->m_a
1527 // are needed for gcc 4 to compile.
1528 if ( this->m_a && this->m_count > 0 && compar )
1529 {
1530 if ( this->m_count > 1 )
1531 {
1532 ON_hsort( this->m_a, this->m_count, sizeof(T), (int(*)(const void*,const void*))compar );
1533
1534 // The MemoryRelocate step is required to synch userdata back pointers
1535 // so the user data destructor will work correctly.
1536 int i;
1537 for ( i = 0; i < this->m_count; i++ )
1538 {
1539 this->m_a[i].MemoryRelocate();
1540 }
1541 }
1542 rc = true;
1543 }
1544 return rc;
1545 }
1546
1547 template <class T>
QuickSort(int (* compar)(const T *,const T *))1548 bool ON_ObjectArray<T>::QuickSort( int (*compar)(const T*,const T*) )
1549 {
1550 bool rc = false;
1551 // The "this->" in this->m_count and this->m_a
1552 // are needed for gcc 4 to compile.
1553 if ( this->m_a && this->m_count > 0 && compar )
1554 {
1555 if ( this->m_count > 1 )
1556 {
1557 ON_qsort( this->m_a, this->m_count, sizeof(T), (int(*)(const void*,const void*))compar );
1558
1559 // The MemoryRelocate step is required to synch userdata back pointers
1560 // so the user data destructor will work correctly.
1561 int i;
1562 for ( i = 0; i < this->m_count; i++ )
1563 {
1564 this->m_a[i].MemoryRelocate();
1565 }
1566 }
1567 rc = true;
1568 }
1569 return rc;
1570 }
1571
1572
1573 template <class T>
Sort(ON::sort_algorithm sa,int * index,int (* compar)(const T *,const T *))1574 bool ON_ClassArray<T>::Sort( ON::sort_algorithm sa, int* index, int (*compar)(const T*,const T*) ) const
1575 {
1576 bool rc = false;
1577 if ( m_a && m_count > 0 && compar && index )
1578 {
1579 if ( m_count > 1 )
1580 ON_Sort(sa, index, m_a, m_count, sizeof(T), (int(*)(const void*,const void*))compar );
1581 else if ( m_count == 1 )
1582 index[0] = 0;
1583 rc = true;
1584 }
1585 return rc;
1586 }
1587
1588 template <class T>
Sort(ON::sort_algorithm sa,int * index,int (* compar)(const T *,const T *,void *),void * p)1589 bool ON_ClassArray<T>::Sort( ON::sort_algorithm sa, int* index, int (*compar)(const T*,const T*,void*),void* p ) const
1590 {
1591 bool rc = false;
1592 if ( m_a && m_count > 0 && compar && index )
1593 {
1594 if ( m_count > 1 )
1595 ON_Sort(sa, index, m_a, m_count, sizeof(T), (int(*)(const void*,const void*,void*))compar, p );
1596 else if ( m_count == 1 )
1597 index[0] = 0;
1598 rc = true;
1599 }
1600 return rc;
1601 }
1602
1603 template <class T>
Permute(const int * index)1604 bool ON_ClassArray<T>::Permute( const int* index )
1605 {
1606 bool rc = false;
1607 if ( m_a && m_count > 0 && index )
1608 {
1609 int i;
1610 T* buffer = (T*)onmalloc(m_count*sizeof(buffer[0]));
1611 memcpy( buffer, m_a, m_count*sizeof(T) );
1612 for (i = 0; i < m_count; i++ )
1613 memcpy( m_a+i, buffer+index[i], sizeof(T) ); // must use memcopy and not operator=
1614 onfree(buffer);
1615 rc = true;
1616 }
1617 return rc;
1618 }
1619
1620 template <class T>
Zero()1621 void ON_ClassArray<T>::Zero()
1622 {
1623 int i;
1624 if ( m_a && m_capacity > 0 ) {
1625 for ( i = m_capacity-1; i >= 0; i-- ) {
1626 DestroyElement(m_a[i]);
1627 // This call to memset is ok even when T has a vtable
1628 // because in-place construction is used later.
1629 memset( (void*)(&m_a[i]), 0, sizeof(T) );
1630 ConstructDefaultElement(&m_a[i]);
1631 }
1632 }
1633 }
1634
1635 // memory managment ////////////////////////////////////////////////////
1636
1637 template <class T>
Reserve(int newcap)1638 void ON_ClassArray<T>::Reserve( int newcap )
1639 {
1640 if( m_capacity < newcap )
1641 SetCapacity( newcap );
1642 }
1643
1644 template <class T>
Shrink()1645 void ON_ClassArray<T>::Shrink()
1646 {
1647 SetCapacity( m_count );
1648 }
1649
1650 template <class T>
Destroy()1651 void ON_ClassArray<T>::Destroy()
1652 {
1653 SetCapacity( 0 );
1654 }
1655
1656 // low level memory managment //////////////////////////////////////////
1657
1658 template <class T>
SetCount(int count)1659 void ON_ClassArray<T>::SetCount( int count )
1660 {
1661 if ( count >= 0 && count <= m_capacity )
1662 m_count = count;
1663 }
1664
1665 template <class T>
SetCapacity(int capacity)1666 void ON_ClassArray<T>::SetCapacity( int capacity )
1667 {
1668 // uses "placement" for class construction/destruction
1669 int i;
1670 if ( capacity < 1 ) {
1671 if ( m_a ) {
1672 for ( i = m_capacity-1; i >= 0; i-- ) {
1673 DestroyElement(m_a[i]);
1674 }
1675 Realloc(m_a,0);
1676 m_a = 0;
1677 }
1678 m_count = 0;
1679 m_capacity = 0;
1680 }
1681 else if ( m_capacity < capacity ) {
1682 // growing
1683 m_a = Realloc( m_a, capacity );
1684 // initialize new elements with default constructor
1685 if ( 0 != m_a )
1686 {
1687 // even when m_a is an array of classes with vtable pointers,
1688 // this call to memset(..., 0, ...) is what I want to do
1689 // because in-place construction will be used when needed
1690 // on this memory.
1691 memset( (void*)(m_a + m_capacity), 0, (capacity-m_capacity)*sizeof(T) );
1692 for ( i = m_capacity; i < capacity; i++ ) {
1693 ConstructDefaultElement(&m_a[i]);
1694 }
1695 m_capacity = capacity;
1696 }
1697 else
1698 {
1699 // memory allocation failed
1700 m_capacity = 0;
1701 m_count = 0;
1702 }
1703 }
1704 else if ( m_capacity > capacity ) {
1705 // shrinking
1706 for ( i = m_capacity-1; i >= capacity; i-- ) {
1707 DestroyElement(m_a[i]);
1708 }
1709 if ( m_count > capacity )
1710 m_count = capacity;
1711 m_capacity = capacity;
1712 m_a = Realloc( m_a, capacity );
1713 if ( 0 == m_a )
1714 {
1715 // memory allocation failed
1716 m_capacity = 0;
1717 m_count = 0;
1718 }
1719 }
1720 }
1721
1722 /////////////////////////////////////////////////////////////////////////////////////
1723 /////////////////////////////////////////////////////////////////////////////////////
1724 /////////////////////////////////////////////////////////////////////////////////////
1725
1726 template< class T>
1727 static
ON_CompareIncreasing(const T * a,const T * b)1728 int ON_CompareIncreasing( const T* a, const T* b)
1729 {
1730 if( *a < *b )
1731 return -1;
1732 if( *b < *a )
1733 return 1;
1734 return 0;
1735 }
1736
1737 template< class T>
1738 static
ON_CompareDecreasing(const T * a,const T * b)1739 int ON_CompareDecreasing( const T* a, const T* b)
1740 {
1741 if( *b < *a )
1742 return -1;
1743 if( *a < *b )
1744 return 1;
1745 return 0;
1746 }
1747
1748 #if defined(ON_COMPILER_MSC)
1749 #pragma warning(pop)
1750 #endif
1751
1752 #endif
1753