JsonCpp project page JsonCpp home page

json_internalmap.inl
Go to the documentation of this file.
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 // included by json_value.cpp
7 
8 namespace Json {
9 
10 // //////////////////////////////////////////////////////////////////
11 // //////////////////////////////////////////////////////////////////
12 // //////////////////////////////////////////////////////////////////
13 // class ValueInternalMap
14 // //////////////////////////////////////////////////////////////////
15 // //////////////////////////////////////////////////////////////////
16 // //////////////////////////////////////////////////////////////////
17 
22  : previous_( 0 )
23  , next_( 0 )
24 {
25 }
26 
28 {
29  for ( int index =0; index < itemPerLink; ++index )
30  {
31  if ( !items_[index].isItemAvailable() )
32  {
33  if ( !items_[index].isMemberNameStatic() )
34  free( keys_[index] );
35  }
36  else
37  break;
38  }
39 }
40 
41 
42 
44 {
45 }
46 
47 #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
48 class DefaultValueMapAllocator : public ValueMapAllocator
49 {
50 public: // overridden from ValueMapAllocator
51  virtual ValueInternalMap *newMap()
52  {
53  return new ValueInternalMap();
54  }
55 
56  virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
57  {
58  return new ValueInternalMap( other );
59  }
60 
61  virtual void destructMap( ValueInternalMap *map )
62  {
63  delete map;
64  }
65 
66  virtual ValueInternalLink *allocateMapBuckets( unsigned int size )
67  {
68  return new ValueInternalLink[size];
69  }
70 
71  virtual void releaseMapBuckets( ValueInternalLink *links )
72  {
73  delete [] links;
74  }
75 
76  virtual ValueInternalLink *allocateMapLink()
77  {
78  return new ValueInternalLink();
79  }
80 
81  virtual void releaseMapLink( ValueInternalLink *link )
82  {
83  delete link;
84  }
85 };
86 #else
87 class DefaultValueMapAllocator : public ValueMapAllocator
89 {
90 public: // overridden from ValueMapAllocator
91  virtual ValueInternalMap *newMap()
92  {
93  ValueInternalMap *map = mapsAllocator_.allocate();
94  new (map) ValueInternalMap(); // placement new
95  return map;
96  }
97 
98  virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
99  {
100  ValueInternalMap *map = mapsAllocator_.allocate();
101  new (map) ValueInternalMap( other ); // placement new
102  return map;
103  }
104 
105  virtual void destructMap( ValueInternalMap *map )
106  {
107  if ( map )
108  {
109  map->~ValueInternalMap();
110  mapsAllocator_.release( map );
111  }
112  }
113 
114  virtual ValueInternalLink *allocateMapBuckets( unsigned int size )
115  {
116  return new ValueInternalLink[size];
117  }
118 
119  virtual void releaseMapBuckets( ValueInternalLink *links )
120  {
121  delete [] links;
122  }
123 
124  virtual ValueInternalLink *allocateMapLink()
125  {
126  ValueInternalLink *link = linksAllocator_.allocate();
127  memset( link, 0, sizeof(ValueInternalLink) );
128  return link;
129  }
130 
131  virtual void releaseMapLink( ValueInternalLink *link )
132  {
133  link->~ValueInternalLink();
134  linksAllocator_.release( link );
135  }
136 private:
137  BatchAllocator<ValueInternalMap,1> mapsAllocator_;
138  BatchAllocator<ValueInternalLink,1> linksAllocator_;
139 };
140 #endif
141 
143 {
144  static DefaultValueMapAllocator defaultAllocator;
145  static ValueMapAllocator *mapAllocator = &defaultAllocator;
146  return mapAllocator;
147 }
148 
149 static struct DummyMapAllocatorInitializer {
150  DummyMapAllocatorInitializer()
151  {
152  mapAllocator(); // ensure mapAllocator() statics are initialized before main().
153  }
155 
156 
157 
158 // h(K) = value * K >> w ; with w = 32 & K prime w.r.t. 2^32.
159 
160 /*
161 use linked list hash map.
162 buckets array is a container.
163 linked list element contains 6 key/values. (memory = (16+4) * 6 + 4 = 124)
164 value have extra state: valid, available, deleted
165 */
166 
167 
169  : buckets_( 0 )
170  , tailLink_( 0 )
171  , bucketsSize_( 0 )
172  , itemCount_( 0 )
173 {
174 }
175 
176 
178  : buckets_( 0 )
179  , tailLink_( 0 )
180  , bucketsSize_( 0 )
181  , itemCount_( 0 )
182 {
183  reserve( other.itemCount_ );
184  IteratorState it;
185  IteratorState itEnd;
186  other.makeBeginIterator( it );
187  other.makeEndIterator( itEnd );
188  for ( ; !equals(it,itEnd); increment(it) )
189  {
190  bool isStatic;
191  const char *memberName = key( it, isStatic );
192  const Value &aValue = value( it );
193  resolveReference(memberName, isStatic) = aValue;
194  }
195 }
196 
197 
200 {
201  ValueInternalMap dummy( other );
202  swap( dummy );
203  return *this;
204 }
205 
206 
208 {
209  if ( buckets_ )
210  {
211  for ( BucketIndex bucketIndex =0; bucketIndex < bucketsSize_; ++bucketIndex )
212  {
213  ValueInternalLink *link = buckets_[bucketIndex].next_;
214  while ( link )
215  {
216  ValueInternalLink *linkToRelease = link;
217  link = link->next_;
218  mapAllocator()->releaseMapLink( linkToRelease );
219  }
220  }
221  mapAllocator()->releaseMapBuckets( buckets_ );
222  }
223 }
224 
225 
226 void
228 {
229  ValueInternalLink *tempBuckets = buckets_;
230  buckets_ = other.buckets_;
231  other.buckets_ = tempBuckets;
232  ValueInternalLink *tempTailLink = tailLink_;
233  tailLink_ = other.tailLink_;
234  other.tailLink_ = tempTailLink;
235  BucketIndex tempBucketsSize = bucketsSize_;
236  bucketsSize_ = other.bucketsSize_;
237  other.bucketsSize_ = tempBucketsSize;
238  BucketIndex tempItemCount = itemCount_;
239  itemCount_ = other.itemCount_;
240  other.itemCount_ = tempItemCount;
241 }
242 
243 
244 void
246 {
247  ValueInternalMap dummy;
248  swap( dummy );
249 }
250 
251 
254 {
255  return itemCount_;
256 }
257 
258 bool
260 {
261  return reserve( itemCount_ + growth );
262 }
263 
264 bool
266 {
267  if ( !buckets_ && newItemCount > 0 )
268  {
269  buckets_ = mapAllocator()->allocateMapBuckets( 1 );
270  bucketsSize_ = 1;
271  tailLink_ = &buckets_[0];
272  }
273 // BucketIndex idealBucketCount = (newItemCount + ValueInternalLink::itemPerLink) / ValueInternalLink::itemPerLink;
274  return true;
275 }
276 
277 
278 const Value *
279 ValueInternalMap::find( const char *key ) const
280 {
281  if ( !bucketsSize_ )
282  return 0;
283  HashKey hashedKey = hash( key );
284  BucketIndex bucketIndex = hashedKey % bucketsSize_;
285  for ( const ValueInternalLink *current = &buckets_[bucketIndex];
286  current != 0;
287  current = current->next_ )
288  {
289  for ( BucketIndex index=0; index < ValueInternalLink::itemPerLink; ++index )
290  {
291  if ( current->items_[index].isItemAvailable() )
292  return 0;
293  if ( strcmp( key, current->keys_[index] ) == 0 )
294  return &current->items_[index];
295  }
296  }
297  return 0;
298 }
299 
300 
301 Value *
302 ValueInternalMap::find( const char *key )
303 {
304  const ValueInternalMap *constThis = this;
305  return const_cast<Value *>( constThis->find( key ) );
306 }
307 
308 
309 Value &
311  bool isStatic )
312 {
313  HashKey hashedKey = hash( key );
314  if ( bucketsSize_ )
315  {
316  BucketIndex bucketIndex = hashedKey % bucketsSize_;
317  ValueInternalLink **previous = 0;
318  BucketIndex index;
319  for ( ValueInternalLink *current = &buckets_[bucketIndex];
320  current != 0;
321  previous = &current->next_, current = current->next_ )
322  {
323  for ( index=0; index < ValueInternalLink::itemPerLink; ++index )
324  {
325  if ( current->items_[index].isItemAvailable() )
326  return setNewItem( key, isStatic, current, index );
327  if ( strcmp( key, current->keys_[index] ) == 0 )
328  return current->items_[index];
329  }
330  }
331  }
332 
333  reserveDelta( 1 );
334  return unsafeAdd( key, isStatic, hashedKey );
335 }
336 
337 
338 void
339 ValueInternalMap::remove( const char *key )
340 {
341  HashKey hashedKey = hash( key );
342  if ( !bucketsSize_ )
343  return;
344  BucketIndex bucketIndex = hashedKey % bucketsSize_;
345  for ( ValueInternalLink *link = &buckets_[bucketIndex];
346  link != 0;
347  link = link->next_ )
348  {
349  BucketIndex index;
350  for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
351  {
352  if ( link->items_[index].isItemAvailable() )
353  return;
354  if ( strcmp( key, link->keys_[index] ) == 0 )
355  {
356  doActualRemove( link, index, bucketIndex );
357  return;
358  }
359  }
360  }
361 }
362 
363 void
365  BucketIndex index,
366  BucketIndex bucketIndex )
367 {
368  // find last item of the bucket and swap it with the 'removed' one.
369  // set removed items flags to 'available'.
370  // if last page only contains 'available' items, then desallocate it (it's empty)
371  ValueInternalLink *&lastLink = getLastLinkInBucket( index );
372  BucketIndex lastItemIndex = 1; // a link can never be empty, so start at 1
373  for ( ;
374  lastItemIndex < ValueInternalLink::itemPerLink;
375  ++lastItemIndex ) // may be optimized with dicotomic search
376  {
377  if ( lastLink->items_[lastItemIndex].isItemAvailable() )
378  break;
379  }
380 
381  BucketIndex lastUsedIndex = lastItemIndex - 1;
382  Value *valueToDelete = &link->items_[index];
383  Value *valueToPreserve = &lastLink->items_[lastUsedIndex];
384  if ( valueToDelete != valueToPreserve )
385  valueToDelete->swap( *valueToPreserve );
386  if ( lastUsedIndex == 0 ) // page is now empty
387  { // remove it from bucket linked list and delete it.
388  ValueInternalLink *linkPreviousToLast = lastLink->previous_;
389  if ( linkPreviousToLast != 0 ) // can not deleted bucket link.
390  {
391  mapAllocator()->releaseMapLink( lastLink );
392  linkPreviousToLast->next_ = 0;
393  lastLink = linkPreviousToLast;
394  }
395  }
396  else
397  {
398  Value dummy;
399  valueToPreserve->swap( dummy ); // restore deleted to default Value.
400  valueToPreserve->setItemUsed( false );
401  }
402  --itemCount_;
403 }
404 
405 
408 {
409  if ( bucketIndex == bucketsSize_ - 1 )
410  return tailLink_;
411  ValueInternalLink *&previous = buckets_[bucketIndex+1].previous_;
412  if ( !previous )
413  previous = &buckets_[bucketIndex];
414  return previous;
415 }
416 
417 
418 Value &
420  bool isStatic,
421  ValueInternalLink *link,
422  BucketIndex index )
423 {
424  char *duplicatedKey = makeMemberName( key );
425  ++itemCount_;
426  link->keys_[index] = duplicatedKey;
427  link->items_[index].setItemUsed();
428  link->items_[index].setMemberNameIsStatic( isStatic );
429  return link->items_[index]; // items already default constructed.
430 }
431 
432 
433 Value &
434 ValueInternalMap::unsafeAdd( const char *key,
435  bool isStatic,
436  HashKey hashedKey )
437 {
438  JSON_ASSERT_MESSAGE( bucketsSize_ > 0, "ValueInternalMap::unsafeAdd(): internal logic error." );
439  BucketIndex bucketIndex = hashedKey % bucketsSize_;
440  ValueInternalLink *&previousLink = getLastLinkInBucket( bucketIndex );
441  ValueInternalLink *link = previousLink;
442  BucketIndex index;
443  for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
444  {
445  if ( link->items_[index].isItemAvailable() )
446  break;
447  }
448  if ( index == ValueInternalLink::itemPerLink ) // need to add a new page
449  {
451  index = 0;
452  link->next_ = newLink;
453  previousLink = newLink;
454  link = newLink;
455  }
456  return setNewItem( key, isStatic, link, index );
457 }
458 
459 
461 ValueInternalMap::hash( const char *key ) const
462 {
463  HashKey hash = 0;
464  while ( *key )
465  hash += *key++ * 37;
466  return hash;
467 }
468 
469 
470 int
472 {
473  int sizeDiff( itemCount_ - other.itemCount_ );
474  if ( sizeDiff != 0 )
475  return sizeDiff;
476  // Strict order guaranty is required. Compare all keys FIRST, then compare values.
477  IteratorState it;
478  IteratorState itEnd;
479  makeBeginIterator( it );
480  makeEndIterator( itEnd );
481  for ( ; !equals(it,itEnd); increment(it) )
482  {
483  if ( !other.find( key( it ) ) )
484  return 1;
485  }
486 
487  // All keys are equals, let's compare values
488  makeBeginIterator( it );
489  for ( ; !equals(it,itEnd); increment(it) )
490  {
491  const Value *otherValue = other.find( key( it ) );
492  int valueDiff = value(it).compare( *otherValue );
493  if ( valueDiff != 0 )
494  return valueDiff;
495  }
496  return 0;
497 }
498 
499 
500 void
501 ValueInternalMap::makeBeginIterator( IteratorState &it ) const
502 {
503  it.map_ = const_cast<ValueInternalMap *>( this );
504  it.bucketIndex_ = 0;
505  it.itemIndex_ = 0;
506  it.link_ = buckets_;
507 }
508 
509 
510 void
511 ValueInternalMap::makeEndIterator( IteratorState &it ) const
512 {
513  it.map_ = const_cast<ValueInternalMap *>( this );
514  it.bucketIndex_ = bucketsSize_;
515  it.itemIndex_ = 0;
516  it.link_ = 0;
517 }
518 
519 
520 bool
521 ValueInternalMap::equals( const IteratorState &x, const IteratorState &other )
522 {
523  return x.map_ == other.map_
524  && x.bucketIndex_ == other.bucketIndex_
525  && x.link_ == other.link_
526  && x.itemIndex_ == other.itemIndex_;
527 }
528 
529 
530 void
531 ValueInternalMap::incrementBucket( IteratorState &iterator )
532 {
533  ++iterator.bucketIndex_;
534  JSON_ASSERT_MESSAGE( iterator.bucketIndex_ <= iterator.map_->bucketsSize_,
535  "ValueInternalMap::increment(): attempting to iterate beyond end." );
536  if ( iterator.bucketIndex_ == iterator.map_->bucketsSize_ )
537  iterator.link_ = 0;
538  else
539  iterator.link_ = &(iterator.map_->buckets_[iterator.bucketIndex_]);
540  iterator.itemIndex_ = 0;
541 }
542 
543 
544 void
545 ValueInternalMap::increment( IteratorState &iterator )
546 {
547  JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterator using invalid iterator." );
548  ++iterator.itemIndex_;
549  if ( iterator.itemIndex_ == ValueInternalLink::itemPerLink )
550  {
551  JSON_ASSERT_MESSAGE( iterator.link_ != 0,
552  "ValueInternalMap::increment(): attempting to iterate beyond end." );
553  iterator.link_ = iterator.link_->next_;
554  if ( iterator.link_ == 0 )
555  incrementBucket( iterator );
556  }
557  else if ( iterator.link_->items_[iterator.itemIndex_].isItemAvailable() )
558  {
559  incrementBucket( iterator );
560  }
561 }
562 
563 
564 void
565 ValueInternalMap::decrement( IteratorState &iterator )
566 {
567  if ( iterator.itemIndex_ == 0 )
568  {
569  JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterate using invalid iterator." );
570  if ( iterator.link_ == &iterator.map_->buckets_[iterator.bucketIndex_] )
571  {
572  JSON_ASSERT_MESSAGE( iterator.bucketIndex_ > 0, "Attempting to iterate beyond beginning." );
573  --(iterator.bucketIndex_);
574  }
575  iterator.link_ = iterator.link_->previous_;
576  iterator.itemIndex_ = ValueInternalLink::itemPerLink - 1;
577  }
578 }
579 
580 
581 const char *
582 ValueInternalMap::key( const IteratorState &iterator )
583 {
584  JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
585  return iterator.link_->keys_[iterator.itemIndex_];
586 }
587 
588 const char *
589 ValueInternalMap::key( const IteratorState &iterator, bool &isStatic )
590 {
591  JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
592  isStatic = iterator.link_->items_[iterator.itemIndex_].isMemberNameStatic();
593  return iterator.link_->keys_[iterator.itemIndex_];
594 }
595 
596 
597 Value &
598 ValueInternalMap::value( const IteratorState &iterator )
599 {
600  JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
601  return iterator.link_->items_[iterator.itemIndex_];
602 }
603 
604 
605 int
606 ValueInternalMap::distance( const IteratorState &x, const IteratorState &y )
607 {
608  int offset = 0;
609  IteratorState it = x;
610  while ( !equals( it, y ) )
611  increment( it );
612  return offset;
613 }
614 
615 } // namespace Json
unsigned int HashKey
Definition: value.h:669
bool reserveDelta(BucketIndex growth)
int compare(const Value &other) const
Definition: json_value.cpp:527
void remove(const char *key)
Value & unsafeAdd(const char *key, bool isStatic, HashKey hashedKey)
void swap(ValueInternalMap &other)
virtual void releaseMapLink(ValueInternalLink *link)=0
int compare(const ValueInternalMap &other) const
#define JSON_ASSERT_MESSAGE(condition, message)
Definition: json_value.cpp:26
virtual void releaseMapBuckets(ValueInternalLink *links)=0
void doActualRemove(ValueInternalLink *link, BucketIndex index, BucketIndex bucketIndex)
bool reserve(BucketIndex newItemCount)
Allocator to customize Value internal map.
Definition: value.h:616
Value & setNewItem(const char *key, bool isStatic, ValueInternalLink *link, BucketIndex index)
JSON (JavaScript Object Notation).
Definition: config.h:73
static struct Json::DummyMapAllocatorInitializer dummyMapAllocatorInitializer
ValueInternalLink *& getLastLinkInBucket(BucketIndex bucketIndex)
const Value * find(const char *key) const
void swap(Value &other)
Swap values.
Definition: json_value.cpp:508
ValueInternalMap & operator=(const ValueInternalMap &other)
unsigned int BucketIndex
Definition: value.h:670
Value & resolveReference(const char *key, bool isStatic)
static ValueMapAllocator *& mapAllocator()
Represents a JSON value.
Definition: value.h:118
A linked page based hash-table implementation used internally by Value.
Definition: value.h:664
virtual ValueInternalLink * allocateMapLink()=0
HashKey hash(const char *key) const
virtual ValueInternalLink * allocateMapBuckets(unsigned int size)=0
BucketIndex size() const

SourceForge Logo hosts this site. Send comments to:
Json-cpp Developers