/ Hex Artifact Content
Login

Artifact 7c134ed05d25e2a19418356d78aa4e7059bd319c:


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 41 6c 6c 6f 63  .};../*.** Alloc
0960: 61 74 65 20 61 20 6e 65 77 20 68 61 73 68 20 74  ate a new hash t
0970: 61 62 6c 65 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c  able..*/.int sql
0980: 69 74 65 33 46 74 73 35 48 61 73 68 4e 65 77 28  ite3Fts5HashNew(
0990: 46 74 73 35 48 61 73 68 20 2a 2a 70 70 4e 65 77  Fts5Hash **ppNew
09a0: 2c 20 69 6e 74 20 2a 70 6e 42 79 74 65 29 7b 0a  , int *pnByte){.
09b0: 20 20 69 6e 74 20 72 63 20 3d 20 53 51 4c 49 54    int rc = SQLIT
09c0: 45 5f 4f 4b 3b 0a 20 20 46 74 73 35 48 61 73 68  E_OK;.  Fts5Hash
09d0: 20 2a 70 4e 65 77 3b 0a 0a 20 20 2a 70 70 4e 65   *pNew;..  *ppNe
09e0: 77 20 3d 20 70 4e 65 77 20 3d 20 28 46 74 73 35  w = pNew = (Fts5
09f0: 48 61 73 68 2a 29 73 71 6c 69 74 65 33 5f 6d 61  Hash*)sqlite3_ma
0a00: 6c 6c 6f 63 28 73 69 7a 65 6f 66 28 46 74 73 35  lloc(sizeof(Fts5
0a10: 48 61 73 68 29 29 3b 0a 20 20 69 66 28 20 70 4e  Hash));.  if( pN
0a20: 65 77 3d 3d 30 20 29 7b 0a 20 20 20 20 72 63 20  ew==0 ){.    rc 
0a30: 3d 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a  = SQLITE_NOMEM;.
0a40: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 69 6e 74    }else{.    int
0a50: 20 6e 42 79 74 65 3b 0a 20 20 20 20 6d 65 6d 73   nByte;.    mems
0a60: 65 74 28 70 4e 65 77 2c 20 30 2c 20 73 69 7a 65  et(pNew, 0, size
0a70: 6f 66 28 46 74 73 35 48 61 73 68 29 29 3b 0a 20  of(Fts5Hash));. 
0a80: 20 20 20 70 4e 65 77 2d 3e 70 6e 42 79 74 65 20     pNew->pnByte 
0a90: 3d 20 70 6e 42 79 74 65 3b 0a 0a 20 20 20 20 70  = pnByte;..    p
0aa0: 4e 65 77 2d 3e 6e 53 6c 6f 74 20 3d 20 31 30 32  New->nSlot = 102
0ab0: 34 3b 0a 20 20 20 20 6e 42 79 74 65 20 3d 20 73  4;.    nByte = s
0ac0: 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e  izeof(Fts5HashEn
0ad0: 74 72 79 2a 29 20 2a 20 70 4e 65 77 2d 3e 6e 53  try*) * pNew->nS
0ae0: 6c 6f 74 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 61  lot;.    pNew->a
0af0: 53 6c 6f 74 20 3d 20 28 46 74 73 35 48 61 73 68  Slot = (Fts5Hash
0b00: 45 6e 74 72 79 2a 2a 29 73 71 6c 69 74 65 33 5f  Entry**)sqlite3_
0b10: 6d 61 6c 6c 6f 63 28 6e 42 79 74 65 29 3b 0a 20  malloc(nByte);. 
0b20: 20 20 20 69 66 28 20 70 4e 65 77 2d 3e 61 53 6c     if( pNew->aSl
0b30: 6f 74 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 73  ot==0 ){.      s
0b40: 71 6c 69 74 65 33 5f 66 72 65 65 28 70 4e 65 77  qlite3_free(pNew
0b50: 29 3b 0a 20 20 20 20 20 20 2a 70 70 4e 65 77 20  );.      *ppNew 
0b60: 3d 20 30 3b 0a 20 20 20 20 20 20 72 63 20 3d 20  = 0;.      rc = 
0b70: 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20  SQLITE_NOMEM;.  
0b80: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 6d    }else{.      m
0b90: 65 6d 73 65 74 28 70 4e 65 77 2d 3e 61 53 6c 6f  emset(pNew->aSlo
0ba0: 74 2c 20 30 2c 20 6e 42 79 74 65 29 3b 0a 20 20  t, 0, nByte);.  
0bb0: 20 20 7d 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e    }.  }.  return
0bc0: 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 46 72   rc;.}../*.** Fr
0bd0: 65 65 20 61 20 68 61 73 68 20 74 61 62 6c 65 20  ee a hash table 
0be0: 6f 62 6a 65 63 74 2e 0a 2a 2f 0a 76 6f 69 64 20  object..*/.void 
0bf0: 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 46  sqlite3Fts5HashF
0c00: 72 65 65 28 46 74 73 35 48 61 73 68 20 2a 70 48  ree(Fts5Hash *pH
0c10: 61 73 68 29 7b 0a 20 20 69 66 28 20 70 48 61 73  ash){.  if( pHas
0c20: 68 20 29 7b 0a 20 20 20 20 73 71 6c 69 74 65 33  h ){.    sqlite3
0c30: 46 74 73 35 48 61 73 68 43 6c 65 61 72 28 70 48  Fts5HashClear(pH
0c40: 61 73 68 29 3b 0a 20 20 20 20 73 71 6c 69 74 65  ash);.    sqlite
0c50: 33 5f 66 72 65 65 28 70 48 61 73 68 2d 3e 61 53  3_free(pHash->aS
0c60: 6c 6f 74 29 3b 0a 20 20 20 20 73 71 6c 69 74 65  lot);.    sqlite
0c70: 33 5f 66 72 65 65 28 70 48 61 73 68 29 3b 0a 20  3_free(pHash);. 
0c80: 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 45 6d 70 74   }.}../*.** Empt
0c90: 79 20 28 62 75 74 20 64 6f 20 6e 6f 74 20 64 65  y (but do not de
0ca0: 6c 65 74 65 29 20 61 20 68 61 73 68 20 74 61 62  lete) a hash tab
0cb0: 6c 65 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69  le..*/.void sqli
0cc0: 74 65 33 46 74 73 35 48 61 73 68 43 6c 65 61 72  te3Fts5HashClear
0cd0: 28 46 74 73 35 48 61 73 68 20 2a 70 48 61 73 68  (Fts5Hash *pHash
0ce0: 29 7b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 66 6f  ){.  int i;.  fo
0cf0: 72 28 69 3d 30 3b 20 69 3c 70 48 61 73 68 2d 3e  r(i=0; i<pHash->
0d00: 6e 53 6c 6f 74 3b 20 69 2b 2b 29 7b 0a 20 20 20  nSlot; i++){.   
0d10: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
0d20: 70 4e 65 78 74 3b 0a 20 20 20 20 46 74 73 35 48  pNext;.    Fts5H
0d30: 61 73 68 45 6e 74 72 79 20 2a 70 53 6c 6f 74 3b  ashEntry *pSlot;
0d40: 0a 20 20 20 20 66 6f 72 28 70 53 6c 6f 74 3d 70  .    for(pSlot=p
0d50: 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 5d 3b 20  Hash->aSlot[i]; 
0d60: 70 53 6c 6f 74 3b 20 70 53 6c 6f 74 3d 70 4e 65  pSlot; pSlot=pNe
0d70: 78 74 29 7b 0a 20 20 20 20 20 20 70 4e 65 78 74  xt){.      pNext
0d80: 20 3d 20 70 53 6c 6f 74 2d 3e 70 48 61 73 68 4e   = pSlot->pHashN
0d90: 65 78 74 3b 0a 20 20 20 20 20 20 73 71 6c 69 74  ext;.      sqlit
0da0: 65 33 5f 66 72 65 65 28 70 53 6c 6f 74 29 3b 0a  e3_free(pSlot);.
0db0: 20 20 20 20 7d 0a 20 20 7d 0a 20 20 6d 65 6d 73      }.  }.  mems
0dc0: 65 74 28 70 48 61 73 68 2d 3e 61 53 6c 6f 74 2c  et(pHash->aSlot,
0dd0: 20 30 2c 20 70 48 61 73 68 2d 3e 6e 53 6c 6f 74   0, pHash->nSlot
0de0: 20 2a 20 73 69 7a 65 6f 66 28 46 74 73 35 48 61   * sizeof(Fts5Ha
0df0: 73 68 45 6e 74 72 79 2a 29 29 3b 0a 20 20 70 48  shEntry*));.  pH
0e00: 61 73 68 2d 3e 6e 45 6e 74 72 79 20 3d 20 30 3b  ash->nEntry = 0;
0e10: 0a 7d 0a 0a 73 74 61 74 69 63 20 75 6e 73 69 67  .}..static unsig
0e20: 6e 65 64 20 69 6e 74 20 66 74 73 35 48 61 73 68  ned int fts5Hash
0e30: 4b 65 79 28 69 6e 74 20 6e 53 6c 6f 74 2c 20 63  Key(int nSlot, c
0e40: 6f 6e 73 74 20 63 68 61 72 20 2a 70 2c 20 69 6e  onst char *p, in
0e50: 74 20 6e 29 7b 0a 20 20 69 6e 74 20 69 3b 0a 20  t n){.  int i;. 
0e60: 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 68 20   unsigned int h 
0e70: 3d 20 31 33 3b 0a 20 20 66 6f 72 28 69 3d 6e 2d  = 13;.  for(i=n-
0e80: 31 3b 20 69 3e 3d 30 3b 20 69 2d 2d 29 7b 0a 20  1; i>=0; i--){. 
0e90: 20 20 20 68 20 3d 20 28 68 20 3c 3c 20 33 29 20     h = (h << 3) 
0ea0: 5e 20 68 20 5e 20 70 5b 69 5d 3b 0a 20 20 7d 0a  ^ h ^ p[i];.  }.
0eb0: 20 20 72 65 74 75 72 6e 20 28 68 20 25 20 6e 53    return (h % nS
0ec0: 6c 6f 74 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52  lot);.}../*.** R
0ed0: 65 73 69 7a 65 20 74 68 65 20 68 61 73 68 20 74  esize the hash t
0ee0: 61 62 6c 65 20 62 79 20 64 6f 75 62 6c 69 6e 67  able by doubling
0ef0: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 73   the number of s
0f00: 6c 6f 74 73 2e 0a 2a 2f 0a 73 74 61 74 69 63 20  lots..*/.static 
0f10: 69 6e 74 20 66 74 73 35 48 61 73 68 52 65 73 69  int fts5HashResi
0f20: 7a 65 28 46 74 73 35 48 61 73 68 20 2a 70 48 61  ze(Fts5Hash *pHa
0f30: 73 68 29 7b 0a 20 20 69 6e 74 20 6e 4e 65 77 20  sh){.  int nNew 
0f40: 3d 20 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 2a 32  = pHash->nSlot*2
0f50: 3b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 46 74 73  ;.  int i;.  Fts
0f60: 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 61 70 4e  5HashEntry **apN
0f70: 65 77 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e  ew;.  Fts5HashEn
0f80: 74 72 79 20 2a 2a 61 70 4f 6c 64 20 3d 20 70 48  try **apOld = pH
0f90: 61 73 68 2d 3e 61 53 6c 6f 74 3b 0a 0a 20 20 61  ash->aSlot;..  a
0fa0: 70 4e 65 77 20 3d 20 28 46 74 73 35 48 61 73 68  pNew = (Fts5Hash
0fb0: 45 6e 74 72 79 2a 2a 29 73 71 6c 69 74 65 33 5f  Entry**)sqlite3_
0fc0: 6d 61 6c 6c 6f 63 28 6e 4e 65 77 2a 73 69 7a 65  malloc(nNew*size
0fd0: 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79  of(Fts5HashEntry
0fe0: 2a 29 29 3b 0a 20 20 69 66 28 20 21 61 70 4e 65  *));.  if( !apNe
0ff0: 77 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54  w ) return SQLIT
1000: 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 6d 65 6d 73 65  E_NOMEM;.  memse
1010: 74 28 61 70 4e 65 77 2c 20 30 2c 20 6e 4e 65 77  t(apNew, 0, nNew
1020: 2a 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68  *sizeof(Fts5Hash
1030: 45 6e 74 72 79 2a 29 29 3b 0a 0a 20 20 66 6f 72  Entry*));..  for
1040: 28 69 3d 30 3b 20 69 3c 70 48 61 73 68 2d 3e 6e  (i=0; i<pHash->n
1050: 53 6c 6f 74 3b 20 69 2b 2b 29 7b 0a 20 20 20 20  Slot; i++){.    
1060: 77 68 69 6c 65 28 20 61 70 4f 6c 64 5b 69 5d 20  while( apOld[i] 
1070: 29 7b 0a 20 20 20 20 20 20 69 6e 74 20 69 48 61  ){.      int iHa
1080: 73 68 3b 0a 20 20 20 20 20 20 46 74 73 35 48 61  sh;.      Fts5Ha
1090: 73 68 45 6e 74 72 79 20 2a 70 20 3d 20 61 70 4f  shEntry *p = apO
10a0: 6c 64 5b 69 5d 3b 0a 20 20 20 20 20 20 61 70 4f  ld[i];.      apO
10b0: 6c 64 5b 69 5d 20 3d 20 70 2d 3e 70 48 61 73 68  ld[i] = p->pHash
10c0: 4e 65 78 74 3b 0a 20 20 20 20 20 20 69 48 61 73  Next;.      iHas
10d0: 68 20 3d 20 66 74 73 35 48 61 73 68 4b 65 79 28  h = fts5HashKey(
10e0: 6e 4e 65 77 2c 20 70 2d 3e 7a 4b 65 79 2c 20 73  nNew, p->zKey, s
10f0: 74 72 6c 65 6e 28 70 2d 3e 7a 4b 65 79 29 29 3b  trlen(p->zKey));
1100: 0a 20 20 20 20 20 20 70 2d 3e 70 48 61 73 68 4e  .      p->pHashN
1110: 65 78 74 20 3d 20 61 70 4e 65 77 5b 69 48 61 73  ext = apNew[iHas
1120: 68 5d 3b 0a 20 20 20 20 20 20 61 70 4e 65 77 5b  h];.      apNew[
1130: 69 48 61 73 68 5d 20 3d 20 70 3b 0a 20 20 20 20  iHash] = p;.    
1140: 7d 0a 20 20 7d 0a 0a 20 20 73 71 6c 69 74 65 33  }.  }..  sqlite3
1150: 5f 66 72 65 65 28 61 70 4f 6c 64 29 3b 0a 20 20  _free(apOld);.  
1160: 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 20 3d 20 6e  pHash->nSlot = n
1170: 4e 65 77 3b 0a 20 20 70 48 61 73 68 2d 3e 61 53  New;.  pHash->aS
1180: 6c 6f 74 20 3d 20 61 70 4e 65 77 3b 0a 20 20 72  lot = apNew;.  r
1190: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b  eturn SQLITE_OK;
11a0: 0a 7d 0a 0a 73 74 61 74 69 63 20 76 6f 69 64 20  .}..static void 
11b0: 66 74 73 35 48 61 73 68 41 64 64 50 6f 73 6c 69  fts5HashAddPosli
11c0: 73 74 53 69 7a 65 28 46 74 73 35 48 61 73 68 45  stSize(Fts5HashE
11d0: 6e 74 72 79 20 2a 70 29 7b 0a 20 20 69 66 28 20  ntry *p){.  if( 
11e0: 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 29 7b  p->iSzPoslist ){
11f0: 0a 20 20 20 20 2f 2a 20 57 52 49 54 45 50 4f 53  .    /* WRITEPOS
1200: 4c 49 53 54 53 49 5a 45 20 2a 2f 0a 20 20 20 20  LISTSIZE */.    
1210: 75 38 20 2a 70 50 74 72 20 3d 20 28 75 38 2a 29  u8 *pPtr = (u8*)
1220: 70 3b 0a 20 20 20 20 69 6e 74 20 6e 53 7a 20 3d  p;.    int nSz =
1230: 20 28 70 2d 3e 6e 44 61 74 61 20 2d 20 70 2d 3e   (p->nData - p->
1240: 69 53 7a 50 6f 73 6c 69 73 74 20 2d 20 31 29 20  iSzPoslist - 1) 
1250: 2a 20 32 3b 0a 0a 20 20 20 20 69 66 28 20 6e 53  * 2;..    if( nS
1260: 7a 3c 3d 31 32 37 20 29 7b 0a 20 20 20 20 20 20  z<=127 ){.      
1270: 70 50 74 72 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69  pPtr[p->iSzPosli
1280: 73 74 5d 20 3d 20 6e 53 7a 3b 0a 20 20 20 20 7d  st] = nSz;.    }
1290: 65 6c 73 65 7b 0a 20 20 20 20 20 20 69 6e 74 20  else{.      int 
12a0: 6e 42 79 74 65 20 3d 20 73 71 6c 69 74 65 33 46  nByte = sqlite3F
12b0: 74 73 35 47 65 74 56 61 72 69 6e 74 4c 65 6e 28  ts5GetVarintLen(
12c0: 28 75 33 32 29 6e 53 7a 29 3b 0a 20 20 20 20 20  (u32)nSz);.     
12d0: 20 2f 2a 20 57 52 49 54 45 50 4f 53 4c 49 53 54   /* WRITEPOSLIST
12e0: 53 49 5a 45 20 2a 2f 0a 20 20 20 20 20 20 6d 65  SIZE */.      me
12f0: 6d 6d 6f 76 65 28 26 70 50 74 72 5b 70 2d 3e 69  mmove(&pPtr[p->i
1300: 53 7a 50 6f 73 6c 69 73 74 20 2b 20 6e 42 79 74  SzPoslist + nByt
1310: 65 5d 2c 20 26 70 50 74 72 5b 70 2d 3e 69 53 7a  e], &pPtr[p->iSz
1320: 50 6f 73 6c 69 73 74 20 2b 20 31 5d 2c 20 6e 53  Poslist + 1], nS
1330: 7a 2f 32 29 3b 0a 20 20 20 20 20 20 73 71 6c 69  z/2);.      sqli
1340: 74 65 33 50 75 74 56 61 72 69 6e 74 28 26 70 50  te3PutVarint(&pP
1350: 74 72 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74  tr[p->iSzPoslist
1360: 5d 2c 20 6e 53 7a 29 3b 0a 20 20 20 20 20 20 70  ], nSz);.      p
1370: 2d 3e 6e 44 61 74 61 20 2b 3d 20 28 6e 42 79 74  ->nData += (nByt
1380: 65 2d 31 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20  e-1);.    }.    
1390: 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 3d 20  p->iSzPoslist = 
13a0: 30 3b 0a 20 20 7d 0a 7d 0a 0a 69 6e 74 20 73 71  0;.  }.}..int sq
13b0: 6c 69 74 65 33 46 74 73 35 48 61 73 68 57 72 69  lite3Fts5HashWri
13c0: 74 65 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a  te(.  Fts5Hash *
13d0: 70 48 61 73 68 2c 0a 20 20 69 36 34 20 69 52 6f  pHash,.  i64 iRo
13e0: 77 69 64 2c 20 20 20 20 20 20 20 20 20 20 20 20  wid,            
13f0: 20 20 20 20 20 20 20 20 20 2f 2a 20 52 6f 77 69           /* Rowi
1400: 64 20 66 6f 72 20 74 68 69 73 20 65 6e 74 72 79  d for this entry
1410: 20 2a 2f 0a 20 20 69 6e 74 20 69 43 6f 6c 2c 20   */.  int iCol, 
1420: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1430: 20 20 20 20 20 20 2f 2a 20 43 6f 6c 75 6d 6e 20        /* Column 
1440: 74 6f 6b 65 6e 20 61 70 70 65 61 72 73 20 69 6e  token appears in
1450: 20 28 2d 76 65 20 2d 3e 20 64 65 6c 65 74 65 29   (-ve -> delete)
1460: 20 2a 2f 0a 20 20 69 6e 74 20 69 50 6f 73 2c 20   */.  int iPos, 
1470: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1480: 20 20 20 20 20 20 2f 2a 20 50 6f 73 69 74 69 6f        /* Positio
1490: 6e 20 6f 66 20 74 6f 6b 65 6e 20 77 69 74 68 69  n of token withi
14a0: 6e 20 63 6f 6c 75 6d 6e 20 2a 2f 0a 20 20 63 6f  n column */.  co
14b0: 6e 73 74 20 63 68 61 72 20 2a 70 54 6f 6b 65 6e  nst char *pToken
14c0: 2c 20 69 6e 74 20 6e 54 6f 6b 65 6e 20 20 2f 2a  , int nToken  /*
14d0: 20 54 6f 6b 65 6e 20 74 6f 20 61 64 64 20 6f 72   Token to add or
14e0: 20 72 65 6d 6f 76 65 20 74 6f 20 6f 72 20 66 72   remove to or fr
14f0: 6f 6d 20 69 6e 64 65 78 20 2a 2f 0a 29 7b 0a 20  om index */.){. 
1500: 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 69 48   unsigned int iH
1510: 61 73 68 20 3d 20 66 74 73 35 48 61 73 68 4b 65  ash = fts5HashKe
1520: 79 28 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20  y(pHash->nSlot, 
1530: 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b  pToken, nToken);
1540: 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  .  Fts5HashEntry
1550: 20 2a 70 3b 0a 20 20 75 38 20 2a 70 50 74 72 3b   *p;.  u8 *pPtr;
1560: 0a 20 20 69 6e 74 20 6e 49 6e 63 72 20 3d 20 30  .  int nIncr = 0
1570: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
1580: 20 20 20 2f 2a 20 41 6d 6f 75 6e 74 20 74 6f 20     /* Amount to 
1590: 69 6e 63 72 65 6d 65 6e 74 20 28 2a 70 48 61 73  increment (*pHas
15a0: 68 2d 3e 70 6e 42 79 74 65 29 20 62 79 20 2a 2f  h->pnByte) by */
15b0: 0a 0a 20 20 2f 2a 20 41 74 74 65 6d 70 74 20 74  ..  /* Attempt t
15c0: 6f 20 6c 6f 63 61 74 65 20 61 6e 20 65 78 69 73  o locate an exis
15d0: 74 69 6e 67 20 68 61 73 68 20 65 6e 74 72 79 20  ting hash entry 
15e0: 2a 2f 0a 20 20 66 6f 72 28 70 3d 70 48 61 73 68  */.  for(p=pHash
15f0: 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d 3b 20  ->aSlot[iHash]; 
1600: 70 3b 20 70 3d 70 2d 3e 70 48 61 73 68 4e 65 78  p; p=p->pHashNex
1610: 74 29 7b 0a 20 20 20 20 69 66 28 20 6d 65 6d 63  t){.    if( memc
1620: 6d 70 28 70 2d 3e 7a 4b 65 79 2c 20 70 54 6f 6b  mp(p->zKey, pTok
1630: 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3d 3d 30 20 26  en, nToken)==0 &
1640: 26 20 70 2d 3e 7a 4b 65 79 5b 6e 54 6f 6b 65 6e  & p->zKey[nToken
1650: 5d 3d 3d 30 20 29 20 62 72 65 61 6b 3b 0a 20 20  ]==0 ) break;.  
1660: 7d 0a 0a 20 20 2f 2a 20 49 66 20 61 6e 20 65 78  }..  /* If an ex
1670: 69 73 74 69 6e 67 20 68 61 73 68 20 65 6e 74 72  isting hash entr
1680: 79 20 63 61 6e 6e 6f 74 20 62 65 20 66 6f 75 6e  y cannot be foun
1690: 64 2c 20 63 72 65 61 74 65 20 61 20 6e 65 77 20  d, create a new 
16a0: 6f 6e 65 2e 20 2a 2f 0a 20 20 69 66 28 20 70 3d  one. */.  if( p=
16b0: 3d 30 20 29 7b 0a 20 20 20 20 69 6e 74 20 6e 42  =0 ){.    int nB
16c0: 79 74 65 20 3d 20 73 69 7a 65 6f 66 28 46 74 73  yte = sizeof(Fts
16d0: 35 48 61 73 68 45 6e 74 72 79 29 20 2b 20 6e 54  5HashEntry) + nT
16e0: 6f 6b 65 6e 20 2b 20 31 20 2b 20 36 34 3b 0a 20  oken + 1 + 64;. 
16f0: 20 20 20 69 66 28 20 6e 42 79 74 65 3c 31 32 38     if( nByte<128
1700: 20 29 20 6e 42 79 74 65 20 3d 20 31 32 38 3b 0a   ) nByte = 128;.
1710: 0a 20 20 20 20 69 66 28 20 28 70 48 61 73 68 2d  .    if( (pHash-
1720: 3e 6e 45 6e 74 72 79 2a 32 29 3e 3d 70 48 61 73  >nEntry*2)>=pHas
1730: 68 2d 3e 6e 53 6c 6f 74 20 29 7b 0a 20 20 20 20  h->nSlot ){.    
1740: 20 20 69 6e 74 20 72 63 20 3d 20 66 74 73 35 48    int rc = fts5H
1750: 61 73 68 52 65 73 69 7a 65 28 70 48 61 73 68 29  ashResize(pHash)
1760: 3b 0a 20 20 20 20 20 20 69 66 28 20 72 63 21 3d  ;.      if( rc!=
1770: 53 51 4c 49 54 45 5f 4f 4b 20 29 20 72 65 74 75  SQLITE_OK ) retu
1780: 72 6e 20 72 63 3b 0a 20 20 20 20 20 20 69 48 61  rn rc;.      iHa
1790: 73 68 20 3d 20 66 74 73 35 48 61 73 68 4b 65 79  sh = fts5HashKey
17a0: 28 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20 70  (pHash->nSlot, p
17b0: 54 6f 6b 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a  Token, nToken);.
17c0: 20 20 20 20 7d 0a 0a 20 20 20 20 70 20 3d 20 28      }..    p = (
17d0: 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29 73  Fts5HashEntry*)s
17e0: 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e 42  qlite3_malloc(nB
17f0: 79 74 65 29 3b 0a 20 20 20 20 69 66 28 20 21 70  yte);.    if( !p
1800: 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45   ) return SQLITE
1810: 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 6d 65 6d 73  _NOMEM;.    mems
1820: 65 74 28 70 2c 20 30 2c 20 73 69 7a 65 6f 66 28  et(p, 0, sizeof(
1830: 46 74 73 35 48 61 73 68 45 6e 74 72 79 29 29 3b  Fts5HashEntry));
1840: 0a 20 20 20 20 70 2d 3e 6e 41 6c 6c 6f 63 20 3d  .    p->nAlloc =
1850: 20 6e 42 79 74 65 3b 0a 20 20 20 20 6d 65 6d 63   nByte;.    memc
1860: 70 79 28 70 2d 3e 7a 4b 65 79 2c 20 70 54 6f 6b  py(p->zKey, pTok
1870: 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 20  en, nToken);.   
1880: 20 70 2d 3e 7a 4b 65 79 5b 6e 54 6f 6b 65 6e 5d   p->zKey[nToken]
1890: 20 3d 20 27 5c 30 27 3b 0a 20 20 20 20 70 2d 3e   = '\0';.    p->
18a0: 6e 44 61 74 61 20 3d 20 6e 54 6f 6b 65 6e 20 2b  nData = nToken +
18b0: 20 31 20 2b 20 73 69 7a 65 6f 66 28 46 74 73 35   1 + sizeof(Fts5
18c0: 48 61 73 68 45 6e 74 72 79 29 3b 0a 20 20 20 20  HashEntry);.    
18d0: 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69  p->nData += sqli
18e0: 74 65 33 50 75 74 56 61 72 69 6e 74 28 26 28 28  te3PutVarint(&((
18f0: 75 38 2a 29 70 29 5b 70 2d 3e 6e 44 61 74 61 5d  u8*)p)[p->nData]
1900: 2c 20 69 52 6f 77 69 64 29 3b 0a 20 20 20 20 70  , iRowid);.    p
1910: 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 3d 20 70  ->iSzPoslist = p
1920: 2d 3e 6e 44 61 74 61 3b 0a 20 20 20 20 70 2d 3e  ->nData;.    p->
1930: 6e 44 61 74 61 20 2b 3d 20 31 3b 0a 20 20 20 20  nData += 1;.    
1940: 70 2d 3e 69 52 6f 77 69 64 20 3d 20 69 52 6f 77  p->iRowid = iRow
1950: 69 64 3b 0a 20 20 20 20 70 2d 3e 70 48 61 73 68  id;.    p->pHash
1960: 4e 65 78 74 20 3d 20 70 48 61 73 68 2d 3e 61 53  Next = pHash->aS
1970: 6c 6f 74 5b 69 48 61 73 68 5d 3b 0a 20 20 20 20  lot[iHash];.    
1980: 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 48 61  pHash->aSlot[iHa
1990: 73 68 5d 20 3d 20 70 3b 0a 20 20 20 20 70 48 61  sh] = p;.    pHa
19a0: 73 68 2d 3e 6e 45 6e 74 72 79 2b 2b 3b 0a 20 20  sh->nEntry++;.  
19b0: 20 20 6e 49 6e 63 72 20 2b 3d 20 70 2d 3e 6e 44    nIncr += p->nD
19c0: 61 74 61 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 43  ata;.  }..  /* C
19d0: 68 65 63 6b 20 74 68 65 72 65 20 69 73 20 65 6e  heck there is en
19e0: 6f 75 67 68 20 73 70 61 63 65 20 74 6f 20 61 70  ough space to ap
19f0: 70 65 6e 64 20 61 20 6e 65 77 20 65 6e 74 72 79  pend a new entry
1a00: 2e 20 57 6f 72 73 74 20 63 61 73 65 20 73 63 65  . Worst case sce
1a10: 6e 61 72 69 6f 0a 20 20 2a 2a 20 69 73 3a 0a 20  nario.  ** is:. 
1a20: 20 2a 2a 0a 20 20 2a 2a 20 20 20 20 20 2b 20 39   **.  **     + 9
1a30: 20 62 79 74 65 73 20 66 6f 72 20 61 20 6e 65 77   bytes for a new
1a40: 20 72 6f 77 69 64 2c 0a 20 20 2a 2a 20 20 20 20   rowid,.  **    
1a50: 20 2b 20 34 20 62 79 74 65 20 72 65 73 65 72 76   + 4 byte reserv
1a60: 65 64 20 66 6f 72 20 74 68 65 20 22 70 6f 73 6c  ed for the "posl
1a70: 69 73 74 20 73 69 7a 65 22 20 76 61 72 69 6e 74  ist size" varint
1a80: 2e 0a 20 20 2a 2a 20 20 20 20 20 2b 20 31 20 62  ..  **     + 1 b
1a90: 79 74 65 20 66 6f 72 20 61 20 22 6e 65 77 20 63  yte for a "new c
1aa0: 6f 6c 75 6d 6e 22 20 62 79 74 65 2c 0a 20 20 2a  olumn" byte,.  *
1ab0: 2a 20 20 20 20 20 2b 20 33 20 62 79 74 65 73 20  *     + 3 bytes 
1ac0: 66 6f 72 20 61 20 6e 65 77 20 63 6f 6c 75 6d 6e  for a new column
1ad0: 20 6e 75 6d 62 65 72 20 28 31 36 2d 62 69 74 20   number (16-bit 
1ae0: 6d 61 78 29 20 61 73 20 61 20 76 61 72 69 6e 74  max) as a varint
1af0: 2c 0a 20 20 2a 2a 20 20 20 20 20 2b 20 35 20 62  ,.  **     + 5 b
1b00: 79 74 65 73 20 66 6f 72 20 74 68 65 20 6e 65 77  ytes for the new
1b10: 20 70 6f 73 69 74 69 6f 6e 20 6f 66 66 73 65 74   position offset
1b20: 20 28 33 32 2d 62 69 74 20 6d 61 78 29 2e 0a 20   (32-bit max).. 
1b30: 20 2a 2f 0a 20 20 69 66 28 20 28 70 2d 3e 6e 41   */.  if( (p->nA
1b40: 6c 6c 6f 63 20 2d 20 70 2d 3e 6e 44 61 74 61 29  lloc - p->nData)
1b50: 20 3c 20 28 39 20 2b 20 34 20 2b 20 31 20 2b 20   < (9 + 4 + 1 + 
1b60: 33 20 2b 20 35 29 20 29 7b 0a 20 20 20 20 69 6e  3 + 5) ){.    in
1b70: 74 20 6e 4e 65 77 20 3d 20 70 2d 3e 6e 41 6c 6c  t nNew = p->nAll
1b80: 6f 63 20 2a 20 32 3b 0a 20 20 20 20 46 74 73 35  oc * 2;.    Fts5
1b90: 48 61 73 68 45 6e 74 72 79 20 2a 70 4e 65 77 3b  HashEntry *pNew;
1ba0: 0a 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74  .    Fts5HashEnt
1bb0: 72 79 20 2a 2a 70 70 3b 0a 20 20 20 20 70 4e 65  ry **pp;.    pNe
1bc0: 77 20 3d 20 28 46 74 73 35 48 61 73 68 45 6e 74  w = (Fts5HashEnt
1bd0: 72 79 2a 29 73 71 6c 69 74 65 33 5f 72 65 61 6c  ry*)sqlite3_real
1be0: 6c 6f 63 28 70 2c 20 6e 4e 65 77 29 3b 0a 20 20  loc(p, nNew);.  
1bf0: 20 20 69 66 28 20 70 4e 65 77 3d 3d 30 20 29 20    if( pNew==0 ) 
1c00: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f  return SQLITE_NO
1c10: 4d 45 4d 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e  MEM;.    pNew->n
1c20: 41 6c 6c 6f 63 20 3d 20 6e 4e 65 77 3b 0a 20 20  Alloc = nNew;.  
1c30: 20 20 66 6f 72 28 70 70 3d 26 70 48 61 73 68 2d    for(pp=&pHash-
1c40: 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d 3b 20 2a  >aSlot[iHash]; *
1c50: 70 70 21 3d 70 3b 20 70 70 3d 26 28 2a 70 70 29  pp!=p; pp=&(*pp)
1c60: 2d 3e 70 48 61 73 68 4e 65 78 74 29 3b 0a 20 20  ->pHashNext);.  
1c70: 20 20 2a 70 70 20 3d 20 70 4e 65 77 3b 0a 20 20    *pp = pNew;.  
1c80: 20 20 70 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 0a    p = pNew;.  }.
1c90: 20 20 70 50 74 72 20 3d 20 28 75 38 2a 29 70 3b    pPtr = (u8*)p;
1ca0: 0a 20 20 6e 49 6e 63 72 20 2d 3d 20 70 2d 3e 6e  .  nIncr -= p->n
1cb0: 44 61 74 61 3b 0a 0a 20 20 2f 2a 20 49 66 20 74  Data;..  /* If t
1cc0: 68 69 73 20 69 73 20 61 20 6e 65 77 20 72 6f 77  his is a new row
1cd0: 69 64 2c 20 61 70 70 65 6e 64 20 74 68 65 20 34  id, append the 4
1ce0: 2d 62 79 74 65 20 73 69 7a 65 20 66 69 65 6c 64  -byte size field
1cf0: 20 66 6f 72 20 74 68 65 20 70 72 65 76 69 6f 75   for the previou
1d00: 73 0a 20 20 2a 2a 20 65 6e 74 72 79 2c 20 61 6e  s.  ** entry, an
1d10: 64 20 74 68 65 20 6e 65 77 20 72 6f 77 69 64 20  d the new rowid 
1d20: 66 6f 72 20 74 68 69 73 20 65 6e 74 72 79 2e 20  for this entry. 
1d30: 20 2a 2f 0a 20 20 69 66 28 20 69 52 6f 77 69 64   */.  if( iRowid
1d40: 21 3d 70 2d 3e 69 52 6f 77 69 64 20 29 7b 0a 20  !=p->iRowid ){. 
1d50: 20 20 20 66 74 73 35 48 61 73 68 41 64 64 50 6f     fts5HashAddPo
1d60: 73 6c 69 73 74 53 69 7a 65 28 70 29 3b 0a 20 20  slistSize(p);.  
1d70: 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71    p->nData += sq
1d80: 6c 69 74 65 33 50 75 74 56 61 72 69 6e 74 28 26  lite3PutVarint(&
1d90: 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20  pPtr[p->nData], 
1da0: 69 52 6f 77 69 64 20 2d 20 70 2d 3e 69 52 6f 77  iRowid - p->iRow
1db0: 69 64 29 3b 0a 20 20 20 20 70 2d 3e 69 53 7a 50  id);.    p->iSzP
1dc0: 6f 73 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74  oslist = p->nDat
1dd0: 61 3b 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20  a;.    p->nData 
1de0: 2b 3d 20 31 3b 0a 20 20 20 20 70 2d 3e 69 43 6f  += 1;.    p->iCo
1df0: 6c 20 3d 20 30 3b 0a 20 20 20 20 70 2d 3e 69 50  l = 0;.    p->iP
1e00: 6f 73 20 3d 20 30 3b 0a 20 20 20 20 70 2d 3e 69  os = 0;.    p->i
1e10: 52 6f 77 69 64 20 3d 20 69 52 6f 77 69 64 3b 0a  Rowid = iRowid;.
1e20: 20 20 7d 0a 0a 20 20 69 66 28 20 69 43 6f 6c 3e    }..  if( iCol>
1e30: 3d 30 20 29 7b 0a 20 20 20 20 2f 2a 20 41 70 70  =0 ){.    /* App
1e40: 65 6e 64 20 61 20 6e 65 77 20 63 6f 6c 75 6d 6e  end a new column
1e50: 20 76 61 6c 75 65 2c 20 69 66 20 6e 65 63 65 73   value, if neces
1e60: 73 61 72 79 20 2a 2f 0a 20 20 20 20 61 73 73 65  sary */.    asse
1e70: 72 74 28 20 69 43 6f 6c 3e 3d 70 2d 3e 69 43 6f  rt( iCol>=p->iCo
1e80: 6c 20 29 3b 0a 20 20 20 20 69 66 28 20 69 43 6f  l );.    if( iCo
1e90: 6c 21 3d 70 2d 3e 69 43 6f 6c 20 29 7b 0a 20 20  l!=p->iCol ){.  
1ea0: 20 20 20 20 70 50 74 72 5b 70 2d 3e 6e 44 61 74      pPtr[p->nDat
1eb0: 61 2b 2b 5d 20 3d 20 30 78 30 31 3b 0a 20 20 20  a++] = 0x01;.   
1ec0: 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73     p->nData += s
1ed0: 71 6c 69 74 65 33 50 75 74 56 61 72 69 6e 74 28  qlite3PutVarint(
1ee0: 26 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61 5d 2c  &pPtr[p->nData],
1ef0: 20 69 43 6f 6c 29 3b 0a 20 20 20 20 20 20 70 2d   iCol);.      p-
1f00: 3e 69 43 6f 6c 20 3d 20 69 43 6f 6c 3b 0a 20 20  >iCol = iCol;.  
1f10: 20 20 20 20 70 2d 3e 69 50 6f 73 20 3d 20 30 3b      p->iPos = 0;
1f20: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f 2a 20 41  .    }..    /* A
1f30: 70 70 65 6e 64 20 74 68 65 20 6e 65 77 20 70 6f  ppend the new po
1f40: 73 69 74 69 6f 6e 20 6f 66 66 73 65 74 20 2a 2f  sition offset */
1f50: 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d  .    p->nData +=
1f60: 20 73 71 6c 69 74 65 33 50 75 74 56 61 72 69 6e   sqlite3PutVarin
1f70: 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61  t(&pPtr[p->nData
1f80: 5d 2c 20 69 50 6f 73 20 2d 20 70 2d 3e 69 50 6f  ], iPos - p->iPo
1f90: 73 20 2b 20 32 29 3b 0a 20 20 20 20 70 2d 3e 69  s + 2);.    p->i
1fa0: 50 6f 73 20 3d 20 69 50 6f 73 3b 0a 20 20 7d 0a  Pos = iPos;.  }.
1fb0: 20 20 6e 49 6e 63 72 20 2b 3d 20 70 2d 3e 6e 44    nIncr += p->nD
1fc0: 61 74 61 3b 0a 0a 20 20 2a 70 48 61 73 68 2d 3e  ata;..  *pHash->
1fd0: 70 6e 42 79 74 65 20 2b 3d 20 6e 49 6e 63 72 3b  pnByte += nIncr;
1fe0: 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45  .  return SQLITE
1ff0: 5f 4f 4b 3b 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a 20 41  _OK;.}.../*.** A
2000: 72 67 75 6d 65 6e 74 73 20 70 4c 65 66 74 20 61  rguments pLeft a
2010: 6e 64 20 70 52 69 67 68 74 20 70 6f 69 6e 74 20  nd pRight point 
2020: 74 6f 20 6c 69 6e 6b 65 64 2d 6c 69 73 74 73 20  to linked-lists 
2030: 6f 66 20 68 61 73 68 2d 65 6e 74 72 79 20 6f 62  of hash-entry ob
2040: 6a 65 63 74 73 2c 0a 2a 2a 20 65 61 63 68 20 73  jects,.** each s
2050: 6f 72 74 65 64 20 69 6e 20 6b 65 79 20 6f 72 64  orted in key ord
2060: 65 72 2e 20 54 68 69 73 20 66 75 6e 63 74 69 6f  er. This functio
2070: 6e 20 6d 65 72 67 65 73 20 74 68 65 20 74 77 6f  n merges the two
2080: 20 6c 69 73 74 73 20 69 6e 74 6f 20 61 0a 2a 2a   lists into a.**
2090: 20 73 69 6e 67 6c 65 20 6c 69 73 74 20 61 6e 64   single list and
20a0: 20 72 65 74 75 72 6e 73 20 61 20 70 6f 69 6e 74   returns a point
20b0: 65 72 20 74 6f 20 69 74 73 20 66 69 72 73 74 20  er to its first 
20c0: 65 6c 65 6d 65 6e 74 2e 0a 2a 2f 0a 73 74 61 74  element..*/.stat
20d0: 69 63 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  ic Fts5HashEntry
20e0: 20 2a 66 74 73 35 48 61 73 68 45 6e 74 72 79 4d   *fts5HashEntryM
20f0: 65 72 67 65 28 0a 20 20 46 74 73 35 48 61 73 68  erge(.  Fts5Hash
2100: 45 6e 74 72 79 20 2a 70 4c 65 66 74 2c 0a 20 20  Entry *pLeft,.  
2110: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70  Fts5HashEntry *p
2120: 52 69 67 68 74 0a 29 7b 0a 20 20 46 74 73 35 48  Right.){.  Fts5H
2130: 61 73 68 45 6e 74 72 79 20 2a 70 31 20 3d 20 70  ashEntry *p1 = p
2140: 4c 65 66 74 3b 0a 20 20 46 74 73 35 48 61 73 68  Left;.  Fts5Hash
2150: 45 6e 74 72 79 20 2a 70 32 20 3d 20 70 52 69 67  Entry *p2 = pRig
2160: 68 74 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e  ht;.  Fts5HashEn
2170: 74 72 79 20 2a 70 52 65 74 20 3d 20 30 3b 0a 20  try *pRet = 0;. 
2180: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
2190: 2a 70 70 4f 75 74 20 3d 20 26 70 52 65 74 3b 0a  *ppOut = &pRet;.
21a0: 0a 20 20 77 68 69 6c 65 28 20 70 31 20 7c 7c 20  .  while( p1 || 
21b0: 70 32 20 29 7b 0a 20 20 20 20 69 66 28 20 70 31  p2 ){.    if( p1
21c0: 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 2a 70 70  ==0 ){.      *pp
21d0: 4f 75 74 20 3d 20 70 32 3b 0a 20 20 20 20 20 20  Out = p2;.      
21e0: 70 32 20 3d 20 30 3b 0a 20 20 20 20 7d 65 6c 73  p2 = 0;.    }els
21f0: 65 20 69 66 28 20 70 32 3d 3d 30 20 29 7b 0a 20  e if( p2==0 ){. 
2200: 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 70 31       *ppOut = p1
2210: 3b 0a 20 20 20 20 20 20 70 31 20 3d 20 30 3b 0a  ;.      p1 = 0;.
2220: 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20      }else{.     
2230: 20 69 6e 74 20 69 20 3d 20 30 3b 0a 20 20 20 20   int i = 0;.    
2240: 20 20 77 68 69 6c 65 28 20 70 31 2d 3e 7a 4b 65    while( p1->zKe
2250: 79 5b 69 5d 3d 3d 70 32 2d 3e 7a 4b 65 79 5b 69  y[i]==p2->zKey[i
2260: 5d 20 29 20 69 2b 2b 3b 0a 0a 20 20 20 20 20 20  ] ) i++;..      
2270: 69 66 28 20 28 28 75 38 29 70 31 2d 3e 7a 4b 65  if( ((u8)p1->zKe
2280: 79 5b 69 5d 29 3e 28 28 75 38 29 70 32 2d 3e 7a  y[i])>((u8)p2->z
2290: 4b 65 79 5b 69 5d 29 20 29 7b 0a 20 20 20 20 20  Key[i]) ){.     
22a0: 20 20 20 2f 2a 20 70 32 20 69 73 20 73 6d 61 6c     /* p2 is smal
22b0: 6c 65 72 20 2a 2f 0a 20 20 20 20 20 20 20 20 2a  ler */.        *
22c0: 70 70 4f 75 74 20 3d 20 70 32 3b 0a 20 20 20 20  ppOut = p2;.    
22d0: 20 20 20 20 70 70 4f 75 74 20 3d 20 26 70 32 2d      ppOut = &p2-
22e0: 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 20 20 20 20  >pScanNext;.    
22f0: 20 20 20 20 70 32 20 3d 20 70 32 2d 3e 70 53 63      p2 = p2->pSc
2300: 61 6e 4e 65 78 74 3b 0a 20 20 20 20 20 20 7d 65  anNext;.      }e
2310: 6c 73 65 7b 0a 20 20 20 20 20 20 20 20 2f 2a 20  lse{.        /* 
2320: 70 31 20 69 73 20 73 6d 61 6c 6c 65 72 20 2a 2f  p1 is smaller */
2330: 0a 20 20 20 20 20 20 20 20 2a 70 70 4f 75 74 20  .        *ppOut 
2340: 3d 20 70 31 3b 0a 20 20 20 20 20 20 20 20 70 70  = p1;.        pp
2350: 4f 75 74 20 3d 20 26 70 31 2d 3e 70 53 63 61 6e  Out = &p1->pScan
2360: 4e 65 78 74 3b 0a 20 20 20 20 20 20 20 20 70 31  Next;.        p1
2370: 20 3d 20 70 31 2d 3e 70 53 63 61 6e 4e 65 78 74   = p1->pScanNext
2380: 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20  ;.      }.      
2390: 2a 70 70 4f 75 74 20 3d 20 30 3b 0a 20 20 20 20  *ppOut = 0;.    
23a0: 7d 0a 20 20 7d 0a 0a 20 20 72 65 74 75 72 6e 20  }.  }..  return 
23b0: 70 52 65 74 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 45  pRet;.}../*.** E
23c0: 78 74 72 61 63 74 20 61 6c 6c 20 74 6f 6b 65 6e  xtract all token
23d0: 73 20 66 72 6f 6d 20 68 61 73 68 20 74 61 62 6c  s from hash tabl
23e0: 65 20 69 48 61 73 68 20 61 6e 64 20 6c 69 6e 6b  e iHash and link
23f0: 20 74 68 65 6d 20 69 6e 74 6f 20 61 20 6c 69 73   them into a lis
2400: 74 0a 2a 2a 20 69 6e 20 73 6f 72 74 65 64 20 6f  t.** in sorted o
2410: 72 64 65 72 2e 20 54 68 65 20 68 61 73 68 20 74  rder. The hash t
2420: 61 62 6c 65 20 69 73 20 63 6c 65 61 72 65 64 20  able is cleared 
2430: 62 65 66 6f 72 65 20 72 65 74 75 72 6e 69 6e 67  before returning
2440: 2e 20 49 74 20 69 73 0a 2a 2a 20 74 68 65 20 72  . It is.** the r
2450: 65 73 70 6f 6e 73 69 62 69 6c 69 74 79 20 6f 66  esponsibility of
2460: 20 74 68 65 20 63 61 6c 6c 65 72 20 74 6f 20 66   the caller to f
2470: 72 65 65 20 74 68 65 20 65 6c 65 6d 65 6e 74 73  ree the elements
2480: 20 6f 66 20 74 68 65 20 72 65 74 75 72 6e 65 64   of the returned
2490: 0a 2a 2a 20 6c 69 73 74 2e 0a 2a 2f 0a 73 74 61  .** list..*/.sta
24a0: 74 69 63 20 69 6e 74 20 66 74 73 35 48 61 73 68  tic int fts5Hash
24b0: 45 6e 74 72 79 53 6f 72 74 28 0a 20 20 46 74 73  EntrySort(.  Fts
24c0: 35 48 61 73 68 20 2a 70 48 61 73 68 2c 20 0a 20  5Hash *pHash, . 
24d0: 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 54 65   const char *pTe
24e0: 72 6d 2c 20 69 6e 74 20 6e 54 65 72 6d 2c 20 20  rm, int nTerm,  
24f0: 20 2f 2a 20 51 75 65 72 79 20 70 72 65 66 69 78   /* Query prefix
2500: 2c 20 69 66 20 61 6e 79 20 2a 2f 0a 20 20 46 74  , if any */.  Ft
2510: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 70 70  s5HashEntry **pp
2520: 53 6f 72 74 65 64 0a 29 7b 0a 20 20 63 6f 6e 73  Sorted.){.  cons
2530: 74 20 69 6e 74 20 6e 4d 65 72 67 65 53 6c 6f 74  t int nMergeSlot
2540: 20 3d 20 33 32 3b 0a 20 20 46 74 73 35 48 61 73   = 32;.  Fts5Has
2550: 68 45 6e 74 72 79 20 2a 2a 61 70 3b 0a 20 20 46  hEntry **ap;.  F
2560: 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 4c  ts5HashEntry *pL
2570: 69 73 74 3b 0a 20 20 69 6e 74 20 69 53 6c 6f 74  ist;.  int iSlot
2580: 3b 0a 20 20 69 6e 74 20 69 3b 0a 0a 20 20 2a 70  ;.  int i;..  *p
2590: 70 53 6f 72 74 65 64 20 3d 20 30 3b 0a 20 20 61  pSorted = 0;.  a
25a0: 70 20 3d 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c  p = sqlite3_mall
25b0: 6f 63 28 73 69 7a 65 6f 66 28 46 74 73 35 48 61  oc(sizeof(Fts5Ha
25c0: 73 68 45 6e 74 72 79 2a 29 20 2a 20 6e 4d 65 72  shEntry*) * nMer
25d0: 67 65 53 6c 6f 74 29 3b 0a 20 20 69 66 28 20 21  geSlot);.  if( !
25e0: 61 70 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49  ap ) return SQLI
25f0: 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 6d 65 6d 73  TE_NOMEM;.  mems
2600: 65 74 28 61 70 2c 20 30 2c 20 73 69 7a 65 6f 66  et(ap, 0, sizeof
2610: 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29  (Fts5HashEntry*)
2620: 20 2a 20 6e 4d 65 72 67 65 53 6c 6f 74 29 3b 0a   * nMergeSlot);.
2630: 0a 20 20 66 6f 72 28 69 53 6c 6f 74 3d 30 3b 20  .  for(iSlot=0; 
2640: 69 53 6c 6f 74 3c 70 48 61 73 68 2d 3e 6e 53 6c  iSlot<pHash->nSl
2650: 6f 74 3b 20 69 53 6c 6f 74 2b 2b 29 7b 0a 20 20  ot; iSlot++){.  
2660: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20    Fts5HashEntry 
2670: 2a 70 49 74 65 72 3b 0a 20 20 20 20 66 6f 72 28  *pIter;.    for(
2680: 70 49 74 65 72 3d 70 48 61 73 68 2d 3e 61 53 6c  pIter=pHash->aSl
2690: 6f 74 5b 69 53 6c 6f 74 5d 3b 20 70 49 74 65 72  ot[iSlot]; pIter
26a0: 3b 20 70 49 74 65 72 3d 70 49 74 65 72 2d 3e 70  ; pIter=pIter->p
26b0: 48 61 73 68 4e 65 78 74 29 7b 0a 20 20 20 20 20  HashNext){.     
26c0: 20 69 66 28 20 70 54 65 72 6d 3d 3d 30 20 7c 7c   if( pTerm==0 ||
26d0: 20 30 3d 3d 6d 65 6d 63 6d 70 28 70 49 74 65 72   0==memcmp(pIter
26e0: 2d 3e 7a 4b 65 79 2c 20 70 54 65 72 6d 2c 20 6e  ->zKey, pTerm, n
26f0: 54 65 72 6d 29 20 29 7b 0a 20 20 20 20 20 20 20  Term) ){.       
2700: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
2710: 70 45 6e 74 72 79 20 3d 20 70 49 74 65 72 3b 0a  pEntry = pIter;.
2720: 20 20 20 20 20 20 20 20 70 45 6e 74 72 79 2d 3e          pEntry->
2730: 70 53 63 61 6e 4e 65 78 74 20 3d 20 30 3b 0a 20  pScanNext = 0;. 
2740: 20 20 20 20 20 20 20 66 6f 72 28 69 3d 30 3b 20         for(i=0; 
2750: 61 70 5b 69 5d 3b 20 69 2b 2b 29 7b 0a 20 20 20  ap[i]; i++){.   
2760: 20 20 20 20 20 20 20 70 45 6e 74 72 79 20 3d 20         pEntry = 
2770: 66 74 73 35 48 61 73 68 45 6e 74 72 79 4d 65 72  fts5HashEntryMer
2780: 67 65 28 70 45 6e 74 72 79 2c 20 61 70 5b 69 5d  ge(pEntry, ap[i]
2790: 29 3b 0a 20 20 20 20 20 20 20 20 20 20 61 70 5b  );.          ap[
27a0: 69 5d 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20  i] = 0;.        
27b0: 7d 0a 20 20 20 20 20 20 20 20 61 70 5b 69 5d 20  }.        ap[i] 
27c0: 3d 20 70 45 6e 74 72 79 3b 0a 20 20 20 20 20 20  = pEntry;.      
27d0: 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 70  }.    }.  }..  p
27e0: 4c 69 73 74 20 3d 20 30 3b 0a 20 20 66 6f 72 28  List = 0;.  for(
27f0: 69 3d 30 3b 20 69 3c 6e 4d 65 72 67 65 53 6c 6f  i=0; i<nMergeSlo
2800: 74 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 70 4c 69  t; i++){.    pLi
2810: 73 74 20 3d 20 66 74 73 35 48 61 73 68 45 6e 74  st = fts5HashEnt
2820: 72 79 4d 65 72 67 65 28 70 4c 69 73 74 2c 20 61  ryMerge(pList, a
2830: 70 5b 69 5d 29 3b 0a 20 20 7d 0a 0a 20 20 70 48  p[i]);.  }..  pH
2840: 61 73 68 2d 3e 6e 45 6e 74 72 79 20 3d 20 30 3b  ash->nEntry = 0;
2850: 0a 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28  .  sqlite3_free(
2860: 61 70 29 3b 0a 20 20 2a 70 70 53 6f 72 74 65 64  ap);.  *ppSorted
2870: 20 3d 20 70 4c 69 73 74 3b 0a 20 20 72 65 74 75   = pList;.  retu
2880: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a  rn SQLITE_OK;.}.
2890: 0a 2f 2a 0a 2a 2a 20 51 75 65 72 79 20 74 68 65  ./*.** Query the
28a0: 20 68 61 73 68 20 74 61 62 6c 65 20 66 6f 72 20   hash table for 
28b0: 61 20 64 6f 63 6c 69 73 74 20 61 73 73 6f 63 69  a doclist associ
28c0: 61 74 65 64 20 77 69 74 68 20 74 65 72 6d 20 70  ated with term p
28d0: 54 65 72 6d 2f 6e 54 65 72 6d 2e 0a 2a 2f 0a 69  Term/nTerm..*/.i
28e0: 6e 74 20 73 71 6c 69 74 65 33 46 74 73 35 48 61  nt sqlite3Fts5Ha
28f0: 73 68 51 75 65 72 79 28 0a 20 20 46 74 73 35 48  shQuery(.  Fts5H
2900: 61 73 68 20 2a 70 48 61 73 68 2c 20 20 20 20 20  ash *pHash,     
2910: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 48 61             /* Ha
2920: 73 68 20 74 61 62 6c 65 20 74 6f 20 71 75 65 72  sh table to quer
2930: 79 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61  y */.  const cha
2940: 72 20 2a 70 54 65 72 6d 2c 20 69 6e 74 20 6e 54  r *pTerm, int nT
2950: 65 72 6d 2c 20 20 20 2f 2a 20 51 75 65 72 79 20  erm,   /* Query 
2960: 74 65 72 6d 20 2a 2f 0a 20 20 63 6f 6e 73 74 20  term */.  const 
2970: 75 38 20 2a 2a 70 70 44 6f 63 6c 69 73 74 2c 20  u8 **ppDoclist, 
2980: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 54            /* OUT
2990: 3a 20 50 6f 69 6e 74 65 72 20 74 6f 20 64 6f 63  : Pointer to doc
29a0: 6c 69 73 74 20 66 6f 72 20 70 54 65 72 6d 20 2a  list for pTerm *
29b0: 2f 0a 20 20 69 6e 74 20 2a 70 6e 44 6f 63 6c 69  /.  int *pnDocli
29c0: 73 74 20 20 20 20 20 20 20 20 20 20 20 20 20 20  st              
29d0: 20 20 20 20 2f 2a 20 4f 55 54 3a 20 53 69 7a 65      /* OUT: Size
29e0: 20 6f 66 20 64 6f 63 6c 69 73 74 20 69 6e 20 62   of doclist in b
29f0: 79 74 65 73 20 2a 2f 0a 29 7b 0a 20 20 75 6e 73  ytes */.){.  uns
2a00: 69 67 6e 65 64 20 69 6e 74 20 69 48 61 73 68 20  igned int iHash 
2a10: 3d 20 66 74 73 35 48 61 73 68 4b 65 79 28 70 48  = fts5HashKey(pH
2a20: 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20 70 54 65 72  ash->nSlot, pTer
2a30: 6d 2c 20 6e 54 65 72 6d 29 3b 0a 20 20 46 74 73  m, nTerm);.  Fts
2a40: 35 48 61 73 68 45 6e 74 72 79 20 2a 70 3b 0a 0a  5HashEntry *p;..
2a50: 20 20 66 6f 72 28 70 3d 70 48 61 73 68 2d 3e 61    for(p=pHash->a
2a60: 53 6c 6f 74 5b 69 48 61 73 68 5d 3b 20 70 3b 20  Slot[iHash]; p; 
2a70: 70 3d 70 2d 3e 70 48 61 73 68 4e 65 78 74 29 7b  p=p->pHashNext){
2a80: 0a 20 20 20 20 69 66 28 20 6d 65 6d 63 6d 70 28  .    if( memcmp(
2a90: 70 2d 3e 7a 4b 65 79 2c 20 70 54 65 72 6d 2c 20  p->zKey, pTerm, 
2aa0: 6e 54 65 72 6d 29 3d 3d 30 20 26 26 20 70 2d 3e  nTerm)==0 && p->
2ab0: 7a 4b 65 79 5b 6e 54 65 72 6d 5d 3d 3d 30 20 29  zKey[nTerm]==0 )
2ac0: 20 62 72 65 61 6b 3b 0a 20 20 7d 0a 0a 20 20 69   break;.  }..  i
2ad0: 66 28 20 70 20 29 7b 0a 20 20 20 20 66 74 73 35  f( p ){.    fts5
2ae0: 48 61 73 68 41 64 64 50 6f 73 6c 69 73 74 53 69  HashAddPoslistSi
2af0: 7a 65 28 70 29 3b 0a 20 20 20 20 2a 70 70 44 6f  ze(p);.    *ppDo
2b00: 63 6c 69 73 74 20 3d 20 28 63 6f 6e 73 74 20 75  clist = (const u
2b10: 38 2a 29 26 70 2d 3e 7a 4b 65 79 5b 6e 54 65 72  8*)&p->zKey[nTer
2b20: 6d 2b 31 5d 3b 0a 20 20 20 20 2a 70 6e 44 6f 63  m+1];.    *pnDoc
2b30: 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74 61 20  list = p->nData 
2b40: 2d 20 28 73 69 7a 65 6f 66 28 2a 70 29 20 2b 20  - (sizeof(*p) + 
2b50: 6e 54 65 72 6d 20 2b 20 31 29 3b 0a 20 20 7d 65  nTerm + 1);.  }e
2b60: 6c 73 65 7b 0a 20 20 20 20 2a 70 70 44 6f 63 6c  lse{.    *ppDocl
2b70: 69 73 74 20 3d 20 30 3b 0a 20 20 20 20 2a 70 6e  ist = 0;.    *pn
2b80: 44 6f 63 6c 69 73 74 20 3d 20 30 3b 0a 20 20 7d  Doclist = 0;.  }
2b90: 0a 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54  ..  return SQLIT
2ba0: 45 5f 4f 4b 3b 0a 7d 0a 0a 69 6e 74 20 73 71 6c  E_OK;.}..int sql
2bb0: 69 74 65 33 46 74 73 35 48 61 73 68 53 63 61 6e  ite3Fts5HashScan
2bc0: 49 6e 69 74 28 0a 20 20 46 74 73 35 48 61 73 68  Init(.  Fts5Hash
2bd0: 20 2a 70 2c 20 20 20 20 20 20 20 20 20 20 20 20   *p,            
2be0: 20 20 20 20 20 20 20 20 2f 2a 20 48 61 73 68 20          /* Hash 
2bf0: 74 61 62 6c 65 20 74 6f 20 71 75 65 72 79 20 2a  table to query *
2c00: 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a  /.  const char *
2c10: 70 54 65 72 6d 2c 20 69 6e 74 20 6e 54 65 72 6d  pTerm, int nTerm
2c20: 20 20 20 20 2f 2a 20 51 75 65 72 79 20 70 72 65      /* Query pre
2c30: 66 69 78 20 2a 2f 0a 29 7b 0a 20 20 72 65 74 75  fix */.){.  retu
2c40: 72 6e 20 66 74 73 35 48 61 73 68 45 6e 74 72 79  rn fts5HashEntry
2c50: 53 6f 72 74 28 70 2c 20 70 54 65 72 6d 2c 20 6e  Sort(p, pTerm, n
2c60: 54 65 72 6d 2c 20 26 70 2d 3e 70 53 63 61 6e 29  Term, &p->pScan)
2c70: 3b 0a 7d 0a 0a 76 6f 69 64 20 73 71 6c 69 74 65  ;.}..void sqlite
2c80: 33 46 74 73 35 48 61 73 68 53 63 61 6e 4e 65 78  3Fts5HashScanNex
2c90: 74 28 46 74 73 35 48 61 73 68 20 2a 70 29 7b 0a  t(Fts5Hash *p){.
2ca0: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20    Fts5HashEntry 
2cb0: 2a 70 53 63 61 6e 20 3d 20 70 2d 3e 70 53 63 61  *pScan = p->pSca
2cc0: 6e 3b 0a 20 20 69 66 28 20 70 53 63 61 6e 20 29  n;.  if( pScan )
2cd0: 20 70 2d 3e 70 53 63 61 6e 20 3d 20 70 53 63 61   p->pScan = pSca
2ce0: 6e 2d 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 7d 0a  n->pScanNext;.}.
2cf0: 0a 69 6e 74 20 73 71 6c 69 74 65 33 46 74 73 35  .int sqlite3Fts5
2d00: 48 61 73 68 53 63 61 6e 45 6f 66 28 46 74 73 35  HashScanEof(Fts5
2d10: 48 61 73 68 20 2a 70 29 7b 0a 20 20 72 65 74 75  Hash *p){.  retu
2d20: 72 6e 20 28 70 2d 3e 70 53 63 61 6e 3d 3d 30 29  rn (p->pScan==0)
2d30: 3b 0a 7d 0a 0a 76 6f 69 64 20 73 71 6c 69 74 65  ;.}..void sqlite
2d40: 33 46 74 73 35 48 61 73 68 53 63 61 6e 45 6e 74  3Fts5HashScanEnt
2d50: 72 79 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a  ry(.  Fts5Hash *
2d60: 70 48 61 73 68 2c 0a 20 20 63 6f 6e 73 74 20 63  pHash,.  const c
2d70: 68 61 72 20 2a 2a 70 7a 54 65 72 6d 2c 20 20 20  har **pzTerm,   
2d80: 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 3a           /* OUT:
2d90: 20 74 65 72 6d 20 28 6e 75 6c 2d 74 65 72 6d 69   term (nul-termi
2da0: 6e 61 74 65 64 29 20 2a 2f 0a 20 20 63 6f 6e 73  nated) */.  cons
2db0: 74 20 75 38 20 2a 2a 70 70 44 6f 63 6c 69 73 74  t u8 **ppDoclist
2dc0: 2c 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f  ,           /* O
2dd0: 55 54 3a 20 70 6f 69 6e 74 65 72 20 74 6f 20 64  UT: pointer to d
2de0: 6f 63 6c 69 73 74 20 2a 2f 0a 20 20 69 6e 74 20  oclist */.  int 
2df0: 2a 70 6e 44 6f 63 6c 69 73 74 20 20 20 20 20 20  *pnDoclist      
2e00: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f              /* O
2e10: 55 54 3a 20 73 69 7a 65 20 6f 66 20 64 6f 63 6c  UT: size of docl
2e20: 69 73 74 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a  ist in bytes */.
2e30: 29 7b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74  ){.  Fts5HashEnt
2e40: 72 79 20 2a 70 3b 0a 20 20 69 66 28 20 28 70 20  ry *p;.  if( (p 
2e50: 3d 20 70 48 61 73 68 2d 3e 70 53 63 61 6e 29 20  = pHash->pScan) 
2e60: 29 7b 0a 20 20 20 20 69 6e 74 20 6e 54 65 72 6d  ){.    int nTerm
2e70: 20 3d 20 73 74 72 6c 65 6e 28 70 2d 3e 7a 4b 65   = strlen(p->zKe
2e80: 79 29 3b 0a 20 20 20 20 66 74 73 35 48 61 73 68  y);.    fts5Hash
2e90: 41 64 64 50 6f 73 6c 69 73 74 53 69 7a 65 28 70  AddPoslistSize(p
2ea0: 29 3b 0a 20 20 20 20 2a 70 7a 54 65 72 6d 20 3d  );.    *pzTerm =
2eb0: 20 70 2d 3e 7a 4b 65 79 3b 0a 20 20 20 20 2a 70   p->zKey;.    *p
2ec0: 70 44 6f 63 6c 69 73 74 20 3d 20 28 63 6f 6e 73  pDoclist = (cons
2ed0: 74 20 75 38 2a 29 26 70 2d 3e 7a 4b 65 79 5b 6e  t u8*)&p->zKey[n
2ee0: 54 65 72 6d 2b 31 5d 3b 0a 20 20 20 20 2a 70 6e  Term+1];.    *pn
2ef0: 44 6f 63 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61  Doclist = p->nDa
2f00: 74 61 20 2d 20 28 73 69 7a 65 6f 66 28 2a 70 29  ta - (sizeof(*p)
2f10: 20 2b 20 6e 54 65 72 6d 20 2b 20 31 29 3b 0a 20   + nTerm + 1);. 
2f20: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2a 70 7a 54   }else{.    *pzT
2f30: 65 72 6d 20 3d 20 30 3b 0a 20 20 20 20 2a 70 70  erm = 0;.    *pp
2f40: 44 6f 63 6c 69 73 74 20 3d 20 30 3b 0a 20 20 20  Doclist = 0;.   
2f50: 20 2a 70 6e 44 6f 63 6c 69 73 74 20 3d 20 30 3b   *pnDoclist = 0;
2f60: 0a 20 20 7d 0a 7d 0a 0a 23 65 6e 64 69 66 20 2f  .  }.}..#endif /
2f70: 2a 20 53 51 4c 49 54 45 5f 45 4e 41 42 4c 45 5f  * SQLITE_ENABLE_
2f80: 46 54 53 35 20 2a 2f 0a                          FTS5 */.