← Back to branch summary

~oif-team/ubuntu/natty/qt4-x11/xi2.1

« back to all changes in this revision

Viewing changes to src/qt3support/tools/q3garray.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-08-24 04:09:09 UTC
  • Revision ID: james.westby@ubuntu.com-20050824040909-xmxe9jfr4a0w5671
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/qt3support/tools/q3garray.cpp
 
1
/****************************************************************************
 
2
**
 
3
** Copyright (C) 1992-2005 Trolltech AS. All rights reserved.
 
4
**
 
5
** This file is part of the Qt 3 compatibility classes of the Qt Toolkit.
 
6
**
 
7
** This file may be distributed under the terms of the Q Public License
 
8
** as defined by Trolltech AS of Norway and appearing in the file
 
9
** LICENSE.QPL included in the packaging of this file.
 
10
**
 
11
** This file may be distributed and/or modified under the terms of the
 
12
** GNU General Public License version 2 as published by the Free Software
 
13
** Foundation and appearing in the file LICENSE.GPL included in the
 
14
** packaging of this file.
 
15
**
 
16
** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
 
17
**   information about Qt Commercial License Agreements.
 
18
** See http://www.trolltech.com/qpl/ for QPL licensing information.
 
19
** See http://www.trolltech.com/gpl/ for GPL licensing information.
 
20
**
 
21
** Contact info@trolltech.com if any conditions of this licensing are
 
22
** not clear to you.
 
23
**
 
24
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 
25
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 
26
**
 
27
****************************************************************************/
 
28
 
 
29
#include "qglobal.h"
 
30
#if defined(Q_CC_BOR)
 
31
    // needed for qsort() because of a std namespace problem on Borland
 
32
#   include "qplatformdefs.h"
 
33
#elif defined(Q_WS_WIN)
 
34
    // needed for bsearch on some platforms
 
35
#   include "qt_windows.h"
 
36
#endif
 
37
 
 
38
#define  Q3GARRAY_CPP
 
39
#include "q3garray.h"
 
40
#include <stdlib.h>
 
41
#include <string.h>
 
42
 
 
43
#ifdef QT_THREAD_SUPPORT
 
44
#  include <private/qmutexpool_p.h>
 
45
#endif // QT_THREAD_SUPPORT
 
46
 
 
47
/*
 
48
  If USE_MALLOC isn't defined, we use new[] and delete[] to allocate
 
49
  memory. The documentation for QMemArray<T>::assign() explicitly
 
50
  mentions that the array is freed using free(), so don't mess around
 
51
  with USE_MALLOC unless you know what you're doing.
 
52
*/
 
53
#define USE_MALLOC
 
54
 
 
55
#undef NEW
 
56
#undef DELETE
 
57
 
 
58
#if defined(USE_MALLOC)
 
59
#define NEW(type,size)  ((type*)malloc(size*sizeof(type)))
 
60
#define DELETE(array)   (free((char*)array))
 
61
#else
 
62
#define NEW(type,size)  (new type[size])
 
63
#define DELETE(array)   (delete[] array)
 
64
#define DONT_USE_REALLOC                        // comment to use realloc()
 
65
#endif
 
66
 
 
67
/*!
 
68
  \class Q3GArray
 
69
  \reentrant
 
70
  \brief The Q3GArray class is an internal class for implementing the QMemArray class.
 
71
 
 
72
  \internal
 
73
 
 
74
  Q3GArray is a strictly internal class that acts as base class for the
 
75
  QMemArray template array.
 
76
 
 
77
  It contains an array of bytes and has no notion of an array element.
 
78
*/
 
79
 
 
80
 
 
81
/*!
 
82
  Constructs a null array.
 
83
*/
 
84
 
 
85
Q3GArray::Q3GArray()
 
86
{
 
87
    shd = newData();
 
88
    Q_CHECK_PTR(shd);
 
89
}
 
90
 
 
91
/*!
 
92
  Dummy constructor; does not allocate any data.
 
93
 
 
94
  This constructor does not initialize any array data so subclasses
 
95
  must do it. The intention is to make the code more efficient.
 
96
*/
 
97
 
 
98
Q3GArray::Q3GArray(int, int)
 
99
{
 
100
}
 
101
 
 
102
/*!
 
103
  Constructs an array with room for \a size bytes.
 
104
*/
 
105
 
 
106
Q3GArray::Q3GArray(int size)
 
107
{
 
108
    if (size < 0) {
 
109
#if defined(QT_CHECK_RANGE)
 
110
        qWarning("Q3GArray: Cannot allocate array with negative length");
 
111
#endif
 
112
        size = 0;
 
113
    }
 
114
    shd = newData();
 
115
    Q_CHECK_PTR(shd);
 
116
    if (size == 0)                              // zero length
 
117
        return;
 
118
    shd->data = NEW(char,size);
 
119
    Q_CHECK_PTR(shd->data);
 
120
    shd->len =
 
121
#ifdef QT_Q3GARRAY_SPEED_OPTIM
 
122
        shd->maxl =
 
123
#endif
 
124
        size;
 
125
}
 
126
 
 
127
/*!
 
128
  Constructs a shallow copy of \a a.
 
129
*/
 
130
 
 
131
Q3GArray::Q3GArray(const Q3GArray &a)
 
132
{
 
133
    shd = a.shd;
 
134
    shd->ref();
 
135
}
 
136
 
 
137
/*!
 
138
  Dereferences the array data and deletes it if this was the last
 
139
  reference.
 
140
*/
 
141
 
 
142
Q3GArray::~Q3GArray()
 
143
{
 
144
    if (shd && shd->deref()) {          // delete when last reference
 
145
        if (shd->data)                  // is lost
 
146
            DELETE(shd->data);
 
147
        deleteData(shd);
 
148
        shd = 0;
 
149
    }
 
150
}
 
151
 
 
152
 
 
153
/*!
 
154
  \fn Q3GArray &Q3GArray::operator=(const Q3GArray &a)
 
155
 
 
156
  Assigns a shallow copy of \a a to this array and returns a reference to
 
157
  this array.  Equivalent to assign().
 
158
*/
 
159
 
 
160
/*!
 
161
  \fn void Q3GArray::detach()
 
162
 
 
163
  Detaches this array from shared array data.
 
164
*/
 
165
 
 
166
/*!
 
167
  \fn char *Q3GArray::data() const
 
168
 
 
169
  Returns a pointer to the actual array data.
 
170
*/
 
171
 
 
172
/*!
 
173
  \fn uint Q3GArray::nrefs() const
 
174
 
 
175
  Returns the reference count.
 
176
*/
 
177
 
 
178
/*!
 
179
  \fn uint Q3GArray::size() const
 
180
 
 
181
  Returns the size of the array, in bytes.
 
182
*/
 
183
 
 
184
 
 
185
/*!
 
186
  Returns true if this array is equal to \a a, otherwise false.
 
187
  The comparison is bitwise, of course.
 
188
*/
 
189
 
 
190
bool Q3GArray::isEqual(const Q3GArray &a) const
 
191
{
 
192
    if (size() != a.size())                     // different size
 
193
        return false;
 
194
    if (data() == a.data())                     // has same data
 
195
        return true;
 
196
    return (size() ? memcmp(data(), a.data(), size()) : 0) == 0;
 
197
}
 
198
 
 
199
 
 
200
/*!
 
201
  Resizes the array to \a newsize bytes. \a optim is either
 
202
  MemOptim (the default) or SpeedOptim.
 
203
*/
 
204
bool Q3GArray::resize(uint newsize, Optimization optim)
 
205
{
 
206
#ifndef QT_Q3GARRAY_SPEED_OPTIM
 
207
    Q_UNUSED(optim);
 
208
#endif
 
209
 
 
210
    if (newsize == shd->len
 
211
#ifdef QT_Q3GARRAY_SPEED_OPTIM
 
212
         && newsize == shd->maxl
 
213
#endif
 
214
        ) // nothing to do
 
215
        return true;
 
216
    if (newsize == 0) {                 // remove array
 
217
        if (shd->data)
 
218
            DELETE(shd->data);
 
219
        shd->data = 0;
 
220
        shd->len = 0;
 
221
#ifdef QT_Q3GARRAY_SPEED_OPTIM
 
222
        shd->maxl = 0;
 
223
#endif
 
224
        return true;
 
225
    }
 
226
 
 
227
    uint newmaxl = newsize;
 
228
#ifdef QT_Q3GARRAY_SPEED_OPTIM
 
229
    if (optim == SpeedOptim) {
 
230
        if (newsize <= shd->maxl &&
 
231
             (newsize * 4 > shd->maxl || shd->maxl <= 4)) {
 
232
            shd->len = newsize;
 
233
            return true;
 
234
        }
 
235
        newmaxl = 4;
 
236
        while (newmaxl < newsize)
 
237
            newmaxl *= 2;
 
238
        // try to spare some memory
 
239
        if (newmaxl >= 1024 * 1024 && newsize <= newmaxl - (newmaxl >> 2))
 
240
            newmaxl -= newmaxl >> 2;
 
241
    }
 
242
    shd->maxl = newmaxl;
 
243
#endif
 
244
 
 
245
    if (shd->data) {                            // existing data
 
246
#if defined(DONT_USE_REALLOC)
 
247
        char *newdata = NEW(char,newsize);      // manual realloc
 
248
        memcpy(newdata, shd->data, QMIN(shd->len,newmaxl));
 
249
        DELETE(shd->data);
 
250
        shd->data = newdata;
 
251
#else
 
252
        shd->data = (char *)realloc(shd->data, newmaxl);
 
253
#endif
 
254
    } else {
 
255
        shd->data = NEW(char,newmaxl);
 
256
    }
 
257
    if (!shd->data)                             // no memory
 
258
        return false;
 
259
    shd->len = newsize;
 
260
    return true;
 
261
}
 
262
 
 
263
/*!\overload
 
264
*/
 
265
bool Q3GArray::resize(uint newsize)
 
266
{
 
267
    return resize(newsize, MemOptim);
 
268
}
 
269
 
 
270
 
 
271
/*!
 
272
  Fills the array with the repeated occurrences of \a d, which is
 
273
  \a sz bytes long.
 
274
  If \a len is specified as different from -1, then the array will be
 
275
  resized to \a len*sz before it is filled.
 
276
 
 
277
  Returns true if successful, or false if the memory cannot be allocated
 
278
  (only when \a len != -1).
 
279
 
 
280
  \sa resize()
 
281
*/
 
282
 
 
283
bool Q3GArray::fill(const char *d, int len, uint sz)
 
284
{
 
285
    if (len < 0)
 
286
        len = shd->len/sz;                      // default: use array length
 
287
    else if (!resize(len*sz))
 
288
        return false;
 
289
    if (sz == 1)                                // 8 bit elements
 
290
        memset(data(), *d, len);
 
291
    else if (sz == 4) {                 // 32 bit elements
 
292
        register Q_INT32 *x = (Q_INT32*)data();
 
293
        Q_INT32 v = *((Q_INT32*)d);
 
294
        while (len--)
 
295
            *x++ = v;
 
296
    } else if (sz == 2) {                       // 16 bit elements
 
297
        register Q_INT16 *x = (Q_INT16*)data();
 
298
        Q_INT16 v = *((Q_INT16*)d);
 
299
        while (len--)
 
300
            *x++ = v;
 
301
    } else {                                    // any other size elements
 
302
        register char *x = data();
 
303
        while (len--) {                 // more complicated
 
304
            memcpy(x, d, sz);
 
305
            x += sz;
 
306
        }
 
307
    }
 
308
    return true;
 
309
}
 
310
 
 
311
/*!
 
312
    \overload
 
313
  Shallow copy. Dereference the current array and references the data
 
314
  contained in \a a instead. Returns a reference to this array.
 
315
  \sa operator=()
 
316
*/
 
317
 
 
318
Q3GArray &Q3GArray::assign(const Q3GArray &a)
 
319
{
 
320
    a.shd->ref();                               // avoid 'a = a'
 
321
    if (shd->deref()) {                 // delete when last reference
 
322
        if (shd->data)                  // is lost
 
323
            DELETE(shd->data);
 
324
        deleteData(shd);
 
325
    }
 
326
    shd = a.shd;
 
327
    return *this;
 
328
}
 
329
 
 
330
/*!
 
331
  Shallow copy. Dereference the current array and references the
 
332
  array data \a d, which contains \a len bytes.
 
333
  Returns a reference to this array.
 
334
 
 
335
  Do not delete \a d later, because Q3GArray takes care of that.
 
336
*/
 
337
 
 
338
Q3GArray &Q3GArray::assign(const char *d, uint len)
 
339
{
 
340
    if (shd->count > 1) {                       // disconnect this
 
341
        shd->count--;
 
342
        shd = newData();
 
343
        Q_CHECK_PTR(shd);
 
344
    } else {
 
345
        if (shd->data)
 
346
            DELETE(shd->data);
 
347
    }
 
348
    shd->data = (char *)d;
 
349
    shd->len =
 
350
#ifdef QT_Q3GARRAY_SPEED_OPTIM
 
351
        shd->maxl =
 
352
#endif
 
353
        len;
 
354
    return *this;
 
355
}
 
356
 
 
357
/*!
 
358
  Deep copy. Dereference the current array and obtains a copy of the data
 
359
  contained in \a a instead. Returns a reference to this array.
 
360
  \sa assign(), operator=()
 
361
*/
 
362
 
 
363
Q3GArray &Q3GArray::duplicate(const Q3GArray &a)
 
364
{
 
365
    if (a.shd == shd) {                 // a.duplicate(a) !
 
366
        if (shd->count > 1) {
 
367
            shd->count--;
 
368
            register array_data *n = newData();
 
369
            Q_CHECK_PTR(n);
 
370
            if ((n->len=shd->len)) {
 
371
                n->data = NEW(char,n->len);
 
372
                Q_CHECK_PTR(n->data);
 
373
                if (n->data)
 
374
                    memcpy(n->data, shd->data, n->len);
 
375
            } else {
 
376
                n->data = 0;
 
377
            }
 
378
            shd = n;
 
379
        }
 
380
        return *this;
 
381
    }
 
382
    char *oldptr = 0;
 
383
    if (shd->count > 1) {                       // disconnect this
 
384
        shd->count--;
 
385
        shd = newData();
 
386
        Q_CHECK_PTR(shd);
 
387
    } else {                                    // delete after copy was made
 
388
        oldptr = shd->data;
 
389
    }
 
390
    if (a.shd->len) {                           // duplicate data
 
391
        shd->data = NEW(char,a.shd->len);
 
392
        Q_CHECK_PTR(shd->data);
 
393
        if (shd->data)
 
394
            memcpy(shd->data, a.shd->data, a.shd->len);
 
395
    } else {
 
396
        shd->data = 0;
 
397
    }
 
398
    shd->len =
 
399
#ifdef QT_Q3GARRAY_SPEED_OPTIM
 
400
        shd->maxl =
 
401
#endif
 
402
        a.shd->len;
 
403
    if (oldptr)
 
404
        DELETE(oldptr);
 
405
    return *this;
 
406
}
 
407
 
 
408
/*!
 
409
    \overload
 
410
  Deep copy. Dereferences the current array and obtains a copy of
 
411
  \a len characters from array data \a d instead.  Returns a reference
 
412
  to this array.
 
413
  \sa assign(), operator=()
 
414
*/
 
415
 
 
416
Q3GArray &Q3GArray::duplicate(const char *d, uint len)
 
417
{
 
418
    char *data;
 
419
    if (d == 0 || len == 0) {
 
420
        data = 0;
 
421
        len  = 0;
 
422
    } else {
 
423
        if (shd->count == 1 && shd->len == len) {
 
424
            if (shd->data != d)         // avoid self-assignment
 
425
                memcpy(shd->data, d, len);      // use same buffer
 
426
            return *this;
 
427
        }
 
428
        data = NEW(char,len);
 
429
        Q_CHECK_PTR(data);
 
430
        memcpy(data, d, len);
 
431
    }
 
432
    if (shd->count > 1) {                       // detach
 
433
        shd->count--;
 
434
        shd = newData();
 
435
        Q_CHECK_PTR(shd);
 
436
    } else {                                    // just a single reference
 
437
        if (shd->data)
 
438
            DELETE(shd->data);
 
439
    }
 
440
    shd->data = data;
 
441
    shd->len =
 
442
#ifdef QT_Q3GARRAY_SPEED_OPTIM
 
443
        shd->maxl =
 
444
#endif
 
445
        len;
 
446
    return *this;
 
447
}
 
448
 
 
449
/*!
 
450
  Resizes this array to \a len bytes and copies the \a len bytes at
 
451
  address \a d into it.
 
452
 
 
453
  \warning This function disregards the reference count mechanism.  If
 
454
  other Q3GArrays reference the same data as this, all will be updated.
 
455
*/
 
456
 
 
457
void Q3GArray::store(const char *d, uint len)
 
458
{                                               // store, but not deref
 
459
    resize(len);
 
460
    memcpy(shd->data, d, len);
 
461
}
 
462
 
 
463
 
 
464
/*!
 
465
  \fn array_data *Q3GArray::sharedBlock() const
 
466
 
 
467
  Returns a pointer to the shared array block.
 
468
 
 
469
  \warning
 
470
 
 
471
  Do not use this function.  Using it is begging for trouble.  We dare
 
472
  not remove it, for fear of breaking code, but we \e strongly
 
473
  discourage new use of it.
 
474
*/
 
475
 
 
476
/*!
 
477
  \fn void Q3GArray::setSharedBlock(array_data *p)
 
478
 
 
479
  Sets the shared array block to \a p.
 
480
 
 
481
  \warning
 
482
 
 
483
  Do not use this function.  Using it is begging for trouble.  We dare
 
484
  not remove it, for fear of breaking code, but we \e strongly
 
485
  discourage new use of it.
 
486
*/
 
487
 
 
488
 
 
489
/*!
 
490
  Sets raw data and returns a reference to the array.
 
491
 
 
492
  Dereferences the current array and sets the new array data to \a d and
 
493
  the new array size to \a len.  Do not attempt to resize or re-assign the
 
494
  array data when raw data has been set.
 
495
  Call resetRawData(d,len) to reset the array.
 
496
 
 
497
  Setting raw data is useful because it sets QMemArray data without
 
498
  allocating memory or copying data.
 
499
 
 
500
  Example of intended use:
 
501
  \code
 
502
    static uchar bindata[] = { 231, 1, 44, ... };
 
503
    QByteArray  a;
 
504
    a.setRawData(bindata, sizeof(bindata));     // a points to bindata
 
505
    QDataStream s(a, IO_ReadOnly);              // open on a's data
 
506
    s >> <something>;                           // read raw bindata
 
507
    s.close();
 
508
    a.resetRawData(bindata, sizeof(bindata)); // finished
 
509
  \endcode
 
510
 
 
511
  Example of misuse (do not do this):
 
512
  \code
 
513
    static uchar bindata[] = { 231, 1, 44, ... };
 
514
    QByteArray  a, b;
 
515
    a.setRawData(bindata, sizeof(bindata));     // a points to bindata
 
516
    a.resize(8);                                // will crash
 
517
    b = a;                                      // will crash
 
518
    a[2] = 123;                                 // might crash
 
519
      // forget to resetRawData - will crash
 
520
  \endcode
 
521
 
 
522
  \warning If you do not call resetRawData(), Q3GArray will attempt to
 
523
  deallocate or reallocate the raw data, which might not be too good.
 
524
  Be careful.
 
525
*/
 
526
 
 
527
Q3GArray &Q3GArray::setRawData(const char *d, uint len)
 
528
{
 
529
    duplicate(0, 0);                            // set null data
 
530
    shd->data = (char *)d;
 
531
    shd->len  = len;
 
532
    return *this;
 
533
}
 
534
 
 
535
/*!
 
536
  Resets raw data.
 
537
 
 
538
  The arguments must be the data, \a d, and length \a len, that were
 
539
  passed to setRawData().  This is for consistency checking.
 
540
*/
 
541
 
 
542
void Q3GArray::resetRawData(const char *d, uint len)
 
543
{
 
544
    if (d != shd->data || len != shd->len) {
 
545
#if defined(QT_CHECK_STATE)
 
546
        qWarning("Q3GArray::resetRawData: Inconsistent arguments");
 
547
#endif
 
548
        return;
 
549
    }
 
550
    shd->data = 0;
 
551
    shd->len  = 0;
 
552
}
 
553
 
 
554
 
 
555
/*!
 
556
  Finds the first occurrence of \a d in the array from position \a index,
 
557
  where \a sz is the size of the \a d element.
 
558
 
 
559
  Note that \a index is given in units of \a sz, not bytes.
 
560
 
 
561
  This function only compares whole cells, not bytes.
 
562
*/
 
563
 
 
564
int Q3GArray::find(const char *d, uint index, uint sz) const
 
565
{
 
566
    index *= sz;
 
567
    if (index >= shd->len) {
 
568
#if defined(QT_CHECK_RANGE)
 
569
        qWarning("Q3GArray::find: Index %d out of range", index/sz);
 
570
#endif
 
571
        return -1;
 
572
    }
 
573
    register uint i;
 
574
    uint ii;
 
575
    switch (sz) {
 
576
        case 1: {                               // 8 bit elements
 
577
            register char *x = data() + index;
 
578
            char v = *d;
 
579
            for (i=index; i<shd->len; i++) {
 
580
                if (*x++ == v)
 
581
                    break;
 
582
            }
 
583
            ii = i;
 
584
            }
 
585
            break;
 
586
        case 2: {                               // 16 bit elements
 
587
            register Q_INT16 *x = (Q_INT16*)(data() + index);
 
588
            Q_INT16 v = *((Q_INT16*)d);
 
589
            for (i=index; i<shd->len; i+=2) {
 
590
                if (*x++ == v)
 
591
                    break;
 
592
            }
 
593
            ii = i/2;
 
594
            }
 
595
            break;
 
596
        case 4: {                               // 32 bit elements
 
597
            register Q_INT32 *x = (Q_INT32*)(data() + index);
 
598
            Q_INT32 v = *((Q_INT32*)d);
 
599
            for (i=index; i<shd->len; i+=4) {
 
600
                if (*x++ == v)
 
601
                    break;
 
602
            }
 
603
            ii = i/4;
 
604
            }
 
605
            break;
 
606
        default: {                              // any size elements
 
607
            for (i=index; i<shd->len; i+=sz) {
 
608
                if (memcmp(d, &shd->data[i], sz) == 0)
 
609
                    break;
 
610
            }
 
611
            ii = i/sz;
 
612
            }
 
613
            break;
 
614
    }
 
615
    return i<shd->len ? (int)ii : -1;
 
616
}
 
617
 
 
618
/*!
 
619
  Returns the number of occurrences of \a d in the array, where \a sz is
 
620
  the size of the \a d element.
 
621
 
 
622
  This function only compares whole cells, not bytes.
 
623
*/
 
624
 
 
625
int Q3GArray::contains(const char *d, uint sz) const
 
626
{
 
627
    register uint i = shd->len;
 
628
    int count = 0;
 
629
    switch (sz) {
 
630
        case 1: {                               // 8 bit elements
 
631
            register char *x = data();
 
632
            char v = *d;
 
633
            while (i--) {
 
634
                if (*x++ == v)
 
635
                    count++;
 
636
            }
 
637
            }
 
638
            break;
 
639
        case 2: {                               // 16 bit elements
 
640
            register Q_INT16 *x = (Q_INT16*)data();
 
641
            Q_INT16 v = *((Q_INT16*)d);
 
642
            i /= 2;
 
643
            while (i--) {
 
644
                if (*x++ == v)
 
645
                    count++;
 
646
            }
 
647
            }
 
648
            break;
 
649
        case 4: {                               // 32 bit elements
 
650
            register Q_INT32 *x = (Q_INT32*)data();
 
651
            Q_INT32 v = *((Q_INT32*)d);
 
652
            i /= 4;
 
653
            while (i--) {
 
654
                if (*x++ == v)
 
655
                    count++;
 
656
            }
 
657
            }
 
658
            break;
 
659
        default: {                              // any size elements
 
660
            for (i=0; i<shd->len; i+=sz) {
 
661
                if (memcmp(d, &shd->data[i], sz) == 0)
 
662
                    count++;
 
663
            }
 
664
            }
 
665
            break;
 
666
    }
 
667
    return count;
 
668
}
 
669
 
 
670
static int cmp_item_size = 0;
 
671
 
 
672
#if defined(Q_C_CALLBACKS)
 
673
extern "C" {
 
674
#endif
 
675
 
 
676
#ifdef Q_OS_TEMP
 
677
static int __cdecl cmp_arr(const void *n1, const void *n2)
 
678
#else
 
679
static int cmp_arr(const void *n1, const void *n2)
 
680
#endif
 
681
{
 
682
    return (n1 && n2) ? memcmp(n1, n2, cmp_item_size)
 
683
                        : (n1 ? 1 : (n2 ? -1 : 0));
 
684
    // ### Qt 3.0: Add a virtual compareItems() method and call that instead
 
685
}
 
686
 
 
687
#if defined(Q_C_CALLBACKS)
 
688
}
 
689
#endif
 
690
 
 
691
/*!
 
692
  Sorts the first \a sz items of the array.
 
693
*/
 
694
 
 
695
void Q3GArray::sort(uint sz)
 
696
{
 
697
    int numItems = size() / sz;
 
698
    if (numItems < 2)
 
699
        return;
 
700
 
 
701
#ifdef QT_THREAD_SUPPORT
 
702
    QMutexLocker locker(qt_global_mutexpool ?
 
703
                         qt_global_mutexpool->get(&cmp_item_size) : 0);
 
704
#endif // QT_THREAD_SUPPORT
 
705
 
 
706
    cmp_item_size = sz;
 
707
    qsort(shd->data, numItems, sz, cmp_arr);
 
708
}
 
709
 
 
710
/*!
 
711
  Binary search; assumes that \a d is a sorted array of size \a sz.
 
712
*/
 
713
 
 
714
int Q3GArray::bsearch(const char *d, uint sz) const
 
715
{
 
716
    int numItems = size() / sz;
 
717
    if (!numItems)
 
718
        return -1;
 
719
 
 
720
#ifdef QT_THREAD_SUPPORT
 
721
    QMutexLocker locker(qt_global_mutexpool ?
 
722
                         qt_global_mutexpool->get(&cmp_item_size) : 0);
 
723
#endif // QT_THREAD_SUPPORT
 
724
 
 
725
    cmp_item_size = sz;
 
726
    char* r = (char*)::bsearch(d, shd->data, numItems, sz, cmp_arr);
 
727
    if (!r)
 
728
        return -1;
 
729
    while((r >= shd->data + sz) && (cmp_arr(r - sz, d) == 0))
 
730
        r -= sz;        // search to first of equal elements; bsearch is undef
 
731
    return (int)((r - shd->data) / sz);
 
732
}
 
733
 
 
734
 
 
735
/*!
 
736
  \fn char *Q3GArray::at(uint index) const
 
737
 
 
738
  Returns a pointer to the byte at offset \a index in the array.
 
739
*/
 
740
 
 
741
/*!
 
742
  Expand the array if necessary, and copies (the first part of) its
 
743
  contents from the \a index * \a sz bytes at \a d.
 
744
 
 
745
  Returns true if the operation succeeds, false if it runs out of
 
746
  memory.
 
747
 
 
748
  \warning This function disregards the reference count mechanism.  If
 
749
  other Q3GArrays reference the same data as this, all will be changed.
 
750
*/
 
751
 
 
752
bool Q3GArray::setExpand(uint index, const char *d, uint sz)
 
753
{
 
754
    index *= sz;
 
755
    if (index >= shd->len) {
 
756
        if (!resize(index+sz))          // no memory
 
757
            return false;
 
758
    }
 
759
    memcpy(data() + index, d, sz);
 
760
    return true;
 
761
}
 
762
 
 
763
 
 
764
/*!
 
765
  Prints a warning message if at() or [] is given a bad index.
 
766
*/
 
767
 
 
768
void Q3GArray::msg_index(uint index)
 
769
{
 
770
#if defined(QT_CHECK_RANGE)
 
771
    qWarning("Q3GArray::at: Absolute index %d out of range", index);
 
772
#else
 
773
    Q_UNUSED(index)
 
774
#endif
 
775
}
 
776
 
 
777
 
 
778
/*!
 
779
  Returns a new shared array block.
 
780
*/
 
781
 
 
782
Q3GArray::array_data * Q3GArray::newData()
 
783
{
 
784
    return new array_data;
 
785
}
 
786
 
 
787
 
 
788
/*!
 
789
  Deletes the shared array block \a p.
 
790
*/
 
791
 
 
792
void Q3GArray::deleteData(array_data *p)
 
793
{
 
794
    delete p;
 
795
}