/****************************************************************************

**

** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the Qt3Support module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, this file may be used under the terms of the GNU Lesser

** General Public License version 2.1 as published by the Free Software

** Foundation and appearing in the file LICENSE.LGPL included in the

** packaging of this file.  Please review the following information to

** ensure the GNU Lesser General Public License version 2.1 requirements

** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights.  These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#include "qglobal.h"

#if defined(Q_CC_BOR)

    // needed for qsort() because of a std namespace problem on Borland

#   include "qplatformdefs.h"

#elif defined(Q_WS_WIN)

    // needed for bsearch on some platforms

#   include "qt_windows.h"

#endif

#define	 Q3GARRAY_CPP

#include "q3garray.h"

#include <stdlib.h>

#include <string.h>

#ifndef QT_NO_THREAD

#  include "private/qmutexpool_p.h"

#endif

#if defined(Q_OS_WINCE)

#   include "qfunctions_wince.h"

#endif

QT_BEGIN_NAMESPACE

/*

  If USE_MALLOC isn't defined, we use new[] and delete[] to allocate

  memory. The documentation for QMemArray<T>::assign() explicitly

  mentions that the array is freed using free(), so don't mess around

  with USE_MALLOC unless you know what you're doing.

*/

#define USE_MALLOC

#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

/*!

  \class Q3GArray

  \reentrant

  \brief The Q3GArray class is an internal class for implementing the QMemArray class.

  \internal

  Q3GArray is a strictly internal class that acts as base class for the

  QMemArray template array.

  It contains an array of bytes and has no notion of an array element.

*/

/*!

  Constructs a null array.

*/

Q3GArray::Q3GArray()

{

    shd = newData();

    Q_CHECK_PTR(shd);

}

/*!

  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.

*/

Q3GArray::Q3GArray(int, int)

    : shd(0)

{

}

/*!

  Constructs an array with room for \a size bytes.

*/

Q3GArray::Q3GArray(int size)

{

    if (size < 0) {

#if defined(QT_CHECK_RANGE)

	qWarning("Q3GArray: Cannot allocate array with negative length");

#endif

	size = 0;

    }

    shd = newData();

    Q_CHECK_PTR(shd);

    if (size == 0)				// zero length

	return;

    shd->data = NEW(char,size);

    Q_CHECK_PTR(shd->data);

    shd->len =

#ifdef QT_Q3GARRAY_SPEED_OPTIM

	shd->maxl =

#endif

	size;

}

/*!

  Constructs a shallow copy of \a a.

*/

Q3GArray::Q3GArray(const Q3GArray &a)

{

    shd = a.shd;

    shd->ref();

}

/*!

  Dereferences the array data and deletes it if this was the last

  reference.

*/

Q3GArray::~Q3GArray()

{

    if (shd && shd->deref()) {		// delete when last reference

	if (shd->data)			// is lost

	    DELETE(shd->data);

	deleteData(shd);

	shd = 0;

    }

}

/*!

  \fn Q3GArray &Q3GArray::operator=(const Q3GArray &a)

  Assigns a shallow copy of \a a to this array and returns a reference to

  this array.  Equivalent to assign().

*/

/*!

  \fn void Q3GArray::detach()

  Detaches this array from shared array data.

*/

/*!

  \fn char *Q3GArray::data() const

  Returns a pointer to the actual array data.

*/

/*!

  \fn uint Q3GArray::nrefs() const

  Returns the reference count.

*/

/*!

  \fn uint Q3GArray::size() const

  Returns the size of the array, in bytes.

*/

/*!

  Returns true if this array is equal to \a a, otherwise false.

  The comparison is bitwise, of course.

*/

bool Q3GArray::isEqual(const Q3GArray &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;

}

/*!

  Resizes the array to \a newsize bytes. \a optim is either

  MemOptim (the default) or SpeedOptim.

*/

bool Q3GArray::resize(uint newsize, Optimization optim)

{

#ifndef QT_Q3GARRAY_SPEED_OPTIM

    Q_UNUSED(optim);

#endif

    if (newsize == shd->len

#ifdef QT_Q3GARRAY_SPEED_OPTIM

	 && newsize == shd->maxl

#endif

	) // nothing to do

	return true;

    if (newsize == 0) {			// remove array

	if (shd->data)

	    DELETE(shd->data);

	shd->data = 0;

	shd->len = 0;

#ifdef QT_Q3GARRAY_SPEED_OPTIM

	shd->maxl = 0;

#endif

	return true;

    }

    uint newmaxl = newsize;

#ifdef QT_Q3GARRAY_SPEED_OPTIM

    if (optim == SpeedOptim) {

	if (newsize <= shd->maxl &&

	     (newsize * 4 > shd->maxl || shd->maxl <= 4)) {

	    shd->len = newsize;

	    return true;

	}

	newmaxl = 4;

	while (newmaxl < newsize)

	    newmaxl *= 2;

	// try to spare some memory

	if (newmaxl >= 1024 * 1024 && newsize <= newmaxl - (newmaxl >> 2))

	    newmaxl -= newmaxl >> 2;

    }

    shd->maxl = newmaxl;

#endif

    if (shd->data) {				// existing data

#if defined(DONT_USE_REALLOC)

	char *newdata = NEW(char,newsize);	// manual realloc

	memcpy(newdata, shd->data, QMIN(shd->len,newmaxl));

	DELETE(shd->data);

	shd->data = newdata;

#else

	shd->data = (char *)realloc(shd->data, newmaxl);

#endif

    } else {

	shd->data = NEW(char,newmaxl);

    }

    if (!shd->data)				// no memory

	return false;

    shd->len = newsize;

    return true;

}

/*!\overload

*/

bool Q3GArray::resize(uint newsize)

{

    return resize(newsize, MemOptim);

}

/*!

  Fills the array with the repeated occurrences of \a d, which is

  \a sz bytes long.

  If \a len is specified as different from -1, then the array will be

  resized to \a len*sz before it is filled.

  Returns true if successful, or false if the memory cannot be allocated

  (only when \a len != -1).

  \sa resize()

*/

bool Q3GArray::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;

}

/*!

    \overload

  Shallow copy. Dereference the current array and references the data

  contained in \a a instead. Returns a reference to this array.

  \sa operator=()

*/

Q3GArray &Q3GArray::assign(const Q3GArray &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;

}

/*!

  Shallow copy. Dereference the current array and references the

  array data \a d, which contains \a len bytes.

  Returns a reference to this array.

  Do not delete \a d later, because Q3GArray takes care of that.

*/

Q3GArray &Q3GArray::assign(const char *d, uint len)

{

    if (shd->count > 1) {			// disconnect this

	shd->count--;

	shd = newData();

	Q_CHECK_PTR(shd);

    } else {

	if (shd->data)

	    DELETE(shd->data);

    }

    shd->data = (char *)d;

    shd->len =

#ifdef QT_Q3GARRAY_SPEED_OPTIM

	shd->maxl =

#endif

	len;

    return *this;

}

/*!

  Deep copy. Dereference the current array and obtains a copy of the data

  contained in \a a instead. Returns a reference to this array.

  \sa assign(), operator=()

*/

Q3GArray &Q3GArray::duplicate(const Q3GArray &a)

{

    if (a.shd == shd) {			// a.duplicate(a) !

	if (shd->count > 1) {

	    shd->count--;

	    register array_data *n = newData();

	    Q_CHECK_PTR(n);

	    if ((n->len=shd->len)) {

		n->data = NEW(char,n->len);

		Q_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();

	Q_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);

	Q_CHECK_PTR(shd->data);

	if (shd->data)

	    memcpy(shd->data, a.shd->data, a.shd->len);

    } else {

	shd->data = 0;

    }

    shd->len =

#ifdef QT_Q3GARRAY_SPEED_OPTIM

	shd->maxl =

#endif

	a.shd->len;

    if (oldptr)

	DELETE(oldptr);

    return *this;

}

/*!

    \overload

  Deep copy. Dereferences the current array and obtains a copy of

  \a len characters from array data \a d instead.  Returns a reference

  to this array.

  \sa assign(), operator=()

*/

Q3GArray &Q3GArray::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) {

	    if (shd->data != d)		// avoid self-assignment

		memcpy(shd->data, d, len);	// use same buffer

	    return *this;

	}

	data = NEW(char,len);

	Q_CHECK_PTR(data);

	memcpy(data, d, len);

    }

    if (shd->count > 1) {			// detach

	shd->count--;

	shd = newData();

	Q_CHECK_PTR(shd);

    } else {					// just a single reference

	if (shd->data)

	    DELETE(shd->data);

    }

    shd->data = data;

    shd->len =

#ifdef QT_Q3GARRAY_SPEED_OPTIM

	shd->maxl =

#endif

	len;

    return *this;

}

/*!

  Resizes this array to \a len bytes and copies the \a len bytes at

  address \a d into it.

  \warning This function disregards the reference count mechanism.  If

  other Q3GArrays reference the same data as this, all will be updated.

*/

void Q3GArray::store(const char *d, uint len)

{						// store, but not deref

    resize(len);

    memcpy(shd->data, d, len);

}

/*!

  \fn array_data *Q3GArray::sharedBlock() const

  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 Q3GArray::setSharedBlock(array_data *p)

  Sets the shared array block to \a 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.

*/

/*!

  Sets raw data and returns a reference to the array.

  Dereferences the current array and sets the new array data to \a d and

  the new array size to \a 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 sets QMemArray data without

  allocating memory or copying data.

  Example of intended use:

  \snippet doc/src/snippets/code/src_qt3support_tools_q3garray.cpp 0

  Example of misuse (do not do this):

  \snippet doc/src/snippets/code/src_qt3support_tools_q3garray.cpp 1

  \warning If you do not call resetRawData(), Q3GArray will attempt to

  deallocate or reallocate the raw data, which might not be too good.

  Be careful.

*/