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.2 by sf-exg, Sat Jan 21 13:44:38 2012 UTC vs.
Revision 1.29 by sf-exg, Thu Nov 13 13:58:12 2014 UTC

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

Diff Legend

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