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