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 | |
29 | using std::min; |
30 | |
31 | namespace KJS { |
32 | |
33 | // tunable parameters |
34 | const int poolSize = 512; |
35 | |
36 | |
37 | enum ListImpState { unusedInPool = 0, usedInPool, usedOnHeap, immortal }; |
38 | |
39 | struct 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 | |
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 | for (int i = 0; i != size; ++i) { |
105 | if (!data[i].val.valueVal->marked()) |
106 | data[i].val.valueVal->mark(); |
107 | } |
108 | } |
109 | |
110 | void 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 | |
128 | static 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 | |
152 | List::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 | |
167 | void 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 | |
212 | void 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 | |
244 | List List::copy() const |
245 | { |
246 | List copy; |
247 | copy.copyFrom(*this); |
248 | return copy; |
249 | } |
250 | |
251 | void 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 | |
275 | List 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 | |
303 | const List &List::empty() |
304 | { |
305 | static List emptyList; |
306 | return emptyList; |
307 | } |
308 | |
309 | List &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 | |