1// Member templates for the -*- C++ -*- string classes.
2// Copyright (C) 1994, 1999 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
28extern "C++" {
29template <class charT, class traits, class Allocator>
30inline void * basic_string <charT, traits, Allocator>::Rep::
31operator new (size_t s, size_t extra)
32{
33  return Allocator::allocate(s + extra * sizeof (charT));
34}
35
36template <class charT, class traits, class Allocator>
37inline void basic_string <charT, traits, Allocator>::Rep::
38operator delete (void * ptr)
39{
40  Allocator::deallocate(ptr, sizeof(Rep) +
41			reinterpret_cast<Rep *>(ptr)->res *
42			sizeof (charT));
43}
44
45template <class charT, class traits, class Allocator>
46inline size_t basic_string <charT, traits, Allocator>::Rep::
47frob_size (size_t s)
48{
49  size_t i = 16;
50  while (i < s) i *= 2;
51  return i;
52}
53
54template <class charT, class traits, class Allocator>
55inline basic_string <charT, traits, Allocator>::Rep *
56basic_string <charT, traits, Allocator>::Rep::
57create (size_t extra)
58{
59  extra = frob_size (extra + 1);
60  Rep *p = new (extra) Rep;
61  p->res = extra;
62  p->ref = 1;
63  p->selfish = false;
64  return p;
65}
66
67template <class charT, class traits, class Allocator>
68charT * basic_string <charT, traits, Allocator>::Rep::
69clone ()
70{
71  Rep *p = Rep::create (len);
72  p->copy (0, data (), len);
73  p->len = len;
74  return p->data ();
75}
76
77template <class charT, class traits, class Allocator>
78inline bool basic_string <charT, traits, Allocator>::Rep::
79excess_slop (size_t s, size_t r)
80{
81  return 2 * (s <= 16 ? 16 : s) < r;
82}
83
84template <class charT, class traits, class Allocator>
85inline bool basic_string <charT, traits, Allocator>::
86check_realloc (basic_string::size_type s) const
87{
88  s += sizeof (charT);
89  rep ()->selfish = false;
90  return (rep ()->ref > 1
91	  || s > capacity ()
92	  || Rep::excess_slop (s, capacity ()));
93}
94
95template <class charT, class traits, class Allocator>
96void basic_string <charT, traits, Allocator>::
97alloc (basic_string::size_type __size, bool __save)
98{
99  if (! check_realloc (__size))
100    return;
101
102  Rep *p = Rep::create (__size);
103
104  if (__save)
105    {
106      p->copy (0, data (), length ());
107      p->len = length ();
108    }
109  else
110    p->len = 0;
111
112  repup (p);
113}
114
115template <class charT, class traits, class Allocator>
116basic_string <charT, traits, Allocator>&
117basic_string <charT, traits, Allocator>::
118replace (size_type pos1, size_type n1,
119	 const basic_string& _str, size_type pos2, size_type n2)
120{
121  const size_t len2 = _str.length ();
122
123  if (pos1 == 0 && n1 >= length () && pos2 == 0 && n2 >= len2)
124    return operator= (_str);
125
126  OUTOFRANGE (pos2 > len2);
127
128  if (n2 > len2 - pos2)
129    n2 = len2 - pos2;
130
131  return replace (pos1, n1, _str.data () + pos2, n2);
132}
133
134template <class charT, class traits, class Allocator>
135inline void basic_string <charT, traits, Allocator>::Rep::
136copy (size_t pos, const charT *s, size_t n)
137{
138  if (n)
139    traits::copy (data () + pos, s, n);
140}
141
142template <class charT, class traits, class Allocator>
143inline void basic_string <charT, traits, Allocator>::Rep::
144move (size_t pos, const charT *s, size_t n)
145{
146  if (n)
147    traits::move (data () + pos, s, n);
148}
149
150template <class charT, class traits, class Allocator>
151basic_string <charT, traits, Allocator>&
152basic_string <charT, traits, Allocator>::
153replace (size_type pos, size_type n1, const charT* s, size_type n2)
154{
155  const size_type len = length ();
156  OUTOFRANGE (pos > len);
157  if (n1 > len - pos)
158    n1 = len - pos;
159  LENGTHERROR (len - n1 > max_size () - n2);
160  size_t newlen = len - n1 + n2;
161
162  if (check_realloc (newlen))
163    {
164      Rep *p = Rep::create (newlen);
165      p->copy (0, data (), pos);
166      p->copy (pos + n2, data () + pos + n1, len - (pos + n1));
167      p->copy (pos, s, n2);
168      repup (p);
169    }
170  else
171    {
172      rep ()->move (pos + n2, data () + pos + n1, len - (pos + n1));
173      rep ()->copy (pos, s, n2);
174    }
175  rep ()->len = newlen;
176
177  return *this;
178}
179
180template <class charT, class traits, class Allocator>
181inline void basic_string <charT, traits, Allocator>::Rep::
182set (size_t pos, const charT c, size_t n)
183{
184  traits::set  (data () + pos, c, n);
185}
186
187template <class charT, class traits, class Allocator>
188basic_string <charT, traits, Allocator>& basic_string <charT, traits, Allocator>::
189replace (size_type pos, size_type n1, size_type n2, charT c)
190{
191  const size_t len = length ();
192  OUTOFRANGE (pos > len);
193  if (n1 > len - pos)
194    n1 = len - pos;
195  LENGTHERROR (len - n1 > max_size () - n2);
196  size_t newlen = len - n1 + n2;
197
198  if (check_realloc (newlen))
199    {
200      Rep *p = Rep::create (newlen);
201      p->copy (0, data (), pos);
202      p->copy (pos + n2, data () + pos + n1, len - (pos + n1));
203      p->set  (pos, c, n2);
204      repup (p);
205    }
206  else
207    {
208      rep ()->move (pos + n2, data () + pos + n1, len - (pos + n1));
209      rep ()->set  (pos, c, n2);
210    }
211  rep ()->len = newlen;
212
213  return *this;
214}
215
216template <class charT, class traits, class Allocator>
217void basic_string <charT, traits, Allocator>::
218resize (size_type n, charT c)
219{
220  LENGTHERROR (n > max_size ());
221
222  if (n > length ())
223    append (n - length (), c);
224  else
225    erase (n);
226}
227
228template <class charT, class traits, class Allocator>
229basic_string <charT, traits, Allocator>::size_type
230basic_string <charT, traits, Allocator>::
231copy (charT* s, size_type n, size_type pos) const
232{
233  OUTOFRANGE (pos > length ());
234
235  if (n > length () - pos)
236    n = length () - pos;
237
238  traits::copy (s, data () + pos, n);
239  return n;
240}
241
242template <class charT, class traits, class Allocator>
243basic_string <charT, traits, Allocator>::size_type
244basic_string <charT, traits, Allocator>::
245find (const charT* s, size_type pos, size_type n) const
246{
247  size_t xpos = pos;
248  for (; xpos + n <= length (); ++xpos)
249    if (traits::eq (data () [xpos], *s)
250	&& traits::compare (data () + xpos, s, n) == 0)
251      return xpos;
252  return npos;
253}
254
255template <class charT, class traits, class Allocator>
256inline basic_string <charT, traits, Allocator>::size_type
257basic_string <charT, traits, Allocator>::
258_find (const charT* ptr, charT c, size_type xpos, size_type len)
259{
260  for (; xpos < len; ++xpos)
261    if (traits::eq (ptr [xpos], c))
262      return xpos;
263  return npos;
264}
265
266template <class charT, class traits, class Allocator>
267basic_string <charT, traits, Allocator>::size_type
268basic_string <charT, traits, Allocator>::
269find (charT c, size_type pos) const
270{
271  return _find (data (), c, pos, length ());
272}
273
274template <class charT, class traits, class Allocator>
275basic_string <charT, traits, Allocator>::size_type
276basic_string <charT, traits, Allocator>::
277rfind (const charT* s, size_type pos, size_type n) const
278{
279  if (n > length ())
280    return npos;
281
282  size_t xpos = length () - n;
283  if (xpos > pos)
284    xpos = pos;
285
286  for (++xpos; xpos-- > 0; )
287    if (traits::eq (data () [xpos], *s)
288	&& traits::compare (data () + xpos, s, n) == 0)
289      return xpos;
290  return npos;
291}
292
293template <class charT, class traits, class Allocator>
294basic_string <charT, traits, Allocator>::size_type
295basic_string <charT, traits, Allocator>::
296rfind (charT c, size_type pos) const
297{
298  if (1 > length ())
299    return npos;
300
301  size_t xpos = length () - 1;
302  if (xpos > pos)
303    xpos = pos;
304
305  for (++xpos; xpos-- > 0; )
306    if (traits::eq (data () [xpos], c))
307      return xpos;
308  return npos;
309}
310
311template <class charT, class traits, class Allocator>
312basic_string <charT, traits, Allocator>::size_type
313basic_string <charT, traits, Allocator>::
314find_first_of (const charT* s, size_type pos, size_type n) const
315{
316  size_t xpos = pos;
317  for (; xpos < length (); ++xpos)
318    if (_find (s, data () [xpos], 0, n) != npos)
319      return xpos;
320  return npos;
321}
322
323template <class charT, class traits, class Allocator>
324basic_string <charT, traits, Allocator>::size_type
325basic_string <charT, traits, Allocator>::
326find_last_of (const charT* s, size_type pos, size_type n) const
327{
328  if (length() == 0)
329    return npos;
330  size_t xpos = length () - 1;
331  if (xpos > pos)
332    xpos = pos;
333  for (++xpos; xpos-- > 0;)
334    if (_find (s, data () [xpos], 0, n) != npos)
335      return xpos;
336  return npos;
337}
338
339template <class charT, class traits, class Allocator>
340basic_string <charT, traits, Allocator>::size_type
341basic_string <charT, traits, Allocator>::
342find_first_not_of (const charT* s, size_type pos, size_type n) const
343{
344  size_t xpos = pos;
345  for (; xpos < length (); ++xpos)
346    if (_find (s, data () [xpos], 0, n) == npos)
347      return xpos;
348  return npos;
349}
350
351template <class charT, class traits, class Allocator>
352basic_string <charT, traits, Allocator>::size_type
353basic_string <charT, traits, Allocator>::
354find_first_not_of (charT c, size_type pos) const
355{
356  size_t xpos = pos;
357  for (; xpos < length (); ++xpos)
358    if (traits::ne (data () [xpos], c))
359      return xpos;
360  return npos;
361}
362
363template <class charT, class traits, class Allocator>
364basic_string <charT, traits, Allocator>::size_type
365basic_string <charT, traits, Allocator>::
366find_last_not_of (const charT* s, size_type pos, size_type n) const
367{
368  if (length() == 0)
369    return npos;
370  size_t xpos = length () - 1;
371  if (xpos > pos)
372    xpos = pos;
373  for (++xpos; xpos-- > 0;)
374    if (_find (s, data () [xpos], 0, n) == npos)
375      return xpos;
376  return npos;
377}
378
379template <class charT, class traits, class Allocator>
380basic_string <charT, traits, Allocator>::size_type
381basic_string <charT, traits, Allocator>::
382find_last_not_of (charT c, size_type pos) const
383{
384  if (length() == 0)
385    return npos;
386  size_t xpos = length () - 1;
387  if (xpos > pos)
388    xpos = pos;
389  for (++xpos; xpos-- > 0;)
390    if (traits::ne (data () [xpos], c))
391      return xpos;
392  return npos;
393}
394
395template <class charT, class traits, class Allocator>
396int basic_string <charT, traits, Allocator>::
397compare (const basic_string& _str, size_type pos, size_type n) const
398{
399  OUTOFRANGE (pos > length ());
400
401  size_t rlen = length () - pos;
402  if (rlen > n)
403    rlen = n;
404  if (rlen > _str.length ())
405    rlen = _str.length ();
406  int r = traits::compare (data () + pos, _str.data (), rlen);
407  if (r != 0)
408    return r;
409  if (rlen == n)
410    return 0;
411  return (length () - pos) - _str.length ();
412}
413
414template <class charT, class traits, class Allocator>
415int basic_string <charT, traits, Allocator>::
416compare (const charT* s, size_type pos, size_type n) const
417{
418  OUTOFRANGE (pos > length ());
419
420  size_t rlen = length () - pos;
421  if (rlen > n)
422    rlen = n;
423  int r = traits::compare (data () + pos, s, rlen);
424  if (r != 0)
425    return r;
426  return (length () - pos) - n;
427}
428
429#include <iostream.h>
430
431template <class charT, class traits, class Allocator>
432istream &
433operator>> (istream &is, basic_string <charT, traits, Allocator> &s)
434{
435  int w = is.width (0);
436  if (is.ipfx0 ())
437    {
438      register streambuf *sb = is.rdbuf ();
439      s.resize (0);
440      while (1)
441	{
442	  int ch = sb->sbumpc ();
443	  if (ch == EOF)
444	    {
445	      is.setstate (ios::eofbit);
446	      break;
447	    }
448	  else if (traits::is_del (ch))
449	    {
450	      sb->sungetc ();
451	      break;
452	    }
453	  s += static_cast<charT> (ch);
454	  if (--w == 1)
455	    break;
456	}
457    }
458
459  is.isfx ();
460  if (s.length () == 0)
461    is.setstate (ios::failbit);
462
463  return is;
464}
465
466template <class charT, class traits, class Allocator>
467ostream &
468operator<< (ostream &o, const basic_string <charT, traits, Allocator>& s)
469{
470  return o.write (s.data (), s.length ());
471}
472
473template <class charT, class traits, class Allocator>
474istream&
475getline (istream &is, basic_string <charT, traits, Allocator>& s, charT delim)
476{
477  if (is.ipfx1 ())
478    {
479      _IO_size_t _count = 0;
480      streambuf *sb = is.rdbuf ();
481      s.resize (0);
482
483      while (1)
484	{
485	  int ch = sb->sbumpc ();
486	  if (ch == EOF)
487	    {
488	      is.setstate (_count == 0
489			   ? (ios::failbit|ios::eofbit)
490			   : ios::eofbit);
491	      break;
492	    }
493
494	  ++_count;
495
496	  if (ch == delim)
497	    break;
498
499	  s += static_cast<charT> (ch);
500
501	  if (s.length () == s.npos - 1)
502	    {
503	      is.setstate (ios::failbit);
504	      break;
505	    }
506	}
507    }
508
509  // We need to be friends with istream to do this.
510  // is._gcount = _count;
511  is.isfx ();
512
513  return is;
514}
515
516template <class charT, class traits, class Allocator>
517basic_string <charT, traits, Allocator>::Rep
518basic_string<charT, traits, Allocator>::nilRep = { 0, 0, 1, false };
519
520template <class charT, class traits, class Allocator>
521const basic_string <charT, traits, Allocator>::size_type
522basic_string <charT, traits, Allocator>::npos;
523
524} // extern "C++"
525