/ Hex Artifact Content
Login

Artifact 8fe2fa52bd17869c87748e42cff5b1e7fbf90822:


0000: 2f 2a 0a 2a 2a 20 32 30 30 31 20 53 65 70 74 65  /*.** 2001 Septe
0010: 6d 62 65 72 20 32 32 0a 2a 2a 0a 2a 2a 20 54 68  mber 22.**.** Th
0020: 65 20 61 75 74 68 6f 72 20 64 69 73 63 6c 61 69  e author disclai
0030: 6d 73 20 63 6f 70 79 72 69 67 68 74 20 74 6f 20  ms copyright to 
0040: 74 68 69 73 20 73 6f 75 72 63 65 20 63 6f 64 65  this source code
0050: 2e 20 20 49 6e 20 70 6c 61 63 65 20 6f 66 0a 2a  .  In place of.*
0060: 2a 20 61 20 6c 65 67 61 6c 20 6e 6f 74 69 63 65  * a legal notice
0070: 2c 20 68 65 72 65 20 69 73 20 61 20 62 6c 65 73  , here is a bles
0080: 73 69 6e 67 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 4d  sing:.**.**    M
0090: 61 79 20 79 6f 75 20 64 6f 20 67 6f 6f 64 20 61  ay you do good a
00a0: 6e 64 20 6e 6f 74 20 65 76 69 6c 2e 0a 2a 2a 20  nd not evil..** 
00b0: 20 20 20 4d 61 79 20 79 6f 75 20 66 69 6e 64 20     May you find 
00c0: 66 6f 72 67 69 76 65 6e 65 73 73 20 66 6f 72 20  forgiveness for 
00d0: 79 6f 75 72 73 65 6c 66 20 61 6e 64 20 66 6f 72  yourself and for
00e0: 67 69 76 65 20 6f 74 68 65 72 73 2e 0a 2a 2a 20  give others..** 
00f0: 20 20 20 4d 61 79 20 79 6f 75 20 73 68 61 72 65     May you share
0100: 20 66 72 65 65 6c 79 2c 20 6e 65 76 65 72 20 74   freely, never t
0110: 61 6b 69 6e 67 20 6d 6f 72 65 20 74 68 61 6e 20  aking more than 
0120: 79 6f 75 20 67 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a  you give..**.***
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0170: 2a 2a 2a 2a 2a 2a 0a 2a 2a 20 54 68 69 73 20 69  ******.** This i
0180: 73 20 74 68 65 20 69 6d 70 6c 65 6d 65 6e 74 61  s the implementa
0190: 74 69 6f 6e 20 6f 66 20 67 65 6e 65 72 69 63 20  tion of generic 
01a0: 68 61 73 68 2d 74 61 62 6c 65 73 0a 2a 2a 20 75  hash-tables.** u
01b0: 73 65 64 20 69 6e 20 53 51 4c 69 74 65 2e 0a 2a  sed in SQLite..*
01c0: 2a 0a 2a 2a 20 24 49 64 3a 20 68 61 73 68 2e 63  *.** $Id: hash.c
01d0: 2c 76 20 31 2e 32 32 20 32 30 30 37 2f 30 38 2f  ,v 1.22 2007/08/
01e0: 32 39 20 31 32 3a 33 31 3a 32 36 20 64 61 6e 69  29 12:31:26 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 70 4e 65 77 22 20 69 73 20 61  *.** "pNew" is a
02a0: 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 20   pointer to the 
02b0: 68 61 73 68 20 74 61 62 6c 65 20 74 68 61 74 20  hash table that 
02c0: 69 73 20 74 6f 20 62 65 20 69 6e 69 74 69 61 6c  is to be initial
02d0: 69 7a 65 64 2e 0a 2a 2a 20 6b 65 79 43 6c 61 73  ized..** keyClas
02e0: 73 20 69 73 20 6f 6e 65 20 6f 66 20 74 68 65 20  s is one of the 
02f0: 63 6f 6e 73 74 61 6e 74 73 20 53 51 4c 49 54 45  constants SQLITE
0300: 5f 48 41 53 48 5f 49 4e 54 2c 20 53 51 4c 49 54  _HASH_INT, SQLIT
0310: 45 5f 48 41 53 48 5f 50 4f 49 4e 54 45 52 2c 0a  E_HASH_POINTER,.
0320: 2a 2a 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 42  ** SQLITE_HASH_B
0330: 49 4e 41 52 59 2c 20 6f 72 20 53 51 4c 49 54 45  INARY, or SQLITE
0340: 5f 48 41 53 48 5f 53 54 52 49 4e 47 2e 20 20 54  _HASH_STRING.  T
0350: 68 65 20 76 61 6c 75 65 20 6f 66 20 6b 65 79 43  he value of keyC
0360: 6c 61 73 73 20 0a 2a 2a 20 64 65 74 65 72 6d 69  lass .** determi
0370: 6e 65 73 20 77 68 61 74 20 6b 69 6e 64 20 6f 66  nes what kind of
0380: 20 6b 65 79 20 74 68 65 20 68 61 73 68 20 74 61   key the hash ta
0390: 62 6c 65 20 77 69 6c 6c 20 75 73 65 2e 20 20 22  ble will use.  "
03a0: 63 6f 70 79 4b 65 79 22 20 69 73 0a 2a 2a 20 74  copyKey" is.** t
03b0: 72 75 65 20 69 66 20 74 68 65 20 68 61 73 68 20  rue if the hash 
03c0: 74 61 62 6c 65 20 73 68 6f 75 6c 64 20 6d 61 6b  table should mak
03d0: 65 20 69 74 73 20 6f 77 6e 20 70 72 69 76 61 74  e its own privat
03e0: 65 20 63 6f 70 79 20 6f 66 20 6b 65 79 73 20 61  e copy of keys a
03f0: 6e 64 0a 2a 2a 20 66 61 6c 73 65 20 69 66 20 69  nd.** false if i
0400: 74 20 73 68 6f 75 6c 64 20 6a 75 73 74 20 75 73  t should just us
0410: 65 20 74 68 65 20 73 75 70 70 6c 69 65 64 20 70  e the supplied p
0420: 6f 69 6e 74 65 72 2e 20 20 43 6f 70 79 4b 65 79  ointer.  CopyKey
0430: 20 6f 6e 6c 79 20 6d 61 6b 65 73 0a 2a 2a 20 73   only makes.** s
0440: 65 6e 73 65 20 66 6f 72 20 53 51 4c 49 54 45 5f  ense for SQLITE_
0450: 48 41 53 48 5f 53 54 52 49 4e 47 20 61 6e 64 20  HASH_STRING and 
0460: 53 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e 41  SQLITE_HASH_BINA
0470: 52 59 20 61 6e 64 20 69 73 20 69 67 6e 6f 72 65  RY and is ignore
0480: 64 0a 2a 2a 20 66 6f 72 20 6f 74 68 65 72 20 6b  d.** for other k
0490: 65 79 20 63 6c 61 73 73 65 73 2e 0a 2a 2f 0a 76  ey classes..*/.v
04a0: 6f 69 64 20 73 71 6c 69 74 65 33 48 61 73 68 49  oid sqlite3HashI
04b0: 6e 69 74 28 48 61 73 68 20 2a 70 4e 65 77 2c 20  nit(Hash *pNew, 
04c0: 69 6e 74 20 6b 65 79 43 6c 61 73 73 2c 20 69 6e  int keyClass, in
04d0: 74 20 63 6f 70 79 4b 65 79 29 7b 0a 20 20 61 73  t copyKey){.  as
04e0: 73 65 72 74 28 20 70 4e 65 77 21 3d 30 20 29 3b  sert( pNew!=0 );
04f0: 0a 20 20 61 73 73 65 72 74 28 20 6b 65 79 43 6c  .  assert( keyCl
0500: 61 73 73 3e 3d 53 51 4c 49 54 45 5f 48 41 53 48  ass>=SQLITE_HASH
0510: 5f 53 54 52 49 4e 47 20 26 26 20 6b 65 79 43 6c  _STRING && keyCl
0520: 61 73 73 3c 3d 53 51 4c 49 54 45 5f 48 41 53 48  ass<=SQLITE_HASH
0530: 5f 42 49 4e 41 52 59 20 29 3b 0a 20 20 70 4e 65  _BINARY );.  pNe
0540: 77 2d 3e 6b 65 79 43 6c 61 73 73 20 3d 20 6b 65  w->keyClass = ke
0550: 79 43 6c 61 73 73 3b 0a 23 69 66 20 30 0a 20 20  yClass;.#if 0.  
0560: 69 66 28 20 6b 65 79 43 6c 61 73 73 3d 3d 53 51  if( keyClass==SQ
0570: 4c 49 54 45 5f 48 41 53 48 5f 50 4f 49 4e 54 45  LITE_HASH_POINTE
0580: 52 20 7c 7c 20 6b 65 79 43 6c 61 73 73 3d 3d 53  R || keyClass==S
0590: 51 4c 49 54 45 5f 48 41 53 48 5f 49 4e 54 20 29  QLITE_HASH_INT )
05a0: 20 63 6f 70 79 4b 65 79 20 3d 20 30 3b 0a 23 65   copyKey = 0;.#e
05b0: 6e 64 69 66 0a 20 20 70 4e 65 77 2d 3e 63 6f 70  ndif.  pNew->cop
05c0: 79 4b 65 79 20 3d 20 63 6f 70 79 4b 65 79 3b 0a  yKey = copyKey;.
05d0: 20 20 70 4e 65 77 2d 3e 66 69 72 73 74 20 3d 20    pNew->first = 
05e0: 30 3b 0a 20 20 70 4e 65 77 2d 3e 63 6f 75 6e 74  0;.  pNew->count
05f0: 20 3d 20 30 3b 0a 20 20 70 4e 65 77 2d 3e 68 74   = 0;.  pNew->ht
0600: 73 69 7a 65 20 3d 20 30 3b 0a 20 20 70 4e 65 77  size = 0;.  pNew
0610: 2d 3e 68 74 20 3d 20 30 3b 0a 7d 0a 0a 2f 2a 20  ->ht = 0;.}../* 
0620: 52 65 6d 6f 76 65 20 61 6c 6c 20 65 6e 74 72 69  Remove all entri
0630: 65 73 20 66 72 6f 6d 20 61 20 68 61 73 68 20 74  es from a hash t
0640: 61 62 6c 65 2e 20 20 52 65 63 6c 61 69 6d 20 61  able.  Reclaim a
0650: 6c 6c 20 6d 65 6d 6f 72 79 2e 0a 2a 2a 20 43 61  ll memory..** Ca
0660: 6c 6c 20 74 68 69 73 20 72 6f 75 74 69 6e 65 20  ll this routine 
0670: 74 6f 20 64 65 6c 65 74 65 20 61 20 68 61 73 68  to delete a hash
0680: 20 74 61 62 6c 65 20 6f 72 20 74 6f 20 72 65 73   table or to res
0690: 65 74 20 61 20 68 61 73 68 20 74 61 62 6c 65 0a  et a hash table.
06a0: 2a 2a 20 74 6f 20 74 68 65 20 65 6d 70 74 79 20  ** to the empty 
06b0: 73 74 61 74 65 2e 0a 2a 2f 0a 76 6f 69 64 20 73  state..*/.void s
06c0: 71 6c 69 74 65 33 48 61 73 68 43 6c 65 61 72 28  qlite3HashClear(
06d0: 48 61 73 68 20 2a 70 48 29 7b 0a 20 20 48 61 73  Hash *pH){.  Has
06e0: 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20  hElem *elem;    
06f0: 20 20 20 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f 70       /* For loop
0700: 69 6e 67 20 6f 76 65 72 20 61 6c 6c 20 65 6c 65  ing over all ele
0710: 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 74 61 62  ments of the tab
0720: 6c 65 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28  le */..  assert(
0730: 20 70 48 21 3d 30 20 29 3b 0a 20 20 65 6c 65 6d   pH!=0 );.  elem
0740: 20 3d 20 70 48 2d 3e 66 69 72 73 74 3b 0a 20 20   = pH->first;.  
0750: 70 48 2d 3e 66 69 72 73 74 20 3d 20 30 3b 0a 20  pH->first = 0;. 
0760: 20 69 66 28 20 70 48 2d 3e 68 74 20 29 20 73 71   if( pH->ht ) sq
0770: 6c 69 74 65 33 5f 66 72 65 65 28 70 48 2d 3e 68  lite3_free(pH->h
0780: 74 29 3b 0a 20 20 70 48 2d 3e 68 74 20 3d 20 30  t);.  pH->ht = 0
0790: 3b 0a 20 20 70 48 2d 3e 68 74 73 69 7a 65 20 3d  ;.  pH->htsize =
07a0: 20 30 3b 0a 20 20 77 68 69 6c 65 28 20 65 6c 65   0;.  while( ele
07b0: 6d 20 29 7b 0a 20 20 20 20 48 61 73 68 45 6c 65  m ){.    HashEle
07c0: 6d 20 2a 6e 65 78 74 5f 65 6c 65 6d 20 3d 20 65  m *next_elem = e
07d0: 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 69  lem->next;.    i
07e0: 66 28 20 70 48 2d 3e 63 6f 70 79 4b 65 79 20 26  f( pH->copyKey &
07f0: 26 20 65 6c 65 6d 2d 3e 70 4b 65 79 20 29 7b 0a  & elem->pKey ){.
0800: 20 20 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72        sqlite3_fr
0810: 65 65 28 65 6c 65 6d 2d 3e 70 4b 65 79 29 3b 0a  ee(elem->pKey);.
0820: 20 20 20 20 7d 0a 20 20 20 20 73 71 6c 69 74 65      }.    sqlite
0830: 33 5f 66 72 65 65 28 65 6c 65 6d 29 3b 0a 20 20  3_free(elem);.  
0840: 20 20 65 6c 65 6d 20 3d 20 6e 65 78 74 5f 65 6c    elem = next_el
0850: 65 6d 3b 0a 20 20 7d 0a 20 20 70 48 2d 3e 63 6f  em;.  }.  pH->co
0860: 75 6e 74 20 3d 20 30 3b 0a 7d 0a 0a 23 69 66 20  unt = 0;.}..#if 
0870: 30 20 2f 2a 20 4e 4f 54 20 55 53 45 44 20 2a 2f  0 /* NOT USED */
0880: 0a 2f 2a 0a 2a 2a 20 48 61 73 68 20 61 6e 64 20  ./*.** Hash and 
0890: 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75 6e 63 74  comparison funct
08a0: 69 6f 6e 73 20 77 68 65 6e 20 74 68 65 20 6d 6f  ions when the mo
08b0: 64 65 20 69 73 20 53 51 4c 49 54 45 5f 48 41 53  de is SQLITE_HAS
08c0: 48 5f 49 4e 54 0a 2a 2f 0a 73 74 61 74 69 63 20  H_INT.*/.static 
08d0: 69 6e 74 20 69 6e 74 48 61 73 68 28 63 6f 6e 73  int intHash(cons
08e0: 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e  t void *pKey, in
08f0: 74 20 6e 4b 65 79 29 7b 0a 20 20 72 65 74 75 72  t nKey){.  retur
0900: 6e 20 6e 4b 65 79 20 5e 20 28 6e 4b 65 79 3c 3c  n nKey ^ (nKey<<
0910: 38 29 20 5e 20 28 6e 4b 65 79 3e 3e 38 29 3b 0a  8) ^ (nKey>>8);.
0920: 7d 0a 73 74 61 74 69 63 20 69 6e 74 20 69 6e 74  }.static int int
0930: 43 6f 6d 70 61 72 65 28 63 6f 6e 73 74 20 76 6f  Compare(const vo
0940: 69 64 20 2a 70 4b 65 79 31 2c 20 69 6e 74 20 6e  id *pKey1, int n
0950: 31 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70  1, const void *p
0960: 4b 65 79 32 2c 20 69 6e 74 20 6e 32 29 7b 0a 20  Key2, int n2){. 
0970: 20 72 65 74 75 72 6e 20 6e 32 20 2d 20 6e 31 3b   return n2 - n1;
0980: 0a 7d 0a 23 65 6e 64 69 66 0a 0a 23 69 66 20 30  .}.#endif..#if 0
0990: 20 2f 2a 20 4e 4f 54 20 55 53 45 44 20 2a 2f 0a   /* NOT USED */.
09a0: 2f 2a 0a 2a 2a 20 48 61 73 68 20 61 6e 64 20 63  /*.** Hash and c
09b0: 6f 6d 70 61 72 69 73 6f 6e 20 66 75 6e 63 74 69  omparison functi
09c0: 6f 6e 73 20 77 68 65 6e 20 74 68 65 20 6d 6f 64  ons when the mod
09d0: 65 20 69 73 20 53 51 4c 49 54 45 5f 48 41 53 48  e is SQLITE_HASH
09e0: 5f 50 4f 49 4e 54 45 52 0a 2a 2f 0a 73 74 61 74  _POINTER.*/.stat
09f0: 69 63 20 69 6e 74 20 70 74 72 48 61 73 68 28 63  ic int ptrHash(c
0a00: 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c  onst void *pKey,
0a10: 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 75 70   int nKey){.  up
0a20: 74 72 20 78 20 3d 20 41 64 64 72 28 70 4b 65 79  tr x = Addr(pKey
0a30: 29 3b 0a 20 20 72 65 74 75 72 6e 20 78 20 5e 20  );.  return x ^ 
0a40: 28 78 3c 3c 38 29 20 5e 20 28 78 3e 3e 38 29 3b  (x<<8) ^ (x>>8);
0a50: 0a 7d 0a 73 74 61 74 69 63 20 69 6e 74 20 70 74  .}.static int pt
0a60: 72 43 6f 6d 70 61 72 65 28 63 6f 6e 73 74 20 76  rCompare(const v
0a70: 6f 69 64 20 2a 70 4b 65 79 31 2c 20 69 6e 74 20  oid *pKey1, int 
0a80: 6e 31 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a  n1, const void *
0a90: 70 4b 65 79 32 2c 20 69 6e 74 20 6e 32 29 7b 0a  pKey2, int n2){.
0aa0: 20 20 69 66 28 20 70 4b 65 79 31 3d 3d 70 4b 65    if( pKey1==pKe
0ab0: 79 32 20 29 20 72 65 74 75 72 6e 20 30 3b 0a 20  y2 ) return 0;. 
0ac0: 20 69 66 28 20 70 4b 65 79 31 3c 70 4b 65 79 32   if( pKey1<pKey2
0ad0: 20 29 20 72 65 74 75 72 6e 20 2d 31 3b 0a 20 20   ) return -1;.  
0ae0: 72 65 74 75 72 6e 20 31 3b 0a 7d 0a 23 65 6e 64  return 1;.}.#end
0af0: 69 66 0a 0a 2f 2a 0a 2a 2a 20 48 61 73 68 20 61  if../*.** Hash a
0b00: 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75  nd comparison fu
0b10: 6e 63 74 69 6f 6e 73 20 77 68 65 6e 20 74 68 65  nctions when the
0b20: 20 6d 6f 64 65 20 69 73 20 53 51 4c 49 54 45 5f   mode is SQLITE_
0b30: 48 41 53 48 5f 53 54 52 49 4e 47 0a 2a 2f 0a 73  HASH_STRING.*/.s
0b40: 74 61 74 69 63 20 69 6e 74 20 73 74 72 48 61 73  tatic int strHas
0b50: 68 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b  h(const void *pK
0b60: 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20  ey, int nKey){. 
0b70: 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a 20 3d   const char *z =
0b80: 20 28 63 6f 6e 73 74 20 63 68 61 72 20 2a 29 70   (const char *)p
0b90: 4b 65 79 3b 0a 20 20 69 6e 74 20 68 20 3d 20 30  Key;.  int h = 0
0ba0: 3b 0a 20 20 69 66 28 20 6e 4b 65 79 3c 3d 30 20  ;.  if( nKey<=0 
0bb0: 29 20 6e 4b 65 79 20 3d 20 73 74 72 6c 65 6e 28  ) nKey = strlen(
0bc0: 7a 29 3b 0a 20 20 77 68 69 6c 65 28 20 6e 4b 65  z);.  while( nKe
0bd0: 79 20 3e 20 30 20 20 29 7b 0a 20 20 20 20 68 20  y > 0  ){.    h 
0be0: 3d 20 28 68 3c 3c 33 29 20 5e 20 68 20 5e 20 73  = (h<<3) ^ h ^ s
0bf0: 71 6c 69 74 65 33 55 70 70 65 72 54 6f 4c 6f 77  qlite3UpperToLow
0c00: 65 72 5b 28 75 6e 73 69 67 6e 65 64 20 63 68 61  er[(unsigned cha
0c10: 72 29 2a 7a 2b 2b 5d 3b 0a 20 20 20 20 6e 4b 65  r)*z++];.    nKe
0c20: 79 2d 2d 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72  y--;.  }.  retur
0c30: 6e 20 68 20 26 20 30 78 37 66 66 66 66 66 66 66  n h & 0x7fffffff
0c40: 3b 0a 7d 0a 73 74 61 74 69 63 20 69 6e 74 20 73  ;.}.static int s
0c50: 74 72 43 6f 6d 70 61 72 65 28 63 6f 6e 73 74 20  trCompare(const 
0c60: 76 6f 69 64 20 2a 70 4b 65 79 31 2c 20 69 6e 74  void *pKey1, int
0c70: 20 6e 31 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20   n1, const void 
0c80: 2a 70 4b 65 79 32 2c 20 69 6e 74 20 6e 32 29 7b  *pKey2, int n2){
0c90: 0a 20 20 69 66 28 20 6e 31 21 3d 6e 32 20 29 20  .  if( n1!=n2 ) 
0ca0: 72 65 74 75 72 6e 20 31 3b 0a 20 20 72 65 74 75  return 1;.  retu
0cb0: 72 6e 20 73 71 6c 69 74 65 33 53 74 72 4e 49 43  rn sqlite3StrNIC
0cc0: 6d 70 28 28 63 6f 6e 73 74 20 63 68 61 72 2a 29  mp((const char*)
0cd0: 70 4b 65 79 31 2c 28 63 6f 6e 73 74 20 63 68 61  pKey1,(const cha
0ce0: 72 2a 29 70 4b 65 79 32 2c 6e 31 29 3b 0a 7d 0a  r*)pKey2,n1);.}.
0cf0: 0a 2f 2a 0a 2a 2a 20 48 61 73 68 20 61 6e 64 20  ./*.** Hash and 
0d00: 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75 6e 63 74  comparison funct
0d10: 69 6f 6e 73 20 77 68 65 6e 20 74 68 65 20 6d 6f  ions when the mo
0d20: 64 65 20 69 73 20 53 51 4c 49 54 45 5f 48 41 53  de is SQLITE_HAS
0d30: 48 5f 42 49 4e 41 52 59 0a 2a 2f 0a 73 74 61 74  H_BINARY.*/.stat
0d40: 69 63 20 69 6e 74 20 62 69 6e 48 61 73 68 28 63  ic int binHash(c
0d50: 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c  onst void *pKey,
0d60: 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 69 6e   int nKey){.  in
0d70: 74 20 68 20 3d 20 30 3b 0a 20 20 63 6f 6e 73 74  t h = 0;.  const
0d80: 20 63 68 61 72 20 2a 7a 20 3d 20 28 63 6f 6e 73   char *z = (cons
0d90: 74 20 63 68 61 72 20 2a 29 70 4b 65 79 3b 0a 20  t char *)pKey;. 
0da0: 20 77 68 69 6c 65 28 20 6e 4b 65 79 2d 2d 20 3e   while( nKey-- >
0db0: 20 30 20 29 7b 0a 20 20 20 20 68 20 3d 20 28 68   0 ){.    h = (h
0dc0: 3c 3c 33 29 20 5e 20 68 20 5e 20 2a 28 7a 2b 2b  <<3) ^ h ^ *(z++
0dd0: 29 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20  );.  }.  return 
0de0: 68 20 26 20 30 78 37 66 66 66 66 66 66 66 3b 0a  h & 0x7fffffff;.
0df0: 7d 0a 73 74 61 74 69 63 20 69 6e 74 20 62 69 6e  }.static int bin
0e00: 43 6f 6d 70 61 72 65 28 63 6f 6e 73 74 20 76 6f  Compare(const vo
0e10: 69 64 20 2a 70 4b 65 79 31 2c 20 69 6e 74 20 6e  id *pKey1, int n
0e20: 31 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70  1, const void *p
0e30: 4b 65 79 32 2c 20 69 6e 74 20 6e 32 29 7b 0a 20  Key2, int n2){. 
0e40: 20 69 66 28 20 6e 31 21 3d 6e 32 20 29 20 72 65   if( n1!=n2 ) re
0e50: 74 75 72 6e 20 31 3b 0a 20 20 72 65 74 75 72 6e  turn 1;.  return
0e60: 20 6d 65 6d 63 6d 70 28 70 4b 65 79 31 2c 70 4b   memcmp(pKey1,pK
0e70: 65 79 32 2c 6e 31 29 3b 0a 7d 0a 0a 2f 2a 0a 2a  ey2,n1);.}../*.*
0e80: 2a 20 52 65 74 75 72 6e 20 61 20 70 6f 69 6e 74  * Return a point
0e90: 65 72 20 74 6f 20 74 68 65 20 61 70 70 72 6f 70  er to the approp
0ea0: 72 69 61 74 65 20 68 61 73 68 20 66 75 6e 63 74  riate hash funct
0eb0: 69 6f 6e 20 67 69 76 65 6e 20 74 68 65 20 6b 65  ion given the ke
0ec0: 79 20 63 6c 61 73 73 2e 0a 2a 2a 0a 2a 2a 20 54  y class..**.** T
0ed0: 68 65 20 43 20 73 79 6e 74 61 78 20 69 6e 20 74  he C syntax in t
0ee0: 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 64 65 66  his function def
0ef0: 69 6e 69 74 69 6f 6e 20 6d 61 79 20 62 65 20 75  inition may be u
0f00: 6e 66 61 6d 69 6c 61 72 20 74 6f 20 73 6f 6d 65  nfamilar to some
0f10: 20 0a 2a 2a 20 70 72 6f 67 72 61 6d 6d 65 72 73   .** programmers
0f20: 2c 20 73 6f 20 77 65 20 70 72 6f 76 69 64 65 20  , so we provide 
0f30: 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 61 64  the following ad
0f40: 64 69 74 69 6f 6e 61 6c 20 65 78 70 6c 61 6e 61  ditional explana
0f50: 74 69 6f 6e 3a 0a 2a 2a 0a 2a 2a 20 54 68 65 20  tion:.**.** The 
0f60: 6e 61 6d 65 20 6f 66 20 74 68 65 20 66 75 6e 63  name of the func
0f70: 74 69 6f 6e 20 69 73 20 22 68 61 73 68 46 75 6e  tion is "hashFun
0f80: 63 74 69 6f 6e 22 2e 20 20 54 68 65 20 66 75 6e  ction".  The fun
0f90: 63 74 69 6f 6e 20 74 61 6b 65 73 20 61 0a 2a 2a  ction takes a.**
0fa0: 20 73 69 6e 67 6c 65 20 70 61 72 61 6d 65 74 65   single paramete
0fb0: 72 20 22 6b 65 79 43 6c 61 73 73 22 2e 20 20 54  r "keyClass".  T
0fc0: 68 65 20 72 65 74 75 72 6e 20 76 61 6c 75 65 20  he return value 
0fd0: 6f 66 20 68 61 73 68 46 75 6e 63 74 69 6f 6e 28  of hashFunction(
0fe0: 29 0a 2a 2a 20 69 73 20 61 20 70 6f 69 6e 74 65  ).** is a pointe
0ff0: 72 20 74 6f 20 61 6e 6f 74 68 65 72 20 66 75 6e  r to another fun
1000: 63 74 69 6f 6e 2e 20 20 53 70 65 63 69 66 69 63  ction.  Specific
1010: 61 6c 6c 79 2c 20 74 68 65 20 72 65 74 75 72 6e  ally, the return
1020: 20 76 61 6c 75 65 0a 2a 2a 20 6f 66 20 68 61 73   value.** of has
1030: 68 46 75 6e 63 74 69 6f 6e 28 29 20 69 73 20 61  hFunction() is a
1040: 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 20 66 75   pointer to a fu
1050: 6e 63 74 69 6f 6e 20 74 68 61 74 20 74 61 6b 65  nction that take
1060: 73 20 74 77 6f 20 70 61 72 61 6d 65 74 65 72 73  s two parameters
1070: 0a 2a 2a 20 77 69 74 68 20 74 79 70 65 73 20 22  .** with types "
1080: 63 6f 6e 73 74 20 76 6f 69 64 2a 22 20 61 6e 64  const void*" and
1090: 20 22 69 6e 74 22 20 61 6e 64 20 72 65 74 75 72   "int" and retur
10a0: 6e 73 20 61 6e 20 22 69 6e 74 22 2e 0a 2a 2f 0a  ns an "int"..*/.
10b0: 73 74 61 74 69 63 20 69 6e 74 20 28 2a 68 61 73  static int (*has
10c0: 68 46 75 6e 63 74 69 6f 6e 28 69 6e 74 20 6b 65  hFunction(int ke
10d0: 79 43 6c 61 73 73 29 29 28 63 6f 6e 73 74 20 76  yClass))(const v
10e0: 6f 69 64 2a 2c 69 6e 74 29 7b 0a 23 69 66 20 30  oid*,int){.#if 0
10f0: 20 20 2f 2a 20 48 41 53 48 5f 49 4e 54 20 61 6e    /* HASH_INT an
1100: 64 20 48 41 53 48 5f 50 4f 49 4e 54 45 52 20 61  d HASH_POINTER a
1110: 72 65 20 6e 65 76 65 72 20 75 73 65 64 20 2a 2f  re never used */
1120: 0a 20 20 73 77 69 74 63 68 28 20 6b 65 79 43 6c  .  switch( keyCl
1130: 61 73 73 20 29 7b 0a 20 20 20 20 63 61 73 65 20  ass ){.    case 
1140: 53 51 4c 49 54 45 5f 48 41 53 48 5f 49 4e 54 3a  SQLITE_HASH_INT:
1150: 20 20 20 20 20 72 65 74 75 72 6e 20 26 69 6e 74       return &int
1160: 48 61 73 68 3b 0a 20 20 20 20 63 61 73 65 20 53  Hash;.    case S
1170: 51 4c 49 54 45 5f 48 41 53 48 5f 50 4f 49 4e 54  QLITE_HASH_POINT
1180: 45 52 3a 20 72 65 74 75 72 6e 20 26 70 74 72 48  ER: return &ptrH
1190: 61 73 68 3b 0a 20 20 20 20 63 61 73 65 20 53 51  ash;.    case SQ
11a0: 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 49 4e 47  LITE_HASH_STRING
11b0: 3a 20 20 72 65 74 75 72 6e 20 26 73 74 72 48 61  :  return &strHa
11c0: 73 68 3b 0a 20 20 20 20 63 61 73 65 20 53 51 4c  sh;.    case SQL
11d0: 49 54 45 5f 48 41 53 48 5f 42 49 4e 41 52 59 3a  ITE_HASH_BINARY:
11e0: 20 20 72 65 74 75 72 6e 20 26 62 69 6e 48 61 73    return &binHas
11f0: 68 3b 3b 0a 20 20 20 20 64 65 66 61 75 6c 74 3a  h;;.    default:
1200: 20 62 72 65 61 6b 3b 0a 20 20 7d 0a 20 20 72 65   break;.  }.  re
1210: 74 75 72 6e 20 30 3b 0a 23 65 6c 73 65 0a 20 20  turn 0;.#else.  
1220: 69 66 28 20 6b 65 79 43 6c 61 73 73 3d 3d 53 51  if( keyClass==SQ
1230: 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 49 4e 47  LITE_HASH_STRING
1240: 20 29 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 26   ){.    return &
1250: 73 74 72 48 61 73 68 3b 0a 20 20 7d 65 6c 73 65  strHash;.  }else
1260: 7b 0a 20 20 20 20 61 73 73 65 72 74 28 20 6b 65  {.    assert( ke
1270: 79 43 6c 61 73 73 3d 3d 53 51 4c 49 54 45 5f 48  yClass==SQLITE_H
1280: 41 53 48 5f 42 49 4e 41 52 59 20 29 3b 0a 20 20  ASH_BINARY );.  
1290: 20 20 72 65 74 75 72 6e 20 26 62 69 6e 48 61 73    return &binHas
12a0: 68 3b 0a 20 20 7d 0a 23 65 6e 64 69 66 0a 7d 0a  h;.  }.#endif.}.
12b0: 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 61 20  ./*.** Return a 
12c0: 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 20 61  pointer to the a
12d0: 70 70 72 6f 70 72 69 61 74 65 20 68 61 73 68 20  ppropriate hash 
12e0: 66 75 6e 63 74 69 6f 6e 20 67 69 76 65 6e 20 74  function given t
12f0: 68 65 20 6b 65 79 20 63 6c 61 73 73 2e 0a 2a 2a  he key class..**
1300: 0a 2a 2a 20 46 6f 72 20 68 65 6c 70 20 69 6e 20  .** For help in 
1310: 69 6e 74 65 72 70 72 65 74 65 64 20 74 68 65 20  interpreted the 
1320: 6f 62 73 63 75 72 65 20 43 20 63 6f 64 65 20 69  obscure C code i
1330: 6e 20 74 68 65 20 66 75 6e 63 74 69 6f 6e 20 64  n the function d
1340: 65 66 69 6e 69 74 69 6f 6e 2c 0a 2a 2a 20 73 65  efinition,.** se
1350: 65 20 74 68 65 20 68 65 61 64 65 72 20 63 6f 6d  e the header com
1360: 6d 65 6e 74 20 6f 6e 20 74 68 65 20 70 72 65 76  ment on the prev
1370: 69 6f 75 73 20 66 75 6e 63 74 69 6f 6e 2e 0a 2a  ious function..*
1380: 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 28 2a 63  /.static int (*c
1390: 6f 6d 70 61 72 65 46 75 6e 63 74 69 6f 6e 28 69  ompareFunction(i
13a0: 6e 74 20 6b 65 79 43 6c 61 73 73 29 29 28 63 6f  nt keyClass))(co
13b0: 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 2c 63 6f  nst void*,int,co
13c0: 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29 7b 0a  nst void*,int){.
13d0: 23 69 66 20 30 20 2f 2a 20 48 41 53 48 5f 49 4e  #if 0 /* HASH_IN
13e0: 54 20 61 6e 64 20 48 41 53 48 5f 50 4f 49 4e 54  T and HASH_POINT
13f0: 45 52 20 61 72 65 20 6e 65 76 65 72 20 75 73 65  ER are never use
1400: 64 20 2a 2f 0a 20 20 73 77 69 74 63 68 28 20 6b  d */.  switch( k
1410: 65 79 43 6c 61 73 73 20 29 7b 0a 20 20 20 20 63  eyClass ){.    c
1420: 61 73 65 20 53 51 4c 49 54 45 5f 48 41 53 48 5f  ase SQLITE_HASH_
1430: 49 4e 54 3a 20 20 20 20 20 72 65 74 75 72 6e 20  INT:     return 
1440: 26 69 6e 74 43 6f 6d 70 61 72 65 3b 0a 20 20 20  &intCompare;.   
1450: 20 63 61 73 65 20 53 51 4c 49 54 45 5f 48 41 53   case SQLITE_HAS
1460: 48 5f 50 4f 49 4e 54 45 52 3a 20 72 65 74 75 72  H_POINTER: retur
1470: 6e 20 26 70 74 72 43 6f 6d 70 61 72 65 3b 0a 20  n &ptrCompare;. 
1480: 20 20 20 63 61 73 65 20 53 51 4c 49 54 45 5f 48     case SQLITE_H
1490: 41 53 48 5f 53 54 52 49 4e 47 3a 20 20 72 65 74  ASH_STRING:  ret
14a0: 75 72 6e 20 26 73 74 72 43 6f 6d 70 61 72 65 3b  urn &strCompare;
14b0: 0a 20 20 20 20 63 61 73 65 20 53 51 4c 49 54 45  .    case SQLITE
14c0: 5f 48 41 53 48 5f 42 49 4e 41 52 59 3a 20 20 72  _HASH_BINARY:  r
14d0: 65 74 75 72 6e 20 26 62 69 6e 43 6f 6d 70 61 72  eturn &binCompar
14e0: 65 3b 0a 20 20 20 20 64 65 66 61 75 6c 74 3a 20  e;.    default: 
14f0: 62 72 65 61 6b 3b 0a 20 20 7d 0a 20 20 72 65 74  break;.  }.  ret
1500: 75 72 6e 20 30 3b 0a 23 65 6c 73 65 0a 20 20 69  urn 0;.#else.  i
1510: 66 28 20 6b 65 79 43 6c 61 73 73 3d 3d 53 51 4c  f( keyClass==SQL
1520: 49 54 45 5f 48 41 53 48 5f 53 54 52 49 4e 47 20  ITE_HASH_STRING 
1530: 29 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 26 73  ){.    return &s
1540: 74 72 43 6f 6d 70 61 72 65 3b 0a 20 20 7d 65 6c  trCompare;.  }el
1550: 73 65 7b 0a 20 20 20 20 61 73 73 65 72 74 28 20  se{.    assert( 
1560: 6b 65 79 43 6c 61 73 73 3d 3d 53 51 4c 49 54 45  keyClass==SQLITE
1570: 5f 48 41 53 48 5f 42 49 4e 41 52 59 20 29 3b 0a  _HASH_BINARY );.
1580: 20 20 20 20 72 65 74 75 72 6e 20 26 62 69 6e 43      return &binC
1590: 6f 6d 70 61 72 65 3b 0a 20 20 7d 0a 23 65 6e 64  ompare;.  }.#end
15a0: 69 66 0a 7d 0a 0a 2f 2a 20 4c 69 6e 6b 20 61 6e  if.}../* Link an
15b0: 20 65 6c 65 6d 65 6e 74 20 69 6e 74 6f 20 74 68   element into th
15c0: 65 20 68 61 73 68 20 74 61 62 6c 65 0a 2a 2f 0a  e hash table.*/.
15d0: 73 74 61 74 69 63 20 76 6f 69 64 20 69 6e 73 65  static void inse
15e0: 72 74 45 6c 65 6d 65 6e 74 28 0a 20 20 48 61 73  rtElement(.  Has
15f0: 68 20 2a 70 48 2c 20 20 20 20 20 20 20 20 20 20  h *pH,          
1600: 20 20 20 20 2f 2a 20 54 68 65 20 63 6f 6d 70 6c      /* The compl
1610: 65 74 65 20 68 61 73 68 20 74 61 62 6c 65 20 2a  ete hash table *
1620: 2f 0a 20 20 73 74 72 75 63 74 20 5f 68 74 20 2a  /.  struct _ht *
1630: 70 45 6e 74 72 79 2c 20 20 20 20 2f 2a 20 54 68  pEntry,    /* Th
1640: 65 20 65 6e 74 72 79 20 69 6e 74 6f 20 77 68 69  e entry into whi
1650: 63 68 20 70 4e 65 77 20 69 73 20 69 6e 73 65 72  ch pNew is inser
1660: 74 65 64 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65  ted */.  HashEle
1670: 6d 20 2a 70 4e 65 77 20 20 20 20 20 20 20 20 20  m *pNew         
1680: 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e 74 20 74  /* The element t
1690: 6f 20 62 65 20 69 6e 73 65 72 74 65 64 20 2a 2f  o be inserted */
16a0: 0a 29 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a  .){.  HashElem *
16b0: 70 48 65 61 64 3b 20 20 20 20 20 20 20 2f 2a 20  pHead;       /* 
16c0: 46 69 72 73 74 20 65 6c 65 6d 65 6e 74 20 61 6c  First element al
16d0: 72 65 61 64 79 20 69 6e 20 70 45 6e 74 72 79 20  ready in pEntry 
16e0: 2a 2f 0a 20 20 70 48 65 61 64 20 3d 20 70 45 6e  */.  pHead = pEn
16f0: 74 72 79 2d 3e 63 68 61 69 6e 3b 0a 20 20 69 66  try->chain;.  if
1700: 28 20 70 48 65 61 64 20 29 7b 0a 20 20 20 20 70  ( pHead ){.    p
1710: 4e 65 77 2d 3e 6e 65 78 74 20 3d 20 70 48 65 61  New->next = pHea
1720: 64 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 70 72 65  d;.    pNew->pre
1730: 76 20 3d 20 70 48 65 61 64 2d 3e 70 72 65 76 3b  v = pHead->prev;
1740: 0a 20 20 20 20 69 66 28 20 70 48 65 61 64 2d 3e  .    if( pHead->
1750: 70 72 65 76 20 29 7b 20 70 48 65 61 64 2d 3e 70  prev ){ pHead->p
1760: 72 65 76 2d 3e 6e 65 78 74 20 3d 20 70 4e 65 77  rev->next = pNew
1770: 3b 20 7d 0a 20 20 20 20 65 6c 73 65 20 20 20 20  ; }.    else    
1780: 20 20 20 20 20 20 20 20 20 7b 20 70 48 2d 3e 66           { pH->f
1790: 69 72 73 74 20 3d 20 70 4e 65 77 3b 20 7d 0a 20  irst = pNew; }. 
17a0: 20 20 20 70 48 65 61 64 2d 3e 70 72 65 76 20 3d     pHead->prev =
17b0: 20 70 4e 65 77 3b 0a 20 20 7d 65 6c 73 65 7b 0a   pNew;.  }else{.
17c0: 20 20 20 20 70 4e 65 77 2d 3e 6e 65 78 74 20 3d      pNew->next =
17d0: 20 70 48 2d 3e 66 69 72 73 74 3b 0a 20 20 20 20   pH->first;.    
17e0: 69 66 28 20 70 48 2d 3e 66 69 72 73 74 20 29 7b  if( pH->first ){
17f0: 20 70 48 2d 3e 66 69 72 73 74 2d 3e 70 72 65 76   pH->first->prev
1800: 20 3d 20 70 4e 65 77 3b 20 7d 0a 20 20 20 20 70   = pNew; }.    p
1810: 4e 65 77 2d 3e 70 72 65 76 20 3d 20 30 3b 0a 20  New->prev = 0;. 
1820: 20 20 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 70     pH->first = p
1830: 4e 65 77 3b 0a 20 20 7d 0a 20 20 70 45 6e 74 72  New;.  }.  pEntr
1840: 79 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20 20 70 45  y->count++;.  pE
1850: 6e 74 72 79 2d 3e 63 68 61 69 6e 20 3d 20 70 4e  ntry->chain = pN
1860: 65 77 3b 0a 7d 0a 0a 0a 2f 2a 20 52 65 73 69 7a  ew;.}.../* Resiz
1870: 65 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65  e the hash table
1880: 20 73 6f 20 74 68 61 74 20 69 74 20 63 61 6e 74   so that it cant
1890: 61 69 6e 73 20 22 6e 65 77 5f 73 69 7a 65 22 20  ains "new_size" 
18a0: 62 75 63 6b 65 74 73 2e 0a 2a 2a 20 22 6e 65 77  buckets..** "new
18b0: 5f 73 69 7a 65 22 20 6d 75 73 74 20 62 65 20 61  _size" must be a
18c0: 20 70 6f 77 65 72 20 6f 66 20 32 2e 20 20 54 68   power of 2.  Th
18d0: 65 20 68 61 73 68 20 74 61 62 6c 65 20 6d 69 67  e hash table mig
18e0: 68 74 20 66 61 69 6c 20 0a 2a 2a 20 74 6f 20 72  ht fail .** to r
18f0: 65 73 69 7a 65 20 69 66 20 73 71 6c 69 74 65 33  esize if sqlite3
1900: 5f 6d 61 6c 6c 6f 63 28 29 20 66 61 69 6c 73 2e  _malloc() fails.
1910: 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20  .*/.static void 
1920: 72 65 68 61 73 68 28 48 61 73 68 20 2a 70 48 2c  rehash(Hash *pH,
1930: 20 69 6e 74 20 6e 65 77 5f 73 69 7a 65 29 7b 0a   int new_size){.
1940: 20 20 73 74 72 75 63 74 20 5f 68 74 20 2a 6e 65    struct _ht *ne
1950: 77 5f 68 74 3b 20 20 20 20 20 20 20 20 20 20 20  w_ht;           
1960: 20 2f 2a 20 54 68 65 20 6e 65 77 20 68 61 73 68   /* The new hash
1970: 20 74 61 62 6c 65 20 2a 2f 0a 20 20 48 61 73 68   table */.  Hash
1980: 45 6c 65 6d 20 2a 65 6c 65 6d 2c 20 2a 6e 65 78  Elem *elem, *nex
1990: 74 5f 65 6c 65 6d 3b 20 20 20 20 2f 2a 20 46 6f  t_elem;    /* Fo
19a0: 72 20 6c 6f 6f 70 69 6e 67 20 6f 76 65 72 20 65  r looping over e
19b0: 78 69 73 74 69 6e 67 20 65 6c 65 6d 65 6e 74 73  xisting elements
19c0: 20 2a 2f 0a 20 20 69 6e 74 20 28 2a 78 48 61 73   */.  int (*xHas
19d0: 68 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69  h)(const void*,i
19e0: 6e 74 29 3b 20 2f 2a 20 54 68 65 20 68 61 73 68  nt); /* The hash
19f0: 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20   function */..  
1a00: 61 73 73 65 72 74 28 20 28 6e 65 77 5f 73 69 7a  assert( (new_siz
1a10: 65 20 26 20 28 6e 65 77 5f 73 69 7a 65 2d 31 29  e & (new_size-1)
1a20: 29 3d 3d 30 20 29 3b 0a 0a 20 20 2f 2a 20 54 68  )==0 );..  /* Th
1a30: 65 72 65 20 69 73 20 61 20 63 61 6c 6c 20 74 6f  ere is a call to
1a40: 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28   sqlite3_malloc(
1a50: 29 20 69 6e 73 69 64 65 20 72 65 68 61 73 68 28  ) inside rehash(
1a60: 29 2e 20 49 66 20 74 68 65 72 65 20 69 73 0a 20  ). If there is. 
1a70: 20 2a 2a 20 61 6c 72 65 61 64 79 20 61 6e 20 61   ** already an a
1a80: 6c 6c 6f 63 61 74 69 6f 6e 20 61 74 20 70 48 2d  llocation at pH-
1a90: 3e 68 74 2c 20 74 68 65 6e 20 69 66 20 74 68 69  >ht, then if thi
1aa0: 73 20 6d 61 6c 6c 6f 63 28 29 20 66 61 69 6c 73  s malloc() fails
1ab0: 20 69 74 0a 20 20 2a 2a 20 69 73 20 62 65 6e 69   it.  ** is beni
1ac0: 67 6e 20 28 73 69 6e 63 65 20 66 61 69 6c 69 6e  gn (since failin
1ad0: 67 20 74 6f 20 72 65 73 69 7a 65 20 61 20 68 61  g to resize a ha
1ae0: 73 68 20 74 61 62 6c 65 20 69 73 20 61 20 70 65  sh table is a pe
1af0: 72 66 6f 72 6d 61 6e 63 65 0a 20 20 2a 2a 20 68  rformance.  ** h
1b00: 69 74 20 6f 6e 6c 79 2c 20 6e 6f 74 20 61 20 66  it only, not a f
1b10: 61 74 61 6c 20 65 72 72 6f 72 29 2e 0a 20 20 2a  atal error)..  *
1b20: 2f 0a 20 20 73 71 6c 69 74 65 33 4d 61 6c 6c 6f  /.  sqlite3Mallo
1b30: 63 42 65 6e 69 67 6e 46 61 69 6c 75 72 65 28 70  cBenignFailure(p
1b40: 48 2d 3e 68 74 73 69 7a 65 3e 30 29 3b 0a 0a 20  H->htsize>0);.. 
1b50: 20 6e 65 77 5f 68 74 20 3d 20 28 73 74 72 75 63   new_ht = (struc
1b60: 74 20 5f 68 74 20 2a 29 73 71 6c 69 74 65 33 4d  t _ht *)sqlite3M
1b70: 61 6c 6c 6f 63 5a 65 72 6f 28 20 6e 65 77 5f 73  allocZero( new_s
1b80: 69 7a 65 2a 73 69 7a 65 6f 66 28 73 74 72 75 63  ize*sizeof(struc
1b90: 74 20 5f 68 74 29 20 29 3b 0a 20 20 69 66 28 20  t _ht) );.  if( 
1ba0: 6e 65 77 5f 68 74 3d 3d 30 20 29 20 72 65 74 75  new_ht==0 ) retu
1bb0: 72 6e 3b 0a 20 20 69 66 28 20 70 48 2d 3e 68 74  rn;.  if( pH->ht
1bc0: 20 29 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28   ) sqlite3_free(
1bd0: 70 48 2d 3e 68 74 29 3b 0a 20 20 70 48 2d 3e 68  pH->ht);.  pH->h
1be0: 74 20 3d 20 6e 65 77 5f 68 74 3b 0a 20 20 70 48  t = new_ht;.  pH
1bf0: 2d 3e 68 74 73 69 7a 65 20 3d 20 6e 65 77 5f 73  ->htsize = new_s
1c00: 69 7a 65 3b 0a 20 20 78 48 61 73 68 20 3d 20 68  ize;.  xHash = h
1c10: 61 73 68 46 75 6e 63 74 69 6f 6e 28 70 48 2d 3e  ashFunction(pH->
1c20: 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20 66 6f 72  keyClass);.  for
1c30: 28 65 6c 65 6d 3d 70 48 2d 3e 66 69 72 73 74 2c  (elem=pH->first,
1c40: 20 70 48 2d 3e 66 69 72 73 74 3d 30 3b 20 65 6c   pH->first=0; el
1c50: 65 6d 3b 20 65 6c 65 6d 20 3d 20 6e 65 78 74 5f  em; elem = next_
1c60: 65 6c 65 6d 29 7b 0a 20 20 20 20 69 6e 74 20 68  elem){.    int h
1c70: 20 3d 20 28 2a 78 48 61 73 68 29 28 65 6c 65 6d   = (*xHash)(elem
1c80: 2d 3e 70 4b 65 79 2c 20 65 6c 65 6d 2d 3e 6e 4b  ->pKey, elem->nK
1c90: 65 79 29 20 26 20 28 6e 65 77 5f 73 69 7a 65 2d  ey) & (new_size-
1ca0: 31 29 3b 0a 20 20 20 20 6e 65 78 74 5f 65 6c 65  1);.    next_ele
1cb0: 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a  m = elem->next;.
1cc0: 20 20 20 20 69 6e 73 65 72 74 45 6c 65 6d 65 6e      insertElemen
1cd0: 74 28 70 48 2c 20 26 6e 65 77 5f 68 74 5b 68 5d  t(pH, &new_ht[h]
1ce0: 2c 20 65 6c 65 6d 29 3b 0a 20 20 7d 0a 7d 0a 0a  , elem);.  }.}..
1cf0: 2f 2a 20 54 68 69 73 20 66 75 6e 63 74 69 6f 6e  /* This function
1d00: 20 28 66 6f 72 20 69 6e 74 65 72 6e 61 6c 20 75   (for internal u
1d10: 73 65 20 6f 6e 6c 79 29 20 6c 6f 63 61 74 65 73  se only) locates
1d20: 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69 6e 20 61   an element in a
1d30: 6e 0a 2a 2a 20 68 61 73 68 20 74 61 62 6c 65 20  n.** hash table 
1d40: 74 68 61 74 20 6d 61 74 63 68 65 73 20 74 68 65  that matches the
1d50: 20 67 69 76 65 6e 20 6b 65 79 2e 20 20 54 68 65   given key.  The
1d60: 20 68 61 73 68 20 66 6f 72 20 74 68 69 73 20 6b   hash for this k
1d70: 65 79 20 68 61 73 0a 2a 2a 20 61 6c 72 65 61 64  ey has.** alread
1d80: 79 20 62 65 65 6e 20 63 6f 6d 70 75 74 65 64 20  y been computed 
1d90: 61 6e 64 20 69 73 20 70 61 73 73 65 64 20 61 73  and is passed as
1da0: 20 74 68 65 20 34 74 68 20 70 61 72 61 6d 65 74   the 4th paramet
1db0: 65 72 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 48 61  er..*/.static Ha
1dc0: 73 68 45 6c 65 6d 20 2a 66 69 6e 64 45 6c 65 6d  shElem *findElem
1dd0: 65 6e 74 47 69 76 65 6e 48 61 73 68 28 0a 20 20  entGivenHash(.  
1de0: 63 6f 6e 73 74 20 48 61 73 68 20 2a 70 48 2c 20  const Hash *pH, 
1df0: 20 20 20 20 2f 2a 20 54 68 65 20 70 48 20 74 6f      /* The pH to
1e00: 20 62 65 20 73 65 61 72 63 68 65 64 20 2a 2f 0a   be searched */.
1e10: 20 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b    const void *pK
1e20: 65 79 2c 20 20 20 2f 2a 20 54 68 65 20 6b 65 79  ey,   /* The key
1e30: 20 77 65 20 61 72 65 20 73 65 61 72 63 68 69 6e   we are searchin
1e40: 67 20 66 6f 72 20 2a 2f 0a 20 20 69 6e 74 20 6e  g for */.  int n
1e50: 4b 65 79 2c 0a 20 20 69 6e 74 20 68 20 20 20 20  Key,.  int h    
1e60: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68             /* Th
1e70: 65 20 68 61 73 68 20 66 6f 72 20 74 68 69 73 20  e hash for this 
1e80: 6b 65 79 2e 20 2a 2f 0a 29 7b 0a 20 20 48 61 73  key. */.){.  Has
1e90: 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20  hElem *elem;    
1ea0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 55              /* U
1eb0: 73 65 64 20 74 6f 20 6c 6f 6f 70 20 74 68 72 75  sed to loop thru
1ec0: 20 74 68 65 20 65 6c 65 6d 65 6e 74 20 6c 69 73   the element lis
1ed0: 74 20 2a 2f 0a 20 20 69 6e 74 20 63 6f 75 6e 74  t */.  int count
1ee0: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
1ef0: 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20        /* Number 
1f00: 6f 66 20 65 6c 65 6d 65 6e 74 73 20 6c 65 66 74  of elements left
1f10: 20 74 6f 20 74 65 73 74 20 2a 2f 0a 20 20 69 6e   to test */.  in
1f20: 74 20 28 2a 78 43 6f 6d 70 61 72 65 29 28 63 6f  t (*xCompare)(co
1f30: 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 2c 63 6f  nst void*,int,co
1f40: 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29 3b 20  nst void*,int); 
1f50: 20 2f 2a 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66   /* comparison f
1f60: 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20 69 66  unction */..  if
1f70: 28 20 70 48 2d 3e 68 74 20 29 7b 0a 20 20 20 20  ( pH->ht ){.    
1f80: 73 74 72 75 63 74 20 5f 68 74 20 2a 70 45 6e 74  struct _ht *pEnt
1f90: 72 79 20 3d 20 26 70 48 2d 3e 68 74 5b 68 5d 3b  ry = &pH->ht[h];
1fa0: 0a 20 20 20 20 65 6c 65 6d 20 3d 20 70 45 6e 74  .    elem = pEnt
1fb0: 72 79 2d 3e 63 68 61 69 6e 3b 0a 20 20 20 20 63  ry->chain;.    c
1fc0: 6f 75 6e 74 20 3d 20 70 45 6e 74 72 79 2d 3e 63  ount = pEntry->c
1fd0: 6f 75 6e 74 3b 0a 20 20 20 20 78 43 6f 6d 70 61  ount;.    xCompa
1fe0: 72 65 20 3d 20 63 6f 6d 70 61 72 65 46 75 6e 63  re = compareFunc
1ff0: 74 69 6f 6e 28 70 48 2d 3e 6b 65 79 43 6c 61 73  tion(pH->keyClas
2000: 73 29 3b 0a 20 20 20 20 77 68 69 6c 65 28 20 63  s);.    while( c
2010: 6f 75 6e 74 2d 2d 20 26 26 20 65 6c 65 6d 20 29  ount-- && elem )
2020: 7b 0a 20 20 20 20 20 20 69 66 28 20 28 2a 78 43  {.      if( (*xC
2030: 6f 6d 70 61 72 65 29 28 65 6c 65 6d 2d 3e 70 4b  ompare)(elem->pK
2040: 65 79 2c 65 6c 65 6d 2d 3e 6e 4b 65 79 2c 70 4b  ey,elem->nKey,pK
2050: 65 79 2c 6e 4b 65 79 29 3d 3d 30 20 29 7b 20 0a  ey,nKey)==0 ){ .
2060: 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 65          return e
2070: 6c 65 6d 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20  lem;.      }.   
2080: 20 20 20 65 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e     elem = elem->
2090: 6e 65 78 74 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a  next;.    }.  }.
20a0: 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a 0a 2f    return 0;.}../
20b0: 2a 20 52 65 6d 6f 76 65 20 61 20 73 69 6e 67 6c  * Remove a singl
20c0: 65 20 65 6e 74 72 79 20 66 72 6f 6d 20 74 68 65  e entry from the
20d0: 20 68 61 73 68 20 74 61 62 6c 65 20 67 69 76 65   hash table give
20e0: 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74  n a pointer to t
20f0: 68 61 74 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 61  hat.** element a
2100: 6e 64 20 61 20 68 61 73 68 20 6f 6e 20 74 68 65  nd a hash on the
2110: 20 65 6c 65 6d 65 6e 74 27 73 20 6b 65 79 2e 0a   element's key..
2120: 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 72  */.static void r
2130: 65 6d 6f 76 65 45 6c 65 6d 65 6e 74 47 69 76 65  emoveElementGive
2140: 6e 48 61 73 68 28 0a 20 20 48 61 73 68 20 2a 70  nHash(.  Hash *p
2150: 48 2c 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68  H,         /* Th
2160: 65 20 70 48 20 63 6f 6e 74 61 69 6e 69 6e 67 20  e pH containing 
2170: 22 65 6c 65 6d 22 20 2a 2f 0a 20 20 48 61 73 68  "elem" */.  Hash
2180: 45 6c 65 6d 2a 20 65 6c 65 6d 2c 20 20 20 2f 2a  Elem* elem,   /*
2190: 20 54 68 65 20 65 6c 65 6d 65 6e 74 20 74 6f 20   The element to 
21a0: 62 65 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20  be removed from 
21b0: 74 68 65 20 70 48 20 2a 2f 0a 20 20 69 6e 74 20  the pH */.  int 
21c0: 68 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  h             /*
21d0: 20 48 61 73 68 20 76 61 6c 75 65 20 66 6f 72 20   Hash value for 
21e0: 74 68 65 20 65 6c 65 6d 65 6e 74 20 2a 2f 0a 29  the element */.)
21f0: 7b 0a 20 20 73 74 72 75 63 74 20 5f 68 74 20 2a  {.  struct _ht *
2200: 70 45 6e 74 72 79 3b 0a 20 20 69 66 28 20 65 6c  pEntry;.  if( el
2210: 65 6d 2d 3e 70 72 65 76 20 29 7b 0a 20 20 20 20  em->prev ){.    
2220: 65 6c 65 6d 2d 3e 70 72 65 76 2d 3e 6e 65 78 74  elem->prev->next
2230: 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 20 0a   = elem->next; .
2240: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 70 48 2d    }else{.    pH-
2250: 3e 66 69 72 73 74 20 3d 20 65 6c 65 6d 2d 3e 6e  >first = elem->n
2260: 65 78 74 3b 0a 20 20 7d 0a 20 20 69 66 28 20 65  ext;.  }.  if( e
2270: 6c 65 6d 2d 3e 6e 65 78 74 20 29 7b 0a 20 20 20  lem->next ){.   
2280: 20 65 6c 65 6d 2d 3e 6e 65 78 74 2d 3e 70 72 65   elem->next->pre
2290: 76 20 3d 20 65 6c 65 6d 2d 3e 70 72 65 76 3b 0a  v = elem->prev;.
22a0: 20 20 7d 0a 20 20 70 45 6e 74 72 79 20 3d 20 26    }.  pEntry = &
22b0: 70 48 2d 3e 68 74 5b 68 5d 3b 0a 20 20 69 66 28  pH->ht[h];.  if(
22c0: 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3d 3d   pEntry->chain==
22d0: 65 6c 65 6d 20 29 7b 0a 20 20 20 20 70 45 6e 74  elem ){.    pEnt
22e0: 72 79 2d 3e 63 68 61 69 6e 20 3d 20 65 6c 65 6d  ry->chain = elem
22f0: 2d 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20 20 70 45  ->next;.  }.  pE
2300: 6e 74 72 79 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a 20  ntry->count--;. 
2310: 20 69 66 28 20 70 45 6e 74 72 79 2d 3e 63 6f 75   if( pEntry->cou
2320: 6e 74 3c 3d 30 20 29 7b 0a 20 20 20 20 70 45 6e  nt<=0 ){.    pEn
2330: 74 72 79 2d 3e 63 68 61 69 6e 20 3d 20 30 3b 0a  try->chain = 0;.
2340: 20 20 7d 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f    }.  if( pH->co
2350: 70 79 4b 65 79 20 29 7b 0a 20 20 20 20 73 71 6c  pyKey ){.    sql
2360: 69 74 65 33 5f 66 72 65 65 28 65 6c 65 6d 2d 3e  ite3_free(elem->
2370: 70 4b 65 79 29 3b 0a 20 20 7d 0a 20 20 73 71 6c  pKey);.  }.  sql
2380: 69 74 65 33 5f 66 72 65 65 28 20 65 6c 65 6d 20  ite3_free( elem 
2390: 29 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 2d 2d  );.  pH->count--
23a0: 3b 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f 75 6e  ;.  if( pH->coun
23b0: 74 3c 3d 30 20 29 7b 0a 20 20 20 20 61 73 73 65  t<=0 ){.    asse
23c0: 72 74 28 20 70 48 2d 3e 66 69 72 73 74 3d 3d 30  rt( pH->first==0
23d0: 20 29 3b 0a 20 20 20 20 61 73 73 65 72 74 28 20   );.    assert( 
23e0: 70 48 2d 3e 63 6f 75 6e 74 3d 3d 30 20 29 3b 0a  pH->count==0 );.
23f0: 20 20 20 20 73 71 6c 69 74 65 33 48 61 73 68 43      sqlite3HashC
2400: 6c 65 61 72 28 70 48 29 3b 0a 20 20 7d 0a 7d 0a  lear(pH);.  }.}.
2410: 0a 2f 2a 20 41 74 74 65 6d 70 74 20 74 6f 20 6c  ./* Attempt to l
2420: 6f 63 61 74 65 20 61 6e 20 65 6c 65 6d 65 6e 74  ocate an element
2430: 20 6f 66 20 74 68 65 20 68 61 73 68 20 74 61 62   of the hash tab
2440: 6c 65 20 70 48 20 77 69 74 68 20 61 20 6b 65 79  le pH with a key
2450: 0a 2a 2a 20 74 68 61 74 20 6d 61 74 63 68 65 73  .** that matches
2460: 20 70 4b 65 79 2c 6e 4b 65 79 2e 20 20 52 65 74   pKey,nKey.  Ret
2470: 75 72 6e 20 74 68 65 20 64 61 74 61 20 66 6f 72  urn the data for
2480: 20 74 68 69 73 20 65 6c 65 6d 65 6e 74 20 69 66   this element if
2490: 20 69 74 20 69 73 0a 2a 2a 20 66 6f 75 6e 64 2c   it is.** found,
24a0: 20 6f 72 20 4e 55 4c 4c 20 69 66 20 74 68 65 72   or NULL if ther
24b0: 65 20 69 73 20 6e 6f 20 6d 61 74 63 68 2e 0a 2a  e is no match..*
24c0: 2f 0a 76 6f 69 64 20 2a 73 71 6c 69 74 65 33 48  /.void *sqlite3H
24d0: 61 73 68 46 69 6e 64 28 63 6f 6e 73 74 20 48 61  ashFind(const Ha
24e0: 73 68 20 2a 70 48 2c 20 63 6f 6e 73 74 20 76 6f  sh *pH, const vo
24f0: 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b  id *pKey, int nK
2500: 65 79 29 7b 0a 20 20 69 6e 74 20 68 3b 20 20 20  ey){.  int h;   
2510: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41 20 68            /* A h
2520: 61 73 68 20 6f 6e 20 6b 65 79 20 2a 2f 0a 20 20  ash on key */.  
2530: 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20  HashElem *elem; 
2540: 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e     /* The elemen
2550: 74 20 74 68 61 74 20 6d 61 74 63 68 65 73 20 6b  t that matches k
2560: 65 79 20 2a 2f 0a 20 20 69 6e 74 20 28 2a 78 48  ey */.  int (*xH
2570: 61 73 68 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a  ash)(const void*
2580: 2c 69 6e 74 29 3b 20 20 2f 2a 20 54 68 65 20 68  ,int);  /* The h
2590: 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a  ash function */.
25a0: 0a 20 20 69 66 28 20 70 48 3d 3d 30 20 7c 7c 20  .  if( pH==0 || 
25b0: 70 48 2d 3e 68 74 3d 3d 30 20 29 20 72 65 74 75  pH->ht==0 ) retu
25c0: 72 6e 20 30 3b 0a 20 20 78 48 61 73 68 20 3d 20  rn 0;.  xHash = 
25d0: 68 61 73 68 46 75 6e 63 74 69 6f 6e 28 70 48 2d  hashFunction(pH-
25e0: 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20 61 73  >keyClass);.  as
25f0: 73 65 72 74 28 20 78 48 61 73 68 21 3d 30 20 29  sert( xHash!=0 )
2600: 3b 0a 20 20 68 20 3d 20 28 2a 78 48 61 73 68 29  ;.  h = (*xHash)
2610: 28 70 4b 65 79 2c 6e 4b 65 79 29 3b 0a 20 20 61  (pKey,nKey);.  a
2620: 73 73 65 72 74 28 20 28 70 48 2d 3e 68 74 73 69  ssert( (pH->htsi
2630: 7a 65 20 26 20 28 70 48 2d 3e 68 74 73 69 7a 65  ze & (pH->htsize
2640: 2d 31 29 29 3d 3d 30 20 29 3b 0a 20 20 65 6c 65  -1))==0 );.  ele
2650: 6d 20 3d 20 66 69 6e 64 45 6c 65 6d 65 6e 74 47  m = findElementG
2660: 69 76 65 6e 48 61 73 68 28 70 48 2c 70 4b 65 79  ivenHash(pH,pKey
2670: 2c 6e 4b 65 79 2c 20 68 20 26 20 28 70 48 2d 3e  ,nKey, h & (pH->
2680: 68 74 73 69 7a 65 2d 31 29 29 3b 0a 20 20 72 65  htsize-1));.  re
2690: 74 75 72 6e 20 65 6c 65 6d 20 3f 20 65 6c 65 6d  turn elem ? elem
26a0: 2d 3e 64 61 74 61 20 3a 20 30 3b 0a 7d 0a 0a 2f  ->data : 0;.}../
26b0: 2a 20 49 6e 73 65 72 74 20 61 6e 20 65 6c 65 6d  * Insert an elem
26c0: 65 6e 74 20 69 6e 74 6f 20 74 68 65 20 68 61 73  ent into the has
26d0: 68 20 74 61 62 6c 65 20 70 48 2e 20 20 54 68 65  h table pH.  The
26e0: 20 6b 65 79 20 69 73 20 70 4b 65 79 2c 6e 4b 65   key is pKey,nKe
26f0: 79 0a 2a 2a 20 61 6e 64 20 74 68 65 20 64 61 74  y.** and the dat
2700: 61 20 69 73 20 22 64 61 74 61 22 2e 0a 2a 2a 0a  a is "data"..**.
2710: 2a 2a 20 49 66 20 6e 6f 20 65 6c 65 6d 65 6e 74  ** If no element
2720: 20 65 78 69 73 74 73 20 77 69 74 68 20 61 20 6d   exists with a m
2730: 61 74 63 68 69 6e 67 20 6b 65 79 2c 20 74 68 65  atching key, the
2740: 6e 20 61 20 6e 65 77 0a 2a 2a 20 65 6c 65 6d 65  n a new.** eleme
2750: 6e 74 20 69 73 20 63 72 65 61 74 65 64 2e 20 20  nt is created.  
2760: 41 20 63 6f 70 79 20 6f 66 20 74 68 65 20 6b 65  A copy of the ke
2770: 79 20 69 73 20 6d 61 64 65 20 69 66 20 74 68 65  y is made if the
2780: 20 63 6f 70 79 4b 65 79 0a 2a 2a 20 66 6c 61 67   copyKey.** flag
2790: 20 69 73 20 73 65 74 2e 20 20 4e 55 4c 4c 20 69   is set.  NULL i
27a0: 73 20 72 65 74 75 72 6e 65 64 2e 0a 2a 2a 0a 2a  s returned..**.*
27b0: 2a 20 49 66 20 61 6e 6f 74 68 65 72 20 65 6c 65  * If another ele
27c0: 6d 65 6e 74 20 61 6c 72 65 61 64 79 20 65 78 69  ment already exi
27d0: 73 74 73 20 77 69 74 68 20 74 68 65 20 73 61 6d  sts with the sam
27e0: 65 20 6b 65 79 2c 20 74 68 65 6e 20 74 68 65 0a  e key, then the.
27f0: 2a 2a 20 6e 65 77 20 64 61 74 61 20 72 65 70 6c  ** new data repl
2800: 61 63 65 73 20 74 68 65 20 6f 6c 64 20 64 61 74  aces the old dat
2810: 61 20 61 6e 64 20 74 68 65 20 6f 6c 64 20 64 61  a and the old da
2820: 74 61 20 69 73 20 72 65 74 75 72 6e 65 64 2e 0a  ta is returned..
2830: 2a 2a 20 54 68 65 20 6b 65 79 20 69 73 20 6e 6f  ** The key is no
2840: 74 20 63 6f 70 69 65 64 20 69 6e 20 74 68 69 73  t copied in this
2850: 20 69 6e 73 74 61 6e 63 65 2e 20 20 49 66 20 61   instance.  If a
2860: 20 6d 61 6c 6c 6f 63 20 66 61 69 6c 73 2c 20 74   malloc fails, t
2870: 68 65 6e 0a 2a 2a 20 74 68 65 20 6e 65 77 20 64  hen.** the new d
2880: 61 74 61 20 69 73 20 72 65 74 75 72 6e 65 64 20  ata is returned 
2890: 61 6e 64 20 74 68 65 20 68 61 73 68 20 74 61 62  and the hash tab
28a0: 6c 65 20 69 73 20 75 6e 63 68 61 6e 67 65 64 2e  le is unchanged.
28b0: 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 65 20 22 64  .**.** If the "d
28c0: 61 74 61 22 20 70 61 72 61 6d 65 74 65 72 20 74  ata" parameter t
28d0: 6f 20 74 68 69 73 20 66 75 6e 63 74 69 6f 6e 20  o this function 
28e0: 69 73 20 4e 55 4c 4c 2c 20 74 68 65 6e 20 74 68  is NULL, then th
28f0: 65 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 63 6f 72  e.** element cor
2900: 72 65 73 70 6f 6e 64 69 6e 67 20 74 6f 20 22 6b  responding to "k
2910: 65 79 22 20 69 73 20 72 65 6d 6f 76 65 64 20 66  ey" is removed f
2920: 72 6f 6d 20 74 68 65 20 68 61 73 68 20 74 61 62  rom the hash tab
2930: 6c 65 2e 0a 2a 2f 0a 76 6f 69 64 20 2a 73 71 6c  le..*/.void *sql
2940: 69 74 65 33 48 61 73 68 49 6e 73 65 72 74 28 48  ite3HashInsert(H
2950: 61 73 68 20 2a 70 48 2c 20 63 6f 6e 73 74 20 76  ash *pH, const v
2960: 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e  oid *pKey, int n
2970: 4b 65 79 2c 20 76 6f 69 64 20 2a 64 61 74 61 29  Key, void *data)
2980: 7b 0a 20 20 69 6e 74 20 68 72 61 77 3b 20 20 20  {.  int hraw;   
2990: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52 61 77            /* Raw
29a0: 20 68 61 73 68 20 76 61 6c 75 65 20 6f 66 20 74   hash value of t
29b0: 68 65 20 6b 65 79 20 2a 2f 0a 20 20 69 6e 74 20  he key */.  int 
29c0: 68 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  h;              
29d0: 20 20 2f 2a 20 74 68 65 20 68 61 73 68 20 6f 66    /* the hash of
29e0: 20 74 68 65 20 6b 65 79 20 6d 6f 64 75 6c 6f 20   the key modulo 
29f0: 68 61 73 68 20 74 61 62 6c 65 20 73 69 7a 65 20  hash table size 
2a00: 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65  */.  HashElem *e
2a10: 6c 65 6d 3b 20 20 20 20 20 20 20 2f 2a 20 55 73  lem;       /* Us
2a20: 65 64 20 74 6f 20 6c 6f 6f 70 20 74 68 72 75 20  ed to loop thru 
2a30: 74 68 65 20 65 6c 65 6d 65 6e 74 20 6c 69 73 74  the element list
2a40: 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a   */.  HashElem *
2a50: 6e 65 77 5f 65 6c 65 6d 3b 20 20 20 2f 2a 20 4e  new_elem;   /* N
2a60: 65 77 20 65 6c 65 6d 65 6e 74 20 61 64 64 65 64  ew element added
2a70: 20 74 6f 20 74 68 65 20 70 48 20 2a 2f 0a 20 20   to the pH */.  
2a80: 69 6e 74 20 28 2a 78 48 61 73 68 29 28 63 6f 6e  int (*xHash)(con
2a90: 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29 3b 20 20  st void*,int);  
2aa0: 2f 2a 20 54 68 65 20 68 61 73 68 20 66 75 6e 63  /* The hash func
2ab0: 74 69 6f 6e 20 2a 2f 0a 0a 20 20 61 73 73 65 72  tion */..  asser
2ac0: 74 28 20 70 48 21 3d 30 20 29 3b 0a 20 20 78 48  t( pH!=0 );.  xH
2ad0: 61 73 68 20 3d 20 68 61 73 68 46 75 6e 63 74 69  ash = hashFuncti
2ae0: 6f 6e 28 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29  on(pH->keyClass)
2af0: 3b 0a 20 20 61 73 73 65 72 74 28 20 78 48 61 73  ;.  assert( xHas
2b00: 68 21 3d 30 20 29 3b 0a 20 20 68 72 61 77 20 3d  h!=0 );.  hraw =
2b10: 20 28 2a 78 48 61 73 68 29 28 70 4b 65 79 2c 20   (*xHash)(pKey, 
2b20: 6e 4b 65 79 29 3b 0a 20 20 61 73 73 65 72 74 28  nKey);.  assert(
2b30: 20 28 70 48 2d 3e 68 74 73 69 7a 65 20 26 20 28   (pH->htsize & (
2b40: 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29 29 3d 3d  pH->htsize-1))==
2b50: 30 20 29 3b 0a 20 20 68 20 3d 20 68 72 61 77 20  0 );.  h = hraw 
2b60: 26 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29  & (pH->htsize-1)
2b70: 3b 0a 20 20 65 6c 65 6d 20 3d 20 66 69 6e 64 45  ;.  elem = findE
2b80: 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28  lementGivenHash(
2b90: 70 48 2c 70 4b 65 79 2c 6e 4b 65 79 2c 68 29 3b  pH,pKey,nKey,h);
2ba0: 0a 20 20 69 66 28 20 65 6c 65 6d 20 29 7b 0a 20  .  if( elem ){. 
2bb0: 20 20 20 76 6f 69 64 20 2a 6f 6c 64 5f 64 61 74     void *old_dat
2bc0: 61 20 3d 20 65 6c 65 6d 2d 3e 64 61 74 61 3b 0a  a = elem->data;.
2bd0: 20 20 20 20 69 66 28 20 64 61 74 61 3d 3d 30 20      if( data==0 
2be0: 29 7b 0a 20 20 20 20 20 20 72 65 6d 6f 76 65 45  ){.      removeE
2bf0: 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28  lementGivenHash(
2c00: 70 48 2c 65 6c 65 6d 2c 68 29 3b 0a 20 20 20 20  pH,elem,h);.    
2c10: 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 65 6c 65  }else{.      ele
2c20: 6d 2d 3e 64 61 74 61 20 3d 20 64 61 74 61 3b 0a  m->data = data;.
2c30: 20 20 20 20 7d 0a 20 20 20 20 72 65 74 75 72 6e      }.    return
2c40: 20 6f 6c 64 5f 64 61 74 61 3b 0a 20 20 7d 0a 20   old_data;.  }. 
2c50: 20 69 66 28 20 64 61 74 61 3d 3d 30 20 29 20 72   if( data==0 ) r
2c60: 65 74 75 72 6e 20 30 3b 0a 20 20 6e 65 77 5f 65  eturn 0;.  new_e
2c70: 6c 65 6d 20 3d 20 28 48 61 73 68 45 6c 65 6d 2a  lem = (HashElem*
2c80: 29 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28  )sqlite3_malloc(
2c90: 20 73 69 7a 65 6f 66 28 48 61 73 68 45 6c 65 6d   sizeof(HashElem
2ca0: 29 20 29 3b 0a 20 20 69 66 28 20 6e 65 77 5f 65  ) );.  if( new_e
2cb0: 6c 65 6d 3d 3d 30 20 29 20 72 65 74 75 72 6e 20  lem==0 ) return 
2cc0: 64 61 74 61 3b 0a 20 20 69 66 28 20 70 48 2d 3e  data;.  if( pH->
2cd0: 63 6f 70 79 4b 65 79 20 26 26 20 70 4b 65 79 21  copyKey && pKey!
2ce0: 3d 30 20 29 7b 0a 20 20 20 20 6e 65 77 5f 65 6c  =0 ){.    new_el
2cf0: 65 6d 2d 3e 70 4b 65 79 20 3d 20 73 71 6c 69 74  em->pKey = sqlit
2d00: 65 33 5f 6d 61 6c 6c 6f 63 28 20 6e 4b 65 79 20  e3_malloc( nKey 
2d10: 29 3b 0a 20 20 20 20 69 66 28 20 6e 65 77 5f 65  );.    if( new_e
2d20: 6c 65 6d 2d 3e 70 4b 65 79 3d 3d 30 20 29 7b 0a  lem->pKey==0 ){.
2d30: 20 20 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72        sqlite3_fr
2d40: 65 65 28 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20 20  ee(new_elem);.  
2d50: 20 20 20 20 72 65 74 75 72 6e 20 64 61 74 61 3b      return data;
2d60: 0a 20 20 20 20 7d 0a 20 20 20 20 6d 65 6d 63 70  .    }.    memcp
2d70: 79 28 28 76 6f 69 64 2a 29 6e 65 77 5f 65 6c 65  y((void*)new_ele
2d80: 6d 2d 3e 70 4b 65 79 2c 20 70 4b 65 79 2c 20 6e  m->pKey, pKey, n
2d90: 4b 65 79 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20  Key);.  }else{. 
2da0: 20 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65     new_elem->pKe
2db0: 79 20 3d 20 28 76 6f 69 64 2a 29 70 4b 65 79 3b  y = (void*)pKey;
2dc0: 0a 20 20 7d 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d  .  }.  new_elem-
2dd0: 3e 6e 4b 65 79 20 3d 20 6e 4b 65 79 3b 0a 20 20  >nKey = nKey;.  
2de0: 70 48 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20 20 69  pH->count++;.  i
2df0: 66 28 20 70 48 2d 3e 68 74 73 69 7a 65 3d 3d 30  f( pH->htsize==0
2e00: 20 29 7b 0a 20 20 20 20 72 65 68 61 73 68 28 70   ){.    rehash(p
2e10: 48 2c 38 29 3b 0a 20 20 20 20 69 66 28 20 70 48  H,8);.    if( pH
2e20: 2d 3e 68 74 73 69 7a 65 3d 3d 30 20 29 7b 0a 20  ->htsize==0 ){. 
2e30: 20 20 20 20 20 70 48 2d 3e 63 6f 75 6e 74 20 3d       pH->count =
2e40: 20 30 3b 0a 20 20 20 20 20 20 69 66 28 20 70 48   0;.      if( pH
2e50: 2d 3e 63 6f 70 79 4b 65 79 20 29 7b 0a 20 20 20  ->copyKey ){.   
2e60: 20 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65       sqlite3_fre
2e70: 65 28 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79  e(new_elem->pKey
2e80: 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20  );.      }.     
2e90: 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 6e 65   sqlite3_free(ne
2ea0: 77 5f 65 6c 65 6d 29 3b 0a 20 20 20 20 20 20 72  w_elem);.      r
2eb0: 65 74 75 72 6e 20 64 61 74 61 3b 0a 20 20 20 20  eturn data;.    
2ec0: 7d 0a 20 20 7d 0a 20 20 69 66 28 20 70 48 2d 3e  }.  }.  if( pH->
2ed0: 63 6f 75 6e 74 20 3e 20 70 48 2d 3e 68 74 73 69  count > pH->htsi
2ee0: 7a 65 20 29 7b 0a 20 20 20 20 72 65 68 61 73 68  ze ){.    rehash
2ef0: 28 70 48 2c 70 48 2d 3e 68 74 73 69 7a 65 2a 32  (pH,pH->htsize*2
2f00: 29 3b 0a 20 20 7d 0a 20 20 61 73 73 65 72 74 28  );.  }.  assert(
2f10: 20 70 48 2d 3e 68 74 73 69 7a 65 3e 30 20 29 3b   pH->htsize>0 );
2f20: 0a 20 20 61 73 73 65 72 74 28 20 28 70 48 2d 3e  .  assert( (pH->
2f30: 68 74 73 69 7a 65 20 26 20 28 70 48 2d 3e 68 74  htsize & (pH->ht
2f40: 73 69 7a 65 2d 31 29 29 3d 3d 30 20 29 3b 0a 20  size-1))==0 );. 
2f50: 20 68 20 3d 20 68 72 61 77 20 26 20 28 70 48 2d   h = hraw & (pH-
2f60: 3e 68 74 73 69 7a 65 2d 31 29 3b 0a 20 20 69 6e  >htsize-1);.  in
2f70: 73 65 72 74 45 6c 65 6d 65 6e 74 28 70 48 2c 20  sertElement(pH, 
2f80: 26 70 48 2d 3e 68 74 5b 68 5d 2c 20 6e 65 77 5f  &pH->ht[h], new_
2f90: 65 6c 65 6d 29 3b 0a 20 20 6e 65 77 5f 65 6c 65  elem);.  new_ele
2fa0: 6d 2d 3e 64 61 74 61 20 3d 20 64 61 74 61 3b 0a  m->data = data;.
2fb0: 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a          return 0;.}.