/ Hex Artifact Content
Login

Artifact 449f3d6620193aa557f5d86cbc5cc6b87702b185:


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 38 20 32 30 30 36 2f 30 32 2f  ,v 1.18 2006/02/
01e0: 31 34 20 31 30 3a 34 38 3a 33 39 20 64 61 6e 69  14 10:48:39 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 20 20 70 4e 65 77  ->ht = 0;.  pNew
0620: 2d 3e 78 4d 61 6c 6c 6f 63 20 3d 20 73 71 6c 69  ->xMalloc = sqli
0630: 74 65 33 4d 61 6c 6c 6f 63 58 3b 0a 20 20 70 4e  te3MallocX;.  pN
0640: 65 77 2d 3e 78 46 72 65 65 20 3d 20 73 71 6c 69  ew->xFree = sqli
0650: 74 65 33 46 72 65 65 58 3b 0a 7d 0a 0a 2f 2a 20  te3FreeX;.}../* 
0660: 52 65 6d 6f 76 65 20 61 6c 6c 20 65 6e 74 72 69  Remove all entri
0670: 65 73 20 66 72 6f 6d 20 61 20 68 61 73 68 20 74  es from a hash t
0680: 61 62 6c 65 2e 20 20 52 65 63 6c 61 69 6d 20 61  able.  Reclaim a
0690: 6c 6c 20 6d 65 6d 6f 72 79 2e 0a 2a 2a 20 43 61  ll memory..** Ca
06a0: 6c 6c 20 74 68 69 73 20 72 6f 75 74 69 6e 65 20  ll this routine 
06b0: 74 6f 20 64 65 6c 65 74 65 20 61 20 68 61 73 68  to delete a hash
06c0: 20 74 61 62 6c 65 20 6f 72 20 74 6f 20 72 65 73   table or to res
06d0: 65 74 20 61 20 68 61 73 68 20 74 61 62 6c 65 0a  et a hash table.
06e0: 2a 2a 20 74 6f 20 74 68 65 20 65 6d 70 74 79 20  ** to the empty 
06f0: 73 74 61 74 65 2e 0a 2a 2f 0a 76 6f 69 64 20 73  state..*/.void s
0700: 71 6c 69 74 65 33 48 61 73 68 43 6c 65 61 72 28  qlite3HashClear(
0710: 48 61 73 68 20 2a 70 48 29 7b 0a 20 20 48 61 73  Hash *pH){.  Has
0720: 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20  hElem *elem;    
0730: 20 20 20 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f 70       /* For loop
0740: 69 6e 67 20 6f 76 65 72 20 61 6c 6c 20 65 6c 65  ing over all ele
0750: 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 74 61 62  ments of the tab
0760: 6c 65 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28  le */..  assert(
0770: 20 70 48 21 3d 30 20 29 3b 0a 20 20 65 6c 65 6d   pH!=0 );.  elem
0780: 20 3d 20 70 48 2d 3e 66 69 72 73 74 3b 0a 20 20   = pH->first;.  
0790: 70 48 2d 3e 66 69 72 73 74 20 3d 20 30 3b 0a 20  pH->first = 0;. 
07a0: 20 69 66 28 20 70 48 2d 3e 68 74 20 29 20 70 48   if( pH->ht ) pH
07b0: 2d 3e 78 46 72 65 65 28 70 48 2d 3e 68 74 29 3b  ->xFree(pH->ht);
07c0: 0a 20 20 70 48 2d 3e 68 74 20 3d 20 30 3b 0a 20  .  pH->ht = 0;. 
07d0: 20 70 48 2d 3e 68 74 73 69 7a 65 20 3d 20 30 3b   pH->htsize = 0;
07e0: 0a 20 20 77 68 69 6c 65 28 20 65 6c 65 6d 20 29  .  while( elem )
07f0: 7b 0a 20 20 20 20 48 61 73 68 45 6c 65 6d 20 2a  {.    HashElem *
0800: 6e 65 78 74 5f 65 6c 65 6d 20 3d 20 65 6c 65 6d  next_elem = elem
0810: 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 69 66 28 20  ->next;.    if( 
0820: 70 48 2d 3e 63 6f 70 79 4b 65 79 20 26 26 20 65  pH->copyKey && e
0830: 6c 65 6d 2d 3e 70 4b 65 79 20 29 7b 0a 20 20 20  lem->pKey ){.   
0840: 20 20 20 70 48 2d 3e 78 46 72 65 65 28 65 6c 65     pH->xFree(ele
0850: 6d 2d 3e 70 4b 65 79 29 3b 0a 20 20 20 20 7d 0a  m->pKey);.    }.
0860: 20 20 20 20 70 48 2d 3e 78 46 72 65 65 28 65 6c      pH->xFree(el
0870: 65 6d 29 3b 0a 20 20 20 20 65 6c 65 6d 20 3d 20  em);.    elem = 
0880: 6e 65 78 74 5f 65 6c 65 6d 3b 0a 20 20 7d 0a 20  next_elem;.  }. 
0890: 20 70 48 2d 3e 63 6f 75 6e 74 20 3d 20 30 3b 0a   pH->count = 0;.
08a0: 7d 0a 0a 23 69 66 20 30 20 2f 2a 20 4e 4f 54 20  }..#if 0 /* NOT 
08b0: 55 53 45 44 20 2a 2f 0a 2f 2a 0a 2a 2a 20 48 61  USED */./*.** Ha
08c0: 73 68 20 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f  sh and compariso
08d0: 6e 20 66 75 6e 63 74 69 6f 6e 73 20 77 68 65 6e  n functions when
08e0: 20 74 68 65 20 6d 6f 64 65 20 69 73 20 53 51 4c   the mode is SQL
08f0: 49 54 45 5f 48 41 53 48 5f 49 4e 54 0a 2a 2f 0a  ITE_HASH_INT.*/.
0900: 73 74 61 74 69 63 20 69 6e 74 20 69 6e 74 48 61  static int intHa
0910: 73 68 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70  sh(const void *p
0920: 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a  Key, int nKey){.
0930: 20 20 72 65 74 75 72 6e 20 6e 4b 65 79 20 5e 20    return nKey ^ 
0940: 28 6e 4b 65 79 3c 3c 38 29 20 5e 20 28 6e 4b 65  (nKey<<8) ^ (nKe
0950: 79 3e 3e 38 29 3b 0a 7d 0a 73 74 61 74 69 63 20  y>>8);.}.static 
0960: 69 6e 74 20 69 6e 74 43 6f 6d 70 61 72 65 28 63  int intCompare(c
0970: 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 31  onst void *pKey1
0980: 2c 20 69 6e 74 20 6e 31 2c 20 63 6f 6e 73 74 20  , int n1, const 
0990: 76 6f 69 64 20 2a 70 4b 65 79 32 2c 20 69 6e 74  void *pKey2, int
09a0: 20 6e 32 29 7b 0a 20 20 72 65 74 75 72 6e 20 6e   n2){.  return n
09b0: 32 20 2d 20 6e 31 3b 0a 7d 0a 23 65 6e 64 69 66  2 - n1;.}.#endif
09c0: 0a 0a 23 69 66 20 30 20 2f 2a 20 4e 4f 54 20 55  ..#if 0 /* NOT U
09d0: 53 45 44 20 2a 2f 0a 2f 2a 0a 2a 2a 20 48 61 73  SED */./*.** Has
09e0: 68 20 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e  h and comparison
09f0: 20 66 75 6e 63 74 69 6f 6e 73 20 77 68 65 6e 20   functions when 
0a00: 74 68 65 20 6d 6f 64 65 20 69 73 20 53 51 4c 49  the mode is SQLI
0a10: 54 45 5f 48 41 53 48 5f 50 4f 49 4e 54 45 52 0a  TE_HASH_POINTER.
0a20: 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 70 74  */.static int pt
0a30: 72 48 61 73 68 28 63 6f 6e 73 74 20 76 6f 69 64  rHash(const void
0a40: 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79   *pKey, int nKey
0a50: 29 7b 0a 20 20 75 70 74 72 20 78 20 3d 20 41 64  ){.  uptr x = Ad
0a60: 64 72 28 70 4b 65 79 29 3b 0a 20 20 72 65 74 75  dr(pKey);.  retu
0a70: 72 6e 20 78 20 5e 20 28 78 3c 3c 38 29 20 5e 20  rn x ^ (x<<8) ^ 
0a80: 28 78 3e 3e 38 29 3b 0a 7d 0a 73 74 61 74 69 63  (x>>8);.}.static
0a90: 20 69 6e 74 20 70 74 72 43 6f 6d 70 61 72 65 28   int ptrCompare(
0aa0: 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79  const void *pKey
0ab0: 31 2c 20 69 6e 74 20 6e 31 2c 20 63 6f 6e 73 74  1, int n1, const
0ac0: 20 76 6f 69 64 20 2a 70 4b 65 79 32 2c 20 69 6e   void *pKey2, in
0ad0: 74 20 6e 32 29 7b 0a 20 20 69 66 28 20 70 4b 65  t n2){.  if( pKe
0ae0: 79 31 3d 3d 70 4b 65 79 32 20 29 20 72 65 74 75  y1==pKey2 ) retu
0af0: 72 6e 20 30 3b 0a 20 20 69 66 28 20 70 4b 65 79  rn 0;.  if( pKey
0b00: 31 3c 70 4b 65 79 32 20 29 20 72 65 74 75 72 6e  1<pKey2 ) return
0b10: 20 2d 31 3b 0a 20 20 72 65 74 75 72 6e 20 31 3b   -1;.  return 1;
0b20: 0a 7d 0a 23 65 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a  .}.#endif../*.**
0b30: 20 48 61 73 68 20 61 6e 64 20 63 6f 6d 70 61 72   Hash and compar
0b40: 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 20 77  ison functions w
0b50: 68 65 6e 20 74 68 65 20 6d 6f 64 65 20 69 73 20  hen the mode is 
0b60: 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 49  SQLITE_HASH_STRI
0b70: 4e 47 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74  NG.*/.static int
0b80: 20 73 74 72 48 61 73 68 28 63 6f 6e 73 74 20 76   strHash(const v
0b90: 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e  oid *pKey, int n
0ba0: 4b 65 79 29 7b 0a 20 20 63 6f 6e 73 74 20 63 68  Key){.  const ch
0bb0: 61 72 20 2a 7a 20 3d 20 28 63 6f 6e 73 74 20 63  ar *z = (const c
0bc0: 68 61 72 20 2a 29 70 4b 65 79 3b 0a 20 20 69 6e  har *)pKey;.  in
0bd0: 74 20 68 20 3d 20 30 3b 0a 20 20 69 66 28 20 6e  t h = 0;.  if( n
0be0: 4b 65 79 3c 3d 30 20 29 20 6e 4b 65 79 20 3d 20  Key<=0 ) nKey = 
0bf0: 73 74 72 6c 65 6e 28 7a 29 3b 0a 20 20 77 68 69  strlen(z);.  whi
0c00: 6c 65 28 20 6e 4b 65 79 20 3e 20 30 20 20 29 7b  le( nKey > 0  ){
0c10: 0a 20 20 20 20 68 20 3d 20 28 68 3c 3c 33 29 20  .    h = (h<<3) 
0c20: 5e 20 68 20 5e 20 73 71 6c 69 74 65 33 55 70 70  ^ h ^ sqlite3Upp
0c30: 65 72 54 6f 4c 6f 77 65 72 5b 28 75 6e 73 69 67  erToLower[(unsig
0c40: 6e 65 64 20 63 68 61 72 29 2a 7a 2b 2b 5d 3b 0a  ned char)*z++];.
0c50: 20 20 20 20 6e 4b 65 79 2d 2d 3b 0a 20 20 7d 0a      nKey--;.  }.
0c60: 20 20 72 65 74 75 72 6e 20 68 20 26 20 30 78 37    return h & 0x7
0c70: 66 66 66 66 66 66 66 3b 0a 7d 0a 73 74 61 74 69  fffffff;.}.stati
0c80: 63 20 69 6e 74 20 73 74 72 43 6f 6d 70 61 72 65  c int strCompare
0c90: 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65  (const void *pKe
0ca0: 79 31 2c 20 69 6e 74 20 6e 31 2c 20 63 6f 6e 73  y1, int n1, cons
0cb0: 74 20 76 6f 69 64 20 2a 70 4b 65 79 32 2c 20 69  t void *pKey2, i
0cc0: 6e 74 20 6e 32 29 7b 0a 20 20 69 66 28 20 6e 31  nt n2){.  if( n1
0cd0: 21 3d 6e 32 20 29 20 72 65 74 75 72 6e 20 31 3b  !=n2 ) return 1;
0ce0: 0a 20 20 72 65 74 75 72 6e 20 73 71 6c 69 74 65  .  return sqlite
0cf0: 33 53 74 72 4e 49 43 6d 70 28 28 63 6f 6e 73 74  3StrNICmp((const
0d00: 20 63 68 61 72 2a 29 70 4b 65 79 31 2c 28 63 6f   char*)pKey1,(co
0d10: 6e 73 74 20 63 68 61 72 2a 29 70 4b 65 79 32 2c  nst char*)pKey2,
0d20: 6e 31 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 48 61  n1);.}../*.** Ha
0d30: 73 68 20 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f  sh and compariso
0d40: 6e 20 66 75 6e 63 74 69 6f 6e 73 20 77 68 65 6e  n functions when
0d50: 20 74 68 65 20 6d 6f 64 65 20 69 73 20 53 51 4c   the mode is SQL
0d60: 49 54 45 5f 48 41 53 48 5f 42 49 4e 41 52 59 0a  ITE_HASH_BINARY.
0d70: 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 62 69  */.static int bi
0d80: 6e 48 61 73 68 28 63 6f 6e 73 74 20 76 6f 69 64  nHash(const void
0d90: 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79   *pKey, int nKey
0da0: 29 7b 0a 20 20 69 6e 74 20 68 20 3d 20 30 3b 0a  ){.  int h = 0;.
0db0: 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a 20    const char *z 
0dc0: 3d 20 28 63 6f 6e 73 74 20 63 68 61 72 20 2a 29  = (const char *)
0dd0: 70 4b 65 79 3b 0a 20 20 77 68 69 6c 65 28 20 6e  pKey;.  while( n
0de0: 4b 65 79 2d 2d 20 3e 20 30 20 29 7b 0a 20 20 20  Key-- > 0 ){.   
0df0: 20 68 20 3d 20 28 68 3c 3c 33 29 20 5e 20 68 20   h = (h<<3) ^ h 
0e00: 5e 20 2a 28 7a 2b 2b 29 3b 0a 20 20 7d 0a 20 20  ^ *(z++);.  }.  
0e10: 72 65 74 75 72 6e 20 68 20 26 20 30 78 37 66 66  return h & 0x7ff
0e20: 66 66 66 66 66 3b 0a 7d 0a 73 74 61 74 69 63 20  fffff;.}.static 
0e30: 69 6e 74 20 62 69 6e 43 6f 6d 70 61 72 65 28 63  int binCompare(c
0e40: 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 31  onst void *pKey1
0e50: 2c 20 69 6e 74 20 6e 31 2c 20 63 6f 6e 73 74 20  , int n1, const 
0e60: 76 6f 69 64 20 2a 70 4b 65 79 32 2c 20 69 6e 74  void *pKey2, int
0e70: 20 6e 32 29 7b 0a 20 20 69 66 28 20 6e 31 21 3d   n2){.  if( n1!=
0e80: 6e 32 20 29 20 72 65 74 75 72 6e 20 31 3b 0a 20  n2 ) return 1;. 
0e90: 20 72 65 74 75 72 6e 20 6d 65 6d 63 6d 70 28 70   return memcmp(p
0ea0: 4b 65 79 31 2c 70 4b 65 79 32 2c 6e 31 29 3b 0a  Key1,pKey2,n1);.
0eb0: 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e 20  }../*.** Return 
0ec0: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65  a pointer to the
0ed0: 20 61 70 70 72 6f 70 72 69 61 74 65 20 68 61 73   appropriate has
0ee0: 68 20 66 75 6e 63 74 69 6f 6e 20 67 69 76 65 6e  h function given
0ef0: 20 74 68 65 20 6b 65 79 20 63 6c 61 73 73 2e 0a   the key class..
0f00: 2a 2a 0a 2a 2a 20 54 68 65 20 43 20 73 79 6e 74  **.** The C synt
0f10: 61 78 20 69 6e 20 74 68 69 73 20 66 75 6e 63 74  ax in this funct
0f20: 69 6f 6e 20 64 65 66 69 6e 69 74 69 6f 6e 20 6d  ion definition m
0f30: 61 79 20 62 65 20 75 6e 66 61 6d 69 6c 61 72 20  ay be unfamilar 
0f40: 74 6f 20 73 6f 6d 65 20 0a 2a 2a 20 70 72 6f 67  to some .** prog
0f50: 72 61 6d 6d 65 72 73 2c 20 73 6f 20 77 65 20 70  rammers, so we p
0f60: 72 6f 76 69 64 65 20 74 68 65 20 66 6f 6c 6c 6f  rovide the follo
0f70: 77 69 6e 67 20 61 64 64 69 74 69 6f 6e 61 6c 20  wing additional 
0f80: 65 78 70 6c 61 6e 61 74 69 6f 6e 3a 0a 2a 2a 0a  explanation:.**.
0f90: 2a 2a 20 54 68 65 20 6e 61 6d 65 20 6f 66 20 74  ** The name of t
0fa0: 68 65 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 22  he function is "
0fb0: 68 61 73 68 46 75 6e 63 74 69 6f 6e 22 2e 20 20  hashFunction".  
0fc0: 54 68 65 20 66 75 6e 63 74 69 6f 6e 20 74 61 6b  The function tak
0fd0: 65 73 20 61 0a 2a 2a 20 73 69 6e 67 6c 65 20 70  es a.** single p
0fe0: 61 72 61 6d 65 74 65 72 20 22 6b 65 79 43 6c 61  arameter "keyCla
0ff0: 73 73 22 2e 20 20 54 68 65 20 72 65 74 75 72 6e  ss".  The return
1000: 20 76 61 6c 75 65 20 6f 66 20 68 61 73 68 46 75   value of hashFu
1010: 6e 63 74 69 6f 6e 28 29 0a 2a 2a 20 69 73 20 61  nction().** is a
1020: 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 6e 6f 74   pointer to anot
1030: 68 65 72 20 66 75 6e 63 74 69 6f 6e 2e 20 20 53  her function.  S
1040: 70 65 63 69 66 69 63 61 6c 6c 79 2c 20 74 68 65  pecifically, the
1050: 20 72 65 74 75 72 6e 20 76 61 6c 75 65 0a 2a 2a   return value.**
1060: 20 6f 66 20 68 61 73 68 46 75 6e 63 74 69 6f 6e   of hashFunction
1070: 28 29 20 69 73 20 61 20 70 6f 69 6e 74 65 72 20  () is a pointer 
1080: 74 6f 20 61 20 66 75 6e 63 74 69 6f 6e 20 74 68  to a function th
1090: 61 74 20 74 61 6b 65 73 20 74 77 6f 20 70 61 72  at takes two par
10a0: 61 6d 65 74 65 72 73 0a 2a 2a 20 77 69 74 68 20  ameters.** with 
10b0: 74 79 70 65 73 20 22 63 6f 6e 73 74 20 76 6f 69  types "const voi
10c0: 64 2a 22 20 61 6e 64 20 22 69 6e 74 22 20 61 6e  d*" and "int" an
10d0: 64 20 72 65 74 75 72 6e 73 20 61 6e 20 22 69 6e  d returns an "in
10e0: 74 22 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e  t"..*/.static in
10f0: 74 20 28 2a 68 61 73 68 46 75 6e 63 74 69 6f 6e  t (*hashFunction
1100: 28 69 6e 74 20 6b 65 79 43 6c 61 73 73 29 29 28  (int keyClass))(
1110: 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29  const void*,int)
1120: 7b 0a 23 69 66 20 30 20 20 2f 2a 20 48 41 53 48  {.#if 0  /* HASH
1130: 5f 49 4e 54 20 61 6e 64 20 48 41 53 48 5f 50 4f  _INT and HASH_PO
1140: 49 4e 54 45 52 20 61 72 65 20 6e 65 76 65 72 20  INTER are never 
1150: 75 73 65 64 20 2a 2f 0a 20 20 73 77 69 74 63 68  used */.  switch
1160: 28 20 6b 65 79 43 6c 61 73 73 20 29 7b 0a 20 20  ( keyClass ){.  
1170: 20 20 63 61 73 65 20 53 51 4c 49 54 45 5f 48 41    case SQLITE_HA
1180: 53 48 5f 49 4e 54 3a 20 20 20 20 20 72 65 74 75  SH_INT:     retu
1190: 72 6e 20 26 69 6e 74 48 61 73 68 3b 0a 20 20 20  rn &intHash;.   
11a0: 20 63 61 73 65 20 53 51 4c 49 54 45 5f 48 41 53   case SQLITE_HAS
11b0: 48 5f 50 4f 49 4e 54 45 52 3a 20 72 65 74 75 72  H_POINTER: retur
11c0: 6e 20 26 70 74 72 48 61 73 68 3b 0a 20 20 20 20  n &ptrHash;.    
11d0: 63 61 73 65 20 53 51 4c 49 54 45 5f 48 41 53 48  case SQLITE_HASH
11e0: 5f 53 54 52 49 4e 47 3a 20 20 72 65 74 75 72 6e  _STRING:  return
11f0: 20 26 73 74 72 48 61 73 68 3b 0a 20 20 20 20 63   &strHash;.    c
1200: 61 73 65 20 53 51 4c 49 54 45 5f 48 41 53 48 5f  ase SQLITE_HASH_
1210: 42 49 4e 41 52 59 3a 20 20 72 65 74 75 72 6e 20  BINARY:  return 
1220: 26 62 69 6e 48 61 73 68 3b 3b 0a 20 20 20 20 64  &binHash;;.    d
1230: 65 66 61 75 6c 74 3a 20 62 72 65 61 6b 3b 0a 20  efault: break;. 
1240: 20 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a 23   }.  return 0;.#
1250: 65 6c 73 65 0a 20 20 69 66 28 20 6b 65 79 43 6c  else.  if( keyCl
1260: 61 73 73 3d 3d 53 51 4c 49 54 45 5f 48 41 53 48  ass==SQLITE_HASH
1270: 5f 53 54 52 49 4e 47 20 29 7b 0a 20 20 20 20 72  _STRING ){.    r
1280: 65 74 75 72 6e 20 26 73 74 72 48 61 73 68 3b 0a  eturn &strHash;.
1290: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 61 73 73    }else{.    ass
12a0: 65 72 74 28 20 6b 65 79 43 6c 61 73 73 3d 3d 53  ert( keyClass==S
12b0: 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e 41 52  QLITE_HASH_BINAR
12c0: 59 20 29 3b 0a 20 20 20 20 72 65 74 75 72 6e 20  Y );.    return 
12d0: 26 62 69 6e 48 61 73 68 3b 0a 20 20 7d 0a 23 65  &binHash;.  }.#e
12e0: 6e 64 69 66 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65  ndif.}../*.** Re
12f0: 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20 74  turn a pointer t
1300: 6f 20 74 68 65 20 61 70 70 72 6f 70 72 69 61 74  o the appropriat
1310: 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 20  e hash function 
1320: 67 69 76 65 6e 20 74 68 65 20 6b 65 79 20 63 6c  given the key cl
1330: 61 73 73 2e 0a 2a 2a 0a 2a 2a 20 46 6f 72 20 68  ass..**.** For h
1340: 65 6c 70 20 69 6e 20 69 6e 74 65 72 70 72 65 74  elp in interpret
1350: 65 64 20 74 68 65 20 6f 62 73 63 75 72 65 20 43  ed the obscure C
1360: 20 63 6f 64 65 20 69 6e 20 74 68 65 20 66 75 6e   code in the fun
1370: 63 74 69 6f 6e 20 64 65 66 69 6e 69 74 69 6f 6e  ction definition
1380: 2c 0a 2a 2a 20 73 65 65 20 74 68 65 20 68 65 61  ,.** see the hea
1390: 64 65 72 20 63 6f 6d 6d 65 6e 74 20 6f 6e 20 74  der comment on t
13a0: 68 65 20 70 72 65 76 69 6f 75 73 20 66 75 6e 63  he previous func
13b0: 74 69 6f 6e 2e 0a 2a 2f 0a 73 74 61 74 69 63 20  tion..*/.static 
13c0: 69 6e 74 20 28 2a 63 6f 6d 70 61 72 65 46 75 6e  int (*compareFun
13d0: 63 74 69 6f 6e 28 69 6e 74 20 6b 65 79 43 6c 61  ction(int keyCla
13e0: 73 73 29 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a  ss))(const void*
13f0: 2c 69 6e 74 2c 63 6f 6e 73 74 20 76 6f 69 64 2a  ,int,const void*
1400: 2c 69 6e 74 29 7b 0a 23 69 66 20 30 20 2f 2a 20  ,int){.#if 0 /* 
1410: 48 41 53 48 5f 49 4e 54 20 61 6e 64 20 48 41 53  HASH_INT and HAS
1420: 48 5f 50 4f 49 4e 54 45 52 20 61 72 65 20 6e 65  H_POINTER are ne
1430: 76 65 72 20 75 73 65 64 20 2a 2f 0a 20 20 73 77  ver used */.  sw
1440: 69 74 63 68 28 20 6b 65 79 43 6c 61 73 73 20 29  itch( keyClass )
1450: 7b 0a 20 20 20 20 63 61 73 65 20 53 51 4c 49 54  {.    case SQLIT
1460: 45 5f 48 41 53 48 5f 49 4e 54 3a 20 20 20 20 20  E_HASH_INT:     
1470: 72 65 74 75 72 6e 20 26 69 6e 74 43 6f 6d 70 61  return &intCompa
1480: 72 65 3b 0a 20 20 20 20 63 61 73 65 20 53 51 4c  re;.    case SQL
1490: 49 54 45 5f 48 41 53 48 5f 50 4f 49 4e 54 45 52  ITE_HASH_POINTER
14a0: 3a 20 72 65 74 75 72 6e 20 26 70 74 72 43 6f 6d  : return &ptrCom
14b0: 70 61 72 65 3b 0a 20 20 20 20 63 61 73 65 20 53  pare;.    case S
14c0: 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 49 4e  QLITE_HASH_STRIN
14d0: 47 3a 20 20 72 65 74 75 72 6e 20 26 73 74 72 43  G:  return &strC
14e0: 6f 6d 70 61 72 65 3b 0a 20 20 20 20 63 61 73 65  ompare;.    case
14f0: 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e   SQLITE_HASH_BIN
1500: 41 52 59 3a 20 20 72 65 74 75 72 6e 20 26 62 69  ARY:  return &bi
1510: 6e 43 6f 6d 70 61 72 65 3b 0a 20 20 20 20 64 65  nCompare;.    de
1520: 66 61 75 6c 74 3a 20 62 72 65 61 6b 3b 0a 20 20  fault: break;.  
1530: 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a 23 65  }.  return 0;.#e
1540: 6c 73 65 0a 20 20 69 66 28 20 6b 65 79 43 6c 61  lse.  if( keyCla
1550: 73 73 3d 3d 53 51 4c 49 54 45 5f 48 41 53 48 5f  ss==SQLITE_HASH_
1560: 53 54 52 49 4e 47 20 29 7b 0a 20 20 20 20 72 65  STRING ){.    re
1570: 74 75 72 6e 20 26 73 74 72 43 6f 6d 70 61 72 65  turn &strCompare
1580: 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 61  ;.  }else{.    a
1590: 73 73 65 72 74 28 20 6b 65 79 43 6c 61 73 73 3d  ssert( keyClass=
15a0: 3d 53 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e  =SQLITE_HASH_BIN
15b0: 41 52 59 20 29 3b 0a 20 20 20 20 72 65 74 75 72  ARY );.    retur
15c0: 6e 20 26 62 69 6e 43 6f 6d 70 61 72 65 3b 0a 20  n &binCompare;. 
15d0: 20 7d 0a 23 65 6e 64 69 66 0a 7d 0a 0a 2f 2a 20   }.#endif.}../* 
15e0: 4c 69 6e 6b 20 61 6e 20 65 6c 65 6d 65 6e 74 20  Link an element 
15f0: 69 6e 74 6f 20 74 68 65 20 68 61 73 68 20 74 61  into the hash ta
1600: 62 6c 65 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f  ble.*/.static vo
1610: 69 64 20 69 6e 73 65 72 74 45 6c 65 6d 65 6e 74  id insertElement
1620: 28 0a 20 20 48 61 73 68 20 2a 70 48 2c 20 20 20  (.  Hash *pH,   
1630: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68             /* Th
1640: 65 20 63 6f 6d 70 6c 65 74 65 20 68 61 73 68 20  e complete hash 
1650: 74 61 62 6c 65 20 2a 2f 0a 20 20 73 74 72 75 63  table */.  struc
1660: 74 20 5f 68 74 20 2a 70 45 6e 74 72 79 2c 20 20  t _ht *pEntry,  
1670: 20 20 2f 2a 20 54 68 65 20 65 6e 74 72 79 20 69    /* The entry i
1680: 6e 74 6f 20 77 68 69 63 68 20 70 4e 65 77 20 69  nto which pNew i
1690: 73 20 69 6e 73 65 72 74 65 64 20 2a 2f 0a 20 20  s inserted */.  
16a0: 48 61 73 68 45 6c 65 6d 20 2a 70 4e 65 77 20 20  HashElem *pNew  
16b0: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 65 6c         /* The el
16c0: 65 6d 65 6e 74 20 74 6f 20 62 65 20 69 6e 73 65  ement to be inse
16d0: 72 74 65 64 20 2a 2f 0a 29 7b 0a 20 20 48 61 73  rted */.){.  Has
16e0: 68 45 6c 65 6d 20 2a 70 48 65 61 64 3b 20 20 20  hElem *pHead;   
16f0: 20 20 20 20 2f 2a 20 46 69 72 73 74 20 65 6c 65      /* First ele
1700: 6d 65 6e 74 20 61 6c 72 65 61 64 79 20 69 6e 20  ment already in 
1710: 70 45 6e 74 72 79 20 2a 2f 0a 20 20 70 48 65 61  pEntry */.  pHea
1720: 64 20 3d 20 70 45 6e 74 72 79 2d 3e 63 68 61 69  d = pEntry->chai
1730: 6e 3b 0a 20 20 69 66 28 20 70 48 65 61 64 20 29  n;.  if( pHead )
1740: 7b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 65 78 74  {.    pNew->next
1750: 20 3d 20 70 48 65 61 64 3b 0a 20 20 20 20 70 4e   = pHead;.    pN
1760: 65 77 2d 3e 70 72 65 76 20 3d 20 70 48 65 61 64  ew->prev = pHead
1770: 2d 3e 70 72 65 76 3b 0a 20 20 20 20 69 66 28 20  ->prev;.    if( 
1780: 70 48 65 61 64 2d 3e 70 72 65 76 20 29 7b 20 70  pHead->prev ){ p
1790: 48 65 61 64 2d 3e 70 72 65 76 2d 3e 6e 65 78 74  Head->prev->next
17a0: 20 3d 20 70 4e 65 77 3b 20 7d 0a 20 20 20 20 65   = pNew; }.    e
17b0: 6c 73 65 20 20 20 20 20 20 20 20 20 20 20 20 20  lse             
17c0: 7b 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 70 4e  { pH->first = pN
17d0: 65 77 3b 20 7d 0a 20 20 20 20 70 48 65 61 64 2d  ew; }.    pHead-
17e0: 3e 70 72 65 76 20 3d 20 70 4e 65 77 3b 0a 20 20  >prev = pNew;.  
17f0: 7d 65 6c 73 65 7b 0a 20 20 20 20 70 4e 65 77 2d  }else{.    pNew-
1800: 3e 6e 65 78 74 20 3d 20 70 48 2d 3e 66 69 72 73  >next = pH->firs
1810: 74 3b 0a 20 20 20 20 69 66 28 20 70 48 2d 3e 66  t;.    if( pH->f
1820: 69 72 73 74 20 29 7b 20 70 48 2d 3e 66 69 72 73  irst ){ pH->firs
1830: 74 2d 3e 70 72 65 76 20 3d 20 70 4e 65 77 3b 20  t->prev = pNew; 
1840: 7d 0a 20 20 20 20 70 4e 65 77 2d 3e 70 72 65 76  }.    pNew->prev
1850: 20 3d 20 30 3b 0a 20 20 20 20 70 48 2d 3e 66 69   = 0;.    pH->fi
1860: 72 73 74 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 0a  rst = pNew;.  }.
1870: 20 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 2b    pEntry->count+
1880: 2b 3b 0a 20 20 70 45 6e 74 72 79 2d 3e 63 68 61  +;.  pEntry->cha
1890: 69 6e 20 3d 20 70 4e 65 77 3b 0a 7d 0a 0a 0a 2f  in = pNew;.}.../
18a0: 2a 20 52 65 73 69 7a 65 20 74 68 65 20 68 61 73  * Resize the has
18b0: 68 20 74 61 62 6c 65 20 73 6f 20 74 68 61 74 20  h table so that 
18c0: 69 74 20 63 61 6e 74 61 69 6e 73 20 22 6e 65 77  it cantains "new
18d0: 5f 73 69 7a 65 22 20 62 75 63 6b 65 74 73 2e 0a  _size" buckets..
18e0: 2a 2a 20 22 6e 65 77 5f 73 69 7a 65 22 20 6d 75  ** "new_size" mu
18f0: 73 74 20 62 65 20 61 20 70 6f 77 65 72 20 6f 66  st be a power of
1900: 20 32 2e 20 20 54 68 65 20 68 61 73 68 20 74 61   2.  The hash ta
1910: 62 6c 65 20 6d 69 67 68 74 20 66 61 69 6c 20 0a  ble might fail .
1920: 2a 2a 20 74 6f 20 72 65 73 69 7a 65 20 69 66 20  ** to resize if 
1930: 73 71 6c 69 74 65 4d 61 6c 6c 6f 63 28 29 20 66  sqliteMalloc() f
1940: 61 69 6c 73 2e 0a 2a 2f 0a 73 74 61 74 69 63 20  ails..*/.static 
1950: 76 6f 69 64 20 72 65 68 61 73 68 28 48 61 73 68  void rehash(Hash
1960: 20 2a 70 48 2c 20 69 6e 74 20 6e 65 77 5f 73 69   *pH, int new_si
1970: 7a 65 29 7b 0a 20 20 73 74 72 75 63 74 20 5f 68  ze){.  struct _h
1980: 74 20 2a 6e 65 77 5f 68 74 3b 20 20 20 20 20 20  t *new_ht;      
1990: 20 20 20 20 20 20 2f 2a 20 54 68 65 20 6e 65 77        /* The new
19a0: 20 68 61 73 68 20 74 61 62 6c 65 20 2a 2f 0a 20   hash table */. 
19b0: 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 2c   HashElem *elem,
19c0: 20 2a 6e 65 78 74 5f 65 6c 65 6d 3b 20 20 20 20   *next_elem;    
19d0: 2f 2a 20 46 6f 72 20 6c 6f 6f 70 69 6e 67 20 6f  /* For looping o
19e0: 76 65 72 20 65 78 69 73 74 69 6e 67 20 65 6c 65  ver existing ele
19f0: 6d 65 6e 74 73 20 2a 2f 0a 20 20 69 6e 74 20 28  ments */.  int (
1a00: 2a 78 48 61 73 68 29 28 63 6f 6e 73 74 20 76 6f  *xHash)(const vo
1a10: 69 64 2a 2c 69 6e 74 29 3b 20 2f 2a 20 54 68 65  id*,int); /* The
1a20: 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 2a   hash function *
1a30: 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 28 6e 65  /..  assert( (ne
1a40: 77 5f 73 69 7a 65 20 26 20 28 6e 65 77 5f 73 69  w_size & (new_si
1a50: 7a 65 2d 31 29 29 3d 3d 30 20 29 3b 0a 20 20 6e  ze-1))==0 );.  n
1a60: 65 77 5f 68 74 20 3d 20 28 73 74 72 75 63 74 20  ew_ht = (struct 
1a70: 5f 68 74 20 2a 29 70 48 2d 3e 78 4d 61 6c 6c 6f  _ht *)pH->xMallo
1a80: 63 28 20 6e 65 77 5f 73 69 7a 65 2a 73 69 7a 65  c( new_size*size
1a90: 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29 20 29  of(struct _ht) )
1aa0: 3b 0a 20 20 69 66 28 20 6e 65 77 5f 68 74 3d 3d  ;.  if( new_ht==
1ab0: 30 20 29 20 72 65 74 75 72 6e 3b 0a 20 20 69 66  0 ) return;.  if
1ac0: 28 20 70 48 2d 3e 68 74 20 29 20 70 48 2d 3e 78  ( pH->ht ) pH->x
1ad0: 46 72 65 65 28 70 48 2d 3e 68 74 29 3b 0a 20 20  Free(pH->ht);.  
1ae0: 70 48 2d 3e 68 74 20 3d 20 6e 65 77 5f 68 74 3b  pH->ht = new_ht;
1af0: 0a 20 20 70 48 2d 3e 68 74 73 69 7a 65 20 3d 20  .  pH->htsize = 
1b00: 6e 65 77 5f 73 69 7a 65 3b 0a 20 20 78 48 61 73  new_size;.  xHas
1b10: 68 20 3d 20 68 61 73 68 46 75 6e 63 74 69 6f 6e  h = hashFunction
1b20: 28 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a  (pH->keyClass);.
1b30: 20 20 66 6f 72 28 65 6c 65 6d 3d 70 48 2d 3e 66    for(elem=pH->f
1b40: 69 72 73 74 2c 20 70 48 2d 3e 66 69 72 73 74 3d  irst, pH->first=
1b50: 30 3b 20 65 6c 65 6d 3b 20 65 6c 65 6d 20 3d 20  0; elem; elem = 
1b60: 6e 65 78 74 5f 65 6c 65 6d 29 7b 0a 20 20 20 20  next_elem){.    
1b70: 69 6e 74 20 68 20 3d 20 28 2a 78 48 61 73 68 29  int h = (*xHash)
1b80: 28 65 6c 65 6d 2d 3e 70 4b 65 79 2c 20 65 6c 65  (elem->pKey, ele
1b90: 6d 2d 3e 6e 4b 65 79 29 20 26 20 28 6e 65 77 5f  m->nKey) & (new_
1ba0: 73 69 7a 65 2d 31 29 3b 0a 20 20 20 20 6e 65 78  size-1);.    nex
1bb0: 74 5f 65 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e 6e  t_elem = elem->n
1bc0: 65 78 74 3b 0a 20 20 20 20 69 6e 73 65 72 74 45  ext;.    insertE
1bd0: 6c 65 6d 65 6e 74 28 70 48 2c 20 26 6e 65 77 5f  lement(pH, &new_
1be0: 68 74 5b 68 5d 2c 20 65 6c 65 6d 29 3b 0a 20 20  ht[h], elem);.  
1bf0: 7d 0a 7d 0a 0a 2f 2a 20 54 68 69 73 20 66 75 6e  }.}../* This fun
1c00: 63 74 69 6f 6e 20 28 66 6f 72 20 69 6e 74 65 72  ction (for inter
1c10: 6e 61 6c 20 75 73 65 20 6f 6e 6c 79 29 20 6c 6f  nal use only) lo
1c20: 63 61 74 65 73 20 61 6e 20 65 6c 65 6d 65 6e 74  cates an element
1c30: 20 69 6e 20 61 6e 0a 2a 2a 20 68 61 73 68 20 74   in an.** hash t
1c40: 61 62 6c 65 20 74 68 61 74 20 6d 61 74 63 68 65  able that matche
1c50: 73 20 74 68 65 20 67 69 76 65 6e 20 6b 65 79 2e  s the given key.
1c60: 20 20 54 68 65 20 68 61 73 68 20 66 6f 72 20 74    The hash for t
1c70: 68 69 73 20 6b 65 79 20 68 61 73 0a 2a 2a 20 61  his key has.** a
1c80: 6c 72 65 61 64 79 20 62 65 65 6e 20 63 6f 6d 70  lready been comp
1c90: 75 74 65 64 20 61 6e 64 20 69 73 20 70 61 73 73  uted and is pass
1ca0: 65 64 20 61 73 20 74 68 65 20 34 74 68 20 70 61  ed as the 4th pa
1cb0: 72 61 6d 65 74 65 72 2e 0a 2a 2f 0a 73 74 61 74  rameter..*/.stat
1cc0: 69 63 20 48 61 73 68 45 6c 65 6d 20 2a 66 69 6e  ic HashElem *fin
1cd0: 64 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61 73  dElementGivenHas
1ce0: 68 28 0a 20 20 63 6f 6e 73 74 20 48 61 73 68 20  h(.  const Hash 
1cf0: 2a 70 48 2c 20 20 20 20 20 2f 2a 20 54 68 65 20  *pH,     /* The 
1d00: 70 48 20 74 6f 20 62 65 20 73 65 61 72 63 68 65  pH to be searche
1d10: 64 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 76 6f 69  d */.  const voi
1d20: 64 20 2a 70 4b 65 79 2c 20 20 20 2f 2a 20 54 68  d *pKey,   /* Th
1d30: 65 20 6b 65 79 20 77 65 20 61 72 65 20 73 65 61  e key we are sea
1d40: 72 63 68 69 6e 67 20 66 6f 72 20 2a 2f 0a 20 20  rching for */.  
1d50: 69 6e 74 20 6e 4b 65 79 2c 0a 20 20 69 6e 74 20  int nKey,.  int 
1d60: 68 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  h               
1d70: 2f 2a 20 54 68 65 20 68 61 73 68 20 66 6f 72 20  /* The hash for 
1d80: 74 68 69 73 20 6b 65 79 2e 20 2a 2f 0a 29 7b 0a  this key. */.){.
1d90: 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d    HashElem *elem
1da0: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
1db0: 20 2f 2a 20 55 73 65 64 20 74 6f 20 6c 6f 6f 70   /* Used to loop
1dc0: 20 74 68 72 75 20 74 68 65 20 65 6c 65 6d 65 6e   thru the elemen
1dd0: 74 20 6c 69 73 74 20 2a 2f 0a 20 20 69 6e 74 20  t list */.  int 
1de0: 63 6f 75 6e 74 3b 20 20 20 20 20 20 20 20 20 20  count;          
1df0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75             /* Nu
1e00: 6d 62 65 72 20 6f 66 20 65 6c 65 6d 65 6e 74 73  mber of elements
1e10: 20 6c 65 66 74 20 74 6f 20 74 65 73 74 20 2a 2f   left to test */
1e20: 0a 20 20 69 6e 74 20 28 2a 78 43 6f 6d 70 61 72  .  int (*xCompar
1e30: 65 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69  e)(const void*,i
1e40: 6e 74 2c 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69  nt,const void*,i
1e50: 6e 74 29 3b 20 20 2f 2a 20 63 6f 6d 70 61 72 69  nt);  /* compari
1e60: 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a  son function */.
1e70: 0a 20 20 69 66 28 20 70 48 2d 3e 68 74 20 29 7b  .  if( pH->ht ){
1e80: 0a 20 20 20 20 73 74 72 75 63 74 20 5f 68 74 20  .    struct _ht 
1e90: 2a 70 45 6e 74 72 79 20 3d 20 26 70 48 2d 3e 68  *pEntry = &pH->h
1ea0: 74 5b 68 5d 3b 0a 20 20 20 20 65 6c 65 6d 20 3d  t[h];.    elem =
1eb0: 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3b 0a   pEntry->chain;.
1ec0: 20 20 20 20 63 6f 75 6e 74 20 3d 20 70 45 6e 74      count = pEnt
1ed0: 72 79 2d 3e 63 6f 75 6e 74 3b 0a 20 20 20 20 78  ry->count;.    x
1ee0: 43 6f 6d 70 61 72 65 20 3d 20 63 6f 6d 70 61 72  Compare = compar
1ef0: 65 46 75 6e 63 74 69 6f 6e 28 70 48 2d 3e 6b 65  eFunction(pH->ke
1f00: 79 43 6c 61 73 73 29 3b 0a 20 20 20 20 77 68 69  yClass);.    whi
1f10: 6c 65 28 20 63 6f 75 6e 74 2d 2d 20 26 26 20 65  le( count-- && e
1f20: 6c 65 6d 20 29 7b 0a 20 20 20 20 20 20 69 66 28  lem ){.      if(
1f30: 20 28 2a 78 43 6f 6d 70 61 72 65 29 28 65 6c 65   (*xCompare)(ele
1f40: 6d 2d 3e 70 4b 65 79 2c 65 6c 65 6d 2d 3e 6e 4b  m->pKey,elem->nK
1f50: 65 79 2c 70 4b 65 79 2c 6e 4b 65 79 29 3d 3d 30  ey,pKey,nKey)==0
1f60: 20 29 7b 20 0a 20 20 20 20 20 20 20 20 72 65 74   ){ .        ret
1f70: 75 72 6e 20 65 6c 65 6d 3b 0a 20 20 20 20 20 20  urn elem;.      
1f80: 7d 0a 20 20 20 20 20 20 65 6c 65 6d 20 3d 20 65  }.      elem = e
1f90: 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 7d  lem->next;.    }
1fa0: 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b  .  }.  return 0;
1fb0: 0a 7d 0a 0a 2f 2a 20 52 65 6d 6f 76 65 20 61 20  .}../* Remove a 
1fc0: 73 69 6e 67 6c 65 20 65 6e 74 72 79 20 66 72 6f  single entry fro
1fd0: 6d 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65  m the hash table
1fe0: 20 67 69 76 65 6e 20 61 20 70 6f 69 6e 74 65 72   given a pointer
1ff0: 20 74 6f 20 74 68 61 74 0a 2a 2a 20 65 6c 65 6d   to that.** elem
2000: 65 6e 74 20 61 6e 64 20 61 20 68 61 73 68 20 6f  ent and a hash o
2010: 6e 20 74 68 65 20 65 6c 65 6d 65 6e 74 27 73 20  n the element's 
2020: 6b 65 79 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76  key..*/.static v
2030: 6f 69 64 20 72 65 6d 6f 76 65 45 6c 65 6d 65 6e  oid removeElemen
2040: 74 47 69 76 65 6e 48 61 73 68 28 0a 20 20 48 61  tGivenHash(.  Ha
2050: 73 68 20 2a 70 48 2c 20 20 20 20 20 20 20 20 20  sh *pH,         
2060: 2f 2a 20 54 68 65 20 70 48 20 63 6f 6e 74 61 69  /* The pH contai
2070: 6e 69 6e 67 20 22 65 6c 65 6d 22 20 2a 2f 0a 20  ning "elem" */. 
2080: 20 48 61 73 68 45 6c 65 6d 2a 20 65 6c 65 6d 2c   HashElem* elem,
2090: 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e     /* The elemen
20a0: 74 20 74 6f 20 62 65 20 72 65 6d 6f 76 65 64 20  t to be removed 
20b0: 66 72 6f 6d 20 74 68 65 20 70 48 20 2a 2f 0a 20  from the pH */. 
20c0: 20 69 6e 74 20 68 20 20 20 20 20 20 20 20 20 20   int h          
20d0: 20 20 20 2f 2a 20 48 61 73 68 20 76 61 6c 75 65     /* Hash value
20e0: 20 66 6f 72 20 74 68 65 20 65 6c 65 6d 65 6e 74   for the element
20f0: 20 2a 2f 0a 29 7b 0a 20 20 73 74 72 75 63 74 20   */.){.  struct 
2100: 5f 68 74 20 2a 70 45 6e 74 72 79 3b 0a 20 20 69  _ht *pEntry;.  i
2110: 66 28 20 65 6c 65 6d 2d 3e 70 72 65 76 20 29 7b  f( elem->prev ){
2120: 0a 20 20 20 20 65 6c 65 6d 2d 3e 70 72 65 76 2d  .    elem->prev-
2130: 3e 6e 65 78 74 20 3d 20 65 6c 65 6d 2d 3e 6e 65  >next = elem->ne
2140: 78 74 3b 20 0a 20 20 7d 65 6c 73 65 7b 0a 20 20  xt; .  }else{.  
2150: 20 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 65 6c    pH->first = el
2160: 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20 20  em->next;.  }.  
2170: 69 66 28 20 65 6c 65 6d 2d 3e 6e 65 78 74 20 29  if( elem->next )
2180: 7b 0a 20 20 20 20 65 6c 65 6d 2d 3e 6e 65 78 74  {.    elem->next
2190: 2d 3e 70 72 65 76 20 3d 20 65 6c 65 6d 2d 3e 70  ->prev = elem->p
21a0: 72 65 76 3b 0a 20 20 7d 0a 20 20 70 45 6e 74 72  rev;.  }.  pEntr
21b0: 79 20 3d 20 26 70 48 2d 3e 68 74 5b 68 5d 3b 0a  y = &pH->ht[h];.
21c0: 20 20 69 66 28 20 70 45 6e 74 72 79 2d 3e 63 68    if( pEntry->ch
21d0: 61 69 6e 3d 3d 65 6c 65 6d 20 29 7b 0a 20 20 20  ain==elem ){.   
21e0: 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 20 3d   pEntry->chain =
21f0: 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 7d   elem->next;.  }
2200: 0a 20 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74  .  pEntry->count
2210: 2d 2d 3b 0a 20 20 69 66 28 20 70 45 6e 74 72 79  --;.  if( pEntry
2220: 2d 3e 63 6f 75 6e 74 3c 3d 30 20 29 7b 0a 20 20  ->count<=0 ){.  
2230: 20 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 20    pEntry->chain 
2240: 3d 20 30 3b 0a 20 20 7d 0a 20 20 69 66 28 20 70  = 0;.  }.  if( p
2250: 48 2d 3e 63 6f 70 79 4b 65 79 20 26 26 20 65 6c  H->copyKey && el
2260: 65 6d 2d 3e 70 4b 65 79 20 29 7b 0a 20 20 20 20  em->pKey ){.    
2270: 70 48 2d 3e 78 46 72 65 65 28 65 6c 65 6d 2d 3e  pH->xFree(elem->
2280: 70 4b 65 79 29 3b 0a 20 20 7d 0a 20 20 70 48 2d  pKey);.  }.  pH-
2290: 3e 78 46 72 65 65 28 20 65 6c 65 6d 20 29 3b 0a  >xFree( elem );.
22a0: 20 20 70 48 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a 20    pH->count--;. 
22b0: 20 69 66 28 20 70 48 2d 3e 63 6f 75 6e 74 3c 3d   if( pH->count<=
22c0: 30 20 29 7b 0a 20 20 20 20 61 73 73 65 72 74 28  0 ){.    assert(
22d0: 20 70 48 2d 3e 66 69 72 73 74 3d 3d 30 20 29 3b   pH->first==0 );
22e0: 0a 20 20 20 20 61 73 73 65 72 74 28 20 70 48 2d  .    assert( pH-
22f0: 3e 63 6f 75 6e 74 3d 3d 30 20 29 3b 0a 20 20 20  >count==0 );.   
2300: 20 73 71 6c 69 74 65 33 48 61 73 68 43 6c 65 61   sqlite3HashClea
2310: 72 28 70 48 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a  r(pH);.  }.}../*
2320: 20 41 74 74 65 6d 70 74 20 74 6f 20 6c 6f 63 61   Attempt to loca
2330: 74 65 20 61 6e 20 65 6c 65 6d 65 6e 74 20 6f 66  te an element of
2340: 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20   the hash table 
2350: 70 48 20 77 69 74 68 20 61 20 6b 65 79 0a 2a 2a  pH with a key.**
2360: 20 74 68 61 74 20 6d 61 74 63 68 65 73 20 70 4b   that matches pK
2370: 65 79 2c 6e 4b 65 79 2e 20 20 52 65 74 75 72 6e  ey,nKey.  Return
2380: 20 74 68 65 20 64 61 74 61 20 66 6f 72 20 74 68   the data for th
2390: 69 73 20 65 6c 65 6d 65 6e 74 20 69 66 20 69 74  is element if it
23a0: 20 69 73 0a 2a 2a 20 66 6f 75 6e 64 2c 20 6f 72   is.** found, or
23b0: 20 4e 55 4c 4c 20 69 66 20 74 68 65 72 65 20 69   NULL if there i
23c0: 73 20 6e 6f 20 6d 61 74 63 68 2e 0a 2a 2f 0a 76  s no match..*/.v
23d0: 6f 69 64 20 2a 73 71 6c 69 74 65 33 48 61 73 68  oid *sqlite3Hash
23e0: 46 69 6e 64 28 63 6f 6e 73 74 20 48 61 73 68 20  Find(const Hash 
23f0: 2a 70 48 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20  *pH, const void 
2400: 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29  *pKey, int nKey)
2410: 7b 0a 20 20 69 6e 74 20 68 3b 20 20 20 20 20 20  {.  int h;      
2420: 20 20 20 20 20 20 20 2f 2a 20 41 20 68 61 73 68         /* A hash
2430: 20 6f 6e 20 6b 65 79 20 2a 2f 0a 20 20 48 61 73   on key */.  Has
2440: 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20  hElem *elem;    
2450: 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e 74 20 74  /* The element t
2460: 68 61 74 20 6d 61 74 63 68 65 73 20 6b 65 79 20  hat matches key 
2470: 2a 2f 0a 20 20 69 6e 74 20 28 2a 78 48 61 73 68  */.  int (*xHash
2480: 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e  )(const void*,in
2490: 74 29 3b 20 20 2f 2a 20 54 68 65 20 68 61 73 68  t);  /* The hash
24a0: 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20   function */..  
24b0: 69 66 28 20 70 48 3d 3d 30 20 7c 7c 20 70 48 2d  if( pH==0 || pH-
24c0: 3e 68 74 3d 3d 30 20 29 20 72 65 74 75 72 6e 20  >ht==0 ) return 
24d0: 30 3b 0a 20 20 78 48 61 73 68 20 3d 20 68 61 73  0;.  xHash = has
24e0: 68 46 75 6e 63 74 69 6f 6e 28 70 48 2d 3e 6b 65  hFunction(pH->ke
24f0: 79 43 6c 61 73 73 29 3b 0a 20 20 61 73 73 65 72  yClass);.  asser
2500: 74 28 20 78 48 61 73 68 21 3d 30 20 29 3b 0a 20  t( xHash!=0 );. 
2510: 20 68 20 3d 20 28 2a 78 48 61 73 68 29 28 70 4b   h = (*xHash)(pK
2520: 65 79 2c 6e 4b 65 79 29 3b 0a 20 20 61 73 73 65  ey,nKey);.  asse
2530: 72 74 28 20 28 70 48 2d 3e 68 74 73 69 7a 65 20  rt( (pH->htsize 
2540: 26 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29  & (pH->htsize-1)
2550: 29 3d 3d 30 20 29 3b 0a 20 20 65 6c 65 6d 20 3d  )==0 );.  elem =
2560: 20 66 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65   findElementGive
2570: 6e 48 61 73 68 28 70 48 2c 70 4b 65 79 2c 6e 4b  nHash(pH,pKey,nK
2580: 65 79 2c 20 68 20 26 20 28 70 48 2d 3e 68 74 73  ey, h & (pH->hts
2590: 69 7a 65 2d 31 29 29 3b 0a 20 20 72 65 74 75 72  ize-1));.  retur
25a0: 6e 20 65 6c 65 6d 20 3f 20 65 6c 65 6d 2d 3e 64  n elem ? elem->d
25b0: 61 74 61 20 3a 20 30 3b 0a 7d 0a 0a 2f 2a 20 49  ata : 0;.}../* I
25c0: 6e 73 65 72 74 20 61 6e 20 65 6c 65 6d 65 6e 74  nsert an element
25d0: 20 69 6e 74 6f 20 74 68 65 20 68 61 73 68 20 74   into the hash t
25e0: 61 62 6c 65 20 70 48 2e 20 20 54 68 65 20 6b 65  able pH.  The ke
25f0: 79 20 69 73 20 70 4b 65 79 2c 6e 4b 65 79 0a 2a  y is pKey,nKey.*
2600: 2a 20 61 6e 64 20 74 68 65 20 64 61 74 61 20 69  * and the data i
2610: 73 20 22 64 61 74 61 22 2e 0a 2a 2a 0a 2a 2a 20  s "data"..**.** 
2620: 49 66 20 6e 6f 20 65 6c 65 6d 65 6e 74 20 65 78  If no element ex
2630: 69 73 74 73 20 77 69 74 68 20 61 20 6d 61 74 63  ists with a matc
2640: 68 69 6e 67 20 6b 65 79 2c 20 74 68 65 6e 20 61  hing key, then a
2650: 20 6e 65 77 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20   new.** element 
2660: 69 73 20 63 72 65 61 74 65 64 2e 20 20 41 20 63  is created.  A c
2670: 6f 70 79 20 6f 66 20 74 68 65 20 6b 65 79 20 69  opy of the key i
2680: 73 20 6d 61 64 65 20 69 66 20 74 68 65 20 63 6f  s made if the co
2690: 70 79 4b 65 79 0a 2a 2a 20 66 6c 61 67 20 69 73  pyKey.** flag is
26a0: 20 73 65 74 2e 20 20 4e 55 4c 4c 20 69 73 20 72   set.  NULL is r
26b0: 65 74 75 72 6e 65 64 2e 0a 2a 2a 0a 2a 2a 20 49  eturned..**.** I
26c0: 66 20 61 6e 6f 74 68 65 72 20 65 6c 65 6d 65 6e  f another elemen
26d0: 74 20 61 6c 72 65 61 64 79 20 65 78 69 73 74 73  t already exists
26e0: 20 77 69 74 68 20 74 68 65 20 73 61 6d 65 20 6b   with the same k
26f0: 65 79 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20  ey, then the.** 
2700: 6e 65 77 20 64 61 74 61 20 72 65 70 6c 61 63 65  new data replace
2710: 73 20 74 68 65 20 6f 6c 64 20 64 61 74 61 20 61  s the old data a
2720: 6e 64 20 74 68 65 20 6f 6c 64 20 64 61 74 61 20  nd the old data 
2730: 69 73 20 72 65 74 75 72 6e 65 64 2e 0a 2a 2a 20  is returned..** 
2740: 54 68 65 20 6b 65 79 20 69 73 20 6e 6f 74 20 63  The key is not c
2750: 6f 70 69 65 64 20 69 6e 20 74 68 69 73 20 69 6e  opied in this in
2760: 73 74 61 6e 63 65 2e 20 20 49 66 20 61 20 6d 61  stance.  If a ma
2770: 6c 6c 6f 63 20 66 61 69 6c 73 2c 20 74 68 65 6e  lloc fails, then
2780: 0a 2a 2a 20 74 68 65 20 6e 65 77 20 64 61 74 61  .** the new data
2790: 20 69 73 20 72 65 74 75 72 6e 65 64 20 61 6e 64   is returned and
27a0: 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20   the hash table 
27b0: 69 73 20 75 6e 63 68 61 6e 67 65 64 2e 0a 2a 2a  is unchanged..**
27c0: 0a 2a 2a 20 49 66 20 74 68 65 20 22 64 61 74 61  .** If the "data
27d0: 22 20 70 61 72 61 6d 65 74 65 72 20 74 6f 20 74  " parameter to t
27e0: 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 69 73 20  his function is 
27f0: 4e 55 4c 4c 2c 20 74 68 65 6e 20 74 68 65 0a 2a  NULL, then the.*
2800: 2a 20 65 6c 65 6d 65 6e 74 20 63 6f 72 72 65 73  * element corres
2810: 70 6f 6e 64 69 6e 67 20 74 6f 20 22 6b 65 79 22  ponding to "key"
2820: 20 69 73 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d   is removed from
2830: 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 2e   the hash table.
2840: 0a 2a 2f 0a 76 6f 69 64 20 2a 73 71 6c 69 74 65  .*/.void *sqlite
2850: 33 48 61 73 68 49 6e 73 65 72 74 28 48 61 73 68  3HashInsert(Hash
2860: 20 2a 70 48 2c 20 63 6f 6e 73 74 20 76 6f 69 64   *pH, const void
2870: 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79   *pKey, int nKey
2880: 2c 20 76 6f 69 64 20 2a 64 61 74 61 29 7b 0a 20  , void *data){. 
2890: 20 69 6e 74 20 68 72 61 77 3b 20 20 20 20 20 20   int hraw;      
28a0: 20 20 20 20 20 20 20 2f 2a 20 52 61 77 20 68 61         /* Raw ha
28b0: 73 68 20 76 61 6c 75 65 20 6f 66 20 74 68 65 20  sh value of the 
28c0: 6b 65 79 20 2a 2f 0a 20 20 69 6e 74 20 68 3b 20  key */.  int h; 
28d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
28e0: 2a 20 74 68 65 20 68 61 73 68 20 6f 66 20 74 68  * the hash of th
28f0: 65 20 6b 65 79 20 6d 6f 64 75 6c 6f 20 68 61 73  e key modulo has
2900: 68 20 74 61 62 6c 65 20 73 69 7a 65 20 2a 2f 0a  h table size */.
2910: 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d    HashElem *elem
2920: 3b 20 20 20 20 20 20 20 2f 2a 20 55 73 65 64 20  ;       /* Used 
2930: 74 6f 20 6c 6f 6f 70 20 74 68 72 75 20 74 68 65  to loop thru the
2940: 20 65 6c 65 6d 65 6e 74 20 6c 69 73 74 20 2a 2f   element list */
2950: 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 6e 65 77  .  HashElem *new
2960: 5f 65 6c 65 6d 3b 20 20 20 2f 2a 20 4e 65 77 20  _elem;   /* New 
2970: 65 6c 65 6d 65 6e 74 20 61 64 64 65 64 20 74 6f  element added to
2980: 20 74 68 65 20 70 48 20 2a 2f 0a 20 20 69 6e 74   the pH */.  int
2990: 20 28 2a 78 48 61 73 68 29 28 63 6f 6e 73 74 20   (*xHash)(const 
29a0: 76 6f 69 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a 20  void*,int);  /* 
29b0: 54 68 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f  The hash functio
29c0: 6e 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20  n */..  assert( 
29d0: 70 48 21 3d 30 20 29 3b 0a 20 20 78 48 61 73 68  pH!=0 );.  xHash
29e0: 20 3d 20 68 61 73 68 46 75 6e 63 74 69 6f 6e 28   = hashFunction(
29f0: 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20  pH->keyClass);. 
2a00: 20 61 73 73 65 72 74 28 20 78 48 61 73 68 21 3d   assert( xHash!=
2a10: 30 20 29 3b 0a 20 20 68 72 61 77 20 3d 20 28 2a  0 );.  hraw = (*
2a20: 78 48 61 73 68 29 28 70 4b 65 79 2c 20 6e 4b 65  xHash)(pKey, nKe
2a30: 79 29 3b 0a 20 20 61 73 73 65 72 74 28 20 28 70  y);.  assert( (p
2a40: 48 2d 3e 68 74 73 69 7a 65 20 26 20 28 70 48 2d  H->htsize & (pH-
2a50: 3e 68 74 73 69 7a 65 2d 31 29 29 3d 3d 30 20 29  >htsize-1))==0 )
2a60: 3b 0a 20 20 68 20 3d 20 68 72 61 77 20 26 20 28  ;.  h = hraw & (
2a70: 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29 3b 0a 20  pH->htsize-1);. 
2a80: 20 65 6c 65 6d 20 3d 20 66 69 6e 64 45 6c 65 6d   elem = findElem
2a90: 65 6e 74 47 69 76 65 6e 48 61 73 68 28 70 48 2c  entGivenHash(pH,
2aa0: 70 4b 65 79 2c 6e 4b 65 79 2c 68 29 3b 0a 20 20  pKey,nKey,h);.  
2ab0: 69 66 28 20 65 6c 65 6d 20 29 7b 0a 20 20 20 20  if( elem ){.    
2ac0: 76 6f 69 64 20 2a 6f 6c 64 5f 64 61 74 61 20 3d  void *old_data =
2ad0: 20 65 6c 65 6d 2d 3e 64 61 74 61 3b 0a 20 20 20   elem->data;.   
2ae0: 20 69 66 28 20 64 61 74 61 3d 3d 30 20 29 7b 0a   if( data==0 ){.
2af0: 20 20 20 20 20 20 72 65 6d 6f 76 65 45 6c 65 6d        removeElem
2b00: 65 6e 74 47 69 76 65 6e 48 61 73 68 28 70 48 2c  entGivenHash(pH,
2b10: 65 6c 65 6d 2c 68 29 3b 0a 20 20 20 20 7d 65 6c  elem,h);.    }el
2b20: 73 65 7b 0a 20 20 20 20 20 20 65 6c 65 6d 2d 3e  se{.      elem->
2b30: 64 61 74 61 20 3d 20 64 61 74 61 3b 0a 20 20 20  data = data;.   
2b40: 20 7d 0a 20 20 20 20 72 65 74 75 72 6e 20 6f 6c   }.    return ol
2b50: 64 5f 64 61 74 61 3b 0a 20 20 7d 0a 20 20 69 66  d_data;.  }.  if
2b60: 28 20 64 61 74 61 3d 3d 30 20 29 20 72 65 74 75  ( data==0 ) retu
2b70: 72 6e 20 30 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d  rn 0;.  new_elem
2b80: 20 3d 20 28 48 61 73 68 45 6c 65 6d 2a 29 70 48   = (HashElem*)pH
2b90: 2d 3e 78 4d 61 6c 6c 6f 63 28 20 73 69 7a 65 6f  ->xMalloc( sizeo
2ba0: 66 28 48 61 73 68 45 6c 65 6d 29 20 29 3b 0a 20  f(HashElem) );. 
2bb0: 20 69 66 28 20 6e 65 77 5f 65 6c 65 6d 3d 3d 30   if( new_elem==0
2bc0: 20 29 20 72 65 74 75 72 6e 20 64 61 74 61 3b 0a   ) return data;.
2bd0: 20 20 69 66 28 20 70 48 2d 3e 63 6f 70 79 4b 65    if( pH->copyKe
2be0: 79 20 26 26 20 70 4b 65 79 21 3d 30 20 29 7b 0a  y && pKey!=0 ){.
2bf0: 20 20 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b      new_elem->pK
2c00: 65 79 20 3d 20 70 48 2d 3e 78 4d 61 6c 6c 6f 63  ey = pH->xMalloc
2c10: 28 20 6e 4b 65 79 20 29 3b 0a 20 20 20 20 69 66  ( nKey );.    if
2c20: 28 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79  ( new_elem->pKey
2c30: 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 70 48 2d  ==0 ){.      pH-
2c40: 3e 78 46 72 65 65 28 6e 65 77 5f 65 6c 65 6d 29  >xFree(new_elem)
2c50: 3b 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 64  ;.      return d
2c60: 61 74 61 3b 0a 20 20 20 20 7d 0a 20 20 20 20 6d  ata;.    }.    m
2c70: 65 6d 63 70 79 28 28 76 6f 69 64 2a 29 6e 65 77  emcpy((void*)new
2c80: 5f 65 6c 65 6d 2d 3e 70 4b 65 79 2c 20 70 4b 65  _elem->pKey, pKe
2c90: 79 2c 20 6e 4b 65 79 29 3b 0a 20 20 7d 65 6c 73  y, nKey);.  }els
2ca0: 65 7b 0a 20 20 20 20 6e 65 77 5f 65 6c 65 6d 2d  e{.    new_elem-
2cb0: 3e 70 4b 65 79 20 3d 20 28 76 6f 69 64 2a 29 70  >pKey = (void*)p
2cc0: 4b 65 79 3b 0a 20 20 7d 0a 20 20 6e 65 77 5f 65  Key;.  }.  new_e
2cd0: 6c 65 6d 2d 3e 6e 4b 65 79 20 3d 20 6e 4b 65 79  lem->nKey = nKey
2ce0: 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 2b 2b 3b  ;.  pH->count++;
2cf0: 0a 20 20 69 66 28 20 70 48 2d 3e 68 74 73 69 7a  .  if( pH->htsiz
2d00: 65 3d 3d 30 20 29 7b 0a 20 20 20 20 72 65 68 61  e==0 ){.    reha
2d10: 73 68 28 70 48 2c 38 29 3b 0a 20 20 20 20 69 66  sh(pH,8);.    if
2d20: 28 20 70 48 2d 3e 68 74 73 69 7a 65 3d 3d 30 20  ( pH->htsize==0 
2d30: 29 7b 0a 20 20 20 20 20 20 70 48 2d 3e 63 6f 75  ){.      pH->cou
2d40: 6e 74 20 3d 20 30 3b 0a 20 20 20 20 20 20 70 48  nt = 0;.      pH
2d50: 2d 3e 78 46 72 65 65 28 6e 65 77 5f 65 6c 65 6d  ->xFree(new_elem
2d60: 29 3b 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20  );.      return 
2d70: 64 61 74 61 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a  data;.    }.  }.
2d80: 20 20 69 66 28 20 70 48 2d 3e 63 6f 75 6e 74 20    if( pH->count 
2d90: 3e 20 70 48 2d 3e 68 74 73 69 7a 65 20 29 7b 0a  > pH->htsize ){.
2da0: 20 20 20 20 72 65 68 61 73 68 28 70 48 2c 70 48      rehash(pH,pH
2db0: 2d 3e 68 74 73 69 7a 65 2a 32 29 3b 0a 20 20 7d  ->htsize*2);.  }
2dc0: 0a 20 20 61 73 73 65 72 74 28 20 70 48 2d 3e 68  .  assert( pH->h
2dd0: 74 73 69 7a 65 3e 30 20 29 3b 0a 20 20 61 73 73  tsize>0 );.  ass
2de0: 65 72 74 28 20 28 70 48 2d 3e 68 74 73 69 7a 65  ert( (pH->htsize
2df0: 20 26 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31   & (pH->htsize-1
2e00: 29 29 3d 3d 30 20 29 3b 0a 20 20 68 20 3d 20 68  ))==0 );.  h = h
2e10: 72 61 77 20 26 20 28 70 48 2d 3e 68 74 73 69 7a  raw & (pH->htsiz
2e20: 65 2d 31 29 3b 0a 20 20 69 6e 73 65 72 74 45 6c  e-1);.  insertEl
2e30: 65 6d 65 6e 74 28 70 48 2c 20 26 70 48 2d 3e 68  ement(pH, &pH->h
2e40: 74 5b 68 5d 2c 20 6e 65 77 5f 65 6c 65 6d 29 3b  t[h], new_elem);
2e50: 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 64 61 74  .  new_elem->dat
2e60: 61 20 3d 20 64 61 74 61 3b 0a 20 20 72 65 74 75  a = data;.  retu
2e70: 72 6e 20 30 3b 0a 7d 0a                          rn 0;.}.