source: trunk/src/qt3support/tools/q3gvector.cpp@ 352

Last change on this file since 352 was 2, checked in by Dmitry A. Kuminov, 16 years ago

Initially imported qt-all-opensource-src-4.5.1 from Trolltech.
File size: 14.0 KB
Line 
1/****************************************************************************
2**
3** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
4** Contact: Qt Software Information ([email protected])
5**
6** This file is part of the Qt3Support module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial Usage
10** Licensees holding valid Qt Commercial licenses may use this file in
11** accordance with the Qt Commercial License Agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and Nokia.
14**
15** GNU Lesser General Public License Usage
16** Alternatively, this file may be used under the terms of the GNU Lesser
17** General Public License version 2.1 as published by the Free Software
18** Foundation and appearing in the file LICENSE.LGPL included in the
19** packaging of this file. Please review the following information to
20** ensure the GNU Lesser General Public License version 2.1 requirements
21** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
22**
23** In addition, as a special exception, Nokia gives you certain
24** additional rights. These rights are described in the Nokia Qt LGPL
25** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this
26** package.
27**
28** GNU General Public License Usage
29** Alternatively, this file may be used under the terms of the GNU
30** General Public License version 3.0 as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL included in the
32** packaging of this file. Please review the following information to
33** ensure the GNU General Public License version 3.0 requirements will be
34** met: http://www.gnu.org/copyleft/gpl.html.
35**
36** If you are unsure which license is appropriate for your use, please
37** contact the sales department at [email protected].
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
59QT_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
126int 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
141QDataStream &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
156QDataStream &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
166Q3GVector::Q3GVector() // create empty vector
167{
168 vec = 0;
169 len = numItems = 0;
170}
171
172Q3GVector::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
185Q3GVector::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
206Q3GVector::~Q3GVector()
207{
208 clear();
209}
210
211Q3GVector& 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
237bool 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
260bool 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
276Q3PtrCollection::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
291void 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
304bool 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
352bool 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
364static Q3GVector *sort_vec=0; // current sort vector
365
366
367#if defined(Q_C_CALLBACKS)
368extern "C" {
369#endif
370
371#ifdef Q_OS_WINCE
372static int _cdecl cmp_vec( const void *n1, const void *n2 )
373#else
374static 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
385void 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
415int 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
453int 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
468int 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
485uint 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
495uint 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
507bool 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
517void 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
527void 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
541QDataStream &operator>>( QDataStream &s, Q3GVector &vec )
542{ // read vector
543 return vec.read( s );
544}
545
546QDataStream &operator<<( QDataStream &s, const Q3GVector &vec )
547{ // write vector
548 return vec.write( s );
549}
550
551QDataStream &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
568QDataStream &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
582bool 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
597QT_END_NAMESPACE
Note: See TracBrowser for help on using the repository browser.