/ Hex Artifact Content
Login

Artifact 29b986e43f4e9dd40110eafa377dc0d63c422c60:


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 6e 63 6c 75 64  ned)..*/.#includ
0360: 65 20 22 66 74 73 33 49 6e 74 2e 68 22 0a 23 69  e "fts3Int.h".#i
0370: 66 20 21 64 65 66 69 6e 65 64 28 53 51 4c 49 54  f !defined(SQLIT
0380: 45 5f 43 4f 52 45 29 20 7c 7c 20 64 65 66 69 6e  E_CORE) || defin
0390: 65 64 28 53 51 4c 49 54 45 5f 45 4e 41 42 4c 45  ed(SQLITE_ENABLE
03a0: 5f 46 54 53 33 29 0a 0a 23 69 6e 63 6c 75 64 65  _FTS3)..#include
03b0: 20 3c 61 73 73 65 72 74 2e 68 3e 0a 23 69 6e 63   <assert.h>.#inc
03c0: 6c 75 64 65 20 3c 73 74 64 6c 69 62 2e 68 3e 0a  lude <stdlib.h>.
03d0: 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e 67  #include <string
03e0: 2e 68 3e 0a 0a 23 69 6e 63 6c 75 64 65 20 22 66  .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 46 74 73 33 48  s3HashInit(Fts3H
06c0: 61 73 68 20 2a 70 4e 65 77 2c 20 63 68 61 72 20  ash *pNew, char 
06d0: 6b 65 79 43 6c 61 73 73 2c 20 63 68 61 72 20 63  keyClass, char c
06e0: 6f 70 79 4b 65 79 29 7b 0a 20 20 61 73 73 65 72  opyKey){.  asser
06f0: 74 28 20 70 4e 65 77 21 3d 30 20 29 3b 0a 20 20  t( pNew!=0 );.  
0700: 61 73 73 65 72 74 28 20 6b 65 79 43 6c 61 73 73  assert( keyClass
0710: 3e 3d 46 54 53 33 5f 48 41 53 48 5f 53 54 52 49  >=FTS3_HASH_STRI
0720: 4e 47 20 26 26 20 6b 65 79 43 6c 61 73 73 3c 3d  NG && keyClass<=
0730: 46 54 53 33 5f 48 41 53 48 5f 42 49 4e 41 52 59  FTS3_HASH_BINARY
0740: 20 29 3b 0a 20 20 70 4e 65 77 2d 3e 6b 65 79 43   );.  pNew->keyC
0750: 6c 61 73 73 20 3d 20 6b 65 79 43 6c 61 73 73 3b  lass = keyClass;
0760: 0a 20 20 70 4e 65 77 2d 3e 63 6f 70 79 4b 65 79  .  pNew->copyKey
0770: 20 3d 20 63 6f 70 79 4b 65 79 3b 0a 20 20 70 4e   = copyKey;.  pN
0780: 65 77 2d 3e 66 69 72 73 74 20 3d 20 30 3b 0a 20  ew->first = 0;. 
0790: 20 70 4e 65 77 2d 3e 63 6f 75 6e 74 20 3d 20 30   pNew->count = 0
07a0: 3b 0a 20 20 70 4e 65 77 2d 3e 68 74 73 69 7a 65  ;.  pNew->htsize
07b0: 20 3d 20 30 3b 0a 20 20 70 4e 65 77 2d 3e 68 74   = 0;.  pNew->ht
07c0: 20 3d 20 30 3b 0a 7d 0a 0a 2f 2a 20 52 65 6d 6f   = 0;.}../* Remo
07d0: 76 65 20 61 6c 6c 20 65 6e 74 72 69 65 73 20 66  ve all entries f
07e0: 72 6f 6d 20 61 20 68 61 73 68 20 74 61 62 6c 65  rom a hash table
07f0: 2e 20 20 52 65 63 6c 61 69 6d 20 61 6c 6c 20 6d  .  Reclaim all m
0800: 65 6d 6f 72 79 2e 0a 2a 2a 20 43 61 6c 6c 20 74  emory..** Call t
0810: 68 69 73 20 72 6f 75 74 69 6e 65 20 74 6f 20 64  his routine to d
0820: 65 6c 65 74 65 20 61 20 68 61 73 68 20 74 61 62  elete a hash tab
0830: 6c 65 20 6f 72 20 74 6f 20 72 65 73 65 74 20 61  le or to reset a
0840: 20 68 61 73 68 20 74 61 62 6c 65 0a 2a 2a 20 74   hash table.** t
0850: 6f 20 74 68 65 20 65 6d 70 74 79 20 73 74 61 74  o the empty stat
0860: 65 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74  e..*/.void sqlit
0870: 65 33 46 74 73 33 48 61 73 68 43 6c 65 61 72 28  e3Fts3HashClear(
0880: 46 74 73 33 48 61 73 68 20 2a 70 48 29 7b 0a 20  Fts3Hash *pH){. 
0890: 20 46 74 73 33 48 61 73 68 45 6c 65 6d 20 2a 65   Fts3HashElem *e
08a0: 6c 65 6d 3b 20 20 20 20 20 20 20 20 20 2f 2a 20  lem;         /* 
08b0: 46 6f 72 20 6c 6f 6f 70 69 6e 67 20 6f 76 65 72  For looping over
08c0: 20 61 6c 6c 20 65 6c 65 6d 65 6e 74 73 20 6f 66   all elements of
08d0: 20 74 68 65 20 74 61 62 6c 65 20 2a 2f 0a 0a 20   the table */.. 
08e0: 20 61 73 73 65 72 74 28 20 70 48 21 3d 30 20 29   assert( pH!=0 )
08f0: 3b 0a 20 20 65 6c 65 6d 20 3d 20 70 48 2d 3e 66  ;.  elem = pH->f
0900: 69 72 73 74 3b 0a 20 20 70 48 2d 3e 66 69 72 73  irst;.  pH->firs
0910: 74 20 3d 20 30 3b 0a 20 20 66 74 73 33 48 61 73  t = 0;.  fts3Has
0920: 68 46 72 65 65 28 70 48 2d 3e 68 74 29 3b 0a 20  hFree(pH->ht);. 
0930: 20 70 48 2d 3e 68 74 20 3d 20 30 3b 0a 20 20 70   pH->ht = 0;.  p
0940: 48 2d 3e 68 74 73 69 7a 65 20 3d 20 30 3b 0a 20  H->htsize = 0;. 
0950: 20 77 68 69 6c 65 28 20 65 6c 65 6d 20 29 7b 0a   while( elem ){.
0960: 20 20 20 20 46 74 73 33 48 61 73 68 45 6c 65 6d      Fts3HashElem
0970: 20 2a 6e 65 78 74 5f 65 6c 65 6d 20 3d 20 65 6c   *next_elem = el
0980: 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 69 66  em->next;.    if
0990: 28 20 70 48 2d 3e 63 6f 70 79 4b 65 79 20 26 26  ( pH->copyKey &&
09a0: 20 65 6c 65 6d 2d 3e 70 4b 65 79 20 29 7b 0a 20   elem->pKey ){. 
09b0: 20 20 20 20 20 66 74 73 33 48 61 73 68 46 72 65       fts3HashFre
09c0: 65 28 65 6c 65 6d 2d 3e 70 4b 65 79 29 3b 0a 20  e(elem->pKey);. 
09d0: 20 20 20 7d 0a 20 20 20 20 66 74 73 33 48 61 73     }.    fts3Has
09e0: 68 46 72 65 65 28 65 6c 65 6d 29 3b 0a 20 20 20  hFree(elem);.   
09f0: 20 65 6c 65 6d 20 3d 20 6e 65 78 74 5f 65 6c 65   elem = next_ele
0a00: 6d 3b 0a 20 20 7d 0a 20 20 70 48 2d 3e 63 6f 75  m;.  }.  pH->cou
0a10: 6e 74 20 3d 20 30 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  nt = 0;.}../*.**
0a20: 20 48 61 73 68 20 61 6e 64 20 63 6f 6d 70 61 72   Hash and compar
0a30: 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 20 77  ison functions w
0a40: 68 65 6e 20 74 68 65 20 6d 6f 64 65 20 69 73 20  hen the mode is 
0a50: 46 54 53 33 5f 48 41 53 48 5f 53 54 52 49 4e 47  FTS3_HASH_STRING
0a60: 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 66  .*/.static int f
0a70: 74 73 33 53 74 72 48 61 73 68 28 63 6f 6e 73 74  ts3StrHash(const
0a80: 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74   void *pKey, int
0a90: 20 6e 4b 65 79 29 7b 0a 20 20 63 6f 6e 73 74 20   nKey){.  const 
0aa0: 63 68 61 72 20 2a 7a 20 3d 20 28 63 6f 6e 73 74  char *z = (const
0ab0: 20 63 68 61 72 20 2a 29 70 4b 65 79 3b 0a 20 20   char *)pKey;.  
0ac0: 75 6e 73 69 67 6e 65 64 20 68 20 3d 20 30 3b 0a  unsigned h = 0;.
0ad0: 20 20 69 66 28 20 6e 4b 65 79 3c 3d 30 20 29 20    if( nKey<=0 ) 
0ae0: 6e 4b 65 79 20 3d 20 28 69 6e 74 29 20 73 74 72  nKey = (int) str
0af0: 6c 65 6e 28 7a 29 3b 0a 20 20 77 68 69 6c 65 28  len(z);.  while(
0b00: 20 6e 4b 65 79 20 3e 20 30 20 20 29 7b 0a 20 20   nKey > 0  ){.  
0b10: 20 20 68 20 3d 20 28 68 3c 3c 33 29 20 5e 20 68    h = (h<<3) ^ h
0b20: 20 5e 20 2a 7a 2b 2b 3b 0a 20 20 20 20 6e 4b 65   ^ *z++;.    nKe
0b30: 79 2d 2d 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72  y--;.  }.  retur
0b40: 6e 20 28 69 6e 74 29 28 68 20 26 20 30 78 37 66  n (int)(h & 0x7f
0b50: 66 66 66 66 66 66 29 3b 0a 7d 0a 73 74 61 74 69  ffffff);.}.stati
0b60: 63 20 69 6e 74 20 66 74 73 33 53 74 72 43 6f 6d  c int fts3StrCom
0b70: 70 61 72 65 28 63 6f 6e 73 74 20 76 6f 69 64 20  pare(const void 
0b80: 2a 70 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c 20  *pKey1, int n1, 
0b90: 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79  const void *pKey
0ba0: 32 2c 20 69 6e 74 20 6e 32 29 7b 0a 20 20 69 66  2, int n2){.  if
0bb0: 28 20 6e 31 21 3d 6e 32 20 29 20 72 65 74 75 72  ( n1!=n2 ) retur
0bc0: 6e 20 31 3b 0a 20 20 72 65 74 75 72 6e 20 73 74  n 1;.  return st
0bd0: 72 6e 63 6d 70 28 28 63 6f 6e 73 74 20 63 68 61  rncmp((const cha
0be0: 72 2a 29 70 4b 65 79 31 2c 28 63 6f 6e 73 74 20  r*)pKey1,(const 
0bf0: 63 68 61 72 2a 29 70 4b 65 79 32 2c 6e 31 29 3b  char*)pKey2,n1);
0c00: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 48 61 73 68 20 61  .}../*.** Hash a
0c10: 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75  nd comparison fu
0c20: 6e 63 74 69 6f 6e 73 20 77 68 65 6e 20 74 68 65  nctions when the
0c30: 20 6d 6f 64 65 20 69 73 20 46 54 53 33 5f 48 41   mode is FTS3_HA
0c40: 53 48 5f 42 49 4e 41 52 59 0a 2a 2f 0a 73 74 61  SH_BINARY.*/.sta
0c50: 74 69 63 20 69 6e 74 20 66 74 73 33 42 69 6e 48  tic int fts3BinH
0c60: 61 73 68 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a  ash(const void *
0c70: 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b  pKey, int nKey){
0c80: 0a 20 20 69 6e 74 20 68 20 3d 20 30 3b 0a 20 20  .  int h = 0;.  
0c90: 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a 20 3d 20  const char *z = 
0ca0: 28 63 6f 6e 73 74 20 63 68 61 72 20 2a 29 70 4b  (const char *)pK
0cb0: 65 79 3b 0a 20 20 77 68 69 6c 65 28 20 6e 4b 65  ey;.  while( nKe
0cc0: 79 2d 2d 20 3e 20 30 20 29 7b 0a 20 20 20 20 68  y-- > 0 ){.    h
0cd0: 20 3d 20 28 68 3c 3c 33 29 20 5e 20 68 20 5e 20   = (h<<3) ^ h ^ 
0ce0: 2a 28 7a 2b 2b 29 3b 0a 20 20 7d 0a 20 20 72 65  *(z++);.  }.  re
0cf0: 74 75 72 6e 20 68 20 26 20 30 78 37 66 66 66 66  turn h & 0x7ffff
0d00: 66 66 66 3b 0a 7d 0a 73 74 61 74 69 63 20 69 6e  fff;.}.static in
0d10: 74 20 66 74 73 33 42 69 6e 43 6f 6d 70 61 72 65  t fts3BinCompare
0d20: 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65  (const void *pKe
0d30: 79 31 2c 20 69 6e 74 20 6e 31 2c 20 63 6f 6e 73  y1, int n1, cons
0d40: 74 20 76 6f 69 64 20 2a 70 4b 65 79 32 2c 20 69  t void *pKey2, i
0d50: 6e 74 20 6e 32 29 7b 0a 20 20 69 66 28 20 6e 31  nt n2){.  if( n1
0d60: 21 3d 6e 32 20 29 20 72 65 74 75 72 6e 20 31 3b  !=n2 ) return 1;
0d70: 0a 20 20 72 65 74 75 72 6e 20 6d 65 6d 63 6d 70  .  return memcmp
0d80: 28 70 4b 65 79 31 2c 70 4b 65 79 32 2c 6e 31 29  (pKey1,pKey2,n1)
0d90: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72  ;.}../*.** Retur
0da0: 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74  n a pointer to t
0db0: 68 65 20 61 70 70 72 6f 70 72 69 61 74 65 20 68  he appropriate h
0dc0: 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 67 69 76  ash function giv
0dd0: 65 6e 20 74 68 65 20 6b 65 79 20 63 6c 61 73 73  en the key class
0de0: 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 43 20 73 79  ..**.** The C sy
0df0: 6e 74 61 78 20 69 6e 20 74 68 69 73 20 66 75 6e  ntax in this fun
0e00: 63 74 69 6f 6e 20 64 65 66 69 6e 69 74 69 6f 6e  ction definition
0e10: 20 6d 61 79 20 62 65 20 75 6e 66 61 6d 69 6c 61   may be unfamila
0e20: 72 20 74 6f 20 73 6f 6d 65 20 0a 2a 2a 20 70 72  r to some .** pr
0e30: 6f 67 72 61 6d 6d 65 72 73 2c 20 73 6f 20 77 65  ogrammers, so we
0e40: 20 70 72 6f 76 69 64 65 20 74 68 65 20 66 6f 6c   provide the fol
0e50: 6c 6f 77 69 6e 67 20 61 64 64 69 74 69 6f 6e 61  lowing additiona
0e60: 6c 20 65 78 70 6c 61 6e 61 74 69 6f 6e 3a 0a 2a  l explanation:.*
0e70: 2a 0a 2a 2a 20 54 68 65 20 6e 61 6d 65 20 6f 66  *.** The name of
0e80: 20 74 68 65 20 66 75 6e 63 74 69 6f 6e 20 69 73   the function is
0e90: 20 22 66 74 73 48 61 73 68 46 75 6e 63 74 69 6f   "ftsHashFunctio
0ea0: 6e 22 2e 20 20 54 68 65 20 66 75 6e 63 74 69 6f  n".  The functio
0eb0: 6e 20 74 61 6b 65 73 20 61 0a 2a 2a 20 73 69 6e  n takes a.** sin
0ec0: 67 6c 65 20 70 61 72 61 6d 65 74 65 72 20 22 6b  gle parameter "k
0ed0: 65 79 43 6c 61 73 73 22 2e 20 20 54 68 65 20 72  eyClass".  The r
0ee0: 65 74 75 72 6e 20 76 61 6c 75 65 20 6f 66 20 66  eturn value of f
0ef0: 74 73 48 61 73 68 46 75 6e 63 74 69 6f 6e 28 29  tsHashFunction()
0f00: 0a 2a 2a 20 69 73 20 61 20 70 6f 69 6e 74 65 72  .** is a pointer
0f10: 20 74 6f 20 61 6e 6f 74 68 65 72 20 66 75 6e 63   to another func
0f20: 74 69 6f 6e 2e 20 20 53 70 65 63 69 66 69 63 61  tion.  Specifica
0f30: 6c 6c 79 2c 20 74 68 65 20 72 65 74 75 72 6e 20  lly, the return 
0f40: 76 61 6c 75 65 0a 2a 2a 20 6f 66 20 66 74 73 48  value.** of ftsH
0f50: 61 73 68 46 75 6e 63 74 69 6f 6e 28 29 20 69 73  ashFunction() is
0f60: 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 20   a pointer to a 
0f70: 66 75 6e 63 74 69 6f 6e 20 74 68 61 74 20 74 61  function that ta
0f80: 6b 65 73 20 74 77 6f 20 70 61 72 61 6d 65 74 65  kes two paramete
0f90: 72 73 0a 2a 2a 20 77 69 74 68 20 74 79 70 65 73  rs.** with types
0fa0: 20 22 63 6f 6e 73 74 20 76 6f 69 64 2a 22 20 61   "const void*" a
0fb0: 6e 64 20 22 69 6e 74 22 20 61 6e 64 20 72 65 74  nd "int" and ret
0fc0: 75 72 6e 73 20 61 6e 20 22 69 6e 74 22 2e 0a 2a  urns an "int"..*
0fd0: 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 28 2a 66  /.static int (*f
0fe0: 74 73 48 61 73 68 46 75 6e 63 74 69 6f 6e 28 69  tsHashFunction(i
0ff0: 6e 74 20 6b 65 79 43 6c 61 73 73 29 29 28 63 6f  nt keyClass))(co
1000: 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29 7b 0a  nst void*,int){.
1010: 20 20 69 66 28 20 6b 65 79 43 6c 61 73 73 3d 3d    if( keyClass==
1020: 46 54 53 33 5f 48 41 53 48 5f 53 54 52 49 4e 47  FTS3_HASH_STRING
1030: 20 29 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 26   ){.    return &
1040: 66 74 73 33 53 74 72 48 61 73 68 3b 0a 20 20 7d  fts3StrHash;.  }
1050: 65 6c 73 65 7b 0a 20 20 20 20 61 73 73 65 72 74  else{.    assert
1060: 28 20 6b 65 79 43 6c 61 73 73 3d 3d 46 54 53 33  ( keyClass==FTS3
1070: 5f 48 41 53 48 5f 42 49 4e 41 52 59 20 29 3b 0a  _HASH_BINARY );.
1080: 20 20 20 20 72 65 74 75 72 6e 20 26 66 74 73 33      return &fts3
1090: 42 69 6e 48 61 73 68 3b 0a 20 20 7d 0a 7d 0a 0a  BinHash;.  }.}..
10a0: 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 61 20 70  /*.** Return a p
10b0: 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 20 61 70  ointer to the ap
10c0: 70 72 6f 70 72 69 61 74 65 20 68 61 73 68 20 66  propriate hash f
10d0: 75 6e 63 74 69 6f 6e 20 67 69 76 65 6e 20 74 68  unction given th
10e0: 65 20 6b 65 79 20 63 6c 61 73 73 2e 0a 2a 2a 0a  e key class..**.
10f0: 2a 2a 20 46 6f 72 20 68 65 6c 70 20 69 6e 20 69  ** For help in i
1100: 6e 74 65 72 70 72 65 74 65 64 20 74 68 65 20 6f  nterpreted the o
1110: 62 73 63 75 72 65 20 43 20 63 6f 64 65 20 69 6e  bscure C code in
1120: 20 74 68 65 20 66 75 6e 63 74 69 6f 6e 20 64 65   the function de
1130: 66 69 6e 69 74 69 6f 6e 2c 0a 2a 2a 20 73 65 65  finition,.** see
1140: 20 74 68 65 20 68 65 61 64 65 72 20 63 6f 6d 6d   the header comm
1150: 65 6e 74 20 6f 6e 20 74 68 65 20 70 72 65 76 69  ent on the previ
1160: 6f 75 73 20 66 75 6e 63 74 69 6f 6e 2e 0a 2a 2f  ous function..*/
1170: 0a 73 74 61 74 69 63 20 69 6e 74 20 28 2a 66 74  .static int (*ft
1180: 73 43 6f 6d 70 61 72 65 46 75 6e 63 74 69 6f 6e  sCompareFunction
1190: 28 69 6e 74 20 6b 65 79 43 6c 61 73 73 29 29 28  (int keyClass))(
11a0: 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 2c  const void*,int,
11b0: 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29  const void*,int)
11c0: 7b 0a 20 20 69 66 28 20 6b 65 79 43 6c 61 73 73  {.  if( keyClass
11d0: 3d 3d 46 54 53 33 5f 48 41 53 48 5f 53 54 52 49  ==FTS3_HASH_STRI
11e0: 4e 47 20 29 7b 0a 20 20 20 20 72 65 74 75 72 6e  NG ){.    return
11f0: 20 26 66 74 73 33 53 74 72 43 6f 6d 70 61 72 65   &fts3StrCompare
1200: 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 61  ;.  }else{.    a
1210: 73 73 65 72 74 28 20 6b 65 79 43 6c 61 73 73 3d  ssert( keyClass=
1220: 3d 46 54 53 33 5f 48 41 53 48 5f 42 49 4e 41 52  =FTS3_HASH_BINAR
1230: 59 20 29 3b 0a 20 20 20 20 72 65 74 75 72 6e 20  Y );.    return 
1240: 26 66 74 73 33 42 69 6e 43 6f 6d 70 61 72 65 3b  &fts3BinCompare;
1250: 0a 20 20 7d 0a 7d 0a 0a 2f 2a 20 4c 69 6e 6b 20  .  }.}../* Link 
1260: 61 6e 20 65 6c 65 6d 65 6e 74 20 69 6e 74 6f 20  an element into 
1270: 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 0a 2a  the hash table.*
1280: 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 66 74  /.static void ft
1290: 73 33 48 61 73 68 49 6e 73 65 72 74 45 6c 65 6d  s3HashInsertElem
12a0: 65 6e 74 28 0a 20 20 46 74 73 33 48 61 73 68 20  ent(.  Fts3Hash 
12b0: 2a 70 48 2c 20 20 20 20 20 20 20 20 20 20 20 20  *pH,            
12c0: 2f 2a 20 54 68 65 20 63 6f 6d 70 6c 65 74 65 20  /* The complete 
12d0: 68 61 73 68 20 74 61 62 6c 65 20 2a 2f 0a 20 20  hash table */.  
12e0: 73 74 72 75 63 74 20 5f 66 74 73 33 68 74 20 2a  struct _fts3ht *
12f0: 70 45 6e 74 72 79 2c 20 20 2f 2a 20 54 68 65 20  pEntry,  /* The 
1300: 65 6e 74 72 79 20 69 6e 74 6f 20 77 68 69 63 68  entry into which
1310: 20 70 4e 65 77 20 69 73 20 69 6e 73 65 72 74 65   pNew is inserte
1320: 64 20 2a 2f 0a 20 20 46 74 73 33 48 61 73 68 45  d */.  Fts3HashE
1330: 6c 65 6d 20 2a 70 4e 65 77 20 20 20 20 20 20 20  lem *pNew       
1340: 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e 74 20 74  /* The element t
1350: 6f 20 62 65 20 69 6e 73 65 72 74 65 64 20 2a 2f  o be inserted */
1360: 0a 29 7b 0a 20 20 46 74 73 33 48 61 73 68 45 6c  .){.  Fts3HashEl
1370: 65 6d 20 2a 70 48 65 61 64 3b 20 20 20 20 20 2f  em *pHead;     /
1380: 2a 20 46 69 72 73 74 20 65 6c 65 6d 65 6e 74 20  * First element 
1390: 61 6c 72 65 61 64 79 20 69 6e 20 70 45 6e 74 72  already in pEntr
13a0: 79 20 2a 2f 0a 20 20 70 48 65 61 64 20 3d 20 70  y */.  pHead = p
13b0: 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3b 0a 20 20  Entry->chain;.  
13c0: 69 66 28 20 70 48 65 61 64 20 29 7b 0a 20 20 20  if( pHead ){.   
13d0: 20 70 4e 65 77 2d 3e 6e 65 78 74 20 3d 20 70 48   pNew->next = pH
13e0: 65 61 64 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 70  ead;.    pNew->p
13f0: 72 65 76 20 3d 20 70 48 65 61 64 2d 3e 70 72 65  rev = pHead->pre
1400: 76 3b 0a 20 20 20 20 69 66 28 20 70 48 65 61 64  v;.    if( pHead
1410: 2d 3e 70 72 65 76 20 29 7b 20 70 48 65 61 64 2d  ->prev ){ pHead-
1420: 3e 70 72 65 76 2d 3e 6e 65 78 74 20 3d 20 70 4e  >prev->next = pN
1430: 65 77 3b 20 7d 0a 20 20 20 20 65 6c 73 65 20 20  ew; }.    else  
1440: 20 20 20 20 20 20 20 20 20 20 20 7b 20 70 48 2d             { pH-
1450: 3e 66 69 72 73 74 20 3d 20 70 4e 65 77 3b 20 7d  >first = pNew; }
1460: 0a 20 20 20 20 70 48 65 61 64 2d 3e 70 72 65 76  .    pHead->prev
1470: 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 65 6c 73 65   = pNew;.  }else
1480: 7b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 65 78 74  {.    pNew->next
1490: 20 3d 20 70 48 2d 3e 66 69 72 73 74 3b 0a 20 20   = pH->first;.  
14a0: 20 20 69 66 28 20 70 48 2d 3e 66 69 72 73 74 20    if( pH->first 
14b0: 29 7b 20 70 48 2d 3e 66 69 72 73 74 2d 3e 70 72  ){ pH->first->pr
14c0: 65 76 20 3d 20 70 4e 65 77 3b 20 7d 0a 20 20 20  ev = pNew; }.   
14d0: 20 70 4e 65 77 2d 3e 70 72 65 76 20 3d 20 30 3b   pNew->prev = 0;
14e0: 0a 20 20 20 20 70 48 2d 3e 66 69 72 73 74 20 3d  .    pH->first =
14f0: 20 70 4e 65 77 3b 0a 20 20 7d 0a 20 20 70 45 6e   pNew;.  }.  pEn
1500: 74 72 79 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20 20  try->count++;.  
1510: 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 20 3d 20  pEntry->chain = 
1520: 70 4e 65 77 3b 0a 7d 0a 0a 0a 2f 2a 20 52 65 73  pNew;.}.../* Res
1530: 69 7a 65 20 74 68 65 20 68 61 73 68 20 74 61 62  ize the hash tab
1540: 6c 65 20 73 6f 20 74 68 61 74 20 69 74 20 63 61  le so that it ca
1550: 6e 74 61 69 6e 73 20 22 6e 65 77 5f 73 69 7a 65  ntains "new_size
1560: 22 20 62 75 63 6b 65 74 73 2e 0a 2a 2a 20 22 6e  " buckets..** "n
1570: 65 77 5f 73 69 7a 65 22 20 6d 75 73 74 20 62 65  ew_size" must be
1580: 20 61 20 70 6f 77 65 72 20 6f 66 20 32 2e 20 20   a power of 2.  
1590: 54 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 6d  The hash table m
15a0: 69 67 68 74 20 66 61 69 6c 20 0a 2a 2a 20 74 6f  ight fail .** to
15b0: 20 72 65 73 69 7a 65 20 69 66 20 73 71 6c 69 74   resize if sqlit
15c0: 65 4d 61 6c 6c 6f 63 28 29 20 66 61 69 6c 73 2e  eMalloc() fails.
15d0: 0a 2a 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 6e 6f  .**.** Return no
15e0: 6e 2d 7a 65 72 6f 20 69 66 20 61 20 6d 65 6d 6f  n-zero if a memo
15f0: 72 79 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 65 72  ry allocation er
1600: 72 6f 72 20 6f 63 63 75 72 73 2e 0a 2a 2f 0a 73  ror occurs..*/.s
1610: 74 61 74 69 63 20 69 6e 74 20 66 74 73 33 52 65  tatic int fts3Re
1620: 68 61 73 68 28 46 74 73 33 48 61 73 68 20 2a 70  hash(Fts3Hash *p
1630: 48 2c 20 69 6e 74 20 6e 65 77 5f 73 69 7a 65 29  H, int new_size)
1640: 7b 0a 20 20 73 74 72 75 63 74 20 5f 66 74 73 33  {.  struct _fts3
1650: 68 74 20 2a 6e 65 77 5f 68 74 3b 20 20 20 20 20  ht *new_ht;     
1660: 20 20 20 20 20 2f 2a 20 54 68 65 20 6e 65 77 20       /* The new 
1670: 68 61 73 68 20 74 61 62 6c 65 20 2a 2f 0a 20 20  hash table */.  
1680: 46 74 73 33 48 61 73 68 45 6c 65 6d 20 2a 65 6c  Fts3HashElem *el
1690: 65 6d 2c 20 2a 6e 65 78 74 5f 65 6c 65 6d 3b 20  em, *next_elem; 
16a0: 20 2f 2a 20 46 6f 72 20 6c 6f 6f 70 69 6e 67 20   /* For looping 
16b0: 6f 76 65 72 20 65 78 69 73 74 69 6e 67 20 65 6c  over existing el
16c0: 65 6d 65 6e 74 73 20 2a 2f 0a 20 20 69 6e 74 20  ements */.  int 
16d0: 28 2a 78 48 61 73 68 29 28 63 6f 6e 73 74 20 76  (*xHash)(const v
16e0: 6f 69 64 2a 2c 69 6e 74 29 3b 20 20 20 2f 2a 20  oid*,int);   /* 
16f0: 54 68 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f  The hash functio
1700: 6e 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20  n */..  assert( 
1710: 28 6e 65 77 5f 73 69 7a 65 20 26 20 28 6e 65 77  (new_size & (new
1720: 5f 73 69 7a 65 2d 31 29 29 3d 3d 30 20 29 3b 0a  _size-1))==0 );.
1730: 20 20 6e 65 77 5f 68 74 20 3d 20 28 73 74 72 75    new_ht = (stru
1740: 63 74 20 5f 66 74 73 33 68 74 20 2a 29 66 74 73  ct _fts3ht *)fts
1750: 33 48 61 73 68 4d 61 6c 6c 6f 63 28 20 6e 65 77  3HashMalloc( new
1760: 5f 73 69 7a 65 2a 73 69 7a 65 6f 66 28 73 74 72  _size*sizeof(str
1770: 75 63 74 20 5f 66 74 73 33 68 74 29 20 29 3b 0a  uct _fts3ht) );.
1780: 20 20 69 66 28 20 6e 65 77 5f 68 74 3d 3d 30 20    if( new_ht==0 
1790: 29 20 72 65 74 75 72 6e 20 31 3b 0a 20 20 66 74  ) return 1;.  ft
17a0: 73 33 48 61 73 68 46 72 65 65 28 70 48 2d 3e 68  s3HashFree(pH->h
17b0: 74 29 3b 0a 20 20 70 48 2d 3e 68 74 20 3d 20 6e  t);.  pH->ht = n
17c0: 65 77 5f 68 74 3b 0a 20 20 70 48 2d 3e 68 74 73  ew_ht;.  pH->hts
17d0: 69 7a 65 20 3d 20 6e 65 77 5f 73 69 7a 65 3b 0a  ize = new_size;.
17e0: 20 20 78 48 61 73 68 20 3d 20 66 74 73 48 61 73    xHash = ftsHas
17f0: 68 46 75 6e 63 74 69 6f 6e 28 70 48 2d 3e 6b 65  hFunction(pH->ke
1800: 79 43 6c 61 73 73 29 3b 0a 20 20 66 6f 72 28 65  yClass);.  for(e
1810: 6c 65 6d 3d 70 48 2d 3e 66 69 72 73 74 2c 20 70  lem=pH->first, p
1820: 48 2d 3e 66 69 72 73 74 3d 30 3b 20 65 6c 65 6d  H->first=0; elem
1830: 3b 20 65 6c 65 6d 20 3d 20 6e 65 78 74 5f 65 6c  ; elem = next_el
1840: 65 6d 29 7b 0a 20 20 20 20 69 6e 74 20 68 20 3d  em){.    int h =
1850: 20 28 2a 78 48 61 73 68 29 28 65 6c 65 6d 2d 3e   (*xHash)(elem->
1860: 70 4b 65 79 2c 20 65 6c 65 6d 2d 3e 6e 4b 65 79  pKey, elem->nKey
1870: 29 20 26 20 28 6e 65 77 5f 73 69 7a 65 2d 31 29  ) & (new_size-1)
1880: 3b 0a 20 20 20 20 6e 65 78 74 5f 65 6c 65 6d 20  ;.    next_elem 
1890: 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20  = elem->next;.  
18a0: 20 20 66 74 73 33 48 61 73 68 49 6e 73 65 72 74    fts3HashInsert
18b0: 45 6c 65 6d 65 6e 74 28 70 48 2c 20 26 6e 65 77  Element(pH, &new
18c0: 5f 68 74 5b 68 5d 2c 20 65 6c 65 6d 29 3b 0a 20  _ht[h], elem);. 
18d0: 20 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d   }.  return 0;.}
18e0: 0a 0a 2f 2a 20 54 68 69 73 20 66 75 6e 63 74 69  ../* This functi
18f0: 6f 6e 20 28 66 6f 72 20 69 6e 74 65 72 6e 61 6c  on (for internal
1900: 20 75 73 65 20 6f 6e 6c 79 29 20 6c 6f 63 61 74   use only) locat
1910: 65 73 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69 6e  es an element in
1920: 20 61 6e 0a 2a 2a 20 68 61 73 68 20 74 61 62 6c   an.** hash tabl
1930: 65 20 74 68 61 74 20 6d 61 74 63 68 65 73 20 74  e that matches t
1940: 68 65 20 67 69 76 65 6e 20 6b 65 79 2e 20 20 54  he given key.  T
1950: 68 65 20 68 61 73 68 20 66 6f 72 20 74 68 69 73  he hash for this
1960: 20 6b 65 79 20 68 61 73 0a 2a 2a 20 61 6c 72 65   key has.** alre
1970: 61 64 79 20 62 65 65 6e 20 63 6f 6d 70 75 74 65  ady been compute
1980: 64 20 61 6e 64 20 69 73 20 70 61 73 73 65 64 20  d and is passed 
1990: 61 73 20 74 68 65 20 34 74 68 20 70 61 72 61 6d  as the 4th param
19a0: 65 74 65 72 2e 0a 2a 2f 0a 73 74 61 74 69 63 20  eter..*/.static 
19b0: 46 74 73 33 48 61 73 68 45 6c 65 6d 20 2a 66 74  Fts3HashElem *ft
19c0: 73 33 46 69 6e 64 45 6c 65 6d 65 6e 74 42 79 48  s3FindElementByH
19d0: 61 73 68 28 0a 20 20 63 6f 6e 73 74 20 46 74 73  ash(.  const Fts
19e0: 33 48 61 73 68 20 2a 70 48 2c 20 2f 2a 20 54 68  3Hash *pH, /* Th
19f0: 65 20 70 48 20 74 6f 20 62 65 20 73 65 61 72 63  e pH to be searc
1a00: 68 65 64 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 76  hed */.  const v
1a10: 6f 69 64 20 2a 70 4b 65 79 2c 20 20 20 2f 2a 20  oid *pKey,   /* 
1a20: 54 68 65 20 6b 65 79 20 77 65 20 61 72 65 20 73  The key we are s
1a30: 65 61 72 63 68 69 6e 67 20 66 6f 72 20 2a 2f 0a  earching for */.
1a40: 20 20 69 6e 74 20 6e 4b 65 79 2c 0a 20 20 69 6e    int nKey,.  in
1a50: 74 20 68 20 20 20 20 20 20 20 20 20 20 20 20 20  t h             
1a60: 20 20 2f 2a 20 54 68 65 20 68 61 73 68 20 66 6f    /* The hash fo
1a70: 72 20 74 68 69 73 20 6b 65 79 2e 20 2a 2f 0a 29  r this key. */.)
1a80: 7b 0a 20 20 46 74 73 33 48 61 73 68 45 6c 65 6d  {.  Fts3HashElem
1a90: 20 2a 65 6c 65 6d 3b 20 20 20 20 20 20 20 20 20   *elem;         
1aa0: 20 20 20 2f 2a 20 55 73 65 64 20 74 6f 20 6c 6f     /* Used to lo
1ab0: 6f 70 20 74 68 72 75 20 74 68 65 20 65 6c 65 6d  op thru the elem
1ac0: 65 6e 74 20 6c 69 73 74 20 2a 2f 0a 20 20 69 6e  ent list */.  in
1ad0: 74 20 63 6f 75 6e 74 3b 20 20 20 20 20 20 20 20  t count;        
1ae0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
1af0: 4e 75 6d 62 65 72 20 6f 66 20 65 6c 65 6d 65 6e  Number of elemen
1b00: 74 73 20 6c 65 66 74 20 74 6f 20 74 65 73 74 20  ts left to test 
1b10: 2a 2f 0a 20 20 69 6e 74 20 28 2a 78 43 6f 6d 70  */.  int (*xComp
1b20: 61 72 65 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a  are)(const void*
1b30: 2c 69 6e 74 2c 63 6f 6e 73 74 20 76 6f 69 64 2a  ,int,const void*
1b40: 2c 69 6e 74 29 3b 20 20 2f 2a 20 63 6f 6d 70 61  ,int);  /* compa
1b50: 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 20 2a  rison function *
1b60: 2f 0a 0a 20 20 69 66 28 20 70 48 2d 3e 68 74 20  /..  if( pH->ht 
1b70: 29 7b 0a 20 20 20 20 73 74 72 75 63 74 20 5f 66  ){.    struct _f
1b80: 74 73 33 68 74 20 2a 70 45 6e 74 72 79 20 3d 20  ts3ht *pEntry = 
1b90: 26 70 48 2d 3e 68 74 5b 68 5d 3b 0a 20 20 20 20  &pH->ht[h];.    
1ba0: 65 6c 65 6d 20 3d 20 70 45 6e 74 72 79 2d 3e 63  elem = pEntry->c
1bb0: 68 61 69 6e 3b 0a 20 20 20 20 63 6f 75 6e 74 20  hain;.    count 
1bc0: 3d 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 3b  = pEntry->count;
1bd0: 0a 20 20 20 20 78 43 6f 6d 70 61 72 65 20 3d 20  .    xCompare = 
1be0: 66 74 73 43 6f 6d 70 61 72 65 46 75 6e 63 74 69  ftsCompareFuncti
1bf0: 6f 6e 28 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29  on(pH->keyClass)
1c00: 3b 0a 20 20 20 20 77 68 69 6c 65 28 20 63 6f 75  ;.    while( cou
1c10: 6e 74 2d 2d 20 26 26 20 65 6c 65 6d 20 29 7b 0a  nt-- && elem ){.
1c20: 20 20 20 20 20 20 69 66 28 20 28 2a 78 43 6f 6d        if( (*xCom
1c30: 70 61 72 65 29 28 65 6c 65 6d 2d 3e 70 4b 65 79  pare)(elem->pKey
1c40: 2c 65 6c 65 6d 2d 3e 6e 4b 65 79 2c 70 4b 65 79  ,elem->nKey,pKey
1c50: 2c 6e 4b 65 79 29 3d 3d 30 20 29 7b 20 0a 20 20  ,nKey)==0 ){ .  
1c60: 20 20 20 20 20 20 72 65 74 75 72 6e 20 65 6c 65        return ele
1c70: 6d 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20  m;.      }.     
1c80: 20 65 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65   elem = elem->ne
1c90: 78 74 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20  xt;.    }.  }.  
1ca0: 72 65 74 75 72 6e 20 30 3b 0a 7d 0a 0a 2f 2a 20  return 0;.}../* 
1cb0: 52 65 6d 6f 76 65 20 61 20 73 69 6e 67 6c 65 20  Remove a single 
1cc0: 65 6e 74 72 79 20 66 72 6f 6d 20 74 68 65 20 68  entry from the h
1cd0: 61 73 68 20 74 61 62 6c 65 20 67 69 76 65 6e 20  ash table given 
1ce0: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 61  a pointer to tha
1cf0: 74 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 61 6e 64  t.** element and
1d00: 20 61 20 68 61 73 68 20 6f 6e 20 74 68 65 20 65   a hash on the e
1d10: 6c 65 6d 65 6e 74 27 73 20 6b 65 79 2e 0a 2a 2f  lement's key..*/
1d20: 0a 73 74 61 74 69 63 20 76 6f 69 64 20 66 74 73  .static void fts
1d30: 33 52 65 6d 6f 76 65 45 6c 65 6d 65 6e 74 42 79  3RemoveElementBy
1d40: 48 61 73 68 28 0a 20 20 46 74 73 33 48 61 73 68  Hash(.  Fts3Hash
1d50: 20 2a 70 48 2c 20 20 20 20 20 20 20 20 20 2f 2a   *pH,         /*
1d60: 20 54 68 65 20 70 48 20 63 6f 6e 74 61 69 6e 69   The pH containi
1d70: 6e 67 20 22 65 6c 65 6d 22 20 2a 2f 0a 20 20 46  ng "elem" */.  F
1d80: 74 73 33 48 61 73 68 45 6c 65 6d 2a 20 65 6c 65  ts3HashElem* ele
1d90: 6d 2c 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d  m,   /* The elem
1da0: 65 6e 74 20 74 6f 20 62 65 20 72 65 6d 6f 76 65  ent to be remove
1db0: 64 20 66 72 6f 6d 20 74 68 65 20 70 48 20 2a 2f  d from the pH */
1dc0: 0a 20 20 69 6e 74 20 68 20 20 20 20 20 20 20 20  .  int h        
1dd0: 20 20 20 20 20 20 20 20 20 2f 2a 20 48 61 73 68           /* Hash
1de0: 20 76 61 6c 75 65 20 66 6f 72 20 74 68 65 20 65   value for the e
1df0: 6c 65 6d 65 6e 74 20 2a 2f 0a 29 7b 0a 20 20 73  lement */.){.  s
1e00: 74 72 75 63 74 20 5f 66 74 73 33 68 74 20 2a 70  truct _fts3ht *p
1e10: 45 6e 74 72 79 3b 0a 20 20 69 66 28 20 65 6c 65  Entry;.  if( ele
1e20: 6d 2d 3e 70 72 65 76 20 29 7b 0a 20 20 20 20 65  m->prev ){.    e
1e30: 6c 65 6d 2d 3e 70 72 65 76 2d 3e 6e 65 78 74 20  lem->prev->next 
1e40: 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 20 0a 20  = elem->next; . 
1e50: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 70 48 2d 3e   }else{.    pH->
1e60: 66 69 72 73 74 20 3d 20 65 6c 65 6d 2d 3e 6e 65  first = elem->ne
1e70: 78 74 3b 0a 20 20 7d 0a 20 20 69 66 28 20 65 6c  xt;.  }.  if( el
1e80: 65 6d 2d 3e 6e 65 78 74 20 29 7b 0a 20 20 20 20  em->next ){.    
1e90: 65 6c 65 6d 2d 3e 6e 65 78 74 2d 3e 70 72 65 76  elem->next->prev
1ea0: 20 3d 20 65 6c 65 6d 2d 3e 70 72 65 76 3b 0a 20   = elem->prev;. 
1eb0: 20 7d 0a 20 20 70 45 6e 74 72 79 20 3d 20 26 70   }.  pEntry = &p
1ec0: 48 2d 3e 68 74 5b 68 5d 3b 0a 20 20 69 66 28 20  H->ht[h];.  if( 
1ed0: 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3d 3d 65  pEntry->chain==e
1ee0: 6c 65 6d 20 29 7b 0a 20 20 20 20 70 45 6e 74 72  lem ){.    pEntr
1ef0: 79 2d 3e 63 68 61 69 6e 20 3d 20 65 6c 65 6d 2d  y->chain = elem-
1f00: 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20 20 70 45 6e  >next;.  }.  pEn
1f10: 74 72 79 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a 20 20  try->count--;.  
1f20: 69 66 28 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e  if( pEntry->coun
1f30: 74 3c 3d 30 20 29 7b 0a 20 20 20 20 70 45 6e 74  t<=0 ){.    pEnt
1f40: 72 79 2d 3e 63 68 61 69 6e 20 3d 20 30 3b 0a 20  ry->chain = 0;. 
1f50: 20 7d 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f 70   }.  if( pH->cop
1f60: 79 4b 65 79 20 26 26 20 65 6c 65 6d 2d 3e 70 4b  yKey && elem->pK
1f70: 65 79 20 29 7b 0a 20 20 20 20 66 74 73 33 48 61  ey ){.    fts3Ha
1f80: 73 68 46 72 65 65 28 65 6c 65 6d 2d 3e 70 4b 65  shFree(elem->pKe
1f90: 79 29 3b 0a 20 20 7d 0a 20 20 66 74 73 33 48 61  y);.  }.  fts3Ha
1fa0: 73 68 46 72 65 65 28 20 65 6c 65 6d 20 29 3b 0a  shFree( elem );.
1fb0: 20 20 70 48 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a 20    pH->count--;. 
1fc0: 20 69 66 28 20 70 48 2d 3e 63 6f 75 6e 74 3c 3d   if( pH->count<=
1fd0: 30 20 29 7b 0a 20 20 20 20 61 73 73 65 72 74 28  0 ){.    assert(
1fe0: 20 70 48 2d 3e 66 69 72 73 74 3d 3d 30 20 29 3b   pH->first==0 );
1ff0: 0a 20 20 20 20 61 73 73 65 72 74 28 20 70 48 2d  .    assert( pH-
2000: 3e 63 6f 75 6e 74 3d 3d 30 20 29 3b 0a 20 20 20  >count==0 );.   
2010: 20 66 74 73 33 48 61 73 68 43 6c 65 61 72 28 70   fts3HashClear(p
2020: 48 29 3b 0a 20 20 7d 0a 7d 0a 0a 46 74 73 33 48  H);.  }.}..Fts3H
2030: 61 73 68 45 6c 65 6d 20 2a 73 71 6c 69 74 65 33  ashElem *sqlite3
2040: 46 74 73 33 48 61 73 68 46 69 6e 64 45 6c 65 6d  Fts3HashFindElem
2050: 28 0a 20 20 63 6f 6e 73 74 20 46 74 73 33 48 61  (.  const Fts3Ha
2060: 73 68 20 2a 70 48 2c 20 0a 20 20 63 6f 6e 73 74  sh *pH, .  const
2070: 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 0a 20 20   void *pKey, .  
2080: 69 6e 74 20 6e 4b 65 79 0a 29 7b 0a 20 20 69 6e  int nKey.){.  in
2090: 74 20 68 3b 20 20 20 20 20 20 20 20 20 20 20 20  t h;            
20a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
20b0: 20 41 20 68 61 73 68 20 6f 6e 20 6b 65 79 20 2a   A hash on key *
20c0: 2f 0a 20 20 69 6e 74 20 28 2a 78 48 61 73 68 29  /.  int (*xHash)
20d0: 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74  (const void*,int
20e0: 29 3b 20 20 2f 2a 20 54 68 65 20 68 61 73 68 20  );  /* The hash 
20f0: 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20 69  function */..  i
2100: 66 28 20 70 48 3d 3d 30 20 7c 7c 20 70 48 2d 3e  f( pH==0 || pH->
2110: 68 74 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 30  ht==0 ) return 0
2120: 3b 0a 20 20 78 48 61 73 68 20 3d 20 66 74 73 48  ;.  xHash = ftsH
2130: 61 73 68 46 75 6e 63 74 69 6f 6e 28 70 48 2d 3e  ashFunction(pH->
2140: 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20 61 73 73  keyClass);.  ass
2150: 65 72 74 28 20 78 48 61 73 68 21 3d 30 20 29 3b  ert( xHash!=0 );
2160: 0a 20 20 68 20 3d 20 28 2a 78 48 61 73 68 29 28  .  h = (*xHash)(
2170: 70 4b 65 79 2c 6e 4b 65 79 29 3b 0a 20 20 61 73  pKey,nKey);.  as
2180: 73 65 72 74 28 20 28 70 48 2d 3e 68 74 73 69 7a  sert( (pH->htsiz
2190: 65 20 26 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d  e & (pH->htsize-
21a0: 31 29 29 3d 3d 30 20 29 3b 0a 20 20 72 65 74 75  1))==0 );.  retu
21b0: 72 6e 20 66 74 73 33 46 69 6e 64 45 6c 65 6d 65  rn fts3FindEleme
21c0: 6e 74 42 79 48 61 73 68 28 70 48 2c 70 4b 65 79  ntByHash(pH,pKey
21d0: 2c 6e 4b 65 79 2c 20 68 20 26 20 28 70 48 2d 3e  ,nKey, h & (pH->
21e0: 68 74 73 69 7a 65 2d 31 29 29 3b 0a 7d 0a 0a 2f  htsize-1));.}../
21f0: 2a 20 0a 2a 2a 20 41 74 74 65 6d 70 74 20 74 6f  * .** Attempt to
2200: 20 6c 6f 63 61 74 65 20 61 6e 20 65 6c 65 6d 65   locate an eleme
2210: 6e 74 20 6f 66 20 74 68 65 20 68 61 73 68 20 74  nt of the hash t
2220: 61 62 6c 65 20 70 48 20 77 69 74 68 20 61 20 6b  able pH with a k
2230: 65 79 0a 2a 2a 20 74 68 61 74 20 6d 61 74 63 68  ey.** that match
2240: 65 73 20 70 4b 65 79 2c 6e 4b 65 79 2e 20 20 52  es pKey,nKey.  R
2250: 65 74 75 72 6e 20 74 68 65 20 64 61 74 61 20 66  eturn the data f
2260: 6f 72 20 74 68 69 73 20 65 6c 65 6d 65 6e 74 20  or this element 
2270: 69 66 20 69 74 20 69 73 0a 2a 2a 20 66 6f 75 6e  if it is.** foun
2280: 64 2c 20 6f 72 20 4e 55 4c 4c 20 69 66 20 74 68  d, or NULL if th
2290: 65 72 65 20 69 73 20 6e 6f 20 6d 61 74 63 68 2e  ere is no match.
22a0: 0a 2a 2f 0a 76 6f 69 64 20 2a 73 71 6c 69 74 65  .*/.void *sqlite
22b0: 33 46 74 73 33 48 61 73 68 46 69 6e 64 28 63 6f  3Fts3HashFind(co
22c0: 6e 73 74 20 46 74 73 33 48 61 73 68 20 2a 70 48  nst Fts3Hash *pH
22d0: 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b  , const void *pK
22e0: 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20  ey, int nKey){. 
22f0: 20 46 74 73 33 48 61 73 68 45 6c 65 6d 20 2a 70   Fts3HashElem *p
2300: 45 6c 65 6d 3b 20 20 20 20 20 20 20 20 20 20 20  Elem;           
2310: 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e 74 20   /* The element 
2320: 74 68 61 74 20 6d 61 74 63 68 65 73 20 6b 65 79  that matches key
2330: 20 28 69 66 20 61 6e 79 29 20 2a 2f 0a 0a 20 20   (if any) */..  
2340: 70 45 6c 65 6d 20 3d 20 73 71 6c 69 74 65 33 46  pElem = sqlite3F
2350: 74 73 33 48 61 73 68 46 69 6e 64 45 6c 65 6d 28  ts3HashFindElem(
2360: 70 48 2c 20 70 4b 65 79 2c 20 6e 4b 65 79 29 3b  pH, pKey, nKey);
2370: 0a 20 20 72 65 74 75 72 6e 20 70 45 6c 65 6d 20  .  return pElem 
2380: 3f 20 70 45 6c 65 6d 2d 3e 64 61 74 61 20 3a 20  ? pElem->data : 
2390: 30 3b 0a 7d 0a 0a 2f 2a 20 49 6e 73 65 72 74 20  0;.}../* Insert 
23a0: 61 6e 20 65 6c 65 6d 65 6e 74 20 69 6e 74 6f 20  an element into 
23b0: 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 70  the hash table p
23c0: 48 2e 20 20 54 68 65 20 6b 65 79 20 69 73 20 70  H.  The key is p
23d0: 4b 65 79 2c 6e 4b 65 79 0a 2a 2a 20 61 6e 64 20  Key,nKey.** and 
23e0: 74 68 65 20 64 61 74 61 20 69 73 20 22 64 61 74  the data is "dat
23f0: 61 22 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 6e 6f 20  a"..**.** If no 
2400: 65 6c 65 6d 65 6e 74 20 65 78 69 73 74 73 20 77  element exists w
2410: 69 74 68 20 61 20 6d 61 74 63 68 69 6e 67 20 6b  ith a matching k
2420: 65 79 2c 20 74 68 65 6e 20 61 20 6e 65 77 0a 2a  ey, then a new.*
2430: 2a 20 65 6c 65 6d 65 6e 74 20 69 73 20 63 72 65  * element is cre
2440: 61 74 65 64 2e 20 20 41 20 63 6f 70 79 20 6f 66  ated.  A copy of
2450: 20 74 68 65 20 6b 65 79 20 69 73 20 6d 61 64 65   the key is made
2460: 20 69 66 20 74 68 65 20 63 6f 70 79 4b 65 79 0a   if the copyKey.
2470: 2a 2a 20 66 6c 61 67 20 69 73 20 73 65 74 2e 20  ** flag is set. 
2480: 20 4e 55 4c 4c 20 69 73 20 72 65 74 75 72 6e 65   NULL is returne
2490: 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 61 6e 6f 74  d..**.** If anot
24a0: 68 65 72 20 65 6c 65 6d 65 6e 74 20 61 6c 72 65  her element alre
24b0: 61 64 79 20 65 78 69 73 74 73 20 77 69 74 68 20  ady exists with 
24c0: 74 68 65 20 73 61 6d 65 20 6b 65 79 2c 20 74 68  the same key, th
24d0: 65 6e 20 74 68 65 0a 2a 2a 20 6e 65 77 20 64 61  en the.** new da
24e0: 74 61 20 72 65 70 6c 61 63 65 73 20 74 68 65 20  ta replaces the 
24f0: 6f 6c 64 20 64 61 74 61 20 61 6e 64 20 74 68 65  old data and the
2500: 20 6f 6c 64 20 64 61 74 61 20 69 73 20 72 65 74   old data is ret
2510: 75 72 6e 65 64 2e 0a 2a 2a 20 54 68 65 20 6b 65  urned..** The ke
2520: 79 20 69 73 20 6e 6f 74 20 63 6f 70 69 65 64 20  y is not copied 
2530: 69 6e 20 74 68 69 73 20 69 6e 73 74 61 6e 63 65  in this instance
2540: 2e 20 20 49 66 20 61 20 6d 61 6c 6c 6f 63 20 66  .  If a malloc f
2550: 61 69 6c 73 2c 20 74 68 65 6e 0a 2a 2a 20 74 68  ails, then.** th
2560: 65 20 6e 65 77 20 64 61 74 61 20 69 73 20 72 65  e new data is re
2570: 74 75 72 6e 65 64 20 61 6e 64 20 74 68 65 20 68  turned and the h
2580: 61 73 68 20 74 61 62 6c 65 20 69 73 20 75 6e 63  ash table is unc
2590: 68 61 6e 67 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66  hanged..**.** If
25a0: 20 74 68 65 20 22 64 61 74 61 22 20 70 61 72 61   the "data" para
25b0: 6d 65 74 65 72 20 74 6f 20 74 68 69 73 20 66 75  meter to this fu
25c0: 6e 63 74 69 6f 6e 20 69 73 20 4e 55 4c 4c 2c 20  nction is NULL, 
25d0: 74 68 65 6e 20 74 68 65 0a 2a 2a 20 65 6c 65 6d  then the.** elem
25e0: 65 6e 74 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e  ent correspondin
25f0: 67 20 74 6f 20 22 6b 65 79 22 20 69 73 20 72 65  g to "key" is re
2600: 6d 6f 76 65 64 20 66 72 6f 6d 20 74 68 65 20 68  moved from the h
2610: 61 73 68 20 74 61 62 6c 65 2e 0a 2a 2f 0a 76 6f  ash table..*/.vo
2620: 69 64 20 2a 73 71 6c 69 74 65 33 46 74 73 33 48  id *sqlite3Fts3H
2630: 61 73 68 49 6e 73 65 72 74 28 0a 20 20 46 74 73  ashInsert(.  Fts
2640: 33 48 61 73 68 20 2a 70 48 2c 20 20 20 20 20 20  3Hash *pH,      
2650: 20 20 2f 2a 20 54 68 65 20 68 61 73 68 20 74 61    /* The hash ta
2660: 62 6c 65 20 74 6f 20 69 6e 73 65 72 74 20 69 6e  ble to insert in
2670: 74 6f 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 76 6f  to */.  const vo
2680: 69 64 20 2a 70 4b 65 79 2c 20 20 20 20 2f 2a 20  id *pKey,    /* 
2690: 54 68 65 20 6b 65 79 20 2a 2f 0a 20 20 69 6e 74  The key */.  int
26a0: 20 6e 4b 65 79 2c 20 20 20 20 20 20 20 20 20 20   nKey,          
26b0: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 62    /* Number of b
26c0: 79 74 65 73 20 69 6e 20 74 68 65 20 6b 65 79 20  ytes in the key 
26d0: 2a 2f 0a 20 20 76 6f 69 64 20 2a 64 61 74 61 20  */.  void *data 
26e0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65            /* The
26f0: 20 64 61 74 61 20 2a 2f 0a 29 7b 0a 20 20 69 6e   data */.){.  in
2700: 74 20 68 72 61 77 3b 20 20 20 20 20 20 20 20 20  t hraw;         
2710: 20 20 20 20 20 20 20 20 2f 2a 20 52 61 77 20 68          /* Raw h
2720: 61 73 68 20 76 61 6c 75 65 20 6f 66 20 74 68 65  ash value of the
2730: 20 6b 65 79 20 2a 2f 0a 20 20 69 6e 74 20 68 3b   key */.  int h;
2740: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2750: 20 20 20 20 2f 2a 20 74 68 65 20 68 61 73 68 20      /* the hash 
2760: 6f 66 20 74 68 65 20 6b 65 79 20 6d 6f 64 75 6c  of the key modul
2770: 6f 20 68 61 73 68 20 74 61 62 6c 65 20 73 69 7a  o hash table siz
2780: 65 20 2a 2f 0a 20 20 46 74 73 33 48 61 73 68 45  e */.  Fts3HashE
2790: 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 20 20  lem *elem;      
27a0: 20 2f 2a 20 55 73 65 64 20 74 6f 20 6c 6f 6f 70   /* Used to loop
27b0: 20 74 68 72 75 20 74 68 65 20 65 6c 65 6d 65 6e   thru the elemen
27c0: 74 20 6c 69 73 74 20 2a 2f 0a 20 20 46 74 73 33  t list */.  Fts3
27d0: 48 61 73 68 45 6c 65 6d 20 2a 6e 65 77 5f 65 6c  HashElem *new_el
27e0: 65 6d 3b 20 20 20 2f 2a 20 4e 65 77 20 65 6c 65  em;   /* New ele
27f0: 6d 65 6e 74 20 61 64 64 65 64 20 74 6f 20 74 68  ment added to th
2800: 65 20 70 48 20 2a 2f 0a 20 20 69 6e 74 20 28 2a  e pH */.  int (*
2810: 78 48 61 73 68 29 28 63 6f 6e 73 74 20 76 6f 69  xHash)(const voi
2820: 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a 20 54 68 65  d*,int);  /* The
2830: 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 2a   hash function *
2840: 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 70 48 21  /..  assert( pH!
2850: 3d 30 20 29 3b 0a 20 20 78 48 61 73 68 20 3d 20  =0 );.  xHash = 
2860: 66 74 73 48 61 73 68 46 75 6e 63 74 69 6f 6e 28  ftsHashFunction(
2870: 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20  pH->keyClass);. 
2880: 20 61 73 73 65 72 74 28 20 78 48 61 73 68 21 3d   assert( xHash!=
2890: 30 20 29 3b 0a 20 20 68 72 61 77 20 3d 20 28 2a  0 );.  hraw = (*
28a0: 78 48 61 73 68 29 28 70 4b 65 79 2c 20 6e 4b 65  xHash)(pKey, nKe
28b0: 79 29 3b 0a 20 20 61 73 73 65 72 74 28 20 28 70  y);.  assert( (p
28c0: 48 2d 3e 68 74 73 69 7a 65 20 26 20 28 70 48 2d  H->htsize & (pH-
28d0: 3e 68 74 73 69 7a 65 2d 31 29 29 3d 3d 30 20 29  >htsize-1))==0 )
28e0: 3b 0a 20 20 68 20 3d 20 68 72 61 77 20 26 20 28  ;.  h = hraw & (
28f0: 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29 3b 0a 20  pH->htsize-1);. 
2900: 20 65 6c 65 6d 20 3d 20 66 74 73 33 46 69 6e 64   elem = fts3Find
2910: 45 6c 65 6d 65 6e 74 42 79 48 61 73 68 28 70 48  ElementByHash(pH
2920: 2c 70 4b 65 79 2c 6e 4b 65 79 2c 68 29 3b 0a 20  ,pKey,nKey,h);. 
2930: 20 69 66 28 20 65 6c 65 6d 20 29 7b 0a 20 20 20   if( elem ){.   
2940: 20 76 6f 69 64 20 2a 6f 6c 64 5f 64 61 74 61 20   void *old_data 
2950: 3d 20 65 6c 65 6d 2d 3e 64 61 74 61 3b 0a 20 20  = elem->data;.  
2960: 20 20 69 66 28 20 64 61 74 61 3d 3d 30 20 29 7b    if( data==0 ){
2970: 0a 20 20 20 20 20 20 66 74 73 33 52 65 6d 6f 76  .      fts3Remov
2980: 65 45 6c 65 6d 65 6e 74 42 79 48 61 73 68 28 70  eElementByHash(p
2990: 48 2c 65 6c 65 6d 2c 68 29 3b 0a 20 20 20 20 7d  H,elem,h);.    }
29a0: 65 6c 73 65 7b 0a 20 20 20 20 20 20 65 6c 65 6d  else{.      elem
29b0: 2d 3e 64 61 74 61 20 3d 20 64 61 74 61 3b 0a 20  ->data = data;. 
29c0: 20 20 20 7d 0a 20 20 20 20 72 65 74 75 72 6e 20     }.    return 
29d0: 6f 6c 64 5f 64 61 74 61 3b 0a 20 20 7d 0a 20 20  old_data;.  }.  
29e0: 69 66 28 20 64 61 74 61 3d 3d 30 20 29 20 72 65  if( data==0 ) re
29f0: 74 75 72 6e 20 30 3b 0a 20 20 69 66 28 20 28 70  turn 0;.  if( (p
2a00: 48 2d 3e 68 74 73 69 7a 65 3d 3d 30 20 26 26 20  H->htsize==0 && 
2a10: 66 74 73 33 52 65 68 61 73 68 28 70 48 2c 38 29  fts3Rehash(pH,8)
2a20: 29 0a 20 20 20 7c 7c 20 28 70 48 2d 3e 63 6f 75  ).   || (pH->cou
2a30: 6e 74 3e 3d 70 48 2d 3e 68 74 73 69 7a 65 20 26  nt>=pH->htsize &
2a40: 26 20 66 74 73 33 52 65 68 61 73 68 28 70 48 2c  & fts3Rehash(pH,
2a50: 20 70 48 2d 3e 68 74 73 69 7a 65 2a 32 29 29 0a   pH->htsize*2)).
2a60: 20 20 29 7b 0a 20 20 20 20 70 48 2d 3e 63 6f 75    ){.    pH->cou
2a70: 6e 74 20 3d 20 30 3b 0a 20 20 20 20 72 65 74 75  nt = 0;.    retu
2a80: 72 6e 20 64 61 74 61 3b 0a 20 20 7d 0a 20 20 61  rn data;.  }.  a
2a90: 73 73 65 72 74 28 20 70 48 2d 3e 68 74 73 69 7a  ssert( pH->htsiz
2aa0: 65 3e 30 20 29 3b 0a 20 20 6e 65 77 5f 65 6c 65  e>0 );.  new_ele
2ab0: 6d 20 3d 20 28 46 74 73 33 48 61 73 68 45 6c 65  m = (Fts3HashEle
2ac0: 6d 2a 29 66 74 73 33 48 61 73 68 4d 61 6c 6c 6f  m*)fts3HashMallo
2ad0: 63 28 20 73 69 7a 65 6f 66 28 46 74 73 33 48 61  c( sizeof(Fts3Ha
2ae0: 73 68 45 6c 65 6d 29 20 29 3b 0a 20 20 69 66 28  shElem) );.  if(
2af0: 20 6e 65 77 5f 65 6c 65 6d 3d 3d 30 20 29 20 72   new_elem==0 ) r
2b00: 65 74 75 72 6e 20 64 61 74 61 3b 0a 20 20 69 66  eturn data;.  if
2b10: 28 20 70 48 2d 3e 63 6f 70 79 4b 65 79 20 26 26  ( pH->copyKey &&
2b20: 20 70 4b 65 79 21 3d 30 20 29 7b 0a 20 20 20 20   pKey!=0 ){.    
2b30: 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 20 3d  new_elem->pKey =
2b40: 20 66 74 73 33 48 61 73 68 4d 61 6c 6c 6f 63 28   fts3HashMalloc(
2b50: 20 6e 4b 65 79 20 29 3b 0a 20 20 20 20 69 66 28   nKey );.    if(
2b60: 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 3d   new_elem->pKey=
2b70: 3d 30 20 29 7b 0a 20 20 20 20 20 20 66 74 73 33  =0 ){.      fts3
2b80: 48 61 73 68 46 72 65 65 28 6e 65 77 5f 65 6c 65  HashFree(new_ele
2b90: 6d 29 3b 0a 20 20 20 20 20 20 72 65 74 75 72 6e  m);.      return
2ba0: 20 64 61 74 61 3b 0a 20 20 20 20 7d 0a 20 20 20   data;.    }.   
2bb0: 20 6d 65 6d 63 70 79 28 28 76 6f 69 64 2a 29 6e   memcpy((void*)n
2bc0: 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 2c 20 70  ew_elem->pKey, p
2bd0: 4b 65 79 2c 20 6e 4b 65 79 29 3b 0a 20 20 7d 65  Key, nKey);.  }e
2be0: 6c 73 65 7b 0a 20 20 20 20 6e 65 77 5f 65 6c 65  lse{.    new_ele
2bf0: 6d 2d 3e 70 4b 65 79 20 3d 20 28 76 6f 69 64 2a  m->pKey = (void*
2c00: 29 70 4b 65 79 3b 0a 20 20 7d 0a 20 20 6e 65 77  )pKey;.  }.  new
2c10: 5f 65 6c 65 6d 2d 3e 6e 4b 65 79 20 3d 20 6e 4b  _elem->nKey = nK
2c20: 65 79 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 2b  ey;.  pH->count+
2c30: 2b 3b 0a 20 20 61 73 73 65 72 74 28 20 70 48 2d  +;.  assert( pH-
2c40: 3e 68 74 73 69 7a 65 3e 30 20 29 3b 0a 20 20 61  >htsize>0 );.  a
2c50: 73 73 65 72 74 28 20 28 70 48 2d 3e 68 74 73 69  ssert( (pH->htsi
2c60: 7a 65 20 26 20 28 70 48 2d 3e 68 74 73 69 7a 65  ze & (pH->htsize
2c70: 2d 31 29 29 3d 3d 30 20 29 3b 0a 20 20 68 20 3d  -1))==0 );.  h =
2c80: 20 68 72 61 77 20 26 20 28 70 48 2d 3e 68 74 73   hraw & (pH->hts
2c90: 69 7a 65 2d 31 29 3b 0a 20 20 66 74 73 33 48 61  ize-1);.  fts3Ha
2ca0: 73 68 49 6e 73 65 72 74 45 6c 65 6d 65 6e 74 28  shInsertElement(
2cb0: 70 48 2c 20 26 70 48 2d 3e 68 74 5b 68 5d 2c 20  pH, &pH->ht[h], 
2cc0: 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20 20 6e 65 77  new_elem);.  new
2cd0: 5f 65 6c 65 6d 2d 3e 64 61 74 61 20 3d 20 64 61  _elem->data = da
2ce0: 74 61 3b 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a  ta;.  return 0;.
2cf0: 7d 0a 0a 23 65 6e 64 69 66 20 2f 2a 20 21 64 65  }..#endif /* !de
2d00: 66 69 6e 65 64 28 53 51 4c 49 54 45 5f 43 4f 52  fined(SQLITE_COR
2d10: 45 29 20 7c 7c 20 64 65 66 69 6e 65 64 28 53 51  E) || defined(SQ
2d20: 4c 49 54 45 5f 45 4e 41 42 4c 45 5f 46 54 53 33  LITE_ENABLE_FTS3
2d30: 29 20 2a 2f 0a                                   ) */.