/ Hex Artifact Content
Login

Artifact 880998e596b60f078348d48732ca4ad9a90caad2:


0000: 2f 2a 0a 2a 2a 20 32 30 31 34 20 41 75 67 75 73  /*.** 2014 Augus
0010: 74 20 31 31 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61  t 11.**.** The a
0020: 75 74 68 6f 72 20 64 69 73 63 6c 61 69 6d 73 20  uthor disclaims 
0030: 63 6f 70 79 72 69 67 68 74 20 74 6f 20 74 68 69  copyright to thi
0040: 73 20 73 6f 75 72 63 65 20 63 6f 64 65 2e 20 20  s source code.  
0050: 49 6e 20 70 6c 61 63 65 20 6f 66 0a 2a 2a 20 61  In place of.** a
0060: 20 6c 65 67 61 6c 20 6e 6f 74 69 63 65 2c 20 68   legal notice, h
0070: 65 72 65 20 69 73 20 61 20 62 6c 65 73 73 69 6e  ere is a blessin
0080: 67 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 4d 61 79 20  g:.**.**    May 
0090: 79 6f 75 20 64 6f 20 67 6f 6f 64 20 61 6e 64 20  you do good and 
00a0: 6e 6f 74 20 65 76 69 6c 2e 0a 2a 2a 20 20 20 20  not evil..**    
00b0: 4d 61 79 20 79 6f 75 20 66 69 6e 64 20 66 6f 72  May you find for
00c0: 67 69 76 65 6e 65 73 73 20 66 6f 72 20 79 6f 75  giveness for you
00d0: 72 73 65 6c 66 20 61 6e 64 20 66 6f 72 67 69 76  rself and forgiv
00e0: 65 20 6f 74 68 65 72 73 2e 0a 2a 2a 20 20 20 20  e others..**    
00f0: 4d 61 79 20 79 6f 75 20 73 68 61 72 65 20 66 72  May you share fr
0100: 65 65 6c 79 2c 20 6e 65 76 65 72 20 74 61 6b 69  eely, never taki
0110: 6e 67 20 6d 6f 72 65 20 74 68 61 6e 20 79 6f 75  ng more than you
0120: 20 67 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a   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 2a 2a 0a 2a 2a 0a 2a 2f 0a 0a  ********.**.*/..
0180: 0a 0a 23 69 6e 63 6c 75 64 65 20 22 66 74 73 35  ..#include "fts5
0190: 49 6e 74 2e 68 22 0a 0a 74 79 70 65 64 65 66 20  Int.h"..typedef 
01a0: 73 74 72 75 63 74 20 46 74 73 35 48 61 73 68 45  struct Fts5HashE
01b0: 6e 74 72 79 20 46 74 73 35 48 61 73 68 45 6e 74  ntry Fts5HashEnt
01c0: 72 79 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20  ry;../*.** This 
01d0: 66 69 6c 65 20 63 6f 6e 74 61 69 6e 73 20 74 68  file contains th
01e0: 65 20 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e  e implementation
01f0: 20 6f 66 20 61 6e 20 69 6e 2d 6d 65 6d 6f 72 79   of an in-memory
0200: 20 68 61 73 68 20 74 61 62 6c 65 20 75 73 65 64   hash table used
0210: 0a 2a 2a 20 74 6f 20 61 63 63 75 6d 75 6c 75 61  .** to accumulua
0220: 74 65 20 22 74 65 72 6d 20 2d 3e 20 64 6f 63 6c  te "term -> docl
0230: 69 73 74 22 20 63 6f 6e 74 65 6e 74 20 62 65 66  ist" content bef
0240: 6f 72 65 20 69 74 20 69 73 20 66 6c 75 73 65 64  ore it is flused
0250: 20 74 6f 20 61 20 6c 65 76 65 6c 2d 30 0a 2a 2a   to a level-0.**
0260: 20 73 65 67 6d 65 6e 74 2e 0a 2a 2f 0a 0a 0a 73   segment..*/...s
0270: 74 72 75 63 74 20 46 74 73 35 48 61 73 68 20 7b  truct Fts5Hash {
0280: 0a 20 20 69 6e 74 20 65 44 65 74 61 69 6c 3b 20  .  int eDetail; 
0290: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
02a0: 20 20 20 2f 2a 20 43 6f 70 79 20 6f 66 20 46 74     /* Copy of Ft
02b0: 73 35 43 6f 6e 66 69 67 2e 65 44 65 74 61 69 6c  s5Config.eDetail
02c0: 20 2a 2f 0a 20 20 69 6e 74 20 2a 70 6e 42 79 74   */.  int *pnByt
02d0: 65 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  e;              
02e0: 20 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72        /* Pointer
02f0: 20 74 6f 20 62 79 74 65 73 20 63 6f 75 6e 74 65   to bytes counte
0300: 72 20 2a 2f 0a 20 20 69 6e 74 20 6e 45 6e 74 72  r */.  int nEntr
0310: 79 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  y;              
0320: 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72         /* Number
0330: 20 6f 66 20 65 6e 74 72 69 65 73 20 63 75 72 72   of entries curr
0340: 65 6e 74 6c 79 20 69 6e 20 68 61 73 68 20 2a 2f  ently in hash */
0350: 0a 20 20 69 6e 74 20 6e 53 6c 6f 74 3b 20 20 20  .  int nSlot;   
0360: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0370: 20 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 61 53     /* Size of aS
0380: 6c 6f 74 5b 5d 20 61 72 72 61 79 20 2a 2f 0a 20  lot[] array */. 
0390: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
03a0: 70 53 63 61 6e 3b 20 20 20 20 20 20 20 20 20 20  pScan;          
03b0: 20 2f 2a 20 43 75 72 72 65 6e 74 20 6f 72 64 65   /* Current orde
03c0: 72 65 64 20 73 63 61 6e 20 69 74 65 6d 20 2a 2f  red scan item */
03d0: 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  .  Fts5HashEntry
03e0: 20 2a 2a 61 53 6c 6f 74 3b 20 20 20 20 20 20 20   **aSlot;       
03f0: 20 20 20 2f 2a 20 41 72 72 61 79 20 6f 66 20 68     /* Array of h
0400: 61 73 68 20 73 6c 6f 74 73 20 2a 2f 0a 7d 3b 0a  ash slots */.};.
0410: 0a 2f 2a 0a 2a 2a 20 45 61 63 68 20 65 6e 74 72  ./*.** Each entr
0420: 79 20 69 6e 20 74 68 65 20 68 61 73 68 20 74 61  y in the hash ta
0430: 62 6c 65 20 69 73 20 72 65 70 72 65 73 65 6e 74  ble is represent
0440: 65 64 20 62 79 20 61 6e 20 6f 62 6a 65 63 74 20  ed by an object 
0450: 6f 66 20 74 68 65 20 0a 2a 2a 20 66 6f 6c 6c 6f  of the .** follo
0460: 77 69 6e 67 20 74 79 70 65 2e 20 45 61 63 68 20  wing type. Each 
0470: 6f 62 6a 65 63 74 2c 20 69 74 73 20 6b 65 79 20  object, its key 
0480: 28 7a 4b 65 79 5b 5d 29 20 61 6e 64 20 69 74 73  (zKey[]) and its
0490: 20 63 75 72 72 65 6e 74 20 64 61 74 61 0a 2a 2a   current data.**
04a0: 20 61 72 65 20 73 74 6f 72 65 64 20 69 6e 20 61   are stored in a
04b0: 20 73 69 6e 67 6c 65 20 6d 65 6d 6f 72 79 20 61   single memory a
04c0: 6c 6c 6f 63 61 74 69 6f 6e 2e 20 54 68 65 20 70  llocation. The p
04d0: 6f 73 69 74 69 6f 6e 20 6c 69 73 74 20 64 61 74  osition list dat
04e0: 61 20 0a 2a 2a 20 69 6d 6d 65 64 69 61 74 65 6c  a .** immediatel
04f0: 79 20 66 6f 6c 6c 6f 77 73 20 74 68 65 20 6b 65  y follows the ke
0500: 79 20 64 61 74 61 20 69 6e 20 6d 65 6d 6f 72 79  y data in memory
0510: 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 64 61 74 61  ..**.** The data
0520: 20 74 68 61 74 20 66 6f 6c 6c 6f 77 73 20 74 68   that follows th
0530: 65 20 6b 65 79 20 69 73 20 69 6e 20 61 20 73 69  e key is in a si
0540: 6d 69 6c 61 72 2c 20 62 75 74 20 6e 6f 74 20 69  milar, but not i
0550: 64 65 6e 74 69 63 61 6c 20 66 6f 72 6d 61 74 0a  dentical format.
0560: 2a 2a 20 74 6f 20 74 68 65 20 64 6f 63 6c 69 73  ** to the doclis
0570: 74 20 64 61 74 61 20 73 74 6f 72 65 64 20 69 6e  t data stored in
0580: 20 74 68 65 20 64 61 74 61 62 61 73 65 2e 20 49   the database. I
0590: 74 20 69 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 2a 20  t is:.**.**   * 
05a0: 52 6f 77 69 64 2c 20 61 73 20 61 20 76 61 72 69  Rowid, as a vari
05b0: 6e 74 0a 2a 2a 20 20 20 2a 20 50 6f 73 69 74 69  nt.**   * Positi
05c0: 6f 6e 20 6c 69 73 74 2c 20 77 69 74 68 6f 75 74  on list, without
05d0: 20 30 78 30 30 20 74 65 72 6d 69 6e 61 74 6f 72   0x00 terminator
05e0: 2e 0a 2a 2a 20 20 20 2a 20 53 69 7a 65 20 6f 66  ..**   * Size of
05f0: 20 70 72 65 76 69 6f 75 73 20 70 6f 73 69 74 69   previous positi
0600: 6f 6e 20 6c 69 73 74 20 61 6e 64 20 72 6f 77 69  on list and rowi
0610: 64 2c 20 61 73 20 61 20 34 20 62 79 74 65 0a 2a  d, as a 4 byte.*
0620: 2a 20 20 20 20 20 62 69 67 2d 65 6e 64 69 61 6e  *     big-endian
0630: 20 69 6e 74 65 67 65 72 2e 0a 2a 2a 0a 2a 2a 20   integer..**.** 
0640: 69 52 6f 77 69 64 4f 66 66 3a 0a 2a 2a 20 20 20  iRowidOff:.**   
0650: 4f 66 66 73 65 74 20 6f 66 20 6c 61 73 74 20 72  Offset of last r
0660: 6f 77 69 64 20 77 72 69 74 74 65 6e 20 74 6f 20  owid written to 
0670: 64 61 74 61 20 61 72 65 61 2e 20 52 65 6c 61 74  data area. Relat
0680: 69 76 65 20 74 6f 20 66 69 72 73 74 20 62 79 74  ive to first byt
0690: 65 20 6f 66 0a 2a 2a 20 20 20 73 74 72 75 63 74  e of.**   struct
06a0: 75 72 65 2e 0a 2a 2a 0a 2a 2a 20 6e 44 61 74 61  ure..**.** nData
06b0: 3a 0a 2a 2a 20 20 20 42 79 74 65 73 20 6f 66 20  :.**   Bytes of 
06c0: 64 61 74 61 20 77 72 69 74 74 65 6e 20 73 69 6e  data written sin
06d0: 63 65 20 69 52 6f 77 69 64 4f 66 66 2e 0a 2a 2f  ce iRowidOff..*/
06e0: 0a 73 74 72 75 63 74 20 46 74 73 35 48 61 73 68  .struct Fts5Hash
06f0: 45 6e 74 72 79 20 7b 0a 20 20 46 74 73 35 48 61  Entry {.  Fts5Ha
0700: 73 68 45 6e 74 72 79 20 2a 70 48 61 73 68 4e 65  shEntry *pHashNe
0710: 78 74 3b 20 20 20 20 20 20 20 2f 2a 20 4e 65 78  xt;       /* Nex
0720: 74 20 68 61 73 68 20 65 6e 74 72 79 20 77 69 74  t hash entry wit
0730: 68 20 73 61 6d 65 20 68 61 73 68 2d 6b 65 79 20  h same hash-key 
0740: 2a 2f 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74  */.  Fts5HashEnt
0750: 72 79 20 2a 70 53 63 61 6e 4e 65 78 74 3b 20 20  ry *pScanNext;  
0760: 20 20 20 20 20 2f 2a 20 4e 65 78 74 20 65 6e 74       /* Next ent
0770: 72 79 20 69 6e 20 73 6f 72 74 65 64 20 6f 72 64  ry in sorted ord
0780: 65 72 20 2a 2f 0a 20 20 0a 20 20 69 6e 74 20 6e  er */.  .  int n
0790: 41 6c 6c 6f 63 3b 20 20 20 20 20 20 20 20 20 20  Alloc;          
07a0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 6f             /* To
07b0: 74 61 6c 20 73 69 7a 65 20 6f 66 20 61 6c 6c 6f  tal size of allo
07c0: 63 61 74 69 6f 6e 20 2a 2f 0a 20 20 69 6e 74 20  cation */.  int 
07d0: 69 53 7a 50 6f 73 6c 69 73 74 3b 20 20 20 20 20  iSzPoslist;     
07e0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f              /* O
07f0: 66 66 73 65 74 20 6f 66 20 73 70 61 63 65 20 66  ffset of space f
0800: 6f 72 20 34 2d 62 79 74 65 20 70 6f 73 6c 69 73  or 4-byte poslis
0810: 74 20 73 69 7a 65 20 2a 2f 0a 20 20 69 6e 74 20  t size */.  int 
0820: 6e 44 61 74 61 3b 20 20 20 20 20 20 20 20 20 20  nData;          
0830: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54              /* T
0840: 6f 74 61 6c 20 62 79 74 65 73 20 6f 66 20 64 61  otal bytes of da
0850: 74 61 20 28 69 6e 63 6c 2e 20 73 74 72 75 63 74  ta (incl. struct
0860: 75 72 65 29 20 2a 2f 0a 20 20 69 6e 74 20 6e 4b  ure) */.  int nK
0870: 65 79 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  ey;             
0880: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4c 65 6e            /* Len
0890: 67 74 68 20 6f 66 20 7a 4b 65 79 5b 5d 20 69 6e  gth of zKey[] in
08a0: 20 62 79 74 65 73 20 2a 2f 0a 20 20 75 38 20 62   bytes */.  u8 b
08b0: 44 65 6c 3b 20 20 20 20 20 20 20 20 20 20 20 20  Del;            
08c0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 53              /* S
08d0: 65 74 20 64 65 6c 65 74 65 2d 66 6c 61 67 20 40  et delete-flag @
08e0: 20 69 53 7a 50 6f 73 6c 69 73 74 20 2a 2f 0a 20   iSzPoslist */. 
08f0: 20 75 38 20 62 43 6f 6e 74 65 6e 74 3b 20 20 20   u8 bContent;   
0900: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0910: 20 2f 2a 20 53 65 74 20 63 6f 6e 74 65 6e 74 2d   /* Set content-
0920: 66 6c 61 67 20 28 64 65 74 61 69 6c 3d 6e 6f 6e  flag (detail=non
0930: 65 20 6d 6f 64 65 29 20 2a 2f 0a 20 20 69 31 36  e mode) */.  i16
0940: 20 69 43 6f 6c 3b 20 20 20 20 20 20 20 20 20 20   iCol;          
0950: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
0960: 43 6f 6c 75 6d 6e 20 6f 66 20 6c 61 73 74 20 76  Column of last v
0970: 61 6c 75 65 20 77 72 69 74 74 65 6e 20 2a 2f 0a  alue written */.
0980: 20 20 69 6e 74 20 69 50 6f 73 3b 20 20 20 20 20    int iPos;     
0990: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
09a0: 20 20 2f 2a 20 50 6f 73 69 74 69 6f 6e 20 6f 66    /* Position of
09b0: 20 6c 61 73 74 20 76 61 6c 75 65 20 77 72 69 74   last value writ
09c0: 74 65 6e 20 2a 2f 0a 20 20 69 36 34 20 69 52 6f  ten */.  i64 iRo
09d0: 77 69 64 3b 20 20 20 20 20 20 20 20 20 20 20 20  wid;            
09e0: 20 20 20 20 20 20 20 20 20 2f 2a 20 52 6f 77 69           /* Rowi
09f0: 64 20 6f 66 20 6c 61 73 74 20 76 61 6c 75 65 20  d of last value 
0a00: 77 72 69 74 74 65 6e 20 2a 2f 0a 20 20 63 68 61  written */.  cha
0a10: 72 20 7a 4b 65 79 5b 38 5d 3b 20 20 20 20 20 20  r zKey[8];      
0a20: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
0a30: 4e 75 6c 2d 74 65 72 6d 69 6e 61 74 65 64 20 65  Nul-terminated e
0a40: 6e 74 72 79 20 6b 65 79 20 2a 2f 0a 7d 3b 0a 0a  ntry key */.};..
0a50: 2f 2a 0a 2a 2a 20 53 69 7a 65 20 6f 66 20 46 74  /*.** Size of Ft
0a60: 73 35 48 61 73 68 45 6e 74 72 79 20 77 69 74 68  s5HashEntry with
0a70: 6f 75 74 20 74 68 65 20 7a 4b 65 79 5b 5d 20 61  out the zKey[] a
0a80: 72 72 61 79 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65  rray..*/.#define
0a90: 20 46 54 53 35 5f 48 41 53 48 45 4e 54 52 59 53   FTS5_HASHENTRYS
0aa0: 49 5a 45 20 28 73 69 7a 65 6f 66 28 46 74 73 35  IZE (sizeof(Fts5
0ab0: 48 61 73 68 45 6e 74 72 79 29 2d 38 29 0a 0a 0a  HashEntry)-8)...
0ac0: 0a 2f 2a 0a 2a 2a 20 41 6c 6c 6f 63 61 74 65 20  ./*.** Allocate 
0ad0: 61 20 6e 65 77 20 68 61 73 68 20 74 61 62 6c 65  a new hash table
0ae0: 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33  ..*/.int sqlite3
0af0: 46 74 73 35 48 61 73 68 4e 65 77 28 46 74 73 35  Fts5HashNew(Fts5
0b00: 43 6f 6e 66 69 67 20 2a 70 43 6f 6e 66 69 67 2c  Config *pConfig,
0b10: 20 46 74 73 35 48 61 73 68 20 2a 2a 70 70 4e 65   Fts5Hash **ppNe
0b20: 77 2c 20 69 6e 74 20 2a 70 6e 42 79 74 65 29 7b  w, int *pnByte){
0b30: 0a 20 20 69 6e 74 20 72 63 20 3d 20 53 51 4c 49  .  int rc = SQLI
0b40: 54 45 5f 4f 4b 3b 0a 20 20 46 74 73 35 48 61 73  TE_OK;.  Fts5Has
0b50: 68 20 2a 70 4e 65 77 3b 0a 0a 20 20 2a 70 70 4e  h *pNew;..  *ppN
0b60: 65 77 20 3d 20 70 4e 65 77 20 3d 20 28 46 74 73  ew = pNew = (Fts
0b70: 35 48 61 73 68 2a 29 73 71 6c 69 74 65 33 5f 6d  5Hash*)sqlite3_m
0b80: 61 6c 6c 6f 63 28 73 69 7a 65 6f 66 28 46 74 73  alloc(sizeof(Fts
0b90: 35 48 61 73 68 29 29 3b 0a 20 20 69 66 28 20 70  5Hash));.  if( p
0ba0: 4e 65 77 3d 3d 30 20 29 7b 0a 20 20 20 20 72 63  New==0 ){.    rc
0bb0: 20 3d 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b   = SQLITE_NOMEM;
0bc0: 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 69 6e  .  }else{.    in
0bd0: 74 20 6e 42 79 74 65 3b 0a 20 20 20 20 6d 65 6d  t nByte;.    mem
0be0: 73 65 74 28 70 4e 65 77 2c 20 30 2c 20 73 69 7a  set(pNew, 0, siz
0bf0: 65 6f 66 28 46 74 73 35 48 61 73 68 29 29 3b 0a  eof(Fts5Hash));.
0c00: 20 20 20 20 70 4e 65 77 2d 3e 70 6e 42 79 74 65      pNew->pnByte
0c10: 20 3d 20 70 6e 42 79 74 65 3b 0a 20 20 20 20 70   = pnByte;.    p
0c20: 4e 65 77 2d 3e 65 44 65 74 61 69 6c 20 3d 20 70  New->eDetail = p
0c30: 43 6f 6e 66 69 67 2d 3e 65 44 65 74 61 69 6c 3b  Config->eDetail;
0c40: 0a 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 53 6c 6f  ..    pNew->nSlo
0c50: 74 20 3d 20 31 30 32 34 3b 0a 20 20 20 20 6e 42  t = 1024;.    nB
0c60: 79 74 65 20 3d 20 73 69 7a 65 6f 66 28 46 74 73  yte = sizeof(Fts
0c70: 35 48 61 73 68 45 6e 74 72 79 2a 29 20 2a 20 70  5HashEntry*) * p
0c80: 4e 65 77 2d 3e 6e 53 6c 6f 74 3b 0a 20 20 20 20  New->nSlot;.    
0c90: 70 4e 65 77 2d 3e 61 53 6c 6f 74 20 3d 20 28 46  pNew->aSlot = (F
0ca0: 74 73 35 48 61 73 68 45 6e 74 72 79 2a 2a 29 73  ts5HashEntry**)s
0cb0: 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e 42  qlite3_malloc(nB
0cc0: 79 74 65 29 3b 0a 20 20 20 20 69 66 28 20 70 4e  yte);.    if( pN
0cd0: 65 77 2d 3e 61 53 6c 6f 74 3d 3d 30 20 29 7b 0a  ew->aSlot==0 ){.
0ce0: 20 20 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72        sqlite3_fr
0cf0: 65 65 28 70 4e 65 77 29 3b 0a 20 20 20 20 20 20  ee(pNew);.      
0d00: 2a 70 70 4e 65 77 20 3d 20 30 3b 0a 20 20 20 20  *ppNew = 0;.    
0d10: 20 20 72 63 20 3d 20 53 51 4c 49 54 45 5f 4e 4f    rc = SQLITE_NO
0d20: 4d 45 4d 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a  MEM;.    }else{.
0d30: 20 20 20 20 20 20 6d 65 6d 73 65 74 28 70 4e 65        memset(pNe
0d40: 77 2d 3e 61 53 6c 6f 74 2c 20 30 2c 20 6e 42 79  w->aSlot, 0, nBy
0d50: 74 65 29 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20  te);.    }.  }. 
0d60: 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f   return rc;.}../
0d70: 2a 0a 2a 2a 20 46 72 65 65 20 61 20 68 61 73 68  *.** Free a hash
0d80: 20 74 61 62 6c 65 20 6f 62 6a 65 63 74 2e 0a 2a   table object..*
0d90: 2f 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 46 74  /.void sqlite3Ft
0da0: 73 35 48 61 73 68 46 72 65 65 28 46 74 73 35 48  s5HashFree(Fts5H
0db0: 61 73 68 20 2a 70 48 61 73 68 29 7b 0a 20 20 69  ash *pHash){.  i
0dc0: 66 28 20 70 48 61 73 68 20 29 7b 0a 20 20 20 20  f( pHash ){.    
0dd0: 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 43  sqlite3Fts5HashC
0de0: 6c 65 61 72 28 70 48 61 73 68 29 3b 0a 20 20 20  lear(pHash);.   
0df0: 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70 48   sqlite3_free(pH
0e00: 61 73 68 2d 3e 61 53 6c 6f 74 29 3b 0a 20 20 20  ash->aSlot);.   
0e10: 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70 48   sqlite3_free(pH
0e20: 61 73 68 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a  ash);.  }.}../*.
0e30: 2a 2a 20 45 6d 70 74 79 20 28 62 75 74 20 64 6f  ** Empty (but do
0e40: 20 6e 6f 74 20 64 65 6c 65 74 65 29 20 61 20 68   not delete) a h
0e50: 61 73 68 20 74 61 62 6c 65 2e 0a 2a 2f 0a 76 6f  ash table..*/.vo
0e60: 69 64 20 73 71 6c 69 74 65 33 46 74 73 35 48 61  id sqlite3Fts5Ha
0e70: 73 68 43 6c 65 61 72 28 46 74 73 35 48 61 73 68  shClear(Fts5Hash
0e80: 20 2a 70 48 61 73 68 29 7b 0a 20 20 69 6e 74 20   *pHash){.  int 
0e90: 69 3b 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c  i;.  for(i=0; i<
0ea0: 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 3b 20 69 2b  pHash->nSlot; i+
0eb0: 2b 29 7b 0a 20 20 20 20 46 74 73 35 48 61 73 68  +){.    Fts5Hash
0ec0: 45 6e 74 72 79 20 2a 70 4e 65 78 74 3b 0a 20 20  Entry *pNext;.  
0ed0: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20    Fts5HashEntry 
0ee0: 2a 70 53 6c 6f 74 3b 0a 20 20 20 20 66 6f 72 28  *pSlot;.    for(
0ef0: 70 53 6c 6f 74 3d 70 48 61 73 68 2d 3e 61 53 6c  pSlot=pHash->aSl
0f00: 6f 74 5b 69 5d 3b 20 70 53 6c 6f 74 3b 20 70 53  ot[i]; pSlot; pS
0f10: 6c 6f 74 3d 70 4e 65 78 74 29 7b 0a 20 20 20 20  lot=pNext){.    
0f20: 20 20 70 4e 65 78 74 20 3d 20 70 53 6c 6f 74 2d    pNext = pSlot-
0f30: 3e 70 48 61 73 68 4e 65 78 74 3b 0a 20 20 20 20  >pHashNext;.    
0f40: 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70    sqlite3_free(p
0f50: 53 6c 6f 74 29 3b 0a 20 20 20 20 7d 0a 20 20 7d  Slot);.    }.  }
0f60: 0a 20 20 6d 65 6d 73 65 74 28 70 48 61 73 68 2d  .  memset(pHash-
0f70: 3e 61 53 6c 6f 74 2c 20 30 2c 20 70 48 61 73 68  >aSlot, 0, pHash
0f80: 2d 3e 6e 53 6c 6f 74 20 2a 20 73 69 7a 65 6f 66  ->nSlot * sizeof
0f90: 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29  (Fts5HashEntry*)
0fa0: 29 3b 0a 20 20 70 48 61 73 68 2d 3e 6e 45 6e 74  );.  pHash->nEnt
0fb0: 72 79 20 3d 20 30 3b 0a 7d 0a 0a 73 74 61 74 69  ry = 0;.}..stati
0fc0: 63 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 66  c unsigned int f
0fd0: 74 73 35 48 61 73 68 4b 65 79 28 69 6e 74 20 6e  ts5HashKey(int n
0fe0: 53 6c 6f 74 2c 20 63 6f 6e 73 74 20 75 38 20 2a  Slot, const u8 *
0ff0: 70 2c 20 69 6e 74 20 6e 29 7b 0a 20 20 69 6e 74  p, int n){.  int
1000: 20 69 3b 0a 20 20 75 6e 73 69 67 6e 65 64 20 69   i;.  unsigned i
1010: 6e 74 20 68 20 3d 20 31 33 3b 0a 20 20 66 6f 72  nt h = 13;.  for
1020: 28 69 3d 6e 2d 31 3b 20 69 3e 3d 30 3b 20 69 2d  (i=n-1; i>=0; i-
1030: 2d 29 7b 0a 20 20 20 20 68 20 3d 20 28 68 20 3c  -){.    h = (h <
1040: 3c 20 33 29 20 5e 20 68 20 5e 20 70 5b 69 5d 3b  < 3) ^ h ^ p[i];
1050: 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 28 68  .  }.  return (h
1060: 20 25 20 6e 53 6c 6f 74 29 3b 0a 7d 0a 0a 73 74   % nSlot);.}..st
1070: 61 74 69 63 20 75 6e 73 69 67 6e 65 64 20 69 6e  atic unsigned in
1080: 74 20 66 74 73 35 48 61 73 68 4b 65 79 32 28 69  t fts5HashKey2(i
1090: 6e 74 20 6e 53 6c 6f 74 2c 20 75 38 20 62 2c 20  nt nSlot, u8 b, 
10a0: 63 6f 6e 73 74 20 75 38 20 2a 70 2c 20 69 6e 74  const u8 *p, int
10b0: 20 6e 29 7b 0a 20 20 69 6e 74 20 69 3b 0a 20 20   n){.  int i;.  
10c0: 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 68 20 3d  unsigned int h =
10d0: 20 31 33 3b 0a 20 20 66 6f 72 28 69 3d 6e 2d 31   13;.  for(i=n-1
10e0: 3b 20 69 3e 3d 30 3b 20 69 2d 2d 29 7b 0a 20 20  ; i>=0; i--){.  
10f0: 20 20 68 20 3d 20 28 68 20 3c 3c 20 33 29 20 5e    h = (h << 3) ^
1100: 20 68 20 5e 20 70 5b 69 5d 3b 0a 20 20 7d 0a 20   h ^ p[i];.  }. 
1110: 20 68 20 3d 20 28 68 20 3c 3c 20 33 29 20 5e 20   h = (h << 3) ^ 
1120: 68 20 5e 20 62 3b 0a 20 20 72 65 74 75 72 6e 20  h ^ b;.  return 
1130: 28 68 20 25 20 6e 53 6c 6f 74 29 3b 0a 7d 0a 0a  (h % nSlot);.}..
1140: 2f 2a 0a 2a 2a 20 52 65 73 69 7a 65 20 74 68 65  /*.** Resize the
1150: 20 68 61 73 68 20 74 61 62 6c 65 20 62 79 20 64   hash table by d
1160: 6f 75 62 6c 69 6e 67 20 74 68 65 20 6e 75 6d 62  oubling the numb
1170: 65 72 20 6f 66 20 73 6c 6f 74 73 2e 0a 2a 2f 0a  er of slots..*/.
1180: 73 74 61 74 69 63 20 69 6e 74 20 66 74 73 35 48  static int fts5H
1190: 61 73 68 52 65 73 69 7a 65 28 46 74 73 35 48 61  ashResize(Fts5Ha
11a0: 73 68 20 2a 70 48 61 73 68 29 7b 0a 20 20 69 6e  sh *pHash){.  in
11b0: 74 20 6e 4e 65 77 20 3d 20 70 48 61 73 68 2d 3e  t nNew = pHash->
11c0: 6e 53 6c 6f 74 2a 32 3b 0a 20 20 69 6e 74 20 69  nSlot*2;.  int i
11d0: 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72  ;.  Fts5HashEntr
11e0: 79 20 2a 2a 61 70 4e 65 77 3b 0a 20 20 46 74 73  y **apNew;.  Fts
11f0: 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 61 70 4f  5HashEntry **apO
1200: 6c 64 20 3d 20 70 48 61 73 68 2d 3e 61 53 6c 6f  ld = pHash->aSlo
1210: 74 3b 0a 0a 20 20 61 70 4e 65 77 20 3d 20 28 46  t;..  apNew = (F
1220: 74 73 35 48 61 73 68 45 6e 74 72 79 2a 2a 29 73  ts5HashEntry**)s
1230: 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e 4e  qlite3_malloc(nN
1240: 65 77 2a 73 69 7a 65 6f 66 28 46 74 73 35 48 61  ew*sizeof(Fts5Ha
1250: 73 68 45 6e 74 72 79 2a 29 29 3b 0a 20 20 69 66  shEntry*));.  if
1260: 28 20 21 61 70 4e 65 77 20 29 20 72 65 74 75 72  ( !apNew ) retur
1270: 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a  n SQLITE_NOMEM;.
1280: 20 20 6d 65 6d 73 65 74 28 61 70 4e 65 77 2c 20    memset(apNew, 
1290: 30 2c 20 6e 4e 65 77 2a 73 69 7a 65 6f 66 28 46  0, nNew*sizeof(F
12a0: 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29 29 3b  ts5HashEntry*));
12b0: 0a 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 70  ..  for(i=0; i<p
12c0: 48 61 73 68 2d 3e 6e 53 6c 6f 74 3b 20 69 2b 2b  Hash->nSlot; i++
12d0: 29 7b 0a 20 20 20 20 77 68 69 6c 65 28 20 61 70  ){.    while( ap
12e0: 4f 6c 64 5b 69 5d 20 29 7b 0a 20 20 20 20 20 20  Old[i] ){.      
12f0: 69 6e 74 20 69 48 61 73 68 3b 0a 20 20 20 20 20  int iHash;.     
1300: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
1310: 70 20 3d 20 61 70 4f 6c 64 5b 69 5d 3b 0a 20 20  p = apOld[i];.  
1320: 20 20 20 20 61 70 4f 6c 64 5b 69 5d 20 3d 20 70      apOld[i] = p
1330: 2d 3e 70 48 61 73 68 4e 65 78 74 3b 0a 20 20 20  ->pHashNext;.   
1340: 20 20 20 69 48 61 73 68 20 3d 20 66 74 73 35 48     iHash = fts5H
1350: 61 73 68 4b 65 79 28 6e 4e 65 77 2c 20 28 75 38  ashKey(nNew, (u8
1360: 2a 29 70 2d 3e 7a 4b 65 79 2c 20 28 69 6e 74 29  *)p->zKey, (int)
1370: 73 74 72 6c 65 6e 28 70 2d 3e 7a 4b 65 79 29 29  strlen(p->zKey))
1380: 3b 0a 20 20 20 20 20 20 70 2d 3e 70 48 61 73 68  ;.      p->pHash
1390: 4e 65 78 74 20 3d 20 61 70 4e 65 77 5b 69 48 61  Next = apNew[iHa
13a0: 73 68 5d 3b 0a 20 20 20 20 20 20 61 70 4e 65 77  sh];.      apNew
13b0: 5b 69 48 61 73 68 5d 20 3d 20 70 3b 0a 20 20 20  [iHash] = p;.   
13c0: 20 7d 0a 20 20 7d 0a 0a 20 20 73 71 6c 69 74 65   }.  }..  sqlite
13d0: 33 5f 66 72 65 65 28 61 70 4f 6c 64 29 3b 0a 20  3_free(apOld);. 
13e0: 20 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 20 3d 20   pHash->nSlot = 
13f0: 6e 4e 65 77 3b 0a 20 20 70 48 61 73 68 2d 3e 61  nNew;.  pHash->a
1400: 53 6c 6f 74 20 3d 20 61 70 4e 65 77 3b 0a 20 20  Slot = apNew;.  
1410: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b  return SQLITE_OK
1420: 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 76 6f 69 64  ;.}..static void
1430: 20 66 74 73 35 48 61 73 68 41 64 64 50 6f 73 6c   fts5HashAddPosl
1440: 69 73 74 53 69 7a 65 28 46 74 73 35 48 61 73 68  istSize(Fts5Hash
1450: 20 2a 70 48 61 73 68 2c 20 46 74 73 35 48 61 73   *pHash, Fts5Has
1460: 68 45 6e 74 72 79 20 2a 70 29 7b 0a 20 20 69 66  hEntry *p){.  if
1470: 28 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20  ( p->iSzPoslist 
1480: 29 7b 0a 20 20 20 20 75 38 20 2a 70 50 74 72 20  ){.    u8 *pPtr 
1490: 3d 20 28 75 38 2a 29 70 3b 0a 20 20 20 20 69 66  = (u8*)p;.    if
14a0: 28 20 70 48 61 73 68 2d 3e 65 44 65 74 61 69 6c  ( pHash->eDetail
14b0: 3d 3d 46 54 53 35 5f 44 45 54 41 49 4c 5f 4e 4f  ==FTS5_DETAIL_NO
14c0: 4e 45 20 29 7b 0a 20 20 20 20 20 20 61 73 73 65  NE ){.      asse
14d0: 72 74 28 20 70 2d 3e 6e 44 61 74 61 3d 3d 70 2d  rt( p->nData==p-
14e0: 3e 69 53 7a 50 6f 73 6c 69 73 74 20 29 3b 0a 20  >iSzPoslist );. 
14f0: 20 20 20 20 20 69 66 28 20 70 2d 3e 62 44 65 6c       if( p->bDel
1500: 20 29 7b 0a 20 20 20 20 20 20 20 20 70 50 74 72   ){.        pPtr
1510: 5b 70 2d 3e 6e 44 61 74 61 2b 2b 5d 20 3d 20 30  [p->nData++] = 0
1520: 78 30 30 3b 0a 20 20 20 20 20 20 20 20 69 66 28  x00;.        if(
1530: 20 70 2d 3e 62 43 6f 6e 74 65 6e 74 20 29 7b 0a   p->bContent ){.
1540: 20 20 20 20 20 20 20 20 20 20 70 50 74 72 5b 70            pPtr[p
1550: 2d 3e 6e 44 61 74 61 2b 2b 5d 20 3d 20 30 78 30  ->nData++] = 0x0
1560: 30 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20  0;.        }.   
1570: 20 20 20 7d 0a 20 20 20 20 7d 65 6c 73 65 7b 0a     }.    }else{.
1580: 20 20 20 20 20 20 69 6e 74 20 6e 53 7a 20 3d 20        int nSz = 
1590: 28 70 2d 3e 6e 44 61 74 61 20 2d 20 70 2d 3e 69  (p->nData - p->i
15a0: 53 7a 50 6f 73 6c 69 73 74 20 2d 20 31 29 3b 20  SzPoslist - 1); 
15b0: 20 20 20 20 20 20 2f 2a 20 53 69 7a 65 20 69 6e        /* Size in
15c0: 20 62 79 74 65 73 20 2a 2f 0a 20 20 20 20 20 20   bytes */.      
15d0: 69 6e 74 20 6e 50 6f 73 20 3d 20 6e 53 7a 2a 32  int nPos = nSz*2
15e0: 20 2b 20 70 2d 3e 62 44 65 6c 3b 20 20 20 20 20   + p->bDel;     
15f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1600: 2f 2a 20 56 61 6c 75 65 20 6f 66 20 6e 50 6f 73  /* Value of nPos
1610: 20 66 69 65 6c 64 20 2a 2f 0a 0a 20 20 20 20 20   field */..     
1620: 20 61 73 73 65 72 74 28 20 70 2d 3e 62 44 65 6c   assert( p->bDel
1630: 3d 3d 30 20 7c 7c 20 70 2d 3e 62 44 65 6c 3d 3d  ==0 || p->bDel==
1640: 31 20 29 3b 0a 20 20 20 20 20 20 69 66 28 20 6e  1 );.      if( n
1650: 50 6f 73 3c 3d 31 32 37 20 29 7b 0a 20 20 20 20  Pos<=127 ){.    
1660: 20 20 20 20 70 50 74 72 5b 70 2d 3e 69 53 7a 50      pPtr[p->iSzP
1670: 6f 73 6c 69 73 74 5d 20 3d 20 28 75 38 29 6e 50  oslist] = (u8)nP
1680: 6f 73 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b  os;.      }else{
1690: 0a 20 20 20 20 20 20 20 20 69 6e 74 20 6e 42 79  .        int nBy
16a0: 74 65 20 3d 20 73 71 6c 69 74 65 33 46 74 73 35  te = sqlite3Fts5
16b0: 47 65 74 56 61 72 69 6e 74 4c 65 6e 28 28 75 33  GetVarintLen((u3
16c0: 32 29 6e 50 6f 73 29 3b 0a 20 20 20 20 20 20 20  2)nPos);.       
16d0: 20 6d 65 6d 6d 6f 76 65 28 26 70 50 74 72 5b 70   memmove(&pPtr[p
16e0: 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 2b 20 6e  ->iSzPoslist + n
16f0: 42 79 74 65 5d 2c 20 26 70 50 74 72 5b 70 2d 3e  Byte], &pPtr[p->
1700: 69 53 7a 50 6f 73 6c 69 73 74 20 2b 20 31 5d 2c  iSzPoslist + 1],
1710: 20 6e 53 7a 29 3b 0a 20 20 20 20 20 20 20 20 73   nSz);.        s
1720: 71 6c 69 74 65 33 46 74 73 35 50 75 74 56 61 72  qlite3Fts5PutVar
1730: 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e 69 53 7a  int(&pPtr[p->iSz
1740: 50 6f 73 6c 69 73 74 5d 2c 20 6e 50 6f 73 29 3b  Poslist], nPos);
1750: 0a 20 20 20 20 20 20 20 20 70 2d 3e 6e 44 61 74  .        p->nDat
1760: 61 20 2b 3d 20 28 6e 42 79 74 65 2d 31 29 3b 0a  a += (nByte-1);.
1770: 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a 0a 20        }.    }.. 
1780: 20 20 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74     p->iSzPoslist
1790: 20 3d 20 30 3b 0a 20 20 20 20 70 2d 3e 62 44 65   = 0;.    p->bDe
17a0: 6c 20 3d 20 30 3b 0a 20 20 20 20 70 2d 3e 62 43  l = 0;.    p->bC
17b0: 6f 6e 74 65 6e 74 20 3d 20 30 3b 0a 20 20 7d 0a  ontent = 0;.  }.
17c0: 7d 0a 0a 2f 2a 0a 2a 2a 20 41 64 64 20 61 6e 20  }../*.** Add an 
17d0: 65 6e 74 72 79 20 74 6f 20 74 68 65 20 69 6e 2d  entry to the in-
17e0: 6d 65 6d 6f 72 79 20 68 61 73 68 20 74 61 62 6c  memory hash tabl
17f0: 65 2e 20 54 68 65 20 6b 65 79 20 69 73 20 74 68  e. The key is th
1800: 65 20 63 6f 6e 63 61 74 65 6e 61 74 69 6f 6e 0a  e concatenation.
1810: 2a 2a 20 6f 66 20 62 42 79 74 65 20 61 6e 64 20  ** of bByte and 
1820: 28 70 54 6f 6b 65 6e 2f 6e 54 6f 6b 65 6e 29 2e  (pToken/nToken).
1830: 20 54 68 65 20 76 61 6c 75 65 20 69 73 20 28 69   The value is (i
1840: 52 6f 77 69 64 2f 69 43 6f 6c 2f 69 50 6f 73 29  Rowid/iCol/iPos)
1850: 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 20 28 62 42 79  ..**.**     (bBy
1860: 74 65 20 7c 7c 20 70 54 6f 6b 65 6e 29 20 2d 3e  te || pToken) ->
1870: 20 28 69 52 6f 77 69 64 2c 69 43 6f 6c 2c 69 50   (iRowid,iCol,iP
1880: 6f 73 29 0a 2a 2a 0a 2a 2a 20 4f 72 2c 20 69 66  os).**.** Or, if
1890: 20 69 43 6f 6c 20 69 73 20 6e 65 67 61 74 69 76   iCol is negativ
18a0: 65 2c 20 74 68 65 6e 20 74 68 65 20 76 61 6c 75  e, then the valu
18b0: 65 20 69 73 20 61 20 64 65 6c 65 74 65 20 6d 61  e is a delete ma
18c0: 72 6b 65 72 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c  rker..*/.int sql
18d0: 69 74 65 33 46 74 73 35 48 61 73 68 57 72 69 74  ite3Fts5HashWrit
18e0: 65 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a 70  e(.  Fts5Hash *p
18f0: 48 61 73 68 2c 0a 20 20 69 36 34 20 69 52 6f 77  Hash,.  i64 iRow
1900: 69 64 2c 20 20 20 20 20 20 20 20 20 20 20 20 20  id,             
1910: 20 20 20 20 20 20 20 20 2f 2a 20 52 6f 77 69 64          /* Rowid
1920: 20 66 6f 72 20 74 68 69 73 20 65 6e 74 72 79 20   for this entry 
1930: 2a 2f 0a 20 20 69 6e 74 20 69 43 6f 6c 2c 20 20  */.  int iCol,  
1940: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1950: 20 20 20 20 20 2f 2a 20 43 6f 6c 75 6d 6e 20 74       /* Column t
1960: 6f 6b 65 6e 20 61 70 70 65 61 72 73 20 69 6e 20  oken appears in 
1970: 28 2d 76 65 20 2d 3e 20 64 65 6c 65 74 65 29 20  (-ve -> delete) 
1980: 2a 2f 0a 20 20 69 6e 74 20 69 50 6f 73 2c 20 20  */.  int iPos,  
1990: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
19a0: 20 20 20 20 20 2f 2a 20 50 6f 73 69 74 69 6f 6e       /* Position
19b0: 20 6f 66 20 74 6f 6b 65 6e 20 77 69 74 68 69 6e   of token within
19c0: 20 63 6f 6c 75 6d 6e 20 2a 2f 0a 20 20 63 68 61   column */.  cha
19d0: 72 20 62 42 79 74 65 2c 20 20 20 20 20 20 20 20  r bByte,        
19e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
19f0: 46 69 72 73 74 20 62 79 74 65 20 6f 66 20 74 6f  First byte of to
1a00: 6b 65 6e 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63  ken */.  const c
1a10: 68 61 72 20 2a 70 54 6f 6b 65 6e 2c 20 69 6e 74  har *pToken, int
1a20: 20 6e 54 6f 6b 65 6e 20 20 2f 2a 20 54 6f 6b 65   nToken  /* Toke
1a30: 6e 20 74 6f 20 61 64 64 20 6f 72 20 72 65 6d 6f  n to add or remo
1a40: 76 65 20 74 6f 20 6f 72 20 66 72 6f 6d 20 69 6e  ve to or from in
1a50: 64 65 78 20 2a 2f 0a 29 7b 0a 20 20 75 6e 73 69  dex */.){.  unsi
1a60: 67 6e 65 64 20 69 6e 74 20 69 48 61 73 68 3b 0a  gned int iHash;.
1a70: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20    Fts5HashEntry 
1a80: 2a 70 3b 0a 20 20 75 38 20 2a 70 50 74 72 3b 0a  *p;.  u8 *pPtr;.
1a90: 20 20 69 6e 74 20 6e 49 6e 63 72 20 3d 20 30 3b    int nIncr = 0;
1aa0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1ab0: 20 20 2f 2a 20 41 6d 6f 75 6e 74 20 74 6f 20 69    /* Amount to i
1ac0: 6e 63 72 65 6d 65 6e 74 20 28 2a 70 48 61 73 68  ncrement (*pHash
1ad0: 2d 3e 70 6e 42 79 74 65 29 20 62 79 20 2a 2f 0a  ->pnByte) by */.
1ae0: 20 20 69 6e 74 20 62 4e 65 77 3b 20 20 20 20 20    int bNew;     
1af0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1b00: 20 20 2f 2a 20 49 66 20 6e 6f 6e 2d 64 65 6c 65    /* If non-dele
1b10: 74 65 20 65 6e 74 72 79 20 73 68 6f 75 6c 64 20  te entry should 
1b20: 62 65 20 77 72 69 74 74 65 6e 20 2a 2f 0a 20 20  be written */.  
1b30: 0a 20 20 62 4e 65 77 20 3d 20 28 70 48 61 73 68  .  bNew = (pHash
1b40: 2d 3e 65 44 65 74 61 69 6c 3d 3d 46 54 53 35 5f  ->eDetail==FTS5_
1b50: 44 45 54 41 49 4c 5f 46 55 4c 4c 29 3b 0a 0a 20  DETAIL_FULL);.. 
1b60: 20 2f 2a 20 41 74 74 65 6d 70 74 20 74 6f 20 6c   /* Attempt to l
1b70: 6f 63 61 74 65 20 61 6e 20 65 78 69 73 74 69 6e  ocate an existin
1b80: 67 20 68 61 73 68 20 65 6e 74 72 79 20 2a 2f 0a  g hash entry */.
1b90: 20 20 69 48 61 73 68 20 3d 20 66 74 73 35 48 61    iHash = fts5Ha
1ba0: 73 68 4b 65 79 32 28 70 48 61 73 68 2d 3e 6e 53  shKey2(pHash->nS
1bb0: 6c 6f 74 2c 20 28 75 38 29 62 42 79 74 65 2c 20  lot, (u8)bByte, 
1bc0: 28 63 6f 6e 73 74 20 75 38 2a 29 70 54 6f 6b 65  (const u8*)pToke
1bd0: 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 66 6f  n, nToken);.  fo
1be0: 72 28 70 3d 70 48 61 73 68 2d 3e 61 53 6c 6f 74  r(p=pHash->aSlot
1bf0: 5b 69 48 61 73 68 5d 3b 20 70 3b 20 70 3d 70 2d  [iHash]; p; p=p-
1c00: 3e 70 48 61 73 68 4e 65 78 74 29 7b 0a 20 20 20  >pHashNext){.   
1c10: 20 69 66 28 20 70 2d 3e 7a 4b 65 79 5b 30 5d 3d   if( p->zKey[0]=
1c20: 3d 62 42 79 74 65 20 0a 20 20 20 20 20 26 26 20  =bByte .     && 
1c30: 70 2d 3e 6e 4b 65 79 3d 3d 6e 54 6f 6b 65 6e 0a  p->nKey==nToken.
1c40: 20 20 20 20 20 26 26 20 6d 65 6d 63 6d 70 28 26       && memcmp(&
1c50: 70 2d 3e 7a 4b 65 79 5b 31 5d 2c 20 70 54 6f 6b  p->zKey[1], pTok
1c60: 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3d 3d 30 20 0a  en, nToken)==0 .
1c70: 20 20 20 20 29 7b 0a 20 20 20 20 20 20 62 72 65      ){.      bre
1c80: 61 6b 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 20  ak;.    }.  }.. 
1c90: 20 2f 2a 20 49 66 20 61 6e 20 65 78 69 73 74 69   /* If an existi
1ca0: 6e 67 20 68 61 73 68 20 65 6e 74 72 79 20 63 61  ng hash entry ca
1cb0: 6e 6e 6f 74 20 62 65 20 66 6f 75 6e 64 2c 20 63  nnot be found, c
1cc0: 72 65 61 74 65 20 61 20 6e 65 77 20 6f 6e 65 2e  reate a new one.
1cd0: 20 2a 2f 0a 20 20 69 66 28 20 70 3d 3d 30 20 29   */.  if( p==0 )
1ce0: 7b 0a 20 20 20 20 2f 2a 20 46 69 67 75 72 65 20  {.    /* Figure 
1cf0: 6f 75 74 20 68 6f 77 20 6d 75 63 68 20 73 70 61  out how much spa
1d00: 63 65 20 74 6f 20 61 6c 6c 6f 63 61 74 65 20 2a  ce to allocate *
1d10: 2f 0a 20 20 20 20 69 6e 74 20 6e 42 79 74 65 20  /.    int nByte 
1d20: 3d 20 46 54 53 35 5f 48 41 53 48 45 4e 54 52 59  = FTS5_HASHENTRY
1d30: 53 49 5a 45 20 2b 20 28 6e 54 6f 6b 65 6e 2b 31  SIZE + (nToken+1
1d40: 29 20 2b 20 31 20 2b 20 36 34 3b 0a 20 20 20 20  ) + 1 + 64;.    
1d50: 69 66 28 20 6e 42 79 74 65 3c 31 32 38 20 29 20  if( nByte<128 ) 
1d60: 6e 42 79 74 65 20 3d 20 31 32 38 3b 0a 0a 20 20  nByte = 128;..  
1d70: 20 20 2f 2a 20 47 72 6f 77 20 74 68 65 20 46 74    /* Grow the Ft
1d80: 73 35 48 61 73 68 2e 61 53 6c 6f 74 5b 5d 20 61  s5Hash.aSlot[] a
1d90: 72 72 61 79 20 69 66 20 6e 65 63 65 73 73 61 72  rray if necessar
1da0: 79 2e 20 2a 2f 0a 20 20 20 20 69 66 28 20 28 70  y. */.    if( (p
1db0: 48 61 73 68 2d 3e 6e 45 6e 74 72 79 2a 32 29 3e  Hash->nEntry*2)>
1dc0: 3d 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 20 29 7b  =pHash->nSlot ){
1dd0: 0a 20 20 20 20 20 20 69 6e 74 20 72 63 20 3d 20  .      int rc = 
1de0: 66 74 73 35 48 61 73 68 52 65 73 69 7a 65 28 70  fts5HashResize(p
1df0: 48 61 73 68 29 3b 0a 20 20 20 20 20 20 69 66 28  Hash);.      if(
1e00: 20 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 29   rc!=SQLITE_OK )
1e10: 20 72 65 74 75 72 6e 20 72 63 3b 0a 20 20 20 20   return rc;.    
1e20: 20 20 69 48 61 73 68 20 3d 20 66 74 73 35 48 61    iHash = fts5Ha
1e30: 73 68 4b 65 79 32 28 70 48 61 73 68 2d 3e 6e 53  shKey2(pHash->nS
1e40: 6c 6f 74 2c 20 28 75 38 29 62 42 79 74 65 2c 20  lot, (u8)bByte, 
1e50: 28 63 6f 6e 73 74 20 75 38 2a 29 70 54 6f 6b 65  (const u8*)pToke
1e60: 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 20 20  n, nToken);.    
1e70: 7d 0a 0a 20 20 20 20 2f 2a 20 41 6c 6c 6f 63 61  }..    /* Alloca
1e80: 74 65 20 6e 65 77 20 46 74 73 35 48 61 73 68 45  te new Fts5HashE
1e90: 6e 74 72 79 20 61 6e 64 20 61 64 64 20 69 74 20  ntry and add it 
1ea0: 74 6f 20 74 68 65 20 68 61 73 68 20 74 61 62 6c  to the hash tabl
1eb0: 65 2e 20 2a 2f 0a 20 20 20 20 70 20 3d 20 28 46  e. */.    p = (F
1ec0: 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29 73 71  ts5HashEntry*)sq
1ed0: 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e 42 79  lite3_malloc(nBy
1ee0: 74 65 29 3b 0a 20 20 20 20 69 66 28 20 21 70 20  te);.    if( !p 
1ef0: 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f  ) return SQLITE_
1f00: 4e 4f 4d 45 4d 3b 0a 20 20 20 20 6d 65 6d 73 65  NOMEM;.    memse
1f10: 74 28 70 2c 20 30 2c 20 46 54 53 35 5f 48 41 53  t(p, 0, FTS5_HAS
1f20: 48 45 4e 54 52 59 53 49 5a 45 29 3b 0a 20 20 20  HENTRYSIZE);.   
1f30: 20 70 2d 3e 6e 41 6c 6c 6f 63 20 3d 20 6e 42 79   p->nAlloc = nBy
1f40: 74 65 3b 0a 20 20 20 20 70 2d 3e 7a 4b 65 79 5b  te;.    p->zKey[
1f50: 30 5d 20 3d 20 62 42 79 74 65 3b 0a 20 20 20 20  0] = bByte;.    
1f60: 6d 65 6d 63 70 79 28 26 70 2d 3e 7a 4b 65 79 5b  memcpy(&p->zKey[
1f70: 31 5d 2c 20 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b  1], pToken, nTok
1f80: 65 6e 29 3b 0a 20 20 20 20 61 73 73 65 72 74 28  en);.    assert(
1f90: 20 69 48 61 73 68 3d 3d 66 74 73 35 48 61 73 68   iHash==fts5Hash
1fa0: 4b 65 79 28 70 48 61 73 68 2d 3e 6e 53 6c 6f 74  Key(pHash->nSlot
1fb0: 2c 20 28 75 38 2a 29 70 2d 3e 7a 4b 65 79 2c 20  , (u8*)p->zKey, 
1fc0: 6e 54 6f 6b 65 6e 2b 31 29 20 29 3b 0a 20 20 20  nToken+1) );.   
1fd0: 20 70 2d 3e 6e 4b 65 79 20 3d 20 6e 54 6f 6b 65   p->nKey = nToke
1fe0: 6e 3b 0a 20 20 20 20 70 2d 3e 7a 4b 65 79 5b 6e  n;.    p->zKey[n
1ff0: 54 6f 6b 65 6e 2b 31 5d 20 3d 20 27 5c 30 27 3b  Token+1] = '\0';
2000: 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 3d 20  .    p->nData = 
2010: 6e 54 6f 6b 65 6e 2b 31 20 2b 20 31 20 2b 20 46  nToken+1 + 1 + F
2020: 54 53 35 5f 48 41 53 48 45 4e 54 52 59 53 49 5a  TS5_HASHENTRYSIZ
2030: 45 3b 0a 20 20 20 20 70 2d 3e 70 48 61 73 68 4e  E;.    p->pHashN
2040: 65 78 74 20 3d 20 70 48 61 73 68 2d 3e 61 53 6c  ext = pHash->aSl
2050: 6f 74 5b 69 48 61 73 68 5d 3b 0a 20 20 20 20 70  ot[iHash];.    p
2060: 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 48 61 73  Hash->aSlot[iHas
2070: 68 5d 20 3d 20 70 3b 0a 20 20 20 20 70 48 61 73  h] = p;.    pHas
2080: 68 2d 3e 6e 45 6e 74 72 79 2b 2b 3b 0a 0a 20 20  h->nEntry++;..  
2090: 20 20 2f 2a 20 41 64 64 20 74 68 65 20 66 69 72    /* Add the fir
20a0: 73 74 20 72 6f 77 69 64 20 66 69 65 6c 64 20 74  st rowid field t
20b0: 6f 20 74 68 65 20 68 61 73 68 2d 65 6e 74 72 79  o the hash-entry
20c0: 20 2a 2f 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61   */.    p->nData
20d0: 20 2b 3d 20 73 71 6c 69 74 65 33 46 74 73 35 50   += sqlite3Fts5P
20e0: 75 74 56 61 72 69 6e 74 28 26 28 28 75 38 2a 29  utVarint(&((u8*)
20f0: 70 29 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20 69 52  p)[p->nData], iR
2100: 6f 77 69 64 29 3b 0a 20 20 20 20 70 2d 3e 69 52  owid);.    p->iR
2110: 6f 77 69 64 20 3d 20 69 52 6f 77 69 64 3b 0a 0a  owid = iRowid;..
2120: 20 20 20 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73      p->iSzPoslis
2130: 74 20 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20 20  t = p->nData;.  
2140: 20 20 69 66 28 20 70 48 61 73 68 2d 3e 65 44 65    if( pHash->eDe
2150: 74 61 69 6c 21 3d 46 54 53 35 5f 44 45 54 41 49  tail!=FTS5_DETAI
2160: 4c 5f 4e 4f 4e 45 20 29 7b 0a 20 20 20 20 20 20  L_NONE ){.      
2170: 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 31 3b 0a 20  p->nData += 1;. 
2180: 20 20 20 20 20 70 2d 3e 69 43 6f 6c 20 3d 20 28       p->iCol = (
2190: 70 48 61 73 68 2d 3e 65 44 65 74 61 69 6c 3d 3d  pHash->eDetail==
21a0: 46 54 53 35 5f 44 45 54 41 49 4c 5f 46 55 4c 4c  FTS5_DETAIL_FULL
21b0: 20 3f 20 30 20 3a 20 2d 31 29 3b 0a 20 20 20 20   ? 0 : -1);.    
21c0: 7d 0a 0a 20 20 20 20 6e 49 6e 63 72 20 2b 3d 20  }..    nIncr += 
21d0: 70 2d 3e 6e 44 61 74 61 3b 0a 20 20 7d 65 6c 73  p->nData;.  }els
21e0: 65 7b 0a 0a 20 20 20 20 2f 2a 20 41 70 70 65 6e  e{..    /* Appen
21f0: 64 69 6e 67 20 74 6f 20 61 6e 20 65 78 69 73 74  ding to an exist
2200: 69 6e 67 20 68 61 73 68 2d 65 6e 74 72 79 2e 20  ing hash-entry. 
2210: 43 68 65 63 6b 20 74 68 61 74 20 74 68 65 72 65  Check that there
2220: 20 69 73 20 65 6e 6f 75 67 68 20 0a 20 20 20 20   is enough .    
2230: 2a 2a 20 73 70 61 63 65 20 74 6f 20 61 70 70 65  ** space to appe
2240: 6e 64 20 74 68 65 20 6c 61 72 67 65 73 74 20 70  nd the largest p
2250: 6f 73 73 69 62 6c 65 20 6e 65 77 20 65 6e 74 72  ossible new entr
2260: 79 2e 20 57 6f 72 73 74 20 63 61 73 65 20 73 63  y. Worst case sc
2270: 65 6e 61 72 69 6f 20 0a 20 20 20 20 2a 2a 20 69  enario .    ** i
2280: 73 3a 0a 20 20 20 20 2a 2a 0a 20 20 20 20 2a 2a  s:.    **.    **
2290: 20 20 20 20 20 2b 20 39 20 62 79 74 65 73 20 66       + 9 bytes f
22a0: 6f 72 20 61 20 6e 65 77 20 72 6f 77 69 64 2c 0a  or a new rowid,.
22b0: 20 20 20 20 2a 2a 20 20 20 20 20 2b 20 34 20 62      **     + 4 b
22c0: 79 74 65 20 72 65 73 65 72 76 65 64 20 66 6f 72  yte reserved for
22d0: 20 74 68 65 20 22 70 6f 73 6c 69 73 74 20 73 69   the "poslist si
22e0: 7a 65 22 20 76 61 72 69 6e 74 2e 0a 20 20 20 20  ze" varint..    
22f0: 2a 2a 20 20 20 20 20 2b 20 31 20 62 79 74 65 20  **     + 1 byte 
2300: 66 6f 72 20 61 20 22 6e 65 77 20 63 6f 6c 75 6d  for a "new colum
2310: 6e 22 20 62 79 74 65 2c 0a 20 20 20 20 2a 2a 20  n" byte,.    ** 
2320: 20 20 20 20 2b 20 33 20 62 79 74 65 73 20 66 6f      + 3 bytes fo
2330: 72 20 61 20 6e 65 77 20 63 6f 6c 75 6d 6e 20 6e  r a new column n
2340: 75 6d 62 65 72 20 28 31 36 2d 62 69 74 20 6d 61  umber (16-bit ma
2350: 78 29 20 61 73 20 61 20 76 61 72 69 6e 74 2c 0a  x) as a varint,.
2360: 20 20 20 20 2a 2a 20 20 20 20 20 2b 20 35 20 62      **     + 5 b
2370: 79 74 65 73 20 66 6f 72 20 74 68 65 20 6e 65 77  ytes for the new
2380: 20 70 6f 73 69 74 69 6f 6e 20 6f 66 66 73 65 74   position offset
2390: 20 28 33 32 2d 62 69 74 20 6d 61 78 29 2e 0a 20   (32-bit max).. 
23a0: 20 20 20 2a 2f 0a 20 20 20 20 69 66 28 20 28 70     */.    if( (p
23b0: 2d 3e 6e 41 6c 6c 6f 63 20 2d 20 70 2d 3e 6e 44  ->nAlloc - p->nD
23c0: 61 74 61 29 20 3c 20 28 39 20 2b 20 34 20 2b 20  ata) < (9 + 4 + 
23d0: 31 20 2b 20 33 20 2b 20 35 29 20 29 7b 0a 20 20  1 + 3 + 5) ){.  
23e0: 20 20 20 20 69 6e 74 20 6e 4e 65 77 20 3d 20 70      int nNew = p
23f0: 2d 3e 6e 41 6c 6c 6f 63 20 2a 20 32 3b 0a 20 20  ->nAlloc * 2;.  
2400: 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74 72      Fts5HashEntr
2410: 79 20 2a 70 4e 65 77 3b 0a 20 20 20 20 20 20 46  y *pNew;.      F
2420: 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 70  ts5HashEntry **p
2430: 70 3b 0a 20 20 20 20 20 20 70 4e 65 77 20 3d 20  p;.      pNew = 
2440: 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29  (Fts5HashEntry*)
2450: 73 71 6c 69 74 65 33 5f 72 65 61 6c 6c 6f 63 28  sqlite3_realloc(
2460: 70 2c 20 6e 4e 65 77 29 3b 0a 20 20 20 20 20 20  p, nNew);.      
2470: 69 66 28 20 70 4e 65 77 3d 3d 30 20 29 20 72 65  if( pNew==0 ) re
2480: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45  turn SQLITE_NOME
2490: 4d 3b 0a 20 20 20 20 20 20 70 4e 65 77 2d 3e 6e  M;.      pNew->n
24a0: 41 6c 6c 6f 63 20 3d 20 6e 4e 65 77 3b 0a 20 20  Alloc = nNew;.  
24b0: 20 20 20 20 66 6f 72 28 70 70 3d 26 70 48 61 73      for(pp=&pHas
24c0: 68 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d 3b  h->aSlot[iHash];
24d0: 20 2a 70 70 21 3d 70 3b 20 70 70 3d 26 28 2a 70   *pp!=p; pp=&(*p
24e0: 70 29 2d 3e 70 48 61 73 68 4e 65 78 74 29 3b 0a  p)->pHashNext);.
24f0: 20 20 20 20 20 20 2a 70 70 20 3d 20 70 4e 65 77        *pp = pNew
2500: 3b 0a 20 20 20 20 20 20 70 20 3d 20 70 4e 65 77  ;.      p = pNew
2510: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 6e 49 6e 63  ;.    }.    nInc
2520: 72 20 2d 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20  r -= p->nData;. 
2530: 20 7d 0a 20 20 61 73 73 65 72 74 28 20 28 70 2d   }.  assert( (p-
2540: 3e 6e 41 6c 6c 6f 63 20 2d 20 70 2d 3e 6e 44 61  >nAlloc - p->nDa
2550: 74 61 29 20 3e 3d 20 28 39 20 2b 20 34 20 2b 20  ta) >= (9 + 4 + 
2560: 31 20 2b 20 33 20 2b 20 35 29 20 29 3b 0a 0a 20  1 + 3 + 5) );.. 
2570: 20 70 50 74 72 20 3d 20 28 75 38 2a 29 70 3b 0a   pPtr = (u8*)p;.
2580: 0a 20 20 2f 2a 20 49 66 20 74 68 69 73 20 69 73  .  /* If this is
2590: 20 61 20 6e 65 77 20 72 6f 77 69 64 2c 20 61 70   a new rowid, ap
25a0: 70 65 6e 64 20 74 68 65 20 34 2d 62 79 74 65 20  pend the 4-byte 
25b0: 73 69 7a 65 20 66 69 65 6c 64 20 66 6f 72 20 74  size field for t
25c0: 68 65 20 70 72 65 76 69 6f 75 73 0a 20 20 2a 2a  he previous.  **
25d0: 20 65 6e 74 72 79 2c 20 61 6e 64 20 74 68 65 20   entry, and the 
25e0: 6e 65 77 20 72 6f 77 69 64 20 66 6f 72 20 74 68  new rowid for th
25f0: 69 73 20 65 6e 74 72 79 2e 20 20 2a 2f 0a 20 20  is entry.  */.  
2600: 69 66 28 20 69 52 6f 77 69 64 21 3d 70 2d 3e 69  if( iRowid!=p->i
2610: 52 6f 77 69 64 20 29 7b 0a 20 20 20 20 66 74 73  Rowid ){.    fts
2620: 35 48 61 73 68 41 64 64 50 6f 73 6c 69 73 74 53  5HashAddPoslistS
2630: 69 7a 65 28 70 48 61 73 68 2c 20 70 29 3b 0a 20  ize(pHash, p);. 
2640: 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73     p->nData += s
2650: 71 6c 69 74 65 33 46 74 73 35 50 75 74 56 61 72  qlite3Fts5PutVar
2660: 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61  int(&pPtr[p->nDa
2670: 74 61 5d 2c 20 69 52 6f 77 69 64 20 2d 20 70 2d  ta], iRowid - p-
2680: 3e 69 52 6f 77 69 64 29 3b 0a 20 20 20 20 70 2d  >iRowid);.    p-
2690: 3e 69 52 6f 77 69 64 20 3d 20 69 52 6f 77 69 64  >iRowid = iRowid
26a0: 3b 0a 20 20 20 20 62 4e 65 77 20 3d 20 31 3b 0a  ;.    bNew = 1;.
26b0: 20 20 20 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73      p->iSzPoslis
26c0: 74 20 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20 20  t = p->nData;.  
26d0: 20 20 69 66 28 20 70 48 61 73 68 2d 3e 65 44 65    if( pHash->eDe
26e0: 74 61 69 6c 21 3d 46 54 53 35 5f 44 45 54 41 49  tail!=FTS5_DETAI
26f0: 4c 5f 4e 4f 4e 45 20 29 7b 0a 20 20 20 20 20 20  L_NONE ){.      
2700: 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 31 3b 0a 20  p->nData += 1;. 
2710: 20 20 20 20 20 70 2d 3e 69 43 6f 6c 20 3d 20 28       p->iCol = (
2720: 70 48 61 73 68 2d 3e 65 44 65 74 61 69 6c 3d 3d  pHash->eDetail==
2730: 46 54 53 35 5f 44 45 54 41 49 4c 5f 46 55 4c 4c  FTS5_DETAIL_FULL
2740: 20 3f 20 30 20 3a 20 2d 31 29 3b 0a 20 20 20 20   ? 0 : -1);.    
2750: 20 20 70 2d 3e 69 50 6f 73 20 3d 20 30 3b 0a 20    p->iPos = 0;. 
2760: 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 69 66 28 20     }.  }..  if( 
2770: 69 43 6f 6c 3e 3d 30 20 29 7b 0a 20 20 20 20 69  iCol>=0 ){.    i
2780: 66 28 20 70 48 61 73 68 2d 3e 65 44 65 74 61 69  f( pHash->eDetai
2790: 6c 3d 3d 46 54 53 35 5f 44 45 54 41 49 4c 5f 4e  l==FTS5_DETAIL_N
27a0: 4f 4e 45 20 29 7b 0a 20 20 20 20 20 20 70 2d 3e  ONE ){.      p->
27b0: 62 43 6f 6e 74 65 6e 74 20 3d 20 31 3b 0a 20 20  bContent = 1;.  
27c0: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 2f    }else{.      /
27d0: 2a 20 41 70 70 65 6e 64 20 61 20 6e 65 77 20 63  * Append a new c
27e0: 6f 6c 75 6d 6e 20 76 61 6c 75 65 2c 20 69 66 20  olumn value, if 
27f0: 6e 65 63 65 73 73 61 72 79 20 2a 2f 0a 20 20 20  necessary */.   
2800: 20 20 20 61 73 73 65 72 74 28 20 69 43 6f 6c 3e     assert( iCol>
2810: 3d 70 2d 3e 69 43 6f 6c 20 29 3b 0a 20 20 20 20  =p->iCol );.    
2820: 20 20 69 66 28 20 69 43 6f 6c 21 3d 70 2d 3e 69    if( iCol!=p->i
2830: 43 6f 6c 20 29 7b 0a 20 20 20 20 20 20 20 20 69  Col ){.        i
2840: 66 28 20 70 48 61 73 68 2d 3e 65 44 65 74 61 69  f( pHash->eDetai
2850: 6c 3d 3d 46 54 53 35 5f 44 45 54 41 49 4c 5f 46  l==FTS5_DETAIL_F
2860: 55 4c 4c 20 29 7b 0a 20 20 20 20 20 20 20 20 20  ULL ){.         
2870: 20 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61 2b 2b   pPtr[p->nData++
2880: 5d 20 3d 20 30 78 30 31 3b 0a 20 20 20 20 20 20  ] = 0x01;.      
2890: 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20      p->nData += 
28a0: 73 71 6c 69 74 65 33 46 74 73 35 50 75 74 56 61  sqlite3Fts5PutVa
28b0: 72 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44  rint(&pPtr[p->nD
28c0: 61 74 61 5d 2c 20 69 43 6f 6c 29 3b 0a 20 20 20  ata], iCol);.   
28d0: 20 20 20 20 20 20 20 70 2d 3e 69 43 6f 6c 20 3d         p->iCol =
28e0: 20 28 69 31 36 29 69 43 6f 6c 3b 0a 20 20 20 20   (i16)iCol;.    
28f0: 20 20 20 20 20 20 70 2d 3e 69 50 6f 73 20 3d 20        p->iPos = 
2900: 30 3b 0a 20 20 20 20 20 20 20 20 7d 65 6c 73 65  0;.        }else
2910: 7b 0a 20 20 20 20 20 20 20 20 20 20 62 4e 65 77  {.          bNew
2920: 20 3d 20 31 3b 0a 20 20 20 20 20 20 20 20 20 20   = 1;.          
2930: 70 2d 3e 69 43 6f 6c 20 3d 20 28 69 31 36 29 28  p->iCol = (i16)(
2940: 69 50 6f 73 20 3d 20 69 43 6f 6c 29 3b 0a 20 20  iPos = iCol);.  
2950: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 7d 0a        }.      }.
2960: 0a 20 20 20 20 20 20 2f 2a 20 41 70 70 65 6e 64  .      /* Append
2970: 20 74 68 65 20 6e 65 77 20 70 6f 73 69 74 69 6f   the new positio
2980: 6e 20 6f 66 66 73 65 74 2c 20 69 66 20 6e 65 63  n offset, if nec
2990: 65 73 73 61 72 79 20 2a 2f 0a 20 20 20 20 20 20  essary */.      
29a0: 69 66 28 20 62 4e 65 77 20 29 7b 0a 20 20 20 20  if( bNew ){.    
29b0: 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20      p->nData += 
29c0: 73 71 6c 69 74 65 33 46 74 73 35 50 75 74 56 61  sqlite3Fts5PutVa
29d0: 72 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44  rint(&pPtr[p->nD
29e0: 61 74 61 5d 2c 20 69 50 6f 73 20 2d 20 70 2d 3e  ata], iPos - p->
29f0: 69 50 6f 73 20 2b 20 32 29 3b 0a 20 20 20 20 20  iPos + 2);.     
2a00: 20 20 20 70 2d 3e 69 50 6f 73 20 3d 20 69 50 6f     p->iPos = iPo
2a10: 73 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 7d  s;.      }.    }
2a20: 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2f 2a  .  }else{.    /*
2a30: 20 54 68 69 73 20 69 73 20 61 20 64 65 6c 65 74   This is a delet
2a40: 65 2e 20 53 65 74 20 74 68 65 20 64 65 6c 65 74  e. Set the delet
2a50: 65 20 66 6c 61 67 2e 20 2a 2f 0a 20 20 20 20 70  e flag. */.    p
2a60: 2d 3e 62 44 65 6c 20 3d 20 31 3b 0a 20 20 7d 0a  ->bDel = 1;.  }.
2a70: 0a 20 20 6e 49 6e 63 72 20 2b 3d 20 70 2d 3e 6e  .  nIncr += p->n
2a80: 44 61 74 61 3b 0a 20 20 2a 70 48 61 73 68 2d 3e  Data;.  *pHash->
2a90: 70 6e 42 79 74 65 20 2b 3d 20 6e 49 6e 63 72 3b  pnByte += nIncr;
2aa0: 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45  .  return SQLITE
2ab0: 5f 4f 4b 3b 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a 20 41  _OK;.}.../*.** A
2ac0: 72 67 75 6d 65 6e 74 73 20 70 4c 65 66 74 20 61  rguments pLeft a
2ad0: 6e 64 20 70 52 69 67 68 74 20 70 6f 69 6e 74 20  nd pRight point 
2ae0: 74 6f 20 6c 69 6e 6b 65 64 2d 6c 69 73 74 73 20  to linked-lists 
2af0: 6f 66 20 68 61 73 68 2d 65 6e 74 72 79 20 6f 62  of hash-entry ob
2b00: 6a 65 63 74 73 2c 0a 2a 2a 20 65 61 63 68 20 73  jects,.** each s
2b10: 6f 72 74 65 64 20 69 6e 20 6b 65 79 20 6f 72 64  orted in key ord
2b20: 65 72 2e 20 54 68 69 73 20 66 75 6e 63 74 69 6f  er. This functio
2b30: 6e 20 6d 65 72 67 65 73 20 74 68 65 20 74 77 6f  n merges the two
2b40: 20 6c 69 73 74 73 20 69 6e 74 6f 20 61 0a 2a 2a   lists into a.**
2b50: 20 73 69 6e 67 6c 65 20 6c 69 73 74 20 61 6e 64   single list and
2b60: 20 72 65 74 75 72 6e 73 20 61 20 70 6f 69 6e 74   returns a point
2b70: 65 72 20 74 6f 20 69 74 73 20 66 69 72 73 74 20  er to its first 
2b80: 65 6c 65 6d 65 6e 74 2e 0a 2a 2f 0a 73 74 61 74  element..*/.stat
2b90: 69 63 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  ic Fts5HashEntry
2ba0: 20 2a 66 74 73 35 48 61 73 68 45 6e 74 72 79 4d   *fts5HashEntryM
2bb0: 65 72 67 65 28 0a 20 20 46 74 73 35 48 61 73 68  erge(.  Fts5Hash
2bc0: 45 6e 74 72 79 20 2a 70 4c 65 66 74 2c 0a 20 20  Entry *pLeft,.  
2bd0: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70  Fts5HashEntry *p
2be0: 52 69 67 68 74 0a 29 7b 0a 20 20 46 74 73 35 48  Right.){.  Fts5H
2bf0: 61 73 68 45 6e 74 72 79 20 2a 70 31 20 3d 20 70  ashEntry *p1 = p
2c00: 4c 65 66 74 3b 0a 20 20 46 74 73 35 48 61 73 68  Left;.  Fts5Hash
2c10: 45 6e 74 72 79 20 2a 70 32 20 3d 20 70 52 69 67  Entry *p2 = pRig
2c20: 68 74 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e  ht;.  Fts5HashEn
2c30: 74 72 79 20 2a 70 52 65 74 20 3d 20 30 3b 0a 20  try *pRet = 0;. 
2c40: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
2c50: 2a 70 70 4f 75 74 20 3d 20 26 70 52 65 74 3b 0a  *ppOut = &pRet;.
2c60: 0a 20 20 77 68 69 6c 65 28 20 70 31 20 7c 7c 20  .  while( p1 || 
2c70: 70 32 20 29 7b 0a 20 20 20 20 69 66 28 20 70 31  p2 ){.    if( p1
2c80: 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 2a 70 70  ==0 ){.      *pp
2c90: 4f 75 74 20 3d 20 70 32 3b 0a 20 20 20 20 20 20  Out = p2;.      
2ca0: 70 32 20 3d 20 30 3b 0a 20 20 20 20 7d 65 6c 73  p2 = 0;.    }els
2cb0: 65 20 69 66 28 20 70 32 3d 3d 30 20 29 7b 0a 20  e if( p2==0 ){. 
2cc0: 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 70 31       *ppOut = p1
2cd0: 3b 0a 20 20 20 20 20 20 70 31 20 3d 20 30 3b 0a  ;.      p1 = 0;.
2ce0: 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20      }else{.     
2cf0: 20 69 6e 74 20 69 20 3d 20 30 3b 0a 20 20 20 20   int i = 0;.    
2d00: 20 20 77 68 69 6c 65 28 20 70 31 2d 3e 7a 4b 65    while( p1->zKe
2d10: 79 5b 69 5d 3d 3d 70 32 2d 3e 7a 4b 65 79 5b 69  y[i]==p2->zKey[i
2d20: 5d 20 29 20 69 2b 2b 3b 0a 0a 20 20 20 20 20 20  ] ) i++;..      
2d30: 69 66 28 20 28 28 75 38 29 70 31 2d 3e 7a 4b 65  if( ((u8)p1->zKe
2d40: 79 5b 69 5d 29 3e 28 28 75 38 29 70 32 2d 3e 7a  y[i])>((u8)p2->z
2d50: 4b 65 79 5b 69 5d 29 20 29 7b 0a 20 20 20 20 20  Key[i]) ){.     
2d60: 20 20 20 2f 2a 20 70 32 20 69 73 20 73 6d 61 6c     /* p2 is smal
2d70: 6c 65 72 20 2a 2f 0a 20 20 20 20 20 20 20 20 2a  ler */.        *
2d80: 70 70 4f 75 74 20 3d 20 70 32 3b 0a 20 20 20 20  ppOut = p2;.    
2d90: 20 20 20 20 70 70 4f 75 74 20 3d 20 26 70 32 2d      ppOut = &p2-
2da0: 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 20 20 20 20  >pScanNext;.    
2db0: 20 20 20 20 70 32 20 3d 20 70 32 2d 3e 70 53 63      p2 = p2->pSc
2dc0: 61 6e 4e 65 78 74 3b 0a 20 20 20 20 20 20 7d 65  anNext;.      }e
2dd0: 6c 73 65 7b 0a 20 20 20 20 20 20 20 20 2f 2a 20  lse{.        /* 
2de0: 70 31 20 69 73 20 73 6d 61 6c 6c 65 72 20 2a 2f  p1 is smaller */
2df0: 0a 20 20 20 20 20 20 20 20 2a 70 70 4f 75 74 20  .        *ppOut 
2e00: 3d 20 70 31 3b 0a 20 20 20 20 20 20 20 20 70 70  = p1;.        pp
2e10: 4f 75 74 20 3d 20 26 70 31 2d 3e 70 53 63 61 6e  Out = &p1->pScan
2e20: 4e 65 78 74 3b 0a 20 20 20 20 20 20 20 20 70 31  Next;.        p1
2e30: 20 3d 20 70 31 2d 3e 70 53 63 61 6e 4e 65 78 74   = p1->pScanNext
2e40: 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20  ;.      }.      
2e50: 2a 70 70 4f 75 74 20 3d 20 30 3b 0a 20 20 20 20  *ppOut = 0;.    
2e60: 7d 0a 20 20 7d 0a 0a 20 20 72 65 74 75 72 6e 20  }.  }..  return 
2e70: 70 52 65 74 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 45  pRet;.}../*.** E
2e80: 78 74 72 61 63 74 20 61 6c 6c 20 74 6f 6b 65 6e  xtract all token
2e90: 73 20 66 72 6f 6d 20 68 61 73 68 20 74 61 62 6c  s from hash tabl
2ea0: 65 20 69 48 61 73 68 20 61 6e 64 20 6c 69 6e 6b  e iHash and link
2eb0: 20 74 68 65 6d 20 69 6e 74 6f 20 61 20 6c 69 73   them into a lis
2ec0: 74 0a 2a 2a 20 69 6e 20 73 6f 72 74 65 64 20 6f  t.** in sorted o
2ed0: 72 64 65 72 2e 20 54 68 65 20 68 61 73 68 20 74  rder. The hash t
2ee0: 61 62 6c 65 20 69 73 20 63 6c 65 61 72 65 64 20  able is cleared 
2ef0: 62 65 66 6f 72 65 20 72 65 74 75 72 6e 69 6e 67  before returning
2f00: 2e 20 49 74 20 69 73 0a 2a 2a 20 74 68 65 20 72  . It is.** the r
2f10: 65 73 70 6f 6e 73 69 62 69 6c 69 74 79 20 6f 66  esponsibility of
2f20: 20 74 68 65 20 63 61 6c 6c 65 72 20 74 6f 20 66   the caller to f
2f30: 72 65 65 20 74 68 65 20 65 6c 65 6d 65 6e 74 73  ree the elements
2f40: 20 6f 66 20 74 68 65 20 72 65 74 75 72 6e 65 64   of the returned
2f50: 0a 2a 2a 20 6c 69 73 74 2e 0a 2a 2f 0a 73 74 61  .** list..*/.sta
2f60: 74 69 63 20 69 6e 74 20 66 74 73 35 48 61 73 68  tic int fts5Hash
2f70: 45 6e 74 72 79 53 6f 72 74 28 0a 20 20 46 74 73  EntrySort(.  Fts
2f80: 35 48 61 73 68 20 2a 70 48 61 73 68 2c 20 0a 20  5Hash *pHash, . 
2f90: 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 54 65   const char *pTe
2fa0: 72 6d 2c 20 69 6e 74 20 6e 54 65 72 6d 2c 20 20  rm, int nTerm,  
2fb0: 20 2f 2a 20 51 75 65 72 79 20 70 72 65 66 69 78   /* Query prefix
2fc0: 2c 20 69 66 20 61 6e 79 20 2a 2f 0a 20 20 46 74  , if any */.  Ft
2fd0: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 70 70  s5HashEntry **pp
2fe0: 53 6f 72 74 65 64 0a 29 7b 0a 20 20 63 6f 6e 73  Sorted.){.  cons
2ff0: 74 20 69 6e 74 20 6e 4d 65 72 67 65 53 6c 6f 74  t int nMergeSlot
3000: 20 3d 20 33 32 3b 0a 20 20 46 74 73 35 48 61 73   = 32;.  Fts5Has
3010: 68 45 6e 74 72 79 20 2a 2a 61 70 3b 0a 20 20 46  hEntry **ap;.  F
3020: 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 4c  ts5HashEntry *pL
3030: 69 73 74 3b 0a 20 20 69 6e 74 20 69 53 6c 6f 74  ist;.  int iSlot
3040: 3b 0a 20 20 69 6e 74 20 69 3b 0a 0a 20 20 2a 70  ;.  int i;..  *p
3050: 70 53 6f 72 74 65 64 20 3d 20 30 3b 0a 20 20 61  pSorted = 0;.  a
3060: 70 20 3d 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c  p = sqlite3_mall
3070: 6f 63 28 73 69 7a 65 6f 66 28 46 74 73 35 48 61  oc(sizeof(Fts5Ha
3080: 73 68 45 6e 74 72 79 2a 29 20 2a 20 6e 4d 65 72  shEntry*) * nMer
3090: 67 65 53 6c 6f 74 29 3b 0a 20 20 69 66 28 20 21  geSlot);.  if( !
30a0: 61 70 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49  ap ) return SQLI
30b0: 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 6d 65 6d 73  TE_NOMEM;.  mems
30c0: 65 74 28 61 70 2c 20 30 2c 20 73 69 7a 65 6f 66  et(ap, 0, sizeof
30d0: 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29  (Fts5HashEntry*)
30e0: 20 2a 20 6e 4d 65 72 67 65 53 6c 6f 74 29 3b 0a   * nMergeSlot);.
30f0: 0a 20 20 66 6f 72 28 69 53 6c 6f 74 3d 30 3b 20  .  for(iSlot=0; 
3100: 69 53 6c 6f 74 3c 70 48 61 73 68 2d 3e 6e 53 6c  iSlot<pHash->nSl
3110: 6f 74 3b 20 69 53 6c 6f 74 2b 2b 29 7b 0a 20 20  ot; iSlot++){.  
3120: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20    Fts5HashEntry 
3130: 2a 70 49 74 65 72 3b 0a 20 20 20 20 66 6f 72 28  *pIter;.    for(
3140: 70 49 74 65 72 3d 70 48 61 73 68 2d 3e 61 53 6c  pIter=pHash->aSl
3150: 6f 74 5b 69 53 6c 6f 74 5d 3b 20 70 49 74 65 72  ot[iSlot]; pIter
3160: 3b 20 70 49 74 65 72 3d 70 49 74 65 72 2d 3e 70  ; pIter=pIter->p
3170: 48 61 73 68 4e 65 78 74 29 7b 0a 20 20 20 20 20  HashNext){.     
3180: 20 69 66 28 20 70 54 65 72 6d 3d 3d 30 20 7c 7c   if( pTerm==0 ||
3190: 20 30 3d 3d 6d 65 6d 63 6d 70 28 70 49 74 65 72   0==memcmp(pIter
31a0: 2d 3e 7a 4b 65 79 2c 20 70 54 65 72 6d 2c 20 6e  ->zKey, pTerm, n
31b0: 54 65 72 6d 29 20 29 7b 0a 20 20 20 20 20 20 20  Term) ){.       
31c0: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
31d0: 70 45 6e 74 72 79 20 3d 20 70 49 74 65 72 3b 0a  pEntry = pIter;.
31e0: 20 20 20 20 20 20 20 20 70 45 6e 74 72 79 2d 3e          pEntry->
31f0: 70 53 63 61 6e 4e 65 78 74 20 3d 20 30 3b 0a 20  pScanNext = 0;. 
3200: 20 20 20 20 20 20 20 66 6f 72 28 69 3d 30 3b 20         for(i=0; 
3210: 61 70 5b 69 5d 3b 20 69 2b 2b 29 7b 0a 20 20 20  ap[i]; i++){.   
3220: 20 20 20 20 20 20 20 70 45 6e 74 72 79 20 3d 20         pEntry = 
3230: 66 74 73 35 48 61 73 68 45 6e 74 72 79 4d 65 72  fts5HashEntryMer
3240: 67 65 28 70 45 6e 74 72 79 2c 20 61 70 5b 69 5d  ge(pEntry, ap[i]
3250: 29 3b 0a 20 20 20 20 20 20 20 20 20 20 61 70 5b  );.          ap[
3260: 69 5d 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20  i] = 0;.        
3270: 7d 0a 20 20 20 20 20 20 20 20 61 70 5b 69 5d 20  }.        ap[i] 
3280: 3d 20 70 45 6e 74 72 79 3b 0a 20 20 20 20 20 20  = pEntry;.      
3290: 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 70  }.    }.  }..  p
32a0: 4c 69 73 74 20 3d 20 30 3b 0a 20 20 66 6f 72 28  List = 0;.  for(
32b0: 69 3d 30 3b 20 69 3c 6e 4d 65 72 67 65 53 6c 6f  i=0; i<nMergeSlo
32c0: 74 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 70 4c 69  t; i++){.    pLi
32d0: 73 74 20 3d 20 66 74 73 35 48 61 73 68 45 6e 74  st = fts5HashEnt
32e0: 72 79 4d 65 72 67 65 28 70 4c 69 73 74 2c 20 61  ryMerge(pList, a
32f0: 70 5b 69 5d 29 3b 0a 20 20 7d 0a 0a 20 20 70 48  p[i]);.  }..  pH
3300: 61 73 68 2d 3e 6e 45 6e 74 72 79 20 3d 20 30 3b  ash->nEntry = 0;
3310: 0a 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28  .  sqlite3_free(
3320: 61 70 29 3b 0a 20 20 2a 70 70 53 6f 72 74 65 64  ap);.  *ppSorted
3330: 20 3d 20 70 4c 69 73 74 3b 0a 20 20 72 65 74 75   = pList;.  retu
3340: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a  rn SQLITE_OK;.}.
3350: 0a 2f 2a 0a 2a 2a 20 51 75 65 72 79 20 74 68 65  ./*.** Query the
3360: 20 68 61 73 68 20 74 61 62 6c 65 20 66 6f 72 20   hash table for 
3370: 61 20 64 6f 63 6c 69 73 74 20 61 73 73 6f 63 69  a doclist associ
3380: 61 74 65 64 20 77 69 74 68 20 74 65 72 6d 20 70  ated with term p
3390: 54 65 72 6d 2f 6e 54 65 72 6d 2e 0a 2a 2f 0a 69  Term/nTerm..*/.i
33a0: 6e 74 20 73 71 6c 69 74 65 33 46 74 73 35 48 61  nt sqlite3Fts5Ha
33b0: 73 68 51 75 65 72 79 28 0a 20 20 46 74 73 35 48  shQuery(.  Fts5H
33c0: 61 73 68 20 2a 70 48 61 73 68 2c 20 20 20 20 20  ash *pHash,     
33d0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 48 61             /* Ha
33e0: 73 68 20 74 61 62 6c 65 20 74 6f 20 71 75 65 72  sh table to quer
33f0: 79 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61  y */.  const cha
3400: 72 20 2a 70 54 65 72 6d 2c 20 69 6e 74 20 6e 54  r *pTerm, int nT
3410: 65 72 6d 2c 20 20 20 2f 2a 20 51 75 65 72 79 20  erm,   /* Query 
3420: 74 65 72 6d 20 2a 2f 0a 20 20 63 6f 6e 73 74 20  term */.  const 
3430: 75 38 20 2a 2a 70 70 44 6f 63 6c 69 73 74 2c 20  u8 **ppDoclist, 
3440: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 54            /* OUT
3450: 3a 20 50 6f 69 6e 74 65 72 20 74 6f 20 64 6f 63  : Pointer to doc
3460: 6c 69 73 74 20 66 6f 72 20 70 54 65 72 6d 20 2a  list for pTerm *
3470: 2f 0a 20 20 69 6e 74 20 2a 70 6e 44 6f 63 6c 69  /.  int *pnDocli
3480: 73 74 20 20 20 20 20 20 20 20 20 20 20 20 20 20  st              
3490: 20 20 20 20 2f 2a 20 4f 55 54 3a 20 53 69 7a 65      /* OUT: Size
34a0: 20 6f 66 20 64 6f 63 6c 69 73 74 20 69 6e 20 62   of doclist in b
34b0: 79 74 65 73 20 2a 2f 0a 29 7b 0a 20 20 75 6e 73  ytes */.){.  uns
34c0: 69 67 6e 65 64 20 69 6e 74 20 69 48 61 73 68 20  igned int iHash 
34d0: 3d 20 66 74 73 35 48 61 73 68 4b 65 79 28 70 48  = fts5HashKey(pH
34e0: 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20 28 63 6f 6e  ash->nSlot, (con
34f0: 73 74 20 75 38 2a 29 70 54 65 72 6d 2c 20 6e 54  st u8*)pTerm, nT
3500: 65 72 6d 29 3b 0a 20 20 46 74 73 35 48 61 73 68  erm);.  Fts5Hash
3510: 45 6e 74 72 79 20 2a 70 3b 0a 0a 20 20 66 6f 72  Entry *p;..  for
3520: 28 70 3d 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b  (p=pHash->aSlot[
3530: 69 48 61 73 68 5d 3b 20 70 3b 20 70 3d 70 2d 3e  iHash]; p; p=p->
3540: 70 48 61 73 68 4e 65 78 74 29 7b 0a 20 20 20 20  pHashNext){.    
3550: 69 66 28 20 6d 65 6d 63 6d 70 28 70 2d 3e 7a 4b  if( memcmp(p->zK
3560: 65 79 2c 20 70 54 65 72 6d 2c 20 6e 54 65 72 6d  ey, pTerm, nTerm
3570: 29 3d 3d 30 20 26 26 20 70 2d 3e 7a 4b 65 79 5b  )==0 && p->zKey[
3580: 6e 54 65 72 6d 5d 3d 3d 30 20 29 20 62 72 65 61  nTerm]==0 ) brea
3590: 6b 3b 0a 20 20 7d 0a 0a 20 20 69 66 28 20 70 20  k;.  }..  if( p 
35a0: 29 7b 0a 20 20 20 20 66 74 73 35 48 61 73 68 41  ){.    fts5HashA
35b0: 64 64 50 6f 73 6c 69 73 74 53 69 7a 65 28 70 48  ddPoslistSize(pH
35c0: 61 73 68 2c 20 70 29 3b 0a 20 20 20 20 2a 70 70  ash, p);.    *pp
35d0: 44 6f 63 6c 69 73 74 20 3d 20 28 63 6f 6e 73 74  Doclist = (const
35e0: 20 75 38 2a 29 26 70 2d 3e 7a 4b 65 79 5b 6e 54   u8*)&p->zKey[nT
35f0: 65 72 6d 2b 31 5d 3b 0a 20 20 20 20 2a 70 6e 44  erm+1];.    *pnD
3600: 6f 63 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74  oclist = p->nDat
3610: 61 20 2d 20 28 46 54 53 35 5f 48 41 53 48 45 4e  a - (FTS5_HASHEN
3620: 54 52 59 53 49 5a 45 20 2b 20 6e 54 65 72 6d 20  TRYSIZE + nTerm 
3630: 2b 20 31 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20  + 1);.  }else{. 
3640: 20 20 20 2a 70 70 44 6f 63 6c 69 73 74 20 3d 20     *ppDoclist = 
3650: 30 3b 0a 20 20 20 20 2a 70 6e 44 6f 63 6c 69 73  0;.    *pnDoclis
3660: 74 20 3d 20 30 3b 0a 20 20 7d 0a 0a 20 20 72 65  t = 0;.  }..  re
3670: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a  turn SQLITE_OK;.
3680: 7d 0a 0a 69 6e 74 20 73 71 6c 69 74 65 33 46 74  }..int sqlite3Ft
3690: 73 35 48 61 73 68 53 63 61 6e 49 6e 69 74 28 0a  s5HashScanInit(.
36a0: 20 20 46 74 73 35 48 61 73 68 20 2a 70 2c 20 20    Fts5Hash *p,  
36b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
36c0: 20 20 2f 2a 20 48 61 73 68 20 74 61 62 6c 65 20    /* Hash table 
36d0: 74 6f 20 71 75 65 72 79 20 2a 2f 0a 20 20 63 6f  to query */.  co
36e0: 6e 73 74 20 63 68 61 72 20 2a 70 54 65 72 6d 2c  nst char *pTerm,
36f0: 20 69 6e 74 20 6e 54 65 72 6d 20 20 20 20 2f 2a   int nTerm    /*
3700: 20 51 75 65 72 79 20 70 72 65 66 69 78 20 2a 2f   Query prefix */
3710: 0a 29 7b 0a 20 20 72 65 74 75 72 6e 20 66 74 73  .){.  return fts
3720: 35 48 61 73 68 45 6e 74 72 79 53 6f 72 74 28 70  5HashEntrySort(p
3730: 2c 20 70 54 65 72 6d 2c 20 6e 54 65 72 6d 2c 20  , pTerm, nTerm, 
3740: 26 70 2d 3e 70 53 63 61 6e 29 3b 0a 7d 0a 0a 76  &p->pScan);.}..v
3750: 6f 69 64 20 73 71 6c 69 74 65 33 46 74 73 35 48  oid sqlite3Fts5H
3760: 61 73 68 53 63 61 6e 4e 65 78 74 28 46 74 73 35  ashScanNext(Fts5
3770: 48 61 73 68 20 2a 70 29 7b 0a 20 20 61 73 73 65  Hash *p){.  asse
3780: 72 74 28 20 21 73 71 6c 69 74 65 33 46 74 73 35  rt( !sqlite3Fts5
3790: 48 61 73 68 53 63 61 6e 45 6f 66 28 70 29 20 29  HashScanEof(p) )
37a0: 3b 0a 20 20 70 2d 3e 70 53 63 61 6e 20 3d 20 70  ;.  p->pScan = p
37b0: 2d 3e 70 53 63 61 6e 2d 3e 70 53 63 61 6e 4e 65  ->pScan->pScanNe
37c0: 78 74 3b 0a 7d 0a 0a 69 6e 74 20 73 71 6c 69 74  xt;.}..int sqlit
37d0: 65 33 46 74 73 35 48 61 73 68 53 63 61 6e 45 6f  e3Fts5HashScanEo
37e0: 66 28 46 74 73 35 48 61 73 68 20 2a 70 29 7b 0a  f(Fts5Hash *p){.
37f0: 20 20 72 65 74 75 72 6e 20 28 70 2d 3e 70 53 63    return (p->pSc
3800: 61 6e 3d 3d 30 29 3b 0a 7d 0a 0a 76 6f 69 64 20  an==0);.}..void 
3810: 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 53  sqlite3Fts5HashS
3820: 63 61 6e 45 6e 74 72 79 28 0a 20 20 46 74 73 35  canEntry(.  Fts5
3830: 48 61 73 68 20 2a 70 48 61 73 68 2c 0a 20 20 63  Hash *pHash,.  c
3840: 6f 6e 73 74 20 63 68 61 72 20 2a 2a 70 7a 54 65  onst char **pzTe
3850: 72 6d 2c 20 20 20 20 20 20 20 20 20 20 20 20 2f  rm,            /
3860: 2a 20 4f 55 54 3a 20 74 65 72 6d 20 28 6e 75 6c  * OUT: term (nul
3870: 2d 74 65 72 6d 69 6e 61 74 65 64 29 20 2a 2f 0a  -terminated) */.
3880: 20 20 63 6f 6e 73 74 20 75 38 20 2a 2a 70 70 44    const u8 **ppD
3890: 6f 63 6c 69 73 74 2c 20 20 20 20 20 20 20 20 20  oclist,         
38a0: 20 20 2f 2a 20 4f 55 54 3a 20 70 6f 69 6e 74 65    /* OUT: pointe
38b0: 72 20 74 6f 20 64 6f 63 6c 69 73 74 20 2a 2f 0a  r to doclist */.
38c0: 20 20 69 6e 74 20 2a 70 6e 44 6f 63 6c 69 73 74    int *pnDoclist
38d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
38e0: 20 20 2f 2a 20 4f 55 54 3a 20 73 69 7a 65 20 6f    /* OUT: size o
38f0: 66 20 64 6f 63 6c 69 73 74 20 69 6e 20 62 79 74  f doclist in byt
3900: 65 73 20 2a 2f 0a 29 7b 0a 20 20 46 74 73 35 48  es */.){.  Fts5H
3910: 61 73 68 45 6e 74 72 79 20 2a 70 3b 0a 20 20 69  ashEntry *p;.  i
3920: 66 28 20 28 70 20 3d 20 70 48 61 73 68 2d 3e 70  f( (p = pHash->p
3930: 53 63 61 6e 29 20 29 7b 0a 20 20 20 20 69 6e 74  Scan) ){.    int
3940: 20 6e 54 65 72 6d 20 3d 20 28 69 6e 74 29 73 74   nTerm = (int)st
3950: 72 6c 65 6e 28 70 2d 3e 7a 4b 65 79 29 3b 0a 20  rlen(p->zKey);. 
3960: 20 20 20 66 74 73 35 48 61 73 68 41 64 64 50 6f     fts5HashAddPo
3970: 73 6c 69 73 74 53 69 7a 65 28 70 48 61 73 68 2c  slistSize(pHash,
3980: 20 70 29 3b 0a 20 20 20 20 2a 70 7a 54 65 72 6d   p);.    *pzTerm
3990: 20 3d 20 70 2d 3e 7a 4b 65 79 3b 0a 20 20 20 20   = p->zKey;.    
39a0: 2a 70 70 44 6f 63 6c 69 73 74 20 3d 20 28 63 6f  *ppDoclist = (co
39b0: 6e 73 74 20 75 38 2a 29 26 70 2d 3e 7a 4b 65 79  nst u8*)&p->zKey
39c0: 5b 6e 54 65 72 6d 2b 31 5d 3b 0a 20 20 20 20 2a  [nTerm+1];.    *
39d0: 70 6e 44 6f 63 6c 69 73 74 20 3d 20 70 2d 3e 6e  pnDoclist = p->n
39e0: 44 61 74 61 20 2d 20 28 46 54 53 35 5f 48 41 53  Data - (FTS5_HAS
39f0: 48 45 4e 54 52 59 53 49 5a 45 20 2b 20 6e 54 65  HENTRYSIZE + nTe
3a00: 72 6d 20 2b 20 31 29 3b 0a 20 20 7d 65 6c 73 65  rm + 1);.  }else
3a10: 7b 0a 20 20 20 20 2a 70 7a 54 65 72 6d 20 3d 20  {.    *pzTerm = 
3a20: 30 3b 0a 20 20 20 20 2a 70 70 44 6f 63 6c 69 73  0;.    *ppDoclis
3a30: 74 20 3d 20 30 3b 0a 20 20 20 20 2a 70 6e 44 6f  t = 0;.    *pnDo
3a40: 63 6c 69 73 74 20 3d 20 30 3b 0a 20 20 7d 0a 7d  clist = 0;.  }.}
3a50: 0a 0a                                            ..