[multiple changes]
[gcc.git] / libstdc++ / std / bastring.h
1 // Main templates for the -*- C++ -*- string classes.
2 // Copyright (C) 1994, 1995 Free Software Foundation
3
4 // This file is part of the GNU ANSI C++ Library. This library is free
5 // software; you can redistribute it and/or modify it under the
6 // terms of the GNU General Public License as published by the
7 // Free Software Foundation; either version 2, or (at your option)
8 // any later version.
9
10 // This library is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
14
15 // You should have received a copy of the GNU General Public License
16 // along with this library; see the file COPYING. If not, write to the Free
17 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18
19 // As a special exception, if you link this library with files
20 // compiled with a GNU compiler to produce an executable, this does not cause
21 // the resulting executable to be covered by the GNU General Public License.
22 // This exception does not however invalidate any other reasons why
23 // the executable file might be covered by the GNU General Public License.
24
25 // Written by Jason Merrill based upon the specification by Takanori Adachi
26 // in ANSI X3J16/94-0013R2.
27
28 #ifndef __BASTRING__
29 #define __BASTRING__
30
31 #ifdef __GNUG__
32 #pragma interface
33 #endif
34
35 #include <cstddef>
36 #include <std/straits.h>
37
38 // NOTE : This does NOT conform to the draft standard and is likely to change
39 #include <alloc.h>
40
41 extern "C++" {
42 class istream; class ostream;
43
44 #include <iterator>
45
46 #ifdef __STL_USE_EXCEPTIONS
47
48 extern void __out_of_range (const char *);
49 extern void __length_error (const char *);
50
51 #define OUTOFRANGE(cond) \
52 do { if (cond) __out_of_range (#cond); } while (0)
53 #define LENGTHERROR(cond) \
54 do { if (cond) __length_error (#cond); } while (0)
55
56 #else
57
58 #include <cassert>
59 #define OUTOFRANGE(cond) assert (!(cond))
60 #define LENGTHERROR(cond) assert (!(cond))
61
62 #endif
63
64 template <class charT, class traits = string_char_traits<charT>,
65 class Allocator = alloc >
66 class basic_string
67 {
68 private:
69 struct Rep {
70 size_t len, res, ref;
71 bool selfish;
72
73 charT* data () { return reinterpret_cast<charT *>(this + 1); }
74 charT& operator[] (size_t s) { return data () [s]; }
75 charT* grab () { if (selfish) return clone (); ++ref; return data (); }
76 void release () { if (--ref == 0) delete this; }
77
78 inline static void * operator new (size_t, size_t);
79 inline static void operator delete (void *);
80 inline static Rep* create (size_t);
81 charT* clone ();
82
83 inline void copy (size_t, const charT *, size_t);
84 inline void move (size_t, const charT *, size_t);
85 inline void set (size_t, const charT, size_t);
86
87 inline static bool excess_slop (size_t, size_t);
88 inline static size_t frob_size (size_t);
89
90 private:
91 Rep &operator= (const Rep &);
92 };
93
94 public:
95 // types:
96 typedef traits traits_type;
97 typedef typename traits::char_type value_type;
98 typedef Allocator allocator_type;
99
100 typedef size_t size_type;
101 typedef ptrdiff_t difference_type;
102 typedef charT& reference;
103 typedef const charT& const_reference;
104 typedef charT* pointer;
105 typedef const charT* const_pointer;
106 typedef pointer iterator;
107 typedef const_pointer const_iterator;
108 typedef ::reverse_iterator<iterator> reverse_iterator;
109 typedef ::reverse_iterator<const_iterator> const_reverse_iterator;
110 static const size_type npos = static_cast<size_type>(-1);
111
112 private:
113 Rep *rep () const { return reinterpret_cast<Rep *>(dat) - 1; }
114 void repup (Rep *p) { rep ()->release (); dat = p->data (); }
115
116 public:
117 const charT* data () const
118 { return rep ()->data(); }
119 size_type length () const
120 { return rep ()->len; }
121 size_type size () const
122 { return rep ()->len; }
123 size_type capacity () const
124 { return rep ()->res; }
125 size_type max_size () const
126 { return (npos - 1)/sizeof (charT); } // XXX
127 bool empty () const
128 { return size () == 0; }
129
130 // _lib.string.cons_ construct/copy/destroy:
131 basic_string& operator= (const basic_string& str)
132 {
133 if (&str != this) { rep ()->release (); dat = str.rep ()->grab (); }
134 return *this;
135 }
136
137 explicit basic_string (): dat (nilRep.grab ()) { }
138 basic_string (const basic_string& str): dat (str.rep ()->grab ()) { }
139 basic_string (const basic_string& str, size_type pos, size_type n = npos)
140 : dat (nilRep.grab ()) { assign (str, pos, n); }
141 basic_string (const charT* s, size_type n)
142 : dat (nilRep.grab ()) { assign (s, n); }
143 basic_string (const charT* s)
144 : dat (nilRep.grab ()) { assign (s); }
145 basic_string (size_type n, charT c)
146 : dat (nilRep.grab ()) { assign (n, c); }
147 #ifdef __STL_MEMBER_TEMPLATES
148 template<class InputIterator>
149 basic_string(InputIterator begin, InputIterator end)
150 #else
151 basic_string(const_iterator begin, const_iterator end)
152 #endif
153 : dat (nilRep.grab ()) { assign (begin, end); }
154
155 ~basic_string ()
156 { rep ()->release (); }
157
158 void swap (basic_string &s) { charT *d = dat; dat = s.dat; s.dat = d; }
159
160 basic_string& append (const basic_string& str, size_type pos = 0,
161 size_type n = npos)
162 { return replace (length (), 0, str, pos, n); }
163 basic_string& append (const charT* s, size_type n)
164 { return replace (length (), 0, s, n); }
165 basic_string& append (const charT* s)
166 { return append (s, traits::length (s)); }
167 basic_string& append (size_type n, charT c)
168 { return replace (length (), 0, n, c); }
169 #ifdef __STL_MEMBER_TEMPLATES
170 template<class InputIterator>
171 basic_string& append(InputIterator first, InputIterator last)
172 #else
173 basic_string& append(const_iterator first, const_iterator last)
174 #endif
175 { return replace (iend (), iend (), first, last); }
176
177 basic_string& assign (const basic_string& str, size_type pos = 0,
178 size_type n = npos)
179 { return replace (0, npos, str, pos, n); }
180 basic_string& assign (const charT* s, size_type n)
181 { return replace (0, npos, s, n); }
182 basic_string& assign (const charT* s)
183 { return assign (s, traits::length (s)); }
184 basic_string& assign (size_type n, charT c)
185 { return replace (0, npos, n, c); }
186 #ifdef __STL_MEMBER_TEMPLATES
187 template<class InputIterator>
188 basic_string& assign(InputIterator first, InputIterator last)
189 #else
190 basic_string& assign(const_iterator first, const_iterator last)
191 #endif
192 { return replace (ibegin (), iend (), first, last); }
193
194 basic_string& operator= (const charT* s)
195 { return assign (s); }
196 basic_string& operator= (charT c)
197 { return assign (1, c); }
198
199 basic_string& operator+= (const basic_string& rhs)
200 { return append (rhs); }
201 basic_string& operator+= (const charT* s)
202 { return append (s); }
203 basic_string& operator+= (charT c)
204 { return append (1, c); }
205
206 basic_string& insert (size_type pos1, const basic_string& str,
207 size_type pos2 = 0, size_type n = npos)
208 { return replace (pos1, 0, str, pos2, n); }
209 basic_string& insert (size_type pos, const charT* s, size_type n)
210 { return replace (pos, 0, s, n); }
211 basic_string& insert (size_type pos, const charT* s)
212 { return insert (pos, s, traits::length (s)); }
213 basic_string& insert (size_type pos, size_type n, charT c)
214 { return replace (pos, 0, n, c); }
215 iterator insert(iterator p, charT c)
216 { insert (p - ibegin (), 1, c); selfish (); return p; }
217 iterator insert(iterator p, size_type n, charT c)
218 { insert (p - ibegin (), n, c); selfish (); return p; }
219 #ifdef __STL_MEMBER_TEMPLATES
220 template<class InputIterator>
221 void insert(iterator p, InputIterator first, InputIterator last)
222 #else
223 void insert(iterator p, const_iterator first, const_iterator last)
224 #endif
225 { replace (p, p, first, last); }
226
227 basic_string& erase (size_type pos = 0, size_type n = npos)
228 { return replace (pos, n, (size_type)0, (charT)0); }
229 iterator erase(iterator p)
230 { replace (p-ibegin (), 1, (size_type)0, (charT)0); selfish (); return p; }
231 iterator erase(iterator f, iterator l)
232 { replace (f-ibegin (), l-f, (size_type)0, (charT)0);selfish ();return f; }
233
234 basic_string& replace (size_type pos1, size_type n1, const basic_string& str,
235 size_type pos2 = 0, size_type n2 = npos);
236 basic_string& replace (size_type pos, size_type n1, const charT* s,
237 size_type n2);
238 basic_string& replace (size_type pos, size_type n1, const charT* s)
239 { return replace (pos, n1, s, traits::length (s)); }
240 basic_string& replace (size_type pos, size_type n1, size_type n2, charT c);
241 basic_string& replace (size_type pos, size_type n, charT c)
242 { return replace (pos, n, 1, c); }
243 basic_string& replace (iterator i1, iterator i2, const basic_string& str)
244 { return replace (i1 - ibegin (), i2 - i1, str); }
245 basic_string& replace (iterator i1, iterator i2, const charT* s, size_type n)
246 { return replace (i1 - ibegin (), i2 - i1, s, n); }
247 basic_string& replace (iterator i1, iterator i2, const charT* s)
248 { return replace (i1 - ibegin (), i2 - i1, s); }
249 basic_string& replace (iterator i1, iterator i2, size_type n, charT c)
250 { return replace (i1 - ibegin (), i2 - i1, n, c); }
251 #ifdef __STL_MEMBER_TEMPLATES
252 template<class InputIterator>
253 basic_string& replace(iterator i1, iterator i2,
254 InputIterator j1, InputIterator j2);
255 #else
256 basic_string& replace(iterator i1, iterator i2,
257 const_iterator j1, const_iterator j2);
258 #endif
259
260 private:
261 static charT eos () { return traits::eos (); }
262 void unique () { if (rep ()->ref > 1) alloc (length (), true); }
263 void selfish () { unique (); rep ()->selfish = true; }
264
265 public:
266 charT operator[] (size_type pos) const
267 {
268 if (pos == length ())
269 return eos ();
270 return data ()[pos];
271 }
272
273 reference operator[] (size_type pos)
274 { selfish (); return (*rep ())[pos]; }
275
276 reference at (size_type pos)
277 {
278 OUTOFRANGE (pos >= length ());
279 return (*this)[pos];
280 }
281 const_reference at (size_type pos) const
282 {
283 OUTOFRANGE (pos >= length ());
284 return data ()[pos];
285 }
286
287 private:
288 void terminate () const
289 { traits::assign ((*rep ())[length ()], eos ()); }
290
291 public:
292 const charT* c_str () const
293 { if (length () == 0) return ""; terminate (); return data (); }
294 void resize (size_type n, charT c);
295 void resize (size_type n)
296 { resize (n, eos ()); }
297 void reserve (size_type) { }
298
299 size_type copy (charT* s, size_type n, size_type pos = 0) const;
300
301 size_type find (const basic_string& str, size_type pos = 0) const
302 { return find (str.data(), pos, str.length()); }
303 size_type find (const charT* s, size_type pos, size_type n) const;
304 size_type find (const charT* s, size_type pos = 0) const
305 { return find (s, pos, traits::length (s)); }
306 size_type find (charT c, size_type pos = 0) const;
307
308 size_type rfind (const basic_string& str, size_type pos = npos) const
309 { return rfind (str.data(), pos, str.length()); }
310 size_type rfind (const charT* s, size_type pos, size_type n) const;
311 size_type rfind (const charT* s, size_type pos = npos) const
312 { return rfind (s, pos, traits::length (s)); }
313 size_type rfind (charT c, size_type pos = npos) const;
314
315 size_type find_first_of (const basic_string& str, size_type pos = 0) const
316 { return find_first_of (str.data(), pos, str.length()); }
317 size_type find_first_of (const charT* s, size_type pos, size_type n) const;
318 size_type find_first_of (const charT* s, size_type pos = 0) const
319 { return find_first_of (s, pos, traits::length (s)); }
320 size_type find_first_of (charT c, size_type pos = 0) const
321 { return find (c, pos); }
322
323 size_type find_last_of (const basic_string& str, size_type pos = npos) const
324 { return find_last_of (str.data(), pos, str.length()); }
325 size_type find_last_of (const charT* s, size_type pos, size_type n) const;
326 size_type find_last_of (const charT* s, size_type pos = npos) const
327 { return find_last_of (s, pos, traits::length (s)); }
328 size_type find_last_of (charT c, size_type pos = npos) const
329 { return rfind (c, pos); }
330
331 size_type find_first_not_of (const basic_string& str, size_type pos = 0) const
332 { return find_first_not_of (str.data(), pos, str.length()); }
333 size_type find_first_not_of (const charT* s, size_type pos, size_type n) const;
334 size_type find_first_not_of (const charT* s, size_type pos = 0) const
335 { return find_first_not_of (s, pos, traits::length (s)); }
336 size_type find_first_not_of (charT c, size_type pos = 0) const;
337
338 size_type find_last_not_of (const basic_string& str, size_type pos = npos) const
339 { return find_last_not_of (str.data(), pos, str.length()); }
340 size_type find_last_not_of (const charT* s, size_type pos, size_type n) const;
341 size_type find_last_not_of (const charT* s, size_type pos = npos) const
342 { return find_last_not_of (s, pos, traits::length (s)); }
343 size_type find_last_not_of (charT c, size_type pos = npos) const;
344
345 basic_string substr (size_type pos = 0, size_type n = npos) const
346 { return basic_string (*this, pos, n); }
347
348 int compare (const basic_string& str, size_type pos = 0, size_type n = npos) const;
349 // There is no 'strncmp' equivalent for charT pointers.
350 int compare (const charT* s, size_type pos, size_type n) const;
351 int compare (const charT* s, size_type pos = 0) const
352 { return compare (s, pos, traits::length (s)); }
353
354 iterator begin () { selfish (); return &(*this)[0]; }
355 iterator end () { selfish (); return &(*this)[length ()]; }
356
357 private:
358 iterator ibegin () const { return &(*rep ())[0]; }
359 iterator iend () const { return &(*rep ())[length ()]; }
360
361 public:
362 const_iterator begin () const { return ibegin (); }
363 const_iterator end () const { return iend (); }
364
365 reverse_iterator rbegin() { return reverse_iterator (end ()); }
366 const_reverse_iterator rbegin() const
367 { return const_reverse_iterator (end ()); }
368 reverse_iterator rend() { return reverse_iterator (begin ()); }
369 const_reverse_iterator rend() const
370 { return const_reverse_iterator (begin ()); }
371
372 private:
373 void alloc (size_type size, bool save);
374 static size_type _find (const charT* ptr, charT c, size_type xpos, size_type len);
375 inline bool check_realloc (size_type s) const;
376
377 static Rep nilRep;
378 charT *dat;
379 };
380
381 #ifdef __STL_MEMBER_TEMPLATES
382 template <class charT, class traits, class Allocator> template <class InputIterator>
383 basic_string <charT, traits, Allocator>& basic_string <charT, traits, Allocator>::
384 replace (iterator i1, iterator i2, InputIterator j1, InputIterator j2)
385 #else
386 template <class charT, class traits, class Allocator>
387 basic_string <charT, traits, Allocator>& basic_string <charT, traits, Allocator>::
388 replace (iterator i1, iterator i2, const_iterator j1, const_iterator j2)
389 #endif
390 {
391 const size_type len = length ();
392 size_type pos = i1 - ibegin ();
393 size_type n1 = i2 - i1;
394 size_type n2 = j2 - j1;
395
396 OUTOFRANGE (pos > len);
397 if (n1 > len - pos)
398 n1 = len - pos;
399 LENGTHERROR (len - n1 > max_size () - n2);
400 size_t newlen = len - n1 + n2;
401
402 if (check_realloc (newlen))
403 {
404 Rep *p = Rep::create (newlen);
405 p->copy (0, data (), pos);
406 p->copy (pos + n2, data () + pos + n1, len - (pos + n1));
407 for (; j1 != j2; ++j1, ++pos)
408 traits::assign ((*p)[pos], *j1);
409 repup (p);
410 }
411 else
412 {
413 rep ()->move (pos + n2, data () + pos + n1, len - (pos + n1));
414 for (; j1 != j2; ++j1, ++pos)
415 traits::assign ((*rep ())[pos], *j1);
416 }
417 rep ()->len = newlen;
418
419 return *this;
420 }
421
422 template <class charT, class traits, class Allocator>
423 inline basic_string <charT, traits, Allocator>
424 operator+ (const basic_string <charT, traits, Allocator>& lhs,
425 const basic_string <charT, traits, Allocator>& rhs)
426 {
427 basic_string <charT, traits, Allocator> str (lhs);
428 str.append (rhs);
429 return str;
430 }
431
432 template <class charT, class traits, class Allocator>
433 inline basic_string <charT, traits, Allocator>
434 operator+ (const charT* lhs, const basic_string <charT, traits, Allocator>& rhs)
435 {
436 basic_string <charT, traits, Allocator> str (lhs);
437 str.append (rhs);
438 return str;
439 }
440
441 template <class charT, class traits, class Allocator>
442 inline basic_string <charT, traits, Allocator>
443 operator+ (charT lhs, const basic_string <charT, traits, Allocator>& rhs)
444 {
445 basic_string <charT, traits, Allocator> str (1, lhs);
446 str.append (rhs);
447 return str;
448 }
449
450 template <class charT, class traits, class Allocator>
451 inline basic_string <charT, traits, Allocator>
452 operator+ (const basic_string <charT, traits, Allocator>& lhs, const charT* rhs)
453 {
454 basic_string <charT, traits, Allocator> str (lhs);
455 str.append (rhs);
456 return str;
457 }
458
459 template <class charT, class traits, class Allocator>
460 inline basic_string <charT, traits, Allocator>
461 operator+ (const basic_string <charT, traits, Allocator>& lhs, charT rhs)
462 {
463 basic_string <charT, traits, Allocator> str (lhs);
464 str.append (1, rhs);
465 return str;
466 }
467
468 template <class charT, class traits, class Allocator>
469 inline bool
470 operator== (const basic_string <charT, traits, Allocator>& lhs,
471 const basic_string <charT, traits, Allocator>& rhs)
472 {
473 return (lhs.compare (rhs) == 0);
474 }
475
476 template <class charT, class traits, class Allocator>
477 inline bool
478 operator== (const charT* lhs, const basic_string <charT, traits, Allocator>& rhs)
479 {
480 return (rhs.compare (lhs) == 0);
481 }
482
483 template <class charT, class traits, class Allocator>
484 inline bool
485 operator== (const basic_string <charT, traits, Allocator>& lhs, const charT* rhs)
486 {
487 return (lhs.compare (rhs) == 0);
488 }
489
490 template <class charT, class traits, class Allocator>
491 inline bool
492 operator!= (const charT* lhs, const basic_string <charT, traits, Allocator>& rhs)
493 {
494 return (rhs.compare (lhs) != 0);
495 }
496
497 template <class charT, class traits, class Allocator>
498 inline bool
499 operator!= (const basic_string <charT, traits, Allocator>& lhs, const charT* rhs)
500 {
501 return (lhs.compare (rhs) != 0);
502 }
503
504 template <class charT, class traits, class Allocator>
505 inline bool
506 operator< (const basic_string <charT, traits, Allocator>& lhs,
507 const basic_string <charT, traits, Allocator>& rhs)
508 {
509 return (lhs.compare (rhs) < 0);
510 }
511
512 template <class charT, class traits, class Allocator>
513 inline bool
514 operator< (const charT* lhs, const basic_string <charT, traits, Allocator>& rhs)
515 {
516 return (rhs.compare (lhs) > 0);
517 }
518
519 template <class charT, class traits, class Allocator>
520 inline bool
521 operator< (const basic_string <charT, traits, Allocator>& lhs, const charT* rhs)
522 {
523 return (lhs.compare (rhs) < 0);
524 }
525
526 template <class charT, class traits, class Allocator>
527 inline bool
528 operator> (const charT* lhs, const basic_string <charT, traits, Allocator>& rhs)
529 {
530 return (rhs.compare (lhs) < 0);
531 }
532
533 template <class charT, class traits, class Allocator>
534 inline bool
535 operator> (const basic_string <charT, traits, Allocator>& lhs, const charT* rhs)
536 {
537 return (lhs.compare (rhs) > 0);
538 }
539
540 template <class charT, class traits, class Allocator>
541 inline bool
542 operator<= (const charT* lhs, const basic_string <charT, traits, Allocator>& rhs)
543 {
544 return (rhs.compare (lhs) >= 0);
545 }
546
547 template <class charT, class traits, class Allocator>
548 inline bool
549 operator<= (const basic_string <charT, traits, Allocator>& lhs, const charT* rhs)
550 {
551 return (lhs.compare (rhs) <= 0);
552 }
553
554 template <class charT, class traits, class Allocator>
555 inline bool
556 operator>= (const charT* lhs, const basic_string <charT, traits, Allocator>& rhs)
557 {
558 return (rhs.compare (lhs) <= 0);
559 }
560
561 template <class charT, class traits, class Allocator>
562 inline bool
563 operator>= (const basic_string <charT, traits, Allocator>& lhs, const charT* rhs)
564 {
565 return (lhs.compare (rhs) >= 0);
566 }
567
568 template <class charT, class traits, class Allocator>
569 inline bool
570 operator!= (const basic_string <charT, traits, Allocator>& lhs,
571 const basic_string <charT, traits, Allocator>& rhs)
572 {
573 return (lhs.compare (rhs) != 0);
574 }
575
576 template <class charT, class traits, class Allocator>
577 inline bool
578 operator> (const basic_string <charT, traits, Allocator>& lhs,
579 const basic_string <charT, traits, Allocator>& rhs)
580 {
581 return (lhs.compare (rhs) > 0);
582 }
583
584 template <class charT, class traits, class Allocator>
585 inline bool
586 operator<= (const basic_string <charT, traits, Allocator>& lhs,
587 const basic_string <charT, traits, Allocator>& rhs)
588 {
589 return (lhs.compare (rhs) <= 0);
590 }
591
592 template <class charT, class traits, class Allocator>
593 inline bool
594 operator>= (const basic_string <charT, traits, Allocator>& lhs,
595 const basic_string <charT, traits, Allocator>& rhs)
596 {
597 return (lhs.compare (rhs) >= 0);
598 }
599
600 class istream; class ostream;
601 template <class charT, class traits, class Allocator> istream&
602 operator>> (istream&, basic_string <charT, traits, Allocator>&);
603 template <class charT, class traits, class Allocator> ostream&
604 operator<< (ostream&, const basic_string <charT, traits, Allocator>&);
605 template <class charT, class traits, class Allocator> istream&
606 getline (istream&, basic_string <charT, traits, Allocator>&, charT delim = '\n');
607
608 } // extern "C++"
609
610 #include <std/bastring.cc>
611
612 #endif