Chameleon

Chameleon Svn Source Tree

Root/branches/xZenu/src/util/doxygen/qtools/qgvector.cpp

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

Archive Download this file

Revision: 1406