1 /****************************************************************************
3 ** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
6 ** This file is part of the QtCore module of the Qt Toolkit.
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and Digia. For licensing terms and
14 ** conditions see http://qt.digia.com/licensing. For further information
15 ** use the contact form at http://qt.digia.com/contact-us.
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 2.1 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 2.1 requirements
23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
25 ** In addition, as a special exception, Digia gives you certain additional
26 ** rights. These rights are described in the Digia Qt LGPL Exception
27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
29 ** GNU General Public License Usage
30 ** Alternatively, this file may be used under the terms of the GNU
31 ** General Public License version 3.0 as published by the Free Software
32 ** Foundation and appearing in the file LICENSE.GPL included in the
33 ** packaging of this file. Please review the following information to
34 ** ensure the GNU General Public License version 3.0 requirements will be
35 ** met: http://www.gnu.org/copyleft/gpl.html.
40 ****************************************************************************/
49 // This file is not part of the Qt API. It exists purely as an
50 // implementation detail. This header file may change from version to
51 // version without notice, or even be removed.
56 #include <qjsonobject.h>
57 #include <qjsonvalue.h>
58 #include <qjsondocument.h>
59 #include <qjsonarray.h>
69 This defines a binary data structure for Json data. The data structure is optimised for fast reading
70 and minimum allocations. The whole data structure can be mmap'ed and used directly.
72 In most cases the binary structure is not as space efficient as a utf8 encoded text representation, but
73 much faster to access.
75 The size requirements are:
78 Latin1 data: 2 bytes header + string.length()
79 Full Unicode: 4 bytes header + 2*(string.length())
81 Values: 4 bytes + size of data (size can be 0 for some data)
83 double: 8 bytes (0 if integer with less than 27bits)
86 object: size of object
87 Array: 12 bytes + 4*length + size of Value data
88 Object: 12 bytes + 8*length + size of Key Strings + size of Value data
90 For an example such as
92 { // object: 12 + 5*8 = 52
93 "firstName": "John", // key 12, value 8 = 20
94 "lastName" : "Smith", // key 12, value 8 = 20
95 "age" : 25, // key 8, value 0 = 8
96 "address" : // key 12, object below = 140
98 "streetAddress": "21 2nd Street", // key 16, value 16
99 "city" : "New York", // key 8, value 12
100 "state" : "NY", // key 8, value 4
101 "postalCode" : "10021" // key 12, value 8
102 }, // object total: 128
103 "phoneNumber": // key: 16, value array below = 172
104 [ // array: 12 + 2*4 + values below: 156
106 "type" : "home", // key 8, value 8
107 "number": "212 555-1234" // key 8, value 16
108 }, // object total: 68
110 "type" : "fax", // key 8, value 8
111 "number": "646 555-4567" // key 8, value 16
112 } // object total: 68
113 ] // array total: 156
114 } // great total: 412 bytes
116 The uncompressed text file used roughly 500 bytes, so in this case we end up using about
117 the same space as the text representation.
119 Other measurements have shown a slightly bigger binary size than a compact text
120 representation where all possible whitespace was stripped out.
122 namespace QJsonPrivate {
135 q_littleendian &operator =(T i) { val = qToLittleEndian(i); return *this; }
136 operator T() const { return qFromLittleEndian(val); }
138 bool operator ==(T i) { return qFromLittleEndian(val) == i; }
139 bool operator !=(T i) { return qFromLittleEndian(val) != i; }
140 bool operator ==(q_littleendian<T> i) { return val == i.val; }
141 bool operator !=(q_littleendian<T> i) { return val != i.val; }
142 bool operator <(T i) { return qFromLittleEndian(val) < i; }
143 bool operator >(T i) { return qFromLittleEndian(val) > i; }
144 bool operator <=(T i) { return qFromLittleEndian(val) <= i; }
145 bool operator >=(T i) { return qFromLittleEndian(val) >= i; }
146 q_littleendian &operator +=(T i) {
147 val = qToLittleEndian(qFromLittleEndian(val) + i);
152 typedef q_littleendian<short> qle_short;
153 typedef q_littleendian<unsigned short> qle_ushort;
154 typedef q_littleendian<int> qle_int;
155 typedef q_littleendian<unsigned int> qle_uint;
157 template<int pos, int width>
164 mask = ((1u << width) - 1) << pos
167 void operator =(uint t) {
168 uint i = qFromLittleEndian(val);
171 val = qToLittleEndian(i);
173 operator uint() const {
174 uint t = qFromLittleEndian(val);
179 bool operator !() const {
180 return !operator uint();
183 bool operator ==(uint t) { return uint(*this) == t; }
184 bool operator !=(uint t) { return uint(*this) != t; }
185 bool operator <(uint t) { return uint(*this) < t; }
186 bool operator >(uint t) { return uint(*this) > t; }
187 bool operator <=(uint t) { return uint(*this) <= t; }
188 bool operator >=(uint t) { return uint(*this) >= t; }
189 qle_bitfield &operator +=(uint i) {
190 *this = (uint(*this) + i);
193 qle_bitfield &operator -=(uint i) {
194 *this = (uint(*this) - i);
199 template<int pos, int width>
200 class qle_signedbitfield
206 mask = ((1u << width) - 1) << pos
209 void operator =(int t) {
210 uint i = qFromLittleEndian(val);
213 val = qToLittleEndian(i);
215 operator int() const {
216 uint i = qFromLittleEndian(val);
217 i <<= 32 - width - pos;
222 bool operator !() const {
223 return !operator int();
226 bool operator ==(int t) { return int(*this) == t; }
227 bool operator !=(int t) { return int(*this) != t; }
228 bool operator <(int t) { return int(*this) < t; }
229 bool operator >(int t) { return int(*this) > t; }
230 bool operator <=(int t) { return int(*this) <= t; }
231 bool operator >=(int t) { return int(*this) >= t; }
232 qle_signedbitfield &operator +=(int i) {
233 *this = (int(*this) + i);
236 qle_signedbitfield &operator -=(int i) {
237 *this = (int(*this) - i);
242 typedef qle_uint offset;
244 // round the size up to the next 4 byte boundary
245 inline int alignedSize(int size) { return (size + 3) & ~3; }
247 static inline bool useCompressed(const QString &s)
249 if (s.length() >= 0x8000)
251 const ushort *uc = (const ushort *)s.constData();
252 const ushort *e = uc + s.length();
261 static inline int qStringSize(const QString &string, bool compress)
263 int l = 2 + string.length();
266 return alignedSize(l);
269 // returns INT_MAX if it can't compress it into 28 bits
270 static inline int compressedNumber(double d)
272 // this relies on details of how ieee floats are represented
273 const int exponent_off = 52;
274 const quint64 fraction_mask = 0x000fffffffffffffull;
275 const quint64 exponent_mask = 0x7ff0000000000000ull;
278 memcpy (&val, &d, sizeof(double));
279 int exp = (int)((val & exponent_mask) >> exponent_off) - 1023;
280 if (exp < 0 || exp > 25)
283 quint64 non_int = val & (fraction_mask >> exp);
287 bool neg = (val >> 63);
288 val &= fraction_mask;
289 val |= ((quint64)1 << 52);
290 int res = (int)(val >> (52 - exp));
291 return neg ? -res : res;
299 String(const char *data) { d = (Data *)data; }
308 inline String &operator=(const QString &str)
310 d->length = str.length();
311 #if Q_BYTE_ORDER == Q_BIG_ENDIAN
312 const qle_ushort *uc = (const qle_ushort *)str.unicode();
313 for (int i = 0; i < str.length(); ++i)
316 memcpy(d->utf16, str.unicode(), str.length()*sizeof(ushort));
318 if (str.length() & 1)
319 d->utf16[str.length()] = 0;
323 inline bool operator ==(const QString &str) const {
324 int slen = str.length();
328 const ushort *s = (const ushort *)str.constData();
329 const qle_ushort *a = d->utf16;
331 while (l-- && *a == *b)
335 inline bool operator !=(const QString &str) const {
336 return !operator ==(str);
338 inline bool operator >=(const QString &str) const {
340 return toString() >= str;
343 inline bool operator<(const Latin1String &str) const;
344 inline bool operator>=(const Latin1String &str) const { return !operator <(str); }
345 inline bool operator ==(const Latin1String &str) const;
347 inline bool operator ==(const String &str) const {
348 if (d->length != str.d->length)
350 return !memcmp(d->utf16, str.d->utf16, d->length*sizeof(ushort));
352 inline bool operator<(const String &other) const;
353 inline bool operator >=(const String &other) const { return other < *this; }
355 inline QString toString() const {
356 #if Q_BYTE_ORDER == Q_LITTLE_ENDIAN
357 return QString((QChar *)d->utf16, d->length);
360 QString str(l, Qt::Uninitialized);
361 QChar *ch = str.data();
362 for (int i = 0; i < l; ++i)
363 ch[i] = QChar(d->utf16[i]);
373 Latin1String(const char *data) { d = (Data *)data; }
381 inline Latin1String &operator=(const QString &str)
383 d->length = str.length();
384 uchar *l = (uchar *)d->latin1;
385 const ushort *uc = (const ushort *)str.unicode();
386 for (int i = 0; i < str.length(); ++i)
388 while ((quintptr)l & 0x3)
393 inline bool operator ==(const QString &str) const {
394 return QLatin1String(d->latin1, d->length) == str;
396 inline bool operator !=(const QString &str) const {
397 return !operator ==(str);
399 inline bool operator >=(const QString &str) const {
400 return QLatin1String(d->latin1, d->length) >= str;
403 inline bool operator ==(const Latin1String &str) const {
404 return d->length == str.d->length && !strcmp(d->latin1, str.d->latin1);
406 inline bool operator >=(const Latin1String &str) const {
407 int l = qMin(d->length, str.d->length);
408 int val = strncmp(d->latin1, str.d->latin1, l);
410 val = d->length - str.d->length;
414 inline bool operator ==(const String &str) const {
415 return (str == *this);
417 inline bool operator >=(const String &str) const {
418 return (str < *this);
421 inline QString toString() const {
422 return QString::fromLatin1(d->latin1, d->length);
426 inline bool String::operator ==(const Latin1String &str) const
428 if ((int)d->length != (int)str.d->length)
430 const qle_ushort *uc = d->utf16;
431 const qle_ushort *e = uc + d->length;
432 const uchar *c = (uchar *)str.d->latin1;
443 inline bool String::operator <(const String &other) const
445 int alen = d->length;
446 int blen = other.d->length;
447 int l = qMin(alen, blen);
448 qle_ushort *a = d->utf16;
449 qle_ushort *b = other.d->utf16;
451 while (l-- && *a == *b)
454 return (alen < blen);
455 return (ushort)*a - (ushort)*b;
458 inline bool String::operator<(const Latin1String &str) const
460 const uchar *c = (uchar *) str.d->latin1;
464 const qle_ushort *uc = d->utf16;
465 const qle_ushort *e = uc + qMin((int)d->length, (int)str.d->length);
473 return (uc == e ? (int)d->length < (int)str.d->length : (ushort)*uc < *c);
477 static inline void copyString(char *dest, const QString &str, bool compress)
480 Latin1String string(dest);
490 Base is the base class for both Object and Array. Both classe work more or less the same way.
491 The class starts with a header (defined by the struct below), then followed by data (the data for
492 values in the Array case and Entry's (see below) for objects.
494 After the data a table follows (tableOffset points to it) containing Value objects for Arrays, and
495 offsets from the beginning of the object to Entry's in the case of Object.
497 Entry's in the Object's table are lexicographically sorted by key in the table(). This allows the usage
498 of a binary search over the keys in an Object.
506 qle_bitfield<0, 1> is_object;
507 qle_bitfield<1, 31> length;
510 // content follows here
512 inline bool isObject() const { return is_object; }
513 inline bool isArray() const { return !isObject(); }
515 inline offset *table() const { return (offset *) (((char *) this) + tableOffset); }
517 int reserveSpace(uint dataSize, int posInTable, uint numItems, bool replace);
518 void removeItems(int pos, int numItems);
521 class Object : public Base
524 Entry *entryAt(int i) const {
525 return reinterpret_cast<Entry *>(((char *)this) + table()[i]);
527 int indexOf(const QString &key, bool *exists);
529 bool isValid() const;
533 class Array : public Base
536 inline Value at(int i) const;
537 inline Value &operator [](int i);
539 bool isValid() const;
548 qle_bitfield<0, 3> type;
549 qle_bitfield<3, 1> latinOrIntValue;
550 qle_bitfield<4, 1> latinKey;
551 qle_bitfield<5, 27> value;
552 qle_signedbitfield<5, 27> int_value;
555 inline char *data(const Base *b) const { return ((char *)b) + value; }
556 int usedStorage(const Base *b) const;
558 bool toBoolean() const;
559 double toDouble(const Base *b) const;
560 QString toString(const Base *b) const;
561 String asString(const Base *b) const;
562 Latin1String asLatin1String(const Base *b) const;
563 Base *base(const Base *b) const;
565 bool isValid(const Base *b) const;
567 static int requiredStorage(const QJsonValue &v, bool *compressed);
568 static uint valueToStore(const QJsonValue &v, uint offset);
569 static void copyData(const QJsonValue &v, char *dest, bool compressed);
572 inline Value Array::at(int i) const
574 return *(Value *) (table() + i);
577 inline Value &Array::operator [](int i)
579 return *(Value *) (table() + i);
588 // value data follows key
591 int s = sizeof(Entry);
593 s += sizeof(ushort) + *(ushort *) ((const char *)this + sizeof(Entry));
595 s += sizeof(uint) + *(int *) ((const char *)this + sizeof(Entry));
596 return alignedSize(s);
599 int usedStorage(Base *b) const {
600 return size() + value.usedStorage(b);
603 String shallowKey() const
605 Q_ASSERT(!value.latinKey);
606 return String((const char *)this + sizeof(Entry));
608 Latin1String shallowLatin1Key() const
610 Q_ASSERT(value.latinKey);
611 return Latin1String((const char *)this + sizeof(Entry));
615 if (value.latinKey) {
616 return shallowLatin1Key().toString();
618 return shallowKey().toString();
621 bool operator ==(const QString &key) const;
622 inline bool operator !=(const QString &key) const { return !operator ==(key); }
623 inline bool operator >=(const QString &key) const;
625 bool operator ==(const Entry &other) const;
626 bool operator >=(const Entry &other) const;
629 inline bool Entry::operator >=(const QString &key) const
632 return (shallowLatin1Key() >= key);
634 return (shallowKey() >= key);
637 inline bool operator <(const QString &key, const Entry &e)
643 qle_uint tag; // 'qbjs'
644 qle_uint version; // 1
645 Base *root() { return (Base *)(this + 1); }
649 inline bool Value::toBoolean() const
651 Q_ASSERT(type == QJsonValue::Bool);
655 inline double Value::toDouble(const Base *b) const
657 Q_ASSERT(type == QJsonValue::Double);
661 quint64 i = qFromLittleEndian<quint64>((const uchar *)b + value);
663 memcpy(&d, &i, sizeof(double));
667 inline String Value::asString(const Base *b) const
669 Q_ASSERT(type == QJsonValue::String && !latinOrIntValue);
670 return String(data(b));
673 inline Latin1String Value::asLatin1String(const Base *b) const
675 Q_ASSERT(type == QJsonValue::String && latinOrIntValue);
676 return Latin1String(data(b));
679 inline QString Value::toString(const Base *b) const
682 return asLatin1String(b).toString();
684 return asString(b).toString();
687 inline Base *Value::base(const Base *b) const
689 Q_ASSERT(type == QJsonValue::Array || type == QJsonValue::Object);
690 return reinterpret_cast<Base *>(data(b));
707 uint compactionCounter : 31;
710 inline Data(char *raw, int a)
711 : alloc(a), rawData(raw), compactionCounter(0), ownsData(true)
714 inline Data(int reserved, QJsonValue::Type valueType)
715 : rawData(0), compactionCounter(0), ownsData(true)
717 Q_ASSERT(valueType == QJsonValue::Array || valueType == QJsonValue::Object);
719 alloc = sizeof(Header) + sizeof(Base) + reserved + sizeof(offset);
720 header = (Header *)malloc(alloc);
722 header->tag = QJsonDocument::BinaryFormatTag;
724 Base *b = header->root();
725 b->size = sizeof(Base);
726 b->is_object = (valueType == QJsonValue::Object);
727 b->tableOffset = sizeof(Base);
731 { if (ownsData) free(rawData); }
733 uint offsetOf(const void *ptr) const { return (uint)(((char *)ptr - rawData)); }
735 QJsonObject toObject(Object *o) const
737 return QJsonObject(const_cast<Data *>(this), o);
740 QJsonArray toArray(Array *a) const
742 return QJsonArray(const_cast<Data *>(this), a);
745 Data *clone(Base *b, int reserve = 0)
747 int size = sizeof(Header) + b->size;
748 if (b == header->root() && ref.load() == 1 && alloc >= size + reserve)
754 size = qMax(size + reserve, size *2);
756 char *raw = (char *)malloc(size);
758 memcpy(raw + sizeof(Header), b, b->size);
759 Header *h = (Header *)raw;
760 h->tag = QJsonDocument::BinaryFormatTag;
762 Data *d = new Data(raw, size);
763 d->compactionCounter = (b == header->root()) ? compactionCounter : 0;