kjs Library API Documentation

list.cpp

00001 /* 00002 * This file is part of the KDE libraries 00003 * Copyright (C) 2003 Apple Computer, Inc. 00004 * 00005 * This library is free software; you can redistribute it and/or 00006 * modify it under the terms of the GNU Library General Public 00007 * License as published by the Free Software Foundation; either 00008 * version 2 of the License, or (at your option) any later version. 00009 * 00010 * This library is distributed in the hope that it will be useful, 00011 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00013 * Library General Public License for more details. 00014 * 00015 * You should have received a copy of the GNU Library General Public License 00016 * along with this library; see the file COPYING.LIB. If not, write to 00017 * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, 00018 * Boston, MA 02111-1307, USA. 00019 * 00020 */ 00021 00022 #include "list.h" 00023 00024 #include "internal.h" 00025 00026 #ifndef MIN 00027 #define MIN(a,b) ((a) < (b) ? (a) : (b)) 00028 #endif 00029 00030 #define DUMP_STATISTICS 0 00031 00032 namespace KJS { 00033 00034 // tunable parameters 00035 const int poolSize = 32; // must be a power of 2 00036 const int inlineValuesSize = 4; 00037 00038 // derived constants 00039 const int poolSizeMask = poolSize - 1; 00040 00041 enum ListImpState { unusedInPool = 0, usedInPool, usedOnHeap, immortal }; 00042 00043 struct ListImp : ListImpBase 00044 { 00045 ListImpState state; 00046 ValueImp *values[inlineValuesSize]; 00047 int capacity; 00048 ValueImp **overflow; 00049 00050 #if DUMP_STATISTICS 00051 int sizeHighWaterMark; 00052 #endif 00053 }; 00054 00055 static ListImp pool[poolSize]; 00056 static int poolCursor; 00057 00058 #if DUMP_STATISTICS 00059 00060 static int numLists; 00061 static int numListsHighWaterMark; 00062 00063 static int listSizeHighWaterMark; 00064 00065 static int numListsDestroyed; 00066 static int numListsBiggerThan[17]; 00067 00068 struct ListStatisticsExitLogger { ~ListStatisticsExitLogger(); }; 00069 00070 static ListStatisticsExitLogger logger; 00071 00072 ListStatisticsExitLogger::~ListStatisticsExitLogger() 00073 { 00074 printf("\nKJS::List statistics:\n\n"); 00075 printf("%d lists were allocated\n", numLists); 00076 printf("%d lists was the high water mark\n", numListsHighWaterMark); 00077 printf("largest list had %d elements\n", listSizeHighWaterMark); 00078 if (numListsDestroyed) { 00079 putc('\n', stdout); 00080 for (int i = 0; i < 17; i++) { 00081 printf("%.1f%% of the lists (%d) had more than %d element%s\n", 00082 100.0 * numListsBiggerThan[i] / numListsDestroyed, 00083 numListsBiggerThan[i], 00084 i, i == 1 ? "" : "s"); 00085 } 00086 putc('\n', stdout); 00087 } 00088 } 00089 00090 #endif 00091 00092 static inline ListImp *allocateListImp() 00093 { 00094 // Find a free one in the pool. 00095 int c = poolCursor; 00096 int i = c; 00097 do { 00098 ListImp *imp = &pool[i]; 00099 ListImpState s = imp->state; 00100 i = (i + 1) & poolSizeMask; 00101 if (s == unusedInPool) { 00102 poolCursor = i; 00103 imp->state = usedInPool; 00104 return imp; 00105 } 00106 } while (i != c); 00107 00108 ListImp *imp = new ListImp; 00109 imp->state = usedOnHeap; 00110 return imp; 00111 } 00112 00113 static inline void deallocateListImp(ListImp *imp) 00114 { 00115 if (imp->state == usedInPool) 00116 imp->state = unusedInPool; 00117 else 00118 delete imp; 00119 } 00120 00121 List::List() : _impBase(allocateListImp()), _needsMarking(false) 00122 { 00123 ListImp *imp = static_cast<ListImp *>(_impBase); 00124 imp->size = 0; 00125 imp->refCount = 1; 00126 imp->capacity = 0; 00127 imp->overflow = 0; 00128 00129 if (!_needsMarking) { 00130 imp->valueRefCount = 1; 00131 } 00132 #if DUMP_STATISTICS 00133 if (++numLists > numListsHighWaterMark) 00134 numListsHighWaterMark = numLists; 00135 imp->sizeHighWaterMark = 0; 00136 #endif 00137 } 00138 00139 List::List(bool needsMarking) : _impBase(allocateListImp()), _needsMarking(needsMarking) 00140 { 00141 ListImp *imp = static_cast<ListImp *>(_impBase); 00142 imp->size = 0; 00143 imp->refCount = 1; 00144 imp->capacity = 0; 00145 imp->overflow = 0; 00146 00147 if (!_needsMarking) { 00148 imp->valueRefCount = 1; 00149 } 00150 00151 #if DUMP_STATISTICS 00152 if (++numLists > numListsHighWaterMark) 00153 numListsHighWaterMark = numLists; 00154 imp->sizeHighWaterMark = 0; 00155 #endif 00156 } 00157 00158 void List::derefValues() 00159 { 00160 ListImp *imp = static_cast<ListImp *>(_impBase); 00161 00162 int size = imp->size; 00163 00164 int inlineSize = MIN(size, inlineValuesSize); 00165 for (int i = 0; i != inlineSize; ++i) 00166 imp->values[i]->deref(); 00167 00168 int overflowSize = size - inlineSize; 00169 ValueImp **overflow = imp->overflow; 00170 for (int i = 0; i != overflowSize; ++i) 00171 overflow[i]->deref(); 00172 } 00173 00174 void List::refValues() 00175 { 00176 ListImp *imp = static_cast<ListImp *>(_impBase); 00177 00178 int size = imp->size; 00179 00180 int inlineSize = MIN(size, inlineValuesSize); 00181 for (int i = 0; i != inlineSize; ++i) 00182 imp->values[i]->ref(); 00183 00184 int overflowSize = size - inlineSize; 00185 ValueImp **overflow = imp->overflow; 00186 for (int i = 0; i != overflowSize; ++i) 00187 overflow[i]->ref(); 00188 } 00189 00190 void List::markValues() 00191 { 00192 ListImp *imp = static_cast<ListImp *>(_impBase); 00193 00194 int size = imp->size; 00195 00196 int inlineSize = MIN(size, inlineValuesSize); 00197 for (int i = 0; i != inlineSize; ++i) { 00198 if (!imp->values[i]->marked()) { 00199 imp->values[i]->mark(); 00200 } 00201 } 00202 00203 int overflowSize = size - inlineSize; 00204 ValueImp **overflow = imp->overflow; 00205 for (int i = 0; i != overflowSize; ++i) { 00206 if (!overflow[i]->marked()) { 00207 overflow[i]->mark(); 00208 } 00209 } 00210 } 00211 00212 void List::release() 00213 { 00214 ListImp *imp = static_cast<ListImp *>(_impBase); 00215 00216 #if DUMP_STATISTICS 00217 --numLists; 00218 ++numListsDestroyed; 00219 for (int i = 0; i < 17; i++) 00220 if (imp->sizeHighWaterMark > i) 00221 ++numListsBiggerThan[i]; 00222 #endif 00223 00224 delete [] imp->overflow; 00225 deallocateListImp(imp); 00226 } 00227 00228 ValueImp *List::impAt(int i) const 00229 { 00230 ListImp *imp = static_cast<ListImp *>(_impBase); 00231 if ((unsigned)i >= (unsigned)imp->size) 00232 return UndefinedImp::staticUndefined; 00233 if (i < inlineValuesSize) 00234 return imp->values[i]; 00235 return imp->overflow[i - inlineValuesSize]; 00236 } 00237 00238 void List::clear() 00239 { 00240 if (_impBase->valueRefCount > 0) { 00241 derefValues(); 00242 } 00243 _impBase->size = 0; 00244 } 00245 00246 void List::append(ValueImp *v) 00247 { 00248 ListImp *imp = static_cast<ListImp *>(_impBase); 00249 00250 int i = imp->size++; 00251 00252 #if DUMP_STATISTICS 00253 if (imp->size > listSizeHighWaterMark) 00254 listSizeHighWaterMark = imp->size; 00255 #endif 00256 00257 if (imp->valueRefCount > 0) { 00258 v->ref(); 00259 } 00260 00261 if (i < inlineValuesSize) { 00262 imp->values[i] = v; 00263 return; 00264 } 00265 00266 if (i >= imp->capacity) { 00267 int newCapacity = i * 2; 00268 ValueImp **newOverflow = new ValueImp * [newCapacity - inlineValuesSize]; 00269 ValueImp **oldOverflow = imp->overflow; 00270 int oldOverflowSize = i - inlineValuesSize; 00271 for (int j = 0; j != oldOverflowSize; j++) 00272 newOverflow[j] = oldOverflow[j]; 00273 delete [] oldOverflow; 00274 imp->overflow = newOverflow; 00275 imp->capacity = newCapacity; 00276 } 00277 00278 imp->overflow[i - inlineValuesSize] = v; 00279 } 00280 00281 List List::copy() const 00282 { 00283 List copy; 00284 00285 ListImp *imp = static_cast<ListImp *>(_impBase); 00286 00287 int size = imp->size; 00288 00289 int inlineSize = MIN(size, inlineValuesSize); 00290 for (int i = 0; i != inlineSize; ++i) 00291 copy.append(imp->values[i]); 00292 00293 ValueImp **overflow = imp->overflow; 00294 int overflowSize = size - inlineSize; 00295 for (int i = 0; i != overflowSize; ++i) 00296 copy.append(overflow[i]); 00297 00298 return copy; 00299 } 00300 00301 00302 List List::copyTail() const 00303 { 00304 List copy; 00305 00306 ListImp *imp = static_cast<ListImp *>(_impBase); 00307 00308 int size = imp->size; 00309 00310 int inlineSize = MIN(size, inlineValuesSize); 00311 for (int i = 1; i < inlineSize; ++i) 00312 copy.append(imp->values[i]); 00313 00314 ValueImp **overflow = imp->overflow; 00315 int overflowSize = size - inlineSize; 00316 for (int i = 0; i < overflowSize; ++i) 00317 copy.append(overflow[i]); 00318 00319 return copy; 00320 } 00321 00322 const List &List::empty() 00323 { 00324 static List emptyList; 00325 return emptyList; 00326 } 00327 00328 } // namespace KJS
KDE Logo
This file is part of the documentation for kjs Library Version 3.3.0.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Wed Sep 29 09:43:40 2004 by doxygen 1.3.8 written by Dimitri van Heesch, © 1997-2003