1 // This file is part of the ustl library, an STL implementation.
3 // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
4 // This file is free software, distributed under the MIT License.
8 // STL basic_string equivalent functionality.
15 #include <stdio.h> // for vsnprintf (in string::format)
19 //----------------------------------------------------------------------
21 const uoff_t
string::npos
;
22 const string::size_type
string::size_Terminator
;
23 const string::value_type
string::c_Terminator
;
24 const char string::empty_string
[string::size_Terminator
] = "";
26 //----------------------------------------------------------------------
28 /// Creates an empty string.
32 link (VectorBlock(empty_string
)-1);
35 /// Assigns itself the value of string \p s
36 string::string (const string
& s
)
40 link (s
.c_str(), s
.size());
46 string::string (const_pointer s
)
54 /// Creates a string of length \p n filled with character \p c.
55 string::string (size_type n
, value_type c
)
59 fill_n (begin(), n
, c
);
62 /// Resize the string to \p n characters. New space contents is undefined.
63 void string::resize (size_type n
)
69 /// Assigns itself the value of string \p s
70 void string::assign (const_pointer s
)
74 assign (s
, strlen (s
));
77 /// Assigns itself the value of string \p s of length \p len.
78 void string::assign (const_pointer s
, size_type len
)
80 while (len
&& s
[len
- 1] == c_Terminator
)
86 /// Appends to itself the value of string \p s of length \p len.
87 void string::append (const_pointer s
)
91 append (s
, strlen (s
));
94 /// Appends to itself the value of string \p s of length \p len.
95 void string::append (const_pointer s
, size_type len
)
97 while (len
&& s
[len
- 1] == c_Terminator
)
99 resize (size() + len
);
100 copy_n (s
, len
, end() - len
);
103 /// Appends to itself \p n characters of value \p c.
104 void string::append (size_type n
, value_type c
)
107 fill_n (end() - n
, n
, c
);
110 /// Copies into itself at offset \p start, the value of string \p p of length \p n.
111 string::size_type
string::copyto (pointer p
, size_type n
, const_iterator start
) const
116 const size_type btc
= min(n
- size_Terminator
, size());
117 copy_n (start
, btc
, p
);
118 p
[btc
] = c_Terminator
;
119 return (btc
+ size_Terminator
);
122 /// Returns comparison value regarding string \p s.
123 /// The return value is:
124 /// \li 1 if this string is greater (by value, not length) than string \p s
125 /// \li 0 if this string is equal to string \p s
126 /// \li -1 if this string is less than string \p s
128 /*static*/ int string::compare (const_iterator first1
, const_iterator last1
, const_iterator first2
, const_iterator last2
)
130 assert (first1
<= last1
&& (first2
<= last2
|| !last2
) && "Negative ranges result in memory allocation errors.");
131 const size_type len1
= distance (first1
, last1
), len2
= distance (first2
, last2
);
132 const int rvbylen
= sign (int(len1
- len2
));
133 int rv
= memcmp (first1
, first2
, min (len1
, len2
));
134 return (rv
? rv
: rvbylen
);
137 /// Returns true if this string is equal to string \p s.
138 bool string::operator== (const_pointer s
) const
142 return (size() == strlen(s
) && 0 == memcmp (c_str(), s
, size()));
145 /// Returns the beginning of character \p i.
146 string::const_iterator
string::wiat (uoff_t i
) const
148 utf8in_iterator
<string::const_iterator
> cfinder (begin());
150 return (cfinder
.base());
153 /// Inserts wide character \p c at \p ipo \p n times as a UTF-8 string.
155 /// \p ipo is a byte position, not a character position, and is intended
156 /// to be obtained from one of the find functions. Generally you are not
157 /// able to know the character position in a localized string; different
158 /// languages will have different character counts, so use find instead.
160 void string::insert (const uoff_t ipo
, wchar_t c
, size_type n
)
162 iterator
ip (iat(ipo
));
163 ip
= iterator (memblock::insert (memblock::iterator(ip
), n
* Utf8Bytes(c
)));
164 fill_n (utf8out (ip
), n
, c
);
165 *end() = c_Terminator
;
168 /// Inserts sequence of wide characters at \p ipo (byte position from a find call)
169 void string::insert (const uoff_t ipo
, const wchar_t* first
, const wchar_t* last
, const size_type n
)
171 iterator
ip (iat(ipo
));
172 size_type nti
= distance (first
, last
), bti
= 0;
173 for (uoff_t i
= 0; i
< nti
; ++ i
)
174 bti
+= Utf8Bytes(first
[i
]);
175 ip
= iterator (memblock::insert (memblock::iterator(ip
), n
* bti
));
176 utf8out_iterator
<string::iterator
> uout (utf8out (ip
));
177 for (uoff_t j
= 0; j
< n
; ++ j
)
178 for (uoff_t k
= 0; k
< nti
; ++ k
, ++ uout
)
180 *end() = c_Terminator
;
183 /// Inserts character \p c into this string at \p start.
184 string::iterator
string::insert (iterator start
, const_reference c
, size_type n
)
186 start
= iterator (memblock::insert (memblock::iterator(start
), n
));
187 fill_n (start
, n
, c
);
188 *end() = c_Terminator
;
192 /// Inserts \p count instances of string \p s at offset \p start.
193 string::iterator
string::insert (iterator start
, const_pointer s
, size_type n
)
197 return (insert (start
, s
, s
+ strlen(s
), n
));
200 /// Inserts [first,last] \p n times.
201 string::iterator
string::insert (iterator start
, const_pointer first
, const_pointer last
, size_type n
)
203 assert (first
<= last
);
204 assert (begin() <= start
&& end() >= start
);
205 assert ((first
< begin() || first
>= end() || size() + abs_distance(first
,last
) < capacity()) && "Insertion of self with autoresize is not supported");
206 start
= iterator (memblock::insert (memblock::iterator(start
), distance(first
, last
) * n
));
207 fill (memblock::iterator(start
), first
, distance(first
, last
), n
);
208 *end() = c_Terminator
;
212 /// Erases \p size bytes at \p ep.
213 string::iterator
string::erase (iterator ep
, size_type n
)
215 string::iterator rv
= memblock::erase (memblock::iterator(ep
), n
);
216 *end() = c_Terminator
;
220 /// Erases \p n bytes at byte offset \p epo.
221 void string::erase (uoff_t epo
, size_type n
)
226 /// Replaces range [\p start, \p start + \p len] with string \p s.
227 void string::replace (iterator first
, iterator last
, const_pointer s
)
231 replace (first
, last
, s
, s
+ strlen(s
));
234 /// Replaces range [\p start, \p start + \p len] with \p count instances of string \p s.
235 void string::replace (iterator first
, iterator last
, const_pointer i1
, const_pointer i2
, size_type n
)
237 assert (first
<= last
);
238 assert (n
|| distance(first
, last
));
239 assert (first
>= begin() && first
<= end() && last
>= first
&& last
<= end());
240 assert ((i1
< begin() || i1
>= end() || abs_distance(i1
,i2
) * n
+ size() < capacity()) && "Replacement by self can not autoresize");
241 const size_type bte
= distance(first
, last
), bti
= distance(i1
, i2
) * n
;
243 first
= iterator (memblock::erase (memblock::iterator(first
), bte
- bti
));
245 first
= iterator (memblock::insert (memblock::iterator(first
), bti
- bte
));
246 fill (memblock::iterator(first
), i1
, distance(i1
, i2
), n
);
247 *end() = c_Terminator
;
250 /// Returns the offset of the first occurence of \p c after \p pos.
251 uoff_t
string::find (const_reference c
, uoff_t pos
) const
253 const_iterator found
= ::ustl::find (iat(pos
), end(), c
);
254 return (found
< end() ? distance(begin(),found
) : npos
);
257 /// Returns the offset of the first occurence of substring \p s of length \p n after \p pos.
258 uoff_t
string::find (const string
& s
, uoff_t pos
) const
260 if (s
.empty() || s
.size() > size() - pos
)
262 const uoff_t endi
= s
.size() - 1;
263 const_reference endchar
= s
[endi
];
264 uoff_t lastPos
= endi
;
265 while (lastPos
-- && s
[lastPos
] != endchar
);
266 const size_type skip
= endi
- lastPos
;
267 const_iterator i
= iat(pos
) + endi
;
268 for (; i
< end() && (i
= ::ustl::find (i
, end(), endchar
)) < end(); i
+= skip
)
269 if (memcmp (i
- endi
, s
.c_str(), s
.size()) == 0)
270 return (distance (begin(), i
) - endi
);
274 /// Returns the offset of the last occurence of character \p c before \p pos.
275 uoff_t
string::rfind (const_reference c
, uoff_t pos
) const
277 for (int i
= min(pos
,size()-1); i
>= 0; --i
)
283 /// Returns the offset of the last occurence of substring \p s of size \p n before \p pos.
284 uoff_t
string::rfind (const string
& s
, uoff_t pos
) const
286 const_iterator d
= iat(pos
) - 1;
287 const_iterator sp
= begin() + s
.size() - 1;
288 const_iterator m
= s
.end() - 1;
289 for (uoff_t i
= 0; d
> sp
&& i
< s
.size(); -- d
)
290 for (i
= 0; i
< s
.size(); ++ i
)
293 return (d
> sp
? distance (begin(), d
+ 2 - s
.size()) : npos
);
296 /// Returns the offset of the first occurence of one of characters in \p s of size \p n after \p pos.
297 uoff_t
string::find_first_of (const string
& s
, uoff_t pos
) const
299 for (uoff_t i
= min(pos
,size()); i
< size(); ++ i
)
300 if (s
.find (at(i
)) != npos
)
305 /// Returns the offset of the first occurence of one of characters not in \p s of size \p n after \p pos.
306 uoff_t
string::find_first_not_of (const string
& s
, uoff_t pos
) const
308 for (uoff_t i
= min(pos
,size()); i
< size(); ++ i
)
309 if (s
.find (at(i
)) == npos
)
314 /// Returns the offset of the last occurence of one of characters in \p s of size \p n before \p pos.
315 uoff_t
string::find_last_of (const string
& s
, uoff_t pos
) const
317 for (int i
= min(pos
,size()-1); i
>= 0; -- i
)
318 if (s
.find (at(i
)) != npos
)
323 /// Returns the offset of the last occurence of one of characters not in \p s of size \p n before \p pos.
324 uoff_t
string::find_last_not_of (const string
& s
, uoff_t pos
) const
326 for (int i
= min(pos
,size()-1); i
>= 0; -- i
)
327 if (s
.find (at(i
)) == npos
)
332 /// Equivalent to a vsprintf on the string.
333 int string::vformat (const char* fmt
, va_list args
)
340 #define __va_copy(x,y)
345 __va_copy (args2
, args
);
346 rv
= vsnprintf (data(), memblock::capacity(), fmt
, args2
);
347 rv
= min (rv
, memblock::capacity());
348 } while (rv
> capacity());
349 resize (min (rv
, capacity()));
353 /// Equivalent to a sprintf on the string.
354 int string::format (const char* fmt
, ...)
357 va_start (args
, fmt
);
358 const int rv
= vformat (fmt
, args
);
363 /// Returns the number of bytes required to write this object to a stream.
364 size_t string::stream_size (void) const
366 return (Utf8Bytes(size()) + size());
369 /// Reads the object from stream \p os
370 void string::read (istream
& is
)
374 size_t szsz (Utf8SequenceBytes (szbuf
[0]) - 1), n
= 0;
375 is
.verify_remaining ("read", "ustl::string", szsz
);
376 is
.read (szbuf
+ 1, szsz
);
378 is
.verify_remaining ("read", "ustl::string", n
);
380 is
.read (data(), size());
383 /// Writes the object to stream \p os
384 void string::write (ostream
& os
) const
386 const written_size_type
sz (size());
387 assert (sz
== size() && "No support for writing strings larger than 4G");
390 utf8out_iterator
<char*> szout (szbuf
);
392 size_t szsz
= distance (szbuf
, szout
.base());
394 os
.verify_remaining ("write", "ustl::string", szsz
+ sz
);
395 os
.write (szbuf
, szsz
);
396 os
.write (cdata(), sz
);
399 /// Returns a hash value for [first, last)
400 /*static*/ hashvalue_t
string::hash (const char* first
, const char* last
)
403 // This has the bits flowing into each other from both sides of the number
404 for (; first
< last
; ++ first
)
405 h
= *first
+ ((h
<< 7) | (h
>> BitsInType(hashvalue_t
) - 7));