/ Hex Artifact Content
Login

Artifact 83e7bb4042106b32811681dd2859b4577a7a6b35:


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 20 75 73 65 64  hash-tables used
01b0: 20 69 6e 20 53 51 4c 69 74 65 2e 0a 2a 2a 20 57   in SQLite..** W
01c0: 65 27 76 65 20 6d 6f 64 69 66 69 65 64 20 69 74  e've modified it
01d0: 20 73 6c 69 67 68 74 6c 79 20 74 6f 20 73 65 72   slightly to ser
01e0: 76 65 20 61 73 20 61 20 73 74 61 6e 64 61 6c 6f  ve as a standalo
01f0: 6e 65 20 68 61 73 68 20 74 61 62 6c 65 0a 2a 2a  ne hash table.**
0200: 20 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20   implementation 
0210: 66 6f 72 20 74 68 65 20 66 75 6c 6c 2d 74 65 78  for the full-tex
0220: 74 20 69 6e 64 65 78 69 6e 67 20 6d 6f 64 75 6c  t indexing modul
0230: 65 2e 0a 2a 2f 0a 0a 2f 2a 0a 2a 2a 20 54 68 65  e..*/../*.** The
0240: 20 63 6f 64 65 20 69 6e 20 74 68 69 73 20 66 69   code in this fi
0250: 6c 65 20 69 73 20 6f 6e 6c 79 20 63 6f 6d 70 69  le is only compi
0260: 6c 65 64 20 69 66 3a 0a 2a 2a 0a 2a 2a 20 20 20  led if:.**.**   
0270: 20 20 2a 20 54 68 65 20 46 54 53 33 20 6d 6f 64    * The FTS3 mod
0280: 75 6c 65 20 69 73 20 62 65 69 6e 67 20 62 75 69  ule is being bui
0290: 6c 74 20 61 73 20 61 6e 20 65 78 74 65 6e 73 69  lt as an extensi
02a0: 6f 6e 0a 2a 2a 20 20 20 20 20 20 20 28 69 6e 20  on.**       (in 
02b0: 77 68 69 63 68 20 63 61 73 65 20 53 51 4c 49 54  which case SQLIT
02c0: 45 5f 43 4f 52 45 20 69 73 20 6e 6f 74 20 64 65  E_CORE is not de
02d0: 66 69 6e 65 64 29 2c 20 6f 72 0a 2a 2a 0a 2a 2a  fined), or.**.**
02e0: 20 20 20 20 20 2a 20 54 68 65 20 46 54 53 33 20       * The FTS3 
02f0: 6d 6f 64 75 6c 65 20 69 73 20 62 65 69 6e 67 20  module is being 
0300: 62 75 69 6c 74 20 69 6e 74 6f 20 74 68 65 20 63  built into the c
0310: 6f 72 65 20 6f 66 0a 2a 2a 20 20 20 20 20 20 20  ore of.**       
0320: 53 51 4c 69 74 65 20 28 69 6e 20 77 68 69 63 68  SQLite (in which
0330: 20 63 61 73 65 20 53 51 4c 49 54 45 5f 45 4e 41   case SQLITE_ENA
0340: 42 4c 45 5f 46 54 53 33 20 69 73 20 64 65 66 69  BLE_FTS3 is defi
0350: 6e 65 64 29 2e 0a 2a 2f 0a 23 69 66 20 21 64 65  ned)..*/.#if !de
0360: 66 69 6e 65 64 28 53 51 4c 49 54 45 5f 43 4f 52  fined(SQLITE_COR
0370: 45 29 20 7c 7c 20 64 65 66 69 6e 65 64 28 53 51  E) || defined(SQ
0380: 4c 49 54 45 5f 45 4e 41 42 4c 45 5f 46 54 53 33  LITE_ENABLE_FTS3
0390: 29 0a 0a 23 69 6e 63 6c 75 64 65 20 3c 61 73 73  )..#include <ass
03a0: 65 72 74 2e 68 3e 0a 23 69 6e 63 6c 75 64 65 20  ert.h>.#include 
03b0: 3c 73 74 64 6c 69 62 2e 68 3e 0a 23 69 6e 63 6c  <stdlib.h>.#incl
03c0: 75 64 65 20 3c 73 74 72 69 6e 67 2e 68 3e 0a 0a  ude <string.h>..
03d0: 23 69 6e 63 6c 75 64 65 20 22 73 71 6c 69 74 65  #include "sqlite
03e0: 33 2e 68 22 0a 23 69 6e 63 6c 75 64 65 20 22 66  3.h".#include "f
03f0: 74 73 33 5f 68 61 73 68 2e 68 22 0a 0a 2f 2a 0a  ts3_hash.h"../*.
0400: 2a 2a 20 4d 61 6c 6c 6f 63 20 61 6e 64 20 46 72  ** Malloc and Fr
0410: 65 65 20 66 75 6e 63 74 69 6f 6e 73 0a 2a 2f 0a  ee functions.*/.
0420: 73 74 61 74 69 63 20 76 6f 69 64 20 2a 66 74 73  static void *fts
0430: 33 48 61 73 68 4d 61 6c 6c 6f 63 28 69 6e 74 20  3HashMalloc(int 
0440: 6e 29 7b 0a 20 20 76 6f 69 64 20 2a 70 20 3d 20  n){.  void *p = 
0450: 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e  sqlite3_malloc(n
0460: 29 3b 0a 20 20 69 66 28 20 70 20 29 7b 0a 20 20  );.  if( p ){.  
0470: 20 20 6d 65 6d 73 65 74 28 70 2c 20 30 2c 20 6e    memset(p, 0, n
0480: 29 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20  );.  }.  return 
0490: 70 3b 0a 7d 0a 73 74 61 74 69 63 20 76 6f 69 64  p;.}.static void
04a0: 20 66 74 73 33 48 61 73 68 46 72 65 65 28 76 6f   fts3HashFree(vo
04b0: 69 64 20 2a 70 29 7b 0a 20 20 73 71 6c 69 74 65  id *p){.  sqlite
04c0: 33 5f 66 72 65 65 28 70 29 3b 0a 7d 0a 0a 2f 2a  3_free(p);.}../*
04d0: 20 54 75 72 6e 20 62 75 6c 6b 20 6d 65 6d 6f 72   Turn bulk memor
04e0: 79 20 69 6e 74 6f 20 61 20 68 61 73 68 20 74 61  y into a hash ta
04f0: 62 6c 65 20 6f 62 6a 65 63 74 20 62 79 20 69 6e  ble object by in
0500: 69 74 69 61 6c 69 7a 69 6e 67 20 74 68 65 0a 2a  itializing the.*
0510: 2a 20 66 69 65 6c 64 73 20 6f 66 20 74 68 65 20  * fields of the 
0520: 48 61 73 68 20 73 74 72 75 63 74 75 72 65 2e 0a  Hash structure..
0530: 2a 2a 0a 2a 2a 20 22 70 4e 65 77 22 20 69 73 20  **.** "pNew" is 
0540: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65  a pointer to the
0550: 20 68 61 73 68 20 74 61 62 6c 65 20 74 68 61 74   hash table that
0560: 20 69 73 20 74 6f 20 62 65 20 69 6e 69 74 69 61   is to be initia
0570: 6c 69 7a 65 64 2e 0a 2a 2a 20 6b 65 79 43 6c 61  lized..** keyCla
0580: 73 73 20 69 73 20 6f 6e 65 20 6f 66 20 74 68 65  ss is one of the
0590: 20 63 6f 6e 73 74 61 6e 74 73 20 0a 2a 2a 20 46   constants .** F
05a0: 54 53 33 5f 48 41 53 48 5f 42 49 4e 41 52 59 20  TS3_HASH_BINARY 
05b0: 6f 72 20 46 54 53 33 5f 48 41 53 48 5f 53 54 52  or FTS3_HASH_STR
05c0: 49 4e 47 2e 20 20 54 68 65 20 76 61 6c 75 65 20  ING.  The value 
05d0: 6f 66 20 6b 65 79 43 6c 61 73 73 20 0a 2a 2a 20  of keyClass .** 
05e0: 64 65 74 65 72 6d 69 6e 65 73 20 77 68 61 74 20  determines what 
05f0: 6b 69 6e 64 20 6f 66 20 6b 65 79 20 74 68 65 20  kind of key the 
0600: 68 61 73 68 20 74 61 62 6c 65 20 77 69 6c 6c 20  hash table will 
0610: 75 73 65 2e 20 20 22 63 6f 70 79 4b 65 79 22 20  use.  "copyKey" 
0620: 69 73 0a 2a 2a 20 74 72 75 65 20 69 66 20 74 68  is.** true if th
0630: 65 20 68 61 73 68 20 74 61 62 6c 65 20 73 68 6f  e hash table sho
0640: 75 6c 64 20 6d 61 6b 65 20 69 74 73 20 6f 77 6e  uld make its own
0650: 20 70 72 69 76 61 74 65 20 63 6f 70 79 20 6f 66   private copy of
0660: 20 6b 65 79 73 20 61 6e 64 0a 2a 2a 20 66 61 6c   keys and.** fal
0670: 73 65 20 69 66 20 69 74 20 73 68 6f 75 6c 64 20  se if it should 
0680: 6a 75 73 74 20 75 73 65 20 74 68 65 20 73 75 70  just use the sup
0690: 70 6c 69 65 64 20 70 6f 69 6e 74 65 72 2e 0a 2a  plied pointer..*
06a0: 2f 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 46 74  /.void sqlite3Ft
06b0: 73 33 48 61 73 68 49 6e 69 74 28 66 74 73 33 48  s3HashInit(fts3H
06c0: 61 73 68 20 2a 70 4e 65 77 2c 20 69 6e 74 20 6b  ash *pNew, int k
06d0: 65 79 43 6c 61 73 73 2c 20 69 6e 74 20 63 6f 70  eyClass, int cop
06e0: 79 4b 65 79 29 7b 0a 20 20 61 73 73 65 72 74 28  yKey){.  assert(
06f0: 20 70 4e 65 77 21 3d 30 20 29 3b 0a 20 20 61 73   pNew!=0 );.  as
0700: 73 65 72 74 28 20 6b 65 79 43 6c 61 73 73 3e 3d  sert( keyClass>=
0710: 46 54 53 33 5f 48 41 53 48 5f 53 54 52 49 4e 47  FTS3_HASH_STRING
0720: 20 26 26 20 6b 65 79 43 6c 61 73 73 3c 3d 46 54   && keyClass<=FT
0730: 53 33 5f 48 41 53 48 5f 42 49 4e 41 52 59 20 29  S3_HASH_BINARY )
0740: 3b 0a 20 20 70 4e 65 77 2d 3e 6b 65 79 43 6c 61  ;.  pNew->keyCla
0750: 73 73 20 3d 20 6b 65 79 43 6c 61 73 73 3b 0a 20  ss = keyClass;. 
0760: 20 70 4e 65 77 2d 3e 63 6f 70 79 4b 65 79 20 3d   pNew->copyKey =
0770: 20 63 6f 70 79 4b 65 79 3b 0a 20 20 70 4e 65 77   copyKey;.  pNew
0780: 2d 3e 66 69 72 73 74 20 3d 20 30 3b 0a 20 20 70  ->first = 0;.  p
0790: 4e 65 77 2d 3e 63 6f 75 6e 74 20 3d 20 30 3b 0a  New->count = 0;.
07a0: 20 20 70 4e 65 77 2d 3e 68 74 73 69 7a 65 20 3d    pNew->htsize =
07b0: 20 30 3b 0a 20 20 70 4e 65 77 2d 3e 68 74 20 3d   0;.  pNew->ht =
07c0: 20 30 3b 0a 7d 0a 0a 2f 2a 20 52 65 6d 6f 76 65   0;.}../* Remove
07d0: 20 61 6c 6c 20 65 6e 74 72 69 65 73 20 66 72 6f   all entries fro
07e0: 6d 20 61 20 68 61 73 68 20 74 61 62 6c 65 2e 20  m a hash table. 
07f0: 20 52 65 63 6c 61 69 6d 20 61 6c 6c 20 6d 65 6d   Reclaim all mem
0800: 6f 72 79 2e 0a 2a 2a 20 43 61 6c 6c 20 74 68 69  ory..** Call thi
0810: 73 20 72 6f 75 74 69 6e 65 20 74 6f 20 64 65 6c  s routine to del
0820: 65 74 65 20 61 20 68 61 73 68 20 74 61 62 6c 65  ete a hash table
0830: 20 6f 72 20 74 6f 20 72 65 73 65 74 20 61 20 68   or to reset a h
0840: 61 73 68 20 74 61 62 6c 65 0a 2a 2a 20 74 6f 20  ash table.** to 
0850: 74 68 65 20 65 6d 70 74 79 20 73 74 61 74 65 2e  the empty state.
0860: 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74 65 33  .*/.void sqlite3
0870: 46 74 73 33 48 61 73 68 43 6c 65 61 72 28 66 74  Fts3HashClear(ft
0880: 73 33 48 61 73 68 20 2a 70 48 29 7b 0a 20 20 66  s3Hash *pH){.  f
0890: 74 73 33 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65  ts3HashElem *ele
08a0: 6d 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 46 6f  m;         /* Fo
08b0: 72 20 6c 6f 6f 70 69 6e 67 20 6f 76 65 72 20 61  r looping over a
08c0: 6c 6c 20 65 6c 65 6d 65 6e 74 73 20 6f 66 20 74  ll elements of t
08d0: 68 65 20 74 61 62 6c 65 20 2a 2f 0a 0a 20 20 61  he table */..  a
08e0: 73 73 65 72 74 28 20 70 48 21 3d 30 20 29 3b 0a  ssert( pH!=0 );.
08f0: 20 20 65 6c 65 6d 20 3d 20 70 48 2d 3e 66 69 72    elem = pH->fir
0900: 73 74 3b 0a 20 20 70 48 2d 3e 66 69 72 73 74 20  st;.  pH->first 
0910: 3d 20 30 3b 0a 20 20 66 74 73 33 48 61 73 68 46  = 0;.  fts3HashF
0920: 72 65 65 28 70 48 2d 3e 68 74 29 3b 0a 20 20 70  ree(pH->ht);.  p
0930: 48 2d 3e 68 74 20 3d 20 30 3b 0a 20 20 70 48 2d  H->ht = 0;.  pH-
0940: 3e 68 74 73 69 7a 65 20 3d 20 30 3b 0a 20 20 77  >htsize = 0;.  w
0950: 68 69 6c 65 28 20 65 6c 65 6d 20 29 7b 0a 20 20  hile( elem ){.  
0960: 20 20 66 74 73 33 48 61 73 68 45 6c 65 6d 20 2a    fts3HashElem *
0970: 6e 65 78 74 5f 65 6c 65 6d 20 3d 20 65 6c 65 6d  next_elem = elem
0980: 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 69 66 28 20  ->next;.    if( 
0990: 70 48 2d 3e 63 6f 70 79 4b 65 79 20 26 26 20 65  pH->copyKey && e
09a0: 6c 65 6d 2d 3e 70 4b 65 79 20 29 7b 0a 20 20 20  lem->pKey ){.   
09b0: 20 20 20 66 74 73 33 48 61 73 68 46 72 65 65 28     fts3HashFree(
09c0: 65 6c 65 6d 2d 3e 70 4b 65 79 29 3b 0a 20 20 20  elem->pKey);.   
09d0: 20 7d 0a 20 20 20 20 66 74 73 33 48 61 73 68 46   }.    fts3HashF
09e0: 72 65 65 28 65 6c 65 6d 29 3b 0a 20 20 20 20 65  ree(elem);.    e
09f0: 6c 65 6d 20 3d 20 6e 65 78 74 5f 65 6c 65 6d 3b  lem = next_elem;
0a00: 0a 20 20 7d 0a 20 20 70 48 2d 3e 63 6f 75 6e 74  .  }.  pH->count
0a10: 20 3d 20 30 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 48   = 0;.}../*.** H
0a20: 61 73 68 20 61 6e 64 20 63 6f 6d 70 61 72 69 73  ash and comparis
0a30: 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 20 77 68 65  on functions whe
0a40: 6e 20 74 68 65 20 6d 6f 64 65 20 69 73 20 46 54  n the mode is FT
0a50: 53 33 5f 48 41 53 48 5f 53 54 52 49 4e 47 0a 2a  S3_HASH_STRING.*
0a60: 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 66 74 73  /.static int fts
0a70: 33 53 74 72 48 61 73 68 28 63 6f 6e 73 74 20 76  3StrHash(const v
0a80: 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e  oid *pKey, int n
0a90: 4b 65 79 29 7b 0a 20 20 63 6f 6e 73 74 20 63 68  Key){.  const ch
0aa0: 61 72 20 2a 7a 20 3d 20 28 63 6f 6e 73 74 20 63  ar *z = (const c
0ab0: 68 61 72 20 2a 29 70 4b 65 79 3b 0a 20 20 69 6e  har *)pKey;.  in
0ac0: 74 20 68 20 3d 20 30 3b 0a 20 20 69 66 28 20 6e  t h = 0;.  if( n
0ad0: 4b 65 79 3c 3d 30 20 29 20 6e 4b 65 79 20 3d 20  Key<=0 ) nKey = 
0ae0: 28 69 6e 74 29 20 73 74 72 6c 65 6e 28 7a 29 3b  (int) strlen(z);
0af0: 0a 20 20 77 68 69 6c 65 28 20 6e 4b 65 79 20 3e  .  while( nKey >
0b00: 20 30 20 20 29 7b 0a 20 20 20 20 68 20 3d 20 28   0  ){.    h = (
0b10: 68 3c 3c 33 29 20 5e 20 68 20 5e 20 2a 7a 2b 2b  h<<3) ^ h ^ *z++
0b20: 3b 0a 20 20 20 20 6e 4b 65 79 2d 2d 3b 0a 20 20  ;.    nKey--;.  
0b30: 7d 0a 20 20 72 65 74 75 72 6e 20 68 20 26 20 30  }.  return h & 0
0b40: 78 37 66 66 66 66 66 66 66 3b 0a 7d 0a 73 74 61  x7fffffff;.}.sta
0b50: 74 69 63 20 69 6e 74 20 66 74 73 33 53 74 72 43  tic int fts3StrC
0b60: 6f 6d 70 61 72 65 28 63 6f 6e 73 74 20 76 6f 69  ompare(const voi
0b70: 64 20 2a 70 4b 65 79 31 2c 20 69 6e 74 20 6e 31  d *pKey1, int n1
0b80: 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b  , const void *pK
0b90: 65 79 32 2c 20 69 6e 74 20 6e 32 29 7b 0a 20 20  ey2, int n2){.  
0ba0: 69 66 28 20 6e 31 21 3d 6e 32 20 29 20 72 65 74  if( n1!=n2 ) ret
0bb0: 75 72 6e 20 31 3b 0a 20 20 72 65 74 75 72 6e 20  urn 1;.  return 
0bc0: 73 74 72 6e 63 6d 70 28 28 63 6f 6e 73 74 20 63  strncmp((const c
0bd0: 68 61 72 2a 29 70 4b 65 79 31 2c 28 63 6f 6e 73  har*)pKey1,(cons
0be0: 74 20 63 68 61 72 2a 29 70 4b 65 79 32 2c 6e 31  t char*)pKey2,n1
0bf0: 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 48 61 73 68  );.}../*.** Hash
0c00: 20 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e 20   and comparison 
0c10: 66 75 6e 63 74 69 6f 6e 73 20 77 68 65 6e 20 74  functions when t
0c20: 68 65 20 6d 6f 64 65 20 69 73 20 46 54 53 33 5f  he mode is FTS3_
0c30: 48 41 53 48 5f 42 49 4e 41 52 59 0a 2a 2f 0a 73  HASH_BINARY.*/.s
0c40: 74 61 74 69 63 20 69 6e 74 20 66 74 73 33 42 69  tatic int fts3Bi
0c50: 6e 48 61 73 68 28 63 6f 6e 73 74 20 76 6f 69 64  nHash(const void
0c60: 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79   *pKey, int nKey
0c70: 29 7b 0a 20 20 69 6e 74 20 68 20 3d 20 30 3b 0a  ){.  int h = 0;.
0c80: 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a 20    const char *z 
0c90: 3d 20 28 63 6f 6e 73 74 20 63 68 61 72 20 2a 29  = (const char *)
0ca0: 70 4b 65 79 3b 0a 20 20 77 68 69 6c 65 28 20 6e  pKey;.  while( n
0cb0: 4b 65 79 2d 2d 20 3e 20 30 20 29 7b 0a 20 20 20  Key-- > 0 ){.   
0cc0: 20 68 20 3d 20 28 68 3c 3c 33 29 20 5e 20 68 20   h = (h<<3) ^ h 
0cd0: 5e 20 2a 28 7a 2b 2b 29 3b 0a 20 20 7d 0a 20 20  ^ *(z++);.  }.  
0ce0: 72 65 74 75 72 6e 20 68 20 26 20 30 78 37 66 66  return h & 0x7ff
0cf0: 66 66 66 66 66 3b 0a 7d 0a 73 74 61 74 69 63 20  fffff;.}.static 
0d00: 69 6e 74 20 66 74 73 33 42 69 6e 43 6f 6d 70 61  int fts3BinCompa
0d10: 72 65 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70  re(const void *p
0d20: 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c 20 63 6f  Key1, int n1, co
0d30: 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 32 2c  nst void *pKey2,
0d40: 20 69 6e 74 20 6e 32 29 7b 0a 20 20 69 66 28 20   int n2){.  if( 
0d50: 6e 31 21 3d 6e 32 20 29 20 72 65 74 75 72 6e 20  n1!=n2 ) return 
0d60: 31 3b 0a 20 20 72 65 74 75 72 6e 20 6d 65 6d 63  1;.  return memc
0d70: 6d 70 28 70 4b 65 79 31 2c 70 4b 65 79 32 2c 6e  mp(pKey1,pKey2,n
0d80: 31 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 74  1);.}../*.** Ret
0d90: 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f  urn a pointer to
0da0: 20 74 68 65 20 61 70 70 72 6f 70 72 69 61 74 65   the appropriate
0db0: 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 67   hash function g
0dc0: 69 76 65 6e 20 74 68 65 20 6b 65 79 20 63 6c 61  iven the key cla
0dd0: 73 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 43 20  ss..**.** The C 
0de0: 73 79 6e 74 61 78 20 69 6e 20 74 68 69 73 20 66  syntax in this f
0df0: 75 6e 63 74 69 6f 6e 20 64 65 66 69 6e 69 74 69  unction definiti
0e00: 6f 6e 20 6d 61 79 20 62 65 20 75 6e 66 61 6d 69  on may be unfami
0e10: 6c 61 72 20 74 6f 20 73 6f 6d 65 20 0a 2a 2a 20  lar to some .** 
0e20: 70 72 6f 67 72 61 6d 6d 65 72 73 2c 20 73 6f 20  programmers, so 
0e30: 77 65 20 70 72 6f 76 69 64 65 20 74 68 65 20 66  we provide the f
0e40: 6f 6c 6c 6f 77 69 6e 67 20 61 64 64 69 74 69 6f  ollowing additio
0e50: 6e 61 6c 20 65 78 70 6c 61 6e 61 74 69 6f 6e 3a  nal explanation:
0e60: 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6e 61 6d 65 20  .**.** The name 
0e70: 6f 66 20 74 68 65 20 66 75 6e 63 74 69 6f 6e 20  of the function 
0e80: 69 73 20 22 66 74 73 48 61 73 68 46 75 6e 63 74  is "ftsHashFunct
0e90: 69 6f 6e 22 2e 20 20 54 68 65 20 66 75 6e 63 74  ion".  The funct
0ea0: 69 6f 6e 20 74 61 6b 65 73 20 61 0a 2a 2a 20 73  ion takes a.** s
0eb0: 69 6e 67 6c 65 20 70 61 72 61 6d 65 74 65 72 20  ingle parameter 
0ec0: 22 6b 65 79 43 6c 61 73 73 22 2e 20 20 54 68 65  "keyClass".  The
0ed0: 20 72 65 74 75 72 6e 20 76 61 6c 75 65 20 6f 66   return value of
0ee0: 20 66 74 73 48 61 73 68 46 75 6e 63 74 69 6f 6e   ftsHashFunction
0ef0: 28 29 0a 2a 2a 20 69 73 20 61 20 70 6f 69 6e 74  ().** is a point
0f00: 65 72 20 74 6f 20 61 6e 6f 74 68 65 72 20 66 75  er to another fu
0f10: 6e 63 74 69 6f 6e 2e 20 20 53 70 65 63 69 66 69  nction.  Specifi
0f20: 63 61 6c 6c 79 2c 20 74 68 65 20 72 65 74 75 72  cally, the retur
0f30: 6e 20 76 61 6c 75 65 0a 2a 2a 20 6f 66 20 66 74  n value.** of ft
0f40: 73 48 61 73 68 46 75 6e 63 74 69 6f 6e 28 29 20  sHashFunction() 
0f50: 69 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20  is a pointer to 
0f60: 61 20 66 75 6e 63 74 69 6f 6e 20 74 68 61 74 20  a function that 
0f70: 74 61 6b 65 73 20 74 77 6f 20 70 61 72 61 6d 65  takes two parame
0f80: 74 65 72 73 0a 2a 2a 20 77 69 74 68 20 74 79 70  ters.** with typ
0f90: 65 73 20 22 63 6f 6e 73 74 20 76 6f 69 64 2a 22  es "const void*"
0fa0: 20 61 6e 64 20 22 69 6e 74 22 20 61 6e 64 20 72   and "int" and r
0fb0: 65 74 75 72 6e 73 20 61 6e 20 22 69 6e 74 22 2e  eturns an "int".
0fc0: 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 28  .*/.static int (
0fd0: 2a 66 74 73 48 61 73 68 46 75 6e 63 74 69 6f 6e  *ftsHashFunction
0fe0: 28 69 6e 74 20 6b 65 79 43 6c 61 73 73 29 29 28  (int keyClass))(
0ff0: 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29  const void*,int)
1000: 7b 0a 20 20 69 66 28 20 6b 65 79 43 6c 61 73 73  {.  if( keyClass
1010: 3d 3d 46 54 53 33 5f 48 41 53 48 5f 53 54 52 49  ==FTS3_HASH_STRI
1020: 4e 47 20 29 7b 0a 20 20 20 20 72 65 74 75 72 6e  NG ){.    return
1030: 20 26 66 74 73 33 53 74 72 48 61 73 68 3b 0a 20   &fts3StrHash;. 
1040: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 61 73 73 65   }else{.    asse
1050: 72 74 28 20 6b 65 79 43 6c 61 73 73 3d 3d 46 54  rt( keyClass==FT
1060: 53 33 5f 48 41 53 48 5f 42 49 4e 41 52 59 20 29  S3_HASH_BINARY )
1070: 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 26 66 74  ;.    return &ft
1080: 73 33 42 69 6e 48 61 73 68 3b 0a 20 20 7d 0a 7d  s3BinHash;.  }.}
1090: 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 61  ../*.** Return a
10a0: 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 20   pointer to the 
10b0: 61 70 70 72 6f 70 72 69 61 74 65 20 68 61 73 68  appropriate hash
10c0: 20 66 75 6e 63 74 69 6f 6e 20 67 69 76 65 6e 20   function given 
10d0: 74 68 65 20 6b 65 79 20 63 6c 61 73 73 2e 0a 2a  the key class..*
10e0: 2a 0a 2a 2a 20 46 6f 72 20 68 65 6c 70 20 69 6e  *.** For help in
10f0: 20 69 6e 74 65 72 70 72 65 74 65 64 20 74 68 65   interpreted the
1100: 20 6f 62 73 63 75 72 65 20 43 20 63 6f 64 65 20   obscure C code 
1110: 69 6e 20 74 68 65 20 66 75 6e 63 74 69 6f 6e 20  in the function 
1120: 64 65 66 69 6e 69 74 69 6f 6e 2c 0a 2a 2a 20 73  definition,.** s
1130: 65 65 20 74 68 65 20 68 65 61 64 65 72 20 63 6f  ee the header co
1140: 6d 6d 65 6e 74 20 6f 6e 20 74 68 65 20 70 72 65  mment on the pre
1150: 76 69 6f 75 73 20 66 75 6e 63 74 69 6f 6e 2e 0a  vious function..
1160: 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 28 2a  */.static int (*
1170: 66 74 73 43 6f 6d 70 61 72 65 46 75 6e 63 74 69  ftsCompareFuncti
1180: 6f 6e 28 69 6e 74 20 6b 65 79 43 6c 61 73 73 29  on(int keyClass)
1190: 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e  )(const void*,in
11a0: 74 2c 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e  t,const void*,in
11b0: 74 29 7b 0a 20 20 69 66 28 20 6b 65 79 43 6c 61  t){.  if( keyCla
11c0: 73 73 3d 3d 46 54 53 33 5f 48 41 53 48 5f 53 54  ss==FTS3_HASH_ST
11d0: 52 49 4e 47 20 29 7b 0a 20 20 20 20 72 65 74 75  RING ){.    retu
11e0: 72 6e 20 26 66 74 73 33 53 74 72 43 6f 6d 70 61  rn &fts3StrCompa
11f0: 72 65 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20  re;.  }else{.   
1200: 20 61 73 73 65 72 74 28 20 6b 65 79 43 6c 61 73   assert( keyClas
1210: 73 3d 3d 46 54 53 33 5f 48 41 53 48 5f 42 49 4e  s==FTS3_HASH_BIN
1220: 41 52 59 20 29 3b 0a 20 20 20 20 72 65 74 75 72  ARY );.    retur
1230: 6e 20 26 66 74 73 33 42 69 6e 43 6f 6d 70 61 72  n &fts3BinCompar
1240: 65 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 20 4c 69 6e  e;.  }.}../* Lin
1250: 6b 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69 6e 74  k an element int
1260: 6f 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65  o the hash table
1270: 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20  .*/.static void 
1280: 66 74 73 33 48 61 73 68 49 6e 73 65 72 74 45 6c  fts3HashInsertEl
1290: 65 6d 65 6e 74 28 0a 20 20 66 74 73 33 48 61 73  ement(.  fts3Has
12a0: 68 20 2a 70 48 2c 20 20 20 20 20 20 20 20 20 20  h *pH,          
12b0: 20 20 2f 2a 20 54 68 65 20 63 6f 6d 70 6c 65 74    /* The complet
12c0: 65 20 68 61 73 68 20 74 61 62 6c 65 20 2a 2f 0a  e hash table */.
12d0: 20 20 73 74 72 75 63 74 20 5f 66 74 73 33 68 74    struct _fts3ht
12e0: 20 2a 70 45 6e 74 72 79 2c 20 20 2f 2a 20 54 68   *pEntry,  /* Th
12f0: 65 20 65 6e 74 72 79 20 69 6e 74 6f 20 77 68 69  e entry into whi
1300: 63 68 20 70 4e 65 77 20 69 73 20 69 6e 73 65 72  ch pNew is inser
1310: 74 65 64 20 2a 2f 0a 20 20 66 74 73 33 48 61 73  ted */.  fts3Has
1320: 68 45 6c 65 6d 20 2a 70 4e 65 77 20 20 20 20 20  hElem *pNew     
1330: 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e 74    /* The element
1340: 20 74 6f 20 62 65 20 69 6e 73 65 72 74 65 64 20   to be inserted 
1350: 2a 2f 0a 29 7b 0a 20 20 66 74 73 33 48 61 73 68  */.){.  fts3Hash
1360: 45 6c 65 6d 20 2a 70 48 65 61 64 3b 20 20 20 20  Elem *pHead;    
1370: 20 2f 2a 20 46 69 72 73 74 20 65 6c 65 6d 65 6e   /* First elemen
1380: 74 20 61 6c 72 65 61 64 79 20 69 6e 20 70 45 6e  t already in pEn
1390: 74 72 79 20 2a 2f 0a 20 20 70 48 65 61 64 20 3d  try */.  pHead =
13a0: 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3b 0a   pEntry->chain;.
13b0: 20 20 69 66 28 20 70 48 65 61 64 20 29 7b 0a 20    if( pHead ){. 
13c0: 20 20 20 70 4e 65 77 2d 3e 6e 65 78 74 20 3d 20     pNew->next = 
13d0: 70 48 65 61 64 3b 0a 20 20 20 20 70 4e 65 77 2d  pHead;.    pNew-
13e0: 3e 70 72 65 76 20 3d 20 70 48 65 61 64 2d 3e 70  >prev = pHead->p
13f0: 72 65 76 3b 0a 20 20 20 20 69 66 28 20 70 48 65  rev;.    if( pHe
1400: 61 64 2d 3e 70 72 65 76 20 29 7b 20 70 48 65 61  ad->prev ){ pHea
1410: 64 2d 3e 70 72 65 76 2d 3e 6e 65 78 74 20 3d 20  d->prev->next = 
1420: 70 4e 65 77 3b 20 7d 0a 20 20 20 20 65 6c 73 65  pNew; }.    else
1430: 20 20 20 20 20 20 20 20 20 20 20 20 20 7b 20 70               { p
1440: 48 2d 3e 66 69 72 73 74 20 3d 20 70 4e 65 77 3b  H->first = pNew;
1450: 20 7d 0a 20 20 20 20 70 48 65 61 64 2d 3e 70 72   }.    pHead->pr
1460: 65 76 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 65 6c  ev = pNew;.  }el
1470: 73 65 7b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 65  se{.    pNew->ne
1480: 78 74 20 3d 20 70 48 2d 3e 66 69 72 73 74 3b 0a  xt = pH->first;.
1490: 20 20 20 20 69 66 28 20 70 48 2d 3e 66 69 72 73      if( pH->firs
14a0: 74 20 29 7b 20 70 48 2d 3e 66 69 72 73 74 2d 3e  t ){ pH->first->
14b0: 70 72 65 76 20 3d 20 70 4e 65 77 3b 20 7d 0a 20  prev = pNew; }. 
14c0: 20 20 20 70 4e 65 77 2d 3e 70 72 65 76 20 3d 20     pNew->prev = 
14d0: 30 3b 0a 20 20 20 20 70 48 2d 3e 66 69 72 73 74  0;.    pH->first
14e0: 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 0a 20 20 70   = pNew;.  }.  p
14f0: 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a  Entry->count++;.
1500: 20 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 20    pEntry->chain 
1510: 3d 20 70 4e 65 77 3b 0a 7d 0a 0a 0a 2f 2a 20 52  = pNew;.}.../* R
1520: 65 73 69 7a 65 20 74 68 65 20 68 61 73 68 20 74  esize the hash t
1530: 61 62 6c 65 20 73 6f 20 74 68 61 74 20 69 74 20  able so that it 
1540: 63 61 6e 74 61 69 6e 73 20 22 6e 65 77 5f 73 69  cantains "new_si
1550: 7a 65 22 20 62 75 63 6b 65 74 73 2e 0a 2a 2a 20  ze" buckets..** 
1560: 22 6e 65 77 5f 73 69 7a 65 22 20 6d 75 73 74 20  "new_size" must 
1570: 62 65 20 61 20 70 6f 77 65 72 20 6f 66 20 32 2e  be a power of 2.
1580: 20 20 54 68 65 20 68 61 73 68 20 74 61 62 6c 65    The hash table
1590: 20 6d 69 67 68 74 20 66 61 69 6c 20 0a 2a 2a 20   might fail .** 
15a0: 74 6f 20 72 65 73 69 7a 65 20 69 66 20 73 71 6c  to resize if sql
15b0: 69 74 65 4d 61 6c 6c 6f 63 28 29 20 66 61 69 6c  iteMalloc() fail
15c0: 73 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69  s..*/.static voi
15d0: 64 20 66 74 73 33 52 65 68 61 73 68 28 66 74 73  d fts3Rehash(fts
15e0: 33 48 61 73 68 20 2a 70 48 2c 20 69 6e 74 20 6e  3Hash *pH, int n
15f0: 65 77 5f 73 69 7a 65 29 7b 0a 20 20 73 74 72 75  ew_size){.  stru
1600: 63 74 20 5f 66 74 73 33 68 74 20 2a 6e 65 77 5f  ct _fts3ht *new_
1610: 68 74 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20  ht;          /* 
1620: 54 68 65 20 6e 65 77 20 68 61 73 68 20 74 61 62  The new hash tab
1630: 6c 65 20 2a 2f 0a 20 20 66 74 73 33 48 61 73 68  le */.  fts3Hash
1640: 45 6c 65 6d 20 2a 65 6c 65 6d 2c 20 2a 6e 65 78  Elem *elem, *nex
1650: 74 5f 65 6c 65 6d 3b 20 20 2f 2a 20 46 6f 72 20  t_elem;  /* For 
1660: 6c 6f 6f 70 69 6e 67 20 6f 76 65 72 20 65 78 69  looping over exi
1670: 73 74 69 6e 67 20 65 6c 65 6d 65 6e 74 73 20 2a  sting elements *
1680: 2f 0a 20 20 69 6e 74 20 28 2a 78 48 61 73 68 29  /.  int (*xHash)
1690: 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74  (const void*,int
16a0: 29 3b 20 20 20 2f 2a 20 54 68 65 20 68 61 73 68  );   /* The hash
16b0: 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20   function */..  
16c0: 61 73 73 65 72 74 28 20 28 6e 65 77 5f 73 69 7a  assert( (new_siz
16d0: 65 20 26 20 28 6e 65 77 5f 73 69 7a 65 2d 31 29  e & (new_size-1)
16e0: 29 3d 3d 30 20 29 3b 0a 20 20 6e 65 77 5f 68 74  )==0 );.  new_ht
16f0: 20 3d 20 28 73 74 72 75 63 74 20 5f 66 74 73 33   = (struct _fts3
1700: 68 74 20 2a 29 66 74 73 33 48 61 73 68 4d 61 6c  ht *)fts3HashMal
1710: 6c 6f 63 28 20 6e 65 77 5f 73 69 7a 65 2a 73 69  loc( new_size*si
1720: 7a 65 6f 66 28 73 74 72 75 63 74 20 5f 66 74 73  zeof(struct _fts
1730: 33 68 74 29 20 29 3b 0a 20 20 69 66 28 20 6e 65  3ht) );.  if( ne
1740: 77 5f 68 74 3d 3d 30 20 29 20 72 65 74 75 72 6e  w_ht==0 ) return
1750: 3b 0a 20 20 66 74 73 33 48 61 73 68 46 72 65 65  ;.  fts3HashFree
1760: 28 70 48 2d 3e 68 74 29 3b 0a 20 20 70 48 2d 3e  (pH->ht);.  pH->
1770: 68 74 20 3d 20 6e 65 77 5f 68 74 3b 0a 20 20 70  ht = new_ht;.  p
1780: 48 2d 3e 68 74 73 69 7a 65 20 3d 20 6e 65 77 5f  H->htsize = new_
1790: 73 69 7a 65 3b 0a 20 20 78 48 61 73 68 20 3d 20  size;.  xHash = 
17a0: 66 74 73 48 61 73 68 46 75 6e 63 74 69 6f 6e 28  ftsHashFunction(
17b0: 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20  pH->keyClass);. 
17c0: 20 66 6f 72 28 65 6c 65 6d 3d 70 48 2d 3e 66 69   for(elem=pH->fi
17d0: 72 73 74 2c 20 70 48 2d 3e 66 69 72 73 74 3d 30  rst, pH->first=0
17e0: 3b 20 65 6c 65 6d 3b 20 65 6c 65 6d 20 3d 20 6e  ; elem; elem = n
17f0: 65 78 74 5f 65 6c 65 6d 29 7b 0a 20 20 20 20 69  ext_elem){.    i
1800: 6e 74 20 68 20 3d 20 28 2a 78 48 61 73 68 29 28  nt h = (*xHash)(
1810: 65 6c 65 6d 2d 3e 70 4b 65 79 2c 20 65 6c 65 6d  elem->pKey, elem
1820: 2d 3e 6e 4b 65 79 29 20 26 20 28 6e 65 77 5f 73  ->nKey) & (new_s
1830: 69 7a 65 2d 31 29 3b 0a 20 20 20 20 6e 65 78 74  ize-1);.    next
1840: 5f 65 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65  _elem = elem->ne
1850: 78 74 3b 0a 20 20 20 20 66 74 73 33 48 61 73 68  xt;.    fts3Hash
1860: 49 6e 73 65 72 74 45 6c 65 6d 65 6e 74 28 70 48  InsertElement(pH
1870: 2c 20 26 6e 65 77 5f 68 74 5b 68 5d 2c 20 65 6c  , &new_ht[h], el
1880: 65 6d 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 20 54  em);.  }.}../* T
1890: 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 28 66 6f  his function (fo
18a0: 72 20 69 6e 74 65 72 6e 61 6c 20 75 73 65 20 6f  r internal use o
18b0: 6e 6c 79 29 20 6c 6f 63 61 74 65 73 20 61 6e 20  nly) locates an 
18c0: 65 6c 65 6d 65 6e 74 20 69 6e 20 61 6e 0a 2a 2a  element in an.**
18d0: 20 68 61 73 68 20 74 61 62 6c 65 20 74 68 61 74   hash table that
18e0: 20 6d 61 74 63 68 65 73 20 74 68 65 20 67 69 76   matches the giv
18f0: 65 6e 20 6b 65 79 2e 20 20 54 68 65 20 68 61 73  en key.  The has
1900: 68 20 66 6f 72 20 74 68 69 73 20 6b 65 79 20 68  h for this key h
1910: 61 73 0a 2a 2a 20 61 6c 72 65 61 64 79 20 62 65  as.** already be
1920: 65 6e 20 63 6f 6d 70 75 74 65 64 20 61 6e 64 20  en computed and 
1930: 69 73 20 70 61 73 73 65 64 20 61 73 20 74 68 65  is passed as the
1940: 20 34 74 68 20 70 61 72 61 6d 65 74 65 72 2e 0a   4th parameter..
1950: 2a 2f 0a 73 74 61 74 69 63 20 66 74 73 33 48 61  */.static fts3Ha
1960: 73 68 45 6c 65 6d 20 2a 66 74 73 33 46 69 6e 64  shElem *fts3Find
1970: 45 6c 65 6d 65 6e 74 42 79 48 61 73 68 28 0a 20  ElementByHash(. 
1980: 20 63 6f 6e 73 74 20 66 74 73 33 48 61 73 68 20   const fts3Hash 
1990: 2a 70 48 2c 20 2f 2a 20 54 68 65 20 70 48 20 74  *pH, /* The pH t
19a0: 6f 20 62 65 20 73 65 61 72 63 68 65 64 20 2a 2f  o be searched */
19b0: 0a 20 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70  .  const void *p
19c0: 4b 65 79 2c 20 20 20 2f 2a 20 54 68 65 20 6b 65  Key,   /* The ke
19d0: 79 20 77 65 20 61 72 65 20 73 65 61 72 63 68 69  y we are searchi
19e0: 6e 67 20 66 6f 72 20 2a 2f 0a 20 20 69 6e 74 20  ng for */.  int 
19f0: 6e 4b 65 79 2c 0a 20 20 69 6e 74 20 68 20 20 20  nKey,.  int h   
1a00: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54              /* T
1a10: 68 65 20 68 61 73 68 20 66 6f 72 20 74 68 69 73  he hash for this
1a20: 20 6b 65 79 2e 20 2a 2f 0a 29 7b 0a 20 20 66 74   key. */.){.  ft
1a30: 73 33 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d  s3HashElem *elem
1a40: 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  ;            /* 
1a50: 55 73 65 64 20 74 6f 20 6c 6f 6f 70 20 74 68 72  Used to loop thr
1a60: 75 20 74 68 65 20 65 6c 65 6d 65 6e 74 20 6c 69  u the element li
1a70: 73 74 20 2a 2f 0a 20 20 69 6e 74 20 63 6f 75 6e  st */.  int coun
1a80: 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  t;              
1a90: 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72         /* Number
1aa0: 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20 6c 65 66   of elements lef
1ab0: 74 20 74 6f 20 74 65 73 74 20 2a 2f 0a 20 20 69  t to test */.  i
1ac0: 6e 74 20 28 2a 78 43 6f 6d 70 61 72 65 29 28 63  nt (*xCompare)(c
1ad0: 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 2c 63  onst void*,int,c
1ae0: 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29 3b  onst void*,int);
1af0: 20 20 2f 2a 20 63 6f 6d 70 61 72 69 73 6f 6e 20    /* comparison 
1b00: 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20 69  function */..  i
1b10: 66 28 20 70 48 2d 3e 68 74 20 29 7b 0a 20 20 20  f( pH->ht ){.   
1b20: 20 73 74 72 75 63 74 20 5f 66 74 73 33 68 74 20   struct _fts3ht 
1b30: 2a 70 45 6e 74 72 79 20 3d 20 26 70 48 2d 3e 68  *pEntry = &pH->h
1b40: 74 5b 68 5d 3b 0a 20 20 20 20 65 6c 65 6d 20 3d  t[h];.    elem =
1b50: 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3b 0a   pEntry->chain;.
1b60: 20 20 20 20 63 6f 75 6e 74 20 3d 20 70 45 6e 74      count = pEnt
1b70: 72 79 2d 3e 63 6f 75 6e 74 3b 0a 20 20 20 20 78  ry->count;.    x
1b80: 43 6f 6d 70 61 72 65 20 3d 20 66 74 73 43 6f 6d  Compare = ftsCom
1b90: 70 61 72 65 46 75 6e 63 74 69 6f 6e 28 70 48 2d  pareFunction(pH-
1ba0: 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20 20 20  >keyClass);.    
1bb0: 77 68 69 6c 65 28 20 63 6f 75 6e 74 2d 2d 20 26  while( count-- &
1bc0: 26 20 65 6c 65 6d 20 29 7b 0a 20 20 20 20 20 20  & elem ){.      
1bd0: 69 66 28 20 28 2a 78 43 6f 6d 70 61 72 65 29 28  if( (*xCompare)(
1be0: 65 6c 65 6d 2d 3e 70 4b 65 79 2c 65 6c 65 6d 2d  elem->pKey,elem-
1bf0: 3e 6e 4b 65 79 2c 70 4b 65 79 2c 6e 4b 65 79 29  >nKey,pKey,nKey)
1c00: 3d 3d 30 20 29 7b 20 0a 20 20 20 20 20 20 20 20  ==0 ){ .        
1c10: 72 65 74 75 72 6e 20 65 6c 65 6d 3b 0a 20 20 20  return elem;.   
1c20: 20 20 20 7d 0a 20 20 20 20 20 20 65 6c 65 6d 20     }.      elem 
1c30: 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20  = elem->next;.  
1c40: 20 20 7d 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e    }.  }.  return
1c50: 20 30 3b 0a 7d 0a 0a 2f 2a 20 52 65 6d 6f 76 65   0;.}../* Remove
1c60: 20 61 20 73 69 6e 67 6c 65 20 65 6e 74 72 79 20   a single entry 
1c70: 66 72 6f 6d 20 74 68 65 20 68 61 73 68 20 74 61  from the hash ta
1c80: 62 6c 65 20 67 69 76 65 6e 20 61 20 70 6f 69 6e  ble given a poin
1c90: 74 65 72 20 74 6f 20 74 68 61 74 0a 2a 2a 20 65  ter to that.** e
1ca0: 6c 65 6d 65 6e 74 20 61 6e 64 20 61 20 68 61 73  lement and a has
1cb0: 68 20 6f 6e 20 74 68 65 20 65 6c 65 6d 65 6e 74  h on the element
1cc0: 27 73 20 6b 65 79 2e 0a 2a 2f 0a 73 74 61 74 69  's key..*/.stati
1cd0: 63 20 76 6f 69 64 20 66 74 73 33 52 65 6d 6f 76  c void fts3Remov
1ce0: 65 45 6c 65 6d 65 6e 74 42 79 48 61 73 68 28 0a  eElementByHash(.
1cf0: 20 20 66 74 73 33 48 61 73 68 20 2a 70 48 2c 20    fts3Hash *pH, 
1d00: 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 70          /* The p
1d10: 48 20 63 6f 6e 74 61 69 6e 69 6e 67 20 22 65 6c  H containing "el
1d20: 65 6d 22 20 2a 2f 0a 20 20 66 74 73 33 48 61 73  em" */.  fts3Has
1d30: 68 45 6c 65 6d 2a 20 65 6c 65 6d 2c 20 20 20 2f  hElem* elem,   /
1d40: 2a 20 54 68 65 20 65 6c 65 6d 65 6e 74 20 74 6f  * The element to
1d50: 20 62 65 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d   be removed from
1d60: 20 74 68 65 20 70 48 20 2a 2f 0a 20 20 69 6e 74   the pH */.  int
1d70: 20 68 20 20 20 20 20 20 20 20 20 20 20 20 20 20   h              
1d80: 20 20 20 2f 2a 20 48 61 73 68 20 76 61 6c 75 65     /* Hash value
1d90: 20 66 6f 72 20 74 68 65 20 65 6c 65 6d 65 6e 74   for the element
1da0: 20 2a 2f 0a 29 7b 0a 20 20 73 74 72 75 63 74 20   */.){.  struct 
1db0: 5f 66 74 73 33 68 74 20 2a 70 45 6e 74 72 79 3b  _fts3ht *pEntry;
1dc0: 0a 20 20 69 66 28 20 65 6c 65 6d 2d 3e 70 72 65  .  if( elem->pre
1dd0: 76 20 29 7b 0a 20 20 20 20 65 6c 65 6d 2d 3e 70  v ){.    elem->p
1de0: 72 65 76 2d 3e 6e 65 78 74 20 3d 20 65 6c 65 6d  rev->next = elem
1df0: 2d 3e 6e 65 78 74 3b 20 0a 20 20 7d 65 6c 73 65  ->next; .  }else
1e00: 7b 0a 20 20 20 20 70 48 2d 3e 66 69 72 73 74 20  {.    pH->first 
1e10: 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20  = elem->next;.  
1e20: 7d 0a 20 20 69 66 28 20 65 6c 65 6d 2d 3e 6e 65  }.  if( elem->ne
1e30: 78 74 20 29 7b 0a 20 20 20 20 65 6c 65 6d 2d 3e  xt ){.    elem->
1e40: 6e 65 78 74 2d 3e 70 72 65 76 20 3d 20 65 6c 65  next->prev = ele
1e50: 6d 2d 3e 70 72 65 76 3b 0a 20 20 7d 0a 20 20 70  m->prev;.  }.  p
1e60: 45 6e 74 72 79 20 3d 20 26 70 48 2d 3e 68 74 5b  Entry = &pH->ht[
1e70: 68 5d 3b 0a 20 20 69 66 28 20 70 45 6e 74 72 79  h];.  if( pEntry
1e80: 2d 3e 63 68 61 69 6e 3d 3d 65 6c 65 6d 20 29 7b  ->chain==elem ){
1e90: 0a 20 20 20 20 70 45 6e 74 72 79 2d 3e 63 68 61  .    pEntry->cha
1ea0: 69 6e 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b  in = elem->next;
1eb0: 0a 20 20 7d 0a 20 20 70 45 6e 74 72 79 2d 3e 63  .  }.  pEntry->c
1ec0: 6f 75 6e 74 2d 2d 3b 0a 20 20 69 66 28 20 70 45  ount--;.  if( pE
1ed0: 6e 74 72 79 2d 3e 63 6f 75 6e 74 3c 3d 30 20 29  ntry->count<=0 )
1ee0: 7b 0a 20 20 20 20 70 45 6e 74 72 79 2d 3e 63 68  {.    pEntry->ch
1ef0: 61 69 6e 20 3d 20 30 3b 0a 20 20 7d 0a 20 20 69  ain = 0;.  }.  i
1f00: 66 28 20 70 48 2d 3e 63 6f 70 79 4b 65 79 20 26  f( pH->copyKey &
1f10: 26 20 65 6c 65 6d 2d 3e 70 4b 65 79 20 29 7b 0a  & elem->pKey ){.
1f20: 20 20 20 20 66 74 73 33 48 61 73 68 46 72 65 65      fts3HashFree
1f30: 28 65 6c 65 6d 2d 3e 70 4b 65 79 29 3b 0a 20 20  (elem->pKey);.  
1f40: 7d 0a 20 20 66 74 73 33 48 61 73 68 46 72 65 65  }.  fts3HashFree
1f50: 28 20 65 6c 65 6d 20 29 3b 0a 20 20 70 48 2d 3e  ( elem );.  pH->
1f60: 63 6f 75 6e 74 2d 2d 3b 0a 20 20 69 66 28 20 70  count--;.  if( p
1f70: 48 2d 3e 63 6f 75 6e 74 3c 3d 30 20 29 7b 0a 20  H->count<=0 ){. 
1f80: 20 20 20 61 73 73 65 72 74 28 20 70 48 2d 3e 66     assert( pH->f
1f90: 69 72 73 74 3d 3d 30 20 29 3b 0a 20 20 20 20 61  irst==0 );.    a
1fa0: 73 73 65 72 74 28 20 70 48 2d 3e 63 6f 75 6e 74  ssert( pH->count
1fb0: 3d 3d 30 20 29 3b 0a 20 20 20 20 66 74 73 33 48  ==0 );.    fts3H
1fc0: 61 73 68 43 6c 65 61 72 28 70 48 29 3b 0a 20 20  ashClear(pH);.  
1fd0: 7d 0a 7d 0a 0a 2f 2a 20 41 74 74 65 6d 70 74 20  }.}../* Attempt 
1fe0: 74 6f 20 6c 6f 63 61 74 65 20 61 6e 20 65 6c 65  to locate an ele
1ff0: 6d 65 6e 74 20 6f 66 20 74 68 65 20 68 61 73 68  ment of the hash
2000: 20 74 61 62 6c 65 20 70 48 20 77 69 74 68 20 61   table pH with a
2010: 20 6b 65 79 0a 2a 2a 20 74 68 61 74 20 6d 61 74   key.** that mat
2020: 63 68 65 73 20 70 4b 65 79 2c 6e 4b 65 79 2e 20  ches pKey,nKey. 
2030: 20 52 65 74 75 72 6e 20 74 68 65 20 64 61 74 61   Return the data
2040: 20 66 6f 72 20 74 68 69 73 20 65 6c 65 6d 65 6e   for this elemen
2050: 74 20 69 66 20 69 74 20 69 73 0a 2a 2a 20 66 6f  t if it is.** fo
2060: 75 6e 64 2c 20 6f 72 20 4e 55 4c 4c 20 69 66 20  und, or NULL if 
2070: 74 68 65 72 65 20 69 73 20 6e 6f 20 6d 61 74 63  there is no matc
2080: 68 2e 0a 2a 2f 0a 76 6f 69 64 20 2a 73 71 6c 69  h..*/.void *sqli
2090: 74 65 33 46 74 73 33 48 61 73 68 46 69 6e 64 28  te3Fts3HashFind(
20a0: 63 6f 6e 73 74 20 66 74 73 33 48 61 73 68 20 2a  const fts3Hash *
20b0: 70 48 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a  pH, const void *
20c0: 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b  pKey, int nKey){
20d0: 0a 20 20 69 6e 74 20 68 3b 20 20 20 20 20 20 20  .  int h;       
20e0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41 20 68            /* A h
20f0: 61 73 68 20 6f 6e 20 6b 65 79 20 2a 2f 0a 20 20  ash on key */.  
2100: 66 74 73 33 48 61 73 68 45 6c 65 6d 20 2a 65 6c  fts3HashElem *el
2110: 65 6d 3b 20 20 20 20 2f 2a 20 54 68 65 20 65 6c  em;    /* The el
2120: 65 6d 65 6e 74 20 74 68 61 74 20 6d 61 74 63 68  ement that match
2130: 65 73 20 6b 65 79 20 2a 2f 0a 20 20 69 6e 74 20  es key */.  int 
2140: 28 2a 78 48 61 73 68 29 28 63 6f 6e 73 74 20 76  (*xHash)(const v
2150: 6f 69 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a 20 54  oid*,int);  /* T
2160: 68 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e  he hash function
2170: 20 2a 2f 0a 0a 20 20 69 66 28 20 70 48 3d 3d 30   */..  if( pH==0
2180: 20 7c 7c 20 70 48 2d 3e 68 74 3d 3d 30 20 29 20   || pH->ht==0 ) 
2190: 72 65 74 75 72 6e 20 30 3b 0a 20 20 78 48 61 73  return 0;.  xHas
21a0: 68 20 3d 20 66 74 73 48 61 73 68 46 75 6e 63 74  h = ftsHashFunct
21b0: 69 6f 6e 28 70 48 2d 3e 6b 65 79 43 6c 61 73 73  ion(pH->keyClass
21c0: 29 3b 0a 20 20 61 73 73 65 72 74 28 20 78 48 61  );.  assert( xHa
21d0: 73 68 21 3d 30 20 29 3b 0a 20 20 68 20 3d 20 28  sh!=0 );.  h = (
21e0: 2a 78 48 61 73 68 29 28 70 4b 65 79 2c 6e 4b 65  *xHash)(pKey,nKe
21f0: 79 29 3b 0a 20 20 61 73 73 65 72 74 28 20 28 70  y);.  assert( (p
2200: 48 2d 3e 68 74 73 69 7a 65 20 26 20 28 70 48 2d  H->htsize & (pH-
2210: 3e 68 74 73 69 7a 65 2d 31 29 29 3d 3d 30 20 29  >htsize-1))==0 )
2220: 3b 0a 20 20 65 6c 65 6d 20 3d 20 66 74 73 33 46  ;.  elem = fts3F
2230: 69 6e 64 45 6c 65 6d 65 6e 74 42 79 48 61 73 68  indElementByHash
2240: 28 70 48 2c 70 4b 65 79 2c 6e 4b 65 79 2c 20 68  (pH,pKey,nKey, h
2250: 20 26 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31   & (pH->htsize-1
2260: 29 29 3b 0a 20 20 72 65 74 75 72 6e 20 65 6c 65  ));.  return ele
2270: 6d 20 3f 20 65 6c 65 6d 2d 3e 64 61 74 61 20 3a  m ? elem->data :
2280: 20 30 3b 0a 7d 0a 0a 2f 2a 20 49 6e 73 65 72 74   0;.}../* Insert
2290: 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69 6e 74 6f   an element into
22a0: 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20   the hash table 
22b0: 70 48 2e 20 20 54 68 65 20 6b 65 79 20 69 73 20  pH.  The key is 
22c0: 70 4b 65 79 2c 6e 4b 65 79 0a 2a 2a 20 61 6e 64  pKey,nKey.** and
22d0: 20 74 68 65 20 64 61 74 61 20 69 73 20 22 64 61   the data is "da
22e0: 74 61 22 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 6e 6f  ta"..**.** If no
22f0: 20 65 6c 65 6d 65 6e 74 20 65 78 69 73 74 73 20   element exists 
2300: 77 69 74 68 20 61 20 6d 61 74 63 68 69 6e 67 20  with a matching 
2310: 6b 65 79 2c 20 74 68 65 6e 20 61 20 6e 65 77 0a  key, then a new.
2320: 2a 2a 20 65 6c 65 6d 65 6e 74 20 69 73 20 63 72  ** element is cr
2330: 65 61 74 65 64 2e 20 20 41 20 63 6f 70 79 20 6f  eated.  A copy o
2340: 66 20 74 68 65 20 6b 65 79 20 69 73 20 6d 61 64  f the key is mad
2350: 65 20 69 66 20 74 68 65 20 63 6f 70 79 4b 65 79  e if the copyKey
2360: 0a 2a 2a 20 66 6c 61 67 20 69 73 20 73 65 74 2e  .** flag is set.
2370: 20 20 4e 55 4c 4c 20 69 73 20 72 65 74 75 72 6e    NULL is return
2380: 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 61 6e 6f  ed..**.** If ano
2390: 74 68 65 72 20 65 6c 65 6d 65 6e 74 20 61 6c 72  ther element alr
23a0: 65 61 64 79 20 65 78 69 73 74 73 20 77 69 74 68  eady exists with
23b0: 20 74 68 65 20 73 61 6d 65 20 6b 65 79 2c 20 74   the same key, t
23c0: 68 65 6e 20 74 68 65 0a 2a 2a 20 6e 65 77 20 64  hen the.** new d
23d0: 61 74 61 20 72 65 70 6c 61 63 65 73 20 74 68 65  ata replaces the
23e0: 20 6f 6c 64 20 64 61 74 61 20 61 6e 64 20 74 68   old data and th
23f0: 65 20 6f 6c 64 20 64 61 74 61 20 69 73 20 72 65  e old data is re
2400: 74 75 72 6e 65 64 2e 0a 2a 2a 20 54 68 65 20 6b  turned..** The k
2410: 65 79 20 69 73 20 6e 6f 74 20 63 6f 70 69 65 64  ey is not copied
2420: 20 69 6e 20 74 68 69 73 20 69 6e 73 74 61 6e 63   in this instanc
2430: 65 2e 20 20 49 66 20 61 20 6d 61 6c 6c 6f 63 20  e.  If a malloc 
2440: 66 61 69 6c 73 2c 20 74 68 65 6e 0a 2a 2a 20 74  fails, then.** t
2450: 68 65 20 6e 65 77 20 64 61 74 61 20 69 73 20 72  he new data is r
2460: 65 74 75 72 6e 65 64 20 61 6e 64 20 74 68 65 20  eturned and the 
2470: 68 61 73 68 20 74 61 62 6c 65 20 69 73 20 75 6e  hash table is un
2480: 63 68 61 6e 67 65 64 2e 0a 2a 2a 0a 2a 2a 20 49  changed..**.** I
2490: 66 20 74 68 65 20 22 64 61 74 61 22 20 70 61 72  f the "data" par
24a0: 61 6d 65 74 65 72 20 74 6f 20 74 68 69 73 20 66  ameter to this f
24b0: 75 6e 63 74 69 6f 6e 20 69 73 20 4e 55 4c 4c 2c  unction is NULL,
24c0: 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20 65 6c 65   then the.** ele
24d0: 6d 65 6e 74 20 63 6f 72 72 65 73 70 6f 6e 64 69  ment correspondi
24e0: 6e 67 20 74 6f 20 22 6b 65 79 22 20 69 73 20 72  ng to "key" is r
24f0: 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74 68 65 20  emoved from the 
2500: 68 61 73 68 20 74 61 62 6c 65 2e 0a 2a 2f 0a 76  hash table..*/.v
2510: 6f 69 64 20 2a 73 71 6c 69 74 65 33 46 74 73 33  oid *sqlite3Fts3
2520: 48 61 73 68 49 6e 73 65 72 74 28 0a 20 20 66 74  HashInsert(.  ft
2530: 73 33 48 61 73 68 20 2a 70 48 2c 20 20 20 20 20  s3Hash *pH,     
2540: 20 20 20 2f 2a 20 54 68 65 20 68 61 73 68 20 74     /* The hash t
2550: 61 62 6c 65 20 74 6f 20 69 6e 73 65 72 74 20 69  able to insert i
2560: 6e 74 6f 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 76  nto */.  const v
2570: 6f 69 64 20 2a 70 4b 65 79 2c 20 20 20 20 2f 2a  oid *pKey,    /*
2580: 20 54 68 65 20 6b 65 79 20 2a 2f 0a 20 20 69 6e   The key */.  in
2590: 74 20 6e 4b 65 79 2c 20 20 20 20 20 20 20 20 20  t nKey,         
25a0: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
25b0: 62 79 74 65 73 20 69 6e 20 74 68 65 20 6b 65 79  bytes in the key
25c0: 20 2a 2f 0a 20 20 76 6f 69 64 20 2a 64 61 74 61   */.  void *data
25d0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68             /* Th
25e0: 65 20 64 61 74 61 20 2a 2f 0a 29 7b 0a 20 20 69  e data */.){.  i
25f0: 6e 74 20 68 72 61 77 3b 20 20 20 20 20 20 20 20  nt hraw;        
2600: 20 20 20 20 20 20 20 20 20 2f 2a 20 52 61 77 20           /* Raw 
2610: 68 61 73 68 20 76 61 6c 75 65 20 6f 66 20 74 68  hash value of th
2620: 65 20 6b 65 79 20 2a 2f 0a 20 20 69 6e 74 20 68  e key */.  int h
2630: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
2640: 20 20 20 20 20 2f 2a 20 74 68 65 20 68 61 73 68       /* the hash
2650: 20 6f 66 20 74 68 65 20 6b 65 79 20 6d 6f 64 75   of the key modu
2660: 6c 6f 20 68 61 73 68 20 74 61 62 6c 65 20 73 69  lo hash table si
2670: 7a 65 20 2a 2f 0a 20 20 66 74 73 33 48 61 73 68  ze */.  fts3Hash
2680: 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 20  Elem *elem;     
2690: 20 20 2f 2a 20 55 73 65 64 20 74 6f 20 6c 6f 6f    /* Used to loo
26a0: 70 20 74 68 72 75 20 74 68 65 20 65 6c 65 6d 65  p thru the eleme
26b0: 6e 74 20 6c 69 73 74 20 2a 2f 0a 20 20 66 74 73  nt list */.  fts
26c0: 33 48 61 73 68 45 6c 65 6d 20 2a 6e 65 77 5f 65  3HashElem *new_e
26d0: 6c 65 6d 3b 20 20 20 2f 2a 20 4e 65 77 20 65 6c  lem;   /* New el
26e0: 65 6d 65 6e 74 20 61 64 64 65 64 20 74 6f 20 74  ement added to t
26f0: 68 65 20 70 48 20 2a 2f 0a 20 20 69 6e 74 20 28  he pH */.  int (
2700: 2a 78 48 61 73 68 29 28 63 6f 6e 73 74 20 76 6f  *xHash)(const vo
2710: 69 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a 20 54 68  id*,int);  /* Th
2720: 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 20  e hash function 
2730: 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 70 48  */..  assert( pH
2740: 21 3d 30 20 29 3b 0a 20 20 78 48 61 73 68 20 3d  !=0 );.  xHash =
2750: 20 66 74 73 48 61 73 68 46 75 6e 63 74 69 6f 6e   ftsHashFunction
2760: 28 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a  (pH->keyClass);.
2770: 20 20 61 73 73 65 72 74 28 20 78 48 61 73 68 21    assert( xHash!
2780: 3d 30 20 29 3b 0a 20 20 68 72 61 77 20 3d 20 28  =0 );.  hraw = (
2790: 2a 78 48 61 73 68 29 28 70 4b 65 79 2c 20 6e 4b  *xHash)(pKey, nK
27a0: 65 79 29 3b 0a 20 20 61 73 73 65 72 74 28 20 28  ey);.  assert( (
27b0: 70 48 2d 3e 68 74 73 69 7a 65 20 26 20 28 70 48  pH->htsize & (pH
27c0: 2d 3e 68 74 73 69 7a 65 2d 31 29 29 3d 3d 30 20  ->htsize-1))==0 
27d0: 29 3b 0a 20 20 68 20 3d 20 68 72 61 77 20 26 20  );.  h = hraw & 
27e0: 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29 3b 0a  (pH->htsize-1);.
27f0: 20 20 65 6c 65 6d 20 3d 20 66 74 73 33 46 69 6e    elem = fts3Fin
2800: 64 45 6c 65 6d 65 6e 74 42 79 48 61 73 68 28 70  dElementByHash(p
2810: 48 2c 70 4b 65 79 2c 6e 4b 65 79 2c 68 29 3b 0a  H,pKey,nKey,h);.
2820: 20 20 69 66 28 20 65 6c 65 6d 20 29 7b 0a 20 20    if( elem ){.  
2830: 20 20 76 6f 69 64 20 2a 6f 6c 64 5f 64 61 74 61    void *old_data
2840: 20 3d 20 65 6c 65 6d 2d 3e 64 61 74 61 3b 0a 20   = elem->data;. 
2850: 20 20 20 69 66 28 20 64 61 74 61 3d 3d 30 20 29     if( data==0 )
2860: 7b 0a 20 20 20 20 20 20 66 74 73 33 52 65 6d 6f  {.      fts3Remo
2870: 76 65 45 6c 65 6d 65 6e 74 42 79 48 61 73 68 28  veElementByHash(
2880: 70 48 2c 65 6c 65 6d 2c 68 29 3b 0a 20 20 20 20  pH,elem,h);.    
2890: 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 65 6c 65  }else{.      ele
28a0: 6d 2d 3e 64 61 74 61 20 3d 20 64 61 74 61 3b 0a  m->data = data;.
28b0: 20 20 20 20 7d 0a 20 20 20 20 72 65 74 75 72 6e      }.    return
28c0: 20 6f 6c 64 5f 64 61 74 61 3b 0a 20 20 7d 0a 20   old_data;.  }. 
28d0: 20 69 66 28 20 64 61 74 61 3d 3d 30 20 29 20 72   if( data==0 ) r
28e0: 65 74 75 72 6e 20 30 3b 0a 20 20 6e 65 77 5f 65  eturn 0;.  new_e
28f0: 6c 65 6d 20 3d 20 28 66 74 73 33 48 61 73 68 45  lem = (fts3HashE
2900: 6c 65 6d 2a 29 66 74 73 33 48 61 73 68 4d 61 6c  lem*)fts3HashMal
2910: 6c 6f 63 28 20 73 69 7a 65 6f 66 28 66 74 73 33  loc( sizeof(fts3
2920: 48 61 73 68 45 6c 65 6d 29 20 29 3b 0a 20 20 69  HashElem) );.  i
2930: 66 28 20 6e 65 77 5f 65 6c 65 6d 3d 3d 30 20 29  f( new_elem==0 )
2940: 20 72 65 74 75 72 6e 20 64 61 74 61 3b 0a 20 20   return data;.  
2950: 69 66 28 20 70 48 2d 3e 63 6f 70 79 4b 65 79 20  if( pH->copyKey 
2960: 26 26 20 70 4b 65 79 21 3d 30 20 29 7b 0a 20 20  && pKey!=0 ){.  
2970: 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79    new_elem->pKey
2980: 20 3d 20 66 74 73 33 48 61 73 68 4d 61 6c 6c 6f   = fts3HashMallo
2990: 63 28 20 6e 4b 65 79 20 29 3b 0a 20 20 20 20 69  c( nKey );.    i
29a0: 66 28 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65  f( new_elem->pKe
29b0: 79 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 66 74  y==0 ){.      ft
29c0: 73 33 48 61 73 68 46 72 65 65 28 6e 65 77 5f 65  s3HashFree(new_e
29d0: 6c 65 6d 29 3b 0a 20 20 20 20 20 20 72 65 74 75  lem);.      retu
29e0: 72 6e 20 64 61 74 61 3b 0a 20 20 20 20 7d 0a 20  rn data;.    }. 
29f0: 20 20 20 6d 65 6d 63 70 79 28 28 76 6f 69 64 2a     memcpy((void*
2a00: 29 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 2c  )new_elem->pKey,
2a10: 20 70 4b 65 79 2c 20 6e 4b 65 79 29 3b 0a 20 20   pKey, nKey);.  
2a20: 7d 65 6c 73 65 7b 0a 20 20 20 20 6e 65 77 5f 65  }else{.    new_e
2a30: 6c 65 6d 2d 3e 70 4b 65 79 20 3d 20 28 76 6f 69  lem->pKey = (voi
2a40: 64 2a 29 70 4b 65 79 3b 0a 20 20 7d 0a 20 20 6e  d*)pKey;.  }.  n
2a50: 65 77 5f 65 6c 65 6d 2d 3e 6e 4b 65 79 20 3d 20  ew_elem->nKey = 
2a60: 6e 4b 65 79 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e  nKey;.  pH->coun
2a70: 74 2b 2b 3b 0a 20 20 69 66 28 20 70 48 2d 3e 68  t++;.  if( pH->h
2a80: 74 73 69 7a 65 3d 3d 30 20 29 7b 0a 20 20 20 20  tsize==0 ){.    
2a90: 66 74 73 33 52 65 68 61 73 68 28 70 48 2c 38 29  fts3Rehash(pH,8)
2aa0: 3b 0a 20 20 20 20 69 66 28 20 70 48 2d 3e 68 74  ;.    if( pH->ht
2ab0: 73 69 7a 65 3d 3d 30 20 29 7b 0a 20 20 20 20 20  size==0 ){.     
2ac0: 20 70 48 2d 3e 63 6f 75 6e 74 20 3d 20 30 3b 0a   pH->count = 0;.
2ad0: 20 20 20 20 20 20 66 74 73 33 48 61 73 68 46 72        fts3HashFr
2ae0: 65 65 28 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20 20  ee(new_elem);.  
2af0: 20 20 20 20 72 65 74 75 72 6e 20 64 61 74 61 3b      return data;
2b00: 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 69 66 28  .    }.  }.  if(
2b10: 20 70 48 2d 3e 63 6f 75 6e 74 20 3e 20 70 48 2d   pH->count > pH-
2b20: 3e 68 74 73 69 7a 65 20 29 7b 0a 20 20 20 20 66  >htsize ){.    f
2b30: 74 73 33 52 65 68 61 73 68 28 70 48 2c 70 48 2d  ts3Rehash(pH,pH-
2b40: 3e 68 74 73 69 7a 65 2a 32 29 3b 0a 20 20 7d 0a  >htsize*2);.  }.
2b50: 20 20 61 73 73 65 72 74 28 20 70 48 2d 3e 68 74    assert( pH->ht
2b60: 73 69 7a 65 3e 30 20 29 3b 0a 20 20 61 73 73 65  size>0 );.  asse
2b70: 72 74 28 20 28 70 48 2d 3e 68 74 73 69 7a 65 20  rt( (pH->htsize 
2b80: 26 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29  & (pH->htsize-1)
2b90: 29 3d 3d 30 20 29 3b 0a 20 20 68 20 3d 20 68 72  )==0 );.  h = hr
2ba0: 61 77 20 26 20 28 70 48 2d 3e 68 74 73 69 7a 65  aw & (pH->htsize
2bb0: 2d 31 29 3b 0a 20 20 66 74 73 33 48 61 73 68 49  -1);.  fts3HashI
2bc0: 6e 73 65 72 74 45 6c 65 6d 65 6e 74 28 70 48 2c  nsertElement(pH,
2bd0: 20 26 70 48 2d 3e 68 74 5b 68 5d 2c 20 6e 65 77   &pH->ht[h], new
2be0: 5f 65 6c 65 6d 29 3b 0a 20 20 6e 65 77 5f 65 6c  _elem);.  new_el
2bf0: 65 6d 2d 3e 64 61 74 61 20 3d 20 64 61 74 61 3b  em->data = data;
2c00: 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a 0a  .  return 0;.}..
2c10: 23 65 6e 64 69 66 20 2f 2a 20 21 64 65 66 69 6e  #endif /* !defin
2c20: 65 64 28 53 51 4c 49 54 45 5f 43 4f 52 45 29 20  ed(SQLITE_CORE) 
2c30: 7c 7c 20 64 65 66 69 6e 65 64 28 53 51 4c 49 54  || defined(SQLIT
2c40: 45 5f 45 4e 41 42 4c 45 5f 46 54 53 33 29 20 2a  E_ENABLE_FTS3) *
2c50: 2f 0a                                            /.