ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/libptytty/src/estl.h
(Generate patch)

Comparing libptytty/src/estl.h (file contents):
Revision 1.1 by sf-exg, Sat Jan 21 13:40:29 2012 UTC vs.
Revision 1.12 by root, Sat May 19 01:57:09 2012 UTC

1#ifndef ESTL_H_
2#define ESTL_H_
3
1#include <stdlib.h> 4#include <stdlib.h>
2#include <string.h> 5#include <string.h>
3 6
7#include "ecb.h"
8
4template<typename T, typename U> static inline T min (T a, U b) { return a < (T)b ? a : (T)b; } 9template<typename T, typename U> static inline T min (T a, U b) { return a < (T)b ? a : (T)b; }
5template<typename T, typename U> static inline T max (T a, U b) { return a > (T)b ? a : (T)b; } 10template<typename T, typename U> static inline T max (T a, U b) { return a > (T)b ? a : (T)b; }
6 11
7template<typename T, typename U> static inline void swap (T& a, U& b) { T t=a; a=(T)b; b=(U)t; } 12template<typename T, typename U> static inline void swap (T& a, U& b) { T t = a; a = (T)b; b = (U)t; }
8 13
9template <typename I, typename T> 14template <typename I, typename T>
10I find (I first, I last, const T& value) 15I find (I first, I last, const T& value)
11{ 16{
12 while (first != last && *first != value) 17 while (first != last && *first != value)
13 ++first; 18 ++first;
14 19
15 return first; 20 return first;
16} 21}
17 22
18/* simplevec taken (and heavily modified), from: 23#include <new>
19 * 24
20 * MICO --- a free CORBA implementation 25#if __cplusplus >= 201103L
21 * Copyright (C) 1997-98 Kay Roemer & Arno Puder 26 #include <type_traits>
22 */ 27#endif
28
29// original version taken from MICO, but this has been completely rewritten
30// known limitations w.r.t. std::vector
31// - many methods missing
32// - no error checking, no exceptions thrown (e.g. at())
33// - size_type is 32bit even on 64 bit hosts, so limited to 2**31 elements
34// - no allocator support
35// - we don't really care about const correctness, but we try
36// - we don't care about namespaces and stupid macros the user might define
37// - no bool specialisation
23template<class T> 38template<class T>
24struct simplevec 39struct simplevec
25{ 40{
26 typedef T* iterator; 41#if ESTL_BIG_VECTOR
27 typedef const T* const_iterator; 42 // shoudl use size_t/ssize_t, but that's not portable enough for us
28 typedef unsigned long size_type; 43 typedef unsigned long size_type;
44 typedef long difference_type;
45#else
46 typedef uint32_t size_type;
47 typedef int32_t difference_type;
48#endif
49
50 typedef T value_type;
51 typedef T *iterator;
52 typedef const T *const_iterator;
53 typedef T *pointer;
54 typedef const T *const_pointer;
55 typedef T &reference;
56 typedef const T &const_reference;
57 // missing: allocator_type
58 // missing: reverse iterator
29 59
30private: 60private:
31 size_type _last, _size; 61 size_type sze, res;
32 T *_buf; 62 T *buf;
63
64 // we shamelessly optimise for "simple" types. everything
65 // "not simple enough" will use the slow path.
66 static bool is_simple_enough ()
67 {
68 return 1; // we are not there yet
69 #if __cplusplus >= 201103L
70 return std::is_trivially_assignable<T, T>::value
71 && std::is_trivially_constructable<T>::value
72 && std::is_trivially_copyable<T>::value
73 && std::is_trivially_destructible<T>::value;
74 #elif ECB_GCC_VERSION(4,4)
75 return __has_trivial_assign (T)
76 && __has_trivial_constructor (T)
77 && __has_trivial_copy (T)
78 && __has_trivial_destructor (T);
79 #else
80 return 0;
81 #endif
82 }
83
84 static void construct (iterator a, size_type n = 1)
85 {
86 if (!is_simple_enough ())
87 while (n--)
88 new (*a++) T ();
89 }
90
91 static void destruct (iterator a, size_type n = 1)
92 {
93 if (!is_simple_enough ())
94 while (n--)
95 (*a++).~T ();
96 }
97
98 template<class I>
99 static void cop_new (iterator a, I b) { new (a) T (*b); }
100 template<class I>
101 static void cop_set (iterator a, I b) { *a = *b ; }
102
103 template<class I>
104 static void copy_lower (iterator dst, I src, size_type n, void (*op)(iterator, I ) = cop_new)
105 {
106 while (n--)
107 op (dst++, src++);
108 }
109
110 static void copy_lower (iterator dst, iterator src, size_type n, void (*op)(iterator, iterator) = cop_new)
111 {
112 if (is_simple_enough ())
113 memmove (dst, src, sizeof (T) * n);
114 else
115 copy_lower<iterator> (dst, src, n, cop_new);
116 }
117
118 static void copy_higher (iterator dst, iterator src, size_type n, void (*op)(iterator, iterator) = cop_new)
119 {
120 if (is_simple_enough ())
121 memmove (dst, src, sizeof (T) * n);
122 else
123 while (n--)
124 op (dst + n, src + n);
125 }
126
127 template<class I>
128 static void copy (iterator dst, I src, size_type n, void (*op)(iterator, I) = cop_new)
129 {
130 copy_lower<I> (dst, src, n, op);
131 }
132
133 static void copy (iterator dst, iterator src, size_type n, void (*op)(iterator, iterator) = cop_new)
134 {
135 if (is_simple_enough ())
136 memcpy (dst, src, sizeof (T) * n);
137 else
138 copy<iterator> (dst, src, n, op);
139 }
140
141 static T *alloc (size_type n) ecb_cold
142 {
143 return (T *)::operator new ((size_t) (sizeof (T) * n));
144 }
145
146 void dealloc () ecb_cold
147 {
148 destruct (buf, sze);
149 ::operator delete (buf);
150 }
151
152 size_type good_size (size_type n) ecb_cold
153 {
154 return n ? 2UL << ecb_ld32 (n) : 5;
155 }
156
157 void ins (iterator where, size_type n)
158 {
159 size_type pos = where - begin ();
160
161 if (ecb_expect_false (sze + n > res))
162 {
163 res = good_size (sze + n);
164
165 T *nbuf = alloc (res);
166 copy (nbuf, buf, sze, cop_new);
167 dealloc ();
168 buf = nbuf;
169 }
170
171 construct (buf + sze, n);
172 copy_higher (buf + pos + n, buf + pos, sze - pos, cop_set);
173 sze += n;
174 }
33 175
34public: 176public:
35 const_iterator begin () const 177 size_type capacity () const { return res; }
178 size_type size () const { return sze; }
179 bool empty () const { return size () == 0; }
180
181 size_t max_size () const
182 {
183 return (~(size_type)0) >> 1;
184 }
185
186 const_iterator begin () const { return &buf [ 0]; }
187 iterator begin () { return &buf [ 0]; }
188 const_iterator end () const { return &buf [sze ]; }
189 iterator end () { return &buf [sze ]; }
190 const_reference front () const { return buf [ 0]; }
191 reference front () { return buf [ 0]; }
192 const_reference back () const { return buf [sze - 1]; }
193 reference back () { return buf [sze - 1]; }
194
195 void reserve (size_type sz)
196 {
197 if (ecb_expect_true (sz <= res))
198 return;
199
200 sz = good_size (sz);
201 T *nbuf = alloc (sz);
202
203 copy (nbuf, begin (), sze);
204 dealloc ();
205
206 buf = nbuf;
207 res = sz;
208 }
209
210 void resize (size_type sz)
211 {
212 reserve (sz);
213
214 if (is_simple_enough ())
215 sze = sz;
216 else
217 {
218 while (sze < sz) construct (buf + sze++);
219 while (sze > sz) destruct (buf + --sze);
220 }
221 }
222
223 simplevec ()
224 : sze(0), res(0), buf(0)
225 {
226 }
227
228 simplevec (size_type n, const T &t = T ())
229 {
230 sze = res = n;
231 buf = alloc (sze);
232
233 while (n--)
234 new (buf + n) T (t);
235 }
236
237 template<class I>
238 simplevec (I first, I last)
239 {
240 sze = res = last - first;
241 buf = alloc (sze);
242 copy (buf, first, sze);
243 }
244
245 simplevec (const simplevec<T> &v)
246 : sze(0), res(0), buf(0)
247 {
248 sze = res = v.size ();
249 buf = alloc (sze);
250 copy (buf, v.begin (), sze);
251 }
252
253 ~simplevec ()
254 {
255 dealloc ();
256 }
257
258 void swap (simplevec<T> &t)
259 {
260 ::swap (sze, t.sze);
261 ::swap (res, t.res);
262 ::swap (buf, t.buf);
263 }
264
265 void clear ()
266 {
267 destruct (buf, sze);
268 sze = 0;
269 }
270
271 void push_back (const T &t)
272 {
273 reserve (sze + 1);
274 new (buf + sze++) T (t);
275 }
276
277 void pop_back ()
278 {
279 destruct (buf + --sze);
280 }
281
282 const_reference operator [](size_type idx) const { return buf[idx]; }
283 reference operator [](size_type idx) { return buf[idx]; }
284
285 const_reference at (size_type idx) const { return buf [idx]; }
286 reference at (size_type idx) { return buf [idx]; }
287
288 template<class I>
289 void assign (I first, I last)
290 {
291 swap (simplevec<T> (first, last));
292 }
293
294 void assign (size_type n, const T &t)
295 {
296 swap (simplevec<T> (n, t));
297 }
298
299 simplevec<T> &operator= (const simplevec<T> &v)
300 {
301 assign (v.begin (), v.end ());
302 return *this;
303 }
304
305 iterator insert (iterator pos, const T &t)
306 {
307 size_type at = pos - begin ();
308
309 ins (pos, 1);
310 buf [at] = t;
311
312 return buf + at;
313 }
314
315 template<class I>
316 iterator insert (iterator pos, I first, I last)
317 {
318 size_type n = last - first;
319 size_type at = pos - begin ();
320
321 ins (pos, n);
322 copy (buf + at, first, n, cop_set);
323
324 return buf + at;
325 }
326
327 iterator insert (iterator pos, size_type n, const T &t)
328 {
329 size_type at = pos - begin ();
330
331 ins (pos, n);
332
333 for (iterator i = buf + at; n--; )
334 *i++ = t;
335
336 return buf + at;
337 }
338
339 void erase (iterator first, iterator last)
340 {
341 size_t n = last - first;
342
343 copy_lower (last, first, end () - last, cop_set);
344 sze -= n;
345 destruct (buf + sze, n);
346 }
347
348 void erase (iterator pos)
349 {
350 if (pos != end ())
351 erase (pos, pos + 1);
352 }
353};
354
355template<class T>
356bool operator ==(const simplevec<T> &v1, const simplevec<T> &v2)
357{
358 if (v1.size () != v2.size ()) return false;
359
360 return !v1.size () || !memcmp (&v1[0], &v2[0], v1.size () * sizeof (T));
361}
362
363template<class T>
364bool operator <(const simplevec<T> &v1, const simplevec<T> &v2)
365{
366 unsigned long minlast = min (v1.size (), v2.size ());
367
368 for (unsigned long i = 0; i < minlast; ++i)
36 { 369 {
37 return &_buf[0]; 370 if (v1[i] < v2[i]) return true;
371 if (v2[i] < v1[i]) return false;
38 } 372 }
39 iterator begin ()
40 {
41 return &_buf[0];
42 }
43 const_iterator end () const
44 {
45 return &_buf[_last];
46 }
47 iterator end ()
48 {
49 return &_buf[_last];
50 }
51 size_type capacity () const
52 {
53 return _size;
54 }
55 size_type size () const
56 {
57 return _last;
58 }
59
60private:
61 static T *alloc (size_type n)
62 {
63 return (T *)::operator new ((size_t) (n * sizeof (T)));
64 }
65 static void dealloc (T *buf)
66 {
67 if (buf)
68 ::operator delete (buf);
69 }
70
71 void reserve (iterator where, size_type n)
72 {
73 if (_last + n <= _size) {
74 memmove (where+n, where, (end ()-where)*sizeof (T));
75 } else {
76 size_type sz = _last+n;
77 sz = (_size == 0) ? max (sz, 5) : max (sz, 2*_size);
78 T *nbuf = alloc (sz);
79 if (_buf) {
80 memcpy (nbuf, begin (), (where-begin ())*sizeof (T));
81 memcpy (nbuf + (where-begin ()) + n, where,
82 (end ()-where)*sizeof (T));
83 dealloc (_buf);
84 }
85 _buf = nbuf;
86 _size = sz;
87 }
88 }
89
90public:
91 void reserve (size_type sz)
92 {
93 if (_size < sz) {
94 sz = (_size == 0) ? max (sz, 5) : max (sz, 2*_size);
95 T *nbuf = alloc (sz);
96 if (_buf) {
97 memcpy (nbuf, begin (), size ()*sizeof (T));
98 dealloc (_buf);
99 }
100 _buf = nbuf;
101 _size = sz;
102 }
103 }
104 simplevec ()
105 : _last(0), _size(0), _buf(0)
106 {
107 }
108 simplevec (size_type n, const T& t = T ())
109 : _last(0), _size(0), _buf(0)
110 {
111 insert (begin (), n, t);
112 }
113 simplevec (const_iterator first, const_iterator last)
114 : _last(0), _size(0), _buf(0)
115 {
116 insert (begin (), first, last);
117 }
118 simplevec (const simplevec<T> &v)
119 : _last(0), _size(0), _buf(0)
120 {
121 reserve (v._last);
122 memcpy (_buf, v.begin (), v.size ()*sizeof (T));
123 _last = v._last;
124 }
125 simplevec<T> &operator= (const simplevec<T> &v)
126 {
127 if (this != &v) {
128 _last = 0;
129 reserve (v._last);
130 memcpy (_buf, v.begin (), v.size ()*sizeof (T));
131 _last = v._last;
132 }
133 return *this;
134 }
135 ~simplevec ()
136 {
137 dealloc (_buf);
138 }
139 const T &front () const
140 {
141 //ministl_assert (size () > 0);
142 return _buf[0];
143 }
144 T &front ()
145 {
146 //ministl_assert (size () > 0);
147 return _buf[0];
148 }
149 const T &back () const
150 {
151 //ministl_assert (size () > 0);
152 return _buf[_last-1];
153 }
154 T &back ()
155 {
156 //ministl_assert (size () > 0);
157 return _buf[_last-1];
158 }
159 bool empty () const
160 {
161 return _last == 0;
162 }
163 void clear ()
164 {
165 _last = 0;
166 }
167 void push_back (const T &t)
168 {
169 reserve (_last+1);
170 *end () = t;
171 ++_last;
172 }
173 void push_back (T &t)
174 {
175 reserve (_last+1);
176 *end () = t;
177 ++_last;
178 }
179 void pop_back ()
180 {
181 //ministl_assert (size () > 0);
182 --_last;
183 }
184 const T &operator[] (size_type idx) const
185 {
186 //ministl_assert (idx < size ());
187 return _buf[idx];
188 }
189 T &operator[] (size_type idx)
190 {
191 //ministl_assert (idx < size ());
192 return _buf[idx];
193 }
194 iterator insert (iterator pos, const T &t)
195 {
196 //ministl_assert (pos <= end ());
197 long at = pos - begin ();
198 reserve (pos, 1);
199 pos = begin ()+at;
200 *pos = t;
201 ++_last;
202 return pos;
203 }
204 iterator insert (iterator pos, const_iterator first, const_iterator last)
205 {
206 //ministl_assert (pos <= end ());
207 long n = last - first;
208 long at = pos - begin ();
209 if (n > 0) {
210 reserve (pos, n);
211 pos = begin ()+at;
212 memcpy (pos, first, (last-first)*sizeof (T));
213 _last += n;
214 }
215 return pos;
216 }
217 iterator insert (iterator pos, size_type n, const T &t)
218 {
219 //ministl_assert (pos <= end ());
220 long at = pos - begin ();
221 if (n > 0) {
222 reserve (pos, n);
223 pos = begin ()+at;
224 for (int i = 0; i < n; ++i)
225 pos[i] = t;
226 _last += n;
227 }
228 return pos;
229 }
230 void erase (iterator first, iterator last)
231 {
232 if (last != first) {
233 memmove (first, last, (end () - last) * sizeof (T));
234 _last -= last - first;
235 }
236 }
237 void erase (iterator pos)
238 {
239 if (pos != end ()) {
240 memmove (pos, pos+1, (end () - (pos+1)) * sizeof (T));
241 --_last;
242 }
243 }
244 void swap (simplevec<T> &t)
245 {
246 ::swap(_last, t._last);
247 ::swap(_size, t._size);
248 ::swap(_buf, t._buf);
249 }
250};
251
252template<class T>
253bool operator== (const simplevec<T> &v1, const simplevec<T> &v2)
254{
255 if (v1.size () != v2.size ())
256 return false;
257 return !v1.size () || !memcmp (&v1[0], &v2[0], v1.size ()*sizeof (T));
258}
259
260template<class T>
261bool operator< (const simplevec<T> &v1, const simplevec<T> &v2)
262{
263 unsigned long minlast = min (v1.size (), v2.size ());
264 for (unsigned long i = 0; i < minlast; ++i) {
265 if (v1[i] < v2[i])
266 return true;
267 if (v2[i] < v1[i])
268 return false;
269 }
270 return v1.size () < v2.size (); 373 return v1.size () < v2.size ();
271} 374}
272 375
273template<typename T> 376template<typename T>
274struct vector : simplevec<T> 377struct vector : simplevec<T>
275{ 378{
276}; 379};
380
381#endif
382

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines