libptytty/src/estl.h

#ifndef ESTL_H_
#define ESTL_H_

#include <stdlib.h>
#include <string.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;
}

// see ecb.h for details
#ifndef ECB_GCC_VERSION
  #if !defined __GNUC_MINOR__ || defined __INTEL_COMPILER || defined __SUNPRO_C || defined __SUNPRO_CC || defined __llvm__ || defined __clang__
    #define ECB_GCC_VERSION(major,minor) 0
  #else
    #define ECB_GCC_VERSION(major,minor) (__GNUC__ > (major) || (__GNUC__ == (major) && __GNUC_MINOR__ >= (minor)))
  #endif
#endif

#include <new>

#if __cplusplus >= 201103L
  #include <type_traits>
#endif

/* simplevec taken (and heavily modified), from:
 *
 *  MICO --- a free CORBA implementation
 *  Copyright (C) 1997-98 Kay Roemer & Arno Puder
 *  originally GPLv2 or any later
 */
template<class T>
struct simplevec
{
  typedef T *iterator;
  typedef const T *const_iterator;
  typedef unsigned long size_type;

  static bool is_simple_enough ()
  {
    #if __cplusplus >= 201103L
      return std::is_trivially_assignable<T, T>::value
          && std::is_trivially_constructable<T>::value
          && std::is_trivially_copyable<T>::value
          && std::is_trivially_destructible<T>::value;
    #elif ECB_GCC_VERSION(4,4)
      return __has_trivial_assign (T)
          && __has_trivial_constructor (T)
          && __has_trivial_copy (T)
          && __has_trivial_destructor (T);
    #else
      return 0;
    #endif
  }

private:
  size_type _last, _size;
  T *_buf;

public:
  const_iterator begin () const { return &_buf[0]; }
  iterator       begin ()       { return &_buf[0]; }

  const_iterator end () const { return &_buf[_last]; }
  iterator       end ()       { return &_buf[_last]; }

  size_type capacity () const { return _size; }
  size_type size     () const { return _last; }

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

  void dealloc ()
  {
    if (!is_simple_enough ())
      for (size_type i = 0; i < _last; ++i)
        _buf [i].~T ();

    ::operator delete (_buf);
  }

  size_type good_size (size_type n)
  {
    return max (n, _size ? _size * 2 : 5);
  }

  // these copy helpers actually use the copy constructor, not assignment
  static void copy_lower (iterator dst, iterator src, size_type n)
  {
    if (is_simple_enough ())
      memmove (dst, src, sizeof (T) * n);
    else
      while (n--)
        new (dst++) T (*src++);
  }

  static void copy_higher (iterator dst, iterator src, size_type n)
  {
    if (is_simple_enough ())
      memmove (dst, src, sizeof (T) * n);
    else
      while (n--)
        new (dst + n) T (*(src + n));
  }

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

  void ins (iterator where, size_type n)
  {
    if (_last + n <= _size)
      copy_higher (where + n, where, end () - where);
    else
      {
        size_type sz = _last + n;
        sz = good_size (sz);
        T *nbuf = alloc (sz);

        if (_buf)
          {
            copy (nbuf, begin (), where - begin ());
            copy (nbuf + (where - begin ()) + n, where, end () - where);
            dealloc ();
          }

        _buf = nbuf;
        _size = sz;
      }
  }

public:
  void reserve (size_type sz)
  {
    if (_size < sz)
      {
        sz = good_size (sz);
        T *nbuf = alloc (sz);

        if (_buf)
          {
            copy (nbuf, begin (), _last);
            dealloc ();
          }

        _buf = nbuf;
        _size = sz;
      }
  }

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

    if (is_simple_enough ())
      _last = sz;
    else
      {
        while (_last < sz)
          new (_buf + _last++) T ();
        while (_last > sz)
          _buf [--_last].~T ();
      }
  }

  simplevec ()
  : _last(0), _size(0), _buf(0)
  {
  }

  simplevec (size_type n, const T& t = T ())
  : _last(0), _size(0), _buf(0)
  {
    insert (begin (), n, t);
  }

  simplevec (const_iterator first, const_iterator last)
  : _last(0), _size(0), _buf(0)
  {
    insert (begin (), first, last);
  }

  simplevec (const simplevec<T> &v)
  : _last(0), _size(0), _buf(0)
  {
    insert (begin (), v.begin (), v.end ());
  }

  simplevec<T> &operator= (const simplevec<T> &v)
  {
    if (this != &v)
      {

        dealloc ();
        _size = 0;
        _buf  = 0;
        _last = 0;
        reserve (v._last);

        copy (_buf, v.begin (), v.size ());
        _last = v._last;
      }

    return *this;
  }

  ~simplevec ()
  {
    dealloc ();
  }

  const T &front () const { return _buf[      0]; }
        T &front ()       { return _buf[      0]; }
  const T &back  () const { return _buf[_last-1]; }
        T &back  ()       { return _buf[_last-1]; }

  bool empty () const
  {
    return _last == 0;
  }

  void clear ()
  {
    _last = 0;
  }

  void push_back (const T &t)
  {
    reserve (_last + 1);
    new (_buf + _last++) T (t);
  }

  void pop_back ()
  {
    --_last;
  }

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

  iterator insert (iterator pos, const T &t)
  {
    size_type at = pos - begin ();
    ins (pos, 1);
    pos = begin () + at;
    *pos = t;
    ++_last;
    return pos;
  }

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

    if (n > 0)
      {
        ins (pos, n);
        _last += n;
        copy (pos, first, n);
      }

    return pos;
  }

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

    if (n > 0)
      {
        ins (pos, n);
        pos = begin () + at;
        for (size_type i = 0; i < n; ++i)
          pos[i] = t;
        _last += n;
      }

    return pos;
  }

  void erase (iterator first, iterator last)
  {
    if (last != first)
      {
        if (!is_simple_enough ())
          for (iterator i = first; i < last; ++i)
            i->~T ();

        copy_lower (last, first, end () - last);

        _last -= last - first;
      }
  }

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

  void swap (simplevec<T> &t)
  {
    ::swap (_last, t._last);
    ::swap (_size, t._size);
    ::swap (_buf , t._buf );
  }
};

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.8
Committed:	Fri May 18 00:10:51 2012 UTC (12 years, 2 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.7:	+109 -42 lines
Log Message:	preliminary
#	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	sf-exg	1.5	template<typename T, typename U> static inline T min (T a, U b) { return a < (T)b ? a : (T)b; }
8			template<typename T, typename U> static inline T max (T a, U b) { return a > (T)b ? a : (T)b; }
9	sf-exg	1.1
10	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; }
11	sf-exg	1.1
12			template <typename I, typename T>
13			I find (I first, I last, const T& value)
14			{
15			while (first != last && *first != value)
16			++first;
17
18			return first;
19			}
20
21	root	1.8	// 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>
31
32			#if __cplusplus >= 201103L
33			#include <type_traits>
34			#endif
35
36	sf-exg	1.1	/* simplevec taken (and heavily modified), from:
37			*
38			* MICO --- a free CORBA implementation
39			* Copyright (C) 1997-98 Kay Roemer & Arno Puder
40	root	1.3	* originally GPLv2 or any later
41	sf-exg	1.1	*/
42			template<class T>
43			struct simplevec
44			{
45	root	1.3	typedef T *iterator;
46			typedef const T *const_iterator;
47			typedef unsigned long size_type;
48	sf-exg	1.1
49	root	1.8	static bool is_simple_enough ()
50			{
51			#if __cplusplus >= 201103L
52			return std::is_trivially_assignable<T, T>::value
53			&& std::is_trivially_constructable<T>::value
54			&& std::is_trivially_copyable<T>::value
55			&& std::is_trivially_destructible<T>::value;
56			#elif ECB_GCC_VERSION(4,4)
57			return __has_trivial_assign (T)
58			&& __has_trivial_constructor (T)
59			&& __has_trivial_copy (T)
60			&& __has_trivial_destructor (T);
61			#else
62			return 0;
63			#endif
64			}
65
66	sf-exg	1.1	private:
67	root	1.3	size_type _last, _size;
68			T *_buf;
69	sf-exg	1.1
70			public:
71	root	1.3	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	sf-exg	1.1
80			private:
81	root	1.3	static T *alloc (size_type n)
82			{
83			return (T )::operator new ((size_t) (n sizeof (T)));
84			}
85
86	root	1.8	void dealloc ()
87	root	1.3	{
88	root	1.8	if (!is_simple_enough ())
89			for (size_type i = 0; i < _last; ++i)
90			_buf [i].~T ();
91
92			::operator delete (_buf);
93	root	1.3	}
94
95			size_type good_size (size_type n)
96			{
97			return max (n, _size ? _size * 2 : 5);
98			}
99
100	root	1.8	// 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--)
107			new (dst++) T (*src++);
108			}
109
110			static void copy_higher (iterator dst, iterator src, size_type n)
111			{
112			if (is_simple_enough ())
113			memmove (dst, src, sizeof (T) * n);
114			else
115			while (n--)
116			new (dst + n) T (*(src + n));
117			}
118
119			static void copy (iterator dst, iterator src, size_type n)
120			{
121			if (is_simple_enough ())
122			memcpy (dst, src, sizeof (T) * n);
123			else
124			copy_lower (dst, src, n);
125			}
126
127			void ins (iterator where, size_type n)
128	root	1.3	{
129			if (_last + n <= _size)
130	root	1.8	copy_higher (where + n, where, end () - where);
131	root	1.3	else
132			{
133			size_type sz = _last + n;
134			sz = good_size (sz);
135			T *nbuf = alloc (sz);
136
137			if (_buf)
138			{
139	root	1.8	copy (nbuf, begin (), where - begin ());
140			copy (nbuf + (where - begin ()) + n, where, end () - where);
141			dealloc ();
142	root	1.3	}
143
144			_buf = nbuf;
145			_size = sz;
146			}
147			}
148	sf-exg	1.1
149			public:
150	root	1.3	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	root	1.8	copy (nbuf, begin (), _last);
160			dealloc ();
161	root	1.3	}
162
163			_buf = nbuf;
164			_size = sz;
165			}
166			}
167
168	root	1.7	void resize (size_type sz)
169			{
170			reserve (sz);
171	root	1.8
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	root	1.7	}
182
183	root	1.3	simplevec ()
184			: _last(0), _size(0), _buf(0)
185			{
186			}
187
188			simplevec (size_type n, const T& t = T ())
189			: _last(0), _size(0), _buf(0)
190			{
191			insert (begin (), n, t);
192			}
193
194			simplevec (const_iterator first, const_iterator last)
195			: _last(0), _size(0), _buf(0)
196			{
197			insert (begin (), first, last);
198			}
199
200			simplevec (const simplevec<T> &v)
201			: _last(0), _size(0), _buf(0)
202			{
203	root	1.8	insert (begin (), v.begin (), v.end ());
204	root	1.3	}
205
206			simplevec<T> &operator= (const simplevec<T> &v)
207			{
208			if (this != &v)
209			{
210	root	1.8
211			dealloc ();
212			_size = 0;
213			_buf = 0;
214	root	1.3	_last = 0;
215	sf-exg	1.1	reserve (v._last);
216	root	1.8
217			copy (_buf, v.begin (), v.size ());
218	sf-exg	1.1	_last = v._last;
219	root	1.3	}
220
221			return *this;
222			}
223
224			~simplevec ()
225			{
226	root	1.8	dealloc ();
227	root	1.3	}
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	root	1.8	reserve (_last + 1);
247			new (_buf + _last++) T (t);
248	root	1.3	}
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)
259			{
260	root	1.8	size_type at = pos - begin ();
261			ins (pos, 1);
262	root	1.3	pos = begin () + at;
263			*pos = t;
264			++_last;
265			return pos;
266			}
267
268			iterator insert (iterator pos, const_iterator first, const_iterator last)
269			{
270	root	1.8	size_type n = last - first;
271			size_type at = pos - begin ();
272	root	1.3
273			if (n > 0)
274			{
275	root	1.8	ins (pos, n);
276	root	1.3	_last += n;
277	root	1.8	copy (pos, first, n);
278	root	1.3	}
279
280			return pos;
281			}
282
283			iterator insert (iterator pos, size_type n, const T &t)
284			{
285	root	1.8	size_type at = pos - begin ();
286	root	1.3
287			if (n > 0)
288			{
289	root	1.8	ins (pos, n);
290	root	1.3	pos = begin () + at;
291	root	1.8	for (size_type i = 0; i < n; ++i)
292	root	1.3	pos[i] = t;
293			_last += n;
294			}
295
296			return pos;
297			}
298
299			void erase (iterator first, iterator last)
300			{
301			if (last != first)
302			{
303	root	1.8	if (!is_simple_enough ())
304			for (iterator i = first; i < last; ++i)
305			i->~T ();
306
307			copy_lower (last, first, end () - last);
308
309	root	1.3	_last -= last - first;
310			}
311			}
312
313			void erase (iterator pos)
314			{
315			if (pos != end ())
316	root	1.8	erase (pos, pos + 1);
317	root	1.3	}
318
319			void swap (simplevec<T> &t)
320			{
321	sf-exg	1.5	::swap (_last, t._last);
322			::swap (_size, t._size);
323	root	1.8	::swap (_buf , t._buf );
324	root	1.3	}
325	sf-exg	1.1	};
326
327			template<class T>
328	root	1.3	bool operator ==(const simplevec<T> &v1, const simplevec<T> &v2)
329	sf-exg	1.1	{
330	root	1.3	if (v1.size () != v2.size ()) return false;
331
332			return !v1.size () \|\| !memcmp (&v1[0], &v2[0], v1.size () * sizeof (T));
333	sf-exg	1.1	}
334
335			template<class T>
336	root	1.3	bool operator <(const simplevec<T> &v1, const simplevec<T> &v2)
337	sf-exg	1.1	{
338	root	1.3	unsigned long minlast = min (v1.size (), v2.size ());
339
340			for (unsigned long i = 0; i < minlast; ++i)
341			{
342			if (v1[i] < v2[i]) return true;
343			if (v2[i] < v1[i]) return false;
344	sf-exg	1.1	}
345	root	1.3	return v1.size () < v2.size ();
346	sf-exg	1.1	}
347
348			template<typename T>
349			struct vector : simplevec<T>
350			{
351			};
352	sf-exg	1.2
353			#endif
354	root	1.3