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