Tcl Source Code

Check-in [820ba0e29a]
Login
Bounty program for improvements to Tcl and certain Tcl packages.
Tcl 2019 Conference, Houston/TX, US, Nov 4-8
Send your abstracts to [email protected]
or submit via the online form by Sep 9.

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:
* 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.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk | potential incompatibility
Files: files | file ages | folders
SHA1: 820ba0e29a10df3d23fcd8e05771b3da80b0957c
User & Date: dgp 2009-02-17 17:17:32
Context
2009-02-17
18:10
* win/tcl.m4, win/configure: Check if cl groks _WIN64 already to avoid CC manipulation that can sc...
check-in: e587ee7ca9 user: hobbs tags: trunk
17:17
* generic/tclStringObj.c: Factor out common GrowStringBuffer().
* generic/tcl...
check-in: 820ba0e29a user: dgp tags: trunk, potential incompatibility
06:52
* generic/tclStringObj.c: Revise buffer growth implementation in ExtendStringR...
check-in: e188de7032 user: dgp tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ChangeLog.

1











2
3
4
5
6
7
8
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.

>
>
>
>
>
>
>
>
>
>
>







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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.

Changes to generic/tclStringObj.c.

29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
..
57
58
59
60
61
62
63

64
65
66
67
68
69
70
...
185
186
187
188
189
190
191





































192
193
194
195
196
197
198
....
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
....
1532
1533
1534
1535
1536
1537
1538

1539
1540
1541
1542
1543
1544
1545
....
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596

1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
....
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
 *
 * 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);
    }






|







 







>







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







<
<
<
<
<
<
<
<











|
|
<
<
<
<
<
<
<
|
<







 







>







 







<
<
<
<
<
<
<
<
<




<
<
<
<
<
<
<
<
<
<
<
<

|
|


<
<
<
<
>
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
..
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
...
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
....
1522
1523
1524
1525
1526
1527
1528








1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541







1542

1543
1544
1545
1546
1547
1548
1549
....
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
....
1579
1580
1581
1582
1583
1584
1585









1586
1587
1588
1589












1590
1591
1592
1593
1594




1595
1596




















































































1597
1598
1599
1600
1601
1602
1603
....
2846
2847
2848
2849
2850
2851
2852
2853


















2854
2855
2856
2857
2858
2859
2860
 *
 * 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);
    }

Changes to tests/stringObj.test.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#
# 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] \






|







 







|







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
...
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#
# 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] \