remove RSA's md4.c, replace by DP's
[xonotic/netradiant.git] / 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