summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/qjson.cpp64
-rw-r--r--src/qjson_p.h127
-rw-r--r--src/qjsonglobal.h1
-rw-r--r--src/qjsonobject.cpp34
-rw-r--r--src/qjsonobject.h1
-rw-r--r--src/qjsonparser.cpp39
-rw-r--r--src/qjsonparser_p.h17
-rw-r--r--tests/auto/test.bjsonbin60992 -> 60992 bytes
-rw-r--r--tests/auto/tst_qtjson.cpp41
9 files changed, 263 insertions, 61 deletions
diff --git a/src/qjson.cpp b/src/qjson.cpp
index db88b03..9b97eab 100644
--- a/src/qjson.cpp
+++ b/src/qjson.cpp
@@ -40,6 +40,7 @@
****************************************************************************/
#include <qjson_p.h>
+#include <qalgorithms.h>
namespace QtJson
{
@@ -176,15 +177,30 @@ void Base::removeItems(int pos, int numItems)
length -= numItems;
}
-
-
-int Object::indexOf(const QString &key)
+int Object::indexOf(const QString &key, bool *exists)
{
- for (int i = 0; i < (int)length; ++i) {
- Entry *e = entryAt(i);
- if (e->matchesKey(key))
- return i;
+ if (exists)
+ *exists = false;
+
+ int min = 0;
+ int n = length;
+ while (n > 0) {
+ int half = n >> 1;
+ int middle = min + half;
+ if (*entryAt(middle) >= key) {
+ n = half;
+ } else {
+ min = middle + 1;
+ n -= half + 1;
+ }
+ }
+ if (min < (int)length && *entryAt(min) == key) {
+ if (exists)
+ *exists = true;
+ return min;
}
+ if (exists)
+ return min;
return -1;
}
@@ -222,7 +238,7 @@ bool Array::isValid() const
}
-bool Entry::matchesKey(const QString &key)
+bool Entry::operator ==(const QString &key) const
{
if (value.latinKey)
return (shallowLatin1Key() == key);
@@ -230,6 +246,38 @@ bool Entry::matchesKey(const QString &key)
return (shallowKey() == key);
}
+bool Entry::operator >=(const QString &key) const
+{
+ if (value.latinKey)
+ return (shallowLatin1Key() >= key);
+ else
+ return (shallowKey() >= key);
+}
+
+bool Entry::operator ==(const Entry &other) const
+{
+ if (value.latinKey) {
+ if (other.value.latinKey)
+ return shallowLatin1Key() == other.shallowLatin1Key();
+ return shallowLatin1Key() == other.shallowKey();
+ } else if (other.value.latinKey) {
+ return shallowKey() == other.shallowLatin1Key();
+ }
+ return shallowKey() == other.shallowKey();
+}
+
+bool Entry::operator >=(const Entry &other) const
+{
+ if (value.latinKey) {
+ if (other.value.latinKey)
+ return shallowLatin1Key() >= other.shallowLatin1Key();
+ return shallowLatin1Key() >= other.shallowKey();
+ } else if (other.value.latinKey) {
+ return shallowKey() >= other.shallowLatin1Key();
+ }
+ return shallowKey() >= other.shallowKey();
+}
+
int Value::usedStorage(const Base *b) const
{
diff --git a/src/qjson_p.h b/src/qjson_p.h
index f14d5a7..f339dd0 100644
--- a/src/qjson_p.h
+++ b/src/qjson_p.h
@@ -310,22 +310,39 @@ struct String
return *this;
}
- bool operator ==(const QString &str) {
+ inline bool operator ==(const QString &str) const {
int slen = str.length();
- const ushort *s = (const ushort *)str.constData();
int l = d->length;
if (slen != l)
return false;
+ const ushort *s = (const ushort *)str.constData();
const qle_ushort *a = d->utf16;
const ushort *b = s;
while (l-- && *a == *b)
a++,b++;
return (l == -1);
}
- bool operator !=(const QString &str) {
+ inline bool operator !=(const QString &str) const {
return !operator ==(str);
}
- QString toString() const {
+ inline bool operator >=(const QString &str) const {
+ // ###
+ return toString() >= str;
+ }
+
+ inline bool operator<(const Latin1String &str) const;
+ inline bool operator>=(const Latin1String &str) const { return !operator <(str); }
+ inline bool operator ==(const Latin1String &str) const;
+
+ inline bool operator ==(const String &str) const {
+ if (d->length != str.d->length)
+ return false;
+ return !memcmp(d->utf16, str.d->utf16, d->length*sizeof(ushort));
+ }
+ inline bool operator<(const String &other) const;
+ inline bool operator >=(const String &other) const { return other < *this; }
+
+ inline QString toString() const {
#if Q_BYTE_ORDER == Q_LITTLE_ENDIAN
return QString((QChar *)d->utf16, d->length);
#else
@@ -362,27 +379,89 @@ struct Latin1String
return *this;
}
- bool operator ==(const QString &str) {
- int slen = str.length();
- const ushort *s = (const ushort *)str.constData();
- if (slen != d->length)
- return false;
- int l = d->length;
- const uchar *a = (uchar *)d->latin1;
- const ushort *b = s;
- while (l-- && *a == *b)
- a++,b++;
- return (l == -1);
+ inline bool operator ==(const QString &str) const {
+ return QLatin1String(d->latin1, d->length) == str;
}
- bool operator !=(const QString &str) {
+ inline bool operator !=(const QString &str) const {
return !operator ==(str);
}
+ inline bool operator >=(const QString &str) const {
+ return QLatin1String(d->latin1, d->length) >= str;
+ }
+
+ inline bool operator ==(const Latin1String &str) const {
+ return d->length == str.d->length && !strcmp(d->latin1, str.d->latin1);
+ }
+ inline bool operator >=(const Latin1String &str) const {
+ int l = qMin(d->length, str.d->length);
+ int val = strncmp(d->latin1, str.d->latin1, l);
+ if (!val)
+ val = d->length - str.d->length;
+ return val >= 0;
+ }
+
+ inline bool operator ==(const String &str) const {
+ return (str == *this);
+ }
+ inline bool operator >=(const String &str) const {
+ return (str < *this);
+ }
- QString toString() const {
+ inline QString toString() const {
return QString::fromLatin1(d->latin1, d->length);
}
};
+inline bool String::operator ==(const Latin1String &str) const
+{
+ if ((int)d->length != (int)str.d->length)
+ return false;
+ const qle_ushort *uc = d->utf16;
+ const qle_ushort *e = uc + d->length;
+ const uchar *c = (uchar *)str.d->latin1;
+
+ while (uc < e) {
+ if (*uc != *c)
+ return false;
+ ++uc;
+ ++c;
+ }
+ return true;
+}
+
+inline bool String::operator <(const String &other) const
+{
+ int alen = d->length;
+ int blen = other.d->length;
+ int l = qMin(alen, blen);
+ qle_ushort *a = d->utf16;
+ qle_ushort *b = other.d->utf16;
+
+ while (l-- && *a == *b)
+ a++,b++;
+ if (l==-1)
+ return (alen < blen);
+ return (ushort)*a - (ushort)*b;
+}
+
+inline bool String::operator<(const Latin1String &str) const
+{
+ const uchar *c = (uchar *) str.d->latin1;
+ if (!c || *c == 0)
+ return false;
+
+ const qle_ushort *uc = d->utf16;
+ const qle_ushort *e = uc + qMin((int)d->length, (int)str.d->length);
+
+ while (uc < e) {
+ if (*uc != *c)
+ break;
+ ++uc;
+ ++c;
+ }
+ return (uc == (d->utf16 + d->length) ? *c : (ushort)*uc < *c);
+
+}
static inline void copyString(char *dest, const QString &str, bool compress)
{
@@ -423,7 +502,7 @@ struct Object : public Base
Entry *entryAt(int i) const {
return reinterpret_cast<Entry *>(((char *)this) + table()[i]);
}
- int indexOf(const QString &key);
+ int indexOf(const QString &key, bool *exists = 0);
bool isValid() const;
};
@@ -440,8 +519,6 @@ struct Array : public Base
struct Value
{
- // unfortunately some compilers can't handle mixed types in bitfields.
- // this works around the problem
union {
uint _dummy;
qle_bitfield<0, 3> type;
@@ -516,9 +593,17 @@ struct Entry {
return shallowKey().toString();
}
- bool matchesKey(const QString &key);
+ bool operator ==(const QString &key) const;
+ inline bool operator !=(const QString &key) const { return !operator ==(key); }
+ bool operator >=(const QString &key) const;
+
+ bool operator ==(const Entry &other) const;
+ bool operator >=(const Entry &other) const;
};
+inline bool operator <(const QString &key, const Entry &e)
+{ return e >= key; }
+
struct Header {
qle_uint tag; // 'qbjs'
qle_uint version; // 1
diff --git a/src/qjsonglobal.h b/src/qjsonglobal.h
index ff7afcb..da59ac5 100644
--- a/src/qjsonglobal.h
+++ b/src/qjsonglobal.h
@@ -60,6 +60,7 @@ namespace QtJson
struct Header;
struct Array;
struct Value;
+ struct Entry;
};
class QJsonValue;
diff --git a/src/qjsonobject.cpp b/src/qjsonobject.cpp
index b93bf8a..ba8acb2 100644
--- a/src/qjsonobject.cpp
+++ b/src/qjsonobject.cpp
@@ -218,12 +218,10 @@ QJsonValue QJsonObject::value(const QString &key) const
if (!d)
return QJsonValue();
- for (uint i = 0; i < o->length; ++i) {
- Private::Entry *e = o->entryAt(i);
- if (e->matchesKey(key))
- return QJsonValue(d, o, e->value);
- }
- return QJsonValue(QJsonValue::Undefined);
+ int i = o->indexOf(key);
+ if (i < 0)
+ return QJsonValue(QJsonValue::Undefined);
+ return QJsonValue(d, o, o->entryAt(i)->value);
}
/*!
@@ -253,10 +251,12 @@ QJsonValue QJsonObject::operator [](const QString &key) const
*/
QJsonValueRef QJsonObject::operator [](const QString &key)
{
- int index = o ? o->indexOf(key) : -1;
- if (index < 0) {
- insert(key, QJsonValue());
- index = o->indexOf(key);
+ // ### somewhat inefficient, as we lookup the key twice if it doesn't yet exist
+ bool keyExists = false;
+ int index = o ? o->indexOf(key, &keyExists) : -1;
+ if (!keyExists) {
+ iterator i = insert(key, QJsonValue());
+ index = i.i;
}
return QJsonValueRef(this, index);
}
@@ -293,16 +293,12 @@ QJsonObject::iterator QJsonObject::insert(const QString &key, const QJsonValue &
if (!o->length)
o->tableOffset = sizeof(Private::Object);
-
- int pos = o->indexOf(key);
- bool replace = false;
- if (pos >= 0) {
+ bool keyExists = false;
+ int pos = o->indexOf(key, &keyExists);
+ if (keyExists)
++d->compactionCounter;
- replace = true;
- } else {
- pos = o->length;
- }
- o->reserveSpace(requiredSize, pos, 1, replace);
+
+ o->reserveSpace(requiredSize, pos, 1, keyExists);
Private::Entry *e = o->entryAt(pos);
e->value.type = value.t;
diff --git a/src/qjsonobject.h b/src/qjsonobject.h
index 9bee307..d048f15 100644
--- a/src/qjsonobject.h
+++ b/src/qjsonobject.h
@@ -132,7 +132,6 @@ public:
typedef std::bidirectional_iterator_tag iterator_category;
typedef int difference_type;
typedef QJsonValue value_type;
- //typedef const T *pointer;
typedef QJsonValue reference;
inline const_iterator() : o(0), i(0) {}
diff --git a/src/qjsonparser.cpp b/src/qjsonparser.cpp
index cd8c574..bd0b4fe 100644
--- a/src/qjsonparser.cpp
+++ b/src/qjsonparser.cpp
@@ -41,7 +41,6 @@
#include <qjsonparser_p.h>
#include <qjson_p.h>
-#include <qvarlengtharray.h>
#include <qdebug.h>
//#define PARSER_DEBUG
@@ -194,6 +193,28 @@ error:
return QJsonDocument();
}
+
+void QJsonParser::ParsedObject::insert(uint offset) {
+ const Private::Entry *newEntry = reinterpret_cast<const Private::Entry *>(parser->data + objectPosition + offset);
+ int min = 0;
+ int n = offsets.size();
+ while (n > 0) {
+ int half = n >> 1;
+ int middle = min + half;
+ if (*entryAt(middle) >= *newEntry) {
+ n = half;
+ } else {
+ min = middle + 1;
+ n -= half + 1;
+ }
+ }
+ if (min < offsets.size() && *entryAt(min) == *newEntry) {
+ offsets[min] = offset;
+ } else {
+ offsets.insert(min, offset);
+ }
+}
+
/*
object = begin-object [ member *( value-separator member ) ]
end-object
@@ -204,14 +225,14 @@ bool QJsonParser::parseObject()
int objectOffset = reserveSpace(sizeof(Private::Object));
BEGIN << "parseObject pos=" << objectOffset << current << json;
- QVarLengthArray<uint> offsets;
+ ParsedObject parsedObject(this, objectOffset);
char token = nextToken();
while (token == Quote) {
int off = current - objectOffset;
if (!parseMember(objectOffset))
return false;
- offsets.append(off);
+ parsedObject.insert(off);
token = nextToken();
if (token != ValueSeparator)
break;
@@ -222,18 +243,18 @@ bool QJsonParser::parseObject()
if (token != EndObject)
return false;
- DEBUG << "numEntries" << offsets.size();
+ DEBUG << "numEntries" << parsedObject.offsets.size();
int table = objectOffset;
// finalize the object
- if (offsets.size()) {
- int tableSize = offsets.size()*sizeof(uint);
+ if (parsedObject.offsets.size()) {
+ int tableSize = parsedObject.offsets.size()*sizeof(uint);
table = reserveSpace(tableSize);
#if Q_BYTE_ORDER == Q_LITTLE_ENDIAN
- memcpy(data + table, offsets.constData(), tableSize);
+ memcpy(data + table, parsedObject.offsets.constData(), tableSize);
#else
offset *o = (offset *)(data + table);
for (int i = 0; i < tableSize; ++i)
- o[i] = offsets[i];
+ o[i] = parsedObject.offsets[i];
#endif
}
@@ -242,7 +263,7 @@ bool QJsonParser::parseObject()
o->tableOffset = table - objectOffset;
o->size = current - objectOffset;
o->is_object = true;
- o->length = offsets.size();
+ o->length = parsedObject.offsets.size();
DEBUG << "current=" << current;
END;
diff --git a/src/qjsonparser_p.h b/src/qjsonparser_p.h
index d3700b2..fa08ed5 100644
--- a/src/qjsonparser_p.h
+++ b/src/qjsonparser_p.h
@@ -54,6 +54,7 @@
//
#include <qjsondocument.h>
+#include <qvarlengtharray.h>
namespace QtJson {
@@ -64,6 +65,22 @@ public:
QtJson::QJsonDocument parse();
+ class ParsedObject
+ {
+ public:
+ ParsedObject(QJsonParser *p, int pos) : parser(p), objectPosition(pos) {}
+ void insert(uint offset);
+
+ QJsonParser *parser;
+ int objectPosition;
+ QVarLengthArray<uint> offsets;
+
+ inline Private::Entry *entryAt(int i) const {
+ return reinterpret_cast<Private::Entry *>(parser->data + objectPosition + offsets[i]);
+ }
+ };
+
+
private:
inline bool eatSpace();
inline char nextToken();
diff --git a/tests/auto/test.bjson b/tests/auto/test.bjson
index 0ccb453..aa412ee 100644
--- a/tests/auto/test.bjson
+++ b/tests/auto/test.bjson
Binary files differ
diff --git a/tests/auto/tst_qtjson.cpp b/tests/auto/tst_qtjson.cpp
index d3c07dd..2453a82 100644
--- a/tests/auto/tst_qtjson.cpp
+++ b/tests/auto/tst_qtjson.cpp
@@ -81,6 +81,8 @@ private Q_SLOTS:
void nullArrays();
void nullObject();
+ void keySorting();
+
void undefinedValues();
void fromVariantMap();
@@ -93,6 +95,7 @@ private Q_SLOTS:
void toAndFromBinary();
void parseNumbers();
void parseStrings();
+ void parseDuplicateKeys();
void testParser();
void compactArray();
@@ -789,6 +792,21 @@ void TestQtJson::nullObject()
QCOMPARE(nullObject.contains("foo"), false);
}
+void TestQtJson::keySorting()
+{
+ const char *json = "{ \"B\": true, \"A\": false }";
+ QJsonDocument doc = QJsonDocument::fromJson(json);
+
+ QCOMPARE(doc.isObject(), true);
+
+ QJsonObject o = doc.object();
+ QCOMPARE(o.size(), 2);
+ QJsonObject::const_iterator it = o.constBegin();
+ QCOMPARE(it.key(), QLatin1String("A"));
+ ++it;
+ QCOMPARE(it.key(), QLatin1String("B"));
+}
+
void TestQtJson::undefinedValues()
{
QJsonObject object;
@@ -888,15 +906,15 @@ void TestQtJson::toJson()
QByteArray expected =
"{\n"
- " \"\\\\Key\\n\": \"Value\",\n"
- " \"null\": null,\n"
" \"Array\": [\n"
" true,\n"
" 999,\n"
" \"string\",\n"
" null,\n"
" \"\\\\\\u0007\\n\\r\\b\\tabcABC\\\"\"\n"
- " ]\n"
+ " ],\n"
+ " \"\\\\Key\\n\": \"Value\",\n"
+ " \"null\": null\n"
"}\n";
QCOMPARE(json, expected);
@@ -1192,6 +1210,23 @@ void TestQtJson::parseStrings()
}
+void TestQtJson::parseDuplicateKeys()
+{
+ const char *json = "{ \"B\": true, \"A\": null, \"B\": false }";
+
+ QJsonDocument doc = QJsonDocument::fromJson(json);
+ QCOMPARE(doc.isObject(), true);
+
+ QJsonObject o = doc.object();
+ QCOMPARE(o.size(), 2);
+ QJsonObject::const_iterator it = o.constBegin();
+ QCOMPARE(it.key(), QLatin1String("A"));
+ QCOMPARE(it.value(), QJsonValue());
+ ++it;
+ QCOMPARE(it.key(), QLatin1String("B"));
+ QCOMPARE(it.value(), QJsonValue(false));
+}
+
void TestQtJson::testParser()
{
QFile file(QLatin1String("test.json"));
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-02 13:54:32 +0000