unvanquished filesystem
[xonotic/netradiant.git] / libs / string / string.h
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
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 Returns true if the ending of \p string is equal to \p suffix.
145 /// O(n)
146 inline bool string_equal_suffix( const char* string, const char* suffix){
147         const char *s = string + string_length( string ) - string_length( suffix );
148         return string_equal_n( s , suffix, string_length( suffix ) );
149 }
150
151 /// \brief Copies \p other into \p string and returns \p string.
152 /// Assumes that the space allocated for \p string is at least string_length(other) + 1.
153 /// O(n)
154 inline char* string_copy( char* string, const char* other ){
155         return std::strcpy( string, other );
156 }
157
158 /// \brief Allocates a string buffer large enough to hold \p length characters, using \p allocator.
159 /// The returned buffer must be released with \c string_release using a matching \p allocator.
160 template<typename Allocator>
161 inline char* string_new( std::size_t length, Allocator& allocator ){
162         return allocator.allocate( length + 1 );
163 }
164
165 /// \brief Deallocates the \p buffer large enough to hold \p length characters, using \p allocator.
166 template<typename Allocator>
167 inline void string_release( char* buffer, std::size_t length, Allocator& allocator ){
168         allocator.deallocate( buffer, length + 1 );
169 }
170
171 /// \brief Returns a newly-allocated string which is a clone of \p other, using \p allocator.
172 /// The returned buffer must be released with \c string_release using a matching \p allocator.
173 template<typename Allocator>
174 inline char* string_clone( const char* other, Allocator& allocator ){
175         char* copied = string_new( string_length( other ), allocator );
176         std::strcpy( copied, other );
177         return copied;
178 }
179
180 /// \brief Returns a newly-allocated string which is a clone of [\p first, \p last), using \p allocator.
181 /// The returned buffer must be released with \c string_release using a matching \p allocator.
182 template<typename Allocator>
183 inline char* string_clone_range( StringRange range, Allocator& allocator ){
184         std::size_t length = range.last - range.first;
185         char* copied = strncpy( string_new( length, allocator ), range.first, length );
186         copied[length] = '\0';
187         return copied;
188 }
189
190 /// \brief Allocates a string buffer large enough to hold \p length characters.
191 /// The returned buffer must be released with \c string_release.
192 inline char* string_new( std::size_t length ){
193         DefaultAllocator<char> allocator;
194         return string_new( length, allocator );
195 }
196
197 /// \brief Allocates a new buffer large enough to hold two concatenated strings and fills it with strings.
198 inline char* string_new_concat( const char* a, const char* b ){
199         char* str = string_new( string_length( a ) + string_length( b ) );
200         strcpy( str, a );
201         strcat( str, b );
202         return str;
203 }
204
205 /// \brief Deallocates the \p buffer large enough to hold \p length characters.
206 inline void string_release( char* string, std::size_t length ){
207         DefaultAllocator<char> allocator;
208         string_release( string, length, allocator );
209 }
210
211 /// \brief Returns a newly-allocated string which is a clone of \p other.
212 /// The returned buffer must be released with \c string_release.
213 inline char* string_clone( const char* other ){
214         DefaultAllocator<char> allocator;
215         return string_clone( other, allocator );
216 }
217
218 /// \brief Returns a newly-allocated string which is a clone of [\p first, \p last).
219 /// The returned buffer must be released with \c string_release.
220 inline char* string_clone_range( StringRange range ){
221         DefaultAllocator<char> allocator;
222         return string_clone_range( range, allocator );
223 }
224
225 typedef char* char_pointer;
226 /// \brief Swaps the values of \p string and \p other.
227 inline void string_swap( char_pointer& string, char_pointer& other ){
228         std::swap( string, other );
229 }
230
231 typedef const char* char_const_pointer;
232 /// \brief Swaps the values of \p string and \p other.
233 inline void string_swap( char_const_pointer& string, char_const_pointer& other ){
234         std::swap( string, other );
235 }
236
237 /// \brief Converts each character of \p string to lower-case and returns \p string.
238 /// O(n)
239 inline char* string_to_lowercase( char* string ){
240         for ( char* p = string; *p != '\0'; ++p )
241         {
242                 *p = (char)std::tolower( *p );
243         }
244         return string;
245 }
246
247 /// \brief Converts each character of \p string to upper-case and returns \p string.
248 /// O(n)
249 inline char* string_to_uppercase( char* string ){
250         for ( char* p = string; *p != '\0'; ++p )
251         {
252                 *p = (char)std::toupper( *p );
253         }
254         return string;
255 }
256
257 /// \brief A re-entrant string tokeniser similar to strchr.
258 class StringTokeniser
259 {
260 bool istoken( char c ) const {
261         if ( strchr( m_delimiters, c ) != 0 ) {
262                 return false;
263         }
264         return true;
265 }
266 const char* advance(){
267         const char* token = m_pos;
268         bool intoken = true;
269         while ( !string_empty( m_pos ) )
270         {
271                 if ( !istoken( *m_pos ) ) {
272                         *m_pos = '\0';
273                         intoken = false;
274                 }
275                 else if ( !intoken ) {
276                         return token;
277                 }
278                 ++m_pos;
279         }
280         return token;
281 }
282 std::size_t m_length;
283 char* m_string;
284 char* m_pos;
285 const char* m_delimiters;
286 public:
287 StringTokeniser( const char* string, const char* delimiters = " \n\r\t\v" ) :
288         m_length( string_length( string ) ),
289         m_string( string_copy( string_new( m_length ), string ) ),
290         m_pos( m_string ),
291         m_delimiters( delimiters ){
292         while ( !string_empty( m_pos ) && !istoken( *m_pos ) )
293         {
294                 ++m_pos;
295         }
296 }
297 ~StringTokeniser(){
298         string_release( m_string, m_length );
299 }
300 /// \brief Returns the next token or "" if there are no more tokens available.
301 const char* getToken(){
302         return advance();
303 }
304 };
305
306 /// \brief A non-mutable c-style string.
307 ///
308 /// \param Buffer The string storage implementation. Must be DefaultConstructible, CopyConstructible and Assignable. Must implement:
309 /// \li Buffer(const char* string) - constructor which copies a c-style \p string.
310 /// \li Buffer(const char* first, const char*) - constructor which copies a c-style string range [\p first, \p last).
311 /// \li void swap(Buffer& other) - swaps contents with \p other.
312 /// \li const char* c_str() - returns the stored non-mutable c-style string.
313 template<typename Buffer>
314 class String : public Buffer
315 {
316 public:
317
318 String()
319         : Buffer(){
320 }
321 String( const char* string )
322         : Buffer( string ){
323 }
324 String( StringRange range )
325         : Buffer( range ){
326 }
327
328 String& operator=( const String& other ){
329         String temp( other );
330         temp.swap( *this );
331         return *this;
332 }
333 String& operator=( const char* string ){
334         String temp( string );
335         temp.swap( *this );
336         return *this;
337 }
338 String& operator=( StringRange range ){
339         String temp( range );
340         temp.swap( *this );
341         return *this;
342 }
343
344 void swap( String& other ){
345         Buffer::swap( other );
346 }
347
348 bool empty() const {
349         return string_empty( Buffer::c_str() );
350 }
351 };
352
353 template<typename Buffer>
354 inline bool operator<( const String<Buffer>& self, const String<Buffer>& other ){
355         return string_less( self.c_str(), other.c_str() );
356 }
357
358 template<typename Buffer>
359 inline bool operator>( const String<Buffer>& self, const String<Buffer>& other ){
360         return string_greater( self.c_str(), other.c_str() );
361 }
362
363 template<typename Buffer>
364 inline bool operator==( const String<Buffer>& self, const String<Buffer>& other ){
365         return string_equal( self.c_str(), other.c_str() );
366 }
367
368 template<typename Buffer>
369 inline bool operator!=( const String<Buffer>& self, const String<Buffer>& other ){
370         return !string_equal( self.c_str(), other.c_str() );
371 }
372
373 template<typename Buffer>
374 inline bool operator==( const String<Buffer>& self, const char* other ){
375         return string_equal( self.c_str(), other );
376 }
377
378 template<typename Buffer>
379 inline bool operator!=( const String<Buffer>& self, const char* other ){
380         return !string_equal( self.c_str(), other );
381 }
382
383 namespace std
384 {
385 /// \brief Swaps the values of \p self and \p other.
386 /// Overloads std::swap.
387 template<typename Buffer>
388 inline void swap( String<Buffer>& self, String<Buffer>& other ){
389         self.swap( other );
390 }
391 }
392
393
394 /// \brief A non-mutable string buffer which manages memory allocation.
395 template<typename Allocator>
396 class CopiedBuffer : private Allocator
397 {
398 char* m_string;
399
400 char* copy_range( StringRange range ){
401         return string_clone_range( range, static_cast<Allocator&>( *this ) );
402 }
403 char* copy( const char* other ){
404         return string_clone( other, static_cast<Allocator&>( *this ) );
405 }
406 void destroy( char* string ){
407         string_release( string, string_length( string ), static_cast<Allocator&>( *this ) );
408 }
409
410 protected:
411 ~CopiedBuffer(){
412         destroy( m_string );
413 }
414 public:
415 CopiedBuffer()
416         : m_string( copy( "" ) ){
417 }
418 explicit CopiedBuffer( const Allocator& allocator )
419         : Allocator( allocator ), m_string( copy( "" ) ){
420 }
421 CopiedBuffer( const CopiedBuffer& other )
422         : Allocator( other ), m_string( copy( other.m_string ) ){
423 }
424 CopiedBuffer( const char* string, const Allocator& allocator = Allocator() )
425         : Allocator( allocator ), m_string( copy( string ) ){
426 }
427 CopiedBuffer( StringRange range, const Allocator& allocator = Allocator() )
428         : Allocator( allocator ), m_string( copy_range( range ) ){
429 }
430 const char* c_str() const {
431         return m_string;
432 }
433 void swap( CopiedBuffer& other ){
434         string_swap( m_string, other.m_string );
435 }
436 };
437
438 /// \brief A non-mutable string which uses copy-by-value for assignment.
439 typedef String< CopiedBuffer< DefaultAllocator<char> > > CopiedString;
440
441
442 /// \brief A non-mutable string buffer which uses reference-counting to avoid unnecessary allocations.
443 template<typename Allocator>
444 class SmartBuffer : private Allocator
445 {
446 char* m_buffer;
447
448 char* copy_range( StringRange range ){
449         char* buffer = Allocator::allocate( sizeof( std::size_t ) + ( range.last - range.first ) + 1 );
450         strncpy( buffer + sizeof( std::size_t ), range.first, range.last - range.first );
451         buffer[sizeof( std::size_t ) + ( range.last - range.first )] = '\0';
452         *reinterpret_cast<std::size_t*>( buffer ) = 0;
453         return buffer;
454 }
455 char* copy( const char* string ){
456         char* buffer = Allocator::allocate( sizeof( std::size_t ) + string_length( string ) + 1 );
457         strcpy( buffer + sizeof( std::size_t ), string );
458         *reinterpret_cast<std::size_t*>( buffer ) = 0;
459         return buffer;
460 }
461 void destroy( char* buffer ){
462         Allocator::deallocate( buffer, sizeof( std::size_t ) + string_length( c_str() ) + 1 );
463 }
464
465 void incref( char* buffer ){
466         ++( *reinterpret_cast<std::size_t*>( buffer ) );
467 }
468 void decref( char* buffer ){
469         if ( --( *reinterpret_cast<std::size_t*>( buffer ) ) == 0 ) {
470                 destroy( buffer );
471         }
472 }
473
474 protected:
475 ~SmartBuffer(){
476         decref( m_buffer );
477 }
478 public:
479 SmartBuffer()
480         : m_buffer( copy( "" ) ){
481         incref( m_buffer );
482 }
483 explicit SmartBuffer( const Allocator& allocator )
484         : Allocator( allocator ), m_buffer( copy( "" ) ){
485         incref( m_buffer );
486 }
487 SmartBuffer( const SmartBuffer& other )
488         : Allocator( other ), m_buffer( other.m_buffer ){
489         incref( m_buffer );
490 }
491 SmartBuffer( const char* string, const Allocator& allocator = Allocator() )
492         : Allocator( allocator ), m_buffer( copy( string ) ){
493         incref( m_buffer );
494 }
495 SmartBuffer( StringRange range, const Allocator& allocator = Allocator() )
496         : Allocator( allocator ), m_buffer( copy_range( range ) ){
497         incref( m_buffer );
498 }
499 const char* c_str() const {
500         return m_buffer + sizeof( std::size_t );
501 }
502 void swap( SmartBuffer& other ){
503         string_swap( m_buffer, other.m_buffer );
504 }
505 };
506
507 /// \brief A non-mutable string which uses copy-by-reference for assignment of SmartString.
508 typedef String< SmartBuffer< DefaultAllocator<char> > > SmartString;
509
510 class StringEqualNoCase
511 {
512 public:
513 bool operator()( const CopiedString& key, const CopiedString& other ) const {
514         return string_equal_nocase( key.c_str(), other.c_str() );
515 }
516 };
517
518 struct StringLessNoCase
519 {
520         bool operator()( const CopiedString& x, const CopiedString& y ) const {
521                 return string_less_nocase( x.c_str(), y.c_str() );
522         }
523 };
524
525 struct RawStringEqual
526 {
527         bool operator()( const char* x, const char* y ) const {
528                 return string_equal( x, y );
529         }
530 };
531
532 struct RawStringLess
533 {
534         bool operator()( const char* x, const char* y ) const {
535                 return string_less( x, y );
536         }
537 };
538
539 struct RawStringLessNoCase
540 {
541         bool operator()( const char* x, const char* y ) const {
542                 return string_less_nocase( x, y );
543         }
544 };
545
546 #endif