/ Hex Artifact Content
Login

Artifact d415f5ad332b051f0ade564bcf1762c4467cc49b2ba8ea5873d8744c705d8d42:


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 61 20 6e 75 6c 2d 74 65 72 6d 69 6e 61 74 65  (a nul-terminate
0490: 64 20 73 74 72 69 6e 67 29 20 61 6e 64 20 0a 2a  d string) and .*
04a0: 2a 20 69 74 73 20 63 75 72 72 65 6e 74 20 64 61  * its current da
04b0: 74 61 20 61 72 65 20 73 74 6f 72 65 64 20 69 6e  ta are stored in
04c0: 20 61 20 73 69 6e 67 6c 65 20 6d 65 6d 6f 72 79   a single memory
04d0: 20 61 6c 6c 6f 63 61 74 69 6f 6e 2e 20 54 68 65   allocation. The
04e0: 20 0a 2a 2a 20 6b 65 79 20 69 6d 6d 65 64 69 61   .** key immedia
04f0: 74 65 6c 79 20 66 6f 6c 6c 6f 77 73 20 74 68 65  tely follows the
0500: 20 6f 62 6a 65 63 74 20 69 6e 20 6d 65 6d 6f 72   object in memor
0510: 79 2e 20 54 68 65 20 70 6f 73 69 74 69 6f 6e 20  y. The position 
0520: 6c 69 73 74 0a 2a 2a 20 64 61 74 61 20 69 6d 6d  list.** data imm
0530: 65 64 69 61 74 65 6c 79 20 66 6f 6c 6c 6f 77 73  ediately follows
0540: 20 74 68 65 20 6b 65 79 20 64 61 74 61 20 69 6e   the key data in
0550: 20 6d 65 6d 6f 72 79 2e 0a 2a 2a 0a 2a 2a 20 54   memory..**.** T
0560: 68 65 20 64 61 74 61 20 74 68 61 74 20 66 6f 6c  he data that fol
0570: 6c 6f 77 73 20 74 68 65 20 6b 65 79 20 69 73 20  lows the key is 
0580: 69 6e 20 61 20 73 69 6d 69 6c 61 72 2c 20 62 75  in a similar, bu
0590: 74 20 6e 6f 74 20 69 64 65 6e 74 69 63 61 6c 20  t not identical 
05a0: 66 6f 72 6d 61 74 0a 2a 2a 20 74 6f 20 74 68 65  format.** to the
05b0: 20 64 6f 63 6c 69 73 74 20 64 61 74 61 20 73 74   doclist data st
05c0: 6f 72 65 64 20 69 6e 20 74 68 65 20 64 61 74 61  ored in the data
05d0: 62 61 73 65 2e 20 49 74 20 69 73 3a 0a 2a 2a 0a  base. It is:.**.
05e0: 2a 2a 20 20 20 2a 20 52 6f 77 69 64 2c 20 61 73  **   * Rowid, as
05f0: 20 61 20 76 61 72 69 6e 74 0a 2a 2a 20 20 20 2a   a varint.**   *
0600: 20 50 6f 73 69 74 69 6f 6e 20 6c 69 73 74 2c 20   Position list, 
0610: 77 69 74 68 6f 75 74 20 30 78 30 30 20 74 65 72  without 0x00 ter
0620: 6d 69 6e 61 74 6f 72 2e 0a 2a 2a 20 20 20 2a 20  minator..**   * 
0630: 53 69 7a 65 20 6f 66 20 70 72 65 76 69 6f 75 73  Size of previous
0640: 20 70 6f 73 69 74 69 6f 6e 20 6c 69 73 74 20 61   position list a
0650: 6e 64 20 72 6f 77 69 64 2c 20 61 73 20 61 20 34  nd rowid, as a 4
0660: 20 62 79 74 65 0a 2a 2a 20 20 20 20 20 62 69 67   byte.**     big
0670: 2d 65 6e 64 69 61 6e 20 69 6e 74 65 67 65 72 2e  -endian integer.
0680: 0a 2a 2a 0a 2a 2a 20 69 52 6f 77 69 64 4f 66 66  .**.** iRowidOff
0690: 3a 0a 2a 2a 20 20 20 4f 66 66 73 65 74 20 6f 66  :.**   Offset of
06a0: 20 6c 61 73 74 20 72 6f 77 69 64 20 77 72 69 74   last rowid writ
06b0: 74 65 6e 20 74 6f 20 64 61 74 61 20 61 72 65 61  ten to data area
06c0: 2e 20 52 65 6c 61 74 69 76 65 20 74 6f 20 66 69  . Relative to fi
06d0: 72 73 74 20 62 79 74 65 20 6f 66 0a 2a 2a 20 20  rst byte of.**  
06e0: 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2a 0a 2a   structure..**.*
06f0: 2a 20 6e 44 61 74 61 3a 0a 2a 2a 20 20 20 42 79  * nData:.**   By
0700: 74 65 73 20 6f 66 20 64 61 74 61 20 77 72 69 74  tes of data writ
0710: 74 65 6e 20 73 69 6e 63 65 20 69 52 6f 77 69 64  ten since iRowid
0720: 4f 66 66 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 46  Off..*/.struct F
0730: 74 73 35 48 61 73 68 45 6e 74 72 79 20 7b 0a 20  ts5HashEntry {. 
0740: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
0750: 70 48 61 73 68 4e 65 78 74 3b 20 20 20 20 20 20  pHashNext;      
0760: 20 2f 2a 20 4e 65 78 74 20 68 61 73 68 20 65 6e   /* Next hash en
0770: 74 72 79 20 77 69 74 68 20 73 61 6d 65 20 68 61  try with same ha
0780: 73 68 2d 6b 65 79 20 2a 2f 0a 20 20 46 74 73 35  sh-key */.  Fts5
0790: 48 61 73 68 45 6e 74 72 79 20 2a 70 53 63 61 6e  HashEntry *pScan
07a0: 4e 65 78 74 3b 20 20 20 20 20 20 20 2f 2a 20 4e  Next;       /* N
07b0: 65 78 74 20 65 6e 74 72 79 20 69 6e 20 73 6f 72  ext entry in sor
07c0: 74 65 64 20 6f 72 64 65 72 20 2a 2f 0a 20 20 0a  ted order */.  .
07d0: 20 20 69 6e 74 20 6e 41 6c 6c 6f 63 3b 20 20 20    int nAlloc;   
07e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
07f0: 20 20 2f 2a 20 54 6f 74 61 6c 20 73 69 7a 65 20    /* Total size 
0800: 6f 66 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 2a 2f  of allocation */
0810: 0a 20 20 69 6e 74 20 69 53 7a 50 6f 73 6c 69 73  .  int iSzPoslis
0820: 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  t;              
0830: 20 20 20 2f 2a 20 4f 66 66 73 65 74 20 6f 66 20     /* Offset of 
0840: 73 70 61 63 65 20 66 6f 72 20 34 2d 62 79 74 65  space for 4-byte
0850: 20 70 6f 73 6c 69 73 74 20 73 69 7a 65 20 2a 2f   poslist size */
0860: 0a 20 20 69 6e 74 20 6e 44 61 74 61 3b 20 20 20  .  int nData;   
0870: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0880: 20 20 20 2f 2a 20 54 6f 74 61 6c 20 62 79 74 65     /* Total byte
0890: 73 20 6f 66 20 64 61 74 61 20 28 69 6e 63 6c 2e  s of data (incl.
08a0: 20 73 74 72 75 63 74 75 72 65 29 20 2a 2f 0a 20   structure) */. 
08b0: 20 69 6e 74 20 6e 4b 65 79 3b 20 20 20 20 20 20   int nKey;      
08c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
08d0: 20 2f 2a 20 4c 65 6e 67 74 68 20 6f 66 20 6b 65   /* Length of ke
08e0: 79 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a 20 20  y in bytes */.  
08f0: 75 38 20 62 44 65 6c 3b 20 20 20 20 20 20 20 20  u8 bDel;        
0900: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0910: 2f 2a 20 53 65 74 20 64 65 6c 65 74 65 2d 66 6c  /* Set delete-fl
0920: 61 67 20 40 20 69 53 7a 50 6f 73 6c 69 73 74 20  ag @ iSzPoslist 
0930: 2a 2f 0a 20 20 75 38 20 62 43 6f 6e 74 65 6e 74  */.  u8 bContent
0940: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
0950: 20 20 20 20 20 2f 2a 20 53 65 74 20 63 6f 6e 74       /* Set cont
0960: 65 6e 74 2d 66 6c 61 67 20 28 64 65 74 61 69 6c  ent-flag (detail
0970: 3d 6e 6f 6e 65 20 6d 6f 64 65 29 20 2a 2f 0a 20  =none mode) */. 
0980: 20 69 31 36 20 69 43 6f 6c 3b 20 20 20 20 20 20   i16 iCol;      
0990: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
09a0: 20 2f 2a 20 43 6f 6c 75 6d 6e 20 6f 66 20 6c 61   /* Column of la
09b0: 73 74 20 76 61 6c 75 65 20 77 72 69 74 74 65 6e  st value written
09c0: 20 2a 2f 0a 20 20 69 6e 74 20 69 50 6f 73 3b 20   */.  int iPos; 
09d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
09e0: 20 20 20 20 20 20 2f 2a 20 50 6f 73 69 74 69 6f        /* Positio
09f0: 6e 20 6f 66 20 6c 61 73 74 20 76 61 6c 75 65 20  n of last value 
0a00: 77 72 69 74 74 65 6e 20 2a 2f 0a 20 20 69 36 34  written */.  i64
0a10: 20 69 52 6f 77 69 64 3b 20 20 20 20 20 20 20 20   iRowid;        
0a20: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
0a30: 52 6f 77 69 64 20 6f 66 20 6c 61 73 74 20 76 61  Rowid of last va
0a40: 6c 75 65 20 77 72 69 74 74 65 6e 20 2a 2f 0a 7d  lue written */.}
0a50: 3b 0a 0a 2f 2a 0a 2a 2a 20 45 71 69 76 61 6c 65  ;../*.** Eqivale
0a60: 6e 74 20 74 6f 3a 0a 2a 2a 0a 2a 2a 20 20 20 63  nt to:.**.**   c
0a70: 68 61 72 20 2a 66 74 73 35 45 6e 74 72 79 4b 65  har *fts5EntryKe
0a80: 79 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 20  y(Fts5HashEntry 
0a90: 2a 70 45 6e 74 72 79 29 7b 20 72 65 74 75 72 6e  *pEntry){ return
0aa0: 20 7a 4b 65 79 3b 20 7d 0a 2a 2f 0a 23 64 65 66   zKey; }.*/.#def
0ab0: 69 6e 65 20 66 74 73 35 45 6e 74 72 79 4b 65 79  ine fts5EntryKey
0ac0: 28 70 29 20 28 20 28 28 63 68 61 72 20 2a 29 28  (p) ( ((char *)(
0ad0: 26 28 70 29 5b 31 5d 29 29 20 29 0a 0a 0a 2f 2a  &(p)[1])) ).../*
0ae0: 0a 2a 2a 20 41 6c 6c 6f 63 61 74 65 20 61 20 6e  .** Allocate a n
0af0: 65 77 20 68 61 73 68 20 74 61 62 6c 65 2e 0a 2a  ew hash table..*
0b00: 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 46 74 73  /.int sqlite3Fts
0b10: 35 48 61 73 68 4e 65 77 28 46 74 73 35 43 6f 6e  5HashNew(Fts5Con
0b20: 66 69 67 20 2a 70 43 6f 6e 66 69 67 2c 20 46 74  fig *pConfig, Ft
0b30: 73 35 48 61 73 68 20 2a 2a 70 70 4e 65 77 2c 20  s5Hash **ppNew, 
0b40: 69 6e 74 20 2a 70 6e 42 79 74 65 29 7b 0a 20 20  int *pnByte){.  
0b50: 69 6e 74 20 72 63 20 3d 20 53 51 4c 49 54 45 5f  int rc = SQLITE_
0b60: 4f 4b 3b 0a 20 20 46 74 73 35 48 61 73 68 20 2a  OK;.  Fts5Hash *
0b70: 70 4e 65 77 3b 0a 0a 20 20 2a 70 70 4e 65 77 20  pNew;..  *ppNew 
0b80: 3d 20 70 4e 65 77 20 3d 20 28 46 74 73 35 48 61  = pNew = (Fts5Ha
0b90: 73 68 2a 29 73 71 6c 69 74 65 33 5f 6d 61 6c 6c  sh*)sqlite3_mall
0ba0: 6f 63 28 73 69 7a 65 6f 66 28 46 74 73 35 48 61  oc(sizeof(Fts5Ha
0bb0: 73 68 29 29 3b 0a 20 20 69 66 28 20 70 4e 65 77  sh));.  if( pNew
0bc0: 3d 3d 30 20 29 7b 0a 20 20 20 20 72 63 20 3d 20  ==0 ){.    rc = 
0bd0: 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20  SQLITE_NOMEM;.  
0be0: 7d 65 6c 73 65 7b 0a 20 20 20 20 73 71 6c 69 74  }else{.    sqlit
0bf0: 65 33 5f 69 6e 74 36 34 20 6e 42 79 74 65 3b 0a  e3_int64 nByte;.
0c00: 20 20 20 20 6d 65 6d 73 65 74 28 70 4e 65 77 2c      memset(pNew,
0c10: 20 30 2c 20 73 69 7a 65 6f 66 28 46 74 73 35 48   0, sizeof(Fts5H
0c20: 61 73 68 29 29 3b 0a 20 20 20 20 70 4e 65 77 2d  ash));.    pNew-
0c30: 3e 70 6e 42 79 74 65 20 3d 20 70 6e 42 79 74 65  >pnByte = pnByte
0c40: 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 65 44 65 74  ;.    pNew->eDet
0c50: 61 69 6c 20 3d 20 70 43 6f 6e 66 69 67 2d 3e 65  ail = pConfig->e
0c60: 44 65 74 61 69 6c 3b 0a 0a 20 20 20 20 70 4e 65  Detail;..    pNe
0c70: 77 2d 3e 6e 53 6c 6f 74 20 3d 20 31 30 32 34 3b  w->nSlot = 1024;
0c80: 0a 20 20 20 20 6e 42 79 74 65 20 3d 20 73 69 7a  .    nByte = siz
0c90: 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 72  eof(Fts5HashEntr
0ca0: 79 2a 29 20 2a 20 70 4e 65 77 2d 3e 6e 53 6c 6f  y*) * pNew->nSlo
0cb0: 74 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 61 53 6c  t;.    pNew->aSl
0cc0: 6f 74 20 3d 20 28 46 74 73 35 48 61 73 68 45 6e  ot = (Fts5HashEn
0cd0: 74 72 79 2a 2a 29 73 71 6c 69 74 65 33 5f 6d 61  try**)sqlite3_ma
0ce0: 6c 6c 6f 63 36 34 28 6e 42 79 74 65 29 3b 0a 20  lloc64(nByte);. 
0cf0: 20 20 20 69 66 28 20 70 4e 65 77 2d 3e 61 53 6c     if( pNew->aSl
0d00: 6f 74 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 73  ot==0 ){.      s
0d10: 71 6c 69 74 65 33 5f 66 72 65 65 28 70 4e 65 77  qlite3_free(pNew
0d20: 29 3b 0a 20 20 20 20 20 20 2a 70 70 4e 65 77 20  );.      *ppNew 
0d30: 3d 20 30 3b 0a 20 20 20 20 20 20 72 63 20 3d 20  = 0;.      rc = 
0d40: 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20  SQLITE_NOMEM;.  
0d50: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 6d    }else{.      m
0d60: 65 6d 73 65 74 28 70 4e 65 77 2d 3e 61 53 6c 6f  emset(pNew->aSlo
0d70: 74 2c 20 30 2c 20 6e 42 79 74 65 29 3b 0a 20 20  t, 0, nByte);.  
0d80: 20 20 7d 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e    }.  }.  return
0d90: 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 46 72   rc;.}../*.** Fr
0da0: 65 65 20 61 20 68 61 73 68 20 74 61 62 6c 65 20  ee a hash table 
0db0: 6f 62 6a 65 63 74 2e 0a 2a 2f 0a 76 6f 69 64 20  object..*/.void 
0dc0: 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 46  sqlite3Fts5HashF
0dd0: 72 65 65 28 46 74 73 35 48 61 73 68 20 2a 70 48  ree(Fts5Hash *pH
0de0: 61 73 68 29 7b 0a 20 20 69 66 28 20 70 48 61 73  ash){.  if( pHas
0df0: 68 20 29 7b 0a 20 20 20 20 73 71 6c 69 74 65 33  h ){.    sqlite3
0e00: 46 74 73 35 48 61 73 68 43 6c 65 61 72 28 70 48  Fts5HashClear(pH
0e10: 61 73 68 29 3b 0a 20 20 20 20 73 71 6c 69 74 65  ash);.    sqlite
0e20: 33 5f 66 72 65 65 28 70 48 61 73 68 2d 3e 61 53  3_free(pHash->aS
0e30: 6c 6f 74 29 3b 0a 20 20 20 20 73 71 6c 69 74 65  lot);.    sqlite
0e40: 33 5f 66 72 65 65 28 70 48 61 73 68 29 3b 0a 20  3_free(pHash);. 
0e50: 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 45 6d 70 74   }.}../*.** Empt
0e60: 79 20 28 62 75 74 20 64 6f 20 6e 6f 74 20 64 65  y (but do not de
0e70: 6c 65 74 65 29 20 61 20 68 61 73 68 20 74 61 62  lete) a hash tab
0e80: 6c 65 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69  le..*/.void sqli
0e90: 74 65 33 46 74 73 35 48 61 73 68 43 6c 65 61 72  te3Fts5HashClear
0ea0: 28 46 74 73 35 48 61 73 68 20 2a 70 48 61 73 68  (Fts5Hash *pHash
0eb0: 29 7b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 66 6f  ){.  int i;.  fo
0ec0: 72 28 69 3d 30 3b 20 69 3c 70 48 61 73 68 2d 3e  r(i=0; i<pHash->
0ed0: 6e 53 6c 6f 74 3b 20 69 2b 2b 29 7b 0a 20 20 20  nSlot; i++){.   
0ee0: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
0ef0: 70 4e 65 78 74 3b 0a 20 20 20 20 46 74 73 35 48  pNext;.    Fts5H
0f00: 61 73 68 45 6e 74 72 79 20 2a 70 53 6c 6f 74 3b  ashEntry *pSlot;
0f10: 0a 20 20 20 20 66 6f 72 28 70 53 6c 6f 74 3d 70  .    for(pSlot=p
0f20: 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 5d 3b 20  Hash->aSlot[i]; 
0f30: 70 53 6c 6f 74 3b 20 70 53 6c 6f 74 3d 70 4e 65  pSlot; pSlot=pNe
0f40: 78 74 29 7b 0a 20 20 20 20 20 20 70 4e 65 78 74  xt){.      pNext
0f50: 20 3d 20 70 53 6c 6f 74 2d 3e 70 48 61 73 68 4e   = pSlot->pHashN
0f60: 65 78 74 3b 0a 20 20 20 20 20 20 73 71 6c 69 74  ext;.      sqlit
0f70: 65 33 5f 66 72 65 65 28 70 53 6c 6f 74 29 3b 0a  e3_free(pSlot);.
0f80: 20 20 20 20 7d 0a 20 20 7d 0a 20 20 6d 65 6d 73      }.  }.  mems
0f90: 65 74 28 70 48 61 73 68 2d 3e 61 53 6c 6f 74 2c  et(pHash->aSlot,
0fa0: 20 30 2c 20 70 48 61 73 68 2d 3e 6e 53 6c 6f 74   0, pHash->nSlot
0fb0: 20 2a 20 73 69 7a 65 6f 66 28 46 74 73 35 48 61   * sizeof(Fts5Ha
0fc0: 73 68 45 6e 74 72 79 2a 29 29 3b 0a 20 20 70 48  shEntry*));.  pH
0fd0: 61 73 68 2d 3e 6e 45 6e 74 72 79 20 3d 20 30 3b  ash->nEntry = 0;
0fe0: 0a 7d 0a 0a 73 74 61 74 69 63 20 75 6e 73 69 67  .}..static unsig
0ff0: 6e 65 64 20 69 6e 74 20 66 74 73 35 48 61 73 68  ned int fts5Hash
1000: 4b 65 79 28 69 6e 74 20 6e 53 6c 6f 74 2c 20 63  Key(int nSlot, c
1010: 6f 6e 73 74 20 75 38 20 2a 70 2c 20 69 6e 74 20  onst u8 *p, int 
1020: 6e 29 7b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 75  n){.  int i;.  u
1030: 6e 73 69 67 6e 65 64 20 69 6e 74 20 68 20 3d 20  nsigned int h = 
1040: 31 33 3b 0a 20 20 66 6f 72 28 69 3d 6e 2d 31 3b  13;.  for(i=n-1;
1050: 20 69 3e 3d 30 3b 20 69 2d 2d 29 7b 0a 20 20 20   i>=0; i--){.   
1060: 20 68 20 3d 20 28 68 20 3c 3c 20 33 29 20 5e 20   h = (h << 3) ^ 
1070: 68 20 5e 20 70 5b 69 5d 3b 0a 20 20 7d 0a 20 20  h ^ p[i];.  }.  
1080: 72 65 74 75 72 6e 20 28 68 20 25 20 6e 53 6c 6f  return (h % nSlo
1090: 74 29 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 75 6e  t);.}..static un
10a0: 73 69 67 6e 65 64 20 69 6e 74 20 66 74 73 35 48  signed int fts5H
10b0: 61 73 68 4b 65 79 32 28 69 6e 74 20 6e 53 6c 6f  ashKey2(int nSlo
10c0: 74 2c 20 75 38 20 62 2c 20 63 6f 6e 73 74 20 75  t, u8 b, const u
10d0: 38 20 2a 70 2c 20 69 6e 74 20 6e 29 7b 0a 20 20  8 *p, int n){.  
10e0: 69 6e 74 20 69 3b 0a 20 20 75 6e 73 69 67 6e 65  int i;.  unsigne
10f0: 64 20 69 6e 74 20 68 20 3d 20 31 33 3b 0a 20 20  d int h = 13;.  
1100: 66 6f 72 28 69 3d 6e 2d 31 3b 20 69 3e 3d 30 3b  for(i=n-1; i>=0;
1110: 20 69 2d 2d 29 7b 0a 20 20 20 20 68 20 3d 20 28   i--){.    h = (
1120: 68 20 3c 3c 20 33 29 20 5e 20 68 20 5e 20 70 5b  h << 3) ^ h ^ p[
1130: 69 5d 3b 0a 20 20 7d 0a 20 20 68 20 3d 20 28 68  i];.  }.  h = (h
1140: 20 3c 3c 20 33 29 20 5e 20 68 20 5e 20 62 3b 0a   << 3) ^ h ^ b;.
1150: 20 20 72 65 74 75 72 6e 20 28 68 20 25 20 6e 53    return (h % nS
1160: 6c 6f 74 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52  lot);.}../*.** R
1170: 65 73 69 7a 65 20 74 68 65 20 68 61 73 68 20 74  esize the hash t
1180: 61 62 6c 65 20 62 79 20 64 6f 75 62 6c 69 6e 67  able by doubling
1190: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 73   the number of s
11a0: 6c 6f 74 73 2e 0a 2a 2f 0a 73 74 61 74 69 63 20  lots..*/.static 
11b0: 69 6e 74 20 66 74 73 35 48 61 73 68 52 65 73 69  int fts5HashResi
11c0: 7a 65 28 46 74 73 35 48 61 73 68 20 2a 70 48 61  ze(Fts5Hash *pHa
11d0: 73 68 29 7b 0a 20 20 69 6e 74 20 6e 4e 65 77 20  sh){.  int nNew 
11e0: 3d 20 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 2a 32  = pHash->nSlot*2
11f0: 3b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 46 74 73  ;.  int i;.  Fts
1200: 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 61 70 4e  5HashEntry **apN
1210: 65 77 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e  ew;.  Fts5HashEn
1220: 74 72 79 20 2a 2a 61 70 4f 6c 64 20 3d 20 70 48  try **apOld = pH
1230: 61 73 68 2d 3e 61 53 6c 6f 74 3b 0a 0a 20 20 61  ash->aSlot;..  a
1240: 70 4e 65 77 20 3d 20 28 46 74 73 35 48 61 73 68  pNew = (Fts5Hash
1250: 45 6e 74 72 79 2a 2a 29 73 71 6c 69 74 65 33 5f  Entry**)sqlite3_
1260: 6d 61 6c 6c 6f 63 36 34 28 6e 4e 65 77 2a 73 69  malloc64(nNew*si
1270: 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74  zeof(Fts5HashEnt
1280: 72 79 2a 29 29 3b 0a 20 20 69 66 28 20 21 61 70  ry*));.  if( !ap
1290: 4e 65 77 20 29 20 72 65 74 75 72 6e 20 53 51 4c  New ) return SQL
12a0: 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 6d 65 6d  ITE_NOMEM;.  mem
12b0: 73 65 74 28 61 70 4e 65 77 2c 20 30 2c 20 6e 4e  set(apNew, 0, nN
12c0: 65 77 2a 73 69 7a 65 6f 66 28 46 74 73 35 48 61  ew*sizeof(Fts5Ha
12d0: 73 68 45 6e 74 72 79 2a 29 29 3b 0a 0a 20 20 66  shEntry*));..  f
12e0: 6f 72 28 69 3d 30 3b 20 69 3c 70 48 61 73 68 2d  or(i=0; i<pHash-
12f0: 3e 6e 53 6c 6f 74 3b 20 69 2b 2b 29 7b 0a 20 20  >nSlot; i++){.  
1300: 20 20 77 68 69 6c 65 28 20 61 70 4f 6c 64 5b 69    while( apOld[i
1310: 5d 20 29 7b 0a 20 20 20 20 20 20 75 6e 73 69 67  ] ){.      unsig
1320: 6e 65 64 20 69 6e 74 20 69 48 61 73 68 3b 0a 20  ned int iHash;. 
1330: 20 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74       Fts5HashEnt
1340: 72 79 20 2a 70 20 3d 20 61 70 4f 6c 64 5b 69 5d  ry *p = apOld[i]
1350: 3b 0a 20 20 20 20 20 20 61 70 4f 6c 64 5b 69 5d  ;.      apOld[i]
1360: 20 3d 20 70 2d 3e 70 48 61 73 68 4e 65 78 74 3b   = p->pHashNext;
1370: 0a 20 20 20 20 20 20 69 48 61 73 68 20 3d 20 66  .      iHash = f
1380: 74 73 35 48 61 73 68 4b 65 79 28 6e 4e 65 77 2c  ts5HashKey(nNew,
1390: 20 28 75 38 2a 29 66 74 73 35 45 6e 74 72 79 4b   (u8*)fts5EntryK
13a0: 65 79 28 70 29 2c 0a 20 20 20 20 20 20 20 20 20  ey(p),.         
13b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
13c0: 20 28 69 6e 74 29 73 74 72 6c 65 6e 28 66 74 73   (int)strlen(fts
13d0: 35 45 6e 74 72 79 4b 65 79 28 70 29 29 29 3b 0a  5EntryKey(p)));.
13e0: 20 20 20 20 20 20 70 2d 3e 70 48 61 73 68 4e 65        p->pHashNe
13f0: 78 74 20 3d 20 61 70 4e 65 77 5b 69 48 61 73 68  xt = apNew[iHash
1400: 5d 3b 0a 20 20 20 20 20 20 61 70 4e 65 77 5b 69  ];.      apNew[i
1410: 48 61 73 68 5d 20 3d 20 70 3b 0a 20 20 20 20 7d  Hash] = p;.    }
1420: 0a 20 20 7d 0a 0a 20 20 73 71 6c 69 74 65 33 5f  .  }..  sqlite3_
1430: 66 72 65 65 28 61 70 4f 6c 64 29 3b 0a 20 20 70  free(apOld);.  p
1440: 48 61 73 68 2d 3e 6e 53 6c 6f 74 20 3d 20 6e 4e  Hash->nSlot = nN
1450: 65 77 3b 0a 20 20 70 48 61 73 68 2d 3e 61 53 6c  ew;.  pHash->aSl
1460: 6f 74 20 3d 20 61 70 4e 65 77 3b 0a 20 20 72 65  ot = apNew;.  re
1470: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a  turn SQLITE_OK;.
1480: 7d 0a 0a 73 74 61 74 69 63 20 76 6f 69 64 20 66  }..static void f
1490: 74 73 35 48 61 73 68 41 64 64 50 6f 73 6c 69 73  ts5HashAddPoslis
14a0: 74 53 69 7a 65 28 46 74 73 35 48 61 73 68 20 2a  tSize(Fts5Hash *
14b0: 70 48 61 73 68 2c 20 46 74 73 35 48 61 73 68 45  pHash, Fts5HashE
14c0: 6e 74 72 79 20 2a 70 29 7b 0a 20 20 69 66 28 20  ntry *p){.  if( 
14d0: 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 29 7b  p->iSzPoslist ){
14e0: 0a 20 20 20 20 75 38 20 2a 70 50 74 72 20 3d 20  .    u8 *pPtr = 
14f0: 28 75 38 2a 29 70 3b 0a 20 20 20 20 69 66 28 20  (u8*)p;.    if( 
1500: 70 48 61 73 68 2d 3e 65 44 65 74 61 69 6c 3d 3d  pHash->eDetail==
1510: 46 54 53 35 5f 44 45 54 41 49 4c 5f 4e 4f 4e 45  FTS5_DETAIL_NONE
1520: 20 29 7b 0a 20 20 20 20 20 20 61 73 73 65 72 74   ){.      assert
1530: 28 20 70 2d 3e 6e 44 61 74 61 3d 3d 70 2d 3e 69  ( p->nData==p->i
1540: 53 7a 50 6f 73 6c 69 73 74 20 29 3b 0a 20 20 20  SzPoslist );.   
1550: 20 20 20 69 66 28 20 70 2d 3e 62 44 65 6c 20 29     if( p->bDel )
1560: 7b 0a 20 20 20 20 20 20 20 20 70 50 74 72 5b 70  {.        pPtr[p
1570: 2d 3e 6e 44 61 74 61 2b 2b 5d 20 3d 20 30 78 30  ->nData++] = 0x0
1580: 30 3b 0a 20 20 20 20 20 20 20 20 69 66 28 20 70  0;.        if( p
1590: 2d 3e 62 43 6f 6e 74 65 6e 74 20 29 7b 0a 20 20  ->bContent ){.  
15a0: 20 20 20 20 20 20 20 20 70 50 74 72 5b 70 2d 3e          pPtr[p->
15b0: 6e 44 61 74 61 2b 2b 5d 20 3d 20 30 78 30 30 3b  nData++] = 0x00;
15c0: 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20  .        }.     
15d0: 20 7d 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20   }.    }else{.  
15e0: 20 20 20 20 69 6e 74 20 6e 53 7a 20 3d 20 28 70      int nSz = (p
15f0: 2d 3e 6e 44 61 74 61 20 2d 20 70 2d 3e 69 53 7a  ->nData - p->iSz
1600: 50 6f 73 6c 69 73 74 20 2d 20 31 29 3b 20 20 20  Poslist - 1);   
1610: 20 20 20 20 2f 2a 20 53 69 7a 65 20 69 6e 20 62      /* Size in b
1620: 79 74 65 73 20 2a 2f 0a 20 20 20 20 20 20 69 6e  ytes */.      in
1630: 74 20 6e 50 6f 73 20 3d 20 6e 53 7a 2a 32 20 2b  t nPos = nSz*2 +
1640: 20 70 2d 3e 62 44 65 6c 3b 20 20 20 20 20 20 20   p->bDel;       
1650: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
1660: 20 56 61 6c 75 65 20 6f 66 20 6e 50 6f 73 20 66   Value of nPos f
1670: 69 65 6c 64 20 2a 2f 0a 0a 20 20 20 20 20 20 61  ield */..      a
1680: 73 73 65 72 74 28 20 70 2d 3e 62 44 65 6c 3d 3d  ssert( p->bDel==
1690: 30 20 7c 7c 20 70 2d 3e 62 44 65 6c 3d 3d 31 20  0 || p->bDel==1 
16a0: 29 3b 0a 20 20 20 20 20 20 69 66 28 20 6e 50 6f  );.      if( nPo
16b0: 73 3c 3d 31 32 37 20 29 7b 0a 20 20 20 20 20 20  s<=127 ){.      
16c0: 20 20 70 50 74 72 5b 70 2d 3e 69 53 7a 50 6f 73    pPtr[p->iSzPos
16d0: 6c 69 73 74 5d 20 3d 20 28 75 38 29 6e 50 6f 73  list] = (u8)nPos
16e0: 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20  ;.      }else{. 
16f0: 20 20 20 20 20 20 20 69 6e 74 20 6e 42 79 74 65         int nByte
1700: 20 3d 20 73 71 6c 69 74 65 33 46 74 73 35 47 65   = sqlite3Fts5Ge
1710: 74 56 61 72 69 6e 74 4c 65 6e 28 28 75 33 32 29  tVarintLen((u32)
1720: 6e 50 6f 73 29 3b 0a 20 20 20 20 20 20 20 20 6d  nPos);.        m
1730: 65 6d 6d 6f 76 65 28 26 70 50 74 72 5b 70 2d 3e  emmove(&pPtr[p->
1740: 69 53 7a 50 6f 73 6c 69 73 74 20 2b 20 6e 42 79  iSzPoslist + nBy
1750: 74 65 5d 2c 20 26 70 50 74 72 5b 70 2d 3e 69 53  te], &pPtr[p->iS
1760: 7a 50 6f 73 6c 69 73 74 20 2b 20 31 5d 2c 20 6e  zPoslist + 1], n
1770: 53 7a 29 3b 0a 20 20 20 20 20 20 20 20 73 71 6c  Sz);.        sql
1780: 69 74 65 33 46 74 73 35 50 75 74 56 61 72 69 6e  ite3Fts5PutVarin
1790: 74 28 26 70 50 74 72 5b 70 2d 3e 69 53 7a 50 6f  t(&pPtr[p->iSzPo
17a0: 73 6c 69 73 74 5d 2c 20 6e 50 6f 73 29 3b 0a 20  slist], nPos);. 
17b0: 20 20 20 20 20 20 20 70 2d 3e 6e 44 61 74 61 20         p->nData 
17c0: 2b 3d 20 28 6e 42 79 74 65 2d 31 29 3b 0a 20 20  += (nByte-1);.  
17d0: 20 20 20 20 7d 0a 20 20 20 20 7d 0a 0a 20 20 20      }.    }..   
17e0: 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 3d   p->iSzPoslist =
17f0: 20 30 3b 0a 20 20 20 20 70 2d 3e 62 44 65 6c 20   0;.    p->bDel 
1800: 3d 20 30 3b 0a 20 20 20 20 70 2d 3e 62 43 6f 6e  = 0;.    p->bCon
1810: 74 65 6e 74 20 3d 20 30 3b 0a 20 20 7d 0a 7d 0a  tent = 0;.  }.}.
1820: 0a 2f 2a 0a 2a 2a 20 41 64 64 20 61 6e 20 65 6e  ./*.** Add an en
1830: 74 72 79 20 74 6f 20 74 68 65 20 69 6e 2d 6d 65  try to the in-me
1840: 6d 6f 72 79 20 68 61 73 68 20 74 61 62 6c 65 2e  mory hash table.
1850: 20 54 68 65 20 6b 65 79 20 69 73 20 74 68 65 20   The key is the 
1860: 63 6f 6e 63 61 74 65 6e 61 74 69 6f 6e 0a 2a 2a  concatenation.**
1870: 20 6f 66 20 62 42 79 74 65 20 61 6e 64 20 28 70   of bByte and (p
1880: 54 6f 6b 65 6e 2f 6e 54 6f 6b 65 6e 29 2e 20 54  Token/nToken). T
1890: 68 65 20 76 61 6c 75 65 20 69 73 20 28 69 52 6f  he value is (iRo
18a0: 77 69 64 2f 69 43 6f 6c 2f 69 50 6f 73 29 2e 0a  wid/iCol/iPos)..
18b0: 2a 2a 0a 2a 2a 20 20 20 20 20 28 62 42 79 74 65  **.**     (bByte
18c0: 20 7c 7c 20 70 54 6f 6b 65 6e 29 20 2d 3e 20 28   || pToken) -> (
18d0: 69 52 6f 77 69 64 2c 69 43 6f 6c 2c 69 50 6f 73  iRowid,iCol,iPos
18e0: 29 0a 2a 2a 0a 2a 2a 20 4f 72 2c 20 69 66 20 69  ).**.** Or, if i
18f0: 43 6f 6c 20 69 73 20 6e 65 67 61 74 69 76 65 2c  Col is negative,
1900: 20 74 68 65 6e 20 74 68 65 20 76 61 6c 75 65 20   then the value 
1910: 69 73 20 61 20 64 65 6c 65 74 65 20 6d 61 72 6b  is a delete mark
1920: 65 72 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74  er..*/.int sqlit
1930: 65 33 46 74 73 35 48 61 73 68 57 72 69 74 65 28  e3Fts5HashWrite(
1940: 0a 20 20 46 74 73 35 48 61 73 68 20 2a 70 48 61  .  Fts5Hash *pHa
1950: 73 68 2c 0a 20 20 69 36 34 20 69 52 6f 77 69 64  sh,.  i64 iRowid
1960: 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ,               
1970: 20 20 20 20 20 20 2f 2a 20 52 6f 77 69 64 20 66        /* Rowid f
1980: 6f 72 20 74 68 69 73 20 65 6e 74 72 79 20 2a 2f  or this entry */
1990: 0a 20 20 69 6e 74 20 69 43 6f 6c 2c 20 20 20 20  .  int iCol,    
19a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
19b0: 20 20 20 2f 2a 20 43 6f 6c 75 6d 6e 20 74 6f 6b     /* Column tok
19c0: 65 6e 20 61 70 70 65 61 72 73 20 69 6e 20 28 2d  en appears in (-
19d0: 76 65 20 2d 3e 20 64 65 6c 65 74 65 29 20 2a 2f  ve -> delete) */
19e0: 0a 20 20 69 6e 74 20 69 50 6f 73 2c 20 20 20 20  .  int iPos,    
19f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1a00: 20 20 20 2f 2a 20 50 6f 73 69 74 69 6f 6e 20 6f     /* Position o
1a10: 66 20 74 6f 6b 65 6e 20 77 69 74 68 69 6e 20 63  f token within c
1a20: 6f 6c 75 6d 6e 20 2a 2f 0a 20 20 63 68 61 72 20  olumn */.  char 
1a30: 62 42 79 74 65 2c 20 20 20 20 20 20 20 20 20 20  bByte,          
1a40: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 46 69             /* Fi
1a50: 72 73 74 20 62 79 74 65 20 6f 66 20 74 6f 6b 65  rst byte of toke
1a60: 6e 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61  n */.  const cha
1a70: 72 20 2a 70 54 6f 6b 65 6e 2c 20 69 6e 74 20 6e  r *pToken, int n
1a80: 54 6f 6b 65 6e 20 20 2f 2a 20 54 6f 6b 65 6e 20  Token  /* Token 
1a90: 74 6f 20 61 64 64 20 6f 72 20 72 65 6d 6f 76 65  to add or remove
1aa0: 20 74 6f 20 6f 72 20 66 72 6f 6d 20 69 6e 64 65   to or from inde
1ab0: 78 20 2a 2f 0a 29 7b 0a 20 20 75 6e 73 69 67 6e  x */.){.  unsign
1ac0: 65 64 20 69 6e 74 20 69 48 61 73 68 3b 0a 20 20  ed int iHash;.  
1ad0: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70  Fts5HashEntry *p
1ae0: 3b 0a 20 20 75 38 20 2a 70 50 74 72 3b 0a 20 20  ;.  u8 *pPtr;.  
1af0: 69 6e 74 20 6e 49 6e 63 72 20 3d 20 30 3b 20 20  int nIncr = 0;  
1b00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1b10: 2f 2a 20 41 6d 6f 75 6e 74 20 74 6f 20 69 6e 63  /* Amount to inc
1b20: 72 65 6d 65 6e 74 20 28 2a 70 48 61 73 68 2d 3e  rement (*pHash->
1b30: 70 6e 42 79 74 65 29 20 62 79 20 2a 2f 0a 20 20  pnByte) by */.  
1b40: 69 6e 74 20 62 4e 65 77 3b 20 20 20 20 20 20 20  int bNew;       
1b50: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1b60: 2f 2a 20 49 66 20 6e 6f 6e 2d 64 65 6c 65 74 65  /* If non-delete
1b70: 20 65 6e 74 72 79 20 73 68 6f 75 6c 64 20 62 65   entry should be
1b80: 20 77 72 69 74 74 65 6e 20 2a 2f 0a 20 20 0a 20   written */.  . 
1b90: 20 62 4e 65 77 20 3d 20 28 70 48 61 73 68 2d 3e   bNew = (pHash->
1ba0: 65 44 65 74 61 69 6c 3d 3d 46 54 53 35 5f 44 45  eDetail==FTS5_DE
1bb0: 54 41 49 4c 5f 46 55 4c 4c 29 3b 0a 0a 20 20 2f  TAIL_FULL);..  /
1bc0: 2a 20 41 74 74 65 6d 70 74 20 74 6f 20 6c 6f 63  * Attempt to loc
1bd0: 61 74 65 20 61 6e 20 65 78 69 73 74 69 6e 67 20  ate an existing 
1be0: 68 61 73 68 20 65 6e 74 72 79 20 2a 2f 0a 20 20  hash entry */.  
1bf0: 69 48 61 73 68 20 3d 20 66 74 73 35 48 61 73 68  iHash = fts5Hash
1c00: 4b 65 79 32 28 70 48 61 73 68 2d 3e 6e 53 6c 6f  Key2(pHash->nSlo
1c10: 74 2c 20 28 75 38 29 62 42 79 74 65 2c 20 28 63  t, (u8)bByte, (c
1c20: 6f 6e 73 74 20 75 38 2a 29 70 54 6f 6b 65 6e 2c  onst u8*)pToken,
1c30: 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 66 6f 72 28   nToken);.  for(
1c40: 70 3d 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69  p=pHash->aSlot[i
1c50: 48 61 73 68 5d 3b 20 70 3b 20 70 3d 70 2d 3e 70  Hash]; p; p=p->p
1c60: 48 61 73 68 4e 65 78 74 29 7b 0a 20 20 20 20 63  HashNext){.    c
1c70: 68 61 72 20 2a 7a 4b 65 79 20 3d 20 66 74 73 35  har *zKey = fts5
1c80: 45 6e 74 72 79 4b 65 79 28 70 29 3b 0a 20 20 20  EntryKey(p);.   
1c90: 20 69 66 28 20 7a 4b 65 79 5b 30 5d 3d 3d 62 42   if( zKey[0]==bB
1ca0: 79 74 65 20 0a 20 20 20 20 20 26 26 20 70 2d 3e  yte .     && p->
1cb0: 6e 4b 65 79 3d 3d 6e 54 6f 6b 65 6e 0a 20 20 20  nKey==nToken.   
1cc0: 20 20 26 26 20 6d 65 6d 63 6d 70 28 26 7a 4b 65    && memcmp(&zKe
1cd0: 79 5b 31 5d 2c 20 70 54 6f 6b 65 6e 2c 20 6e 54  y[1], pToken, nT
1ce0: 6f 6b 65 6e 29 3d 3d 30 20 0a 20 20 20 20 29 7b  oken)==0 .    ){
1cf0: 0a 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20  .      break;.  
1d00: 20 20 7d 0a 20 20 7d 0a 0a 20 20 2f 2a 20 49 66    }.  }..  /* If
1d10: 20 61 6e 20 65 78 69 73 74 69 6e 67 20 68 61 73   an existing has
1d20: 68 20 65 6e 74 72 79 20 63 61 6e 6e 6f 74 20 62  h entry cannot b
1d30: 65 20 66 6f 75 6e 64 2c 20 63 72 65 61 74 65 20  e found, create 
1d40: 61 20 6e 65 77 20 6f 6e 65 2e 20 2a 2f 0a 20 20  a new one. */.  
1d50: 69 66 28 20 70 3d 3d 30 20 29 7b 0a 20 20 20 20  if( p==0 ){.    
1d60: 2f 2a 20 46 69 67 75 72 65 20 6f 75 74 20 68 6f  /* Figure out ho
1d70: 77 20 6d 75 63 68 20 73 70 61 63 65 20 74 6f 20  w much space to 
1d80: 61 6c 6c 6f 63 61 74 65 20 2a 2f 0a 20 20 20 20  allocate */.    
1d90: 63 68 61 72 20 2a 7a 4b 65 79 3b 0a 20 20 20 20  char *zKey;.    
1da0: 73 71 6c 69 74 65 33 5f 69 6e 74 36 34 20 6e 42  sqlite3_int64 nB
1db0: 79 74 65 20 3d 20 73 69 7a 65 6f 66 28 46 74 73  yte = sizeof(Fts
1dc0: 35 48 61 73 68 45 6e 74 72 79 29 20 2b 20 28 6e  5HashEntry) + (n
1dd0: 54 6f 6b 65 6e 2b 31 29 20 2b 20 31 20 2b 20 36  Token+1) + 1 + 6
1de0: 34 3b 0a 20 20 20 20 69 66 28 20 6e 42 79 74 65  4;.    if( nByte
1df0: 3c 31 32 38 20 29 20 6e 42 79 74 65 20 3d 20 31  <128 ) nByte = 1
1e00: 32 38 3b 0a 0a 20 20 20 20 2f 2a 20 47 72 6f 77  28;..    /* Grow
1e10: 20 74 68 65 20 46 74 73 35 48 61 73 68 2e 61 53   the Fts5Hash.aS
1e20: 6c 6f 74 5b 5d 20 61 72 72 61 79 20 69 66 20 6e  lot[] array if n
1e30: 65 63 65 73 73 61 72 79 2e 20 2a 2f 0a 20 20 20  ecessary. */.   
1e40: 20 69 66 28 20 28 70 48 61 73 68 2d 3e 6e 45 6e   if( (pHash->nEn
1e50: 74 72 79 2a 32 29 3e 3d 70 48 61 73 68 2d 3e 6e  try*2)>=pHash->n
1e60: 53 6c 6f 74 20 29 7b 0a 20 20 20 20 20 20 69 6e  Slot ){.      in
1e70: 74 20 72 63 20 3d 20 66 74 73 35 48 61 73 68 52  t rc = fts5HashR
1e80: 65 73 69 7a 65 28 70 48 61 73 68 29 3b 0a 20 20  esize(pHash);.  
1e90: 20 20 20 20 69 66 28 20 72 63 21 3d 53 51 4c 49      if( rc!=SQLI
1ea0: 54 45 5f 4f 4b 20 29 20 72 65 74 75 72 6e 20 72  TE_OK ) return r
1eb0: 63 3b 0a 20 20 20 20 20 20 69 48 61 73 68 20 3d  c;.      iHash =
1ec0: 20 66 74 73 35 48 61 73 68 4b 65 79 32 28 70 48   fts5HashKey2(pH
1ed0: 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20 28 75 38 29  ash->nSlot, (u8)
1ee0: 62 42 79 74 65 2c 20 28 63 6f 6e 73 74 20 75 38  bByte, (const u8
1ef0: 2a 29 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b 65 6e  *)pToken, nToken
1f00: 29 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f 2a  );.    }..    /*
1f10: 20 41 6c 6c 6f 63 61 74 65 20 6e 65 77 20 46 74   Allocate new Ft
1f20: 73 35 48 61 73 68 45 6e 74 72 79 20 61 6e 64 20  s5HashEntry and 
1f30: 61 64 64 20 69 74 20 74 6f 20 74 68 65 20 68 61  add it to the ha
1f40: 73 68 20 74 61 62 6c 65 2e 20 2a 2f 0a 20 20 20  sh table. */.   
1f50: 20 70 20 3d 20 28 46 74 73 35 48 61 73 68 45 6e   p = (Fts5HashEn
1f60: 74 72 79 2a 29 73 71 6c 69 74 65 33 5f 6d 61 6c  try*)sqlite3_mal
1f70: 6c 6f 63 36 34 28 6e 42 79 74 65 29 3b 0a 20 20  loc64(nByte);.  
1f80: 20 20 69 66 28 20 21 70 20 29 20 72 65 74 75 72    if( !p ) retur
1f90: 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a  n SQLITE_NOMEM;.
1fa0: 20 20 20 20 6d 65 6d 73 65 74 28 70 2c 20 30 2c      memset(p, 0,
1fb0: 20 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68   sizeof(Fts5Hash
1fc0: 45 6e 74 72 79 29 29 3b 0a 20 20 20 20 70 2d 3e  Entry));.    p->
1fd0: 6e 41 6c 6c 6f 63 20 3d 20 6e 42 79 74 65 3b 0a  nAlloc = nByte;.
1fe0: 20 20 20 20 7a 4b 65 79 20 3d 20 66 74 73 35 45      zKey = fts5E
1ff0: 6e 74 72 79 4b 65 79 28 70 29 3b 0a 20 20 20 20  ntryKey(p);.    
2000: 7a 4b 65 79 5b 30 5d 20 3d 20 62 42 79 74 65 3b  zKey[0] = bByte;
2010: 0a 20 20 20 20 6d 65 6d 63 70 79 28 26 7a 4b 65  .    memcpy(&zKe
2020: 79 5b 31 5d 2c 20 70 54 6f 6b 65 6e 2c 20 6e 54  y[1], pToken, nT
2030: 6f 6b 65 6e 29 3b 0a 20 20 20 20 61 73 73 65 72  oken);.    asser
2040: 74 28 20 69 48 61 73 68 3d 3d 66 74 73 35 48 61  t( iHash==fts5Ha
2050: 73 68 4b 65 79 28 70 48 61 73 68 2d 3e 6e 53 6c  shKey(pHash->nSl
2060: 6f 74 2c 20 28 75 38 2a 29 7a 4b 65 79 2c 20 6e  ot, (u8*)zKey, n
2070: 54 6f 6b 65 6e 2b 31 29 20 29 3b 0a 20 20 20 20  Token+1) );.    
2080: 70 2d 3e 6e 4b 65 79 20 3d 20 6e 54 6f 6b 65 6e  p->nKey = nToken
2090: 3b 0a 20 20 20 20 7a 4b 65 79 5b 6e 54 6f 6b 65  ;.    zKey[nToke
20a0: 6e 2b 31 5d 20 3d 20 27 5c 30 27 3b 0a 20 20 20  n+1] = '\0';.   
20b0: 20 70 2d 3e 6e 44 61 74 61 20 3d 20 6e 54 6f 6b   p->nData = nTok
20c0: 65 6e 2b 31 20 2b 20 31 20 2b 20 73 69 7a 65 6f  en+1 + 1 + sizeo
20d0: 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 29  f(Fts5HashEntry)
20e0: 3b 0a 20 20 20 20 70 2d 3e 70 48 61 73 68 4e 65  ;.    p->pHashNe
20f0: 78 74 20 3d 20 70 48 61 73 68 2d 3e 61 53 6c 6f  xt = pHash->aSlo
2100: 74 5b 69 48 61 73 68 5d 3b 0a 20 20 20 20 70 48  t[iHash];.    pH
2110: 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68  ash->aSlot[iHash
2120: 5d 20 3d 20 70 3b 0a 20 20 20 20 70 48 61 73 68  ] = p;.    pHash
2130: 2d 3e 6e 45 6e 74 72 79 2b 2b 3b 0a 0a 20 20 20  ->nEntry++;..   
2140: 20 2f 2a 20 41 64 64 20 74 68 65 20 66 69 72 73   /* Add the firs
2150: 74 20 72 6f 77 69 64 20 66 69 65 6c 64 20 74 6f  t rowid field to
2160: 20 74 68 65 20 68 61 73 68 2d 65 6e 74 72 79 20   the hash-entry 
2170: 2a 2f 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20  */.    p->nData 
2180: 2b 3d 20 73 71 6c 69 74 65 33 46 74 73 35 50 75  += sqlite3Fts5Pu
2190: 74 56 61 72 69 6e 74 28 26 28 28 75 38 2a 29 70  tVarint(&((u8*)p
21a0: 29 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20 69 52 6f  )[p->nData], iRo
21b0: 77 69 64 29 3b 0a 20 20 20 20 70 2d 3e 69 52 6f  wid);.    p->iRo
21c0: 77 69 64 20 3d 20 69 52 6f 77 69 64 3b 0a 0a 20  wid = iRowid;.. 
21d0: 20 20 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74     p->iSzPoslist
21e0: 20 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20 20 20   = p->nData;.   
21f0: 20 69 66 28 20 70 48 61 73 68 2d 3e 65 44 65 74   if( pHash->eDet
2200: 61 69 6c 21 3d 46 54 53 35 5f 44 45 54 41 49 4c  ail!=FTS5_DETAIL
2210: 5f 4e 4f 4e 45 20 29 7b 0a 20 20 20 20 20 20 70  _NONE ){.      p
2220: 2d 3e 6e 44 61 74 61 20 2b 3d 20 31 3b 0a 20 20  ->nData += 1;.  
2230: 20 20 20 20 70 2d 3e 69 43 6f 6c 20 3d 20 28 70      p->iCol = (p
2240: 48 61 73 68 2d 3e 65 44 65 74 61 69 6c 3d 3d 46  Hash->eDetail==F
2250: 54 53 35 5f 44 45 54 41 49 4c 5f 46 55 4c 4c 20  TS5_DETAIL_FULL 
2260: 3f 20 30 20 3a 20 2d 31 29 3b 0a 20 20 20 20 7d  ? 0 : -1);.    }
2270: 0a 0a 20 20 20 20 6e 49 6e 63 72 20 2b 3d 20 70  ..    nIncr += p
2280: 2d 3e 6e 44 61 74 61 3b 0a 20 20 7d 65 6c 73 65  ->nData;.  }else
2290: 7b 0a 0a 20 20 20 20 2f 2a 20 41 70 70 65 6e 64  {..    /* Append
22a0: 69 6e 67 20 74 6f 20 61 6e 20 65 78 69 73 74 69  ing to an existi
22b0: 6e 67 20 68 61 73 68 2d 65 6e 74 72 79 2e 20 43  ng hash-entry. C
22c0: 68 65 63 6b 20 74 68 61 74 20 74 68 65 72 65 20  heck that there 
22d0: 69 73 20 65 6e 6f 75 67 68 20 0a 20 20 20 20 2a  is enough .    *
22e0: 2a 20 73 70 61 63 65 20 74 6f 20 61 70 70 65 6e  * space to appen
22f0: 64 20 74 68 65 20 6c 61 72 67 65 73 74 20 70 6f  d the largest po
2300: 73 73 69 62 6c 65 20 6e 65 77 20 65 6e 74 72 79  ssible new entry
2310: 2e 20 57 6f 72 73 74 20 63 61 73 65 20 73 63 65  . Worst case sce
2320: 6e 61 72 69 6f 20 0a 20 20 20 20 2a 2a 20 69 73  nario .    ** is
2330: 3a 0a 20 20 20 20 2a 2a 0a 20 20 20 20 2a 2a 20  :.    **.    ** 
2340: 20 20 20 20 2b 20 39 20 62 79 74 65 73 20 66 6f      + 9 bytes fo
2350: 72 20 61 20 6e 65 77 20 72 6f 77 69 64 2c 0a 20  r a new rowid,. 
2360: 20 20 20 2a 2a 20 20 20 20 20 2b 20 34 20 62 79     **     + 4 by
2370: 74 65 20 72 65 73 65 72 76 65 64 20 66 6f 72 20  te reserved for 
2380: 74 68 65 20 22 70 6f 73 6c 69 73 74 20 73 69 7a  the "poslist siz
2390: 65 22 20 76 61 72 69 6e 74 2e 0a 20 20 20 20 2a  e" varint..    *
23a0: 2a 20 20 20 20 20 2b 20 31 20 62 79 74 65 20 66  *     + 1 byte f
23b0: 6f 72 20 61 20 22 6e 65 77 20 63 6f 6c 75 6d 6e  or a "new column
23c0: 22 20 62 79 74 65 2c 0a 20 20 20 20 2a 2a 20 20  " byte,.    **  
23d0: 20 20 20 2b 20 33 20 62 79 74 65 73 20 66 6f 72     + 3 bytes for
23e0: 20 61 20 6e 65 77 20 63 6f 6c 75 6d 6e 20 6e 75   a new column nu
23f0: 6d 62 65 72 20 28 31 36 2d 62 69 74 20 6d 61 78  mber (16-bit max
2400: 29 20 61 73 20 61 20 76 61 72 69 6e 74 2c 0a 20  ) as a varint,. 
2410: 20 20 20 2a 2a 20 20 20 20 20 2b 20 35 20 62 79     **     + 5 by
2420: 74 65 73 20 66 6f 72 20 74 68 65 20 6e 65 77 20  tes for the new 
2430: 70 6f 73 69 74 69 6f 6e 20 6f 66 66 73 65 74 20  position offset 
2440: 28 33 32 2d 62 69 74 20 6d 61 78 29 2e 0a 20 20  (32-bit max)..  
2450: 20 20 2a 2f 0a 20 20 20 20 69 66 28 20 28 70 2d    */.    if( (p-
2460: 3e 6e 41 6c 6c 6f 63 20 2d 20 70 2d 3e 6e 44 61  >nAlloc - p->nDa
2470: 74 61 29 20 3c 20 28 39 20 2b 20 34 20 2b 20 31  ta) < (9 + 4 + 1
2480: 20 2b 20 33 20 2b 20 35 29 20 29 7b 0a 20 20 20   + 3 + 5) ){.   
2490: 20 20 20 73 71 6c 69 74 65 33 5f 69 6e 74 36 34     sqlite3_int64
24a0: 20 6e 4e 65 77 20 3d 20 70 2d 3e 6e 41 6c 6c 6f   nNew = p->nAllo
24b0: 63 20 2a 20 32 3b 0a 20 20 20 20 20 20 46 74 73  c * 2;.      Fts
24c0: 35 48 61 73 68 45 6e 74 72 79 20 2a 70 4e 65 77  5HashEntry *pNew
24d0: 3b 0a 20 20 20 20 20 20 46 74 73 35 48 61 73 68  ;.      Fts5Hash
24e0: 45 6e 74 72 79 20 2a 2a 70 70 3b 0a 20 20 20 20  Entry **pp;.    
24f0: 20 20 70 4e 65 77 20 3d 20 28 46 74 73 35 48 61    pNew = (Fts5Ha
2500: 73 68 45 6e 74 72 79 2a 29 73 71 6c 69 74 65 33  shEntry*)sqlite3
2510: 5f 72 65 61 6c 6c 6f 63 36 34 28 70 2c 20 6e 4e  _realloc64(p, nN
2520: 65 77 29 3b 0a 20 20 20 20 20 20 69 66 28 20 70  ew);.      if( p
2530: 4e 65 77 3d 3d 30 20 29 20 72 65 74 75 72 6e 20  New==0 ) return 
2540: 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20  SQLITE_NOMEM;.  
2550: 20 20 20 20 70 4e 65 77 2d 3e 6e 41 6c 6c 6f 63      pNew->nAlloc
2560: 20 3d 20 28 69 6e 74 29 6e 4e 65 77 3b 0a 20 20   = (int)nNew;.  
2570: 20 20 20 20 66 6f 72 28 70 70 3d 26 70 48 61 73      for(pp=&pHas
2580: 68 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d 3b  h->aSlot[iHash];
2590: 20 2a 70 70 21 3d 70 3b 20 70 70 3d 26 28 2a 70   *pp!=p; pp=&(*p
25a0: 70 29 2d 3e 70 48 61 73 68 4e 65 78 74 29 3b 0a  p)->pHashNext);.
25b0: 20 20 20 20 20 20 2a 70 70 20 3d 20 70 4e 65 77        *pp = pNew
25c0: 3b 0a 20 20 20 20 20 20 70 20 3d 20 70 4e 65 77  ;.      p = pNew
25d0: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 6e 49 6e 63  ;.    }.    nInc
25e0: 72 20 2d 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20  r -= p->nData;. 
25f0: 20 7d 0a 20 20 61 73 73 65 72 74 28 20 28 70 2d   }.  assert( (p-
2600: 3e 6e 41 6c 6c 6f 63 20 2d 20 70 2d 3e 6e 44 61  >nAlloc - p->nDa
2610: 74 61 29 20 3e 3d 20 28 39 20 2b 20 34 20 2b 20  ta) >= (9 + 4 + 
2620: 31 20 2b 20 33 20 2b 20 35 29 20 29 3b 0a 0a 20  1 + 3 + 5) );.. 
2630: 20 70 50 74 72 20 3d 20 28 75 38 2a 29 70 3b 0a   pPtr = (u8*)p;.
2640: 0a 20 20 2f 2a 20 49 66 20 74 68 69 73 20 69 73  .  /* If this is
2650: 20 61 20 6e 65 77 20 72 6f 77 69 64 2c 20 61 70   a new rowid, ap
2660: 70 65 6e 64 20 74 68 65 20 34 2d 62 79 74 65 20  pend the 4-byte 
2670: 73 69 7a 65 20 66 69 65 6c 64 20 66 6f 72 20 74  size field for t
2680: 68 65 20 70 72 65 76 69 6f 75 73 0a 20 20 2a 2a  he previous.  **
2690: 20 65 6e 74 72 79 2c 20 61 6e 64 20 74 68 65 20   entry, and the 
26a0: 6e 65 77 20 72 6f 77 69 64 20 66 6f 72 20 74 68  new rowid for th
26b0: 69 73 20 65 6e 74 72 79 2e 20 20 2a 2f 0a 20 20  is entry.  */.  
26c0: 69 66 28 20 69 52 6f 77 69 64 21 3d 70 2d 3e 69  if( iRowid!=p->i
26d0: 52 6f 77 69 64 20 29 7b 0a 20 20 20 20 66 74 73  Rowid ){.    fts
26e0: 35 48 61 73 68 41 64 64 50 6f 73 6c 69 73 74 53  5HashAddPoslistS
26f0: 69 7a 65 28 70 48 61 73 68 2c 20 70 29 3b 0a 20  ize(pHash, p);. 
2700: 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73     p->nData += s
2710: 71 6c 69 74 65 33 46 74 73 35 50 75 74 56 61 72  qlite3Fts5PutVar
2720: 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61  int(&pPtr[p->nDa
2730: 74 61 5d 2c 20 69 52 6f 77 69 64 20 2d 20 70 2d  ta], iRowid - p-
2740: 3e 69 52 6f 77 69 64 29 3b 0a 20 20 20 20 70 2d  >iRowid);.    p-
2750: 3e 69 52 6f 77 69 64 20 3d 20 69 52 6f 77 69 64  >iRowid = iRowid
2760: 3b 0a 20 20 20 20 62 4e 65 77 20 3d 20 31 3b 0a  ;.    bNew = 1;.
2770: 20 20 20 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73      p->iSzPoslis
2780: 74 20 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20 20  t = p->nData;.  
2790: 20 20 69 66 28 20 70 48 61 73 68 2d 3e 65 44 65    if( pHash->eDe
27a0: 74 61 69 6c 21 3d 46 54 53 35 5f 44 45 54 41 49  tail!=FTS5_DETAI
27b0: 4c 5f 4e 4f 4e 45 20 29 7b 0a 20 20 20 20 20 20  L_NONE ){.      
27c0: 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 31 3b 0a 20  p->nData += 1;. 
27d0: 20 20 20 20 20 70 2d 3e 69 43 6f 6c 20 3d 20 28       p->iCol = (
27e0: 70 48 61 73 68 2d 3e 65 44 65 74 61 69 6c 3d 3d  pHash->eDetail==
27f0: 46 54 53 35 5f 44 45 54 41 49 4c 5f 46 55 4c 4c  FTS5_DETAIL_FULL
2800: 20 3f 20 30 20 3a 20 2d 31 29 3b 0a 20 20 20 20   ? 0 : -1);.    
2810: 20 20 70 2d 3e 69 50 6f 73 20 3d 20 30 3b 0a 20    p->iPos = 0;. 
2820: 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 69 66 28 20     }.  }..  if( 
2830: 69 43 6f 6c 3e 3d 30 20 29 7b 0a 20 20 20 20 69  iCol>=0 ){.    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 4e  l==FTS5_DETAIL_N
2860: 4f 4e 45 20 29 7b 0a 20 20 20 20 20 20 70 2d 3e  ONE ){.      p->
2870: 62 43 6f 6e 74 65 6e 74 20 3d 20 31 3b 0a 20 20  bContent = 1;.  
2880: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 2f    }else{.      /
2890: 2a 20 41 70 70 65 6e 64 20 61 20 6e 65 77 20 63  * Append a new c
28a0: 6f 6c 75 6d 6e 20 76 61 6c 75 65 2c 20 69 66 20  olumn value, if 
28b0: 6e 65 63 65 73 73 61 72 79 20 2a 2f 0a 20 20 20  necessary */.   
28c0: 20 20 20 61 73 73 65 72 74 28 20 69 43 6f 6c 3e     assert( iCol>
28d0: 3d 70 2d 3e 69 43 6f 6c 20 29 3b 0a 20 20 20 20  =p->iCol );.    
28e0: 20 20 69 66 28 20 69 43 6f 6c 21 3d 70 2d 3e 69    if( iCol!=p->i
28f0: 43 6f 6c 20 29 7b 0a 20 20 20 20 20 20 20 20 69  Col ){.        i
2900: 66 28 20 70 48 61 73 68 2d 3e 65 44 65 74 61 69  f( pHash->eDetai
2910: 6c 3d 3d 46 54 53 35 5f 44 45 54 41 49 4c 5f 46  l==FTS5_DETAIL_F
2920: 55 4c 4c 20 29 7b 0a 20 20 20 20 20 20 20 20 20  ULL ){.         
2930: 20 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61 2b 2b   pPtr[p->nData++
2940: 5d 20 3d 20 30 78 30 31 3b 0a 20 20 20 20 20 20  ] = 0x01;.      
2950: 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20      p->nData += 
2960: 73 71 6c 69 74 65 33 46 74 73 35 50 75 74 56 61  sqlite3Fts5PutVa
2970: 72 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44  rint(&pPtr[p->nD
2980: 61 74 61 5d 2c 20 69 43 6f 6c 29 3b 0a 20 20 20  ata], iCol);.   
2990: 20 20 20 20 20 20 20 70 2d 3e 69 43 6f 6c 20 3d         p->iCol =
29a0: 20 28 69 31 36 29 69 43 6f 6c 3b 0a 20 20 20 20   (i16)iCol;.    
29b0: 20 20 20 20 20 20 70 2d 3e 69 50 6f 73 20 3d 20        p->iPos = 
29c0: 30 3b 0a 20 20 20 20 20 20 20 20 7d 65 6c 73 65  0;.        }else
29d0: 7b 0a 20 20 20 20 20 20 20 20 20 20 62 4e 65 77  {.          bNew
29e0: 20 3d 20 31 3b 0a 20 20 20 20 20 20 20 20 20 20   = 1;.          
29f0: 70 2d 3e 69 43 6f 6c 20 3d 20 28 69 31 36 29 28  p->iCol = (i16)(
2a00: 69 50 6f 73 20 3d 20 69 43 6f 6c 29 3b 0a 20 20  iPos = iCol);.  
2a10: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 7d 0a        }.      }.
2a20: 0a 20 20 20 20 20 20 2f 2a 20 41 70 70 65 6e 64  .      /* Append
2a30: 20 74 68 65 20 6e 65 77 20 70 6f 73 69 74 69 6f   the new positio
2a40: 6e 20 6f 66 66 73 65 74 2c 20 69 66 20 6e 65 63  n offset, if nec
2a50: 65 73 73 61 72 79 20 2a 2f 0a 20 20 20 20 20 20  essary */.      
2a60: 69 66 28 20 62 4e 65 77 20 29 7b 0a 20 20 20 20  if( bNew ){.    
2a70: 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20      p->nData += 
2a80: 73 71 6c 69 74 65 33 46 74 73 35 50 75 74 56 61  sqlite3Fts5PutVa
2a90: 72 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44  rint(&pPtr[p->nD
2aa0: 61 74 61 5d 2c 20 69 50 6f 73 20 2d 20 70 2d 3e  ata], iPos - p->
2ab0: 69 50 6f 73 20 2b 20 32 29 3b 0a 20 20 20 20 20  iPos + 2);.     
2ac0: 20 20 20 70 2d 3e 69 50 6f 73 20 3d 20 69 50 6f     p->iPos = iPo
2ad0: 73 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 7d  s;.      }.    }
2ae0: 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2f 2a  .  }else{.    /*
2af0: 20 54 68 69 73 20 69 73 20 61 20 64 65 6c 65 74   This is a delet
2b00: 65 2e 20 53 65 74 20 74 68 65 20 64 65 6c 65 74  e. Set the delet
2b10: 65 20 66 6c 61 67 2e 20 2a 2f 0a 20 20 20 20 70  e flag. */.    p
2b20: 2d 3e 62 44 65 6c 20 3d 20 31 3b 0a 20 20 7d 0a  ->bDel = 1;.  }.
2b30: 0a 20 20 6e 49 6e 63 72 20 2b 3d 20 70 2d 3e 6e  .  nIncr += p->n
2b40: 44 61 74 61 3b 0a 20 20 2a 70 48 61 73 68 2d 3e  Data;.  *pHash->
2b50: 70 6e 42 79 74 65 20 2b 3d 20 6e 49 6e 63 72 3b  pnByte += nIncr;
2b60: 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45  .  return SQLITE
2b70: 5f 4f 4b 3b 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a 20 41  _OK;.}.../*.** A
2b80: 72 67 75 6d 65 6e 74 73 20 70 4c 65 66 74 20 61  rguments pLeft a
2b90: 6e 64 20 70 52 69 67 68 74 20 70 6f 69 6e 74 20  nd pRight point 
2ba0: 74 6f 20 6c 69 6e 6b 65 64 2d 6c 69 73 74 73 20  to linked-lists 
2bb0: 6f 66 20 68 61 73 68 2d 65 6e 74 72 79 20 6f 62  of hash-entry ob
2bc0: 6a 65 63 74 73 2c 0a 2a 2a 20 65 61 63 68 20 73  jects,.** each s
2bd0: 6f 72 74 65 64 20 69 6e 20 6b 65 79 20 6f 72 64  orted in key ord
2be0: 65 72 2e 20 54 68 69 73 20 66 75 6e 63 74 69 6f  er. This functio
2bf0: 6e 20 6d 65 72 67 65 73 20 74 68 65 20 74 77 6f  n merges the two
2c00: 20 6c 69 73 74 73 20 69 6e 74 6f 20 61 0a 2a 2a   lists into a.**
2c10: 20 73 69 6e 67 6c 65 20 6c 69 73 74 20 61 6e 64   single list and
2c20: 20 72 65 74 75 72 6e 73 20 61 20 70 6f 69 6e 74   returns a point
2c30: 65 72 20 74 6f 20 69 74 73 20 66 69 72 73 74 20  er to its first 
2c40: 65 6c 65 6d 65 6e 74 2e 0a 2a 2f 0a 73 74 61 74  element..*/.stat
2c50: 69 63 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  ic Fts5HashEntry
2c60: 20 2a 66 74 73 35 48 61 73 68 45 6e 74 72 79 4d   *fts5HashEntryM
2c70: 65 72 67 65 28 0a 20 20 46 74 73 35 48 61 73 68  erge(.  Fts5Hash
2c80: 45 6e 74 72 79 20 2a 70 4c 65 66 74 2c 0a 20 20  Entry *pLeft,.  
2c90: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70  Fts5HashEntry *p
2ca0: 52 69 67 68 74 0a 29 7b 0a 20 20 46 74 73 35 48  Right.){.  Fts5H
2cb0: 61 73 68 45 6e 74 72 79 20 2a 70 31 20 3d 20 70  ashEntry *p1 = p
2cc0: 4c 65 66 74 3b 0a 20 20 46 74 73 35 48 61 73 68  Left;.  Fts5Hash
2cd0: 45 6e 74 72 79 20 2a 70 32 20 3d 20 70 52 69 67  Entry *p2 = pRig
2ce0: 68 74 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e  ht;.  Fts5HashEn
2cf0: 74 72 79 20 2a 70 52 65 74 20 3d 20 30 3b 0a 20  try *pRet = 0;. 
2d00: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
2d10: 2a 70 70 4f 75 74 20 3d 20 26 70 52 65 74 3b 0a  *ppOut = &pRet;.
2d20: 0a 20 20 77 68 69 6c 65 28 20 70 31 20 7c 7c 20  .  while( p1 || 
2d30: 70 32 20 29 7b 0a 20 20 20 20 69 66 28 20 70 31  p2 ){.    if( p1
2d40: 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 2a 70 70  ==0 ){.      *pp
2d50: 4f 75 74 20 3d 20 70 32 3b 0a 20 20 20 20 20 20  Out = p2;.      
2d60: 70 32 20 3d 20 30 3b 0a 20 20 20 20 7d 65 6c 73  p2 = 0;.    }els
2d70: 65 20 69 66 28 20 70 32 3d 3d 30 20 29 7b 0a 20  e if( p2==0 ){. 
2d80: 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 70 31       *ppOut = p1
2d90: 3b 0a 20 20 20 20 20 20 70 31 20 3d 20 30 3b 0a  ;.      p1 = 0;.
2da0: 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20      }else{.     
2db0: 20 69 6e 74 20 69 20 3d 20 30 3b 0a 20 20 20 20   int i = 0;.    
2dc0: 20 20 63 68 61 72 20 2a 7a 4b 65 79 31 20 3d 20    char *zKey1 = 
2dd0: 66 74 73 35 45 6e 74 72 79 4b 65 79 28 70 31 29  fts5EntryKey(p1)
2de0: 3b 0a 20 20 20 20 20 20 63 68 61 72 20 2a 7a 4b  ;.      char *zK
2df0: 65 79 32 20 3d 20 66 74 73 35 45 6e 74 72 79 4b  ey2 = fts5EntryK
2e00: 65 79 28 70 32 29 3b 0a 20 20 20 20 20 20 77 68  ey(p2);.      wh
2e10: 69 6c 65 28 20 7a 4b 65 79 31 5b 69 5d 3d 3d 7a  ile( zKey1[i]==z
2e20: 4b 65 79 32 5b 69 5d 20 29 20 69 2b 2b 3b 0a 0a  Key2[i] ) i++;..
2e30: 20 20 20 20 20 20 69 66 28 20 28 28 75 38 29 7a        if( ((u8)z
2e40: 4b 65 79 31 5b 69 5d 29 3e 28 28 75 38 29 7a 4b  Key1[i])>((u8)zK
2e50: 65 79 32 5b 69 5d 29 20 29 7b 0a 20 20 20 20 20  ey2[i]) ){.     
2e60: 20 20 20 2f 2a 20 70 32 20 69 73 20 73 6d 61 6c     /* p2 is smal
2e70: 6c 65 72 20 2a 2f 0a 20 20 20 20 20 20 20 20 2a  ler */.        *
2e80: 70 70 4f 75 74 20 3d 20 70 32 3b 0a 20 20 20 20  ppOut = p2;.    
2e90: 20 20 20 20 70 70 4f 75 74 20 3d 20 26 70 32 2d      ppOut = &p2-
2ea0: 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 20 20 20 20  >pScanNext;.    
2eb0: 20 20 20 20 70 32 20 3d 20 70 32 2d 3e 70 53 63      p2 = p2->pSc
2ec0: 61 6e 4e 65 78 74 3b 0a 20 20 20 20 20 20 7d 65  anNext;.      }e
2ed0: 6c 73 65 7b 0a 20 20 20 20 20 20 20 20 2f 2a 20  lse{.        /* 
2ee0: 70 31 20 69 73 20 73 6d 61 6c 6c 65 72 20 2a 2f  p1 is smaller */
2ef0: 0a 20 20 20 20 20 20 20 20 2a 70 70 4f 75 74 20  .        *ppOut 
2f00: 3d 20 70 31 3b 0a 20 20 20 20 20 20 20 20 70 70  = p1;.        pp
2f10: 4f 75 74 20 3d 20 26 70 31 2d 3e 70 53 63 61 6e  Out = &p1->pScan
2f20: 4e 65 78 74 3b 0a 20 20 20 20 20 20 20 20 70 31  Next;.        p1
2f30: 20 3d 20 70 31 2d 3e 70 53 63 61 6e 4e 65 78 74   = p1->pScanNext
2f40: 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20  ;.      }.      
2f50: 2a 70 70 4f 75 74 20 3d 20 30 3b 0a 20 20 20 20  *ppOut = 0;.    
2f60: 7d 0a 20 20 7d 0a 0a 20 20 72 65 74 75 72 6e 20  }.  }..  return 
2f70: 70 52 65 74 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 45  pRet;.}../*.** E
2f80: 78 74 72 61 63 74 20 61 6c 6c 20 74 6f 6b 65 6e  xtract all token
2f90: 73 20 66 72 6f 6d 20 68 61 73 68 20 74 61 62 6c  s from hash tabl
2fa0: 65 20 69 48 61 73 68 20 61 6e 64 20 6c 69 6e 6b  e iHash and link
2fb0: 20 74 68 65 6d 20 69 6e 74 6f 20 61 20 6c 69 73   them into a lis
2fc0: 74 0a 2a 2a 20 69 6e 20 73 6f 72 74 65 64 20 6f  t.** in sorted o
2fd0: 72 64 65 72 2e 20 54 68 65 20 68 61 73 68 20 74  rder. The hash t
2fe0: 61 62 6c 65 20 69 73 20 63 6c 65 61 72 65 64 20  able is cleared 
2ff0: 62 65 66 6f 72 65 20 72 65 74 75 72 6e 69 6e 67  before returning
3000: 2e 20 49 74 20 69 73 0a 2a 2a 20 74 68 65 20 72  . It is.** the r
3010: 65 73 70 6f 6e 73 69 62 69 6c 69 74 79 20 6f 66  esponsibility of
3020: 20 74 68 65 20 63 61 6c 6c 65 72 20 74 6f 20 66   the caller to f
3030: 72 65 65 20 74 68 65 20 65 6c 65 6d 65 6e 74 73  ree the elements
3040: 20 6f 66 20 74 68 65 20 72 65 74 75 72 6e 65 64   of the returned
3050: 0a 2a 2a 20 6c 69 73 74 2e 0a 2a 2f 0a 73 74 61  .** list..*/.sta
3060: 74 69 63 20 69 6e 74 20 66 74 73 35 48 61 73 68  tic int fts5Hash
3070: 45 6e 74 72 79 53 6f 72 74 28 0a 20 20 46 74 73  EntrySort(.  Fts
3080: 35 48 61 73 68 20 2a 70 48 61 73 68 2c 20 0a 20  5Hash *pHash, . 
3090: 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 54 65   const char *pTe
30a0: 72 6d 2c 20 69 6e 74 20 6e 54 65 72 6d 2c 20 20  rm, int nTerm,  
30b0: 20 2f 2a 20 51 75 65 72 79 20 70 72 65 66 69 78   /* Query prefix
30c0: 2c 20 69 66 20 61 6e 79 20 2a 2f 0a 20 20 46 74  , if any */.  Ft
30d0: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 70 70  s5HashEntry **pp
30e0: 53 6f 72 74 65 64 0a 29 7b 0a 20 20 63 6f 6e 73  Sorted.){.  cons
30f0: 74 20 69 6e 74 20 6e 4d 65 72 67 65 53 6c 6f 74  t int nMergeSlot
3100: 20 3d 20 33 32 3b 0a 20 20 46 74 73 35 48 61 73   = 32;.  Fts5Has
3110: 68 45 6e 74 72 79 20 2a 2a 61 70 3b 0a 20 20 46  hEntry **ap;.  F
3120: 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 4c  ts5HashEntry *pL
3130: 69 73 74 3b 0a 20 20 69 6e 74 20 69 53 6c 6f 74  ist;.  int iSlot
3140: 3b 0a 20 20 69 6e 74 20 69 3b 0a 0a 20 20 2a 70  ;.  int i;..  *p
3150: 70 53 6f 72 74 65 64 20 3d 20 30 3b 0a 20 20 61  pSorted = 0;.  a
3160: 70 20 3d 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c  p = sqlite3_mall
3170: 6f 63 36 34 28 73 69 7a 65 6f 66 28 46 74 73 35  oc64(sizeof(Fts5
3180: 48 61 73 68 45 6e 74 72 79 2a 29 20 2a 20 6e 4d  HashEntry*) * nM
3190: 65 72 67 65 53 6c 6f 74 29 3b 0a 20 20 69 66 28  ergeSlot);.  if(
31a0: 20 21 61 70 20 29 20 72 65 74 75 72 6e 20 53 51   !ap ) return SQ
31b0: 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 6d 65  LITE_NOMEM;.  me
31c0: 6d 73 65 74 28 61 70 2c 20 30 2c 20 73 69 7a 65  mset(ap, 0, size
31d0: 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79  of(Fts5HashEntry
31e0: 2a 29 20 2a 20 6e 4d 65 72 67 65 53 6c 6f 74 29  *) * nMergeSlot)
31f0: 3b 0a 0a 20 20 66 6f 72 28 69 53 6c 6f 74 3d 30  ;..  for(iSlot=0
3200: 3b 20 69 53 6c 6f 74 3c 70 48 61 73 68 2d 3e 6e  ; iSlot<pHash->n
3210: 53 6c 6f 74 3b 20 69 53 6c 6f 74 2b 2b 29 7b 0a  Slot; iSlot++){.
3220: 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74 72      Fts5HashEntr
3230: 79 20 2a 70 49 74 65 72 3b 0a 20 20 20 20 66 6f  y *pIter;.    fo
3240: 72 28 70 49 74 65 72 3d 70 48 61 73 68 2d 3e 61  r(pIter=pHash->a
3250: 53 6c 6f 74 5b 69 53 6c 6f 74 5d 3b 20 70 49 74  Slot[iSlot]; pIt
3260: 65 72 3b 20 70 49 74 65 72 3d 70 49 74 65 72 2d  er; pIter=pIter-
3270: 3e 70 48 61 73 68 4e 65 78 74 29 7b 0a 20 20 20  >pHashNext){.   
3280: 20 20 20 69 66 28 20 70 54 65 72 6d 3d 3d 30 20     if( pTerm==0 
3290: 7c 7c 20 30 3d 3d 6d 65 6d 63 6d 70 28 66 74 73  || 0==memcmp(fts
32a0: 35 45 6e 74 72 79 4b 65 79 28 70 49 74 65 72 29  5EntryKey(pIter)
32b0: 2c 20 70 54 65 72 6d 2c 20 6e 54 65 72 6d 29 20  , pTerm, nTerm) 
32c0: 29 7b 0a 20 20 20 20 20 20 20 20 46 74 73 35 48  ){.        Fts5H
32d0: 61 73 68 45 6e 74 72 79 20 2a 70 45 6e 74 72 79  ashEntry *pEntry
32e0: 20 3d 20 70 49 74 65 72 3b 0a 20 20 20 20 20 20   = pIter;.      
32f0: 20 20 70 45 6e 74 72 79 2d 3e 70 53 63 61 6e 4e    pEntry->pScanN
3300: 65 78 74 20 3d 20 30 3b 0a 20 20 20 20 20 20 20  ext = 0;.       
3310: 20 66 6f 72 28 69 3d 30 3b 20 61 70 5b 69 5d 3b   for(i=0; ap[i];
3320: 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 20   i++){.         
3330: 20 70 45 6e 74 72 79 20 3d 20 66 74 73 35 48 61   pEntry = fts5Ha
3340: 73 68 45 6e 74 72 79 4d 65 72 67 65 28 70 45 6e  shEntryMerge(pEn
3350: 74 72 79 2c 20 61 70 5b 69 5d 29 3b 0a 20 20 20  try, ap[i]);.   
3360: 20 20 20 20 20 20 20 61 70 5b 69 5d 20 3d 20 30         ap[i] = 0
3370: 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20  ;.        }.    
3380: 20 20 20 20 61 70 5b 69 5d 20 3d 20 70 45 6e 74      ap[i] = pEnt
3390: 72 79 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20  ry;.      }.    
33a0: 7d 0a 20 20 7d 0a 0a 20 20 70 4c 69 73 74 20 3d  }.  }..  pList =
33b0: 20 30 3b 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69   0;.  for(i=0; i
33c0: 3c 6e 4d 65 72 67 65 53 6c 6f 74 3b 20 69 2b 2b  <nMergeSlot; i++
33d0: 29 7b 0a 20 20 20 20 70 4c 69 73 74 20 3d 20 66  ){.    pList = f
33e0: 74 73 35 48 61 73 68 45 6e 74 72 79 4d 65 72 67  ts5HashEntryMerg
33f0: 65 28 70 4c 69 73 74 2c 20 61 70 5b 69 5d 29 3b  e(pList, ap[i]);
3400: 0a 20 20 7d 0a 0a 20 20 70 48 61 73 68 2d 3e 6e  .  }..  pHash->n
3410: 45 6e 74 72 79 20 3d 20 30 3b 0a 20 20 73 71 6c  Entry = 0;.  sql
3420: 69 74 65 33 5f 66 72 65 65 28 61 70 29 3b 0a 20  ite3_free(ap);. 
3430: 20 2a 70 70 53 6f 72 74 65 64 20 3d 20 70 4c 69   *ppSorted = pLi
3440: 73 74 3b 0a 20 20 72 65 74 75 72 6e 20 53 51 4c  st;.  return SQL
3450: 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  ITE_OK;.}../*.**
3460: 20 51 75 65 72 79 20 74 68 65 20 68 61 73 68 20   Query the hash 
3470: 74 61 62 6c 65 20 66 6f 72 20 61 20 64 6f 63 6c  table for a docl
3480: 69 73 74 20 61 73 73 6f 63 69 61 74 65 64 20 77  ist associated w
3490: 69 74 68 20 74 65 72 6d 20 70 54 65 72 6d 2f 6e  ith term pTerm/n
34a0: 54 65 72 6d 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c  Term..*/.int sql
34b0: 69 74 65 33 46 74 73 35 48 61 73 68 51 75 65 72  ite3Fts5HashQuer
34c0: 79 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a 70  y(.  Fts5Hash *p
34d0: 48 61 73 68 2c 20 20 20 20 20 20 20 20 20 20 20  Hash,           
34e0: 20 20 20 20 20 2f 2a 20 48 61 73 68 20 74 61 62       /* Hash tab
34f0: 6c 65 20 74 6f 20 71 75 65 72 79 20 2a 2f 0a 20  le to query */. 
3500: 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 54 65   const char *pTe
3510: 72 6d 2c 20 69 6e 74 20 6e 54 65 72 6d 2c 20 20  rm, int nTerm,  
3520: 20 2f 2a 20 51 75 65 72 79 20 74 65 72 6d 20 2a   /* Query term *
3530: 2f 0a 20 20 63 6f 6e 73 74 20 75 38 20 2a 2a 70  /.  const u8 **p
3540: 70 44 6f 63 6c 69 73 74 2c 20 20 20 20 20 20 20  pDoclist,       
3550: 20 20 20 20 2f 2a 20 4f 55 54 3a 20 50 6f 69 6e      /* OUT: Poin
3560: 74 65 72 20 74 6f 20 64 6f 63 6c 69 73 74 20 66  ter to doclist f
3570: 6f 72 20 70 54 65 72 6d 20 2a 2f 0a 20 20 69 6e  or pTerm */.  in
3580: 74 20 2a 70 6e 44 6f 63 6c 69 73 74 20 20 20 20  t *pnDoclist    
3590: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
35a0: 20 4f 55 54 3a 20 53 69 7a 65 20 6f 66 20 64 6f   OUT: Size of do
35b0: 63 6c 69 73 74 20 69 6e 20 62 79 74 65 73 20 2a  clist in bytes *
35c0: 2f 0a 29 7b 0a 20 20 75 6e 73 69 67 6e 65 64 20  /.){.  unsigned 
35d0: 69 6e 74 20 69 48 61 73 68 20 3d 20 66 74 73 35  int iHash = fts5
35e0: 48 61 73 68 4b 65 79 28 70 48 61 73 68 2d 3e 6e  HashKey(pHash->n
35f0: 53 6c 6f 74 2c 20 28 63 6f 6e 73 74 20 75 38 2a  Slot, (const u8*
3600: 29 70 54 65 72 6d 2c 20 6e 54 65 72 6d 29 3b 0a  )pTerm, nTerm);.
3610: 20 20 63 68 61 72 20 2a 7a 4b 65 79 20 3d 20 30    char *zKey = 0
3620: 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72  ;.  Fts5HashEntr
3630: 79 20 2a 70 3b 0a 0a 20 20 66 6f 72 28 70 3d 70  y *p;..  for(p=p
3640: 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 48 61 73  Hash->aSlot[iHas
3650: 68 5d 3b 20 70 3b 20 70 3d 70 2d 3e 70 48 61 73  h]; p; p=p->pHas
3660: 68 4e 65 78 74 29 7b 0a 20 20 20 20 7a 4b 65 79  hNext){.    zKey
3670: 20 3d 20 66 74 73 35 45 6e 74 72 79 4b 65 79 28   = fts5EntryKey(
3680: 70 29 3b 0a 20 20 20 20 61 73 73 65 72 74 28 20  p);.    assert( 
3690: 70 2d 3e 6e 4b 65 79 2b 31 3d 3d 28 69 6e 74 29  p->nKey+1==(int)
36a0: 73 74 72 6c 65 6e 28 7a 4b 65 79 29 20 29 3b 0a  strlen(zKey) );.
36b0: 20 20 20 20 69 66 28 20 6e 54 65 72 6d 3d 3d 70      if( nTerm==p
36c0: 2d 3e 6e 4b 65 79 2b 31 20 26 26 20 6d 65 6d 63  ->nKey+1 && memc
36d0: 6d 70 28 7a 4b 65 79 2c 20 70 54 65 72 6d 2c 20  mp(zKey, pTerm, 
36e0: 6e 54 65 72 6d 29 3d 3d 30 20 29 20 62 72 65 61  nTerm)==0 ) brea
36f0: 6b 3b 0a 20 20 7d 0a 0a 20 20 69 66 28 20 70 20  k;.  }..  if( p 
3700: 29 7b 0a 20 20 20 20 66 74 73 35 48 61 73 68 41  ){.    fts5HashA
3710: 64 64 50 6f 73 6c 69 73 74 53 69 7a 65 28 70 48  ddPoslistSize(pH
3720: 61 73 68 2c 20 70 29 3b 0a 20 20 20 20 2a 70 70  ash, p);.    *pp
3730: 44 6f 63 6c 69 73 74 20 3d 20 28 63 6f 6e 73 74  Doclist = (const
3740: 20 75 38 2a 29 26 7a 4b 65 79 5b 6e 54 65 72 6d   u8*)&zKey[nTerm
3750: 2b 31 5d 3b 0a 20 20 20 20 2a 70 6e 44 6f 63 6c  +1];.    *pnDocl
3760: 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74 61 20 2d  ist = p->nData -
3770: 20 28 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73   (sizeof(Fts5Has
3780: 68 45 6e 74 72 79 29 20 2b 20 6e 54 65 72 6d 20  hEntry) + nTerm 
3790: 2b 20 31 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20  + 1);.  }else{. 
37a0: 20 20 20 2a 70 70 44 6f 63 6c 69 73 74 20 3d 20     *ppDoclist = 
37b0: 30 3b 0a 20 20 20 20 2a 70 6e 44 6f 63 6c 69 73  0;.    *pnDoclis
37c0: 74 20 3d 20 30 3b 0a 20 20 7d 0a 0a 20 20 72 65  t = 0;.  }..  re
37d0: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a  turn SQLITE_OK;.
37e0: 7d 0a 0a 69 6e 74 20 73 71 6c 69 74 65 33 46 74  }..int sqlite3Ft
37f0: 73 35 48 61 73 68 53 63 61 6e 49 6e 69 74 28 0a  s5HashScanInit(.
3800: 20 20 46 74 73 35 48 61 73 68 20 2a 70 2c 20 20    Fts5Hash *p,  
3810: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3820: 20 20 2f 2a 20 48 61 73 68 20 74 61 62 6c 65 20    /* Hash table 
3830: 74 6f 20 71 75 65 72 79 20 2a 2f 0a 20 20 63 6f  to query */.  co
3840: 6e 73 74 20 63 68 61 72 20 2a 70 54 65 72 6d 2c  nst char *pTerm,
3850: 20 69 6e 74 20 6e 54 65 72 6d 20 20 20 20 2f 2a   int nTerm    /*
3860: 20 51 75 65 72 79 20 70 72 65 66 69 78 20 2a 2f   Query prefix */
3870: 0a 29 7b 0a 20 20 72 65 74 75 72 6e 20 66 74 73  .){.  return fts
3880: 35 48 61 73 68 45 6e 74 72 79 53 6f 72 74 28 70  5HashEntrySort(p
3890: 2c 20 70 54 65 72 6d 2c 20 6e 54 65 72 6d 2c 20  , pTerm, nTerm, 
38a0: 26 70 2d 3e 70 53 63 61 6e 29 3b 0a 7d 0a 0a 76  &p->pScan);.}..v
38b0: 6f 69 64 20 73 71 6c 69 74 65 33 46 74 73 35 48  oid sqlite3Fts5H
38c0: 61 73 68 53 63 61 6e 4e 65 78 74 28 46 74 73 35  ashScanNext(Fts5
38d0: 48 61 73 68 20 2a 70 29 7b 0a 20 20 61 73 73 65  Hash *p){.  asse
38e0: 72 74 28 20 21 73 71 6c 69 74 65 33 46 74 73 35  rt( !sqlite3Fts5
38f0: 48 61 73 68 53 63 61 6e 45 6f 66 28 70 29 20 29  HashScanEof(p) )
3900: 3b 0a 20 20 70 2d 3e 70 53 63 61 6e 20 3d 20 70  ;.  p->pScan = p
3910: 2d 3e 70 53 63 61 6e 2d 3e 70 53 63 61 6e 4e 65  ->pScan->pScanNe
3920: 78 74 3b 0a 7d 0a 0a 69 6e 74 20 73 71 6c 69 74  xt;.}..int sqlit
3930: 65 33 46 74 73 35 48 61 73 68 53 63 61 6e 45 6f  e3Fts5HashScanEo
3940: 66 28 46 74 73 35 48 61 73 68 20 2a 70 29 7b 0a  f(Fts5Hash *p){.
3950: 20 20 72 65 74 75 72 6e 20 28 70 2d 3e 70 53 63    return (p->pSc
3960: 61 6e 3d 3d 30 29 3b 0a 7d 0a 0a 76 6f 69 64 20  an==0);.}..void 
3970: 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 53  sqlite3Fts5HashS
3980: 63 61 6e 45 6e 74 72 79 28 0a 20 20 46 74 73 35  canEntry(.  Fts5
3990: 48 61 73 68 20 2a 70 48 61 73 68 2c 0a 20 20 63  Hash *pHash,.  c
39a0: 6f 6e 73 74 20 63 68 61 72 20 2a 2a 70 7a 54 65  onst char **pzTe
39b0: 72 6d 2c 20 20 20 20 20 20 20 20 20 20 20 20 2f  rm,            /
39c0: 2a 20 4f 55 54 3a 20 74 65 72 6d 20 28 6e 75 6c  * OUT: term (nul
39d0: 2d 74 65 72 6d 69 6e 61 74 65 64 29 20 2a 2f 0a  -terminated) */.
39e0: 20 20 63 6f 6e 73 74 20 75 38 20 2a 2a 70 70 44    const u8 **ppD
39f0: 6f 63 6c 69 73 74 2c 20 20 20 20 20 20 20 20 20  oclist,         
3a00: 20 20 2f 2a 20 4f 55 54 3a 20 70 6f 69 6e 74 65    /* OUT: pointe
3a10: 72 20 74 6f 20 64 6f 63 6c 69 73 74 20 2a 2f 0a  r to doclist */.
3a20: 20 20 69 6e 74 20 2a 70 6e 44 6f 63 6c 69 73 74    int *pnDoclist
3a30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3a40: 20 20 2f 2a 20 4f 55 54 3a 20 73 69 7a 65 20 6f    /* OUT: size o
3a50: 66 20 64 6f 63 6c 69 73 74 20 69 6e 20 62 79 74  f doclist in byt
3a60: 65 73 20 2a 2f 0a 29 7b 0a 20 20 46 74 73 35 48  es */.){.  Fts5H
3a70: 61 73 68 45 6e 74 72 79 20 2a 70 3b 0a 20 20 69  ashEntry *p;.  i
3a80: 66 28 20 28 70 20 3d 20 70 48 61 73 68 2d 3e 70  f( (p = pHash->p
3a90: 53 63 61 6e 29 20 29 7b 0a 20 20 20 20 63 68 61  Scan) ){.    cha
3aa0: 72 20 2a 7a 4b 65 79 20 3d 20 66 74 73 35 45 6e  r *zKey = fts5En
3ab0: 74 72 79 4b 65 79 28 70 29 3b 0a 20 20 20 20 69  tryKey(p);.    i
3ac0: 6e 74 20 6e 54 65 72 6d 20 3d 20 28 69 6e 74 29  nt nTerm = (int)
3ad0: 73 74 72 6c 65 6e 28 7a 4b 65 79 29 3b 0a 20 20  strlen(zKey);.  
3ae0: 20 20 66 74 73 35 48 61 73 68 41 64 64 50 6f 73    fts5HashAddPos
3af0: 6c 69 73 74 53 69 7a 65 28 70 48 61 73 68 2c 20  listSize(pHash, 
3b00: 70 29 3b 0a 20 20 20 20 2a 70 7a 54 65 72 6d 20  p);.    *pzTerm 
3b10: 3d 20 7a 4b 65 79 3b 0a 20 20 20 20 2a 70 70 44  = zKey;.    *ppD
3b20: 6f 63 6c 69 73 74 20 3d 20 28 63 6f 6e 73 74 20  oclist = (const 
3b30: 75 38 2a 29 26 7a 4b 65 79 5b 6e 54 65 72 6d 2b  u8*)&zKey[nTerm+
3b40: 31 5d 3b 0a 20 20 20 20 2a 70 6e 44 6f 63 6c 69  1];.    *pnDocli
3b50: 73 74 20 3d 20 70 2d 3e 6e 44 61 74 61 20 2d 20  st = p->nData - 
3b60: 28 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68  (sizeof(Fts5Hash
3b70: 45 6e 74 72 79 29 20 2b 20 6e 54 65 72 6d 20 2b  Entry) + nTerm +
3b80: 20 31 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20   1);.  }else{.  
3b90: 20 20 2a 70 7a 54 65 72 6d 20 3d 20 30 3b 0a 20    *pzTerm = 0;. 
3ba0: 20 20 20 2a 70 70 44 6f 63 6c 69 73 74 20 3d 20     *ppDoclist = 
3bb0: 30 3b 0a 20 20 20 20 2a 70 6e 44 6f 63 6c 69 73  0;.    *pnDoclis
3bc0: 74 20 3d 20 30 3b 0a 20 20 7d 0a 7d 0a           t = 0;.  }.}.