d77844328275f11ad89cb4f75ce47aec7b8b5794
[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 = 512;
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     ListImp *nextInOutsideList;
46     ListImp *prevInOutsideList;
47
48 #if DUMP_STATISTICS
49     int sizeHighWaterMark;
50 #endif
51
52     void markValues();
53 };
54
55 static ListImp pool[poolSize];
56 static ListImp *poolFreeList;
57 static ListImp *outsidePoolList;
58 static int poolUsed;
59
60 #if DUMP_STATISTICS
61
62 static int numLists;
63 static int numListsHighWaterMark;
64
65 static int listSizeHighWaterMark;
66
67 static int numListsDestroyed;
68 static int numListsBiggerThan[17];
69
70 struct ListStatisticsExitLogger { ~ListStatisticsExitLogger(); };
71
72 static ListStatisticsExitLogger logger;
73
74 ListStatisticsExitLogger::~ListStatisticsExitLogger()
75 {
76     printf("\nKJS::List statistics:\n\n");
77     printf("%d lists were allocated\n", numLists);
78     printf("%d lists was the high water mark\n", numListsHighWaterMark);
79     printf("largest list had %d elements\n", listSizeHighWaterMark);
80     if (numListsDestroyed) {
81         putc('\n', stdout);
82         for (int i = 0; i < 17; i++) {
83             printf("%.1f%% of the lists (%d) had more than %d element%s\n",
84                 100.0 * numListsBiggerThan[i] / numListsDestroyed,
85                 numListsBiggerThan[i],
86                 i, i == 1 ? "" : "s");
87         }
88         putc('\n', stdout);
89     }
90 }
91
92 #endif
93
94
95 inline void ListImp::markValues()
96 {
97     int inlineSize = MIN(size, inlineValuesSize);
98     for (int i = 0; i != inlineSize; ++i) {
99         if (!values[i]->marked()) {
100             values[i]->mark();
101         }
102     }
103
104     int overflowSize = size - inlineSize;
105     for (int i = 0; i != overflowSize; ++i) {
106         if (!overflow[i]->marked()) {
107             overflow[i]->mark();
108         }
109     }
110 }
111
112 void List::markProtectedLists()
113 {
114 #if TEST_CONSERVATIVE_GC || USE_CONSERVATIVE_GC
115     int seen = 0;
116     for (int i = 0; i < poolSize; i++) {
117         if (seen >= poolUsed)
118             break;
119
120         if (pool[i].state == usedInPool) {
121             seen++;
122             if (pool[i].valueRefCount > 0) {
123                 pool[i].markValues();
124             }
125         }
126     }
127
128     for (ListImp *l = outsidePoolList; l; l = l->nextInOutsideList) {
129         if (l->valueRefCount > 0) {
130             l->markValues();
131         }
132     }
133 #endif
134 }
135
136
137 static inline ListImp *allocateListImp()
138 {
139     // Find a free one in the pool.
140     if (poolUsed < poolSize) {
141         ListImp *imp = poolFreeList ? poolFreeList : &pool[0];
142         poolFreeList = imp->nextInFreeList ? imp->nextInFreeList : imp + 1;
143         imp->state = usedInPool;
144         poolUsed++;
145         return imp;
146     }
147     
148     ListImp *imp = new ListImp;
149     imp->state = usedOnHeap;
150     // link into outside pool list
151     if (outsidePoolList) {
152         outsidePoolList->prevInOutsideList = imp;
153     }
154     imp->nextInOutsideList = outsidePoolList;
155     imp->prevInOutsideList = NULL;
156     outsidePoolList = imp;
157
158     return imp;
159 }
160
161 static inline void deallocateListImp(ListImp *imp)
162 {
163     if (imp->state == usedInPool) {
164         imp->state = unusedInPool;
165         imp->nextInFreeList = poolFreeList;
166         poolFreeList = imp;
167         poolUsed--;
168     } else {
169         // unlink from outside pool list
170         if (!imp->prevInOutsideList) {
171             outsidePoolList = imp->nextInOutsideList;
172             if (outsidePoolList) {
173                 outsidePoolList->prevInOutsideList = NULL;
174             }
175         } else {
176             imp->prevInOutsideList->nextInOutsideList = imp->nextInOutsideList;
177             if (imp->nextInOutsideList) {
178                 imp->nextInOutsideList->prevInOutsideList = imp->prevInOutsideList;
179             }
180         }
181
182         delete imp;
183     }
184 }
185
186 List::List() : _impBase(allocateListImp()), _needsMarking(false)
187 {
188     ListImp *imp = static_cast<ListImp *>(_impBase);
189     imp->size = 0;
190     imp->refCount = 1;
191     imp->capacity = 0;
192     imp->overflow = 0;
193
194     if (!_needsMarking) {
195         imp->valueRefCount = 1;
196     }
197 #if DUMP_STATISTICS
198     if (++numLists > numListsHighWaterMark)
199         numListsHighWaterMark = numLists;
200     imp->sizeHighWaterMark = 0;
201 #endif
202 }
203
204 List::List(bool needsMarking) : _impBase(allocateListImp()), _needsMarking(needsMarking)
205 {
206     ListImp *imp = static_cast<ListImp *>(_impBase);
207     imp->size = 0;
208     imp->refCount = 1;
209     imp->capacity = 0;
210     imp->overflow = 0;
211
212     if (!_needsMarking) {
213         imp->valueRefCount = 1;
214     }
215
216 #if DUMP_STATISTICS
217     if (++numLists > numListsHighWaterMark)
218         numListsHighWaterMark = numLists;
219     imp->sizeHighWaterMark = 0;
220 #endif
221 }
222
223 void List::derefValues()
224 {
225 #if !USE_CONSERVATIVE_GC
226     ListImp *imp = static_cast<ListImp *>(_impBase);
227     
228     int size = imp->size;
229     
230     int inlineSize = MIN(size, inlineValuesSize);
231     for (int i = 0; i != inlineSize; ++i)
232         imp->values[i]->deref();
233
234     int overflowSize = size - inlineSize;
235     ValueImp **overflow = imp->overflow;
236
237     for (int i = 0; i != overflowSize; ++i)
238         overflow[i]->deref();
239 #endif
240 }
241
242 void List::refValues()
243 {
244 #if !USE_CONSERVATIVE_GC
245     ListImp *imp = static_cast<ListImp *>(_impBase);
246     
247     int size = imp->size;
248     
249     int inlineSize = MIN(size, inlineValuesSize);
250     for (int i = 0; i != inlineSize; ++i)
251         imp->values[i]->ref();
252     
253     int overflowSize = size - inlineSize;
254     ValueImp **overflow = imp->overflow;
255     for (int i = 0; i != overflowSize; ++i)
256         overflow[i]->ref();
257 #endif
258 }
259
260 void List::markValues()
261 {
262     static_cast<ListImp *>(_impBase)->markValues();
263 }
264
265 void List::release()
266 {
267     ListImp *imp = static_cast<ListImp *>(_impBase);
268     
269 #if DUMP_STATISTICS
270     --numLists;
271     ++numListsDestroyed;
272     for (int i = 0; i < 17; i++)
273         if (imp->sizeHighWaterMark > i)
274             ++numListsBiggerThan[i];
275 #endif
276
277     delete [] imp->overflow;
278     deallocateListImp(imp);
279 }
280
281 ValueImp *List::impAt(int i) const
282 {
283     ListImp *imp = static_cast<ListImp *>(_impBase);
284     if ((unsigned)i >= (unsigned)imp->size)
285         return UndefinedImp::staticUndefined;
286     if (i < inlineValuesSize)
287         return imp->values[i];
288     return imp->overflow[i - inlineValuesSize];
289 }
290
291 void List::clear()
292 {
293     if (_impBase->valueRefCount > 0) {
294         derefValues();
295     }
296     _impBase->size = 0;
297 }
298
299 void List::append(ValueImp *v)
300 {
301     ListImp *imp = static_cast<ListImp *>(_impBase);
302
303     int i = imp->size++;
304
305 #if DUMP_STATISTICS
306     if (imp->size > listSizeHighWaterMark)
307         listSizeHighWaterMark = imp->size;
308 #endif
309
310     if (imp->valueRefCount > 0) {
311 #if !USE_CONSERVATIVE_GC
312         v->ref();
313 #endif
314     }
315     
316     if (i < inlineValuesSize) {
317         imp->values[i] = v;
318         return;
319     }
320     
321     if (i >= imp->capacity) {
322         int newCapacity = i * 2;
323         ValueImp **newOverflow = new ValueImp * [newCapacity - inlineValuesSize];
324         ValueImp **oldOverflow = imp->overflow;
325         int oldOverflowSize = i - inlineValuesSize;
326         for (int j = 0; j != oldOverflowSize; j++)
327             newOverflow[j] = oldOverflow[j];
328         delete [] oldOverflow;
329         imp->overflow = newOverflow;
330         imp->capacity = newCapacity;
331     }
332     
333     imp->overflow[i - inlineValuesSize] = v;
334 }
335
336 List List::copy() const
337 {
338     List copy;
339
340     ListImp *imp = static_cast<ListImp *>(_impBase);
341
342     int size = imp->size;
343
344     int inlineSize = MIN(size, inlineValuesSize);
345     for (int i = 0; i != inlineSize; ++i)
346         copy.append(imp->values[i]);
347
348     ValueImp **overflow = imp->overflow;
349     int overflowSize = size - inlineSize;
350     for (int i = 0; i != overflowSize; ++i)
351         copy.append(overflow[i]);
352
353     return copy;
354 }
355
356
357 List List::copyTail() const
358 {
359     List copy;
360
361     ListImp *imp = static_cast<ListImp *>(_impBase);
362
363     int size = imp->size;
364
365     int inlineSize = MIN(size, inlineValuesSize);
366     for (int i = 1; i < inlineSize; ++i)
367         copy.append(imp->values[i]);
368
369     ValueImp **overflow = imp->overflow;
370     int overflowSize = size - inlineSize;
371     for (int i = 0; i < overflowSize; ++i)
372         copy.append(overflow[i]);
373
374     return copy;
375 }
376
377 const List &List::empty()
378 {
379     static List emptyList;
380     return emptyList;
381 }
382
383 } // namespace KJS