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