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.4 by root, Sat Jan 21 13:56:48 2012 UTC vs.
Revision 1.11 by root, Sat May 19 01:56:09 2012 UTC

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

Diff Legend

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