Tcl Source Code

2009-02-17  Don Porter  <[email protected]>












	* generic/tclStringObj.c:	Revise buffer growth implementation
	in ExtendStringRepWithUnicode.  Use cheap checks to determine that
	no reallocation is necessary without cost of computing the precise
	number of bytes needed.  Also make use of the string growth algortihm
	in the case of repeated appends.

2009-02-17  Don Porter  <[email protected]>

	* generic/tclStringObj.c:	Factor out common GrowStringBuffer().

	* generic/tclStringObj.c:	Convert Tcl_AppendStringsToObj into
	* tests/stringObj.test:		a radically simpler implementation
	where we just loop over calls to Tcl_AppendToObj.  This fixes [Bug
	2597185].  It also creates a *** POTENTIAL INCOMPATIBILITY *** in
	that T_ASTO can now allocate more space than is strictly required,
	like all the other Tcl_Append* routines.  The incompatibility was
	detected by test stringObj-6.5, which I've updated to reflect the
	new behavior.

	* generic/tclStringObj.c:	Revise buffer growth implementation
	in ExtendStringRepWithUnicode.  Use cheap checks to determine that
	no reallocation is necessary without cost of computing the precise
	number of bytes needed.  Also make use of the string growth algortihm
	in the case of repeated appends.

 *
 * Copyright (c) 1995-1997 Sun Microsystems, Inc.
 * Copyright (c) 1999 by Scriptics Corporation.
 *
 * See the file "license.terms" for information on usage and redistribution of
 * this file, and for a DISCLAIMER OF ALL WARRANTIES.
 *
 * RCS: @(#) $Id: tclStringObj.c,v 1.110 2009/02/17 06:52:05 dgp Exp $ */

#include "tclInt.h"
#include "tommath.h"

/*
 * Prototypes for functions defined later in this file:
 */
................................................................................
static int		ExtendStringRepWithUnicode(Tcl_Obj *objPtr,
			    const Tcl_UniChar *unicode, int numChars);
static void		ExtendUnicodeRepWithString(Tcl_Obj *objPtr,
			    const char *bytes, int numBytes,
			    int numAppendChars);
static void		FillUnicodeRep(Tcl_Obj *objPtr);
static void		FreeStringInternalRep(Tcl_Obj *objPtr);

static int		SetStringFromAny(Tcl_Interp *interp, Tcl_Obj *objPtr);
static void		SetUnicodeObj(Tcl_Obj *objPtr,
			    const Tcl_UniChar *unicode, int numChars);
static int		UnicodeLength(const Tcl_UniChar *unicode);
static void		UpdateStringOfString(Tcl_Obj *objPtr);

/*
................................................................................
 *				the double allocation has failed. Default is
 *				1024 (1 kilobyte).
 */

#ifndef TCL_GROWTH_MIN_ALLOC
#define TCL_GROWTH_MIN_ALLOC	1024
#endif





































 
/*
 *----------------------------------------------------------------------
 *
 * Tcl_NewStringObj --
 *
 *	This function is normally called when not debugging: i.e., when
................................................................................
    if (numBytes > INT_MAX - oldLength) {
	Tcl_Panic("max size for a Tcl value (%d bytes) exceeded", INT_MAX);
    }
    newLength = numBytes + oldLength;

    stringPtr = GET_STRING(objPtr);
    if (newLength > stringPtr->allocated) {
	/*
	 * There isn't currently enough space in the string representation so
	 * allocate additional space. First, try to double the length
	 * required. If that fails, try a more modest allocation. See the "TCL
	 * STRING GROWTH ALGORITHM" comment at the top of this file for an
	 * explanation of this growth algorithm.
	 */

	/*
	 * Protect against case where unicode points into the existing
	 * stringPtr->unicode array.  Force it to follow any relocations
	 * due to the reallocs below.
	 */
	int offset = -1;
	if (bytes >= objPtr->bytes
		&& bytes <= objPtr->bytes + objPtr->length) {
	    offset = bytes - objPtr->bytes;
	}

	if (Tcl_AttemptSetObjLength(objPtr, 2 * newLength) == 0) {
	    /*
	     * Take care computing the amount of modest growth to avoid
	     * overflow into invalid argument values for Tcl_SetObjLength.
	     */
	    unsigned int limit = INT_MAX - newLength;
	    unsigned int extra = numBytes + TCL_GROWTH_MIN_ALLOC;
	    int growth = (int) ((extra > limit) ? limit : extra);

	    Tcl_SetObjLength(objPtr, newLength + growth);
	}

	/* Relocate bytes if needed; see above. */
	if (offset >= 0) {
	    bytes = objPtr->bytes + offset;
	}
    }

................................................................................
    stringPtr->numChars = -1;
    stringPtr->hasUnicode = 0;

    memcpy(objPtr->bytes + oldLength, bytes, numBytes);
    objPtr->bytes[newLength] = 0;
    objPtr->length = newLength;
}

 
/*
 *----------------------------------------------------------------------
 *
 * Tcl_AppendStringsToObjVA --
 *
 *	This function appends one or more null-terminated strings to an
................................................................................
 */

void
Tcl_AppendStringsToObjVA(
    Tcl_Obj *objPtr,		/* Points to the object to append to. */
    va_list argList)		/* Variable argument list. */
{
#define STATIC_LIST_SIZE 16
    String *stringPtr;
    int newLength, oldLength, attemptLength;
    char *string, *dst;
    char *static_list[STATIC_LIST_SIZE];
    char **args = static_list;
    int nargs_space = STATIC_LIST_SIZE;
    int nargs, i;

    if (Tcl_IsShared(objPtr)) {
	Tcl_Panic("%s called with shared object", "Tcl_AppendStringsToObj");
    }

    SetStringFromAny(NULL, objPtr);

    /*
     * Figure out how much space is needed for all the strings, and expand the
     * string representation if it isn't big enough. If no bytes would be
     * appended, just return. Note that on some platforms (notably OS/390) the
     * argList is an array so we need to use memcpy.
     */

    nargs = 0;
    newLength = 0;
    oldLength = objPtr->length;
    while (1) {
	string = va_arg(argList, char *);
	if (string == NULL) {
	    break;
	}
	if (nargs >= nargs_space) {
	    /*
	     * Expand the args buffer.
	     */


	    nargs_space += STATIC_LIST_SIZE;
	    if (args == static_list) {
		args = (void *) ckalloc(nargs_space * sizeof(char *));
		for (i = 0; i < nargs; ++i) {
		    args[i] = static_list[i];
		}
	    } else {
		args = (void *) ckrealloc((void *) args,
			nargs_space * sizeof(char *));
	    }
	}
	newLength += strlen(string);
	args[nargs++] = string;
    }
    if (newLength == 0) {
	goto done;
    }

    stringPtr = GET_STRING(objPtr);
    /* TODO: pure unicode will crash! */
    if (oldLength + newLength > stringPtr->allocated) {
	/*
	 * There isn't currently enough space in the string representation, so
	 * allocate additional space. If the current string representation
	 * isn't empty (i.e. it looks like we're doing a series of appends)
	 * then try to allocate extra space to accomodate future growth: first
	 * try to double the required memory; if that fails, try a more modest
	 * allocation. See the "TCL STRING GROWTH ALGORITHM" comment at the
	 * top of this file for an explanation of this growth algorithm.
	 * Otherwise, if the current string representation is empty, exactly
	 * enough memory is allocated.
	 */

	if (oldLength == 0) {
	    Tcl_SetObjLength(objPtr, newLength);
	} else {
	    attemptLength = 2 * (oldLength + newLength);
	    if (Tcl_AttemptSetObjLength(objPtr, attemptLength) == 0) {
		attemptLength = oldLength + (2 * newLength) +
			TCL_GROWTH_MIN_ALLOC;
		Tcl_SetObjLength(objPtr, attemptLength);
	    }
	}
    }

    /*
     * Make a second pass through the arguments, appending all the strings to
     * the object.
     */

    dst = objPtr->bytes + oldLength;
    for (i = 0; i < nargs; ++i) {
	string = args[i];
	if (string == NULL) {
	    break;
	}
	while (*string != 0) {
	    *dst = *string;
	    dst++;
	    string++;
	}
    }

    /*
     * Add a null byte to terminate the string. However, be careful: it's
     * possible that the object is totally empty (if it was empty originally
     * and there was nothing to append). In this case dst is NULL; just leave
     * everything alone.
     */

    if (dst != NULL) {
	*dst = 0;
    }
    objPtr->length = oldLength + newLength;

  done:
    /*
     * If we had to allocate a buffer from the heap, free it now.
     */

    if (args != static_list) {
	ckfree((char *) args);
    }
#undef STATIC_LIST_SIZE
}
 
/*
 *----------------------------------------------------------------------
 *
 * Tcl_AppendStringsToObj --
 *
................................................................................
    }
    if (size < 0) {
	Tcl_Panic("max size for a Tcl value (%d bytes) exceeded", INT_MAX);
    }

    /* Grow space if needed */
    if (size > stringPtr->allocated) {
	if (stringPtr->allocated == 0) {
	    /* First allocation - just big enough */
	    objPtr->bytes = ckrealloc(objPtr->bytes, (unsigned) size+1);
	    stringPtr->allocated = size;
	} else {
	    /* Subsequent appends - apply the growth algorithm. */
	    if (Tcl_AttemptSetObjLength(objPtr, 2 * size) == 0) {
		/*
		 * Take care computing the amount of modest growth to avoid
		 * overflow into invalid argument values for Tcl_SetObjLength.
		 */
		unsigned int limit = INT_MAX - size;
		unsigned int extra = size - objPtr->length
			+ TCL_GROWTH_MIN_ALLOC;
		int growth = (int) ((extra > limit) ? limit : extra);

		Tcl_SetObjLength(objPtr, size + growth);
	    }
	}
    }

    copyBytes:
    dst = objPtr->bytes + origLength;
    for (i = 0; i < numChars; i++) {
	dst += Tcl_UniCharToUtf((int) unicode[i], dst);
    }

 *
 * Copyright (c) 1995-1997 Sun Microsystems, Inc.
 * Copyright (c) 1999 by Scriptics Corporation.
 *
 * See the file "license.terms" for information on usage and redistribution of
 * this file, and for a DISCLAIMER OF ALL WARRANTIES.
 *
 * RCS: @(#) $Id: tclStringObj.c,v 1.111 2009/02/17 17:17:32 dgp Exp $ */

#include "tclInt.h"
#include "tommath.h"

/*
 * Prototypes for functions defined later in this file:
 */
................................................................................
static int		ExtendStringRepWithUnicode(Tcl_Obj *objPtr,
			    const Tcl_UniChar *unicode, int numChars);
static void		ExtendUnicodeRepWithString(Tcl_Obj *objPtr,
			    const char *bytes, int numBytes,
			    int numAppendChars);
static void		FillUnicodeRep(Tcl_Obj *objPtr);
static void		FreeStringInternalRep(Tcl_Obj *objPtr);
static void		GrowStringBuffer(Tcl_Obj *objPtr, int needed, int flag);
static int		SetStringFromAny(Tcl_Interp *interp, Tcl_Obj *objPtr);
static void		SetUnicodeObj(Tcl_Obj *objPtr,
			    const Tcl_UniChar *unicode, int numChars);
static int		UnicodeLength(const Tcl_UniChar *unicode);
static void		UpdateStringOfString(Tcl_Obj *objPtr);

/*
................................................................................
 *				the double allocation has failed. Default is
 *				1024 (1 kilobyte).
 */

#ifndef TCL_GROWTH_MIN_ALLOC
#define TCL_GROWTH_MIN_ALLOC	1024
#endif

static void
GrowStringBuffer(
    Tcl_Obj *objPtr,
    int needed,
    int flag)
{
    /* Pre-conditions: 
     *	objPtr->typePtr == &tclStringType
     *	needed > stringPtr->allocated
     *	flag || objPtr->bytes != NULL
     */
    String *stringPtr = GET_STRING(objPtr);

    if (flag && stringPtr->allocated == 0) {
	/* First allocation - just big enough */
	if (objPtr->bytes == tclEmptyStringRep) {
	    objPtr->bytes = ckalloc((unsigned) needed + 1);
	} else {
	    objPtr->bytes = ckrealloc(objPtr->bytes, (unsigned) needed + 1);
	}
	stringPtr->allocated = needed;
    } else {
	/* Subsequent appends - apply the growth algorithm. */
	if (Tcl_AttemptSetObjLength(objPtr, 2 * needed) == 0) {
	    /*
	     * Take care computing the amount of modest growth to avoid
	     * overflow into invalid argument values for Tcl_SetObjLength.
	     */
	    unsigned int limit = INT_MAX - needed;
	    unsigned int extra = needed - objPtr->length + TCL_GROWTH_MIN_ALLOC;
	    int growth = (int) ((extra > limit) ? limit : extra);

	    Tcl_SetObjLength(objPtr, needed + growth);
	}
    }
}
 
/*
 *----------------------------------------------------------------------
 *
 * Tcl_NewStringObj --
 *
 *	This function is normally called when not debugging: i.e., when
................................................................................
    if (numBytes > INT_MAX - oldLength) {
	Tcl_Panic("max size for a Tcl value (%d bytes) exceeded", INT_MAX);
    }
    newLength = numBytes + oldLength;

    stringPtr = GET_STRING(objPtr);
    if (newLength > stringPtr->allocated) {








	/*
	 * Protect against case where unicode points into the existing
	 * stringPtr->unicode array.  Force it to follow any relocations
	 * due to the reallocs below.
	 */
	int offset = -1;
	if (bytes >= objPtr->bytes
		&& bytes <= objPtr->bytes + objPtr->length) {
	    offset = bytes - objPtr->bytes;
	}

	/* TODO: consider passing flag=1: no overalloc on first append.
	 * This would make test stringObj-8.1 fail.*/







	GrowStringBuffer(objPtr, newLength, 0);


	/* Relocate bytes if needed; see above. */
	if (offset >= 0) {
	    bytes = objPtr->bytes + offset;
	}
    }

................................................................................
    stringPtr->numChars = -1;
    stringPtr->hasUnicode = 0;

    memcpy(objPtr->bytes + oldLength, bytes, numBytes);
    objPtr->bytes[newLength] = 0;
    objPtr->length = newLength;
}

 
/*
 *----------------------------------------------------------------------
 *
 * Tcl_AppendStringsToObjVA --
 *
 *	This function appends one or more null-terminated strings to an
................................................................................
 */

void
Tcl_AppendStringsToObjVA(
    Tcl_Obj *objPtr,		/* Points to the object to append to. */
    va_list argList)		/* Variable argument list. */
{









    if (Tcl_IsShared(objPtr)) {
	Tcl_Panic("%s called with shared object", "Tcl_AppendStringsToObj");
    }













    while (1) {
	const char *bytes = va_arg(argList, char *);
	if (bytes == NULL) {
	    break;
	}




	Tcl_AppendToObj(objPtr, bytes, -1);
    }




















































































}
 
/*
 *----------------------------------------------------------------------
 *
 * Tcl_AppendStringsToObj --
 *
................................................................................
    }
    if (size < 0) {
	Tcl_Panic("max size for a Tcl value (%d bytes) exceeded", INT_MAX);
    }

    /* Grow space if needed */
    if (size > stringPtr->allocated) {
	GrowStringBuffer(objPtr, size, 1);


















    }

    copyBytes:
    dst = objPtr->bytes + origLength;
    for (i = 0; i < numChars; i++) {
	dst += Tcl_UniCharToUtf((int) unicode[i], dst);
    }

#
# Copyright (c) 1995-1997 Sun Microsystems, Inc.
# Copyright (c) 1998-1999 by Scriptics Corporation.
#
# See the file "license.terms" for information on usage and redistribution of
# this file, and for a DISCLAIMER OF ALL WARRANTIES.
#
# RCS: @(#) $Id: stringObj.test,v 1.20 2009/02/16 04:33:10 dgp Exp $

if {[lsearch [namespace children] ::tcltest] == -1} {
    package require tcltest
    namespace import -force ::tcltest::*
}

testConstraint testobj [llength [info commands testobj]]
................................................................................
    list [teststringobj length 1] [teststringobj get 1]
} {15 {abc 123 abcdefg}}
test stringObj-6.5 {Tcl_AppendStringsToObj procedure, don't double space if initial string empty} testobj {
    testobj freeallvars
    testobj newobj 1
    teststringobj appendstrings 1 123 abcdefg
    list [teststringobj length 1] [teststringobj length2 1] [teststringobj get 1]
} {10 10 123abcdefg}
test stringObj-6.6 {Tcl_AppendStringsToObj procedure, space reallocation} testobj {
    testobj freeallvars
    teststringobj set 1 abc
    teststringobj setlength 1 10
    teststringobj setlength 1 2
    teststringobj appendstrings 1 34567890
    list [teststringobj length 1] [teststringobj length2 1] \

#
# Copyright (c) 1995-1997 Sun Microsystems, Inc.
# Copyright (c) 1998-1999 by Scriptics Corporation.
#
# See the file "license.terms" for information on usage and redistribution of
# this file, and for a DISCLAIMER OF ALL WARRANTIES.
#
# RCS: @(#) $Id: stringObj.test,v 1.21 2009/02/17 17:17:32 dgp Exp $

if {[lsearch [namespace children] ::tcltest] == -1} {
    package require tcltest
    namespace import -force ::tcltest::*
}

testConstraint testobj [llength [info commands testobj]]
................................................................................
    list [teststringobj length 1] [teststringobj get 1]
} {15 {abc 123 abcdefg}}
test stringObj-6.5 {Tcl_AppendStringsToObj procedure, don't double space if initial string empty} testobj {
    testobj freeallvars
    testobj newobj 1
    teststringobj appendstrings 1 123 abcdefg
    list [teststringobj length 1] [teststringobj length2 1] [teststringobj get 1]
} {10 20 123abcdefg}
test stringObj-6.6 {Tcl_AppendStringsToObj procedure, space reallocation} testobj {
    testobj freeallvars
    teststringobj set 1 abc
    teststringobj setlength 1 10
    teststringobj setlength 1 2
    teststringobj appendstrings 1 34567890
    list [teststringobj length 1] [teststringobj length2 1] \