/ Hex Artifact Content
Login

Artifact 57febfb06e59ae419ee9ba31667635f70d7c4dd0:


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: 73 74 61 74 69 63 20 69 6e 74 20 66 74 73 35 47  static int fts5G
0aa0: 65 74 34 42 79 74 65 56 61 72 69 6e 74 28 75 38  et4ByteVarint(u8
0ab0: 20 2a 61 2c 20 69 6e 74 20 2a 70 6e 56 61 72 69   *a, int *pnVari
0ac0: 6e 74 29 7b 0a 20 20 69 6e 74 20 69 52 65 74 20  nt){.  int iRet 
0ad0: 3d 20 28 28 69 6e 74 29 28 61 5b 30 5d 20 26 20  = ((int)(a[0] & 
0ae0: 30 78 37 46 29 20 3c 3c 20 32 31 29 20 2b 20 28  0x7F) << 21) + (
0af0: 28 69 6e 74 29 28 61 5b 31 5d 20 26 20 30 78 37  (int)(a[1] & 0x7
0b00: 46 29 20 3c 3c 20 31 34 29 0a 20 20 20 20 20 20  F) << 14).      
0b10: 20 2b 20 28 28 69 6e 74 29 28 61 5b 32 5d 20 26   + ((int)(a[2] &
0b20: 20 30 78 37 46 29 20 3c 3c 20 20 37 29 20 2b 20   0x7F) <<  7) + 
0b30: 28 28 69 6e 74 29 28 61 5b 33 5d 29 29 3b 0a 20  ((int)(a[3]));. 
0b40: 20 2a 70 6e 56 61 72 69 6e 74 20 3d 20 28 0a 20   *pnVarint = (. 
0b50: 20 20 20 20 20 28 69 52 65 74 20 26 20 30 78 46       (iRet & 0xF
0b60: 46 46 46 46 46 38 30 29 3d 3d 30 20 3f 20 31 20  FFFFF80)==0 ? 1 
0b70: 3a 20 0a 20 20 20 20 20 20 28 69 52 65 74 20 26  : .      (iRet &
0b80: 20 30 78 46 46 46 46 43 30 30 30 29 3d 3d 30 20   0xFFFFC000)==0 
0b90: 3f 20 32 20 3a 0a 20 20 20 20 20 20 28 69 52 65  ? 2 :.      (iRe
0ba0: 74 20 26 20 30 78 46 46 45 30 30 30 30 30 29 3d  t & 0xFFE00000)=
0bb0: 3d 30 20 3f 20 33 20 3a 20 34 0a 20 20 29 3b 0a  =0 ? 3 : 4.  );.
0bc0: 20 20 72 65 74 75 72 6e 20 69 52 65 74 3b 0a 7d    return iRet;.}
0bd0: 0a 0a 2f 2a 0a 2a 2a 20 41 6c 6c 6f 63 61 74 65  ../*.** Allocate
0be0: 20 61 20 6e 65 77 20 68 61 73 68 20 74 61 62 6c   a new hash tabl
0bf0: 65 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65  e..*/.int sqlite
0c00: 33 46 74 73 35 48 61 73 68 4e 65 77 28 46 74 73  3Fts5HashNew(Fts
0c10: 35 48 61 73 68 20 2a 2a 70 70 4e 65 77 2c 20 69  5Hash **ppNew, i
0c20: 6e 74 20 2a 70 6e 42 79 74 65 29 7b 0a 20 20 69  nt *pnByte){.  i
0c30: 6e 74 20 72 63 20 3d 20 53 51 4c 49 54 45 5f 4f  nt rc = SQLITE_O
0c40: 4b 3b 0a 20 20 46 74 73 35 48 61 73 68 20 2a 70  K;.  Fts5Hash *p
0c50: 4e 65 77 3b 0a 0a 20 20 2a 70 70 4e 65 77 20 3d  New;..  *ppNew =
0c60: 20 70 4e 65 77 20 3d 20 28 46 74 73 35 48 61 73   pNew = (Fts5Has
0c70: 68 2a 29 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f  h*)sqlite3_mallo
0c80: 63 28 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73  c(sizeof(Fts5Has
0c90: 68 29 29 3b 0a 20 20 69 66 28 20 70 4e 65 77 3d  h));.  if( pNew=
0ca0: 3d 30 20 29 7b 0a 20 20 20 20 72 63 20 3d 20 53  =0 ){.    rc = S
0cb0: 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 7d  QLITE_NOMEM;.  }
0cc0: 65 6c 73 65 7b 0a 20 20 20 20 69 6e 74 20 6e 42  else{.    int nB
0cd0: 79 74 65 3b 0a 20 20 20 20 6d 65 6d 73 65 74 28  yte;.    memset(
0ce0: 70 4e 65 77 2c 20 30 2c 20 73 69 7a 65 6f 66 28  pNew, 0, sizeof(
0cf0: 46 74 73 35 48 61 73 68 29 29 3b 0a 20 20 20 20  Fts5Hash));.    
0d00: 70 4e 65 77 2d 3e 70 6e 42 79 74 65 20 3d 20 70  pNew->pnByte = p
0d10: 6e 42 79 74 65 3b 0a 0a 20 20 20 20 70 4e 65 77  nByte;..    pNew
0d20: 2d 3e 6e 53 6c 6f 74 20 3d 20 31 30 32 34 3b 0a  ->nSlot = 1024;.
0d30: 20 20 20 20 6e 42 79 74 65 20 3d 20 73 69 7a 65      nByte = size
0d40: 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79  of(Fts5HashEntry
0d50: 2a 29 20 2a 20 70 4e 65 77 2d 3e 6e 53 6c 6f 74  *) * pNew->nSlot
0d60: 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 61 53 6c 6f  ;.    pNew->aSlo
0d70: 74 20 3d 20 28 46 74 73 35 48 61 73 68 45 6e 74  t = (Fts5HashEnt
0d80: 72 79 2a 2a 29 73 71 6c 69 74 65 33 5f 6d 61 6c  ry**)sqlite3_mal
0d90: 6c 6f 63 28 6e 42 79 74 65 29 3b 0a 20 20 20 20  loc(nByte);.    
0da0: 69 66 28 20 70 4e 65 77 2d 3e 61 53 6c 6f 74 3d  if( pNew->aSlot=
0db0: 3d 30 20 29 7b 0a 20 20 20 20 20 20 73 71 6c 69  =0 ){.      sqli
0dc0: 74 65 33 5f 66 72 65 65 28 70 4e 65 77 29 3b 0a  te3_free(pNew);.
0dd0: 20 20 20 20 20 20 2a 70 70 4e 65 77 20 3d 20 30        *ppNew = 0
0de0: 3b 0a 20 20 20 20 20 20 72 63 20 3d 20 53 51 4c  ;.      rc = SQL
0df0: 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 7d  ITE_NOMEM;.    }
0e00: 65 6c 73 65 7b 0a 20 20 20 20 20 20 6d 65 6d 73  else{.      mems
0e10: 65 74 28 70 4e 65 77 2d 3e 61 53 6c 6f 74 2c 20  et(pNew->aSlot, 
0e20: 30 2c 20 6e 42 79 74 65 29 3b 0a 20 20 20 20 7d  0, nByte);.    }
0e30: 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 72 63  .  }.  return rc
0e40: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 46 72 65 65 20  ;.}../*.** Free 
0e50: 61 20 68 61 73 68 20 74 61 62 6c 65 20 6f 62 6a  a hash table obj
0e60: 65 63 74 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c  ect..*/.void sql
0e70: 69 74 65 33 46 74 73 35 48 61 73 68 46 72 65 65  ite3Fts5HashFree
0e80: 28 46 74 73 35 48 61 73 68 20 2a 70 48 61 73 68  (Fts5Hash *pHash
0e90: 29 7b 0a 20 20 69 66 28 20 70 48 61 73 68 20 29  ){.  if( pHash )
0ea0: 7b 0a 20 20 20 20 73 71 6c 69 74 65 33 46 74 73  {.    sqlite3Fts
0eb0: 35 48 61 73 68 43 6c 65 61 72 28 70 48 61 73 68  5HashClear(pHash
0ec0: 29 3b 0a 20 20 20 20 73 71 6c 69 74 65 33 5f 66  );.    sqlite3_f
0ed0: 72 65 65 28 70 48 61 73 68 2d 3e 61 53 6c 6f 74  ree(pHash->aSlot
0ee0: 29 3b 0a 20 20 20 20 73 71 6c 69 74 65 33 5f 66  );.    sqlite3_f
0ef0: 72 65 65 28 70 48 61 73 68 29 3b 0a 20 20 7d 0a  ree(pHash);.  }.
0f00: 7d 0a 0a 2f 2a 0a 2a 2a 20 45 6d 70 74 79 20 28  }../*.** Empty (
0f10: 62 75 74 20 64 6f 20 6e 6f 74 20 64 65 6c 65 74  but do not delet
0f20: 65 29 20 61 20 68 61 73 68 20 74 61 62 6c 65 2e  e) a hash table.
0f30: 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74 65 33  .*/.void sqlite3
0f40: 46 74 73 35 48 61 73 68 43 6c 65 61 72 28 46 74  Fts5HashClear(Ft
0f50: 73 35 48 61 73 68 20 2a 70 48 61 73 68 29 7b 0a  s5Hash *pHash){.
0f60: 20 20 69 6e 74 20 69 3b 0a 20 20 66 6f 72 28 69    int i;.  for(i
0f70: 3d 30 3b 20 69 3c 70 48 61 73 68 2d 3e 6e 53 6c  =0; i<pHash->nSl
0f80: 6f 74 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 46 74  ot; i++){.    Ft
0f90: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 4e 65  s5HashEntry *pNe
0fa0: 78 74 3b 0a 20 20 20 20 46 74 73 35 48 61 73 68  xt;.    Fts5Hash
0fb0: 45 6e 74 72 79 20 2a 70 53 6c 6f 74 3b 0a 20 20  Entry *pSlot;.  
0fc0: 20 20 66 6f 72 28 70 53 6c 6f 74 3d 70 48 61 73    for(pSlot=pHas
0fd0: 68 2d 3e 61 53 6c 6f 74 5b 69 5d 3b 20 70 53 6c  h->aSlot[i]; pSl
0fe0: 6f 74 3b 20 70 53 6c 6f 74 3d 70 4e 65 78 74 29  ot; pSlot=pNext)
0ff0: 7b 0a 20 20 20 20 20 20 70 4e 65 78 74 20 3d 20  {.      pNext = 
1000: 70 53 6c 6f 74 2d 3e 70 48 61 73 68 4e 65 78 74  pSlot->pHashNext
1010: 3b 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33 5f  ;.      sqlite3_
1020: 66 72 65 65 28 70 53 6c 6f 74 29 3b 0a 20 20 20  free(pSlot);.   
1030: 20 7d 0a 20 20 7d 0a 20 20 6d 65 6d 73 65 74 28   }.  }.  memset(
1040: 70 48 61 73 68 2d 3e 61 53 6c 6f 74 2c 20 30 2c  pHash->aSlot, 0,
1050: 20 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 20 2a 20   pHash->nSlot * 
1060: 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45  sizeof(Fts5HashE
1070: 6e 74 72 79 2a 29 29 3b 0a 20 20 70 48 61 73 68  ntry*));.  pHash
1080: 2d 3e 6e 45 6e 74 72 79 20 3d 20 30 3b 0a 7d 0a  ->nEntry = 0;.}.
1090: 0a 73 74 61 74 69 63 20 75 6e 73 69 67 6e 65 64  .static unsigned
10a0: 20 69 6e 74 20 66 74 73 35 48 61 73 68 4b 65 79   int fts5HashKey
10b0: 28 69 6e 74 20 6e 53 6c 6f 74 2c 20 63 6f 6e 73  (int nSlot, cons
10c0: 74 20 63 68 61 72 20 2a 70 2c 20 69 6e 74 20 6e  t char *p, int n
10d0: 29 7b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 75 6e  ){.  int i;.  un
10e0: 73 69 67 6e 65 64 20 69 6e 74 20 68 20 3d 20 31  signed int h = 1
10f0: 33 3b 0a 20 20 66 6f 72 28 69 3d 6e 2d 31 3b 20  3;.  for(i=n-1; 
1100: 69 3e 3d 30 3b 20 69 2d 2d 29 7b 0a 20 20 20 20  i>=0; i--){.    
1110: 68 20 3d 20 28 68 20 3c 3c 20 33 29 20 5e 20 68  h = (h << 3) ^ h
1120: 20 5e 20 70 5b 69 5d 3b 0a 20 20 7d 0a 20 20 72   ^ p[i];.  }.  r
1130: 65 74 75 72 6e 20 28 68 20 25 20 6e 53 6c 6f 74  eturn (h % nSlot
1140: 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 73 69  );.}../*.** Resi
1150: 7a 65 20 74 68 65 20 68 61 73 68 20 74 61 62 6c  ze the hash tabl
1160: 65 20 62 79 20 64 6f 75 62 6c 69 6e 67 20 74 68  e by doubling th
1170: 65 20 6e 75 6d 62 65 72 20 6f 66 20 73 6c 6f 74  e number of slot
1180: 73 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74  s..*/.static int
1190: 20 66 74 73 35 48 61 73 68 52 65 73 69 7a 65 28   fts5HashResize(
11a0: 46 74 73 35 48 61 73 68 20 2a 70 48 61 73 68 29  Fts5Hash *pHash)
11b0: 7b 0a 20 20 69 6e 74 20 6e 4e 65 77 20 3d 20 70  {.  int nNew = p
11c0: 48 61 73 68 2d 3e 6e 53 6c 6f 74 2a 32 3b 0a 20  Hash->nSlot*2;. 
11d0: 20 69 6e 74 20 69 3b 0a 20 20 46 74 73 35 48 61   int i;.  Fts5Ha
11e0: 73 68 45 6e 74 72 79 20 2a 2a 61 70 4e 65 77 3b  shEntry **apNew;
11f0: 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  .  Fts5HashEntry
1200: 20 2a 2a 61 70 4f 6c 64 20 3d 20 70 48 61 73 68   **apOld = pHash
1210: 2d 3e 61 53 6c 6f 74 3b 0a 0a 20 20 61 70 4e 65  ->aSlot;..  apNe
1220: 77 20 3d 20 28 46 74 73 35 48 61 73 68 45 6e 74  w = (Fts5HashEnt
1230: 72 79 2a 2a 29 73 71 6c 69 74 65 33 5f 6d 61 6c  ry**)sqlite3_mal
1240: 6c 6f 63 28 6e 4e 65 77 2a 73 69 7a 65 6f 66 28  loc(nNew*sizeof(
1250: 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29 29  Fts5HashEntry*))
1260: 3b 0a 20 20 69 66 28 20 21 61 70 4e 65 77 20 29  ;.  if( !apNew )
1270: 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e   return SQLITE_N
1280: 4f 4d 45 4d 3b 0a 20 20 6d 65 6d 73 65 74 28 61  OMEM;.  memset(a
1290: 70 4e 65 77 2c 20 30 2c 20 6e 4e 65 77 2a 73 69  pNew, 0, nNew*si
12a0: 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74  zeof(Fts5HashEnt
12b0: 72 79 2a 29 29 3b 0a 0a 20 20 66 6f 72 28 69 3d  ry*));..  for(i=
12c0: 30 3b 20 69 3c 70 48 61 73 68 2d 3e 6e 53 6c 6f  0; i<pHash->nSlo
12d0: 74 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 77 68 69  t; i++){.    whi
12e0: 6c 65 28 20 61 70 4f 6c 64 5b 69 5d 20 29 7b 0a  le( apOld[i] ){.
12f0: 20 20 20 20 20 20 69 6e 74 20 69 48 61 73 68 3b        int iHash;
1300: 0a 20 20 20 20 20 20 46 74 73 35 48 61 73 68 45  .      Fts5HashE
1310: 6e 74 72 79 20 2a 70 20 3d 20 61 70 4f 6c 64 5b  ntry *p = apOld[
1320: 69 5d 3b 0a 20 20 20 20 20 20 61 70 4f 6c 64 5b  i];.      apOld[
1330: 69 5d 20 3d 20 70 2d 3e 70 48 61 73 68 4e 65 78  i] = p->pHashNex
1340: 74 3b 0a 20 20 20 20 20 20 69 48 61 73 68 20 3d  t;.      iHash =
1350: 20 66 74 73 35 48 61 73 68 4b 65 79 28 6e 4e 65   fts5HashKey(nNe
1360: 77 2c 20 70 2d 3e 7a 4b 65 79 2c 20 73 74 72 6c  w, p->zKey, strl
1370: 65 6e 28 70 2d 3e 7a 4b 65 79 29 29 3b 0a 20 20  en(p->zKey));.  
1380: 20 20 20 20 70 2d 3e 70 48 61 73 68 4e 65 78 74      p->pHashNext
1390: 20 3d 20 61 70 4e 65 77 5b 69 48 61 73 68 5d 3b   = apNew[iHash];
13a0: 0a 20 20 20 20 20 20 61 70 4e 65 77 5b 69 48 61  .      apNew[iHa
13b0: 73 68 5d 20 3d 20 70 3b 0a 20 20 20 20 7d 0a 20  sh] = p;.    }. 
13c0: 20 7d 0a 0a 20 20 73 71 6c 69 74 65 33 5f 66 72   }..  sqlite3_fr
13d0: 65 65 28 61 70 4f 6c 64 29 3b 0a 20 20 70 48 61  ee(apOld);.  pHa
13e0: 73 68 2d 3e 6e 53 6c 6f 74 20 3d 20 6e 4e 65 77  sh->nSlot = nNew
13f0: 3b 0a 20 20 70 48 61 73 68 2d 3e 61 53 6c 6f 74  ;.  pHash->aSlot
1400: 20 3d 20 61 70 4e 65 77 3b 0a 20 20 72 65 74 75   = apNew;.  retu
1410: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a  rn SQLITE_OK;.}.
1420: 0a 69 6e 74 20 73 71 6c 69 74 65 33 46 74 73 35  .int sqlite3Fts5
1430: 48 61 73 68 57 72 69 74 65 28 0a 20 20 46 74 73  HashWrite(.  Fts
1440: 35 48 61 73 68 20 2a 70 48 61 73 68 2c 0a 20 20  5Hash *pHash,.  
1450: 69 36 34 20 69 52 6f 77 69 64 2c 20 20 20 20 20  i64 iRowid,     
1460: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1470: 2f 2a 20 52 6f 77 69 64 20 66 6f 72 20 74 68 69  /* Rowid for thi
1480: 73 20 65 6e 74 72 79 20 2a 2f 0a 20 20 69 6e 74  s entry */.  int
1490: 20 69 43 6f 6c 2c 20 20 20 20 20 20 20 20 20 20   iCol,          
14a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
14b0: 43 6f 6c 75 6d 6e 20 74 6f 6b 65 6e 20 61 70 70  Column token app
14c0: 65 61 72 73 20 69 6e 20 28 2d 76 65 20 2d 3e 20  ears in (-ve -> 
14d0: 64 65 6c 65 74 65 29 20 2a 2f 0a 20 20 69 6e 74  delete) */.  int
14e0: 20 69 50 6f 73 2c 20 20 20 20 20 20 20 20 20 20   iPos,          
14f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
1500: 50 6f 73 69 74 69 6f 6e 20 6f 66 20 74 6f 6b 65  Position of toke
1510: 6e 20 77 69 74 68 69 6e 20 63 6f 6c 75 6d 6e 20  n within column 
1520: 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20  */.  const char 
1530: 2a 70 54 6f 6b 65 6e 2c 20 69 6e 74 20 6e 54 6f  *pToken, int nTo
1540: 6b 65 6e 20 20 2f 2a 20 54 6f 6b 65 6e 20 74 6f  ken  /* Token to
1550: 20 61 64 64 20 6f 72 20 72 65 6d 6f 76 65 20 74   add or remove t
1560: 6f 20 6f 72 20 66 72 6f 6d 20 69 6e 64 65 78 20  o or from index 
1570: 2a 2f 0a 29 7b 0a 20 20 75 6e 73 69 67 6e 65 64  */.){.  unsigned
1580: 20 69 6e 74 20 69 48 61 73 68 20 3d 20 66 74 73   int iHash = fts
1590: 35 48 61 73 68 4b 65 79 28 70 48 61 73 68 2d 3e  5HashKey(pHash->
15a0: 6e 53 6c 6f 74 2c 20 70 54 6f 6b 65 6e 2c 20 6e  nSlot, pToken, n
15b0: 54 6f 6b 65 6e 29 3b 0a 20 20 46 74 73 35 48 61  Token);.  Fts5Ha
15c0: 73 68 45 6e 74 72 79 20 2a 70 3b 0a 20 20 75 38  shEntry *p;.  u8
15d0: 20 2a 70 50 74 72 3b 0a 20 20 69 6e 74 20 6e 49   *pPtr;.  int nI
15e0: 6e 63 72 20 3d 20 30 3b 20 20 20 20 20 20 20 20  ncr = 0;        
15f0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41 6d 6f            /* Amo
1600: 75 6e 74 20 74 6f 20 69 6e 63 72 65 6d 65 6e 74  unt to increment
1610: 20 28 2a 70 48 61 73 68 2d 3e 70 6e 42 79 74 65   (*pHash->pnByte
1620: 29 20 62 79 20 2a 2f 0a 0a 20 20 2f 2a 20 41 74  ) by */..  /* At
1630: 74 65 6d 70 74 20 74 6f 20 6c 6f 63 61 74 65 20  tempt to locate 
1640: 61 6e 20 65 78 69 73 74 69 6e 67 20 68 61 73 68  an existing hash
1650: 20 65 6e 74 72 79 20 2a 2f 0a 20 20 66 6f 72 28   entry */.  for(
1660: 70 3d 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69  p=pHash->aSlot[i
1670: 48 61 73 68 5d 3b 20 70 3b 20 70 3d 70 2d 3e 70  Hash]; p; p=p->p
1680: 48 61 73 68 4e 65 78 74 29 7b 0a 20 20 20 20 69  HashNext){.    i
1690: 66 28 20 6d 65 6d 63 6d 70 28 70 2d 3e 7a 4b 65  f( memcmp(p->zKe
16a0: 79 2c 20 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b 65  y, pToken, nToke
16b0: 6e 29 3d 3d 30 20 26 26 20 70 2d 3e 7a 4b 65 79  n)==0 && p->zKey
16c0: 5b 6e 54 6f 6b 65 6e 5d 3d 3d 30 20 29 20 62 72  [nToken]==0 ) br
16d0: 65 61 6b 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 49  eak;.  }..  /* I
16e0: 66 20 61 6e 20 65 78 69 73 74 69 6e 67 20 68 61  f an existing ha
16f0: 73 68 20 65 6e 74 72 79 20 63 61 6e 6e 6f 74 20  sh entry cannot 
1700: 62 65 20 66 6f 75 6e 64 2c 20 63 72 65 61 74 65  be found, create
1710: 20 61 20 6e 65 77 20 6f 6e 65 2e 20 2a 2f 0a 20   a new one. */. 
1720: 20 69 66 28 20 70 3d 3d 30 20 29 7b 0a 20 20 20   if( p==0 ){.   
1730: 20 69 6e 74 20 6e 42 79 74 65 20 3d 20 73 69 7a   int nByte = siz
1740: 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 72  eof(Fts5HashEntr
1750: 79 29 20 2b 20 6e 54 6f 6b 65 6e 20 2b 20 31 20  y) + nToken + 1 
1760: 2b 20 36 34 3b 0a 20 20 20 20 69 66 28 20 6e 42  + 64;.    if( nB
1770: 79 74 65 3c 31 32 38 20 29 20 6e 42 79 74 65 20  yte<128 ) nByte 
1780: 3d 20 31 32 38 3b 0a 0a 20 20 20 20 69 66 28 20  = 128;..    if( 
1790: 28 70 48 61 73 68 2d 3e 6e 45 6e 74 72 79 2a 32  (pHash->nEntry*2
17a0: 29 3e 3d 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 20  )>=pHash->nSlot 
17b0: 29 7b 0a 20 20 20 20 20 20 69 6e 74 20 72 63 20  ){.      int rc 
17c0: 3d 20 66 74 73 35 48 61 73 68 52 65 73 69 7a 65  = fts5HashResize
17d0: 28 70 48 61 73 68 29 3b 0a 20 20 20 20 20 20 69  (pHash);.      i
17e0: 66 28 20 72 63 21 3d 53 51 4c 49 54 45 5f 4f 4b  f( rc!=SQLITE_OK
17f0: 20 29 20 72 65 74 75 72 6e 20 72 63 3b 0a 20 20   ) return rc;.  
1800: 20 20 20 20 69 48 61 73 68 20 3d 20 66 74 73 35      iHash = fts5
1810: 48 61 73 68 4b 65 79 28 70 48 61 73 68 2d 3e 6e  HashKey(pHash->n
1820: 53 6c 6f 74 2c 20 70 54 6f 6b 65 6e 2c 20 6e 54  Slot, pToken, nT
1830: 6f 6b 65 6e 29 3b 0a 20 20 20 20 7d 0a 0a 20 20  oken);.    }..  
1840: 20 20 70 20 3d 20 28 46 74 73 35 48 61 73 68 45    p = (Fts5HashE
1850: 6e 74 72 79 2a 29 73 71 6c 69 74 65 33 5f 6d 61  ntry*)sqlite3_ma
1860: 6c 6c 6f 63 28 6e 42 79 74 65 29 3b 0a 20 20 20  lloc(nByte);.   
1870: 20 69 66 28 20 21 70 20 29 20 72 65 74 75 72 6e   if( !p ) return
1880: 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20   SQLITE_NOMEM;. 
1890: 20 20 20 6d 65 6d 73 65 74 28 70 2c 20 30 2c 20     memset(p, 0, 
18a0: 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45  sizeof(Fts5HashE
18b0: 6e 74 72 79 29 29 3b 0a 20 20 20 20 70 2d 3e 6e  ntry));.    p->n
18c0: 41 6c 6c 6f 63 20 3d 20 6e 42 79 74 65 3b 0a 20  Alloc = nByte;. 
18d0: 20 20 20 6d 65 6d 63 70 79 28 70 2d 3e 7a 4b 65     memcpy(p->zKe
18e0: 79 2c 20 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b 65  y, pToken, nToke
18f0: 6e 29 3b 0a 20 20 20 20 70 2d 3e 7a 4b 65 79 5b  n);.    p->zKey[
1900: 6e 54 6f 6b 65 6e 5d 20 3d 20 27 5c 30 27 3b 0a  nToken] = '\0';.
1910: 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 3d 20 6e      p->nData = n
1920: 54 6f 6b 65 6e 20 2b 20 31 20 2b 20 73 69 7a 65  Token + 1 + size
1930: 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79  of(Fts5HashEntry
1940: 29 3b 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20  );.    p->nData 
1950: 2b 3d 20 73 71 6c 69 74 65 33 50 75 74 56 61 72  += sqlite3PutVar
1960: 69 6e 74 28 26 28 28 75 38 2a 29 70 29 5b 70 2d  int(&((u8*)p)[p-
1970: 3e 6e 44 61 74 61 5d 2c 20 69 52 6f 77 69 64 29  >nData], iRowid)
1980: 3b 0a 20 20 20 20 70 2d 3e 69 53 7a 50 6f 73 6c  ;.    p->iSzPosl
1990: 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a  ist = p->nData;.
19a0: 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20      p->nData += 
19b0: 34 3b 0a 20 20 20 20 70 2d 3e 69 52 6f 77 69 64  4;.    p->iRowid
19c0: 20 3d 20 69 52 6f 77 69 64 3b 0a 20 20 20 20 70   = iRowid;.    p
19d0: 2d 3e 70 48 61 73 68 4e 65 78 74 20 3d 20 70 48  ->pHashNext = pH
19e0: 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68  ash->aSlot[iHash
19f0: 5d 3b 0a 20 20 20 20 70 48 61 73 68 2d 3e 61 53  ];.    pHash->aS
1a00: 6c 6f 74 5b 69 48 61 73 68 5d 20 3d 20 70 3b 0a  lot[iHash] = p;.
1a10: 20 20 20 20 70 48 61 73 68 2d 3e 6e 45 6e 74 72      pHash->nEntr
1a20: 79 2b 2b 3b 0a 20 20 20 20 6e 49 6e 63 72 20 2b  y++;.    nIncr +
1a30: 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20 20 7d 0a  = p->nData;.  }.
1a40: 0a 20 20 2f 2a 20 43 68 65 63 6b 20 74 68 65 72  .  /* Check ther
1a50: 65 20 69 73 20 65 6e 6f 75 67 68 20 73 70 61 63  e is enough spac
1a60: 65 20 74 6f 20 61 70 70 65 6e 64 20 61 20 6e 65  e to append a ne
1a70: 77 20 65 6e 74 72 79 2e 20 57 6f 72 73 74 20 63  w entry. Worst c
1a80: 61 73 65 20 73 63 65 6e 61 72 69 6f 0a 20 20 2a  ase scenario.  *
1a90: 2a 20 69 73 3a 0a 20 20 2a 2a 0a 20 20 2a 2a 20  * is:.  **.  ** 
1aa0: 20 20 20 20 2b 20 39 20 62 79 74 65 73 20 66 6f      + 9 bytes fo
1ab0: 72 20 61 20 6e 65 77 20 72 6f 77 69 64 2c 0a 20  r a new rowid,. 
1ac0: 20 2a 2a 20 20 20 20 20 2b 20 34 20 62 79 74 65   **     + 4 byte
1ad0: 73 20 72 65 73 65 72 76 65 64 20 66 6f 72 20 74  s reserved for t
1ae0: 68 65 20 22 70 6f 73 6c 69 73 74 20 73 69 7a 65  he "poslist size
1af0: 22 20 76 61 72 69 6e 74 2e 0a 20 20 2a 2a 20 20  " varint..  **  
1b00: 20 20 20 2b 20 31 20 62 79 74 65 20 66 6f 72 20     + 1 byte for 
1b10: 61 20 22 6e 65 77 20 63 6f 6c 75 6d 6e 22 20 62  a "new column" b
1b20: 79 74 65 2c 0a 20 20 2a 2a 20 20 20 20 20 2b 20  yte,.  **     + 
1b30: 33 20 62 79 74 65 73 20 66 6f 72 20 61 20 6e 65  3 bytes for a ne
1b40: 77 20 63 6f 6c 75 6d 6e 20 6e 75 6d 62 65 72 20  w column number 
1b50: 28 31 36 2d 62 69 74 20 6d 61 78 29 20 61 73 20  (16-bit max) as 
1b60: 61 20 76 61 72 69 6e 74 2c 0a 20 20 2a 2a 20 20  a varint,.  **  
1b70: 20 20 20 2b 20 35 20 62 79 74 65 73 20 66 6f 72     + 5 bytes for
1b80: 20 74 68 65 20 6e 65 77 20 70 6f 73 69 74 69 6f   the new positio
1b90: 6e 20 6f 66 66 73 65 74 20 28 33 32 2d 62 69 74  n offset (32-bit
1ba0: 20 6d 61 78 29 2e 0a 20 20 2a 2f 0a 20 20 69 66   max)..  */.  if
1bb0: 28 20 28 70 2d 3e 6e 41 6c 6c 6f 63 20 2d 20 70  ( (p->nAlloc - p
1bc0: 2d 3e 6e 44 61 74 61 29 20 3c 20 28 39 20 2b 20  ->nData) < (9 + 
1bd0: 34 20 2b 20 31 20 2b 20 33 20 2b 20 35 29 20 29  4 + 1 + 3 + 5) )
1be0: 7b 0a 20 20 20 20 69 6e 74 20 6e 4e 65 77 20 3d  {.    int nNew =
1bf0: 20 70 2d 3e 6e 41 6c 6c 6f 63 20 2a 20 32 3b 0a   p->nAlloc * 2;.
1c00: 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74 72      Fts5HashEntr
1c10: 79 20 2a 70 4e 65 77 3b 0a 20 20 20 20 46 74 73  y *pNew;.    Fts
1c20: 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 70 70 3b  5HashEntry **pp;
1c30: 0a 20 20 20 20 70 4e 65 77 20 3d 20 28 46 74 73  .    pNew = (Fts
1c40: 35 48 61 73 68 45 6e 74 72 79 2a 29 73 71 6c 69  5HashEntry*)sqli
1c50: 74 65 33 5f 72 65 61 6c 6c 6f 63 28 70 2c 20 6e  te3_realloc(p, n
1c60: 4e 65 77 29 3b 0a 20 20 20 20 69 66 28 20 70 4e  New);.    if( pN
1c70: 65 77 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 53  ew==0 ) return S
1c80: 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 20  QLITE_NOMEM;.   
1c90: 20 70 4e 65 77 2d 3e 6e 41 6c 6c 6f 63 20 3d 20   pNew->nAlloc = 
1ca0: 6e 4e 65 77 3b 0a 20 20 20 20 66 6f 72 28 70 70  nNew;.    for(pp
1cb0: 3d 26 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69  =&pHash->aSlot[i
1cc0: 48 61 73 68 5d 3b 20 2a 70 70 21 3d 70 3b 20 70  Hash]; *pp!=p; p
1cd0: 70 3d 26 28 2a 70 70 29 2d 3e 70 48 61 73 68 4e  p=&(*pp)->pHashN
1ce0: 65 78 74 29 3b 0a 20 20 20 20 2a 70 70 20 3d 20  ext);.    *pp = 
1cf0: 70 4e 65 77 3b 0a 20 20 20 20 70 20 3d 20 70 4e  pNew;.    p = pN
1d00: 65 77 3b 0a 20 20 7d 0a 20 20 70 50 74 72 20 3d  ew;.  }.  pPtr =
1d10: 20 28 75 38 2a 29 70 3b 0a 20 20 6e 49 6e 63 72   (u8*)p;.  nIncr
1d20: 20 2d 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 0a 20   -= p->nData;.. 
1d30: 20 2f 2a 20 49 66 20 74 68 69 73 20 69 73 20 61   /* If this is a
1d40: 20 6e 65 77 20 72 6f 77 69 64 2c 20 61 70 70 65   new rowid, appe
1d50: 6e 64 20 74 68 65 20 34 2d 62 79 74 65 20 73 69  nd the 4-byte si
1d60: 7a 65 20 66 69 65 6c 64 20 66 6f 72 20 74 68 65  ze field for the
1d70: 20 70 72 65 76 69 6f 75 73 0a 20 20 2a 2a 20 65   previous.  ** e
1d80: 6e 74 72 79 2c 20 61 6e 64 20 74 68 65 20 6e 65  ntry, and the ne
1d90: 77 20 72 6f 77 69 64 20 66 6f 72 20 74 68 69 73  w rowid for this
1da0: 20 65 6e 74 72 79 2e 20 20 2a 2f 0a 20 20 69 66   entry.  */.  if
1db0: 28 20 69 52 6f 77 69 64 21 3d 70 2d 3e 69 52 6f  ( iRowid!=p->iRo
1dc0: 77 69 64 20 29 7b 0a 20 20 20 20 61 73 73 65 72  wid ){.    asser
1dd0: 74 28 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74  t( p->iSzPoslist
1de0: 3e 30 20 29 3b 0a 20 20 20 20 66 74 73 35 50 75  >0 );.    fts5Pu
1df0: 74 34 42 79 74 65 56 61 72 69 6e 74 28 26 70 50  t4ByteVarint(&pP
1e00: 74 72 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74  tr[p->iSzPoslist
1e10: 5d 2c 20 70 2d 3e 6e 44 61 74 61 20 2d 20 70 2d  ], p->nData - p-
1e20: 3e 69 53 7a 50 6f 73 6c 69 73 74 20 2d 20 34 29  >iSzPoslist - 4)
1e30: 3b 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b  ;.    p->nData +
1e40: 3d 20 73 71 6c 69 74 65 33 50 75 74 56 61 72 69  = sqlite3PutVari
1e50: 6e 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61 74  nt(&pPtr[p->nDat
1e60: 61 5d 2c 20 69 52 6f 77 69 64 20 2d 20 70 2d 3e  a], iRowid - p->
1e70: 69 52 6f 77 69 64 29 3b 0a 20 20 20 20 70 2d 3e  iRowid);.    p->
1e80: 69 53 7a 50 6f 73 6c 69 73 74 20 3d 20 70 2d 3e  iSzPoslist = p->
1e90: 6e 44 61 74 61 3b 0a 20 20 20 20 70 2d 3e 6e 44  nData;.    p->nD
1ea0: 61 74 61 20 2b 3d 20 34 3b 0a 20 20 20 20 70 2d  ata += 4;.    p-
1eb0: 3e 69 43 6f 6c 20 3d 20 30 3b 0a 20 20 20 20 70  >iCol = 0;.    p
1ec0: 2d 3e 69 50 6f 73 20 3d 20 30 3b 0a 20 20 20 20  ->iPos = 0;.    
1ed0: 70 2d 3e 69 52 6f 77 69 64 20 3d 20 69 52 6f 77  p->iRowid = iRow
1ee0: 69 64 3b 0a 20 20 7d 0a 0a 20 20 69 66 28 20 69  id;.  }..  if( i
1ef0: 43 6f 6c 3e 3d 30 20 29 7b 0a 20 20 20 20 2f 2a  Col>=0 ){.    /*
1f00: 20 41 70 70 65 6e 64 20 61 20 6e 65 77 20 63 6f   Append a new co
1f10: 6c 75 6d 6e 20 76 61 6c 75 65 2c 20 69 66 20 6e  lumn value, if n
1f20: 65 63 65 73 73 61 72 79 20 2a 2f 0a 20 20 20 20  ecessary */.    
1f30: 61 73 73 65 72 74 28 20 69 43 6f 6c 3e 3d 70 2d  assert( iCol>=p-
1f40: 3e 69 43 6f 6c 20 29 3b 0a 20 20 20 20 69 66 28  >iCol );.    if(
1f50: 20 69 43 6f 6c 21 3d 70 2d 3e 69 43 6f 6c 20 29   iCol!=p->iCol )
1f60: 7b 0a 20 20 20 20 20 20 70 50 74 72 5b 70 2d 3e  {.      pPtr[p->
1f70: 6e 44 61 74 61 2b 2b 5d 20 3d 20 30 78 30 31 3b  nData++] = 0x01;
1f80: 0a 20 20 20 20 20 20 70 2d 3e 6e 44 61 74 61 20  .      p->nData 
1f90: 2b 3d 20 73 71 6c 69 74 65 33 50 75 74 56 61 72  += sqlite3PutVar
1fa0: 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61  int(&pPtr[p->nDa
1fb0: 74 61 5d 2c 20 69 43 6f 6c 29 3b 0a 20 20 20 20  ta], iCol);.    
1fc0: 20 20 70 2d 3e 69 43 6f 6c 20 3d 20 69 43 6f 6c    p->iCol = iCol
1fd0: 3b 0a 20 20 20 20 20 20 70 2d 3e 69 50 6f 73 20  ;.      p->iPos 
1fe0: 3d 20 30 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20  = 0;.    }..    
1ff0: 2f 2a 20 41 70 70 65 6e 64 20 74 68 65 20 6e 65  /* Append the ne
2000: 77 20 70 6f 73 69 74 69 6f 6e 20 6f 66 66 73 65  w position offse
2010: 74 20 2a 2f 0a 20 20 20 20 70 2d 3e 6e 44 61 74  t */.    p->nDat
2020: 61 20 2b 3d 20 73 71 6c 69 74 65 33 50 75 74 56  a += sqlite3PutV
2030: 61 72 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e 6e  arint(&pPtr[p->n
2040: 44 61 74 61 5d 2c 20 69 50 6f 73 20 2d 20 70 2d  Data], iPos - p-
2050: 3e 69 50 6f 73 20 2b 20 32 29 3b 0a 20 20 20 20  >iPos + 2);.    
2060: 70 2d 3e 69 50 6f 73 20 3d 20 69 50 6f 73 3b 0a  p->iPos = iPos;.
2070: 20 20 7d 0a 20 20 6e 49 6e 63 72 20 2b 3d 20 70    }.  nIncr += p
2080: 2d 3e 6e 44 61 74 61 3b 0a 0a 20 20 2a 70 48 61  ->nData;..  *pHa
2090: 73 68 2d 3e 70 6e 42 79 74 65 20 2b 3d 20 6e 49  sh->pnByte += nI
20a0: 6e 63 72 3b 0a 20 20 72 65 74 75 72 6e 20 53 51  ncr;.  return SQ
20b0: 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 0a 2f 2a 0a  LITE_OK;.}.../*.
20c0: 2a 2a 20 41 72 67 75 6d 65 6e 74 73 20 70 4c 65  ** Arguments pLe
20d0: 66 74 20 61 6e 64 20 70 52 69 67 68 74 20 70 6f  ft and pRight po
20e0: 69 6e 74 20 74 6f 20 6c 69 6e 6b 65 64 2d 6c 69  int to linked-li
20f0: 73 74 73 20 6f 66 20 68 61 73 68 2d 65 6e 74 72  sts of hash-entr
2100: 79 20 6f 62 6a 65 63 74 73 2c 0a 2a 2a 20 65 61  y objects,.** ea
2110: 63 68 20 73 6f 72 74 65 64 20 69 6e 20 6b 65 79  ch sorted in key
2120: 20 6f 72 64 65 72 2e 20 54 68 69 73 20 66 75 6e   order. This fun
2130: 63 74 69 6f 6e 20 6d 65 72 67 65 73 20 74 68 65  ction merges the
2140: 20 74 77 6f 20 6c 69 73 74 73 20 69 6e 74 6f 20   two lists into 
2150: 61 0a 2a 2a 20 73 69 6e 67 6c 65 20 6c 69 73 74  a.** single list
2160: 20 61 6e 64 20 72 65 74 75 72 6e 73 20 61 20 70   and returns a p
2170: 6f 69 6e 74 65 72 20 74 6f 20 69 74 73 20 66 69  ointer to its fi
2180: 72 73 74 20 65 6c 65 6d 65 6e 74 2e 0a 2a 2f 0a  rst element..*/.
2190: 73 74 61 74 69 63 20 46 74 73 35 48 61 73 68 45  static Fts5HashE
21a0: 6e 74 72 79 20 2a 66 74 73 35 48 61 73 68 45 6e  ntry *fts5HashEn
21b0: 74 72 79 4d 65 72 67 65 28 0a 20 20 46 74 73 35  tryMerge(.  Fts5
21c0: 48 61 73 68 45 6e 74 72 79 20 2a 70 4c 65 66 74  HashEntry *pLeft
21d0: 2c 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72  ,.  Fts5HashEntr
21e0: 79 20 2a 70 52 69 67 68 74 0a 29 7b 0a 20 20 46  y *pRight.){.  F
21f0: 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 31  ts5HashEntry *p1
2200: 20 3d 20 70 4c 65 66 74 3b 0a 20 20 46 74 73 35   = pLeft;.  Fts5
2210: 48 61 73 68 45 6e 74 72 79 20 2a 70 32 20 3d 20  HashEntry *p2 = 
2220: 70 52 69 67 68 74 3b 0a 20 20 46 74 73 35 48 61  pRight;.  Fts5Ha
2230: 73 68 45 6e 74 72 79 20 2a 70 52 65 74 20 3d 20  shEntry *pRet = 
2240: 30 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74  0;.  Fts5HashEnt
2250: 72 79 20 2a 2a 70 70 4f 75 74 20 3d 20 26 70 52  ry **ppOut = &pR
2260: 65 74 3b 0a 0a 20 20 77 68 69 6c 65 28 20 70 31  et;..  while( p1
2270: 20 7c 7c 20 70 32 20 29 7b 0a 20 20 20 20 69 66   || p2 ){.    if
2280: 28 20 70 31 3d 3d 30 20 29 7b 0a 20 20 20 20 20  ( p1==0 ){.     
2290: 20 2a 70 70 4f 75 74 20 3d 20 70 32 3b 0a 20 20   *ppOut = p2;.  
22a0: 20 20 20 20 70 32 20 3d 20 30 3b 0a 20 20 20 20      p2 = 0;.    
22b0: 7d 65 6c 73 65 20 69 66 28 20 70 32 3d 3d 30 20  }else if( p2==0 
22c0: 29 7b 0a 20 20 20 20 20 20 2a 70 70 4f 75 74 20  ){.      *ppOut 
22d0: 3d 20 70 31 3b 0a 20 20 20 20 20 20 70 31 20 3d  = p1;.      p1 =
22e0: 20 30 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20   0;.    }else{. 
22f0: 20 20 20 20 20 69 6e 74 20 69 20 3d 20 30 3b 0a       int i = 0;.
2300: 20 20 20 20 20 20 77 68 69 6c 65 28 20 70 31 2d        while( p1-
2310: 3e 7a 4b 65 79 5b 69 5d 3d 3d 70 32 2d 3e 7a 4b  >zKey[i]==p2->zK
2320: 65 79 5b 69 5d 20 29 20 69 2b 2b 3b 0a 0a 20 20  ey[i] ) i++;..  
2330: 20 20 20 20 69 66 28 20 28 28 75 38 29 70 31 2d      if( ((u8)p1-
2340: 3e 7a 4b 65 79 5b 69 5d 29 3e 28 28 75 38 29 70  >zKey[i])>((u8)p
2350: 32 2d 3e 7a 4b 65 79 5b 69 5d 29 20 29 7b 0a 20  2->zKey[i]) ){. 
2360: 20 20 20 20 20 20 20 2f 2a 20 70 32 20 69 73 20         /* p2 is 
2370: 73 6d 61 6c 6c 65 72 20 2a 2f 0a 20 20 20 20 20  smaller */.     
2380: 20 20 20 2a 70 70 4f 75 74 20 3d 20 70 32 3b 0a     *ppOut = p2;.
2390: 20 20 20 20 20 20 20 20 70 70 4f 75 74 20 3d 20          ppOut = 
23a0: 26 70 32 2d 3e 70 53 63 61 6e 4e 65 78 74 3b 0a  &p2->pScanNext;.
23b0: 20 20 20 20 20 20 20 20 70 32 20 3d 20 70 32 2d          p2 = p2-
23c0: 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 20 20 20 20  >pScanNext;.    
23d0: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 20    }else{.       
23e0: 20 2f 2a 20 70 31 20 69 73 20 73 6d 61 6c 6c 65   /* p1 is smalle
23f0: 72 20 2a 2f 0a 20 20 20 20 20 20 20 20 2a 70 70  r */.        *pp
2400: 4f 75 74 20 3d 20 70 31 3b 0a 20 20 20 20 20 20  Out = p1;.      
2410: 20 20 70 70 4f 75 74 20 3d 20 26 70 31 2d 3e 70    ppOut = &p1->p
2420: 53 63 61 6e 4e 65 78 74 3b 0a 20 20 20 20 20 20  ScanNext;.      
2430: 20 20 70 31 20 3d 20 70 31 2d 3e 70 53 63 61 6e    p1 = p1->pScan
2440: 4e 65 78 74 3b 0a 20 20 20 20 20 20 7d 0a 20 20  Next;.      }.  
2450: 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 30 3b 0a      *ppOut = 0;.
2460: 20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 72 65 74      }.  }..  ret
2470: 75 72 6e 20 70 52 65 74 3b 0a 7d 0a 0a 2f 2a 0a  urn pRet;.}../*.
2480: 2a 2a 20 45 78 74 72 61 63 74 20 61 6c 6c 20 74  ** Extract all t
2490: 6f 6b 65 6e 73 20 66 72 6f 6d 20 68 61 73 68 20  okens from hash 
24a0: 74 61 62 6c 65 20 69 48 61 73 68 20 61 6e 64 20  table iHash and 
24b0: 6c 69 6e 6b 20 74 68 65 6d 20 69 6e 74 6f 20 61  link them into a
24c0: 20 6c 69 73 74 0a 2a 2a 20 69 6e 20 73 6f 72 74   list.** in sort
24d0: 65 64 20 6f 72 64 65 72 2e 20 54 68 65 20 68 61  ed order. The ha
24e0: 73 68 20 74 61 62 6c 65 20 69 73 20 63 6c 65 61  sh table is clea
24f0: 72 65 64 20 62 65 66 6f 72 65 20 72 65 74 75 72  red before retur
2500: 6e 69 6e 67 2e 20 49 74 20 69 73 0a 2a 2a 20 74  ning. It is.** t
2510: 68 65 20 72 65 73 70 6f 6e 73 69 62 69 6c 69 74  he responsibilit
2520: 79 20 6f 66 20 74 68 65 20 63 61 6c 6c 65 72 20  y of the caller 
2530: 74 6f 20 66 72 65 65 20 74 68 65 20 65 6c 65 6d  to free the elem
2540: 65 6e 74 73 20 6f 66 20 74 68 65 20 72 65 74 75  ents of the retu
2550: 72 6e 65 64 0a 2a 2a 20 6c 69 73 74 2e 0a 2a 2f  rned.** list..*/
2560: 0a 73 74 61 74 69 63 20 69 6e 74 20 66 74 73 35  .static int fts5
2570: 48 61 73 68 45 6e 74 72 79 53 6f 72 74 28 0a 20  HashEntrySort(. 
2580: 20 46 74 73 35 48 61 73 68 20 2a 70 48 61 73 68   Fts5Hash *pHash
2590: 2c 20 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20  , .  const char 
25a0: 2a 70 54 65 72 6d 2c 20 69 6e 74 20 6e 54 65 72  *pTerm, int nTer
25b0: 6d 2c 20 20 20 2f 2a 20 51 75 65 72 79 20 70 72  m,   /* Query pr
25c0: 65 66 69 78 2c 20 69 66 20 61 6e 79 20 2a 2f 0a  efix, if any */.
25d0: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20    Fts5HashEntry 
25e0: 2a 2a 70 70 53 6f 72 74 65 64 0a 29 7b 0a 20 20  **ppSorted.){.  
25f0: 63 6f 6e 73 74 20 69 6e 74 20 6e 4d 65 72 67 65  const int nMerge
2600: 53 6c 6f 74 20 3d 20 33 32 3b 0a 20 20 46 74 73  Slot = 32;.  Fts
2610: 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 61 70 3b  5HashEntry **ap;
2620: 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  .  Fts5HashEntry
2630: 20 2a 70 4c 69 73 74 3b 0a 20 20 69 6e 74 20 69   *pList;.  int i
2640: 53 6c 6f 74 3b 0a 20 20 69 6e 74 20 69 3b 0a 0a  Slot;.  int i;..
2650: 20 20 2a 70 70 53 6f 72 74 65 64 20 3d 20 30 3b    *ppSorted = 0;
2660: 0a 20 20 61 70 20 3d 20 73 71 6c 69 74 65 33 5f  .  ap = sqlite3_
2670: 6d 61 6c 6c 6f 63 28 73 69 7a 65 6f 66 28 46 74  malloc(sizeof(Ft
2680: 73 35 48 61 73 68 45 6e 74 72 79 2a 29 20 2a 20  s5HashEntry*) * 
2690: 6e 4d 65 72 67 65 53 6c 6f 74 29 3b 0a 20 20 69  nMergeSlot);.  i
26a0: 66 28 20 21 61 70 20 29 20 72 65 74 75 72 6e 20  f( !ap ) return 
26b0: 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20  SQLITE_NOMEM;.  
26c0: 6d 65 6d 73 65 74 28 61 70 2c 20 30 2c 20 73 69  memset(ap, 0, si
26d0: 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74  zeof(Fts5HashEnt
26e0: 72 79 2a 29 20 2a 20 6e 4d 65 72 67 65 53 6c 6f  ry*) * nMergeSlo
26f0: 74 29 3b 0a 0a 20 20 66 6f 72 28 69 53 6c 6f 74  t);..  for(iSlot
2700: 3d 30 3b 20 69 53 6c 6f 74 3c 70 48 61 73 68 2d  =0; iSlot<pHash-
2710: 3e 6e 53 6c 6f 74 3b 20 69 53 6c 6f 74 2b 2b 29  >nSlot; iSlot++)
2720: 7b 0a 20 20 20 20 46 74 73 35 48 61 73 68 45 6e  {.    Fts5HashEn
2730: 74 72 79 20 2a 70 49 74 65 72 3b 0a 20 20 20 20  try *pIter;.    
2740: 66 6f 72 28 70 49 74 65 72 3d 70 48 61 73 68 2d  for(pIter=pHash-
2750: 3e 61 53 6c 6f 74 5b 69 53 6c 6f 74 5d 3b 20 70  >aSlot[iSlot]; p
2760: 49 74 65 72 3b 20 70 49 74 65 72 3d 70 49 74 65  Iter; pIter=pIte
2770: 72 2d 3e 70 48 61 73 68 4e 65 78 74 29 7b 0a 20  r->pHashNext){. 
2780: 20 20 20 20 20 69 66 28 20 70 54 65 72 6d 3d 3d       if( pTerm==
2790: 30 20 7c 7c 20 30 3d 3d 6d 65 6d 63 6d 70 28 70  0 || 0==memcmp(p
27a0: 49 74 65 72 2d 3e 7a 4b 65 79 2c 20 70 54 65 72  Iter->zKey, pTer
27b0: 6d 2c 20 6e 54 65 72 6d 29 20 29 7b 0a 20 20 20  m, nTerm) ){.   
27c0: 20 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74       Fts5HashEnt
27d0: 72 79 20 2a 70 45 6e 74 72 79 20 3d 20 70 49 74  ry *pEntry = pIt
27e0: 65 72 3b 0a 20 20 20 20 20 20 20 20 70 45 6e 74  er;.        pEnt
27f0: 72 79 2d 3e 70 53 63 61 6e 4e 65 78 74 20 3d 20  ry->pScanNext = 
2800: 30 3b 0a 20 20 20 20 20 20 20 20 66 6f 72 28 69  0;.        for(i
2810: 3d 30 3b 20 61 70 5b 69 5d 3b 20 69 2b 2b 29 7b  =0; ap[i]; i++){
2820: 0a 20 20 20 20 20 20 20 20 20 20 70 45 6e 74 72  .          pEntr
2830: 79 20 3d 20 66 74 73 35 48 61 73 68 45 6e 74 72  y = fts5HashEntr
2840: 79 4d 65 72 67 65 28 70 45 6e 74 72 79 2c 20 61  yMerge(pEntry, a
2850: 70 5b 69 5d 29 3b 0a 20 20 20 20 20 20 20 20 20  p[i]);.         
2860: 20 61 70 5b 69 5d 20 3d 20 30 3b 0a 20 20 20 20   ap[i] = 0;.    
2870: 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 61 70      }.        ap
2880: 5b 69 5d 20 3d 20 70 45 6e 74 72 79 3b 0a 20 20  [i] = pEntry;.  
2890: 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a      }.    }.  }.
28a0: 0a 20 20 70 4c 69 73 74 20 3d 20 30 3b 0a 20 20  .  pList = 0;.  
28b0: 66 6f 72 28 69 3d 30 3b 20 69 3c 6e 4d 65 72 67  for(i=0; i<nMerg
28c0: 65 53 6c 6f 74 3b 20 69 2b 2b 29 7b 0a 20 20 20  eSlot; i++){.   
28d0: 20 70 4c 69 73 74 20 3d 20 66 74 73 35 48 61 73   pList = fts5Has
28e0: 68 45 6e 74 72 79 4d 65 72 67 65 28 70 4c 69 73  hEntryMerge(pLis
28f0: 74 2c 20 61 70 5b 69 5d 29 3b 0a 20 20 7d 0a 0a  t, ap[i]);.  }..
2900: 20 20 70 48 61 73 68 2d 3e 6e 45 6e 74 72 79 20    pHash->nEntry 
2910: 3d 20 30 3b 0a 20 20 73 71 6c 69 74 65 33 5f 66  = 0;.  sqlite3_f
2920: 72 65 65 28 61 70 29 3b 0a 20 20 2a 70 70 53 6f  ree(ap);.  *ppSo
2930: 72 74 65 64 20 3d 20 70 4c 69 73 74 3b 0a 20 20  rted = pList;.  
2940: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b  return SQLITE_OK
2950: 3b 0a 7d 0a 0a 69 6e 74 20 73 71 6c 69 74 65 33  ;.}..int sqlite3
2960: 46 74 73 35 48 61 73 68 49 74 65 72 61 74 65 28  Fts5HashIterate(
2970: 0a 20 20 46 74 73 35 48 61 73 68 20 2a 70 48 61  .  Fts5Hash *pHa
2980: 73 68 2c 0a 20 20 76 6f 69 64 20 2a 70 43 74 78  sh,.  void *pCtx
2990: 2c 0a 20 20 69 6e 74 20 28 2a 78 54 65 72 6d 29  ,.  int (*xTerm)
29a0: 28 76 6f 69 64 2a 2c 20 63 6f 6e 73 74 20 63 68  (void*, const ch
29b0: 61 72 2a 2c 20 69 6e 74 29 2c 0a 20 20 69 6e 74  ar*, int),.  int
29c0: 20 28 2a 78 45 6e 74 72 79 29 28 76 6f 69 64 2a   (*xEntry)(void*
29d0: 2c 20 69 36 34 2c 20 63 6f 6e 73 74 20 75 38 2a  , i64, const u8*
29e0: 2c 20 69 6e 74 29 2c 0a 20 20 69 6e 74 20 28 2a  , int),.  int (*
29f0: 78 54 65 72 6d 44 6f 6e 65 29 28 76 6f 69 64 2a  xTermDone)(void*
2a00: 29 0a 29 7b 0a 20 20 46 74 73 35 48 61 73 68 45  ).){.  Fts5HashE
2a10: 6e 74 72 79 20 2a 70 4c 69 73 74 3b 0a 20 20 69  ntry *pList;.  i
2a20: 6e 74 20 72 63 3b 0a 0a 20 20 72 63 20 3d 20 66  nt rc;..  rc = f
2a30: 74 73 35 48 61 73 68 45 6e 74 72 79 53 6f 72 74  ts5HashEntrySort
2a40: 28 70 48 61 73 68 2c 20 30 2c 20 30 2c 20 26 70  (pHash, 0, 0, &p
2a50: 4c 69 73 74 29 3b 0a 20 20 69 66 28 20 72 63 3d  List);.  if( rc=
2a60: 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20  =SQLITE_OK ){.  
2a70: 20 20 6d 65 6d 73 65 74 28 70 48 61 73 68 2d 3e    memset(pHash->
2a80: 61 53 6c 6f 74 2c 20 30 2c 20 73 69 7a 65 6f 66  aSlot, 0, sizeof
2a90: 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29  (Fts5HashEntry*)
2aa0: 20 2a 20 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 29   * pHash->nSlot)
2ab0: 3b 0a 20 20 20 20 77 68 69 6c 65 28 20 70 4c 69  ;.    while( pLi
2ac0: 73 74 20 29 7b 0a 20 20 20 20 20 20 46 74 73 35  st ){.      Fts5
2ad0: 48 61 73 68 45 6e 74 72 79 20 2a 70 4e 65 78 74  HashEntry *pNext
2ae0: 20 3d 20 70 4c 69 73 74 2d 3e 70 53 63 61 6e 4e   = pList->pScanN
2af0: 65 78 74 3b 0a 20 20 20 20 20 20 69 66 28 20 72  ext;.      if( r
2b00: 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b 0a  c==SQLITE_OK ){.
2b10: 20 20 20 20 20 20 20 20 63 6f 6e 73 74 20 69 6e          const in
2b20: 74 20 6e 53 7a 20 3d 20 70 4c 69 73 74 2d 3e 6e  t nSz = pList->n
2b30: 44 61 74 61 20 2d 20 70 4c 69 73 74 2d 3e 69 53  Data - pList->iS
2b40: 7a 50 6f 73 6c 69 73 74 20 2d 20 34 3b 0a 20 20  zPoslist - 4;.  
2b50: 20 20 20 20 20 20 63 6f 6e 73 74 20 69 6e 74 20        const int 
2b60: 6e 4b 65 79 20 3d 20 73 74 72 6c 65 6e 28 70 4c  nKey = strlen(pL
2b70: 69 73 74 2d 3e 7a 4b 65 79 29 3b 0a 20 20 20 20  ist->zKey);.    
2b80: 20 20 20 20 69 36 34 20 69 52 6f 77 69 64 20 3d      i64 iRowid =
2b90: 20 30 3b 0a 20 20 20 20 20 20 20 20 75 38 20 2a   0;.        u8 *
2ba0: 70 50 74 72 20 3d 20 28 75 38 2a 29 70 4c 69 73  pPtr = (u8*)pLis
2bb0: 74 3b 0a 20 20 20 20 20 20 20 20 69 6e 74 20 69  t;.        int i
2bc0: 4f 66 66 20 3d 20 73 69 7a 65 6f 66 28 46 74 73  Off = sizeof(Fts
2bd0: 35 48 61 73 68 45 6e 74 72 79 29 20 2b 20 6e 4b  5HashEntry) + nK
2be0: 65 79 20 2b 20 31 3b 0a 0a 20 20 20 20 20 20 20  ey + 1;..       
2bf0: 20 2f 2a 20 46 69 6c 6c 20 69 6e 20 74 68 65 20   /* Fill in the 
2c00: 66 69 6e 61 6c 20 70 6f 73 6c 69 73 74 20 73 69  final poslist si
2c10: 7a 65 20 66 69 65 6c 64 20 2a 2f 0a 20 20 20 20  ze field */.    
2c20: 20 20 20 20 66 74 73 35 50 75 74 34 42 79 74 65      fts5Put4Byte
2c30: 56 61 72 69 6e 74 28 26 70 50 74 72 5b 70 4c 69  Varint(&pPtr[pLi
2c40: 73 74 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 5d 2c  st->iSzPoslist],
2c50: 20 6e 53 7a 29 3b 0a 20 20 20 20 20 20 20 20 0a   nSz);.        .
2c60: 20 20 20 20 20 20 20 20 2f 2a 20 49 73 73 75 65          /* Issue
2c70: 20 74 68 65 20 6e 65 77 2d 74 65 72 6d 20 63 61   the new-term ca
2c80: 6c 6c 62 61 63 6b 20 2a 2f 0a 20 20 20 20 20 20  llback */.      
2c90: 20 20 72 63 20 3d 20 78 54 65 72 6d 28 70 43 74    rc = xTerm(pCt
2ca0: 78 2c 20 70 4c 69 73 74 2d 3e 7a 4b 65 79 2c 20  x, pList->zKey, 
2cb0: 6e 4b 65 79 29 3b 0a 0a 20 20 20 20 20 20 20 20  nKey);..        
2cc0: 2f 2a 20 49 73 73 75 65 20 74 68 65 20 78 45 6e  /* Issue the xEn
2cd0: 74 72 79 20 63 61 6c 6c 62 61 63 6b 73 20 2a 2f  try callbacks */
2ce0: 0a 20 20 20 20 20 20 20 20 77 68 69 6c 65 28 20  .        while( 
2cf0: 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 26 26  rc==SQLITE_OK &&
2d00: 20 69 4f 66 66 3c 70 4c 69 73 74 2d 3e 6e 44 61   iOff<pList->nDa
2d10: 74 61 20 29 7b 0a 20 20 20 20 20 20 20 20 20 20  ta ){.          
2d20: 69 36 34 20 69 44 65 6c 74 61 3b 20 20 20 20 20  i64 iDelta;     
2d30: 20 20 20 20 20 20 20 20 2f 2a 20 52 6f 77 69 64          /* Rowid
2d40: 20 64 65 6c 74 61 20 76 61 6c 75 65 20 2a 2f 0a   delta value */.
2d50: 20 20 20 20 20 20 20 20 20 20 69 6e 74 20 6e 50            int nP
2d60: 6f 73 6c 69 73 74 3b 20 20 20 20 20 20 20 20 20  oslist;         
2d70: 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 70 6f 73    /* Size of pos
2d80: 69 74 69 6f 6e 20 6c 69 73 74 20 69 6e 20 62 79  ition list in by
2d90: 74 65 73 20 2a 2f 0a 20 20 20 20 20 20 20 20 20  tes */.         
2da0: 20 69 6e 74 20 6e 56 61 72 69 6e 74 3b 0a 20 20   int nVarint;.  
2db0: 20 20 20 20 20 20 20 20 69 4f 66 66 20 2b 3d 20          iOff += 
2dc0: 67 65 74 56 61 72 69 6e 74 28 26 70 50 74 72 5b  getVarint(&pPtr[
2dd0: 69 4f 66 66 5d 2c 20 28 75 36 34 2a 29 26 69 44  iOff], (u64*)&iD
2de0: 65 6c 74 61 29 3b 0a 20 20 20 20 20 20 20 20 20  elta);.         
2df0: 20 69 52 6f 77 69 64 20 2b 3d 20 69 44 65 6c 74   iRowid += iDelt
2e00: 61 3b 0a 20 20 20 20 20 20 20 20 20 20 6e 50 6f  a;.          nPo
2e10: 73 6c 69 73 74 20 3d 20 66 74 73 35 47 65 74 34  slist = fts5Get4
2e20: 42 79 74 65 56 61 72 69 6e 74 28 26 70 50 74 72  ByteVarint(&pPtr
2e30: 5b 69 4f 66 66 5d 2c 20 26 6e 56 61 72 69 6e 74  [iOff], &nVarint
2e40: 29 3b 0a 20 20 20 20 20 20 20 20 20 20 69 4f 66  );.          iOf
2e50: 66 20 2b 3d 20 34 3b 0a 20 20 20 20 20 20 20 20  f += 4;.        
2e60: 20 20 72 63 20 3d 20 78 45 6e 74 72 79 28 70 43    rc = xEntry(pC
2e70: 74 78 2c 20 69 52 6f 77 69 64 2c 20 26 70 50 74  tx, iRowid, &pPt
2e80: 72 5b 69 4f 66 66 2d 6e 56 61 72 69 6e 74 5d 2c  r[iOff-nVarint],
2e90: 20 6e 50 6f 73 6c 69 73 74 2b 6e 56 61 72 69 6e   nPoslist+nVarin
2ea0: 74 29 3b 0a 20 20 20 20 20 20 20 20 20 20 69 4f  t);.          iO
2eb0: 66 66 20 2b 3d 20 6e 50 6f 73 6c 69 73 74 3b 0a  ff += nPoslist;.
2ec0: 20 20 20 20 20 20 20 20 7d 0a 0a 20 20 20 20 20          }..     
2ed0: 20 20 20 2f 2a 20 49 73 73 75 65 20 74 68 65 20     /* Issue the 
2ee0: 74 65 72 6d 2d 64 6f 6e 65 20 63 61 6c 6c 62 61  term-done callba
2ef0: 63 6b 20 2a 2f 0a 20 20 20 20 20 20 20 20 69 66  ck */.        if
2f00: 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20  ( rc==SQLITE_OK 
2f10: 29 20 72 63 20 3d 20 78 54 65 72 6d 44 6f 6e 65  ) rc = xTermDone
2f20: 28 70 43 74 78 29 3b 0a 20 20 20 20 20 20 7d 0a  (pCtx);.      }.
2f30: 20 20 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72        sqlite3_fr
2f40: 65 65 28 70 4c 69 73 74 29 3b 0a 20 20 20 20 20  ee(pList);.     
2f50: 20 70 4c 69 73 74 20 3d 20 70 4e 65 78 74 3b 0a   pList = pNext;.
2f60: 20 20 20 20 7d 0a 20 20 7d 0a 20 20 72 65 74 75      }.  }.  retu
2f70: 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20  rn rc;.}../*.** 
2f80: 51 75 65 72 79 20 74 68 65 20 68 61 73 68 20 74  Query the hash t
2f90: 61 62 6c 65 20 66 6f 72 20 61 20 64 6f 63 6c 69  able for a docli
2fa0: 73 74 20 61 73 73 6f 63 69 61 74 65 64 20 77 69  st associated wi
2fb0: 74 68 20 74 65 72 6d 20 70 54 65 72 6d 2f 6e 54  th term pTerm/nT
2fc0: 65 72 6d 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69  erm..*/.int sqli
2fd0: 74 65 33 46 74 73 35 48 61 73 68 51 75 65 72 79  te3Fts5HashQuery
2fe0: 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a 70 48  (.  Fts5Hash *pH
2ff0: 61 73 68 2c 20 20 20 20 20 20 20 20 20 20 20 20  ash,            
3000: 20 20 20 20 2f 2a 20 48 61 73 68 20 74 61 62 6c      /* Hash tabl
3010: 65 20 74 6f 20 71 75 65 72 79 20 2a 2f 0a 20 20  e to query */.  
3020: 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 54 65 72  const char *pTer
3030: 6d 2c 20 69 6e 74 20 6e 54 65 72 6d 2c 20 20 20  m, int nTerm,   
3040: 2f 2a 20 51 75 65 72 79 20 74 65 72 6d 20 2a 2f  /* Query term */
3050: 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 2a  .  const char **
3060: 70 70 44 6f 63 6c 69 73 74 2c 20 20 20 20 20 20  ppDoclist,      
3070: 20 20 20 2f 2a 20 4f 55 54 3a 20 50 6f 69 6e 74     /* OUT: Point
3080: 65 72 20 74 6f 20 64 6f 63 6c 69 73 74 20 66 6f  er to doclist fo
3090: 72 20 70 54 65 72 6d 20 2a 2f 0a 20 20 69 6e 74  r pTerm */.  int
30a0: 20 2a 70 6e 44 6f 63 6c 69 73 74 20 20 20 20 20   *pnDoclist     
30b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
30c0: 4f 55 54 3a 20 53 69 7a 65 20 6f 66 20 64 6f 63  OUT: Size of doc
30d0: 6c 69 73 74 20 69 6e 20 62 79 74 65 73 20 2a 2f  list in bytes */
30e0: 0a 29 7b 0a 20 20 75 6e 73 69 67 6e 65 64 20 69  .){.  unsigned i
30f0: 6e 74 20 69 48 61 73 68 20 3d 20 66 74 73 35 48  nt iHash = fts5H
3100: 61 73 68 4b 65 79 28 70 48 61 73 68 2d 3e 6e 53  ashKey(pHash->nS
3110: 6c 6f 74 2c 20 70 54 65 72 6d 2c 20 6e 54 65 72  lot, pTerm, nTer
3120: 6d 29 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e  m);.  Fts5HashEn
3130: 74 72 79 20 2a 70 3b 0a 0a 20 20 66 6f 72 28 70  try *p;..  for(p
3140: 3d 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 48  =pHash->aSlot[iH
3150: 61 73 68 5d 3b 20 70 3b 20 70 3d 70 2d 3e 70 48  ash]; p; p=p->pH
3160: 61 73 68 4e 65 78 74 29 7b 0a 20 20 20 20 69 66  ashNext){.    if
3170: 28 20 6d 65 6d 63 6d 70 28 70 2d 3e 7a 4b 65 79  ( memcmp(p->zKey
3180: 2c 20 70 54 65 72 6d 2c 20 6e 54 65 72 6d 29 3d  , pTerm, nTerm)=
3190: 3d 30 20 26 26 20 70 2d 3e 7a 4b 65 79 5b 6e 54  =0 && p->zKey[nT
31a0: 65 72 6d 5d 3d 3d 30 20 29 20 62 72 65 61 6b 3b  erm]==0 ) break;
31b0: 0a 20 20 7d 0a 0a 20 20 69 66 28 20 70 20 29 7b  .  }..  if( p ){
31c0: 0a 20 20 20 20 75 38 20 2a 70 50 74 72 20 3d 20  .    u8 *pPtr = 
31d0: 28 75 38 2a 29 70 3b 0a 20 20 20 20 66 74 73 35  (u8*)p;.    fts5
31e0: 50 75 74 34 42 79 74 65 56 61 72 69 6e 74 28 26  Put4ByteVarint(&
31f0: 70 50 74 72 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69  pPtr[p->iSzPosli
3200: 73 74 5d 2c 20 70 2d 3e 6e 44 61 74 61 20 2d 20  st], p->nData - 
3210: 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 2d 20  p->iSzPoslist - 
3220: 34 29 3b 0a 20 20 20 20 2a 70 70 44 6f 63 6c 69  4);.    *ppDocli
3230: 73 74 20 3d 20 26 70 2d 3e 7a 4b 65 79 5b 6e 54  st = &p->zKey[nT
3240: 65 72 6d 2b 31 5d 3b 0a 20 20 20 20 2a 70 6e 44  erm+1];.    *pnD
3250: 6f 63 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74  oclist = p->nDat
3260: 61 20 2d 20 28 73 69 7a 65 6f 66 28 2a 70 29 20  a - (sizeof(*p) 
3270: 2b 20 6e 54 65 72 6d 20 2b 20 31 29 3b 0a 20 20  + nTerm + 1);.  
3280: 7d 65 6c 73 65 7b 0a 20 20 20 20 2a 70 70 44 6f  }else{.    *ppDo
3290: 63 6c 69 73 74 20 3d 20 30 3b 0a 20 20 20 20 2a  clist = 0;.    *
32a0: 70 6e 44 6f 63 6c 69 73 74 20 3d 20 30 3b 0a 20  pnDoclist = 0;. 
32b0: 20 7d 0a 0a 20 20 72 65 74 75 72 6e 20 53 51 4c   }..  return SQL
32c0: 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 76 6f 69 64 20  ITE_OK;.}..void 
32d0: 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 53  sqlite3Fts5HashS
32e0: 63 61 6e 49 6e 69 74 28 0a 20 20 46 74 73 35 48  canInit(.  Fts5H
32f0: 61 73 68 20 2a 70 2c 20 20 20 20 20 20 20 20 20  ash *p,         
3300: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 48 61             /* Ha
3310: 73 68 20 74 61 62 6c 65 20 74 6f 20 71 75 65 72  sh table to quer
3320: 79 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61  y */.  const cha
3330: 72 20 2a 70 54 65 72 6d 2c 20 69 6e 74 20 6e 54  r *pTerm, int nT
3340: 65 72 6d 20 20 20 20 2f 2a 20 51 75 65 72 79 20  erm    /* Query 
3350: 70 72 65 66 69 78 20 2a 2f 0a 29 7b 0a 20 20 66  prefix */.){.  f
3360: 74 73 35 48 61 73 68 45 6e 74 72 79 53 6f 72 74  ts5HashEntrySort
3370: 28 70 2c 20 70 54 65 72 6d 2c 20 6e 54 65 72 6d  (p, pTerm, nTerm
3380: 2c 20 26 70 2d 3e 70 53 63 61 6e 29 3b 0a 7d 0a  , &p->pScan);.}.
3390: 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 46 74 73  .void sqlite3Fts
33a0: 35 48 61 73 68 53 63 61 6e 4e 65 78 74 28 46 74  5HashScanNext(Ft
33b0: 73 35 48 61 73 68 20 2a 70 29 7b 0a 20 20 69 66  s5Hash *p){.  if
33c0: 28 20 70 2d 3e 70 53 63 61 6e 20 29 7b 0a 20 20  ( p->pScan ){.  
33d0: 20 20 70 2d 3e 70 53 63 61 6e 20 3d 20 70 2d 3e    p->pScan = p->
33e0: 70 53 63 61 6e 2d 3e 70 53 63 61 6e 4e 65 78 74  pScan->pScanNext
33f0: 3b 0a 20 20 7d 0a 7d 0a 0a 69 6e 74 20 73 71 6c  ;.  }.}..int sql
3400: 69 74 65 33 46 74 73 35 48 61 73 68 53 63 61 6e  ite3Fts5HashScan
3410: 45 6f 66 28 46 74 73 35 48 61 73 68 20 2a 70 29  Eof(Fts5Hash *p)
3420: 7b 0a 20 20 72 65 74 75 72 6e 20 28 70 2d 3e 70  {.  return (p->p
3430: 53 63 61 6e 3d 3d 30 29 3b 0a 7d 0a 0a 76 6f 69  Scan==0);.}..voi
3440: 64 20 73 71 6c 69 74 65 33 46 74 73 35 48 61 73  d sqlite3Fts5Has
3450: 68 53 63 61 6e 45 6e 74 72 79 28 0a 20 20 46 74  hScanEntry(.  Ft
3460: 73 35 48 61 73 68 20 2a 70 48 61 73 68 2c 0a 20  s5Hash *pHash,. 
3470: 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 2a 70 7a   const char **pz
3480: 54 65 72 6d 2c 20 20 20 20 20 20 20 20 20 20 20  Term,           
3490: 20 2f 2a 20 4f 55 54 3a 20 74 65 72 6d 20 28 6e   /* OUT: term (n
34a0: 75 6c 2d 74 65 72 6d 69 6e 61 74 65 64 29 20 2a  ul-terminated) *
34b0: 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a  /.  const char *
34c0: 2a 70 70 44 6f 63 6c 69 73 74 2c 20 20 20 20 20  *ppDoclist,     
34d0: 20 20 20 20 2f 2a 20 4f 55 54 3a 20 70 6f 69 6e      /* OUT: poin
34e0: 74 65 72 20 74 6f 20 64 6f 63 6c 69 73 74 20 2a  ter to doclist *
34f0: 2f 0a 20 20 69 6e 74 20 2a 70 6e 44 6f 63 6c 69  /.  int *pnDocli
3500: 73 74 20 20 20 20 20 20 20 20 20 20 20 20 20 20  st              
3510: 20 20 20 20 2f 2a 20 4f 55 54 3a 20 73 69 7a 65      /* OUT: size
3520: 20 6f 66 20 64 6f 63 6c 69 73 74 20 69 6e 20 62   of doclist in b
3530: 79 74 65 73 20 2a 2f 0a 29 7b 0a 20 20 46 74 73  ytes */.){.  Fts
3540: 35 48 61 73 68 45 6e 74 72 79 20 2a 70 3b 0a 20  5HashEntry *p;. 
3550: 20 69 66 28 20 28 70 20 3d 20 70 48 61 73 68 2d   if( (p = pHash-
3560: 3e 70 53 63 61 6e 29 20 29 7b 0a 20 20 20 20 75  >pScan) ){.    u
3570: 38 20 2a 70 50 74 72 20 3d 20 28 75 38 2a 29 70  8 *pPtr = (u8*)p
3580: 3b 0a 20 20 20 20 69 6e 74 20 6e 54 65 72 6d 20  ;.    int nTerm 
3590: 3d 20 73 74 72 6c 65 6e 28 70 2d 3e 7a 4b 65 79  = strlen(p->zKey
35a0: 29 3b 0a 20 20 20 20 66 74 73 35 50 75 74 34 42  );.    fts5Put4B
35b0: 79 74 65 56 61 72 69 6e 74 28 26 70 50 74 72 5b  yteVarint(&pPtr[
35c0: 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 5d 2c 20  p->iSzPoslist], 
35d0: 70 2d 3e 6e 44 61 74 61 20 2d 20 70 2d 3e 69 53  p->nData - p->iS
35e0: 7a 50 6f 73 6c 69 73 74 20 2d 20 34 29 3b 0a 20  zPoslist - 4);. 
35f0: 20 20 20 2a 70 7a 54 65 72 6d 20 3d 20 70 2d 3e     *pzTerm = p->
3600: 7a 4b 65 79 3b 0a 20 20 20 20 2a 70 70 44 6f 63  zKey;.    *ppDoc
3610: 6c 69 73 74 20 3d 20 26 70 2d 3e 7a 4b 65 79 5b  list = &p->zKey[
3620: 6e 54 65 72 6d 2b 31 5d 3b 0a 20 20 20 20 2a 70  nTerm+1];.    *p
3630: 6e 44 6f 63 6c 69 73 74 20 3d 20 70 2d 3e 6e 44  nDoclist = p->nD
3640: 61 74 61 20 2d 20 28 73 69 7a 65 6f 66 28 2a 70  ata - (sizeof(*p
3650: 29 20 2b 20 6e 54 65 72 6d 20 2b 20 31 29 3b 0a  ) + nTerm + 1);.
3660: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2a 70 7a    }else{.    *pz
3670: 54 65 72 6d 20 3d 20 30 3b 0a 20 20 20 20 2a 70  Term = 0;.    *p
3680: 70 44 6f 63 6c 69 73 74 20 3d 20 30 3b 0a 20 20  pDoclist = 0;.  
3690: 20 20 2a 70 6e 44 6f 63 6c 69 73 74 20 3d 20 30    *pnDoclist = 0
36a0: 3b 0a 20 20 7d 0a 7d 0a 0a                       ;.  }.}..