summaryrefslogtreecommitdiffstats
path: root/qtools/qgarray.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'qtools/qgarray.cpp')
-rw-r--r--qtools/qgarray.cpp747
1 files changed, 747 insertions, 0 deletions
diff --git a/qtools/qgarray.cpp b/qtools/qgarray.cpp
new file mode 100644
index 0000000..efc9de0
--- /dev/null
+++ b/qtools/qgarray.cpp
@@ -0,0 +1,747 @@
+/****************************************************************************
+**
+**
+** Implementation of QGArray class
+**
+** Created : 930906
+**
+** Copyright (C) 1992-2000 Trolltech AS. All rights reserved.
+**
+** This file is part of the tools module of the Qt GUI Toolkit.
+**
+** This file may be distributed under the terms of the Q Public License
+** as defined by Trolltech AS of Norway and appearing in the file
+** LICENSE.QPL included in the packaging of this file.
+**
+** This file may be distributed and/or modified under the terms of the
+** GNU General Public License version 2 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file.
+**
+** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
+** licenses may use this file in accordance with the Qt Commercial License
+** Agreement provided with the Software.
+**
+** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+**
+** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
+** information about Qt Commercial License Agreements.
+** See http://www.trolltech.com/qpl/ for QPL licensing information.
+** See http://www.trolltech.com/gpl/ for GPL licensing information.
+**
+** Contact info@trolltech.com if any conditions of this licensing are
+** not clear to you.
+**
+**********************************************************************/
+
+#define QGARRAY_CPP
+#include "qgarray.h"
+#include "qstring.h"
+#include <stdlib.h>
+
+#define USE_MALLOC // comment to use new/delete
+
+#undef NEW
+#undef DELETE
+
+#if defined(USE_MALLOC)
+#define NEW(type,size) ((type*)malloc(size*sizeof(type)))
+#define DELETE(array) (free((char*)array))
+#else
+#define NEW(type,size) (new type[size])
+#define DELETE(array) (delete[] array)
+#define DONT_USE_REALLOC // comment to use realloc()
+#endif
+
+
+// NOT REVISED
+/*!
+ \class QShared qshared.h
+ \brief The QShared struct is internally used for implementing shared classes.
+
+ It only contains a reference count and member functions to increment and
+ decrement it.
+
+ Shared classes normally have internal classes that inherit QShared and
+ add the shared data.
+
+ \sa \link shclass.html Shared Classes\endlink
+*/
+
+
+/*!
+ \class QGArray qgarray.h
+ \brief The QGArray class is an internal class for implementing the QArray class.
+
+ QGArray is a strictly internal class that acts as base class for the
+ QArray template array.
+
+ It contains an array of bytes and has no notion of an array element.
+*/
+
+
+/*!
+ \internal
+ Constructs a null array.
+*/
+
+QGArray::QGArray()
+{
+ shd = newData();
+ CHECK_PTR( shd );
+}
+
+/*!
+ \internal
+ Dummy constructor; does not allocate any data.
+
+ This constructor does not initialize any array data so subclasses
+ must do it. The intention is to make the code more efficient.
+*/
+
+QGArray::QGArray( int, int )
+{
+}
+
+/*!
+ \internal
+ Constructs an array with room for \e size bytes.
+*/
+
+QGArray::QGArray( int size )
+{
+ if ( size < 0 ) {
+#if defined(CHECK_RANGE)
+ qWarning( "QGArray: Cannot allocate array with negative length" );
+#endif
+ size = 0;
+ }
+ shd = newData();
+ CHECK_PTR( shd );
+ if ( size == 0 ) // zero length
+ return;
+ shd->data = NEW(char,size);
+ CHECK_PTR( shd->data );
+ shd->len = size;
+}
+
+/*!
+ \internal
+ Constructs a shallow copy of \e a.
+*/
+
+QGArray::QGArray( const QGArray &a )
+{
+ shd = a.shd;
+ shd->ref();
+}
+
+/*!
+ \internal
+ Dereferences the array data and deletes it if this was the last
+ reference.
+*/
+
+QGArray::~QGArray()
+{
+ if ( shd && shd->deref() ) { // delete when last reference
+ if ( shd->data ) // is lost
+ DELETE(shd->data);
+ deleteData( shd );
+ }
+}
+
+
+/*!
+ \fn QGArray &QGArray::operator=( const QGArray &a )
+ \internal
+ Assigns a shallow copy of \e a to this array and returns a reference to
+ this array. Equivalent to assign().
+*/
+
+/*!
+ \fn void QGArray::detach()
+ \internal
+ Detaches this array from shared array data.
+*/
+
+/*!
+ \fn char *QGArray::data() const
+ \internal
+ Returns a pointer to the actual array data.
+*/
+
+/*!
+ \fn uint QGArray::nrefs() const
+ \internal
+ Returns the reference count.
+*/
+
+/*!
+ \fn uint QGArray::size() const
+ \internal
+ Returns the size of the array, in bytes.
+*/
+
+
+/*!
+ \internal
+ Returns TRUE if this array is equal to \e a, otherwise FALSE.
+ The comparison is bitwise, of course.
+*/
+
+bool QGArray::isEqual( const QGArray &a ) const
+{
+ if ( size() != a.size() ) // different size
+ return FALSE;
+ if ( data() == a.data() ) // has same data
+ return TRUE;
+ return (size() ? memcmp( data(), a.data(), size() ) : 0) == 0;
+}
+
+
+/*!
+ \internal
+ Resizes the array to \e newsize bytes.
+*/
+
+bool QGArray::resize( uint newsize )
+{
+ if ( newsize == shd->len ) // nothing to do
+ return TRUE;
+ if ( newsize == 0 ) { // remove array
+ duplicate( 0, 0 );
+ return TRUE;
+ }
+ if ( shd->data ) { // existing data
+#if defined(DONT_USE_REALLOC)
+ char *newdata = NEW(char,newsize); // manual realloc
+ memcpy( newdata, shd->data, QMIN(shd->len,newsize) );
+ DELETE(shd->data);
+ shd->data = newdata;
+#else
+ shd->data = (char *)realloc( shd->data, newsize );
+#endif
+ } else {
+ shd->data = NEW(char,newsize);
+ }
+ CHECK_PTR( shd->data );
+ if ( !shd->data ) // no memory
+ return FALSE;
+ shd->len = newsize;
+ return TRUE;
+}
+
+/*!
+ \internal
+ Fills the array with the repeated occurrences of \e d, which is
+ \e sz bytes long.
+ If \e len is specified as different from -1, then the array will be
+ resized to \e len*sz before it is filled.
+
+ Returns TRUE if successful, or FALSE if the memory cannot be allocated
+ (only when \e len != -1).
+
+ \sa resize()
+*/
+
+bool QGArray::fill( const char *d, int len, uint sz )
+{
+ if ( len < 0 )
+ len = shd->len/sz; // default: use array length
+ else if ( !resize( len*sz ) )
+ return FALSE;
+ if ( sz == 1 ) // 8 bit elements
+ memset( data(), *d, len );
+ else if ( sz == 4 ) { // 32 bit elements
+ register Q_INT32 *x = (Q_INT32*)data();
+ Q_INT32 v = *((Q_INT32*)d);
+ while ( len-- )
+ *x++ = v;
+ } else if ( sz == 2 ) { // 16 bit elements
+ register Q_INT16 *x = (Q_INT16*)data();
+ Q_INT16 v = *((Q_INT16*)d);
+ while ( len-- )
+ *x++ = v;
+ } else { // any other size elements
+ register char *x = data();
+ while ( len-- ) { // more complicated
+ memcpy( x, d, sz );
+ x += sz;
+ }
+ }
+ return TRUE;
+}
+
+/*!
+ \internal
+ Shallow copy. Dereference the current array and references the data
+ contained in \e a instead. Returns a reference to this array.
+ \sa operator=()
+*/
+
+QGArray &QGArray::assign( const QGArray &a )
+{
+ a.shd->ref(); // avoid 'a = a'
+ if ( shd->deref() ) { // delete when last reference
+ if ( shd->data ) // is lost
+ DELETE(shd->data);
+ deleteData( shd );
+ }
+ shd = a.shd;
+ return *this;
+}
+
+/*!
+ \internal
+ Shallow copy. Dereference the current array and references the
+ array data \e d, which contains \e len bytes.
+ Returns a reference to this array.
+
+ Do not delete \e d later, because QGArray takes care of that.
+*/
+
+QGArray &QGArray::assign( const char *d, uint len )
+{
+ if ( shd->count > 1 ) { // disconnect this
+ shd->count--;
+ shd = newData();
+ CHECK_PTR( shd );
+ } else {
+ if ( shd->data )
+ DELETE(shd->data);
+ }
+ shd->data = (char *)d;
+ shd->len = len;
+ return *this;
+}
+
+/*!
+ \internal
+ Deep copy. Dereference the current array and obtains a copy of the data
+ contained in \e a instead. Returns a reference to this array.
+ \sa assign(), operator=()
+*/
+
+QGArray &QGArray::duplicate( const QGArray &a )
+{
+ if ( a.shd == shd ) { // a.duplicate(a) !
+ if ( shd->count > 1 ) {
+ shd->count--;
+ register array_data *n = newData();
+ CHECK_PTR( n );
+ if ( (n->len=shd->len) ) {
+ n->data = NEW(char,n->len);
+ CHECK_PTR( n->data );
+ if ( n->data )
+ memcpy( n->data, shd->data, n->len );
+ } else {
+ n->data = 0;
+ }
+ shd = n;
+ }
+ return *this;
+ }
+ char *oldptr = 0;
+ if ( shd->count > 1 ) { // disconnect this
+ shd->count--;
+ shd = newData();
+ CHECK_PTR( shd );
+ } else { // delete after copy was made
+ oldptr = shd->data;
+ }
+ if ( a.shd->len ) { // duplicate data
+ shd->data = NEW(char,a.shd->len);
+ CHECK_PTR( shd->data );
+ if ( shd->data )
+ memcpy( shd->data, a.shd->data, a.shd->len );
+ } else {
+ shd->data = 0;
+ }
+ shd->len = a.shd->len;
+ if ( oldptr )
+ DELETE(oldptr);
+ return *this;
+}
+
+/*!
+ \internal
+ Deep copy. Dereferences the current array and obtains a copy of the
+ array data \e d instead. Returns a reference to this array.
+ \sa assign(), operator=()
+*/
+
+QGArray &QGArray::duplicate( const char *d, uint len )
+{
+ char *data;
+ if ( d == 0 || len == 0 ) {
+ data = 0;
+ len = 0;
+ } else {
+ if ( shd->count == 1 && shd->len == len ) {
+ memcpy( shd->data, d, len ); // use same buffer
+ return *this;
+ }
+ data = NEW(char,len);
+ CHECK_PTR( data );
+ memcpy( data, d, len );
+ }
+ if ( shd->count > 1 ) { // detach
+ shd->count--;
+ shd = newData();
+ CHECK_PTR( shd );
+ } else { // just a single reference
+ if ( shd->data )
+ DELETE(shd->data);
+ }
+ shd->data = data;
+ shd->len = len;
+ return *this;
+}
+
+/*!
+ \internal
+ Resizes this array to \e len bytes and copies the \e len bytes at
+ address \e into it.
+
+ \warning This function disregards the reference count mechanism. If
+ other QGArrays reference the same data as this, all will be updated.
+*/
+
+void QGArray::store( const char *d, uint len )
+{ // store, but not deref
+ resize( len );
+ memcpy( shd->data, d, len );
+}
+
+
+/*!
+ \fn array_data *QGArray::sharedBlock() const
+ \internal
+ Returns a pointer to the shared array block.
+
+ \warning
+
+ Do not use this function. Using it is begging for trouble. We dare
+ not remove it, for fear of breaking code, but we \e strongly
+ discourage new use of it.
+*/
+
+/*!
+ \fn void QGArray::setSharedBlock( array_data *p )
+ \internal
+ Sets the shared array block to \e p.
+
+ \warning
+
+ Do not use this function. Using it is begging for trouble. We dare
+ not remove it, for fear of breaking code, but we \e strongly
+ discourage new use of it.
+*/
+
+
+/*!
+ \internal
+ Sets raw data and returns a reference to the array.
+
+ Dereferences the current array and sets the new array data to \e d and
+ the new array size to \e len. Do not attempt to resize or re-assign the
+ array data when raw data has been set.
+ Call resetRawData(d,len) to reset the array.
+
+ Setting raw data is useful because it set QArray data without allocating
+ memory or copying data.
+
+ Example of intended use:
+ \code
+ static uchar bindata[] = { 231, 1, 44, ... };
+ QByteArray a;
+ a.setRawData( bindata, sizeof(bindata) ); // a points to bindata
+ QDataStream s( a, IO_ReadOnly ); // open on a's data
+ s >> <something>; // read raw bindata
+ s.close();
+ a.resetRawData( bindata, sizeof(bindata) ); // finished
+ \endcode
+
+ Example of misuse (do not do this):
+ \code
+ static uchar bindata[] = { 231, 1, 44, ... };
+ QByteArray a, b;
+ a.setRawData( bindata, sizeof(bindata) ); // a points to bindata
+ a.resize( 8 ); // will crash
+ b = a; // will crash
+ a[2] = 123; // might crash
+ // forget to resetRawData - will crash
+ \endcode
+
+ \warning If you do not call resetRawData(), QGArray will attempt to
+ deallocate or reallocate the raw data, which might not be too good.
+ Be careful.
+*/
+
+QGArray &QGArray::setRawData( const char *d, uint len )
+{
+ duplicate( 0, 0 ); // set null data
+ shd->data = (char *)d;
+ shd->len = len;
+ return *this;
+}
+
+/*!
+ \internal
+ Resets raw data.
+
+ The arguments must be the data and length that were passed to
+ setRawData(). This is for consistency checking.
+*/
+
+void QGArray::resetRawData( const char *d, uint len )
+{
+ if ( d != shd->data || len != shd->len ) {
+#if defined(CHECK_STATE)
+ qWarning( "QGArray::resetRawData: Inconsistent arguments" );
+#endif
+ return;
+ }
+ shd->data = 0;
+ shd->len = 0;
+}
+
+
+/*!
+ \internal
+ Finds the first occurrence of \e d in the array from position \e index,
+ where \e sz is the size of the \e d element.
+
+ Note that \e index is given in units of \e sz, not bytes.
+
+ This function only compares whole cells, not bytes.
+*/
+
+int QGArray::find( const char *d, uint index, uint sz ) const
+{
+ index *= sz;
+ if ( index >= shd->len ) {
+#if defined(CHECK_RANGE)
+ qWarning( "QGArray::find: Index %d out of range", index/sz );
+#endif
+ return -1;
+ }
+ register uint i;
+ uint ii;
+ switch ( sz ) {
+ case 1: { // 8 bit elements
+ register char *x = data() + index;
+ char v = *d;
+ for ( i=index; i<shd->len; i++ ) {
+ if ( *x++ == v )
+ break;
+ }
+ ii = i;
+ }
+ break;
+ case 2: { // 16 bit elements
+ register Q_INT16 *x = (Q_INT16*)(data() + index);
+ Q_INT16 v = *((Q_INT16*)d);
+ for ( i=index; i<shd->len; i+=2 ) {
+ if ( *x++ == v )
+ break;
+ }
+ ii = i/2;
+ }
+ break;
+ case 4: { // 32 bit elements
+ register Q_INT32 *x = (Q_INT32*)(data() + index);
+ Q_INT32 v = *((Q_INT32*)d);
+ for ( i=index; i<shd->len; i+=4 ) {
+ if ( *x++ == v )
+ break;
+ }
+ ii = i/4;
+ }
+ break;
+ default: { // any size elements
+ for ( i=index; i<shd->len; i+=sz ) {
+ if ( memcmp( d, &shd->data[i], sz ) == 0 )
+ break;
+ }
+ ii = i/sz;
+ }
+ break;
+ }
+ return i<shd->len ? (int)ii : -1;
+}
+
+/*!
+ \internal
+ Returns the number of occurrences of \e d in the array, where \e sz is
+ the size of the \e d element.
+
+ This function only compares whole cells, not bytes.
+*/
+
+int QGArray::contains( const char *d, uint sz ) const
+{
+ register uint i = shd->len;
+ int count = 0;
+ switch ( sz ) {
+ case 1: { // 8 bit elements
+ register char *x = data();
+ char v = *d;
+ while ( i-- ) {
+ if ( *x++ == v )
+ count++;
+ }
+ }
+ break;
+ case 2: { // 16 bit elements
+ register Q_INT16 *x = (Q_INT16*)data();
+ Q_INT16 v = *((Q_INT16*)d);
+ i /= 2;
+ while ( i-- ) {
+ if ( *x++ == v )
+ count++;
+ }
+ }
+ break;
+ case 4: { // 32 bit elements
+ register Q_INT32 *x = (Q_INT32*)data();
+ Q_INT32 v = *((Q_INT32*)d);
+ i /= 4;
+ while ( i-- ) {
+ if ( *x++ == v )
+ count++;
+ }
+ }
+ break;
+ default: { // any size elements
+ for ( i=0; i<shd->len; i+=sz ) {
+ if ( memcmp(d, &shd->data[i], sz) == 0 )
+ count++;
+ }
+ }
+ break;
+ }
+ return count;
+}
+
+static int cmp_item_size = 0;
+
+#if defined(Q_C_CALLBACKS)
+extern "C" {
+#endif
+
+static int cmp_arr( const void *n1, const void *n2 )
+{
+ return ( n1 && n2 ) ? memcmp( n1, n2, cmp_item_size )
+ : (int)((long)n1 - (long)n2);
+ // Qt 3.0: Add a virtual compareItems() method and call that instead
+}
+
+#if defined(Q_C_CALLBACKS)
+}
+#endif
+
+/*!
+ \internal
+
+ Sort the array.
+*/
+
+void QGArray::sort( uint sz )
+{
+ int numItems = size() / sz;
+ if ( numItems < 2 )
+ return;
+ cmp_item_size = sz;
+ qsort( shd->data, numItems, sz, cmp_arr );
+}
+
+/*!
+ \internal
+
+ Binary search; assumes sorted array
+*/
+
+int QGArray::bsearch( const char *d, uint sz ) const
+{
+ int numItems = size() / sz;
+ if ( !numItems )
+ return -1;
+ cmp_item_size = sz;
+ char* r = (char*)::bsearch( d, shd->data, numItems, sz, cmp_arr );
+ if ( !r )
+ return -1;
+ while( (r >= shd->data + sz) && (cmp_arr( r - sz, d ) == 0) )
+ r -= sz; // search to first of equal elements; bsearch is undef
+ return (int)(( r - shd->data ) / sz);
+}
+
+
+/*!
+ \fn char *QGArray::at( uint index ) const
+ \internal
+ Returns a pointer to the byte at offset \e index in the array.
+*/
+
+/*!
+ \internal
+ Expand the array if necessary, and copies (the first part of) its
+ contents from the \e index*zx bytes at \e d.
+
+ Returns TRUE if the operation succeeds, FALSE if it runs out of
+ memory.
+
+ \warning This function disregards the reference count mechanism. If
+ other QGArrays reference the same data as this, all will be changed.
+*/
+
+bool QGArray::setExpand( uint index, const char *d, uint sz )
+{
+ index *= sz;
+ if ( index >= shd->len ) {
+ if ( !resize( index+sz ) ) // no memory
+ return FALSE;
+ }
+ memcpy( data() + index, d, sz );
+ return TRUE;
+}
+
+
+/*!
+ \internal
+ Prints a warning message if at() or [] is given a bad index.
+*/
+
+void QGArray::msg_index( uint index )
+{
+#if defined(CHECK_RANGE)
+ qWarning( "QGArray::at: Absolute index %d out of range", index );
+#else
+ Q_UNUSED( index )
+#endif
+}
+
+
+/*!
+ \internal
+ Returns a new shared array block.
+*/
+
+QGArray::array_data * QGArray::newData()
+{
+ return new array_data;
+}
+
+
+/*!
+ \internal
+ Deletes the shared array block.
+*/
+
+void QGArray::deleteData( array_data *p )
+{
+ delete p;
+ p = 0;
+}