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

1 files changed, 328 insertions, 0 deletions

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<ListImp *>(_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<ListImp *>(_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<ListImp *>(_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<ListImp *>(_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<ListImp *>(_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<ListImp *>(_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<ListImp *>(_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<ListImp *>(_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<ListImp *>(_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<ListImp *>(_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