/ Hex Artifact Content
Login

Artifact b54822ca901fb76d79c6a09daecbc464e5fe02c1:


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: 23 69 6e 63 6c 75 64 65 20 22 66 74 73 35 49 6e  #include "fts5In
0190: 74 2e 68 22 0a 0a 74 79 70 65 64 65 66 20 73 74  t.h"..typedef st
01a0: 72 75 63 74 20 46 74 73 35 48 61 73 68 45 6e 74  ruct Fts5HashEnt
01b0: 72 79 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  ry Fts5HashEntry
01c0: 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20 66 69  ;../*.** This fi
01d0: 6c 65 20 63 6f 6e 74 61 69 6e 73 20 74 68 65 20  le contains the 
01e0: 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 6f  implementation o
01f0: 66 20 61 6e 20 69 6e 2d 6d 65 6d 6f 72 79 20 68  f an in-memory h
0200: 61 73 68 20 74 61 62 6c 65 20 75 73 65 64 0a 2a  ash table used.*
0210: 2a 20 74 6f 20 61 63 63 75 6d 75 6c 75 61 74 65  * to accumuluate
0220: 20 22 74 65 72 6d 20 2d 3e 20 64 6f 63 6c 69 73   "term -> doclis
0230: 74 22 20 63 6f 6e 74 65 6e 74 20 62 65 66 6f 72  t" content befor
0240: 65 20 69 74 20 69 73 20 66 6c 75 73 65 64 20 74  e it is flused t
0250: 6f 20 61 20 6c 65 76 65 6c 2d 30 0a 2a 2a 20 73  o a level-0.** s
0260: 65 67 6d 65 6e 74 2e 0a 2a 2f 0a 0a 0a 73 74 72  egment..*/...str
0270: 75 63 74 20 46 74 73 35 48 61 73 68 20 7b 0a 20  uct Fts5Hash {. 
0280: 20 69 6e 74 20 2a 70 6e 42 79 74 65 3b 20 20 20   int *pnByte;   
0290: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
02a0: 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 62   /* Pointer to b
02b0: 79 74 65 73 20 63 6f 75 6e 74 65 72 20 2a 2f 0a  ytes counter */.
02c0: 20 20 69 6e 74 20 6e 45 6e 74 72 79 3b 20 20 20    int nEntry;   
02d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
02e0: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65    /* Number of e
02f0: 6e 74 72 69 65 73 20 63 75 72 72 65 6e 74 6c 79  ntries currently
0300: 20 69 6e 20 68 61 73 68 20 2a 2f 0a 20 20 69 6e   in hash */.  in
0310: 74 20 6e 53 6c 6f 74 3b 20 20 20 20 20 20 20 20  t nSlot;        
0320: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
0330: 20 53 69 7a 65 20 6f 66 20 61 53 6c 6f 74 5b 5d   Size of aSlot[]
0340: 20 61 72 72 61 79 20 2a 2f 0a 20 20 46 74 73 35   array */.  Fts5
0350: 48 61 73 68 45 6e 74 72 79 20 2a 70 53 63 61 6e  HashEntry *pScan
0360: 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43  ;           /* C
0370: 75 72 72 65 6e 74 20 6f 72 64 65 72 65 64 20 73  urrent ordered s
0380: 63 61 6e 20 69 74 65 6d 20 2a 2f 0a 20 20 46 74  can item */.  Ft
0390: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 61 53  s5HashEntry **aS
03a0: 6c 6f 74 3b 20 20 20 20 20 20 20 20 20 20 2f 2a  lot;          /*
03b0: 20 41 72 72 61 79 20 6f 66 20 68 61 73 68 20 73   Array of hash s
03c0: 6c 6f 74 73 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a  lots */.};../*.*
03d0: 2a 20 45 61 63 68 20 65 6e 74 72 79 20 69 6e 20  * Each entry in 
03e0: 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 69  the hash table i
03f0: 73 20 72 65 70 72 65 73 65 6e 74 65 64 20 62 79  s represented by
0400: 20 61 6e 20 6f 62 6a 65 63 74 20 6f 66 20 74 68   an object of th
0410: 65 20 0a 2a 2a 20 66 6f 6c 6c 6f 77 69 6e 67 20  e .** following 
0420: 74 79 70 65 2e 20 45 61 63 68 20 6f 62 6a 65 63  type. Each objec
0430: 74 2c 20 69 74 73 20 6b 65 79 20 28 7a 4b 65 79  t, its key (zKey
0440: 5b 5d 29 20 61 6e 64 20 69 74 73 20 63 75 72 72  []) and its curr
0450: 65 6e 74 20 64 61 74 61 0a 2a 2a 20 61 72 65 20  ent data.** are 
0460: 73 74 6f 72 65 64 20 69 6e 20 61 20 73 69 6e 67  stored in a sing
0470: 6c 65 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f 63 61  le memory alloca
0480: 74 69 6f 6e 2e 20 54 68 65 20 70 6f 73 69 74 69  tion. The positi
0490: 6f 6e 20 6c 69 73 74 20 64 61 74 61 20 0a 2a 2a  on list data .**
04a0: 20 69 6d 6d 65 64 69 61 74 65 6c 79 20 66 6f 6c   immediately fol
04b0: 6c 6f 77 73 20 74 68 65 20 6b 65 79 20 64 61 74  lows the key dat
04c0: 61 20 69 6e 20 6d 65 6d 6f 72 79 2e 0a 2a 2a 0a  a in memory..**.
04d0: 2a 2a 20 54 68 65 20 64 61 74 61 20 74 68 61 74  ** The data that
04e0: 20 66 6f 6c 6c 6f 77 73 20 74 68 65 20 6b 65 79   follows the key
04f0: 20 69 73 20 69 6e 20 61 20 73 69 6d 69 6c 61 72   is in a similar
0500: 2c 20 62 75 74 20 6e 6f 74 20 69 64 65 6e 74 69  , but not identi
0510: 63 61 6c 20 66 6f 72 6d 61 74 0a 2a 2a 20 74 6f  cal format.** to
0520: 20 74 68 65 20 64 6f 63 6c 69 73 74 20 64 61 74   the doclist dat
0530: 61 20 73 74 6f 72 65 64 20 69 6e 20 74 68 65 20  a stored in the 
0540: 64 61 74 61 62 61 73 65 2e 20 49 74 20 69 73 3a  database. It is:
0550: 0a 2a 2a 0a 2a 2a 20 20 20 2a 20 52 6f 77 69 64  .**.**   * Rowid
0560: 2c 20 61 73 20 61 20 76 61 72 69 6e 74 0a 2a 2a  , as a varint.**
0570: 20 20 20 2a 20 50 6f 73 69 74 69 6f 6e 20 6c 69     * Position li
0580: 73 74 2c 20 77 69 74 68 6f 75 74 20 30 78 30 30  st, without 0x00
0590: 20 74 65 72 6d 69 6e 61 74 6f 72 2e 0a 2a 2a 20   terminator..** 
05a0: 20 20 2a 20 53 69 7a 65 20 6f 66 20 70 72 65 76    * Size of prev
05b0: 69 6f 75 73 20 70 6f 73 69 74 69 6f 6e 20 6c 69  ious position li
05c0: 73 74 20 61 6e 64 20 72 6f 77 69 64 2c 20 61 73  st and rowid, as
05d0: 20 61 20 34 20 62 79 74 65 0a 2a 2a 20 20 20 20   a 4 byte.**    
05e0: 20 62 69 67 2d 65 6e 64 69 61 6e 20 69 6e 74 65   big-endian inte
05f0: 67 65 72 2e 0a 2a 2a 0a 2a 2a 20 69 52 6f 77 69  ger..**.** iRowi
0600: 64 4f 66 66 3a 0a 2a 2a 20 20 20 4f 66 66 73 65  dOff:.**   Offse
0610: 74 20 6f 66 20 6c 61 73 74 20 72 6f 77 69 64 20  t of last rowid 
0620: 77 72 69 74 74 65 6e 20 74 6f 20 64 61 74 61 20  written to data 
0630: 61 72 65 61 2e 20 52 65 6c 61 74 69 76 65 20 74  area. Relative t
0640: 6f 20 66 69 72 73 74 20 62 79 74 65 20 6f 66 0a  o first byte of.
0650: 2a 2a 20 20 20 73 74 72 75 63 74 75 72 65 2e 0a  **   structure..
0660: 2a 2a 0a 2a 2a 20 6e 44 61 74 61 3a 0a 2a 2a 20  **.** nData:.** 
0670: 20 20 42 79 74 65 73 20 6f 66 20 64 61 74 61 20    Bytes of data 
0680: 77 72 69 74 74 65 6e 20 73 69 6e 63 65 20 69 52  written since iR
0690: 6f 77 69 64 4f 66 66 2e 0a 2a 2f 0a 73 74 72 75  owidOff..*/.stru
06a0: 63 74 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  ct Fts5HashEntry
06b0: 20 7b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74   {.  Fts5HashEnt
06c0: 72 79 20 2a 70 48 61 73 68 4e 65 78 74 3b 20 20  ry *pHashNext;  
06d0: 20 20 20 20 20 2f 2a 20 4e 65 78 74 20 68 61 73       /* Next has
06e0: 68 20 65 6e 74 72 79 20 77 69 74 68 20 73 61 6d  h entry with sam
06f0: 65 20 68 61 73 68 2d 6b 65 79 20 2a 2f 0a 20 20  e hash-key */.  
0700: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70  Fts5HashEntry *p
0710: 53 63 61 6e 4e 65 78 74 3b 20 20 20 20 20 20 20  ScanNext;       
0720: 2f 2a 20 4e 65 78 74 20 65 6e 74 72 79 20 69 6e  /* Next entry in
0730: 20 73 6f 72 74 65 64 20 6f 72 64 65 72 20 2a 2f   sorted order */
0740: 0a 20 20 0a 20 20 69 6e 74 20 6e 41 6c 6c 6f 63  .  .  int nAlloc
0750: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
0760: 20 20 20 20 20 20 2f 2a 20 54 6f 74 61 6c 20 73        /* Total s
0770: 69 7a 65 20 6f 66 20 61 6c 6c 6f 63 61 74 69 6f  ize of allocatio
0780: 6e 20 2a 2f 0a 20 20 69 6e 74 20 69 53 7a 50 6f  n */.  int iSzPo
0790: 73 6c 69 73 74 3b 20 20 20 20 20 20 20 20 20 20  slist;          
07a0: 20 20 20 20 20 20 20 2f 2a 20 4f 66 66 73 65 74         /* Offset
07b0: 20 6f 66 20 73 70 61 63 65 20 66 6f 72 20 34 2d   of space for 4-
07c0: 62 79 74 65 20 70 6f 73 6c 69 73 74 20 73 69 7a  byte poslist siz
07d0: 65 20 2a 2f 0a 20 20 69 6e 74 20 6e 44 61 74 61  e */.  int nData
07e0: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
07f0: 20 20 20 20 20 20 20 2f 2a 20 54 6f 74 61 6c 20         /* Total 
0800: 62 79 74 65 73 20 6f 66 20 64 61 74 61 20 28 69  bytes of data (i
0810: 6e 63 6c 2e 20 73 74 72 75 63 74 75 72 65 29 20  ncl. structure) 
0820: 2a 2f 0a 0a 20 20 69 6e 74 20 69 43 6f 6c 3b 20  */..  int iCol; 
0830: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0840: 20 20 20 20 20 20 2f 2a 20 43 6f 6c 75 6d 6e 20        /* Column 
0850: 6f 66 20 6c 61 73 74 20 76 61 6c 75 65 20 77 72  of last value wr
0860: 69 74 74 65 6e 20 2a 2f 0a 20 20 69 6e 74 20 69  itten */.  int i
0870: 50 6f 73 3b 20 20 20 20 20 20 20 20 20 20 20 20  Pos;            
0880: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f             /* Po
0890: 73 69 74 69 6f 6e 20 6f 66 20 6c 61 73 74 20 76  sition of last v
08a0: 61 6c 75 65 20 77 72 69 74 74 65 6e 20 2a 2f 0a  alue written */.
08b0: 20 20 69 36 34 20 69 52 6f 77 69 64 3b 20 20 20    i64 iRowid;   
08c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
08d0: 20 20 2f 2a 20 52 6f 77 69 64 20 6f 66 20 6c 61    /* Rowid of la
08e0: 73 74 20 76 61 6c 75 65 20 77 72 69 74 74 65 6e  st value written
08f0: 20 2a 2f 0a 20 20 63 68 61 72 20 7a 4b 65 79 5b   */.  char zKey[
0900: 30 5d 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  0];             
0910: 20 20 20 20 20 20 2f 2a 20 4e 75 6c 2d 74 65 72        /* Nul-ter
0920: 6d 69 6e 61 74 65 64 20 65 6e 74 72 79 20 6b 65  minated entry ke
0930: 79 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 46  y */.};../*.** F
0940: 6f 72 6d 61 74 20 76 61 6c 75 65 20 69 56 61 6c  ormat value iVal
0950: 20 61 73 20 61 20 34 2d 62 79 74 65 20 76 61 72   as a 4-byte var
0960: 69 6e 74 20 61 6e 64 20 77 72 69 74 65 20 69 74  int and write it
0970: 20 74 6f 20 62 75 66 66 65 72 20 61 5b 5d 2e 20   to buffer a[]. 
0980: 34 20 62 79 74 65 73 0a 2a 2a 20 61 72 65 20 75  4 bytes.** are u
0990: 73 65 64 20 65 76 65 6e 20 69 66 20 74 68 65 20  sed even if the 
09a0: 76 61 6c 75 65 20 63 6f 75 6c 64 20 66 69 74 20  value could fit 
09b0: 69 6e 20 61 20 73 6d 61 6c 6c 65 72 20 61 6d 6f  in a smaller amo
09c0: 75 6e 74 20 6f 66 20 73 70 61 63 65 2e 20 0a 2a  unt of space. .*
09d0: 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 66 74  /.static void ft
09e0: 73 35 50 75 74 34 42 79 74 65 56 61 72 69 6e 74  s5Put4ByteVarint
09f0: 28 75 38 20 2a 61 2c 20 69 6e 74 20 69 56 61 6c  (u8 *a, int iVal
0a00: 29 7b 0a 20 20 61 5b 30 5d 20 3d 20 28 30 78 38  ){.  a[0] = (0x8
0a10: 30 20 7c 20 28 75 38 29 28 69 56 61 6c 20 3e 3e  0 | (u8)(iVal >>
0a20: 20 32 31 29 29 3b 0a 20 20 61 5b 31 5d 20 3d 20   21));.  a[1] = 
0a30: 28 30 78 38 30 20 7c 20 28 75 38 29 28 69 56 61  (0x80 | (u8)(iVa
0a40: 6c 20 3e 3e 20 31 34 29 29 3b 0a 20 20 61 5b 32  l >> 14));.  a[2
0a50: 5d 20 3d 20 28 30 78 38 30 20 7c 20 28 75 38 29  ] = (0x80 | (u8)
0a60: 28 69 56 61 6c 20 3e 3e 20 20 37 29 29 3b 0a 20  (iVal >>  7));. 
0a70: 20 61 5b 33 5d 20 3d 20 28 30 78 37 46 20 26 20   a[3] = (0x7F & 
0a80: 28 75 38 29 28 69 56 61 6c 29 29 3b 0a 7d 0a 0a  (u8)(iVal));.}..
0a90: 2f 2a 0a 2a 2a 20 41 6c 6c 6f 63 61 74 65 20 61  /*.** Allocate a
0aa0: 20 6e 65 77 20 68 61 73 68 20 74 61 62 6c 65 2e   new hash table.
0ab0: 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 46  .*/.int sqlite3F
0ac0: 74 73 35 48 61 73 68 4e 65 77 28 46 74 73 35 48  ts5HashNew(Fts5H
0ad0: 61 73 68 20 2a 2a 70 70 4e 65 77 2c 20 69 6e 74  ash **ppNew, int
0ae0: 20 2a 70 6e 42 79 74 65 29 7b 0a 20 20 69 6e 74   *pnByte){.  int
0af0: 20 72 63 20 3d 20 53 51 4c 49 54 45 5f 4f 4b 3b   rc = SQLITE_OK;
0b00: 0a 20 20 46 74 73 35 48 61 73 68 20 2a 70 4e 65  .  Fts5Hash *pNe
0b10: 77 3b 0a 0a 20 20 2a 70 70 4e 65 77 20 3d 20 70  w;..  *ppNew = p
0b20: 4e 65 77 20 3d 20 28 46 74 73 35 48 61 73 68 2a  New = (Fts5Hash*
0b30: 29 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28  )sqlite3_malloc(
0b40: 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 29  sizeof(Fts5Hash)
0b50: 29 3b 0a 20 20 69 66 28 20 70 4e 65 77 3d 3d 30  );.  if( pNew==0
0b60: 20 29 7b 0a 20 20 20 20 72 63 20 3d 20 53 51 4c   ){.    rc = SQL
0b70: 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 7d 65 6c  ITE_NOMEM;.  }el
0b80: 73 65 7b 0a 20 20 20 20 69 6e 74 20 6e 42 79 74  se{.    int nByt
0b90: 65 3b 0a 20 20 20 20 6d 65 6d 73 65 74 28 70 4e  e;.    memset(pN
0ba0: 65 77 2c 20 30 2c 20 73 69 7a 65 6f 66 28 46 74  ew, 0, sizeof(Ft
0bb0: 73 35 48 61 73 68 29 29 3b 0a 20 20 20 20 70 4e  s5Hash));.    pN
0bc0: 65 77 2d 3e 70 6e 42 79 74 65 20 3d 20 70 6e 42  ew->pnByte = pnB
0bd0: 79 74 65 3b 0a 0a 20 20 20 20 70 4e 65 77 2d 3e  yte;..    pNew->
0be0: 6e 53 6c 6f 74 20 3d 20 31 30 32 34 3b 0a 20 20  nSlot = 1024;.  
0bf0: 20 20 6e 42 79 74 65 20 3d 20 73 69 7a 65 6f 66    nByte = sizeof
0c00: 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29  (Fts5HashEntry*)
0c10: 20 2a 20 70 4e 65 77 2d 3e 6e 53 6c 6f 74 3b 0a   * pNew->nSlot;.
0c20: 20 20 20 20 70 4e 65 77 2d 3e 61 53 6c 6f 74 20      pNew->aSlot 
0c30: 3d 20 28 46 74 73 35 48 61 73 68 45 6e 74 72 79  = (Fts5HashEntry
0c40: 2a 2a 29 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f  **)sqlite3_mallo
0c50: 63 28 6e 42 79 74 65 29 3b 0a 20 20 20 20 69 66  c(nByte);.    if
0c60: 28 20 70 4e 65 77 2d 3e 61 53 6c 6f 74 3d 3d 30  ( pNew->aSlot==0
0c70: 20 29 7b 0a 20 20 20 20 20 20 73 71 6c 69 74 65   ){.      sqlite
0c80: 33 5f 66 72 65 65 28 70 4e 65 77 29 3b 0a 20 20  3_free(pNew);.  
0c90: 20 20 20 20 2a 70 70 4e 65 77 20 3d 20 30 3b 0a      *ppNew = 0;.
0ca0: 20 20 20 20 20 20 72 63 20 3d 20 53 51 4c 49 54        rc = SQLIT
0cb0: 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 7d 65 6c  E_NOMEM;.    }el
0cc0: 73 65 7b 0a 20 20 20 20 20 20 6d 65 6d 73 65 74  se{.      memset
0cd0: 28 70 4e 65 77 2d 3e 61 53 6c 6f 74 2c 20 30 2c  (pNew->aSlot, 0,
0ce0: 20 6e 42 79 74 65 29 3b 0a 20 20 20 20 7d 0a 20   nByte);.    }. 
0cf0: 20 7d 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a   }.  return rc;.
0d00: 7d 0a 0a 2f 2a 0a 2a 2a 20 46 72 65 65 20 61 20  }../*.** Free a 
0d10: 68 61 73 68 20 74 61 62 6c 65 20 6f 62 6a 65 63  hash table objec
0d20: 74 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74  t..*/.void sqlit
0d30: 65 33 46 74 73 35 48 61 73 68 46 72 65 65 28 46  e3Fts5HashFree(F
0d40: 74 73 35 48 61 73 68 20 2a 70 48 61 73 68 29 7b  ts5Hash *pHash){
0d50: 0a 20 20 69 66 28 20 70 48 61 73 68 20 29 7b 0a  .  if( pHash ){.
0d60: 20 20 20 20 73 71 6c 69 74 65 33 46 74 73 35 48      sqlite3Fts5H
0d70: 61 73 68 43 6c 65 61 72 28 70 48 61 73 68 29 3b  ashClear(pHash);
0d80: 0a 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65  .    sqlite3_fre
0d90: 65 28 70 48 61 73 68 2d 3e 61 53 6c 6f 74 29 3b  e(pHash->aSlot);
0da0: 0a 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65  .    sqlite3_fre
0db0: 65 28 70 48 61 73 68 29 3b 0a 20 20 7d 0a 7d 0a  e(pHash);.  }.}.
0dc0: 0a 2f 2a 0a 2a 2a 20 45 6d 70 74 79 20 28 62 75  ./*.** Empty (bu
0dd0: 74 20 64 6f 20 6e 6f 74 20 64 65 6c 65 74 65 29  t do not delete)
0de0: 20 61 20 68 61 73 68 20 74 61 62 6c 65 2e 0a 2a   a hash table..*
0df0: 2f 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 46 74  /.void sqlite3Ft
0e00: 73 35 48 61 73 68 43 6c 65 61 72 28 46 74 73 35  s5HashClear(Fts5
0e10: 48 61 73 68 20 2a 70 48 61 73 68 29 7b 0a 20 20  Hash *pHash){.  
0e20: 69 6e 74 20 69 3b 0a 20 20 66 6f 72 28 69 3d 30  int i;.  for(i=0
0e30: 3b 20 69 3c 70 48 61 73 68 2d 3e 6e 53 6c 6f 74  ; i<pHash->nSlot
0e40: 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 46 74 73 35  ; i++){.    Fts5
0e50: 48 61 73 68 45 6e 74 72 79 20 2a 70 4e 65 78 74  HashEntry *pNext
0e60: 3b 0a 20 20 20 20 46 74 73 35 48 61 73 68 45 6e  ;.    Fts5HashEn
0e70: 74 72 79 20 2a 70 53 6c 6f 74 3b 0a 20 20 20 20  try *pSlot;.    
0e80: 66 6f 72 28 70 53 6c 6f 74 3d 70 48 61 73 68 2d  for(pSlot=pHash-
0e90: 3e 61 53 6c 6f 74 5b 69 5d 3b 20 70 53 6c 6f 74  >aSlot[i]; pSlot
0ea0: 3b 20 70 53 6c 6f 74 3d 70 4e 65 78 74 29 7b 0a  ; pSlot=pNext){.
0eb0: 20 20 20 20 20 20 70 4e 65 78 74 20 3d 20 70 53        pNext = pS
0ec0: 6c 6f 74 2d 3e 70 48 61 73 68 4e 65 78 74 3b 0a  lot->pHashNext;.
0ed0: 20 20 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72        sqlite3_fr
0ee0: 65 65 28 70 53 6c 6f 74 29 3b 0a 20 20 20 20 7d  ee(pSlot);.    }
0ef0: 0a 20 20 7d 0a 20 20 6d 65 6d 73 65 74 28 70 48  .  }.  memset(pH
0f00: 61 73 68 2d 3e 61 53 6c 6f 74 2c 20 30 2c 20 70  ash->aSlot, 0, p
0f10: 48 61 73 68 2d 3e 6e 53 6c 6f 74 20 2a 20 73 69  Hash->nSlot * si
0f20: 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74  zeof(Fts5HashEnt
0f30: 72 79 2a 29 29 3b 0a 20 20 70 48 61 73 68 2d 3e  ry*));.  pHash->
0f40: 6e 45 6e 74 72 79 20 3d 20 30 3b 0a 7d 0a 0a 73  nEntry = 0;.}..s
0f50: 74 61 74 69 63 20 75 6e 73 69 67 6e 65 64 20 69  tatic unsigned i
0f60: 6e 74 20 66 74 73 35 48 61 73 68 4b 65 79 28 69  nt fts5HashKey(i
0f70: 6e 74 20 6e 53 6c 6f 74 2c 20 63 6f 6e 73 74 20  nt nSlot, const 
0f80: 63 68 61 72 20 2a 70 2c 20 69 6e 74 20 6e 29 7b  char *p, int n){
0f90: 0a 20 20 69 6e 74 20 69 3b 0a 20 20 75 6e 73 69  .  int i;.  unsi
0fa0: 67 6e 65 64 20 69 6e 74 20 68 20 3d 20 31 33 3b  gned int h = 13;
0fb0: 0a 20 20 66 6f 72 28 69 3d 6e 2d 31 3b 20 69 3e  .  for(i=n-1; i>
0fc0: 3d 30 3b 20 69 2d 2d 29 7b 0a 20 20 20 20 68 20  =0; i--){.    h 
0fd0: 3d 20 28 68 20 3c 3c 20 33 29 20 5e 20 68 20 5e  = (h << 3) ^ h ^
0fe0: 20 70 5b 69 5d 3b 0a 20 20 7d 0a 20 20 72 65 74   p[i];.  }.  ret
0ff0: 75 72 6e 20 28 68 20 25 20 6e 53 6c 6f 74 29 3b  urn (h % nSlot);
1000: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 73 69 7a 65  .}../*.** Resize
1010: 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20   the hash table 
1020: 62 79 20 64 6f 75 62 6c 69 6e 67 20 74 68 65 20  by doubling the 
1030: 6e 75 6d 62 65 72 20 6f 66 20 73 6c 6f 74 73 2e  number of slots.
1040: 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 66  .*/.static int f
1050: 74 73 35 48 61 73 68 52 65 73 69 7a 65 28 46 74  ts5HashResize(Ft
1060: 73 35 48 61 73 68 20 2a 70 48 61 73 68 29 7b 0a  s5Hash *pHash){.
1070: 20 20 69 6e 74 20 6e 4e 65 77 20 3d 20 70 48 61    int nNew = pHa
1080: 73 68 2d 3e 6e 53 6c 6f 74 2a 32 3b 0a 20 20 69  sh->nSlot*2;.  i
1090: 6e 74 20 69 3b 0a 20 20 46 74 73 35 48 61 73 68  nt i;.  Fts5Hash
10a0: 45 6e 74 72 79 20 2a 2a 61 70 4e 65 77 3b 0a 20  Entry **apNew;. 
10b0: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
10c0: 2a 61 70 4f 6c 64 20 3d 20 70 48 61 73 68 2d 3e  *apOld = pHash->
10d0: 61 53 6c 6f 74 3b 0a 0a 20 20 61 70 4e 65 77 20  aSlot;..  apNew 
10e0: 3d 20 28 46 74 73 35 48 61 73 68 45 6e 74 72 79  = (Fts5HashEntry
10f0: 2a 2a 29 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f  **)sqlite3_mallo
1100: 63 28 6e 4e 65 77 2a 73 69 7a 65 6f 66 28 46 74  c(nNew*sizeof(Ft
1110: 73 35 48 61 73 68 45 6e 74 72 79 2a 29 29 3b 0a  s5HashEntry*));.
1120: 20 20 69 66 28 20 21 61 70 4e 65 77 20 29 20 72    if( !apNew ) r
1130: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d  eturn SQLITE_NOM
1140: 45 4d 3b 0a 20 20 6d 65 6d 73 65 74 28 61 70 4e  EM;.  memset(apN
1150: 65 77 2c 20 30 2c 20 6e 4e 65 77 2a 73 69 7a 65  ew, 0, nNew*size
1160: 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79  of(Fts5HashEntry
1170: 2a 29 29 3b 0a 0a 20 20 66 6f 72 28 69 3d 30 3b  *));..  for(i=0;
1180: 20 69 3c 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 3b   i<pHash->nSlot;
1190: 20 69 2b 2b 29 7b 0a 20 20 20 20 77 68 69 6c 65   i++){.    while
11a0: 28 20 61 70 4f 6c 64 5b 69 5d 20 29 7b 0a 20 20  ( apOld[i] ){.  
11b0: 20 20 20 20 69 6e 74 20 69 48 61 73 68 3b 0a 20      int iHash;. 
11c0: 20 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74       Fts5HashEnt
11d0: 72 79 20 2a 70 20 3d 20 61 70 4f 6c 64 5b 69 5d  ry *p = apOld[i]
11e0: 3b 0a 20 20 20 20 20 20 61 70 4f 6c 64 5b 69 5d  ;.      apOld[i]
11f0: 20 3d 20 70 2d 3e 70 48 61 73 68 4e 65 78 74 3b   = p->pHashNext;
1200: 0a 20 20 20 20 20 20 69 48 61 73 68 20 3d 20 66  .      iHash = f
1210: 74 73 35 48 61 73 68 4b 65 79 28 6e 4e 65 77 2c  ts5HashKey(nNew,
1220: 20 70 2d 3e 7a 4b 65 79 2c 20 73 74 72 6c 65 6e   p->zKey, strlen
1230: 28 70 2d 3e 7a 4b 65 79 29 29 3b 0a 20 20 20 20  (p->zKey));.    
1240: 20 20 70 2d 3e 70 48 61 73 68 4e 65 78 74 20 3d    p->pHashNext =
1250: 20 61 70 4e 65 77 5b 69 48 61 73 68 5d 3b 0a 20   apNew[iHash];. 
1260: 20 20 20 20 20 61 70 4e 65 77 5b 69 48 61 73 68       apNew[iHash
1270: 5d 20 3d 20 70 3b 0a 20 20 20 20 7d 0a 20 20 7d  ] = p;.    }.  }
1280: 0a 0a 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65  ..  sqlite3_free
1290: 28 61 70 4f 6c 64 29 3b 0a 20 20 70 48 61 73 68  (apOld);.  pHash
12a0: 2d 3e 6e 53 6c 6f 74 20 3d 20 6e 4e 65 77 3b 0a  ->nSlot = nNew;.
12b0: 20 20 70 48 61 73 68 2d 3e 61 53 6c 6f 74 20 3d    pHash->aSlot =
12c0: 20 61 70 4e 65 77 3b 0a 20 20 72 65 74 75 72 6e   apNew;.  return
12d0: 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 69   SQLITE_OK;.}..i
12e0: 6e 74 20 73 71 6c 69 74 65 33 46 74 73 35 48 61  nt sqlite3Fts5Ha
12f0: 73 68 57 72 69 74 65 28 0a 20 20 46 74 73 35 48  shWrite(.  Fts5H
1300: 61 73 68 20 2a 70 48 61 73 68 2c 0a 20 20 69 36  ash *pHash,.  i6
1310: 34 20 69 52 6f 77 69 64 2c 20 20 20 20 20 20 20  4 iRowid,       
1320: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
1330: 20 52 6f 77 69 64 20 66 6f 72 20 74 68 69 73 20   Rowid for this 
1340: 65 6e 74 72 79 20 2a 2f 0a 20 20 69 6e 74 20 69  entry */.  int i
1350: 43 6f 6c 2c 20 20 20 20 20 20 20 20 20 20 20 20  Col,            
1360: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 6f             /* Co
1370: 6c 75 6d 6e 20 74 6f 6b 65 6e 20 61 70 70 65 61  lumn token appea
1380: 72 73 20 69 6e 20 28 2d 76 65 20 2d 3e 20 64 65  rs in (-ve -> de
1390: 6c 65 74 65 29 20 2a 2f 0a 20 20 69 6e 74 20 69  lete) */.  int i
13a0: 50 6f 73 2c 20 20 20 20 20 20 20 20 20 20 20 20  Pos,            
13b0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f             /* Po
13c0: 73 69 74 69 6f 6e 20 6f 66 20 74 6f 6b 65 6e 20  sition of token 
13d0: 77 69 74 68 69 6e 20 63 6f 6c 75 6d 6e 20 2a 2f  within column */
13e0: 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70  .  const char *p
13f0: 54 6f 6b 65 6e 2c 20 69 6e 74 20 6e 54 6f 6b 65  Token, int nToke
1400: 6e 20 20 2f 2a 20 54 6f 6b 65 6e 20 74 6f 20 61  n  /* Token to a
1410: 64 64 20 6f 72 20 72 65 6d 6f 76 65 20 74 6f 20  dd or remove to 
1420: 6f 72 20 66 72 6f 6d 20 69 6e 64 65 78 20 2a 2f  or from index */
1430: 0a 29 7b 0a 20 20 75 6e 73 69 67 6e 65 64 20 69  .){.  unsigned i
1440: 6e 74 20 69 48 61 73 68 20 3d 20 66 74 73 35 48  nt iHash = fts5H
1450: 61 73 68 4b 65 79 28 70 48 61 73 68 2d 3e 6e 53  ashKey(pHash->nS
1460: 6c 6f 74 2c 20 70 54 6f 6b 65 6e 2c 20 6e 54 6f  lot, pToken, nTo
1470: 6b 65 6e 29 3b 0a 20 20 46 74 73 35 48 61 73 68  ken);.  Fts5Hash
1480: 45 6e 74 72 79 20 2a 70 3b 0a 20 20 75 38 20 2a  Entry *p;.  u8 *
1490: 70 50 74 72 3b 0a 20 20 69 6e 74 20 6e 49 6e 63  pPtr;.  int nInc
14a0: 72 20 3d 20 30 3b 20 20 20 20 20 20 20 20 20 20  r = 0;          
14b0: 20 20 20 20 20 20 20 20 2f 2a 20 41 6d 6f 75 6e          /* Amoun
14c0: 74 20 74 6f 20 69 6e 63 72 65 6d 65 6e 74 20 28  t to increment (
14d0: 2a 70 48 61 73 68 2d 3e 70 6e 42 79 74 65 29 20  *pHash->pnByte) 
14e0: 62 79 20 2a 2f 0a 0a 20 20 2f 2a 20 41 74 74 65  by */..  /* Atte
14f0: 6d 70 74 20 74 6f 20 6c 6f 63 61 74 65 20 61 6e  mpt to locate an
1500: 20 65 78 69 73 74 69 6e 67 20 68 61 73 68 20 65   existing hash e
1510: 6e 74 72 79 20 2a 2f 0a 20 20 66 6f 72 28 70 3d  ntry */.  for(p=
1520: 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 48 61  pHash->aSlot[iHa
1530: 73 68 5d 3b 20 70 3b 20 70 3d 70 2d 3e 70 48 61  sh]; p; p=p->pHa
1540: 73 68 4e 65 78 74 29 7b 0a 20 20 20 20 69 66 28  shNext){.    if(
1550: 20 6d 65 6d 63 6d 70 28 70 2d 3e 7a 4b 65 79 2c   memcmp(p->zKey,
1560: 20 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b 65 6e 29   pToken, nToken)
1570: 3d 3d 30 20 26 26 20 70 2d 3e 7a 4b 65 79 5b 6e  ==0 && p->zKey[n
1580: 54 6f 6b 65 6e 5d 3d 3d 30 20 29 20 62 72 65 61  Token]==0 ) brea
1590: 6b 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 49 66 20  k;.  }..  /* If 
15a0: 61 6e 20 65 78 69 73 74 69 6e 67 20 68 61 73 68  an existing hash
15b0: 20 65 6e 74 72 79 20 63 61 6e 6e 6f 74 20 62 65   entry cannot be
15c0: 20 66 6f 75 6e 64 2c 20 63 72 65 61 74 65 20 61   found, create a
15d0: 20 6e 65 77 20 6f 6e 65 2e 20 2a 2f 0a 20 20 69   new one. */.  i
15e0: 66 28 20 70 3d 3d 30 20 29 7b 0a 20 20 20 20 69  f( p==0 ){.    i
15f0: 6e 74 20 6e 42 79 74 65 20 3d 20 73 69 7a 65 6f  nt nByte = sizeo
1600: 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 29  f(Fts5HashEntry)
1610: 20 2b 20 6e 54 6f 6b 65 6e 20 2b 20 31 20 2b 20   + nToken + 1 + 
1620: 36 34 3b 0a 20 20 20 20 69 66 28 20 6e 42 79 74  64;.    if( nByt
1630: 65 3c 31 32 38 20 29 20 6e 42 79 74 65 20 3d 20  e<128 ) nByte = 
1640: 31 32 38 3b 0a 0a 20 20 20 20 69 66 28 20 28 70  128;..    if( (p
1650: 48 61 73 68 2d 3e 6e 45 6e 74 72 79 2a 32 29 3e  Hash->nEntry*2)>
1660: 3d 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 20 29 7b  =pHash->nSlot ){
1670: 0a 20 20 20 20 20 20 69 6e 74 20 72 63 20 3d 20  .      int rc = 
1680: 66 74 73 35 48 61 73 68 52 65 73 69 7a 65 28 70  fts5HashResize(p
1690: 48 61 73 68 29 3b 0a 20 20 20 20 20 20 69 66 28  Hash);.      if(
16a0: 20 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b 20 29   rc!=SQLITE_OK )
16b0: 20 72 65 74 75 72 6e 20 72 63 3b 0a 20 20 20 20   return rc;.    
16c0: 20 20 69 48 61 73 68 20 3d 20 66 74 73 35 48 61    iHash = fts5Ha
16d0: 73 68 4b 65 79 28 70 48 61 73 68 2d 3e 6e 53 6c  shKey(pHash->nSl
16e0: 6f 74 2c 20 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b  ot, pToken, nTok
16f0: 65 6e 29 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20  en);.    }..    
1700: 70 20 3d 20 28 46 74 73 35 48 61 73 68 45 6e 74  p = (Fts5HashEnt
1710: 72 79 2a 29 73 71 6c 69 74 65 33 5f 6d 61 6c 6c  ry*)sqlite3_mall
1720: 6f 63 28 6e 42 79 74 65 29 3b 0a 20 20 20 20 69  oc(nByte);.    i
1730: 66 28 20 21 70 20 29 20 72 65 74 75 72 6e 20 53  f( !p ) return S
1740: 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 20  QLITE_NOMEM;.   
1750: 20 6d 65 6d 73 65 74 28 70 2c 20 30 2c 20 73 69   memset(p, 0, si
1760: 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74  zeof(Fts5HashEnt
1770: 72 79 29 29 3b 0a 20 20 20 20 70 2d 3e 6e 41 6c  ry));.    p->nAl
1780: 6c 6f 63 20 3d 20 6e 42 79 74 65 3b 0a 20 20 20  loc = nByte;.   
1790: 20 6d 65 6d 63 70 79 28 70 2d 3e 7a 4b 65 79 2c   memcpy(p->zKey,
17a0: 20 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b 65 6e 29   pToken, nToken)
17b0: 3b 0a 20 20 20 20 70 2d 3e 7a 4b 65 79 5b 6e 54  ;.    p->zKey[nT
17c0: 6f 6b 65 6e 5d 20 3d 20 27 5c 30 27 3b 0a 20 20  oken] = '\0';.  
17d0: 20 20 70 2d 3e 6e 44 61 74 61 20 3d 20 6e 54 6f    p->nData = nTo
17e0: 6b 65 6e 20 2b 20 31 20 2b 20 73 69 7a 65 6f 66  ken + 1 + sizeof
17f0: 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 29 3b  (Fts5HashEntry);
1800: 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d  .    p->nData +=
1810: 20 73 71 6c 69 74 65 33 50 75 74 56 61 72 69 6e   sqlite3PutVarin
1820: 74 28 26 28 28 75 38 2a 29 70 29 5b 70 2d 3e 6e  t(&((u8*)p)[p->n
1830: 44 61 74 61 5d 2c 20 69 52 6f 77 69 64 29 3b 0a  Data], iRowid);.
1840: 20 20 20 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73      p->iSzPoslis
1850: 74 20 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20 20  t = p->nData;.  
1860: 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 34 3b    p->nData += 4;
1870: 0a 20 20 20 20 70 2d 3e 69 52 6f 77 69 64 20 3d  .    p->iRowid =
1880: 20 69 52 6f 77 69 64 3b 0a 20 20 20 20 70 2d 3e   iRowid;.    p->
1890: 70 48 61 73 68 4e 65 78 74 20 3d 20 70 48 61 73  pHashNext = pHas
18a0: 68 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d 3b  h->aSlot[iHash];
18b0: 0a 20 20 20 20 70 48 61 73 68 2d 3e 61 53 6c 6f  .    pHash->aSlo
18c0: 74 5b 69 48 61 73 68 5d 20 3d 20 70 3b 0a 20 20  t[iHash] = p;.  
18d0: 20 20 70 48 61 73 68 2d 3e 6e 45 6e 74 72 79 2b    pHash->nEntry+
18e0: 2b 3b 0a 20 20 20 20 6e 49 6e 63 72 20 2b 3d 20  +;.    nIncr += 
18f0: 70 2d 3e 6e 44 61 74 61 3b 0a 20 20 7d 0a 0a 20  p->nData;.  }.. 
1900: 20 2f 2a 20 43 68 65 63 6b 20 74 68 65 72 65 20   /* Check there 
1910: 69 73 20 65 6e 6f 75 67 68 20 73 70 61 63 65 20  is enough space 
1920: 74 6f 20 61 70 70 65 6e 64 20 61 20 6e 65 77 20  to append a new 
1930: 65 6e 74 72 79 2e 20 57 6f 72 73 74 20 63 61 73  entry. Worst cas
1940: 65 20 73 63 65 6e 61 72 69 6f 0a 20 20 2a 2a 20  e scenario.  ** 
1950: 69 73 3a 0a 20 20 2a 2a 0a 20 20 2a 2a 20 20 20  is:.  **.  **   
1960: 20 20 2b 20 39 20 62 79 74 65 73 20 66 6f 72 20    + 9 bytes for 
1970: 61 20 6e 65 77 20 72 6f 77 69 64 2c 0a 20 20 2a  a new rowid,.  *
1980: 2a 20 20 20 20 20 2b 20 34 20 62 79 74 65 73 20  *     + 4 bytes 
1990: 72 65 73 65 72 76 65 64 20 66 6f 72 20 74 68 65  reserved for the
19a0: 20 22 70 6f 73 6c 69 73 74 20 73 69 7a 65 22 20   "poslist size" 
19b0: 76 61 72 69 6e 74 2e 0a 20 20 2a 2a 20 20 20 20  varint..  **    
19c0: 20 2b 20 31 20 62 79 74 65 20 66 6f 72 20 61 20   + 1 byte for a 
19d0: 22 6e 65 77 20 63 6f 6c 75 6d 6e 22 20 62 79 74  "new column" byt
19e0: 65 2c 0a 20 20 2a 2a 20 20 20 20 20 2b 20 33 20  e,.  **     + 3 
19f0: 62 79 74 65 73 20 66 6f 72 20 61 20 6e 65 77 20  bytes for a new 
1a00: 63 6f 6c 75 6d 6e 20 6e 75 6d 62 65 72 20 28 31  column number (1
1a10: 36 2d 62 69 74 20 6d 61 78 29 20 61 73 20 61 20  6-bit max) as a 
1a20: 76 61 72 69 6e 74 2c 0a 20 20 2a 2a 20 20 20 20  varint,.  **    
1a30: 20 2b 20 35 20 62 79 74 65 73 20 66 6f 72 20 74   + 5 bytes for t
1a40: 68 65 20 6e 65 77 20 70 6f 73 69 74 69 6f 6e 20  he new position 
1a50: 6f 66 66 73 65 74 20 28 33 32 2d 62 69 74 20 6d  offset (32-bit m
1a60: 61 78 29 2e 0a 20 20 2a 2f 0a 20 20 69 66 28 20  ax)..  */.  if( 
1a70: 28 70 2d 3e 6e 41 6c 6c 6f 63 20 2d 20 70 2d 3e  (p->nAlloc - p->
1a80: 6e 44 61 74 61 29 20 3c 20 28 39 20 2b 20 34 20  nData) < (9 + 4 
1a90: 2b 20 31 20 2b 20 33 20 2b 20 35 29 20 29 7b 0a  + 1 + 3 + 5) ){.
1aa0: 20 20 20 20 69 6e 74 20 6e 4e 65 77 20 3d 20 70      int nNew = p
1ab0: 2d 3e 6e 41 6c 6c 6f 63 20 2a 20 32 3b 0a 20 20  ->nAlloc * 2;.  
1ac0: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20    Fts5HashEntry 
1ad0: 2a 70 4e 65 77 3b 0a 20 20 20 20 46 74 73 35 48  *pNew;.    Fts5H
1ae0: 61 73 68 45 6e 74 72 79 20 2a 2a 70 70 3b 0a 20  ashEntry **pp;. 
1af0: 20 20 20 70 4e 65 77 20 3d 20 28 46 74 73 35 48     pNew = (Fts5H
1b00: 61 73 68 45 6e 74 72 79 2a 29 73 71 6c 69 74 65  ashEntry*)sqlite
1b10: 33 5f 72 65 61 6c 6c 6f 63 28 70 2c 20 6e 4e 65  3_realloc(p, nNe
1b20: 77 29 3b 0a 20 20 20 20 69 66 28 20 70 4e 65 77  w);.    if( pNew
1b30: 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 53 51 4c  ==0 ) return SQL
1b40: 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 70  ITE_NOMEM;.    p
1b50: 4e 65 77 2d 3e 6e 41 6c 6c 6f 63 20 3d 20 6e 4e  New->nAlloc = nN
1b60: 65 77 3b 0a 20 20 20 20 66 6f 72 28 70 70 3d 26  ew;.    for(pp=&
1b70: 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 48 61  pHash->aSlot[iHa
1b80: 73 68 5d 3b 20 2a 70 70 21 3d 70 3b 20 70 70 3d  sh]; *pp!=p; pp=
1b90: 26 28 2a 70 70 29 2d 3e 70 48 61 73 68 4e 65 78  &(*pp)->pHashNex
1ba0: 74 29 3b 0a 20 20 20 20 2a 70 70 20 3d 20 70 4e  t);.    *pp = pN
1bb0: 65 77 3b 0a 20 20 20 20 70 20 3d 20 70 4e 65 77  ew;.    p = pNew
1bc0: 3b 0a 20 20 7d 0a 20 20 70 50 74 72 20 3d 20 28  ;.  }.  pPtr = (
1bd0: 75 38 2a 29 70 3b 0a 20 20 6e 49 6e 63 72 20 2d  u8*)p;.  nIncr -
1be0: 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 0a 20 20 2f  = p->nData;..  /
1bf0: 2a 20 49 66 20 74 68 69 73 20 69 73 20 61 20 6e  * If this is a n
1c00: 65 77 20 72 6f 77 69 64 2c 20 61 70 70 65 6e 64  ew rowid, append
1c10: 20 74 68 65 20 34 2d 62 79 74 65 20 73 69 7a 65   the 4-byte size
1c20: 20 66 69 65 6c 64 20 66 6f 72 20 74 68 65 20 70   field for the p
1c30: 72 65 76 69 6f 75 73 0a 20 20 2a 2a 20 65 6e 74  revious.  ** ent
1c40: 72 79 2c 20 61 6e 64 20 74 68 65 20 6e 65 77 20  ry, and the new 
1c50: 72 6f 77 69 64 20 66 6f 72 20 74 68 69 73 20 65  rowid for this e
1c60: 6e 74 72 79 2e 20 20 2a 2f 0a 20 20 69 66 28 20  ntry.  */.  if( 
1c70: 69 52 6f 77 69 64 21 3d 70 2d 3e 69 52 6f 77 69  iRowid!=p->iRowi
1c80: 64 20 29 7b 0a 20 20 20 20 61 73 73 65 72 74 28  d ){.    assert(
1c90: 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 3e 30   p->iSzPoslist>0
1ca0: 20 29 3b 0a 20 20 20 20 66 74 73 35 50 75 74 34   );.    fts5Put4
1cb0: 42 79 74 65 56 61 72 69 6e 74 28 26 70 50 74 72  ByteVarint(&pPtr
1cc0: 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 5d 2c  [p->iSzPoslist],
1cd0: 20 70 2d 3e 6e 44 61 74 61 20 2d 20 70 2d 3e 69   p->nData - p->i
1ce0: 53 7a 50 6f 73 6c 69 73 74 20 2d 20 34 29 3b 0a  SzPoslist - 4);.
1cf0: 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20      p->nData += 
1d00: 73 71 6c 69 74 65 33 50 75 74 56 61 72 69 6e 74  sqlite3PutVarint
1d10: 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61 5d  (&pPtr[p->nData]
1d20: 2c 20 69 52 6f 77 69 64 20 2d 20 70 2d 3e 69 52  , iRowid - p->iR
1d30: 6f 77 69 64 29 3b 0a 20 20 20 20 70 2d 3e 69 53  owid);.    p->iS
1d40: 7a 50 6f 73 6c 69 73 74 20 3d 20 70 2d 3e 6e 44  zPoslist = p->nD
1d50: 61 74 61 3b 0a 20 20 20 20 70 2d 3e 6e 44 61 74  ata;.    p->nDat
1d60: 61 20 2b 3d 20 34 3b 0a 20 20 20 20 70 2d 3e 69  a += 4;.    p->i
1d70: 43 6f 6c 20 3d 20 30 3b 0a 20 20 20 20 70 2d 3e  Col = 0;.    p->
1d80: 69 50 6f 73 20 3d 20 30 3b 0a 20 20 20 20 70 2d  iPos = 0;.    p-
1d90: 3e 69 52 6f 77 69 64 20 3d 20 69 52 6f 77 69 64  >iRowid = iRowid
1da0: 3b 0a 20 20 7d 0a 0a 20 20 69 66 28 20 69 43 6f  ;.  }..  if( iCo
1db0: 6c 3e 3d 30 20 29 7b 0a 20 20 20 20 2f 2a 20 41  l>=0 ){.    /* A
1dc0: 70 70 65 6e 64 20 61 20 6e 65 77 20 63 6f 6c 75  ppend a new colu
1dd0: 6d 6e 20 76 61 6c 75 65 2c 20 69 66 20 6e 65 63  mn value, if nec
1de0: 65 73 73 61 72 79 20 2a 2f 0a 20 20 20 20 61 73  essary */.    as
1df0: 73 65 72 74 28 20 69 43 6f 6c 3e 3d 70 2d 3e 69  sert( iCol>=p->i
1e00: 43 6f 6c 20 29 3b 0a 20 20 20 20 69 66 28 20 69  Col );.    if( i
1e10: 43 6f 6c 21 3d 70 2d 3e 69 43 6f 6c 20 29 7b 0a  Col!=p->iCol ){.
1e20: 20 20 20 20 20 20 70 50 74 72 5b 70 2d 3e 6e 44        pPtr[p->nD
1e30: 61 74 61 2b 2b 5d 20 3d 20 30 78 30 31 3b 0a 20  ata++] = 0x01;. 
1e40: 20 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d       p->nData +=
1e50: 20 73 71 6c 69 74 65 33 50 75 74 56 61 72 69 6e   sqlite3PutVarin
1e60: 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61  t(&pPtr[p->nData
1e70: 5d 2c 20 69 43 6f 6c 29 3b 0a 20 20 20 20 20 20  ], iCol);.      
1e80: 70 2d 3e 69 43 6f 6c 20 3d 20 69 43 6f 6c 3b 0a  p->iCol = iCol;.
1e90: 20 20 20 20 20 20 70 2d 3e 69 50 6f 73 20 3d 20        p->iPos = 
1ea0: 30 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f 2a  0;.    }..    /*
1eb0: 20 41 70 70 65 6e 64 20 74 68 65 20 6e 65 77 20   Append the new 
1ec0: 70 6f 73 69 74 69 6f 6e 20 6f 66 66 73 65 74 20  position offset 
1ed0: 2a 2f 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20  */.    p->nData 
1ee0: 2b 3d 20 73 71 6c 69 74 65 33 50 75 74 56 61 72  += sqlite3PutVar
1ef0: 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61  int(&pPtr[p->nDa
1f00: 74 61 5d 2c 20 69 50 6f 73 20 2d 20 70 2d 3e 69  ta], iPos - p->i
1f10: 50 6f 73 20 2b 20 32 29 3b 0a 20 20 20 20 70 2d  Pos + 2);.    p-
1f20: 3e 69 50 6f 73 20 3d 20 69 50 6f 73 3b 0a 20 20  >iPos = iPos;.  
1f30: 7d 0a 20 20 6e 49 6e 63 72 20 2b 3d 20 70 2d 3e  }.  nIncr += p->
1f40: 6e 44 61 74 61 3b 0a 0a 20 20 2a 70 48 61 73 68  nData;..  *pHash
1f50: 2d 3e 70 6e 42 79 74 65 20 2b 3d 20 6e 49 6e 63  ->pnByte += nInc
1f60: 72 3b 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49  r;.  return SQLI
1f70: 54 45 5f 4f 4b 3b 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a  TE_OK;.}.../*.**
1f80: 20 41 72 67 75 6d 65 6e 74 73 20 70 4c 65 66 74   Arguments pLeft
1f90: 20 61 6e 64 20 70 52 69 67 68 74 20 70 6f 69 6e   and pRight poin
1fa0: 74 20 74 6f 20 6c 69 6e 6b 65 64 2d 6c 69 73 74  t to linked-list
1fb0: 73 20 6f 66 20 68 61 73 68 2d 65 6e 74 72 79 20  s of hash-entry 
1fc0: 6f 62 6a 65 63 74 73 2c 0a 2a 2a 20 65 61 63 68  objects,.** each
1fd0: 20 73 6f 72 74 65 64 20 69 6e 20 6b 65 79 20 6f   sorted in key o
1fe0: 72 64 65 72 2e 20 54 68 69 73 20 66 75 6e 63 74  rder. This funct
1ff0: 69 6f 6e 20 6d 65 72 67 65 73 20 74 68 65 20 74  ion merges the t
2000: 77 6f 20 6c 69 73 74 73 20 69 6e 74 6f 20 61 0a  wo lists into a.
2010: 2a 2a 20 73 69 6e 67 6c 65 20 6c 69 73 74 20 61  ** single list a
2020: 6e 64 20 72 65 74 75 72 6e 73 20 61 20 70 6f 69  nd returns a poi
2030: 6e 74 65 72 20 74 6f 20 69 74 73 20 66 69 72 73  nter to its firs
2040: 74 20 65 6c 65 6d 65 6e 74 2e 0a 2a 2f 0a 73 74  t element..*/.st
2050: 61 74 69 63 20 46 74 73 35 48 61 73 68 45 6e 74  atic Fts5HashEnt
2060: 72 79 20 2a 66 74 73 35 48 61 73 68 45 6e 74 72  ry *fts5HashEntr
2070: 79 4d 65 72 67 65 28 0a 20 20 46 74 73 35 48 61  yMerge(.  Fts5Ha
2080: 73 68 45 6e 74 72 79 20 2a 70 4c 65 66 74 2c 0a  shEntry *pLeft,.
2090: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20    Fts5HashEntry 
20a0: 2a 70 52 69 67 68 74 0a 29 7b 0a 20 20 46 74 73  *pRight.){.  Fts
20b0: 35 48 61 73 68 45 6e 74 72 79 20 2a 70 31 20 3d  5HashEntry *p1 =
20c0: 20 70 4c 65 66 74 3b 0a 20 20 46 74 73 35 48 61   pLeft;.  Fts5Ha
20d0: 73 68 45 6e 74 72 79 20 2a 70 32 20 3d 20 70 52  shEntry *p2 = pR
20e0: 69 67 68 74 3b 0a 20 20 46 74 73 35 48 61 73 68  ight;.  Fts5Hash
20f0: 45 6e 74 72 79 20 2a 70 52 65 74 20 3d 20 30 3b  Entry *pRet = 0;
2100: 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  .  Fts5HashEntry
2110: 20 2a 2a 70 70 4f 75 74 20 3d 20 26 70 52 65 74   **ppOut = &pRet
2120: 3b 0a 0a 20 20 77 68 69 6c 65 28 20 70 31 20 7c  ;..  while( p1 |
2130: 7c 20 70 32 20 29 7b 0a 20 20 20 20 69 66 28 20  | p2 ){.    if( 
2140: 70 31 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 2a  p1==0 ){.      *
2150: 70 70 4f 75 74 20 3d 20 70 32 3b 0a 20 20 20 20  ppOut = p2;.    
2160: 20 20 70 32 20 3d 20 30 3b 0a 20 20 20 20 7d 65    p2 = 0;.    }e
2170: 6c 73 65 20 69 66 28 20 70 32 3d 3d 30 20 29 7b  lse if( p2==0 ){
2180: 0a 20 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20  .      *ppOut = 
2190: 70 31 3b 0a 20 20 20 20 20 20 70 31 20 3d 20 30  p1;.      p1 = 0
21a0: 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20  ;.    }else{.   
21b0: 20 20 20 69 6e 74 20 69 20 3d 20 30 3b 0a 20 20     int i = 0;.  
21c0: 20 20 20 20 77 68 69 6c 65 28 20 70 31 2d 3e 7a      while( p1->z
21d0: 4b 65 79 5b 69 5d 3d 3d 70 32 2d 3e 7a 4b 65 79  Key[i]==p2->zKey
21e0: 5b 69 5d 20 29 20 69 2b 2b 3b 0a 0a 20 20 20 20  [i] ) i++;..    
21f0: 20 20 69 66 28 20 28 28 75 38 29 70 31 2d 3e 7a    if( ((u8)p1->z
2200: 4b 65 79 5b 69 5d 29 3e 28 28 75 38 29 70 32 2d  Key[i])>((u8)p2-
2210: 3e 7a 4b 65 79 5b 69 5d 29 20 29 7b 0a 20 20 20  >zKey[i]) ){.   
2220: 20 20 20 20 20 2f 2a 20 70 32 20 69 73 20 73 6d       /* p2 is sm
2230: 61 6c 6c 65 72 20 2a 2f 0a 20 20 20 20 20 20 20  aller */.       
2240: 20 2a 70 70 4f 75 74 20 3d 20 70 32 3b 0a 20 20   *ppOut = p2;.  
2250: 20 20 20 20 20 20 70 70 4f 75 74 20 3d 20 26 70        ppOut = &p
2260: 32 2d 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 20 20  2->pScanNext;.  
2270: 20 20 20 20 20 20 70 32 20 3d 20 70 32 2d 3e 70        p2 = p2->p
2280: 53 63 61 6e 4e 65 78 74 3b 0a 20 20 20 20 20 20  ScanNext;.      
2290: 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 20 20 2f  }else{.        /
22a0: 2a 20 70 31 20 69 73 20 73 6d 61 6c 6c 65 72 20  * p1 is smaller 
22b0: 2a 2f 0a 20 20 20 20 20 20 20 20 2a 70 70 4f 75  */.        *ppOu
22c0: 74 20 3d 20 70 31 3b 0a 20 20 20 20 20 20 20 20  t = p1;.        
22d0: 70 70 4f 75 74 20 3d 20 26 70 31 2d 3e 70 53 63  ppOut = &p1->pSc
22e0: 61 6e 4e 65 78 74 3b 0a 20 20 20 20 20 20 20 20  anNext;.        
22f0: 70 31 20 3d 20 70 31 2d 3e 70 53 63 61 6e 4e 65  p1 = p1->pScanNe
2300: 78 74 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20  xt;.      }.    
2310: 20 20 2a 70 70 4f 75 74 20 3d 20 30 3b 0a 20 20    *ppOut = 0;.  
2320: 20 20 7d 0a 20 20 7d 0a 0a 20 20 72 65 74 75 72    }.  }..  retur
2330: 6e 20 70 52 65 74 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  n pRet;.}../*.**
2340: 20 45 78 74 72 61 63 74 20 61 6c 6c 20 74 6f 6b   Extract all tok
2350: 65 6e 73 20 66 72 6f 6d 20 68 61 73 68 20 74 61  ens from hash ta
2360: 62 6c 65 20 69 48 61 73 68 20 61 6e 64 20 6c 69  ble iHash and li
2370: 6e 6b 20 74 68 65 6d 20 69 6e 74 6f 20 61 20 6c  nk them into a l
2380: 69 73 74 0a 2a 2a 20 69 6e 20 73 6f 72 74 65 64  ist.** in sorted
2390: 20 6f 72 64 65 72 2e 20 54 68 65 20 68 61 73 68   order. The hash
23a0: 20 74 61 62 6c 65 20 69 73 20 63 6c 65 61 72 65   table is cleare
23b0: 64 20 62 65 66 6f 72 65 20 72 65 74 75 72 6e 69  d before returni
23c0: 6e 67 2e 20 49 74 20 69 73 0a 2a 2a 20 74 68 65  ng. It is.** the
23d0: 20 72 65 73 70 6f 6e 73 69 62 69 6c 69 74 79 20   responsibility 
23e0: 6f 66 20 74 68 65 20 63 61 6c 6c 65 72 20 74 6f  of the caller to
23f0: 20 66 72 65 65 20 74 68 65 20 65 6c 65 6d 65 6e   free the elemen
2400: 74 73 20 6f 66 20 74 68 65 20 72 65 74 75 72 6e  ts of the return
2410: 65 64 0a 2a 2a 20 6c 69 73 74 2e 0a 2a 2f 0a 73  ed.** list..*/.s
2420: 74 61 74 69 63 20 69 6e 74 20 66 74 73 35 48 61  tatic int fts5Ha
2430: 73 68 45 6e 74 72 79 53 6f 72 74 28 0a 20 20 46  shEntrySort(.  F
2440: 74 73 35 48 61 73 68 20 2a 70 48 61 73 68 2c 20  ts5Hash *pHash, 
2450: 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70  .  const char *p
2460: 54 65 72 6d 2c 20 69 6e 74 20 6e 54 65 72 6d 2c  Term, int nTerm,
2470: 20 20 20 2f 2a 20 51 75 65 72 79 20 70 72 65 66     /* Query pref
2480: 69 78 2c 20 69 66 20 61 6e 79 20 2a 2f 0a 20 20  ix, if any */.  
2490: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a  Fts5HashEntry **
24a0: 70 70 53 6f 72 74 65 64 0a 29 7b 0a 20 20 63 6f  ppSorted.){.  co
24b0: 6e 73 74 20 69 6e 74 20 6e 4d 65 72 67 65 53 6c  nst int nMergeSl
24c0: 6f 74 20 3d 20 33 32 3b 0a 20 20 46 74 73 35 48  ot = 32;.  Fts5H
24d0: 61 73 68 45 6e 74 72 79 20 2a 2a 61 70 3b 0a 20  ashEntry **ap;. 
24e0: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
24f0: 70 4c 69 73 74 3b 0a 20 20 69 6e 74 20 69 53 6c  pList;.  int iSl
2500: 6f 74 3b 0a 20 20 69 6e 74 20 69 3b 0a 0a 20 20  ot;.  int i;..  
2510: 2a 70 70 53 6f 72 74 65 64 20 3d 20 30 3b 0a 20  *ppSorted = 0;. 
2520: 20 61 70 20 3d 20 73 71 6c 69 74 65 33 5f 6d 61   ap = sqlite3_ma
2530: 6c 6c 6f 63 28 73 69 7a 65 6f 66 28 46 74 73 35  lloc(sizeof(Fts5
2540: 48 61 73 68 45 6e 74 72 79 2a 29 20 2a 20 6e 4d  HashEntry*) * nM
2550: 65 72 67 65 53 6c 6f 74 29 3b 0a 20 20 69 66 28  ergeSlot);.  if(
2560: 20 21 61 70 20 29 20 72 65 74 75 72 6e 20 53 51   !ap ) return SQ
2570: 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 6d 65  LITE_NOMEM;.  me
2580: 6d 73 65 74 28 61 70 2c 20 30 2c 20 73 69 7a 65  mset(ap, 0, size
2590: 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79  of(Fts5HashEntry
25a0: 2a 29 20 2a 20 6e 4d 65 72 67 65 53 6c 6f 74 29  *) * nMergeSlot)
25b0: 3b 0a 0a 20 20 66 6f 72 28 69 53 6c 6f 74 3d 30  ;..  for(iSlot=0
25c0: 3b 20 69 53 6c 6f 74 3c 70 48 61 73 68 2d 3e 6e  ; iSlot<pHash->n
25d0: 53 6c 6f 74 3b 20 69 53 6c 6f 74 2b 2b 29 7b 0a  Slot; iSlot++){.
25e0: 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74 72      Fts5HashEntr
25f0: 79 20 2a 70 49 74 65 72 3b 0a 20 20 20 20 66 6f  y *pIter;.    fo
2600: 72 28 70 49 74 65 72 3d 70 48 61 73 68 2d 3e 61  r(pIter=pHash->a
2610: 53 6c 6f 74 5b 69 53 6c 6f 74 5d 3b 20 70 49 74  Slot[iSlot]; pIt
2620: 65 72 3b 20 70 49 74 65 72 3d 70 49 74 65 72 2d  er; pIter=pIter-
2630: 3e 70 48 61 73 68 4e 65 78 74 29 7b 0a 20 20 20  >pHashNext){.   
2640: 20 20 20 69 66 28 20 70 54 65 72 6d 3d 3d 30 20     if( pTerm==0 
2650: 7c 7c 20 30 3d 3d 6d 65 6d 63 6d 70 28 70 49 74  || 0==memcmp(pIt
2660: 65 72 2d 3e 7a 4b 65 79 2c 20 70 54 65 72 6d 2c  er->zKey, pTerm,
2670: 20 6e 54 65 72 6d 29 20 29 7b 0a 20 20 20 20 20   nTerm) ){.     
2680: 20 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79     Fts5HashEntry
2690: 20 2a 70 45 6e 74 72 79 20 3d 20 70 49 74 65 72   *pEntry = pIter
26a0: 3b 0a 20 20 20 20 20 20 20 20 70 45 6e 74 72 79  ;.        pEntry
26b0: 2d 3e 70 53 63 61 6e 4e 65 78 74 20 3d 20 30 3b  ->pScanNext = 0;
26c0: 0a 20 20 20 20 20 20 20 20 66 6f 72 28 69 3d 30  .        for(i=0
26d0: 3b 20 61 70 5b 69 5d 3b 20 69 2b 2b 29 7b 0a 20  ; ap[i]; i++){. 
26e0: 20 20 20 20 20 20 20 20 20 70 45 6e 74 72 79 20           pEntry 
26f0: 3d 20 66 74 73 35 48 61 73 68 45 6e 74 72 79 4d  = fts5HashEntryM
2700: 65 72 67 65 28 70 45 6e 74 72 79 2c 20 61 70 5b  erge(pEntry, ap[
2710: 69 5d 29 3b 0a 20 20 20 20 20 20 20 20 20 20 61  i]);.          a
2720: 70 5b 69 5d 20 3d 20 30 3b 0a 20 20 20 20 20 20  p[i] = 0;.      
2730: 20 20 7d 0a 20 20 20 20 20 20 20 20 61 70 5b 69    }.        ap[i
2740: 5d 20 3d 20 70 45 6e 74 72 79 3b 0a 20 20 20 20  ] = pEntry;.    
2750: 20 20 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 20    }.    }.  }.. 
2760: 20 70 4c 69 73 74 20 3d 20 30 3b 0a 20 20 66 6f   pList = 0;.  fo
2770: 72 28 69 3d 30 3b 20 69 3c 6e 4d 65 72 67 65 53  r(i=0; i<nMergeS
2780: 6c 6f 74 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 70  lot; i++){.    p
2790: 4c 69 73 74 20 3d 20 66 74 73 35 48 61 73 68 45  List = fts5HashE
27a0: 6e 74 72 79 4d 65 72 67 65 28 70 4c 69 73 74 2c  ntryMerge(pList,
27b0: 20 61 70 5b 69 5d 29 3b 0a 20 20 7d 0a 0a 20 20   ap[i]);.  }..  
27c0: 70 48 61 73 68 2d 3e 6e 45 6e 74 72 79 20 3d 20  pHash->nEntry = 
27d0: 30 3b 0a 20 20 73 71 6c 69 74 65 33 5f 66 72 65  0;.  sqlite3_fre
27e0: 65 28 61 70 29 3b 0a 20 20 2a 70 70 53 6f 72 74  e(ap);.  *ppSort
27f0: 65 64 20 3d 20 70 4c 69 73 74 3b 0a 20 20 72 65  ed = pList;.  re
2800: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a  turn SQLITE_OK;.
2810: 7d 0a 0a 69 6e 74 20 73 71 6c 69 74 65 33 46 74  }..int sqlite3Ft
2820: 73 35 48 61 73 68 49 74 65 72 61 74 65 28 0a 20  s5HashIterate(. 
2830: 20 46 74 73 35 48 61 73 68 20 2a 70 48 61 73 68   Fts5Hash *pHash
2840: 2c 0a 20 20 76 6f 69 64 20 2a 70 43 74 78 2c 0a  ,.  void *pCtx,.
2850: 20 20 69 6e 74 20 28 2a 78 54 65 72 6d 29 28 76    int (*xTerm)(v
2860: 6f 69 64 2a 2c 20 63 6f 6e 73 74 20 63 68 61 72  oid*, const char
2870: 2a 2c 20 69 6e 74 29 2c 0a 20 20 69 6e 74 20 28  *, int),.  int (
2880: 2a 78 45 6e 74 72 79 29 28 76 6f 69 64 2a 2c 20  *xEntry)(void*, 
2890: 69 36 34 2c 20 63 6f 6e 73 74 20 75 38 2a 2c 20  i64, const u8*, 
28a0: 69 6e 74 29 2c 0a 20 20 69 6e 74 20 28 2a 78 54  int),.  int (*xT
28b0: 65 72 6d 44 6f 6e 65 29 28 76 6f 69 64 2a 29 0a  ermDone)(void*).
28c0: 29 7b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74  ){.  Fts5HashEnt
28d0: 72 79 20 2a 70 4c 69 73 74 3b 0a 20 20 69 6e 74  ry *pList;.  int
28e0: 20 72 63 3b 0a 0a 20 20 72 63 20 3d 20 66 74 73   rc;..  rc = fts
28f0: 35 48 61 73 68 45 6e 74 72 79 53 6f 72 74 28 70  5HashEntrySort(p
2900: 48 61 73 68 2c 20 30 2c 20 30 2c 20 26 70 4c 69  Hash, 0, 0, &pLi
2910: 73 74 29 3b 0a 20 20 69 66 28 20 72 63 3d 3d 53  st);.  if( rc==S
2920: 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20  QLITE_OK ){.    
2930: 6d 65 6d 73 65 74 28 70 48 61 73 68 2d 3e 61 53  memset(pHash->aS
2940: 6c 6f 74 2c 20 30 2c 20 73 69 7a 65 6f 66 28 46  lot, 0, sizeof(F
2950: 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29 20 2a  ts5HashEntry*) *
2960: 20 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 29 3b 0a   pHash->nSlot);.
2970: 20 20 20 20 77 68 69 6c 65 28 20 70 4c 69 73 74      while( pList
2980: 20 29 7b 0a 20 20 20 20 20 20 46 74 73 35 48 61   ){.      Fts5Ha
2990: 73 68 45 6e 74 72 79 20 2a 70 4e 65 78 74 20 3d  shEntry *pNext =
29a0: 20 70 4c 69 73 74 2d 3e 70 53 63 61 6e 4e 65 78   pList->pScanNex
29b0: 74 3b 0a 20 20 20 20 20 20 69 66 28 20 72 63 3d  t;.      if( rc=
29c0: 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20  =SQLITE_OK ){.  
29d0: 20 20 20 20 20 20 63 6f 6e 73 74 20 69 6e 74 20        const int 
29e0: 6e 53 7a 20 3d 20 70 4c 69 73 74 2d 3e 6e 44 61  nSz = pList->nDa
29f0: 74 61 20 2d 20 70 4c 69 73 74 2d 3e 69 53 7a 50  ta - pList->iSzP
2a00: 6f 73 6c 69 73 74 20 2d 20 34 3b 0a 20 20 20 20  oslist - 4;.    
2a10: 20 20 20 20 63 6f 6e 73 74 20 69 6e 74 20 6e 4b      const int nK
2a20: 65 79 20 3d 20 73 74 72 6c 65 6e 28 70 4c 69 73  ey = strlen(pLis
2a30: 74 2d 3e 7a 4b 65 79 29 3b 0a 20 20 20 20 20 20  t->zKey);.      
2a40: 20 20 69 36 34 20 69 52 6f 77 69 64 20 3d 20 30    i64 iRowid = 0
2a50: 3b 0a 20 20 20 20 20 20 20 20 75 38 20 2a 70 50  ;.        u8 *pP
2a60: 74 72 20 3d 20 28 75 38 2a 29 70 4c 69 73 74 3b  tr = (u8*)pList;
2a70: 0a 20 20 20 20 20 20 20 20 69 6e 74 20 69 4f 66  .        int iOf
2a80: 66 20 3d 20 73 69 7a 65 6f 66 28 46 74 73 35 48  f = sizeof(Fts5H
2a90: 61 73 68 45 6e 74 72 79 29 20 2b 20 6e 4b 65 79  ashEntry) + nKey
2aa0: 20 2b 20 31 3b 0a 0a 20 20 20 20 20 20 20 20 2f   + 1;..        /
2ab0: 2a 20 46 69 6c 6c 20 69 6e 20 74 68 65 20 66 69  * Fill in the fi
2ac0: 6e 61 6c 20 70 6f 73 6c 69 73 74 20 73 69 7a 65  nal poslist size
2ad0: 20 66 69 65 6c 64 20 2a 2f 0a 20 20 20 20 20 20   field */.      
2ae0: 20 20 66 74 73 35 50 75 74 34 42 79 74 65 56 61    fts5Put4ByteVa
2af0: 72 69 6e 74 28 26 70 50 74 72 5b 70 4c 69 73 74  rint(&pPtr[pList
2b00: 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 5d 2c 20 6e  ->iSzPoslist], n
2b10: 53 7a 29 3b 0a 20 20 20 20 20 20 20 20 0a 20 20  Sz);.        .  
2b20: 20 20 20 20 20 20 2f 2a 20 49 73 73 75 65 20 74        /* Issue t
2b30: 68 65 20 6e 65 77 2d 74 65 72 6d 20 63 61 6c 6c  he new-term call
2b40: 62 61 63 6b 20 2a 2f 0a 20 20 20 20 20 20 20 20  back */.        
2b50: 72 63 20 3d 20 78 54 65 72 6d 28 70 43 74 78 2c  rc = xTerm(pCtx,
2b60: 20 70 4c 69 73 74 2d 3e 7a 4b 65 79 2c 20 6e 4b   pList->zKey, nK
2b70: 65 79 29 3b 0a 0a 20 20 20 20 20 20 20 20 2f 2a  ey);..        /*
2b80: 20 49 73 73 75 65 20 74 68 65 20 78 45 6e 74 72   Issue the xEntr
2b90: 79 20 63 61 6c 6c 62 61 63 6b 73 20 2a 2f 0a 20  y callbacks */. 
2ba0: 20 20 20 20 20 20 20 77 68 69 6c 65 28 20 72 63         while( rc
2bb0: 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 26 26 20 69  ==SQLITE_OK && i
2bc0: 4f 66 66 3c 70 4c 69 73 74 2d 3e 6e 44 61 74 61  Off<pList->nData
2bd0: 20 29 7b 0a 20 20 20 20 20 20 20 20 20 20 69 36   ){.          i6
2be0: 34 20 69 44 65 6c 74 61 3b 20 20 20 20 20 20 20  4 iDelta;       
2bf0: 20 20 20 20 20 20 2f 2a 20 52 6f 77 69 64 20 64        /* Rowid d
2c00: 65 6c 74 61 20 76 61 6c 75 65 20 2a 2f 0a 20 20  elta value */.  
2c10: 20 20 20 20 20 20 20 20 69 6e 74 20 6e 50 6f 73          int nPos
2c20: 6c 69 73 74 3b 20 20 20 20 20 20 20 20 20 20 20  list;           
2c30: 2f 2a 20 53 69 7a 65 20 6f 66 20 70 6f 73 69 74  /* Size of posit
2c40: 69 6f 6e 20 6c 69 73 74 20 69 6e 20 62 79 74 65  ion list in byte
2c50: 73 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 69  s */.          i
2c60: 4f 66 66 20 2b 3d 20 67 65 74 56 61 72 69 6e 74  Off += getVarint
2c70: 28 26 70 50 74 72 5b 69 4f 66 66 5d 2c 20 28 75  (&pPtr[iOff], (u
2c80: 36 34 2a 29 26 69 44 65 6c 74 61 29 3b 0a 20 20  64*)&iDelta);.  
2c90: 20 20 20 20 20 20 20 20 69 52 6f 77 69 64 20 2b          iRowid +
2ca0: 3d 20 69 44 65 6c 74 61 3b 0a 20 20 20 20 20 20  = iDelta;.      
2cb0: 20 20 20 20 69 4f 66 66 20 2b 3d 20 66 74 73 35      iOff += fts5
2cc0: 47 65 74 56 61 72 69 6e 74 33 32 28 26 70 50 74  GetVarint32(&pPt
2cd0: 72 5b 69 4f 66 66 5d 2c 20 6e 50 6f 73 6c 69 73  r[iOff], nPoslis
2ce0: 74 29 3b 0a 20 20 20 20 20 20 20 20 20 20 72 63  t);.          rc
2cf0: 20 3d 20 78 45 6e 74 72 79 28 70 43 74 78 2c 20   = xEntry(pCtx, 
2d00: 69 52 6f 77 69 64 2c 20 26 70 50 74 72 5b 69 4f  iRowid, &pPtr[iO
2d10: 66 66 5d 2c 20 6e 50 6f 73 6c 69 73 74 29 3b 0a  ff], nPoslist);.
2d20: 20 20 20 20 20 20 20 20 20 20 69 4f 66 66 20 2b            iOff +
2d30: 3d 20 6e 50 6f 73 6c 69 73 74 3b 0a 20 20 20 20  = nPoslist;.    
2d40: 20 20 20 20 7d 0a 0a 20 20 20 20 20 20 20 20 2f      }..        /
2d50: 2a 20 49 73 73 75 65 20 74 68 65 20 74 65 72 6d  * Issue the term
2d60: 2d 64 6f 6e 65 20 63 61 6c 6c 62 61 63 6b 20 2a  -done callback *
2d70: 2f 0a 20 20 20 20 20 20 20 20 69 66 28 20 72 63  /.        if( rc
2d80: 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 20 72 63  ==SQLITE_OK ) rc
2d90: 20 3d 20 78 54 65 72 6d 44 6f 6e 65 28 70 43 74   = xTermDone(pCt
2da0: 78 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20  x);.      }.    
2db0: 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70    sqlite3_free(p
2dc0: 4c 69 73 74 29 3b 0a 20 20 20 20 20 20 70 4c 69  List);.      pLi
2dd0: 73 74 20 3d 20 70 4e 65 78 74 3b 0a 20 20 20 20  st = pNext;.    
2de0: 7d 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 72  }.  }.  return r
2df0: 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 51 75 65 72  c;.}../*.** Quer
2e00: 79 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65  y the hash table
2e10: 20 66 6f 72 20 61 20 64 6f 63 6c 69 73 74 20 61   for a doclist a
2e20: 73 73 6f 63 69 61 74 65 64 20 77 69 74 68 20 74  ssociated with t
2e30: 65 72 6d 20 70 54 65 72 6d 2f 6e 54 65 72 6d 2e  erm pTerm/nTerm.
2e40: 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 46  .*/.int sqlite3F
2e50: 74 73 35 48 61 73 68 51 75 65 72 79 28 0a 20 20  ts5HashQuery(.  
2e60: 46 74 73 35 48 61 73 68 20 2a 70 48 61 73 68 2c  Fts5Hash *pHash,
2e70: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2e80: 2f 2a 20 48 61 73 68 20 74 61 62 6c 65 20 74 6f  /* Hash table to
2e90: 20 71 75 65 72 79 20 2a 2f 0a 20 20 63 6f 6e 73   query */.  cons
2ea0: 74 20 63 68 61 72 20 2a 70 54 65 72 6d 2c 20 69  t char *pTerm, i
2eb0: 6e 74 20 6e 54 65 72 6d 2c 20 20 20 2f 2a 20 51  nt nTerm,   /* Q
2ec0: 75 65 72 79 20 74 65 72 6d 20 2a 2f 0a 20 20 63  uery term */.  c
2ed0: 6f 6e 73 74 20 63 68 61 72 20 2a 2a 70 70 44 6f  onst char **ppDo
2ee0: 63 6c 69 73 74 2c 20 20 20 20 20 20 20 20 20 2f  clist,         /
2ef0: 2a 20 4f 55 54 3a 20 50 6f 69 6e 74 65 72 20 74  * OUT: Pointer t
2f00: 6f 20 64 6f 63 6c 69 73 74 20 66 6f 72 20 70 54  o doclist for pT
2f10: 65 72 6d 20 2a 2f 0a 20 20 69 6e 74 20 2a 70 6e  erm */.  int *pn
2f20: 44 6f 63 6c 69 73 74 20 20 20 20 20 20 20 20 20  Doclist         
2f30: 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 3a           /* OUT:
2f40: 20 53 69 7a 65 20 6f 66 20 64 6f 63 6c 69 73 74   Size of doclist
2f50: 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a 29 7b 0a   in bytes */.){.
2f60: 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 69    unsigned int i
2f70: 48 61 73 68 20 3d 20 66 74 73 35 48 61 73 68 4b  Hash = fts5HashK
2f80: 65 79 28 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 2c  ey(pHash->nSlot,
2f90: 20 70 54 65 72 6d 2c 20 6e 54 65 72 6d 29 3b 0a   pTerm, nTerm);.
2fa0: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20    Fts5HashEntry 
2fb0: 2a 70 3b 0a 0a 20 20 66 6f 72 28 70 3d 70 48 61  *p;..  for(p=pHa
2fc0: 73 68 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d  sh->aSlot[iHash]
2fd0: 3b 20 70 3b 20 70 3d 70 2d 3e 70 48 61 73 68 4e  ; p; p=p->pHashN
2fe0: 65 78 74 29 7b 0a 20 20 20 20 69 66 28 20 6d 65  ext){.    if( me
2ff0: 6d 63 6d 70 28 70 2d 3e 7a 4b 65 79 2c 20 70 54  mcmp(p->zKey, pT
3000: 65 72 6d 2c 20 6e 54 65 72 6d 29 3d 3d 30 20 26  erm, nTerm)==0 &
3010: 26 20 70 2d 3e 7a 4b 65 79 5b 6e 54 65 72 6d 5d  & p->zKey[nTerm]
3020: 3d 3d 30 20 29 20 62 72 65 61 6b 3b 0a 20 20 7d  ==0 ) break;.  }
3030: 0a 0a 20 20 69 66 28 20 70 20 29 7b 0a 20 20 20  ..  if( p ){.   
3040: 20 75 38 20 2a 70 50 74 72 20 3d 20 28 75 38 2a   u8 *pPtr = (u8*
3050: 29 70 3b 0a 20 20 20 20 66 74 73 35 50 75 74 34  )p;.    fts5Put4
3060: 42 79 74 65 56 61 72 69 6e 74 28 26 70 50 74 72  ByteVarint(&pPtr
3070: 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 5d 2c  [p->iSzPoslist],
3080: 20 70 2d 3e 6e 44 61 74 61 20 2d 20 70 2d 3e 69   p->nData - p->i
3090: 53 7a 50 6f 73 6c 69 73 74 20 2d 20 34 29 3b 0a  SzPoslist - 4);.
30a0: 20 20 20 20 2a 70 70 44 6f 63 6c 69 73 74 20 3d      *ppDoclist =
30b0: 20 26 70 2d 3e 7a 4b 65 79 5b 6e 54 65 72 6d 2b   &p->zKey[nTerm+
30c0: 31 5d 3b 0a 20 20 20 20 2a 70 6e 44 6f 63 6c 69  1];.    *pnDocli
30d0: 73 74 20 3d 20 70 2d 3e 6e 44 61 74 61 20 2d 20  st = p->nData - 
30e0: 28 73 69 7a 65 6f 66 28 2a 70 29 20 2b 20 6e 54  (sizeof(*p) + nT
30f0: 65 72 6d 20 2b 20 31 29 3b 0a 20 20 7d 65 6c 73  erm + 1);.  }els
3100: 65 7b 0a 20 20 20 20 2a 70 70 44 6f 63 6c 69 73  e{.    *ppDoclis
3110: 74 20 3d 20 30 3b 0a 20 20 20 20 2a 70 6e 44 6f  t = 0;.    *pnDo
3120: 63 6c 69 73 74 20 3d 20 30 3b 0a 20 20 7d 0a 0a  clist = 0;.  }..
3130: 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f    return SQLITE_
3140: 4f 4b 3b 0a 7d 0a 0a 76 6f 69 64 20 73 71 6c 69  OK;.}..void sqli
3150: 74 65 33 46 74 73 35 48 61 73 68 53 63 61 6e 49  te3Fts5HashScanI
3160: 6e 69 74 28 0a 20 20 46 74 73 35 48 61 73 68 20  nit(.  Fts5Hash 
3170: 2a 70 2c 20 20 20 20 20 20 20 20 20 20 20 20 20  *p,             
3180: 20 20 20 20 20 20 20 2f 2a 20 48 61 73 68 20 74         /* Hash t
3190: 61 62 6c 65 20 74 6f 20 71 75 65 72 79 20 2a 2f  able to query */
31a0: 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70  .  const char *p
31b0: 54 65 72 6d 2c 20 69 6e 74 20 6e 54 65 72 6d 20  Term, int nTerm 
31c0: 20 20 20 2f 2a 20 51 75 65 72 79 20 70 72 65 66     /* Query pref
31d0: 69 78 20 2a 2f 0a 29 7b 0a 20 20 66 74 73 35 48  ix */.){.  fts5H
31e0: 61 73 68 45 6e 74 72 79 53 6f 72 74 28 70 2c 20  ashEntrySort(p, 
31f0: 70 54 65 72 6d 2c 20 6e 54 65 72 6d 2c 20 26 70  pTerm, nTerm, &p
3200: 2d 3e 70 53 63 61 6e 29 3b 0a 7d 0a 0a 76 6f 69  ->pScan);.}..voi
3210: 64 20 73 71 6c 69 74 65 33 46 74 73 35 48 61 73  d sqlite3Fts5Has
3220: 68 53 63 61 6e 4e 65 78 74 28 46 74 73 35 48 61  hScanNext(Fts5Ha
3230: 73 68 20 2a 70 29 7b 0a 20 20 69 66 28 20 70 2d  sh *p){.  if( p-
3240: 3e 70 53 63 61 6e 20 29 7b 0a 20 20 20 20 70 2d  >pScan ){.    p-
3250: 3e 70 53 63 61 6e 20 3d 20 70 2d 3e 70 53 63 61  >pScan = p->pSca
3260: 6e 2d 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 20 20  n->pScanNext;.  
3270: 7d 0a 7d 0a 0a 69 6e 74 20 73 71 6c 69 74 65 33  }.}..int sqlite3
3280: 46 74 73 35 48 61 73 68 53 63 61 6e 45 6f 66 28  Fts5HashScanEof(
3290: 46 74 73 35 48 61 73 68 20 2a 70 29 7b 0a 20 20  Fts5Hash *p){.  
32a0: 72 65 74 75 72 6e 20 28 70 2d 3e 70 53 63 61 6e  return (p->pScan
32b0: 3d 3d 30 29 3b 0a 7d 0a 0a 76 6f 69 64 20 73 71  ==0);.}..void sq
32c0: 6c 69 74 65 33 46 74 73 35 48 61 73 68 53 63 61  lite3Fts5HashSca
32d0: 6e 45 6e 74 72 79 28 0a 20 20 46 74 73 35 48 61  nEntry(.  Fts5Ha
32e0: 73 68 20 2a 70 48 61 73 68 2c 0a 20 20 63 6f 6e  sh *pHash,.  con
32f0: 73 74 20 63 68 61 72 20 2a 2a 70 7a 54 65 72 6d  st char **pzTerm
3300: 2c 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  ,            /* 
3310: 4f 55 54 3a 20 74 65 72 6d 20 28 6e 75 6c 2d 74  OUT: term (nul-t
3320: 65 72 6d 69 6e 61 74 65 64 29 20 2a 2f 0a 20 20  erminated) */.  
3330: 63 6f 6e 73 74 20 63 68 61 72 20 2a 2a 70 70 44  const char **ppD
3340: 6f 63 6c 69 73 74 2c 20 20 20 20 20 20 20 20 20  oclist,         
3350: 2f 2a 20 4f 55 54 3a 20 70 6f 69 6e 74 65 72 20  /* OUT: pointer 
3360: 74 6f 20 64 6f 63 6c 69 73 74 20 2a 2f 0a 20 20  to doclist */.  
3370: 69 6e 74 20 2a 70 6e 44 6f 63 6c 69 73 74 20 20  int *pnDoclist  
3380: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
3390: 2f 2a 20 4f 55 54 3a 20 73 69 7a 65 20 6f 66 20  /* OUT: size of 
33a0: 64 6f 63 6c 69 73 74 20 69 6e 20 62 79 74 65 73  doclist in bytes
33b0: 20 2a 2f 0a 29 7b 0a 20 20 46 74 73 35 48 61 73   */.){.  Fts5Has
33c0: 68 45 6e 74 72 79 20 2a 70 3b 0a 20 20 69 66 28  hEntry *p;.  if(
33d0: 20 28 70 20 3d 20 70 48 61 73 68 2d 3e 70 53 63   (p = pHash->pSc
33e0: 61 6e 29 20 29 7b 0a 20 20 20 20 75 38 20 2a 70  an) ){.    u8 *p
33f0: 50 74 72 20 3d 20 28 75 38 2a 29 70 3b 0a 20 20  Ptr = (u8*)p;.  
3400: 20 20 69 6e 74 20 6e 54 65 72 6d 20 3d 20 73 74    int nTerm = st
3410: 72 6c 65 6e 28 70 2d 3e 7a 4b 65 79 29 3b 0a 20  rlen(p->zKey);. 
3420: 20 20 20 66 74 73 35 50 75 74 34 42 79 74 65 56     fts5Put4ByteV
3430: 61 72 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e 69  arint(&pPtr[p->i
3440: 53 7a 50 6f 73 6c 69 73 74 5d 2c 20 70 2d 3e 6e  SzPoslist], p->n
3450: 44 61 74 61 20 2d 20 70 2d 3e 69 53 7a 50 6f 73  Data - p->iSzPos
3460: 6c 69 73 74 20 2d 20 34 29 3b 0a 20 20 20 20 2a  list - 4);.    *
3470: 70 7a 54 65 72 6d 20 3d 20 70 2d 3e 7a 4b 65 79  pzTerm = p->zKey
3480: 3b 0a 20 20 20 20 2a 70 70 44 6f 63 6c 69 73 74  ;.    *ppDoclist
3490: 20 3d 20 26 70 2d 3e 7a 4b 65 79 5b 6e 54 65 72   = &p->zKey[nTer
34a0: 6d 2b 31 5d 3b 0a 20 20 20 20 2a 70 6e 44 6f 63  m+1];.    *pnDoc
34b0: 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74 61 20  list = p->nData 
34c0: 2d 20 28 73 69 7a 65 6f 66 28 2a 70 29 20 2b 20  - (sizeof(*p) + 
34d0: 6e 54 65 72 6d 20 2b 20 31 29 3b 0a 20 20 7d 65  nTerm + 1);.  }e
34e0: 6c 73 65 7b 0a 20 20 20 20 2a 70 7a 54 65 72 6d  lse{.    *pzTerm
34f0: 20 3d 20 30 3b 0a 20 20 20 20 2a 70 70 44 6f 63   = 0;.    *ppDoc
3500: 6c 69 73 74 20 3d 20 30 3b 0a 20 20 20 20 2a 70  list = 0;.    *p
3510: 6e 44 6f 63 6c 69 73 74 20 3d 20 30 3b 0a 20 20  nDoclist = 0;.  
3520: 7d 0a 7d 0a 0a                                   }.}..