/ Hex Artifact Content
Login

Artifact 534d5591f479c0999543689122ad6952823bc7c85273a0ff4f7f91d9f914a54b:


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 69 6e 74 20 6e  }else{.    int n
0bf0: 42 79 74 65 3b 0a 20 20 20 20 6d 65 6d 73 65 74  Byte;.    memset
0c00: 28 70 4e 65 77 2c 20 30 2c 20 73 69 7a 65 6f 66  (pNew, 0, sizeof
0c10: 28 46 74 73 35 48 61 73 68 29 29 3b 0a 20 20 20  (Fts5Hash));.   
0c20: 20 70 4e 65 77 2d 3e 70 6e 42 79 74 65 20 3d 20   pNew->pnByte = 
0c30: 70 6e 42 79 74 65 3b 0a 20 20 20 20 70 4e 65 77  pnByte;.    pNew
0c40: 2d 3e 65 44 65 74 61 69 6c 20 3d 20 70 43 6f 6e  ->eDetail = pCon
0c50: 66 69 67 2d 3e 65 44 65 74 61 69 6c 3b 0a 0a 20  fig->eDetail;.. 
0c60: 20 20 20 70 4e 65 77 2d 3e 6e 53 6c 6f 74 20 3d     pNew->nSlot =
0c70: 20 31 30 32 34 3b 0a 20 20 20 20 6e 42 79 74 65   1024;.    nByte
0c80: 20 3d 20 73 69 7a 65 6f 66 28 46 74 73 35 48 61   = sizeof(Fts5Ha
0c90: 73 68 45 6e 74 72 79 2a 29 20 2a 20 70 4e 65 77  shEntry*) * pNew
0ca0: 2d 3e 6e 53 6c 6f 74 3b 0a 20 20 20 20 70 4e 65  ->nSlot;.    pNe
0cb0: 77 2d 3e 61 53 6c 6f 74 20 3d 20 28 46 74 73 35  w->aSlot = (Fts5
0cc0: 48 61 73 68 45 6e 74 72 79 2a 2a 29 73 71 6c 69  HashEntry**)sqli
0cd0: 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e 42 79 74 65  te3_malloc(nByte
0ce0: 29 3b 0a 20 20 20 20 69 66 28 20 70 4e 65 77 2d  );.    if( pNew-
0cf0: 3e 61 53 6c 6f 74 3d 3d 30 20 29 7b 0a 20 20 20  >aSlot==0 ){.   
0d00: 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28     sqlite3_free(
0d10: 70 4e 65 77 29 3b 0a 20 20 20 20 20 20 2a 70 70  pNew);.      *pp
0d20: 4e 65 77 20 3d 20 30 3b 0a 20 20 20 20 20 20 72  New = 0;.      r
0d30: 63 20 3d 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d  c = SQLITE_NOMEM
0d40: 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20  ;.    }else{.   
0d50: 20 20 20 6d 65 6d 73 65 74 28 70 4e 65 77 2d 3e     memset(pNew->
0d60: 61 53 6c 6f 74 2c 20 30 2c 20 6e 42 79 74 65 29  aSlot, 0, nByte)
0d70: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 72 65  ;.    }.  }.  re
0d80: 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a  turn rc;.}../*.*
0d90: 2a 20 46 72 65 65 20 61 20 68 61 73 68 20 74 61  * Free a hash ta
0da0: 62 6c 65 20 6f 62 6a 65 63 74 2e 0a 2a 2f 0a 76  ble object..*/.v
0db0: 6f 69 64 20 73 71 6c 69 74 65 33 46 74 73 35 48  oid sqlite3Fts5H
0dc0: 61 73 68 46 72 65 65 28 46 74 73 35 48 61 73 68  ashFree(Fts5Hash
0dd0: 20 2a 70 48 61 73 68 29 7b 0a 20 20 69 66 28 20   *pHash){.  if( 
0de0: 70 48 61 73 68 20 29 7b 0a 20 20 20 20 73 71 6c  pHash ){.    sql
0df0: 69 74 65 33 46 74 73 35 48 61 73 68 43 6c 65 61  ite3Fts5HashClea
0e00: 72 28 70 48 61 73 68 29 3b 0a 20 20 20 20 73 71  r(pHash);.    sq
0e10: 6c 69 74 65 33 5f 66 72 65 65 28 70 48 61 73 68  lite3_free(pHash
0e20: 2d 3e 61 53 6c 6f 74 29 3b 0a 20 20 20 20 73 71  ->aSlot);.    sq
0e30: 6c 69 74 65 33 5f 66 72 65 65 28 70 48 61 73 68  lite3_free(pHash
0e40: 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20  );.  }.}../*.** 
0e50: 45 6d 70 74 79 20 28 62 75 74 20 64 6f 20 6e 6f  Empty (but do no
0e60: 74 20 64 65 6c 65 74 65 29 20 61 20 68 61 73 68  t delete) a hash
0e70: 20 74 61 62 6c 65 2e 0a 2a 2f 0a 76 6f 69 64 20   table..*/.void 
0e80: 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 43  sqlite3Fts5HashC
0e90: 6c 65 61 72 28 46 74 73 35 48 61 73 68 20 2a 70  lear(Fts5Hash *p
0ea0: 48 61 73 68 29 7b 0a 20 20 69 6e 74 20 69 3b 0a  Hash){.  int i;.
0eb0: 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 70 48 61    for(i=0; i<pHa
0ec0: 73 68 2d 3e 6e 53 6c 6f 74 3b 20 69 2b 2b 29 7b  sh->nSlot; i++){
0ed0: 0a 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74  .    Fts5HashEnt
0ee0: 72 79 20 2a 70 4e 65 78 74 3b 0a 20 20 20 20 46  ry *pNext;.    F
0ef0: 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 53  ts5HashEntry *pS
0f00: 6c 6f 74 3b 0a 20 20 20 20 66 6f 72 28 70 53 6c  lot;.    for(pSl
0f10: 6f 74 3d 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b  ot=pHash->aSlot[
0f20: 69 5d 3b 20 70 53 6c 6f 74 3b 20 70 53 6c 6f 74  i]; pSlot; pSlot
0f30: 3d 70 4e 65 78 74 29 7b 0a 20 20 20 20 20 20 70  =pNext){.      p
0f40: 4e 65 78 74 20 3d 20 70 53 6c 6f 74 2d 3e 70 48  Next = pSlot->pH
0f50: 61 73 68 4e 65 78 74 3b 0a 20 20 20 20 20 20 73  ashNext;.      s
0f60: 71 6c 69 74 65 33 5f 66 72 65 65 28 70 53 6c 6f  qlite3_free(pSlo
0f70: 74 29 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20  t);.    }.  }.  
0f80: 6d 65 6d 73 65 74 28 70 48 61 73 68 2d 3e 61 53  memset(pHash->aS
0f90: 6c 6f 74 2c 20 30 2c 20 70 48 61 73 68 2d 3e 6e  lot, 0, pHash->n
0fa0: 53 6c 6f 74 20 2a 20 73 69 7a 65 6f 66 28 46 74  Slot * sizeof(Ft
0fb0: 73 35 48 61 73 68 45 6e 74 72 79 2a 29 29 3b 0a  s5HashEntry*));.
0fc0: 20 20 70 48 61 73 68 2d 3e 6e 45 6e 74 72 79 20    pHash->nEntry 
0fd0: 3d 20 30 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 75  = 0;.}..static u
0fe0: 6e 73 69 67 6e 65 64 20 69 6e 74 20 66 74 73 35  nsigned int fts5
0ff0: 48 61 73 68 4b 65 79 28 69 6e 74 20 6e 53 6c 6f  HashKey(int nSlo
1000: 74 2c 20 63 6f 6e 73 74 20 75 38 20 2a 70 2c 20  t, const u8 *p, 
1010: 69 6e 74 20 6e 29 7b 0a 20 20 69 6e 74 20 69 3b  int n){.  int i;
1020: 0a 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20  .  unsigned int 
1030: 68 20 3d 20 31 33 3b 0a 20 20 66 6f 72 28 69 3d  h = 13;.  for(i=
1040: 6e 2d 31 3b 20 69 3e 3d 30 3b 20 69 2d 2d 29 7b  n-1; i>=0; i--){
1050: 0a 20 20 20 20 68 20 3d 20 28 68 20 3c 3c 20 33  .    h = (h << 3
1060: 29 20 5e 20 68 20 5e 20 70 5b 69 5d 3b 0a 20 20  ) ^ h ^ p[i];.  
1070: 7d 0a 20 20 72 65 74 75 72 6e 20 28 68 20 25 20  }.  return (h % 
1080: 6e 53 6c 6f 74 29 3b 0a 7d 0a 0a 73 74 61 74 69  nSlot);.}..stati
1090: 63 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 66  c unsigned int f
10a0: 74 73 35 48 61 73 68 4b 65 79 32 28 69 6e 74 20  ts5HashKey2(int 
10b0: 6e 53 6c 6f 74 2c 20 75 38 20 62 2c 20 63 6f 6e  nSlot, u8 b, con
10c0: 73 74 20 75 38 20 2a 70 2c 20 69 6e 74 20 6e 29  st u8 *p, int n)
10d0: 7b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 75 6e 73  {.  int i;.  uns
10e0: 69 67 6e 65 64 20 69 6e 74 20 68 20 3d 20 31 33  igned int h = 13
10f0: 3b 0a 20 20 66 6f 72 28 69 3d 6e 2d 31 3b 20 69  ;.  for(i=n-1; i
1100: 3e 3d 30 3b 20 69 2d 2d 29 7b 0a 20 20 20 20 68  >=0; i--){.    h
1110: 20 3d 20 28 68 20 3c 3c 20 33 29 20 5e 20 68 20   = (h << 3) ^ h 
1120: 5e 20 70 5b 69 5d 3b 0a 20 20 7d 0a 20 20 68 20  ^ p[i];.  }.  h 
1130: 3d 20 28 68 20 3c 3c 20 33 29 20 5e 20 68 20 5e  = (h << 3) ^ h ^
1140: 20 62 3b 0a 20 20 72 65 74 75 72 6e 20 28 68 20   b;.  return (h 
1150: 25 20 6e 53 6c 6f 74 29 3b 0a 7d 0a 0a 2f 2a 0a  % nSlot);.}../*.
1160: 2a 2a 20 52 65 73 69 7a 65 20 74 68 65 20 68 61  ** Resize the ha
1170: 73 68 20 74 61 62 6c 65 20 62 79 20 64 6f 75 62  sh table by doub
1180: 6c 69 6e 67 20 74 68 65 20 6e 75 6d 62 65 72 20  ling the number 
1190: 6f 66 20 73 6c 6f 74 73 2e 0a 2a 2f 0a 73 74 61  of slots..*/.sta
11a0: 74 69 63 20 69 6e 74 20 66 74 73 35 48 61 73 68  tic int fts5Hash
11b0: 52 65 73 69 7a 65 28 46 74 73 35 48 61 73 68 20  Resize(Fts5Hash 
11c0: 2a 70 48 61 73 68 29 7b 0a 20 20 69 6e 74 20 6e  *pHash){.  int n
11d0: 4e 65 77 20 3d 20 70 48 61 73 68 2d 3e 6e 53 6c  New = pHash->nSl
11e0: 6f 74 2a 32 3b 0a 20 20 69 6e 74 20 69 3b 0a 20  ot*2;.  int i;. 
11f0: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
1200: 2a 61 70 4e 65 77 3b 0a 20 20 46 74 73 35 48 61  *apNew;.  Fts5Ha
1210: 73 68 45 6e 74 72 79 20 2a 2a 61 70 4f 6c 64 20  shEntry **apOld 
1220: 3d 20 70 48 61 73 68 2d 3e 61 53 6c 6f 74 3b 0a  = pHash->aSlot;.
1230: 0a 20 20 61 70 4e 65 77 20 3d 20 28 46 74 73 35  .  apNew = (Fts5
1240: 48 61 73 68 45 6e 74 72 79 2a 2a 29 73 71 6c 69  HashEntry**)sqli
1250: 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e 4e 65 77 2a  te3_malloc(nNew*
1260: 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45  sizeof(Fts5HashE
1270: 6e 74 72 79 2a 29 29 3b 0a 20 20 69 66 28 20 21  ntry*));.  if( !
1280: 61 70 4e 65 77 20 29 20 72 65 74 75 72 6e 20 53  apNew ) return S
1290: 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 6d  QLITE_NOMEM;.  m
12a0: 65 6d 73 65 74 28 61 70 4e 65 77 2c 20 30 2c 20  emset(apNew, 0, 
12b0: 6e 4e 65 77 2a 73 69 7a 65 6f 66 28 46 74 73 35  nNew*sizeof(Fts5
12c0: 48 61 73 68 45 6e 74 72 79 2a 29 29 3b 0a 0a 20  HashEntry*));.. 
12d0: 20 66 6f 72 28 69 3d 30 3b 20 69 3c 70 48 61 73   for(i=0; i<pHas
12e0: 68 2d 3e 6e 53 6c 6f 74 3b 20 69 2b 2b 29 7b 0a  h->nSlot; i++){.
12f0: 20 20 20 20 77 68 69 6c 65 28 20 61 70 4f 6c 64      while( apOld
1300: 5b 69 5d 20 29 7b 0a 20 20 20 20 20 20 69 6e 74  [i] ){.      int
1310: 20 69 48 61 73 68 3b 0a 20 20 20 20 20 20 46 74   iHash;.      Ft
1320: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 20 3d  s5HashEntry *p =
1330: 20 61 70 4f 6c 64 5b 69 5d 3b 0a 20 20 20 20 20   apOld[i];.     
1340: 20 61 70 4f 6c 64 5b 69 5d 20 3d 20 70 2d 3e 70   apOld[i] = p->p
1350: 48 61 73 68 4e 65 78 74 3b 0a 20 20 20 20 20 20  HashNext;.      
1360: 69 48 61 73 68 20 3d 20 66 74 73 35 48 61 73 68  iHash = fts5Hash
1370: 4b 65 79 28 6e 4e 65 77 2c 20 28 75 38 2a 29 66  Key(nNew, (u8*)f
1380: 74 73 35 45 6e 74 72 79 4b 65 79 28 70 29 2c 20  ts5EntryKey(p), 
1390: 73 74 72 6c 65 6e 28 66 74 73 35 45 6e 74 72 79  strlen(fts5Entry
13a0: 4b 65 79 28 70 29 29 29 3b 0a 20 20 20 20 20 20  Key(p)));.      
13b0: 70 2d 3e 70 48 61 73 68 4e 65 78 74 20 3d 20 61  p->pHashNext = a
13c0: 70 4e 65 77 5b 69 48 61 73 68 5d 3b 0a 20 20 20  pNew[iHash];.   
13d0: 20 20 20 61 70 4e 65 77 5b 69 48 61 73 68 5d 20     apNew[iHash] 
13e0: 3d 20 70 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a  = p;.    }.  }..
13f0: 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 61    sqlite3_free(a
1400: 70 4f 6c 64 29 3b 0a 20 20 70 48 61 73 68 2d 3e  pOld);.  pHash->
1410: 6e 53 6c 6f 74 20 3d 20 6e 4e 65 77 3b 0a 20 20  nSlot = nNew;.  
1420: 70 48 61 73 68 2d 3e 61 53 6c 6f 74 20 3d 20 61  pHash->aSlot = a
1430: 70 4e 65 77 3b 0a 20 20 72 65 74 75 72 6e 20 53  pNew;.  return S
1440: 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 73 74 61  QLITE_OK;.}..sta
1450: 74 69 63 20 76 6f 69 64 20 66 74 73 35 48 61 73  tic void fts5Has
1460: 68 41 64 64 50 6f 73 6c 69 73 74 53 69 7a 65 28  hAddPoslistSize(
1470: 46 74 73 35 48 61 73 68 20 2a 70 48 61 73 68 2c  Fts5Hash *pHash,
1480: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
1490: 70 29 7b 0a 20 20 69 66 28 20 70 2d 3e 69 53 7a  p){.  if( p->iSz
14a0: 50 6f 73 6c 69 73 74 20 29 7b 0a 20 20 20 20 75  Poslist ){.    u
14b0: 38 20 2a 70 50 74 72 20 3d 20 28 75 38 2a 29 70  8 *pPtr = (u8*)p
14c0: 3b 0a 20 20 20 20 69 66 28 20 70 48 61 73 68 2d  ;.    if( pHash-
14d0: 3e 65 44 65 74 61 69 6c 3d 3d 46 54 53 35 5f 44  >eDetail==FTS5_D
14e0: 45 54 41 49 4c 5f 4e 4f 4e 45 20 29 7b 0a 20 20  ETAIL_NONE ){.  
14f0: 20 20 20 20 61 73 73 65 72 74 28 20 70 2d 3e 6e      assert( p->n
1500: 44 61 74 61 3d 3d 70 2d 3e 69 53 7a 50 6f 73 6c  Data==p->iSzPosl
1510: 69 73 74 20 29 3b 0a 20 20 20 20 20 20 69 66 28  ist );.      if(
1520: 20 70 2d 3e 62 44 65 6c 20 29 7b 0a 20 20 20 20   p->bDel ){.    
1530: 20 20 20 20 70 50 74 72 5b 70 2d 3e 6e 44 61 74      pPtr[p->nDat
1540: 61 2b 2b 5d 20 3d 20 30 78 30 30 3b 0a 20 20 20  a++] = 0x00;.   
1550: 20 20 20 20 20 69 66 28 20 70 2d 3e 62 43 6f 6e       if( p->bCon
1560: 74 65 6e 74 20 29 7b 0a 20 20 20 20 20 20 20 20  tent ){.        
1570: 20 20 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61 2b    pPtr[p->nData+
1580: 2b 5d 20 3d 20 30 78 30 30 3b 0a 20 20 20 20 20  +] = 0x00;.     
1590: 20 20 20 7d 0a 20 20 20 20 20 20 7d 0a 20 20 20     }.      }.   
15a0: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 69 6e   }else{.      in
15b0: 74 20 6e 53 7a 20 3d 20 28 70 2d 3e 6e 44 61 74  t nSz = (p->nDat
15c0: 61 20 2d 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73  a - p->iSzPoslis
15d0: 74 20 2d 20 31 29 3b 20 20 20 20 20 20 20 2f 2a  t - 1);       /*
15e0: 20 53 69 7a 65 20 69 6e 20 62 79 74 65 73 20 2a   Size in bytes *
15f0: 2f 0a 20 20 20 20 20 20 69 6e 74 20 6e 50 6f 73  /.      int nPos
1600: 20 3d 20 6e 53 7a 2a 32 20 2b 20 70 2d 3e 62 44   = nSz*2 + p->bD
1610: 65 6c 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  el;             
1620: 20 20 20 20 20 20 20 20 2f 2a 20 56 61 6c 75 65          /* Value
1630: 20 6f 66 20 6e 50 6f 73 20 66 69 65 6c 64 20 2a   of nPos field *
1640: 2f 0a 0a 20 20 20 20 20 20 61 73 73 65 72 74 28  /..      assert(
1650: 20 70 2d 3e 62 44 65 6c 3d 3d 30 20 7c 7c 20 70   p->bDel==0 || p
1660: 2d 3e 62 44 65 6c 3d 3d 31 20 29 3b 0a 20 20 20  ->bDel==1 );.   
1670: 20 20 20 69 66 28 20 6e 50 6f 73 3c 3d 31 32 37     if( nPos<=127
1680: 20 29 7b 0a 20 20 20 20 20 20 20 20 70 50 74 72   ){.        pPtr
1690: 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 5d 20  [p->iSzPoslist] 
16a0: 3d 20 28 75 38 29 6e 50 6f 73 3b 0a 20 20 20 20  = (u8)nPos;.    
16b0: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 20    }else{.       
16c0: 20 69 6e 74 20 6e 42 79 74 65 20 3d 20 73 71 6c   int nByte = sql
16d0: 69 74 65 33 46 74 73 35 47 65 74 56 61 72 69 6e  ite3Fts5GetVarin
16e0: 74 4c 65 6e 28 28 75 33 32 29 6e 50 6f 73 29 3b  tLen((u32)nPos);
16f0: 0a 20 20 20 20 20 20 20 20 6d 65 6d 6d 6f 76 65  .        memmove
1700: 28 26 70 50 74 72 5b 70 2d 3e 69 53 7a 50 6f 73  (&pPtr[p->iSzPos
1710: 6c 69 73 74 20 2b 20 6e 42 79 74 65 5d 2c 20 26  list + nByte], &
1720: 70 50 74 72 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69  pPtr[p->iSzPosli
1730: 73 74 20 2b 20 31 5d 2c 20 6e 53 7a 29 3b 0a 20  st + 1], nSz);. 
1740: 20 20 20 20 20 20 20 73 71 6c 69 74 65 33 46 74         sqlite3Ft
1750: 73 35 50 75 74 56 61 72 69 6e 74 28 26 70 50 74  s5PutVarint(&pPt
1760: 72 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 5d  r[p->iSzPoslist]
1770: 2c 20 6e 50 6f 73 29 3b 0a 20 20 20 20 20 20 20  , nPos);.       
1780: 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 28 6e 42   p->nData += (nB
1790: 79 74 65 2d 31 29 3b 0a 20 20 20 20 20 20 7d 0a  yte-1);.      }.
17a0: 20 20 20 20 7d 0a 0a 20 20 20 20 70 2d 3e 69 53      }..    p->iS
17b0: 7a 50 6f 73 6c 69 73 74 20 3d 20 30 3b 0a 20 20  zPoslist = 0;.  
17c0: 20 20 70 2d 3e 62 44 65 6c 20 3d 20 30 3b 0a 20    p->bDel = 0;. 
17d0: 20 20 20 70 2d 3e 62 43 6f 6e 74 65 6e 74 20 3d     p->bContent =
17e0: 20 30 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a   0;.  }.}../*.**
17f0: 20 41 64 64 20 61 6e 20 65 6e 74 72 79 20 74 6f   Add an entry to
1800: 20 74 68 65 20 69 6e 2d 6d 65 6d 6f 72 79 20 68   the in-memory h
1810: 61 73 68 20 74 61 62 6c 65 2e 20 54 68 65 20 6b  ash table. The k
1820: 65 79 20 69 73 20 74 68 65 20 63 6f 6e 63 61 74  ey is the concat
1830: 65 6e 61 74 69 6f 6e 0a 2a 2a 20 6f 66 20 62 42  enation.** of bB
1840: 79 74 65 20 61 6e 64 20 28 70 54 6f 6b 65 6e 2f  yte and (pToken/
1850: 6e 54 6f 6b 65 6e 29 2e 20 54 68 65 20 76 61 6c  nToken). The val
1860: 75 65 20 69 73 20 28 69 52 6f 77 69 64 2f 69 43  ue is (iRowid/iC
1870: 6f 6c 2f 69 50 6f 73 29 2e 0a 2a 2a 0a 2a 2a 20  ol/iPos)..**.** 
1880: 20 20 20 20 28 62 42 79 74 65 20 7c 7c 20 70 54      (bByte || pT
1890: 6f 6b 65 6e 29 20 2d 3e 20 28 69 52 6f 77 69 64  oken) -> (iRowid
18a0: 2c 69 43 6f 6c 2c 69 50 6f 73 29 0a 2a 2a 0a 2a  ,iCol,iPos).**.*
18b0: 2a 20 4f 72 2c 20 69 66 20 69 43 6f 6c 20 69 73  * Or, if iCol is
18c0: 20 6e 65 67 61 74 69 76 65 2c 20 74 68 65 6e 20   negative, then 
18d0: 74 68 65 20 76 61 6c 75 65 20 69 73 20 61 20 64  the value is a d
18e0: 65 6c 65 74 65 20 6d 61 72 6b 65 72 2e 0a 2a 2f  elete marker..*/
18f0: 0a 69 6e 74 20 73 71 6c 69 74 65 33 46 74 73 35  .int sqlite3Fts5
1900: 48 61 73 68 57 72 69 74 65 28 0a 20 20 46 74 73  HashWrite(.  Fts
1910: 35 48 61 73 68 20 2a 70 48 61 73 68 2c 0a 20 20  5Hash *pHash,.  
1920: 69 36 34 20 69 52 6f 77 69 64 2c 20 20 20 20 20  i64 iRowid,     
1930: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1940: 2f 2a 20 52 6f 77 69 64 20 66 6f 72 20 74 68 69  /* Rowid for thi
1950: 73 20 65 6e 74 72 79 20 2a 2f 0a 20 20 69 6e 74  s entry */.  int
1960: 20 69 43 6f 6c 2c 20 20 20 20 20 20 20 20 20 20   iCol,          
1970: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
1980: 43 6f 6c 75 6d 6e 20 74 6f 6b 65 6e 20 61 70 70  Column token app
1990: 65 61 72 73 20 69 6e 20 28 2d 76 65 20 2d 3e 20  ears in (-ve -> 
19a0: 64 65 6c 65 74 65 29 20 2a 2f 0a 20 20 69 6e 74  delete) */.  int
19b0: 20 69 50 6f 73 2c 20 20 20 20 20 20 20 20 20 20   iPos,          
19c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
19d0: 50 6f 73 69 74 69 6f 6e 20 6f 66 20 74 6f 6b 65  Position of toke
19e0: 6e 20 77 69 74 68 69 6e 20 63 6f 6c 75 6d 6e 20  n within column 
19f0: 2a 2f 0a 20 20 63 68 61 72 20 62 42 79 74 65 2c  */.  char bByte,
1a00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1a10: 20 20 20 20 20 2f 2a 20 46 69 72 73 74 20 62 79       /* First by
1a20: 74 65 20 6f 66 20 74 6f 6b 65 6e 20 2a 2f 0a 20  te of token */. 
1a30: 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 54 6f   const char *pTo
1a40: 6b 65 6e 2c 20 69 6e 74 20 6e 54 6f 6b 65 6e 20  ken, int nToken 
1a50: 20 2f 2a 20 54 6f 6b 65 6e 20 74 6f 20 61 64 64   /* Token to add
1a60: 20 6f 72 20 72 65 6d 6f 76 65 20 74 6f 20 6f 72   or remove to or
1a70: 20 66 72 6f 6d 20 69 6e 64 65 78 20 2a 2f 0a 29   from index */.)
1a80: 7b 0a 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74  {.  unsigned int
1a90: 20 69 48 61 73 68 3b 0a 20 20 46 74 73 35 48 61   iHash;.  Fts5Ha
1aa0: 73 68 45 6e 74 72 79 20 2a 70 3b 0a 20 20 75 38  shEntry *p;.  u8
1ab0: 20 2a 70 50 74 72 3b 0a 20 20 69 6e 74 20 6e 49   *pPtr;.  int nI
1ac0: 6e 63 72 20 3d 20 30 3b 20 20 20 20 20 20 20 20  ncr = 0;        
1ad0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41 6d 6f            /* Amo
1ae0: 75 6e 74 20 74 6f 20 69 6e 63 72 65 6d 65 6e 74  unt to increment
1af0: 20 28 2a 70 48 61 73 68 2d 3e 70 6e 42 79 74 65   (*pHash->pnByte
1b00: 29 20 62 79 20 2a 2f 0a 20 20 69 6e 74 20 62 4e  ) by */.  int bN
1b10: 65 77 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  ew;             
1b20: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 49 66 20            /* If 
1b30: 6e 6f 6e 2d 64 65 6c 65 74 65 20 65 6e 74 72 79  non-delete entry
1b40: 20 73 68 6f 75 6c 64 20 62 65 20 77 72 69 74 74   should be writt
1b50: 65 6e 20 2a 2f 0a 20 20 0a 20 20 62 4e 65 77 20  en */.  .  bNew 
1b60: 3d 20 28 70 48 61 73 68 2d 3e 65 44 65 74 61 69  = (pHash->eDetai
1b70: 6c 3d 3d 46 54 53 35 5f 44 45 54 41 49 4c 5f 46  l==FTS5_DETAIL_F
1b80: 55 4c 4c 29 3b 0a 0a 20 20 2f 2a 20 41 74 74 65  ULL);..  /* Atte
1b90: 6d 70 74 20 74 6f 20 6c 6f 63 61 74 65 20 61 6e  mpt to locate an
1ba0: 20 65 78 69 73 74 69 6e 67 20 68 61 73 68 20 65   existing hash e
1bb0: 6e 74 72 79 20 2a 2f 0a 20 20 69 48 61 73 68 20  ntry */.  iHash 
1bc0: 3d 20 66 74 73 35 48 61 73 68 4b 65 79 32 28 70  = fts5HashKey2(p
1bd0: 48 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20 28 75 38  Hash->nSlot, (u8
1be0: 29 62 42 79 74 65 2c 20 28 63 6f 6e 73 74 20 75  )bByte, (const u
1bf0: 38 2a 29 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b 65  8*)pToken, nToke
1c00: 6e 29 3b 0a 20 20 66 6f 72 28 70 3d 70 48 61 73  n);.  for(p=pHas
1c10: 68 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d 3b  h->aSlot[iHash];
1c20: 20 70 3b 20 70 3d 70 2d 3e 70 48 61 73 68 4e 65   p; p=p->pHashNe
1c30: 78 74 29 7b 0a 20 20 20 20 63 68 61 72 20 2a 7a  xt){.    char *z
1c40: 4b 65 79 20 3d 20 66 74 73 35 45 6e 74 72 79 4b  Key = fts5EntryK
1c50: 65 79 28 70 29 3b 0a 20 20 20 20 69 66 28 20 7a  ey(p);.    if( z
1c60: 4b 65 79 5b 30 5d 3d 3d 62 42 79 74 65 20 0a 20  Key[0]==bByte . 
1c70: 20 20 20 20 26 26 20 70 2d 3e 6e 4b 65 79 3d 3d      && p->nKey==
1c80: 6e 54 6f 6b 65 6e 0a 20 20 20 20 20 26 26 20 6d  nToken.     && m
1c90: 65 6d 63 6d 70 28 26 7a 4b 65 79 5b 31 5d 2c 20  emcmp(&zKey[1], 
1ca0: 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3d  pToken, nToken)=
1cb0: 3d 30 20 0a 20 20 20 20 29 7b 0a 20 20 20 20 20  =0 .    ){.     
1cc0: 20 62 72 65 61 6b 3b 0a 20 20 20 20 7d 0a 20 20   break;.    }.  
1cd0: 7d 0a 0a 20 20 2f 2a 20 49 66 20 61 6e 20 65 78  }..  /* If an ex
1ce0: 69 73 74 69 6e 67 20 68 61 73 68 20 65 6e 74 72  isting hash entr
1cf0: 79 20 63 61 6e 6e 6f 74 20 62 65 20 66 6f 75 6e  y cannot be foun
1d00: 64 2c 20 63 72 65 61 74 65 20 61 20 6e 65 77 20  d, create a new 
1d10: 6f 6e 65 2e 20 2a 2f 0a 20 20 69 66 28 20 70 3d  one. */.  if( p=
1d20: 3d 30 20 29 7b 0a 20 20 20 20 2f 2a 20 46 69 67  =0 ){.    /* Fig
1d30: 75 72 65 20 6f 75 74 20 68 6f 77 20 6d 75 63 68  ure out how much
1d40: 20 73 70 61 63 65 20 74 6f 20 61 6c 6c 6f 63 61   space to alloca
1d50: 74 65 20 2a 2f 0a 20 20 20 20 63 68 61 72 20 2a  te */.    char *
1d60: 7a 4b 65 79 3b 0a 20 20 20 20 69 6e 74 20 6e 42  zKey;.    int nB
1d70: 79 74 65 20 3d 20 73 69 7a 65 6f 66 28 46 74 73  yte = sizeof(Fts
1d80: 35 48 61 73 68 45 6e 74 72 79 29 20 2b 20 28 6e  5HashEntry) + (n
1d90: 54 6f 6b 65 6e 2b 31 29 20 2b 20 31 20 2b 20 36  Token+1) + 1 + 6
1da0: 34 3b 0a 20 20 20 20 69 66 28 20 6e 42 79 74 65  4;.    if( nByte
1db0: 3c 31 32 38 20 29 20 6e 42 79 74 65 20 3d 20 31  <128 ) nByte = 1
1dc0: 32 38 3b 0a 0a 20 20 20 20 2f 2a 20 47 72 6f 77  28;..    /* Grow
1dd0: 20 74 68 65 20 46 74 73 35 48 61 73 68 2e 61 53   the Fts5Hash.aS
1de0: 6c 6f 74 5b 5d 20 61 72 72 61 79 20 69 66 20 6e  lot[] array if n
1df0: 65 63 65 73 73 61 72 79 2e 20 2a 2f 0a 20 20 20  ecessary. */.   
1e00: 20 69 66 28 20 28 70 48 61 73 68 2d 3e 6e 45 6e   if( (pHash->nEn
1e10: 74 72 79 2a 32 29 3e 3d 70 48 61 73 68 2d 3e 6e  try*2)>=pHash->n
1e20: 53 6c 6f 74 20 29 7b 0a 20 20 20 20 20 20 69 6e  Slot ){.      in
1e30: 74 20 72 63 20 3d 20 66 74 73 35 48 61 73 68 52  t rc = fts5HashR
1e40: 65 73 69 7a 65 28 70 48 61 73 68 29 3b 0a 20 20  esize(pHash);.  
1e50: 20 20 20 20 69 66 28 20 72 63 21 3d 53 51 4c 49      if( rc!=SQLI
1e60: 54 45 5f 4f 4b 20 29 20 72 65 74 75 72 6e 20 72  TE_OK ) return r
1e70: 63 3b 0a 20 20 20 20 20 20 69 48 61 73 68 20 3d  c;.      iHash =
1e80: 20 66 74 73 35 48 61 73 68 4b 65 79 32 28 70 48   fts5HashKey2(pH
1e90: 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20 28 75 38 29  ash->nSlot, (u8)
1ea0: 62 42 79 74 65 2c 20 28 63 6f 6e 73 74 20 75 38  bByte, (const u8
1eb0: 2a 29 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b 65 6e  *)pToken, nToken
1ec0: 29 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f 2a  );.    }..    /*
1ed0: 20 41 6c 6c 6f 63 61 74 65 20 6e 65 77 20 46 74   Allocate new Ft
1ee0: 73 35 48 61 73 68 45 6e 74 72 79 20 61 6e 64 20  s5HashEntry and 
1ef0: 61 64 64 20 69 74 20 74 6f 20 74 68 65 20 68 61  add it to the ha
1f00: 73 68 20 74 61 62 6c 65 2e 20 2a 2f 0a 20 20 20  sh table. */.   
1f10: 20 70 20 3d 20 28 46 74 73 35 48 61 73 68 45 6e   p = (Fts5HashEn
1f20: 74 72 79 2a 29 73 71 6c 69 74 65 33 5f 6d 61 6c  try*)sqlite3_mal
1f30: 6c 6f 63 28 6e 42 79 74 65 29 3b 0a 20 20 20 20  loc(nByte);.    
1f40: 69 66 28 20 21 70 20 29 20 72 65 74 75 72 6e 20  if( !p ) return 
1f50: 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20  SQLITE_NOMEM;.  
1f60: 20 20 6d 65 6d 73 65 74 28 70 2c 20 30 2c 20 73    memset(p, 0, s
1f70: 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e  izeof(Fts5HashEn
1f80: 74 72 79 29 29 3b 0a 20 20 20 20 70 2d 3e 6e 41  try));.    p->nA
1f90: 6c 6c 6f 63 20 3d 20 6e 42 79 74 65 3b 0a 20 20  lloc = nByte;.  
1fa0: 20 20 7a 4b 65 79 20 3d 20 66 74 73 35 45 6e 74    zKey = fts5Ent
1fb0: 72 79 4b 65 79 28 70 29 3b 0a 20 20 20 20 7a 4b  ryKey(p);.    zK
1fc0: 65 79 5b 30 5d 20 3d 20 62 42 79 74 65 3b 0a 20  ey[0] = bByte;. 
1fd0: 20 20 20 6d 65 6d 63 70 79 28 26 7a 4b 65 79 5b     memcpy(&zKey[
1fe0: 31 5d 2c 20 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b  1], pToken, nTok
1ff0: 65 6e 29 3b 0a 20 20 20 20 61 73 73 65 72 74 28  en);.    assert(
2000: 20 69 48 61 73 68 3d 3d 66 74 73 35 48 61 73 68   iHash==fts5Hash
2010: 4b 65 79 28 70 48 61 73 68 2d 3e 6e 53 6c 6f 74  Key(pHash->nSlot
2020: 2c 20 28 75 38 2a 29 7a 4b 65 79 2c 20 6e 54 6f  , (u8*)zKey, nTo
2030: 6b 65 6e 2b 31 29 20 29 3b 0a 20 20 20 20 70 2d  ken+1) );.    p-
2040: 3e 6e 4b 65 79 20 3d 20 6e 54 6f 6b 65 6e 3b 0a  >nKey = nToken;.
2050: 20 20 20 20 7a 4b 65 79 5b 6e 54 6f 6b 65 6e 2b      zKey[nToken+
2060: 31 5d 20 3d 20 27 5c 30 27 3b 0a 20 20 20 20 70  1] = '\0';.    p
2070: 2d 3e 6e 44 61 74 61 20 3d 20 6e 54 6f 6b 65 6e  ->nData = nToken
2080: 2b 31 20 2b 20 31 20 2b 20 73 69 7a 65 6f 66 28  +1 + 1 + sizeof(
2090: 46 74 73 35 48 61 73 68 45 6e 74 72 79 29 3b 0a  Fts5HashEntry);.
20a0: 20 20 20 20 70 2d 3e 70 48 61 73 68 4e 65 78 74      p->pHashNext
20b0: 20 3d 20 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b   = pHash->aSlot[
20c0: 69 48 61 73 68 5d 3b 0a 20 20 20 20 70 48 61 73  iHash];.    pHas
20d0: 68 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d 20  h->aSlot[iHash] 
20e0: 3d 20 70 3b 0a 20 20 20 20 70 48 61 73 68 2d 3e  = p;.    pHash->
20f0: 6e 45 6e 74 72 79 2b 2b 3b 0a 0a 20 20 20 20 2f  nEntry++;..    /
2100: 2a 20 41 64 64 20 74 68 65 20 66 69 72 73 74 20  * Add the first 
2110: 72 6f 77 69 64 20 66 69 65 6c 64 20 74 6f 20 74  rowid field to t
2120: 68 65 20 68 61 73 68 2d 65 6e 74 72 79 20 2a 2f  he hash-entry */
2130: 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d  .    p->nData +=
2140: 20 73 71 6c 69 74 65 33 46 74 73 35 50 75 74 56   sqlite3Fts5PutV
2150: 61 72 69 6e 74 28 26 28 28 75 38 2a 29 70 29 5b  arint(&((u8*)p)[
2160: 70 2d 3e 6e 44 61 74 61 5d 2c 20 69 52 6f 77 69  p->nData], iRowi
2170: 64 29 3b 0a 20 20 20 20 70 2d 3e 69 52 6f 77 69  d);.    p->iRowi
2180: 64 20 3d 20 69 52 6f 77 69 64 3b 0a 0a 20 20 20  d = iRowid;..   
2190: 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 3d   p->iSzPoslist =
21a0: 20 70 2d 3e 6e 44 61 74 61 3b 0a 20 20 20 20 69   p->nData;.    i
21b0: 66 28 20 70 48 61 73 68 2d 3e 65 44 65 74 61 69  f( pHash->eDetai
21c0: 6c 21 3d 46 54 53 35 5f 44 45 54 41 49 4c 5f 4e  l!=FTS5_DETAIL_N
21d0: 4f 4e 45 20 29 7b 0a 20 20 20 20 20 20 70 2d 3e  ONE ){.      p->
21e0: 6e 44 61 74 61 20 2b 3d 20 31 3b 0a 20 20 20 20  nData += 1;.    
21f0: 20 20 70 2d 3e 69 43 6f 6c 20 3d 20 28 70 48 61    p->iCol = (pHa
2200: 73 68 2d 3e 65 44 65 74 61 69 6c 3d 3d 46 54 53  sh->eDetail==FTS
2210: 35 5f 44 45 54 41 49 4c 5f 46 55 4c 4c 20 3f 20  5_DETAIL_FULL ? 
2220: 30 20 3a 20 2d 31 29 3b 0a 20 20 20 20 7d 0a 0a  0 : -1);.    }..
2230: 20 20 20 20 6e 49 6e 63 72 20 2b 3d 20 70 2d 3e      nIncr += p->
2240: 6e 44 61 74 61 3b 0a 20 20 7d 65 6c 73 65 7b 0a  nData;.  }else{.
2250: 0a 20 20 20 20 2f 2a 20 41 70 70 65 6e 64 69 6e  .    /* Appendin
2260: 67 20 74 6f 20 61 6e 20 65 78 69 73 74 69 6e 67  g to an existing
2270: 20 68 61 73 68 2d 65 6e 74 72 79 2e 20 43 68 65   hash-entry. Che
2280: 63 6b 20 74 68 61 74 20 74 68 65 72 65 20 69 73  ck that there is
2290: 20 65 6e 6f 75 67 68 20 0a 20 20 20 20 2a 2a 20   enough .    ** 
22a0: 73 70 61 63 65 20 74 6f 20 61 70 70 65 6e 64 20  space to append 
22b0: 74 68 65 20 6c 61 72 67 65 73 74 20 70 6f 73 73  the largest poss
22c0: 69 62 6c 65 20 6e 65 77 20 65 6e 74 72 79 2e 20  ible new entry. 
22d0: 57 6f 72 73 74 20 63 61 73 65 20 73 63 65 6e 61  Worst case scena
22e0: 72 69 6f 20 0a 20 20 20 20 2a 2a 20 69 73 3a 0a  rio .    ** is:.
22f0: 20 20 20 20 2a 2a 0a 20 20 20 20 2a 2a 20 20 20      **.    **   
2300: 20 20 2b 20 39 20 62 79 74 65 73 20 66 6f 72 20    + 9 bytes for 
2310: 61 20 6e 65 77 20 72 6f 77 69 64 2c 0a 20 20 20  a new rowid,.   
2320: 20 2a 2a 20 20 20 20 20 2b 20 34 20 62 79 74 65   **     + 4 byte
2330: 20 72 65 73 65 72 76 65 64 20 66 6f 72 20 74 68   reserved for th
2340: 65 20 22 70 6f 73 6c 69 73 74 20 73 69 7a 65 22  e "poslist size"
2350: 20 76 61 72 69 6e 74 2e 0a 20 20 20 20 2a 2a 20   varint..    ** 
2360: 20 20 20 20 2b 20 31 20 62 79 74 65 20 66 6f 72      + 1 byte for
2370: 20 61 20 22 6e 65 77 20 63 6f 6c 75 6d 6e 22 20   a "new column" 
2380: 62 79 74 65 2c 0a 20 20 20 20 2a 2a 20 20 20 20  byte,.    **    
2390: 20 2b 20 33 20 62 79 74 65 73 20 66 6f 72 20 61   + 3 bytes for a
23a0: 20 6e 65 77 20 63 6f 6c 75 6d 6e 20 6e 75 6d 62   new column numb
23b0: 65 72 20 28 31 36 2d 62 69 74 20 6d 61 78 29 20  er (16-bit max) 
23c0: 61 73 20 61 20 76 61 72 69 6e 74 2c 0a 20 20 20  as a varint,.   
23d0: 20 2a 2a 20 20 20 20 20 2b 20 35 20 62 79 74 65   **     + 5 byte
23e0: 73 20 66 6f 72 20 74 68 65 20 6e 65 77 20 70 6f  s for the new po
23f0: 73 69 74 69 6f 6e 20 6f 66 66 73 65 74 20 28 33  sition offset (3
2400: 32 2d 62 69 74 20 6d 61 78 29 2e 0a 20 20 20 20  2-bit max)..    
2410: 2a 2f 0a 20 20 20 20 69 66 28 20 28 70 2d 3e 6e  */.    if( (p->n
2420: 41 6c 6c 6f 63 20 2d 20 70 2d 3e 6e 44 61 74 61  Alloc - p->nData
2430: 29 20 3c 20 28 39 20 2b 20 34 20 2b 20 31 20 2b  ) < (9 + 4 + 1 +
2440: 20 33 20 2b 20 35 29 20 29 7b 0a 20 20 20 20 20   3 + 5) ){.     
2450: 20 69 6e 74 20 6e 4e 65 77 20 3d 20 70 2d 3e 6e   int nNew = p->n
2460: 41 6c 6c 6f 63 20 2a 20 32 3b 0a 20 20 20 20 20  Alloc * 2;.     
2470: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
2480: 70 4e 65 77 3b 0a 20 20 20 20 20 20 46 74 73 35  pNew;.      Fts5
2490: 48 61 73 68 45 6e 74 72 79 20 2a 2a 70 70 3b 0a  HashEntry **pp;.
24a0: 20 20 20 20 20 20 70 4e 65 77 20 3d 20 28 46 74        pNew = (Ft
24b0: 73 35 48 61 73 68 45 6e 74 72 79 2a 29 73 71 6c  s5HashEntry*)sql
24c0: 69 74 65 33 5f 72 65 61 6c 6c 6f 63 28 70 2c 20  ite3_realloc(p, 
24d0: 6e 4e 65 77 29 3b 0a 20 20 20 20 20 20 69 66 28  nNew);.      if(
24e0: 20 70 4e 65 77 3d 3d 30 20 29 20 72 65 74 75 72   pNew==0 ) retur
24f0: 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a  n SQLITE_NOMEM;.
2500: 20 20 20 20 20 20 70 4e 65 77 2d 3e 6e 41 6c 6c        pNew->nAll
2510: 6f 63 20 3d 20 6e 4e 65 77 3b 0a 20 20 20 20 20  oc = nNew;.     
2520: 20 66 6f 72 28 70 70 3d 26 70 48 61 73 68 2d 3e   for(pp=&pHash->
2530: 61 53 6c 6f 74 5b 69 48 61 73 68 5d 3b 20 2a 70  aSlot[iHash]; *p
2540: 70 21 3d 70 3b 20 70 70 3d 26 28 2a 70 70 29 2d  p!=p; pp=&(*pp)-
2550: 3e 70 48 61 73 68 4e 65 78 74 29 3b 0a 20 20 20  >pHashNext);.   
2560: 20 20 20 2a 70 70 20 3d 20 70 4e 65 77 3b 0a 20     *pp = pNew;. 
2570: 20 20 20 20 20 70 20 3d 20 70 4e 65 77 3b 0a 20       p = pNew;. 
2580: 20 20 20 7d 0a 20 20 20 20 6e 49 6e 63 72 20 2d     }.    nIncr -
2590: 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20 20 7d 0a  = p->nData;.  }.
25a0: 20 20 61 73 73 65 72 74 28 20 28 70 2d 3e 6e 41    assert( (p->nA
25b0: 6c 6c 6f 63 20 2d 20 70 2d 3e 6e 44 61 74 61 29  lloc - p->nData)
25c0: 20 3e 3d 20 28 39 20 2b 20 34 20 2b 20 31 20 2b   >= (9 + 4 + 1 +
25d0: 20 33 20 2b 20 35 29 20 29 3b 0a 0a 20 20 70 50   3 + 5) );..  pP
25e0: 74 72 20 3d 20 28 75 38 2a 29 70 3b 0a 0a 20 20  tr = (u8*)p;..  
25f0: 2f 2a 20 49 66 20 74 68 69 73 20 69 73 20 61 20  /* If this is a 
2600: 6e 65 77 20 72 6f 77 69 64 2c 20 61 70 70 65 6e  new rowid, appen
2610: 64 20 74 68 65 20 34 2d 62 79 74 65 20 73 69 7a  d the 4-byte siz
2620: 65 20 66 69 65 6c 64 20 66 6f 72 20 74 68 65 20  e field for the 
2630: 70 72 65 76 69 6f 75 73 0a 20 20 2a 2a 20 65 6e  previous.  ** en
2640: 74 72 79 2c 20 61 6e 64 20 74 68 65 20 6e 65 77  try, and the new
2650: 20 72 6f 77 69 64 20 66 6f 72 20 74 68 69 73 20   rowid for this 
2660: 65 6e 74 72 79 2e 20 20 2a 2f 0a 20 20 69 66 28  entry.  */.  if(
2670: 20 69 52 6f 77 69 64 21 3d 70 2d 3e 69 52 6f 77   iRowid!=p->iRow
2680: 69 64 20 29 7b 0a 20 20 20 20 66 74 73 35 48 61  id ){.    fts5Ha
2690: 73 68 41 64 64 50 6f 73 6c 69 73 74 53 69 7a 65  shAddPoslistSize
26a0: 28 70 48 61 73 68 2c 20 70 29 3b 0a 20 20 20 20  (pHash, p);.    
26b0: 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69  p->nData += sqli
26c0: 74 65 33 46 74 73 35 50 75 74 56 61 72 69 6e 74  te3Fts5PutVarint
26d0: 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61 5d  (&pPtr[p->nData]
26e0: 2c 20 69 52 6f 77 69 64 20 2d 20 70 2d 3e 69 52  , iRowid - p->iR
26f0: 6f 77 69 64 29 3b 0a 20 20 20 20 70 2d 3e 69 52  owid);.    p->iR
2700: 6f 77 69 64 20 3d 20 69 52 6f 77 69 64 3b 0a 20  owid = iRowid;. 
2710: 20 20 20 62 4e 65 77 20 3d 20 31 3b 0a 20 20 20     bNew = 1;.   
2720: 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 3d   p->iSzPoslist =
2730: 20 70 2d 3e 6e 44 61 74 61 3b 0a 20 20 20 20 69   p->nData;.    i
2740: 66 28 20 70 48 61 73 68 2d 3e 65 44 65 74 61 69  f( pHash->eDetai
2750: 6c 21 3d 46 54 53 35 5f 44 45 54 41 49 4c 5f 4e  l!=FTS5_DETAIL_N
2760: 4f 4e 45 20 29 7b 0a 20 20 20 20 20 20 70 2d 3e  ONE ){.      p->
2770: 6e 44 61 74 61 20 2b 3d 20 31 3b 0a 20 20 20 20  nData += 1;.    
2780: 20 20 70 2d 3e 69 43 6f 6c 20 3d 20 28 70 48 61    p->iCol = (pHa
2790: 73 68 2d 3e 65 44 65 74 61 69 6c 3d 3d 46 54 53  sh->eDetail==FTS
27a0: 35 5f 44 45 54 41 49 4c 5f 46 55 4c 4c 20 3f 20  5_DETAIL_FULL ? 
27b0: 30 20 3a 20 2d 31 29 3b 0a 20 20 20 20 20 20 70  0 : -1);.      p
27c0: 2d 3e 69 50 6f 73 20 3d 20 30 3b 0a 20 20 20 20  ->iPos = 0;.    
27d0: 7d 0a 20 20 7d 0a 0a 20 20 69 66 28 20 69 43 6f  }.  }..  if( iCo
27e0: 6c 3e 3d 30 20 29 7b 0a 20 20 20 20 69 66 28 20  l>=0 ){.    if( 
27f0: 70 48 61 73 68 2d 3e 65 44 65 74 61 69 6c 3d 3d  pHash->eDetail==
2800: 46 54 53 35 5f 44 45 54 41 49 4c 5f 4e 4f 4e 45  FTS5_DETAIL_NONE
2810: 20 29 7b 0a 20 20 20 20 20 20 70 2d 3e 62 43 6f   ){.      p->bCo
2820: 6e 74 65 6e 74 20 3d 20 31 3b 0a 20 20 20 20 7d  ntent = 1;.    }
2830: 65 6c 73 65 7b 0a 20 20 20 20 20 20 2f 2a 20 41  else{.      /* A
2840: 70 70 65 6e 64 20 61 20 6e 65 77 20 63 6f 6c 75  ppend a new colu
2850: 6d 6e 20 76 61 6c 75 65 2c 20 69 66 20 6e 65 63  mn value, if nec
2860: 65 73 73 61 72 79 20 2a 2f 0a 20 20 20 20 20 20  essary */.      
2870: 61 73 73 65 72 74 28 20 69 43 6f 6c 3e 3d 70 2d  assert( iCol>=p-
2880: 3e 69 43 6f 6c 20 29 3b 0a 20 20 20 20 20 20 69  >iCol );.      i
2890: 66 28 20 69 43 6f 6c 21 3d 70 2d 3e 69 43 6f 6c  f( iCol!=p->iCol
28a0: 20 29 7b 0a 20 20 20 20 20 20 20 20 69 66 28 20   ){.        if( 
28b0: 70 48 61 73 68 2d 3e 65 44 65 74 61 69 6c 3d 3d  pHash->eDetail==
28c0: 46 54 53 35 5f 44 45 54 41 49 4c 5f 46 55 4c 4c  FTS5_DETAIL_FULL
28d0: 20 29 7b 0a 20 20 20 20 20 20 20 20 20 20 70 50   ){.          pP
28e0: 74 72 5b 70 2d 3e 6e 44 61 74 61 2b 2b 5d 20 3d  tr[p->nData++] =
28f0: 20 30 78 30 31 3b 0a 20 20 20 20 20 20 20 20 20   0x01;.         
2900: 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71 6c   p->nData += sql
2910: 69 74 65 33 46 74 73 35 50 75 74 56 61 72 69 6e  ite3Fts5PutVarin
2920: 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61  t(&pPtr[p->nData
2930: 5d 2c 20 69 43 6f 6c 29 3b 0a 20 20 20 20 20 20  ], iCol);.      
2940: 20 20 20 20 70 2d 3e 69 43 6f 6c 20 3d 20 28 69      p->iCol = (i
2950: 31 36 29 69 43 6f 6c 3b 0a 20 20 20 20 20 20 20  16)iCol;.       
2960: 20 20 20 70 2d 3e 69 50 6f 73 20 3d 20 30 3b 0a     p->iPos = 0;.
2970: 20 20 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20          }else{. 
2980: 20 20 20 20 20 20 20 20 20 62 4e 65 77 20 3d 20           bNew = 
2990: 31 3b 0a 20 20 20 20 20 20 20 20 20 20 70 2d 3e  1;.          p->
29a0: 69 43 6f 6c 20 3d 20 28 69 31 36 29 28 69 50 6f  iCol = (i16)(iPo
29b0: 73 20 3d 20 69 43 6f 6c 29 3b 0a 20 20 20 20 20  s = iCol);.     
29c0: 20 20 20 7d 0a 20 20 20 20 20 20 7d 0a 0a 20 20     }.      }..  
29d0: 20 20 20 20 2f 2a 20 41 70 70 65 6e 64 20 74 68      /* Append th
29e0: 65 20 6e 65 77 20 70 6f 73 69 74 69 6f 6e 20 6f  e new position o
29f0: 66 66 73 65 74 2c 20 69 66 20 6e 65 63 65 73 73  ffset, if necess
2a00: 61 72 79 20 2a 2f 0a 20 20 20 20 20 20 69 66 28  ary */.      if(
2a10: 20 62 4e 65 77 20 29 7b 0a 20 20 20 20 20 20 20   bNew ){.       
2a20: 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71 6c   p->nData += sql
2a30: 69 74 65 33 46 74 73 35 50 75 74 56 61 72 69 6e  ite3Fts5PutVarin
2a40: 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61  t(&pPtr[p->nData
2a50: 5d 2c 20 69 50 6f 73 20 2d 20 70 2d 3e 69 50 6f  ], iPos - p->iPo
2a60: 73 20 2b 20 32 29 3b 0a 20 20 20 20 20 20 20 20  s + 2);.        
2a70: 70 2d 3e 69 50 6f 73 20 3d 20 69 50 6f 73 3b 0a  p->iPos = iPos;.
2a80: 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20        }.    }.  
2a90: 7d 65 6c 73 65 7b 0a 20 20 20 20 2f 2a 20 54 68  }else{.    /* Th
2aa0: 69 73 20 69 73 20 61 20 64 65 6c 65 74 65 2e 20  is is a delete. 
2ab0: 53 65 74 20 74 68 65 20 64 65 6c 65 74 65 20 66  Set the delete f
2ac0: 6c 61 67 2e 20 2a 2f 0a 20 20 20 20 70 2d 3e 62  lag. */.    p->b
2ad0: 44 65 6c 20 3d 20 31 3b 0a 20 20 7d 0a 0a 20 20  Del = 1;.  }..  
2ae0: 6e 49 6e 63 72 20 2b 3d 20 70 2d 3e 6e 44 61 74  nIncr += p->nDat
2af0: 61 3b 0a 20 20 2a 70 48 61 73 68 2d 3e 70 6e 42  a;.  *pHash->pnB
2b00: 79 74 65 20 2b 3d 20 6e 49 6e 63 72 3b 0a 20 20  yte += nIncr;.  
2b10: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b  return SQLITE_OK
2b20: 3b 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a 20 41 72 67 75  ;.}.../*.** Argu
2b30: 6d 65 6e 74 73 20 70 4c 65 66 74 20 61 6e 64 20  ments pLeft and 
2b40: 70 52 69 67 68 74 20 70 6f 69 6e 74 20 74 6f 20  pRight point to 
2b50: 6c 69 6e 6b 65 64 2d 6c 69 73 74 73 20 6f 66 20  linked-lists of 
2b60: 68 61 73 68 2d 65 6e 74 72 79 20 6f 62 6a 65 63  hash-entry objec
2b70: 74 73 2c 0a 2a 2a 20 65 61 63 68 20 73 6f 72 74  ts,.** each sort
2b80: 65 64 20 69 6e 20 6b 65 79 20 6f 72 64 65 72 2e  ed in key order.
2b90: 20 54 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 6d   This function m
2ba0: 65 72 67 65 73 20 74 68 65 20 74 77 6f 20 6c 69  erges the two li
2bb0: 73 74 73 20 69 6e 74 6f 20 61 0a 2a 2a 20 73 69  sts into a.** si
2bc0: 6e 67 6c 65 20 6c 69 73 74 20 61 6e 64 20 72 65  ngle list and re
2bd0: 74 75 72 6e 73 20 61 20 70 6f 69 6e 74 65 72 20  turns a pointer 
2be0: 74 6f 20 69 74 73 20 66 69 72 73 74 20 65 6c 65  to its first ele
2bf0: 6d 65 6e 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 20  ment..*/.static 
2c00: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 66  Fts5HashEntry *f
2c10: 74 73 35 48 61 73 68 45 6e 74 72 79 4d 65 72 67  ts5HashEntryMerg
2c20: 65 28 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74  e(.  Fts5HashEnt
2c30: 72 79 20 2a 70 4c 65 66 74 2c 0a 20 20 46 74 73  ry *pLeft,.  Fts
2c40: 35 48 61 73 68 45 6e 74 72 79 20 2a 70 52 69 67  5HashEntry *pRig
2c50: 68 74 0a 29 7b 0a 20 20 46 74 73 35 48 61 73 68  ht.){.  Fts5Hash
2c60: 45 6e 74 72 79 20 2a 70 31 20 3d 20 70 4c 65 66  Entry *p1 = pLef
2c70: 74 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74  t;.  Fts5HashEnt
2c80: 72 79 20 2a 70 32 20 3d 20 70 52 69 67 68 74 3b  ry *p2 = pRight;
2c90: 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  .  Fts5HashEntry
2ca0: 20 2a 70 52 65 74 20 3d 20 30 3b 0a 20 20 46 74   *pRet = 0;.  Ft
2cb0: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 70 70  s5HashEntry **pp
2cc0: 4f 75 74 20 3d 20 26 70 52 65 74 3b 0a 0a 20 20  Out = &pRet;..  
2cd0: 77 68 69 6c 65 28 20 70 31 20 7c 7c 20 70 32 20  while( p1 || p2 
2ce0: 29 7b 0a 20 20 20 20 69 66 28 20 70 31 3d 3d 30  ){.    if( p1==0
2cf0: 20 29 7b 0a 20 20 20 20 20 20 2a 70 70 4f 75 74   ){.      *ppOut
2d00: 20 3d 20 70 32 3b 0a 20 20 20 20 20 20 70 32 20   = p2;.      p2 
2d10: 3d 20 30 3b 0a 20 20 20 20 7d 65 6c 73 65 20 69  = 0;.    }else i
2d20: 66 28 20 70 32 3d 3d 30 20 29 7b 0a 20 20 20 20  f( p2==0 ){.    
2d30: 20 20 2a 70 70 4f 75 74 20 3d 20 70 31 3b 0a 20    *ppOut = p1;. 
2d40: 20 20 20 20 20 70 31 20 3d 20 30 3b 0a 20 20 20       p1 = 0;.   
2d50: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 69 6e   }else{.      in
2d60: 74 20 69 20 3d 20 30 3b 0a 20 20 20 20 20 20 63  t i = 0;.      c
2d70: 68 61 72 20 2a 7a 4b 65 79 31 20 3d 20 66 74 73  har *zKey1 = fts
2d80: 35 45 6e 74 72 79 4b 65 79 28 70 31 29 3b 0a 20  5EntryKey(p1);. 
2d90: 20 20 20 20 20 63 68 61 72 20 2a 7a 4b 65 79 32       char *zKey2
2da0: 20 3d 20 66 74 73 35 45 6e 74 72 79 4b 65 79 28   = fts5EntryKey(
2db0: 70 32 29 3b 0a 20 20 20 20 20 20 77 68 69 6c 65  p2);.      while
2dc0: 28 20 7a 4b 65 79 31 5b 69 5d 3d 3d 7a 4b 65 79  ( zKey1[i]==zKey
2dd0: 32 5b 69 5d 20 29 20 69 2b 2b 3b 0a 0a 20 20 20  2[i] ) i++;..   
2de0: 20 20 20 69 66 28 20 28 28 75 38 29 7a 4b 65 79     if( ((u8)zKey
2df0: 31 5b 69 5d 29 3e 28 28 75 38 29 7a 4b 65 79 32  1[i])>((u8)zKey2
2e00: 5b 69 5d 29 20 29 7b 0a 20 20 20 20 20 20 20 20  [i]) ){.        
2e10: 2f 2a 20 70 32 20 69 73 20 73 6d 61 6c 6c 65 72  /* p2 is smaller
2e20: 20 2a 2f 0a 20 20 20 20 20 20 20 20 2a 70 70 4f   */.        *ppO
2e30: 75 74 20 3d 20 70 32 3b 0a 20 20 20 20 20 20 20  ut = p2;.       
2e40: 20 70 70 4f 75 74 20 3d 20 26 70 32 2d 3e 70 53   ppOut = &p2->pS
2e50: 63 61 6e 4e 65 78 74 3b 0a 20 20 20 20 20 20 20  canNext;.       
2e60: 20 70 32 20 3d 20 70 32 2d 3e 70 53 63 61 6e 4e   p2 = p2->pScanN
2e70: 65 78 74 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65  ext;.      }else
2e80: 7b 0a 20 20 20 20 20 20 20 20 2f 2a 20 70 31 20  {.        /* p1 
2e90: 69 73 20 73 6d 61 6c 6c 65 72 20 2a 2f 0a 20 20  is smaller */.  
2ea0: 20 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 70        *ppOut = p
2eb0: 31 3b 0a 20 20 20 20 20 20 20 20 70 70 4f 75 74  1;.        ppOut
2ec0: 20 3d 20 26 70 31 2d 3e 70 53 63 61 6e 4e 65 78   = &p1->pScanNex
2ed0: 74 3b 0a 20 20 20 20 20 20 20 20 70 31 20 3d 20  t;.        p1 = 
2ee0: 70 31 2d 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 20  p1->pScanNext;. 
2ef0: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 2a 70 70       }.      *pp
2f00: 4f 75 74 20 3d 20 30 3b 0a 20 20 20 20 7d 0a 20  Out = 0;.    }. 
2f10: 20 7d 0a 0a 20 20 72 65 74 75 72 6e 20 70 52 65   }..  return pRe
2f20: 74 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 45 78 74 72  t;.}../*.** Extr
2f30: 61 63 74 20 61 6c 6c 20 74 6f 6b 65 6e 73 20 66  act all tokens f
2f40: 72 6f 6d 20 68 61 73 68 20 74 61 62 6c 65 20 69  rom hash table i
2f50: 48 61 73 68 20 61 6e 64 20 6c 69 6e 6b 20 74 68  Hash and link th
2f60: 65 6d 20 69 6e 74 6f 20 61 20 6c 69 73 74 0a 2a  em into a list.*
2f70: 2a 20 69 6e 20 73 6f 72 74 65 64 20 6f 72 64 65  * in sorted orde
2f80: 72 2e 20 54 68 65 20 68 61 73 68 20 74 61 62 6c  r. The hash tabl
2f90: 65 20 69 73 20 63 6c 65 61 72 65 64 20 62 65 66  e is cleared bef
2fa0: 6f 72 65 20 72 65 74 75 72 6e 69 6e 67 2e 20 49  ore returning. I
2fb0: 74 20 69 73 0a 2a 2a 20 74 68 65 20 72 65 73 70  t is.** the resp
2fc0: 6f 6e 73 69 62 69 6c 69 74 79 20 6f 66 20 74 68  onsibility of th
2fd0: 65 20 63 61 6c 6c 65 72 20 74 6f 20 66 72 65 65  e caller to free
2fe0: 20 74 68 65 20 65 6c 65 6d 65 6e 74 73 20 6f 66   the elements of
2ff0: 20 74 68 65 20 72 65 74 75 72 6e 65 64 0a 2a 2a   the returned.**
3000: 20 6c 69 73 74 2e 0a 2a 2f 0a 73 74 61 74 69 63   list..*/.static
3010: 20 69 6e 74 20 66 74 73 35 48 61 73 68 45 6e 74   int fts5HashEnt
3020: 72 79 53 6f 72 74 28 0a 20 20 46 74 73 35 48 61  rySort(.  Fts5Ha
3030: 73 68 20 2a 70 48 61 73 68 2c 20 0a 20 20 63 6f  sh *pHash, .  co
3040: 6e 73 74 20 63 68 61 72 20 2a 70 54 65 72 6d 2c  nst char *pTerm,
3050: 20 69 6e 74 20 6e 54 65 72 6d 2c 20 20 20 2f 2a   int nTerm,   /*
3060: 20 51 75 65 72 79 20 70 72 65 66 69 78 2c 20 69   Query prefix, i
3070: 66 20 61 6e 79 20 2a 2f 0a 20 20 46 74 73 35 48  f any */.  Fts5H
3080: 61 73 68 45 6e 74 72 79 20 2a 2a 70 70 53 6f 72  ashEntry **ppSor
3090: 74 65 64 0a 29 7b 0a 20 20 63 6f 6e 73 74 20 69  ted.){.  const i
30a0: 6e 74 20 6e 4d 65 72 67 65 53 6c 6f 74 20 3d 20  nt nMergeSlot = 
30b0: 33 32 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e  32;.  Fts5HashEn
30c0: 74 72 79 20 2a 2a 61 70 3b 0a 20 20 46 74 73 35  try **ap;.  Fts5
30d0: 48 61 73 68 45 6e 74 72 79 20 2a 70 4c 69 73 74  HashEntry *pList
30e0: 3b 0a 20 20 69 6e 74 20 69 53 6c 6f 74 3b 0a 20  ;.  int iSlot;. 
30f0: 20 69 6e 74 20 69 3b 0a 0a 20 20 2a 70 70 53 6f   int i;..  *ppSo
3100: 72 74 65 64 20 3d 20 30 3b 0a 20 20 61 70 20 3d  rted = 0;.  ap =
3110: 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28   sqlite3_malloc(
3120: 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45  sizeof(Fts5HashE
3130: 6e 74 72 79 2a 29 20 2a 20 6e 4d 65 72 67 65 53  ntry*) * nMergeS
3140: 6c 6f 74 29 3b 0a 20 20 69 66 28 20 21 61 70 20  lot);.  if( !ap 
3150: 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f  ) return SQLITE_
3160: 4e 4f 4d 45 4d 3b 0a 20 20 6d 65 6d 73 65 74 28  NOMEM;.  memset(
3170: 61 70 2c 20 30 2c 20 73 69 7a 65 6f 66 28 46 74  ap, 0, sizeof(Ft
3180: 73 35 48 61 73 68 45 6e 74 72 79 2a 29 20 2a 20  s5HashEntry*) * 
3190: 6e 4d 65 72 67 65 53 6c 6f 74 29 3b 0a 0a 20 20  nMergeSlot);..  
31a0: 66 6f 72 28 69 53 6c 6f 74 3d 30 3b 20 69 53 6c  for(iSlot=0; iSl
31b0: 6f 74 3c 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 3b  ot<pHash->nSlot;
31c0: 20 69 53 6c 6f 74 2b 2b 29 7b 0a 20 20 20 20 46   iSlot++){.    F
31d0: 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 49  ts5HashEntry *pI
31e0: 74 65 72 3b 0a 20 20 20 20 66 6f 72 28 70 49 74  ter;.    for(pIt
31f0: 65 72 3d 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b  er=pHash->aSlot[
3200: 69 53 6c 6f 74 5d 3b 20 70 49 74 65 72 3b 20 70  iSlot]; pIter; p
3210: 49 74 65 72 3d 70 49 74 65 72 2d 3e 70 48 61 73  Iter=pIter->pHas
3220: 68 4e 65 78 74 29 7b 0a 20 20 20 20 20 20 69 66  hNext){.      if
3230: 28 20 70 54 65 72 6d 3d 3d 30 20 7c 7c 20 30 3d  ( pTerm==0 || 0=
3240: 3d 6d 65 6d 63 6d 70 28 66 74 73 35 45 6e 74 72  =memcmp(fts5Entr
3250: 79 4b 65 79 28 70 49 74 65 72 29 2c 20 70 54 65  yKey(pIter), pTe
3260: 72 6d 2c 20 6e 54 65 72 6d 29 20 29 7b 0a 20 20  rm, nTerm) ){.  
3270: 20 20 20 20 20 20 46 74 73 35 48 61 73 68 45 6e        Fts5HashEn
3280: 74 72 79 20 2a 70 45 6e 74 72 79 20 3d 20 70 49  try *pEntry = pI
3290: 74 65 72 3b 0a 20 20 20 20 20 20 20 20 70 45 6e  ter;.        pEn
32a0: 74 72 79 2d 3e 70 53 63 61 6e 4e 65 78 74 20 3d  try->pScanNext =
32b0: 20 30 3b 0a 20 20 20 20 20 20 20 20 66 6f 72 28   0;.        for(
32c0: 69 3d 30 3b 20 61 70 5b 69 5d 3b 20 69 2b 2b 29  i=0; ap[i]; i++)
32d0: 7b 0a 20 20 20 20 20 20 20 20 20 20 70 45 6e 74  {.          pEnt
32e0: 72 79 20 3d 20 66 74 73 35 48 61 73 68 45 6e 74  ry = fts5HashEnt
32f0: 72 79 4d 65 72 67 65 28 70 45 6e 74 72 79 2c 20  ryMerge(pEntry, 
3300: 61 70 5b 69 5d 29 3b 0a 20 20 20 20 20 20 20 20  ap[i]);.        
3310: 20 20 61 70 5b 69 5d 20 3d 20 30 3b 0a 20 20 20    ap[i] = 0;.   
3320: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 61       }.        a
3330: 70 5b 69 5d 20 3d 20 70 45 6e 74 72 79 3b 0a 20  p[i] = pEntry;. 
3340: 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 7d       }.    }.  }
3350: 0a 0a 20 20 70 4c 69 73 74 20 3d 20 30 3b 0a 20  ..  pList = 0;. 
3360: 20 66 6f 72 28 69 3d 30 3b 20 69 3c 6e 4d 65 72   for(i=0; i<nMer
3370: 67 65 53 6c 6f 74 3b 20 69 2b 2b 29 7b 0a 20 20  geSlot; i++){.  
3380: 20 20 70 4c 69 73 74 20 3d 20 66 74 73 35 48 61    pList = fts5Ha
3390: 73 68 45 6e 74 72 79 4d 65 72 67 65 28 70 4c 69  shEntryMerge(pLi
33a0: 73 74 2c 20 61 70 5b 69 5d 29 3b 0a 20 20 7d 0a  st, ap[i]);.  }.
33b0: 0a 20 20 70 48 61 73 68 2d 3e 6e 45 6e 74 72 79  .  pHash->nEntry
33c0: 20 3d 20 30 3b 0a 20 20 73 71 6c 69 74 65 33 5f   = 0;.  sqlite3_
33d0: 66 72 65 65 28 61 70 29 3b 0a 20 20 2a 70 70 53  free(ap);.  *ppS
33e0: 6f 72 74 65 64 20 3d 20 70 4c 69 73 74 3b 0a 20  orted = pList;. 
33f0: 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f   return SQLITE_O
3400: 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 51 75 65 72  K;.}../*.** Quer
3410: 79 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65  y the hash table
3420: 20 66 6f 72 20 61 20 64 6f 63 6c 69 73 74 20 61   for a doclist a
3430: 73 73 6f 63 69 61 74 65 64 20 77 69 74 68 20 74  ssociated with t
3440: 65 72 6d 20 70 54 65 72 6d 2f 6e 54 65 72 6d 2e  erm pTerm/nTerm.
3450: 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 46  .*/.int sqlite3F
3460: 74 73 35 48 61 73 68 51 75 65 72 79 28 0a 20 20  ts5HashQuery(.  
3470: 46 74 73 35 48 61 73 68 20 2a 70 48 61 73 68 2c  Fts5Hash *pHash,
3480: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3490: 2f 2a 20 48 61 73 68 20 74 61 62 6c 65 20 74 6f  /* Hash table to
34a0: 20 71 75 65 72 79 20 2a 2f 0a 20 20 63 6f 6e 73   query */.  cons
34b0: 74 20 63 68 61 72 20 2a 70 54 65 72 6d 2c 20 69  t char *pTerm, i
34c0: 6e 74 20 6e 54 65 72 6d 2c 20 20 20 2f 2a 20 51  nt nTerm,   /* Q
34d0: 75 65 72 79 20 74 65 72 6d 20 2a 2f 0a 20 20 63  uery term */.  c
34e0: 6f 6e 73 74 20 75 38 20 2a 2a 70 70 44 6f 63 6c  onst u8 **ppDocl
34f0: 69 73 74 2c 20 20 20 20 20 20 20 20 20 20 20 2f  ist,           /
3500: 2a 20 4f 55 54 3a 20 50 6f 69 6e 74 65 72 20 74  * OUT: Pointer t
3510: 6f 20 64 6f 63 6c 69 73 74 20 66 6f 72 20 70 54  o doclist for pT
3520: 65 72 6d 20 2a 2f 0a 20 20 69 6e 74 20 2a 70 6e  erm */.  int *pn
3530: 44 6f 63 6c 69 73 74 20 20 20 20 20 20 20 20 20  Doclist         
3540: 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 3a           /* OUT:
3550: 20 53 69 7a 65 20 6f 66 20 64 6f 63 6c 69 73 74   Size of doclist
3560: 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a 29 7b 0a   in bytes */.){.
3570: 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 69    unsigned int i
3580: 48 61 73 68 20 3d 20 66 74 73 35 48 61 73 68 4b  Hash = fts5HashK
3590: 65 79 28 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 2c  ey(pHash->nSlot,
35a0: 20 28 63 6f 6e 73 74 20 75 38 2a 29 70 54 65 72   (const u8*)pTer
35b0: 6d 2c 20 6e 54 65 72 6d 29 3b 0a 20 20 63 68 61  m, nTerm);.  cha
35c0: 72 20 2a 7a 4b 65 79 3b 0a 20 20 46 74 73 35 48  r *zKey;.  Fts5H
35d0: 61 73 68 45 6e 74 72 79 20 2a 70 3b 0a 0a 20 20  ashEntry *p;..  
35e0: 66 6f 72 28 70 3d 70 48 61 73 68 2d 3e 61 53 6c  for(p=pHash->aSl
35f0: 6f 74 5b 69 48 61 73 68 5d 3b 20 70 3b 20 70 3d  ot[iHash]; p; p=
3600: 70 2d 3e 70 48 61 73 68 4e 65 78 74 29 7b 0a 20  p->pHashNext){. 
3610: 20 20 20 7a 4b 65 79 20 3d 20 66 74 73 35 45 6e     zKey = fts5En
3620: 74 72 79 4b 65 79 28 70 29 3b 0a 20 20 20 20 69  tryKey(p);.    i
3630: 66 28 20 6d 65 6d 63 6d 70 28 7a 4b 65 79 2c 20  f( memcmp(zKey, 
3640: 70 54 65 72 6d 2c 20 6e 54 65 72 6d 29 3d 3d 30  pTerm, nTerm)==0
3650: 20 26 26 20 7a 4b 65 79 5b 6e 54 65 72 6d 5d 3d   && zKey[nTerm]=
3660: 3d 30 20 29 20 62 72 65 61 6b 3b 0a 20 20 7d 0a  =0 ) break;.  }.
3670: 0a 20 20 69 66 28 20 70 20 29 7b 0a 20 20 20 20  .  if( p ){.    
3680: 66 74 73 35 48 61 73 68 41 64 64 50 6f 73 6c 69  fts5HashAddPosli
3690: 73 74 53 69 7a 65 28 70 48 61 73 68 2c 20 70 29  stSize(pHash, p)
36a0: 3b 0a 20 20 20 20 2a 70 70 44 6f 63 6c 69 73 74  ;.    *ppDoclist
36b0: 20 3d 20 28 63 6f 6e 73 74 20 75 38 2a 29 26 7a   = (const u8*)&z
36c0: 4b 65 79 5b 6e 54 65 72 6d 2b 31 5d 3b 0a 20 20  Key[nTerm+1];.  
36d0: 20 20 2a 70 6e 44 6f 63 6c 69 73 74 20 3d 20 70    *pnDoclist = p
36e0: 2d 3e 6e 44 61 74 61 20 2d 20 28 73 69 7a 65 6f  ->nData - (sizeo
36f0: 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 29  f(Fts5HashEntry)
3700: 20 2b 20 6e 54 65 72 6d 20 2b 20 31 29 3b 0a 20   + nTerm + 1);. 
3710: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2a 70 70 44   }else{.    *ppD
3720: 6f 63 6c 69 73 74 20 3d 20 30 3b 0a 20 20 20 20  oclist = 0;.    
3730: 2a 70 6e 44 6f 63 6c 69 73 74 20 3d 20 30 3b 0a  *pnDoclist = 0;.
3740: 20 20 7d 0a 0a 20 20 72 65 74 75 72 6e 20 53 51    }..  return SQ
3750: 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 69 6e 74 20  LITE_OK;.}..int 
3760: 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 53  sqlite3Fts5HashS
3770: 63 61 6e 49 6e 69 74 28 0a 20 20 46 74 73 35 48  canInit(.  Fts5H
3780: 61 73 68 20 2a 70 2c 20 20 20 20 20 20 20 20 20  ash *p,         
3790: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 48 61             /* Ha
37a0: 73 68 20 74 61 62 6c 65 20 74 6f 20 71 75 65 72  sh table to quer
37b0: 79 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61  y */.  const cha
37c0: 72 20 2a 70 54 65 72 6d 2c 20 69 6e 74 20 6e 54  r *pTerm, int nT
37d0: 65 72 6d 20 20 20 20 2f 2a 20 51 75 65 72 79 20  erm    /* Query 
37e0: 70 72 65 66 69 78 20 2a 2f 0a 29 7b 0a 20 20 72  prefix */.){.  r
37f0: 65 74 75 72 6e 20 66 74 73 35 48 61 73 68 45 6e  eturn fts5HashEn
3800: 74 72 79 53 6f 72 74 28 70 2c 20 70 54 65 72 6d  trySort(p, pTerm
3810: 2c 20 6e 54 65 72 6d 2c 20 26 70 2d 3e 70 53 63  , nTerm, &p->pSc
3820: 61 6e 29 3b 0a 7d 0a 0a 76 6f 69 64 20 73 71 6c  an);.}..void sql
3830: 69 74 65 33 46 74 73 35 48 61 73 68 53 63 61 6e  ite3Fts5HashScan
3840: 4e 65 78 74 28 46 74 73 35 48 61 73 68 20 2a 70  Next(Fts5Hash *p
3850: 29 7b 0a 20 20 61 73 73 65 72 74 28 20 21 73 71  ){.  assert( !sq
3860: 6c 69 74 65 33 46 74 73 35 48 61 73 68 53 63 61  lite3Fts5HashSca
3870: 6e 45 6f 66 28 70 29 20 29 3b 0a 20 20 70 2d 3e  nEof(p) );.  p->
3880: 70 53 63 61 6e 20 3d 20 70 2d 3e 70 53 63 61 6e  pScan = p->pScan
3890: 2d 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 7d 0a 0a  ->pScanNext;.}..
38a0: 69 6e 74 20 73 71 6c 69 74 65 33 46 74 73 35 48  int sqlite3Fts5H
38b0: 61 73 68 53 63 61 6e 45 6f 66 28 46 74 73 35 48  ashScanEof(Fts5H
38c0: 61 73 68 20 2a 70 29 7b 0a 20 20 72 65 74 75 72  ash *p){.  retur
38d0: 6e 20 28 70 2d 3e 70 53 63 61 6e 3d 3d 30 29 3b  n (p->pScan==0);
38e0: 0a 7d 0a 0a 76 6f 69 64 20 73 71 6c 69 74 65 33  .}..void sqlite3
38f0: 46 74 73 35 48 61 73 68 53 63 61 6e 45 6e 74 72  Fts5HashScanEntr
3900: 79 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a 70  y(.  Fts5Hash *p
3910: 48 61 73 68 2c 0a 20 20 63 6f 6e 73 74 20 63 68  Hash,.  const ch
3920: 61 72 20 2a 2a 70 7a 54 65 72 6d 2c 20 20 20 20  ar **pzTerm,    
3930: 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20          /* OUT: 
3940: 74 65 72 6d 20 28 6e 75 6c 2d 74 65 72 6d 69 6e  term (nul-termin
3950: 61 74 65 64 29 20 2a 2f 0a 20 20 63 6f 6e 73 74  ated) */.  const
3960: 20 75 38 20 2a 2a 70 70 44 6f 63 6c 69 73 74 2c   u8 **ppDoclist,
3970: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55             /* OU
3980: 54 3a 20 70 6f 69 6e 74 65 72 20 74 6f 20 64 6f  T: pointer to do
3990: 63 6c 69 73 74 20 2a 2f 0a 20 20 69 6e 74 20 2a  clist */.  int *
39a0: 70 6e 44 6f 63 6c 69 73 74 20 20 20 20 20 20 20  pnDoclist       
39b0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55             /* OU
39c0: 54 3a 20 73 69 7a 65 20 6f 66 20 64 6f 63 6c 69  T: size of docli
39d0: 73 74 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a 29  st in bytes */.)
39e0: 7b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72  {.  Fts5HashEntr
39f0: 79 20 2a 70 3b 0a 20 20 69 66 28 20 28 70 20 3d  y *p;.  if( (p =
3a00: 20 70 48 61 73 68 2d 3e 70 53 63 61 6e 29 20 29   pHash->pScan) )
3a10: 7b 0a 20 20 20 20 63 68 61 72 20 2a 7a 4b 65 79  {.    char *zKey
3a20: 20 3d 20 66 74 73 35 45 6e 74 72 79 4b 65 79 28   = fts5EntryKey(
3a30: 70 29 3b 0a 20 20 20 20 69 6e 74 20 6e 54 65 72  p);.    int nTer
3a40: 6d 20 3d 20 28 69 6e 74 29 73 74 72 6c 65 6e 28  m = (int)strlen(
3a50: 7a 4b 65 79 29 3b 0a 20 20 20 20 66 74 73 35 48  zKey);.    fts5H
3a60: 61 73 68 41 64 64 50 6f 73 6c 69 73 74 53 69 7a  ashAddPoslistSiz
3a70: 65 28 70 48 61 73 68 2c 20 70 29 3b 0a 20 20 20  e(pHash, p);.   
3a80: 20 2a 70 7a 54 65 72 6d 20 3d 20 7a 4b 65 79 3b   *pzTerm = zKey;
3a90: 0a 20 20 20 20 2a 70 70 44 6f 63 6c 69 73 74 20  .    *ppDoclist 
3aa0: 3d 20 28 63 6f 6e 73 74 20 75 38 2a 29 26 7a 4b  = (const u8*)&zK
3ab0: 65 79 5b 6e 54 65 72 6d 2b 31 5d 3b 0a 20 20 20  ey[nTerm+1];.   
3ac0: 20 2a 70 6e 44 6f 63 6c 69 73 74 20 3d 20 70 2d   *pnDoclist = p-
3ad0: 3e 6e 44 61 74 61 20 2d 20 28 73 69 7a 65 6f 66  >nData - (sizeof
3ae0: 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 29 20  (Fts5HashEntry) 
3af0: 2b 20 6e 54 65 72 6d 20 2b 20 31 29 3b 0a 20 20  + nTerm + 1);.  
3b00: 7d 65 6c 73 65 7b 0a 20 20 20 20 2a 70 7a 54 65  }else{.    *pzTe
3b10: 72 6d 20 3d 20 30 3b 0a 20 20 20 20 2a 70 70 44  rm = 0;.    *ppD
3b20: 6f 63 6c 69 73 74 20 3d 20 30 3b 0a 20 20 20 20  oclist = 0;.    
3b30: 2a 70 6e 44 6f 63 6c 69 73 74 20 3d 20 30 3b 0a  *pnDoclist = 0;.
3b40: 20 20 7d 0a 7d 0a 0a                               }.}..