/ Hex Artifact Content
Login

Artifact ad22ab3d89828cf3d996f784b7a6452ee16a940aa46abe466a1f14aa3d42bbf2:


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 75 6e 73  [i] ){.      uns
1310: 69 67 6e 65 64 20 69 6e 74 20 69 48 61 73 68 3b  igned int iHash;
1320: 0a 20 20 20 20 20 20 46 74 73 35 48 61 73 68 45  .      Fts5HashE
1330: 6e 74 72 79 20 2a 70 20 3d 20 61 70 4f 6c 64 5b  ntry *p = apOld[
1340: 69 5d 3b 0a 20 20 20 20 20 20 61 70 4f 6c 64 5b  i];.      apOld[
1350: 69 5d 20 3d 20 70 2d 3e 70 48 61 73 68 4e 65 78  i] = p->pHashNex
1360: 74 3b 0a 20 20 20 20 20 20 69 48 61 73 68 20 3d  t;.      iHash =
1370: 20 66 74 73 35 48 61 73 68 4b 65 79 28 6e 4e 65   fts5HashKey(nNe
1380: 77 2c 20 28 75 38 2a 29 66 74 73 35 45 6e 74 72  w, (u8*)fts5Entr
1390: 79 4b 65 79 28 70 29 2c 0a 20 20 20 20 20 20 20  yKey(p),.       
13a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
13b0: 20 20 20 28 69 6e 74 29 73 74 72 6c 65 6e 28 66     (int)strlen(f
13c0: 74 73 35 45 6e 74 72 79 4b 65 79 28 70 29 29 29  ts5EntryKey(p)))
13d0: 3b 0a 20 20 20 20 20 20 70 2d 3e 70 48 61 73 68  ;.      p->pHash
13e0: 4e 65 78 74 20 3d 20 61 70 4e 65 77 5b 69 48 61  Next = apNew[iHa
13f0: 73 68 5d 3b 0a 20 20 20 20 20 20 61 70 4e 65 77  sh];.      apNew
1400: 5b 69 48 61 73 68 5d 20 3d 20 70 3b 0a 20 20 20  [iHash] = p;.   
1410: 20 7d 0a 20 20 7d 0a 0a 20 20 73 71 6c 69 74 65   }.  }..  sqlite
1420: 33 5f 66 72 65 65 28 61 70 4f 6c 64 29 3b 0a 20  3_free(apOld);. 
1430: 20 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 20 3d 20   pHash->nSlot = 
1440: 6e 4e 65 77 3b 0a 20 20 70 48 61 73 68 2d 3e 61  nNew;.  pHash->a
1450: 53 6c 6f 74 20 3d 20 61 70 4e 65 77 3b 0a 20 20  Slot = apNew;.  
1460: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b  return SQLITE_OK
1470: 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 76 6f 69 64  ;.}..static void
1480: 20 66 74 73 35 48 61 73 68 41 64 64 50 6f 73 6c   fts5HashAddPosl
1490: 69 73 74 53 69 7a 65 28 46 74 73 35 48 61 73 68  istSize(Fts5Hash
14a0: 20 2a 70 48 61 73 68 2c 20 46 74 73 35 48 61 73   *pHash, Fts5Has
14b0: 68 45 6e 74 72 79 20 2a 70 29 7b 0a 20 20 69 66  hEntry *p){.  if
14c0: 28 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20  ( p->iSzPoslist 
14d0: 29 7b 0a 20 20 20 20 75 38 20 2a 70 50 74 72 20  ){.    u8 *pPtr 
14e0: 3d 20 28 75 38 2a 29 70 3b 0a 20 20 20 20 69 66  = (u8*)p;.    if
14f0: 28 20 70 48 61 73 68 2d 3e 65 44 65 74 61 69 6c  ( pHash->eDetail
1500: 3d 3d 46 54 53 35 5f 44 45 54 41 49 4c 5f 4e 4f  ==FTS5_DETAIL_NO
1510: 4e 45 20 29 7b 0a 20 20 20 20 20 20 61 73 73 65  NE ){.      asse
1520: 72 74 28 20 70 2d 3e 6e 44 61 74 61 3d 3d 70 2d  rt( p->nData==p-
1530: 3e 69 53 7a 50 6f 73 6c 69 73 74 20 29 3b 0a 20  >iSzPoslist );. 
1540: 20 20 20 20 20 69 66 28 20 70 2d 3e 62 44 65 6c       if( p->bDel
1550: 20 29 7b 0a 20 20 20 20 20 20 20 20 70 50 74 72   ){.        pPtr
1560: 5b 70 2d 3e 6e 44 61 74 61 2b 2b 5d 20 3d 20 30  [p->nData++] = 0
1570: 78 30 30 3b 0a 20 20 20 20 20 20 20 20 69 66 28  x00;.        if(
1580: 20 70 2d 3e 62 43 6f 6e 74 65 6e 74 20 29 7b 0a   p->bContent ){.
1590: 20 20 20 20 20 20 20 20 20 20 70 50 74 72 5b 70            pPtr[p
15a0: 2d 3e 6e 44 61 74 61 2b 2b 5d 20 3d 20 30 78 30  ->nData++] = 0x0
15b0: 30 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20  0;.        }.   
15c0: 20 20 20 7d 0a 20 20 20 20 7d 65 6c 73 65 7b 0a     }.    }else{.
15d0: 20 20 20 20 20 20 69 6e 74 20 6e 53 7a 20 3d 20        int nSz = 
15e0: 28 70 2d 3e 6e 44 61 74 61 20 2d 20 70 2d 3e 69  (p->nData - p->i
15f0: 53 7a 50 6f 73 6c 69 73 74 20 2d 20 31 29 3b 20  SzPoslist - 1); 
1600: 20 20 20 20 20 20 2f 2a 20 53 69 7a 65 20 69 6e        /* Size in
1610: 20 62 79 74 65 73 20 2a 2f 0a 20 20 20 20 20 20   bytes */.      
1620: 69 6e 74 20 6e 50 6f 73 20 3d 20 6e 53 7a 2a 32  int nPos = nSz*2
1630: 20 2b 20 70 2d 3e 62 44 65 6c 3b 20 20 20 20 20   + p->bDel;     
1640: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1650: 2f 2a 20 56 61 6c 75 65 20 6f 66 20 6e 50 6f 73  /* Value of nPos
1660: 20 66 69 65 6c 64 20 2a 2f 0a 0a 20 20 20 20 20   field */..     
1670: 20 61 73 73 65 72 74 28 20 70 2d 3e 62 44 65 6c   assert( p->bDel
1680: 3d 3d 30 20 7c 7c 20 70 2d 3e 62 44 65 6c 3d 3d  ==0 || p->bDel==
1690: 31 20 29 3b 0a 20 20 20 20 20 20 69 66 28 20 6e  1 );.      if( n
16a0: 50 6f 73 3c 3d 31 32 37 20 29 7b 0a 20 20 20 20  Pos<=127 ){.    
16b0: 20 20 20 20 70 50 74 72 5b 70 2d 3e 69 53 7a 50      pPtr[p->iSzP
16c0: 6f 73 6c 69 73 74 5d 20 3d 20 28 75 38 29 6e 50  oslist] = (u8)nP
16d0: 6f 73 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b  os;.      }else{
16e0: 0a 20 20 20 20 20 20 20 20 69 6e 74 20 6e 42 79  .        int nBy
16f0: 74 65 20 3d 20 73 71 6c 69 74 65 33 46 74 73 35  te = sqlite3Fts5
1700: 47 65 74 56 61 72 69 6e 74 4c 65 6e 28 28 75 33  GetVarintLen((u3
1710: 32 29 6e 50 6f 73 29 3b 0a 20 20 20 20 20 20 20  2)nPos);.       
1720: 20 6d 65 6d 6d 6f 76 65 28 26 70 50 74 72 5b 70   memmove(&pPtr[p
1730: 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 2b 20 6e  ->iSzPoslist + n
1740: 42 79 74 65 5d 2c 20 26 70 50 74 72 5b 70 2d 3e  Byte], &pPtr[p->
1750: 69 53 7a 50 6f 73 6c 69 73 74 20 2b 20 31 5d 2c  iSzPoslist + 1],
1760: 20 6e 53 7a 29 3b 0a 20 20 20 20 20 20 20 20 73   nSz);.        s
1770: 71 6c 69 74 65 33 46 74 73 35 50 75 74 56 61 72  qlite3Fts5PutVar
1780: 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e 69 53 7a  int(&pPtr[p->iSz
1790: 50 6f 73 6c 69 73 74 5d 2c 20 6e 50 6f 73 29 3b  Poslist], nPos);
17a0: 0a 20 20 20 20 20 20 20 20 70 2d 3e 6e 44 61 74  .        p->nDat
17b0: 61 20 2b 3d 20 28 6e 42 79 74 65 2d 31 29 3b 0a  a += (nByte-1);.
17c0: 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a 0a 20        }.    }.. 
17d0: 20 20 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74     p->iSzPoslist
17e0: 20 3d 20 30 3b 0a 20 20 20 20 70 2d 3e 62 44 65   = 0;.    p->bDe
17f0: 6c 20 3d 20 30 3b 0a 20 20 20 20 70 2d 3e 62 43  l = 0;.    p->bC
1800: 6f 6e 74 65 6e 74 20 3d 20 30 3b 0a 20 20 7d 0a  ontent = 0;.  }.
1810: 7d 0a 0a 2f 2a 0a 2a 2a 20 41 64 64 20 61 6e 20  }../*.** Add an 
1820: 65 6e 74 72 79 20 74 6f 20 74 68 65 20 69 6e 2d  entry to the in-
1830: 6d 65 6d 6f 72 79 20 68 61 73 68 20 74 61 62 6c  memory hash tabl
1840: 65 2e 20 54 68 65 20 6b 65 79 20 69 73 20 74 68  e. The key is th
1850: 65 20 63 6f 6e 63 61 74 65 6e 61 74 69 6f 6e 0a  e concatenation.
1860: 2a 2a 20 6f 66 20 62 42 79 74 65 20 61 6e 64 20  ** of bByte and 
1870: 28 70 54 6f 6b 65 6e 2f 6e 54 6f 6b 65 6e 29 2e  (pToken/nToken).
1880: 20 54 68 65 20 76 61 6c 75 65 20 69 73 20 28 69   The value is (i
1890: 52 6f 77 69 64 2f 69 43 6f 6c 2f 69 50 6f 73 29  Rowid/iCol/iPos)
18a0: 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 20 28 62 42 79  ..**.**     (bBy
18b0: 74 65 20 7c 7c 20 70 54 6f 6b 65 6e 29 20 2d 3e  te || pToken) ->
18c0: 20 28 69 52 6f 77 69 64 2c 69 43 6f 6c 2c 69 50   (iRowid,iCol,iP
18d0: 6f 73 29 0a 2a 2a 0a 2a 2a 20 4f 72 2c 20 69 66  os).**.** Or, if
18e0: 20 69 43 6f 6c 20 69 73 20 6e 65 67 61 74 69 76   iCol is negativ
18f0: 65 2c 20 74 68 65 6e 20 74 68 65 20 76 61 6c 75  e, then the valu
1900: 65 20 69 73 20 61 20 64 65 6c 65 74 65 20 6d 61  e is a delete ma
1910: 72 6b 65 72 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c  rker..*/.int sql
1920: 69 74 65 33 46 74 73 35 48 61 73 68 57 72 69 74  ite3Fts5HashWrit
1930: 65 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a 70  e(.  Fts5Hash *p
1940: 48 61 73 68 2c 0a 20 20 69 36 34 20 69 52 6f 77  Hash,.  i64 iRow
1950: 69 64 2c 20 20 20 20 20 20 20 20 20 20 20 20 20  id,             
1960: 20 20 20 20 20 20 20 20 2f 2a 20 52 6f 77 69 64          /* Rowid
1970: 20 66 6f 72 20 74 68 69 73 20 65 6e 74 72 79 20   for this entry 
1980: 2a 2f 0a 20 20 69 6e 74 20 69 43 6f 6c 2c 20 20  */.  int iCol,  
1990: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
19a0: 20 20 20 20 20 2f 2a 20 43 6f 6c 75 6d 6e 20 74       /* Column t
19b0: 6f 6b 65 6e 20 61 70 70 65 61 72 73 20 69 6e 20  oken appears in 
19c0: 28 2d 76 65 20 2d 3e 20 64 65 6c 65 74 65 29 20  (-ve -> delete) 
19d0: 2a 2f 0a 20 20 69 6e 74 20 69 50 6f 73 2c 20 20  */.  int iPos,  
19e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
19f0: 20 20 20 20 20 2f 2a 20 50 6f 73 69 74 69 6f 6e       /* Position
1a00: 20 6f 66 20 74 6f 6b 65 6e 20 77 69 74 68 69 6e   of token within
1a10: 20 63 6f 6c 75 6d 6e 20 2a 2f 0a 20 20 63 68 61   column */.  cha
1a20: 72 20 62 42 79 74 65 2c 20 20 20 20 20 20 20 20  r bByte,        
1a30: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
1a40: 46 69 72 73 74 20 62 79 74 65 20 6f 66 20 74 6f  First byte of to
1a50: 6b 65 6e 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63  ken */.  const c
1a60: 68 61 72 20 2a 70 54 6f 6b 65 6e 2c 20 69 6e 74  har *pToken, int
1a70: 20 6e 54 6f 6b 65 6e 20 20 2f 2a 20 54 6f 6b 65   nToken  /* Toke
1a80: 6e 20 74 6f 20 61 64 64 20 6f 72 20 72 65 6d 6f  n to add or remo
1a90: 76 65 20 74 6f 20 6f 72 20 66 72 6f 6d 20 69 6e  ve to or from in
1aa0: 64 65 78 20 2a 2f 0a 29 7b 0a 20 20 75 6e 73 69  dex */.){.  unsi
1ab0: 67 6e 65 64 20 69 6e 74 20 69 48 61 73 68 3b 0a  gned int iHash;.
1ac0: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20    Fts5HashEntry 
1ad0: 2a 70 3b 0a 20 20 75 38 20 2a 70 50 74 72 3b 0a  *p;.  u8 *pPtr;.
1ae0: 20 20 69 6e 74 20 6e 49 6e 63 72 20 3d 20 30 3b    int nIncr = 0;
1af0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1b00: 20 20 2f 2a 20 41 6d 6f 75 6e 74 20 74 6f 20 69    /* Amount to i
1b10: 6e 63 72 65 6d 65 6e 74 20 28 2a 70 48 61 73 68  ncrement (*pHash
1b20: 2d 3e 70 6e 42 79 74 65 29 20 62 79 20 2a 2f 0a  ->pnByte) by */.
1b30: 20 20 69 6e 74 20 62 4e 65 77 3b 20 20 20 20 20    int bNew;     
1b40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1b50: 20 20 2f 2a 20 49 66 20 6e 6f 6e 2d 64 65 6c 65    /* If non-dele
1b60: 74 65 20 65 6e 74 72 79 20 73 68 6f 75 6c 64 20  te entry should 
1b70: 62 65 20 77 72 69 74 74 65 6e 20 2a 2f 0a 20 20  be written */.  
1b80: 0a 20 20 62 4e 65 77 20 3d 20 28 70 48 61 73 68  .  bNew = (pHash
1b90: 2d 3e 65 44 65 74 61 69 6c 3d 3d 46 54 53 35 5f  ->eDetail==FTS5_
1ba0: 44 45 54 41 49 4c 5f 46 55 4c 4c 29 3b 0a 0a 20  DETAIL_FULL);.. 
1bb0: 20 2f 2a 20 41 74 74 65 6d 70 74 20 74 6f 20 6c   /* Attempt to l
1bc0: 6f 63 61 74 65 20 61 6e 20 65 78 69 73 74 69 6e  ocate an existin
1bd0: 67 20 68 61 73 68 20 65 6e 74 72 79 20 2a 2f 0a  g hash entry */.
1be0: 20 20 69 48 61 73 68 20 3d 20 66 74 73 35 48 61    iHash = fts5Ha
1bf0: 73 68 4b 65 79 32 28 70 48 61 73 68 2d 3e 6e 53  shKey2(pHash->nS
1c00: 6c 6f 74 2c 20 28 75 38 29 62 42 79 74 65 2c 20  lot, (u8)bByte, 
1c10: 28 63 6f 6e 73 74 20 75 38 2a 29 70 54 6f 6b 65  (const u8*)pToke
1c20: 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 66 6f  n, nToken);.  fo
1c30: 72 28 70 3d 70 48 61 73 68 2d 3e 61 53 6c 6f 74  r(p=pHash->aSlot
1c40: 5b 69 48 61 73 68 5d 3b 20 70 3b 20 70 3d 70 2d  [iHash]; p; p=p-
1c50: 3e 70 48 61 73 68 4e 65 78 74 29 7b 0a 20 20 20  >pHashNext){.   
1c60: 20 63 68 61 72 20 2a 7a 4b 65 79 20 3d 20 66 74   char *zKey = ft
1c70: 73 35 45 6e 74 72 79 4b 65 79 28 70 29 3b 0a 20  s5EntryKey(p);. 
1c80: 20 20 20 69 66 28 20 7a 4b 65 79 5b 30 5d 3d 3d     if( zKey[0]==
1c90: 62 42 79 74 65 20 0a 20 20 20 20 20 26 26 20 70  bByte .     && p
1ca0: 2d 3e 6e 4b 65 79 3d 3d 6e 54 6f 6b 65 6e 0a 20  ->nKey==nToken. 
1cb0: 20 20 20 20 26 26 20 6d 65 6d 63 6d 70 28 26 7a      && memcmp(&z
1cc0: 4b 65 79 5b 31 5d 2c 20 70 54 6f 6b 65 6e 2c 20  Key[1], pToken, 
1cd0: 6e 54 6f 6b 65 6e 29 3d 3d 30 20 0a 20 20 20 20  nToken)==0 .    
1ce0: 29 7b 0a 20 20 20 20 20 20 62 72 65 61 6b 3b 0a  ){.      break;.
1cf0: 20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 2f 2a 20      }.  }..  /* 
1d00: 49 66 20 61 6e 20 65 78 69 73 74 69 6e 67 20 68  If an existing h
1d10: 61 73 68 20 65 6e 74 72 79 20 63 61 6e 6e 6f 74  ash entry cannot
1d20: 20 62 65 20 66 6f 75 6e 64 2c 20 63 72 65 61 74   be found, creat
1d30: 65 20 61 20 6e 65 77 20 6f 6e 65 2e 20 2a 2f 0a  e a new one. */.
1d40: 20 20 69 66 28 20 70 3d 3d 30 20 29 7b 0a 20 20    if( p==0 ){.  
1d50: 20 20 2f 2a 20 46 69 67 75 72 65 20 6f 75 74 20    /* Figure out 
1d60: 68 6f 77 20 6d 75 63 68 20 73 70 61 63 65 20 74  how much space t
1d70: 6f 20 61 6c 6c 6f 63 61 74 65 20 2a 2f 0a 20 20  o allocate */.  
1d80: 20 20 63 68 61 72 20 2a 7a 4b 65 79 3b 0a 20 20    char *zKey;.  
1d90: 20 20 69 6e 74 20 6e 42 79 74 65 20 3d 20 73 69    int nByte = si
1da0: 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74  zeof(Fts5HashEnt
1db0: 72 79 29 20 2b 20 28 6e 54 6f 6b 65 6e 2b 31 29  ry) + (nToken+1)
1dc0: 20 2b 20 31 20 2b 20 36 34 3b 0a 20 20 20 20 69   + 1 + 64;.    i
1dd0: 66 28 20 6e 42 79 74 65 3c 31 32 38 20 29 20 6e  f( nByte<128 ) n
1de0: 42 79 74 65 20 3d 20 31 32 38 3b 0a 0a 20 20 20  Byte = 128;..   
1df0: 20 2f 2a 20 47 72 6f 77 20 74 68 65 20 46 74 73   /* Grow the Fts
1e00: 35 48 61 73 68 2e 61 53 6c 6f 74 5b 5d 20 61 72  5Hash.aSlot[] ar
1e10: 72 61 79 20 69 66 20 6e 65 63 65 73 73 61 72 79  ray if necessary
1e20: 2e 20 2a 2f 0a 20 20 20 20 69 66 28 20 28 70 48  . */.    if( (pH
1e30: 61 73 68 2d 3e 6e 45 6e 74 72 79 2a 32 29 3e 3d  ash->nEntry*2)>=
1e40: 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 20 29 7b 0a  pHash->nSlot ){.
1e50: 20 20 20 20 20 20 69 6e 74 20 72 63 20 3d 20 66        int rc = f
1e60: 74 73 35 48 61 73 68 52 65 73 69 7a 65 28 70 48  ts5HashResize(pH
1e70: 61 73 68 29 3b 0a 20 20 20 20 20 20 69 66 28 20  ash);.      if( 
1e80: 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 20  rc!=SQLITE_OK ) 
1e90: 72 65 74 75 72 6e 20 72 63 3b 0a 20 20 20 20 20  return rc;.     
1ea0: 20 69 48 61 73 68 20 3d 20 66 74 73 35 48 61 73   iHash = fts5Has
1eb0: 68 4b 65 79 32 28 70 48 61 73 68 2d 3e 6e 53 6c  hKey2(pHash->nSl
1ec0: 6f 74 2c 20 28 75 38 29 62 42 79 74 65 2c 20 28  ot, (u8)bByte, (
1ed0: 63 6f 6e 73 74 20 75 38 2a 29 70 54 6f 6b 65 6e  const u8*)pToken
1ee0: 2c 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 20 20 7d  , nToken);.    }
1ef0: 0a 0a 20 20 20 20 2f 2a 20 41 6c 6c 6f 63 61 74  ..    /* Allocat
1f00: 65 20 6e 65 77 20 46 74 73 35 48 61 73 68 45 6e  e new Fts5HashEn
1f10: 74 72 79 20 61 6e 64 20 61 64 64 20 69 74 20 74  try and add it t
1f20: 6f 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65  o the hash table
1f30: 2e 20 2a 2f 0a 20 20 20 20 70 20 3d 20 28 46 74  . */.    p = (Ft
1f40: 73 35 48 61 73 68 45 6e 74 72 79 2a 29 73 71 6c  s5HashEntry*)sql
1f50: 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e 42 79 74  ite3_malloc(nByt
1f60: 65 29 3b 0a 20 20 20 20 69 66 28 20 21 70 20 29  e);.    if( !p )
1f70: 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e   return SQLITE_N
1f80: 4f 4d 45 4d 3b 0a 20 20 20 20 6d 65 6d 73 65 74  OMEM;.    memset
1f90: 28 70 2c 20 30 2c 20 73 69 7a 65 6f 66 28 46 74  (p, 0, sizeof(Ft
1fa0: 73 35 48 61 73 68 45 6e 74 72 79 29 29 3b 0a 20  s5HashEntry));. 
1fb0: 20 20 20 70 2d 3e 6e 41 6c 6c 6f 63 20 3d 20 6e     p->nAlloc = n
1fc0: 42 79 74 65 3b 0a 20 20 20 20 7a 4b 65 79 20 3d  Byte;.    zKey =
1fd0: 20 66 74 73 35 45 6e 74 72 79 4b 65 79 28 70 29   fts5EntryKey(p)
1fe0: 3b 0a 20 20 20 20 7a 4b 65 79 5b 30 5d 20 3d 20  ;.    zKey[0] = 
1ff0: 62 42 79 74 65 3b 0a 20 20 20 20 6d 65 6d 63 70  bByte;.    memcp
2000: 79 28 26 7a 4b 65 79 5b 31 5d 2c 20 70 54 6f 6b  y(&zKey[1], pTok
2010: 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 20  en, nToken);.   
2020: 20 61 73 73 65 72 74 28 20 69 48 61 73 68 3d 3d   assert( iHash==
2030: 66 74 73 35 48 61 73 68 4b 65 79 28 70 48 61 73  fts5HashKey(pHas
2040: 68 2d 3e 6e 53 6c 6f 74 2c 20 28 75 38 2a 29 7a  h->nSlot, (u8*)z
2050: 4b 65 79 2c 20 6e 54 6f 6b 65 6e 2b 31 29 20 29  Key, nToken+1) )
2060: 3b 0a 20 20 20 20 70 2d 3e 6e 4b 65 79 20 3d 20  ;.    p->nKey = 
2070: 6e 54 6f 6b 65 6e 3b 0a 20 20 20 20 7a 4b 65 79  nToken;.    zKey
2080: 5b 6e 54 6f 6b 65 6e 2b 31 5d 20 3d 20 27 5c 30  [nToken+1] = '\0
2090: 27 3b 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20  ';.    p->nData 
20a0: 3d 20 6e 54 6f 6b 65 6e 2b 31 20 2b 20 31 20 2b  = nToken+1 + 1 +
20b0: 20 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68   sizeof(Fts5Hash
20c0: 45 6e 74 72 79 29 3b 0a 20 20 20 20 70 2d 3e 70  Entry);.    p->p
20d0: 48 61 73 68 4e 65 78 74 20 3d 20 70 48 61 73 68  HashNext = pHash
20e0: 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d 3b 0a  ->aSlot[iHash];.
20f0: 20 20 20 20 70 48 61 73 68 2d 3e 61 53 6c 6f 74      pHash->aSlot
2100: 5b 69 48 61 73 68 5d 20 3d 20 70 3b 0a 20 20 20  [iHash] = p;.   
2110: 20 70 48 61 73 68 2d 3e 6e 45 6e 74 72 79 2b 2b   pHash->nEntry++
2120: 3b 0a 0a 20 20 20 20 2f 2a 20 41 64 64 20 74 68  ;..    /* Add th
2130: 65 20 66 69 72 73 74 20 72 6f 77 69 64 20 66 69  e first rowid fi
2140: 65 6c 64 20 74 6f 20 74 68 65 20 68 61 73 68 2d  eld to the hash-
2150: 65 6e 74 72 79 20 2a 2f 0a 20 20 20 20 70 2d 3e  entry */.    p->
2160: 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69 74 65 33  nData += sqlite3
2170: 46 74 73 35 50 75 74 56 61 72 69 6e 74 28 26 28  Fts5PutVarint(&(
2180: 28 75 38 2a 29 70 29 5b 70 2d 3e 6e 44 61 74 61  (u8*)p)[p->nData
2190: 5d 2c 20 69 52 6f 77 69 64 29 3b 0a 20 20 20 20  ], iRowid);.    
21a0: 70 2d 3e 69 52 6f 77 69 64 20 3d 20 69 52 6f 77  p->iRowid = iRow
21b0: 69 64 3b 0a 0a 20 20 20 20 70 2d 3e 69 53 7a 50  id;..    p->iSzP
21c0: 6f 73 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74  oslist = p->nDat
21d0: 61 3b 0a 20 20 20 20 69 66 28 20 70 48 61 73 68  a;.    if( pHash
21e0: 2d 3e 65 44 65 74 61 69 6c 21 3d 46 54 53 35 5f  ->eDetail!=FTS5_
21f0: 44 45 54 41 49 4c 5f 4e 4f 4e 45 20 29 7b 0a 20  DETAIL_NONE ){. 
2200: 20 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d       p->nData +=
2210: 20 31 3b 0a 20 20 20 20 20 20 70 2d 3e 69 43 6f   1;.      p->iCo
2220: 6c 20 3d 20 28 70 48 61 73 68 2d 3e 65 44 65 74  l = (pHash->eDet
2230: 61 69 6c 3d 3d 46 54 53 35 5f 44 45 54 41 49 4c  ail==FTS5_DETAIL
2240: 5f 46 55 4c 4c 20 3f 20 30 20 3a 20 2d 31 29 3b  _FULL ? 0 : -1);
2250: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 6e 49 6e 63  .    }..    nInc
2260: 72 20 2b 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20  r += p->nData;. 
2270: 20 7d 65 6c 73 65 7b 0a 0a 20 20 20 20 2f 2a 20   }else{..    /* 
2280: 41 70 70 65 6e 64 69 6e 67 20 74 6f 20 61 6e 20  Appending to an 
2290: 65 78 69 73 74 69 6e 67 20 68 61 73 68 2d 65 6e  existing hash-en
22a0: 74 72 79 2e 20 43 68 65 63 6b 20 74 68 61 74 20  try. Check that 
22b0: 74 68 65 72 65 20 69 73 20 65 6e 6f 75 67 68 20  there is enough 
22c0: 0a 20 20 20 20 2a 2a 20 73 70 61 63 65 20 74 6f  .    ** space to
22d0: 20 61 70 70 65 6e 64 20 74 68 65 20 6c 61 72 67   append the larg
22e0: 65 73 74 20 70 6f 73 73 69 62 6c 65 20 6e 65 77  est possible new
22f0: 20 65 6e 74 72 79 2e 20 57 6f 72 73 74 20 63 61   entry. Worst ca
2300: 73 65 20 73 63 65 6e 61 72 69 6f 20 0a 20 20 20  se scenario .   
2310: 20 2a 2a 20 69 73 3a 0a 20 20 20 20 2a 2a 0a 20   ** is:.    **. 
2320: 20 20 20 2a 2a 20 20 20 20 20 2b 20 39 20 62 79     **     + 9 by
2330: 74 65 73 20 66 6f 72 20 61 20 6e 65 77 20 72 6f  tes for a new ro
2340: 77 69 64 2c 0a 20 20 20 20 2a 2a 20 20 20 20 20  wid,.    **     
2350: 2b 20 34 20 62 79 74 65 20 72 65 73 65 72 76 65  + 4 byte reserve
2360: 64 20 66 6f 72 20 74 68 65 20 22 70 6f 73 6c 69  d for the "posli
2370: 73 74 20 73 69 7a 65 22 20 76 61 72 69 6e 74 2e  st size" varint.
2380: 0a 20 20 20 20 2a 2a 20 20 20 20 20 2b 20 31 20  .    **     + 1 
2390: 62 79 74 65 20 66 6f 72 20 61 20 22 6e 65 77 20  byte for a "new 
23a0: 63 6f 6c 75 6d 6e 22 20 62 79 74 65 2c 0a 20 20  column" byte,.  
23b0: 20 20 2a 2a 20 20 20 20 20 2b 20 33 20 62 79 74    **     + 3 byt
23c0: 65 73 20 66 6f 72 20 61 20 6e 65 77 20 63 6f 6c  es for a new col
23d0: 75 6d 6e 20 6e 75 6d 62 65 72 20 28 31 36 2d 62  umn number (16-b
23e0: 69 74 20 6d 61 78 29 20 61 73 20 61 20 76 61 72  it max) as a var
23f0: 69 6e 74 2c 0a 20 20 20 20 2a 2a 20 20 20 20 20  int,.    **     
2400: 2b 20 35 20 62 79 74 65 73 20 66 6f 72 20 74 68  + 5 bytes for th
2410: 65 20 6e 65 77 20 70 6f 73 69 74 69 6f 6e 20 6f  e new position o
2420: 66 66 73 65 74 20 28 33 32 2d 62 69 74 20 6d 61  ffset (32-bit ma
2430: 78 29 2e 0a 20 20 20 20 2a 2f 0a 20 20 20 20 69  x)..    */.    i
2440: 66 28 20 28 70 2d 3e 6e 41 6c 6c 6f 63 20 2d 20  f( (p->nAlloc - 
2450: 70 2d 3e 6e 44 61 74 61 29 20 3c 20 28 39 20 2b  p->nData) < (9 +
2460: 20 34 20 2b 20 31 20 2b 20 33 20 2b 20 35 29 20   4 + 1 + 3 + 5) 
2470: 29 7b 0a 20 20 20 20 20 20 69 6e 74 20 6e 4e 65  ){.      int nNe
2480: 77 20 3d 20 70 2d 3e 6e 41 6c 6c 6f 63 20 2a 20  w = p->nAlloc * 
2490: 32 3b 0a 20 20 20 20 20 20 46 74 73 35 48 61 73  2;.      Fts5Has
24a0: 68 45 6e 74 72 79 20 2a 70 4e 65 77 3b 0a 20 20  hEntry *pNew;.  
24b0: 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74 72      Fts5HashEntr
24c0: 79 20 2a 2a 70 70 3b 0a 20 20 20 20 20 20 70 4e  y **pp;.      pN
24d0: 65 77 20 3d 20 28 46 74 73 35 48 61 73 68 45 6e  ew = (Fts5HashEn
24e0: 74 72 79 2a 29 73 71 6c 69 74 65 33 5f 72 65 61  try*)sqlite3_rea
24f0: 6c 6c 6f 63 28 70 2c 20 6e 4e 65 77 29 3b 0a 20  lloc(p, nNew);. 
2500: 20 20 20 20 20 69 66 28 20 70 4e 65 77 3d 3d 30       if( pNew==0
2510: 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45   ) return SQLITE
2520: 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 20 20 70 4e  _NOMEM;.      pN
2530: 65 77 2d 3e 6e 41 6c 6c 6f 63 20 3d 20 6e 4e 65  ew->nAlloc = nNe
2540: 77 3b 0a 20 20 20 20 20 20 66 6f 72 28 70 70 3d  w;.      for(pp=
2550: 26 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 48  &pHash->aSlot[iH
2560: 61 73 68 5d 3b 20 2a 70 70 21 3d 70 3b 20 70 70  ash]; *pp!=p; pp
2570: 3d 26 28 2a 70 70 29 2d 3e 70 48 61 73 68 4e 65  =&(*pp)->pHashNe
2580: 78 74 29 3b 0a 20 20 20 20 20 20 2a 70 70 20 3d  xt);.      *pp =
2590: 20 70 4e 65 77 3b 0a 20 20 20 20 20 20 70 20 3d   pNew;.      p =
25a0: 20 70 4e 65 77 3b 0a 20 20 20 20 7d 0a 20 20 20   pNew;.    }.   
25b0: 20 6e 49 6e 63 72 20 2d 3d 20 70 2d 3e 6e 44 61   nIncr -= p->nDa
25c0: 74 61 3b 0a 20 20 7d 0a 20 20 61 73 73 65 72 74  ta;.  }.  assert
25d0: 28 20 28 70 2d 3e 6e 41 6c 6c 6f 63 20 2d 20 70  ( (p->nAlloc - p
25e0: 2d 3e 6e 44 61 74 61 29 20 3e 3d 20 28 39 20 2b  ->nData) >= (9 +
25f0: 20 34 20 2b 20 31 20 2b 20 33 20 2b 20 35 29 20   4 + 1 + 3 + 5) 
2600: 29 3b 0a 0a 20 20 70 50 74 72 20 3d 20 28 75 38  );..  pPtr = (u8
2610: 2a 29 70 3b 0a 0a 20 20 2f 2a 20 49 66 20 74 68  *)p;..  /* If th
2620: 69 73 20 69 73 20 61 20 6e 65 77 20 72 6f 77 69  is is a new rowi
2630: 64 2c 20 61 70 70 65 6e 64 20 74 68 65 20 34 2d  d, append the 4-
2640: 62 79 74 65 20 73 69 7a 65 20 66 69 65 6c 64 20  byte size field 
2650: 66 6f 72 20 74 68 65 20 70 72 65 76 69 6f 75 73  for the previous
2660: 0a 20 20 2a 2a 20 65 6e 74 72 79 2c 20 61 6e 64  .  ** entry, and
2670: 20 74 68 65 20 6e 65 77 20 72 6f 77 69 64 20 66   the new rowid f
2680: 6f 72 20 74 68 69 73 20 65 6e 74 72 79 2e 20 20  or this entry.  
2690: 2a 2f 0a 20 20 69 66 28 20 69 52 6f 77 69 64 21  */.  if( iRowid!
26a0: 3d 70 2d 3e 69 52 6f 77 69 64 20 29 7b 0a 20 20  =p->iRowid ){.  
26b0: 20 20 66 74 73 35 48 61 73 68 41 64 64 50 6f 73    fts5HashAddPos
26c0: 6c 69 73 74 53 69 7a 65 28 70 48 61 73 68 2c 20  listSize(pHash, 
26d0: 70 29 3b 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61  p);.    p->nData
26e0: 20 2b 3d 20 73 71 6c 69 74 65 33 46 74 73 35 50   += sqlite3Fts5P
26f0: 75 74 56 61 72 69 6e 74 28 26 70 50 74 72 5b 70  utVarint(&pPtr[p
2700: 2d 3e 6e 44 61 74 61 5d 2c 20 69 52 6f 77 69 64  ->nData], iRowid
2710: 20 2d 20 70 2d 3e 69 52 6f 77 69 64 29 3b 0a 20   - p->iRowid);. 
2720: 20 20 20 70 2d 3e 69 52 6f 77 69 64 20 3d 20 69     p->iRowid = i
2730: 52 6f 77 69 64 3b 0a 20 20 20 20 62 4e 65 77 20  Rowid;.    bNew 
2740: 3d 20 31 3b 0a 20 20 20 20 70 2d 3e 69 53 7a 50  = 1;.    p->iSzP
2750: 6f 73 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74  oslist = p->nDat
2760: 61 3b 0a 20 20 20 20 69 66 28 20 70 48 61 73 68  a;.    if( pHash
2770: 2d 3e 65 44 65 74 61 69 6c 21 3d 46 54 53 35 5f  ->eDetail!=FTS5_
2780: 44 45 54 41 49 4c 5f 4e 4f 4e 45 20 29 7b 0a 20  DETAIL_NONE ){. 
2790: 20 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d       p->nData +=
27a0: 20 31 3b 0a 20 20 20 20 20 20 70 2d 3e 69 43 6f   1;.      p->iCo
27b0: 6c 20 3d 20 28 70 48 61 73 68 2d 3e 65 44 65 74  l = (pHash->eDet
27c0: 61 69 6c 3d 3d 46 54 53 35 5f 44 45 54 41 49 4c  ail==FTS5_DETAIL
27d0: 5f 46 55 4c 4c 20 3f 20 30 20 3a 20 2d 31 29 3b  _FULL ? 0 : -1);
27e0: 0a 20 20 20 20 20 20 70 2d 3e 69 50 6f 73 20 3d  .      p->iPos =
27f0: 20 30 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 20   0;.    }.  }.. 
2800: 20 69 66 28 20 69 43 6f 6c 3e 3d 30 20 29 7b 0a   if( iCol>=0 ){.
2810: 20 20 20 20 69 66 28 20 70 48 61 73 68 2d 3e 65      if( pHash->e
2820: 44 65 74 61 69 6c 3d 3d 46 54 53 35 5f 44 45 54  Detail==FTS5_DET
2830: 41 49 4c 5f 4e 4f 4e 45 20 29 7b 0a 20 20 20 20  AIL_NONE ){.    
2840: 20 20 70 2d 3e 62 43 6f 6e 74 65 6e 74 20 3d 20    p->bContent = 
2850: 31 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20  1;.    }else{.  
2860: 20 20 20 20 2f 2a 20 41 70 70 65 6e 64 20 61 20      /* Append a 
2870: 6e 65 77 20 63 6f 6c 75 6d 6e 20 76 61 6c 75 65  new column value
2880: 2c 20 69 66 20 6e 65 63 65 73 73 61 72 79 20 2a  , if necessary *
2890: 2f 0a 20 20 20 20 20 20 61 73 73 65 72 74 28 20  /.      assert( 
28a0: 69 43 6f 6c 3e 3d 70 2d 3e 69 43 6f 6c 20 29 3b  iCol>=p->iCol );
28b0: 0a 20 20 20 20 20 20 69 66 28 20 69 43 6f 6c 21  .      if( iCol!
28c0: 3d 70 2d 3e 69 43 6f 6c 20 29 7b 0a 20 20 20 20  =p->iCol ){.    
28d0: 20 20 20 20 69 66 28 20 70 48 61 73 68 2d 3e 65      if( pHash->e
28e0: 44 65 74 61 69 6c 3d 3d 46 54 53 35 5f 44 45 54  Detail==FTS5_DET
28f0: 41 49 4c 5f 46 55 4c 4c 20 29 7b 0a 20 20 20 20  AIL_FULL ){.    
2900: 20 20 20 20 20 20 70 50 74 72 5b 70 2d 3e 6e 44        pPtr[p->nD
2910: 61 74 61 2b 2b 5d 20 3d 20 30 78 30 31 3b 0a 20  ata++] = 0x01;. 
2920: 20 20 20 20 20 20 20 20 20 70 2d 3e 6e 44 61 74           p->nDat
2930: 61 20 2b 3d 20 73 71 6c 69 74 65 33 46 74 73 35  a += sqlite3Fts5
2940: 50 75 74 56 61 72 69 6e 74 28 26 70 50 74 72 5b  PutVarint(&pPtr[
2950: 70 2d 3e 6e 44 61 74 61 5d 2c 20 69 43 6f 6c 29  p->nData], iCol)
2960: 3b 0a 20 20 20 20 20 20 20 20 20 20 70 2d 3e 69  ;.          p->i
2970: 43 6f 6c 20 3d 20 28 69 31 36 29 69 43 6f 6c 3b  Col = (i16)iCol;
2980: 0a 20 20 20 20 20 20 20 20 20 20 70 2d 3e 69 50  .          p->iP
2990: 6f 73 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20  os = 0;.        
29a0: 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 20 20 20  }else{.         
29b0: 20 62 4e 65 77 20 3d 20 31 3b 0a 20 20 20 20 20   bNew = 1;.     
29c0: 20 20 20 20 20 70 2d 3e 69 43 6f 6c 20 3d 20 28       p->iCol = (
29d0: 69 31 36 29 28 69 50 6f 73 20 3d 20 69 43 6f 6c  i16)(iPos = iCol
29e0: 29 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20  );.        }.   
29f0: 20 20 20 7d 0a 0a 20 20 20 20 20 20 2f 2a 20 41     }..      /* A
2a00: 70 70 65 6e 64 20 74 68 65 20 6e 65 77 20 70 6f  ppend the new po
2a10: 73 69 74 69 6f 6e 20 6f 66 66 73 65 74 2c 20 69  sition offset, i
2a20: 66 20 6e 65 63 65 73 73 61 72 79 20 2a 2f 0a 20  f necessary */. 
2a30: 20 20 20 20 20 69 66 28 20 62 4e 65 77 20 29 7b       if( bNew ){
2a40: 0a 20 20 20 20 20 20 20 20 70 2d 3e 6e 44 61 74  .        p->nDat
2a50: 61 20 2b 3d 20 73 71 6c 69 74 65 33 46 74 73 35  a += sqlite3Fts5
2a60: 50 75 74 56 61 72 69 6e 74 28 26 70 50 74 72 5b  PutVarint(&pPtr[
2a70: 70 2d 3e 6e 44 61 74 61 5d 2c 20 69 50 6f 73 20  p->nData], iPos 
2a80: 2d 20 70 2d 3e 69 50 6f 73 20 2b 20 32 29 3b 0a  - p->iPos + 2);.
2a90: 20 20 20 20 20 20 20 20 70 2d 3e 69 50 6f 73 20          p->iPos 
2aa0: 3d 20 69 50 6f 73 3b 0a 20 20 20 20 20 20 7d 0a  = iPos;.      }.
2ab0: 20 20 20 20 7d 0a 20 20 7d 65 6c 73 65 7b 0a 20      }.  }else{. 
2ac0: 20 20 20 2f 2a 20 54 68 69 73 20 69 73 20 61 20     /* This is a 
2ad0: 64 65 6c 65 74 65 2e 20 53 65 74 20 74 68 65 20  delete. Set the 
2ae0: 64 65 6c 65 74 65 20 66 6c 61 67 2e 20 2a 2f 0a  delete flag. */.
2af0: 20 20 20 20 70 2d 3e 62 44 65 6c 20 3d 20 31 3b      p->bDel = 1;
2b00: 0a 20 20 7d 0a 0a 20 20 6e 49 6e 63 72 20 2b 3d  .  }..  nIncr +=
2b10: 20 70 2d 3e 6e 44 61 74 61 3b 0a 20 20 2a 70 48   p->nData;.  *pH
2b20: 61 73 68 2d 3e 70 6e 42 79 74 65 20 2b 3d 20 6e  ash->pnByte += n
2b30: 49 6e 63 72 3b 0a 20 20 72 65 74 75 72 6e 20 53  Incr;.  return S
2b40: 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 0a 2f 2a  QLITE_OK;.}.../*
2b50: 0a 2a 2a 20 41 72 67 75 6d 65 6e 74 73 20 70 4c  .** Arguments pL
2b60: 65 66 74 20 61 6e 64 20 70 52 69 67 68 74 20 70  eft and pRight p
2b70: 6f 69 6e 74 20 74 6f 20 6c 69 6e 6b 65 64 2d 6c  oint to linked-l
2b80: 69 73 74 73 20 6f 66 20 68 61 73 68 2d 65 6e 74  ists of hash-ent
2b90: 72 79 20 6f 62 6a 65 63 74 73 2c 0a 2a 2a 20 65  ry objects,.** e
2ba0: 61 63 68 20 73 6f 72 74 65 64 20 69 6e 20 6b 65  ach sorted in ke
2bb0: 79 20 6f 72 64 65 72 2e 20 54 68 69 73 20 66 75  y order. This fu
2bc0: 6e 63 74 69 6f 6e 20 6d 65 72 67 65 73 20 74 68  nction merges th
2bd0: 65 20 74 77 6f 20 6c 69 73 74 73 20 69 6e 74 6f  e two lists into
2be0: 20 61 0a 2a 2a 20 73 69 6e 67 6c 65 20 6c 69 73   a.** single lis
2bf0: 74 20 61 6e 64 20 72 65 74 75 72 6e 73 20 61 20  t and returns a 
2c00: 70 6f 69 6e 74 65 72 20 74 6f 20 69 74 73 20 66  pointer to its f
2c10: 69 72 73 74 20 65 6c 65 6d 65 6e 74 2e 0a 2a 2f  irst element..*/
2c20: 0a 73 74 61 74 69 63 20 46 74 73 35 48 61 73 68  .static Fts5Hash
2c30: 45 6e 74 72 79 20 2a 66 74 73 35 48 61 73 68 45  Entry *fts5HashE
2c40: 6e 74 72 79 4d 65 72 67 65 28 0a 20 20 46 74 73  ntryMerge(.  Fts
2c50: 35 48 61 73 68 45 6e 74 72 79 20 2a 70 4c 65 66  5HashEntry *pLef
2c60: 74 2c 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74  t,.  Fts5HashEnt
2c70: 72 79 20 2a 70 52 69 67 68 74 0a 29 7b 0a 20 20  ry *pRight.){.  
2c80: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70  Fts5HashEntry *p
2c90: 31 20 3d 20 70 4c 65 66 74 3b 0a 20 20 46 74 73  1 = pLeft;.  Fts
2ca0: 35 48 61 73 68 45 6e 74 72 79 20 2a 70 32 20 3d  5HashEntry *p2 =
2cb0: 20 70 52 69 67 68 74 3b 0a 20 20 46 74 73 35 48   pRight;.  Fts5H
2cc0: 61 73 68 45 6e 74 72 79 20 2a 70 52 65 74 20 3d  ashEntry *pRet =
2cd0: 20 30 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e   0;.  Fts5HashEn
2ce0: 74 72 79 20 2a 2a 70 70 4f 75 74 20 3d 20 26 70  try **ppOut = &p
2cf0: 52 65 74 3b 0a 0a 20 20 77 68 69 6c 65 28 20 70  Ret;..  while( p
2d00: 31 20 7c 7c 20 70 32 20 29 7b 0a 20 20 20 20 69  1 || p2 ){.    i
2d10: 66 28 20 70 31 3d 3d 30 20 29 7b 0a 20 20 20 20  f( p1==0 ){.    
2d20: 20 20 2a 70 70 4f 75 74 20 3d 20 70 32 3b 0a 20    *ppOut = p2;. 
2d30: 20 20 20 20 20 70 32 20 3d 20 30 3b 0a 20 20 20       p2 = 0;.   
2d40: 20 7d 65 6c 73 65 20 69 66 28 20 70 32 3d 3d 30   }else if( p2==0
2d50: 20 29 7b 0a 20 20 20 20 20 20 2a 70 70 4f 75 74   ){.      *ppOut
2d60: 20 3d 20 70 31 3b 0a 20 20 20 20 20 20 70 31 20   = p1;.      p1 
2d70: 3d 20 30 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a  = 0;.    }else{.
2d80: 20 20 20 20 20 20 69 6e 74 20 69 20 3d 20 30 3b        int i = 0;
2d90: 0a 20 20 20 20 20 20 63 68 61 72 20 2a 7a 4b 65  .      char *zKe
2da0: 79 31 20 3d 20 66 74 73 35 45 6e 74 72 79 4b 65  y1 = fts5EntryKe
2db0: 79 28 70 31 29 3b 0a 20 20 20 20 20 20 63 68 61  y(p1);.      cha
2dc0: 72 20 2a 7a 4b 65 79 32 20 3d 20 66 74 73 35 45  r *zKey2 = fts5E
2dd0: 6e 74 72 79 4b 65 79 28 70 32 29 3b 0a 20 20 20  ntryKey(p2);.   
2de0: 20 20 20 77 68 69 6c 65 28 20 7a 4b 65 79 31 5b     while( zKey1[
2df0: 69 5d 3d 3d 7a 4b 65 79 32 5b 69 5d 20 29 20 69  i]==zKey2[i] ) i
2e00: 2b 2b 3b 0a 0a 20 20 20 20 20 20 69 66 28 20 28  ++;..      if( (
2e10: 28 75 38 29 7a 4b 65 79 31 5b 69 5d 29 3e 28 28  (u8)zKey1[i])>((
2e20: 75 38 29 7a 4b 65 79 32 5b 69 5d 29 20 29 7b 0a  u8)zKey2[i]) ){.
2e30: 20 20 20 20 20 20 20 20 2f 2a 20 70 32 20 69 73          /* p2 is
2e40: 20 73 6d 61 6c 6c 65 72 20 2a 2f 0a 20 20 20 20   smaller */.    
2e50: 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 70 32 3b      *ppOut = p2;
2e60: 0a 20 20 20 20 20 20 20 20 70 70 4f 75 74 20 3d  .        ppOut =
2e70: 20 26 70 32 2d 3e 70 53 63 61 6e 4e 65 78 74 3b   &p2->pScanNext;
2e80: 0a 20 20 20 20 20 20 20 20 70 32 20 3d 20 70 32  .        p2 = p2
2e90: 2d 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 20 20 20  ->pScanNext;.   
2ea0: 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20     }else{.      
2eb0: 20 20 2f 2a 20 70 31 20 69 73 20 73 6d 61 6c 6c    /* p1 is small
2ec0: 65 72 20 2a 2f 0a 20 20 20 20 20 20 20 20 2a 70  er */.        *p
2ed0: 70 4f 75 74 20 3d 20 70 31 3b 0a 20 20 20 20 20  pOut = p1;.     
2ee0: 20 20 20 70 70 4f 75 74 20 3d 20 26 70 31 2d 3e     ppOut = &p1->
2ef0: 70 53 63 61 6e 4e 65 78 74 3b 0a 20 20 20 20 20  pScanNext;.     
2f00: 20 20 20 70 31 20 3d 20 70 31 2d 3e 70 53 63 61     p1 = p1->pSca
2f10: 6e 4e 65 78 74 3b 0a 20 20 20 20 20 20 7d 0a 20  nNext;.      }. 
2f20: 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 30 3b       *ppOut = 0;
2f30: 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 72 65  .    }.  }..  re
2f40: 74 75 72 6e 20 70 52 65 74 3b 0a 7d 0a 0a 2f 2a  turn pRet;.}../*
2f50: 0a 2a 2a 20 45 78 74 72 61 63 74 20 61 6c 6c 20  .** Extract all 
2f60: 74 6f 6b 65 6e 73 20 66 72 6f 6d 20 68 61 73 68  tokens from hash
2f70: 20 74 61 62 6c 65 20 69 48 61 73 68 20 61 6e 64   table iHash and
2f80: 20 6c 69 6e 6b 20 74 68 65 6d 20 69 6e 74 6f 20   link them into 
2f90: 61 20 6c 69 73 74 0a 2a 2a 20 69 6e 20 73 6f 72  a list.** in sor
2fa0: 74 65 64 20 6f 72 64 65 72 2e 20 54 68 65 20 68  ted order. The h
2fb0: 61 73 68 20 74 61 62 6c 65 20 69 73 20 63 6c 65  ash table is cle
2fc0: 61 72 65 64 20 62 65 66 6f 72 65 20 72 65 74 75  ared before retu
2fd0: 72 6e 69 6e 67 2e 20 49 74 20 69 73 0a 2a 2a 20  rning. It is.** 
2fe0: 74 68 65 20 72 65 73 70 6f 6e 73 69 62 69 6c 69  the responsibili
2ff0: 74 79 20 6f 66 20 74 68 65 20 63 61 6c 6c 65 72  ty of the caller
3000: 20 74 6f 20 66 72 65 65 20 74 68 65 20 65 6c 65   to free the ele
3010: 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 72 65 74  ments of the ret
3020: 75 72 6e 65 64 0a 2a 2a 20 6c 69 73 74 2e 0a 2a  urned.** list..*
3030: 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 66 74 73  /.static int fts
3040: 35 48 61 73 68 45 6e 74 72 79 53 6f 72 74 28 0a  5HashEntrySort(.
3050: 20 20 46 74 73 35 48 61 73 68 20 2a 70 48 61 73    Fts5Hash *pHas
3060: 68 2c 20 0a 20 20 63 6f 6e 73 74 20 63 68 61 72  h, .  const char
3070: 20 2a 70 54 65 72 6d 2c 20 69 6e 74 20 6e 54 65   *pTerm, int nTe
3080: 72 6d 2c 20 20 20 2f 2a 20 51 75 65 72 79 20 70  rm,   /* Query p
3090: 72 65 66 69 78 2c 20 69 66 20 61 6e 79 20 2a 2f  refix, if any */
30a0: 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  .  Fts5HashEntry
30b0: 20 2a 2a 70 70 53 6f 72 74 65 64 0a 29 7b 0a 20   **ppSorted.){. 
30c0: 20 63 6f 6e 73 74 20 69 6e 74 20 6e 4d 65 72 67   const int nMerg
30d0: 65 53 6c 6f 74 20 3d 20 33 32 3b 0a 20 20 46 74  eSlot = 32;.  Ft
30e0: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 61 70  s5HashEntry **ap
30f0: 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72  ;.  Fts5HashEntr
3100: 79 20 2a 70 4c 69 73 74 3b 0a 20 20 69 6e 74 20  y *pList;.  int 
3110: 69 53 6c 6f 74 3b 0a 20 20 69 6e 74 20 69 3b 0a  iSlot;.  int i;.
3120: 0a 20 20 2a 70 70 53 6f 72 74 65 64 20 3d 20 30  .  *ppSorted = 0
3130: 3b 0a 20 20 61 70 20 3d 20 73 71 6c 69 74 65 33  ;.  ap = sqlite3
3140: 5f 6d 61 6c 6c 6f 63 28 73 69 7a 65 6f 66 28 46  _malloc(sizeof(F
3150: 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29 20 2a  ts5HashEntry*) *
3160: 20 6e 4d 65 72 67 65 53 6c 6f 74 29 3b 0a 20 20   nMergeSlot);.  
3170: 69 66 28 20 21 61 70 20 29 20 72 65 74 75 72 6e  if( !ap ) return
3180: 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20   SQLITE_NOMEM;. 
3190: 20 6d 65 6d 73 65 74 28 61 70 2c 20 30 2c 20 73   memset(ap, 0, s
31a0: 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e  izeof(Fts5HashEn
31b0: 74 72 79 2a 29 20 2a 20 6e 4d 65 72 67 65 53 6c  try*) * nMergeSl
31c0: 6f 74 29 3b 0a 0a 20 20 66 6f 72 28 69 53 6c 6f  ot);..  for(iSlo
31d0: 74 3d 30 3b 20 69 53 6c 6f 74 3c 70 48 61 73 68  t=0; iSlot<pHash
31e0: 2d 3e 6e 53 6c 6f 74 3b 20 69 53 6c 6f 74 2b 2b  ->nSlot; iSlot++
31f0: 29 7b 0a 20 20 20 20 46 74 73 35 48 61 73 68 45  ){.    Fts5HashE
3200: 6e 74 72 79 20 2a 70 49 74 65 72 3b 0a 20 20 20  ntry *pIter;.   
3210: 20 66 6f 72 28 70 49 74 65 72 3d 70 48 61 73 68   for(pIter=pHash
3220: 2d 3e 61 53 6c 6f 74 5b 69 53 6c 6f 74 5d 3b 20  ->aSlot[iSlot]; 
3230: 70 49 74 65 72 3b 20 70 49 74 65 72 3d 70 49 74  pIter; pIter=pIt
3240: 65 72 2d 3e 70 48 61 73 68 4e 65 78 74 29 7b 0a  er->pHashNext){.
3250: 20 20 20 20 20 20 69 66 28 20 70 54 65 72 6d 3d        if( pTerm=
3260: 3d 30 20 7c 7c 20 30 3d 3d 6d 65 6d 63 6d 70 28  =0 || 0==memcmp(
3270: 66 74 73 35 45 6e 74 72 79 4b 65 79 28 70 49 74  fts5EntryKey(pIt
3280: 65 72 29 2c 20 70 54 65 72 6d 2c 20 6e 54 65 72  er), pTerm, nTer
3290: 6d 29 20 29 7b 0a 20 20 20 20 20 20 20 20 46 74  m) ){.        Ft
32a0: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 45 6e  s5HashEntry *pEn
32b0: 74 72 79 20 3d 20 70 49 74 65 72 3b 0a 20 20 20  try = pIter;.   
32c0: 20 20 20 20 20 70 45 6e 74 72 79 2d 3e 70 53 63       pEntry->pSc
32d0: 61 6e 4e 65 78 74 20 3d 20 30 3b 0a 20 20 20 20  anNext = 0;.    
32e0: 20 20 20 20 66 6f 72 28 69 3d 30 3b 20 61 70 5b      for(i=0; ap[
32f0: 69 5d 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20  i]; i++){.      
3300: 20 20 20 20 70 45 6e 74 72 79 20 3d 20 66 74 73      pEntry = fts
3310: 35 48 61 73 68 45 6e 74 72 79 4d 65 72 67 65 28  5HashEntryMerge(
3320: 70 45 6e 74 72 79 2c 20 61 70 5b 69 5d 29 3b 0a  pEntry, ap[i]);.
3330: 20 20 20 20 20 20 20 20 20 20 61 70 5b 69 5d 20            ap[i] 
3340: 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20  = 0;.        }. 
3350: 20 20 20 20 20 20 20 61 70 5b 69 5d 20 3d 20 70         ap[i] = p
3360: 45 6e 74 72 79 3b 0a 20 20 20 20 20 20 7d 0a 20  Entry;.      }. 
3370: 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 70 4c 69 73     }.  }..  pLis
3380: 74 20 3d 20 30 3b 0a 20 20 66 6f 72 28 69 3d 30  t = 0;.  for(i=0
3390: 3b 20 69 3c 6e 4d 65 72 67 65 53 6c 6f 74 3b 20  ; i<nMergeSlot; 
33a0: 69 2b 2b 29 7b 0a 20 20 20 20 70 4c 69 73 74 20  i++){.    pList 
33b0: 3d 20 66 74 73 35 48 61 73 68 45 6e 74 72 79 4d  = fts5HashEntryM
33c0: 65 72 67 65 28 70 4c 69 73 74 2c 20 61 70 5b 69  erge(pList, ap[i
33d0: 5d 29 3b 0a 20 20 7d 0a 0a 20 20 70 48 61 73 68  ]);.  }..  pHash
33e0: 2d 3e 6e 45 6e 74 72 79 20 3d 20 30 3b 0a 20 20  ->nEntry = 0;.  
33f0: 73 71 6c 69 74 65 33 5f 66 72 65 65 28 61 70 29  sqlite3_free(ap)
3400: 3b 0a 20 20 2a 70 70 53 6f 72 74 65 64 20 3d 20  ;.  *ppSorted = 
3410: 70 4c 69 73 74 3b 0a 20 20 72 65 74 75 72 6e 20  pList;.  return 
3420: 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a  SQLITE_OK;.}../*
3430: 0a 2a 2a 20 51 75 65 72 79 20 74 68 65 20 68 61  .** Query the ha
3440: 73 68 20 74 61 62 6c 65 20 66 6f 72 20 61 20 64  sh table for a d
3450: 6f 63 6c 69 73 74 20 61 73 73 6f 63 69 61 74 65  oclist associate
3460: 64 20 77 69 74 68 20 74 65 72 6d 20 70 54 65 72  d with term pTer
3470: 6d 2f 6e 54 65 72 6d 2e 0a 2a 2f 0a 69 6e 74 20  m/nTerm..*/.int 
3480: 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 51  sqlite3Fts5HashQ
3490: 75 65 72 79 28 0a 20 20 46 74 73 35 48 61 73 68  uery(.  Fts5Hash
34a0: 20 2a 70 48 61 73 68 2c 20 20 20 20 20 20 20 20   *pHash,        
34b0: 20 20 20 20 20 20 20 20 2f 2a 20 48 61 73 68 20          /* Hash 
34c0: 74 61 62 6c 65 20 74 6f 20 71 75 65 72 79 20 2a  table to query *
34d0: 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a  /.  const char *
34e0: 70 54 65 72 6d 2c 20 69 6e 74 20 6e 54 65 72 6d  pTerm, int nTerm
34f0: 2c 20 20 20 2f 2a 20 51 75 65 72 79 20 74 65 72  ,   /* Query ter
3500: 6d 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 75 38 20  m */.  const u8 
3510: 2a 2a 70 70 44 6f 63 6c 69 73 74 2c 20 20 20 20  **ppDoclist,    
3520: 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20 50         /* OUT: P
3530: 6f 69 6e 74 65 72 20 74 6f 20 64 6f 63 6c 69 73  ointer to doclis
3540: 74 20 66 6f 72 20 70 54 65 72 6d 20 2a 2f 0a 20  t for pTerm */. 
3550: 20 69 6e 74 20 2a 70 6e 44 6f 63 6c 69 73 74 20   int *pnDoclist 
3560: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3570: 20 2f 2a 20 4f 55 54 3a 20 53 69 7a 65 20 6f 66   /* OUT: Size of
3580: 20 64 6f 63 6c 69 73 74 20 69 6e 20 62 79 74 65   doclist in byte
3590: 73 20 2a 2f 0a 29 7b 0a 20 20 75 6e 73 69 67 6e  s */.){.  unsign
35a0: 65 64 20 69 6e 74 20 69 48 61 73 68 20 3d 20 66  ed int iHash = f
35b0: 74 73 35 48 61 73 68 4b 65 79 28 70 48 61 73 68  ts5HashKey(pHash
35c0: 2d 3e 6e 53 6c 6f 74 2c 20 28 63 6f 6e 73 74 20  ->nSlot, (const 
35d0: 75 38 2a 29 70 54 65 72 6d 2c 20 6e 54 65 72 6d  u8*)pTerm, nTerm
35e0: 29 3b 0a 20 20 63 68 61 72 20 2a 7a 4b 65 79 20  );.  char *zKey 
35f0: 3d 20 30 3b 0a 20 20 46 74 73 35 48 61 73 68 45  = 0;.  Fts5HashE
3600: 6e 74 72 79 20 2a 70 3b 0a 0a 20 20 66 6f 72 28  ntry *p;..  for(
3610: 70 3d 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69  p=pHash->aSlot[i
3620: 48 61 73 68 5d 3b 20 70 3b 20 70 3d 70 2d 3e 70  Hash]; p; p=p->p
3630: 48 61 73 68 4e 65 78 74 29 7b 0a 20 20 20 20 7a  HashNext){.    z
3640: 4b 65 79 20 3d 20 66 74 73 35 45 6e 74 72 79 4b  Key = fts5EntryK
3650: 65 79 28 70 29 3b 0a 20 20 20 20 61 73 73 65 72  ey(p);.    asser
3660: 74 28 20 70 2d 3e 6e 4b 65 79 2b 31 3d 3d 28 69  t( p->nKey+1==(i
3670: 6e 74 29 73 74 72 6c 65 6e 28 7a 4b 65 79 29 20  nt)strlen(zKey) 
3680: 29 3b 0a 20 20 20 20 69 66 28 20 6e 54 65 72 6d  );.    if( nTerm
3690: 3d 3d 70 2d 3e 6e 4b 65 79 2b 31 20 26 26 20 6d  ==p->nKey+1 && m
36a0: 65 6d 63 6d 70 28 7a 4b 65 79 2c 20 70 54 65 72  emcmp(zKey, pTer
36b0: 6d 2c 20 6e 54 65 72 6d 29 3d 3d 30 20 29 20 62  m, nTerm)==0 ) b
36c0: 72 65 61 6b 3b 0a 20 20 7d 0a 0a 20 20 69 66 28  reak;.  }..  if(
36d0: 20 70 20 29 7b 0a 20 20 20 20 66 74 73 35 48 61   p ){.    fts5Ha
36e0: 73 68 41 64 64 50 6f 73 6c 69 73 74 53 69 7a 65  shAddPoslistSize
36f0: 28 70 48 61 73 68 2c 20 70 29 3b 0a 20 20 20 20  (pHash, p);.    
3700: 2a 70 70 44 6f 63 6c 69 73 74 20 3d 20 28 63 6f  *ppDoclist = (co
3710: 6e 73 74 20 75 38 2a 29 26 7a 4b 65 79 5b 6e 54  nst u8*)&zKey[nT
3720: 65 72 6d 2b 31 5d 3b 0a 20 20 20 20 2a 70 6e 44  erm+1];.    *pnD
3730: 6f 63 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74  oclist = p->nDat
3740: 61 20 2d 20 28 73 69 7a 65 6f 66 28 46 74 73 35  a - (sizeof(Fts5
3750: 48 61 73 68 45 6e 74 72 79 29 20 2b 20 6e 54 65  HashEntry) + nTe
3760: 72 6d 20 2b 20 31 29 3b 0a 20 20 7d 65 6c 73 65  rm + 1);.  }else
3770: 7b 0a 20 20 20 20 2a 70 70 44 6f 63 6c 69 73 74  {.    *ppDoclist
3780: 20 3d 20 30 3b 0a 20 20 20 20 2a 70 6e 44 6f 63   = 0;.    *pnDoc
3790: 6c 69 73 74 20 3d 20 30 3b 0a 20 20 7d 0a 0a 20  list = 0;.  }.. 
37a0: 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f   return SQLITE_O
37b0: 4b 3b 0a 7d 0a 0a 69 6e 74 20 73 71 6c 69 74 65  K;.}..int sqlite
37c0: 33 46 74 73 35 48 61 73 68 53 63 61 6e 49 6e 69  3Fts5HashScanIni
37d0: 74 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a 70  t(.  Fts5Hash *p
37e0: 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ,               
37f0: 20 20 20 20 20 2f 2a 20 48 61 73 68 20 74 61 62       /* Hash tab
3800: 6c 65 20 74 6f 20 71 75 65 72 79 20 2a 2f 0a 20  le to query */. 
3810: 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 54 65   const char *pTe
3820: 72 6d 2c 20 69 6e 74 20 6e 54 65 72 6d 20 20 20  rm, int nTerm   
3830: 20 2f 2a 20 51 75 65 72 79 20 70 72 65 66 69 78   /* Query prefix
3840: 20 2a 2f 0a 29 7b 0a 20 20 72 65 74 75 72 6e 20   */.){.  return 
3850: 66 74 73 35 48 61 73 68 45 6e 74 72 79 53 6f 72  fts5HashEntrySor
3860: 74 28 70 2c 20 70 54 65 72 6d 2c 20 6e 54 65 72  t(p, pTerm, nTer
3870: 6d 2c 20 26 70 2d 3e 70 53 63 61 6e 29 3b 0a 7d  m, &p->pScan);.}
3880: 0a 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 46 74  ..void sqlite3Ft
3890: 73 35 48 61 73 68 53 63 61 6e 4e 65 78 74 28 46  s5HashScanNext(F
38a0: 74 73 35 48 61 73 68 20 2a 70 29 7b 0a 20 20 61  ts5Hash *p){.  a
38b0: 73 73 65 72 74 28 20 21 73 71 6c 69 74 65 33 46  ssert( !sqlite3F
38c0: 74 73 35 48 61 73 68 53 63 61 6e 45 6f 66 28 70  ts5HashScanEof(p
38d0: 29 20 29 3b 0a 20 20 70 2d 3e 70 53 63 61 6e 20  ) );.  p->pScan 
38e0: 3d 20 70 2d 3e 70 53 63 61 6e 2d 3e 70 53 63 61  = p->pScan->pSca
38f0: 6e 4e 65 78 74 3b 0a 7d 0a 0a 69 6e 74 20 73 71  nNext;.}..int sq
3900: 6c 69 74 65 33 46 74 73 35 48 61 73 68 53 63 61  lite3Fts5HashSca
3910: 6e 45 6f 66 28 46 74 73 35 48 61 73 68 20 2a 70  nEof(Fts5Hash *p
3920: 29 7b 0a 20 20 72 65 74 75 72 6e 20 28 70 2d 3e  ){.  return (p->
3930: 70 53 63 61 6e 3d 3d 30 29 3b 0a 7d 0a 0a 76 6f  pScan==0);.}..vo
3940: 69 64 20 73 71 6c 69 74 65 33 46 74 73 35 48 61  id sqlite3Fts5Ha
3950: 73 68 53 63 61 6e 45 6e 74 72 79 28 0a 20 20 46  shScanEntry(.  F
3960: 74 73 35 48 61 73 68 20 2a 70 48 61 73 68 2c 0a  ts5Hash *pHash,.
3970: 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 2a 70    const char **p
3980: 7a 54 65 72 6d 2c 20 20 20 20 20 20 20 20 20 20  zTerm,          
3990: 20 20 2f 2a 20 4f 55 54 3a 20 74 65 72 6d 20 28    /* OUT: term (
39a0: 6e 75 6c 2d 74 65 72 6d 69 6e 61 74 65 64 29 20  nul-terminated) 
39b0: 2a 2f 0a 20 20 63 6f 6e 73 74 20 75 38 20 2a 2a  */.  const u8 **
39c0: 70 70 44 6f 63 6c 69 73 74 2c 20 20 20 20 20 20  ppDoclist,      
39d0: 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20 70 6f 69       /* OUT: poi
39e0: 6e 74 65 72 20 74 6f 20 64 6f 63 6c 69 73 74 20  nter to doclist 
39f0: 2a 2f 0a 20 20 69 6e 74 20 2a 70 6e 44 6f 63 6c  */.  int *pnDocl
3a00: 69 73 74 20 20 20 20 20 20 20 20 20 20 20 20 20  ist             
3a10: 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20 73 69 7a       /* OUT: siz
3a20: 65 20 6f 66 20 64 6f 63 6c 69 73 74 20 69 6e 20  e of doclist in 
3a30: 62 79 74 65 73 20 2a 2f 0a 29 7b 0a 20 20 46 74  bytes */.){.  Ft
3a40: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 3b 0a  s5HashEntry *p;.
3a50: 20 20 69 66 28 20 28 70 20 3d 20 70 48 61 73 68    if( (p = pHash
3a60: 2d 3e 70 53 63 61 6e 29 20 29 7b 0a 20 20 20 20  ->pScan) ){.    
3a70: 63 68 61 72 20 2a 7a 4b 65 79 20 3d 20 66 74 73  char *zKey = fts
3a80: 35 45 6e 74 72 79 4b 65 79 28 70 29 3b 0a 20 20  5EntryKey(p);.  
3a90: 20 20 69 6e 74 20 6e 54 65 72 6d 20 3d 20 28 69    int nTerm = (i
3aa0: 6e 74 29 73 74 72 6c 65 6e 28 7a 4b 65 79 29 3b  nt)strlen(zKey);
3ab0: 0a 20 20 20 20 66 74 73 35 48 61 73 68 41 64 64  .    fts5HashAdd
3ac0: 50 6f 73 6c 69 73 74 53 69 7a 65 28 70 48 61 73  PoslistSize(pHas
3ad0: 68 2c 20 70 29 3b 0a 20 20 20 20 2a 70 7a 54 65  h, p);.    *pzTe
3ae0: 72 6d 20 3d 20 7a 4b 65 79 3b 0a 20 20 20 20 2a  rm = zKey;.    *
3af0: 70 70 44 6f 63 6c 69 73 74 20 3d 20 28 63 6f 6e  ppDoclist = (con
3b00: 73 74 20 75 38 2a 29 26 7a 4b 65 79 5b 6e 54 65  st u8*)&zKey[nTe
3b10: 72 6d 2b 31 5d 3b 0a 20 20 20 20 2a 70 6e 44 6f  rm+1];.    *pnDo
3b20: 63 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74 61  clist = p->nData
3b30: 20 2d 20 28 73 69 7a 65 6f 66 28 46 74 73 35 48   - (sizeof(Fts5H
3b40: 61 73 68 45 6e 74 72 79 29 20 2b 20 6e 54 65 72  ashEntry) + nTer
3b50: 6d 20 2b 20 31 29 3b 0a 20 20 7d 65 6c 73 65 7b  m + 1);.  }else{
3b60: 0a 20 20 20 20 2a 70 7a 54 65 72 6d 20 3d 20 30  .    *pzTerm = 0
3b70: 3b 0a 20 20 20 20 2a 70 70 44 6f 63 6c 69 73 74  ;.    *ppDoclist
3b80: 20 3d 20 30 3b 0a 20 20 20 20 2a 70 6e 44 6f 63   = 0;.    *pnDoc
3b90: 6c 69 73 74 20 3d 20 30 3b 0a 20 20 7d 0a 7d 0a  list = 0;.  }.}.
3ba0: 0a                                               .