/ Hex Artifact Content
Login

Artifact c27852a632e3cacf40cd8262afbf019f32a3d67d948c27225ecdede6ab6ae3e7:


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 69 6e 74 20 66 74  }..static int ft
1490: 73 35 48 61 73 68 41 64 64 50 6f 73 6c 69 73 74  s5HashAddPoslist
14a0: 53 69 7a 65 28 0a 20 20 46 74 73 35 48 61 73 68  Size(.  Fts5Hash
14b0: 20 2a 70 48 61 73 68 2c 20 0a 20 20 46 74 73 35   *pHash, .  Fts5
14c0: 48 61 73 68 45 6e 74 72 79 20 2a 70 2c 0a 20 20  HashEntry *p,.  
14d0: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70  Fts5HashEntry *p
14e0: 32 0a 29 7b 0a 20 20 69 6e 74 20 6e 52 65 74 20  2.){.  int nRet 
14f0: 3d 20 30 3b 0a 20 20 69 66 28 20 70 2d 3e 69 53  = 0;.  if( p->iS
1500: 7a 50 6f 73 6c 69 73 74 20 29 7b 0a 20 20 20 20  zPoslist ){.    
1510: 75 38 20 2a 70 50 74 72 20 3d 20 70 32 20 3f 20  u8 *pPtr = p2 ? 
1520: 28 75 38 2a 29 70 32 20 3a 20 28 75 38 2a 29 70  (u8*)p2 : (u8*)p
1530: 3b 0a 20 20 20 20 69 6e 74 20 6e 44 61 74 61 20  ;.    int nData 
1540: 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20 20 20 20  = p->nData;.    
1550: 69 66 28 20 70 48 61 73 68 2d 3e 65 44 65 74 61  if( pHash->eDeta
1560: 69 6c 3d 3d 46 54 53 35 5f 44 45 54 41 49 4c 5f  il==FTS5_DETAIL_
1570: 4e 4f 4e 45 20 29 7b 0a 20 20 20 20 20 20 61 73  NONE ){.      as
1580: 73 65 72 74 28 20 6e 44 61 74 61 3d 3d 70 2d 3e  sert( nData==p->
1590: 69 53 7a 50 6f 73 6c 69 73 74 20 29 3b 0a 20 20  iSzPoslist );.  
15a0: 20 20 20 20 69 66 28 20 70 2d 3e 62 44 65 6c 20      if( p->bDel 
15b0: 29 7b 0a 20 20 20 20 20 20 20 20 70 50 74 72 5b  ){.        pPtr[
15c0: 6e 44 61 74 61 2b 2b 5d 20 3d 20 30 78 30 30 3b  nData++] = 0x00;
15d0: 0a 20 20 20 20 20 20 20 20 69 66 28 20 70 2d 3e  .        if( p->
15e0: 62 43 6f 6e 74 65 6e 74 20 29 7b 0a 20 20 20 20  bContent ){.    
15f0: 20 20 20 20 20 20 70 50 74 72 5b 6e 44 61 74 61        pPtr[nData
1600: 2b 2b 5d 20 3d 20 30 78 30 30 3b 0a 20 20 20 20  ++] = 0x00;.    
1610: 20 20 20 20 7d 0a 20 20 20 20 20 20 7d 0a 20 20      }.      }.  
1620: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 69    }else{.      i
1630: 6e 74 20 6e 53 7a 20 3d 20 28 6e 44 61 74 61 20  nt nSz = (nData 
1640: 2d 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20  - p->iSzPoslist 
1650: 2d 20 31 29 3b 20 20 20 20 20 20 20 2f 2a 20 53  - 1);       /* S
1660: 69 7a 65 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a  ize in bytes */.
1670: 20 20 20 20 20 20 69 6e 74 20 6e 50 6f 73 20 3d        int nPos =
1680: 20 6e 53 7a 2a 32 20 2b 20 70 2d 3e 62 44 65 6c   nSz*2 + p->bDel
1690: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
16a0: 20 20 20 20 20 20 2f 2a 20 56 61 6c 75 65 20 6f        /* Value o
16b0: 66 20 6e 50 6f 73 20 66 69 65 6c 64 20 2a 2f 0a  f nPos field */.
16c0: 0a 20 20 20 20 20 20 61 73 73 65 72 74 28 20 70  .      assert( p
16d0: 2d 3e 62 44 65 6c 3d 3d 30 20 7c 7c 20 70 2d 3e  ->bDel==0 || p->
16e0: 62 44 65 6c 3d 3d 31 20 29 3b 0a 20 20 20 20 20  bDel==1 );.     
16f0: 20 69 66 28 20 6e 50 6f 73 3c 3d 31 32 37 20 29   if( nPos<=127 )
1700: 7b 0a 20 20 20 20 20 20 20 20 70 50 74 72 5b 70  {.        pPtr[p
1710: 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 5d 20 3d 20  ->iSzPoslist] = 
1720: 28 75 38 29 6e 50 6f 73 3b 0a 20 20 20 20 20 20  (u8)nPos;.      
1730: 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 20 20 69  }else{.        i
1740: 6e 74 20 6e 42 79 74 65 20 3d 20 73 71 6c 69 74  nt nByte = sqlit
1750: 65 33 46 74 73 35 47 65 74 56 61 72 69 6e 74 4c  e3Fts5GetVarintL
1760: 65 6e 28 28 75 33 32 29 6e 50 6f 73 29 3b 0a 20  en((u32)nPos);. 
1770: 20 20 20 20 20 20 20 6d 65 6d 6d 6f 76 65 28 26         memmove(&
1780: 70 50 74 72 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69  pPtr[p->iSzPosli
1790: 73 74 20 2b 20 6e 42 79 74 65 5d 2c 20 26 70 50  st + nByte], &pP
17a0: 74 72 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74  tr[p->iSzPoslist
17b0: 20 2b 20 31 5d 2c 20 6e 53 7a 29 3b 0a 20 20 20   + 1], nSz);.   
17c0: 20 20 20 20 20 73 71 6c 69 74 65 33 46 74 73 35       sqlite3Fts5
17d0: 50 75 74 56 61 72 69 6e 74 28 26 70 50 74 72 5b  PutVarint(&pPtr[
17e0: 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 5d 2c 20  p->iSzPoslist], 
17f0: 6e 50 6f 73 29 3b 0a 20 20 20 20 20 20 20 20 6e  nPos);.        n
1800: 44 61 74 61 20 2b 3d 20 28 6e 42 79 74 65 2d 31  Data += (nByte-1
1810: 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 7d  );.      }.    }
1820: 0a 0a 20 20 20 20 6e 52 65 74 20 3d 20 6e 44 61  ..    nRet = nDa
1830: 74 61 20 2d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20  ta - p->nData;. 
1840: 20 20 20 69 66 28 20 70 32 3d 3d 30 20 29 7b 0a     if( p2==0 ){.
1850: 20 20 20 20 20 20 70 2d 3e 69 53 7a 50 6f 73 6c        p->iSzPosl
1860: 69 73 74 20 3d 20 30 3b 0a 20 20 20 20 20 20 70  ist = 0;.      p
1870: 2d 3e 62 44 65 6c 20 3d 20 30 3b 0a 20 20 20 20  ->bDel = 0;.    
1880: 20 20 70 2d 3e 62 43 6f 6e 74 65 6e 74 20 3d 20    p->bContent = 
1890: 30 3b 0a 20 20 20 20 20 20 70 2d 3e 6e 44 61 74  0;.      p->nDat
18a0: 61 20 3d 20 6e 44 61 74 61 3b 0a 20 20 20 20 7d  a = nData;.    }
18b0: 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 6e 52  .  }.  return nR
18c0: 65 74 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 41 64 64  et;.}../*.** Add
18d0: 20 61 6e 20 65 6e 74 72 79 20 74 6f 20 74 68 65   an entry to the
18e0: 20 69 6e 2d 6d 65 6d 6f 72 79 20 68 61 73 68 20   in-memory hash 
18f0: 74 61 62 6c 65 2e 20 54 68 65 20 6b 65 79 20 69  table. The key i
1900: 73 20 74 68 65 20 63 6f 6e 63 61 74 65 6e 61 74  s the concatenat
1910: 69 6f 6e 0a 2a 2a 20 6f 66 20 62 42 79 74 65 20  ion.** of bByte 
1920: 61 6e 64 20 28 70 54 6f 6b 65 6e 2f 6e 54 6f 6b  and (pToken/nTok
1930: 65 6e 29 2e 20 54 68 65 20 76 61 6c 75 65 20 69  en). The value i
1940: 73 20 28 69 52 6f 77 69 64 2f 69 43 6f 6c 2f 69  s (iRowid/iCol/i
1950: 50 6f 73 29 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 20  Pos)..**.**     
1960: 28 62 42 79 74 65 20 7c 7c 20 70 54 6f 6b 65 6e  (bByte || pToken
1970: 29 20 2d 3e 20 28 69 52 6f 77 69 64 2c 69 43 6f  ) -> (iRowid,iCo
1980: 6c 2c 69 50 6f 73 29 0a 2a 2a 0a 2a 2a 20 4f 72  l,iPos).**.** Or
1990: 2c 20 69 66 20 69 43 6f 6c 20 69 73 20 6e 65 67  , if iCol is neg
19a0: 61 74 69 76 65 2c 20 74 68 65 6e 20 74 68 65 20  ative, then the 
19b0: 76 61 6c 75 65 20 69 73 20 61 20 64 65 6c 65 74  value is a delet
19c0: 65 20 6d 61 72 6b 65 72 2e 0a 2a 2f 0a 69 6e 74  e marker..*/.int
19d0: 20 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68   sqlite3Fts5Hash
19e0: 57 72 69 74 65 28 0a 20 20 46 74 73 35 48 61 73  Write(.  Fts5Has
19f0: 68 20 2a 70 48 61 73 68 2c 0a 20 20 69 36 34 20  h *pHash,.  i64 
1a00: 69 52 6f 77 69 64 2c 20 20 20 20 20 20 20 20 20  iRowid,         
1a10: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52              /* R
1a20: 6f 77 69 64 20 66 6f 72 20 74 68 69 73 20 65 6e  owid for this en
1a30: 74 72 79 20 2a 2f 0a 20 20 69 6e 74 20 69 43 6f  try */.  int iCo
1a40: 6c 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20  l,              
1a50: 20 20 20 20 20 20 20 20 20 2f 2a 20 43 6f 6c 75           /* Colu
1a60: 6d 6e 20 74 6f 6b 65 6e 20 61 70 70 65 61 72 73  mn token appears
1a70: 20 69 6e 20 28 2d 76 65 20 2d 3e 20 64 65 6c 65   in (-ve -> dele
1a80: 74 65 29 20 2a 2f 0a 20 20 69 6e 74 20 69 50 6f  te) */.  int iPo
1a90: 73 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20  s,              
1aa0: 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 73 69           /* Posi
1ab0: 74 69 6f 6e 20 6f 66 20 74 6f 6b 65 6e 20 77 69  tion of token wi
1ac0: 74 68 69 6e 20 63 6f 6c 75 6d 6e 20 2a 2f 0a 20  thin column */. 
1ad0: 20 63 68 61 72 20 62 42 79 74 65 2c 20 20 20 20   char bByte,    
1ae0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1af0: 20 2f 2a 20 46 69 72 73 74 20 62 79 74 65 20 6f   /* First byte o
1b00: 66 20 74 6f 6b 65 6e 20 2a 2f 0a 20 20 63 6f 6e  f token */.  con
1b10: 73 74 20 63 68 61 72 20 2a 70 54 6f 6b 65 6e 2c  st char *pToken,
1b20: 20 69 6e 74 20 6e 54 6f 6b 65 6e 20 20 2f 2a 20   int nToken  /* 
1b30: 54 6f 6b 65 6e 20 74 6f 20 61 64 64 20 6f 72 20  Token to add or 
1b40: 72 65 6d 6f 76 65 20 74 6f 20 6f 72 20 66 72 6f  remove to or fro
1b50: 6d 20 69 6e 64 65 78 20 2a 2f 0a 29 7b 0a 20 20  m index */.){.  
1b60: 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 69 48 61  unsigned int iHa
1b70: 73 68 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e  sh;.  Fts5HashEn
1b80: 74 72 79 20 2a 70 3b 0a 20 20 75 38 20 2a 70 50  try *p;.  u8 *pP
1b90: 74 72 3b 0a 20 20 69 6e 74 20 6e 49 6e 63 72 20  tr;.  int nIncr 
1ba0: 3d 20 30 3b 20 20 20 20 20 20 20 20 20 20 20 20  = 0;            
1bb0: 20 20 20 20 20 20 2f 2a 20 41 6d 6f 75 6e 74 20        /* Amount 
1bc0: 74 6f 20 69 6e 63 72 65 6d 65 6e 74 20 28 2a 70  to increment (*p
1bd0: 48 61 73 68 2d 3e 70 6e 42 79 74 65 29 20 62 79  Hash->pnByte) by
1be0: 20 2a 2f 0a 20 20 69 6e 74 20 62 4e 65 77 3b 20   */.  int bNew; 
1bf0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1c00: 20 20 20 20 20 20 2f 2a 20 49 66 20 6e 6f 6e 2d        /* If non-
1c10: 64 65 6c 65 74 65 20 65 6e 74 72 79 20 73 68 6f  delete entry sho
1c20: 75 6c 64 20 62 65 20 77 72 69 74 74 65 6e 20 2a  uld be written *
1c30: 2f 0a 20 20 0a 20 20 62 4e 65 77 20 3d 20 28 70  /.  .  bNew = (p
1c40: 48 61 73 68 2d 3e 65 44 65 74 61 69 6c 3d 3d 46  Hash->eDetail==F
1c50: 54 53 35 5f 44 45 54 41 49 4c 5f 46 55 4c 4c 29  TS5_DETAIL_FULL)
1c60: 3b 0a 0a 20 20 2f 2a 20 41 74 74 65 6d 70 74 20  ;..  /* Attempt 
1c70: 74 6f 20 6c 6f 63 61 74 65 20 61 6e 20 65 78 69  to locate an exi
1c80: 73 74 69 6e 67 20 68 61 73 68 20 65 6e 74 72 79  sting hash entry
1c90: 20 2a 2f 0a 20 20 69 48 61 73 68 20 3d 20 66 74   */.  iHash = ft
1ca0: 73 35 48 61 73 68 4b 65 79 32 28 70 48 61 73 68  s5HashKey2(pHash
1cb0: 2d 3e 6e 53 6c 6f 74 2c 20 28 75 38 29 62 42 79  ->nSlot, (u8)bBy
1cc0: 74 65 2c 20 28 63 6f 6e 73 74 20 75 38 2a 29 70  te, (const u8*)p
1cd0: 54 6f 6b 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a  Token, nToken);.
1ce0: 20 20 66 6f 72 28 70 3d 70 48 61 73 68 2d 3e 61    for(p=pHash->a
1cf0: 53 6c 6f 74 5b 69 48 61 73 68 5d 3b 20 70 3b 20  Slot[iHash]; p; 
1d00: 70 3d 70 2d 3e 70 48 61 73 68 4e 65 78 74 29 7b  p=p->pHashNext){
1d10: 0a 20 20 20 20 63 68 61 72 20 2a 7a 4b 65 79 20  .    char *zKey 
1d20: 3d 20 66 74 73 35 45 6e 74 72 79 4b 65 79 28 70  = fts5EntryKey(p
1d30: 29 3b 0a 20 20 20 20 69 66 28 20 7a 4b 65 79 5b  );.    if( zKey[
1d40: 30 5d 3d 3d 62 42 79 74 65 20 0a 20 20 20 20 20  0]==bByte .     
1d50: 26 26 20 70 2d 3e 6e 4b 65 79 3d 3d 6e 54 6f 6b  && p->nKey==nTok
1d60: 65 6e 0a 20 20 20 20 20 26 26 20 6d 65 6d 63 6d  en.     && memcm
1d70: 70 28 26 7a 4b 65 79 5b 31 5d 2c 20 70 54 6f 6b  p(&zKey[1], pTok
1d80: 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3d 3d 30 20 0a  en, nToken)==0 .
1d90: 20 20 20 20 29 7b 0a 20 20 20 20 20 20 62 72 65      ){.      bre
1da0: 61 6b 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 20  ak;.    }.  }.. 
1db0: 20 2f 2a 20 49 66 20 61 6e 20 65 78 69 73 74 69   /* If an existi
1dc0: 6e 67 20 68 61 73 68 20 65 6e 74 72 79 20 63 61  ng hash entry ca
1dd0: 6e 6e 6f 74 20 62 65 20 66 6f 75 6e 64 2c 20 63  nnot be found, c
1de0: 72 65 61 74 65 20 61 20 6e 65 77 20 6f 6e 65 2e  reate a new one.
1df0: 20 2a 2f 0a 20 20 69 66 28 20 70 3d 3d 30 20 29   */.  if( p==0 )
1e00: 7b 0a 20 20 20 20 2f 2a 20 46 69 67 75 72 65 20  {.    /* Figure 
1e10: 6f 75 74 20 68 6f 77 20 6d 75 63 68 20 73 70 61  out how much spa
1e20: 63 65 20 74 6f 20 61 6c 6c 6f 63 61 74 65 20 2a  ce to allocate *
1e30: 2f 0a 20 20 20 20 63 68 61 72 20 2a 7a 4b 65 79  /.    char *zKey
1e40: 3b 0a 20 20 20 20 73 71 6c 69 74 65 33 5f 69 6e  ;.    sqlite3_in
1e50: 74 36 34 20 6e 42 79 74 65 20 3d 20 73 69 7a 65  t64 nByte = size
1e60: 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79  of(Fts5HashEntry
1e70: 29 20 2b 20 28 6e 54 6f 6b 65 6e 2b 31 29 20 2b  ) + (nToken+1) +
1e80: 20 31 20 2b 20 36 34 3b 0a 20 20 20 20 69 66 28   1 + 64;.    if(
1e90: 20 6e 42 79 74 65 3c 31 32 38 20 29 20 6e 42 79   nByte<128 ) nBy
1ea0: 74 65 20 3d 20 31 32 38 3b 0a 0a 20 20 20 20 2f  te = 128;..    /
1eb0: 2a 20 47 72 6f 77 20 74 68 65 20 46 74 73 35 48  * Grow the Fts5H
1ec0: 61 73 68 2e 61 53 6c 6f 74 5b 5d 20 61 72 72 61  ash.aSlot[] arra
1ed0: 79 20 69 66 20 6e 65 63 65 73 73 61 72 79 2e 20  y if necessary. 
1ee0: 2a 2f 0a 20 20 20 20 69 66 28 20 28 70 48 61 73  */.    if( (pHas
1ef0: 68 2d 3e 6e 45 6e 74 72 79 2a 32 29 3e 3d 70 48  h->nEntry*2)>=pH
1f00: 61 73 68 2d 3e 6e 53 6c 6f 74 20 29 7b 0a 20 20  ash->nSlot ){.  
1f10: 20 20 20 20 69 6e 74 20 72 63 20 3d 20 66 74 73      int rc = fts
1f20: 35 48 61 73 68 52 65 73 69 7a 65 28 70 48 61 73  5HashResize(pHas
1f30: 68 29 3b 0a 20 20 20 20 20 20 69 66 28 20 72 63  h);.      if( rc
1f40: 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 20 72 65  !=SQLITE_OK ) re
1f50: 74 75 72 6e 20 72 63 3b 0a 20 20 20 20 20 20 69  turn rc;.      i
1f60: 48 61 73 68 20 3d 20 66 74 73 35 48 61 73 68 4b  Hash = fts5HashK
1f70: 65 79 32 28 70 48 61 73 68 2d 3e 6e 53 6c 6f 74  ey2(pHash->nSlot
1f80: 2c 20 28 75 38 29 62 42 79 74 65 2c 20 28 63 6f  , (u8)bByte, (co
1f90: 6e 73 74 20 75 38 2a 29 70 54 6f 6b 65 6e 2c 20  nst u8*)pToken, 
1fa0: 6e 54 6f 6b 65 6e 29 3b 0a 20 20 20 20 7d 0a 0a  nToken);.    }..
1fb0: 20 20 20 20 2f 2a 20 41 6c 6c 6f 63 61 74 65 20      /* Allocate 
1fc0: 6e 65 77 20 46 74 73 35 48 61 73 68 45 6e 74 72  new Fts5HashEntr
1fd0: 79 20 61 6e 64 20 61 64 64 20 69 74 20 74 6f 20  y and add it to 
1fe0: 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 2e 20  the hash table. 
1ff0: 2a 2f 0a 20 20 20 20 70 20 3d 20 28 46 74 73 35  */.    p = (Fts5
2000: 48 61 73 68 45 6e 74 72 79 2a 29 73 71 6c 69 74  HashEntry*)sqlit
2010: 65 33 5f 6d 61 6c 6c 6f 63 36 34 28 6e 42 79 74  e3_malloc64(nByt
2020: 65 29 3b 0a 20 20 20 20 69 66 28 20 21 70 20 29  e);.    if( !p )
2030: 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e   return SQLITE_N
2040: 4f 4d 45 4d 3b 0a 20 20 20 20 6d 65 6d 73 65 74  OMEM;.    memset
2050: 28 70 2c 20 30 2c 20 73 69 7a 65 6f 66 28 46 74  (p, 0, sizeof(Ft
2060: 73 35 48 61 73 68 45 6e 74 72 79 29 29 3b 0a 20  s5HashEntry));. 
2070: 20 20 20 70 2d 3e 6e 41 6c 6c 6f 63 20 3d 20 6e     p->nAlloc = n
2080: 42 79 74 65 3b 0a 20 20 20 20 7a 4b 65 79 20 3d  Byte;.    zKey =
2090: 20 66 74 73 35 45 6e 74 72 79 4b 65 79 28 70 29   fts5EntryKey(p)
20a0: 3b 0a 20 20 20 20 7a 4b 65 79 5b 30 5d 20 3d 20  ;.    zKey[0] = 
20b0: 62 42 79 74 65 3b 0a 20 20 20 20 6d 65 6d 63 70  bByte;.    memcp
20c0: 79 28 26 7a 4b 65 79 5b 31 5d 2c 20 70 54 6f 6b  y(&zKey[1], pTok
20d0: 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 20  en, nToken);.   
20e0: 20 61 73 73 65 72 74 28 20 69 48 61 73 68 3d 3d   assert( iHash==
20f0: 66 74 73 35 48 61 73 68 4b 65 79 28 70 48 61 73  fts5HashKey(pHas
2100: 68 2d 3e 6e 53 6c 6f 74 2c 20 28 75 38 2a 29 7a  h->nSlot, (u8*)z
2110: 4b 65 79 2c 20 6e 54 6f 6b 65 6e 2b 31 29 20 29  Key, nToken+1) )
2120: 3b 0a 20 20 20 20 70 2d 3e 6e 4b 65 79 20 3d 20  ;.    p->nKey = 
2130: 6e 54 6f 6b 65 6e 3b 0a 20 20 20 20 7a 4b 65 79  nToken;.    zKey
2140: 5b 6e 54 6f 6b 65 6e 2b 31 5d 20 3d 20 27 5c 30  [nToken+1] = '\0
2150: 27 3b 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20  ';.    p->nData 
2160: 3d 20 6e 54 6f 6b 65 6e 2b 31 20 2b 20 31 20 2b  = nToken+1 + 1 +
2170: 20 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68   sizeof(Fts5Hash
2180: 45 6e 74 72 79 29 3b 0a 20 20 20 20 70 2d 3e 70  Entry);.    p->p
2190: 48 61 73 68 4e 65 78 74 20 3d 20 70 48 61 73 68  HashNext = pHash
21a0: 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d 3b 0a  ->aSlot[iHash];.
21b0: 20 20 20 20 70 48 61 73 68 2d 3e 61 53 6c 6f 74      pHash->aSlot
21c0: 5b 69 48 61 73 68 5d 20 3d 20 70 3b 0a 20 20 20  [iHash] = p;.   
21d0: 20 70 48 61 73 68 2d 3e 6e 45 6e 74 72 79 2b 2b   pHash->nEntry++
21e0: 3b 0a 0a 20 20 20 20 2f 2a 20 41 64 64 20 74 68  ;..    /* Add th
21f0: 65 20 66 69 72 73 74 20 72 6f 77 69 64 20 66 69  e first rowid fi
2200: 65 6c 64 20 74 6f 20 74 68 65 20 68 61 73 68 2d  eld to the hash-
2210: 65 6e 74 72 79 20 2a 2f 0a 20 20 20 20 70 2d 3e  entry */.    p->
2220: 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69 74 65 33  nData += sqlite3
2230: 46 74 73 35 50 75 74 56 61 72 69 6e 74 28 26 28  Fts5PutVarint(&(
2240: 28 75 38 2a 29 70 29 5b 70 2d 3e 6e 44 61 74 61  (u8*)p)[p->nData
2250: 5d 2c 20 69 52 6f 77 69 64 29 3b 0a 20 20 20 20  ], iRowid);.    
2260: 70 2d 3e 69 52 6f 77 69 64 20 3d 20 69 52 6f 77  p->iRowid = iRow
2270: 69 64 3b 0a 0a 20 20 20 20 70 2d 3e 69 53 7a 50  id;..    p->iSzP
2280: 6f 73 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74  oslist = p->nDat
2290: 61 3b 0a 20 20 20 20 69 66 28 20 70 48 61 73 68  a;.    if( pHash
22a0: 2d 3e 65 44 65 74 61 69 6c 21 3d 46 54 53 35 5f  ->eDetail!=FTS5_
22b0: 44 45 54 41 49 4c 5f 4e 4f 4e 45 20 29 7b 0a 20  DETAIL_NONE ){. 
22c0: 20 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d       p->nData +=
22d0: 20 31 3b 0a 20 20 20 20 20 20 70 2d 3e 69 43 6f   1;.      p->iCo
22e0: 6c 20 3d 20 28 70 48 61 73 68 2d 3e 65 44 65 74  l = (pHash->eDet
22f0: 61 69 6c 3d 3d 46 54 53 35 5f 44 45 54 41 49 4c  ail==FTS5_DETAIL
2300: 5f 46 55 4c 4c 20 3f 20 30 20 3a 20 2d 31 29 3b  _FULL ? 0 : -1);
2310: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 6e 49 6e 63  .    }..    nInc
2320: 72 20 2b 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20  r += p->nData;. 
2330: 20 7d 65 6c 73 65 7b 0a 0a 20 20 20 20 2f 2a 20   }else{..    /* 
2340: 41 70 70 65 6e 64 69 6e 67 20 74 6f 20 61 6e 20  Appending to an 
2350: 65 78 69 73 74 69 6e 67 20 68 61 73 68 2d 65 6e  existing hash-en
2360: 74 72 79 2e 20 43 68 65 63 6b 20 74 68 61 74 20  try. Check that 
2370: 74 68 65 72 65 20 69 73 20 65 6e 6f 75 67 68 20  there is enough 
2380: 0a 20 20 20 20 2a 2a 20 73 70 61 63 65 20 74 6f  .    ** space to
2390: 20 61 70 70 65 6e 64 20 74 68 65 20 6c 61 72 67   append the larg
23a0: 65 73 74 20 70 6f 73 73 69 62 6c 65 20 6e 65 77  est possible new
23b0: 20 65 6e 74 72 79 2e 20 57 6f 72 73 74 20 63 61   entry. Worst ca
23c0: 73 65 20 73 63 65 6e 61 72 69 6f 20 0a 20 20 20  se scenario .   
23d0: 20 2a 2a 20 69 73 3a 0a 20 20 20 20 2a 2a 0a 20   ** is:.    **. 
23e0: 20 20 20 2a 2a 20 20 20 20 20 2b 20 39 20 62 79     **     + 9 by
23f0: 74 65 73 20 66 6f 72 20 61 20 6e 65 77 20 72 6f  tes for a new ro
2400: 77 69 64 2c 0a 20 20 20 20 2a 2a 20 20 20 20 20  wid,.    **     
2410: 2b 20 34 20 62 79 74 65 20 72 65 73 65 72 76 65  + 4 byte reserve
2420: 64 20 66 6f 72 20 74 68 65 20 22 70 6f 73 6c 69  d for the "posli
2430: 73 74 20 73 69 7a 65 22 20 76 61 72 69 6e 74 2e  st size" varint.
2440: 0a 20 20 20 20 2a 2a 20 20 20 20 20 2b 20 31 20  .    **     + 1 
2450: 62 79 74 65 20 66 6f 72 20 61 20 22 6e 65 77 20  byte for a "new 
2460: 63 6f 6c 75 6d 6e 22 20 62 79 74 65 2c 0a 20 20  column" byte,.  
2470: 20 20 2a 2a 20 20 20 20 20 2b 20 33 20 62 79 74    **     + 3 byt
2480: 65 73 20 66 6f 72 20 61 20 6e 65 77 20 63 6f 6c  es for a new col
2490: 75 6d 6e 20 6e 75 6d 62 65 72 20 28 31 36 2d 62  umn number (16-b
24a0: 69 74 20 6d 61 78 29 20 61 73 20 61 20 76 61 72  it max) as a var
24b0: 69 6e 74 2c 0a 20 20 20 20 2a 2a 20 20 20 20 20  int,.    **     
24c0: 2b 20 35 20 62 79 74 65 73 20 66 6f 72 20 74 68  + 5 bytes for th
24d0: 65 20 6e 65 77 20 70 6f 73 69 74 69 6f 6e 20 6f  e new position o
24e0: 66 66 73 65 74 20 28 33 32 2d 62 69 74 20 6d 61  ffset (32-bit ma
24f0: 78 29 2e 0a 20 20 20 20 2a 2f 0a 20 20 20 20 69  x)..    */.    i
2500: 66 28 20 28 70 2d 3e 6e 41 6c 6c 6f 63 20 2d 20  f( (p->nAlloc - 
2510: 70 2d 3e 6e 44 61 74 61 29 20 3c 20 28 39 20 2b  p->nData) < (9 +
2520: 20 34 20 2b 20 31 20 2b 20 33 20 2b 20 35 29 20   4 + 1 + 3 + 5) 
2530: 29 7b 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33  ){.      sqlite3
2540: 5f 69 6e 74 36 34 20 6e 4e 65 77 20 3d 20 70 2d  _int64 nNew = p-
2550: 3e 6e 41 6c 6c 6f 63 20 2a 20 32 3b 0a 20 20 20  >nAlloc * 2;.   
2560: 20 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79     Fts5HashEntry
2570: 20 2a 70 4e 65 77 3b 0a 20 20 20 20 20 20 46 74   *pNew;.      Ft
2580: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 70 70  s5HashEntry **pp
2590: 3b 0a 20 20 20 20 20 20 70 4e 65 77 20 3d 20 28  ;.      pNew = (
25a0: 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29 73  Fts5HashEntry*)s
25b0: 71 6c 69 74 65 33 5f 72 65 61 6c 6c 6f 63 36 34  qlite3_realloc64
25c0: 28 70 2c 20 6e 4e 65 77 29 3b 0a 20 20 20 20 20  (p, nNew);.     
25d0: 20 69 66 28 20 70 4e 65 77 3d 3d 30 20 29 20 72   if( pNew==0 ) r
25e0: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d  eturn SQLITE_NOM
25f0: 45 4d 3b 0a 20 20 20 20 20 20 70 4e 65 77 2d 3e  EM;.      pNew->
2600: 6e 41 6c 6c 6f 63 20 3d 20 28 69 6e 74 29 6e 4e  nAlloc = (int)nN
2610: 65 77 3b 0a 20 20 20 20 20 20 66 6f 72 28 70 70  ew;.      for(pp
2620: 3d 26 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69  =&pHash->aSlot[i
2630: 48 61 73 68 5d 3b 20 2a 70 70 21 3d 70 3b 20 70  Hash]; *pp!=p; p
2640: 70 3d 26 28 2a 70 70 29 2d 3e 70 48 61 73 68 4e  p=&(*pp)->pHashN
2650: 65 78 74 29 3b 0a 20 20 20 20 20 20 2a 70 70 20  ext);.      *pp 
2660: 3d 20 70 4e 65 77 3b 0a 20 20 20 20 20 20 70 20  = pNew;.      p 
2670: 3d 20 70 4e 65 77 3b 0a 20 20 20 20 7d 0a 20 20  = pNew;.    }.  
2680: 20 20 6e 49 6e 63 72 20 2d 3d 20 70 2d 3e 6e 44    nIncr -= p->nD
2690: 61 74 61 3b 0a 20 20 7d 0a 20 20 61 73 73 65 72  ata;.  }.  asser
26a0: 74 28 20 28 70 2d 3e 6e 41 6c 6c 6f 63 20 2d 20  t( (p->nAlloc - 
26b0: 70 2d 3e 6e 44 61 74 61 29 20 3e 3d 20 28 39 20  p->nData) >= (9 
26c0: 2b 20 34 20 2b 20 31 20 2b 20 33 20 2b 20 35 29  + 4 + 1 + 3 + 5)
26d0: 20 29 3b 0a 0a 20 20 70 50 74 72 20 3d 20 28 75   );..  pPtr = (u
26e0: 38 2a 29 70 3b 0a 0a 20 20 2f 2a 20 49 66 20 74  8*)p;..  /* If t
26f0: 68 69 73 20 69 73 20 61 20 6e 65 77 20 72 6f 77  his is a new row
2700: 69 64 2c 20 61 70 70 65 6e 64 20 74 68 65 20 34  id, append the 4
2710: 2d 62 79 74 65 20 73 69 7a 65 20 66 69 65 6c 64  -byte size field
2720: 20 66 6f 72 20 74 68 65 20 70 72 65 76 69 6f 75   for the previou
2730: 73 0a 20 20 2a 2a 20 65 6e 74 72 79 2c 20 61 6e  s.  ** entry, an
2740: 64 20 74 68 65 20 6e 65 77 20 72 6f 77 69 64 20  d the new rowid 
2750: 66 6f 72 20 74 68 69 73 20 65 6e 74 72 79 2e 20  for this entry. 
2760: 20 2a 2f 0a 20 20 69 66 28 20 69 52 6f 77 69 64   */.  if( iRowid
2770: 21 3d 70 2d 3e 69 52 6f 77 69 64 20 29 7b 0a 20  !=p->iRowid ){. 
2780: 20 20 20 66 74 73 35 48 61 73 68 41 64 64 50 6f     fts5HashAddPo
2790: 73 6c 69 73 74 53 69 7a 65 28 70 48 61 73 68 2c  slistSize(pHash,
27a0: 20 70 2c 20 30 29 3b 0a 20 20 20 20 70 2d 3e 6e   p, 0);.    p->n
27b0: 44 61 74 61 20 2b 3d 20 73 71 6c 69 74 65 33 46  Data += sqlite3F
27c0: 74 73 35 50 75 74 56 61 72 69 6e 74 28 26 70 50  ts5PutVarint(&pP
27d0: 74 72 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20 69 52  tr[p->nData], iR
27e0: 6f 77 69 64 20 2d 20 70 2d 3e 69 52 6f 77 69 64  owid - p->iRowid
27f0: 29 3b 0a 20 20 20 20 70 2d 3e 69 52 6f 77 69 64  );.    p->iRowid
2800: 20 3d 20 69 52 6f 77 69 64 3b 0a 20 20 20 20 62   = iRowid;.    b
2810: 4e 65 77 20 3d 20 31 3b 0a 20 20 20 20 70 2d 3e  New = 1;.    p->
2820: 69 53 7a 50 6f 73 6c 69 73 74 20 3d 20 70 2d 3e  iSzPoslist = p->
2830: 6e 44 61 74 61 3b 0a 20 20 20 20 69 66 28 20 70  nData;.    if( p
2840: 48 61 73 68 2d 3e 65 44 65 74 61 69 6c 21 3d 46  Hash->eDetail!=F
2850: 54 53 35 5f 44 45 54 41 49 4c 5f 4e 4f 4e 45 20  TS5_DETAIL_NONE 
2860: 29 7b 0a 20 20 20 20 20 20 70 2d 3e 6e 44 61 74  ){.      p->nDat
2870: 61 20 2b 3d 20 31 3b 0a 20 20 20 20 20 20 70 2d  a += 1;.      p-
2880: 3e 69 43 6f 6c 20 3d 20 28 70 48 61 73 68 2d 3e  >iCol = (pHash->
2890: 65 44 65 74 61 69 6c 3d 3d 46 54 53 35 5f 44 45  eDetail==FTS5_DE
28a0: 54 41 49 4c 5f 46 55 4c 4c 20 3f 20 30 20 3a 20  TAIL_FULL ? 0 : 
28b0: 2d 31 29 3b 0a 20 20 20 20 20 20 70 2d 3e 69 50  -1);.      p->iP
28c0: 6f 73 20 3d 20 30 3b 0a 20 20 20 20 7d 0a 20 20  os = 0;.    }.  
28d0: 7d 0a 0a 20 20 69 66 28 20 69 43 6f 6c 3e 3d 30  }..  if( iCol>=0
28e0: 20 29 7b 0a 20 20 20 20 69 66 28 20 70 48 61 73   ){.    if( pHas
28f0: 68 2d 3e 65 44 65 74 61 69 6c 3d 3d 46 54 53 35  h->eDetail==FTS5
2900: 5f 44 45 54 41 49 4c 5f 4e 4f 4e 45 20 29 7b 0a  _DETAIL_NONE ){.
2910: 20 20 20 20 20 20 70 2d 3e 62 43 6f 6e 74 65 6e        p->bConten
2920: 74 20 3d 20 31 3b 0a 20 20 20 20 7d 65 6c 73 65  t = 1;.    }else
2930: 7b 0a 20 20 20 20 20 20 2f 2a 20 41 70 70 65 6e  {.      /* Appen
2940: 64 20 61 20 6e 65 77 20 63 6f 6c 75 6d 6e 20 76  d a new column v
2950: 61 6c 75 65 2c 20 69 66 20 6e 65 63 65 73 73 61  alue, if necessa
2960: 72 79 20 2a 2f 0a 20 20 20 20 20 20 61 73 73 65  ry */.      asse
2970: 72 74 28 20 69 43 6f 6c 3e 3d 70 2d 3e 69 43 6f  rt( iCol>=p->iCo
2980: 6c 20 29 3b 0a 20 20 20 20 20 20 69 66 28 20 69  l );.      if( i
2990: 43 6f 6c 21 3d 70 2d 3e 69 43 6f 6c 20 29 7b 0a  Col!=p->iCol ){.
29a0: 20 20 20 20 20 20 20 20 69 66 28 20 70 48 61 73          if( pHas
29b0: 68 2d 3e 65 44 65 74 61 69 6c 3d 3d 46 54 53 35  h->eDetail==FTS5
29c0: 5f 44 45 54 41 49 4c 5f 46 55 4c 4c 20 29 7b 0a  _DETAIL_FULL ){.
29d0: 20 20 20 20 20 20 20 20 20 20 70 50 74 72 5b 70            pPtr[p
29e0: 2d 3e 6e 44 61 74 61 2b 2b 5d 20 3d 20 30 78 30  ->nData++] = 0x0
29f0: 31 3b 0a 20 20 20 20 20 20 20 20 20 20 70 2d 3e  1;.          p->
2a00: 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69 74 65 33  nData += sqlite3
2a10: 46 74 73 35 50 75 74 56 61 72 69 6e 74 28 26 70  Fts5PutVarint(&p
2a20: 50 74 72 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20 69  Ptr[p->nData], i
2a30: 43 6f 6c 29 3b 0a 20 20 20 20 20 20 20 20 20 20  Col);.          
2a40: 70 2d 3e 69 43 6f 6c 20 3d 20 28 69 31 36 29 69  p->iCol = (i16)i
2a50: 43 6f 6c 3b 0a 20 20 20 20 20 20 20 20 20 20 70  Col;.          p
2a60: 2d 3e 69 50 6f 73 20 3d 20 30 3b 0a 20 20 20 20  ->iPos = 0;.    
2a70: 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20      }else{.     
2a80: 20 20 20 20 20 62 4e 65 77 20 3d 20 31 3b 0a 20       bNew = 1;. 
2a90: 20 20 20 20 20 20 20 20 20 70 2d 3e 69 43 6f 6c           p->iCol
2aa0: 20 3d 20 28 69 31 36 29 28 69 50 6f 73 20 3d 20   = (i16)(iPos = 
2ab0: 69 43 6f 6c 29 3b 0a 20 20 20 20 20 20 20 20 7d  iCol);.        }
2ac0: 0a 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 20 20  .      }..      
2ad0: 2f 2a 20 41 70 70 65 6e 64 20 74 68 65 20 6e 65  /* Append the ne
2ae0: 77 20 70 6f 73 69 74 69 6f 6e 20 6f 66 66 73 65  w position offse
2af0: 74 2c 20 69 66 20 6e 65 63 65 73 73 61 72 79 20  t, if necessary 
2b00: 2a 2f 0a 20 20 20 20 20 20 69 66 28 20 62 4e 65  */.      if( bNe
2b10: 77 20 29 7b 0a 20 20 20 20 20 20 20 20 70 2d 3e  w ){.        p->
2b20: 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69 74 65 33  nData += sqlite3
2b30: 46 74 73 35 50 75 74 56 61 72 69 6e 74 28 26 70  Fts5PutVarint(&p
2b40: 50 74 72 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20 69  Ptr[p->nData], i
2b50: 50 6f 73 20 2d 20 70 2d 3e 69 50 6f 73 20 2b 20  Pos - p->iPos + 
2b60: 32 29 3b 0a 20 20 20 20 20 20 20 20 70 2d 3e 69  2);.        p->i
2b70: 50 6f 73 20 3d 20 69 50 6f 73 3b 0a 20 20 20 20  Pos = iPos;.    
2b80: 20 20 7d 0a 20 20 20 20 7d 0a 20 20 7d 65 6c 73    }.    }.  }els
2b90: 65 7b 0a 20 20 20 20 2f 2a 20 54 68 69 73 20 69  e{.    /* This i
2ba0: 73 20 61 20 64 65 6c 65 74 65 2e 20 53 65 74 20  s a delete. Set 
2bb0: 74 68 65 20 64 65 6c 65 74 65 20 66 6c 61 67 2e  the delete flag.
2bc0: 20 2a 2f 0a 20 20 20 20 70 2d 3e 62 44 65 6c 20   */.    p->bDel 
2bd0: 3d 20 31 3b 0a 20 20 7d 0a 0a 20 20 6e 49 6e 63  = 1;.  }..  nInc
2be0: 72 20 2b 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20  r += p->nData;. 
2bf0: 20 2a 70 48 61 73 68 2d 3e 70 6e 42 79 74 65 20   *pHash->pnByte 
2c00: 2b 3d 20 6e 49 6e 63 72 3b 0a 20 20 72 65 74 75  += nIncr;.  retu
2c10: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a  rn SQLITE_OK;.}.
2c20: 0a 0a 2f 2a 0a 2a 2a 20 41 72 67 75 6d 65 6e 74  ../*.** Argument
2c30: 73 20 70 4c 65 66 74 20 61 6e 64 20 70 52 69 67  s pLeft and pRig
2c40: 68 74 20 70 6f 69 6e 74 20 74 6f 20 6c 69 6e 6b  ht point to link
2c50: 65 64 2d 6c 69 73 74 73 20 6f 66 20 68 61 73 68  ed-lists of hash
2c60: 2d 65 6e 74 72 79 20 6f 62 6a 65 63 74 73 2c 0a  -entry objects,.
2c70: 2a 2a 20 65 61 63 68 20 73 6f 72 74 65 64 20 69  ** each sorted i
2c80: 6e 20 6b 65 79 20 6f 72 64 65 72 2e 20 54 68 69  n key order. Thi
2c90: 73 20 66 75 6e 63 74 69 6f 6e 20 6d 65 72 67 65  s function merge
2ca0: 73 20 74 68 65 20 74 77 6f 20 6c 69 73 74 73 20  s the two lists 
2cb0: 69 6e 74 6f 20 61 0a 2a 2a 20 73 69 6e 67 6c 65  into a.** single
2cc0: 20 6c 69 73 74 20 61 6e 64 20 72 65 74 75 72 6e   list and return
2cd0: 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 69  s a pointer to i
2ce0: 74 73 20 66 69 72 73 74 20 65 6c 65 6d 65 6e 74  ts first element
2cf0: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 46 74 73 35  ..*/.static Fts5
2d00: 48 61 73 68 45 6e 74 72 79 20 2a 66 74 73 35 48  HashEntry *fts5H
2d10: 61 73 68 45 6e 74 72 79 4d 65 72 67 65 28 0a 20  ashEntryMerge(. 
2d20: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
2d30: 70 4c 65 66 74 2c 0a 20 20 46 74 73 35 48 61 73  pLeft,.  Fts5Has
2d40: 68 45 6e 74 72 79 20 2a 70 52 69 67 68 74 0a 29  hEntry *pRight.)
2d50: 7b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72  {.  Fts5HashEntr
2d60: 79 20 2a 70 31 20 3d 20 70 4c 65 66 74 3b 0a 20  y *p1 = pLeft;. 
2d70: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
2d80: 70 32 20 3d 20 70 52 69 67 68 74 3b 0a 20 20 46  p2 = pRight;.  F
2d90: 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 52  ts5HashEntry *pR
2da0: 65 74 20 3d 20 30 3b 0a 20 20 46 74 73 35 48 61  et = 0;.  Fts5Ha
2db0: 73 68 45 6e 74 72 79 20 2a 2a 70 70 4f 75 74 20  shEntry **ppOut 
2dc0: 3d 20 26 70 52 65 74 3b 0a 0a 20 20 77 68 69 6c  = &pRet;..  whil
2dd0: 65 28 20 70 31 20 7c 7c 20 70 32 20 29 7b 0a 20  e( p1 || p2 ){. 
2de0: 20 20 20 69 66 28 20 70 31 3d 3d 30 20 29 7b 0a     if( p1==0 ){.
2df0: 20 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 70        *ppOut = p
2e00: 32 3b 0a 20 20 20 20 20 20 70 32 20 3d 20 30 3b  2;.      p2 = 0;
2e10: 0a 20 20 20 20 7d 65 6c 73 65 20 69 66 28 20 70  .    }else if( p
2e20: 32 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 2a 70  2==0 ){.      *p
2e30: 70 4f 75 74 20 3d 20 70 31 3b 0a 20 20 20 20 20  pOut = p1;.     
2e40: 20 70 31 20 3d 20 30 3b 0a 20 20 20 20 7d 65 6c   p1 = 0;.    }el
2e50: 73 65 7b 0a 20 20 20 20 20 20 69 6e 74 20 69 20  se{.      int i 
2e60: 3d 20 30 3b 0a 20 20 20 20 20 20 63 68 61 72 20  = 0;.      char 
2e70: 2a 7a 4b 65 79 31 20 3d 20 66 74 73 35 45 6e 74  *zKey1 = fts5Ent
2e80: 72 79 4b 65 79 28 70 31 29 3b 0a 20 20 20 20 20  ryKey(p1);.     
2e90: 20 63 68 61 72 20 2a 7a 4b 65 79 32 20 3d 20 66   char *zKey2 = f
2ea0: 74 73 35 45 6e 74 72 79 4b 65 79 28 70 32 29 3b  ts5EntryKey(p2);
2eb0: 0a 20 20 20 20 20 20 77 68 69 6c 65 28 20 7a 4b  .      while( zK
2ec0: 65 79 31 5b 69 5d 3d 3d 7a 4b 65 79 32 5b 69 5d  ey1[i]==zKey2[i]
2ed0: 20 29 20 69 2b 2b 3b 0a 0a 20 20 20 20 20 20 69   ) i++;..      i
2ee0: 66 28 20 28 28 75 38 29 7a 4b 65 79 31 5b 69 5d  f( ((u8)zKey1[i]
2ef0: 29 3e 28 28 75 38 29 7a 4b 65 79 32 5b 69 5d 29  )>((u8)zKey2[i])
2f00: 20 29 7b 0a 20 20 20 20 20 20 20 20 2f 2a 20 70   ){.        /* p
2f10: 32 20 69 73 20 73 6d 61 6c 6c 65 72 20 2a 2f 0a  2 is smaller */.
2f20: 20 20 20 20 20 20 20 20 2a 70 70 4f 75 74 20 3d          *ppOut =
2f30: 20 70 32 3b 0a 20 20 20 20 20 20 20 20 70 70 4f   p2;.        ppO
2f40: 75 74 20 3d 20 26 70 32 2d 3e 70 53 63 61 6e 4e  ut = &p2->pScanN
2f50: 65 78 74 3b 0a 20 20 20 20 20 20 20 20 70 32 20  ext;.        p2 
2f60: 3d 20 70 32 2d 3e 70 53 63 61 6e 4e 65 78 74 3b  = p2->pScanNext;
2f70: 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20  .      }else{.  
2f80: 20 20 20 20 20 20 2f 2a 20 70 31 20 69 73 20 73        /* p1 is s
2f90: 6d 61 6c 6c 65 72 20 2a 2f 0a 20 20 20 20 20 20  maller */.      
2fa0: 20 20 2a 70 70 4f 75 74 20 3d 20 70 31 3b 0a 20    *ppOut = p1;. 
2fb0: 20 20 20 20 20 20 20 70 70 4f 75 74 20 3d 20 26         ppOut = &
2fc0: 70 31 2d 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 20  p1->pScanNext;. 
2fd0: 20 20 20 20 20 20 20 70 31 20 3d 20 70 31 2d 3e         p1 = p1->
2fe0: 70 53 63 61 6e 4e 65 78 74 3b 0a 20 20 20 20 20  pScanNext;.     
2ff0: 20 7d 0a 20 20 20 20 20 20 2a 70 70 4f 75 74 20   }.      *ppOut 
3000: 3d 20 30 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a  = 0;.    }.  }..
3010: 20 20 72 65 74 75 72 6e 20 70 52 65 74 3b 0a 7d    return pRet;.}
3020: 0a 0a 2f 2a 0a 2a 2a 20 45 78 74 72 61 63 74 20  ../*.** Extract 
3030: 61 6c 6c 20 74 6f 6b 65 6e 73 20 66 72 6f 6d 20  all tokens from 
3040: 68 61 73 68 20 74 61 62 6c 65 20 69 48 61 73 68  hash table iHash
3050: 20 61 6e 64 20 6c 69 6e 6b 20 74 68 65 6d 20 69   and link them i
3060: 6e 74 6f 20 61 20 6c 69 73 74 0a 2a 2a 20 69 6e  nto a list.** in
3070: 20 73 6f 72 74 65 64 20 6f 72 64 65 72 2e 20 54   sorted order. T
3080: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 69 73  he hash table is
3090: 20 63 6c 65 61 72 65 64 20 62 65 66 6f 72 65 20   cleared before 
30a0: 72 65 74 75 72 6e 69 6e 67 2e 20 49 74 20 69 73  returning. It is
30b0: 0a 2a 2a 20 74 68 65 20 72 65 73 70 6f 6e 73 69  .** the responsi
30c0: 62 69 6c 69 74 79 20 6f 66 20 74 68 65 20 63 61  bility of the ca
30d0: 6c 6c 65 72 20 74 6f 20 66 72 65 65 20 74 68 65  ller to free the
30e0: 20 65 6c 65 6d 65 6e 74 73 20 6f 66 20 74 68 65   elements of the
30f0: 20 72 65 74 75 72 6e 65 64 0a 2a 2a 20 6c 69 73   returned.** lis
3100: 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74  t..*/.static int
3110: 20 66 74 73 35 48 61 73 68 45 6e 74 72 79 53 6f   fts5HashEntrySo
3120: 72 74 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a  rt(.  Fts5Hash *
3130: 70 48 61 73 68 2c 20 0a 20 20 63 6f 6e 73 74 20  pHash, .  const 
3140: 63 68 61 72 20 2a 70 54 65 72 6d 2c 20 69 6e 74  char *pTerm, int
3150: 20 6e 54 65 72 6d 2c 20 20 20 2f 2a 20 51 75 65   nTerm,   /* Que
3160: 72 79 20 70 72 65 66 69 78 2c 20 69 66 20 61 6e  ry prefix, if an
3170: 79 20 2a 2f 0a 20 20 46 74 73 35 48 61 73 68 45  y */.  Fts5HashE
3180: 6e 74 72 79 20 2a 2a 70 70 53 6f 72 74 65 64 0a  ntry **ppSorted.
3190: 29 7b 0a 20 20 63 6f 6e 73 74 20 69 6e 74 20 6e  ){.  const int n
31a0: 4d 65 72 67 65 53 6c 6f 74 20 3d 20 33 32 3b 0a  MergeSlot = 32;.
31b0: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20    Fts5HashEntry 
31c0: 2a 2a 61 70 3b 0a 20 20 46 74 73 35 48 61 73 68  **ap;.  Fts5Hash
31d0: 45 6e 74 72 79 20 2a 70 4c 69 73 74 3b 0a 20 20  Entry *pList;.  
31e0: 69 6e 74 20 69 53 6c 6f 74 3b 0a 20 20 69 6e 74  int iSlot;.  int
31f0: 20 69 3b 0a 0a 20 20 2a 70 70 53 6f 72 74 65 64   i;..  *ppSorted
3200: 20 3d 20 30 3b 0a 20 20 61 70 20 3d 20 73 71 6c   = 0;.  ap = sql
3210: 69 74 65 33 5f 6d 61 6c 6c 6f 63 36 34 28 73 69  ite3_malloc64(si
3220: 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74  zeof(Fts5HashEnt
3230: 72 79 2a 29 20 2a 20 6e 4d 65 72 67 65 53 6c 6f  ry*) * nMergeSlo
3240: 74 29 3b 0a 20 20 69 66 28 20 21 61 70 20 29 20  t);.  if( !ap ) 
3250: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f  return SQLITE_NO
3260: 4d 45 4d 3b 0a 20 20 6d 65 6d 73 65 74 28 61 70  MEM;.  memset(ap
3270: 2c 20 30 2c 20 73 69 7a 65 6f 66 28 46 74 73 35  , 0, sizeof(Fts5
3280: 48 61 73 68 45 6e 74 72 79 2a 29 20 2a 20 6e 4d  HashEntry*) * nM
3290: 65 72 67 65 53 6c 6f 74 29 3b 0a 0a 20 20 66 6f  ergeSlot);..  fo
32a0: 72 28 69 53 6c 6f 74 3d 30 3b 20 69 53 6c 6f 74  r(iSlot=0; iSlot
32b0: 3c 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 3b 20 69  <pHash->nSlot; i
32c0: 53 6c 6f 74 2b 2b 29 7b 0a 20 20 20 20 46 74 73  Slot++){.    Fts
32d0: 35 48 61 73 68 45 6e 74 72 79 20 2a 70 49 74 65  5HashEntry *pIte
32e0: 72 3b 0a 20 20 20 20 66 6f 72 28 70 49 74 65 72  r;.    for(pIter
32f0: 3d 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 53  =pHash->aSlot[iS
3300: 6c 6f 74 5d 3b 20 70 49 74 65 72 3b 20 70 49 74  lot]; pIter; pIt
3310: 65 72 3d 70 49 74 65 72 2d 3e 70 48 61 73 68 4e  er=pIter->pHashN
3320: 65 78 74 29 7b 0a 20 20 20 20 20 20 69 66 28 20  ext){.      if( 
3330: 70 54 65 72 6d 3d 3d 30 20 0a 20 20 20 20 20 20  pTerm==0 .      
3340: 20 7c 7c 20 28 70 49 74 65 72 2d 3e 6e 4b 65 79   || (pIter->nKey
3350: 2b 31 3e 3d 6e 54 65 72 6d 20 26 26 20 30 3d 3d  +1>=nTerm && 0==
3360: 6d 65 6d 63 6d 70 28 66 74 73 35 45 6e 74 72 79  memcmp(fts5Entry
3370: 4b 65 79 28 70 49 74 65 72 29 2c 20 70 54 65 72  Key(pIter), pTer
3380: 6d 2c 20 6e 54 65 72 6d 29 29 0a 20 20 20 20 20  m, nTerm)).     
3390: 20 29 7b 0a 20 20 20 20 20 20 20 20 46 74 73 35   ){.        Fts5
33a0: 48 61 73 68 45 6e 74 72 79 20 2a 70 45 6e 74 72  HashEntry *pEntr
33b0: 79 20 3d 20 70 49 74 65 72 3b 0a 20 20 20 20 20  y = pIter;.     
33c0: 20 20 20 70 45 6e 74 72 79 2d 3e 70 53 63 61 6e     pEntry->pScan
33d0: 4e 65 78 74 20 3d 20 30 3b 0a 20 20 20 20 20 20  Next = 0;.      
33e0: 20 20 66 6f 72 28 69 3d 30 3b 20 61 70 5b 69 5d    for(i=0; ap[i]
33f0: 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20  ; i++){.        
3400: 20 20 70 45 6e 74 72 79 20 3d 20 66 74 73 35 48    pEntry = fts5H
3410: 61 73 68 45 6e 74 72 79 4d 65 72 67 65 28 70 45  ashEntryMerge(pE
3420: 6e 74 72 79 2c 20 61 70 5b 69 5d 29 3b 0a 20 20  ntry, ap[i]);.  
3430: 20 20 20 20 20 20 20 20 61 70 5b 69 5d 20 3d 20          ap[i] = 
3440: 30 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20  0;.        }.   
3450: 20 20 20 20 20 61 70 5b 69 5d 20 3d 20 70 45 6e       ap[i] = pEn
3460: 74 72 79 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20  try;.      }.   
3470: 20 7d 0a 20 20 7d 0a 0a 20 20 70 4c 69 73 74 20   }.  }..  pList 
3480: 3d 20 30 3b 0a 20 20 66 6f 72 28 69 3d 30 3b 20  = 0;.  for(i=0; 
3490: 69 3c 6e 4d 65 72 67 65 53 6c 6f 74 3b 20 69 2b  i<nMergeSlot; i+
34a0: 2b 29 7b 0a 20 20 20 20 70 4c 69 73 74 20 3d 20  +){.    pList = 
34b0: 66 74 73 35 48 61 73 68 45 6e 74 72 79 4d 65 72  fts5HashEntryMer
34c0: 67 65 28 70 4c 69 73 74 2c 20 61 70 5b 69 5d 29  ge(pList, ap[i])
34d0: 3b 0a 20 20 7d 0a 0a 20 20 70 48 61 73 68 2d 3e  ;.  }..  pHash->
34e0: 6e 45 6e 74 72 79 20 3d 20 30 3b 0a 20 20 73 71  nEntry = 0;.  sq
34f0: 6c 69 74 65 33 5f 66 72 65 65 28 61 70 29 3b 0a  lite3_free(ap);.
3500: 20 20 2a 70 70 53 6f 72 74 65 64 20 3d 20 70 4c    *ppSorted = pL
3510: 69 73 74 3b 0a 20 20 72 65 74 75 72 6e 20 53 51  ist;.  return SQ
3520: 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a  LITE_OK;.}../*.*
3530: 2a 20 51 75 65 72 79 20 74 68 65 20 68 61 73 68  * Query the hash
3540: 20 74 61 62 6c 65 20 66 6f 72 20 61 20 64 6f 63   table for a doc
3550: 6c 69 73 74 20 61 73 73 6f 63 69 61 74 65 64 20  list associated 
3560: 77 69 74 68 20 74 65 72 6d 20 70 54 65 72 6d 2f  with term pTerm/
3570: 6e 54 65 72 6d 2e 0a 2a 2f 0a 69 6e 74 20 73 71  nTerm..*/.int sq
3580: 6c 69 74 65 33 46 74 73 35 48 61 73 68 51 75 65  lite3Fts5HashQue
3590: 72 79 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a  ry(.  Fts5Hash *
35a0: 70 48 61 73 68 2c 20 20 20 20 20 20 20 20 20 20  pHash,          
35b0: 20 20 20 20 20 20 2f 2a 20 48 61 73 68 20 74 61        /* Hash ta
35c0: 62 6c 65 20 74 6f 20 71 75 65 72 79 20 2a 2f 0a  ble to query */.
35d0: 20 20 69 6e 74 20 6e 50 72 65 2c 0a 20 20 63 6f    int nPre,.  co
35e0: 6e 73 74 20 63 68 61 72 20 2a 70 54 65 72 6d 2c  nst char *pTerm,
35f0: 20 69 6e 74 20 6e 54 65 72 6d 2c 20 20 20 2f 2a   int nTerm,   /*
3600: 20 51 75 65 72 79 20 74 65 72 6d 20 2a 2f 0a 20   Query term */. 
3610: 20 76 6f 69 64 20 2a 2a 70 70 4f 75 74 2c 20 20   void **ppOut,  
3620: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3630: 20 2f 2a 20 4f 55 54 3a 20 50 6f 69 6e 74 65 72   /* OUT: Pointer
3640: 20 74 6f 20 6e 65 77 20 6f 62 6a 65 63 74 20 2a   to new object *
3650: 2f 0a 20 20 69 6e 74 20 2a 70 6e 44 6f 63 6c 69  /.  int *pnDocli
3660: 73 74 20 20 20 20 20 20 20 20 20 20 20 20 20 20  st              
3670: 20 20 20 20 2f 2a 20 4f 55 54 3a 20 53 69 7a 65      /* OUT: Size
3680: 20 6f 66 20 64 6f 63 6c 69 73 74 20 69 6e 20 62   of doclist in b
3690: 79 74 65 73 20 2a 2f 0a 29 7b 0a 20 20 75 6e 73  ytes */.){.  uns
36a0: 69 67 6e 65 64 20 69 6e 74 20 69 48 61 73 68 20  igned int iHash 
36b0: 3d 20 66 74 73 35 48 61 73 68 4b 65 79 28 70 48  = fts5HashKey(pH
36c0: 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20 28 63 6f 6e  ash->nSlot, (con
36d0: 73 74 20 75 38 2a 29 70 54 65 72 6d 2c 20 6e 54  st u8*)pTerm, nT
36e0: 65 72 6d 29 3b 0a 20 20 63 68 61 72 20 2a 7a 4b  erm);.  char *zK
36f0: 65 79 20 3d 20 30 3b 0a 20 20 46 74 73 35 48 61  ey = 0;.  Fts5Ha
3700: 73 68 45 6e 74 72 79 20 2a 70 3b 0a 0a 20 20 66  shEntry *p;..  f
3710: 6f 72 28 70 3d 70 48 61 73 68 2d 3e 61 53 6c 6f  or(p=pHash->aSlo
3720: 74 5b 69 48 61 73 68 5d 3b 20 70 3b 20 70 3d 70  t[iHash]; p; p=p
3730: 2d 3e 70 48 61 73 68 4e 65 78 74 29 7b 0a 20 20  ->pHashNext){.  
3740: 20 20 7a 4b 65 79 20 3d 20 66 74 73 35 45 6e 74    zKey = fts5Ent
3750: 72 79 4b 65 79 28 70 29 3b 0a 20 20 20 20 61 73  ryKey(p);.    as
3760: 73 65 72 74 28 20 70 2d 3e 6e 4b 65 79 2b 31 3d  sert( p->nKey+1=
3770: 3d 28 69 6e 74 29 73 74 72 6c 65 6e 28 7a 4b 65  =(int)strlen(zKe
3780: 79 29 20 29 3b 0a 20 20 20 20 69 66 28 20 6e 54  y) );.    if( nT
3790: 65 72 6d 3d 3d 70 2d 3e 6e 4b 65 79 2b 31 20 26  erm==p->nKey+1 &
37a0: 26 20 6d 65 6d 63 6d 70 28 7a 4b 65 79 2c 20 70  & memcmp(zKey, p
37b0: 54 65 72 6d 2c 20 6e 54 65 72 6d 29 3d 3d 30 20  Term, nTerm)==0 
37c0: 29 20 62 72 65 61 6b 3b 0a 20 20 7d 0a 0a 20 20  ) break;.  }..  
37d0: 69 66 28 20 70 20 29 7b 0a 20 20 20 20 69 6e 74  if( p ){.    int
37e0: 20 6e 48 61 73 68 50 72 65 20 3d 20 73 69 7a 65   nHashPre = size
37f0: 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79  of(Fts5HashEntry
3800: 29 20 2b 20 6e 54 65 72 6d 20 2b 20 31 3b 0a 20  ) + nTerm + 1;. 
3810: 20 20 20 69 6e 74 20 6e 4c 69 73 74 20 3d 20 70     int nList = p
3820: 2d 3e 6e 44 61 74 61 20 2d 20 6e 48 61 73 68 50  ->nData - nHashP
3830: 72 65 3b 0a 20 20 20 20 75 38 20 2a 70 52 65 74  re;.    u8 *pRet
3840: 20 3d 20 28 75 38 2a 29 28 2a 70 70 4f 75 74 20   = (u8*)(*ppOut 
3850: 3d 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63  = sqlite3_malloc
3860: 36 34 28 6e 50 72 65 20 2b 20 6e 4c 69 73 74 20  64(nPre + nList 
3870: 2b 20 31 30 29 29 3b 0a 20 20 20 20 69 66 28 20  + 10));.    if( 
3880: 70 52 65 74 20 29 7b 0a 20 20 20 20 20 20 46 74  pRet ){.      Ft
3890: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 46 61  s5HashEntry *pFa
38a0: 75 78 20 3d 20 28 46 74 73 35 48 61 73 68 45 6e  ux = (Fts5HashEn
38b0: 74 72 79 2a 29 26 70 52 65 74 5b 6e 50 72 65 2d  try*)&pRet[nPre-
38c0: 6e 48 61 73 68 50 72 65 5d 3b 0a 20 20 20 20 20  nHashPre];.     
38d0: 20 6d 65 6d 63 70 79 28 26 70 52 65 74 5b 6e 50   memcpy(&pRet[nP
38e0: 72 65 5d 2c 20 26 28 28 75 38 2a 29 70 29 5b 6e  re], &((u8*)p)[n
38f0: 48 61 73 68 50 72 65 5d 2c 20 6e 4c 69 73 74 29  HashPre], nList)
3900: 3b 0a 20 20 20 20 20 20 6e 4c 69 73 74 20 2b 3d  ;.      nList +=
3910: 20 66 74 73 35 48 61 73 68 41 64 64 50 6f 73 6c   fts5HashAddPosl
3920: 69 73 74 53 69 7a 65 28 70 48 61 73 68 2c 20 70  istSize(pHash, p
3930: 2c 20 70 46 61 75 78 29 3b 0a 20 20 20 20 20 20  , pFaux);.      
3940: 2a 70 6e 44 6f 63 6c 69 73 74 20 3d 20 6e 4c 69  *pnDoclist = nLi
3950: 73 74 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20  st;.    }else{. 
3960: 20 20 20 20 20 2a 70 6e 44 6f 63 6c 69 73 74 20       *pnDoclist 
3970: 3d 20 30 3b 0a 20 20 20 20 20 20 72 65 74 75 72  = 0;.      retur
3980: 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a  n SQLITE_NOMEM;.
3990: 20 20 20 20 7d 0a 20 20 7d 65 6c 73 65 7b 0a 20      }.  }else{. 
39a0: 20 20 20 2a 70 70 4f 75 74 20 3d 20 30 3b 0a 20     *ppOut = 0;. 
39b0: 20 20 20 2a 70 6e 44 6f 63 6c 69 73 74 20 3d 20     *pnDoclist = 
39c0: 30 3b 0a 20 20 7d 0a 0a 20 20 72 65 74 75 72 6e  0;.  }..  return
39d0: 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 69   SQLITE_OK;.}..i
39e0: 6e 74 20 73 71 6c 69 74 65 33 46 74 73 35 48 61  nt sqlite3Fts5Ha
39f0: 73 68 53 63 61 6e 49 6e 69 74 28 0a 20 20 46 74  shScanInit(.  Ft
3a00: 73 35 48 61 73 68 20 2a 70 2c 20 20 20 20 20 20  s5Hash *p,      
3a10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
3a20: 20 48 61 73 68 20 74 61 62 6c 65 20 74 6f 20 71   Hash table to q
3a30: 75 65 72 79 20 2a 2f 0a 20 20 63 6f 6e 73 74 20  uery */.  const 
3a40: 63 68 61 72 20 2a 70 54 65 72 6d 2c 20 69 6e 74  char *pTerm, int
3a50: 20 6e 54 65 72 6d 20 20 20 20 2f 2a 20 51 75 65   nTerm    /* Que
3a60: 72 79 20 70 72 65 66 69 78 20 2a 2f 0a 29 7b 0a  ry prefix */.){.
3a70: 20 20 72 65 74 75 72 6e 20 66 74 73 35 48 61 73    return fts5Has
3a80: 68 45 6e 74 72 79 53 6f 72 74 28 70 2c 20 70 54  hEntrySort(p, pT
3a90: 65 72 6d 2c 20 6e 54 65 72 6d 2c 20 26 70 2d 3e  erm, nTerm, &p->
3aa0: 70 53 63 61 6e 29 3b 0a 7d 0a 0a 76 6f 69 64 20  pScan);.}..void 
3ab0: 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 53  sqlite3Fts5HashS
3ac0: 63 61 6e 4e 65 78 74 28 46 74 73 35 48 61 73 68  canNext(Fts5Hash
3ad0: 20 2a 70 29 7b 0a 20 20 61 73 73 65 72 74 28 20   *p){.  assert( 
3ae0: 21 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68  !sqlite3Fts5Hash
3af0: 53 63 61 6e 45 6f 66 28 70 29 20 29 3b 0a 20 20  ScanEof(p) );.  
3b00: 70 2d 3e 70 53 63 61 6e 20 3d 20 70 2d 3e 70 53  p->pScan = p->pS
3b10: 63 61 6e 2d 3e 70 53 63 61 6e 4e 65 78 74 3b 0a  can->pScanNext;.
3b20: 7d 0a 0a 69 6e 74 20 73 71 6c 69 74 65 33 46 74  }..int sqlite3Ft
3b30: 73 35 48 61 73 68 53 63 61 6e 45 6f 66 28 46 74  s5HashScanEof(Ft
3b40: 73 35 48 61 73 68 20 2a 70 29 7b 0a 20 20 72 65  s5Hash *p){.  re
3b50: 74 75 72 6e 20 28 70 2d 3e 70 53 63 61 6e 3d 3d  turn (p->pScan==
3b60: 30 29 3b 0a 7d 0a 0a 76 6f 69 64 20 73 71 6c 69  0);.}..void sqli
3b70: 74 65 33 46 74 73 35 48 61 73 68 53 63 61 6e 45  te3Fts5HashScanE
3b80: 6e 74 72 79 28 0a 20 20 46 74 73 35 48 61 73 68  ntry(.  Fts5Hash
3b90: 20 2a 70 48 61 73 68 2c 0a 20 20 63 6f 6e 73 74   *pHash,.  const
3ba0: 20 63 68 61 72 20 2a 2a 70 7a 54 65 72 6d 2c 20   char **pzTerm, 
3bb0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55             /* OU
3bc0: 54 3a 20 74 65 72 6d 20 28 6e 75 6c 2d 74 65 72  T: term (nul-ter
3bd0: 6d 69 6e 61 74 65 64 29 20 2a 2f 0a 20 20 63 6f  minated) */.  co
3be0: 6e 73 74 20 75 38 20 2a 2a 70 70 44 6f 63 6c 69  nst u8 **ppDocli
3bf0: 73 74 2c 20 20 20 20 20 20 20 20 20 20 20 2f 2a  st,           /*
3c00: 20 4f 55 54 3a 20 70 6f 69 6e 74 65 72 20 74 6f   OUT: pointer to
3c10: 20 64 6f 63 6c 69 73 74 20 2a 2f 0a 20 20 69 6e   doclist */.  in
3c20: 74 20 2a 70 6e 44 6f 63 6c 69 73 74 20 20 20 20  t *pnDoclist    
3c30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
3c40: 20 4f 55 54 3a 20 73 69 7a 65 20 6f 66 20 64 6f   OUT: size of do
3c50: 63 6c 69 73 74 20 69 6e 20 62 79 74 65 73 20 2a  clist in bytes *
3c60: 2f 0a 29 7b 0a 20 20 46 74 73 35 48 61 73 68 45  /.){.  Fts5HashE
3c70: 6e 74 72 79 20 2a 70 3b 0a 20 20 69 66 28 20 28  ntry *p;.  if( (
3c80: 70 20 3d 20 70 48 61 73 68 2d 3e 70 53 63 61 6e  p = pHash->pScan
3c90: 29 20 29 7b 0a 20 20 20 20 63 68 61 72 20 2a 7a  ) ){.    char *z
3ca0: 4b 65 79 20 3d 20 66 74 73 35 45 6e 74 72 79 4b  Key = fts5EntryK
3cb0: 65 79 28 70 29 3b 0a 20 20 20 20 69 6e 74 20 6e  ey(p);.    int n
3cc0: 54 65 72 6d 20 3d 20 28 69 6e 74 29 73 74 72 6c  Term = (int)strl
3cd0: 65 6e 28 7a 4b 65 79 29 3b 0a 20 20 20 20 66 74  en(zKey);.    ft
3ce0: 73 35 48 61 73 68 41 64 64 50 6f 73 6c 69 73 74  s5HashAddPoslist
3cf0: 53 69 7a 65 28 70 48 61 73 68 2c 20 70 2c 20 30  Size(pHash, p, 0
3d00: 29 3b 0a 20 20 20 20 2a 70 7a 54 65 72 6d 20 3d  );.    *pzTerm =
3d10: 20 7a 4b 65 79 3b 0a 20 20 20 20 2a 70 70 44 6f   zKey;.    *ppDo
3d20: 63 6c 69 73 74 20 3d 20 28 63 6f 6e 73 74 20 75  clist = (const u
3d30: 38 2a 29 26 7a 4b 65 79 5b 6e 54 65 72 6d 2b 31  8*)&zKey[nTerm+1
3d40: 5d 3b 0a 20 20 20 20 2a 70 6e 44 6f 63 6c 69 73  ];.    *pnDoclis
3d50: 74 20 3d 20 70 2d 3e 6e 44 61 74 61 20 2d 20 28  t = p->nData - (
3d60: 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45  sizeof(Fts5HashE
3d70: 6e 74 72 79 29 20 2b 20 6e 54 65 72 6d 20 2b 20  ntry) + nTerm + 
3d80: 31 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20  1);.  }else{.   
3d90: 20 2a 70 7a 54 65 72 6d 20 3d 20 30 3b 0a 20 20   *pzTerm = 0;.  
3da0: 20 20 2a 70 70 44 6f 63 6c 69 73 74 20 3d 20 30    *ppDoclist = 0
3db0: 3b 0a 20 20 20 20 2a 70 6e 44 6f 63 6c 69 73 74  ;.    *pnDoclist
3dc0: 20 3d 20 30 3b 0a 20 20 7d 0a 7d 0a               = 0;.  }.}.