00001
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 }