1 /****************************************************************************
4 ** Implementation of QGArray class
8 ** Copyright (C) 1992-2000 Trolltech AS. All rights reserved.
10 ** This file is part of the tools module of the Qt GUI Toolkit.
12 ** This file may be distributed under the terms of the Q Public License
13 ** as defined by Trolltech AS of Norway and appearing in the file
14 ** LICENSE.QPL included in the packaging of this file.
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.
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.
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.
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.
33 ** Contact info@trolltech.com if any conditions of this licensing are
36 **********************************************************************/
43 #define USE_MALLOC // comment to use new/delete
48 #if defined(USE_MALLOC)
49 #define NEW(type,size) ((type*)malloc(size*sizeof(type)))
50 #define DELETE(array) (free((char*)array))
52 #define NEW(type,size) (new type[size])
53 #define DELETE(array) (delete[] array)
54 #define DONT_USE_REALLOC // comment to use realloc()
60 \class QShared qshared.h
61 \brief The QShared struct is internally used for implementing shared classes.
63 It only contains a reference count and member functions to increment and
66 Shared classes normally have internal classes that inherit QShared and
69 \sa \link shclass.html Shared Classes\endlink
74 \class QGArray qgarray.h
75 \brief The QGArray class is an internal class for implementing the QArray class.
77 QGArray is a strictly internal class that acts as base class for the
78 QArray template array.
80 It contains an array of bytes and has no notion of an array element.
86 Constructs a null array.
97 Dummy constructor; does not allocate any data.
99 This constructor does not initialize any array data so subclasses
100 must do it. The intention is to make the code more efficient.
103 QGArray::QGArray( int, int )
109 Constructs an array with room for \e size bytes.
112 QGArray::QGArray( int size )
115 #if defined(CHECK_RANGE)
116 qWarning( "QGArray: Cannot allocate array with negative length" );
122 if ( size == 0 ) // zero length
124 shd->data = NEW(char,size);
125 CHECK_PTR( shd->data );
131 Constructs a shallow copy of \e a.
134 QGArray::QGArray( const QGArray &a )
142 Dereferences the array data and deletes it if this was the last
148 if ( shd && shd->deref() ) { // delete when last reference
149 if ( shd->data ) // is lost
157 \fn QGArray &QGArray::operator=( const QGArray &a )
159 Assigns a shallow copy of \e a to this array and returns a reference to
160 this array. Equivalent to assign().
164 \fn void QGArray::detach()
166 Detaches this array from shared array data.
170 \fn char *QGArray::data() const
172 Returns a pointer to the actual array data.
176 \fn uint QGArray::nrefs() const
178 Returns the reference count.
182 \fn uint QGArray::size() const
184 Returns the size of the array, in bytes.
190 Returns TRUE if this array is equal to \e a, otherwise FALSE.
191 The comparison is bitwise, of course.
194 bool QGArray::isEqual( const QGArray &a ) const
196 if ( size() != a.size() ) // different size
198 if ( data() == a.data() ) // has same data
200 return (size() ? memcmp( data(), a.data(), size() ) : 0) == 0;
206 Resizes the array to \e newsize bytes.
209 bool QGArray::resize( uint newsize )
211 if ( newsize == shd->len ) // nothing to do
213 if ( newsize == 0 ) { // remove array
217 if ( shd->data ) { // existing data
218 #if defined(DONT_USE_REALLOC)
219 char *newdata = NEW(char,newsize); // manual realloc
220 memcpy( newdata, shd->data, QMIN(shd->len,newsize) );
224 shd->data = (char *)realloc( shd->data, newsize );
227 shd->data = NEW(char,newsize);
229 CHECK_PTR( shd->data );
230 if ( !shd->data ) // no memory
238 Fills the array with the repeated occurrences of \e d, which is
240 If \e len is specified as different from -1, then the array will be
241 resized to \e len*sz before it is filled.
243 Returns TRUE if successful, or FALSE if the memory cannot be allocated
244 (only when \e len != -1).
249 bool QGArray::fill( const char *d, int len, uint sz )
252 len = shd->len/sz; // default: use array length
253 else if ( !resize( len*sz ) )
255 if ( sz == 1 ) // 8 bit elements
256 memset( data(), *d, len );
257 else if ( sz == 4 ) { // 32 bit elements
258 register Q_INT32 *x = (Q_INT32*)data();
259 Q_INT32 v = *((Q_INT32*)d);
262 } else if ( sz == 2 ) { // 16 bit elements
263 register Q_INT16 *x = (Q_INT16*)data();
264 Q_INT16 v = *((Q_INT16*)d);
267 } else { // any other size elements
268 register char *x = data();
269 while ( len-- ) { // more complicated
279 Shallow copy. Dereference the current array and references the data
280 contained in \e a instead. Returns a reference to this array.
284 QGArray &QGArray::assign( const QGArray &a )
286 a.shd->ref(); // avoid 'a = a'
287 if ( shd->deref() ) { // delete when last reference
288 if ( shd->data ) // is lost
298 Shallow copy. Dereference the current array and references the
299 array data \e d, which contains \e len bytes.
300 Returns a reference to this array.
302 Do not delete \e d later, because QGArray takes care of that.
305 QGArray &QGArray::assign( const char *d, uint len )
307 if ( shd->count > 1 ) { // disconnect this
315 shd->data = (char *)d;
322 Deep copy. Dereference the current array and obtains a copy of the data
323 contained in \e a instead. Returns a reference to this array.
324 \sa assign(), operator=()
327 QGArray &QGArray::duplicate( const QGArray &a )
329 if ( a.shd == shd ) { // a.duplicate(a) !
330 if ( shd->count > 1 ) {
332 register array_data *n = newData();
334 if ( (n->len=shd->len) ) {
335 n->data = NEW(char,n->len);
336 CHECK_PTR( n->data );
338 memcpy( n->data, shd->data, n->len );
347 if ( shd->count > 1 ) { // disconnect this
351 } else { // delete after copy was made
354 if ( a.shd->len ) { // duplicate data
355 shd->data = NEW(char,a.shd->len);
356 CHECK_PTR( shd->data );
358 memcpy( shd->data, a.shd->data, a.shd->len );
362 shd->len = a.shd->len;
370 Deep copy. Dereferences the current array and obtains a copy of the
371 array data \e d instead. Returns a reference to this array.
372 \sa assign(), operator=()
375 QGArray &QGArray::duplicate( const char *d, uint len )
378 if ( d == 0 || len == 0 ) {
382 if ( shd->count == 1 && shd->len == len ) {
383 memcpy( shd->data, d, len ); // use same buffer
386 data = NEW(char,len);
388 memcpy( data, d, len );
390 if ( shd->count > 1 ) { // detach
394 } else { // just a single reference
405 Resizes this array to \e len bytes and copies the \e len bytes at
408 \warning This function disregards the reference count mechanism. If
409 other QGArrays reference the same data as this, all will be updated.
412 void QGArray::store( const char *d, uint len )
413 { // store, but not deref
415 memcpy( shd->data, d, len );
420 \fn array_data *QGArray::sharedBlock() const
422 Returns a pointer to the shared array block.
426 Do not use this function. Using it is begging for trouble. We dare
427 not remove it, for fear of breaking code, but we \e strongly
428 discourage new use of it.
432 \fn void QGArray::setSharedBlock( array_data *p )
434 Sets the shared array block to \e p.
438 Do not use this function. Using it is begging for trouble. We dare
439 not remove it, for fear of breaking code, but we \e strongly
440 discourage new use of it.
446 Sets raw data and returns a reference to the array.
448 Dereferences the current array and sets the new array data to \e d and
449 the new array size to \e len. Do not attempt to resize or re-assign the
450 array data when raw data has been set.
451 Call resetRawData(d,len) to reset the array.
453 Setting raw data is useful because it set QArray data without allocating
454 memory or copying data.
456 Example of intended use:
458 static uchar bindata[] = { 231, 1, 44, ... };
460 a.setRawData( bindata, sizeof(bindata) ); // a points to bindata
461 QDataStream s( a, IO_ReadOnly ); // open on a's data
462 s >> <something>; // read raw bindata
464 a.resetRawData( bindata, sizeof(bindata) ); // finished
467 Example of misuse (do not do this):
469 static uchar bindata[] = { 231, 1, 44, ... };
471 a.setRawData( bindata, sizeof(bindata) ); // a points to bindata
472 a.resize( 8 ); // will crash
474 a[2] = 123; // might crash
475 // forget to resetRawData - will crash
478 \warning If you do not call resetRawData(), QGArray will attempt to
479 deallocate or reallocate the raw data, which might not be too good.
483 QGArray &QGArray::setRawData( const char *d, uint len )
485 duplicate( 0, 0 ); // set null data
486 shd->data = (char *)d;
495 The arguments must be the data and length that were passed to
496 setRawData(). This is for consistency checking.
499 void QGArray::resetRawData( const char *d, uint len )
501 if ( d != shd->data || len != shd->len ) {
502 #if defined(CHECK_STATE)
503 qWarning( "QGArray::resetRawData: Inconsistent arguments" );
514 Finds the first occurrence of \e d in the array from position \e index,
515 where \e sz is the size of the \e d element.
517 Note that \e index is given in units of \e sz, not bytes.
519 This function only compares whole cells, not bytes.
522 int QGArray::find( const char *d, uint index, uint sz ) const
525 if ( index >= shd->len ) {
526 #if defined(CHECK_RANGE)
527 qWarning( "QGArray::find: Index %d out of range", index/sz );
534 case 1: { // 8 bit elements
535 register char *x = data() + index;
537 for ( i=index; i<shd->len; i++ ) {
544 case 2: { // 16 bit elements
545 register Q_INT16 *x = (Q_INT16*)(data() + index);
546 Q_INT16 v = *((Q_INT16*)d);
547 for ( i=index; i<shd->len; i+=2 ) {
554 case 4: { // 32 bit elements
555 register Q_INT32 *x = (Q_INT32*)(data() + index);
556 Q_INT32 v = *((Q_INT32*)d);
557 for ( i=index; i<shd->len; i+=4 ) {
564 default: { // any size elements
565 for ( i=index; i<shd->len; i+=sz ) {
566 if ( memcmp( d, &shd->data[i], sz ) == 0 )
573 return i<shd->len ? (int)ii : -1;
578 Returns the number of occurrences of \e d in the array, where \e sz is
579 the size of the \e d element.
581 This function only compares whole cells, not bytes.
584 int QGArray::contains( const char *d, uint sz ) const
586 register uint i = shd->len;
589 case 1: { // 8 bit elements
590 register char *x = data();
598 case 2: { // 16 bit elements
599 register Q_INT16 *x = (Q_INT16*)data();
600 Q_INT16 v = *((Q_INT16*)d);
608 case 4: { // 32 bit elements
609 register Q_INT32 *x = (Q_INT32*)data();
610 Q_INT32 v = *((Q_INT32*)d);
618 default: { // any size elements
619 for ( i=0; i<shd->len; i+=sz ) {
620 if ( memcmp(d, &shd->data[i], sz) == 0 )
629 static int cmp_item_size = 0;
631 #if defined(Q_C_CALLBACKS)
635 static int cmp_arr( const void *n1, const void *n2 )
637 return ( n1 && n2 ) ? memcmp( n1, n2, cmp_item_size )
638 : (int)((intptr_t)n1 - (intptr_t)n2);
639 // Qt 3.0: Add a virtual compareItems() method and call that instead
642 #if defined(Q_C_CALLBACKS)
652 void QGArray::sort( uint sz )
654 int numItems = size() / sz;
658 qsort( shd->data, numItems, sz, cmp_arr );
664 Binary search; assumes sorted array
667 int QGArray::bsearch( const char *d, uint sz ) const
669 int numItems = size() / sz;
673 char* r = (char*)::bsearch( d, shd->data, numItems, sz, cmp_arr );
676 while( (r >= shd->data + sz) && (cmp_arr( r - sz, d ) == 0) )
677 r -= sz; // search to first of equal elements; bsearch is undef
678 return (int)(( r - shd->data ) / sz);
683 \fn char *QGArray::at( uint index ) const
685 Returns a pointer to the byte at offset \e index in the array.
690 Expand the array if necessary, and copies (the first part of) its
691 contents from the \e index*zx bytes at \e d.
693 Returns TRUE if the operation succeeds, FALSE if it runs out of
696 \warning This function disregards the reference count mechanism. If
697 other QGArrays reference the same data as this, all will be changed.
700 bool QGArray::setExpand( uint index, const char *d, uint sz )
703 if ( index >= shd->len ) {
704 if ( !resize( index+sz ) ) // no memory
707 memcpy( data() + index, d, sz );
714 Prints a warning message if at() or [] is given a bad index.
717 void QGArray::msg_index( uint index )
719 #if defined(CHECK_RANGE)
720 qWarning( "QGArray::at: Absolute index %d out of range", index );
729 Returns a new shared array block.
732 QGArray::array_data * QGArray::newData()
734 return new array_data;
740 Deletes the shared array block.
743 void QGArray::deleteData( array_data *p )