libptytty/src/estl.h

#ifndef ESTL_H_
#define ESTL_H_

#include <stdlib.h>
#include <string.h>

#include "ecb.h"

template<typename T, typename U> static inline T min (T a, U b) { return a < (T)b ? a : (T)b; }
template<typename T, typename U> static inline T max (T a, U b) { return a > (T)b ? a : (T)b; }

template<typename T, typename U> static inline void swap (T& a, U& b) { T t = a; a = (T)b; b = (U)t; }

template <typename I, typename T>
I find (I first, I last, const T& value)
{
  while (first != last && *first != value)
    ++first;

  return first;
}

#include <new>

#if ECB_CPP11
  #include <type_traits>
#endif

namespace estl
{
#if ESTL_LARGE_MEMORY_MODEL
  // should use size_t/ssize_t, but that's not portable enough for us
  typedef unsigned long size_type;
  typedef          long difference_type;
#else
  typedef uint32_t size_type;
  typedef  int32_t difference_type;
#endif

  template<typename T>
  struct scoped_ptr
  {
    T *p;

    scoped_ptr ()     : p (0) { }

    explicit
    scoped_ptr (T *a) : p (a) { }

    ~scoped_ptr ()
    {
      delete p;
    }

    void reset (T *a)
    {
      delete p;
      p = a;
    }

    T *operator ->() const { return p; }
    T &operator *() const { return *p; }

    operator T *()  { return p; }
    T *get () const { return p; }
  };

  template<typename T>
  struct scoped_array
  {
    T *p;

    scoped_array ()     : p (0) { }

    explicit
    scoped_array (T *a) : p (a) { }

    ~scoped_array ()
    {
      delete [] p;
    }

    void reset (T *a)
    {
      delete [] p;
      p = a;
    }

    T & operator [](size_type idx) const { return p[idx]; }

    operator T *()  { return p; }
    T *get () const { return p; }
  };
}

// original version taken from MICO, but this has been completely rewritten
// known limitations w.r.t. std::vector
// - many methods missing
// - no error checking, no exceptions thrown (e.g. at())
// - size_type is 32bit even on 64 bit hosts, so limited to 2**31 elements
// - no allocator support
// - we don't really care about const correctness, but we try
// - we don't care about namespaces and stupid macros the user might define
// - no bool specialisation
template<class T>
struct simplevec
{
  typedef estl::size_type size_type;

  typedef       T  value_type;
  typedef       T *iterator;
  typedef const T *const_iterator;
  typedef       T *pointer;
  typedef const T *const_pointer;
  typedef       T &reference;
  typedef const T &const_reference;
  // missing: allocator_type
  // missing: reverse iterator

private:
  size_type sze, res;
  T *buf;

  // we shamelessly optimise for "simple" types. everything
  // "not simple enough" will use the slow path.
  static bool is_simple_enough ()
  {
    #if ECB_CPP11
      return std::is_trivially_assignable<T, T>::value
          && std::is_trivially_constructible<T>::value
          && std::is_trivially_copyable<T>::value
          && std::is_trivially_destructible<T>::value;
    #elif ECB_GCC_VERSION(4,4) || ECB_CLANG_VERSION(2,8)
      return __has_trivial_assign (T)
          && __has_trivial_constructor (T)
          && __has_trivial_copy (T)
          && __has_trivial_destructor (T);
    #else
      return 0;
    #endif
  }

  static void construct (iterator a, size_type n = 1)
  {
    if (!is_simple_enough ())
      while (n--)
        new (a++) T ();
  }

  static void destruct (iterator a, size_type n = 1)
  {
    if (!is_simple_enough ())
      while (n--)
        (*a++).~T ();
  }

  template<class I>
  static void cop_new (iterator a, I b) { new (a) T (*b); }
  template<class I>
  static void cop_set (iterator a, I b) {     *a  =  *b ; }

  // MUST copy forwards
  template<class I>
  static void copy (iterator dst, I        src, size_type n, void (*op)(iterator,        I))
  {
    while (n--)
      op (dst++, src++);
  }

  static void copy (iterator dst, iterator src, size_type n, void (*op)(iterator, iterator))
  {
    if (is_simple_enough ())
      memcpy (dst, src, sizeof (T) * n);
    else
      copy<iterator> (dst, src, n, op);
  }

  static T *alloc (size_type n) ecb_cold
  {
    return (T *)::operator new ((size_t) (sizeof (T) * n));
  }

  void dealloc () ecb_cold
  {
    destruct (buf, sze);
    ::operator delete (buf);
  }

  size_type good_size (size_type n) ecb_cold
  {
    return n ? 2UL << ecb_ld32 (n) : 5;
  }

  void ins (iterator where, size_type n)
  {
    size_type pos = where - begin ();

    if (ecb_expect_false (sze + n > res))
      {
        res = good_size (sze + n);

        T *nbuf = alloc (res);
        copy (nbuf, buf, sze, cop_new);
        dealloc ();
        buf = nbuf;
      }

    construct (buf + sze, n);

    iterator src = buf + pos;
    if (is_simple_enough ())
      memmove (src + n, src, sizeof (T) * (sze - pos));
    else
      for (size_type i = sze - pos; i--; )
        cop_set (src + n + i, src + i);

    sze += n;
  }

public:
  size_type capacity () const { return res; }
  size_type size     () const { return sze; }
  bool empty         () const { return size () == 0; }

  size_t max_size () const
  {
    return (~(size_type)0) >> 1;
  }

  const_iterator  begin () const { return &buf [      0]; }
        iterator  begin ()       { return &buf [      0]; }
  const_iterator  end   () const { return &buf [sze    ]; }
        iterator  end   ()       { return &buf [sze    ]; }
  const_reference front () const { return  buf [      0]; }
        reference front ()       { return  buf [      0]; }
  const_reference back  () const { return  buf [sze - 1]; }
        reference back  ()       { return  buf [sze - 1]; }

  void reserve (size_type sz)
  {
    if (ecb_expect_true (sz <= res))
      return;

    sz = good_size (sz);
    T *nbuf = alloc (sz);

    copy (nbuf, begin (), sze, cop_new);
    dealloc ();

    buf  = nbuf;
    res = sz;
  }

  void resize (size_type sz)
  {
    reserve (sz);

    if (is_simple_enough ())
      sze = sz;
    else
      {
        while (sze < sz) construct (buf + sze++);
        while (sze > sz) destruct  (buf + --sze);
      }
  }

  simplevec ()
  : sze(0), res(0), buf(0)
  {
  }

  simplevec (size_type n, const T &t = T ())
  {
    sze = res = n;
    buf = alloc (sze);

    while (n--)
      new (buf + n) T (t);
  }

  simplevec (const_iterator first, const_iterator last)
  {
    sze = res = last - first;
    buf = alloc (sze);
    copy (buf, first, sze, cop_new);
  }

  simplevec (const simplevec<T> &v)
  : sze(0), res(0), buf(0)
  {
    sze = res = v.size ();
    buf = alloc (sze);
    copy (buf, v.begin (), sze, cop_new);
  }

  ~simplevec ()
  {
    dealloc ();
  }

  void swap (simplevec<T> &t)
  {
    ::swap (sze, t.sze);
    ::swap (res, t.res);
    ::swap (buf, t.buf);
  }

  void clear ()
  {
    destruct (buf, sze);
    sze = 0;
  }

  void push_back (const T &t)
  {
    reserve (sze + 1);
    new (buf + sze++) T (t);
  }

  void pop_back ()
  {
    destruct (buf + --sze);
  }

  const_reference operator [](size_type idx) const { return buf[idx]; }
        reference operator [](size_type idx)       { return buf[idx]; }

  const_reference at (size_type idx) const { return buf [idx]; }
        reference at (size_type idx)       { return buf [idx]; }

  void assign (const_iterator first, const_iterator last)
  {
    simplevec<T> v (first, last);
    swap (v);
  }

  void assign (size_type n, const T &t)
  {
    simplevec<T> v (n, t);
    swap (v);
  }

  simplevec<T> &operator= (const simplevec<T> &v)
  {
    assign (v.begin (), v.end ());
    return *this;
  }

  iterator insert (iterator pos, const T &t)
  {
    size_type at = pos - begin ();

    ins (pos, 1);
    buf [at] = t;

    return buf + at;
  }

  iterator insert (iterator pos, const_iterator first, const_iterator last)
  {
    size_type n  = last - first;
    size_type at = pos - begin ();

    ins (pos, n);
    copy (buf + at, first, n, cop_set);

    return buf + at;
  }

  iterator insert (iterator pos, size_type n, const T &t)
  {
    size_type at = pos - begin ();

    ins (pos, n);

    for (iterator i = buf + at; n--; )
      *i++ = t;

    return buf + at;
  }

  iterator erase (iterator first, iterator last)
  {
    size_type n = last - first;
    size_type c = end () - last;

    if (is_simple_enough ())
      memmove (first, last, sizeof (T) * c);
    else
      copy (first, last, c, cop_set);

    sze -= n;
    destruct (buf + sze, n);

    return first;
  }

  iterator erase (iterator pos)
  {
    if (pos != end ())
      erase (pos, pos + 1);

    return pos;
  }
};

template<class T>
bool operator ==(const simplevec<T> &v1, const simplevec<T> &v2)
{
  if (v1.size () != v2.size ()) return false;

  return !v1.size () || !memcmp (&v1[0], &v2[0], v1.size () * sizeof (T));
}

template<class T>
bool operator <(const simplevec<T> &v1, const simplevec<T> &v2)
{
  unsigned long minlast = min (v1.size (), v2.size ());

  for (unsigned long i = 0; i < minlast; ++i)
    {
      if (v1[i] < v2[i]) return true;
      if (v2[i] < v1[i]) return false;
    }
  return v1.size () < v2.size ();
}

template<typename T>
struct vector : simplevec<T>
{
};

#endif

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