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 "list.h"
22#include <config-kjs.h>
23
24#include "internal.h"
25#include <algorithm>
26
27#define DUMP_STATISTICS 0
28
29using std::min;
30
31namespace KJS {
32
33// tunable parameters
34const int poolSize = 512;
35
36
37enum ListImpState { unusedInPool = 0, usedInPool, usedOnHeap, immortal };
38
39struct ListImp : ListImpBase
40{
41 ListImpState state;
42
43 union {
44 int capacity; // or 0 if data is inline
45 ListImp *nextInFreeList;
46 };
47
48 LocalStorageEntry values[inlineListValuesSize];
49
50#if DUMP_STATISTICS
51 int sizeHighWaterMark;
52#endif
53
54 void markValues();
55};
56
57struct HeapListImp : ListImp
58{
59 HeapListImp *nextInHeapList;
60 HeapListImp *prevInHeapList;
61};
62
63static ListImp pool[poolSize];
64static ListImp *poolFreeList;
65static HeapListImp *heapList;
66static int poolUsed;
67
68#if DUMP_STATISTICS
69
70static int numLists;
71static int numListsHighWaterMark;
72
73static int listSizeHighWaterMark;
74
75static int numListsDestroyed;
76static int numListsBiggerThan[17];
77
78struct ListStatisticsExitLogger { ~ListStatisticsExitLogger(); };
79
80static ListStatisticsExitLogger logger;
81
82ListStatisticsExitLogger::~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
102inline void ListImp::markValues()
103{
104 for (int i = 0; i != size; ++i) {
105 if (!data[i].val.valueVal->marked())
106 data[i].val.valueVal->mark();
107 }
108}
109
110void List::markProtectedLists()
111{
112 int seen = 0;
113 int used = poolUsed;
114
115 for (int i = 0; i < poolSize && seen < used; i++) {
116 if (pool[i].state == usedInPool) {
117 seen++;
118 pool[i].markValues();
119 }
120 }
121
122 for (HeapListImp *l = heapList; l; l = l->nextInHeapList) {
123 l->markValues();
124 }
125}
126
127
128static inline ListImp *allocateListImp()
129{
130 // Find a free one in the pool.
131 if (poolUsed < poolSize) {
132 ListImp *imp = poolFreeList ? poolFreeList : &pool[0];
133 poolFreeList = imp->nextInFreeList ? imp->nextInFreeList : imp + 1;
134 imp->state = usedInPool;
135 poolUsed++;
136 return imp;
137 }
138
139 HeapListImp *imp = new HeapListImp;
140 imp->state = usedOnHeap;
141 // link into heap list
142 if (heapList) {
143 heapList->prevInHeapList = imp;
144 }
145 imp->nextInHeapList = heapList;
146 imp->prevInHeapList = NULL;
147 heapList = imp;
148
149 return imp;
150}
151
152List::List() : _impBase(allocateListImp())
153{
154 ListImp *imp = static_cast<ListImp *>(_impBase);
155 imp->size = 0;
156 imp->refCount = 1;
157 imp->capacity = 0;
158 imp->data = imp->values;
159
160#if DUMP_STATISTICS
161 if (++numLists > numListsHighWaterMark)
162 numListsHighWaterMark = numLists;
163 imp->sizeHighWaterMark = 0;
164#endif
165}
166
167void List::release()
168{
169 ListImp *imp = static_cast<ListImp *>(_impBase);
170
171#if DUMP_STATISTICS
172 if (imp->size > imp->sizeHighWaterMark)
173 imp->sizeHighWaterMark = imp->size;
174
175 --numLists;
176 ++numListsDestroyed;
177 for (int i = 0; i < 17; i++)
178 if (imp->sizeHighWaterMark > i)
179 ++numListsBiggerThan[i];
180#endif
181
182 if (imp->capacity)
183 delete [] imp->data;
184 imp->data = 0;
185
186 if (imp->state == usedInPool) {
187 imp->state = unusedInPool;
188 imp->nextInFreeList = poolFreeList;
189 poolFreeList = imp;
190 poolUsed--;
191 } else {
192 assert(imp->state == usedOnHeap);
193 HeapListImp *list = static_cast<HeapListImp *>(imp);
194
195 // unlink from heap list
196 if (!list->prevInHeapList) {
197 heapList = list->nextInHeapList;
198 if (heapList) {
199 heapList->prevInHeapList = NULL;
200 }
201 } else {
202 list->prevInHeapList->nextInHeapList = list->nextInHeapList;
203 if (list->nextInHeapList) {
204 list->nextInHeapList->prevInHeapList = list->prevInHeapList;
205 }
206 }
207
208 delete list;
209 }
210}
211
212void List::appendSlowCase(JSValue *v)
213{
214 ListImp *imp = static_cast<ListImp *>(_impBase);
215
216 int i = imp->size++; // insert index/old size
217
218#if DUMP_STATISTICS
219 if (imp->size > listSizeHighWaterMark)
220 listSizeHighWaterMark = imp->size;
221#endif
222
223 // If we got here, we need to use an out-of-line buffer.
224
225 if (i >= imp->capacity) {
226 int newCapacity = i * 2;
227
228 LocalStorageEntry* newBuffer = new LocalStorageEntry[newCapacity];
229
230 // Copy everything over
231 for (int c = 0; c < i; ++c)
232 newBuffer[c] = imp->data[c];
233
234 if (imp->capacity) // had an old out-of-line buffer
235 delete[] imp->data;
236
237 imp->data = newBuffer;
238 imp->capacity = newCapacity;
239 }
240
241 imp->data[i].val.valueVal = v;
242}
243
244List List::copy() const
245{
246 List copy;
247 copy.copyFrom(*this);
248 return copy;
249}
250
251void List::copyFrom(const List& other)
252{
253 // Assumption: we're empty (e.g. called from copy)
254 ListImpBase* otherImp = other._impBase;
255 ListImp* ourImp = static_cast<ListImp *>(_impBase);
256
257 assert(ourImp->size == 0 && ourImp->capacity == 0);
258
259 int size = otherImp->size;
260 ourImp->size = size;
261
262 if (size > inlineListValuesSize) {
263 // need an out-of-line buffer
264 ourImp->capacity = size;
265 ourImp->data = new LocalStorageEntry[size];
266 } else {
267 ourImp->capacity = 0;
268 }
269
270 for (int c = 0; c < size; ++c)
271 ourImp->data[c] = otherImp->data[c];
272}
273
274
275List List::copyTail() const
276{
277 List copy;
278
279 ListImpBase* inImp = _impBase;
280 ListImp* outImp = static_cast<ListImp *>(copy._impBase);
281
282 int size = inImp->size - 1;
283
284 if (size < 0)
285 size = 0; // copyTail on empty list.
286
287 outImp->size = size;
288
289 if (size > inlineListValuesSize) {
290 // need an out-of-line buffer
291 outImp->capacity = size;
292 outImp->data = new LocalStorageEntry[size];
293 } else {
294 outImp->capacity = 0;
295 }
296
297 for (int c = 0; c < size; ++c)
298 outImp->data[c] = inImp->data[c+1];
299
300 return copy;
301}
302
303const List &List::empty()
304{
305 static List emptyList;
306 return emptyList;
307}
308
309List &List::operator=(const List &b)
310{
311 ListImpBase *bImpBase = b._impBase;
312 ++bImpBase->refCount;
313 deref();
314 _impBase = bImpBase;
315 return *this;
316}
317
318} // namespace KJS
319
320// kate: indent-width 4; replace-tabs on; tab-width 4; space-indent on;
321