/ Hex Artifact Content
Login

Artifact 6bc0f78cb3630c5ff27dbfb58847758e82c3d0ac:


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 66 64 65 66 20 53 51 4c 49 54 45 5f 45 4e  #ifdef SQLITE_EN
0190: 41 42 4c 45 5f 46 54 53 35 0a 0a 0a 23 69 6e 63  ABLE_FTS5...#inc
01a0: 6c 75 64 65 20 22 66 74 73 35 49 6e 74 2e 68 22  lude "fts5Int.h"
01b0: 0a 0a 74 79 70 65 64 65 66 20 73 74 72 75 63 74  ..typedef struct
01c0: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 46   Fts5HashEntry F
01d0: 74 73 35 48 61 73 68 45 6e 74 72 79 3b 0a 0a 2f  ts5HashEntry;../
01e0: 2a 0a 2a 2a 20 54 68 69 73 20 66 69 6c 65 20 63  *.** This file c
01f0: 6f 6e 74 61 69 6e 73 20 74 68 65 20 69 6d 70 6c  ontains the impl
0200: 65 6d 65 6e 74 61 74 69 6f 6e 20 6f 66 20 61 6e  ementation of an
0210: 20 69 6e 2d 6d 65 6d 6f 72 79 20 68 61 73 68 20   in-memory hash 
0220: 74 61 62 6c 65 20 75 73 65 64 0a 2a 2a 20 74 6f  table used.** to
0230: 20 61 63 63 75 6d 75 6c 75 61 74 65 20 22 74 65   accumuluate "te
0240: 72 6d 20 2d 3e 20 64 6f 63 6c 69 73 74 22 20 63  rm -> doclist" c
0250: 6f 6e 74 65 6e 74 20 62 65 66 6f 72 65 20 69 74  ontent before it
0260: 20 69 73 20 66 6c 75 73 65 64 20 74 6f 20 61 20   is flused to a 
0270: 6c 65 76 65 6c 2d 30 0a 2a 2a 20 73 65 67 6d 65  level-0.** segme
0280: 6e 74 2e 0a 2a 2f 0a 0a 0a 73 74 72 75 63 74 20  nt..*/...struct 
0290: 46 74 73 35 48 61 73 68 20 7b 0a 20 20 69 6e 74  Fts5Hash {.  int
02a0: 20 2a 70 6e 42 79 74 65 3b 20 20 20 20 20 20 20   *pnByte;       
02b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
02c0: 50 6f 69 6e 74 65 72 20 74 6f 20 62 79 74 65 73  Pointer to bytes
02d0: 20 63 6f 75 6e 74 65 72 20 2a 2f 0a 20 20 69 6e   counter */.  in
02e0: 74 20 6e 45 6e 74 72 79 3b 20 20 20 20 20 20 20  t nEntry;       
02f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
0300: 20 4e 75 6d 62 65 72 20 6f 66 20 65 6e 74 72 69   Number of entri
0310: 65 73 20 63 75 72 72 65 6e 74 6c 79 20 69 6e 20  es currently in 
0320: 68 61 73 68 20 2a 2f 0a 20 20 69 6e 74 20 6e 53  hash */.  int nS
0330: 6c 6f 74 3b 20 20 20 20 20 20 20 20 20 20 20 20  lot;            
0340: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 53 69 7a            /* Siz
0350: 65 20 6f 66 20 61 53 6c 6f 74 5b 5d 20 61 72 72  e of aSlot[] arr
0360: 61 79 20 2a 2f 0a 20 20 46 74 73 35 48 61 73 68  ay */.  Fts5Hash
0370: 45 6e 74 72 79 20 2a 70 53 63 61 6e 3b 20 20 20  Entry *pScan;   
0380: 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72 72 65          /* Curre
0390: 6e 74 20 6f 72 64 65 72 65 64 20 73 63 61 6e 20  nt ordered scan 
03a0: 69 74 65 6d 20 2a 2f 0a 20 20 46 74 73 35 48 61  item */.  Fts5Ha
03b0: 73 68 45 6e 74 72 79 20 2a 2a 61 53 6c 6f 74 3b  shEntry **aSlot;
03c0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41 72 72            /* Arr
03d0: 61 79 20 6f 66 20 68 61 73 68 20 73 6c 6f 74 73  ay of hash slots
03e0: 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 45 61   */.};../*.** Ea
03f0: 63 68 20 65 6e 74 72 79 20 69 6e 20 74 68 65 20  ch entry in the 
0400: 68 61 73 68 20 74 61 62 6c 65 20 69 73 20 72 65  hash table is re
0410: 70 72 65 73 65 6e 74 65 64 20 62 79 20 61 6e 20  presented by an 
0420: 6f 62 6a 65 63 74 20 6f 66 20 74 68 65 20 0a 2a  object of the .*
0430: 2a 20 66 6f 6c 6c 6f 77 69 6e 67 20 74 79 70 65  * following type
0440: 2e 20 45 61 63 68 20 6f 62 6a 65 63 74 2c 20 69  . Each object, i
0450: 74 73 20 6b 65 79 20 28 7a 4b 65 79 5b 5d 29 20  ts key (zKey[]) 
0460: 61 6e 64 20 69 74 73 20 63 75 72 72 65 6e 74 20  and its current 
0470: 64 61 74 61 0a 2a 2a 20 61 72 65 20 73 74 6f 72  data.** are stor
0480: 65 64 20 69 6e 20 61 20 73 69 6e 67 6c 65 20 6d  ed in a single m
0490: 65 6d 6f 72 79 20 61 6c 6c 6f 63 61 74 69 6f 6e  emory allocation
04a0: 2e 20 54 68 65 20 70 6f 73 69 74 69 6f 6e 20 6c  . The position l
04b0: 69 73 74 20 64 61 74 61 20 0a 2a 2a 20 69 6d 6d  ist data .** imm
04c0: 65 64 69 61 74 65 6c 79 20 66 6f 6c 6c 6f 77 73  ediately follows
04d0: 20 74 68 65 20 6b 65 79 20 64 61 74 61 20 69 6e   the key data in
04e0: 20 6d 65 6d 6f 72 79 2e 0a 2a 2a 0a 2a 2a 20 54   memory..**.** T
04f0: 68 65 20 64 61 74 61 20 74 68 61 74 20 66 6f 6c  he data that fol
0500: 6c 6f 77 73 20 74 68 65 20 6b 65 79 20 69 73 20  lows the key is 
0510: 69 6e 20 61 20 73 69 6d 69 6c 61 72 2c 20 62 75  in a similar, bu
0520: 74 20 6e 6f 74 20 69 64 65 6e 74 69 63 61 6c 20  t not identical 
0530: 66 6f 72 6d 61 74 0a 2a 2a 20 74 6f 20 74 68 65  format.** to the
0540: 20 64 6f 63 6c 69 73 74 20 64 61 74 61 20 73 74   doclist data st
0550: 6f 72 65 64 20 69 6e 20 74 68 65 20 64 61 74 61  ored in the data
0560: 62 61 73 65 2e 20 49 74 20 69 73 3a 0a 2a 2a 0a  base. It is:.**.
0570: 2a 2a 20 20 20 2a 20 52 6f 77 69 64 2c 20 61 73  **   * Rowid, as
0580: 20 61 20 76 61 72 69 6e 74 0a 2a 2a 20 20 20 2a   a varint.**   *
0590: 20 50 6f 73 69 74 69 6f 6e 20 6c 69 73 74 2c 20   Position list, 
05a0: 77 69 74 68 6f 75 74 20 30 78 30 30 20 74 65 72  without 0x00 ter
05b0: 6d 69 6e 61 74 6f 72 2e 0a 2a 2a 20 20 20 2a 20  minator..**   * 
05c0: 53 69 7a 65 20 6f 66 20 70 72 65 76 69 6f 75 73  Size of previous
05d0: 20 70 6f 73 69 74 69 6f 6e 20 6c 69 73 74 20 61   position list a
05e0: 6e 64 20 72 6f 77 69 64 2c 20 61 73 20 61 20 34  nd rowid, as a 4
05f0: 20 62 79 74 65 0a 2a 2a 20 20 20 20 20 62 69 67   byte.**     big
0600: 2d 65 6e 64 69 61 6e 20 69 6e 74 65 67 65 72 2e  -endian integer.
0610: 0a 2a 2a 0a 2a 2a 20 69 52 6f 77 69 64 4f 66 66  .**.** iRowidOff
0620: 3a 0a 2a 2a 20 20 20 4f 66 66 73 65 74 20 6f 66  :.**   Offset of
0630: 20 6c 61 73 74 20 72 6f 77 69 64 20 77 72 69 74   last rowid writ
0640: 74 65 6e 20 74 6f 20 64 61 74 61 20 61 72 65 61  ten to data area
0650: 2e 20 52 65 6c 61 74 69 76 65 20 74 6f 20 66 69  . Relative to fi
0660: 72 73 74 20 62 79 74 65 20 6f 66 0a 2a 2a 20 20  rst byte of.**  
0670: 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2a 0a 2a   structure..**.*
0680: 2a 20 6e 44 61 74 61 3a 0a 2a 2a 20 20 20 42 79  * nData:.**   By
0690: 74 65 73 20 6f 66 20 64 61 74 61 20 77 72 69 74  tes of data writ
06a0: 74 65 6e 20 73 69 6e 63 65 20 69 52 6f 77 69 64  ten since iRowid
06b0: 4f 66 66 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 46  Off..*/.struct F
06c0: 74 73 35 48 61 73 68 45 6e 74 72 79 20 7b 0a 20  ts5HashEntry {. 
06d0: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
06e0: 70 48 61 73 68 4e 65 78 74 3b 20 20 20 20 20 20  pHashNext;      
06f0: 20 2f 2a 20 4e 65 78 74 20 68 61 73 68 20 65 6e   /* Next hash en
0700: 74 72 79 20 77 69 74 68 20 73 61 6d 65 20 68 61  try with same ha
0710: 73 68 2d 6b 65 79 20 2a 2f 0a 20 20 46 74 73 35  sh-key */.  Fts5
0720: 48 61 73 68 45 6e 74 72 79 20 2a 70 53 63 61 6e  HashEntry *pScan
0730: 4e 65 78 74 3b 20 20 20 20 20 20 20 2f 2a 20 4e  Next;       /* N
0740: 65 78 74 20 65 6e 74 72 79 20 69 6e 20 73 6f 72  ext entry in sor
0750: 74 65 64 20 6f 72 64 65 72 20 2a 2f 0a 20 20 0a  ted order */.  .
0760: 20 20 69 6e 74 20 6e 41 6c 6c 6f 63 3b 20 20 20    int nAlloc;   
0770: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0780: 20 20 2f 2a 20 54 6f 74 61 6c 20 73 69 7a 65 20    /* Total size 
0790: 6f 66 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 2a 2f  of allocation */
07a0: 0a 20 20 69 6e 74 20 69 53 7a 50 6f 73 6c 69 73  .  int iSzPoslis
07b0: 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  t;              
07c0: 20 20 20 2f 2a 20 4f 66 66 73 65 74 20 6f 66 20     /* Offset of 
07d0: 73 70 61 63 65 20 66 6f 72 20 34 2d 62 79 74 65  space for 4-byte
07e0: 20 70 6f 73 6c 69 73 74 20 73 69 7a 65 20 2a 2f   poslist size */
07f0: 0a 20 20 69 6e 74 20 6e 44 61 74 61 3b 20 20 20  .  int nData;   
0800: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0810: 20 20 20 2f 2a 20 54 6f 74 61 6c 20 62 79 74 65     /* Total byte
0820: 73 20 6f 66 20 64 61 74 61 20 28 69 6e 63 6c 2e  s of data (incl.
0830: 20 73 74 72 75 63 74 75 72 65 29 20 2a 2f 0a 0a   structure) */..
0840: 20 20 69 6e 74 20 69 43 6f 6c 3b 20 20 20 20 20    int iCol;     
0850: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0860: 20 20 2f 2a 20 43 6f 6c 75 6d 6e 20 6f 66 20 6c    /* Column of l
0870: 61 73 74 20 76 61 6c 75 65 20 77 72 69 74 74 65  ast value writte
0880: 6e 20 2a 2f 0a 20 20 69 6e 74 20 69 50 6f 73 3b  n */.  int iPos;
0890: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
08a0: 20 20 20 20 20 20 20 2f 2a 20 50 6f 73 69 74 69         /* Positi
08b0: 6f 6e 20 6f 66 20 6c 61 73 74 20 76 61 6c 75 65  on of last value
08c0: 20 77 72 69 74 74 65 6e 20 2a 2f 0a 20 20 69 36   written */.  i6
08d0: 34 20 69 52 6f 77 69 64 3b 20 20 20 20 20 20 20  4 iRowid;       
08e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
08f0: 20 52 6f 77 69 64 20 6f 66 20 6c 61 73 74 20 76   Rowid of last v
0900: 61 6c 75 65 20 77 72 69 74 74 65 6e 20 2a 2f 0a  alue written */.
0910: 20 20 63 68 61 72 20 7a 4b 65 79 5b 30 5d 3b 20    char zKey[0]; 
0920: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0930: 20 20 2f 2a 20 4e 75 6c 2d 74 65 72 6d 69 6e 61    /* Nul-termina
0940: 74 65 64 20 65 6e 74 72 79 20 6b 65 79 20 2a 2f  ted entry key */
0950: 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 46 6f 72 6d 61  .};../*.** Forma
0960: 74 20 76 61 6c 75 65 20 69 56 61 6c 20 61 73 20  t value iVal as 
0970: 61 20 34 2d 62 79 74 65 20 76 61 72 69 6e 74 20  a 4-byte varint 
0980: 61 6e 64 20 77 72 69 74 65 20 69 74 20 74 6f 20  and write it to 
0990: 62 75 66 66 65 72 20 61 5b 5d 2e 20 34 20 62 79  buffer a[]. 4 by
09a0: 74 65 73 0a 2a 2a 20 61 72 65 20 75 73 65 64 20  tes.** are used 
09b0: 65 76 65 6e 20 69 66 20 74 68 65 20 76 61 6c 75  even if the valu
09c0: 65 20 63 6f 75 6c 64 20 66 69 74 20 69 6e 20 61  e could fit in a
09d0: 20 73 6d 61 6c 6c 65 72 20 61 6d 6f 75 6e 74 20   smaller amount 
09e0: 6f 66 20 73 70 61 63 65 2e 20 0a 2a 2f 0a 73 74  of space. .*/.st
09f0: 61 74 69 63 20 76 6f 69 64 20 66 74 73 35 50 75  atic void fts5Pu
0a00: 74 34 42 79 74 65 56 61 72 69 6e 74 28 75 38 20  t4ByteVarint(u8 
0a10: 2a 61 2c 20 69 6e 74 20 69 56 61 6c 29 7b 0a 20  *a, int iVal){. 
0a20: 20 61 5b 30 5d 20 3d 20 28 30 78 38 30 20 7c 20   a[0] = (0x80 | 
0a30: 28 75 38 29 28 69 56 61 6c 20 3e 3e 20 32 31 29  (u8)(iVal >> 21)
0a40: 29 3b 0a 20 20 61 5b 31 5d 20 3d 20 28 30 78 38  );.  a[1] = (0x8
0a50: 30 20 7c 20 28 75 38 29 28 69 56 61 6c 20 3e 3e  0 | (u8)(iVal >>
0a60: 20 31 34 29 29 3b 0a 20 20 61 5b 32 5d 20 3d 20   14));.  a[2] = 
0a70: 28 30 78 38 30 20 7c 20 28 75 38 29 28 69 56 61  (0x80 | (u8)(iVa
0a80: 6c 20 3e 3e 20 20 37 29 29 3b 0a 20 20 61 5b 33  l >>  7));.  a[3
0a90: 5d 20 3d 20 28 30 78 37 46 20 26 20 28 75 38 29  ] = (0x7F & (u8)
0aa0: 28 69 56 61 6c 29 29 3b 0a 7d 0a 0a 73 74 61 74  (iVal));.}..stat
0ab0: 69 63 20 69 6e 74 20 66 74 73 35 47 65 74 34 42  ic int fts5Get4B
0ac0: 79 74 65 56 61 72 69 6e 74 28 75 38 20 2a 61 2c  yteVarint(u8 *a,
0ad0: 20 69 6e 74 20 2a 70 6e 56 61 72 69 6e 74 29 7b   int *pnVarint){
0ae0: 0a 20 20 69 6e 74 20 69 52 65 74 20 3d 20 28 28  .  int iRet = ((
0af0: 69 6e 74 29 28 61 5b 30 5d 20 26 20 30 78 37 46  int)(a[0] & 0x7F
0b00: 29 20 3c 3c 20 32 31 29 20 2b 20 28 28 69 6e 74  ) << 21) + ((int
0b10: 29 28 61 5b 31 5d 20 26 20 30 78 37 46 29 20 3c  )(a[1] & 0x7F) <
0b20: 3c 20 31 34 29 0a 20 20 20 20 20 20 20 2b 20 28  < 14).       + (
0b30: 28 69 6e 74 29 28 61 5b 32 5d 20 26 20 30 78 37  (int)(a[2] & 0x7
0b40: 46 29 20 3c 3c 20 20 37 29 20 2b 20 28 28 69 6e  F) <<  7) + ((in
0b50: 74 29 28 61 5b 33 5d 29 29 3b 0a 20 20 2a 70 6e  t)(a[3]));.  *pn
0b60: 56 61 72 69 6e 74 20 3d 20 28 0a 20 20 20 20 20  Varint = (.     
0b70: 20 28 69 52 65 74 20 26 20 30 78 46 46 46 46 46   (iRet & 0xFFFFF
0b80: 46 38 30 29 3d 3d 30 20 3f 20 31 20 3a 20 0a 20  F80)==0 ? 1 : . 
0b90: 20 20 20 20 20 28 69 52 65 74 20 26 20 30 78 46       (iRet & 0xF
0ba0: 46 46 46 43 30 30 30 29 3d 3d 30 20 3f 20 32 20  FFFC000)==0 ? 2 
0bb0: 3a 0a 20 20 20 20 20 20 28 69 52 65 74 20 26 20  :.      (iRet & 
0bc0: 30 78 46 46 45 30 30 30 30 30 29 3d 3d 30 20 3f  0xFFE00000)==0 ?
0bd0: 20 33 20 3a 20 34 0a 20 20 29 3b 0a 20 20 72 65   3 : 4.  );.  re
0be0: 74 75 72 6e 20 69 52 65 74 3b 0a 7d 0a 0a 2f 2a  turn iRet;.}../*
0bf0: 0a 2a 2a 20 41 6c 6c 6f 63 61 74 65 20 61 20 6e  .** Allocate a n
0c00: 65 77 20 68 61 73 68 20 74 61 62 6c 65 2e 0a 2a  ew hash table..*
0c10: 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 46 74 73  /.int sqlite3Fts
0c20: 35 48 61 73 68 4e 65 77 28 46 74 73 35 48 61 73  5HashNew(Fts5Has
0c30: 68 20 2a 2a 70 70 4e 65 77 2c 20 69 6e 74 20 2a  h **ppNew, int *
0c40: 70 6e 42 79 74 65 29 7b 0a 20 20 69 6e 74 20 72  pnByte){.  int r
0c50: 63 20 3d 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 20  c = SQLITE_OK;. 
0c60: 20 46 74 73 35 48 61 73 68 20 2a 70 4e 65 77 3b   Fts5Hash *pNew;
0c70: 0a 0a 20 20 2a 70 70 4e 65 77 20 3d 20 70 4e 65  ..  *ppNew = pNe
0c80: 77 20 3d 20 28 46 74 73 35 48 61 73 68 2a 29 73  w = (Fts5Hash*)s
0c90: 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 73 69  qlite3_malloc(si
0ca0: 7a 65 6f 66 28 46 74 73 35 48 61 73 68 29 29 3b  zeof(Fts5Hash));
0cb0: 0a 20 20 69 66 28 20 70 4e 65 77 3d 3d 30 20 29  .  if( pNew==0 )
0cc0: 7b 0a 20 20 20 20 72 63 20 3d 20 53 51 4c 49 54  {.    rc = SQLIT
0cd0: 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 7d 65 6c 73 65  E_NOMEM;.  }else
0ce0: 7b 0a 20 20 20 20 69 6e 74 20 6e 42 79 74 65 3b  {.    int nByte;
0cf0: 0a 20 20 20 20 6d 65 6d 73 65 74 28 70 4e 65 77  .    memset(pNew
0d00: 2c 20 30 2c 20 73 69 7a 65 6f 66 28 46 74 73 35  , 0, sizeof(Fts5
0d10: 48 61 73 68 29 29 3b 0a 20 20 20 20 70 4e 65 77  Hash));.    pNew
0d20: 2d 3e 70 6e 42 79 74 65 20 3d 20 70 6e 42 79 74  ->pnByte = pnByt
0d30: 65 3b 0a 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 53  e;..    pNew->nS
0d40: 6c 6f 74 20 3d 20 31 30 32 34 3b 0a 20 20 20 20  lot = 1024;.    
0d50: 6e 42 79 74 65 20 3d 20 73 69 7a 65 6f 66 28 46  nByte = sizeof(F
0d60: 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29 20 2a  ts5HashEntry*) *
0d70: 20 70 4e 65 77 2d 3e 6e 53 6c 6f 74 3b 0a 20 20   pNew->nSlot;.  
0d80: 20 20 70 4e 65 77 2d 3e 61 53 6c 6f 74 20 3d 20    pNew->aSlot = 
0d90: 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 2a  (Fts5HashEntry**
0da0: 29 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28  )sqlite3_malloc(
0db0: 6e 42 79 74 65 29 3b 0a 20 20 20 20 69 66 28 20  nByte);.    if( 
0dc0: 70 4e 65 77 2d 3e 61 53 6c 6f 74 3d 3d 30 20 29  pNew->aSlot==0 )
0dd0: 7b 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33 5f  {.      sqlite3_
0de0: 66 72 65 65 28 70 4e 65 77 29 3b 0a 20 20 20 20  free(pNew);.    
0df0: 20 20 2a 70 70 4e 65 77 20 3d 20 30 3b 0a 20 20    *ppNew = 0;.  
0e00: 20 20 20 20 72 63 20 3d 20 53 51 4c 49 54 45 5f      rc = SQLITE_
0e10: 4e 4f 4d 45 4d 3b 0a 20 20 20 20 7d 65 6c 73 65  NOMEM;.    }else
0e20: 7b 0a 20 20 20 20 20 20 6d 65 6d 73 65 74 28 70  {.      memset(p
0e30: 4e 65 77 2d 3e 61 53 6c 6f 74 2c 20 30 2c 20 6e  New->aSlot, 0, n
0e40: 42 79 74 65 29 3b 0a 20 20 20 20 7d 0a 20 20 7d  Byte);.    }.  }
0e50: 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a  .  return rc;.}.
0e60: 0a 2f 2a 0a 2a 2a 20 46 72 65 65 20 61 20 68 61  ./*.** Free a ha
0e70: 73 68 20 74 61 62 6c 65 20 6f 62 6a 65 63 74 2e  sh table object.
0e80: 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74 65 33  .*/.void sqlite3
0e90: 46 74 73 35 48 61 73 68 46 72 65 65 28 46 74 73  Fts5HashFree(Fts
0ea0: 35 48 61 73 68 20 2a 70 48 61 73 68 29 7b 0a 20  5Hash *pHash){. 
0eb0: 20 69 66 28 20 70 48 61 73 68 20 29 7b 0a 20 20   if( pHash ){.  
0ec0: 20 20 73 71 6c 69 74 65 33 46 74 73 35 48 61 73    sqlite3Fts5Has
0ed0: 68 43 6c 65 61 72 28 70 48 61 73 68 29 3b 0a 20  hClear(pHash);. 
0ee0: 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28     sqlite3_free(
0ef0: 70 48 61 73 68 2d 3e 61 53 6c 6f 74 29 3b 0a 20  pHash->aSlot);. 
0f00: 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28     sqlite3_free(
0f10: 70 48 61 73 68 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f  pHash);.  }.}../
0f20: 2a 0a 2a 2a 20 45 6d 70 74 79 20 28 62 75 74 20  *.** Empty (but 
0f30: 64 6f 20 6e 6f 74 20 64 65 6c 65 74 65 29 20 61  do not delete) a
0f40: 20 68 61 73 68 20 74 61 62 6c 65 2e 0a 2a 2f 0a   hash table..*/.
0f50: 76 6f 69 64 20 73 71 6c 69 74 65 33 46 74 73 35  void sqlite3Fts5
0f60: 48 61 73 68 43 6c 65 61 72 28 46 74 73 35 48 61  HashClear(Fts5Ha
0f70: 73 68 20 2a 70 48 61 73 68 29 7b 0a 20 20 69 6e  sh *pHash){.  in
0f80: 74 20 69 3b 0a 20 20 66 6f 72 28 69 3d 30 3b 20  t i;.  for(i=0; 
0f90: 69 3c 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 3b 20  i<pHash->nSlot; 
0fa0: 69 2b 2b 29 7b 0a 20 20 20 20 46 74 73 35 48 61  i++){.    Fts5Ha
0fb0: 73 68 45 6e 74 72 79 20 2a 70 4e 65 78 74 3b 0a  shEntry *pNext;.
0fc0: 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74 72      Fts5HashEntr
0fd0: 79 20 2a 70 53 6c 6f 74 3b 0a 20 20 20 20 66 6f  y *pSlot;.    fo
0fe0: 72 28 70 53 6c 6f 74 3d 70 48 61 73 68 2d 3e 61  r(pSlot=pHash->a
0ff0: 53 6c 6f 74 5b 69 5d 3b 20 70 53 6c 6f 74 3b 20  Slot[i]; pSlot; 
1000: 70 53 6c 6f 74 3d 70 4e 65 78 74 29 7b 0a 20 20  pSlot=pNext){.  
1010: 20 20 20 20 70 4e 65 78 74 20 3d 20 70 53 6c 6f      pNext = pSlo
1020: 74 2d 3e 70 48 61 73 68 4e 65 78 74 3b 0a 20 20  t->pHashNext;.  
1030: 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65      sqlite3_free
1040: 28 70 53 6c 6f 74 29 3b 0a 20 20 20 20 7d 0a 20  (pSlot);.    }. 
1050: 20 7d 0a 20 20 6d 65 6d 73 65 74 28 70 48 61 73   }.  memset(pHas
1060: 68 2d 3e 61 53 6c 6f 74 2c 20 30 2c 20 70 48 61  h->aSlot, 0, pHa
1070: 73 68 2d 3e 6e 53 6c 6f 74 20 2a 20 73 69 7a 65  sh->nSlot * size
1080: 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79  of(Fts5HashEntry
1090: 2a 29 29 3b 0a 20 20 70 48 61 73 68 2d 3e 6e 45  *));.  pHash->nE
10a0: 6e 74 72 79 20 3d 20 30 3b 0a 7d 0a 0a 73 74 61  ntry = 0;.}..sta
10b0: 74 69 63 20 75 6e 73 69 67 6e 65 64 20 69 6e 74  tic unsigned int
10c0: 20 66 74 73 35 48 61 73 68 4b 65 79 28 69 6e 74   fts5HashKey(int
10d0: 20 6e 53 6c 6f 74 2c 20 63 6f 6e 73 74 20 63 68   nSlot, const ch
10e0: 61 72 20 2a 70 2c 20 69 6e 74 20 6e 29 7b 0a 20  ar *p, int n){. 
10f0: 20 69 6e 74 20 69 3b 0a 20 20 75 6e 73 69 67 6e   int i;.  unsign
1100: 65 64 20 69 6e 74 20 68 20 3d 20 31 33 3b 0a 20  ed int h = 13;. 
1110: 20 66 6f 72 28 69 3d 6e 2d 31 3b 20 69 3e 3d 30   for(i=n-1; i>=0
1120: 3b 20 69 2d 2d 29 7b 0a 20 20 20 20 68 20 3d 20  ; i--){.    h = 
1130: 28 68 20 3c 3c 20 33 29 20 5e 20 68 20 5e 20 70  (h << 3) ^ h ^ p
1140: 5b 69 5d 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72  [i];.  }.  retur
1150: 6e 20 28 68 20 25 20 6e 53 6c 6f 74 29 3b 0a 7d  n (h % nSlot);.}
1160: 0a 0a 2f 2a 0a 2a 2a 20 52 65 73 69 7a 65 20 74  ../*.** Resize t
1170: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 62 79  he hash table by
1180: 20 64 6f 75 62 6c 69 6e 67 20 74 68 65 20 6e 75   doubling the nu
1190: 6d 62 65 72 20 6f 66 20 73 6c 6f 74 73 2e 0a 2a  mber of slots..*
11a0: 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 66 74 73  /.static int fts
11b0: 35 48 61 73 68 52 65 73 69 7a 65 28 46 74 73 35  5HashResize(Fts5
11c0: 48 61 73 68 20 2a 70 48 61 73 68 29 7b 0a 20 20  Hash *pHash){.  
11d0: 69 6e 74 20 6e 4e 65 77 20 3d 20 70 48 61 73 68  int nNew = pHash
11e0: 2d 3e 6e 53 6c 6f 74 2a 32 3b 0a 20 20 69 6e 74  ->nSlot*2;.  int
11f0: 20 69 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e   i;.  Fts5HashEn
1200: 74 72 79 20 2a 2a 61 70 4e 65 77 3b 0a 20 20 46  try **apNew;.  F
1210: 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 61  ts5HashEntry **a
1220: 70 4f 6c 64 20 3d 20 70 48 61 73 68 2d 3e 61 53  pOld = pHash->aS
1230: 6c 6f 74 3b 0a 0a 20 20 61 70 4e 65 77 20 3d 20  lot;..  apNew = 
1240: 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 2a  (Fts5HashEntry**
1250: 29 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28  )sqlite3_malloc(
1260: 6e 4e 65 77 2a 73 69 7a 65 6f 66 28 46 74 73 35  nNew*sizeof(Fts5
1270: 48 61 73 68 45 6e 74 72 79 2a 29 29 3b 0a 20 20  HashEntry*));.  
1280: 69 66 28 20 21 61 70 4e 65 77 20 29 20 72 65 74  if( !apNew ) ret
1290: 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d  urn SQLITE_NOMEM
12a0: 3b 0a 20 20 6d 65 6d 73 65 74 28 61 70 4e 65 77  ;.  memset(apNew
12b0: 2c 20 30 2c 20 6e 4e 65 77 2a 73 69 7a 65 6f 66  , 0, nNew*sizeof
12c0: 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29  (Fts5HashEntry*)
12d0: 29 3b 0a 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69  );..  for(i=0; i
12e0: 3c 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 3b 20 69  <pHash->nSlot; i
12f0: 2b 2b 29 7b 0a 20 20 20 20 77 68 69 6c 65 28 20  ++){.    while( 
1300: 61 70 4f 6c 64 5b 69 5d 20 29 7b 0a 20 20 20 20  apOld[i] ){.    
1310: 20 20 69 6e 74 20 69 48 61 73 68 3b 0a 20 20 20    int iHash;.   
1320: 20 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79     Fts5HashEntry
1330: 20 2a 70 20 3d 20 61 70 4f 6c 64 5b 69 5d 3b 0a   *p = apOld[i];.
1340: 20 20 20 20 20 20 61 70 4f 6c 64 5b 69 5d 20 3d        apOld[i] =
1350: 20 70 2d 3e 70 48 61 73 68 4e 65 78 74 3b 0a 20   p->pHashNext;. 
1360: 20 20 20 20 20 69 48 61 73 68 20 3d 20 66 74 73       iHash = fts
1370: 35 48 61 73 68 4b 65 79 28 6e 4e 65 77 2c 20 70  5HashKey(nNew, p
1380: 2d 3e 7a 4b 65 79 2c 20 73 74 72 6c 65 6e 28 70  ->zKey, strlen(p
1390: 2d 3e 7a 4b 65 79 29 29 3b 0a 20 20 20 20 20 20  ->zKey));.      
13a0: 70 2d 3e 70 48 61 73 68 4e 65 78 74 20 3d 20 61  p->pHashNext = a
13b0: 70 4e 65 77 5b 69 48 61 73 68 5d 3b 0a 20 20 20  pNew[iHash];.   
13c0: 20 20 20 61 70 4e 65 77 5b 69 48 61 73 68 5d 20     apNew[iHash] 
13d0: 3d 20 70 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a  = p;.    }.  }..
13e0: 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 61    sqlite3_free(a
13f0: 70 4f 6c 64 29 3b 0a 20 20 70 48 61 73 68 2d 3e  pOld);.  pHash->
1400: 6e 53 6c 6f 74 20 3d 20 6e 4e 65 77 3b 0a 20 20  nSlot = nNew;.  
1410: 70 48 61 73 68 2d 3e 61 53 6c 6f 74 20 3d 20 61  pHash->aSlot = a
1420: 70 4e 65 77 3b 0a 20 20 72 65 74 75 72 6e 20 53  pNew;.  return S
1430: 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 73 74 61  QLITE_OK;.}..sta
1440: 74 69 63 20 76 6f 69 64 20 66 74 73 35 48 61 73  tic void fts5Has
1450: 68 41 64 64 50 6f 73 6c 69 73 74 53 69 7a 65 28  hAddPoslistSize(
1460: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70  Fts5HashEntry *p
1470: 29 7b 0a 20 20 69 66 28 20 70 2d 3e 69 53 7a 50  ){.  if( p->iSzP
1480: 6f 73 6c 69 73 74 20 29 7b 0a 20 20 20 20 75 38  oslist ){.    u8
1490: 20 2a 70 50 74 72 20 3d 20 28 75 38 2a 29 70 3b   *pPtr = (u8*)p;
14a0: 0a 20 20 20 20 69 6e 74 20 6e 53 7a 20 3d 20 70  .    int nSz = p
14b0: 2d 3e 6e 44 61 74 61 20 2d 20 70 2d 3e 69 53 7a  ->nData - p->iSz
14c0: 50 6f 73 6c 69 73 74 20 2d 20 31 3b 0a 0a 20 20  Poslist - 1;..  
14d0: 20 20 69 66 28 20 6e 53 7a 3c 3d 31 32 37 20 29    if( nSz<=127 )
14e0: 7b 0a 20 20 20 20 20 20 70 50 74 72 5b 70 2d 3e  {.      pPtr[p->
14f0: 69 53 7a 50 6f 73 6c 69 73 74 5d 20 3d 20 6e 53  iSzPoslist] = nS
1500: 7a 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20  z;.    }else{.  
1510: 20 20 20 20 69 6e 74 20 6e 42 79 74 65 20 3d 20      int nByte = 
1520: 73 71 6c 69 74 65 33 46 74 73 35 47 65 74 56 61  sqlite3Fts5GetVa
1530: 72 69 6e 74 4c 65 6e 28 28 75 33 32 29 6e 53 7a  rintLen((u32)nSz
1540: 29 3b 0a 20 20 20 20 20 20 6d 65 6d 6d 6f 76 65  );.      memmove
1550: 28 26 70 50 74 72 5b 70 2d 3e 69 53 7a 50 6f 73  (&pPtr[p->iSzPos
1560: 6c 69 73 74 20 2b 20 6e 42 79 74 65 5d 2c 20 26  list + nByte], &
1570: 70 50 74 72 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69  pPtr[p->iSzPosli
1580: 73 74 20 2b 20 31 5d 2c 20 6e 53 7a 29 3b 0a 20  st + 1], nSz);. 
1590: 20 20 20 20 20 73 71 6c 69 74 65 33 50 75 74 56       sqlite3PutV
15a0: 61 72 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e 69  arint(&pPtr[p->i
15b0: 53 7a 50 6f 73 6c 69 73 74 5d 2c 20 6e 53 7a 29  SzPoslist], nSz)
15c0: 3b 0a 20 20 20 20 20 20 70 2d 3e 6e 44 61 74 61  ;.      p->nData
15d0: 20 2b 3d 20 28 6e 42 79 74 65 2d 31 29 3b 0a 20   += (nByte-1);. 
15e0: 20 20 20 7d 0a 20 20 20 20 70 2d 3e 69 53 7a 50     }.    p->iSzP
15f0: 6f 73 6c 69 73 74 20 3d 20 30 3b 0a 20 20 7d 0a  oslist = 0;.  }.
1600: 7d 0a 0a 69 6e 74 20 73 71 6c 69 74 65 33 46 74  }..int sqlite3Ft
1610: 73 35 48 61 73 68 57 72 69 74 65 28 0a 20 20 46  s5HashWrite(.  F
1620: 74 73 35 48 61 73 68 20 2a 70 48 61 73 68 2c 0a  ts5Hash *pHash,.
1630: 20 20 69 36 34 20 69 52 6f 77 69 64 2c 20 20 20    i64 iRowid,   
1640: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1650: 20 20 2f 2a 20 52 6f 77 69 64 20 66 6f 72 20 74    /* Rowid for t
1660: 68 69 73 20 65 6e 74 72 79 20 2a 2f 0a 20 20 69  his entry */.  i
1670: 6e 74 20 69 43 6f 6c 2c 20 20 20 20 20 20 20 20  nt iCol,        
1680: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
1690: 2a 20 43 6f 6c 75 6d 6e 20 74 6f 6b 65 6e 20 61  * Column token a
16a0: 70 70 65 61 72 73 20 69 6e 20 28 2d 76 65 20 2d  ppears in (-ve -
16b0: 3e 20 64 65 6c 65 74 65 29 20 2a 2f 0a 20 20 69  > delete) */.  i
16c0: 6e 74 20 69 50 6f 73 2c 20 20 20 20 20 20 20 20  nt iPos,        
16d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
16e0: 2a 20 50 6f 73 69 74 69 6f 6e 20 6f 66 20 74 6f  * Position of to
16f0: 6b 65 6e 20 77 69 74 68 69 6e 20 63 6f 6c 75 6d  ken within colum
1700: 6e 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61  n */.  const cha
1710: 72 20 2a 70 54 6f 6b 65 6e 2c 20 69 6e 74 20 6e  r *pToken, int n
1720: 54 6f 6b 65 6e 20 20 2f 2a 20 54 6f 6b 65 6e 20  Token  /* Token 
1730: 74 6f 20 61 64 64 20 6f 72 20 72 65 6d 6f 76 65  to add or remove
1740: 20 74 6f 20 6f 72 20 66 72 6f 6d 20 69 6e 64 65   to or from inde
1750: 78 20 2a 2f 0a 29 7b 0a 20 20 75 6e 73 69 67 6e  x */.){.  unsign
1760: 65 64 20 69 6e 74 20 69 48 61 73 68 20 3d 20 66  ed int iHash = f
1770: 74 73 35 48 61 73 68 4b 65 79 28 70 48 61 73 68  ts5HashKey(pHash
1780: 2d 3e 6e 53 6c 6f 74 2c 20 70 54 6f 6b 65 6e 2c  ->nSlot, pToken,
1790: 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 46 74 73 35   nToken);.  Fts5
17a0: 48 61 73 68 45 6e 74 72 79 20 2a 70 3b 0a 20 20  HashEntry *p;.  
17b0: 75 38 20 2a 70 50 74 72 3b 0a 20 20 69 6e 74 20  u8 *pPtr;.  int 
17c0: 6e 49 6e 63 72 20 3d 20 30 3b 20 20 20 20 20 20  nIncr = 0;      
17d0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41              /* A
17e0: 6d 6f 75 6e 74 20 74 6f 20 69 6e 63 72 65 6d 65  mount to increme
17f0: 6e 74 20 28 2a 70 48 61 73 68 2d 3e 70 6e 42 79  nt (*pHash->pnBy
1800: 74 65 29 20 62 79 20 2a 2f 0a 0a 20 20 2f 2a 20  te) by */..  /* 
1810: 41 74 74 65 6d 70 74 20 74 6f 20 6c 6f 63 61 74  Attempt to locat
1820: 65 20 61 6e 20 65 78 69 73 74 69 6e 67 20 68 61  e an existing ha
1830: 73 68 20 65 6e 74 72 79 20 2a 2f 0a 20 20 66 6f  sh entry */.  fo
1840: 72 28 70 3d 70 48 61 73 68 2d 3e 61 53 6c 6f 74  r(p=pHash->aSlot
1850: 5b 69 48 61 73 68 5d 3b 20 70 3b 20 70 3d 70 2d  [iHash]; p; p=p-
1860: 3e 70 48 61 73 68 4e 65 78 74 29 7b 0a 20 20 20  >pHashNext){.   
1870: 20 69 66 28 20 6d 65 6d 63 6d 70 28 70 2d 3e 7a   if( memcmp(p->z
1880: 4b 65 79 2c 20 70 54 6f 6b 65 6e 2c 20 6e 54 6f  Key, pToken, nTo
1890: 6b 65 6e 29 3d 3d 30 20 26 26 20 70 2d 3e 7a 4b  ken)==0 && p->zK
18a0: 65 79 5b 6e 54 6f 6b 65 6e 5d 3d 3d 30 20 29 20  ey[nToken]==0 ) 
18b0: 62 72 65 61 6b 3b 0a 20 20 7d 0a 0a 20 20 2f 2a  break;.  }..  /*
18c0: 20 49 66 20 61 6e 20 65 78 69 73 74 69 6e 67 20   If an existing 
18d0: 68 61 73 68 20 65 6e 74 72 79 20 63 61 6e 6e 6f  hash entry canno
18e0: 74 20 62 65 20 66 6f 75 6e 64 2c 20 63 72 65 61  t be found, crea
18f0: 74 65 20 61 20 6e 65 77 20 6f 6e 65 2e 20 2a 2f  te a new one. */
1900: 0a 20 20 69 66 28 20 70 3d 3d 30 20 29 7b 0a 20  .  if( p==0 ){. 
1910: 20 20 20 69 6e 74 20 6e 42 79 74 65 20 3d 20 73     int nByte = s
1920: 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e  izeof(Fts5HashEn
1930: 74 72 79 29 20 2b 20 6e 54 6f 6b 65 6e 20 2b 20  try) + nToken + 
1940: 31 20 2b 20 36 34 3b 0a 20 20 20 20 69 66 28 20  1 + 64;.    if( 
1950: 6e 42 79 74 65 3c 31 32 38 20 29 20 6e 42 79 74  nByte<128 ) nByt
1960: 65 20 3d 20 31 32 38 3b 0a 0a 20 20 20 20 69 66  e = 128;..    if
1970: 28 20 28 70 48 61 73 68 2d 3e 6e 45 6e 74 72 79  ( (pHash->nEntry
1980: 2a 32 29 3e 3d 70 48 61 73 68 2d 3e 6e 53 6c 6f  *2)>=pHash->nSlo
1990: 74 20 29 7b 0a 20 20 20 20 20 20 69 6e 74 20 72  t ){.      int r
19a0: 63 20 3d 20 66 74 73 35 48 61 73 68 52 65 73 69  c = fts5HashResi
19b0: 7a 65 28 70 48 61 73 68 29 3b 0a 20 20 20 20 20  ze(pHash);.     
19c0: 20 69 66 28 20 72 63 21 3d 53 51 4c 49 54 45 5f   if( rc!=SQLITE_
19d0: 4f 4b 20 29 20 72 65 74 75 72 6e 20 72 63 3b 0a  OK ) return rc;.
19e0: 20 20 20 20 20 20 69 48 61 73 68 20 3d 20 66 74        iHash = ft
19f0: 73 35 48 61 73 68 4b 65 79 28 70 48 61 73 68 2d  s5HashKey(pHash-
1a00: 3e 6e 53 6c 6f 74 2c 20 70 54 6f 6b 65 6e 2c 20  >nSlot, pToken, 
1a10: 6e 54 6f 6b 65 6e 29 3b 0a 20 20 20 20 7d 0a 0a  nToken);.    }..
1a20: 20 20 20 20 70 20 3d 20 28 46 74 73 35 48 61 73      p = (Fts5Has
1a30: 68 45 6e 74 72 79 2a 29 73 71 6c 69 74 65 33 5f  hEntry*)sqlite3_
1a40: 6d 61 6c 6c 6f 63 28 6e 42 79 74 65 29 3b 0a 20  malloc(nByte);. 
1a50: 20 20 20 69 66 28 20 21 70 20 29 20 72 65 74 75     if( !p ) retu
1a60: 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b  rn SQLITE_NOMEM;
1a70: 0a 20 20 20 20 6d 65 6d 73 65 74 28 70 2c 20 30  .    memset(p, 0
1a80: 2c 20 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73  , sizeof(Fts5Has
1a90: 68 45 6e 74 72 79 29 29 3b 0a 20 20 20 20 70 2d  hEntry));.    p-
1aa0: 3e 6e 41 6c 6c 6f 63 20 3d 20 6e 42 79 74 65 3b  >nAlloc = nByte;
1ab0: 0a 20 20 20 20 6d 65 6d 63 70 79 28 70 2d 3e 7a  .    memcpy(p->z
1ac0: 4b 65 79 2c 20 70 54 6f 6b 65 6e 2c 20 6e 54 6f  Key, pToken, nTo
1ad0: 6b 65 6e 29 3b 0a 20 20 20 20 70 2d 3e 7a 4b 65  ken);.    p->zKe
1ae0: 79 5b 6e 54 6f 6b 65 6e 5d 20 3d 20 27 5c 30 27  y[nToken] = '\0'
1af0: 3b 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 3d  ;.    p->nData =
1b00: 20 6e 54 6f 6b 65 6e 20 2b 20 31 20 2b 20 73 69   nToken + 1 + si
1b10: 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74  zeof(Fts5HashEnt
1b20: 72 79 29 3b 0a 20 20 20 20 70 2d 3e 6e 44 61 74  ry);.    p->nDat
1b30: 61 20 2b 3d 20 73 71 6c 69 74 65 33 50 75 74 56  a += sqlite3PutV
1b40: 61 72 69 6e 74 28 26 28 28 75 38 2a 29 70 29 5b  arint(&((u8*)p)[
1b50: 70 2d 3e 6e 44 61 74 61 5d 2c 20 69 52 6f 77 69  p->nData], iRowi
1b60: 64 29 3b 0a 20 20 20 20 70 2d 3e 69 53 7a 50 6f  d);.    p->iSzPo
1b70: 73 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74 61  slist = p->nData
1b80: 3b 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b  ;.    p->nData +
1b90: 3d 20 31 3b 0a 20 20 20 20 70 2d 3e 69 52 6f 77  = 1;.    p->iRow
1ba0: 69 64 20 3d 20 69 52 6f 77 69 64 3b 0a 20 20 20  id = iRowid;.   
1bb0: 20 70 2d 3e 70 48 61 73 68 4e 65 78 74 20 3d 20   p->pHashNext = 
1bc0: 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 48 61  pHash->aSlot[iHa
1bd0: 73 68 5d 3b 0a 20 20 20 20 70 48 61 73 68 2d 3e  sh];.    pHash->
1be0: 61 53 6c 6f 74 5b 69 48 61 73 68 5d 20 3d 20 70  aSlot[iHash] = p
1bf0: 3b 0a 20 20 20 20 70 48 61 73 68 2d 3e 6e 45 6e  ;.    pHash->nEn
1c00: 74 72 79 2b 2b 3b 0a 20 20 20 20 6e 49 6e 63 72  try++;.    nIncr
1c10: 20 2b 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20 20   += p->nData;.  
1c20: 7d 0a 0a 20 20 2f 2a 20 43 68 65 63 6b 20 74 68  }..  /* Check th
1c30: 65 72 65 20 69 73 20 65 6e 6f 75 67 68 20 73 70  ere is enough sp
1c40: 61 63 65 20 74 6f 20 61 70 70 65 6e 64 20 61 20  ace to append a 
1c50: 6e 65 77 20 65 6e 74 72 79 2e 20 57 6f 72 73 74  new entry. Worst
1c60: 20 63 61 73 65 20 73 63 65 6e 61 72 69 6f 0a 20   case scenario. 
1c70: 20 2a 2a 20 69 73 3a 0a 20 20 2a 2a 0a 20 20 2a   ** is:.  **.  *
1c80: 2a 20 20 20 20 20 2b 20 39 20 62 79 74 65 73 20  *     + 9 bytes 
1c90: 66 6f 72 20 61 20 6e 65 77 20 72 6f 77 69 64 2c  for a new rowid,
1ca0: 0a 20 20 2a 2a 20 20 20 20 20 2b 20 34 20 62 79  .  **     + 4 by
1cb0: 74 65 20 72 65 73 65 72 76 65 64 20 66 6f 72 20  te reserved for 
1cc0: 74 68 65 20 22 70 6f 73 6c 69 73 74 20 73 69 7a  the "poslist siz
1cd0: 65 22 20 76 61 72 69 6e 74 2e 0a 20 20 2a 2a 20  e" varint..  ** 
1ce0: 20 20 20 20 2b 20 31 20 62 79 74 65 20 66 6f 72      + 1 byte for
1cf0: 20 61 20 22 6e 65 77 20 63 6f 6c 75 6d 6e 22 20   a "new column" 
1d00: 62 79 74 65 2c 0a 20 20 2a 2a 20 20 20 20 20 2b  byte,.  **     +
1d10: 20 33 20 62 79 74 65 73 20 66 6f 72 20 61 20 6e   3 bytes for a n
1d20: 65 77 20 63 6f 6c 75 6d 6e 20 6e 75 6d 62 65 72  ew column number
1d30: 20 28 31 36 2d 62 69 74 20 6d 61 78 29 20 61 73   (16-bit max) as
1d40: 20 61 20 76 61 72 69 6e 74 2c 0a 20 20 2a 2a 20   a varint,.  ** 
1d50: 20 20 20 20 2b 20 35 20 62 79 74 65 73 20 66 6f      + 5 bytes fo
1d60: 72 20 74 68 65 20 6e 65 77 20 70 6f 73 69 74 69  r the new positi
1d70: 6f 6e 20 6f 66 66 73 65 74 20 28 33 32 2d 62 69  on offset (32-bi
1d80: 74 20 6d 61 78 29 2e 0a 20 20 2a 2f 0a 20 20 69  t max)..  */.  i
1d90: 66 28 20 28 70 2d 3e 6e 41 6c 6c 6f 63 20 2d 20  f( (p->nAlloc - 
1da0: 70 2d 3e 6e 44 61 74 61 29 20 3c 20 28 39 20 2b  p->nData) < (9 +
1db0: 20 34 20 2b 20 31 20 2b 20 33 20 2b 20 35 29 20   4 + 1 + 3 + 5) 
1dc0: 29 7b 0a 20 20 20 20 69 6e 74 20 6e 4e 65 77 20  ){.    int nNew 
1dd0: 3d 20 70 2d 3e 6e 41 6c 6c 6f 63 20 2a 20 32 3b  = p->nAlloc * 2;
1de0: 0a 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74  .    Fts5HashEnt
1df0: 72 79 20 2a 70 4e 65 77 3b 0a 20 20 20 20 46 74  ry *pNew;.    Ft
1e00: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 70 70  s5HashEntry **pp
1e10: 3b 0a 20 20 20 20 70 4e 65 77 20 3d 20 28 46 74  ;.    pNew = (Ft
1e20: 73 35 48 61 73 68 45 6e 74 72 79 2a 29 73 71 6c  s5HashEntry*)sql
1e30: 69 74 65 33 5f 72 65 61 6c 6c 6f 63 28 70 2c 20  ite3_realloc(p, 
1e40: 6e 4e 65 77 29 3b 0a 20 20 20 20 69 66 28 20 70  nNew);.    if( p
1e50: 4e 65 77 3d 3d 30 20 29 20 72 65 74 75 72 6e 20  New==0 ) return 
1e60: 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20  SQLITE_NOMEM;.  
1e70: 20 20 70 4e 65 77 2d 3e 6e 41 6c 6c 6f 63 20 3d    pNew->nAlloc =
1e80: 20 6e 4e 65 77 3b 0a 20 20 20 20 66 6f 72 28 70   nNew;.    for(p
1e90: 70 3d 26 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b  p=&pHash->aSlot[
1ea0: 69 48 61 73 68 5d 3b 20 2a 70 70 21 3d 70 3b 20  iHash]; *pp!=p; 
1eb0: 70 70 3d 26 28 2a 70 70 29 2d 3e 70 48 61 73 68  pp=&(*pp)->pHash
1ec0: 4e 65 78 74 29 3b 0a 20 20 20 20 2a 70 70 20 3d  Next);.    *pp =
1ed0: 20 70 4e 65 77 3b 0a 20 20 20 20 70 20 3d 20 70   pNew;.    p = p
1ee0: 4e 65 77 3b 0a 20 20 7d 0a 20 20 70 50 74 72 20  New;.  }.  pPtr 
1ef0: 3d 20 28 75 38 2a 29 70 3b 0a 20 20 6e 49 6e 63  = (u8*)p;.  nInc
1f00: 72 20 2d 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 0a  r -= p->nData;..
1f10: 20 20 2f 2a 20 49 66 20 74 68 69 73 20 69 73 20    /* If this is 
1f20: 61 20 6e 65 77 20 72 6f 77 69 64 2c 20 61 70 70  a new rowid, app
1f30: 65 6e 64 20 74 68 65 20 34 2d 62 79 74 65 20 73  end the 4-byte s
1f40: 69 7a 65 20 66 69 65 6c 64 20 66 6f 72 20 74 68  ize field for th
1f50: 65 20 70 72 65 76 69 6f 75 73 0a 20 20 2a 2a 20  e previous.  ** 
1f60: 65 6e 74 72 79 2c 20 61 6e 64 20 74 68 65 20 6e  entry, and the n
1f70: 65 77 20 72 6f 77 69 64 20 66 6f 72 20 74 68 69  ew rowid for thi
1f80: 73 20 65 6e 74 72 79 2e 20 20 2a 2f 0a 20 20 69  s entry.  */.  i
1f90: 66 28 20 69 52 6f 77 69 64 21 3d 70 2d 3e 69 52  f( iRowid!=p->iR
1fa0: 6f 77 69 64 20 29 7b 0a 20 20 20 20 66 74 73 35  owid ){.    fts5
1fb0: 48 61 73 68 41 64 64 50 6f 73 6c 69 73 74 53 69  HashAddPoslistSi
1fc0: 7a 65 28 70 29 3b 0a 20 20 20 20 70 2d 3e 6e 44  ze(p);.    p->nD
1fd0: 61 74 61 20 2b 3d 20 73 71 6c 69 74 65 33 50 75  ata += sqlite3Pu
1fe0: 74 56 61 72 69 6e 74 28 26 70 50 74 72 5b 70 2d  tVarint(&pPtr[p-
1ff0: 3e 6e 44 61 74 61 5d 2c 20 69 52 6f 77 69 64 20  >nData], iRowid 
2000: 2d 20 70 2d 3e 69 52 6f 77 69 64 29 3b 0a 20 20  - p->iRowid);.  
2010: 20 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20    p->iSzPoslist 
2020: 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20 20 20 20  = p->nData;.    
2030: 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 31 3b 0a 20  p->nData += 1;. 
2040: 20 20 20 70 2d 3e 69 43 6f 6c 20 3d 20 30 3b 0a     p->iCol = 0;.
2050: 20 20 20 20 70 2d 3e 69 50 6f 73 20 3d 20 30 3b      p->iPos = 0;
2060: 0a 20 20 20 20 70 2d 3e 69 52 6f 77 69 64 20 3d  .    p->iRowid =
2070: 20 69 52 6f 77 69 64 3b 0a 20 20 7d 0a 0a 20 20   iRowid;.  }..  
2080: 69 66 28 20 69 43 6f 6c 3e 3d 30 20 29 7b 0a 20  if( iCol>=0 ){. 
2090: 20 20 20 2f 2a 20 41 70 70 65 6e 64 20 61 20 6e     /* Append a n
20a0: 65 77 20 63 6f 6c 75 6d 6e 20 76 61 6c 75 65 2c  ew column value,
20b0: 20 69 66 20 6e 65 63 65 73 73 61 72 79 20 2a 2f   if necessary */
20c0: 0a 20 20 20 20 61 73 73 65 72 74 28 20 69 43 6f  .    assert( iCo
20d0: 6c 3e 3d 70 2d 3e 69 43 6f 6c 20 29 3b 0a 20 20  l>=p->iCol );.  
20e0: 20 20 69 66 28 20 69 43 6f 6c 21 3d 70 2d 3e 69    if( iCol!=p->i
20f0: 43 6f 6c 20 29 7b 0a 20 20 20 20 20 20 70 50 74  Col ){.      pPt
2100: 72 5b 70 2d 3e 6e 44 61 74 61 2b 2b 5d 20 3d 20  r[p->nData++] = 
2110: 30 78 30 31 3b 0a 20 20 20 20 20 20 70 2d 3e 6e  0x01;.      p->n
2120: 44 61 74 61 20 2b 3d 20 73 71 6c 69 74 65 33 50  Data += sqlite3P
2130: 75 74 56 61 72 69 6e 74 28 26 70 50 74 72 5b 70  utVarint(&pPtr[p
2140: 2d 3e 6e 44 61 74 61 5d 2c 20 69 43 6f 6c 29 3b  ->nData], iCol);
2150: 0a 20 20 20 20 20 20 70 2d 3e 69 43 6f 6c 20 3d  .      p->iCol =
2160: 20 69 43 6f 6c 3b 0a 20 20 20 20 20 20 70 2d 3e   iCol;.      p->
2170: 69 50 6f 73 20 3d 20 30 3b 0a 20 20 20 20 7d 0a  iPos = 0;.    }.
2180: 0a 20 20 20 20 2f 2a 20 41 70 70 65 6e 64 20 74  .    /* Append t
2190: 68 65 20 6e 65 77 20 70 6f 73 69 74 69 6f 6e 20  he new position 
21a0: 6f 66 66 73 65 74 20 2a 2f 0a 20 20 20 20 70 2d  offset */.    p-
21b0: 3e 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69 74 65  >nData += sqlite
21c0: 33 50 75 74 56 61 72 69 6e 74 28 26 70 50 74 72  3PutVarint(&pPtr
21d0: 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20 69 50 6f 73  [p->nData], iPos
21e0: 20 2d 20 70 2d 3e 69 50 6f 73 20 2b 20 32 29 3b   - p->iPos + 2);
21f0: 0a 20 20 20 20 70 2d 3e 69 50 6f 73 20 3d 20 69  .    p->iPos = i
2200: 50 6f 73 3b 0a 20 20 7d 0a 20 20 6e 49 6e 63 72  Pos;.  }.  nIncr
2210: 20 2b 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 0a 20   += p->nData;.. 
2220: 20 2a 70 48 61 73 68 2d 3e 70 6e 42 79 74 65 20   *pHash->pnByte 
2230: 2b 3d 20 6e 49 6e 63 72 3b 0a 20 20 72 65 74 75  += nIncr;.  retu
2240: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a  rn SQLITE_OK;.}.
2250: 0a 0a 2f 2a 0a 2a 2a 20 41 72 67 75 6d 65 6e 74  ../*.** Argument
2260: 73 20 70 4c 65 66 74 20 61 6e 64 20 70 52 69 67  s pLeft and pRig
2270: 68 74 20 70 6f 69 6e 74 20 74 6f 20 6c 69 6e 6b  ht point to link
2280: 65 64 2d 6c 69 73 74 73 20 6f 66 20 68 61 73 68  ed-lists of hash
2290: 2d 65 6e 74 72 79 20 6f 62 6a 65 63 74 73 2c 0a  -entry objects,.
22a0: 2a 2a 20 65 61 63 68 20 73 6f 72 74 65 64 20 69  ** each sorted i
22b0: 6e 20 6b 65 79 20 6f 72 64 65 72 2e 20 54 68 69  n key order. Thi
22c0: 73 20 66 75 6e 63 74 69 6f 6e 20 6d 65 72 67 65  s function merge
22d0: 73 20 74 68 65 20 74 77 6f 20 6c 69 73 74 73 20  s the two lists 
22e0: 69 6e 74 6f 20 61 0a 2a 2a 20 73 69 6e 67 6c 65  into a.** single
22f0: 20 6c 69 73 74 20 61 6e 64 20 72 65 74 75 72 6e   list and return
2300: 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 69  s a pointer to i
2310: 74 73 20 66 69 72 73 74 20 65 6c 65 6d 65 6e 74  ts first element
2320: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 46 74 73 35  ..*/.static Fts5
2330: 48 61 73 68 45 6e 74 72 79 20 2a 66 74 73 35 48  HashEntry *fts5H
2340: 61 73 68 45 6e 74 72 79 4d 65 72 67 65 28 0a 20  ashEntryMerge(. 
2350: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
2360: 70 4c 65 66 74 2c 0a 20 20 46 74 73 35 48 61 73  pLeft,.  Fts5Has
2370: 68 45 6e 74 72 79 20 2a 70 52 69 67 68 74 0a 29  hEntry *pRight.)
2380: 7b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72  {.  Fts5HashEntr
2390: 79 20 2a 70 31 20 3d 20 70 4c 65 66 74 3b 0a 20  y *p1 = pLeft;. 
23a0: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
23b0: 70 32 20 3d 20 70 52 69 67 68 74 3b 0a 20 20 46  p2 = pRight;.  F
23c0: 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 52  ts5HashEntry *pR
23d0: 65 74 20 3d 20 30 3b 0a 20 20 46 74 73 35 48 61  et = 0;.  Fts5Ha
23e0: 73 68 45 6e 74 72 79 20 2a 2a 70 70 4f 75 74 20  shEntry **ppOut 
23f0: 3d 20 26 70 52 65 74 3b 0a 0a 20 20 77 68 69 6c  = &pRet;..  whil
2400: 65 28 20 70 31 20 7c 7c 20 70 32 20 29 7b 0a 20  e( p1 || p2 ){. 
2410: 20 20 20 69 66 28 20 70 31 3d 3d 30 20 29 7b 0a     if( p1==0 ){.
2420: 20 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 70        *ppOut = p
2430: 32 3b 0a 20 20 20 20 20 20 70 32 20 3d 20 30 3b  2;.      p2 = 0;
2440: 0a 20 20 20 20 7d 65 6c 73 65 20 69 66 28 20 70  .    }else if( p
2450: 32 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 2a 70  2==0 ){.      *p
2460: 70 4f 75 74 20 3d 20 70 31 3b 0a 20 20 20 20 20  pOut = p1;.     
2470: 20 70 31 20 3d 20 30 3b 0a 20 20 20 20 7d 65 6c   p1 = 0;.    }el
2480: 73 65 7b 0a 20 20 20 20 20 20 69 6e 74 20 69 20  se{.      int i 
2490: 3d 20 30 3b 0a 20 20 20 20 20 20 77 68 69 6c 65  = 0;.      while
24a0: 28 20 70 31 2d 3e 7a 4b 65 79 5b 69 5d 3d 3d 70  ( p1->zKey[i]==p
24b0: 32 2d 3e 7a 4b 65 79 5b 69 5d 20 29 20 69 2b 2b  2->zKey[i] ) i++
24c0: 3b 0a 0a 20 20 20 20 20 20 69 66 28 20 28 28 75  ;..      if( ((u
24d0: 38 29 70 31 2d 3e 7a 4b 65 79 5b 69 5d 29 3e 28  8)p1->zKey[i])>(
24e0: 28 75 38 29 70 32 2d 3e 7a 4b 65 79 5b 69 5d 29  (u8)p2->zKey[i])
24f0: 20 29 7b 0a 20 20 20 20 20 20 20 20 2f 2a 20 70   ){.        /* p
2500: 32 20 69 73 20 73 6d 61 6c 6c 65 72 20 2a 2f 0a  2 is smaller */.
2510: 20 20 20 20 20 20 20 20 2a 70 70 4f 75 74 20 3d          *ppOut =
2520: 20 70 32 3b 0a 20 20 20 20 20 20 20 20 70 70 4f   p2;.        ppO
2530: 75 74 20 3d 20 26 70 32 2d 3e 70 53 63 61 6e 4e  ut = &p2->pScanN
2540: 65 78 74 3b 0a 20 20 20 20 20 20 20 20 70 32 20  ext;.        p2 
2550: 3d 20 70 32 2d 3e 70 53 63 61 6e 4e 65 78 74 3b  = p2->pScanNext;
2560: 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20  .      }else{.  
2570: 20 20 20 20 20 20 2f 2a 20 70 31 20 69 73 20 73        /* p1 is s
2580: 6d 61 6c 6c 65 72 20 2a 2f 0a 20 20 20 20 20 20  maller */.      
2590: 20 20 2a 70 70 4f 75 74 20 3d 20 70 31 3b 0a 20    *ppOut = p1;. 
25a0: 20 20 20 20 20 20 20 70 70 4f 75 74 20 3d 20 26         ppOut = &
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 20 20 70 31 20 3d 20 70 31 2d 3e         p1 = p1->
25d0: 70 53 63 61 6e 4e 65 78 74 3b 0a 20 20 20 20 20  pScanNext;.     
25e0: 20 7d 0a 20 20 20 20 20 20 2a 70 70 4f 75 74 20   }.      *ppOut 
25f0: 3d 20 30 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a  = 0;.    }.  }..
2600: 20 20 72 65 74 75 72 6e 20 70 52 65 74 3b 0a 7d    return pRet;.}
2610: 0a 0a 2f 2a 0a 2a 2a 20 45 78 74 72 61 63 74 20  ../*.** Extract 
2620: 61 6c 6c 20 74 6f 6b 65 6e 73 20 66 72 6f 6d 20  all tokens from 
2630: 68 61 73 68 20 74 61 62 6c 65 20 69 48 61 73 68  hash table iHash
2640: 20 61 6e 64 20 6c 69 6e 6b 20 74 68 65 6d 20 69   and link them i
2650: 6e 74 6f 20 61 20 6c 69 73 74 0a 2a 2a 20 69 6e  nto a list.** in
2660: 20 73 6f 72 74 65 64 20 6f 72 64 65 72 2e 20 54   sorted order. T
2670: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 69 73  he hash table is
2680: 20 63 6c 65 61 72 65 64 20 62 65 66 6f 72 65 20   cleared before 
2690: 72 65 74 75 72 6e 69 6e 67 2e 20 49 74 20 69 73  returning. It is
26a0: 0a 2a 2a 20 74 68 65 20 72 65 73 70 6f 6e 73 69  .** the responsi
26b0: 62 69 6c 69 74 79 20 6f 66 20 74 68 65 20 63 61  bility of the ca
26c0: 6c 6c 65 72 20 74 6f 20 66 72 65 65 20 74 68 65  ller to free the
26d0: 20 65 6c 65 6d 65 6e 74 73 20 6f 66 20 74 68 65   elements of the
26e0: 20 72 65 74 75 72 6e 65 64 0a 2a 2a 20 6c 69 73   returned.** lis
26f0: 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74  t..*/.static int
2700: 20 66 74 73 35 48 61 73 68 45 6e 74 72 79 53 6f   fts5HashEntrySo
2710: 72 74 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a  rt(.  Fts5Hash *
2720: 70 48 61 73 68 2c 20 0a 20 20 63 6f 6e 73 74 20  pHash, .  const 
2730: 63 68 61 72 20 2a 70 54 65 72 6d 2c 20 69 6e 74  char *pTerm, int
2740: 20 6e 54 65 72 6d 2c 20 20 20 2f 2a 20 51 75 65   nTerm,   /* Que
2750: 72 79 20 70 72 65 66 69 78 2c 20 69 66 20 61 6e  ry prefix, if an
2760: 79 20 2a 2f 0a 20 20 46 74 73 35 48 61 73 68 45  y */.  Fts5HashE
2770: 6e 74 72 79 20 2a 2a 70 70 53 6f 72 74 65 64 0a  ntry **ppSorted.
2780: 29 7b 0a 20 20 63 6f 6e 73 74 20 69 6e 74 20 6e  ){.  const int n
2790: 4d 65 72 67 65 53 6c 6f 74 20 3d 20 33 32 3b 0a  MergeSlot = 32;.
27a0: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20    Fts5HashEntry 
27b0: 2a 2a 61 70 3b 0a 20 20 46 74 73 35 48 61 73 68  **ap;.  Fts5Hash
27c0: 45 6e 74 72 79 20 2a 70 4c 69 73 74 3b 0a 20 20  Entry *pList;.  
27d0: 69 6e 74 20 69 53 6c 6f 74 3b 0a 20 20 69 6e 74  int iSlot;.  int
27e0: 20 69 3b 0a 0a 20 20 2a 70 70 53 6f 72 74 65 64   i;..  *ppSorted
27f0: 20 3d 20 30 3b 0a 20 20 61 70 20 3d 20 73 71 6c   = 0;.  ap = sql
2800: 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 73 69 7a 65  ite3_malloc(size
2810: 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79  of(Fts5HashEntry
2820: 2a 29 20 2a 20 6e 4d 65 72 67 65 53 6c 6f 74 29  *) * nMergeSlot)
2830: 3b 0a 20 20 69 66 28 20 21 61 70 20 29 20 72 65  ;.  if( !ap ) re
2840: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45  turn SQLITE_NOME
2850: 4d 3b 0a 20 20 6d 65 6d 73 65 74 28 61 70 2c 20  M;.  memset(ap, 
2860: 30 2c 20 73 69 7a 65 6f 66 28 46 74 73 35 48 61  0, sizeof(Fts5Ha
2870: 73 68 45 6e 74 72 79 2a 29 20 2a 20 6e 4d 65 72  shEntry*) * nMer
2880: 67 65 53 6c 6f 74 29 3b 0a 0a 20 20 66 6f 72 28  geSlot);..  for(
2890: 69 53 6c 6f 74 3d 30 3b 20 69 53 6c 6f 74 3c 70  iSlot=0; iSlot<p
28a0: 48 61 73 68 2d 3e 6e 53 6c 6f 74 3b 20 69 53 6c  Hash->nSlot; iSl
28b0: 6f 74 2b 2b 29 7b 0a 20 20 20 20 46 74 73 35 48  ot++){.    Fts5H
28c0: 61 73 68 45 6e 74 72 79 20 2a 70 49 74 65 72 3b  ashEntry *pIter;
28d0: 0a 20 20 20 20 66 6f 72 28 70 49 74 65 72 3d 70  .    for(pIter=p
28e0: 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 53 6c 6f  Hash->aSlot[iSlo
28f0: 74 5d 3b 20 70 49 74 65 72 3b 20 70 49 74 65 72  t]; pIter; pIter
2900: 3d 70 49 74 65 72 2d 3e 70 48 61 73 68 4e 65 78  =pIter->pHashNex
2910: 74 29 7b 0a 20 20 20 20 20 20 69 66 28 20 70 54  t){.      if( pT
2920: 65 72 6d 3d 3d 30 20 7c 7c 20 30 3d 3d 6d 65 6d  erm==0 || 0==mem
2930: 63 6d 70 28 70 49 74 65 72 2d 3e 7a 4b 65 79 2c  cmp(pIter->zKey,
2940: 20 70 54 65 72 6d 2c 20 6e 54 65 72 6d 29 20 29   pTerm, nTerm) )
2950: 7b 0a 20 20 20 20 20 20 20 20 46 74 73 35 48 61  {.        Fts5Ha
2960: 73 68 45 6e 74 72 79 20 2a 70 45 6e 74 72 79 20  shEntry *pEntry 
2970: 3d 20 70 49 74 65 72 3b 0a 20 20 20 20 20 20 20  = pIter;.       
2980: 20 70 45 6e 74 72 79 2d 3e 70 53 63 61 6e 4e 65   pEntry->pScanNe
2990: 78 74 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20  xt = 0;.        
29a0: 66 6f 72 28 69 3d 30 3b 20 61 70 5b 69 5d 3b 20  for(i=0; ap[i]; 
29b0: 69 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 20 20  i++){.          
29c0: 70 45 6e 74 72 79 20 3d 20 66 74 73 35 48 61 73  pEntry = fts5Has
29d0: 68 45 6e 74 72 79 4d 65 72 67 65 28 70 45 6e 74  hEntryMerge(pEnt
29e0: 72 79 2c 20 61 70 5b 69 5d 29 3b 0a 20 20 20 20  ry, ap[i]);.    
29f0: 20 20 20 20 20 20 61 70 5b 69 5d 20 3d 20 30 3b        ap[i] = 0;
2a00: 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20  .        }.     
2a10: 20 20 20 61 70 5b 69 5d 20 3d 20 70 45 6e 74 72     ap[i] = pEntr
2a20: 79 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 7d  y;.      }.    }
2a30: 0a 20 20 7d 0a 0a 20 20 70 4c 69 73 74 20 3d 20  .  }..  pList = 
2a40: 30 3b 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c  0;.  for(i=0; i<
2a50: 6e 4d 65 72 67 65 53 6c 6f 74 3b 20 69 2b 2b 29  nMergeSlot; i++)
2a60: 7b 0a 20 20 20 20 70 4c 69 73 74 20 3d 20 66 74  {.    pList = ft
2a70: 73 35 48 61 73 68 45 6e 74 72 79 4d 65 72 67 65  s5HashEntryMerge
2a80: 28 70 4c 69 73 74 2c 20 61 70 5b 69 5d 29 3b 0a  (pList, ap[i]);.
2a90: 20 20 7d 0a 0a 20 20 70 48 61 73 68 2d 3e 6e 45    }..  pHash->nE
2aa0: 6e 74 72 79 20 3d 20 30 3b 0a 20 20 73 71 6c 69  ntry = 0;.  sqli
2ab0: 74 65 33 5f 66 72 65 65 28 61 70 29 3b 0a 20 20  te3_free(ap);.  
2ac0: 2a 70 70 53 6f 72 74 65 64 20 3d 20 70 4c 69 73  *ppSorted = pLis
2ad0: 74 3b 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49  t;.  return SQLI
2ae0: 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20  TE_OK;.}../*.** 
2af0: 51 75 65 72 79 20 74 68 65 20 68 61 73 68 20 74  Query the hash t
2b00: 61 62 6c 65 20 66 6f 72 20 61 20 64 6f 63 6c 69  able for a docli
2b10: 73 74 20 61 73 73 6f 63 69 61 74 65 64 20 77 69  st associated wi
2b20: 74 68 20 74 65 72 6d 20 70 54 65 72 6d 2f 6e 54  th term pTerm/nT
2b30: 65 72 6d 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69  erm..*/.int sqli
2b40: 74 65 33 46 74 73 35 48 61 73 68 51 75 65 72 79  te3Fts5HashQuery
2b50: 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a 70 48  (.  Fts5Hash *pH
2b60: 61 73 68 2c 20 20 20 20 20 20 20 20 20 20 20 20  ash,            
2b70: 20 20 20 20 2f 2a 20 48 61 73 68 20 74 61 62 6c      /* Hash tabl
2b80: 65 20 74 6f 20 71 75 65 72 79 20 2a 2f 0a 20 20  e to query */.  
2b90: 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 54 65 72  const char *pTer
2ba0: 6d 2c 20 69 6e 74 20 6e 54 65 72 6d 2c 20 20 20  m, int nTerm,   
2bb0: 2f 2a 20 51 75 65 72 79 20 74 65 72 6d 20 2a 2f  /* Query term */
2bc0: 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 2a  .  const char **
2bd0: 70 70 44 6f 63 6c 69 73 74 2c 20 20 20 20 20 20  ppDoclist,      
2be0: 20 20 20 2f 2a 20 4f 55 54 3a 20 50 6f 69 6e 74     /* OUT: Point
2bf0: 65 72 20 74 6f 20 64 6f 63 6c 69 73 74 20 66 6f  er to doclist fo
2c00: 72 20 70 54 65 72 6d 20 2a 2f 0a 20 20 69 6e 74  r pTerm */.  int
2c10: 20 2a 70 6e 44 6f 63 6c 69 73 74 20 20 20 20 20   *pnDoclist     
2c20: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
2c30: 4f 55 54 3a 20 53 69 7a 65 20 6f 66 20 64 6f 63  OUT: Size of doc
2c40: 6c 69 73 74 20 69 6e 20 62 79 74 65 73 20 2a 2f  list in bytes */
2c50: 0a 29 7b 0a 20 20 75 6e 73 69 67 6e 65 64 20 69  .){.  unsigned i
2c60: 6e 74 20 69 48 61 73 68 20 3d 20 66 74 73 35 48  nt iHash = fts5H
2c70: 61 73 68 4b 65 79 28 70 48 61 73 68 2d 3e 6e 53  ashKey(pHash->nS
2c80: 6c 6f 74 2c 20 70 54 65 72 6d 2c 20 6e 54 65 72  lot, pTerm, nTer
2c90: 6d 29 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e  m);.  Fts5HashEn
2ca0: 74 72 79 20 2a 70 3b 0a 0a 20 20 66 6f 72 28 70  try *p;..  for(p
2cb0: 3d 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 48  =pHash->aSlot[iH
2cc0: 61 73 68 5d 3b 20 70 3b 20 70 3d 70 2d 3e 70 48  ash]; p; p=p->pH
2cd0: 61 73 68 4e 65 78 74 29 7b 0a 20 20 20 20 69 66  ashNext){.    if
2ce0: 28 20 6d 65 6d 63 6d 70 28 70 2d 3e 7a 4b 65 79  ( memcmp(p->zKey
2cf0: 2c 20 70 54 65 72 6d 2c 20 6e 54 65 72 6d 29 3d  , pTerm, nTerm)=
2d00: 3d 30 20 26 26 20 70 2d 3e 7a 4b 65 79 5b 6e 54  =0 && p->zKey[nT
2d10: 65 72 6d 5d 3d 3d 30 20 29 20 62 72 65 61 6b 3b  erm]==0 ) break;
2d20: 0a 20 20 7d 0a 0a 20 20 69 66 28 20 70 20 29 7b  .  }..  if( p ){
2d30: 0a 20 20 20 20 66 74 73 35 48 61 73 68 41 64 64  .    fts5HashAdd
2d40: 50 6f 73 6c 69 73 74 53 69 7a 65 28 70 29 3b 0a  PoslistSize(p);.
2d50: 20 20 20 20 2a 70 70 44 6f 63 6c 69 73 74 20 3d      *ppDoclist =
2d60: 20 26 70 2d 3e 7a 4b 65 79 5b 6e 54 65 72 6d 2b   &p->zKey[nTerm+
2d70: 31 5d 3b 0a 20 20 20 20 2a 70 6e 44 6f 63 6c 69  1];.    *pnDocli
2d80: 73 74 20 3d 20 70 2d 3e 6e 44 61 74 61 20 2d 20  st = p->nData - 
2d90: 28 73 69 7a 65 6f 66 28 2a 70 29 20 2b 20 6e 54  (sizeof(*p) + nT
2da0: 65 72 6d 20 2b 20 31 29 3b 0a 20 20 7d 65 6c 73  erm + 1);.  }els
2db0: 65 7b 0a 20 20 20 20 2a 70 70 44 6f 63 6c 69 73  e{.    *ppDoclis
2dc0: 74 20 3d 20 30 3b 0a 20 20 20 20 2a 70 6e 44 6f  t = 0;.    *pnDo
2dd0: 63 6c 69 73 74 20 3d 20 30 3b 0a 20 20 7d 0a 0a  clist = 0;.  }..
2de0: 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f    return SQLITE_
2df0: 4f 4b 3b 0a 7d 0a 0a 69 6e 74 20 73 71 6c 69 74  OK;.}..int sqlit
2e00: 65 33 46 74 73 35 48 61 73 68 53 63 61 6e 49 6e  e3Fts5HashScanIn
2e10: 69 74 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a  it(.  Fts5Hash *
2e20: 70 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20  p,              
2e30: 20 20 20 20 20 20 2f 2a 20 48 61 73 68 20 74 61        /* Hash ta
2e40: 62 6c 65 20 74 6f 20 71 75 65 72 79 20 2a 2f 0a  ble to query */.
2e50: 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 54    const char *pT
2e60: 65 72 6d 2c 20 69 6e 74 20 6e 54 65 72 6d 20 20  erm, int nTerm  
2e70: 20 20 2f 2a 20 51 75 65 72 79 20 70 72 65 66 69    /* Query prefi
2e80: 78 20 2a 2f 0a 29 7b 0a 20 20 72 65 74 75 72 6e  x */.){.  return
2e90: 20 66 74 73 35 48 61 73 68 45 6e 74 72 79 53 6f   fts5HashEntrySo
2ea0: 72 74 28 70 2c 20 70 54 65 72 6d 2c 20 6e 54 65  rt(p, pTerm, nTe
2eb0: 72 6d 2c 20 26 70 2d 3e 70 53 63 61 6e 29 3b 0a  rm, &p->pScan);.
2ec0: 7d 0a 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 46  }..void sqlite3F
2ed0: 74 73 35 48 61 73 68 53 63 61 6e 4e 65 78 74 28  ts5HashScanNext(
2ee0: 46 74 73 35 48 61 73 68 20 2a 70 29 7b 0a 20 20  Fts5Hash *p){.  
2ef0: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70  Fts5HashEntry *p
2f00: 53 63 61 6e 20 3d 20 70 2d 3e 70 53 63 61 6e 3b  Scan = p->pScan;
2f10: 0a 20 20 69 66 28 20 70 53 63 61 6e 20 29 20 70  .  if( pScan ) p
2f20: 2d 3e 70 53 63 61 6e 20 3d 20 70 53 63 61 6e 2d  ->pScan = pScan-
2f30: 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 7d 0a 0a 69  >pScanNext;.}..i
2f40: 6e 74 20 73 71 6c 69 74 65 33 46 74 73 35 48 61  nt sqlite3Fts5Ha
2f50: 73 68 53 63 61 6e 45 6f 66 28 46 74 73 35 48 61  shScanEof(Fts5Ha
2f60: 73 68 20 2a 70 29 7b 0a 20 20 72 65 74 75 72 6e  sh *p){.  return
2f70: 20 28 70 2d 3e 70 53 63 61 6e 3d 3d 30 29 3b 0a   (p->pScan==0);.
2f80: 7d 0a 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 46  }..void sqlite3F
2f90: 74 73 35 48 61 73 68 53 63 61 6e 45 6e 74 72 79  ts5HashScanEntry
2fa0: 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a 70 48  (.  Fts5Hash *pH
2fb0: 61 73 68 2c 0a 20 20 63 6f 6e 73 74 20 63 68 61  ash,.  const cha
2fc0: 72 20 2a 2a 70 7a 54 65 72 6d 2c 20 20 20 20 20  r **pzTerm,     
2fd0: 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20 74         /* OUT: t
2fe0: 65 72 6d 20 28 6e 75 6c 2d 74 65 72 6d 69 6e 61  erm (nul-termina
2ff0: 74 65 64 29 20 2a 2f 0a 20 20 63 6f 6e 73 74 20  ted) */.  const 
3000: 63 68 61 72 20 2a 2a 70 70 44 6f 63 6c 69 73 74  char **ppDoclist
3010: 2c 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 54  ,         /* OUT
3020: 3a 20 70 6f 69 6e 74 65 72 20 74 6f 20 64 6f 63  : pointer to doc
3030: 6c 69 73 74 20 2a 2f 0a 20 20 69 6e 74 20 2a 70  list */.  int *p
3040: 6e 44 6f 63 6c 69 73 74 20 20 20 20 20 20 20 20  nDoclist        
3050: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 54            /* OUT
3060: 3a 20 73 69 7a 65 20 6f 66 20 64 6f 63 6c 69 73  : size of doclis
3070: 74 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a 29 7b  t in bytes */.){
3080: 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  .  Fts5HashEntry
3090: 20 2a 70 3b 0a 20 20 69 66 28 20 28 70 20 3d 20   *p;.  if( (p = 
30a0: 70 48 61 73 68 2d 3e 70 53 63 61 6e 29 20 29 7b  pHash->pScan) ){
30b0: 0a 20 20 20 20 69 6e 74 20 6e 54 65 72 6d 20 3d  .    int nTerm =
30c0: 20 73 74 72 6c 65 6e 28 70 2d 3e 7a 4b 65 79 29   strlen(p->zKey)
30d0: 3b 0a 20 20 20 20 66 74 73 35 48 61 73 68 41 64  ;.    fts5HashAd
30e0: 64 50 6f 73 6c 69 73 74 53 69 7a 65 28 70 29 3b  dPoslistSize(p);
30f0: 0a 20 20 20 20 2a 70 7a 54 65 72 6d 20 3d 20 70  .    *pzTerm = p
3100: 2d 3e 7a 4b 65 79 3b 0a 20 20 20 20 2a 70 70 44  ->zKey;.    *ppD
3110: 6f 63 6c 69 73 74 20 3d 20 26 70 2d 3e 7a 4b 65  oclist = &p->zKe
3120: 79 5b 6e 54 65 72 6d 2b 31 5d 3b 0a 20 20 20 20  y[nTerm+1];.    
3130: 2a 70 6e 44 6f 63 6c 69 73 74 20 3d 20 70 2d 3e  *pnDoclist = p->
3140: 6e 44 61 74 61 20 2d 20 28 73 69 7a 65 6f 66 28  nData - (sizeof(
3150: 2a 70 29 20 2b 20 6e 54 65 72 6d 20 2b 20 31 29  *p) + nTerm + 1)
3160: 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2a  ;.  }else{.    *
3170: 70 7a 54 65 72 6d 20 3d 20 30 3b 0a 20 20 20 20  pzTerm = 0;.    
3180: 2a 70 70 44 6f 63 6c 69 73 74 20 3d 20 30 3b 0a  *ppDoclist = 0;.
3190: 20 20 20 20 2a 70 6e 44 6f 63 6c 69 73 74 20 3d      *pnDoclist =
31a0: 20 30 3b 0a 20 20 7d 0a 7d 0a 0a 23 65 6e 64 69   0;.  }.}..#endi
31b0: 66 20 2f 2a 20 53 51 4c 49 54 45 5f 45 4e 41 42  f /* SQLITE_ENAB
31c0: 4c 45 5f 46 54 53 35 20 2a 2f 0a                 LE_FTS5 */.