author | kergoth <kergoth> | 2002-11-01 00:10:42 (UTC) |
---|---|---|
committer | kergoth <kergoth> | 2002-11-01 00:10:42 (UTC) |
commit | 5042e3cf0d3514552769e441f5aad590c8eaf967 (patch) (unidiff) | |
tree | 4a5ea45f3519d981a172ab5275bf38c6fa778dec /qmake/tools/qgvector.cpp | |
parent | 108c1c753e74e989cc13923086996791428c9af4 (diff) | |
download | opie-5042e3cf0d3514552769e441f5aad590c8eaf967.zip opie-5042e3cf0d3514552769e441f5aad590c8eaf967.tar.gz opie-5042e3cf0d3514552769e441f5aad590c8eaf967.tar.bz2 |
Adding qmake in preperation for new build system
-rw-r--r-- | qmake/tools/qgvector.cpp | 584 |
1 files changed, 584 insertions, 0 deletions
diff --git a/qmake/tools/qgvector.cpp b/qmake/tools/qgvector.cpp new file mode 100644 index 0000000..1985f03 --- a/dev/null +++ b/qmake/tools/qgvector.cpp | |||
@@ -0,0 +1,584 @@ | |||
1 | /**************************************************************************** | ||
2 | ** $Id$ | ||
3 | ** | ||
4 | ** Implementation of QGVector class | ||
5 | ** | ||
6 | ** Created : 930907 | ||
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 QGVECTOR_CPP | ||
39 | #include "qgvector.h" | ||
40 | #include "qglist.h" | ||
41 | #include "qstring.h" | ||
42 | #include "qdatastream.h" | ||
43 | #include <stdlib.h> | ||
44 | |||
45 | #ifdef QT_THREAD_SUPPORT | ||
46 | # include <private/qmutexpool_p.h> | ||
47 | #endif // QT_THREAD_SUPPORT | ||
48 | |||
49 | #define USE_MALLOC // comment to use new/delete | ||
50 | |||
51 | #undef NEW | ||
52 | #undef DELETE | ||
53 | |||
54 | #if defined(USE_MALLOC) | ||
55 | #define NEW(type,size)((type*)malloc(size*sizeof(type))) | ||
56 | #define DELETE(array)(free((char*)array)) | ||
57 | #else | ||
58 | #define NEW(type,size)(new type[size]) | ||
59 | #define DELETE(array)(delete[] array) | ||
60 | #define DONT_USE_REALLOC // comment to use realloc() | ||
61 | #endif | ||
62 | |||
63 | /*! | ||
64 | \class QGVector | ||
65 | \reentrant | ||
66 | \ingroup collection | ||
67 | |||
68 | \brief The QGVector class is an internal class for implementing Qt | ||
69 | collection classes. | ||
70 | |||
71 | \internal | ||
72 | |||
73 | QGVector is an internal class that acts as a base class for the | ||
74 | QPtrVector collection class. | ||
75 | |||
76 | QGVector has some virtual functions that may be reimplemented in | ||
77 | subclasses to customize behavior. | ||
78 | |||
79 | \list | ||
80 | \i compareItems() compares two collection/vector items. | ||
81 | \i read() reads a collection/vector item from a QDataStream. | ||
82 | \i write() writes a collection/vector item to a QDataStream. | ||
83 | \endlist | ||
84 | */ | ||
85 | |||
86 | /***************************************************************************** | ||
87 | Default implementation of virtual functions | ||
88 | *****************************************************************************/ | ||
89 | |||
90 | /*! | ||
91 | This virtual function compares two list items. | ||
92 | |||
93 | Returns: | ||
94 | <ul> | ||
95 | <li> 0 if \a d1 == \a d2 | ||
96 | <li> non-zero if \a d1 != \a d2 | ||
97 | </ul> | ||
98 | |||
99 | This function returns \e int rather than \e bool so that | ||
100 | reimplementations can return one of three values and use it to sort | ||
101 | by: | ||
102 | <ul> | ||
103 | <li> 0 if \a d1 == \a d2 | ||
104 | <li> \> 0 (positive integer) if \a d1 \> \a d2 | ||
105 | <li> \< 0 (negative integer) if \a d1 \< \a d2 | ||
106 | </ul> | ||
107 | |||
108 | The QPtrVector::sort() and QPtrVector::bsearch() functions require that | ||
109 | compareItems() is implemented as described here. | ||
110 | |||
111 | This function should not modify the vector because some const | ||
112 | functions call compareItems(). | ||
113 | */ | ||
114 | |||
115 | int QGVector::compareItems( Item d1, Item d2 ) | ||
116 | { | ||
117 | return d1 != d2; // compare pointers | ||
118 | } | ||
119 | |||
120 | #ifndef QT_NO_DATASTREAM | ||
121 | /*! | ||
122 | Reads a collection/vector item from the stream \a s and returns a reference | ||
123 | to the stream. | ||
124 | |||
125 | The default implementation sets \a d to 0. | ||
126 | |||
127 | \sa write() | ||
128 | */ | ||
129 | |||
130 | QDataStream &QGVector::read( QDataStream &s, Item &d ) | ||
131 | { // read item from stream | ||
132 | d = 0; | ||
133 | return s; | ||
134 | } | ||
135 | |||
136 | /*! | ||
137 | Writes a collection/vector item to the stream \a s and returns a reference | ||
138 | to the stream. | ||
139 | |||
140 | The default implementation does nothing. | ||
141 | |||
142 | \sa read() | ||
143 | */ | ||
144 | |||
145 | QDataStream &QGVector::write( QDataStream &s, Item ) const | ||
146 | { // write item to stream | ||
147 | return s; | ||
148 | } | ||
149 | #endif // QT_NO_DATASTREAM | ||
150 | |||
151 | /***************************************************************************** | ||
152 | QGVector member functions | ||
153 | *****************************************************************************/ | ||
154 | |||
155 | QGVector::QGVector() // create empty vector | ||
156 | { | ||
157 | vec = 0; | ||
158 | len = numItems = 0; | ||
159 | } | ||
160 | |||
161 | QGVector::QGVector( uint size ) // create vectors with nullptrs | ||
162 | { | ||
163 | len = size; | ||
164 | numItems = 0; | ||
165 | if ( len == 0 ) { // zero length | ||
166 | vec = 0; | ||
167 | return; | ||
168 | } | ||
169 | vec = NEW(Item,len); | ||
170 | Q_CHECK_PTR( vec ); | ||
171 | memset( (void*)vec, 0, len*sizeof(Item) );// fill with nulls | ||
172 | } | ||
173 | |||
174 | QGVector::QGVector( const QGVector &a ) // make copy of other vector | ||
175 | : QPtrCollection( a ) | ||
176 | { | ||
177 | len = a.len; | ||
178 | numItems = a.numItems; | ||
179 | if ( len == 0 ) { | ||
180 | vec = 0; | ||
181 | return; | ||
182 | } | ||
183 | vec = NEW( Item, len ); | ||
184 | Q_CHECK_PTR( vec ); | ||
185 | for ( uint i = 0; i < len; i++ ) { | ||
186 | if ( a.vec[i] ) { | ||
187 | vec[i] = newItem( a.vec[i] ); | ||
188 | Q_CHECK_PTR( vec[i] ); | ||
189 | } else { | ||
190 | vec[i] = 0; | ||
191 | } | ||
192 | } | ||
193 | } | ||
194 | |||
195 | QGVector::~QGVector() | ||
196 | { | ||
197 | clear(); | ||
198 | } | ||
199 | |||
200 | QGVector& QGVector::operator=( const QGVector &v ) | ||
201 | { | ||
202 | if ( &v == this ) | ||
203 | return *this; | ||
204 | |||
205 | clear(); | ||
206 | len = v.len; | ||
207 | numItems = v.numItems; | ||
208 | if ( len == 0 ) { | ||
209 | vec = 0; | ||
210 | return *this; | ||
211 | } | ||
212 | vec = NEW( Item, len ); | ||
213 | Q_CHECK_PTR( vec ); | ||
214 | for ( uint i = 0; i < len; i++ ) { | ||
215 | if ( v.vec[i] ) { | ||
216 | vec[i] = newItem( v.vec[i] ); | ||
217 | Q_CHECK_PTR( vec[i] ); | ||
218 | } else { | ||
219 | vec[i] = 0; | ||
220 | } | ||
221 | } | ||
222 | return *this; | ||
223 | } | ||
224 | |||
225 | |||
226 | bool QGVector::insert( uint index, Item d )// insert item at index | ||
227 | { | ||
228 | #if defined(QT_CHECK_RANGE) | ||
229 | if ( index >= len ) { // range error | ||
230 | qWarning( "QGVector::insert: Index %d out of range", index ); | ||
231 | return FALSE; | ||
232 | } | ||
233 | #endif | ||
234 | if ( vec[index] ) { // remove old item | ||
235 | deleteItem( vec[index] ); | ||
236 | numItems--; | ||
237 | } | ||
238 | if ( d ) { | ||
239 | vec[index] = newItem( d ); | ||
240 | Q_CHECK_PTR( vec[index] ); | ||
241 | numItems++; | ||
242 | return vec[index] != 0; | ||
243 | } else { | ||
244 | vec[index] = 0; // reset item | ||
245 | } | ||
246 | return TRUE; | ||
247 | } | ||
248 | |||
249 | bool QGVector::remove( uint index ) // remove item at index | ||
250 | { | ||
251 | #if defined(QT_CHECK_RANGE) | ||
252 | if ( index >= len ) { // range error | ||
253 | qWarning( "QGVector::remove: Index %d out of range", index ); | ||
254 | return FALSE; | ||
255 | } | ||
256 | #endif | ||
257 | if ( vec[index] ) { // valid item | ||
258 | deleteItem( vec[index] ); // delete it | ||
259 | vec[index] = 0; // reset pointer | ||
260 | numItems--; | ||
261 | } | ||
262 | return TRUE; | ||
263 | } | ||
264 | |||
265 | QPtrCollection::Item QGVector::take( uint index ) // take out item | ||
266 | { | ||
267 | #if defined(QT_CHECK_RANGE) | ||
268 | if ( index >= len ) { // range error | ||
269 | qWarning( "QGVector::take: Index %d out of range", index ); | ||
270 | return 0; | ||
271 | } | ||
272 | #endif | ||
273 | Item d = vec[index]; // don't delete item | ||
274 | if ( d ) | ||
275 | numItems--; | ||
276 | vec[index] = 0; | ||
277 | return d; | ||
278 | } | ||
279 | |||
280 | void QGVector::clear() // clear vector | ||
281 | { | ||
282 | if ( vec ) { | ||
283 | for ( uint i=0; i<len; i++ ) { // delete each item | ||
284 | if ( vec[i] ) | ||
285 | deleteItem( vec[i] ); | ||
286 | } | ||
287 | DELETE(vec); | ||
288 | vec = 0; | ||
289 | len = numItems = 0; | ||
290 | } | ||
291 | } | ||
292 | |||
293 | bool QGVector::resize( uint newsize ) // resize array | ||
294 | { | ||
295 | if ( newsize == len ) // nothing to do | ||
296 | return TRUE; | ||
297 | if ( vec ) { // existing data | ||
298 | if ( newsize < len ) { // shrink vector | ||
299 | uint i = newsize; | ||
300 | while ( i < len ) { // delete lost items | ||
301 | if ( vec[i] ) { | ||
302 | deleteItem( vec[i] ); | ||
303 | numItems--; | ||
304 | } | ||
305 | i++; | ||
306 | } | ||
307 | } | ||
308 | if ( newsize == 0 ) { // vector becomes empty | ||
309 | DELETE(vec); | ||
310 | vec = 0; | ||
311 | len = numItems = 0; | ||
312 | return TRUE; | ||
313 | } | ||
314 | #if defined(DONT_USE_REALLOC) | ||
315 | if ( newsize == 0 ) { | ||
316 | DELETE(vec); | ||
317 | vec = 0; | ||
318 | return FALSE; | ||
319 | } | ||
320 | Item *newvec = NEW(Item,newsize); // manual realloc | ||
321 | memcpy( newvec, vec, (len < newsize ? len : newsize)*sizeof(Item) ); | ||
322 | DELETE(vec); | ||
323 | vec = newvec; | ||
324 | #else | ||
325 | vec = (Item*)realloc( (char *)vec, newsize*sizeof(Item) ); | ||
326 | #endif | ||
327 | } else { // create new vector | ||
328 | vec = NEW(Item,newsize); | ||
329 | len = numItems = 0; | ||
330 | } | ||
331 | Q_CHECK_PTR( vec ); | ||
332 | if ( !vec ) // no memory | ||
333 | return FALSE; | ||
334 | if ( newsize > len ) // init extra space added | ||
335 | memset( (void*)&vec[len], 0, (newsize-len)*sizeof(Item) ); | ||
336 | len = newsize; | ||
337 | return TRUE; | ||
338 | } | ||
339 | |||
340 | |||
341 | bool QGVector::fill( Item d, int flen ) // resize and fill vector | ||
342 | { | ||
343 | if ( flen < 0 ) | ||
344 | flen = len; // default: use vector length | ||
345 | else if ( !resize( flen ) ) | ||
346 | return FALSE; | ||
347 | for ( uint i=0; i<(uint)flen; i++ ) // insert d at every index | ||
348 | insert( i, d ); | ||
349 | return TRUE; | ||
350 | } | ||
351 | |||
352 | |||
353 | static QGVector *sort_vec=0; // current sort vector | ||
354 | |||
355 | |||
356 | #if defined(Q_C_CALLBACKS) | ||
357 | extern "C" { | ||
358 | #endif | ||
359 | |||
360 | #ifdef Q_OS_TEMP | ||
361 | static int _cdecl cmp_vec( const void *n1, const void *n2 ) | ||
362 | #else | ||
363 | static int cmp_vec( const void *n1, const void *n2 ) | ||
364 | #endif | ||
365 | { | ||
366 | return sort_vec->compareItems( *((QPtrCollection::Item*)n1), *((QPtrCollection::Item*)n2) ); | ||
367 | } | ||
368 | |||
369 | #if defined(Q_C_CALLBACKS) | ||
370 | } | ||
371 | #endif | ||
372 | |||
373 | |||
374 | void QGVector::sort() // sort vector | ||
375 | { | ||
376 | if ( count() == 0 ) // no elements | ||
377 | return; | ||
378 | register Item *start = &vec[0]; | ||
379 | register Item *end= &vec[len-1]; | ||
380 | Item tmp; | ||
381 | for (;;) { // put all zero elements behind | ||
382 | while ( start < end && *start != 0 ) | ||
383 | start++; | ||
384 | while ( end > start && *end == 0 ) | ||
385 | end--; | ||
386 | if ( start < end ) { | ||
387 | tmp = *start; | ||
388 | *start = *end; | ||
389 | *end = tmp; | ||
390 | } else { | ||
391 | break; | ||
392 | } | ||
393 | } | ||
394 | |||
395 | #ifdef QT_THREAD_SUPPORT | ||
396 | QMutexLocker locker( qt_global_mutexpool->get( &sort_vec ) ); | ||
397 | #endif // QT_THREAD_SUPPORT | ||
398 | |||
399 | sort_vec = (QGVector*)this; | ||
400 | qsort( vec, count(), sizeof(Item), cmp_vec ); | ||
401 | sort_vec = 0; | ||
402 | } | ||
403 | |||
404 | int QGVector::bsearch( Item d ) const // binary search; when sorted | ||
405 | { | ||
406 | if ( !len ) | ||
407 | return -1; | ||
408 | if ( !d ) { | ||
409 | #if defined(QT_CHECK_NULL) | ||
410 | qWarning( "QGVector::bsearch: Cannot search for null object" ); | ||
411 | #endif | ||
412 | return -1; | ||
413 | } | ||
414 | int n1 = 0; | ||
415 | int n2 = len - 1; | ||
416 | int mid = 0; | ||
417 | bool found = FALSE; | ||
418 | while ( n1 <= n2 ) { | ||
419 | int res; | ||
420 | mid = (n1 + n2)/2; | ||
421 | if ( vec[mid] == 0 ) // null item greater | ||
422 | res = -1; | ||
423 | else | ||
424 | res = ((QGVector*)this)->compareItems( d, vec[mid] ); | ||
425 | if ( res < 0 ) | ||
426 | n2 = mid - 1; | ||
427 | else if ( res > 0 ) | ||
428 | n1 = mid + 1; | ||
429 | else { // found it | ||
430 | found = TRUE; | ||
431 | break; | ||
432 | } | ||
433 | } | ||
434 | if ( !found ) | ||
435 | return -1; | ||
436 | // search to first of equal items | ||
437 | while ( (mid - 1 >= 0) && !((QGVector*)this)->compareItems(d, vec[mid-1]) ) | ||
438 | mid--; | ||
439 | return mid; | ||
440 | } | ||
441 | |||
442 | int QGVector::findRef( Item d, uint index) const // find exact item in vector | ||
443 | { | ||
444 | #if defined(QT_CHECK_RANGE) | ||
445 | if ( index > len ) { // range error | ||
446 | qWarning( "QGVector::findRef: Index %d out of range", index ); | ||
447 | return -1; | ||
448 | } | ||
449 | #endif | ||
450 | for ( uint i=index; i<len; i++ ) { | ||
451 | if ( vec[i] == d ) | ||
452 | return i; | ||
453 | } | ||
454 | return -1; | ||
455 | } | ||
456 | |||
457 | int QGVector::find( Item d, uint index ) const// find equal item in vector | ||
458 | { | ||
459 | #if defined(QT_CHECK_RANGE) | ||
460 | if ( index >= len ) { // range error | ||
461 | qWarning( "QGVector::find: Index %d out of range", index ); | ||
462 | return -1; | ||
463 | } | ||
464 | #endif | ||
465 | for ( uint i=index; i<len; i++ ) { | ||
466 | if ( vec[i] == 0 && d == 0 ) // found null item | ||
467 | return i; | ||
468 | if ( vec[i] && ((QGVector*)this)->compareItems( vec[i], d ) == 0 ) | ||
469 | return i; | ||
470 | } | ||
471 | return -1; | ||
472 | } | ||
473 | |||
474 | uint QGVector::containsRef( Item d ) const// get number of exact matches | ||
475 | { | ||
476 | uint count = 0; | ||
477 | for ( uint i=0; i<len; i++ ) { | ||
478 | if ( vec[i] == d ) | ||
479 | count++; | ||
480 | } | ||
481 | return count; | ||
482 | } | ||
483 | |||
484 | uint QGVector::contains( Item d ) const // get number of equal matches | ||
485 | { | ||
486 | uint count = 0; | ||
487 | for ( uint i=0; i<len; i++ ) { | ||
488 | if ( vec[i] == 0 && d == 0 ) // count null items | ||
489 | count++; | ||
490 | if ( vec[i] && ((QGVector*)this)->compareItems( vec[i], d ) == 0 ) | ||
491 | count++; | ||
492 | } | ||
493 | return count; | ||
494 | } | ||
495 | |||
496 | bool QGVector::insertExpand( uint index, Item d )// insert and grow if necessary | ||
497 | { | ||
498 | if ( index >= len ) { | ||
499 | if ( !resize( index+1 ) ) // no memory | ||
500 | return FALSE; | ||
501 | } | ||
502 | insert( index, d ); | ||
503 | return TRUE; | ||
504 | } | ||
505 | |||
506 | void QGVector::toList( QGList *list ) const// store items in list | ||
507 | { | ||
508 | list->clear(); | ||
509 | for ( uint i=0; i<len; i++ ) { | ||
510 | if ( vec[i] ) | ||
511 | list->append( vec[i] ); | ||
512 | } | ||
513 | } | ||
514 | |||
515 | |||
516 | void QGVector::warningIndexRange( uint i ) | ||
517 | { | ||
518 | #if defined(QT_CHECK_RANGE) | ||
519 | qWarning( "QGVector::operator[]: Index %d out of range", i ); | ||
520 | #else | ||
521 | Q_UNUSED( i ) | ||
522 | #endif | ||
523 | } | ||
524 | |||
525 | |||
526 | /***************************************************************************** | ||
527 | QGVector stream functions | ||
528 | *****************************************************************************/ | ||
529 | #ifndef QT_NO_DATASTREAM | ||
530 | QDataStream &operator>>( QDataStream &s, QGVector &vec ) | ||
531 | { // read vector | ||
532 | return vec.read( s ); | ||
533 | } | ||
534 | |||
535 | QDataStream &operator<<( QDataStream &s, const QGVector &vec ) | ||
536 | { // write vector | ||
537 | return vec.write( s ); | ||
538 | } | ||
539 | |||
540 | QDataStream &QGVector::read( QDataStream &s )// read vector from stream | ||
541 | { | ||
542 | uint num; | ||
543 | s >> num; // read number of items | ||
544 | clear(); // clear vector | ||
545 | resize( num ); | ||
546 | for (uint i=0; i<num; i++) { // read all items | ||
547 | Item d; | ||
548 | read( s, d ); | ||
549 | Q_CHECK_PTR( d ); | ||
550 | if ( !d ) // no memory | ||
551 | break; | ||
552 | vec[i] = d; | ||
553 | } | ||
554 | return s; | ||
555 | } | ||
556 | |||
557 | QDataStream &QGVector::write( QDataStream &s ) const | ||
558 | { // write vector to stream | ||
559 | uint num = count(); | ||
560 | s << num; // number of items to write | ||
561 | num = size(); | ||
562 | for (uint i=0; i<num; i++) { // write non-null items | ||
563 | if ( vec[i] ) | ||
564 | write( s, vec[i] ); | ||
565 | } | ||
566 | return s; | ||
567 | } | ||
568 | |||
569 | /* Returns whether v equals this vector or not */ | ||
570 | |||
571 | bool QGVector::operator==( const QGVector &v ) const | ||
572 | { | ||
573 | if ( size() != v.size() ) | ||
574 | return FALSE; | ||
575 | if ( count() != v.count() ) | ||
576 | return FALSE; | ||
577 | for ( int i = 0; i < (int)size(); ++i ) { | ||
578 | if ( ( (QGVector*)this )->compareItems( at( i ), v.at( i ) ) != 0 ) | ||
579 | return FALSE; | ||
580 | } | ||
581 | return TRUE; | ||
582 | } | ||
583 | |||
584 | #endif // QT_NO_DATASTREAM | ||