0000: 2f 2a 0a 2a 2a 20 32 30 30 31 20 53 65 70 74 65 /*.** 2001 Septe
0010: 6d 62 65 72 20 32 32 0a 2a 2a 0a 2a 2a 20 54 68 mber 22.**.** Th
0020: 65 20 61 75 74 68 6f 72 20 64 69 73 63 6c 61 69 e author disclai
0030: 6d 73 20 63 6f 70 79 72 69 67 68 74 20 74 6f 20 ms copyright to
0040: 74 68 69 73 20 73 6f 75 72 63 65 20 63 6f 64 65 this source code
0050: 2e 20 20 49 6e 20 70 6c 61 63 65 20 6f 66 0a 2a . In place of.*
0060: 2a 20 61 20 6c 65 67 61 6c 20 6e 6f 74 69 63 65 * a legal notice
0070: 2c 20 68 65 72 65 20 69 73 20 61 20 62 6c 65 73 , here is a bles
0080: 73 69 6e 67 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 4d sing:.**.** M
0090: 61 79 20 79 6f 75 20 64 6f 20 67 6f 6f 64 20 61 ay you do good a
00a0: 6e 64 20 6e 6f 74 20 65 76 69 6c 2e 0a 2a 2a 20 nd not evil..**
00b0: 20 20 20 4d 61 79 20 79 6f 75 20 66 69 6e 64 20 May you find
00c0: 66 6f 72 67 69 76 65 6e 65 73 73 20 66 6f 72 20 forgiveness for
00d0: 79 6f 75 72 73 65 6c 66 20 61 6e 64 20 66 6f 72 yourself and for
00e0: 67 69 76 65 20 6f 74 68 65 72 73 2e 0a 2a 2a 20 give others..**
00f0: 20 20 20 4d 61 79 20 79 6f 75 20 73 68 61 72 65 May you share
0100: 20 66 72 65 65 6c 79 2c 20 6e 65 76 65 72 20 74 freely, never t
0110: 61 6b 69 6e 67 20 6d 6f 72 65 20 74 68 61 6e 20 aking more than
0120: 79 6f 75 20 67 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a you give..**.***
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0170: 2a 2a 2a 2a 2a 2a 0a 2a 2a 20 54 68 69 73 20 69 ******.** This i
0180: 73 20 74 68 65 20 69 6d 70 6c 65 6d 65 6e 74 61 s the implementa
0190: 74 69 6f 6e 20 6f 66 20 67 65 6e 65 72 69 63 20 tion of generic
01a0: 68 61 73 68 2d 74 61 62 6c 65 73 0a 2a 2a 20 75 hash-tables.** u
01b0: 73 65 64 20 69 6e 20 53 51 4c 69 74 65 2e 0a 2a sed in SQLite..*
01c0: 2a 0a 2a 2a 20 24 49 64 3a 20 68 61 73 68 2e 63 *.** $Id: hash.c
01d0: 2c 76 20 31 2e 32 30 20 32 30 30 37 2f 30 38 2f ,v 1.20 2007/08/
01e0: 31 36 20 30 34 3a 33 30 3a 34 30 20 64 72 68 20 16 04:30:40 drh
01f0: 45 78 70 20 24 0a 2a 2f 0a 23 69 6e 63 6c 75 64 Exp $.*/.#includ
0200: 65 20 22 73 71 6c 69 74 65 49 6e 74 2e 68 22 0a e "sqliteInt.h".
0210: 23 69 6e 63 6c 75 64 65 20 3c 61 73 73 65 72 74 #include <assert
0220: 2e 68 3e 0a 0a 2f 2a 20 54 75 72 6e 20 62 75 6c .h>../* Turn bul
0230: 6b 20 6d 65 6d 6f 72 79 20 69 6e 74 6f 20 61 20 k memory into a
0240: 68 61 73 68 20 74 61 62 6c 65 20 6f 62 6a 65 63 hash table objec
0250: 74 20 62 79 20 69 6e 69 74 69 61 6c 69 7a 69 6e t by initializin
0260: 67 20 74 68 65 0a 2a 2a 20 66 69 65 6c 64 73 20 g the.** fields
0270: 6f 66 20 74 68 65 20 48 61 73 68 20 73 74 72 75 of the Hash stru
0280: 63 74 75 72 65 2e 0a 2a 2a 0a 2a 2a 20 22 70 4e cture..**.** "pN
0290: 65 77 22 20 69 73 20 61 20 70 6f 69 6e 74 65 72 ew" is a pointer
02a0: 20 74 6f 20 74 68 65 20 68 61 73 68 20 74 61 62 to the hash tab
02b0: 6c 65 20 74 68 61 74 20 69 73 20 74 6f 20 62 65 le that is to be
02c0: 20 69 6e 69 74 69 61 6c 69 7a 65 64 2e 0a 2a 2a initialized..**
02d0: 20 6b 65 79 43 6c 61 73 73 20 69 73 20 6f 6e 65 keyClass is one
02e0: 20 6f 66 20 74 68 65 20 63 6f 6e 73 74 61 6e 74 of the constant
02f0: 73 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 49 4e s SQLITE_HASH_IN
0300: 54 2c 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 50 T, SQLITE_HASH_P
0310: 4f 49 4e 54 45 52 2c 0a 2a 2a 20 53 51 4c 49 54 OINTER,.** SQLIT
0320: 45 5f 48 41 53 48 5f 42 49 4e 41 52 59 2c 20 6f E_HASH_BINARY, o
0330: 72 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 r SQLITE_HASH_ST
0340: 52 49 4e 47 2e 20 20 54 68 65 20 76 61 6c 75 65 RING. The value
0350: 20 6f 66 20 6b 65 79 43 6c 61 73 73 20 0a 2a 2a of keyClass .**
0360: 20 64 65 74 65 72 6d 69 6e 65 73 20 77 68 61 74 determines what
0370: 20 6b 69 6e 64 20 6f 66 20 6b 65 79 20 74 68 65 kind of key the
0380: 20 68 61 73 68 20 74 61 62 6c 65 20 77 69 6c 6c hash table will
0390: 20 75 73 65 2e 20 20 22 63 6f 70 79 4b 65 79 22 use. "copyKey"
03a0: 20 69 73 0a 2a 2a 20 74 72 75 65 20 69 66 20 74 is.** true if t
03b0: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 73 68 he hash table sh
03c0: 6f 75 6c 64 20 6d 61 6b 65 20 69 74 73 20 6f 77 ould make its ow
03d0: 6e 20 70 72 69 76 61 74 65 20 63 6f 70 79 20 6f n private copy o
03e0: 66 20 6b 65 79 73 20 61 6e 64 0a 2a 2a 20 66 61 f keys and.** fa
03f0: 6c 73 65 20 69 66 20 69 74 20 73 68 6f 75 6c 64 lse if it should
0400: 20 6a 75 73 74 20 75 73 65 20 74 68 65 20 73 75 just use the su
0410: 70 70 6c 69 65 64 20 70 6f 69 6e 74 65 72 2e 20 pplied pointer.
0420: 20 43 6f 70 79 4b 65 79 20 6f 6e 6c 79 20 6d 61 CopyKey only ma
0430: 6b 65 73 0a 2a 2a 20 73 65 6e 73 65 20 66 6f 72 kes.** sense for
0440: 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 SQLITE_HASH_STR
0450: 49 4e 47 20 61 6e 64 20 53 51 4c 49 54 45 5f 48 ING and SQLITE_H
0460: 41 53 48 5f 42 49 4e 41 52 59 20 61 6e 64 20 69 ASH_BINARY and i
0470: 73 20 69 67 6e 6f 72 65 64 0a 2a 2a 20 66 6f 72 s ignored.** for
0480: 20 6f 74 68 65 72 20 6b 65 79 20 63 6c 61 73 73 other key class
0490: 65 73 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 es..*/.void sqli
04a0: 74 65 33 48 61 73 68 49 6e 69 74 28 48 61 73 68 te3HashInit(Hash
04b0: 20 2a 70 4e 65 77 2c 20 69 6e 74 20 6b 65 79 43 *pNew, int keyC
04c0: 6c 61 73 73 2c 20 69 6e 74 20 63 6f 70 79 4b 65 lass, int copyKe
04d0: 79 29 7b 0a 20 20 61 73 73 65 72 74 28 20 70 4e y){. assert( pN
04e0: 65 77 21 3d 30 20 29 3b 0a 20 20 61 73 73 65 72 ew!=0 );. asser
04f0: 74 28 20 6b 65 79 43 6c 61 73 73 3e 3d 53 51 4c t( keyClass>=SQL
0500: 49 54 45 5f 48 41 53 48 5f 53 54 52 49 4e 47 20 ITE_HASH_STRING
0510: 26 26 20 6b 65 79 43 6c 61 73 73 3c 3d 53 51 4c && keyClass<=SQL
0520: 49 54 45 5f 48 41 53 48 5f 42 49 4e 41 52 59 20 ITE_HASH_BINARY
0530: 29 3b 0a 20 20 70 4e 65 77 2d 3e 6b 65 79 43 6c );. pNew->keyCl
0540: 61 73 73 20 3d 20 6b 65 79 43 6c 61 73 73 3b 0a ass = keyClass;.
0550: 23 69 66 20 30 0a 20 20 69 66 28 20 6b 65 79 43 #if 0. if( keyC
0560: 6c 61 73 73 3d 3d 53 51 4c 49 54 45 5f 48 41 53 lass==SQLITE_HAS
0570: 48 5f 50 4f 49 4e 54 45 52 20 7c 7c 20 6b 65 79 H_POINTER || key
0580: 43 6c 61 73 73 3d 3d 53 51 4c 49 54 45 5f 48 41 Class==SQLITE_HA
0590: 53 48 5f 49 4e 54 20 29 20 63 6f 70 79 4b 65 79 SH_INT ) copyKey
05a0: 20 3d 20 30 3b 0a 23 65 6e 64 69 66 0a 20 20 70 = 0;.#endif. p
05b0: 4e 65 77 2d 3e 63 6f 70 79 4b 65 79 20 3d 20 63 New->copyKey = c
05c0: 6f 70 79 4b 65 79 3b 0a 20 20 70 4e 65 77 2d 3e opyKey;. pNew->
05d0: 66 69 72 73 74 20 3d 20 30 3b 0a 20 20 70 4e 65 first = 0;. pNe
05e0: 77 2d 3e 63 6f 75 6e 74 20 3d 20 30 3b 0a 20 20 w->count = 0;.
05f0: 70 4e 65 77 2d 3e 68 74 73 69 7a 65 20 3d 20 30 pNew->htsize = 0
0600: 3b 0a 20 20 70 4e 65 77 2d 3e 68 74 20 3d 20 30 ;. pNew->ht = 0
0610: 3b 0a 7d 0a 0a 2f 2a 20 52 65 6d 6f 76 65 20 61 ;.}../* Remove a
0620: 6c 6c 20 65 6e 74 72 69 65 73 20 66 72 6f 6d 20 ll entries from
0630: 61 20 68 61 73 68 20 74 61 62 6c 65 2e 20 20 52 a hash table. R
0640: 65 63 6c 61 69 6d 20 61 6c 6c 20 6d 65 6d 6f 72 eclaim all memor
0650: 79 2e 0a 2a 2a 20 43 61 6c 6c 20 74 68 69 73 20 y..** Call this
0660: 72 6f 75 74 69 6e 65 20 74 6f 20 64 65 6c 65 74 routine to delet
0670: 65 20 61 20 68 61 73 68 20 74 61 62 6c 65 20 6f e a hash table o
0680: 72 20 74 6f 20 72 65 73 65 74 20 61 20 68 61 73 r to reset a has
0690: 68 20 74 61 62 6c 65 0a 2a 2a 20 74 6f 20 74 68 h table.** to th
06a0: 65 20 65 6d 70 74 79 20 73 74 61 74 65 2e 0a 2a e empty state..*
06b0: 2f 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 48 61 /.void sqlite3Ha
06c0: 73 68 43 6c 65 61 72 28 48 61 73 68 20 2a 70 48 shClear(Hash *pH
06d0: 29 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 ){. HashElem *e
06e0: 6c 65 6d 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 lem; /*
06f0: 46 6f 72 20 6c 6f 6f 70 69 6e 67 20 6f 76 65 72 For looping over
0700: 20 61 6c 6c 20 65 6c 65 6d 65 6e 74 73 20 6f 66 all elements of
0710: 20 74 68 65 20 74 61 62 6c 65 20 2a 2f 0a 0a 20 the table */..
0720: 20 61 73 73 65 72 74 28 20 70 48 21 3d 30 20 29 assert( pH!=0 )
0730: 3b 0a 20 20 65 6c 65 6d 20 3d 20 70 48 2d 3e 66 ;. elem = pH->f
0740: 69 72 73 74 3b 0a 20 20 70 48 2d 3e 66 69 72 73 irst;. pH->firs
0750: 74 20 3d 20 30 3b 0a 20 20 69 66 28 20 70 48 2d t = 0;. if( pH-
0760: 3e 68 74 20 29 20 73 71 6c 69 74 65 33 5f 66 72 >ht ) sqlite3_fr
0770: 65 65 28 70 48 2d 3e 68 74 29 3b 0a 20 20 70 48 ee(pH->ht);. pH
0780: 2d 3e 68 74 20 3d 20 30 3b 0a 20 20 70 48 2d 3e ->ht = 0;. pH->
0790: 68 74 73 69 7a 65 20 3d 20 30 3b 0a 20 20 77 68 htsize = 0;. wh
07a0: 69 6c 65 28 20 65 6c 65 6d 20 29 7b 0a 20 20 20 ile( elem ){.
07b0: 20 48 61 73 68 45 6c 65 6d 20 2a 6e 65 78 74 5f HashElem *next_
07c0: 65 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 elem = elem->nex
07d0: 74 3b 0a 20 20 20 20 69 66 28 20 70 48 2d 3e 63 t;. if( pH->c
07e0: 6f 70 79 4b 65 79 20 26 26 20 65 6c 65 6d 2d 3e opyKey && elem->
07f0: 70 4b 65 79 20 29 7b 0a 20 20 20 20 20 20 73 71 pKey ){. sq
0800: 6c 69 74 65 33 5f 66 72 65 65 28 65 6c 65 6d 2d lite3_free(elem-
0810: 3e 70 4b 65 79 29 3b 0a 20 20 20 20 7d 0a 20 20 >pKey);. }.
0820: 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 65 sqlite3_free(e
0830: 6c 65 6d 29 3b 0a 20 20 20 20 65 6c 65 6d 20 3d lem);. elem =
0840: 20 6e 65 78 74 5f 65 6c 65 6d 3b 0a 20 20 7d 0a next_elem;. }.
0850: 20 20 70 48 2d 3e 63 6f 75 6e 74 20 3d 20 30 3b pH->count = 0;
0860: 0a 7d 0a 0a 23 69 66 20 30 20 2f 2a 20 4e 4f 54 .}..#if 0 /* NOT
0870: 20 55 53 45 44 20 2a 2f 0a 2f 2a 0a 2a 2a 20 48 USED */./*.** H
0880: 61 73 68 20 61 6e 64 20 63 6f 6d 70 61 72 69 73 ash and comparis
0890: 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 20 77 68 65 on functions whe
08a0: 6e 20 74 68 65 20 6d 6f 64 65 20 69 73 20 53 51 n the mode is SQ
08b0: 4c 49 54 45 5f 48 41 53 48 5f 49 4e 54 0a 2a 2f LITE_HASH_INT.*/
08c0: 0a 73 74 61 74 69 63 20 69 6e 74 20 69 6e 74 48 .static int intH
08d0: 61 73 68 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a ash(const void *
08e0: 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b pKey, int nKey){
08f0: 0a 20 20 72 65 74 75 72 6e 20 6e 4b 65 79 20 5e . return nKey ^
0900: 20 28 6e 4b 65 79 3c 3c 38 29 20 5e 20 28 6e 4b (nKey<<8) ^ (nK
0910: 65 79 3e 3e 38 29 3b 0a 7d 0a 73 74 61 74 69 63 ey>>8);.}.static
0920: 20 69 6e 74 20 69 6e 74 43 6f 6d 70 61 72 65 28 int intCompare(
0930: 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 const void *pKey
0940: 31 2c 20 69 6e 74 20 6e 31 2c 20 63 6f 6e 73 74 1, int n1, const
0950: 20 76 6f 69 64 20 2a 70 4b 65 79 32 2c 20 69 6e void *pKey2, in
0960: 74 20 6e 32 29 7b 0a 20 20 72 65 74 75 72 6e 20 t n2){. return
0970: 6e 32 20 2d 20 6e 31 3b 0a 7d 0a 23 65 6e 64 69 n2 - n1;.}.#endi
0980: 66 0a 0a 23 69 66 20 30 20 2f 2a 20 4e 4f 54 20 f..#if 0 /* NOT
0990: 55 53 45 44 20 2a 2f 0a 2f 2a 0a 2a 2a 20 48 61 USED */./*.** Ha
09a0: 73 68 20 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f sh and compariso
09b0: 6e 20 66 75 6e 63 74 69 6f 6e 73 20 77 68 65 6e n functions when
09c0: 20 74 68 65 20 6d 6f 64 65 20 69 73 20 53 51 4c the mode is SQL
09d0: 49 54 45 5f 48 41 53 48 5f 50 4f 49 4e 54 45 52 ITE_HASH_POINTER
09e0: 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 70 .*/.static int p
09f0: 74 72 48 61 73 68 28 63 6f 6e 73 74 20 76 6f 69 trHash(const voi
0a00: 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 d *pKey, int nKe
0a10: 79 29 7b 0a 20 20 75 70 74 72 20 78 20 3d 20 41 y){. uptr x = A
0a20: 64 64 72 28 70 4b 65 79 29 3b 0a 20 20 72 65 74 ddr(pKey);. ret
0a30: 75 72 6e 20 78 20 5e 20 28 78 3c 3c 38 29 20 5e urn x ^ (x<<8) ^
0a40: 20 28 78 3e 3e 38 29 3b 0a 7d 0a 73 74 61 74 69 (x>>8);.}.stati
0a50: 63 20 69 6e 74 20 70 74 72 43 6f 6d 70 61 72 65 c int ptrCompare
0a60: 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 (const void *pKe
0a70: 79 31 2c 20 69 6e 74 20 6e 31 2c 20 63 6f 6e 73 y1, int n1, cons
0a80: 74 20 76 6f 69 64 20 2a 70 4b 65 79 32 2c 20 69 t void *pKey2, i
0a90: 6e 74 20 6e 32 29 7b 0a 20 20 69 66 28 20 70 4b nt n2){. if( pK
0aa0: 65 79 31 3d 3d 70 4b 65 79 32 20 29 20 72 65 74 ey1==pKey2 ) ret
0ab0: 75 72 6e 20 30 3b 0a 20 20 69 66 28 20 70 4b 65 urn 0;. if( pKe
0ac0: 79 31 3c 70 4b 65 79 32 20 29 20 72 65 74 75 72 y1<pKey2 ) retur
0ad0: 6e 20 2d 31 3b 0a 20 20 72 65 74 75 72 6e 20 31 n -1;. return 1
0ae0: 3b 0a 7d 0a 23 65 6e 64 69 66 0a 0a 2f 2a 0a 2a ;.}.#endif../*.*
0af0: 2a 20 48 61 73 68 20 61 6e 64 20 63 6f 6d 70 61 * Hash and compa
0b00: 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 20 rison functions
0b10: 77 68 65 6e 20 74 68 65 20 6d 6f 64 65 20 69 73 when the mode is
0b20: 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 SQLITE_HASH_STR
0b30: 49 4e 47 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e ING.*/.static in
0b40: 74 20 73 74 72 48 61 73 68 28 63 6f 6e 73 74 20 t strHash(const
0b50: 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 void *pKey, int
0b60: 6e 4b 65 79 29 7b 0a 20 20 63 6f 6e 73 74 20 63 nKey){. const c
0b70: 68 61 72 20 2a 7a 20 3d 20 28 63 6f 6e 73 74 20 har *z = (const
0b80: 63 68 61 72 20 2a 29 70 4b 65 79 3b 0a 20 20 69 char *)pKey;. i
0b90: 6e 74 20 68 20 3d 20 30 3b 0a 20 20 69 66 28 20 nt h = 0;. if(
0ba0: 6e 4b 65 79 3c 3d 30 20 29 20 6e 4b 65 79 20 3d nKey<=0 ) nKey =
0bb0: 20 73 74 72 6c 65 6e 28 7a 29 3b 0a 20 20 77 68 strlen(z);. wh
0bc0: 69 6c 65 28 20 6e 4b 65 79 20 3e 20 30 20 20 29 ile( nKey > 0 )
0bd0: 7b 0a 20 20 20 20 68 20 3d 20 28 68 3c 3c 33 29 {. h = (h<<3)
0be0: 20 5e 20 68 20 5e 20 73 71 6c 69 74 65 33 55 70 ^ h ^ sqlite3Up
0bf0: 70 65 72 54 6f 4c 6f 77 65 72 5b 28 75 6e 73 69 perToLower[(unsi
0c00: 67 6e 65 64 20 63 68 61 72 29 2a 7a 2b 2b 5d 3b gned char)*z++];
0c10: 0a 20 20 20 20 6e 4b 65 79 2d 2d 3b 0a 20 20 7d . nKey--;. }
0c20: 0a 20 20 72 65 74 75 72 6e 20 68 20 26 20 30 78 . return h & 0x
0c30: 37 66 66 66 66 66 66 66 3b 0a 7d 0a 73 74 61 74 7fffffff;.}.stat
0c40: 69 63 20 69 6e 74 20 73 74 72 43 6f 6d 70 61 72 ic int strCompar
0c50: 65 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b e(const void *pK
0c60: 65 79 31 2c 20 69 6e 74 20 6e 31 2c 20 63 6f 6e ey1, int n1, con
0c70: 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 32 2c 20 st void *pKey2,
0c80: 69 6e 74 20 6e 32 29 7b 0a 20 20 69 66 28 20 6e int n2){. if( n
0c90: 31 21 3d 6e 32 20 29 20 72 65 74 75 72 6e 20 31 1!=n2 ) return 1
0ca0: 3b 0a 20 20 72 65 74 75 72 6e 20 73 71 6c 69 74 ;. return sqlit
0cb0: 65 33 53 74 72 4e 49 43 6d 70 28 28 63 6f 6e 73 e3StrNICmp((cons
0cc0: 74 20 63 68 61 72 2a 29 70 4b 65 79 31 2c 28 63 t char*)pKey1,(c
0cd0: 6f 6e 73 74 20 63 68 61 72 2a 29 70 4b 65 79 32 onst char*)pKey2
0ce0: 2c 6e 31 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 48 ,n1);.}../*.** H
0cf0: 61 73 68 20 61 6e 64 20 63 6f 6d 70 61 72 69 73 ash and comparis
0d00: 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 20 77 68 65 on functions whe
0d10: 6e 20 74 68 65 20 6d 6f 64 65 20 69 73 20 53 51 n the mode is SQ
0d20: 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e 41 52 59 LITE_HASH_BINARY
0d30: 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 62 .*/.static int b
0d40: 69 6e 48 61 73 68 28 63 6f 6e 73 74 20 76 6f 69 inHash(const voi
0d50: 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 d *pKey, int nKe
0d60: 79 29 7b 0a 20 20 69 6e 74 20 68 20 3d 20 30 3b y){. int h = 0;
0d70: 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a . const char *z
0d80: 20 3d 20 28 63 6f 6e 73 74 20 63 68 61 72 20 2a = (const char *
0d90: 29 70 4b 65 79 3b 0a 20 20 77 68 69 6c 65 28 20 )pKey;. while(
0da0: 6e 4b 65 79 2d 2d 20 3e 20 30 20 29 7b 0a 20 20 nKey-- > 0 ){.
0db0: 20 20 68 20 3d 20 28 68 3c 3c 33 29 20 5e 20 68 h = (h<<3) ^ h
0dc0: 20 5e 20 2a 28 7a 2b 2b 29 3b 0a 20 20 7d 0a 20 ^ *(z++);. }.
0dd0: 20 72 65 74 75 72 6e 20 68 20 26 20 30 78 37 66 return h & 0x7f
0de0: 66 66 66 66 66 66 3b 0a 7d 0a 73 74 61 74 69 63 ffffff;.}.static
0df0: 20 69 6e 74 20 62 69 6e 43 6f 6d 70 61 72 65 28 int binCompare(
0e00: 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 const void *pKey
0e10: 31 2c 20 69 6e 74 20 6e 31 2c 20 63 6f 6e 73 74 1, int n1, const
0e20: 20 76 6f 69 64 20 2a 70 4b 65 79 32 2c 20 69 6e void *pKey2, in
0e30: 74 20 6e 32 29 7b 0a 20 20 69 66 28 20 6e 31 21 t n2){. if( n1!
0e40: 3d 6e 32 20 29 20 72 65 74 75 72 6e 20 31 3b 0a =n2 ) return 1;.
0e50: 20 20 72 65 74 75 72 6e 20 6d 65 6d 63 6d 70 28 return memcmp(
0e60: 70 4b 65 79 31 2c 70 4b 65 79 32 2c 6e 31 29 3b pKey1,pKey2,n1);
0e70: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e .}../*.** Return
0e80: 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 a pointer to th
0e90: 65 20 61 70 70 72 6f 70 72 69 61 74 65 20 68 61 e appropriate ha
0ea0: 73 68 20 66 75 6e 63 74 69 6f 6e 20 67 69 76 65 sh function give
0eb0: 6e 20 74 68 65 20 6b 65 79 20 63 6c 61 73 73 2e n the key class.
0ec0: 0a 2a 2a 0a 2a 2a 20 54 68 65 20 43 20 73 79 6e .**.** The C syn
0ed0: 74 61 78 20 69 6e 20 74 68 69 73 20 66 75 6e 63 tax in this func
0ee0: 74 69 6f 6e 20 64 65 66 69 6e 69 74 69 6f 6e 20 tion definition
0ef0: 6d 61 79 20 62 65 20 75 6e 66 61 6d 69 6c 61 72 may be unfamilar
0f00: 20 74 6f 20 73 6f 6d 65 20 0a 2a 2a 20 70 72 6f to some .** pro
0f10: 67 72 61 6d 6d 65 72 73 2c 20 73 6f 20 77 65 20 grammers, so we
0f20: 70 72 6f 76 69 64 65 20 74 68 65 20 66 6f 6c 6c provide the foll
0f30: 6f 77 69 6e 67 20 61 64 64 69 74 69 6f 6e 61 6c owing additional
0f40: 20 65 78 70 6c 61 6e 61 74 69 6f 6e 3a 0a 2a 2a explanation:.**
0f50: 0a 2a 2a 20 54 68 65 20 6e 61 6d 65 20 6f 66 20 .** The name of
0f60: 74 68 65 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 the function is
0f70: 22 68 61 73 68 46 75 6e 63 74 69 6f 6e 22 2e 20 "hashFunction".
0f80: 20 54 68 65 20 66 75 6e 63 74 69 6f 6e 20 74 61 The function ta
0f90: 6b 65 73 20 61 0a 2a 2a 20 73 69 6e 67 6c 65 20 kes a.** single
0fa0: 70 61 72 61 6d 65 74 65 72 20 22 6b 65 79 43 6c parameter "keyCl
0fb0: 61 73 73 22 2e 20 20 54 68 65 20 72 65 74 75 72 ass". The retur
0fc0: 6e 20 76 61 6c 75 65 20 6f 66 20 68 61 73 68 46 n value of hashF
0fd0: 75 6e 63 74 69 6f 6e 28 29 0a 2a 2a 20 69 73 20 unction().** is
0fe0: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 6e 6f a pointer to ano
0ff0: 74 68 65 72 20 66 75 6e 63 74 69 6f 6e 2e 20 20 ther function.
1000: 53 70 65 63 69 66 69 63 61 6c 6c 79 2c 20 74 68 Specifically, th
1010: 65 20 72 65 74 75 72 6e 20 76 61 6c 75 65 0a 2a e return value.*
1020: 2a 20 6f 66 20 68 61 73 68 46 75 6e 63 74 69 6f * of hashFunctio
1030: 6e 28 29 20 69 73 20 61 20 70 6f 69 6e 74 65 72 n() is a pointer
1040: 20 74 6f 20 61 20 66 75 6e 63 74 69 6f 6e 20 74 to a function t
1050: 68 61 74 20 74 61 6b 65 73 20 74 77 6f 20 70 61 hat takes two pa
1060: 72 61 6d 65 74 65 72 73 0a 2a 2a 20 77 69 74 68 rameters.** with
1070: 20 74 79 70 65 73 20 22 63 6f 6e 73 74 20 76 6f types "const vo
1080: 69 64 2a 22 20 61 6e 64 20 22 69 6e 74 22 20 61 id*" and "int" a
1090: 6e 64 20 72 65 74 75 72 6e 73 20 61 6e 20 22 69 nd returns an "i
10a0: 6e 74 22 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 nt"..*/.static i
10b0: 6e 74 20 28 2a 68 61 73 68 46 75 6e 63 74 69 6f nt (*hashFunctio
10c0: 6e 28 69 6e 74 20 6b 65 79 43 6c 61 73 73 29 29 n(int keyClass))
10d0: 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 (const void*,int
10e0: 29 7b 0a 23 69 66 20 30 20 20 2f 2a 20 48 41 53 ){.#if 0 /* HAS
10f0: 48 5f 49 4e 54 20 61 6e 64 20 48 41 53 48 5f 50 H_INT and HASH_P
1100: 4f 49 4e 54 45 52 20 61 72 65 20 6e 65 76 65 72 OINTER are never
1110: 20 75 73 65 64 20 2a 2f 0a 20 20 73 77 69 74 63 used */. switc
1120: 68 28 20 6b 65 79 43 6c 61 73 73 20 29 7b 0a 20 h( keyClass ){.
1130: 20 20 20 63 61 73 65 20 53 51 4c 49 54 45 5f 48 case SQLITE_H
1140: 41 53 48 5f 49 4e 54 3a 20 20 20 20 20 72 65 74 ASH_INT: ret
1150: 75 72 6e 20 26 69 6e 74 48 61 73 68 3b 0a 20 20 urn &intHash;.
1160: 20 20 63 61 73 65 20 53 51 4c 49 54 45 5f 48 41 case SQLITE_HA
1170: 53 48 5f 50 4f 49 4e 54 45 52 3a 20 72 65 74 75 SH_POINTER: retu
1180: 72 6e 20 26 70 74 72 48 61 73 68 3b 0a 20 20 20 rn &ptrHash;.
1190: 20 63 61 73 65 20 53 51 4c 49 54 45 5f 48 41 53 case SQLITE_HAS
11a0: 48 5f 53 54 52 49 4e 47 3a 20 20 72 65 74 75 72 H_STRING: retur
11b0: 6e 20 26 73 74 72 48 61 73 68 3b 0a 20 20 20 20 n &strHash;.
11c0: 63 61 73 65 20 53 51 4c 49 54 45 5f 48 41 53 48 case SQLITE_HASH
11d0: 5f 42 49 4e 41 52 59 3a 20 20 72 65 74 75 72 6e _BINARY: return
11e0: 20 26 62 69 6e 48 61 73 68 3b 3b 0a 20 20 20 20 &binHash;;.
11f0: 64 65 66 61 75 6c 74 3a 20 62 72 65 61 6b 3b 0a default: break;.
1200: 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a }. return 0;.
1210: 23 65 6c 73 65 0a 20 20 69 66 28 20 6b 65 79 43 #else. if( keyC
1220: 6c 61 73 73 3d 3d 53 51 4c 49 54 45 5f 48 41 53 lass==SQLITE_HAS
1230: 48 5f 53 54 52 49 4e 47 20 29 7b 0a 20 20 20 20 H_STRING ){.
1240: 72 65 74 75 72 6e 20 26 73 74 72 48 61 73 68 3b return &strHash;
1250: 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 61 73 . }else{. as
1260: 73 65 72 74 28 20 6b 65 79 43 6c 61 73 73 3d 3d sert( keyClass==
1270: 53 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e 41 SQLITE_HASH_BINA
1280: 52 59 20 29 3b 0a 20 20 20 20 72 65 74 75 72 6e RY );. return
1290: 20 26 62 69 6e 48 61 73 68 3b 0a 20 20 7d 0a 23 &binHash;. }.#
12a0: 65 6e 64 69 66 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 endif.}../*.** R
12b0: 65 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20 eturn a pointer
12c0: 74 6f 20 74 68 65 20 61 70 70 72 6f 70 72 69 61 to the appropria
12d0: 74 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e te hash function
12e0: 20 67 69 76 65 6e 20 74 68 65 20 6b 65 79 20 63 given the key c
12f0: 6c 61 73 73 2e 0a 2a 2a 0a 2a 2a 20 46 6f 72 20 lass..**.** For
1300: 68 65 6c 70 20 69 6e 20 69 6e 74 65 72 70 72 65 help in interpre
1310: 74 65 64 20 74 68 65 20 6f 62 73 63 75 72 65 20 ted the obscure
1320: 43 20 63 6f 64 65 20 69 6e 20 74 68 65 20 66 75 C code in the fu
1330: 6e 63 74 69 6f 6e 20 64 65 66 69 6e 69 74 69 6f nction definitio
1340: 6e 2c 0a 2a 2a 20 73 65 65 20 74 68 65 20 68 65 n,.** see the he
1350: 61 64 65 72 20 63 6f 6d 6d 65 6e 74 20 6f 6e 20 ader comment on
1360: 74 68 65 20 70 72 65 76 69 6f 75 73 20 66 75 6e the previous fun
1370: 63 74 69 6f 6e 2e 0a 2a 2f 0a 73 74 61 74 69 63 ction..*/.static
1380: 20 69 6e 74 20 28 2a 63 6f 6d 70 61 72 65 46 75 int (*compareFu
1390: 6e 63 74 69 6f 6e 28 69 6e 74 20 6b 65 79 43 6c nction(int keyCl
13a0: 61 73 73 29 29 28 63 6f 6e 73 74 20 76 6f 69 64 ass))(const void
13b0: 2a 2c 69 6e 74 2c 63 6f 6e 73 74 20 76 6f 69 64 *,int,const void
13c0: 2a 2c 69 6e 74 29 7b 0a 23 69 66 20 30 20 2f 2a *,int){.#if 0 /*
13d0: 20 48 41 53 48 5f 49 4e 54 20 61 6e 64 20 48 41 HASH_INT and HA
13e0: 53 48 5f 50 4f 49 4e 54 45 52 20 61 72 65 20 6e SH_POINTER are n
13f0: 65 76 65 72 20 75 73 65 64 20 2a 2f 0a 20 20 73 ever used */. s
1400: 77 69 74 63 68 28 20 6b 65 79 43 6c 61 73 73 20 witch( keyClass
1410: 29 7b 0a 20 20 20 20 63 61 73 65 20 53 51 4c 49 ){. case SQLI
1420: 54 45 5f 48 41 53 48 5f 49 4e 54 3a 20 20 20 20 TE_HASH_INT:
1430: 20 72 65 74 75 72 6e 20 26 69 6e 74 43 6f 6d 70 return &intComp
1440: 61 72 65 3b 0a 20 20 20 20 63 61 73 65 20 53 51 are;. case SQ
1450: 4c 49 54 45 5f 48 41 53 48 5f 50 4f 49 4e 54 45 LITE_HASH_POINTE
1460: 52 3a 20 72 65 74 75 72 6e 20 26 70 74 72 43 6f R: return &ptrCo
1470: 6d 70 61 72 65 3b 0a 20 20 20 20 63 61 73 65 20 mpare;. case
1480: 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 49 SQLITE_HASH_STRI
1490: 4e 47 3a 20 20 72 65 74 75 72 6e 20 26 73 74 72 NG: return &str
14a0: 43 6f 6d 70 61 72 65 3b 0a 20 20 20 20 63 61 73 Compare;. cas
14b0: 65 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 e SQLITE_HASH_BI
14c0: 4e 41 52 59 3a 20 20 72 65 74 75 72 6e 20 26 62 NARY: return &b
14d0: 69 6e 43 6f 6d 70 61 72 65 3b 0a 20 20 20 20 64 inCompare;. d
14e0: 65 66 61 75 6c 74 3a 20 62 72 65 61 6b 3b 0a 20 efault: break;.
14f0: 20 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a 23 }. return 0;.#
1500: 65 6c 73 65 0a 20 20 69 66 28 20 6b 65 79 43 6c else. if( keyCl
1510: 61 73 73 3d 3d 53 51 4c 49 54 45 5f 48 41 53 48 ass==SQLITE_HASH
1520: 5f 53 54 52 49 4e 47 20 29 7b 0a 20 20 20 20 72 _STRING ){. r
1530: 65 74 75 72 6e 20 26 73 74 72 43 6f 6d 70 61 72 eturn &strCompar
1540: 65 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 e;. }else{.
1550: 61 73 73 65 72 74 28 20 6b 65 79 43 6c 61 73 73 assert( keyClass
1560: 3d 3d 53 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 ==SQLITE_HASH_BI
1570: 4e 41 52 59 20 29 3b 0a 20 20 20 20 72 65 74 75 NARY );. retu
1580: 72 6e 20 26 62 69 6e 43 6f 6d 70 61 72 65 3b 0a rn &binCompare;.
1590: 20 20 7d 0a 23 65 6e 64 69 66 0a 7d 0a 0a 2f 2a }.#endif.}../*
15a0: 20 4c 69 6e 6b 20 61 6e 20 65 6c 65 6d 65 6e 74 Link an element
15b0: 20 69 6e 74 6f 20 74 68 65 20 68 61 73 68 20 74 into the hash t
15c0: 61 62 6c 65 0a 2a 2f 0a 73 74 61 74 69 63 20 76 able.*/.static v
15d0: 6f 69 64 20 69 6e 73 65 72 74 45 6c 65 6d 65 6e oid insertElemen
15e0: 74 28 0a 20 20 48 61 73 68 20 2a 70 48 2c 20 20 t(. Hash *pH,
15f0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 /* T
1600: 68 65 20 63 6f 6d 70 6c 65 74 65 20 68 61 73 68 he complete hash
1610: 20 74 61 62 6c 65 20 2a 2f 0a 20 20 73 74 72 75 table */. stru
1620: 63 74 20 5f 68 74 20 2a 70 45 6e 74 72 79 2c 20 ct _ht *pEntry,
1630: 20 20 20 2f 2a 20 54 68 65 20 65 6e 74 72 79 20 /* The entry
1640: 69 6e 74 6f 20 77 68 69 63 68 20 70 4e 65 77 20 into which pNew
1650: 69 73 20 69 6e 73 65 72 74 65 64 20 2a 2f 0a 20 is inserted */.
1660: 20 48 61 73 68 45 6c 65 6d 20 2a 70 4e 65 77 20 HashElem *pNew
1670: 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 65 /* The e
1680: 6c 65 6d 65 6e 74 20 74 6f 20 62 65 20 69 6e 73 lement to be ins
1690: 65 72 74 65 64 20 2a 2f 0a 29 7b 0a 20 20 48 61 erted */.){. Ha
16a0: 73 68 45 6c 65 6d 20 2a 70 48 65 61 64 3b 20 20 shElem *pHead;
16b0: 20 20 20 20 20 2f 2a 20 46 69 72 73 74 20 65 6c /* First el
16c0: 65 6d 65 6e 74 20 61 6c 72 65 61 64 79 20 69 6e ement already in
16d0: 20 70 45 6e 74 72 79 20 2a 2f 0a 20 20 70 48 65 pEntry */. pHe
16e0: 61 64 20 3d 20 70 45 6e 74 72 79 2d 3e 63 68 61 ad = pEntry->cha
16f0: 69 6e 3b 0a 20 20 69 66 28 20 70 48 65 61 64 20 in;. if( pHead
1700: 29 7b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 65 78 ){. pNew->nex
1710: 74 20 3d 20 70 48 65 61 64 3b 0a 20 20 20 20 70 t = pHead;. p
1720: 4e 65 77 2d 3e 70 72 65 76 20 3d 20 70 48 65 61 New->prev = pHea
1730: 64 2d 3e 70 72 65 76 3b 0a 20 20 20 20 69 66 28 d->prev;. if(
1740: 20 70 48 65 61 64 2d 3e 70 72 65 76 20 29 7b 20 pHead->prev ){
1750: 70 48 65 61 64 2d 3e 70 72 65 76 2d 3e 6e 65 78 pHead->prev->nex
1760: 74 20 3d 20 70 4e 65 77 3b 20 7d 0a 20 20 20 20 t = pNew; }.
1770: 65 6c 73 65 20 20 20 20 20 20 20 20 20 20 20 20 else
1780: 20 7b 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 70 { pH->first = p
1790: 4e 65 77 3b 20 7d 0a 20 20 20 20 70 48 65 61 64 New; }. pHead
17a0: 2d 3e 70 72 65 76 20 3d 20 70 4e 65 77 3b 0a 20 ->prev = pNew;.
17b0: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 70 4e 65 77 }else{. pNew
17c0: 2d 3e 6e 65 78 74 20 3d 20 70 48 2d 3e 66 69 72 ->next = pH->fir
17d0: 73 74 3b 0a 20 20 20 20 69 66 28 20 70 48 2d 3e st;. if( pH->
17e0: 66 69 72 73 74 20 29 7b 20 70 48 2d 3e 66 69 72 first ){ pH->fir
17f0: 73 74 2d 3e 70 72 65 76 20 3d 20 70 4e 65 77 3b st->prev = pNew;
1800: 20 7d 0a 20 20 20 20 70 4e 65 77 2d 3e 70 72 65 }. pNew->pre
1810: 76 20 3d 20 30 3b 0a 20 20 20 20 70 48 2d 3e 66 v = 0;. pH->f
1820: 69 72 73 74 20 3d 20 70 4e 65 77 3b 0a 20 20 7d irst = pNew;. }
1830: 0a 20 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 . pEntry->count
1840: 2b 2b 3b 0a 20 20 70 45 6e 74 72 79 2d 3e 63 68 ++;. pEntry->ch
1850: 61 69 6e 20 3d 20 70 4e 65 77 3b 0a 7d 0a 0a 0a ain = pNew;.}...
1860: 2f 2a 20 52 65 73 69 7a 65 20 74 68 65 20 68 61 /* Resize the ha
1870: 73 68 20 74 61 62 6c 65 20 73 6f 20 74 68 61 74 sh table so that
1880: 20 69 74 20 63 61 6e 74 61 69 6e 73 20 22 6e 65 it cantains "ne
1890: 77 5f 73 69 7a 65 22 20 62 75 63 6b 65 74 73 2e w_size" buckets.
18a0: 0a 2a 2a 20 22 6e 65 77 5f 73 69 7a 65 22 20 6d .** "new_size" m
18b0: 75 73 74 20 62 65 20 61 20 70 6f 77 65 72 20 6f ust be a power o
18c0: 66 20 32 2e 20 20 54 68 65 20 68 61 73 68 20 74 f 2. The hash t
18d0: 61 62 6c 65 20 6d 69 67 68 74 20 66 61 69 6c 20 able might fail
18e0: 0a 2a 2a 20 74 6f 20 72 65 73 69 7a 65 20 69 66 .** to resize if
18f0: 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 sqlite3_malloc(
1900: 29 20 66 61 69 6c 73 2e 0a 2a 2f 0a 73 74 61 74 ) fails..*/.stat
1910: 69 63 20 76 6f 69 64 20 72 65 68 61 73 68 28 48 ic void rehash(H
1920: 61 73 68 20 2a 70 48 2c 20 69 6e 74 20 6e 65 77 ash *pH, int new
1930: 5f 73 69 7a 65 29 7b 0a 20 20 73 74 72 75 63 74 _size){. struct
1940: 20 5f 68 74 20 2a 6e 65 77 5f 68 74 3b 20 20 20 _ht *new_ht;
1950: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 /* The
1960: 6e 65 77 20 68 61 73 68 20 74 61 62 6c 65 20 2a new hash table *
1970: 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c /. HashElem *el
1980: 65 6d 2c 20 2a 6e 65 78 74 5f 65 6c 65 6d 3b 20 em, *next_elem;
1990: 20 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f 70 69 6e /* For loopin
19a0: 67 20 6f 76 65 72 20 65 78 69 73 74 69 6e 67 20 g over existing
19b0: 65 6c 65 6d 65 6e 74 73 20 2a 2f 0a 20 20 69 6e elements */. in
19c0: 74 20 28 2a 78 48 61 73 68 29 28 63 6f 6e 73 74 t (*xHash)(const
19d0: 20 76 6f 69 64 2a 2c 69 6e 74 29 3b 20 2f 2a 20 void*,int); /*
19e0: 54 68 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f The hash functio
19f0: 6e 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 n */.. assert(
1a00: 28 6e 65 77 5f 73 69 7a 65 20 26 20 28 6e 65 77 (new_size & (new
1a10: 5f 73 69 7a 65 2d 31 29 29 3d 3d 30 20 29 3b 0a _size-1))==0 );.
1a20: 20 20 6e 65 77 5f 68 74 20 3d 20 28 73 74 72 75 new_ht = (stru
1a30: 63 74 20 5f 68 74 20 2a 29 73 71 6c 69 74 65 33 ct _ht *)sqlite3
1a40: 5f 6d 61 6c 6c 6f 63 28 20 6e 65 77 5f 73 69 7a _malloc( new_siz
1a50: 65 2a 73 69 7a 65 6f 66 28 73 74 72 75 63 74 20 e*sizeof(struct
1a60: 5f 68 74 29 20 29 3b 0a 20 20 69 66 28 20 6e 65 _ht) );. if( ne
1a70: 77 5f 68 74 3d 3d 30 20 29 20 72 65 74 75 72 6e w_ht==0 ) return
1a80: 3b 0a 20 20 69 66 28 20 70 48 2d 3e 68 74 20 29 ;. if( pH->ht )
1a90: 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70 48 sqlite3_free(pH
1aa0: 2d 3e 68 74 29 3b 0a 20 20 70 48 2d 3e 68 74 20 ->ht);. pH->ht
1ab0: 3d 20 6e 65 77 5f 68 74 3b 0a 20 20 70 48 2d 3e = new_ht;. pH->
1ac0: 68 74 73 69 7a 65 20 3d 20 6e 65 77 5f 73 69 7a htsize = new_siz
1ad0: 65 3b 0a 20 20 78 48 61 73 68 20 3d 20 68 61 73 e;. xHash = has
1ae0: 68 46 75 6e 63 74 69 6f 6e 28 70 48 2d 3e 6b 65 hFunction(pH->ke
1af0: 79 43 6c 61 73 73 29 3b 0a 20 20 66 6f 72 28 65 yClass);. for(e
1b00: 6c 65 6d 3d 70 48 2d 3e 66 69 72 73 74 2c 20 70 lem=pH->first, p
1b10: 48 2d 3e 66 69 72 73 74 3d 30 3b 20 65 6c 65 6d H->first=0; elem
1b20: 3b 20 65 6c 65 6d 20 3d 20 6e 65 78 74 5f 65 6c ; elem = next_el
1b30: 65 6d 29 7b 0a 20 20 20 20 69 6e 74 20 68 20 3d em){. int h =
1b40: 20 28 2a 78 48 61 73 68 29 28 65 6c 65 6d 2d 3e (*xHash)(elem->
1b50: 70 4b 65 79 2c 20 65 6c 65 6d 2d 3e 6e 4b 65 79 pKey, elem->nKey
1b60: 29 20 26 20 28 6e 65 77 5f 73 69 7a 65 2d 31 29 ) & (new_size-1)
1b70: 3b 0a 20 20 20 20 6e 65 78 74 5f 65 6c 65 6d 20 ;. next_elem
1b80: 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 = elem->next;.
1b90: 20 20 69 6e 73 65 72 74 45 6c 65 6d 65 6e 74 28 insertElement(
1ba0: 70 48 2c 20 26 6e 65 77 5f 68 74 5b 68 5d 2c 20 pH, &new_ht[h],
1bb0: 65 6c 65 6d 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a elem);. }.}../*
1bc0: 20 54 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 28 This function (
1bd0: 66 6f 72 20 69 6e 74 65 72 6e 61 6c 20 75 73 65 for internal use
1be0: 20 6f 6e 6c 79 29 20 6c 6f 63 61 74 65 73 20 61 only) locates a
1bf0: 6e 20 65 6c 65 6d 65 6e 74 20 69 6e 20 61 6e 0a n element in an.
1c00: 2a 2a 20 68 61 73 68 20 74 61 62 6c 65 20 74 68 ** hash table th
1c10: 61 74 20 6d 61 74 63 68 65 73 20 74 68 65 20 67 at matches the g
1c20: 69 76 65 6e 20 6b 65 79 2e 20 20 54 68 65 20 68 iven key. The h
1c30: 61 73 68 20 66 6f 72 20 74 68 69 73 20 6b 65 79 ash for this key
1c40: 20 68 61 73 0a 2a 2a 20 61 6c 72 65 61 64 79 20 has.** already
1c50: 62 65 65 6e 20 63 6f 6d 70 75 74 65 64 20 61 6e been computed an
1c60: 64 20 69 73 20 70 61 73 73 65 64 20 61 73 20 74 d is passed as t
1c70: 68 65 20 34 74 68 20 70 61 72 61 6d 65 74 65 72 he 4th parameter
1c80: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 48 61 73 68 ..*/.static Hash
1c90: 45 6c 65 6d 20 2a 66 69 6e 64 45 6c 65 6d 65 6e Elem *findElemen
1ca0: 74 47 69 76 65 6e 48 61 73 68 28 0a 20 20 63 6f tGivenHash(. co
1cb0: 6e 73 74 20 48 61 73 68 20 2a 70 48 2c 20 20 20 nst Hash *pH,
1cc0: 20 20 2f 2a 20 54 68 65 20 70 48 20 74 6f 20 62 /* The pH to b
1cd0: 65 20 73 65 61 72 63 68 65 64 20 2a 2f 0a 20 20 e searched */.
1ce0: 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 const void *pKey
1cf0: 2c 20 20 20 2f 2a 20 54 68 65 20 6b 65 79 20 77 , /* The key w
1d00: 65 20 61 72 65 20 73 65 61 72 63 68 69 6e 67 20 e are searching
1d10: 66 6f 72 20 2a 2f 0a 20 20 69 6e 74 20 6e 4b 65 for */. int nKe
1d20: 79 2c 0a 20 20 69 6e 74 20 68 20 20 20 20 20 20 y,. int h
1d30: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 /* The
1d40: 68 61 73 68 20 66 6f 72 20 74 68 69 73 20 6b 65 hash for this ke
1d50: 79 2e 20 2a 2f 0a 29 7b 0a 20 20 48 61 73 68 45 y. */.){. HashE
1d60: 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 20 20 lem *elem;
1d70: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 55 73 65 /* Use
1d80: 64 20 74 6f 20 6c 6f 6f 70 20 74 68 72 75 20 74 d to loop thru t
1d90: 68 65 20 65 6c 65 6d 65 6e 74 20 6c 69 73 74 20 he element list
1da0: 2a 2f 0a 20 20 69 6e 74 20 63 6f 75 6e 74 3b 20 */. int count;
1db0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1dc0: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 /* Number of
1dd0: 20 65 6c 65 6d 65 6e 74 73 20 6c 65 66 74 20 74 elements left t
1de0: 6f 20 74 65 73 74 20 2a 2f 0a 20 20 69 6e 74 20 o test */. int
1df0: 28 2a 78 43 6f 6d 70 61 72 65 29 28 63 6f 6e 73 (*xCompare)(cons
1e00: 74 20 76 6f 69 64 2a 2c 69 6e 74 2c 63 6f 6e 73 t void*,int,cons
1e10: 74 20 76 6f 69 64 2a 2c 69 6e 74 29 3b 20 20 2f t void*,int); /
1e20: 2a 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75 6e * comparison fun
1e30: 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20 69 66 28 20 ction */.. if(
1e40: 70 48 2d 3e 68 74 20 29 7b 0a 20 20 20 20 73 74 pH->ht ){. st
1e50: 72 75 63 74 20 5f 68 74 20 2a 70 45 6e 74 72 79 ruct _ht *pEntry
1e60: 20 3d 20 26 70 48 2d 3e 68 74 5b 68 5d 3b 0a 20 = &pH->ht[h];.
1e70: 20 20 20 65 6c 65 6d 20 3d 20 70 45 6e 74 72 79 elem = pEntry
1e80: 2d 3e 63 68 61 69 6e 3b 0a 20 20 20 20 63 6f 75 ->chain;. cou
1e90: 6e 74 20 3d 20 70 45 6e 74 72 79 2d 3e 63 6f 75 nt = pEntry->cou
1ea0: 6e 74 3b 0a 20 20 20 20 78 43 6f 6d 70 61 72 65 nt;. xCompare
1eb0: 20 3d 20 63 6f 6d 70 61 72 65 46 75 6e 63 74 69 = compareFuncti
1ec0: 6f 6e 28 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29 on(pH->keyClass)
1ed0: 3b 0a 20 20 20 20 77 68 69 6c 65 28 20 63 6f 75 ;. while( cou
1ee0: 6e 74 2d 2d 20 26 26 20 65 6c 65 6d 20 29 7b 0a nt-- && elem ){.
1ef0: 20 20 20 20 20 20 69 66 28 20 28 2a 78 43 6f 6d if( (*xCom
1f00: 70 61 72 65 29 28 65 6c 65 6d 2d 3e 70 4b 65 79 pare)(elem->pKey
1f10: 2c 65 6c 65 6d 2d 3e 6e 4b 65 79 2c 70 4b 65 79 ,elem->nKey,pKey
1f20: 2c 6e 4b 65 79 29 3d 3d 30 20 29 7b 20 0a 20 20 ,nKey)==0 ){ .
1f30: 20 20 20 20 20 20 72 65 74 75 72 6e 20 65 6c 65 return ele
1f40: 6d 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 m;. }.
1f50: 20 65 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65 elem = elem->ne
1f60: 78 74 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 xt;. }. }.
1f70: 72 65 74 75 72 6e 20 30 3b 0a 7d 0a 0a 2f 2a 20 return 0;.}../*
1f80: 52 65 6d 6f 76 65 20 61 20 73 69 6e 67 6c 65 20 Remove a single
1f90: 65 6e 74 72 79 20 66 72 6f 6d 20 74 68 65 20 68 entry from the h
1fa0: 61 73 68 20 74 61 62 6c 65 20 67 69 76 65 6e 20 ash table given
1fb0: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 61 a pointer to tha
1fc0: 74 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 61 6e 64 t.** element and
1fd0: 20 61 20 68 61 73 68 20 6f 6e 20 74 68 65 20 65 a hash on the e
1fe0: 6c 65 6d 65 6e 74 27 73 20 6b 65 79 2e 0a 2a 2f lement's key..*/
1ff0: 0a 73 74 61 74 69 63 20 76 6f 69 64 20 72 65 6d .static void rem
2000: 6f 76 65 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48 oveElementGivenH
2010: 61 73 68 28 0a 20 20 48 61 73 68 20 2a 70 48 2c ash(. Hash *pH,
2020: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 /* The
2030: 70 48 20 63 6f 6e 74 61 69 6e 69 6e 67 20 22 65 pH containing "e
2040: 6c 65 6d 22 20 2a 2f 0a 20 20 48 61 73 68 45 6c lem" */. HashEl
2050: 65 6d 2a 20 65 6c 65 6d 2c 20 20 20 2f 2a 20 54 em* elem, /* T
2060: 68 65 20 65 6c 65 6d 65 6e 74 20 74 6f 20 62 65 he element to be
2070: 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74 68 removed from th
2080: 65 20 70 48 20 2a 2f 0a 20 20 69 6e 74 20 68 20 e pH */. int h
2090: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 48 /* H
20a0: 61 73 68 20 76 61 6c 75 65 20 66 6f 72 20 74 68 ash value for th
20b0: 65 20 65 6c 65 6d 65 6e 74 20 2a 2f 0a 29 7b 0a e element */.){.
20c0: 20 20 73 74 72 75 63 74 20 5f 68 74 20 2a 70 45 struct _ht *pE
20d0: 6e 74 72 79 3b 0a 20 20 69 66 28 20 65 6c 65 6d ntry;. if( elem
20e0: 2d 3e 70 72 65 76 20 29 7b 0a 20 20 20 20 65 6c ->prev ){. el
20f0: 65 6d 2d 3e 70 72 65 76 2d 3e 6e 65 78 74 20 3d em->prev->next =
2100: 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 20 0a 20 20 elem->next; .
2110: 7d 65 6c 73 65 7b 0a 20 20 20 20 70 48 2d 3e 66 }else{. pH->f
2120: 69 72 73 74 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 irst = elem->nex
2130: 74 3b 0a 20 20 7d 0a 20 20 69 66 28 20 65 6c 65 t;. }. if( ele
2140: 6d 2d 3e 6e 65 78 74 20 29 7b 0a 20 20 20 20 65 m->next ){. e
2150: 6c 65 6d 2d 3e 6e 65 78 74 2d 3e 70 72 65 76 20 lem->next->prev
2160: 3d 20 65 6c 65 6d 2d 3e 70 72 65 76 3b 0a 20 20 = elem->prev;.
2170: 7d 0a 20 20 70 45 6e 74 72 79 20 3d 20 26 70 48 }. pEntry = &pH
2180: 2d 3e 68 74 5b 68 5d 3b 0a 20 20 69 66 28 20 70 ->ht[h];. if( p
2190: 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3d 3d 65 6c Entry->chain==el
21a0: 65 6d 20 29 7b 0a 20 20 20 20 70 45 6e 74 72 79 em ){. pEntry
21b0: 2d 3e 63 68 61 69 6e 20 3d 20 65 6c 65 6d 2d 3e ->chain = elem->
21c0: 6e 65 78 74 3b 0a 20 20 7d 0a 20 20 70 45 6e 74 next;. }. pEnt
21d0: 72 79 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a 20 20 69 ry->count--;. i
21e0: 66 28 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 f( pEntry->count
21f0: 3c 3d 30 20 29 7b 0a 20 20 20 20 70 45 6e 74 72 <=0 ){. pEntr
2200: 79 2d 3e 63 68 61 69 6e 20 3d 20 30 3b 0a 20 20 y->chain = 0;.
2210: 7d 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f 70 79 }. if( pH->copy
2220: 4b 65 79 20 29 7b 0a 20 20 20 20 73 71 6c 69 74 Key ){. sqlit
2230: 65 33 5f 66 72 65 65 28 65 6c 65 6d 2d 3e 70 4b e3_free(elem->pK
2240: 65 79 29 3b 0a 20 20 7d 0a 20 20 73 71 6c 69 74 ey);. }. sqlit
2250: 65 33 5f 66 72 65 65 28 20 65 6c 65 6d 20 29 3b e3_free( elem );
2260: 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a . pH->count--;.
2270: 20 20 69 66 28 20 70 48 2d 3e 63 6f 75 6e 74 3c if( pH->count<
2280: 3d 30 20 29 7b 0a 20 20 20 20 61 73 73 65 72 74 =0 ){. assert
2290: 28 20 70 48 2d 3e 66 69 72 73 74 3d 3d 30 20 29 ( pH->first==0 )
22a0: 3b 0a 20 20 20 20 61 73 73 65 72 74 28 20 70 48 ;. assert( pH
22b0: 2d 3e 63 6f 75 6e 74 3d 3d 30 20 29 3b 0a 20 20 ->count==0 );.
22c0: 20 20 73 71 6c 69 74 65 33 48 61 73 68 43 6c 65 sqlite3HashCle
22d0: 61 72 28 70 48 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f ar(pH);. }.}../
22e0: 2a 20 41 74 74 65 6d 70 74 20 74 6f 20 6c 6f 63 * Attempt to loc
22f0: 61 74 65 20 61 6e 20 65 6c 65 6d 65 6e 74 20 6f ate an element o
2300: 66 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 f the hash table
2310: 20 70 48 20 77 69 74 68 20 61 20 6b 65 79 0a 2a pH with a key.*
2320: 2a 20 74 68 61 74 20 6d 61 74 63 68 65 73 20 70 * that matches p
2330: 4b 65 79 2c 6e 4b 65 79 2e 20 20 52 65 74 75 72 Key,nKey. Retur
2340: 6e 20 74 68 65 20 64 61 74 61 20 66 6f 72 20 74 n the data for t
2350: 68 69 73 20 65 6c 65 6d 65 6e 74 20 69 66 20 69 his element if i
2360: 74 20 69 73 0a 2a 2a 20 66 6f 75 6e 64 2c 20 6f t is.** found, o
2370: 72 20 4e 55 4c 4c 20 69 66 20 74 68 65 72 65 20 r NULL if there
2380: 69 73 20 6e 6f 20 6d 61 74 63 68 2e 0a 2a 2f 0a is no match..*/.
2390: 76 6f 69 64 20 2a 73 71 6c 69 74 65 33 48 61 73 void *sqlite3Has
23a0: 68 46 69 6e 64 28 63 6f 6e 73 74 20 48 61 73 68 hFind(const Hash
23b0: 20 2a 70 48 2c 20 63 6f 6e 73 74 20 76 6f 69 64 *pH, const void
23c0: 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 *pKey, int nKey
23d0: 29 7b 0a 20 20 69 6e 74 20 68 3b 20 20 20 20 20 ){. int h;
23e0: 20 20 20 20 20 20 20 20 2f 2a 20 41 20 68 61 73 /* A has
23f0: 68 20 6f 6e 20 6b 65 79 20 2a 2f 0a 20 20 48 61 h on key */. Ha
2400: 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 shElem *elem;
2410: 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e 74 20 /* The element
2420: 74 68 61 74 20 6d 61 74 63 68 65 73 20 6b 65 79 that matches key
2430: 20 2a 2f 0a 20 20 69 6e 74 20 28 2a 78 48 61 73 */. int (*xHas
2440: 68 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 h)(const void*,i
2450: 6e 74 29 3b 20 20 2f 2a 20 54 68 65 20 68 61 73 nt); /* The has
2460: 68 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 h function */..
2470: 20 69 66 28 20 70 48 3d 3d 30 20 7c 7c 20 70 48 if( pH==0 || pH
2480: 2d 3e 68 74 3d 3d 30 20 29 20 72 65 74 75 72 6e ->ht==0 ) return
2490: 20 30 3b 0a 20 20 78 48 61 73 68 20 3d 20 68 61 0;. xHash = ha
24a0: 73 68 46 75 6e 63 74 69 6f 6e 28 70 48 2d 3e 6b shFunction(pH->k
24b0: 65 79 43 6c 61 73 73 29 3b 0a 20 20 61 73 73 65 eyClass);. asse
24c0: 72 74 28 20 78 48 61 73 68 21 3d 30 20 29 3b 0a rt( xHash!=0 );.
24d0: 20 20 68 20 3d 20 28 2a 78 48 61 73 68 29 28 70 h = (*xHash)(p
24e0: 4b 65 79 2c 6e 4b 65 79 29 3b 0a 20 20 61 73 73 Key,nKey);. ass
24f0: 65 72 74 28 20 28 70 48 2d 3e 68 74 73 69 7a 65 ert( (pH->htsize
2500: 20 26 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31 & (pH->htsize-1
2510: 29 29 3d 3d 30 20 29 3b 0a 20 20 65 6c 65 6d 20 ))==0 );. elem
2520: 3d 20 66 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76 = findElementGiv
2530: 65 6e 48 61 73 68 28 70 48 2c 70 4b 65 79 2c 6e enHash(pH,pKey,n
2540: 4b 65 79 2c 20 68 20 26 20 28 70 48 2d 3e 68 74 Key, h & (pH->ht
2550: 73 69 7a 65 2d 31 29 29 3b 0a 20 20 72 65 74 75 size-1));. retu
2560: 72 6e 20 65 6c 65 6d 20 3f 20 65 6c 65 6d 2d 3e rn elem ? elem->
2570: 64 61 74 61 20 3a 20 30 3b 0a 7d 0a 0a 2f 2a 20 data : 0;.}../*
2580: 49 6e 73 65 72 74 20 61 6e 20 65 6c 65 6d 65 6e Insert an elemen
2590: 74 20 69 6e 74 6f 20 74 68 65 20 68 61 73 68 20 t into the hash
25a0: 74 61 62 6c 65 20 70 48 2e 20 20 54 68 65 20 6b table pH. The k
25b0: 65 79 20 69 73 20 70 4b 65 79 2c 6e 4b 65 79 0a ey is pKey,nKey.
25c0: 2a 2a 20 61 6e 64 20 74 68 65 20 64 61 74 61 20 ** and the data
25d0: 69 73 20 22 64 61 74 61 22 2e 0a 2a 2a 0a 2a 2a is "data"..**.**
25e0: 20 49 66 20 6e 6f 20 65 6c 65 6d 65 6e 74 20 65 If no element e
25f0: 78 69 73 74 73 20 77 69 74 68 20 61 20 6d 61 74 xists with a mat
2600: 63 68 69 6e 67 20 6b 65 79 2c 20 74 68 65 6e 20 ching key, then
2610: 61 20 6e 65 77 0a 2a 2a 20 65 6c 65 6d 65 6e 74 a new.** element
2620: 20 69 73 20 63 72 65 61 74 65 64 2e 20 20 41 20 is created. A
2630: 63 6f 70 79 20 6f 66 20 74 68 65 20 6b 65 79 20 copy of the key
2640: 69 73 20 6d 61 64 65 20 69 66 20 74 68 65 20 63 is made if the c
2650: 6f 70 79 4b 65 79 0a 2a 2a 20 66 6c 61 67 20 69 opyKey.** flag i
2660: 73 20 73 65 74 2e 20 20 4e 55 4c 4c 20 69 73 20 s set. NULL is
2670: 72 65 74 75 72 6e 65 64 2e 0a 2a 2a 0a 2a 2a 20 returned..**.**
2680: 49 66 20 61 6e 6f 74 68 65 72 20 65 6c 65 6d 65 If another eleme
2690: 6e 74 20 61 6c 72 65 61 64 79 20 65 78 69 73 74 nt already exist
26a0: 73 20 77 69 74 68 20 74 68 65 20 73 61 6d 65 20 s with the same
26b0: 6b 65 79 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a key, then the.**
26c0: 20 6e 65 77 20 64 61 74 61 20 72 65 70 6c 61 63 new data replac
26d0: 65 73 20 74 68 65 20 6f 6c 64 20 64 61 74 61 20 es the old data
26e0: 61 6e 64 20 74 68 65 20 6f 6c 64 20 64 61 74 61 and the old data
26f0: 20 69 73 20 72 65 74 75 72 6e 65 64 2e 0a 2a 2a is returned..**
2700: 20 54 68 65 20 6b 65 79 20 69 73 20 6e 6f 74 20 The key is not
2710: 63 6f 70 69 65 64 20 69 6e 20 74 68 69 73 20 69 copied in this i
2720: 6e 73 74 61 6e 63 65 2e 20 20 49 66 20 61 20 6d nstance. If a m
2730: 61 6c 6c 6f 63 20 66 61 69 6c 73 2c 20 74 68 65 alloc fails, the
2740: 6e 0a 2a 2a 20 74 68 65 20 6e 65 77 20 64 61 74 n.** the new dat
2750: 61 20 69 73 20 72 65 74 75 72 6e 65 64 20 61 6e a is returned an
2760: 64 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 d the hash table
2770: 20 69 73 20 75 6e 63 68 61 6e 67 65 64 2e 0a 2a is unchanged..*
2780: 2a 0a 2a 2a 20 49 66 20 74 68 65 20 22 64 61 74 *.** If the "dat
2790: 61 22 20 70 61 72 61 6d 65 74 65 72 20 74 6f 20 a" parameter to
27a0: 74 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 69 73 this function is
27b0: 20 4e 55 4c 4c 2c 20 74 68 65 6e 20 74 68 65 0a NULL, then the.
27c0: 2a 2a 20 65 6c 65 6d 65 6e 74 20 63 6f 72 72 65 ** element corre
27d0: 73 70 6f 6e 64 69 6e 67 20 74 6f 20 22 6b 65 79 sponding to "key
27e0: 22 20 69 73 20 72 65 6d 6f 76 65 64 20 66 72 6f " is removed fro
27f0: 6d 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 m the hash table
2800: 2e 0a 2a 2f 0a 76 6f 69 64 20 2a 73 71 6c 69 74 ..*/.void *sqlit
2810: 65 33 48 61 73 68 49 6e 73 65 72 74 28 48 61 73 e3HashInsert(Has
2820: 68 20 2a 70 48 2c 20 63 6f 6e 73 74 20 76 6f 69 h *pH, const voi
2830: 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 d *pKey, int nKe
2840: 79 2c 20 76 6f 69 64 20 2a 64 61 74 61 29 7b 0a y, void *data){.
2850: 20 20 69 6e 74 20 68 72 61 77 3b 20 20 20 20 20 int hraw;
2860: 20 20 20 20 20 20 20 20 2f 2a 20 52 61 77 20 68 /* Raw h
2870: 61 73 68 20 76 61 6c 75 65 20 6f 66 20 74 68 65 ash value of the
2880: 20 6b 65 79 20 2a 2f 0a 20 20 69 6e 74 20 68 3b key */. int h;
2890: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
28a0: 2f 2a 20 74 68 65 20 68 61 73 68 20 6f 66 20 74 /* the hash of t
28b0: 68 65 20 6b 65 79 20 6d 6f 64 75 6c 6f 20 68 61 he key modulo ha
28c0: 73 68 20 74 61 62 6c 65 20 73 69 7a 65 20 2a 2f sh table size */
28d0: 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 . HashElem *ele
28e0: 6d 3b 20 20 20 20 20 20 20 2f 2a 20 55 73 65 64 m; /* Used
28f0: 20 74 6f 20 6c 6f 6f 70 20 74 68 72 75 20 74 68 to loop thru th
2900: 65 20 65 6c 65 6d 65 6e 74 20 6c 69 73 74 20 2a e element list *
2910: 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 6e 65 /. HashElem *ne
2920: 77 5f 65 6c 65 6d 3b 20 20 20 2f 2a 20 4e 65 77 w_elem; /* New
2930: 20 65 6c 65 6d 65 6e 74 20 61 64 64 65 64 20 74 element added t
2940: 6f 20 74 68 65 20 70 48 20 2a 2f 0a 20 20 69 6e o the pH */. in
2950: 74 20 28 2a 78 48 61 73 68 29 28 63 6f 6e 73 74 t (*xHash)(const
2960: 20 76 6f 69 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a void*,int); /*
2970: 20 54 68 65 20 68 61 73 68 20 66 75 6e 63 74 69 The hash functi
2980: 6f 6e 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 on */.. assert(
2990: 20 70 48 21 3d 30 20 29 3b 0a 20 20 78 48 61 73 pH!=0 );. xHas
29a0: 68 20 3d 20 68 61 73 68 46 75 6e 63 74 69 6f 6e h = hashFunction
29b0: 28 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a (pH->keyClass);.
29c0: 20 20 61 73 73 65 72 74 28 20 78 48 61 73 68 21 assert( xHash!
29d0: 3d 30 20 29 3b 0a 20 20 68 72 61 77 20 3d 20 28 =0 );. hraw = (
29e0: 2a 78 48 61 73 68 29 28 70 4b 65 79 2c 20 6e 4b *xHash)(pKey, nK
29f0: 65 79 29 3b 0a 20 20 61 73 73 65 72 74 28 20 28 ey);. assert( (
2a00: 70 48 2d 3e 68 74 73 69 7a 65 20 26 20 28 70 48 pH->htsize & (pH
2a10: 2d 3e 68 74 73 69 7a 65 2d 31 29 29 3d 3d 30 20 ->htsize-1))==0
2a20: 29 3b 0a 20 20 68 20 3d 20 68 72 61 77 20 26 20 );. h = hraw &
2a30: 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29 3b 0a (pH->htsize-1);.
2a40: 20 20 65 6c 65 6d 20 3d 20 66 69 6e 64 45 6c 65 elem = findEle
2a50: 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28 70 48 mentGivenHash(pH
2a60: 2c 70 4b 65 79 2c 6e 4b 65 79 2c 68 29 3b 0a 20 ,pKey,nKey,h);.
2a70: 20 69 66 28 20 65 6c 65 6d 20 29 7b 0a 20 20 20 if( elem ){.
2a80: 20 76 6f 69 64 20 2a 6f 6c 64 5f 64 61 74 61 20 void *old_data
2a90: 3d 20 65 6c 65 6d 2d 3e 64 61 74 61 3b 0a 20 20 = elem->data;.
2aa0: 20 20 69 66 28 20 64 61 74 61 3d 3d 30 20 29 7b if( data==0 ){
2ab0: 0a 20 20 20 20 20 20 72 65 6d 6f 76 65 45 6c 65 . removeEle
2ac0: 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28 70 48 mentGivenHash(pH
2ad0: 2c 65 6c 65 6d 2c 68 29 3b 0a 20 20 20 20 7d 65 ,elem,h);. }e
2ae0: 6c 73 65 7b 0a 20 20 20 20 20 20 65 6c 65 6d 2d lse{. elem-
2af0: 3e 64 61 74 61 20 3d 20 64 61 74 61 3b 0a 20 20 >data = data;.
2b00: 20 20 7d 0a 20 20 20 20 72 65 74 75 72 6e 20 6f }. return o
2b10: 6c 64 5f 64 61 74 61 3b 0a 20 20 7d 0a 20 20 69 ld_data;. }. i
2b20: 66 28 20 64 61 74 61 3d 3d 30 20 29 20 72 65 74 f( data==0 ) ret
2b30: 75 72 6e 20 30 3b 0a 20 20 6e 65 77 5f 65 6c 65 urn 0;. new_ele
2b40: 6d 20 3d 20 28 48 61 73 68 45 6c 65 6d 2a 29 73 m = (HashElem*)s
2b50: 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 20 73 qlite3_malloc( s
2b60: 69 7a 65 6f 66 28 48 61 73 68 45 6c 65 6d 29 20 izeof(HashElem)
2b70: 29 3b 0a 20 20 69 66 28 20 6e 65 77 5f 65 6c 65 );. if( new_ele
2b80: 6d 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 64 61 m==0 ) return da
2b90: 74 61 3b 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f ta;. if( pH->co
2ba0: 70 79 4b 65 79 20 26 26 20 70 4b 65 79 21 3d 30 pyKey && pKey!=0
2bb0: 20 29 7b 0a 20 20 20 20 6e 65 77 5f 65 6c 65 6d ){. new_elem
2bc0: 2d 3e 70 4b 65 79 20 3d 20 73 71 6c 69 74 65 33 ->pKey = sqlite3
2bd0: 5f 6d 61 6c 6c 6f 63 28 20 6e 4b 65 79 20 29 3b _malloc( nKey );
2be0: 0a 20 20 20 20 69 66 28 20 6e 65 77 5f 65 6c 65 . if( new_ele
2bf0: 6d 2d 3e 70 4b 65 79 3d 3d 30 20 29 7b 0a 20 20 m->pKey==0 ){.
2c00: 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 sqlite3_free
2c10: 28 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20 20 20 20 (new_elem);.
2c20: 20 20 72 65 74 75 72 6e 20 64 61 74 61 3b 0a 20 return data;.
2c30: 20 20 20 7d 0a 20 20 20 20 6d 65 6d 63 70 79 28 }. memcpy(
2c40: 28 76 6f 69 64 2a 29 6e 65 77 5f 65 6c 65 6d 2d (void*)new_elem-
2c50: 3e 70 4b 65 79 2c 20 70 4b 65 79 2c 20 6e 4b 65 >pKey, pKey, nKe
2c60: 79 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 y);. }else{.
2c70: 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 20 new_elem->pKey
2c80: 3d 20 28 76 6f 69 64 2a 29 70 4b 65 79 3b 0a 20 = (void*)pKey;.
2c90: 20 7d 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 6e }. new_elem->n
2ca0: 4b 65 79 20 3d 20 6e 4b 65 79 3b 0a 20 20 70 48 Key = nKey;. pH
2cb0: 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20 20 69 66 28 ->count++;. if(
2cc0: 20 70 48 2d 3e 68 74 73 69 7a 65 3d 3d 30 20 29 pH->htsize==0 )
2cd0: 7b 0a 20 20 20 20 72 65 68 61 73 68 28 70 48 2c {. rehash(pH,
2ce0: 38 29 3b 0a 20 20 20 20 69 66 28 20 70 48 2d 3e 8);. if( pH->
2cf0: 68 74 73 69 7a 65 3d 3d 30 20 29 7b 0a 20 20 20 htsize==0 ){.
2d00: 20 20 20 70 48 2d 3e 63 6f 75 6e 74 20 3d 20 30 pH->count = 0
2d10: 3b 0a 20 20 20 20 20 20 69 66 28 20 70 48 2d 3e ;. if( pH->
2d20: 63 6f 70 79 4b 65 79 20 29 7b 0a 20 20 20 20 20 copyKey ){.
2d30: 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 sqlite3_free(
2d40: 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 29 3b new_elem->pKey);
2d50: 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 73 . }. s
2d60: 71 6c 69 74 65 33 5f 66 72 65 65 28 6e 65 77 5f qlite3_free(new_
2d70: 65 6c 65 6d 29 3b 0a 20 20 20 20 20 20 72 65 74 elem);. ret
2d80: 75 72 6e 20 64 61 74 61 3b 0a 20 20 20 20 7d 0a urn data;. }.
2d90: 20 20 7d 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f }. if( pH->co
2da0: 75 6e 74 20 3e 20 70 48 2d 3e 68 74 73 69 7a 65 unt > pH->htsize
2db0: 20 29 7b 0a 20 20 20 20 72 65 68 61 73 68 28 70 ){. rehash(p
2dc0: 48 2c 70 48 2d 3e 68 74 73 69 7a 65 2a 32 29 3b H,pH->htsize*2);
2dd0: 0a 20 20 7d 0a 20 20 61 73 73 65 72 74 28 20 70 . }. assert( p
2de0: 48 2d 3e 68 74 73 69 7a 65 3e 30 20 29 3b 0a 20 H->htsize>0 );.
2df0: 20 61 73 73 65 72 74 28 20 28 70 48 2d 3e 68 74 assert( (pH->ht
2e00: 73 69 7a 65 20 26 20 28 70 48 2d 3e 68 74 73 69 size & (pH->htsi
2e10: 7a 65 2d 31 29 29 3d 3d 30 20 29 3b 0a 20 20 68 ze-1))==0 );. h
2e20: 20 3d 20 68 72 61 77 20 26 20 28 70 48 2d 3e 68 = hraw & (pH->h
2e30: 74 73 69 7a 65 2d 31 29 3b 0a 20 20 69 6e 73 65 tsize-1);. inse
2e40: 72 74 45 6c 65 6d 65 6e 74 28 70 48 2c 20 26 70 rtElement(pH, &p
2e50: 48 2d 3e 68 74 5b 68 5d 2c 20 6e 65 77 5f 65 6c H->ht[h], new_el
2e60: 65 6d 29 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d em);. new_elem-
2e70: 3e 64 61 74 61 20 3d 20 64 61 74 61 3b 0a 20 20 >data = data;.
2e80: 72 65 74 75 72 6e 20 30 3b 0a 7d 0a return 0;.}.