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., 51 Franklin Street, Fifth Floor,
00018  *  Boston, MA 02110-1301, 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 Home | KDE Accessibility Home | Description of Access Keys