← Back to branch summary

~ubuntu-branches/ubuntu/maverick/webkit/maverick

« back to all changes in this revision

Viewing changes to JavaScriptCore/kjs/list.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Mike Hommey
  • Date: 2007-08-19 15:54:12 UTC
  • Revision ID: james.westby@ubuntu.com-20070819155412-uxxg1h9plpghmtbi
Tags: upstream-0~svn25144
Import upstream version 0~svn25144

Show diffs side-by-side

added added

removed removed

Lines of Context:
JavaScriptCore/kjs/list.cpp
 
1
/*
 
2
 *  Copyright (C) 2003, 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.
 
3
 *
 
4
 *  This library is free software; you can redistribute it and/or
 
5
 *  modify it under the terms of the GNU Library General Public
 
6
 *  License as published by the Free Software Foundation; either
 
7
 *  version 2 of the License, or (at your option) any later version.
 
8
 *
 
9
 *  This library is distributed in the hope that it will be useful,
 
10
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
11
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
12
 *  Library General Public License for more details.
 
13
 *
 
14
 *  You should have received a copy of the GNU Library General Public License
 
15
 *  along with this library; see the file COPYING.LIB.  If not, write to
 
16
 *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 
17
 *  Boston, MA 02110-1301, USA.
 
18
 *
 
19
 */
 
20
 
 
21
#include "config.h"
 
22
#include "list.h"
 
23
 
 
24
#include "internal.h"
 
25
#include <algorithm>
 
26
 
 
27
#define DUMP_STATISTICS 0
 
28
 
 
29
using std::min;
 
30
 
 
31
namespace KJS {
 
32
 
 
33
// tunable parameters
 
34
const int poolSize = 512;
 
35
const int inlineValuesSize = 5;
 
36
 
 
37
enum ListImpState { unusedInPool = 0, usedInPool, usedOnHeap, immortal };
 
38
 
 
39
struct ListImp : ListImpBase
 
40
{
 
41
    ListImpState state;
 
42
    int capacity;
 
43
    JSValue** overflow;
 
44
 
 
45
    union {
 
46
        JSValue *values[inlineValuesSize];
 
47
        ListImp *nextInFreeList;
 
48
    };
 
49
 
 
50
#if DUMP_STATISTICS
 
51
    int sizeHighWaterMark;
 
52
#endif
 
53
 
 
54
    void markValues();
 
55
};
 
56
 
 
57
struct HeapListImp : ListImp
 
58
{
 
59
    HeapListImp *nextInHeapList;
 
60
    HeapListImp *prevInHeapList;
 
61
};
 
62
 
 
63
static ListImp pool[poolSize];
 
64
static ListImp *poolFreeList;
 
65
static HeapListImp *heapList;
 
66
static int poolUsed;
 
67
 
 
68
#if DUMP_STATISTICS
 
69
 
 
70
static int numLists;
 
71
static int numListsHighWaterMark;
 
72
 
 
73
static int listSizeHighWaterMark;
 
74
 
 
75
static int numListsDestroyed;
 
76
static int numListsBiggerThan[17];
 
77
 
 
78
struct ListStatisticsExitLogger { ~ListStatisticsExitLogger(); };
 
79
 
 
80
static ListStatisticsExitLogger logger;
 
81
 
 
82
ListStatisticsExitLogger::~ListStatisticsExitLogger()
 
83
{
 
84
    printf("\nKJS::List statistics:\n\n");
 
85
    printf("%d lists were allocated\n", numLists);
 
86
    printf("%d lists was the high water mark\n", numListsHighWaterMark);
 
87
    printf("largest list had %d elements\n", listSizeHighWaterMark);
 
88
    if (numListsDestroyed) {
 
89
        putc('\n', stdout);
 
90
        for (int i = 0; i < 17; i++) {
 
91
            printf("%.1f%% of the lists (%d) had more than %d element%s\n",
 
92
                100.0 * numListsBiggerThan[i] / numListsDestroyed,
 
93
                numListsBiggerThan[i],
 
94
                i, i == 1 ? "" : "s");
 
95
        }
 
96
        putc('\n', stdout);
 
97
    }
 
98
}
 
99
 
 
100
#endif
 
101
 
 
102
inline void ListImp::markValues()
 
103
{
 
104
    int inlineSize = min(size, inlineValuesSize);
 
105
    for (int i = 0; i != inlineSize; ++i) {
 
106
        if (!values[i]->marked()) {
 
107
            values[i]->mark();
 
108
        }
 
109
    }
 
110
 
 
111
    int overflowSize = size - inlineSize;
 
112
    for (int i = 0; i != overflowSize; ++i) {
 
113
        if (!overflow[i]->marked()) {
 
114
            overflow[i]->mark();
 
115
        }
 
116
    }
 
117
}
 
118
 
 
119
void List::markProtectedLists()
 
120
{
 
121
    int seen = 0;
 
122
    int used = poolUsed;
 
123
 
 
124
    for (int i = 0; i < poolSize && seen < used; i++) {
 
125
        if (pool[i].state == usedInPool) {
 
126
            seen++;
 
127
            if (pool[i].valueRefCount > 0) {
 
128
                pool[i].markValues();
 
129
            }
 
130
        }
 
131
    }
 
132
 
 
133
    for (HeapListImp *l = heapList; l; l = l->nextInHeapList) {
 
134
        if (l->valueRefCount > 0) {
 
135
            l->markValues();
 
136
        }
 
137
    }
 
138
}
 
139
 
 
140
 
 
141
static inline ListImp *allocateListImp()
 
142
{
 
143
    ASSERT(JSLock::lockCount() > 0);
 
144
    
 
145
    // Find a free one in the pool.
 
146
    if (poolUsed < poolSize) {
 
147
        ListImp *imp = poolFreeList ? poolFreeList : &pool[0];
 
148
        poolFreeList = imp->nextInFreeList ? imp->nextInFreeList : imp + 1;
 
149
        imp->state = usedInPool;
 
150
        poolUsed++;
 
151
        return imp;
 
152
    }
 
153
    
 
154
    HeapListImp *imp = new HeapListImp;
 
155
    imp->state = usedOnHeap;
 
156
    // link into heap list
 
157
    if (heapList) {
 
158
        heapList->prevInHeapList = imp;
 
159
    }
 
160
    imp->nextInHeapList = heapList;
 
161
    imp->prevInHeapList = NULL;
 
162
    heapList = imp;
 
163
 
 
164
    return imp;
 
165
}
 
166
 
 
167
List::List() : _impBase(allocateListImp())
 
168
{
 
169
    ListImp *imp = static_cast<ListImp *>(_impBase);
 
170
    imp->size = 0;
 
171
    imp->refCount = 1;
 
172
    imp->valueRefCount = 1;
 
173
    imp->capacity = 0;
 
174
    imp->overflow = 0;
 
175
 
 
176
#if DUMP_STATISTICS
 
177
    if (++numLists > numListsHighWaterMark)
 
178
        numListsHighWaterMark = numLists;
 
179
    imp->sizeHighWaterMark = 0;
 
180
#endif
 
181
}
 
182
 
 
183
void List::markValues()
 
184
{
 
185
    static_cast<ListImp *>(_impBase)->markValues();
 
186
}
 
187
 
 
188
void List::release()
 
189
{   
 
190
    ASSERT(JSLock::lockCount() > 0);
 
191
    
 
192
    ListImp *imp = static_cast<ListImp *>(_impBase);
 
193
    
 
194
#if DUMP_STATISTICS
 
195
    --numLists;
 
196
    ++numListsDestroyed;
 
197
    for (int i = 0; i < 17; i++)
 
198
        if (imp->sizeHighWaterMark > i)
 
199
            ++numListsBiggerThan[i];
 
200
#endif
 
201
 
 
202
    delete [] imp->overflow;
 
203
    imp->overflow = 0;
 
204
 
 
205
    if (imp->state == usedInPool) {
 
206
        imp->state = unusedInPool;
 
207
        imp->nextInFreeList = poolFreeList;
 
208
        poolFreeList = imp;
 
209
        poolUsed--;
 
210
    } else {
 
211
        ASSERT(imp->state == usedOnHeap);
 
212
        HeapListImp *list = static_cast<HeapListImp *>(imp);
 
213
 
 
214
        // unlink from heap list
 
215
        if (!list->prevInHeapList) {
 
216
            heapList = list->nextInHeapList;
 
217
            if (heapList) {
 
218
                heapList->prevInHeapList = NULL;
 
219
            }
 
220
        } else {
 
221
            list->prevInHeapList->nextInHeapList = list->nextInHeapList;
 
222
            if (list->nextInHeapList) {
 
223
                list->nextInHeapList->prevInHeapList = list->prevInHeapList;
 
224
            }
 
225
        }
 
226
 
 
227
        delete list;
 
228
    }
 
229
}
 
230
 
 
231
JSValue *List::at(int i) const
 
232
{
 
233
    ListImp *imp = static_cast<ListImp *>(_impBase);
 
234
    if ((unsigned)i >= (unsigned)imp->size)
 
235
        return jsUndefined();
 
236
    if (i < inlineValuesSize)
 
237
        return imp->values[i];
 
238
    return imp->overflow[i - inlineValuesSize];
 
239
}
 
240
 
 
241
void List::clear()
 
242
{
 
243
    _impBase->size = 0;
 
244
}
 
245
 
 
246
void List::append(JSValue *v)
 
247
{
 
248
    ASSERT(JSLock::lockCount() > 0);
 
249
    
 
250
    ListImp *imp = static_cast<ListImp *>(_impBase);
 
251
 
 
252
    int i = imp->size++;
 
253
 
 
254
#if DUMP_STATISTICS
 
255
    if (imp->size > listSizeHighWaterMark)
 
256
        listSizeHighWaterMark = imp->size;
 
257
#endif
 
258
 
 
259
    if (i < inlineValuesSize) {
 
260
        imp->values[i] = v;
 
261
        return;
 
262
    }
 
263
    
 
264
    if (i >= imp->capacity) {
 
265
        int newCapacity = i * 2;
 
266
        JSValue** newOverflow = new JSValue* [newCapacity - inlineValuesSize];
 
267
        JSValue** oldOverflow = imp->overflow;
 
268
        int oldOverflowSize = i - inlineValuesSize;
 
269
        for (int j = 0; j != oldOverflowSize; j++)
 
270
            newOverflow[j] = oldOverflow[j];
 
271
        delete [] oldOverflow;
 
272
        imp->overflow = newOverflow;
 
273
        imp->capacity = newCapacity;
 
274
    }
 
275
    
 
276
    imp->overflow[i - inlineValuesSize] = v;
 
277
}
 
278
 
 
279
List List::copy() const
 
280
{
 
281
    List copy;
 
282
    copy.copyFrom(*this);
 
283
    return copy;
 
284
}
 
285
 
 
286
void List::copyFrom(const List& other)
 
287
{
 
288
    ListImp *imp = static_cast<ListImp *>(other._impBase);
 
289
 
 
290
    int size = imp->size;
 
291
 
 
292
    int inlineSize = min(size, inlineValuesSize);
 
293
    for (int i = 0; i != inlineSize; ++i)
 
294
        append(imp->values[i]);
 
295
 
 
296
    JSValue** overflow = imp->overflow;
 
297
    int overflowSize = size - inlineSize;
 
298
    for (int i = 0; i != overflowSize; ++i)
 
299
        append(overflow[i]);
 
300
}
 
301
 
 
302
 
 
303
List List::copyTail() const
 
304
{
 
305
    List copy;
 
306
 
 
307
    ListImp *imp = static_cast<ListImp *>(_impBase);
 
308
 
 
309
    int size = imp->size;
 
310
 
 
311
    int inlineSize = min(size, inlineValuesSize);
 
312
    for (int i = 1; i < inlineSize; ++i)
 
313
        copy.append(imp->values[i]);
 
314
 
 
315
    JSValue** overflow = imp->overflow;
 
316
    int overflowSize = size - inlineSize;
 
317
    for (int i = 0; i < overflowSize; ++i)
 
318
        copy.append(overflow[i]);
 
319
 
 
320
    return copy;
 
321
}
 
322
 
 
323
const List& List::empty()
 
324
{
 
325
    static List* staticEmptyList = new List;
 
326
    return *staticEmptyList;
 
327
}
 
328
 
 
329
List &List::operator=(const List &b)
 
330
{
 
331
    ListImpBase *bImpBase = b._impBase;
 
332
    ++bImpBase->refCount;
 
333
    ++bImpBase->valueRefCount;
 
334
    deref();
 
335
    _impBase = bImpBase;
 
336
    return *this;
 
337
}
 
338
 
 
339
} // namespace KJS