/ Hex Artifact Content
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

Artifact 440c2f8cb373ee1b4e13a0988489c7cd95d55b6f:


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 32 20 32 30 30 34 2f 30 35 2f  ,v 1.12 2004/05/
01e0: 30 38 20 30 38 3a 32 33 3a 32 35 20 64 61 6e 69  08 08:23:25 dani
01f0: 65 6c 6b 31 39 37 37 20 45 78 70 20 24 0a 2a 2f  elk1977 Exp $.*/
0200: 0a 23 69 6e 63 6c 75 64 65 20 22 73 71 6c 69 74  .#include "sqlit
0210: 65 49 6e 74 2e 68 22 0a 23 69 6e 63 6c 75 64 65  eInt.h".#include
0220: 20 3c 61 73 73 65 72 74 2e 68 3e 0a 0a 2f 2a 20   <assert.h>../* 
0230: 54 75 72 6e 20 62 75 6c 6b 20 6d 65 6d 6f 72 79  Turn bulk memory
0240: 20 69 6e 74 6f 20 61 20 68 61 73 68 20 74 61 62   into a hash tab
0250: 6c 65 20 6f 62 6a 65 63 74 20 62 79 20 69 6e 69  le object by ini
0260: 74 69 61 6c 69 7a 69 6e 67 20 74 68 65 0a 2a 2a  tializing the.**
0270: 20 66 69 65 6c 64 73 20 6f 66 20 74 68 65 20 48   fields of the H
0280: 61 73 68 20 73 74 72 75 63 74 75 72 65 2e 0a 2a  ash structure..*
0290: 2a 0a 2a 2a 20 22 6e 65 77 22 20 69 73 20 61 20  *.** "new" is a 
02a0: 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 20 68  pointer to the h
02b0: 61 73 68 20 74 61 62 6c 65 20 74 68 61 74 20 69  ash table that i
02c0: 73 20 74 6f 20 62 65 20 69 6e 69 74 69 61 6c 69  s to be initiali
02d0: 7a 65 64 2e 0a 2a 2a 20 6b 65 79 43 6c 61 73 73  zed..** keyClass
02e0: 20 69 73 20 6f 6e 65 20 6f 66 20 74 68 65 20 63   is one of the c
02f0: 6f 6e 73 74 61 6e 74 73 20 53 51 4c 49 54 45 5f  onstants SQLITE_
0300: 48 41 53 48 5f 49 4e 54 2c 20 53 51 4c 49 54 45  HASH_INT, SQLITE
0310: 5f 48 41 53 48 5f 50 4f 49 4e 54 45 52 2c 0a 2a  _HASH_POINTER,.*
0320: 2a 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 42 49  * SQLITE_HASH_BI
0330: 4e 41 52 59 2c 20 6f 72 20 53 51 4c 49 54 45 5f  NARY, or SQLITE_
0340: 48 41 53 48 5f 53 54 52 49 4e 47 2e 20 20 54 68  HASH_STRING.  Th
0350: 65 20 76 61 6c 75 65 20 6f 66 20 6b 65 79 43 6c  e value of keyCl
0360: 61 73 73 20 0a 2a 2a 20 64 65 74 65 72 6d 69 6e  ass .** determin
0370: 65 73 20 77 68 61 74 20 6b 69 6e 64 20 6f 66 20  es what kind of 
0380: 6b 65 79 20 74 68 65 20 68 61 73 68 20 74 61 62  key the hash tab
0390: 6c 65 20 77 69 6c 6c 20 75 73 65 2e 20 20 22 63  le will use.  "c
03a0: 6f 70 79 4b 65 79 22 20 69 73 0a 2a 2a 20 74 72  opyKey" is.** tr
03b0: 75 65 20 69 66 20 74 68 65 20 68 61 73 68 20 74  ue if the hash t
03c0: 61 62 6c 65 20 73 68 6f 75 6c 64 20 6d 61 6b 65  able should make
03d0: 20 69 74 73 20 6f 77 6e 20 70 72 69 76 61 74 65   its own private
03e0: 20 63 6f 70 79 20 6f 66 20 6b 65 79 73 20 61 6e   copy of keys an
03f0: 64 0a 2a 2a 20 66 61 6c 73 65 20 69 66 20 69 74  d.** false if it
0400: 20 73 68 6f 75 6c 64 20 6a 75 73 74 20 75 73 65   should just use
0410: 20 74 68 65 20 73 75 70 70 6c 69 65 64 20 70 6f   the supplied po
0420: 69 6e 74 65 72 2e 20 20 43 6f 70 79 4b 65 79 20  inter.  CopyKey 
0430: 6f 6e 6c 79 20 6d 61 6b 65 73 0a 2a 2a 20 73 65  only makes.** se
0440: 6e 73 65 20 66 6f 72 20 53 51 4c 49 54 45 5f 48  nse for SQLITE_H
0450: 41 53 48 5f 53 54 52 49 4e 47 20 61 6e 64 20 53  ASH_STRING and S
0460: 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e 41 52  QLITE_HASH_BINAR
0470: 59 20 61 6e 64 20 69 73 20 69 67 6e 6f 72 65 64  Y and is ignored
0480: 0a 2a 2a 20 66 6f 72 20 6f 74 68 65 72 20 6b 65  .** for other ke
0490: 79 20 63 6c 61 73 73 65 73 2e 0a 2a 2f 0a 76 6f  y classes..*/.vo
04a0: 69 64 20 73 71 6c 69 74 65 33 48 61 73 68 49 6e  id sqlite3HashIn
04b0: 69 74 28 48 61 73 68 20 2a 6e 65 77 2c 20 69 6e  it(Hash *new, in
04c0: 74 20 6b 65 79 43 6c 61 73 73 2c 20 69 6e 74 20  t keyClass, int 
04d0: 63 6f 70 79 4b 65 79 29 7b 0a 20 20 61 73 73 65  copyKey){.  asse
04e0: 72 74 28 20 6e 65 77 21 3d 30 20 29 3b 0a 20 20  rt( new!=0 );.  
04f0: 61 73 73 65 72 74 28 20 6b 65 79 43 6c 61 73 73  assert( keyClass
0500: 3e 3d 53 51 4c 49 54 45 5f 48 41 53 48 5f 49 4e  >=SQLITE_HASH_IN
0510: 54 20 26 26 20 6b 65 79 43 6c 61 73 73 3c 3d 53  T && keyClass<=S
0520: 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e 41 52  QLITE_HASH_BINAR
0530: 59 20 29 3b 0a 20 20 6e 65 77 2d 3e 6b 65 79 43  Y );.  new->keyC
0540: 6c 61 73 73 20 3d 20 6b 65 79 43 6c 61 73 73 3b  lass = keyClass;
0550: 0a 20 20 6e 65 77 2d 3e 63 6f 70 79 4b 65 79 20  .  new->copyKey 
0560: 3d 20 63 6f 70 79 4b 65 79 20 26 26 0a 20 20 20  = copyKey &&.   
0570: 20 20 20 20 20 20 20 20 20 20 20 20 20 28 6b 65               (ke
0580: 79 43 6c 61 73 73 3d 3d 53 51 4c 49 54 45 5f 48  yClass==SQLITE_H
0590: 41 53 48 5f 53 54 52 49 4e 47 20 7c 7c 20 6b 65  ASH_STRING || ke
05a0: 79 43 6c 61 73 73 3d 3d 53 51 4c 49 54 45 5f 48  yClass==SQLITE_H
05b0: 41 53 48 5f 42 49 4e 41 52 59 29 3b 0a 20 20 6e  ASH_BINARY);.  n
05c0: 65 77 2d 3e 66 69 72 73 74 20 3d 20 30 3b 0a 20  ew->first = 0;. 
05d0: 20 6e 65 77 2d 3e 63 6f 75 6e 74 20 3d 20 30 3b   new->count = 0;
05e0: 0a 20 20 6e 65 77 2d 3e 68 74 73 69 7a 65 20 3d  .  new->htsize =
05f0: 20 30 3b 0a 20 20 6e 65 77 2d 3e 68 74 20 3d 20   0;.  new->ht = 
0600: 30 3b 0a 7d 0a 0a 2f 2a 20 52 65 6d 6f 76 65 20  0;.}../* Remove 
0610: 61 6c 6c 20 65 6e 74 72 69 65 73 20 66 72 6f 6d  all entries from
0620: 20 61 20 68 61 73 68 20 74 61 62 6c 65 2e 20 20   a hash table.  
0630: 52 65 63 6c 61 69 6d 20 61 6c 6c 20 6d 65 6d 6f  Reclaim all memo
0640: 72 79 2e 0a 2a 2a 20 43 61 6c 6c 20 74 68 69 73  ry..** Call this
0650: 20 72 6f 75 74 69 6e 65 20 74 6f 20 64 65 6c 65   routine to dele
0660: 74 65 20 61 20 68 61 73 68 20 74 61 62 6c 65 20  te a hash table 
0670: 6f 72 20 74 6f 20 72 65 73 65 74 20 61 20 68 61  or to reset a ha
0680: 73 68 20 74 61 62 6c 65 0a 2a 2a 20 74 6f 20 74  sh table.** to t
0690: 68 65 20 65 6d 70 74 79 20 73 74 61 74 65 2e 0a  he empty state..
06a0: 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 48  */.void sqlite3H
06b0: 61 73 68 43 6c 65 61 72 28 48 61 73 68 20 2a 70  ashClear(Hash *p
06c0: 48 29 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a  H){.  HashElem *
06d0: 65 6c 65 6d 3b 20 20 20 20 20 20 20 20 20 2f 2a  elem;         /*
06e0: 20 46 6f 72 20 6c 6f 6f 70 69 6e 67 20 6f 76 65   For looping ove
06f0: 72 20 61 6c 6c 20 65 6c 65 6d 65 6e 74 73 20 6f  r all elements o
0700: 66 20 74 68 65 20 74 61 62 6c 65 20 2a 2f 0a 0a  f the table */..
0710: 20 20 61 73 73 65 72 74 28 20 70 48 21 3d 30 20    assert( pH!=0 
0720: 29 3b 0a 20 20 65 6c 65 6d 20 3d 20 70 48 2d 3e  );.  elem = pH->
0730: 66 69 72 73 74 3b 0a 20 20 70 48 2d 3e 66 69 72  first;.  pH->fir
0740: 73 74 20 3d 20 30 3b 0a 20 20 69 66 28 20 70 48  st = 0;.  if( pH
0750: 2d 3e 68 74 20 29 20 73 71 6c 69 74 65 46 72 65  ->ht ) sqliteFre
0760: 65 28 70 48 2d 3e 68 74 29 3b 0a 20 20 70 48 2d  e(pH->ht);.  pH-
0770: 3e 68 74 20 3d 20 30 3b 0a 20 20 70 48 2d 3e 68  >ht = 0;.  pH->h
0780: 74 73 69 7a 65 20 3d 20 30 3b 0a 20 20 77 68 69  tsize = 0;.  whi
0790: 6c 65 28 20 65 6c 65 6d 20 29 7b 0a 20 20 20 20  le( elem ){.    
07a0: 48 61 73 68 45 6c 65 6d 20 2a 6e 65 78 74 5f 65  HashElem *next_e
07b0: 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74  lem = elem->next
07c0: 3b 0a 20 20 20 20 69 66 28 20 70 48 2d 3e 63 6f  ;.    if( pH->co
07d0: 70 79 4b 65 79 20 26 26 20 65 6c 65 6d 2d 3e 70  pyKey && elem->p
07e0: 4b 65 79 20 29 7b 0a 20 20 20 20 20 20 73 71 6c  Key ){.      sql
07f0: 69 74 65 46 72 65 65 28 65 6c 65 6d 2d 3e 70 4b  iteFree(elem->pK
0800: 65 79 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 73  ey);.    }.    s
0810: 71 6c 69 74 65 46 72 65 65 28 65 6c 65 6d 29 3b  qliteFree(elem);
0820: 0a 20 20 20 20 65 6c 65 6d 20 3d 20 6e 65 78 74  .    elem = next
0830: 5f 65 6c 65 6d 3b 0a 20 20 7d 0a 20 20 70 48 2d  _elem;.  }.  pH-
0840: 3e 63 6f 75 6e 74 20 3d 20 30 3b 0a 7d 0a 0a 2f  >count = 0;.}../
0850: 2a 0a 2a 2a 20 48 61 73 68 20 61 6e 64 20 63 6f  *.** Hash and co
0860: 6d 70 61 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f  mparison functio
0870: 6e 73 20 77 68 65 6e 20 74 68 65 20 6d 6f 64 65  ns when the mode
0880: 20 69 73 20 53 51 4c 49 54 45 5f 48 41 53 48 5f   is SQLITE_HASH_
0890: 49 4e 54 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e  INT.*/.static in
08a0: 74 20 69 6e 74 48 61 73 68 28 63 6f 6e 73 74 20  t intHash(const 
08b0: 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20  void *pKey, int 
08c0: 6e 4b 65 79 29 7b 0a 20 20 72 65 74 75 72 6e 20  nKey){.  return 
08d0: 6e 4b 65 79 20 5e 20 28 6e 4b 65 79 3c 3c 38 29  nKey ^ (nKey<<8)
08e0: 20 5e 20 28 6e 4b 65 79 3e 3e 38 29 3b 0a 7d 0a   ^ (nKey>>8);.}.
08f0: 73 74 61 74 69 63 20 69 6e 74 20 69 6e 74 43 6f  static int intCo
0900: 6d 70 61 72 65 28 63 6f 6e 73 74 20 76 6f 69 64  mpare(const void
0910: 20 2a 70 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c   *pKey1, int n1,
0920: 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65   const void *pKe
0930: 79 32 2c 20 69 6e 74 20 6e 32 29 7b 0a 20 20 72  y2, int n2){.  r
0940: 65 74 75 72 6e 20 6e 32 20 2d 20 6e 31 3b 0a 7d  eturn n2 - n1;.}
0950: 0a 0a 23 69 66 20 30 20 2f 2a 20 4e 4f 54 20 55  ..#if 0 /* NOT U
0960: 53 45 44 20 2a 2f 0a 2f 2a 0a 2a 2a 20 48 61 73  SED */./*.** Has
0970: 68 20 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e  h and comparison
0980: 20 66 75 6e 63 74 69 6f 6e 73 20 77 68 65 6e 20   functions when 
0990: 74 68 65 20 6d 6f 64 65 20 69 73 20 53 51 4c 49  the mode is SQLI
09a0: 54 45 5f 48 41 53 48 5f 50 4f 49 4e 54 45 52 0a  TE_HASH_POINTER.
09b0: 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 70 74  */.static int pt
09c0: 72 48 61 73 68 28 63 6f 6e 73 74 20 76 6f 69 64  rHash(const void
09d0: 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79   *pKey, int nKey
09e0: 29 7b 0a 20 20 75 70 74 72 20 78 20 3d 20 41 64  ){.  uptr x = Ad
09f0: 64 72 28 70 4b 65 79 29 3b 0a 20 20 72 65 74 75  dr(pKey);.  retu
0a00: 72 6e 20 78 20 5e 20 28 78 3c 3c 38 29 20 5e 20  rn x ^ (x<<8) ^ 
0a10: 28 78 3e 3e 38 29 3b 0a 7d 0a 73 74 61 74 69 63  (x>>8);.}.static
0a20: 20 69 6e 74 20 70 74 72 43 6f 6d 70 61 72 65 28   int ptrCompare(
0a30: 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79  const void *pKey
0a40: 31 2c 20 69 6e 74 20 6e 31 2c 20 63 6f 6e 73 74  1, int n1, const
0a50: 20 76 6f 69 64 20 2a 70 4b 65 79 32 2c 20 69 6e   void *pKey2, in
0a60: 74 20 6e 32 29 7b 0a 20 20 69 66 28 20 70 4b 65  t n2){.  if( pKe
0a70: 79 31 3d 3d 70 4b 65 79 32 20 29 20 72 65 74 75  y1==pKey2 ) retu
0a80: 72 6e 20 30 3b 0a 20 20 69 66 28 20 70 4b 65 79  rn 0;.  if( pKey
0a90: 31 3c 70 4b 65 79 32 20 29 20 72 65 74 75 72 6e  1<pKey2 ) return
0aa0: 20 2d 31 3b 0a 20 20 72 65 74 75 72 6e 20 31 3b   -1;.  return 1;
0ab0: 0a 7d 0a 23 65 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a  .}.#endif../*.**
0ac0: 20 48 61 73 68 20 61 6e 64 20 63 6f 6d 70 61 72   Hash and compar
0ad0: 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 20 77  ison functions w
0ae0: 68 65 6e 20 74 68 65 20 6d 6f 64 65 20 69 73 20  hen the mode is 
0af0: 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 49  SQLITE_HASH_STRI
0b00: 4e 47 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74  NG.*/.static int
0b10: 20 73 74 72 48 61 73 68 28 63 6f 6e 73 74 20 76   strHash(const v
0b20: 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e  oid *pKey, int n
0b30: 4b 65 79 29 7b 0a 20 20 72 65 74 75 72 6e 20 73  Key){.  return s
0b40: 71 6c 69 74 65 33 48 61 73 68 4e 6f 43 61 73 65  qlite3HashNoCase
0b50: 28 28 63 6f 6e 73 74 20 63 68 61 72 2a 29 70 4b  ((const char*)pK
0b60: 65 79 2c 20 6e 4b 65 79 29 3b 20 0a 7d 0a 73 74  ey, nKey); .}.st
0b70: 61 74 69 63 20 69 6e 74 20 73 74 72 43 6f 6d 70  atic int strComp
0b80: 61 72 65 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a  are(const void *
0b90: 70 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c 20 63  pKey1, int n1, c
0ba0: 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 32  onst void *pKey2
0bb0: 2c 20 69 6e 74 20 6e 32 29 7b 0a 20 20 69 66 28  , int n2){.  if(
0bc0: 20 6e 31 21 3d 6e 32 20 29 20 72 65 74 75 72 6e   n1!=n2 ) return
0bd0: 20 6e 32 2d 6e 31 3b 0a 20 20 72 65 74 75 72 6e   n2-n1;.  return
0be0: 20 73 71 6c 69 74 65 33 53 74 72 4e 49 43 6d 70   sqlite3StrNICmp
0bf0: 28 28 63 6f 6e 73 74 20 63 68 61 72 2a 29 70 4b  ((const char*)pK
0c00: 65 79 31 2c 28 63 6f 6e 73 74 20 63 68 61 72 2a  ey1,(const char*
0c10: 29 70 4b 65 79 32 2c 6e 31 29 3b 0a 7d 0a 0a 2f  )pKey2,n1);.}../
0c20: 2a 0a 2a 2a 20 48 61 73 68 20 61 6e 64 20 63 6f  *.** Hash and co
0c30: 6d 70 61 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f  mparison functio
0c40: 6e 73 20 77 68 65 6e 20 74 68 65 20 6d 6f 64 65  ns when the mode
0c50: 20 69 73 20 53 51 4c 49 54 45 5f 48 41 53 48 5f   is SQLITE_HASH_
0c60: 42 49 4e 41 52 59 0a 2a 2f 0a 73 74 61 74 69 63  BINARY.*/.static
0c70: 20 69 6e 74 20 62 69 6e 48 61 73 68 28 63 6f 6e   int binHash(con
0c80: 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69  st void *pKey, i
0c90: 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 69 6e 74 20  nt nKey){.  int 
0ca0: 68 20 3d 20 30 3b 0a 20 20 63 6f 6e 73 74 20 63  h = 0;.  const c
0cb0: 68 61 72 20 2a 7a 20 3d 20 28 63 6f 6e 73 74 20  har *z = (const 
0cc0: 63 68 61 72 20 2a 29 70 4b 65 79 3b 0a 20 20 77  char *)pKey;.  w
0cd0: 68 69 6c 65 28 20 6e 4b 65 79 2d 2d 20 3e 20 30  hile( nKey-- > 0
0ce0: 20 29 7b 0a 20 20 20 20 68 20 3d 20 28 68 3c 3c   ){.    h = (h<<
0cf0: 33 29 20 5e 20 68 20 5e 20 2a 28 7a 2b 2b 29 3b  3) ^ h ^ *(z++);
0d00: 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 68 20  .  }.  return h 
0d10: 26 20 30 78 37 66 66 66 66 66 66 66 3b 0a 7d 0a  & 0x7fffffff;.}.
0d20: 73 74 61 74 69 63 20 69 6e 74 20 62 69 6e 43 6f  static int binCo
0d30: 6d 70 61 72 65 28 63 6f 6e 73 74 20 76 6f 69 64  mpare(const void
0d40: 20 2a 70 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c   *pKey1, int n1,
0d50: 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65   const void *pKe
0d60: 79 32 2c 20 69 6e 74 20 6e 32 29 7b 0a 20 20 69  y2, int n2){.  i
0d70: 66 28 20 6e 31 21 3d 6e 32 20 29 20 72 65 74 75  f( n1!=n2 ) retu
0d80: 72 6e 20 6e 32 2d 6e 31 3b 0a 20 20 72 65 74 75  rn n2-n1;.  retu
0d90: 72 6e 20 6d 65 6d 63 6d 70 28 70 4b 65 79 31 2c  rn memcmp(pKey1,
0da0: 70 4b 65 79 32 2c 6e 31 29 3b 0a 7d 0a 0a 2f 2a  pKey2,n1);.}../*
0db0: 0a 2a 2a 20 52 65 74 75 72 6e 20 61 20 70 6f 69  .** Return a poi
0dc0: 6e 74 65 72 20 74 6f 20 74 68 65 20 61 70 70 72  nter to the appr
0dd0: 6f 70 72 69 61 74 65 20 68 61 73 68 20 66 75 6e  opriate hash fun
0de0: 63 74 69 6f 6e 20 67 69 76 65 6e 20 74 68 65 20  ction given the 
0df0: 6b 65 79 20 63 6c 61 73 73 2e 0a 2a 2a 0a 2a 2a  key class..**.**
0e00: 20 54 68 65 20 43 20 73 79 6e 74 61 78 20 69 6e   The C syntax in
0e10: 20 74 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 64   this function d
0e20: 65 66 69 6e 69 74 69 6f 6e 20 6d 61 79 20 62 65  efinition may be
0e30: 20 75 6e 66 61 6d 69 6c 61 72 20 74 6f 20 73 6f   unfamilar to so
0e40: 6d 65 20 0a 2a 2a 20 70 72 6f 67 72 61 6d 6d 65  me .** programme
0e50: 72 73 2c 20 73 6f 20 77 65 20 70 72 6f 76 69 64  rs, so we provid
0e60: 65 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20  e the following 
0e70: 61 64 64 69 74 69 6f 6e 61 6c 20 65 78 70 6c 61  additional expla
0e80: 6e 61 74 69 6f 6e 3a 0a 2a 2a 0a 2a 2a 20 54 68  nation:.**.** Th
0e90: 65 20 6e 61 6d 65 20 6f 66 20 74 68 65 20 66 75  e name of the fu
0ea0: 6e 63 74 69 6f 6e 20 69 73 20 22 68 61 73 68 46  nction is "hashF
0eb0: 75 6e 63 74 69 6f 6e 22 2e 20 20 54 68 65 20 66  unction".  The f
0ec0: 75 6e 63 74 69 6f 6e 20 74 61 6b 65 73 20 61 0a  unction takes a.
0ed0: 2a 2a 20 73 69 6e 67 6c 65 20 70 61 72 61 6d 65  ** single parame
0ee0: 74 65 72 20 22 6b 65 79 43 6c 61 73 73 22 2e 20  ter "keyClass". 
0ef0: 20 54 68 65 20 72 65 74 75 72 6e 20 76 61 6c 75   The return valu
0f00: 65 20 6f 66 20 68 61 73 68 46 75 6e 63 74 69 6f  e of hashFunctio
0f10: 6e 28 29 0a 2a 2a 20 69 73 20 61 20 70 6f 69 6e  n().** is a poin
0f20: 74 65 72 20 74 6f 20 61 6e 6f 74 68 65 72 20 66  ter to another f
0f30: 75 6e 63 74 69 6f 6e 2e 20 20 53 70 65 63 69 66  unction.  Specif
0f40: 69 63 61 6c 6c 79 2c 20 74 68 65 20 72 65 74 75  ically, the retu
0f50: 72 6e 20 76 61 6c 75 65 0a 2a 2a 20 6f 66 20 68  rn value.** of h
0f60: 61 73 68 46 75 6e 63 74 69 6f 6e 28 29 20 69 73  ashFunction() is
0f70: 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 20   a pointer to a 
0f80: 66 75 6e 63 74 69 6f 6e 20 74 68 61 74 20 74 61  function that ta
0f90: 6b 65 73 20 74 77 6f 20 70 61 72 61 6d 65 74 65  kes two paramete
0fa0: 72 73 0a 2a 2a 20 77 69 74 68 20 74 79 70 65 73  rs.** with types
0fb0: 20 22 63 6f 6e 73 74 20 76 6f 69 64 2a 22 20 61   "const void*" a
0fc0: 6e 64 20 22 69 6e 74 22 20 61 6e 64 20 72 65 74  nd "int" and ret
0fd0: 75 72 6e 73 20 61 6e 20 22 69 6e 74 22 2e 0a 2a  urns an "int"..*
0fe0: 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 28 2a 68  /.static int (*h
0ff0: 61 73 68 46 75 6e 63 74 69 6f 6e 28 69 6e 74 20  ashFunction(int 
1000: 6b 65 79 43 6c 61 73 73 29 29 28 63 6f 6e 73 74  keyClass))(const
1010: 20 76 6f 69 64 2a 2c 69 6e 74 29 7b 0a 20 20 73   void*,int){.  s
1020: 77 69 74 63 68 28 20 6b 65 79 43 6c 61 73 73 20  witch( keyClass 
1030: 29 7b 0a 20 20 20 20 63 61 73 65 20 53 51 4c 49  ){.    case SQLI
1040: 54 45 5f 48 41 53 48 5f 49 4e 54 3a 20 20 20 20  TE_HASH_INT:    
1050: 20 72 65 74 75 72 6e 20 26 69 6e 74 48 61 73 68   return &intHash
1060: 3b 0a 20 20 20 20 2f 2a 20 63 61 73 65 20 53 51  ;.    /* case SQ
1070: 4c 49 54 45 5f 48 41 53 48 5f 50 4f 49 4e 54 45  LITE_HASH_POINTE
1080: 52 3a 20 72 65 74 75 72 6e 20 26 70 74 72 48 61  R: return &ptrHa
1090: 73 68 3b 20 2f 2f 20 4e 4f 54 20 55 53 45 44 20  sh; // NOT USED 
10a0: 2a 2f 0a 20 20 20 20 63 61 73 65 20 53 51 4c 49  */.    case SQLI
10b0: 54 45 5f 48 41 53 48 5f 53 54 52 49 4e 47 3a 20  TE_HASH_STRING: 
10c0: 20 72 65 74 75 72 6e 20 26 73 74 72 48 61 73 68   return &strHash
10d0: 3b 0a 20 20 20 20 63 61 73 65 20 53 51 4c 49 54  ;.    case SQLIT
10e0: 45 5f 48 41 53 48 5f 42 49 4e 41 52 59 3a 20 20  E_HASH_BINARY:  
10f0: 72 65 74 75 72 6e 20 26 62 69 6e 48 61 73 68 3b  return &binHash;
1100: 3b 0a 20 20 20 20 64 65 66 61 75 6c 74 3a 20 62  ;.    default: b
1110: 72 65 61 6b 3b 0a 20 20 7d 0a 20 20 72 65 74 75  reak;.  }.  retu
1120: 72 6e 20 30 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52  rn 0;.}../*.** R
1130: 65 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20  eturn a pointer 
1140: 74 6f 20 74 68 65 20 61 70 70 72 6f 70 72 69 61  to the appropria
1150: 74 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e  te hash function
1160: 20 67 69 76 65 6e 20 74 68 65 20 6b 65 79 20 63   given the key c
1170: 6c 61 73 73 2e 0a 2a 2a 0a 2a 2a 20 46 6f 72 20  lass..**.** For 
1180: 68 65 6c 70 20 69 6e 20 69 6e 74 65 72 70 72 65  help in interpre
1190: 74 65 64 20 74 68 65 20 6f 62 73 63 75 72 65 20  ted the obscure 
11a0: 43 20 63 6f 64 65 20 69 6e 20 74 68 65 20 66 75  C code in the fu
11b0: 6e 63 74 69 6f 6e 20 64 65 66 69 6e 69 74 69 6f  nction definitio
11c0: 6e 2c 0a 2a 2a 20 73 65 65 20 74 68 65 20 68 65  n,.** see the he
11d0: 61 64 65 72 20 63 6f 6d 6d 65 6e 74 20 6f 6e 20  ader comment on 
11e0: 74 68 65 20 70 72 65 76 69 6f 75 73 20 66 75 6e  the previous fun
11f0: 63 74 69 6f 6e 2e 0a 2a 2f 0a 73 74 61 74 69 63  ction..*/.static
1200: 20 69 6e 74 20 28 2a 63 6f 6d 70 61 72 65 46 75   int (*compareFu
1210: 6e 63 74 69 6f 6e 28 69 6e 74 20 6b 65 79 43 6c  nction(int keyCl
1220: 61 73 73 29 29 28 63 6f 6e 73 74 20 76 6f 69 64  ass))(const void
1230: 2a 2c 69 6e 74 2c 63 6f 6e 73 74 20 76 6f 69 64  *,int,const void
1240: 2a 2c 69 6e 74 29 7b 0a 20 20 73 77 69 74 63 68  *,int){.  switch
1250: 28 20 6b 65 79 43 6c 61 73 73 20 29 7b 0a 20 20  ( keyClass ){.  
1260: 20 20 63 61 73 65 20 53 51 4c 49 54 45 5f 48 41    case SQLITE_HA
1270: 53 48 5f 49 4e 54 3a 20 20 20 20 20 72 65 74 75  SH_INT:     retu
1280: 72 6e 20 26 69 6e 74 43 6f 6d 70 61 72 65 3b 0a  rn &intCompare;.
1290: 20 20 20 20 2f 2a 20 63 61 73 65 20 53 51 4c 49      /* case SQLI
12a0: 54 45 5f 48 41 53 48 5f 50 4f 49 4e 54 45 52 3a  TE_HASH_POINTER:
12b0: 20 72 65 74 75 72 6e 20 26 70 74 72 43 6f 6d 70   return &ptrComp
12c0: 61 72 65 3b 20 2f 2f 20 4e 4f 54 20 55 53 45 44  are; // NOT USED
12d0: 20 2a 2f 0a 20 20 20 20 63 61 73 65 20 53 51 4c   */.    case SQL
12e0: 49 54 45 5f 48 41 53 48 5f 53 54 52 49 4e 47 3a  ITE_HASH_STRING:
12f0: 20 20 72 65 74 75 72 6e 20 26 73 74 72 43 6f 6d    return &strCom
1300: 70 61 72 65 3b 0a 20 20 20 20 63 61 73 65 20 53  pare;.    case S
1310: 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e 41 52  QLITE_HASH_BINAR
1320: 59 3a 20 20 72 65 74 75 72 6e 20 26 62 69 6e 43  Y:  return &binC
1330: 6f 6d 70 61 72 65 3b 0a 20 20 20 20 64 65 66 61  ompare;.    defa
1340: 75 6c 74 3a 20 62 72 65 61 6b 3b 0a 20 20 7d 0a  ult: break;.  }.
1350: 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a 0a 0a    return 0;.}...
1360: 2f 2a 20 52 65 73 69 7a 65 20 74 68 65 20 68 61  /* Resize the ha
1370: 73 68 20 74 61 62 6c 65 20 73 6f 20 74 68 61 74  sh table so that
1380: 20 69 74 20 63 61 6e 74 61 69 6e 73 20 22 6e 65   it cantains "ne
1390: 77 5f 73 69 7a 65 22 20 62 75 63 6b 65 74 73 2e  w_size" buckets.
13a0: 0a 2a 2a 20 22 6e 65 77 5f 73 69 7a 65 22 20 6d  .** "new_size" m
13b0: 75 73 74 20 62 65 20 61 20 70 6f 77 65 72 20 6f  ust be a power o
13c0: 66 20 32 2e 20 20 54 68 65 20 68 61 73 68 20 74  f 2.  The hash t
13d0: 61 62 6c 65 20 6d 69 67 68 74 20 66 61 69 6c 20  able might fail 
13e0: 0a 2a 2a 20 74 6f 20 72 65 73 69 7a 65 20 69 66  .** to resize if
13f0: 20 73 71 6c 69 74 65 4d 61 6c 6c 6f 63 28 29 20   sqliteMalloc() 
1400: 66 61 69 6c 73 2e 0a 2a 2f 0a 73 74 61 74 69 63  fails..*/.static
1410: 20 76 6f 69 64 20 72 65 68 61 73 68 28 48 61 73   void rehash(Has
1420: 68 20 2a 70 48 2c 20 69 6e 74 20 6e 65 77 5f 73  h *pH, int new_s
1430: 69 7a 65 29 7b 0a 20 20 73 74 72 75 63 74 20 5f  ize){.  struct _
1440: 68 74 20 2a 6e 65 77 5f 68 74 3b 20 20 20 20 20  ht *new_ht;     
1450: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 6e 65         /* The ne
1460: 77 20 68 61 73 68 20 74 61 62 6c 65 20 2a 2f 0a  w hash table */.
1470: 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d    HashElem *elem
1480: 2c 20 2a 6e 65 78 74 5f 65 6c 65 6d 3b 20 20 20  , *next_elem;   
1490: 20 2f 2a 20 46 6f 72 20 6c 6f 6f 70 69 6e 67 20   /* For looping 
14a0: 6f 76 65 72 20 65 78 69 73 74 69 6e 67 20 65 6c  over existing el
14b0: 65 6d 65 6e 74 73 20 2a 2f 0a 20 20 48 61 73 68  ements */.  Hash
14c0: 45 6c 65 6d 20 2a 78 3b 20 20 20 20 20 20 20 20  Elem *x;        
14d0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 45 6c             /* El
14e0: 65 6d 65 6e 74 20 62 65 69 6e 67 20 63 6f 70 69  ement being copi
14f0: 65 64 20 74 6f 20 6e 65 77 20 68 61 73 68 20 74  ed to new hash t
1500: 61 62 6c 65 20 2a 2f 0a 20 20 69 6e 74 20 28 2a  able */.  int (*
1510: 78 48 61 73 68 29 28 63 6f 6e 73 74 20 76 6f 69  xHash)(const voi
1520: 64 2a 2c 69 6e 74 29 3b 20 2f 2a 20 54 68 65 20  d*,int); /* The 
1530: 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 2a 2f  hash function */
1540: 0a 0a 20 20 61 73 73 65 72 74 28 20 28 6e 65 77  ..  assert( (new
1550: 5f 73 69 7a 65 20 26 20 28 6e 65 77 5f 73 69 7a  _size & (new_siz
1560: 65 2d 31 29 29 3d 3d 30 20 29 3b 0a 20 20 6e 65  e-1))==0 );.  ne
1570: 77 5f 68 74 20 3d 20 28 73 74 72 75 63 74 20 5f  w_ht = (struct _
1580: 68 74 20 2a 29 73 71 6c 69 74 65 4d 61 6c 6c 6f  ht *)sqliteMallo
1590: 63 28 20 6e 65 77 5f 73 69 7a 65 2a 73 69 7a 65  c( new_size*size
15a0: 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29 20 29  of(struct _ht) )
15b0: 3b 0a 20 20 69 66 28 20 6e 65 77 5f 68 74 3d 3d  ;.  if( new_ht==
15c0: 30 20 29 20 72 65 74 75 72 6e 3b 0a 20 20 69 66  0 ) return;.  if
15d0: 28 20 70 48 2d 3e 68 74 20 29 20 73 71 6c 69 74  ( pH->ht ) sqlit
15e0: 65 46 72 65 65 28 70 48 2d 3e 68 74 29 3b 0a 20  eFree(pH->ht);. 
15f0: 20 70 48 2d 3e 68 74 20 3d 20 6e 65 77 5f 68 74   pH->ht = new_ht
1600: 3b 0a 20 20 70 48 2d 3e 68 74 73 69 7a 65 20 3d  ;.  pH->htsize =
1610: 20 6e 65 77 5f 73 69 7a 65 3b 0a 20 20 78 48 61   new_size;.  xHa
1620: 73 68 20 3d 20 68 61 73 68 46 75 6e 63 74 69 6f  sh = hashFunctio
1630: 6e 28 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b  n(pH->keyClass);
1640: 0a 20 20 66 6f 72 28 65 6c 65 6d 3d 70 48 2d 3e  .  for(elem=pH->
1650: 66 69 72 73 74 2c 20 70 48 2d 3e 66 69 72 73 74  first, pH->first
1660: 3d 30 3b 20 65 6c 65 6d 3b 20 65 6c 65 6d 20 3d  =0; elem; elem =
1670: 20 6e 65 78 74 5f 65 6c 65 6d 29 7b 0a 20 20 20   next_elem){.   
1680: 20 69 6e 74 20 68 20 3d 20 28 2a 78 48 61 73 68   int h = (*xHash
1690: 29 28 65 6c 65 6d 2d 3e 70 4b 65 79 2c 20 65 6c  )(elem->pKey, el
16a0: 65 6d 2d 3e 6e 4b 65 79 29 20 26 20 28 6e 65 77  em->nKey) & (new
16b0: 5f 73 69 7a 65 2d 31 29 3b 0a 20 20 20 20 6e 65  _size-1);.    ne
16c0: 78 74 5f 65 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e  xt_elem = elem->
16d0: 6e 65 78 74 3b 0a 20 20 20 20 78 20 3d 20 6e 65  next;.    x = ne
16e0: 77 5f 68 74 5b 68 5d 2e 63 68 61 69 6e 3b 0a 20  w_ht[h].chain;. 
16f0: 20 20 20 69 66 28 20 78 20 29 7b 0a 20 20 20 20     if( x ){.    
1700: 20 20 65 6c 65 6d 2d 3e 6e 65 78 74 20 3d 20 78    elem->next = x
1710: 3b 0a 20 20 20 20 20 20 65 6c 65 6d 2d 3e 70 72  ;.      elem->pr
1720: 65 76 20 3d 20 78 2d 3e 70 72 65 76 3b 0a 20 20  ev = x->prev;.  
1730: 20 20 20 20 69 66 28 20 78 2d 3e 70 72 65 76 20      if( x->prev 
1740: 29 20 78 2d 3e 70 72 65 76 2d 3e 6e 65 78 74 20  ) x->prev->next 
1750: 3d 20 65 6c 65 6d 3b 0a 20 20 20 20 20 20 65 6c  = elem;.      el
1760: 73 65 20 20 20 20 20 20 20 20 20 20 70 48 2d 3e  se          pH->
1770: 66 69 72 73 74 20 3d 20 65 6c 65 6d 3b 0a 20 20  first = elem;.  
1780: 20 20 20 20 78 2d 3e 70 72 65 76 20 3d 20 65 6c      x->prev = el
1790: 65 6d 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20  em;.    }else{. 
17a0: 20 20 20 20 20 65 6c 65 6d 2d 3e 6e 65 78 74 20       elem->next 
17b0: 3d 20 70 48 2d 3e 66 69 72 73 74 3b 0a 20 20 20  = pH->first;.   
17c0: 20 20 20 69 66 28 20 70 48 2d 3e 66 69 72 73 74     if( pH->first
17d0: 20 29 20 70 48 2d 3e 66 69 72 73 74 2d 3e 70 72   ) pH->first->pr
17e0: 65 76 20 3d 20 65 6c 65 6d 3b 0a 20 20 20 20 20  ev = elem;.     
17f0: 20 65 6c 65 6d 2d 3e 70 72 65 76 20 3d 20 30 3b   elem->prev = 0;
1800: 0a 20 20 20 20 20 20 70 48 2d 3e 66 69 72 73 74  .      pH->first
1810: 20 3d 20 65 6c 65 6d 3b 0a 20 20 20 20 7d 0a 20   = elem;.    }. 
1820: 20 20 20 6e 65 77 5f 68 74 5b 68 5d 2e 63 68 61     new_ht[h].cha
1830: 69 6e 20 3d 20 65 6c 65 6d 3b 0a 20 20 20 20 6e  in = elem;.    n
1840: 65 77 5f 68 74 5b 68 5d 2e 63 6f 75 6e 74 2b 2b  ew_ht[h].count++
1850: 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 20 54 68 69 73  ;.  }.}../* This
1860: 20 66 75 6e 63 74 69 6f 6e 20 28 66 6f 72 20 69   function (for i
1870: 6e 74 65 72 6e 61 6c 20 75 73 65 20 6f 6e 6c 79  nternal use only
1880: 29 20 6c 6f 63 61 74 65 73 20 61 6e 20 65 6c 65  ) locates an ele
1890: 6d 65 6e 74 20 69 6e 20 61 6e 0a 2a 2a 20 68 61  ment in an.** ha
18a0: 73 68 20 74 61 62 6c 65 20 74 68 61 74 20 6d 61  sh table that ma
18b0: 74 63 68 65 73 20 74 68 65 20 67 69 76 65 6e 20  tches the given 
18c0: 6b 65 79 2e 20 20 54 68 65 20 68 61 73 68 20 66  key.  The hash f
18d0: 6f 72 20 74 68 69 73 20 6b 65 79 20 68 61 73 0a  or this key has.
18e0: 2a 2a 20 61 6c 72 65 61 64 79 20 62 65 65 6e 20  ** already been 
18f0: 63 6f 6d 70 75 74 65 64 20 61 6e 64 20 69 73 20  computed and is 
1900: 70 61 73 73 65 64 20 61 73 20 74 68 65 20 34 74  passed as the 4t
1910: 68 20 70 61 72 61 6d 65 74 65 72 2e 0a 2a 2f 0a  h parameter..*/.
1920: 73 74 61 74 69 63 20 48 61 73 68 45 6c 65 6d 20  static HashElem 
1930: 2a 66 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65  *findElementGive
1940: 6e 48 61 73 68 28 0a 20 20 63 6f 6e 73 74 20 48  nHash(.  const H
1950: 61 73 68 20 2a 70 48 2c 20 20 20 20 20 2f 2a 20  ash *pH,     /* 
1960: 54 68 65 20 70 48 20 74 6f 20 62 65 20 73 65 61  The pH to be sea
1970: 72 63 68 65 64 20 2a 2f 0a 20 20 63 6f 6e 73 74  rched */.  const
1980: 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 20 20 2f   void *pKey,   /
1990: 2a 20 54 68 65 20 6b 65 79 20 77 65 20 61 72 65  * The key we are
19a0: 20 73 65 61 72 63 68 69 6e 67 20 66 6f 72 20 2a   searching for *
19b0: 2f 0a 20 20 69 6e 74 20 6e 4b 65 79 2c 0a 20 20  /.  int nKey,.  
19c0: 69 6e 74 20 68 20 20 20 20 20 20 20 20 20 20 20  int h           
19d0: 20 20 20 20 2f 2a 20 54 68 65 20 68 61 73 68 20      /* The hash 
19e0: 66 6f 72 20 74 68 69 73 20 6b 65 79 2e 20 2a 2f  for this key. */
19f0: 0a 29 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a  .){.  HashElem *
1a00: 65 6c 65 6d 3b 20 20 20 20 20 20 20 20 20 20 20  elem;           
1a10: 20 20 20 20 20 2f 2a 20 55 73 65 64 20 74 6f 20       /* Used to 
1a20: 6c 6f 6f 70 20 74 68 72 75 20 74 68 65 20 65 6c  loop thru the el
1a30: 65 6d 65 6e 74 20 6c 69 73 74 20 2a 2f 0a 20 20  ement list */.  
1a40: 69 6e 74 20 63 6f 75 6e 74 3b 20 20 20 20 20 20  int count;      
1a50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
1a60: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65 6c 65 6d  * Number of elem
1a70: 65 6e 74 73 20 6c 65 66 74 20 74 6f 20 74 65 73  ents left to tes
1a80: 74 20 2a 2f 0a 20 20 69 6e 74 20 28 2a 78 43 6f  t */.  int (*xCo
1a90: 6d 70 61 72 65 29 28 63 6f 6e 73 74 20 76 6f 69  mpare)(const voi
1aa0: 64 2a 2c 69 6e 74 2c 63 6f 6e 73 74 20 76 6f 69  d*,int,const voi
1ab0: 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a 20 63 6f 6d  d*,int);  /* com
1ac0: 70 61 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e  parison function
1ad0: 20 2a 2f 0a 0a 20 20 69 66 28 20 70 48 2d 3e 68   */..  if( pH->h
1ae0: 74 20 29 7b 0a 20 20 20 20 65 6c 65 6d 20 3d 20  t ){.    elem = 
1af0: 70 48 2d 3e 68 74 5b 68 5d 2e 63 68 61 69 6e 3b  pH->ht[h].chain;
1b00: 0a 20 20 20 20 63 6f 75 6e 74 20 3d 20 70 48 2d  .    count = pH-
1b10: 3e 68 74 5b 68 5d 2e 63 6f 75 6e 74 3b 0a 20 20  >ht[h].count;.  
1b20: 20 20 78 43 6f 6d 70 61 72 65 20 3d 20 63 6f 6d    xCompare = com
1b30: 70 61 72 65 46 75 6e 63 74 69 6f 6e 28 70 48 2d  pareFunction(pH-
1b40: 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20 20 20  >keyClass);.    
1b50: 77 68 69 6c 65 28 20 63 6f 75 6e 74 2d 2d 20 26  while( count-- &
1b60: 26 20 65 6c 65 6d 20 29 7b 0a 20 20 20 20 20 20  & elem ){.      
1b70: 69 66 28 20 28 2a 78 43 6f 6d 70 61 72 65 29 28  if( (*xCompare)(
1b80: 65 6c 65 6d 2d 3e 70 4b 65 79 2c 65 6c 65 6d 2d  elem->pKey,elem-
1b90: 3e 6e 4b 65 79 2c 70 4b 65 79 2c 6e 4b 65 79 29  >nKey,pKey,nKey)
1ba0: 3d 3d 30 20 29 7b 20 0a 20 20 20 20 20 20 20 20  ==0 ){ .        
1bb0: 72 65 74 75 72 6e 20 65 6c 65 6d 3b 0a 20 20 20  return elem;.   
1bc0: 20 20 20 7d 0a 20 20 20 20 20 20 65 6c 65 6d 20     }.      elem 
1bd0: 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20  = elem->next;.  
1be0: 20 20 7d 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e    }.  }.  return
1bf0: 20 30 3b 0a 7d 0a 0a 2f 2a 20 52 65 6d 6f 76 65   0;.}../* Remove
1c00: 20 61 20 73 69 6e 67 6c 65 20 65 6e 74 72 79 20   a single entry 
1c10: 66 72 6f 6d 20 74 68 65 20 68 61 73 68 20 74 61  from the hash ta
1c20: 62 6c 65 20 67 69 76 65 6e 20 61 20 70 6f 69 6e  ble given a poin
1c30: 74 65 72 20 74 6f 20 74 68 61 74 0a 2a 2a 20 65  ter to that.** e
1c40: 6c 65 6d 65 6e 74 20 61 6e 64 20 61 20 68 61 73  lement and a has
1c50: 68 20 6f 6e 20 74 68 65 20 65 6c 65 6d 65 6e 74  h on the element
1c60: 27 73 20 6b 65 79 2e 0a 2a 2f 0a 73 74 61 74 69  's key..*/.stati
1c70: 63 20 76 6f 69 64 20 72 65 6d 6f 76 65 45 6c 65  c void removeEle
1c80: 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28 0a 20  mentGivenHash(. 
1c90: 20 48 61 73 68 20 2a 70 48 2c 20 20 20 20 20 20   Hash *pH,      
1ca0: 20 20 20 2f 2a 20 54 68 65 20 70 48 20 63 6f 6e     /* The pH con
1cb0: 74 61 69 6e 69 6e 67 20 22 65 6c 65 6d 22 20 2a  taining "elem" *
1cc0: 2f 0a 20 20 48 61 73 68 45 6c 65 6d 2a 20 65 6c  /.  HashElem* el
1cd0: 65 6d 2c 20 20 20 2f 2a 20 54 68 65 20 65 6c 65  em,   /* The ele
1ce0: 6d 65 6e 74 20 74 6f 20 62 65 20 72 65 6d 6f 76  ment to be remov
1cf0: 65 64 20 66 72 6f 6d 20 74 68 65 20 70 48 20 2a  ed from the pH *
1d00: 2f 0a 20 20 69 6e 74 20 68 20 20 20 20 20 20 20  /.  int h       
1d10: 20 20 20 20 20 20 2f 2a 20 48 61 73 68 20 76 61        /* Hash va
1d20: 6c 75 65 20 66 6f 72 20 74 68 65 20 65 6c 65 6d  lue for the elem
1d30: 65 6e 74 20 2a 2f 0a 29 7b 0a 20 20 69 66 28 20  ent */.){.  if( 
1d40: 65 6c 65 6d 2d 3e 70 72 65 76 20 29 7b 0a 20 20  elem->prev ){.  
1d50: 20 20 65 6c 65 6d 2d 3e 70 72 65 76 2d 3e 6e 65    elem->prev->ne
1d60: 78 74 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b  xt = elem->next;
1d70: 20 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 70   .  }else{.    p
1d80: 48 2d 3e 66 69 72 73 74 20 3d 20 65 6c 65 6d 2d  H->first = elem-
1d90: 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20 20 69 66 28  >next;.  }.  if(
1da0: 20 65 6c 65 6d 2d 3e 6e 65 78 74 20 29 7b 0a 20   elem->next ){. 
1db0: 20 20 20 65 6c 65 6d 2d 3e 6e 65 78 74 2d 3e 70     elem->next->p
1dc0: 72 65 76 20 3d 20 65 6c 65 6d 2d 3e 70 72 65 76  rev = elem->prev
1dd0: 3b 0a 20 20 7d 0a 20 20 69 66 28 20 70 48 2d 3e  ;.  }.  if( pH->
1de0: 68 74 5b 68 5d 2e 63 68 61 69 6e 3d 3d 65 6c 65  ht[h].chain==ele
1df0: 6d 20 29 7b 0a 20 20 20 20 70 48 2d 3e 68 74 5b  m ){.    pH->ht[
1e00: 68 5d 2e 63 68 61 69 6e 20 3d 20 65 6c 65 6d 2d  h].chain = elem-
1e10: 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20 20 70 48 2d  >next;.  }.  pH-
1e20: 3e 68 74 5b 68 5d 2e 63 6f 75 6e 74 2d 2d 3b 0a  >ht[h].count--;.
1e30: 20 20 69 66 28 20 70 48 2d 3e 68 74 5b 68 5d 2e    if( pH->ht[h].
1e40: 63 6f 75 6e 74 3c 3d 30 20 29 7b 0a 20 20 20 20  count<=0 ){.    
1e50: 70 48 2d 3e 68 74 5b 68 5d 2e 63 68 61 69 6e 20  pH->ht[h].chain 
1e60: 3d 20 30 3b 0a 20 20 7d 0a 20 20 69 66 28 20 70  = 0;.  }.  if( p
1e70: 48 2d 3e 63 6f 70 79 4b 65 79 20 26 26 20 65 6c  H->copyKey && el
1e80: 65 6d 2d 3e 70 4b 65 79 20 29 7b 0a 20 20 20 20  em->pKey ){.    
1e90: 73 71 6c 69 74 65 46 72 65 65 28 65 6c 65 6d 2d  sqliteFree(elem-
1ea0: 3e 70 4b 65 79 29 3b 0a 20 20 7d 0a 20 20 73 71  >pKey);.  }.  sq
1eb0: 6c 69 74 65 46 72 65 65 28 20 65 6c 65 6d 20 29  liteFree( elem )
1ec0: 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 2d 2d 3b  ;.  pH->count--;
1ed0: 0a 7d 0a 0a 2f 2a 20 41 74 74 65 6d 70 74 20 74  .}../* Attempt t
1ee0: 6f 20 6c 6f 63 61 74 65 20 61 6e 20 65 6c 65 6d  o locate an elem
1ef0: 65 6e 74 20 6f 66 20 74 68 65 20 68 61 73 68 20  ent of the hash 
1f00: 74 61 62 6c 65 20 70 48 20 77 69 74 68 20 61 20  table pH with a 
1f10: 6b 65 79 0a 2a 2a 20 74 68 61 74 20 6d 61 74 63  key.** that matc
1f20: 68 65 73 20 70 4b 65 79 2c 6e 4b 65 79 2e 20 20  hes pKey,nKey.  
1f30: 52 65 74 75 72 6e 20 74 68 65 20 64 61 74 61 20  Return the data 
1f40: 66 6f 72 20 74 68 69 73 20 65 6c 65 6d 65 6e 74  for this element
1f50: 20 69 66 20 69 74 20 69 73 0a 2a 2a 20 66 6f 75   if it is.** fou
1f60: 6e 64 2c 20 6f 72 20 4e 55 4c 4c 20 69 66 20 74  nd, or NULL if t
1f70: 68 65 72 65 20 69 73 20 6e 6f 20 6d 61 74 63 68  here is no match
1f80: 2e 0a 2a 2f 0a 76 6f 69 64 20 2a 73 71 6c 69 74  ..*/.void *sqlit
1f90: 65 33 48 61 73 68 46 69 6e 64 28 63 6f 6e 73 74  e3HashFind(const
1fa0: 20 48 61 73 68 20 2a 70 48 2c 20 63 6f 6e 73 74   Hash *pH, const
1fb0: 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74   void *pKey, int
1fc0: 20 6e 4b 65 79 29 7b 0a 20 20 69 6e 74 20 68 3b   nKey){.  int h;
1fd0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
1fe0: 41 20 68 61 73 68 20 6f 6e 20 6b 65 79 20 2a 2f  A hash on key */
1ff0: 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65  .  HashElem *ele
2000: 6d 3b 20 20 20 20 2f 2a 20 54 68 65 20 65 6c 65  m;    /* The ele
2010: 6d 65 6e 74 20 74 68 61 74 20 6d 61 74 63 68 65  ment that matche
2020: 73 20 6b 65 79 20 2a 2f 0a 20 20 69 6e 74 20 28  s key */.  int (
2030: 2a 78 48 61 73 68 29 28 63 6f 6e 73 74 20 76 6f  *xHash)(const vo
2040: 69 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a 20 54 68  id*,int);  /* Th
2050: 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 20  e hash function 
2060: 2a 2f 0a 0a 20 20 69 66 28 20 70 48 3d 3d 30 20  */..  if( pH==0 
2070: 7c 7c 20 70 48 2d 3e 68 74 3d 3d 30 20 29 20 72  || pH->ht==0 ) r
2080: 65 74 75 72 6e 20 30 3b 0a 20 20 78 48 61 73 68  eturn 0;.  xHash
2090: 20 3d 20 68 61 73 68 46 75 6e 63 74 69 6f 6e 28   = hashFunction(
20a0: 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20  pH->keyClass);. 
20b0: 20 61 73 73 65 72 74 28 20 78 48 61 73 68 21 3d   assert( xHash!=
20c0: 30 20 29 3b 0a 20 20 68 20 3d 20 28 2a 78 48 61  0 );.  h = (*xHa
20d0: 73 68 29 28 70 4b 65 79 2c 6e 4b 65 79 29 3b 0a  sh)(pKey,nKey);.
20e0: 20 20 61 73 73 65 72 74 28 20 28 70 48 2d 3e 68    assert( (pH->h
20f0: 74 73 69 7a 65 20 26 20 28 70 48 2d 3e 68 74 73  tsize & (pH->hts
2100: 69 7a 65 2d 31 29 29 3d 3d 30 20 29 3b 0a 20 20  ize-1))==0 );.  
2110: 65 6c 65 6d 20 3d 20 66 69 6e 64 45 6c 65 6d 65  elem = findEleme
2120: 6e 74 47 69 76 65 6e 48 61 73 68 28 70 48 2c 70  ntGivenHash(pH,p
2130: 4b 65 79 2c 6e 4b 65 79 2c 20 68 20 26 20 28 70  Key,nKey, h & (p
2140: 48 2d 3e 68 74 73 69 7a 65 2d 31 29 29 3b 0a 20  H->htsize-1));. 
2150: 20 72 65 74 75 72 6e 20 65 6c 65 6d 20 3f 20 65   return elem ? e
2160: 6c 65 6d 2d 3e 64 61 74 61 20 3a 20 30 3b 0a 7d  lem->data : 0;.}
2170: 0a 0a 2f 2a 20 49 6e 73 65 72 74 20 61 6e 20 65  ../* Insert an e
2180: 6c 65 6d 65 6e 74 20 69 6e 74 6f 20 74 68 65 20  lement into the 
2190: 68 61 73 68 20 74 61 62 6c 65 20 70 48 2e 20 20  hash table pH.  
21a0: 54 68 65 20 6b 65 79 20 69 73 20 70 4b 65 79 2c  The key is pKey,
21b0: 6e 4b 65 79 0a 2a 2a 20 61 6e 64 20 74 68 65 20  nKey.** and the 
21c0: 64 61 74 61 20 69 73 20 22 64 61 74 61 22 2e 0a  data is "data"..
21d0: 2a 2a 0a 2a 2a 20 49 66 20 6e 6f 20 65 6c 65 6d  **.** If no elem
21e0: 65 6e 74 20 65 78 69 73 74 73 20 77 69 74 68 20  ent exists with 
21f0: 61 20 6d 61 74 63 68 69 6e 67 20 6b 65 79 2c 20  a matching key, 
2200: 74 68 65 6e 20 61 20 6e 65 77 0a 2a 2a 20 65 6c  then a new.** el
2210: 65 6d 65 6e 74 20 69 73 20 63 72 65 61 74 65 64  ement is created
2220: 2e 20 20 41 20 63 6f 70 79 20 6f 66 20 74 68 65  .  A copy of the
2230: 20 6b 65 79 20 69 73 20 6d 61 64 65 20 69 66 20   key is made if 
2240: 74 68 65 20 63 6f 70 79 4b 65 79 0a 2a 2a 20 66  the copyKey.** f
2250: 6c 61 67 20 69 73 20 73 65 74 2e 20 20 4e 55 4c  lag is set.  NUL
2260: 4c 20 69 73 20 72 65 74 75 72 6e 65 64 2e 0a 2a  L is returned..*
2270: 2a 0a 2a 2a 20 49 66 20 61 6e 6f 74 68 65 72 20  *.** If another 
2280: 65 6c 65 6d 65 6e 74 20 61 6c 72 65 61 64 79 20  element already 
2290: 65 78 69 73 74 73 20 77 69 74 68 20 74 68 65 20  exists with the 
22a0: 73 61 6d 65 20 6b 65 79 2c 20 74 68 65 6e 20 74  same key, then t
22b0: 68 65 0a 2a 2a 20 6e 65 77 20 64 61 74 61 20 72  he.** new data r
22c0: 65 70 6c 61 63 65 73 20 74 68 65 20 6f 6c 64 20  eplaces the old 
22d0: 64 61 74 61 20 61 6e 64 20 74 68 65 20 6f 6c 64  data and the old
22e0: 20 64 61 74 61 20 69 73 20 72 65 74 75 72 6e 65   data is returne
22f0: 64 2e 0a 2a 2a 20 54 68 65 20 6b 65 79 20 69 73  d..** The key is
2300: 20 6e 6f 74 20 63 6f 70 69 65 64 20 69 6e 20 74   not copied in t
2310: 68 69 73 20 69 6e 73 74 61 6e 63 65 2e 20 20 49  his instance.  I
2320: 66 20 61 20 6d 61 6c 6c 6f 63 20 66 61 69 6c 73  f a malloc fails
2330: 2c 20 74 68 65 6e 0a 2a 2a 20 74 68 65 20 6e 65  , then.** the ne
2340: 77 20 64 61 74 61 20 69 73 20 72 65 74 75 72 6e  w data is return
2350: 65 64 20 61 6e 64 20 74 68 65 20 68 61 73 68 20  ed and the hash 
2360: 74 61 62 6c 65 20 69 73 20 75 6e 63 68 61 6e 67  table is unchang
2370: 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 65  ed..**.** If the
2380: 20 22 64 61 74 61 22 20 70 61 72 61 6d 65 74 65   "data" paramete
2390: 72 20 74 6f 20 74 68 69 73 20 66 75 6e 63 74 69  r to this functi
23a0: 6f 6e 20 69 73 20 4e 55 4c 4c 2c 20 74 68 65 6e  on is NULL, then
23b0: 20 74 68 65 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20   the.** element 
23c0: 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 74 6f  corresponding to
23d0: 20 22 6b 65 79 22 20 69 73 20 72 65 6d 6f 76 65   "key" is remove
23e0: 64 20 66 72 6f 6d 20 74 68 65 20 68 61 73 68 20  d from the hash 
23f0: 74 61 62 6c 65 2e 0a 2a 2f 0a 76 6f 69 64 20 2a  table..*/.void *
2400: 73 71 6c 69 74 65 33 48 61 73 68 49 6e 73 65 72  sqlite3HashInser
2410: 74 28 48 61 73 68 20 2a 70 48 2c 20 63 6f 6e 73  t(Hash *pH, cons
2420: 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e  t void *pKey, in
2430: 74 20 6e 4b 65 79 2c 20 76 6f 69 64 20 2a 64 61  t nKey, void *da
2440: 74 61 29 7b 0a 20 20 69 6e 74 20 68 72 61 77 3b  ta){.  int hraw;
2450: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
2460: 52 61 77 20 68 61 73 68 20 76 61 6c 75 65 20 6f  Raw hash value o
2470: 66 20 74 68 65 20 6b 65 79 20 2a 2f 0a 20 20 69  f the key */.  i
2480: 6e 74 20 68 3b 20 20 20 20 20 20 20 20 20 20 20  nt h;           
2490: 20 20 20 20 20 2f 2a 20 74 68 65 20 68 61 73 68       /* the hash
24a0: 20 6f 66 20 74 68 65 20 6b 65 79 20 6d 6f 64 75   of the key modu
24b0: 6c 6f 20 68 61 73 68 20 74 61 62 6c 65 20 73 69  lo hash table si
24c0: 7a 65 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d  ze */.  HashElem
24d0: 20 2a 65 6c 65 6d 3b 20 20 20 20 20 20 20 2f 2a   *elem;       /*
24e0: 20 55 73 65 64 20 74 6f 20 6c 6f 6f 70 20 74 68   Used to loop th
24f0: 72 75 20 74 68 65 20 65 6c 65 6d 65 6e 74 20 6c  ru the element l
2500: 69 73 74 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65  ist */.  HashEle
2510: 6d 20 2a 6e 65 77 5f 65 6c 65 6d 3b 20 20 20 2f  m *new_elem;   /
2520: 2a 20 4e 65 77 20 65 6c 65 6d 65 6e 74 20 61 64  * New element ad
2530: 64 65 64 20 74 6f 20 74 68 65 20 70 48 20 2a 2f  ded to the pH */
2540: 0a 20 20 69 6e 74 20 28 2a 78 48 61 73 68 29 28  .  int (*xHash)(
2550: 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29  const void*,int)
2560: 3b 20 20 2f 2a 20 54 68 65 20 68 61 73 68 20 66  ;  /* The hash f
2570: 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20 61 73  unction */..  as
2580: 73 65 72 74 28 20 70 48 21 3d 30 20 29 3b 0a 20  sert( pH!=0 );. 
2590: 20 78 48 61 73 68 20 3d 20 68 61 73 68 46 75 6e   xHash = hashFun
25a0: 63 74 69 6f 6e 28 70 48 2d 3e 6b 65 79 43 6c 61  ction(pH->keyCla
25b0: 73 73 29 3b 0a 20 20 61 73 73 65 72 74 28 20 78  ss);.  assert( x
25c0: 48 61 73 68 21 3d 30 20 29 3b 0a 20 20 68 72 61  Hash!=0 );.  hra
25d0: 77 20 3d 20 28 2a 78 48 61 73 68 29 28 70 4b 65  w = (*xHash)(pKe
25e0: 79 2c 20 6e 4b 65 79 29 3b 0a 20 20 61 73 73 65  y, nKey);.  asse
25f0: 72 74 28 20 28 70 48 2d 3e 68 74 73 69 7a 65 20  rt( (pH->htsize 
2600: 26 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29  & (pH->htsize-1)
2610: 29 3d 3d 30 20 29 3b 0a 20 20 68 20 3d 20 68 72  )==0 );.  h = hr
2620: 61 77 20 26 20 28 70 48 2d 3e 68 74 73 69 7a 65  aw & (pH->htsize
2630: 2d 31 29 3b 0a 20 20 65 6c 65 6d 20 3d 20 66 69  -1);.  elem = fi
2640: 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61  ndElementGivenHa
2650: 73 68 28 70 48 2c 70 4b 65 79 2c 6e 4b 65 79 2c  sh(pH,pKey,nKey,
2660: 68 29 3b 0a 20 20 69 66 28 20 65 6c 65 6d 20 29  h);.  if( elem )
2670: 7b 0a 20 20 20 20 76 6f 69 64 20 2a 6f 6c 64 5f  {.    void *old_
2680: 64 61 74 61 20 3d 20 65 6c 65 6d 2d 3e 64 61 74  data = elem->dat
2690: 61 3b 0a 20 20 20 20 69 66 28 20 64 61 74 61 3d  a;.    if( data=
26a0: 3d 30 20 29 7b 0a 20 20 20 20 20 20 72 65 6d 6f  =0 ){.      remo
26b0: 76 65 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61  veElementGivenHa
26c0: 73 68 28 70 48 2c 65 6c 65 6d 2c 68 29 3b 0a 20  sh(pH,elem,h);. 
26d0: 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20     }else{.      
26e0: 65 6c 65 6d 2d 3e 64 61 74 61 20 3d 20 64 61 74  elem->data = dat
26f0: 61 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72 65 74  a;.    }.    ret
2700: 75 72 6e 20 6f 6c 64 5f 64 61 74 61 3b 0a 20 20  urn old_data;.  
2710: 7d 0a 20 20 69 66 28 20 64 61 74 61 3d 3d 30 20  }.  if( data==0 
2720: 29 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 6e 65  ) return 0;.  ne
2730: 77 5f 65 6c 65 6d 20 3d 20 28 48 61 73 68 45 6c  w_elem = (HashEl
2740: 65 6d 2a 29 73 71 6c 69 74 65 4d 61 6c 6c 6f 63  em*)sqliteMalloc
2750: 28 20 73 69 7a 65 6f 66 28 48 61 73 68 45 6c 65  ( sizeof(HashEle
2760: 6d 29 20 29 3b 0a 20 20 69 66 28 20 6e 65 77 5f  m) );.  if( new_
2770: 65 6c 65 6d 3d 3d 30 20 29 20 72 65 74 75 72 6e  elem==0 ) return
2780: 20 64 61 74 61 3b 0a 20 20 69 66 28 20 70 48 2d   data;.  if( pH-
2790: 3e 63 6f 70 79 4b 65 79 20 26 26 20 70 4b 65 79  >copyKey && pKey
27a0: 21 3d 30 20 29 7b 0a 20 20 20 20 6e 65 77 5f 65  !=0 ){.    new_e
27b0: 6c 65 6d 2d 3e 70 4b 65 79 20 3d 20 73 71 6c 69  lem->pKey = sqli
27c0: 74 65 4d 61 6c 6c 6f 63 52 61 77 28 20 6e 4b 65  teMallocRaw( nKe
27d0: 79 20 29 3b 0a 20 20 20 20 69 66 28 20 6e 65 77  y );.    if( new
27e0: 5f 65 6c 65 6d 2d 3e 70 4b 65 79 3d 3d 30 20 29  _elem->pKey==0 )
27f0: 7b 0a 20 20 20 20 20 20 73 71 6c 69 74 65 46 72  {.      sqliteFr
2800: 65 65 28 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20 20  ee(new_elem);.  
2810: 20 20 20 20 72 65 74 75 72 6e 20 64 61 74 61 3b      return data;
2820: 0a 20 20 20 20 7d 0a 20 20 20 20 6d 65 6d 63 70  .    }.    memcp
2830: 79 28 28 76 6f 69 64 2a 29 6e 65 77 5f 65 6c 65  y((void*)new_ele
2840: 6d 2d 3e 70 4b 65 79 2c 20 70 4b 65 79 2c 20 6e  m->pKey, pKey, n
2850: 4b 65 79 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20  Key);.  }else{. 
2860: 20 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65     new_elem->pKe
2870: 79 20 3d 20 28 76 6f 69 64 2a 29 70 4b 65 79 3b  y = (void*)pKey;
2880: 0a 20 20 7d 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d  .  }.  new_elem-
2890: 3e 6e 4b 65 79 20 3d 20 6e 4b 65 79 3b 0a 20 20  >nKey = nKey;.  
28a0: 70 48 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20 20 69  pH->count++;.  i
28b0: 66 28 20 70 48 2d 3e 68 74 73 69 7a 65 3d 3d 30  f( pH->htsize==0
28c0: 20 29 20 72 65 68 61 73 68 28 70 48 2c 38 29 3b   ) rehash(pH,8);
28d0: 0a 20 20 69 66 28 20 70 48 2d 3e 68 74 73 69 7a  .  if( pH->htsiz
28e0: 65 3d 3d 30 20 29 7b 0a 20 20 20 20 70 48 2d 3e  e==0 ){.    pH->
28f0: 63 6f 75 6e 74 20 3d 20 30 3b 0a 20 20 20 20 73  count = 0;.    s
2900: 71 6c 69 74 65 46 72 65 65 28 6e 65 77 5f 65 6c  qliteFree(new_el
2910: 65 6d 29 3b 0a 20 20 20 20 72 65 74 75 72 6e 20  em);.    return 
2920: 64 61 74 61 3b 0a 20 20 7d 0a 20 20 69 66 28 20  data;.  }.  if( 
2930: 70 48 2d 3e 63 6f 75 6e 74 20 3e 20 70 48 2d 3e  pH->count > pH->
2940: 68 74 73 69 7a 65 20 29 7b 0a 20 20 20 20 72 65  htsize ){.    re
2950: 68 61 73 68 28 70 48 2c 70 48 2d 3e 68 74 73 69  hash(pH,pH->htsi
2960: 7a 65 2a 32 29 3b 0a 20 20 7d 0a 20 20 61 73 73  ze*2);.  }.  ass
2970: 65 72 74 28 20 28 70 48 2d 3e 68 74 73 69 7a 65  ert( (pH->htsize
2980: 20 26 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31   & (pH->htsize-1
2990: 29 29 3d 3d 30 20 29 3b 0a 20 20 68 20 3d 20 68  ))==0 );.  h = h
29a0: 72 61 77 20 26 20 28 70 48 2d 3e 68 74 73 69 7a  raw & (pH->htsiz
29b0: 65 2d 31 29 3b 0a 20 20 65 6c 65 6d 20 3d 20 70  e-1);.  elem = p
29c0: 48 2d 3e 68 74 5b 68 5d 2e 63 68 61 69 6e 3b 0a  H->ht[h].chain;.
29d0: 20 20 69 66 28 20 65 6c 65 6d 20 29 7b 0a 20 20    if( elem ){.  
29e0: 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 6e 65 78 74    new_elem->next
29f0: 20 3d 20 65 6c 65 6d 3b 0a 20 20 20 20 6e 65 77   = elem;.    new
2a00: 5f 65 6c 65 6d 2d 3e 70 72 65 76 20 3d 20 65 6c  _elem->prev = el
2a10: 65 6d 2d 3e 70 72 65 76 3b 0a 20 20 20 20 69 66  em->prev;.    if
2a20: 28 20 65 6c 65 6d 2d 3e 70 72 65 76 20 29 7b 20  ( elem->prev ){ 
2a30: 65 6c 65 6d 2d 3e 70 72 65 76 2d 3e 6e 65 78 74  elem->prev->next
2a40: 20 3d 20 6e 65 77 5f 65 6c 65 6d 3b 20 7d 0a 20   = new_elem; }. 
2a50: 20 20 20 65 6c 73 65 20 20 20 20 20 20 20 20 20     else         
2a60: 20 20 20 7b 20 70 48 2d 3e 66 69 72 73 74 20 3d     { pH->first =
2a70: 20 6e 65 77 5f 65 6c 65 6d 3b 20 7d 0a 20 20 20   new_elem; }.   
2a80: 20 65 6c 65 6d 2d 3e 70 72 65 76 20 3d 20 6e 65   elem->prev = ne
2a90: 77 5f 65 6c 65 6d 3b 0a 20 20 7d 65 6c 73 65 7b  w_elem;.  }else{
2aa0: 0a 20 20 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 6e  .    new_elem->n
2ab0: 65 78 74 20 3d 20 70 48 2d 3e 66 69 72 73 74 3b  ext = pH->first;
2ac0: 0a 20 20 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70  .    new_elem->p
2ad0: 72 65 76 20 3d 20 30 3b 0a 20 20 20 20 69 66 28  rev = 0;.    if(
2ae0: 20 70 48 2d 3e 66 69 72 73 74 20 29 7b 20 70 48   pH->first ){ pH
2af0: 2d 3e 66 69 72 73 74 2d 3e 70 72 65 76 20 3d 20  ->first->prev = 
2b00: 6e 65 77 5f 65 6c 65 6d 3b 20 7d 0a 20 20 20 20  new_elem; }.    
2b10: 70 48 2d 3e 66 69 72 73 74 20 3d 20 6e 65 77 5f  pH->first = new_
2b20: 65 6c 65 6d 3b 0a 20 20 7d 0a 20 20 70 48 2d 3e  elem;.  }.  pH->
2b30: 68 74 5b 68 5d 2e 63 6f 75 6e 74 2b 2b 3b 0a 20  ht[h].count++;. 
2b40: 20 70 48 2d 3e 68 74 5b 68 5d 2e 63 68 61 69 6e   pH->ht[h].chain
2b50: 20 3d 20 6e 65 77 5f 65 6c 65 6d 3b 0a 20 20 6e   = new_elem;.  n
2b60: 65 77 5f 65 6c 65 6d 2d 3e 64 61 74 61 20 3d 20  ew_elem->data = 
2b70: 64 61 74 61 3b 0a 20 20 72 65 74 75 72 6e 20 30  data;.  return 0
2b80: 3b 0a 7d 0a 0a 0a 0a                             ;.}....