ff57dad2f0ee62eafbcb325de9bb2f0022d13e98
[profile/ivi/qtbase.git] / src / corelib / json / qjson_p.h
1 /****************************************************************************
2 **
3 ** Copyright (C) 2012 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
5 **
6 ** This file is part of the QtCore module of the Qt Toolkit.
7 **
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.
16 **
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.
24 **
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.
28 **
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.
36 **
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41
42 #ifndef QJSON_P_H
43 #define QJSON_P_H
44
45 //
46 //  W A R N I N G
47 //  -------------
48 //
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.
52 //
53 // We mean it.
54 //
55
56 #include <qjsonobject.h>
57 #include <qjsonvalue.h>
58 #include <qjsondocument.h>
59 #include <qjsonarray.h>
60 #include <qatomic.h>
61 #include <qstring.h>
62 #include <qendian.h>
63
64 #include <limits.h>
65
66 QT_BEGIN_NAMESPACE
67
68 /*
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.
71
72   In most cases the binary structure is not as space efficient as a utf8 encoded text representation, but
73   much faster to access.
74
75   The size requirements are:
76
77   String:
78     Latin1 data: 2 bytes header + string.length()
79     Full Unicode: 4 bytes header + 2*(string.length())
80
81   Values: 4 bytes + size of data (size can be 0 for some data)
82     bool: 0 bytes
83     double: 8 bytes (0 if integer with less than 27bits)
84     string: see above
85     array: size of array
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
89
90   For an example such as
91
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
97          {                                      // object: 12 + 4*8
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
105              {                                  // object 12 + 2*8
106                "type"  : "home",                // key 8, value 8
107                "number": "212 555-1234"         // key 8, value 16
108              },                                 // object total: 68
109              {                                  // object 12 + 2*8
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
115
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.
118
119     Other measurements have shown a slightly bigger binary size than a compact text
120     representation where all possible whitespace was stripped out.
121 */
122 namespace QJsonPrivate {
123
124 class Array;
125 class Object;
126 class Value;
127 class Entry;
128
129 template<typename T>
130 class q_littleendian
131 {
132 public:
133     T val;
134
135     q_littleendian &operator =(T i) { val = qToLittleEndian(i); return *this; }
136     operator T() const { return qFromLittleEndian(val); }
137
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);
148         return *this;
149     }
150 };
151
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;
156
157 template<int pos, int width>
158 class qle_bitfield
159 {
160 public:
161     uint val;
162
163     enum {
164         mask = ((1u << width) - 1) << pos
165     };
166
167     void operator =(uint t) {
168         uint i = qFromLittleEndian(val);
169         i &= ~mask;
170         i |= t << pos;
171         val = qToLittleEndian(i);
172     }
173     operator uint() const {
174         uint t = qFromLittleEndian(val);
175         t &= mask;
176         t >>= pos;
177         return t;
178     }
179     bool operator !() const {
180         return !operator uint();
181     }
182
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);
191         return *this;
192     }
193     qle_bitfield &operator -=(uint i) {
194         *this = (uint(*this) - i);
195         return *this;
196     }
197 };
198
199 template<int pos, int width>
200 class qle_signedbitfield
201 {
202 public:
203     uint val;
204
205     enum {
206         mask = ((1u << width) - 1) << pos
207     };
208
209     void operator =(int t) {
210         uint i = qFromLittleEndian(val);
211         i &= ~mask;
212         i |= t << pos;
213         val = qToLittleEndian(i);
214     }
215     operator int() const {
216         uint i = qFromLittleEndian(val);
217         i <<= 32 - width - pos;
218         int t = (int) i;
219         t >>= pos;
220         return t;
221     }
222     bool operator !() const {
223         return !operator int();
224     }
225
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);
234         return *this;
235     }
236     qle_signedbitfield &operator -=(int i) {
237         *this = (int(*this) - i);
238         return *this;
239     }
240 };
241
242 typedef qle_uint offset;
243
244 // round the size up to the next 4 byte boundary
245 inline int alignedSize(int size) { return (size + 3) & ~3; }
246
247 static inline bool useCompressed(const QString &s)
248 {
249     if (s.length() >= 0x8000)
250         return false;
251     const ushort *uc = (const ushort *)s.constData();
252     const ushort *e = uc + s.length();
253     while (uc < e) {
254         if (*uc > 0xff)
255             return false;
256         ++uc;
257     }
258     return true;
259 }
260
261 static inline int qStringSize(const QString &string, bool compress)
262 {
263     int l = 2 + string.length();
264     if (!compress)
265         l *= 2;
266     return alignedSize(l);
267 }
268
269 // returns INT_MAX if it can't compress it into 28 bits
270 static inline int compressedNumber(double d)
271 {
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;
276
277     quint64 val;
278     memcpy (&val, &d, sizeof(double));
279     int exp = (int)((val & exponent_mask) >> exponent_off) - 1023;
280     if (exp < 0 || exp > 25)
281         return INT_MAX;
282
283     quint64 non_int = val & (fraction_mask >> exp);
284     if (non_int)
285         return INT_MAX;
286
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;
292 }
293
294 class Latin1String;
295
296 class String
297 {
298 public:
299     String(const char *data) { d = (Data *)data; }
300
301     struct Data {
302         qle_int length;
303         qle_ushort utf16[1];
304     };
305
306     Data *d;
307
308     inline String &operator=(const QString &str)
309     {
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)
314             d->utf16[i] = uc[i];
315 #else
316         memcpy(d->utf16, str.unicode(), str.length()*sizeof(ushort));
317 #endif
318         if (str.length() & 1)
319             d->utf16[str.length()] = 0;
320         return *this;
321     }
322
323     inline bool operator ==(const QString &str) const {
324         int slen = str.length();
325         int l = d->length;
326         if (slen != l)
327             return false;
328         const ushort *s = (const ushort *)str.constData();
329         const qle_ushort *a = d->utf16;
330         const ushort *b = s;
331         while (l-- && *a == *b)
332             a++,b++;
333         return (l == -1);
334     }
335     inline bool operator !=(const QString &str) const {
336         return !operator ==(str);
337     }
338     inline bool operator >=(const QString &str) const {
339         // ###
340         return toString() >= str;
341     }
342
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;
346
347     inline bool operator ==(const String &str) const {
348         if (d->length != str.d->length)
349             return false;
350         return !memcmp(d->utf16, str.d->utf16, d->length*sizeof(ushort));
351     }
352     inline bool operator<(const String &other) const;
353     inline bool operator >=(const String &other) const { return other < *this; }
354
355     inline QString toString() const {
356 #if Q_BYTE_ORDER == Q_LITTLE_ENDIAN
357         return QString((QChar *)d->utf16, d->length);
358 #else
359         int l = 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]);
364         return str;
365 #endif
366     }
367
368 };
369
370 class Latin1String
371 {
372 public:
373     Latin1String(const char *data) { d = (Data *)data; }
374
375     struct Data {
376         qle_short length;
377         char latin1[1];
378     };
379     Data *d;
380
381     inline Latin1String &operator=(const QString &str)
382     {
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)
387             *l++ = uc[i];
388         while ((quintptr)l & 0x3)
389             *l++ = 0;
390         return *this;
391     }
392
393     inline bool operator ==(const QString &str) const {
394         return QLatin1String(d->latin1, d->length) == str;
395     }
396     inline bool operator !=(const QString &str) const {
397         return !operator ==(str);
398     }
399     inline bool operator >=(const QString &str) const {
400         return QLatin1String(d->latin1, d->length) >= str;
401     }
402
403     inline bool operator ==(const Latin1String &str) const {
404         return d->length == str.d->length && !strcmp(d->latin1, str.d->latin1);
405     }
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);
409         if (!val)
410             val = d->length - str.d->length;
411         return val >= 0;
412     }
413
414     inline bool operator ==(const String &str) const {
415         return (str == *this);
416     }
417     inline bool operator >=(const String &str) const {
418         return (str < *this);
419     }
420
421     inline QString toString() const {
422         return QString::fromLatin1(d->latin1, d->length);
423     }
424 };
425
426 inline bool String::operator ==(const Latin1String &str) const
427 {
428     if ((int)d->length != (int)str.d->length)
429         return false;
430     const qle_ushort *uc = d->utf16;
431     const qle_ushort *e = uc + d->length;
432     const uchar *c = (uchar *)str.d->latin1;
433
434     while (uc < e) {
435         if (*uc != *c)
436             return false;
437         ++uc;
438         ++c;
439     }
440     return true;
441 }
442
443 inline bool String::operator <(const String &other) const
444 {
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;
450
451     while (l-- && *a == *b)
452         a++,b++;
453     if (l==-1)
454         return (alen < blen);
455     return (ushort)*a - (ushort)*b;
456 }
457
458 inline bool String::operator<(const Latin1String &str) const
459 {
460     const uchar *c = (uchar *) str.d->latin1;
461     if (!c || *c == 0)
462         return false;
463
464     const qle_ushort *uc = d->utf16;
465     const qle_ushort *e = uc + qMin((int)d->length, (int)str.d->length);
466
467     while (uc < e) {
468         if (*uc != *c)
469             break;
470         ++uc;
471         ++c;
472     }
473     return (uc == e ? (int)d->length < (int)str.d->length : (ushort)*uc < *c);
474
475 }
476
477 static inline void copyString(char *dest, const QString &str, bool compress)
478 {
479     if (compress) {
480         Latin1String string(dest);
481         string = str;
482     } else {
483         String string(dest);
484         string = str;
485     }
486 }
487
488
489 /*
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.
493
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.
496
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.
499  */
500 class Base
501 {
502 public:
503     qle_uint size;
504     union {
505         uint _dummy;
506         qle_bitfield<0, 1> is_object;
507         qle_bitfield<1, 31> length;
508     };
509     offset tableOffset;
510     // content follows here
511
512     inline bool isObject() const { return is_object; }
513     inline bool isArray() const { return !isObject(); }
514
515     inline offset *table() const { return (offset *) (((char *) this) + tableOffset); }
516
517     int reserveSpace(uint dataSize, int posInTable, uint numItems, bool replace);
518     void removeItems(int pos, int numItems);
519 };
520
521 class Object : public Base
522 {
523 public:
524     Entry *entryAt(int i) const {
525         return reinterpret_cast<Entry *>(((char *)this) + table()[i]);
526     }
527     int indexOf(const QString &key, bool *exists);
528
529     bool isValid() const;
530 };
531
532
533 class Array : public Base
534 {
535 public:
536     inline Value at(int i) const;
537     inline Value &operator [](int i);
538
539     bool isValid() const;
540 };
541
542
543 class Value
544 {
545 public:
546     union {
547         uint _dummy;
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;
553     };
554
555     inline char *data(const Base *b) const { return ((char *)b) + value; }
556     int usedStorage(const Base *b) const;
557
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;
564
565     bool isValid(const Base *b) const;
566
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);
570 };
571
572 inline Value Array::at(int i) const
573 {
574     return *(Value *) (table() + i);
575 }
576
577 inline Value &Array::operator [](int i)
578 {
579     return *(Value *) (table() + i);
580 }
581
582
583
584 class Entry {
585 public:
586     Value value;
587     // key
588     // value data follows key
589
590     int size() const {
591         int s = sizeof(Entry);
592         if (value.latinKey)
593             s += sizeof(ushort) + *(ushort *) ((const char *)this + sizeof(Entry));
594         else
595             s += sizeof(uint) + *(int *) ((const char *)this + sizeof(Entry));
596         return alignedSize(s);
597     }
598
599     int usedStorage(Base *b) const {
600         return size() + value.usedStorage(b);
601     }
602
603     String shallowKey() const
604     {
605         Q_ASSERT(!value.latinKey);
606         return String((const char *)this + sizeof(Entry));
607     }
608     Latin1String shallowLatin1Key() const
609     {
610         Q_ASSERT(value.latinKey);
611         return Latin1String((const char *)this + sizeof(Entry));
612     }
613     QString key() const
614     {
615         if (value.latinKey) {
616             return shallowLatin1Key().toString();
617         }
618         return shallowKey().toString();
619     }
620
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;
624
625     bool operator ==(const Entry &other) const;
626     bool operator >=(const Entry &other) const;
627 };
628
629 inline bool Entry::operator >=(const QString &key) const
630 {
631     if (value.latinKey)
632         return (shallowLatin1Key() >= key);
633     else
634         return (shallowKey() >= key);
635 }
636
637 inline bool operator <(const QString &key, const Entry &e)
638 { return e >= key; }
639
640
641 class Header {
642 public:
643     qle_uint tag; // 'qbjs'
644     qle_uint version; // 1
645     Base *root() { return (Base *)(this + 1); }
646 };
647
648
649 inline bool Value::toBoolean() const
650 {
651     Q_ASSERT(type == QJsonValue::Bool);
652     return value != 0;
653 }
654
655 inline double Value::toDouble(const Base *b) const
656 {
657     Q_ASSERT(type == QJsonValue::Double);
658     if (latinOrIntValue)
659         return int_value;
660
661     quint64 i = qFromLittleEndian<quint64>((const uchar *)b + value);
662     double d;
663     memcpy(&d, &i, sizeof(double));
664     return d;
665 }
666
667 inline String Value::asString(const Base *b) const
668 {
669     Q_ASSERT(type == QJsonValue::String && !latinOrIntValue);
670     return String(data(b));
671 }
672
673 inline Latin1String Value::asLatin1String(const Base *b) const
674 {
675     Q_ASSERT(type == QJsonValue::String && latinOrIntValue);
676     return Latin1String(data(b));
677 }
678
679 inline QString Value::toString(const Base *b) const
680 {
681     if (latinOrIntValue)
682         return asLatin1String(b).toString();
683     else
684         return asString(b).toString();
685 }
686
687 inline Base *Value::base(const Base *b) const
688 {
689     Q_ASSERT(type == QJsonValue::Array || type == QJsonValue::Object);
690     return reinterpret_cast<Base *>(data(b));
691 }
692
693 class Data {
694 public:
695     enum Validation {
696         Unchecked,
697         Validated,
698         Invalid
699     };
700
701     QAtomicInt ref;
702     int alloc;
703     union {
704         char *rawData;
705         Header *header;
706     };
707     uint compactionCounter : 31;
708     uint ownsData : 1;
709
710     inline Data(char *raw, int a)
711         : alloc(a), rawData(raw), compactionCounter(0), ownsData(true)
712     {
713     }
714     inline Data(int reserved, QJsonValue::Type valueType)
715         : rawData(0), compactionCounter(0), ownsData(true)
716     {
717         Q_ASSERT(valueType == QJsonValue::Array || valueType == QJsonValue::Object);
718
719         alloc = sizeof(Header) + sizeof(Base) + reserved + sizeof(offset);
720         header = (Header *)malloc(alloc);
721         Q_CHECK_PTR(header);
722         header->tag = QJsonDocument::BinaryFormatTag;
723         header->version = 1;
724         Base *b = header->root();
725         b->size = sizeof(Base);
726         b->is_object = (valueType == QJsonValue::Object);
727         b->tableOffset = sizeof(Base);
728         b->length = 0;
729     }
730     inline ~Data()
731     { if (ownsData) free(rawData); }
732
733     uint offsetOf(const void *ptr) const { return (uint)(((char *)ptr - rawData)); }
734
735     QJsonObject toObject(Object *o) const
736     {
737         return QJsonObject(const_cast<Data *>(this), o);
738     }
739
740     QJsonArray toArray(Array *a) const
741     {
742         return QJsonArray(const_cast<Data *>(this), a);
743     }
744
745     Data *clone(Base *b, int reserve = 0)
746     {
747         int size = sizeof(Header) + b->size;
748         if (b == header->root() && ref.load() == 1 && alloc >= size + reserve)
749             return this;
750
751         if (reserve) {
752             if (reserve < 128)
753                 reserve = 128;
754             size = qMax(size + reserve, size *2);
755         }
756         char *raw = (char *)malloc(size);
757         Q_CHECK_PTR(raw);
758         memcpy(raw + sizeof(Header), b, b->size);
759         Header *h = (Header *)raw;
760         h->tag = QJsonDocument::BinaryFormatTag;
761         h->version = 1;
762         Data *d = new Data(raw, size);
763         d->compactionCounter = (b == header->root()) ? compactionCounter : 0;
764         return d;
765     }
766
767     void compact();
768     bool valid() const;
769
770 private:
771     Q_DISABLE_COPY(Data)
772 };
773
774 }
775
776 QT_END_NAMESPACE
777
778 #endif // QJSON_P_H