aboutsummaryrefslogtreecommitdiff
path: root/common/str.h
blob: d55ba072a9f18c24036d7c10796abb433fda2951 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
/* ScummVM - Graphic Adventure Engine
 *
 * ScummVM is the legal property of its developers, whose names
 * are too numerous to list here. Please refer to the COPYRIGHT
 * file distributed with this source distribution.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 */

#ifndef COMMON_STRING_H
#define COMMON_STRING_H

#include "common/scummsys.h"

#include <stdarg.h>

namespace Common {

/**
 * Simple string class for ScummVM. Provides automatic storage managment,
 * and overloads several operators in a 'natural' fashion, mimicking
 * the std::string class. Even provides simple iterators.
 *
 * This class tries to avoid allocating lots of small blocks on the heap,
 * since that is inefficient on several platforms supported by ScummVM.
 * Instead, small strings are stored 'inside' the string object (i.e. on
 * the stack, for stack allocated objects), and only for strings exceeding
 * a certain length do we allocate a buffer on the heap.
 *
 * The presence of \0 characters in the string will cause undefined
 * behavior in some operations.
 */
class String {
public:
	static const uint32 npos = 0xFFFFFFFF;

	typedef char          value_type;
	/**
	 * Unsigned version of the underlying type. This can be used to cast
	 * individual string characters to bigger integer types without sign
	 * extension happening.
	 */
	typedef unsigned char unsigned_type;
	typedef char *        iterator;
	typedef const char *  const_iterator;

protected:
	/**
	 * The size of the internal storage. Increasing this means less heap
	 * allocations are needed, at the cost of more stack memory usage,
	 * and of course lots of wasted memory. Empirically, 90% or more of
	 * all String instances are less than 32 chars long. If a platform
	 * is very short on stack space, it would be possible to lower this.
	 * A value of 24 still seems acceptable, though considerably worse,
	 * while 16 seems to be the lowest you want to go... Anything lower
	 * than 8 makes no sense, since that's the size of member _extern
	 * (on 32 bit machines; 12 bytes on systems with 64bit pointers).
	 */
	static const uint32 _builtinCapacity = 32 - sizeof(uint32) - sizeof(char *);

	/**
	 * Length of the string. Stored to avoid having to call strlen
	 * a lot. Yes, we limit ourselves to strings shorter than 4GB --
	 * on purpose :-).
	 */
	uint32 _size;

	/**
	 * Pointer to the actual string storage. Either points to _storage,
	 * or to a block allocated on the heap via malloc.
	 */
	char  *_str;


	union {
		/**
		 * Internal string storage.
		 */
		char _storage[_builtinCapacity];
		/**
		 * External string storage data -- the refcounter, and the
		 * capacity of the string _str points to.
		 */
		struct {
			mutable int *_refCount;
			uint32       _capacity;
		} _extern;
	};

	inline bool isStorageIntern() const {
		return _str == _storage;
	}

public:
	/** Construct a new empty string. */
	String() : _size(0), _str(_storage) { _storage[0] = 0; }

	/** Construct a new string from the given NULL-terminated C string. */
	String(const char *str);

	/** Construct a new string containing exactly len characters read from address str. */
	String(const char *str, uint32 len);

	/** Construct a new string containing the characters between beginP (including) and endP (excluding). */
	String(const char *beginP, const char *endP);

	/** Construct a copy of the given string. */
	String(const String &str);

	/** Construct a string consisting of the given character. */
	explicit String(char c);

	~String();

	String &operator=(const char *str);
	String &operator=(const String &str);
	String &operator=(char c);
	String &operator+=(const char *str);
	String &operator+=(const String &str);
	String &operator+=(char c);

	bool operator==(const String &x) const;
	bool operator==(const char *x) const;
	bool operator!=(const String &x) const;
	bool operator!=(const char *x) const;

	bool operator<(const String &x) const;
	bool operator<=(const String &x) const;
	bool operator>(const String &x) const;
	bool operator>=(const String &x) const;

	bool equals(const String &x) const;
	bool equalsIgnoreCase(const String &x) const;
	int compareTo(const String &x) const;           // strcmp clone
	int compareToIgnoreCase(const String &x) const; // stricmp clone

	bool equals(const char *x) const;
	bool equalsIgnoreCase(const char *x) const;
	int compareTo(const char *x) const;             // strcmp clone
	int compareToIgnoreCase(const char *x) const;   // stricmp clone

	bool hasSuffix(const String &x) const;
	bool hasSuffix(const char *x) const;

	bool hasPrefix(const String &x) const;
	bool hasPrefix(const char *x) const;

	bool contains(const String &x) const;
	bool contains(const char *x) const;
	bool contains(char x) const;

	/** Return uint64 corrensponding to String's contents. */
	uint64 asUint64() const;

	/**
	 * Simple DOS-style pattern matching function (understands * and ? like used in DOS).
	 * Taken from exult/files/listfiles.cc
	 *
	 * Token meaning:
	 *      "*": any character, any amount of times.
	 *      "?": any character, only once.
	 *      "#": any decimal digit, only once.
	 *
	 * Example strings/patterns:
	 *      String: monkey.s01   Pattern: monkey.s??    => true
	 *      String: monkey.s101  Pattern: monkey.s??    => false
	 *      String: monkey.s99   Pattern: monkey.s?1    => false
	 *      String: monkey.s101  Pattern: monkey.s*     => true
	 *      String: monkey.s99   Pattern: monkey.s*1    => false
	 *      String: monkey.s01   Pattern: monkey.s##    => true
	 *      String: monkey.s01   Pattern: monkey.###    => false
	 *
	 * @param pat Glob pattern.
	 * @param ignoreCase Whether to ignore the case when doing pattern match
	 * @param pathMode Whether to use path mode, i.e., whether slashes must be matched explicitly.
	 *
	 * @return true if str matches the pattern, false otherwise.
	 */
	bool matchString(const char *pat, bool ignoreCase = false, bool pathMode = false) const;
	bool matchString(const String &pat, bool ignoreCase = false, bool pathMode = false) const;


	inline const char *c_str() const { return _str; }
	inline uint size() const         { return _size; }

	inline bool empty() const { return (_size == 0); }
	char firstChar() const    { return (_size > 0) ? _str[0] : 0; }
	char lastChar() const     { return (_size > 0) ? _str[_size - 1] : 0; }

	char operator[](int idx) const {
		assert(_str && idx >= 0 && idx < (int)_size);
		return _str[idx];
	}

	/** Remove the last character from the string. */
	void deleteLastChar();

	/** Remove the character at position p from the string. */
	void deleteChar(uint32 p);

	/** Remove all characters from position p to the p + len. If len = String::npos, removes all characters to the end */
	void erase(uint32 p, uint32 len = npos);

	/** Set character c at position p, replacing the previous character there. */
	void setChar(char c, uint32 p);

	/** Insert character c before position p. */
	void insertChar(char c, uint32 p);

	/** Clears the string, making it empty. */
	void clear();

	/** Convert all characters in the string to lowercase. */
	void toLowercase();

	/** Convert all characters in the string to uppercase. */
	void toUppercase();

	/**
	 * Removes trailing and leading whitespaces. Uses isspace() to decide
	 * what is whitespace and what not.
	 */
	void trim();

	uint hash() const;

	/**@{
	 * Functions to replace some amount of chars with chars from some other string.
	 *
	 * @note The implementation follows that of the STL's std::string:
	 *       http://www.cplusplus.com/reference/string/string/replace/
	 *
	 * @param pos Starting position for the replace in the original string.
	 * @param count Number of chars to replace from the original string.
	 * @param str Source of the new chars.
	 * @param posOri Same as pos
	 * @param countOri Same as count
	 * @param posDest Initial position to read str from.
	 * @param countDest Number of chars to read from str. npos by default.
	 */
	// Replace 'count' bytes, starting from 'pos' with str.
	void replace(uint32 pos, uint32 count, const String &str);
	// The same as above, but accepts a C-like array of characters.
	void replace(uint32 pos, uint32 count, const char *str);
	// Replace the characters in [begin, end) with str._str.
	void replace(iterator begin, iterator end, const String &str);
	// Replace the characters in [begin, end) with str.
	void replace(iterator begin, iterator end, const char *str);
	// Replace _str[posOri, posOri + countOri) with
	// str._str[posDest, posDest + countDest)
	void replace(uint32 posOri, uint32 countOri, const String &str,
					uint32 posDest, uint32 countDest);
	// Replace _str[posOri, posOri + countOri) with
	// str[posDest, posDest + countDest)
	void replace(uint32 posOri, uint32 countOri, const char *str,
					uint32 posDest, uint32 countDest);
	/**@}*/

	/**
	 * Print formatted data into a String object. Similar to sprintf,
	 * except that it stores the result in (variably sized) String
	 * instead of a fixed size buffer.
	 */
	static String format(const char *fmt, ...) GCC_PRINTF(1,2);

	/**
	 * Print formatted data into a String object. Similar to vsprintf,
	 * except that it stores the result in (variably sized) String
	 * instead of a fixed size buffer.
	 */
	static String vformat(const char *fmt, va_list args);

public:

	iterator begin() {
		// Since the user could potentially
		// change the string via the returned
		// iterator we have to assure we are
		// pointing to a unique storage.
		makeUnique();

		return _str;
	}

	iterator end() {
		return begin() + size();
	}

	const_iterator begin() const {
		return _str;
	}

	const_iterator end() const {
		return begin() + size();
	}

protected:
	void makeUnique();
	void ensureCapacity(uint32 new_size, bool keep_old);
	void incRefCount() const;
	void decRefCount(int *oldRefCount);
	void initWithCStr(const char *str, uint32 len);
};

// Append two strings to form a new (temp) string
String operator+(const String &x, const String &y);

String operator+(const char *x, const String &y);
String operator+(const String &x, const char *y);

String operator+(const String &x, char y);
String operator+(char x, const String &y);

// Some useful additional comparison operators for Strings
bool operator==(const char *x, const String &y);
bool operator!=(const char *x, const String &y);

// Utility functions to remove leading and trailing whitespaces
extern char *ltrim(char *t);
extern char *rtrim(char *t);
extern char *trim(char *t);


/**
 * Returns the last component of a given path.
 *
 * Examples:
 *          /foo/bar.txt    would return 'bar.txt'
 *          /foo/bar/       would return 'bar'
 *          /foo/./bar//    would return 'bar'
 *
 * @param path the path of which we want to know the last component
 * @param sep character used to separate path components
 * @return The last component of the path.
 */
String lastPathComponent(const String &path, const char sep);

/**
 * Normalize a given path to a canonical form. In particular:
 * - trailing separators are removed:  /foo/bar/ -> /foo/bar
 * - double separators (= empty components) are removed:   /foo//bar -> /foo/bar
 * - dot components are removed:  /foo/./bar -> /foo/bar
 *
 * @todo remove double dot components:  /foo/baz/../bar -> /foo/bar
 *
 * @param path  the path to normalize
 * @param sep   the separator token (usually '/' on Unix-style systems, or '\\' on Windows based stuff)
 * @return      the normalized path
 */
String normalizePath(const String &path, const char sep);


/**
 * Simple DOS-style pattern matching function (understands * and ? like used in DOS).
 * Taken from exult/files/listfiles.cc
 *
 * Token meaning:
 *      "*": any character, any amount of times.
 *      "?": any character, only once.
 *      "#": any decimal digit, only once.
 *
 * Example strings/patterns:
 *      String: monkey.s01   Pattern: monkey.s??    => true
 *      String: monkey.s101  Pattern: monkey.s??    => false
 *      String: monkey.s99   Pattern: monkey.s?1    => false
 *      String: monkey.s101  Pattern: monkey.s*     => true
 *      String: monkey.s99   Pattern: monkey.s*1    => false
 *      String: monkey.s01   Pattern: monkey.s##    => true
 *      String: monkey.s01   Pattern: monkey.###    => false
 *
 * @param str Text to be matched against the given pattern.
 * @param pat Glob pattern.
 * @param ignoreCase Whether to ignore the case when doing pattern match
 * @param pathMode Whether to use path mode, i.e., whether slashes must be matched explicitly.
 *
 * @return true if str matches the pattern, false otherwise.
 */
bool matchString(const char *str, const char *pat, bool ignoreCase = false, bool pathMode = false);

/**
 * Function which replaces substring with the other. It happens in place.
 * If there is no substring found, original string is not changed.
 *
 * @param source String to search and replace substring in.
 * @param what Substring to replace.
 * @param with String to replace with.
 */
void replace(Common::String &source, const Common::String &what, const Common::String &with);

/**
 * Take a 32 bit value and turn it into a four character string, where each of
 * the four bytes is turned into one character. Most significant byte is printed
 * first.
 */
String tag2string(uint32 tag);

/**
 * Copy up to size - 1 characters from src to dst and also zero terminate the
 * result. Note that src must be a zero terminated string.
 *
 * In case size is zero this function just returns the length of the source
 * string.
 *
 * @note This is modeled after OpenBSD's strlcpy. See the manpage here:
 *       http://www.openbsd.org/cgi-bin/man.cgi?query=strlcpy
 *
 * @param dst The destination buffer.
 * @param src The source string.
 * @param size The size of the destination buffer.
 * @return The length of the (non-truncated) result, i.e. strlen(src).
 */
size_t strlcpy(char *dst, const char *src, size_t size);

/**
 * Append the string src to the string dst. Note that both src and dst must be
 * zero terminated. The result will be zero terminated. At most
 * "size - strlen(dst) - 1" bytes will be appended.
 *
 * In case the dst string does not contain a zero within the first "size" bytes
 * the dst string will not be changed and size + strlen(src) is returned.
 *
 * @note This is modeled after OpenBSD's strlcat. See the manpage here:
 *       http://www.openbsd.org/cgi-bin/man.cgi?query=strlcat
 *
 * @param dst The string the source string should be appended to.
 * @param src The source string.
 * @param size The (total) size of the destination buffer.
 * @return The length of the (non-truncated) result. That is
 *         strlen(dst) + strlen(src). In case strlen(dst) > size
 *         size + strlen(src) is returned.
 */
size_t strlcat(char *dst, const char *src, size_t size);

/**
 * Convenience wrapper for tag2string which "returns" a C string.
 * Note: It is *NOT* safe to do anything with the return value other than directly
 * copying or printing it.
 */
#define tag2str(x)	Common::tag2string(x).c_str()


} // End of namespace Common

extern int scumm_stricmp(const char *s1, const char *s2);
extern int scumm_strnicmp(const char *s1, const char *s2, uint n);

#endif