1 // Main templates for the -*- C++ -*- string classes.
2 // Copyright (C) 1994, 1995, 1999 Free Software Foundation
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)
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.
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.
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.
25 // Written by Jason Merrill based upon the specification by Takanori Adachi
26 // in ANSI X3J16/94-0013R2.
36 #include <std/straits.h>
38 // NOTE : This does NOT conform to the draft standard and is likely to change
42 class istream
; class ostream
;
46 #ifdef __STL_USE_EXCEPTIONS
48 extern void __out_of_range (const char *);
49 extern void __length_error (const char *);
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)
59 #define OUTOFRANGE(cond) assert (!(cond))
60 #define LENGTHERROR(cond) assert (!(cond))
64 template <class charT
, class traits
= string_char_traits
<charT
>,
65 class Allocator
= alloc
>
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 #if defined __i486__ || defined __i586__ || defined __i686__
80 // This opcode exists as a .byte instead of as a mnemonic for the
81 // benefit of SCO OpenServer 5. The system assembler (which is
82 // essentially required on this target) can't assemble xaddl in
84 asm (".byte 0xf0, 0x0f, 0xc1, 0x02" // lock; xaddl %eax, (%edx)
86 : "0" (-1), "m" (ref
), "d" (&ref
)
92 #elif defined __sparcv9__
95 size_t __newval
, __oldval
= ref
;
98 __newval
= __oldval
- 1;
99 __asm__ ("cas [%4], %2, %0"
100 : "=r" (__oldval
), "=m" (ref
)
101 : "r" (__oldval
), "m" (ref
), "r"(&(ref
)), "0" (__newval
));
103 while (__newval
!= __oldval
);
109 void release () { if (--ref
== 0) delete this; }
112 inline static void * operator new (size_t, size_t);
113 inline static void operator delete (void *);
114 inline static Rep
* create (size_t);
117 inline void copy (size_t, const charT
*, size_t);
118 inline void move (size_t, const charT
*, size_t);
119 inline void set (size_t, const charT
, size_t);
121 inline static bool excess_slop (size_t, size_t);
122 inline static size_t frob_size (size_t);
125 Rep
&operator= (const Rep
&);
130 typedef traits traits_type
;
131 typedef typename
traits::char_type value_type
;
132 typedef Allocator allocator_type
;
134 typedef size_t size_type
;
135 typedef ptrdiff_t difference_type
;
136 typedef charT
& reference
;
137 typedef const charT
& const_reference
;
138 typedef charT
* pointer
;
139 typedef const charT
* const_pointer
;
140 typedef pointer iterator
;
141 typedef const_pointer const_iterator
;
142 typedef ::reverse_iterator
<iterator
> reverse_iterator
;
143 typedef ::reverse_iterator
<const_iterator
> const_reverse_iterator
;
144 static const size_type npos
= static_cast<size_type
>(-1);
147 Rep
*rep () const { return reinterpret_cast<Rep
*>(dat
) - 1; }
148 void repup (Rep
*p
) { rep ()->release (); dat
= p
->data (); }
151 const charT
* data () const
152 { return rep ()->data(); }
153 size_type
length () const
154 { return rep ()->len
; }
155 size_type
size () const
156 { return rep ()->len
; }
157 size_type
capacity () const
158 { return rep ()->res
; }
159 size_type
max_size () const
160 { return (npos
- 1)/sizeof (charT
); } // XXX
162 { return size () == 0; }
164 // _lib.string.cons_ construct/copy/destroy:
165 basic_string
& operator= (const basic_string
& str
)
167 if (&str
!= this) { rep ()->release (); dat
= str
.rep ()->grab (); }
171 explicit basic_string (): dat (nilRep
.grab ()) { }
172 basic_string (const basic_string
& str
): dat (str
.rep ()->grab ()) { }
173 basic_string (const basic_string
& str
, size_type pos
, size_type n
= npos
)
174 : dat (nilRep
.grab ()) { assign (str
, pos
, n
); }
175 basic_string (const charT
* s
, size_type n
)
176 : dat (nilRep
.grab ()) { assign (s
, n
); }
177 basic_string (const charT
* s
)
178 : dat (nilRep
.grab ()) { assign (s
); }
179 basic_string (size_type n
, charT c
)
180 : dat (nilRep
.grab ()) { assign (n
, c
); }
181 #ifdef __STL_MEMBER_TEMPLATES
182 template<class InputIterator
>
183 basic_string(InputIterator __begin
, InputIterator __end
)
185 basic_string(const_iterator __begin
, const_iterator __end
)
187 : dat (nilRep
.grab ()) { assign (__begin
, __end
); }
190 { rep ()->release (); }
192 void swap (basic_string
&s
) { charT
*d
= dat
; dat
= s
.dat
; s
.dat
= d
; }
194 basic_string
& append (const basic_string
& str
, size_type pos
= 0,
196 { return replace (length (), 0, str
, pos
, n
); }
197 basic_string
& append (const charT
* s
, size_type n
)
198 { return replace (length (), 0, s
, n
); }
199 basic_string
& append (const charT
* s
)
200 { return append (s
, traits::length (s
)); }
201 basic_string
& append (size_type n
, charT c
)
202 { return replace (length (), 0, n
, c
); }
203 #ifdef __STL_MEMBER_TEMPLATES
204 template<class InputIterator
>
205 basic_string
& append(InputIterator first
, InputIterator last
)
207 basic_string
& append(const_iterator first
, const_iterator last
)
209 { return replace (iend (), iend (), first
, last
); }
211 void push_back(charT __c
)
214 basic_string
& assign (const basic_string
& str
, size_type pos
= 0,
216 { return replace (0, npos
, str
, pos
, n
); }
217 basic_string
& assign (const charT
* s
, size_type n
)
218 { return replace (0, npos
, s
, n
); }
219 basic_string
& assign (const charT
* s
)
220 { return assign (s
, traits::length (s
)); }
221 basic_string
& assign (size_type n
, charT c
)
222 { return replace (0, npos
, n
, c
); }
223 #ifdef __STL_MEMBER_TEMPLATES
224 template<class InputIterator
>
225 basic_string
& assign(InputIterator first
, InputIterator last
)
227 basic_string
& assign(const_iterator first
, const_iterator last
)
229 { return replace (ibegin (), iend (), first
, last
); }
231 basic_string
& operator= (const charT
* s
)
232 { return assign (s
); }
233 basic_string
& operator= (charT c
)
234 { return assign (1, c
); }
236 basic_string
& operator+= (const basic_string
& rhs
)
237 { return append (rhs
); }
238 basic_string
& operator+= (const charT
* s
)
239 { return append (s
); }
240 basic_string
& operator+= (charT c
)
241 { return append (1, c
); }
243 basic_string
& insert (size_type pos1
, const basic_string
& str
,
244 size_type pos2
= 0, size_type n
= npos
)
245 { return replace (pos1
, 0, str
, pos2
, n
); }
246 basic_string
& insert (size_type pos
, const charT
* s
, size_type n
)
247 { return replace (pos
, 0, s
, n
); }
248 basic_string
& insert (size_type pos
, const charT
* s
)
249 { return insert (pos
, s
, traits::length (s
)); }
250 basic_string
& insert (size_type pos
, size_type n
, charT c
)
251 { return replace (pos
, 0, n
, c
); }
252 iterator
insert(iterator p
, charT c
)
253 { size_type __o
= p
- ibegin ();
254 insert (p
- ibegin (), 1, c
); selfish ();
255 return ibegin () + __o
; }
256 iterator
insert(iterator p
, size_type n
, charT c
)
257 { size_type __o
= p
- ibegin ();
258 insert (p
- ibegin (), n
, c
); selfish ();
259 return ibegin () + __o
; }
260 #ifdef __STL_MEMBER_TEMPLATES
261 template<class InputIterator
>
262 void insert(iterator p
, InputIterator first
, InputIterator last
)
264 void insert(iterator p
, const_iterator first
, const_iterator last
)
266 { replace (p
, p
, first
, last
); }
268 basic_string
& erase (size_type pos
= 0, size_type n
= npos
)
269 { return replace (pos
, n
, (size_type
)0, (charT
)0); }
270 iterator
erase(iterator p
)
271 { size_type __o
= p
- begin();
272 replace (__o
, 1, (size_type
)0, (charT
)0); selfish ();
273 return ibegin() + __o
; }
274 iterator
erase(iterator f
, iterator l
)
275 { size_type __o
= f
- ibegin();
276 replace (__o
, l
-f
, (size_type
)0, (charT
)0);selfish ();
277 return ibegin() + __o
; }
279 basic_string
& replace (size_type pos1
, size_type n1
, const basic_string
& str
,
280 size_type pos2
= 0, size_type n2
= npos
);
281 basic_string
& replace (size_type pos
, size_type n1
, const charT
* s
,
283 basic_string
& replace (size_type pos
, size_type n1
, const charT
* s
)
284 { return replace (pos
, n1
, s
, traits::length (s
)); }
285 basic_string
& replace (size_type pos
, size_type n1
, size_type n2
, charT c
);
286 basic_string
& replace (size_type pos
, size_type n
, charT c
)
287 { return replace (pos
, n
, 1, c
); }
288 basic_string
& replace (iterator i1
, iterator i2
, const basic_string
& str
)
289 { return replace (i1
- ibegin (), i2
- i1
, str
); }
290 basic_string
& replace (iterator i1
, iterator i2
, const charT
* s
, size_type n
)
291 { return replace (i1
- ibegin (), i2
- i1
, s
, n
); }
292 basic_string
& replace (iterator i1
, iterator i2
, const charT
* s
)
293 { return replace (i1
- ibegin (), i2
- i1
, s
); }
294 basic_string
& replace (iterator i1
, iterator i2
, size_type n
, charT c
)
295 { return replace (i1
- ibegin (), i2
- i1
, n
, c
); }
296 #ifdef __STL_MEMBER_TEMPLATES
297 template<class InputIterator
>
298 basic_string
& replace(iterator i1
, iterator i2
,
299 InputIterator j1
, InputIterator j2
);
301 basic_string
& replace(iterator i1
, iterator i2
,
302 const_iterator j1
, const_iterator j2
);
306 static charT
eos () { return traits::eos (); }
307 void unique () { if (rep ()->ref
> 1) alloc (length (), true); }
308 void selfish () { unique (); rep ()->selfish
= true; }
311 charT
operator[] (size_type pos
) const
313 if (pos
== length ())
318 reference
operator[] (size_type pos
)
319 { selfish (); return (*rep ())[pos
]; }
321 reference
at (size_type pos
)
323 OUTOFRANGE (pos
>= length ());
326 const_reference
at (size_type pos
) const
328 OUTOFRANGE (pos
>= length ());
333 void terminate () const
334 { traits::assign ((*rep ())[length ()], eos ()); }
337 const charT
* c_str () const
338 { if (length () == 0) return ""; terminate (); return data (); }
339 void resize (size_type n
, charT c
);
340 void resize (size_type n
)
341 { resize (n
, eos ()); }
342 void reserve (size_type
) { }
344 size_type
copy (charT
* s
, size_type n
, size_type pos
= 0) const;
346 size_type
find (const basic_string
& str
, size_type pos
= 0) const
347 { return find (str
.data(), pos
, str
.length()); }
348 size_type
find (const charT
* s
, size_type pos
, size_type n
) const;
349 size_type
find (const charT
* s
, size_type pos
= 0) const
350 { return find (s
, pos
, traits::length (s
)); }
351 size_type
find (charT c
, size_type pos
= 0) const;
353 size_type
rfind (const basic_string
& str
, size_type pos
= npos
) const
354 { return rfind (str
.data(), pos
, str
.length()); }
355 size_type
rfind (const charT
* s
, size_type pos
, size_type n
) const;
356 size_type
rfind (const charT
* s
, size_type pos
= npos
) const
357 { return rfind (s
, pos
, traits::length (s
)); }
358 size_type
rfind (charT c
, size_type pos
= npos
) const;
360 size_type
find_first_of (const basic_string
& str
, size_type pos
= 0) const
361 { return find_first_of (str
.data(), pos
, str
.length()); }
362 size_type
find_first_of (const charT
* s
, size_type pos
, size_type n
) const;
363 size_type
find_first_of (const charT
* s
, size_type pos
= 0) const
364 { return find_first_of (s
, pos
, traits::length (s
)); }
365 size_type
find_first_of (charT c
, size_type pos
= 0) const
366 { return find (c
, pos
); }
368 size_type
find_last_of (const basic_string
& str
, size_type pos
= npos
) const
369 { return find_last_of (str
.data(), pos
, str
.length()); }
370 size_type
find_last_of (const charT
* s
, size_type pos
, size_type n
) const;
371 size_type
find_last_of (const charT
* s
, size_type pos
= npos
) const
372 { return find_last_of (s
, pos
, traits::length (s
)); }
373 size_type
find_last_of (charT c
, size_type pos
= npos
) const
374 { return rfind (c
, pos
); }
376 size_type
find_first_not_of (const basic_string
& str
, size_type pos
= 0) const
377 { return find_first_not_of (str
.data(), pos
, str
.length()); }
378 size_type
find_first_not_of (const charT
* s
, size_type pos
, size_type n
) const;
379 size_type
find_first_not_of (const charT
* s
, size_type pos
= 0) const
380 { return find_first_not_of (s
, pos
, traits::length (s
)); }
381 size_type
find_first_not_of (charT c
, size_type pos
= 0) const;
383 size_type
find_last_not_of (const basic_string
& str
, size_type pos
= npos
) const
384 { return find_last_not_of (str
.data(), pos
, str
.length()); }
385 size_type
find_last_not_of (const charT
* s
, size_type pos
, size_type n
) const;
386 size_type
find_last_not_of (const charT
* s
, size_type pos
= npos
) const
387 { return find_last_not_of (s
, pos
, traits::length (s
)); }
388 size_type
find_last_not_of (charT c
, size_type pos
= npos
) const;
390 basic_string
substr (size_type pos
= 0, size_type n
= npos
) const
391 { return basic_string (*this, pos
, n
); }
393 int compare (const basic_string
& str
, size_type pos
= 0, size_type n
= npos
) const;
394 // There is no 'strncmp' equivalent for charT pointers.
395 int compare (const charT
* s
, size_type pos
, size_type n
) const;
396 int compare (const charT
* s
, size_type pos
= 0) const
397 { return compare (s
, pos
, traits::length (s
)); }
399 iterator
begin () { selfish (); return &(*this)[0]; }
400 iterator
end () { selfish (); return &(*this)[length ()]; }
403 iterator
ibegin () const { return &(*rep ())[0]; }
404 iterator
iend () const { return &(*rep ())[length ()]; }
407 const_iterator
begin () const { return ibegin (); }
408 const_iterator
end () const { return iend (); }
410 reverse_iterator
rbegin() { return reverse_iterator (end ()); }
411 const_reverse_iterator
rbegin() const
412 { return const_reverse_iterator (end ()); }
413 reverse_iterator
rend() { return reverse_iterator (begin ()); }
414 const_reverse_iterator
rend() const
415 { return const_reverse_iterator (begin ()); }
418 void alloc (size_type size
, bool save
);
419 static size_type
_find (const charT
* ptr
, charT c
, size_type xpos
, size_type len
);
420 inline bool check_realloc (size_type s
) const;
426 #ifdef __STL_MEMBER_TEMPLATES
427 template <class charT
, class traits
, class Allocator
> template <class InputIterator
>
428 basic_string
<charT
, traits
, Allocator
>& basic_string
<charT
, traits
, Allocator
>::
429 replace (iterator i1
, iterator i2
, InputIterator j1
, InputIterator j2
)
431 template <class charT
, class traits
, class Allocator
>
432 basic_string
<charT
, traits
, Allocator
>& basic_string
<charT
, traits
, Allocator
>::
433 replace (iterator i1
, iterator i2
, const_iterator j1
, const_iterator j2
)
436 const size_type len
= length ();
437 size_type pos
= i1
- ibegin ();
438 size_type n1
= i2
- i1
;
439 size_type n2
= j2
- j1
;
441 OUTOFRANGE (pos
> len
);
444 LENGTHERROR (len
- n1
> max_size () - n2
);
445 size_t newlen
= len
- n1
+ n2
;
447 if (check_realloc (newlen
))
449 Rep
*p
= Rep::create (newlen
);
450 p
->copy (0, data (), pos
);
451 p
->copy (pos
+ n2
, data () + pos
+ n1
, len
- (pos
+ n1
));
452 for (; j1
!= j2
; ++j1
, ++pos
)
453 traits::assign ((*p
)[pos
], *j1
);
458 rep ()->move (pos
+ n2
, data () + pos
+ n1
, len
- (pos
+ n1
));
459 for (; j1
!= j2
; ++j1
, ++pos
)
460 traits::assign ((*rep ())[pos
], *j1
);
462 rep ()->len
= newlen
;
467 template <class charT
, class traits
, class Allocator
>
468 inline basic_string
<charT
, traits
, Allocator
>
469 operator+ (const basic_string
<charT
, traits
, Allocator
>& lhs
,
470 const basic_string
<charT
, traits
, Allocator
>& rhs
)
472 basic_string
<charT
, traits
, Allocator
> str (lhs
);
477 template <class charT
, class traits
, class Allocator
>
478 inline basic_string
<charT
, traits
, Allocator
>
479 operator+ (const charT
* lhs
, const basic_string
<charT
, traits
, Allocator
>& rhs
)
481 basic_string
<charT
, traits
, Allocator
> str (lhs
);
486 template <class charT
, class traits
, class Allocator
>
487 inline basic_string
<charT
, traits
, Allocator
>
488 operator+ (charT lhs
, const basic_string
<charT
, traits
, Allocator
>& rhs
)
490 basic_string
<charT
, traits
, Allocator
> str (1, lhs
);
495 template <class charT
, class traits
, class Allocator
>
496 inline basic_string
<charT
, traits
, Allocator
>
497 operator+ (const basic_string
<charT
, traits
, Allocator
>& lhs
, const charT
* rhs
)
499 basic_string
<charT
, traits
, Allocator
> str (lhs
);
504 template <class charT
, class traits
, class Allocator
>
505 inline basic_string
<charT
, traits
, Allocator
>
506 operator+ (const basic_string
<charT
, traits
, Allocator
>& lhs
, charT rhs
)
508 basic_string
<charT
, traits
, Allocator
> str (lhs
);
513 template <class charT
, class traits
, class Allocator
>
515 operator== (const basic_string
<charT
, traits
, Allocator
>& lhs
,
516 const basic_string
<charT
, traits
, Allocator
>& rhs
)
518 return (lhs
.compare (rhs
) == 0);
521 template <class charT
, class traits
, class Allocator
>
523 operator== (const charT
* lhs
, const basic_string
<charT
, traits
, Allocator
>& rhs
)
525 return (rhs
.compare (lhs
) == 0);
528 template <class charT
, class traits
, class Allocator
>
530 operator== (const basic_string
<charT
, traits
, Allocator
>& lhs
, const charT
* rhs
)
532 return (lhs
.compare (rhs
) == 0);
535 template <class charT
, class traits
, class Allocator
>
537 operator!= (const charT
* lhs
, const basic_string
<charT
, traits
, Allocator
>& rhs
)
539 return (rhs
.compare (lhs
) != 0);
542 template <class charT
, class traits
, class Allocator
>
544 operator!= (const basic_string
<charT
, traits
, Allocator
>& lhs
, const charT
* rhs
)
546 return (lhs
.compare (rhs
) != 0);
549 template <class charT
, class traits
, class Allocator
>
551 operator< (const basic_string
<charT
, traits
, Allocator
>& lhs
,
552 const basic_string
<charT
, traits
, Allocator
>& rhs
)
554 return (lhs
.compare (rhs
) < 0);
557 template <class charT
, class traits
, class Allocator
>
559 operator< (const charT
* lhs
, const basic_string
<charT
, traits
, Allocator
>& rhs
)
561 return (rhs
.compare (lhs
) > 0);
564 template <class charT
, class traits
, class Allocator
>
566 operator< (const basic_string
<charT
, traits
, Allocator
>& lhs
, const charT
* rhs
)
568 return (lhs
.compare (rhs
) < 0);
571 template <class charT
, class traits
, class Allocator
>
573 operator> (const charT
* lhs
, const basic_string
<charT
, traits
, Allocator
>& rhs
)
575 return (rhs
.compare (lhs
) < 0);
578 template <class charT
, class traits
, class Allocator
>
580 operator> (const basic_string
<charT
, traits
, Allocator
>& lhs
, const charT
* rhs
)
582 return (lhs
.compare (rhs
) > 0);
585 template <class charT
, class traits
, class Allocator
>
587 operator<= (const charT
* lhs
, const basic_string
<charT
, traits
, Allocator
>& rhs
)
589 return (rhs
.compare (lhs
) >= 0);
592 template <class charT
, class traits
, class Allocator
>
594 operator<= (const basic_string
<charT
, traits
, Allocator
>& lhs
, const charT
* rhs
)
596 return (lhs
.compare (rhs
) <= 0);
599 template <class charT
, class traits
, class Allocator
>
601 operator>= (const charT
* lhs
, const basic_string
<charT
, traits
, Allocator
>& rhs
)
603 return (rhs
.compare (lhs
) <= 0);
606 template <class charT
, class traits
, class Allocator
>
608 operator>= (const basic_string
<charT
, traits
, Allocator
>& lhs
, const charT
* rhs
)
610 return (lhs
.compare (rhs
) >= 0);
613 template <class charT
, class traits
, class Allocator
>
615 operator!= (const basic_string
<charT
, traits
, Allocator
>& lhs
,
616 const basic_string
<charT
, traits
, Allocator
>& rhs
)
618 return (lhs
.compare (rhs
) != 0);
621 template <class charT
, class traits
, class Allocator
>
623 operator> (const basic_string
<charT
, traits
, Allocator
>& lhs
,
624 const basic_string
<charT
, traits
, Allocator
>& rhs
)
626 return (lhs
.compare (rhs
) > 0);
629 template <class charT
, class traits
, class Allocator
>
631 operator<= (const basic_string
<charT
, traits
, Allocator
>& lhs
,
632 const basic_string
<charT
, traits
, Allocator
>& rhs
)
634 return (lhs
.compare (rhs
) <= 0);
637 template <class charT
, class traits
, class Allocator
>
639 operator>= (const basic_string
<charT
, traits
, Allocator
>& lhs
,
640 const basic_string
<charT
, traits
, Allocator
>& rhs
)
642 return (lhs
.compare (rhs
) >= 0);
645 class istream
; class ostream
;
646 template <class charT
, class traits
, class Allocator
> istream
&
647 operator>> (istream
&, basic_string
<charT
, traits
, Allocator
>&);
648 template <class charT
, class traits
, class Allocator
> ostream
&
649 operator<< (ostream
&, const basic_string
<charT
, traits
, Allocator
>&);
650 template <class charT
, class traits
, class Allocator
> istream
&
651 getline (istream
&, basic_string
<charT
, traits
, Allocator
>&, charT delim
= '\n');
655 #include <std/bastring.cc>