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 28 63 29 20 31 39 39 31 pyright (c) 1991
0080: 2d 31 39 39 33 20 54 68 65 20 52 65 67 65 6e 74 -1993 The Regent
0090: 73 20 6f 66 20 74 68 65 20 55 6e 69 76 65 72 73 s of the Univers
00a0: 69 74 79 20 6f 66 20 43 61 6c 69 66 6f 72 6e 69 ity of Californi
00b0: 61 2e 0a 20 2a 20 43 6f 70 79 72 69 67 68 74 20 a.. * Copyright
00c0: 28 63 29 20 31 39 39 34 20 53 75 6e 20 4d 69 63 (c) 1994 Sun Mic
00d0: 72 6f 73 79 73 74 65 6d 73 2c 20 49 6e 63 2e 0a rosystems, Inc..
00e0: 20 2a 0a 20 2a 20 53 65 65 20 74 68 65 20 66 69 *. * See the fi
00f0: 6c 65 20 22 6c 69 63 65 6e 73 65 2e 74 65 72 6d le "license.term
0100: 73 22 20 66 6f 72 20 69 6e 66 6f 72 6d 61 74 69 s" for informati
0110: 6f 6e 20 6f 6e 20 75 73 61 67 65 20 61 6e 64 20 on on usage and
0120: 72 65 64 69 73 74 72 69 62 75 74 69 6f 6e 20 6f redistribution o
0130: 66 0a 20 2a 20 74 68 69 73 20 66 69 6c 65 2c 20 f. * this file,
0140: 61 6e 64 20 66 6f 72 20 61 20 44 49 53 43 4c 41 and for a DISCLA
0150: 49 4d 45 52 20 4f 46 20 41 4c 4c 20 57 41 52 52 IMER OF ALL WARR
0160: 41 4e 54 49 45 53 2e 0a 20 2a 2f 0a 0a 23 69 6e ANTIES.. */..#in
0170: 63 6c 75 64 65 20 22 74 63 6c 49 6e 74 2e 68 22 clude "tclInt.h"
0180: 0a 0a 2f 2a 0a 20 2a 20 50 72 65 76 65 6e 74 20 ../*. * Prevent
0190: 6d 61 63 72 6f 73 20 66 72 6f 6d 20 63 6c 61 73 macros from clas
01a0: 68 69 6e 67 20 77 69 74 68 20 66 75 6e 63 74 69 hing with functi
01b0: 6f 6e 20 64 65 66 69 6e 69 74 69 6f 6e 73 2e 0a on definitions..
01c0: 20 2a 2f 0a 0a 23 75 6e 64 65 66 20 54 63 6c 5f */..#undef Tcl_
01d0: 46 69 6e 64 48 61 73 68 45 6e 74 72 79 0a 23 75 FindHashEntry.#u
01e0: 6e 64 65 66 20 54 63 6c 5f 43 72 65 61 74 65 48 ndef Tcl_CreateH
01f0: 61 73 68 45 6e 74 72 79 0a 0a 2f 2a 0a 20 2a 20 ashEntry../*. *
0200: 57 68 65 6e 20 74 68 65 72 65 20 61 72 65 20 74 When there are t
0210: 68 69 73 20 6d 61 6e 79 20 65 6e 74 72 69 65 73 his many entries
0220: 20 70 65 72 20 62 75 63 6b 65 74 2c 20 6f 6e 20 per bucket, on
0230: 61 76 65 72 61 67 65 2c 20 72 65 62 75 69 6c 64 average, rebuild
0240: 20 74 68 65 20 68 61 73 68 0a 20 2a 20 74 61 62 the hash. * tab
0250: 6c 65 20 74 6f 20 6d 61 6b 65 20 69 74 20 6c 61 le to make it la
0260: 72 67 65 72 2e 0a 20 2a 2f 0a 0a 23 64 65 66 69 rger.. */..#defi
0270: 6e 65 20 52 45 42 55 49 4c 44 5f 4d 55 4c 54 49 ne REBUILD_MULTI
0280: 50 4c 49 45 52 09 33 0a 0a 2f 2a 0a 20 2a 20 54 PLIER.3../*. * T
0290: 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 6d 61 63 he following mac
02a0: 72 6f 20 74 61 6b 65 73 20 61 20 70 72 65 6c 69 ro takes a preli
02b0: 6d 69 6e 61 72 79 20 69 6e 74 65 67 65 72 20 68 minary integer h
02c0: 61 73 68 20 76 61 6c 75 65 20 61 6e 64 20 70 72 ash value and pr
02d0: 6f 64 75 63 65 73 20 61 6e 0a 20 2a 20 69 6e 64 oduces an. * ind
02e0: 65 78 20 69 6e 74 6f 20 61 20 68 61 73 68 20 74 ex into a hash t
02f0: 61 62 6c 65 73 20 62 75 63 6b 65 74 20 6c 69 73 ables bucket lis
0300: 74 2e 20 54 68 65 20 69 64 65 61 20 69 73 20 74 t. The idea is t
0310: 6f 20 6d 61 6b 65 20 69 74 20 73 6f 20 74 68 61 o make it so tha
0320: 74 0a 20 2a 20 70 72 65 6c 69 6d 69 6e 61 72 79 t. * preliminary
0330: 20 76 61 6c 75 65 73 20 74 68 61 74 20 61 72 65 values that are
0340: 20 61 72 62 69 74 72 61 72 69 6c 79 20 73 69 6d arbitrarily sim
0350: 69 6c 61 72 20 77 69 6c 6c 20 65 6e 64 20 75 70 ilar will end up
0360: 20 69 6e 20 64 69 66 66 65 72 65 6e 74 0a 20 2a in different. *
0370: 20 62 75 63 6b 65 74 73 2e 20 54 68 65 20 68 61 buckets. The ha
0380: 73 68 20 66 75 6e 63 74 69 6f 6e 20 77 61 73 20 sh function was
0390: 74 61 6b 65 6e 20 66 72 6f 6d 20 61 20 72 61 6e taken from a ran
03a0: 64 6f 6d 2d 6e 75 6d 62 65 72 20 67 65 6e 65 72 dom-number gener
03b0: 61 74 6f 72 2e 0a 20 2a 2f 0a 0a 23 64 65 66 69 ator.. */..#defi
03c0: 6e 65 20 52 41 4e 44 4f 4d 5f 49 4e 44 45 58 28 ne RANDOM_INDEX(
03d0: 74 61 62 6c 65 50 74 72 2c 20 69 29 20 5c 0a 20 tablePtr, i) \.
03e0: 20 20 20 28 28 28 28 69 29 2a 31 31 30 33 35 31 ((((i)*110351
03f0: 35 32 34 35 55 4c 29 20 3e 3e 20 28 74 61 62 6c 5245UL) >> (tabl
0400: 65 50 74 72 29 2d 3e 64 6f 77 6e 53 68 69 66 74 ePtr)->downShift
0410: 29 20 26 20 28 74 61 62 6c 65 50 74 72 29 2d 3e ) & (tablePtr)->
0420: 6d 61 73 6b 29 0a 0a 2f 2a 0a 20 2a 20 50 72 6f mask)../*. * Pro
0430: 74 6f 74 79 70 65 73 20 66 6f 72 20 74 68 65 20 totypes for the
0440: 61 72 72 61 79 20 68 61 73 68 20 6b 65 79 20 6d array hash key m
0450: 65 74 68 6f 64 73 2e 0a 20 2a 2f 0a 0a 73 74 61 ethods.. */..sta
0460: 74 69 63 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 tic Tcl_HashEntr
0470: 79 20 2a 09 41 6c 6c 6f 63 41 72 72 61 79 45 6e y *.AllocArrayEn
0480: 74 72 79 28 54 63 6c 5f 48 61 73 68 54 61 62 6c try(Tcl_HashTabl
0490: 65 20 2a 74 61 62 6c 65 50 74 72 2c 20 76 6f 69 e *tablePtr, voi
04a0: 64 20 2a 6b 65 79 50 74 72 29 3b 0a 73 74 61 74 d *keyPtr);.stat
04b0: 69 63 20 69 6e 74 09 09 43 6f 6d 70 61 72 65 41 ic int..CompareA
04c0: 72 72 61 79 4b 65 79 73 28 76 6f 69 64 20 2a 6b rrayKeys(void *k
04d0: 65 79 50 74 72 2c 20 54 63 6c 5f 48 61 73 68 45 eyPtr, Tcl_HashE
04e0: 6e 74 72 79 20 2a 68 50 74 72 29 3b 0a 73 74 61 ntry *hPtr);.sta
04f0: 74 69 63 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 tic unsigned int
0500: 09 48 61 73 68 41 72 72 61 79 4b 65 79 28 54 63 .HashArrayKey(Tc
0510: 6c 5f 48 61 73 68 54 61 62 6c 65 20 2a 74 61 62 l_HashTable *tab
0520: 6c 65 50 74 72 2c 20 76 6f 69 64 20 2a 6b 65 79 lePtr, void *key
0530: 50 74 72 29 3b 0a 0a 2f 2a 0a 20 2a 20 50 72 6f Ptr);../*. * Pro
0540: 74 6f 74 79 70 65 73 20 66 6f 72 20 74 68 65 20 totypes for the
0550: 6f 6e 65 20 77 6f 72 64 20 68 61 73 68 20 6b 65 one word hash ke
0560: 79 20 6d 65 74 68 6f 64 73 2e 20 4e 6f 74 20 61 y methods. Not a
0570: 63 74 75 61 6c 6c 79 20 64 65 63 6c 61 72 65 64 ctually declared
0580: 20 62 65 63 61 75 73 65 0a 20 2a 20 74 68 69 73 because. * this
0590: 20 69 73 20 61 20 63 72 69 74 69 63 61 6c 20 70 is a critical p
05a0: 61 74 68 20 74 68 61 74 20 69 73 20 69 6d 70 6c ath that is impl
05b0: 65 6d 65 6e 74 65 64 20 69 6e 20 74 68 65 20 63 emented in the c
05c0: 6f 72 65 20 68 61 73 68 20 74 61 62 6c 65 20 61 ore hash table a
05d0: 63 63 65 73 73 0a 20 2a 20 66 75 6e 63 74 69 6f ccess. * functio
05e0: 6e 2e 0a 20 2a 2f 0a 0a 23 69 66 20 30 0a 73 74 n.. */..#if 0.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 41 6c 6c 6f 63 4f 6e 65 57 6f 72 ry *.AllocOneWor
0610: 64 45 6e 74 72 79 28 54 63 6c 5f 48 61 73 68 54 dEntry(Tcl_HashT
0620: 61 62 6c 65 20 2a 74 61 62 6c 65 50 74 72 2c 0a able *tablePtr,.
0630: 09 09 09 20 20 20 20 76 6f 69 64 20 2a 6b 65 79 ... void *key
0640: 50 74 72 29 3b 0a 73 74 61 74 69 63 20 69 6e 74 Ptr);.static int
0650: 09 09 43 6f 6d 70 61 72 65 4f 6e 65 57 6f 72 64 ..CompareOneWord
0660: 4b 65 79 73 28 76 6f 69 64 20 2a 6b 65 79 50 74 Keys(void *keyPt
0670: 72 2c 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 r, Tcl_HashEntry
0680: 20 2a 68 50 74 72 29 3b 0a 73 74 61 74 69 63 20 *hPtr);.static
0690: 75 6e 73 69 67 6e 65 64 20 69 6e 74 09 48 61 73 unsigned int.Has
06a0: 68 4f 6e 65 57 6f 72 64 4b 65 79 28 54 63 6c 5f hOneWordKey(Tcl_
06b0: 48 61 73 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 HashTable *table
06c0: 50 74 72 2c 20 76 6f 69 64 20 2a 6b 65 79 50 74 Ptr, void *keyPt
06d0: 72 29 3b 0a 23 65 6e 64 69 66 0a 0a 2f 2a 0a 20 r);.#endif../*.
06e0: 2a 20 50 72 6f 74 6f 74 79 70 65 73 20 66 6f 72 * Prototypes for
06f0: 20 74 68 65 20 73 74 72 69 6e 67 20 68 61 73 68 the string hash
0700: 20 6b 65 79 20 6d 65 74 68 6f 64 73 2e 0a 20 2a key methods.. *
0710: 2f 0a 0a 73 74 61 74 69 63 20 54 63 6c 5f 48 61 /..static Tcl_Ha
0720: 73 68 45 6e 74 72 79 20 2a 09 41 6c 6c 6f 63 53 shEntry *.AllocS
0730: 74 72 69 6e 67 45 6e 74 72 79 28 54 63 6c 5f 48 tringEntry(Tcl_H
0740: 61 73 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 50 ashTable *tableP
0750: 74 72 2c 0a 09 09 09 20 20 20 20 76 6f 69 64 20 tr,.... void
0760: 2a 6b 65 79 50 74 72 29 3b 0a 73 74 61 74 69 63 *keyPtr);.static
0770: 20 69 6e 74 09 09 43 6f 6d 70 61 72 65 53 74 72 int..CompareStr
0780: 69 6e 67 4b 65 79 73 28 76 6f 69 64 20 2a 6b 65 ingKeys(void *ke
0790: 79 50 74 72 2c 20 54 63 6c 5f 48 61 73 68 45 6e yPtr, Tcl_HashEn
07a0: 74 72 79 20 2a 68 50 74 72 29 3b 0a 73 74 61 74 try *hPtr);.stat
07b0: 69 63 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 09 ic unsigned int.
07c0: 48 61 73 68 53 74 72 69 6e 67 4b 65 79 28 54 63 HashStringKey(Tc
07d0: 6c 5f 48 61 73 68 54 61 62 6c 65 20 2a 74 61 62 l_HashTable *tab
07e0: 6c 65 50 74 72 2c 20 76 6f 69 64 20 2a 6b 65 79 lePtr, void *key
07f0: 50 74 72 29 3b 0a 0a 2f 2a 0a 20 2a 20 46 75 6e Ptr);../*. * Fun
0800: 63 74 69 6f 6e 20 70 72 6f 74 6f 74 79 70 65 73 ction prototypes
0810: 20 66 6f 72 20 73 74 61 74 69 63 20 66 75 6e 63 for static func
0820: 74 69 6f 6e 73 20 69 6e 20 74 68 69 73 20 66 69 tions in this fi
0830: 6c 65 3a 0a 20 2a 2f 0a 0a 73 74 61 74 69 63 20 le:. */..static
0840: 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 2a 09 Tcl_HashEntry *.
0850: 42 6f 67 75 73 46 69 6e 64 28 54 63 6c 5f 48 61 BogusFind(Tcl_Ha
0860: 73 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 50 74 shTable *tablePt
0870: 72 2c 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 6b r, const char *k
0880: 65 79 29 3b 0a 73 74 61 74 69 63 20 54 63 6c 5f ey);.static Tcl_
0890: 48 61 73 68 45 6e 74 72 79 20 2a 09 42 6f 67 75 HashEntry *.Bogu
08a0: 73 43 72 65 61 74 65 28 54 63 6c 5f 48 61 73 68 sCreate(Tcl_Hash
08b0: 54 61 62 6c 65 20 2a 74 61 62 6c 65 50 74 72 2c Table *tablePtr,
08c0: 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 6b 65 79 const char *key
08d0: 2c 0a 09 09 09 20 20 20 20 69 6e 74 20 2a 6e 65 ,.... int *ne
08e0: 77 50 74 72 29 3b 0a 73 74 61 74 69 63 20 54 63 wPtr);.static Tc
08f0: 6c 5f 48 61 73 68 45 6e 74 72 79 20 2a 09 43 72 l_HashEntry *.Cr
0900: 65 61 74 65 48 61 73 68 45 6e 74 72 79 28 54 63 eateHashEntry(Tc
0910: 6c 5f 48 61 73 68 54 61 62 6c 65 20 2a 74 61 62 l_HashTable *tab
0920: 6c 65 50 74 72 2c 20 63 6f 6e 73 74 20 63 68 61 lePtr, const cha
0930: 72 20 2a 6b 65 79 2c 0a 09 09 09 20 20 20 20 69 r *key,.... i
0940: 6e 74 20 2a 6e 65 77 50 74 72 29 3b 0a 73 74 61 nt *newPtr);.sta
0950: 74 69 63 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 tic Tcl_HashEntr
0960: 79 20 2a 09 46 69 6e 64 48 61 73 68 45 6e 74 72 y *.FindHashEntr
0970: 79 28 54 63 6c 5f 48 61 73 68 54 61 62 6c 65 20 y(Tcl_HashTable
0980: 2a 74 61 62 6c 65 50 74 72 2c 20 63 6f 6e 73 74 *tablePtr, const
0990: 20 63 68 61 72 20 2a 6b 65 79 29 3b 0a 73 74 61 char *key);.sta
09a0: 74 69 63 20 76 6f 69 64 09 09 52 65 62 75 69 6c tic void..Rebuil
09b0: 64 54 61 62 6c 65 28 54 63 6c 5f 48 61 73 68 54 dTable(Tcl_HashT
09c0: 61 62 6c 65 20 2a 74 61 62 6c 65 50 74 72 29 3b able *tablePtr);
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 41 72 72 61 79 KeyType tclArray
09f0: 48 61 73 68 4b 65 79 54 79 70 65 20 3d 20 7b 0a HashKeyType = {.
0a00: 20 20 20 20 54 43 4c 5f 48 41 53 48 5f 4b 45 59 TCL_HASH_KEY
0a10: 5f 54 59 50 45 5f 56 45 52 53 49 4f 4e 2c 09 09 _TYPE_VERSION,..
0a20: 2f 2a 20 76 65 72 73 69 6f 6e 20 2a 2f 0a 20 20 /* version */.
0a30: 20 20 54 43 4c 5f 48 41 53 48 5f 4b 45 59 5f 52 TCL_HASH_KEY_R
0a40: 41 4e 44 4f 4d 49 5a 45 5f 48 41 53 48 2c 09 2f ANDOMIZE_HASH,./
0a50: 2a 20 66 6c 61 67 73 20 2a 2f 0a 20 20 20 20 48 * flags */. H
0a60: 61 73 68 41 72 72 61 79 4b 65 79 2c 09 09 09 2f ashArrayKey,.../
0a70: 2a 20 68 61 73 68 4b 65 79 50 72 6f 63 20 2a 2f * hashKeyProc */
0a80: 0a 20 20 20 20 43 6f 6d 70 61 72 65 41 72 72 61 . CompareArra
0a90: 79 4b 65 79 73 2c 09 09 09 2f 2a 20 63 6f 6d 70 yKeys,.../* comp
0aa0: 61 72 65 4b 65 79 73 50 72 6f 63 20 2a 2f 0a 20 areKeysProc */.
0ab0: 20 20 20 41 6c 6c 6f 63 41 72 72 61 79 45 6e 74 AllocArrayEnt
0ac0: 72 79 2c 09 09 09 2f 2a 20 61 6c 6c 6f 63 45 6e ry,.../* allocEn
0ad0: 74 72 79 50 72 6f 63 20 2a 2f 0a 20 20 20 20 4e tryProc */. N
0ae0: 55 4c 4c 09 09 09 09 2f 2a 20 66 72 65 65 45 6e ULL..../* freeEn
0af0: 74 72 79 50 72 6f 63 20 2a 2f 0a 7d 3b 0a 0a 63 tryProc */.};..c
0b00: 6f 6e 73 74 20 54 63 6c 5f 48 61 73 68 4b 65 79 onst Tcl_HashKey
0b10: 54 79 70 65 20 74 63 6c 4f 6e 65 57 6f 72 64 48 Type tclOneWordH
0b20: 61 73 68 4b 65 79 54 79 70 65 20 3d 20 7b 0a 20 ashKeyType = {.
0b30: 20 20 20 54 43 4c 5f 48 41 53 48 5f 4b 45 59 5f TCL_HASH_KEY_
0b40: 54 59 50 45 5f 56 45 52 53 49 4f 4e 2c 09 09 2f TYPE_VERSION,../
0b50: 2a 20 76 65 72 73 69 6f 6e 20 2a 2f 0a 20 20 20 * version */.
0b60: 20 30 2c 09 09 09 09 09 2f 2a 20 66 6c 61 67 73 0,...../* flags
0b70: 20 2a 2f 0a 20 20 20 20 4e 55 4c 4c 2c 20 2f 2a */. NULL, /*
0b80: 20 48 61 73 68 4f 6e 65 57 6f 72 64 4b 65 79 2c HashOneWordKey,
0b90: 20 2a 2f 09 09 2f 2a 20 68 61 73 68 50 72 6f 63 */../* hashProc
0ba0: 20 2a 2f 0a 20 20 20 20 4e 55 4c 4c 2c 20 2f 2a */. NULL, /*
0bb0: 20 43 6f 6d 70 61 72 65 4f 6e 65 57 6f 72 64 4b CompareOneWordK
0bc0: 65 79 2c 20 2a 2f 09 2f 2a 20 63 6f 6d 70 61 72 ey, */./* compar
0bd0: 65 50 72 6f 63 20 2a 2f 0a 20 20 20 20 4e 55 4c eProc */. NUL
0be0: 4c 2c 20 2f 2a 20 41 6c 6c 6f 63 4f 6e 65 57 6f L, /* AllocOneWo
0bf0: 72 64 4b 65 79 2c 20 2a 2f 09 2f 2a 20 61 6c 6c rdKey, */./* all
0c00: 6f 63 45 6e 74 72 79 50 72 6f 63 20 2a 2f 0a 20 ocEntryProc */.
0c10: 20 20 20 4e 55 4c 4c 20 20 2f 2a 20 46 72 65 65 NULL /* Free
0c20: 4f 6e 65 57 6f 72 64 4b 65 79 2c 20 2a 2f 09 09 OneWordKey, */..
0c30: 2f 2a 20 66 72 65 65 45 6e 74 72 79 50 72 6f 63 /* freeEntryProc
0c40: 20 2a 2f 0a 7d 3b 0a 0a 63 6f 6e 73 74 20 54 63 */.};..const Tc
0c50: 6c 5f 48 61 73 68 4b 65 79 54 79 70 65 20 74 63 l_HashKeyType tc
0c60: 6c 53 74 72 69 6e 67 48 61 73 68 4b 65 79 54 79 lStringHashKeyTy
0c70: 70 65 20 3d 20 7b 0a 20 20 20 20 54 43 4c 5f 48 pe = {. TCL_H
0c80: 41 53 48 5f 4b 45 59 5f 54 59 50 45 5f 56 45 52 ASH_KEY_TYPE_VER
0c90: 53 49 4f 4e 2c 09 09 2f 2a 20 76 65 72 73 69 6f SION,../* versio
0ca0: 6e 20 2a 2f 0a 20 20 20 20 30 2c 09 09 09 09 09 n */. 0,.....
0cb0: 2f 2a 20 66 6c 61 67 73 20 2a 2f 0a 20 20 20 20 /* flags */.
0cc0: 48 61 73 68 53 74 72 69 6e 67 4b 65 79 2c 09 09 HashStringKey,..
0cd0: 09 2f 2a 20 68 61 73 68 4b 65 79 50 72 6f 63 20 ./* hashKeyProc
0ce0: 2a 2f 0a 20 20 20 20 43 6f 6d 70 61 72 65 53 74 */. CompareSt
0cf0: 72 69 6e 67 4b 65 79 73 2c 09 09 09 2f 2a 20 63 ringKeys,.../* c
0d00: 6f 6d 70 61 72 65 4b 65 79 73 50 72 6f 63 20 2a ompareKeysProc *
0d10: 2f 0a 20 20 20 20 41 6c 6c 6f 63 53 74 72 69 6e /. AllocStrin
0d20: 67 45 6e 74 72 79 2c 09 09 09 2f 2a 20 61 6c 6c gEntry,.../* all
0d30: 6f 63 45 6e 74 72 79 50 72 6f 63 20 2a 2f 0a 20 ocEntryProc */.
0d40: 20 20 20 4e 55 4c 4c 09 09 09 09 2f 2a 20 66 72 NULL..../* fr
0d50: 65 65 45 6e 74 72 79 50 72 6f 63 20 2a 2f 0a 7d eeEntryProc */.}
0d60: 3b 0a 0c 0a 2f 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d ;.../*. *-------
0d70: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0d80: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0d90: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0da0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
0db0: 20 2a 0a 20 2a 20 54 63 6c 5f 49 6e 69 74 48 61 *. * Tcl_InitHa
0dc0: 73 68 54 61 62 6c 65 20 2d 2d 0a 20 2a 0a 20 2a shTable --. *. *
0dd0: 09 47 69 76 65 6e 20 73 74 6f 72 61 67 65 20 66 .Given storage f
0de0: 6f 72 20 61 20 68 61 73 68 20 74 61 62 6c 65 2c or a hash table,
0df0: 20 73 65 74 20 75 70 20 74 68 65 20 66 69 65 6c set up the fiel
0e00: 64 73 20 74 6f 20 70 72 65 70 61 72 65 20 74 68 ds to prepare th
0e10: 65 20 68 61 73 68 0a 20 2a 09 74 61 62 6c 65 20 e hash. *.table
0e20: 66 6f 72 20 75 73 65 2e 0a 20 2a 0a 20 2a 20 52 for use.. *. * R
0e30: 65 73 75 6c 74 73 3a 0a 20 2a 09 4e 6f 6e 65 2e esults:. *.None.
0e40: 0a 20 2a 0a 20 2a 20 53 69 64 65 20 65 66 66 65 . *. * Side effe
0e50: 63 74 73 3a 0a 20 2a 09 54 61 62 6c 65 50 74 72 cts:. *.TablePtr
0e60: 20 69 73 20 6e 6f 77 20 72 65 61 64 79 20 74 6f is now ready to
0e70: 20 62 65 20 70 61 73 73 65 64 20 74 6f 20 54 63 be passed to Tc
0e80: 6c 5f 46 69 6e 64 48 61 73 68 45 6e 74 72 79 20 l_FindHashEntry
0e90: 61 6e 64 0a 20 2a 09 54 63 6c 5f 43 72 65 61 74 and. *.Tcl_Creat
0ea0: 65 48 61 73 68 45 6e 74 72 79 2e 0a 20 2a 0a 20 eHashEntry.. *.
0eb0: 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *---------------
0ec0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0ed0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0ee0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0ef0: 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 2f 0a 0a 76 6f 69 -------. */..voi
0f00: 64 0a 54 63 6c 5f 49 6e 69 74 48 61 73 68 54 61 d.Tcl_InitHashTa
0f10: 62 6c 65 28 0a 20 20 20 20 54 63 6c 5f 48 61 73 ble(. Tcl_Has
0f20: 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 50 74 72 hTable *tablePtr
0f30: 2c 0a 09 09 09 09 2f 2a 20 50 6f 69 6e 74 65 72 ,...../* Pointer
0f40: 20 74 6f 20 74 61 62 6c 65 20 72 65 63 6f 72 64 to table record
0f50: 2c 20 77 68 69 63 68 20 69 73 20 73 75 70 70 6c , which is suppl
0f60: 69 65 64 0a 09 09 09 09 20 2a 20 62 79 20 74 68 ied..... * by th
0f70: 65 20 63 61 6c 6c 65 72 2e 20 2a 2f 0a 20 20 20 e caller. */.
0f80: 20 69 6e 74 20 6b 65 79 54 79 70 65 29 09 09 2f int keyType)../
0f90: 2a 20 54 79 70 65 20 6f 66 20 6b 65 79 73 20 74 * Type of keys t
0fa0: 6f 20 75 73 65 20 69 6e 20 74 61 62 6c 65 3a 0a o use in table:.
0fb0: 09 09 09 09 20 2a 20 54 43 4c 5f 53 54 52 49 4e .... * TCL_STRIN
0fc0: 47 5f 4b 45 59 53 2c 20 54 43 4c 5f 4f 4e 45 5f G_KEYS, TCL_ONE_
0fd0: 57 4f 52 44 5f 4b 45 59 53 2c 20 6f 72 20 61 6e WORD_KEYS, or an
0fe0: 0a 09 09 09 09 20 2a 20 69 6e 74 65 67 65 72 20 ..... * integer
0ff0: 3e 3d 20 32 2e 20 2a 2f 0a 7b 0a 20 20 20 20 2f >= 2. */.{. /
1000: 2a 0a 20 20 20 20 20 2a 20 55 73 65 20 61 20 73 *. * Use a s
1010: 70 65 63 69 61 6c 20 76 61 6c 75 65 20 74 6f 20 pecial value to
1020: 69 6e 66 6f 72 6d 20 74 68 65 20 65 78 74 65 6e inform the exten
1030: 64 65 64 20 76 65 72 73 69 6f 6e 20 74 68 61 74 ded version that
1040: 20 69 74 20 6d 75 73 74 20 6e 6f 74 0a 20 20 20 it must not.
1050: 20 20 2a 20 61 63 63 65 73 73 20 61 6e 79 20 6f * access any o
1060: 66 20 74 68 65 20 6e 65 77 20 66 69 65 6c 64 73 f the new fields
1070: 20 69 6e 20 74 68 65 20 54 63 6c 5f 48 61 73 68 in the Tcl_Hash
1080: 54 61 62 6c 65 2e 20 49 66 20 61 6e 20 65 78 74 Table. If an ext
1090: 65 6e 73 69 6f 6e 20 69 73 0a 20 20 20 20 20 2a ension is. *
10a0: 20 72 65 62 75 69 6c 74 20 74 68 65 6e 20 61 6e rebuilt then an
10b0: 79 20 63 61 6c 6c 73 20 74 6f 20 74 68 69 73 20 y calls to this
10c0: 66 75 6e 63 74 69 6f 6e 20 77 69 6c 6c 20 62 65 function will be
10d0: 20 72 65 64 69 72 65 63 74 65 64 20 74 6f 20 74 redirected to t
10e0: 68 65 0a 20 20 20 20 20 2a 20 65 78 74 65 6e 64 he. * extend
10f0: 65 64 20 76 65 72 73 69 6f 6e 20 62 79 20 61 20 ed version by a
1100: 6d 61 63 72 6f 2e 0a 20 20 20 20 20 2a 2f 0a 0a macro.. */..
1110: 20 20 20 20 54 63 6c 5f 49 6e 69 74 43 75 73 74 Tcl_InitCust
1120: 6f 6d 48 61 73 68 54 61 62 6c 65 28 74 61 62 6c omHashTable(tabl
1130: 65 50 74 72 2c 20 6b 65 79 54 79 70 65 2c 20 28 ePtr, keyType, (
1140: 63 6f 6e 73 74 20 54 63 6c 5f 48 61 73 68 4b 65 const Tcl_HashKe
1150: 79 54 79 70 65 20 2a 29 20 2d 31 29 3b 0a 7d 0a yType *) -1);.}.
1160: 0c 0a 2f 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d ../*. *---------
1170: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1180: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1190: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
11a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a -------------. *
11b0: 0a 20 2a 20 54 63 6c 5f 49 6e 69 74 43 75 73 74 . * Tcl_InitCust
11c0: 6f 6d 48 61 73 68 54 61 62 6c 65 20 2d 2d 0a 20 omHashTable --.
11d0: 2a 0a 20 2a 09 47 69 76 65 6e 20 73 74 6f 72 61 *. *.Given stora
11e0: 67 65 20 66 6f 72 20 61 20 68 61 73 68 20 74 61 ge for a hash ta
11f0: 62 6c 65 2c 20 73 65 74 20 75 70 20 74 68 65 20 ble, set up the
1200: 66 69 65 6c 64 73 20 74 6f 20 70 72 65 70 61 72 fields to prepar
1210: 65 20 74 68 65 20 68 61 73 68 0a 20 2a 09 74 61 e the hash. *.ta
1220: 62 6c 65 20 66 6f 72 20 75 73 65 2e 20 54 68 69 ble for use. Thi
1230: 73 20 69 73 20 61 6e 20 65 78 74 65 6e 64 65 64 s is an extended
1240: 20 76 65 72 73 69 6f 6e 20 6f 66 20 54 63 6c 5f version of Tcl_
1250: 49 6e 69 74 48 61 73 68 54 61 62 6c 65 20 77 68 InitHashTable wh
1260: 69 63 68 0a 20 2a 09 73 75 70 70 6f 72 74 73 20 ich. *.supports
1270: 75 73 65 72 20 64 65 66 69 6e 65 64 20 6b 65 79 user defined key
1280: 73 2e 0a 20 2a 0a 20 2a 20 52 65 73 75 6c 74 73 s.. *. * Results
1290: 3a 0a 20 2a 09 4e 6f 6e 65 2e 0a 20 2a 0a 20 2a :. *.None.. *. *
12a0: 20 53 69 64 65 20 65 66 66 65 63 74 73 3a 0a 20 Side effects:.
12b0: 2a 09 54 61 62 6c 65 50 74 72 20 69 73 20 6e 6f *.TablePtr is no
12c0: 77 20 72 65 61 64 79 20 74 6f 20 62 65 20 70 61 w ready to be pa
12d0: 73 73 65 64 20 74 6f 20 54 63 6c 5f 46 69 6e 64 ssed to Tcl_Find
12e0: 48 61 73 68 45 6e 74 72 79 20 61 6e 64 0a 20 2a HashEntry and. *
12f0: 09 54 63 6c 5f 43 72 65 61 74 65 48 61 73 68 45 .Tcl_CreateHashE
1300: 6e 74 72 79 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d ntry.. *. *-----
1310: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1320: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1330: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1340: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1350: 2d 0a 20 2a 2f 0a 0a 76 6f 69 64 0a 54 63 6c 5f -. */..void.Tcl_
1360: 49 6e 69 74 43 75 73 74 6f 6d 48 61 73 68 54 61 InitCustomHashTa
1370: 62 6c 65 28 0a 20 20 20 20 54 63 6c 5f 48 61 73 ble(. Tcl_Has
1380: 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 50 74 72 hTable *tablePtr
1390: 2c 0a 09 09 09 09 2f 2a 20 50 6f 69 6e 74 65 72 ,...../* Pointer
13a0: 20 74 6f 20 74 61 62 6c 65 20 72 65 63 6f 72 64 to table record
13b0: 2c 20 77 68 69 63 68 20 69 73 20 73 75 70 70 6c , which is suppl
13c0: 69 65 64 0a 09 09 09 09 20 2a 20 62 79 20 74 68 ied..... * by th
13d0: 65 20 63 61 6c 6c 65 72 2e 20 2a 2f 0a 20 20 20 e caller. */.
13e0: 20 69 6e 74 20 6b 65 79 54 79 70 65 2c 09 09 2f int keyType,../
13f0: 2a 20 54 79 70 65 20 6f 66 20 6b 65 79 73 20 74 * Type of keys t
1400: 6f 20 75 73 65 20 69 6e 20 74 61 62 6c 65 3a 0a o use in table:.
1410: 09 09 09 09 20 2a 20 54 43 4c 5f 53 54 52 49 4e .... * TCL_STRIN
1420: 47 5f 4b 45 59 53 2c 20 54 43 4c 5f 4f 4e 45 5f G_KEYS, TCL_ONE_
1430: 57 4f 52 44 5f 4b 45 59 53 2c 0a 09 09 09 09 20 WORD_KEYS,.....
1440: 2a 20 54 43 4c 5f 43 55 53 54 4f 4d 5f 54 59 50 * TCL_CUSTOM_TYP
1450: 45 5f 4b 45 59 53 2c 20 54 43 4c 5f 43 55 53 54 E_KEYS, TCL_CUST
1460: 4f 4d 5f 50 54 52 5f 4b 45 59 53 2c 0a 09 09 09 OM_PTR_KEYS,....
1470: 09 20 2a 20 6f 72 20 61 6e 20 69 6e 74 65 67 65 . * or an intege
1480: 72 20 3e 3d 20 32 2e 20 2a 2f 0a 20 20 20 20 63 r >= 2. */. c
1490: 6f 6e 73 74 20 54 63 6c 5f 48 61 73 68 4b 65 79 onst Tcl_HashKey
14a0: 54 79 70 65 20 2a 74 79 70 65 50 74 72 29 20 2f Type *typePtr) /
14b0: 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 73 74 72 * Pointer to str
14c0: 75 63 74 75 72 65 20 77 68 69 63 68 20 64 65 66 ucture which def
14d0: 69 6e 65 73 20 74 68 65 0a 09 09 09 09 20 2a 20 ines the..... *
14e0: 62 65 68 61 76 69 6f 75 72 20 6f 66 20 74 68 69 behaviour of thi
14f0: 73 20 74 61 62 6c 65 2e 20 2a 2f 0a 7b 0a 23 69 s table. */.{.#i
1500: 66 20 28 54 43 4c 5f 53 4d 41 4c 4c 5f 48 41 53 f (TCL_SMALL_HAS
1510: 48 5f 54 41 42 4c 45 20 21 3d 20 34 29 0a 20 20 H_TABLE != 4).
1520: 20 20 54 63 6c 5f 50 61 6e 69 63 28 22 54 63 6c Tcl_Panic("Tcl
1530: 5f 49 6e 69 74 43 75 73 74 6f 6d 48 61 73 68 54 _InitCustomHashT
1540: 61 62 6c 65 3a 20 54 43 4c 5f 53 4d 41 4c 4c 5f able: TCL_SMALL_
1550: 48 41 53 48 5f 54 41 42 4c 45 20 69 73 20 25 64 HASH_TABLE is %d
1560: 2c 20 6e 6f 74 20 34 22 2c 0a 09 20 20 20 20 54 , not 4",.. T
1570: 43 4c 5f 53 4d 41 4c 4c 5f 48 41 53 48 5f 54 41 CL_SMALL_HASH_TA
1580: 42 4c 45 29 3b 0a 23 65 6e 64 69 66 0a 0a 20 20 BLE);.#endif..
1590: 20 20 74 61 62 6c 65 50 74 72 2d 3e 62 75 63 6b tablePtr->buck
15a0: 65 74 73 20 3d 20 74 61 62 6c 65 50 74 72 2d 3e ets = tablePtr->
15b0: 73 74 61 74 69 63 42 75 63 6b 65 74 73 3b 0a 20 staticBuckets;.
15c0: 20 20 20 74 61 62 6c 65 50 74 72 2d 3e 73 74 61 tablePtr->sta
15d0: 74 69 63 42 75 63 6b 65 74 73 5b 30 5d 20 3d 20 ticBuckets[0] =
15e0: 74 61 62 6c 65 50 74 72 2d 3e 73 74 61 74 69 63 tablePtr->static
15f0: 42 75 63 6b 65 74 73 5b 31 5d 20 3d 20 30 3b 0a Buckets[1] = 0;.
1600: 20 20 20 20 74 61 62 6c 65 50 74 72 2d 3e 73 74 tablePtr->st
1610: 61 74 69 63 42 75 63 6b 65 74 73 5b 32 5d 20 3d aticBuckets[2] =
1620: 20 74 61 62 6c 65 50 74 72 2d 3e 73 74 61 74 69 tablePtr->stati
1630: 63 42 75 63 6b 65 74 73 5b 33 5d 20 3d 20 30 3b cBuckets[3] = 0;
1640: 0a 20 20 20 20 74 61 62 6c 65 50 74 72 2d 3e 6e . tablePtr->n
1650: 75 6d 42 75 63 6b 65 74 73 20 3d 20 54 43 4c 5f umBuckets = TCL_
1660: 53 4d 41 4c 4c 5f 48 41 53 48 5f 54 41 42 4c 45 SMALL_HASH_TABLE
1670: 3b 0a 20 20 20 20 74 61 62 6c 65 50 74 72 2d 3e ;. tablePtr->
1680: 6e 75 6d 45 6e 74 72 69 65 73 20 3d 20 30 3b 0a numEntries = 0;.
1690: 20 20 20 20 74 61 62 6c 65 50 74 72 2d 3e 72 65 tablePtr->re
16a0: 62 75 69 6c 64 53 69 7a 65 20 3d 20 54 43 4c 5f buildSize = TCL_
16b0: 53 4d 41 4c 4c 5f 48 41 53 48 5f 54 41 42 4c 45 SMALL_HASH_TABLE
16c0: 2a 52 45 42 55 49 4c 44 5f 4d 55 4c 54 49 50 4c *REBUILD_MULTIPL
16d0: 49 45 52 3b 0a 20 20 20 20 74 61 62 6c 65 50 74 IER;. tablePt
16e0: 72 2d 3e 64 6f 77 6e 53 68 69 66 74 20 3d 20 32 r->downShift = 2
16f0: 38 3b 0a 20 20 20 20 74 61 62 6c 65 50 74 72 2d 8;. tablePtr-
1700: 3e 6d 61 73 6b 20 3d 20 33 3b 0a 20 20 20 20 74 >mask = 3;. t
1710: 61 62 6c 65 50 74 72 2d 3e 6b 65 79 54 79 70 65 ablePtr->keyType
1720: 20 3d 20 6b 65 79 54 79 70 65 3b 0a 20 20 20 20 = keyType;.
1730: 74 61 62 6c 65 50 74 72 2d 3e 66 69 6e 64 50 72 tablePtr->findPr
1740: 6f 63 20 3d 20 46 69 6e 64 48 61 73 68 45 6e 74 oc = FindHashEnt
1750: 72 79 3b 0a 20 20 20 20 74 61 62 6c 65 50 74 72 ry;. tablePtr
1760: 2d 3e 63 72 65 61 74 65 50 72 6f 63 20 3d 20 43 ->createProc = C
1770: 72 65 61 74 65 48 61 73 68 45 6e 74 72 79 3b 0a reateHashEntry;.
1780: 0a 20 20 20 20 69 66 20 28 74 79 70 65 50 74 72 . if (typePtr
1790: 20 3d 3d 20 4e 55 4c 4c 29 20 7b 0a 09 2f 2a 0a == NULL) {../*.
17a0: 09 20 2a 20 54 68 65 20 63 61 6c 6c 65 72 20 68 . * The caller h
17b0: 61 73 20 62 65 65 6e 20 72 65 62 75 69 6c 74 20 as been rebuilt
17c0: 73 6f 20 74 68 65 20 68 61 73 68 20 74 61 62 6c so the hash tabl
17d0: 65 20 69 73 20 61 6e 20 65 78 74 65 6e 64 65 64 e is an extended
17e0: 0a 09 20 2a 20 76 65 72 73 69 6f 6e 2e 0a 09 20 .. * version...
17f0: 2a 2f 0a 20 20 20 20 7d 20 65 6c 73 65 20 69 66 */. } else if
1800: 20 28 74 79 70 65 50 74 72 20 21 3d 20 28 54 63 (typePtr != (Tc
1810: 6c 5f 48 61 73 68 4b 65 79 54 79 70 65 20 2a 29 l_HashKeyType *)
1820: 20 2d 31 29 20 7b 0a 09 2f 2a 0a 09 20 2a 20 54 -1) {../*.. * T
1830: 68 65 20 63 61 6c 6c 65 72 20 69 73 20 72 65 71 he caller is req
1840: 75 65 73 74 69 6e 67 20 61 20 63 75 73 74 6f 6d uesting a custom
1850: 69 7a 65 64 20 68 61 73 68 20 74 61 62 6c 65 20 ized hash table
1860: 73 6f 20 69 74 20 6d 75 73 74 20 62 65 20 61 6e so it must be an
1870: 0a 09 20 2a 20 65 78 74 65 6e 64 65 64 20 76 65 .. * extended ve
1880: 72 73 69 6f 6e 2e 0a 09 20 2a 2f 0a 0a 09 74 61 rsion... */...ta
1890: 62 6c 65 50 74 72 2d 3e 74 79 70 65 50 74 72 20 blePtr->typePtr
18a0: 3d 20 74 79 70 65 50 74 72 3b 0a 20 20 20 20 7d = typePtr;. }
18b0: 20 65 6c 73 65 20 7b 0a 09 2f 2a 0a 09 20 2a 20 else {../*.. *
18c0: 54 68 65 20 63 61 6c 6c 65 72 20 68 61 73 20 6e The caller has n
18d0: 6f 74 20 62 65 65 6e 20 72 65 62 75 69 6c 74 20 ot been rebuilt
18e0: 73 6f 20 74 68 65 20 68 61 73 68 20 74 61 62 6c so the hash tabl
18f0: 65 20 69 73 20 6e 6f 74 20 65 78 74 65 6e 64 65 e is not extende
1900: 64 2e 0a 09 20 2a 2f 0a 20 20 20 20 7d 0a 7d 0a d... */. }.}.
1910: 0c 0a 2f 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d ../*. *---------
1920: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1930: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1940: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1950: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a -------------. *
1960: 0a 20 2a 20 54 63 6c 5f 46 69 6e 64 48 61 73 68 . * Tcl_FindHash
1970: 45 6e 74 72 79 20 2d 2d 0a 20 2a 0a 20 2a 09 47 Entry --. *. *.G
1980: 69 76 65 6e 20 61 20 68 61 73 68 20 74 61 62 6c iven a hash tabl
1990: 65 20 66 69 6e 64 20 74 68 65 20 65 6e 74 72 79 e find the entry
19a0: 20 77 69 74 68 20 61 20 6d 61 74 63 68 69 6e 67 with a matching
19b0: 20 6b 65 79 2e 0a 20 2a 0a 20 2a 20 52 65 73 75 key.. *. * Resu
19c0: 6c 74 73 3a 0a 20 2a 09 54 68 65 20 72 65 74 75 lts:. *.The retu
19d0: 72 6e 20 76 61 6c 75 65 20 69 73 20 61 20 74 6f rn value is a to
19e0: 6b 65 6e 20 66 6f 72 20 74 68 65 20 6d 61 74 63 ken for the matc
19f0: 68 69 6e 67 20 65 6e 74 72 79 20 69 6e 20 74 68 hing entry in th
1a00: 65 20 68 61 73 68 20 74 61 62 6c 65 2c 0a 20 2a e hash table,. *
1a10: 09 6f 72 20 4e 55 4c 4c 20 69 66 20 74 68 65 72 .or NULL if ther
1a20: 65 20 77 61 73 20 6e 6f 20 6d 61 74 63 68 69 6e e was no matchin
1a30: 67 20 65 6e 74 72 79 2e 0a 20 2a 0a 20 2a 20 53 g entry.. *. * S
1a40: 69 64 65 20 65 66 66 65 63 74 73 3a 0a 20 2a 09 ide effects:. *.
1a50: 4e 6f 6e 65 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d None.. *. *-----
1a60: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1a70: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1a80: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1a90: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1aa0: 2d 0a 20 2a 2f 0a 0a 54 63 6c 5f 48 61 73 68 45 -. */..Tcl_HashE
1ab0: 6e 74 72 79 20 2a 0a 54 63 6c 5f 46 69 6e 64 48 ntry *.Tcl_FindH
1ac0: 61 73 68 45 6e 74 72 79 28 0a 20 20 20 20 54 63 ashEntry(. Tc
1ad0: 6c 5f 48 61 73 68 54 61 62 6c 65 20 2a 74 61 62 l_HashTable *tab
1ae0: 6c 65 50 74 72 2c 09 2f 2a 20 54 61 62 6c 65 20 lePtr,./* Table
1af0: 69 6e 20 77 68 69 63 68 20 74 6f 20 6c 6f 6f 6b in which to look
1b00: 75 70 20 65 6e 74 72 79 2e 20 2a 2f 0a 20 20 20 up entry. */.
1b10: 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 6b 65 79 const void *key
1b20: 29 09 09 2f 2a 20 4b 65 79 20 74 6f 20 75 73 65 )../* Key to use
1b30: 20 74 6f 20 66 69 6e 64 20 6d 61 74 63 68 69 6e to find matchin
1b40: 67 20 65 6e 74 72 79 2e 20 2a 2f 0a 7b 0a 20 20 g entry. */.{.
1b50: 20 20 72 65 74 75 72 6e 20 28 2a 28 28 74 61 62 return (*((tab
1b60: 6c 65 50 74 72 29 2d 3e 66 69 6e 64 50 72 6f 63 lePtr)->findProc
1b70: 29 29 28 74 61 62 6c 65 50 74 72 2c 20 6b 65 79 ))(tablePtr, key
1b80: 29 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 54 63 6c );.}..static Tcl
1b90: 5f 48 61 73 68 45 6e 74 72 79 20 2a 0a 46 69 6e _HashEntry *.Fin
1ba0: 64 48 61 73 68 45 6e 74 72 79 28 0a 20 20 20 20 dHashEntry(.
1bb0: 54 63 6c 5f 48 61 73 68 54 61 62 6c 65 20 2a 74 Tcl_HashTable *t
1bc0: 61 62 6c 65 50 74 72 2c 09 2f 2a 20 54 61 62 6c ablePtr,./* Tabl
1bd0: 65 20 69 6e 20 77 68 69 63 68 20 74 6f 20 6c 6f e in which to lo
1be0: 6f 6b 75 70 20 65 6e 74 72 79 2e 20 2a 2f 0a 20 okup entry. */.
1bf0: 20 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 6b const char *k
1c00: 65 79 29 09 09 2f 2a 20 4b 65 79 20 74 6f 20 75 ey)../* Key to u
1c10: 73 65 20 74 6f 20 66 69 6e 64 20 6d 61 74 63 68 se to find match
1c20: 69 6e 67 20 65 6e 74 72 79 2e 20 2a 2f 0a 7b 0a ing entry. */.{.
1c30: 20 20 20 20 72 65 74 75 72 6e 20 43 72 65 61 74 return Creat
1c40: 65 48 61 73 68 45 6e 74 72 79 28 74 61 62 6c 65 eHashEntry(table
1c50: 50 74 72 2c 20 6b 65 79 2c 20 4e 55 4c 4c 29 3b Ptr, key, NULL);
1c60: 0a 7d 0a 0a 0c 0a 2f 2a 0a 20 2a 2d 2d 2d 2d 2d .}..../*. *-----
1c70: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1c80: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1c90: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1ca0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1cb0: 2d 0a 20 2a 0a 20 2a 20 54 63 6c 5f 43 72 65 61 -. *. * Tcl_Crea
1cc0: 74 65 48 61 73 68 45 6e 74 72 79 20 2d 2d 0a 20 teHashEntry --.
1cd0: 2a 0a 20 2a 09 47 69 76 65 6e 20 61 20 68 61 73 *. *.Given a has
1ce0: 68 20 74 61 62 6c 65 20 77 69 74 68 20 73 74 72 h table with str
1cf0: 69 6e 67 20 6b 65 79 73 2c 20 61 6e 64 20 61 20 ing keys, and a
1d00: 73 74 72 69 6e 67 20 6b 65 79 2c 20 66 69 6e 64 string key, find
1d10: 20 74 68 65 20 65 6e 74 72 79 0a 20 2a 09 77 69 the entry. *.wi
1d20: 74 68 20 61 20 6d 61 74 63 68 69 6e 67 20 6b 65 th a matching ke
1d30: 79 2e 20 49 66 20 74 68 65 72 65 20 69 73 20 6e y. If there is n
1d40: 6f 20 6d 61 74 63 68 69 6e 67 20 65 6e 74 72 79 o matching entry
1d50: 2c 20 74 68 65 6e 20 63 72 65 61 74 65 20 61 20 , then create a
1d60: 6e 65 77 0a 20 2a 09 65 6e 74 72 79 20 74 68 61 new. *.entry tha
1d70: 74 20 64 6f 65 73 20 6d 61 74 63 68 2e 0a 20 2a t does match.. *
1d80: 0a 20 2a 20 52 65 73 75 6c 74 73 3a 0a 20 2a 09 . * Results:. *.
1d90: 54 68 65 20 72 65 74 75 72 6e 20 76 61 6c 75 65 The return value
1da0: 20 69 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f is a pointer to
1db0: 20 74 68 65 20 6d 61 74 63 68 69 6e 67 20 65 6e the matching en
1dc0: 74 72 79 2e 20 49 66 20 74 68 69 73 20 69 73 20 try. If this is
1dd0: 61 0a 20 2a 09 6e 65 77 6c 79 2d 63 72 65 61 74 a. *.newly-creat
1de0: 65 64 20 65 6e 74 72 79 2c 20 74 68 65 6e 20 2a ed entry, then *
1df0: 6e 65 77 50 74 72 20 77 69 6c 6c 20 62 65 20 73 newPtr will be s
1e00: 65 74 20 74 6f 20 61 20 6e 6f 6e 2d 7a 65 72 6f et to a non-zero
1e10: 20 76 61 6c 75 65 3b 0a 20 2a 09 6f 74 68 65 72 value;. *.other
1e20: 77 69 73 65 20 2a 6e 65 77 50 74 72 20 77 69 6c wise *newPtr wil
1e30: 6c 20 62 65 20 73 65 74 20 74 6f 20 30 2e 20 49 l be set to 0. I
1e40: 66 20 74 68 69 73 20 69 73 20 61 20 6e 65 77 20 f this is a new
1e50: 65 6e 74 72 79 20 74 68 65 20 76 61 6c 75 65 0a entry the value.
1e60: 20 2a 09 73 74 6f 72 65 64 20 69 6e 20 74 68 65 *.stored in the
1e70: 20 65 6e 74 72 79 20 77 69 6c 6c 20 69 6e 69 74 entry will init
1e80: 69 61 6c 6c 79 20 62 65 20 30 2e 0a 20 2a 0a 20 ially be 0.. *.
1e90: 2a 20 53 69 64 65 20 65 66 66 65 63 74 73 3a 0a * Side effects:.
1ea0: 20 2a 09 41 20 6e 65 77 20 65 6e 74 72 79 20 6d *.A new entry m
1eb0: 61 79 20 62 65 20 61 64 64 65 64 20 74 6f 20 74 ay be added to t
1ec0: 68 65 20 68 61 73 68 20 74 61 62 6c 65 2e 0a 20 he hash table..
1ed0: 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *. *------------
1ee0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1ef0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1f00: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1f10: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 2f 0a 0a ----------. */..
1f20: 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 2a 0a Tcl_HashEntry *.
1f30: 54 63 6c 5f 43 72 65 61 74 65 48 61 73 68 45 6e Tcl_CreateHashEn
1f40: 74 72 79 28 0a 20 20 20 20 54 63 6c 5f 48 61 73 try(. Tcl_Has
1f50: 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 50 74 72 hTable *tablePtr
1f60: 2c 09 2f 2a 20 54 61 62 6c 65 20 69 6e 20 77 68 ,./* Table in wh
1f70: 69 63 68 20 74 6f 20 6c 6f 6f 6b 75 70 20 65 6e ich to lookup en
1f80: 74 72 79 2e 20 2a 2f 0a 20 20 20 20 63 6f 6e 73 try. */. cons
1f90: 74 20 76 6f 69 64 20 2a 6b 65 79 2c 09 09 2f 2a t void *key,../*
1fa0: 20 4b 65 79 20 74 6f 20 75 73 65 20 74 6f 20 66 Key to use to f
1fb0: 69 6e 64 20 6f 72 20 63 72 65 61 74 65 20 6d 61 ind or create ma
1fc0: 74 63 68 69 6e 67 0a 09 09 09 09 20 2a 20 65 6e tching..... * en
1fd0: 74 72 79 2e 20 2a 2f 0a 20 20 20 20 69 6e 74 20 try. */. int
1fe0: 2a 6e 65 77 50 74 72 29 09 09 2f 2a 20 53 74 6f *newPtr)../* Sto
1ff0: 72 65 20 69 6e 66 6f 20 68 65 72 65 20 74 65 6c re info here tel
2000: 6c 69 6e 67 20 77 68 65 74 68 65 72 20 61 20 6e ling whether a n
2010: 65 77 20 65 6e 74 72 79 0a 09 09 09 09 20 2a 20 ew entry..... *
2020: 77 61 73 20 63 72 65 61 74 65 64 2e 20 2a 2f 0a was created. */.
2030: 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 28 2a 28 {. return (*(
2040: 28 74 61 62 6c 65 50 74 72 29 2d 3e 63 72 65 61 (tablePtr)->crea
2050: 74 65 50 72 6f 63 29 29 28 74 61 62 6c 65 50 74 teProc))(tablePt
2060: 72 2c 20 6b 65 79 2c 20 6e 65 77 50 74 72 29 3b r, key, newPtr);
2070: 0a 7d 0a 0a 73 74 61 74 69 63 20 54 63 6c 5f 48 .}..static Tcl_H
2080: 61 73 68 45 6e 74 72 79 20 2a 0a 43 72 65 61 74 ashEntry *.Creat
2090: 65 48 61 73 68 45 6e 74 72 79 28 0a 20 20 20 20 eHashEntry(.
20a0: 54 63 6c 5f 48 61 73 68 54 61 62 6c 65 20 2a 74 Tcl_HashTable *t
20b0: 61 62 6c 65 50 74 72 2c 09 2f 2a 20 54 61 62 6c ablePtr,./* Tabl
20c0: 65 20 69 6e 20 77 68 69 63 68 20 74 6f 20 6c 6f e in which to lo
20d0: 6f 6b 75 70 20 65 6e 74 72 79 2e 20 2a 2f 0a 20 okup entry. */.
20e0: 20 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 6b const char *k
20f0: 65 79 2c 09 09 2f 2a 20 4b 65 79 20 74 6f 20 75 ey,../* Key to u
2100: 73 65 20 74 6f 20 66 69 6e 64 20 6f 72 20 63 72 se to find or cr
2110: 65 61 74 65 20 6d 61 74 63 68 69 6e 67 0a 09 09 eate matching...
2120: 09 09 20 2a 20 65 6e 74 72 79 2e 20 2a 2f 0a 20 .. * entry. */.
2130: 20 20 20 69 6e 74 20 2a 6e 65 77 50 74 72 29 09 int *newPtr).
2140: 09 2f 2a 20 53 74 6f 72 65 20 69 6e 66 6f 20 68 ./* Store info h
2150: 65 72 65 20 74 65 6c 6c 69 6e 67 20 77 68 65 74 ere telling whet
2160: 68 65 72 20 61 20 6e 65 77 20 65 6e 74 72 79 0a her a new entry.
2170: 09 09 09 09 20 2a 20 77 61 73 20 63 72 65 61 74 .... * was creat
2180: 65 64 2e 20 2a 2f 0a 7b 0a 20 20 20 20 54 63 6c ed. */.{. Tcl
2190: 5f 48 61 73 68 45 6e 74 72 79 20 2a 68 50 74 72 _HashEntry *hPtr
21a0: 3b 0a 20 20 20 20 63 6f 6e 73 74 20 54 63 6c 5f ;. const Tcl_
21b0: 48 61 73 68 4b 65 79 54 79 70 65 20 2a 74 79 70 HashKeyType *typ
21c0: 65 50 74 72 3b 0a 20 20 20 20 75 6e 73 69 67 6e ePtr;. unsign
21d0: 65 64 20 69 6e 74 20 68 61 73 68 3b 0a 20 20 20 ed int hash;.
21e0: 20 69 6e 74 20 69 6e 64 65 78 3b 0a 0a 20 20 20 int index;..
21f0: 20 69 66 20 28 74 61 62 6c 65 50 74 72 2d 3e 6b if (tablePtr->k
2200: 65 79 54 79 70 65 20 3d 3d 20 54 43 4c 5f 53 54 eyType == TCL_ST
2210: 52 49 4e 47 5f 4b 45 59 53 29 20 7b 0a 09 74 79 RING_KEYS) {..ty
2220: 70 65 50 74 72 20 3d 20 26 74 63 6c 53 74 72 69 pePtr = &tclStri
2230: 6e 67 48 61 73 68 4b 65 79 54 79 70 65 3b 0a 20 ngHashKeyType;.
2240: 20 20 20 7d 20 65 6c 73 65 20 69 66 20 28 74 61 } else if (ta
2250: 62 6c 65 50 74 72 2d 3e 6b 65 79 54 79 70 65 20 blePtr->keyType
2260: 3d 3d 20 54 43 4c 5f 4f 4e 45 5f 57 4f 52 44 5f == TCL_ONE_WORD_
2270: 4b 45 59 53 29 20 7b 0a 09 74 79 70 65 50 74 72 KEYS) {..typePtr
2280: 20 3d 20 26 74 63 6c 4f 6e 65 57 6f 72 64 48 61 = &tclOneWordHa
2290: 73 68 4b 65 79 54 79 70 65 3b 0a 20 20 20 20 7d shKeyType;. }
22a0: 20 65 6c 73 65 20 69 66 20 28 74 61 62 6c 65 50 else if (tableP
22b0: 74 72 2d 3e 6b 65 79 54 79 70 65 20 3d 3d 20 54 tr->keyType == T
22c0: 43 4c 5f 43 55 53 54 4f 4d 5f 54 59 50 45 5f 4b CL_CUSTOM_TYPE_K
22d0: 45 59 53 0a 09 20 20 20 20 7c 7c 20 74 61 62 6c EYS.. || tabl
22e0: 65 50 74 72 2d 3e 6b 65 79 54 79 70 65 20 3d 3d ePtr->keyType ==
22f0: 20 54 43 4c 5f 43 55 53 54 4f 4d 5f 50 54 52 5f TCL_CUSTOM_PTR_
2300: 4b 45 59 53 29 20 7b 0a 09 74 79 70 65 50 74 72 KEYS) {..typePtr
2310: 20 3d 20 74 61 62 6c 65 50 74 72 2d 3e 74 79 70 = tablePtr->typ
2320: 65 50 74 72 3b 0a 20 20 20 20 7d 20 65 6c 73 65 ePtr;. } else
2330: 20 7b 0a 09 74 79 70 65 50 74 72 20 3d 20 26 74 {..typePtr = &t
2340: 63 6c 41 72 72 61 79 48 61 73 68 4b 65 79 54 79 clArrayHashKeyTy
2350: 70 65 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20 69 pe;. }.. i
2360: 66 20 28 74 79 70 65 50 74 72 2d 3e 68 61 73 68 f (typePtr->hash
2370: 4b 65 79 50 72 6f 63 29 20 7b 0a 09 68 61 73 68 KeyProc) {..hash
2380: 20 3d 20 74 79 70 65 50 74 72 2d 3e 68 61 73 68 = typePtr->hash
2390: 4b 65 79 50 72 6f 63 28 74 61 62 6c 65 50 74 72 KeyProc(tablePtr
23a0: 2c 20 28 76 6f 69 64 20 2a 29 20 6b 65 79 29 3b , (void *) key);
23b0: 0a 09 69 66 20 28 74 79 70 65 50 74 72 2d 3e 66 ..if (typePtr->f
23c0: 6c 61 67 73 20 26 20 54 43 4c 5f 48 41 53 48 5f lags & TCL_HASH_
23d0: 4b 45 59 5f 52 41 4e 44 4f 4d 49 5a 45 5f 48 41 KEY_RANDOMIZE_HA
23e0: 53 48 29 20 7b 0a 09 20 20 20 20 69 6e 64 65 78 SH) {.. index
23f0: 20 3d 20 52 41 4e 44 4f 4d 5f 49 4e 44 45 58 28 = RANDOM_INDEX(
2400: 74 61 62 6c 65 50 74 72 2c 20 68 61 73 68 29 3b tablePtr, hash);
2410: 0a 09 7d 20 65 6c 73 65 20 7b 0a 09 20 20 20 20 ..} else {..
2420: 69 6e 64 65 78 20 3d 20 68 61 73 68 20 26 20 74 index = hash & t
2430: 61 62 6c 65 50 74 72 2d 3e 6d 61 73 6b 3b 0a 09 ablePtr->mask;..
2440: 7d 0a 20 20 20 20 7d 20 65 6c 73 65 20 7b 0a 09 }. } else {..
2450: 68 61 73 68 20 3d 20 50 54 52 32 55 49 4e 54 28 hash = PTR2UINT(
2460: 6b 65 79 29 3b 0a 09 69 6e 64 65 78 20 3d 20 52 key);..index = R
2470: 41 4e 44 4f 4d 5f 49 4e 44 45 58 28 74 61 62 6c ANDOM_INDEX(tabl
2480: 65 50 74 72 2c 20 68 61 73 68 29 3b 0a 20 20 20 ePtr, hash);.
2490: 20 7d 0a 0a 20 20 20 20 2f 2a 0a 20 20 20 20 20 }.. /*.
24a0: 2a 20 53 65 61 72 63 68 20 61 6c 6c 20 6f 66 20 * Search all of
24b0: 74 68 65 20 65 6e 74 72 69 65 73 20 69 6e 20 74 the entries in t
24c0: 68 65 20 61 70 70 72 6f 70 72 69 61 74 65 20 62 he appropriate b
24d0: 75 63 6b 65 74 2e 0a 20 20 20 20 20 2a 2f 0a 0a ucket.. */..
24e0: 20 20 20 20 69 66 20 28 74 79 70 65 50 74 72 2d if (typePtr-
24f0: 3e 63 6f 6d 70 61 72 65 4b 65 79 73 50 72 6f 63 >compareKeysProc
2500: 29 20 7b 0a 09 54 63 6c 5f 43 6f 6d 70 61 72 65 ) {..Tcl_Compare
2510: 48 61 73 68 4b 65 79 73 50 72 6f 63 20 2a 63 6f HashKeysProc *co
2520: 6d 70 61 72 65 4b 65 79 73 50 72 6f 63 20 3d 20 mpareKeysProc =
2530: 74 79 70 65 50 74 72 2d 3e 63 6f 6d 70 61 72 65 typePtr->compare
2540: 4b 65 79 73 50 72 6f 63 3b 0a 09 69 66 20 28 74 KeysProc;..if (t
2550: 79 70 65 50 74 72 2d 3e 66 6c 61 67 73 20 26 20 ypePtr->flags &
2560: 54 43 4c 5f 48 41 53 48 5f 4b 45 59 5f 44 49 52 TCL_HASH_KEY_DIR
2570: 45 43 54 5f 43 4f 4d 50 41 52 45 29 20 7b 0a 09 ECT_COMPARE) {..
2580: 20 20 20 20 66 6f 72 20 28 68 50 74 72 20 3d 20 for (hPtr =
2590: 74 61 62 6c 65 50 74 72 2d 3e 62 75 63 6b 65 74 tablePtr->bucket
25a0: 73 5b 69 6e 64 65 78 5d 3b 20 68 50 74 72 20 21 s[index]; hPtr !
25b0: 3d 20 4e 55 4c 4c 3b 0a 09 09 20 20 20 20 68 50 = NULL;... hP
25c0: 74 72 20 3d 20 68 50 74 72 2d 3e 6e 65 78 74 50 tr = hPtr->nextP
25d0: 74 72 29 20 7b 0a 23 69 66 20 54 43 4c 5f 48 41 tr) {.#if TCL_HA
25e0: 53 48 5f 4b 45 59 5f 53 54 4f 52 45 5f 48 41 53 SH_KEY_STORE_HAS
25f0: 48 0a 09 09 69 66 20 28 68 61 73 68 20 21 3d 20 H...if (hash !=
2600: 50 54 52 32 55 49 4e 54 28 68 50 74 72 2d 3e 68 PTR2UINT(hPtr->h
2610: 61 73 68 29 29 20 7b 0a 09 09 20 20 20 20 63 6f ash)) {... co
2620: 6e 74 69 6e 75 65 3b 0a 09 09 7d 0a 23 65 6e 64 ntinue;...}.#end
2630: 69 66 0a 09 09 2f 2a 20 69 66 20 6b 65 79 73 20 if.../* if keys
2640: 70 6f 69 6e 74 65 72 73 20 6f 72 20 76 61 6c 75 pointers or valu
2650: 65 73 20 61 72 65 20 65 71 75 61 6c 20 2a 2f 0a es are equal */.
2660: 09 09 69 66 20 28 28 6b 65 79 20 3d 3d 20 68 50 ..if ((key == hP
2670: 74 72 2d 3e 6b 65 79 2e 6f 6e 65 57 6f 72 64 56 tr->key.oneWordV
2680: 61 6c 75 65 29 0a 09 09 20 20 20 20 7c 7c 20 63 alue)... || c
2690: 6f 6d 70 61 72 65 4b 65 79 73 50 72 6f 63 28 28 ompareKeysProc((
26a0: 76 6f 69 64 20 2a 29 20 6b 65 79 2c 20 68 50 74 void *) key, hPt
26b0: 72 29 0a 09 09 29 20 7b 0a 09 09 20 20 20 20 69 r)...) {... i
26c0: 66 20 28 6e 65 77 50 74 72 29 20 7b 0a 09 09 09 f (newPtr) {....
26d0: 2a 6e 65 77 50 74 72 20 3d 20 30 3b 0a 09 09 20 *newPtr = 0;...
26e0: 20 20 20 7d 0a 09 09 20 20 20 20 72 65 74 75 72 }... retur
26f0: 6e 20 68 50 74 72 3b 0a 09 09 7d 0a 09 20 20 20 n hPtr;...}..
2700: 20 7d 0a 09 7d 20 65 6c 73 65 20 7b 20 2f 2a 20 }..} else { /*
2710: 6e 6f 20 64 69 72 65 63 74 20 63 6f 6d 70 61 72 no direct compar
2720: 65 20 2d 20 63 6f 6d 70 61 72 65 20 6b 65 79 20 e - compare key
2730: 61 64 64 72 65 73 73 65 73 20 6f 6e 6c 79 20 2a addresses only *
2740: 2f 0a 09 20 20 20 20 66 6f 72 20 28 68 50 74 72 /.. for (hPtr
2750: 20 3d 20 74 61 62 6c 65 50 74 72 2d 3e 62 75 63 = tablePtr->buc
2760: 6b 65 74 73 5b 69 6e 64 65 78 5d 3b 20 68 50 74 kets[index]; hPt
2770: 72 20 21 3d 20 4e 55 4c 4c 3b 0a 09 09 20 20 20 r != NULL;...
2780: 20 68 50 74 72 20 3d 20 68 50 74 72 2d 3e 6e 65 hPtr = hPtr->ne
2790: 78 74 50 74 72 29 20 7b 0a 23 69 66 20 54 43 4c xtPtr) {.#if TCL
27a0: 5f 48 41 53 48 5f 4b 45 59 5f 53 54 4f 52 45 5f _HASH_KEY_STORE_
27b0: 48 41 53 48 0a 09 09 69 66 20 28 68 61 73 68 20 HASH...if (hash
27c0: 21 3d 20 50 54 52 32 55 49 4e 54 28 68 50 74 72 != PTR2UINT(hPtr
27d0: 2d 3e 68 61 73 68 29 29 20 7b 0a 09 09 20 20 20 ->hash)) {...
27e0: 20 63 6f 6e 74 69 6e 75 65 3b 0a 09 09 7d 0a 23 continue;...}.#
27f0: 65 6e 64 69 66 0a 09 09 2f 2a 20 69 66 20 6e 65 endif.../* if ne
2800: 65 64 6c 65 20 70 6f 69 6e 74 65 72 20 65 71 75 edle pointer equ
2810: 61 6c 73 20 63 6f 6e 74 65 6e 74 20 70 6f 69 6e als content poin
2820: 74 65 72 20 6f 72 20 76 61 6c 75 65 73 20 65 71 ter or values eq
2830: 75 61 6c 20 2a 2f 0a 09 09 69 66 20 28 28 6b 65 ual */...if ((ke
2840: 79 20 3d 3d 20 68 50 74 72 2d 3e 6b 65 79 2e 73 y == hPtr->key.s
2850: 74 72 69 6e 67 29 0a 09 09 20 20 20 20 7c 7c 20 tring)... ||
2860: 63 6f 6d 70 61 72 65 4b 65 79 73 50 72 6f 63 28 compareKeysProc(
2870: 28 76 6f 69 64 20 2a 29 20 6b 65 79 2c 20 68 50 (void *) key, hP
2880: 74 72 29 0a 09 09 29 20 7b 0a 09 09 20 20 20 20 tr)...) {...
2890: 69 66 20 28 6e 65 77 50 74 72 29 20 7b 0a 09 09 if (newPtr) {...
28a0: 09 2a 6e 65 77 50 74 72 20 3d 20 30 3b 0a 09 09 .*newPtr = 0;...
28b0: 20 20 20 20 7d 0a 09 09 20 20 20 20 72 65 74 75 }... retu
28c0: 72 6e 20 68 50 74 72 3b 0a 09 09 7d 0a 09 20 20 rn hPtr;...}..
28d0: 20 20 7d 0a 09 7d 0a 20 20 20 20 7d 20 65 6c 73 }..}. } els
28e0: 65 20 7b 0a 09 66 6f 72 20 28 68 50 74 72 20 3d e {..for (hPtr =
28f0: 20 74 61 62 6c 65 50 74 72 2d 3e 62 75 63 6b 65 tablePtr->bucke
2900: 74 73 5b 69 6e 64 65 78 5d 3b 20 68 50 74 72 20 ts[index]; hPtr
2910: 21 3d 20 4e 55 4c 4c 3b 0a 09 09 68 50 74 72 20 != NULL;...hPtr
2920: 3d 20 68 50 74 72 2d 3e 6e 65 78 74 50 74 72 29 = hPtr->nextPtr)
2930: 20 7b 0a 23 69 66 20 54 43 4c 5f 48 41 53 48 5f {.#if TCL_HASH_
2940: 4b 45 59 5f 53 54 4f 52 45 5f 48 41 53 48 0a 09 KEY_STORE_HASH..
2950: 20 20 20 20 69 66 20 28 68 61 73 68 20 21 3d 20 if (hash !=
2960: 50 54 52 32 55 49 4e 54 28 68 50 74 72 2d 3e 68 PTR2UINT(hPtr->h
2970: 61 73 68 29 29 20 7b 0a 09 09 63 6f 6e 74 69 6e ash)) {...contin
2980: 75 65 3b 0a 09 20 20 20 20 7d 0a 23 65 6e 64 69 ue;.. }.#endi
2990: 66 0a 09 20 20 20 20 69 66 20 28 6b 65 79 20 3d f.. if (key =
29a0: 3d 20 68 50 74 72 2d 3e 6b 65 79 2e 6f 6e 65 57 = hPtr->key.oneW
29b0: 6f 72 64 56 61 6c 75 65 29 20 7b 0a 09 09 69 66 ordValue) {...if
29c0: 20 28 6e 65 77 50 74 72 29 20 7b 0a 09 09 20 20 (newPtr) {...
29d0: 20 20 2a 6e 65 77 50 74 72 20 3d 20 30 3b 0a 09 *newPtr = 0;..
29e0: 09 7d 0a 09 09 72 65 74 75 72 6e 20 68 50 74 72 .}...return hPtr
29f0: 3b 0a 09 20 20 20 20 7d 0a 09 7d 0a 20 20 20 20 ;.. }..}.
2a00: 7d 0a 0a 20 20 20 20 69 66 20 28 21 6e 65 77 50 }.. if (!newP
2a10: 74 72 29 20 7b 0a 09 72 65 74 75 72 6e 20 4e 55 tr) {..return NU
2a20: 4c 4c 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f LL;. }.. /
2a30: 2a 0a 20 20 20 20 20 2a 20 45 6e 74 72 79 20 6e *. * Entry n
2a40: 6f 74 20 66 6f 75 6e 64 2e 20 41 64 64 20 61 20 ot found. Add a
2a50: 6e 65 77 20 6f 6e 65 20 74 6f 20 74 68 65 20 62 new one to the b
2a60: 75 63 6b 65 74 2e 0a 20 20 20 20 20 2a 2f 0a 0a ucket.. */..
2a70: 20 20 20 20 2a 6e 65 77 50 74 72 20 3d 20 31 3b *newPtr = 1;
2a80: 0a 20 20 20 20 69 66 20 28 74 79 70 65 50 74 72 . if (typePtr
2a90: 2d 3e 61 6c 6c 6f 63 45 6e 74 72 79 50 72 6f 63 ->allocEntryProc
2aa0: 29 20 7b 0a 09 68 50 74 72 20 3d 20 74 79 70 65 ) {..hPtr = type
2ab0: 50 74 72 2d 3e 61 6c 6c 6f 63 45 6e 74 72 79 50 Ptr->allocEntryP
2ac0: 72 6f 63 28 74 61 62 6c 65 50 74 72 2c 20 28 76 roc(tablePtr, (v
2ad0: 6f 69 64 20 2a 29 20 6b 65 79 29 3b 0a 20 20 20 oid *) key);.
2ae0: 20 7d 20 65 6c 73 65 20 7b 0a 09 68 50 74 72 20 } else {..hPtr
2af0: 3d 20 63 6b 61 6c 6c 6f 63 28 73 69 7a 65 6f 66 = ckalloc(sizeof
2b00: 28 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 29 29 (Tcl_HashEntry))
2b10: 3b 0a 09 68 50 74 72 2d 3e 6b 65 79 2e 6f 6e 65 ;..hPtr->key.one
2b20: 57 6f 72 64 56 61 6c 75 65 20 3d 20 28 63 68 61 WordValue = (cha
2b30: 72 20 2a 29 20 6b 65 79 3b 0a 09 68 50 74 72 2d r *) key;..hPtr-
2b40: 3e 63 6c 69 65 6e 74 44 61 74 61 20 3d 20 30 3b >clientData = 0;
2b50: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 68 50 74 72 . }.. hPtr
2b60: 2d 3e 74 61 62 6c 65 50 74 72 20 3d 20 74 61 62 ->tablePtr = tab
2b70: 6c 65 50 74 72 3b 0a 23 69 66 20 54 43 4c 5f 48 lePtr;.#if TCL_H
2b80: 41 53 48 5f 4b 45 59 5f 53 54 4f 52 45 5f 48 41 ASH_KEY_STORE_HA
2b90: 53 48 0a 20 20 20 20 68 50 74 72 2d 3e 68 61 73 SH. hPtr->has
2ba0: 68 20 3d 20 55 49 4e 54 32 50 54 52 28 68 61 73 h = UINT2PTR(has
2bb0: 68 29 3b 0a 20 20 20 20 68 50 74 72 2d 3e 6e 65 h);. hPtr->ne
2bc0: 78 74 50 74 72 20 3d 20 74 61 62 6c 65 50 74 72 xtPtr = tablePtr
2bd0: 2d 3e 62 75 63 6b 65 74 73 5b 69 6e 64 65 78 5d ->buckets[index]
2be0: 3b 0a 20 20 20 20 74 61 62 6c 65 50 74 72 2d 3e ;. tablePtr->
2bf0: 62 75 63 6b 65 74 73 5b 69 6e 64 65 78 5d 20 3d buckets[index] =
2c00: 20 68 50 74 72 3b 0a 23 65 6c 73 65 0a 20 20 20 hPtr;.#else.
2c10: 20 68 50 74 72 2d 3e 62 75 63 6b 65 74 50 74 72 hPtr->bucketPtr
2c20: 20 3d 20 26 74 61 62 6c 65 50 74 72 2d 3e 62 75 = &tablePtr->bu
2c30: 63 6b 65 74 73 5b 69 6e 64 65 78 5d 3b 0a 20 20 ckets[index];.
2c40: 20 20 68 50 74 72 2d 3e 6e 65 78 74 50 74 72 20 hPtr->nextPtr
2c50: 3d 20 2a 68 50 74 72 2d 3e 62 75 63 6b 65 74 50 = *hPtr->bucketP
2c60: 74 72 3b 0a 20 20 20 20 2a 68 50 74 72 2d 3e 62 tr;. *hPtr->b
2c70: 75 63 6b 65 74 50 74 72 20 3d 20 68 50 74 72 3b ucketPtr = hPtr;
2c80: 0a 23 65 6e 64 69 66 0a 20 20 20 20 74 61 62 6c .#endif. tabl
2c90: 65 50 74 72 2d 3e 6e 75 6d 45 6e 74 72 69 65 73 ePtr->numEntries
2ca0: 2b 2b 3b 0a 0a 20 20 20 20 2f 2a 0a 20 20 20 20 ++;.. /*.
2cb0: 20 2a 20 49 66 20 74 68 65 20 74 61 62 6c 65 20 * If the table
2cc0: 68 61 73 20 65 78 63 65 65 64 65 64 20 61 20 64 has exceeded a d
2cd0: 65 63 65 6e 74 20 73 69 7a 65 2c 20 72 65 62 75 ecent size, rebu
2ce0: 69 6c 64 20 69 74 20 77 69 74 68 20 6d 61 6e 79 ild it with many
2cf0: 20 6d 6f 72 65 0a 20 20 20 20 20 2a 20 62 75 63 more. * buc
2d00: 6b 65 74 73 2e 0a 20 20 20 20 20 2a 2f 0a 0a 20 kets.. */..
2d10: 20 20 20 69 66 20 28 74 61 62 6c 65 50 74 72 2d if (tablePtr-
2d20: 3e 6e 75 6d 45 6e 74 72 69 65 73 20 3e 3d 20 74 >numEntries >= t
2d30: 61 62 6c 65 50 74 72 2d 3e 72 65 62 75 69 6c 64 ablePtr->rebuild
2d40: 53 69 7a 65 29 20 7b 0a 09 52 65 62 75 69 6c 64 Size) {..Rebuild
2d50: 54 61 62 6c 65 28 74 61 62 6c 65 50 74 72 29 3b Table(tablePtr);
2d60: 0a 20 20 20 20 7d 0a 20 20 20 20 72 65 74 75 72 . }. retur
2d70: 6e 20 68 50 74 72 3b 0a 7d 0a 0c 0a 2f 2a 0a 20 n hPtr;.}.../*.
2d80: 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *---------------
2d90: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2da0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2db0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2dc0: 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 54 63 -------. *. * Tc
2dd0: 6c 5f 44 65 6c 65 74 65 48 61 73 68 45 6e 74 72 l_DeleteHashEntr
2de0: 79 20 2d 2d 0a 20 2a 0a 20 2a 09 52 65 6d 6f 76 y --. *. *.Remov
2df0: 65 20 61 20 73 69 6e 67 6c 65 20 65 6e 74 72 79 e a single entry
2e00: 20 66 72 6f 6d 20 61 20 68 61 73 68 20 74 61 62 from a hash tab
2e10: 6c 65 2e 0a 20 2a 0a 20 2a 20 52 65 73 75 6c 74 le.. *. * Result
2e20: 73 3a 0a 20 2a 09 4e 6f 6e 65 2e 0a 20 2a 0a 20 s:. *.None.. *.
2e30: 2a 20 53 69 64 65 20 65 66 66 65 63 74 73 3a 0a * Side effects:.
2e40: 20 2a 09 54 68 65 20 65 6e 74 72 79 20 67 69 76 *.The entry giv
2e50: 65 6e 20 62 79 20 65 6e 74 72 79 50 74 72 20 69 en by entryPtr i
2e60: 73 20 64 65 6c 65 74 65 64 20 66 72 6f 6d 20 69 s deleted from i
2e70: 74 73 20 74 61 62 6c 65 20 61 6e 64 20 73 68 6f ts table and sho
2e80: 75 6c 64 20 6e 65 76 65 72 0a 20 2a 09 61 67 61 uld never. *.aga
2e90: 69 6e 20 62 65 20 75 73 65 64 20 62 79 20 74 68 in be used by th
2ea0: 65 20 63 61 6c 6c 65 72 2e 20 49 74 20 69 73 20 e caller. It is
2eb0: 75 70 20 74 6f 20 74 68 65 20 63 61 6c 6c 65 72 up to the caller
2ec0: 20 74 6f 20 66 72 65 65 20 74 68 65 0a 20 2a 09 to free the. *.
2ed0: 63 6c 69 65 6e 74 44 61 74 61 20 66 69 65 6c 64 clientData field
2ee0: 20 6f 66 20 74 68 65 20 65 6e 74 72 79 2c 20 69 of the entry, i
2ef0: 66 20 74 68 61 74 20 69 73 20 72 65 6c 65 76 61 f that is releva
2f00: 6e 74 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d nt.. *. *-------
2f10: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2f20: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2f30: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
2f40: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
2f50: 20 2a 2f 0a 0a 76 6f 69 64 0a 54 63 6c 5f 44 65 */..void.Tcl_De
2f60: 6c 65 74 65 48 61 73 68 45 6e 74 72 79 28 0a 20 leteHashEntry(.
2f70: 20 20 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 Tcl_HashEntry
2f80: 20 2a 65 6e 74 72 79 50 74 72 29 0a 7b 0a 20 20 *entryPtr).{.
2f90: 20 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 Tcl_HashEntry
2fa0: 2a 70 72 65 76 50 74 72 3b 0a 20 20 20 20 63 6f *prevPtr;. co
2fb0: 6e 73 74 20 54 63 6c 5f 48 61 73 68 4b 65 79 54 nst Tcl_HashKeyT
2fc0: 79 70 65 20 2a 74 79 70 65 50 74 72 3b 0a 20 20 ype *typePtr;.
2fd0: 20 20 54 63 6c 5f 48 61 73 68 54 61 62 6c 65 20 Tcl_HashTable
2fe0: 2a 74 61 62 6c 65 50 74 72 3b 0a 20 20 20 20 54 *tablePtr;. T
2ff0: 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 2a 2a 62 cl_HashEntry **b
3000: 75 63 6b 65 74 50 74 72 3b 0a 23 69 66 20 54 43 ucketPtr;.#if TC
3010: 4c 5f 48 41 53 48 5f 4b 45 59 5f 53 54 4f 52 45 L_HASH_KEY_STORE
3020: 5f 48 41 53 48 0a 20 20 20 20 69 6e 74 20 69 6e _HASH. int in
3030: 64 65 78 3b 0a 23 65 6e 64 69 66 0a 0a 20 20 20 dex;.#endif..
3040: 20 74 61 62 6c 65 50 74 72 20 3d 20 65 6e 74 72 tablePtr = entr
3050: 79 50 74 72 2d 3e 74 61 62 6c 65 50 74 72 3b 0a yPtr->tablePtr;.
3060: 0a 20 20 20 20 69 66 20 28 74 61 62 6c 65 50 74 . if (tablePt
3070: 72 2d 3e 6b 65 79 54 79 70 65 20 3d 3d 20 54 43 r->keyType == TC
3080: 4c 5f 53 54 52 49 4e 47 5f 4b 45 59 53 29 20 7b L_STRING_KEYS) {
3090: 0a 09 74 79 70 65 50 74 72 20 3d 20 26 74 63 6c ..typePtr = &tcl
30a0: 53 74 72 69 6e 67 48 61 73 68 4b 65 79 54 79 70 StringHashKeyTyp
30b0: 65 3b 0a 20 20 20 20 7d 20 65 6c 73 65 20 69 66 e;. } else if
30c0: 20 28 74 61 62 6c 65 50 74 72 2d 3e 6b 65 79 54 (tablePtr->keyT
30d0: 79 70 65 20 3d 3d 20 54 43 4c 5f 4f 4e 45 5f 57 ype == TCL_ONE_W
30e0: 4f 52 44 5f 4b 45 59 53 29 20 7b 0a 09 74 79 70 ORD_KEYS) {..typ
30f0: 65 50 74 72 20 3d 20 26 74 63 6c 4f 6e 65 57 6f ePtr = &tclOneWo
3100: 72 64 48 61 73 68 4b 65 79 54 79 70 65 3b 0a 20 rdHashKeyType;.
3110: 20 20 20 7d 20 65 6c 73 65 20 69 66 20 28 74 61 } else if (ta
3120: 62 6c 65 50 74 72 2d 3e 6b 65 79 54 79 70 65 20 blePtr->keyType
3130: 3d 3d 20 54 43 4c 5f 43 55 53 54 4f 4d 5f 54 59 == TCL_CUSTOM_TY
3140: 50 45 5f 4b 45 59 53 0a 09 20 20 20 20 7c 7c 20 PE_KEYS.. ||
3150: 74 61 62 6c 65 50 74 72 2d 3e 6b 65 79 54 79 70 tablePtr->keyTyp
3160: 65 20 3d 3d 20 54 43 4c 5f 43 55 53 54 4f 4d 5f e == TCL_CUSTOM_
3170: 50 54 52 5f 4b 45 59 53 29 20 7b 0a 09 74 79 70 PTR_KEYS) {..typ
3180: 65 50 74 72 20 3d 20 74 61 62 6c 65 50 74 72 2d ePtr = tablePtr-
3190: 3e 74 79 70 65 50 74 72 3b 0a 20 20 20 20 7d 20 >typePtr;. }
31a0: 65 6c 73 65 20 7b 0a 09 74 79 70 65 50 74 72 20 else {..typePtr
31b0: 3d 20 26 74 63 6c 41 72 72 61 79 48 61 73 68 4b = &tclArrayHashK
31c0: 65 79 54 79 70 65 3b 0a 20 20 20 20 7d 0a 0a 23 eyType;. }..#
31d0: 69 66 20 54 43 4c 5f 48 41 53 48 5f 4b 45 59 5f if TCL_HASH_KEY_
31e0: 53 54 4f 52 45 5f 48 41 53 48 0a 20 20 20 20 69 STORE_HASH. i
31f0: 66 20 28 74 79 70 65 50 74 72 2d 3e 68 61 73 68 f (typePtr->hash
3200: 4b 65 79 50 72 6f 63 20 3d 3d 20 4e 55 4c 4c 0a KeyProc == NULL.
3210: 09 20 20 20 20 7c 7c 20 74 79 70 65 50 74 72 2d . || typePtr-
3220: 3e 66 6c 61 67 73 20 26 20 54 43 4c 5f 48 41 53 >flags & TCL_HAS
3230: 48 5f 4b 45 59 5f 52 41 4e 44 4f 4d 49 5a 45 5f H_KEY_RANDOMIZE_
3240: 48 41 53 48 29 20 7b 0a 09 69 6e 64 65 78 20 3d HASH) {..index =
3250: 20 52 41 4e 44 4f 4d 5f 49 4e 44 45 58 28 74 61 RANDOM_INDEX(ta
3260: 62 6c 65 50 74 72 2c 20 50 54 52 32 49 4e 54 28 blePtr, PTR2INT(
3270: 65 6e 74 72 79 50 74 72 2d 3e 68 61 73 68 29 29 entryPtr->hash))
3280: 3b 0a 20 20 20 20 7d 20 65 6c 73 65 20 7b 0a 09 ;. } else {..
3290: 69 6e 64 65 78 20 3d 20 50 54 52 32 55 49 4e 54 index = PTR2UINT
32a0: 28 65 6e 74 72 79 50 74 72 2d 3e 68 61 73 68 29 (entryPtr->hash)
32b0: 20 26 20 74 61 62 6c 65 50 74 72 2d 3e 6d 61 73 & tablePtr->mas
32c0: 6b 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20 62 75 k;. }.. bu
32d0: 63 6b 65 74 50 74 72 20 3d 20 26 74 61 62 6c 65 cketPtr = &table
32e0: 50 74 72 2d 3e 62 75 63 6b 65 74 73 5b 69 6e 64 Ptr->buckets[ind
32f0: 65 78 5d 3b 0a 23 65 6c 73 65 0a 20 20 20 20 62 ex];.#else. b
3300: 75 63 6b 65 74 50 74 72 20 3d 20 65 6e 74 72 79 ucketPtr = entry
3310: 50 74 72 2d 3e 62 75 63 6b 65 74 50 74 72 3b 0a Ptr->bucketPtr;.
3320: 23 65 6e 64 69 66 0a 0a 20 20 20 20 69 66 20 28 #endif.. if (
3330: 2a 62 75 63 6b 65 74 50 74 72 20 3d 3d 20 65 6e *bucketPtr == en
3340: 74 72 79 50 74 72 29 20 7b 0a 09 2a 62 75 63 6b tryPtr) {..*buck
3350: 65 74 50 74 72 20 3d 20 65 6e 74 72 79 50 74 72 etPtr = entryPtr
3360: 2d 3e 6e 65 78 74 50 74 72 3b 0a 20 20 20 20 7d ->nextPtr;. }
3370: 20 65 6c 73 65 20 7b 0a 09 66 6f 72 20 28 70 72 else {..for (pr
3380: 65 76 50 74 72 20 3d 20 2a 62 75 63 6b 65 74 50 evPtr = *bucketP
3390: 74 72 3b 20 3b 20 70 72 65 76 50 74 72 20 3d 20 tr; ; prevPtr =
33a0: 70 72 65 76 50 74 72 2d 3e 6e 65 78 74 50 74 72 prevPtr->nextPtr
33b0: 29 20 7b 0a 09 20 20 20 20 69 66 20 28 70 72 65 ) {.. if (pre
33c0: 76 50 74 72 20 3d 3d 20 4e 55 4c 4c 29 20 7b 0a vPtr == NULL) {.
33d0: 09 09 54 63 6c 5f 50 61 6e 69 63 28 22 6d 61 6c ..Tcl_Panic("mal
33e0: 66 6f 72 6d 65 64 20 62 75 63 6b 65 74 20 63 68 formed bucket ch
33f0: 61 69 6e 20 69 6e 20 54 63 6c 5f 44 65 6c 65 74 ain in Tcl_Delet
3400: 65 48 61 73 68 45 6e 74 72 79 22 29 3b 0a 09 20 eHashEntry");..
3410: 20 20 20 7d 0a 09 20 20 20 20 69 66 20 28 70 72 }.. if (pr
3420: 65 76 50 74 72 2d 3e 6e 65 78 74 50 74 72 20 3d evPtr->nextPtr =
3430: 3d 20 65 6e 74 72 79 50 74 72 29 20 7b 0a 09 09 = entryPtr) {...
3440: 70 72 65 76 50 74 72 2d 3e 6e 65 78 74 50 74 72 prevPtr->nextPtr
3450: 20 3d 20 65 6e 74 72 79 50 74 72 2d 3e 6e 65 78 = entryPtr->nex
3460: 74 50 74 72 3b 0a 09 09 62 72 65 61 6b 3b 0a 09 tPtr;...break;..
3470: 20 20 20 20 7d 0a 09 7d 0a 20 20 20 20 7d 0a 0a }..}. }..
3480: 20 20 20 20 74 61 62 6c 65 50 74 72 2d 3e 6e 75 tablePtr->nu
3490: 6d 45 6e 74 72 69 65 73 2d 2d 3b 0a 20 20 20 20 mEntries--;.
34a0: 69 66 20 28 74 79 70 65 50 74 72 2d 3e 66 72 65 if (typePtr->fre
34b0: 65 45 6e 74 72 79 50 72 6f 63 29 20 7b 0a 09 74 eEntryProc) {..t
34c0: 79 70 65 50 74 72 2d 3e 66 72 65 65 45 6e 74 72 ypePtr->freeEntr
34d0: 79 50 72 6f 63 28 65 6e 74 72 79 50 74 72 29 3b yProc(entryPtr);
34e0: 0a 20 20 20 20 7d 20 65 6c 73 65 20 7b 0a 09 63 . } else {..c
34f0: 6b 66 72 65 65 28 65 6e 74 72 79 50 74 72 29 3b kfree(entryPtr);
3500: 0a 20 20 20 20 7d 0a 7d 0a 0c 0a 2f 2a 0a 20 2a . }.}.../*. *
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 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3540: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3550: 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 54 63 6c ------. *. * Tcl
3560: 5f 44 65 6c 65 74 65 48 61 73 68 54 61 62 6c 65 _DeleteHashTable
3570: 20 2d 2d 0a 20 2a 0a 20 2a 09 46 72 65 65 20 75 --. *. *.Free u
3580: 70 20 65 76 65 72 79 74 68 69 6e 67 20 61 73 73 p everything ass
3590: 6f 63 69 61 74 65 64 20 77 69 74 68 20 61 20 68 ociated with a h
35a0: 61 73 68 20 74 61 62 6c 65 20 65 78 63 65 70 74 ash table except
35b0: 20 66 6f 72 20 74 68 65 20 72 65 63 6f 72 64 0a for the record.
35c0: 20 2a 09 66 6f 72 20 74 68 65 20 74 61 62 6c 65 *.for the table
35d0: 20 69 74 73 65 6c 66 2e 0a 20 2a 0a 20 2a 20 52 itself.. *. * R
35e0: 65 73 75 6c 74 73 3a 0a 20 2a 09 4e 6f 6e 65 2e esults:. *.None.
35f0: 0a 20 2a 0a 20 2a 20 53 69 64 65 20 65 66 66 65 . *. * Side effe
3600: 63 74 73 3a 0a 20 2a 09 54 68 65 20 68 61 73 68 cts:. *.The hash
3610: 20 74 61 62 6c 65 20 69 73 20 6e 6f 20 6c 6f 6e table is no lon
3620: 67 65 72 20 75 73 65 61 62 6c 65 2e 0a 20 2a 0a ger useable.. *.
3630: 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *--------------
3640: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3650: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3660: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3670: 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 2f 0a 0a 76 6f --------. */..vo
3680: 69 64 0a 54 63 6c 5f 44 65 6c 65 74 65 48 61 73 id.Tcl_DeleteHas
3690: 68 54 61 62 6c 65 28 0a 20 20 20 20 54 63 6c 5f hTable(. Tcl_
36a0: 48 61 73 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 HashTable *table
36b0: 50 74 72 29 09 2f 2a 20 54 61 62 6c 65 20 74 6f Ptr)./* Table to
36c0: 20 64 65 6c 65 74 65 2e 20 2a 2f 0a 7b 0a 20 20 delete. */.{.
36d0: 20 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 Tcl_HashEntry
36e0: 2a 68 50 74 72 2c 20 2a 6e 65 78 74 50 74 72 3b *hPtr, *nextPtr;
36f0: 0a 20 20 20 20 63 6f 6e 73 74 20 54 63 6c 5f 48 . const Tcl_H
3700: 61 73 68 4b 65 79 54 79 70 65 20 2a 74 79 70 65 ashKeyType *type
3710: 50 74 72 3b 0a 20 20 20 20 69 6e 74 20 69 3b 0a Ptr;. int i;.
3720: 0a 20 20 20 20 69 66 20 28 74 61 62 6c 65 50 74 . if (tablePt
3730: 72 2d 3e 6b 65 79 54 79 70 65 20 3d 3d 20 54 43 r->keyType == TC
3740: 4c 5f 53 54 52 49 4e 47 5f 4b 45 59 53 29 20 7b L_STRING_KEYS) {
3750: 0a 09 74 79 70 65 50 74 72 20 3d 20 26 74 63 6c ..typePtr = &tcl
3760: 53 74 72 69 6e 67 48 61 73 68 4b 65 79 54 79 70 StringHashKeyTyp
3770: 65 3b 0a 20 20 20 20 7d 20 65 6c 73 65 20 69 66 e;. } else if
3780: 20 28 74 61 62 6c 65 50 74 72 2d 3e 6b 65 79 54 (tablePtr->keyT
3790: 79 70 65 20 3d 3d 20 54 43 4c 5f 4f 4e 45 5f 57 ype == TCL_ONE_W
37a0: 4f 52 44 5f 4b 45 59 53 29 20 7b 0a 09 74 79 70 ORD_KEYS) {..typ
37b0: 65 50 74 72 20 3d 20 26 74 63 6c 4f 6e 65 57 6f ePtr = &tclOneWo
37c0: 72 64 48 61 73 68 4b 65 79 54 79 70 65 3b 0a 20 rdHashKeyType;.
37d0: 20 20 20 7d 20 65 6c 73 65 20 69 66 20 28 74 61 } else if (ta
37e0: 62 6c 65 50 74 72 2d 3e 6b 65 79 54 79 70 65 20 blePtr->keyType
37f0: 3d 3d 20 54 43 4c 5f 43 55 53 54 4f 4d 5f 54 59 == TCL_CUSTOM_TY
3800: 50 45 5f 4b 45 59 53 0a 09 20 20 20 20 7c 7c 20 PE_KEYS.. ||
3810: 74 61 62 6c 65 50 74 72 2d 3e 6b 65 79 54 79 70 tablePtr->keyTyp
3820: 65 20 3d 3d 20 54 43 4c 5f 43 55 53 54 4f 4d 5f e == TCL_CUSTOM_
3830: 50 54 52 5f 4b 45 59 53 29 20 7b 0a 09 74 79 70 PTR_KEYS) {..typ
3840: 65 50 74 72 20 3d 20 74 61 62 6c 65 50 74 72 2d ePtr = tablePtr-
3850: 3e 74 79 70 65 50 74 72 3b 0a 20 20 20 20 7d 20 >typePtr;. }
3860: 65 6c 73 65 20 7b 0a 09 74 79 70 65 50 74 72 20 else {..typePtr
3870: 3d 20 26 74 63 6c 41 72 72 61 79 48 61 73 68 4b = &tclArrayHashK
3880: 65 79 54 79 70 65 3b 0a 20 20 20 20 7d 0a 0a 20 eyType;. }..
3890: 20 20 20 2f 2a 0a 20 20 20 20 20 2a 20 46 72 65 /*. * Fre
38a0: 65 20 75 70 20 61 6c 6c 20 74 68 65 20 65 6e 74 e up all the ent
38b0: 72 69 65 73 20 69 6e 20 74 68 65 20 74 61 62 6c ries in the tabl
38c0: 65 2e 0a 20 20 20 20 20 2a 2f 0a 0a 20 20 20 20 e.. */..
38d0: 66 6f 72 20 28 69 20 3d 20 30 3b 20 69 20 3c 20 for (i = 0; i <
38e0: 74 61 62 6c 65 50 74 72 2d 3e 6e 75 6d 42 75 63 tablePtr->numBuc
38f0: 6b 65 74 73 3b 20 69 2b 2b 29 20 7b 0a 09 68 50 kets; i++) {..hP
3900: 74 72 20 3d 20 74 61 62 6c 65 50 74 72 2d 3e 62 tr = tablePtr->b
3910: 75 63 6b 65 74 73 5b 69 5d 3b 0a 09 77 68 69 6c uckets[i];..whil
3920: 65 20 28 68 50 74 72 20 21 3d 20 4e 55 4c 4c 29 e (hPtr != NULL)
3930: 20 7b 0a 09 20 20 20 20 6e 65 78 74 50 74 72 20 {.. nextPtr
3940: 3d 20 68 50 74 72 2d 3e 6e 65 78 74 50 74 72 3b = hPtr->nextPtr;
3950: 0a 09 20 20 20 20 69 66 20 28 74 79 70 65 50 74 .. if (typePt
3960: 72 2d 3e 66 72 65 65 45 6e 74 72 79 50 72 6f 63 r->freeEntryProc
3970: 29 20 7b 0a 09 09 74 79 70 65 50 74 72 2d 3e 66 ) {...typePtr->f
3980: 72 65 65 45 6e 74 72 79 50 72 6f 63 28 68 50 74 reeEntryProc(hPt
3990: 72 29 3b 0a 09 20 20 20 20 7d 20 65 6c 73 65 20 r);.. } else
39a0: 7b 0a 09 09 63 6b 66 72 65 65 28 68 50 74 72 29 {...ckfree(hPtr)
39b0: 3b 0a 09 20 20 20 20 7d 0a 09 20 20 20 20 68 50 ;.. }.. hP
39c0: 74 72 20 3d 20 6e 65 78 74 50 74 72 3b 0a 09 7d tr = nextPtr;..}
39d0: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f 2a 0a 20 . }.. /*.
39e0: 20 20 20 20 2a 20 46 72 65 65 20 75 70 20 74 68 * Free up th
39f0: 65 20 62 75 63 6b 65 74 20 61 72 72 61 79 2c 20 e bucket array,
3a00: 69 66 20 69 74 20 77 61 73 20 64 79 6e 61 6d 69 if it was dynami
3a10: 63 61 6c 6c 79 20 61 6c 6c 6f 63 61 74 65 64 2e cally allocated.
3a20: 0a 20 20 20 20 20 2a 2f 0a 0a 20 20 20 20 69 66 . */.. if
3a30: 20 28 74 61 62 6c 65 50 74 72 2d 3e 62 75 63 6b (tablePtr->buck
3a40: 65 74 73 20 21 3d 20 74 61 62 6c 65 50 74 72 2d ets != tablePtr-
3a50: 3e 73 74 61 74 69 63 42 75 63 6b 65 74 73 29 20 >staticBuckets)
3a60: 7b 0a 09 69 66 20 28 74 79 70 65 50 74 72 2d 3e {..if (typePtr->
3a70: 66 6c 61 67 73 20 26 20 54 43 4c 5f 48 41 53 48 flags & TCL_HASH
3a80: 5f 4b 45 59 5f 53 59 53 54 45 4d 5f 48 41 53 48 _KEY_SYSTEM_HASH
3a90: 29 20 7b 0a 09 20 20 20 20 54 63 6c 70 53 79 73 ) {.. TclpSys
3aa0: 46 72 65 65 28 28 63 68 61 72 20 2a 29 20 74 61 Free((char *) ta
3ab0: 62 6c 65 50 74 72 2d 3e 62 75 63 6b 65 74 73 29 blePtr->buckets)
3ac0: 3b 0a 09 7d 20 65 6c 73 65 20 7b 0a 09 20 20 20 ;..} else {..
3ad0: 20 63 6b 66 72 65 65 28 74 61 62 6c 65 50 74 72 ckfree(tablePtr
3ae0: 2d 3e 62 75 63 6b 65 74 73 29 3b 0a 09 7d 0a 20 ->buckets);..}.
3af0: 20 20 20 7d 0a 0a 20 20 20 20 2f 2a 0a 20 20 20 }.. /*.
3b00: 20 20 2a 20 41 72 72 61 6e 67 65 20 66 6f 72 20 * Arrange for
3b10: 70 61 6e 69 63 73 20 69 66 20 74 68 65 20 74 61 panics if the ta
3b20: 62 6c 65 20 69 73 20 75 73 65 64 20 61 67 61 69 ble is used agai
3b30: 6e 20 77 69 74 68 6f 75 74 0a 20 20 20 20 20 2a n without. *
3b40: 20 72 65 2d 69 6e 69 74 69 61 6c 69 7a 61 74 69 re-initializati
3b50: 6f 6e 2e 0a 20 20 20 20 20 2a 2f 0a 0a 20 20 20 on.. */..
3b60: 20 74 61 62 6c 65 50 74 72 2d 3e 66 69 6e 64 50 tablePtr->findP
3b70: 72 6f 63 20 3d 20 42 6f 67 75 73 46 69 6e 64 3b roc = BogusFind;
3b80: 0a 20 20 20 20 74 61 62 6c 65 50 74 72 2d 3e 63 . tablePtr->c
3b90: 72 65 61 74 65 50 72 6f 63 20 3d 20 42 6f 67 75 reateProc = Bogu
3ba0: 73 43 72 65 61 74 65 3b 0a 7d 0a 0c 0a 2f 2a 0a sCreate;.}.../*.
3bb0: 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *--------------
3bc0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3bd0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3be0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3bf0: 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 54 --------. *. * T
3c00: 63 6c 5f 46 69 72 73 74 48 61 73 68 45 6e 74 72 cl_FirstHashEntr
3c10: 79 20 2d 2d 0a 20 2a 0a 20 2a 09 4c 6f 63 61 74 y --. *. *.Locat
3c20: 65 20 74 68 65 20 66 69 72 73 74 20 65 6e 74 72 e the first entr
3c30: 79 20 69 6e 20 61 20 68 61 73 68 20 74 61 62 6c y in a hash tabl
3c40: 65 20 61 6e 64 20 73 65 74 20 75 70 20 61 20 72 e and set up a r
3c50: 65 63 6f 72 64 20 74 68 61 74 20 63 61 6e 20 62 ecord that can b
3c60: 65 0a 20 2a 09 75 73 65 64 20 74 6f 20 73 74 65 e. *.used to ste
3c70: 70 20 74 68 72 6f 75 67 68 20 61 6c 6c 20 74 68 p through all th
3c80: 65 20 72 65 6d 61 69 6e 69 6e 67 20 65 6e 74 72 e remaining entr
3c90: 69 65 73 20 6f 66 20 74 68 65 20 74 61 62 6c 65 ies of the table
3ca0: 2e 0a 20 2a 0a 20 2a 20 52 65 73 75 6c 74 73 3a .. *. * Results:
3cb0: 0a 20 2a 09 54 68 65 20 72 65 74 75 72 6e 20 76 . *.The return v
3cc0: 61 6c 75 65 20 69 73 20 61 20 70 6f 69 6e 74 65 alue is a pointe
3cd0: 72 20 74 6f 20 74 68 65 20 66 69 72 73 74 20 65 r to the first e
3ce0: 6e 74 72 79 20 69 6e 20 74 61 62 6c 65 50 74 72 ntry in tablePtr
3cf0: 2c 20 6f 72 20 4e 55 4c 4c 0a 20 2a 09 69 66 20 , or NULL. *.if
3d00: 74 61 62 6c 65 50 74 72 20 68 61 73 20 6e 6f 20 tablePtr has no
3d10: 65 6e 74 72 69 65 73 20 69 6e 20 69 74 2e 20 54 entries in it. T
3d20: 68 65 20 6d 65 6d 6f 72 79 20 61 74 20 2a 73 65 he memory at *se
3d30: 61 72 63 68 50 74 72 20 69 73 0a 20 2a 09 69 6e archPtr is. *.in
3d40: 69 74 69 61 6c 69 7a 65 64 20 73 6f 20 74 68 61 itialized so tha
3d50: 74 20 73 75 62 73 65 71 75 65 6e 74 20 63 61 6c t subsequent cal
3d60: 6c 73 20 74 6f 20 54 63 6c 5f 4e 65 78 74 48 61 ls to Tcl_NextHa
3d70: 73 68 45 6e 74 72 79 20 77 69 6c 6c 20 72 65 74 shEntry will ret
3d80: 75 72 6e 0a 20 2a 09 61 6c 6c 20 6f 66 20 74 68 urn. *.all of th
3d90: 65 20 65 6e 74 72 69 65 73 20 69 6e 20 74 68 65 e entries in the
3da0: 20 74 61 62 6c 65 2c 20 6f 6e 65 20 61 74 20 61 table, one at a
3db0: 20 74 69 6d 65 2e 0a 20 2a 0a 20 2a 20 53 69 64 time.. *. * Sid
3dc0: 65 20 65 66 66 65 63 74 73 3a 0a 20 2a 09 4e 6f e effects:. *.No
3dd0: 6e 65 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d ne.. *. *-------
3de0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3df0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3e00: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3e10: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
3e20: 20 2a 2f 0a 0a 54 63 6c 5f 48 61 73 68 45 6e 74 */..Tcl_HashEnt
3e30: 72 79 20 2a 0a 54 63 6c 5f 46 69 72 73 74 48 61 ry *.Tcl_FirstHa
3e40: 73 68 45 6e 74 72 79 28 0a 20 20 20 20 54 63 6c shEntry(. Tcl
3e50: 5f 48 61 73 68 54 61 62 6c 65 20 2a 74 61 62 6c _HashTable *tabl
3e60: 65 50 74 72 2c 09 2f 2a 20 54 61 62 6c 65 20 74 ePtr,./* Table t
3e70: 6f 20 73 65 61 72 63 68 2e 20 2a 2f 0a 20 20 20 o search. */.
3e80: 20 54 63 6c 5f 48 61 73 68 53 65 61 72 63 68 20 Tcl_HashSearch
3e90: 2a 73 65 61 72 63 68 50 74 72 29 09 2f 2a 20 50 *searchPtr)./* P
3ea0: 6c 61 63 65 20 74 6f 20 73 74 6f 72 65 20 69 6e lace to store in
3eb0: 66 6f 72 6d 61 74 69 6f 6e 20 61 62 6f 75 74 20 formation about
3ec0: 70 72 6f 67 72 65 73 73 0a 09 09 09 09 20 2a 20 progress..... *
3ed0: 74 68 72 6f 75 67 68 20 74 68 65 20 74 61 62 6c through the tabl
3ee0: 65 2e 20 2a 2f 0a 7b 0a 20 20 20 20 73 65 61 72 e. */.{. sear
3ef0: 63 68 50 74 72 2d 3e 74 61 62 6c 65 50 74 72 20 chPtr->tablePtr
3f00: 3d 20 74 61 62 6c 65 50 74 72 3b 0a 20 20 20 20 = tablePtr;.
3f10: 73 65 61 72 63 68 50 74 72 2d 3e 6e 65 78 74 49 searchPtr->nextI
3f20: 6e 64 65 78 20 3d 20 30 3b 0a 20 20 20 20 73 65 ndex = 0;. se
3f30: 61 72 63 68 50 74 72 2d 3e 6e 65 78 74 45 6e 74 archPtr->nextEnt
3f40: 72 79 50 74 72 20 3d 20 4e 55 4c 4c 3b 0a 20 20 ryPtr = NULL;.
3f50: 20 20 72 65 74 75 72 6e 20 54 63 6c 5f 4e 65 78 return Tcl_Nex
3f60: 74 48 61 73 68 45 6e 74 72 79 28 73 65 61 72 63 tHashEntry(searc
3f70: 68 50 74 72 29 3b 0a 7d 0a 0c 0a 2f 2a 0a 20 2a hPtr);.}.../*. *
3f80: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3f90: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3fa0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3fb0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
3fc0: 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 54 63 6c ------. *. * Tcl
3fd0: 5f 4e 65 78 74 48 61 73 68 45 6e 74 72 79 20 2d _NextHashEntry -
3fe0: 2d 0a 20 2a 0a 20 2a 09 4f 6e 63 65 20 61 20 68 -. *. *.Once a h
3ff0: 61 73 68 20 74 61 62 6c 65 20 65 6e 75 6d 65 72 ash table enumer
4000: 61 74 69 6f 6e 20 68 61 73 20 62 65 65 6e 20 69 ation has been i
4010: 6e 69 74 69 61 74 65 64 20 62 79 20 63 61 6c 6c nitiated by call
4020: 69 6e 67 0a 20 2a 09 54 63 6c 5f 46 69 72 73 74 ing. *.Tcl_First
4030: 48 61 73 68 45 6e 74 72 79 2c 20 74 68 69 73 20 HashEntry, this
4040: 66 75 6e 63 74 69 6f 6e 20 6d 61 79 20 62 65 20 function may be
4050: 63 61 6c 6c 65 64 20 74 6f 20 72 65 74 75 72 6e called to return
4060: 20 73 75 63 63 65 73 73 69 76 65 0a 20 2a 09 65 successive. *.e
4070: 6c 65 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 74 lements of the t
4080: 61 62 6c 65 2e 0a 20 2a 0a 20 2a 20 52 65 73 75 able.. *. * Resu
4090: 6c 74 73 3a 0a 20 2a 09 54 68 65 20 72 65 74 75 lts:. *.The retu
40a0: 72 6e 20 76 61 6c 75 65 20 69 73 20 74 68 65 20 rn value is the
40b0: 6e 65 78 74 20 65 6e 74 72 79 20 69 6e 20 74 68 next entry in th
40c0: 65 20 68 61 73 68 20 74 61 62 6c 65 20 62 65 69 e hash table bei
40d0: 6e 67 20 65 6e 75 6d 65 72 61 74 65 64 2c 0a 20 ng enumerated,.
40e0: 2a 09 6f 72 20 4e 55 4c 4c 20 69 66 20 74 68 65 *.or NULL if the
40f0: 20 65 6e 64 20 6f 66 20 74 68 65 20 74 61 62 6c end of the tabl
4100: 65 20 69 73 20 72 65 61 63 68 65 64 2e 0a 20 2a e is reached.. *
4110: 0a 20 2a 20 53 69 64 65 20 65 66 66 65 63 74 73 . * Side effects
4120: 3a 0a 20 2a 09 4e 6f 6e 65 2e 0a 20 2a 0a 20 2a :. *.None.. *. *
4130: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4140: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4150: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4160: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4170: 2d 2d 2d 2d 2d 2d 0a 20 2a 2f 0a 0a 54 63 6c 5f ------. */..Tcl_
4180: 48 61 73 68 45 6e 74 72 79 20 2a 0a 54 63 6c 5f HashEntry *.Tcl_
4190: 4e 65 78 74 48 61 73 68 45 6e 74 72 79 28 0a 20 NextHashEntry(.
41a0: 20 20 20 54 63 6c 5f 48 61 73 68 53 65 61 72 63 Tcl_HashSearc
41b0: 68 20 2a 73 65 61 72 63 68 50 74 72 29 0a 09 09 h *searchPtr)...
41c0: 09 09 2f 2a 20 50 6c 61 63 65 20 74 6f 20 73 74 ../* Place to st
41d0: 6f 72 65 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 ore information
41e0: 61 62 6f 75 74 20 70 72 6f 67 72 65 73 73 0a 09 about progress..
41f0: 09 09 09 20 2a 20 74 68 72 6f 75 67 68 20 74 68 ... * through th
4200: 65 20 74 61 62 6c 65 2e 20 4d 75 73 74 20 68 61 e table. Must ha
4210: 76 65 20 62 65 65 6e 0a 09 09 09 09 20 2a 20 69 ve been..... * i
4220: 6e 69 74 69 61 6c 69 7a 65 64 20 62 79 20 63 61 nitialized by ca
4230: 6c 6c 69 6e 67 0a 09 09 09 09 20 2a 20 54 63 6c lling..... * Tcl
4240: 5f 46 69 72 73 74 48 61 73 68 45 6e 74 72 79 2e _FirstHashEntry.
4250: 20 2a 2f 0a 7b 0a 20 20 20 20 54 63 6c 5f 48 61 */.{. Tcl_Ha
4260: 73 68 45 6e 74 72 79 20 2a 68 50 74 72 3b 0a 20 shEntry *hPtr;.
4270: 20 20 20 54 63 6c 5f 48 61 73 68 54 61 62 6c 65 Tcl_HashTable
4280: 20 2a 74 61 62 6c 65 50 74 72 20 3d 20 73 65 61 *tablePtr = sea
4290: 72 63 68 50 74 72 2d 3e 74 61 62 6c 65 50 74 72 rchPtr->tablePtr
42a0: 3b 0a 0a 20 20 20 20 77 68 69 6c 65 20 28 73 65 ;.. while (se
42b0: 61 72 63 68 50 74 72 2d 3e 6e 65 78 74 45 6e 74 archPtr->nextEnt
42c0: 72 79 50 74 72 20 3d 3d 20 4e 55 4c 4c 29 20 7b ryPtr == NULL) {
42d0: 0a 09 69 66 20 28 73 65 61 72 63 68 50 74 72 2d ..if (searchPtr-
42e0: 3e 6e 65 78 74 49 6e 64 65 78 20 3e 3d 20 74 61 >nextIndex >= ta
42f0: 62 6c 65 50 74 72 2d 3e 6e 75 6d 42 75 63 6b 65 blePtr->numBucke
4300: 74 73 29 20 7b 0a 09 20 20 20 20 72 65 74 75 72 ts) {.. retur
4310: 6e 20 4e 55 4c 4c 3b 0a 09 7d 0a 09 73 65 61 72 n NULL;..}..sear
4320: 63 68 50 74 72 2d 3e 6e 65 78 74 45 6e 74 72 79 chPtr->nextEntry
4330: 50 74 72 20 3d 0a 09 09 74 61 62 6c 65 50 74 72 Ptr =...tablePtr
4340: 2d 3e 62 75 63 6b 65 74 73 5b 73 65 61 72 63 68 ->buckets[search
4350: 50 74 72 2d 3e 6e 65 78 74 49 6e 64 65 78 5d 3b Ptr->nextIndex];
4360: 0a 09 73 65 61 72 63 68 50 74 72 2d 3e 6e 65 78 ..searchPtr->nex
4370: 74 49 6e 64 65 78 2b 2b 3b 0a 20 20 20 20 7d 0a tIndex++;. }.
4380: 20 20 20 20 68 50 74 72 20 3d 20 73 65 61 72 63 hPtr = searc
4390: 68 50 74 72 2d 3e 6e 65 78 74 45 6e 74 72 79 50 hPtr->nextEntryP
43a0: 74 72 3b 0a 20 20 20 20 73 65 61 72 63 68 50 74 tr;. searchPt
43b0: 72 2d 3e 6e 65 78 74 45 6e 74 72 79 50 74 72 20 r->nextEntryPtr
43c0: 3d 20 68 50 74 72 2d 3e 6e 65 78 74 50 74 72 3b = hPtr->nextPtr;
43d0: 0a 20 20 20 20 72 65 74 75 72 6e 20 68 50 74 72 . return hPtr
43e0: 3b 0a 7d 0a 0c 0a 2f 2a 0a 20 2a 2d 2d 2d 2d 2d ;.}.../*. *-----
43f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4400: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4410: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4420: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4430: 2d 0a 20 2a 0a 20 2a 20 54 63 6c 5f 48 61 73 68 -. *. * Tcl_Hash
4440: 53 74 61 74 73 20 2d 2d 0a 20 2a 0a 20 2a 09 52 Stats --. *. *.R
4450: 65 74 75 72 6e 20 73 74 61 74 69 73 74 69 63 73 eturn statistics
4460: 20 64 65 73 63 72 69 62 69 6e 67 20 74 68 65 20 describing the
4470: 6c 61 79 6f 75 74 20 6f 66 20 74 68 65 20 68 61 layout of the ha
4480: 73 68 20 74 61 62 6c 65 20 69 6e 20 69 74 73 20 sh table in its
4490: 68 61 73 68 0a 20 2a 09 62 75 63 6b 65 74 73 2e hash. *.buckets.
44a0: 0a 20 2a 0a 20 2a 20 52 65 73 75 6c 74 73 3a 0a . *. * Results:.
44b0: 20 2a 09 54 68 65 20 72 65 74 75 72 6e 20 76 61 *.The return va
44c0: 6c 75 65 20 69 73 20 61 20 6d 61 6c 6c 6f 63 2d lue is a malloc-
44d0: 65 64 20 73 74 72 69 6e 67 20 63 6f 6e 74 61 69 ed string contai
44e0: 6e 69 6e 67 20 69 6e 66 6f 72 6d 61 74 69 6f 6e ning information
44f0: 20 61 62 6f 75 74 0a 20 2a 09 74 61 62 6c 65 50 about. *.tableP
4500: 74 72 2e 20 49 74 20 69 73 20 74 68 65 20 63 61 tr. It is the ca
4510: 6c 6c 65 72 27 73 20 72 65 73 70 6f 6e 73 69 62 ller's responsib
4520: 69 6c 69 74 79 20 74 6f 20 66 72 65 65 20 74 68 ility to free th
4530: 69 73 20 73 74 72 69 6e 67 2e 0a 20 2a 0a 20 2a is string.. *. *
4540: 20 53 69 64 65 20 65 66 66 65 63 74 73 3a 0a 20 Side effects:.
4550: 2a 09 4e 6f 6e 65 2e 0a 20 2a 0a 20 2a 2d 2d 2d *.None.. *. *---
4560: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4570: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4580: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4590: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
45a0: 2d 2d 2d 0a 20 2a 2f 0a 0a 63 68 61 72 20 2a 0a ---. */..char *.
45b0: 54 63 6c 5f 48 61 73 68 53 74 61 74 73 28 0a 20 Tcl_HashStats(.
45c0: 20 20 20 54 63 6c 5f 48 61 73 68 54 61 62 6c 65 Tcl_HashTable
45d0: 20 2a 74 61 62 6c 65 50 74 72 29 09 2f 2a 20 54 *tablePtr)./* T
45e0: 61 62 6c 65 20 66 6f 72 20 77 68 69 63 68 20 74 able for which t
45f0: 6f 20 70 72 6f 64 75 63 65 20 73 74 61 74 73 2e o produce stats.
4600: 20 2a 2f 0a 7b 0a 23 64 65 66 69 6e 65 20 4e 55 */.{.#define NU
4610: 4d 5f 43 4f 55 4e 54 45 52 53 20 31 30 0a 20 20 M_COUNTERS 10.
4620: 20 20 69 6e 74 20 63 6f 75 6e 74 5b 4e 55 4d 5f int count[NUM_
4630: 43 4f 55 4e 54 45 52 53 5d 2c 20 6f 76 65 72 66 COUNTERS], overf
4640: 6c 6f 77 2c 20 69 2c 20 6a 3b 0a 20 20 20 20 64 low, i, j;. d
4650: 6f 75 62 6c 65 20 61 76 65 72 61 67 65 2c 20 74 ouble average, t
4660: 6d 70 3b 0a 20 20 20 20 54 63 6c 5f 48 61 73 68 mp;. Tcl_Hash
4670: 45 6e 74 72 79 20 2a 68 50 74 72 3b 0a 20 20 20 Entry *hPtr;.
4680: 20 63 68 61 72 20 2a 72 65 73 75 6c 74 2c 20 2a char *result, *
4690: 70 3b 0a 0a 20 20 20 20 2f 2a 0a 20 20 20 20 20 p;.. /*.
46a0: 2a 20 43 6f 6d 70 75 74 65 20 61 20 68 69 73 74 * Compute a hist
46b0: 6f 67 72 61 6d 20 6f 66 20 62 75 63 6b 65 74 20 ogram of bucket
46c0: 75 73 61 67 65 2e 0a 20 20 20 20 20 2a 2f 0a 0a usage.. */..
46d0: 20 20 20 20 66 6f 72 20 28 69 20 3d 20 30 3b 20 for (i = 0;
46e0: 69 20 3c 20 4e 55 4d 5f 43 4f 55 4e 54 45 52 53 i < NUM_COUNTERS
46f0: 3b 20 69 2b 2b 29 20 7b 0a 09 63 6f 75 6e 74 5b ; i++) {..count[
4700: 69 5d 20 3d 20 30 3b 0a 20 20 20 20 7d 0a 20 20 i] = 0;. }.
4710: 20 20 6f 76 65 72 66 6c 6f 77 20 3d 20 30 3b 0a overflow = 0;.
4720: 20 20 20 20 61 76 65 72 61 67 65 20 3d 20 30 2e average = 0.
4730: 30 3b 0a 20 20 20 20 66 6f 72 20 28 69 20 3d 20 0;. for (i =
4740: 30 3b 20 69 20 3c 20 74 61 62 6c 65 50 74 72 2d 0; i < tablePtr-
4750: 3e 6e 75 6d 42 75 63 6b 65 74 73 3b 20 69 2b 2b >numBuckets; i++
4760: 29 20 7b 0a 09 6a 20 3d 20 30 3b 0a 09 66 6f 72 ) {..j = 0;..for
4770: 20 28 68 50 74 72 20 3d 20 74 61 62 6c 65 50 74 (hPtr = tablePt
4780: 72 2d 3e 62 75 63 6b 65 74 73 5b 69 5d 3b 20 68 r->buckets[i]; h
4790: 50 74 72 20 21 3d 20 4e 55 4c 4c 3b 20 68 50 74 Ptr != NULL; hPt
47a0: 72 20 3d 20 68 50 74 72 2d 3e 6e 65 78 74 50 74 r = hPtr->nextPt
47b0: 72 29 20 7b 0a 09 20 20 20 20 6a 2b 2b 3b 0a 09 r) {.. j++;..
47c0: 7d 0a 09 69 66 20 28 6a 20 3c 20 4e 55 4d 5f 43 }..if (j < NUM_C
47d0: 4f 55 4e 54 45 52 53 29 20 7b 0a 09 20 20 20 20 OUNTERS) {..
47e0: 63 6f 75 6e 74 5b 6a 5d 2b 2b 3b 0a 09 7d 20 65 count[j]++;..} e
47f0: 6c 73 65 20 7b 0a 09 20 20 20 20 6f 76 65 72 66 lse {.. overf
4800: 6c 6f 77 2b 2b 3b 0a 09 7d 0a 09 74 6d 70 20 3d low++;..}..tmp =
4810: 20 6a 3b 0a 09 69 66 20 28 74 61 62 6c 65 50 74 j;..if (tablePt
4820: 72 2d 3e 6e 75 6d 45 6e 74 72 69 65 73 20 21 3d r->numEntries !=
4830: 20 30 29 20 7b 0a 09 20 20 20 20 61 76 65 72 61 0) {.. avera
4840: 67 65 20 2b 3d 20 28 74 6d 70 2b 31 2e 30 29 2a ge += (tmp+1.0)*
4850: 28 74 6d 70 2f 74 61 62 6c 65 50 74 72 2d 3e 6e (tmp/tablePtr->n
4860: 75 6d 45 6e 74 72 69 65 73 29 2f 32 2e 30 3b 0a umEntries)/2.0;.
4870: 09 7d 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f 2a .}. }.. /*
4880: 0a 20 20 20 20 20 2a 20 50 72 69 6e 74 20 6f 75 . * Print ou
4890: 74 20 74 68 65 20 68 69 73 74 6f 67 72 61 6d 20 t the histogram
48a0: 61 6e 64 20 61 20 66 65 77 20 6f 74 68 65 72 20 and a few other
48b0: 70 69 65 63 65 73 20 6f 66 20 69 6e 66 6f 72 6d pieces of inform
48c0: 61 74 69 6f 6e 2e 0a 20 20 20 20 20 2a 2f 0a 0a ation.. */..
48d0: 20 20 20 20 72 65 73 75 6c 74 20 3d 20 63 6b 61 result = cka
48e0: 6c 6c 6f 63 28 28 4e 55 4d 5f 43 4f 55 4e 54 45 lloc((NUM_COUNTE
48f0: 52 53 20 2a 20 36 30 29 20 2b 20 33 30 30 29 3b RS * 60) + 300);
4900: 0a 20 20 20 20 73 6e 70 72 69 6e 74 66 28 72 65 . snprintf(re
4910: 73 75 6c 74 2c 20 36 30 2c 20 22 25 64 20 65 6e sult, 60, "%d en
4920: 74 72 69 65 73 20 69 6e 20 74 61 62 6c 65 2c 20 tries in table,
4930: 25 64 20 62 75 63 6b 65 74 73 5c 6e 22 2c 0a 09 %d buckets\n",..
4940: 20 20 20 20 74 61 62 6c 65 50 74 72 2d 3e 6e 75 tablePtr->nu
4950: 6d 45 6e 74 72 69 65 73 2c 20 74 61 62 6c 65 50 mEntries, tableP
4960: 74 72 2d 3e 6e 75 6d 42 75 63 6b 65 74 73 29 3b tr->numBuckets);
4970: 0a 20 20 20 20 70 20 3d 20 72 65 73 75 6c 74 20 . p = result
4980: 2b 20 73 74 72 6c 65 6e 28 72 65 73 75 6c 74 29 + strlen(result)
4990: 3b 0a 20 20 20 20 66 6f 72 20 28 69 20 3d 20 30 ;. for (i = 0
49a0: 3b 20 69 20 3c 20 4e 55 4d 5f 43 4f 55 4e 54 45 ; i < NUM_COUNTE
49b0: 52 53 3b 20 69 2b 2b 29 20 7b 0a 09 73 6e 70 72 RS; i++) {..snpr
49c0: 69 6e 74 66 28 70 2c 20 36 30 2c 20 22 6e 75 6d intf(p, 60, "num
49d0: 62 65 72 20 6f 66 20 62 75 63 6b 65 74 73 20 77 ber of buckets w
49e0: 69 74 68 20 25 64 20 65 6e 74 72 69 65 73 3a 20 ith %d entries:
49f0: 25 64 5c 6e 22 2c 0a 09 09 69 2c 20 63 6f 75 6e %d\n",...i, coun
4a00: 74 5b 69 5d 29 3b 0a 09 70 20 2b 3d 20 73 74 72 t[i]);..p += str
4a10: 6c 65 6e 28 70 29 3b 0a 20 20 20 20 7d 0a 20 20 len(p);. }.
4a20: 20 20 73 6e 70 72 69 6e 74 66 28 70 2c 20 36 30 snprintf(p, 60
4a30: 2c 20 22 6e 75 6d 62 65 72 20 6f 66 20 62 75 63 , "number of buc
4a40: 6b 65 74 73 20 77 69 74 68 20 25 64 20 6f 72 20 kets with %d or
4a50: 6d 6f 72 65 20 65 6e 74 72 69 65 73 3a 20 25 64 more entries: %d
4a60: 5c 6e 22 2c 0a 09 20 20 20 20 4e 55 4d 5f 43 4f \n",.. NUM_CO
4a70: 55 4e 54 45 52 53 2c 20 6f 76 65 72 66 6c 6f 77 UNTERS, overflow
4a80: 29 3b 0a 20 20 20 20 70 20 2b 3d 20 73 74 72 6c );. p += strl
4a90: 65 6e 28 70 29 3b 0a 20 20 20 20 73 6e 70 72 69 en(p);. snpri
4aa0: 6e 74 66 28 70 2c 20 36 30 2c 20 22 61 76 65 72 ntf(p, 60, "aver
4ab0: 61 67 65 20 73 65 61 72 63 68 20 64 69 73 74 61 age search dista
4ac0: 6e 63 65 20 66 6f 72 20 65 6e 74 72 79 3a 20 25 nce for entry: %
4ad0: 2e 31 66 22 2c 20 61 76 65 72 61 67 65 29 3b 0a .1f", average);.
4ae0: 20 20 20 20 72 65 74 75 72 6e 20 72 65 73 75 6c return resul
4af0: 74 3b 0a 7d 0a 0c 0a 2f 2a 0a 20 2a 2d 2d 2d 2d t;.}.../*. *----
4b00: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4b10: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4b20: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4b30: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4b40: 2d 2d 0a 20 2a 0a 20 2a 20 41 6c 6c 6f 63 41 72 --. *. * AllocAr
4b50: 72 61 79 45 6e 74 72 79 20 2d 2d 0a 20 2a 0a 20 rayEntry --. *.
4b60: 2a 09 41 6c 6c 6f 63 61 74 65 20 73 70 61 63 65 *.Allocate space
4b70: 20 66 6f 72 20 61 20 54 63 6c 5f 48 61 73 68 45 for a Tcl_HashE
4b80: 6e 74 72 79 20 63 6f 6e 74 61 69 6e 69 6e 67 20 ntry containing
4b90: 74 68 65 20 61 72 72 61 79 20 6b 65 79 2e 0a 20 the array key..
4ba0: 2a 0a 20 2a 20 52 65 73 75 6c 74 73 3a 0a 20 2a *. * Results:. *
4bb0: 09 54 68 65 20 72 65 74 75 72 6e 20 76 61 6c 75 .The return valu
4bc0: 65 20 69 73 20 61 20 70 6f 69 6e 74 65 72 20 74 e is a pointer t
4bd0: 6f 20 74 68 65 20 63 72 65 61 74 65 64 20 65 6e o the created en
4be0: 74 72 79 2e 0a 20 2a 0a 20 2a 20 53 69 64 65 20 try.. *. * Side
4bf0: 65 66 66 65 63 74 73 3a 0a 20 2a 09 4e 6f 6e 65 effects:. *.None
4c00: 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d .. *. *---------
4c10: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4c20: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4c30: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4c40: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a -------------. *
4c50: 2f 0a 0a 73 74 61 74 69 63 20 54 63 6c 5f 48 61 /..static Tcl_Ha
4c60: 73 68 45 6e 74 72 79 20 2a 0a 41 6c 6c 6f 63 41 shEntry *.AllocA
4c70: 72 72 61 79 45 6e 74 72 79 28 0a 20 20 20 20 54 rrayEntry(. T
4c80: 63 6c 5f 48 61 73 68 54 61 62 6c 65 20 2a 74 61 cl_HashTable *ta
4c90: 62 6c 65 50 74 72 2c 09 2f 2a 20 48 61 73 68 20 blePtr,./* Hash
4ca0: 74 61 62 6c 65 2e 20 2a 2f 0a 20 20 20 20 76 6f table. */. vo
4cb0: 69 64 20 2a 6b 65 79 50 74 72 29 09 09 2f 2a 20 id *keyPtr)../*
4cc0: 4b 65 79 20 74 6f 20 73 74 6f 72 65 20 69 6e 20 Key to store in
4cd0: 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 65 the hash table e
4ce0: 6e 74 72 79 2e 20 2a 2f 0a 7b 0a 20 20 20 20 69 ntry. */.{. i
4cf0: 6e 74 20 2a 61 72 72 61 79 20 3d 20 28 69 6e 74 nt *array = (int
4d00: 20 2a 29 20 6b 65 79 50 74 72 3b 0a 20 20 20 20 *) keyPtr;.
4d10: 69 6e 74 20 2a 69 50 74 72 31 2c 20 2a 69 50 74 int *iPtr1, *iPt
4d20: 72 32 3b 0a 20 20 20 20 54 63 6c 5f 48 61 73 68 r2;. Tcl_Hash
4d30: 45 6e 74 72 79 20 2a 68 50 74 72 3b 0a 20 20 20 Entry *hPtr;.
4d40: 20 69 6e 74 20 63 6f 75 6e 74 3b 0a 20 20 20 20 int count;.
4d50: 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 73 69 7a unsigned int siz
4d60: 65 3b 0a 0a 20 20 20 20 63 6f 75 6e 74 20 3d 20 e;.. count =
4d70: 74 61 62 6c 65 50 74 72 2d 3e 6b 65 79 54 79 70 tablePtr->keyTyp
4d80: 65 3b 0a 0a 20 20 20 20 73 69 7a 65 20 3d 20 54 e;.. size = T
4d90: 63 6c 4f 66 66 73 65 74 28 54 63 6c 5f 48 61 73 clOffset(Tcl_Has
4da0: 68 45 6e 74 72 79 2c 20 6b 65 79 29 20 2b 20 63 hEntry, key) + c
4db0: 6f 75 6e 74 2a 73 69 7a 65 6f 66 28 69 6e 74 29 ount*sizeof(int)
4dc0: 3b 0a 20 20 20 20 69 66 20 28 73 69 7a 65 20 3c ;. if (size <
4dd0: 20 73 69 7a 65 6f 66 28 54 63 6c 5f 48 61 73 68 sizeof(Tcl_Hash
4de0: 45 6e 74 72 79 29 29 20 7b 0a 09 73 69 7a 65 20 Entry)) {..size
4df0: 3d 20 73 69 7a 65 6f 66 28 54 63 6c 5f 48 61 73 = sizeof(Tcl_Has
4e00: 68 45 6e 74 72 79 29 3b 0a 20 20 20 20 7d 0a 20 hEntry);. }.
4e10: 20 20 20 68 50 74 72 20 3d 20 63 6b 61 6c 6c 6f hPtr = ckallo
4e20: 63 28 73 69 7a 65 29 3b 0a 0a 20 20 20 20 66 6f c(size);.. fo
4e30: 72 20 28 69 50 74 72 31 20 3d 20 61 72 72 61 79 r (iPtr1 = array
4e40: 2c 20 69 50 74 72 32 20 3d 20 68 50 74 72 2d 3e , iPtr2 = hPtr->
4e50: 6b 65 79 2e 77 6f 72 64 73 3b 0a 09 20 20 20 20 key.words;..
4e60: 63 6f 75 6e 74 20 3e 20 30 3b 20 63 6f 75 6e 74 count > 0; count
4e70: 2d 2d 2c 20 69 50 74 72 31 2b 2b 2c 20 69 50 74 --, iPtr1++, iPt
4e80: 72 32 2b 2b 29 20 7b 0a 09 2a 69 50 74 72 32 20 r2++) {..*iPtr2
4e90: 3d 20 2a 69 50 74 72 31 3b 0a 20 20 20 20 7d 0a = *iPtr1;. }.
4ea0: 20 20 20 20 68 50 74 72 2d 3e 63 6c 69 65 6e 74 hPtr->client
4eb0: 44 61 74 61 20 3d 20 30 3b 0a 0a 20 20 20 20 72 Data = 0;.. r
4ec0: 65 74 75 72 6e 20 68 50 74 72 3b 0a 7d 0a 0c 0a eturn hPtr;.}...
4ed0: 2f 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d /*. *-----------
4ee0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
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 0a 20 2a 0a 20 -----------. *.
4f20: 2a 20 43 6f 6d 70 61 72 65 41 72 72 61 79 4b 65 * CompareArrayKe
4f30: 79 73 20 2d 2d 0a 20 2a 0a 20 2a 09 43 6f 6d 70 ys --. *. *.Comp
4f40: 61 72 65 73 20 74 77 6f 20 61 72 72 61 79 20 6b ares two array k
4f50: 65 79 73 2e 0a 20 2a 0a 20 2a 20 52 65 73 75 6c eys.. *. * Resul
4f60: 74 73 3a 0a 20 2a 09 54 68 65 20 72 65 74 75 72 ts:. *.The retur
4f70: 6e 20 76 61 6c 75 65 20 69 73 20 30 20 69 66 20 n value is 0 if
4f80: 74 68 65 79 20 61 72 65 20 64 69 66 66 65 72 65 they are differe
4f90: 6e 74 20 61 6e 64 20 31 20 69 66 20 74 68 65 79 nt and 1 if they
4fa0: 20 61 72 65 20 74 68 65 0a 20 2a 09 73 61 6d 65 are the. *.same
4fb0: 2e 0a 20 2a 0a 20 2a 20 53 69 64 65 20 65 66 66 .. *. * Side eff
4fc0: 65 63 74 73 3a 0a 20 2a 09 4e 6f 6e 65 2e 0a 20 ects:. *.None..
4fd0: 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *. *------------
4fe0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
4ff0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5000: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 2f 0a 0a ----------. */..
5020: 73 74 61 74 69 63 20 69 6e 74 0a 43 6f 6d 70 61 static int.Compa
5030: 72 65 41 72 72 61 79 4b 65 79 73 28 0a 20 20 20 reArrayKeys(.
5040: 20 76 6f 69 64 20 2a 6b 65 79 50 74 72 2c 09 09 void *keyPtr,..
5050: 2f 2a 20 4e 65 77 20 6b 65 79 20 74 6f 20 63 6f /* New key to co
5060: 6d 70 61 72 65 2e 20 2a 2f 0a 20 20 20 20 54 63 mpare. */. Tc
5070: 6c 5f 48 61 73 68 45 6e 74 72 79 20 2a 68 50 74 l_HashEntry *hPt
5080: 72 29 09 2f 2a 20 45 78 69 73 74 69 6e 67 20 6b r)./* Existing k
5090: 65 79 20 74 6f 20 63 6f 6d 70 61 72 65 2e 20 2a ey to compare. *
50a0: 2f 0a 7b 0a 20 20 20 20 63 6f 6e 73 74 20 69 6e /.{. const in
50b0: 74 20 2a 69 50 74 72 31 20 3d 20 28 63 6f 6e 73 t *iPtr1 = (cons
50c0: 74 20 69 6e 74 20 2a 29 20 6b 65 79 50 74 72 3b t int *) keyPtr;
50d0: 0a 20 20 20 20 63 6f 6e 73 74 20 69 6e 74 20 2a . const int *
50e0: 69 50 74 72 32 20 3d 20 28 63 6f 6e 73 74 20 69 iPtr2 = (const i
50f0: 6e 74 20 2a 29 20 68 50 74 72 2d 3e 6b 65 79 2e nt *) hPtr->key.
5100: 77 6f 72 64 73 3b 0a 20 20 20 20 54 63 6c 5f 48 words;. Tcl_H
5110: 61 73 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 50 ashTable *tableP
5120: 74 72 20 3d 20 68 50 74 72 2d 3e 74 61 62 6c 65 tr = hPtr->table
5130: 50 74 72 3b 0a 20 20 20 20 69 6e 74 20 63 6f 75 Ptr;. int cou
5140: 6e 74 3b 0a 0a 20 20 20 20 66 6f 72 20 28 63 6f nt;.. for (co
5150: 75 6e 74 20 3d 20 74 61 62 6c 65 50 74 72 2d 3e unt = tablePtr->
5160: 6b 65 79 54 79 70 65 3b 20 3b 20 63 6f 75 6e 74 keyType; ; count
5170: 2d 2d 2c 20 69 50 74 72 31 2b 2b 2c 20 69 50 74 --, iPtr1++, iPt
5180: 72 32 2b 2b 29 20 7b 0a 09 69 66 20 28 63 6f 75 r2++) {..if (cou
5190: 6e 74 20 3d 3d 20 30 29 20 7b 0a 09 20 20 20 20 nt == 0) {..
51a0: 72 65 74 75 72 6e 20 31 3b 0a 09 7d 0a 09 69 66 return 1;..}..if
51b0: 20 28 2a 69 50 74 72 31 20 21 3d 20 2a 69 50 74 (*iPtr1 != *iPt
51c0: 72 32 29 20 7b 0a 09 20 20 20 20 62 72 65 61 6b r2) {.. break
51d0: 3b 0a 09 7d 0a 20 20 20 20 7d 0a 20 20 20 20 72 ;..}. }. r
51e0: 65 74 75 72 6e 20 30 3b 0a 7d 0a 0c 0a 2f 2a 0a eturn 0;.}.../*.
51f0: 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *--------------
5200: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5210: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5220: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5230: 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 48 --------. *. * H
5240: 61 73 68 41 72 72 61 79 4b 65 79 20 2d 2d 0a 20 ashArrayKey --.
5250: 2a 0a 20 2a 09 43 6f 6d 70 75 74 65 20 61 20 6f *. *.Compute a o
5260: 6e 65 2d 77 6f 72 64 20 73 75 6d 6d 61 72 79 20 ne-word summary
5270: 6f 66 20 61 6e 20 61 72 72 61 79 2c 20 77 68 69 of an array, whi
5280: 63 68 20 63 61 6e 20 62 65 20 75 73 65 64 20 74 ch can be used t
5290: 6f 20 67 65 6e 65 72 61 74 65 0a 20 2a 09 61 20 o generate. *.a
52a0: 68 61 73 68 20 69 6e 64 65 78 2e 0a 20 2a 0a 20 hash index.. *.
52b0: 2a 20 52 65 73 75 6c 74 73 3a 0a 20 2a 09 54 68 * Results:. *.Th
52c0: 65 20 72 65 74 75 72 6e 20 76 61 6c 75 65 20 69 e return value i
52d0: 73 20 61 20 6f 6e 65 2d 77 6f 72 64 20 73 75 6d s a one-word sum
52e0: 6d 61 72 79 20 6f 66 20 74 68 65 20 69 6e 66 6f mary of the info
52f0: 72 6d 61 74 69 6f 6e 20 69 6e 0a 20 2a 09 73 74 rmation in. *.st
5300: 72 69 6e 67 2e 0a 20 2a 0a 20 2a 20 53 69 64 65 ring.. *. * Side
5310: 20 65 66 66 65 63 74 73 3a 0a 20 2a 09 4e 6f 6e effects:. *.Non
5320: 65 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d e.. *. *--------
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 2d ----------------
5360: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 --------------.
5370: 2a 2f 0a 0a 73 74 61 74 69 63 20 75 6e 73 69 67 */..static unsig
5380: 6e 65 64 20 69 6e 74 0a 48 61 73 68 41 72 72 61 ned int.HashArra
5390: 79 4b 65 79 28 0a 20 20 20 20 54 63 6c 5f 48 61 yKey(. Tcl_Ha
53a0: 73 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 50 74 shTable *tablePt
53b0: 72 2c 09 2f 2a 20 48 61 73 68 20 74 61 62 6c 65 r,./* Hash table
53c0: 2e 20 2a 2f 0a 20 20 20 20 76 6f 69 64 20 2a 6b . */. void *k
53d0: 65 79 50 74 72 29 09 09 2f 2a 20 4b 65 79 20 66 eyPtr)../* Key f
53e0: 72 6f 6d 20 77 68 69 63 68 20 74 6f 20 63 6f 6d rom which to com
53f0: 70 75 74 65 20 68 61 73 68 20 76 61 6c 75 65 2e pute hash value.
5400: 20 2a 2f 0a 7b 0a 20 20 20 20 63 6f 6e 73 74 20 */.{. const
5410: 69 6e 74 20 2a 61 72 72 61 79 20 3d 20 28 63 6f int *array = (co
5420: 6e 73 74 20 69 6e 74 20 2a 29 20 6b 65 79 50 74 nst int *) keyPt
5430: 72 3b 0a 20 20 20 20 75 6e 73 69 67 6e 65 64 20 r;. unsigned
5440: 69 6e 74 20 72 65 73 75 6c 74 3b 0a 20 20 20 20 int result;.
5450: 69 6e 74 20 63 6f 75 6e 74 3b 0a 0a 20 20 20 20 int count;..
5460: 66 6f 72 20 28 72 65 73 75 6c 74 20 3d 20 30 2c for (result = 0,
5470: 20 63 6f 75 6e 74 20 3d 20 74 61 62 6c 65 50 74 count = tablePt
5480: 72 2d 3e 6b 65 79 54 79 70 65 3b 20 63 6f 75 6e r->keyType; coun
5490: 74 20 3e 20 30 3b 0a 09 20 20 20 20 63 6f 75 6e t > 0;.. coun
54a0: 74 2d 2d 2c 20 61 72 72 61 79 2b 2b 29 20 7b 0a t--, array++) {.
54b0: 09 72 65 73 75 6c 74 20 2b 3d 20 2a 61 72 72 61 .result += *arra
54c0: 79 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72 65 74 y;. }. ret
54d0: 75 72 6e 20 72 65 73 75 6c 74 3b 0a 7d 0a 0c 0a urn result;.}...
54e0: 2f 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d /*. *-----------
54f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5500: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5510: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5520: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 -----------. *.
5530: 2a 20 41 6c 6c 6f 63 53 74 72 69 6e 67 45 6e 74 * AllocStringEnt
5540: 72 79 20 2d 2d 0a 20 2a 0a 20 2a 09 41 6c 6c 6f ry --. *. *.Allo
5550: 63 61 74 65 20 73 70 61 63 65 20 66 6f 72 20 61 cate space for a
5560: 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 63 Tcl_HashEntry c
5570: 6f 6e 74 61 69 6e 69 6e 67 20 74 68 65 20 73 74 ontaining the st
5580: 72 69 6e 67 20 6b 65 79 2e 0a 20 2a 0a 20 2a 20 ring key.. *. *
5590: 52 65 73 75 6c 74 73 3a 0a 20 2a 09 54 68 65 20 Results:. *.The
55a0: 72 65 74 75 72 6e 20 76 61 6c 75 65 20 69 73 20 return value is
55b0: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 a pointer to the
55c0: 20 63 72 65 61 74 65 64 20 65 6e 74 72 79 2e 0a created entry..
55d0: 20 2a 0a 20 2a 20 53 69 64 65 20 65 66 66 65 63 *. * Side effec
55e0: 74 73 3a 0a 20 2a 09 4e 6f 6e 65 2e 0a 20 2a 0a ts:. *.None.. *.
55f0: 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *--------------
5600: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5610: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5620: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5630: 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 2f 0a 0a 73 74 --------. */..st
5640: 61 74 69 63 20 54 63 6c 5f 48 61 73 68 45 6e 74 atic Tcl_HashEnt
5650: 72 79 20 2a 0a 41 6c 6c 6f 63 53 74 72 69 6e 67 ry *.AllocString
5660: 45 6e 74 72 79 28 0a 20 20 20 20 54 63 6c 5f 48 Entry(. Tcl_H
5670: 61 73 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 50 ashTable *tableP
5680: 74 72 2c 09 2f 2a 20 48 61 73 68 20 74 61 62 6c tr,./* Hash tabl
5690: 65 2e 20 2a 2f 0a 20 20 20 20 76 6f 69 64 20 2a e. */. void *
56a0: 6b 65 79 50 74 72 29 09 09 2f 2a 20 4b 65 79 20 keyPtr)../* Key
56b0: 74 6f 20 73 74 6f 72 65 20 69 6e 20 74 68 65 20 to store in the
56c0: 68 61 73 68 20 74 61 62 6c 65 20 65 6e 74 72 79 hash table entry
56d0: 2e 20 2a 2f 0a 7b 0a 20 20 20 20 63 6f 6e 73 74 . */.{. const
56e0: 20 63 68 61 72 20 2a 73 74 72 69 6e 67 20 3d 20 char *string =
56f0: 28 63 6f 6e 73 74 20 63 68 61 72 20 2a 29 20 6b (const char *) k
5700: 65 79 50 74 72 3b 0a 20 20 20 20 54 63 6c 5f 48 eyPtr;. Tcl_H
5710: 61 73 68 45 6e 74 72 79 20 2a 68 50 74 72 3b 0a ashEntry *hPtr;.
5720: 20 20 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 unsigned int
5730: 20 73 69 7a 65 2c 20 61 6c 6c 6f 63 73 69 7a 65 size, allocsize
5740: 3b 0a 0a 20 20 20 20 61 6c 6c 6f 63 73 69 7a 65 ;.. allocsize
5750: 20 3d 20 73 69 7a 65 20 3d 20 73 74 72 6c 65 6e = size = strlen
5760: 28 73 74 72 69 6e 67 29 20 2b 20 31 3b 0a 20 20 (string) + 1;.
5770: 20 20 69 66 20 28 73 69 7a 65 20 3c 20 73 69 7a if (size < siz
5780: 65 6f 66 28 68 50 74 72 2d 3e 6b 65 79 29 29 20 eof(hPtr->key))
5790: 7b 0a 09 61 6c 6c 6f 63 73 69 7a 65 20 3d 20 73 {..allocsize = s
57a0: 69 7a 65 6f 66 28 68 50 74 72 2d 3e 6b 65 79 29 izeof(hPtr->key)
57b0: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 68 50 74 72 ;. }. hPtr
57c0: 20 3d 20 63 6b 61 6c 6c 6f 63 28 54 63 6c 4f 66 = ckalloc(TclOf
57d0: 66 73 65 74 28 54 63 6c 5f 48 61 73 68 45 6e 74 fset(Tcl_HashEnt
57e0: 72 79 2c 20 6b 65 79 29 20 2b 20 61 6c 6c 6f 63 ry, key) + alloc
57f0: 73 69 7a 65 29 3b 0a 20 20 20 20 6d 65 6d 73 65 size);. memse
5800: 74 28 68 50 74 72 2c 20 30 2c 20 54 63 6c 4f 66 t(hPtr, 0, TclOf
5810: 66 73 65 74 28 54 63 6c 5f 48 61 73 68 45 6e 74 fset(Tcl_HashEnt
5820: 72 79 2c 20 6b 65 79 29 20 2b 20 61 6c 6c 6f 63 ry, key) + alloc
5830: 73 69 7a 65 29 3b 0a 20 20 20 20 6d 65 6d 63 70 size);. memcp
5840: 79 28 68 50 74 72 2d 3e 6b 65 79 2e 73 74 72 69 y(hPtr->key.stri
5850: 6e 67 2c 20 73 74 72 69 6e 67 2c 20 73 69 7a 65 ng, string, size
5860: 29 3b 0a 20 20 20 20 68 50 74 72 2d 3e 63 6c 69 );. hPtr->cli
5870: 65 6e 74 44 61 74 61 20 3d 20 30 3b 0a 20 20 20 entData = 0;.
5880: 20 72 65 74 75 72 6e 20 68 50 74 72 3b 0a 7d 0a return hPtr;.}.
5890: 0c 0a 2f 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d ../*. *---------
58a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
58b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
58c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
58d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a -------------. *
58e0: 0a 20 2a 20 43 6f 6d 70 61 72 65 53 74 72 69 6e . * CompareStrin
58f0: 67 4b 65 79 73 20 2d 2d 0a 20 2a 0a 20 2a 09 43 gKeys --. *. *.C
5900: 6f 6d 70 61 72 65 73 20 74 77 6f 20 73 74 72 69 ompares two stri
5910: 6e 67 20 6b 65 79 73 2e 0a 20 2a 0a 20 2a 20 52 ng keys.. *. * R
5920: 65 73 75 6c 74 73 3a 0a 20 2a 09 54 68 65 20 72 esults:. *.The r
5930: 65 74 75 72 6e 20 76 61 6c 75 65 20 69 73 20 30 eturn value is 0
5940: 20 69 66 20 74 68 65 79 20 61 72 65 20 64 69 66 if they are dif
5950: 66 65 72 65 6e 74 20 61 6e 64 20 31 20 69 66 20 ferent and 1 if
5960: 74 68 65 79 20 61 72 65 20 74 68 65 0a 20 2a 09 they are the. *.
5970: 73 61 6d 65 2e 0a 20 2a 0a 20 2a 20 53 69 64 65 same.. *. * Side
5980: 20 65 66 66 65 63 74 73 3a 0a 20 2a 09 4e 6f 6e effects:. *.Non
5990: 65 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d e.. *. *--------
59a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
59b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
59c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
59d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 --------------.
59e0: 2a 2f 0a 0a 73 74 61 74 69 63 20 69 6e 74 0a 43 */..static int.C
59f0: 6f 6d 70 61 72 65 53 74 72 69 6e 67 4b 65 79 73 ompareStringKeys
5a00: 28 0a 20 20 20 20 76 6f 69 64 20 2a 6b 65 79 50 (. void *keyP
5a10: 74 72 2c 09 09 2f 2a 20 4e 65 77 20 6b 65 79 20 tr,../* New key
5a20: 74 6f 20 63 6f 6d 70 61 72 65 2e 20 2a 2f 0a 20 to compare. */.
5a30: 20 20 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 Tcl_HashEntry
5a40: 20 2a 68 50 74 72 29 09 2f 2a 20 45 78 69 73 74 *hPtr)./* Exist
5a50: 69 6e 67 20 6b 65 79 20 74 6f 20 63 6f 6d 70 61 ing key to compa
5a60: 72 65 2e 20 2a 2f 0a 7b 0a 20 20 20 20 63 6f 6e re. */.{. con
5a70: 73 74 20 63 68 61 72 20 2a 70 31 20 3d 20 28 63 st char *p1 = (c
5a80: 6f 6e 73 74 20 63 68 61 72 20 2a 29 20 6b 65 79 onst char *) key
5a90: 50 74 72 3b 0a 20 20 20 20 63 6f 6e 73 74 20 63 Ptr;. const c
5aa0: 68 61 72 20 2a 70 32 20 3d 20 28 63 6f 6e 73 74 har *p2 = (const
5ab0: 20 63 68 61 72 20 2a 29 20 68 50 74 72 2d 3e 6b char *) hPtr->k
5ac0: 65 79 2e 73 74 72 69 6e 67 3b 0a 0a 20 20 20 20 ey.string;..
5ad0: 72 65 74 75 72 6e 20 21 73 74 72 63 6d 70 28 70 return !strcmp(p
5ae0: 31 2c 20 70 32 29 3b 0a 7d 0a 0c 0a 2f 2a 0a 20 1, p2);.}.../*.
5af0: 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *---------------
5b00: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5b10: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5b20: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5b30: 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 48 61 -------. *. * Ha
5b40: 73 68 53 74 72 69 6e 67 4b 65 79 20 2d 2d 0a 20 shStringKey --.
5b50: 2a 0a 20 2a 09 43 6f 6d 70 75 74 65 20 61 20 6f *. *.Compute a o
5b60: 6e 65 2d 77 6f 72 64 20 73 75 6d 6d 61 72 79 20 ne-word summary
5b70: 6f 66 20 61 20 74 65 78 74 20 73 74 72 69 6e 67 of a text string
5b80: 2c 20 77 68 69 63 68 20 63 61 6e 20 62 65 20 75 , which can be u
5b90: 73 65 64 20 74 6f 0a 20 2a 09 67 65 6e 65 72 61 sed to. *.genera
5ba0: 74 65 20 61 20 68 61 73 68 20 69 6e 64 65 78 2e te a hash index.
5bb0: 0a 20 2a 0a 20 2a 20 52 65 73 75 6c 74 73 3a 0a . *. * Results:.
5bc0: 20 2a 09 54 68 65 20 72 65 74 75 72 6e 20 76 61 *.The return va
5bd0: 6c 75 65 20 69 73 20 61 20 6f 6e 65 2d 77 6f 72 lue is a one-wor
5be0: 64 20 73 75 6d 6d 61 72 79 20 6f 66 20 74 68 65 d summary of the
5bf0: 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 69 6e 20 information in
5c00: 73 74 72 69 6e 67 2e 0a 20 2a 0a 20 2a 20 53 69 string.. *. * Si
5c10: 64 65 20 65 66 66 65 63 74 73 3a 0a 20 2a 09 4e de effects:. *.N
5c20: 6f 6e 65 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d one.. *. *------
5c30: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5c40: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5c50: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5c60: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
5c70: 0a 20 2a 2f 0a 0a 73 74 61 74 69 63 20 75 6e 73 . */..static uns
5c80: 69 67 6e 65 64 0a 48 61 73 68 53 74 72 69 6e 67 igned.HashString
5c90: 4b 65 79 28 0a 20 20 20 20 54 63 6c 5f 48 61 73 Key(. Tcl_Has
5ca0: 68 54 61 62 6c 65 20 2a 74 61 62 6c 65 50 74 72 hTable *tablePtr
5cb0: 2c 09 2f 2a 20 48 61 73 68 20 74 61 62 6c 65 2e ,./* Hash table.
5cc0: 20 2a 2f 0a 20 20 20 20 76 6f 69 64 20 2a 6b 65 */. void *ke
5cd0: 79 50 74 72 29 09 09 2f 2a 20 4b 65 79 20 66 72 yPtr)../* Key fr
5ce0: 6f 6d 20 77 68 69 63 68 20 74 6f 20 63 6f 6d 70 om which to comp
5cf0: 75 74 65 20 68 61 73 68 20 76 61 6c 75 65 2e 20 ute hash value.
5d00: 2a 2f 0a 7b 0a 20 20 20 20 63 6f 6e 73 74 20 63 */.{. const c
5d10: 68 61 72 20 2a 73 74 72 69 6e 67 20 3d 20 6b 65 har *string = ke
5d20: 79 50 74 72 3b 0a 20 20 20 20 75 6e 73 69 67 6e yPtr;. unsign
5d30: 65 64 20 69 6e 74 20 72 65 73 75 6c 74 3b 0a 20 ed int result;.
5d40: 20 20 20 63 68 61 72 20 63 3b 0a 0a 20 20 20 20 char c;..
5d50: 2f 2a 0a 20 20 20 20 20 2a 20 49 20 74 72 69 65 /*. * I trie
5d60: 64 20 61 20 7a 69 6c 6c 69 6f 6e 20 64 69 66 66 d a zillion diff
5d70: 65 72 65 6e 74 20 68 61 73 68 20 66 75 6e 63 74 erent hash funct
5d80: 69 6f 6e 73 20 61 6e 64 20 61 73 6b 65 64 20 6d ions and asked m
5d90: 61 6e 79 20 6f 74 68 65 72 20 70 65 6f 70 6c 65 any other people
5da0: 0a 20 20 20 20 20 2a 20 66 6f 72 20 61 64 76 69 . * for advi
5db0: 63 65 2e 20 4d 61 6e 79 20 70 65 6f 70 6c 65 20 ce. Many people
5dc0: 68 61 64 20 74 68 65 69 72 20 6f 77 6e 20 66 61 had their own fa
5dd0: 76 6f 72 69 74 65 20 66 75 6e 63 74 69 6f 6e 73 vorite functions
5de0: 2c 20 61 6c 6c 0a 20 20 20 20 20 2a 20 64 69 66 , all. * dif
5df0: 66 65 72 65 6e 74 2c 20 62 75 74 20 6e 6f 2d 6f ferent, but no-o
5e00: 6e 65 20 68 61 64 20 6d 75 63 68 20 69 64 65 61 ne had much idea
5e10: 20 77 68 79 20 74 68 65 79 20 77 65 72 65 20 67 why they were g
5e20: 6f 6f 64 20 6f 6e 65 73 2e 20 49 20 63 68 6f 73 ood ones. I chos
5e30: 65 0a 20 20 20 20 20 2a 20 74 68 65 20 6f 6e 65 e. * the one
5e40: 20 62 65 6c 6f 77 20 28 6d 75 6c 74 69 70 6c 79 below (multiply
5e50: 20 62 79 20 39 20 61 6e 64 20 61 64 64 20 6e 65 by 9 and add ne
5e60: 77 20 63 68 61 72 61 63 74 65 72 29 20 62 65 63 w character) bec
5e70: 61 75 73 65 20 6f 66 20 74 68 65 0a 20 20 20 20 ause of the.
5e80: 20 2a 20 66 6f 6c 6c 6f 77 69 6e 67 20 72 65 61 * following rea
5e90: 73 6f 6e 73 3a 0a 20 20 20 20 20 2a 0a 20 20 20 sons:. *.
5ea0: 20 20 2a 20 31 2e 20 4d 75 6c 74 69 70 6c 79 69 * 1. Multiplyi
5eb0: 6e 67 20 62 79 20 31 30 20 69 73 20 70 65 72 66 ng by 10 is perf
5ec0: 65 63 74 20 66 6f 72 20 6b 65 79 73 20 74 68 61 ect for keys tha
5ed0: 74 20 61 72 65 20 64 65 63 69 6d 61 6c 20 73 74 t are decimal st
5ee0: 72 69 6e 67 73 2c 20 61 6e 64 0a 20 20 20 20 20 rings, and.
5ef0: 2a 20 20 20 20 6d 75 6c 74 69 70 6c 79 69 6e 67 * multiplying
5f00: 20 62 79 20 39 20 69 73 20 6a 75 73 74 20 61 62 by 9 is just ab
5f10: 6f 75 74 20 61 73 20 67 6f 6f 64 2e 0a 20 20 20 out as good..
5f20: 20 20 2a 20 32 2e 20 54 69 6d 65 73 2d 39 20 69 * 2. Times-9 i
5f30: 73 20 28 73 68 69 66 74 2d 6c 65 66 74 2d 33 29 s (shift-left-3)
5f40: 20 70 6c 75 73 20 28 6f 6c 64 29 2e 20 54 68 69 plus (old). Thi
5f50: 73 20 6d 65 61 6e 73 20 74 68 61 74 20 65 61 63 s means that eac
5f60: 68 0a 20 20 20 20 20 2a 20 20 20 20 63 68 61 72 h. * char
5f70: 61 63 74 65 72 27 73 20 62 69 74 73 20 68 61 6e acter's bits han
5f80: 67 20 61 72 6f 75 6e 64 20 69 6e 20 74 68 65 20 g around in the
5f90: 6c 6f 77 2d 6f 72 64 65 72 20 62 69 74 73 20 6f low-order bits o
5fa0: 66 20 74 68 65 20 68 61 73 68 20 76 61 6c 75 65 f the hash value
5fb0: 0a 20 20 20 20 20 2a 20 20 20 20 66 6f 72 20 65 . * for e
5fc0: 76 65 72 2c 20 70 6c 75 73 20 74 68 65 79 20 73 ver, plus they s
5fd0: 70 72 65 61 64 20 66 61 69 72 6c 79 20 72 61 70 pread fairly rap
5fe0: 69 64 6c 79 20 75 70 20 74 6f 20 74 68 65 20 68 idly up to the h
5ff0: 69 67 68 2d 6f 72 64 65 72 20 62 69 74 73 0a 20 igh-order bits.
6000: 20 20 20 20 2a 20 20 20 20 74 6f 20 66 69 6c 6c * to fill
6010: 20 6f 75 74 20 74 68 65 20 68 61 73 68 20 76 61 out the hash va
6020: 6c 75 65 2e 20 54 68 69 73 20 73 65 65 6d 73 20 lue. This seems
6030: 77 6f 72 6b 73 20 77 65 6c 6c 20 62 6f 74 68 20 works well both
6040: 66 6f 72 20 64 65 63 69 6d 61 6c 0a 20 20 20 20 for decimal.
6050: 20 2a 20 20 20 20 61 6e 64 20 6e 6f 6e 2d 64 65 * and non-de
6060: 63 69 6d 61 6c 20 73 74 72 69 6e 67 73 2c 20 62 cimal strings, b
6070: 75 74 20 69 73 6e 27 74 20 73 74 72 6f 6e 67 20 ut isn't strong
6080: 61 67 61 69 6e 73 74 20 6d 61 6c 69 63 69 6f 75 against maliciou
6090: 73 6c 79 2d 63 68 6f 73 65 6e 0a 20 20 20 20 20 sly-chosen.
60a0: 2a 20 20 20 20 6b 65 79 73 2e 0a 20 20 20 20 20 * keys..
60b0: 2a 0a 20 20 20 20 20 2a 20 4e 6f 74 65 20 74 68 *. * Note th
60c0: 61 74 20 74 68 69 73 20 66 75 6e 63 74 69 6f 6e at this function
60d0: 20 69 73 20 76 65 72 79 20 77 65 61 6b 20 61 67 is very weak ag
60e0: 61 69 6e 73 74 20 6d 61 6c 69 63 69 6f 75 73 20 ainst malicious
60f0: 73 74 72 69 6e 67 73 3b 20 69 74 27 73 0a 20 20 strings; it's.
6100: 20 20 20 2a 20 76 65 72 79 20 65 61 73 79 20 74 * very easy t
6110: 6f 20 67 65 6e 65 72 61 74 65 20 6d 75 6c 74 69 o generate multi
6120: 70 6c 65 20 6b 65 79 73 20 74 68 61 74 20 68 61 ple keys that ha
6130: 76 65 20 74 68 65 20 73 61 6d 65 20 68 61 73 68 ve the same hash
6140: 63 6f 64 65 2e 20 4f 6e 20 74 68 65 0a 20 20 20 code. On the.
6150: 20 20 2a 20 6f 74 68 65 72 20 68 61 6e 64 2c 20 * other hand,
6160: 74 68 61 74 20 68 61 72 64 6c 79 20 65 76 65 72 that hardly ever
6170: 20 61 63 74 75 61 6c 6c 79 20 6f 63 63 75 72 73 actually occurs
6180: 20 61 6e 64 20 74 68 69 73 20 66 75 6e 63 74 69 and this functi
6190: 6f 6e 20 2a 69 73 2a 0a 20 20 20 20 20 2a 20 76 on *is*. * v
61a0: 65 72 79 20 63 68 65 61 70 2c 20 65 76 65 6e 20 ery cheap, even
61b0: 62 79 20 63 6f 6d 70 61 72 69 73 6f 6e 20 77 69 by comparison wi
61c0: 74 68 20 69 6e 64 75 73 74 72 79 2d 73 74 61 6e th industry-stan
61d0: 64 61 72 64 20 68 61 73 68 65 73 20 6c 69 6b 65 dard hashes like
61e0: 20 46 4e 56 2e 0a 20 20 20 20 20 2a 20 49 66 20 FNV.. * If
61f0: 72 65 61 6c 20 73 74 72 65 6e 67 74 68 20 6f 66 real strength of
6200: 20 68 61 73 68 20 69 73 20 72 65 71 75 69 72 65 hash is require
6210: 64 20 74 68 6f 75 67 68 2c 20 75 73 65 20 61 20 d though, use a
6220: 63 75 73 74 6f 6d 20 68 61 73 68 20 62 61 73 65 custom hash base
6230: 64 20 6f 6e 0a 20 20 20 20 20 2a 20 42 6f 62 20 d on. * Bob
6240: 4a 65 6e 6b 69 6e 73 27 73 20 6c 6f 6f 6b 75 70 Jenkins's lookup
6250: 33 28 29 2c 20 62 75 74 20 62 65 20 61 77 61 72 3(), but be awar
6260: 65 20 74 68 61 74 20 69 74 27 73 20 73 69 67 6e e that it's sign
6270: 69 66 69 63 61 6e 74 6c 79 20 73 6c 6f 77 65 72 ificantly slower
6280: 2e 0a 20 20 20 20 20 2a 20 53 69 6e 63 65 20 54 .. * Since T
6290: 63 6c 20 63 6f 6d 6d 61 6e 64 20 61 6e 64 20 6e cl command and n
62a0: 61 6d 65 73 70 61 63 65 20 6e 61 6d 65 73 20 61 amespace names a
62b0: 72 65 20 75 73 75 61 6c 6c 79 20 72 65 61 73 6f re usually reaso
62c0: 6e 61 62 6c 79 2d 6e 61 6d 65 64 20 28 74 68 65 nably-named (the
62d0: 0a 20 20 20 20 20 2a 20 6d 61 69 6e 20 75 73 65 . * main use
62e0: 20 66 6f 72 20 73 74 72 69 6e 67 20 68 61 73 68 for string hash
62f0: 65 73 20 69 6e 20 6d 6f 64 65 72 6e 20 54 63 6c es in modern Tcl
6300: 29 20 73 70 65 65 64 20 69 73 20 66 61 72 20 6d ) speed is far m
6310: 6f 72 65 20 69 6d 70 6f 72 74 61 6e 74 0a 20 20 ore important.
6320: 20 20 20 2a 20 74 68 61 6e 20 73 74 72 65 6e 67 * than streng
6330: 74 68 2e 0a 20 20 20 20 20 2a 0a 20 20 20 20 20 th.. *.
6340: 2a 20 53 65 65 20 61 6c 73 6f 20 48 61 73 68 53 * See also HashS
6350: 74 72 69 6e 67 20 69 6e 20 74 63 6c 4c 69 74 65 tring in tclLite
6360: 72 61 6c 2e 63 2e 0a 20 20 20 20 20 2a 20 53 65 ral.c.. * Se
6370: 65 20 61 6c 73 6f 20 54 63 6c 4f 62 6a 48 61 73 e also TclObjHas
6380: 68 4b 65 79 20 69 6e 20 74 63 6c 4f 62 6a 2e 63 hKey in tclObj.c
6390: 2e 0a 20 20 20 20 20 2a 0a 20 20 20 20 20 2a 20 .. *. *
63a0: 53 65 65 20 5b 74 63 6c 2d 46 65 61 74 75 72 65 See [tcl-Feature
63b0: 20 52 65 71 75 65 73 74 20 23 32 39 35 38 38 33 Request #295883
63c0: 32 5d 0a 20 20 20 20 20 2a 2f 0a 0a 20 20 20 20 2]. */..
63d0: 69 66 20 28 28 72 65 73 75 6c 74 20 3d 20 55 43 if ((result = UC
63e0: 48 41 52 28 2a 73 74 72 69 6e 67 29 29 20 21 3d HAR(*string)) !=
63f0: 20 30 29 20 7b 0a 09 77 68 69 6c 65 20 28 28 63 0) {..while ((c
6400: 20 3d 20 2a 2b 2b 73 74 72 69 6e 67 29 20 21 3d = *++string) !=
6410: 20 30 29 20 7b 0a 09 20 20 20 20 72 65 73 75 6c 0) {.. resul
6420: 74 20 2b 3d 20 28 72 65 73 75 6c 74 20 3c 3c 20 t += (result <<
6430: 33 29 20 2b 20 55 43 48 41 52 28 63 29 3b 0a 09 3) + UCHAR(c);..
6440: 7d 0a 20 20 20 20 7d 0a 20 20 20 20 72 65 74 75 }. }. retu
6450: 72 6e 20 72 65 73 75 6c 74 3b 0a 7d 0a 0c 0a 2f rn result;.}.../
6460: 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *. *------------
6470: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6480: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6490: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
64a0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a ----------. *. *
64b0: 20 42 6f 67 75 73 46 69 6e 64 20 2d 2d 0a 20 2a BogusFind --. *
64c0: 0a 20 2a 09 54 68 69 73 20 66 75 6e 63 74 69 6f . *.This functio
64d0: 6e 20 69 73 20 69 6e 76 6f 6b 65 64 20 77 68 65 n is invoked whe
64e0: 6e 20 61 6e 20 54 63 6c 5f 46 69 6e 64 48 61 73 n an Tcl_FindHas
64f0: 68 45 6e 74 72 79 20 69 73 20 63 61 6c 6c 65 64 hEntry is called
6500: 20 6f 6e 20 61 0a 20 2a 09 74 61 62 6c 65 20 74 on a. *.table t
6510: 68 61 74 20 68 61 73 20 62 65 65 6e 20 64 65 6c hat has been del
6520: 65 74 65 64 2e 0a 20 2a 0a 20 2a 20 52 65 73 75 eted.. *. * Resu
6530: 6c 74 73 3a 0a 20 2a 09 49 66 20 54 63 6c 5f 50 lts:. *.If Tcl_P
6540: 61 6e 69 63 20 72 65 74 75 72 6e 73 20 28 77 68 anic returns (wh
6550: 69 63 68 20 69 74 20 73 68 6f 75 6c 64 6e 27 74 ich it shouldn't
6560: 29 20 74 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 ) this function
6570: 72 65 74 75 72 6e 73 20 4e 55 4c 4c 2e 0a 20 2a returns NULL.. *
6580: 0a 20 2a 20 53 69 64 65 20 65 66 66 65 63 74 73 . * Side effects
6590: 3a 0a 20 2a 09 47 65 6e 65 72 61 74 65 73 20 61 :. *.Generates a
65a0: 20 70 61 6e 69 63 2e 0a 20 2a 0a 20 2a 2d 2d 2d panic.. *. *---
65b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
65c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
65d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
65e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
65f0: 2d 2d 2d 0a 20 2a 2f 0a 0a 09 2f 2a 20 41 52 47 ---. */.../* ARG
6600: 53 55 53 45 44 20 2a 2f 0a 73 74 61 74 69 63 20 SUSED */.static
6610: 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 2a 0a Tcl_HashEntry *.
6620: 42 6f 67 75 73 46 69 6e 64 28 0a 20 20 20 20 54 BogusFind(. T
6630: 63 6c 5f 48 61 73 68 54 61 62 6c 65 20 2a 74 61 cl_HashTable *ta
6640: 62 6c 65 50 74 72 2c 09 2f 2a 20 54 61 62 6c 65 blePtr,./* Table
6650: 20 69 6e 20 77 68 69 63 68 20 74 6f 20 6c 6f 6f in which to loo
6660: 6b 75 70 20 65 6e 74 72 79 2e 20 2a 2f 0a 20 20 kup entry. */.
6670: 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 6b 65 const char *ke
6680: 79 29 09 09 2f 2a 20 4b 65 79 20 74 6f 20 75 73 y)../* Key to us
6690: 65 20 74 6f 20 66 69 6e 64 20 6d 61 74 63 68 69 e to find matchi
66a0: 6e 67 20 65 6e 74 72 79 2e 20 2a 2f 0a 7b 0a 20 ng entry. */.{.
66b0: 20 20 20 54 63 6c 5f 50 61 6e 69 63 28 22 63 61 Tcl_Panic("ca
66c0: 6c 6c 65 64 20 25 73 20 6f 6e 20 64 65 6c 65 74 lled %s on delet
66d0: 65 64 20 74 61 62 6c 65 22 2c 20 22 54 63 6c 5f ed table", "Tcl_
66e0: 46 69 6e 64 48 61 73 68 45 6e 74 72 79 22 29 3b FindHashEntry");
66f0: 0a 20 20 20 20 72 65 74 75 72 6e 20 4e 55 4c 4c . return NULL
6700: 3b 0a 7d 0a 0c 0a 2f 2a 0a 20 2a 2d 2d 2d 2d 2d ;.}.../*. *-----
6710: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6720: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6730: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6740: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6750: 2d 0a 20 2a 0a 20 2a 20 42 6f 67 75 73 43 72 65 -. *. * BogusCre
6760: 61 74 65 20 2d 2d 0a 20 2a 0a 20 2a 09 54 68 69 ate --. *. *.Thi
6770: 73 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 69 6e s function is in
6780: 76 6f 6b 65 64 20 77 68 65 6e 20 61 6e 20 54 63 voked when an Tc
6790: 6c 5f 43 72 65 61 74 65 48 61 73 68 45 6e 74 72 l_CreateHashEntr
67a0: 79 20 69 73 20 63 61 6c 6c 65 64 20 6f 6e 20 61 y is called on a
67b0: 0a 20 2a 09 74 61 62 6c 65 20 74 68 61 74 20 68 . *.table that h
67c0: 61 73 20 62 65 65 6e 20 64 65 6c 65 74 65 64 2e as been deleted.
67d0: 0a 20 2a 0a 20 2a 20 52 65 73 75 6c 74 73 3a 0a . *. * Results:.
67e0: 20 2a 09 49 66 20 70 61 6e 69 63 20 72 65 74 75 *.If panic retu
67f0: 72 6e 73 20 28 77 68 69 63 68 20 69 74 20 73 68 rns (which it sh
6800: 6f 75 6c 64 6e 27 74 29 20 74 68 69 73 20 66 75 ouldn't) this fu
6810: 6e 63 74 69 6f 6e 20 72 65 74 75 72 6e 73 20 4e nction returns N
6820: 55 4c 4c 2e 0a 20 2a 0a 20 2a 20 53 69 64 65 20 ULL.. *. * Side
6830: 65 66 66 65 63 74 73 3a 0a 20 2a 09 47 65 6e 65 effects:. *.Gene
6840: 72 61 74 65 73 20 61 20 70 61 6e 69 63 2e 0a 20 rates a panic..
6850: 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d *. *------------
6860: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6870: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6880: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6890: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a 2f 0a 0a ----------. */..
68a0: 09 2f 2a 20 41 52 47 53 55 53 45 44 20 2a 2f 0a ./* ARGSUSED */.
68b0: 73 74 61 74 69 63 20 54 63 6c 5f 48 61 73 68 45 static Tcl_HashE
68c0: 6e 74 72 79 20 2a 0a 42 6f 67 75 73 43 72 65 61 ntry *.BogusCrea
68d0: 74 65 28 0a 20 20 20 20 54 63 6c 5f 48 61 73 68 te(. Tcl_Hash
68e0: 54 61 62 6c 65 20 2a 74 61 62 6c 65 50 74 72 2c Table *tablePtr,
68f0: 09 2f 2a 20 54 61 62 6c 65 20 69 6e 20 77 68 69 ./* Table in whi
6900: 63 68 20 74 6f 20 6c 6f 6f 6b 75 70 20 65 6e 74 ch to lookup ent
6910: 72 79 2e 20 2a 2f 0a 20 20 20 20 63 6f 6e 73 74 ry. */. const
6920: 20 63 68 61 72 20 2a 6b 65 79 2c 09 09 2f 2a 20 char *key,../*
6930: 4b 65 79 20 74 6f 20 75 73 65 20 74 6f 20 66 69 Key to use to fi
6940: 6e 64 20 6f 72 20 63 72 65 61 74 65 20 6d 61 74 nd or create mat
6950: 63 68 69 6e 67 0a 09 09 09 09 20 2a 20 65 6e 74 ching..... * ent
6960: 72 79 2e 20 2a 2f 0a 20 20 20 20 69 6e 74 20 2a ry. */. int *
6970: 6e 65 77 50 74 72 29 09 09 2f 2a 20 53 74 6f 72 newPtr)../* Stor
6980: 65 20 69 6e 66 6f 20 68 65 72 65 20 74 65 6c 6c e info here tell
6990: 69 6e 67 20 77 68 65 74 68 65 72 20 61 20 6e 65 ing whether a ne
69a0: 77 20 65 6e 74 72 79 0a 09 09 09 09 20 2a 20 77 w entry..... * w
69b0: 61 73 20 63 72 65 61 74 65 64 2e 20 2a 2f 0a 7b as created. */.{
69c0: 0a 20 20 20 20 54 63 6c 5f 50 61 6e 69 63 28 22 . Tcl_Panic("
69d0: 63 61 6c 6c 65 64 20 25 73 20 6f 6e 20 64 65 6c called %s on del
69e0: 65 74 65 64 20 74 61 62 6c 65 22 2c 20 22 54 63 eted table", "Tc
69f0: 6c 5f 43 72 65 61 74 65 48 61 73 68 45 6e 74 72 l_CreateHashEntr
6a00: 79 22 29 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 y");. return
6a10: 4e 55 4c 4c 3b 0a 7d 0a 0c 0a 2f 2a 0a 20 2a 2d NULL;.}.../*. *-
6a20: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6a30: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6a40: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6a50: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6a60: 2d 2d 2d 2d 2d 0a 20 2a 0a 20 2a 20 52 65 62 75 -----. *. * Rebu
6a70: 69 6c 64 54 61 62 6c 65 20 2d 2d 0a 20 2a 0a 20 ildTable --. *.
6a80: 2a 09 54 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 *.This function
6a90: 69 73 20 69 6e 76 6f 6b 65 64 20 77 68 65 6e 20 is invoked when
6aa0: 74 68 65 20 72 61 74 69 6f 20 6f 66 20 65 6e 74 the ratio of ent
6ab0: 72 69 65 73 20 74 6f 20 68 61 73 68 20 62 75 63 ries to hash buc
6ac0: 6b 65 74 73 0a 20 2a 09 62 65 63 6f 6d 65 73 20 kets. *.becomes
6ad0: 74 6f 6f 20 6c 61 72 67 65 2e 20 49 74 20 63 72 too large. It cr
6ae0: 65 61 74 65 73 20 61 20 6e 65 77 20 74 61 62 6c eates a new tabl
6af0: 65 20 77 69 74 68 20 61 20 6c 61 72 67 65 72 20 e with a larger
6b00: 62 75 63 6b 65 74 20 61 72 72 61 79 0a 20 2a 09 bucket array. *.
6b10: 61 6e 64 20 6d 6f 76 65 73 20 61 6c 6c 20 6f 66 and moves all of
6b20: 20 74 68 65 20 65 6e 74 72 69 65 73 20 69 6e 74 the entries int
6b30: 6f 20 74 68 65 20 6e 65 77 20 74 61 62 6c 65 2e o the new table.
6b40: 0a 20 2a 0a 20 2a 20 52 65 73 75 6c 74 73 3a 0a . *. * Results:.
6b50: 20 2a 09 4e 6f 6e 65 2e 0a 20 2a 0a 20 2a 20 53 *.None.. *. * S
6b60: 69 64 65 20 65 66 66 65 63 74 73 3a 0a 20 2a 09 ide effects:. *.
6b70: 4d 65 6d 6f 72 79 20 67 65 74 73 20 72 65 61 6c Memory gets real
6b80: 6c 6f 63 61 74 65 64 20 61 6e 64 20 65 6e 74 72 located and entr
6b90: 69 65 73 20 67 65 74 20 72 65 2d 68 61 73 68 65 ies get re-hashe
6ba0: 64 20 74 6f 20 6e 65 77 20 62 75 63 6b 65 74 73 d to new buckets
6bb0: 2e 0a 20 2a 0a 20 2a 2d 2d 2d 2d 2d 2d 2d 2d 2d .. *. *---------
6bc0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6bd0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6be0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
6bf0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 20 2a -------------. *
6c00: 2f 0a 0a 73 74 61 74 69 63 20 76 6f 69 64 0a 52 /..static void.R
6c10: 65 62 75 69 6c 64 54 61 62 6c 65 28 0a 20 20 20 ebuildTable(.
6c20: 20 54 63 6c 5f 48 61 73 68 54 61 62 6c 65 20 2a Tcl_HashTable *
6c30: 74 61 62 6c 65 50 74 72 29 09 2f 2a 20 54 61 62 tablePtr)./* Tab
6c40: 6c 65 20 74 6f 20 65 6e 6c 61 72 67 65 2e 20 2a le to enlarge. *
6c50: 2f 0a 7b 0a 20 20 20 20 69 6e 74 20 63 6f 75 6e /.{. int coun
6c60: 74 2c 20 69 6e 64 65 78 2c 20 6f 6c 64 53 69 7a t, index, oldSiz
6c70: 65 20 3d 20 74 61 62 6c 65 50 74 72 2d 3e 6e 75 e = tablePtr->nu
6c80: 6d 42 75 63 6b 65 74 73 3b 0a 20 20 20 20 54 63 mBuckets;. Tc
6c90: 6c 5f 48 61 73 68 45 6e 74 72 79 20 2a 2a 6f 6c l_HashEntry **ol
6ca0: 64 42 75 63 6b 65 74 73 20 3d 20 74 61 62 6c 65 dBuckets = table
6cb0: 50 74 72 2d 3e 62 75 63 6b 65 74 73 3b 0a 20 20 Ptr->buckets;.
6cc0: 20 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 Tcl_HashEntry
6cd0: 2a 2a 6f 6c 64 43 68 61 69 6e 50 74 72 2c 20 2a **oldChainPtr, *
6ce0: 2a 6e 65 77 43 68 61 69 6e 50 74 72 3b 0a 20 20 *newChainPtr;.
6cf0: 20 20 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 Tcl_HashEntry
6d00: 2a 68 50 74 72 3b 0a 20 20 20 20 63 6f 6e 73 74 *hPtr;. const
6d10: 20 54 63 6c 5f 48 61 73 68 4b 65 79 54 79 70 65 Tcl_HashKeyType
6d20: 20 2a 74 79 70 65 50 74 72 3b 0a 0a 20 20 20 20 *typePtr;..
6d30: 2f 2a 20 41 76 6f 69 64 20 6f 75 74 67 72 6f 77 /* Avoid outgrow
6d40: 69 6e 67 20 63 61 70 61 62 69 6c 69 74 79 20 6f ing capability o
6d50: 66 20 74 68 65 20 6d 65 6d 6f 72 79 20 61 6c 6c f the memory all
6d60: 6f 63 61 74 6f 72 73 20 2a 2f 0a 20 20 20 20 69 ocators */. i
6d70: 66 20 28 6f 6c 64 53 69 7a 65 20 3e 20 28 69 6e f (oldSize > (in
6d80: 74 29 28 55 49 4e 54 5f 4d 41 58 20 2f 20 28 34 t)(UINT_MAX / (4
6d90: 20 2a 20 73 69 7a 65 6f 66 28 54 63 6c 5f 48 61 * sizeof(Tcl_Ha
6da0: 73 68 45 6e 74 72 79 20 2a 29 29 29 29 20 7b 0a shEntry *)))) {.
6db0: 09 74 61 62 6c 65 50 74 72 2d 3e 72 65 62 75 69 .tablePtr->rebui
6dc0: 6c 64 53 69 7a 65 20 3d 20 49 4e 54 5f 4d 41 58 ldSize = INT_MAX
6dd0: 3b 0a 09 72 65 74 75 72 6e 3b 0a 20 20 20 20 7d ;..return;. }
6de0: 0a 0a 20 20 20 20 69 66 20 28 74 61 62 6c 65 50 .. if (tableP
6df0: 74 72 2d 3e 6b 65 79 54 79 70 65 20 3d 3d 20 54 tr->keyType == T
6e00: 43 4c 5f 53 54 52 49 4e 47 5f 4b 45 59 53 29 20 CL_STRING_KEYS)
6e10: 7b 0a 09 74 79 70 65 50 74 72 20 3d 20 26 74 63 {..typePtr = &tc
6e20: 6c 53 74 72 69 6e 67 48 61 73 68 4b 65 79 54 79 lStringHashKeyTy
6e30: 70 65 3b 0a 20 20 20 20 7d 20 65 6c 73 65 20 69 pe;. } else i
6e40: 66 20 28 74 61 62 6c 65 50 74 72 2d 3e 6b 65 79 f (tablePtr->key
6e50: 54 79 70 65 20 3d 3d 20 54 43 4c 5f 4f 4e 45 5f Type == TCL_ONE_
6e60: 57 4f 52 44 5f 4b 45 59 53 29 20 7b 0a 09 74 79 WORD_KEYS) {..ty
6e70: 70 65 50 74 72 20 3d 20 26 74 63 6c 4f 6e 65 57 pePtr = &tclOneW
6e80: 6f 72 64 48 61 73 68 4b 65 79 54 79 70 65 3b 0a ordHashKeyType;.
6e90: 20 20 20 20 7d 20 65 6c 73 65 20 69 66 20 28 74 } else if (t
6ea0: 61 62 6c 65 50 74 72 2d 3e 6b 65 79 54 79 70 65 ablePtr->keyType
6eb0: 20 3d 3d 20 54 43 4c 5f 43 55 53 54 4f 4d 5f 54 == TCL_CUSTOM_T
6ec0: 59 50 45 5f 4b 45 59 53 0a 09 20 20 20 20 7c 7c YPE_KEYS.. ||
6ed0: 20 74 61 62 6c 65 50 74 72 2d 3e 6b 65 79 54 79 tablePtr->keyTy
6ee0: 70 65 20 3d 3d 20 54 43 4c 5f 43 55 53 54 4f 4d pe == TCL_CUSTOM
6ef0: 5f 50 54 52 5f 4b 45 59 53 29 20 7b 0a 09 74 79 _PTR_KEYS) {..ty
6f00: 70 65 50 74 72 20 3d 20 74 61 62 6c 65 50 74 72 pePtr = tablePtr
6f10: 2d 3e 74 79 70 65 50 74 72 3b 0a 20 20 20 20 7d ->typePtr;. }
6f20: 20 65 6c 73 65 20 7b 0a 09 74 79 70 65 50 74 72 else {..typePtr
6f30: 20 3d 20 26 74 63 6c 41 72 72 61 79 48 61 73 68 = &tclArrayHash
6f40: 4b 65 79 54 79 70 65 3b 0a 20 20 20 20 7d 0a 0a KeyType;. }..
6f50: 20 20 20 20 2f 2a 0a 20 20 20 20 20 2a 20 41 6c /*. * Al
6f60: 6c 6f 63 61 74 65 20 61 6e 64 20 69 6e 69 74 69 locate and initi
6f70: 61 6c 69 7a 65 20 74 68 65 20 6e 65 77 20 62 75 alize the new bu
6f80: 63 6b 65 74 20 61 72 72 61 79 2c 20 61 6e 64 20 cket array, and
6f90: 73 65 74 20 75 70 20 68 61 73 68 69 6e 67 0a 20 set up hashing.
6fa0: 20 20 20 20 2a 20 63 6f 6e 73 74 61 6e 74 73 20 * constants
6fb0: 66 6f 72 20 6e 65 77 20 61 72 72 61 79 20 73 69 for new array si
6fc0: 7a 65 2e 0a 20 20 20 20 20 2a 2f 0a 0a 20 20 20 ze.. */..
6fd0: 20 74 61 62 6c 65 50 74 72 2d 3e 6e 75 6d 42 75 tablePtr->numBu
6fe0: 63 6b 65 74 73 20 2a 3d 20 34 3b 0a 20 20 20 20 ckets *= 4;.
6ff0: 69 66 20 28 74 79 70 65 50 74 72 2d 3e 66 6c 61 if (typePtr->fla
7000: 67 73 20 26 20 54 43 4c 5f 48 41 53 48 5f 4b 45 gs & TCL_HASH_KE
7010: 59 5f 53 59 53 54 45 4d 5f 48 41 53 48 29 20 7b Y_SYSTEM_HASH) {
7020: 0a 09 74 61 62 6c 65 50 74 72 2d 3e 62 75 63 6b ..tablePtr->buck
7030: 65 74 73 20 3d 20 28 54 63 6c 5f 48 61 73 68 45 ets = (Tcl_HashE
7040: 6e 74 72 79 20 2a 2a 29 20 54 63 6c 70 53 79 73 ntry **) TclpSys
7050: 41 6c 6c 6f 63 28 28 75 6e 73 69 67 6e 65 64 29 Alloc((unsigned)
7060: 0a 09 09 28 74 61 62 6c 65 50 74 72 2d 3e 6e 75 ...(tablePtr->nu
7070: 6d 42 75 63 6b 65 74 73 20 2a 20 73 69 7a 65 6f mBuckets * sizeo
7080: 66 28 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 20 f(Tcl_HashEntry
7090: 2a 29 29 2c 20 30 29 3b 0a 20 20 20 20 7d 20 65 *)), 0);. } e
70a0: 6c 73 65 20 7b 0a 09 74 61 62 6c 65 50 74 72 2d lse {..tablePtr-
70b0: 3e 62 75 63 6b 65 74 73 20 3d 0a 09 09 63 6b 61 >buckets =...cka
70c0: 6c 6c 6f 63 28 74 61 62 6c 65 50 74 72 2d 3e 6e lloc(tablePtr->n
70d0: 75 6d 42 75 63 6b 65 74 73 20 2a 20 73 69 7a 65 umBuckets * size
70e0: 6f 66 28 54 63 6c 5f 48 61 73 68 45 6e 74 72 79 of(Tcl_HashEntry
70f0: 20 2a 29 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 *));. }.
7100: 66 6f 72 20 28 63 6f 75 6e 74 20 3d 20 74 61 62 for (count = tab
7110: 6c 65 50 74 72 2d 3e 6e 75 6d 42 75 63 6b 65 74 lePtr->numBucket
7120: 73 2c 20 6e 65 77 43 68 61 69 6e 50 74 72 20 3d s, newChainPtr =
7130: 20 74 61 62 6c 65 50 74 72 2d 3e 62 75 63 6b 65 tablePtr->bucke
7140: 74 73 3b 0a 09 20 20 20 20 63 6f 75 6e 74 20 3e ts;.. count >
7150: 20 30 3b 20 63 6f 75 6e 74 2d 2d 2c 20 6e 65 77 0; count--, new
7160: 43 68 61 69 6e 50 74 72 2b 2b 29 20 7b 0a 09 2a ChainPtr++) {..*
7170: 6e 65 77 43 68 61 69 6e 50 74 72 20 3d 20 4e 55 newChainPtr = NU
7180: 4c 4c 3b 0a 20 20 20 20 7d 0a 20 20 20 20 74 61 LL;. }. ta
7190: 62 6c 65 50 74 72 2d 3e 72 65 62 75 69 6c 64 53 blePtr->rebuildS
71a0: 69 7a 65 20 2a 3d 20 34 3b 0a 20 20 20 20 74 61 ize *= 4;. ta
71b0: 62 6c 65 50 74 72 2d 3e 64 6f 77 6e 53 68 69 66 blePtr->downShif
71c0: 74 20 2d 3d 20 32 3b 0a 20 20 20 20 74 61 62 6c t -= 2;. tabl
71d0: 65 50 74 72 2d 3e 6d 61 73 6b 20 3d 20 28 74 61 ePtr->mask = (ta
71e0: 62 6c 65 50 74 72 2d 3e 6d 61 73 6b 20 3c 3c 20 blePtr->mask <<
71f0: 32 29 20 2b 20 33 3b 0a 0a 20 20 20 20 2f 2a 0a 2) + 3;.. /*.
7200: 20 20 20 20 20 2a 20 52 65 68 61 73 68 20 61 6c * Rehash al
7210: 6c 20 6f 66 20 74 68 65 20 65 78 69 73 74 69 6e l of the existin
7220: 67 20 65 6e 74 72 69 65 73 20 69 6e 74 6f 20 74 g entries into t
7230: 68 65 20 6e 65 77 20 62 75 63 6b 65 74 20 61 72 he new bucket ar
7240: 72 61 79 2e 0a 20 20 20 20 20 2a 2f 0a 0a 20 20 ray.. */..
7250: 20 20 66 6f 72 20 28 6f 6c 64 43 68 61 69 6e 50 for (oldChainP
7260: 74 72 20 3d 20 6f 6c 64 42 75 63 6b 65 74 73 3b tr = oldBuckets;
7270: 20 6f 6c 64 53 69 7a 65 20 3e 20 30 3b 20 6f 6c oldSize > 0; ol
7280: 64 53 69 7a 65 2d 2d 2c 20 6f 6c 64 43 68 61 69 dSize--, oldChai
7290: 6e 50 74 72 2b 2b 29 20 7b 0a 09 66 6f 72 20 28 nPtr++) {..for (
72a0: 68 50 74 72 20 3d 20 2a 6f 6c 64 43 68 61 69 6e hPtr = *oldChain
72b0: 50 74 72 3b 20 68 50 74 72 20 21 3d 20 4e 55 4c Ptr; hPtr != NUL
72c0: 4c 3b 20 68 50 74 72 20 3d 20 2a 6f 6c 64 43 68 L; hPtr = *oldCh
72d0: 61 69 6e 50 74 72 29 20 7b 0a 09 20 20 20 20 2a ainPtr) {.. *
72e0: 6f 6c 64 43 68 61 69 6e 50 74 72 20 3d 20 68 50 oldChainPtr = hP
72f0: 74 72 2d 3e 6e 65 78 74 50 74 72 3b 0a 23 69 66 tr->nextPtr;.#if
7300: 20 54 43 4c 5f 48 41 53 48 5f 4b 45 59 5f 53 54 TCL_HASH_KEY_ST
7310: 4f 52 45 5f 48 41 53 48 0a 09 20 20 20 20 69 66 ORE_HASH.. if
7320: 20 28 74 79 70 65 50 74 72 2d 3e 68 61 73 68 4b (typePtr->hashK
7330: 65 79 50 72 6f 63 20 3d 3d 20 4e 55 4c 4c 0a 09 eyProc == NULL..
7340: 09 20 20 20 20 7c 7c 20 74 79 70 65 50 74 72 2d . || typePtr-
7350: 3e 66 6c 61 67 73 20 26 20 54 43 4c 5f 48 41 53 >flags & TCL_HAS
7360: 48 5f 4b 45 59 5f 52 41 4e 44 4f 4d 49 5a 45 5f H_KEY_RANDOMIZE_
7370: 48 41 53 48 29 20 7b 0a 09 09 69 6e 64 65 78 20 HASH) {...index
7380: 3d 20 52 41 4e 44 4f 4d 5f 49 4e 44 45 58 28 74 = RANDOM_INDEX(t
7390: 61 62 6c 65 50 74 72 2c 20 50 54 52 32 49 4e 54 ablePtr, PTR2INT
73a0: 28 68 50 74 72 2d 3e 68 61 73 68 29 29 3b 0a 09 (hPtr->hash));..
73b0: 20 20 20 20 7d 20 65 6c 73 65 20 7b 0a 09 09 69 } else {...i
73c0: 6e 64 65 78 20 3d 20 50 54 52 32 55 49 4e 54 28 ndex = PTR2UINT(
73d0: 68 50 74 72 2d 3e 68 61 73 68 29 20 26 20 74 61 hPtr->hash) & ta
73e0: 62 6c 65 50 74 72 2d 3e 6d 61 73 6b 3b 0a 09 20 blePtr->mask;..
73f0: 20 20 20 7d 0a 09 20 20 20 20 68 50 74 72 2d 3e }.. hPtr->
7400: 6e 65 78 74 50 74 72 20 3d 20 74 61 62 6c 65 50 nextPtr = tableP
7410: 74 72 2d 3e 62 75 63 6b 65 74 73 5b 69 6e 64 65 tr->buckets[inde
7420: 78 5d 3b 0a 09 20 20 20 20 74 61 62 6c 65 50 74 x];.. tablePt
7430: 72 2d 3e 62 75 63 6b 65 74 73 5b 69 6e 64 65 78 r->buckets[index
7440: 5d 20 3d 20 68 50 74 72 3b 0a 23 65 6c 73 65 0a ] = hPtr;.#else.
7450: 09 20 20 20 20 76 6f 69 64 20 2a 6b 65 79 20 3d . void *key =
7460: 20 54 63 6c 5f 47 65 74 48 61 73 68 4b 65 79 28 Tcl_GetHashKey(
7470: 74 61 62 6c 65 50 74 72 2c 20 68 50 74 72 29 3b tablePtr, hPtr);
7480: 0a 0a 09 20 20 20 20 69 66 20 28 74 79 70 65 50 ... if (typeP
7490: 74 72 2d 3e 68 61 73 68 4b 65 79 50 72 6f 63 29 tr->hashKeyProc)
74a0: 20 7b 0a 09 09 75 6e 73 69 67 6e 65 64 20 69 6e {...unsigned in
74b0: 74 20 68 61 73 68 3b 0a 0a 09 09 68 61 73 68 20 t hash;....hash
74c0: 3d 20 74 79 70 65 50 74 72 2d 3e 68 61 73 68 4b = typePtr->hashK
74d0: 65 79 50 72 6f 63 28 74 61 62 6c 65 50 74 72 2c eyProc(tablePtr,
74e0: 20 6b 65 79 29 3b 0a 09 09 69 66 20 28 74 79 70 key);...if (typ
74f0: 65 50 74 72 2d 3e 66 6c 61 67 73 20 26 20 54 43 ePtr->flags & TC
7500: 4c 5f 48 41 53 48 5f 4b 45 59 5f 52 41 4e 44 4f L_HASH_KEY_RANDO
7510: 4d 49 5a 45 5f 48 41 53 48 29 20 7b 0a 09 09 20 MIZE_HASH) {...
7520: 20 20 20 69 6e 64 65 78 20 3d 20 52 41 4e 44 4f index = RANDO
7530: 4d 5f 49 4e 44 45 58 28 74 61 62 6c 65 50 74 72 M_INDEX(tablePtr
7540: 2c 20 68 61 73 68 29 3b 0a 09 09 7d 20 65 6c 73 , hash);...} els
7550: 65 20 7b 0a 09 09 20 20 20 20 69 6e 64 65 78 20 e {... index
7560: 3d 20 68 61 73 68 20 26 20 74 61 62 6c 65 50 74 = hash & tablePt
7570: 72 2d 3e 6d 61 73 6b 3b 0a 09 09 7d 0a 09 20 20 r->mask;...}..
7580: 20 20 7d 20 65 6c 73 65 20 7b 0a 09 09 69 6e 64 } else {...ind
7590: 65 78 20 3d 20 52 41 4e 44 4f 4d 5f 49 4e 44 45 ex = RANDOM_INDE
75a0: 58 28 74 61 62 6c 65 50 74 72 2c 20 6b 65 79 29 X(tablePtr, key)
75b0: 3b 0a 09 20 20 20 20 7d 0a 0a 09 20 20 20 20 68 ;.. }... h
75c0: 50 74 72 2d 3e 62 75 63 6b 65 74 50 74 72 20 3d Ptr->bucketPtr =
75d0: 20 26 74 61 62 6c 65 50 74 72 2d 3e 62 75 63 6b &tablePtr->buck
75e0: 65 74 73 5b 69 6e 64 65 78 5d 3b 0a 09 20 20 20 ets[index];..
75f0: 20 68 50 74 72 2d 3e 6e 65 78 74 50 74 72 20 3d hPtr->nextPtr =
7600: 20 2a 68 50 74 72 2d 3e 62 75 63 6b 65 74 50 74 *hPtr->bucketPt
7610: 72 3b 0a 09 20 20 20 20 2a 68 50 74 72 2d 3e 62 r;.. *hPtr->b
7620: 75 63 6b 65 74 50 74 72 20 3d 20 68 50 74 72 3b ucketPtr = hPtr;
7630: 0a 23 65 6e 64 69 66 0a 09 7d 0a 20 20 20 20 7d .#endif..}. }
7640: 0a 0a 20 20 20 20 2f 2a 0a 20 20 20 20 20 2a 20 .. /*. *
7650: 46 72 65 65 20 75 70 20 74 68 65 20 6f 6c 64 20 Free up the old
7660: 62 75 63 6b 65 74 20 61 72 72 61 79 2c 20 69 66 bucket array, if
7670: 20 69 74 20 77 61 73 20 64 79 6e 61 6d 69 63 61 it was dynamica
7680: 6c 6c 79 20 61 6c 6c 6f 63 61 74 65 64 2e 0a 20 lly allocated..
7690: 20 20 20 20 2a 2f 0a 0a 20 20 20 20 69 66 20 28 */.. if (
76a0: 6f 6c 64 42 75 63 6b 65 74 73 20 21 3d 20 74 61 oldBuckets != ta
76b0: 62 6c 65 50 74 72 2d 3e 73 74 61 74 69 63 42 75 blePtr->staticBu
76c0: 63 6b 65 74 73 29 20 7b 0a 09 69 66 20 28 74 79 ckets) {..if (ty
76d0: 70 65 50 74 72 2d 3e 66 6c 61 67 73 20 26 20 54 pePtr->flags & T
76e0: 43 4c 5f 48 41 53 48 5f 4b 45 59 5f 53 59 53 54 CL_HASH_KEY_SYST
76f0: 45 4d 5f 48 41 53 48 29 20 7b 0a 09 20 20 20 20 EM_HASH) {..
7700: 54 63 6c 70 53 79 73 46 72 65 65 28 28 63 68 61 TclpSysFree((cha
7710: 72 20 2a 29 20 6f 6c 64 42 75 63 6b 65 74 73 29 r *) oldBuckets)
7720: 3b 0a 09 7d 20 65 6c 73 65 20 7b 0a 09 20 20 20 ;..} else {..
7730: 20 63 6b 66 72 65 65 28 6f 6c 64 42 75 63 6b 65 ckfree(oldBucke
7740: 74 73 29 3b 0a 09 7d 0a 20 20 20 20 7d 0a 7d 0a ts);..}. }.}.
7750: 0c 0a 2f 2a 0a 20 2a 20 4c 6f 63 61 6c 20 56 61 ../*. * Local Va
7760: 72 69 61 62 6c 65 73 3a 0a 20 2a 20 6d 6f 64 65 riables:. * mode
7770: 3a 20 63 0a 20 2a 20 63 2d 62 61 73 69 63 2d 6f : c. * c-basic-o
7780: 66 66 73 65 74 3a 20 34 0a 20 2a 20 66 69 6c 6c ffset: 4. * fill
7790: 2d 63 6f 6c 75 6d 6e 3a 20 37 38 0a 20 2a 20 45 -column: 78. * E
77a0: 6e 64 3a 0a 20 2a 2f 0a nd:. */.
