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 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)
 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>
 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>
 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>
 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>
 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.
 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.
 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.
 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.
 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.
 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.
 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)
 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)
 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 {
 245 bool istoken( char c ) const {
 246         if ( strchr( m_delimiters, c ) != 0 ) {
 247                 return false;
 248         }
 249         return true;
 250 }
 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" ) :
 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 }
 282 ~StringTokeniser(){
 283         string_release( m_string, m_length );
 284 }
 285 /// \brief Returns the next token or "" if there are no more tokens available.
 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
 303 String()
 304         : Buffer(){
 305 }
 306 String( const char* string )
 307         : Buffer( string ){
 308 }
 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
 329 void swap( String& other ){
 330         Buffer::swap( other );
 331 }
 332
 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>
 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
 385 char* copy_range( StringRange range ){
 386         return string_clone_range( range, static_cast<Allocator&>( *this ) );
 387 }
 388 char* copy( const char* other ){
 389         return string_clone( other, static_cast<Allocator&>( *this ) );
 390 }
 391 void destroy( char* string ){
 392         string_release( string, string_length( string ), static_cast<Allocator&>( *this ) );
 393 }
 394
 395 protected:
 396 ~CopiedBuffer(){
 397         destroy( m_string );
 398 }
 399 public:
 400 CopiedBuffer()
 401         : m_string( copy( "" ) ){
 402 }
 403 explicit CopiedBuffer( const Allocator& allocator )
 404         : Allocator( allocator ), m_string( copy( "" ) ){
 405 }
 406 CopiedBuffer( const CopiedBuffer& other )
 407         : Allocator( other ), m_string( copy( other.m_string ) ){
 408 }
 409 CopiedBuffer( const char* string, const Allocator& allocator = Allocator() )
 410         : Allocator( allocator ), m_string( copy( string ) ){
 411 }
 412 CopiedBuffer( StringRange range, const Allocator& allocator = Allocator() )
 413         : Allocator( allocator ), m_string( copy_range( range ) ){
 414 }
 415 const char* c_str() const {
 416         return m_string;
 417 }
 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
 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 }
 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 }
 446 void destroy( char* buffer ){
 447         Allocator::deallocate( buffer, sizeof( std::size_t ) + string_length( c_str() ) + 1 );
 448 }
 449
 450 void incref( char* buffer ){
 451         ++( *reinterpret_cast<std::size_t*>( buffer ) );
 452 }
 453 void decref( char* buffer ){
 454         if ( --( *reinterpret_cast<std::size_t*>( buffer ) ) == 0 ) {
 455                 destroy( buffer );
 456         }
 457 }
 458
 459 protected:
 460 ~SmartBuffer(){
 461         decref( m_buffer );
 462 }
 463 public:
 464 SmartBuffer()
 465         : m_buffer( copy( "" ) ){
 466         incref( m_buffer );
 467 }
 468 explicit SmartBuffer( const Allocator& allocator )
 469         : Allocator( allocator ), m_buffer( copy( "" ) ){
 470         incref( m_buffer );
 471 }
 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() )
 477         : Allocator( allocator ), m_buffer( copy( string ) ){
 478         incref( m_buffer );
 479 }
 480 SmartBuffer( StringRange range, const Allocator& allocator = Allocator() )
 481         : Allocator( allocator ), m_buffer( copy_range( range ) ){
 482         incref( m_buffer );
 483 }
 484 const char* c_str() const {
 485         return m_buffer + sizeof( std::size_t );
 486 }
 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:
 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 {
 505         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 {
 512         bool operator()( const char* x, const char* y ) const {
 513                 return string_equal( x, y );
 514         }
 515 };
 516
 517 struct RawStringLess
 518 {
 519         bool operator()( const char* x, const char* y ) const {
 520                 return string_less( x, y );
 521         }
 522 };
 523
 524 struct RawStringLessNoCase
 525 {
 526         bool operator()( const char* x, const char* y ) const {
 527                 return string_less_nocase( x, y );
 528         }
 529 };
 530
 531 #endif