qtools/qgarray.cpp

   1 /****************************************************************************
   2 **
   3 **
   4 ** Implementation of QGArray class
   5 **
   6 ** Created : 930906
   7 **
   8 ** Copyright (C) 1992-2000 Trolltech AS.  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 AS 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 #define  QGARRAY_CPP
  39 #include "qgarray.h"
  40 #include "qstring.h"
  41 #include <stdlib.h>
  42
  43 #define USE_MALLOC                              // comment to use new/delete
  44
  45 #undef NEW
  46 #undef DELETE
  47
  48 #if defined(USE_MALLOC)
  49 #define NEW(type,size)  ((type*)malloc(size*sizeof(type)))
  50 #define DELETE(array)   (free((char*)array))
  51 #else
  52 #define NEW(type,size)  (new type[size])
  53 #define DELETE(array)   (delete[] array)
  54 #define DONT_USE_REALLOC                        // comment to use realloc()
  55 #endif
  56
  57
  58 // NOT REVISED
  59 /*!
  60   \class QShared qshared.h
  61   \brief The QShared struct is internally used for implementing shared classes.
  62
  63   It only contains a reference count and member functions to increment and
  64   decrement it.
  65
  66   Shared classes normally have internal classes that inherit QShared and
  67   add the shared data.
  68
  69   \sa \link shclass.html Shared Classes\endlink
  70 */
  71
  72
  73 /*!
  74   \class QGArray qgarray.h
  75   \brief The QGArray class is an internal class for implementing the QArray class.
  76
  77   QGArray is a strictly internal class that acts as base class for the
  78   QArray template array.
  79
  80   It contains an array of bytes and has no notion of an array element.
  81 */
  82
  83
  84 /*!
  85   \internal
  86   Constructs a null array.
  87 */
  88
  89 QGArray::QGArray()
  90 {
  91     shd = newData();
  92     CHECK_PTR( shd );
  93 }
  94
  95 /*!
  96   \internal
  97   Dummy constructor; does not allocate any data.
  98
  99   This constructor does not initialize any array data so subclasses
 100   must do it. The intention is to make the code more efficient.
 101 */
 102
 103 QGArray::QGArray( int, int )
 104 {
 105 }
 106
 107 /*!
 108   \internal
 109   Constructs an array with room for \e size bytes.
 110 */
 111
 112 QGArray::QGArray( int size )
 113 {
 114     if ( size < 0 ) {
 115 #if defined(CHECK_RANGE)
 116         qWarning( "QGArray: Cannot allocate array with negative length" );
 117 #endif
 118         size = 0;
 119     }
 120     shd = newData();
 121     CHECK_PTR( shd );
 122     if ( size == 0 )                            // zero length
 123         return;
 124     shd->data = NEW(char,size);
 125     CHECK_PTR( shd->data );
 126     shd->len = size;
 127 }
 128
 129 /*!
 130   \internal
 131   Constructs a shallow copy of \e a.
 132 */
 133
 134 QGArray::QGArray( const QGArray &a )
 135 {
 136     shd = a.shd;
 137     shd->ref();
 138 }
 139
 140 /*!
 141   \internal
 142   Dereferences the array data and deletes it if this was the last
 143   reference.
 144 */
 145
 146 QGArray::~QGArray()
 147 {
 148     if ( shd && shd->deref() ) {                // delete when last reference
 149         if ( shd->data )                        // is lost
 150             DELETE(shd->data);
 151         deleteData( shd );
 152     }
 153 }
 154
 155
 156 /*!
 157   \fn QGArray &QGArray::operator=( const QGArray &a )
 158   \internal
 159   Assigns a shallow copy of \e a to this array and returns a reference to
 160   this array.  Equivalent to assign().
 161 */
 162
 163 /*!
 164   \fn void QGArray::detach()
 165   \internal
 166   Detaches this array from shared array data.
 167 */
 168
 169 /*!
 170   \fn char *QGArray::data() const
 171   \internal
 172   Returns a pointer to the actual array data.
 173 */
 174
 175 /*!
 176   \fn uint QGArray::nrefs() const
 177   \internal
 178   Returns the reference count.
 179 */
 180
 181 /*!
 182   \fn uint QGArray::size() const
 183   \internal
 184   Returns the size of the array, in bytes.
 185 */
 186
 187
 188 /*!
 189   \internal
 190   Returns TRUE if this array is equal to \e a, otherwise FALSE.
 191   The comparison is bitwise, of course.
 192 */
 193
 194 bool QGArray::isEqual( const QGArray &a ) const
 195 {
 196     if ( size() != a.size() )                   // different size
 197         return FALSE;
 198     if ( data() == a.data() )                   // has same data
 199         return TRUE;
 200     return (size() ? memcmp( data(), a.data(), size() ) : 0) == 0;
 201 }
 202
 203
 204 /*!
 205   \internal
 206   Resizes the array to \e newsize bytes.
 207 */
 208
 209 bool QGArray::resize( uint newsize )
 210 {
 211     if ( newsize == shd->len )                  // nothing to do
 212         return TRUE;
 213     if ( newsize == 0 ) {                       // remove array
 214         duplicate( 0, 0 );
 215         return TRUE;
 216     }
 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) );
 221         DELETE(shd->data);
 222         shd->data = newdata;
 223 #else
 224         shd->data = (char *)realloc( shd->data, newsize );
 225 #endif
 226     } else {
 227         shd->data = NEW(char,newsize);
 228     }
 229     CHECK_PTR( shd->data );
 230     if ( !shd->data )                           // no memory
 231         return FALSE;
 232     shd->len = newsize;
 233     return TRUE;
 234 }
 235
 236 /*!
 237   \internal
 238   Fills the array with the repeated occurrences of \e d, which is
 239   \e sz bytes long.
 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.
 242
 243   Returns TRUE if successful, or FALSE if the memory cannot be allocated
 244   (only when \e len != -1).
 245
 246   \sa resize()
 247 */
 248
 249 bool QGArray::fill( const char *d, int len, uint sz )
 250 {
 251     if ( len < 0 )
 252         len = shd->len/sz;                      // default: use array length
 253     else if ( !resize( len*sz ) )
 254         return FALSE;
 255     if ( sz == 1 )                              // 8 bit elements
 256         memset( data(), *d, len );
 257     else if ( sz == 4 ) {                       // 32 bit elements
 258         Q_INT32 *x = (Q_INT32*)data();
 259         Q_INT32 v = *((Q_INT32*)d);
 260         while ( len-- )
 261             *x++ = v;
 262     } else if ( sz == 2 ) {                     // 16 bit elements
 263         Q_INT16 *x = (Q_INT16*)data();
 264         Q_INT16 v = *((Q_INT16*)d);
 265         while ( len-- )
 266             *x++ = v;
 267     } else {                                    // any other size elements
 268         char *x = data();
 269         while ( len-- ) {                       // more complicated
 270             memcpy( x, d, sz );
 271             x += sz;
 272         }
 273     }
 274     return TRUE;
 275 }
 276
 277 /*!
 278   \internal
 279   Shallow copy. Dereference the current array and references the data
 280   contained in \e a instead. Returns a reference to this array.
 281   \sa operator=()
 282 */
 283
 284 QGArray &QGArray::assign( const QGArray &a )
 285 {
 286     a.shd->ref();                               // avoid 'a = a'
 287     if ( shd->deref() ) {                       // delete when last reference
 288         if ( shd->data )                        // is lost
 289             DELETE(shd->data);
 290         deleteData( shd );
 291     }
 292     shd = a.shd;
 293     return *this;
 294 }
 295
 296 /*!
 297   \internal
 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.
 301
 302   Do not delete \e d later, because QGArray takes care of that.
 303 */
 304
 305 QGArray &QGArray::assign( const char *d, uint len )
 306 {
 307     if ( shd->count > 1 ) {                     // disconnect this
 308         shd->count--;
 309         shd = newData();
 310         CHECK_PTR( shd );
 311     } else {
 312         if ( shd->data )
 313             DELETE(shd->data);
 314     }
 315     shd->data = (char *)d;
 316     shd->len = len;
 317     return *this;
 318 }
 319
 320 /*!
 321   \internal
 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=()
 325 */
 326
 327 QGArray &QGArray::duplicate( const QGArray &a )
 328 {
 329     if ( a.shd == shd ) {                       // a.duplicate(a) !
 330         if ( shd->count > 1 ) {
 331             shd->count--;
 332             array_data *n = newData();
 333             CHECK_PTR( n );
 334             if ( (n->len=shd->len) ) {
 335                 n->data = NEW(char,n->len);
 336                 CHECK_PTR( n->data );
 337                 if ( n->data )
 338                     memcpy( n->data, shd->data, n->len );
 339             } else {
 340                 n->data = 0;
 341             }
 342             shd = n;
 343         }
 344         return *this;
 345     }
 346     char *oldptr = 0;
 347     if ( shd->count > 1 ) {                     // disconnect this
 348         shd->count--;
 349         shd = newData();
 350         CHECK_PTR( shd );
 351     } else {                                    // delete after copy was made
 352         oldptr = shd->data;
 353     }
 354     if ( a.shd->len ) {                         // duplicate data
 355         shd->data = NEW(char,a.shd->len);
 356         CHECK_PTR( shd->data );
 357         if ( shd->data )
 358             memcpy( shd->data, a.shd->data, a.shd->len );
 359     } else {
 360         shd->data = 0;
 361     }
 362     shd->len = a.shd->len;
 363     if ( oldptr )
 364         DELETE(oldptr);
 365     return *this;
 366 }
 367
 368 /*!
 369   \internal
 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=()
 373 */
 374
 375 QGArray &QGArray::duplicate( const char *d, uint len )
 376 {
 377     char *data;
 378     if ( d == 0 || len == 0 ) {
 379         data = 0;
 380         len  = 0;
 381     } else {
 382         if ( shd->count == 1 && shd->len == len ) {
 383             memcpy( shd->data, d, len );        // use same buffer
 384             return *this;
 385         }
 386         data = NEW(char,len);
 387         CHECK_PTR( data );
 388         memcpy( data, d, len );
 389     }
 390     if ( shd->count > 1 ) {                     // detach
 391         shd->count--;
 392         shd = newData();
 393         CHECK_PTR( shd );
 394     } else {                                    // just a single reference
 395         if ( shd->data )
 396             DELETE(shd->data);
 397     }
 398     shd->data = data;
 399     shd->len  = len;
 400     return *this;
 401 }
 402
 403 /*!
 404   \internal
 405   Resizes this array to \e len bytes and copies the \e len bytes at
 406   address \e into it.
 407
 408   \warning This function disregards the reference count mechanism.  If
 409   other QGArrays reference the same data as this, all will be updated.
 410 */
 411
 412 void QGArray::store( const char *d, uint len )
 413 {                                               // store, but not deref
 414     resize( len );
 415     memcpy( shd->data, d, len );
 416 }
 417
 418
 419 /*!
 420   \fn array_data *QGArray::sharedBlock() const
 421   \internal
 422   Returns a pointer to the shared array block.
 423
 424   \warning
 425
 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.
 429 */
 430
 431 /*!
 432   \fn void QGArray::setSharedBlock( array_data *p )
 433   \internal
 434   Sets the shared array block to \e p.
 435
 436   \warning
 437
 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.
 441 */
 442
 443
 444 /*!
 445   \internal
 446   Sets raw data and returns a reference to the array.
 447
 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.
 452
 453   Setting raw data is useful because it set QArray data without allocating
 454   memory or copying data.
 455
 456   Example of intended use:
 457   \code
 458     static uchar bindata[] = { 231, 1, 44, ... };
 459     QByteArray  a;
 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
 463     s.close();
 464     a.resetRawData( bindata, sizeof(bindata) ); // finished
 465   \endcode
 466
 467   Example of misuse (do not do this):
 468   \code
 469     static uchar bindata[] = { 231, 1, 44, ... };
 470     QByteArray  a, b;
 471     a.setRawData( bindata, sizeof(bindata) );   // a points to bindata
 472     a.resize( 8 );                              // will crash
 473     b = a;                                      // will crash
 474     a[2] = 123;                                 // might crash
 475       // forget to resetRawData - will crash
 476   \endcode
 477
 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.
 480   Be careful.
 481 */
 482
 483 QGArray &QGArray::setRawData( const char *d, uint len )
 484 {
 485     duplicate( 0, 0 );                          // set null data
 486     shd->data = (char *)d;
 487     shd->len  = len;
 488     return *this;
 489 }
 490
 491 /*!
 492   \internal
 493   Resets raw data.
 494
 495   The arguments must be the data and length that were passed to
 496   setRawData().  This is for consistency checking.
 497 */
 498
 499 void QGArray::resetRawData( const char *d, uint len )
 500 {
 501     if ( d != shd->data || len != shd->len ) {
 502 #if defined(CHECK_STATE)
 503         qWarning( "QGArray::resetRawData: Inconsistent arguments" );
 504 #endif
 505         return;
 506     }
 507     shd->data = 0;
 508     shd->len  = 0;
 509 }
 510
 511
 512 /*!
 513   \internal
 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.
 516
 517   Note that \e index is given in units of \e sz, not bytes.
 518
 519   This function only compares whole cells, not bytes.
 520 */
 521
 522 int QGArray::find( const char *d, uint index, uint sz ) const
 523 {
 524     index *= sz;
 525     if ( index >= shd->len ) {
 526 #if defined(CHECK_RANGE)
 527         qWarning( "QGArray::find: Index %d out of range", index/sz );
 528 #endif
 529         return -1;
 530     }
 531     uint i;
 532     uint ii;
 533     switch ( sz ) {
 534         case 1: {                               // 8 bit elements
 535             char *x = data() + index;
 536             char v = *d;
 537             for ( i=index; i<shd->len; i++ ) {
 538                 if ( *x++ == v )
 539                     break;
 540             }
 541             ii = i;
 542             }
 543             break;
 544         case 2: {                               // 16 bit elements
 545             Q_INT16 *x = (Q_INT16*)(data() + index);
 546             Q_INT16 v = *((Q_INT16*)d);
 547             for ( i=index; i<shd->len; i+=2 ) {
 548                 if ( *x++ == v )
 549                     break;
 550             }
 551             ii = i/2;
 552             }
 553             break;
 554         case 4: {                               // 32 bit elements
 555             Q_INT32 *x = (Q_INT32*)(data() + index);
 556             Q_INT32 v = *((Q_INT32*)d);
 557             for ( i=index; i<shd->len; i+=4 ) {
 558                 if ( *x++ == v )
 559                     break;
 560             }
 561             ii = i/4;
 562             }
 563             break;
 564         default: {                              // any size elements
 565             for ( i=index; i<shd->len; i+=sz ) {
 566                 if ( memcmp( d, &shd->data[i], sz ) == 0 )
 567                     break;
 568             }
 569             ii = i/sz;
 570             }
 571             break;
 572     }
 573     return i<shd->len ? (int)ii : -1;
 574 }
 575
 576 /*!
 577   \internal
 578   Returns the number of occurrences of \e d in the array, where \e sz is
 579   the size of the \e d element.
 580
 581   This function only compares whole cells, not bytes.
 582 */
 583
 584 int QGArray::contains( const char *d, uint sz ) const
 585 {
 586     uint i = shd->len;
 587     int count = 0;
 588     switch ( sz ) {
 589         case 1: {                               // 8 bit elements
 590             char *x = data();
 591             char v = *d;
 592             while ( i-- ) {
 593                 if ( *x++ == v )
 594                     count++;
 595             }
 596             }
 597             break;
 598         case 2: {                               // 16 bit elements
 599             Q_INT16 *x = (Q_INT16*)data();
 600             Q_INT16 v = *((Q_INT16*)d);
 601             i /= 2;
 602             while ( i-- ) {
 603                 if ( *x++ == v )
 604                     count++;
 605             }
 606             }
 607             break;
 608         case 4: {                               // 32 bit elements
 609             Q_INT32 *x = (Q_INT32*)data();
 610             Q_INT32 v = *((Q_INT32*)d);
 611             i /= 4;
 612             while ( i-- ) {
 613                 if ( *x++ == v )
 614                     count++;
 615             }
 616             }
 617             break;
 618         default: {                              // any size elements
 619             for ( i=0; i<shd->len; i+=sz ) {
 620                 if ( memcmp(d, &shd->data[i], sz) == 0 )
 621                     count++;
 622             }
 623             }
 624             break;
 625     }
 626     return count;
 627 }
 628
 629 static int cmp_item_size = 0;
 630
 631 #if defined(Q_C_CALLBACKS)
 632 extern "C" {
 633 #endif
 634
 635 static int cmp_arr( const void *n1, const void *n2 )
 636 {
 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
 640 }
 641
 642 #if defined(Q_C_CALLBACKS)
 643 }
 644 #endif
 645
 646 /*!
 647   \internal
 648
 649   Sort the array.
 650 */
 651
 652 void QGArray::sort( uint sz )
 653 {
 654     int numItems = size() / sz;
 655     if ( numItems < 2 )
 656         return;
 657     cmp_item_size = sz;
 658     qsort( shd->data, numItems, sz, cmp_arr );
 659 }
 660
 661 /*!
 662   \internal
 663
 664   Binary search; assumes sorted array
 665 */
 666
 667 int QGArray::bsearch( const char *d, uint sz ) const
 668 {
 669     int numItems = size() / sz;
 670     if ( !numItems )
 671         return -1;
 672     cmp_item_size = sz;
 673     char* r = (char*)::bsearch( d, shd->data, numItems, sz, cmp_arr );
 674     if ( !r )
 675         return -1;
 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);
 679 }
 680
 681
 682 /*!
 683   \fn char *QGArray::at( uint index ) const
 684   \internal
 685   Returns a pointer to the byte at offset \e index in the array.
 686 */
 687
 688 /*!
 689   \internal
 690   Expand the array if necessary, and copies (the first part of) its
 691   contents from the \e index*zx bytes at \e d.
 692
 693   Returns TRUE if the operation succeeds, FALSE if it runs out of
 694   memory.
 695
 696   \warning This function disregards the reference count mechanism.  If
 697   other QGArrays reference the same data as this, all will be changed.
 698 */
 699
 700 bool QGArray::setExpand( uint index, const char *d, uint sz )
 701 {
 702     index *= sz;
 703     if ( index >= shd->len ) {
 704         if ( !resize( index+sz ) )              // no memory
 705             return FALSE;
 706     }
 707     memcpy( data() + index, d, sz );
 708     return TRUE;
 709 }
 710
 711
 712 /*!
 713   \internal
 714   Prints a warning message if at() or [] is given a bad index.
 715 */
 716
 717 void QGArray::msg_index( uint index )
 718 {
 719 #if defined(CHECK_RANGE)
 720     qWarning( "QGArray::at: Absolute index %d out of range", index );
 721 #else
 722     Q_UNUSED( index )
 723 #endif
 724 }
 725
 726
 727 /*!
 728   \internal
 729   Returns a new shared array block.
 730 */
 731
 732 QGArray::array_data * QGArray::newData()
 733 {
 734     return new array_data;
 735 }
 736
 737
 738 /*!
 739   \internal
 740   Deletes the shared array block.
 741 */
 742
 743 void QGArray::deleteData( array_data *p )
 744 {
 745     delete p;
 746     p = 0;
 747 }