src/third_party/jsoncpp/json_value.h

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