1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the Qt3Support module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #include "qglobal.h"

    43 #if defined(Q_CC_BOR)

    44 // needed for qsort() because of a std namespace problem on Borland

    45 #include "qplatformdefs.h"

    46 #endif

    47 

    48 #define	 Q3GVECTOR_CPP

    49 #include "q3gvector.h"

    50 #include "q3glist.h"

    51 #include "qstring.h"

    52 #include "qdatastream.h"

    53 #include <stdlib.h>

    54 

    55 #ifndef QT_NO_THREAD

    56 #  include "private/qmutexpool_p.h"

    57 #endif

    58 

    59 QT_BEGIN_NAMESPACE

    60 

    61 #define USE_MALLOC				// comment to use new/delete

    62 

    63 #undef NEW

    64 #undef DELETE

    65 

    66 #if defined(USE_MALLOC)

    67 #define NEW(type,size)	((type*)malloc(size*sizeof(type)))

    68 #define DELETE(array)	(free((char*)array))

    69 #else

    70 #define NEW(type,size)	(new type[size])

    71 #define DELETE(array)	(delete[] array)

    72 #define DONT_USE_REALLOC			// comment to use realloc()

    73 #endif

    74 

    75 /*!

    76   \class Q3GVector

    77   \reentrant

    78 

    79   \brief The Q3GVector class is an internal class for implementing Qt

    80   collection classes.

    81 

    82   \internal

    83 

    84   Q3GVector is an internal class that acts as a base class for the

    85   Q3PtrVector collection class.

    86 

    87   Q3GVector has some virtual functions that may be reimplemented in

    88   subclasses to customize behavior.

    89 

    90   \list

    91   \i compareItems() compares two collection/vector items.

    92   \i read() reads a collection/vector item from a QDataStream.

    93   \i write() writes a collection/vector item to a QDataStream.

    94   \endlist

    95 */

    96 

    97 /*****************************************************************************

    98   Default implementation of virtual functions

    99  *****************************************************************************/

   100 

   101 /*!

   102   This virtual function compares two list items.

   103 

   104   Returns:

   105   <ul>

   106   <li> 0 if \a d1 == \a d2

   107   <li> non-zero if \a d1 != \a d2

   108   </ul>

   109 

   110   This function returns \e int rather than \e bool so that

   111   reimplementations can return one of three values and use it to sort

   112   by:

   113   <ul>

   114   <li> 0 if \a d1 == \a d2

   115   <li> \> 0 (positive integer) if \a d1 \> \a d2

   116   <li> \< 0 (negative integer) if \a d1 \< \a d2

   117   </ul>

   118 

   119   The Q3PtrVector::sort() and Q3PtrVector::bsearch() functions require that

   120   compareItems() is implemented as described here.

   121 

   122   This function should not modify the vector because some const

   123   functions call compareItems().

   124 */

   125 

   126 int Q3GVector::compareItems( Item d1, Item d2 )

   127 {

   128     return d1 != d2;				// compare pointers

   129 }

   130 

   131 #ifndef QT_NO_DATASTREAM

   132 /*!

   133   Reads a collection/vector item from the stream \a s and returns a reference

   134   to the stream.

   135 

   136   The default implementation sets \a d to 0.

   137 

   138   \sa write()

   139 */

   140 

   141 QDataStream &Q3GVector::read( QDataStream &s, Item &d )

   142 {						// read item from stream

   143     d = 0;

   144     return s;

   145 }

   146 

   147 /*!

   148   Writes a collection/vector item to the stream \a s and returns a reference

   149   to the stream.

   150 

   151   The default implementation does nothing.

   152 

   153   \sa read()

   154 */

   155 

   156 QDataStream &Q3GVector::write( QDataStream &s, Item ) const

   157 {						// write item to stream

   158     return s;

   159 }

   160 #endif // QT_NO_DATASTREAM

   161 

   162 /*****************************************************************************

   163   Q3GVector member functions

   164  *****************************************************************************/

   165 

   166 Q3GVector::Q3GVector()				// create empty vector

   167 {

   168     vec = 0;

   169     len = numItems = 0;

   170 }

   171 

   172 Q3GVector::Q3GVector( uint size )			// create vectors with nullptrs

   173 {

   174     len = size;

   175     numItems = 0;

   176     if ( len == 0 ) {				// zero length

   177 	vec = 0;

   178 	return;

   179     }

   180     vec = NEW(Item,len);

   181     Q_CHECK_PTR( vec );

   182     memset( (void*)vec, 0, len*sizeof(Item) );	// fill with nulls

   183 }

   184 

   185 Q3GVector::Q3GVector( const Q3GVector &a )		// make copy of other vector

   186     : Q3PtrCollection( a )

   187 {

   188     len = a.len;

   189     numItems = a.numItems;

   190     if ( len == 0 ) {

   191 	vec = 0;

   192 	return;

   193     }

   194     vec = NEW( Item, len );

   195     Q_CHECK_PTR( vec );

   196     for ( uint i = 0; i < len; i++ ) {

   197 	if ( a.vec[i] ) {

   198 	    vec[i] = newItem( a.vec[i] );

   199 	    Q_CHECK_PTR( vec[i] );

   200 	} else {

   201 	    vec[i] = 0;

   202 	}

   203     }

   204 }

   205 

   206 Q3GVector::~Q3GVector()

   207 {

   208     clear();

   209 }

   210 

   211 Q3GVector& Q3GVector::operator=( const Q3GVector &v )

   212 {

   213     if ( &v == this )

   214 	return *this;

   215 

   216     clear();

   217     len = v.len;

   218     numItems = v.numItems;

   219     if ( len == 0 ) {

   220 	vec = 0;

   221 	return *this;

   222     }

   223     vec = NEW( Item, len );

   224     Q_CHECK_PTR( vec );

   225     for ( uint i = 0; i < len; i++ ) {

   226 	if ( v.vec[i] ) {

   227 	    vec[i] = newItem( v.vec[i] );

   228 	    Q_CHECK_PTR( vec[i] );

   229 	} else {

   230 	    vec[i] = 0;

   231 	}

   232     }

   233     return *this;

   234 }

   235 

   236 

   237 bool Q3GVector::insert( uint index, Item d )	// insert item at index

   238 {

   239 #if defined(QT_CHECK_RANGE)

   240     if ( index >= len ) {			// range error

   241 	qWarning( "Q3GVector::insert: Index %d out of range", index );

   242 	return false;

   243     }

   244 #endif

   245     if ( vec[index] ) {				// remove old item

   246 	deleteItem( vec[index] );

   247 	numItems--;

   248     }

   249     if ( d ) {

   250 	vec[index] = newItem( d );

   251 	Q_CHECK_PTR( vec[index] );

   252 	numItems++;

   253 	return vec[index] != 0;

   254     } else {

   255 	vec[index] = 0;				// reset item

   256     }

   257     return true;

   258 }

   259 

   260 bool Q3GVector::remove( uint index )		// remove item at index

   261 {

   262 #if defined(QT_CHECK_RANGE)

   263     if ( index >= len ) {			// range error

   264 	qWarning( "Q3GVector::remove: Index %d out of range", index );

   265 	return false;

   266     }

   267 #endif

   268     if ( vec[index] ) {				// valid item

   269 	deleteItem( vec[index] );		// delete it

   270 	vec[index] = 0;				// reset pointer

   271 	numItems--;

   272     }

   273     return true;

   274 }

   275 

   276 Q3PtrCollection::Item Q3GVector::take( uint index )		// take out item

   277 {

   278 #if defined(QT_CHECK_RANGE)

   279     if ( index >= len ) {			// range error

   280 	qWarning( "Q3GVector::take: Index %d out of range", index );

   281 	return 0;

   282     }

   283 #endif

   284     Item d = vec[index];				// don't delete item

   285     if ( d )

   286 	numItems--;

   287     vec[index] = 0;

   288     return d;

   289 }

   290 

   291 void Q3GVector::clear()				// clear vector

   292 {

   293     if ( vec ) {

   294 	for ( uint i=0; i<len; i++ ) {		// delete each item

   295 	    if ( vec[i] )

   296 		deleteItem( vec[i] );

   297 	}

   298 	DELETE(vec);

   299 	vec = 0;

   300 	len = numItems = 0;

   301     }

   302 }

   303 

   304 bool Q3GVector::resize( uint newsize )		// resize array

   305 {

   306     if ( newsize == len )			// nothing to do

   307 	return true;

   308     if ( vec ) {				// existing data

   309 	if ( newsize < len ) {			// shrink vector

   310 	    uint i = newsize;

   311 	    while ( i < len ) {			// delete lost items

   312 		if ( vec[i] ) {

   313 		    deleteItem( vec[i] );

   314 		    numItems--;

   315 		}

   316 		i++;

   317 	    }

   318 	}

   319 	if ( newsize == 0 ) {			// vector becomes empty

   320 	    DELETE(vec);

   321 	    vec = 0;

   322 	    len = numItems = 0;

   323 	    return true;

   324 	}

   325 #if defined(DONT_USE_REALLOC)

   326 	if ( newsize == 0 ) {

   327 	    DELETE(vec);

   328 	    vec = 0;

   329 	    return false;

   330 	}

   331 	Item *newvec = NEW(Item,newsize);		// manual realloc

   332 	memcpy( newvec, vec, (len < newsize ? len : newsize)*sizeof(Item) );

   333 	DELETE(vec);

   334 	vec = newvec;

   335 #else

   336 	vec = (Item*)realloc( (char *)vec, newsize*sizeof(Item) );

   337 #endif

   338     } else {					// create new vector

   339 	vec = NEW(Item,newsize);

   340 	len = numItems = 0;

   341     }

   342     Q_CHECK_PTR( vec );

   343     if ( !vec )					// no memory

   344 	return false;

   345     if ( newsize > len )			// init extra space added

   346 	memset( (void*)&vec[len], 0, (newsize-len)*sizeof(Item) );

   347     len = newsize;

   348     return true;

   349 }

   350 

   351 

   352 bool Q3GVector::fill( Item d, int flen )		// resize and fill vector

   353 {

   354     if ( flen < 0 )

   355 	flen = len;				// default: use vector length

   356     else if ( !resize( flen ) )

   357 	return false;

   358     for ( uint i=0; i<(uint)flen; i++ )		// insert d at every index

   359 	insert( i, d );

   360     return true;

   361 }

   362 

   363 

   364 static Q3GVector *sort_vec=0;			// current sort vector

   365 

   366 

   367 #if defined(Q_C_CALLBACKS)

   368 extern "C" {

   369 #endif

   370 

   371 #ifdef Q_OS_WINCE

   372 static int _cdecl cmp_vec( const void *n1, const void *n2 )

   373 #else

   374 static int cmp_vec( const void *n1, const void *n2 )

   375 #endif

   376 {

   377     return sort_vec->compareItems( *((Q3PtrCollection::Item*)n1), *((Q3PtrCollection::Item*)n2) );

   378 }

   379 

   380 #if defined(Q_C_CALLBACKS)

   381 }

   382 #endif

   383 

   384 

   385 void Q3GVector::sort()				// sort vector

   386 {

   387     if ( count() == 0 )				// no elements

   388 	return;

   389     register Item *start = &vec[0];

   390     register Item *end	= &vec[len-1];

   391     Item tmp;

   392     for (;;) {				// put all zero elements behind

   393 	while ( start < end && *start != 0 )

   394 	    start++;

   395 	while ( end > start && *end == 0 )

   396 	    end--;

   397 	if ( start < end ) {

   398 	    tmp = *start;

   399 	    *start = *end;

   400 	    *end = tmp;

   401 	} else {

   402 	    break;

   403 	}

   404     }

   405 

   406 #ifndef QT_NO_THREAD

   407     QMutexLocker locker(QMutexPool::globalInstanceGet(&sort_vec));

   408 #endif

   409 

   410     sort_vec = (Q3GVector*)this;

   411     qsort( vec, count(), sizeof(Item), cmp_vec );

   412     sort_vec = 0;

   413 }

   414 

   415 int Q3GVector::bsearch( Item d ) const		// binary search; when sorted

   416 {

   417     if ( !len )

   418 	return -1;

   419     if ( !d ) {

   420 #if defined(QT_CHECK_NULL)

   421 	qWarning( "Q3GVector::bsearch: Cannot search for null object" );

   422 #endif

   423 	return -1;

   424     }

   425     int n1 = 0;

   426     int n2 = len - 1;

   427     int mid = 0;

   428     bool found = false;

   429     while ( n1 <= n2 ) {

   430 	int  res;

   431 	mid = (n1 + n2)/2;

   432 	if ( vec[mid] == 0 )			// null item greater

   433 	    res = -1;

   434 	else

   435 	    res = ((Q3GVector*)this)->compareItems( d, vec[mid] );

   436 	if ( res < 0 )

   437 	    n2 = mid - 1;

   438 	else if ( res > 0 )

   439 	    n1 = mid + 1;

   440 	else {					// found it

   441 	    found = true;

   442 	    break;

   443 	}

   444     }

   445     if ( !found )

   446 	return -1;

   447     // search to first of equal items

   448     while ( (mid - 1 >= 0) && !((Q3GVector*)this)->compareItems(d, vec[mid-1]) )

   449 	mid--;

   450     return mid;

   451 }

   452 

   453 int Q3GVector::findRef( Item d, uint index) const // find exact item in vector

   454 {

   455 #if defined(QT_CHECK_RANGE)

   456     if ( index > len ) {			// range error

   457 	qWarning( "Q3GVector::findRef: Index %d out of range", index );

   458 	return -1;

   459     }

   460 #endif

   461     for ( uint i=index; i<len; i++ ) {

   462 	if ( vec[i] == d )

   463 	    return i;

   464     }

   465     return -1;

   466 }

   467 

   468 int Q3GVector::find( Item d, uint index ) const	// find equal item in vector

   469 {

   470 #if defined(QT_CHECK_RANGE)

   471     if ( index >= len ) {			// range error

   472 	qWarning( "Q3GVector::find: Index %d out of range", index );

   473 	return -1;

   474     }

   475 #endif

   476     for ( uint i=index; i<len; i++ ) {

   477 	if ( vec[i] == 0 && d == 0 )		// found null item

   478 	    return i;

   479 	if ( vec[i] && ((Q3GVector*)this)->compareItems( vec[i], d ) == 0 )

   480 	    return i;

   481     }

   482     return -1;

   483 }

   484 

   485 uint Q3GVector::containsRef( Item d ) const	// get number of exact matches

   486 {

   487     uint count = 0;

   488     for ( uint i=0; i<len; i++ ) {

   489 	if ( vec[i] == d )

   490 	    count++;

   491     }

   492     return count;

   493 }

   494 

   495 uint Q3GVector::contains( Item d ) const		// get number of equal matches

   496 {

   497     uint count = 0;

   498     for ( uint i=0; i<len; i++ ) {

   499 	if ( vec[i] == 0 && d == 0 )		// count null items

   500 	    count++;

   501 	if ( vec[i] && ((Q3GVector*)this)->compareItems( vec[i], d ) == 0 )

   502 	    count++;

   503     }

   504     return count;

   505 }

   506 

   507 bool Q3GVector::insertExpand( uint index, Item d )// insert and grow if necessary

   508 {

   509     if ( index >= len ) {

   510 	if ( !resize( index+1 ) )		// no memory

   511 	    return false;

   512     }

   513     insert( index, d );

   514     return true;

   515 }

   516 

   517 void Q3GVector::toList( Q3GList *list ) const	// store items in list

   518 {

   519     list->clear();

   520     for ( uint i=0; i<len; i++ ) {

   521 	if ( vec[i] )

   522 	    list->append( vec[i] );

   523     }

   524 }

   525 

   526 

   527 void Q3GVector::warningIndexRange( uint i )

   528 {

   529 #if defined(QT_CHECK_RANGE)

   530     qWarning( "Q3GVector::operator[]: Index %d out of range", i );

   531 #else

   532     Q_UNUSED( i )

   533 #endif

   534 }

   535 

   536 

   537 /*****************************************************************************

   538   Q3GVector stream functions

   539  *****************************************************************************/

   540 #ifndef QT_NO_DATASTREAM

   541 QDataStream &operator>>( QDataStream &s, Q3GVector &vec )

   542 {						// read vector

   543     return vec.read( s );

   544 }

   545 

   546 QDataStream &operator<<( QDataStream &s, const Q3GVector &vec )

   547 {						// write vector

   548     return vec.write( s );

   549 }

   550 

   551 QDataStream &Q3GVector::read( QDataStream &s )	// read vector from stream

   552 {

   553     uint num;

   554     s >> num;					// read number of items

   555     clear();					// clear vector

   556     resize( num );

   557     for (uint i=0; i<num; i++) {		// read all items

   558 	Item d;

   559 	read( s, d );

   560 	Q_CHECK_PTR( d );

   561 	if ( !d )				// no memory

   562 	    break;

   563 	vec[i] = d;

   564     }

   565     return s;

   566 }

   567 

   568 QDataStream &Q3GVector::write( QDataStream &s ) const

   569 {						// write vector to stream

   570     uint num = count();

   571     s << num;					// number of items to write

   572     num = size();

   573     for (uint i=0; i<num; i++) {		// write non-null items

   574 	if ( vec[i] )

   575 	    write( s, vec[i] );

   576     }

   577     return s;

   578 }

   579 

   580 /* Returns whether v equals this vector or not */

   581 

   582 bool Q3GVector::operator==( const Q3GVector &v ) const

   583 {

   584     if ( size() != v.size() )

   585 	return false;

   586     if ( count() != v.count() )

   587 	return false;

   588     for ( int i = 0; i < (int)size(); ++i ) {

   589 	if ( ( (Q3GVector*)this )->compareItems( at( i ), v.at( i ) ) != 0 )

   590 	    return false;

   591     }

   592     return true;

   593 }

   594 

   595 #endif // QT_NO_DATASTREAM

   596 

   597 QT_END_NAMESPACE