rxvt-unicode/src/estl.h

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