Coverage Report

Created: 2017-02-05 08:41

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/JSON/include/json/value.h
Line
Count
Source (jump to first uncovered line)
1
#ifndef CPPTL_JSON_H_INCLUDED
2
# define CPPTL_JSON_H_INCLUDED
3
4
# include "forwards.h"
5
# include <string>
6
# include <vector>
7
8
# ifndef JSON_USE_CPPTL_SMALLMAP
9
#  include <map>
10
# else
11
#  include <cpptl/smallmap.h>
12
# endif
13
# ifdef JSON_USE_CPPTL
14
#  include <cpptl/forwards.h>
15
# endif
16
17
/** \brief JSON (JavaScript Object Notation).
18
 */
19
namespace Json {
20
21
   /** \brief Type of the value held by a Value object.
22
    */
23
   enum ValueType
24
   {
25
      nullValue = 0, ///< 'null' value
26
      intValue,      ///< signed integer value
27
      uintValue,     ///< unsigned integer value
28
      realValue,     ///< double value
29
      stringValue,   ///< UTF-8 string value
30
      booleanValue,  ///< bool value
31
      arrayValue,    ///< array value (ordered list)
32
      objectValue    ///< object value (collection of name/value pairs).
33
   };
34
35
   enum CommentPlacement
36
   {
37
      commentBefore = 0,        ///< a comment placed on the line before a value
38
      commentAfterOnSameLine,   ///< a comment just after a value on the same line
39
      commentAfter,             ///< a comment on the line after a value (only make sense for root value)
40
      numberOfCommentPlacement
41
   };
42
43
//# ifdef JSON_USE_CPPTL
44
//   typedef CppTL::AnyEnumerator<const char *> EnumMemberNames;
45
//   typedef CppTL::AnyEnumerator<const Value &> EnumValues;
46
//# endif
47
48
   /** \brief Lightweight wrapper to tag static string.
49
    *
50
    * Value constructor and objectValue member assignement takes advantage of the
51
    * StaticString and avoid the cost of string duplication when storing the
52
    * string or the member name.
53
    *
54
    * Example of usage:
55
    * \code
56
    * Json::Value aValue( StaticString("some text") );
57
    * Json::Value object;
58
    * static const StaticString code("code");
59
    * object[code] = 1234;
60
    * \endcode
61
    */
62
   class JSON_API StaticString
63
   {
64
   public:
65
      explicit StaticString( const char *czstring )
66
         : str_( czstring )
67
0
      {
68
0
      }
69
70
      operator const char *() const
71
0
      {
72
0
         return str_;
73
0
      }
74
75
      const char *c_str() const
76
0
      {
77
0
         return str_;
78
0
      }
79
80
   private:
81
      const char *str_;
82
   };
83
84
   /** \brief Represents a <a HREF="http://www.json.org">JSON</a> value.
85
    *
86
    * This class is a discriminated union wrapper that can represents a:
87
    * - signed integer [range: Value::minInt - Value::maxInt]
88
    * - unsigned integer (range: 0 - Value::maxUInt)
89
    * - double
90
    * - UTF-8 string
91
    * - boolean
92
    * - 'null'
93
    * - an ordered list of Value
94
    * - collection of name/value pairs (javascript object)
95
    *
96
    * The type of the held value is represented by a #ValueType and 
97
    * can be obtained using type().
98
    *
99
    * values of an #objectValue or #arrayValue can be accessed using operator[]() methods. 
100
    * Non const methods will automatically create the a #nullValue element 
101
    * if it does not exist. 
102
    * The sequence of an #arrayValue will be automatically resize and initialized 
103
    * with #nullValue. resize() can be used to enlarge or truncate an #arrayValue.
104
    *
105
    * The get() methods can be used to obtanis default value in the case the required element
106
    * does not exist.
107
    *
108
    * It is possible to iterate over the list of a #objectValue values using 
109
    * the getMemberNames() method.
110
    */
111
   class JSON_API Value 
112
   {
113
      friend class ValueIteratorBase;
114
# ifdef JSON_VALUE_USE_INTERNAL_MAP
115
      friend class ValueInternalLink;
116
      friend class ValueInternalMap;
117
# endif
118
   public:
119
      typedef std::vector<std::string> Members;
120
      typedef ValueIterator iterator;
121
      typedef ValueConstIterator const_iterator;
122
      typedef Json::UInt UInt;
123
      typedef Json::Int Int;
124
      typedef UInt ArrayIndex;
125
126
      static const Value null;
127
      static const Int minInt;
128
      static const Int maxInt;
129
      static const UInt maxUInt;
130
131
   private:
132
#ifndef JSONCPP_DOC_EXCLUDE_IMPLEMENTATION
133
# ifndef JSON_VALUE_USE_INTERNAL_MAP
134
      class CZString 
135
      {
136
      public:
137
         enum DuplicationPolicy 
138
         {
139
            noDuplication = 0,
140
            duplicate,
141
            duplicateOnCopy
142
         };
143
         CZString( int index );
144
         CZString( const char *cstr, DuplicationPolicy allocate );
145
         CZString( const CZString &other );
146
         ~CZString();
147
         CZString &operator =( const CZString &other );
148
         bool operator<( const CZString &other ) const;
149
         bool operator==( const CZString &other ) const;
150
         int index() const;
151
         const char *c_str() const;
152
         bool isStaticString() const;
153
      private:
154
         void swap( CZString &other );
155
         const char *cstr_;
156
         int index_;
157
      };
158
159
   public:
160
#  ifndef JSON_USE_CPPTL_SMALLMAP
161
      typedef std::map<CZString, Value> ObjectValues;
162
#  else
163
      typedef CppTL::SmallMap<CZString, Value> ObjectValues;
164
#  endif // ifndef JSON_USE_CPPTL_SMALLMAP
165
# endif // ifndef JSON_VALUE_USE_INTERNAL_MAP
166
#endif // ifndef JSONCPP_DOC_EXCLUDE_IMPLEMENTATION
167
168
   public:
169
      /** \brief Create a default Value of the given type.
170
171
        This is a very useful constructor.
172
        To create an empty array, pass arrayValue.
173
        To create an empty object, pass objectValue.
174
        Another Value can then be set to this one by assignment.
175
  This is useful since clear() and resize() will not alter types.
176
177
        Examples:
178
  \code
179
  Json::Value null_value; // null
180
  Json::Value arr_value(Json::arrayValue); // []
181
  Json::Value obj_value(Json::objectValue); // {}
182
  \endcode
183
      */
184
      Value( ValueType type = nullValue );
185
      Value( Int value );
186
      Value( UInt value );
187
      Value( double value );
188
      Value( const char *value );
189
      Value( const char *beginValue, const char *endValue );
190
      /** \brief Constructs a value from a static string.
191
192
       * Like other value string constructor but do not duplicate the string for
193
       * internal storage. The given string must remain alive after the call to this
194
       * constructor.
195
       * Example of usage:
196
       * \code
197
       * Json::Value aValue( StaticString("some text") );
198
       * \endcode
199
       */
200
      Value( const StaticString &value );
201
      Value( const std::string &value );
202
# ifdef JSON_USE_CPPTL
203
      Value( const CppTL::ConstString &value );
204
# endif
205
      Value( bool value );
206
      Value( const Value &other );
207
      ~Value();
208
209
      Value &operator=( const Value &other );
210
      /// Swap values.
211
      /// \note Currently, comments are intentionally not swapped, for
212
      /// both logic and efficiency.
213
      void swap( Value &other );
214
215
      ValueType type() const;
216
217
      bool operator <( const Value &other ) const;
218
      bool operator <=( const Value &other ) const;
219
      bool operator >=( const Value &other ) const;
220
      bool operator >( const Value &other ) const;
221
222
      bool operator ==( const Value &other ) const;
223
      bool operator !=( const Value &other ) const;
224
225
      int compare( const Value &other );
226
227
      const char *asCString() const;
228
      std::string asString() const;
229
# ifdef JSON_USE_CPPTL
230
      CppTL::ConstString asConstString() const;
231
# endif
232
      Int asInt() const;
233
      UInt asUInt() const;
234
      double asDouble() const;
235
      bool asBool() const;
236
237
      bool isNull() const;
238
      bool isBool() const;
239
      bool isInt() const;
240
      bool isUInt() const;
241
      bool isIntegral() const;
242
      bool isDouble() const;
243
      bool isNumeric() const;
244
      bool isString() const;
245
      bool isArray() const;
246
      bool isObject() const;
247
248
      bool isConvertibleTo( ValueType other ) const;
249
250
      /// Number of values in array or object
251
      UInt size() const;
252
253
      /// \brief Return true if empty array, empty object, or null;
254
      /// otherwise, false.
255
      bool empty() const;
256
257
      /// Return isNull()
258
      bool operator!() const;
259
260
      /// Remove all object members and array elements.
261
      /// \pre type() is arrayValue, objectValue, or nullValue
262
      /// \post type() is unchanged
263
      void clear();
264
265
      /// Resize the array to size elements. 
266
      /// New elements are initialized to null.
267
      /// May only be called on nullValue or arrayValue.
268
      /// \pre type() is arrayValue or nullValue
269
      /// \post type() is arrayValue
270
      void resize( UInt size );
271
272
      /// Access an array element (zero based index ).
273
      /// If the array contains less than index element, then null value are inserted
274
      /// in the array so that its size is index+1.
275
      /// (You may need to say 'value[0u]' to get your compiler to distinguish
276
      ///  this from the operator[] which takes a string.)
277
      Value &operator[]( UInt index );
278
      /// Access an array element (zero based index )
279
      /// (You may need to say 'value[0u]' to get your compiler to distinguish
280
      ///  this from the operator[] which takes a string.)
281
      const Value &operator[]( UInt index ) const;
282
      /// If the array contains at least index+1 elements, returns the element value, 
283
      /// otherwise returns defaultValue.
284
      Value get( UInt index, 
285
                 const Value &defaultValue ) const;
286
      /// Return true if index < size().
287
      bool isValidIndex( UInt index ) const;
288
      /// \brief Append value to array at the end.
289
      ///
290
      /// Equivalent to jsonvalue[jsonvalue.size()] = value;
291
      Value &append( const Value &value );
292
293
      /// Access an object value by name, create a null member if it does not exist.
294
      Value &operator[]( const char *key );
295
      /// Access an object value by name, returns null if there is no member with that name.
296
      const Value &operator[]( const char *key ) const;
297
      /// Access an object value by name, create a null member if it does not exist.
298
      Value &operator[]( const std::string &key );
299
      /// Access an object value by name, returns null if there is no member with that name.
300
      const Value &operator[]( const std::string &key ) const;
301
      /** \brief Access an object value by name, create a null member if it does not exist.
302
303
       * If the object as no entry for that name, then the member name used to store
304
       * the new entry is not duplicated.
305
       * Example of use:
306
       * \code
307
       * Json::Value object;
308
       * static const StaticString code("code");
309
       * object[code] = 1234;
310
       * \endcode
311
       */
312
      Value &operator[]( const StaticString &key );
313
# ifdef JSON_USE_CPPTL
314
      /// Access an object value by name, create a null member if it does not exist.
315
      Value &operator[]( const CppTL::ConstString &key );
316
      /// Access an object value by name, returns null if there is no member with that name.
317
      const Value &operator[]( const CppTL::ConstString &key ) const;
318
# endif
319
      /// Return the member named key if it exist, defaultValue otherwise.
320
      Value get( const char *key, 
321
                 const Value &defaultValue ) const;
322
      /// Return the member named key if it exist, defaultValue otherwise.
323
      Value get( const std::string &key,
324
                 const Value &defaultValue ) const;
325
# ifdef JSON_USE_CPPTL
326
      /// Return the member named key if it exist, defaultValue otherwise.
327
      Value get( const CppTL::ConstString &key,
328
                 const Value &defaultValue ) const;
329
# endif
330
      /// \brief Remove and return the named member.  
331
      ///
332
      /// Do nothing if it did not exist.
333
      /// \return the removed Value, or null.
334
      /// \pre type() is objectValue or nullValue
335
      /// \post type() is unchanged
336
      Value removeMember( const char* key );
337
      /// Same as removeMember(const char*)
338
      Value removeMember( const std::string &key );
339
340
      /// Return true if the object has a member named key.
341
      bool isMember( const char *key ) const;
342
      /// Return true if the object has a member named key.
343
      bool isMember( const std::string &key ) const;
344
# ifdef JSON_USE_CPPTL
345
      /// Return true if the object has a member named key.
346
      bool isMember( const CppTL::ConstString &key ) const;
347
# endif
348
349
      /// \brief Return a list of the member names.
350
      ///
351
      /// If null, return an empty list.
352
      /// \pre type() is objectValue or nullValue
353
      /// \post if type() was nullValue, it remains nullValue
354
      Members getMemberNames() const;
355
356
//# ifdef JSON_USE_CPPTL
357
//      EnumMemberNames enumMemberNames() const;
358
//      EnumValues enumValues() const;
359
//# endif
360
361
      /// Comments must be //... or /* ... */
362
      void setComment( const char *comment,
363
                       CommentPlacement placement );
364
      /// Comments must be //... or /* ... */
365
      void setComment( const std::string &comment,
366
                       CommentPlacement placement );
367
      bool hasComment( CommentPlacement placement ) const;
368
      /// Include delimiters and embedded newlines.
369
      std::string getComment( CommentPlacement placement ) const;
370
371
      std::string toStyledString() const;
372
373
      const_iterator begin() const;
374
      const_iterator end() const;
375
376
      iterator begin();
377
      iterator end();
378
379
   private:
380
      Value &resolveReference( const char *key, 
381
                               bool isStatic );
382
383
# ifdef JSON_VALUE_USE_INTERNAL_MAP
384
      inline bool isItemAvailable() const
385
      {
386
         return itemIsUsed_ == 0;
387
      }
388
389
      inline void setItemUsed( bool isUsed = true )
390
      {
391
         itemIsUsed_ = isUsed ? 1 : 0;
392
      }
393
394
      inline bool isMemberNameStatic() const
395
      {
396
         return memberNameIsStatic_ == 0;
397
      }
398
399
      inline void setMemberNameIsStatic( bool isStatic )
400
      {
401
         memberNameIsStatic_ = isStatic ? 1 : 0;
402
      }
403
# endif // # ifdef JSON_VALUE_USE_INTERNAL_MAP
404
405
   private:
406
      struct CommentInfo
407
      {
408
         CommentInfo();
409
         ~CommentInfo();
410
411
         void setComment( const char *text );
412
413
         char *comment_;
414
      };
415
416
      //struct MemberNamesTransform
417
      //{
418
      //   typedef const char *result_type;
419
      //   const char *operator()( const CZString &name ) const
420
      //   {
421
      //      return name.c_str();
422
      //   }
423
      //};
424
425
      union ValueHolder
426
      {
427
         Int int_;
428
         UInt uint_;
429
         double real_;
430
         bool bool_;
431
         char *string_;
432
# ifdef JSON_VALUE_USE_INTERNAL_MAP
433
         ValueInternalArray *array_;
434
         ValueInternalMap *map_;
435
#else
436
         ObjectValues *map_;
437
# endif
438
      } value_;
439
      ValueType type_ : 8;
440
      int allocated_ : 1;     // Notes: if declared as bool, bitfield is useless.
441
# ifdef JSON_VALUE_USE_INTERNAL_MAP
442
      unsigned int itemIsUsed_ : 1;      // used by the ValueInternalMap container.
443
      int memberNameIsStatic_ : 1;       // used by the ValueInternalMap container.
444
# endif
445
      CommentInfo *comments_;
446
   };
447
448
449
   /** \brief Experimental and untested: represents an element of the "path" to access a node.
450
    */
451
   class PathArgument
452
   {
453
   public:
454
      friend class Path;
455
456
      PathArgument();
457
      PathArgument( UInt index );
458
      PathArgument( const char *key );
459
      PathArgument( const std::string &key );
460
461
   private:
462
      enum Kind
463
      {
464
         kindNone = 0,
465
         kindIndex,
466
         kindKey
467
      };
468
      std::string key_;
469
      UInt index_;
470
      Kind kind_;
471
   };
472
473
   /** \brief Experimental and untested: represents a "path" to access a node.
474
    *
475
    * Syntax:
476
    * - "." => root node
477
    * - ".[n]" => elements at index 'n' of root node (an array value)
478
    * - ".name" => member named 'name' of root node (an object value)
479
    * - ".name1.name2.name3"
480
    * - ".[0][1][2].name1[3]"
481
    * - ".%" => member name is provided as parameter
482
    * - ".[%]" => index is provied as parameter
483
    */
484
   class Path
485
   {
486
   public:
487
      Path( const std::string &path,
488
            const PathArgument &a1 = PathArgument(),
489
            const PathArgument &a2 = PathArgument(),
490
            const PathArgument &a3 = PathArgument(),
491
            const PathArgument &a4 = PathArgument(),
492
            const PathArgument &a5 = PathArgument() );
493
494
      const Value &resolve( const Value &root ) const;
495
      Value resolve( const Value &root, 
496
                     const Value &defaultValue ) const;
497
      /// Creates the "path" to access the specified node and returns a reference on the node.
498
      Value &make( Value &root ) const;
499
500
   private:
501
      typedef std::vector<const PathArgument *> InArgs;
502
      typedef std::vector<PathArgument> Args;
503
504
      void makePath( const std::string &path,
505
                     const InArgs &in );
506
      void addPathInArg( const std::string &path, 
507
                         const InArgs &in, 
508
                         InArgs::const_iterator &itInArg, 
509
                         PathArgument::Kind kind );
510
      void invalidPath( const std::string &path, 
511
                        int location );
512
513
      Args args_;
514
   };
515
516
   /** \brief Experimental do not use: Allocator to customize member name and string value memory management done by Value.
517
    *
518
    * - makeMemberName() and releaseMemberName() are called to respectively duplicate and
519
    *   free an Json::objectValue member name.
520
    * - duplicateStringValue() and releaseStringValue() are called similarly to
521
    *   duplicate and free a Json::stringValue value.
522
    */
523
   class ValueAllocator
524
   {
525
   public:
526
      enum { unknown = (unsigned)-1 };
527
528
      virtual ~ValueAllocator();
529
530
      virtual char *makeMemberName( const char *memberName ) = 0;
531
      virtual void releaseMemberName( char *memberName ) = 0;
532
      virtual char *duplicateStringValue( const char *value, 
533
                                          unsigned int length = unknown ) = 0;
534
      virtual void releaseStringValue( char *value ) = 0;
535
   };
536
537
#ifdef JSON_VALUE_USE_INTERNAL_MAP
538
   /** \brief Allocator to customize Value internal map.
539
    * Below is an example of a simple implementation (default implementation actually
540
    * use memory pool for speed).
541
    * \code
542
      class DefaultValueMapAllocator : public ValueMapAllocator
543
      {
544
      public: // overridden from ValueMapAllocator
545
         virtual ValueInternalMap *newMap()
546
         {
547
            return new ValueInternalMap();
548
         }
549
550
         virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
551
         {
552
            return new ValueInternalMap( other );
553
         }
554
555
         virtual void destructMap( ValueInternalMap *map )
556
         {
557
            delete map;
558
         }
559
560
         virtual ValueInternalLink *allocateMapBuckets( unsigned int size )
561
         {
562
            return new ValueInternalLink[size];
563
         }
564
565
         virtual void releaseMapBuckets( ValueInternalLink *links )
566
         {
567
            delete [] links;
568
         }
569
570
         virtual ValueInternalLink *allocateMapLink()
571
         {
572
            return new ValueInternalLink();
573
         }
574
575
         virtual void releaseMapLink( ValueInternalLink *link )
576
         {
577
            delete link;
578
         }
579
      };
580
    * \endcode
581
    */ 
582
   class JSON_API ValueMapAllocator
583
   {
584
   public:
585
      virtual ~ValueMapAllocator();
586
      virtual ValueInternalMap *newMap() = 0;
587
      virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other ) = 0;
588
      virtual void destructMap( ValueInternalMap *map ) = 0;
589
      virtual ValueInternalLink *allocateMapBuckets( unsigned int size ) = 0;
590
      virtual void releaseMapBuckets( ValueInternalLink *links ) = 0;
591
      virtual ValueInternalLink *allocateMapLink() = 0;
592
      virtual void releaseMapLink( ValueInternalLink *link ) = 0;
593
   };
594
595
   /** \brief ValueInternalMap hash-map bucket chain link (for internal use only).
596
    * \internal previous_ & next_ allows for bidirectional traversal.
597
    */
598
   class JSON_API ValueInternalLink
599
   {
600
   public:
601
      enum { itemPerLink = 6 };  // sizeof(ValueInternalLink) = 128 on 32 bits architecture.
602
      enum InternalFlags { 
603
         flagAvailable = 0,
604
         flagUsed = 1
605
      };
606
607
      ValueInternalLink();
608
609
      ~ValueInternalLink();
610
611
      Value items_[itemPerLink];
612
      char *keys_[itemPerLink];
613
      ValueInternalLink *previous_;
614
      ValueInternalLink *next_;
615
   };
616
617
618
   /** \brief A linked page based hash-table implementation used internally by Value.
619
    * \internal ValueInternalMap is a tradional bucket based hash-table, with a linked
620
    * list in each bucket to handle collision. There is an additional twist in that
621
    * each node of the collision linked list is a page containing a fixed amount of
622
    * value. This provides a better compromise between memory usage and speed.
623
    * 
624
    * Each bucket is made up of a chained list of ValueInternalLink. The last
625
    * link of a given bucket can be found in the 'previous_' field of the following bucket.
626
    * The last link of the last bucket is stored in tailLink_ as it has no following bucket.
627
    * Only the last link of a bucket may contains 'available' item. The last link always
628
    * contains at least one element unless is it the bucket one very first link.
629
    */
630
   class JSON_API ValueInternalMap
631
   {
632
      friend class ValueIteratorBase;
633
      friend class Value;
634
   public:
635
      typedef unsigned int HashKey;
636
      typedef unsigned int BucketIndex;
637
638
# ifndef JSONCPP_DOC_EXCLUDE_IMPLEMENTATION
639
      struct IteratorState
640
      {
641
         IteratorState() 
642
            : map_(0)
643
            , link_(0)
644
            , itemIndex_(0)
645
            , bucketIndex_(0) 
646
         {
647
         }
648
         ValueInternalMap *map_;
649
         ValueInternalLink *link_;
650
         BucketIndex itemIndex_;
651
         BucketIndex bucketIndex_;
652
      };
653
# endif // ifndef JSONCPP_DOC_EXCLUDE_IMPLEMENTATION
654
655
      ValueInternalMap();
656
      ValueInternalMap( const ValueInternalMap &other );
657
      ValueInternalMap &operator =( const ValueInternalMap &other );
658
      ~ValueInternalMap();
659
660
      void swap( ValueInternalMap &other );
661
662
      BucketIndex size() const;
663
664
      void clear();
665
666
      bool reserveDelta( BucketIndex growth );
667
668
      bool reserve( BucketIndex newItemCount );
669
670
      const Value *find( const char *key ) const;
671
672
      Value *find( const char *key );
673
674
      Value &resolveReference( const char *key, 
675
                               bool isStatic );
676
677
      void remove( const char *key );
678
679
      void doActualRemove( ValueInternalLink *link, 
680
                           BucketIndex index,
681
                           BucketIndex bucketIndex );
682
683
      ValueInternalLink *&getLastLinkInBucket( BucketIndex bucketIndex );
684
685
      Value &setNewItem( const char *key, 
686
                         bool isStatic, 
687
                         ValueInternalLink *link, 
688
                         BucketIndex index );
689
690
      Value &unsafeAdd( const char *key, 
691
                        bool isStatic, 
692
                        HashKey hashedKey );
693
694
      HashKey hash( const char *key ) const;
695
696
      int compare( const ValueInternalMap &other ) const;
697
698
   private:
699
      void makeBeginIterator( IteratorState &it ) const;
700
      void makeEndIterator( IteratorState &it ) const;
701
      static bool equals( const IteratorState &x, const IteratorState &other );
702
      static void increment( IteratorState &iterator );
703
      static void incrementBucket( IteratorState &iterator );
704
      static void decrement( IteratorState &iterator );
705
      static const char *key( const IteratorState &iterator );
706
      static const char *key( const IteratorState &iterator, bool &isStatic );
707
      static Value &value( const IteratorState &iterator );
708
      static int distance( const IteratorState &x, const IteratorState &y );
709
710
   private:
711
      ValueInternalLink *buckets_;
712
      ValueInternalLink *tailLink_;
713
      BucketIndex bucketsSize_;
714
      BucketIndex itemCount_;
715
   };
716
717
   /** \brief A simplified deque implementation used internally by Value.
718
   * \internal
719
   * It is based on a list of fixed "page", each page contains a fixed number of items.
720
   * Instead of using a linked-list, a array of pointer is used for fast item look-up.
721
   * Look-up for an element is as follow:
722
   * - compute page index: pageIndex = itemIndex / itemsPerPage
723
   * - look-up item in page: pages_[pageIndex][itemIndex % itemsPerPage]
724
   *
725
   * Insertion is amortized constant time (only the array containing the index of pointers
726
   * need to be reallocated when items are appended).
727
   */
728
   class JSON_API ValueInternalArray
729
   {
730
      friend class Value;
731
      friend class ValueIteratorBase;
732
   public:
733
      enum { itemsPerPage = 8 };    // should be a power of 2 for fast divide and modulo.
734
      typedef Value::ArrayIndex ArrayIndex;
735
      typedef unsigned int PageIndex;
736
737
# ifndef JSONCPP_DOC_EXCLUDE_IMPLEMENTATION
738
      struct IteratorState // Must be a POD
739
      {
740
         IteratorState() 
741
            : array_(0)
742
            , currentPageIndex_(0)
743
            , currentItemIndex_(0) 
744
         {
745
         }
746
         ValueInternalArray *array_;
747
         Value **currentPageIndex_;
748
         unsigned int currentItemIndex_;
749
      };
750
# endif // ifndef JSONCPP_DOC_EXCLUDE_IMPLEMENTATION
751
752
      ValueInternalArray();
753
      ValueInternalArray( const ValueInternalArray &other );
754
      ValueInternalArray &operator =( const ValueInternalArray &other );
755
      ~ValueInternalArray();
756
      void swap( ValueInternalArray &other );
757
758
      void clear();
759
      void resize( ArrayIndex newSize );
760
761
      Value &resolveReference( ArrayIndex index );
762
763
      Value *find( ArrayIndex index ) const;
764
765
      ArrayIndex size() const;
766
767
      int compare( const ValueInternalArray &other ) const;
768
769
   private:
770
      static bool equals( const IteratorState &x, const IteratorState &other );
771
      static void increment( IteratorState &iterator );
772
      static void decrement( IteratorState &iterator );
773
      static Value &dereference( const IteratorState &iterator );
774
      static Value &unsafeDereference( const IteratorState &iterator );
775
      static int distance( const IteratorState &x, const IteratorState &y );
776
      static ArrayIndex indexOf( const IteratorState &iterator );
777
      void makeBeginIterator( IteratorState &it ) const;
778
      void makeEndIterator( IteratorState &it ) const;
779
      void makeIterator( IteratorState &it, ArrayIndex index ) const;
780
781
      void makeIndexValid( ArrayIndex index );
782
783
      Value **pages_;
784
      ArrayIndex size_;
785
      PageIndex pageCount_;
786
   };
787
788
   /** \brief Experimental: do not use. Allocator to customize Value internal array.
789
    * Below is an example of a simple implementation (actual implementation use
790
    * memory pool).
791
      \code
792
class DefaultValueArrayAllocator : public ValueArrayAllocator
793
{
794
public: // overridden from ValueArrayAllocator
795
   virtual ~DefaultValueArrayAllocator()
796
   {
797
   }
798
799
   virtual ValueInternalArray *newArray()
800
   {
801
      return new ValueInternalArray();
802
   }
803
804
   virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other )
805
   {
806
      return new ValueInternalArray( other );
807
   }
808
809
   virtual void destruct( ValueInternalArray *array )
810
   {
811
      delete array;
812
   }
813
814
   virtual void reallocateArrayPageIndex( Value **&indexes, 
815
                                          ValueInternalArray::PageIndex &indexCount,
816
                                          ValueInternalArray::PageIndex minNewIndexCount )
817
   {
818
      ValueInternalArray::PageIndex newIndexCount = (indexCount*3)/2 + 1;
819
      if ( minNewIndexCount > newIndexCount )
820
         newIndexCount = minNewIndexCount;
821
      void *newIndexes = realloc( indexes, sizeof(Value*) * newIndexCount );
822
      if ( !newIndexes )
823
         throw std::bad_alloc();
824
      indexCount = newIndexCount;
825
      indexes = static_cast<Value **>( newIndexes );
826
   }
827
   virtual void releaseArrayPageIndex( Value **indexes, 
828
                                       ValueInternalArray::PageIndex indexCount )
829
   {
830
      if ( indexes )
831
         free( indexes );
832
   }
833
834
   virtual Value *allocateArrayPage()
835
   {
836
      return static_cast<Value *>( malloc( sizeof(Value) * ValueInternalArray::itemsPerPage ) );
837
   }
838
839
   virtual void releaseArrayPage( Value *value )
840
   {
841
      if ( value )
842
         free( value );
843
   }
844
};
845
      \endcode
846
    */ 
847
   class JSON_API ValueArrayAllocator
848
   {
849
   public:
850
      virtual ~ValueArrayAllocator();
851
      virtual ValueInternalArray *newArray() = 0;
852
      virtual ValueInternalArray *newArrayCopy( const ValueInternalArray &other ) = 0;
853
      virtual void destructArray( ValueInternalArray *array ) = 0;
854
      /** \brief Reallocate array page index.
855
       * Reallocates an array of pointer on each page.
856
       * \param indexes [input] pointer on the current index. May be \c NULL.
857
       *                [output] pointer on the new index of at least 
858
       *                         \a minNewIndexCount pages. 
859
       * \param indexCount [input] current number of pages in the index.
860
       *                   [output] number of page the reallocated index can handle.
861
       *                            \b MUST be >= \a minNewIndexCount.
862
       * \param minNewIndexCount Minimum number of page the new index must be able to
863
       *                         handle.
864
       */
865
      virtual void reallocateArrayPageIndex( Value **&indexes, 
866
                                             ValueInternalArray::PageIndex &indexCount,
867
                                             ValueInternalArray::PageIndex minNewIndexCount ) = 0;
868
      virtual void releaseArrayPageIndex( Value **indexes, 
869
                                          ValueInternalArray::PageIndex indexCount ) = 0;
870
      virtual Value *allocateArrayPage() = 0;
871
      virtual void releaseArrayPage( Value *value ) = 0;
872
   };
873
#endif // #ifdef JSON_VALUE_USE_INTERNAL_MAP
874
875
876
   /** \brief base class for Value iterators.
877
    *
878
    */
879
   class ValueIteratorBase
880
   {
881
   public:
882
      typedef unsigned int size_t;
883
      typedef int difference_type;
884
      typedef ValueIteratorBase SelfType;
885
886
      ValueIteratorBase();
887
#ifndef JSON_VALUE_USE_INTERNAL_MAP
888
      explicit ValueIteratorBase( const Value::ObjectValues::iterator &current );
889
#else
890
      ValueIteratorBase( const ValueInternalArray::IteratorState &state );
891
      ValueIteratorBase( const ValueInternalMap::IteratorState &state );
892
#endif
893
894
      bool operator ==( const SelfType &other ) const
895
0
      {
896
0
         return isEqual( other );
897
0
      }
898
899
      bool operator !=( const SelfType &other ) const
900
0
      {
901
0
         return !isEqual( other );
902
0
      }
903
904
      difference_type operator -( const SelfType &other ) const
905
0
      {
906
0
         return computeDistance( other );
907
0
      }
908
909
      /// Return either the index or the member name of the referenced value as a Value.
910
      Value key() const;
911
912
      /// Return the index of the referenced Value. -1 if it is not an arrayValue.
913
      UInt index() const;
914
915
      /// Return the member name of the referenced Value. "" if it is not an objectValue.
916
      const char *memberName() const;
917
918
   protected:
919
      Value &deref() const;
920
921
      void increment();
922
923
      void decrement();
924
925
      difference_type computeDistance( const SelfType &other ) const;
926
927
      bool isEqual( const SelfType &other ) const;
928
929
      void copy( const SelfType &other );
930
931
   private:
932
#ifndef JSON_VALUE_USE_INTERNAL_MAP
933
      Value::ObjectValues::iterator current_;
934
      // Indicates that iterator is for a null value.
935
      bool isNull_;
936
#else
937
      union
938
      {
939
         ValueInternalArray::IteratorState array_;
940
         ValueInternalMap::IteratorState map_;
941
      } iterator_;
942
      bool isArray_;
943
#endif
944
   };
945
946
   /** \brief const iterator for object and array value.
947
    *
948
    */
949
   class ValueConstIterator : public ValueIteratorBase
950
   {
951
      friend class Value;
952
   public:
953
      typedef unsigned int size_t;
954
      typedef int difference_type;
955
      typedef const Value &reference;
956
      typedef const Value *pointer;
957
      typedef ValueConstIterator SelfType;
958
959
      ValueConstIterator();
960
   private:
961
      /*! \internal Use by Value to create an iterator.
962
       */
963
#ifndef JSON_VALUE_USE_INTERNAL_MAP
964
      explicit ValueConstIterator( const Value::ObjectValues::iterator &current );
965
#else
966
      ValueConstIterator( const ValueInternalArray::IteratorState &state );
967
      ValueConstIterator( const ValueInternalMap::IteratorState &state );
968
#endif
969
   public:
970
      SelfType &operator =( const ValueIteratorBase &other );
971
972
      SelfType operator++( int )
973
0
      {
974
0
         SelfType temp( *this );
975
0
         ++*this;
976
0
         return temp;
977
0
      }
978
979
      SelfType operator--( int )
980
0
      {
981
0
         SelfType temp( *this );
982
0
         --*this;
983
0
         return temp;
984
0
      }
985
986
      SelfType &operator--()
987
0
      {
988
0
         decrement();
989
0
         return *this;
990
0
      }
991
992
      SelfType &operator++()
993
0
      {
994
0
         increment();
995
0
         return *this;
996
0
      }
997
998
      reference operator *() const
999
0
      {
1000
0
         return deref();
1001
0
      }
1002
   };
1003
1004
1005
   /** \brief Iterator for object and array value.
1006
    */
1007
   class ValueIterator : public ValueIteratorBase
1008
   {
1009
      friend class Value;
1010
   public:
1011
      typedef unsigned int size_t;
1012
      typedef int difference_type;
1013
      typedef Value &reference;
1014
      typedef Value *pointer;
1015
      typedef ValueIterator SelfType;
1016
1017
      ValueIterator();
1018
      ValueIterator( const ValueConstIterator &other );
1019
      ValueIterator( const ValueIterator &other );
1020
   private:
1021
      /*! \internal Use by Value to create an iterator.
1022
       */
1023
#ifndef JSON_VALUE_USE_INTERNAL_MAP
1024
      explicit ValueIterator( const Value::ObjectValues::iterator &current );
1025
#else
1026
      ValueIterator( const ValueInternalArray::IteratorState &state );
1027
      ValueIterator( const ValueInternalMap::IteratorState &state );
1028
#endif
1029
   public:
1030
1031
      SelfType &operator =( const SelfType &other );
1032
1033
      SelfType operator++( int )
1034
0
      {
1035
0
         SelfType temp( *this );
1036
0
         ++*this;
1037
0
         return temp;
1038
0
      }
1039
1040
      SelfType operator--( int )
1041
0
      {
1042
0
         SelfType temp( *this );
1043
0
         --*this;
1044
0
         return temp;
1045
0
      }
1046
1047
      SelfType &operator--()
1048
0
      {
1049
0
         decrement();
1050
0
         return *this;
1051
0
      }
1052
1053
      SelfType &operator++()
1054
0
      {
1055
0
         increment();
1056
0
         return *this;
1057
0
      }
1058
1059
      reference operator *() const
1060
0
      {
1061
0
         return deref();
1062
0
      }
1063
   };
1064
1065
1066
} // namespace Json
1067
1068
1069
#endif // CPPTL_JSON_H_INCLUDED