/ Hex Artifact Content
Login

Artifact 283864c1adf546d4f0a6ee3694b62beeda8fbd35:


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 39 20 32 30 30 38 2f 30 36 2f  ,v 1.29 2008/06/
01e0: 31 35 20 30 32 3a 35 31 3a 34 37 20 64 72 68 20  15 02:51:47 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 73 71 6c 69 74 65 33  t = 0;.  sqlite3
0760: 5f 66 72 65 65 28 70 48 2d 3e 68 74 29 3b 0a 20  _free(pH->ht);. 
0770: 20 70 48 2d 3e 68 74 20 3d 20 30 3b 0a 20 20 70   pH->ht = 0;.  p
0780: 48 2d 3e 68 74 73 69 7a 65 20 3d 20 30 3b 0a 20  H->htsize = 0;. 
0790: 20 77 68 69 6c 65 28 20 65 6c 65 6d 20 29 7b 0a   while( elem ){.
07a0: 20 20 20 20 48 61 73 68 45 6c 65 6d 20 2a 6e 65      HashElem *ne
07b0: 78 74 5f 65 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e  xt_elem = elem->
07c0: 6e 65 78 74 3b 0a 20 20 20 20 69 66 28 20 70 48  next;.    if( pH
07d0: 2d 3e 63 6f 70 79 4b 65 79 20 26 26 20 65 6c 65  ->copyKey && ele
07e0: 6d 2d 3e 70 4b 65 79 20 29 7b 0a 20 20 20 20 20  m->pKey ){.     
07f0: 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 65 6c   sqlite3_free(el
0800: 65 6d 2d 3e 70 4b 65 79 29 3b 0a 20 20 20 20 7d  em->pKey);.    }
0810: 0a 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65  .    sqlite3_fre
0820: 65 28 65 6c 65 6d 29 3b 0a 20 20 20 20 65 6c 65  e(elem);.    ele
0830: 6d 20 3d 20 6e 65 78 74 5f 65 6c 65 6d 3b 0a 20  m = next_elem;. 
0840: 20 7d 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 20 3d   }.  pH->count =
0850: 20 30 3b 0a 7d 0a 0a 23 69 66 20 30 20 2f 2a 20   0;.}..#if 0 /* 
0860: 4e 4f 54 20 55 53 45 44 20 2a 2f 0a 2f 2a 0a 2a  NOT USED */./*.*
0870: 2a 20 48 61 73 68 20 61 6e 64 20 63 6f 6d 70 61  * Hash and compa
0880: 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 20  rison functions 
0890: 77 68 65 6e 20 74 68 65 20 6d 6f 64 65 20 69 73  when the mode is
08a0: 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 49 4e 54   SQLITE_HASH_INT
08b0: 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 69  .*/.static int i
08c0: 6e 74 48 61 73 68 28 63 6f 6e 73 74 20 76 6f 69  ntHash(const voi
08d0: 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65  d *pKey, int nKe
08e0: 79 29 7b 0a 20 20 72 65 74 75 72 6e 20 6e 4b 65  y){.  return nKe
08f0: 79 20 5e 20 28 6e 4b 65 79 3c 3c 38 29 20 5e 20  y ^ (nKey<<8) ^ 
0900: 28 6e 4b 65 79 3e 3e 38 29 3b 0a 7d 0a 73 74 61  (nKey>>8);.}.sta
0910: 74 69 63 20 69 6e 74 20 69 6e 74 43 6f 6d 70 61  tic int intCompa
0920: 72 65 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70  re(const void *p
0930: 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c 20 63 6f  Key1, int n1, co
0940: 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 32 2c  nst void *pKey2,
0950: 20 69 6e 74 20 6e 32 29 7b 0a 20 20 72 65 74 75   int n2){.  retu
0960: 72 6e 20 6e 32 20 2d 20 6e 31 3b 0a 7d 0a 23 65  rn n2 - n1;.}.#e
0970: 6e 64 69 66 0a 0a 23 69 66 20 30 20 2f 2a 20 4e  ndif..#if 0 /* N
0980: 4f 54 20 55 53 45 44 20 2a 2f 0a 2f 2a 0a 2a 2a  OT USED */./*.**
0990: 20 48 61 73 68 20 61 6e 64 20 63 6f 6d 70 61 72   Hash and compar
09a0: 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 20 77  ison functions w
09b0: 68 65 6e 20 74 68 65 20 6d 6f 64 65 20 69 73 20  hen the mode is 
09c0: 53 51 4c 49 54 45 5f 48 41 53 48 5f 50 4f 49 4e  SQLITE_HASH_POIN
09d0: 54 45 52 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e  TER.*/.static in
09e0: 74 20 70 74 72 48 61 73 68 28 63 6f 6e 73 74 20  t ptrHash(const 
09f0: 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20  void *pKey, int 
0a00: 6e 4b 65 79 29 7b 0a 20 20 75 70 74 72 20 78 20  nKey){.  uptr x 
0a10: 3d 20 41 64 64 72 28 70 4b 65 79 29 3b 0a 20 20  = Addr(pKey);.  
0a20: 72 65 74 75 72 6e 20 78 20 5e 20 28 78 3c 3c 38  return x ^ (x<<8
0a30: 29 20 5e 20 28 78 3e 3e 38 29 3b 0a 7d 0a 73 74  ) ^ (x>>8);.}.st
0a40: 61 74 69 63 20 69 6e 74 20 70 74 72 43 6f 6d 70  atic int ptrComp
0a50: 61 72 65 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a  are(const void *
0a60: 70 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c 20 63  pKey1, int n1, c
0a70: 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 32  onst void *pKey2
0a80: 2c 20 69 6e 74 20 6e 32 29 7b 0a 20 20 69 66 28  , int n2){.  if(
0a90: 20 70 4b 65 79 31 3d 3d 70 4b 65 79 32 20 29 20   pKey1==pKey2 ) 
0aa0: 72 65 74 75 72 6e 20 30 3b 0a 20 20 69 66 28 20  return 0;.  if( 
0ab0: 70 4b 65 79 31 3c 70 4b 65 79 32 20 29 20 72 65  pKey1<pKey2 ) re
0ac0: 74 75 72 6e 20 2d 31 3b 0a 20 20 72 65 74 75 72  turn -1;.  retur
0ad0: 6e 20 31 3b 0a 7d 0a 23 65 6e 64 69 66 0a 0a 2f  n 1;.}.#endif../
0ae0: 2a 0a 2a 2a 20 48 61 73 68 20 61 6e 64 20 63 6f  *.** Hash and co
0af0: 6d 70 61 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f  mparison functio
0b00: 6e 73 20 77 68 65 6e 20 74 68 65 20 6d 6f 64 65  ns when the mode
0b10: 20 69 73 20 53 51 4c 49 54 45 5f 48 41 53 48 5f   is SQLITE_HASH_
0b20: 53 54 52 49 4e 47 0a 2a 2f 0a 73 74 61 74 69 63  STRING.*/.static
0b30: 20 69 6e 74 20 73 74 72 48 61 73 68 28 63 6f 6e   int strHash(con
0b40: 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69  st void *pKey, i
0b50: 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 63 6f 6e 73  nt nKey){.  cons
0b60: 74 20 63 68 61 72 20 2a 7a 20 3d 20 28 63 6f 6e  t char *z = (con
0b70: 73 74 20 63 68 61 72 20 2a 29 70 4b 65 79 3b 0a  st char *)pKey;.
0b80: 20 20 69 6e 74 20 68 20 3d 20 30 3b 0a 20 20 69    int h = 0;.  i
0b90: 66 28 20 6e 4b 65 79 3c 3d 30 20 29 20 6e 4b 65  f( nKey<=0 ) nKe
0ba0: 79 20 3d 20 73 74 72 6c 65 6e 28 7a 29 3b 0a 20  y = strlen(z);. 
0bb0: 20 77 68 69 6c 65 28 20 6e 4b 65 79 20 3e 20 30   while( nKey > 0
0bc0: 20 20 29 7b 0a 20 20 20 20 68 20 3d 20 28 68 3c    ){.    h = (h<
0bd0: 3c 33 29 20 5e 20 68 20 5e 20 73 71 6c 69 74 65  <3) ^ h ^ sqlite
0be0: 33 55 70 70 65 72 54 6f 4c 6f 77 65 72 5b 28 75  3UpperToLower[(u
0bf0: 6e 73 69 67 6e 65 64 20 63 68 61 72 29 2a 7a 2b  nsigned char)*z+
0c00: 2b 5d 3b 0a 20 20 20 20 6e 4b 65 79 2d 2d 3b 0a  +];.    nKey--;.
0c10: 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 68 20 26    }.  return h &
0c20: 20 30 78 37 66 66 66 66 66 66 66 3b 0a 7d 0a 73   0x7fffffff;.}.s
0c30: 74 61 74 69 63 20 69 6e 74 20 73 74 72 43 6f 6d  tatic int strCom
0c40: 70 61 72 65 28 63 6f 6e 73 74 20 76 6f 69 64 20  pare(const void 
0c50: 2a 70 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c 20  *pKey1, int n1, 
0c60: 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79  const void *pKey
0c70: 32 2c 20 69 6e 74 20 6e 32 29 7b 0a 20 20 69 66  2, int n2){.  if
0c80: 28 20 6e 31 21 3d 6e 32 20 29 20 72 65 74 75 72  ( n1!=n2 ) retur
0c90: 6e 20 31 3b 0a 20 20 72 65 74 75 72 6e 20 73 71  n 1;.  return sq
0ca0: 6c 69 74 65 33 53 74 72 4e 49 43 6d 70 28 28 63  lite3StrNICmp((c
0cb0: 6f 6e 73 74 20 63 68 61 72 2a 29 70 4b 65 79 31  onst char*)pKey1
0cc0: 2c 28 63 6f 6e 73 74 20 63 68 61 72 2a 29 70 4b  ,(const char*)pK
0cd0: 65 79 32 2c 6e 31 29 3b 0a 7d 0a 0a 2f 2a 0a 2a  ey2,n1);.}../*.*
0ce0: 2a 20 48 61 73 68 20 61 6e 64 20 63 6f 6d 70 61  * Hash and compa
0cf0: 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 20  rison functions 
0d00: 77 68 65 6e 20 74 68 65 20 6d 6f 64 65 20 69 73  when the mode is
0d10: 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e   SQLITE_HASH_BIN
0d20: 41 52 59 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e  ARY.*/.static in
0d30: 74 20 62 69 6e 48 61 73 68 28 63 6f 6e 73 74 20  t binHash(const 
0d40: 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20  void *pKey, int 
0d50: 6e 4b 65 79 29 7b 0a 20 20 69 6e 74 20 68 20 3d  nKey){.  int h =
0d60: 20 30 3b 0a 20 20 63 6f 6e 73 74 20 63 68 61 72   0;.  const char
0d70: 20 2a 7a 20 3d 20 28 63 6f 6e 73 74 20 63 68 61   *z = (const cha
0d80: 72 20 2a 29 70 4b 65 79 3b 0a 20 20 77 68 69 6c  r *)pKey;.  whil
0d90: 65 28 20 6e 4b 65 79 2d 2d 20 3e 20 30 20 29 7b  e( nKey-- > 0 ){
0da0: 0a 20 20 20 20 68 20 3d 20 28 68 3c 3c 33 29 20  .    h = (h<<3) 
0db0: 5e 20 68 20 5e 20 2a 28 7a 2b 2b 29 3b 0a 20 20  ^ h ^ *(z++);.  
0dc0: 7d 0a 20 20 72 65 74 75 72 6e 20 68 20 26 20 30  }.  return h & 0
0dd0: 78 37 66 66 66 66 66 66 66 3b 0a 7d 0a 73 74 61  x7fffffff;.}.sta
0de0: 74 69 63 20 69 6e 74 20 62 69 6e 43 6f 6d 70 61  tic int binCompa
0df0: 72 65 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70  re(const void *p
0e00: 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c 20 63 6f  Key1, int n1, co
0e10: 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 32 2c  nst void *pKey2,
0e20: 20 69 6e 74 20 6e 32 29 7b 0a 20 20 69 66 28 20   int n2){.  if( 
0e30: 6e 31 21 3d 6e 32 20 29 20 72 65 74 75 72 6e 20  n1!=n2 ) return 
0e40: 31 3b 0a 20 20 72 65 74 75 72 6e 20 6d 65 6d 63  1;.  return memc
0e50: 6d 70 28 70 4b 65 79 31 2c 70 4b 65 79 32 2c 6e  mp(pKey1,pKey2,n
0e60: 31 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 74  1);.}../*.** Ret
0e70: 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f  urn a pointer to
0e80: 20 74 68 65 20 61 70 70 72 6f 70 72 69 61 74 65   the appropriate
0e90: 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 67   hash function g
0ea0: 69 76 65 6e 20 74 68 65 20 6b 65 79 20 63 6c 61  iven the key cla
0eb0: 73 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 43 20  ss..**.** The C 
0ec0: 73 79 6e 74 61 78 20 69 6e 20 74 68 69 73 20 66  syntax in this f
0ed0: 75 6e 63 74 69 6f 6e 20 64 65 66 69 6e 69 74 69  unction definiti
0ee0: 6f 6e 20 6d 61 79 20 62 65 20 75 6e 66 61 6d 69  on may be unfami
0ef0: 6c 61 72 20 74 6f 20 73 6f 6d 65 20 0a 2a 2a 20  lar to some .** 
0f00: 70 72 6f 67 72 61 6d 6d 65 72 73 2c 20 73 6f 20  programmers, so 
0f10: 77 65 20 70 72 6f 76 69 64 65 20 74 68 65 20 66  we provide the f
0f20: 6f 6c 6c 6f 77 69 6e 67 20 61 64 64 69 74 69 6f  ollowing additio
0f30: 6e 61 6c 20 65 78 70 6c 61 6e 61 74 69 6f 6e 3a  nal explanation:
0f40: 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6e 61 6d 65 20  .**.** The name 
0f50: 6f 66 20 74 68 65 20 66 75 6e 63 74 69 6f 6e 20  of the function 
0f60: 69 73 20 22 68 61 73 68 46 75 6e 63 74 69 6f 6e  is "hashFunction
0f70: 22 2e 20 20 54 68 65 20 66 75 6e 63 74 69 6f 6e  ".  The function
0f80: 20 74 61 6b 65 73 20 61 0a 2a 2a 20 73 69 6e 67   takes a.** sing
0f90: 6c 65 20 70 61 72 61 6d 65 74 65 72 20 22 6b 65  le parameter "ke
0fa0: 79 43 6c 61 73 73 22 2e 20 20 54 68 65 20 72 65  yClass".  The re
0fb0: 74 75 72 6e 20 76 61 6c 75 65 20 6f 66 20 68 61  turn value of ha
0fc0: 73 68 46 75 6e 63 74 69 6f 6e 28 29 0a 2a 2a 20  shFunction().** 
0fd0: 69 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20  is a pointer to 
0fe0: 61 6e 6f 74 68 65 72 20 66 75 6e 63 74 69 6f 6e  another function
0ff0: 2e 20 20 53 70 65 63 69 66 69 63 61 6c 6c 79 2c  .  Specifically,
1000: 20 74 68 65 20 72 65 74 75 72 6e 20 76 61 6c 75   the return valu
1010: 65 0a 2a 2a 20 6f 66 20 68 61 73 68 46 75 6e 63  e.** of hashFunc
1020: 74 69 6f 6e 28 29 20 69 73 20 61 20 70 6f 69 6e  tion() is a poin
1030: 74 65 72 20 74 6f 20 61 20 66 75 6e 63 74 69 6f  ter to a functio
1040: 6e 20 74 68 61 74 20 74 61 6b 65 73 20 74 77 6f  n that takes two
1050: 20 70 61 72 61 6d 65 74 65 72 73 0a 2a 2a 20 77   parameters.** w
1060: 69 74 68 20 74 79 70 65 73 20 22 63 6f 6e 73 74  ith types "const
1070: 20 76 6f 69 64 2a 22 20 61 6e 64 20 22 69 6e 74   void*" and "int
1080: 22 20 61 6e 64 20 72 65 74 75 72 6e 73 20 61 6e  " and returns an
1090: 20 22 69 6e 74 22 2e 0a 2a 2f 0a 73 74 61 74 69   "int"..*/.stati
10a0: 63 20 69 6e 74 20 28 2a 68 61 73 68 46 75 6e 63  c int (*hashFunc
10b0: 74 69 6f 6e 28 69 6e 74 20 6b 65 79 43 6c 61 73  tion(int keyClas
10c0: 73 29 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c  s))(const void*,
10d0: 69 6e 74 29 7b 0a 23 69 66 20 30 20 20 2f 2a 20  int){.#if 0  /* 
10e0: 48 41 53 48 5f 49 4e 54 20 61 6e 64 20 48 41 53  HASH_INT and HAS
10f0: 48 5f 50 4f 49 4e 54 45 52 20 61 72 65 20 6e 65  H_POINTER are ne
1100: 76 65 72 20 75 73 65 64 20 2a 2f 0a 20 20 73 77  ver used */.  sw
1110: 69 74 63 68 28 20 6b 65 79 43 6c 61 73 73 20 29  itch( keyClass )
1120: 7b 0a 20 20 20 20 63 61 73 65 20 53 51 4c 49 54  {.    case SQLIT
1130: 45 5f 48 41 53 48 5f 49 4e 54 3a 20 20 20 20 20  E_HASH_INT:     
1140: 72 65 74 75 72 6e 20 26 69 6e 74 48 61 73 68 3b  return &intHash;
1150: 0a 20 20 20 20 63 61 73 65 20 53 51 4c 49 54 45  .    case SQLITE
1160: 5f 48 41 53 48 5f 50 4f 49 4e 54 45 52 3a 20 72  _HASH_POINTER: r
1170: 65 74 75 72 6e 20 26 70 74 72 48 61 73 68 3b 0a  eturn &ptrHash;.
1180: 20 20 20 20 63 61 73 65 20 53 51 4c 49 54 45 5f      case SQLITE_
1190: 48 41 53 48 5f 53 54 52 49 4e 47 3a 20 20 72 65  HASH_STRING:  re
11a0: 74 75 72 6e 20 26 73 74 72 48 61 73 68 3b 0a 20  turn &strHash;. 
11b0: 20 20 20 63 61 73 65 20 53 51 4c 49 54 45 5f 48     case SQLITE_H
11c0: 41 53 48 5f 42 49 4e 41 52 59 3a 20 20 72 65 74  ASH_BINARY:  ret
11d0: 75 72 6e 20 26 62 69 6e 48 61 73 68 3b 3b 0a 20  urn &binHash;;. 
11e0: 20 20 20 64 65 66 61 75 6c 74 3a 20 62 72 65 61     default: brea
11f0: 6b 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20  k;.  }.  return 
1200: 30 3b 0a 23 65 6c 73 65 0a 20 20 69 66 28 20 6b  0;.#else.  if( k
1210: 65 79 43 6c 61 73 73 3d 3d 53 51 4c 49 54 45 5f  eyClass==SQLITE_
1220: 48 41 53 48 5f 53 54 52 49 4e 47 20 29 7b 0a 20  HASH_STRING ){. 
1230: 20 20 20 72 65 74 75 72 6e 20 26 73 74 72 48 61     return &strHa
1240: 73 68 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20  sh;.  }else{.   
1250: 20 61 73 73 65 72 74 28 20 6b 65 79 43 6c 61 73   assert( keyClas
1260: 73 3d 3d 53 51 4c 49 54 45 5f 48 41 53 48 5f 42  s==SQLITE_HASH_B
1270: 49 4e 41 52 59 20 29 3b 0a 20 20 20 20 72 65 74  INARY );.    ret
1280: 75 72 6e 20 26 62 69 6e 48 61 73 68 3b 0a 20 20  urn &binHash;.  
1290: 7d 0a 23 65 6e 64 69 66 0a 7d 0a 0a 2f 2a 0a 2a  }.#endif.}../*.*
12a0: 2a 20 52 65 74 75 72 6e 20 61 20 70 6f 69 6e 74  * Return a point
12b0: 65 72 20 74 6f 20 74 68 65 20 61 70 70 72 6f 70  er to the approp
12c0: 72 69 61 74 65 20 68 61 73 68 20 66 75 6e 63 74  riate hash funct
12d0: 69 6f 6e 20 67 69 76 65 6e 20 74 68 65 20 6b 65  ion given the ke
12e0: 79 20 63 6c 61 73 73 2e 0a 2a 2a 0a 2a 2a 20 46  y class..**.** F
12f0: 6f 72 20 68 65 6c 70 20 69 6e 20 69 6e 74 65 72  or help in inter
1300: 70 72 65 74 65 64 20 74 68 65 20 6f 62 73 63 75  preted the obscu
1310: 72 65 20 43 20 63 6f 64 65 20 69 6e 20 74 68 65  re C code in the
1320: 20 66 75 6e 63 74 69 6f 6e 20 64 65 66 69 6e 69   function defini
1330: 74 69 6f 6e 2c 0a 2a 2a 20 73 65 65 20 74 68 65  tion,.** see the
1340: 20 68 65 61 64 65 72 20 63 6f 6d 6d 65 6e 74 20   header comment 
1350: 6f 6e 20 74 68 65 20 70 72 65 76 69 6f 75 73 20  on the previous 
1360: 66 75 6e 63 74 69 6f 6e 2e 0a 2a 2f 0a 73 74 61  function..*/.sta
1370: 74 69 63 20 69 6e 74 20 28 2a 63 6f 6d 70 61 72  tic int (*compar
1380: 65 46 75 6e 63 74 69 6f 6e 28 69 6e 74 20 6b 65  eFunction(int ke
1390: 79 43 6c 61 73 73 29 29 28 63 6f 6e 73 74 20 76  yClass))(const v
13a0: 6f 69 64 2a 2c 69 6e 74 2c 63 6f 6e 73 74 20 76  oid*,int,const v
13b0: 6f 69 64 2a 2c 69 6e 74 29 7b 0a 23 69 66 20 30  oid*,int){.#if 0
13c0: 20 2f 2a 20 48 41 53 48 5f 49 4e 54 20 61 6e 64   /* HASH_INT and
13d0: 20 48 41 53 48 5f 50 4f 49 4e 54 45 52 20 61 72   HASH_POINTER ar
13e0: 65 20 6e 65 76 65 72 20 75 73 65 64 20 2a 2f 0a  e never used */.
13f0: 20 20 73 77 69 74 63 68 28 20 6b 65 79 43 6c 61    switch( keyCla
1400: 73 73 20 29 7b 0a 20 20 20 20 63 61 73 65 20 53  ss ){.    case S
1410: 51 4c 49 54 45 5f 48 41 53 48 5f 49 4e 54 3a 20  QLITE_HASH_INT: 
1420: 20 20 20 20 72 65 74 75 72 6e 20 26 69 6e 74 43      return &intC
1430: 6f 6d 70 61 72 65 3b 0a 20 20 20 20 63 61 73 65  ompare;.    case
1440: 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 50 4f 49   SQLITE_HASH_POI
1450: 4e 54 45 52 3a 20 72 65 74 75 72 6e 20 26 70 74  NTER: return &pt
1460: 72 43 6f 6d 70 61 72 65 3b 0a 20 20 20 20 63 61  rCompare;.    ca
1470: 73 65 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 53  se SQLITE_HASH_S
1480: 54 52 49 4e 47 3a 20 20 72 65 74 75 72 6e 20 26  TRING:  return &
1490: 73 74 72 43 6f 6d 70 61 72 65 3b 0a 20 20 20 20  strCompare;.    
14a0: 63 61 73 65 20 53 51 4c 49 54 45 5f 48 41 53 48  case SQLITE_HASH
14b0: 5f 42 49 4e 41 52 59 3a 20 20 72 65 74 75 72 6e  _BINARY:  return
14c0: 20 26 62 69 6e 43 6f 6d 70 61 72 65 3b 0a 20 20   &binCompare;.  
14d0: 20 20 64 65 66 61 75 6c 74 3a 20 62 72 65 61 6b    default: break
14e0: 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 30  ;.  }.  return 0
14f0: 3b 0a 23 65 6c 73 65 0a 20 20 69 66 28 20 6b 65  ;.#else.  if( ke
1500: 79 43 6c 61 73 73 3d 3d 53 51 4c 49 54 45 5f 48  yClass==SQLITE_H
1510: 41 53 48 5f 53 54 52 49 4e 47 20 29 7b 0a 20 20  ASH_STRING ){.  
1520: 20 20 72 65 74 75 72 6e 20 26 73 74 72 43 6f 6d    return &strCom
1530: 70 61 72 65 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20  pare;.  }else{. 
1540: 20 20 20 61 73 73 65 72 74 28 20 6b 65 79 43 6c     assert( keyCl
1550: 61 73 73 3d 3d 53 51 4c 49 54 45 5f 48 41 53 48  ass==SQLITE_HASH
1560: 5f 42 49 4e 41 52 59 20 29 3b 0a 20 20 20 20 72  _BINARY );.    r
1570: 65 74 75 72 6e 20 26 62 69 6e 43 6f 6d 70 61 72  eturn &binCompar
1580: 65 3b 0a 20 20 7d 0a 23 65 6e 64 69 66 0a 7d 0a  e;.  }.#endif.}.
1590: 0a 2f 2a 20 4c 69 6e 6b 20 61 6e 20 65 6c 65 6d  ./* Link an elem
15a0: 65 6e 74 20 69 6e 74 6f 20 74 68 65 20 68 61 73  ent into the has
15b0: 68 20 74 61 62 6c 65 0a 2a 2f 0a 73 74 61 74 69  h table.*/.stati
15c0: 63 20 76 6f 69 64 20 69 6e 73 65 72 74 45 6c 65  c void insertEle
15d0: 6d 65 6e 74 28 0a 20 20 48 61 73 68 20 2a 70 48  ment(.  Hash *pH
15e0: 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f  ,              /
15f0: 2a 20 54 68 65 20 63 6f 6d 70 6c 65 74 65 20 68  * The complete h
1600: 61 73 68 20 74 61 62 6c 65 20 2a 2f 0a 20 20 73  ash table */.  s
1610: 74 72 75 63 74 20 5f 68 74 20 2a 70 45 6e 74 72  truct _ht *pEntr
1620: 79 2c 20 20 20 20 2f 2a 20 54 68 65 20 65 6e 74  y,    /* The ent
1630: 72 79 20 69 6e 74 6f 20 77 68 69 63 68 20 70 4e  ry into which pN
1640: 65 77 20 69 73 20 69 6e 73 65 72 74 65 64 20 2a  ew is inserted *
1650: 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 70 4e  /.  HashElem *pN
1660: 65 77 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68  ew         /* Th
1670: 65 20 65 6c 65 6d 65 6e 74 20 74 6f 20 62 65 20  e element to be 
1680: 69 6e 73 65 72 74 65 64 20 2a 2f 0a 29 7b 0a 20  inserted */.){. 
1690: 20 48 61 73 68 45 6c 65 6d 20 2a 70 48 65 61 64   HashElem *pHead
16a0: 3b 20 20 20 20 20 20 20 2f 2a 20 46 69 72 73 74  ;       /* First
16b0: 20 65 6c 65 6d 65 6e 74 20 61 6c 72 65 61 64 79   element already
16c0: 20 69 6e 20 70 45 6e 74 72 79 20 2a 2f 0a 20 20   in pEntry */.  
16d0: 70 48 65 61 64 20 3d 20 70 45 6e 74 72 79 2d 3e  pHead = pEntry->
16e0: 63 68 61 69 6e 3b 0a 20 20 69 66 28 20 70 48 65  chain;.  if( pHe
16f0: 61 64 20 29 7b 0a 20 20 20 20 70 4e 65 77 2d 3e  ad ){.    pNew->
1700: 6e 65 78 74 20 3d 20 70 48 65 61 64 3b 0a 20 20  next = pHead;.  
1710: 20 20 70 4e 65 77 2d 3e 70 72 65 76 20 3d 20 70    pNew->prev = p
1720: 48 65 61 64 2d 3e 70 72 65 76 3b 0a 20 20 20 20  Head->prev;.    
1730: 69 66 28 20 70 48 65 61 64 2d 3e 70 72 65 76 20  if( pHead->prev 
1740: 29 7b 20 70 48 65 61 64 2d 3e 70 72 65 76 2d 3e  ){ pHead->prev->
1750: 6e 65 78 74 20 3d 20 70 4e 65 77 3b 20 7d 0a 20  next = pNew; }. 
1760: 20 20 20 65 6c 73 65 20 20 20 20 20 20 20 20 20     else         
1770: 20 20 20 20 7b 20 70 48 2d 3e 66 69 72 73 74 20      { pH->first 
1780: 3d 20 70 4e 65 77 3b 20 7d 0a 20 20 20 20 70 48  = pNew; }.    pH
1790: 65 61 64 2d 3e 70 72 65 76 20 3d 20 70 4e 65 77  ead->prev = pNew
17a0: 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 70  ;.  }else{.    p
17b0: 4e 65 77 2d 3e 6e 65 78 74 20 3d 20 70 48 2d 3e  New->next = pH->
17c0: 66 69 72 73 74 3b 0a 20 20 20 20 69 66 28 20 70  first;.    if( p
17d0: 48 2d 3e 66 69 72 73 74 20 29 7b 20 70 48 2d 3e  H->first ){ pH->
17e0: 66 69 72 73 74 2d 3e 70 72 65 76 20 3d 20 70 4e  first->prev = pN
17f0: 65 77 3b 20 7d 0a 20 20 20 20 70 4e 65 77 2d 3e  ew; }.    pNew->
1800: 70 72 65 76 20 3d 20 30 3b 0a 20 20 20 20 70 48  prev = 0;.    pH
1810: 2d 3e 66 69 72 73 74 20 3d 20 70 4e 65 77 3b 0a  ->first = pNew;.
1820: 20 20 7d 0a 20 20 70 45 6e 74 72 79 2d 3e 63 6f    }.  pEntry->co
1830: 75 6e 74 2b 2b 3b 0a 20 20 70 45 6e 74 72 79 2d  unt++;.  pEntry-
1840: 3e 63 68 61 69 6e 20 3d 20 70 4e 65 77 3b 0a 7d  >chain = pNew;.}
1850: 0a 0a 0a 2f 2a 20 52 65 73 69 7a 65 20 74 68 65  .../* Resize the
1860: 20 68 61 73 68 20 74 61 62 6c 65 20 73 6f 20 74   hash table so t
1870: 68 61 74 20 69 74 20 63 61 6e 74 61 69 6e 73 20  hat it cantains 
1880: 22 6e 65 77 5f 73 69 7a 65 22 20 62 75 63 6b 65  "new_size" bucke
1890: 74 73 2e 0a 2a 2a 20 22 6e 65 77 5f 73 69 7a 65  ts..** "new_size
18a0: 22 20 6d 75 73 74 20 62 65 20 61 20 70 6f 77 65  " must be a powe
18b0: 72 20 6f 66 20 32 2e 20 20 54 68 65 20 68 61 73  r of 2.  The has
18c0: 68 20 74 61 62 6c 65 20 6d 69 67 68 74 20 66 61  h table might fa
18d0: 69 6c 20 0a 2a 2a 20 74 6f 20 72 65 73 69 7a 65  il .** to resize
18e0: 20 69 66 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c   if sqlite3_mall
18f0: 6f 63 28 29 20 66 61 69 6c 73 2e 0a 2a 2f 0a 73  oc() fails..*/.s
1900: 74 61 74 69 63 20 76 6f 69 64 20 72 65 68 61 73  tatic void rehas
1910: 68 28 48 61 73 68 20 2a 70 48 2c 20 69 6e 74 20  h(Hash *pH, int 
1920: 6e 65 77 5f 73 69 7a 65 29 7b 0a 20 20 73 74 72  new_size){.  str
1930: 75 63 74 20 5f 68 74 20 2a 6e 65 77 5f 68 74 3b  uct _ht *new_ht;
1940: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54              /* T
1950: 68 65 20 6e 65 77 20 68 61 73 68 20 74 61 62 6c  he new hash tabl
1960: 65 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20  e */.  HashElem 
1970: 2a 65 6c 65 6d 2c 20 2a 6e 65 78 74 5f 65 6c 65  *elem, *next_ele
1980: 6d 3b 20 20 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f  m;    /* For loo
1990: 70 69 6e 67 20 6f 76 65 72 20 65 78 69 73 74 69  ping over existi
19a0: 6e 67 20 65 6c 65 6d 65 6e 74 73 20 2a 2f 0a 20  ng elements */. 
19b0: 20 69 6e 74 20 28 2a 78 48 61 73 68 29 28 63 6f   int (*xHash)(co
19c0: 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29 3b 20  nst void*,int); 
19d0: 2f 2a 20 54 68 65 20 68 61 73 68 20 66 75 6e 63  /* The hash func
19e0: 74 69 6f 6e 20 2a 2f 0a 0a 23 69 66 64 65 66 20  tion */..#ifdef 
19f0: 53 51 4c 49 54 45 5f 4d 41 4c 4c 4f 43 5f 53 4f  SQLITE_MALLOC_SO
1a00: 46 54 5f 4c 49 4d 49 54 0a 20 20 69 66 28 20 6e  FT_LIMIT.  if( n
1a10: 65 77 5f 73 69 7a 65 2a 73 69 7a 65 6f 66 28 73  ew_size*sizeof(s
1a20: 74 72 75 63 74 20 5f 68 74 29 3e 53 51 4c 49 54  truct _ht)>SQLIT
1a30: 45 5f 4d 41 4c 4c 4f 43 5f 53 4f 46 54 5f 4c 49  E_MALLOC_SOFT_LI
1a40: 4d 49 54 20 29 7b 0a 20 20 20 20 6e 65 77 5f 73  MIT ){.    new_s
1a50: 69 7a 65 20 3d 20 53 51 4c 49 54 45 5f 4d 41 4c  ize = SQLITE_MAL
1a60: 4c 4f 43 5f 53 4f 46 54 5f 4c 49 4d 49 54 2f 73  LOC_SOFT_LIMIT/s
1a70: 69 7a 65 6f 66 28 73 74 72 75 63 74 20 5f 68 74  izeof(struct _ht
1a80: 29 3b 0a 20 20 7d 0a 20 20 69 66 28 20 6e 65 77  );.  }.  if( new
1a90: 5f 73 69 7a 65 3d 3d 70 48 2d 3e 68 74 73 69 7a  _size==pH->htsiz
1aa0: 65 20 29 20 72 65 74 75 72 6e 3b 0a 23 65 6e 64  e ) return;.#end
1ab0: 69 66 0a 0a 20 20 2f 2a 20 54 68 65 72 65 20 69  if..  /* There i
1ac0: 73 20 61 20 63 61 6c 6c 20 74 6f 20 73 71 6c 69  s a call to sqli
1ad0: 74 65 33 5f 6d 61 6c 6c 6f 63 28 29 20 69 6e 73  te3_malloc() ins
1ae0: 69 64 65 20 72 65 68 61 73 68 28 29 2e 20 49 66  ide rehash(). If
1af0: 20 74 68 65 72 65 20 69 73 0a 20 20 2a 2a 20 61   there is.  ** a
1b00: 6c 72 65 61 64 79 20 61 6e 20 61 6c 6c 6f 63 61  lready an alloca
1b10: 74 69 6f 6e 20 61 74 20 70 48 2d 3e 68 74 2c 20  tion at pH->ht, 
1b20: 74 68 65 6e 20 69 66 20 74 68 69 73 20 6d 61 6c  then if this mal
1b30: 6c 6f 63 28 29 20 66 61 69 6c 73 20 69 74 0a 20  loc() fails it. 
1b40: 20 2a 2a 20 69 73 20 62 65 6e 69 67 6e 20 28 73   ** is benign (s
1b50: 69 6e 63 65 20 66 61 69 6c 69 6e 67 20 74 6f 20  ince failing to 
1b60: 72 65 73 69 7a 65 20 61 20 68 61 73 68 20 74 61  resize a hash ta
1b70: 62 6c 65 20 69 73 20 61 20 70 65 72 66 6f 72 6d  ble is a perform
1b80: 61 6e 63 65 0a 20 20 2a 2a 20 68 69 74 20 6f 6e  ance.  ** hit on
1b90: 6c 79 2c 20 6e 6f 74 20 61 20 66 61 74 61 6c 20  ly, not a fatal 
1ba0: 65 72 72 6f 72 29 2e 0a 20 20 2a 2f 0a 20 20 69  error)..  */.  i
1bb0: 66 28 20 70 48 2d 3e 68 74 73 69 7a 65 3e 30 20  f( pH->htsize>0 
1bc0: 29 20 73 71 6c 69 74 65 33 46 61 75 6c 74 42 65  ) sqlite3FaultBe
1bd0: 67 69 6e 42 65 6e 69 67 6e 28 53 51 4c 49 54 45  ginBenign(SQLITE
1be0: 5f 46 41 55 4c 54 49 4e 4a 45 43 54 4f 52 5f 4d  _FAULTINJECTOR_M
1bf0: 41 4c 4c 4f 43 29 3b 0a 20 20 6e 65 77 5f 68 74  ALLOC);.  new_ht
1c00: 20 3d 20 28 73 74 72 75 63 74 20 5f 68 74 20 2a   = (struct _ht *
1c10: 29 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 5a 65  )sqlite3MallocZe
1c20: 72 6f 28 20 6e 65 77 5f 73 69 7a 65 2a 73 69 7a  ro( new_size*siz
1c30: 65 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29 20  eof(struct _ht) 
1c40: 29 3b 0a 20 20 69 66 28 20 70 48 2d 3e 68 74 73  );.  if( pH->hts
1c50: 69 7a 65 3e 30 20 29 20 73 71 6c 69 74 65 33 46  ize>0 ) sqlite3F
1c60: 61 75 6c 74 45 6e 64 42 65 6e 69 67 6e 28 53 51  aultEndBenign(SQ
1c70: 4c 49 54 45 5f 46 41 55 4c 54 49 4e 4a 45 43 54  LITE_FAULTINJECT
1c80: 4f 52 5f 4d 41 4c 4c 4f 43 29 3b 0a 0a 20 20 69  OR_MALLOC);..  i
1c90: 66 28 20 6e 65 77 5f 68 74 3d 3d 30 20 29 20 72  f( new_ht==0 ) r
1ca0: 65 74 75 72 6e 3b 0a 20 20 73 71 6c 69 74 65 33  eturn;.  sqlite3
1cb0: 5f 66 72 65 65 28 70 48 2d 3e 68 74 29 3b 0a 20  _free(pH->ht);. 
1cc0: 20 70 48 2d 3e 68 74 20 3d 20 6e 65 77 5f 68 74   pH->ht = new_ht
1cd0: 3b 0a 20 20 70 48 2d 3e 68 74 73 69 7a 65 20 3d  ;.  pH->htsize =
1ce0: 20 6e 65 77 5f 73 69 7a 65 3b 0a 20 20 78 48 61   new_size;.  xHa
1cf0: 73 68 20 3d 20 68 61 73 68 46 75 6e 63 74 69 6f  sh = hashFunctio
1d00: 6e 28 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b  n(pH->keyClass);
1d10: 0a 20 20 66 6f 72 28 65 6c 65 6d 3d 70 48 2d 3e  .  for(elem=pH->
1d20: 66 69 72 73 74 2c 20 70 48 2d 3e 66 69 72 73 74  first, pH->first
1d30: 3d 30 3b 20 65 6c 65 6d 3b 20 65 6c 65 6d 20 3d  =0; elem; elem =
1d40: 20 6e 65 78 74 5f 65 6c 65 6d 29 7b 0a 20 20 20   next_elem){.   
1d50: 20 69 6e 74 20 68 20 3d 20 28 2a 78 48 61 73 68   int h = (*xHash
1d60: 29 28 65 6c 65 6d 2d 3e 70 4b 65 79 2c 20 65 6c  )(elem->pKey, el
1d70: 65 6d 2d 3e 6e 4b 65 79 29 20 26 20 28 6e 65 77  em->nKey) & (new
1d80: 5f 73 69 7a 65 2d 31 29 3b 0a 20 20 20 20 6e 65  _size-1);.    ne
1d90: 78 74 5f 65 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e  xt_elem = elem->
1da0: 6e 65 78 74 3b 0a 20 20 20 20 69 6e 73 65 72 74  next;.    insert
1db0: 45 6c 65 6d 65 6e 74 28 70 48 2c 20 26 6e 65 77  Element(pH, &new
1dc0: 5f 68 74 5b 68 5d 2c 20 65 6c 65 6d 29 3b 0a 20  _ht[h], elem);. 
1dd0: 20 7d 0a 7d 0a 0a 2f 2a 20 54 68 69 73 20 66 75   }.}../* This fu
1de0: 6e 63 74 69 6f 6e 20 28 66 6f 72 20 69 6e 74 65  nction (for inte
1df0: 72 6e 61 6c 20 75 73 65 20 6f 6e 6c 79 29 20 6c  rnal use only) l
1e00: 6f 63 61 74 65 73 20 61 6e 20 65 6c 65 6d 65 6e  ocates an elemen
1e10: 74 20 69 6e 20 61 6e 0a 2a 2a 20 68 61 73 68 20  t in an.** hash 
1e20: 74 61 62 6c 65 20 74 68 61 74 20 6d 61 74 63 68  table that match
1e30: 65 73 20 74 68 65 20 67 69 76 65 6e 20 6b 65 79  es the given key
1e40: 2e 20 20 54 68 65 20 68 61 73 68 20 66 6f 72 20  .  The hash for 
1e50: 74 68 69 73 20 6b 65 79 20 68 61 73 0a 2a 2a 20  this key has.** 
1e60: 61 6c 72 65 61 64 79 20 62 65 65 6e 20 63 6f 6d  already been com
1e70: 70 75 74 65 64 20 61 6e 64 20 69 73 20 70 61 73  puted and is pas
1e80: 73 65 64 20 61 73 20 74 68 65 20 34 74 68 20 70  sed as the 4th p
1e90: 61 72 61 6d 65 74 65 72 2e 0a 2a 2f 0a 73 74 61  arameter..*/.sta
1ea0: 74 69 63 20 48 61 73 68 45 6c 65 6d 20 2a 66 69  tic HashElem *fi
1eb0: 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61  ndElementGivenHa
1ec0: 73 68 28 0a 20 20 63 6f 6e 73 74 20 48 61 73 68  sh(.  const Hash
1ed0: 20 2a 70 48 2c 20 20 20 20 20 2f 2a 20 54 68 65   *pH,     /* The
1ee0: 20 70 48 20 74 6f 20 62 65 20 73 65 61 72 63 68   pH to be search
1ef0: 65 64 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 76 6f  ed */.  const vo
1f00: 69 64 20 2a 70 4b 65 79 2c 20 20 20 2f 2a 20 54  id *pKey,   /* T
1f10: 68 65 20 6b 65 79 20 77 65 20 61 72 65 20 73 65  he key we are se
1f20: 61 72 63 68 69 6e 67 20 66 6f 72 20 2a 2f 0a 20  arching for */. 
1f30: 20 69 6e 74 20 6e 4b 65 79 2c 0a 20 20 69 6e 74   int nKey,.  int
1f40: 20 68 20 20 20 20 20 20 20 20 20 20 20 20 20 20   h              
1f50: 20 2f 2a 20 54 68 65 20 68 61 73 68 20 66 6f 72   /* The hash for
1f60: 20 74 68 69 73 20 6b 65 79 2e 20 2a 2f 0a 29 7b   this key. */.){
1f70: 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65  .  HashElem *ele
1f80: 6d 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  m;              
1f90: 20 20 2f 2a 20 55 73 65 64 20 74 6f 20 6c 6f 6f    /* Used to loo
1fa0: 70 20 74 68 72 75 20 74 68 65 20 65 6c 65 6d 65  p thru the eleme
1fb0: 6e 74 20 6c 69 73 74 20 2a 2f 0a 20 20 69 6e 74  nt list */.  int
1fc0: 20 63 6f 75 6e 74 3b 20 20 20 20 20 20 20 20 20   count;         
1fd0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e              /* N
1fe0: 75 6d 62 65 72 20 6f 66 20 65 6c 65 6d 65 6e 74  umber of element
1ff0: 73 20 6c 65 66 74 20 74 6f 20 74 65 73 74 20 2a  s left to test *
2000: 2f 0a 20 20 69 6e 74 20 28 2a 78 43 6f 6d 70 61  /.  int (*xCompa
2010: 72 65 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c  re)(const void*,
2020: 69 6e 74 2c 63 6f 6e 73 74 20 76 6f 69 64 2a 2c  int,const void*,
2030: 69 6e 74 29 3b 20 20 2f 2a 20 63 6f 6d 70 61 72  int);  /* compar
2040: 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 20 2a 2f  ison function */
2050: 0a 0a 20 20 69 66 28 20 70 48 2d 3e 68 74 20 29  ..  if( pH->ht )
2060: 7b 0a 20 20 20 20 73 74 72 75 63 74 20 5f 68 74  {.    struct _ht
2070: 20 2a 70 45 6e 74 72 79 20 3d 20 26 70 48 2d 3e   *pEntry = &pH->
2080: 68 74 5b 68 5d 3b 0a 20 20 20 20 65 6c 65 6d 20  ht[h];.    elem 
2090: 3d 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3b  = pEntry->chain;
20a0: 0a 20 20 20 20 63 6f 75 6e 74 20 3d 20 70 45 6e  .    count = pEn
20b0: 74 72 79 2d 3e 63 6f 75 6e 74 3b 0a 20 20 20 20  try->count;.    
20c0: 78 43 6f 6d 70 61 72 65 20 3d 20 63 6f 6d 70 61  xCompare = compa
20d0: 72 65 46 75 6e 63 74 69 6f 6e 28 70 48 2d 3e 6b  reFunction(pH->k
20e0: 65 79 43 6c 61 73 73 29 3b 0a 20 20 20 20 77 68  eyClass);.    wh
20f0: 69 6c 65 28 20 63 6f 75 6e 74 2d 2d 20 26 26 20  ile( count-- && 
2100: 65 6c 65 6d 20 29 7b 0a 20 20 20 20 20 20 69 66  elem ){.      if
2110: 28 20 28 2a 78 43 6f 6d 70 61 72 65 29 28 65 6c  ( (*xCompare)(el
2120: 65 6d 2d 3e 70 4b 65 79 2c 65 6c 65 6d 2d 3e 6e  em->pKey,elem->n
2130: 4b 65 79 2c 70 4b 65 79 2c 6e 4b 65 79 29 3d 3d  Key,pKey,nKey)==
2140: 30 20 29 7b 20 0a 20 20 20 20 20 20 20 20 72 65  0 ){ .        re
2150: 74 75 72 6e 20 65 6c 65 6d 3b 0a 20 20 20 20 20  turn elem;.     
2160: 20 7d 0a 20 20 20 20 20 20 65 6c 65 6d 20 3d 20   }.      elem = 
2170: 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20 20  elem->next;.    
2180: 7d 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 30  }.  }.  return 0
2190: 3b 0a 7d 0a 0a 2f 2a 20 52 65 6d 6f 76 65 20 61  ;.}../* Remove a
21a0: 20 73 69 6e 67 6c 65 20 65 6e 74 72 79 20 66 72   single entry fr
21b0: 6f 6d 20 74 68 65 20 68 61 73 68 20 74 61 62 6c  om the hash tabl
21c0: 65 20 67 69 76 65 6e 20 61 20 70 6f 69 6e 74 65  e given a pointe
21d0: 72 20 74 6f 20 74 68 61 74 0a 2a 2a 20 65 6c 65  r to that.** ele
21e0: 6d 65 6e 74 20 61 6e 64 20 61 20 68 61 73 68 20  ment and a hash 
21f0: 6f 6e 20 74 68 65 20 65 6c 65 6d 65 6e 74 27 73  on the element's
2200: 20 6b 65 79 2e 0a 2a 2f 0a 73 74 61 74 69 63 20   key..*/.static 
2210: 76 6f 69 64 20 72 65 6d 6f 76 65 45 6c 65 6d 65  void removeEleme
2220: 6e 74 47 69 76 65 6e 48 61 73 68 28 0a 20 20 48  ntGivenHash(.  H
2230: 61 73 68 20 2a 70 48 2c 20 20 20 20 20 20 20 20  ash *pH,        
2240: 20 2f 2a 20 54 68 65 20 70 48 20 63 6f 6e 74 61   /* The pH conta
2250: 69 6e 69 6e 67 20 22 65 6c 65 6d 22 20 2a 2f 0a  ining "elem" */.
2260: 20 20 48 61 73 68 45 6c 65 6d 2a 20 65 6c 65 6d    HashElem* elem
2270: 2c 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65  ,   /* The eleme
2280: 6e 74 20 74 6f 20 62 65 20 72 65 6d 6f 76 65 64  nt to be removed
2290: 20 66 72 6f 6d 20 74 68 65 20 70 48 20 2a 2f 0a   from the pH */.
22a0: 20 20 69 6e 74 20 68 20 20 20 20 20 20 20 20 20    int h         
22b0: 20 20 20 20 2f 2a 20 48 61 73 68 20 76 61 6c 75      /* Hash valu
22c0: 65 20 66 6f 72 20 74 68 65 20 65 6c 65 6d 65 6e  e for the elemen
22d0: 74 20 2a 2f 0a 29 7b 0a 20 20 73 74 72 75 63 74  t */.){.  struct
22e0: 20 5f 68 74 20 2a 70 45 6e 74 72 79 3b 0a 20 20   _ht *pEntry;.  
22f0: 69 66 28 20 65 6c 65 6d 2d 3e 70 72 65 76 20 29  if( elem->prev )
2300: 7b 0a 20 20 20 20 65 6c 65 6d 2d 3e 70 72 65 76  {.    elem->prev
2310: 2d 3e 6e 65 78 74 20 3d 20 65 6c 65 6d 2d 3e 6e  ->next = elem->n
2320: 65 78 74 3b 20 0a 20 20 7d 65 6c 73 65 7b 0a 20  ext; .  }else{. 
2330: 20 20 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 65     pH->first = e
2340: 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20  lem->next;.  }. 
2350: 20 69 66 28 20 65 6c 65 6d 2d 3e 6e 65 78 74 20   if( elem->next 
2360: 29 7b 0a 20 20 20 20 65 6c 65 6d 2d 3e 6e 65 78  ){.    elem->nex
2370: 74 2d 3e 70 72 65 76 20 3d 20 65 6c 65 6d 2d 3e  t->prev = elem->
2380: 70 72 65 76 3b 0a 20 20 7d 0a 20 20 70 45 6e 74  prev;.  }.  pEnt
2390: 72 79 20 3d 20 26 70 48 2d 3e 68 74 5b 68 5d 3b  ry = &pH->ht[h];
23a0: 0a 20 20 69 66 28 20 70 45 6e 74 72 79 2d 3e 63  .  if( pEntry->c
23b0: 68 61 69 6e 3d 3d 65 6c 65 6d 20 29 7b 0a 20 20  hain==elem ){.  
23c0: 20 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 20    pEntry->chain 
23d0: 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20  = elem->next;.  
23e0: 7d 0a 20 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e  }.  pEntry->coun
23f0: 74 2d 2d 3b 0a 20 20 69 66 28 20 70 45 6e 74 72  t--;.  if( pEntr
2400: 79 2d 3e 63 6f 75 6e 74 3c 3d 30 20 29 7b 0a 20  y->count<=0 ){. 
2410: 20 20 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e     pEntry->chain
2420: 20 3d 20 30 3b 0a 20 20 7d 0a 20 20 69 66 28 20   = 0;.  }.  if( 
2430: 70 48 2d 3e 63 6f 70 79 4b 65 79 20 29 7b 0a 20  pH->copyKey ){. 
2440: 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28     sqlite3_free(
2450: 65 6c 65 6d 2d 3e 70 4b 65 79 29 3b 0a 20 20 7d  elem->pKey);.  }
2460: 0a 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28  .  sqlite3_free(
2470: 20 65 6c 65 6d 20 29 3b 0a 20 20 70 48 2d 3e 63   elem );.  pH->c
2480: 6f 75 6e 74 2d 2d 3b 0a 20 20 69 66 28 20 70 48  ount--;.  if( pH
2490: 2d 3e 63 6f 75 6e 74 3c 3d 30 20 29 7b 0a 20 20  ->count<=0 ){.  
24a0: 20 20 61 73 73 65 72 74 28 20 70 48 2d 3e 66 69    assert( pH->fi
24b0: 72 73 74 3d 3d 30 20 29 3b 0a 20 20 20 20 61 73  rst==0 );.    as
24c0: 73 65 72 74 28 20 70 48 2d 3e 63 6f 75 6e 74 3d  sert( pH->count=
24d0: 3d 30 20 29 3b 0a 20 20 20 20 73 71 6c 69 74 65  =0 );.    sqlite
24e0: 33 48 61 73 68 43 6c 65 61 72 28 70 48 29 3b 0a  3HashClear(pH);.
24f0: 20 20 7d 0a 7d 0a 0a 2f 2a 20 41 74 74 65 6d 70    }.}../* Attemp
2500: 74 20 74 6f 20 6c 6f 63 61 74 65 20 61 6e 20 65  t to locate an e
2510: 6c 65 6d 65 6e 74 20 6f 66 20 74 68 65 20 68 61  lement of the ha
2520: 73 68 20 74 61 62 6c 65 20 70 48 20 77 69 74 68  sh table pH with
2530: 20 61 20 6b 65 79 0a 2a 2a 20 74 68 61 74 20 6d   a key.** that m
2540: 61 74 63 68 65 73 20 70 4b 65 79 2c 6e 4b 65 79  atches pKey,nKey
2550: 2e 20 20 52 65 74 75 72 6e 20 61 20 70 6f 69 6e  .  Return a poin
2560: 74 65 72 20 74 6f 20 74 68 65 20 63 6f 72 72 65  ter to the corre
2570: 73 70 6f 6e 64 69 6e 67 20 0a 2a 2a 20 48 61 73  sponding .** Has
2580: 68 45 6c 65 6d 20 73 74 72 75 63 74 75 72 65 20  hElem structure 
2590: 66 6f 72 20 74 68 69 73 20 65 6c 65 6d 65 6e 74  for this element
25a0: 20 69 66 20 69 74 20 69 73 20 66 6f 75 6e 64 2c   if it is found,
25b0: 20 6f 72 20 4e 55 4c 4c 0a 2a 2a 20 6f 74 68 65   or NULL.** othe
25c0: 72 77 69 73 65 2e 0a 2a 2f 0a 48 61 73 68 45 6c  rwise..*/.HashEl
25d0: 65 6d 20 2a 73 71 6c 69 74 65 33 48 61 73 68 46  em *sqlite3HashF
25e0: 69 6e 64 45 6c 65 6d 28 63 6f 6e 73 74 20 48 61  indElem(const Ha
25f0: 73 68 20 2a 70 48 2c 20 63 6f 6e 73 74 20 76 6f  sh *pH, const vo
2600: 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b  id *pKey, int nK
2610: 65 79 29 7b 0a 20 20 69 6e 74 20 68 3b 20 20 20  ey){.  int h;   
2620: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41 20 68            /* A h
2630: 61 73 68 20 6f 6e 20 6b 65 79 20 2a 2f 0a 20 20  ash on key */.  
2640: 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20  HashElem *elem; 
2650: 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e     /* The elemen
2660: 74 20 74 68 61 74 20 6d 61 74 63 68 65 73 20 6b  t that matches k
2670: 65 79 20 2a 2f 0a 20 20 69 6e 74 20 28 2a 78 48  ey */.  int (*xH
2680: 61 73 68 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a  ash)(const void*
2690: 2c 69 6e 74 29 3b 20 20 2f 2a 20 54 68 65 20 68  ,int);  /* The h
26a0: 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a  ash function */.
26b0: 0a 20 20 69 66 28 20 70 48 3d 3d 30 20 7c 7c 20  .  if( pH==0 || 
26c0: 70 48 2d 3e 68 74 3d 3d 30 20 29 20 72 65 74 75  pH->ht==0 ) retu
26d0: 72 6e 20 30 3b 0a 20 20 78 48 61 73 68 20 3d 20  rn 0;.  xHash = 
26e0: 68 61 73 68 46 75 6e 63 74 69 6f 6e 28 70 48 2d  hashFunction(pH-
26f0: 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20 61 73  >keyClass);.  as
2700: 73 65 72 74 28 20 78 48 61 73 68 21 3d 30 20 29  sert( xHash!=0 )
2710: 3b 0a 20 20 68 20 3d 20 28 2a 78 48 61 73 68 29  ;.  h = (*xHash)
2720: 28 70 4b 65 79 2c 6e 4b 65 79 29 3b 0a 20 20 65  (pKey,nKey);.  e
2730: 6c 65 6d 20 3d 20 66 69 6e 64 45 6c 65 6d 65 6e  lem = findElemen
2740: 74 47 69 76 65 6e 48 61 73 68 28 70 48 2c 70 4b  tGivenHash(pH,pK
2750: 65 79 2c 6e 4b 65 79 2c 20 68 20 25 20 70 48 2d  ey,nKey, h % pH-
2760: 3e 68 74 73 69 7a 65 29 3b 0a 20 20 72 65 74 75  >htsize);.  retu
2770: 72 6e 20 65 6c 65 6d 3b 0a 7d 0a 0a 2f 2a 20 41  rn elem;.}../* A
2780: 74 74 65 6d 70 74 20 74 6f 20 6c 6f 63 61 74 65  ttempt to locate
2790: 20 61 6e 20 65 6c 65 6d 65 6e 74 20 6f 66 20 74   an element of t
27a0: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 70 48  he hash table pH
27b0: 20 77 69 74 68 20 61 20 6b 65 79 0a 2a 2a 20 74   with a key.** t
27c0: 68 61 74 20 6d 61 74 63 68 65 73 20 70 4b 65 79  hat matches pKey
27d0: 2c 6e 4b 65 79 2e 20 20 52 65 74 75 72 6e 20 74  ,nKey.  Return t
27e0: 68 65 20 64 61 74 61 20 66 6f 72 20 74 68 69 73  he data for this
27f0: 20 65 6c 65 6d 65 6e 74 20 69 66 20 69 74 20 69   element if it i
2800: 73 0a 2a 2a 20 66 6f 75 6e 64 2c 20 6f 72 20 4e  s.** found, or N
2810: 55 4c 4c 20 69 66 20 74 68 65 72 65 20 69 73 20  ULL if there is 
2820: 6e 6f 20 6d 61 74 63 68 2e 0a 2a 2f 0a 76 6f 69  no match..*/.voi
2830: 64 20 2a 73 71 6c 69 74 65 33 48 61 73 68 46 69  d *sqlite3HashFi
2840: 6e 64 28 63 6f 6e 73 74 20 48 61 73 68 20 2a 70  nd(const Hash *p
2850: 48 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70  H, const void *p
2860: 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a  Key, int nKey){.
2870: 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d    HashElem *elem
2880: 3b 20 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d  ;    /* The elem
2890: 65 6e 74 20 74 68 61 74 20 6d 61 74 63 68 65 73  ent that matches
28a0: 20 6b 65 79 20 2a 2f 0a 20 20 65 6c 65 6d 20 3d   key */.  elem =
28b0: 20 73 71 6c 69 74 65 33 48 61 73 68 46 69 6e 64   sqlite3HashFind
28c0: 45 6c 65 6d 28 70 48 2c 20 70 4b 65 79 2c 20 6e  Elem(pH, pKey, n
28d0: 4b 65 79 29 3b 0a 20 20 72 65 74 75 72 6e 20 65  Key);.  return e
28e0: 6c 65 6d 20 3f 20 65 6c 65 6d 2d 3e 64 61 74 61  lem ? elem->data
28f0: 20 3a 20 30 3b 0a 7d 0a 0a 2f 2a 20 49 6e 73 65   : 0;.}../* Inse
2900: 72 74 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69 6e  rt an element in
2910: 74 6f 20 74 68 65 20 68 61 73 68 20 74 61 62 6c  to the hash tabl
2920: 65 20 70 48 2e 20 20 54 68 65 20 6b 65 79 20 69  e pH.  The key i
2930: 73 20 70 4b 65 79 2c 6e 4b 65 79 0a 2a 2a 20 61  s pKey,nKey.** a
2940: 6e 64 20 74 68 65 20 64 61 74 61 20 69 73 20 22  nd the data is "
2950: 64 61 74 61 22 2e 0a 2a 2a 0a 2a 2a 20 49 66 20  data"..**.** If 
2960: 6e 6f 20 65 6c 65 6d 65 6e 74 20 65 78 69 73 74  no element exist
2970: 73 20 77 69 74 68 20 61 20 6d 61 74 63 68 69 6e  s with a matchin
2980: 67 20 6b 65 79 2c 20 74 68 65 6e 20 61 20 6e 65  g key, then a ne
2990: 77 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 69 73 20  w.** element is 
29a0: 63 72 65 61 74 65 64 2e 20 20 41 20 63 6f 70 79  created.  A copy
29b0: 20 6f 66 20 74 68 65 20 6b 65 79 20 69 73 20 6d   of the key is m
29c0: 61 64 65 20 69 66 20 74 68 65 20 63 6f 70 79 4b  ade if the copyK
29d0: 65 79 0a 2a 2a 20 66 6c 61 67 20 69 73 20 73 65  ey.** flag is se
29e0: 74 2e 20 20 4e 55 4c 4c 20 69 73 20 72 65 74 75  t.  NULL is retu
29f0: 72 6e 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 61  rned..**.** If a
2a00: 6e 6f 74 68 65 72 20 65 6c 65 6d 65 6e 74 20 61  nother element a
2a10: 6c 72 65 61 64 79 20 65 78 69 73 74 73 20 77 69  lready exists wi
2a20: 74 68 20 74 68 65 20 73 61 6d 65 20 6b 65 79 2c  th the same key,
2a30: 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20 6e 65 77   then the.** new
2a40: 20 64 61 74 61 20 72 65 70 6c 61 63 65 73 20 74   data replaces t
2a50: 68 65 20 6f 6c 64 20 64 61 74 61 20 61 6e 64 20  he old data and 
2a60: 74 68 65 20 6f 6c 64 20 64 61 74 61 20 69 73 20  the old data is 
2a70: 72 65 74 75 72 6e 65 64 2e 0a 2a 2a 20 54 68 65  returned..** The
2a80: 20 6b 65 79 20 69 73 20 6e 6f 74 20 63 6f 70 69   key is not copi
2a90: 65 64 20 69 6e 20 74 68 69 73 20 69 6e 73 74 61  ed in this insta
2aa0: 6e 63 65 2e 20 20 49 66 20 61 20 6d 61 6c 6c 6f  nce.  If a mallo
2ab0: 63 20 66 61 69 6c 73 2c 20 74 68 65 6e 0a 2a 2a  c fails, then.**
2ac0: 20 74 68 65 20 6e 65 77 20 64 61 74 61 20 69 73   the new data is
2ad0: 20 72 65 74 75 72 6e 65 64 20 61 6e 64 20 74 68   returned and th
2ae0: 65 20 68 61 73 68 20 74 61 62 6c 65 20 69 73 20  e hash table is 
2af0: 75 6e 63 68 61 6e 67 65 64 2e 0a 2a 2a 0a 2a 2a  unchanged..**.**
2b00: 20 49 66 20 74 68 65 20 22 64 61 74 61 22 20 70   If the "data" p
2b10: 61 72 61 6d 65 74 65 72 20 74 6f 20 74 68 69 73  arameter to this
2b20: 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 4e 55 4c   function is NUL
2b30: 4c 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20 65  L, then the.** e
2b40: 6c 65 6d 65 6e 74 20 63 6f 72 72 65 73 70 6f 6e  lement correspon
2b50: 64 69 6e 67 20 74 6f 20 22 6b 65 79 22 20 69 73  ding to "key" is
2b60: 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74 68   removed from th
2b70: 65 20 68 61 73 68 20 74 61 62 6c 65 2e 0a 2a 2f  e hash table..*/
2b80: 0a 76 6f 69 64 20 2a 73 71 6c 69 74 65 33 48 61  .void *sqlite3Ha
2b90: 73 68 49 6e 73 65 72 74 28 48 61 73 68 20 2a 70  shInsert(Hash *p
2ba0: 48 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70  H, const void *p
2bb0: 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 2c 20 76  Key, int nKey, v
2bc0: 6f 69 64 20 2a 64 61 74 61 29 7b 0a 20 20 69 6e  oid *data){.  in
2bd0: 74 20 68 72 61 77 3b 20 20 20 20 20 20 20 20 20  t hraw;         
2be0: 20 20 20 20 2f 2a 20 52 61 77 20 68 61 73 68 20      /* Raw hash 
2bf0: 76 61 6c 75 65 20 6f 66 20 74 68 65 20 6b 65 79  value of the key
2c00: 20 2a 2f 0a 20 20 69 6e 74 20 68 3b 20 20 20 20   */.  int h;    
2c10: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 74              /* t
2c20: 68 65 20 68 61 73 68 20 6f 66 20 74 68 65 20 6b  he hash of the k
2c30: 65 79 20 6d 6f 64 75 6c 6f 20 68 61 73 68 20 74  ey modulo hash t
2c40: 61 62 6c 65 20 73 69 7a 65 20 2a 2f 0a 20 20 48  able size */.  H
2c50: 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20  ashElem *elem;  
2c60: 20 20 20 20 20 2f 2a 20 55 73 65 64 20 74 6f 20       /* Used to 
2c70: 6c 6f 6f 70 20 74 68 72 75 20 74 68 65 20 65 6c  loop thru the el
2c80: 65 6d 65 6e 74 20 6c 69 73 74 20 2a 2f 0a 20 20  ement list */.  
2c90: 48 61 73 68 45 6c 65 6d 20 2a 6e 65 77 5f 65 6c  HashElem *new_el
2ca0: 65 6d 3b 20 20 20 2f 2a 20 4e 65 77 20 65 6c 65  em;   /* New ele
2cb0: 6d 65 6e 74 20 61 64 64 65 64 20 74 6f 20 74 68  ment added to th
2cc0: 65 20 70 48 20 2a 2f 0a 20 20 69 6e 74 20 28 2a  e pH */.  int (*
2cd0: 78 48 61 73 68 29 28 63 6f 6e 73 74 20 76 6f 69  xHash)(const voi
2ce0: 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a 20 54 68 65  d*,int);  /* The
2cf0: 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 2a   hash function *
2d00: 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 70 48 21  /..  assert( pH!
2d10: 3d 30 20 29 3b 0a 20 20 78 48 61 73 68 20 3d 20  =0 );.  xHash = 
2d20: 68 61 73 68 46 75 6e 63 74 69 6f 6e 28 70 48 2d  hashFunction(pH-
2d30: 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20 61 73  >keyClass);.  as
2d40: 73 65 72 74 28 20 78 48 61 73 68 21 3d 30 20 29  sert( xHash!=0 )
2d50: 3b 0a 20 20 68 72 61 77 20 3d 20 28 2a 78 48 61  ;.  hraw = (*xHa
2d60: 73 68 29 28 70 4b 65 79 2c 20 6e 4b 65 79 29 3b  sh)(pKey, nKey);
2d70: 0a 20 20 69 66 28 20 70 48 2d 3e 68 74 73 69 7a  .  if( pH->htsiz
2d80: 65 20 29 7b 0a 20 20 20 20 68 20 3d 20 68 72 61  e ){.    h = hra
2d90: 77 20 25 20 70 48 2d 3e 68 74 73 69 7a 65 3b 0a  w % pH->htsize;.
2da0: 20 20 20 20 65 6c 65 6d 20 3d 20 66 69 6e 64 45      elem = findE
2db0: 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28  lementGivenHash(
2dc0: 70 48 2c 70 4b 65 79 2c 6e 4b 65 79 2c 68 29 3b  pH,pKey,nKey,h);
2dd0: 0a 20 20 20 20 69 66 28 20 65 6c 65 6d 20 29 7b  .    if( elem ){
2de0: 0a 20 20 20 20 20 20 76 6f 69 64 20 2a 6f 6c 64  .      void *old
2df0: 5f 64 61 74 61 20 3d 20 65 6c 65 6d 2d 3e 64 61  _data = elem->da
2e00: 74 61 3b 0a 20 20 20 20 20 20 69 66 28 20 64 61  ta;.      if( da
2e10: 74 61 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 20  ta==0 ){.       
2e20: 20 72 65 6d 6f 76 65 45 6c 65 6d 65 6e 74 47 69   removeElementGi
2e30: 76 65 6e 48 61 73 68 28 70 48 2c 65 6c 65 6d 2c  venHash(pH,elem,
2e40: 68 29 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b  h);.      }else{
2e50: 0a 20 20 20 20 20 20 20 20 65 6c 65 6d 2d 3e 64  .        elem->d
2e60: 61 74 61 20 3d 20 64 61 74 61 3b 0a 20 20 20 20  ata = data;.    
2e70: 20 20 20 20 69 66 28 20 21 70 48 2d 3e 63 6f 70      if( !pH->cop
2e80: 79 4b 65 79 20 29 7b 0a 20 20 20 20 20 20 20 20  yKey ){.        
2e90: 20 20 65 6c 65 6d 2d 3e 70 4b 65 79 20 3d 20 28    elem->pKey = (
2ea0: 76 6f 69 64 20 2a 29 70 4b 65 79 3b 0a 20 20 20  void *)pKey;.   
2eb0: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 61       }.        a
2ec0: 73 73 65 72 74 28 6e 4b 65 79 3d 3d 65 6c 65 6d  ssert(nKey==elem
2ed0: 2d 3e 6e 4b 65 79 29 3b 0a 20 20 20 20 20 20 7d  ->nKey);.      }
2ee0: 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 6f 6c  .      return ol
2ef0: 64 5f 64 61 74 61 3b 0a 20 20 20 20 7d 0a 20 20  d_data;.    }.  
2f00: 7d 0a 20 20 69 66 28 20 64 61 74 61 3d 3d 30 20  }.  if( data==0 
2f10: 29 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 6e 65  ) return 0;.  ne
2f20: 77 5f 65 6c 65 6d 20 3d 20 28 48 61 73 68 45 6c  w_elem = (HashEl
2f30: 65 6d 2a 29 73 71 6c 69 74 65 33 4d 61 6c 6c 6f  em*)sqlite3Mallo
2f40: 63 28 20 73 69 7a 65 6f 66 28 48 61 73 68 45 6c  c( sizeof(HashEl
2f50: 65 6d 29 20 29 3b 0a 20 20 69 66 28 20 6e 65 77  em) );.  if( new
2f60: 5f 65 6c 65 6d 3d 3d 30 20 29 20 72 65 74 75 72  _elem==0 ) retur
2f70: 6e 20 64 61 74 61 3b 0a 20 20 69 66 28 20 70 48  n data;.  if( pH
2f80: 2d 3e 63 6f 70 79 4b 65 79 20 26 26 20 70 4b 65  ->copyKey && pKe
2f90: 79 21 3d 30 20 29 7b 0a 20 20 20 20 6e 65 77 5f  y!=0 ){.    new_
2fa0: 65 6c 65 6d 2d 3e 70 4b 65 79 20 3d 20 73 71 6c  elem->pKey = sql
2fb0: 69 74 65 33 4d 61 6c 6c 6f 63 28 20 6e 4b 65 79  ite3Malloc( nKey
2fc0: 20 29 3b 0a 20 20 20 20 69 66 28 20 6e 65 77 5f   );.    if( new_
2fd0: 65 6c 65 6d 2d 3e 70 4b 65 79 3d 3d 30 20 29 7b  elem->pKey==0 ){
2fe0: 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33 5f 66  .      sqlite3_f
2ff0: 72 65 65 28 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20  ree(new_elem);. 
3000: 20 20 20 20 20 72 65 74 75 72 6e 20 64 61 74 61       return data
3010: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 6d 65 6d 63  ;.    }.    memc
3020: 70 79 28 28 76 6f 69 64 2a 29 6e 65 77 5f 65 6c  py((void*)new_el
3030: 65 6d 2d 3e 70 4b 65 79 2c 20 70 4b 65 79 2c 20  em->pKey, pKey, 
3040: 6e 4b 65 79 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a  nKey);.  }else{.
3050: 20 20 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b      new_elem->pK
3060: 65 79 20 3d 20 28 76 6f 69 64 2a 29 70 4b 65 79  ey = (void*)pKey
3070: 3b 0a 20 20 7d 0a 20 20 6e 65 77 5f 65 6c 65 6d  ;.  }.  new_elem
3080: 2d 3e 6e 4b 65 79 20 3d 20 6e 4b 65 79 3b 0a 20  ->nKey = nKey;. 
3090: 20 70 48 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20 20   pH->count++;.  
30a0: 69 66 28 20 70 48 2d 3e 68 74 73 69 7a 65 3d 3d  if( pH->htsize==
30b0: 30 20 29 7b 0a 20 20 20 20 72 65 68 61 73 68 28  0 ){.    rehash(
30c0: 70 48 2c 20 31 32 38 2f 73 69 7a 65 6f 66 28 70  pH, 128/sizeof(p
30d0: 48 2d 3e 68 74 5b 30 5d 29 29 3b 0a 20 20 20 20  H->ht[0]));.    
30e0: 69 66 28 20 70 48 2d 3e 68 74 73 69 7a 65 3d 3d  if( pH->htsize==
30f0: 30 20 29 7b 0a 20 20 20 20 20 20 70 48 2d 3e 63  0 ){.      pH->c
3100: 6f 75 6e 74 20 3d 20 30 3b 0a 20 20 20 20 20 20  ount = 0;.      
3110: 69 66 28 20 70 48 2d 3e 63 6f 70 79 4b 65 79 20  if( pH->copyKey 
3120: 29 7b 0a 20 20 20 20 20 20 20 20 73 71 6c 69 74  ){.        sqlit
3130: 65 33 5f 66 72 65 65 28 6e 65 77 5f 65 6c 65 6d  e3_free(new_elem
3140: 2d 3e 70 4b 65 79 29 3b 0a 20 20 20 20 20 20 7d  ->pKey);.      }
3150: 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33 5f 66  .      sqlite3_f
3160: 72 65 65 28 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20  ree(new_elem);. 
3170: 20 20 20 20 20 72 65 74 75 72 6e 20 64 61 74 61       return data
3180: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 69 66  ;.    }.  }.  if
3190: 28 20 70 48 2d 3e 63 6f 75 6e 74 20 3e 20 70 48  ( pH->count > pH
31a0: 2d 3e 68 74 73 69 7a 65 20 29 7b 0a 20 20 20 20  ->htsize ){.    
31b0: 72 65 68 61 73 68 28 70 48 2c 70 48 2d 3e 68 74  rehash(pH,pH->ht
31c0: 73 69 7a 65 2a 32 29 3b 0a 20 20 7d 0a 20 20 61  size*2);.  }.  a
31d0: 73 73 65 72 74 28 20 70 48 2d 3e 68 74 73 69 7a  ssert( pH->htsiz
31e0: 65 3e 30 20 29 3b 0a 20 20 68 20 3d 20 68 72 61  e>0 );.  h = hra
31f0: 77 20 25 20 70 48 2d 3e 68 74 73 69 7a 65 3b 0a  w % pH->htsize;.
3200: 20 20 69 6e 73 65 72 74 45 6c 65 6d 65 6e 74 28    insertElement(
3210: 70 48 2c 20 26 70 48 2d 3e 68 74 5b 68 5d 2c 20  pH, &pH->ht[h], 
3220: 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20 20 6e 65 77  new_elem);.  new
3230: 5f 65 6c 65 6d 2d 3e 64 61 74 61 20 3d 20 64 61  _elem->data = da
3240: 74 61 3b 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a  ta;.  return 0;.
3250: 7d 0a                                            }.