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 __cplusplus >= 201103L
  #include <type_traits>
#endif

// 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
{
#if ESTL_BIG_VECTOR
  // shoudl 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

  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 ()
  {
    return 1; // we are not there yet
    #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
  }

  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 ; }

  template<class I>
  static void copy_lower (iterator dst, I        src, size_type n, void (*op)(iterator, I       ) = cop_new)
  {
    while (n--)
      op (dst++, src++);
  }

  static void copy_lower (iterator dst, iterator src, size_type n, void (*op)(iterator, iterator) = cop_new)
  {
    if (is_simple_enough ())
      memmove (dst, src, sizeof (T) * n);
    else
      copy_lower<iterator> (dst, src, n, cop_new);
  }

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

  template<class I>
  static void copy (iterator dst, I        src, size_type n, void (*op)(iterator,        I) = cop_new)
  {
    copy_lower<I> (dst, src, n, op);
  }

  static void copy (iterator dst, iterator src, size_type n, void (*op)(iterator, iterator) = cop_new)
  {
    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);
    copy_higher (buf + pos + n, buf + pos, sze - pos, cop_set);
    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);
    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);
  }

  template<class I>
  simplevec (I first, I last)
  {
    sze = res = last - first;
    buf = alloc (sze);
    copy (buf, first, sze);
  }

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

  ~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]; }

  template<class I>
  void assign (I first, I last)
  {
    swap (simplevec<T> (first, last));
  }

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

  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;
  }

  template<class I>
  iterator insert (iterator pos, I first, I 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;
  }

  void erase (iterator first, iterator last)
  {
    size_t n = last - first;

    copy_lower (last, first, end () - last, cop_set);
    sze -= n;
    destruct (buf + sze, n);
  }

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

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.12
Committed:	Sat May 19 01:57:09 2012 UTC (12 years, 2 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.11:	+2 -1 lines
Log Message:	schmorp was here, and bloated urxvt
#	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			#if __cplusplus >= 201103L
26			#include <type_traits>
27			#endif
28
29	root	1.9	// original version taken from MICO, but this has been completely rewritten
30			// known limitations w.r.t. std::vector
31			// - many methods missing
32	root	1.12	// - no error checking, no exceptions thrown (e.g. at())
33	root	1.9	// - 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
37	root	1.12	// - no bool specialisation
38	sf-exg	1.1	template<class T>
39			struct simplevec
40			{
41	root	1.9	#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;
51			typedef T *iterator;
52	root	1.3	typedef const T *const_iterator;
53	root	1.9	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
59
60			private:
61			size_type sze, res;
62			T *buf;
63	sf-exg	1.1
64	root	1.9	// we shamelessly optimise for "simple" types. everything
65			// "not simple enough" will use the slow path.
66	root	1.8	static bool is_simple_enough ()
67			{
68	root	1.9	return 1; // we are not there yet
69	root	1.8	#if __cplusplus >= 201103L
70			return std::is_trivially_assignable<T, T>::value
71			&& std::is_trivially_constructable<T>::value
72			&& std::is_trivially_copyable<T>::value
73			&& std::is_trivially_destructible<T>::value;
74			#elif ECB_GCC_VERSION(4,4)
75			return __has_trivial_assign (T)
76			&& __has_trivial_constructor (T)
77			&& __has_trivial_copy (T)
78			&& __has_trivial_destructor (T);
79			#else
80			return 0;
81			#endif
82			}
83
84	root	1.9	static void construct (iterator a, size_type n = 1)
85	root	1.3	{
86	root	1.9	if (!is_simple_enough ())
87			while (n--)
88			new (*a++) T ();
89	root	1.3	}
90
91	root	1.9	static void destruct (iterator a, size_type n = 1)
92	root	1.3	{
93	root	1.8	if (!is_simple_enough ())
94	root	1.9	while (n--)
95			(*a++).~T ();
96	root	1.3	}
97
98	root	1.11	template<class I>
99			static void cop_new (iterator a, I b) { new (a) T (*b); }
100			template<class I>
101			static void cop_set (iterator a, I b) { a = b ; }
102
103			template<class I>
104			static void copy_lower (iterator dst, I src, size_type n, void (*op)(iterator, I ) = cop_new)
105			{
106			while (n--)
107			op (dst++, src++);
108			}
109	root	1.3
110	root	1.9	static void copy_lower (iterator dst, iterator src, size_type n, void (*op)(iterator, iterator) = cop_new)
111	root	1.8	{
112			if (is_simple_enough ())
113			memmove (dst, src, sizeof (T) * n);
114			else
115	root	1.11	copy_lower<iterator> (dst, src, n, cop_new);
116	root	1.8	}
117
118	root	1.9	static void copy_higher (iterator dst, iterator src, size_type n, void (*op)(iterator, iterator) = cop_new)
119	root	1.8	{
120			if (is_simple_enough ())
121			memmove (dst, src, sizeof (T) * n);
122			else
123			while (n--)
124	root	1.9	op (dst + n, src + n);
125	root	1.8	}
126
127	root	1.11	template<class I>
128			static void copy (iterator dst, I src, size_type n, void (*op)(iterator, I) = cop_new)
129			{
130			copy_lower<I> (dst, src, n, op);
131			}
132
133	root	1.9	static void copy (iterator dst, iterator src, size_type n, void (*op)(iterator, iterator) = cop_new)
134	root	1.8	{
135			if (is_simple_enough ())
136			memcpy (dst, src, sizeof (T) * n);
137			else
138	root	1.11	copy<iterator> (dst, src, n, op);
139	root	1.9	}
140
141			static T *alloc (size_type n) ecb_cold
142			{
143			return (T )::operator new ((size_t) (sizeof (T) n));
144			}
145
146			void dealloc () ecb_cold
147			{
148			destruct (buf, sze);
149			::operator delete (buf);
150			}
151
152			size_type good_size (size_type n) ecb_cold
153			{
154			return n ? 2UL << ecb_ld32 (n) : 5;
155	root	1.8	}
156
157			void ins (iterator where, size_type n)
158	root	1.3	{
159	root	1.9	size_type pos = where - begin ();
160
161			if (ecb_expect_false (sze + n > res))
162	root	1.3	{
163	root	1.9	res = good_size (sze + n);
164	root	1.3
165	root	1.9	T *nbuf = alloc (res);
166			copy (nbuf, buf, sze, cop_new);
167			dealloc ();
168			buf = nbuf;
169	root	1.3	}
170	root	1.9
171			construct (buf + sze, n);
172			copy_higher (buf + pos + n, buf + pos, sze - pos, cop_set);
173			sze += n;
174	root	1.3	}
175	sf-exg	1.1
176			public:
177	root	1.9	size_type capacity () const { return res; }
178			size_type size () const { return sze; }
179			bool empty () const { return size () == 0; }
180
181	root	1.11	size_t max_size () const
182			{
183			return (~(size_type)0) >> 1;
184			}
185
186	root	1.9	const_iterator begin () const { return &buf [ 0]; }
187			iterator begin () { return &buf [ 0]; }
188			const_iterator end () const { return &buf [sze ]; }
189			iterator end () { return &buf [sze ]; }
190			const_reference front () const { return buf [ 0]; }
191			reference front () { return buf [ 0]; }
192			const_reference back () const { return buf [sze - 1]; }
193			reference back () { return buf [sze - 1]; }
194
195	root	1.3	void reserve (size_type sz)
196			{
197	root	1.9	if (ecb_expect_true (sz <= res))
198			return;
199	root	1.3
200	root	1.9	sz = good_size (sz);
201			T *nbuf = alloc (sz);
202	root	1.3
203	root	1.9	copy (nbuf, begin (), sze);
204			dealloc ();
205
206			buf = nbuf;
207			res = sz;
208	root	1.3	}
209
210	root	1.7	void resize (size_type sz)
211			{
212			reserve (sz);
213	root	1.8
214			if (is_simple_enough ())
215	root	1.9	sze = sz;
216	root	1.8	else
217			{
218	root	1.9	while (sze < sz) construct (buf + sze++);
219			while (sze > sz) destruct (buf + --sze);
220	root	1.8	}
221	root	1.7	}
222
223	root	1.3	simplevec ()
224	root	1.9	: sze(0), res(0), buf(0)
225	root	1.3	{
226			}
227
228	root	1.9	simplevec (size_type n, const T &t = T ())
229	root	1.3	{
230	root	1.11	sze = res = n;
231			buf = alloc (sze);
232
233			while (n--)
234			new (buf + n) T (t);
235	root	1.3	}
236
237	root	1.11	template<class I>
238			simplevec (I first, I last)
239	root	1.3	{
240	root	1.11	sze = res = last - first;
241			buf = alloc (sze);
242			copy (buf, first, sze);
243	root	1.3	}
244
245			simplevec (const simplevec<T> &v)
246	root	1.9	: sze(0), res(0), buf(0)
247	root	1.3	{
248	root	1.11	sze = res = v.size ();
249			buf = alloc (sze);
250			copy (buf, v.begin (), sze);
251	root	1.3	}
252
253			~simplevec ()
254			{
255	root	1.8	dealloc ();
256	root	1.3	}
257
258	root	1.9	void swap (simplevec<T> &t)
259	root	1.3	{
260	root	1.9	::swap (sze, t.sze);
261			::swap (res, t.res);
262			::swap (buf, t.buf);
263	root	1.3	}
264
265			void clear ()
266			{
267	root	1.9	destruct (buf, sze);
268			sze = 0;
269	root	1.3	}
270
271			void push_back (const T &t)
272			{
273	root	1.9	reserve (sze + 1);
274			new (buf + sze++) T (t);
275	root	1.3	}
276
277			void pop_back ()
278			{
279	root	1.9	destruct (buf + --sze);
280	root	1.3	}
281
282	root	1.11	const_reference operator [](size_type idx) const { return buf[idx]; }
283			reference operator [](size_type idx) { return buf[idx]; }
284
285			const_reference at (size_type idx) const { return buf [idx]; }
286			reference at (size_type idx) { return buf [idx]; }
287
288			template<class I>
289			void assign (I first, I last)
290			{
291			swap (simplevec<T> (first, last));
292			}
293
294			void assign (size_type n, const T &t)
295			{
296			swap (simplevec<T> (n, t));
297			}
298
299			simplevec<T> &operator= (const simplevec<T> &v)
300			{
301			assign (v.begin (), v.end ());
302			return *this;
303			}
304	root	1.3
305			iterator insert (iterator pos, const T &t)
306			{
307	root	1.8	size_type at = pos - begin ();
308	root	1.10
309	root	1.8	ins (pos, 1);
310	root	1.10	buf [at] = t;
311
312			return buf + at;
313	root	1.3	}
314
315	root	1.11	template<class I>
316			iterator insert (iterator pos, I first, I last)
317	root	1.3	{
318	root	1.8	size_type n = last - first;
319			size_type at = pos - begin ();
320	root	1.3
321	root	1.9	ins (pos, n);
322	root	1.10	copy (buf + at, first, n, cop_set);
323	root	1.3
324	root	1.10	return buf + at;
325	root	1.3	}
326
327			iterator insert (iterator pos, size_type n, const T &t)
328			{
329	root	1.8	size_type at = pos - begin ();
330	root	1.3
331	root	1.9	ins (pos, n);
332
333	root	1.10	for (iterator i = buf + at; n--; )
334			*i++ = t;
335	root	1.3
336	root	1.10	return buf + at;
337	root	1.3	}
338
339			void erase (iterator first, iterator last)
340			{
341	root	1.9	size_t n = last - first;
342	root	1.8
343	root	1.9	copy_lower (last, first, end () - last, cop_set);
344			sze -= n;
345			destruct (buf + sze, n);
346	root	1.3	}
347
348			void erase (iterator pos)
349			{
350			if (pos != end ())
351	root	1.8	erase (pos, pos + 1);
352	root	1.3	}
353	sf-exg	1.1	};
354
355			template<class T>
356	root	1.3	bool operator ==(const simplevec<T> &v1, const simplevec<T> &v2)
357	sf-exg	1.1	{
358	root	1.3	if (v1.size () != v2.size ()) return false;
359
360			return !v1.size () \|\| !memcmp (&v1[0], &v2[0], v1.size () * sizeof (T));
361	sf-exg	1.1	}
362
363			template<class T>
364	root	1.3	bool operator <(const simplevec<T> &v1, const simplevec<T> &v2)
365	sf-exg	1.1	{
366	root	1.3	unsigned long minlast = min (v1.size (), v2.size ());
367
368			for (unsigned long i = 0; i < minlast; ++i)
369			{
370			if (v1[i] < v2[i]) return true;
371			if (v2[i] < v1[i]) return false;
372	sf-exg	1.1	}
373	root	1.3	return v1.size () < v2.size ();
374	sf-exg	1.1	}
375
376			template<typename T>
377			struct vector : simplevec<T>
378			{
379			};
380	sf-exg	1.2
381			#endif
382	root	1.3