commonroutesServer/www/plugins/ionic-plugin-keyboard/src/blackberry10/native/public/json_internalmap.inl
www/plugins/ionic-plugin-keyboard/src/blackberry10/native/public/json_internalmap.inlRaw
1// included by json_value.cpp
2// everything is within Json namespace
3
4// //////////////////////////////////////////////////////////////////
5// //////////////////////////////////////////////////////////////////
6// //////////////////////////////////////////////////////////////////
7// class ValueInternalMap
8// //////////////////////////////////////////////////////////////////
9// //////////////////////////////////////////////////////////////////
10// //////////////////////////////////////////////////////////////////
11
12/** \internal MUST be safely initialized using memset( this, 0, sizeof(ValueInternalLink) );
13 * This optimization is used by the fast allocator.
14 */
15ValueInternalLink::ValueInternalLink()
16 : previous_( 0 )
17 , next_( 0 )
18{
19}
20
21ValueInternalLink::~ValueInternalLink()
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
37ValueMapAllocator::~ValueMapAllocator()
38{
39}
40
41#ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
42class DefaultValueMapAllocator : public ValueMapAllocator
43{
44public: // 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/// @todo make this thread-safe (lock when accessign batch allocator)
82class DefaultValueMapAllocator : public ValueMapAllocator
83{
84public: // 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 }
130private:
131 BatchAllocator<ValueInternalMap,1> mapsAllocator_;
132 BatchAllocator<ValueInternalLink,1> linksAllocator_;
133};
134#endif
135
136static ValueMapAllocator *&mapAllocator()
137{
138 static DefaultValueMapAllocator defaultAllocator;
139 static ValueMapAllocator *mapAllocator = &defaultAllocator;
140 return mapAllocator;
141}
142
143static struct DummyMapAllocatorInitializer {
144 DummyMapAllocatorInitializer()
145 {
146 mapAllocator(); // ensure mapAllocator() statics are initialized before main().
147 }
148} dummyMapAllocatorInitializer;
149
150
151
152// h(K) = value * K >> w ; with w = 32 & K prime w.r.t. 2^32.
153
154/*
155use linked list hash map.
156buckets array is a container.
157linked list element contains 6 key/values. (memory = (16+4) * 6 + 4 = 124)
158value have extra state: valid, available, deleted
159*/
160
161
162ValueInternalMap::ValueInternalMap()
163 : buckets_( 0 )
164 , tailLink_( 0 )
165 , bucketsSize_( 0 )
166 , itemCount_( 0 )
167{
168}
169
170
171ValueInternalMap::ValueInternalMap( const ValueInternalMap &other )
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
192ValueInternalMap &
193ValueInternalMap::operator =( const ValueInternalMap &other )
194{
195 ValueInternalMap dummy( other );
196 swap( dummy );
197 return *this;
198}
199
200
201ValueInternalMap::~ValueInternalMap()
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
220void
221ValueInternalMap::swap( ValueInternalMap &other )
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
238void
239ValueInternalMap::clear()
240{
241 ValueInternalMap dummy;
242 swap( dummy );
243}
244
245
246ValueInternalMap::BucketIndex
247ValueInternalMap::size() const
248{
249 return itemCount_;
250}
251
252bool
253ValueInternalMap::reserveDelta( BucketIndex growth )
254{
255 return reserve( itemCount_ + growth );
256}
257
258bool
259ValueInternalMap::reserve( BucketIndex newItemCount )
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
272const Value *
273ValueInternalMap::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 ¤t->items_[index];
289 }
290 }
291 return 0;
292}
293
294
295Value *
296ValueInternalMap::find( const char *key )
297{
298 const ValueInternalMap *constThis = this;
299 return const_cast<Value *>( constThis->find( key ) );
300}
301
302
303Value &
304ValueInternalMap::resolveReference( const char *key,
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 = ¤t->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
332void
333ValueInternalMap::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
357void
358ValueInternalMap::doActualRemove( ValueInternalLink *link,
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
400ValueInternalLink *&
401ValueInternalMap::getLastLinkInBucket( BucketIndex bucketIndex )
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
412Value &
413ValueInternalMap::setNewItem( const char *key,
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
427Value &
428ValueInternalMap::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 {
444 ValueInternalLink *newLink = mapAllocator()->allocateMapLink();
445 index = 0;
446 link->next_ = newLink;
447 previousLink = newLink;
448 link = newLink;
449 }
450 return setNewItem( key, isStatic, link, index );
451}
452
453
454ValueInternalMap::HashKey
455ValueInternalMap::hash( const char *key ) const
456{
457 HashKey hash = 0;
458 while ( *key )
459 hash += *key++ * 37;
460 return hash;
461}
462
463
464int
465ValueInternalMap::compare( const ValueInternalMap &other ) const
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
494void
495ValueInternalMap::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
504void
505ValueInternalMap::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
514bool
515ValueInternalMap::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
524void
525ValueInternalMap::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
538void
539ValueInternalMap::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
558void
559ValueInternalMap::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
575const char *
576ValueInternalMap::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
582const char *
583ValueInternalMap::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
591Value &
592ValueInternalMap::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
599int
600ValueInternalMap::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}