0000: 2f 2a 0a 20 2a 20 74 63 6c 48 61 73 68 2e 63 20 /*. * tclHash.c
0010: 2d 2d 0a 20 2a 0a 20 2a 09 49 6d 70 6c 65 6d 65 --. *. *.Impleme
0020: 6e 74 61 74 69 6f 6e 20 6f 66 20 69 6e 2d 6d 65 ntation of in-me
0030: 6d 6f 72 79 20 68 61 73 68 20 74 61 62 6c 65 73 mory hash tables
0040: 20 66 6f 72 20 54 63 6c 20 61 6e 64 20 54 63 6c for Tcl and Tcl
0050: 2d 62 61 73 65 64 0a 20 2a 09 61 70 70 6c 69 63 -based. *.applic
0060: 61 74 69 6f 6e 73 2e 0a 20 2a 0a 20 2a 20 43 6f ations.. *. * Co
0070: 70 79 72 69 67 68 74 20 c2 a9 20 31 39 39 31 2d pyright © 1991-
0080: 31 39 39 33 20 54 68 65 20 52 65 67 65 6e 74 73 1993 The Regents
0090: 20 6f 66 20 74 68 65 20 55 6e 69 76 65 72 73 69 of the Universi
00a0: 74 79 20 6f 66 20 43 61 6c 69 66 6f 72 6e 69 61 ty of California
00b0: 2e 0a 20 2a 20 43 6f 70 79 72 69 67 68 74 20 c2 .. * Copyright �
00c0: a9 20 31 39 39 34 20 53 75 6e 20 4d 69 63 72 6f � 1994 Sun Micro
00d0: 73 79 73 74 65 6d 73 2c 20 49 6e 63 2e 0a 20 2a systems, Inc.. *
00e0: 0a 20 2a 20 53 65 65 20 74 68 65 20 66 69 6c 65 . * See the file
00f0: 20 22 6c 69 63 65 6e 73 65 2e 74 65 72 6d 73 22 "license.terms"
0100: 20 66 6f 72 20 69 6e 66 6f 72 6d 61 74 69 6f 6e for information
0110: 20 6f 6e 20 75 73 61 67 65 20 61 6e 64 20 72 65 on usage and re
0120: 64 69 73 74 72 69 62 75 74 69 6f 6e 20 6f 66 0a distribution of.
0130: 20 2a 20 74 68 69 73 20 66 69 6c 65 2c 20 61 6e * this file, an
0140: 64 20 66 6f 72 20 61 20 44 49 53 43 4c 41 49 4d d for a DISCLAIM
0150: 45 52 20 4f 46 20 41 4c 4c 20 57 41 52 52 41 4e ER OF ALL WARRAN
0160: 54 49 45 53 2e 0a 20 2a 2f 0a 0a 23 69 6e 63 6c TIES.. */..#incl
0170: 75 64 65 20 22 74 63 6c 49 6e 74 2e 68 22 0a 0a ude "tclInt.h"..
0180: 2f 2a 0a 20 2a 20 50 72 65 76 65 6e 74 20 6d 61 /*. * Prevent ma
0190: 63 72 6f 73 20 66 72 6f 6d 20 63 6c 61 73 68 69 cros from clashi
01a0: 6e 67 20 77 69 74 68 20 66 75 6e 63 74 69 6f 6e ng with function
01b0: 20 64 65 66 69 6e 69 74 69 6f 6e 73 2e 0a 20 2a definitions.. *
01c0: 2f 0a 0a 23 75 6e 64 65 66 20 54 63 6c 5f 43 72 /..#undef Tcl_Cr
01d0: 65 61 74 65 48 61 73 68 45 6e 74 72 79 0a 0a 2f eateHashEntry../
01e0: 2a 0a 20 2a 20 57 68 65 6e 20 74 68 65 72 65 20 *. * When there
01f0: 61 72 65 20 74 68 69 73 20 6d 61 6e 79 20 65 6e are this many en
0200: 74 72 69 65 73 20 70 65 72 20 62 75 63 6b 65 74 tries per bucket
0210: 2c 20 6f 6e 20 61 76 65 72 61 67 65 2c 20 72 65 , on average, re
0220: 62 75 69 6c 64 20 74 68 65 20 68 61 73 68 0a 20 build the hash.
0230: 2a 20 74 61 62 6c 65 20 74 6f 20 6d 61 6b 65 20 * table to make
0240: 69 74 20 6c 61 72 67 65 72 2e 0a 20 2a 2f 0a 0a it larger.. */..
0250: 23 64 65 66 69 6e 65 20 52 45 42 55 49 4c 44 5f #define REBUILD_
0260: 4d 55 4c 54 49 50 4c 49 45 52 09 33 0a 0a 2f 2a MULTIPLIER.3../*
0270: 0a 20 2a 20 54 68 65 20 66 6f 6c 6c 6f 77 69 6e . * The followin
0280: 67 20 6d 61 63 72 6f 20 74 61 6b 65 73 20 61 20 g macro takes a
0290: 70 72 65 6c 69 6d 69 6e 61 72 79 20 69 6e 74 65 preliminary inte
02a0: 67 65 72 20 68 61 73 68 20 76 61 6c 75 65 20 61 ger hash value a
02b0: 6e 64 20 70 72 6f 64 75 63 65 73 20 61 6e 0a 20 nd produces an.
02c0: 2a 20 69 6e 64 65 78 20 69 6e 74 6f 20 61 20 68 * index into a h
02d0: 61 73 68 20 74 61 62 6c 65 73 20 62 75 63 6b 65 ash tables bucke
02e0: 74 20 6c 69 73 74 2e 20 54 68 65 20 69 64 65 61 t list. The idea
02f0: 20 69 73 20 74 6f 20 6d 61 6b 65 20 69 74 20 73 is to make it s
0300: 6f 20 74 68 61 74 0a 20 2a 20 70 72 65 6c 69 6d o that. * prelim
0310: 69 6e 61 72 79 20 76 61 6c 75 65 73 20 74 68 61 inary values tha
0320: 74 20 61 72 65 20 61 72 62 69 74 72 61 72 69 6c t are arbitraril
0330: 79 20 73 69 6d 69 6c 61 72 20 77 69 6c 6c 20 65 y similar will e
0340: 6e 64 20 75 70 20 69 6e 20 64 69 66 66 65 72 65 nd up in differe
0350: 6e 74 0a 20 2a 20 62 75 63 6b 65 74 73 2e 20 54 nt. * buckets. T
0360: 68 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e he hash function
0370: 20 77 61 73 20 74 61 6b 65 6e 20 66 72 6f 6d 20 was taken from
0380: 61 20 72 61 6e 64 6f 6d 2d 6e 75 6d 62 65 72 20 a random-number
0390: 67 65 6e 65 72 61 74 6f 72 2e 0a 20 2a 2f 0a 0a generator.. */..
03a0: 23 64 65 66 69 6e 65 20 52 41 4e 44 4f 4d 5f 49 #define RANDOM_I
03b0: 4e 44 45 58 28 74 61 62 6c 65 50 74 72 2c 20 69 NDEX(tablePtr, i
03c0: 29 20 5c 0a 20 20 20 20 28 28 28 28 69 29 2a 28 ) \. ((((i)*(
03d0: 73 69 7a 65 5f 74 29 31 31 30 33 35 31 35 32 34 size_t)110351524
03e0: 35 29 20 3e 3e 20 28 74 61 62 6c 65 50 74 72 29 5) >> (tablePtr)
03f0: 2d 3e 64 6f 77 6e 53 68 69 66 74 29 20 26 20 28 ->downShift) & (
0400: 74 61 62 6c 65 50 74 72 29 2d 3e 6d 61 73 6b 29 tablePtr)->mask)
0410: 0a 0a 2f 2a 0a 20 2a 20 50 72 6f 74 6f 74 79 70 ../*. * Prototyp
0420: 65 73 20 66 6f 72 20 74 68 65 20 61 72 72 61 79 es for the array
0430: 20 68 61 73 68 20 6b 65 79 20 6d 65 74 68 6f 64 hash key method
0440: 73 2e 0a 20 2a 2f 0a 0a 73 74 61 74 69 63 20 54 s.. */..static T
0450: 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 2a 09 41 cl_HashEntry *.A
0460: 6c 6c 6f 63 41 72 72 61 79 45 6e 74 72 79 28 54 llocArrayEntry(T
0470: 63 6c 5f 48 61 73 68 54 61 62 6c 65 20 2a 74 61 cl_HashTable *ta
0480: 62 6c 65 50 74 72 2c 20 76 6f 69 64 20 2a 6b 65 blePtr, void *ke
0490: 79 50 74 72 29 3b 0a 73 74 61 74 69 63 20 69 6e yPtr);.static in
04a0: 74 09 09 43 6f 6d 70 61 72 65 41 72 72 61 79 4b t..CompareArrayK
04b0: 65 79 73 28 76 6f 69 64 20 2a 6b 65 79 50 74 72 eys(void *keyPtr
04c0: 2c 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 , Tcl_HashEntry
04d0: 2a 68 50 74 72 29 3b 0a 73 74 61 74 69 63 20 73 *hPtr);.static s
04e0: 69 7a 65 5f 74 09 09 48 61 73 68 41 72 72 61 79 ize_t..HashArray
04f0: 4b 65 79 28 54 63 6c 5f 48 61 73 68 54 61 62 6c Key(Tcl_HashTabl
0500: 65 20 2a 74 61 62 6c 65 50 74 72 2c 20 76 6f 69 e *tablePtr, voi
0510: 64 20 2a 6b 65 79 50 74 72 29 3b 0a 0a 2f 2a 0a d *keyPtr);../*.
0520: 20 2a 20 50 72 6f 74 6f 74 79 70 65 73 20 66 6f * Prototypes fo
0530: 72 20 74 68 65 20 73 74 72 69 6e 67 20 68 61 73 r the string has
0540: 68 20 6b 65 79 20 6d 65 74 68 6f 64 73 2e 0a 20 h key methods..
0550: 2a 2f 0a 0a 73 74 61 74 69 63 20 54 63 6c 5f 48 */..static Tcl_H
0560: 61 73 68 45 6e 74 72 79 20 2a 09 41 6c 6c 6f 63 ashEntry *.Alloc
0570: 53 74 72 69 6e 67 45 6e 74 72 79 28 54 63 6c 5f StringEntry(Tcl_
0580: 48 61 73 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 HashTable *table
0590: 50 74 72 2c 0a 09 09 09 20 20 20 20 76 6f 69 64 Ptr,.... void
05a0: 20 2a 6b 65 79 50 74 72 29 3b 0a 0a 2f 2a 0a 20 *keyPtr);../*.
05b0: 2a 20 46 75 6e 63 74 69 6f 6e 20 70 72 6f 74 6f * Function proto
05c0: 74 79 70 65 73 20 66 6f 72 20 73 74 61 74 69 63 types for static
05d0: 20 66 75 6e 63 74 69 6f 6e 73 20 69 6e 20 74 68 functions in th
05e0: 69 73 20 66 69 6c 65 3a 0a 20 2a 2f 0a 0a 73 74 is file:. */..st
05f0: 61 74 69 63 20 54 63 6c 5f 48 61 73 68 45 6e 74 atic Tcl_HashEnt
0600: 72 79 20 2a 09 42 6f 67 75 73 43 72 65 61 74 65 ry *.BogusCreate
0610: 28 54 63 6c 5f 48 61 73 68 54 61 62 6c 65 20 2a (Tcl_HashTable *
0620: 74 61 62 6c 65 50 74 72 2c 20 63 6f 6e 73 74 20 tablePtr, const
0630: 63 68 61 72 20 2a 6b 65 79 2c 0a 09 09 09 20 20 char *key,....
0640: 20 20 69 6e 74 20 2a 6e 65 77 50 74 72 29 3b 0a int *newPtr);.
0650: 73 74 61 74 69 63 20 54 63 6c 5f 48 61 73 68 45 static Tcl_HashE
0660: 6e 74 72 79 20 2a 09 43 72 65 61 74 65 48 61 73 ntry *.CreateHas
0670: 68 45 6e 74 72 79 28 54 63 6c 5f 48 61 73 68 54 hEntry(Tcl_HashT
0680: 61 62 6c 65 20 2a 74 61 62 6c 65 50 74 72 2c 20 able *tablePtr,
0690: 63 6f 6e 73 74 20 63 68 61 72 20 2a 6b 65 79 2c const char *key,
06a0: 0a 09 09 09 20 20 20 20 69 6e 74 20 2a 6e 65 77 .... int *new
06b0: 50 74 72 29 3b 0a 23 69 66 6e 64 65 66 20 54 43 Ptr);.#ifndef TC
06c0: 4c 5f 4e 4f 5f 44 45 50 52 45 43 41 54 45 44 0a L_NO_DEPRECATED.
06d0: 73 74 61 74 69 63 20 54 63 6c 5f 48 61 73 68 45 static Tcl_HashE
06e0: 6e 74 72 79 20 2a 09 46 69 6e 64 48 61 73 68 45 ntry *.FindHashE
06f0: 6e 74 72 79 28 54 63 6c 5f 48 61 73 68 54 61 62 ntry(Tcl_HashTab
0700: 6c 65 20 2a 74 61 62 6c 65 50 74 72 2c 20 63 6f le *tablePtr, co
0710: 6e 73 74 20 63 68 61 72 20 2a 6b 65 79 29 3b 0a nst char *key);.
0720: 23 65 6e 64 69 66 0a 73 74 61 74 69 63 20 76 6f #endif.static vo
0730: 69 64 09 09 52 65 62 75 69 6c 64 54 61 62 6c 65 id..RebuildTable
0740: 28 54 63 6c 5f 48 61 73 68 54 61 62 6c 65 20 2a (Tcl_HashTable *
0750: 74 61 62 6c 65 50 74 72 29 3b 0a 0a 63 6f 6e 73 tablePtr);..cons
0760: 74 20 54 63 6c 5f 48 61 73 68 4b 65 79 54 79 70 t Tcl_HashKeyTyp
0770: 65 20 74 63 6c 41 72 72 61 79 48 61 73 68 4b 65 e tclArrayHashKe
0780: 79 54 79 70 65 20 3d 20 7b 0a 20 20 20 20 54 43 yType = {. TC
0790: 4c 5f 48 41 53 48 5f 4b 45 59 5f 54 59 50 45 5f L_HASH_KEY_TYPE_
07a0: 56 45 52 53 49 4f 4e 2c 09 09 2f 2a 20 76 65 72 VERSION,../* ver
07b0: 73 69 6f 6e 20 2a 2f 0a 20 20 20 20 54 43 4c 5f sion */. TCL_
07c0: 48 41 53 48 5f 4b 45 59 5f 52 41 4e 44 4f 4d 49 HASH_KEY_RANDOMI
07d0: 5a 45 5f 48 41 53 48 2c 09 2f 2a 20 66 6c 61 67 ZE_HASH,./* flag
07e0: 73 20 2a 2f 0a 20 20 20 20 48 61 73 68 41 72 72 s */. HashArr
07f0: 61 79 4b 65 79 2c 09 09 09 2f 2a 20 68 61 73 68 ayKey,.../* hash
0800: 4b 65 79 50 72 6f 63 20 2a 2f 0a 20 20 20 20 43 KeyProc */. C
0810: 6f 6d 70 61 72 65 41 72 72 61 79 4b 65 79 73 2c ompareArrayKeys,
0820: 09 09 09 2f 2a 20 63 6f 6d 70 61 72 65 4b 65 79 .../* compareKey
0830: 73 50 72 6f 63 20 2a 2f 0a 20 20 20 20 41 6c 6c sProc */. All
0840: 6f 63 41 72 72 61 79 45 6e 74 72 79 2c 09 09 09 ocArrayEntry,...
0850: 2f 2a 20 61 6c 6c 6f 63 45 6e 74 72 79 50 72 6f /* allocEntryPro
0860: 63 20 2a 2f 0a 20 20 20 20 4e 55 4c 4c 09 09 09 c */. NULL...
0870: 09 2f 2a 20 66 72 65 65 45 6e 74 72 79 50 72 6f ./* freeEntryPro
0880: 63 20 2a 2f 0a 7d 3b 0a 0a 63 6f 6e 73 74 20 54 c */.};..const T
0890: 63 6c 5f 48 61 73 68 4b 65 79 54 79 70 65 20 74 cl_HashKeyType t
08a0: 63 6c 4f 6e 65 57 6f 72 64 48 61 73 68 4b 65 79 clOneWordHashKey
08b0: 54 79 70 65 20 3d 20 7b 0a 20 20 20 20 54 43 4c Type = {. TCL
08c0: 5f 48 41 53 48 5f 4b 45 59 5f 54 59 50 45 5f 56 _HASH_KEY_TYPE_V
08d0: 45 52 53 49 4f 4e 2c 09 09 2f 2a 20 76 65 72 73 ERSION,../* vers
08e0: 69 6f 6e 20 2a 2f 0a 20 20 20 20 30 2c 09 09 09 ion */. 0,...
08f0: 09 09 2f 2a 20 66 6c 61 67 73 20 2a 2f 0a 20 20 ../* flags */.
0900: 20 20 4e 55 4c 4c 2c 20 2f 2a 20 48 61 73 68 4f NULL, /* HashO
0910: 6e 65 57 6f 72 64 4b 65 79 2c 20 2a 2f 09 09 2f neWordKey, */../
0920: 2a 20 68 61 73 68 50 72 6f 63 20 2a 2f 0a 20 20 * hashProc */.
0930: 20 20 4e 55 4c 4c 2c 20 2f 2a 20 43 6f 6d 70 61 NULL, /* Compa
0940: 72 65 4f 6e 65 57 6f 72 64 4b 65 79 2c 20 2a 2f reOneWordKey, */
0950: 09 2f 2a 20 63 6f 6d 70 61 72 65 50 72 6f 63 20 ./* compareProc
0960: 2a 2f 0a 20 20 20 20 4e 55 4c 4c 2c 20 2f 2a 20 */. NULL, /*
0970: 41 6c 6c 6f 63 4f 6e 65 57 6f 72 64 4b 65 79 2c AllocOneWordKey,
0980: 20 2a 2f 09 2f 2a 20 61 6c 6c 6f 63 45 6e 74 72 */./* allocEntr
0990: 79 50 72 6f 63 20 2a 2f 0a 20 20 20 20 4e 55 4c yProc */. NUL
09a0: 4c 20 20 2f 2a 20 46 72 65 65 4f 6e 65 57 6f 72 L /* FreeOneWor
09b0: 64 4b 65 79 2c 20 2a 2f 09 09 2f 2a 20 66 72 65 dKey, */../* fre
09c0: 65 45 6e 74 72 79 50 72 6f 63 20 2a 2f 0a 7d 3b eEntryProc */.};
09d0: 0a 0a 63 6f 6e 73 74 20 54 63 6c 5f 48 61 73 68 ..const Tcl_Hash
09e0: 4b 65 79 54 79 70 65 20 74 63 6c 53 74 72 69 6e KeyType tclStrin
09f0: 67 48 61 73 68 4b 65 79 54 79 70 65 20 3d 20 7b gHashKeyType = {
0a00: 0a 20 20 20 20 54 43 4c 5f 48 41 53 48 5f 4b 45 . TCL_HASH_KE
0a10: 59 5f 54 59 50 45 5f 56 45 52 53 49 4f 4e 2c 09 Y_TYPE_VERSION,.
0a20: 09 2f 2a 20 76 65 72 73 69 6f 6e 20 2a 2f 0a 20 ./* version */.
0a30: 20 20 20 30 2c 09 09 09 09 09 2f 2a 20 66 6c 61 0,...../* fla
0a40: 67 73 20 2a 2f 0a 20 20 20 20 54 63 6c 48 61 73 gs */. TclHas
0a50: 68 53 74 72 69 6e 67 4b 65 79 2c 09 09 09 2f 2a hStringKey,.../*
0a60: 20 68 61 73 68 4b 65 79 50 72 6f 63 20 2a 2f 0a hashKeyProc */.
0a70: 20 20 20 20 54 63 6c 43 6f 6d 70 61 72 65 53 74 TclCompareSt
0a80: 72 69 6e 67 4b 65 79 73 2c 09 09 2f 2a 20 63 6f ringKeys,../* co
0a90: 6d 70 61 72 65 4b 65 79 73 50 72 6f 63 20 2a 2f mpareKeysProc */
0aa0: 0a 20 20 20 20 41 6c 6c 6f 63 53 74 72 69 6e 67 . AllocString
0ab0: 45 6e 74 72 79 2c 09 09 09 2f 2a 20 61 6c 6c 6f Entry,.../* allo
0ac0: 63 45 6e 74 72 79 50 72 6f 63 20 2a 2f 0a 20 20 cEntryProc */.
0ad0: 20 20 4e 55 4c 4c 09 09 09 09 2f 2a 20 66 72 65 NULL..../* fre
0ae0: 65 45 6e 74 72 79 50 72 6f 63 20 2a 2f 0a 7d 3b eEntryProc */.};
0af0: 0a 0c 0a 2f 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d .../*. *--------
0b00: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0b10: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0b20: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0b30: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 --------------.
0b40: 2a 0a 20 2a 20 54 63 6c 5f 49 6e 69 74 48 61 73 *. * Tcl_InitHas
0b50: 68 54 61 62 6c 65 20 2d 2d 0a 20 2a 0a 20 2a 09 hTable --. *. *.
0b60: 47 69 76 65 6e 20 73 74 6f 72 61 67 65 20 66 6f Given storage fo
0b70: 72 20 61 20 68 61 73 68 20 74 61 62 6c 65 2c 20 r a hash table,
0b80: 73 65 74 20 75 70 20 74 68 65 20 66 69 65 6c 64 set up the field
0b90: 73 20 74 6f 20 70 72 65 70 61 72 65 20 74 68 65 s to prepare the
0ba0: 20 68 61 73 68 0a 20 2a 09 74 61 62 6c 65 20 66 hash. *.table f
0bb0: 6f 72 20 75 73 65 2e 0a 20 2a 0a 20 2a 20 52 65 or use.. *. * Re
0bc0: 73 75 6c 74 73 3a 0a 20 2a 09 4e 6f 6e 65 2e 0a sults:. *.None..
0bd0: 20 2a 0a 20 2a 20 53 69 64 65 20 65 66 66 65 63 *. * Side effec
0be0: 74 73 3a 0a 20 2a 09 54 61 62 6c 65 50 74 72 20 ts:. *.TablePtr
0bf0: 69 73 20 6e 6f 77 20 72 65 61 64 79 20 74 6f 20 is now ready to
0c00: 62 65 20 70 61 73 73 65 64 20 74 6f 20 54 63 6c be passed to Tcl
0c10: 5f 46 69 6e 64 48 61 73 68 45 6e 74 72 79 20 61 _FindHashEntry a
0c20: 6e 64 0a 20 2a 09 54 63 6c 5f 43 72 65 61 74 65 nd. *.Tcl_Create
0c30: 48 61 73 68 45 6e 74 72 79 2e 0a 20 2a 0a 20 2a HashEntry.. *. *
0c40: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0c50: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0c60: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0c70: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0c80: 2d 2d 2d 2d 2d 2d 0a 20 2a 2f 0a 0a 76 6f 69 64 ------. */..void
0c90: 0a 54 63 6c 5f 49 6e 69 74 48 61 73 68 54 61 62 .Tcl_InitHashTab
0ca0: 6c 65 28 0a 20 20 20 20 54 63 6c 5f 48 61 73 68 le(. Tcl_Hash
0cb0: 54 61 62 6c 65 20 2a 74 61 62 6c 65 50 74 72 2c Table *tablePtr,
0cc0: 09 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 74 ./* Pointer to t
0cd0: 61 62 6c 65 20 72 65 63 6f 72 64 2c 20 77 68 69 able record, whi
0ce0: 63 68 20 69 73 20 73 75 70 70 6c 69 65 64 0a 09 ch is supplied..
0cf0: 09 09 09 20 2a 20 62 79 20 74 68 65 20 63 61 6c ... * by the cal
0d00: 6c 65 72 2e 20 2a 2f 0a 20 20 20 20 69 6e 74 20 ler. */. int
0d10: 6b 65 79 54 79 70 65 29 09 09 2f 2a 20 54 79 70 keyType)../* Typ
0d20: 65 20 6f 66 20 6b 65 79 73 20 74 6f 20 75 73 65 e of keys to use
0d30: 20 69 6e 20 74 61 62 6c 65 3a 0a 09 09 09 09 20 in table:.....
0d40: 2a 20 54 43 4c 5f 53 54 52 49 4e 47 5f 4b 45 59 * TCL_STRING_KEY
0d50: 53 2c 20 54 43 4c 5f 4f 4e 45 5f 57 4f 52 44 5f S, TCL_ONE_WORD_
0d60: 4b 45 59 53 2c 20 6f 72 20 61 6e 0a 09 09 09 09 KEYS, or an.....
0d70: 20 2a 20 69 6e 74 65 67 65 72 20 3e 3d 20 32 2e * integer >= 2.
0d80: 20 2a 2f 0a 7b 0a 20 20 20 20 2f 2a 0a 20 20 20 */.{. /*.
0d90: 20 20 2a 20 55 73 65 20 61 20 73 70 65 63 69 61 * Use a specia
0da0: 6c 20 76 61 6c 75 65 20 74 6f 20 69 6e 66 6f 72 l value to infor
0db0: 6d 20 74 68 65 20 65 78 74 65 6e 64 65 64 20 76 m the extended v
0dc0: 65 72 73 69 6f 6e 20 74 68 61 74 20 69 74 20 6d ersion that it m
0dd0: 75 73 74 20 6e 6f 74 0a 20 20 20 20 20 2a 20 61 ust not. * a
0de0: 63 63 65 73 73 20 61 6e 79 20 6f 66 20 74 68 65 ccess any of the
0df0: 20 6e 65 77 20 66 69 65 6c 64 73 20 69 6e 20 74 new fields in t
0e00: 68 65 20 54 63 6c 5f 48 61 73 68 54 61 62 6c 65 he Tcl_HashTable
0e10: 2e 20 49 66 20 61 6e 20 65 78 74 65 6e 73 69 6f . If an extensio
0e20: 6e 20 69 73 0a 20 20 20 20 20 2a 20 72 65 62 75 n is. * rebu
0e30: 69 6c 74 20 74 68 65 6e 20 61 6e 79 20 63 61 6c ilt then any cal
0e40: 6c 73 20 74 6f 20 74 68 69 73 20 66 75 6e 63 74 ls to this funct
0e50: 69 6f 6e 20 77 69 6c 6c 20 62 65 20 72 65 64 69 ion will be redi
0e60: 72 65 63 74 65 64 20 74 6f 20 74 68 65 0a 20 20 rected to the.
0e70: 20 20 20 2a 20 65 78 74 65 6e 64 65 64 20 76 65 * extended ve
0e80: 72 73 69 6f 6e 20 62 79 20 61 20 6d 61 63 72 6f rsion by a macro
0e90: 2e 0a 20 20 20 20 20 2a 2f 0a 0a 20 20 20 20 54 .. */.. T
0ea0: 63 6c 5f 49 6e 69 74 43 75 73 74 6f 6d 48 61 73 cl_InitCustomHas
0eb0: 68 54 61 62 6c 65 28 74 61 62 6c 65 50 74 72 2c hTable(tablePtr,
0ec0: 20 6b 65 79 54 79 70 65 2c 20 28 63 6f 6e 73 74 keyType, (const
0ed0: 20 54 63 6c 5f 48 61 73 68 4b 65 79 54 79 70 65 Tcl_HashKeyType
0ee0: 20 2a 29 20 2d 31 29 3b 0a 7d 0a 0c 0a 2f 2a 0a *) -1);.}.../*.
0ef0: 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *--------------
0f00: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0f10: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0f20: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0f30: 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 54 --------. *. * T
0f40: 63 6c 5f 49 6e 69 74 43 75 73 74 6f 6d 48 61 73 cl_InitCustomHas
0f50: 68 54 61 62 6c 65 20 2d 2d 0a 20 2a 0a 20 2a 09 hTable --. *. *.
0f60: 47 69 76 65 6e 20 73 74 6f 72 61 67 65 20 66 6f Given storage fo
0f70: 72 20 61 20 68 61 73 68 20 74 61 62 6c 65 2c 20 r a hash table,
0f80: 73 65 74 20 75 70 20 74 68 65 20 66 69 65 6c 64 set up the field
0f90: 73 20 74 6f 20 70 72 65 70 61 72 65 20 74 68 65 s to prepare the
0fa0: 20 68 61 73 68 0a 20 2a 09 74 61 62 6c 65 20 66 hash. *.table f
0fb0: 6f 72 20 75 73 65 2e 20 54 68 69 73 20 69 73 20 or use. This is
0fc0: 61 6e 20 65 78 74 65 6e 64 65 64 20 76 65 72 73 an extended vers
0fd0: 69 6f 6e 20 6f 66 20 54 63 6c 5f 49 6e 69 74 48 ion of Tcl_InitH
0fe0: 61 73 68 54 61 62 6c 65 20 77 68 69 63 68 0a 20 ashTable which.
0ff0: 2a 09 73 75 70 70 6f 72 74 73 20 75 73 65 72 20 *.supports user
1000: 64 65 66 69 6e 65 64 20 6b 65 79 73 2e 0a 20 2a defined keys.. *
1010: 0a 20 2a 20 52 65 73 75 6c 74 73 3a 0a 20 2a 09 . * Results:. *.
1020: 4e 6f 6e 65 2e 0a 20 2a 0a 20 2a 20 53 69 64 65 None.. *. * Side
1030: 20 65 66 66 65 63 74 73 3a 0a 20 2a 09 54 61 62 effects:. *.Tab
1040: 6c 65 50 74 72 20 69 73 20 6e 6f 77 20 72 65 61 lePtr is now rea
1050: 64 79 20 74 6f 20 62 65 20 70 61 73 73 65 64 20 dy to be passed
1060: 74 6f 20 54 63 6c 5f 46 69 6e 64 48 61 73 68 45 to Tcl_FindHashE
1070: 6e 74 72 79 20 61 6e 64 0a 20 2a 09 54 63 6c 5f ntry and. *.Tcl_
1080: 43 72 65 61 74 65 48 61 73 68 45 6e 74 72 79 2e CreateHashEntry.
1090: 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d . *. *----------
10a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
10b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
10c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
10d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 2f ------------. */
10e0: 0a 0a 76 6f 69 64 0a 54 63 6c 5f 49 6e 69 74 43 ..void.Tcl_InitC
10f0: 75 73 74 6f 6d 48 61 73 68 54 61 62 6c 65 28 0a ustomHashTable(.
1100: 20 20 20 20 54 63 6c 5f 48 61 73 68 54 61 62 6c Tcl_HashTabl
1110: 65 20 2a 74 61 62 6c 65 50 74 72 2c 09 2f 2a 20 e *tablePtr,./*
1120: 50 6f 69 6e 74 65 72 20 74 6f 20 74 61 62 6c 65 Pointer to table
1130: 20 72 65 63 6f 72 64 2c 20 77 68 69 63 68 20 69 record, which i
1140: 73 20 73 75 70 70 6c 69 65 64 0a 09 09 09 09 20 s supplied.....
1150: 2a 20 62 79 20 74 68 65 20 63 61 6c 6c 65 72 2e * by the caller.
1160: 20 2a 2f 0a 20 20 20 20 69 6e 74 20 6b 65 79 54 */. int keyT
1170: 79 70 65 2c 09 09 2f 2a 20 54 79 70 65 20 6f 66 ype,../* Type of
1180: 20 6b 65 79 73 20 74 6f 20 75 73 65 20 69 6e 20 keys to use in
1190: 74 61 62 6c 65 3a 0a 09 09 09 09 20 2a 20 54 43 table:..... * TC
11a0: 4c 5f 53 54 52 49 4e 47 5f 4b 45 59 53 2c 20 54 L_STRING_KEYS, T
11b0: 43 4c 5f 4f 4e 45 5f 57 4f 52 44 5f 4b 45 59 53 CL_ONE_WORD_KEYS
11c0: 2c 0a 09 09 09 09 20 2a 20 54 43 4c 5f 43 55 53 ,..... * TCL_CUS
11d0: 54 4f 4d 5f 54 59 50 45 5f 4b 45 59 53 2c 20 54 TOM_TYPE_KEYS, T
11e0: 43 4c 5f 43 55 53 54 4f 4d 5f 50 54 52 5f 4b 45 CL_CUSTOM_PTR_KE
11f0: 59 53 2c 0a 09 09 09 09 20 2a 20 6f 72 20 61 6e YS,..... * or an
1200: 20 69 6e 74 65 67 65 72 20 3e 3d 20 32 2e 20 2a integer >= 2. *
1210: 2f 0a 20 20 20 20 63 6f 6e 73 74 20 54 63 6c 5f /. const Tcl_
1220: 48 61 73 68 4b 65 79 54 79 70 65 20 2a 74 79 70 HashKeyType *typ
1230: 65 50 74 72 29 20 2f 2a 20 50 6f 69 6e 74 65 72 ePtr) /* Pointer
1240: 20 74 6f 20 73 74 72 75 63 74 75 72 65 20 77 68 to structure wh
1250: 69 63 68 20 64 65 66 69 6e 65 73 20 74 68 65 0a ich defines the.
1260: 09 09 09 09 20 2a 20 62 65 68 61 76 69 6f 75 72 .... * behaviour
1270: 20 6f 66 20 74 68 69 73 20 74 61 62 6c 65 2e 20 of this table.
1280: 2a 2f 0a 7b 0a 23 69 66 20 28 54 43 4c 5f 53 4d */.{.#if (TCL_SM
1290: 41 4c 4c 5f 48 41 53 48 5f 54 41 42 4c 45 20 21 ALL_HASH_TABLE !
12a0: 3d 20 34 29 0a 20 20 20 20 54 63 6c 5f 50 61 6e = 4). Tcl_Pan
12b0: 69 63 28 22 54 63 6c 5f 49 6e 69 74 43 75 73 74 ic("Tcl_InitCust
12c0: 6f 6d 48 61 73 68 54 61 62 6c 65 3a 20 54 43 4c omHashTable: TCL
12d0: 5f 53 4d 41 4c 4c 5f 48 41 53 48 5f 54 41 42 4c _SMALL_HASH_TABL
12e0: 45 20 69 73 20 25 64 2c 20 6e 6f 74 20 34 22 2c E is %d, not 4",
12f0: 0a 09 20 20 20 20 54 43 4c 5f 53 4d 41 4c 4c 5f .. TCL_SMALL_
1300: 48 41 53 48 5f 54 41 42 4c 45 29 3b 0a 23 65 6e HASH_TABLE);.#en
1310: 64 69 66 0a 0a 20 20 20 20 74 61 62 6c 65 50 74 dif.. tablePt
1320: 72 2d 3e 62 75 63 6b 65 74 73 20 3d 20 74 61 62 r->buckets = tab
1330: 6c 65 50 74 72 2d 3e 73 74 61 74 69 63 42 75 63 lePtr->staticBuc
1340: 6b 65 74 73 3b 0a 20 20 20 20 74 61 62 6c 65 50 kets;. tableP
1350: 74 72 2d 3e 73 74 61 74 69 63 42 75 63 6b 65 74 tr->staticBucket
1360: 73 5b 30 5d 20 3d 20 74 61 62 6c 65 50 74 72 2d s[0] = tablePtr-
1370: 3e 73 74 61 74 69 63 42 75 63 6b 65 74 73 5b 31 >staticBuckets[1
1380: 5d 20 3d 20 30 3b 0a 20 20 20 20 74 61 62 6c 65 ] = 0;. table
1390: 50 74 72 2d 3e 73 74 61 74 69 63 42 75 63 6b 65 Ptr->staticBucke
13a0: 74 73 5b 32 5d 20 3d 20 74 61 62 6c 65 50 74 72 ts[2] = tablePtr
13b0: 2d 3e 73 74 61 74 69 63 42 75 63 6b 65 74 73 5b ->staticBuckets[
13c0: 33 5d 20 3d 20 30 3b 0a 20 20 20 20 74 61 62 6c 3] = 0;. tabl
13d0: 65 50 74 72 2d 3e 6e 75 6d 42 75 63 6b 65 74 73 ePtr->numBuckets
13e0: 20 3d 20 54 43 4c 5f 53 4d 41 4c 4c 5f 48 41 53 = TCL_SMALL_HAS
13f0: 48 5f 54 41 42 4c 45 3b 0a 20 20 20 20 74 61 62 H_TABLE;. tab
1400: 6c 65 50 74 72 2d 3e 6e 75 6d 45 6e 74 72 69 65 lePtr->numEntrie
1410: 73 20 3d 20 30 3b 0a 20 20 20 20 74 61 62 6c 65 s = 0;. table
1420: 50 74 72 2d 3e 72 65 62 75 69 6c 64 53 69 7a 65 Ptr->rebuildSize
1430: 20 3d 20 54 43 4c 5f 53 4d 41 4c 4c 5f 48 41 53 = TCL_SMALL_HAS
1440: 48 5f 54 41 42 4c 45 2a 52 45 42 55 49 4c 44 5f H_TABLE*REBUILD_
1450: 4d 55 4c 54 49 50 4c 49 45 52 3b 0a 20 20 20 20 MULTIPLIER;.
1460: 74 61 62 6c 65 50 74 72 2d 3e 64 6f 77 6e 53 68 tablePtr->downSh
1470: 69 66 74 20 3d 20 32 38 3b 0a 20 20 20 20 74 61 ift = 28;. ta
1480: 62 6c 65 50 74 72 2d 3e 6d 61 73 6b 20 3d 20 33 blePtr->mask = 3
1490: 3b 0a 20 20 20 20 74 61 62 6c 65 50 74 72 2d 3e ;. tablePtr->
14a0: 6b 65 79 54 79 70 65 20 3d 20 6b 65 79 54 79 70 keyType = keyTyp
14b0: 65 3b 0a 23 69 66 6e 64 65 66 20 54 43 4c 5f 4e e;.#ifndef TCL_N
14c0: 4f 5f 44 45 50 52 45 43 41 54 45 44 0a 20 20 20 O_DEPRECATED.
14d0: 20 74 61 62 6c 65 50 74 72 2d 3e 66 69 6e 64 50 tablePtr->findP
14e0: 72 6f 63 20 3d 20 46 69 6e 64 48 61 73 68 45 6e roc = FindHashEn
14f0: 74 72 79 3b 0a 23 65 6e 64 69 66 0a 20 20 20 20 try;.#endif.
1500: 74 61 62 6c 65 50 74 72 2d 3e 63 72 65 61 74 65 tablePtr->create
1510: 50 72 6f 63 20 3d 20 43 72 65 61 74 65 48 61 73 Proc = CreateHas
1520: 68 45 6e 74 72 79 3b 0a 0a 20 20 20 20 69 66 20 hEntry;.. if
1530: 28 74 79 70 65 50 74 72 20 3d 3d 20 4e 55 4c 4c (typePtr == NULL
1540: 29 20 7b 0a 09 2f 2a 0a 09 20 2a 20 54 68 65 20 ) {../*.. * The
1550: 63 61 6c 6c 65 72 20 68 61 73 20 62 65 65 6e 20 caller has been
1560: 72 65 62 75 69 6c 74 20 73 6f 20 74 68 65 20 68 rebuilt so the h
1570: 61 73 68 20 74 61 62 6c 65 20 69 73 20 61 6e 20 ash table is an
1580: 65 78 74 65 6e 64 65 64 0a 09 20 2a 20 76 65 72 extended.. * ver
1590: 73 69 6f 6e 2e 0a 09 20 2a 2f 0a 20 20 20 20 7d sion... */. }
15a0: 20 65 6c 73 65 20 69 66 20 28 74 79 70 65 50 74 else if (typePt
15b0: 72 20 21 3d 20 28 54 63 6c 5f 48 61 73 68 4b 65 r != (Tcl_HashKe
15c0: 79 54 79 70 65 20 2a 29 20 2d 31 29 20 7b 0a 09 yType *) -1) {..
15d0: 2f 2a 0a 09 20 2a 20 54 68 65 20 63 61 6c 6c 65 /*.. * The calle
15e0: 72 20 69 73 20 72 65 71 75 65 73 74 69 6e 67 20 r is requesting
15f0: 61 20 63 75 73 74 6f 6d 69 7a 65 64 20 68 61 73 a customized has
1600: 68 20 74 61 62 6c 65 20 73 6f 20 69 74 20 6d 75 h table so it mu
1610: 73 74 20 62 65 20 61 6e 0a 09 20 2a 20 65 78 74 st be an.. * ext
1620: 65 6e 64 65 64 20 76 65 72 73 69 6f 6e 2e 0a 09 ended version...
1630: 20 2a 2f 0a 0a 09 74 61 62 6c 65 50 74 72 2d 3e */...tablePtr->
1640: 74 79 70 65 50 74 72 20 3d 20 74 79 70 65 50 74 typePtr = typePt
1650: 72 3b 0a 20 20 20 20 7d 20 65 6c 73 65 20 7b 0a r;. } else {.
1660: 09 2f 2a 0a 09 20 2a 20 54 68 65 20 63 61 6c 6c ./*.. * The call
1670: 65 72 20 68 61 73 20 6e 6f 74 20 62 65 65 6e 20 er has not been
1680: 72 65 62 75 69 6c 74 20 73 6f 20 74 68 65 20 68 rebuilt so the h
1690: 61 73 68 20 74 61 62 6c 65 20 69 73 20 6e 6f 74 ash table is not
16a0: 20 65 78 74 65 6e 64 65 64 2e 0a 09 20 2a 2f 0a extended... */.
16b0: 20 20 20 20 7d 0a 7d 0a 0c 0a 2f 2a 0a 20 2a 2d }.}.../*. *-
16c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
16d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
16e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
16f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1700: 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 46 69 6e 64 -----. *. * Find
1710: 48 61 73 68 45 6e 74 72 79 20 2d 2d 0a 20 2a 0a HashEntry --. *.
1720: 20 2a 09 47 69 76 65 6e 20 61 20 68 61 73 68 20 *.Given a hash
1730: 74 61 62 6c 65 20 66 69 6e 64 20 74 68 65 20 65 table find the e
1740: 6e 74 72 79 20 77 69 74 68 20 61 20 6d 61 74 63 ntry with a matc
1750: 68 69 6e 67 20 6b 65 79 2e 0a 20 2a 0a 20 2a 20 hing key.. *. *
1760: 52 65 73 75 6c 74 73 3a 0a 20 2a 09 54 68 65 20 Results:. *.The
1770: 72 65 74 75 72 6e 20 76 61 6c 75 65 20 69 73 20 return value is
1780: 61 20 74 6f 6b 65 6e 20 66 6f 72 20 74 68 65 20 a token for the
1790: 6d 61 74 63 68 69 6e 67 20 65 6e 74 72 79 20 69 matching entry i
17a0: 6e 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 n the hash table
17b0: 2c 0a 20 2a 09 6f 72 20 4e 55 4c 4c 20 69 66 20 ,. *.or NULL if
17c0: 74 68 65 72 65 20 77 61 73 20 6e 6f 20 6d 61 74 there was no mat
17d0: 63 68 69 6e 67 20 65 6e 74 72 79 2e 0a 20 2a 0a ching entry.. *.
17e0: 20 2a 20 53 69 64 65 20 65 66 66 65 63 74 73 3a * Side effects:
17f0: 0a 20 2a 09 4e 6f 6e 65 2e 0a 20 2a 0a 20 2a 2d . *.None.. *. *-
1800: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1810: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1820: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1830: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1840: 2d 2d 2d 2d 2d 0a 20 2a 2f 0a 0a 23 69 66 6e 64 -----. */..#ifnd
1850: 65 66 20 54 43 4c 5f 4e 4f 5f 44 45 50 52 45 43 ef TCL_NO_DEPREC
1860: 41 54 45 44 0a 73 74 61 74 69 63 20 54 63 6c 5f ATED.static Tcl_
1870: 48 61 73 68 45 6e 74 72 79 20 2a 0a 46 69 6e 64 HashEntry *.Find
1880: 48 61 73 68 45 6e 74 72 79 28 0a 20 20 20 20 54 HashEntry(. T
1890: 63 6c 5f 48 61 73 68 54 61 62 6c 65 20 2a 74 61 cl_HashTable *ta
18a0: 62 6c 65 50 74 72 2c 09 2f 2a 20 54 61 62 6c 65 blePtr,./* Table
18b0: 20 69 6e 20 77 68 69 63 68 20 74 6f 20 6c 6f 6f in which to loo
18c0: 6b 75 70 20 65 6e 74 72 79 2e 20 2a 2f 0a 20 20 kup entry. */.
18d0: 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 6b 65 const char *ke
18e0: 79 29 09 09 2f 2a 20 4b 65 79 20 74 6f 20 75 73 y)../* Key to us
18f0: 65 20 74 6f 20 66 69 6e 64 20 6d 61 74 63 68 69 e to find matchi
1900: 6e 67 20 65 6e 74 72 79 2e 20 2a 2f 0a 7b 0a 20 ng entry. */.{.
1910: 20 20 20 72 65 74 75 72 6e 20 74 61 62 6c 65 50 return tableP
1920: 74 72 2d 3e 63 72 65 61 74 65 50 72 6f 63 28 74 tr->createProc(t
1930: 61 62 6c 65 50 74 72 2c 20 6b 65 79 2c 20 54 43 ablePtr, key, TC
1940: 4c 5f 48 41 53 48 5f 46 49 4e 44 29 3b 0a 7d 0a L_HASH_FIND);.}.
1950: 23 65 6e 64 69 66 0a 0c 0a 2f 2a 0a 20 2a 2d 2d #endif.../*. *--
1960: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1970: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1980: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1990: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
19a0: 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 54 63 6c 5f 43 ----. *. * Tcl_C
19b0: 72 65 61 74 65 48 61 73 68 45 6e 74 72 79 20 2d reateHashEntry -
19c0: 2d 0a 20 2a 0a 20 2a 09 47 69 76 65 6e 20 61 20 -. *. *.Given a
19d0: 68 61 73 68 20 74 61 62 6c 65 20 77 69 74 68 20 hash table with
19e0: 73 74 72 69 6e 67 20 6b 65 79 73 2c 20 61 6e 64 string keys, and
19f0: 20 61 20 73 74 72 69 6e 67 20 6b 65 79 2c 20 66 a string key, f
1a00: 69 6e 64 20 74 68 65 20 65 6e 74 72 79 0a 20 2a ind the entry. *
1a10: 09 77 69 74 68 20 61 20 6d 61 74 63 68 69 6e 67 .with a matching
1a20: 20 6b 65 79 2e 20 49 66 20 74 68 65 72 65 20 69 key. If there i
1a30: 73 20 6e 6f 20 6d 61 74 63 68 69 6e 67 20 65 6e s no matching en
1a40: 74 72 79 2c 20 74 68 65 6e 20 63 72 65 61 74 65 try, then create
1a50: 20 61 20 6e 65 77 0a 20 2a 09 65 6e 74 72 79 20 a new. *.entry
1a60: 74 68 61 74 20 64 6f 65 73 20 6d 61 74 63 68 2e that does match.
1a70: 0a 20 2a 0a 20 2a 20 52 65 73 75 6c 74 73 3a 0a . *. * Results:.
1a80: 20 2a 09 54 68 65 20 72 65 74 75 72 6e 20 76 61 *.The return va
1a90: 6c 75 65 20 69 73 20 61 20 70 6f 69 6e 74 65 72 lue is a pointer
1aa0: 20 74 6f 20 74 68 65 20 6d 61 74 63 68 69 6e 67 to the matching
1ab0: 20 65 6e 74 72 79 2e 20 49 66 20 74 68 69 73 20 entry. If this
1ac0: 69 73 20 61 0a 20 2a 09 6e 65 77 6c 79 2d 63 72 is a. *.newly-cr
1ad0: 65 61 74 65 64 20 65 6e 74 72 79 2c 20 74 68 65 eated entry, the
1ae0: 6e 20 2a 6e 65 77 50 74 72 20 77 69 6c 6c 20 62 n *newPtr will b
1af0: 65 20 73 65 74 20 74 6f 20 61 20 6e 6f 6e 2d 7a e set to a non-z
1b00: 65 72 6f 20 76 61 6c 75 65 3b 0a 20 2a 09 6f 74 ero value;. *.ot
1b10: 68 65 72 77 69 73 65 20 2a 6e 65 77 50 74 72 20 herwise *newPtr
1b20: 77 69 6c 6c 20 62 65 20 73 65 74 20 74 6f 20 30 will be set to 0
1b30: 2e 20 49 66 20 74 68 69 73 20 69 73 20 61 20 6e . If this is a n
1b40: 65 77 20 65 6e 74 72 79 20 74 68 65 20 76 61 6c ew entry the val
1b50: 75 65 0a 20 2a 09 73 74 6f 72 65 64 20 69 6e 20 ue. *.stored in
1b60: 74 68 65 20 65 6e 74 72 79 20 77 69 6c 6c 20 69 the entry will i
1b70: 6e 69 74 69 61 6c 6c 79 20 62 65 20 30 2e 0a 20 nitially be 0..
1b80: 2a 0a 20 2a 20 53 69 64 65 20 65 66 66 65 63 74 *. * Side effect
1b90: 73 3a 0a 20 2a 09 41 20 6e 65 77 20 65 6e 74 72 s:. *.A new entr
1ba0: 79 20 6d 61 79 20 62 65 20 61 64 64 65 64 20 74 y may be added t
1bb0: 6f 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 o the hash table
1bc0: 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d .. *. *---------
1bd0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1be0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1bf0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1c00: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a -------------. *
1c10: 2f 0a 0a 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 /..Tcl_HashEntry
1c20: 20 2a 0a 54 63 6c 5f 43 72 65 61 74 65 48 61 73 *.Tcl_CreateHas
1c30: 68 45 6e 74 72 79 28 0a 20 20 20 20 54 63 6c 5f hEntry(. Tcl_
1c40: 48 61 73 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 HashTable *table
1c50: 50 74 72 2c 09 2f 2a 20 54 61 62 6c 65 20 69 6e Ptr,./* Table in
1c60: 20 77 68 69 63 68 20 74 6f 20 6c 6f 6f 6b 75 70 which to lookup
1c70: 20 65 6e 74 72 79 2e 20 2a 2f 0a 20 20 20 20 63 entry. */. c
1c80: 6f 6e 73 74 20 76 6f 69 64 20 2a 6b 65 79 2c 09 onst void *key,.
1c90: 09 2f 2a 20 4b 65 79 20 74 6f 20 75 73 65 20 74 ./* Key to use t
1ca0: 6f 20 66 69 6e 64 20 6f 72 20 63 72 65 61 74 65 o find or create
1cb0: 20 6d 61 74 63 68 69 6e 67 0a 09 09 09 09 20 2a matching..... *
1cc0: 20 65 6e 74 72 79 2e 20 2a 2f 0a 20 20 20 20 69 entry. */. i
1cd0: 6e 74 20 2a 6e 65 77 50 74 72 29 09 09 2f 2a 20 nt *newPtr)../*
1ce0: 53 74 6f 72 65 20 69 6e 66 6f 20 68 65 72 65 20 Store info here
1cf0: 74 65 6c 6c 69 6e 67 20 77 68 65 74 68 65 72 20 telling whether
1d00: 61 20 6e 65 77 20 65 6e 74 72 79 0a 09 09 09 09 a new entry.....
1d10: 20 2a 20 77 61 73 20 63 72 65 61 74 65 64 2e 20 * was created.
1d20: 2a 2f 0a 7b 0a 20 20 20 20 54 63 6c 5f 48 61 73 */.{. Tcl_Has
1d30: 68 45 6e 74 72 79 20 2a 65 6e 74 72 79 20 3d 20 hEntry *entry =
1d40: 28 2a 28 28 74 61 62 6c 65 50 74 72 29 2d 3e 63 (*((tablePtr)->c
1d50: 72 65 61 74 65 50 72 6f 63 29 29 28 74 61 62 6c reateProc))(tabl
1d60: 65 50 74 72 2c 20 28 63 6f 6e 73 74 20 63 68 61 ePtr, (const cha
1d70: 72 20 2a 29 6b 65 79 2c 20 6e 65 77 50 74 72 29 r *)key, newPtr)
1d80: 3b 0a 20 20 20 20 69 66 20 28 21 65 6e 74 72 79 ;. if (!entry
1d90: 29 20 7b 0a 09 54 63 6c 5f 50 61 6e 69 63 28 22 ) {..Tcl_Panic("
1da0: 25 73 3a 20 4d 65 6d 6f 72 79 20 6f 76 65 72 66 %s: Memory overf
1db0: 6c 6f 77 22 2c 20 22 54 63 6c 5f 43 72 65 61 74 low", "Tcl_Creat
1dc0: 65 48 61 73 68 45 6e 74 72 79 22 29 3b 0a 20 20 eHashEntry");.
1dd0: 20 20 7d 0a 20 20 20 20 72 65 74 75 72 6e 20 65 }. return e
1de0: 6e 74 72 79 3b 0a 7d 0a 0a 54 63 6c 5f 48 61 73 ntry;.}..Tcl_Has
1df0: 68 45 6e 74 72 79 20 2a 0a 54 63 6c 5f 44 62 43 hEntry *.Tcl_DbC
1e00: 72 65 61 74 65 48 61 73 68 45 6e 74 72 79 28 0a reateHashEntry(.
1e10: 20 20 20 20 54 63 6c 5f 48 61 73 68 54 61 62 6c Tcl_HashTabl
1e20: 65 20 2a 74 61 62 6c 65 50 74 72 2c 09 2f 2a 20 e *tablePtr,./*
1e30: 54 61 62 6c 65 20 69 6e 20 77 68 69 63 68 20 74 Table in which t
1e40: 6f 20 6c 6f 6f 6b 75 70 20 65 6e 74 72 79 2e 20 o lookup entry.
1e50: 2a 2f 0a 20 20 20 20 63 6f 6e 73 74 20 76 6f 69 */. const voi
1e60: 64 20 2a 6b 65 79 2c 09 09 2f 2a 20 4b 65 79 20 d *key,../* Key
1e70: 74 6f 20 75 73 65 20 74 6f 20 66 69 6e 64 20 6f to use to find o
1e80: 72 20 63 72 65 61 74 65 20 6d 61 74 63 68 69 6e r create matchin
1e90: 67 0a 09 09 09 09 20 2a 20 65 6e 74 72 79 2e 20 g..... * entry.
1ea0: 2a 2f 0a 20 20 20 20 69 6e 74 20 2a 6e 65 77 50 */. int *newP
1eb0: 74 72 2c 09 09 2f 2a 20 53 74 6f 72 65 20 69 6e tr,../* Store in
1ec0: 66 6f 20 68 65 72 65 20 74 65 6c 6c 69 6e 67 20 fo here telling
1ed0: 77 68 65 74 68 65 72 20 61 20 6e 65 77 20 65 6e whether a new en
1ee0: 74 72 79 0a 09 09 09 09 20 2a 20 77 61 73 20 63 try..... * was c
1ef0: 72 65 61 74 65 64 2e 20 2a 2f 0a 20 20 20 20 63 reated. */. c
1f00: 6f 6e 73 74 20 63 68 61 72 20 2a 66 69 6c 65 2c onst char *file,
1f10: 0a 20 20 20 20 69 6e 74 20 6c 69 6e 65 29 0a 7b . int line).{
1f20: 0a 20 20 20 20 54 63 6c 5f 48 61 73 68 45 6e 74 . Tcl_HashEnt
1f30: 72 79 20 2a 65 6e 74 72 79 20 3d 20 28 2a 28 28 ry *entry = (*((
1f40: 74 61 62 6c 65 50 74 72 29 2d 3e 63 72 65 61 74 tablePtr)->creat
1f50: 65 50 72 6f 63 29 29 28 74 61 62 6c 65 50 74 72 eProc))(tablePtr
1f60: 2c 20 28 63 6f 6e 73 74 20 63 68 61 72 20 2a 29 , (const char *)
1f70: 6b 65 79 2c 20 6e 65 77 50 74 72 29 3b 0a 20 20 key, newPtr);.
1f80: 20 20 69 66 20 28 21 65 6e 74 72 79 29 20 7b 0a if (!entry) {.
1f90: 09 54 63 6c 5f 50 61 6e 69 63 28 22 25 73 3a 20 .Tcl_Panic("%s:
1fa0: 4d 65 6d 6f 72 79 20 6f 76 65 72 66 6c 6f 77 20 Memory overflow
1fb0: 69 6e 20 66 69 6c 65 20 25 73 3a 25 64 22 2c 20 in file %s:%d",
1fc0: 22 54 63 6c 5f 43 72 65 61 74 65 48 61 73 68 45 "Tcl_CreateHashE
1fd0: 6e 74 72 79 22 2c 20 66 69 6c 65 2c 20 6c 69 6e ntry", file, lin
1fe0: 65 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72 65 e);. }. re
1ff0: 74 75 72 6e 20 65 6e 74 72 79 3b 0a 7d 0a 0a 73 turn entry;.}..s
2000: 74 61 74 69 63 20 54 63 6c 5f 48 61 73 68 45 6e tatic Tcl_HashEn
2010: 74 72 79 20 2a 0a 43 72 65 61 74 65 48 61 73 68 try *.CreateHash
2020: 45 6e 74 72 79 28 0a 20 20 20 20 54 63 6c 5f 48 Entry(. Tcl_H
2030: 61 73 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 50 ashTable *tableP
2040: 74 72 2c 09 2f 2a 20 54 61 62 6c 65 20 69 6e 20 tr,./* Table in
2050: 77 68 69 63 68 20 74 6f 20 6c 6f 6f 6b 75 70 20 which to lookup
2060: 65 6e 74 72 79 2e 20 2a 2f 0a 20 20 20 20 63 6f entry. */. co
2070: 6e 73 74 20 63 68 61 72 20 2a 6b 65 79 2c 09 09 nst char *key,..
2080: 2f 2a 20 4b 65 79 20 74 6f 20 75 73 65 20 74 6f /* Key to use to
2090: 20 66 69 6e 64 20 6f 72 20 63 72 65 61 74 65 20 find or create
20a0: 6d 61 74 63 68 69 6e 67 0a 09 09 09 09 20 2a 20 matching..... *
20b0: 65 6e 74 72 79 2e 20 2a 2f 0a 20 20 20 20 69 6e entry. */. in
20c0: 74 20 2a 6e 65 77 50 74 72 29 09 09 2f 2a 20 53 t *newPtr)../* S
20d0: 74 6f 72 65 20 69 6e 66 6f 20 68 65 72 65 20 74 tore info here t
20e0: 65 6c 6c 69 6e 67 20 77 68 65 74 68 65 72 20 61 elling whether a
20f0: 20 6e 65 77 20 65 6e 74 72 79 0a 09 09 09 09 20 new entry.....
2100: 2a 20 77 61 73 20 63 72 65 61 74 65 64 2e 20 2a * was created. *
2110: 2f 0a 7b 0a 20 20 20 20 54 63 6c 5f 48 61 73 68 /.{. Tcl_Hash
2120: 45 6e 74 72 79 20 2a 68 50 74 72 3b 0a 20 20 20 Entry *hPtr;.
2130: 20 63 6f 6e 73 74 20 54 63 6c 5f 48 61 73 68 4b const Tcl_HashK
2140: 65 79 54 79 70 65 20 2a 74 79 70 65 50 74 72 3b eyType *typePtr;
2150: 0a 20 20 20 20 73 69 7a 65 5f 74 20 68 61 73 68 . size_t hash
2160: 2c 20 69 6e 64 65 78 3b 0a 0a 20 20 20 20 69 66 , index;.. if
2170: 20 28 74 61 62 6c 65 50 74 72 2d 3e 6b 65 79 54 (tablePtr->keyT
2180: 79 70 65 20 3d 3d 20 54 43 4c 5f 53 54 52 49 4e ype == TCL_STRIN
2190: 47 5f 4b 45 59 53 29 20 7b 0a 09 74 79 70 65 50 G_KEYS) {..typeP
21a0: 74 72 20 3d 20 26 74 63 6c 53 74 72 69 6e 67 48 tr = &tclStringH
21b0: 61 73 68 4b 65 79 54 79 70 65 3b 0a 20 20 20 20 ashKeyType;.
21c0: 7d 20 65 6c 73 65 20 69 66 20 28 74 61 62 6c 65 } else if (table
21d0: 50 74 72 2d 3e 6b 65 79 54 79 70 65 20 3d 3d 20 Ptr->keyType ==
21e0: 54 43 4c 5f 4f 4e 45 5f 57 4f 52 44 5f 4b 45 59 TCL_ONE_WORD_KEY
21f0: 53 29 20 7b 0a 09 74 79 70 65 50 74 72 20 3d 20 S) {..typePtr =
2200: 26 74 63 6c 4f 6e 65 57 6f 72 64 48 61 73 68 4b &tclOneWordHashK
2210: 65 79 54 79 70 65 3b 0a 20 20 20 20 7d 20 65 6c eyType;. } el
2220: 73 65 20 69 66 20 28 74 61 62 6c 65 50 74 72 2d se if (tablePtr-
2230: 3e 6b 65 79 54 79 70 65 20 3d 3d 20 54 43 4c 5f >keyType == TCL_
2240: 43 55 53 54 4f 4d 5f 54 59 50 45 5f 4b 45 59 53 CUSTOM_TYPE_KEYS
2250: 0a 09 20 20 20 20 7c 7c 20 74 61 62 6c 65 50 74 .. || tablePt
2260: 72 2d 3e 6b 65 79 54 79 70 65 20 3d 3d 20 54 43 r->keyType == TC
2270: 4c 5f 43 55 53 54 4f 4d 5f 50 54 52 5f 4b 45 59 L_CUSTOM_PTR_KEY
2280: 53 29 20 7b 0a 09 74 79 70 65 50 74 72 20 3d 20 S) {..typePtr =
2290: 74 61 62 6c 65 50 74 72 2d 3e 74 79 70 65 50 74 tablePtr->typePt
22a0: 72 3b 0a 20 20 20 20 7d 20 65 6c 73 65 20 7b 0a r;. } else {.
22b0: 09 74 79 70 65 50 74 72 20 3d 20 26 74 63 6c 41 .typePtr = &tclA
22c0: 72 72 61 79 48 61 73 68 4b 65 79 54 79 70 65 3b rrayHashKeyType;
22d0: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 69 66 20 28 . }.. if (
22e0: 74 79 70 65 50 74 72 2d 3e 68 61 73 68 4b 65 79 typePtr->hashKey
22f0: 50 72 6f 63 29 20 7b 0a 09 68 61 73 68 20 3d 20 Proc) {..hash =
2300: 74 79 70 65 50 74 72 2d 3e 68 61 73 68 4b 65 79 typePtr->hashKey
2310: 50 72 6f 63 28 74 61 62 6c 65 50 74 72 2c 20 28 Proc(tablePtr, (
2320: 76 6f 69 64 20 2a 29 20 6b 65 79 29 3b 0a 09 69 void *) key);..i
2330: 66 20 28 74 79 70 65 50 74 72 2d 3e 66 6c 61 67 f (typePtr->flag
2340: 73 20 26 20 54 43 4c 5f 48 41 53 48 5f 4b 45 59 s & TCL_HASH_KEY
2350: 5f 52 41 4e 44 4f 4d 49 5a 45 5f 48 41 53 48 29 _RANDOMIZE_HASH)
2360: 20 7b 0a 09 20 20 20 20 69 6e 64 65 78 20 3d 20 {.. index =
2370: 52 41 4e 44 4f 4d 5f 49 4e 44 45 58 28 74 61 62 RANDOM_INDEX(tab
2380: 6c 65 50 74 72 2c 20 68 61 73 68 29 3b 0a 09 7d lePtr, hash);..}
2390: 20 65 6c 73 65 20 7b 0a 09 20 20 20 20 69 6e 64 else {.. ind
23a0: 65 78 20 3d 20 68 61 73 68 20 26 20 74 61 62 6c ex = hash & tabl
23b0: 65 50 74 72 2d 3e 6d 61 73 6b 3b 0a 09 7d 0a 20 ePtr->mask;..}.
23c0: 20 20 20 7d 20 65 6c 73 65 20 7b 0a 09 68 61 73 } else {..has
23d0: 68 20 3d 20 50 54 52 32 55 49 4e 54 28 6b 65 79 h = PTR2UINT(key
23e0: 29 3b 0a 09 69 6e 64 65 78 20 3d 20 52 41 4e 44 );..index = RAND
23f0: 4f 4d 5f 49 4e 44 45 58 28 74 61 62 6c 65 50 74 OM_INDEX(tablePt
2400: 72 2c 20 68 61 73 68 29 3b 0a 20 20 20 20 7d 0a r, hash);. }.
2410: 0a 20 20 20 20 2f 2a 0a 20 20 20 20 20 2a 20 53 . /*. * S
2420: 65 61 72 63 68 20 61 6c 6c 20 6f 66 20 74 68 65 earch all of the
2430: 20 65 6e 74 72 69 65 73 20 69 6e 20 74 68 65 20 entries in the
2440: 61 70 70 72 6f 70 72 69 61 74 65 20 62 75 63 6b appropriate buck
2450: 65 74 2e 0a 20 20 20 20 20 2a 2f 0a 0a 20 20 20 et.. */..
2460: 20 69 66 20 28 74 79 70 65 50 74 72 2d 3e 63 6f if (typePtr->co
2470: 6d 70 61 72 65 4b 65 79 73 50 72 6f 63 29 20 7b mpareKeysProc) {
2480: 0a 09 54 63 6c 5f 43 6f 6d 70 61 72 65 48 61 73 ..Tcl_CompareHas
2490: 68 4b 65 79 73 50 72 6f 63 20 2a 63 6f 6d 70 61 hKeysProc *compa
24a0: 72 65 4b 65 79 73 50 72 6f 63 20 3d 20 74 79 70 reKeysProc = typ
24b0: 65 50 74 72 2d 3e 63 6f 6d 70 61 72 65 4b 65 79 ePtr->compareKey
24c0: 73 50 72 6f 63 3b 0a 09 69 66 20 28 74 79 70 65 sProc;..if (type
24d0: 50 74 72 2d 3e 66 6c 61 67 73 20 26 20 54 43 4c Ptr->flags & TCL
24e0: 5f 48 41 53 48 5f 4b 45 59 5f 44 49 52 45 43 54 _HASH_KEY_DIRECT
24f0: 5f 43 4f 4d 50 41 52 45 29 20 7b 0a 09 20 20 20 _COMPARE) {..
2500: 20 66 6f 72 20 28 68 50 74 72 20 3d 20 74 61 62 for (hPtr = tab
2510: 6c 65 50 74 72 2d 3e 62 75 63 6b 65 74 73 5b 69 lePtr->buckets[i
2520: 6e 64 65 78 5d 3b 20 68 50 74 72 20 21 3d 20 4e ndex]; hPtr != N
2530: 55 4c 4c 3b 0a 09 09 20 20 20 20 68 50 74 72 20 ULL;... hPtr
2540: 3d 20 68 50 74 72 2d 3e 6e 65 78 74 50 74 72 29 = hPtr->nextPtr)
2550: 20 7b 0a 09 09 69 66 20 28 68 61 73 68 20 21 3d {...if (hash !=
2560: 20 68 50 74 72 2d 3e 68 61 73 68 29 20 7b 0a 09 hPtr->hash) {..
2570: 09 20 20 20 20 63 6f 6e 74 69 6e 75 65 3b 0a 09 . continue;..
2580: 09 7d 0a 09 09 2f 2a 20 69 66 20 6b 65 79 73 20 .}.../* if keys
2590: 70 6f 69 6e 74 65 72 73 20 6f 72 20 76 61 6c 75 pointers or valu
25a0: 65 73 20 61 72 65 20 65 71 75 61 6c 20 2a 2f 0a es are equal */.
25b0: 09 09 69 66 20 28 28 6b 65 79 20 3d 3d 20 68 50 ..if ((key == hP
25c0: 74 72 2d 3e 6b 65 79 2e 6f 6e 65 57 6f 72 64 56 tr->key.oneWordV
25d0: 61 6c 75 65 29 0a 09 09 09 7c 7c 20 63 6f 6d 70 alue)....|| comp
25e0: 61 72 65 4b 65 79 73 50 72 6f 63 28 28 76 6f 69 areKeysProc((voi
25f0: 64 20 2a 29 20 6b 65 79 2c 20 68 50 74 72 29 29 d *) key, hPtr))
2600: 20 7b 0a 09 09 20 20 20 20 69 66 20 28 6e 65 77 {... if (new
2610: 50 74 72 20 26 26 20 28 6e 65 77 50 74 72 20 21 Ptr && (newPtr !
2620: 3d 20 54 43 4c 5f 48 41 53 48 5f 46 49 4e 44 29 = TCL_HASH_FIND)
2630: 29 20 7b 0a 09 09 09 2a 6e 65 77 50 74 72 20 3d ) {....*newPtr =
2640: 20 30 3b 0a 09 09 20 20 20 20 7d 0a 09 09 20 20 0;... }...
2650: 20 20 72 65 74 75 72 6e 20 68 50 74 72 3b 0a 09 return hPtr;..
2660: 09 7d 0a 09 20 20 20 20 7d 0a 09 7d 20 65 6c 73 .}.. }..} els
2670: 65 20 7b 20 2f 2a 20 6e 6f 20 64 69 72 65 63 74 e { /* no direct
2680: 20 63 6f 6d 70 61 72 65 20 2d 20 63 6f 6d 70 61 compare - compa
2690: 72 65 20 6b 65 79 20 61 64 64 72 65 73 73 65 73 re key addresses
26a0: 20 6f 6e 6c 79 20 2a 2f 0a 09 20 20 20 20 66 6f only */.. fo
26b0: 72 20 28 68 50 74 72 20 3d 20 74 61 62 6c 65 50 r (hPtr = tableP
26c0: 74 72 2d 3e 62 75 63 6b 65 74 73 5b 69 6e 64 65 tr->buckets[inde
26d0: 78 5d 3b 20 68 50 74 72 20 21 3d 20 4e 55 4c 4c x]; hPtr != NULL
26e0: 3b 0a 09 09 20 20 20 20 68 50 74 72 20 3d 20 68 ;... hPtr = h
26f0: 50 74 72 2d 3e 6e 65 78 74 50 74 72 29 20 7b 0a Ptr->nextPtr) {.
2700: 09 09 69 66 20 28 68 61 73 68 20 21 3d 20 68 50 ..if (hash != hP
2710: 74 72 2d 3e 68 61 73 68 29 20 7b 0a 09 09 20 20 tr->hash) {...
2720: 20 20 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 7d 0a continue;...}.
2730: 09 09 2f 2a 20 69 66 20 6e 65 65 64 6c 65 20 70 ../* if needle p
2740: 6f 69 6e 74 65 72 20 65 71 75 61 6c 73 20 63 6f ointer equals co
2750: 6e 74 65 6e 74 20 70 6f 69 6e 74 65 72 20 6f 72 ntent pointer or
2760: 20 76 61 6c 75 65 73 20 65 71 75 61 6c 20 2a 2f values equal */
2770: 0a 09 09 69 66 20 28 28 6b 65 79 20 3d 3d 20 68 ...if ((key == h
2780: 50 74 72 2d 3e 6b 65 79 2e 73 74 72 69 6e 67 29 Ptr->key.string)
2790: 0a 09 09 09 7c 7c 20 63 6f 6d 70 61 72 65 4b 65 ....|| compareKe
27a0: 79 73 50 72 6f 63 28 28 76 6f 69 64 20 2a 29 20 ysProc((void *)
27b0: 6b 65 79 2c 20 68 50 74 72 29 29 20 7b 0a 09 09 key, hPtr)) {...
27c0: 20 20 20 20 69 66 20 28 6e 65 77 50 74 72 20 26 if (newPtr &
27d0: 26 20 28 6e 65 77 50 74 72 20 21 3d 20 54 43 4c & (newPtr != TCL
27e0: 5f 48 41 53 48 5f 46 49 4e 44 29 29 20 7b 0a 09 _HASH_FIND)) {..
27f0: 09 09 2a 6e 65 77 50 74 72 20 3d 20 30 3b 0a 09 ..*newPtr = 0;..
2800: 09 20 20 20 20 7d 0a 09 09 20 20 20 20 72 65 74 . }... ret
2810: 75 72 6e 20 68 50 74 72 3b 0a 09 09 7d 0a 09 20 urn hPtr;...}..
2820: 20 20 20 7d 0a 09 7d 0a 20 20 20 20 7d 20 65 6c }..}. } el
2830: 73 65 20 7b 0a 09 66 6f 72 20 28 68 50 74 72 20 se {..for (hPtr
2840: 3d 20 74 61 62 6c 65 50 74 72 2d 3e 62 75 63 6b = tablePtr->buck
2850: 65 74 73 5b 69 6e 64 65 78 5d 3b 20 68 50 74 72 ets[index]; hPtr
2860: 20 21 3d 20 4e 55 4c 4c 3b 0a 09 09 68 50 74 72 != NULL;...hPtr
2870: 20 3d 20 68 50 74 72 2d 3e 6e 65 78 74 50 74 72 = hPtr->nextPtr
2880: 29 20 7b 0a 09 20 20 20 20 69 66 20 28 68 61 73 ) {.. if (has
2890: 68 20 21 3d 20 68 50 74 72 2d 3e 68 61 73 68 29 h != hPtr->hash)
28a0: 20 7b 0a 09 09 63 6f 6e 74 69 6e 75 65 3b 0a 09 {...continue;..
28b0: 20 20 20 20 7d 0a 09 20 20 20 20 69 66 20 28 6b }.. if (k
28c0: 65 79 20 3d 3d 20 68 50 74 72 2d 3e 6b 65 79 2e ey == hPtr->key.
28d0: 6f 6e 65 57 6f 72 64 56 61 6c 75 65 29 20 7b 0a oneWordValue) {.
28e0: 09 09 69 66 20 28 6e 65 77 50 74 72 20 26 26 20 ..if (newPtr &&
28f0: 28 6e 65 77 50 74 72 20 21 3d 20 54 43 4c 5f 48 (newPtr != TCL_H
2900: 41 53 48 5f 46 49 4e 44 29 29 20 7b 0a 09 09 20 ASH_FIND)) {...
2910: 20 20 20 2a 6e 65 77 50 74 72 20 3d 20 30 3b 0a *newPtr = 0;.
2920: 09 09 7d 0a 09 09 72 65 74 75 72 6e 20 68 50 74 ..}...return hPt
2930: 72 3b 0a 09 20 20 20 20 7d 0a 09 7d 0a 20 20 20 r;.. }..}.
2940: 20 7d 0a 0a 20 20 20 20 69 66 20 28 6e 65 77 50 }.. if (newP
2950: 74 72 20 3d 3d 20 54 43 4c 5f 48 41 53 48 5f 46 tr == TCL_HASH_F
2960: 49 4e 44 29 20 7b 0a 09 2f 2a 20 54 68 69 73 20 IND) {../* This
2970: 69 73 20 74 68 65 20 66 69 6e 64 50 72 6f 63 20 is the findProc
2980: 66 75 6e 63 74 69 6f 6e 61 6c 69 74 79 2c 20 73 functionality, s
2990: 6f 20 77 65 20 61 72 65 20 64 6f 6e 65 2e 20 2a o we are done. *
29a0: 2f 0a 09 72 65 74 75 72 6e 20 4e 55 4c 4c 3b 0a /..return NULL;.
29b0: 20 20 20 20 7d 0a 0a 20 20 20 20 2f 2a 0a 20 20 }.. /*.
29c0: 20 20 20 2a 20 45 6e 74 72 79 20 6e 6f 74 20 66 * Entry not f
29d0: 6f 75 6e 64 2e 20 41 64 64 20 61 20 6e 65 77 20 ound. Add a new
29e0: 6f 6e 65 20 74 6f 20 74 68 65 20 62 75 63 6b 65 one to the bucke
29f0: 74 2e 0a 20 20 20 20 20 2a 2f 0a 0a 20 20 20 20 t.. */..
2a00: 69 66 20 28 6e 65 77 50 74 72 29 20 7b 0a 09 2a if (newPtr) {..*
2a10: 6e 65 77 50 74 72 20 3d 20 31 3b 0a 20 20 20 20 newPtr = 1;.
2a20: 7d 0a 20 20 20 20 69 66 20 28 74 79 70 65 50 74 }. if (typePt
2a30: 72 2d 3e 61 6c 6c 6f 63 45 6e 74 72 79 50 72 6f r->allocEntryPro
2a40: 63 29 20 7b 0a 09 68 50 74 72 20 3d 20 74 79 70 c) {..hPtr = typ
2a50: 65 50 74 72 2d 3e 61 6c 6c 6f 63 45 6e 74 72 79 ePtr->allocEntry
2a60: 50 72 6f 63 28 74 61 62 6c 65 50 74 72 2c 20 28 Proc(tablePtr, (
2a70: 76 6f 69 64 20 2a 29 20 6b 65 79 29 3b 0a 20 20 void *) key);.
2a80: 20 20 7d 20 65 6c 73 65 20 7b 0a 09 68 50 74 72 } else {..hPtr
2a90: 20 3d 20 28 54 63 6c 5f 48 61 73 68 45 6e 74 72 = (Tcl_HashEntr
2aa0: 79 20 2a 29 54 63 6c 5f 41 74 74 65 6d 70 74 41 y *)Tcl_AttemptA
2ab0: 6c 6c 6f 63 28 73 69 7a 65 6f 66 28 54 63 6c 5f lloc(sizeof(Tcl_
2ac0: 48 61 73 68 45 6e 74 72 79 29 29 3b 0a 09 69 66 HashEntry));..if
2ad0: 20 28 21 68 50 74 72 29 20 7b 0a 09 20 20 20 20 (!hPtr) {..
2ae0: 72 65 74 75 72 6e 20 4e 55 4c 4c 3b 0a 09 7d 0a return NULL;..}.
2af0: 09 68 50 74 72 2d 3e 6b 65 79 2e 6f 6e 65 57 6f .hPtr->key.oneWo
2b00: 72 64 56 61 6c 75 65 20 3d 20 28 63 68 61 72 20 rdValue = (char
2b10: 2a 29 20 6b 65 79 3b 0a 09 54 63 6c 5f 53 65 74 *) key;..Tcl_Set
2b20: 48 61 73 68 56 61 6c 75 65 28 68 50 74 72 2c 20 HashValue(hPtr,
2b30: 4e 55 4c 4c 29 3b 0a 20 20 20 20 7d 0a 0a 20 20 NULL);. }..
2b40: 20 20 68 50 74 72 2d 3e 74 61 62 6c 65 50 74 72 hPtr->tablePtr
2b50: 20 3d 20 74 61 62 6c 65 50 74 72 3b 0a 20 20 20 = tablePtr;.
2b60: 20 68 50 74 72 2d 3e 68 61 73 68 20 3d 20 68 61 hPtr->hash = ha
2b70: 73 68 3b 0a 20 20 20 20 68 50 74 72 2d 3e 6e 65 sh;. hPtr->ne
2b80: 78 74 50 74 72 20 3d 20 74 61 62 6c 65 50 74 72 xtPtr = tablePtr
2b90: 2d 3e 62 75 63 6b 65 74 73 5b 69 6e 64 65 78 5d ->buckets[index]
2ba0: 3b 0a 20 20 20 20 74 61 62 6c 65 50 74 72 2d 3e ;. tablePtr->
2bb0: 62 75 63 6b 65 74 73 5b 69 6e 64 65 78 5d 20 3d buckets[index] =
2bc0: 20 68 50 74 72 3b 0a 20 20 20 20 74 61 62 6c 65 hPtr;. table
2bd0: 50 74 72 2d 3e 6e 75 6d 45 6e 74 72 69 65 73 2b Ptr->numEntries+
2be0: 2b 3b 0a 0a 20 20 20 20 2f 2a 0a 20 20 20 20 20 +;.. /*.
2bf0: 2a 20 49 66 20 74 68 65 20 74 61 62 6c 65 20 68 * If the table h
2c00: 61 73 20 65 78 63 65 65 64 65 64 20 61 20 64 65 as exceeded a de
2c10: 63 65 6e 74 20 73 69 7a 65 2c 20 72 65 62 75 69 cent size, rebui
2c20: 6c 64 20 69 74 20 77 69 74 68 20 6d 61 6e 79 20 ld it with many
2c30: 6d 6f 72 65 0a 20 20 20 20 20 2a 20 62 75 63 6b more. * buck
2c40: 65 74 73 2e 0a 20 20 20 20 20 2a 2f 0a 0a 20 20 ets.. */..
2c50: 20 20 69 66 20 28 74 61 62 6c 65 50 74 72 2d 3e if (tablePtr->
2c60: 6e 75 6d 45 6e 74 72 69 65 73 20 3e 3d 20 74 61 numEntries >= ta
2c70: 62 6c 65 50 74 72 2d 3e 72 65 62 75 69 6c 64 53 blePtr->rebuildS
2c80: 69 7a 65 29 20 7b 0a 09 52 65 62 75 69 6c 64 54 ize) {..RebuildT
2c90: 61 62 6c 65 28 74 61 62 6c 65 50 74 72 29 3b 0a able(tablePtr);.
2ca0: 20 20 20 20 7d 0a 20 20 20 20 72 65 74 75 72 6e }. return
2cb0: 20 68 50 74 72 3b 0a 7d 0a 0c 0a 2f 2a 0a 20 2a hPtr;.}.../*. *
2cc0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2cd0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2ce0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2cf0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2d00: 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 54 63 6c ------. *. * Tcl
2d10: 5f 44 65 6c 65 74 65 48 61 73 68 45 6e 74 72 79 _DeleteHashEntry
2d20: 20 2d 2d 0a 20 2a 0a 20 2a 09 52 65 6d 6f 76 65 --. *. *.Remove
2d30: 20 61 20 73 69 6e 67 6c 65 20 65 6e 74 72 79 20 a single entry
2d40: 66 72 6f 6d 20 61 20 68 61 73 68 20 74 61 62 6c from a hash tabl
2d50: 65 2e 0a 20 2a 0a 20 2a 20 52 65 73 75 6c 74 73 e.. *. * Results
2d60: 3a 0a 20 2a 09 4e 6f 6e 65 2e 0a 20 2a 0a 20 2a :. *.None.. *. *
2d70: 20 53 69 64 65 20 65 66 66 65 63 74 73 3a 0a 20 Side effects:.
2d80: 2a 09 54 68 65 20 65 6e 74 72 79 20 67 69 76 65 *.The entry give
2d90: 6e 20 62 79 20 65 6e 74 72 79 50 74 72 20 69 73 n by entryPtr is
2da0: 20 64 65 6c 65 74 65 64 20 66 72 6f 6d 20 69 74 deleted from it
2db0: 73 20 74 61 62 6c 65 20 61 6e 64 20 73 68 6f 75 s table and shou
2dc0: 6c 64 20 6e 65 76 65 72 0a 20 2a 09 61 67 61 69 ld never. *.agai
2dd0: 6e 20 62 65 20 75 73 65 64 20 62 79 20 74 68 65 n be used by the
2de0: 20 63 61 6c 6c 65 72 2e 20 49 74 20 69 73 20 75 caller. It is u
2df0: 70 20 74 6f 20 74 68 65 20 63 61 6c 6c 65 72 20 p to the caller
2e00: 74 6f 20 66 72 65 65 20 74 68 65 0a 20 2a 09 63 to free the. *.c
2e10: 6c 69 65 6e 74 44 61 74 61 20 66 69 65 6c 64 20 lientData field
2e20: 6f 66 20 74 68 65 20 65 6e 74 72 79 2c 20 69 66 of the entry, if
2e30: 20 74 68 61 74 20 69 73 20 72 65 6c 65 76 61 6e that is relevan
2e40: 74 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d t.. *. *--------
2e50: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2e60: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2e70: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2e80: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 --------------.
2e90: 2a 2f 0a 0a 76 6f 69 64 0a 54 63 6c 5f 44 65 6c */..void.Tcl_Del
2ea0: 65 74 65 48 61 73 68 45 6e 74 72 79 28 0a 20 20 eteHashEntry(.
2eb0: 20 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 Tcl_HashEntry
2ec0: 2a 65 6e 74 72 79 50 74 72 29 0a 7b 0a 20 20 20 *entryPtr).{.
2ed0: 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 2a Tcl_HashEntry *
2ee0: 70 72 65 76 50 74 72 3b 0a 20 20 20 20 63 6f 6e prevPtr;. con
2ef0: 73 74 20 54 63 6c 5f 48 61 73 68 4b 65 79 54 79 st Tcl_HashKeyTy
2f00: 70 65 20 2a 74 79 70 65 50 74 72 3b 0a 20 20 20 pe *typePtr;.
2f10: 20 54 63 6c 5f 48 61 73 68 54 61 62 6c 65 20 2a Tcl_HashTable *
2f20: 74 61 62 6c 65 50 74 72 3b 0a 20 20 20 20 54 63 tablePtr;. Tc
2f30: 6c 5f 48 61 73 68 45 6e 74 72 79 20 2a 2a 62 75 l_HashEntry **bu
2f40: 63 6b 65 74 50 74 72 3b 0a 20 20 20 20 73 69 7a cketPtr;. siz
2f50: 65 5f 74 20 69 6e 64 65 78 3b 0a 0a 20 20 20 20 e_t index;..
2f60: 74 61 62 6c 65 50 74 72 20 3d 20 65 6e 74 72 79 tablePtr = entry
2f70: 50 74 72 2d 3e 74 61 62 6c 65 50 74 72 3b 0a 0a Ptr->tablePtr;..
2f80: 20 20 20 20 69 66 20 28 74 61 62 6c 65 50 74 72 if (tablePtr
2f90: 2d 3e 6b 65 79 54 79 70 65 20 3d 3d 20 54 43 4c ->keyType == TCL
2fa0: 5f 53 54 52 49 4e 47 5f 4b 45 59 53 29 20 7b 0a _STRING_KEYS) {.
2fb0: 09 74 79 70 65 50 74 72 20 3d 20 26 74 63 6c 53 .typePtr = &tclS
2fc0: 74 72 69 6e 67 48 61 73 68 4b 65 79 54 79 70 65 tringHashKeyType
2fd0: 3b 0a 20 20 20 20 7d 20 65 6c 73 65 20 69 66 20 ;. } else if
2fe0: 28 74 61 62 6c 65 50 74 72 2d 3e 6b 65 79 54 79 (tablePtr->keyTy
2ff0: 70 65 20 3d 3d 20 54 43 4c 5f 4f 4e 45 5f 57 4f pe == TCL_ONE_WO
3000: 52 44 5f 4b 45 59 53 29 20 7b 0a 09 74 79 70 65 RD_KEYS) {..type
3010: 50 74 72 20 3d 20 26 74 63 6c 4f 6e 65 57 6f 72 Ptr = &tclOneWor
3020: 64 48 61 73 68 4b 65 79 54 79 70 65 3b 0a 20 20 dHashKeyType;.
3030: 20 20 7d 20 65 6c 73 65 20 69 66 20 28 74 61 62 } else if (tab
3040: 6c 65 50 74 72 2d 3e 6b 65 79 54 79 70 65 20 3d lePtr->keyType =
3050: 3d 20 54 43 4c 5f 43 55 53 54 4f 4d 5f 54 59 50 = TCL_CUSTOM_TYP
3060: 45 5f 4b 45 59 53 0a 09 20 20 20 20 7c 7c 20 74 E_KEYS.. || t
3070: 61 62 6c 65 50 74 72 2d 3e 6b 65 79 54 79 70 65 ablePtr->keyType
3080: 20 3d 3d 20 54 43 4c 5f 43 55 53 54 4f 4d 5f 50 == TCL_CUSTOM_P
3090: 54 52 5f 4b 45 59 53 29 20 7b 0a 09 74 79 70 65 TR_KEYS) {..type
30a0: 50 74 72 20 3d 20 74 61 62 6c 65 50 74 72 2d 3e Ptr = tablePtr->
30b0: 74 79 70 65 50 74 72 3b 0a 20 20 20 20 7d 20 65 typePtr;. } e
30c0: 6c 73 65 20 7b 0a 09 74 79 70 65 50 74 72 20 3d lse {..typePtr =
30d0: 20 26 74 63 6c 41 72 72 61 79 48 61 73 68 4b 65 &tclArrayHashKe
30e0: 79 54 79 70 65 3b 0a 20 20 20 20 7d 0a 0a 20 20 yType;. }..
30f0: 20 20 69 66 20 28 74 79 70 65 50 74 72 2d 3e 68 if (typePtr->h
3100: 61 73 68 4b 65 79 50 72 6f 63 20 3d 3d 20 4e 55 ashKeyProc == NU
3110: 4c 4c 0a 09 20 20 20 20 7c 7c 20 74 79 70 65 50 LL.. || typeP
3120: 74 72 2d 3e 66 6c 61 67 73 20 26 20 54 43 4c 5f tr->flags & TCL_
3130: 48 41 53 48 5f 4b 45 59 5f 52 41 4e 44 4f 4d 49 HASH_KEY_RANDOMI
3140: 5a 45 5f 48 41 53 48 29 20 7b 0a 09 69 6e 64 65 ZE_HASH) {..inde
3150: 78 20 3d 20 52 41 4e 44 4f 4d 5f 49 4e 44 45 58 x = RANDOM_INDEX
3160: 28 74 61 62 6c 65 50 74 72 2c 20 65 6e 74 72 79 (tablePtr, entry
3170: 50 74 72 2d 3e 68 61 73 68 29 3b 0a 20 20 20 20 Ptr->hash);.
3180: 7d 20 65 6c 73 65 20 7b 0a 09 69 6e 64 65 78 20 } else {..index
3190: 3d 20 65 6e 74 72 79 50 74 72 2d 3e 68 61 73 68 = entryPtr->hash
31a0: 20 26 20 74 61 62 6c 65 50 74 72 2d 3e 6d 61 73 & tablePtr->mas
31b0: 6b 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20 62 75 k;. }.. bu
31c0: 63 6b 65 74 50 74 72 20 3d 20 26 74 61 62 6c 65 cketPtr = &table
31d0: 50 74 72 2d 3e 62 75 63 6b 65 74 73 5b 69 6e 64 Ptr->buckets[ind
31e0: 65 78 5d 3b 0a 0a 20 20 20 20 69 66 20 28 2a 62 ex];.. if (*b
31f0: 75 63 6b 65 74 50 74 72 20 3d 3d 20 65 6e 74 72 ucketPtr == entr
3200: 79 50 74 72 29 20 7b 0a 09 2a 62 75 63 6b 65 74 yPtr) {..*bucket
3210: 50 74 72 20 3d 20 65 6e 74 72 79 50 74 72 2d 3e Ptr = entryPtr->
3220: 6e 65 78 74 50 74 72 3b 0a 20 20 20 20 7d 20 65 nextPtr;. } e
3230: 6c 73 65 20 7b 0a 09 66 6f 72 20 28 70 72 65 76 lse {..for (prev
3240: 50 74 72 20 3d 20 2a 62 75 63 6b 65 74 50 74 72 Ptr = *bucketPtr
3250: 3b 20 3b 20 70 72 65 76 50 74 72 20 3d 20 70 72 ; ; prevPtr = pr
3260: 65 76 50 74 72 2d 3e 6e 65 78 74 50 74 72 29 20 evPtr->nextPtr)
3270: 7b 0a 09 20 20 20 20 69 66 20 28 70 72 65 76 50 {.. if (prevP
3280: 74 72 20 3d 3d 20 4e 55 4c 4c 29 20 7b 0a 09 09 tr == NULL) {...
3290: 54 63 6c 5f 50 61 6e 69 63 28 22 6d 61 6c 66 6f Tcl_Panic("malfo
32a0: 72 6d 65 64 20 62 75 63 6b 65 74 20 63 68 61 69 rmed bucket chai
32b0: 6e 20 69 6e 20 54 63 6c 5f 44 65 6c 65 74 65 48 n in Tcl_DeleteH
32c0: 61 73 68 45 6e 74 72 79 22 29 3b 0a 09 20 20 20 ashEntry");..
32d0: 20 7d 0a 09 20 20 20 20 69 66 20 28 70 72 65 76 }.. if (prev
32e0: 50 74 72 2d 3e 6e 65 78 74 50 74 72 20 3d 3d 20 Ptr->nextPtr ==
32f0: 65 6e 74 72 79 50 74 72 29 20 7b 0a 09 09 70 72 entryPtr) {...pr
3300: 65 76 50 74 72 2d 3e 6e 65 78 74 50 74 72 20 3d evPtr->nextPtr =
3310: 20 65 6e 74 72 79 50 74 72 2d 3e 6e 65 78 74 50 entryPtr->nextP
3320: 74 72 3b 0a 09 09 62 72 65 61 6b 3b 0a 09 20 20 tr;...break;..
3330: 20 20 7d 0a 09 7d 0a 20 20 20 20 7d 0a 0a 20 20 }..}. }..
3340: 20 20 74 61 62 6c 65 50 74 72 2d 3e 6e 75 6d 45 tablePtr->numE
3350: 6e 74 72 69 65 73 2d 2d 3b 0a 20 20 20 20 69 66 ntries--;. if
3360: 20 28 74 79 70 65 50 74 72 2d 3e 66 72 65 65 45 (typePtr->freeE
3370: 6e 74 72 79 50 72 6f 63 29 20 7b 0a 09 74 79 70 ntryProc) {..typ
3380: 65 50 74 72 2d 3e 66 72 65 65 45 6e 74 72 79 50 ePtr->freeEntryP
3390: 72 6f 63 28 65 6e 74 72 79 50 74 72 29 3b 0a 20 roc(entryPtr);.
33a0: 20 20 20 7d 20 65 6c 73 65 20 7b 0a 09 54 63 6c } else {..Tcl
33b0: 5f 46 72 65 65 28 65 6e 74 72 79 50 74 72 29 3b _Free(entryPtr);
33c0: 0a 20 20 20 20 7d 0a 7d 0a 0c 0a 2f 2a 0a 20 2a . }.}.../*. *
33d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
33e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
33f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3400: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3410: 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 54 63 6c ------. *. * Tcl
3420: 5f 44 65 6c 65 74 65 48 61 73 68 54 61 62 6c 65 _DeleteHashTable
3430: 20 2d 2d 0a 20 2a 0a 20 2a 09 46 72 65 65 20 75 --. *. *.Free u
3440: 70 20 65 76 65 72 79 74 68 69 6e 67 20 61 73 73 p everything ass
3450: 6f 63 69 61 74 65 64 20 77 69 74 68 20 61 20 68 ociated with a h
3460: 61 73 68 20 74 61 62 6c 65 20 65 78 63 65 70 74 ash table except
3470: 20 66 6f 72 20 74 68 65 20 72 65 63 6f 72 64 0a for the record.
3480: 20 2a 09 66 6f 72 20 74 68 65 20 74 61 62 6c 65 *.for the table
3490: 20 69 74 73 65 6c 66 2e 0a 20 2a 0a 20 2a 20 52 itself.. *. * R
34a0: 65 73 75 6c 74 73 3a 0a 20 2a 09 4e 6f 6e 65 2e esults:. *.None.
34b0: 0a 20 2a 0a 20 2a 20 53 69 64 65 20 65 66 66 65 . *. * Side effe
34c0: 63 74 73 3a 0a 20 2a 09 54 68 65 20 68 61 73 68 cts:. *.The hash
34d0: 20 74 61 62 6c 65 20 69 73 20 6e 6f 20 6c 6f 6e table is no lon
34e0: 67 65 72 20 75 73 65 61 62 6c 65 2e 0a 20 2a 0a ger useable.. *.
34f0: 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *--------------
3500: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3510: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3520: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3530: 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 2f 0a 0a 76 6f --------. */..vo
3540: 69 64 0a 54 63 6c 5f 44 65 6c 65 74 65 48 61 73 id.Tcl_DeleteHas
3550: 68 54 61 62 6c 65 28 0a 20 20 20 20 54 63 6c 5f hTable(. Tcl_
3560: 48 61 73 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 HashTable *table
3570: 50 74 72 29 09 2f 2a 20 54 61 62 6c 65 20 74 6f Ptr)./* Table to
3580: 20 64 65 6c 65 74 65 2e 20 2a 2f 0a 7b 0a 20 20 delete. */.{.
3590: 20 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 Tcl_HashEntry
35a0: 2a 68 50 74 72 2c 20 2a 6e 65 78 74 50 74 72 3b *hPtr, *nextPtr;
35b0: 0a 20 20 20 20 63 6f 6e 73 74 20 54 63 6c 5f 48 . const Tcl_H
35c0: 61 73 68 4b 65 79 54 79 70 65 20 2a 74 79 70 65 ashKeyType *type
35d0: 50 74 72 3b 0a 20 20 20 20 54 63 6c 5f 53 69 7a Ptr;. Tcl_Siz
35e0: 65 20 69 3b 0a 0a 20 20 20 20 69 66 20 28 74 61 e i;.. if (ta
35f0: 62 6c 65 50 74 72 2d 3e 6b 65 79 54 79 70 65 20 blePtr->keyType
3600: 3d 3d 20 54 43 4c 5f 53 54 52 49 4e 47 5f 4b 45 == TCL_STRING_KE
3610: 59 53 29 20 7b 0a 09 74 79 70 65 50 74 72 20 3d YS) {..typePtr =
3620: 20 26 74 63 6c 53 74 72 69 6e 67 48 61 73 68 4b &tclStringHashK
3630: 65 79 54 79 70 65 3b 0a 20 20 20 20 7d 20 65 6c eyType;. } el
3640: 73 65 20 69 66 20 28 74 61 62 6c 65 50 74 72 2d se if (tablePtr-
3650: 3e 6b 65 79 54 79 70 65 20 3d 3d 20 54 43 4c 5f >keyType == TCL_
3660: 4f 4e 45 5f 57 4f 52 44 5f 4b 45 59 53 29 20 7b ONE_WORD_KEYS) {
3670: 0a 09 74 79 70 65 50 74 72 20 3d 20 26 74 63 6c ..typePtr = &tcl
3680: 4f 6e 65 57 6f 72 64 48 61 73 68 4b 65 79 54 79 OneWordHashKeyTy
3690: 70 65 3b 0a 20 20 20 20 7d 20 65 6c 73 65 20 69 pe;. } else i
36a0: 66 20 28 74 61 62 6c 65 50 74 72 2d 3e 6b 65 79 f (tablePtr->key
36b0: 54 79 70 65 20 3d 3d 20 54 43 4c 5f 43 55 53 54 Type == TCL_CUST
36c0: 4f 4d 5f 54 59 50 45 5f 4b 45 59 53 0a 09 20 20 OM_TYPE_KEYS..
36d0: 20 20 7c 7c 20 74 61 62 6c 65 50 74 72 2d 3e 6b || tablePtr->k
36e0: 65 79 54 79 70 65 20 3d 3d 20 54 43 4c 5f 43 55 eyType == TCL_CU
36f0: 53 54 4f 4d 5f 50 54 52 5f 4b 45 59 53 29 20 7b STOM_PTR_KEYS) {
3700: 0a 09 74 79 70 65 50 74 72 20 3d 20 74 61 62 6c ..typePtr = tabl
3710: 65 50 74 72 2d 3e 74 79 70 65 50 74 72 3b 0a 20 ePtr->typePtr;.
3720: 20 20 20 7d 20 65 6c 73 65 20 7b 0a 09 74 79 70 } else {..typ
3730: 65 50 74 72 20 3d 20 26 74 63 6c 41 72 72 61 79 ePtr = &tclArray
3740: 48 61 73 68 4b 65 79 54 79 70 65 3b 0a 20 20 20 HashKeyType;.
3750: 20 7d 0a 0a 20 20 20 20 2f 2a 0a 20 20 20 20 20 }.. /*.
3760: 2a 20 46 72 65 65 20 75 70 20 61 6c 6c 20 74 68 * Free up all th
3770: 65 20 65 6e 74 72 69 65 73 20 69 6e 20 74 68 65 e entries in the
3780: 20 74 61 62 6c 65 2e 0a 20 20 20 20 20 2a 2f 0a table.. */.
3790: 0a 20 20 20 20 66 6f 72 20 28 69 20 3d 20 30 3b . for (i = 0;
37a0: 20 69 20 3c 20 74 61 62 6c 65 50 74 72 2d 3e 6e i < tablePtr->n
37b0: 75 6d 42 75 63 6b 65 74 73 3b 20 69 2b 2b 29 20 umBuckets; i++)
37c0: 7b 0a 09 68 50 74 72 20 3d 20 74 61 62 6c 65 50 {..hPtr = tableP
37d0: 74 72 2d 3e 62 75 63 6b 65 74 73 5b 69 5d 3b 0a tr->buckets[i];.
37e0: 09 77 68 69 6c 65 20 28 68 50 74 72 20 21 3d 20 .while (hPtr !=
37f0: 4e 55 4c 4c 29 20 7b 0a 09 20 20 20 20 6e 65 78 NULL) {.. nex
3800: 74 50 74 72 20 3d 20 68 50 74 72 2d 3e 6e 65 78 tPtr = hPtr->nex
3810: 74 50 74 72 3b 0a 09 20 20 20 20 69 66 20 28 74 tPtr;.. if (t
3820: 79 70 65 50 74 72 2d 3e 66 72 65 65 45 6e 74 72 ypePtr->freeEntr
3830: 79 50 72 6f 63 29 20 7b 0a 09 09 74 79 70 65 50 yProc) {...typeP
3840: 74 72 2d 3e 66 72 65 65 45 6e 74 72 79 50 72 6f tr->freeEntryPro
3850: 63 28 68 50 74 72 29 3b 0a 09 20 20 20 20 7d 20 c(hPtr);.. }
3860: 65 6c 73 65 20 7b 0a 09 09 54 63 6c 5f 46 72 65 else {...Tcl_Fre
3870: 65 28 68 50 74 72 29 3b 0a 09 20 20 20 20 7d 0a e(hPtr);.. }.
3880: 09 20 20 20 20 68 50 74 72 20 3d 20 6e 65 78 74 . hPtr = next
3890: 50 74 72 3b 0a 09 7d 0a 20 20 20 20 7d 0a 0a 20 Ptr;..}. }..
38a0: 20 20 20 2f 2a 0a 20 20 20 20 20 2a 20 46 72 65 /*. * Fre
38b0: 65 20 75 70 20 74 68 65 20 62 75 63 6b 65 74 20 e up the bucket
38c0: 61 72 72 61 79 2c 20 69 66 20 69 74 20 77 61 73 array, if it was
38d0: 20 64 79 6e 61 6d 69 63 61 6c 6c 79 20 61 6c 6c dynamically all
38e0: 6f 63 61 74 65 64 2e 0a 20 20 20 20 20 2a 2f 0a ocated.. */.
38f0: 0a 20 20 20 20 69 66 20 28 74 61 62 6c 65 50 74 . if (tablePt
3900: 72 2d 3e 62 75 63 6b 65 74 73 20 21 3d 20 74 61 r->buckets != ta
3910: 62 6c 65 50 74 72 2d 3e 73 74 61 74 69 63 42 75 blePtr->staticBu
3920: 63 6b 65 74 73 29 20 7b 0a 09 69 66 20 28 74 79 ckets) {..if (ty
3930: 70 65 50 74 72 2d 3e 66 6c 61 67 73 20 26 20 54 pePtr->flags & T
3940: 43 4c 5f 48 41 53 48 5f 4b 45 59 5f 53 59 53 54 CL_HASH_KEY_SYST
3950: 45 4d 5f 48 41 53 48 29 20 7b 0a 09 20 20 20 20 EM_HASH) {..
3960: 54 63 6c 70 53 79 73 46 72 65 65 28 28 63 68 61 TclpSysFree((cha
3970: 72 20 2a 29 20 74 61 62 6c 65 50 74 72 2d 3e 62 r *) tablePtr->b
3980: 75 63 6b 65 74 73 29 3b 0a 09 7d 20 65 6c 73 65 uckets);..} else
3990: 20 7b 0a 09 20 20 20 20 54 63 6c 5f 46 72 65 65 {.. Tcl_Free
39a0: 28 74 61 62 6c 65 50 74 72 2d 3e 62 75 63 6b 65 (tablePtr->bucke
39b0: 74 73 29 3b 0a 09 7d 0a 20 20 20 20 7d 0a 0a 20 ts);..}. }..
39c0: 20 20 20 2f 2a 0a 20 20 20 20 20 2a 20 41 72 72 /*. * Arr
39d0: 61 6e 67 65 20 66 6f 72 20 70 61 6e 69 63 73 20 ange for panics
39e0: 69 66 20 74 68 65 20 74 61 62 6c 65 20 69 73 20 if the table is
39f0: 75 73 65 64 20 61 67 61 69 6e 20 77 69 74 68 6f used again witho
3a00: 75 74 0a 20 20 20 20 20 2a 20 72 65 2d 69 6e 69 ut. * re-ini
3a10: 74 69 61 6c 69 7a 61 74 69 6f 6e 2e 0a 20 20 20 tialization..
3a20: 20 20 2a 2f 0a 0a 23 69 66 6e 64 65 66 20 54 43 */..#ifndef TC
3a30: 4c 5f 4e 4f 5f 44 45 50 52 45 43 41 54 45 44 0a L_NO_DEPRECATED.
3a40: 20 20 20 20 74 61 62 6c 65 50 74 72 2d 3e 66 69 tablePtr->fi
3a50: 6e 64 50 72 6f 63 20 3d 20 46 69 6e 64 48 61 73 ndProc = FindHas
3a60: 68 45 6e 74 72 79 3b 0a 23 65 6e 64 69 66 0a 20 hEntry;.#endif.
3a70: 20 20 20 74 61 62 6c 65 50 74 72 2d 3e 63 72 65 tablePtr->cre
3a80: 61 74 65 50 72 6f 63 20 3d 20 42 6f 67 75 73 43 ateProc = BogusC
3a90: 72 65 61 74 65 3b 0a 7d 0a 0c 0a 2f 2a 0a 20 2a reate;.}.../*. *
3aa0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3ab0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3ac0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3ad0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3ae0: 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 54 63 6c ------. *. * Tcl
3af0: 5f 46 69 72 73 74 48 61 73 68 45 6e 74 72 79 20 _FirstHashEntry
3b00: 2d 2d 0a 20 2a 0a 20 2a 09 4c 6f 63 61 74 65 20 --. *. *.Locate
3b10: 74 68 65 20 66 69 72 73 74 20 65 6e 74 72 79 20 the first entry
3b20: 69 6e 20 61 20 68 61 73 68 20 74 61 62 6c 65 20 in a hash table
3b30: 61 6e 64 20 73 65 74 20 75 70 20 61 20 72 65 63 and set up a rec
3b40: 6f 72 64 20 74 68 61 74 20 63 61 6e 20 62 65 0a ord that can be.
3b50: 20 2a 09 75 73 65 64 20 74 6f 20 73 74 65 70 20 *.used to step
3b60: 74 68 72 6f 75 67 68 20 61 6c 6c 20 74 68 65 20 through all the
3b70: 72 65 6d 61 69 6e 69 6e 67 20 65 6e 74 72 69 65 remaining entrie
3b80: 73 20 6f 66 20 74 68 65 20 74 61 62 6c 65 2e 0a s of the table..
3b90: 20 2a 0a 20 2a 20 52 65 73 75 6c 74 73 3a 0a 20 *. * Results:.
3ba0: 2a 09 54 68 65 20 72 65 74 75 72 6e 20 76 61 6c *.The return val
3bb0: 75 65 20 69 73 20 61 20 70 6f 69 6e 74 65 72 20 ue is a pointer
3bc0: 74 6f 20 74 68 65 20 66 69 72 73 74 20 65 6e 74 to the first ent
3bd0: 72 79 20 69 6e 20 74 61 62 6c 65 50 74 72 2c 20 ry in tablePtr,
3be0: 6f 72 20 4e 55 4c 4c 0a 20 2a 09 69 66 20 74 61 or NULL. *.if ta
3bf0: 62 6c 65 50 74 72 20 68 61 73 20 6e 6f 20 65 6e blePtr has no en
3c00: 74 72 69 65 73 20 69 6e 20 69 74 2e 20 54 68 65 tries in it. The
3c10: 20 6d 65 6d 6f 72 79 20 61 74 20 2a 73 65 61 72 memory at *sear
3c20: 63 68 50 74 72 20 69 73 0a 20 2a 09 69 6e 69 74 chPtr is. *.init
3c30: 69 61 6c 69 7a 65 64 20 73 6f 20 74 68 61 74 20 ialized so that
3c40: 73 75 62 73 65 71 75 65 6e 74 20 63 61 6c 6c 73 subsequent calls
3c50: 20 74 6f 20 54 63 6c 5f 4e 65 78 74 48 61 73 68 to Tcl_NextHash
3c60: 45 6e 74 72 79 20 77 69 6c 6c 20 72 65 74 75 72 Entry will retur
3c70: 6e 0a 20 2a 09 61 6c 6c 20 6f 66 20 74 68 65 20 n. *.all of the
3c80: 65 6e 74 72 69 65 73 20 69 6e 20 74 68 65 20 74 entries in the t
3c90: 61 62 6c 65 2c 20 6f 6e 65 20 61 74 20 61 20 74 able, one at a t
3ca0: 69 6d 65 2e 0a 20 2a 0a 20 2a 20 53 69 64 65 20 ime.. *. * Side
3cb0: 65 66 66 65 63 74 73 3a 0a 20 2a 09 4e 6f 6e 65 effects:. *.None
3cc0: 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d .. *. *---------
3cd0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3ce0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3cf0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3d00: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a -------------. *
3d10: 2f 0a 0a 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 /..Tcl_HashEntry
3d20: 20 2a 0a 54 63 6c 5f 46 69 72 73 74 48 61 73 68 *.Tcl_FirstHash
3d30: 45 6e 74 72 79 28 0a 20 20 20 20 54 63 6c 5f 48 Entry(. Tcl_H
3d40: 61 73 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 50 ashTable *tableP
3d50: 74 72 2c 09 2f 2a 20 54 61 62 6c 65 20 74 6f 20 tr,./* Table to
3d60: 73 65 61 72 63 68 2e 20 2a 2f 0a 20 20 20 20 54 search. */. T
3d70: 63 6c 5f 48 61 73 68 53 65 61 72 63 68 20 2a 73 cl_HashSearch *s
3d80: 65 61 72 63 68 50 74 72 29 09 2f 2a 20 50 6c 61 earchPtr)./* Pla
3d90: 63 65 20 74 6f 20 73 74 6f 72 65 20 69 6e 66 6f ce to store info
3da0: 72 6d 61 74 69 6f 6e 20 61 62 6f 75 74 20 70 72 rmation about pr
3db0: 6f 67 72 65 73 73 0a 09 09 09 09 20 2a 20 74 68 ogress..... * th
3dc0: 72 6f 75 67 68 20 74 68 65 20 74 61 62 6c 65 2e rough the table.
3dd0: 20 2a 2f 0a 7b 0a 20 20 20 20 73 65 61 72 63 68 */.{. search
3de0: 50 74 72 2d 3e 74 61 62 6c 65 50 74 72 20 3d 20 Ptr->tablePtr =
3df0: 74 61 62 6c 65 50 74 72 3b 0a 20 20 20 20 73 65 tablePtr;. se
3e00: 61 72 63 68 50 74 72 2d 3e 6e 65 78 74 49 6e 64 archPtr->nextInd
3e10: 65 78 20 3d 20 30 3b 0a 20 20 20 20 73 65 61 72 ex = 0;. sear
3e20: 63 68 50 74 72 2d 3e 6e 65 78 74 45 6e 74 72 79 chPtr->nextEntry
3e30: 50 74 72 20 3d 20 4e 55 4c 4c 3b 0a 20 20 20 20 Ptr = NULL;.
3e40: 72 65 74 75 72 6e 20 54 63 6c 5f 4e 65 78 74 48 return Tcl_NextH
3e50: 61 73 68 45 6e 74 72 79 28 73 65 61 72 63 68 50 ashEntry(searchP
3e60: 74 72 29 3b 0a 7d 0a 0c 0a 2f 2a 0a 20 2a 2d 2d tr);.}.../*. *--
3e70: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3e80: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3e90: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3ea0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3eb0: 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 54 63 6c 5f 4e ----. *. * Tcl_N
3ec0: 65 78 74 48 61 73 68 45 6e 74 72 79 20 2d 2d 0a extHashEntry --.
3ed0: 20 2a 0a 20 2a 09 4f 6e 63 65 20 61 20 68 61 73 *. *.Once a has
3ee0: 68 20 74 61 62 6c 65 20 65 6e 75 6d 65 72 61 74 h table enumerat
3ef0: 69 6f 6e 20 68 61 73 20 62 65 65 6e 20 69 6e 69 ion has been ini
3f00: 74 69 61 74 65 64 20 62 79 20 63 61 6c 6c 69 6e tiated by callin
3f10: 67 0a 20 2a 09 54 63 6c 5f 46 69 72 73 74 48 61 g. *.Tcl_FirstHa
3f20: 73 68 45 6e 74 72 79 2c 20 74 68 69 73 20 66 75 shEntry, this fu
3f30: 6e 63 74 69 6f 6e 20 6d 61 79 20 62 65 20 63 61 nction may be ca
3f40: 6c 6c 65 64 20 74 6f 20 72 65 74 75 72 6e 20 73 lled to return s
3f50: 75 63 63 65 73 73 69 76 65 0a 20 2a 09 65 6c 65 uccessive. *.ele
3f60: 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 74 61 62 ments of the tab
3f70: 6c 65 2e 0a 20 2a 0a 20 2a 20 52 65 73 75 6c 74 le.. *. * Result
3f80: 73 3a 0a 20 2a 09 54 68 65 20 72 65 74 75 72 6e s:. *.The return
3f90: 20 76 61 6c 75 65 20 69 73 20 74 68 65 20 6e 65 value is the ne
3fa0: 78 74 20 65 6e 74 72 79 20 69 6e 20 74 68 65 20 xt entry in the
3fb0: 68 61 73 68 20 74 61 62 6c 65 20 62 65 69 6e 67 hash table being
3fc0: 20 65 6e 75 6d 65 72 61 74 65 64 2c 0a 20 2a 09 enumerated,. *.
3fd0: 6f 72 20 4e 55 4c 4c 20 69 66 20 74 68 65 20 65 or NULL if the e
3fe0: 6e 64 20 6f 66 20 74 68 65 20 74 61 62 6c 65 20 nd of the table
3ff0: 69 73 20 72 65 61 63 68 65 64 2e 0a 20 2a 0a 20 is reached.. *.
4000: 2a 20 53 69 64 65 20 65 66 66 65 63 74 73 3a 0a * Side effects:.
4010: 20 2a 09 4e 6f 6e 65 2e 0a 20 2a 0a 20 2a 2d 2d *.None.. *. *--
4020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4040: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4050: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4060: 2d 2d 2d 2d 0a 20 2a 2f 0a 0a 54 63 6c 5f 48 61 ----. */..Tcl_Ha
4070: 73 68 45 6e 74 72 79 20 2a 0a 54 63 6c 5f 4e 65 shEntry *.Tcl_Ne
4080: 78 74 48 61 73 68 45 6e 74 72 79 28 0a 20 20 20 xtHashEntry(.
4090: 20 54 63 6c 5f 48 61 73 68 53 65 61 72 63 68 20 Tcl_HashSearch
40a0: 2a 73 65 61 72 63 68 50 74 72 29 09 2f 2a 20 50 *searchPtr)./* P
40b0: 6c 61 63 65 20 74 6f 20 73 74 6f 72 65 20 69 6e lace to store in
40c0: 66 6f 72 6d 61 74 69 6f 6e 20 61 62 6f 75 74 20 formation about
40d0: 70 72 6f 67 72 65 73 73 0a 09 09 09 09 20 2a 20 progress..... *
40e0: 74 68 72 6f 75 67 68 20 74 68 65 20 74 61 62 6c through the tabl
40f0: 65 2e 20 4d 75 73 74 20 68 61 76 65 20 62 65 65 e. Must have bee
4100: 6e 0a 09 09 09 09 20 2a 20 69 6e 69 74 69 61 6c n..... * initial
4110: 69 7a 65 64 20 62 79 20 63 61 6c 6c 69 6e 67 0a ized by calling.
4120: 09 09 09 09 20 2a 20 54 63 6c 5f 46 69 72 73 74 .... * Tcl_First
4130: 48 61 73 68 45 6e 74 72 79 2e 20 2a 2f 0a 7b 0a HashEntry. */.{.
4140: 20 20 20 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 Tcl_HashEntr
4150: 79 20 2a 68 50 74 72 3b 0a 20 20 20 20 54 63 6c y *hPtr;. Tcl
4160: 5f 48 61 73 68 54 61 62 6c 65 20 2a 74 61 62 6c _HashTable *tabl
4170: 65 50 74 72 20 3d 20 73 65 61 72 63 68 50 74 72 ePtr = searchPtr
4180: 2d 3e 74 61 62 6c 65 50 74 72 3b 0a 0a 20 20 20 ->tablePtr;..
4190: 20 77 68 69 6c 65 20 28 73 65 61 72 63 68 50 74 while (searchPt
41a0: 72 2d 3e 6e 65 78 74 45 6e 74 72 79 50 74 72 20 r->nextEntryPtr
41b0: 3d 3d 20 4e 55 4c 4c 29 20 7b 0a 09 69 66 20 28 == NULL) {..if (
41c0: 73 65 61 72 63 68 50 74 72 2d 3e 6e 65 78 74 49 searchPtr->nextI
41d0: 6e 64 65 78 20 3e 3d 20 74 61 62 6c 65 50 74 72 ndex >= tablePtr
41e0: 2d 3e 6e 75 6d 42 75 63 6b 65 74 73 29 20 7b 0a ->numBuckets) {.
41f0: 09 20 20 20 20 72 65 74 75 72 6e 20 4e 55 4c 4c . return NULL
4200: 3b 0a 09 7d 0a 09 73 65 61 72 63 68 50 74 72 2d ;..}..searchPtr-
4210: 3e 6e 65 78 74 45 6e 74 72 79 50 74 72 20 3d 0a >nextEntryPtr =.
4220: 09 09 74 61 62 6c 65 50 74 72 2d 3e 62 75 63 6b ..tablePtr->buck
4230: 65 74 73 5b 73 65 61 72 63 68 50 74 72 2d 3e 6e ets[searchPtr->n
4240: 65 78 74 49 6e 64 65 78 5d 3b 0a 09 73 65 61 72 extIndex];..sear
4250: 63 68 50 74 72 2d 3e 6e 65 78 74 49 6e 64 65 78 chPtr->nextIndex
4260: 2b 2b 3b 0a 20 20 20 20 7d 0a 20 20 20 20 68 50 ++;. }. hP
4270: 74 72 20 3d 20 73 65 61 72 63 68 50 74 72 2d 3e tr = searchPtr->
4280: 6e 65 78 74 45 6e 74 72 79 50 74 72 3b 0a 20 20 nextEntryPtr;.
4290: 20 20 73 65 61 72 63 68 50 74 72 2d 3e 6e 65 78 searchPtr->nex
42a0: 74 45 6e 74 72 79 50 74 72 20 3d 20 68 50 74 72 tEntryPtr = hPtr
42b0: 2d 3e 6e 65 78 74 50 74 72 3b 0a 20 20 20 20 72 ->nextPtr;. r
42c0: 65 74 75 72 6e 20 68 50 74 72 3b 0a 7d 0a 0c 0a eturn hPtr;.}...
42d0: 2f 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d /*. *-----------
42e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
42f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4300: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4310: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 -----------. *.
4320: 2a 20 54 63 6c 5f 48 61 73 68 53 74 61 74 73 20 * Tcl_HashStats
4330: 2d 2d 0a 20 2a 0a 20 2a 09 52 65 74 75 72 6e 20 --. *. *.Return
4340: 73 74 61 74 69 73 74 69 63 73 20 64 65 73 63 72 statistics descr
4350: 69 62 69 6e 67 20 74 68 65 20 6c 61 79 6f 75 74 ibing the layout
4360: 20 6f 66 20 74 68 65 20 68 61 73 68 20 74 61 62 of the hash tab
4370: 6c 65 20 69 6e 20 69 74 73 20 68 61 73 68 0a 20 le in its hash.
4380: 2a 09 62 75 63 6b 65 74 73 2e 0a 20 2a 0a 20 2a *.buckets.. *. *
4390: 20 52 65 73 75 6c 74 73 3a 0a 20 2a 09 54 68 65 Results:. *.The
43a0: 20 72 65 74 75 72 6e 20 76 61 6c 75 65 20 69 73 return value is
43b0: 20 61 20 6d 61 6c 6c 6f 63 2d 65 64 20 73 74 72 a malloc-ed str
43c0: 69 6e 67 20 63 6f 6e 74 61 69 6e 69 6e 67 20 69 ing containing i
43d0: 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 62 6f 75 74 nformation about
43e0: 0a 20 2a 09 74 61 62 6c 65 50 74 72 2e 20 49 74 . *.tablePtr. It
43f0: 20 69 73 20 74 68 65 20 63 61 6c 6c 65 72 27 73 is the caller's
4400: 20 72 65 73 70 6f 6e 73 69 62 69 6c 69 74 79 20 responsibility
4410: 74 6f 20 66 72 65 65 20 74 68 69 73 20 73 74 72 to free this str
4420: 69 6e 67 2e 0a 20 2a 0a 20 2a 20 53 69 64 65 20 ing.. *. * Side
4430: 65 66 66 65 63 74 73 3a 0a 20 2a 09 4e 6f 6e 65 effects:. *.None
4440: 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d .. *. *---------
4450: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4460: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4470: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4480: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a -------------. *
4490: 2f 0a 0a 63 68 61 72 20 2a 0a 54 63 6c 5f 48 61 /..char *.Tcl_Ha
44a0: 73 68 53 74 61 74 73 28 0a 20 20 20 20 54 63 6c shStats(. Tcl
44b0: 5f 48 61 73 68 54 61 62 6c 65 20 2a 74 61 62 6c _HashTable *tabl
44c0: 65 50 74 72 29 09 2f 2a 20 54 61 62 6c 65 20 66 ePtr)./* Table f
44d0: 6f 72 20 77 68 69 63 68 20 74 6f 20 70 72 6f 64 or which to prod
44e0: 75 63 65 20 73 74 61 74 73 2e 20 2a 2f 0a 7b 0a uce stats. */.{.
44f0: 23 64 65 66 69 6e 65 20 4e 55 4d 5f 43 4f 55 4e #define NUM_COUN
4500: 54 45 52 53 20 31 30 0a 20 20 20 20 54 63 6c 5f TERS 10. Tcl_
4510: 53 69 7a 65 20 69 3b 0a 20 20 20 20 73 69 7a 65 Size i;. size
4520: 5f 74 20 63 6f 75 6e 74 5b 4e 55 4d 5f 43 4f 55 _t count[NUM_COU
4530: 4e 54 45 52 53 5d 2c 20 6f 76 65 72 66 6c 6f 77 NTERS], overflow
4540: 2c 20 6a 3b 0a 20 20 20 20 64 6f 75 62 6c 65 20 , j;. double
4550: 61 76 65 72 61 67 65 2c 20 74 6d 70 3b 0a 20 20 average, tmp;.
4560: 20 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 Tcl_HashEntry
4570: 2a 68 50 74 72 3b 0a 20 20 20 20 63 68 61 72 20 *hPtr;. char
4580: 2a 72 65 73 75 6c 74 2c 20 2a 70 3b 0a 0a 20 20 *result, *p;..
4590: 20 20 2f 2a 0a 20 20 20 20 20 2a 20 43 6f 6d 70 /*. * Comp
45a0: 75 74 65 20 61 20 68 69 73 74 6f 67 72 61 6d 20 ute a histogram
45b0: 6f 66 20 62 75 63 6b 65 74 20 75 73 61 67 65 2e of bucket usage.
45c0: 0a 20 20 20 20 20 2a 2f 0a 0a 20 20 20 20 66 6f . */.. fo
45d0: 72 20 28 69 20 3d 20 30 3b 20 69 20 3c 20 4e 55 r (i = 0; i < NU
45e0: 4d 5f 43 4f 55 4e 54 45 52 53 3b 20 69 2b 2b 29 M_COUNTERS; i++)
45f0: 20 7b 0a 09 63 6f 75 6e 74 5b 69 5d 20 3d 20 30 {..count[i] = 0
4600: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 6f 76 65 72 ;. }. over
4610: 66 6c 6f 77 20 3d 20 30 3b 0a 20 20 20 20 61 76 flow = 0;. av
4620: 65 72 61 67 65 20 3d 20 30 2e 30 3b 0a 20 20 20 erage = 0.0;.
4630: 20 66 6f 72 20 28 69 20 3d 20 30 3b 20 69 20 3c for (i = 0; i <
4640: 20 74 61 62 6c 65 50 74 72 2d 3e 6e 75 6d 42 75 tablePtr->numBu
4650: 63 6b 65 74 73 3b 20 69 2b 2b 29 20 7b 0a 09 6a ckets; i++) {..j
4660: 20 3d 20 30 3b 0a 09 66 6f 72 20 28 68 50 74 72 = 0;..for (hPtr
4670: 20 3d 20 74 61 62 6c 65 50 74 72 2d 3e 62 75 63 = tablePtr->buc
4680: 6b 65 74 73 5b 69 5d 3b 20 68 50 74 72 20 21 3d kets[i]; hPtr !=
4690: 20 4e 55 4c 4c 3b 20 68 50 74 72 20 3d 20 68 50 NULL; hPtr = hP
46a0: 74 72 2d 3e 6e 65 78 74 50 74 72 29 20 7b 0a 09 tr->nextPtr) {..
46b0: 20 20 20 20 6a 2b 2b 3b 0a 09 7d 0a 09 69 66 20 j++;..}..if
46c0: 28 6a 20 3c 20 4e 55 4d 5f 43 4f 55 4e 54 45 52 (j < NUM_COUNTER
46d0: 53 29 20 7b 0a 09 20 20 20 20 63 6f 75 6e 74 5b S) {.. count[
46e0: 6a 5d 2b 2b 3b 0a 09 7d 20 65 6c 73 65 20 7b 0a j]++;..} else {.
46f0: 09 20 20 20 20 6f 76 65 72 66 6c 6f 77 2b 2b 3b . overflow++;
4700: 0a 09 7d 0a 09 74 6d 70 20 3d 20 28 64 6f 75 62 ..}..tmp = (doub
4710: 6c 65 29 6a 3b 0a 09 69 66 20 28 74 61 62 6c 65 le)j;..if (table
4720: 50 74 72 2d 3e 6e 75 6d 45 6e 74 72 69 65 73 20 Ptr->numEntries
4730: 21 3d 20 30 29 20 7b 0a 09 20 20 20 20 61 76 65 != 0) {.. ave
4740: 72 61 67 65 20 2b 3d 20 28 74 6d 70 2b 31 2e 30 rage += (tmp+1.0
4750: 29 2a 28 74 6d 70 2f 28 64 6f 75 62 6c 65 29 74 )*(tmp/(double)t
4760: 61 62 6c 65 50 74 72 2d 3e 6e 75 6d 45 6e 74 72 ablePtr->numEntr
4770: 69 65 73 29 2f 32 2e 30 3b 0a 09 7d 0a 20 20 20 ies)/2.0;..}.
4780: 20 7d 0a 0a 20 20 20 20 2f 2a 0a 20 20 20 20 20 }.. /*.
4790: 2a 20 50 72 69 6e 74 20 6f 75 74 20 74 68 65 20 * Print out the
47a0: 68 69 73 74 6f 67 72 61 6d 20 61 6e 64 20 61 20 histogram and a
47b0: 66 65 77 20 6f 74 68 65 72 20 70 69 65 63 65 73 few other pieces
47c0: 20 6f 66 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 2e of information.
47d0: 0a 20 20 20 20 20 2a 2f 0a 0a 20 20 20 20 72 65 . */.. re
47e0: 73 75 6c 74 20 3d 20 28 63 68 61 72 20 2a 29 54 sult = (char *)T
47f0: 63 6c 5f 41 6c 6c 6f 63 28 28 4e 55 4d 5f 43 4f cl_Alloc((NUM_CO
4800: 55 4e 54 45 52 53 20 2a 20 36 30 29 20 2b 20 33 UNTERS * 60) + 3
4810: 30 30 29 3b 0a 20 20 20 20 73 6e 70 72 69 6e 74 00);. snprint
4820: 66 28 72 65 73 75 6c 74 2c 20 36 30 2c 20 22 25 f(result, 60, "%
4830: 22 20 54 43 4c 5f 53 49 5a 45 5f 4d 4f 44 49 46 " TCL_SIZE_MODIF
4840: 49 45 52 20 22 75 20 65 6e 74 72 69 65 73 20 69 IER "u entries i
4850: 6e 20 74 61 62 6c 65 2c 20 25 22 20 54 43 4c 5f n table, %" TCL_
4860: 53 49 5a 45 5f 4d 4f 44 49 46 49 45 52 20 22 75 SIZE_MODIFIER "u
4870: 20 62 75 63 6b 65 74 73 5c 6e 22 2c 0a 09 20 20 buckets\n",..
4880: 20 20 74 61 62 6c 65 50 74 72 2d 3e 6e 75 6d 45 tablePtr->numE
4890: 6e 74 72 69 65 73 2c 20 74 61 62 6c 65 50 74 72 ntries, tablePtr
48a0: 2d 3e 6e 75 6d 42 75 63 6b 65 74 73 29 3b 0a 20 ->numBuckets);.
48b0: 20 20 20 70 20 3d 20 72 65 73 75 6c 74 20 2b 20 p = result +
48c0: 73 74 72 6c 65 6e 28 72 65 73 75 6c 74 29 3b 0a strlen(result);.
48d0: 20 20 20 20 66 6f 72 20 28 69 20 3d 20 30 3b 20 for (i = 0;
48e0: 69 20 3c 20 4e 55 4d 5f 43 4f 55 4e 54 45 52 53 i < NUM_COUNTERS
48f0: 3b 20 69 2b 2b 29 20 7b 0a 09 73 6e 70 72 69 6e ; i++) {..snprin
4900: 74 66 28 70 2c 20 36 30 2c 20 22 6e 75 6d 62 65 tf(p, 60, "numbe
4910: 72 20 6f 66 20 62 75 63 6b 65 74 73 20 77 69 74 r of buckets wit
4920: 68 20 25 22 20 54 43 4c 5f 53 49 5a 45 5f 4d 4f h %" TCL_SIZE_MO
4930: 44 49 46 49 45 52 20 22 75 20 65 6e 74 72 69 65 DIFIER "u entrie
4940: 73 3a 20 25 22 20 54 43 4c 5f 53 49 5a 45 5f 4d s: %" TCL_SIZE_M
4950: 4f 44 49 46 49 45 52 20 22 75 5c 6e 22 2c 0a 09 ODIFIER "u\n",..
4960: 09 69 2c 20 63 6f 75 6e 74 5b 69 5d 29 3b 0a 09 .i, count[i]);..
4970: 70 20 2b 3d 20 73 74 72 6c 65 6e 28 70 29 3b 0a p += strlen(p);.
4980: 20 20 20 20 7d 0a 20 20 20 20 73 6e 70 72 69 6e }. snprin
4990: 74 66 28 70 2c 20 36 30 2c 20 22 6e 75 6d 62 65 tf(p, 60, "numbe
49a0: 72 20 6f 66 20 62 75 63 6b 65 74 73 20 77 69 74 r of buckets wit
49b0: 68 20 25 64 20 6f 72 20 6d 6f 72 65 20 65 6e 74 h %d or more ent
49c0: 72 69 65 73 3a 20 25 22 20 54 43 4c 5f 53 49 5a ries: %" TCL_SIZ
49d0: 45 5f 4d 4f 44 49 46 49 45 52 20 22 75 5c 6e 22 E_MODIFIER "u\n"
49e0: 2c 0a 09 20 20 20 20 4e 55 4d 5f 43 4f 55 4e 54 ,.. NUM_COUNT
49f0: 45 52 53 2c 20 6f 76 65 72 66 6c 6f 77 29 3b 0a ERS, overflow);.
4a00: 20 20 20 20 70 20 2b 3d 20 73 74 72 6c 65 6e 28 p += strlen(
4a10: 70 29 3b 0a 20 20 20 20 73 6e 70 72 69 6e 74 66 p);. snprintf
4a20: 28 70 2c 20 36 30 2c 20 22 61 76 65 72 61 67 65 (p, 60, "average
4a30: 20 73 65 61 72 63 68 20 64 69 73 74 61 6e 63 65 search distance
4a40: 20 66 6f 72 20 65 6e 74 72 79 3a 20 25 2e 31 66 for entry: %.1f
4a50: 22 2c 20 61 76 65 72 61 67 65 29 3b 0a 20 20 20 ", average);.
4a60: 20 72 65 74 75 72 6e 20 72 65 73 75 6c 74 3b 0a return result;.
4a70: 7d 0a 0c 0a 2f 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d }.../*. *-------
4a80: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4a90: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4aa0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4ab0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
4ac0: 20 2a 0a 20 2a 20 41 6c 6c 6f 63 41 72 72 61 79 *. * AllocArray
4ad0: 45 6e 74 72 79 20 2d 2d 0a 20 2a 0a 20 2a 09 41 Entry --. *. *.A
4ae0: 6c 6c 6f 63 61 74 65 20 73 70 61 63 65 20 66 6f llocate space fo
4af0: 72 20 61 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 r a Tcl_HashEntr
4b00: 79 20 63 6f 6e 74 61 69 6e 69 6e 67 20 74 68 65 y containing the
4b10: 20 61 72 72 61 79 20 6b 65 79 2e 0a 20 2a 0a 20 array key.. *.
4b20: 2a 20 52 65 73 75 6c 74 73 3a 0a 20 2a 09 54 68 * Results:. *.Th
4b30: 65 20 72 65 74 75 72 6e 20 76 61 6c 75 65 20 69 e return value i
4b40: 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 s a pointer to t
4b50: 68 65 20 63 72 65 61 74 65 64 20 65 6e 74 72 79 he created entry
4b60: 2e 0a 20 2a 0a 20 2a 20 53 69 64 65 20 65 66 66 .. *. * Side eff
4b70: 65 63 74 73 3a 0a 20 2a 09 4e 6f 6e 65 2e 0a 20 ects:. *.None..
4b80: 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *. *------------
4b90: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4ba0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4bb0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4bc0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 2f 0a 0a ----------. */..
4bd0: 73 74 61 74 69 63 20 54 63 6c 5f 48 61 73 68 45 static Tcl_HashE
4be0: 6e 74 72 79 20 2a 0a 41 6c 6c 6f 63 41 72 72 61 ntry *.AllocArra
4bf0: 79 45 6e 74 72 79 28 0a 20 20 20 20 54 63 6c 5f yEntry(. Tcl_
4c00: 48 61 73 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 HashTable *table
4c10: 50 74 72 2c 09 2f 2a 20 48 61 73 68 20 74 61 62 Ptr,./* Hash tab
4c20: 6c 65 2e 20 2a 2f 0a 20 20 20 20 76 6f 69 64 20 le. */. void
4c30: 2a 6b 65 79 50 74 72 29 09 09 2f 2a 20 4b 65 79 *keyPtr)../* Key
4c40: 20 74 6f 20 73 74 6f 72 65 20 69 6e 20 74 68 65 to store in the
4c50: 20 68 61 73 68 20 74 61 62 6c 65 20 65 6e 74 72 hash table entr
4c60: 79 2e 20 2a 2f 0a 7b 0a 20 20 20 20 54 63 6c 5f y. */.{. Tcl_
4c70: 48 61 73 68 45 6e 74 72 79 20 2a 68 50 74 72 3b HashEntry *hPtr;
4c80: 0a 20 20 20 20 73 69 7a 65 5f 74 20 63 6f 75 6e . size_t coun
4c90: 74 20 3d 20 74 61 62 6c 65 50 74 72 2d 3e 6b 65 t = tablePtr->ke
4ca0: 79 54 79 70 65 20 2a 20 73 69 7a 65 6f 66 28 69 yType * sizeof(i
4cb0: 6e 74 29 3b 0a 20 20 20 20 73 69 7a 65 5f 74 20 nt);. size_t
4cc0: 73 69 7a 65 20 3d 20 6f 66 66 73 65 74 6f 66 28 size = offsetof(
4cd0: 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 2c 20 6b Tcl_HashEntry, k
4ce0: 65 79 29 20 2b 20 63 6f 75 6e 74 3b 0a 0a 20 20 ey) + count;..
4cf0: 20 20 69 66 20 28 73 69 7a 65 20 3c 20 73 69 7a if (size < siz
4d00: 65 6f 66 28 54 63 6c 5f 48 61 73 68 45 6e 74 72 eof(Tcl_HashEntr
4d10: 79 29 29 20 7b 0a 09 73 69 7a 65 20 3d 20 73 69 y)) {..size = si
4d20: 7a 65 6f 66 28 54 63 6c 5f 48 61 73 68 45 6e 74 zeof(Tcl_HashEnt
4d30: 72 79 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 68 ry);. }. h
4d40: 50 74 72 20 3d 20 28 54 63 6c 5f 48 61 73 68 45 Ptr = (Tcl_HashE
4d50: 6e 74 72 79 20 2a 29 54 63 6c 5f 41 74 74 65 6d ntry *)Tcl_Attem
4d60: 70 74 41 6c 6c 6f 63 28 73 69 7a 65 29 3b 0a 0a ptAlloc(size);..
4d70: 20 20 20 20 69 66 20 28 68 50 74 72 29 20 7b 0a if (hPtr) {.
4d80: 09 6d 65 6d 63 70 79 28 68 50 74 72 2d 3e 6b 65 .memcpy(hPtr->ke
4d90: 79 2e 73 74 72 69 6e 67 2c 20 6b 65 79 50 74 72 y.string, keyPtr
4da0: 2c 20 63 6f 75 6e 74 29 3b 0a 09 54 63 6c 5f 53 , count);..Tcl_S
4db0: 65 74 48 61 73 68 56 61 6c 75 65 28 68 50 74 72 etHashValue(hPtr
4dc0: 2c 20 4e 55 4c 4c 29 3b 0a 20 20 20 20 7d 0a 0a , NULL);. }..
4dd0: 20 20 20 20 72 65 74 75 72 6e 20 68 50 74 72 3b return hPtr;
4de0: 0a 7d 0a 0c 0a 2f 2a 0a 20 2a 2d 2d 2d 2d 2d 2d .}.../*. *------
4df0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4e00: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4e10: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4e20: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4e30: 0a 20 2a 0a 20 2a 20 43 6f 6d 70 61 72 65 41 72 . *. * CompareAr
4e40: 72 61 79 4b 65 79 73 20 2d 2d 0a 20 2a 0a 20 2a rayKeys --. *. *
4e50: 09 43 6f 6d 70 61 72 65 73 20 74 77 6f 20 61 72 .Compares two ar
4e60: 72 61 79 20 6b 65 79 73 2e 0a 20 2a 0a 20 2a 20 ray keys.. *. *
4e70: 52 65 73 75 6c 74 73 3a 0a 20 2a 09 54 68 65 20 Results:. *.The
4e80: 72 65 74 75 72 6e 20 76 61 6c 75 65 20 69 73 20 return value is
4e90: 30 20 69 66 20 74 68 65 79 20 61 72 65 20 64 69 0 if they are di
4ea0: 66 66 65 72 65 6e 74 20 61 6e 64 20 31 20 69 66 fferent and 1 if
4eb0: 20 74 68 65 79 20 61 72 65 20 74 68 65 0a 20 2a they are the. *
4ec0: 09 73 61 6d 65 2e 0a 20 2a 0a 20 2a 20 53 69 64 .same.. *. * Sid
4ed0: 65 20 65 66 66 65 63 74 73 3a 0a 20 2a 09 4e 6f e effects:. *.No
4ee0: 6e 65 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d ne.. *. *-------
4ef0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4f00: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4f10: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4f20: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
4f30: 20 2a 2f 0a 0a 73 74 61 74 69 63 20 69 6e 74 0a */..static int.
4f40: 43 6f 6d 70 61 72 65 41 72 72 61 79 4b 65 79 73 CompareArrayKeys
4f50: 28 0a 20 20 20 20 76 6f 69 64 20 2a 6b 65 79 50 (. void *keyP
4f60: 74 72 2c 09 09 2f 2a 20 4e 65 77 20 6b 65 79 20 tr,../* New key
4f70: 74 6f 20 63 6f 6d 70 61 72 65 2e 20 2a 2f 0a 20 to compare. */.
4f80: 20 20 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 Tcl_HashEntry
4f90: 20 2a 68 50 74 72 29 09 2f 2a 20 45 78 69 73 74 *hPtr)./* Exist
4fa0: 69 6e 67 20 6b 65 79 20 74 6f 20 63 6f 6d 70 61 ing key to compa
4fb0: 72 65 2e 20 2a 2f 0a 7b 0a 20 20 20 20 73 69 7a re. */.{. siz
4fc0: 65 5f 74 20 63 6f 75 6e 74 20 3d 20 68 50 74 72 e_t count = hPtr
4fd0: 2d 3e 74 61 62 6c 65 50 74 72 2d 3e 6b 65 79 54 ->tablePtr->keyT
4fe0: 79 70 65 20 2a 20 73 69 7a 65 6f 66 28 69 6e 74 ype * sizeof(int
4ff0: 29 3b 0a 0a 20 20 20 20 72 65 74 75 72 6e 20 21 );.. return !
5000: 6d 65 6d 63 6d 70 28 6b 65 79 50 74 72 2c 20 68 memcmp(keyPtr, h
5010: 50 74 72 2d 3e 6b 65 79 2e 73 74 72 69 6e 67 2c Ptr->key.string,
5020: 20 63 6f 75 6e 74 29 3b 0a 7d 0a 0c 0a 2f 2a 0a count);.}.../*.
5030: 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *--------------
5040: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5050: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5060: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5070: 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 48 --------. *. * H
5080: 61 73 68 41 72 72 61 79 4b 65 79 20 2d 2d 0a 20 ashArrayKey --.
5090: 2a 0a 20 2a 09 43 6f 6d 70 75 74 65 20 61 20 6f *. *.Compute a o
50a0: 6e 65 2d 77 6f 72 64 20 73 75 6d 6d 61 72 79 20 ne-word summary
50b0: 6f 66 20 61 6e 20 61 72 72 61 79 2c 20 77 68 69 of an array, whi
50c0: 63 68 20 63 61 6e 20 62 65 20 75 73 65 64 20 74 ch can be used t
50d0: 6f 20 67 65 6e 65 72 61 74 65 0a 20 2a 09 61 20 o generate. *.a
50e0: 68 61 73 68 20 69 6e 64 65 78 2e 0a 20 2a 0a 20 hash index.. *.
50f0: 2a 20 52 65 73 75 6c 74 73 3a 0a 20 2a 09 54 68 * Results:. *.Th
5100: 65 20 72 65 74 75 72 6e 20 76 61 6c 75 65 20 69 e return value i
5110: 73 20 61 20 6f 6e 65 2d 77 6f 72 64 20 73 75 6d s a one-word sum
5120: 6d 61 72 79 20 6f 66 20 74 68 65 20 69 6e 66 6f mary of the info
5130: 72 6d 61 74 69 6f 6e 20 69 6e 0a 20 2a 09 73 74 rmation in. *.st
5140: 72 69 6e 67 2e 0a 20 2a 0a 20 2a 20 53 69 64 65 ring.. *. * Side
5150: 20 65 66 66 65 63 74 73 3a 0a 20 2a 09 4e 6f 6e effects:. *.Non
5160: 65 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d e.. *. *--------
5170: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5180: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5190: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
51a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 --------------.
51b0: 2a 2f 0a 0a 73 74 61 74 69 63 20 73 69 7a 65 5f */..static size_
51c0: 74 0a 48 61 73 68 41 72 72 61 79 4b 65 79 28 0a t.HashArrayKey(.
51d0: 20 20 20 20 54 63 6c 5f 48 61 73 68 54 61 62 6c Tcl_HashTabl
51e0: 65 20 2a 74 61 62 6c 65 50 74 72 2c 09 2f 2a 20 e *tablePtr,./*
51f0: 48 61 73 68 20 74 61 62 6c 65 2e 20 2a 2f 0a 20 Hash table. */.
5200: 20 20 20 76 6f 69 64 20 2a 6b 65 79 50 74 72 29 void *keyPtr)
5210: 09 09 2f 2a 20 4b 65 79 20 66 72 6f 6d 20 77 68 ../* Key from wh
5220: 69 63 68 20 74 6f 20 63 6f 6d 70 75 74 65 20 68 ich to compute h
5230: 61 73 68 20 76 61 6c 75 65 2e 20 2a 2f 0a 7b 0a ash value. */.{.
5240: 20 20 20 20 63 6f 6e 73 74 20 69 6e 74 20 2a 61 const int *a
5250: 72 72 61 79 20 3d 20 28 63 6f 6e 73 74 20 69 6e rray = (const in
5260: 74 20 2a 29 20 6b 65 79 50 74 72 3b 0a 20 20 20 t *) keyPtr;.
5270: 20 73 69 7a 65 5f 74 20 72 65 73 75 6c 74 3b 0a size_t result;.
5280: 20 20 20 20 69 6e 74 20 63 6f 75 6e 74 3b 0a 0a int count;..
5290: 20 20 20 20 66 6f 72 20 28 72 65 73 75 6c 74 20 for (result
52a0: 3d 20 30 2c 20 63 6f 75 6e 74 20 3d 20 74 61 62 = 0, count = tab
52b0: 6c 65 50 74 72 2d 3e 6b 65 79 54 79 70 65 3b 20 lePtr->keyType;
52c0: 63 6f 75 6e 74 20 3e 20 30 3b 0a 09 20 20 20 20 count > 0;..
52d0: 63 6f 75 6e 74 2d 2d 2c 20 61 72 72 61 79 2b 2b count--, array++
52e0: 29 20 7b 0a 09 72 65 73 75 6c 74 20 2b 3d 20 2a ) {..result += *
52f0: 61 72 72 61 79 3b 0a 20 20 20 20 7d 0a 20 20 20 array;. }.
5300: 20 72 65 74 75 72 6e 20 72 65 73 75 6c 74 3b 0a return result;.
5310: 7d 0a 0c 0a 2f 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d }.../*. *-------
5320: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5330: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5340: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5350: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
5360: 20 2a 0a 20 2a 20 41 6c 6c 6f 63 53 74 72 69 6e *. * AllocStrin
5370: 67 45 6e 74 72 79 20 2d 2d 0a 20 2a 0a 20 2a 09 gEntry --. *. *.
5380: 41 6c 6c 6f 63 61 74 65 20 73 70 61 63 65 20 66 Allocate space f
5390: 6f 72 20 61 20 54 63 6c 5f 48 61 73 68 45 6e 74 or a Tcl_HashEnt
53a0: 72 79 20 63 6f 6e 74 61 69 6e 69 6e 67 20 74 68 ry containing th
53b0: 65 20 73 74 72 69 6e 67 20 6b 65 79 2e 0a 20 2a e string key.. *
53c0: 0a 20 2a 20 52 65 73 75 6c 74 73 3a 0a 20 2a 09 . * Results:. *.
53d0: 54 68 65 20 72 65 74 75 72 6e 20 76 61 6c 75 65 The return value
53e0: 20 69 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f is a pointer to
53f0: 20 74 68 65 20 63 72 65 61 74 65 64 20 65 6e 74 the created ent
5400: 72 79 2e 0a 20 2a 0a 20 2a 20 53 69 64 65 20 65 ry.. *. * Side e
5410: 66 66 65 63 74 73 3a 0a 20 2a 09 4e 6f 6e 65 2e ffects:. *.None.
5420: 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d . *. *----------
5430: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5440: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5450: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5460: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 2f ------------. */
5470: 0a 0a 73 74 61 74 69 63 20 54 63 6c 5f 48 61 73 ..static Tcl_Has
5480: 68 45 6e 74 72 79 20 2a 0a 41 6c 6c 6f 63 53 74 hEntry *.AllocSt
5490: 72 69 6e 67 45 6e 74 72 79 28 0a 20 20 20 20 54 ringEntry(. T
54a0: 43 4c 5f 55 4e 55 53 45 44 28 54 63 6c 5f 48 61 CL_UNUSED(Tcl_Ha
54b0: 73 68 54 61 62 6c 65 20 2a 29 2c 0a 20 20 20 20 shTable *),.
54c0: 76 6f 69 64 20 2a 6b 65 79 50 74 72 29 09 09 2f void *keyPtr)../
54d0: 2a 20 4b 65 79 20 74 6f 20 73 74 6f 72 65 20 69 * Key to store i
54e0: 6e 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 n the hash table
54f0: 20 65 6e 74 72 79 2e 20 2a 2f 0a 7b 0a 20 20 20 entry. */.{.
5500: 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 73 74 72 const char *str
5510: 69 6e 67 20 3d 20 28 63 6f 6e 73 74 20 63 68 61 ing = (const cha
5520: 72 20 2a 29 20 6b 65 79 50 74 72 3b 0a 20 20 20 r *) keyPtr;.
5530: 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 2a Tcl_HashEntry *
5540: 68 50 74 72 3b 0a 20 20 20 20 73 69 7a 65 5f 74 hPtr;. size_t
5550: 20 73 69 7a 65 2c 20 61 6c 6c 6f 63 73 69 7a 65 size, allocsize
5560: 3b 0a 0a 20 20 20 20 61 6c 6c 6f 63 73 69 7a 65 ;.. allocsize
5570: 20 3d 20 73 69 7a 65 20 3d 20 73 74 72 6c 65 6e = size = strlen
5580: 28 73 74 72 69 6e 67 29 20 2b 20 31 3b 0a 20 20 (string) + 1;.
5590: 20 20 69 66 20 28 73 69 7a 65 20 3c 20 73 69 7a if (size < siz
55a0: 65 6f 66 28 68 50 74 72 2d 3e 6b 65 79 29 29 20 eof(hPtr->key))
55b0: 7b 0a 09 61 6c 6c 6f 63 73 69 7a 65 20 3d 20 73 {..allocsize = s
55c0: 69 7a 65 6f 66 28 68 50 74 72 2d 3e 6b 65 79 29 izeof(hPtr->key)
55d0: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 68 50 74 72 ;. }. hPtr
55e0: 20 3d 20 28 54 63 6c 5f 48 61 73 68 45 6e 74 72 = (Tcl_HashEntr
55f0: 79 20 2a 29 54 63 6c 5f 41 74 74 65 6d 70 74 41 y *)Tcl_AttemptA
5600: 6c 6c 6f 63 28 6f 66 66 73 65 74 6f 66 28 54 63 lloc(offsetof(Tc
5610: 6c 5f 48 61 73 68 45 6e 74 72 79 2c 20 6b 65 79 l_HashEntry, key
5620: 29 20 2b 20 61 6c 6c 6f 63 73 69 7a 65 29 3b 0a ) + allocsize);.
5630: 20 20 20 20 69 66 20 28 68 50 74 72 29 20 7b 0a if (hPtr) {.
5640: 09 6d 65 6d 73 65 74 28 68 50 74 72 2c 20 30 2c .memset(hPtr, 0,
5650: 20 6f 66 66 73 65 74 6f 66 28 54 63 6c 5f 48 61 offsetof(Tcl_Ha
5660: 73 68 45 6e 74 72 79 2c 20 6b 65 79 29 20 2b 20 shEntry, key) +
5670: 61 6c 6c 6f 63 73 69 7a 65 29 3b 0a 09 6d 65 6d allocsize);..mem
5680: 63 70 79 28 68 50 74 72 2d 3e 6b 65 79 2e 73 74 cpy(hPtr->key.st
5690: 72 69 6e 67 2c 20 73 74 72 69 6e 67 2c 20 73 69 ring, string, si
56a0: 7a 65 29 3b 0a 09 54 63 6c 5f 53 65 74 48 61 73 ze);..Tcl_SetHas
56b0: 68 56 61 6c 75 65 28 68 50 74 72 2c 20 4e 55 4c hValue(hPtr, NUL
56c0: 4c 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72 65 L);. }. re
56d0: 74 75 72 6e 20 68 50 74 72 3b 0a 7d 0a 0c 0a 2f turn hPtr;.}.../
56e0: 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *. *------------
56f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5700: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5710: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5720: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a ----------. *. *
5730: 20 54 63 6c 43 6f 6d 70 61 72 65 53 74 72 69 6e TclCompareStrin
5740: 67 4b 65 79 73 20 2d 2d 0a 20 2a 0a 20 2a 09 43 gKeys --. *. *.C
5750: 6f 6d 70 61 72 65 73 20 74 77 6f 20 73 74 72 69 ompares two stri
5760: 6e 67 20 6b 65 79 73 2e 0a 20 2a 0a 20 2a 20 52 ng keys.. *. * R
5770: 65 73 75 6c 74 73 3a 0a 20 2a 09 54 68 65 20 72 esults:. *.The r
5780: 65 74 75 72 6e 20 76 61 6c 75 65 20 69 73 20 30 eturn value is 0
5790: 20 69 66 20 74 68 65 79 20 61 72 65 20 64 69 66 if they are dif
57a0: 66 65 72 65 6e 74 20 61 6e 64 20 31 20 69 66 20 ferent and 1 if
57b0: 74 68 65 79 20 61 72 65 20 74 68 65 0a 20 2a 09 they are the. *.
57c0: 73 61 6d 65 2e 0a 20 2a 0a 20 2a 20 53 69 64 65 same.. *. * Side
57d0: 20 65 66 66 65 63 74 73 3a 0a 20 2a 09 4e 6f 6e effects:. *.Non
57e0: 65 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d e.. *. *--------
57f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5800: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5810: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5820: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 --------------.
5830: 2a 2f 0a 0a 69 6e 74 0a 54 63 6c 43 6f 6d 70 61 */..int.TclCompa
5840: 72 65 53 74 72 69 6e 67 4b 65 79 73 28 0a 20 20 reStringKeys(.
5850: 20 20 76 6f 69 64 20 2a 6b 65 79 50 74 72 2c 09 void *keyPtr,.
5860: 09 2f 2a 20 4e 65 77 20 6b 65 79 20 74 6f 20 63 ./* New key to c
5870: 6f 6d 70 61 72 65 2e 20 2a 2f 0a 20 20 20 20 54 ompare. */. T
5880: 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 2a 68 50 cl_HashEntry *hP
5890: 74 72 29 09 2f 2a 20 45 78 69 73 74 69 6e 67 20 tr)./* Existing
58a0: 6b 65 79 20 74 6f 20 63 6f 6d 70 61 72 65 2e 20 key to compare.
58b0: 2a 2f 0a 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 */.{. return
58c0: 21 73 74 72 63 6d 70 28 28 63 68 61 72 20 2a 29 !strcmp((char *)
58d0: 6b 65 79 50 74 72 2c 20 68 50 74 72 2d 3e 6b 65 keyPtr, hPtr->ke
58e0: 79 2e 73 74 72 69 6e 67 29 3b 0a 7d 0a 0c 0a 2f y.string);.}.../
58f0: 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *. *------------
5900: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5910: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5920: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5930: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a ----------. *. *
5940: 20 54 63 6c 48 61 73 68 53 74 72 69 6e 67 4b 65 TclHashStringKe
5950: 79 20 2d 2d 0a 20 2a 0a 20 2a 09 43 6f 6d 70 75 y --. *. *.Compu
5960: 74 65 20 61 20 6f 6e 65 2d 77 6f 72 64 20 73 75 te a one-word su
5970: 6d 6d 61 72 79 20 6f 66 20 61 20 74 65 78 74 20 mmary of a text
5980: 73 74 72 69 6e 67 2c 20 77 68 69 63 68 20 63 61 string, which ca
5990: 6e 20 62 65 20 75 73 65 64 20 74 6f 0a 20 2a 09 n be used to. *.
59a0: 67 65 6e 65 72 61 74 65 20 61 20 68 61 73 68 20 generate a hash
59b0: 69 6e 64 65 78 2e 0a 20 2a 0a 20 2a 20 52 65 73 index.. *. * Res
59c0: 75 6c 74 73 3a 0a 20 2a 09 54 68 65 20 72 65 74 ults:. *.The ret
59d0: 75 72 6e 20 76 61 6c 75 65 20 69 73 20 61 20 6f urn value is a o
59e0: 6e 65 2d 77 6f 72 64 20 73 75 6d 6d 61 72 79 20 ne-word summary
59f0: 6f 66 20 74 68 65 20 69 6e 66 6f 72 6d 61 74 69 of the informati
5a00: 6f 6e 20 69 6e 20 73 74 72 69 6e 67 2e 0a 20 2a on in string.. *
5a10: 0a 20 2a 20 53 69 64 65 20 65 66 66 65 63 74 73 . * Side effects
5a20: 3a 0a 20 2a 09 4e 6f 6e 65 2e 0a 20 2a 0a 20 2a :. *.None.. *. *
5a30: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5a40: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5a50: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5a60: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5a70: 2d 2d 2d 2d 2d 2d 0a 20 2a 2f 0a 0a 73 69 7a 65 ------. */..size
5a80: 5f 74 0a 54 63 6c 48 61 73 68 53 74 72 69 6e 67 _t.TclHashString
5a90: 4b 65 79 28 0a 20 20 20 20 54 43 4c 5f 55 4e 55 Key(. TCL_UNU
5aa0: 53 45 44 28 54 63 6c 5f 48 61 73 68 54 61 62 6c SED(Tcl_HashTabl
5ab0: 65 20 2a 29 2c 0a 20 20 20 20 76 6f 69 64 20 2a e *),. void *
5ac0: 6b 65 79 50 74 72 29 09 09 2f 2a 20 4b 65 79 20 keyPtr)../* Key
5ad0: 66 72 6f 6d 20 77 68 69 63 68 20 74 6f 20 63 6f from which to co
5ae0: 6d 70 75 74 65 20 68 61 73 68 20 76 61 6c 75 65 mpute hash value
5af0: 2e 20 2a 2f 0a 7b 0a 20 20 20 20 63 6f 6e 73 74 . */.{. const
5b00: 20 63 68 61 72 20 2a 73 74 72 69 6e 67 20 3d 20 char *string =
5b10: 28 63 6f 6e 73 74 20 63 68 61 72 20 2a 29 6b 65 (const char *)ke
5b20: 79 50 74 72 3b 0a 20 20 20 20 73 69 7a 65 5f 74 yPtr;. size_t
5b30: 20 72 65 73 75 6c 74 3b 0a 20 20 20 20 63 68 61 result;. cha
5b40: 72 20 63 3b 0a 0a 20 20 20 20 2f 2a 0a 20 20 20 r c;.. /*.
5b50: 20 20 2a 20 49 20 74 72 69 65 64 20 61 20 7a 69 * I tried a zi
5b60: 6c 6c 69 6f 6e 20 64 69 66 66 65 72 65 6e 74 20 llion different
5b70: 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 73 20 61 hash functions a
5b80: 6e 64 20 61 73 6b 65 64 20 6d 61 6e 79 20 6f 74 nd asked many ot
5b90: 68 65 72 20 70 65 6f 70 6c 65 0a 20 20 20 20 20 her people.
5ba0: 2a 20 66 6f 72 20 61 64 76 69 63 65 2e 20 4d 61 * for advice. Ma
5bb0: 6e 79 20 70 65 6f 70 6c 65 20 68 61 64 20 74 68 ny people had th
5bc0: 65 69 72 20 6f 77 6e 20 66 61 76 6f 72 69 74 65 eir own favorite
5bd0: 20 66 75 6e 63 74 69 6f 6e 73 2c 20 61 6c 6c 0a functions, all.
5be0: 20 20 20 20 20 2a 20 64 69 66 66 65 72 65 6e 74 * different
5bf0: 2c 20 62 75 74 20 6e 6f 2d 6f 6e 65 20 68 61 64 , but no-one had
5c00: 20 6d 75 63 68 20 69 64 65 61 20 77 68 79 20 74 much idea why t
5c10: 68 65 79 20 77 65 72 65 20 67 6f 6f 64 20 6f 6e hey were good on
5c20: 65 73 2e 20 49 20 63 68 6f 73 65 0a 20 20 20 20 es. I chose.
5c30: 20 2a 20 74 68 65 20 6f 6e 65 20 62 65 6c 6f 77 * the one below
5c40: 20 28 6d 75 6c 74 69 70 6c 79 20 62 79 20 39 20 (multiply by 9
5c50: 61 6e 64 20 61 64 64 20 6e 65 77 20 63 68 61 72 and add new char
5c60: 61 63 74 65 72 29 20 62 65 63 61 75 73 65 20 6f acter) because o
5c70: 66 20 74 68 65 0a 20 20 20 20 20 2a 20 66 6f 6c f the. * fol
5c80: 6c 6f 77 69 6e 67 20 72 65 61 73 6f 6e 73 3a 0a lowing reasons:.
5c90: 20 20 20 20 20 2a 0a 20 20 20 20 20 2a 20 31 2e *. * 1.
5ca0: 20 4d 75 6c 74 69 70 6c 79 69 6e 67 20 62 79 20 Multiplying by
5cb0: 31 30 20 69 73 20 70 65 72 66 65 63 74 20 66 6f 10 is perfect fo
5cc0: 72 20 6b 65 79 73 20 74 68 61 74 20 61 72 65 20 r keys that are
5cd0: 64 65 63 69 6d 61 6c 20 73 74 72 69 6e 67 73 2c decimal strings,
5ce0: 20 61 6e 64 0a 20 20 20 20 20 2a 20 20 20 20 6d and. * m
5cf0: 75 6c 74 69 70 6c 79 69 6e 67 20 62 79 20 39 20 ultiplying by 9
5d00: 69 73 20 6a 75 73 74 20 61 62 6f 75 74 20 61 73 is just about as
5d10: 20 67 6f 6f 64 2e 0a 20 20 20 20 20 2a 20 32 2e good.. * 2.
5d20: 20 54 69 6d 65 73 2d 39 20 69 73 20 28 73 68 69 Times-9 is (shi
5d30: 66 74 2d 6c 65 66 74 2d 33 29 20 70 6c 75 73 20 ft-left-3) plus
5d40: 28 6f 6c 64 29 2e 20 54 68 69 73 20 6d 65 61 6e (old). This mean
5d50: 73 20 74 68 61 74 20 65 61 63 68 0a 20 20 20 20 s that each.
5d60: 20 2a 20 20 20 20 63 68 61 72 61 63 74 65 72 27 * character'
5d70: 73 20 62 69 74 73 20 68 61 6e 67 20 61 72 6f 75 s bits hang arou
5d80: 6e 64 20 69 6e 20 74 68 65 20 6c 6f 77 2d 6f 72 nd in the low-or
5d90: 64 65 72 20 62 69 74 73 20 6f 66 20 74 68 65 20 der bits of the
5da0: 68 61 73 68 20 76 61 6c 75 65 0a 20 20 20 20 20 hash value.
5db0: 2a 20 20 20 20 66 6f 72 20 65 76 65 72 2c 20 70 * for ever, p
5dc0: 6c 75 73 20 74 68 65 79 20 73 70 72 65 61 64 20 lus they spread
5dd0: 66 61 69 72 6c 79 20 72 61 70 69 64 6c 79 20 75 fairly rapidly u
5de0: 70 20 74 6f 20 74 68 65 20 68 69 67 68 2d 6f 72 p to the high-or
5df0: 64 65 72 20 62 69 74 73 0a 20 20 20 20 20 2a 20 der bits. *
5e00: 20 20 20 74 6f 20 66 69 6c 6c 20 6f 75 74 20 74 to fill out t
5e10: 68 65 20 68 61 73 68 20 76 61 6c 75 65 2e 20 54 he hash value. T
5e20: 68 69 73 20 73 65 65 6d 73 20 77 6f 72 6b 73 20 his seems works
5e30: 77 65 6c 6c 20 62 6f 74 68 20 66 6f 72 20 64 65 well both for de
5e40: 63 69 6d 61 6c 0a 20 20 20 20 20 2a 20 20 20 20 cimal. *
5e50: 61 6e 64 20 6e 6f 6e 2d 64 65 63 69 6d 61 6c 20 and non-decimal
5e60: 73 74 72 69 6e 67 73 2c 20 62 75 74 20 69 73 6e strings, but isn
5e70: 27 74 20 73 74 72 6f 6e 67 20 61 67 61 69 6e 73 't strong agains
5e80: 74 20 6d 61 6c 69 63 69 6f 75 73 6c 79 2d 63 68 t maliciously-ch
5e90: 6f 73 65 6e 0a 20 20 20 20 20 2a 20 20 20 20 6b osen. * k
5ea0: 65 79 73 2e 0a 20 20 20 20 20 2a 0a 20 20 20 20 eys.. *.
5eb0: 20 2a 20 4e 6f 74 65 20 74 68 61 74 20 74 68 69 * Note that thi
5ec0: 73 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 76 65 s function is ve
5ed0: 72 79 20 77 65 61 6b 20 61 67 61 69 6e 73 74 20 ry weak against
5ee0: 6d 61 6c 69 63 69 6f 75 73 20 73 74 72 69 6e 67 malicious string
5ef0: 73 3b 20 69 74 27 73 0a 20 20 20 20 20 2a 20 76 s; it's. * v
5f00: 65 72 79 20 65 61 73 79 20 74 6f 20 67 65 6e 65 ery easy to gene
5f10: 72 61 74 65 20 6d 75 6c 74 69 70 6c 65 20 6b 65 rate multiple ke
5f20: 79 73 20 74 68 61 74 20 68 61 76 65 20 74 68 65 ys that have the
5f30: 20 73 61 6d 65 20 68 61 73 68 63 6f 64 65 2e 20 same hashcode.
5f40: 4f 6e 20 74 68 65 0a 20 20 20 20 20 2a 20 6f 74 On the. * ot
5f50: 68 65 72 20 68 61 6e 64 2c 20 74 68 61 74 20 68 her hand, that h
5f60: 61 72 64 6c 79 20 65 76 65 72 20 61 63 74 75 61 ardly ever actua
5f70: 6c 6c 79 20 6f 63 63 75 72 73 20 61 6e 64 20 74 lly occurs and t
5f80: 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 2a 69 73 his function *is
5f90: 2a 0a 20 20 20 20 20 2a 20 76 65 72 79 20 63 68 *. * very ch
5fa0: 65 61 70 2c 20 65 76 65 6e 20 62 79 20 63 6f 6d eap, even by com
5fb0: 70 61 72 69 73 6f 6e 20 77 69 74 68 20 69 6e 64 parison with ind
5fc0: 75 73 74 72 79 2d 73 74 61 6e 64 61 72 64 20 68 ustry-standard h
5fd0: 61 73 68 65 73 20 6c 69 6b 65 20 46 4e 56 2e 0a ashes like FNV..
5fe0: 20 20 20 20 20 2a 20 49 66 20 72 65 61 6c 20 73 * If real s
5ff0: 74 72 65 6e 67 74 68 20 6f 66 20 68 61 73 68 20 trength of hash
6000: 69 73 20 72 65 71 75 69 72 65 64 20 74 68 6f 75 is required thou
6010: 67 68 2c 20 75 73 65 20 61 20 63 75 73 74 6f 6d gh, use a custom
6020: 20 68 61 73 68 20 62 61 73 65 64 20 6f 6e 0a 20 hash based on.
6030: 20 20 20 20 2a 20 42 6f 62 20 4a 65 6e 6b 69 6e * Bob Jenkin
6040: 73 27 73 20 6c 6f 6f 6b 75 70 33 28 29 2c 20 62 s's lookup3(), b
6050: 75 74 20 62 65 20 61 77 61 72 65 20 74 68 61 74 ut be aware that
6060: 20 69 74 27 73 20 73 69 67 6e 69 66 69 63 61 6e it's significan
6070: 74 6c 79 20 73 6c 6f 77 65 72 2e 0a 20 20 20 20 tly slower..
6080: 20 2a 20 53 69 6e 63 65 20 54 63 6c 20 63 6f 6d * Since Tcl com
6090: 6d 61 6e 64 20 61 6e 64 20 6e 61 6d 65 73 70 61 mand and namespa
60a0: 63 65 20 6e 61 6d 65 73 20 61 72 65 20 75 73 75 ce names are usu
60b0: 61 6c 6c 79 20 72 65 61 73 6f 6e 61 62 6c 79 2d ally reasonably-
60c0: 6e 61 6d 65 64 20 28 74 68 65 0a 20 20 20 20 20 named (the.
60d0: 2a 20 6d 61 69 6e 20 75 73 65 20 66 6f 72 20 73 * main use for s
60e0: 74 72 69 6e 67 20 68 61 73 68 65 73 20 69 6e 20 tring hashes in
60f0: 6d 6f 64 65 72 6e 20 54 63 6c 29 20 73 70 65 65 modern Tcl) spee
6100: 64 20 69 73 20 66 61 72 20 6d 6f 72 65 20 69 6d d is far more im
6110: 70 6f 72 74 61 6e 74 0a 20 20 20 20 20 2a 20 74 portant. * t
6120: 68 61 6e 20 73 74 72 65 6e 67 74 68 2e 0a 20 20 han strength..
6130: 20 20 20 2a 0a 20 20 20 20 20 2a 20 53 65 65 20 *. * See
6140: 61 6c 73 6f 20 48 61 73 68 53 74 72 69 6e 67 20 also HashString
6150: 69 6e 20 74 63 6c 4c 69 74 65 72 61 6c 2e 63 2e in tclLiteral.c.
6160: 0a 20 20 20 20 20 2a 20 53 65 65 20 61 6c 73 6f . * See also
6170: 20 54 63 6c 4f 62 6a 48 61 73 68 4b 65 79 20 69 TclObjHashKey i
6180: 6e 20 74 63 6c 4f 62 6a 2e 63 2e 0a 20 20 20 20 n tclObj.c..
6190: 20 2a 0a 20 20 20 20 20 2a 20 53 65 65 20 5b 74 *. * See [t
61a0: 63 6c 2d 46 65 61 74 75 72 65 20 52 65 71 75 65 cl-Feature Reque
61b0: 73 74 20 23 32 39 35 38 38 33 32 5d 0a 20 20 20 st #2958832].
61c0: 20 20 2a 2f 0a 0a 20 20 20 20 69 66 20 28 28 72 */.. if ((r
61d0: 65 73 75 6c 74 20 3d 20 55 43 48 41 52 28 2a 73 esult = UCHAR(*s
61e0: 74 72 69 6e 67 29 29 20 21 3d 20 30 29 20 7b 0a tring)) != 0) {.
61f0: 09 77 68 69 6c 65 20 28 28 63 20 3d 20 2a 2b 2b .while ((c = *++
6200: 73 74 72 69 6e 67 29 20 21 3d 20 30 29 20 7b 0a string) != 0) {.
6210: 09 20 20 20 20 72 65 73 75 6c 74 20 2b 3d 20 28 . result += (
6220: 72 65 73 75 6c 74 20 3c 3c 20 33 29 20 2b 20 55 result << 3) + U
6230: 43 48 41 52 28 63 29 3b 0a 09 7d 0a 20 20 20 20 CHAR(c);..}.
6240: 7d 0a 20 20 20 20 72 65 74 75 72 6e 20 72 65 73 }. return res
6250: 75 6c 74 3b 0a 7d 0a 0c 0a 2f 2a 0a 20 2a 2d 2d ult;.}.../*. *--
6260: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6270: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6280: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6290: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
62a0: 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 42 6f 67 75 73 ----. *. * Bogus
62b0: 43 72 65 61 74 65 20 2d 2d 0a 20 2a 0a 20 2a 09 Create --. *. *.
62c0: 54 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 69 73 This function is
62d0: 20 69 6e 76 6f 6b 65 64 20 77 68 65 6e 20 54 63 invoked when Tc
62e0: 6c 5f 43 72 65 61 74 65 48 61 73 68 45 6e 74 72 l_CreateHashEntr
62f0: 79 20 69 73 20 63 61 6c 6c 65 64 20 6f 6e 20 61 y is called on a
6300: 0a 20 2a 09 74 61 62 6c 65 20 74 68 61 74 20 68 . *.table that h
6310: 61 73 20 62 65 65 6e 20 64 65 6c 65 74 65 64 2e as been deleted.
6320: 0a 20 2a 0a 20 2a 20 52 65 73 75 6c 74 73 3a 0a . *. * Results:.
6330: 20 2a 09 49 66 20 70 61 6e 69 63 20 72 65 74 75 *.If panic retu
6340: 72 6e 73 20 28 77 68 69 63 68 20 69 74 20 73 68 rns (which it sh
6350: 6f 75 6c 64 6e 27 74 29 20 74 68 69 73 20 66 75 ouldn't) this fu
6360: 6e 63 74 69 6f 6e 20 72 65 74 75 72 6e 73 20 4e nction returns N
6370: 55 4c 4c 2e 0a 20 2a 0a 20 2a 20 53 69 64 65 20 ULL.. *. * Side
6380: 65 66 66 65 63 74 73 3a 0a 20 2a 09 47 65 6e 65 effects:. *.Gene
6390: 72 61 74 65 73 20 61 20 70 61 6e 69 63 2e 0a 20 rates a panic..
63a0: 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *. *------------
63b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
63c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
63d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
63e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 2f 0a 0a ----------. */..
63f0: 73 74 61 74 69 63 20 54 63 6c 5f 48 61 73 68 45 static Tcl_HashE
6400: 6e 74 72 79 20 2a 0a 42 6f 67 75 73 43 72 65 61 ntry *.BogusCrea
6410: 74 65 28 0a 20 20 20 20 54 43 4c 5f 55 4e 55 53 te(. TCL_UNUS
6420: 45 44 28 54 63 6c 5f 48 61 73 68 54 61 62 6c 65 ED(Tcl_HashTable
6430: 20 2a 29 2c 0a 20 20 20 20 54 43 4c 5f 55 4e 55 *),. TCL_UNU
6440: 53 45 44 28 63 6f 6e 73 74 20 63 68 61 72 20 2a SED(const char *
6450: 29 2c 0a 20 20 20 20 69 6e 74 20 2a 69 73 4e 65 ),. int *isNe
6460: 77 29 0a 7b 0a 20 20 20 20 54 63 6c 5f 50 61 6e w).{. Tcl_Pan
6470: 69 63 28 22 63 61 6c 6c 65 64 20 25 73 20 6f 6e ic("called %s on
6480: 20 64 65 6c 65 74 65 64 20 74 61 62 6c 65 22 2c deleted table",
6490: 0a 09 20 20 20 20 28 69 73 4e 65 77 20 21 3d 20 .. (isNew !=
64a0: 54 43 4c 5f 48 41 53 48 5f 46 49 4e 44 29 3f 20 TCL_HASH_FIND)?
64b0: 22 54 63 6c 5f 43 72 65 61 74 65 48 61 73 68 45 "Tcl_CreateHashE
64c0: 6e 74 72 79 22 20 3a 20 22 54 63 6c 5f 46 69 6e ntry" : "Tcl_Fin
64d0: 64 48 61 73 68 45 6e 74 72 79 22 29 3b 0a 20 20 dHashEntry");.
64e0: 20 20 72 65 74 75 72 6e 20 4e 55 4c 4c 3b 0a 7d return NULL;.}
64f0: 0a 0c 0a 2f 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d .../*. *--------
6500: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6510: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6520: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6530: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 --------------.
6540: 2a 0a 20 2a 20 52 65 62 75 69 6c 64 54 61 62 6c *. * RebuildTabl
6550: 65 20 2d 2d 0a 20 2a 0a 20 2a 09 54 68 69 73 20 e --. *. *.This
6560: 66 75 6e 63 74 69 6f 6e 20 69 73 20 69 6e 76 6f function is invo
6570: 6b 65 64 20 77 68 65 6e 20 74 68 65 20 72 61 74 ked when the rat
6580: 69 6f 20 6f 66 20 65 6e 74 72 69 65 73 20 74 6f io of entries to
6590: 20 68 61 73 68 20 62 75 63 6b 65 74 73 0a 20 2a hash buckets. *
65a0: 09 62 65 63 6f 6d 65 73 20 74 6f 6f 20 6c 61 72 .becomes too lar
65b0: 67 65 2e 20 49 74 20 63 72 65 61 74 65 73 20 61 ge. It creates a
65c0: 20 6e 65 77 20 74 61 62 6c 65 20 77 69 74 68 20 new table with
65d0: 61 20 6c 61 72 67 65 72 20 62 75 63 6b 65 74 20 a larger bucket
65e0: 61 72 72 61 79 0a 20 2a 09 61 6e 64 20 6d 6f 76 array. *.and mov
65f0: 65 73 20 61 6c 6c 20 6f 66 20 74 68 65 20 65 6e es all of the en
6600: 74 72 69 65 73 20 69 6e 74 6f 20 74 68 65 20 6e tries into the n
6610: 65 77 20 74 61 62 6c 65 2e 0a 20 2a 0a 20 2a 20 ew table.. *. *
6620: 52 65 73 75 6c 74 73 3a 0a 20 2a 09 4e 6f 6e 65 Results:. *.None
6630: 2e 0a 20 2a 0a 20 2a 20 53 69 64 65 20 65 66 66 .. *. * Side eff
6640: 65 63 74 73 3a 0a 20 2a 09 4d 65 6d 6f 72 79 20 ects:. *.Memory
6650: 67 65 74 73 20 72 65 61 6c 6c 6f 63 61 74 65 64 gets reallocated
6660: 20 61 6e 64 20 65 6e 74 72 69 65 73 20 67 65 74 and entries get
6670: 20 72 65 2d 68 61 73 68 65 64 20 74 6f 20 6e 65 re-hashed to ne
6680: 77 20 62 75 63 6b 65 74 73 2e 0a 20 2a 0a 20 2a w buckets.. *. *
6690: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
66a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
66b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
66c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
66d0: 2d 2d 2d 2d 2d 2d 0a 20 2a 2f 0a 0a 73 74 61 74 ------. */..stat
66e0: 69 63 20 76 6f 69 64 0a 52 65 62 75 69 6c 64 54 ic void.RebuildT
66f0: 61 62 6c 65 28 0a 20 20 20 20 54 63 6c 5f 48 61 able(. Tcl_Ha
6700: 73 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 50 74 shTable *tablePt
6710: 72 29 09 2f 2a 20 54 61 62 6c 65 20 74 6f 20 65 r)./* Table to e
6720: 6e 6c 61 72 67 65 2e 20 2a 2f 0a 7b 0a 20 20 20 nlarge. */.{.
6730: 20 73 69 7a 65 5f 74 20 63 6f 75 6e 74 2c 20 69 size_t count, i
6740: 6e 64 65 78 2c 20 6f 6c 64 53 69 7a 65 20 3d 20 ndex, oldSize =
6750: 74 61 62 6c 65 50 74 72 2d 3e 6e 75 6d 42 75 63 tablePtr->numBuc
6760: 6b 65 74 73 3b 0a 20 20 20 20 54 63 6c 5f 48 61 kets;. Tcl_Ha
6770: 73 68 45 6e 74 72 79 20 2a 2a 6f 6c 64 42 75 63 shEntry **oldBuc
6780: 6b 65 74 73 20 3d 20 74 61 62 6c 65 50 74 72 2d kets = tablePtr-
6790: 3e 62 75 63 6b 65 74 73 3b 0a 20 20 20 20 54 63 >buckets;. Tc
67a0: 6c 5f 48 61 73 68 45 6e 74 72 79 20 2a 2a 6f 6c l_HashEntry **ol
67b0: 64 43 68 61 69 6e 50 74 72 2c 20 2a 2a 6e 65 77 dChainPtr, **new
67c0: 43 68 61 69 6e 50 74 72 3b 0a 20 20 20 20 54 63 ChainPtr;. Tc
67d0: 6c 5f 48 61 73 68 45 6e 74 72 79 20 2a 68 50 74 l_HashEntry *hPt
67e0: 72 3b 0a 20 20 20 20 63 6f 6e 73 74 20 54 63 6c r;. const Tcl
67f0: 5f 48 61 73 68 4b 65 79 54 79 70 65 20 2a 74 79 _HashKeyType *ty
6800: 70 65 50 74 72 3b 0a 0a 20 20 20 20 2f 2a 20 41 pePtr;.. /* A
6810: 76 6f 69 64 20 6f 75 74 67 72 6f 77 69 6e 67 20 void outgrowing
6820: 63 61 70 61 62 69 6c 69 74 79 20 6f 66 20 74 68 capability of th
6830: 65 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f 63 61 74 e memory allocat
6840: 6f 72 73 20 2a 2f 0a 20 20 20 20 69 66 20 28 6f ors */. if (o
6850: 6c 64 53 69 7a 65 20 3e 20 55 49 4e 54 5f 4d 41 ldSize > UINT_MA
6860: 58 20 2f 20 28 34 20 2a 20 73 69 7a 65 6f 66 28 X / (4 * sizeof(
6870: 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 2a 29 Tcl_HashEntry *)
6880: 29 29 20 7b 0a 09 74 61 62 6c 65 50 74 72 2d 3e )) {..tablePtr->
6890: 72 65 62 75 69 6c 64 53 69 7a 65 20 3d 20 49 4e rebuildSize = IN
68a0: 54 5f 4d 41 58 3b 0a 09 72 65 74 75 72 6e 3b 0a T_MAX;..return;.
68b0: 20 20 20 20 7d 0a 0a 20 20 20 20 69 66 20 28 74 }.. if (t
68c0: 61 62 6c 65 50 74 72 2d 3e 6b 65 79 54 79 70 65 ablePtr->keyType
68d0: 20 3d 3d 20 54 43 4c 5f 53 54 52 49 4e 47 5f 4b == TCL_STRING_K
68e0: 45 59 53 29 20 7b 0a 09 74 79 70 65 50 74 72 20 EYS) {..typePtr
68f0: 3d 20 26 74 63 6c 53 74 72 69 6e 67 48 61 73 68 = &tclStringHash
6900: 4b 65 79 54 79 70 65 3b 0a 20 20 20 20 7d 20 65 KeyType;. } e
6910: 6c 73 65 20 69 66 20 28 74 61 62 6c 65 50 74 72 lse if (tablePtr
6920: 2d 3e 6b 65 79 54 79 70 65 20 3d 3d 20 54 43 4c ->keyType == TCL
6930: 5f 4f 4e 45 5f 57 4f 52 44 5f 4b 45 59 53 29 20 _ONE_WORD_KEYS)
6940: 7b 0a 09 74 79 70 65 50 74 72 20 3d 20 26 74 63 {..typePtr = &tc
6950: 6c 4f 6e 65 57 6f 72 64 48 61 73 68 4b 65 79 54 lOneWordHashKeyT
6960: 79 70 65 3b 0a 20 20 20 20 7d 20 65 6c 73 65 20 ype;. } else
6970: 69 66 20 28 74 61 62 6c 65 50 74 72 2d 3e 6b 65 if (tablePtr->ke
6980: 79 54 79 70 65 20 3d 3d 20 54 43 4c 5f 43 55 53 yType == TCL_CUS
6990: 54 4f 4d 5f 54 59 50 45 5f 4b 45 59 53 0a 09 20 TOM_TYPE_KEYS..
69a0: 20 20 20 7c 7c 20 74 61 62 6c 65 50 74 72 2d 3e || tablePtr->
69b0: 6b 65 79 54 79 70 65 20 3d 3d 20 54 43 4c 5f 43 keyType == TCL_C
69c0: 55 53 54 4f 4d 5f 50 54 52 5f 4b 45 59 53 29 20 USTOM_PTR_KEYS)
69d0: 7b 0a 09 74 79 70 65 50 74 72 20 3d 20 74 61 62 {..typePtr = tab
69e0: 6c 65 50 74 72 2d 3e 74 79 70 65 50 74 72 3b 0a lePtr->typePtr;.
69f0: 20 20 20 20 7d 20 65 6c 73 65 20 7b 0a 09 74 79 } else {..ty
6a00: 70 65 50 74 72 20 3d 20 26 74 63 6c 41 72 72 61 pePtr = &tclArra
6a10: 79 48 61 73 68 4b 65 79 54 79 70 65 3b 0a 20 20 yHashKeyType;.
6a20: 20 20 7d 0a 0a 20 20 20 20 2f 2a 0a 20 20 20 20 }.. /*.
6a30: 20 2a 20 41 6c 6c 6f 63 61 74 65 20 61 6e 64 20 * Allocate and
6a40: 69 6e 69 74 69 61 6c 69 7a 65 20 74 68 65 20 6e initialize the n
6a50: 65 77 20 62 75 63 6b 65 74 20 61 72 72 61 79 2c ew bucket array,
6a60: 20 61 6e 64 20 73 65 74 20 75 70 20 68 61 73 68 and set up hash
6a70: 69 6e 67 0a 20 20 20 20 20 2a 20 63 6f 6e 73 74 ing. * const
6a80: 61 6e 74 73 20 66 6f 72 20 6e 65 77 20 61 72 72 ants for new arr
6a90: 61 79 20 73 69 7a 65 2e 0a 20 20 20 20 20 2a 2f ay size.. */
6aa0: 0a 0a 20 20 20 20 74 61 62 6c 65 50 74 72 2d 3e .. tablePtr->
6ab0: 6e 75 6d 42 75 63 6b 65 74 73 20 2a 3d 20 34 3b numBuckets *= 4;
6ac0: 0a 20 20 20 20 69 66 20 28 74 79 70 65 50 74 72 . if (typePtr
6ad0: 2d 3e 66 6c 61 67 73 20 26 20 54 43 4c 5f 48 41 ->flags & TCL_HA
6ae0: 53 48 5f 4b 45 59 5f 53 59 53 54 45 4d 5f 48 41 SH_KEY_SYSTEM_HA
6af0: 53 48 29 20 7b 0a 09 74 61 62 6c 65 50 74 72 2d SH) {..tablePtr-
6b00: 3e 62 75 63 6b 65 74 73 20 3d 20 28 54 63 6c 5f >buckets = (Tcl_
6b10: 48 61 73 68 45 6e 74 72 79 20 2a 2a 29 54 63 6c HashEntry **)Tcl
6b20: 70 53 79 73 41 6c 6c 6f 63 28 0a 09 09 74 61 62 pSysAlloc(...tab
6b30: 6c 65 50 74 72 2d 3e 6e 75 6d 42 75 63 6b 65 74 lePtr->numBucket
6b40: 73 20 2a 20 73 69 7a 65 6f 66 28 54 63 6c 5f 48 s * sizeof(Tcl_H
6b50: 61 73 68 45 6e 74 72 79 20 2a 29 29 3b 0a 20 20 ashEntry *));.
6b60: 20 20 7d 20 65 6c 73 65 20 7b 0a 09 74 61 62 6c } else {..tabl
6b70: 65 50 74 72 2d 3e 62 75 63 6b 65 74 73 20 3d 0a ePtr->buckets =.
6b80: 09 09 28 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 ..(Tcl_HashEntry
6b90: 20 2a 2a 29 54 63 6c 5f 41 6c 6c 6f 63 28 74 61 **)Tcl_Alloc(ta
6ba0: 62 6c 65 50 74 72 2d 3e 6e 75 6d 42 75 63 6b 65 blePtr->numBucke
6bb0: 74 73 20 2a 20 73 69 7a 65 6f 66 28 54 63 6c 5f ts * sizeof(Tcl_
6bc0: 48 61 73 68 45 6e 74 72 79 20 2a 29 29 3b 0a 20 HashEntry *));.
6bd0: 20 20 20 7d 0a 20 20 20 20 66 6f 72 20 28 63 6f }. for (co
6be0: 75 6e 74 20 3d 20 74 61 62 6c 65 50 74 72 2d 3e unt = tablePtr->
6bf0: 6e 75 6d 42 75 63 6b 65 74 73 2c 20 6e 65 77 43 numBuckets, newC
6c00: 68 61 69 6e 50 74 72 20 3d 20 74 61 62 6c 65 50 hainPtr = tableP
6c10: 74 72 2d 3e 62 75 63 6b 65 74 73 3b 0a 09 20 20 tr->buckets;..
6c20: 20 20 63 6f 75 6e 74 20 3e 20 30 3b 20 63 6f 75 count > 0; cou
6c30: 6e 74 2d 2d 2c 20 6e 65 77 43 68 61 69 6e 50 74 nt--, newChainPt
6c40: 72 2b 2b 29 20 7b 0a 09 2a 6e 65 77 43 68 61 69 r++) {..*newChai
6c50: 6e 50 74 72 20 3d 20 4e 55 4c 4c 3b 0a 20 20 20 nPtr = NULL;.
6c60: 20 7d 0a 20 20 20 20 74 61 62 6c 65 50 74 72 2d }. tablePtr-
6c70: 3e 72 65 62 75 69 6c 64 53 69 7a 65 20 2a 3d 20 >rebuildSize *=
6c80: 34 3b 0a 20 20 20 20 69 66 20 28 74 61 62 6c 65 4;. if (table
6c90: 50 74 72 2d 3e 64 6f 77 6e 53 68 69 66 74 20 3e Ptr->downShift >
6ca0: 20 31 29 20 7b 0a 09 74 61 62 6c 65 50 74 72 2d 1) {..tablePtr-
6cb0: 3e 64 6f 77 6e 53 68 69 66 74 20 2d 3d 20 32 3b >downShift -= 2;
6cc0: 0a 20 20 20 20 7d 0a 20 20 20 20 74 61 62 6c 65 . }. table
6cd0: 50 74 72 2d 3e 6d 61 73 6b 20 3d 20 28 74 61 62 Ptr->mask = (tab
6ce0: 6c 65 50 74 72 2d 3e 6d 61 73 6b 20 3c 3c 20 32 lePtr->mask << 2
6cf0: 29 20 2b 20 33 3b 0a 0a 20 20 20 20 2f 2a 0a 20 ) + 3;.. /*.
6d00: 20 20 20 20 2a 20 52 65 68 61 73 68 20 61 6c 6c * Rehash all
6d10: 20 6f 66 20 74 68 65 20 65 78 69 73 74 69 6e 67 of the existing
6d20: 20 65 6e 74 72 69 65 73 20 69 6e 74 6f 20 74 68 entries into th
6d30: 65 20 6e 65 77 20 62 75 63 6b 65 74 20 61 72 72 e new bucket arr
6d40: 61 79 2e 0a 20 20 20 20 20 2a 2f 0a 0a 20 20 20 ay.. */..
6d50: 20 66 6f 72 20 28 6f 6c 64 43 68 61 69 6e 50 74 for (oldChainPt
6d60: 72 20 3d 20 6f 6c 64 42 75 63 6b 65 74 73 3b 20 r = oldBuckets;
6d70: 6f 6c 64 53 69 7a 65 20 3e 20 30 3b 20 6f 6c 64 oldSize > 0; old
6d80: 53 69 7a 65 2d 2d 2c 20 6f 6c 64 43 68 61 69 6e Size--, oldChain
6d90: 50 74 72 2b 2b 29 20 7b 0a 09 66 6f 72 20 28 68 Ptr++) {..for (h
6da0: 50 74 72 20 3d 20 2a 6f 6c 64 43 68 61 69 6e 50 Ptr = *oldChainP
6db0: 74 72 3b 20 68 50 74 72 20 21 3d 20 4e 55 4c 4c tr; hPtr != NULL
6dc0: 3b 20 68 50 74 72 20 3d 20 2a 6f 6c 64 43 68 61 ; hPtr = *oldCha
6dd0: 69 6e 50 74 72 29 20 7b 0a 09 20 20 20 20 2a 6f inPtr) {.. *o
6de0: 6c 64 43 68 61 69 6e 50 74 72 20 3d 20 68 50 74 ldChainPtr = hPt
6df0: 72 2d 3e 6e 65 78 74 50 74 72 3b 0a 09 20 20 20 r->nextPtr;..
6e00: 20 69 66 20 28 74 79 70 65 50 74 72 2d 3e 68 61 if (typePtr->ha
6e10: 73 68 4b 65 79 50 72 6f 63 20 3d 3d 20 4e 55 4c shKeyProc == NUL
6e20: 4c 0a 09 09 20 20 20 20 7c 7c 20 74 79 70 65 50 L... || typeP
6e30: 74 72 2d 3e 66 6c 61 67 73 20 26 20 54 43 4c 5f tr->flags & TCL_
6e40: 48 41 53 48 5f 4b 45 59 5f 52 41 4e 44 4f 4d 49 HASH_KEY_RANDOMI
6e50: 5a 45 5f 48 41 53 48 29 20 7b 0a 09 09 69 6e 64 ZE_HASH) {...ind
6e60: 65 78 20 3d 20 52 41 4e 44 4f 4d 5f 49 4e 44 45 ex = RANDOM_INDE
6e70: 58 28 74 61 62 6c 65 50 74 72 2c 20 68 50 74 72 X(tablePtr, hPtr
6e80: 2d 3e 68 61 73 68 29 3b 0a 09 20 20 20 20 7d 20 ->hash);.. }
6e90: 65 6c 73 65 20 7b 0a 09 09 69 6e 64 65 78 20 3d else {...index =
6ea0: 20 68 50 74 72 2d 3e 68 61 73 68 20 26 20 74 61 hPtr->hash & ta
6eb0: 62 6c 65 50 74 72 2d 3e 6d 61 73 6b 3b 0a 09 20 blePtr->mask;..
6ec0: 20 20 20 7d 0a 09 20 20 20 20 68 50 74 72 2d 3e }.. hPtr->
6ed0: 6e 65 78 74 50 74 72 20 3d 20 74 61 62 6c 65 50 nextPtr = tableP
6ee0: 74 72 2d 3e 62 75 63 6b 65 74 73 5b 69 6e 64 65 tr->buckets[inde
6ef0: 78 5d 3b 0a 09 20 20 20 20 74 61 62 6c 65 50 74 x];.. tablePt
6f00: 72 2d 3e 62 75 63 6b 65 74 73 5b 69 6e 64 65 78 r->buckets[index
6f10: 5d 20 3d 20 68 50 74 72 3b 0a 09 7d 0a 20 20 20 ] = hPtr;..}.
6f20: 20 7d 0a 0a 20 20 20 20 2f 2a 0a 20 20 20 20 20 }.. /*.
6f30: 2a 20 46 72 65 65 20 75 70 20 74 68 65 20 6f 6c * Free up the ol
6f40: 64 20 62 75 63 6b 65 74 20 61 72 72 61 79 2c 20 d bucket array,
6f50: 69 66 20 69 74 20 77 61 73 20 64 79 6e 61 6d 69 if it was dynami
6f60: 63 61 6c 6c 79 20 61 6c 6c 6f 63 61 74 65 64 2e cally allocated.
6f70: 0a 20 20 20 20 20 2a 2f 0a 0a 20 20 20 20 69 66 . */.. if
6f80: 20 28 6f 6c 64 42 75 63 6b 65 74 73 20 21 3d 20 (oldBuckets !=
6f90: 74 61 62 6c 65 50 74 72 2d 3e 73 74 61 74 69 63 tablePtr->static
6fa0: 42 75 63 6b 65 74 73 29 20 7b 0a 09 69 66 20 28 Buckets) {..if (
6fb0: 74 79 70 65 50 74 72 2d 3e 66 6c 61 67 73 20 26 typePtr->flags &
6fc0: 20 54 43 4c 5f 48 41 53 48 5f 4b 45 59 5f 53 59 TCL_HASH_KEY_SY
6fd0: 53 54 45 4d 5f 48 41 53 48 29 20 7b 0a 09 20 20 STEM_HASH) {..
6fe0: 20 20 54 63 6c 70 53 79 73 46 72 65 65 28 28 63 TclpSysFree((c
6ff0: 68 61 72 20 2a 29 20 6f 6c 64 42 75 63 6b 65 74 har *) oldBucket
7000: 73 29 3b 0a 09 7d 20 65 6c 73 65 20 7b 0a 09 20 s);..} else {..
7010: 20 20 20 54 63 6c 5f 46 72 65 65 28 6f 6c 64 42 Tcl_Free(oldB
7020: 75 63 6b 65 74 73 29 3b 0a 09 7d 0a 20 20 20 20 uckets);..}.
7030: 7d 0a 7d 0a 0c 0a 2f 2a 0a 20 2a 20 4c 6f 63 61 }.}.../*. * Loca
7040: 6c 20 56 61 72 69 61 62 6c 65 73 3a 0a 20 2a 20 l Variables:. *
7050: 6d 6f 64 65 3a 20 63 0a 20 2a 20 63 2d 62 61 73 mode: c. * c-bas
7060: 69 63 2d 6f 66 66 73 65 74 3a 20 34 0a 20 2a 20 ic-offset: 4. *
7070: 66 69 6c 6c 2d 63 6f 6c 75 6d 6e 3a 20 37 38 0a fill-column: 78.
7080: 20 2a 20 45 6e 64 3a 0a 20 2a 2f 0a * End:. */.
