/ Hex Artifact Content
Login

Artifact 9b56ef3b291e25168f630d5643a4264ec011c70e:


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 31 20 32 30 30 34 2f 30 31 2f  ,v 1.11 2004/01/
01e0: 30 38 20 30 32 3a 31 37 3a 33 33 20 64 72 68 20  08 02:17:33 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 48 61 73 68 49 6e 69 74 28 48 61 73 68 20 2a  eHashInit(Hash *
04b0: 6e 65 77 2c 20 69 6e 74 20 6b 65 79 43 6c 61 73  new, int keyClas
04c0: 73 2c 20 69 6e 74 20 63 6f 70 79 4b 65 79 29 7b  s, int copyKey){
04d0: 0a 20 20 61 73 73 65 72 74 28 20 6e 65 77 21 3d  .  assert( new!=
04e0: 30 20 29 3b 0a 20 20 61 73 73 65 72 74 28 20 6b  0 );.  assert( k
04f0: 65 79 43 6c 61 73 73 3e 3d 53 51 4c 49 54 45 5f  eyClass>=SQLITE_
0500: 48 41 53 48 5f 49 4e 54 20 26 26 20 6b 65 79 43  HASH_INT && keyC
0510: 6c 61 73 73 3c 3d 53 51 4c 49 54 45 5f 48 41 53  lass<=SQLITE_HAS
0520: 48 5f 42 49 4e 41 52 59 20 29 3b 0a 20 20 6e 65  H_BINARY );.  ne
0530: 77 2d 3e 6b 65 79 43 6c 61 73 73 20 3d 20 6b 65  w->keyClass = ke
0540: 79 43 6c 61 73 73 3b 0a 20 20 6e 65 77 2d 3e 63  yClass;.  new->c
0550: 6f 70 79 4b 65 79 20 3d 20 63 6f 70 79 4b 65 79  opyKey = copyKey
0560: 20 26 26 0a 20 20 20 20 20 20 20 20 20 20 20 20   &&.            
0570: 20 20 20 20 28 6b 65 79 43 6c 61 73 73 3d 3d 53      (keyClass==S
0580: 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 49 4e  QLITE_HASH_STRIN
0590: 47 20 7c 7c 20 6b 65 79 43 6c 61 73 73 3d 3d 53  G || keyClass==S
05a0: 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e 41 52  QLITE_HASH_BINAR
05b0: 59 29 3b 0a 20 20 6e 65 77 2d 3e 66 69 72 73 74  Y);.  new->first
05c0: 20 3d 20 30 3b 0a 20 20 6e 65 77 2d 3e 63 6f 75   = 0;.  new->cou
05d0: 6e 74 20 3d 20 30 3b 0a 20 20 6e 65 77 2d 3e 68  nt = 0;.  new->h
05e0: 74 73 69 7a 65 20 3d 20 30 3b 0a 20 20 6e 65 77  tsize = 0;.  new
05f0: 2d 3e 68 74 20 3d 20 30 3b 0a 7d 0a 0a 2f 2a 20  ->ht = 0;.}../* 
0600: 52 65 6d 6f 76 65 20 61 6c 6c 20 65 6e 74 72 69  Remove all entri
0610: 65 73 20 66 72 6f 6d 20 61 20 68 61 73 68 20 74  es from a hash t
0620: 61 62 6c 65 2e 20 20 52 65 63 6c 61 69 6d 20 61  able.  Reclaim a
0630: 6c 6c 20 6d 65 6d 6f 72 79 2e 0a 2a 2a 20 43 61  ll memory..** Ca
0640: 6c 6c 20 74 68 69 73 20 72 6f 75 74 69 6e 65 20  ll this routine 
0650: 74 6f 20 64 65 6c 65 74 65 20 61 20 68 61 73 68  to delete a hash
0660: 20 74 61 62 6c 65 20 6f 72 20 74 6f 20 72 65 73   table or to res
0670: 65 74 20 61 20 68 61 73 68 20 74 61 62 6c 65 0a  et a hash table.
0680: 2a 2a 20 74 6f 20 74 68 65 20 65 6d 70 74 79 20  ** to the empty 
0690: 73 74 61 74 65 2e 0a 2a 2f 0a 76 6f 69 64 20 73  state..*/.void s
06a0: 71 6c 69 74 65 48 61 73 68 43 6c 65 61 72 28 48  qliteHashClear(H
06b0: 61 73 68 20 2a 70 48 29 7b 0a 20 20 48 61 73 68  ash *pH){.  Hash
06c0: 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 20  Elem *elem;     
06d0: 20 20 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f 70 69      /* For loopi
06e0: 6e 67 20 6f 76 65 72 20 61 6c 6c 20 65 6c 65 6d  ng over all elem
06f0: 65 6e 74 73 20 6f 66 20 74 68 65 20 74 61 62 6c  ents of the tabl
0700: 65 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20  e */..  assert( 
0710: 70 48 21 3d 30 20 29 3b 0a 20 20 65 6c 65 6d 20  pH!=0 );.  elem 
0720: 3d 20 70 48 2d 3e 66 69 72 73 74 3b 0a 20 20 70  = pH->first;.  p
0730: 48 2d 3e 66 69 72 73 74 20 3d 20 30 3b 0a 20 20  H->first = 0;.  
0740: 69 66 28 20 70 48 2d 3e 68 74 20 29 20 73 71 6c  if( pH->ht ) sql
0750: 69 74 65 46 72 65 65 28 70 48 2d 3e 68 74 29 3b  iteFree(pH->ht);
0760: 0a 20 20 70 48 2d 3e 68 74 20 3d 20 30 3b 0a 20  .  pH->ht = 0;. 
0770: 20 70 48 2d 3e 68 74 73 69 7a 65 20 3d 20 30 3b   pH->htsize = 0;
0780: 0a 20 20 77 68 69 6c 65 28 20 65 6c 65 6d 20 29  .  while( elem )
0790: 7b 0a 20 20 20 20 48 61 73 68 45 6c 65 6d 20 2a  {.    HashElem *
07a0: 6e 65 78 74 5f 65 6c 65 6d 20 3d 20 65 6c 65 6d  next_elem = elem
07b0: 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 69 66 28 20  ->next;.    if( 
07c0: 70 48 2d 3e 63 6f 70 79 4b 65 79 20 26 26 20 65  pH->copyKey && e
07d0: 6c 65 6d 2d 3e 70 4b 65 79 20 29 7b 0a 20 20 20  lem->pKey ){.   
07e0: 20 20 20 73 71 6c 69 74 65 46 72 65 65 28 65 6c     sqliteFree(el
07f0: 65 6d 2d 3e 70 4b 65 79 29 3b 0a 20 20 20 20 7d  em->pKey);.    }
0800: 0a 20 20 20 20 73 71 6c 69 74 65 46 72 65 65 28  .    sqliteFree(
0810: 65 6c 65 6d 29 3b 0a 20 20 20 20 65 6c 65 6d 20  elem);.    elem 
0820: 3d 20 6e 65 78 74 5f 65 6c 65 6d 3b 0a 20 20 7d  = next_elem;.  }
0830: 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 20 3d 20 30  .  pH->count = 0
0840: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 48 61 73 68 20  ;.}../*.** Hash 
0850: 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66  and comparison f
0860: 75 6e 63 74 69 6f 6e 73 20 77 68 65 6e 20 74 68  unctions when th
0870: 65 20 6d 6f 64 65 20 69 73 20 53 51 4c 49 54 45  e mode is SQLITE
0880: 5f 48 41 53 48 5f 49 4e 54 0a 2a 2f 0a 73 74 61  _HASH_INT.*/.sta
0890: 74 69 63 20 69 6e 74 20 69 6e 74 48 61 73 68 28  tic int intHash(
08a0: 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79  const void *pKey
08b0: 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 72  , int nKey){.  r
08c0: 65 74 75 72 6e 20 6e 4b 65 79 20 5e 20 28 6e 4b  eturn nKey ^ (nK
08d0: 65 79 3c 3c 38 29 20 5e 20 28 6e 4b 65 79 3e 3e  ey<<8) ^ (nKey>>
08e0: 38 29 3b 0a 7d 0a 73 74 61 74 69 63 20 69 6e 74  8);.}.static int
08f0: 20 69 6e 74 43 6f 6d 70 61 72 65 28 63 6f 6e 73   intCompare(cons
0900: 74 20 76 6f 69 64 20 2a 70 4b 65 79 31 2c 20 69  t void *pKey1, i
0910: 6e 74 20 6e 31 2c 20 63 6f 6e 73 74 20 76 6f 69  nt n1, const voi
0920: 64 20 2a 70 4b 65 79 32 2c 20 69 6e 74 20 6e 32  d *pKey2, int n2
0930: 29 7b 0a 20 20 72 65 74 75 72 6e 20 6e 32 20 2d  ){.  return n2 -
0940: 20 6e 31 3b 0a 7d 0a 0a 23 69 66 20 30 20 2f 2a   n1;.}..#if 0 /*
0950: 20 4e 4f 54 20 55 53 45 44 20 2a 2f 0a 2f 2a 0a   NOT USED */./*.
0960: 2a 2a 20 48 61 73 68 20 61 6e 64 20 63 6f 6d 70  ** Hash and comp
0970: 61 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 73  arison functions
0980: 20 77 68 65 6e 20 74 68 65 20 6d 6f 64 65 20 69   when the mode i
0990: 73 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 50 4f  s SQLITE_HASH_PO
09a0: 49 4e 54 45 52 0a 2a 2f 0a 73 74 61 74 69 63 20  INTER.*/.static 
09b0: 69 6e 74 20 70 74 72 48 61 73 68 28 63 6f 6e 73  int ptrHash(cons
09c0: 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e  t void *pKey, in
09d0: 74 20 6e 4b 65 79 29 7b 0a 20 20 75 70 74 72 20  t nKey){.  uptr 
09e0: 78 20 3d 20 41 64 64 72 28 70 4b 65 79 29 3b 0a  x = Addr(pKey);.
09f0: 20 20 72 65 74 75 72 6e 20 78 20 5e 20 28 78 3c    return x ^ (x<
0a00: 3c 38 29 20 5e 20 28 78 3e 3e 38 29 3b 0a 7d 0a  <8) ^ (x>>8);.}.
0a10: 73 74 61 74 69 63 20 69 6e 74 20 70 74 72 43 6f  static int ptrCo
0a20: 6d 70 61 72 65 28 63 6f 6e 73 74 20 76 6f 69 64  mpare(const void
0a30: 20 2a 70 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c   *pKey1, int n1,
0a40: 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65   const void *pKe
0a50: 79 32 2c 20 69 6e 74 20 6e 32 29 7b 0a 20 20 69  y2, int n2){.  i
0a60: 66 28 20 70 4b 65 79 31 3d 3d 70 4b 65 79 32 20  f( pKey1==pKey2 
0a70: 29 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 69 66  ) return 0;.  if
0a80: 28 20 70 4b 65 79 31 3c 70 4b 65 79 32 20 29 20  ( pKey1<pKey2 ) 
0a90: 72 65 74 75 72 6e 20 2d 31 3b 0a 20 20 72 65 74  return -1;.  ret
0aa0: 75 72 6e 20 31 3b 0a 7d 0a 23 65 6e 64 69 66 0a  urn 1;.}.#endif.
0ab0: 0a 2f 2a 0a 2a 2a 20 48 61 73 68 20 61 6e 64 20  ./*.** Hash and 
0ac0: 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75 6e 63 74  comparison funct
0ad0: 69 6f 6e 73 20 77 68 65 6e 20 74 68 65 20 6d 6f  ions when the mo
0ae0: 64 65 20 69 73 20 53 51 4c 49 54 45 5f 48 41 53  de is SQLITE_HAS
0af0: 48 5f 53 54 52 49 4e 47 0a 2a 2f 0a 73 74 61 74  H_STRING.*/.stat
0b00: 69 63 20 69 6e 74 20 73 74 72 48 61 73 68 28 63  ic int strHash(c
0b10: 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c  onst void *pKey,
0b20: 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 72 65   int nKey){.  re
0b30: 74 75 72 6e 20 73 71 6c 69 74 65 48 61 73 68 4e  turn sqliteHashN
0b40: 6f 43 61 73 65 28 28 63 6f 6e 73 74 20 63 68 61  oCase((const cha
0b50: 72 2a 29 70 4b 65 79 2c 20 6e 4b 65 79 29 3b 20  r*)pKey, nKey); 
0b60: 0a 7d 0a 73 74 61 74 69 63 20 69 6e 74 20 73 74  .}.static int st
0b70: 72 43 6f 6d 70 61 72 65 28 63 6f 6e 73 74 20 76  rCompare(const v
0b80: 6f 69 64 20 2a 70 4b 65 79 31 2c 20 69 6e 74 20  oid *pKey1, int 
0b90: 6e 31 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a  n1, const void *
0ba0: 70 4b 65 79 32 2c 20 69 6e 74 20 6e 32 29 7b 0a  pKey2, int n2){.
0bb0: 20 20 69 66 28 20 6e 31 21 3d 6e 32 20 29 20 72    if( n1!=n2 ) r
0bc0: 65 74 75 72 6e 20 6e 32 2d 6e 31 3b 0a 20 20 72  eturn n2-n1;.  r
0bd0: 65 74 75 72 6e 20 73 71 6c 69 74 65 53 74 72 4e  eturn sqliteStrN
0be0: 49 43 6d 70 28 28 63 6f 6e 73 74 20 63 68 61 72  ICmp((const char
0bf0: 2a 29 70 4b 65 79 31 2c 28 63 6f 6e 73 74 20 63  *)pKey1,(const c
0c00: 68 61 72 2a 29 70 4b 65 79 32 2c 6e 31 29 3b 0a  har*)pKey2,n1);.
0c10: 7d 0a 0a 2f 2a 0a 2a 2a 20 48 61 73 68 20 61 6e  }../*.** Hash an
0c20: 64 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75 6e  d comparison fun
0c30: 63 74 69 6f 6e 73 20 77 68 65 6e 20 74 68 65 20  ctions when the 
0c40: 6d 6f 64 65 20 69 73 20 53 51 4c 49 54 45 5f 48  mode is SQLITE_H
0c50: 41 53 48 5f 42 49 4e 41 52 59 0a 2a 2f 0a 73 74  ASH_BINARY.*/.st
0c60: 61 74 69 63 20 69 6e 74 20 62 69 6e 48 61 73 68  atic int binHash
0c70: 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65  (const void *pKe
0c80: 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20 20  y, int nKey){.  
0c90: 69 6e 74 20 68 20 3d 20 30 3b 0a 20 20 63 6f 6e  int h = 0;.  con
0ca0: 73 74 20 63 68 61 72 20 2a 7a 20 3d 20 28 63 6f  st char *z = (co
0cb0: 6e 73 74 20 63 68 61 72 20 2a 29 70 4b 65 79 3b  nst char *)pKey;
0cc0: 0a 20 20 77 68 69 6c 65 28 20 6e 4b 65 79 2d 2d  .  while( nKey--
0cd0: 20 3e 20 30 20 29 7b 0a 20 20 20 20 68 20 3d 20   > 0 ){.    h = 
0ce0: 28 68 3c 3c 33 29 20 5e 20 68 20 5e 20 2a 28 7a  (h<<3) ^ h ^ *(z
0cf0: 2b 2b 29 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72  ++);.  }.  retur
0d00: 6e 20 68 20 26 20 30 78 37 66 66 66 66 66 66 66  n h & 0x7fffffff
0d10: 3b 0a 7d 0a 73 74 61 74 69 63 20 69 6e 74 20 62  ;.}.static int b
0d20: 69 6e 43 6f 6d 70 61 72 65 28 63 6f 6e 73 74 20  inCompare(const 
0d30: 76 6f 69 64 20 2a 70 4b 65 79 31 2c 20 69 6e 74  void *pKey1, int
0d40: 20 6e 31 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20   n1, const void 
0d50: 2a 70 4b 65 79 32 2c 20 69 6e 74 20 6e 32 29 7b  *pKey2, int n2){
0d60: 0a 20 20 69 66 28 20 6e 31 21 3d 6e 32 20 29 20  .  if( n1!=n2 ) 
0d70: 72 65 74 75 72 6e 20 6e 32 2d 6e 31 3b 0a 20 20  return n2-n1;.  
0d80: 72 65 74 75 72 6e 20 6d 65 6d 63 6d 70 28 70 4b  return memcmp(pK
0d90: 65 79 31 2c 70 4b 65 79 32 2c 6e 31 29 3b 0a 7d  ey1,pKey2,n1);.}
0da0: 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 61  ../*.** Return a
0db0: 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 20   pointer to the 
0dc0: 61 70 70 72 6f 70 72 69 61 74 65 20 68 61 73 68  appropriate hash
0dd0: 20 66 75 6e 63 74 69 6f 6e 20 67 69 76 65 6e 20   function given 
0de0: 74 68 65 20 6b 65 79 20 63 6c 61 73 73 2e 0a 2a  the key class..*
0df0: 2a 0a 2a 2a 20 54 68 65 20 43 20 73 79 6e 74 61  *.** The C synta
0e00: 78 20 69 6e 20 74 68 69 73 20 66 75 6e 63 74 69  x in this functi
0e10: 6f 6e 20 64 65 66 69 6e 69 74 69 6f 6e 20 6d 61  on definition ma
0e20: 79 20 62 65 20 75 6e 66 61 6d 69 6c 61 72 20 74  y be unfamilar t
0e30: 6f 20 73 6f 6d 65 20 0a 2a 2a 20 70 72 6f 67 72  o some .** progr
0e40: 61 6d 6d 65 72 73 2c 20 73 6f 20 77 65 20 70 72  ammers, so we pr
0e50: 6f 76 69 64 65 20 74 68 65 20 66 6f 6c 6c 6f 77  ovide the follow
0e60: 69 6e 67 20 61 64 64 69 74 69 6f 6e 61 6c 20 65  ing additional e
0e70: 78 70 6c 61 6e 61 74 69 6f 6e 3a 0a 2a 2a 0a 2a  xplanation:.**.*
0e80: 2a 20 54 68 65 20 6e 61 6d 65 20 6f 66 20 74 68  * The name of th
0e90: 65 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 22 68  e function is "h
0ea0: 61 73 68 46 75 6e 63 74 69 6f 6e 22 2e 20 20 54  ashFunction".  T
0eb0: 68 65 20 66 75 6e 63 74 69 6f 6e 20 74 61 6b 65  he function take
0ec0: 73 20 61 0a 2a 2a 20 73 69 6e 67 6c 65 20 70 61  s a.** single pa
0ed0: 72 61 6d 65 74 65 72 20 22 6b 65 79 43 6c 61 73  rameter "keyClas
0ee0: 73 22 2e 20 20 54 68 65 20 72 65 74 75 72 6e 20  s".  The return 
0ef0: 76 61 6c 75 65 20 6f 66 20 68 61 73 68 46 75 6e  value of hashFun
0f00: 63 74 69 6f 6e 28 29 0a 2a 2a 20 69 73 20 61 20  ction().** is a 
0f10: 70 6f 69 6e 74 65 72 20 74 6f 20 61 6e 6f 74 68  pointer to anoth
0f20: 65 72 20 66 75 6e 63 74 69 6f 6e 2e 20 20 53 70  er function.  Sp
0f30: 65 63 69 66 69 63 61 6c 6c 79 2c 20 74 68 65 20  ecifically, the 
0f40: 72 65 74 75 72 6e 20 76 61 6c 75 65 0a 2a 2a 20  return value.** 
0f50: 6f 66 20 68 61 73 68 46 75 6e 63 74 69 6f 6e 28  of hashFunction(
0f60: 29 20 69 73 20 61 20 70 6f 69 6e 74 65 72 20 74  ) is a pointer t
0f70: 6f 20 61 20 66 75 6e 63 74 69 6f 6e 20 74 68 61  o a function tha
0f80: 74 20 74 61 6b 65 73 20 74 77 6f 20 70 61 72 61  t takes two para
0f90: 6d 65 74 65 72 73 0a 2a 2a 20 77 69 74 68 20 74  meters.** with t
0fa0: 79 70 65 73 20 22 63 6f 6e 73 74 20 76 6f 69 64  ypes "const void
0fb0: 2a 22 20 61 6e 64 20 22 69 6e 74 22 20 61 6e 64  *" and "int" and
0fc0: 20 72 65 74 75 72 6e 73 20 61 6e 20 22 69 6e 74   returns an "int
0fd0: 22 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74  "..*/.static int
0fe0: 20 28 2a 68 61 73 68 46 75 6e 63 74 69 6f 6e 28   (*hashFunction(
0ff0: 69 6e 74 20 6b 65 79 43 6c 61 73 73 29 29 28 63  int keyClass))(c
1000: 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29 7b  onst void*,int){
1010: 0a 20 20 73 77 69 74 63 68 28 20 6b 65 79 43 6c  .  switch( keyCl
1020: 61 73 73 20 29 7b 0a 20 20 20 20 63 61 73 65 20  ass ){.    case 
1030: 53 51 4c 49 54 45 5f 48 41 53 48 5f 49 4e 54 3a  SQLITE_HASH_INT:
1040: 20 20 20 20 20 72 65 74 75 72 6e 20 26 69 6e 74       return &int
1050: 48 61 73 68 3b 0a 20 20 20 20 2f 2a 20 63 61 73  Hash;.    /* cas
1060: 65 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 50 4f  e SQLITE_HASH_PO
1070: 49 4e 54 45 52 3a 20 72 65 74 75 72 6e 20 26 70  INTER: return &p
1080: 74 72 48 61 73 68 3b 20 2f 2f 20 4e 4f 54 20 55  trHash; // NOT U
1090: 53 45 44 20 2a 2f 0a 20 20 20 20 63 61 73 65 20  SED */.    case 
10a0: 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 49  SQLITE_HASH_STRI
10b0: 4e 47 3a 20 20 72 65 74 75 72 6e 20 26 73 74 72  NG:  return &str
10c0: 48 61 73 68 3b 0a 20 20 20 20 63 61 73 65 20 53  Hash;.    case S
10d0: 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e 41 52  QLITE_HASH_BINAR
10e0: 59 3a 20 20 72 65 74 75 72 6e 20 26 62 69 6e 48  Y:  return &binH
10f0: 61 73 68 3b 3b 0a 20 20 20 20 64 65 66 61 75 6c  ash;;.    defaul
1100: 74 3a 20 62 72 65 61 6b 3b 0a 20 20 7d 0a 20 20  t: break;.  }.  
1110: 72 65 74 75 72 6e 20 30 3b 0a 7d 0a 0a 2f 2a 0a  return 0;.}../*.
1120: 2a 2a 20 52 65 74 75 72 6e 20 61 20 70 6f 69 6e  ** Return a poin
1130: 74 65 72 20 74 6f 20 74 68 65 20 61 70 70 72 6f  ter to the appro
1140: 70 72 69 61 74 65 20 68 61 73 68 20 66 75 6e 63  priate hash func
1150: 74 69 6f 6e 20 67 69 76 65 6e 20 74 68 65 20 6b  tion given the k
1160: 65 79 20 63 6c 61 73 73 2e 0a 2a 2a 0a 2a 2a 20  ey class..**.** 
1170: 46 6f 72 20 68 65 6c 70 20 69 6e 20 69 6e 74 65  For help in inte
1180: 72 70 72 65 74 65 64 20 74 68 65 20 6f 62 73 63  rpreted the obsc
1190: 75 72 65 20 43 20 63 6f 64 65 20 69 6e 20 74 68  ure C code in th
11a0: 65 20 66 75 6e 63 74 69 6f 6e 20 64 65 66 69 6e  e function defin
11b0: 69 74 69 6f 6e 2c 0a 2a 2a 20 73 65 65 20 74 68  ition,.** see th
11c0: 65 20 68 65 61 64 65 72 20 63 6f 6d 6d 65 6e 74  e header comment
11d0: 20 6f 6e 20 74 68 65 20 70 72 65 76 69 6f 75 73   on the previous
11e0: 20 66 75 6e 63 74 69 6f 6e 2e 0a 2a 2f 0a 73 74   function..*/.st
11f0: 61 74 69 63 20 69 6e 74 20 28 2a 63 6f 6d 70 61  atic int (*compa
1200: 72 65 46 75 6e 63 74 69 6f 6e 28 69 6e 74 20 6b  reFunction(int k
1210: 65 79 43 6c 61 73 73 29 29 28 63 6f 6e 73 74 20  eyClass))(const 
1220: 76 6f 69 64 2a 2c 69 6e 74 2c 63 6f 6e 73 74 20  void*,int,const 
1230: 76 6f 69 64 2a 2c 69 6e 74 29 7b 0a 20 20 73 77  void*,int){.  sw
1240: 69 74 63 68 28 20 6b 65 79 43 6c 61 73 73 20 29  itch( keyClass )
1250: 7b 0a 20 20 20 20 63 61 73 65 20 53 51 4c 49 54  {.    case SQLIT
1260: 45 5f 48 41 53 48 5f 49 4e 54 3a 20 20 20 20 20  E_HASH_INT:     
1270: 72 65 74 75 72 6e 20 26 69 6e 74 43 6f 6d 70 61  return &intCompa
1280: 72 65 3b 0a 20 20 20 20 2f 2a 20 63 61 73 65 20  re;.    /* case 
1290: 53 51 4c 49 54 45 5f 48 41 53 48 5f 50 4f 49 4e  SQLITE_HASH_POIN
12a0: 54 45 52 3a 20 72 65 74 75 72 6e 20 26 70 74 72  TER: return &ptr
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 63 61 73 65  USED */.    case
12d0: 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52   SQLITE_HASH_STR
12e0: 49 4e 47 3a 20 20 72 65 74 75 72 6e 20 26 73 74  ING:  return &st
12f0: 72 43 6f 6d 70 61 72 65 3b 0a 20 20 20 20 63 61  rCompare;.    ca
1300: 73 65 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 42  se SQLITE_HASH_B
1310: 49 4e 41 52 59 3a 20 20 72 65 74 75 72 6e 20 26  INARY:  return &
1320: 62 69 6e 43 6f 6d 70 61 72 65 3b 0a 20 20 20 20  binCompare;.    
1330: 64 65 66 61 75 6c 74 3a 20 62 72 65 61 6b 3b 0a  default: break;.
1340: 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a    }.  return 0;.
1350: 7d 0a 0a 0a 2f 2a 20 52 65 73 69 7a 65 20 74 68  }.../* Resize th
1360: 65 20 68 61 73 68 20 74 61 62 6c 65 20 73 6f 20  e hash table so 
1370: 74 68 61 74 20 69 74 20 63 61 6e 74 61 69 6e 73  that it cantains
1380: 20 22 6e 65 77 5f 73 69 7a 65 22 20 62 75 63 6b   "new_size" buck
1390: 65 74 73 2e 0a 2a 2a 20 22 6e 65 77 5f 73 69 7a  ets..** "new_siz
13a0: 65 22 20 6d 75 73 74 20 62 65 20 61 20 70 6f 77  e" must be a pow
13b0: 65 72 20 6f 66 20 32 2e 20 20 54 68 65 20 68 61  er of 2.  The ha
13c0: 73 68 20 74 61 62 6c 65 20 6d 69 67 68 74 20 66  sh table might f
13d0: 61 69 6c 20 0a 2a 2a 20 74 6f 20 72 65 73 69 7a  ail .** to resiz
13e0: 65 20 69 66 20 73 71 6c 69 74 65 4d 61 6c 6c 6f  e if sqliteMallo
13f0: 63 28 29 20 66 61 69 6c 73 2e 0a 2a 2f 0a 73 74  c() fails..*/.st
1400: 61 74 69 63 20 76 6f 69 64 20 72 65 68 61 73 68  atic void rehash
1410: 28 48 61 73 68 20 2a 70 48 2c 20 69 6e 74 20 6e  (Hash *pH, int n
1420: 65 77 5f 73 69 7a 65 29 7b 0a 20 20 73 74 72 75  ew_size){.  stru
1430: 63 74 20 5f 68 74 20 2a 6e 65 77 5f 68 74 3b 20  ct _ht *new_ht; 
1440: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68             /* Th
1450: 65 20 6e 65 77 20 68 61 73 68 20 74 61 62 6c 65  e new hash table
1460: 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a   */.  HashElem *
1470: 65 6c 65 6d 2c 20 2a 6e 65 78 74 5f 65 6c 65 6d  elem, *next_elem
1480: 3b 20 20 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f 70  ;    /* For loop
1490: 69 6e 67 20 6f 76 65 72 20 65 78 69 73 74 69 6e  ing over existin
14a0: 67 20 65 6c 65 6d 65 6e 74 73 20 2a 2f 0a 20 20  g elements */.  
14b0: 48 61 73 68 45 6c 65 6d 20 2a 78 3b 20 20 20 20  HashElem *x;    
14c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
14d0: 2a 20 45 6c 65 6d 65 6e 74 20 62 65 69 6e 67 20  * Element being 
14e0: 63 6f 70 69 65 64 20 74 6f 20 6e 65 77 20 68 61  copied to new ha
14f0: 73 68 20 74 61 62 6c 65 20 2a 2f 0a 20 20 69 6e  sh table */.  in
1500: 74 20 28 2a 78 48 61 73 68 29 28 63 6f 6e 73 74  t (*xHash)(const
1510: 20 76 6f 69 64 2a 2c 69 6e 74 29 3b 20 2f 2a 20   void*,int); /* 
1520: 54 68 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f  The hash functio
1530: 6e 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20  n */..  assert( 
1540: 28 6e 65 77 5f 73 69 7a 65 20 26 20 28 6e 65 77  (new_size & (new
1550: 5f 73 69 7a 65 2d 31 29 29 3d 3d 30 20 29 3b 0a  _size-1))==0 );.
1560: 20 20 6e 65 77 5f 68 74 20 3d 20 28 73 74 72 75    new_ht = (stru
1570: 63 74 20 5f 68 74 20 2a 29 73 71 6c 69 74 65 4d  ct _ht *)sqliteM
1580: 61 6c 6c 6f 63 28 20 6e 65 77 5f 73 69 7a 65 2a  alloc( new_size*
1590: 73 69 7a 65 6f 66 28 73 74 72 75 63 74 20 5f 68  sizeof(struct _h
15a0: 74 29 20 29 3b 0a 20 20 69 66 28 20 6e 65 77 5f  t) );.  if( new_
15b0: 68 74 3d 3d 30 20 29 20 72 65 74 75 72 6e 3b 0a  ht==0 ) return;.
15c0: 20 20 69 66 28 20 70 48 2d 3e 68 74 20 29 20 73    if( pH->ht ) s
15d0: 71 6c 69 74 65 46 72 65 65 28 70 48 2d 3e 68 74  qliteFree(pH->ht
15e0: 29 3b 0a 20 20 70 48 2d 3e 68 74 20 3d 20 6e 65  );.  pH->ht = ne
15f0: 77 5f 68 74 3b 0a 20 20 70 48 2d 3e 68 74 73 69  w_ht;.  pH->htsi
1600: 7a 65 20 3d 20 6e 65 77 5f 73 69 7a 65 3b 0a 20  ze = new_size;. 
1610: 20 78 48 61 73 68 20 3d 20 68 61 73 68 46 75 6e   xHash = hashFun
1620: 63 74 69 6f 6e 28 70 48 2d 3e 6b 65 79 43 6c 61  ction(pH->keyCla
1630: 73 73 29 3b 0a 20 20 66 6f 72 28 65 6c 65 6d 3d  ss);.  for(elem=
1640: 70 48 2d 3e 66 69 72 73 74 2c 20 70 48 2d 3e 66  pH->first, pH->f
1650: 69 72 73 74 3d 30 3b 20 65 6c 65 6d 3b 20 65 6c  irst=0; elem; el
1660: 65 6d 20 3d 20 6e 65 78 74 5f 65 6c 65 6d 29 7b  em = next_elem){
1670: 0a 20 20 20 20 69 6e 74 20 68 20 3d 20 28 2a 78  .    int h = (*x
1680: 48 61 73 68 29 28 65 6c 65 6d 2d 3e 70 4b 65 79  Hash)(elem->pKey
1690: 2c 20 65 6c 65 6d 2d 3e 6e 4b 65 79 29 20 26 20  , elem->nKey) & 
16a0: 28 6e 65 77 5f 73 69 7a 65 2d 31 29 3b 0a 20 20  (new_size-1);.  
16b0: 20 20 6e 65 78 74 5f 65 6c 65 6d 20 3d 20 65 6c    next_elem = el
16c0: 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 78 20  em->next;.    x 
16d0: 3d 20 6e 65 77 5f 68 74 5b 68 5d 2e 63 68 61 69  = new_ht[h].chai
16e0: 6e 3b 0a 20 20 20 20 69 66 28 20 78 20 29 7b 0a  n;.    if( x ){.
16f0: 20 20 20 20 20 20 65 6c 65 6d 2d 3e 6e 65 78 74        elem->next
1700: 20 3d 20 78 3b 0a 20 20 20 20 20 20 65 6c 65 6d   = x;.      elem
1710: 2d 3e 70 72 65 76 20 3d 20 78 2d 3e 70 72 65 76  ->prev = x->prev
1720: 3b 0a 20 20 20 20 20 20 69 66 28 20 78 2d 3e 70  ;.      if( x->p
1730: 72 65 76 20 29 20 78 2d 3e 70 72 65 76 2d 3e 6e  rev ) x->prev->n
1740: 65 78 74 20 3d 20 65 6c 65 6d 3b 0a 20 20 20 20  ext = elem;.    
1750: 20 20 65 6c 73 65 20 20 20 20 20 20 20 20 20 20    else          
1760: 70 48 2d 3e 66 69 72 73 74 20 3d 20 65 6c 65 6d  pH->first = elem
1770: 3b 0a 20 20 20 20 20 20 78 2d 3e 70 72 65 76 20  ;.      x->prev 
1780: 3d 20 65 6c 65 6d 3b 0a 20 20 20 20 7d 65 6c 73  = elem;.    }els
1790: 65 7b 0a 20 20 20 20 20 20 65 6c 65 6d 2d 3e 6e  e{.      elem->n
17a0: 65 78 74 20 3d 20 70 48 2d 3e 66 69 72 73 74 3b  ext = pH->first;
17b0: 0a 20 20 20 20 20 20 69 66 28 20 70 48 2d 3e 66  .      if( pH->f
17c0: 69 72 73 74 20 29 20 70 48 2d 3e 66 69 72 73 74  irst ) pH->first
17d0: 2d 3e 70 72 65 76 20 3d 20 65 6c 65 6d 3b 0a 20  ->prev = elem;. 
17e0: 20 20 20 20 20 65 6c 65 6d 2d 3e 70 72 65 76 20       elem->prev 
17f0: 3d 20 30 3b 0a 20 20 20 20 20 20 70 48 2d 3e 66  = 0;.      pH->f
1800: 69 72 73 74 20 3d 20 65 6c 65 6d 3b 0a 20 20 20  irst = elem;.   
1810: 20 7d 0a 20 20 20 20 6e 65 77 5f 68 74 5b 68 5d   }.    new_ht[h]
1820: 2e 63 68 61 69 6e 20 3d 20 65 6c 65 6d 3b 0a 20  .chain = elem;. 
1830: 20 20 20 6e 65 77 5f 68 74 5b 68 5d 2e 63 6f 75     new_ht[h].cou
1840: 6e 74 2b 2b 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 20  nt++;.  }.}../* 
1850: 54 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 28 66  This function (f
1860: 6f 72 20 69 6e 74 65 72 6e 61 6c 20 75 73 65 20  or internal use 
1870: 6f 6e 6c 79 29 20 6c 6f 63 61 74 65 73 20 61 6e  only) locates an
1880: 20 65 6c 65 6d 65 6e 74 20 69 6e 20 61 6e 0a 2a   element in an.*
1890: 2a 20 68 61 73 68 20 74 61 62 6c 65 20 74 68 61  * hash table tha
18a0: 74 20 6d 61 74 63 68 65 73 20 74 68 65 20 67 69  t matches the gi
18b0: 76 65 6e 20 6b 65 79 2e 20 20 54 68 65 20 68 61  ven key.  The ha
18c0: 73 68 20 66 6f 72 20 74 68 69 73 20 6b 65 79 20  sh for this key 
18d0: 68 61 73 0a 2a 2a 20 61 6c 72 65 61 64 79 20 62  has.** already b
18e0: 65 65 6e 20 63 6f 6d 70 75 74 65 64 20 61 6e 64  een computed and
18f0: 20 69 73 20 70 61 73 73 65 64 20 61 73 20 74 68   is passed as th
1900: 65 20 34 74 68 20 70 61 72 61 6d 65 74 65 72 2e  e 4th parameter.
1910: 0a 2a 2f 0a 73 74 61 74 69 63 20 48 61 73 68 45  .*/.static HashE
1920: 6c 65 6d 20 2a 66 69 6e 64 45 6c 65 6d 65 6e 74  lem *findElement
1930: 47 69 76 65 6e 48 61 73 68 28 0a 20 20 63 6f 6e  GivenHash(.  con
1940: 73 74 20 48 61 73 68 20 2a 70 48 2c 20 20 20 20  st Hash *pH,    
1950: 20 2f 2a 20 54 68 65 20 70 48 20 74 6f 20 62 65   /* The pH to be
1960: 20 73 65 61 72 63 68 65 64 20 2a 2f 0a 20 20 63   searched */.  c
1970: 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c  onst void *pKey,
1980: 20 20 20 2f 2a 20 54 68 65 20 6b 65 79 20 77 65     /* The key we
1990: 20 61 72 65 20 73 65 61 72 63 68 69 6e 67 20 66   are searching f
19a0: 6f 72 20 2a 2f 0a 20 20 69 6e 74 20 6e 4b 65 79  or */.  int nKey
19b0: 2c 0a 20 20 69 6e 74 20 68 20 20 20 20 20 20 20  ,.  int h       
19c0: 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 68          /* The h
19d0: 61 73 68 20 66 6f 72 20 74 68 69 73 20 6b 65 79  ash for this key
19e0: 2e 20 2a 2f 0a 29 7b 0a 20 20 48 61 73 68 45 6c  . */.){.  HashEl
19f0: 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 20 20 20  em *elem;       
1a00: 20 20 20 20 20 20 20 20 20 2f 2a 20 55 73 65 64           /* Used
1a10: 20 74 6f 20 6c 6f 6f 70 20 74 68 72 75 20 74 68   to loop thru th
1a20: 65 20 65 6c 65 6d 65 6e 74 20 6c 69 73 74 20 2a  e element list *
1a30: 2f 0a 20 20 69 6e 74 20 63 6f 75 6e 74 3b 20 20  /.  int count;  
1a40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1a50: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
1a60: 65 6c 65 6d 65 6e 74 73 20 6c 65 66 74 20 74 6f  elements left to
1a70: 20 74 65 73 74 20 2a 2f 0a 20 20 69 6e 74 20 28   test */.  int (
1a80: 2a 78 43 6f 6d 70 61 72 65 29 28 63 6f 6e 73 74  *xCompare)(const
1a90: 20 76 6f 69 64 2a 2c 69 6e 74 2c 63 6f 6e 73 74   void*,int,const
1aa0: 20 76 6f 69 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a   void*,int);  /*
1ab0: 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75 6e 63   comparison func
1ac0: 74 69 6f 6e 20 2a 2f 0a 0a 20 20 69 66 28 20 70  tion */..  if( p
1ad0: 48 2d 3e 68 74 20 29 7b 0a 20 20 20 20 65 6c 65  H->ht ){.    ele
1ae0: 6d 20 3d 20 70 48 2d 3e 68 74 5b 68 5d 2e 63 68  m = pH->ht[h].ch
1af0: 61 69 6e 3b 0a 20 20 20 20 63 6f 75 6e 74 20 3d  ain;.    count =
1b00: 20 70 48 2d 3e 68 74 5b 68 5d 2e 63 6f 75 6e 74   pH->ht[h].count
1b10: 3b 0a 20 20 20 20 78 43 6f 6d 70 61 72 65 20 3d  ;.    xCompare =
1b20: 20 63 6f 6d 70 61 72 65 46 75 6e 63 74 69 6f 6e   compareFunction
1b30: 28 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a  (pH->keyClass);.
1b40: 20 20 20 20 77 68 69 6c 65 28 20 63 6f 75 6e 74      while( count
1b50: 2d 2d 20 26 26 20 65 6c 65 6d 20 29 7b 0a 20 20  -- && elem ){.  
1b60: 20 20 20 20 69 66 28 20 28 2a 78 43 6f 6d 70 61      if( (*xCompa
1b70: 72 65 29 28 65 6c 65 6d 2d 3e 70 4b 65 79 2c 65  re)(elem->pKey,e
1b80: 6c 65 6d 2d 3e 6e 4b 65 79 2c 70 4b 65 79 2c 6e  lem->nKey,pKey,n
1b90: 4b 65 79 29 3d 3d 30 20 29 7b 20 0a 20 20 20 20  Key)==0 ){ .    
1ba0: 20 20 20 20 72 65 74 75 72 6e 20 65 6c 65 6d 3b      return elem;
1bb0: 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 65  .      }.      e
1bc0: 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74  lem = elem->next
1bd0: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 72 65  ;.    }.  }.  re
1be0: 74 75 72 6e 20 30 3b 0a 7d 0a 0a 2f 2a 20 52 65  turn 0;.}../* Re
1bf0: 6d 6f 76 65 20 61 20 73 69 6e 67 6c 65 20 65 6e  move a single en
1c00: 74 72 79 20 66 72 6f 6d 20 74 68 65 20 68 61 73  try from the has
1c10: 68 20 74 61 62 6c 65 20 67 69 76 65 6e 20 61 20  h table given a 
1c20: 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 61 74 0a  pointer to that.
1c30: 2a 2a 20 65 6c 65 6d 65 6e 74 20 61 6e 64 20 61  ** element and a
1c40: 20 68 61 73 68 20 6f 6e 20 74 68 65 20 65 6c 65   hash on the ele
1c50: 6d 65 6e 74 27 73 20 6b 65 79 2e 0a 2a 2f 0a 73  ment's key..*/.s
1c60: 74 61 74 69 63 20 76 6f 69 64 20 72 65 6d 6f 76  tatic void remov
1c70: 65 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61 73  eElementGivenHas
1c80: 68 28 0a 20 20 48 61 73 68 20 2a 70 48 2c 20 20  h(.  Hash *pH,  
1c90: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 70 48         /* The pH
1ca0: 20 63 6f 6e 74 61 69 6e 69 6e 67 20 22 65 6c 65   containing "ele
1cb0: 6d 22 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d  m" */.  HashElem
1cc0: 2a 20 65 6c 65 6d 2c 20 20 20 2f 2a 20 54 68 65  * elem,   /* The
1cd0: 20 65 6c 65 6d 65 6e 74 20 74 6f 20 62 65 20 72   element to be r
1ce0: 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74 68 65 20  emoved from the 
1cf0: 70 48 20 2a 2f 0a 20 20 69 6e 74 20 68 20 20 20  pH */.  int h   
1d00: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 48 61 73            /* Has
1d10: 68 20 76 61 6c 75 65 20 66 6f 72 20 74 68 65 20  h value for the 
1d20: 65 6c 65 6d 65 6e 74 20 2a 2f 0a 29 7b 0a 20 20  element */.){.  
1d30: 69 66 28 20 65 6c 65 6d 2d 3e 70 72 65 76 20 29  if( elem->prev )
1d40: 7b 0a 20 20 20 20 65 6c 65 6d 2d 3e 70 72 65 76  {.    elem->prev
1d50: 2d 3e 6e 65 78 74 20 3d 20 65 6c 65 6d 2d 3e 6e  ->next = elem->n
1d60: 65 78 74 3b 20 0a 20 20 7d 65 6c 73 65 7b 0a 20  ext; .  }else{. 
1d70: 20 20 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 65     pH->first = e
1d80: 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20  lem->next;.  }. 
1d90: 20 69 66 28 20 65 6c 65 6d 2d 3e 6e 65 78 74 20   if( elem->next 
1da0: 29 7b 0a 20 20 20 20 65 6c 65 6d 2d 3e 6e 65 78  ){.    elem->nex
1db0: 74 2d 3e 70 72 65 76 20 3d 20 65 6c 65 6d 2d 3e  t->prev = elem->
1dc0: 70 72 65 76 3b 0a 20 20 7d 0a 20 20 69 66 28 20  prev;.  }.  if( 
1dd0: 70 48 2d 3e 68 74 5b 68 5d 2e 63 68 61 69 6e 3d  pH->ht[h].chain=
1de0: 3d 65 6c 65 6d 20 29 7b 0a 20 20 20 20 70 48 2d  =elem ){.    pH-
1df0: 3e 68 74 5b 68 5d 2e 63 68 61 69 6e 20 3d 20 65  >ht[h].chain = e
1e00: 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20  lem->next;.  }. 
1e10: 20 70 48 2d 3e 68 74 5b 68 5d 2e 63 6f 75 6e 74   pH->ht[h].count
1e20: 2d 2d 3b 0a 20 20 69 66 28 20 70 48 2d 3e 68 74  --;.  if( pH->ht
1e30: 5b 68 5d 2e 63 6f 75 6e 74 3c 3d 30 20 29 7b 0a  [h].count<=0 ){.
1e40: 20 20 20 20 70 48 2d 3e 68 74 5b 68 5d 2e 63 68      pH->ht[h].ch
1e50: 61 69 6e 20 3d 20 30 3b 0a 20 20 7d 0a 20 20 69  ain = 0;.  }.  i
1e60: 66 28 20 70 48 2d 3e 63 6f 70 79 4b 65 79 20 26  f( pH->copyKey &
1e70: 26 20 65 6c 65 6d 2d 3e 70 4b 65 79 20 29 7b 0a  & elem->pKey ){.
1e80: 20 20 20 20 73 71 6c 69 74 65 46 72 65 65 28 65      sqliteFree(e
1e90: 6c 65 6d 2d 3e 70 4b 65 79 29 3b 0a 20 20 7d 0a  lem->pKey);.  }.
1ea0: 20 20 73 71 6c 69 74 65 46 72 65 65 28 20 65 6c    sqliteFree( el
1eb0: 65 6d 20 29 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e  em );.  pH->coun
1ec0: 74 2d 2d 3b 0a 7d 0a 0a 2f 2a 20 41 74 74 65 6d  t--;.}../* Attem
1ed0: 70 74 20 74 6f 20 6c 6f 63 61 74 65 20 61 6e 20  pt to locate an 
1ee0: 65 6c 65 6d 65 6e 74 20 6f 66 20 74 68 65 20 68  element of the h
1ef0: 61 73 68 20 74 61 62 6c 65 20 70 48 20 77 69 74  ash table pH wit
1f00: 68 20 61 20 6b 65 79 0a 2a 2a 20 74 68 61 74 20  h a key.** that 
1f10: 6d 61 74 63 68 65 73 20 70 4b 65 79 2c 6e 4b 65  matches pKey,nKe
1f20: 79 2e 20 20 52 65 74 75 72 6e 20 74 68 65 20 64  y.  Return the d
1f30: 61 74 61 20 66 6f 72 20 74 68 69 73 20 65 6c 65  ata for this ele
1f40: 6d 65 6e 74 20 69 66 20 69 74 20 69 73 0a 2a 2a  ment if it is.**
1f50: 20 66 6f 75 6e 64 2c 20 6f 72 20 4e 55 4c 4c 20   found, or NULL 
1f60: 69 66 20 74 68 65 72 65 20 69 73 20 6e 6f 20 6d  if there is no m
1f70: 61 74 63 68 2e 0a 2a 2f 0a 76 6f 69 64 20 2a 73  atch..*/.void *s
1f80: 71 6c 69 74 65 48 61 73 68 46 69 6e 64 28 63 6f  qliteHashFind(co
1f90: 6e 73 74 20 48 61 73 68 20 2a 70 48 2c 20 63 6f  nst Hash *pH, co
1fa0: 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20  nst void *pKey, 
1fb0: 69 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 69 6e 74  int nKey){.  int
1fc0: 20 68 3b 20 20 20 20 20 20 20 20 20 20 20 20 20   h;             
1fd0: 2f 2a 20 41 20 68 61 73 68 20 6f 6e 20 6b 65 79  /* A hash on key
1fe0: 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a   */.  HashElem *
1ff0: 65 6c 65 6d 3b 20 20 20 20 2f 2a 20 54 68 65 20  elem;    /* The 
2000: 65 6c 65 6d 65 6e 74 20 74 68 61 74 20 6d 61 74  element that mat
2010: 63 68 65 73 20 6b 65 79 20 2a 2f 0a 20 20 69 6e  ches key */.  in
2020: 74 20 28 2a 78 48 61 73 68 29 28 63 6f 6e 73 74  t (*xHash)(const
2030: 20 76 6f 69 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a   void*,int);  /*
2040: 20 54 68 65 20 68 61 73 68 20 66 75 6e 63 74 69   The hash functi
2050: 6f 6e 20 2a 2f 0a 0a 20 20 69 66 28 20 70 48 3d  on */..  if( pH=
2060: 3d 30 20 7c 7c 20 70 48 2d 3e 68 74 3d 3d 30 20  =0 || pH->ht==0 
2070: 29 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 78 48  ) return 0;.  xH
2080: 61 73 68 20 3d 20 68 61 73 68 46 75 6e 63 74 69  ash = hashFuncti
2090: 6f 6e 28 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29  on(pH->keyClass)
20a0: 3b 0a 20 20 61 73 73 65 72 74 28 20 78 48 61 73  ;.  assert( xHas
20b0: 68 21 3d 30 20 29 3b 0a 20 20 68 20 3d 20 28 2a  h!=0 );.  h = (*
20c0: 78 48 61 73 68 29 28 70 4b 65 79 2c 6e 4b 65 79  xHash)(pKey,nKey
20d0: 29 3b 0a 20 20 61 73 73 65 72 74 28 20 28 70 48  );.  assert( (pH
20e0: 2d 3e 68 74 73 69 7a 65 20 26 20 28 70 48 2d 3e  ->htsize & (pH->
20f0: 68 74 73 69 7a 65 2d 31 29 29 3d 3d 30 20 29 3b  htsize-1))==0 );
2100: 0a 20 20 65 6c 65 6d 20 3d 20 66 69 6e 64 45 6c  .  elem = findEl
2110: 65 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28 70  ementGivenHash(p
2120: 48 2c 70 4b 65 79 2c 6e 4b 65 79 2c 20 68 20 26  H,pKey,nKey, h &
2130: 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29 29   (pH->htsize-1))
2140: 3b 0a 20 20 72 65 74 75 72 6e 20 65 6c 65 6d 20  ;.  return elem 
2150: 3f 20 65 6c 65 6d 2d 3e 64 61 74 61 20 3a 20 30  ? elem->data : 0
2160: 3b 0a 7d 0a 0a 2f 2a 20 49 6e 73 65 72 74 20 61  ;.}../* Insert a
2170: 6e 20 65 6c 65 6d 65 6e 74 20 69 6e 74 6f 20 74  n element into t
2180: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 70 48  he hash table pH
2190: 2e 20 20 54 68 65 20 6b 65 79 20 69 73 20 70 4b  .  The key is pK
21a0: 65 79 2c 6e 4b 65 79 0a 2a 2a 20 61 6e 64 20 74  ey,nKey.** and t
21b0: 68 65 20 64 61 74 61 20 69 73 20 22 64 61 74 61  he data is "data
21c0: 22 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 6e 6f 20 65  "..**.** If no e
21d0: 6c 65 6d 65 6e 74 20 65 78 69 73 74 73 20 77 69  lement exists wi
21e0: 74 68 20 61 20 6d 61 74 63 68 69 6e 67 20 6b 65  th a matching ke
21f0: 79 2c 20 74 68 65 6e 20 61 20 6e 65 77 0a 2a 2a  y, then a new.**
2200: 20 65 6c 65 6d 65 6e 74 20 69 73 20 63 72 65 61   element is crea
2210: 74 65 64 2e 20 20 41 20 63 6f 70 79 20 6f 66 20  ted.  A copy of 
2220: 74 68 65 20 6b 65 79 20 69 73 20 6d 61 64 65 20  the key is made 
2230: 69 66 20 74 68 65 20 63 6f 70 79 4b 65 79 0a 2a  if the copyKey.*
2240: 2a 20 66 6c 61 67 20 69 73 20 73 65 74 2e 20 20  * flag is set.  
2250: 4e 55 4c 4c 20 69 73 20 72 65 74 75 72 6e 65 64  NULL is returned
2260: 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 61 6e 6f 74 68  ..**.** If anoth
2270: 65 72 20 65 6c 65 6d 65 6e 74 20 61 6c 72 65 61  er element alrea
2280: 64 79 20 65 78 69 73 74 73 20 77 69 74 68 20 74  dy exists with t
2290: 68 65 20 73 61 6d 65 20 6b 65 79 2c 20 74 68 65  he same key, the
22a0: 6e 20 74 68 65 0a 2a 2a 20 6e 65 77 20 64 61 74  n the.** new dat
22b0: 61 20 72 65 70 6c 61 63 65 73 20 74 68 65 20 6f  a replaces the o
22c0: 6c 64 20 64 61 74 61 20 61 6e 64 20 74 68 65 20  ld data and the 
22d0: 6f 6c 64 20 64 61 74 61 20 69 73 20 72 65 74 75  old data is retu
22e0: 72 6e 65 64 2e 0a 2a 2a 20 54 68 65 20 6b 65 79  rned..** The key
22f0: 20 69 73 20 6e 6f 74 20 63 6f 70 69 65 64 20 69   is not copied i
2300: 6e 20 74 68 69 73 20 69 6e 73 74 61 6e 63 65 2e  n this instance.
2310: 20 20 49 66 20 61 20 6d 61 6c 6c 6f 63 20 66 61    If a malloc fa
2320: 69 6c 73 2c 20 74 68 65 6e 0a 2a 2a 20 74 68 65  ils, then.** the
2330: 20 6e 65 77 20 64 61 74 61 20 69 73 20 72 65 74   new data is ret
2340: 75 72 6e 65 64 20 61 6e 64 20 74 68 65 20 68 61  urned and the ha
2350: 73 68 20 74 61 62 6c 65 20 69 73 20 75 6e 63 68  sh table is unch
2360: 61 6e 67 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20  anged..**.** If 
2370: 74 68 65 20 22 64 61 74 61 22 20 70 61 72 61 6d  the "data" param
2380: 65 74 65 72 20 74 6f 20 74 68 69 73 20 66 75 6e  eter to this fun
2390: 63 74 69 6f 6e 20 69 73 20 4e 55 4c 4c 2c 20 74  ction is NULL, t
23a0: 68 65 6e 20 74 68 65 0a 2a 2a 20 65 6c 65 6d 65  hen the.** eleme
23b0: 6e 74 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67  nt corresponding
23c0: 20 74 6f 20 22 6b 65 79 22 20 69 73 20 72 65 6d   to "key" is rem
23d0: 6f 76 65 64 20 66 72 6f 6d 20 74 68 65 20 68 61  oved from the ha
23e0: 73 68 20 74 61 62 6c 65 2e 0a 2a 2f 0a 76 6f 69  sh table..*/.voi
23f0: 64 20 2a 73 71 6c 69 74 65 48 61 73 68 49 6e 73  d *sqliteHashIns
2400: 65 72 74 28 48 61 73 68 20 2a 70 48 2c 20 63 6f  ert(Hash *pH, co
2410: 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20  nst void *pKey, 
2420: 69 6e 74 20 6e 4b 65 79 2c 20 76 6f 69 64 20 2a  int nKey, void *
2430: 64 61 74 61 29 7b 0a 20 20 69 6e 74 20 68 72 61  data){.  int hra
2440: 77 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 2f  w;             /
2450: 2a 20 52 61 77 20 68 61 73 68 20 76 61 6c 75 65  * Raw hash value
2460: 20 6f 66 20 74 68 65 20 6b 65 79 20 2a 2f 0a 20   of the key */. 
2470: 20 69 6e 74 20 68 3b 20 20 20 20 20 20 20 20 20   int h;         
2480: 20 20 20 20 20 20 20 2f 2a 20 74 68 65 20 68 61         /* the ha
2490: 73 68 20 6f 66 20 74 68 65 20 6b 65 79 20 6d 6f  sh of the key mo
24a0: 64 75 6c 6f 20 68 61 73 68 20 74 61 62 6c 65 20  dulo hash table 
24b0: 73 69 7a 65 20 2a 2f 0a 20 20 48 61 73 68 45 6c  size */.  HashEl
24c0: 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 20 20 20  em *elem;       
24d0: 2f 2a 20 55 73 65 64 20 74 6f 20 6c 6f 6f 70 20  /* Used to loop 
24e0: 74 68 72 75 20 74 68 65 20 65 6c 65 6d 65 6e 74  thru the element
24f0: 20 6c 69 73 74 20 2a 2f 0a 20 20 48 61 73 68 45   list */.  HashE
2500: 6c 65 6d 20 2a 6e 65 77 5f 65 6c 65 6d 3b 20 20  lem *new_elem;  
2510: 20 2f 2a 20 4e 65 77 20 65 6c 65 6d 65 6e 74 20   /* New element 
2520: 61 64 64 65 64 20 74 6f 20 74 68 65 20 70 48 20  added to the pH 
2530: 2a 2f 0a 20 20 69 6e 74 20 28 2a 78 48 61 73 68  */.  int (*xHash
2540: 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e  )(const void*,in
2550: 74 29 3b 20 20 2f 2a 20 54 68 65 20 68 61 73 68  t);  /* The hash
2560: 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20   function */..  
2570: 61 73 73 65 72 74 28 20 70 48 21 3d 30 20 29 3b  assert( pH!=0 );
2580: 0a 20 20 78 48 61 73 68 20 3d 20 68 61 73 68 46  .  xHash = hashF
2590: 75 6e 63 74 69 6f 6e 28 70 48 2d 3e 6b 65 79 43  unction(pH->keyC
25a0: 6c 61 73 73 29 3b 0a 20 20 61 73 73 65 72 74 28  lass);.  assert(
25b0: 20 78 48 61 73 68 21 3d 30 20 29 3b 0a 20 20 68   xHash!=0 );.  h
25c0: 72 61 77 20 3d 20 28 2a 78 48 61 73 68 29 28 70  raw = (*xHash)(p
25d0: 4b 65 79 2c 20 6e 4b 65 79 29 3b 0a 20 20 61 73  Key, nKey);.  as
25e0: 73 65 72 74 28 20 28 70 48 2d 3e 68 74 73 69 7a  sert( (pH->htsiz
25f0: 65 20 26 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d  e & (pH->htsize-
2600: 31 29 29 3d 3d 30 20 29 3b 0a 20 20 68 20 3d 20  1))==0 );.  h = 
2610: 68 72 61 77 20 26 20 28 70 48 2d 3e 68 74 73 69  hraw & (pH->htsi
2620: 7a 65 2d 31 29 3b 0a 20 20 65 6c 65 6d 20 3d 20  ze-1);.  elem = 
2630: 66 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65 6e  findElementGiven
2640: 48 61 73 68 28 70 48 2c 70 4b 65 79 2c 6e 4b 65  Hash(pH,pKey,nKe
2650: 79 2c 68 29 3b 0a 20 20 69 66 28 20 65 6c 65 6d  y,h);.  if( elem
2660: 20 29 7b 0a 20 20 20 20 76 6f 69 64 20 2a 6f 6c   ){.    void *ol
2670: 64 5f 64 61 74 61 20 3d 20 65 6c 65 6d 2d 3e 64  d_data = elem->d
2680: 61 74 61 3b 0a 20 20 20 20 69 66 28 20 64 61 74  ata;.    if( dat
2690: 61 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 72 65  a==0 ){.      re
26a0: 6d 6f 76 65 45 6c 65 6d 65 6e 74 47 69 76 65 6e  moveElementGiven
26b0: 48 61 73 68 28 70 48 2c 65 6c 65 6d 2c 68 29 3b  Hash(pH,elem,h);
26c0: 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20  .    }else{.    
26d0: 20 20 65 6c 65 6d 2d 3e 64 61 74 61 20 3d 20 64    elem->data = d
26e0: 61 74 61 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72  ata;.    }.    r
26f0: 65 74 75 72 6e 20 6f 6c 64 5f 64 61 74 61 3b 0a  eturn old_data;.
2700: 20 20 7d 0a 20 20 69 66 28 20 64 61 74 61 3d 3d    }.  if( data==
2710: 30 20 29 20 72 65 74 75 72 6e 20 30 3b 0a 20 20  0 ) return 0;.  
2720: 6e 65 77 5f 65 6c 65 6d 20 3d 20 28 48 61 73 68  new_elem = (Hash
2730: 45 6c 65 6d 2a 29 73 71 6c 69 74 65 4d 61 6c 6c  Elem*)sqliteMall
2740: 6f 63 28 20 73 69 7a 65 6f 66 28 48 61 73 68 45  oc( sizeof(HashE
2750: 6c 65 6d 29 20 29 3b 0a 20 20 69 66 28 20 6e 65  lem) );.  if( ne
2760: 77 5f 65 6c 65 6d 3d 3d 30 20 29 20 72 65 74 75  w_elem==0 ) retu
2770: 72 6e 20 64 61 74 61 3b 0a 20 20 69 66 28 20 70  rn data;.  if( p
2780: 48 2d 3e 63 6f 70 79 4b 65 79 20 26 26 20 70 4b  H->copyKey && pK
2790: 65 79 21 3d 30 20 29 7b 0a 20 20 20 20 6e 65 77  ey!=0 ){.    new
27a0: 5f 65 6c 65 6d 2d 3e 70 4b 65 79 20 3d 20 73 71  _elem->pKey = sq
27b0: 6c 69 74 65 4d 61 6c 6c 6f 63 52 61 77 28 20 6e  liteMallocRaw( n
27c0: 4b 65 79 20 29 3b 0a 20 20 20 20 69 66 28 20 6e  Key );.    if( n
27d0: 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 3d 3d 30  ew_elem->pKey==0
27e0: 20 29 7b 0a 20 20 20 20 20 20 73 71 6c 69 74 65   ){.      sqlite
27f0: 46 72 65 65 28 6e 65 77 5f 65 6c 65 6d 29 3b 0a  Free(new_elem);.
2800: 20 20 20 20 20 20 72 65 74 75 72 6e 20 64 61 74        return dat
2810: 61 3b 0a 20 20 20 20 7d 0a 20 20 20 20 6d 65 6d  a;.    }.    mem
2820: 63 70 79 28 28 76 6f 69 64 2a 29 6e 65 77 5f 65  cpy((void*)new_e
2830: 6c 65 6d 2d 3e 70 4b 65 79 2c 20 70 4b 65 79 2c  lem->pKey, pKey,
2840: 20 6e 4b 65 79 29 3b 0a 20 20 7d 65 6c 73 65 7b   nKey);.  }else{
2850: 0a 20 20 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70  .    new_elem->p
2860: 4b 65 79 20 3d 20 28 76 6f 69 64 2a 29 70 4b 65  Key = (void*)pKe
2870: 79 3b 0a 20 20 7d 0a 20 20 6e 65 77 5f 65 6c 65  y;.  }.  new_ele
2880: 6d 2d 3e 6e 4b 65 79 20 3d 20 6e 4b 65 79 3b 0a  m->nKey = nKey;.
2890: 20 20 70 48 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20    pH->count++;. 
28a0: 20 69 66 28 20 70 48 2d 3e 68 74 73 69 7a 65 3d   if( pH->htsize=
28b0: 3d 30 20 29 20 72 65 68 61 73 68 28 70 48 2c 38  =0 ) rehash(pH,8
28c0: 29 3b 0a 20 20 69 66 28 20 70 48 2d 3e 68 74 73  );.  if( pH->hts
28d0: 69 7a 65 3d 3d 30 20 29 7b 0a 20 20 20 20 70 48  ize==0 ){.    pH
28e0: 2d 3e 63 6f 75 6e 74 20 3d 20 30 3b 0a 20 20 20  ->count = 0;.   
28f0: 20 73 71 6c 69 74 65 46 72 65 65 28 6e 65 77 5f   sqliteFree(new_
2900: 65 6c 65 6d 29 3b 0a 20 20 20 20 72 65 74 75 72  elem);.    retur
2910: 6e 20 64 61 74 61 3b 0a 20 20 7d 0a 20 20 69 66  n data;.  }.  if
2920: 28 20 70 48 2d 3e 63 6f 75 6e 74 20 3e 20 70 48  ( pH->count > pH
2930: 2d 3e 68 74 73 69 7a 65 20 29 7b 0a 20 20 20 20  ->htsize ){.    
2940: 72 65 68 61 73 68 28 70 48 2c 70 48 2d 3e 68 74  rehash(pH,pH->ht
2950: 73 69 7a 65 2a 32 29 3b 0a 20 20 7d 0a 20 20 61  size*2);.  }.  a
2960: 73 73 65 72 74 28 20 28 70 48 2d 3e 68 74 73 69  ssert( (pH->htsi
2970: 7a 65 20 26 20 28 70 48 2d 3e 68 74 73 69 7a 65  ze & (pH->htsize
2980: 2d 31 29 29 3d 3d 30 20 29 3b 0a 20 20 68 20 3d  -1))==0 );.  h =
2990: 20 68 72 61 77 20 26 20 28 70 48 2d 3e 68 74 73   hraw & (pH->hts
29a0: 69 7a 65 2d 31 29 3b 0a 20 20 65 6c 65 6d 20 3d  ize-1);.  elem =
29b0: 20 70 48 2d 3e 68 74 5b 68 5d 2e 63 68 61 69 6e   pH->ht[h].chain
29c0: 3b 0a 20 20 69 66 28 20 65 6c 65 6d 20 29 7b 0a  ;.  if( elem ){.
29d0: 20 20 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 6e 65      new_elem->ne
29e0: 78 74 20 3d 20 65 6c 65 6d 3b 0a 20 20 20 20 6e  xt = elem;.    n
29f0: 65 77 5f 65 6c 65 6d 2d 3e 70 72 65 76 20 3d 20  ew_elem->prev = 
2a00: 65 6c 65 6d 2d 3e 70 72 65 76 3b 0a 20 20 20 20  elem->prev;.    
2a10: 69 66 28 20 65 6c 65 6d 2d 3e 70 72 65 76 20 29  if( elem->prev )
2a20: 7b 20 65 6c 65 6d 2d 3e 70 72 65 76 2d 3e 6e 65  { elem->prev->ne
2a30: 78 74 20 3d 20 6e 65 77 5f 65 6c 65 6d 3b 20 7d  xt = new_elem; }
2a40: 0a 20 20 20 20 65 6c 73 65 20 20 20 20 20 20 20  .    else       
2a50: 20 20 20 20 20 7b 20 70 48 2d 3e 66 69 72 73 74       { pH->first
2a60: 20 3d 20 6e 65 77 5f 65 6c 65 6d 3b 20 7d 0a 20   = new_elem; }. 
2a70: 20 20 20 65 6c 65 6d 2d 3e 70 72 65 76 20 3d 20     elem->prev = 
2a80: 6e 65 77 5f 65 6c 65 6d 3b 0a 20 20 7d 65 6c 73  new_elem;.  }els
2a90: 65 7b 0a 20 20 20 20 6e 65 77 5f 65 6c 65 6d 2d  e{.    new_elem-
2aa0: 3e 6e 65 78 74 20 3d 20 70 48 2d 3e 66 69 72 73  >next = pH->firs
2ab0: 74 3b 0a 20 20 20 20 6e 65 77 5f 65 6c 65 6d 2d  t;.    new_elem-
2ac0: 3e 70 72 65 76 20 3d 20 30 3b 0a 20 20 20 20 69  >prev = 0;.    i
2ad0: 66 28 20 70 48 2d 3e 66 69 72 73 74 20 29 7b 20  f( pH->first ){ 
2ae0: 70 48 2d 3e 66 69 72 73 74 2d 3e 70 72 65 76 20  pH->first->prev 
2af0: 3d 20 6e 65 77 5f 65 6c 65 6d 3b 20 7d 0a 20 20  = new_elem; }.  
2b00: 20 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 6e 65    pH->first = ne
2b10: 77 5f 65 6c 65 6d 3b 0a 20 20 7d 0a 20 20 70 48  w_elem;.  }.  pH
2b20: 2d 3e 68 74 5b 68 5d 2e 63 6f 75 6e 74 2b 2b 3b  ->ht[h].count++;
2b30: 0a 20 20 70 48 2d 3e 68 74 5b 68 5d 2e 63 68 61  .  pH->ht[h].cha
2b40: 69 6e 20 3d 20 6e 65 77 5f 65 6c 65 6d 3b 0a 20  in = new_elem;. 
2b50: 20 6e 65 77 5f 65 6c 65 6d 2d 3e 64 61 74 61 20   new_elem->data 
2b60: 3d 20 64 61 74 61 3b 0a 20 20 72 65 74 75 72 6e  = data;.  return
2b70: 20 30 3b 0a 7d 0a                                 0;.}.