« back to all changes in this revision
Viewing changes to plugin/json_server/json/json_internalmap.inl
- browse files at revision 2310
- compare with another revision
- download diff
- download tarball
- view history from revision 2310
- Committer: Mark Atwood
- Date: 2011-05-12 22:20:08 UTC
- mfrom: (2283.4.17 json-interface)
- Revision ID: me@mark.atwood.name-20110512222008-7facdn0qu7lsbm0g
merge lp:~stewart/drizzle/json-interface
- files added:
- plugin/http_functions
- plugin/json_server
- plugin/json_server/json
- plugin/json_server/tests
- plugin/json_server/tests/r
- plugin/json_server/tests/t
- files modified:
- drizzled/plugin/client/cached.h
added
removed
plugin/json_server/json/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
50
/** \internal MUST be safely initialized using memset( this, 0, sizeof(ValueInternalLink) );
51
* This optimization is used by the fast allocator.
52
*/
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
/// @todo make this thread-safe (lock when accessign batch allocator)
120
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
181
static struct DummyMapAllocatorInitializer {
182
DummyMapAllocatorInitializer()
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 ¤t->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 = ¤t->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
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1