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

  private:
    scoped_ptr (const scoped_ptr &);
    scoped_ptr &operator =(const scoped_ptr &);
  };

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

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

  private:
    scoped_array (const scoped_array &);
    scoped_array &operator =(const scoped_array &);
  };
}

// 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.29
Committed:	Thu Nov 13 13:58:12 2014 UTC (9 years, 7 months ago) by sf-exg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rel-1_8, rxvt-unicode-rel-9_26, rxvt-unicode-rel-9_25, rxvt-unicode-rel-9_22, rel-1_7, rxvt-unicode-rel-9_21
Changes since 1.28:	+8 -2 lines
Log Message:	* empty log message *
#	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 ECB_CPP11
26	#include <type_traits>
27	#endif
28
29	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	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
111	template<class T>
112	struct simplevec
113	{
114	typedef estl::size_type size_type;
115
116	typedef T value_type;
117	typedef T *iterator;
118	typedef const T *const_iterator;
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
125
126	private:
127	size_type sze, res;
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	}
225
226	public:
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
413	template<class T>
414	bool 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
421	template<class T>
422	bool 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)
427	{
428	if (v1[i] < v2[i]) return true;
429	if (v2[i] < v1[i]) return false;
430	}
431	return v1.size () < v2.size ();
432	}
433
434	template<typename T>
435	struct vector : simplevec<T>
436	{
437	};
438
439	#endif
440