Rewrote class String to use an internal (stack based) storage for small strings, thus avoiding a couple ten thousand heap allocations

svn-id: r24043

2 files changed, 214 insertions, 127 deletions

diff --git a/common/str.cpp b/common/str.cpp
index d793c54cb8..20844894b8 100644
--- a/common/str.cpp
+++ b/common/str.cpp
@@ -44,89 +44,99 @@ static int computeCapacity(int len) {
 	return ((len + 32 - 1) & ~0x1F) - 1;
 }
 
-String::String(const char *str, int len, int capacity)
-: _str(0), _len(0), _refCount(0) {
-
-	if (str && *str && len != 0) {
-		if (len > 0)
-			_len = len;
-		else
-			_len = strlen(str);
-
-		_capacity = computeCapacity(_len);
-		if (_capacity < capacity)
-			_capacity = capacity;
-
-		_str = (char *)malloc(_capacity+1);
-		memcpy(_str, str, _len);
-		_str[_len] = 0;
-	} else {
-		_capacity = _len = 0;
-		_str = 0;
+String::String(const char *str, uint32 len)
+: _len(0), _str(_storage), _storage() {
+
+	if (str && *str) {
+		const uint32 tmp = strlen(str);
+		assert(len <= tmp);
+		if (len <= 0)
+			len = tmp;
+		_len = len;
+		
+		if (len >= _builtinCapacity) {
+			// Not enough internal storage, so allocate more
+			_extern._capacity = computeCapacity(len);
+			_extern._refCount = 0;
+			_str = (char *)malloc(_extern._capacity+1);
+			assert(_str != 0);
+		}
+		
+		// Copy the string into the storage area
+		memcpy(_str, str, len);
+		_str[len] = 0;
 	}
 }
 
 String::String(const String &str)
- : _str(str._str), _len(str._len), _refCount(0), _capacity(str._capacity) {
-
-	if (_str != 0) {
-		// If the string we are copying is non-empty, we increment its
-		// refcount.
+ : _len(str._len), _str(str.isStorageIntern() ? _storage : str._str) {
+	if (str.isStorageIntern()) {
+		// String in internal storage: just copy it
+		memcpy(_storage, str._storage, _builtinCapacity);
+	} else {
+		// String in external storage: use refcount mechanism
 		str.incRefCount();
-		_refCount = str._refCount;
+		_extern._refCount = str._extern._refCount;
+		_extern._capacity = str._extern._capacity;
 	}
+	assert(_str != 0);
 }
-
+	
 String::~String() {
-	decRefCount();
+	decRefCount(_extern._refCount);
 }
 
 void String::incRefCount() const {
-	if (_refCount == 0) {
-		_refCount = new int(2);
+	assert(!isStorageIntern());
+	if (_extern._refCount == 0) {
+		_extern._refCount = new int(2);
 	} else {
-		++(*_refCount);
+		++(*_extern._refCount);
 	}
 }
 
-void String::decRefCount() {
-	if (_refCount) {
-		--(*_refCount);
+void String::decRefCount(int *oldRefCount) {
+	if (isStorageIntern())
+		return;
+
+	if (oldRefCount) {
+		--(*oldRefCount);
 	}
-	if (!_refCount || *_refCount <= 0) {
-		delete _refCount;
-		_refCount = 0;
+	if (!oldRefCount || *oldRefCount <= 0) {
+		// The ref count reached zero, so we free the string storage
+		// and the ref count storage.
+		delete oldRefCount;
 		free(_str);
-		_str = 0;
+
+		// Even though _str points to a freed memory block now,
+		// we do not change its value, because any code that calls
+		// decRefCount will have to do this afterwards anyway.
 	}
 }
 
 String& String::operator  =(const char *str) {
-	int len = strlen(str);
-	if (len > 0) {
-		ensureCapacity(len, false);
-
-		_len = len;
-		memcpy(_str, str, _len + 1);
-	} else if (_len > 0) {
-		decRefCount();
-
-		_refCount = 0;
-		_capacity = 0;
-		_len = 0;
-		_str = 0;
-	}
+	uint32 len = strlen(str);
+	ensureCapacity(len, false);
+	_len = len;
+	memcpy(_str, str, len + 1);
 	return *this;
 }
 
 String &String::operator  =(const String &str) {
-	str.incRefCount();
-	decRefCount();
-
-	_refCount = str._refCount;
-	_capacity = str._capacity;
-	_len = str._len;
-	_str = str._str;
+	if (str.isStorageIntern()) {
+		decRefCount(_extern._refCount);
+		_len = str._len;
+		_str = _storage;
+		memcpy(_str, str._str, _len + 1);
+	} else {
+		str.incRefCount();
+		decRefCount(_extern._refCount);
+	
+		_extern._refCount = str._extern._refCount;
+		_extern._capacity = str._extern._capacity;
+		_len = str._len;
+		_str = str._str;
+	}
 
 	return *this;
 }
@@ -161,7 +171,7 @@ String &String::operator +=(const String &str) {
 	return *this;
 }
 
-String &String::operator += (char c) {
+String &String::operator +=(char c) {
 	ensureCapacity(_len + 1, true);
 
 	_str[_len++] = c;
@@ -186,7 +196,7 @@ bool String::hasPrefix(const char *x) const {
 bool String::hasSuffix(const char *x) const {
 	assert(x != 0);
 	// Compare x with the end of _str.
-	const int x_len = strlen(x);
+	const uint32 x_len = strlen(x);
 	if (x_len > _len)
 		return false;
 	const char *y = c_str() + _len - x_len;
@@ -200,88 +210,113 @@ bool String::hasSuffix(const char *x) const {
 }
 
 void String::deleteLastChar() {
-	if (_len > 0) {
-		ensureCapacity(_len - 1, true);
-		_str[--_len] = 0;
-	}
+	deleteChar(_len - 1);
 }
 
-void String::deleteChar(int p) {
-	if (p >= 0 && p < _len) {
-		ensureCapacity(_len - 1, true);
-		while (p++ < _len)
-			_str[p-1] = _str[p];
-		_len--;
-	}
+void String::deleteChar(uint32 p) {
+	assert(p < _len);
+
+	// Call ensureCapacity to make sure we actually *own* the storage
+	// to which _str points to -- we wouldn't want to modify a storage
+	// which other string objects are sharing, after all.
+	ensureCapacity(_len - 1, true);
+	while (p++ < _len)
+		_str[p-1] = _str[p];
+	_len--;
 }
 
 void String::clear() {
-	if (_capacity) {
-		decRefCount();
+	decRefCount(_extern._refCount);
 
-		_refCount = 0;
-		_capacity = 0;
-		_len = 0;
-		_str = 0;
-	}
+	_len = 0;
+	_str = _storage;
+	_storage[0] = 0;
 }
 
-void String::insertChar(char c, int p) {
-	// FIXME: This should be an 'assert', not an 'if' !
-	if (p >= 0 && p <= _len) {
-		ensureCapacity(_len + 1, true);
-		_len++;
-		for (int i = _len; i > p; i--) {
-			_str[i] = _str[i-1];
-		}
-		_str[p] = c;
-	}
+void String::insertChar(char c, uint32 p) {
+	assert(p <= _len);
+
+	ensureCapacity(_len + 1, true);
+	_len++;
+	for (uint32 i = _len; i > p; --i)
+		_str[i] = _str[i-1];
+	_str[p] = c;
 }
 
 void String::toLowercase() {
-	if (_str == 0 || _len == 0)
-		return;
-
 	ensureCapacity(_len, true);
-	for (int i = 0; i < _len; ++i)
+	for (uint32 i = 0; i < _len; ++i)
 		_str[i] = tolower(_str[i]);
 }
 
 void String::toUppercase() {
-	if (_str == 0 || _len == 0)
-		return;
-
 	ensureCapacity(_len, true);
-	for (int i = 0; i < _len; ++i)
+	for (uint32 i = 0; i < _len; ++i)
 		_str[i] = toupper(_str[i]);
 }
 
-void String::ensureCapacity(int new_len, bool keep_old) {
-	// If there is not enough space, or if we are not the only owner
-	// of the current data, then we have to reallocate it.
-	if (new_len <= _capacity && (_refCount == 0 || *_refCount == 1))
+/**
+ * Ensure that enough storage is available to store at least new_len
+ * characters plus a null byte. In addition, if we currently share
+ * the storage with another string, unshare it, so that we can safely
+ * write to the storage.
+ */
+void String::ensureCapacity(uint32 new_len, bool keep_old) {
+	bool isShared;
+	uint32 curCapacity, newCapacity;
+	char *newStorage;
+	int *oldRefCount = _extern._refCount;
+	
+	if (isStorageIntern()) {
+		isShared = false;
+		curCapacity = _builtinCapacity - 1;
+	} else {
+		isShared = (oldRefCount && *oldRefCount > 1);
+		curCapacity = _extern._capacity;
+	}
+	
+	// Special case: If there is enough space, and we do not share
+	// the storage, then there is nothing to do.
+	if (!isShared && new_len <= curCapacity)
 		return;
 
-	int newCapacity = computeCapacity(new_len);
+	if (isShared && new_len <= _builtinCapacity - 1) {
+		// We share the storage, but there is enough internal storage: Use that.
+		newStorage = _storage;
+		newCapacity = _builtinCapacity - 1;
+	} else {
+		// We need to allocate storage on the heap!
 
-	// FIXME: We never shrink the capacity here. Is that really a good idea?
-	if (newCapacity < _capacity)
-		newCapacity = _capacity;
+		// Compute a suitable new capacity limit
+		newCapacity = computeCapacity(new_len);
 
-	char *newStr = (char *)malloc(newCapacity+1);
+		// Allocate new storage
+		newStorage = (char *)malloc(newCapacity+1);
+		assert(newStorage);
+	}
 
-	if (keep_old && _str) {
-		memcpy(newStr, _str, _len + 1);
+	// Copy old data if needed, elsewise reset the new storage.
+	if (keep_old) {
+		assert(_len <= newCapacity);
+		memcpy(newStorage, _str, _len + 1);
 	} else {
 		_len = 0;
-		newStr[0] = 0;
+		newStorage[0] = 0;
 	}
 
-	decRefCount();
+	// Release hold on the old storage ...
+	decRefCount(oldRefCount);
 
-	_refCount = 0;
-	_capacity = newCapacity;
-	_str = newStr;
+	// ... in favor of the new storage
+	_str = newStorage;
+
+	if (!isStorageIntern()) {
+		// Set the ref count & capacity if we use an external storage.
+		// It is important to do this *after* copying any old content,
+		// else we would override data that has not yet been copied!
+		_extern._refCount = 0;
+		_extern._capacity = newCapacity;
+	}
 }
 
 uint String::hash() const {
diff --git a/common/str.h b/common/str.h
index 5110fdf6d6..3a57be0ce4 100644
--- a/common/str.h
+++ b/common/str.h
@@ -30,13 +30,65 @@
 
 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.
+ */
 class String {
 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;
+
+	/**
+	 * 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 		_len;
+	
+	/**
+	 * Pointer to the actual string storage. Either points to _storage,
+	 * or to a block allocated on the heap via malloc.
+	 */
 	char		*_str;
-	int 		_len;
-	mutable int *_refCount;
-	int 		_capacity;
-
+	
+	
+	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:
 #if !(defined(PALMOS_ARM) || defined(PALMOS_DEBUG) || defined(__GP32__))
 	static const String emptyString;
@@ -44,8 +96,8 @@ public:
 	static const char *emptyString;
 #endif
 
-	String() : _str(0), _len(0), _refCount(0), _capacity(0) {}
-	String(const char *str, int len = -1, int capacity = 16);
+	String() : _len(0), _str(_storage), _storage() {}
+	String(const char *str, uint32 len = 0);
 	String(const String &str);
 	virtual ~String();
 
@@ -81,26 +133,26 @@ public:
 	bool hasSuffix(const char *x) const;
 	bool hasPrefix(const char *x) const;
 
-	const char *c_str() const		{ return _str ? _str : ""; }
-	uint size() const				{ return _len; }
+	inline const char *c_str() const		{ return _str; }
+	inline uint size() const				{ return _len; }
 
-	bool empty() const	{ return (_len == 0); }
+	inline bool empty() const	{ return (_len == 0); }
 	char lastChar() const	{ return (_len > 0) ? _str[_len-1] : 0; }
 
 	char operator [](int idx) const {
-		assert(_str && idx >= 0 && idx < _len);
+		assert(_str && idx >= 0 && idx < (int)_len);
 		return _str[idx];
 	}
 
 	char &operator [](int idx) {
-		assert(_str && idx >= 0 && idx < _len);
+		assert(_str && idx >= 0 && idx < (int)_len);
 		return _str[idx];
 	}
 
 	void deleteLastChar();
-	void deleteChar(int p);
+	void deleteChar(uint32 p);
 	void clear();
-	void insertChar(char c, int p);
+	void insertChar(char c, uint32 p);
 
 	void toLowercase();
 	void toUppercase();
@@ -128,9 +180,9 @@ public:
 	}
 
 protected:
-	void ensureCapacity(int new_len, bool keep_old);
+	void ensureCapacity(uint32 new_len, bool keep_old);
 	void incRefCount() const;
-	void decRefCount();
+	void decRefCount(int *oldRefCount);
 };
 
 // Append two strings to form a new (temp) string