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
// - 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
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 ();
  }

  static void cop_new (iterator a, iterator b) { new (a) T (*b); }
  static void cop_set (iterator a, iterator b) {     *a  =  *b ; }

  // these copy helpers actually use the copy constructor, not assignment
  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
      while (n--)
        op (dst++, src++);
  }

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

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

  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(0), res(0), buf(0)
  {
    insert (begin (), n, t);
  }

  simplevec (const_iterator first, const_iterator last)
  : sze(0), res(0), buf(0)
  {
    insert (begin (), first, last);
  }

  simplevec (const simplevec<T> &v)
  : sze(0), res(0), buf(0)
  {
    insert (begin (), v.begin (), v.end ());
  }

  simplevec<T> &operator= (const simplevec<T> &v)
  {
    swap (simplevec<T> (v));
    return *this;
  }

  ~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 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);
    buf [pos] = t;
    return pos;
  }

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

    ins (pos, n);
    copy (pos, first, n, cop_set);

    return pos;
  }

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

    ins (pos, n);

    for (size_type i = 0; i < n; ++i)
      buf [at + i] = t;

    return pos;
  }

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