Drizzled Public API Documentation

json_internalmap.inl
1 /* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
2  *
3  * JSON Library, originally from http://jsoncpp.sourceforge.net/
4  *
5  * Copyright (C) 2011 Stewart Smith
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions are
10  * met:
11  *
12  * * Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  *
15  * * Redistributions in binary form must reproduce the above
16  * copyright notice, this list of conditions and the following disclaimer
17  * in the documentation and/or other materials provided with the
18  * distribution.
19  *
20  * * The names of its contributors may not be used to endorse or
21  * promote products derived from this software without specific prior
22  * written permission.
23  *
24  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
27  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
28  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
29  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
30  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
31  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
32  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
33  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
34  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35  *
36  */
37 
38 #pragma once
39 // included by json_value.cpp
40 // everything is within Json namespace
41 
42 // //////////////////////////////////////////////////////////////////
43 // //////////////////////////////////////////////////////////////////
44 // //////////////////////////////////////////////////////////////////
45 // class ValueInternalMap
46 // //////////////////////////////////////////////////////////////////
47 // //////////////////////////////////////////////////////////////////
48 // //////////////////////////////////////////////////////////////////
49 
53 ValueInternalLink::ValueInternalLink()
54  : previous_( 0 )
55  , next_( 0 )
56 {
57 }
58 
59 ValueInternalLink::~ValueInternalLink()
60 {
61  for ( int index =0; index < itemPerLink; ++index )
62  {
63  if ( !items_[index].isItemAvailable() )
64  {
65  if ( !items_[index].isMemberNameStatic() )
66  free( keys_[index] );
67  }
68  else
69  break;
70  }
71 }
72 
73 
74 
75 ValueMapAllocator::~ValueMapAllocator()
76 {
77 }
78 
79 #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
80 class DefaultValueMapAllocator : public ValueMapAllocator
81 {
82 public: // overridden from ValueMapAllocator
83  virtual ValueInternalMap *newMap()
84  {
85  return new ValueInternalMap();
86  }
87 
88  virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
89  {
90  return new ValueInternalMap( other );
91  }
92 
93  virtual void destructMap( ValueInternalMap *map )
94  {
95  delete map;
96  }
97 
98  virtual ValueInternalLink *allocateMapBuckets( unsigned int size )
99  {
100  return new ValueInternalLink[size];
101  }
102 
103  virtual void releaseMapBuckets( ValueInternalLink *links )
104  {
105  delete[] links;
106  }
107 
108  virtual ValueInternalLink *allocateMapLink()
109  {
110  return new ValueInternalLink();
111  }
112 
113  virtual void releaseMapLink( ValueInternalLink *link )
114  {
115  delete link;
116  }
117 };
118 #else
119 class DefaultValueMapAllocator : public ValueMapAllocator
121 {
122 public: // overridden from ValueMapAllocator
123  virtual ValueInternalMap *newMap()
124  {
125  ValueInternalMap *map = mapsAllocator_.allocate();
126  new (map) ValueInternalMap(); // placement new
127  return map;
128  }
129 
130  virtual ValueInternalMap *newMapCopy( const ValueInternalMap &other )
131  {
132  ValueInternalMap *map = mapsAllocator_.allocate();
133  new (map) ValueInternalMap( other ); // placement new
134  return map;
135  }
136 
137  virtual void destructMap( ValueInternalMap *map )
138  {
139  if ( map )
140  {
141  map->~ValueInternalMap();
142  mapsAllocator_.release( map );
143  }
144  }
145 
146  virtual ValueInternalLink *allocateMapBuckets( unsigned int size )
147  {
148  return new ValueInternalLink[size];
149  }
150 
151  virtual void releaseMapBuckets( ValueInternalLink *links )
152  {
153  delete[] links;
154  }
155 
156  virtual ValueInternalLink *allocateMapLink()
157  {
158  ValueInternalLink *link = linksAllocator_.allocate();
159  memset( link, 0, sizeof(ValueInternalLink) );
160  return link;
161  }
162 
163  virtual void releaseMapLink( ValueInternalLink *link )
164  {
165  link->~ValueInternalLink();
166  linksAllocator_.release( link );
167  }
168 private:
169  BatchAllocator<ValueInternalMap,1> mapsAllocator_;
170  BatchAllocator<ValueInternalLink,1> linksAllocator_;
171 };
172 #endif
173 
174 static ValueMapAllocator *&mapAllocator()
175 {
176  static DefaultValueMapAllocator defaultAllocator;
177  static ValueMapAllocator *mapAllocator = &defaultAllocator;
178  return mapAllocator;
179 }
180 
183  {
184  mapAllocator(); // ensure mapAllocator() statics are initialized before main().
185  }
186 } dummyMapAllocatorInitializer;
187 
188 
189 
190 // h(K) = value * K >> w ; with w = 32 & K prime w.r.t. 2^32.
191 
192 /*
193 use linked list hash map.
194 buckets array is a container.
195 linked list element contains 6 key/values. (memory = (16+4) * 6 + 4 = 124)
196 value have extra state: valid, available, deleted
197 */
198 
199 
200 ValueInternalMap::ValueInternalMap()
201  : buckets_( 0 )
202  , tailLink_( 0 )
203  , bucketsSize_( 0 )
204  , itemCount_( 0 )
205 {
206 }
207 
208 
209 ValueInternalMap::ValueInternalMap( const ValueInternalMap &other )
210  : buckets_( 0 )
211  , tailLink_( 0 )
212  , bucketsSize_( 0 )
213  , itemCount_( 0 )
214 {
215  reserve( other.itemCount_ );
216  IteratorState it;
217  IteratorState itEnd;
218  other.makeBeginIterator( it );
219  other.makeEndIterator( itEnd );
220  for ( ; !equals(it,itEnd); increment(it) )
221  {
222  bool isStatic;
223  const char *memberName = key( it, isStatic );
224  const Value &aValue = value( it );
225  resolveReference(memberName, isStatic) = aValue;
226  }
227 }
228 
229 
230 ValueInternalMap &
231 ValueInternalMap::operator =( const ValueInternalMap &other )
232 {
233  ValueInternalMap dummy( other );
234  swap( dummy );
235  return *this;
236 }
237 
238 
239 ValueInternalMap::~ValueInternalMap()
240 {
241  if ( buckets_ )
242  {
243  for ( BucketIndex bucketIndex =0; bucketIndex < bucketsSize_; ++bucketIndex )
244  {
245  ValueInternalLink *link = buckets_[bucketIndex].next_;
246  while ( link )
247  {
248  ValueInternalLink *linkToRelease = link;
249  link = link->next_;
250  mapAllocator()->releaseMapLink( linkToRelease );
251  }
252  }
253  mapAllocator()->releaseMapBuckets( buckets_ );
254  }
255 }
256 
257 
258 void
259 ValueInternalMap::swap( ValueInternalMap &other )
260 {
261  ValueInternalLink *tempBuckets = buckets_;
262  buckets_ = other.buckets_;
263  other.buckets_ = tempBuckets;
264  ValueInternalLink *tempTailLink = tailLink_;
265  tailLink_ = other.tailLink_;
266  other.tailLink_ = tempTailLink;
267  BucketIndex tempBucketsSize = bucketsSize_;
268  bucketsSize_ = other.bucketsSize_;
269  other.bucketsSize_ = tempBucketsSize;
270  BucketIndex tempItemCount = itemCount_;
271  itemCount_ = other.itemCount_;
272  other.itemCount_ = tempItemCount;
273 }
274 
275 
276 void
277 ValueInternalMap::clear()
278 {
279  ValueInternalMap dummy;
280  swap( dummy );
281 }
282 
283 
284 ValueInternalMap::BucketIndex
285 ValueInternalMap::size() const
286 {
287  return itemCount_;
288 }
289 
290 bool
291 ValueInternalMap::reserveDelta( BucketIndex growth )
292 {
293  return reserve( itemCount_ + growth );
294 }
295 
296 bool
297 ValueInternalMap::reserve( BucketIndex newItemCount )
298 {
299  if ( !buckets_ && newItemCount > 0 )
300  {
301  buckets_ = mapAllocator()->allocateMapBuckets( 1 );
302  bucketsSize_ = 1;
303  tailLink_ = &buckets_[0];
304  }
305 // BucketIndex idealBucketCount = (newItemCount + ValueInternalLink::itemPerLink) / ValueInternalLink::itemPerLink;
306  return true;
307 }
308 
309 
310 const Value *
311 ValueInternalMap::find( const char *key ) const
312 {
313  if ( !bucketsSize_ )
314  return 0;
315  HashKey hashedKey = hash( key );
316  BucketIndex bucketIndex = hashedKey % bucketsSize_;
317  for ( const ValueInternalLink *current = &buckets_[bucketIndex];
318  current != 0;
319  current = current->next_ )
320  {
321  for ( BucketIndex index=0; index < ValueInternalLink::itemPerLink; ++index )
322  {
323  if ( current->items_[index].isItemAvailable() )
324  return 0;
325  if ( strcmp( key, current->keys_[index] ) == 0 )
326  return &current->items_[index];
327  }
328  }
329  return 0;
330 }
331 
332 
333 Value *
334 ValueInternalMap::find( const char *key )
335 {
336  const ValueInternalMap *constThis = this;
337  return const_cast<Value *>( constThis->find( key ) );
338 }
339 
340 
341 Value &
342 ValueInternalMap::resolveReference( const char *key,
343  bool isStatic )
344 {
345  HashKey hashedKey = hash( key );
346  if ( bucketsSize_ )
347  {
348  BucketIndex bucketIndex = hashedKey % bucketsSize_;
349  ValueInternalLink **previous = 0;
350  BucketIndex index;
351  for ( ValueInternalLink *current = &buckets_[bucketIndex];
352  current != 0;
353  previous = &current->next_, current = current->next_ )
354  {
355  for ( index=0; index < ValueInternalLink::itemPerLink; ++index )
356  {
357  if ( current->items_[index].isItemAvailable() )
358  return setNewItem( key, isStatic, current, index );
359  if ( strcmp( key, current->keys_[index] ) == 0 )
360  return current->items_[index];
361  }
362  }
363  }
364 
365  reserveDelta( 1 );
366  return unsafeAdd( key, isStatic, hashedKey );
367 }
368 
369 
370 void
371 ValueInternalMap::remove( const char *key )
372 {
373  HashKey hashedKey = hash( key );
374  if ( !bucketsSize_ )
375  return;
376  BucketIndex bucketIndex = hashedKey % bucketsSize_;
377  for ( ValueInternalLink *link = &buckets_[bucketIndex];
378  link != 0;
379  link = link->next_ )
380  {
381  BucketIndex index;
382  for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
383  {
384  if ( link->items_[index].isItemAvailable() )
385  return;
386  if ( strcmp( key, link->keys_[index] ) == 0 )
387  {
388  doActualRemove( link, index, bucketIndex );
389  return;
390  }
391  }
392  }
393 }
394 
395 void
396 ValueInternalMap::doActualRemove( ValueInternalLink *link,
397  BucketIndex index,
398  BucketIndex bucketIndex )
399 {
400  // find last item of the bucket and swap it with the 'removed' one.
401  // set removed items flags to 'available'.
402  // if last page only contains 'available' items, then desallocate it (it's empty)
403  ValueInternalLink *&lastLink = getLastLinkInBucket( index );
404  BucketIndex lastItemIndex = 1; // a link can never be empty, so start at 1
405  for ( ;
406  lastItemIndex < ValueInternalLink::itemPerLink;
407  ++lastItemIndex ) // may be optimized with dicotomic search
408  {
409  if ( lastLink->items_[lastItemIndex].isItemAvailable() )
410  break;
411  }
412 
413  BucketIndex lastUsedIndex = lastItemIndex - 1;
414  Value *valueToDelete = &link->items_[index];
415  Value *valueToPreserve = &lastLink->items_[lastUsedIndex];
416  if ( valueToDelete != valueToPreserve )
417  valueToDelete->swap( *valueToPreserve );
418  if ( lastUsedIndex == 0 ) // page is now empty
419  { // remove it from bucket linked list and delete it.
420  ValueInternalLink *linkPreviousToLast = lastLink->previous_;
421  if ( linkPreviousToLast != 0 ) // can not deleted bucket link.
422  {
423  mapAllocator()->releaseMapLink( lastLink );
424  linkPreviousToLast->next_ = 0;
425  lastLink = linkPreviousToLast;
426  }
427  }
428  else
429  {
430  Value dummy;
431  valueToPreserve->swap( dummy ); // restore deleted to default Value.
432  valueToPreserve->setItemUsed( false );
433  }
434  --itemCount_;
435 }
436 
437 
438 ValueInternalLink *&
439 ValueInternalMap::getLastLinkInBucket( BucketIndex bucketIndex )
440 {
441  if ( bucketIndex == bucketsSize_ - 1 )
442  return tailLink_;
443  ValueInternalLink *&previous = buckets_[bucketIndex+1].previous_;
444  if ( !previous )
445  previous = &buckets_[bucketIndex];
446  return previous;
447 }
448 
449 
450 Value &
451 ValueInternalMap::setNewItem( const char *key,
452  bool isStatic,
453  ValueInternalLink *link,
454  BucketIndex index )
455 {
456  char *duplicatedKey = valueAllocator()->makeMemberName( key );
457  ++itemCount_;
458  link->keys_[index] = duplicatedKey;
459  link->items_[index].setItemUsed();
460  link->items_[index].setMemberNameIsStatic( isStatic );
461  return link->items_[index]; // items already default constructed.
462 }
463 
464 
465 Value &
466 ValueInternalMap::unsafeAdd( const char *key,
467  bool isStatic,
468  HashKey hashedKey )
469 {
470  JSON_ASSERT_MESSAGE( bucketsSize_ > 0, "ValueInternalMap::unsafeAdd(): internal logic error." );
471  BucketIndex bucketIndex = hashedKey % bucketsSize_;
472  ValueInternalLink *&previousLink = getLastLinkInBucket( bucketIndex );
473  ValueInternalLink *link = previousLink;
474  BucketIndex index;
475  for ( index =0; index < ValueInternalLink::itemPerLink; ++index )
476  {
477  if ( link->items_[index].isItemAvailable() )
478  break;
479  }
480  if ( index == ValueInternalLink::itemPerLink ) // need to add a new page
481  {
482  ValueInternalLink *newLink = mapAllocator()->allocateMapLink();
483  index = 0;
484  link->next_ = newLink;
485  previousLink = newLink;
486  link = newLink;
487  }
488  return setNewItem( key, isStatic, link, index );
489 }
490 
491 
492 ValueInternalMap::HashKey
493 ValueInternalMap::hash( const char *key ) const
494 {
495  HashKey hash = 0;
496  while ( *key )
497  hash += *key++ * 37;
498  return hash;
499 }
500 
501 
502 int
503 ValueInternalMap::compare( const ValueInternalMap &other ) const
504 {
505  int sizeDiff( itemCount_ - other.itemCount_ );
506  if ( sizeDiff != 0 )
507  return sizeDiff;
508  // Strict order guaranty is required. Compare all keys FIRST, then compare values.
509  IteratorState it;
510  IteratorState itEnd;
511  makeBeginIterator( it );
512  makeEndIterator( itEnd );
513  for ( ; !equals(it,itEnd); increment(it) )
514  {
515  if ( !other.find( key( it ) ) )
516  return 1;
517  }
518 
519  // All keys are equals, let's compare values
520  makeBeginIterator( it );
521  for ( ; !equals(it,itEnd); increment(it) )
522  {
523  const Value *otherValue = other.find( key( it ) );
524  int valueDiff = value(it).compare( *otherValue );
525  if ( valueDiff != 0 )
526  return valueDiff;
527  }
528  return 0;
529 }
530 
531 
532 void
533 ValueInternalMap::makeBeginIterator( IteratorState &it ) const
534 {
535  it.map_ = const_cast<ValueInternalMap *>( this );
536  it.bucketIndex_ = 0;
537  it.itemIndex_ = 0;
538  it.link_ = buckets_;
539 }
540 
541 
542 void
543 ValueInternalMap::makeEndIterator( IteratorState &it ) const
544 {
545  it.map_ = const_cast<ValueInternalMap *>( this );
546  it.bucketIndex_ = bucketsSize_;
547  it.itemIndex_ = 0;
548  it.link_ = 0;
549 }
550 
551 
552 bool
553 ValueInternalMap::equals( const IteratorState &x, const IteratorState &other )
554 {
555  return x.map_ == other.map_
556  && x.bucketIndex_ == other.bucketIndex_
557  && x.link_ == other.link_
558  && x.itemIndex_ == other.itemIndex_;
559 }
560 
561 
562 void
563 ValueInternalMap::incrementBucket( IteratorState &iterator )
564 {
565  ++iterator.bucketIndex_;
566  JSON_ASSERT_MESSAGE( iterator.bucketIndex_ <= iterator.map_->bucketsSize_,
567  "ValueInternalMap::increment(): attempting to iterate beyond end." );
568  if ( iterator.bucketIndex_ == iterator.map_->bucketsSize_ )
569  iterator.link_ = 0;
570  else
571  iterator.link_ = &(iterator.map_->buckets_[iterator.bucketIndex_]);
572  iterator.itemIndex_ = 0;
573 }
574 
575 
576 void
577 ValueInternalMap::increment( IteratorState &iterator )
578 {
579  JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterator using invalid iterator." );
580  ++iterator.itemIndex_;
581  if ( iterator.itemIndex_ == ValueInternalLink::itemPerLink )
582  {
583  JSON_ASSERT_MESSAGE( iterator.link_ != 0,
584  "ValueInternalMap::increment(): attempting to iterate beyond end." );
585  iterator.link_ = iterator.link_->next_;
586  if ( iterator.link_ == 0 )
587  incrementBucket( iterator );
588  }
589  else if ( iterator.link_->items_[iterator.itemIndex_].isItemAvailable() )
590  {
591  incrementBucket( iterator );
592  }
593 }
594 
595 
596 void
597 ValueInternalMap::decrement( IteratorState &iterator )
598 {
599  if ( iterator.itemIndex_ == 0 )
600  {
601  JSON_ASSERT_MESSAGE( iterator.map_, "Attempting to iterate using invalid iterator." );
602  if ( iterator.link_ == &iterator.map_->buckets_[iterator.bucketIndex_] )
603  {
604  JSON_ASSERT_MESSAGE( iterator.bucketIndex_ > 0, "Attempting to iterate beyond beginning." );
605  --(iterator.bucketIndex_);
606  }
607  iterator.link_ = iterator.link_->previous_;
608  iterator.itemIndex_ = ValueInternalLink::itemPerLink - 1;
609  }
610 }
611 
612 
613 const char *
614 ValueInternalMap::key( const IteratorState &iterator )
615 {
616  JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
617  return iterator.link_->keys_[iterator.itemIndex_];
618 }
619 
620 const char *
621 ValueInternalMap::key( const IteratorState &iterator, bool &isStatic )
622 {
623  JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
624  isStatic = iterator.link_->items_[iterator.itemIndex_].isMemberNameStatic();
625  return iterator.link_->keys_[iterator.itemIndex_];
626 }
627 
628 
629 Value &
630 ValueInternalMap::value( const IteratorState &iterator )
631 {
632  JSON_ASSERT_MESSAGE( iterator.link_, "Attempting to iterate using invalid iterator." );
633  return iterator.link_->items_[iterator.itemIndex_];
634 }
635 
636 
637 int
638 ValueInternalMap::distance( const IteratorState &x, const IteratorState &y )
639 {
640  int offset = 0;
641  IteratorState it = x;
642  while ( !equals( it, y ) )
643  increment( it );
644  return offset;
645 }