/ Hex Artifact Content
Login

Artifact 148e3512f1b4e90f8477f852c70b36a137b116a7:


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 31 33 20 32 30 30 34 2f 30 36 2f  ,v 1.13 2004/06/
01e0: 33 30 20 30 33 3a 30 38 3a 32 35 20 64 72 68 20  30 03:08:25 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 6e 65  cture..**.** "ne
0290: 77 22 20 69 73 20 61 20 70 6f 69 6e 74 65 72 20  w" is a pointer 
02a0: 74 6f 20 74 68 65 20 68 61 73 68 20 74 61 62 6c  to the hash tabl
02b0: 65 20 74 68 61 74 20 69 73 20 74 6f 20 62 65 20  e that is to be 
02c0: 69 6e 69 74 69 61 6c 69 7a 65 64 2e 0a 2a 2a 20  initialized..** 
02d0: 6b 65 79 43 6c 61 73 73 20 69 73 20 6f 6e 65 20  keyClass is one 
02e0: 6f 66 20 74 68 65 20 63 6f 6e 73 74 61 6e 74 73  of the constants
02f0: 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 49 4e 54   SQLITE_HASH_INT
0300: 2c 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 50 4f  , SQLITE_HASH_PO
0310: 49 4e 54 45 52 2c 0a 2a 2a 20 53 51 4c 49 54 45  INTER,.** SQLITE
0320: 5f 48 41 53 48 5f 42 49 4e 41 52 59 2c 20 6f 72  _HASH_BINARY, or
0330: 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52   SQLITE_HASH_STR
0340: 49 4e 47 2e 20 20 54 68 65 20 76 61 6c 75 65 20  ING.  The value 
0350: 6f 66 20 6b 65 79 43 6c 61 73 73 20 0a 2a 2a 20  of keyClass .** 
0360: 64 65 74 65 72 6d 69 6e 65 73 20 77 68 61 74 20  determines what 
0370: 6b 69 6e 64 20 6f 66 20 6b 65 79 20 74 68 65 20  kind of key the 
0380: 68 61 73 68 20 74 61 62 6c 65 20 77 69 6c 6c 20  hash table will 
0390: 75 73 65 2e 20 20 22 63 6f 70 79 4b 65 79 22 20  use.  "copyKey" 
03a0: 69 73 0a 2a 2a 20 74 72 75 65 20 69 66 20 74 68  is.** true if th
03b0: 65 20 68 61 73 68 20 74 61 62 6c 65 20 73 68 6f  e hash table sho
03c0: 75 6c 64 20 6d 61 6b 65 20 69 74 73 20 6f 77 6e  uld make its own
03d0: 20 70 72 69 76 61 74 65 20 63 6f 70 79 20 6f 66   private copy of
03e0: 20 6b 65 79 73 20 61 6e 64 0a 2a 2a 20 66 61 6c   keys and.** fal
03f0: 73 65 20 69 66 20 69 74 20 73 68 6f 75 6c 64 20  se if it should 
0400: 6a 75 73 74 20 75 73 65 20 74 68 65 20 73 75 70  just use the sup
0410: 70 6c 69 65 64 20 70 6f 69 6e 74 65 72 2e 20 20  plied pointer.  
0420: 43 6f 70 79 4b 65 79 20 6f 6e 6c 79 20 6d 61 6b  CopyKey only mak
0430: 65 73 0a 2a 2a 20 73 65 6e 73 65 20 66 6f 72 20  es.** sense for 
0440: 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 49  SQLITE_HASH_STRI
0450: 4e 47 20 61 6e 64 20 53 51 4c 49 54 45 5f 48 41  NG and SQLITE_HA
0460: 53 48 5f 42 49 4e 41 52 59 20 61 6e 64 20 69 73  SH_BINARY and is
0470: 20 69 67 6e 6f 72 65 64 0a 2a 2a 20 66 6f 72 20   ignored.** for 
0480: 6f 74 68 65 72 20 6b 65 79 20 63 6c 61 73 73 65  other key classe
0490: 73 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74  s..*/.void sqlit
04a0: 65 33 48 61 73 68 49 6e 69 74 28 48 61 73 68 20  e3HashInit(Hash 
04b0: 2a 6e 65 77 2c 20 69 6e 74 20 6b 65 79 43 6c 61  *new, int keyCla
04c0: 73 73 2c 20 69 6e 74 20 63 6f 70 79 4b 65 79 29  ss, int copyKey)
04d0: 7b 0a 20 20 61 73 73 65 72 74 28 20 6e 65 77 21  {.  assert( new!
04e0: 3d 30 20 29 3b 0a 20 20 61 73 73 65 72 74 28 20  =0 );.  assert( 
04f0: 6b 65 79 43 6c 61 73 73 3e 3d 53 51 4c 49 54 45  keyClass>=SQLITE
0500: 5f 48 41 53 48 5f 49 4e 54 20 26 26 20 6b 65 79  _HASH_INT && key
0510: 43 6c 61 73 73 3c 3d 53 51 4c 49 54 45 5f 48 41  Class<=SQLITE_HA
0520: 53 48 5f 42 49 4e 41 52 59 20 29 3b 0a 20 20 6e  SH_BINARY );.  n
0530: 65 77 2d 3e 6b 65 79 43 6c 61 73 73 20 3d 20 6b  ew->keyClass = k
0540: 65 79 43 6c 61 73 73 3b 0a 20 20 6e 65 77 2d 3e  eyClass;.  new->
0550: 63 6f 70 79 4b 65 79 20 3d 20 63 6f 70 79 4b 65  copyKey = copyKe
0560: 79 20 26 26 0a 20 20 20 20 20 20 20 20 20 20 20  y &&.           
0570: 20 20 20 20 20 28 6b 65 79 43 6c 61 73 73 3d 3d       (keyClass==
0580: 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 49  SQLITE_HASH_STRI
0590: 4e 47 20 7c 7c 20 6b 65 79 43 6c 61 73 73 3d 3d  NG || keyClass==
05a0: 53 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e 41  SQLITE_HASH_BINA
05b0: 52 59 29 3b 0a 20 20 6e 65 77 2d 3e 66 69 72 73  RY);.  new->firs
05c0: 74 20 3d 20 30 3b 0a 20 20 6e 65 77 2d 3e 63 6f  t = 0;.  new->co
05d0: 75 6e 74 20 3d 20 30 3b 0a 20 20 6e 65 77 2d 3e  unt = 0;.  new->
05e0: 68 74 73 69 7a 65 20 3d 20 30 3b 0a 20 20 6e 65  htsize = 0;.  ne
05f0: 77 2d 3e 68 74 20 3d 20 30 3b 0a 7d 0a 0a 2f 2a  w->ht = 0;.}../*
0600: 20 52 65 6d 6f 76 65 20 61 6c 6c 20 65 6e 74 72   Remove all entr
0610: 69 65 73 20 66 72 6f 6d 20 61 20 68 61 73 68 20  ies from a hash 
0620: 74 61 62 6c 65 2e 20 20 52 65 63 6c 61 69 6d 20  table.  Reclaim 
0630: 61 6c 6c 20 6d 65 6d 6f 72 79 2e 0a 2a 2a 20 43  all memory..** C
0640: 61 6c 6c 20 74 68 69 73 20 72 6f 75 74 69 6e 65  all this routine
0650: 20 74 6f 20 64 65 6c 65 74 65 20 61 20 68 61 73   to delete a has
0660: 68 20 74 61 62 6c 65 20 6f 72 20 74 6f 20 72 65  h table or to re
0670: 73 65 74 20 61 20 68 61 73 68 20 74 61 62 6c 65  set a hash table
0680: 0a 2a 2a 20 74 6f 20 74 68 65 20 65 6d 70 74 79  .** to the empty
0690: 20 73 74 61 74 65 2e 0a 2a 2f 0a 76 6f 69 64 20   state..*/.void 
06a0: 73 71 6c 69 74 65 33 48 61 73 68 43 6c 65 61 72  sqlite3HashClear
06b0: 28 48 61 73 68 20 2a 70 48 29 7b 0a 20 20 48 61  (Hash *pH){.  Ha
06c0: 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20  shElem *elem;   
06d0: 20 20 20 20 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f        /* For loo
06e0: 70 69 6e 67 20 6f 76 65 72 20 61 6c 6c 20 65 6c  ping over all el
06f0: 65 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 74 61  ements of the ta
0700: 62 6c 65 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74  ble */..  assert
0710: 28 20 70 48 21 3d 30 20 29 3b 0a 20 20 65 6c 65  ( pH!=0 );.  ele
0720: 6d 20 3d 20 70 48 2d 3e 66 69 72 73 74 3b 0a 20  m = pH->first;. 
0730: 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 30 3b 0a   pH->first = 0;.
0740: 20 20 69 66 28 20 70 48 2d 3e 68 74 20 29 20 73    if( pH->ht ) s
0750: 71 6c 69 74 65 46 72 65 65 28 70 48 2d 3e 68 74  qliteFree(pH->ht
0760: 29 3b 0a 20 20 70 48 2d 3e 68 74 20 3d 20 30 3b  );.  pH->ht = 0;
0770: 0a 20 20 70 48 2d 3e 68 74 73 69 7a 65 20 3d 20  .  pH->htsize = 
0780: 30 3b 0a 20 20 77 68 69 6c 65 28 20 65 6c 65 6d  0;.  while( elem
0790: 20 29 7b 0a 20 20 20 20 48 61 73 68 45 6c 65 6d   ){.    HashElem
07a0: 20 2a 6e 65 78 74 5f 65 6c 65 6d 20 3d 20 65 6c   *next_elem = el
07b0: 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 69 66  em->next;.    if
07c0: 28 20 70 48 2d 3e 63 6f 70 79 4b 65 79 20 26 26  ( pH->copyKey &&
07d0: 20 65 6c 65 6d 2d 3e 70 4b 65 79 20 29 7b 0a 20   elem->pKey ){. 
07e0: 20 20 20 20 20 73 71 6c 69 74 65 46 72 65 65 28       sqliteFree(
07f0: 65 6c 65 6d 2d 3e 70 4b 65 79 29 3b 0a 20 20 20  elem->pKey);.   
0800: 20 7d 0a 20 20 20 20 73 71 6c 69 74 65 46 72 65   }.    sqliteFre
0810: 65 28 65 6c 65 6d 29 3b 0a 20 20 20 20 65 6c 65  e(elem);.    ele
0820: 6d 20 3d 20 6e 65 78 74 5f 65 6c 65 6d 3b 0a 20  m = next_elem;. 
0830: 20 7d 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 20 3d   }.  pH->count =
0840: 20 30 3b 0a 7d 0a 0a 23 69 66 20 30 20 2f 2a 20   0;.}..#if 0 /* 
0850: 4e 4f 54 20 55 53 45 44 20 2a 2f 0a 2f 2a 0a 2a  NOT USED */./*.*
0860: 2a 20 48 61 73 68 20 61 6e 64 20 63 6f 6d 70 61  * Hash and compa
0870: 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 20  rison functions 
0880: 77 68 65 6e 20 74 68 65 20 6d 6f 64 65 20 69 73  when the mode is
0890: 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 49 4e 54   SQLITE_HASH_INT
08a0: 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 69  .*/.static int i
08b0: 6e 74 48 61 73 68 28 63 6f 6e 73 74 20 76 6f 69  ntHash(const voi
08c0: 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65  d *pKey, int nKe
08d0: 79 29 7b 0a 20 20 72 65 74 75 72 6e 20 6e 4b 65  y){.  return nKe
08e0: 79 20 5e 20 28 6e 4b 65 79 3c 3c 38 29 20 5e 20  y ^ (nKey<<8) ^ 
08f0: 28 6e 4b 65 79 3e 3e 38 29 3b 0a 7d 0a 73 74 61  (nKey>>8);.}.sta
0900: 74 69 63 20 69 6e 74 20 69 6e 74 43 6f 6d 70 61  tic int intCompa
0910: 72 65 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70  re(const void *p
0920: 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c 20 63 6f  Key1, int n1, co
0930: 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 32 2c  nst void *pKey2,
0940: 20 69 6e 74 20 6e 32 29 7b 0a 20 20 72 65 74 75   int n2){.  retu
0950: 72 6e 20 6e 32 20 2d 20 6e 31 3b 0a 7d 0a 23 65  rn n2 - n1;.}.#e
0960: 6e 64 69 66 0a 0a 23 69 66 20 30 20 2f 2a 20 4e  ndif..#if 0 /* N
0970: 4f 54 20 55 53 45 44 20 2a 2f 0a 2f 2a 0a 2a 2a  OT USED */./*.**
0980: 20 48 61 73 68 20 61 6e 64 20 63 6f 6d 70 61 72   Hash and compar
0990: 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 20 77  ison functions w
09a0: 68 65 6e 20 74 68 65 20 6d 6f 64 65 20 69 73 20  hen the mode is 
09b0: 53 51 4c 49 54 45 5f 48 41 53 48 5f 50 4f 49 4e  SQLITE_HASH_POIN
09c0: 54 45 52 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e  TER.*/.static in
09d0: 74 20 70 74 72 48 61 73 68 28 63 6f 6e 73 74 20  t ptrHash(const 
09e0: 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20  void *pKey, int 
09f0: 6e 4b 65 79 29 7b 0a 20 20 75 70 74 72 20 78 20  nKey){.  uptr x 
0a00: 3d 20 41 64 64 72 28 70 4b 65 79 29 3b 0a 20 20  = Addr(pKey);.  
0a10: 72 65 74 75 72 6e 20 78 20 5e 20 28 78 3c 3c 38  return x ^ (x<<8
0a20: 29 20 5e 20 28 78 3e 3e 38 29 3b 0a 7d 0a 73 74  ) ^ (x>>8);.}.st
0a30: 61 74 69 63 20 69 6e 74 20 70 74 72 43 6f 6d 70  atic int ptrComp
0a40: 61 72 65 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a  are(const void *
0a50: 70 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c 20 63  pKey1, int n1, c
0a60: 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 32  onst void *pKey2
0a70: 2c 20 69 6e 74 20 6e 32 29 7b 0a 20 20 69 66 28  , int n2){.  if(
0a80: 20 70 4b 65 79 31 3d 3d 70 4b 65 79 32 20 29 20   pKey1==pKey2 ) 
0a90: 72 65 74 75 72 6e 20 30 3b 0a 20 20 69 66 28 20  return 0;.  if( 
0aa0: 70 4b 65 79 31 3c 70 4b 65 79 32 20 29 20 72 65  pKey1<pKey2 ) re
0ab0: 74 75 72 6e 20 2d 31 3b 0a 20 20 72 65 74 75 72  turn -1;.  retur
0ac0: 6e 20 31 3b 0a 7d 0a 23 65 6e 64 69 66 0a 0a 2f  n 1;.}.#endif../
0ad0: 2a 0a 2a 2a 20 48 61 73 68 20 61 6e 64 20 63 6f  *.** Hash and co
0ae0: 6d 70 61 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f  mparison functio
0af0: 6e 73 20 77 68 65 6e 20 74 68 65 20 6d 6f 64 65  ns when the mode
0b00: 20 69 73 20 53 51 4c 49 54 45 5f 48 41 53 48 5f   is SQLITE_HASH_
0b10: 53 54 52 49 4e 47 0a 2a 2f 0a 73 74 61 74 69 63  STRING.*/.static
0b20: 20 69 6e 74 20 73 74 72 48 61 73 68 28 63 6f 6e   int strHash(con
0b30: 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69  st void *pKey, i
0b40: 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 72 65 74 75  nt nKey){.  retu
0b50: 72 6e 20 73 71 6c 69 74 65 33 48 61 73 68 4e 6f  rn sqlite3HashNo
0b60: 43 61 73 65 28 28 63 6f 6e 73 74 20 63 68 61 72  Case((const char
0b70: 2a 29 70 4b 65 79 2c 20 6e 4b 65 79 29 3b 20 0a  *)pKey, nKey); .
0b80: 7d 0a 73 74 61 74 69 63 20 69 6e 74 20 73 74 72  }.static int str
0b90: 43 6f 6d 70 61 72 65 28 63 6f 6e 73 74 20 76 6f  Compare(const vo
0ba0: 69 64 20 2a 70 4b 65 79 31 2c 20 69 6e 74 20 6e  id *pKey1, int n
0bb0: 31 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70  1, const void *p
0bc0: 4b 65 79 32 2c 20 69 6e 74 20 6e 32 29 7b 0a 20  Key2, int n2){. 
0bd0: 20 69 66 28 20 6e 31 21 3d 6e 32 20 29 20 72 65   if( n1!=n2 ) re
0be0: 74 75 72 6e 20 6e 32 2d 6e 31 3b 0a 20 20 72 65  turn n2-n1;.  re
0bf0: 74 75 72 6e 20 73 71 6c 69 74 65 33 53 74 72 4e  turn sqlite3StrN
0c00: 49 43 6d 70 28 28 63 6f 6e 73 74 20 63 68 61 72  ICmp((const char
0c10: 2a 29 70 4b 65 79 31 2c 28 63 6f 6e 73 74 20 63  *)pKey1,(const c
0c20: 68 61 72 2a 29 70 4b 65 79 32 2c 6e 31 29 3b 0a  har*)pKey2,n1);.
0c30: 7d 0a 0a 2f 2a 0a 2a 2a 20 48 61 73 68 20 61 6e  }../*.** Hash an
0c40: 64 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75 6e  d comparison fun
0c50: 63 74 69 6f 6e 73 20 77 68 65 6e 20 74 68 65 20  ctions when the 
0c60: 6d 6f 64 65 20 69 73 20 53 51 4c 49 54 45 5f 48  mode is SQLITE_H
0c70: 41 53 48 5f 42 49 4e 41 52 59 0a 2a 2f 0a 73 74  ASH_BINARY.*/.st
0c80: 61 74 69 63 20 69 6e 74 20 62 69 6e 48 61 73 68  atic int binHash
0c90: 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65  (const void *pKe
0ca0: 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20 20  y, int nKey){.  
0cb0: 69 6e 74 20 68 20 3d 20 30 3b 0a 20 20 63 6f 6e  int h = 0;.  con
0cc0: 73 74 20 63 68 61 72 20 2a 7a 20 3d 20 28 63 6f  st char *z = (co
0cd0: 6e 73 74 20 63 68 61 72 20 2a 29 70 4b 65 79 3b  nst char *)pKey;
0ce0: 0a 20 20 77 68 69 6c 65 28 20 6e 4b 65 79 2d 2d  .  while( nKey--
0cf0: 20 3e 20 30 20 29 7b 0a 20 20 20 20 68 20 3d 20   > 0 ){.    h = 
0d00: 28 68 3c 3c 33 29 20 5e 20 68 20 5e 20 2a 28 7a  (h<<3) ^ h ^ *(z
0d10: 2b 2b 29 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72  ++);.  }.  retur
0d20: 6e 20 68 20 26 20 30 78 37 66 66 66 66 66 66 66  n h & 0x7fffffff
0d30: 3b 0a 7d 0a 73 74 61 74 69 63 20 69 6e 74 20 62  ;.}.static int b
0d40: 69 6e 43 6f 6d 70 61 72 65 28 63 6f 6e 73 74 20  inCompare(const 
0d50: 76 6f 69 64 20 2a 70 4b 65 79 31 2c 20 69 6e 74  void *pKey1, int
0d60: 20 6e 31 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20   n1, const void 
0d70: 2a 70 4b 65 79 32 2c 20 69 6e 74 20 6e 32 29 7b  *pKey2, int n2){
0d80: 0a 20 20 69 66 28 20 6e 31 21 3d 6e 32 20 29 20  .  if( n1!=n2 ) 
0d90: 72 65 74 75 72 6e 20 6e 32 2d 6e 31 3b 0a 20 20  return n2-n1;.  
0da0: 72 65 74 75 72 6e 20 6d 65 6d 63 6d 70 28 70 4b  return memcmp(pK
0db0: 65 79 31 2c 70 4b 65 79 32 2c 6e 31 29 3b 0a 7d  ey1,pKey2,n1);.}
0dc0: 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 61  ../*.** Return a
0dd0: 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 20   pointer to the 
0de0: 61 70 70 72 6f 70 72 69 61 74 65 20 68 61 73 68  appropriate hash
0df0: 20 66 75 6e 63 74 69 6f 6e 20 67 69 76 65 6e 20   function given 
0e00: 74 68 65 20 6b 65 79 20 63 6c 61 73 73 2e 0a 2a  the key class..*
0e10: 2a 0a 2a 2a 20 54 68 65 20 43 20 73 79 6e 74 61  *.** The C synta
0e20: 78 20 69 6e 20 74 68 69 73 20 66 75 6e 63 74 69  x in this functi
0e30: 6f 6e 20 64 65 66 69 6e 69 74 69 6f 6e 20 6d 61  on definition ma
0e40: 79 20 62 65 20 75 6e 66 61 6d 69 6c 61 72 20 74  y be unfamilar t
0e50: 6f 20 73 6f 6d 65 20 0a 2a 2a 20 70 72 6f 67 72  o some .** progr
0e60: 61 6d 6d 65 72 73 2c 20 73 6f 20 77 65 20 70 72  ammers, so we pr
0e70: 6f 76 69 64 65 20 74 68 65 20 66 6f 6c 6c 6f 77  ovide the follow
0e80: 69 6e 67 20 61 64 64 69 74 69 6f 6e 61 6c 20 65  ing additional e
0e90: 78 70 6c 61 6e 61 74 69 6f 6e 3a 0a 2a 2a 0a 2a  xplanation:.**.*
0ea0: 2a 20 54 68 65 20 6e 61 6d 65 20 6f 66 20 74 68  * The name of th
0eb0: 65 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 22 68  e function is "h
0ec0: 61 73 68 46 75 6e 63 74 69 6f 6e 22 2e 20 20 54  ashFunction".  T
0ed0: 68 65 20 66 75 6e 63 74 69 6f 6e 20 74 61 6b 65  he function take
0ee0: 73 20 61 0a 2a 2a 20 73 69 6e 67 6c 65 20 70 61  s a.** single pa
0ef0: 72 61 6d 65 74 65 72 20 22 6b 65 79 43 6c 61 73  rameter "keyClas
0f00: 73 22 2e 20 20 54 68 65 20 72 65 74 75 72 6e 20  s".  The return 
0f10: 76 61 6c 75 65 20 6f 66 20 68 61 73 68 46 75 6e  value of hashFun
0f20: 63 74 69 6f 6e 28 29 0a 2a 2a 20 69 73 20 61 20  ction().** is a 
0f30: 70 6f 69 6e 74 65 72 20 74 6f 20 61 6e 6f 74 68  pointer to anoth
0f40: 65 72 20 66 75 6e 63 74 69 6f 6e 2e 20 20 53 70  er function.  Sp
0f50: 65 63 69 66 69 63 61 6c 6c 79 2c 20 74 68 65 20  ecifically, the 
0f60: 72 65 74 75 72 6e 20 76 61 6c 75 65 0a 2a 2a 20  return value.** 
0f70: 6f 66 20 68 61 73 68 46 75 6e 63 74 69 6f 6e 28  of hashFunction(
0f80: 29 20 69 73 20 61 20 70 6f 69 6e 74 65 72 20 74  ) is a pointer t
0f90: 6f 20 61 20 66 75 6e 63 74 69 6f 6e 20 74 68 61  o a function tha
0fa0: 74 20 74 61 6b 65 73 20 74 77 6f 20 70 61 72 61  t takes two para
0fb0: 6d 65 74 65 72 73 0a 2a 2a 20 77 69 74 68 20 74  meters.** with t
0fc0: 79 70 65 73 20 22 63 6f 6e 73 74 20 76 6f 69 64  ypes "const void
0fd0: 2a 22 20 61 6e 64 20 22 69 6e 74 22 20 61 6e 64  *" and "int" and
0fe0: 20 72 65 74 75 72 6e 73 20 61 6e 20 22 69 6e 74   returns an "int
0ff0: 22 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74  "..*/.static int
1000: 20 28 2a 68 61 73 68 46 75 6e 63 74 69 6f 6e 28   (*hashFunction(
1010: 69 6e 74 20 6b 65 79 43 6c 61 73 73 29 29 28 63  int keyClass))(c
1020: 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29 7b  onst void*,int){
1030: 0a 20 20 73 77 69 74 63 68 28 20 6b 65 79 43 6c  .  switch( keyCl
1040: 61 73 73 20 29 7b 0a 20 20 20 20 2f 2a 20 63 61  ass ){.    /* ca
1050: 73 65 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 49  se SQLITE_HASH_I
1060: 4e 54 3a 20 20 20 20 20 72 65 74 75 72 6e 20 26  NT:     return &
1070: 69 6e 74 48 61 73 68 3b 20 2f 2f 20 4e 4f 54 20  intHash; // NOT 
1080: 55 53 45 44 20 2a 2f 0a 20 20 20 20 2f 2a 20 63  USED */.    /* c
1090: 61 73 65 20 53 51 4c 49 54 45 5f 48 41 53 48 5f  ase SQLITE_HASH_
10a0: 50 4f 49 4e 54 45 52 3a 20 72 65 74 75 72 6e 20  POINTER: return 
10b0: 26 70 74 72 48 61 73 68 3b 20 2f 2f 20 4e 4f 54  &ptrHash; // NOT
10c0: 20 55 53 45 44 20 2a 2f 0a 20 20 20 20 63 61 73   USED */.    cas
10d0: 65 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54  e SQLITE_HASH_ST
10e0: 52 49 4e 47 3a 20 20 72 65 74 75 72 6e 20 26 73  RING:  return &s
10f0: 74 72 48 61 73 68 3b 0a 20 20 20 20 63 61 73 65  trHash;.    case
1100: 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e   SQLITE_HASH_BIN
1110: 41 52 59 3a 20 20 72 65 74 75 72 6e 20 26 62 69  ARY:  return &bi
1120: 6e 48 61 73 68 3b 3b 0a 20 20 20 20 64 65 66 61  nHash;;.    defa
1130: 75 6c 74 3a 20 62 72 65 61 6b 3b 0a 20 20 7d 0a  ult: break;.  }.
1140: 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a 0a 2f    return 0;.}../
1150: 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 61 20 70 6f  *.** Return a po
1160: 69 6e 74 65 72 20 74 6f 20 74 68 65 20 61 70 70  inter to the app
1170: 72 6f 70 72 69 61 74 65 20 68 61 73 68 20 66 75  ropriate hash fu
1180: 6e 63 74 69 6f 6e 20 67 69 76 65 6e 20 74 68 65  nction given the
1190: 20 6b 65 79 20 63 6c 61 73 73 2e 0a 2a 2a 0a 2a   key class..**.*
11a0: 2a 20 46 6f 72 20 68 65 6c 70 20 69 6e 20 69 6e  * For help in in
11b0: 74 65 72 70 72 65 74 65 64 20 74 68 65 20 6f 62  terpreted the ob
11c0: 73 63 75 72 65 20 43 20 63 6f 64 65 20 69 6e 20  scure C code in 
11d0: 74 68 65 20 66 75 6e 63 74 69 6f 6e 20 64 65 66  the function def
11e0: 69 6e 69 74 69 6f 6e 2c 0a 2a 2a 20 73 65 65 20  inition,.** see 
11f0: 74 68 65 20 68 65 61 64 65 72 20 63 6f 6d 6d 65  the header comme
1200: 6e 74 20 6f 6e 20 74 68 65 20 70 72 65 76 69 6f  nt on the previo
1210: 75 73 20 66 75 6e 63 74 69 6f 6e 2e 0a 2a 2f 0a  us function..*/.
1220: 73 74 61 74 69 63 20 69 6e 74 20 28 2a 63 6f 6d  static int (*com
1230: 70 61 72 65 46 75 6e 63 74 69 6f 6e 28 69 6e 74  pareFunction(int
1240: 20 6b 65 79 43 6c 61 73 73 29 29 28 63 6f 6e 73   keyClass))(cons
1250: 74 20 76 6f 69 64 2a 2c 69 6e 74 2c 63 6f 6e 73  t void*,int,cons
1260: 74 20 76 6f 69 64 2a 2c 69 6e 74 29 7b 0a 20 20  t void*,int){.  
1270: 73 77 69 74 63 68 28 20 6b 65 79 43 6c 61 73 73  switch( keyClass
1280: 20 29 7b 0a 20 20 20 20 2f 2a 20 63 61 73 65 20   ){.    /* case 
1290: 53 51 4c 49 54 45 5f 48 41 53 48 5f 49 4e 54 3a  SQLITE_HASH_INT:
12a0: 20 20 20 20 20 72 65 74 75 72 6e 20 26 69 6e 74       return &int
12b0: 43 6f 6d 70 61 72 65 3b 20 2f 2f 20 4e 4f 54 20  Compare; // NOT 
12c0: 55 53 45 44 20 2a 2f 0a 20 20 20 20 2f 2a 20 63  USED */.    /* c
12d0: 61 73 65 20 53 51 4c 49 54 45 5f 48 41 53 48 5f  ase SQLITE_HASH_
12e0: 50 4f 49 4e 54 45 52 3a 20 72 65 74 75 72 6e 20  POINTER: return 
12f0: 26 70 74 72 43 6f 6d 70 61 72 65 3b 20 2f 2f 20  &ptrCompare; // 
1300: 4e 4f 54 20 55 53 45 44 20 2a 2f 0a 20 20 20 20  NOT USED */.    
1310: 63 61 73 65 20 53 51 4c 49 54 45 5f 48 41 53 48  case SQLITE_HASH
1320: 5f 53 54 52 49 4e 47 3a 20 20 72 65 74 75 72 6e  _STRING:  return
1330: 20 26 73 74 72 43 6f 6d 70 61 72 65 3b 0a 20 20   &strCompare;.  
1340: 20 20 63 61 73 65 20 53 51 4c 49 54 45 5f 48 41    case SQLITE_HA
1350: 53 48 5f 42 49 4e 41 52 59 3a 20 20 72 65 74 75  SH_BINARY:  retu
1360: 72 6e 20 26 62 69 6e 43 6f 6d 70 61 72 65 3b 0a  rn &binCompare;.
1370: 20 20 20 20 64 65 66 61 75 6c 74 3a 20 62 72 65      default: bre
1380: 61 6b 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e  ak;.  }.  return
1390: 20 30 3b 0a 7d 0a 0a 0a 2f 2a 20 52 65 73 69 7a   0;.}.../* Resiz
13a0: 65 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65  e the hash table
13b0: 20 73 6f 20 74 68 61 74 20 69 74 20 63 61 6e 74   so that it cant
13c0: 61 69 6e 73 20 22 6e 65 77 5f 73 69 7a 65 22 20  ains "new_size" 
13d0: 62 75 63 6b 65 74 73 2e 0a 2a 2a 20 22 6e 65 77  buckets..** "new
13e0: 5f 73 69 7a 65 22 20 6d 75 73 74 20 62 65 20 61  _size" must be a
13f0: 20 70 6f 77 65 72 20 6f 66 20 32 2e 20 20 54 68   power of 2.  Th
1400: 65 20 68 61 73 68 20 74 61 62 6c 65 20 6d 69 67  e hash table mig
1410: 68 74 20 66 61 69 6c 20 0a 2a 2a 20 74 6f 20 72  ht fail .** to r
1420: 65 73 69 7a 65 20 69 66 20 73 71 6c 69 74 65 4d  esize if sqliteM
1430: 61 6c 6c 6f 63 28 29 20 66 61 69 6c 73 2e 0a 2a  alloc() fails..*
1440: 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 72 65  /.static void re
1450: 68 61 73 68 28 48 61 73 68 20 2a 70 48 2c 20 69  hash(Hash *pH, i
1460: 6e 74 20 6e 65 77 5f 73 69 7a 65 29 7b 0a 20 20  nt new_size){.  
1470: 73 74 72 75 63 74 20 5f 68 74 20 2a 6e 65 77 5f  struct _ht *new_
1480: 68 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f  ht;            /
1490: 2a 20 54 68 65 20 6e 65 77 20 68 61 73 68 20 74  * The new hash t
14a0: 61 62 6c 65 20 2a 2f 0a 20 20 48 61 73 68 45 6c  able */.  HashEl
14b0: 65 6d 20 2a 65 6c 65 6d 2c 20 2a 6e 65 78 74 5f  em *elem, *next_
14c0: 65 6c 65 6d 3b 20 20 20 20 2f 2a 20 46 6f 72 20  elem;    /* For 
14d0: 6c 6f 6f 70 69 6e 67 20 6f 76 65 72 20 65 78 69  looping over exi
14e0: 73 74 69 6e 67 20 65 6c 65 6d 65 6e 74 73 20 2a  sting elements *
14f0: 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 78 3b  /.  HashElem *x;
1500: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1510: 20 20 20 2f 2a 20 45 6c 65 6d 65 6e 74 20 62 65     /* Element be
1520: 69 6e 67 20 63 6f 70 69 65 64 20 74 6f 20 6e 65  ing copied to ne
1530: 77 20 68 61 73 68 20 74 61 62 6c 65 20 2a 2f 0a  w hash table */.
1540: 20 20 69 6e 74 20 28 2a 78 48 61 73 68 29 28 63    int (*xHash)(c
1550: 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29 3b  onst void*,int);
1560: 20 2f 2a 20 54 68 65 20 68 61 73 68 20 66 75 6e   /* The hash fun
1570: 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20 61 73 73 65  ction */..  asse
1580: 72 74 28 20 28 6e 65 77 5f 73 69 7a 65 20 26 20  rt( (new_size & 
1590: 28 6e 65 77 5f 73 69 7a 65 2d 31 29 29 3d 3d 30  (new_size-1))==0
15a0: 20 29 3b 0a 20 20 6e 65 77 5f 68 74 20 3d 20 28   );.  new_ht = (
15b0: 73 74 72 75 63 74 20 5f 68 74 20 2a 29 73 71 6c  struct _ht *)sql
15c0: 69 74 65 4d 61 6c 6c 6f 63 28 20 6e 65 77 5f 73  iteMalloc( new_s
15d0: 69 7a 65 2a 73 69 7a 65 6f 66 28 73 74 72 75 63  ize*sizeof(struc
15e0: 74 20 5f 68 74 29 20 29 3b 0a 20 20 69 66 28 20  t _ht) );.  if( 
15f0: 6e 65 77 5f 68 74 3d 3d 30 20 29 20 72 65 74 75  new_ht==0 ) retu
1600: 72 6e 3b 0a 20 20 69 66 28 20 70 48 2d 3e 68 74  rn;.  if( pH->ht
1610: 20 29 20 73 71 6c 69 74 65 46 72 65 65 28 70 48   ) sqliteFree(pH
1620: 2d 3e 68 74 29 3b 0a 20 20 70 48 2d 3e 68 74 20  ->ht);.  pH->ht 
1630: 3d 20 6e 65 77 5f 68 74 3b 0a 20 20 70 48 2d 3e  = new_ht;.  pH->
1640: 68 74 73 69 7a 65 20 3d 20 6e 65 77 5f 73 69 7a  htsize = new_siz
1650: 65 3b 0a 20 20 78 48 61 73 68 20 3d 20 68 61 73  e;.  xHash = has
1660: 68 46 75 6e 63 74 69 6f 6e 28 70 48 2d 3e 6b 65  hFunction(pH->ke
1670: 79 43 6c 61 73 73 29 3b 0a 20 20 66 6f 72 28 65  yClass);.  for(e
1680: 6c 65 6d 3d 70 48 2d 3e 66 69 72 73 74 2c 20 70  lem=pH->first, p
1690: 48 2d 3e 66 69 72 73 74 3d 30 3b 20 65 6c 65 6d  H->first=0; elem
16a0: 3b 20 65 6c 65 6d 20 3d 20 6e 65 78 74 5f 65 6c  ; elem = next_el
16b0: 65 6d 29 7b 0a 20 20 20 20 69 6e 74 20 68 20 3d  em){.    int h =
16c0: 20 28 2a 78 48 61 73 68 29 28 65 6c 65 6d 2d 3e   (*xHash)(elem->
16d0: 70 4b 65 79 2c 20 65 6c 65 6d 2d 3e 6e 4b 65 79  pKey, elem->nKey
16e0: 29 20 26 20 28 6e 65 77 5f 73 69 7a 65 2d 31 29  ) & (new_size-1)
16f0: 3b 0a 20 20 20 20 6e 65 78 74 5f 65 6c 65 6d 20  ;.    next_elem 
1700: 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20  = elem->next;.  
1710: 20 20 78 20 3d 20 6e 65 77 5f 68 74 5b 68 5d 2e    x = new_ht[h].
1720: 63 68 61 69 6e 3b 0a 20 20 20 20 69 66 28 20 78  chain;.    if( x
1730: 20 29 7b 0a 20 20 20 20 20 20 65 6c 65 6d 2d 3e   ){.      elem->
1740: 6e 65 78 74 20 3d 20 78 3b 0a 20 20 20 20 20 20  next = x;.      
1750: 65 6c 65 6d 2d 3e 70 72 65 76 20 3d 20 78 2d 3e  elem->prev = x->
1760: 70 72 65 76 3b 0a 20 20 20 20 20 20 69 66 28 20  prev;.      if( 
1770: 78 2d 3e 70 72 65 76 20 29 20 78 2d 3e 70 72 65  x->prev ) x->pre
1780: 76 2d 3e 6e 65 78 74 20 3d 20 65 6c 65 6d 3b 0a  v->next = elem;.
1790: 20 20 20 20 20 20 65 6c 73 65 20 20 20 20 20 20        else      
17a0: 20 20 20 20 70 48 2d 3e 66 69 72 73 74 20 3d 20      pH->first = 
17b0: 65 6c 65 6d 3b 0a 20 20 20 20 20 20 78 2d 3e 70  elem;.      x->p
17c0: 72 65 76 20 3d 20 65 6c 65 6d 3b 0a 20 20 20 20  rev = elem;.    
17d0: 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 65 6c 65  }else{.      ele
17e0: 6d 2d 3e 6e 65 78 74 20 3d 20 70 48 2d 3e 66 69  m->next = pH->fi
17f0: 72 73 74 3b 0a 20 20 20 20 20 20 69 66 28 20 70  rst;.      if( p
1800: 48 2d 3e 66 69 72 73 74 20 29 20 70 48 2d 3e 66  H->first ) pH->f
1810: 69 72 73 74 2d 3e 70 72 65 76 20 3d 20 65 6c 65  irst->prev = ele
1820: 6d 3b 0a 20 20 20 20 20 20 65 6c 65 6d 2d 3e 70  m;.      elem->p
1830: 72 65 76 20 3d 20 30 3b 0a 20 20 20 20 20 20 70  rev = 0;.      p
1840: 48 2d 3e 66 69 72 73 74 20 3d 20 65 6c 65 6d 3b  H->first = elem;
1850: 0a 20 20 20 20 7d 0a 20 20 20 20 6e 65 77 5f 68  .    }.    new_h
1860: 74 5b 68 5d 2e 63 68 61 69 6e 20 3d 20 65 6c 65  t[h].chain = ele
1870: 6d 3b 0a 20 20 20 20 6e 65 77 5f 68 74 5b 68 5d  m;.    new_ht[h]
1880: 2e 63 6f 75 6e 74 2b 2b 3b 0a 20 20 7d 0a 7d 0a  .count++;.  }.}.
1890: 0a 2f 2a 20 54 68 69 73 20 66 75 6e 63 74 69 6f  ./* This functio
18a0: 6e 20 28 66 6f 72 20 69 6e 74 65 72 6e 61 6c 20  n (for internal 
18b0: 75 73 65 20 6f 6e 6c 79 29 20 6c 6f 63 61 74 65  use only) locate
18c0: 73 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69 6e 20  s an element in 
18d0: 61 6e 0a 2a 2a 20 68 61 73 68 20 74 61 62 6c 65  an.** hash table
18e0: 20 74 68 61 74 20 6d 61 74 63 68 65 73 20 74 68   that matches th
18f0: 65 20 67 69 76 65 6e 20 6b 65 79 2e 20 20 54 68  e given key.  Th
1900: 65 20 68 61 73 68 20 66 6f 72 20 74 68 69 73 20  e hash for this 
1910: 6b 65 79 20 68 61 73 0a 2a 2a 20 61 6c 72 65 61  key has.** alrea
1920: 64 79 20 62 65 65 6e 20 63 6f 6d 70 75 74 65 64  dy been computed
1930: 20 61 6e 64 20 69 73 20 70 61 73 73 65 64 20 61   and is passed a
1940: 73 20 74 68 65 20 34 74 68 20 70 61 72 61 6d 65  s the 4th parame
1950: 74 65 72 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 48  ter..*/.static H
1960: 61 73 68 45 6c 65 6d 20 2a 66 69 6e 64 45 6c 65  ashElem *findEle
1970: 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28 0a 20  mentGivenHash(. 
1980: 20 63 6f 6e 73 74 20 48 61 73 68 20 2a 70 48 2c   const Hash *pH,
1990: 20 20 20 20 20 2f 2a 20 54 68 65 20 70 48 20 74       /* The pH t
19a0: 6f 20 62 65 20 73 65 61 72 63 68 65 64 20 2a 2f  o be searched */
19b0: 0a 20 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70  .  const void *p
19c0: 4b 65 79 2c 20 20 20 2f 2a 20 54 68 65 20 6b 65  Key,   /* The ke
19d0: 79 20 77 65 20 61 72 65 20 73 65 61 72 63 68 69  y we are searchi
19e0: 6e 67 20 66 6f 72 20 2a 2f 0a 20 20 69 6e 74 20  ng for */.  int 
19f0: 6e 4b 65 79 2c 0a 20 20 69 6e 74 20 68 20 20 20  nKey,.  int h   
1a00: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54              /* T
1a10: 68 65 20 68 61 73 68 20 66 6f 72 20 74 68 69 73  he hash for this
1a20: 20 6b 65 79 2e 20 2a 2f 0a 29 7b 0a 20 20 48 61   key. */.){.  Ha
1a30: 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20  shElem *elem;   
1a40: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
1a50: 55 73 65 64 20 74 6f 20 6c 6f 6f 70 20 74 68 72  Used to loop thr
1a60: 75 20 74 68 65 20 65 6c 65 6d 65 6e 74 20 6c 69  u the element li
1a70: 73 74 20 2a 2f 0a 20 20 69 6e 74 20 63 6f 75 6e  st */.  int coun
1a80: 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  t;              
1a90: 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72         /* Number
1aa0: 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20 6c 65 66   of elements lef
1ab0: 74 20 74 6f 20 74 65 73 74 20 2a 2f 0a 20 20 69  t to test */.  i
1ac0: 6e 74 20 28 2a 78 43 6f 6d 70 61 72 65 29 28 63  nt (*xCompare)(c
1ad0: 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 2c 63  onst void*,int,c
1ae0: 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29 3b  onst void*,int);
1af0: 20 20 2f 2a 20 63 6f 6d 70 61 72 69 73 6f 6e 20    /* comparison 
1b00: 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20 69  function */..  i
1b10: 66 28 20 70 48 2d 3e 68 74 20 29 7b 0a 20 20 20  f( pH->ht ){.   
1b20: 20 65 6c 65 6d 20 3d 20 70 48 2d 3e 68 74 5b 68   elem = pH->ht[h
1b30: 5d 2e 63 68 61 69 6e 3b 0a 20 20 20 20 63 6f 75  ].chain;.    cou
1b40: 6e 74 20 3d 20 70 48 2d 3e 68 74 5b 68 5d 2e 63  nt = pH->ht[h].c
1b50: 6f 75 6e 74 3b 0a 20 20 20 20 78 43 6f 6d 70 61  ount;.    xCompa
1b60: 72 65 20 3d 20 63 6f 6d 70 61 72 65 46 75 6e 63  re = compareFunc
1b70: 74 69 6f 6e 28 70 48 2d 3e 6b 65 79 43 6c 61 73  tion(pH->keyClas
1b80: 73 29 3b 0a 20 20 20 20 77 68 69 6c 65 28 20 63  s);.    while( c
1b90: 6f 75 6e 74 2d 2d 20 26 26 20 65 6c 65 6d 20 29  ount-- && elem )
1ba0: 7b 0a 20 20 20 20 20 20 69 66 28 20 28 2a 78 43  {.      if( (*xC
1bb0: 6f 6d 70 61 72 65 29 28 65 6c 65 6d 2d 3e 70 4b  ompare)(elem->pK
1bc0: 65 79 2c 65 6c 65 6d 2d 3e 6e 4b 65 79 2c 70 4b  ey,elem->nKey,pK
1bd0: 65 79 2c 6e 4b 65 79 29 3d 3d 30 20 29 7b 20 0a  ey,nKey)==0 ){ .
1be0: 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 65          return e
1bf0: 6c 65 6d 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20  lem;.      }.   
1c00: 20 20 20 65 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e     elem = elem->
1c10: 6e 65 78 74 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a  next;.    }.  }.
1c20: 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a 0a 2f    return 0;.}../
1c30: 2a 20 52 65 6d 6f 76 65 20 61 20 73 69 6e 67 6c  * Remove a singl
1c40: 65 20 65 6e 74 72 79 20 66 72 6f 6d 20 74 68 65  e entry from the
1c50: 20 68 61 73 68 20 74 61 62 6c 65 20 67 69 76 65   hash table give
1c60: 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74  n a pointer to t
1c70: 68 61 74 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 61  hat.** element a
1c80: 6e 64 20 61 20 68 61 73 68 20 6f 6e 20 74 68 65  nd a hash on the
1c90: 20 65 6c 65 6d 65 6e 74 27 73 20 6b 65 79 2e 0a   element's key..
1ca0: 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 72  */.static void r
1cb0: 65 6d 6f 76 65 45 6c 65 6d 65 6e 74 47 69 76 65  emoveElementGive
1cc0: 6e 48 61 73 68 28 0a 20 20 48 61 73 68 20 2a 70  nHash(.  Hash *p
1cd0: 48 2c 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68  H,         /* Th
1ce0: 65 20 70 48 20 63 6f 6e 74 61 69 6e 69 6e 67 20  e pH containing 
1cf0: 22 65 6c 65 6d 22 20 2a 2f 0a 20 20 48 61 73 68  "elem" */.  Hash
1d00: 45 6c 65 6d 2a 20 65 6c 65 6d 2c 20 20 20 2f 2a  Elem* elem,   /*
1d10: 20 54 68 65 20 65 6c 65 6d 65 6e 74 20 74 6f 20   The element to 
1d20: 62 65 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20  be removed from 
1d30: 74 68 65 20 70 48 20 2a 2f 0a 20 20 69 6e 74 20  the pH */.  int 
1d40: 68 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  h             /*
1d50: 20 48 61 73 68 20 76 61 6c 75 65 20 66 6f 72 20   Hash value for 
1d60: 74 68 65 20 65 6c 65 6d 65 6e 74 20 2a 2f 0a 29  the element */.)
1d70: 7b 0a 20 20 69 66 28 20 65 6c 65 6d 2d 3e 70 72  {.  if( elem->pr
1d80: 65 76 20 29 7b 0a 20 20 20 20 65 6c 65 6d 2d 3e  ev ){.    elem->
1d90: 70 72 65 76 2d 3e 6e 65 78 74 20 3d 20 65 6c 65  prev->next = ele
1da0: 6d 2d 3e 6e 65 78 74 3b 20 0a 20 20 7d 65 6c 73  m->next; .  }els
1db0: 65 7b 0a 20 20 20 20 70 48 2d 3e 66 69 72 73 74  e{.    pH->first
1dc0: 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20   = elem->next;. 
1dd0: 20 7d 0a 20 20 69 66 28 20 65 6c 65 6d 2d 3e 6e   }.  if( elem->n
1de0: 65 78 74 20 29 7b 0a 20 20 20 20 65 6c 65 6d 2d  ext ){.    elem-
1df0: 3e 6e 65 78 74 2d 3e 70 72 65 76 20 3d 20 65 6c  >next->prev = el
1e00: 65 6d 2d 3e 70 72 65 76 3b 0a 20 20 7d 0a 20 20  em->prev;.  }.  
1e10: 69 66 28 20 70 48 2d 3e 68 74 5b 68 5d 2e 63 68  if( pH->ht[h].ch
1e20: 61 69 6e 3d 3d 65 6c 65 6d 20 29 7b 0a 20 20 20  ain==elem ){.   
1e30: 20 70 48 2d 3e 68 74 5b 68 5d 2e 63 68 61 69 6e   pH->ht[h].chain
1e40: 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20   = elem->next;. 
1e50: 20 7d 0a 20 20 70 48 2d 3e 68 74 5b 68 5d 2e 63   }.  pH->ht[h].c
1e60: 6f 75 6e 74 2d 2d 3b 0a 20 20 69 66 28 20 70 48  ount--;.  if( pH
1e70: 2d 3e 68 74 5b 68 5d 2e 63 6f 75 6e 74 3c 3d 30  ->ht[h].count<=0
1e80: 20 29 7b 0a 20 20 20 20 70 48 2d 3e 68 74 5b 68   ){.    pH->ht[h
1e90: 5d 2e 63 68 61 69 6e 20 3d 20 30 3b 0a 20 20 7d  ].chain = 0;.  }
1ea0: 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f 70 79 4b  .  if( pH->copyK
1eb0: 65 79 20 26 26 20 65 6c 65 6d 2d 3e 70 4b 65 79  ey && elem->pKey
1ec0: 20 29 7b 0a 20 20 20 20 73 71 6c 69 74 65 46 72   ){.    sqliteFr
1ed0: 65 65 28 65 6c 65 6d 2d 3e 70 4b 65 79 29 3b 0a  ee(elem->pKey);.
1ee0: 20 20 7d 0a 20 20 73 71 6c 69 74 65 46 72 65 65    }.  sqliteFree
1ef0: 28 20 65 6c 65 6d 20 29 3b 0a 20 20 70 48 2d 3e  ( elem );.  pH->
1f00: 63 6f 75 6e 74 2d 2d 3b 0a 7d 0a 0a 2f 2a 20 41  count--;.}../* A
1f10: 74 74 65 6d 70 74 20 74 6f 20 6c 6f 63 61 74 65  ttempt to locate
1f20: 20 61 6e 20 65 6c 65 6d 65 6e 74 20 6f 66 20 74   an element of t
1f30: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 70 48  he hash table pH
1f40: 20 77 69 74 68 20 61 20 6b 65 79 0a 2a 2a 20 74   with a key.** t
1f50: 68 61 74 20 6d 61 74 63 68 65 73 20 70 4b 65 79  hat matches pKey
1f60: 2c 6e 4b 65 79 2e 20 20 52 65 74 75 72 6e 20 74  ,nKey.  Return t
1f70: 68 65 20 64 61 74 61 20 66 6f 72 20 74 68 69 73  he data for this
1f80: 20 65 6c 65 6d 65 6e 74 20 69 66 20 69 74 20 69   element if it i
1f90: 73 0a 2a 2a 20 66 6f 75 6e 64 2c 20 6f 72 20 4e  s.** found, or N
1fa0: 55 4c 4c 20 69 66 20 74 68 65 72 65 20 69 73 20  ULL if there is 
1fb0: 6e 6f 20 6d 61 74 63 68 2e 0a 2a 2f 0a 76 6f 69  no match..*/.voi
1fc0: 64 20 2a 73 71 6c 69 74 65 33 48 61 73 68 46 69  d *sqlite3HashFi
1fd0: 6e 64 28 63 6f 6e 73 74 20 48 61 73 68 20 2a 70  nd(const Hash *p
1fe0: 48 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70  H, const void *p
1ff0: 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a  Key, int nKey){.
2000: 20 20 69 6e 74 20 68 3b 20 20 20 20 20 20 20 20    int h;        
2010: 20 20 20 20 20 2f 2a 20 41 20 68 61 73 68 20 6f       /* A hash o
2020: 6e 20 6b 65 79 20 2a 2f 0a 20 20 48 61 73 68 45  n key */.  HashE
2030: 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 2f 2a  lem *elem;    /*
2040: 20 54 68 65 20 65 6c 65 6d 65 6e 74 20 74 68 61   The element tha
2050: 74 20 6d 61 74 63 68 65 73 20 6b 65 79 20 2a 2f  t matches key */
2060: 0a 20 20 69 6e 74 20 28 2a 78 48 61 73 68 29 28  .  int (*xHash)(
2070: 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29  const void*,int)
2080: 3b 20 20 2f 2a 20 54 68 65 20 68 61 73 68 20 66  ;  /* The hash f
2090: 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20 69 66  unction */..  if
20a0: 28 20 70 48 3d 3d 30 20 7c 7c 20 70 48 2d 3e 68  ( pH==0 || pH->h
20b0: 74 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 30 3b  t==0 ) return 0;
20c0: 0a 20 20 78 48 61 73 68 20 3d 20 68 61 73 68 46  .  xHash = hashF
20d0: 75 6e 63 74 69 6f 6e 28 70 48 2d 3e 6b 65 79 43  unction(pH->keyC
20e0: 6c 61 73 73 29 3b 0a 20 20 61 73 73 65 72 74 28  lass);.  assert(
20f0: 20 78 48 61 73 68 21 3d 30 20 29 3b 0a 20 20 68   xHash!=0 );.  h
2100: 20 3d 20 28 2a 78 48 61 73 68 29 28 70 4b 65 79   = (*xHash)(pKey
2110: 2c 6e 4b 65 79 29 3b 0a 20 20 61 73 73 65 72 74  ,nKey);.  assert
2120: 28 20 28 70 48 2d 3e 68 74 73 69 7a 65 20 26 20  ( (pH->htsize & 
2130: 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29 29 3d  (pH->htsize-1))=
2140: 3d 30 20 29 3b 0a 20 20 65 6c 65 6d 20 3d 20 66  =0 );.  elem = f
2150: 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48  indElementGivenH
2160: 61 73 68 28 70 48 2c 70 4b 65 79 2c 6e 4b 65 79  ash(pH,pKey,nKey
2170: 2c 20 68 20 26 20 28 70 48 2d 3e 68 74 73 69 7a  , h & (pH->htsiz
2180: 65 2d 31 29 29 3b 0a 20 20 72 65 74 75 72 6e 20  e-1));.  return 
2190: 65 6c 65 6d 20 3f 20 65 6c 65 6d 2d 3e 64 61 74  elem ? elem->dat
21a0: 61 20 3a 20 30 3b 0a 7d 0a 0a 2f 2a 20 49 6e 73  a : 0;.}../* Ins
21b0: 65 72 74 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69  ert an element i
21c0: 6e 74 6f 20 74 68 65 20 68 61 73 68 20 74 61 62  nto the hash tab
21d0: 6c 65 20 70 48 2e 20 20 54 68 65 20 6b 65 79 20  le pH.  The key 
21e0: 69 73 20 70 4b 65 79 2c 6e 4b 65 79 0a 2a 2a 20  is pKey,nKey.** 
21f0: 61 6e 64 20 74 68 65 20 64 61 74 61 20 69 73 20  and the data is 
2200: 22 64 61 74 61 22 2e 0a 2a 2a 0a 2a 2a 20 49 66  "data"..**.** If
2210: 20 6e 6f 20 65 6c 65 6d 65 6e 74 20 65 78 69 73   no element exis
2220: 74 73 20 77 69 74 68 20 61 20 6d 61 74 63 68 69  ts with a matchi
2230: 6e 67 20 6b 65 79 2c 20 74 68 65 6e 20 61 20 6e  ng key, then a n
2240: 65 77 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 69 73  ew.** element is
2250: 20 63 72 65 61 74 65 64 2e 20 20 41 20 63 6f 70   created.  A cop
2260: 79 20 6f 66 20 74 68 65 20 6b 65 79 20 69 73 20  y of the key is 
2270: 6d 61 64 65 20 69 66 20 74 68 65 20 63 6f 70 79  made if the copy
2280: 4b 65 79 0a 2a 2a 20 66 6c 61 67 20 69 73 20 73  Key.** flag is s
2290: 65 74 2e 20 20 4e 55 4c 4c 20 69 73 20 72 65 74  et.  NULL is ret
22a0: 75 72 6e 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20  urned..**.** If 
22b0: 61 6e 6f 74 68 65 72 20 65 6c 65 6d 65 6e 74 20  another element 
22c0: 61 6c 72 65 61 64 79 20 65 78 69 73 74 73 20 77  already exists w
22d0: 69 74 68 20 74 68 65 20 73 61 6d 65 20 6b 65 79  ith the same key
22e0: 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20 6e 65  , then the.** ne
22f0: 77 20 64 61 74 61 20 72 65 70 6c 61 63 65 73 20  w data replaces 
2300: 74 68 65 20 6f 6c 64 20 64 61 74 61 20 61 6e 64  the old data and
2310: 20 74 68 65 20 6f 6c 64 20 64 61 74 61 20 69 73   the old data is
2320: 20 72 65 74 75 72 6e 65 64 2e 0a 2a 2a 20 54 68   returned..** Th
2330: 65 20 6b 65 79 20 69 73 20 6e 6f 74 20 63 6f 70  e key is not cop
2340: 69 65 64 20 69 6e 20 74 68 69 73 20 69 6e 73 74  ied in this inst
2350: 61 6e 63 65 2e 20 20 49 66 20 61 20 6d 61 6c 6c  ance.  If a mall
2360: 6f 63 20 66 61 69 6c 73 2c 20 74 68 65 6e 0a 2a  oc fails, then.*
2370: 2a 20 74 68 65 20 6e 65 77 20 64 61 74 61 20 69  * the new data i
2380: 73 20 72 65 74 75 72 6e 65 64 20 61 6e 64 20 74  s returned and t
2390: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 69 73  he hash table is
23a0: 20 75 6e 63 68 61 6e 67 65 64 2e 0a 2a 2a 0a 2a   unchanged..**.*
23b0: 2a 20 49 66 20 74 68 65 20 22 64 61 74 61 22 20  * If the "data" 
23c0: 70 61 72 61 6d 65 74 65 72 20 74 6f 20 74 68 69  parameter to thi
23d0: 73 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 4e 55  s function is NU
23e0: 4c 4c 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20  LL, then the.** 
23f0: 65 6c 65 6d 65 6e 74 20 63 6f 72 72 65 73 70 6f  element correspo
2400: 6e 64 69 6e 67 20 74 6f 20 22 6b 65 79 22 20 69  nding to "key" i
2410: 73 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74  s removed from t
2420: 68 65 20 68 61 73 68 20 74 61 62 6c 65 2e 0a 2a  he hash table..*
2430: 2f 0a 76 6f 69 64 20 2a 73 71 6c 69 74 65 33 48  /.void *sqlite3H
2440: 61 73 68 49 6e 73 65 72 74 28 48 61 73 68 20 2a  ashInsert(Hash *
2450: 70 48 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a  pH, const void *
2460: 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 2c 20  pKey, int nKey, 
2470: 76 6f 69 64 20 2a 64 61 74 61 29 7b 0a 20 20 69  void *data){.  i
2480: 6e 74 20 68 72 61 77 3b 20 20 20 20 20 20 20 20  nt hraw;        
2490: 20 20 20 20 20 2f 2a 20 52 61 77 20 68 61 73 68       /* Raw hash
24a0: 20 76 61 6c 75 65 20 6f 66 20 74 68 65 20 6b 65   value of the ke
24b0: 79 20 2a 2f 0a 20 20 69 6e 74 20 68 3b 20 20 20  y */.  int h;   
24c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
24d0: 74 68 65 20 68 61 73 68 20 6f 66 20 74 68 65 20  the hash of the 
24e0: 6b 65 79 20 6d 6f 64 75 6c 6f 20 68 61 73 68 20  key modulo hash 
24f0: 74 61 62 6c 65 20 73 69 7a 65 20 2a 2f 0a 20 20  table size */.  
2500: 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20  HashElem *elem; 
2510: 20 20 20 20 20 20 2f 2a 20 55 73 65 64 20 74 6f        /* Used to
2520: 20 6c 6f 6f 70 20 74 68 72 75 20 74 68 65 20 65   loop thru the e
2530: 6c 65 6d 65 6e 74 20 6c 69 73 74 20 2a 2f 0a 20  lement list */. 
2540: 20 48 61 73 68 45 6c 65 6d 20 2a 6e 65 77 5f 65   HashElem *new_e
2550: 6c 65 6d 3b 20 20 20 2f 2a 20 4e 65 77 20 65 6c  lem;   /* New el
2560: 65 6d 65 6e 74 20 61 64 64 65 64 20 74 6f 20 74  ement added to t
2570: 68 65 20 70 48 20 2a 2f 0a 20 20 69 6e 74 20 28  he pH */.  int (
2580: 2a 78 48 61 73 68 29 28 63 6f 6e 73 74 20 76 6f  *xHash)(const vo
2590: 69 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a 20 54 68  id*,int);  /* Th
25a0: 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 20  e hash function 
25b0: 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 70 48  */..  assert( pH
25c0: 21 3d 30 20 29 3b 0a 20 20 78 48 61 73 68 20 3d  !=0 );.  xHash =
25d0: 20 68 61 73 68 46 75 6e 63 74 69 6f 6e 28 70 48   hashFunction(pH
25e0: 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20 61  ->keyClass);.  a
25f0: 73 73 65 72 74 28 20 78 48 61 73 68 21 3d 30 20  ssert( xHash!=0 
2600: 29 3b 0a 20 20 68 72 61 77 20 3d 20 28 2a 78 48  );.  hraw = (*xH
2610: 61 73 68 29 28 70 4b 65 79 2c 20 6e 4b 65 79 29  ash)(pKey, nKey)
2620: 3b 0a 20 20 61 73 73 65 72 74 28 20 28 70 48 2d  ;.  assert( (pH-
2630: 3e 68 74 73 69 7a 65 20 26 20 28 70 48 2d 3e 68  >htsize & (pH->h
2640: 74 73 69 7a 65 2d 31 29 29 3d 3d 30 20 29 3b 0a  tsize-1))==0 );.
2650: 20 20 68 20 3d 20 68 72 61 77 20 26 20 28 70 48    h = hraw & (pH
2660: 2d 3e 68 74 73 69 7a 65 2d 31 29 3b 0a 20 20 65  ->htsize-1);.  e
2670: 6c 65 6d 20 3d 20 66 69 6e 64 45 6c 65 6d 65 6e  lem = findElemen
2680: 74 47 69 76 65 6e 48 61 73 68 28 70 48 2c 70 4b  tGivenHash(pH,pK
2690: 65 79 2c 6e 4b 65 79 2c 68 29 3b 0a 20 20 69 66  ey,nKey,h);.  if
26a0: 28 20 65 6c 65 6d 20 29 7b 0a 20 20 20 20 76 6f  ( elem ){.    vo
26b0: 69 64 20 2a 6f 6c 64 5f 64 61 74 61 20 3d 20 65  id *old_data = e
26c0: 6c 65 6d 2d 3e 64 61 74 61 3b 0a 20 20 20 20 69  lem->data;.    i
26d0: 66 28 20 64 61 74 61 3d 3d 30 20 29 7b 0a 20 20  f( data==0 ){.  
26e0: 20 20 20 20 72 65 6d 6f 76 65 45 6c 65 6d 65 6e      removeElemen
26f0: 74 47 69 76 65 6e 48 61 73 68 28 70 48 2c 65 6c  tGivenHash(pH,el
2700: 65 6d 2c 68 29 3b 0a 20 20 20 20 7d 65 6c 73 65  em,h);.    }else
2710: 7b 0a 20 20 20 20 20 20 65 6c 65 6d 2d 3e 64 61  {.      elem->da
2720: 74 61 20 3d 20 64 61 74 61 3b 0a 20 20 20 20 7d  ta = data;.    }
2730: 0a 20 20 20 20 72 65 74 75 72 6e 20 6f 6c 64 5f  .    return old_
2740: 64 61 74 61 3b 0a 20 20 7d 0a 20 20 69 66 28 20  data;.  }.  if( 
2750: 64 61 74 61 3d 3d 30 20 29 20 72 65 74 75 72 6e  data==0 ) return
2760: 20 30 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 20 3d   0;.  new_elem =
2770: 20 28 48 61 73 68 45 6c 65 6d 2a 29 73 71 6c 69   (HashElem*)sqli
2780: 74 65 4d 61 6c 6c 6f 63 28 20 73 69 7a 65 6f 66  teMalloc( sizeof
2790: 28 48 61 73 68 45 6c 65 6d 29 20 29 3b 0a 20 20  (HashElem) );.  
27a0: 69 66 28 20 6e 65 77 5f 65 6c 65 6d 3d 3d 30 20  if( new_elem==0 
27b0: 29 20 72 65 74 75 72 6e 20 64 61 74 61 3b 0a 20  ) return data;. 
27c0: 20 69 66 28 20 70 48 2d 3e 63 6f 70 79 4b 65 79   if( pH->copyKey
27d0: 20 26 26 20 70 4b 65 79 21 3d 30 20 29 7b 0a 20   && pKey!=0 ){. 
27e0: 20 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65     new_elem->pKe
27f0: 79 20 3d 20 73 71 6c 69 74 65 4d 61 6c 6c 6f 63  y = sqliteMalloc
2800: 52 61 77 28 20 6e 4b 65 79 20 29 3b 0a 20 20 20  Raw( nKey );.   
2810: 20 69 66 28 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70   if( new_elem->p
2820: 4b 65 79 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20  Key==0 ){.      
2830: 73 71 6c 69 74 65 46 72 65 65 28 6e 65 77 5f 65  sqliteFree(new_e
2840: 6c 65 6d 29 3b 0a 20 20 20 20 20 20 72 65 74 75  lem);.      retu
2850: 72 6e 20 64 61 74 61 3b 0a 20 20 20 20 7d 0a 20  rn data;.    }. 
2860: 20 20 20 6d 65 6d 63 70 79 28 28 76 6f 69 64 2a     memcpy((void*
2870: 29 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 2c  )new_elem->pKey,
2880: 20 70 4b 65 79 2c 20 6e 4b 65 79 29 3b 0a 20 20   pKey, nKey);.  
2890: 7d 65 6c 73 65 7b 0a 20 20 20 20 6e 65 77 5f 65  }else{.    new_e
28a0: 6c 65 6d 2d 3e 70 4b 65 79 20 3d 20 28 76 6f 69  lem->pKey = (voi
28b0: 64 2a 29 70 4b 65 79 3b 0a 20 20 7d 0a 20 20 6e  d*)pKey;.  }.  n
28c0: 65 77 5f 65 6c 65 6d 2d 3e 6e 4b 65 79 20 3d 20  ew_elem->nKey = 
28d0: 6e 4b 65 79 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e  nKey;.  pH->coun
28e0: 74 2b 2b 3b 0a 20 20 69 66 28 20 70 48 2d 3e 68  t++;.  if( pH->h
28f0: 74 73 69 7a 65 3d 3d 30 20 29 20 72 65 68 61 73  tsize==0 ) rehas
2900: 68 28 70 48 2c 38 29 3b 0a 20 20 69 66 28 20 70  h(pH,8);.  if( p
2910: 48 2d 3e 68 74 73 69 7a 65 3d 3d 30 20 29 7b 0a  H->htsize==0 ){.
2920: 20 20 20 20 70 48 2d 3e 63 6f 75 6e 74 20 3d 20      pH->count = 
2930: 30 3b 0a 20 20 20 20 73 71 6c 69 74 65 46 72 65  0;.    sqliteFre
2940: 65 28 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20 20 20  e(new_elem);.   
2950: 20 72 65 74 75 72 6e 20 64 61 74 61 3b 0a 20 20   return data;.  
2960: 7d 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f 75 6e  }.  if( pH->coun
2970: 74 20 3e 20 70 48 2d 3e 68 74 73 69 7a 65 20 29  t > pH->htsize )
2980: 7b 0a 20 20 20 20 72 65 68 61 73 68 28 70 48 2c  {.    rehash(pH,
2990: 70 48 2d 3e 68 74 73 69 7a 65 2a 32 29 3b 0a 20  pH->htsize*2);. 
29a0: 20 7d 0a 20 20 61 73 73 65 72 74 28 20 28 70 48   }.  assert( (pH
29b0: 2d 3e 68 74 73 69 7a 65 20 26 20 28 70 48 2d 3e  ->htsize & (pH->
29c0: 68 74 73 69 7a 65 2d 31 29 29 3d 3d 30 20 29 3b  htsize-1))==0 );
29d0: 0a 20 20 68 20 3d 20 68 72 61 77 20 26 20 28 70  .  h = hraw & (p
29e0: 48 2d 3e 68 74 73 69 7a 65 2d 31 29 3b 0a 20 20  H->htsize-1);.  
29f0: 65 6c 65 6d 20 3d 20 70 48 2d 3e 68 74 5b 68 5d  elem = pH->ht[h]
2a00: 2e 63 68 61 69 6e 3b 0a 20 20 69 66 28 20 65 6c  .chain;.  if( el
2a10: 65 6d 20 29 7b 0a 20 20 20 20 6e 65 77 5f 65 6c  em ){.    new_el
2a20: 65 6d 2d 3e 6e 65 78 74 20 3d 20 65 6c 65 6d 3b  em->next = elem;
2a30: 0a 20 20 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70  .    new_elem->p
2a40: 72 65 76 20 3d 20 65 6c 65 6d 2d 3e 70 72 65 76  rev = elem->prev
2a50: 3b 0a 20 20 20 20 69 66 28 20 65 6c 65 6d 2d 3e  ;.    if( elem->
2a60: 70 72 65 76 20 29 7b 20 65 6c 65 6d 2d 3e 70 72  prev ){ elem->pr
2a70: 65 76 2d 3e 6e 65 78 74 20 3d 20 6e 65 77 5f 65  ev->next = new_e
2a80: 6c 65 6d 3b 20 7d 0a 20 20 20 20 65 6c 73 65 20  lem; }.    else 
2a90: 20 20 20 20 20 20 20 20 20 20 20 7b 20 70 48 2d             { pH-
2aa0: 3e 66 69 72 73 74 20 3d 20 6e 65 77 5f 65 6c 65  >first = new_ele
2ab0: 6d 3b 20 7d 0a 20 20 20 20 65 6c 65 6d 2d 3e 70  m; }.    elem->p
2ac0: 72 65 76 20 3d 20 6e 65 77 5f 65 6c 65 6d 3b 0a  rev = new_elem;.
2ad0: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 6e 65 77    }else{.    new
2ae0: 5f 65 6c 65 6d 2d 3e 6e 65 78 74 20 3d 20 70 48  _elem->next = pH
2af0: 2d 3e 66 69 72 73 74 3b 0a 20 20 20 20 6e 65 77  ->first;.    new
2b00: 5f 65 6c 65 6d 2d 3e 70 72 65 76 20 3d 20 30 3b  _elem->prev = 0;
2b10: 0a 20 20 20 20 69 66 28 20 70 48 2d 3e 66 69 72  .    if( pH->fir
2b20: 73 74 20 29 7b 20 70 48 2d 3e 66 69 72 73 74 2d  st ){ pH->first-
2b30: 3e 70 72 65 76 20 3d 20 6e 65 77 5f 65 6c 65 6d  >prev = new_elem
2b40: 3b 20 7d 0a 20 20 20 20 70 48 2d 3e 66 69 72 73  ; }.    pH->firs
2b50: 74 20 3d 20 6e 65 77 5f 65 6c 65 6d 3b 0a 20 20  t = new_elem;.  
2b60: 7d 0a 20 20 70 48 2d 3e 68 74 5b 68 5d 2e 63 6f  }.  pH->ht[h].co
2b70: 75 6e 74 2b 2b 3b 0a 20 20 70 48 2d 3e 68 74 5b  unt++;.  pH->ht[
2b80: 68 5d 2e 63 68 61 69 6e 20 3d 20 6e 65 77 5f 65  h].chain = new_e
2b90: 6c 65 6d 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d  lem;.  new_elem-
2ba0: 3e 64 61 74 61 20 3d 20 64 61 74 61 3b 0a 20 20  >data = data;.  
2bb0: 72 65 74 75 72 6e 20 30 3b 0a 7d 0a              return 0;.}.