1 /**************************************************************************
3 * Copyright 2013-2014 RAD Game Tools and Valve Software
4 * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 **************************************************************************/
27 // File: vogl_dynamic_string.h
29 // Dynamic string class with the small string optimization.
31 // Important note: For historical reasons the comparisons operators in this class are
32 // case insensitive (using locale independent helper functions) by default, mostly because
33 // the last X engines I've worked on used this default and I got used to it. Its the day after
34 // and now I'm kinda regretting this idea, but there's too much code that depends on this behavior.
35 // If you need to do case sensitive comparisons: either call compare(other, false), or dynamic_string_less_than_case_insensitive.
38 #include "vogl_core.h"
40 #ifdef VOGL_BUILD_DEBUG
41 #ifndef VOGL_SLOW_STRING_LEN_CHECKS
42 #define VOGL_SLOW_STRING_LEN_CHECKS 1
51 typedef vogl::vector<dynamic_string> dynamic_string_array;
53 // These limits are in place so plain signed int's can be safely used as offsets into the buffer (use something else if you need strings this big).
56 cMaxDynamicStringBufSize = 0x7FFFFFFFU,
57 cMaxDynamicStringLen = cMaxDynamicStringBufSize - 1
63 inline dynamic_string()
65 set_to_empty_small_string();
67 dynamic_string(eVarArg dummy, const char *p, ...) VOGL_ATTRIBUTE_PRINTF(3, 4);
68 dynamic_string(const char *p);
69 dynamic_string(const char *p, uint len);
70 dynamic_string(const dynamic_string &other);
72 inline ~dynamic_string()
75 vogl_delete_array(m_dyn.m_pStr);
78 // Truncates the string to 0 chars and frees the buffer.
82 void reserve(uint new_capacity);
84 // Truncates the string to 0 chars, but does not free the buffer.
87 // Returns the string buffer to the caller and clears the string.
88 // The caller takes ownership of the returned buffer, free it using vogl_delete_array(pStr);
89 inline const char *assume_ownership()
92 const char *p = m_dyn.m_pStr;
93 set_to_empty_small_string();
97 inline uint get_len() const
101 inline uint size() const
105 inline bool is_empty() const
109 inline bool has_content() const
114 // Returns a pointer to the zero terminated C-style string (which may be a zero terminated empty string) - never NULL.
115 inline const char *get_ptr() const
117 return get_ptr_priv();
119 inline const char *c_str() const
121 return get_ptr_priv();
124 // Returns a pointer to the zero terminated C-style string (which may be a zero terminated empty string) - never NULL.
125 // Do not change the length of the string via this pointer! This method is intended for faster deserialization.
126 inline char *get_ptr_raw()
128 return get_ptr_priv();
131 // Returns a duplicate of the string.
132 dynamic_string get_clone() const
134 return dynamic_string(*this);
137 inline char front() const
139 return m_len ? get_ptr_priv()[0] : '\0';
141 inline char back() const
143 return m_len ? get_ptr_priv()[m_len - 1] : '\0';
146 inline char operator[](uint i) const
148 VOGL_ASSERT(i <= m_len);
152 // Index string, beginning from back, 0 = last character, 1 = next to last char, etc.
153 inline char get_char_at_end(uint i) const
155 VOGL_ASSERT(i <= m_len);
156 return (i < m_len) ? get_ptr()[m_len - 1U - i] : '\0';
159 inline string_hash get_hash() const
161 return string_hash(get_ptr(), m_len);
164 // IMPORTANT: These comparison methods are all CASE INSENSITIVE by default!
165 // Yes this seems maybe sorta nutty to me now, but in the past I've worked on a bunch of projects where this was the default and it was rarely a problem.
166 int compare(const char *p, bool case_sensitive = false) const;
167 int compare(const dynamic_string &rhs, bool case_sensitive = false) const;
169 // length of string is the first key, then followed by a lex compare using compare() if lengths are equal
170 int compare_using_length(const char *p, bool case_sensitive = false) const;
171 int compare_using_length(const dynamic_string &rhs, bool case_sensitive = false) const;
173 // IMPORTANT: These comparison methods are all CASE INSENSITIVE by default!
174 inline bool operator==(const dynamic_string &rhs) const
176 return compare(rhs) == 0;
178 inline bool operator==(const char *p) const
180 return compare(p) == 0;
183 inline bool operator!=(const dynamic_string &rhs) const
185 return compare(rhs) != 0;
187 inline bool operator!=(const char *p) const
189 return compare(p) != 0;
192 inline bool operator<(const dynamic_string &rhs) const
194 return compare(rhs) < 0;
196 inline bool operator<(const char *p) const
198 return compare(p) < 0;
201 inline bool operator>(const dynamic_string &rhs) const
203 return compare(rhs) > 0;
205 inline bool operator>(const char *p) const
207 return compare(p) > 0;
210 inline bool operator<=(const dynamic_string &rhs) const
212 return compare(rhs) <= 0;
214 inline bool operator<=(const char *p) const
216 return compare(p) <= 0;
219 inline bool operator>=(const dynamic_string &rhs) const
221 return compare(rhs) >= 0;
223 inline bool operator>=(const char *p) const
225 return compare(p) >= 0;
228 friend inline bool operator==(const char *p, const dynamic_string &rhs)
230 return rhs.compare(p) == 0;
233 dynamic_string &set(const char *p, uint max_len = UINT_MAX);
234 dynamic_string &set(const dynamic_string &other, uint max_len = UINT_MAX);
236 bool set_len(uint new_len, char fill_char = ' ');
238 // Set from a NON-zero terminated buffer (i.e. pBuf cannot contain any 0's, buf_len_in_chars is the size of the string).
239 dynamic_string &set_from_buf(const void *pBuf, uint buf_len_in_chars);
241 dynamic_string &operator=(const dynamic_string &rhs)
245 dynamic_string &operator=(const char *p)
250 dynamic_string &set_char(uint index, char c);
251 dynamic_string &append_char(char c);
252 dynamic_string &append_char(int c)
254 VOGL_ASSERT((c > 0) && (c <= 255));
255 return append_char(static_cast<char>(c));
257 dynamic_string &truncate(uint new_len);
258 dynamic_string &shorten(uint chars_to_remove);
259 dynamic_string &tolower();
260 dynamic_string &toupper();
262 dynamic_string &append(const char *p);
263 dynamic_string &append(const char *p, uint len);
264 dynamic_string &append(const dynamic_string &other);
265 dynamic_string &operator+=(const char *p)
269 dynamic_string &operator+=(const dynamic_string &other)
271 return append(other);
274 friend dynamic_string operator+(const char *p, const dynamic_string &a);
275 friend dynamic_string operator+(const dynamic_string &a, const char *p);
276 friend dynamic_string operator+(const dynamic_string &a, const dynamic_string &b);
278 dynamic_string &format_args(const char *p, va_list args);
279 dynamic_string &format(const char *p, ...) VOGL_ATTRIBUTE_PRINTF(2, 3);
280 dynamic_string &format_append(const char *p, ...) VOGL_ATTRIBUTE_PRINTF(2, 3);
282 // Note many of these ops are IN-PLACE string operations to avoid constructing new dynamic_string objects.
283 // Yes this is awkward, one way to work around this is to close the string like this (which introduces a clone and then does the op in-place):
284 // result = str.get_clone().left(x);
285 dynamic_string &crop(uint start, uint len);
286 dynamic_string &remove(uint start, uint len);
288 // trims string to [start, end), i.e. up to but not including end
289 dynamic_string &substring(uint start, uint end);
291 dynamic_string &left(uint len);
292 dynamic_string &mid(uint start, uint len);
293 dynamic_string &right(uint start);
294 dynamic_string &tail(uint num);
296 dynamic_string &replace(const char *pFind, const char *pReplacement, bool case_sensitive = true, uint *pNum_found = NULL, uint max_replacements = UINT_MAX);
298 dynamic_string &unquote();
300 uint count_char(char c) const;
302 int find_left(const char *p, bool case_sensitive = false, uint start_ofs = 0) const;
303 int find_left(char c, int start_ofs = 0) const;
305 int find_right(char c) const;
306 int find_right(char c, uint start_ofs) const;
307 int find_right(const char *p, bool case_sensitive = false) const;
309 bool contains(const char *p, bool case_sensitive = false) const;
310 bool contains(char c) const;
312 bool begins_with(const char *p, bool case_sensitive = false) const;
313 bool ends_with(const char *p, bool case_sensitive = false) const;
315 dynamic_string &trim();
316 dynamic_string &trim_end();
317 dynamic_string &trim_crlf();
319 dynamic_string &remap(int from_char, int to_char);
321 void swap(dynamic_string &other);
323 void tokenize(const char *pDelims, dynamic_string_array &tokens, bool trim = false) const;
325 uint get_serialize_size() const
327 return sizeof(uint32) + m_len;
330 // Returns -1 on failure, or the number of bytes written.
331 int serialize(void *pBuf, uint buf_size, bool little_endian) const;
333 // Returns -1 on failure, or the number of bytes read.
334 int deserialize(const void *pBuf, uint buf_size, bool little_endian);
336 void translate_lf_to_crlf();
338 static inline char *create_raw_buffer(uint &buf_size_in_chars);
339 static inline void free_raw_buffer(char *p)
341 vogl_delete_array(p);
344 // Buf size must be a power of 2, or cUINT32_MAX. TODO: Relax this BS.
345 dynamic_string &set_from_raw_buf_and_assume_ownership(char *pBuf, uint buf_size_in_bytes, uint len_in_chars);
347 bool validate() const;
349 // Forces the string to use a dynamically allocated buffer (the buffer is not optimized for enlarging).
350 void ensure_dynamic();
352 // True if the string is dynamic, false if it's static/small
353 inline bool is_dynamic() const
355 return (m_small.m_flag & 1) == 0;
358 // True if the string is inside of the object, false if it's dynamic.
359 inline bool is_small_string() const
361 return !is_dynamic();
367 cSmallStringExtraBufSize = 4,
368 cSmallStringBufSize = ((sizeof(char *) - 1) + sizeof(uint32)) + cSmallStringExtraBufSize,
369 cSmallStringMaxLen = cSmallStringBufSize - 1,
372 // TODO: Store m_len at the end of the struct, and use 1 byte to hold X-len. When the string is size X, the last byte will be zero, so we can use the entire struct to hold the string.
373 // Current string length in bytes.
374 // In this design, the string can be either static (small) or dynamic, independent of its size.
375 // I could gate whether or not the string is dynamic pased purely off the length, but this would be more restrictive.
382 // m_pStr is always zero terminated, and never NULL. Obviously, don't access it directly, use get_ptr() or get_ptr_priv() instead.
385 // Current buffer size in bytes.
392 char m_buf[cSmallStringBufSize];
396 inline void check() const
398 VOGL_ASSERT(validate());
401 // expands buffer to at least new_buf_size bytes
402 bool expand_buf(uint new_buf_size, bool preserve_contents);
404 // ensures a buffer at least large enough to hold len chars + zero terminator
405 bool ensure_buf(uint len, bool preserve_contents = true);
407 inline uint get_buf_size() const
409 return is_dynamic() ? static_cast<uint>(m_dyn.m_buf_size) : static_cast<uint>(cSmallStringBufSize);
412 inline void set_small_string_flag()
417 inline void set_to_empty_small_string()
421 m_small.m_buf[0] = 0;
424 inline void set_dyn_string_ptr(char *p)
428 VOGL_ASSERT(is_dynamic());
431 // Returns ptr to string, never NULL
432 inline const char *get_ptr_priv() const
434 return is_dynamic() ? m_dyn.m_pStr : m_small.m_buf;
437 // Returns ptr to string, never NULL
438 inline char *get_ptr_priv()
440 return is_dynamic() ? m_dyn.m_pStr : m_small.m_buf;
443 inline bool ptr_refers_to_self(const char *p) const
445 const char *pStr = get_ptr_priv();
446 return (p >= pStr) && (p < (pStr + get_buf_size()));
450 extern dynamic_string g_empty_dynamic_string;
452 VOGL_DEFINE_BITWISE_MOVABLE(dynamic_string);
454 inline void swap(dynamic_string &a, dynamic_string &b)
459 inline char *dynamic_string::create_raw_buffer(uint &buf_size_in_chars)
461 buf_size_in_chars = static_cast<uint>(math::minimum<uint64_t>(cUINT32_MAX, math::next_pow2(static_cast<uint64_t>(buf_size_in_chars))));
462 return vogl_new_array(char, buf_size_in_chars);
465 inline int scan_dynamic_string_array_for_string(const dynamic_string_array &strings, const char *pStr, bool case_sensitive)
467 for (uint i = 0; i < strings.size(); i++)
468 if (!strings[i].compare(pStr, case_sensitive))
474 struct hasher<dynamic_string>
476 inline size_t operator()(const dynamic_string &key) const
478 return key.get_hash();
482 struct dynamic_string_less_than_case_insensitive
484 inline bool operator()(const dynamic_string &a, const dynamic_string &b) const
486 return a.compare(b, false) < 0;
490 struct dynamic_string_equal_to_case_insensitive
492 inline bool operator()(const dynamic_string &a, const dynamic_string &b) const
494 return a.compare(b, false) == 0;
498 struct dynamic_string_less_than_case_sensitive
500 inline bool operator()(const dynamic_string &a, const dynamic_string &b) const
502 return a.compare(b, true) < 0;
506 struct dynamic_string_equal_to_case_sensitive
508 inline bool operator()(const dynamic_string &a, const dynamic_string &b) const
510 return a.compare(b, true) == 0;
514 bool json_serialize(const dynamic_string &str, json_value &val);
515 bool json_deserialize(dynamic_string &str, const json_value &val);
517 bool dynamic_string_test();
524 inline void swap(vogl::dynamic_string &a, vogl::dynamic_string &b)