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