/ Hex Artifact Content
Login

Artifact 2dc6afe7478a0b739499af360c8863c900ea11a8:


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 35 20 32 30 30 38 2f 30 31 2f  ,v 1.25 2008/01/
01e0: 32 32 20 32 31 3a 33 30 3a 35 33 20 64 72 68 20  22 21:30:53 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: 0a 20 20 2f 2a 20 54 68 65 72 65 20 69 73 20 61  .  /* There is a
1a30: 20 63 61 6c 6c 20 74 6f 20 73 71 6c 69 74 65 33   call to sqlite3
1a40: 5f 6d 61 6c 6c 6f 63 28 29 20 69 6e 73 69 64 65  _malloc() inside
1a50: 20 72 65 68 61 73 68 28 29 2e 20 49 66 20 74 68   rehash(). If th
1a60: 65 72 65 20 69 73 0a 20 20 2a 2a 20 61 6c 72 65  ere is.  ** alre
1a70: 61 64 79 20 61 6e 20 61 6c 6c 6f 63 61 74 69 6f  ady an allocatio
1a80: 6e 20 61 74 20 70 48 2d 3e 68 74 2c 20 74 68 65  n at pH->ht, the
1a90: 6e 20 69 66 20 74 68 69 73 20 6d 61 6c 6c 6f 63  n if this malloc
1aa0: 28 29 20 66 61 69 6c 73 20 69 74 0a 20 20 2a 2a  () fails it.  **
1ab0: 20 69 73 20 62 65 6e 69 67 6e 20 28 73 69 6e 63   is benign (sinc
1ac0: 65 20 66 61 69 6c 69 6e 67 20 74 6f 20 72 65 73  e failing to res
1ad0: 69 7a 65 20 61 20 68 61 73 68 20 74 61 62 6c 65  ize a hash table
1ae0: 20 69 73 20 61 20 70 65 72 66 6f 72 6d 61 6e 63   is a performanc
1af0: 65 0a 20 20 2a 2a 20 68 69 74 20 6f 6e 6c 79 2c  e.  ** hit only,
1b00: 20 6e 6f 74 20 61 20 66 61 74 61 6c 20 65 72 72   not a fatal err
1b10: 6f 72 29 2e 0a 20 20 2a 2f 0a 20 20 73 71 6c 69  or)..  */.  sqli
1b20: 74 65 33 46 61 75 6c 74 42 65 6e 69 67 6e 28 53  te3FaultBenign(S
1b30: 51 4c 49 54 45 5f 46 41 55 4c 54 49 4e 4a 45 43  QLITE_FAULTINJEC
1b40: 54 4f 52 5f 4d 41 4c 4c 4f 43 2c 20 70 48 2d 3e  TOR_MALLOC, pH->
1b50: 68 74 73 69 7a 65 3e 30 29 3b 0a 20 20 6e 65 77  htsize>0);.  new
1b60: 5f 68 74 20 3d 20 28 73 74 72 75 63 74 20 5f 68  _ht = (struct _h
1b70: 74 20 2a 29 73 71 6c 69 74 65 33 4d 61 6c 6c 6f  t *)sqlite3Mallo
1b80: 63 5a 65 72 6f 28 20 6e 65 77 5f 73 69 7a 65 2a  cZero( new_size*
1b90: 73 69 7a 65 6f 66 28 73 74 72 75 63 74 20 5f 68  sizeof(struct _h
1ba0: 74 29 20 29 3b 0a 20 20 73 71 6c 69 74 65 33 46  t) );.  sqlite3F
1bb0: 61 75 6c 74 42 65 6e 69 67 6e 28 53 51 4c 49 54  aultBenign(SQLIT
1bc0: 45 5f 46 41 55 4c 54 49 4e 4a 45 43 54 4f 52 5f  E_FAULTINJECTOR_
1bd0: 4d 41 4c 4c 4f 43 2c 20 30 29 3b 0a 0a 20 20 69  MALLOC, 0);..  i
1be0: 66 28 20 6e 65 77 5f 68 74 3d 3d 30 20 29 20 72  f( new_ht==0 ) r
1bf0: 65 74 75 72 6e 3b 0a 20 20 69 66 28 20 70 48 2d  eturn;.  if( pH-
1c00: 3e 68 74 20 29 20 73 71 6c 69 74 65 33 5f 66 72  >ht ) sqlite3_fr
1c10: 65 65 28 70 48 2d 3e 68 74 29 3b 0a 20 20 70 48  ee(pH->ht);.  pH
1c20: 2d 3e 68 74 20 3d 20 6e 65 77 5f 68 74 3b 0a 20  ->ht = new_ht;. 
1c30: 20 70 48 2d 3e 68 74 73 69 7a 65 20 3d 20 6e 65   pH->htsize = ne
1c40: 77 5f 73 69 7a 65 3b 0a 20 20 78 48 61 73 68 20  w_size;.  xHash 
1c50: 3d 20 68 61 73 68 46 75 6e 63 74 69 6f 6e 28 70  = hashFunction(p
1c60: 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20  H->keyClass);.  
1c70: 66 6f 72 28 65 6c 65 6d 3d 70 48 2d 3e 66 69 72  for(elem=pH->fir
1c80: 73 74 2c 20 70 48 2d 3e 66 69 72 73 74 3d 30 3b  st, pH->first=0;
1c90: 20 65 6c 65 6d 3b 20 65 6c 65 6d 20 3d 20 6e 65   elem; elem = ne
1ca0: 78 74 5f 65 6c 65 6d 29 7b 0a 20 20 20 20 69 6e  xt_elem){.    in
1cb0: 74 20 68 20 3d 20 28 2a 78 48 61 73 68 29 28 65  t h = (*xHash)(e
1cc0: 6c 65 6d 2d 3e 70 4b 65 79 2c 20 65 6c 65 6d 2d  lem->pKey, elem-
1cd0: 3e 6e 4b 65 79 29 20 26 20 28 6e 65 77 5f 73 69  >nKey) & (new_si
1ce0: 7a 65 2d 31 29 3b 0a 20 20 20 20 6e 65 78 74 5f  ze-1);.    next_
1cf0: 65 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78  elem = elem->nex
1d00: 74 3b 0a 20 20 20 20 69 6e 73 65 72 74 45 6c 65  t;.    insertEle
1d10: 6d 65 6e 74 28 70 48 2c 20 26 6e 65 77 5f 68 74  ment(pH, &new_ht
1d20: 5b 68 5d 2c 20 65 6c 65 6d 29 3b 0a 20 20 7d 0a  [h], elem);.  }.
1d30: 7d 0a 0a 2f 2a 20 54 68 69 73 20 66 75 6e 63 74  }../* This funct
1d40: 69 6f 6e 20 28 66 6f 72 20 69 6e 74 65 72 6e 61  ion (for interna
1d50: 6c 20 75 73 65 20 6f 6e 6c 79 29 20 6c 6f 63 61  l use only) loca
1d60: 74 65 73 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69  tes an element i
1d70: 6e 20 61 6e 0a 2a 2a 20 68 61 73 68 20 74 61 62  n an.** hash tab
1d80: 6c 65 20 74 68 61 74 20 6d 61 74 63 68 65 73 20  le that matches 
1d90: 74 68 65 20 67 69 76 65 6e 20 6b 65 79 2e 20 20  the given key.  
1da0: 54 68 65 20 68 61 73 68 20 66 6f 72 20 74 68 69  The hash for thi
1db0: 73 20 6b 65 79 20 68 61 73 0a 2a 2a 20 61 6c 72  s key has.** alr
1dc0: 65 61 64 79 20 62 65 65 6e 20 63 6f 6d 70 75 74  eady been comput
1dd0: 65 64 20 61 6e 64 20 69 73 20 70 61 73 73 65 64  ed and is passed
1de0: 20 61 73 20 74 68 65 20 34 74 68 20 70 61 72 61   as the 4th para
1df0: 6d 65 74 65 72 2e 0a 2a 2f 0a 73 74 61 74 69 63  meter..*/.static
1e00: 20 48 61 73 68 45 6c 65 6d 20 2a 66 69 6e 64 45   HashElem *findE
1e10: 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28  lementGivenHash(
1e20: 0a 20 20 63 6f 6e 73 74 20 48 61 73 68 20 2a 70  .  const Hash *p
1e30: 48 2c 20 20 20 20 20 2f 2a 20 54 68 65 20 70 48  H,     /* The pH
1e40: 20 74 6f 20 62 65 20 73 65 61 72 63 68 65 64 20   to be searched 
1e50: 2a 2f 0a 20 20 63 6f 6e 73 74 20 76 6f 69 64 20  */.  const void 
1e60: 2a 70 4b 65 79 2c 20 20 20 2f 2a 20 54 68 65 20  *pKey,   /* The 
1e70: 6b 65 79 20 77 65 20 61 72 65 20 73 65 61 72 63  key we are searc
1e80: 68 69 6e 67 20 66 6f 72 20 2a 2f 0a 20 20 69 6e  hing for */.  in
1e90: 74 20 6e 4b 65 79 2c 0a 20 20 69 6e 74 20 68 20  t nKey,.  int h 
1ea0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
1eb0: 20 54 68 65 20 68 61 73 68 20 66 6f 72 20 74 68   The hash for th
1ec0: 69 73 20 6b 65 79 2e 20 2a 2f 0a 29 7b 0a 20 20  is key. */.){.  
1ed0: 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20  HashElem *elem; 
1ee0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
1ef0: 2a 20 55 73 65 64 20 74 6f 20 6c 6f 6f 70 20 74  * Used to loop t
1f00: 68 72 75 20 74 68 65 20 65 6c 65 6d 65 6e 74 20  hru the element 
1f10: 6c 69 73 74 20 2a 2f 0a 20 20 69 6e 74 20 63 6f  list */.  int co
1f20: 75 6e 74 3b 20 20 20 20 20 20 20 20 20 20 20 20  unt;            
1f30: 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62           /* Numb
1f40: 65 72 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20 6c  er of elements l
1f50: 65 66 74 20 74 6f 20 74 65 73 74 20 2a 2f 0a 20  eft to test */. 
1f60: 20 69 6e 74 20 28 2a 78 43 6f 6d 70 61 72 65 29   int (*xCompare)
1f70: 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74  (const void*,int
1f80: 2c 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74  ,const void*,int
1f90: 29 3b 20 20 2f 2a 20 63 6f 6d 70 61 72 69 73 6f  );  /* compariso
1fa0: 6e 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20  n function */.. 
1fb0: 20 69 66 28 20 70 48 2d 3e 68 74 20 29 7b 0a 20   if( pH->ht ){. 
1fc0: 20 20 20 73 74 72 75 63 74 20 5f 68 74 20 2a 70     struct _ht *p
1fd0: 45 6e 74 72 79 20 3d 20 26 70 48 2d 3e 68 74 5b  Entry = &pH->ht[
1fe0: 68 5d 3b 0a 20 20 20 20 65 6c 65 6d 20 3d 20 70  h];.    elem = p
1ff0: 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3b 0a 20 20  Entry->chain;.  
2000: 20 20 63 6f 75 6e 74 20 3d 20 70 45 6e 74 72 79    count = pEntry
2010: 2d 3e 63 6f 75 6e 74 3b 0a 20 20 20 20 78 43 6f  ->count;.    xCo
2020: 6d 70 61 72 65 20 3d 20 63 6f 6d 70 61 72 65 46  mpare = compareF
2030: 75 6e 63 74 69 6f 6e 28 70 48 2d 3e 6b 65 79 43  unction(pH->keyC
2040: 6c 61 73 73 29 3b 0a 20 20 20 20 77 68 69 6c 65  lass);.    while
2050: 28 20 63 6f 75 6e 74 2d 2d 20 26 26 20 65 6c 65  ( count-- && ele
2060: 6d 20 29 7b 0a 20 20 20 20 20 20 69 66 28 20 28  m ){.      if( (
2070: 2a 78 43 6f 6d 70 61 72 65 29 28 65 6c 65 6d 2d  *xCompare)(elem-
2080: 3e 70 4b 65 79 2c 65 6c 65 6d 2d 3e 6e 4b 65 79  >pKey,elem->nKey
2090: 2c 70 4b 65 79 2c 6e 4b 65 79 29 3d 3d 30 20 29  ,pKey,nKey)==0 )
20a0: 7b 20 0a 20 20 20 20 20 20 20 20 72 65 74 75 72  { .        retur
20b0: 6e 20 65 6c 65 6d 3b 0a 20 20 20 20 20 20 7d 0a  n elem;.      }.
20c0: 20 20 20 20 20 20 65 6c 65 6d 20 3d 20 65 6c 65        elem = ele
20d0: 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 7d 0a 20  m->next;.    }. 
20e0: 20 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d   }.  return 0;.}
20f0: 0a 0a 2f 2a 20 52 65 6d 6f 76 65 20 61 20 73 69  ../* Remove a si
2100: 6e 67 6c 65 20 65 6e 74 72 79 20 66 72 6f 6d 20  ngle entry from 
2110: 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 67  the hash table g
2120: 69 76 65 6e 20 61 20 70 6f 69 6e 74 65 72 20 74  iven a pointer t
2130: 6f 20 74 68 61 74 0a 2a 2a 20 65 6c 65 6d 65 6e  o that.** elemen
2140: 74 20 61 6e 64 20 61 20 68 61 73 68 20 6f 6e 20  t and a hash on 
2150: 74 68 65 20 65 6c 65 6d 65 6e 74 27 73 20 6b 65  the element's ke
2160: 79 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69  y..*/.static voi
2170: 64 20 72 65 6d 6f 76 65 45 6c 65 6d 65 6e 74 47  d removeElementG
2180: 69 76 65 6e 48 61 73 68 28 0a 20 20 48 61 73 68  ivenHash(.  Hash
2190: 20 2a 70 48 2c 20 20 20 20 20 20 20 20 20 2f 2a   *pH,         /*
21a0: 20 54 68 65 20 70 48 20 63 6f 6e 74 61 69 6e 69   The pH containi
21b0: 6e 67 20 22 65 6c 65 6d 22 20 2a 2f 0a 20 20 48  ng "elem" */.  H
21c0: 61 73 68 45 6c 65 6d 2a 20 65 6c 65 6d 2c 20 20  ashElem* elem,  
21d0: 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e 74 20   /* The element 
21e0: 74 6f 20 62 65 20 72 65 6d 6f 76 65 64 20 66 72  to be removed fr
21f0: 6f 6d 20 74 68 65 20 70 48 20 2a 2f 0a 20 20 69  om the pH */.  i
2200: 6e 74 20 68 20 20 20 20 20 20 20 20 20 20 20 20  nt h            
2210: 20 2f 2a 20 48 61 73 68 20 76 61 6c 75 65 20 66   /* Hash value f
2220: 6f 72 20 74 68 65 20 65 6c 65 6d 65 6e 74 20 2a  or the element *
2230: 2f 0a 29 7b 0a 20 20 73 74 72 75 63 74 20 5f 68  /.){.  struct _h
2240: 74 20 2a 70 45 6e 74 72 79 3b 0a 20 20 69 66 28  t *pEntry;.  if(
2250: 20 65 6c 65 6d 2d 3e 70 72 65 76 20 29 7b 0a 20   elem->prev ){. 
2260: 20 20 20 65 6c 65 6d 2d 3e 70 72 65 76 2d 3e 6e     elem->prev->n
2270: 65 78 74 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74  ext = elem->next
2280: 3b 20 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20  ; .  }else{.    
2290: 70 48 2d 3e 66 69 72 73 74 20 3d 20 65 6c 65 6d  pH->first = elem
22a0: 2d 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20 20 69 66  ->next;.  }.  if
22b0: 28 20 65 6c 65 6d 2d 3e 6e 65 78 74 20 29 7b 0a  ( elem->next ){.
22c0: 20 20 20 20 65 6c 65 6d 2d 3e 6e 65 78 74 2d 3e      elem->next->
22d0: 70 72 65 76 20 3d 20 65 6c 65 6d 2d 3e 70 72 65  prev = elem->pre
22e0: 76 3b 0a 20 20 7d 0a 20 20 70 45 6e 74 72 79 20  v;.  }.  pEntry 
22f0: 3d 20 26 70 48 2d 3e 68 74 5b 68 5d 3b 0a 20 20  = &pH->ht[h];.  
2300: 69 66 28 20 70 45 6e 74 72 79 2d 3e 63 68 61 69  if( pEntry->chai
2310: 6e 3d 3d 65 6c 65 6d 20 29 7b 0a 20 20 20 20 70  n==elem ){.    p
2320: 45 6e 74 72 79 2d 3e 63 68 61 69 6e 20 3d 20 65  Entry->chain = e
2330: 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20  lem->next;.  }. 
2340: 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 2d 2d   pEntry->count--
2350: 3b 0a 20 20 69 66 28 20 70 45 6e 74 72 79 2d 3e  ;.  if( pEntry->
2360: 63 6f 75 6e 74 3c 3d 30 20 29 7b 0a 20 20 20 20  count<=0 ){.    
2370: 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 20 3d 20  pEntry->chain = 
2380: 30 3b 0a 20 20 7d 0a 20 20 69 66 28 20 70 48 2d  0;.  }.  if( pH-
2390: 3e 63 6f 70 79 4b 65 79 20 29 7b 0a 20 20 20 20  >copyKey ){.    
23a0: 73 71 6c 69 74 65 33 5f 66 72 65 65 28 65 6c 65  sqlite3_free(ele
23b0: 6d 2d 3e 70 4b 65 79 29 3b 0a 20 20 7d 0a 20 20  m->pKey);.  }.  
23c0: 73 71 6c 69 74 65 33 5f 66 72 65 65 28 20 65 6c  sqlite3_free( el
23d0: 65 6d 20 29 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e  em );.  pH->coun
23e0: 74 2d 2d 3b 0a 20 20 69 66 28 20 70 48 2d 3e 63  t--;.  if( pH->c
23f0: 6f 75 6e 74 3c 3d 30 20 29 7b 0a 20 20 20 20 61  ount<=0 ){.    a
2400: 73 73 65 72 74 28 20 70 48 2d 3e 66 69 72 73 74  ssert( pH->first
2410: 3d 3d 30 20 29 3b 0a 20 20 20 20 61 73 73 65 72  ==0 );.    asser
2420: 74 28 20 70 48 2d 3e 63 6f 75 6e 74 3d 3d 30 20  t( pH->count==0 
2430: 29 3b 0a 20 20 20 20 73 71 6c 69 74 65 33 48 61  );.    sqlite3Ha
2440: 73 68 43 6c 65 61 72 28 70 48 29 3b 0a 20 20 7d  shClear(pH);.  }
2450: 0a 7d 0a 0a 2f 2a 20 41 74 74 65 6d 70 74 20 74  .}../* Attempt t
2460: 6f 20 6c 6f 63 61 74 65 20 61 6e 20 65 6c 65 6d  o locate an elem
2470: 65 6e 74 20 6f 66 20 74 68 65 20 68 61 73 68 20  ent of the hash 
2480: 74 61 62 6c 65 20 70 48 20 77 69 74 68 20 61 20  table pH with a 
2490: 6b 65 79 0a 2a 2a 20 74 68 61 74 20 6d 61 74 63  key.** that matc
24a0: 68 65 73 20 70 4b 65 79 2c 6e 4b 65 79 2e 20 20  hes pKey,nKey.  
24b0: 52 65 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 72  Return a pointer
24c0: 20 74 6f 20 74 68 65 20 63 6f 72 72 65 73 70 6f   to the correspo
24d0: 6e 64 69 6e 67 20 0a 2a 2a 20 48 61 73 68 45 6c  nding .** HashEl
24e0: 65 6d 20 73 74 72 75 63 74 75 72 65 20 66 6f 72  em structure for
24f0: 20 74 68 69 73 20 65 6c 65 6d 65 6e 74 20 69 66   this element if
2500: 20 69 74 20 69 73 20 66 6f 75 6e 64 2c 20 6f 72   it is found, or
2510: 20 4e 55 4c 4c 0a 2a 2a 20 6f 74 68 65 72 77 69   NULL.** otherwi
2520: 73 65 2e 0a 2a 2f 0a 48 61 73 68 45 6c 65 6d 20  se..*/.HashElem 
2530: 2a 73 71 6c 69 74 65 33 48 61 73 68 46 69 6e 64  *sqlite3HashFind
2540: 45 6c 65 6d 28 63 6f 6e 73 74 20 48 61 73 68 20  Elem(const Hash 
2550: 2a 70 48 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20  *pH, const void 
2560: 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29  *pKey, int nKey)
2570: 7b 0a 20 20 69 6e 74 20 68 3b 20 20 20 20 20 20  {.  int h;      
2580: 20 20 20 20 20 20 20 2f 2a 20 41 20 68 61 73 68         /* A hash
2590: 20 6f 6e 20 6b 65 79 20 2a 2f 0a 20 20 48 61 73   on key */.  Has
25a0: 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20  hElem *elem;    
25b0: 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e 74 20 74  /* The element t
25c0: 68 61 74 20 6d 61 74 63 68 65 73 20 6b 65 79 20  hat matches key 
25d0: 2a 2f 0a 20 20 69 6e 74 20 28 2a 78 48 61 73 68  */.  int (*xHash
25e0: 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e  )(const void*,in
25f0: 74 29 3b 20 20 2f 2a 20 54 68 65 20 68 61 73 68  t);  /* The hash
2600: 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20   function */..  
2610: 69 66 28 20 70 48 3d 3d 30 20 7c 7c 20 70 48 2d  if( pH==0 || pH-
2620: 3e 68 74 3d 3d 30 20 29 20 72 65 74 75 72 6e 20  >ht==0 ) return 
2630: 30 3b 0a 20 20 78 48 61 73 68 20 3d 20 68 61 73  0;.  xHash = has
2640: 68 46 75 6e 63 74 69 6f 6e 28 70 48 2d 3e 6b 65  hFunction(pH->ke
2650: 79 43 6c 61 73 73 29 3b 0a 20 20 61 73 73 65 72  yClass);.  asser
2660: 74 28 20 78 48 61 73 68 21 3d 30 20 29 3b 0a 20  t( xHash!=0 );. 
2670: 20 68 20 3d 20 28 2a 78 48 61 73 68 29 28 70 4b   h = (*xHash)(pK
2680: 65 79 2c 6e 4b 65 79 29 3b 0a 20 20 61 73 73 65  ey,nKey);.  asse
2690: 72 74 28 20 28 70 48 2d 3e 68 74 73 69 7a 65 20  rt( (pH->htsize 
26a0: 26 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29  & (pH->htsize-1)
26b0: 29 3d 3d 30 20 29 3b 0a 20 20 65 6c 65 6d 20 3d  )==0 );.  elem =
26c0: 20 66 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65   findElementGive
26d0: 6e 48 61 73 68 28 70 48 2c 70 4b 65 79 2c 6e 4b  nHash(pH,pKey,nK
26e0: 65 79 2c 20 68 20 26 20 28 70 48 2d 3e 68 74 73  ey, h & (pH->hts
26f0: 69 7a 65 2d 31 29 29 3b 0a 20 20 72 65 74 75 72  ize-1));.  retur
2700: 6e 20 65 6c 65 6d 3b 0a 7d 0a 0a 2f 2a 20 41 74  n elem;.}../* At
2710: 74 65 6d 70 74 20 74 6f 20 6c 6f 63 61 74 65 20  tempt to locate 
2720: 61 6e 20 65 6c 65 6d 65 6e 74 20 6f 66 20 74 68  an element of th
2730: 65 20 68 61 73 68 20 74 61 62 6c 65 20 70 48 20  e hash table pH 
2740: 77 69 74 68 20 61 20 6b 65 79 0a 2a 2a 20 74 68  with a key.** th
2750: 61 74 20 6d 61 74 63 68 65 73 20 70 4b 65 79 2c  at matches pKey,
2760: 6e 4b 65 79 2e 20 20 52 65 74 75 72 6e 20 74 68  nKey.  Return th
2770: 65 20 64 61 74 61 20 66 6f 72 20 74 68 69 73 20  e data for this 
2780: 65 6c 65 6d 65 6e 74 20 69 66 20 69 74 20 69 73  element if it is
2790: 0a 2a 2a 20 66 6f 75 6e 64 2c 20 6f 72 20 4e 55  .** found, or NU
27a0: 4c 4c 20 69 66 20 74 68 65 72 65 20 69 73 20 6e  LL if there is n
27b0: 6f 20 6d 61 74 63 68 2e 0a 2a 2f 0a 76 6f 69 64  o match..*/.void
27c0: 20 2a 73 71 6c 69 74 65 33 48 61 73 68 46 69 6e   *sqlite3HashFin
27d0: 64 28 63 6f 6e 73 74 20 48 61 73 68 20 2a 70 48  d(const Hash *pH
27e0: 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b  , const void *pK
27f0: 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20  ey, int nKey){. 
2800: 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b   HashElem *elem;
2810: 20 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65      /* The eleme
2820: 6e 74 20 74 68 61 74 20 6d 61 74 63 68 65 73 20  nt that matches 
2830: 6b 65 79 20 2a 2f 0a 20 20 65 6c 65 6d 20 3d 20  key */.  elem = 
2840: 73 71 6c 69 74 65 33 48 61 73 68 46 69 6e 64 45  sqlite3HashFindE
2850: 6c 65 6d 28 70 48 2c 20 70 4b 65 79 2c 20 6e 4b  lem(pH, pKey, nK
2860: 65 79 29 3b 0a 20 20 72 65 74 75 72 6e 20 65 6c  ey);.  return el
2870: 65 6d 20 3f 20 65 6c 65 6d 2d 3e 64 61 74 61 20  em ? elem->data 
2880: 3a 20 30 3b 0a 7d 0a 0a 2f 2a 20 49 6e 73 65 72  : 0;.}../* Inser
2890: 74 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69 6e 74  t an element int
28a0: 6f 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65  o the hash table
28b0: 20 70 48 2e 20 20 54 68 65 20 6b 65 79 20 69 73   pH.  The key is
28c0: 20 70 4b 65 79 2c 6e 4b 65 79 0a 2a 2a 20 61 6e   pKey,nKey.** an
28d0: 64 20 74 68 65 20 64 61 74 61 20 69 73 20 22 64  d the data is "d
28e0: 61 74 61 22 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 6e  ata"..**.** If n
28f0: 6f 20 65 6c 65 6d 65 6e 74 20 65 78 69 73 74 73  o element exists
2900: 20 77 69 74 68 20 61 20 6d 61 74 63 68 69 6e 67   with a matching
2910: 20 6b 65 79 2c 20 74 68 65 6e 20 61 20 6e 65 77   key, then a new
2920: 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 69 73 20 63  .** element is c
2930: 72 65 61 74 65 64 2e 20 20 41 20 63 6f 70 79 20  reated.  A copy 
2940: 6f 66 20 74 68 65 20 6b 65 79 20 69 73 20 6d 61  of the key is ma
2950: 64 65 20 69 66 20 74 68 65 20 63 6f 70 79 4b 65  de if the copyKe
2960: 79 0a 2a 2a 20 66 6c 61 67 20 69 73 20 73 65 74  y.** flag is set
2970: 2e 20 20 4e 55 4c 4c 20 69 73 20 72 65 74 75 72  .  NULL is retur
2980: 6e 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 61 6e  ned..**.** If an
2990: 6f 74 68 65 72 20 65 6c 65 6d 65 6e 74 20 61 6c  other element al
29a0: 72 65 61 64 79 20 65 78 69 73 74 73 20 77 69 74  ready exists wit
29b0: 68 20 74 68 65 20 73 61 6d 65 20 6b 65 79 2c 20  h the same key, 
29c0: 74 68 65 6e 20 74 68 65 0a 2a 2a 20 6e 65 77 20  then the.** new 
29d0: 64 61 74 61 20 72 65 70 6c 61 63 65 73 20 74 68  data replaces th
29e0: 65 20 6f 6c 64 20 64 61 74 61 20 61 6e 64 20 74  e old data and t
29f0: 68 65 20 6f 6c 64 20 64 61 74 61 20 69 73 20 72  he old data is r
2a00: 65 74 75 72 6e 65 64 2e 0a 2a 2a 20 54 68 65 20  eturned..** The 
2a10: 6b 65 79 20 69 73 20 6e 6f 74 20 63 6f 70 69 65  key is not copie
2a20: 64 20 69 6e 20 74 68 69 73 20 69 6e 73 74 61 6e  d in this instan
2a30: 63 65 2e 20 20 49 66 20 61 20 6d 61 6c 6c 6f 63  ce.  If a malloc
2a40: 20 66 61 69 6c 73 2c 20 74 68 65 6e 0a 2a 2a 20   fails, then.** 
2a50: 74 68 65 20 6e 65 77 20 64 61 74 61 20 69 73 20  the new data is 
2a60: 72 65 74 75 72 6e 65 64 20 61 6e 64 20 74 68 65  returned and the
2a70: 20 68 61 73 68 20 74 61 62 6c 65 20 69 73 20 75   hash table is u
2a80: 6e 63 68 61 6e 67 65 64 2e 0a 2a 2a 0a 2a 2a 20  nchanged..**.** 
2a90: 49 66 20 74 68 65 20 22 64 61 74 61 22 20 70 61  If the "data" pa
2aa0: 72 61 6d 65 74 65 72 20 74 6f 20 74 68 69 73 20  rameter to this 
2ab0: 66 75 6e 63 74 69 6f 6e 20 69 73 20 4e 55 4c 4c  function is NULL
2ac0: 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20 65 6c  , then the.** el
2ad0: 65 6d 65 6e 74 20 63 6f 72 72 65 73 70 6f 6e 64  ement correspond
2ae0: 69 6e 67 20 74 6f 20 22 6b 65 79 22 20 69 73 20  ing to "key" is 
2af0: 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74 68 65  removed from the
2b00: 20 68 61 73 68 20 74 61 62 6c 65 2e 0a 2a 2f 0a   hash table..*/.
2b10: 76 6f 69 64 20 2a 73 71 6c 69 74 65 33 48 61 73  void *sqlite3Has
2b20: 68 49 6e 73 65 72 74 28 48 61 73 68 20 2a 70 48  hInsert(Hash *pH
2b30: 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b  , const void *pK
2b40: 65 79 2c 20 69 6e 74 20 6e 4b 65 79 2c 20 76 6f  ey, int nKey, vo
2b50: 69 64 20 2a 64 61 74 61 29 7b 0a 20 20 69 6e 74  id *data){.  int
2b60: 20 68 72 61 77 3b 20 20 20 20 20 20 20 20 20 20   hraw;          
2b70: 20 20 20 2f 2a 20 52 61 77 20 68 61 73 68 20 76     /* Raw hash v
2b80: 61 6c 75 65 20 6f 66 20 74 68 65 20 6b 65 79 20  alue of the key 
2b90: 2a 2f 0a 20 20 69 6e 74 20 68 3b 20 20 20 20 20  */.  int h;     
2ba0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 74 68             /* th
2bb0: 65 20 68 61 73 68 20 6f 66 20 74 68 65 20 6b 65  e hash of the ke
2bc0: 79 20 6d 6f 64 75 6c 6f 20 68 61 73 68 20 74 61  y modulo hash ta
2bd0: 62 6c 65 20 73 69 7a 65 20 2a 2f 0a 20 20 48 61  ble size */.  Ha
2be0: 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20  shElem *elem;   
2bf0: 20 20 20 20 2f 2a 20 55 73 65 64 20 74 6f 20 6c      /* Used to l
2c00: 6f 6f 70 20 74 68 72 75 20 74 68 65 20 65 6c 65  oop thru the ele
2c10: 6d 65 6e 74 20 6c 69 73 74 20 2a 2f 0a 20 20 48  ment list */.  H
2c20: 61 73 68 45 6c 65 6d 20 2a 6e 65 77 5f 65 6c 65  ashElem *new_ele
2c30: 6d 3b 20 20 20 2f 2a 20 4e 65 77 20 65 6c 65 6d  m;   /* New elem
2c40: 65 6e 74 20 61 64 64 65 64 20 74 6f 20 74 68 65  ent added to the
2c50: 20 70 48 20 2a 2f 0a 20 20 69 6e 74 20 28 2a 78   pH */.  int (*x
2c60: 48 61 73 68 29 28 63 6f 6e 73 74 20 76 6f 69 64  Hash)(const void
2c70: 2a 2c 69 6e 74 29 3b 20 20 2f 2a 20 54 68 65 20  *,int);  /* The 
2c80: 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 2a 2f  hash function */
2c90: 0a 0a 20 20 61 73 73 65 72 74 28 20 70 48 21 3d  ..  assert( pH!=
2ca0: 30 20 29 3b 0a 20 20 78 48 61 73 68 20 3d 20 68  0 );.  xHash = h
2cb0: 61 73 68 46 75 6e 63 74 69 6f 6e 28 70 48 2d 3e  ashFunction(pH->
2cc0: 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20 61 73 73  keyClass);.  ass
2cd0: 65 72 74 28 20 78 48 61 73 68 21 3d 30 20 29 3b  ert( xHash!=0 );
2ce0: 0a 20 20 68 72 61 77 20 3d 20 28 2a 78 48 61 73  .  hraw = (*xHas
2cf0: 68 29 28 70 4b 65 79 2c 20 6e 4b 65 79 29 3b 0a  h)(pKey, nKey);.
2d00: 20 20 61 73 73 65 72 74 28 20 28 70 48 2d 3e 68    assert( (pH->h
2d10: 74 73 69 7a 65 20 26 20 28 70 48 2d 3e 68 74 73  tsize & (pH->hts
2d20: 69 7a 65 2d 31 29 29 3d 3d 30 20 29 3b 0a 20 20  ize-1))==0 );.  
2d30: 68 20 3d 20 68 72 61 77 20 26 20 28 70 48 2d 3e  h = hraw & (pH->
2d40: 68 74 73 69 7a 65 2d 31 29 3b 0a 20 20 65 6c 65  htsize-1);.  ele
2d50: 6d 20 3d 20 66 69 6e 64 45 6c 65 6d 65 6e 74 47  m = findElementG
2d60: 69 76 65 6e 48 61 73 68 28 70 48 2c 70 4b 65 79  ivenHash(pH,pKey
2d70: 2c 6e 4b 65 79 2c 68 29 3b 0a 20 20 69 66 28 20  ,nKey,h);.  if( 
2d80: 65 6c 65 6d 20 29 7b 0a 20 20 20 20 76 6f 69 64  elem ){.    void
2d90: 20 2a 6f 6c 64 5f 64 61 74 61 20 3d 20 65 6c 65   *old_data = ele
2da0: 6d 2d 3e 64 61 74 61 3b 0a 20 20 20 20 69 66 28  m->data;.    if(
2db0: 20 64 61 74 61 3d 3d 30 20 29 7b 0a 20 20 20 20   data==0 ){.    
2dc0: 20 20 72 65 6d 6f 76 65 45 6c 65 6d 65 6e 74 47    removeElementG
2dd0: 69 76 65 6e 48 61 73 68 28 70 48 2c 65 6c 65 6d  ivenHash(pH,elem
2de0: 2c 68 29 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a  ,h);.    }else{.
2df0: 20 20 20 20 20 20 65 6c 65 6d 2d 3e 64 61 74 61        elem->data
2e00: 20 3d 20 64 61 74 61 3b 0a 20 20 20 20 20 20 69   = data;.      i
2e10: 66 28 20 21 70 48 2d 3e 63 6f 70 79 4b 65 79 20  f( !pH->copyKey 
2e20: 29 7b 0a 20 20 20 20 20 20 20 20 65 6c 65 6d 2d  ){.        elem-
2e30: 3e 70 4b 65 79 20 3d 20 28 76 6f 69 64 20 2a 29  >pKey = (void *)
2e40: 70 4b 65 79 3b 0a 20 20 20 20 20 20 7d 0a 20 20  pKey;.      }.  
2e50: 20 20 20 20 61 73 73 65 72 74 28 6e 4b 65 79 3d      assert(nKey=
2e60: 3d 65 6c 65 6d 2d 3e 6e 4b 65 79 29 3b 0a 20 20  =elem->nKey);.  
2e70: 20 20 7d 0a 20 20 20 20 72 65 74 75 72 6e 20 6f    }.    return o
2e80: 6c 64 5f 64 61 74 61 3b 0a 20 20 7d 0a 20 20 69  ld_data;.  }.  i
2e90: 66 28 20 64 61 74 61 3d 3d 30 20 29 20 72 65 74  f( data==0 ) ret
2ea0: 75 72 6e 20 30 3b 0a 20 20 6e 65 77 5f 65 6c 65  urn 0;.  new_ele
2eb0: 6d 20 3d 20 28 48 61 73 68 45 6c 65 6d 2a 29 73  m = (HashElem*)s
2ec0: 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 20 73  qlite3_malloc( s
2ed0: 69 7a 65 6f 66 28 48 61 73 68 45 6c 65 6d 29 20  izeof(HashElem) 
2ee0: 29 3b 0a 20 20 69 66 28 20 6e 65 77 5f 65 6c 65  );.  if( new_ele
2ef0: 6d 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 64 61  m==0 ) return da
2f00: 74 61 3b 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f  ta;.  if( pH->co
2f10: 70 79 4b 65 79 20 26 26 20 70 4b 65 79 21 3d 30  pyKey && pKey!=0
2f20: 20 29 7b 0a 20 20 20 20 6e 65 77 5f 65 6c 65 6d   ){.    new_elem
2f30: 2d 3e 70 4b 65 79 20 3d 20 73 71 6c 69 74 65 33  ->pKey = sqlite3
2f40: 5f 6d 61 6c 6c 6f 63 28 20 6e 4b 65 79 20 29 3b  _malloc( nKey );
2f50: 0a 20 20 20 20 69 66 28 20 6e 65 77 5f 65 6c 65  .    if( new_ele
2f60: 6d 2d 3e 70 4b 65 79 3d 3d 30 20 29 7b 0a 20 20  m->pKey==0 ){.  
2f70: 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65      sqlite3_free
2f80: 28 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20 20 20 20  (new_elem);.    
2f90: 20 20 72 65 74 75 72 6e 20 64 61 74 61 3b 0a 20    return data;. 
2fa0: 20 20 20 7d 0a 20 20 20 20 6d 65 6d 63 70 79 28     }.    memcpy(
2fb0: 28 76 6f 69 64 2a 29 6e 65 77 5f 65 6c 65 6d 2d  (void*)new_elem-
2fc0: 3e 70 4b 65 79 2c 20 70 4b 65 79 2c 20 6e 4b 65  >pKey, pKey, nKe
2fd0: 79 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20  y);.  }else{.   
2fe0: 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 20   new_elem->pKey 
2ff0: 3d 20 28 76 6f 69 64 2a 29 70 4b 65 79 3b 0a 20  = (void*)pKey;. 
3000: 20 7d 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 6e   }.  new_elem->n
3010: 4b 65 79 20 3d 20 6e 4b 65 79 3b 0a 20 20 70 48  Key = nKey;.  pH
3020: 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20 20 69 66 28  ->count++;.  if(
3030: 20 70 48 2d 3e 68 74 73 69 7a 65 3d 3d 30 20 29   pH->htsize==0 )
3040: 7b 0a 20 20 20 20 72 65 68 61 73 68 28 70 48 2c  {.    rehash(pH,
3050: 38 29 3b 0a 20 20 20 20 69 66 28 20 70 48 2d 3e  8);.    if( pH->
3060: 68 74 73 69 7a 65 3d 3d 30 20 29 7b 0a 20 20 20  htsize==0 ){.   
3070: 20 20 20 70 48 2d 3e 63 6f 75 6e 74 20 3d 20 30     pH->count = 0
3080: 3b 0a 20 20 20 20 20 20 69 66 28 20 70 48 2d 3e  ;.      if( pH->
3090: 63 6f 70 79 4b 65 79 20 29 7b 0a 20 20 20 20 20  copyKey ){.     
30a0: 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28     sqlite3_free(
30b0: 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 29 3b  new_elem->pKey);
30c0: 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 73  .      }.      s
30d0: 71 6c 69 74 65 33 5f 66 72 65 65 28 6e 65 77 5f  qlite3_free(new_
30e0: 65 6c 65 6d 29 3b 0a 20 20 20 20 20 20 72 65 74  elem);.      ret
30f0: 75 72 6e 20 64 61 74 61 3b 0a 20 20 20 20 7d 0a  urn data;.    }.
3100: 20 20 7d 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f    }.  if( pH->co
3110: 75 6e 74 20 3e 20 70 48 2d 3e 68 74 73 69 7a 65  unt > pH->htsize
3120: 20 29 7b 0a 20 20 20 20 72 65 68 61 73 68 28 70   ){.    rehash(p
3130: 48 2c 70 48 2d 3e 68 74 73 69 7a 65 2a 32 29 3b  H,pH->htsize*2);
3140: 0a 20 20 7d 0a 20 20 61 73 73 65 72 74 28 20 70  .  }.  assert( p
3150: 48 2d 3e 68 74 73 69 7a 65 3e 30 20 29 3b 0a 20  H->htsize>0 );. 
3160: 20 61 73 73 65 72 74 28 20 28 70 48 2d 3e 68 74   assert( (pH->ht
3170: 73 69 7a 65 20 26 20 28 70 48 2d 3e 68 74 73 69  size & (pH->htsi
3180: 7a 65 2d 31 29 29 3d 3d 30 20 29 3b 0a 20 20 68  ze-1))==0 );.  h
3190: 20 3d 20 68 72 61 77 20 26 20 28 70 48 2d 3e 68   = hraw & (pH->h
31a0: 74 73 69 7a 65 2d 31 29 3b 0a 20 20 69 6e 73 65  tsize-1);.  inse
31b0: 72 74 45 6c 65 6d 65 6e 74 28 70 48 2c 20 26 70  rtElement(pH, &p
31c0: 48 2d 3e 68 74 5b 68 5d 2c 20 6e 65 77 5f 65 6c  H->ht[h], new_el
31d0: 65 6d 29 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d  em);.  new_elem-
31e0: 3e 64 61 74 61 20 3d 20 64 61 74 61 3b 0a 20 20  >data = data;.  
31f0: 72 65 74 75 72 6e 20 30 3b 0a 7d 0a              return 0;.}.