/ Hex Artifact Content
Login

Artifact eb64e48f3781100e5934f759fbe72a63a8fe78cb:


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 33 30 20 32 30 30 38 2f 30 36 2f  ,v 1.30 2008/06/
01e0: 32 30 20 31 34 3a 35 39 3a 35 31 20 64 61 6e 69  20 14:59:51 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 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70 48   sqlite3_free(pH
0770: 2d 3e 68 74 29 3b 0a 20 20 70 48 2d 3e 68 74 20  ->ht);.  pH->ht 
0780: 3d 20 30 3b 0a 20 20 70 48 2d 3e 68 74 73 69 7a  = 0;.  pH->htsiz
0790: 65 20 3d 20 30 3b 0a 20 20 77 68 69 6c 65 28 20  e = 0;.  while( 
07a0: 65 6c 65 6d 20 29 7b 0a 20 20 20 20 48 61 73 68  elem ){.    Hash
07b0: 45 6c 65 6d 20 2a 6e 65 78 74 5f 65 6c 65 6d 20  Elem *next_elem 
07c0: 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20  = elem->next;.  
07d0: 20 20 69 66 28 20 70 48 2d 3e 63 6f 70 79 4b 65    if( pH->copyKe
07e0: 79 20 26 26 20 65 6c 65 6d 2d 3e 70 4b 65 79 20  y && elem->pKey 
07f0: 29 7b 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33  ){.      sqlite3
0800: 5f 66 72 65 65 28 65 6c 65 6d 2d 3e 70 4b 65 79  _free(elem->pKey
0810: 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 73 71 6c  );.    }.    sql
0820: 69 74 65 33 5f 66 72 65 65 28 65 6c 65 6d 29 3b  ite3_free(elem);
0830: 0a 20 20 20 20 65 6c 65 6d 20 3d 20 6e 65 78 74  .    elem = next
0840: 5f 65 6c 65 6d 3b 0a 20 20 7d 0a 20 20 70 48 2d  _elem;.  }.  pH-
0850: 3e 63 6f 75 6e 74 20 3d 20 30 3b 0a 7d 0a 0a 23  >count = 0;.}..#
0860: 69 66 20 30 20 2f 2a 20 4e 4f 54 20 55 53 45 44  if 0 /* NOT USED
0870: 20 2a 2f 0a 2f 2a 0a 2a 2a 20 48 61 73 68 20 61   */./*.** Hash a
0880: 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75  nd comparison fu
0890: 6e 63 74 69 6f 6e 73 20 77 68 65 6e 20 74 68 65  nctions when the
08a0: 20 6d 6f 64 65 20 69 73 20 53 51 4c 49 54 45 5f   mode is SQLITE_
08b0: 48 41 53 48 5f 49 4e 54 0a 2a 2f 0a 73 74 61 74  HASH_INT.*/.stat
08c0: 69 63 20 69 6e 74 20 69 6e 74 48 61 73 68 28 63  ic int intHash(c
08d0: 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c  onst void *pKey,
08e0: 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 72 65   int nKey){.  re
08f0: 74 75 72 6e 20 6e 4b 65 79 20 5e 20 28 6e 4b 65  turn nKey ^ (nKe
0900: 79 3c 3c 38 29 20 5e 20 28 6e 4b 65 79 3e 3e 38  y<<8) ^ (nKey>>8
0910: 29 3b 0a 7d 0a 73 74 61 74 69 63 20 69 6e 74 20  );.}.static int 
0920: 69 6e 74 43 6f 6d 70 61 72 65 28 63 6f 6e 73 74  intCompare(const
0930: 20 76 6f 69 64 20 2a 70 4b 65 79 31 2c 20 69 6e   void *pKey1, in
0940: 74 20 6e 31 2c 20 63 6f 6e 73 74 20 76 6f 69 64  t n1, const void
0950: 20 2a 70 4b 65 79 32 2c 20 69 6e 74 20 6e 32 29   *pKey2, int n2)
0960: 7b 0a 20 20 72 65 74 75 72 6e 20 6e 32 20 2d 20  {.  return n2 - 
0970: 6e 31 3b 0a 7d 0a 23 65 6e 64 69 66 0a 0a 23 69  n1;.}.#endif..#i
0980: 66 20 30 20 2f 2a 20 4e 4f 54 20 55 53 45 44 20  f 0 /* NOT USED 
0990: 2a 2f 0a 2f 2a 0a 2a 2a 20 48 61 73 68 20 61 6e  */./*.** Hash an
09a0: 64 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75 6e  d comparison fun
09b0: 63 74 69 6f 6e 73 20 77 68 65 6e 20 74 68 65 20  ctions when the 
09c0: 6d 6f 64 65 20 69 73 20 53 51 4c 49 54 45 5f 48  mode is SQLITE_H
09d0: 41 53 48 5f 50 4f 49 4e 54 45 52 0a 2a 2f 0a 73  ASH_POINTER.*/.s
09e0: 74 61 74 69 63 20 69 6e 74 20 70 74 72 48 61 73  tatic int ptrHas
09f0: 68 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b  h(const void *pK
0a00: 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20  ey, int nKey){. 
0a10: 20 75 70 74 72 20 78 20 3d 20 41 64 64 72 28 70   uptr x = Addr(p
0a20: 4b 65 79 29 3b 0a 20 20 72 65 74 75 72 6e 20 78  Key);.  return x
0a30: 20 5e 20 28 78 3c 3c 38 29 20 5e 20 28 78 3e 3e   ^ (x<<8) ^ (x>>
0a40: 38 29 3b 0a 7d 0a 73 74 61 74 69 63 20 69 6e 74  8);.}.static int
0a50: 20 70 74 72 43 6f 6d 70 61 72 65 28 63 6f 6e 73   ptrCompare(cons
0a60: 74 20 76 6f 69 64 20 2a 70 4b 65 79 31 2c 20 69  t void *pKey1, i
0a70: 6e 74 20 6e 31 2c 20 63 6f 6e 73 74 20 76 6f 69  nt n1, const voi
0a80: 64 20 2a 70 4b 65 79 32 2c 20 69 6e 74 20 6e 32  d *pKey2, int n2
0a90: 29 7b 0a 20 20 69 66 28 20 70 4b 65 79 31 3d 3d  ){.  if( pKey1==
0aa0: 70 4b 65 79 32 20 29 20 72 65 74 75 72 6e 20 30  pKey2 ) return 0
0ab0: 3b 0a 20 20 69 66 28 20 70 4b 65 79 31 3c 70 4b  ;.  if( pKey1<pK
0ac0: 65 79 32 20 29 20 72 65 74 75 72 6e 20 2d 31 3b  ey2 ) return -1;
0ad0: 0a 20 20 72 65 74 75 72 6e 20 31 3b 0a 7d 0a 23  .  return 1;.}.#
0ae0: 65 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a 20 48 61 73  endif../*.** Has
0af0: 68 20 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e  h and comparison
0b00: 20 66 75 6e 63 74 69 6f 6e 73 20 77 68 65 6e 20   functions when 
0b10: 74 68 65 20 6d 6f 64 65 20 69 73 20 53 51 4c 49  the mode is SQLI
0b20: 54 45 5f 48 41 53 48 5f 53 54 52 49 4e 47 0a 2a  TE_HASH_STRING.*
0b30: 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 73 74 72  /.static int str
0b40: 48 61 73 68 28 63 6f 6e 73 74 20 76 6f 69 64 20  Hash(const void 
0b50: 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29  *pKey, int nKey)
0b60: 7b 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a  {.  const char *
0b70: 7a 20 3d 20 28 63 6f 6e 73 74 20 63 68 61 72 20  z = (const char 
0b80: 2a 29 70 4b 65 79 3b 0a 20 20 69 6e 74 20 68 20  *)pKey;.  int h 
0b90: 3d 20 30 3b 0a 20 20 69 66 28 20 6e 4b 65 79 3c  = 0;.  if( nKey<
0ba0: 3d 30 20 29 20 6e 4b 65 79 20 3d 20 73 74 72 6c  =0 ) nKey = strl
0bb0: 65 6e 28 7a 29 3b 0a 20 20 77 68 69 6c 65 28 20  en(z);.  while( 
0bc0: 6e 4b 65 79 20 3e 20 30 20 20 29 7b 0a 20 20 20  nKey > 0  ){.   
0bd0: 20 68 20 3d 20 28 68 3c 3c 33 29 20 5e 20 68 20   h = (h<<3) ^ h 
0be0: 5e 20 73 71 6c 69 74 65 33 55 70 70 65 72 54 6f  ^ sqlite3UpperTo
0bf0: 4c 6f 77 65 72 5b 28 75 6e 73 69 67 6e 65 64 20  Lower[(unsigned 
0c00: 63 68 61 72 29 2a 7a 2b 2b 5d 3b 0a 20 20 20 20  char)*z++];.    
0c10: 6e 4b 65 79 2d 2d 3b 0a 20 20 7d 0a 20 20 72 65  nKey--;.  }.  re
0c20: 74 75 72 6e 20 68 20 26 20 30 78 37 66 66 66 66  turn h & 0x7ffff
0c30: 66 66 66 3b 0a 7d 0a 73 74 61 74 69 63 20 69 6e  fff;.}.static in
0c40: 74 20 73 74 72 43 6f 6d 70 61 72 65 28 63 6f 6e  t strCompare(con
0c50: 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 31 2c 20  st void *pKey1, 
0c60: 69 6e 74 20 6e 31 2c 20 63 6f 6e 73 74 20 76 6f  int n1, const vo
0c70: 69 64 20 2a 70 4b 65 79 32 2c 20 69 6e 74 20 6e  id *pKey2, int n
0c80: 32 29 7b 0a 20 20 69 66 28 20 6e 31 21 3d 6e 32  2){.  if( n1!=n2
0c90: 20 29 20 72 65 74 75 72 6e 20 31 3b 0a 20 20 72   ) return 1;.  r
0ca0: 65 74 75 72 6e 20 73 71 6c 69 74 65 33 53 74 72  eturn sqlite3Str
0cb0: 4e 49 43 6d 70 28 28 63 6f 6e 73 74 20 63 68 61  NICmp((const cha
0cc0: 72 2a 29 70 4b 65 79 31 2c 28 63 6f 6e 73 74 20  r*)pKey1,(const 
0cd0: 63 68 61 72 2a 29 70 4b 65 79 32 2c 6e 31 29 3b  char*)pKey2,n1);
0ce0: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 48 61 73 68 20 61  .}../*.** Hash a
0cf0: 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75  nd comparison fu
0d00: 6e 63 74 69 6f 6e 73 20 77 68 65 6e 20 74 68 65  nctions when the
0d10: 20 6d 6f 64 65 20 69 73 20 53 51 4c 49 54 45 5f   mode is SQLITE_
0d20: 48 41 53 48 5f 42 49 4e 41 52 59 0a 2a 2f 0a 73  HASH_BINARY.*/.s
0d30: 74 61 74 69 63 20 69 6e 74 20 62 69 6e 48 61 73  tatic int binHas
0d40: 68 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b  h(const void *pK
0d50: 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20  ey, int nKey){. 
0d60: 20 69 6e 74 20 68 20 3d 20 30 3b 0a 20 20 63 6f   int h = 0;.  co
0d70: 6e 73 74 20 63 68 61 72 20 2a 7a 20 3d 20 28 63  nst char *z = (c
0d80: 6f 6e 73 74 20 63 68 61 72 20 2a 29 70 4b 65 79  onst char *)pKey
0d90: 3b 0a 20 20 77 68 69 6c 65 28 20 6e 4b 65 79 2d  ;.  while( nKey-
0da0: 2d 20 3e 20 30 20 29 7b 0a 20 20 20 20 68 20 3d  - > 0 ){.    h =
0db0: 20 28 68 3c 3c 33 29 20 5e 20 68 20 5e 20 2a 28   (h<<3) ^ h ^ *(
0dc0: 7a 2b 2b 29 3b 0a 20 20 7d 0a 20 20 72 65 74 75  z++);.  }.  retu
0dd0: 72 6e 20 68 20 26 20 30 78 37 66 66 66 66 66 66  rn h & 0x7ffffff
0de0: 66 3b 0a 7d 0a 73 74 61 74 69 63 20 69 6e 74 20  f;.}.static int 
0df0: 62 69 6e 43 6f 6d 70 61 72 65 28 63 6f 6e 73 74  binCompare(const
0e00: 20 76 6f 69 64 20 2a 70 4b 65 79 31 2c 20 69 6e   void *pKey1, in
0e10: 74 20 6e 31 2c 20 63 6f 6e 73 74 20 76 6f 69 64  t n1, const void
0e20: 20 2a 70 4b 65 79 32 2c 20 69 6e 74 20 6e 32 29   *pKey2, int n2)
0e30: 7b 0a 20 20 69 66 28 20 6e 31 21 3d 6e 32 20 29  {.  if( n1!=n2 )
0e40: 20 72 65 74 75 72 6e 20 31 3b 0a 20 20 72 65 74   return 1;.  ret
0e50: 75 72 6e 20 6d 65 6d 63 6d 70 28 70 4b 65 79 31  urn memcmp(pKey1
0e60: 2c 70 4b 65 79 32 2c 6e 31 29 3b 0a 7d 0a 0a 2f  ,pKey2,n1);.}../
0e70: 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 61 20 70 6f  *.** Return a po
0e80: 69 6e 74 65 72 20 74 6f 20 74 68 65 20 61 70 70  inter to the app
0e90: 72 6f 70 72 69 61 74 65 20 68 61 73 68 20 66 75  ropriate hash fu
0ea0: 6e 63 74 69 6f 6e 20 67 69 76 65 6e 20 74 68 65  nction given the
0eb0: 20 6b 65 79 20 63 6c 61 73 73 2e 0a 2a 2a 0a 2a   key class..**.*
0ec0: 2a 20 54 68 65 20 43 20 73 79 6e 74 61 78 20 69  * The C syntax i
0ed0: 6e 20 74 68 69 73 20 66 75 6e 63 74 69 6f 6e 20  n this function 
0ee0: 64 65 66 69 6e 69 74 69 6f 6e 20 6d 61 79 20 62  definition may b
0ef0: 65 20 75 6e 66 61 6d 69 6c 61 72 20 74 6f 20 73  e unfamilar to s
0f00: 6f 6d 65 20 0a 2a 2a 20 70 72 6f 67 72 61 6d 6d  ome .** programm
0f10: 65 72 73 2c 20 73 6f 20 77 65 20 70 72 6f 76 69  ers, so we provi
0f20: 64 65 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67  de the following
0f30: 20 61 64 64 69 74 69 6f 6e 61 6c 20 65 78 70 6c   additional expl
0f40: 61 6e 61 74 69 6f 6e 3a 0a 2a 2a 0a 2a 2a 20 54  anation:.**.** T
0f50: 68 65 20 6e 61 6d 65 20 6f 66 20 74 68 65 20 66  he name of the f
0f60: 75 6e 63 74 69 6f 6e 20 69 73 20 22 68 61 73 68  unction is "hash
0f70: 46 75 6e 63 74 69 6f 6e 22 2e 20 20 54 68 65 20  Function".  The 
0f80: 66 75 6e 63 74 69 6f 6e 20 74 61 6b 65 73 20 61  function takes a
0f90: 0a 2a 2a 20 73 69 6e 67 6c 65 20 70 61 72 61 6d  .** single param
0fa0: 65 74 65 72 20 22 6b 65 79 43 6c 61 73 73 22 2e  eter "keyClass".
0fb0: 20 20 54 68 65 20 72 65 74 75 72 6e 20 76 61 6c    The return val
0fc0: 75 65 20 6f 66 20 68 61 73 68 46 75 6e 63 74 69  ue of hashFuncti
0fd0: 6f 6e 28 29 0a 2a 2a 20 69 73 20 61 20 70 6f 69  on().** is a poi
0fe0: 6e 74 65 72 20 74 6f 20 61 6e 6f 74 68 65 72 20  nter to another 
0ff0: 66 75 6e 63 74 69 6f 6e 2e 20 20 53 70 65 63 69  function.  Speci
1000: 66 69 63 61 6c 6c 79 2c 20 74 68 65 20 72 65 74  fically, the ret
1010: 75 72 6e 20 76 61 6c 75 65 0a 2a 2a 20 6f 66 20  urn value.** of 
1020: 68 61 73 68 46 75 6e 63 74 69 6f 6e 28 29 20 69  hashFunction() i
1030: 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 61  s a pointer to a
1040: 20 66 75 6e 63 74 69 6f 6e 20 74 68 61 74 20 74   function that t
1050: 61 6b 65 73 20 74 77 6f 20 70 61 72 61 6d 65 74  akes two paramet
1060: 65 72 73 0a 2a 2a 20 77 69 74 68 20 74 79 70 65  ers.** with type
1070: 73 20 22 63 6f 6e 73 74 20 76 6f 69 64 2a 22 20  s "const void*" 
1080: 61 6e 64 20 22 69 6e 74 22 20 61 6e 64 20 72 65  and "int" and re
1090: 74 75 72 6e 73 20 61 6e 20 22 69 6e 74 22 2e 0a  turns an "int"..
10a0: 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 28 2a  */.static int (*
10b0: 68 61 73 68 46 75 6e 63 74 69 6f 6e 28 69 6e 74  hashFunction(int
10c0: 20 6b 65 79 43 6c 61 73 73 29 29 28 63 6f 6e 73   keyClass))(cons
10d0: 74 20 76 6f 69 64 2a 2c 69 6e 74 29 7b 0a 23 69  t void*,int){.#i
10e0: 66 20 30 20 20 2f 2a 20 48 41 53 48 5f 49 4e 54  f 0  /* HASH_INT
10f0: 20 61 6e 64 20 48 41 53 48 5f 50 4f 49 4e 54 45   and HASH_POINTE
1100: 52 20 61 72 65 20 6e 65 76 65 72 20 75 73 65 64  R are never used
1110: 20 2a 2f 0a 20 20 73 77 69 74 63 68 28 20 6b 65   */.  switch( ke
1120: 79 43 6c 61 73 73 20 29 7b 0a 20 20 20 20 63 61  yClass ){.    ca
1130: 73 65 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 49  se SQLITE_HASH_I
1140: 4e 54 3a 20 20 20 20 20 72 65 74 75 72 6e 20 26  NT:     return &
1150: 69 6e 74 48 61 73 68 3b 0a 20 20 20 20 63 61 73  intHash;.    cas
1160: 65 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 50 4f  e SQLITE_HASH_PO
1170: 49 4e 54 45 52 3a 20 72 65 74 75 72 6e 20 26 70  INTER: return &p
1180: 74 72 48 61 73 68 3b 0a 20 20 20 20 63 61 73 65  trHash;.    case
1190: 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52   SQLITE_HASH_STR
11a0: 49 4e 47 3a 20 20 72 65 74 75 72 6e 20 26 73 74  ING:  return &st
11b0: 72 48 61 73 68 3b 0a 20 20 20 20 63 61 73 65 20  rHash;.    case 
11c0: 53 51 4c 49 54 45 5f 48 41 53 48 5f 42 49 4e 41  SQLITE_HASH_BINA
11d0: 52 59 3a 20 20 72 65 74 75 72 6e 20 26 62 69 6e  RY:  return &bin
11e0: 48 61 73 68 3b 3b 0a 20 20 20 20 64 65 66 61 75  Hash;;.    defau
11f0: 6c 74 3a 20 62 72 65 61 6b 3b 0a 20 20 7d 0a 20  lt: break;.  }. 
1200: 20 72 65 74 75 72 6e 20 30 3b 0a 23 65 6c 73 65   return 0;.#else
1210: 0a 20 20 69 66 28 20 6b 65 79 43 6c 61 73 73 3d  .  if( keyClass=
1220: 3d 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52  =SQLITE_HASH_STR
1230: 49 4e 47 20 29 7b 0a 20 20 20 20 72 65 74 75 72  ING ){.    retur
1240: 6e 20 26 73 74 72 48 61 73 68 3b 0a 20 20 7d 65  n &strHash;.  }e
1250: 6c 73 65 7b 0a 20 20 20 20 61 73 73 65 72 74 28  lse{.    assert(
1260: 20 6b 65 79 43 6c 61 73 73 3d 3d 53 51 4c 49 54   keyClass==SQLIT
1270: 45 5f 48 41 53 48 5f 42 49 4e 41 52 59 20 29 3b  E_HASH_BINARY );
1280: 0a 20 20 20 20 72 65 74 75 72 6e 20 26 62 69 6e  .    return &bin
1290: 48 61 73 68 3b 0a 20 20 7d 0a 23 65 6e 64 69 66  Hash;.  }.#endif
12a0: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e  .}../*.** Return
12b0: 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68   a pointer to th
12c0: 65 20 61 70 70 72 6f 70 72 69 61 74 65 20 68 61  e appropriate ha
12d0: 73 68 20 66 75 6e 63 74 69 6f 6e 20 67 69 76 65  sh function give
12e0: 6e 20 74 68 65 20 6b 65 79 20 63 6c 61 73 73 2e  n the key class.
12f0: 0a 2a 2a 0a 2a 2a 20 46 6f 72 20 68 65 6c 70 20  .**.** For help 
1300: 69 6e 20 69 6e 74 65 72 70 72 65 74 65 64 20 74  in interpreted t
1310: 68 65 20 6f 62 73 63 75 72 65 20 43 20 63 6f 64  he obscure C cod
1320: 65 20 69 6e 20 74 68 65 20 66 75 6e 63 74 69 6f  e in the functio
1330: 6e 20 64 65 66 69 6e 69 74 69 6f 6e 2c 0a 2a 2a  n definition,.**
1340: 20 73 65 65 20 74 68 65 20 68 65 61 64 65 72 20   see the header 
1350: 63 6f 6d 6d 65 6e 74 20 6f 6e 20 74 68 65 20 70  comment on the p
1360: 72 65 76 69 6f 75 73 20 66 75 6e 63 74 69 6f 6e  revious function
1370: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20  ..*/.static int 
1380: 28 2a 63 6f 6d 70 61 72 65 46 75 6e 63 74 69 6f  (*compareFunctio
1390: 6e 28 69 6e 74 20 6b 65 79 43 6c 61 73 73 29 29  n(int keyClass))
13a0: 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74  (const void*,int
13b0: 2c 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74  ,const void*,int
13c0: 29 7b 0a 23 69 66 20 30 20 2f 2a 20 48 41 53 48  ){.#if 0 /* HASH
13d0: 5f 49 4e 54 20 61 6e 64 20 48 41 53 48 5f 50 4f  _INT and HASH_PO
13e0: 49 4e 54 45 52 20 61 72 65 20 6e 65 76 65 72 20  INTER are never 
13f0: 75 73 65 64 20 2a 2f 0a 20 20 73 77 69 74 63 68  used */.  switch
1400: 28 20 6b 65 79 43 6c 61 73 73 20 29 7b 0a 20 20  ( keyClass ){.  
1410: 20 20 63 61 73 65 20 53 51 4c 49 54 45 5f 48 41    case SQLITE_HA
1420: 53 48 5f 49 4e 54 3a 20 20 20 20 20 72 65 74 75  SH_INT:     retu
1430: 72 6e 20 26 69 6e 74 43 6f 6d 70 61 72 65 3b 0a  rn &intCompare;.
1440: 20 20 20 20 63 61 73 65 20 53 51 4c 49 54 45 5f      case SQLITE_
1450: 48 41 53 48 5f 50 4f 49 4e 54 45 52 3a 20 72 65  HASH_POINTER: re
1460: 74 75 72 6e 20 26 70 74 72 43 6f 6d 70 61 72 65  turn &ptrCompare
1470: 3b 0a 20 20 20 20 63 61 73 65 20 53 51 4c 49 54  ;.    case SQLIT
1480: 45 5f 48 41 53 48 5f 53 54 52 49 4e 47 3a 20 20  E_HASH_STRING:  
1490: 72 65 74 75 72 6e 20 26 73 74 72 43 6f 6d 70 61  return &strCompa
14a0: 72 65 3b 0a 20 20 20 20 63 61 73 65 20 53 51 4c  re;.    case SQL
14b0: 49 54 45 5f 48 41 53 48 5f 42 49 4e 41 52 59 3a  ITE_HASH_BINARY:
14c0: 20 20 72 65 74 75 72 6e 20 26 62 69 6e 43 6f 6d    return &binCom
14d0: 70 61 72 65 3b 0a 20 20 20 20 64 65 66 61 75 6c  pare;.    defaul
14e0: 74 3a 20 62 72 65 61 6b 3b 0a 20 20 7d 0a 20 20  t: break;.  }.  
14f0: 72 65 74 75 72 6e 20 30 3b 0a 23 65 6c 73 65 0a  return 0;.#else.
1500: 20 20 69 66 28 20 6b 65 79 43 6c 61 73 73 3d 3d    if( keyClass==
1510: 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 49  SQLITE_HASH_STRI
1520: 4e 47 20 29 7b 0a 20 20 20 20 72 65 74 75 72 6e  NG ){.    return
1530: 20 26 73 74 72 43 6f 6d 70 61 72 65 3b 0a 20 20   &strCompare;.  
1540: 7d 65 6c 73 65 7b 0a 20 20 20 20 61 73 73 65 72  }else{.    asser
1550: 74 28 20 6b 65 79 43 6c 61 73 73 3d 3d 53 51 4c  t( keyClass==SQL
1560: 49 54 45 5f 48 41 53 48 5f 42 49 4e 41 52 59 20  ITE_HASH_BINARY 
1570: 29 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 26 62  );.    return &b
1580: 69 6e 43 6f 6d 70 61 72 65 3b 0a 20 20 7d 0a 23  inCompare;.  }.#
1590: 65 6e 64 69 66 0a 7d 0a 0a 2f 2a 20 4c 69 6e 6b  endif.}../* Link
15a0: 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69 6e 74 6f   an element into
15b0: 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 0a   the hash table.
15c0: 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 69  */.static void i
15d0: 6e 73 65 72 74 45 6c 65 6d 65 6e 74 28 0a 20 20  nsertElement(.  
15e0: 48 61 73 68 20 2a 70 48 2c 20 20 20 20 20 20 20  Hash *pH,       
15f0: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 63 6f         /* The co
1600: 6d 70 6c 65 74 65 20 68 61 73 68 20 74 61 62 6c  mplete hash tabl
1610: 65 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 5f 68  e */.  struct _h
1620: 74 20 2a 70 45 6e 74 72 79 2c 20 20 20 20 2f 2a  t *pEntry,    /*
1630: 20 54 68 65 20 65 6e 74 72 79 20 69 6e 74 6f 20   The entry into 
1640: 77 68 69 63 68 20 70 4e 65 77 20 69 73 20 69 6e  which pNew is in
1650: 73 65 72 74 65 64 20 2a 2f 0a 20 20 48 61 73 68  serted */.  Hash
1660: 45 6c 65 6d 20 2a 70 4e 65 77 20 20 20 20 20 20  Elem *pNew      
1670: 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e     /* The elemen
1680: 74 20 74 6f 20 62 65 20 69 6e 73 65 72 74 65 64  t to be inserted
1690: 20 2a 2f 0a 29 7b 0a 20 20 48 61 73 68 45 6c 65   */.){.  HashEle
16a0: 6d 20 2a 70 48 65 61 64 3b 20 20 20 20 20 20 20  m *pHead;       
16b0: 2f 2a 20 46 69 72 73 74 20 65 6c 65 6d 65 6e 74  /* First element
16c0: 20 61 6c 72 65 61 64 79 20 69 6e 20 70 45 6e 74   already in pEnt
16d0: 72 79 20 2a 2f 0a 20 20 70 48 65 61 64 20 3d 20  ry */.  pHead = 
16e0: 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3b 0a 20  pEntry->chain;. 
16f0: 20 69 66 28 20 70 48 65 61 64 20 29 7b 0a 20 20   if( pHead ){.  
1700: 20 20 70 4e 65 77 2d 3e 6e 65 78 74 20 3d 20 70    pNew->next = p
1710: 48 65 61 64 3b 0a 20 20 20 20 70 4e 65 77 2d 3e  Head;.    pNew->
1720: 70 72 65 76 20 3d 20 70 48 65 61 64 2d 3e 70 72  prev = pHead->pr
1730: 65 76 3b 0a 20 20 20 20 69 66 28 20 70 48 65 61  ev;.    if( pHea
1740: 64 2d 3e 70 72 65 76 20 29 7b 20 70 48 65 61 64  d->prev ){ pHead
1750: 2d 3e 70 72 65 76 2d 3e 6e 65 78 74 20 3d 20 70  ->prev->next = p
1760: 4e 65 77 3b 20 7d 0a 20 20 20 20 65 6c 73 65 20  New; }.    else 
1770: 20 20 20 20 20 20 20 20 20 20 20 20 7b 20 70 48              { pH
1780: 2d 3e 66 69 72 73 74 20 3d 20 70 4e 65 77 3b 20  ->first = pNew; 
1790: 7d 0a 20 20 20 20 70 48 65 61 64 2d 3e 70 72 65  }.    pHead->pre
17a0: 76 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 65 6c 73  v = pNew;.  }els
17b0: 65 7b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 65 78  e{.    pNew->nex
17c0: 74 20 3d 20 70 48 2d 3e 66 69 72 73 74 3b 0a 20  t = pH->first;. 
17d0: 20 20 20 69 66 28 20 70 48 2d 3e 66 69 72 73 74     if( pH->first
17e0: 20 29 7b 20 70 48 2d 3e 66 69 72 73 74 2d 3e 70   ){ pH->first->p
17f0: 72 65 76 20 3d 20 70 4e 65 77 3b 20 7d 0a 20 20  rev = pNew; }.  
1800: 20 20 70 4e 65 77 2d 3e 70 72 65 76 20 3d 20 30    pNew->prev = 0
1810: 3b 0a 20 20 20 20 70 48 2d 3e 66 69 72 73 74 20  ;.    pH->first 
1820: 3d 20 70 4e 65 77 3b 0a 20 20 7d 0a 20 20 70 45  = pNew;.  }.  pE
1830: 6e 74 72 79 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20  ntry->count++;. 
1840: 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 20 3d   pEntry->chain =
1850: 20 70 4e 65 77 3b 0a 7d 0a 0a 0a 2f 2a 20 52 65   pNew;.}.../* Re
1860: 73 69 7a 65 20 74 68 65 20 68 61 73 68 20 74 61  size the hash ta
1870: 62 6c 65 20 73 6f 20 74 68 61 74 20 69 74 20 63  ble so that it c
1880: 61 6e 74 61 69 6e 73 20 22 6e 65 77 5f 73 69 7a  antains "new_siz
1890: 65 22 20 62 75 63 6b 65 74 73 2e 0a 2a 2a 20 22  e" buckets..** "
18a0: 6e 65 77 5f 73 69 7a 65 22 20 6d 75 73 74 20 62  new_size" must b
18b0: 65 20 61 20 70 6f 77 65 72 20 6f 66 20 32 2e 20  e a power of 2. 
18c0: 20 54 68 65 20 68 61 73 68 20 74 61 62 6c 65 20   The hash table 
18d0: 6d 69 67 68 74 20 66 61 69 6c 20 0a 2a 2a 20 74  might fail .** t
18e0: 6f 20 72 65 73 69 7a 65 20 69 66 20 73 71 6c 69  o resize if sqli
18f0: 74 65 33 5f 6d 61 6c 6c 6f 63 28 29 20 66 61 69  te3_malloc() fai
1900: 6c 73 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f  ls..*/.static vo
1910: 69 64 20 72 65 68 61 73 68 28 48 61 73 68 20 2a  id rehash(Hash *
1920: 70 48 2c 20 69 6e 74 20 6e 65 77 5f 73 69 7a 65  pH, int new_size
1930: 29 7b 0a 20 20 73 74 72 75 63 74 20 5f 68 74 20  ){.  struct _ht 
1940: 2a 6e 65 77 5f 68 74 3b 20 20 20 20 20 20 20 20  *new_ht;        
1950: 20 20 20 20 2f 2a 20 54 68 65 20 6e 65 77 20 68      /* The new h
1960: 61 73 68 20 74 61 62 6c 65 20 2a 2f 0a 20 20 48  ash table */.  H
1970: 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 2c 20 2a  ashElem *elem, *
1980: 6e 65 78 74 5f 65 6c 65 6d 3b 20 20 20 20 2f 2a  next_elem;    /*
1990: 20 46 6f 72 20 6c 6f 6f 70 69 6e 67 20 6f 76 65   For looping ove
19a0: 72 20 65 78 69 73 74 69 6e 67 20 65 6c 65 6d 65  r existing eleme
19b0: 6e 74 73 20 2a 2f 0a 20 20 69 6e 74 20 28 2a 78  nts */.  int (*x
19c0: 48 61 73 68 29 28 63 6f 6e 73 74 20 76 6f 69 64  Hash)(const void
19d0: 2a 2c 69 6e 74 29 3b 20 2f 2a 20 54 68 65 20 68  *,int); /* The h
19e0: 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a  ash function */.
19f0: 0a 23 69 66 64 65 66 20 53 51 4c 49 54 45 5f 4d  .#ifdef SQLITE_M
1a00: 41 4c 4c 4f 43 5f 53 4f 46 54 5f 4c 49 4d 49 54  ALLOC_SOFT_LIMIT
1a10: 0a 20 20 69 66 28 20 6e 65 77 5f 73 69 7a 65 2a  .  if( new_size*
1a20: 73 69 7a 65 6f 66 28 73 74 72 75 63 74 20 5f 68  sizeof(struct _h
1a30: 74 29 3e 53 51 4c 49 54 45 5f 4d 41 4c 4c 4f 43  t)>SQLITE_MALLOC
1a40: 5f 53 4f 46 54 5f 4c 49 4d 49 54 20 29 7b 0a 20  _SOFT_LIMIT ){. 
1a50: 20 20 20 6e 65 77 5f 73 69 7a 65 20 3d 20 53 51     new_size = SQ
1a60: 4c 49 54 45 5f 4d 41 4c 4c 4f 43 5f 53 4f 46 54  LITE_MALLOC_SOFT
1a70: 5f 4c 49 4d 49 54 2f 73 69 7a 65 6f 66 28 73 74  _LIMIT/sizeof(st
1a80: 72 75 63 74 20 5f 68 74 29 3b 0a 20 20 7d 0a 20  ruct _ht);.  }. 
1a90: 20 69 66 28 20 6e 65 77 5f 73 69 7a 65 3d 3d 70   if( new_size==p
1aa0: 48 2d 3e 68 74 73 69 7a 65 20 29 20 72 65 74 75  H->htsize ) retu
1ab0: 72 6e 3b 0a 23 65 6e 64 69 66 0a 0a 20 20 2f 2a  rn;.#endif..  /*
1ac0: 20 54 68 65 72 65 20 69 73 20 61 20 63 61 6c 6c   There is a call
1ad0: 20 74 6f 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c   to sqlite3_mall
1ae0: 6f 63 28 29 20 69 6e 73 69 64 65 20 72 65 68 61  oc() inside reha
1af0: 73 68 28 29 2e 20 49 66 20 74 68 65 72 65 20 69  sh(). If there i
1b00: 73 0a 20 20 2a 2a 20 61 6c 72 65 61 64 79 20 61  s.  ** already a
1b10: 6e 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 61 74 20  n allocation at 
1b20: 70 48 2d 3e 68 74 2c 20 74 68 65 6e 20 69 66 20  pH->ht, then if 
1b30: 74 68 69 73 20 6d 61 6c 6c 6f 63 28 29 20 66 61  this malloc() fa
1b40: 69 6c 73 20 69 74 0a 20 20 2a 2a 20 69 73 20 62  ils it.  ** is b
1b50: 65 6e 69 67 6e 20 28 73 69 6e 63 65 20 66 61 69  enign (since fai
1b60: 6c 69 6e 67 20 74 6f 20 72 65 73 69 7a 65 20 61  ling to resize a
1b70: 20 68 61 73 68 20 74 61 62 6c 65 20 69 73 20 61   hash table is a
1b80: 20 70 65 72 66 6f 72 6d 61 6e 63 65 0a 20 20 2a   performance.  *
1b90: 2a 20 68 69 74 20 6f 6e 6c 79 2c 20 6e 6f 74 20  * hit only, not 
1ba0: 61 20 66 61 74 61 6c 20 65 72 72 6f 72 29 2e 0a  a fatal error)..
1bb0: 20 20 2a 2f 0a 20 20 69 66 28 20 70 48 2d 3e 68    */.  if( pH->h
1bc0: 74 73 69 7a 65 3e 30 20 29 20 73 71 6c 69 74 65  tsize>0 ) sqlite
1bd0: 33 42 65 67 69 6e 42 65 6e 69 67 6e 4d 61 6c 6c  3BeginBenignMall
1be0: 6f 63 28 29 3b 0a 20 20 6e 65 77 5f 68 74 20 3d  oc();.  new_ht =
1bf0: 20 28 73 74 72 75 63 74 20 5f 68 74 20 2a 29 73   (struct _ht *)s
1c00: 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 5a 65 72 6f  qlite3MallocZero
1c10: 28 20 6e 65 77 5f 73 69 7a 65 2a 73 69 7a 65 6f  ( new_size*sizeo
1c20: 66 28 73 74 72 75 63 74 20 5f 68 74 29 20 29 3b  f(struct _ht) );
1c30: 0a 20 20 69 66 28 20 70 48 2d 3e 68 74 73 69 7a  .  if( pH->htsiz
1c40: 65 3e 30 20 29 20 73 71 6c 69 74 65 33 45 6e 64  e>0 ) sqlite3End
1c50: 42 65 6e 69 67 6e 4d 61 6c 6c 6f 63 28 29 3b 0a  BenignMalloc();.
1c60: 0a 20 20 69 66 28 20 6e 65 77 5f 68 74 3d 3d 30  .  if( new_ht==0
1c70: 20 29 20 72 65 74 75 72 6e 3b 0a 20 20 73 71 6c   ) return;.  sql
1c80: 69 74 65 33 5f 66 72 65 65 28 70 48 2d 3e 68 74  ite3_free(pH->ht
1c90: 29 3b 0a 20 20 70 48 2d 3e 68 74 20 3d 20 6e 65  );.  pH->ht = ne
1ca0: 77 5f 68 74 3b 0a 20 20 70 48 2d 3e 68 74 73 69  w_ht;.  pH->htsi
1cb0: 7a 65 20 3d 20 6e 65 77 5f 73 69 7a 65 3b 0a 20  ze = new_size;. 
1cc0: 20 78 48 61 73 68 20 3d 20 68 61 73 68 46 75 6e   xHash = hashFun
1cd0: 63 74 69 6f 6e 28 70 48 2d 3e 6b 65 79 43 6c 61  ction(pH->keyCla
1ce0: 73 73 29 3b 0a 20 20 66 6f 72 28 65 6c 65 6d 3d  ss);.  for(elem=
1cf0: 70 48 2d 3e 66 69 72 73 74 2c 20 70 48 2d 3e 66  pH->first, pH->f
1d00: 69 72 73 74 3d 30 3b 20 65 6c 65 6d 3b 20 65 6c  irst=0; elem; el
1d10: 65 6d 20 3d 20 6e 65 78 74 5f 65 6c 65 6d 29 7b  em = next_elem){
1d20: 0a 20 20 20 20 69 6e 74 20 68 20 3d 20 28 2a 78  .    int h = (*x
1d30: 48 61 73 68 29 28 65 6c 65 6d 2d 3e 70 4b 65 79  Hash)(elem->pKey
1d40: 2c 20 65 6c 65 6d 2d 3e 6e 4b 65 79 29 20 26 20  , elem->nKey) & 
1d50: 28 6e 65 77 5f 73 69 7a 65 2d 31 29 3b 0a 20 20  (new_size-1);.  
1d60: 20 20 6e 65 78 74 5f 65 6c 65 6d 20 3d 20 65 6c    next_elem = el
1d70: 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 69 6e  em->next;.    in
1d80: 73 65 72 74 45 6c 65 6d 65 6e 74 28 70 48 2c 20  sertElement(pH, 
1d90: 26 6e 65 77 5f 68 74 5b 68 5d 2c 20 65 6c 65 6d  &new_ht[h], elem
1da0: 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 20 54 68 69  );.  }.}../* Thi
1db0: 73 20 66 75 6e 63 74 69 6f 6e 20 28 66 6f 72 20  s function (for 
1dc0: 69 6e 74 65 72 6e 61 6c 20 75 73 65 20 6f 6e 6c  internal use onl
1dd0: 79 29 20 6c 6f 63 61 74 65 73 20 61 6e 20 65 6c  y) locates an el
1de0: 65 6d 65 6e 74 20 69 6e 20 61 6e 0a 2a 2a 20 68  ement in an.** h
1df0: 61 73 68 20 74 61 62 6c 65 20 74 68 61 74 20 6d  ash table that m
1e00: 61 74 63 68 65 73 20 74 68 65 20 67 69 76 65 6e  atches the given
1e10: 20 6b 65 79 2e 20 20 54 68 65 20 68 61 73 68 20   key.  The hash 
1e20: 66 6f 72 20 74 68 69 73 20 6b 65 79 20 68 61 73  for this key has
1e30: 0a 2a 2a 20 61 6c 72 65 61 64 79 20 62 65 65 6e  .** already been
1e40: 20 63 6f 6d 70 75 74 65 64 20 61 6e 64 20 69 73   computed and is
1e50: 20 70 61 73 73 65 64 20 61 73 20 74 68 65 20 34   passed as the 4
1e60: 74 68 20 70 61 72 61 6d 65 74 65 72 2e 0a 2a 2f  th parameter..*/
1e70: 0a 73 74 61 74 69 63 20 48 61 73 68 45 6c 65 6d  .static HashElem
1e80: 20 2a 66 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76   *findElementGiv
1e90: 65 6e 48 61 73 68 28 0a 20 20 63 6f 6e 73 74 20  enHash(.  const 
1ea0: 48 61 73 68 20 2a 70 48 2c 20 20 20 20 20 2f 2a  Hash *pH,     /*
1eb0: 20 54 68 65 20 70 48 20 74 6f 20 62 65 20 73 65   The pH to be se
1ec0: 61 72 63 68 65 64 20 2a 2f 0a 20 20 63 6f 6e 73  arched */.  cons
1ed0: 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 20 20  t void *pKey,   
1ee0: 2f 2a 20 54 68 65 20 6b 65 79 20 77 65 20 61 72  /* The key we ar
1ef0: 65 20 73 65 61 72 63 68 69 6e 67 20 66 6f 72 20  e searching for 
1f00: 2a 2f 0a 20 20 69 6e 74 20 6e 4b 65 79 2c 0a 20  */.  int nKey,. 
1f10: 20 69 6e 74 20 68 20 20 20 20 20 20 20 20 20 20   int h          
1f20: 20 20 20 20 20 2f 2a 20 54 68 65 20 68 61 73 68       /* The hash
1f30: 20 66 6f 72 20 74 68 69 73 20 6b 65 79 2e 20 2a   for this key. *
1f40: 2f 0a 29 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20  /.){.  HashElem 
1f50: 2a 65 6c 65 6d 3b 20 20 20 20 20 20 20 20 20 20  *elem;          
1f60: 20 20 20 20 20 20 2f 2a 20 55 73 65 64 20 74 6f        /* Used to
1f70: 20 6c 6f 6f 70 20 74 68 72 75 20 74 68 65 20 65   loop thru the e
1f80: 6c 65 6d 65 6e 74 20 6c 69 73 74 20 2a 2f 0a 20  lement list */. 
1f90: 20 69 6e 74 20 63 6f 75 6e 74 3b 20 20 20 20 20   int count;     
1fa0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1fb0: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65 6c 65  /* Number of ele
1fc0: 6d 65 6e 74 73 20 6c 65 66 74 20 74 6f 20 74 65  ments left to te
1fd0: 73 74 20 2a 2f 0a 20 20 69 6e 74 20 28 2a 78 43  st */.  int (*xC
1fe0: 6f 6d 70 61 72 65 29 28 63 6f 6e 73 74 20 76 6f  ompare)(const vo
1ff0: 69 64 2a 2c 69 6e 74 2c 63 6f 6e 73 74 20 76 6f  id*,int,const vo
2000: 69 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a 20 63 6f  id*,int);  /* co
2010: 6d 70 61 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f  mparison functio
2020: 6e 20 2a 2f 0a 0a 20 20 69 66 28 20 70 48 2d 3e  n */..  if( pH->
2030: 68 74 20 29 7b 0a 20 20 20 20 73 74 72 75 63 74  ht ){.    struct
2040: 20 5f 68 74 20 2a 70 45 6e 74 72 79 20 3d 20 26   _ht *pEntry = &
2050: 70 48 2d 3e 68 74 5b 68 5d 3b 0a 20 20 20 20 65  pH->ht[h];.    e
2060: 6c 65 6d 20 3d 20 70 45 6e 74 72 79 2d 3e 63 68  lem = pEntry->ch
2070: 61 69 6e 3b 0a 20 20 20 20 63 6f 75 6e 74 20 3d  ain;.    count =
2080: 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 3b 0a   pEntry->count;.
2090: 20 20 20 20 78 43 6f 6d 70 61 72 65 20 3d 20 63      xCompare = c
20a0: 6f 6d 70 61 72 65 46 75 6e 63 74 69 6f 6e 28 70  ompareFunction(p
20b0: 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20  H->keyClass);.  
20c0: 20 20 77 68 69 6c 65 28 20 63 6f 75 6e 74 2d 2d    while( count--
20d0: 20 26 26 20 65 6c 65 6d 20 29 7b 0a 20 20 20 20   && elem ){.    
20e0: 20 20 69 66 28 20 28 2a 78 43 6f 6d 70 61 72 65    if( (*xCompare
20f0: 29 28 65 6c 65 6d 2d 3e 70 4b 65 79 2c 65 6c 65  )(elem->pKey,ele
2100: 6d 2d 3e 6e 4b 65 79 2c 70 4b 65 79 2c 6e 4b 65  m->nKey,pKey,nKe
2110: 79 29 3d 3d 30 20 29 7b 20 0a 20 20 20 20 20 20  y)==0 ){ .      
2120: 20 20 72 65 74 75 72 6e 20 65 6c 65 6d 3b 0a 20    return elem;. 
2130: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 65 6c 65       }.      ele
2140: 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a  m = elem->next;.
2150: 20 20 20 20 7d 0a 20 20 7d 0a 20 20 72 65 74 75      }.  }.  retu
2160: 72 6e 20 30 3b 0a 7d 0a 0a 2f 2a 20 52 65 6d 6f  rn 0;.}../* Remo
2170: 76 65 20 61 20 73 69 6e 67 6c 65 20 65 6e 74 72  ve a single entr
2180: 79 20 66 72 6f 6d 20 74 68 65 20 68 61 73 68 20  y from the hash 
2190: 74 61 62 6c 65 20 67 69 76 65 6e 20 61 20 70 6f  table given a po
21a0: 69 6e 74 65 72 20 74 6f 20 74 68 61 74 0a 2a 2a  inter to that.**
21b0: 20 65 6c 65 6d 65 6e 74 20 61 6e 64 20 61 20 68   element and a h
21c0: 61 73 68 20 6f 6e 20 74 68 65 20 65 6c 65 6d 65  ash on the eleme
21d0: 6e 74 27 73 20 6b 65 79 2e 0a 2a 2f 0a 73 74 61  nt's key..*/.sta
21e0: 74 69 63 20 76 6f 69 64 20 72 65 6d 6f 76 65 45  tic void removeE
21f0: 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28  lementGivenHash(
2200: 0a 20 20 48 61 73 68 20 2a 70 48 2c 20 20 20 20  .  Hash *pH,    
2210: 20 20 20 20 20 2f 2a 20 54 68 65 20 70 48 20 63       /* The pH c
2220: 6f 6e 74 61 69 6e 69 6e 67 20 22 65 6c 65 6d 22  ontaining "elem"
2230: 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 2a 20   */.  HashElem* 
2240: 65 6c 65 6d 2c 20 20 20 2f 2a 20 54 68 65 20 65  elem,   /* The e
2250: 6c 65 6d 65 6e 74 20 74 6f 20 62 65 20 72 65 6d  lement to be rem
2260: 6f 76 65 64 20 66 72 6f 6d 20 74 68 65 20 70 48  oved from the pH
2270: 20 2a 2f 0a 20 20 69 6e 74 20 68 20 20 20 20 20   */.  int h     
2280: 20 20 20 20 20 20 20 20 2f 2a 20 48 61 73 68 20          /* Hash 
2290: 76 61 6c 75 65 20 66 6f 72 20 74 68 65 20 65 6c  value for the el
22a0: 65 6d 65 6e 74 20 2a 2f 0a 29 7b 0a 20 20 73 74  ement */.){.  st
22b0: 72 75 63 74 20 5f 68 74 20 2a 70 45 6e 74 72 79  ruct _ht *pEntry
22c0: 3b 0a 20 20 69 66 28 20 65 6c 65 6d 2d 3e 70 72  ;.  if( elem->pr
22d0: 65 76 20 29 7b 0a 20 20 20 20 65 6c 65 6d 2d 3e  ev ){.    elem->
22e0: 70 72 65 76 2d 3e 6e 65 78 74 20 3d 20 65 6c 65  prev->next = ele
22f0: 6d 2d 3e 6e 65 78 74 3b 20 0a 20 20 7d 65 6c 73  m->next; .  }els
2300: 65 7b 0a 20 20 20 20 70 48 2d 3e 66 69 72 73 74  e{.    pH->first
2310: 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20   = elem->next;. 
2320: 20 7d 0a 20 20 69 66 28 20 65 6c 65 6d 2d 3e 6e   }.  if( elem->n
2330: 65 78 74 20 29 7b 0a 20 20 20 20 65 6c 65 6d 2d  ext ){.    elem-
2340: 3e 6e 65 78 74 2d 3e 70 72 65 76 20 3d 20 65 6c  >next->prev = el
2350: 65 6d 2d 3e 70 72 65 76 3b 0a 20 20 7d 0a 20 20  em->prev;.  }.  
2360: 70 45 6e 74 72 79 20 3d 20 26 70 48 2d 3e 68 74  pEntry = &pH->ht
2370: 5b 68 5d 3b 0a 20 20 69 66 28 20 70 45 6e 74 72  [h];.  if( pEntr
2380: 79 2d 3e 63 68 61 69 6e 3d 3d 65 6c 65 6d 20 29  y->chain==elem )
2390: 7b 0a 20 20 20 20 70 45 6e 74 72 79 2d 3e 63 68  {.    pEntry->ch
23a0: 61 69 6e 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74  ain = elem->next
23b0: 3b 0a 20 20 7d 0a 20 20 70 45 6e 74 72 79 2d 3e  ;.  }.  pEntry->
23c0: 63 6f 75 6e 74 2d 2d 3b 0a 20 20 69 66 28 20 70  count--;.  if( p
23d0: 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 3c 3d 30 20  Entry->count<=0 
23e0: 29 7b 0a 20 20 20 20 70 45 6e 74 72 79 2d 3e 63  ){.    pEntry->c
23f0: 68 61 69 6e 20 3d 20 30 3b 0a 20 20 7d 0a 20 20  hain = 0;.  }.  
2400: 69 66 28 20 70 48 2d 3e 63 6f 70 79 4b 65 79 20  if( pH->copyKey 
2410: 29 7b 0a 20 20 20 20 73 71 6c 69 74 65 33 5f 66  ){.    sqlite3_f
2420: 72 65 65 28 65 6c 65 6d 2d 3e 70 4b 65 79 29 3b  ree(elem->pKey);
2430: 0a 20 20 7d 0a 20 20 73 71 6c 69 74 65 33 5f 66  .  }.  sqlite3_f
2440: 72 65 65 28 20 65 6c 65 6d 20 29 3b 0a 20 20 70  ree( elem );.  p
2450: 48 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a 20 20 69 66  H->count--;.  if
2460: 28 20 70 48 2d 3e 63 6f 75 6e 74 3c 3d 30 20 29  ( pH->count<=0 )
2470: 7b 0a 20 20 20 20 61 73 73 65 72 74 28 20 70 48  {.    assert( pH
2480: 2d 3e 66 69 72 73 74 3d 3d 30 20 29 3b 0a 20 20  ->first==0 );.  
2490: 20 20 61 73 73 65 72 74 28 20 70 48 2d 3e 63 6f    assert( pH->co
24a0: 75 6e 74 3d 3d 30 20 29 3b 0a 20 20 20 20 73 71  unt==0 );.    sq
24b0: 6c 69 74 65 33 48 61 73 68 43 6c 65 61 72 28 70  lite3HashClear(p
24c0: 48 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 20 41 74  H);.  }.}../* At
24d0: 74 65 6d 70 74 20 74 6f 20 6c 6f 63 61 74 65 20  tempt to locate 
24e0: 61 6e 20 65 6c 65 6d 65 6e 74 20 6f 66 20 74 68  an element of th
24f0: 65 20 68 61 73 68 20 74 61 62 6c 65 20 70 48 20  e hash table pH 
2500: 77 69 74 68 20 61 20 6b 65 79 0a 2a 2a 20 74 68  with a key.** th
2510: 61 74 20 6d 61 74 63 68 65 73 20 70 4b 65 79 2c  at matches pKey,
2520: 6e 4b 65 79 2e 20 20 52 65 74 75 72 6e 20 61 20  nKey.  Return a 
2530: 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 20 63  pointer to the c
2540: 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 0a 2a 2a  orresponding .**
2550: 20 48 61 73 68 45 6c 65 6d 20 73 74 72 75 63 74   HashElem struct
2560: 75 72 65 20 66 6f 72 20 74 68 69 73 20 65 6c 65  ure for this ele
2570: 6d 65 6e 74 20 69 66 20 69 74 20 69 73 20 66 6f  ment if it is fo
2580: 75 6e 64 2c 20 6f 72 20 4e 55 4c 4c 0a 2a 2a 20  und, or NULL.** 
2590: 6f 74 68 65 72 77 69 73 65 2e 0a 2a 2f 0a 48 61  otherwise..*/.Ha
25a0: 73 68 45 6c 65 6d 20 2a 73 71 6c 69 74 65 33 48  shElem *sqlite3H
25b0: 61 73 68 46 69 6e 64 45 6c 65 6d 28 63 6f 6e 73  ashFindElem(cons
25c0: 74 20 48 61 73 68 20 2a 70 48 2c 20 63 6f 6e 73  t Hash *pH, cons
25d0: 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e  t void *pKey, in
25e0: 74 20 6e 4b 65 79 29 7b 0a 20 20 69 6e 74 20 68  t nKey){.  int h
25f0: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  ;             /*
2600: 20 41 20 68 61 73 68 20 6f 6e 20 6b 65 79 20 2a   A hash on key *
2610: 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c  /.  HashElem *el
2620: 65 6d 3b 20 20 20 20 2f 2a 20 54 68 65 20 65 6c  em;    /* The el
2630: 65 6d 65 6e 74 20 74 68 61 74 20 6d 61 74 63 68  ement that match
2640: 65 73 20 6b 65 79 20 2a 2f 0a 20 20 69 6e 74 20  es key */.  int 
2650: 28 2a 78 48 61 73 68 29 28 63 6f 6e 73 74 20 76  (*xHash)(const v
2660: 6f 69 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a 20 54  oid*,int);  /* T
2670: 68 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e  he hash function
2680: 20 2a 2f 0a 0a 20 20 69 66 28 20 70 48 3d 3d 30   */..  if( pH==0
2690: 20 7c 7c 20 70 48 2d 3e 68 74 3d 3d 30 20 29 20   || pH->ht==0 ) 
26a0: 72 65 74 75 72 6e 20 30 3b 0a 20 20 78 48 61 73  return 0;.  xHas
26b0: 68 20 3d 20 68 61 73 68 46 75 6e 63 74 69 6f 6e  h = hashFunction
26c0: 28 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a  (pH->keyClass);.
26d0: 20 20 61 73 73 65 72 74 28 20 78 48 61 73 68 21    assert( xHash!
26e0: 3d 30 20 29 3b 0a 20 20 68 20 3d 20 28 2a 78 48  =0 );.  h = (*xH
26f0: 61 73 68 29 28 70 4b 65 79 2c 6e 4b 65 79 29 3b  ash)(pKey,nKey);
2700: 0a 20 20 65 6c 65 6d 20 3d 20 66 69 6e 64 45 6c  .  elem = findEl
2710: 65 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28 70  ementGivenHash(p
2720: 48 2c 70 4b 65 79 2c 6e 4b 65 79 2c 20 68 20 25  H,pKey,nKey, h %
2730: 20 70 48 2d 3e 68 74 73 69 7a 65 29 3b 0a 20 20   pH->htsize);.  
2740: 72 65 74 75 72 6e 20 65 6c 65 6d 3b 0a 7d 0a 0a  return elem;.}..
2750: 2f 2a 20 41 74 74 65 6d 70 74 20 74 6f 20 6c 6f  /* Attempt to lo
2760: 63 61 74 65 20 61 6e 20 65 6c 65 6d 65 6e 74 20  cate an element 
2770: 6f 66 20 74 68 65 20 68 61 73 68 20 74 61 62 6c  of the hash tabl
2780: 65 20 70 48 20 77 69 74 68 20 61 20 6b 65 79 0a  e pH with a key.
2790: 2a 2a 20 74 68 61 74 20 6d 61 74 63 68 65 73 20  ** that matches 
27a0: 70 4b 65 79 2c 6e 4b 65 79 2e 20 20 52 65 74 75  pKey,nKey.  Retu
27b0: 72 6e 20 74 68 65 20 64 61 74 61 20 66 6f 72 20  rn the data for 
27c0: 74 68 69 73 20 65 6c 65 6d 65 6e 74 20 69 66 20  this element if 
27d0: 69 74 20 69 73 0a 2a 2a 20 66 6f 75 6e 64 2c 20  it is.** found, 
27e0: 6f 72 20 4e 55 4c 4c 20 69 66 20 74 68 65 72 65  or NULL if there
27f0: 20 69 73 20 6e 6f 20 6d 61 74 63 68 2e 0a 2a 2f   is no match..*/
2800: 0a 76 6f 69 64 20 2a 73 71 6c 69 74 65 33 48 61  .void *sqlite3Ha
2810: 73 68 46 69 6e 64 28 63 6f 6e 73 74 20 48 61 73  shFind(const Has
2820: 68 20 2a 70 48 2c 20 63 6f 6e 73 74 20 76 6f 69  h *pH, const voi
2830: 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65  d *pKey, int nKe
2840: 79 29 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a  y){.  HashElem *
2850: 65 6c 65 6d 3b 20 20 20 20 2f 2a 20 54 68 65 20  elem;    /* The 
2860: 65 6c 65 6d 65 6e 74 20 74 68 61 74 20 6d 61 74  element that mat
2870: 63 68 65 73 20 6b 65 79 20 2a 2f 0a 20 20 65 6c  ches key */.  el
2880: 65 6d 20 3d 20 73 71 6c 69 74 65 33 48 61 73 68  em = sqlite3Hash
2890: 46 69 6e 64 45 6c 65 6d 28 70 48 2c 20 70 4b 65  FindElem(pH, pKe
28a0: 79 2c 20 6e 4b 65 79 29 3b 0a 20 20 72 65 74 75  y, nKey);.  retu
28b0: 72 6e 20 65 6c 65 6d 20 3f 20 65 6c 65 6d 2d 3e  rn elem ? elem->
28c0: 64 61 74 61 20 3a 20 30 3b 0a 7d 0a 0a 2f 2a 20  data : 0;.}../* 
28d0: 49 6e 73 65 72 74 20 61 6e 20 65 6c 65 6d 65 6e  Insert an elemen
28e0: 74 20 69 6e 74 6f 20 74 68 65 20 68 61 73 68 20  t into the hash 
28f0: 74 61 62 6c 65 20 70 48 2e 20 20 54 68 65 20 6b  table pH.  The k
2900: 65 79 20 69 73 20 70 4b 65 79 2c 6e 4b 65 79 0a  ey is pKey,nKey.
2910: 2a 2a 20 61 6e 64 20 74 68 65 20 64 61 74 61 20  ** and the data 
2920: 69 73 20 22 64 61 74 61 22 2e 0a 2a 2a 0a 2a 2a  is "data"..**.**
2930: 20 49 66 20 6e 6f 20 65 6c 65 6d 65 6e 74 20 65   If no element e
2940: 78 69 73 74 73 20 77 69 74 68 20 61 20 6d 61 74  xists with a mat
2950: 63 68 69 6e 67 20 6b 65 79 2c 20 74 68 65 6e 20  ching key, then 
2960: 61 20 6e 65 77 0a 2a 2a 20 65 6c 65 6d 65 6e 74  a new.** element
2970: 20 69 73 20 63 72 65 61 74 65 64 2e 20 20 41 20   is created.  A 
2980: 63 6f 70 79 20 6f 66 20 74 68 65 20 6b 65 79 20  copy of the key 
2990: 69 73 20 6d 61 64 65 20 69 66 20 74 68 65 20 63  is made if the c
29a0: 6f 70 79 4b 65 79 0a 2a 2a 20 66 6c 61 67 20 69  opyKey.** flag i
29b0: 73 20 73 65 74 2e 20 20 4e 55 4c 4c 20 69 73 20  s set.  NULL is 
29c0: 72 65 74 75 72 6e 65 64 2e 0a 2a 2a 0a 2a 2a 20  returned..**.** 
29d0: 49 66 20 61 6e 6f 74 68 65 72 20 65 6c 65 6d 65  If another eleme
29e0: 6e 74 20 61 6c 72 65 61 64 79 20 65 78 69 73 74  nt already exist
29f0: 73 20 77 69 74 68 20 74 68 65 20 73 61 6d 65 20  s with the same 
2a00: 6b 65 79 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a  key, then the.**
2a10: 20 6e 65 77 20 64 61 74 61 20 72 65 70 6c 61 63   new data replac
2a20: 65 73 20 74 68 65 20 6f 6c 64 20 64 61 74 61 20  es the old data 
2a30: 61 6e 64 20 74 68 65 20 6f 6c 64 20 64 61 74 61  and the old data
2a40: 20 69 73 20 72 65 74 75 72 6e 65 64 2e 0a 2a 2a   is returned..**
2a50: 20 54 68 65 20 6b 65 79 20 69 73 20 6e 6f 74 20   The key is not 
2a60: 63 6f 70 69 65 64 20 69 6e 20 74 68 69 73 20 69  copied in this i
2a70: 6e 73 74 61 6e 63 65 2e 20 20 49 66 20 61 20 6d  nstance.  If a m
2a80: 61 6c 6c 6f 63 20 66 61 69 6c 73 2c 20 74 68 65  alloc fails, the
2a90: 6e 0a 2a 2a 20 74 68 65 20 6e 65 77 20 64 61 74  n.** the new dat
2aa0: 61 20 69 73 20 72 65 74 75 72 6e 65 64 20 61 6e  a is returned an
2ab0: 64 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65  d the hash table
2ac0: 20 69 73 20 75 6e 63 68 61 6e 67 65 64 2e 0a 2a   is unchanged..*
2ad0: 2a 0a 2a 2a 20 49 66 20 74 68 65 20 22 64 61 74  *.** If the "dat
2ae0: 61 22 20 70 61 72 61 6d 65 74 65 72 20 74 6f 20  a" parameter to 
2af0: 74 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 69 73  this function is
2b00: 20 4e 55 4c 4c 2c 20 74 68 65 6e 20 74 68 65 0a   NULL, then the.
2b10: 2a 2a 20 65 6c 65 6d 65 6e 74 20 63 6f 72 72 65  ** element corre
2b20: 73 70 6f 6e 64 69 6e 67 20 74 6f 20 22 6b 65 79  sponding to "key
2b30: 22 20 69 73 20 72 65 6d 6f 76 65 64 20 66 72 6f  " is removed fro
2b40: 6d 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65  m the hash table
2b50: 2e 0a 2a 2f 0a 76 6f 69 64 20 2a 73 71 6c 69 74  ..*/.void *sqlit
2b60: 65 33 48 61 73 68 49 6e 73 65 72 74 28 48 61 73  e3HashInsert(Has
2b70: 68 20 2a 70 48 2c 20 63 6f 6e 73 74 20 76 6f 69  h *pH, const voi
2b80: 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65  d *pKey, int nKe
2b90: 79 2c 20 76 6f 69 64 20 2a 64 61 74 61 29 7b 0a  y, void *data){.
2ba0: 20 20 69 6e 74 20 68 72 61 77 3b 20 20 20 20 20    int hraw;     
2bb0: 20 20 20 20 20 20 20 20 2f 2a 20 52 61 77 20 68          /* Raw h
2bc0: 61 73 68 20 76 61 6c 75 65 20 6f 66 20 74 68 65  ash value of the
2bd0: 20 6b 65 79 20 2a 2f 0a 20 20 69 6e 74 20 68 3b   key */.  int h;
2be0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2bf0: 2f 2a 20 74 68 65 20 68 61 73 68 20 6f 66 20 74  /* the hash of t
2c00: 68 65 20 6b 65 79 20 6d 6f 64 75 6c 6f 20 68 61  he key modulo ha
2c10: 73 68 20 74 61 62 6c 65 20 73 69 7a 65 20 2a 2f  sh table size */
2c20: 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65  .  HashElem *ele
2c30: 6d 3b 20 20 20 20 20 20 20 2f 2a 20 55 73 65 64  m;       /* Used
2c40: 20 74 6f 20 6c 6f 6f 70 20 74 68 72 75 20 74 68   to loop thru th
2c50: 65 20 65 6c 65 6d 65 6e 74 20 6c 69 73 74 20 2a  e element list *
2c60: 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 6e 65  /.  HashElem *ne
2c70: 77 5f 65 6c 65 6d 3b 20 20 20 2f 2a 20 4e 65 77  w_elem;   /* New
2c80: 20 65 6c 65 6d 65 6e 74 20 61 64 64 65 64 20 74   element added t
2c90: 6f 20 74 68 65 20 70 48 20 2a 2f 0a 20 20 69 6e  o the pH */.  in
2ca0: 74 20 28 2a 78 48 61 73 68 29 28 63 6f 6e 73 74  t (*xHash)(const
2cb0: 20 76 6f 69 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a   void*,int);  /*
2cc0: 20 54 68 65 20 68 61 73 68 20 66 75 6e 63 74 69   The hash functi
2cd0: 6f 6e 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28  on */..  assert(
2ce0: 20 70 48 21 3d 30 20 29 3b 0a 20 20 78 48 61 73   pH!=0 );.  xHas
2cf0: 68 20 3d 20 68 61 73 68 46 75 6e 63 74 69 6f 6e  h = hashFunction
2d00: 28 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a  (pH->keyClass);.
2d10: 20 20 61 73 73 65 72 74 28 20 78 48 61 73 68 21    assert( xHash!
2d20: 3d 30 20 29 3b 0a 20 20 68 72 61 77 20 3d 20 28  =0 );.  hraw = (
2d30: 2a 78 48 61 73 68 29 28 70 4b 65 79 2c 20 6e 4b  *xHash)(pKey, nK
2d40: 65 79 29 3b 0a 20 20 69 66 28 20 70 48 2d 3e 68  ey);.  if( pH->h
2d50: 74 73 69 7a 65 20 29 7b 0a 20 20 20 20 68 20 3d  tsize ){.    h =
2d60: 20 68 72 61 77 20 25 20 70 48 2d 3e 68 74 73 69   hraw % pH->htsi
2d70: 7a 65 3b 0a 20 20 20 20 65 6c 65 6d 20 3d 20 66  ze;.    elem = f
2d80: 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48  indElementGivenH
2d90: 61 73 68 28 70 48 2c 70 4b 65 79 2c 6e 4b 65 79  ash(pH,pKey,nKey
2da0: 2c 68 29 3b 0a 20 20 20 20 69 66 28 20 65 6c 65  ,h);.    if( ele
2db0: 6d 20 29 7b 0a 20 20 20 20 20 20 76 6f 69 64 20  m ){.      void 
2dc0: 2a 6f 6c 64 5f 64 61 74 61 20 3d 20 65 6c 65 6d  *old_data = elem
2dd0: 2d 3e 64 61 74 61 3b 0a 20 20 20 20 20 20 69 66  ->data;.      if
2de0: 28 20 64 61 74 61 3d 3d 30 20 29 7b 0a 20 20 20  ( data==0 ){.   
2df0: 20 20 20 20 20 72 65 6d 6f 76 65 45 6c 65 6d 65       removeEleme
2e00: 6e 74 47 69 76 65 6e 48 61 73 68 28 70 48 2c 65  ntGivenHash(pH,e
2e10: 6c 65 6d 2c 68 29 3b 0a 20 20 20 20 20 20 7d 65  lem,h);.      }e
2e20: 6c 73 65 7b 0a 20 20 20 20 20 20 20 20 65 6c 65  lse{.        ele
2e30: 6d 2d 3e 64 61 74 61 20 3d 20 64 61 74 61 3b 0a  m->data = data;.
2e40: 20 20 20 20 20 20 20 20 69 66 28 20 21 70 48 2d          if( !pH-
2e50: 3e 63 6f 70 79 4b 65 79 20 29 7b 0a 20 20 20 20  >copyKey ){.    
2e60: 20 20 20 20 20 20 65 6c 65 6d 2d 3e 70 4b 65 79        elem->pKey
2e70: 20 3d 20 28 76 6f 69 64 20 2a 29 70 4b 65 79 3b   = (void *)pKey;
2e80: 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20  .        }.     
2e90: 20 20 20 61 73 73 65 72 74 28 6e 4b 65 79 3d 3d     assert(nKey==
2ea0: 65 6c 65 6d 2d 3e 6e 4b 65 79 29 3b 0a 20 20 20  elem->nKey);.   
2eb0: 20 20 20 7d 0a 20 20 20 20 20 20 72 65 74 75 72     }.      retur
2ec0: 6e 20 6f 6c 64 5f 64 61 74 61 3b 0a 20 20 20 20  n old_data;.    
2ed0: 7d 0a 20 20 7d 0a 20 20 69 66 28 20 64 61 74 61  }.  }.  if( data
2ee0: 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 30 3b 0a  ==0 ) return 0;.
2ef0: 20 20 6e 65 77 5f 65 6c 65 6d 20 3d 20 28 48 61    new_elem = (Ha
2f00: 73 68 45 6c 65 6d 2a 29 73 71 6c 69 74 65 33 4d  shElem*)sqlite3M
2f10: 61 6c 6c 6f 63 28 20 73 69 7a 65 6f 66 28 48 61  alloc( sizeof(Ha
2f20: 73 68 45 6c 65 6d 29 20 29 3b 0a 20 20 69 66 28  shElem) );.  if(
2f30: 20 6e 65 77 5f 65 6c 65 6d 3d 3d 30 20 29 20 72   new_elem==0 ) r
2f40: 65 74 75 72 6e 20 64 61 74 61 3b 0a 20 20 69 66  eturn data;.  if
2f50: 28 20 70 48 2d 3e 63 6f 70 79 4b 65 79 20 26 26  ( pH->copyKey &&
2f60: 20 70 4b 65 79 21 3d 30 20 29 7b 0a 20 20 20 20   pKey!=0 ){.    
2f70: 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 20 3d  new_elem->pKey =
2f80: 20 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 28 20   sqlite3Malloc( 
2f90: 6e 4b 65 79 20 29 3b 0a 20 20 20 20 69 66 28 20  nKey );.    if( 
2fa0: 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 3d 3d  new_elem->pKey==
2fb0: 30 20 29 7b 0a 20 20 20 20 20 20 73 71 6c 69 74  0 ){.      sqlit
2fc0: 65 33 5f 66 72 65 65 28 6e 65 77 5f 65 6c 65 6d  e3_free(new_elem
2fd0: 29 3b 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20  );.      return 
2fe0: 64 61 74 61 3b 0a 20 20 20 20 7d 0a 20 20 20 20  data;.    }.    
2ff0: 6d 65 6d 63 70 79 28 28 76 6f 69 64 2a 29 6e 65  memcpy((void*)ne
3000: 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 2c 20 70 4b  w_elem->pKey, pK
3010: 65 79 2c 20 6e 4b 65 79 29 3b 0a 20 20 7d 65 6c  ey, nKey);.  }el
3020: 73 65 7b 0a 20 20 20 20 6e 65 77 5f 65 6c 65 6d  se{.    new_elem
3030: 2d 3e 70 4b 65 79 20 3d 20 28 76 6f 69 64 2a 29  ->pKey = (void*)
3040: 70 4b 65 79 3b 0a 20 20 7d 0a 20 20 6e 65 77 5f  pKey;.  }.  new_
3050: 65 6c 65 6d 2d 3e 6e 4b 65 79 20 3d 20 6e 4b 65  elem->nKey = nKe
3060: 79 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 2b 2b  y;.  pH->count++
3070: 3b 0a 20 20 69 66 28 20 70 48 2d 3e 68 74 73 69  ;.  if( pH->htsi
3080: 7a 65 3d 3d 30 20 29 7b 0a 20 20 20 20 72 65 68  ze==0 ){.    reh
3090: 61 73 68 28 70 48 2c 20 31 32 38 2f 73 69 7a 65  ash(pH, 128/size
30a0: 6f 66 28 70 48 2d 3e 68 74 5b 30 5d 29 29 3b 0a  of(pH->ht[0]));.
30b0: 20 20 20 20 69 66 28 20 70 48 2d 3e 68 74 73 69      if( pH->htsi
30c0: 7a 65 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 70  ze==0 ){.      p
30d0: 48 2d 3e 63 6f 75 6e 74 20 3d 20 30 3b 0a 20 20  H->count = 0;.  
30e0: 20 20 20 20 69 66 28 20 70 48 2d 3e 63 6f 70 79      if( pH->copy
30f0: 4b 65 79 20 29 7b 0a 20 20 20 20 20 20 20 20 73  Key ){.        s
3100: 71 6c 69 74 65 33 5f 66 72 65 65 28 6e 65 77 5f  qlite3_free(new_
3110: 65 6c 65 6d 2d 3e 70 4b 65 79 29 3b 0a 20 20 20  elem->pKey);.   
3120: 20 20 20 7d 0a 20 20 20 20 20 20 73 71 6c 69 74     }.      sqlit
3130: 65 33 5f 66 72 65 65 28 6e 65 77 5f 65 6c 65 6d  e3_free(new_elem
3140: 29 3b 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20  );.      return 
3150: 64 61 74 61 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a  data;.    }.  }.
3160: 20 20 69 66 28 20 70 48 2d 3e 63 6f 75 6e 74 20    if( pH->count 
3170: 3e 20 70 48 2d 3e 68 74 73 69 7a 65 20 29 7b 0a  > pH->htsize ){.
3180: 20 20 20 20 72 65 68 61 73 68 28 70 48 2c 70 48      rehash(pH,pH
3190: 2d 3e 68 74 73 69 7a 65 2a 32 29 3b 0a 20 20 7d  ->htsize*2);.  }
31a0: 0a 20 20 61 73 73 65 72 74 28 20 70 48 2d 3e 68  .  assert( pH->h
31b0: 74 73 69 7a 65 3e 30 20 29 3b 0a 20 20 68 20 3d  tsize>0 );.  h =
31c0: 20 68 72 61 77 20 25 20 70 48 2d 3e 68 74 73 69   hraw % pH->htsi
31d0: 7a 65 3b 0a 20 20 69 6e 73 65 72 74 45 6c 65 6d  ze;.  insertElem
31e0: 65 6e 74 28 70 48 2c 20 26 70 48 2d 3e 68 74 5b  ent(pH, &pH->ht[
31f0: 68 5d 2c 20 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20  h], new_elem);. 
3200: 20 6e 65 77 5f 65 6c 65 6d 2d 3e 64 61 74 61 20   new_elem->data 
3210: 3d 20 64 61 74 61 3b 0a 20 20 72 65 74 75 72 6e  = data;.  return
3220: 20 30 3b 0a 7d 0a                                 0;.}.