From ce4a32fe52ef09d8f5ff1dd22c001110902b60a2 Mon Sep 17 00:00:00 2001 From: toma Date: Wed, 25 Nov 2009 17:56:58 +0000 Subject: Copy the KDE 3.5 branch to branches/trinity for new KDE 3.5 features. BUG:215923 git-svn-id: svn://anonsvn.kde.org/home/kde/branches/trinity/kdelibs@1054174 283d02a7-25f6-0310-bc7c-ecb5cbfe19da --- kjs/list.cpp | 328 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 328 insertions(+) create mode 100644 kjs/list.cpp (limited to 'kjs/list.cpp') diff --git a/kjs/list.cpp b/kjs/list.cpp new file mode 100644 index 000000000..7c674573b --- /dev/null +++ b/kjs/list.cpp @@ -0,0 +1,328 @@ +/* + * This file is part of the KDE libraries + * Copyright (C) 2003 Apple Computer, Inc. + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Library General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public License + * along with this library; see the file COPYING.LIB. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, + * Boston, MA 02110-1301, USA. + * + */ + +#include "list.h" + +#include "internal.h" + +#ifndef MIN +#define MIN(a,b) ((a) < (b) ? (a) : (b)) +#endif + +#define DUMP_STATISTICS 0 + +namespace KJS { + +// tunable parameters +const int poolSize = 32; // must be a power of 2 +const int inlineValuesSize = 4; + +// derived constants +const int poolSizeMask = poolSize - 1; + +enum ListImpState { unusedInPool = 0, usedInPool, usedOnHeap, immortal }; + +struct ListImp : ListImpBase +{ + ListImpState state; + ValueImp *values[inlineValuesSize]; + int capacity; + ValueImp **overflow; + +#if DUMP_STATISTICS + int sizeHighWaterMark; +#endif +}; + +static ListImp pool[poolSize]; +static int poolCursor; + +#if DUMP_STATISTICS + +static int numLists; +static int numListsHighWaterMark; + +static int listSizeHighWaterMark; + +static int numListsDestroyed; +static int numListsBiggerThan[17]; + +struct ListStatisticsExitLogger { ~ListStatisticsExitLogger(); }; + +static ListStatisticsExitLogger logger; + +ListStatisticsExitLogger::~ListStatisticsExitLogger() +{ + printf("\nKJS::List statistics:\n\n"); + printf("%d lists were allocated\n", numLists); + printf("%d lists was the high water mark\n", numListsHighWaterMark); + printf("largest list had %d elements\n", listSizeHighWaterMark); + if (numListsDestroyed) { + putc('\n', stdout); + for (int i = 0; i < 17; i++) { + printf("%.1f%% of the lists (%d) had more than %d element%s\n", + 100.0 * numListsBiggerThan[i] / numListsDestroyed, + numListsBiggerThan[i], + i, i == 1 ? "" : "s"); + } + putc('\n', stdout); + } +} + +#endif + +static inline ListImp *allocateListImp() +{ + // Find a free one in the pool. + int c = poolCursor; + int i = c; + do { + ListImp *imp = &pool[i]; + ListImpState s = imp->state; + i = (i + 1) & poolSizeMask; + if (s == unusedInPool) { + poolCursor = i; + imp->state = usedInPool; + return imp; + } + } while (i != c); + + ListImp *imp = new ListImp; + imp->state = usedOnHeap; + return imp; +} + +static inline void deallocateListImp(ListImp *imp) +{ + if (imp->state == usedInPool) + imp->state = unusedInPool; + else + delete imp; +} + +List::List() : _impBase(allocateListImp()), _needsMarking(false) +{ + ListImp *imp = static_cast(_impBase); + imp->size = 0; + imp->refCount = 1; + imp->capacity = 0; + imp->overflow = 0; + + if (!_needsMarking) { + imp->valueRefCount = 1; + } +#if DUMP_STATISTICS + if (++numLists > numListsHighWaterMark) + numListsHighWaterMark = numLists; + imp->sizeHighWaterMark = 0; +#endif +} + +List::List(bool needsMarking) : _impBase(allocateListImp()), _needsMarking(needsMarking) +{ + ListImp *imp = static_cast(_impBase); + imp->size = 0; + imp->refCount = 1; + imp->capacity = 0; + imp->overflow = 0; + + if (!_needsMarking) { + imp->valueRefCount = 1; + } + +#if DUMP_STATISTICS + if (++numLists > numListsHighWaterMark) + numListsHighWaterMark = numLists; + imp->sizeHighWaterMark = 0; +#endif +} + +void List::derefValues() +{ + ListImp *imp = static_cast(_impBase); + + int size = imp->size; + + int inlineSize = MIN(size, inlineValuesSize); + for (int i = 0; i != inlineSize; ++i) + imp->values[i]->deref(); + + int overflowSize = size - inlineSize; + ValueImp **overflow = imp->overflow; + for (int i = 0; i != overflowSize; ++i) + overflow[i]->deref(); +} + +void List::refValues() +{ + ListImp *imp = static_cast(_impBase); + + int size = imp->size; + + int inlineSize = MIN(size, inlineValuesSize); + for (int i = 0; i != inlineSize; ++i) + imp->values[i]->ref(); + + int overflowSize = size - inlineSize; + ValueImp **overflow = imp->overflow; + for (int i = 0; i != overflowSize; ++i) + overflow[i]->ref(); +} + +void List::markValues() +{ + ListImp *imp = static_cast(_impBase); + + int size = imp->size; + + int inlineSize = MIN(size, inlineValuesSize); + for (int i = 0; i != inlineSize; ++i) { + if (!imp->values[i]->marked()) { + imp->values[i]->mark(); + } + } + + int overflowSize = size - inlineSize; + ValueImp **overflow = imp->overflow; + for (int i = 0; i != overflowSize; ++i) { + if (!overflow[i]->marked()) { + overflow[i]->mark(); + } + } +} + +void List::release() +{ + ListImp *imp = static_cast(_impBase); + +#if DUMP_STATISTICS + --numLists; + ++numListsDestroyed; + for (int i = 0; i < 17; i++) + if (imp->sizeHighWaterMark > i) + ++numListsBiggerThan[i]; +#endif + + delete [] imp->overflow; + deallocateListImp(imp); +} + +ValueImp *List::impAt(int i) const +{ + ListImp *imp = static_cast(_impBase); + if ((unsigned)i >= (unsigned)imp->size) + return UndefinedImp::staticUndefined; + if (i < inlineValuesSize) + return imp->values[i]; + return imp->overflow[i - inlineValuesSize]; +} + +void List::clear() +{ + if (_impBase->valueRefCount > 0) { + derefValues(); + } + _impBase->size = 0; +} + +void List::append(ValueImp *v) +{ + ListImp *imp = static_cast(_impBase); + + int i = imp->size++; + +#if DUMP_STATISTICS + if (imp->size > listSizeHighWaterMark) + listSizeHighWaterMark = imp->size; +#endif + + if (imp->valueRefCount > 0) { + v->ref(); + } + + if (i < inlineValuesSize) { + imp->values[i] = v; + return; + } + + if (i >= imp->capacity) { + int newCapacity = i * 2; + ValueImp **newOverflow = new ValueImp * [newCapacity - inlineValuesSize]; + ValueImp **oldOverflow = imp->overflow; + int oldOverflowSize = i - inlineValuesSize; + for (int j = 0; j != oldOverflowSize; j++) + newOverflow[j] = oldOverflow[j]; + delete [] oldOverflow; + imp->overflow = newOverflow; + imp->capacity = newCapacity; + } + + imp->overflow[i - inlineValuesSize] = v; +} + +List List::copy() const +{ + List copy; + + ListImp *imp = static_cast(_impBase); + + int size = imp->size; + + int inlineSize = MIN(size, inlineValuesSize); + for (int i = 0; i != inlineSize; ++i) + copy.append(imp->values[i]); + + ValueImp **overflow = imp->overflow; + int overflowSize = size - inlineSize; + for (int i = 0; i != overflowSize; ++i) + copy.append(overflow[i]); + + return copy; +} + + +List List::copyTail() const +{ + List copy; + + ListImp *imp = static_cast(_impBase); + + int size = imp->size; + + int inlineSize = MIN(size, inlineValuesSize); + for (int i = 1; i < inlineSize; ++i) + copy.append(imp->values[i]); + + ValueImp **overflow = imp->overflow; + int overflowSize = size - inlineSize; + for (int i = 0; i < overflowSize; ++i) + copy.append(overflow[i]); + + return copy; +} + +const List &List::empty() +{ + static List emptyList; + return emptyList; +} + +} // namespace KJS -- cgit v1.2.1