/ Hex Artifact Content
Login

Artifact 4ab952b75f27d5ed3ef0f3b4f7fa1464744483e8:


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 53 7a 50 6f 73 6c 69 73 74    int iSzPoslist
0710: 3b 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 73    /* Offset of s
0730: 70 61 63 65 20 66 6f 72 20 34 2d 62 79 74 65 20  pace for 4-byte 
0740: 70 6f 73 6c 69 73 74 20 73 69 7a 65 20 2a 2f 0a  poslist size */.
0750: 20 20 69 6e 74 20 6e 44 61 74 61 3b 20 20 20 20    int nData;    
0760: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0770: 20 20 2f 2a 20 54 6f 74 61 6c 20 62 79 74 65 73    /* Total bytes
0780: 20 6f 66 20 64 61 74 61 20 28 69 6e 63 6c 2e 20   of data (incl. 
0790: 73 74 72 75 63 74 75 72 65 29 20 2a 2f 0a 0a 20  structure) */.. 
07a0: 20 69 6e 74 20 69 43 6f 6c 3b 20 20 20 20 20 20   int iCol;      
07b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
07c0: 20 2f 2a 20 43 6f 6c 75 6d 6e 20 6f 66 20 6c 61   /* Column of la
07d0: 73 74 20 76 61 6c 75 65 20 77 72 69 74 74 65 6e  st value written
07e0: 20 2a 2f 0a 20 20 69 6e 74 20 69 50 6f 73 3b 20   */.  int iPos; 
07f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0800: 20 20 20 20 20 20 2f 2a 20 50 6f 73 69 74 69 6f        /* Positio
0810: 6e 20 6f 66 20 6c 61 73 74 20 76 61 6c 75 65 20  n of last value 
0820: 77 72 69 74 74 65 6e 20 2a 2f 0a 20 20 69 36 34  written */.  i64
0830: 20 69 52 6f 77 69 64 3b 20 20 20 20 20 20 20 20   iRowid;        
0840: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
0850: 52 6f 77 69 64 20 6f 66 20 6c 61 73 74 20 76 61  Rowid of last va
0860: 6c 75 65 20 77 72 69 74 74 65 6e 20 2a 2f 0a 20  lue written */. 
0870: 20 63 68 61 72 20 7a 4b 65 79 5b 30 5d 3b 20 20   char zKey[0];  
0880: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0890: 20 2f 2a 20 4e 75 6c 2d 74 65 72 6d 69 6e 61 74   /* Nul-terminat
08a0: 65 64 20 65 6e 74 72 79 20 6b 65 79 20 2a 2f 0a  ed entry key */.
08b0: 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 46 6f 72 6d 61 74  };../*.** Format
08c0: 20 76 61 6c 75 65 20 69 56 61 6c 20 61 73 20 61   value iVal as a
08d0: 20 34 2d 62 79 74 65 20 76 61 72 69 6e 74 20 61   4-byte varint a
08e0: 6e 64 20 77 72 69 74 65 20 69 74 20 74 6f 20 62  nd write it to b
08f0: 75 66 66 65 72 20 61 5b 5d 2e 20 34 20 62 79 74  uffer a[]. 4 byt
0900: 65 73 0a 2a 2a 20 61 72 65 20 75 73 65 64 20 65  es.** are used e
0910: 76 65 6e 20 69 66 20 74 68 65 20 76 61 6c 75 65  ven if the value
0920: 20 63 6f 75 6c 64 20 66 69 74 20 69 6e 20 61 20   could fit in a 
0930: 73 6d 61 6c 6c 65 72 20 61 6d 6f 75 6e 74 20 6f  smaller amount o
0940: 66 20 73 70 61 63 65 2e 20 0a 2a 2f 0a 73 74 61  f space. .*/.sta
0950: 74 69 63 20 76 6f 69 64 20 66 74 73 35 50 75 74  tic void fts5Put
0960: 34 42 79 74 65 56 61 72 69 6e 74 28 75 38 20 2a  4ByteVarint(u8 *
0970: 61 2c 20 69 6e 74 20 69 56 61 6c 29 7b 0a 20 20  a, int iVal){.  
0980: 61 5b 30 5d 20 3d 20 28 30 78 38 30 20 7c 20 28  a[0] = (0x80 | (
0990: 75 38 29 28 69 56 61 6c 20 3e 3e 20 32 31 29 29  u8)(iVal >> 21))
09a0: 3b 0a 20 20 61 5b 31 5d 20 3d 20 28 30 78 38 30  ;.  a[1] = (0x80
09b0: 20 7c 20 28 75 38 29 28 69 56 61 6c 20 3e 3e 20   | (u8)(iVal >> 
09c0: 31 34 29 29 3b 0a 20 20 61 5b 32 5d 20 3d 20 28  14));.  a[2] = (
09d0: 30 78 38 30 20 7c 20 28 75 38 29 28 69 56 61 6c  0x80 | (u8)(iVal
09e0: 20 3e 3e 20 20 37 29 29 3b 0a 20 20 61 5b 33 5d   >>  7));.  a[3]
09f0: 20 3d 20 28 30 78 37 46 20 26 20 28 75 38 29 28   = (0x7F & (u8)(
0a00: 69 56 61 6c 29 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  iVal));.}../*.**
0a10: 20 41 6c 6c 6f 63 61 74 65 20 61 20 6e 65 77 20   Allocate a new 
0a20: 68 61 73 68 20 74 61 62 6c 65 2e 0a 2a 2f 0a 69  hash table..*/.i
0a30: 6e 74 20 73 71 6c 69 74 65 33 46 74 73 35 48 61  nt sqlite3Fts5Ha
0a40: 73 68 4e 65 77 28 46 74 73 35 48 61 73 68 20 2a  shNew(Fts5Hash *
0a50: 2a 70 70 4e 65 77 2c 20 69 6e 74 20 2a 70 6e 42  *ppNew, int *pnB
0a60: 79 74 65 29 7b 0a 20 20 69 6e 74 20 72 63 20 3d  yte){.  int rc =
0a70: 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 20 20 46 74   SQLITE_OK;.  Ft
0a80: 73 35 48 61 73 68 20 2a 70 4e 65 77 3b 0a 0a 20  s5Hash *pNew;.. 
0a90: 20 2a 70 70 4e 65 77 20 3d 20 70 4e 65 77 20 3d   *ppNew = pNew =
0aa0: 20 28 46 74 73 35 48 61 73 68 2a 29 73 71 6c 69   (Fts5Hash*)sqli
0ab0: 74 65 33 5f 6d 61 6c 6c 6f 63 28 73 69 7a 65 6f  te3_malloc(sizeo
0ac0: 66 28 46 74 73 35 48 61 73 68 29 29 3b 0a 20 20  f(Fts5Hash));.  
0ad0: 69 66 28 20 70 4e 65 77 3d 3d 30 20 29 7b 0a 20  if( pNew==0 ){. 
0ae0: 20 20 20 72 63 20 3d 20 53 51 4c 49 54 45 5f 4e     rc = SQLITE_N
0af0: 4f 4d 45 4d 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20  OMEM;.  }else{. 
0b00: 20 20 20 69 6e 74 20 6e 42 79 74 65 3b 0a 20 20     int nByte;.  
0b10: 20 20 6d 65 6d 73 65 74 28 70 4e 65 77 2c 20 30    memset(pNew, 0
0b20: 2c 20 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73  , sizeof(Fts5Has
0b30: 68 29 29 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 70  h));.    pNew->p
0b40: 6e 42 79 74 65 20 3d 20 70 6e 42 79 74 65 3b 0a  nByte = pnByte;.
0b50: 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 53 6c 6f 74  .    pNew->nSlot
0b60: 20 3d 20 31 30 32 34 3b 0a 20 20 20 20 6e 42 79   = 1024;.    nBy
0b70: 74 65 20 3d 20 73 69 7a 65 6f 66 28 46 74 73 35  te = sizeof(Fts5
0b80: 48 61 73 68 45 6e 74 72 79 2a 29 20 2a 20 70 4e  HashEntry*) * pN
0b90: 65 77 2d 3e 6e 53 6c 6f 74 3b 0a 20 20 20 20 70  ew->nSlot;.    p
0ba0: 4e 65 77 2d 3e 61 53 6c 6f 74 20 3d 20 28 46 74  New->aSlot = (Ft
0bb0: 73 35 48 61 73 68 45 6e 74 72 79 2a 2a 29 73 71  s5HashEntry**)sq
0bc0: 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e 42 79  lite3_malloc(nBy
0bd0: 74 65 29 3b 0a 20 20 20 20 69 66 28 20 70 4e 65  te);.    if( pNe
0be0: 77 2d 3e 61 53 6c 6f 74 3d 3d 30 20 29 7b 0a 20  w->aSlot==0 ){. 
0bf0: 20 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65       sqlite3_fre
0c00: 65 28 70 4e 65 77 29 3b 0a 20 20 20 20 20 20 2a  e(pNew);.      *
0c10: 70 70 4e 65 77 20 3d 20 30 3b 0a 20 20 20 20 20  ppNew = 0;.     
0c20: 20 72 63 20 3d 20 53 51 4c 49 54 45 5f 4e 4f 4d   rc = SQLITE_NOM
0c30: 45 4d 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20  EM;.    }else{. 
0c40: 20 20 20 20 20 6d 65 6d 73 65 74 28 70 4e 65 77       memset(pNew
0c50: 2d 3e 61 53 6c 6f 74 2c 20 30 2c 20 6e 42 79 74  ->aSlot, 0, nByt
0c60: 65 29 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20  e);.    }.  }.  
0c70: 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a 2f 2a  return rc;.}../*
0c80: 0a 2a 2a 20 46 72 65 65 20 61 20 68 61 73 68 20  .** Free a hash 
0c90: 74 61 62 6c 65 20 6f 62 6a 65 63 74 2e 0a 2a 2f  table object..*/
0ca0: 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 46 74 73  .void sqlite3Fts
0cb0: 35 48 61 73 68 46 72 65 65 28 46 74 73 35 48 61  5HashFree(Fts5Ha
0cc0: 73 68 20 2a 70 48 61 73 68 29 7b 0a 20 20 69 66  sh *pHash){.  if
0cd0: 28 20 70 48 61 73 68 20 29 7b 0a 20 20 20 20 73  ( pHash ){.    s
0ce0: 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 43 6c  qlite3Fts5HashCl
0cf0: 65 61 72 28 70 48 61 73 68 29 3b 0a 20 20 20 20  ear(pHash);.    
0d00: 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70 48 61  sqlite3_free(pHa
0d10: 73 68 2d 3e 61 53 6c 6f 74 29 3b 0a 20 20 20 20  sh->aSlot);.    
0d20: 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70 48 61  sqlite3_free(pHa
0d30: 73 68 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a  sh);.  }.}../*.*
0d40: 2a 20 45 6d 70 74 79 20 28 62 75 74 20 64 6f 20  * Empty (but do 
0d50: 6e 6f 74 20 64 65 6c 65 74 65 29 20 61 20 68 61  not delete) a ha
0d60: 73 68 20 74 61 62 6c 65 2e 0a 2a 2f 0a 76 6f 69  sh table..*/.voi
0d70: 64 20 73 71 6c 69 74 65 33 46 74 73 35 48 61 73  d sqlite3Fts5Has
0d80: 68 43 6c 65 61 72 28 46 74 73 35 48 61 73 68 20  hClear(Fts5Hash 
0d90: 2a 70 48 61 73 68 29 7b 0a 20 20 69 6e 74 20 69  *pHash){.  int i
0da0: 3b 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 70  ;.  for(i=0; i<p
0db0: 48 61 73 68 2d 3e 6e 53 6c 6f 74 3b 20 69 2b 2b  Hash->nSlot; i++
0dc0: 29 7b 0a 20 20 20 20 46 74 73 35 48 61 73 68 45  ){.    Fts5HashE
0dd0: 6e 74 72 79 20 2a 70 4e 65 78 74 3b 0a 20 20 20  ntry *pNext;.   
0de0: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a   Fts5HashEntry *
0df0: 70 53 6c 6f 74 3b 0a 20 20 20 20 66 6f 72 28 70  pSlot;.    for(p
0e00: 53 6c 6f 74 3d 70 48 61 73 68 2d 3e 61 53 6c 6f  Slot=pHash->aSlo
0e10: 74 5b 69 5d 3b 20 70 53 6c 6f 74 3b 20 70 53 6c  t[i]; pSlot; pSl
0e20: 6f 74 3d 70 4e 65 78 74 29 7b 0a 20 20 20 20 20  ot=pNext){.     
0e30: 20 70 4e 65 78 74 20 3d 20 70 53 6c 6f 74 2d 3e   pNext = pSlot->
0e40: 70 4e 65 78 74 3b 0a 20 20 20 20 20 20 73 71 6c  pNext;.      sql
0e50: 69 74 65 33 5f 66 72 65 65 28 70 53 6c 6f 74 29  ite3_free(pSlot)
0e60: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 6d 65  ;.    }.  }.  me
0e70: 6d 73 65 74 28 70 48 61 73 68 2d 3e 61 53 6c 6f  mset(pHash->aSlo
0e80: 74 2c 20 30 2c 20 70 48 61 73 68 2d 3e 6e 53 6c  t, 0, pHash->nSl
0e90: 6f 74 20 2a 20 73 69 7a 65 6f 66 28 46 74 73 35  ot * sizeof(Fts5
0ea0: 48 61 73 68 45 6e 74 72 79 2a 29 29 3b 0a 20 20  HashEntry*));.  
0eb0: 70 48 61 73 68 2d 3e 6e 45 6e 74 72 79 20 3d 20  pHash->nEntry = 
0ec0: 30 3b 0a 7d 0a 0a 73 74 61 74 69 63 20 75 6e 73  0;.}..static uns
0ed0: 69 67 6e 65 64 20 69 6e 74 20 66 74 73 35 48 61  igned int fts5Ha
0ee0: 73 68 4b 65 79 28 69 6e 74 20 6e 53 6c 6f 74 2c  shKey(int nSlot,
0ef0: 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 2c 20   const char *p, 
0f00: 69 6e 74 20 6e 29 7b 0a 20 20 69 6e 74 20 69 3b  int n){.  int i;
0f10: 0a 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20  .  unsigned int 
0f20: 68 20 3d 20 31 33 3b 0a 20 20 66 6f 72 28 69 3d  h = 13;.  for(i=
0f30: 6e 2d 31 3b 20 69 3e 3d 30 3b 20 69 2d 2d 29 7b  n-1; i>=0; i--){
0f40: 0a 20 20 20 20 68 20 3d 20 28 68 20 3c 3c 20 33  .    h = (h << 3
0f50: 29 20 5e 20 68 20 5e 20 70 5b 69 5d 3b 0a 20 20  ) ^ h ^ p[i];.  
0f60: 7d 0a 20 20 72 65 74 75 72 6e 20 28 68 20 25 20  }.  return (h % 
0f70: 6e 53 6c 6f 74 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  nSlot);.}../*.**
0f80: 20 52 65 73 69 7a 65 20 74 68 65 20 68 61 73 68   Resize the hash
0f90: 20 74 61 62 6c 65 20 62 79 20 64 6f 75 62 6c 69   table by doubli
0fa0: 6e 67 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66  ng the number of
0fb0: 20 73 6c 6f 74 73 2e 0a 2a 2f 0a 73 74 61 74 69   slots..*/.stati
0fc0: 63 20 69 6e 74 20 66 74 73 35 48 61 73 68 52 65  c int fts5HashRe
0fd0: 73 69 7a 65 28 46 74 73 35 48 61 73 68 20 2a 70  size(Fts5Hash *p
0fe0: 48 61 73 68 29 7b 0a 20 20 69 6e 74 20 6e 4e 65  Hash){.  int nNe
0ff0: 77 20 3d 20 70 48 61 73 68 2d 3e 6e 53 6c 6f 74  w = pHash->nSlot
1000: 2a 32 3b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 46  *2;.  int i;.  F
1010: 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 61  ts5HashEntry **a
1020: 70 4e 65 77 3b 0a 20 20 46 74 73 35 48 61 73 68  pNew;.  Fts5Hash
1030: 45 6e 74 72 79 20 2a 2a 61 70 4f 6c 64 20 3d 20  Entry **apOld = 
1040: 70 48 61 73 68 2d 3e 61 53 6c 6f 74 3b 0a 0a 20  pHash->aSlot;.. 
1050: 20 61 70 4e 65 77 20 3d 20 28 46 74 73 35 48 61   apNew = (Fts5Ha
1060: 73 68 45 6e 74 72 79 2a 2a 29 73 71 6c 69 74 65  shEntry**)sqlite
1070: 33 5f 6d 61 6c 6c 6f 63 28 6e 4e 65 77 2a 73 69  3_malloc(nNew*si
1080: 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74  zeof(Fts5HashEnt
1090: 72 79 2a 29 29 3b 0a 20 20 69 66 28 20 21 61 70  ry*));.  if( !ap
10a0: 4e 65 77 20 29 20 72 65 74 75 72 6e 20 53 51 4c  New ) return SQL
10b0: 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 6d 65 6d  ITE_NOMEM;.  mem
10c0: 73 65 74 28 61 70 4e 65 77 2c 20 30 2c 20 6e 4e  set(apNew, 0, nN
10d0: 65 77 2a 73 69 7a 65 6f 66 28 46 74 73 35 48 61  ew*sizeof(Fts5Ha
10e0: 73 68 45 6e 74 72 79 2a 29 29 3b 0a 0a 20 20 66  shEntry*));..  f
10f0: 6f 72 28 69 3d 30 3b 20 69 3c 70 48 61 73 68 2d  or(i=0; i<pHash-
1100: 3e 6e 53 6c 6f 74 3b 20 69 2b 2b 29 7b 0a 20 20  >nSlot; i++){.  
1110: 20 20 77 68 69 6c 65 28 20 61 70 4f 6c 64 5b 69    while( apOld[i
1120: 5d 20 29 7b 0a 20 20 20 20 20 20 69 6e 74 20 69  ] ){.      int i
1130: 48 61 73 68 3b 0a 20 20 20 20 20 20 46 74 73 35  Hash;.      Fts5
1140: 48 61 73 68 45 6e 74 72 79 20 2a 70 20 3d 20 61  HashEntry *p = a
1150: 70 4f 6c 64 5b 69 5d 3b 0a 20 20 20 20 20 20 61  pOld[i];.      a
1160: 70 4f 6c 64 5b 69 5d 20 3d 20 70 2d 3e 70 4e 65  pOld[i] = p->pNe
1170: 78 74 3b 0a 20 20 20 20 20 20 69 48 61 73 68 20  xt;.      iHash 
1180: 3d 20 66 74 73 35 48 61 73 68 4b 65 79 28 6e 4e  = fts5HashKey(nN
1190: 65 77 2c 20 70 2d 3e 7a 4b 65 79 2c 20 73 74 72  ew, p->zKey, str
11a0: 6c 65 6e 28 70 2d 3e 7a 4b 65 79 29 29 3b 0a 20  len(p->zKey));. 
11b0: 20 20 20 20 20 70 2d 3e 70 4e 65 78 74 20 3d 20       p->pNext = 
11c0: 61 70 4e 65 77 5b 69 48 61 73 68 5d 3b 0a 20 20  apNew[iHash];.  
11d0: 20 20 20 20 61 70 4e 65 77 5b 69 48 61 73 68 5d      apNew[iHash]
11e0: 20 3d 20 70 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a   = p;.    }.  }.
11f0: 0a 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28  .  sqlite3_free(
1200: 61 70 4f 6c 64 29 3b 0a 20 20 70 48 61 73 68 2d  apOld);.  pHash-
1210: 3e 6e 53 6c 6f 74 20 3d 20 6e 4e 65 77 3b 0a 20  >nSlot = nNew;. 
1220: 20 70 48 61 73 68 2d 3e 61 53 6c 6f 74 20 3d 20   pHash->aSlot = 
1230: 61 70 4e 65 77 3b 0a 20 20 72 65 74 75 72 6e 20  apNew;.  return 
1240: 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 69 6e  SQLITE_OK;.}..in
1250: 74 20 73 71 6c 69 74 65 33 46 74 73 35 48 61 73  t sqlite3Fts5Has
1260: 68 57 72 69 74 65 28 0a 20 20 46 74 73 35 48 61  hWrite(.  Fts5Ha
1270: 73 68 20 2a 70 48 61 73 68 2c 0a 20 20 69 36 34  sh *pHash,.  i64
1280: 20 69 52 6f 77 69 64 2c 20 20 20 20 20 20 20 20   iRowid,        
1290: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
12a0: 52 6f 77 69 64 20 66 6f 72 20 74 68 69 73 20 65  Rowid for this e
12b0: 6e 74 72 79 20 2a 2f 0a 20 20 69 6e 74 20 69 43  ntry */.  int iC
12c0: 6f 6c 2c 20 20 20 20 20 20 20 20 20 20 20 20 20  ol,             
12d0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 6f 6c            /* Col
12e0: 75 6d 6e 20 74 6f 6b 65 6e 20 61 70 70 65 61 72  umn token appear
12f0: 73 20 69 6e 20 28 2d 76 65 20 2d 3e 20 64 65 6c  s in (-ve -> del
1300: 65 74 65 29 20 2a 2f 0a 20 20 69 6e 74 20 69 50  ete) */.  int iP
1310: 6f 73 2c 20 20 20 20 20 20 20 20 20 20 20 20 20  os,             
1320: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 73            /* Pos
1330: 69 74 69 6f 6e 20 6f 66 20 74 6f 6b 65 6e 20 77  ition of token w
1340: 69 74 68 69 6e 20 63 6f 6c 75 6d 6e 20 2a 2f 0a  ithin column */.
1350: 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 54    const char *pT
1360: 6f 6b 65 6e 2c 20 69 6e 74 20 6e 54 6f 6b 65 6e  oken, int nToken
1370: 20 20 2f 2a 20 54 6f 6b 65 6e 20 74 6f 20 61 64    /* Token to ad
1380: 64 20 6f 72 20 72 65 6d 6f 76 65 20 74 6f 20 6f  d or remove to o
1390: 72 20 66 72 6f 6d 20 69 6e 64 65 78 20 2a 2f 0a  r from index */.
13a0: 29 7b 0a 20 20 75 6e 73 69 67 6e 65 64 20 69 6e  ){.  unsigned in
13b0: 74 20 69 48 61 73 68 20 3d 20 66 74 73 35 48 61  t iHash = fts5Ha
13c0: 73 68 4b 65 79 28 70 48 61 73 68 2d 3e 6e 53 6c  shKey(pHash->nSl
13d0: 6f 74 2c 20 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b  ot, pToken, nTok
13e0: 65 6e 29 3b 0a 20 20 46 74 73 35 48 61 73 68 45  en);.  Fts5HashE
13f0: 6e 74 72 79 20 2a 70 3b 0a 20 20 75 38 20 2a 70  ntry *p;.  u8 *p
1400: 50 74 72 3b 0a 20 20 69 6e 74 20 6e 49 6e 63 72  Ptr;.  int nIncr
1410: 20 3d 20 30 3b 20 20 20 20 20 20 20 20 20 20 20   = 0;           
1420: 20 20 20 20 20 20 20 2f 2a 20 41 6d 6f 75 6e 74         /* Amount
1430: 20 74 6f 20 69 6e 63 72 65 6d 65 6e 74 20 28 2a   to increment (*
1440: 70 48 61 73 68 2d 3e 70 6e 42 79 74 65 29 20 62  pHash->pnByte) b
1450: 79 20 2a 2f 0a 0a 20 20 2f 2a 20 41 74 74 65 6d  y */..  /* Attem
1460: 70 74 20 74 6f 20 6c 6f 63 61 74 65 20 61 6e 20  pt to locate an 
1470: 65 78 69 73 74 69 6e 67 20 68 61 73 68 20 65 6e  existing hash en
1480: 74 72 79 20 2a 2f 0a 20 20 66 6f 72 28 70 3d 70  try */.  for(p=p
1490: 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 48 61 73  Hash->aSlot[iHas
14a0: 68 5d 3b 20 70 3b 20 70 3d 70 2d 3e 70 4e 65 78  h]; p; p=p->pNex
14b0: 74 29 7b 0a 20 20 20 20 69 66 28 20 6d 65 6d 63  t){.    if( memc
14c0: 6d 70 28 70 2d 3e 7a 4b 65 79 2c 20 70 54 6f 6b  mp(p->zKey, pTok
14d0: 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3d 3d 30 20 26  en, nToken)==0 &
14e0: 26 20 70 2d 3e 7a 4b 65 79 5b 6e 54 6f 6b 65 6e  & p->zKey[nToken
14f0: 5d 3d 3d 30 20 29 20 62 72 65 61 6b 3b 0a 20 20  ]==0 ) break;.  
1500: 7d 0a 0a 20 20 2f 2a 20 49 66 20 61 6e 20 65 78  }..  /* If an ex
1510: 69 73 74 69 6e 67 20 68 61 73 68 20 65 6e 74 72  isting hash entr
1520: 79 20 63 61 6e 6e 6f 74 20 62 65 20 66 6f 75 6e  y cannot be foun
1530: 64 2c 20 63 72 65 61 74 65 20 61 20 6e 65 77 20  d, create a new 
1540: 6f 6e 65 2e 20 2a 2f 0a 20 20 69 66 28 20 70 3d  one. */.  if( p=
1550: 3d 30 20 29 7b 0a 20 20 20 20 69 6e 74 20 6e 42  =0 ){.    int nB
1560: 79 74 65 20 3d 20 73 69 7a 65 6f 66 28 46 74 73  yte = sizeof(Fts
1570: 35 48 61 73 68 45 6e 74 72 79 29 20 2b 20 6e 54  5HashEntry) + nT
1580: 6f 6b 65 6e 20 2b 20 31 20 2b 20 36 34 3b 0a 20  oken + 1 + 64;. 
1590: 20 20 20 69 66 28 20 6e 42 79 74 65 3c 31 32 38     if( nByte<128
15a0: 20 29 20 6e 42 79 74 65 20 3d 20 31 32 38 3b 0a   ) nByte = 128;.
15b0: 0a 20 20 20 20 69 66 28 20 28 70 48 61 73 68 2d  .    if( (pHash-
15c0: 3e 6e 45 6e 74 72 79 2a 32 29 3e 3d 70 48 61 73  >nEntry*2)>=pHas
15d0: 68 2d 3e 6e 53 6c 6f 74 20 29 7b 0a 20 20 20 20  h->nSlot ){.    
15e0: 20 20 69 6e 74 20 72 63 20 3d 20 66 74 73 35 48    int rc = fts5H
15f0: 61 73 68 52 65 73 69 7a 65 28 70 48 61 73 68 29  ashResize(pHash)
1600: 3b 0a 20 20 20 20 20 20 69 66 28 20 72 63 21 3d  ;.      if( rc!=
1610: 53 51 4c 49 54 45 5f 4f 4b 20 29 20 72 65 74 75  SQLITE_OK ) retu
1620: 72 6e 20 72 63 3b 0a 20 20 20 20 20 20 69 48 61  rn rc;.      iHa
1630: 73 68 20 3d 20 66 74 73 35 48 61 73 68 4b 65 79  sh = fts5HashKey
1640: 28 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20 70  (pHash->nSlot, p
1650: 54 6f 6b 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a  Token, nToken);.
1660: 20 20 20 20 7d 0a 0a 20 20 20 20 70 20 3d 20 28      }..    p = (
1670: 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29 73  Fts5HashEntry*)s
1680: 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e 42  qlite3_malloc(nB
1690: 79 74 65 29 3b 0a 20 20 20 20 69 66 28 20 21 70  yte);.    if( !p
16a0: 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45   ) return SQLITE
16b0: 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 6d 65 6d 73  _NOMEM;.    mems
16c0: 65 74 28 70 2c 20 30 2c 20 73 69 7a 65 6f 66 28  et(p, 0, sizeof(
16d0: 46 74 73 35 48 61 73 68 45 6e 74 72 79 29 29 3b  Fts5HashEntry));
16e0: 0a 20 20 20 20 70 2d 3e 6e 41 6c 6c 6f 63 20 3d  .    p->nAlloc =
16f0: 20 6e 42 79 74 65 3b 0a 20 20 20 20 6d 65 6d 63   nByte;.    memc
1700: 70 79 28 70 2d 3e 7a 4b 65 79 2c 20 70 54 6f 6b  py(p->zKey, pTok
1710: 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 20  en, nToken);.   
1720: 20 70 2d 3e 7a 4b 65 79 5b 6e 54 6f 6b 65 6e 5d   p->zKey[nToken]
1730: 20 3d 20 27 5c 30 27 3b 0a 20 20 20 20 70 2d 3e   = '\0';.    p->
1740: 6e 44 61 74 61 20 3d 20 6e 54 6f 6b 65 6e 20 2b  nData = nToken +
1750: 20 31 20 2b 20 73 69 7a 65 6f 66 28 46 74 73 35   1 + sizeof(Fts5
1760: 48 61 73 68 45 6e 74 72 79 29 3b 0a 20 20 20 20  HashEntry);.    
1770: 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69  p->nData += sqli
1780: 74 65 33 50 75 74 56 61 72 69 6e 74 28 26 28 28  te3PutVarint(&((
1790: 75 38 2a 29 70 29 5b 70 2d 3e 6e 44 61 74 61 5d  u8*)p)[p->nData]
17a0: 2c 20 69 52 6f 77 69 64 29 3b 0a 20 20 20 20 70  , iRowid);.    p
17b0: 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 3d 20 70  ->iSzPoslist = p
17c0: 2d 3e 6e 44 61 74 61 3b 0a 20 20 20 20 70 2d 3e  ->nData;.    p->
17d0: 6e 44 61 74 61 20 2b 3d 20 34 3b 0a 20 20 20 20  nData += 4;.    
17e0: 70 2d 3e 69 52 6f 77 69 64 20 3d 20 69 52 6f 77  p->iRowid = iRow
17f0: 69 64 3b 0a 20 20 20 20 70 2d 3e 70 4e 65 78 74  id;.    p->pNext
1800: 20 3d 20 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b   = pHash->aSlot[
1810: 69 48 61 73 68 5d 3b 0a 20 20 20 20 70 48 61 73  iHash];.    pHas
1820: 68 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d 20  h->aSlot[iHash] 
1830: 3d 20 70 3b 0a 20 20 20 20 70 48 61 73 68 2d 3e  = p;.    pHash->
1840: 6e 45 6e 74 72 79 2b 2b 3b 0a 20 20 20 20 6e 49  nEntry++;.    nI
1850: 6e 63 72 20 2b 3d 20 70 2d 3e 6e 44 61 74 61 3b  ncr += p->nData;
1860: 0a 20 20 7d 0a 0a 20 20 2f 2a 20 43 68 65 63 6b  .  }..  /* Check
1870: 20 74 68 65 72 65 20 69 73 20 65 6e 6f 75 67 68   there is enough
1880: 20 73 70 61 63 65 20 74 6f 20 61 70 70 65 6e 64   space to append
1890: 20 61 20 6e 65 77 20 65 6e 74 72 79 2e 20 57 6f   a new entry. Wo
18a0: 72 73 74 20 63 61 73 65 20 73 63 65 6e 61 72 69  rst case scenari
18b0: 6f 0a 20 20 2a 2a 20 69 73 3a 0a 20 20 2a 2a 0a  o.  ** is:.  **.
18c0: 20 20 2a 2a 20 20 20 20 20 2b 20 39 20 62 79 74    **     + 9 byt
18d0: 65 73 20 66 6f 72 20 61 20 6e 65 77 20 72 6f 77  es for a new row
18e0: 69 64 2c 0a 20 20 2a 2a 20 20 20 20 20 2b 20 34  id,.  **     + 4
18f0: 20 62 79 74 65 73 20 72 65 73 65 72 76 65 64 20   bytes reserved 
1900: 66 6f 72 20 74 68 65 20 22 70 6f 73 6c 69 73 74  for the "poslist
1910: 20 73 69 7a 65 22 20 76 61 72 69 6e 74 2e 0a 20   size" varint.. 
1920: 20 2a 2a 20 20 20 20 20 2b 20 31 20 62 79 74 65   **     + 1 byte
1930: 20 66 6f 72 20 61 20 22 6e 65 77 20 63 6f 6c 75   for a "new colu
1940: 6d 6e 22 20 62 79 74 65 2c 0a 20 20 2a 2a 20 20  mn" byte,.  **  
1950: 20 20 20 2b 20 33 20 62 79 74 65 73 20 66 6f 72     + 3 bytes for
1960: 20 61 20 6e 65 77 20 63 6f 6c 75 6d 6e 20 6e 75   a new column nu
1970: 6d 62 65 72 20 28 31 36 2d 62 69 74 20 6d 61 78  mber (16-bit max
1980: 29 20 61 73 20 61 20 76 61 72 69 6e 74 2c 0a 20  ) as a varint,. 
1990: 20 2a 2a 20 20 20 20 20 2b 20 35 20 62 79 74 65   **     + 5 byte
19a0: 73 20 66 6f 72 20 74 68 65 20 6e 65 77 20 70 6f  s for the new po
19b0: 73 69 74 69 6f 6e 20 6f 66 66 73 65 74 20 28 33  sition offset (3
19c0: 32 2d 62 69 74 20 6d 61 78 29 2e 0a 20 20 2a 2f  2-bit max)..  */
19d0: 0a 20 20 69 66 28 20 28 70 2d 3e 6e 41 6c 6c 6f  .  if( (p->nAllo
19e0: 63 20 2d 20 70 2d 3e 6e 44 61 74 61 29 20 3c 20  c - p->nData) < 
19f0: 28 39 20 2b 20 34 20 2b 20 31 20 2b 20 33 20 2b  (9 + 4 + 1 + 3 +
1a00: 20 35 29 20 29 7b 0a 20 20 20 20 69 6e 74 20 6e   5) ){.    int n
1a10: 4e 65 77 20 3d 20 70 2d 3e 6e 41 6c 6c 6f 63 20  New = p->nAlloc 
1a20: 2a 20 32 3b 0a 20 20 20 20 46 74 73 35 48 61 73  * 2;.    Fts5Has
1a30: 68 45 6e 74 72 79 20 2a 70 4e 65 77 3b 0a 20 20  hEntry *pNew;.  
1a40: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20    Fts5HashEntry 
1a50: 2a 2a 70 70 3b 0a 20 20 20 20 70 4e 65 77 20 3d  **pp;.    pNew =
1a60: 20 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a   (Fts5HashEntry*
1a70: 29 73 71 6c 69 74 65 33 5f 72 65 61 6c 6c 6f 63  )sqlite3_realloc
1a80: 28 70 2c 20 6e 4e 65 77 29 3b 0a 20 20 20 20 69  (p, nNew);.    i
1a90: 66 28 20 70 4e 65 77 3d 3d 30 20 29 20 72 65 74  f( pNew==0 ) ret
1aa0: 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d  urn SQLITE_NOMEM
1ab0: 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 41 6c 6c  ;.    pNew->nAll
1ac0: 6f 63 20 3d 20 6e 4e 65 77 3b 0a 20 20 20 20 66  oc = nNew;.    f
1ad0: 6f 72 28 70 70 3d 26 70 48 61 73 68 2d 3e 61 53  or(pp=&pHash->aS
1ae0: 6c 6f 74 5b 69 48 61 73 68 5d 3b 20 2a 70 70 21  lot[iHash]; *pp!
1af0: 3d 70 3b 20 70 70 3d 26 28 2a 70 70 29 2d 3e 70  =p; pp=&(*pp)->p
1b00: 4e 65 78 74 29 3b 0a 20 20 20 20 2a 70 70 20 3d  Next);.    *pp =
1b10: 20 70 4e 65 77 3b 0a 20 20 20 20 70 20 3d 20 70   pNew;.    p = p
1b20: 4e 65 77 3b 0a 20 20 7d 0a 20 20 70 50 74 72 20  New;.  }.  pPtr 
1b30: 3d 20 28 75 38 2a 29 70 3b 0a 20 20 6e 49 6e 63  = (u8*)p;.  nInc
1b40: 72 20 2d 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a 0a  r -= p->nData;..
1b50: 20 20 2f 2a 20 49 66 20 74 68 69 73 20 69 73 20    /* If this is 
1b60: 61 20 6e 65 77 20 72 6f 77 69 64 2c 20 61 70 70  a new rowid, app
1b70: 65 6e 64 20 74 68 65 20 34 2d 62 79 74 65 20 73  end the 4-byte s
1b80: 69 7a 65 20 66 69 65 6c 64 20 66 6f 72 20 74 68  ize field for th
1b90: 65 20 70 72 65 76 69 6f 75 73 0a 20 20 2a 2a 20  e previous.  ** 
1ba0: 65 6e 74 72 79 2c 20 61 6e 64 20 74 68 65 20 6e  entry, and the n
1bb0: 65 77 20 72 6f 77 69 64 20 66 6f 72 20 74 68 69  ew rowid for thi
1bc0: 73 20 65 6e 74 72 79 2e 20 20 2a 2f 0a 20 20 69  s entry.  */.  i
1bd0: 66 28 20 69 52 6f 77 69 64 21 3d 70 2d 3e 69 52  f( iRowid!=p->iR
1be0: 6f 77 69 64 20 29 7b 0a 20 20 20 20 61 73 73 65  owid ){.    asse
1bf0: 72 74 28 20 70 2d 3e 69 53 7a 50 6f 73 6c 69 73  rt( p->iSzPoslis
1c00: 74 3e 30 20 29 3b 0a 20 20 20 20 66 74 73 35 50  t>0 );.    fts5P
1c10: 75 74 34 42 79 74 65 56 61 72 69 6e 74 28 26 70  ut4ByteVarint(&p
1c20: 50 74 72 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69 73  Ptr[p->iSzPoslis
1c30: 74 5d 2c 20 70 2d 3e 6e 44 61 74 61 20 2d 20 70  t], p->nData - p
1c40: 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 2d 20 34  ->iSzPoslist - 4
1c50: 29 3b 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20  );.    p->nData 
1c60: 2b 3d 20 73 71 6c 69 74 65 33 50 75 74 56 61 72  += sqlite3PutVar
1c70: 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61  int(&pPtr[p->nDa
1c80: 74 61 5d 2c 20 69 52 6f 77 69 64 20 2d 20 70 2d  ta], iRowid - p-
1c90: 3e 69 52 6f 77 69 64 29 3b 0a 20 20 20 20 70 2d  >iRowid);.    p-
1ca0: 3e 69 53 7a 50 6f 73 6c 69 73 74 20 3d 20 70 2d  >iSzPoslist = p-
1cb0: 3e 6e 44 61 74 61 3b 0a 20 20 20 20 70 2d 3e 6e  >nData;.    p->n
1cc0: 44 61 74 61 20 2b 3d 20 34 3b 0a 20 20 20 20 70  Data += 4;.    p
1cd0: 2d 3e 69 43 6f 6c 20 3d 20 30 3b 0a 20 20 20 20  ->iCol = 0;.    
1ce0: 70 2d 3e 69 50 6f 73 20 3d 20 30 3b 0a 20 20 20  p->iPos = 0;.   
1cf0: 20 70 2d 3e 69 52 6f 77 69 64 20 3d 20 69 52 6f   p->iRowid = iRo
1d00: 77 69 64 3b 0a 20 20 7d 0a 0a 20 20 69 66 28 20  wid;.  }..  if( 
1d10: 69 43 6f 6c 3e 3d 30 20 29 7b 0a 20 20 20 20 2f  iCol>=0 ){.    /
1d20: 2a 20 41 70 70 65 6e 64 20 61 20 6e 65 77 20 63  * Append a new c
1d30: 6f 6c 75 6d 6e 20 76 61 6c 75 65 2c 20 69 66 20  olumn value, if 
1d40: 6e 65 63 65 73 73 61 72 79 20 2a 2f 0a 20 20 20  necessary */.   
1d50: 20 61 73 73 65 72 74 28 20 69 43 6f 6c 3e 3d 70   assert( iCol>=p
1d60: 2d 3e 69 43 6f 6c 20 29 3b 0a 20 20 20 20 69 66  ->iCol );.    if
1d70: 28 20 69 43 6f 6c 21 3d 70 2d 3e 69 43 6f 6c 20  ( iCol!=p->iCol 
1d80: 29 7b 0a 20 20 20 20 20 20 70 50 74 72 5b 70 2d  ){.      pPtr[p-
1d90: 3e 6e 44 61 74 61 2b 2b 5d 20 3d 20 30 78 30 31  >nData++] = 0x01
1da0: 3b 0a 20 20 20 20 20 20 70 2d 3e 6e 44 61 74 61  ;.      p->nData
1db0: 20 2b 3d 20 73 71 6c 69 74 65 33 50 75 74 56 61   += sqlite3PutVa
1dc0: 72 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44  rint(&pPtr[p->nD
1dd0: 61 74 61 5d 2c 20 69 43 6f 6c 29 3b 0a 20 20 20  ata], iCol);.   
1de0: 20 20 20 70 2d 3e 69 43 6f 6c 20 3d 20 69 43 6f     p->iCol = iCo
1df0: 6c 3b 0a 20 20 20 20 20 20 70 2d 3e 69 50 6f 73  l;.      p->iPos
1e00: 20 3d 20 30 3b 0a 20 20 20 20 7d 0a 0a 20 20 20   = 0;.    }..   
1e10: 20 2f 2a 20 41 70 70 65 6e 64 20 74 68 65 20 6e   /* Append the n
1e20: 65 77 20 70 6f 73 69 74 69 6f 6e 20 6f 66 66 73  ew position offs
1e30: 65 74 20 2a 2f 0a 20 20 20 20 70 2d 3e 6e 44 61  et */.    p->nDa
1e40: 74 61 20 2b 3d 20 73 71 6c 69 74 65 33 50 75 74  ta += sqlite3Put
1e50: 56 61 72 69 6e 74 28 26 70 50 74 72 5b 70 2d 3e  Varint(&pPtr[p->
1e60: 6e 44 61 74 61 5d 2c 20 69 50 6f 73 20 2d 20 70  nData], iPos - p
1e70: 2d 3e 69 50 6f 73 20 2b 20 32 29 3b 0a 20 20 20  ->iPos + 2);.   
1e80: 20 70 2d 3e 69 50 6f 73 20 3d 20 69 50 6f 73 3b   p->iPos = iPos;
1e90: 0a 20 20 7d 0a 20 20 6e 49 6e 63 72 20 2b 3d 20  .  }.  nIncr += 
1ea0: 70 2d 3e 6e 44 61 74 61 3b 0a 0a 20 20 2a 70 48  p->nData;..  *pH
1eb0: 61 73 68 2d 3e 70 6e 42 79 74 65 20 2b 3d 20 6e  ash->pnByte += n
1ec0: 49 6e 63 72 3b 0a 20 20 72 65 74 75 72 6e 20 53  Incr;.  return S
1ed0: 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 0a 2f 2a  QLITE_OK;.}.../*
1ee0: 0a 2a 2a 20 41 72 67 75 6d 65 6e 74 73 20 70 4c  .** Arguments pL
1ef0: 65 66 74 20 61 6e 64 20 70 52 69 67 68 74 20 70  eft and pRight p
1f00: 6f 69 6e 74 20 74 6f 20 6c 69 6e 6b 65 64 2d 6c  oint to linked-l
1f10: 69 73 74 73 20 6f 66 20 68 61 73 68 2d 65 6e 74  ists of hash-ent
1f20: 72 79 20 6f 62 6a 65 63 74 73 2c 0a 2a 2a 20 65  ry objects,.** e
1f30: 61 63 68 20 73 6f 72 74 65 64 20 69 6e 20 6b 65  ach sorted in ke
1f40: 79 20 6f 72 64 65 72 2e 20 54 68 69 73 20 66 75  y order. This fu
1f50: 6e 63 74 69 6f 6e 20 6d 65 72 67 65 73 20 74 68  nction merges th
1f60: 65 20 74 77 6f 20 6c 69 73 74 73 20 69 6e 74 6f  e two lists into
1f70: 20 61 0a 2a 2a 20 73 69 6e 67 6c 65 20 6c 69 73   a.** single lis
1f80: 74 20 61 6e 64 20 72 65 74 75 72 6e 73 20 61 20  t and returns a 
1f90: 70 6f 69 6e 74 65 72 20 74 6f 20 69 74 73 20 66  pointer to its f
1fa0: 69 72 73 74 20 65 6c 65 6d 65 6e 74 2e 0a 2a 2f  irst element..*/
1fb0: 0a 73 74 61 74 69 63 20 46 74 73 35 48 61 73 68  .static Fts5Hash
1fc0: 45 6e 74 72 79 20 2a 66 74 73 35 48 61 73 68 45  Entry *fts5HashE
1fd0: 6e 74 72 79 4d 65 72 67 65 28 0a 20 20 46 74 73  ntryMerge(.  Fts
1fe0: 35 48 61 73 68 45 6e 74 72 79 20 2a 70 4c 65 66  5HashEntry *pLef
1ff0: 74 2c 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74  t,.  Fts5HashEnt
2000: 72 79 20 2a 70 52 69 67 68 74 0a 29 7b 0a 20 20  ry *pRight.){.  
2010: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70  Fts5HashEntry *p
2020: 31 20 3d 20 70 4c 65 66 74 3b 0a 20 20 46 74 73  1 = pLeft;.  Fts
2030: 35 48 61 73 68 45 6e 74 72 79 20 2a 70 32 20 3d  5HashEntry *p2 =
2040: 20 70 52 69 67 68 74 3b 0a 20 20 46 74 73 35 48   pRight;.  Fts5H
2050: 61 73 68 45 6e 74 72 79 20 2a 70 52 65 74 20 3d  ashEntry *pRet =
2060: 20 30 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e   0;.  Fts5HashEn
2070: 74 72 79 20 2a 2a 70 70 4f 75 74 20 3d 20 26 70  try **ppOut = &p
2080: 52 65 74 3b 0a 0a 20 20 77 68 69 6c 65 28 20 70  Ret;..  while( p
2090: 31 20 7c 7c 20 70 32 20 29 7b 0a 20 20 20 20 69  1 || p2 ){.    i
20a0: 66 28 20 70 31 3d 3d 30 20 29 7b 0a 20 20 20 20  f( p1==0 ){.    
20b0: 20 20 2a 70 70 4f 75 74 20 3d 20 70 32 3b 0a 20    *ppOut = p2;. 
20c0: 20 20 20 20 20 70 32 20 3d 20 30 3b 0a 20 20 20       p2 = 0;.   
20d0: 20 7d 65 6c 73 65 20 69 66 28 20 70 32 3d 3d 30   }else if( p2==0
20e0: 20 29 7b 0a 20 20 20 20 20 20 2a 70 70 4f 75 74   ){.      *ppOut
20f0: 20 3d 20 70 31 3b 0a 20 20 20 20 20 20 70 31 20   = p1;.      p1 
2100: 3d 20 30 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a  = 0;.    }else{.
2110: 20 20 20 20 20 20 69 6e 74 20 69 20 3d 20 30 3b        int i = 0;
2120: 0a 20 20 20 20 20 20 77 68 69 6c 65 28 20 70 31  .      while( p1
2130: 2d 3e 7a 4b 65 79 5b 69 5d 3d 3d 70 32 2d 3e 7a  ->zKey[i]==p2->z
2140: 4b 65 79 5b 69 5d 20 29 20 69 2b 2b 3b 0a 0a 20  Key[i] ) i++;.. 
2150: 20 20 20 20 20 69 66 28 20 28 28 75 38 29 70 31       if( ((u8)p1
2160: 2d 3e 7a 4b 65 79 5b 69 5d 29 3e 28 28 75 38 29  ->zKey[i])>((u8)
2170: 70 32 2d 3e 7a 4b 65 79 5b 69 5d 29 20 29 7b 0a  p2->zKey[i]) ){.
2180: 20 20 20 20 20 20 20 20 2f 2a 20 70 32 20 69 73          /* p2 is
2190: 20 73 6d 61 6c 6c 65 72 20 2a 2f 0a 20 20 20 20   smaller */.    
21a0: 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 70 32 3b      *ppOut = p2;
21b0: 0a 20 20 20 20 20 20 20 20 70 70 4f 75 74 20 3d  .        ppOut =
21c0: 20 26 70 32 2d 3e 70 4e 65 78 74 3b 0a 20 20 20   &p2->pNext;.   
21d0: 20 20 20 20 20 70 32 20 3d 20 70 32 2d 3e 70 4e       p2 = p2->pN
21e0: 65 78 74 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65  ext;.      }else
21f0: 7b 0a 20 20 20 20 20 20 20 20 2f 2a 20 70 31 20  {.        /* p1 
2200: 69 73 20 73 6d 61 6c 6c 65 72 20 2a 2f 0a 20 20  is smaller */.  
2210: 20 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 70        *ppOut = p
2220: 31 3b 0a 20 20 20 20 20 20 20 20 70 70 4f 75 74  1;.        ppOut
2230: 20 3d 20 26 70 31 2d 3e 70 4e 65 78 74 3b 0a 20   = &p1->pNext;. 
2240: 20 20 20 20 20 20 20 70 31 20 3d 20 70 31 2d 3e         p1 = p1->
2250: 70 4e 65 78 74 3b 0a 20 20 20 20 20 20 7d 0a 20  pNext;.      }. 
2260: 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 30 3b       *ppOut = 0;
2270: 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 72 65  .    }.  }..  re
2280: 74 75 72 6e 20 70 52 65 74 3b 0a 7d 0a 0a 2f 2a  turn pRet;.}../*
2290: 0a 2a 2a 20 45 78 74 72 61 63 74 20 61 6c 6c 20  .** Extract all 
22a0: 74 6f 6b 65 6e 73 20 66 72 6f 6d 20 68 61 73 68  tokens from hash
22b0: 20 74 61 62 6c 65 20 69 48 61 73 68 20 61 6e 64   table iHash and
22c0: 20 6c 69 6e 6b 20 74 68 65 6d 20 69 6e 74 6f 20   link them into 
22d0: 61 20 6c 69 73 74 0a 2a 2a 20 69 6e 20 73 6f 72  a list.** in sor
22e0: 74 65 64 20 6f 72 64 65 72 2e 20 54 68 65 20 68  ted order. The h
22f0: 61 73 68 20 74 61 62 6c 65 20 69 73 20 63 6c 65  ash table is cle
2300: 61 72 65 64 20 62 65 66 6f 72 65 20 72 65 74 75  ared before retu
2310: 72 6e 69 6e 67 2e 20 49 74 20 69 73 0a 2a 2a 20  rning. It is.** 
2320: 74 68 65 20 72 65 73 70 6f 6e 73 69 62 69 6c 69  the responsibili
2330: 74 79 20 6f 66 20 74 68 65 20 63 61 6c 6c 65 72  ty of the caller
2340: 20 74 6f 20 66 72 65 65 20 74 68 65 20 65 6c 65   to free the ele
2350: 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 72 65 74  ments of the ret
2360: 75 72 6e 65 64 0a 2a 2a 20 6c 69 73 74 2e 0a 2a  urned.** list..*
2370: 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 66 74 73  /.static int fts
2380: 35 48 61 73 68 45 6e 74 72 79 53 6f 72 74 28 46  5HashEntrySort(F
2390: 74 73 35 48 61 73 68 20 2a 70 48 61 73 68 2c 20  ts5Hash *pHash, 
23a0: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a  Fts5HashEntry **
23b0: 70 70 53 6f 72 74 65 64 29 7b 0a 20 20 63 6f 6e  ppSorted){.  con
23c0: 73 74 20 69 6e 74 20 6e 4d 65 72 67 65 53 6c 6f  st int nMergeSlo
23d0: 74 20 3d 20 33 32 3b 0a 20 20 46 74 73 35 48 61  t = 32;.  Fts5Ha
23e0: 73 68 45 6e 74 72 79 20 2a 2a 61 70 3b 0a 20 20  shEntry **ap;.  
23f0: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70  Fts5HashEntry *p
2400: 4c 69 73 74 3b 0a 20 20 69 6e 74 20 69 53 6c 6f  List;.  int iSlo
2410: 74 3b 0a 20 20 69 6e 74 20 69 3b 0a 0a 20 20 2a  t;.  int i;..  *
2420: 70 70 53 6f 72 74 65 64 20 3d 20 30 3b 0a 20 20  ppSorted = 0;.  
2430: 61 70 20 3d 20 73 71 6c 69 74 65 33 5f 6d 61 6c  ap = sqlite3_mal
2440: 6c 6f 63 28 73 69 7a 65 6f 66 28 46 74 73 35 48  loc(sizeof(Fts5H
2450: 61 73 68 45 6e 74 72 79 2a 29 20 2a 20 6e 4d 65  ashEntry*) * nMe
2460: 72 67 65 53 6c 6f 74 29 3b 0a 20 20 69 66 28 20  rgeSlot);.  if( 
2470: 21 61 70 20 29 20 72 65 74 75 72 6e 20 53 51 4c  !ap ) return SQL
2480: 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 6d 65 6d  ITE_NOMEM;.  mem
2490: 73 65 74 28 61 70 2c 20 30 2c 20 73 69 7a 65 6f  set(ap, 0, sizeo
24a0: 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a  f(Fts5HashEntry*
24b0: 29 20 2a 20 6e 4d 65 72 67 65 53 6c 6f 74 29 3b  ) * nMergeSlot);
24c0: 0a 0a 20 20 66 6f 72 28 69 53 6c 6f 74 3d 30 3b  ..  for(iSlot=0;
24d0: 20 69 53 6c 6f 74 3c 70 48 61 73 68 2d 3e 6e 53   iSlot<pHash->nS
24e0: 6c 6f 74 3b 20 69 53 6c 6f 74 2b 2b 29 7b 0a 20  lot; iSlot++){. 
24f0: 20 20 20 77 68 69 6c 65 28 20 70 48 61 73 68 2d     while( pHash-
2500: 3e 61 53 6c 6f 74 5b 69 53 6c 6f 74 5d 20 29 7b  >aSlot[iSlot] ){
2510: 0a 20 20 20 20 20 20 46 74 73 35 48 61 73 68 45  .      Fts5HashE
2520: 6e 74 72 79 20 2a 70 45 6e 74 72 79 20 3d 20 70  ntry *pEntry = p
2530: 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 53 6c 6f  Hash->aSlot[iSlo
2540: 74 5d 3b 0a 20 20 20 20 20 20 70 48 61 73 68 2d  t];.      pHash-
2550: 3e 61 53 6c 6f 74 5b 69 53 6c 6f 74 5d 20 3d 20  >aSlot[iSlot] = 
2560: 70 45 6e 74 72 79 2d 3e 70 4e 65 78 74 3b 0a 20  pEntry->pNext;. 
2570: 20 20 20 20 20 70 45 6e 74 72 79 2d 3e 70 4e 65       pEntry->pNe
2580: 78 74 20 3d 20 30 3b 0a 20 20 20 20 20 20 66 6f  xt = 0;.      fo
2590: 72 28 69 3d 30 3b 20 61 70 5b 69 5d 3b 20 69 2b  r(i=0; ap[i]; i+
25a0: 2b 29 7b 0a 20 20 20 20 20 20 20 20 70 45 6e 74  +){.        pEnt
25b0: 72 79 20 3d 20 66 74 73 35 48 61 73 68 45 6e 74  ry = fts5HashEnt
25c0: 72 79 4d 65 72 67 65 28 70 45 6e 74 72 79 2c 20  ryMerge(pEntry, 
25d0: 61 70 5b 69 5d 29 3b 0a 20 20 20 20 20 20 20 20  ap[i]);.        
25e0: 61 70 5b 69 5d 20 3d 20 30 3b 0a 20 20 20 20 20  ap[i] = 0;.     
25f0: 20 7d 0a 20 20 20 20 20 20 61 70 5b 69 5d 20 3d   }.      ap[i] =
2600: 20 70 45 6e 74 72 79 3b 0a 20 20 20 20 7d 0a 20   pEntry;.    }. 
2610: 20 7d 0a 0a 20 20 70 4c 69 73 74 20 3d 20 30 3b   }..  pList = 0;
2620: 0a 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 6e 4d  .  for(i=0; i<nM
2630: 65 72 67 65 53 6c 6f 74 3b 20 69 2b 2b 29 7b 0a  ergeSlot; i++){.
2640: 20 20 20 20 70 4c 69 73 74 20 3d 20 66 74 73 35      pList = fts5
2650: 48 61 73 68 45 6e 74 72 79 4d 65 72 67 65 28 70  HashEntryMerge(p
2660: 4c 69 73 74 2c 20 61 70 5b 69 5d 29 3b 0a 20 20  List, ap[i]);.  
2670: 7d 0a 0a 20 20 70 48 61 73 68 2d 3e 6e 45 6e 74  }..  pHash->nEnt
2680: 72 79 20 3d 20 30 3b 0a 20 20 73 71 6c 69 74 65  ry = 0;.  sqlite
2690: 33 5f 66 72 65 65 28 61 70 29 3b 0a 20 20 2a 70  3_free(ap);.  *p
26a0: 70 53 6f 72 74 65 64 20 3d 20 70 4c 69 73 74 3b  pSorted = pList;
26b0: 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45  .  return SQLITE
26c0: 5f 4f 4b 3b 0a 7d 0a 0a 69 6e 74 20 73 71 6c 69  _OK;.}..int sqli
26d0: 74 65 33 46 74 73 35 48 61 73 68 49 74 65 72 61  te3Fts5HashItera
26e0: 74 65 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a  te(.  Fts5Hash *
26f0: 70 48 61 73 68 2c 0a 20 20 76 6f 69 64 20 2a 70  pHash,.  void *p
2700: 43 74 78 2c 0a 20 20 69 6e 74 20 28 2a 78 54 65  Ctx,.  int (*xTe
2710: 72 6d 29 28 76 6f 69 64 2a 2c 20 63 6f 6e 73 74  rm)(void*, const
2720: 20 63 68 61 72 2a 2c 20 69 6e 74 29 2c 0a 20 20   char*, int),.  
2730: 69 6e 74 20 28 2a 78 45 6e 74 72 79 29 28 76 6f  int (*xEntry)(vo
2740: 69 64 2a 2c 20 69 36 34 2c 20 63 6f 6e 73 74 20  id*, i64, const 
2750: 75 38 2a 2c 20 69 6e 74 29 2c 0a 20 20 69 6e 74  u8*, int),.  int
2760: 20 28 2a 78 54 65 72 6d 44 6f 6e 65 29 28 76 6f   (*xTermDone)(vo
2770: 69 64 2a 29 0a 29 7b 0a 20 20 46 74 73 35 48 61  id*).){.  Fts5Ha
2780: 73 68 45 6e 74 72 79 20 2a 70 4c 69 73 74 3b 0a  shEntry *pList;.
2790: 20 20 69 6e 74 20 72 63 3b 0a 0a 20 20 72 63 20    int rc;..  rc 
27a0: 3d 20 66 74 73 35 48 61 73 68 45 6e 74 72 79 53  = fts5HashEntryS
27b0: 6f 72 74 28 70 48 61 73 68 2c 20 26 70 4c 69 73  ort(pHash, &pLis
27c0: 74 29 3b 0a 20 20 69 66 28 20 72 63 3d 3d 53 51  t);.  if( rc==SQ
27d0: 4c 49 54 45 5f 4f 4b 20 29 7b 0a 20 20 20 20 77  LITE_OK ){.    w
27e0: 68 69 6c 65 28 20 70 4c 69 73 74 20 29 7b 0a 20  hile( pList ){. 
27f0: 20 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74       Fts5HashEnt
2800: 72 79 20 2a 70 4e 65 78 74 20 3d 20 70 4c 69 73  ry *pNext = pLis
2810: 74 2d 3e 70 4e 65 78 74 3b 0a 20 20 20 20 20 20  t->pNext;.      
2820: 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f 4f  if( rc==SQLITE_O
2830: 4b 20 29 7b 0a 20 20 20 20 20 20 20 20 63 6f 6e  K ){.        con
2840: 73 74 20 69 6e 74 20 6e 53 7a 20 3d 20 70 4c 69  st int nSz = pLi
2850: 73 74 2d 3e 6e 44 61 74 61 20 2d 20 70 4c 69 73  st->nData - pLis
2860: 74 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 2d 20  t->iSzPoslist - 
2870: 34 3b 0a 20 20 20 20 20 20 20 20 63 6f 6e 73 74  4;.        const
2880: 20 69 6e 74 20 6e 4b 65 79 20 3d 20 73 74 72 6c   int nKey = strl
2890: 65 6e 28 70 4c 69 73 74 2d 3e 7a 4b 65 79 29 3b  en(pList->zKey);
28a0: 0a 20 20 20 20 20 20 20 20 69 36 34 20 69 52 6f  .        i64 iRo
28b0: 77 69 64 20 3d 20 30 3b 0a 20 20 20 20 20 20 20  wid = 0;.       
28c0: 20 75 38 20 2a 70 50 74 72 20 3d 20 28 75 38 2a   u8 *pPtr = (u8*
28d0: 29 70 4c 69 73 74 3b 0a 20 20 20 20 20 20 20 20  )pList;.        
28e0: 69 6e 74 20 69 4f 66 66 20 3d 20 73 69 7a 65 6f  int iOff = sizeo
28f0: 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 29  f(Fts5HashEntry)
2900: 20 2b 20 6e 4b 65 79 20 2b 20 31 3b 0a 0a 20 20   + nKey + 1;..  
2910: 20 20 20 20 20 20 2f 2a 20 46 69 6c 6c 20 69 6e        /* Fill in
2920: 20 74 68 65 20 66 69 6e 61 6c 20 70 6f 73 6c 69   the final posli
2930: 73 74 20 73 69 7a 65 20 66 69 65 6c 64 20 2a 2f  st size field */
2940: 0a 20 20 20 20 20 20 20 20 66 74 73 35 50 75 74  .        fts5Put
2950: 34 42 79 74 65 56 61 72 69 6e 74 28 26 70 50 74  4ByteVarint(&pPt
2960: 72 5b 70 4c 69 73 74 2d 3e 69 53 7a 50 6f 73 6c  r[pList->iSzPosl
2970: 69 73 74 5d 2c 20 6e 53 7a 29 3b 0a 20 20 20 20  ist], nSz);.    
2980: 20 20 20 20 0a 20 20 20 20 20 20 20 20 2f 2a 20      .        /* 
2990: 49 73 73 75 65 20 74 68 65 20 6e 65 77 2d 74 65  Issue the new-te
29a0: 72 6d 20 63 61 6c 6c 62 61 63 6b 20 2a 2f 0a 20  rm callback */. 
29b0: 20 20 20 20 20 20 20 72 63 20 3d 20 78 54 65 72         rc = xTer
29c0: 6d 28 70 43 74 78 2c 20 70 4c 69 73 74 2d 3e 7a  m(pCtx, pList->z
29d0: 4b 65 79 2c 20 6e 4b 65 79 29 3b 0a 0a 20 20 20  Key, nKey);..   
29e0: 20 20 20 20 20 2f 2a 20 49 73 73 75 65 20 74 68       /* Issue th
29f0: 65 20 78 45 6e 74 72 79 20 63 61 6c 6c 62 61 63  e xEntry callbac
2a00: 6b 73 20 2a 2f 0a 20 20 20 20 20 20 20 20 77 68  ks */.        wh
2a10: 69 6c 65 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f  ile( rc==SQLITE_
2a20: 4f 4b 20 26 26 20 69 4f 66 66 3c 70 4c 69 73 74  OK && iOff<pList
2a30: 2d 3e 6e 44 61 74 61 20 29 7b 0a 20 20 20 20 20  ->nData ){.     
2a40: 20 20 20 20 20 69 36 34 20 69 44 65 6c 74 61 3b       i64 iDelta;
2a50: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
2a60: 52 6f 77 69 64 20 64 65 6c 74 61 20 76 61 6c 75  Rowid delta valu
2a70: 65 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 69  e */.          i
2a80: 6e 74 20 6e 50 6f 73 6c 69 73 74 3b 20 20 20 20  nt nPoslist;    
2a90: 20 20 20 20 20 20 20 2f 2a 20 53 69 7a 65 20 6f         /* Size o
2aa0: 66 20 70 6f 73 69 74 69 6f 6e 20 6c 69 73 74 20  f position list 
2ab0: 69 6e 20 62 79 74 65 73 20 2a 2f 0a 20 20 20 20  in bytes */.    
2ac0: 20 20 20 20 20 20 69 4f 66 66 20 2b 3d 20 67 65        iOff += ge
2ad0: 74 56 61 72 69 6e 74 28 26 70 50 74 72 5b 69 4f  tVarint(&pPtr[iO
2ae0: 66 66 5d 2c 20 28 75 36 34 2a 29 26 69 44 65 6c  ff], (u64*)&iDel
2af0: 74 61 29 3b 0a 20 20 20 20 20 20 20 20 20 20 69  ta);.          i
2b00: 52 6f 77 69 64 20 2b 3d 20 69 44 65 6c 74 61 3b  Rowid += iDelta;
2b10: 0a 20 20 20 20 20 20 20 20 20 20 69 4f 66 66 20  .          iOff 
2b20: 2b 3d 20 66 74 73 35 47 65 74 56 61 72 69 6e 74  += fts5GetVarint
2b30: 33 32 28 26 70 50 74 72 5b 69 4f 66 66 5d 2c 20  32(&pPtr[iOff], 
2b40: 6e 50 6f 73 6c 69 73 74 29 3b 0a 20 20 20 20 20  nPoslist);.     
2b50: 20 20 20 20 20 72 63 20 3d 20 78 45 6e 74 72 79       rc = xEntry
2b60: 28 70 43 74 78 2c 20 69 52 6f 77 69 64 2c 20 26  (pCtx, iRowid, &
2b70: 70 50 74 72 5b 69 4f 66 66 5d 2c 20 6e 50 6f 73  pPtr[iOff], nPos
2b80: 6c 69 73 74 29 3b 0a 20 20 20 20 20 20 20 20 20  list);.         
2b90: 20 69 4f 66 66 20 2b 3d 20 6e 50 6f 73 6c 69 73   iOff += nPoslis
2ba0: 74 3b 0a 20 20 20 20 20 20 20 20 7d 0a 0a 20 20  t;.        }..  
2bb0: 20 20 20 20 20 20 2f 2a 20 49 73 73 75 65 20 74        /* Issue t
2bc0: 68 65 20 74 65 72 6d 2d 64 6f 6e 65 20 63 61 6c  he term-done cal
2bd0: 6c 62 61 63 6b 20 2a 2f 0a 20 20 20 20 20 20 20  lback */.       
2be0: 20 69 66 28 20 72 63 3d 3d 53 51 4c 49 54 45 5f   if( rc==SQLITE_
2bf0: 4f 4b 20 29 20 72 63 20 3d 20 78 54 65 72 6d 44  OK ) rc = xTermD
2c00: 6f 6e 65 28 70 43 74 78 29 3b 0a 20 20 20 20 20  one(pCtx);.     
2c10: 20 7d 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33   }.      sqlite3
2c20: 5f 66 72 65 65 28 70 4c 69 73 74 29 3b 0a 20 20  _free(pList);.  
2c30: 20 20 20 20 70 4c 69 73 74 20 3d 20 70 4e 65 78      pList = pNex
2c40: 74 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 72  t;.    }.  }.  r
2c50: 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 0a           eturn rc;.}..