• Skip to content
  • Skip to link menu
Trinity API Reference
  • Trinity API Reference
  • kjs
 

kjs

  • 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., 51 Franklin Street, Fifth Floor,
18  * Boston, MA 02110-1301, USA.
19  *
20  */
21 
22 #include "list.h"
23 
24 #include "internal.h"
25 
26 #ifndef MIN
27 #define MIN(a,b) ((a) < (b) ? (a) : (b))
28 #endif
29 
30 #define DUMP_STATISTICS 0
31 
32 namespace KJS {
33 
34 // tunable parameters
35 const int poolSize = 32; // must be a power of 2
36 const int inlineValuesSize = 4;
37 
38 // derived constants
39 const int poolSizeMask = poolSize - 1;
40 
41 enum ListImpState { unusedInPool = 0, usedInPool, usedOnHeap, immortal };
42 
43 struct ListImp : ListImpBase
44 {
45  ListImpState state;
46  ValueImp *values[inlineValuesSize];
47  int capacity;
48  ValueImp **overflow;
49 
50 #if DUMP_STATISTICS
51  int sizeHighWaterMark;
52 #endif
53 };
54 
55 static ListImp pool[poolSize];
56 static int poolCursor;
57 
58 #if DUMP_STATISTICS
59 
60 static int numLists;
61 static int numListsHighWaterMark;
62 
63 static int listSizeHighWaterMark;
64 
65 static int numListsDestroyed;
66 static int numListsBiggerThan[17];
67 
68 struct ListStatisticsExitLogger { ~ListStatisticsExitLogger(); };
69 
70 static ListStatisticsExitLogger logger;
71 
72 ListStatisticsExitLogger::~ListStatisticsExitLogger()
73 {
74  printf("\nKJS::List statistics:\n\n");
75  printf("%d lists were allocated\n", numLists);
76  printf("%d lists was the high water mark\n", numListsHighWaterMark);
77  printf("largest list had %d elements\n", listSizeHighWaterMark);
78  if (numListsDestroyed) {
79  putc('\n', stdout);
80  for (int i = 0; i < 17; i++) {
81  printf("%.1f%% of the lists (%d) had more than %d element%s\n",
82  100.0 * numListsBiggerThan[i] / numListsDestroyed,
83  numListsBiggerThan[i],
84  i, i == 1 ? "" : "s");
85  }
86  putc('\n', stdout);
87  }
88 }
89 
90 #endif
91 
92 static inline ListImp *allocateListImp()
93 {
94  // Find a free one in the pool.
95  int c = poolCursor;
96  int i = c;
97  do {
98  ListImp *imp = &pool[i];
99  ListImpState s = imp->state;
100  i = (i + 1) & poolSizeMask;
101  if (s == unusedInPool) {
102  poolCursor = i;
103  imp->state = usedInPool;
104  return imp;
105  }
106  } while (i != c);
107 
108  ListImp *imp = new ListImp;
109  imp->state = usedOnHeap;
110  return imp;
111 }
112 
113 static inline void deallocateListImp(ListImp *imp)
114 {
115  if (imp->state == usedInPool)
116  imp->state = unusedInPool;
117  else
118  delete imp;
119 }
120 
121 List::List() : _impBase(allocateListImp()), _needsMarking(false)
122 {
123  ListImp *imp = static_cast<ListImp *>(_impBase);
124  imp->size = 0;
125  imp->refCount = 1;
126  imp->capacity = 0;
127  imp->overflow = 0;
128 
129  if (!_needsMarking) {
130  imp->valueRefCount = 1;
131  }
132 #if DUMP_STATISTICS
133  if (++numLists > numListsHighWaterMark)
134  numListsHighWaterMark = numLists;
135  imp->sizeHighWaterMark = 0;
136 #endif
137 }
138 
139 List::List(bool needsMarking) : _impBase(allocateListImp()), _needsMarking(needsMarking)
140 {
141  ListImp *imp = static_cast<ListImp *>(_impBase);
142  imp->size = 0;
143  imp->refCount = 1;
144  imp->capacity = 0;
145  imp->overflow = 0;
146 
147  if (!_needsMarking) {
148  imp->valueRefCount = 1;
149  }
150 
151 #if DUMP_STATISTICS
152  if (++numLists > numListsHighWaterMark)
153  numListsHighWaterMark = numLists;
154  imp->sizeHighWaterMark = 0;
155 #endif
156 }
157 
158 void List::derefValues()
159 {
160  ListImp *imp = static_cast<ListImp *>(_impBase);
161 
162  int size = imp->size;
163 
164  int inlineSize = MIN(size, inlineValuesSize);
165  for (int i = 0; i != inlineSize; ++i)
166  imp->values[i]->deref();
167 
168  int overflowSize = size - inlineSize;
169  ValueImp **overflow = imp->overflow;
170  for (int i = 0; i != overflowSize; ++i)
171  overflow[i]->deref();
172 }
173 
174 void List::refValues()
175 {
176  ListImp *imp = static_cast<ListImp *>(_impBase);
177 
178  int size = imp->size;
179 
180  int inlineSize = MIN(size, inlineValuesSize);
181  for (int i = 0; i != inlineSize; ++i)
182  imp->values[i]->ref();
183 
184  int overflowSize = size - inlineSize;
185  ValueImp **overflow = imp->overflow;
186  for (int i = 0; i != overflowSize; ++i)
187  overflow[i]->ref();
188 }
189 
190 void List::markValues()
191 {
192  ListImp *imp = static_cast<ListImp *>(_impBase);
193 
194  int size = imp->size;
195 
196  int inlineSize = MIN(size, inlineValuesSize);
197  for (int i = 0; i != inlineSize; ++i) {
198  if (!imp->values[i]->marked()) {
199  imp->values[i]->mark();
200  }
201  }
202 
203  int overflowSize = size - inlineSize;
204  ValueImp **overflow = imp->overflow;
205  for (int i = 0; i != overflowSize; ++i) {
206  if (!overflow[i]->marked()) {
207  overflow[i]->mark();
208  }
209  }
210 }
211 
212 void List::release()
213 {
214  ListImp *imp = static_cast<ListImp *>(_impBase);
215 
216 #if DUMP_STATISTICS
217  --numLists;
218  ++numListsDestroyed;
219  for (int i = 0; i < 17; i++)
220  if (imp->sizeHighWaterMark > i)
221  ++numListsBiggerThan[i];
222 #endif
223 
224  delete [] imp->overflow;
225  deallocateListImp(imp);
226 }
227 
228 ValueImp *List::impAt(int i) const
229 {
230  ListImp *imp = static_cast<ListImp *>(_impBase);
231  if ((unsigned)i >= (unsigned)imp->size)
232  return UndefinedImp::staticUndefined;
233  if (i < inlineValuesSize)
234  return imp->values[i];
235  return imp->overflow[i - inlineValuesSize];
236 }
237 
238 void List::clear()
239 {
240  if (_impBase->valueRefCount > 0) {
241  derefValues();
242  }
243  _impBase->size = 0;
244 }
245 
246 void List::append(ValueImp *v)
247 {
248  ListImp *imp = static_cast<ListImp *>(_impBase);
249 
250  int i = imp->size++;
251 
252 #if DUMP_STATISTICS
253  if (imp->size > listSizeHighWaterMark)
254  listSizeHighWaterMark = imp->size;
255 #endif
256 
257  if (imp->valueRefCount > 0) {
258  v->ref();
259  }
260 
261  if (i < inlineValuesSize) {
262  imp->values[i] = v;
263  return;
264  }
265 
266  if (i >= imp->capacity) {
267  int newCapacity = i * 2;
268  ValueImp **newOverflow = new ValueImp * [newCapacity - inlineValuesSize];
269  ValueImp **oldOverflow = imp->overflow;
270  int oldOverflowSize = i - inlineValuesSize;
271  for (int j = 0; j != oldOverflowSize; j++)
272  newOverflow[j] = oldOverflow[j];
273  delete [] oldOverflow;
274  imp->overflow = newOverflow;
275  imp->capacity = newCapacity;
276  }
277 
278  imp->overflow[i - inlineValuesSize] = v;
279 }
280 
281 List List::copy() const
282 {
283  List copy;
284 
285  ListImp *imp = static_cast<ListImp *>(_impBase);
286 
287  int size = imp->size;
288 
289  int inlineSize = MIN(size, inlineValuesSize);
290  for (int i = 0; i != inlineSize; ++i)
291  copy.append(imp->values[i]);
292 
293  ValueImp **overflow = imp->overflow;
294  int overflowSize = size - inlineSize;
295  for (int i = 0; i != overflowSize; ++i)
296  copy.append(overflow[i]);
297 
298  return copy;
299 }
300 
301 
302 List List::copyTail() const
303 {
304  List copy;
305 
306  ListImp *imp = static_cast<ListImp *>(_impBase);
307 
308  int size = imp->size;
309 
310  int inlineSize = MIN(size, inlineValuesSize);
311  for (int i = 1; i < inlineSize; ++i)
312  copy.append(imp->values[i]);
313 
314  ValueImp **overflow = imp->overflow;
315  int overflowSize = size - inlineSize;
316  for (int i = 0; i < overflowSize; ++i)
317  copy.append(overflow[i]);
318 
319  return copy;
320 }
321 
322 const List &List::empty()
323 {
324  static List emptyList;
325  return emptyList;
326 }
327 
328 } // namespace KJS
KJS::List::append
void append(const Value &val)
Append an object to the end of the list.
Definition: list.h:66
KJS::List::copyTail
List copyTail() const
Make a copy of the list, omitting the first element.
Definition: list.cpp:302
KJS
Definition: array_instance.h:27
KJS::ValueImp
ValueImp is the base type for all primitives (Undefined, Null, Boolean, String, Number) and objects i...
Definition: value.h:78
KJS::List::size
int size() const
Definition: list.h:90
KJS::List::empty
static const List & empty()
Returns a pointer to a static instance of an empty list.
Definition: list.cpp:322
KJS::List::clear
void clear()
Remove all elements from the list.
Definition: list.cpp:238
KJS::List
Native list type.
Definition: list.h:48
KJS::List::copy
List copy() const
Make a copy of the list.
Definition: list.cpp:281

kjs

Skip menu "kjs"
  • Main Page
  • Class Hierarchy
  • Alphabetical List
  • Class List
  • File List
  • Class Members
  • Related Pages

kjs

Skip menu "kjs"
  • arts
  • dcop
  • dnssd
  • interfaces
  •   kspeech
  •     interface
  •     library
  •   tdetexteditor
  • kate
  • kded
  • kdoctools
  • kimgio
  • kjs
  • libtdemid
  • libtdescreensaver
  •     tdecore
  • tdeabc
  • tdecmshell
  • tdecore
  • tdefx
  • tdehtml
  • tdeinit
  • tdeio
  •   bookmarks
  •   httpfilter
  •   kpasswdserver
  •   kssl
  • tdeioslave
  •   http
  •   tdefile
  •   tdeio
  •   tdeioexec
  • tdemdi
  •   tdemdi
  • tdenewstuff
  • tdeparts
  • tdeprint
  • tderandr
  • tderesources
  • tdespell2
  • tdesu
  • tdeui
  • tdeunittest
  • tdeutils
  • tdewallet
Generated for kjs by doxygen 1.8.8
This website is maintained by Timothy Pearson.