/ Hex Artifact Content
Login

Artifact 8f7c740ef2eaaa8decfa8751f2be30680b123e46:


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 36 20 32 30 30 32 2f 30 31 2f 31  ,v 1.6 2002/01/1
01e0: 34 20 30 39 3a 32 38 3a 32 30 20 64 72 68 20 45  4 09:28:20 drh E
01f0: 78 70 20 24 0a 2a 2f 0a 23 69 6e 63 6c 75 64 65  xp $.*/.#include
0200: 20 22 73 71 6c 69 74 65 49 6e 74 2e 68 22 0a 23   "sqliteInt.h".#
0210: 69 6e 63 6c 75 64 65 20 3c 61 73 73 65 72 74 2e  include <assert.
0220: 68 3e 0a 0a 2f 2a 20 54 75 72 6e 20 62 75 6c 6b  h>../* Turn bulk
0230: 20 6d 65 6d 6f 72 79 20 69 6e 74 6f 20 61 20 68   memory into a h
0240: 61 73 68 20 74 61 62 6c 65 20 6f 62 6a 65 63 74  ash table object
0250: 20 62 79 20 69 6e 69 74 69 61 6c 69 7a 69 6e 67   by initializing
0260: 20 74 68 65 0a 2a 2a 20 66 69 65 6c 64 73 20 6f   the.** fields o
0270: 66 20 74 68 65 20 48 61 73 68 20 73 74 72 75 63  f the Hash struc
0280: 74 75 72 65 2e 0a 2a 2a 0a 2a 2a 20 22 6e 65 77  ture..**.** "new
0290: 22 20 69 73 20 61 20 70 6f 69 6e 74 65 72 20 74  " is a pointer t
02a0: 6f 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65  o the hash table
02b0: 20 74 68 61 74 20 69 73 20 74 6f 20 62 65 20 69   that is to be i
02c0: 6e 69 74 69 61 6c 69 7a 65 64 2e 0a 2a 2a 20 6b  nitialized..** k
02d0: 65 79 43 6c 61 73 73 20 69 73 20 6f 6e 65 20 6f  eyClass is one o
02e0: 66 20 74 68 65 20 63 6f 6e 73 74 61 6e 74 73 20  f the constants 
02f0: 53 51 4c 49 54 45 5f 48 41 53 48 5f 49 4e 54 2c  SQLITE_HASH_INT,
0300: 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 50 4f 49   SQLITE_HASH_POI
0310: 4e 54 45 52 2c 0a 2a 2a 20 53 51 4c 49 54 45 5f  NTER,.** SQLITE_
0320: 48 41 53 48 5f 42 49 4e 41 52 59 2c 20 6f 72 20  HASH_BINARY, or 
0330: 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 49  SQLITE_HASH_STRI
0340: 4e 47 2e 20 20 54 68 65 20 76 61 6c 75 65 20 6f  NG.  The value o
0350: 66 20 6b 65 79 43 6c 61 73 73 20 0a 2a 2a 20 64  f keyClass .** d
0360: 65 74 65 72 6d 69 6e 65 73 20 77 68 61 74 20 6b  etermines what k
0370: 69 6e 64 20 6f 66 20 6b 65 79 20 74 68 65 20 68  ind of key the h
0380: 61 73 68 20 74 61 62 6c 65 20 77 69 6c 6c 20 75  ash table will u
0390: 73 65 2e 20 20 22 63 6f 70 79 4b 65 79 22 20 69  se.  "copyKey" i
03a0: 73 0a 2a 2a 20 74 72 75 65 20 69 66 20 74 68 65  s.** true if the
03b0: 20 68 61 73 68 20 74 61 62 6c 65 20 73 68 6f 75   hash table shou
03c0: 6c 64 20 6d 61 6b 65 20 69 74 73 20 6f 77 6e 20  ld make its own 
03d0: 70 72 69 76 61 74 65 20 63 6f 70 79 20 6f 66 20  private copy of 
03e0: 6b 65 79 73 20 61 6e 64 0a 2a 2a 20 66 61 6c 73  keys and.** fals
03f0: 65 20 69 66 20 69 74 20 73 68 6f 75 6c 64 20 6a  e if it should j
0400: 75 73 74 20 75 73 65 20 74 68 65 20 73 75 70 70  ust use the supp
0410: 6c 69 65 64 20 70 6f 69 6e 74 65 72 2e 20 20 43  lied pointer.  C
0420: 6f 70 79 4b 65 79 20 6f 6e 6c 79 20 6d 61 6b 65  opyKey only make
0430: 73 0a 2a 2a 20 73 65 6e 73 65 20 66 6f 72 20 53  s.** sense for S
0440: 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 49 4e  QLITE_HASH_STRIN
0450: 47 20 61 6e 64 20 53 51 4c 49 54 45 5f 48 41 53  G and SQLITE_HAS
0460: 48 5f 42 49 4e 41 52 59 20 61 6e 64 20 69 73 20  H_BINARY and is 
0470: 69 67 6e 6f 72 65 64 0a 2a 2a 20 66 6f 72 20 6f  ignored.** for o
0480: 74 68 65 72 20 6b 65 79 20 63 6c 61 73 73 65 73  ther key classes
0490: 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74 65  ..*/.void sqlite
04a0: 48 61 73 68 49 6e 69 74 28 48 61 73 68 20 2a 6e  HashInit(Hash *n
04b0: 65 77 2c 20 69 6e 74 20 6b 65 79 43 6c 61 73 73  ew, int keyClass
04c0: 2c 20 69 6e 74 20 63 6f 70 79 4b 65 79 29 7b 0a  , int copyKey){.
04d0: 20 20 61 73 73 65 72 74 28 20 6e 65 77 21 3d 30    assert( new!=0
04e0: 20 29 3b 0a 20 20 61 73 73 65 72 74 28 20 6b 65   );.  assert( ke
04f0: 79 43 6c 61 73 73 3e 3d 53 51 4c 49 54 45 5f 48  yClass>=SQLITE_H
0500: 41 53 48 5f 49 4e 54 20 26 26 20 6b 65 79 43 6c  ASH_INT && keyCl
0510: 61 73 73 3c 3d 53 51 4c 49 54 45 5f 48 41 53 48  ass<=SQLITE_HASH
0520: 5f 42 49 4e 41 52 59 20 29 3b 0a 20 20 6e 65 77  _BINARY );.  new
0530: 2d 3e 6b 65 79 43 6c 61 73 73 20 3d 20 6b 65 79  ->keyClass = key
0540: 43 6c 61 73 73 3b 0a 20 20 6e 65 77 2d 3e 63 6f  Class;.  new->co
0550: 70 79 4b 65 79 20 3d 20 63 6f 70 79 4b 65 79 20  pyKey = copyKey 
0560: 26 26 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  &&.             
0570: 20 20 20 28 6b 65 79 43 6c 61 73 73 3d 3d 53 51     (keyClass==SQ
0580: 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 49 4e 47  LITE_HASH_STRING
0590: 20 7c 7c 20 6b 65 79 43 6c 61 73 73 3d 3d 53 51   || keyClass==SQ
05a0: 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e 41 52 59  LITE_HASH_BINARY
05b0: 29 3b 0a 20 20 6e 65 77 2d 3e 66 69 72 73 74 20  );.  new->first 
05c0: 3d 20 30 3b 0a 20 20 6e 65 77 2d 3e 63 6f 75 6e  = 0;.  new->coun
05d0: 74 20 3d 20 30 3b 0a 20 20 6e 65 77 2d 3e 68 74  t = 0;.  new->ht
05e0: 73 69 7a 65 20 3d 20 30 3b 0a 20 20 6e 65 77 2d  size = 0;.  new-
05f0: 3e 68 74 20 3d 20 30 3b 0a 7d 0a 0a 2f 2a 20 52  >ht = 0;.}../* R
0600: 65 6d 6f 76 65 20 61 6c 6c 20 65 6e 74 72 69 65  emove all entrie
0610: 73 20 66 72 6f 6d 20 61 20 68 61 73 68 20 74 61  s from a hash ta
0620: 62 6c 65 2e 20 20 52 65 63 6c 61 69 6d 20 61 6c  ble.  Reclaim al
0630: 6c 20 6d 65 6d 6f 72 79 2e 0a 2a 2a 20 43 61 6c  l memory..** Cal
0640: 6c 20 74 68 69 73 20 72 6f 75 74 69 6e 65 20 74  l this routine t
0650: 6f 20 64 65 6c 65 74 65 20 61 20 68 61 73 68 20  o delete a hash 
0660: 74 61 62 6c 65 20 6f 72 20 74 6f 20 72 65 73 65  table or to rese
0670: 74 20 61 20 68 61 73 68 20 74 61 62 6c 65 0a 2a  t a hash table.*
0680: 2a 20 74 6f 20 74 68 65 20 65 6d 70 74 79 20 73  * to the empty s
0690: 74 61 74 65 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71  tate..*/.void sq
06a0: 6c 69 74 65 48 61 73 68 43 6c 65 61 72 28 48 61  liteHashClear(Ha
06b0: 73 68 20 2a 70 48 29 7b 0a 20 20 48 61 73 68 45  sh *pH){.  HashE
06c0: 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 20 20  lem *elem;      
06d0: 20 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f 70 69 6e     /* For loopin
06e0: 67 20 6f 76 65 72 20 61 6c 6c 20 65 6c 65 6d 65  g over all eleme
06f0: 6e 74 73 20 6f 66 20 74 68 65 20 74 61 62 6c 65  nts of the table
0700: 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 70   */..  assert( p
0710: 48 21 3d 30 20 29 3b 0a 20 20 65 6c 65 6d 20 3d  H!=0 );.  elem =
0720: 20 70 48 2d 3e 66 69 72 73 74 3b 0a 20 20 70 48   pH->first;.  pH
0730: 2d 3e 66 69 72 73 74 20 3d 20 30 3b 0a 20 20 69  ->first = 0;.  i
0740: 66 28 20 70 48 2d 3e 68 74 20 29 20 73 71 6c 69  f( pH->ht ) sqli
0750: 74 65 46 72 65 65 28 70 48 2d 3e 68 74 29 3b 0a  teFree(pH->ht);.
0760: 20 20 70 48 2d 3e 68 74 20 3d 20 30 3b 0a 20 20    pH->ht = 0;.  
0770: 70 48 2d 3e 68 74 73 69 7a 65 20 3d 20 30 3b 0a  pH->htsize = 0;.
0780: 20 20 77 68 69 6c 65 28 20 65 6c 65 6d 20 29 7b    while( elem ){
0790: 0a 20 20 20 20 48 61 73 68 45 6c 65 6d 20 2a 6e  .    HashElem *n
07a0: 65 78 74 5f 65 6c 65 6d 20 3d 20 65 6c 65 6d 2d  ext_elem = elem-
07b0: 3e 6e 65 78 74 3b 0a 20 20 20 20 69 66 28 20 70  >next;.    if( p
07c0: 48 2d 3e 63 6f 70 79 4b 65 79 20 26 26 20 65 6c  H->copyKey && el
07d0: 65 6d 2d 3e 70 4b 65 79 20 29 7b 0a 20 20 20 20  em->pKey ){.    
07e0: 20 20 73 71 6c 69 74 65 46 72 65 65 28 65 6c 65    sqliteFree(ele
07f0: 6d 2d 3e 70 4b 65 79 29 3b 0a 20 20 20 20 7d 0a  m->pKey);.    }.
0800: 20 20 20 20 73 71 6c 69 74 65 46 72 65 65 28 65      sqliteFree(e
0810: 6c 65 6d 29 3b 0a 20 20 20 20 65 6c 65 6d 20 3d  lem);.    elem =
0820: 20 6e 65 78 74 5f 65 6c 65 6d 3b 0a 20 20 7d 0a   next_elem;.  }.
0830: 20 20 70 48 2d 3e 63 6f 75 6e 74 20 3d 20 30 3b    pH->count = 0;
0840: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 48 61 73 68 20 61  .}../*.** Hash a
0850: 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75  nd comparison fu
0860: 6e 63 74 69 6f 6e 73 20 77 68 65 6e 20 74 68 65  nctions when the
0870: 20 6d 6f 64 65 20 69 73 20 53 51 4c 49 54 45 5f   mode is SQLITE_
0880: 48 41 53 48 5f 49 4e 54 0a 2a 2f 0a 73 74 61 74  HASH_INT.*/.stat
0890: 69 63 20 69 6e 74 20 69 6e 74 48 61 73 68 28 63  ic int intHash(c
08a0: 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c  onst void *pKey,
08b0: 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 72 65   int nKey){.  re
08c0: 74 75 72 6e 20 6e 4b 65 79 20 5e 20 28 6e 4b 65  turn nKey ^ (nKe
08d0: 79 3c 3c 38 29 20 5e 20 28 6e 4b 65 79 3e 3e 38  y<<8) ^ (nKey>>8
08e0: 29 3b 0a 7d 0a 73 74 61 74 69 63 20 69 6e 74 20  );.}.static int 
08f0: 69 6e 74 43 6f 6d 70 61 72 65 28 63 6f 6e 73 74  intCompare(const
0900: 20 76 6f 69 64 20 2a 70 4b 65 79 31 2c 20 69 6e   void *pKey1, in
0910: 74 20 6e 31 2c 20 63 6f 6e 73 74 20 76 6f 69 64  t n1, const void
0920: 20 2a 70 4b 65 79 32 2c 20 69 6e 74 20 6e 32 29   *pKey2, int n2)
0930: 7b 0a 20 20 72 65 74 75 72 6e 20 6e 32 20 2d 20  {.  return n2 - 
0940: 6e 31 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 48 61 73  n1;.}../*.** Has
0950: 68 20 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e  h and comparison
0960: 20 66 75 6e 63 74 69 6f 6e 73 20 77 68 65 6e 20   functions when 
0970: 74 68 65 20 6d 6f 64 65 20 69 73 20 53 51 4c 49  the mode is SQLI
0980: 54 45 5f 48 41 53 48 5f 50 4f 49 4e 54 45 52 0a  TE_HASH_POINTER.
0990: 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 70 74  */.static int pt
09a0: 72 48 61 73 68 28 63 6f 6e 73 74 20 76 6f 69 64  rHash(const void
09b0: 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79   *pKey, int nKey
09c0: 29 7b 0a 20 20 75 70 74 72 20 78 20 3d 20 41 64  ){.  uptr x = Ad
09d0: 64 72 28 70 4b 65 79 29 3b 0a 20 20 72 65 74 75  dr(pKey);.  retu
09e0: 72 6e 20 78 20 5e 20 28 78 3c 3c 38 29 20 5e 20  rn x ^ (x<<8) ^ 
09f0: 28 78 3e 3e 38 29 3b 0a 7d 0a 73 74 61 74 69 63  (x>>8);.}.static
0a00: 20 69 6e 74 20 70 74 72 43 6f 6d 70 61 72 65 28   int ptrCompare(
0a10: 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79  const void *pKey
0a20: 31 2c 20 69 6e 74 20 6e 31 2c 20 63 6f 6e 73 74  1, int n1, const
0a30: 20 76 6f 69 64 20 2a 70 4b 65 79 32 2c 20 69 6e   void *pKey2, in
0a40: 74 20 6e 32 29 7b 0a 20 20 69 66 28 20 70 4b 65  t n2){.  if( pKe
0a50: 79 31 3d 3d 70 4b 65 79 32 20 29 20 72 65 74 75  y1==pKey2 ) retu
0a60: 72 6e 20 30 3b 0a 20 20 69 66 28 20 70 4b 65 79  rn 0;.  if( pKey
0a70: 31 3c 70 4b 65 79 32 20 29 20 72 65 74 75 72 6e  1<pKey2 ) return
0a80: 20 2d 31 3b 0a 20 20 72 65 74 75 72 6e 20 31 3b   -1;.  return 1;
0a90: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 48 61 73 68 20 61  .}../*.** Hash a
0aa0: 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75  nd comparison fu
0ab0: 6e 63 74 69 6f 6e 73 20 77 68 65 6e 20 74 68 65  nctions when the
0ac0: 20 6d 6f 64 65 20 69 73 20 53 51 4c 49 54 45 5f   mode is SQLITE_
0ad0: 48 41 53 48 5f 53 54 52 49 4e 47 0a 2a 2f 0a 73  HASH_STRING.*/.s
0ae0: 74 61 74 69 63 20 69 6e 74 20 73 74 72 48 61 73  tatic int strHas
0af0: 68 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b  h(const void *pK
0b00: 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20  ey, int nKey){. 
0b10: 20 72 65 74 75 72 6e 20 73 71 6c 69 74 65 48 61   return sqliteHa
0b20: 73 68 4e 6f 43 61 73 65 28 28 63 6f 6e 73 74 20  shNoCase((const 
0b30: 63 68 61 72 2a 29 70 4b 65 79 2c 20 6e 4b 65 79  char*)pKey, nKey
0b40: 29 3b 20 0a 7d 0a 73 74 61 74 69 63 20 69 6e 74  ); .}.static int
0b50: 20 73 74 72 43 6f 6d 70 61 72 65 28 63 6f 6e 73   strCompare(cons
0b60: 74 20 76 6f 69 64 20 2a 70 4b 65 79 31 2c 20 69  t void *pKey1, i
0b70: 6e 74 20 6e 31 2c 20 63 6f 6e 73 74 20 76 6f 69  nt n1, const voi
0b80: 64 20 2a 70 4b 65 79 32 2c 20 69 6e 74 20 6e 32  d *pKey2, int n2
0b90: 29 7b 0a 20 20 69 66 28 20 6e 31 21 3d 6e 32 20  ){.  if( n1!=n2 
0ba0: 29 20 72 65 74 75 72 6e 20 6e 32 2d 6e 31 3b 0a  ) return n2-n1;.
0bb0: 20 20 72 65 74 75 72 6e 20 73 71 6c 69 74 65 53    return sqliteS
0bc0: 74 72 4e 49 43 6d 70 28 28 63 6f 6e 73 74 20 63  trNICmp((const c
0bd0: 68 61 72 2a 29 70 4b 65 79 31 2c 28 63 6f 6e 73  har*)pKey1,(cons
0be0: 74 20 63 68 61 72 2a 29 70 4b 65 79 32 2c 6e 31  t char*)pKey2,n1
0bf0: 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 48 61 73 68  );.}../*.** Hash
0c00: 20 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e 20   and comparison 
0c10: 66 75 6e 63 74 69 6f 6e 73 20 77 68 65 6e 20 74  functions when t
0c20: 68 65 20 6d 6f 64 65 20 69 73 20 53 51 4c 49 54  he mode is SQLIT
0c30: 45 5f 48 41 53 48 5f 42 49 4e 41 52 59 0a 2a 2f  E_HASH_BINARY.*/
0c40: 0a 73 74 61 74 69 63 20 69 6e 74 20 62 69 6e 48  .static int binH
0c50: 61 73 68 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a  ash(const void *
0c60: 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b  pKey, int nKey){
0c70: 0a 20 20 69 6e 74 20 68 20 3d 20 30 3b 0a 20 20  .  int h = 0;.  
0c80: 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a 20 3d 20  const char *z = 
0c90: 28 63 6f 6e 73 74 20 63 68 61 72 20 2a 29 70 4b  (const char *)pK
0ca0: 65 79 3b 0a 20 20 77 68 69 6c 65 28 20 6e 4b 65  ey;.  while( nKe
0cb0: 79 2d 2d 20 3e 20 30 20 29 7b 0a 20 20 20 20 68  y-- > 0 ){.    h
0cc0: 20 3d 20 28 68 3c 3c 33 29 20 5e 20 68 20 5e 20   = (h<<3) ^ h ^ 
0cd0: 2a 28 7a 2b 2b 29 3b 0a 20 20 7d 0a 20 20 69 66  *(z++);.  }.  if
0ce0: 28 20 68 3c 30 20 29 20 68 20 3d 20 2d 68 3b 0a  ( h<0 ) h = -h;.
0cf0: 20 20 72 65 74 75 72 6e 20 68 3b 0a 7d 0a 73 74    return h;.}.st
0d00: 61 74 69 63 20 69 6e 74 20 62 69 6e 43 6f 6d 70  atic int binComp
0d10: 61 72 65 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a  are(const void *
0d20: 70 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c 20 63  pKey1, int n1, c
0d30: 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 32  onst void *pKey2
0d40: 2c 20 69 6e 74 20 6e 32 29 7b 0a 20 20 69 66 28  , int n2){.  if(
0d50: 20 6e 31 21 3d 6e 32 20 29 20 72 65 74 75 72 6e   n1!=n2 ) return
0d60: 20 6e 32 2d 6e 31 3b 0a 20 20 72 65 74 75 72 6e   n2-n1;.  return
0d70: 20 6d 65 6d 63 6d 70 28 70 4b 65 79 31 2c 70 4b   memcmp(pKey1,pK
0d80: 65 79 32 2c 6e 31 29 3b 0a 7d 0a 0a 2f 2a 0a 2a  ey2,n1);.}../*.*
0d90: 2a 20 52 65 74 75 72 6e 20 61 20 70 6f 69 6e 74  * Return a point
0da0: 65 72 20 74 6f 20 74 68 65 20 61 70 70 72 6f 70  er to the approp
0db0: 72 69 61 74 65 20 68 61 73 68 20 66 75 6e 63 74  riate hash funct
0dc0: 69 6f 6e 20 67 69 76 65 6e 20 74 68 65 20 6b 65  ion given the ke
0dd0: 79 20 63 6c 61 73 73 2e 0a 2a 2a 0a 2a 2a 20 54  y class..**.** T
0de0: 68 65 20 43 20 73 79 6e 74 61 78 20 69 6e 20 74  he C syntax in t
0df0: 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 64 65 66  his function def
0e00: 69 6e 69 74 69 6f 6e 20 6d 61 79 20 62 65 20 75  inition may be u
0e10: 6e 66 61 6d 69 6c 61 72 20 74 6f 20 73 6f 6d 65  nfamilar to some
0e20: 20 0a 2a 2a 20 70 72 6f 67 72 61 6d 6d 65 72 73   .** programmers
0e30: 2c 20 73 6f 20 77 65 20 70 72 6f 76 69 64 65 20  , so we provide 
0e40: 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 61 64  the following ad
0e50: 64 69 74 69 6f 6e 61 6c 20 65 78 70 6c 61 6e 61  ditional explana
0e60: 74 69 6f 6e 3a 0a 2a 2a 0a 2a 2a 20 54 68 65 20  tion:.**.** The 
0e70: 6e 61 6d 65 20 6f 66 20 74 68 65 20 66 75 6e 63  name of the func
0e80: 74 69 6f 6e 20 69 73 20 22 68 61 73 68 46 75 6e  tion is "hashFun
0e90: 63 74 69 6f 6e 22 2e 20 20 54 68 65 20 66 75 6e  ction".  The fun
0ea0: 63 74 69 6f 6e 20 74 61 6b 65 73 20 61 0a 2a 2a  ction takes a.**
0eb0: 20 73 69 6e 67 6c 65 20 70 61 72 61 6d 65 74 65   single paramete
0ec0: 72 20 22 6b 65 79 43 6c 61 73 73 22 2e 20 20 54  r "keyClass".  T
0ed0: 68 65 20 72 65 74 75 72 6e 20 76 61 6c 75 65 20  he return value 
0ee0: 6f 66 20 68 61 73 68 46 75 6e 63 74 69 6f 6e 28  of hashFunction(
0ef0: 29 0a 2a 2a 20 69 73 20 61 20 70 6f 69 6e 74 65  ).** is a pointe
0f00: 72 20 74 6f 20 61 6e 6f 74 68 65 72 20 66 75 6e  r to another fun
0f10: 63 74 69 6f 6e 2e 20 20 53 70 65 63 69 66 69 63  ction.  Specific
0f20: 61 6c 6c 79 2c 20 74 68 65 20 72 65 74 75 72 6e  ally, the return
0f30: 20 76 61 6c 75 65 0a 2a 2a 20 6f 66 20 68 61 73   value.** of has
0f40: 68 46 75 6e 63 74 69 6f 6e 28 29 20 69 73 20 61  hFunction() is a
0f50: 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 20 66 75   pointer to a fu
0f60: 6e 63 74 69 6f 6e 20 74 68 61 74 20 74 61 6b 65  nction that take
0f70: 73 20 74 77 6f 20 70 61 72 61 6d 65 74 65 72 73  s two parameters
0f80: 0a 2a 2a 20 77 69 74 68 20 74 79 70 65 73 20 22  .** with types "
0f90: 63 6f 6e 73 74 20 76 6f 69 64 2a 22 20 61 6e 64  const void*" and
0fa0: 20 22 69 6e 74 22 20 61 6e 64 20 72 65 74 75 72   "int" and retur
0fb0: 6e 73 20 61 6e 20 22 69 6e 74 22 2e 0a 2a 2f 0a  ns an "int"..*/.
0fc0: 73 74 61 74 69 63 20 69 6e 74 20 28 2a 68 61 73  static int (*has
0fd0: 68 46 75 6e 63 74 69 6f 6e 28 69 6e 74 20 6b 65  hFunction(int ke
0fe0: 79 43 6c 61 73 73 29 29 28 63 6f 6e 73 74 20 76  yClass))(const v
0ff0: 6f 69 64 2a 2c 69 6e 74 29 7b 0a 20 20 73 77 69  oid*,int){.  swi
1000: 74 63 68 28 20 6b 65 79 43 6c 61 73 73 20 29 7b  tch( keyClass ){
1010: 0a 20 20 20 20 63 61 73 65 20 53 51 4c 49 54 45  .    case SQLITE
1020: 5f 48 41 53 48 5f 49 4e 54 3a 20 20 20 20 20 72  _HASH_INT:     r
1030: 65 74 75 72 6e 20 26 69 6e 74 48 61 73 68 3b 0a  eturn &intHash;.
1040: 20 20 20 20 63 61 73 65 20 53 51 4c 49 54 45 5f      case SQLITE_
1050: 48 41 53 48 5f 50 4f 49 4e 54 45 52 3a 20 72 65  HASH_POINTER: re
1060: 74 75 72 6e 20 26 70 74 72 48 61 73 68 3b 0a 20  turn &ptrHash;. 
1070: 20 20 20 63 61 73 65 20 53 51 4c 49 54 45 5f 48     case SQLITE_H
1080: 41 53 48 5f 53 54 52 49 4e 47 3a 20 20 72 65 74  ASH_STRING:  ret
1090: 75 72 6e 20 26 73 74 72 48 61 73 68 3b 0a 20 20  urn &strHash;.  
10a0: 20 20 63 61 73 65 20 53 51 4c 49 54 45 5f 48 41    case SQLITE_HA
10b0: 53 48 5f 42 49 4e 41 52 59 3a 20 20 72 65 74 75  SH_BINARY:  retu
10c0: 72 6e 20 26 62 69 6e 48 61 73 68 3b 3b 0a 20 20  rn &binHash;;.  
10d0: 20 20 64 65 66 61 75 6c 74 3a 20 62 72 65 61 6b    default: break
10e0: 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 30  ;.  }.  return 0
10f0: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72  ;.}../*.** Retur
1100: 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74  n a pointer to t
1110: 68 65 20 61 70 70 72 6f 70 72 69 61 74 65 20 68  he appropriate h
1120: 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 67 69 76  ash function giv
1130: 65 6e 20 74 68 65 20 6b 65 79 20 63 6c 61 73 73  en the key class
1140: 2e 0a 2a 2a 0a 2a 2a 20 46 6f 72 20 68 65 6c 70  ..**.** For help
1150: 20 69 6e 20 69 6e 74 65 72 70 72 65 74 65 64 20   in interpreted 
1160: 74 68 65 20 6f 62 73 63 75 72 65 20 43 20 63 6f  the obscure C co
1170: 64 65 20 69 6e 20 74 68 65 20 66 75 6e 63 74 69  de in the functi
1180: 6f 6e 20 64 65 66 69 6e 69 74 69 6f 6e 2c 0a 2a  on definition,.*
1190: 2a 20 73 65 65 20 74 68 65 20 68 65 61 64 65 72  * see the header
11a0: 20 63 6f 6d 6d 65 6e 74 20 6f 6e 20 74 68 65 20   comment on the 
11b0: 70 72 65 76 69 6f 75 73 20 66 75 6e 63 74 69 6f  previous functio
11c0: 6e 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74  n..*/.static int
11d0: 20 28 2a 63 6f 6d 70 61 72 65 46 75 6e 63 74 69   (*compareFuncti
11e0: 6f 6e 28 69 6e 74 20 6b 65 79 43 6c 61 73 73 29  on(int keyClass)
11f0: 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e  )(const void*,in
1200: 74 2c 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e  t,const void*,in
1210: 74 29 7b 0a 20 20 73 77 69 74 63 68 28 20 6b 65  t){.  switch( ke
1220: 79 43 6c 61 73 73 20 29 7b 0a 20 20 20 20 63 61  yClass ){.    ca
1230: 73 65 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 49  se SQLITE_HASH_I
1240: 4e 54 3a 20 20 20 20 20 72 65 74 75 72 6e 20 26  NT:     return &
1250: 69 6e 74 43 6f 6d 70 61 72 65 3b 0a 20 20 20 20  intCompare;.    
1260: 63 61 73 65 20 53 51 4c 49 54 45 5f 48 41 53 48  case SQLITE_HASH
1270: 5f 50 4f 49 4e 54 45 52 3a 20 72 65 74 75 72 6e  _POINTER: return
1280: 20 26 70 74 72 43 6f 6d 70 61 72 65 3b 0a 20 20   &ptrCompare;.  
1290: 20 20 63 61 73 65 20 53 51 4c 49 54 45 5f 48 41    case SQLITE_HA
12a0: 53 48 5f 53 54 52 49 4e 47 3a 20 20 72 65 74 75  SH_STRING:  retu
12b0: 72 6e 20 26 73 74 72 43 6f 6d 70 61 72 65 3b 0a  rn &strCompare;.
12c0: 20 20 20 20 63 61 73 65 20 53 51 4c 49 54 45 5f      case SQLITE_
12d0: 48 41 53 48 5f 42 49 4e 41 52 59 3a 20 20 72 65  HASH_BINARY:  re
12e0: 74 75 72 6e 20 26 62 69 6e 43 6f 6d 70 61 72 65  turn &binCompare
12f0: 3b 0a 20 20 20 20 64 65 66 61 75 6c 74 3a 20 62  ;.    default: b
1300: 72 65 61 6b 3b 0a 20 20 7d 0a 20 20 72 65 74 75  reak;.  }.  retu
1310: 72 6e 20 30 3b 0a 7d 0a 0a 0a 2f 2a 20 52 65 73  rn 0;.}.../* Res
1320: 69 7a 65 20 74 68 65 20 68 61 73 68 20 74 61 62  ize the hash tab
1330: 6c 65 20 73 6f 20 74 68 61 74 20 69 74 20 63 61  le so that it ca
1340: 6e 74 61 69 6e 73 20 22 6e 65 77 5f 73 69 7a 65  ntains "new_size
1350: 22 20 62 75 63 6b 65 74 73 2e 0a 2a 2a 20 22 6e  " buckets..** "n
1360: 65 77 5f 73 69 7a 65 22 20 6d 75 73 74 20 62 65  ew_size" must be
1370: 20 61 20 70 6f 77 65 72 20 6f 66 20 32 2e 20 20   a power of 2.  
1380: 54 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 6d  The hash table m
1390: 69 67 68 74 20 66 61 69 6c 20 0a 2a 2a 20 74 6f  ight fail .** to
13a0: 20 72 65 73 69 7a 65 20 69 66 20 73 71 6c 69 74   resize if sqlit
13b0: 65 4d 61 6c 6c 6f 63 28 29 20 66 61 69 6c 73 2e  eMalloc() fails.
13c0: 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20  .*/.static void 
13d0: 72 65 68 61 73 68 28 48 61 73 68 20 2a 70 48 2c  rehash(Hash *pH,
13e0: 20 69 6e 74 20 6e 65 77 5f 73 69 7a 65 29 7b 0a   int new_size){.
13f0: 20 20 73 74 72 75 63 74 20 5f 68 74 20 2a 6e 65    struct _ht *ne
1400: 77 5f 68 74 3b 20 20 20 20 20 20 20 20 20 20 20  w_ht;           
1410: 20 2f 2a 20 54 68 65 20 6e 65 77 20 68 61 73 68   /* The new hash
1420: 20 74 61 62 6c 65 20 2a 2f 0a 20 20 48 61 73 68   table */.  Hash
1430: 45 6c 65 6d 20 2a 65 6c 65 6d 2c 20 2a 6e 65 78  Elem *elem, *nex
1440: 74 5f 65 6c 65 6d 3b 20 20 20 20 2f 2a 20 46 6f  t_elem;    /* Fo
1450: 72 20 6c 6f 6f 70 69 6e 67 20 6f 76 65 72 20 65  r looping over e
1460: 78 69 73 74 69 6e 67 20 65 6c 65 6d 65 6e 74 73  xisting elements
1470: 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a   */.  HashElem *
1480: 78 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  x;              
1490: 20 20 20 20 20 2f 2a 20 45 6c 65 6d 65 6e 74 20       /* Element 
14a0: 62 65 69 6e 67 20 63 6f 70 69 65 64 20 74 6f 20  being copied to 
14b0: 6e 65 77 20 68 61 73 68 20 74 61 62 6c 65 20 2a  new hash table *
14c0: 2f 0a 20 20 69 6e 74 20 28 2a 78 48 61 73 68 29  /.  int (*xHash)
14d0: 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74  (const void*,int
14e0: 29 3b 20 2f 2a 20 54 68 65 20 68 61 73 68 20 66  ); /* The hash f
14f0: 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20 61 73  unction */..  as
1500: 73 65 72 74 28 20 28 6e 65 77 5f 73 69 7a 65 20  sert( (new_size 
1510: 26 20 28 6e 65 77 5f 73 69 7a 65 2d 31 29 29 3d  & (new_size-1))=
1520: 3d 30 20 29 3b 0a 20 20 6e 65 77 5f 68 74 20 3d  =0 );.  new_ht =
1530: 20 28 73 74 72 75 63 74 20 5f 68 74 20 2a 29 73   (struct _ht *)s
1540: 71 6c 69 74 65 4d 61 6c 6c 6f 63 28 20 6e 65 77  qliteMalloc( new
1550: 5f 73 69 7a 65 2a 73 69 7a 65 6f 66 28 73 74 72  _size*sizeof(str
1560: 75 63 74 20 5f 68 74 29 20 29 3b 0a 20 20 69 66  uct _ht) );.  if
1570: 28 20 6e 65 77 5f 68 74 3d 3d 30 20 29 20 72 65  ( new_ht==0 ) re
1580: 74 75 72 6e 3b 0a 20 20 69 66 28 20 70 48 2d 3e  turn;.  if( pH->
1590: 68 74 20 29 20 73 71 6c 69 74 65 46 72 65 65 28  ht ) sqliteFree(
15a0: 70 48 2d 3e 68 74 29 3b 0a 20 20 70 48 2d 3e 68  pH->ht);.  pH->h
15b0: 74 20 3d 20 6e 65 77 5f 68 74 3b 0a 20 20 70 48  t = new_ht;.  pH
15c0: 2d 3e 68 74 73 69 7a 65 20 3d 20 6e 65 77 5f 73  ->htsize = new_s
15d0: 69 7a 65 3b 0a 20 20 78 48 61 73 68 20 3d 20 68  ize;.  xHash = h
15e0: 61 73 68 46 75 6e 63 74 69 6f 6e 28 70 48 2d 3e  ashFunction(pH->
15f0: 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20 66 6f 72  keyClass);.  for
1600: 28 65 6c 65 6d 3d 70 48 2d 3e 66 69 72 73 74 2c  (elem=pH->first,
1610: 20 70 48 2d 3e 66 69 72 73 74 3d 30 3b 20 65 6c   pH->first=0; el
1620: 65 6d 3b 20 65 6c 65 6d 20 3d 20 6e 65 78 74 5f  em; elem = next_
1630: 65 6c 65 6d 29 7b 0a 20 20 20 20 69 6e 74 20 68  elem){.    int h
1640: 20 3d 20 28 2a 78 48 61 73 68 29 28 65 6c 65 6d   = (*xHash)(elem
1650: 2d 3e 70 4b 65 79 2c 20 65 6c 65 6d 2d 3e 6e 4b  ->pKey, elem->nK
1660: 65 79 29 20 26 20 28 6e 65 77 5f 73 69 7a 65 2d  ey) & (new_size-
1670: 31 29 3b 0a 20 20 20 20 6e 65 78 74 5f 65 6c 65  1);.    next_ele
1680: 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a  m = elem->next;.
1690: 20 20 20 20 78 20 3d 20 6e 65 77 5f 68 74 5b 68      x = new_ht[h
16a0: 5d 2e 63 68 61 69 6e 3b 0a 20 20 20 20 69 66 28  ].chain;.    if(
16b0: 20 78 20 29 7b 0a 20 20 20 20 20 20 65 6c 65 6d   x ){.      elem
16c0: 2d 3e 6e 65 78 74 20 3d 20 78 3b 0a 20 20 20 20  ->next = x;.    
16d0: 20 20 65 6c 65 6d 2d 3e 70 72 65 76 20 3d 20 78    elem->prev = x
16e0: 2d 3e 70 72 65 76 3b 0a 20 20 20 20 20 20 69 66  ->prev;.      if
16f0: 28 20 78 2d 3e 70 72 65 76 20 29 20 78 2d 3e 70  ( x->prev ) x->p
1700: 72 65 76 2d 3e 6e 65 78 74 20 3d 20 65 6c 65 6d  rev->next = elem
1710: 3b 0a 20 20 20 20 20 20 65 6c 73 65 20 20 20 20  ;.      else    
1720: 20 20 20 20 20 20 70 48 2d 3e 66 69 72 73 74 20        pH->first 
1730: 3d 20 65 6c 65 6d 3b 0a 20 20 20 20 20 20 78 2d  = elem;.      x-
1740: 3e 70 72 65 76 20 3d 20 65 6c 65 6d 3b 0a 20 20  >prev = elem;.  
1750: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 65    }else{.      e
1760: 6c 65 6d 2d 3e 6e 65 78 74 20 3d 20 70 48 2d 3e  lem->next = pH->
1770: 66 69 72 73 74 3b 0a 20 20 20 20 20 20 69 66 28  first;.      if(
1780: 20 70 48 2d 3e 66 69 72 73 74 20 29 20 70 48 2d   pH->first ) pH-
1790: 3e 66 69 72 73 74 2d 3e 70 72 65 76 20 3d 20 65  >first->prev = e
17a0: 6c 65 6d 3b 0a 20 20 20 20 20 20 65 6c 65 6d 2d  lem;.      elem-
17b0: 3e 70 72 65 76 20 3d 20 30 3b 0a 20 20 20 20 20  >prev = 0;.     
17c0: 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 65 6c 65   pH->first = ele
17d0: 6d 3b 0a 20 20 20 20 7d 0a 20 20 20 20 6e 65 77  m;.    }.    new
17e0: 5f 68 74 5b 68 5d 2e 63 68 61 69 6e 20 3d 20 65  _ht[h].chain = e
17f0: 6c 65 6d 3b 0a 20 20 20 20 6e 65 77 5f 68 74 5b  lem;.    new_ht[
1800: 68 5d 2e 63 6f 75 6e 74 2b 2b 3b 0a 20 20 7d 0a  h].count++;.  }.
1810: 7d 0a 0a 2f 2a 20 54 68 69 73 20 66 75 6e 63 74  }../* This funct
1820: 69 6f 6e 20 28 66 6f 72 20 69 6e 74 65 72 6e 61  ion (for interna
1830: 6c 20 75 73 65 20 6f 6e 6c 79 29 20 6c 6f 63 61  l use only) loca
1840: 74 65 73 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69  tes an element i
1850: 6e 20 61 6e 0a 2a 2a 20 68 61 73 68 20 74 61 62  n an.** hash tab
1860: 6c 65 20 74 68 61 74 20 6d 61 74 63 68 65 73 20  le that matches 
1870: 74 68 65 20 67 69 76 65 6e 20 6b 65 79 2e 20 20  the given key.  
1880: 54 68 65 20 68 61 73 68 20 66 6f 72 20 74 68 69  The hash for thi
1890: 73 20 6b 65 79 20 68 61 73 0a 2a 2a 20 61 6c 72  s key has.** alr
18a0: 65 61 64 79 20 62 65 65 6e 20 63 6f 6d 70 75 74  eady been comput
18b0: 65 64 20 61 6e 64 20 69 73 20 70 61 73 73 65 64  ed and is passed
18c0: 20 61 73 20 74 68 65 20 34 74 68 20 70 61 72 61   as the 4th para
18d0: 6d 65 74 65 72 2e 0a 2a 2f 0a 73 74 61 74 69 63  meter..*/.static
18e0: 20 48 61 73 68 45 6c 65 6d 20 2a 66 69 6e 64 45   HashElem *findE
18f0: 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28  lementGivenHash(
1900: 0a 20 20 63 6f 6e 73 74 20 48 61 73 68 20 2a 70  .  const Hash *p
1910: 48 2c 20 20 20 20 20 2f 2a 20 54 68 65 20 70 48  H,     /* The pH
1920: 20 74 6f 20 62 65 20 73 65 61 72 63 68 65 64 20   to be searched 
1930: 2a 2f 0a 20 20 63 6f 6e 73 74 20 76 6f 69 64 20  */.  const void 
1940: 2a 70 4b 65 79 2c 20 20 20 2f 2a 20 54 68 65 20  *pKey,   /* The 
1950: 6b 65 79 20 77 65 20 61 72 65 20 73 65 61 72 63  key we are searc
1960: 68 69 6e 67 20 66 6f 72 20 2a 2f 0a 20 20 69 6e  hing for */.  in
1970: 74 20 6e 4b 65 79 2c 0a 20 20 69 6e 74 20 68 20  t nKey,.  int h 
1980: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
1990: 20 54 68 65 20 68 61 73 68 20 66 6f 72 20 74 68   The hash for th
19a0: 69 73 20 6b 65 79 2e 20 2a 2f 0a 29 7b 0a 20 20  is key. */.){.  
19b0: 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20  HashElem *elem; 
19c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
19d0: 2a 20 55 73 65 64 20 74 6f 20 6c 6f 6f 70 20 74  * Used to loop t
19e0: 68 72 75 20 74 68 65 20 65 6c 65 6d 65 6e 74 20  hru the element 
19f0: 6c 69 73 74 20 2a 2f 0a 20 20 69 6e 74 20 63 6f  list */.  int co
1a00: 75 6e 74 3b 20 20 20 20 20 20 20 20 20 20 20 20  unt;            
1a10: 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62           /* Numb
1a20: 65 72 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20 6c  er of elements l
1a30: 65 66 74 20 74 6f 20 74 65 73 74 20 2a 2f 0a 20  eft to test */. 
1a40: 20 69 6e 74 20 28 2a 78 43 6f 6d 70 61 72 65 29   int (*xCompare)
1a50: 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74  (const void*,int
1a60: 2c 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74  ,const void*,int
1a70: 29 3b 20 20 2f 2a 20 63 6f 6d 70 61 72 69 73 6f  );  /* compariso
1a80: 6e 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20  n function */.. 
1a90: 20 69 66 28 20 70 48 2d 3e 68 74 20 29 7b 0a 20   if( pH->ht ){. 
1aa0: 20 20 20 65 6c 65 6d 20 3d 20 70 48 2d 3e 68 74     elem = pH->ht
1ab0: 5b 68 5d 2e 63 68 61 69 6e 3b 0a 20 20 20 20 63  [h].chain;.    c
1ac0: 6f 75 6e 74 20 3d 20 70 48 2d 3e 68 74 5b 68 5d  ount = pH->ht[h]
1ad0: 2e 63 6f 75 6e 74 3b 0a 20 20 20 20 78 43 6f 6d  .count;.    xCom
1ae0: 70 61 72 65 20 3d 20 63 6f 6d 70 61 72 65 46 75  pare = compareFu
1af0: 6e 63 74 69 6f 6e 28 70 48 2d 3e 6b 65 79 43 6c  nction(pH->keyCl
1b00: 61 73 73 29 3b 0a 20 20 20 20 77 68 69 6c 65 28  ass);.    while(
1b10: 20 63 6f 75 6e 74 2d 2d 20 26 26 20 65 6c 65 6d   count-- && elem
1b20: 20 29 7b 0a 20 20 20 20 20 20 69 66 28 20 28 2a   ){.      if( (*
1b30: 78 43 6f 6d 70 61 72 65 29 28 65 6c 65 6d 2d 3e  xCompare)(elem->
1b40: 70 4b 65 79 2c 65 6c 65 6d 2d 3e 6e 4b 65 79 2c  pKey,elem->nKey,
1b50: 70 4b 65 79 2c 6e 4b 65 79 29 3d 3d 30 20 29 7b  pKey,nKey)==0 ){
1b60: 20 0a 20 20 20 20 20 20 20 20 72 65 74 75 72 6e   .        return
1b70: 20 65 6c 65 6d 3b 0a 20 20 20 20 20 20 7d 0a 20   elem;.      }. 
1b80: 20 20 20 20 20 65 6c 65 6d 20 3d 20 65 6c 65 6d       elem = elem
1b90: 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 7d 0a 20 20  ->next;.    }.  
1ba0: 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a  }.  return 0;.}.
1bb0: 0a 2f 2a 20 52 65 6d 6f 76 65 20 61 20 73 69 6e  ./* Remove a sin
1bc0: 67 6c 65 20 65 6e 74 72 79 20 66 72 6f 6d 20 74  gle entry from t
1bd0: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 67 69  he hash table gi
1be0: 76 65 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f  ven a pointer to
1bf0: 20 74 68 61 74 0a 2a 2a 20 65 6c 65 6d 65 6e 74   that.** element
1c00: 20 61 6e 64 20 61 20 68 61 73 68 20 6f 6e 20 74   and a hash on t
1c10: 68 65 20 65 6c 65 6d 65 6e 74 27 73 20 6b 65 79  he element's key
1c20: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64  ..*/.static void
1c30: 20 72 65 6d 6f 76 65 45 6c 65 6d 65 6e 74 47 69   removeElementGi
1c40: 76 65 6e 48 61 73 68 28 0a 20 20 48 61 73 68 20  venHash(.  Hash 
1c50: 2a 70 48 2c 20 20 20 20 20 20 20 20 20 2f 2a 20  *pH,         /* 
1c60: 54 68 65 20 70 48 20 63 6f 6e 74 61 69 6e 69 6e  The pH containin
1c70: 67 20 22 65 6c 65 6d 22 20 2a 2f 0a 20 20 48 61  g "elem" */.  Ha
1c80: 73 68 45 6c 65 6d 2a 20 65 6c 65 6d 2c 20 20 20  shElem* elem,   
1c90: 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e 74 20 74  /* The element t
1ca0: 6f 20 62 65 20 72 65 6d 6f 76 65 64 20 66 72 6f  o be removed fro
1cb0: 6d 20 74 68 65 20 70 48 20 2a 2f 0a 20 20 69 6e  m the pH */.  in
1cc0: 74 20 68 20 20 20 20 20 20 20 20 20 20 20 20 20  t h             
1cd0: 2f 2a 20 48 61 73 68 20 76 61 6c 75 65 20 66 6f  /* Hash value fo
1ce0: 72 20 74 68 65 20 65 6c 65 6d 65 6e 74 20 2a 2f  r the element */
1cf0: 0a 29 7b 0a 20 20 69 66 28 20 65 6c 65 6d 2d 3e  .){.  if( elem->
1d00: 70 72 65 76 20 29 7b 0a 20 20 20 20 65 6c 65 6d  prev ){.    elem
1d10: 2d 3e 70 72 65 76 2d 3e 6e 65 78 74 20 3d 20 65  ->prev->next = e
1d20: 6c 65 6d 2d 3e 6e 65 78 74 3b 20 0a 20 20 7d 65  lem->next; .  }e
1d30: 6c 73 65 7b 0a 20 20 20 20 70 48 2d 3e 66 69 72  lse{.    pH->fir
1d40: 73 74 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b  st = elem->next;
1d50: 0a 20 20 7d 0a 20 20 69 66 28 20 65 6c 65 6d 2d  .  }.  if( elem-
1d60: 3e 6e 65 78 74 20 29 7b 0a 20 20 20 20 65 6c 65  >next ){.    ele
1d70: 6d 2d 3e 6e 65 78 74 2d 3e 70 72 65 76 20 3d 20  m->next->prev = 
1d80: 65 6c 65 6d 2d 3e 70 72 65 76 3b 0a 20 20 7d 0a  elem->prev;.  }.
1d90: 20 20 69 66 28 20 70 48 2d 3e 68 74 5b 68 5d 2e    if( pH->ht[h].
1da0: 63 68 61 69 6e 3d 3d 65 6c 65 6d 20 29 7b 0a 20  chain==elem ){. 
1db0: 20 20 20 70 48 2d 3e 68 74 5b 68 5d 2e 63 68 61     pH->ht[h].cha
1dc0: 69 6e 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b  in = elem->next;
1dd0: 0a 20 20 7d 0a 20 20 70 48 2d 3e 68 74 5b 68 5d  .  }.  pH->ht[h]
1de0: 2e 63 6f 75 6e 74 2d 2d 3b 0a 20 20 69 66 28 20  .count--;.  if( 
1df0: 70 48 2d 3e 68 74 5b 68 5d 2e 63 6f 75 6e 74 3c  pH->ht[h].count<
1e00: 3d 30 20 29 7b 0a 20 20 20 20 70 48 2d 3e 68 74  =0 ){.    pH->ht
1e10: 5b 68 5d 2e 63 68 61 69 6e 20 3d 20 30 3b 0a 20  [h].chain = 0;. 
1e20: 20 7d 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f 70   }.  if( pH->cop
1e30: 79 4b 65 79 20 26 26 20 65 6c 65 6d 2d 3e 70 4b  yKey && elem->pK
1e40: 65 79 20 29 7b 0a 20 20 20 20 73 71 6c 69 74 65  ey ){.    sqlite
1e50: 46 72 65 65 28 65 6c 65 6d 2d 3e 70 4b 65 79 29  Free(elem->pKey)
1e60: 3b 0a 20 20 7d 0a 20 20 73 71 6c 69 74 65 46 72  ;.  }.  sqliteFr
1e70: 65 65 28 20 65 6c 65 6d 20 29 3b 0a 20 20 70 48  ee( elem );.  pH
1e80: 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a 7d 0a 0a 2f 2a  ->count--;.}../*
1e90: 20 41 74 74 65 6d 70 74 20 74 6f 20 6c 6f 63 61   Attempt to loca
1ea0: 74 65 20 61 6e 20 65 6c 65 6d 65 6e 74 20 6f 66  te an element of
1eb0: 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20   the hash table 
1ec0: 70 48 20 77 69 74 68 20 61 20 6b 65 79 0a 2a 2a  pH with a key.**
1ed0: 20 74 68 61 74 20 6d 61 74 63 68 65 73 20 70 4b   that matches pK
1ee0: 65 79 2c 6e 4b 65 79 2e 20 20 52 65 74 75 72 6e  ey,nKey.  Return
1ef0: 20 74 68 65 20 64 61 74 61 20 66 6f 72 20 74 68   the data for th
1f00: 69 73 20 65 6c 65 6d 65 6e 74 20 69 66 20 69 74  is element if it
1f10: 20 69 73 0a 2a 2a 20 66 6f 75 6e 64 2c 20 6f 72   is.** found, or
1f20: 20 4e 55 4c 4c 20 69 66 20 74 68 65 72 65 20 69   NULL if there i
1f30: 73 20 6e 6f 20 6d 61 74 63 68 2e 0a 2a 2f 0a 76  s no match..*/.v
1f40: 6f 69 64 20 2a 73 71 6c 69 74 65 48 61 73 68 46  oid *sqliteHashF
1f50: 69 6e 64 28 63 6f 6e 73 74 20 48 61 73 68 20 2a  ind(const Hash *
1f60: 70 48 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a  pH, const void *
1f70: 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b  pKey, int nKey){
1f80: 0a 20 20 69 6e 74 20 68 3b 20 20 20 20 20 20 20  .  int h;       
1f90: 20 20 20 20 20 20 2f 2a 20 41 20 68 61 73 68 20        /* A hash 
1fa0: 6f 6e 20 6b 65 79 20 2a 2f 0a 20 20 48 61 73 68  on key */.  Hash
1fb0: 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 2f  Elem *elem;    /
1fc0: 2a 20 54 68 65 20 65 6c 65 6d 65 6e 74 20 74 68  * The element th
1fd0: 61 74 20 6d 61 74 63 68 65 73 20 6b 65 79 20 2a  at matches key *
1fe0: 2f 0a 20 20 69 6e 74 20 28 2a 78 48 61 73 68 29  /.  int (*xHash)
1ff0: 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74  (const void*,int
2000: 29 3b 20 20 2f 2a 20 54 68 65 20 68 61 73 68 20  );  /* The hash 
2010: 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20 69  function */..  i
2020: 66 28 20 70 48 3d 3d 30 20 7c 7c 20 70 48 2d 3e  f( pH==0 || pH->
2030: 68 74 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 30  ht==0 ) return 0
2040: 3b 0a 20 20 78 48 61 73 68 20 3d 20 68 61 73 68  ;.  xHash = hash
2050: 46 75 6e 63 74 69 6f 6e 28 70 48 2d 3e 6b 65 79  Function(pH->key
2060: 43 6c 61 73 73 29 3b 0a 20 20 61 73 73 65 72 74  Class);.  assert
2070: 28 20 78 48 61 73 68 21 3d 30 20 29 3b 0a 20 20  ( xHash!=0 );.  
2080: 68 20 3d 20 28 2a 78 48 61 73 68 29 28 70 4b 65  h = (*xHash)(pKe
2090: 79 2c 6e 4b 65 79 29 3b 0a 20 20 61 73 73 65 72  y,nKey);.  asser
20a0: 74 28 20 28 70 48 2d 3e 68 74 73 69 7a 65 20 26  t( (pH->htsize &
20b0: 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29 29   (pH->htsize-1))
20c0: 3d 3d 30 20 29 3b 0a 20 20 65 6c 65 6d 20 3d 20  ==0 );.  elem = 
20d0: 66 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65 6e  findElementGiven
20e0: 48 61 73 68 28 70 48 2c 70 4b 65 79 2c 6e 4b 65  Hash(pH,pKey,nKe
20f0: 79 2c 20 68 20 26 20 28 70 48 2d 3e 68 74 73 69  y, h & (pH->htsi
2100: 7a 65 2d 31 29 29 3b 0a 20 20 72 65 74 75 72 6e  ze-1));.  return
2110: 20 65 6c 65 6d 20 3f 20 65 6c 65 6d 2d 3e 64 61   elem ? elem->da
2120: 74 61 20 3a 20 30 3b 0a 7d 0a 0a 2f 2a 20 49 6e  ta : 0;.}../* In
2130: 73 65 72 74 20 61 6e 20 65 6c 65 6d 65 6e 74 20  sert an element 
2140: 69 6e 74 6f 20 74 68 65 20 68 61 73 68 20 74 61  into the hash ta
2150: 62 6c 65 20 70 48 2e 20 20 54 68 65 20 6b 65 79  ble pH.  The key
2160: 20 69 73 20 70 4b 65 79 2c 6e 4b 65 79 0a 2a 2a   is pKey,nKey.**
2170: 20 61 6e 64 20 74 68 65 20 64 61 74 61 20 69 73   and the data is
2180: 20 22 64 61 74 61 22 2e 0a 2a 2a 0a 2a 2a 20 49   "data"..**.** I
2190: 66 20 6e 6f 20 65 6c 65 6d 65 6e 74 20 65 78 69  f no element exi
21a0: 73 74 73 20 77 69 74 68 20 61 20 6d 61 74 63 68  sts with a match
21b0: 69 6e 67 20 6b 65 79 2c 20 74 68 65 6e 20 61 20  ing key, then a 
21c0: 6e 65 77 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 69  new.** element i
21d0: 73 20 63 72 65 61 74 65 64 2e 20 20 41 20 63 6f  s created.  A co
21e0: 70 79 20 6f 66 20 74 68 65 20 6b 65 79 20 69 73  py of the key is
21f0: 20 6d 61 64 65 20 69 66 20 74 68 65 20 63 6f 70   made if the cop
2200: 79 4b 65 79 0a 2a 2a 20 66 6c 61 67 20 69 73 20  yKey.** flag is 
2210: 73 65 74 2e 20 20 4e 55 4c 4c 20 69 73 20 72 65  set.  NULL is re
2220: 74 75 72 6e 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66  turned..**.** If
2230: 20 61 6e 6f 74 68 65 72 20 65 6c 65 6d 65 6e 74   another element
2240: 20 61 6c 72 65 61 64 79 20 65 78 69 73 74 73 20   already exists 
2250: 77 69 74 68 20 74 68 65 20 73 61 6d 65 20 6b 65  with the same ke
2260: 79 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20 6e  y, then the.** n
2270: 65 77 20 64 61 74 61 20 72 65 70 6c 61 63 65 73  ew data replaces
2280: 20 74 68 65 20 6f 6c 64 20 64 61 74 61 20 61 6e   the old data an
2290: 64 20 74 68 65 20 6f 6c 64 20 64 61 74 61 20 69  d the old data i
22a0: 73 20 72 65 74 75 72 6e 65 64 2e 0a 2a 2a 20 54  s returned..** T
22b0: 68 65 20 6b 65 79 20 69 73 20 6e 6f 74 20 63 6f  he key is not co
22c0: 70 69 65 64 20 69 6e 20 74 68 69 73 20 69 6e 73  pied in this ins
22d0: 74 61 6e 63 65 2e 20 20 49 66 20 61 20 6d 61 6c  tance.  If a mal
22e0: 6c 6f 63 20 66 61 69 6c 73 2c 20 74 68 65 6e 0a  loc fails, then.
22f0: 2a 2a 20 74 68 65 20 6e 65 77 20 64 61 74 61 20  ** the new data 
2300: 69 73 20 72 65 74 75 72 6e 65 64 20 61 6e 64 20  is returned and 
2310: 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 69  the hash table i
2320: 73 20 75 6e 63 68 61 6e 67 65 64 2e 0a 2a 2a 0a  s unchanged..**.
2330: 2a 2a 20 49 66 20 74 68 65 20 22 64 61 74 61 22  ** If the "data"
2340: 20 70 61 72 61 6d 65 74 65 72 20 74 6f 20 74 68   parameter to th
2350: 69 73 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 4e  is function is N
2360: 55 4c 4c 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a  ULL, then the.**
2370: 20 65 6c 65 6d 65 6e 74 20 63 6f 72 72 65 73 70   element corresp
2380: 6f 6e 64 69 6e 67 20 74 6f 20 22 6b 65 79 22 20  onding to "key" 
2390: 69 73 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20  is removed from 
23a0: 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 2e 0a  the hash table..
23b0: 2a 2f 0a 76 6f 69 64 20 2a 73 71 6c 69 74 65 48  */.void *sqliteH
23c0: 61 73 68 49 6e 73 65 72 74 28 48 61 73 68 20 2a  ashInsert(Hash *
23d0: 70 48 2c 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20  pH, void *pKey, 
23e0: 69 6e 74 20 6e 4b 65 79 2c 20 76 6f 69 64 20 2a  int nKey, void *
23f0: 64 61 74 61 29 7b 0a 20 20 69 6e 74 20 68 72 61  data){.  int hra
2400: 77 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 2f  w;             /
2410: 2a 20 52 61 77 20 68 61 73 68 20 76 61 6c 75 65  * Raw hash value
2420: 20 6f 66 20 74 68 65 20 6b 65 79 20 2a 2f 0a 20   of the key */. 
2430: 20 69 6e 74 20 68 3b 20 20 20 20 20 20 20 20 20   int h;         
2440: 20 20 20 20 20 20 20 2f 2a 20 74 68 65 20 68 61         /* the ha
2450: 73 68 20 6f 66 20 74 68 65 20 6b 65 79 20 6d 6f  sh of the key mo
2460: 64 75 6c 6f 20 68 61 73 68 20 74 61 62 6c 65 20  dulo hash table 
2470: 73 69 7a 65 20 2a 2f 0a 20 20 48 61 73 68 45 6c  size */.  HashEl
2480: 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 20 20 20  em *elem;       
2490: 2f 2a 20 55 73 65 64 20 74 6f 20 6c 6f 6f 70 20  /* Used to loop 
24a0: 74 68 72 75 20 74 68 65 20 65 6c 65 6d 65 6e 74  thru the element
24b0: 20 6c 69 73 74 20 2a 2f 0a 20 20 48 61 73 68 45   list */.  HashE
24c0: 6c 65 6d 20 2a 6e 65 77 5f 65 6c 65 6d 3b 20 20  lem *new_elem;  
24d0: 20 2f 2a 20 4e 65 77 20 65 6c 65 6d 65 6e 74 20   /* New element 
24e0: 61 64 64 65 64 20 74 6f 20 74 68 65 20 70 48 20  added to the pH 
24f0: 2a 2f 0a 20 20 69 6e 74 20 28 2a 78 48 61 73 68  */.  int (*xHash
2500: 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e  )(const void*,in
2510: 74 29 3b 20 20 2f 2a 20 54 68 65 20 68 61 73 68  t);  /* The hash
2520: 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20   function */..  
2530: 61 73 73 65 72 74 28 20 70 48 21 3d 30 20 29 3b  assert( pH!=0 );
2540: 0a 20 20 78 48 61 73 68 20 3d 20 68 61 73 68 46  .  xHash = hashF
2550: 75 6e 63 74 69 6f 6e 28 70 48 2d 3e 6b 65 79 43  unction(pH->keyC
2560: 6c 61 73 73 29 3b 0a 20 20 61 73 73 65 72 74 28  lass);.  assert(
2570: 20 78 48 61 73 68 21 3d 30 20 29 3b 0a 20 20 68   xHash!=0 );.  h
2580: 72 61 77 20 3d 20 28 2a 78 48 61 73 68 29 28 70  raw = (*xHash)(p
2590: 4b 65 79 2c 20 6e 4b 65 79 29 3b 0a 20 20 61 73  Key, nKey);.  as
25a0: 73 65 72 74 28 20 28 70 48 2d 3e 68 74 73 69 7a  sert( (pH->htsiz
25b0: 65 20 26 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d  e & (pH->htsize-
25c0: 31 29 29 3d 3d 30 20 29 3b 0a 20 20 68 20 3d 20  1))==0 );.  h = 
25d0: 68 72 61 77 20 26 20 28 70 48 2d 3e 68 74 73 69  hraw & (pH->htsi
25e0: 7a 65 2d 31 29 3b 0a 20 20 65 6c 65 6d 20 3d 20  ze-1);.  elem = 
25f0: 66 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65 6e  findElementGiven
2600: 48 61 73 68 28 70 48 2c 70 4b 65 79 2c 6e 4b 65  Hash(pH,pKey,nKe
2610: 79 2c 68 29 3b 0a 20 20 69 66 28 20 65 6c 65 6d  y,h);.  if( elem
2620: 20 29 7b 0a 20 20 20 20 76 6f 69 64 20 2a 6f 6c   ){.    void *ol
2630: 64 5f 64 61 74 61 20 3d 20 65 6c 65 6d 2d 3e 64  d_data = elem->d
2640: 61 74 61 3b 0a 20 20 20 20 69 66 28 20 64 61 74  ata;.    if( dat
2650: 61 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 72 65  a==0 ){.      re
2660: 6d 6f 76 65 45 6c 65 6d 65 6e 74 47 69 76 65 6e  moveElementGiven
2670: 48 61 73 68 28 70 48 2c 65 6c 65 6d 2c 68 29 3b  Hash(pH,elem,h);
2680: 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20  .    }else{.    
2690: 20 20 65 6c 65 6d 2d 3e 64 61 74 61 20 3d 20 64    elem->data = d
26a0: 61 74 61 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72  ata;.    }.    r
26b0: 65 74 75 72 6e 20 6f 6c 64 5f 64 61 74 61 3b 0a  eturn old_data;.
26c0: 20 20 7d 0a 20 20 69 66 28 20 64 61 74 61 3d 3d    }.  if( data==
26d0: 30 20 29 20 72 65 74 75 72 6e 20 30 3b 0a 20 20  0 ) return 0;.  
26e0: 6e 65 77 5f 65 6c 65 6d 20 3d 20 28 48 61 73 68  new_elem = (Hash
26f0: 45 6c 65 6d 2a 29 73 71 6c 69 74 65 4d 61 6c 6c  Elem*)sqliteMall
2700: 6f 63 28 20 73 69 7a 65 6f 66 28 48 61 73 68 45  oc( sizeof(HashE
2710: 6c 65 6d 29 20 29 3b 0a 20 20 69 66 28 20 6e 65  lem) );.  if( ne
2720: 77 5f 65 6c 65 6d 3d 3d 30 20 29 20 72 65 74 75  w_elem==0 ) retu
2730: 72 6e 20 64 61 74 61 3b 0a 20 20 69 66 28 20 70  rn data;.  if( p
2740: 48 2d 3e 63 6f 70 79 4b 65 79 20 26 26 20 70 4b  H->copyKey && pK
2750: 65 79 21 3d 30 20 29 7b 0a 20 20 20 20 6e 65 77  ey!=0 ){.    new
2760: 5f 65 6c 65 6d 2d 3e 70 4b 65 79 20 3d 20 73 71  _elem->pKey = sq
2770: 6c 69 74 65 4d 61 6c 6c 6f 63 28 20 6e 4b 65 79  liteMalloc( nKey
2780: 20 29 3b 0a 20 20 20 20 69 66 28 20 6e 65 77 5f   );.    if( new_
2790: 65 6c 65 6d 2d 3e 70 4b 65 79 3d 3d 30 20 29 7b  elem->pKey==0 ){
27a0: 0a 20 20 20 20 20 20 73 71 6c 69 74 65 46 72 65  .      sqliteFre
27b0: 65 28 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20 20 20  e(new_elem);.   
27c0: 20 20 20 72 65 74 75 72 6e 20 64 61 74 61 3b 0a     return data;.
27d0: 20 20 20 20 7d 0a 20 20 20 20 6d 65 6d 63 70 79      }.    memcpy
27e0: 28 28 76 6f 69 64 2a 29 6e 65 77 5f 65 6c 65 6d  ((void*)new_elem
27f0: 2d 3e 70 4b 65 79 2c 20 70 4b 65 79 2c 20 6e 4b  ->pKey, pKey, nK
2800: 65 79 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20  ey);.  }else{.  
2810: 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79    new_elem->pKey
2820: 20 3d 20 70 4b 65 79 3b 0a 20 20 7d 0a 20 20 6e   = pKey;.  }.  n
2830: 65 77 5f 65 6c 65 6d 2d 3e 6e 4b 65 79 20 3d 20  ew_elem->nKey = 
2840: 6e 4b 65 79 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e  nKey;.  pH->coun
2850: 74 2b 2b 3b 0a 20 20 69 66 28 20 70 48 2d 3e 68  t++;.  if( pH->h
2860: 74 73 69 7a 65 3d 3d 30 20 29 20 72 65 68 61 73  tsize==0 ) rehas
2870: 68 28 70 48 2c 38 29 3b 0a 20 20 69 66 28 20 70  h(pH,8);.  if( p
2880: 48 2d 3e 68 74 73 69 7a 65 3d 3d 30 20 29 7b 0a  H->htsize==0 ){.
2890: 20 20 20 20 70 48 2d 3e 63 6f 75 6e 74 20 3d 20      pH->count = 
28a0: 30 3b 0a 20 20 20 20 73 71 6c 69 74 65 46 72 65  0;.    sqliteFre
28b0: 65 28 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20 20 20  e(new_elem);.   
28c0: 20 72 65 74 75 72 6e 20 64 61 74 61 3b 0a 20 20   return data;.  
28d0: 7d 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f 75 6e  }.  if( pH->coun
28e0: 74 20 3e 20 70 48 2d 3e 68 74 73 69 7a 65 20 29  t > pH->htsize )
28f0: 7b 0a 20 20 20 20 72 65 68 61 73 68 28 70 48 2c  {.    rehash(pH,
2900: 70 48 2d 3e 68 74 73 69 7a 65 2a 32 29 3b 0a 20  pH->htsize*2);. 
2910: 20 7d 0a 20 20 61 73 73 65 72 74 28 20 28 70 48   }.  assert( (pH
2920: 2d 3e 68 74 73 69 7a 65 20 26 20 28 70 48 2d 3e  ->htsize & (pH->
2930: 68 74 73 69 7a 65 2d 31 29 29 3d 3d 30 20 29 3b  htsize-1))==0 );
2940: 0a 20 20 68 20 3d 20 68 72 61 77 20 26 20 28 70  .  h = hraw & (p
2950: 48 2d 3e 68 74 73 69 7a 65 2d 31 29 3b 0a 20 20  H->htsize-1);.  
2960: 65 6c 65 6d 20 3d 20 70 48 2d 3e 68 74 5b 68 5d  elem = pH->ht[h]
2970: 2e 63 68 61 69 6e 3b 0a 20 20 69 66 28 20 65 6c  .chain;.  if( el
2980: 65 6d 20 29 7b 0a 20 20 20 20 6e 65 77 5f 65 6c  em ){.    new_el
2990: 65 6d 2d 3e 6e 65 78 74 20 3d 20 65 6c 65 6d 3b  em->next = elem;
29a0: 0a 20 20 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70  .    new_elem->p
29b0: 72 65 76 20 3d 20 65 6c 65 6d 2d 3e 70 72 65 76  rev = elem->prev
29c0: 3b 0a 20 20 20 20 69 66 28 20 65 6c 65 6d 2d 3e  ;.    if( elem->
29d0: 70 72 65 76 20 29 7b 20 65 6c 65 6d 2d 3e 70 72  prev ){ elem->pr
29e0: 65 76 2d 3e 6e 65 78 74 20 3d 20 6e 65 77 5f 65  ev->next = new_e
29f0: 6c 65 6d 3b 20 7d 0a 20 20 20 20 65 6c 73 65 20  lem; }.    else 
2a00: 20 20 20 20 20 20 20 20 20 20 20 7b 20 70 48 2d             { pH-
2a10: 3e 66 69 72 73 74 20 3d 20 6e 65 77 5f 65 6c 65  >first = new_ele
2a20: 6d 3b 20 7d 0a 20 20 20 20 65 6c 65 6d 2d 3e 70  m; }.    elem->p
2a30: 72 65 76 20 3d 20 6e 65 77 5f 65 6c 65 6d 3b 0a  rev = new_elem;.
2a40: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 6e 65 77    }else{.    new
2a50: 5f 65 6c 65 6d 2d 3e 6e 65 78 74 20 3d 20 70 48  _elem->next = pH
2a60: 2d 3e 66 69 72 73 74 3b 0a 20 20 20 20 6e 65 77  ->first;.    new
2a70: 5f 65 6c 65 6d 2d 3e 70 72 65 76 20 3d 20 30 3b  _elem->prev = 0;
2a80: 0a 20 20 20 20 69 66 28 20 70 48 2d 3e 66 69 72  .    if( pH->fir
2a90: 73 74 20 29 7b 20 70 48 2d 3e 66 69 72 73 74 2d  st ){ pH->first-
2aa0: 3e 70 72 65 76 20 3d 20 6e 65 77 5f 65 6c 65 6d  >prev = new_elem
2ab0: 3b 20 7d 0a 20 20 20 20 70 48 2d 3e 66 69 72 73  ; }.    pH->firs
2ac0: 74 20 3d 20 6e 65 77 5f 65 6c 65 6d 3b 0a 20 20  t = new_elem;.  
2ad0: 7d 0a 20 20 70 48 2d 3e 68 74 5b 68 5d 2e 63 6f  }.  pH->ht[h].co
2ae0: 75 6e 74 2b 2b 3b 0a 20 20 70 48 2d 3e 68 74 5b  unt++;.  pH->ht[
2af0: 68 5d 2e 63 68 61 69 6e 20 3d 20 6e 65 77 5f 65  h].chain = new_e
2b00: 6c 65 6d 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d  lem;.  new_elem-
2b10: 3e 64 61 74 61 20 3d 20 64 61 74 61 3b 0a 20 20  >data = data;.  
2b20: 72 65 74 75 72 6e 20 30 3b 0a 7d 0a              return 0;.}.