@@ -129,22 +129,29 @@
 	[self freeMemory: unicodeString];
 
 	[self freeMemory: s->cString];
 	s->cString = newCString;
 	s->cStringLength = newCStringLength;
+
+	/*
+	 * Even though cStringLength can change, length can not, therefore no
+	 * need to change it.
+	 */
 }
 
 - (void)setToCString: (const char*)newCString
 {
 	size_t newCStringLength = strlen(newCString);
+	size_t newLength;
 
 	if (newCStringLength >= 3 && !memcmp(newCString, "\xEF\xBB\xBF", 3)) {
 		newCString += 3;
 		newCStringLength -= 3;
 	}
 
-	switch (of_string_check_utf8(newCString, newCStringLength)) {
+	switch (of_string_check_utf8(newCString, newCStringLength,
+	    &newLength)) {
 	case 0:
 		s->isUTF8 = NO;
 		break;
 	case 1:
 		s->isUTF8 = YES;
@@ -154,24 +161,27 @@
 	}
 
 	[self freeMemory: s->cString];
 
 	s->cStringLength = newCStringLength;
+	s->length = newLength;
+
 	s->cString = [self allocMemoryWithSize: newCStringLength + 1];
 	memcpy(s->cString, newCString, newCStringLength + 1);
 }
 
 - (void)appendCString: (const char*)cString
 {
 	size_t cStringLength = strlen(cString);
+	size_t length;
 
 	if (cStringLength >= 3 && !memcmp(cString, "\xEF\xBB\xBF", 3)) {
 		cString += 3;
 		cStringLength -= 3;
 	}
 
-	switch (of_string_check_utf8(cString, cStringLength)) {
+	switch (of_string_check_utf8(cString, cStringLength, &length)) {
 	case 1:
 		s->isUTF8 = YES;
 		break;
 	case -1:
 		@throw [OFInvalidEncodingException newWithClass: isa];
@@ -178,22 +188,26 @@
 	}
 
 	s->cString = [self resizeMemory: s->cString
 				 toSize: s->cStringLength + cStringLength + 1];
 	memcpy(s->cString + s->cStringLength, cString, cStringLength + 1);
+
 	s->cStringLength += cStringLength;
+	s->length += length;
 }
 
 - (void)appendCString: (const char*)cString
 	   withLength: (size_t)cStringLength
 {
+	size_t length;
+
 	if (cStringLength >= 3 && !memcmp(cString, "\xEF\xBB\xBF", 3)) {
 		cString += 3;
 		cStringLength -= 3;
 	}
 
-	switch (of_string_check_utf8(cString, cStringLength)) {
+	switch (of_string_check_utf8(cString, cStringLength, &length)) {
 	case 1:
 		s->isUTF8 = YES;
 		break;
 	case -1:
 		@throw [OFInvalidEncodingException newWithClass: isa];
@@ -200,11 +214,14 @@
 	}
 
 	s->cString = [self resizeMemory: s->cString
 				 toSize: s->cStringLength + cStringLength + 1];
 	memcpy(s->cString + s->cStringLength, cString, cStringLength);
+
 	s->cStringLength += cStringLength;
+	s->length += length;
+
 	s->cString[s->cStringLength] = 0;
 }
 
 - (void)appendCString: (const char*)cString
 	 withEncoding: (of_string_encoding_t)encoding
@@ -221,39 +238,29 @@
 					 length: cStringLength]];
 		[pool release];
 	}
 }
 
-- (void)appendCStringWithoutUTF8Checking: (const char*)cString
+- (void)appendString: (OFString*)string
 {
 	size_t cStringLength;
 
-	cStringLength = strlen(cString);
-	s->cString = [self resizeMemory: s->cString
-				 toSize: s->cStringLength + cStringLength + 1];
-	memcpy(s->cString + s->cStringLength, cString, cStringLength + 1);
-	s->cStringLength += cStringLength;
-}
-
-- (void)appendCStringWithoutUTF8Checking: (const char*)cString
-				  length: (size_t)cStringLength
-{
-	s->cString = [self resizeMemory: s->cString
-				 toSize: s->cStringLength + cStringLength + 1];
-	memcpy(s->cString + s->cStringLength, cString, cStringLength);
-	s->cStringLength += cStringLength;
-	s->cString[s->cStringLength] = 0;
-}
-
-- (void)appendString: (OFString*)string
-{
 	if (string == nil)
 		@throw [OFInvalidArgumentException newWithClass: isa
 						       selector: _cmd];
 
-	[self appendCStringWithoutUTF8Checking: [string cString]
-					length: [string cStringLength]];
+	cStringLength = [string cStringLength];
+
+	s->cString = [self resizeMemory: s->cString
+				 toSize: s->cStringLength + cStringLength + 1];
+	memcpy(s->cString + s->cStringLength, string->s->cString,
+	    cStringLength);
+
+	s->cStringLength += cStringLength;
+	s->length += string->s->length;
+
+	s->cString[s->cStringLength] = 0;
 
 	if (string->s->isUTF8)
 		s->isUTF8 = YES;
 }
 
@@ -403,46 +410,50 @@
 - (void)insertString: (OFString*)string
 	     atIndex: (size_t)index
 {
 	size_t newCStringLength;
 
+	if (index > s->length)
+		@throw [OFOutOfRangeException newWithClass: isa];
+
 	if (s->isUTF8)
 		index = of_string_index_to_position(s->cString, index,
 		    s->cStringLength);
 
-	if (index > s->cStringLength)
-		@throw [OFOutOfRangeException newWithClass: isa];
-
 	newCStringLength = s->cStringLength + [string cStringLength];
 	s->cString = [self resizeMemory: s->cString
 				 toSize: newCStringLength + 1];
 
-	memmove(s->cString + index + [string cStringLength], s->cString + index,
-	    s->cStringLength - index);
-	memcpy(s->cString + index, [string cString], [string cStringLength]);
+	memmove(s->cString + index + string->s->cStringLength,
+	    s->cString + index, s->cStringLength - index);
+	memcpy(s->cString + index, string->s->cString,
+	    string->s->cStringLength);
 	s->cString[newCStringLength] = '\0';
 
 	s->cStringLength = newCStringLength;
+	s->length += string->s->length;
 }
 
 - (void)deleteCharactersFromIndex: (size_t)start
 			  toIndex: (size_t)end
 {
+	if (start > end)
+		@throw [OFInvalidArgumentException newWithClass: isa
+						       selector: _cmd];
+
+	if (end > s->length)
+		@throw [OFOutOfRangeException newWithClass: isa];
+
+	s->length -= end - start;
+
 	if (s->isUTF8) {
 		start = of_string_index_to_position(s->cString, start,
 		    s->cStringLength);
 		end = of_string_index_to_position(s->cString, end,
 		    s->cStringLength);
 	}
 
-	if (start > end)
-		@throw [OFInvalidArgumentException newWithClass: isa
-						       selector: _cmd];
-
-	if (end > s->cStringLength)
-		@throw [OFOutOfRangeException newWithClass: isa];
-
 	memmove(s->cString + start, s->cString + end, s->cStringLength - end);
 	s->cStringLength -= end - start;
 	s->cString[s->cStringLength] = 0;
 
 	@try {
@@ -462,38 +473,41 @@
 
 - (void)replaceCharactersFromIndex: (size_t)start
 			   toIndex: (size_t)end
 			withString: (OFString*)replacement
 {
-	size_t newCStringLength;
+	size_t newCStringLength, newLength;
+
+	if (start > end)
+		@throw [OFInvalidArgumentException newWithClass: isa
+						       selector: _cmd];
+
+	if (end > s->length)
+		@throw [OFOutOfRangeException newWithClass: isa];
+
+	newLength = s->length - (end - start) + [replacement length];
 
 	if (s->isUTF8) {
 		start = of_string_index_to_position(s->cString, start,
 		    s->cStringLength);
 		end = of_string_index_to_position(s->cString, end,
 		    s->cStringLength);
 	}
 
-	if (start > end)
-		@throw [OFInvalidArgumentException newWithClass: isa
-						       selector: _cmd];
-
-	if (end > s->cStringLength)
-		@throw [OFOutOfRangeException newWithClass: isa];
-
 	newCStringLength = s->cStringLength - (end - start) +
-	    [replacement cStringLength];
+	    replacement->s->cStringLength;
 	s->cString = [self resizeMemory: s->cString
 				 toSize: newCStringLength + 1];
 
 	memmove(s->cString + end, s->cString + start +
-	    [replacement cStringLength], s->cStringLength - end);
-	memcpy(s->cString + start, [replacement cString],
-	    [replacement cStringLength]);
+	    replacement->s->cStringLength, s->cStringLength - end);
+	memcpy(s->cString + start, replacement->s->cString,
+	    replacement->s->cStringLength);
 	s->cString[newCStringLength] = '\0';
 
 	s->cStringLength = newCStringLength;
+	s->length = newLength;
 }
 
 - (void)replaceCharactersInRange: (of_range_t)range
 		      withString: (OFString*)replacement
 {
@@ -505,20 +519,21 @@
 - (void)replaceOccurrencesOfString: (OFString*)string
 			withString: (OFString*)replacement
 {
 	const char *cString = [string cString];
 	const char *replacementCString = [replacement cString];
-	size_t cStringLength = [string cStringLength];
-	size_t replacementCStringLength = [replacement cStringLength];
-	size_t i, last, newCStringLength;
+	size_t cStringLength = string->s->cStringLength;
+	size_t replacementCStringLength = replacement->s->cStringLength;
+	size_t i, last, newCStringLength, newLength;
 	char *newCString;
 
 	if (cStringLength > s->cStringLength)
 		return;
 
 	newCString = NULL;
 	newCStringLength = 0;
+	newLength = s->length;
 
 	for (i = 0, last = 0; i <= s->cStringLength - cStringLength; i++) {
 		if (memcmp(s->cString + i, cString, cStringLength))
 			continue;
 
@@ -533,11 +548,15 @@
 		}
 		memcpy(newCString + newCStringLength, s->cString + last,
 		    i - last);
 		memcpy(newCString + newCStringLength + i - last,
 		    replacementCString, replacementCStringLength);
+
 		newCStringLength += i - last + replacementCStringLength;
+		newLength = newLength - string->s->length +
+		    replacement->s->length;
+
 		i += cStringLength - 1;
 		last = i + 1;
 	}
 
 	@try {
@@ -555,10 +574,11 @@
 	newCString[newCStringLength] = 0;
 
 	[self freeMemory: s->cString];
 	s->cString = newCString;
 	s->cStringLength = newCStringLength;
+	s->length = newLength;
 }
 
 - (void)deleteLeadingWhitespaces
 {
 	size_t i;
@@ -567,10 +587,12 @@
 		if (s->cString[i] != ' '  && s->cString[i] != '\t' &&
 		    s->cString[i] != '\n' && s->cString[i] != '\r')
 			break;
 
 	s->cStringLength -= i;
+	s->length -= i;
+
 	memmove(s->cString, s->cString + i, s->cStringLength);
 	s->cString[s->cStringLength] = '\0';
 
 	@try {
 		s->cString = [self resizeMemory: s->cString
@@ -594,10 +616,11 @@
 		*p = '\0';
 		d++;
 	}
 
 	s->cStringLength -= d;
+	s->length -= d;
 
 	@try {
 		s->cString = [self resizeMemory: s->cString
 					 toSize: s->cStringLength + 1];
 	} @catch (OFOutOfMemoryException *e) {
@@ -619,17 +642,20 @@
 		*p = '\0';
 		d++;
 	}
 
 	s->cStringLength -= d;
+	s->length -= d;
 
 	for (i = 0; i < s->cStringLength; i++)
 		if (s->cString[i] != ' '  && s->cString[i] != '\t' &&
 		    s->cString[i] != '\n' && s->cString[i] != '\r')
 			break;
 
 	s->cStringLength -= i;
+	s->length -= i;
+
 	memmove(s->cString, s->cString + i, s->cStringLength);
 	s->cString[s->cStringLength] = '\0';
 
 	@try {
 		s->cString = [self resizeMemory: s->cString