1 /****************************************************************************
2 ** $Id: qt/qgarray.cpp 3.3.8 edited Jan 11 14:38 $
3 **
4 ** Implementation of QGArray class
5 **
6 ** Created : 930906
7 **
8 ** Copyright (C) 1992-2007 Trolltech ASA. All rights reserved.
9 **
10 ** This file is part of the tools module of the Qt GUI Toolkit.
11 **
12 ** This file may be distributed under the terms of the Q Public License
13 ** as defined by Trolltech ASA of Norway and appearing in the file
14 ** LICENSE.QPL included in the packaging of this file.
15 **
16 ** This file may be distributed and/or modified under the terms of the
17 ** GNU General Public License version 2 as published by the Free Software
18 ** Foundation and appearing in the file LICENSE.GPL included in the
19 ** packaging of this file.
20 **
21 ** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
22 ** licenses may use this file in accordance with the Qt Commercial License
23 ** Agreement provided with the Software.
24 **
25 ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
26 ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
27 **
28 ** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
29 ** information about Qt Commercial License Agreements.
30 ** See http://www.trolltech.com/qpl/ for QPL licensing information.
31 ** See http://www.trolltech.com/gpl/ for GPL licensing information.
32 **
33 ** Contact info@trolltech.com if any conditions of this licensing are
34 ** not clear to you.
35 **
36 **********************************************************************/
37
38 #include "qglobal.h"
39 #if defined(Q_CC_BOR)
40 // needed for qsort() because of a std namespace problem on Borland
41 # include "qplatformdefs.h"
42 #elif defined(Q_WS_WIN)
43 // needed for bsearch on some platforms
44 # include "qt_windows.h"
45 #endif
46
47 #define QGARRAY_CPP
48 #include "qgarray.h"
49 #include <stdlib.h>
50 #include <string.h>
51
52 #ifdef QT_THREAD_SUPPORT
53 # include <private/qmutexpool_p.h>
54 #endif // QT_THREAD_SUPPORT
55
56 /*
57 If USE_MALLOC isn't defined, we use new[] and delete[] to allocate
58 memory. The documentation for QMemArray<T>::assign() explicitly
59 mentions that the array is freed using free(), so don't mess around
60 with USE_MALLOC unless you know what you're doing.
61 */
62 #define USE_MALLOC
63
64 #undef NEW
65 #undef DELETE
66
67 #if defined(USE_MALLOC)
68 #define NEW(type,size) ((type*)malloc(size*sizeof(type)))
69 #define DELETE(array) (free((char*)array))
70 #else
71 #define NEW(type,size) (new type[size])
72 #define DELETE(array) (delete[] array)
73 #define DONT_USE_REALLOC // comment to use realloc()
74 #endif
75
76 /*!
77 \class QShared qshared.h
78 \reentrant
79 \ingroup shared
80 \brief The QShared class is used internally for implementing shared classes.
81
82 \internal
83
84 It only contains a reference count and member functions to increment and
85 decrement it.
86
87 Shared classes normally have internal classes that inherit QShared and
88 add the shared data.
89
90 \sa \link shclass.html Shared Classes\endlink
91 */
92
93 /*!
94 \class QGArray qgarray.h
95 \reentrant
96 \ingroup shared
97 \ingroup collection
98 \brief The QGArray class is an internal class for implementing the QMemArray class.
99
100 \internal
101
102 QGArray is a strictly internal class that acts as base class for the
103 QMemArray template array.
104
105 It contains an array of bytes and has no notion of an array element.
106 */
107
108
109 /*!
110 Constructs a null array.
111 */
112
QGArray()113 QGArray::QGArray()
114 {
115 shd = newData();
116 Q_CHECK_PTR( shd );
117 }
118
119 /*!
120 Dummy constructor; does not allocate any data.
121
122 This constructor does not initialize any array data so subclasses
123 must do it. The intention is to make the code more efficient.
124 */
125
QGArray(int,int)126 QGArray::QGArray( int, int )
127 {
128 }
129
130 /*!
131 Constructs an array with room for \a size bytes.
132 */
133
QGArray(int size)134 QGArray::QGArray( int size )
135 {
136 if ( size < 0 ) {
137 #if defined(QT_CHECK_RANGE)
138 qWarning( "QGArray: Cannot allocate array with negative length" );
139 #endif
140 size = 0;
141 }
142 shd = newData();
143 Q_CHECK_PTR( shd );
144 if ( size == 0 ) // zero length
145 return;
146 shd->data = NEW(char,size);
147 Q_CHECK_PTR( shd->data );
148 shd->len =
149 #ifdef QT_QGARRAY_SPEED_OPTIM
150 shd->maxl =
151 #endif
152 size;
153 }
154
155 /*!
156 Constructs a shallow copy of \a a.
157 */
158
QGArray(const QGArray & a)159 QGArray::QGArray( const QGArray &a )
160 {
161 shd = a.shd;
162 shd->ref();
163 }
164
165 /*!
166 Dereferences the array data and deletes it if this was the last
167 reference.
168 */
169
~QGArray()170 QGArray::~QGArray()
171 {
172 if ( shd && shd->deref() ) { // delete when last reference
173 if ( shd->data ) // is lost
174 DELETE(shd->data);
175 deleteData( shd );
176 shd = 0;
177 }
178 }
179
180
181 /*!
182 \fn QGArray &QGArray::operator=( const QGArray &a )
183
184 Assigns a shallow copy of \a a to this array and returns a reference to
185 this array. Equivalent to assign().
186 */
187
188 /*!
189 \fn void QGArray::detach()
190
191 Detaches this array from shared array data.
192 */
193
194 /*!
195 \fn char *QGArray::data() const
196
197 Returns a pointer to the actual array data.
198 */
199
200 /*!
201 \fn uint QGArray::nrefs() const
202
203 Returns the reference count.
204 */
205
206 /*!
207 \fn uint QGArray::size() const
208
209 Returns the size of the array, in bytes.
210 */
211
212
213 /*!
214 Returns TRUE if this array is equal to \a a, otherwise FALSE.
215 The comparison is bitwise, of course.
216 */
217
isEqual(const QGArray & a) const218 bool QGArray::isEqual( const QGArray &a ) const
219 {
220 if ( size() != a.size() ) // different size
221 return FALSE;
222 if ( data() == a.data() ) // has same data
223 return TRUE;
224 return (size() ? memcmp( data(), a.data(), size() ) : 0) == 0;
225 }
226
227
228 /*!
229 Resizes the array to \a newsize bytes. \a optim is either
230 \c MemOptim (the default) or \c SpeedOptim.
231
232 <b>Note:</b> \c SpeedOptim is only available if Qt is built in a
233 particular configuration. By default, \c SpeedOptim is not available
234 for general use.
235 */
resize(uint newsize,Optimization optim)236 bool QGArray::resize( uint newsize, Optimization optim )
237 {
238 #ifndef QT_QGARRAY_SPEED_OPTIM
239 Q_UNUSED(optim);
240 #endif
241
242 if ( newsize == shd->len
243 #ifdef QT_QGARRAY_SPEED_OPTIM
244 && newsize == shd->maxl
245 #endif
246 ) // nothing to do
247 return TRUE;
248 if ( newsize == 0 ) { // remove array
249 if ( shd->data )
250 DELETE(shd->data);
251 shd->data = 0;
252 shd->len = 0;
253 #ifdef QT_QGARRAY_SPEED_OPTIM
254 shd->maxl = 0;
255 #endif
256 return TRUE;
257 }
258
259 uint newmaxl = newsize;
260 #ifdef QT_QGARRAY_SPEED_OPTIM
261 if ( optim == SpeedOptim ) {
262 if ( newsize <= shd->maxl &&
263 ( newsize * 4 > shd->maxl || shd->maxl <= 4 ) ) {
264 shd->len = newsize;
265 return TRUE;
266 }
267 newmaxl = 4;
268 while ( newmaxl < newsize )
269 newmaxl *= 2;
270 // try to spare some memory
271 if ( newmaxl >= 1024 * 1024 && newsize <= newmaxl - (newmaxl >> 2) )
272 newmaxl -= newmaxl >> 2;
273 }
274 shd->maxl = newmaxl;
275 #endif
276
277 if ( shd->data ) { // existing data
278 #if defined(DONT_USE_REALLOC)
279 char *newdata = NEW(char,newsize); // manual realloc
280 memcpy( newdata, shd->data, QMIN(shd->len,newmaxl) );
281 DELETE(shd->data);
282 shd->data = newdata;
283 #else
284 shd->data = (char *)realloc( shd->data, newmaxl );
285 #endif
286 } else {
287 shd->data = NEW(char,newmaxl);
288 }
289 if ( !shd->data ) // no memory
290 return FALSE;
291 shd->len = newsize;
292 return TRUE;
293 }
294
295 /*!\overload
296 */
resize(uint newsize)297 bool QGArray::resize( uint newsize )
298 {
299 return resize( newsize, MemOptim );
300 }
301
302
303 /*!
304 Fills the array with the repeated occurrences of \a d, which is
305 \a sz bytes long.
306 If \a len is specified as different from -1, then the array will be
307 resized to \a len*sz before it is filled.
308
309 Returns TRUE if successful, or FALSE if the memory cannot be allocated
310 (only when \a len != -1).
311
312 \sa resize()
313 */
314
fill(const char * d,int len,uint sz)315 bool QGArray::fill( const char *d, int len, uint sz )
316 {
317 if ( len < 0 )
318 len = shd->len/sz; // default: use array length
319 else if ( !resize( len*sz ) )
320 return FALSE;
321 if ( sz == 1 ) // 8 bit elements
322 memset( data(), *d, len );
323 else if ( sz == 4 ) { // 32 bit elements
324 register Q_INT32 *x = (Q_INT32*)data();
325 Q_INT32 v = *((Q_INT32*)d);
326 while ( len-- )
327 *x++ = v;
328 } else if ( sz == 2 ) { // 16 bit elements
329 register Q_INT16 *x = (Q_INT16*)data();
330 Q_INT16 v = *((Q_INT16*)d);
331 while ( len-- )
332 *x++ = v;
333 } else { // any other size elements
334 register char *x = data();
335 while ( len-- ) { // more complicated
336 memcpy( x, d, sz );
337 x += sz;
338 }
339 }
340 return TRUE;
341 }
342
343 /*!
344 \overload
345 Shallow copy. Dereference the current array and references the data
346 contained in \a a instead. Returns a reference to this array.
347 \sa operator=()
348 */
349
assign(const QGArray & a)350 QGArray &QGArray::assign( const QGArray &a )
351 {
352 a.shd->ref(); // avoid 'a = a'
353 if ( shd->deref() ) { // delete when last reference
354 if ( shd->data ) // is lost
355 DELETE(shd->data);
356 deleteData( shd );
357 }
358 shd = a.shd;
359 return *this;
360 }
361
362 /*!
363 Shallow copy. Dereference the current array and references the
364 array data \a d, which contains \a len bytes.
365 Returns a reference to this array.
366
367 Do not delete \a d later, because QGArray takes care of that.
368 */
369
assign(const char * d,uint len)370 QGArray &QGArray::assign( const char *d, uint len )
371 {
372 if ( shd->count > 1 ) { // disconnect this
373 shd->count--;
374 shd = newData();
375 Q_CHECK_PTR( shd );
376 } else {
377 if ( shd->data )
378 DELETE(shd->data);
379 }
380 shd->data = (char *)d;
381 shd->len =
382 #ifdef QT_QGARRAY_SPEED_OPTIM
383 shd->maxl =
384 #endif
385 len;
386 return *this;
387 }
388
389 /*!
390 Deep copy. Dereference the current array and obtains a copy of the data
391 contained in \a a instead. Returns a reference to this array.
392 \sa assign(), operator=()
393 */
394
duplicate(const QGArray & a)395 QGArray &QGArray::duplicate( const QGArray &a )
396 {
397 if ( a.shd == shd ) { // a.duplicate(a) !
398 if ( shd->count > 1 ) {
399 shd->count--;
400 register array_data *n = newData();
401 Q_CHECK_PTR( n );
402 if ( (n->len=shd->len) ) {
403 n->data = NEW(char,n->len);
404 Q_CHECK_PTR( n->data );
405 if ( n->data )
406 memcpy( n->data, shd->data, n->len );
407 } else {
408 n->data = 0;
409 }
410 shd = n;
411 }
412 return *this;
413 }
414 char *oldptr = 0;
415 if ( shd->count > 1 ) { // disconnect this
416 shd->count--;
417 shd = newData();
418 Q_CHECK_PTR( shd );
419 } else { // delete after copy was made
420 oldptr = shd->data;
421 }
422 if ( a.shd->len ) { // duplicate data
423 shd->data = NEW(char,a.shd->len);
424 Q_CHECK_PTR( shd->data );
425 if ( shd->data )
426 memcpy( shd->data, a.shd->data, a.shd->len );
427 } else {
428 shd->data = 0;
429 }
430 shd->len =
431 #ifdef QT_QGARRAY_SPEED_OPTIM
432 shd->maxl =
433 #endif
434 a.shd->len;
435 if ( oldptr )
436 DELETE(oldptr);
437 return *this;
438 }
439
440 /*!
441 \overload
442 Deep copy. Dereferences the current array and obtains a copy of
443 \a len characters from array data \a d instead. Returns a reference
444 to this array.
445 \sa assign(), operator=()
446 */
447
duplicate(const char * d,uint len)448 QGArray &QGArray::duplicate( const char *d, uint len )
449 {
450 char *data;
451 if ( d == 0 || len == 0 ) {
452 data = 0;
453 len = 0;
454 } else {
455 if ( shd->count == 1 && shd->len == len ) {
456 if ( shd->data != d ) // avoid self-assignment
457 memcpy( shd->data, d, len ); // use same buffer
458 return *this;
459 }
460 data = NEW(char,len);
461 Q_CHECK_PTR( data );
462 memcpy( data, d, len );
463 }
464 if ( shd->count > 1 ) { // detach
465 shd->count--;
466 shd = newData();
467 Q_CHECK_PTR( shd );
468 } else { // just a single reference
469 if ( shd->data )
470 DELETE(shd->data);
471 }
472 shd->data = data;
473 shd->len =
474 #ifdef QT_QGARRAY_SPEED_OPTIM
475 shd->maxl =
476 #endif
477 len;
478 return *this;
479 }
480
481 /*!
482 Resizes this array to \a len bytes and copies the \a len bytes at
483 address \a d into it.
484
485 \warning This function disregards the reference count mechanism. If
486 other QGArrays reference the same data as this, all will be updated.
487 */
488
store(const char * d,uint len)489 void QGArray::store( const char *d, uint len )
490 { // store, but not deref
491 resize( len );
492 memcpy( shd->data, d, len );
493 }
494
495
496 /*!
497 \fn array_data *QGArray::sharedBlock() const
498
499 Returns a pointer to the shared array block.
500
501 \warning
502
503 Do not use this function. Using it is begging for trouble. We dare
504 not remove it, for fear of breaking code, but we \e strongly
505 discourage new use of it.
506 */
507
508 /*!
509 \fn void QGArray::setSharedBlock( array_data *p )
510
511 Sets the shared array block to \a p.
512
513 \warning
514
515 Do not use this function. Using it is begging for trouble. We dare
516 not remove it, for fear of breaking code, but we \e strongly
517 discourage new use of it.
518 */
519
520
521 /*!
522 Sets raw data and returns a reference to the array.
523
524 Dereferences the current array and sets the new array data to \a d and
525 the new array size to \a len. Do not attempt to resize or re-assign the
526 array data when raw data has been set.
527 Call resetRawData(d,len) to reset the array.
528
529 Setting raw data is useful because it sets QMemArray data without
530 allocating memory or copying data.
531
532 Example of intended use:
533 \code
534 static uchar bindata[] = { 231, 1, 44, ... };
535 QByteArray a;
536 a.setRawData( bindata, sizeof(bindata) ); // a points to bindata
537 QDataStream s( a, IO_ReadOnly ); // open on a's data
538 s >> <something>; // read raw bindata
539 s.close();
540 a.resetRawData( bindata, sizeof(bindata) ); // finished
541 \endcode
542
543 Example of misuse (do not do this):
544 \code
545 static uchar bindata[] = { 231, 1, 44, ... };
546 QByteArray a, b;
547 a.setRawData( bindata, sizeof(bindata) ); // a points to bindata
548 a.resize( 8 ); // will crash
549 b = a; // will crash
550 a[2] = 123; // might crash
551 // forget to resetRawData - will crash
552 \endcode
553
554 \warning If you do not call resetRawData(), QGArray will attempt to
555 deallocate or reallocate the raw data, which might not be too good.
556 Be careful.
557 */
558
setRawData(const char * d,uint len)559 QGArray &QGArray::setRawData( const char *d, uint len )
560 {
561 duplicate( 0, 0 ); // set null data
562 shd->data = (char *)d;
563 shd->len = len;
564 return *this;
565 }
566
567 /*!
568 Resets raw data.
569
570 The arguments must be the data, \a d, and length \a len, that were
571 passed to setRawData(). This is for consistency checking.
572 */
573
resetRawData(const char * d,uint len)574 void QGArray::resetRawData( const char *d, uint len )
575 {
576 if ( d != shd->data || len != shd->len ) {
577 #if defined(QT_CHECK_STATE)
578 qWarning( "QGArray::resetRawData: Inconsistent arguments" );
579 #endif
580 return;
581 }
582 shd->data = 0;
583 shd->len = 0;
584 }
585
586
587 /*!
588 Finds the first occurrence of \a d in the array from position \a index,
589 where \a sz is the size of the \a d element.
590
591 Note that \a index is given in units of \a sz, not bytes.
592
593 This function only compares whole cells, not bytes.
594 */
595
find(const char * d,uint index,uint sz) const596 int QGArray::find( const char *d, uint index, uint sz ) const
597 {
598 index *= sz;
599 if ( index >= shd->len ) {
600 #if defined(QT_CHECK_RANGE)
601 qWarning( "QGArray::find: Index %d out of range", index/sz );
602 #endif
603 return -1;
604 }
605 register uint i;
606 uint ii;
607 switch ( sz ) {
608 case 1: { // 8 bit elements
609 register char *x = data() + index;
610 char v = *d;
611 for ( i=index; i<shd->len; i++ ) {
612 if ( *x++ == v )
613 break;
614 }
615 ii = i;
616 }
617 break;
618 case 2: { // 16 bit elements
619 register Q_INT16 *x = (Q_INT16*)(data() + index);
620 Q_INT16 v = *((Q_INT16*)d);
621 for ( i=index; i<shd->len; i+=2 ) {
622 if ( *x++ == v )
623 break;
624 }
625 ii = i/2;
626 }
627 break;
628 case 4: { // 32 bit elements
629 register Q_INT32 *x = (Q_INT32*)(data() + index);
630 Q_INT32 v = *((Q_INT32*)d);
631 for ( i=index; i<shd->len; i+=4 ) {
632 if ( *x++ == v )
633 break;
634 }
635 ii = i/4;
636 }
637 break;
638 default: { // any size elements
639 for ( i=index; i<shd->len; i+=sz ) {
640 if ( memcmp( d, &shd->data[i], sz ) == 0 )
641 break;
642 }
643 ii = i/sz;
644 }
645 break;
646 }
647 return i<shd->len ? (int)ii : -1;
648 }
649
650 /*!
651 Returns the number of occurrences of \a d in the array, where \a sz is
652 the size of the \a d element.
653
654 This function only compares whole cells, not bytes.
655 */
656
contains(const char * d,uint sz) const657 int QGArray::contains( const char *d, uint sz ) const
658 {
659 register uint i = shd->len;
660 int count = 0;
661 switch ( sz ) {
662 case 1: { // 8 bit elements
663 register char *x = data();
664 char v = *d;
665 while ( i-- ) {
666 if ( *x++ == v )
667 count++;
668 }
669 }
670 break;
671 case 2: { // 16 bit elements
672 register Q_INT16 *x = (Q_INT16*)data();
673 Q_INT16 v = *((Q_INT16*)d);
674 i /= 2;
675 while ( i-- ) {
676 if ( *x++ == v )
677 count++;
678 }
679 }
680 break;
681 case 4: { // 32 bit elements
682 register Q_INT32 *x = (Q_INT32*)data();
683 Q_INT32 v = *((Q_INT32*)d);
684 i /= 4;
685 while ( i-- ) {
686 if ( *x++ == v )
687 count++;
688 }
689 }
690 break;
691 default: { // any size elements
692 for ( i=0; i<shd->len; i+=sz ) {
693 if ( memcmp(d, &shd->data[i], sz) == 0 )
694 count++;
695 }
696 }
697 break;
698 }
699 return count;
700 }
701
702 static int cmp_item_size = 0;
703
704 #if defined(Q_C_CALLBACKS)
705 extern "C" {
706 #endif
707
708 #ifdef Q_OS_TEMP
cmp_arr(const void * n1,const void * n2)709 static int __cdecl cmp_arr( const void *n1, const void *n2 )
710 #else
711 static int cmp_arr( const void *n1, const void *n2 )
712 #endif
713 {
714 return ( n1 && n2 ) ? memcmp( n1, n2, cmp_item_size )
715 : ( n1 ? 1 : ( n2 ? -1 : 0 ) );
716 // ### Qt 3.0: Add a virtual compareItems() method and call that instead
717 }
718
719 #if defined(Q_C_CALLBACKS)
720 }
721 #endif
722
723 /*!
724 Sorts the first \a sz items of the array.
725 */
726
sort(uint sz)727 void QGArray::sort( uint sz )
728 {
729 int numItems = size() / sz;
730 if ( numItems < 2 )
731 return;
732
733 #ifdef QT_THREAD_SUPPORT
734 QMutexLocker locker( qt_global_mutexpool ?
735 qt_global_mutexpool->get( &cmp_item_size ) : 0 );
736 #endif // QT_THREAD_SUPPORT
737
738 cmp_item_size = sz;
739 qsort( shd->data, numItems, sz, cmp_arr );
740 }
741
742 /*!
743 Binary search; assumes that \a d is a sorted array of size \a sz.
744 */
745
bsearch(const char * d,uint sz) const746 int QGArray::bsearch( const char *d, uint sz ) const
747 {
748 int numItems = size() / sz;
749 if ( !numItems )
750 return -1;
751
752 #ifdef QT_THREAD_SUPPORT
753 QMutexLocker locker( qt_global_mutexpool ?
754 qt_global_mutexpool->get( &cmp_item_size ) : 0 );
755 #endif // QT_THREAD_SUPPORT
756
757 cmp_item_size = sz;
758 char* r = (char*)::bsearch( d, shd->data, numItems, sz, cmp_arr );
759 if ( !r )
760 return -1;
761 while( (r >= shd->data + sz) && (cmp_arr( r - sz, d ) == 0) )
762 r -= sz; // search to first of equal elements; bsearch is undef
763 return (int)(( r - shd->data ) / sz);
764 }
765
766
767 /*!
768 \fn char *QGArray::at( uint index ) const
769
770 Returns a pointer to the byte at offset \a index in the array.
771 */
772
773 /*!
774 Expand the array if necessary, and copies (the first part of) its
775 contents from the \a index * \a sz bytes at \a d.
776
777 Returns TRUE if the operation succeeds, FALSE if it runs out of
778 memory.
779
780 \warning This function disregards the reference count mechanism. If
781 other QGArrays reference the same data as this, all will be changed.
782 */
783
setExpand(uint index,const char * d,uint sz)784 bool QGArray::setExpand( uint index, const char *d, uint sz )
785 {
786 index *= sz;
787 if ( index >= shd->len ) {
788 if ( !resize( index+sz ) ) // no memory
789 return FALSE;
790 }
791 memcpy( data() + index, d, sz );
792 return TRUE;
793 }
794
795
796 /*!
797 Prints a warning message if at() or [] is given a bad index.
798 */
799
msg_index(uint index)800 void QGArray::msg_index( uint index )
801 {
802 #if defined(QT_CHECK_RANGE)
803 qWarning( "QGArray::at: Absolute index %d out of range", index );
804 #else
805 Q_UNUSED( index )
806 #endif
807 }
808
809
810 /*!
811 Returns a new shared array block.
812 */
813
newData()814 QGArray::array_data * QGArray::newData()
815 {
816 return new array_data;
817 }
818
819
820 /*!
821 Deletes the shared array block \a p.
822 */
823
deleteData(array_data * p)824 void QGArray::deleteData( array_data *p )
825 {
826 delete p;
827 }
828