/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: edam
  • Date: 2012-02-25 14:54:33 UTC
  • Revision ID: edam@waxworlds.org-20120225145433-kih8qs45x05cum46
removed Bounce library and updated/fixed new code

Show diffs side-by-side

added added

removed removed

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