JsonCpp project page JsonCpp home page

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

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