Tcl Source Code

Check-in [9208e61ec9]
Login
Bounty program for improvements to Tcl and certain Tcl packages.
Tcl 2019 Conference, Houston/TX, US, Nov 4-8
Send your abstracts to tclconference@googlegroups.com
or submit via the online form by Sep 9.

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

Overview
Comment:more clean-up, size_t-related consolidation (prepared for unsigned object length in 9.0)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | tip-534-sebres-fast-number-hash
Files: files | file ages | folders
SHA3-256:9208e61ec95771f60ad5a44b1135e60cf6bf6776844abce71c22bacad7fdfaf0
User & Date: sebres 2019-05-17 18:26:56
Context
2019-05-17
21:54
code review check-in: 7f19c9f6b1 user: sebres tags: tip-534-sebres-fast-number-hash
18:26
more clean-up, size_t-related consolidation (prepared for unsigned object length in 9.0) check-in: 9208e61ec9 user: sebres tags: tip-534-sebres-fast-number-hash
17:43
code review (typo fixed, compiler compat, etc) + more test cases (hashing of not canonical form of i... check-in: 0c26cd8178 user: sebres tags: tip-534-sebres-fast-number-hash
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to generic/tclObj.c.

4208
4209
4210
4211
4212
4213
4214

4215
4216
4217
4218
4219
4220
4221
4222
4223
4224
4225
4226
4227
4228
4229
4230
4231
4232
....
4235
4236
4237
4238
4239
4240
4241
4242
4243
4244
4245






4246

4247
4248
4249
4250
4251
4252
4253
4254
4255
4256
4257
4258
4259
4260
4261
4262
4263
4264
4265
4266
4267
4268
4269
4270
4271
4272
....
4318
4319
4320
4321
4322
4323
4324
4325
4326
4327

4328
4329
4330
4331
4332
4333
4334
int
TclCompareObjKeys(
    void *keyPtr,		/* New key to compare. */
    Tcl_HashEntry *hPtr)	/* Existing key to compare. */
{
    register Tcl_Obj *objPtr1 = keyPtr;
    register Tcl_Obj *objPtr2 = hPtr->key.objPtr;

    register size_t l1, l2;

    /*
     * If the object pointers are the same then they match.
     * OPT: this comparison was moved to the caller
     *
     * if (objPtr1 == objPtr2) return 1;
     *
     * Normally we don't need to get strings, because if it is expected, it is
     * already done in TclHashObjKey, this is also covered by assert below.
     */

    /* Optimisation for comparing integer objects */

    if (objPtr1->typePtr == &tclIntType && objPtr2->typePtr == &tclIntType) {
	if (objPtr1->internalRep.wideValue != objPtr2->internalRep.wideValue) {
	    return 0;
	}
................................................................................
	 */

	if (IntObjIsCanonical(objPtr1) && IntObjIsCanonical(objPtr2)) {
	    return 1;
	}

	/*
	 * Compare its string representations.
	 */
    }







    l1 = objPtr1->length;

    l2 = objPtr2->length;

    /*
     * Only compare string representations of the same length.
     */

    if (l1 != l2) {
        return 0;
    } else {
	register const char *p1, *p2;

	if (!l1) { /* empty string are equal */
	    return 1;
	}

	/* compare both strings */
	p1 = objPtr1->bytes; p2 = objPtr2->bytes;

	assert(p1 != NULL && p2 != NULL);
	do {
	    if (*p1++ != *p2++) {
		return 0;
	    }
	} while (--l1);
    }
    return 1;
................................................................................

TCL_HASH_TYPE
TclHashObjKey(
    Tcl_HashTable *tablePtr,	/* Hash table. */
    void *keyPtr)		/* Key from which to compute hash value. */
{
    Tcl_Obj *objPtr = keyPtr;
    TCL_HASH_TYPE result = 0;
    int length;
    const char *string;


    /*
     * I tried a zillion different hash functions and asked many other people
     * for advice. Many people had their own favorite functions, all
     * different, but no-one had much idea why they were good ones. I chose
     * the one below (multiply by 9 and add new character) because of the
     * following reasons:







>





|
|
|
<
<
<







 







|



>
>
>
>
>
>

>









<
<





<

<







 







<
|

>







4208
4209
4210
4211
4212
4213
4214
4215
4216
4217
4218
4219
4220
4221
4222
4223



4224
4225
4226
4227
4228
4229
4230
....
4233
4234
4235
4236
4237
4238
4239
4240
4241
4242
4243
4244
4245
4246
4247
4248
4249
4250
4251
4252
4253
4254
4255
4256
4257
4258
4259
4260


4261
4262
4263
4264
4265

4266

4267
4268
4269
4270
4271
4272
4273
....
4319
4320
4321
4322
4323
4324
4325

4326
4327
4328
4329
4330
4331
4332
4333
4334
4335
int
TclCompareObjKeys(
    void *keyPtr,		/* New key to compare. */
    Tcl_HashEntry *hPtr)	/* Existing key to compare. */
{
    register Tcl_Obj *objPtr1 = keyPtr;
    register Tcl_Obj *objPtr2 = hPtr->key.objPtr;
    register const char *p1, *p2;
    register size_t l1, l2;

    /*
     * If the object pointers are the same then they match.
     * OPT: this comparison was moved to the caller

       if (objPtr1 == objPtr2) return 1;
    */




    /* Optimisation for comparing integer objects */

    if (objPtr1->typePtr == &tclIntType && objPtr2->typePtr == &tclIntType) {
	if (objPtr1->internalRep.wideValue != objPtr2->internalRep.wideValue) {
	    return 0;
	}
................................................................................
	 */

	if (IntObjIsCanonical(objPtr1) && IntObjIsCanonical(objPtr2)) {
	    return 1;
	}

	/*
	 * Compare those string representations.
	 */
    }

    /*
     * Don't use Tcl_GetStringFromObj as it would prevent l1 and l2 being
     * in a register.
     */

    p1 = TclGetString(objPtr1);
    l1 = objPtr1->length;
    p2 = TclGetString(objPtr2);
    l2 = objPtr2->length;

    /*
     * Only compare string representations of the same length.
     */

    if (l1 != l2) {
        return 0;
    } else {


	if (!l1) { /* empty string are equal */
	    return 1;
	}

	/* compare both strings */



	do {
	    if (*p1++ != *p2++) {
		return 0;
	    }
	} while (--l1);
    }
    return 1;
................................................................................

TCL_HASH_TYPE
TclHashObjKey(
    Tcl_HashTable *tablePtr,	/* Hash table. */
    void *keyPtr)		/* Key from which to compute hash value. */
{
    Tcl_Obj *objPtr = keyPtr;

    size_t length;
    const char *string;
    TCL_HASH_TYPE result = 0;

    /*
     * I tried a zillion different hash functions and asked many other people
     * for advice. Many people had their own favorite functions, all
     * different, but no-one had much idea why they were good ones. I chose
     * the one below (multiply by 9 and add new character) because of the
     * following reasons: