/elec/propeller-clock

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

  • Committer: Dan
  • Date: 2011-11-03 00:54:13 UTC
  • Revision ID: dan@waxworlds.org-20111103005413-miheyjsrpm3a0r1e
modified notes

Show diffs side-by-side

added added

removed removed

Lines of Context:
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