Implement support for compacting objects and arrays

This is required so arrays and objects don't continue
growing in size when being edited.

Change-Id: I75518a8edda374e44161496e50ad8576dd4f0f5c
Reviewed-by: Jamey Hicks <jamey.hicks@nokia.com>

9 files changed, 233 insertions, 40 deletions

diff --git a/src/qjson.cpp b/src/qjson.cpp
new file mode 100644
index 0000000..46e7599
--- /dev/null
+++ b/src/qjson.cpp
@@ -0,0 +1,116 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtCore module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include <qjson_p.h>
+
+using namespace QtJson;
+
+void Data::compact()
+{
+    Q_ASSERT(sizeof(Value) == sizeof(offset));
+
+    if (!compactionCounter)
+        return;
+
+    Base *base = header->root();
+    int reserve = 0;
+    if (base->is_object) {
+        Object *o = static_cast<Object *>(base);
+        for (int i = 0; i < (int)o->length; ++i)
+            reserve += o->entryAt(i)->usedStorage(o);
+    } else {
+        Array *a = static_cast<Array *>(base);
+        for (int i = 0; i < (int)a->length; ++i)
+            reserve += (*a)[i].usedStorage(a);
+    }
+
+    int size = sizeof(Base) + reserve + base->length*sizeof(offset);
+    int alloc = sizeof(Header) + size;
+    Header *h = (Header *) malloc(alloc);
+    Base *b = h->root();
+    b->size = size;
+    b->is_object = header->root()->is_object;
+    b->length = base->length;
+    b->tableOffset = reserve + sizeof(Array);
+
+    int offset = sizeof(Base);
+    if (b->is_object) {
+        Object *o = static_cast<Object *>(base);
+        Object *no = static_cast<Object *>(b);
+
+        for (int i = 0; i < (int)o->length; ++i) {
+            no->table()[i] = offset;
+
+            const Entry *e = o->entryAt(i);
+            Entry *ne = no->entryAt(i);
+            int s = e->size();
+            memcpy(ne, e, s);
+            offset += s;
+            int dataSize = e->value.usedStorage(o);
+            if (dataSize) {
+                memcpy((char *)no + offset, e->value.data(o), dataSize);
+                ne->value.val = offset;
+                offset += dataSize;
+            }
+        }
+    } else {
+        Array *a = static_cast<Array *>(base);
+        Array *na = static_cast<Array *>(b);
+
+        for (int i = 0; i < (int)a->length; ++i) {
+            const Value &v = (*a)[i];
+            Value &nv = (*na)[i];
+            nv = v;
+            int dataSize = v.usedStorage(a);
+            if (dataSize) {
+                memcpy((char *)na + offset, v.data(a), dataSize);
+                nv.val = offset;
+                offset += dataSize;
+            }
+        }
+    }
+    Q_ASSERT(offset == (int)b->tableOffset);
+
+    free(header);
+    header = h;
+    alloc = alloc;
+    compactionCounter = 0;
+}
diff --git a/src/qjson_p.h b/src/qjson_p.h
index 3dd58b2..df6c48e 100644
--- a/src/qjson_p.h
+++ b/src/qjson_p.h
@@ -367,6 +367,7 @@ struct Value
 
 
     inline char *data(const Base *b) const { return ((char *)b) + val; }
+    inline int usedStorage(Base *b) const;
 
     bool toBoolean() const;
     double toNumber(const Base *b) const;
@@ -427,13 +428,25 @@ inline Value &Array::operator [](int i)
 
 
 struct Entry {
-    uint size;
     Value value;
     ushort *keyData() const { return (ushort *)((const char *)this + sizeof(Entry) + sizeof(int)); }
     uchar *latin1KeyData() const { return (uchar *)((const char *)this + sizeof(Entry) + sizeof(ushort)); }
     // key
     // value data follows key
 
+    int size() const {
+        int s = sizeof(Entry);
+        if (value.latinKey)
+            s += sizeof(ushort) + *(ushort *) ((const char *)this + sizeof(Entry));
+        else
+            s += sizeof(uint) + *(int *) ((const char *)this + sizeof(Entry));
+        return alignedSize(s);
+    }
+
+    int usedStorage(Base *b) const {
+        return size() + value.usedStorage(b);
+    }
+
     String shallowKey() const
     {
         Q_ASSERT(!value.latinKey);
@@ -480,6 +493,36 @@ struct Header {
 };
 
 
+inline int Value::usedStorage(Base *b) const
+{
+    int s = 0;
+    switch (type) {
+    case NumberValue:
+        if (latinOrIntValue)
+            break;
+        s = sizeof(double);
+        break;
+    case StringValue: {
+        char *d = data(b);
+        if (latinOrIntValue)
+            s = sizeof(ushort) + *(ushort *)d;
+        else
+            s = sizeof(int) + sizeof(ushort)*(*(int *)d);
+        break;
+    }
+    case ArrayValue:
+    case ObjectValue:
+        s = objectOrArray(b)->size;
+        break;
+    case NullValue:
+    case BooleanValue:
+    default:
+        break;
+    }
+    return alignedSize(s);
+}
+
+
 inline bool Value::toBoolean() const
 {
     Q_ASSERT(type == BooleanValue);
@@ -544,10 +587,12 @@ inline Base *Value::objectOrArray(const Base *b) const
 
 struct Data {
     inline Data(char *raw, int a)
-        : alloc(a), needsCompaction(false), rawData(raw)
-    { ref.store(0); }
+        : alloc(a), compactionCounter(0), rawData(raw)
+    {
+        ref.store(0);
+    }
     inline Data(int reserved, ValueType valueType)
-        : needsCompaction(false), rawData(0)
+        : compactionCounter(0), rawData(0)
     {
         ref.store(0);
 
@@ -566,7 +611,7 @@ struct Data {
 
     QBasicAtomicInt ref;
     int alloc;
-    bool needsCompaction;
+    int compactionCounter;
     union {
         char *rawData;
         Header *header;
@@ -597,8 +642,12 @@ struct Data {
         Header *h = (Header *)raw;
         h->tag = QBJS_Tag;
         h->version = 1;
-        return new Data(raw, size);
+        Data *d = new Data(raw, size);
+        d->compactionCounter = compactionCounter;
+        return d;
     }
+
+    void compact();
 };
 
 }
diff --git a/src/qjsonarray.cpp b/src/qjsonarray.cpp
index 5428c30..6a5ed4a 100644
--- a/src/qjsonarray.cpp
+++ b/src/qjsonarray.cpp
@@ -46,6 +46,7 @@
 #include <qjsonvalue.h>
 
 #include <qstringlist.h>
+#include <qdebug.h>
 
 using namespace QtJson;
 
@@ -162,7 +163,9 @@ void JsonArray::removeAt(int i)
 
     detach();
     a->removeItems(i, 1);
-    d->needsCompaction = true;
+    ++d->compactionCounter;
+    if (d->compactionCounter > 32 && d->compactionCounter >= a->length/2)
+        compact();
 }
 
 JsonValue JsonArray::takeAt(int i)
@@ -255,6 +258,9 @@ void JsonArray::detach(uint reserve)
         d->ref.ref();
         return;
     }
+    if (reserve == 0 && d->ref.load() == 1)
+        return;
+
     Data *x = d->detach(a, reserve);
     x->ref.ref();
     if (!d->ref.deref())
@@ -262,3 +268,13 @@ void JsonArray::detach(uint reserve)
     d = x;
     a = static_cast<Array *>(d->header->root());
 }
+
+void JsonArray::compact() const
+{
+    if (!d || !d->compactionCounter)
+        return;
+
+    const_cast<JsonArray *>(this)->detach();
+    d->compact();
+    const_cast<JsonArray *>(this)->a = static_cast<Array *>(d->header->root());
+}
diff --git a/src/qjsonarray.h b/src/qjsonarray.h
index c92c7a3..136dcee 100644
--- a/src/qjsonarray.h
+++ b/src/qjsonarray.h
@@ -88,6 +88,7 @@ private:
     friend class JsonValue;
     friend class JsonDocument;
     JsonArray(Data *data, Array *array);
+    void compact() const;
     Data *d;
     Array *a;
 };
diff --git a/src/qjsondocument.cpp b/src/qjsondocument.cpp
index 87f5f9a..33a9806 100644
--- a/src/qjsondocument.cpp
+++ b/src/qjsondocument.cpp
@@ -57,33 +57,15 @@ JsonDocument::JsonDocument()
 }
 
 JsonDocument::JsonDocument(const JsonObject &object)
-    : d(object.d)
+    : d(0)
 {
-    if (object.d && (object.o != object.d->header->root())) {
-        JsonObject detached(object);
-        detached.detach();
-        d = detached.d;
-        d->ref.ref();
-        return;
-    }
-    if (!d)
-        d = new Data(0, ObjectValue);
-    d->ref.ref();
+    setObject(object);
 }
 
 JsonDocument::JsonDocument(const JsonArray &array)
-    : d(array.d)
+    : d(0)
 {
-    if (array.d && (array.a != array.d->header->root())) {
-        JsonArray detached(array);
-        detached.detach();
-        d = detached.d;
-        d->ref.ref();
-        return;
-    }
-    if (!d)
-        d = new Data(0, ArrayValue);
-    d->ref.ref();
+    setArray(array);
 }
 
 JsonDocument::JsonDocument(Data *data)
@@ -231,16 +213,19 @@ void JsonDocument::setObject(const JsonObject &object)
     if (d && !d->ref.deref())
         delete d;
 
-    if (object.o && (object.o != object.d->header->root())) {
+    d = object.d;
+    if (!d) {
+        d = new Data(0, ObjectValue);
+    } else if (d->compactionCounter) {
+        object.compact();
+        d = object.d;
+    } else if (object.o != d->header->root()) {
         JsonObject detached(object);
         detached.detach();
         d = detached.d;
         d->ref.ref();
         return;
     }
-    d = object.d;
-    if (!d)
-        d = new Data(0, ObjectValue);
     d->ref.ref();
 }
 
@@ -249,16 +234,20 @@ void JsonDocument::setArray(const JsonArray &array)
     if (d && !d->ref.deref())
         delete d;
 
-    if (array.d && (array.a != array.d->header->root())) {
+    d = array.d;
+
+    if (!d) {
+        d = new Data(0, ArrayValue);
+    } else if (d->compactionCounter) {
+        array.compact();
+        d = array.d;
+    } else if (array.a != d->header->root()) {
         JsonArray detached(array);
         detached.detach();
         d = detached.d;
         d->ref.ref();
         return;
     }
-    d = array.d;
-    if (!d)
-        d = new Data(0, ArrayValue);
     d->ref.ref();
 }
 
diff --git a/src/qjsonobject.cpp b/src/qjsonobject.cpp
index fe35173..5eefd1c 100644
--- a/src/qjsonobject.cpp
+++ b/src/qjsonobject.cpp
@@ -193,7 +193,6 @@ void JsonObject::insert(const QString &key, const JsonValue &value)
     int pos = o->length;
     o->reserveSpace(requiredSize, pos, 1);
     Entry *e = o->entryAt(pos);
-    e->size = requiredSize;
     e->value.type = value.t;
     e->value.latinKey = latinKey;
     e->value.latinOrIntValue = latinOrIntValue;
@@ -212,8 +211,11 @@ void JsonObject::remove(const QString &key)
     if (index < 0)
         return;
 
+    detach();
     o->removeItems(index, 1);
-    d->needsCompaction = true;
+    ++d->compactionCounter;
+    if (d->compactionCounter > 32 && d->compactionCounter >= o->length/2)
+        compact();
 }
 
 JsonValue JsonObject::take(const QString &key)
@@ -227,7 +229,10 @@ JsonValue JsonObject::take(const QString &key)
 
     Entry *e = o->entryAt(index);
     o->removeItems(index, 1);
-    d->needsCompaction = true;
+    ++d->compactionCounter;
+    if (d->compactionCounter > 32 && d->compactionCounter >= o->length/2)
+        compact();
+
     return JsonValue(d, o, e->value);
 }
 
@@ -274,6 +279,9 @@ void JsonObject::detach(uint reserve)
         d->ref.ref();
         return;
     }
+    if (reserve == 0 && d->ref.load() == 1)
+        return;
+
     Data *x = d->detach(o, reserve);
     x->ref.ref();
     if (!d->ref.deref())
@@ -281,3 +289,13 @@ void JsonObject::detach(uint reserve)
     d = x;
     o = static_cast<Object *>(d->header->root());
 }
+
+void JsonObject::compact() const
+{
+    if (!d || !d->compactionCounter)
+        return;
+
+    const_cast<JsonObject *>(this)->detach();
+    d->compact();
+    const_cast<JsonObject *>(this)->o = static_cast<Object *>(d->header->root());
+}
diff --git a/src/qjsonobject.h b/src/qjsonobject.h
index 0db5d29..ab0711e 100644
--- a/src/qjsonobject.h
+++ b/src/qjsonobject.h
@@ -87,6 +87,7 @@ private:
     friend class JsonDocument;
     friend class QJsonParser;
     JsonObject(Data *data, Object *object);
+    void compact() const;
 
     Data *d;
     Object *o;
diff --git a/src/qjsonvalue.cpp b/src/qjsonvalue.cpp
index 36cd392..3277997 100644
--- a/src/qjsonvalue.cpp
+++ b/src/qjsonvalue.cpp
@@ -127,6 +127,7 @@ JsonValue::JsonValue(const QLatin1String &s)
 JsonValue::JsonValue(const JsonArray &a)
     : t(ArrayValue), d(a.d)
 {
+    a.compact();
     array = a.a;
     if (d)
         d->ref.ref();
@@ -135,6 +136,7 @@ JsonValue::JsonValue(const JsonArray &a)
 JsonValue::JsonValue(const JsonObject &o)
     : t(ObjectValue), d(o.d)
 {
+    o.compact();
     object = o.o;
     if (d)
         d->ref.ref();
diff --git a/src/src.pro b/src/src.pro
index e921b4a..a697d12 100644
--- a/src/src.pro
+++ b/src/src.pro
@@ -16,6 +16,7 @@ HEADERS += \
     qjsonparser_p.h
 
 SOURCES += \
+    qjson.cpp \
     qjsondocument.cpp \
     qjsonobject.cpp \
     qjsonarray.cpp \