← Back to branch summary

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

« back to all changes in this revision

Viewing changes to tools/porting/src/list.h

  • 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:
tools/porting/src/list.h
 
1
/****************************************************************************
 
2
**
 
3
** Copyright (C) 1992-2005 Trolltech AS. All rights reserved.
 
4
**
 
5
** This file is part of the porting application 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
#ifndef LIST_H
 
29
#define LIST_H
 
30
 
 
31
#include <qglobal.h>
 
32
#include <smallobject.h>
 
33
 
 
34
template <typename T>
 
35
class List
 
36
{
 
37
    struct Data
 
38
    {
 
39
        int alloc, size;
 
40
        T array[1];
 
41
    };
 
42
    pool *p;
 
43
    Data *d;
 
44
 
 
45
public:
 
46
    inline List(pool *_pool) : p(_pool), d(0) { d = malloc(16); d->size = 0; d->alloc = 16; }
 
47
 
 
48
    inline List(const List &v) : d(0) { operator=(v); }
 
49
    inline ~List() { d = 0; }
 
50
    List &operator=(const List &v);
 
51
 
 
52
    bool operator==(const List &v) const;
 
53
    inline bool operator!=(const List &v) const { return !(*this == v); }
 
54
 
 
55
    inline int size() const { return d->size; }
 
56
    inline bool isEmpty() const { return d->size == 0; }
 
57
 
 
58
    inline int capacity() const { return d->alloc; }
 
59
    void reserve(int alloc);
 
60
 
 
61
    inline T* data() { return d->array; }
 
62
    inline const T* data() const { return d->array; }
 
63
    void clear();
 
64
 
 
65
    const T &at(int i) const;
 
66
    T &operator[](int i);
 
67
    const T &operator[](int i) const;
 
68
    void append(const T &t);
 
69
    void prepend(const T &t);
 
70
    void insert(int i, const T &t);
 
71
    void insert(int i, int n, const T &t);
 
72
    void replace(int i, const T &t);
 
73
    void remove(int i);
 
74
    void remove(int i, int n);
 
75
 
 
76
    List &fill(const T &t, int size = -1);
 
77
 
 
78
    int indexOf(const T &t, int from = 0) const;
 
79
    int lastIndexOf(const T &t, int from = -1) const;
 
80
    bool contains(const T &t) const;
 
81
    int count(const T &t) const;
 
82
 
 
83
    // STL-style
 
84
    typedef T* iterator;
 
85
    typedef const T* const_iterator;
 
86
    inline iterator begin() { return d->array; }
 
87
    inline const_iterator begin() const { return d->array; }
 
88
    inline iterator end() { return d->array + d->size; }
 
89
    inline const_iterator end() const { return d->array + d->size; }
 
90
    iterator insert(iterator before, int n, const T &x);
 
91
    inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); }
 
92
    iterator erase(iterator begin, iterator end);
 
93
    inline iterator erase(iterator pos) { return erase(pos, pos+1); }
 
94
 
 
95
    // more Qt
 
96
    inline int count() const { return d->size; }
 
97
    inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
 
98
    inline const T& first() const { Q_ASSERT(!isEmpty()); return *begin(); }
 
99
    inline T& last() { Q_ASSERT(!isEmpty()); return *(end()-1); }
 
100
    inline const T& last() const { Q_ASSERT(!isEmpty()); return *(end()-1); }
 
101
 
 
102
    T value(int i) const;
 
103
    T value(int i, const T &defaultValue) const;
 
104
 
 
105
    // STL compatibility
 
106
    typedef T value_type;
 
107
    typedef value_type* pointer;
 
108
    typedef const value_type* const_pointer;
 
109
    typedef value_type& reference;
 
110
    typedef const value_type& const_reference;
 
111
#ifndef QT_NO_STL
 
112
    typedef ptrdiff_t difference_type;
 
113
#else
 
114
    typedef int difference_type;
 
115
#endif
 
116
    typedef iterator Iterator;
 
117
    typedef const_iterator ConstIterator;
 
118
    typedef int size_type;
 
119
    inline void push_back(const T &t) { append(t); }
 
120
    inline void push_front(const T &t) { prepend(t); }
 
121
    void pop_back() { Q_ASSERT(!isEmpty()); erase(end()-1); }
 
122
    void pop_front() { Q_ASSERT(!isEmpty()); erase(begin()); }
 
123
    inline bool empty() const
 
124
    { return d->size == 0; }
 
125
    inline T& front() { return first(); }
 
126
    inline const_reference front() const { return first(); }
 
127
    inline reference back() { return last(); }
 
128
    inline const_reference back() const { return last(); }
 
129
 
 
130
    //comfort
 
131
    List &operator+=(const List &l);
 
132
    inline List operator+(const List &l) const
 
133
    { List n = *this; n += l; return n; }
 
134
    inline void operator+=(const T &t)
 
135
    { append(t); }
 
136
    inline List &operator<< (const T &t)
 
137
    { append(t); return *this; }
 
138
 
 
139
private:
 
140
    Data *malloc(int alloc);
 
141
};
 
142
 
 
143
template <typename T>
 
144
inline void List<T>::clear()
 
145
{ d->size = 0; }
 
146
 
 
147
template <typename T>
 
148
inline const T &List<T>::at(int i) const
 
149
{ Q_ASSERT_X(i >= 0 && i < d->size, "List<T>::at", "index out of range");
 
150
  return d->array[i]; }
 
151
template <typename T>
 
152
inline const T &List<T>::operator[](int i) const
 
153
{ Q_ASSERT_X(i >= 0 && i < d->size, "List<T>::operator[]", "index out of range");
 
154
  return d->array[i]; }
 
155
template <typename T>
 
156
inline T &List<T>::operator[](int i)
 
157
{ Q_ASSERT_X(i >= 0 && i < d->size, "List<T>::operator[]", "index out of range");
 
158
  return d->array[i]; }
 
159
template <typename T>
 
160
inline void List<T>::insert(int i, const T &t)
 
161
{ Q_ASSERT_X(i >= 0 && i <= d->size, "List<T>::insert", "index out of range");
 
162
  insert(begin()+i, 1, t); }
 
163
template <typename T>
 
164
inline void List<T>::insert(int i, int n, const T &t)
 
165
{ Q_ASSERT_X(i >= 0 && i <= d->size, "List<T>::insert", "index out of range");
 
166
  insert(begin() + i, n, t); }
 
167
template <typename T>
 
168
inline void List<T>::remove(int i, int n)
 
169
{ Q_ASSERT_X(i >= 0 && i + n <= d->size, "List<T>::remove", "index out of range");
 
170
  erase(begin() + i, begin() + i + n); }
 
171
template <typename T>
 
172
inline void List<T>::remove(int i)
 
173
{ Q_ASSERT_X(i >= 0 && i < d->size, "List<T>::remove", "index out of range");
 
174
  erase(begin() + i, begin() + i + 1); }
 
175
template <typename T>
 
176
inline void List<T>::prepend(const T &t)
 
177
{ insert(begin(), 1, t); }
 
178
template <typename T>
 
179
inline void List<T>::replace(int i, const T &t)
 
180
{ Q_ASSERT_X(i >= 0 && i < d->size, "List<T>::replace", "index out of range");
 
181
  data()[i] = t; }
 
182
 
 
183
template <typename T>
 
184
List<T> &List<T>::operator=(const List<T> &v)
 
185
{
 
186
    p = v.p;
 
187
    d = malloc(v.d->alloc);
 
188
    memcpy(d, v.d, sizeof(Data) + (v.d->size - 1) * sizeof(T));
 
189
    return *this;
 
190
}
 
191
 
 
192
template <typename T>
 
193
inline typename List<T>::Data *List<T>::malloc(int alloc)
 
194
{
 
195
    return static_cast<Data *>(p->allocate(sizeof(Data) + (alloc - 1) * sizeof(T)));
 
196
}
 
197
 
 
198
template <typename T>
 
199
void List<T>::reserve(int alloc)
 
200
{
 
201
    if (alloc <= d->alloc)
 
202
        return;
 
203
    alloc <<= 2;
 
204
    d = static_cast<Data *>(p->reallocate(d, sizeof(Data) + d->alloc * sizeof(T),
 
205
                                          sizeof(Data) + (alloc - 1) * sizeof(T)));
 
206
    d->alloc = alloc;
 
207
}
 
208
 
 
209
template<typename T>
 
210
T List<T>::value(int i) const
 
211
{
 
212
    if(i < 0 || i >= d->size) {
 
213
        return T();
 
214
    }
 
215
    return d->array[i];
 
216
}
 
217
template<typename T>
 
218
T List<T>::value(int i, const T& defaultValue) const
 
219
{
 
220
    return ((i < 0 || i >= d->size) ? defaultValue : d->array[i]);
 
221
}
 
222
 
 
223
template <typename T>
 
224
void List<T>::append(const T &t)
 
225
{
 
226
    reserve(d->size + 1);
 
227
    d->array[d->size++] = t;
 
228
}
 
229
 
 
230
 
 
231
template <typename T>
 
232
typename List<T>::iterator List<T>::insert(iterator before, size_type n, const T& t)
 
233
{
 
234
    int p = before - d->array;
 
235
    if (n != 0) {
 
236
        reserve(d->size + n);
 
237
        T *b = d->array+p;
 
238
        T *i = b+n;
 
239
        memmove(i, b, (d->size-p)*sizeof(T));
 
240
        while (i != b)
 
241
            *(--i) = t;
 
242
    }
 
243
    d->size += n;
 
244
    return d->array+p;
 
245
}
 
246
 
 
247
template <typename T>
 
248
typename List<T>::iterator List<T>::erase(iterator begin, iterator end)
 
249
{
 
250
    int f = begin - d->array;
 
251
    int l = end - d->array;
 
252
    int n = l - f;
 
253
    memmove(d->array + f, d->array + l, (d->size-l)*sizeof(T));
 
254
    d->size -= n;
 
255
    return d->array + f;
 
256
}
 
257
 
 
258
template <typename T>
 
259
bool List<T>::operator==(const List<T> &v) const
 
260
{
 
261
    if (d->size != v.d->size)
 
262
        return false;
 
263
    T* b = d->array;
 
264
    T* i = b + d->size;
 
265
    T* j = v.d->array + d->size;
 
266
    while (i != b)
 
267
        if (!(*--i == *--j))
 
268
            return false;
 
269
    return true;
 
270
}
 
271
 
 
272
template <typename T>
 
273
List<T> &List<T>::fill(const T &t, int size)
 
274
{
 
275
    resize(size < 0 ? d->size : size);
 
276
    if (d->size) {
 
277
        T* i = d->array + d->size;
 
278
        T* b = d->array;
 
279
        while (i != b)
 
280
            *--i = t;
 
281
    }
 
282
    return *this;
 
283
}
 
284
 
 
285
template <typename T>
 
286
List<T> &List<T>::operator+=(const List &l)
 
287
{
 
288
    int newSize = d->size + l.d->size;
 
289
    reserve(newSize);
 
290
 
 
291
    T *w = d->array + newSize;
 
292
    T *i = l.d->array + l.d->size;
 
293
    T *b = l.d->array;
 
294
    while (i != b)
 
295
        *--w = *--i;
 
296
    d->size = newSize;
 
297
    return *this;
 
298
}
 
299
 
 
300
template <typename T>
 
301
int List<T>::indexOf(const T &t, int from) const
 
302
{
 
303
    if (from < 0)
 
304
        from = qMax(from + d->size, 0);
 
305
    if (from < d->size) {
 
306
        T* n = d->array + from - 1;
 
307
        T* e = d->array + d->size;
 
308
        while (++n != e)
 
309
            if (*n == t)
 
310
                return n - d->array;
 
311
    }
 
312
    return -1;
 
313
}
 
314
 
 
315
template <typename T>
 
316
int List<T>::lastIndexOf(const T &t, int from) const
 
317
{
 
318
    if (from < 0)
 
319
        from += d->size;
 
320
    else if (from >= d->size)
 
321
        from = d->size-1;
 
322
    if (from >= 0) {
 
323
        T* b = d->array;
 
324
        T* n = d->array + from + 1;
 
325
        while (n != b) {
 
326
            if (*--n == t)
 
327
                return n - b;
 
328
        }
 
329
    }
 
330
    return -1;
 
331
}
 
332
 
 
333
template <typename T>
 
334
bool List<T>::contains(const T &t) const
 
335
{
 
336
    T* b = d->array;
 
337
    T* i = d->array + d->size;
 
338
    while (i != b)
 
339
        if (*--i == t)
 
340
            return true;
 
341
    return false;
 
342
}
 
343
 
 
344
template <typename T>
 
345
int List<T>::count(const T &t) const
 
346
{
 
347
    int c = 0;
 
348
    T* b = d->array;
 
349
    T* i = d->array + d->size;
 
350
    while (i != b)
 
351
        if (*--i == t)
 
352
            ++c;
 
353
    return c;
 
354
}
 
355
 
 
356
#endif // LIST_H