/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 ¤t ); |
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 ¤t ); |
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 ¤t ); |
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 |