list.cpp00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
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
00035 const int poolSize = 32;
00036 const int inlineValuesSize = 4;
00037
00038
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
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 }
|