Chameleon

Chameleon Svn Source Tree

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

Source at commit 1322 created 12 years 8 months ago.
By meklort, Add doxygen to utils folder
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
89QGArray::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
103QGArray::QGArray( int, int )
104{
105}
106
107/*!
108 \internal
109 Constructs an array with room for \e size bytes.
110*/
111
112QGArray::QGArray( int size )
113{
114 if ( size < 0 ) {
115#if defined(CHECK_RANGE)
116qWarning( "QGArray: Cannot allocate array with negative length" );
117#endif
118size = 0;
119 }
120 shd = newData();
121 CHECK_PTR( shd );
122 if ( size == 0 )// zero length
123return;
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
134QGArray::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
146QGArray::~QGArray()
147{
148 if ( shd && shd->deref() ) {// delete when last reference
149if ( shd->data )// is lost
150 DELETE(shd->data);
151deleteData( 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
194bool QGArray::isEqual( const QGArray &a ) const
195{
196 if ( size() != a.size() )// different size
197return FALSE;
198 if ( data() == a.data() )// has same data
199return 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
209bool QGArray::resize( uint newsize )
210{
211 if ( newsize == shd->len )// nothing to do
212return TRUE;
213 if ( newsize == 0 ) {// remove array
214duplicate( 0, 0 );
215return TRUE;
216 }
217 if ( shd->data ) {// existing data
218#if defined(DONT_USE_REALLOC)
219char *newdata = NEW(char,newsize);// manual realloc
220memcpy( newdata, shd->data, QMIN(shd->len,newsize) );
221DELETE(shd->data);
222shd->data = newdata;
223#else
224shd->data = (char *)realloc( shd->data, newsize );
225#endif
226 } else {
227shd->data = NEW(char,newsize);
228 }
229 CHECK_PTR( shd->data );
230 if ( !shd->data )// no memory
231return 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
249bool QGArray::fill( const char *d, int len, uint sz )
250{
251 if ( len < 0 )
252len = shd->len/sz;// default: use array length
253 else if ( !resize( len*sz ) )
254return FALSE;
255 if ( sz == 1 )// 8 bit elements
256memset( data(), *d, len );
257 else if ( sz == 4 ) {// 32 bit elements
258register Q_INT32 *x = (Q_INT32*)data();
259Q_INT32 v = *((Q_INT32*)d);
260while ( len-- )
261 *x++ = v;
262 } else if ( sz == 2 ) {// 16 bit elements
263register Q_INT16 *x = (Q_INT16*)data();
264Q_INT16 v = *((Q_INT16*)d);
265while ( len-- )
266 *x++ = v;
267 } else {// any other size elements
268register char *x = data();
269while ( 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
284QGArray &QGArray::assign( const QGArray &a )
285{
286 a.shd->ref();// avoid 'a = a'
287 if ( shd->deref() ) {// delete when last reference
288if ( shd->data )// is lost
289 DELETE(shd->data);
290deleteData( 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
305QGArray &QGArray::assign( const char *d, uint len )
306{
307 if ( shd->count > 1 ) {// disconnect this
308shd->count--;
309shd = newData();
310CHECK_PTR( shd );
311 } else {
312if ( 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
327QGArray &QGArray::duplicate( const QGArray &a )
328{
329 if ( a.shd == shd ) {// a.duplicate(a) !
330if ( shd->count > 1 ) {
331 shd->count--;
332 register array_data *n = newData();
333 CHECK_PTR( n );
334 if ( (n->len=shd->len) ) {
335n->data = NEW(char,n->len);
336CHECK_PTR( n->data );
337if ( n->data )
338 memcpy( n->data, shd->data, n->len );
339 } else {
340n->data = 0;
341 }
342 shd = n;
343}
344return *this;
345 }
346 char *oldptr = 0;
347 if ( shd->count > 1 ) {// disconnect this
348shd->count--;
349shd = newData();
350CHECK_PTR( shd );
351 } else {// delete after copy was made
352oldptr = shd->data;
353 }
354 if ( a.shd->len ) {// duplicate data
355shd->data = NEW(char,a.shd->len);
356CHECK_PTR( shd->data );
357if ( shd->data )
358 memcpy( shd->data, a.shd->data, a.shd->len );
359 } else {
360shd->data = 0;
361 }
362 shd->len = a.shd->len;
363 if ( oldptr )
364DELETE(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
375QGArray &QGArray::duplicate( const char *d, uint len )
376{
377 char *data;
378 if ( d == 0 || len == 0 ) {
379data = 0;
380len = 0;
381 } else {
382if ( shd->count == 1 && shd->len == len ) {
383 memcpy( shd->data, d, len );// use same buffer
384 return *this;
385}
386data = NEW(char,len);
387CHECK_PTR( data );
388memcpy( data, d, len );
389 }
390 if ( shd->count > 1 ) {// detach
391shd->count--;
392shd = newData();
393CHECK_PTR( shd );
394 } else {// just a single reference
395if ( 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
412void 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 QByteArraya;
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 QByteArraya, 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
483QGArray &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
499void QGArray::resetRawData( const char *d, uint len )
500{
501 if ( d != shd->data || len != shd->len ) {
502#if defined(CHECK_STATE)
503qWarning( "QGArray::resetRawData: Inconsistent arguments" );
504#endif
505return;
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
522int QGArray::find( const char *d, uint index, uint sz ) const
523{
524 index *= sz;
525 if ( index >= shd->len ) {
526#if defined(CHECK_RANGE)
527qWarning( "QGArray::find: Index %d out of range", index/sz );
528#endif
529return -1;
530 }
531 register uint i;
532 uint ii;
533 switch ( sz ) {
534case 1: {// 8 bit elements
535 register char *x = data() + index;
536 char v = *d;
537 for ( i=index; i<shd->len; i++ ) {
538if ( *x++ == v )
539 break;
540 }
541 ii = i;
542 }
543 break;
544case 2: {// 16 bit elements
545 register Q_INT16 *x = (Q_INT16*)(data() + index);
546 Q_INT16 v = *((Q_INT16*)d);
547 for ( i=index; i<shd->len; i+=2 ) {
548if ( *x++ == v )
549 break;
550 }
551 ii = i/2;
552 }
553 break;
554case 4: {// 32 bit elements
555 register Q_INT32 *x = (Q_INT32*)(data() + index);
556 Q_INT32 v = *((Q_INT32*)d);
557 for ( i=index; i<shd->len; i+=4 ) {
558if ( *x++ == v )
559 break;
560 }
561 ii = i/4;
562 }
563 break;
564default: {// any size elements
565 for ( i=index; i<shd->len; i+=sz ) {
566if ( 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
584int QGArray::contains( const char *d, uint sz ) const
585{
586 register uint i = shd->len;
587 int count = 0;
588 switch ( sz ) {
589case 1: {// 8 bit elements
590 register char *x = data();
591 char v = *d;
592 while ( i-- ) {
593if ( *x++ == v )
594 count++;
595 }
596 }
597 break;
598case 2: {// 16 bit elements
599 register Q_INT16 *x = (Q_INT16*)data();
600 Q_INT16 v = *((Q_INT16*)d);
601 i /= 2;
602 while ( i-- ) {
603if ( *x++ == v )
604 count++;
605 }
606 }
607 break;
608case 4: {// 32 bit elements
609 register Q_INT32 *x = (Q_INT32*)data();
610 Q_INT32 v = *((Q_INT32*)d);
611 i /= 4;
612 while ( i-- ) {
613if ( *x++ == v )
614 count++;
615 }
616 }
617 break;
618default: {// any size elements
619 for ( i=0; i<shd->len; i+=sz ) {
620if ( memcmp(d, &shd->data[i], sz) == 0 )
621 count++;
622 }
623 }
624 break;
625 }
626 return count;
627}
628
629static int cmp_item_size = 0;
630
631#if defined(Q_C_CALLBACKS)
632extern "C" {
633#endif
634
635static int cmp_arr( const void *n1, const void *n2 )
636{
637 return ( n1 && n2 ) ? memcmp( n1, n2, cmp_item_size )
638 : (int)((long)n1 - (long)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
652void QGArray::sort( uint sz )
653{
654 int numItems = size() / sz;
655 if ( numItems < 2 )
656return;
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
667int QGArray::bsearch( const char *d, uint sz ) const
668{
669 int numItems = size() / sz;
670 if ( !numItems )
671return -1;
672 cmp_item_size = sz;
673 char* r = (char*)::bsearch( d, shd->data, numItems, sz, cmp_arr );
674 if ( !r )
675return -1;
676 while( (r >= shd->data + sz) && (cmp_arr( r - sz, d ) == 0) )
677r -= 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
700bool QGArray::setExpand( uint index, const char *d, uint sz )
701{
702 index *= sz;
703 if ( index >= shd->len ) {
704if ( !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
717void 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
732QGArray::array_data * QGArray::newData()
733{
734 return new array_data;
735}
736
737
738/*!
739 \internal
740 Deletes the shared array block.
741*/
742
743void QGArray::deleteData( array_data *p )
744{
745 delete p;
746 p = 0;
747}
748

Archive Download this file

Revision: 1322