← Back to branch summary

~ubuntu-branches/ubuntu/precise/mysql-5.1/precise

« back to all changes in this revision

Viewing changes to extra/yassl/taocrypt/mySTL/list.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Norbert Tretkowski
  • Date: 2010-03-17 14:56:02 UTC
  • Revision ID: james.westby@ubuntu.com-20100317145602-x7e30l1b2sb5s6w6
Tags: upstream-5.1.45
Import upstream version 5.1.45

Show diffs side-by-side

added added

removed removed

Lines of Context:
extra/yassl/taocrypt/mySTL/list.hpp
 
1
/*
 
2
   Copyright (C) 2000-2007 MySQL AB
 
3
 
 
4
   This program is free software; you can redistribute it and/or modify
 
5
   it under the terms of the GNU General Public License as published by
 
6
   the Free Software Foundation; version 2 of the License.
 
7
 
 
8
   This program is distributed in the hope that it will be useful,
 
9
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
   GNU General Public License for more details.
 
12
 
 
13
   You should have received a copy of the GNU General Public License
 
14
   along with this program; see the file COPYING. If not, write to the
 
15
   Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
 
16
   MA  02110-1301  USA.
 
17
*/
 
18
 
 
19
 
 
20
/* mySTL list implements a simple list
 
21
 *
 
22
 */
 
23
 
 
24
#ifndef mySTL_LIST_HPP
 
25
#define mySTL_LIST_HPP
 
26
 
 
27
 
 
28
#include "helpers.hpp"
 
29
 
 
30
 
 
31
namespace mySTL {
 
32
 
 
33
 
 
34
 
 
35
template<typename T> 
 
36
class list {
 
37
 
 
38
#ifdef __SUNPRO_CC
 
39
/*
 
40
   Sun Forte 7 C++ v. 5.4 needs class 'node' public to be visible to
 
41
   the nested class 'iterator' (a non-standard behaviour).
 
42
*/
 
43
public:
 
44
#endif
 
45
 
 
46
    struct node {
 
47
        node(T t) : prev_(0), next_(0), value_(t) {}
 
48
 
 
49
        node* prev_;
 
50
        node* next_;
 
51
        T     value_;
 
52
    };   
 
53
public:
 
54
    list() : head_(0), tail_(0), sz_(0) {}
 
55
    ~list();
 
56
 
 
57
    void   push_front(T);
 
58
    void   pop_front();
 
59
    T      front() const;
 
60
    void   push_back(T);
 
61
    void   pop_back();
 
62
    T      back() const;
 
63
    bool   remove(T);
 
64
    size_t size()  const { return sz_; }
 
65
    bool   empty() const { return sz_ == 0; }
 
66
 
 
67
    class iterator {
 
68
        node* current_;
 
69
    public:
 
70
        explicit iterator(node* p = 0) : current_(p) {}
 
71
 
 
72
        T& operator*() const
 
73
        {
 
74
            return current_->value_;
 
75
        }
 
76
 
 
77
        T* operator->() const
 
78
        {
 
79
            return &(operator*());
 
80
        }
 
81
 
 
82
        iterator& operator++()
 
83
        {
 
84
            current_ = current_->next_;
 
85
            return *this;
 
86
        }
 
87
 
 
88
        iterator& operator--()
 
89
        {
 
90
            current_ = current_->prev_;
 
91
            return *this;
 
92
        }
 
93
 
 
94
        iterator operator++(int)
 
95
        {
 
96
            iterator tmp = *this;
 
97
            current_ = current_->next_;
 
98
            return tmp;
 
99
        }
 
100
 
 
101
        iterator operator--(int)
 
102
        {
 
103
            iterator tmp = *this;
 
104
            current_ = current_->prev_;
 
105
            return tmp;
 
106
        }
 
107
 
 
108
        bool operator==(const iterator& other) const
 
109
        { 
 
110
            return current_ == other.current_;
 
111
        }
 
112
 
 
113
        bool operator!=(const iterator& other) const
 
114
        {
 
115
            return current_ != other.current_;
 
116
        }
 
117
 
 
118
        friend class list<T>;
 
119
    };
 
120
 
 
121
 
 
122
    class reverse_iterator {
 
123
        node* current_;
 
124
    public:
 
125
        explicit reverse_iterator(node* p = 0) : current_(p) {}
 
126
 
 
127
        T& operator*() const
 
128
        {
 
129
            return current_->value_;
 
130
        }
 
131
 
 
132
        T* operator->() const
 
133
        {
 
134
            return &(operator*());
 
135
        }
 
136
 
 
137
        reverse_iterator& operator++()
 
138
        {
 
139
            current_ = current_->prev_;
 
140
            return *this;
 
141
        }
 
142
 
 
143
        reverse_iterator& operator--()
 
144
        {
 
145
            current_ = current_->next_;
 
146
            return *this;
 
147
        }
 
148
 
 
149
        reverse_iterator operator++(int)
 
150
        {
 
151
            reverse_iterator tmp = *this;
 
152
            current_ = current_->prev_;
 
153
            return tmp;
 
154
        }
 
155
 
 
156
        reverse_iterator operator--(int)
 
157
        {
 
158
            reverse_iterator tmp = *this;
 
159
            current_ = current_->next_;
 
160
            return tmp;
 
161
        }
 
162
 
 
163
        bool operator==(const reverse_iterator& other) const
 
164
        { 
 
165
            return current_ == other.current_;
 
166
        }
 
167
 
 
168
        bool operator!=(const reverse_iterator& other) const
 
169
        {
 
170
            return current_ != other.current_;
 
171
        }
 
172
 
 
173
        friend class list<T>;
 
174
    };
 
175
 
 
176
    bool erase(iterator);
 
177
 
 
178
    iterator         begin()  const { return iterator(head_); }
 
179
    reverse_iterator rbegin() const { return reverse_iterator(tail_); }
 
180
    iterator         end()    const { return iterator(); }
 
181
    reverse_iterator rend()   const { return reverse_iterator(); }
 
182
 
 
183
    typedef iterator const_iterator;    // for now
 
184
 
 
185
    class underflow {};
 
186
    class overflow {}; 
 
187
private:
 
188
    node*  head_;
 
189
    node*  tail_;
 
190
    size_t sz_;
 
191
 
 
192
    node* look_up(T);
 
193
 
 
194
    list(const list&);            // hide copy
 
195
    list& operator=(const list&); // and assign
 
196
};
 
197
 
 
198
 
 
199
template<typename T> 
 
200
list<T>::~list()
 
201
{
 
202
    node* start = head_;
 
203
    node* next_;
 
204
 
 
205
    for (; start; start = next_) {
 
206
        next_ = start->next_;
 
207
        destroy(start);
 
208
        FreeMemory(start);
 
209
    }
 
210
}
 
211
 
 
212
 
 
213
template<typename T> 
 
214
void list<T>::push_front(T t)
 
215
{
 
216
    void* mem = GetMemory(sizeof(node));
 
217
    node* add = new (reinterpret_cast<yassl_pointer>(mem)) node(t);
 
218
 
 
219
    if (head_) {
 
220
        add->next_ = head_;
 
221
        head_->prev_ = add;
 
222
    }
 
223
    else
 
224
        tail_ = add;
 
225
 
 
226
    head_ = add;
 
227
    ++sz_; 
 
228
}
 
229
 
 
230
 
 
231
template<typename T> 
 
232
void list<T>::pop_front()
 
233
{
 
234
    node* front = head_;
 
235
 
 
236
    if (head_ == 0)
 
237
        return;
 
238
    else if (head_ == tail_)
 
239
        head_ = tail_ = 0;
 
240
    else {
 
241
        head_ = head_->next_;
 
242
        head_->prev_ = 0;
 
243
    }
 
244
    destroy(front);
 
245
    FreeMemory(front);
 
246
    --sz_;
 
247
}
 
248
 
 
249
 
 
250
template<typename T> 
 
251
T list<T>::front() const
 
252
{
 
253
    if (head_ == 0) return T();
 
254
    return head_->value_;
 
255
}
 
256
 
 
257
 
 
258
template<typename T> 
 
259
void list<T>::push_back(T t)
 
260
{
 
261
    void* mem = GetMemory(sizeof(node));
 
262
    node* add = new (reinterpret_cast<yassl_pointer>(mem)) node(t);
 
263
 
 
264
    if (tail_) {
 
265
        tail_->next_ = add;
 
266
        add->prev_ = tail_;
 
267
    }
 
268
    else
 
269
        head_ = add;
 
270
 
 
271
    tail_ = add;
 
272
    ++sz_;
 
273
}
 
274
 
 
275
 
 
276
template<typename T> 
 
277
void list<T>::pop_back()
 
278
{
 
279
    node* rear = tail_;
 
280
 
 
281
    if (tail_ == 0)
 
282
        return;
 
283
    else if (tail_ == head_)
 
284
        tail_ = head_ = 0;
 
285
    else {
 
286
        tail_ = tail_->prev_;
 
287
        tail_->next_ = 0;
 
288
    }
 
289
    destroy(rear);
 
290
    FreeMemory(rear);
 
291
    --sz_;
 
292
}
 
293
 
 
294
 
 
295
template<typename T> 
 
296
T list<T>::back() const
 
297
{
 
298
    if (tail_ == 0) return T();
 
299
    return tail_->value_;
 
300
}
 
301
 
 
302
 
 
303
template<typename T>
 
304
typename list<T>::node* list<T>::look_up(T t)
 
305
{
 
306
    node* list = head_;
 
307
 
 
308
    if (list == 0) return 0;
 
309
 
 
310
    for (; list; list = list->next_)
 
311
        if (list->value_ == t)
 
312
            return list;
 
313
 
 
314
    return 0;
 
315
}
 
316
 
 
317
 
 
318
template<typename T> 
 
319
bool list<T>::remove(T t)
 
320
{
 
321
    node* del = look_up(t);
 
322
 
 
323
    if (del == 0)
 
324
        return false;
 
325
    else if (del == head_)
 
326
        pop_front();
 
327
    else if (del == tail_)
 
328
        pop_back();
 
329
    else {
 
330
        del->prev_->next_ = del->next_;
 
331
        del->next_->prev_ = del->prev_;
 
332
 
 
333
        destroy(del);
 
334
        FreeMemory(del);
 
335
        --sz_;
 
336
    }
 
337
    return true;
 
338
}
 
339
 
 
340
 
 
341
template<typename T> 
 
342
bool list<T>::erase(iterator iter)
 
343
{
 
344
    node* del = iter.current_;
 
345
 
 
346
    if (del == 0)
 
347
        return false;
 
348
    else if (del == head_)
 
349
        pop_front();
 
350
    else if (del == tail_)
 
351
        pop_back();
 
352
    else {
 
353
        del->prev_->next_ = del->next_;
 
354
        del->next_->prev_ = del->prev_;
 
355
 
 
356
        destroy(del);
 
357
        FreeMemory(del);
 
358
        --sz_;
 
359
    }
 
360
    return true;
 
361
}
 
362
 
 
363
 
 
364
 
 
365
} // namespace mySTL
 
366
 
 
367
#endif // mySTL_LIST_HPP