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)
string_empty(const char * string)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)
string_not_empty(const char * string)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)
string_compare(const char * string,const char * other)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)
string_equal(const char * string,const char * other)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)
string_equal_n(const char * string,const char * other,std::size_t 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)
string_less(const char * string,const char * other)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)
string_greater(const char * string,const char * other)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)
string_compare_nocase(const char * string,const char * other)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)
string_compare_nocase_n(const char * string,const char * other,std::size_t 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)
string_equal_nocase(const char * string,const char * other)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)
string_equal_nocase_n(const char * string,const char * other,std::size_t 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)
string_less_nocase(const char * string,const char * other)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)
string_greater_nocase(const char * string,const char * other)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)
string_length(const char * string)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)
string_equal_prefix(const char * string,const char * prefix)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)
string_copy(char * string,const char * other)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>
string_new(std::size_t length,Allocator & 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>
string_release(char * buffer,std::size_t length,Allocator & 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>
string_clone(const char * other,Allocator & 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>
string_clone_range(const char * first,const char * last,Allocator & 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.
string_new(std::size_t length)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.
string_release(char * string,std::size_t length)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.
string_clone(const char * other)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.
string_clone_range(const char * first,const char * last)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.
string_swap(char_pointer & string,char_pointer & 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.
string_swap(char_const_pointer & string,char_const_pointer & 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)
string_to_lowercase(char * string)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)
string_to_uppercase(char * string)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 {
istoken(char c)272 bool istoken(char c) const
273 {
274 if(strchr(m_delimiters, c) != 0)
275 {
276 return false;
277 }
278 return true;
279 }
advance()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") :
m_length(string_length (string))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 }
~StringTokeniser()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.
getToken()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
String()338 String()
339 : Buffer()
340 {
341 }
String(const char * string)342 String(const char* string)
343 : Buffer(string)
344 {
345 }
String(const char * first,const char * last)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
swap(String & other)364 void swap(String& other)
365 {
366 Buffer::swap(other);
367 }
368
empty()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>
swap(String<Buffer> & self,String<Buffer> & other)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
copy_range(const char * first,const char * last)429 char* copy_range(const char* first, const char* last)
430 {
431 return string_clone_range(first, last, static_cast<Allocator&>(*this));
432 }
copy(const char * other)433 char* copy(const char* other)
434 {
435 return string_clone(other, static_cast<Allocator&>(*this));
436 }
destroy(char * string)437 void destroy(char* string)
438 {
439 string_release(string, string_length(string), static_cast<Allocator&>(*this));
440 }
441
442 protected:
~CopiedBuffer()443 ~CopiedBuffer()
444 {
445 destroy(m_string);
446 }
447 public:
CopiedBuffer()448 CopiedBuffer()
449 : m_string(copy(""))
450 {
451 }
CopiedBuffer(const Allocator & allocator)452 explicit CopiedBuffer(const Allocator& allocator)
453 : Allocator(allocator), m_string(copy(""))
454 {
455 }
CopiedBuffer(const CopiedBuffer & other)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())
Allocator(allocator)461 : Allocator(allocator), m_string(copy(string))
462 {
463 }
464 CopiedBuffer(const char* first, const char* last, const Allocator& allocator = Allocator())
Allocator(allocator)465 : Allocator(allocator), m_string(copy_range(first, last))
466 {
467 }
c_str()468 const char* c_str() const
469 {
470 return m_string;
471 }
swap(CopiedBuffer & other)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
copy_range(const char * first,const char * last)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 }
copy(const char * string)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 }
destroy(char * buffer)503 void destroy(char* buffer)
504 {
505 Allocator::deallocate(buffer, sizeof(std::size_t) + string_length(c_str()) + 1);
506 }
507
incref(char * buffer)508 void incref(char* buffer)
509 {
510 ++(*reinterpret_cast<std::size_t*>(buffer));
511 }
decref(char * buffer)512 void decref(char* buffer)
513 {
514 if(--(*reinterpret_cast<std::size_t*>(buffer)) == 0)
515 destroy(buffer);
516 }
517
518 protected:
~SmartBuffer()519 ~SmartBuffer()
520 {
521 decref(m_buffer);
522 }
523 public:
SmartBuffer()524 SmartBuffer()
525 : m_buffer(copy(""))
526 {
527 incref(m_buffer);
528 }
SmartBuffer(const Allocator & allocator)529 explicit SmartBuffer(const Allocator& allocator)
530 : Allocator(allocator), m_buffer(copy(""))
531 {
532 incref(m_buffer);
533 }
SmartBuffer(const SmartBuffer & other)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())
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())
Allocator(allocator)545 : Allocator(allocator), m_buffer(copy_range(first, last))
546 {
547 incref(m_buffer);
548 }
c_str()549 const char* c_str() const
550 {
551 return m_buffer + sizeof(std::size_t);
552 }
swap(SmartBuffer & other)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:
operator()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 {
operatorStringLessNoCase573 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 {
operatorRawStringEqual581 bool operator()(const char* x, const char* y) const
582 {
583 return string_equal(x, y);
584 }
585 };
586
587 struct RawStringLess
588 {
operatorRawStringLess589 bool operator()(const char* x, const char* y) const
590 {
591 return string_less(x, y);
592 }
593 };
594
595 struct RawStringLessNoCase
596 {
operatorRawStringLessNoCase597 bool operator()(const char* x, const char* y) const
598 {
599 return string_less_nocase(x, y);
600 }
601 };
602
603 #endif
604