0000: 2f 2a 0a 2a 2a 20 32 30 31 34 20 41 75 67 75 73 /*.** 2014 Augus
0010: 74 20 31 31 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61 t 11.**.** The a
0020: 75 74 68 6f 72 20 64 69 73 63 6c 61 69 6d 73 20 uthor disclaims
0030: 63 6f 70 79 72 69 67 68 74 20 74 6f 20 74 68 69 copyright to thi
0040: 73 20 73 6f 75 72 63 65 20 63 6f 64 65 2e 20 20 s source code.
0050: 49 6e 20 70 6c 61 63 65 20 6f 66 0a 2a 2a 20 61 In place of.** a
0060: 20 6c 65 67 61 6c 20 6e 6f 74 69 63 65 2c 20 68 legal notice, h
0070: 65 72 65 20 69 73 20 61 20 62 6c 65 73 73 69 6e ere is a blessin
0080: 67 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 4d 61 79 20 g:.**.** May
0090: 79 6f 75 20 64 6f 20 67 6f 6f 64 20 61 6e 64 20 you do good and
00a0: 6e 6f 74 20 65 76 69 6c 2e 0a 2a 2a 20 20 20 20 not evil..**
00b0: 4d 61 79 20 79 6f 75 20 66 69 6e 64 20 66 6f 72 May you find for
00c0: 67 69 76 65 6e 65 73 73 20 66 6f 72 20 79 6f 75 giveness for you
00d0: 72 73 65 6c 66 20 61 6e 64 20 66 6f 72 67 69 76 rself and forgiv
00e0: 65 20 6f 74 68 65 72 73 2e 0a 2a 2a 20 20 20 20 e others..**
00f0: 4d 61 79 20 79 6f 75 20 73 68 61 72 65 20 66 72 May you share fr
0100: 65 65 6c 79 2c 20 6e 65 76 65 72 20 74 61 6b 69 eely, never taki
0110: 6e 67 20 6d 6f 72 65 20 74 68 61 6e 20 79 6f 75 ng more than you
0120: 20 67 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a give..**.******
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0170: 2a 2a 2a 2a 2a 2a 2a 2a 0a 2a 2a 0a 2a 2f 0a 0a ********.**.*/..
0180: 23 69 66 64 65 66 20 53 51 4c 49 54 45 5f 45 4e #ifdef SQLITE_EN
0190: 41 42 4c 45 5f 46 54 53 35 0a 0a 0a 23 69 6e 63 ABLE_FTS5...#inc
01a0: 6c 75 64 65 20 22 66 74 73 35 49 6e 74 2e 68 22 lude "fts5Int.h"
01b0: 0a 0a 74 79 70 65 64 65 66 20 73 74 72 75 63 74 ..typedef struct
01c0: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 46 Fts5HashEntry F
01d0: 74 73 35 48 61 73 68 45 6e 74 72 79 3b 0a 0a 2f ts5HashEntry;../
01e0: 2a 0a 2a 2a 20 54 68 69 73 20 66 69 6c 65 20 63 *.** This file c
01f0: 6f 6e 74 61 69 6e 73 20 74 68 65 20 69 6d 70 6c ontains the impl
0200: 65 6d 65 6e 74 61 74 69 6f 6e 20 6f 66 20 61 6e ementation of an
0210: 20 69 6e 2d 6d 65 6d 6f 72 79 20 68 61 73 68 20 in-memory hash
0220: 74 61 62 6c 65 20 75 73 65 64 0a 2a 2a 20 74 6f table used.** to
0230: 20 61 63 63 75 6d 75 6c 75 61 74 65 20 22 74 65 accumuluate "te
0240: 72 6d 20 2d 3e 20 64 6f 63 6c 69 73 74 22 20 63 rm -> doclist" c
0250: 6f 6e 74 65 6e 74 20 62 65 66 6f 72 65 20 69 74 ontent before it
0260: 20 69 73 20 66 6c 75 73 65 64 20 74 6f 20 61 20 is flused to a
0270: 6c 65 76 65 6c 2d 30 0a 2a 2a 20 73 65 67 6d 65 level-0.** segme
0280: 6e 74 2e 0a 2a 2f 0a 0a 0a 73 74 72 75 63 74 20 nt..*/...struct
0290: 46 74 73 35 48 61 73 68 20 7b 0a 20 20 69 6e 74 Fts5Hash {. int
02a0: 20 2a 70 6e 42 79 74 65 3b 20 20 20 20 20 20 20 *pnByte;
02b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 /*
02c0: 50 6f 69 6e 74 65 72 20 74 6f 20 62 79 74 65 73 Pointer to bytes
02d0: 20 63 6f 75 6e 74 65 72 20 2a 2f 0a 20 20 69 6e counter */. in
02e0: 74 20 6e 45 6e 74 72 79 3b 20 20 20 20 20 20 20 t nEntry;
02f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a /*
0300: 20 4e 75 6d 62 65 72 20 6f 66 20 65 6e 74 72 69 Number of entri
0310: 65 73 20 63 75 72 72 65 6e 74 6c 79 20 69 6e 20 es currently in
0320: 68 61 73 68 20 2a 2f 0a 20 20 69 6e 74 20 6e 53 hash */. int nS
0330: 6c 6f 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 lot;
0340: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 53 69 7a /* Siz
0350: 65 20 6f 66 20 61 53 6c 6f 74 5b 5d 20 61 72 72 e of aSlot[] arr
0360: 61 79 20 2a 2f 0a 20 20 46 74 73 35 48 61 73 68 ay */. Fts5Hash
0370: 45 6e 74 72 79 20 2a 70 53 63 61 6e 3b 20 20 20 Entry *pScan;
0380: 20 20 20 20 20 20 20 20 2f 2a 20 43 75 72 72 65 /* Curre
0390: 6e 74 20 6f 72 64 65 72 65 64 20 73 63 61 6e 20 nt ordered scan
03a0: 69 74 65 6d 20 2a 2f 0a 20 20 46 74 73 35 48 61 item */. Fts5Ha
03b0: 73 68 45 6e 74 72 79 20 2a 2a 61 53 6c 6f 74 3b shEntry **aSlot;
03c0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41 72 72 /* Arr
03d0: 61 79 20 6f 66 20 68 61 73 68 20 73 6c 6f 74 73 ay of hash slots
03e0: 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 45 61 */.};../*.** Ea
03f0: 63 68 20 65 6e 74 72 79 20 69 6e 20 74 68 65 20 ch entry in the
0400: 68 61 73 68 20 74 61 62 6c 65 20 69 73 20 72 65 hash table is re
0410: 70 72 65 73 65 6e 74 65 64 20 62 79 20 61 6e 20 presented by an
0420: 6f 62 6a 65 63 74 20 6f 66 20 74 68 65 20 0a 2a object of the .*
0430: 2a 20 66 6f 6c 6c 6f 77 69 6e 67 20 74 79 70 65 * following type
0440: 2e 20 45 61 63 68 20 6f 62 6a 65 63 74 2c 20 69 . Each object, i
0450: 74 73 20 6b 65 79 20 28 7a 4b 65 79 5b 5d 29 20 ts key (zKey[])
0460: 61 6e 64 20 69 74 73 20 63 75 72 72 65 6e 74 20 and its current
0470: 64 61 74 61 0a 2a 2a 20 61 72 65 20 73 74 6f 72 data.** are stor
0480: 65 64 20 69 6e 20 61 20 73 69 6e 67 6c 65 20 6d ed in a single m
0490: 65 6d 6f 72 79 20 61 6c 6c 6f 63 61 74 69 6f 6e emory allocation
04a0: 2e 20 54 68 65 20 70 6f 73 69 74 69 6f 6e 20 6c . The position l
04b0: 69 73 74 20 64 61 74 61 20 0a 2a 2a 20 69 6d 6d ist data .** imm
04c0: 65 64 69 61 74 65 6c 79 20 66 6f 6c 6c 6f 77 73 ediately follows
04d0: 20 74 68 65 20 6b 65 79 20 64 61 74 61 20 69 6e the key data in
04e0: 20 6d 65 6d 6f 72 79 2e 0a 2a 2a 0a 2a 2a 20 54 memory..**.** T
04f0: 68 65 20 64 61 74 61 20 74 68 61 74 20 66 6f 6c he data that fol
0500: 6c 6f 77 73 20 74 68 65 20 6b 65 79 20 69 73 20 lows the key is
0510: 69 6e 20 61 20 73 69 6d 69 6c 61 72 2c 20 62 75 in a similar, bu
0520: 74 20 6e 6f 74 20 69 64 65 6e 74 69 63 61 6c 20 t not identical
0530: 66 6f 72 6d 61 74 0a 2a 2a 20 74 6f 20 74 68 65 format.** to the
0540: 20 64 6f 63 6c 69 73 74 20 64 61 74 61 20 73 74 doclist data st
0550: 6f 72 65 64 20 69 6e 20 74 68 65 20 64 61 74 61 ored in the data
0560: 62 61 73 65 2e 20 49 74 20 69 73 3a 0a 2a 2a 0a base. It is:.**.
0570: 2a 2a 20 20 20 2a 20 52 6f 77 69 64 2c 20 61 73 ** * Rowid, as
0580: 20 61 20 76 61 72 69 6e 74 0a 2a 2a 20 20 20 2a a varint.** *
0590: 20 50 6f 73 69 74 69 6f 6e 20 6c 69 73 74 2c 20 Position list,
05a0: 77 69 74 68 6f 75 74 20 30 78 30 30 20 74 65 72 without 0x00 ter
05b0: 6d 69 6e 61 74 6f 72 2e 0a 2a 2a 20 20 20 2a 20 minator..** *
05c0: 53 69 7a 65 20 6f 66 20 70 72 65 76 69 6f 75 73 Size of previous
05d0: 20 70 6f 73 69 74 69 6f 6e 20 6c 69 73 74 20 61 position list a
05e0: 6e 64 20 72 6f 77 69 64 2c 20 61 73 20 61 20 34 nd rowid, as a 4
05f0: 20 62 79 74 65 0a 2a 2a 20 20 20 20 20 62 69 67 byte.** big
0600: 2d 65 6e 64 69 61 6e 20 69 6e 74 65 67 65 72 2e -endian integer.
0610: 0a 2a 2a 0a 2a 2a 20 69 52 6f 77 69 64 4f 66 66 .**.** iRowidOff
0620: 3a 0a 2a 2a 20 20 20 4f 66 66 73 65 74 20 6f 66 :.** Offset of
0630: 20 6c 61 73 74 20 72 6f 77 69 64 20 77 72 69 74 last rowid writ
0640: 74 65 6e 20 74 6f 20 64 61 74 61 20 61 72 65 61 ten to data area
0650: 2e 20 52 65 6c 61 74 69 76 65 20 74 6f 20 66 69 . Relative to fi
0660: 72 73 74 20 62 79 74 65 20 6f 66 0a 2a 2a 20 20 rst byte of.**
0670: 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2a 0a 2a structure..**.*
0680: 2a 20 6e 44 61 74 61 3a 0a 2a 2a 20 20 20 42 79 * nData:.** By
0690: 74 65 73 20 6f 66 20 64 61 74 61 20 77 72 69 74 tes of data writ
06a0: 74 65 6e 20 73 69 6e 63 65 20 69 52 6f 77 69 64 ten since iRowid
06b0: 4f 66 66 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 46 Off..*/.struct F
06c0: 74 73 35 48 61 73 68 45 6e 74 72 79 20 7b 0a 20 ts5HashEntry {.
06d0: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a Fts5HashEntry *
06e0: 70 48 61 73 68 4e 65 78 74 3b 20 20 20 20 20 20 pHashNext;
06f0: 20 2f 2a 20 4e 65 78 74 20 68 61 73 68 20 65 6e /* Next hash en
0700: 74 72 79 20 77 69 74 68 20 73 61 6d 65 20 68 61 try with same ha
0710: 73 68 2d 6b 65 79 20 2a 2f 0a 20 20 46 74 73 35 sh-key */. Fts5
0720: 48 61 73 68 45 6e 74 72 79 20 2a 70 53 63 61 6e HashEntry *pScan
0730: 4e 65 78 74 3b 20 20 20 20 20 20 20 2f 2a 20 4e Next; /* N
0740: 65 78 74 20 65 6e 74 72 79 20 69 6e 20 73 6f 72 ext entry in sor
0750: 74 65 64 20 6f 72 64 65 72 20 2a 2f 0a 20 20 0a ted order */. .
0760: 20 20 69 6e 74 20 6e 41 6c 6c 6f 63 3b 20 20 20 int nAlloc;
0770: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0780: 20 20 2f 2a 20 54 6f 74 61 6c 20 73 69 7a 65 20 /* Total size
0790: 6f 66 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 2a 2f of allocation */
07a0: 0a 20 20 69 6e 74 20 69 53 7a 50 6f 73 6c 69 73 . int iSzPoslis
07b0: 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 t;
07c0: 20 20 20 2f 2a 20 4f 66 66 73 65 74 20 6f 66 20 /* Offset of
07d0: 73 70 61 63 65 20 66 6f 72 20 34 2d 62 79 74 65 space for 4-byte
07e0: 20 70 6f 73 6c 69 73 74 20 73 69 7a 65 20 2a 2f poslist size */
07f0: 0a 20 20 69 6e 74 20 6e 44 61 74 61 3b 20 20 20 . int nData;
0800: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0810: 20 20 20 2f 2a 20 54 6f 74 61 6c 20 62 79 74 65 /* Total byte
0820: 73 20 6f 66 20 64 61 74 61 20 28 69 6e 63 6c 2e s of data (incl.
0830: 20 73 74 72 75 63 74 75 72 65 29 20 2a 2f 0a 0a structure) */..
0840: 20 20 69 6e 74 20 69 43 6f 6c 3b 20 20 20 20 20 int iCol;
0850: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0860: 20 20 2f 2a 20 43 6f 6c 75 6d 6e 20 6f 66 20 6c /* Column of l
0870: 61 73 74 20 76 61 6c 75 65 20 77 72 69 74 74 65 ast value writte
0880: 6e 20 2a 2f 0a 20 20 69 6e 74 20 69 50 6f 73 3b n */. int iPos;
0890: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
08a0: 20 20 20 20 20 20 20 2f 2a 20 50 6f 73 69 74 69 /* Positi
08b0: 6f 6e 20 6f 66 20 6c 61 73 74 20 76 61 6c 75 65 on of last value
08c0: 20 77 72 69 74 74 65 6e 20 2a 2f 0a 20 20 69 36 written */. i6
08d0: 34 20 69 52 6f 77 69 64 3b 20 20 20 20 20 20 20 4 iRowid;
08e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a /*
08f0: 20 52 6f 77 69 64 20 6f 66 20 6c 61 73 74 20 76 Rowid of last v
0900: 61 6c 75 65 20 77 72 69 74 74 65 6e 20 2a 2f 0a alue written */.
0910: 20 20 63 68 61 72 20 7a 4b 65 79 5b 30 5d 3b 20 char zKey[0];
0920: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0930: 20 20 2f 2a 20 4e 75 6c 2d 74 65 72 6d 69 6e 61 /* Nul-termina
0940: 74 65 64 20 65 6e 74 72 79 20 6b 65 79 20 2a 2f ted entry key */
0950: 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41 6c 6c 6f 63 .};../*.** Alloc
0960: 61 74 65 20 61 20 6e 65 77 20 68 61 73 68 20 74 ate a new hash t
0970: 61 62 6c 65 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c able..*/.int sql
0980: 69 74 65 33 46 74 73 35 48 61 73 68 4e 65 77 28 ite3Fts5HashNew(
0990: 46 74 73 35 48 61 73 68 20 2a 2a 70 70 4e 65 77 Fts5Hash **ppNew
09a0: 2c 20 69 6e 74 20 2a 70 6e 42 79 74 65 29 7b 0a , int *pnByte){.
09b0: 20 20 69 6e 74 20 72 63 20 3d 20 53 51 4c 49 54 int rc = SQLIT
09c0: 45 5f 4f 4b 3b 0a 20 20 46 74 73 35 48 61 73 68 E_OK;. Fts5Hash
09d0: 20 2a 70 4e 65 77 3b 0a 0a 20 20 2a 70 70 4e 65 *pNew;.. *ppNe
09e0: 77 20 3d 20 70 4e 65 77 20 3d 20 28 46 74 73 35 w = pNew = (Fts5
09f0: 48 61 73 68 2a 29 73 71 6c 69 74 65 33 5f 6d 61 Hash*)sqlite3_ma
0a00: 6c 6c 6f 63 28 73 69 7a 65 6f 66 28 46 74 73 35 lloc(sizeof(Fts5
0a10: 48 61 73 68 29 29 3b 0a 20 20 69 66 28 20 70 4e Hash));. if( pN
0a20: 65 77 3d 3d 30 20 29 7b 0a 20 20 20 20 72 63 20 ew==0 ){. rc
0a30: 3d 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a = SQLITE_NOMEM;.
0a40: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 69 6e 74 }else{. int
0a50: 20 6e 42 79 74 65 3b 0a 20 20 20 20 6d 65 6d 73 nByte;. mems
0a60: 65 74 28 70 4e 65 77 2c 20 30 2c 20 73 69 7a 65 et(pNew, 0, size
0a70: 6f 66 28 46 74 73 35 48 61 73 68 29 29 3b 0a 20 of(Fts5Hash));.
0a80: 20 20 20 70 4e 65 77 2d 3e 70 6e 42 79 74 65 20 pNew->pnByte
0a90: 3d 20 70 6e 42 79 74 65 3b 0a 0a 20 20 20 20 70 = pnByte;.. p
0aa0: 4e 65 77 2d 3e 6e 53 6c 6f 74 20 3d 20 31 30 32 New->nSlot = 102
0ab0: 34 3b 0a 20 20 20 20 6e 42 79 74 65 20 3d 20 73 4;. nByte = s
0ac0: 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e izeof(Fts5HashEn
0ad0: 74 72 79 2a 29 20 2a 20 70 4e 65 77 2d 3e 6e 53 try*) * pNew->nS
0ae0: 6c 6f 74 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 61 lot;. pNew->a
0af0: 53 6c 6f 74 20 3d 20 28 46 74 73 35 48 61 73 68 Slot = (Fts5Hash
0b00: 45 6e 74 72 79 2a 2a 29 73 71 6c 69 74 65 33 5f Entry**)sqlite3_
0b10: 6d 61 6c 6c 6f 63 28 6e 42 79 74 65 29 3b 0a 20 malloc(nByte);.
0b20: 20 20 20 69 66 28 20 70 4e 65 77 2d 3e 61 53 6c if( pNew->aSl
0b30: 6f 74 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 73 ot==0 ){. s
0b40: 71 6c 69 74 65 33 5f 66 72 65 65 28 70 4e 65 77 qlite3_free(pNew
0b50: 29 3b 0a 20 20 20 20 20 20 2a 70 70 4e 65 77 20 );. *ppNew
0b60: 3d 20 30 3b 0a 20 20 20 20 20 20 72 63 20 3d 20 = 0;. rc =
0b70: 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 SQLITE_NOMEM;.
0b80: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 6d }else{. m
0b90: 65 6d 73 65 74 28 70 4e 65 77 2d 3e 61 53 6c 6f emset(pNew->aSlo
0ba0: 74 2c 20 30 2c 20 6e 42 79 74 65 29 3b 0a 20 20 t, 0, nByte);.
0bb0: 20 20 7d 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e }. }. return
0bc0: 20 72 63 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 46 72 rc;.}../*.** Fr
0bd0: 65 65 20 61 20 68 61 73 68 20 74 61 62 6c 65 20 ee a hash table
0be0: 6f 62 6a 65 63 74 2e 0a 2a 2f 0a 76 6f 69 64 20 object..*/.void
0bf0: 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 46 sqlite3Fts5HashF
0c00: 72 65 65 28 46 74 73 35 48 61 73 68 20 2a 70 48 ree(Fts5Hash *pH
0c10: 61 73 68 29 7b 0a 20 20 69 66 28 20 70 48 61 73 ash){. if( pHas
0c20: 68 20 29 7b 0a 20 20 20 20 73 71 6c 69 74 65 33 h ){. sqlite3
0c30: 46 74 73 35 48 61 73 68 43 6c 65 61 72 28 70 48 Fts5HashClear(pH
0c40: 61 73 68 29 3b 0a 20 20 20 20 73 71 6c 69 74 65 ash);. sqlite
0c50: 33 5f 66 72 65 65 28 70 48 61 73 68 2d 3e 61 53 3_free(pHash->aS
0c60: 6c 6f 74 29 3b 0a 20 20 20 20 73 71 6c 69 74 65 lot);. sqlite
0c70: 33 5f 66 72 65 65 28 70 48 61 73 68 29 3b 0a 20 3_free(pHash);.
0c80: 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 45 6d 70 74 }.}../*.** Empt
0c90: 79 20 28 62 75 74 20 64 6f 20 6e 6f 74 20 64 65 y (but do not de
0ca0: 6c 65 74 65 29 20 61 20 68 61 73 68 20 74 61 62 lete) a hash tab
0cb0: 6c 65 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 le..*/.void sqli
0cc0: 74 65 33 46 74 73 35 48 61 73 68 43 6c 65 61 72 te3Fts5HashClear
0cd0: 28 46 74 73 35 48 61 73 68 20 2a 70 48 61 73 68 (Fts5Hash *pHash
0ce0: 29 7b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 66 6f ){. int i;. fo
0cf0: 72 28 69 3d 30 3b 20 69 3c 70 48 61 73 68 2d 3e r(i=0; i<pHash->
0d00: 6e 53 6c 6f 74 3b 20 69 2b 2b 29 7b 0a 20 20 20 nSlot; i++){.
0d10: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a Fts5HashEntry *
0d20: 70 4e 65 78 74 3b 0a 20 20 20 20 46 74 73 35 48 pNext;. Fts5H
0d30: 61 73 68 45 6e 74 72 79 20 2a 70 53 6c 6f 74 3b ashEntry *pSlot;
0d40: 0a 20 20 20 20 66 6f 72 28 70 53 6c 6f 74 3d 70 . for(pSlot=p
0d50: 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 5d 3b 20 Hash->aSlot[i];
0d60: 70 53 6c 6f 74 3b 20 70 53 6c 6f 74 3d 70 4e 65 pSlot; pSlot=pNe
0d70: 78 74 29 7b 0a 20 20 20 20 20 20 70 4e 65 78 74 xt){. pNext
0d80: 20 3d 20 70 53 6c 6f 74 2d 3e 70 48 61 73 68 4e = pSlot->pHashN
0d90: 65 78 74 3b 0a 20 20 20 20 20 20 73 71 6c 69 74 ext;. sqlit
0da0: 65 33 5f 66 72 65 65 28 70 53 6c 6f 74 29 3b 0a e3_free(pSlot);.
0db0: 20 20 20 20 7d 0a 20 20 7d 0a 20 20 6d 65 6d 73 }. }. mems
0dc0: 65 74 28 70 48 61 73 68 2d 3e 61 53 6c 6f 74 2c et(pHash->aSlot,
0dd0: 20 30 2c 20 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 0, pHash->nSlot
0de0: 20 2a 20 73 69 7a 65 6f 66 28 46 74 73 35 48 61 * sizeof(Fts5Ha
0df0: 73 68 45 6e 74 72 79 2a 29 29 3b 0a 20 20 70 48 shEntry*));. pH
0e00: 61 73 68 2d 3e 6e 45 6e 74 72 79 20 3d 20 30 3b ash->nEntry = 0;
0e10: 0a 7d 0a 0a 73 74 61 74 69 63 20 75 6e 73 69 67 .}..static unsig
0e20: 6e 65 64 20 69 6e 74 20 66 74 73 35 48 61 73 68 ned int fts5Hash
0e30: 4b 65 79 28 69 6e 74 20 6e 53 6c 6f 74 2c 20 63 Key(int nSlot, c
0e40: 6f 6e 73 74 20 63 68 61 72 20 2a 70 2c 20 69 6e onst char *p, in
0e50: 74 20 6e 29 7b 0a 20 20 69 6e 74 20 69 3b 0a 20 t n){. int i;.
0e60: 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 68 20 unsigned int h
0e70: 3d 20 31 33 3b 0a 20 20 66 6f 72 28 69 3d 6e 2d = 13;. for(i=n-
0e80: 31 3b 20 69 3e 3d 30 3b 20 69 2d 2d 29 7b 0a 20 1; i>=0; i--){.
0e90: 20 20 20 68 20 3d 20 28 68 20 3c 3c 20 33 29 20 h = (h << 3)
0ea0: 5e 20 68 20 5e 20 70 5b 69 5d 3b 0a 20 20 7d 0a ^ h ^ p[i];. }.
0eb0: 20 20 72 65 74 75 72 6e 20 28 68 20 25 20 6e 53 return (h % nS
0ec0: 6c 6f 74 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 lot);.}../*.** R
0ed0: 65 73 69 7a 65 20 74 68 65 20 68 61 73 68 20 74 esize the hash t
0ee0: 61 62 6c 65 20 62 79 20 64 6f 75 62 6c 69 6e 67 able by doubling
0ef0: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 73 the number of s
0f00: 6c 6f 74 73 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 lots..*/.static
0f10: 69 6e 74 20 66 74 73 35 48 61 73 68 52 65 73 69 int fts5HashResi
0f20: 7a 65 28 46 74 73 35 48 61 73 68 20 2a 70 48 61 ze(Fts5Hash *pHa
0f30: 73 68 29 7b 0a 20 20 69 6e 74 20 6e 4e 65 77 20 sh){. int nNew
0f40: 3d 20 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 2a 32 = pHash->nSlot*2
0f50: 3b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 46 74 73 ;. int i;. Fts
0f60: 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 61 70 4e 5HashEntry **apN
0f70: 65 77 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e ew;. Fts5HashEn
0f80: 74 72 79 20 2a 2a 61 70 4f 6c 64 20 3d 20 70 48 try **apOld = pH
0f90: 61 73 68 2d 3e 61 53 6c 6f 74 3b 0a 0a 20 20 61 ash->aSlot;.. a
0fa0: 70 4e 65 77 20 3d 20 28 46 74 73 35 48 61 73 68 pNew = (Fts5Hash
0fb0: 45 6e 74 72 79 2a 2a 29 73 71 6c 69 74 65 33 5f Entry**)sqlite3_
0fc0: 6d 61 6c 6c 6f 63 28 6e 4e 65 77 2a 73 69 7a 65 malloc(nNew*size
0fd0: 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 of(Fts5HashEntry
0fe0: 2a 29 29 3b 0a 20 20 69 66 28 20 21 61 70 4e 65 *));. if( !apNe
0ff0: 77 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 w ) return SQLIT
1000: 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 6d 65 6d 73 65 E_NOMEM;. memse
1010: 74 28 61 70 4e 65 77 2c 20 30 2c 20 6e 4e 65 77 t(apNew, 0, nNew
1020: 2a 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 *sizeof(Fts5Hash
1030: 45 6e 74 72 79 2a 29 29 3b 0a 0a 20 20 66 6f 72 Entry*));.. for
1040: 28 69 3d 30 3b 20 69 3c 70 48 61 73 68 2d 3e 6e (i=0; i<pHash->n
1050: 53 6c 6f 74 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 Slot; i++){.
1060: 77 68 69 6c 65 28 20 61 70 4f 6c 64 5b 69 5d 20 while( apOld[i]
1070: 29 7b 0a 20 20 20 20 20 20 69 6e 74 20 69 48 61 ){. int iHa
1080: 73 68 3b 0a 20 20 20 20 20 20 46 74 73 35 48 61 sh;. Fts5Ha
1090: 73 68 45 6e 74 72 79 20 2a 70 20 3d 20 61 70 4f shEntry *p = apO
10a0: 6c 64 5b 69 5d 3b 0a 20 20 20 20 20 20 61 70 4f ld[i];. apO
10b0: 6c 64 5b 69 5d 20 3d 20 70 2d 3e 70 48 61 73 68 ld[i] = p->pHash
10c0: 4e 65 78 74 3b 0a 20 20 20 20 20 20 69 48 61 73 Next;. iHas
10d0: 68 20 3d 20 66 74 73 35 48 61 73 68 4b 65 79 28 h = fts5HashKey(
10e0: 6e 4e 65 77 2c 20 70 2d 3e 7a 4b 65 79 2c 20 73 nNew, p->zKey, s
10f0: 74 72 6c 65 6e 28 70 2d 3e 7a 4b 65 79 29 29 3b trlen(p->zKey));
1100: 0a 20 20 20 20 20 20 70 2d 3e 70 48 61 73 68 4e . p->pHashN
1110: 65 78 74 20 3d 20 61 70 4e 65 77 5b 69 48 61 73 ext = apNew[iHas
1120: 68 5d 3b 0a 20 20 20 20 20 20 61 70 4e 65 77 5b h];. apNew[
1130: 69 48 61 73 68 5d 20 3d 20 70 3b 0a 20 20 20 20 iHash] = p;.
1140: 7d 0a 20 20 7d 0a 0a 20 20 73 71 6c 69 74 65 33 }. }.. sqlite3
1150: 5f 66 72 65 65 28 61 70 4f 6c 64 29 3b 0a 20 20 _free(apOld);.
1160: 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 20 3d 20 6e pHash->nSlot = n
1170: 4e 65 77 3b 0a 20 20 70 48 61 73 68 2d 3e 61 53 New;. pHash->aS
1180: 6c 6f 74 20 3d 20 61 70 4e 65 77 3b 0a 20 20 72 lot = apNew;. r
1190: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b eturn SQLITE_OK;
11a0: 0a 7d 0a 0a 73 74 61 74 69 63 20 76 6f 69 64 20 .}..static void
11b0: 66 74 73 35 48 61 73 68 41 64 64 50 6f 73 6c 69 fts5HashAddPosli
11c0: 73 74 53 69 7a 65 28 46 74 73 35 48 61 73 68 45 stSize(Fts5HashE
11d0: 6e 74 72 79 20 2a 70 29 7b 0a 20 20 69 66 28 20 ntry *p){. if(
11e0: 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 29 7b p->iSzPoslist ){
11f0: 0a 20 20 20 20 2f 2a 20 57 52 49 54 45 50 4f 53 . /* WRITEPOS
1200: 4c 49 53 54 53 49 5a 45 20 2a 2f 0a 20 20 20 20 LISTSIZE */.
1210: 75 38 20 2a 70 50 74 72 20 3d 20 28 75 38 2a 29 u8 *pPtr = (u8*)
1220: 70 3b 0a 20 20 20 20 69 6e 74 20 6e 53 7a 20 3d p;. int nSz =
1230: 20 28 70 2d 3e 6e 44 61 74 61 20 2d 20 70 2d 3e (p->nData - p->
1240: 69 53 7a 50 6f 73 6c 69 73 74 20 2d 20 31 29 20 iSzPoslist - 1)
1250: 2a 20 32 3b 0a 0a 20 20 20 20 69 66 28 20 6e 53 * 2;.. if( nS
1260: 7a 3c 3d 31 32 37 20 29 7b 0a 20 20 20 20 20 20 z<=127 ){.
1270: 70 50 74 72 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69 pPtr[p->iSzPosli
1280: 73 74 5d 20 3d 20 6e 53 7a 3b 0a 20 20 20 20 7d st] = nSz;. }
1290: 65 6c 73 65 7b 0a 20 20 20 20 20 20 69 6e 74 20 else{. int
12a0: 6e 42 79 74 65 20 3d 20 73 71 6c 69 74 65 33 46 nByte = sqlite3F
12b0: 74 73 35 47 65 74 56 61 72 69 6e 74 4c 65 6e 28 ts5GetVarintLen(
12c0: 28 75 33 32 29 6e 53 7a 29 3b 0a 20 20 20 20 20 (u32)nSz);.
12d0: 20 2f 2a 20 57 52 49 54 45 50 4f 53 4c 49 53 54 /* WRITEPOSLIST
12e0: 53 49 5a 45 20 2a 2f 0a 20 20 20 20 20 20 6d 65 SIZE */. me
12f0: 6d 6d 6f 76 65 28 26 70 50 74 72 5b 70 2d 3e 69 mmove(&pPtr[p->i
1300: 53 7a 50 6f 73 6c 69 73 74 20 2b 20 6e 42 79 74 SzPoslist + nByt
1310: 65 5d 2c 20 26 70 50 74 72 5b 70 2d 3e 69 53 7a e], &pPtr[p->iSz
1320: 50 6f 73 6c 69 73 74 20 2b 20 31 5d 2c 20 6e 53 Poslist + 1], nS
1330: 7a 2f 32 29 3b 0a 20 20 20 20 20 20 73 71 6c 69 z/2);. sqli
1340: 74 65 33 50 75 74 56 61 72 69 6e 74 28 26 70 50 te3PutVarint(&pP
1350: 74 72 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 tr[p->iSzPoslist
1360: 5d 2c 20 6e 53 7a 29 3b 0a 20 20 20 20 20 20 70 ], nSz);. p
1370: 2d 3e 6e 44 61 74 61 20 2b 3d 20 28 6e 42 79 74 ->nData += (nByt
1380: 65 2d 31 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 e-1);. }.
1390: 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 3d 20 p->iSzPoslist =
13a0: 30 3b 0a 20 20 7d 0a 7d 0a 0a 69 6e 74 20 73 71 0;. }.}..int sq
13b0: 6c 69 74 65 33 46 74 73 35 48 61 73 68 57 72 69 lite3Fts5HashWri
13c0: 74 65 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a te(. Fts5Hash *
13d0: 70 48 61 73 68 2c 0a 20 20 69 36 34 20 69 52 6f pHash,. i64 iRo
13e0: 77 69 64 2c 20 20 20 20 20 20 20 20 20 20 20 20 wid,
13f0: 20 20 20 20 20 20 20 20 20 2f 2a 20 52 6f 77 69 /* Rowi
1400: 64 20 66 6f 72 20 74 68 69 73 20 65 6e 74 72 79 d for this entry
1410: 20 2a 2f 0a 20 20 69 6e 74 20 69 43 6f 6c 2c 20 */. int iCol,
1420: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1430: 20 20 20 20 20 20 2f 2a 20 43 6f 6c 75 6d 6e 20 /* Column
1440: 74 6f 6b 65 6e 20 61 70 70 65 61 72 73 20 69 6e token appears in
1450: 20 28 2d 76 65 20 2d 3e 20 64 65 6c 65 74 65 29 (-ve -> delete)
1460: 20 2a 2f 0a 20 20 69 6e 74 20 69 50 6f 73 2c 20 */. int iPos,
1470: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1480: 20 20 20 20 20 20 2f 2a 20 50 6f 73 69 74 69 6f /* Positio
1490: 6e 20 6f 66 20 74 6f 6b 65 6e 20 77 69 74 68 69 n of token withi
14a0: 6e 20 63 6f 6c 75 6d 6e 20 2a 2f 0a 20 20 63 6f n column */. co
14b0: 6e 73 74 20 63 68 61 72 20 2a 70 54 6f 6b 65 6e nst char *pToken
14c0: 2c 20 69 6e 74 20 6e 54 6f 6b 65 6e 20 20 2f 2a , int nToken /*
14d0: 20 54 6f 6b 65 6e 20 74 6f 20 61 64 64 20 6f 72 Token to add or
14e0: 20 72 65 6d 6f 76 65 20 74 6f 20 6f 72 20 66 72 remove to or fr
14f0: 6f 6d 20 69 6e 64 65 78 20 2a 2f 0a 29 7b 0a 20 om index */.){.
1500: 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 69 48 unsigned int iH
1510: 61 73 68 20 3d 20 66 74 73 35 48 61 73 68 4b 65 ash = fts5HashKe
1520: 79 28 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20 y(pHash->nSlot,
1530: 70 54 6f 6b 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b pToken, nToken);
1540: 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 . Fts5HashEntry
1550: 20 2a 70 3b 0a 20 20 75 38 20 2a 70 50 74 72 3b *p;. u8 *pPtr;
1560: 0a 20 20 69 6e 74 20 6e 49 6e 63 72 20 3d 20 30 . int nIncr = 0
1570: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ;
1580: 20 20 20 2f 2a 20 41 6d 6f 75 6e 74 20 74 6f 20 /* Amount to
1590: 69 6e 63 72 65 6d 65 6e 74 20 28 2a 70 48 61 73 increment (*pHas
15a0: 68 2d 3e 70 6e 42 79 74 65 29 20 62 79 20 2a 2f h->pnByte) by */
15b0: 0a 0a 20 20 2f 2a 20 41 74 74 65 6d 70 74 20 74 .. /* Attempt t
15c0: 6f 20 6c 6f 63 61 74 65 20 61 6e 20 65 78 69 73 o locate an exis
15d0: 74 69 6e 67 20 68 61 73 68 20 65 6e 74 72 79 20 ting hash entry
15e0: 2a 2f 0a 20 20 66 6f 72 28 70 3d 70 48 61 73 68 */. for(p=pHash
15f0: 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d 3b 20 ->aSlot[iHash];
1600: 70 3b 20 70 3d 70 2d 3e 70 48 61 73 68 4e 65 78 p; p=p->pHashNex
1610: 74 29 7b 0a 20 20 20 20 69 66 28 20 6d 65 6d 63 t){. if( memc
1620: 6d 70 28 70 2d 3e 7a 4b 65 79 2c 20 70 54 6f 6b mp(p->zKey, pTok
1630: 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3d 3d 30 20 26 en, nToken)==0 &
1640: 26 20 70 2d 3e 7a 4b 65 79 5b 6e 54 6f 6b 65 6e & p->zKey[nToken
1650: 5d 3d 3d 30 20 29 20 62 72 65 61 6b 3b 0a 20 20 ]==0 ) break;.
1660: 7d 0a 0a 20 20 2f 2a 20 49 66 20 61 6e 20 65 78 }.. /* If an ex
1670: 69 73 74 69 6e 67 20 68 61 73 68 20 65 6e 74 72 isting hash entr
1680: 79 20 63 61 6e 6e 6f 74 20 62 65 20 66 6f 75 6e y cannot be foun
1690: 64 2c 20 63 72 65 61 74 65 20 61 20 6e 65 77 20 d, create a new
16a0: 6f 6e 65 2e 20 2a 2f 0a 20 20 69 66 28 20 70 3d one. */. if( p=
16b0: 3d 30 20 29 7b 0a 20 20 20 20 69 6e 74 20 6e 42 =0 ){. int nB
16c0: 79 74 65 20 3d 20 73 69 7a 65 6f 66 28 46 74 73 yte = sizeof(Fts
16d0: 35 48 61 73 68 45 6e 74 72 79 29 20 2b 20 6e 54 5HashEntry) + nT
16e0: 6f 6b 65 6e 20 2b 20 31 20 2b 20 36 34 3b 0a 20 oken + 1 + 64;.
16f0: 20 20 20 69 66 28 20 6e 42 79 74 65 3c 31 32 38 if( nByte<128
1700: 20 29 20 6e 42 79 74 65 20 3d 20 31 32 38 3b 0a ) nByte = 128;.
1710: 0a 20 20 20 20 69 66 28 20 28 70 48 61 73 68 2d . if( (pHash-
1720: 3e 6e 45 6e 74 72 79 2a 32 29 3e 3d 70 48 61 73 >nEntry*2)>=pHas
1730: 68 2d 3e 6e 53 6c 6f 74 20 29 7b 0a 20 20 20 20 h->nSlot ){.
1740: 20 20 69 6e 74 20 72 63 20 3d 20 66 74 73 35 48 int rc = fts5H
1750: 61 73 68 52 65 73 69 7a 65 28 70 48 61 73 68 29 ashResize(pHash)
1760: 3b 0a 20 20 20 20 20 20 69 66 28 20 72 63 21 3d ;. if( rc!=
1770: 53 51 4c 49 54 45 5f 4f 4b 20 29 20 72 65 74 75 SQLITE_OK ) retu
1780: 72 6e 20 72 63 3b 0a 20 20 20 20 20 20 69 48 61 rn rc;. iHa
1790: 73 68 20 3d 20 66 74 73 35 48 61 73 68 4b 65 79 sh = fts5HashKey
17a0: 28 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20 70 (pHash->nSlot, p
17b0: 54 6f 6b 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a Token, nToken);.
17c0: 20 20 20 20 7d 0a 0a 20 20 20 20 70 20 3d 20 28 }.. p = (
17d0: 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29 73 Fts5HashEntry*)s
17e0: 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e 42 qlite3_malloc(nB
17f0: 79 74 65 29 3b 0a 20 20 20 20 69 66 28 20 21 70 yte);. if( !p
1800: 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 ) return SQLITE
1810: 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 6d 65 6d 73 _NOMEM;. mems
1820: 65 74 28 70 2c 20 30 2c 20 73 69 7a 65 6f 66 28 et(p, 0, sizeof(
1830: 46 74 73 35 48 61 73 68 45 6e 74 72 79 29 29 3b Fts5HashEntry));
1840: 0a 20 20 20 20 70 2d 3e 6e 41 6c 6c 6f 63 20 3d . p->nAlloc =
1850: 20 6e 42 79 74 65 3b 0a 20 20 20 20 6d 65 6d 63 nByte;. memc
1860: 70 79 28 70 2d 3e 7a 4b 65 79 2c 20 70 54 6f 6b py(p->zKey, pTok
1870: 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 20 en, nToken);.
1880: 20 70 2d 3e 7a 4b 65 79 5b 6e 54 6f 6b 65 6e 5d p->zKey[nToken]
1890: 20 3d 20 27 5c 30 27 3b 0a 20 20 20 20 70 2d 3e = '\0';. p->
18a0: 6e 44 61 74 61 20 3d 20 6e 54 6f 6b 65 6e 20 2b nData = nToken +
18b0: 20 31 20 2b 20 73 69 7a 65 6f 66 28 46 74 73 35 1 + sizeof(Fts5
18c0: 48 61 73 68 45 6e 74 72 79 29 3b 0a 20 20 20 20 HashEntry);.
18d0: 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69 p->nData += sqli
18e0: 74 65 33 50 75 74 56 61 72 69 6e 74 28 26 28 28 te3PutVarint(&((
18f0: 75 38 2a 29 70 29 5b 70 2d 3e 6e 44 61 74 61 5d u8*)p)[p->nData]
1900: 2c 20 69 52 6f 77 69 64 29 3b 0a 20 20 20 20 70 , iRowid);. p
1910: 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 20 3d 20 70 ->iSzPoslist = p
1920: 2d 3e 6e 44 61 74 61 3b 0a 20 20 20 20 70 2d 3e ->nData;. p->
1930: 6e 44 61 74 61 20 2b 3d 20 31 3b 0a 20 20 20 20 nData += 1;.
1940: 70 2d 3e 69 52 6f 77 69 64 20 3d 20 69 52 6f 77 p->iRowid = iRow
1950: 69 64 3b 0a 20 20 20 20 70 2d 3e 70 48 61 73 68 id;. p->pHash
1960: 4e 65 78 74 20 3d 20 70 48 61 73 68 2d 3e 61 53 Next = pHash->aS
1970: 6c 6f 74 5b 69 48 61 73 68 5d 3b 0a 20 20 20 20 lot[iHash];.
1980: 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b 69 48 61 pHash->aSlot[iHa
1990: 73 68 5d 20 3d 20 70 3b 0a 20 20 20 20 70 48 61 sh] = p;. pHa
19a0: 73 68 2d 3e 6e 45 6e 74 72 79 2b 2b 3b 0a 20 20 sh->nEntry++;.
19b0: 20 20 6e 49 6e 63 72 20 2b 3d 20 70 2d 3e 6e 44 nIncr += p->nD
19c0: 61 74 61 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 43 ata;. }.. /* C
19d0: 68 65 63 6b 20 74 68 65 72 65 20 69 73 20 65 6e heck there is en
19e0: 6f 75 67 68 20 73 70 61 63 65 20 74 6f 20 61 70 ough space to ap
19f0: 70 65 6e 64 20 61 20 6e 65 77 20 65 6e 74 72 79 pend a new entry
1a00: 2e 20 57 6f 72 73 74 20 63 61 73 65 20 73 63 65 . Worst case sce
1a10: 6e 61 72 69 6f 0a 20 20 2a 2a 20 69 73 3a 0a 20 nario. ** is:.
1a20: 20 2a 2a 0a 20 20 2a 2a 20 20 20 20 20 2b 20 39 **. ** + 9
1a30: 20 62 79 74 65 73 20 66 6f 72 20 61 20 6e 65 77 bytes for a new
1a40: 20 72 6f 77 69 64 2c 0a 20 20 2a 2a 20 20 20 20 rowid,. **
1a50: 20 2b 20 34 20 62 79 74 65 20 72 65 73 65 72 76 + 4 byte reserv
1a60: 65 64 20 66 6f 72 20 74 68 65 20 22 70 6f 73 6c ed for the "posl
1a70: 69 73 74 20 73 69 7a 65 22 20 76 61 72 69 6e 74 ist size" varint
1a80: 2e 0a 20 20 2a 2a 20 20 20 20 20 2b 20 31 20 62 .. ** + 1 b
1a90: 79 74 65 20 66 6f 72 20 61 20 22 6e 65 77 20 63 yte for a "new c
1aa0: 6f 6c 75 6d 6e 22 20 62 79 74 65 2c 0a 20 20 2a olumn" byte,. *
1ab0: 2a 20 20 20 20 20 2b 20 33 20 62 79 74 65 73 20 * + 3 bytes
1ac0: 66 6f 72 20 61 20 6e 65 77 20 63 6f 6c 75 6d 6e for a new column
1ad0: 20 6e 75 6d 62 65 72 20 28 31 36 2d 62 69 74 20 number (16-bit
1ae0: 6d 61 78 29 20 61 73 20 61 20 76 61 72 69 6e 74 max) as a varint
1af0: 2c 0a 20 20 2a 2a 20 20 20 20 20 2b 20 35 20 62 ,. ** + 5 b
1b00: 79 74 65 73 20 66 6f 72 20 74 68 65 20 6e 65 77 ytes for the new
1b10: 20 70 6f 73 69 74 69 6f 6e 20 6f 66 66 73 65 74 position offset
1b20: 20 28 33 32 2d 62 69 74 20 6d 61 78 29 2e 0a 20 (32-bit max)..
1b30: 20 2a 2f 0a 20 20 69 66 28 20 28 70 2d 3e 6e 41 */. if( (p->nA
1b40: 6c 6c 6f 63 20 2d 20 70 2d 3e 6e 44 61 74 61 29 lloc - p->nData)
1b50: 20 3c 20 28 39 20 2b 20 34 20 2b 20 31 20 2b 20 < (9 + 4 + 1 +
1b60: 33 20 2b 20 35 29 20 29 7b 0a 20 20 20 20 69 6e 3 + 5) ){. in
1b70: 74 20 6e 4e 65 77 20 3d 20 70 2d 3e 6e 41 6c 6c t nNew = p->nAll
1b80: 6f 63 20 2a 20 32 3b 0a 20 20 20 20 46 74 73 35 oc * 2;. Fts5
1b90: 48 61 73 68 45 6e 74 72 79 20 2a 70 4e 65 77 3b HashEntry *pNew;
1ba0: 0a 20 20 20 20 46 74 73 35 48 61 73 68 45 6e 74 . Fts5HashEnt
1bb0: 72 79 20 2a 2a 70 70 3b 0a 20 20 20 20 70 4e 65 ry **pp;. pNe
1bc0: 77 20 3d 20 28 46 74 73 35 48 61 73 68 45 6e 74 w = (Fts5HashEnt
1bd0: 72 79 2a 29 73 71 6c 69 74 65 33 5f 72 65 61 6c ry*)sqlite3_real
1be0: 6c 6f 63 28 70 2c 20 6e 4e 65 77 29 3b 0a 20 20 loc(p, nNew);.
1bf0: 20 20 69 66 28 20 70 4e 65 77 3d 3d 30 20 29 20 if( pNew==0 )
1c00: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f return SQLITE_NO
1c10: 4d 45 4d 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e MEM;. pNew->n
1c20: 41 6c 6c 6f 63 20 3d 20 6e 4e 65 77 3b 0a 20 20 Alloc = nNew;.
1c30: 20 20 66 6f 72 28 70 70 3d 26 70 48 61 73 68 2d for(pp=&pHash-
1c40: 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d 3b 20 2a >aSlot[iHash]; *
1c50: 70 70 21 3d 70 3b 20 70 70 3d 26 28 2a 70 70 29 pp!=p; pp=&(*pp)
1c60: 2d 3e 70 48 61 73 68 4e 65 78 74 29 3b 0a 20 20 ->pHashNext);.
1c70: 20 20 2a 70 70 20 3d 20 70 4e 65 77 3b 0a 20 20 *pp = pNew;.
1c80: 20 20 70 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 0a p = pNew;. }.
1c90: 20 20 70 50 74 72 20 3d 20 28 75 38 2a 29 70 3b pPtr = (u8*)p;
1ca0: 0a 20 20 6e 49 6e 63 72 20 2d 3d 20 70 2d 3e 6e . nIncr -= p->n
1cb0: 44 61 74 61 3b 0a 0a 20 20 2f 2a 20 49 66 20 74 Data;.. /* If t
1cc0: 68 69 73 20 69 73 20 61 20 6e 65 77 20 72 6f 77 his is a new row
1cd0: 69 64 2c 20 61 70 70 65 6e 64 20 74 68 65 20 34 id, append the 4
1ce0: 2d 62 79 74 65 20 73 69 7a 65 20 66 69 65 6c 64 -byte size field
1cf0: 20 66 6f 72 20 74 68 65 20 70 72 65 76 69 6f 75 for the previou
1d00: 73 0a 20 20 2a 2a 20 65 6e 74 72 79 2c 20 61 6e s. ** entry, an
1d10: 64 20 74 68 65 20 6e 65 77 20 72 6f 77 69 64 20 d the new rowid
1d20: 66 6f 72 20 74 68 69 73 20 65 6e 74 72 79 2e 20 for this entry.
1d30: 20 2a 2f 0a 20 20 69 66 28 20 69 52 6f 77 69 64 */. if( iRowid
1d40: 21 3d 70 2d 3e 69 52 6f 77 69 64 20 29 7b 0a 20 !=p->iRowid ){.
1d50: 20 20 20 66 74 73 35 48 61 73 68 41 64 64 50 6f fts5HashAddPo
1d60: 73 6c 69 73 74 53 69 7a 65 28 70 29 3b 0a 20 20 slistSize(p);.
1d70: 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71 p->nData += sq
1d80: 6c 69 74 65 33 50 75 74 56 61 72 69 6e 74 28 26 lite3PutVarint(&
1d90: 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20 pPtr[p->nData],
1da0: 69 52 6f 77 69 64 20 2d 20 70 2d 3e 69 52 6f 77 iRowid - p->iRow
1db0: 69 64 29 3b 0a 20 20 20 20 70 2d 3e 69 53 7a 50 id);. p->iSzP
1dc0: 6f 73 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74 oslist = p->nDat
1dd0: 61 3b 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 a;. p->nData
1de0: 2b 3d 20 31 3b 0a 20 20 20 20 70 2d 3e 69 43 6f += 1;. p->iCo
1df0: 6c 20 3d 20 30 3b 0a 20 20 20 20 70 2d 3e 69 50 l = 0;. p->iP
1e00: 6f 73 20 3d 20 30 3b 0a 20 20 20 20 70 2d 3e 69 os = 0;. p->i
1e10: 52 6f 77 69 64 20 3d 20 69 52 6f 77 69 64 3b 0a Rowid = iRowid;.
1e20: 20 20 7d 0a 0a 20 20 69 66 28 20 69 43 6f 6c 3e }.. if( iCol>
1e30: 3d 30 20 29 7b 0a 20 20 20 20 2f 2a 20 41 70 70 =0 ){. /* App
1e40: 65 6e 64 20 61 20 6e 65 77 20 63 6f 6c 75 6d 6e end a new column
1e50: 20 76 61 6c 75 65 2c 20 69 66 20 6e 65 63 65 73 value, if neces
1e60: 73 61 72 79 20 2a 2f 0a 20 20 20 20 61 73 73 65 sary */. asse
1e70: 72 74 28 20 69 43 6f 6c 3e 3d 70 2d 3e 69 43 6f rt( iCol>=p->iCo
1e80: 6c 20 29 3b 0a 20 20 20 20 69 66 28 20 69 43 6f l );. if( iCo
1e90: 6c 21 3d 70 2d 3e 69 43 6f 6c 20 29 7b 0a 20 20 l!=p->iCol ){.
1ea0: 20 20 20 20 70 50 74 72 5b 70 2d 3e 6e 44 61 74 pPtr[p->nDat
1eb0: 61 2b 2b 5d 20 3d 20 30 78 30 31 3b 0a 20 20 20 a++] = 0x01;.
1ec0: 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 p->nData += s
1ed0: 71 6c 69 74 65 33 50 75 74 56 61 72 69 6e 74 28 qlite3PutVarint(
1ee0: 26 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61 5d 2c &pPtr[p->nData],
1ef0: 20 69 43 6f 6c 29 3b 0a 20 20 20 20 20 20 70 2d iCol);. p-
1f00: 3e 69 43 6f 6c 20 3d 20 69 43 6f 6c 3b 0a 20 20 >iCol = iCol;.
1f10: 20 20 20 20 70 2d 3e 69 50 6f 73 20 3d 20 30 3b p->iPos = 0;
1f20: 0a 20 20 20 20 7d 0a 0a 20 20 20 20 2f 2a 20 41 . }.. /* A
1f30: 70 70 65 6e 64 20 74 68 65 20 6e 65 77 20 70 6f ppend the new po
1f40: 73 69 74 69 6f 6e 20 6f 66 66 73 65 74 20 2a 2f sition offset */
1f50: 0a 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d . p->nData +=
1f60: 20 73 71 6c 69 74 65 33 50 75 74 56 61 72 69 6e sqlite3PutVarin
1f70: 74 28 26 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61 t(&pPtr[p->nData
1f80: 5d 2c 20 69 50 6f 73 20 2d 20 70 2d 3e 69 50 6f ], iPos - p->iPo
1f90: 73 20 2b 20 32 29 3b 0a 20 20 20 20 70 2d 3e 69 s + 2);. p->i
1fa0: 50 6f 73 20 3d 20 69 50 6f 73 3b 0a 20 20 7d 0a Pos = iPos;. }.
1fb0: 20 20 6e 49 6e 63 72 20 2b 3d 20 70 2d 3e 6e 44 nIncr += p->nD
1fc0: 61 74 61 3b 0a 0a 20 20 2a 70 48 61 73 68 2d 3e ata;.. *pHash->
1fd0: 70 6e 42 79 74 65 20 2b 3d 20 6e 49 6e 63 72 3b pnByte += nIncr;
1fe0: 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 . return SQLITE
1ff0: 5f 4f 4b 3b 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a 20 41 _OK;.}.../*.** A
2000: 72 67 75 6d 65 6e 74 73 20 70 4c 65 66 74 20 61 rguments pLeft a
2010: 6e 64 20 70 52 69 67 68 74 20 70 6f 69 6e 74 20 nd pRight point
2020: 74 6f 20 6c 69 6e 6b 65 64 2d 6c 69 73 74 73 20 to linked-lists
2030: 6f 66 20 68 61 73 68 2d 65 6e 74 72 79 20 6f 62 of hash-entry ob
2040: 6a 65 63 74 73 2c 0a 2a 2a 20 65 61 63 68 20 73 jects,.** each s
2050: 6f 72 74 65 64 20 69 6e 20 6b 65 79 20 6f 72 64 orted in key ord
2060: 65 72 2e 20 54 68 69 73 20 66 75 6e 63 74 69 6f er. This functio
2070: 6e 20 6d 65 72 67 65 73 20 74 68 65 20 74 77 6f n merges the two
2080: 20 6c 69 73 74 73 20 69 6e 74 6f 20 61 0a 2a 2a lists into a.**
2090: 20 73 69 6e 67 6c 65 20 6c 69 73 74 20 61 6e 64 single list and
20a0: 20 72 65 74 75 72 6e 73 20 61 20 70 6f 69 6e 74 returns a point
20b0: 65 72 20 74 6f 20 69 74 73 20 66 69 72 73 74 20 er to its first
20c0: 65 6c 65 6d 65 6e 74 2e 0a 2a 2f 0a 73 74 61 74 element..*/.stat
20d0: 69 63 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 ic Fts5HashEntry
20e0: 20 2a 66 74 73 35 48 61 73 68 45 6e 74 72 79 4d *fts5HashEntryM
20f0: 65 72 67 65 28 0a 20 20 46 74 73 35 48 61 73 68 erge(. Fts5Hash
2100: 45 6e 74 72 79 20 2a 70 4c 65 66 74 2c 0a 20 20 Entry *pLeft,.
2110: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 Fts5HashEntry *p
2120: 52 69 67 68 74 0a 29 7b 0a 20 20 46 74 73 35 48 Right.){. Fts5H
2130: 61 73 68 45 6e 74 72 79 20 2a 70 31 20 3d 20 70 ashEntry *p1 = p
2140: 4c 65 66 74 3b 0a 20 20 46 74 73 35 48 61 73 68 Left;. Fts5Hash
2150: 45 6e 74 72 79 20 2a 70 32 20 3d 20 70 52 69 67 Entry *p2 = pRig
2160: 68 74 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e ht;. Fts5HashEn
2170: 74 72 79 20 2a 70 52 65 74 20 3d 20 30 3b 0a 20 try *pRet = 0;.
2180: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a Fts5HashEntry *
2190: 2a 70 70 4f 75 74 20 3d 20 26 70 52 65 74 3b 0a *ppOut = &pRet;.
21a0: 0a 20 20 77 68 69 6c 65 28 20 70 31 20 7c 7c 20 . while( p1 ||
21b0: 70 32 20 29 7b 0a 20 20 20 20 69 66 28 20 70 31 p2 ){. if( p1
21c0: 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 2a 70 70 ==0 ){. *pp
21d0: 4f 75 74 20 3d 20 70 32 3b 0a 20 20 20 20 20 20 Out = p2;.
21e0: 70 32 20 3d 20 30 3b 0a 20 20 20 20 7d 65 6c 73 p2 = 0;. }els
21f0: 65 20 69 66 28 20 70 32 3d 3d 30 20 29 7b 0a 20 e if( p2==0 ){.
2200: 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 70 31 *ppOut = p1
2210: 3b 0a 20 20 20 20 20 20 70 31 20 3d 20 30 3b 0a ;. p1 = 0;.
2220: 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 }else{.
2230: 20 69 6e 74 20 69 20 3d 20 30 3b 0a 20 20 20 20 int i = 0;.
2240: 20 20 77 68 69 6c 65 28 20 70 31 2d 3e 7a 4b 65 while( p1->zKe
2250: 79 5b 69 5d 3d 3d 70 32 2d 3e 7a 4b 65 79 5b 69 y[i]==p2->zKey[i
2260: 5d 20 29 20 69 2b 2b 3b 0a 0a 20 20 20 20 20 20 ] ) i++;..
2270: 69 66 28 20 28 28 75 38 29 70 31 2d 3e 7a 4b 65 if( ((u8)p1->zKe
2280: 79 5b 69 5d 29 3e 28 28 75 38 29 70 32 2d 3e 7a y[i])>((u8)p2->z
2290: 4b 65 79 5b 69 5d 29 20 29 7b 0a 20 20 20 20 20 Key[i]) ){.
22a0: 20 20 20 2f 2a 20 70 32 20 69 73 20 73 6d 61 6c /* p2 is smal
22b0: 6c 65 72 20 2a 2f 0a 20 20 20 20 20 20 20 20 2a ler */. *
22c0: 70 70 4f 75 74 20 3d 20 70 32 3b 0a 20 20 20 20 ppOut = p2;.
22d0: 20 20 20 20 70 70 4f 75 74 20 3d 20 26 70 32 2d ppOut = &p2-
22e0: 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 20 20 20 20 >pScanNext;.
22f0: 20 20 20 20 70 32 20 3d 20 70 32 2d 3e 70 53 63 p2 = p2->pSc
2300: 61 6e 4e 65 78 74 3b 0a 20 20 20 20 20 20 7d 65 anNext;. }e
2310: 6c 73 65 7b 0a 20 20 20 20 20 20 20 20 2f 2a 20 lse{. /*
2320: 70 31 20 69 73 20 73 6d 61 6c 6c 65 72 20 2a 2f p1 is smaller */
2330: 0a 20 20 20 20 20 20 20 20 2a 70 70 4f 75 74 20 . *ppOut
2340: 3d 20 70 31 3b 0a 20 20 20 20 20 20 20 20 70 70 = p1;. pp
2350: 4f 75 74 20 3d 20 26 70 31 2d 3e 70 53 63 61 6e Out = &p1->pScan
2360: 4e 65 78 74 3b 0a 20 20 20 20 20 20 20 20 70 31 Next;. p1
2370: 20 3d 20 70 31 2d 3e 70 53 63 61 6e 4e 65 78 74 = p1->pScanNext
2380: 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 ;. }.
2390: 2a 70 70 4f 75 74 20 3d 20 30 3b 0a 20 20 20 20 *ppOut = 0;.
23a0: 7d 0a 20 20 7d 0a 0a 20 20 72 65 74 75 72 6e 20 }. }.. return
23b0: 70 52 65 74 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 45 pRet;.}../*.** E
23c0: 78 74 72 61 63 74 20 61 6c 6c 20 74 6f 6b 65 6e xtract all token
23d0: 73 20 66 72 6f 6d 20 68 61 73 68 20 74 61 62 6c s from hash tabl
23e0: 65 20 69 48 61 73 68 20 61 6e 64 20 6c 69 6e 6b e iHash and link
23f0: 20 74 68 65 6d 20 69 6e 74 6f 20 61 20 6c 69 73 them into a lis
2400: 74 0a 2a 2a 20 69 6e 20 73 6f 72 74 65 64 20 6f t.** in sorted o
2410: 72 64 65 72 2e 20 54 68 65 20 68 61 73 68 20 74 rder. The hash t
2420: 61 62 6c 65 20 69 73 20 63 6c 65 61 72 65 64 20 able is cleared
2430: 62 65 66 6f 72 65 20 72 65 74 75 72 6e 69 6e 67 before returning
2440: 2e 20 49 74 20 69 73 0a 2a 2a 20 74 68 65 20 72 . It is.** the r
2450: 65 73 70 6f 6e 73 69 62 69 6c 69 74 79 20 6f 66 esponsibility of
2460: 20 74 68 65 20 63 61 6c 6c 65 72 20 74 6f 20 66 the caller to f
2470: 72 65 65 20 74 68 65 20 65 6c 65 6d 65 6e 74 73 ree the elements
2480: 20 6f 66 20 74 68 65 20 72 65 74 75 72 6e 65 64 of the returned
2490: 0a 2a 2a 20 6c 69 73 74 2e 0a 2a 2f 0a 73 74 61 .** list..*/.sta
24a0: 74 69 63 20 69 6e 74 20 66 74 73 35 48 61 73 68 tic int fts5Hash
24b0: 45 6e 74 72 79 53 6f 72 74 28 0a 20 20 46 74 73 EntrySort(. Fts
24c0: 35 48 61 73 68 20 2a 70 48 61 73 68 2c 20 0a 20 5Hash *pHash, .
24d0: 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 54 65 const char *pTe
24e0: 72 6d 2c 20 69 6e 74 20 6e 54 65 72 6d 2c 20 20 rm, int nTerm,
24f0: 20 2f 2a 20 51 75 65 72 79 20 70 72 65 66 69 78 /* Query prefix
2500: 2c 20 69 66 20 61 6e 79 20 2a 2f 0a 20 20 46 74 , if any */. Ft
2510: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 70 70 s5HashEntry **pp
2520: 53 6f 72 74 65 64 0a 29 7b 0a 20 20 63 6f 6e 73 Sorted.){. cons
2530: 74 20 69 6e 74 20 6e 4d 65 72 67 65 53 6c 6f 74 t int nMergeSlot
2540: 20 3d 20 33 32 3b 0a 20 20 46 74 73 35 48 61 73 = 32;. Fts5Has
2550: 68 45 6e 74 72 79 20 2a 2a 61 70 3b 0a 20 20 46 hEntry **ap;. F
2560: 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 4c ts5HashEntry *pL
2570: 69 73 74 3b 0a 20 20 69 6e 74 20 69 53 6c 6f 74 ist;. int iSlot
2580: 3b 0a 20 20 69 6e 74 20 69 3b 0a 0a 20 20 2a 70 ;. int i;.. *p
2590: 70 53 6f 72 74 65 64 20 3d 20 30 3b 0a 20 20 61 pSorted = 0;. a
25a0: 70 20 3d 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c p = sqlite3_mall
25b0: 6f 63 28 73 69 7a 65 6f 66 28 46 74 73 35 48 61 oc(sizeof(Fts5Ha
25c0: 73 68 45 6e 74 72 79 2a 29 20 2a 20 6e 4d 65 72 shEntry*) * nMer
25d0: 67 65 53 6c 6f 74 29 3b 0a 20 20 69 66 28 20 21 geSlot);. if( !
25e0: 61 70 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49 ap ) return SQLI
25f0: 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 6d 65 6d 73 TE_NOMEM;. mems
2600: 65 74 28 61 70 2c 20 30 2c 20 73 69 7a 65 6f 66 et(ap, 0, sizeof
2610: 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29 (Fts5HashEntry*)
2620: 20 2a 20 6e 4d 65 72 67 65 53 6c 6f 74 29 3b 0a * nMergeSlot);.
2630: 0a 20 20 66 6f 72 28 69 53 6c 6f 74 3d 30 3b 20 . for(iSlot=0;
2640: 69 53 6c 6f 74 3c 70 48 61 73 68 2d 3e 6e 53 6c iSlot<pHash->nSl
2650: 6f 74 3b 20 69 53 6c 6f 74 2b 2b 29 7b 0a 20 20 ot; iSlot++){.
2660: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 Fts5HashEntry
2670: 2a 70 49 74 65 72 3b 0a 20 20 20 20 66 6f 72 28 *pIter;. for(
2680: 70 49 74 65 72 3d 70 48 61 73 68 2d 3e 61 53 6c pIter=pHash->aSl
2690: 6f 74 5b 69 53 6c 6f 74 5d 3b 20 70 49 74 65 72 ot[iSlot]; pIter
26a0: 3b 20 70 49 74 65 72 3d 70 49 74 65 72 2d 3e 70 ; pIter=pIter->p
26b0: 48 61 73 68 4e 65 78 74 29 7b 0a 20 20 20 20 20 HashNext){.
26c0: 20 69 66 28 20 70 54 65 72 6d 3d 3d 30 20 7c 7c if( pTerm==0 ||
26d0: 20 30 3d 3d 6d 65 6d 63 6d 70 28 70 49 74 65 72 0==memcmp(pIter
26e0: 2d 3e 7a 4b 65 79 2c 20 70 54 65 72 6d 2c 20 6e ->zKey, pTerm, n
26f0: 54 65 72 6d 29 20 29 7b 0a 20 20 20 20 20 20 20 Term) ){.
2700: 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a Fts5HashEntry *
2710: 70 45 6e 74 72 79 20 3d 20 70 49 74 65 72 3b 0a pEntry = pIter;.
2720: 20 20 20 20 20 20 20 20 70 45 6e 74 72 79 2d 3e pEntry->
2730: 70 53 63 61 6e 4e 65 78 74 20 3d 20 30 3b 0a 20 pScanNext = 0;.
2740: 20 20 20 20 20 20 20 66 6f 72 28 69 3d 30 3b 20 for(i=0;
2750: 61 70 5b 69 5d 3b 20 69 2b 2b 29 7b 0a 20 20 20 ap[i]; i++){.
2760: 20 20 20 20 20 20 20 70 45 6e 74 72 79 20 3d 20 pEntry =
2770: 66 74 73 35 48 61 73 68 45 6e 74 72 79 4d 65 72 fts5HashEntryMer
2780: 67 65 28 70 45 6e 74 72 79 2c 20 61 70 5b 69 5d ge(pEntry, ap[i]
2790: 29 3b 0a 20 20 20 20 20 20 20 20 20 20 61 70 5b );. ap[
27a0: 69 5d 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 i] = 0;.
27b0: 7d 0a 20 20 20 20 20 20 20 20 61 70 5b 69 5d 20 }. ap[i]
27c0: 3d 20 70 45 6e 74 72 79 3b 0a 20 20 20 20 20 20 = pEntry;.
27d0: 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 70 }. }. }.. p
27e0: 4c 69 73 74 20 3d 20 30 3b 0a 20 20 66 6f 72 28 List = 0;. for(
27f0: 69 3d 30 3b 20 69 3c 6e 4d 65 72 67 65 53 6c 6f i=0; i<nMergeSlo
2800: 74 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 70 4c 69 t; i++){. pLi
2810: 73 74 20 3d 20 66 74 73 35 48 61 73 68 45 6e 74 st = fts5HashEnt
2820: 72 79 4d 65 72 67 65 28 70 4c 69 73 74 2c 20 61 ryMerge(pList, a
2830: 70 5b 69 5d 29 3b 0a 20 20 7d 0a 0a 20 20 70 48 p[i]);. }.. pH
2840: 61 73 68 2d 3e 6e 45 6e 74 72 79 20 3d 20 30 3b ash->nEntry = 0;
2850: 0a 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 . sqlite3_free(
2860: 61 70 29 3b 0a 20 20 2a 70 70 53 6f 72 74 65 64 ap);. *ppSorted
2870: 20 3d 20 70 4c 69 73 74 3b 0a 20 20 72 65 74 75 = pList;. retu
2880: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a rn SQLITE_OK;.}.
2890: 0a 2f 2a 0a 2a 2a 20 51 75 65 72 79 20 74 68 65 ./*.** Query the
28a0: 20 68 61 73 68 20 74 61 62 6c 65 20 66 6f 72 20 hash table for
28b0: 61 20 64 6f 63 6c 69 73 74 20 61 73 73 6f 63 69 a doclist associ
28c0: 61 74 65 64 20 77 69 74 68 20 74 65 72 6d 20 70 ated with term p
28d0: 54 65 72 6d 2f 6e 54 65 72 6d 2e 0a 2a 2f 0a 69 Term/nTerm..*/.i
28e0: 6e 74 20 73 71 6c 69 74 65 33 46 74 73 35 48 61 nt sqlite3Fts5Ha
28f0: 73 68 51 75 65 72 79 28 0a 20 20 46 74 73 35 48 shQuery(. Fts5H
2900: 61 73 68 20 2a 70 48 61 73 68 2c 20 20 20 20 20 ash *pHash,
2910: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 48 61 /* Ha
2920: 73 68 20 74 61 62 6c 65 20 74 6f 20 71 75 65 72 sh table to quer
2930: 79 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61 y */. const cha
2940: 72 20 2a 70 54 65 72 6d 2c 20 69 6e 74 20 6e 54 r *pTerm, int nT
2950: 65 72 6d 2c 20 20 20 2f 2a 20 51 75 65 72 79 20 erm, /* Query
2960: 74 65 72 6d 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 term */. const
2970: 75 38 20 2a 2a 70 70 44 6f 63 6c 69 73 74 2c 20 u8 **ppDoclist,
2980: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 /* OUT
2990: 3a 20 50 6f 69 6e 74 65 72 20 74 6f 20 64 6f 63 : Pointer to doc
29a0: 6c 69 73 74 20 66 6f 72 20 70 54 65 72 6d 20 2a list for pTerm *
29b0: 2f 0a 20 20 69 6e 74 20 2a 70 6e 44 6f 63 6c 69 /. int *pnDocli
29c0: 73 74 20 20 20 20 20 20 20 20 20 20 20 20 20 20 st
29d0: 20 20 20 20 2f 2a 20 4f 55 54 3a 20 53 69 7a 65 /* OUT: Size
29e0: 20 6f 66 20 64 6f 63 6c 69 73 74 20 69 6e 20 62 of doclist in b
29f0: 79 74 65 73 20 2a 2f 0a 29 7b 0a 20 20 75 6e 73 ytes */.){. uns
2a00: 69 67 6e 65 64 20 69 6e 74 20 69 48 61 73 68 20 igned int iHash
2a10: 3d 20 66 74 73 35 48 61 73 68 4b 65 79 28 70 48 = fts5HashKey(pH
2a20: 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20 70 54 65 72 ash->nSlot, pTer
2a30: 6d 2c 20 6e 54 65 72 6d 29 3b 0a 20 20 46 74 73 m, nTerm);. Fts
2a40: 35 48 61 73 68 45 6e 74 72 79 20 2a 70 3b 0a 0a 5HashEntry *p;..
2a50: 20 20 66 6f 72 28 70 3d 70 48 61 73 68 2d 3e 61 for(p=pHash->a
2a60: 53 6c 6f 74 5b 69 48 61 73 68 5d 3b 20 70 3b 20 Slot[iHash]; p;
2a70: 70 3d 70 2d 3e 70 48 61 73 68 4e 65 78 74 29 7b p=p->pHashNext){
2a80: 0a 20 20 20 20 69 66 28 20 6d 65 6d 63 6d 70 28 . if( memcmp(
2a90: 70 2d 3e 7a 4b 65 79 2c 20 70 54 65 72 6d 2c 20 p->zKey, pTerm,
2aa0: 6e 54 65 72 6d 29 3d 3d 30 20 26 26 20 70 2d 3e nTerm)==0 && p->
2ab0: 7a 4b 65 79 5b 6e 54 65 72 6d 5d 3d 3d 30 20 29 zKey[nTerm]==0 )
2ac0: 20 62 72 65 61 6b 3b 0a 20 20 7d 0a 0a 20 20 69 break;. }.. i
2ad0: 66 28 20 70 20 29 7b 0a 20 20 20 20 66 74 73 35 f( p ){. fts5
2ae0: 48 61 73 68 41 64 64 50 6f 73 6c 69 73 74 53 69 HashAddPoslistSi
2af0: 7a 65 28 70 29 3b 0a 20 20 20 20 2a 70 70 44 6f ze(p);. *ppDo
2b00: 63 6c 69 73 74 20 3d 20 28 63 6f 6e 73 74 20 75 clist = (const u
2b10: 38 2a 29 26 70 2d 3e 7a 4b 65 79 5b 6e 54 65 72 8*)&p->zKey[nTer
2b20: 6d 2b 31 5d 3b 0a 20 20 20 20 2a 70 6e 44 6f 63 m+1];. *pnDoc
2b30: 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74 61 20 list = p->nData
2b40: 2d 20 28 73 69 7a 65 6f 66 28 2a 70 29 20 2b 20 - (sizeof(*p) +
2b50: 6e 54 65 72 6d 20 2b 20 31 29 3b 0a 20 20 7d 65 nTerm + 1);. }e
2b60: 6c 73 65 7b 0a 20 20 20 20 2a 70 70 44 6f 63 6c lse{. *ppDocl
2b70: 69 73 74 20 3d 20 30 3b 0a 20 20 20 20 2a 70 6e ist = 0;. *pn
2b80: 44 6f 63 6c 69 73 74 20 3d 20 30 3b 0a 20 20 7d Doclist = 0;. }
2b90: 0a 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 .. return SQLIT
2ba0: 45 5f 4f 4b 3b 0a 7d 0a 0a 69 6e 74 20 73 71 6c E_OK;.}..int sql
2bb0: 69 74 65 33 46 74 73 35 48 61 73 68 53 63 61 6e ite3Fts5HashScan
2bc0: 49 6e 69 74 28 0a 20 20 46 74 73 35 48 61 73 68 Init(. Fts5Hash
2bd0: 20 2a 70 2c 20 20 20 20 20 20 20 20 20 20 20 20 *p,
2be0: 20 20 20 20 20 20 20 20 2f 2a 20 48 61 73 68 20 /* Hash
2bf0: 74 61 62 6c 65 20 74 6f 20 71 75 65 72 79 20 2a table to query *
2c00: 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a /. const char *
2c10: 70 54 65 72 6d 2c 20 69 6e 74 20 6e 54 65 72 6d pTerm, int nTerm
2c20: 20 20 20 20 2f 2a 20 51 75 65 72 79 20 70 72 65 /* Query pre
2c30: 66 69 78 20 2a 2f 0a 29 7b 0a 20 20 72 65 74 75 fix */.){. retu
2c40: 72 6e 20 66 74 73 35 48 61 73 68 45 6e 74 72 79 rn fts5HashEntry
2c50: 53 6f 72 74 28 70 2c 20 70 54 65 72 6d 2c 20 6e Sort(p, pTerm, n
2c60: 54 65 72 6d 2c 20 26 70 2d 3e 70 53 63 61 6e 29 Term, &p->pScan)
2c70: 3b 0a 7d 0a 0a 76 6f 69 64 20 73 71 6c 69 74 65 ;.}..void sqlite
2c80: 33 46 74 73 35 48 61 73 68 53 63 61 6e 4e 65 78 3Fts5HashScanNex
2c90: 74 28 46 74 73 35 48 61 73 68 20 2a 70 29 7b 0a t(Fts5Hash *p){.
2ca0: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 Fts5HashEntry
2cb0: 2a 70 53 63 61 6e 20 3d 20 70 2d 3e 70 53 63 61 *pScan = p->pSca
2cc0: 6e 3b 0a 20 20 69 66 28 20 70 53 63 61 6e 20 29 n;. if( pScan )
2cd0: 20 70 2d 3e 70 53 63 61 6e 20 3d 20 70 53 63 61 p->pScan = pSca
2ce0: 6e 2d 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 7d 0a n->pScanNext;.}.
2cf0: 0a 69 6e 74 20 73 71 6c 69 74 65 33 46 74 73 35 .int sqlite3Fts5
2d00: 48 61 73 68 53 63 61 6e 45 6f 66 28 46 74 73 35 HashScanEof(Fts5
2d10: 48 61 73 68 20 2a 70 29 7b 0a 20 20 72 65 74 75 Hash *p){. retu
2d20: 72 6e 20 28 70 2d 3e 70 53 63 61 6e 3d 3d 30 29 rn (p->pScan==0)
2d30: 3b 0a 7d 0a 0a 76 6f 69 64 20 73 71 6c 69 74 65 ;.}..void sqlite
2d40: 33 46 74 73 35 48 61 73 68 53 63 61 6e 45 6e 74 3Fts5HashScanEnt
2d50: 72 79 28 0a 20 20 46 74 73 35 48 61 73 68 20 2a ry(. Fts5Hash *
2d60: 70 48 61 73 68 2c 0a 20 20 63 6f 6e 73 74 20 63 pHash,. const c
2d70: 68 61 72 20 2a 2a 70 7a 54 65 72 6d 2c 20 20 20 har **pzTerm,
2d80: 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 3a /* OUT:
2d90: 20 74 65 72 6d 20 28 6e 75 6c 2d 74 65 72 6d 69 term (nul-termi
2da0: 6e 61 74 65 64 29 20 2a 2f 0a 20 20 63 6f 6e 73 nated) */. cons
2db0: 74 20 75 38 20 2a 2a 70 70 44 6f 63 6c 69 73 74 t u8 **ppDoclist
2dc0: 2c 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f , /* O
2dd0: 55 54 3a 20 70 6f 69 6e 74 65 72 20 74 6f 20 64 UT: pointer to d
2de0: 6f 63 6c 69 73 74 20 2a 2f 0a 20 20 69 6e 74 20 oclist */. int
2df0: 2a 70 6e 44 6f 63 6c 69 73 74 20 20 20 20 20 20 *pnDoclist
2e00: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f /* O
2e10: 55 54 3a 20 73 69 7a 65 20 6f 66 20 64 6f 63 6c UT: size of docl
2e20: 69 73 74 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a ist in bytes */.
2e30: 29 7b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 ){. Fts5HashEnt
2e40: 72 79 20 2a 70 3b 0a 20 20 69 66 28 20 28 70 20 ry *p;. if( (p
2e50: 3d 20 70 48 61 73 68 2d 3e 70 53 63 61 6e 29 20 = pHash->pScan)
2e60: 29 7b 0a 20 20 20 20 69 6e 74 20 6e 54 65 72 6d ){. int nTerm
2e70: 20 3d 20 73 74 72 6c 65 6e 28 70 2d 3e 7a 4b 65 = strlen(p->zKe
2e80: 79 29 3b 0a 20 20 20 20 66 74 73 35 48 61 73 68 y);. fts5Hash
2e90: 41 64 64 50 6f 73 6c 69 73 74 53 69 7a 65 28 70 AddPoslistSize(p
2ea0: 29 3b 0a 20 20 20 20 2a 70 7a 54 65 72 6d 20 3d );. *pzTerm =
2eb0: 20 70 2d 3e 7a 4b 65 79 3b 0a 20 20 20 20 2a 70 p->zKey;. *p
2ec0: 70 44 6f 63 6c 69 73 74 20 3d 20 28 63 6f 6e 73 pDoclist = (cons
2ed0: 74 20 75 38 2a 29 26 70 2d 3e 7a 4b 65 79 5b 6e t u8*)&p->zKey[n
2ee0: 54 65 72 6d 2b 31 5d 3b 0a 20 20 20 20 2a 70 6e Term+1];. *pn
2ef0: 44 6f 63 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 Doclist = p->nDa
2f00: 74 61 20 2d 20 28 73 69 7a 65 6f 66 28 2a 70 29 ta - (sizeof(*p)
2f10: 20 2b 20 6e 54 65 72 6d 20 2b 20 31 29 3b 0a 20 + nTerm + 1);.
2f20: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 2a 70 7a 54 }else{. *pzT
2f30: 65 72 6d 20 3d 20 30 3b 0a 20 20 20 20 2a 70 70 erm = 0;. *pp
2f40: 44 6f 63 6c 69 73 74 20 3d 20 30 3b 0a 20 20 20 Doclist = 0;.
2f50: 20 2a 70 6e 44 6f 63 6c 69 73 74 20 3d 20 30 3b *pnDoclist = 0;
2f60: 0a 20 20 7d 0a 7d 0a 0a 23 65 6e 64 69 66 20 2f . }.}..#endif /
2f70: 2a 20 53 51 4c 49 54 45 5f 45 4e 41 42 4c 45 5f * SQLITE_ENABLE_
2f80: 46 54 53 35 20 2a 2f 0a FTS5 */.