1 /****************************************************************************

     2 **

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

     4 ** All rights reserved.

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

     6 **

     7 ** This file is part of the documentation of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

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

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

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

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

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

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

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

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

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

    23 **

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

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

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

    27 **

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

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

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 /*!

    43     \class Q3MemArray

    44     \brief The Q3MemArray class is a template class that provides arrays of simple types.

    45     \compat

    46 

    47     Q3MemArray is implemented as a template class. Define a template

    48     instance Q3MemArray\<X\> to create an array that contains X items.

    49 

    50     Q3MemArray stores the array elements directly in the array. It can

    51     only deal with simple types (i.e. C++ types, structs, and classes

    52     that have no constructors, destructors, or virtual functions).

    53     Q3MemArray uses bitwise operations to copy and compare array

    54     elements. 

    55 

    56     The Q3PtrVector collection class is also a kind of array. Like most

    57     old Qt collection classes, it uses pointers to the contained items.

    58 

    59     Q3MemArray uses explicit sharing with a

    60     reference count. If more than one array shares common data and one

    61     of the arrays is modified, all the arrays are modified.

    62 

    63     The benefit of sharing is that a program does not need to duplicate

    64     data when it is not required, which results in lower memory use

    65     and less copying of data.

    66 

    67     Example:

    68     \snippet doc/src/snippets/code/doc_src_q3memarray.qdoc 0

    69 

    70     Program output:

    71     \snippet doc/src/snippets/code/doc_src_q3memarray.qdoc 1

    72 

    73     Note concerning the use of Q3MemArray for manipulating structs or

    74     classes: Compilers will often pad the size of structs of odd sizes

    75     up to the nearest word boundary. This will then be the size

    76     Q3MemArray will use for its bitwise element comparisons. Because

    77     the remaining bytes will typically be uninitialized, this can

    78     cause find() etc. to fail to find the element. Example:

    79 

    80     \snippet doc/src/snippets/code/doc_src_q3memarray.qdoc 2

    81 

    82     To work around this, make sure that you use a struct where

    83     sizeof() returns the same as the sum of the sizes of the members

    84     either by changing the types of the struct members or by adding

    85     dummy members.

    86 

    87     Q3MemArray data can be traversed by iterators (see begin() and

    88     end()). The number of items is returned by count(). The array can

    89     be resized with resize() and filled using fill().

    90 

    91     You can make a shallow copy of the array with assign() (or

    92     operator=()) and a deep copy with duplicate().

    93 

    94     Search for values in the array with find() and contains(). For

    95     sorted arrays (see sort()) you can search using bsearch().

    96 

    97     You can set the data directly using setRawData() and

    98     resetRawData(), although this requires care.

    99 */

   100 

   101 /*! \fn Q3MemArray::operator QVector<type>() const

   102 

   103     Automatically converts the Q3MemArray<type> into a QVector<type>.

   104 */

   105 

   106 /*! \typedef Q3MemArray::Iterator

   107     A Q3MemArray iterator.

   108     \sa begin() end()

   109 */

   110 /*! \typedef Q3MemArray::ConstIterator

   111     A const Q3MemArray iterator.

   112     \sa begin() end()

   113 */

   114 /*! \typedef Q3MemArray::ValueType

   115     \internal

   116 */

   117 

   118 /*!

   119     \fn Q3MemArray::Q3MemArray()

   120 

   121     Constructs a null array.

   122 

   123     \sa isNull()

   124 */

   125 

   126 /*!

   127     \fn Q3MemArray::Q3MemArray( int size )

   128 

   129     Constructs an array with room for \a size elements. Makes a null

   130     array if \a size == 0.

   131 

   132     The elements are left uninitialized.

   133 

   134     \sa resize(), isNull()

   135 */

   136 

   137 /*!

   138     \fn Q3MemArray::Q3MemArray( const Q3MemArray<type> &a )

   139 

   140     Constructs a shallow copy of \a a.

   141 

   142     \sa assign()

   143 */

   144 

   145 /*!

   146     \fn Q3MemArray::Q3MemArray(const QVector<type> &vector)

   147 

   148     Constructs a copy of \a vector.

   149 */

   150 

   151 /*!

   152     \fn Q3MemArray::Q3MemArray(int arg1, int arg2)

   153 

   154     Constructs an array \e{without allocating} array space. The

   155     arguments \a arg1 and \a arg2 should be zero. Use at your own

   156     risk.

   157 */

   158 

   159 /*!

   160     \fn Q3MemArray::~Q3MemArray()

   161 

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

   163     reference.

   164 */

   165 

   166 /*!

   167     \fn Q3MemArray<type> &Q3MemArray::operator=( const Q3MemArray<type> &a )

   168 

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

   170     reference to this array.

   171 

   172     Equivalent to assign( a ).

   173 */

   174 

   175 /*!

   176     \fn type *Q3MemArray::data() const

   177 

   178     Returns a pointer to the actual array data.

   179 

   180     The array is a null array if data() == 0 (null pointer).

   181 

   182     \sa isNull()

   183 */

   184 

   185 /*!

   186     \fn uint Q3MemArray::nrefs() const

   187 

   188     Returns the reference count for the shared array data. This

   189     reference count is always greater than zero.

   190 */

   191 

   192 /*!

   193     \fn uint Q3MemArray::size() const

   194 

   195     Returns the size of the array (maximum number of elements).

   196 

   197     The array is a null array if size() == 0.

   198 

   199     \sa isNull(), resize()

   200 */

   201 

   202 /*!

   203     \fn uint Q3MemArray::count() const

   204 

   205     Returns the same as size().

   206 

   207     \sa size()

   208 */

   209 

   210 /*!

   211     \fn bool Q3MemArray::isEmpty() const

   212 

   213     Returns TRUE if the array is empty; otherwise returns FALSE.

   214 

   215     isEmpty() is equivalent to isNull() for Q3MemArray (unlike

   216     QString).

   217 */

   218 

   219 /*!

   220     \fn bool Q3MemArray::isNull() const

   221 

   222     Returns TRUE if the array is null; otherwise returns FALSE.

   223 

   224     A null array has size() == 0 and data() == 0.

   225 */

   226 

   227 /*!

   228     \fn bool Q3MemArray::resize( uint size, Optimization optim )

   229 

   230     Resizes (expands or shrinks) the array to \a size elements. The

   231     array becomes a null array if \a size == 0.

   232 

   233     Returns TRUE if successful, or FALSE if the memory cannot be

   234     allocated.

   235 

   236     New elements are not initialized.

   237 

   238     \a optim is either Q3GArray::MemOptim (the default) or

   239     Q3GArray::SpeedOptim. When optimizing for speed rather than memory

   240     consumption, the array uses a smart grow and shrink algorithm that

   241     might allocate more memory than is actually needed for \a size

   242     elements. This speeds up subsequent resize operations, for example

   243     when appending many elements to an array, since the space has

   244     already been allocated.

   245 

   246     \sa size()

   247 */

   248 

   249 /*!

   250     \fn bool Q3MemArray::resize( uint size )

   251 

   252     \overload

   253 

   254     Resizes (expands or shrinks) the array to \a size elements. The

   255     array becomes a null array if \a size == 0.

   256 

   257     Returns TRUE if successful, i.e. if the memory can be allocated;

   258     otherwise returns FALSE.

   259 

   260     New elements are not initialized.

   261 

   262     \sa size()

   263 */

   264 

   265 /*!

   266     \fn bool Q3MemArray::truncate( uint pos )

   267 

   268     Truncates the array at position \a pos.

   269 

   270     Returns TRUE if successful, i.e. if the memory can be allocated;

   271     otherwise returns FALSE.

   272 

   273     Equivalent to resize(\a pos).

   274 

   275     \sa resize()

   276 */

   277 

   278 /*!

   279     \fn bool Q3MemArray::fill( const type &v, int size )

   280 

   281     Fills the array with the value \a v. If \a size is specified as

   282     different from -1, then the array will be resized before being

   283     filled.

   284 

   285     Returns TRUE if successful, i.e. if \a size is -1, or \a size is

   286     != -1 and the memory can be allocated; otherwise returns FALSE.

   287 

   288     \sa resize()

   289 */

   290 

   291 /*!

   292     \fn void Q3MemArray::detach()

   293 

   294     Detaches this array from shared array data; i.e. it makes a

   295     private, deep copy of the data.

   296 

   297     Copying will be performed only if the \link nrefs() reference

   298     count\endlink is greater than one.

   299 

   300     \sa copy()

   301 */

   302 

   303 /*!

   304     \fn Q3MemArray<type> Q3MemArray::copy() const

   305 

   306     Returns a deep copy of this array.

   307 

   308     \sa detach(), duplicate()

   309 */

   310 

   311 /*!

   312     \fn Q3MemArray<type> &Q3MemArray::assign( const Q3MemArray<type> &a )

   313 

   314     Shallow copy. Dereferences the current array and references the

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

   316 

   317     \sa operator=()

   318 */

   319 

   320 /*!

   321     \fn Q3MemArray<type> &Q3MemArray::assign( const type *data, uint size )

   322 

   323     \overload

   324 

   325     Shallow copy. Dereferences the current array and references the

   326     array data \a data, which contains \a size elements. Returns a

   327     reference to this array.

   328 

   329     Do not delete \a data later; Q3MemArray will call free() on it

   330     at the right time.

   331 */

   332 

   333 /*!

   334     \fn Q3MemArray<type> &Q3MemArray::duplicate( const Q3MemArray<type> &a )

   335 

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

   337     the data contained in \a a instead. Returns a reference to this

   338     array.

   339 

   340     \sa copy()

   341 */

   342 

   343 /*!

   344     \fn Q3MemArray<type> &Q3MemArray::duplicate( const type *data, uint size )

   345 

   346     \overload

   347 

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

   349     the array data \a data instead. Returns a reference to this array.

   350     The size of the array is given by \a size.

   351 

   352     \sa copy()

   353 */

   354 

   355 /*!

   356     \fn Q3MemArray<type> &Q3MemArray::setRawData( const type *data, uint size )

   357 

   358     Sets raw data and returns a reference to the array.

   359 

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

   361     data and the new array size to \a size. Do not attempt to resize

   362     or re-assign the array data when raw data has been set. Call

   363     resetRawData(\a data, \a size) to reset the array.

   364 

   365     Setting raw data is useful because it sets Q3MemArray data without

   366     allocating memory or copying data.

   367 

   368     Example I (intended use):

   369     \snippet doc/src/snippets/code/doc_src_q3memarray.qdoc 3

   370 

   371     Example II (you don't want to do this):

   372     \snippet doc/src/snippets/code/doc_src_q3memarray.qdoc 4

   373 

   374     \warning If you do not call resetRawData(), Q3MemArray will attempt

   375     to deallocate or reallocate the raw data, which might not be too

   376     good. Be careful.

   377 

   378     \sa resetRawData()

   379 */

   380 

   381 /*!

   382     \fn void Q3MemArray::resetRawData( const type *data, uint size )

   383 

   384     Removes internal references to the raw data that was set using

   385     setRawData(). This means that Q3MemArray no longer has access to

   386     the \a data, so you are free to manipulate \a data as you wish.

   387     You can now use the Q3MemArray without affecting the original \a

   388     data, for example by calling setRawData() with a pointer to some

   389     other data.

   390 

   391     The arguments must be the \a data and length, \a size, that were

   392     passed to setRawData(). This is for consistency checking.

   393 

   394     \sa setRawData()

   395 */

   396 

   397 /*!

   398     \fn int Q3MemArray::find( const type &v, uint index ) const

   399 

   400     Finds the first occurrence of \a v, starting at position \a index.

   401 

   402     Returns the position of \a v, or -1 if \a v could not be found.

   403 

   404     \sa contains()

   405 */

   406 

   407 /*!

   408     \fn int Q3MemArray::contains( const type &v ) const

   409 

   410     Returns the number of times \a v occurs in the array.

   411 

   412     \sa find()

   413 */

   414 

   415 /*!

   416     \fn void Q3MemArray::sort()

   417 

   418     Sorts the array elements in ascending order, using bitwise

   419     comparison (memcmp()).

   420 

   421     \sa bsearch()

   422 */

   423 

   424 /*!

   425     \fn int Q3MemArray::bsearch( const type &v ) const

   426 

   427     In a sorted array (as sorted by sort()), finds the first

   428     occurrence of \a v by using a binary search. For a sorted

   429     array this is generally much faster than find(), which does

   430     a linear search.

   431 

   432     Returns the position of \a v, or -1 if \a v could not be found.

   433 

   434     \sa sort(), find()

   435 */

   436 

   437 /*!

   438     \fn type &Q3MemArray::operator[]( int index ) const

   439 

   440     Returns a reference to the element at position \a index in the

   441     array.

   442 

   443     This can be used to both read and set an element. Equivalent to

   444     at().

   445 

   446     \sa at()

   447 */

   448 

   449 /*!

   450     \fn type &Q3MemArray::at( uint index ) const

   451 

   452     Returns a reference to the element at position \a index in the array.

   453 

   454     This can be used to both read and set an element.

   455 

   456     \sa operator[]()

   457 */

   458 

   459 /*!

   460     \fn Q3MemArray::operator const type *() const

   461 

   462     Cast operator. Returns a pointer to the array.

   463 

   464     \sa data()

   465 */

   466 

   467 /*!

   468     \fn bool Q3MemArray::operator==( const Q3MemArray<type> &a ) const

   469 

   470     Returns TRUE if this array is equal to \a a; otherwise returns

   471     FALSE.

   472 

   473     The two arrays are compared bitwise.

   474 

   475     \sa operator!=()

   476 */

   477 

   478 /*!

   479     \fn bool Q3MemArray::operator!=( const Q3MemArray<type> &a ) const

   480 

   481     Returns TRUE if this array is different from \a a; otherwise

   482     returns FALSE.

   483 

   484     The two arrays are compared bitwise.

   485 

   486     \sa operator==()

   487 */

   488 

   489 /*!

   490     \fn Iterator Q3MemArray::begin()

   491 

   492     Returns an iterator pointing at the beginning of this array. This

   493     iterator can be used in the same way as the iterators of

   494     Q3ValueList and QMap, for example.

   495 */

   496 

   497 /*!

   498     \fn Iterator Q3MemArray::end()

   499 

   500     Returns an iterator pointing behind the last element of this

   501     array. This iterator can be used in the same way as the iterators

   502     of Q3ValueList and QMap, for example.

   503 */

   504 

   505 /*!

   506     \fn ConstIterator Q3MemArray::begin() const

   507 

   508     \overload

   509 

   510     Returns a const iterator pointing at the beginning of this array.

   511     This iterator can be used in the same way as the iterators of

   512     Q3ValueList and QMap, for example.

   513 */

   514 

   515 /*!

   516     \fn ConstIterator Q3MemArray::end() const

   517 

   518     \overload

   519 

   520     Returns a const iterator pointing behind the last element of this

   521     array. This iterator can be used in the same way as the iterators

   522     of Q3ValueList and QMap, for example. 

   523 */