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

Diff Legend

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