/ Hex Artifact Content
Login

Artifact 63fa8379c5f2ac107d47c2b7d9ac04c95ef8a279:


0000: 2f 2a 0a 2a 2a 20 32 30 31 34 20 41 75 67 75 73  /*.** 2014 Augus
0010: 74 20 31 31 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61  t 11.**.** The a
0020: 75 74 68 6f 72 20 64 69 73 63 6c 61 69 6d 73 20  uthor disclaims 
0030: 63 6f 70 79 72 69 67 68 74 20 74 6f 20 74 68 69  copyright to thi
0040: 73 20 73 6f 75 72 63 65 20 63 6f 64 65 2e 20 20  s source code.  
0050: 49 6e 20 70 6c 61 63 65 20 6f 66 0a 2a 2a 20 61  In place of.** a
0060: 20 6c 65 67 61 6c 20 6e 6f 74 69 63 65 2c 20 68   legal notice, h
0070: 65 72 65 20 69 73 20 61 20 62 6c 65 73 73 69 6e  ere is a blessin
0080: 67 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 4d 61 79 20  g:.**.**    May 
0090: 79 6f 75 20 64 6f 20 67 6f 6f 64 20 61 6e 64 20  you do good and 
00a0: 6e 6f 74 20 65 76 69 6c 2e 0a 2a 2a 20 20 20 20  not evil..**    
00b0: 4d 61 79 20 79 6f 75 20 66 69 6e 64 20 66 6f 72  May you find for
00c0: 67 69 76 65 6e 65 73 73 20 66 6f 72 20 79 6f 75  giveness for you
00d0: 72 73 65 6c 66 20 61 6e 64 20 66 6f 72 67 69 76  rself and forgiv
00e0: 65 20 6f 74 68 65 72 73 2e 0a 2a 2a 20 20 20 20  e others..**    
00f0: 4d 61 79 20 79 6f 75 20 73 68 61 72 65 20 66 72  May you share fr
0100: 65 65 6c 79 2c 20 6e 65 76 65 72 20 74 61 6b 69  eely, never taki
0110: 6e 67 20 6d 6f 72 65 20 74 68 61 6e 20 79 6f 75  ng more than you
0120: 20 67 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a   give..**.******
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0170: 2a 2a 2a 2a 2a 2a 2a 2a 0a 2a 2a 0a 2a 2f 0a 0a  ********.**.*/..
0180: 23 69 6e 63 6c 75 64 65 20 22 66 74 73 35 49 6e  #include "fts5In
0190: 74 2e 68 22 0a 0a 74 79 70 65 64 65 66 20 73 74  t.h"..typedef st
01a0: 72 75 63 74 20 46 74 73 35 48 61 73 68 45 6e 74  ruct Fts5HashEnt
01b0: 72 79 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  ry Fts5HashEntry
01c0: 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20 66 69  ;../*.** This fi
01d0: 6c 65 20 63 6f 6e 74 61 69 6e 73 20 74 68 65 20  le contains the 
01e0: 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 6f  implementation o
01f0: 66 20 61 6e 20 69 6e 2d 6d 65 6d 6f 72 79 20 68  f an in-memory h
0200: 61 73 68 20 74 61 62 6c 65 20 75 73 65 64 0a 2a  ash table used.*
0210: 2a 20 74 6f 20 61 63 63 75 6d 75 6c 75 61 74 65  * to accumuluate
0220: 20 22 74 65 72 6d 20 2d 3e 20 64 6f 63 6c 69 73   "term -> doclis
0230: 74 22 20 63 6f 6e 74 65 6e 74 20 62 65 66 6f 72  t" content befor
0240: 65 20 69 74 20 69 73 20 66 6c 75 73 65 64 20 74  e it is flused t
0250: 6f 20 61 20 6c 65 76 65 6c 2d 30 0a 2a 2a 20 73  o a level-0.** s
0260: 65 67 6d 65 6e 74 2e 0a 2a 2f 0a 0a 0a 73 74 72  egment..*/...str
0270: 75 63 74 20 46 74 73 35 48 61 73 68 20 7b 0a 20  uct Fts5Hash {. 
0280: 20 69 6e 74 20 2a 70 6e 42 79 74 65 3b 20 20 20   int *pnByte;   
0290: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
02a0: 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 62   /* Pointer to b
02b0: 79 74 65 73 20 63 6f 75 6e 74 65 72 20 2a 2f 0a  ytes counter */.
02c0: 20 20 69 6e 74 20 6e 45 6e 74 72 79 3b 20 20 20    int nEntry;   
02d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
02e0: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65    /* Number of e
02f0: 6e 74 72 69 65 73 20 63 75 72 72 65 6e 74 6c 79  ntries currently
0300: 20 69 6e 20 68 61 73 68 20 2a 2f 0a 20 20 69 6e   in hash */.  in
0310: 74 20 6e 53 6c 6f 74 3b 20 20 20 20 20 20 20 20  t nSlot;        
0320: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
0330: 20 53 69 7a 65 20 6f 66 20 61 53 6c 6f 74 5b 5d   Size of aSlot[]
0340: 20 61 72 72 61 79 20 2a 2f 0a 20 20 46 74 73 35   array */.  Fts5
0350: 48 61 73 68 45 6e 74 72 79 20 2a 2a 61 53 6c 6f  HashEntry **aSlo
0360: 74 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41  t;          /* A
0370: 72 72 61 79 20 6f 66 20 68 61 73 68 20 73 6c 6f  rray of hash slo
0380: 74 73 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20  ts */.};../*.** 
0390: 45 61 63 68 20 65 6e 74 72 79 20 69 6e 20 74 68  Each entry in th
03a0: 65 20 68 61 73 68 20 74 61 62 6c 65 20 69 73 20  e hash table is 
03b0: 72 65 70 72 65 73 65 6e 74 65 64 20 62 79 20 61  represented by a
03c0: 6e 20 6f 62 6a 65 63 74 20 6f 66 20 74 68 65 20  n object of the 
03d0: 0a 2a 2a 20 66 6f 6c 6c 6f 77 69 6e 67 20 74 79  .** following ty
03e0: 70 65 2e 20 45 61 63 68 20 6f 62 6a 65 63 74 2c  pe. Each object,
03f0: 20 69 74 73 20 6b 65 79 20 28 7a 4b 65 79 5b 5d   its key (zKey[]
0400: 29 20 61 6e 64 20 69 74 73 20 63 75 72 72 65 6e  ) and its curren
0410: 74 20 64 61 74 61 0a 2a 2a 20 61 72 65 20 73 74  t data.** are st
0420: 6f 72 65 64 20 69 6e 20 61 20 73 69 6e 67 6c 65  ored in a single
0430: 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f 63 61 74 69   memory allocati
0440: 6f 6e 2e 20 54 68 65 20 70 6f 73 69 74 69 6f 6e  on. The position
0450: 20 6c 69 73 74 20 64 61 74 61 20 0a 2a 2a 20 69   list data .** i
0460: 6d 6d 65 64 69 61 74 65 6c 79 20 66 6f 6c 6c 6f  mmediately follo
0470: 77 73 20 74 68 65 20 6b 65 79 20 64 61 74 61 20  ws the key data 
0480: 69 6e 20 6d 65 6d 6f 72 79 2e 0a 2a 2a 0a 2a 2a  in memory..**.**
0490: 20 54 68 65 20 64 61 74 61 20 74 68 61 74 20 66   The data that f
04a0: 6f 6c 6c 6f 77 73 20 74 68 65 20 6b 65 79 20 69  ollows the key i
04b0: 73 20 69 6e 20 61 20 73 69 6d 69 6c 61 72 2c 20  s in a similar, 
04c0: 62 75 74 20 6e 6f 74 20 69 64 65 6e 74 69 63 61  but not identica
04d0: 6c 20 66 6f 72 6d 61 74 0a 2a 2a 20 74 6f 20 74  l format.** to t
04e0: 68 65 20 64 6f 63 6c 69 73 74 20 64 61 74 61 20  he doclist data 
04f0: 73 74 6f 72 65 64 20 69 6e 20 74 68 65 20 64 61  stored in the da
0500: 74 61 62 61 73 65 2e 20 49 74 20 69 73 3a 0a 2a  tabase. It is:.*
0510: 2a 0a 2a 2a 20 20 20 2a 20 52 6f 77 69 64 2c 20  *.**   * Rowid, 
0520: 61 73 20 61 20 76 61 72 69 6e 74 0a 2a 2a 20 20  as a varint.**  
0530: 20 2a 20 50 6f 73 69 74 69 6f 6e 20 6c 69 73 74   * Position list
0540: 2c 20 77 69 74 68 6f 75 74 20 30 78 30 30 20 74  , without 0x00 t
0550: 65 72 6d 69 6e 61 74 6f 72 2e 0a 2a 2a 20 20 20  erminator..**   
0560: 2a 20 53 69 7a 65 20 6f 66 20 70 72 65 76 69 6f  * Size of previo
0570: 75 73 20 70 6f 73 69 74 69 6f 6e 20 6c 69 73 74  us position list
0580: 20 61 6e 64 20 72 6f 77 69 64 2c 20 61 73 20 61   and rowid, as a
0590: 20 34 20 62 79 74 65 0a 2a 2a 20 20 20 20 20 62   4 byte.**     b
05a0: 69 67 2d 65 6e 64 69 61 6e 20 69 6e 74 65 67 65  ig-endian intege
05b0: 72 2e 0a 2a 2a 0a 2a 2a 20 69 52 6f 77 69 64 4f  r..**.** iRowidO
05c0: 66 66 3a 0a 2a 2a 20 20 20 4f 66 66 73 65 74 20  ff:.**   Offset 
05d0: 6f 66 20 6c 61 73 74 20 72 6f 77 69 64 20 77 72  of last rowid wr
05e0: 69 74 74 65 6e 20 74 6f 20 64 61 74 61 20 61 72  itten to data ar
05f0: 65 61 2e 20 52 65 6c 61 74 69 76 65 20 74 6f 20  ea. Relative to 
0600: 66 69 72 73 74 20 62 79 74 65 20 6f 66 0a 2a 2a  first byte of.**
0610: 20 20 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2a     structure..**
0620: 0a 2a 2a 20 6e 44 61 74 61 3a 0a 2a 2a 20 20 20  .** nData:.**   
0630: 42 79 74 65 73 20 6f 66 20 64 61 74 61 20 77 72  Bytes of data wr
0640: 69 74 74 65 6e 20 73 69 6e 63 65 20 69 52 6f 77  itten since iRow
0650: 69 64 4f 66 66 2e 0a 2a 2f 0a 73 74 72 75 63 74  idOff..*/.struct
0660: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 7b   Fts5HashEntry {
0670: 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79  .  Fts5HashEntry
0680: 20 2a 70 4e 65 78 74 3b 20 20 20 20 20 20 20 20   *pNext;        
0690: 20 20 20 2f 2a 20 4e 65 78 74 20 68 61 73 68 20     /* Next hash 
06a0: 65 6e 74 72 79 20 77 69 74 68 20 73 61 6d 65 20  entry with same 
06b0: 68 61 73 68 2d 6b 65 79 20 2a 2f 0a 20 20 0a 20  hash-key */.  . 
06c0: 20 69 6e 74 20 6e 41 6c 6c 6f 63 3b 20 20 20 20   int nAlloc;    
06d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
06e0: 20 2f 2a 20 54 6f 74 61 6c 20 73 69 7a 65 20 6f   /* Total size o
06f0: 66 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 2a 2f 0a  f allocation */.
0700: 20 20 69 6e 74 20 69 52 6f 77 69 64 4f 66 66 3b    int iRowidOff;
0710: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0720: 20 20 2f 2a 20 4f 66 66 73 65 74 20 6f 66 20 6c    /* Offset of l
0730: 61 73 74 20 72 6f 77 69 64 20 77 72 69 74 74 65  ast rowid writte
0740: 6e 20 2a 2f 0a 20 20 69 6e 74 20 6e 44 61 74 61  n */.  int nData
0750: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ;               
0760: 20 20 20 20 20 20 20 2f 2a 20 54 6f 74 61 6c 20         /* Total 
0770: 62 79 74 65 73 20 6f 66 20 64 61 74 61 20 28 69  bytes of data (i
0780: 6e 63 6c 2e 20 73 74 72 75 63 74 75 72 65 29 20  ncl. structure) 
0790: 2a 2f 0a 0a 20 20 69 6e 74 20 69 43 6f 6c 3b 20  */..  int iCol; 
07a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
07b0: 20 20 20 20 20 20 2f 2a 20 43 6f 6c 75 6d 6e 20        /* Column 
07c0: 6f 66 20 6c 61 73 74 20 76 61 6c 75 65 20 77 72  of last value wr
07d0: 69 74 74 65 6e 20 2a 2f 0a 20 20 69 6e 74 20 69  itten */.  int i
07e0: 50 6f 73 3b 20 20 20 20 20 20 20 20 20 20 20 20  Pos;            
07f0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f             /* Po
0800: 73 69 74 69 6f 6e 20 6f 66 20 6c 61 73 74 20 76  sition of last v
0810: 61 6c 75 65 20 77 72 69 74 74 65 6e 20 2a 2f 0a  alue written */.
0820: 20 20 69 36 34 20 69 52 6f 77 69 64 3b 20 20 20    i64 iRowid;   
0830: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0840: 20 20 2f 2a 20 52 6f 77 69 64 20 6f 66 20 6c 61    /* Rowid of la
0850: 73 74 20 76 61 6c 75 65 20 77 72 69 74 74 65 6e  st value written
0860: 20 2a 2f 0a 20 20 63 68 61 72 20 7a 4b 65 79 5b   */.  char zKey[
0870: 30 5d 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  0];             
0880: 20 20 20 20 20 20 2f 2a 20 4e 75 6c 2d 74 65 72        /* Nul-ter
0890: 6d 69 6e 61 74 65 64 20 65 6e 74 72 79 20 6b 65  minated entry ke
08a0: 79 20 2a 2f 0a 7d 3b 0a 0a 0a 2f 2a 0a 2a 2a 20  y */.};.../*.** 
08b0: 41 6c 6c 6f 63 61 74 65 20 61 20 6e 65 77 20 68  Allocate a new h
08c0: 61 73 68 20 74 61 62 6c 65 2e 0a 2a 2f 0a 69 6e  ash table..*/.in
08d0: 74 20 73 71 6c 69 74 65 33 46 74 73 35 48 61 73  t sqlite3Fts5Has
08e0: 68 4e 65 77 28 46 74 73 35 48 61 73 68 20 2a 2a  hNew(Fts5Hash **
08f0: 70 70 4e 65 77 2c 20 69 6e 74 20 2a 70 6e 42 79  ppNew, int *pnBy
0900: 74 65 29 7b 0a 20 20 69 6e 74 20 72 63 20 3d 20  te){.  int rc = 
0910: 53 51 4c 49 54 45 5f 4f 4b 3b 0a 20 20 46 74 73  SQLITE_OK;.  Fts
0920: 35 48 61 73 68 20 2a 70 4e 65 77 3b 0a 0a 20 20  5Hash *pNew;..  
0930: 2a 70 70 4e 65 77 20 3d 20 70 4e 65 77 20 3d 20  *ppNew = pNew = 
0940: 28 46 74 73 35 48 61 73 68 2a 29 73 71 6c 69 74  (Fts5Hash*)sqlit
0950: 65 33 5f 6d 61 6c 6c 6f 63 28 73 69 7a 65 6f 66  e3_malloc(sizeof
0960: 28 46 74 73 35 48 61 73 68 29 29 3b 0a 20 20 69  (Fts5Hash));.  i
0970: 66 28 20 70 4e 65 77 3d 3d 30 20 29 7b 0a 20 20  f( pNew==0 ){.  
0980: 20 20 72 63 20 3d 20 53 51 4c 49 54 45 5f 4e 4f    rc = SQLITE_NO
0990: 4d 45 4d 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20  MEM;.  }else{.  
09a0: 20 20 69 6e 74 20 6e 42 79 74 65 3b 0a 20 20 20    int nByte;.   
09b0: 20 6d 65 6d 73 65 74 28 70 4e 65 77 2c 20 30 2c   memset(pNew, 0,
09c0: 20 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68   sizeof(Fts5Hash
09d0: 29 29 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 70 6e  ));.    pNew->pn
09e0: 42 79 74 65 20 3d 20 70 6e 42 79 74 65 3b 0a 0a  Byte = pnByte;..
09f0: 20 20 20 20 70 4e 65 77 2d 3e 6e 53 6c 6f 74 20      pNew->nSlot 
0a00: 3d 20 31 30 32 34 3b 0a 20 20 20 20 6e 42 79 74  = 1024;.    nByt
0a10: 65 20 3d 20 73 69 7a 65 6f 66 28 46 74 73 35 48  e = sizeof(Fts5H
0a20: 61 73 68 45 6e 74 72 79 2a 29 20 2a 20 70 4e 65  ashEntry*) * pNe
0a30: 77 2d 3e 6e 53 6c 6f 74 3b 0a 20 20 20 20 70 4e  w->nSlot;.    pN
0a40: 65 77 2d 3e 61 53 6c 6f 74 20 3d 20 28 46 74 73  ew->aSlot = (Fts
0a50: 35 48 61 73 68 45 6e 74 72 79 2a 2a 29 73 71 6c  5HashEntry**)sql
0a60: 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e 42 79 74  ite3_malloc(nByt
0a70: 65 29 3b 0a 20 20 20 20 69 66 28 20 70 4e 65 77  e);.    if( pNew
0a80: 2d 3e 61 53 6c 6f 74 3d 3d 30 20 29 7b 0a 20 20  ->aSlot==0 ){.  
0a90: 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65      sqlite3_free
0aa0: 28 70 4e 65 77 29 3b 0a 20 20 20 20 20 20 2a 70  (pNew);.      *p
0ab0: 70 4e 65 77 20 3d 20 30 3b 0a 20 20 20 20 20 20  pNew = 0;.      
0ac0: 72 63 20 3d 20 53 51 4c 49 54 45 5f 4e 4f 4d 45  rc = SQLITE_NOME
0ad0: 4d 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20  M;.    }else{.  
0ae0: 20 20 20 20 6d 65 6d 73 65 74 28 70 4e 65 77 2d      memset(pNew-
0af0: 3e 61 53 6c 6f 74 2c 20 30 2c 20 6e 42 79 74 65  >aSlot, 0, nByte
0b00: 29 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 72  );.    }.  }.  r
0b10: 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a  eturn rc;.}../*.
0b20: 2a 2a 20 46 72 65 65 20 61 20 68 61 73 68 20 74  ** Free a hash t
0b30: 61 62 6c 65 20 6f 62 6a 65 63 74 2e 0a 2a 2f 0a  able object..*/.
0b40: 76 6f 69 64 20 73 71 6c 69 74 65 33 46 74 73 35  void sqlite3Fts5
0b50: 48 61 73 68 46 72 65 65 28 46 74 73 35 48 61 73  HashFree(Fts5Has
0b60: 68 20 2a 70 48 61 73 68 29 7b 0a 20 20 69 66 28  h *pHash){.  if(
0b70: 20 70 48 61 73 68 20 29 7b 0a 20 20 20 20 73 71   pHash ){.    sq
0b80: 6c 69 74 65 33 46 74 73 35 48 61 73 68 43 6c 65  lite3Fts5HashCle
0b90: 61 72 28 70 48 61 73 68 29 3b 0a 20 20 20 20 73  ar(pHash);.    s
0ba0: 71 6c 69 74 65 33 5f 66 72 65 65 28 70 48 61 73  qlite3_free(pHas
0bb0: 68 2d 3e 61 53 6c 6f 74 29 3b 0a 20 20 20 20 73  h->aSlot);.    s
0bc0: 71 6c 69 74 65 33 5f 66 72 65 65 28 70 48 61 73  qlite3_free(pHas
0bd0: 68 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a  h);.  }.}../*.**
0be0: 20 45 6d 70 74 79 20 28 62 75 74 20 64 6f 20 6e   Empty (but do n
0bf0: 6f 74 20 64 65 6c 65 74 65 29 20 61 20 68 61 73  ot delete) a has
0c00: 68 20 74 61 62 6c 65 2e 0a 2a 2f 0a 76 6f 69 64  h table..*/.void
0c10: 20 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68   sqlite3Fts5Hash
0c20: 43 6c 65 61 72 28 46 74 73 35 48 61 73 68 20 2a  Clear(Fts5Hash *
0c30: 70 48 61 73 68 29 7b 0a 20 20 69 6e 74 20 69 3b  pHash){.  int i;
0c40: 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 70 48  .  for(i=0; i<pH
0c50: 61 73 68 2d 3e 6e 53 6c 6f 74 3b 20 69 2b 2b 29  ash->nSlot; i++)
0c60: 7b 0a 20 20 20 20 69 66 28 20 70 48 61 73 68 2d  {.    if( pHash-
0c70: 3e 61 53 6c 6f 74 5b 69 5d 20 29 7b 0a 20 20 20  >aSlot[i] ){.   
0c80: 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28     sqlite3_free(
0c90: 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 5d 29  pHash->aSlot[i])
0ca0: 3b 0a 20 20 20 20 20 20 70 48 61 73 68 2d 3e 61  ;.      pHash->a
0cb0: 53 6c 6f 74 5b 69 5d 20 3d 20 30 3b 0a 20 20 20  Slot[i] = 0;.   
0cc0: 20 7d 0a 20 20 7d 0a 20 20 70 48 61 73 68 2d 3e   }.  }.  pHash->
0cd0: 6e 45 6e 74 72 79 20 3d 20 30 3b 0a 7d 0a 0a 73  nEntry = 0;.}..s
0ce0: 74 61 74 69 63 20 75 6e 73 69 67 6e 65 64 20 69  tatic unsigned i
0cf0: 6e 74 20 66 74 73 35 48 61 73 68 4b 65 79 28 69  nt fts5HashKey(i
0d00: 6e 74 20 6e 53 6c 6f 74 2c 20 63 6f 6e 73 74 20  nt nSlot, const 
0d10: 63 68 61 72 20 2a 70 2c 20 69 6e 74 20 6e 29 7b  char *p, int n){
0d20: 0a 20 20 69 6e 74 20 69 3b 0a 20 20 75 6e 73 69  .  int i;.  unsi
0d30: 67 6e 65 64 20 69 6e 74 20 68 20 3d 20 31 33 3b  gned int h = 13;
0d40: 0a 20 20 66 6f 72 28 69 3d 6e 2d 31 3b 20 69 3e  .  for(i=n-1; i>
0d50: 3d 30 3b 20 69 2d 2d 29 7b 0a 20 20 20 20 68 20  =0; i--){.    h 
0d60: 3d 20 28 68 20 3c 3c 20 33 29 20 5e 20 68 20 5e  = (h << 3) ^ h ^
0d70: 20 70 5b 69 5d 3b 0a 20 20 7d 0a 20 20 72 65 74   p[i];.  }.  ret
0d80: 75 72 6e 20 28 68 20 25 20 6e 53 6c 6f 74 29 3b  urn (h % nSlot);
0d90: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 73 69 7a 65  .}../*.** Resize
0da0: 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20   the hash table 
0db0: 62 79 20 64 6f 75 62 6c 69 6e 67 20 74 68 65 20  by doubling the 
0dc0: 6e 75 6d 62 65 72 20 6f 66 20 73 6c 6f 74 73 2e  number of slots.
0dd0: 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 66  .*/.static int f
0de0: 74 73 35 48 61 73 68 52 65 73 69 7a 65 28 46 74  ts5HashResize(Ft
0df0: 73 35 48 61 73 68 20 2a 70 48 61 73 68 29 7b 0a  s5Hash *pHash){.
0e00: 20 20 69 6e 74 20 6e 4e 65 77 20 3d 20 70 48 61    int nNew = pHa
0e10: 73 68 2d 3e 6e 53 6c 6f 74 2a 32 3b 0a 20 20 69  sh->nSlot*2;.  i
0e20: 6e 74 20 69 3b 0a 20 20 46 74 73 35 48 61 73 68  nt i;.  Fts5Hash
0e30: 45 6e 74 72 79 20 2a 2a 61 70 4e 65 77 3b 0a 20  Entry **apNew;. 
0e40: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
0e50: 2a 61 70 4f 6c 64 20 3d 20 70 48 61 73 68 2d 3e  *apOld = pHash->
0e60: 61 53 6c 6f 74 3b 0a 0a 20 20 61 70 4e 65 77 20  aSlot;..  apNew 
0e70: 3d 20 28 46 74 73 35 48 61 73 68 45 6e 74 72 79  = (Fts5HashEntry
0e80: 2a 2a 29 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f  **)sqlite3_mallo
0e90: 63 28 6e 4e 65 77 2a 73 69 7a 65 6f 66 28 46 74  c(nNew*sizeof(Ft
0ea0: 73 35 48 61 73 68 45 6e 74 72 79 2a 29 29 3b 0a  s5HashEntry*));.
0eb0: 20 20 69 66 28 20 21 61 70 4e 65 77 20 29 20 72    if( !apNew ) r
0ec0: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d  eturn SQLITE_NOM
0ed0: 45 4d 3b 0a 20 20 6d 65 6d 73 65 74 28 61 70 4e  EM;.  memset(apN
0ee0: 65 77 2c 20 30 2c 20 6e 4e 65 77 2a 73 69 7a 65  ew, 0, nNew*size
0ef0: 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79  of(Fts5HashEntry
0f00: 2a 29 29 3b 0a 0a 20 20 66 6f 72 28 69 3d 30 3b  *));..  for(i=0;
0f10: 20 69 3c 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 3b   i<pHash->nSlot;
0f20: 20 69 2b 2b 29 7b 0a 20 20 20 20 77 68 69 6c 65   i++){.    while
0f30: 28 20 61 70 4f 6c 64 5b 69 5d 20 29 7b 0a 20 20  ( apOld[i] ){.  
0f40: 20 20 20 20 69 6e 74 20 69 48 61 73 68 3b 0a 20      int iHash;. 
0f50: 20 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74       Fts5HashEnt
0f60: 72 79 20 2a 70 20 3d 20 61 70 4f 6c 64 5b 69 5d  ry *p = apOld[i]
0f70: 3b 0a 20 20 20 20 20 20 61 70 4f 6c 64 5b 69 5d  ;.      apOld[i]
0f80: 20 3d 20 70 2d 3e 70 4e 65 78 74 3b 0a 20 20 20   = p->pNext;.   
0f90: 20 20 20 69 48 61 73 68 20 3d 20 66 74 73 35 48     iHash = fts5H
0fa0: 61 73 68 4b 65 79 28 6e 4e 65 77 2c 20 70 2d 3e  ashKey(nNew, p->
0fb0: 7a 4b 65 79 2c 20 73 74 72 6c 65 6e 28 70 2d 3e  zKey, strlen(p->
0fc0: 7a 4b 65 79 29 29 3b 0a 20 20 20 20 20 20 70 2d  zKey));.      p-
0fd0: 3e 70 4e 65 78 74 20 3d 20 61 70 4e 65 77 5b 69  >pNext = apNew[i
0fe0: 48 61 73 68 5d 3b 0a 20 20 20 20 20 20 61 70 4e  Hash];.      apN
0ff0: 65 77 5b 69 48 61 73 68 5d 20 3d 20 70 3b 0a 20  ew[iHash] = p;. 
1000: 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 73 71 6c 69     }.  }..  sqli
1010: 74 65 33 5f 66 72 65 65 28 61 70 4f 6c 64 29 3b  te3_free(apOld);
1020: 0a 20 20 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 20  .  pHash->nSlot 
1030: 3d 20 6e 4e 65 77 3b 0a 20 20 70 48 61 73 68 2d  = nNew;.  pHash-
1040: 3e 61 53 6c 6f 74 20 3d 20 61 70 4e 65 77 3b 0a  >aSlot = apNew;.
1050: 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f    return SQLITE_
1060: 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 53 74 6f  OK;.}../*.** Sto
1070: 72 65 20 74 68 65 20 33 32 2d 62 69 74 20 69 6e  re the 32-bit in
1080: 74 65 67 65 72 20 70 61 73 73 65 64 20 61 73 20  teger passed as 
1090: 74 68 65 20 73 65 63 6f 6e 64 20 61 72 67 75 6d  the second argum
10a0: 65 6e 74 20 69 6e 20 62 75 66 66 65 72 20 70 2e  ent in buffer p.
10b0: 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 66  .*/.static int f
10c0: 74 73 35 50 75 74 4e 61 74 69 76 65 49 6e 74 28  ts5PutNativeInt(
10d0: 75 38 20 2a 70 2c 20 69 6e 74 20 69 29 7b 0a 20  u8 *p, int i){. 
10e0: 20 61 73 73 65 72 74 28 20 73 69 7a 65 6f 66 28   assert( sizeof(
10f0: 69 29 3d 3d 34 20 29 3b 0a 20 20 6d 65 6d 63 70  i)==4 );.  memcp
1100: 79 28 70 2c 20 26 69 2c 20 73 69 7a 65 6f 66 28  y(p, &i, sizeof(
1110: 69 29 29 3b 0a 20 20 72 65 74 75 72 6e 20 73 69  i));.  return si
1120: 7a 65 6f 66 28 69 29 3b 0a 7d 0a 0a 2f 2a 0a 2a  zeof(i);.}../*.*
1130: 2a 20 52 65 61 64 20 61 6e 64 20 72 65 74 75 72  * Read and retur
1140: 6e 20 74 68 65 20 33 32 2d 62 69 74 20 69 6e 74  n the 32-bit int
1150: 65 67 65 72 20 73 74 6f 72 65 64 20 69 6e 20 62  eger stored in b
1160: 75 66 66 65 72 20 70 2e 0a 2a 2f 0a 73 74 61 74  uffer p..*/.stat
1170: 69 63 20 69 6e 74 20 66 74 73 35 47 65 74 4e 61  ic int fts5GetNa
1180: 74 69 76 65 55 33 32 28 75 38 20 2a 70 29 7b 0a  tiveU32(u8 *p){.
1190: 20 20 69 6e 74 20 69 3b 0a 20 20 61 73 73 65 72    int i;.  asser
11a0: 74 28 20 73 69 7a 65 6f 66 28 69 29 3d 3d 34 20  t( sizeof(i)==4 
11b0: 29 3b 0a 20 20 6d 65 6d 63 70 79 28 26 69 2c 20  );.  memcpy(&i, 
11c0: 70 2c 20 73 69 7a 65 6f 66 28 69 29 29 3b 0a 20  p, sizeof(i));. 
11d0: 20 72 65 74 75 72 6e 20 69 3b 0a 7d 0a 0a 69 6e   return i;.}..in
11e0: 74 20 73 71 6c 69 74 65 33 46 74 73 35 48 61 73  t sqlite3Fts5Has
11f0: 68 57 72 69 74 65 28 0a 20 20 46 74 73 35 48 61  hWrite(.  Fts5Ha
1200: 73 68 20 2a 70 48 61 73 68 2c 0a 20 20 69 36 34  sh *pHash,.  i64
1210: 20 69 52 6f 77 69 64 2c 20 20 20 20 20 20 20 20   iRowid,        
1220: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
1230: 52 6f 77 69 64 20 66 6f 72 20 74 68 69 73 20 65  Rowid for this e
1240: 6e 74 72 79 20 2a 2f 0a 20 20 69 6e 74 20 69 43  ntry */.  int iC
1250: 6f 6c 2c 20 20 20 20 20 20 20 20 20 20 20 20 20  ol,             
1260: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 6f 6c            /* Col
1270: 75 6d 6e 20 74 6f 6b 65 6e 20 61 70 70 65 61 72  umn token appear
1280: 73 20 69 6e 20 28 2d 76 65 20 2d 3e 20 64 65 6c  s in (-ve -> del
1290: 65 74 65 29 20 2a 2f 0a 20 20 69 6e 74 20 69 50  ete) */.  int iP
12a0: 6f 73 2c 20 20 20 20 20 20 20 20 20 20 20 20 20  os,             
12b0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 73            /* Pos
12c0: 69 74 69 6f 6e 20 6f 66 20 74 6f 6b 65 6e 20 77  ition of token w
12d0: 69 74 68 69 6e 20 63 6f 6c 75 6d 6e 20 2a 2f 0a  ithin column */.
12e0: 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 54    const char *pT
12f0: 6f 6b 65 6e 2c 20 69 6e 74 20 6e 54 6f 6b 65 6e  oken, int nToken
1300: 20 20 2f 2a 20 54 6f 6b 65 6e 20 74 6f 20 61 64    /* Token to ad
1310: 64 20 6f 72 20 72 65 6d 6f 76 65 20 74 6f 20 6f  d or remove to o
1320: 72 20 66 72 6f 6d 20 69 6e 64 65 78 20 2a 2f 0a  r from index */.
1330: 29 7b 0a 20 20 75 6e 73 69 67 6e 65 64 20 69 6e  ){.  unsigned in
1340: 74 20 69 48 61 73 68 20 3d 20 66 74 73 35 48 61  t iHash = fts5Ha
1350: 73 68 4b 65 79 28 70 48 61 73 68 2d 3e 6e 53 6c  shKey(pHash->nSl
1360: 6f 74 2c 20 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b  ot, pToken, nTok
1370: 65 6e 29 3b 0a 20 20 46 74 73 35 48 61 73 68 45  en);.  Fts5HashE
1380: 6e 74 72 79 20 2a 70 3b 0a 20 20 75 38 20 2a 70  ntry *p;.  u8 *p
1390: 50 74 72 3b 0a 20 20 69 6e 74 20 6e 49 6e 63 72  Ptr;.  int nIncr
13a0: 20 3d 20 30 3b 20 20 20 20 20 20 20 20 20 20 20   = 0;           
13b0: 20 20 20 20 20 20 20 2f 2a 20 41 6d 6f 75 6e 74         /* Amount
13c0: 20 74 6f 20 69 6e 63 72 65 6d 65 6e 74 20 28 2a   to increment (*
13d0: 70 48 61 73 68 2d 3e 70 6e 42 79 74 65 29 20 62  pHash->pnByte) b
13e0: 79 20 2a 2f 0a 0a 20 20 2f 2a 20 41 74 74 65 6d  y */..  /* Attem
13f0: 70 74 20 74 6f 20 6c 6f 63 61 74 65 20 61 6e 20  pt to locate an 
1400: 65 78 69 73 74 69 6e 67 20 68 61 73 68 20 6f 62  existing hash ob
1410: 6a 65 63 74 20 2a 2f 0a 20 20 66 6f 72 28 70 3d  ject */.  for(p=
1420: 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 48 61  pHash->aSlot[iHa
1430: 73 68 5d 3b 20 70 3b 20 70 3d 70 2d 3e 70 4e 65  sh]; p; p=p->pNe
1440: 78 74 29 7b 0a 20 20 20 20 69 66 28 20 6d 65 6d  xt){.    if( mem
1450: 63 6d 70 28 70 2d 3e 7a 4b 65 79 2c 20 70 54 6f  cmp(p->zKey, pTo
1460: 6b 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3d 3d 30 20  ken, nToken)==0 
1470: 26 26 20 70 2d 3e 7a 4b 65 79 5b 6e 54 6f 6b 65  && p->zKey[nToke
1480: 6e 5d 3d 3d 30 20 29 20 62 72 65 61 6b 3b 0a 20  n]==0 ) break;. 
1490: 20 7d 0a 0a 20 20 2f 2a 20 49 66 20 61 6e 20 65   }..  /* If an e
14a0: 78 69 73 74 69 6e 67 20 68 61 73 68 20 65 6e 74  xisting hash ent
14b0: 72 79 20 63 61 6e 6e 6f 74 20 62 65 20 66 6f 75  ry cannot be fou
14c0: 6e 64 2c 20 63 72 65 61 74 65 20 61 20 6e 65 77  nd, create a new
14d0: 20 6f 6e 65 2e 20 2a 2f 0a 20 20 69 66 28 20 70   one. */.  if( p
14e0: 3d 3d 30 20 29 7b 0a 20 20 20 20 69 6e 74 20 6e  ==0 ){.    int n
14f0: 42 79 74 65 20 3d 20 73 69 7a 65 6f 66 28 46 74  Byte = sizeof(Ft
1500: 73 35 48 61 73 68 45 6e 74 72 79 29 20 2b 20 6e  s5HashEntry) + n
1510: 54 6f 6b 65 6e 20 2b 20 31 20 2b 20 36 34 3b 0a  Token + 1 + 64;.
1520: 20 20 20 20 69 66 28 20 6e 42 79 74 65 3c 31 32      if( nByte<12
1530: 38 20 29 20 6e 42 79 74 65 20 3d 20 31 32 38 3b  8 ) nByte = 128;
1540: 0a 0a 20 20 20 20 69 66 28 20 28 70 48 61 73 68  ..    if( (pHash
1550: 2d 3e 6e 45 6e 74 72 79 2a 32 29 3e 3d 70 48 61  ->nEntry*2)>=pHa
1560: 73 68 2d 3e 6e 53 6c 6f 74 20 29 7b 0a 20 20 20  sh->nSlot ){.   
1570: 20 20 20 69 6e 74 20 72 63 20 3d 20 66 74 73 35     int rc = fts5
1580: 48 61 73 68 52 65 73 69 7a 65 28 70 48 61 73 68  HashResize(pHash
1590: 29 3b 0a 20 20 20 20 20 20 69 66 28 20 72 63 21  );.      if( rc!
15a0: 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 20 72 65 74  =SQLITE_OK ) ret
15b0: 75 72 6e 20 72 63 3b 0a 20 20 20 20 20 20 69 48  urn rc;.      iH
15c0: 61 73 68 20 3d 20 66 74 73 35 48 61 73 68 4b 65  ash = fts5HashKe
15d0: 79 28 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20  y(pHash->nSlot, 
15e0: 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b  pToken, nToken);
15f0: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 70 20 3d 20  .    }..    p = 
1600: 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29  (Fts5HashEntry*)
1610: 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e  sqlite3_malloc(n
1620: 42 79 74 65 29 3b 0a 20 20 20 20 69 66 28 20 21  Byte);.    if( !
1630: 70 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54  p ) return SQLIT
1640: 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 6d 65 6d  E_NOMEM;.    mem
1650: 73 65 74 28 70 2c 20 30 2c 20 73 69 7a 65 6f 66  set(p, 0, sizeof
1660: 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 29 29  (Fts5HashEntry))
1670: 3b 0a 20 20 20 20 70 2d 3e 6e 41 6c 6c 6f 63 20  ;.    p->nAlloc 
1680: 3d 20 6e 42 79 74 65 3b 0a 20 20 20 20 6d 65 6d  = nByte;.    mem
1690: 63 70 79 28 70 2d 3e 7a 4b 65 79 2c 20 70 54 6f  cpy(p->zKey, pTo
16a0: 6b 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20  ken, nToken);.  
16b0: 20 20 70 2d 3e 7a 4b 65 79 5b 6e 54 6f 6b 65 6e    p->zKey[nToken
16c0: 5d 20 3d 20 27 5c 30 27 3b 0a 20 20 20 20 70 2d  ] = '\0';.    p-
16d0: 3e 69 52 6f 77 69 64 4f 66 66 20 3d 20 70 2d 3e  >iRowidOff = p->
16e0: 6e 44 61 74 61 20 3d 20 6e 54 6f 6b 65 6e 20 2b  nData = nToken +
16f0: 20 31 20 2b 20 73 69 7a 65 6f 66 28 46 74 73 35   1 + sizeof(Fts5
1700: 48 61 73 68 45 6e 74 72 79 29 3b 0a 20 20 20 20  HashEntry);.    
1710: 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69  p->nData += sqli
1720: 74 65 33 50 75 74 56 61 72 69 6e 74 28 26 28 28  te3PutVarint(&((
1730: 75 38 2a 29 70 29 5b 70 2d 3e 6e 44 61 74 61 5d  u8*)p)[p->nData]
1740: 2c 20 69 52 6f 77 69 64 29 3b 0a 20 20 20 20 70  , iRowid);.    p
1750: 2d 3e 69 52 6f 77 69 64 20 3d 20 69 52 6f 77 69  ->iRowid = iRowi
1760: 64 3b 0a 20 20 20 20 70 2d 3e 70 4e 65 78 74 20  d;.    p->pNext 
1770: 3d 20 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69  = pHash->aSlot[i
1780: 48 61 73 68 5d 3b 0a 20 20 20 20 70 48 61 73 68  Hash];.    pHash
1790: 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d 20 3d  ->aSlot[iHash] =
17a0: 20 70 3b 0a 20 20 20 20 70 48 61 73 68 2d 3e 6e   p;.    pHash->n
17b0: 45 6e 74 72 79 2b 2b 3b 0a 0a 20 20 20 20 6e 49  Entry++;..    nI
17c0: 6e 63 72 20 2b 3d 20 70 2d 3e 6e 44 61 74 61 3b  ncr += p->nData;
17d0: 0a 20 20 7d 0a 0a 20 20 2f 2a 20 43 68 65 63 6b  .  }..  /* Check
17e0: 20 74 68 65 72 65 20 69 73 20 65 6e 6f 75 67 68   there is enough
17f0: 20 73 70 61 63 65 20 74 6f 20 61 70 70 65 6e 64   space to append
1800: 20 61 20 6e 65 77 20 65 6e 74 72 79 2e 20 57 6f   a new entry. Wo
1810: 72 73 74 20 63 61 73 65 20 73 63 65 6e 61 72 69  rst case scenari
1820: 6f 0a 20 20 2a 2a 20 69 73 3a 0a 20 20 2a 2a 0a  o.  ** is:.  **.
1830: 20 20 2a 2a 20 20 20 20 20 2b 20 34 20 62 79 74    **     + 4 byt
1840: 65 73 20 66 6f 72 20 74 68 65 20 70 72 65 76 69  es for the previ
1850: 6f 75 73 20 65 6e 74 72 79 20 73 69 7a 65 20 66  ous entry size f
1860: 69 65 6c 64 2c 0a 20 20 2a 2a 20 20 20 20 20 2b  ield,.  **     +
1870: 20 39 20 62 79 74 65 73 20 66 6f 72 20 61 20 6e   9 bytes for a n
1880: 65 77 20 72 6f 77 69 64 2c 0a 20 20 2a 2a 20 20  ew rowid,.  **  
1890: 20 20 20 2b 20 31 20 62 79 74 65 20 66 6f 72 20     + 1 byte for 
18a0: 61 20 22 6e 65 77 20 63 6f 6c 75 6d 6e 22 20 62  a "new column" b
18b0: 79 74 65 2c 0a 20 20 2a 2a 20 20 20 20 20 2b 20  yte,.  **     + 
18c0: 33 20 62 79 74 65 73 20 66 6f 72 20 61 20 6e 65  3 bytes for a ne
18d0: 77 20 63 6f 6c 75 6d 6e 20 6e 75 6d 62 65 72 20  w column number 
18e0: 28 31 36 2d 62 69 74 20 6d 61 78 29 20 61 73 20  (16-bit max) as 
18f0: 61 20 76 61 72 69 6e 74 2c 0a 20 20 2a 2a 20 20  a varint,.  **  
1900: 20 20 20 2b 20 35 20 62 79 74 65 73 20 66 6f 72     + 5 bytes for
1910: 20 74 68 65 20 6e 65 77 20 70 6f 73 69 74 69 6f   the new positio
1920: 6e 20 6f 66 66 73 65 74 20 28 33 32 2d 62 69 74  n offset (32-bit
1930: 20 6d 61 78 29 2e 0a 20 20 2a 2f 0a 20 20 69 66   max)..  */.  if
1940: 28 20 28 70 2d 3e 6e 41 6c 6c 6f 63 20 2d 20 70  ( (p->nAlloc - p
1950: 2d 3e 6e 44 61 74 61 29 20 3c 20 28 34 20 2b 20  ->nData) < (4 + 
1960: 39 20 2b 20 31 20 2b 20 33 20 2b 20 35 29 20 29  9 + 1 + 3 + 5) )
1970: 7b 0a 20 20 20 20 69 6e 74 20 6e 4e 65 77 20 3d  {.    int nNew =
1980: 20 70 2d 3e 6e 41 6c 6c 6f 63 20 2a 20 32 3b 0a   p->nAlloc * 2;.
1990: 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74 72      Fts5HashEntr
19a0: 79 20 2a 70 4e 65 77 3b 0a 20 20 20 20 46 74 73  y *pNew;.    Fts
19b0: 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 70 70 3b  5HashEntry **pp;
19c0: 0a 20 20 20 20 70 4e 65 77 20 3d 20 28 46 74 73  .    pNew = (Fts
19d0: 35 48 61 73 68 45 6e 74 72 79 2a 29 73 71 6c 69  5HashEntry*)sqli
19e0: 74 65 33 5f 72 65 61 6c 6c 6f 63 28 70 2c 20 6e  te3_realloc(p, n
19f0: 4e 65 77 29 3b 0a 20 20 20 20 69 66 28 20 70 4e  New);.    if( pN
1a00: 65 77 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 53  ew==0 ) return S
1a10: 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 20  QLITE_NOMEM;.   
1a20: 20 70 4e 65 77 2d 3e 6e 41 6c 6c 6f 63 20 3d 20   pNew->nAlloc = 
1a30: 6e 4e 65 77 3b 0a 20 20 20 20 66 6f 72 28 70 70  nNew;.    for(pp
1a40: 3d 26 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69  =&pHash->aSlot[i
1a50: 48 61 73 68 5d 3b 20 2a 70 70 21 3d 70 3b 20 70  Hash]; *pp!=p; p
1a60: 70 3d 26 28 2a 70 70 29 2d 3e 70 4e 65 78 74 29  p=&(*pp)->pNext)
1a70: 3b 0a 20 20 20 20 2a 70 70 20 3d 20 70 4e 65 77  ;.    *pp = pNew
1a80: 3b 0a 20 20 20 20 70 20 3d 20 70 4e 65 77 3b 0a  ;.    p = pNew;.
1a90: 20 20 7d 0a 20 20 70 50 74 72 20 3d 20 28 75 38    }.  pPtr = (u8
1aa0: 2a 29 70 3b 0a 20 20 6e 49 6e 63 72 20 2d 3d 20  *)p;.  nIncr -= 
1ab0: 70 2d 3e 6e 44 61 74 61 3b 0a 0a 20 20 2f 2a 20  p->nData;..  /* 
1ac0: 49 66 20 74 68 69 73 20 69 73 20 61 20 6e 65 77  If this is a new
1ad0: 20 72 6f 77 69 64 2c 20 61 70 70 65 6e 64 20 74   rowid, append t
1ae0: 68 65 20 34 2d 62 79 74 65 20 73 69 7a 65 20 66  he 4-byte size f
1af0: 69 65 6c 64 20 66 6f 72 20 74 68 65 20 70 72 65  ield for the pre
1b00: 76 69 6f 75 73 0a 20 20 2a 2a 20 65 6e 74 72 79  vious.  ** entry
1b10: 2c 20 61 6e 64 20 74 68 65 20 6e 65 77 20 72 6f  , and the new ro
1b20: 77 69 64 20 66 6f 72 20 74 68 69 73 20 65 6e 74  wid for this ent
1b30: 72 79 2e 20 20 2a 2f 0a 20 20 69 66 28 20 69 52  ry.  */.  if( iR
1b40: 6f 77 69 64 21 3d 70 2d 3e 69 52 6f 77 69 64 20  owid!=p->iRowid 
1b50: 29 7b 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20  ){.    p->nData 
1b60: 2b 3d 20 66 74 73 35 50 75 74 4e 61 74 69 76 65  += fts5PutNative
1b70: 49 6e 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61  Int(&pPtr[p->nDa
1b80: 74 61 5d 2c 20 70 2d 3e 6e 44 61 74 61 20 2d 20  ta], p->nData - 
1b90: 70 2d 3e 69 52 6f 77 69 64 4f 66 66 29 3b 0a 20  p->iRowidOff);. 
1ba0: 20 20 20 70 2d 3e 69 52 6f 77 69 64 4f 66 66 20     p->iRowidOff 
1bb0: 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 20 20 20 20  = p->nData;.    
1bc0: 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69  p->nData += sqli
1bd0: 74 65 33 50 75 74 56 61 72 69 6e 74 28 26 70 50  te3PutVarint(&pP
1be0: 74 72 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20 69 52  tr[p->nData], iR
1bf0: 6f 77 69 64 29 3b 0a 20 20 20 20 70 2d 3e 69 43  owid);.    p->iC
1c00: 6f 6c 20 3d 20 30 3b 0a 20 20 20 20 70 2d 3e 69  ol = 0;.    p->i
1c10: 50 6f 73 20 3d 20 30 3b 0a 20 20 20 20 70 2d 3e  Pos = 0;.    p->
1c20: 69 52 6f 77 69 64 20 3d 20 69 52 6f 77 69 64 3b  iRowid = iRowid;
1c30: 0a 20 20 7d 0a 0a 20 20 69 66 28 20 69 43 6f 6c  .  }..  if( iCol
1c40: 3e 3d 30 20 29 7b 0a 20 20 20 20 2f 2a 20 41 70  >=0 ){.    /* Ap
1c50: 70 65 6e 64 20 61 20 6e 65 77 20 63 6f 6c 75 6d  pend a new colum
1c60: 6e 20 76 61 6c 75 65 2c 20 69 66 20 6e 65 63 65  n value, if nece
1c70: 73 73 61 72 79 20 2a 2f 0a 20 20 20 20 61 73 73  ssary */.    ass
1c80: 65 72 74 28 20 69 43 6f 6c 3e 3d 70 2d 3e 69 43  ert( iCol>=p->iC
1c90: 6f 6c 20 29 3b 0a 20 20 20 20 69 66 28 20 69 43  ol );.    if( iC
1ca0: 6f 6c 21 3d 70 2d 3e 69 43 6f 6c 20 29 7b 0a 20  ol!=p->iCol ){. 
1cb0: 20 20 20 20 20 70 50 74 72 5b 70 2d 3e 6e 44 61       pPtr[p->nDa
1cc0: 74 61 2b 2b 5d 20 3d 20 30 78 30 31 3b 0a 20 20  ta++] = 0x01;.  
1cd0: 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20      p->nData += 
1ce0: 73 71 6c 69 74 65 33 50 75 74 56 61 72 69 6e 74  sqlite3PutVarint
1cf0: 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61 5d  (&pPtr[p->nData]
1d00: 2c 20 69 43 6f 6c 29 3b 0a 20 20 20 20 20 20 70  , iCol);.      p
1d10: 2d 3e 69 43 6f 6c 20 3d 20 69 43 6f 6c 3b 0a 20  ->iCol = iCol;. 
1d20: 20 20 20 20 20 70 2d 3e 69 50 6f 73 20 3d 20 30       p->iPos = 0
1d30: 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f 2a 20  ;.    }..    /* 
1d40: 41 70 70 65 6e 64 20 74 68 65 20 6e 65 77 20 70  Append the new p
1d50: 6f 73 69 74 69 6f 6e 20 6f 66 66 73 65 74 20 2a  osition offset *
1d60: 2f 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b  /.    p->nData +
1d70: 3d 20 73 71 6c 69 74 65 33 50 75 74 56 61 72 69  = sqlite3PutVari
1d80: 6e 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61 74  nt(&pPtr[p->nDat
1d90: 61 5d 2c 20 69 50 6f 73 20 2d 20 70 2d 3e 69 50  a], iPos - p->iP
1da0: 6f 73 20 2b 20 32 29 3b 0a 20 20 20 20 70 2d 3e  os + 2);.    p->
1db0: 69 50 6f 73 20 3d 20 69 50 6f 73 3b 0a 20 20 7d  iPos = iPos;.  }
1dc0: 0a 20 20 6e 49 6e 63 72 20 2b 3d 20 70 2d 3e 6e  .  nIncr += p->n
1dd0: 44 61 74 61 3b 0a 0a 20 20 2a 70 48 61 73 68 2d  Data;..  *pHash-
1de0: 3e 70 6e 42 79 74 65 20 2b 3d 20 6e 49 6e 63 72  >pnByte += nIncr
1df0: 3b 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54  ;.  return SQLIT
1e00: 45 5f 4f 4b 3b 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a 20  E_OK;.}.../*.** 
1e10: 41 72 67 75 6d 65 6e 74 73 20 70 4c 65 66 74 20  Arguments pLeft 
1e20: 61 6e 64 20 70 52 69 67 68 74 20 70 6f 69 6e 74  and pRight point
1e30: 20 74 6f 20 6c 69 6e 6b 65 64 2d 6c 69 73 74 73   to linked-lists
1e40: 20 6f 66 20 68 61 73 68 2d 65 6e 74 72 79 20 6f   of hash-entry o
1e50: 62 6a 65 63 74 73 2c 0a 2a 2a 20 65 61 63 68 20  bjects,.** each 
1e60: 73 6f 72 74 65 64 20 69 6e 20 6b 65 79 20 6f 72  sorted in key or
1e70: 64 65 72 2e 20 54 68 69 73 20 66 75 6e 63 74 69  der. This functi
1e80: 6f 6e 20 6d 65 72 67 65 73 20 74 68 65 20 74 77  on merges the tw
1e90: 6f 20 6c 69 73 74 73 20 69 6e 74 6f 20 61 0a 2a  o lists into a.*
1ea0: 2a 20 73 69 6e 67 6c 65 20 6c 69 73 74 20 61 6e  * single list an
1eb0: 64 20 72 65 74 75 72 6e 73 20 61 20 70 6f 69 6e  d returns a poin
1ec0: 74 65 72 20 74 6f 20 69 74 73 20 66 69 72 73 74  ter to its first
1ed0: 20 65 6c 65 6d 65 6e 74 2e 0a 2a 2f 0a 73 74 61   element..*/.sta
1ee0: 74 69 63 20 46 74 73 35 48 61 73 68 45 6e 74 72  tic Fts5HashEntr
1ef0: 79 20 2a 66 74 73 35 48 61 73 68 45 6e 74 72 79  y *fts5HashEntry
1f00: 4d 65 72 67 65 28 0a 20 20 46 74 73 35 48 61 73  Merge(.  Fts5Has
1f10: 68 45 6e 74 72 79 20 2a 70 4c 65 66 74 2c 0a 20  hEntry *pLeft,. 
1f20: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
1f30: 70 52 69 67 68 74 0a 29 7b 0a 20 20 46 74 73 35  pRight.){.  Fts5
1f40: 48 61 73 68 45 6e 74 72 79 20 2a 70 31 20 3d 20  HashEntry *p1 = 
1f50: 70 4c 65 66 74 3b 0a 20 20 46 74 73 35 48 61 73  pLeft;.  Fts5Has
1f60: 68 45 6e 74 72 79 20 2a 70 32 20 3d 20 70 52 69  hEntry *p2 = pRi
1f70: 67 68 74 3b 0a 20 20 46 74 73 35 48 61 73 68 45  ght;.  Fts5HashE
1f80: 6e 74 72 79 20 2a 70 52 65 74 20 3d 20 30 3b 0a  ntry *pRet = 0;.
1f90: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20    Fts5HashEntry 
1fa0: 2a 2a 70 70 4f 75 74 20 3d 20 26 70 52 65 74 3b  **ppOut = &pRet;
1fb0: 0a 0a 20 20 77 68 69 6c 65 28 20 70 31 20 7c 7c  ..  while( p1 ||
1fc0: 20 70 32 20 29 7b 0a 20 20 20 20 69 66 28 20 70   p2 ){.    if( p
1fd0: 31 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 2a 70  1==0 ){.      *p
1fe0: 70 4f 75 74 20 3d 20 70 32 3b 0a 20 20 20 20 20  pOut = p2;.     
1ff0: 20 70 32 20 3d 20 30 3b 0a 20 20 20 20 7d 65 6c   p2 = 0;.    }el
2000: 73 65 20 69 66 28 20 70 32 3d 3d 30 20 29 7b 0a  se if( p2==0 ){.
2010: 20 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 70        *ppOut = p
2020: 31 3b 0a 20 20 20 20 20 20 70 31 20 3d 20 30 3b  1;.      p1 = 0;
2030: 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20  .    }else{.    
2040: 20 20 69 6e 74 20 69 20 3d 20 30 3b 0a 20 20 20    int i = 0;.   
2050: 20 20 20 77 68 69 6c 65 28 20 70 31 2d 3e 7a 4b     while( p1->zK
2060: 65 79 5b 69 5d 3d 3d 70 32 2d 3e 7a 4b 65 79 5b  ey[i]==p2->zKey[
2070: 69 5d 20 29 20 69 2b 2b 3b 0a 0a 20 20 20 20 20  i] ) i++;..     
2080: 20 69 66 28 20 28 28 75 38 29 70 31 2d 3e 7a 4b   if( ((u8)p1->zK
2090: 65 79 5b 69 5d 29 3e 28 28 75 38 29 70 32 2d 3e  ey[i])>((u8)p2->
20a0: 7a 4b 65 79 5b 69 5d 29 20 29 7b 0a 20 20 20 20  zKey[i]) ){.    
20b0: 20 20 20 20 2f 2a 20 70 32 20 69 73 20 73 6d 61      /* p2 is sma
20c0: 6c 6c 65 72 20 2a 2f 0a 20 20 20 20 20 20 20 20  ller */.        
20d0: 2a 70 70 4f 75 74 20 3d 20 70 32 3b 0a 20 20 20  *ppOut = p2;.   
20e0: 20 20 20 20 20 70 70 4f 75 74 20 3d 20 26 70 32       ppOut = &p2
20f0: 2d 3e 70 4e 65 78 74 3b 0a 20 20 20 20 20 20 20  ->pNext;.       
2100: 20 70 32 20 3d 20 70 32 2d 3e 70 4e 65 78 74 3b   p2 = p2->pNext;
2110: 0a 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20  .      }else{.  
2120: 20 20 20 20 20 20 2f 2a 20 70 31 20 69 73 20 73        /* p1 is s
2130: 6d 61 6c 6c 65 72 20 2a 2f 0a 20 20 20 20 20 20  maller */.      
2140: 20 20 2a 70 70 4f 75 74 20 3d 20 70 31 3b 0a 20    *ppOut = p1;. 
2150: 20 20 20 20 20 20 20 70 70 4f 75 74 20 3d 20 26         ppOut = &
2160: 70 31 2d 3e 70 4e 65 78 74 3b 0a 20 20 20 20 20  p1->pNext;.     
2170: 20 20 20 70 31 20 3d 20 70 31 2d 3e 70 4e 65 78     p1 = p1->pNex
2180: 74 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20  t;.      }.     
2190: 20 2a 70 70 4f 75 74 20 3d 20 30 3b 0a 20 20 20   *ppOut = 0;.   
21a0: 20 7d 0a 20 20 7d 0a 0a 20 20 72 65 74 75 72 6e   }.  }..  return
21b0: 20 70 52 65 74 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20   pRet;.}../*.** 
21c0: 45 78 74 72 61 63 74 20 61 6c 6c 20 74 6f 6b 65  Extract all toke
21d0: 6e 73 20 66 72 6f 6d 20 68 61 73 68 20 74 61 62  ns from hash tab
21e0: 6c 65 20 69 48 61 73 68 20 61 6e 64 20 6c 69 6e  le iHash and lin
21f0: 6b 20 74 68 65 6d 20 69 6e 74 6f 20 61 20 6c 69  k them into a li
2200: 73 74 0a 2a 2a 20 69 6e 20 73 6f 72 74 65 64 20  st.** in sorted 
2210: 6f 72 64 65 72 2e 20 54 68 65 20 68 61 73 68 20  order. The hash 
2220: 74 61 62 6c 65 20 69 73 20 63 6c 65 61 72 65 64  table is cleared
2230: 20 62 65 66 6f 72 65 20 72 65 74 75 72 6e 69 6e   before returnin
2240: 67 2e 20 49 74 20 69 73 0a 2a 2a 20 74 68 65 20  g. It is.** the 
2250: 72 65 73 70 6f 6e 73 69 62 69 6c 69 74 79 20 6f  responsibility o
2260: 66 20 74 68 65 20 63 61 6c 6c 65 72 20 74 6f 20  f the caller to 
2270: 66 72 65 65 20 74 68 65 20 65 6c 65 6d 65 6e 74  free the element
2280: 73 20 6f 66 20 74 68 65 20 72 65 74 75 72 6e 65  s of the returne
2290: 64 0a 2a 2a 20 6c 69 73 74 2e 0a 2a 2f 0a 73 74  d.** list..*/.st
22a0: 61 74 69 63 20 69 6e 74 20 66 74 73 35 48 61 73  atic int fts5Has
22b0: 68 45 6e 74 72 79 53 6f 72 74 28 46 74 73 35 48  hEntrySort(Fts5H
22c0: 61 73 68 20 2a 70 48 61 73 68 2c 20 46 74 73 35  ash *pHash, Fts5
22d0: 48 61 73 68 45 6e 74 72 79 20 2a 2a 70 70 53 6f  HashEntry **ppSo
22e0: 72 74 65 64 29 7b 0a 20 20 63 6f 6e 73 74 20 69  rted){.  const i
22f0: 6e 74 20 6e 4d 65 72 67 65 53 6c 6f 74 20 3d 20  nt nMergeSlot = 
2300: 33 32 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e  32;.  Fts5HashEn
2310: 74 72 79 20 2a 2a 61 70 3b 0a 20 20 46 74 73 35  try **ap;.  Fts5
2320: 48 61 73 68 45 6e 74 72 79 20 2a 70 4c 69 73 74  HashEntry *pList
2330: 3b 0a 20 20 69 6e 74 20 69 53 6c 6f 74 3b 0a 20  ;.  int iSlot;. 
2340: 20 69 6e 74 20 69 3b 0a 0a 20 20 2a 70 70 53 6f   int i;..  *ppSo
2350: 72 74 65 64 20 3d 20 30 3b 0a 20 20 61 70 20 3d  rted = 0;.  ap =
2360: 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28   sqlite3_malloc(
2370: 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45  sizeof(Fts5HashE
2380: 6e 74 72 79 2a 29 20 2a 20 6e 4d 65 72 67 65 53  ntry*) * nMergeS
2390: 6c 6f 74 29 3b 0a 20 20 69 66 28 20 21 61 70 20  lot);.  if( !ap 
23a0: 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f  ) return SQLITE_
23b0: 4e 4f 4d 45 4d 3b 0a 20 20 6d 65 6d 73 65 74 28  NOMEM;.  memset(
23c0: 61 70 2c 20 30 2c 20 73 69 7a 65 6f 66 28 46 74  ap, 0, sizeof(Ft
23d0: 73 35 48 61 73 68 45 6e 74 72 79 2a 29 20 2a 20  s5HashEntry*) * 
23e0: 6e 4d 65 72 67 65 53 6c 6f 74 29 3b 0a 0a 20 20  nMergeSlot);..  
23f0: 66 6f 72 28 69 53 6c 6f 74 3d 30 3b 20 69 53 6c  for(iSlot=0; iSl
2400: 6f 74 3c 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 3b  ot<pHash->nSlot;
2410: 20 69 53 6c 6f 74 2b 2b 29 7b 0a 20 20 20 20 77   iSlot++){.    w
2420: 68 69 6c 65 28 20 70 48 61 73 68 2d 3e 61 53 6c  hile( pHash->aSl
2430: 6f 74 5b 69 53 6c 6f 74 5d 20 29 7b 0a 20 20 20  ot[iSlot] ){.   
2440: 20 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79     Fts5HashEntry
2450: 20 2a 70 45 6e 74 72 79 20 3d 20 70 48 61 73 68   *pEntry = pHash
2460: 2d 3e 61 53 6c 6f 74 5b 69 53 6c 6f 74 5d 3b 0a  ->aSlot[iSlot];.
2470: 20 20 20 20 20 20 70 48 61 73 68 2d 3e 61 53 6c        pHash->aSl
2480: 6f 74 5b 69 53 6c 6f 74 5d 20 3d 20 70 45 6e 74  ot[iSlot] = pEnt
2490: 72 79 2d 3e 70 4e 65 78 74 3b 0a 20 20 20 20 20  ry->pNext;.     
24a0: 20 70 45 6e 74 72 79 2d 3e 70 4e 65 78 74 20 3d   pEntry->pNext =
24b0: 20 30 3b 0a 20 20 20 20 20 20 66 6f 72 28 69 3d   0;.      for(i=
24c0: 30 3b 20 61 70 5b 69 5d 3b 20 69 2b 2b 29 7b 0a  0; ap[i]; i++){.
24d0: 20 20 20 20 20 20 20 20 70 45 6e 74 72 79 20 3d          pEntry =
24e0: 20 66 74 73 35 48 61 73 68 45 6e 74 72 79 4d 65   fts5HashEntryMe
24f0: 72 67 65 28 70 45 6e 74 72 79 2c 20 61 70 5b 69  rge(pEntry, ap[i
2500: 5d 29 3b 0a 20 20 20 20 20 20 20 20 61 70 5b 69  ]);.        ap[i
2510: 5d 20 3d 20 30 3b 0a 20 20 20 20 20 20 7d 0a 20  ] = 0;.      }. 
2520: 20 20 20 20 20 61 70 5b 69 5d 20 3d 20 70 45 6e       ap[i] = pEn
2530: 74 72 79 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a  try;.    }.  }..
2540: 20 20 70 4c 69 73 74 20 3d 20 30 3b 0a 20 20 66    pList = 0;.  f
2550: 6f 72 28 69 3d 30 3b 20 69 3c 6e 4d 65 72 67 65  or(i=0; i<nMerge
2560: 53 6c 6f 74 3b 20 69 2b 2b 29 7b 0a 20 20 20 20  Slot; i++){.    
2570: 70 4c 69 73 74 20 3d 20 66 74 73 35 48 61 73 68  pList = fts5Hash
2580: 45 6e 74 72 79 4d 65 72 67 65 28 70 4c 69 73 74  EntryMerge(pList
2590: 2c 20 61 70 5b 69 5d 29 3b 0a 20 20 7d 0a 0a 20  , ap[i]);.  }.. 
25a0: 20 70 48 61 73 68 2d 3e 6e 45 6e 74 72 79 20 3d   pHash->nEntry =
25b0: 20 30 3b 0a 20 20 73 71 6c 69 74 65 33 5f 66 72   0;.  sqlite3_fr
25c0: 65 65 28 61 70 29 3b 0a 20 20 2a 70 70 53 6f 72  ee(ap);.  *ppSor
25d0: 74 65 64 20 3d 20 70 4c 69 73 74 3b 0a 20 20 72  ted = pList;.  r
25e0: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b  eturn SQLITE_OK;
25f0: 0a 7d 0a 0a 69 6e 74 20 73 71 6c 69 74 65 33 46  .}..int sqlite3F
2600: 74 73 35 48 61 73 68 49 74 65 72 61 74 65 28 0a  ts5HashIterate(.
2610: 20 20 46 74 73 35 48 61 73 68 20 2a 70 48 61 73    Fts5Hash *pHas
2620: 68 2c 0a 20 20 76 6f 69 64 20 2a 70 43 74 78 2c  h,.  void *pCtx,
2630: 0a 20 20 69 6e 74 20 28 2a 78 54 65 72 6d 29 28  .  int (*xTerm)(
2640: 76 6f 69 64 2a 2c 20 63 6f 6e 73 74 20 63 68 61  void*, const cha
2650: 72 2a 2c 20 69 6e 74 29 2c 0a 20 20 69 6e 74 20  r*, int),.  int 
2660: 28 2a 78 45 6e 74 72 79 29 28 76 6f 69 64 2a 2c  (*xEntry)(void*,
2670: 20 69 36 34 2c 20 63 6f 6e 73 74 20 75 38 2a 2c   i64, const u8*,
2680: 20 69 6e 74 29 2c 0a 20 20 69 6e 74 20 28 2a 78   int),.  int (*x
2690: 54 65 72 6d 44 6f 6e 65 29 28 76 6f 69 64 2a 29  TermDone)(void*)
26a0: 0a 29 7b 0a 20 20 46 74 73 35 48 61 73 68 45 6e  .){.  Fts5HashEn
26b0: 74 72 79 20 2a 70 4c 69 73 74 3b 0a 20 20 69 6e  try *pList;.  in
26c0: 74 20 72 63 3b 0a 0a 20 20 72 63 20 3d 20 66 74  t rc;..  rc = ft
26d0: 73 35 48 61 73 68 45 6e 74 72 79 53 6f 72 74 28  s5HashEntrySort(
26e0: 70 48 61 73 68 2c 20 26 70 4c 69 73 74 29 3b 0a  pHash, &pList);.
26f0: 20 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45    if( rc==SQLITE
2700: 5f 4f 4b 20 29 7b 0a 20 20 20 20 77 68 69 6c 65  _OK ){.    while
2710: 28 20 70 4c 69 73 74 20 29 7b 0a 20 20 20 20 20  ( pList ){.     
2720: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
2730: 70 4e 65 78 74 20 3d 20 70 4c 69 73 74 2d 3e 70  pNext = pList->p
2740: 4e 65 78 74 3b 0a 20 20 20 20 20 20 69 66 28 20  Next;.      if( 
2750: 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 29 7b  rc==SQLITE_OK ){
2760: 0a 20 20 20 20 20 20 20 20 75 38 20 2a 70 50 74  .        u8 *pPt
2770: 72 20 3d 20 28 75 38 2a 29 70 4c 69 73 74 3b 0a  r = (u8*)pList;.
2780: 20 20 20 20 20 20 20 20 69 6e 74 20 6e 4b 65 79          int nKey
2790: 20 3d 20 73 74 72 6c 65 6e 28 70 4c 69 73 74 2d   = strlen(pList-
27a0: 3e 7a 4b 65 79 29 3b 0a 20 20 20 20 20 20 20 20  >zKey);.        
27b0: 69 6e 74 20 69 4f 66 66 20 3d 20 70 4c 69 73 74  int iOff = pList
27c0: 2d 3e 69 52 6f 77 69 64 4f 66 66 3b 0a 20 20 20  ->iRowidOff;.   
27d0: 20 20 20 20 20 69 6e 74 20 69 45 6e 64 20 3d 20       int iEnd = 
27e0: 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45  sizeof(Fts5HashE
27f0: 6e 74 72 79 29 20 2b 20 6e 4b 65 79 20 2b 20 31  ntry) + nKey + 1
2800: 3b 0a 20 20 20 20 20 20 20 20 69 6e 74 20 6e 42  ;.        int nB
2810: 79 74 65 20 3d 20 70 4c 69 73 74 2d 3e 6e 44 61  yte = pList->nDa
2820: 74 61 20 2d 20 70 4c 69 73 74 2d 3e 69 52 6f 77  ta - pList->iRow
2830: 69 64 4f 66 66 3b 0a 0a 20 20 20 20 20 20 20 20  idOff;..        
2840: 72 63 20 3d 20 78 54 65 72 6d 28 70 43 74 78 2c  rc = xTerm(pCtx,
2850: 20 70 4c 69 73 74 2d 3e 7a 4b 65 79 2c 20 6e 4b   pList->zKey, nK
2860: 65 79 29 3b 0a 20 20 20 20 20 20 20 20 77 68 69  ey);.        whi
2870: 6c 65 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f  le( rc==SQLITE_O
2880: 4b 20 26 26 20 69 4f 66 66 20 29 7b 0a 20 20 20  K && iOff ){.   
2890: 20 20 20 20 20 20 20 69 6e 74 20 6e 56 61 72 69         int nVari
28a0: 6e 74 3b 0a 20 20 20 20 20 20 20 20 20 20 69 36  nt;.          i6
28b0: 34 20 69 52 6f 77 69 64 3b 0a 20 20 20 20 20 20  4 iRowid;.      
28c0: 20 20 20 20 6e 56 61 72 69 6e 74 20 3d 20 67 65      nVarint = ge
28d0: 74 56 61 72 69 6e 74 28 26 70 50 74 72 5b 69 4f  tVarint(&pPtr[iO
28e0: 66 66 5d 2c 20 28 75 36 34 2a 29 26 69 52 6f 77  ff], (u64*)&iRow
28f0: 69 64 29 3b 0a 20 20 20 20 20 20 20 20 20 20 72  id);.          r
2900: 63 20 3d 20 78 45 6e 74 72 79 28 70 43 74 78 2c  c = xEntry(pCtx,
2910: 20 69 52 6f 77 69 64 2c 20 26 70 50 74 72 5b 69   iRowid, &pPtr[i
2920: 4f 66 66 2b 6e 56 61 72 69 6e 74 5d 2c 20 6e 42  Off+nVarint], nB
2930: 79 74 65 2d 6e 56 61 72 69 6e 74 29 3b 0a 20 20  yte-nVarint);.  
2940: 20 20 20 20 20 20 20 20 69 66 28 20 69 4f 66 66          if( iOff
2950: 3d 3d 69 45 6e 64 20 29 7b 0a 20 20 20 20 20 20  ==iEnd ){.      
2960: 20 20 20 20 20 20 69 4f 66 66 20 3d 20 30 3b 0a        iOff = 0;.
2970: 20 20 20 20 20 20 20 20 20 20 7d 65 6c 73 65 7b            }else{
2980: 0a 20 20 20 20 20 20 20 20 20 20 20 20 6e 42 79  .            nBy
2990: 74 65 20 3d 20 66 74 73 35 47 65 74 4e 61 74 69  te = fts5GetNati
29a0: 76 65 55 33 32 28 26 70 50 74 72 5b 69 4f 66 66  veU32(&pPtr[iOff
29b0: 2d 73 69 7a 65 6f 66 28 69 6e 74 29 5d 29 3b 0a  -sizeof(int)]);.
29c0: 20 20 20 20 20 20 20 20 20 20 20 20 69 4f 66 66              iOff
29d0: 20 3d 20 69 4f 66 66 20 2d 20 73 69 7a 65 6f 66   = iOff - sizeof
29e0: 28 69 6e 74 29 20 2d 20 6e 42 79 74 65 3b 0a 20  (int) - nByte;. 
29f0: 20 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20           }.     
2a00: 20 20 20 7d 0a 20 20 20 20 20 20 20 20 69 66 28     }.        if(
2a10: 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f 4b 20 29   rc==SQLITE_OK )
2a20: 7b 0a 20 20 20 20 20 20 20 20 20 20 72 63 20 3d  {.          rc =
2a30: 20 78 54 65 72 6d 44 6f 6e 65 28 70 43 74 78 29   xTermDone(pCtx)
2a40: 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20  ;.        }.    
2a50: 20 20 7d 0a 20 20 20 20 20 20 73 71 6c 69 74 65    }.      sqlite
2a60: 33 5f 66 72 65 65 28 70 4c 69 73 74 29 3b 0a 20  3_free(pList);. 
2a70: 20 20 20 20 20 70 4c 69 73 74 20 3d 20 70 4e 65       pList = pNe
2a80: 78 74 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20  xt;.    }.  }.  
2a90: 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 0a 0a  return rc;.}....