1 /*
2 Copyright (C) 2001-2006, William Joseph.
3 All Rights Reserved.
4
5 This file is part of GtkRadiant.
6
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 */
21
22 #if !defined( INCLUDED_STRING_STRING_H )
23 #define INCLUDED_STRING_STRING_H
24
25 /// \file
26 /// C-style null-terminated-character-array string library.
27
28 #include <cstring>
29 #include <cctype>
30 #include <algorithm>
31
32 #include "memory/allocator.h"
33 #include "generic/arrayrange.h"
34
35 /// \brief Returns true if \p string length is zero.
36 /// O(1)
string_empty(const char * string)37 inline bool string_empty( const char* string ){
38 return *string == '\0';
39 }
40
41 /// \brief Returns true if \p string length is not zero.
42 /// O(1)
string_not_empty(const char * string)43 inline bool string_not_empty( const char* string ){
44 return !string_empty( string );
45 }
46
47 /// \brief Returns <0 if \p string is lexicographically less than \p other.
48 /// Returns >0 if \p string is lexicographically greater than \p other.
49 /// Returns 0 if \p string is lexicographically equal to \p other.
50 /// O(n)
string_compare(const char * string,const char * other)51 inline int string_compare( const char* string, const char* other ){
52 return std::strcmp( string, other );
53 }
54
55 /// \brief Returns true if \p string is lexicographically equal to \p other.
56 /// O(n)
string_equal(const char * string,const char * other)57 inline bool string_equal( const char* string, const char* other ){
58 return string_compare( string, other ) == 0;
59 }
60
61 /// \brief Returns true if [\p string, \p string + \p n) is lexicographically equal to [\p other, \p other + \p n).
62 /// O(n)
string_equal_n(const char * string,const char * other,std::size_t n)63 inline bool string_equal_n( const char* string, const char* other, std::size_t n ){
64 return std::strncmp( string, other, n ) == 0;
65 }
66
67 /// \brief Returns true if \p string is lexicographically less than \p other.
68 /// O(n)
string_less(const char * string,const char * other)69 inline bool string_less( const char* string, const char* other ){
70 return string_compare( string, other ) < 0;
71 }
72
73 /// \brief Returns true if \p string is lexicographically greater than \p other.
74 /// O(n)
string_greater(const char * string,const char * other)75 inline bool string_greater( const char* string, const char* other ){
76 return string_compare( string, other ) > 0;
77 }
78
79 /// \brief Returns <0 if \p string is lexicographically less than \p other after converting both to lower-case.
80 /// Returns >0 if \p string is lexicographically greater than \p other after converting both to lower-case.
81 /// Returns 0 if \p string is lexicographically equal to \p other after converting both to lower-case.
82 /// O(n)
string_compare_nocase(const char * string,const char * other)83 inline int string_compare_nocase( const char* string, const char* other ){
84 #ifdef WIN32
85 return _stricmp( string, other );
86 #else
87 return strcasecmp( string, other );
88 #endif
89 }
90
91 /// \brief Returns <0 if [\p string, \p string + \p n) is lexicographically less than [\p other, \p other + \p n).
92 /// Returns >0 if [\p string, \p string + \p n) is lexicographically greater than [\p other, \p other + \p n).
93 /// Returns 0 if [\p string, \p string + \p n) is lexicographically equal to [\p other, \p other + \p n).
94 /// Treats all ascii characters as lower-case during comparisons.
95 /// O(n)
string_compare_nocase_n(const char * string,const char * other,std::size_t n)96 inline int string_compare_nocase_n( const char* string, const char* other, std::size_t n ){
97 #ifdef WIN32
98 return _strnicmp( string, other, n );
99 #else
100 return strncasecmp( string, other, n );
101 #endif
102 }
103
104 /// \brief Returns true if \p string is lexicographically equal to \p other.
105 /// Treats all ascii characters as lower-case during comparisons.
106 /// O(n)
string_equal_nocase(const char * string,const char * other)107 inline bool string_equal_nocase( const char* string, const char* other ){
108 return string_compare_nocase( string, other ) == 0;
109 }
110
111 /// \brief Returns true if [\p string, \p string + \p n) is lexicographically equal to [\p other, \p other + \p n).
112 /// Treats all ascii characters as lower-case during comparisons.
113 /// O(n)
string_equal_nocase_n(const char * string,const char * other,std::size_t n)114 inline bool string_equal_nocase_n( const char* string, const char* other, std::size_t n ){
115 return string_compare_nocase_n( string, other, n ) == 0;
116 }
117
118 /// \brief Returns true if \p string is lexicographically less than \p other.
119 /// Treats all ascii characters as lower-case during comparisons.
120 /// O(n)
string_less_nocase(const char * string,const char * other)121 inline bool string_less_nocase( const char* string, const char* other ){
122 return string_compare_nocase( string, other ) < 0;
123 }
124
125 /// \brief Returns true if \p string is lexicographically greater than \p other.
126 /// Treats all ascii characters as lower-case during comparisons.
127 /// O(n)
string_greater_nocase(const char * string,const char * other)128 inline bool string_greater_nocase( const char* string, const char* other ){
129 return string_compare_nocase( string, other ) > 0;
130 }
131
132 /// \brief Returns the number of non-null characters in \p string.
133 /// O(n)
string_length(const char * string)134 inline std::size_t string_length( const char* string ){
135 return std::strlen( string );
136 }
137
138 /// \brief Returns true if the beginning of \p string is equal to \p prefix.
139 /// O(n)
string_equal_prefix(const char * string,const char * prefix)140 inline bool string_equal_prefix( const char* string, const char* prefix ){
141 return string_equal_n( string, prefix, string_length( prefix ) );
142 }
143
144 /// \brief Copies \p other into \p string and returns \p string.
145 /// Assumes that the space allocated for \p string is at least string_length(other) + 1.
146 /// O(n)
string_copy(char * string,const char * other)147 inline char* string_copy( char* string, const char* other ){
148 return std::strcpy( string, other );
149 }
150
151 /// \brief Allocates a string buffer large enough to hold \p length characters, using \p allocator.
152 /// The returned buffer must be released with \c string_release using a matching \p allocator.
153 template<typename Allocator>
string_new(std::size_t length,Allocator & allocator)154 inline char* string_new( std::size_t length, Allocator& allocator ){
155 return allocator.allocate( length + 1 );
156 }
157
158 /// \brief Deallocates the \p buffer large enough to hold \p length characters, using \p allocator.
159 template<typename Allocator>
string_release(char * buffer,std::size_t length,Allocator & allocator)160 inline void string_release( char* buffer, std::size_t length, Allocator& allocator ){
161 allocator.deallocate( buffer, length + 1 );
162 }
163
164 /// \brief Returns a newly-allocated string which is a clone of \p other, using \p allocator.
165 /// The returned buffer must be released with \c string_release using a matching \p allocator.
166 template<typename Allocator>
string_clone(const char * other,Allocator & allocator)167 inline char* string_clone( const char* other, Allocator& allocator ){
168 char* copied = string_new( string_length( other ), allocator );
169 std::strcpy( copied, other );
170 return copied;
171 }
172
173 /// \brief Returns a newly-allocated string which is a clone of [\p first, \p last), using \p allocator.
174 /// The returned buffer must be released with \c string_release using a matching \p allocator.
175 template<typename Allocator>
string_clone_range(StringRange range,Allocator & allocator)176 inline char* string_clone_range( StringRange range, Allocator& allocator ){
177 std::size_t length = range.last - range.first;
178 char* copied = strncpy( string_new( length, allocator ), range.first, length );
179 copied[length] = '\0';
180 return copied;
181 }
182
183 /// \brief Allocates a string buffer large enough to hold \p length characters.
184 /// The returned buffer must be released with \c string_release.
string_new(std::size_t length)185 inline char* string_new( std::size_t length ){
186 DefaultAllocator<char> allocator;
187 return string_new( length, allocator );
188 }
189
190 /// \brief Deallocates the \p buffer large enough to hold \p length characters.
string_release(char * string,std::size_t length)191 inline void string_release( char* string, std::size_t length ){
192 DefaultAllocator<char> allocator;
193 string_release( string, length, allocator );
194 }
195
196 /// \brief Returns a newly-allocated string which is a clone of \p other.
197 /// The returned buffer must be released with \c string_release.
string_clone(const char * other)198 inline char* string_clone( const char* other ){
199 DefaultAllocator<char> allocator;
200 return string_clone( other, allocator );
201 }
202
203 /// \brief Returns a newly-allocated string which is a clone of [\p first, \p last).
204 /// The returned buffer must be released with \c string_release.
string_clone_range(StringRange range)205 inline char* string_clone_range( StringRange range ){
206 DefaultAllocator<char> allocator;
207 return string_clone_range( range, allocator );
208 }
209
210 typedef char* char_pointer;
211 /// \brief Swaps the values of \p string and \p other.
string_swap(char_pointer & string,char_pointer & other)212 inline void string_swap( char_pointer& string, char_pointer& other ){
213 std::swap( string, other );
214 }
215
216 typedef const char* char_const_pointer;
217 /// \brief Swaps the values of \p string and \p other.
string_swap(char_const_pointer & string,char_const_pointer & other)218 inline void string_swap( char_const_pointer& string, char_const_pointer& other ){
219 std::swap( string, other );
220 }
221
222 /// \brief Converts each character of \p string to lower-case and returns \p string.
223 /// O(n)
string_to_lowercase(char * string)224 inline char* string_to_lowercase( char* string ){
225 for ( char* p = string; *p != '\0'; ++p )
226 {
227 *p = (char)std::tolower( *p );
228 }
229 return string;
230 }
231
232 /// \brief Converts each character of \p string to upper-case and returns \p string.
233 /// O(n)
string_to_uppercase(char * string)234 inline char* string_to_uppercase( char* string ){
235 for ( char* p = string; *p != '\0'; ++p )
236 {
237 *p = (char)std::toupper( *p );
238 }
239 return string;
240 }
241
242 /// \brief A re-entrant string tokeniser similar to strchr.
243 class StringTokeniser
244 {
istoken(char c)245 bool istoken( char c ) const {
246 if ( strchr( m_delimiters, c ) != 0 ) {
247 return false;
248 }
249 return true;
250 }
advance()251 const char* advance(){
252 const char* token = m_pos;
253 bool intoken = true;
254 while ( !string_empty( m_pos ) )
255 {
256 if ( !istoken( *m_pos ) ) {
257 *m_pos = '\0';
258 intoken = false;
259 }
260 else if ( !intoken ) {
261 return token;
262 }
263 ++m_pos;
264 }
265 return token;
266 }
267 std::size_t m_length;
268 char* m_string;
269 char* m_pos;
270 const char* m_delimiters;
271 public:
272 StringTokeniser( const char* string, const char* delimiters = " \n\r\t\v" ) :
m_length(string_length (string))273 m_length( string_length( string ) ),
274 m_string( string_copy( string_new( m_length ), string ) ),
275 m_pos( m_string ),
276 m_delimiters( delimiters ){
277 while ( !string_empty( m_pos ) && !istoken( *m_pos ) )
278 {
279 ++m_pos;
280 }
281 }
~StringTokeniser()282 ~StringTokeniser(){
283 string_release( m_string, m_length );
284 }
285 /// \brief Returns the next token or "" if there are no more tokens available.
getToken()286 const char* getToken(){
287 return advance();
288 }
289 };
290
291 /// \brief A non-mutable c-style string.
292 ///
293 /// \param Buffer The string storage implementation. Must be DefaultConstructible, CopyConstructible and Assignable. Must implement:
294 /// \li Buffer(const char* string) - constructor which copies a c-style \p string.
295 /// \li Buffer(const char* first, const char*) - constructor which copies a c-style string range [\p first, \p last).
296 /// \li void swap(Buffer& other) - swaps contents with \p other.
297 /// \li const char* c_str() - returns the stored non-mutable c-style string.
298 template<typename Buffer>
299 class String : public Buffer
300 {
301 public:
302
String()303 String()
304 : Buffer(){
305 }
String(const char * string)306 String( const char* string )
307 : Buffer( string ){
308 }
String(StringRange range)309 String( StringRange range )
310 : Buffer( range ){
311 }
312
313 String& operator=( const String& other ){
314 String temp( other );
315 temp.swap( *this );
316 return *this;
317 }
318 String& operator=( const char* string ){
319 String temp( string );
320 temp.swap( *this );
321 return *this;
322 }
323 String& operator=( StringRange range ){
324 String temp( range );
325 temp.swap( *this );
326 return *this;
327 }
328
swap(String & other)329 void swap( String& other ){
330 Buffer::swap( other );
331 }
332
empty()333 bool empty() const {
334 return string_empty( Buffer::c_str() );
335 }
336 };
337
338 template<typename Buffer>
339 inline bool operator<( const String<Buffer>& self, const String<Buffer>& other ){
340 return string_less( self.c_str(), other.c_str() );
341 }
342
343 template<typename Buffer>
344 inline bool operator>( const String<Buffer>& self, const String<Buffer>& other ){
345 return string_greater( self.c_str(), other.c_str() );
346 }
347
348 template<typename Buffer>
349 inline bool operator==( const String<Buffer>& self, const String<Buffer>& other ){
350 return string_equal( self.c_str(), other.c_str() );
351 }
352
353 template<typename Buffer>
354 inline bool operator!=( const String<Buffer>& self, const String<Buffer>& other ){
355 return !string_equal( self.c_str(), other.c_str() );
356 }
357
358 template<typename Buffer>
359 inline bool operator==( const String<Buffer>& self, const char* other ){
360 return string_equal( self.c_str(), other );
361 }
362
363 template<typename Buffer>
364 inline bool operator!=( const String<Buffer>& self, const char* other ){
365 return !string_equal( self.c_str(), other );
366 }
367
368 namespace std
369 {
370 /// \brief Swaps the values of \p self and \p other.
371 /// Overloads std::swap.
372 template<typename Buffer>
swap(String<Buffer> & self,String<Buffer> & other)373 inline void swap( String<Buffer>& self, String<Buffer>& other ){
374 self.swap( other );
375 }
376 }
377
378
379 /// \brief A non-mutable string buffer which manages memory allocation.
380 template<typename Allocator>
381 class CopiedBuffer : private Allocator
382 {
383 char* m_string;
384
copy_range(StringRange range)385 char* copy_range( StringRange range ){
386 return string_clone_range( range, static_cast<Allocator&>( *this ) );
387 }
copy(const char * other)388 char* copy( const char* other ){
389 return string_clone( other, static_cast<Allocator&>( *this ) );
390 }
destroy(char * string)391 void destroy( char* string ){
392 string_release( string, string_length( string ), static_cast<Allocator&>( *this ) );
393 }
394
395 protected:
~CopiedBuffer()396 ~CopiedBuffer(){
397 destroy( m_string );
398 }
399 public:
CopiedBuffer()400 CopiedBuffer()
401 : m_string( copy( "" ) ){
402 }
CopiedBuffer(const Allocator & allocator)403 explicit CopiedBuffer( const Allocator& allocator )
404 : Allocator( allocator ), m_string( copy( "" ) ){
405 }
CopiedBuffer(const CopiedBuffer & other)406 CopiedBuffer( const CopiedBuffer& other )
407 : Allocator( other ), m_string( copy( other.m_string ) ){
408 }
409 CopiedBuffer( const char* string, const Allocator& allocator = Allocator() )
Allocator(allocator)410 : Allocator( allocator ), m_string( copy( string ) ){
411 }
412 CopiedBuffer( StringRange range, const Allocator& allocator = Allocator() )
Allocator(allocator)413 : Allocator( allocator ), m_string( copy_range( range ) ){
414 }
c_str()415 const char* c_str() const {
416 return m_string;
417 }
swap(CopiedBuffer & other)418 void swap( CopiedBuffer& other ){
419 string_swap( m_string, other.m_string );
420 }
421 };
422
423 /// \brief A non-mutable string which uses copy-by-value for assignment.
424 typedef String< CopiedBuffer< DefaultAllocator<char> > > CopiedString;
425
426
427 /// \brief A non-mutable string buffer which uses reference-counting to avoid unnecessary allocations.
428 template<typename Allocator>
429 class SmartBuffer : private Allocator
430 {
431 char* m_buffer;
432
copy_range(StringRange range)433 char* copy_range( StringRange range ){
434 char* buffer = Allocator::allocate( sizeof( std::size_t ) + ( range.last - range.first ) + 1 );
435 strncpy( buffer + sizeof( std::size_t ), range.first, range.last - range.first );
436 buffer[sizeof( std::size_t ) + ( range.last - range.first )] = '\0';
437 *reinterpret_cast<std::size_t*>( buffer ) = 0;
438 return buffer;
439 }
copy(const char * string)440 char* copy( const char* string ){
441 char* buffer = Allocator::allocate( sizeof( std::size_t ) + string_length( string ) + 1 );
442 strcpy( buffer + sizeof( std::size_t ), string );
443 *reinterpret_cast<std::size_t*>( buffer ) = 0;
444 return buffer;
445 }
destroy(char * buffer)446 void destroy( char* buffer ){
447 Allocator::deallocate( buffer, sizeof( std::size_t ) + string_length( c_str() ) + 1 );
448 }
449
incref(char * buffer)450 void incref( char* buffer ){
451 ++( *reinterpret_cast<std::size_t*>( buffer ) );
452 }
decref(char * buffer)453 void decref( char* buffer ){
454 if ( --( *reinterpret_cast<std::size_t*>( buffer ) ) == 0 ) {
455 destroy( buffer );
456 }
457 }
458
459 protected:
~SmartBuffer()460 ~SmartBuffer(){
461 decref( m_buffer );
462 }
463 public:
SmartBuffer()464 SmartBuffer()
465 : m_buffer( copy( "" ) ){
466 incref( m_buffer );
467 }
SmartBuffer(const Allocator & allocator)468 explicit SmartBuffer( const Allocator& allocator )
469 : Allocator( allocator ), m_buffer( copy( "" ) ){
470 incref( m_buffer );
471 }
SmartBuffer(const SmartBuffer & other)472 SmartBuffer( const SmartBuffer& other )
473 : Allocator( other ), m_buffer( other.m_buffer ){
474 incref( m_buffer );
475 }
476 SmartBuffer( const char* string, const Allocator& allocator = Allocator() )
Allocator(allocator)477 : Allocator( allocator ), m_buffer( copy( string ) ){
478 incref( m_buffer );
479 }
480 SmartBuffer( StringRange range, const Allocator& allocator = Allocator() )
Allocator(allocator)481 : Allocator( allocator ), m_buffer( copy_range( range ) ){
482 incref( m_buffer );
483 }
c_str()484 const char* c_str() const {
485 return m_buffer + sizeof( std::size_t );
486 }
swap(SmartBuffer & other)487 void swap( SmartBuffer& other ){
488 string_swap( m_buffer, other.m_buffer );
489 }
490 };
491
492 /// \brief A non-mutable string which uses copy-by-reference for assignment of SmartString.
493 typedef String< SmartBuffer< DefaultAllocator<char> > > SmartString;
494
495 class StringEqualNoCase
496 {
497 public:
operator()498 bool operator()( const CopiedString& key, const CopiedString& other ) const {
499 return string_equal_nocase( key.c_str(), other.c_str() );
500 }
501 };
502
503 struct StringLessNoCase
504 {
operatorStringLessNoCase505 bool operator()( const CopiedString& x, const CopiedString& y ) const {
506 return string_less_nocase( x.c_str(), y.c_str() );
507 }
508 };
509
510 struct RawStringEqual
511 {
operatorRawStringEqual512 bool operator()( const char* x, const char* y ) const {
513 return string_equal( x, y );
514 }
515 };
516
517 struct RawStringLess
518 {
operatorRawStringLess519 bool operator()( const char* x, const char* y ) const {
520 return string_less( x, y );
521 }
522 };
523
524 struct RawStringLessNoCase
525 {
operatorRawStringLessNoCase526 bool operator()( const char* x, const char* y ) const {
527 return string_less_nocase( x, y );
528 }
529 };
530
531 #endif
532