To get this branch, use:
bzr branch
http://bzr.ed.am/elec/propeller-clock
« back to all changes in this revision
Viewing changes to src/utility/associative_base
- browse files at revision 57
- compare with another revision
- download diff
- download tarball
- view history from revision 57
- Committer: edam
- Date: 2012-02-25 01:31:43 UTC
- Revision ID: tim@ed.am-20120225013143-9fet2y2d3fjlrwez
added ulibc
- files added:
- src/utility
added
removed
src/utility/associative_base
1
/* Copyright (C) 2007 Garrett A. Kajmowicz
2
This file is part of the uClibc++ Library.
3
4
This library is free software; you can redistribute it and/or
5
modify it under the terms of the GNU Lesser General Public
6
License as published by the Free Software Foundation; either
7
version 2.1 of the License, or (at your option) any later version.
8
9
This library is distributed in the hope that it will be useful,
10
but WITHOUT ANY WARRANTY; without even the implied warranty of
11
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12
Lesser General Public License for more details.
13
14
You should have received a copy of the GNU Lesser General Public
15
License along with this library; if not, write to the Free Software
16
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
*/
18
19
20
21
#include<memory>
22
#include<utility.h>
23
#include<iterator>
24
#include<functional>
25
#include<list>
26
27
28
#ifndef __STD_HEADER_ASSOCIATIVE_BASE
29
#define __STD_HEADER_ASSOCIATIVE_BASE
30
31
#pragma GCC visibility push(default)
32
33
namespace std{
34
35
36
/*
37
* The basic premise here is that most of the code used by map, multimap, set and
38
* multiset is really common. There are a number of interface additions, and
39
* considerations about how to address multiple entries with the same key.
40
* The goal is that the tree/storage code should be here, and managing
41
* single or multiple counts will be left to subclasses.
42
* Yes, inheritence for the purpose of code sharing is usually a bad idea.
43
* However, since our goal is to reduce the total amount of code written
44
* and the overall binary size, this seems to be the best approach possible.
45
*/
46
47
template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __base_associative;
48
template<class ValueType, class Compare, class Allocator> class _associative_iter;
49
template<class ValueType, class Compare, class Allocator> class _associative_citer;
50
51
template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __single_associative;
52
template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __multi_associative;
53
54
template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __base_associative{
55
56
protected:
57
58
public:
59
typedef Key key_type;
60
typedef ValueType value_type;
61
typedef Compare key_compare;
62
typedef Allocator allocator_type;
63
typedef typename Allocator::reference reference;
64
typedef typename Allocator::const_reference const_reference;
65
typedef typename Allocator::size_type size_type;
66
typedef typename Allocator::difference_type difference_type;
67
typedef typename Allocator::pointer pointer;
68
typedef typename Allocator::const_pointer const_pointer;
69
typedef __base_associative<Key, ValueType, Compare, Allocator> associative_type;
70
71
typedef _associative_iter<value_type, Compare, Allocator> iterator;
72
typedef _associative_citer<value_type, Compare, Allocator> const_iterator;
73
typedef typename std::reverse_iterator<iterator> reverse_iterator;
74
typedef typename std::reverse_iterator<const_iterator> const_reverse_iterator;
75
76
77
explicit __base_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type))
78
: c(comp), value_to_key(v_to_k) { }
79
protected:
80
__base_associative(const associative_type& x)
81
: c(x.c), backing(x.backing), value_to_key(x.value_to_key) { }
82
83
public:
84
~__base_associative(){
85
}
86
87
bool empty() const{
88
return backing.empty();
89
}
90
size_type size() const{
91
return backing.size();
92
}
93
size_type max_size() const{
94
return backing.max_size();
95
}
96
97
iterator begin(){
98
return iterator(backing.begin());
99
}
100
101
const_iterator begin() const{
102
return const_iterator(backing.begin());
103
}
104
105
iterator end() {
106
return iterator(backing.end());
107
}
108
109
const_iterator end() const{
110
return const_iterator(backing.end());
111
}
112
113
reverse_iterator rbegin(){
114
return reverse_iterator(end());
115
}
116
117
const_reverse_iterator rbegin() const{
118
return const_reverse_iterator(end());
119
}
120
121
reverse_iterator rend(){
122
return reverse_iterator(begin());
123
}
124
125
const_reverse_iterator rend() const{
126
return const_reverse_iterator(begin());
127
}
128
129
130
iterator lower_bound(const key_type &x);
131
const_iterator lower_bound(const key_type &x) const;
132
iterator upper_bound(const key_type &x);
133
const_iterator upper_bound(const key_type &x) const;
134
135
pair<iterator,iterator> equal_range(const key_type& x){
136
pair<iterator, iterator> retval;
137
retval.first = lower_bound(x);
138
retval.second = retval.first;
139
while(retval.second != end() && !c(x, value_to_key(*retval.second))){
140
++retval.second;
141
}
142
return retval;
143
}
144
pair<const_iterator,const_iterator> equal_range(const key_type& x) const{
145
pair<const_iterator, const_iterator> retval;
146
retval.first = lower_bound(x);
147
retval.second = retval.first;
148
while(retval.second != end() && !c(x, value_to_key(*retval.second))){
149
++retval.second;
150
}
151
return retval;
152
}
153
154
iterator find(const key_type& x){
155
iterator retval = lower_bound(x);
156
if(retval == end()){
157
return retval;
158
}
159
if(c(x, value_to_key(*retval))){
160
return end();
161
}
162
return retval;
163
}
164
const_iterator find(const key_type& x) const{
165
const_iterator retval = lower_bound(x);
166
if(retval == end()){
167
return retval;
168
}
169
if(c(x, value_to_key(*retval))){
170
return end();
171
}
172
return retval;
173
}
174
size_type count(const key_type& x) const{
175
size_type retval(0);
176
const_iterator first = lower_bound(x);
177
while(first != end() && !c(x, value_to_key(*first))){
178
++retval;
179
++first;
180
}
181
return retval;
182
}
183
184
void clear(){
185
backing.clear();
186
}
187
188
void erase(iterator pos){
189
backing.erase(pos.base_iterator());
190
}
191
size_type erase(const key_type& x){
192
size_type count(0);
193
iterator start = lower_bound(x);
194
iterator end = upper_bound(x);
195
while(start != end){
196
start = backing.erase(start.base_iterator());
197
++count;
198
}
199
return count;
200
}
201
void erase(iterator first, iterator last){
202
while(first != last){
203
backing.erase(first.base_iterator());
204
++first;
205
}
206
}
207
208
key_compare key_comp() const{
209
return c;
210
}
211
212
__base_associative &operator=(const __base_associative & x){
213
c = x.c;
214
backing = x.backing;
215
value_to_key = x.value_to_key;
216
return *this;
217
}
218
bool operator==(const __base_associative & x){
219
return x.backing == backing;
220
}
221
bool operator!=(const __base_associative & x){
222
return !(x.backing == backing);
223
}
224
225
protected:
226
void swap(__base_associative & x);
227
228
Compare c;
229
std::list<value_type> backing;
230
231
const key_type (*value_to_key)(const value_type);
232
233
};
234
235
236
/*
237
* Tree iterators for the base associative class
238
*/
239
240
template<class ValueType, class Compare, class Allocator> class _associative_citer
241
: public std::iterator<
242
bidirectional_iterator_tag,
243
ValueType,
244
typename Allocator::difference_type,
245
ValueType*,
246
ValueType&
247
>
248
{
249
protected:
250
typedef std::list<ValueType> listtype;
251
252
typename listtype::const_iterator base_iter;
253
friend class _associative_iter<ValueType, Compare, Allocator>;
254
public:
255
_associative_citer() { }
256
_associative_citer(const _associative_citer & m)
257
: base_iter(m.base_iter) { }
258
_associative_citer(const typename listtype::const_iterator & m)
259
: base_iter(m) { }
260
~_associative_citer() { }
261
ValueType operator*() const{
262
return *base_iter;
263
}
264
const ValueType * operator->() const{
265
return &(*base_iter);
266
}
267
_associative_citer & operator=(const _associative_citer & m){
268
base_iter = m.base_iter;
269
return *this;
270
}
271
bool operator==(const _associative_citer & m) const{
272
return m.base_iter == base_iter;
273
}
274
bool operator!=(const _associative_citer & m) const{
275
return m.base_iter != base_iter;
276
}
277
_associative_citer & operator++(){
278
++base_iter;
279
return *this;
280
}
281
_associative_citer operator++(int){
282
//The following approach ensures that we only need to
283
//provide code for ++ in one place (above)
284
_associative_citer temp(base_iter);
285
++base_iter;
286
return temp;
287
}
288
_associative_citer & operator--(){
289
--base_iter;
290
return *this;
291
}
292
_associative_citer operator--(int){
293
//The following approach ensures that we only need to
294
//provide code for -- in one place (above)
295
_associative_citer temp(base_iter);
296
--base_iter;
297
return temp;
298
}
299
300
//This is an implementation-defined function designed to make internals work correctly
301
typename listtype::const_iterator base_iterator(){
302
return base_iter;
303
}
304
};
305
306
307
template<class ValueType, class Compare, class Allocator> class _associative_iter
308
: public std::iterator<
309
bidirectional_iterator_tag,
310
ValueType,
311
typename Allocator::difference_type,
312
ValueType*,
313
ValueType&
314
>
315
{
316
protected:
317
typedef std::list<ValueType> listtype;
318
319
typename listtype::iterator base_iter;
320
typedef _associative_citer<ValueType, Compare, Allocator> __associative_citer;
321
322
public:
323
_associative_iter() { }
324
_associative_iter(const _associative_iter & m)
325
: base_iter(m.base_iter) { }
326
_associative_iter(const typename listtype::iterator & m)
327
: base_iter(m) { }
328
~_associative_iter() { }
329
const ValueType & operator*() const{
330
return *base_iter;
331
}
332
ValueType & operator*(){
333
return *base_iter;
334
}
335
ValueType * operator->(){
336
return &(*base_iter);
337
}
338
const ValueType * operator->() const{
339
return &(*base_iter);
340
}
341
_associative_iter & operator=(const _associative_iter & m){
342
base_iter = m.base_iter;
343
return *this;
344
}
345
bool operator==(const _associative_iter & m) const{
346
return m.base_iter == base_iter;
347
}
348
bool operator==(const __associative_citer & m) const{
349
return m.base_iter == base_iter;
350
}
351
bool operator!=(const _associative_iter & m) const{
352
return m.base_iter != base_iter;
353
}
354
bool operator!=(const __associative_citer & m) const{
355
return m.base_iter != base_iter;
356
}
357
_associative_iter & operator++(){
358
++base_iter;
359
return *this;
360
}
361
_associative_iter operator++(int){
362
//The following approach ensures that we only need to
363
//provide code for ++ in one place (above)
364
_associative_iter temp(base_iter);
365
++base_iter;
366
return temp;
367
}
368
_associative_iter & operator--(){
369
--base_iter;
370
return *this;
371
}
372
_associative_iter operator--(int){
373
//The following approach ensures that we only need to
374
//provide code for -- in one place (above)
375
_associative_iter temp(base_iter);
376
--base_iter;
377
return temp;
378
}
379
operator __associative_citer() const{
380
return __associative_citer(base_iter);
381
}
382
typename listtype::iterator base_iterator(){
383
return base_iter;
384
}
385
const typename listtype::iterator base_iterator() const{
386
return base_iter;
387
}
388
389
};
390
391
392
// The lower_bound code is really crappy linear search. However, it is a dead
393
// simple implementation (easy to audit). It can also be easily replaced.
394
395
396
template <class Key, class ValueType, class Compare, class Allocator>
397
typename __base_associative<Key, ValueType, Compare, Allocator>::iterator
398
__base_associative<Key, ValueType, Compare, Allocator>::lower_bound(const key_type &x)
399
{
400
iterator retval = begin();
401
while(retval != end() && c(value_to_key(*retval), x)){
402
++retval;
403
}
404
return retval;
405
}
406
407
template <class Key, class ValueType, class Compare, class Allocator>
408
typename __base_associative<Key, ValueType, Compare, Allocator>::const_iterator
409
__base_associative<Key, ValueType, Compare, Allocator>::lower_bound(const key_type &x) const
410
{
411
const_iterator retval = begin();
412
while(retval != end() && c(value_to_key(*retval), x)){
413
++retval;
414
}
415
return retval;
416
}
417
418
// Upper bound search is linear from the point of lower_bound. This is likely the best solution
419
// in all but the most pathological of cases.
420
421
template <class Key, class ValueType, class Compare, class Allocator>
422
typename __base_associative<Key, ValueType, Compare, Allocator>::iterator
423
__base_associative<Key, ValueType, Compare, Allocator>::upper_bound(const key_type &x)
424
{
425
iterator retval = lower_bound(x);
426
while(retval != end() && !c(x, value_to_key(*retval))){
427
++retval;
428
}
429
return retval;
430
}
431
432
template <class Key, class ValueType, class Compare, class Allocator>
433
typename __base_associative<Key, ValueType, Compare, Allocator>::const_iterator
434
__base_associative<Key, ValueType, Compare, Allocator>::upper_bound(const key_type &x) const
435
{
436
const_iterator retval = begin();
437
while(retval != end() && !c(x, value_to_key(*retval))){
438
++retval;
439
}
440
return retval;
441
}
442
443
444
template <class Key, class ValueType, class Compare, class Allocator>
445
void __base_associative<Key, ValueType, Compare, Allocator>::swap(__base_associative<Key, ValueType, Compare, Allocator>& m)
446
{
447
Compare n = c;
448
c = m.c;
449
m.c = n;
450
451
m.backing.swap(backing);
452
}
453
454
455
template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __single_associative :
456
public __base_associative<Key, ValueType, Compare, Allocator>
457
{
458
protected:
459
typedef __base_associative<Key, ValueType, Compare, Allocator> base;
460
using base::backing;
461
462
using base::c;
463
464
public:
465
typedef typename base::key_type key_type;
466
typedef typename base::value_type value_type;
467
typedef typename base::key_compare key_compare;
468
typedef typename base::allocator_type allocator_type;
469
typedef typename base::reference reference;
470
typedef typename base::const_reference const_reference;
471
typedef typename base::iterator iterator;
472
typedef typename base::const_iterator const_iterator;
473
typedef typename base::size_type size_type;
474
typedef typename base::difference_type difference_type;
475
typedef typename base::pointer pointer;
476
typedef typename base::const_pointer const_pointer;
477
typedef typename base::reverse_iterator reverse_iterator;
478
typedef typename base::const_reverse_iterator const_reverse_iterator;
479
480
using base::begin;
481
using base::end;
482
using base::rbegin;
483
using base::rend;
484
485
using base::empty;
486
using base::size;
487
using base::max_size;
488
489
using base::find;
490
using base::count;
491
using base::lower_bound;
492
using base::upper_bound;
493
using base::equal_range;
494
495
using base::operator=;
496
using base::operator==;
497
using base::operator!=;
498
499
explicit __single_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type))
500
: base(comp, A, v_to_k) { }
501
502
template <class InputIterator> __single_associative(
503
InputIterator first,
504
InputIterator last,
505
const Compare& comp,
506
const Allocator& A,
507
const key_type (*v_to_k)(const value_type)
508
) : base(comp, A, v_to_k) {
509
insert(first, last);
510
}
511
512
pair<iterator, bool> insert(const value_type& x){
513
pair<iterator, bool> retval;
514
iterator location = lower_bound(value_to_key(x));
515
retval.second = true;
516
//Empty list or need to insert at end
517
if(end() == location){
518
backing.push_back(x);
519
retval.first = --(end());
520
return retval;
521
}
522
//Something in the list
523
if(c(value_to_key(x), value_to_key(*location))){
524
location = backing.insert(location.base_iterator(), x);
525
retval.first = location;
526
}else{
527
retval.second = false;
528
retval.first = location;
529
}
530
return retval;
531
}
532
533
iterator insert(iterator position, const value_type& x){
534
// FIXME - this is cheating and probably should be more efficient since we are
535
// now log(n) to find for inserts
536
return insert(x).first;
537
}
538
539
template <class InputIterator> void insert(InputIterator first, InputIterator last){
540
while(first != last){
541
insert(*first);
542
++first;
543
}
544
}
545
546
};
547
548
549
template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __multi_associative :
550
public __base_associative<Key, ValueType, Compare, Allocator>
551
{
552
protected:
553
typedef __base_associative<Key, ValueType, Compare, Allocator> base;
554
using base::backing;
555
556
using base::c;
557
558
public:
559
typedef typename base::key_type key_type;
560
typedef typename base::value_type value_type;
561
typedef typename base::key_compare key_compare;
562
typedef typename base::allocator_type allocator_type;
563
typedef typename base::reference reference;
564
typedef typename base::const_reference const_reference;
565
typedef typename base::iterator iterator;
566
typedef typename base::const_iterator const_iterator;
567
typedef typename base::size_type size_type;
568
typedef typename base::difference_type difference_type;
569
typedef typename base::pointer pointer;
570
typedef typename base::const_pointer const_pointer;
571
typedef typename base::reverse_iterator reverse_iterator;
572
typedef typename base::const_reverse_iterator const_reverse_iterator;
573
574
using base::begin;
575
using base::end;
576
using base::rbegin;
577
using base::rend;
578
579
using base::empty;
580
using base::size;
581
using base::max_size;
582
583
using base::find;
584
using base::count;
585
using base::lower_bound;
586
using base::upper_bound;
587
using base::equal_range;
588
589
using base::operator=;
590
using base::operator==;
591
592
593
explicit __multi_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type))
594
: base(comp, A, v_to_k) { }
595
596
template <class InputIterator> __multi_associative(
597
InputIterator first,
598
InputIterator last,
599
const Compare& comp,
600
const Allocator& A,
601
const key_type (*v_to_k)(const value_type)
602
) : base(comp, A, v_to_k) {
603
insert(first, last);
604
}
605
606
iterator insert(const value_type& x){
607
iterator location = lower_bound(value_to_key(x));
608
609
if(location == begin()){
610
backing.push_front(x);
611
location = begin();
612
}else{
613
location = backing.insert(location.base_iterator(), x);
614
}
615
return location;
616
}
617
618
iterator insert(iterator position, const value_type& x){
619
// FIXME - this is cheating and probably should be more efficient since we are
620
// now log(n) to find for inserts
621
return insert(x);
622
}
623
624
template <class InputIterator> void insert(InputIterator first, InputIterator last){
625
while(first != last){
626
insert(*first);
627
++first;
628
}
629
}
630
};
631
632
633
634
635
}
636
637
#pragma GCC visibility pop
638
639
#endif //__STD_HEADER_ASSOCIATIVE_BASE
640
Loggerhead is a web-based interface for Bazaar branches
Version: 1.18.2, Revision: 480