/ Hex Artifact Content
Login

Artifact 323099a445bf8f608af069e2d8ff4bb93db9904c:


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 73 74 61 74 69 63 20 76 6f 69 64 20 66 74 73  .static void fts
1430: 35 48 61 73 68 41 64 64 50 6f 73 6c 69 73 74 53  5HashAddPoslistS
1440: 69 7a 65 28 46 74 73 35 48 61 73 68 45 6e 74 72  ize(Fts5HashEntr
1450: 79 20 2a 70 29 7b 0a 20 20 69 66 28 20 70 2d 3e  y *p){.  if( p->
1460: 69 53 7a 50 6f 73 6c 69 73 74 20 29 7b 0a 20 20  iSzPoslist ){.  
1470: 20 20 75 38 20 2a 70 50 74 72 20 3d 20 28 75 38    u8 *pPtr = (u8
1480: 2a 29 70 3b 0a 20 20 20 20 69 6e 74 20 6e 53 7a  *)p;.    int nSz
1490: 20 3d 20 70 2d 3e 6e 44 61 74 61 20 2d 20 70 2d   = p->nData - p-
14a0: 3e 69 53 7a 50 6f 73 6c 69 73 74 20 2d 20 31 3b  >iSzPoslist - 1;
14b0: 0a 0a 20 20 20 20 69 66 28 20 6e 53 7a 3c 3d 31  ..    if( nSz<=1
14c0: 32 37 20 29 7b 0a 20 20 20 20 20 20 70 50 74 72  27 ){.      pPtr
14d0: 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 5d 20  [p->iSzPoslist] 
14e0: 3d 20 6e 53 7a 3b 0a 20 20 20 20 7d 65 6c 73 65  = nSz;.    }else
14f0: 7b 0a 20 20 20 20 20 20 69 6e 74 20 6e 42 79 74  {.      int nByt
1500: 65 20 3d 20 73 71 6c 69 74 65 33 46 74 73 35 47  e = sqlite3Fts5G
1510: 65 74 56 61 72 69 6e 74 4c 65 6e 28 28 75 33 32  etVarintLen((u32
1520: 29 6e 53 7a 29 3b 0a 20 20 20 20 20 20 6d 65 6d  )nSz);.      mem
1530: 6d 6f 76 65 28 26 70 50 74 72 5b 70 2d 3e 69 53  move(&pPtr[p->iS
1540: 7a 50 6f 73 6c 69 73 74 20 2b 20 6e 42 79 74 65  zPoslist + nByte
1550: 5d 2c 20 26 70 50 74 72 5b 70 2d 3e 69 53 7a 50  ], &pPtr[p->iSzP
1560: 6f 73 6c 69 73 74 20 2b 20 31 5d 2c 20 6e 53 7a  oslist + 1], nSz
1570: 29 3b 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33  );.      sqlite3
1580: 50 75 74 56 61 72 69 6e 74 28 26 70 50 74 72 5b  PutVarint(&pPtr[
1590: 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 5d 2c 20  p->iSzPoslist], 
15a0: 6e 53 7a 29 3b 0a 20 20 20 20 20 20 70 2d 3e 6e  nSz);.      p->n
15b0: 44 61 74 61 20 2b 3d 20 28 6e 42 79 74 65 2d 31  Data += (nByte-1
15c0: 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 70 2d 3e  );.    }.    p->
15d0: 69 53 7a 50 6f 73 6c 69 73 74 20 3d 20 30 3b 0a  iSzPoslist = 0;.
15e0: 20 20 7d 0a 7d 0a 0a 69 6e 74 20 73 71 6c 69 74    }.}..int sqlit
15f0: 65 33 46 74 73 35 48 61 73 68 57 72 69 74 65 28  e3Fts5HashWrite(
1600: 0a 20 20 46 74 73 35 48 61 73 68 20 2a 70 48 61  .  Fts5Hash *pHa
1610: 73 68 2c 0a 20 20 69 36 34 20 69 52 6f 77 69 64  sh,.  i64 iRowid
1620: 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ,               
1630: 20 20 20 20 20 20 2f 2a 20 52 6f 77 69 64 20 66        /* Rowid f
1640: 6f 72 20 74 68 69 73 20 65 6e 74 72 79 20 2a 2f  or this entry */
1650: 0a 20 20 69 6e 74 20 69 43 6f 6c 2c 20 20 20 20  .  int iCol,    
1660: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1670: 20 20 20 2f 2a 20 43 6f 6c 75 6d 6e 20 74 6f 6b     /* Column tok
1680: 65 6e 20 61 70 70 65 61 72 73 20 69 6e 20 28 2d  en appears in (-
1690: 76 65 20 2d 3e 20 64 65 6c 65 74 65 29 20 2a 2f  ve -> delete) */
16a0: 0a 20 20 69 6e 74 20 69 50 6f 73 2c 20 20 20 20  .  int iPos,    
16b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
16c0: 20 20 20 2f 2a 20 50 6f 73 69 74 69 6f 6e 20 6f     /* Position o
16d0: 66 20 74 6f 6b 65 6e 20 77 69 74 68 69 6e 20 63  f token within c
16e0: 6f 6c 75 6d 6e 20 2a 2f 0a 20 20 63 6f 6e 73 74  olumn */.  const
16f0: 20 63 68 61 72 20 2a 70 54 6f 6b 65 6e 2c 20 69   char *pToken, i
1700: 6e 74 20 6e 54 6f 6b 65 6e 20 20 2f 2a 20 54 6f  nt nToken  /* To
1710: 6b 65 6e 20 74 6f 20 61 64 64 20 6f 72 20 72 65  ken to add or re
1720: 6d 6f 76 65 20 74 6f 20 6f 72 20 66 72 6f 6d 20  move to or from 
1730: 69 6e 64 65 78 20 2a 2f 0a 29 7b 0a 20 20 75 6e  index */.){.  un
1740: 73 69 67 6e 65 64 20 69 6e 74 20 69 48 61 73 68  signed int iHash
1750: 20 3d 20 66 74 73 35 48 61 73 68 4b 65 79 28 70   = fts5HashKey(p
1760: 48 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20 70 54 6f  Hash->nSlot, pTo
1770: 6b 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20  ken, nToken);.  
1780: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70  Fts5HashEntry *p
1790: 3b 0a 20 20 75 38 20 2a 70 50 74 72 3b 0a 20 20  ;.  u8 *pPtr;.  
17a0: 69 6e 74 20 6e 49 6e 63 72 20 3d 20 30 3b 20 20  int nIncr = 0;  
17b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
17c0: 2f 2a 20 41 6d 6f 75 6e 74 20 74 6f 20 69 6e 63  /* Amount to inc
17d0: 72 65 6d 65 6e 74 20 28 2a 70 48 61 73 68 2d 3e  rement (*pHash->
17e0: 70 6e 42 79 74 65 29 20 62 79 20 2a 2f 0a 0a 20  pnByte) by */.. 
17f0: 20 2f 2a 20 41 74 74 65 6d 70 74 20 74 6f 20 6c   /* Attempt to l
1800: 6f 63 61 74 65 20 61 6e 20 65 78 69 73 74 69 6e  ocate an existin
1810: 67 20 68 61 73 68 20 65 6e 74 72 79 20 2a 2f 0a  g hash entry */.
1820: 20 20 66 6f 72 28 70 3d 70 48 61 73 68 2d 3e 61    for(p=pHash->a
1830: 53 6c 6f 74 5b 69 48 61 73 68 5d 3b 20 70 3b 20  Slot[iHash]; p; 
1840: 70 3d 70 2d 3e 70 48 61 73 68 4e 65 78 74 29 7b  p=p->pHashNext){
1850: 0a 20 20 20 20 69 66 28 20 6d 65 6d 63 6d 70 28  .    if( memcmp(
1860: 70 2d 3e 7a 4b 65 79 2c 20 70 54 6f 6b 65 6e 2c  p->zKey, pToken,
1870: 20 6e 54 6f 6b 65 6e 29 3d 3d 30 20 26 26 20 70   nToken)==0 && p
1880: 2d 3e 7a 4b 65 79 5b 6e 54 6f 6b 65 6e 5d 3d 3d  ->zKey[nToken]==
1890: 30 20 29 20 62 72 65 61 6b 3b 0a 20 20 7d 0a 0a  0 ) break;.  }..
18a0: 20 20 2f 2a 20 49 66 20 61 6e 20 65 78 69 73 74    /* If an exist
18b0: 69 6e 67 20 68 61 73 68 20 65 6e 74 72 79 20 63  ing hash entry c
18c0: 61 6e 6e 6f 74 20 62 65 20 66 6f 75 6e 64 2c 20  annot be found, 
18d0: 63 72 65 61 74 65 20 61 20 6e 65 77 20 6f 6e 65  create a new one
18e0: 2e 20 2a 2f 0a 20 20 69 66 28 20 70 3d 3d 30 20  . */.  if( p==0 
18f0: 29 7b 0a 20 20 20 20 69 6e 74 20 6e 42 79 74 65  ){.    int nByte
1900: 20 3d 20 73 69 7a 65 6f 66 28 46 74 73 35 48 61   = sizeof(Fts5Ha
1910: 73 68 45 6e 74 72 79 29 20 2b 20 6e 54 6f 6b 65  shEntry) + nToke
1920: 6e 20 2b 20 31 20 2b 20 36 34 3b 0a 20 20 20 20  n + 1 + 64;.    
1930: 69 66 28 20 6e 42 79 74 65 3c 31 32 38 20 29 20  if( nByte<128 ) 
1940: 6e 42 79 74 65 20 3d 20 31 32 38 3b 0a 0a 20 20  nByte = 128;..  
1950: 20 20 69 66 28 20 28 70 48 61 73 68 2d 3e 6e 45    if( (pHash->nE
1960: 6e 74 72 79 2a 32 29 3e 3d 70 48 61 73 68 2d 3e  ntry*2)>=pHash->
1970: 6e 53 6c 6f 74 20 29 7b 0a 20 20 20 20 20 20 69  nSlot ){.      i
1980: 6e 74 20 72 63 20 3d 20 66 74 73 35 48 61 73 68  nt rc = fts5Hash
1990: 52 65 73 69 7a 65 28 70 48 61 73 68 29 3b 0a 20  Resize(pHash);. 
19a0: 20 20 20 20 20 69 66 28 20 72 63 21 3d 53 51 4c       if( rc!=SQL
19b0: 49 54 45 5f 4f 4b 20 29 20 72 65 74 75 72 6e 20  ITE_OK ) return 
19c0: 72 63 3b 0a 20 20 20 20 20 20 69 48 61 73 68 20  rc;.      iHash 
19d0: 3d 20 66 74 73 35 48 61 73 68 4b 65 79 28 70 48  = fts5HashKey(pH
19e0: 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20 70 54 6f 6b  ash->nSlot, pTok
19f0: 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 20  en, nToken);.   
1a00: 20 7d 0a 0a 20 20 20 20 70 20 3d 20 28 46 74 73   }..    p = (Fts
1a10: 35 48 61 73 68 45 6e 74 72 79 2a 29 73 71 6c 69  5HashEntry*)sqli
1a20: 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e 42 79 74 65  te3_malloc(nByte
1a30: 29 3b 0a 20 20 20 20 69 66 28 20 21 70 20 29 20  );.    if( !p ) 
1a40: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f  return SQLITE_NO
1a50: 4d 45 4d 3b 0a 20 20 20 20 6d 65 6d 73 65 74 28  MEM;.    memset(
1a60: 70 2c 20 30 2c 20 73 69 7a 65 6f 66 28 46 74 73  p, 0, sizeof(Fts
1a70: 35 48 61 73 68 45 6e 74 72 79 29 29 3b 0a 20 20  5HashEntry));.  
1a80: 20 20 70 2d 3e 6e 41 6c 6c 6f 63 20 3d 20 6e 42    p->nAlloc = nB
1a90: 79 74 65 3b 0a 20 20 20 20 6d 65 6d 63 70 79 28  yte;.    memcpy(
1aa0: 70 2d 3e 7a 4b 65 79 2c 20 70 54 6f 6b 65 6e 2c  p->zKey, pToken,
1ab0: 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 20 20 70 2d   nToken);.    p-
1ac0: 3e 7a 4b 65 79 5b 6e 54 6f 6b 65 6e 5d 20 3d 20  >zKey[nToken] = 
1ad0: 27 5c 30 27 3b 0a 20 20 20 20 70 2d 3e 6e 44 61  '\0';.    p->nDa
1ae0: 74 61 20 3d 20 6e 54 6f 6b 65 6e 20 2b 20 31 20  ta = nToken + 1 
1af0: 2b 20 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73  + sizeof(Fts5Has
1b00: 68 45 6e 74 72 79 29 3b 0a 20 20 20 20 70 2d 3e  hEntry);.    p->
1b10: 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69 74 65 33  nData += sqlite3
1b20: 50 75 74 56 61 72 69 6e 74 28 26 28 28 75 38 2a  PutVarint(&((u8*
1b30: 29 70 29 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20 69  )p)[p->nData], i
1b40: 52 6f 77 69 64 29 3b 0a 20 20 20 20 70 2d 3e 69  Rowid);.    p->i
1b50: 53 7a 50 6f 73 6c 69 73 74 20 3d 20 70 2d 3e 6e  SzPoslist = p->n
1b60: 44 61 74 61 3b 0a 20 20 20 20 70 2d 3e 6e 44 61  Data;.    p->nDa
1b70: 74 61 20 2b 3d 20 31 3b 0a 20 20 20 20 70 2d 3e  ta += 1;.    p->
1b80: 69 52 6f 77 69 64 20 3d 20 69 52 6f 77 69 64 3b  iRowid = iRowid;
1b90: 0a 20 20 20 20 70 2d 3e 70 48 61 73 68 4e 65 78  .    p->pHashNex
1ba0: 74 20 3d 20 70 48 61 73 68 2d 3e 61 53 6c 6f 74  t = pHash->aSlot
1bb0: 5b 69 48 61 73 68 5d 3b 0a 20 20 20 20 70 48 61  [iHash];.    pHa
1bc0: 73 68 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d  sh->aSlot[iHash]
1bd0: 20 3d 20 70 3b 0a 20 20 20 20 70 48 61 73 68 2d   = p;.    pHash-
1be0: 3e 6e 45 6e 74 72 79 2b 2b 3b 0a 20 20 20 20 6e  >nEntry++;.    n
1bf0: 49 6e 63 72 20 2b 3d 20 70 2d 3e 6e 44 61 74 61  Incr += p->nData
1c00: 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 43 68 65 63  ;.  }..  /* Chec
1c10: 6b 20 74 68 65 72 65 20 69 73 20 65 6e 6f 75 67  k there is enoug
1c20: 68 20 73 70 61 63 65 20 74 6f 20 61 70 70 65 6e  h space to appen
1c30: 64 20 61 20 6e 65 77 20 65 6e 74 72 79 2e 20 57  d a new entry. W
1c40: 6f 72 73 74 20 63 61 73 65 20 73 63 65 6e 61 72  orst case scenar
1c50: 69 6f 0a 20 20 2a 2a 20 69 73 3a 0a 20 20 2a 2a  io.  ** is:.  **
1c60: 0a 20 20 2a 2a 20 20 20 20 20 2b 20 39 20 62 79  .  **     + 9 by
1c70: 74 65 73 20 66 6f 72 20 61 20 6e 65 77 20 72 6f  tes for a new ro
1c80: 77 69 64 2c 0a 20 20 2a 2a 20 20 20 20 20 2b 20  wid,.  **     + 
1c90: 34 20 62 79 74 65 20 72 65 73 65 72 76 65 64 20  4 byte reserved 
1ca0: 66 6f 72 20 74 68 65 20 22 70 6f 73 6c 69 73 74  for the "poslist
1cb0: 20 73 69 7a 65 22 20 76 61 72 69 6e 74 2e 0a 20   size" varint.. 
1cc0: 20 2a 2a 20 20 20 20 20 2b 20 31 20 62 79 74 65   **     + 1 byte
1cd0: 20 66 6f 72 20 61 20 22 6e 65 77 20 63 6f 6c 75   for a "new colu
1ce0: 6d 6e 22 20 62 79 74 65 2c 0a 20 20 2a 2a 20 20  mn" byte,.  **  
1cf0: 20 20 20 2b 20 33 20 62 79 74 65 73 20 66 6f 72     + 3 bytes for
1d00: 20 61 20 6e 65 77 20 63 6f 6c 75 6d 6e 20 6e 75   a new column nu
1d10: 6d 62 65 72 20 28 31 36 2d 62 69 74 20 6d 61 78  mber (16-bit max
1d20: 29 20 61 73 20 61 20 76 61 72 69 6e 74 2c 0a 20  ) as a varint,. 
1d30: 20 2a 2a 20 20 20 20 20 2b 20 35 20 62 79 74 65   **     + 5 byte
1d40: 73 20 66 6f 72 20 74 68 65 20 6e 65 77 20 70 6f  s for the new po
1d50: 73 69 74 69 6f 6e 20 6f 66 66 73 65 74 20 28 33  sition offset (3
1d60: 32 2d 62 69 74 20 6d 61 78 29 2e 0a 20 20 2a 2f  2-bit max)..  */
1d70: 0a 20 20 69 66 28 20 28 70 2d 3e 6e 41 6c 6c 6f  .  if( (p->nAllo
1d80: 63 20 2d 20 70 2d 3e 6e 44 61 74 61 29 20 3c 20  c - p->nData) < 
1d90: 28 39 20 2b 20 34 20 2b 20 31 20 2b 20 33 20 2b  (9 + 4 + 1 + 3 +
1da0: 20 35 29 20 29 7b 0a 20 20 20 20 69 6e 74 20 6e   5) ){.    int n
1db0: 4e 65 77 20 3d 20 70 2d 3e 6e 41 6c 6c 6f 63 20  New = p->nAlloc 
1dc0: 2a 20 32 3b 0a 20 20 20 20 46 74 73 35 48 61 73  * 2;.    Fts5Has
1dd0: 68 45 6e 74 72 79 20 2a 70 4e 65 77 3b 0a 20 20  hEntry *pNew;.  
1de0: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20    Fts5HashEntry 
1df0: 2a 2a 70 70 3b 0a 20 20 20 20 70 4e 65 77 20 3d  **pp;.    pNew =
1e00: 20 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a   (Fts5HashEntry*
1e10: 29 73 71 6c 69 74 65 33 5f 72 65 61 6c 6c 6f 63  )sqlite3_realloc
1e20: 28 70 2c 20 6e 4e 65 77 29 3b 0a 20 20 20 20 69  (p, nNew);.    i
1e30: 66 28 20 70 4e 65 77 3d 3d 30 20 29 20 72 65 74  f( pNew==0 ) ret
1e40: 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d  urn SQLITE_NOMEM
1e50: 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 41 6c 6c  ;.    pNew->nAll
1e60: 6f 63 20 3d 20 6e 4e 65 77 3b 0a 20 20 20 20 66  oc = nNew;.    f
1e70: 6f 72 28 70 70 3d 26 70 48 61 73 68 2d 3e 61 53  or(pp=&pHash->aS
1e80: 6c 6f 74 5b 69 48 61 73 68 5d 3b 20 2a 70 70 21  lot[iHash]; *pp!
1e90: 3d 70 3b 20 70 70 3d 26 28 2a 70 70 29 2d 3e 70  =p; pp=&(*pp)->p
1ea0: 48 61 73 68 4e 65 78 74 29 3b 0a 20 20 20 20 2a  HashNext);.    *
1eb0: 70 70 20 3d 20 70 4e 65 77 3b 0a 20 20 20 20 70  pp = pNew;.    p
1ec0: 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 0a 20 20 70   = pNew;.  }.  p
1ed0: 50 74 72 20 3d 20 28 75 38 2a 29 70 3b 0a 20 20  Ptr = (u8*)p;.  
1ee0: 6e 49 6e 63 72 20 2d 3d 20 70 2d 3e 6e 44 61 74  nIncr -= p->nDat
1ef0: 61 3b 0a 0a 20 20 2f 2a 20 49 66 20 74 68 69 73  a;..  /* If this
1f00: 20 69 73 20 61 20 6e 65 77 20 72 6f 77 69 64 2c   is a new rowid,
1f10: 20 61 70 70 65 6e 64 20 74 68 65 20 34 2d 62 79   append the 4-by
1f20: 74 65 20 73 69 7a 65 20 66 69 65 6c 64 20 66 6f  te size field fo
1f30: 72 20 74 68 65 20 70 72 65 76 69 6f 75 73 0a 20  r the previous. 
1f40: 20 2a 2a 20 65 6e 74 72 79 2c 20 61 6e 64 20 74   ** entry, and t
1f50: 68 65 20 6e 65 77 20 72 6f 77 69 64 20 66 6f 72  he new rowid for
1f60: 20 74 68 69 73 20 65 6e 74 72 79 2e 20 20 2a 2f   this entry.  */
1f70: 0a 20 20 69 66 28 20 69 52 6f 77 69 64 21 3d 70  .  if( iRowid!=p
1f80: 2d 3e 69 52 6f 77 69 64 20 29 7b 0a 20 20 20 20  ->iRowid ){.    
1f90: 66 74 73 35 48 61 73 68 41 64 64 50 6f 73 6c 69  fts5HashAddPosli
1fa0: 73 74 53 69 7a 65 28 70 29 3b 0a 20 20 20 20 70  stSize(p);.    p
1fb0: 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69 74  ->nData += sqlit
1fc0: 65 33 50 75 74 56 61 72 69 6e 74 28 26 70 50 74  e3PutVarint(&pPt
1fd0: 72 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20 69 52 6f  r[p->nData], iRo
1fe0: 77 69 64 20 2d 20 70 2d 3e 69 52 6f 77 69 64 29  wid - p->iRowid)
1ff0: 3b 0a 20 20 20 20 70 2d 3e 69 53 7a 50 6f 73 6c  ;.    p->iSzPosl
2000: 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a  ist = p->nData;.
2010: 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20      p->nData += 
2020: 31 3b 0a 20 20 20 20 70 2d 3e 69 43 6f 6c 20 3d  1;.    p->iCol =
2030: 20 30 3b 0a 20 20 20 20 70 2d 3e 69 50 6f 73 20   0;.    p->iPos 
2040: 3d 20 30 3b 0a 20 20 20 20 70 2d 3e 69 52 6f 77  = 0;.    p->iRow
2050: 69 64 20 3d 20 69 52 6f 77 69 64 3b 0a 20 20 7d  id = iRowid;.  }
2060: 0a 0a 20 20 69 66 28 20 69 43 6f 6c 3e 3d 30 20  ..  if( iCol>=0 
2070: 29 7b 0a 20 20 20 20 2f 2a 20 41 70 70 65 6e 64  ){.    /* Append
2080: 20 61 20 6e 65 77 20 63 6f 6c 75 6d 6e 20 76 61   a new column va
2090: 6c 75 65 2c 20 69 66 20 6e 65 63 65 73 73 61 72  lue, if necessar
20a0: 79 20 2a 2f 0a 20 20 20 20 61 73 73 65 72 74 28  y */.    assert(
20b0: 20 69 43 6f 6c 3e 3d 70 2d 3e 69 43 6f 6c 20 29   iCol>=p->iCol )
20c0: 3b 0a 20 20 20 20 69 66 28 20 69 43 6f 6c 21 3d  ;.    if( iCol!=
20d0: 70 2d 3e 69 43 6f 6c 20 29 7b 0a 20 20 20 20 20  p->iCol ){.     
20e0: 20 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61 2b 2b   pPtr[p->nData++
20f0: 5d 20 3d 20 30 78 30 31 3b 0a 20 20 20 20 20 20  ] = 0x01;.      
2100: 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69  p->nData += sqli
2110: 74 65 33 50 75 74 56 61 72 69 6e 74 28 26 70 50  te3PutVarint(&pP
2120: 74 72 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20 69 43  tr[p->nData], iC
2130: 6f 6c 29 3b 0a 20 20 20 20 20 20 70 2d 3e 69 43  ol);.      p->iC
2140: 6f 6c 20 3d 20 69 43 6f 6c 3b 0a 20 20 20 20 20  ol = iCol;.     
2150: 20 70 2d 3e 69 50 6f 73 20 3d 20 30 3b 0a 20 20   p->iPos = 0;.  
2160: 20 20 7d 0a 0a 20 20 20 20 2f 2a 20 41 70 70 65    }..    /* Appe
2170: 6e 64 20 74 68 65 20 6e 65 77 20 70 6f 73 69 74  nd the new posit
2180: 69 6f 6e 20 6f 66 66 73 65 74 20 2a 2f 0a 20 20  ion offset */.  
2190: 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71    p->nData += sq
21a0: 6c 69 74 65 33 50 75 74 56 61 72 69 6e 74 28 26  lite3PutVarint(&
21b0: 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20  pPtr[p->nData], 
21c0: 69 50 6f 73 20 2d 20 70 2d 3e 69 50 6f 73 20 2b  iPos - p->iPos +
21d0: 20 32 29 3b 0a 20 20 20 20 70 2d 3e 69 50 6f 73   2);.    p->iPos
21e0: 20 3d 20 69 50 6f 73 3b 0a 20 20 7d 0a 20 20 6e   = iPos;.  }.  n
21f0: 49 6e 63 72 20 2b 3d 20 70 2d 3e 6e 44 61 74 61  Incr += p->nData
2200: 3b 0a 0a 20 20 2a 70 48 61 73 68 2d 3e 70 6e 42  ;..  *pHash->pnB
2210: 79 74 65 20 2b 3d 20 6e 49 6e 63 72 3b 0a 20 20  yte += nIncr;.  
2220: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b  return SQLITE_OK
2230: 3b 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a 20 41 72 67 75  ;.}.../*.** Argu
2240: 6d 65 6e 74 73 20 70 4c 65 66 74 20 61 6e 64 20  ments pLeft and 
2250: 70 52 69 67 68 74 20 70 6f 69 6e 74 20 74 6f 20  pRight point to 
2260: 6c 69 6e 6b 65 64 2d 6c 69 73 74 73 20 6f 66 20  linked-lists of 
2270: 68 61 73 68 2d 65 6e 74 72 79 20 6f 62 6a 65 63  hash-entry objec
2280: 74 73 2c 0a 2a 2a 20 65 61 63 68 20 73 6f 72 74  ts,.** each sort
2290: 65 64 20 69 6e 20 6b 65 79 20 6f 72 64 65 72 2e  ed in key order.
22a0: 20 54 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 6d   This function m
22b0: 65 72 67 65 73 20 74 68 65 20 74 77 6f 20 6c 69  erges the two li
22c0: 73 74 73 20 69 6e 74 6f 20 61 0a 2a 2a 20 73 69  sts into a.** si
22d0: 6e 67 6c 65 20 6c 69 73 74 20 61 6e 64 20 72 65  ngle list and re
22e0: 74 75 72 6e 73 20 61 20 70 6f 69 6e 74 65 72 20  turns a pointer 
22f0: 74 6f 20 69 74 73 20 66 69 72 73 74 20 65 6c 65  to its first ele
2300: 6d 65 6e 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 20  ment..*/.static 
2310: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 66  Fts5HashEntry *f
2320: 74 73 35 48 61 73 68 45 6e 74 72 79 4d 65 72 67  ts5HashEntryMerg
2330: 65 28 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74  e(.  Fts5HashEnt
2340: 72 79 20 2a 70 4c 65 66 74 2c 0a 20 20 46 74 73  ry *pLeft,.  Fts
2350: 35 48 61 73 68 45 6e 74 72 79 20 2a 70 52 69 67  5HashEntry *pRig
2360: 68 74 0a 29 7b 0a 20 20 46 74 73 35 48 61 73 68  ht.){.  Fts5Hash
2370: 45 6e 74 72 79 20 2a 70 31 20 3d 20 70 4c 65 66  Entry *p1 = pLef
2380: 74 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74  t;.  Fts5HashEnt
2390: 72 79 20 2a 70 32 20 3d 20 70 52 69 67 68 74 3b  ry *p2 = pRight;
23a0: 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  .  Fts5HashEntry
23b0: 20 2a 70 52 65 74 20 3d 20 30 3b 0a 20 20 46 74   *pRet = 0;.  Ft
23c0: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 70 70  s5HashEntry **pp
23d0: 4f 75 74 20 3d 20 26 70 52 65 74 3b 0a 0a 20 20  Out = &pRet;..  
23e0: 77 68 69 6c 65 28 20 70 31 20 7c 7c 20 70 32 20  while( p1 || p2 
23f0: 29 7b 0a 20 20 20 20 69 66 28 20 70 31 3d 3d 30  ){.    if( p1==0
2400: 20 29 7b 0a 20 20 20 20 20 20 2a 70 70 4f 75 74   ){.      *ppOut
2410: 20 3d 20 70 32 3b 0a 20 20 20 20 20 20 70 32 20   = p2;.      p2 
2420: 3d 20 30 3b 0a 20 20 20 20 7d 65 6c 73 65 20 69  = 0;.    }else i
2430: 66 28 20 70 32 3d 3d 30 20 29 7b 0a 20 20 20 20  f( p2==0 ){.    
2440: 20 20 2a 70 70 4f 75 74 20 3d 20 70 31 3b 0a 20    *ppOut = p1;. 
2450: 20 20 20 20 20 70 31 20 3d 20 30 3b 0a 20 20 20       p1 = 0;.   
2460: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 69 6e   }else{.      in
2470: 74 20 69 20 3d 20 30 3b 0a 20 20 20 20 20 20 77  t i = 0;.      w
2480: 68 69 6c 65 28 20 70 31 2d 3e 7a 4b 65 79 5b 69  hile( p1->zKey[i
2490: 5d 3d 3d 70 32 2d 3e 7a 4b 65 79 5b 69 5d 20 29  ]==p2->zKey[i] )
24a0: 20 69 2b 2b 3b 0a 0a 20 20 20 20 20 20 69 66 28   i++;..      if(
24b0: 20 28 28 75 38 29 70 31 2d 3e 7a 4b 65 79 5b 69   ((u8)p1->zKey[i
24c0: 5d 29 3e 28 28 75 38 29 70 32 2d 3e 7a 4b 65 79  ])>((u8)p2->zKey
24d0: 5b 69 5d 29 20 29 7b 0a 20 20 20 20 20 20 20 20  [i]) ){.        
24e0: 2f 2a 20 70 32 20 69 73 20 73 6d 61 6c 6c 65 72  /* p2 is smaller
24f0: 20 2a 2f 0a 20 20 20 20 20 20 20 20 2a 70 70 4f   */.        *ppO
2500: 75 74 20 3d 20 70 32 3b 0a 20 20 20 20 20 20 20  ut = p2;.       
2510: 20 70 70 4f 75 74 20 3d 20 26 70 32 2d 3e 70 53   ppOut = &p2->pS
2520: 63 61 6e 4e 65 78 74 3b 0a 20 20 20 20 20 20 20  canNext;.       
2530: 20 70 32 20 3d 20 70 32 2d 3e 70 53 63 61 6e 4e   p2 = p2->pScanN
2540: 65 78 74 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65  ext;.      }else
2550: 7b 0a 20 20 20 20 20 20 20 20 2f 2a 20 70 31 20  {.        /* p1 
2560: 69 73 20 73 6d 61 6c 6c 65 72 20 2a 2f 0a 20 20  is smaller */.  
2570: 20 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 70        *ppOut = p
2580: 31 3b 0a 20 20 20 20 20 20 20 20 70 70 4f 75 74  1;.        ppOut
2590: 20 3d 20 26 70 31 2d 3e 70 53 63 61 6e 4e 65 78   = &p1->pScanNex
25a0: 74 3b 0a 20 20 20 20 20 20 20 20 70 31 20 3d 20  t;.        p1 = 
25b0: 70 31 2d 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 20  p1->pScanNext;. 
25c0: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 2a 70 70       }.      *pp
25d0: 4f 75 74 20 3d 20 30 3b 0a 20 20 20 20 7d 0a 20  Out = 0;.    }. 
25e0: 20 7d 0a 0a 20 20 72 65 74 75 72 6e 20 70 52 65   }..  return pRe
25f0: 74 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 45 78 74 72  t;.}../*.** Extr
2600: 61 63 74 20 61 6c 6c 20 74 6f 6b 65 6e 73 20 66  act all tokens f
2610: 72 6f 6d 20 68 61 73 68 20 74 61 62 6c 65 20 69  rom hash table i
2620: 48 61 73 68 20 61 6e 64 20 6c 69 6e 6b 20 74 68  Hash and link th
2630: 65 6d 20 69 6e 74 6f 20 61 20 6c 69 73 74 0a 2a  em into a list.*
2640: 2a 20 69 6e 20 73 6f 72 74 65 64 20 6f 72 64 65  * in sorted orde
2650: 72 2e 20 54 68 65 20 68 61 73 68 20 74 61 62 6c  r. The hash tabl
2660: 65 20 69 73 20 63 6c 65 61 72 65 64 20 62 65 66  e is cleared bef
2670: 6f 72 65 20 72 65 74 75 72 6e 69 6e 67 2e 20 49  ore returning. I
2680: 74 20 69 73 0a 2a 2a 20 74 68 65 20 72 65 73 70  t is.** the resp
2690: 6f 6e 73 69 62 69 6c 69 74 79 20 6f 66 20 74 68  onsibility of th
26a0: 65 20 63 61 6c 6c 65 72 20 74 6f 20 66 72 65 65  e caller to free
26b0: 20 74 68 65 20 65 6c 65 6d 65 6e 74 73 20 6f 66   the elements of
26c0: 20 74 68 65 20 72 65 74 75 72 6e 65 64 0a 2a 2a   the returned.**
26d0: 20 6c 69 73 74 2e 0a 2a 2f 0a 73 74 61 74 69 63   list..*/.static
26e0: 20 69 6e 74 20 66 74 73 35 48 61 73 68 45 6e 74   int fts5HashEnt
26f0: 72 79 53 6f 72 74 28 0a 20 20 46 74 73 35 48 61  rySort(.  Fts5Ha
2700: 73 68 20 2a 70 48 61 73 68 2c 20 0a 20 20 63 6f  sh *pHash, .  co
2710: 6e 73 74 20 63 68 61 72 20 2a 70 54 65 72 6d 2c  nst char *pTerm,
2720: 20 69 6e 74 20 6e 54 65 72 6d 2c 20 20 20 2f 2a   int nTerm,   /*
2730: 20 51 75 65 72 79 20 70 72 65 66 69 78 2c 20 69   Query prefix, i
2740: 66 20 61 6e 79 20 2a 2f 0a 20 20 46 74 73 35 48  f any */.  Fts5H
2750: 61 73 68 45 6e 74 72 79 20 2a 2a 70 70 53 6f 72  ashEntry **ppSor
2760: 74 65 64 0a 29 7b 0a 20 20 63 6f 6e 73 74 20 69  ted.){.  const i
2770: 6e 74 20 6e 4d 65 72 67 65 53 6c 6f 74 20 3d 20  nt nMergeSlot = 
2780: 33 32 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e  32;.  Fts5HashEn
2790: 74 72 79 20 2a 2a 61 70 3b 0a 20 20 46 74 73 35  try **ap;.  Fts5
27a0: 48 61 73 68 45 6e 74 72 79 20 2a 70 4c 69 73 74  HashEntry *pList
27b0: 3b 0a 20 20 69 6e 74 20 69 53 6c 6f 74 3b 0a 20  ;.  int iSlot;. 
27c0: 20 69 6e 74 20 69 3b 0a 0a 20 20 2a 70 70 53 6f   int i;..  *ppSo
27d0: 72 74 65 64 20 3d 20 30 3b 0a 20 20 61 70 20 3d  rted = 0;.  ap =
27e0: 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28   sqlite3_malloc(
27f0: 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45  sizeof(Fts5HashE
2800: 6e 74 72 79 2a 29 20 2a 20 6e 4d 65 72 67 65 53  ntry*) * nMergeS
2810: 6c 6f 74 29 3b 0a 20 20 69 66 28 20 21 61 70 20  lot);.  if( !ap 
2820: 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f  ) return SQLITE_
2830: 4e 4f 4d 45 4d 3b 0a 20 20 6d 65 6d 73 65 74 28  NOMEM;.  memset(
2840: 61 70 2c 20 30 2c 20 73 69 7a 65 6f 66 28 46 74  ap, 0, sizeof(Ft
2850: 73 35 48 61 73 68 45 6e 74 72 79 2a 29 20 2a 20  s5HashEntry*) * 
2860: 6e 4d 65 72 67 65 53 6c 6f 74 29 3b 0a 0a 20 20  nMergeSlot);..  
2870: 66 6f 72 28 69 53 6c 6f 74 3d 30 3b 20 69 53 6c  for(iSlot=0; iSl
2880: 6f 74 3c 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 3b  ot<pHash->nSlot;
2890: 20 69 53 6c 6f 74 2b 2b 29 7b 0a 20 20 20 20 46   iSlot++){.    F
28a0: 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 49  ts5HashEntry *pI
28b0: 74 65 72 3b 0a 20 20 20 20 66 6f 72 28 70 49 74  ter;.    for(pIt
28c0: 65 72 3d 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b  er=pHash->aSlot[
28d0: 69 53 6c 6f 74 5d 3b 20 70 49 74 65 72 3b 20 70  iSlot]; pIter; p
28e0: 49 74 65 72 3d 70 49 74 65 72 2d 3e 70 48 61 73  Iter=pIter->pHas
28f0: 68 4e 65 78 74 29 7b 0a 20 20 20 20 20 20 69 66  hNext){.      if
2900: 28 20 70 54 65 72 6d 3d 3d 30 20 7c 7c 20 30 3d  ( pTerm==0 || 0=
2910: 3d 6d 65 6d 63 6d 70 28 70 49 74 65 72 2d 3e 7a  =memcmp(pIter->z
2920: 4b 65 79 2c 20 70 54 65 72 6d 2c 20 6e 54 65 72  Key, pTerm, nTer
2930: 6d 29 20 29 7b 0a 20 20 20 20 20 20 20 20 46 74  m) ){.        Ft
2940: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 45 6e  s5HashEntry *pEn
2950: 74 72 79 20 3d 20 70 49 74 65 72 3b 0a 20 20 20  try = pIter;.   
2960: 20 20 20 20 20 70 45 6e 74 72 79 2d 3e 70 53 63       pEntry->pSc
2970: 61 6e 4e 65 78 74 20 3d 20 30 3b 0a 20 20 20 20  anNext = 0;.    
2980: 20 20 20 20 66 6f 72 28 69 3d 30 3b 20 61 70 5b      for(i=0; ap[
2990: 69 5d 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20  i]; i++){.      
29a0: 20 20 20 20 70 45 6e 74 72 79 20 3d 20 66 74 73      pEntry = fts
29b0: 35 48 61 73 68 45 6e 74 72 79 4d 65 72 67 65 28  5HashEntryMerge(
29c0: 70 45 6e 74 72 79 2c 20 61 70 5b 69 5d 29 3b 0a  pEntry, ap[i]);.
29d0: 20 20 20 20 20 20 20 20 20 20 61 70 5b 69 5d 20            ap[i] 
29e0: 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20  = 0;.        }. 
29f0: 20 20 20 20 20 20 20 61 70 5b 69 5d 20 3d 20 70         ap[i] = p
2a00: 45 6e 74 72 79 3b 0a 20 20 20 20 20 20 7d 0a 20  Entry;.      }. 
2a10: 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 70 4c 69 73     }.  }..  pLis
2a20: 74 20 3d 20 30 3b 0a 20 20 66 6f 72 28 69 3d 30  t = 0;.  for(i=0
2a30: 3b 20 69 3c 6e 4d 65 72 67 65 53 6c 6f 74 3b 20  ; i<nMergeSlot; 
2a40: 69 2b 2b 29 7b 0a 20 20 20 20 70 4c 69 73 74 20  i++){.    pList 
2a50: 3d 20 66 74 73 35 48 61 73 68 45 6e 74 72 79 4d  = fts5HashEntryM
2a60: 65 72 67 65 28 70 4c 69 73 74 2c 20 61 70 5b 69  erge(pList, ap[i
2a70: 5d 29 3b 0a 20 20 7d 0a 0a 20 20 70 48 61 73 68  ]);.  }..  pHash
2a80: 2d 3e 6e 45 6e 74 72 79 20 3d 20 30 3b 0a 20 20  ->nEntry = 0;.  
2a90: 73 71 6c 69 74 65 33 5f 66 72 65 65 28 61 70 29  sqlite3_free(ap)
2aa0: 3b 0a 20 20 2a 70 70 53 6f 72 74 65 64 20 3d 20  ;.  *ppSorted = 
2ab0: 70 4c 69 73 74 3b 0a 20 20 72 65 74 75 72 6e 20  pList;.  return 
2ac0: 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a  SQLITE_OK;.}../*
2ad0: 0a 2a 2a 20 51 75 65 72 79 20 74 68 65 20 68 61  .** Query the ha
2ae0: 73 68 20 74 61 62 6c 65 20 66 6f 72 20 61 20 64  sh table for a d
2af0: 6f 63 6c 69 73 74 20 61 73 73 6f 63 69 61 74 65  oclist associate
2b00: 64 20 77 69 74 68 20 74 65 72 6d 20 70 54 65 72  d with term pTer
2b10: 6d 2f 6e 54 65 72 6d 2e 0a 2a 2f 0a 69 6e 74 20  m/nTerm..*/.int 
2b20: 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 51  sqlite3Fts5HashQ
2b30: 75 65 72 79 28 0a 20 20 46 74 73 35 48 61 73 68  uery(.  Fts5Hash
2b40: 20 2a 70 48 61 73 68 2c 20 20 20 20 20 20 20 20   *pHash,        
2b50: 20 20 20 20 20 20 20 20 2f 2a 20 48 61 73 68 20          /* Hash 
2b60: 74 61 62 6c 65 20 74 6f 20 71 75 65 72 79 20 2a  table to query *
2b70: 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a  /.  const char *
2b80: 70 54 65 72 6d 2c 20 69 6e 74 20 6e 54 65 72 6d  pTerm, int nTerm
2b90: 2c 20 20 20 2f 2a 20 51 75 65 72 79 20 74 65 72  ,   /* Query ter
2ba0: 6d 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61  m */.  const cha
2bb0: 72 20 2a 2a 70 70 44 6f 63 6c 69 73 74 2c 20 20  r **ppDoclist,  
2bc0: 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20 50         /* OUT: P
2bd0: 6f 69 6e 74 65 72 20 74 6f 20 64 6f 63 6c 69 73  ointer to doclis
2be0: 74 20 66 6f 72 20 70 54 65 72 6d 20 2a 2f 0a 20  t for pTerm */. 
2bf0: 20 69 6e 74 20 2a 70 6e 44 6f 63 6c 69 73 74 20   int *pnDoclist 
2c00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2c10: 20 2f 2a 20 4f 55 54 3a 20 53 69 7a 65 20 6f 66   /* OUT: Size of
2c20: 20 64 6f 63 6c 69 73 74 20 69 6e 20 62 79 74 65   doclist in byte
2c30: 73 20 2a 2f 0a 29 7b 0a 20 20 75 6e 73 69 67 6e  s */.){.  unsign
2c40: 65 64 20 69 6e 74 20 69 48 61 73 68 20 3d 20 66  ed int iHash = f
2c50: 74 73 35 48 61 73 68 4b 65 79 28 70 48 61 73 68  ts5HashKey(pHash
2c60: 2d 3e 6e 53 6c 6f 74 2c 20 70 54 65 72 6d 2c 20  ->nSlot, pTerm, 
2c70: 6e 54 65 72 6d 29 3b 0a 20 20 46 74 73 35 48 61  nTerm);.  Fts5Ha
2c80: 73 68 45 6e 74 72 79 20 2a 70 3b 0a 0a 20 20 66  shEntry *p;..  f
2c90: 6f 72 28 70 3d 70 48 61 73 68 2d 3e 61 53 6c 6f  or(p=pHash->aSlo
2ca0: 74 5b 69 48 61 73 68 5d 3b 20 70 3b 20 70 3d 70  t[iHash]; p; p=p
2cb0: 2d 3e 70 48 61 73 68 4e 65 78 74 29 7b 0a 20 20  ->pHashNext){.  
2cc0: 20 20 69 66 28 20 6d 65 6d 63 6d 70 28 70 2d 3e    if( memcmp(p->
2cd0: 7a 4b 65 79 2c 20 70 54 65 72 6d 2c 20 6e 54 65  zKey, pTerm, nTe
2ce0: 72 6d 29 3d 3d 30 20 26 26 20 70 2d 3e 7a 4b 65  rm)==0 && p->zKe
2cf0: 79 5b 6e 54 65 72 6d 5d 3d 3d 30 20 29 20 62 72  y[nTerm]==0 ) br
2d00: 65 61 6b 3b 0a 20 20 7d 0a 0a 20 20 69 66 28 20  eak;.  }..  if( 
2d10: 70 20 29 7b 0a 20 20 20 20 66 74 73 35 48 61 73  p ){.    fts5Has
2d20: 68 41 64 64 50 6f 73 6c 69 73 74 53 69 7a 65 28  hAddPoslistSize(
2d30: 70 29 3b 0a 20 20 20 20 2a 70 70 44 6f 63 6c 69  p);.    *ppDocli
2d40: 73 74 20 3d 20 26 70 2d 3e 7a 4b 65 79 5b 6e 54  st = &p->zKey[nT
2d50: 65 72 6d 2b 31 5d 3b 0a 20 20 20 20 2a 70 6e 44  erm+1];.    *pnD
2d60: 6f 63 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74  oclist = p->nDat
2d70: 61 20 2d 20 28 73 69 7a 65 6f 66 28 2a 70 29 20  a - (sizeof(*p) 
2d80: 2b 20 6e 54 65 72 6d 20 2b 20 31 29 3b 0a 20 20  + nTerm + 1);.  
2d90: 7d 65 6c 73 65 7b 0a 20 20 20 20 2a 70 70 44 6f  }else{.    *ppDo
2da0: 63 6c 69 73 74 20 3d 20 30 3b 0a 20 20 20 20 2a  clist = 0;.    *
2db0: 70 6e 44 6f 63 6c 69 73 74 20 3d 20 30 3b 0a 20  pnDoclist = 0;. 
2dc0: 20 7d 0a 0a 20 20 72 65 74 75 72 6e 20 53 51 4c   }..  return SQL
2dd0: 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 76 6f 69 64 20  ITE_OK;.}..void 
2de0: 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 53  sqlite3Fts5HashS
2df0: 63 61 6e 49 6e 69 74 28 0a 20 20 46 74 73 35 48  canInit(.  Fts5H
2e00: 61 73 68 20 2a 70 2c 20 20 20 20 20 20 20 20 20  ash *p,         
2e10: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 48 61             /* Ha
2e20: 73 68 20 74 61 62 6c 65 20 74 6f 20 71 75 65 72  sh table to quer
2e30: 79 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61  y */.  const cha
2e40: 72 20 2a 70 54 65 72 6d 2c 20 69 6e 74 20 6e 54  r *pTerm, int nT
2e50: 65 72 6d 20 20 20 20 2f 2a 20 51 75 65 72 79 20  erm    /* Query 
2e60: 70 72 65 66 69 78 20 2a 2f 0a 29 7b 0a 20 20 66  prefix */.){.  f
2e70: 74 73 35 48 61 73 68 45 6e 74 72 79 53 6f 72 74  ts5HashEntrySort
2e80: 28 70 2c 20 70 54 65 72 6d 2c 20 6e 54 65 72 6d  (p, pTerm, nTerm
2e90: 2c 20 26 70 2d 3e 70 53 63 61 6e 29 3b 0a 7d 0a  , &p->pScan);.}.
2ea0: 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 46 74 73  .void sqlite3Fts
2eb0: 35 48 61 73 68 53 63 61 6e 4e 65 78 74 28 46 74  5HashScanNext(Ft
2ec0: 73 35 48 61 73 68 20 2a 70 29 7b 0a 20 20 46 74  s5Hash *p){.  Ft
2ed0: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 53 63  s5HashEntry *pSc
2ee0: 61 6e 20 3d 20 70 2d 3e 70 53 63 61 6e 3b 0a 20  an = p->pScan;. 
2ef0: 20 69 66 28 20 70 53 63 61 6e 20 29 20 70 2d 3e   if( pScan ) p->
2f00: 70 53 63 61 6e 20 3d 20 70 53 63 61 6e 2d 3e 70  pScan = pScan->p
2f10: 53 63 61 6e 4e 65 78 74 3b 0a 7d 0a 0a 69 6e 74  ScanNext;.}..int
2f20: 20 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68   sqlite3Fts5Hash
2f30: 53 63 61 6e 45 6f 66 28 46 74 73 35 48 61 73 68  ScanEof(Fts5Hash
2f40: 20 2a 70 29 7b 0a 20 20 72 65 74 75 72 6e 20 28   *p){.  return (
2f50: 70 2d 3e 70 53 63 61 6e 3d 3d 30 29 3b 0a 7d 0a  p->pScan==0);.}.
2f60: 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 46 74 73  .void sqlite3Fts
2f70: 35 48 61 73 68 53 63 61 6e 45 6e 74 72 79 28 0a  5HashScanEntry(.
2f80: 20 20 46 74 73 35 48 61 73 68 20 2a 70 48 61 73    Fts5Hash *pHas
2f90: 68 2c 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20  h,.  const char 
2fa0: 2a 2a 70 7a 54 65 72 6d 2c 20 20 20 20 20 20 20  **pzTerm,       
2fb0: 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20 74 65 72       /* OUT: ter
2fc0: 6d 20 28 6e 75 6c 2d 74 65 72 6d 69 6e 61 74 65  m (nul-terminate
2fd0: 64 29 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68  d) */.  const ch
2fe0: 61 72 20 2a 2a 70 70 44 6f 63 6c 69 73 74 2c 20  ar **ppDoclist, 
2ff0: 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20          /* OUT: 
3000: 70 6f 69 6e 74 65 72 20 74 6f 20 64 6f 63 6c 69  pointer to docli
3010: 73 74 20 2a 2f 0a 20 20 69 6e 74 20 2a 70 6e 44  st */.  int *pnD
3020: 6f 63 6c 69 73 74 20 20 20 20 20 20 20 20 20 20  oclist          
3030: 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20          /* OUT: 
3040: 73 69 7a 65 20 6f 66 20 64 6f 63 6c 69 73 74 20  size of doclist 
3050: 69 6e 20 62 79 74 65 73 20 2a 2f 0a 29 7b 0a 20  in bytes */.){. 
3060: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
3070: 70 3b 0a 20 20 69 66 28 20 28 70 20 3d 20 70 48  p;.  if( (p = pH
3080: 61 73 68 2d 3e 70 53 63 61 6e 29 20 29 7b 0a 20  ash->pScan) ){. 
3090: 20 20 20 69 6e 74 20 6e 54 65 72 6d 20 3d 20 73     int nTerm = s
30a0: 74 72 6c 65 6e 28 70 2d 3e 7a 4b 65 79 29 3b 0a  trlen(p->zKey);.
30b0: 20 20 20 20 66 74 73 35 48 61 73 68 41 64 64 50      fts5HashAddP
30c0: 6f 73 6c 69 73 74 53 69 7a 65 28 70 29 3b 0a 20  oslistSize(p);. 
30d0: 20 20 20 2a 70 7a 54 65 72 6d 20 3d 20 70 2d 3e     *pzTerm = p->
30e0: 7a 4b 65 79 3b 0a 20 20 20 20 2a 70 70 44 6f 63  zKey;.    *ppDoc
30f0: 6c 69 73 74 20 3d 20 26 70 2d 3e 7a 4b 65 79 5b  list = &p->zKey[
3100: 6e 54 65 72 6d 2b 31 5d 3b 0a 20 20 20 20 2a 70  nTerm+1];.    *p
3110: 6e 44 6f 63 6c 69 73 74 20 3d 20 70 2d 3e 6e 44  nDoclist = p->nD
3120: 61 74 61 20 2d 20 28 73 69 7a 65 6f 66 28 2a 70  ata - (sizeof(*p
3130: 29 20 2b 20 6e 54 65 72 6d 20 2b 20 31 29 3b 0a  ) + nTerm + 1);.
3140: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2a 70 7a    }else{.    *pz
3150: 54 65 72 6d 20 3d 20 30 3b 0a 20 20 20 20 2a 70  Term = 0;.    *p
3160: 70 44 6f 63 6c 69 73 74 20 3d 20 30 3b 0a 20 20  pDoclist = 0;.  
3170: 20 20 2a 70 6e 44 6f 63 6c 69 73 74 20 3d 20 30    *pnDoclist = 0
3180: 3b 0a 20 20 7d 0a 7d 0a 0a                       ;.  }.}..