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