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