PikaScript
QStrings.h
1 
50 #ifndef QStrings_h
51 #define QStrings_h
52 
53 #include <stdlib.h>
54 #include <string.h>
55 #include <stddef.h>
56 #include <wchar.h>
57 #include <string>
58 #include <algorithm>
59 #include <limits>
60 #include "assert.h"
61 
62 namespace QStrings {
63 
64 /* --- Declaration --- */
65 
66 // TODO : documentation
67 template<typename C, size_t PS = (64 - 12)> class QString {
68  public: enum { npos = 0x7FFFFFFF };
69  public: typedef size_t size_type;
70  public: typedef C value_type;
71  public: template<typename E, class Q> class _iterator;
72  public: typedef _iterator<C, QString<C, PS> > iterator;
74  public: class Buffer;
75  public: typedef std::reverse_iterator<iterator> reverse_iterator;
76  public: typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
77  public: static void deinit() throw();
78  public: template<size_t N> QString(const C (&s)[N]);
79  public: QString();
80  public: QString(const QString& copy);
81  public: QString(C* s);
82  public: QString(size_type n, C c);
83  public: QString(const C* b, size_type l, size_type extra = 0);
84  public: QString(const_iterator b, const_iterator e);
85  public: QString(const C* b, const C* e);
86  public: QString(const std::basic_string<C>& copy);
87  public: QString(const QString& copy, size_type offset, size_type count);
88  public: QString& operator=(const QString& copy);
89  public: C operator[](size_type index) const;
90  public: QString& operator+=(const QString& s);
91  public: QString operator+(const QString& s) const;
92  public: template<size_t N> QString& operator+=(const C (&s)[N]);
93  public: template<size_t N> QString operator+(const C (&s)[N]) const;
94  public: QString& operator+=(C c);
95  public: QString operator+(C c) const;
96  public: size_type size() const;
97  public: bool empty() const;
98  public: const C* data() const;
99  public: const C* c_str() const;
100  public: QString substr(size_type offset, size_type count = npos) const;
101  public: ~QString() throw();
102  public: bool operator<(const QString& r) const;
103  public: bool operator<=(const QString& r) const;
104  public: bool operator==(const QString& r) const;
105  public: bool operator!=(const QString& r) const;
106  public: bool operator>=(const QString& r) const;
107  public: bool operator>(const QString& r) const;
108  public: const_iterator begin() const { return const_iterator(pointer, this); }
109  public: const_iterator end() const { return const_iterator(pointer + length, this); }
110  public: iterator begin() { unshare(); return iterator(pointer, this); }
111  public: iterator end() { unshare(); return iterator(pointer + length, this); }
112  public: const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
113  public: const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
114  public: reverse_iterator rbegin() { unshare(); return reverse_iterator(end()); }
115  public: reverse_iterator rend() { unshare(); return reverse_iterator(begin()); }
116  public: operator std::basic_string<C>() const { return std::basic_string<C>(pointer, length); }
117  protected: void newBuffer(size_type l, const C* b, size_type extra = 0);
118  protected: QString& append(const C* p, typename QString<C, PS>::size_type l);
119  protected: QString concat(const C* p, typename QString<C, PS>::size_type l) const;
120  protected: void unshare() const;
121  protected: void retain() const throw();
122  protected: void release() throw();
123  protected: static void copychars(C* d, const C* s, size_t l);
124  protected: C* pointer;
125  protected: size_type length;
126  protected: Buffer* buffer;
127  protected: static Buffer* obtainDummyBuffer();
128 };
129 
130 /* --- Implementation --- */
131 
132 template<> inline void QString<char>::copychars(char* d, const char* s, size_t l) { memcpy(d, s, l); }
133 template<> inline void QString<wchar_t>::copychars(wchar_t* d, const wchar_t* s, size_t l) { wmemcpy(d, s, l); }
134 
135 template<typename C, size_t PS> class QString<C, PS>::Buffer {
136  friend class QString<C, PS>;
137  protected: static Buffer*& obtainPoolHead() { static Buffer* poolHead; return poolHead; }
138 
139  public: Buffer(size_type n) : rc(1), size(n > PS ? n : PS), chars(n > PS ? new C[n] : internal) { };
140  public: ~Buffer() { if (chars != internal) delete [] chars; }
141 
142  public: static void* operator new(size_t count) {
143  assert(count == sizeof (Buffer));
144  Buffer* h = obtainPoolHead();
145  if (h == 0) h = reinterpret_cast<Buffer*>(::operator new(count));
146  else obtainPoolHead() = obtainPoolHead()->next;
147  return h;
148  }
149 
150  public: static void operator delete(void* pointer) throw() {
151  Buffer* h = reinterpret_cast<Buffer*>(pointer);
152  h->next = obtainPoolHead();
153  obtainPoolHead() = h;
154  }
155 
156  public: static void cleanPool() throw() {
157  while (obtainPoolHead() != 0) {
158  Buffer* h = obtainPoolHead();
159  obtainPoolHead() = h->next;
160  ::operator delete(h);
161  }
162  }
163 
164  protected: union {
165  struct {
166  C internal[PS];
167  int rc;
168  size_type size;
169  C* chars;
170  };
171  Buffer* next;
172  };
173 };
174 
175 template<typename C, size_t PS> void QString<C, PS>::retain() const throw() { ++buffer->rc; }
176 template<typename C, size_t PS> void QString<C, PS>::deinit() throw() { Buffer::cleanPool(); }
177 template<typename C, size_t PS> typename QString<C, PS>::size_type QString<C, PS>::size() const { return length; }
178 template<typename C, size_t PS> bool QString<C, PS>::empty() const { return (length == 0); }
179 template<typename C, size_t PS> const C* QString<C, PS>::data() const { return pointer; }
180 
181 template<typename C, size_t PS> template<typename E, class Q> class QString<C, PS>::_iterator
182  : public std::iterator<std::random_access_iterator_tag, E> { // FIX : is there some good base-class for this in STL?
183  friend class QString;
184  public: _iterator() : p(0), s(0) { }
185  public: template<typename E2, class Q2> _iterator(const _iterator<E2, Q2>& copy) : p(copy.p), s(copy.s) { }
186  protected: explicit _iterator(E* p, Q* s) : p(p), s(s) { }
187  public: friend _iterator operator+(const _iterator& it, ptrdiff_t d) { return _iterator(it.p + d, it.s); }
188  public: friend _iterator operator+(ptrdiff_t d, const _iterator& it) { return _iterator(it.p + d, it.s); }
189  public: friend _iterator operator-(const _iterator& it, ptrdiff_t d) { return _iterator(it.p - d, it.s); }
190  public: friend ptrdiff_t operator-(const _iterator& a, const _iterator& b) {
191  assert(a.s == b.s);
192  return a.p - b.p;
193  }
194  public: _iterator& operator+=(ptrdiff_t d) { p += d; return (*this); }
195  public: _iterator& operator-=(ptrdiff_t d) { p -= d; return (*this); }
196  public: _iterator& operator++() { ++p; return (*this); }
197  public: _iterator& operator--() { --p; return (*this); }
198  public: const _iterator operator++(int) { _iterator copy(*this); ++p; return copy; }
199  public: const _iterator operator--(int) { _iterator copy(*this); --p; return copy; }
200  public: template<typename E2, class Q2> _iterator& operator=(const _iterator<E2, Q2>& copy) {
201  p = copy.p;
202  s = copy.s;
203  return (*this);
204  }
205  public: template<typename E2, class Q2> bool operator<(const _iterator<E2, Q2>& r) const {
206  assert(r.s == s);
207  return (p < r.p);
208  }
209  public: template<typename E2, class Q2> bool operator<=(const _iterator<E2, Q2>& r) const {
210  assert(r.s == s);
211  return (p <= r.p);
212  }
213  public: template<typename E2, class Q2> bool operator==(const _iterator<E2, Q2>& r) const { return (p == r.p); }
214  public: template<typename E2, class Q2> bool operator!=(const _iterator<E2, Q2>& r) const { return (p != r.p); }
215  public: template<typename E2, class Q2> bool operator>=(const _iterator<E2, Q2>& r) const {
216  assert(r.s == s);
217  return (p >= r.p);
218  }
219  public: template<typename E2, class Q2> bool operator>(const _iterator<E2, Q2>& r) const {
220  assert(r.s == s);
221  return (p > r.p);
222  }
223  public: E& operator*() const { assert(s->data() <= p && p < s->data() + s->size()); return *p; }
224  public: E& operator[](ptrdiff_t d) const { return *((*this) + d); }
225  public: E* p;
226  public: Q* s;
227 };
228 
229 template<typename C, size_t PS> template<size_t N> QString<C, PS>::QString(const C (&s)[N])
230  : pointer(const_cast<C*>(s)), length(N - 1), buffer(obtainDummyBuffer()) {
231  retain();
232 }
233 
234 template<typename C, size_t PS> QString<C, PS>::QString() : length(0), buffer(obtainDummyBuffer()) {
235  pointer = buffer->chars;
236  retain();
237 }
238 template<typename C, size_t PS> typename QString<C, PS>::Buffer* QString<C, PS>::obtainDummyBuffer() {
239  static typename QString<C, PS>::Buffer dummy(0);
240  return &dummy;
241 }
242 
243 template<typename C, size_t PS> void QString<C, PS>::release() throw() {
244  assert(buffer->rc >= 1);
245  if (--buffer->rc == 0) delete buffer;
246 }
247 
248 template<typename C, size_t PS> QString<C, PS>::~QString() throw() { release(); }
249 
250 template<typename C, size_t PS> void QString<C, PS>::newBuffer(size_type l, const C* b, size_type extra) {
251  assert(l == 0 || b != 0);
252  buffer = new Buffer(l + extra + 1);
253  pointer = buffer->chars;
254  length = l;
255  copychars(pointer, b, l);
256  pointer[length] = 0;
257 }
258 
259 template<typename C, size_t PS> QString<C, PS>::QString(C* s) {
260  assert(s != 0);
261  newBuffer(std::char_traits<C>::length(s), s);
262 }
263 
264 template<typename C, size_t PS> QString<C, PS>::QString(const C* b, size_type l, size_type extra) {
265  assert(b != 0);
266  newBuffer(l, b, extra);
267 }
268 
269 template<typename C, size_t PS> QString<C, PS>::QString(size_type n, C c) {
270  newBuffer(0, 0, n);
271  std::fill_n(pointer, n, c);
272  length = n;
273 }
274 
275 template<typename C, size_t PS> QString<C, PS>::QString(const QString& copy)
276  : pointer(copy.pointer), length(copy.length), buffer(copy.buffer) {
277  retain();
278 }
279 
280 template<typename C, size_t PS> QString<C, PS>::QString(const_iterator b, const_iterator e)
281  : pointer(const_cast<C*>(b.p)), length(e.p - b.p), buffer(b.s->buffer) {
282  assert(b.s->begin() <= b && b <= b.s->end());
283  assert(b <= e && e <= b.s->end());
284  retain();
285 }
286 
287 template<typename C, size_t PS> QString<C, PS>::QString(const C* b, const C* e) {
288  assert(b != 0);
289  assert(e != 0);
290  assert(b <= e);
291  newBuffer(e - b, b);
292 }
293 
294 template<typename C, size_t PS> QString<C, PS>::QString(const std::basic_string<C>& copy) {
295  newBuffer(copy.size(), copy.data());
296 }
297 
298 template<typename C, size_t PS> QString<C, PS>::QString(const QString& copy, size_type offset, size_type count)
299  : pointer(copy.pointer + offset), length(count < copy.length - offset ? count : copy.length - offset), buffer(copy.buffer) {
300  assert((!std::numeric_limits<size_type>::is_signed || offset >= 0) && offset <= copy.length);
301  retain();
302 }
303 
304 template<typename C, size_t PS> QString<C, PS>& QString<C, PS>::operator=(const QString<C, PS>& copy) {
305  copy.retain();
306  this->release();
307  this->pointer = copy.pointer;
308  this->length = copy.length;
309  this->buffer = copy.buffer;
310  return (*this);
311 }
312 
313 template<typename C, size_t PS> QString<C, PS>& QString<C, PS>::append(const C* p, size_type l) {
314  assert(p != 0);
315  bool fit = (pointer + length + l < buffer->chars + buffer->size);
316  if (buffer->rc != 1 && fit && memcmp(pointer + length, p, l) == 0) {
317  length += l;
318  return (*this);
319  }
320  if (buffer->rc != 1 || !fit)
321  (*this) = QString(pointer, length, l + (length < 65536 ? length : 65536)); // FIX : constant
322 
323  copychars(pointer + length, p, l);
324  length += l;
325  assert(buffer->rc == 1);
326  pointer[length] = 0;
327  return (*this);
328 }
329 
330 template<typename C, size_t PS> QString<C, PS> QString<C, PS>::concat(const C* p, size_type l) const {
331  assert(p != 0);
332  QString copy(pointer, length, l + (l < size_type(65536) ? l : size_type(65536)));
333  copychars(copy.pointer + copy.length, p, l);
334  copy.length += l;
335  assert(copy.buffer->rc == 1);
336  copy.pointer[copy.length] = 0;
337  return copy;
338 }
339 
340 template<typename C, size_t PS> QString<C, PS>& QString<C, PS>::operator+=(const QString<C, PS>& s) {
341  return (length == 0) ? (*this = s) : append(s.pointer, s.length);
342 }
343 
344 template<typename C, size_t PS> QString<C, PS> QString<C, PS>::operator+(const QString<C, PS>& s) const {
345  return (length == 0) ? s : concat(s.pointer, s.length);
346 }
347 
348 template<typename C, size_t PS> template<size_t N> QString<C, PS>& QString<C, PS>::operator+=(const C (&s)[N]) {
349  return append(s, N - 1);
350 }
351 
352 template<typename C, size_t PS> template<size_t N> QString<C, PS> QString<C, PS>::operator+(const C (&s)[N]) const {
353  return concat(s, N - 1);
354 }
355 
356 template<typename C, size_t PS> QString<C, PS>& QString<C, PS>::operator+=(C c) { return append(&c, 1); }
357 template<typename C, size_t PS> QString<C, PS> QString<C, PS>::operator+(C c) const { return concat(&c, 1); }
358 
359 template<typename C, size_t PS> void QString<C, PS>::unshare() const {
360  if (buffer->rc != 1) *const_cast<QString<C, PS>*>(this) = QString(pointer, length);
361 }
362 
363 template<typename C, size_t PS> const C* QString<C, PS>::c_str() const {
364  if (*(pointer + length) != 0) {
365  unshare();
366  *(pointer + length) = 0;
367  }
368  return pointer;
369 }
370 
371 template<typename C, size_t PS> QString<C, PS> QString<C, PS>::substr(size_type offset, size_type count) const {
372  return QString(*this, offset, count);
373 }
374 
375 template<typename C, size_t PS> C QString<C, PS>::operator[](size_type index) const {
376  assert((!std::numeric_limits<size_type>::is_signed || 0 <= index) && index <= length);
377  return (index == length) ? 0 : pointer[index];
378 }
379 
380 template<typename C, size_t PS> bool QString<C, PS>::operator<(const QString<C, PS>& r) const {
381  int d = (this->pointer == r.pointer ? 0 : std::char_traits<C>::compare
382  (this->pointer, r.pointer, (this->length < r.length ? this->length : r.length)));
383  return (d == 0 ? (this->length < r.length) : (d < 0));
384 }
385 
386 template<typename C, size_t PS> bool QString<C, PS>::operator<=(const QString<C, PS>& r) const {
387  int d = (this->pointer == r.pointer ? 0 : std::char_traits<C>::compare
388  (this->pointer, r.pointer, (this->length < r.length ? this->length : r.length)));
389  return (d == 0 ? (this->length <= r.length) : (d < 0));
390 }
391 
392 template<typename C, size_t PS> bool QString<C, PS>::operator==(const QString<C, PS>& r) const {
393  return (this->length == r.length && (this->pointer == r.pointer
394  || std::char_traits<C>::compare(this->pointer, r.pointer, this->length) == 0));
395 }
396 
397 template<typename C, size_t PS> bool QString<C, PS>::operator!=(const QString<C, PS>& r) const { return !(*this == r); }
398 template<typename C, size_t PS> bool QString<C, PS>::operator>=(const QString<C, PS>& r) const { return !(*this < r); }
399 template<typename C, size_t PS> bool QString<C, PS>::operator>(const QString<C, PS>& r) const { return !(*this <= r); }
400 
401 void unitTest();
402 
403 }
404 
405 #endif