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 "list.h"
22 
23 #include "internal.h"
24 #include <algorithm>
25 
26 #define DUMP_STATISTICS 0
27 
28 using std::min;
29 
30 namespace KJS
31 {
32 
33 // tunable parameters
34 const int poolSize = 512;
35 
36 enum ListImpState { unusedInPool = 0, usedInPool, usedOnHeap, immortal };
37 
38 struct ListImp : ListImpBase {
39  ListImpState state;
40 
41  union {
42  int capacity; // or 0 if data is inline
43  ListImp *nextInFreeList;
44  };
45 
46  LocalStorageEntry values[inlineListValuesSize];
47 
48 #if DUMP_STATISTICS
49  int sizeHighWaterMark;
50 #endif
51 
52  void markValues();
53 };
54 
55 struct HeapListImp : ListImp {
56  HeapListImp *nextInHeapList;
57  HeapListImp *prevInHeapList;
58 };
59 
60 static ListImp pool[poolSize];
61 static ListImp *poolFreeList;
62 static HeapListImp *heapList;
63 static int poolUsed;
64 
65 #if DUMP_STATISTICS
66 
67 static int numLists;
68 static int numListsHighWaterMark;
69 
70 static int listSizeHighWaterMark;
71 
72 static int numListsDestroyed;
73 static int numListsBiggerThan[17];
74 
75 struct ListStatisticsExitLogger {
76  ~ListStatisticsExitLogger();
77 };
78 
79 static ListStatisticsExitLogger logger;
80 
81 ListStatisticsExitLogger::~ListStatisticsExitLogger()
82 {
83  printf("\nKJS::List statistics:\n\n");
84  printf("%d lists were allocated\n", numLists);
85  printf("%d lists was the high water mark\n", numListsHighWaterMark);
86  printf("largest list had %d elements\n", listSizeHighWaterMark);
87  if (numListsDestroyed) {
88  putc('\n', stdout);
89  for (int i = 0; i < 17; i++) {
90  printf("%.1f%% of the lists (%d) had more than %d element%s\n",
91  100.0 * numListsBiggerThan[i] / numListsDestroyed,
92  numListsBiggerThan[i],
93  i, i == 1 ? "" : "s");
94  }
95  putc('\n', stdout);
96  }
97 }
98 
99 #endif
100 
101 inline void ListImp::markValues()
102 {
103  for (int i = 0; i != size; ++i) {
104  if (!JSValue::marked(data[i].val.valueVal)) {
105  JSValue::mark(data[i].val.valueVal);
106  }
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 static inline ListImp *allocateListImp()
128 {
129  // Find a free one in the pool.
130  if (poolUsed < poolSize) {
131  ListImp *imp = poolFreeList ? poolFreeList : &pool[0];
132  poolFreeList = imp->nextInFreeList ? imp->nextInFreeList : imp + 1;
133  imp->state = usedInPool;
134  poolUsed++;
135  return imp;
136  }
137 
138  HeapListImp *imp = new HeapListImp;
139  imp->state = usedOnHeap;
140  // link into heap list
141  if (heapList) {
142  heapList->prevInHeapList = imp;
143  }
144  imp->nextInHeapList = heapList;
145  imp->prevInHeapList = nullptr;
146  heapList = imp;
147 
148  return imp;
149 }
150 
151 List::List() : _impBase(allocateListImp())
152 {
153  ListImp *imp = static_cast<ListImp *>(_impBase);
154  imp->size = 0;
155  imp->refCount = 1;
156  imp->capacity = 0;
157  imp->data = imp->values;
158 
159 #if DUMP_STATISTICS
160  if (++numLists > numListsHighWaterMark) {
161  numListsHighWaterMark = numLists;
162  }
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 
176  --numLists;
177  ++numListsDestroyed;
178  for (int i = 0; i < 17; i++)
179  if (imp->sizeHighWaterMark > i) {
180  ++numListsBiggerThan[i];
181  }
182 #endif
183 
184  if (imp->capacity) {
185  delete [] imp->data;
186  }
187  imp->data = nullptr;
188 
189  if (imp->state == usedInPool) {
190  imp->state = unusedInPool;
191  imp->nextInFreeList = poolFreeList;
192  poolFreeList = imp;
193  poolUsed--;
194  } else {
195  assert(imp->state == usedOnHeap);
196  HeapListImp *list = static_cast<HeapListImp *>(imp);
197 
198  // unlink from heap list
199  if (!list->prevInHeapList) {
200  heapList = list->nextInHeapList;
201  if (heapList) {
202  heapList->prevInHeapList = nullptr;
203  }
204  } else {
205  list->prevInHeapList->nextInHeapList = list->nextInHeapList;
206  if (list->nextInHeapList) {
207  list->nextInHeapList->prevInHeapList = list->prevInHeapList;
208  }
209  }
210 
211  delete list;
212  }
213 }
214 
215 void List::appendSlowCase(JSValue *v)
216 {
217  ListImp *imp = static_cast<ListImp *>(_impBase);
218 
219  int i = imp->size++; // insert index/old size
220 
221 #if DUMP_STATISTICS
222  if (imp->size > listSizeHighWaterMark) {
223  listSizeHighWaterMark = imp->size;
224  }
225 #endif
226 
227  // If we got here, we need to use an out-of-line buffer.
228 
229  if (i >= imp->capacity) {
230  int newCapacity = i * 2;
231 
232  LocalStorageEntry *newBuffer = new LocalStorageEntry[newCapacity];
233 
234  // Copy everything over
235  for (int c = 0; c < i; ++c) {
236  newBuffer[c] = imp->data[c];
237  }
238 
239  if (imp->capacity) { // had an old out-of-line buffer
240  delete[] imp->data;
241  }
242 
243  imp->data = newBuffer;
244  imp->capacity = newCapacity;
245  }
246 
247  imp->data[i].val.valueVal = v;
248 }
249 
250 List List::copy() const
251 {
252  List copy;
253  copy.copyFrom(*this);
254  return copy;
255 }
256 
257 void List::copyFrom(const List &other)
258 {
259  // Assumption: we're empty (e.g. called from copy)
260  ListImpBase *otherImp = other._impBase;
261  ListImp *ourImp = static_cast<ListImp *>(_impBase);
262 
263  assert(ourImp->size == 0 && ourImp->capacity == 0);
264 
265  int size = otherImp->size;
266  ourImp->size = size;
267 
268  if (size > inlineListValuesSize) {
269  // need an out-of-line buffer
270  ourImp->capacity = size;
271  ourImp->data = new LocalStorageEntry[size];
272  } else {
273  ourImp->capacity = 0;
274  }
275 
276  for (int c = 0; c < size; ++c) {
277  ourImp->data[c] = otherImp->data[c];
278  }
279 }
280 
281 List List::copyTail() const
282 {
283  List copy;
284 
285  ListImpBase *inImp = _impBase;
286  ListImp *outImp = static_cast<ListImp *>(copy._impBase);
287 
288  int size = inImp->size - 1;
289 
290  if (size < 0) {
291  size = 0; // copyTail on empty list.
292  }
293 
294  outImp->size = size;
295 
296  if (size > inlineListValuesSize) {
297  // need an out-of-line buffer
298  outImp->capacity = size;
299  outImp->data = new LocalStorageEntry[size];
300  } else {
301  outImp->capacity = 0;
302  }
303 
304  for (int c = 0; c < size; ++c) {
305  outImp->data[c] = inImp->data[c + 1];
306  }
307 
308  return copy;
309 }
310 
311 const List &List::empty()
312 {
313  static List emptyList;
314  return emptyList;
315 }
316 
317 List &List::operator=(const List &b)
318 {
319  ListImpBase *bImpBase = b._impBase;
320  ++bImpBase->refCount;
321  deref();
322  _impBase = bImpBase;
323  return *this;
324 }
325 
326 } // namespace KJS
327 
virtual void release(quint64 objid)
KIOFILEWIDGETS_EXPORT QStringList list(const QString &fileClass)
QCA_EXPORT Logger * logger()
Native list type.
Definition: list.h:52
QVector< V > values(const QMultiHash< K, V > &c)
This file is part of the KDE documentation.
Documentation copyright © 1996-2022 The KDE developers.
Generated on Wed May 25 2022 03:58:40 by doxygen 1.8.17 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.