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 70 53 63 61 6e HashEntry *pScan
0360: 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 ; /* C
0370: 75 72 72 65 6e 74 20 6f 72 64 65 72 65 64 20 73 urrent ordered s
0380: 63 61 6e 20 69 74 65 6d 20 2a 2f 0a 20 20 46 74 can item */. Ft
0390: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 61 53 s5HashEntry **aS
03a0: 6c 6f 74 3b 20 20 20 20 20 20 20 20 20 20 2f 2a lot; /*
03b0: 20 41 72 72 61 79 20 6f 66 20 68 61 73 68 20 73 Array of hash s
03c0: 6c 6f 74 73 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a lots */.};../*.*
03d0: 2a 20 45 61 63 68 20 65 6e 74 72 79 20 69 6e 20 * Each entry in
03e0: 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 69 the hash table i
03f0: 73 20 72 65 70 72 65 73 65 6e 74 65 64 20 62 79 s represented by
0400: 20 61 6e 20 6f 62 6a 65 63 74 20 6f 66 20 74 68 an object of th
0410: 65 20 0a 2a 2a 20 66 6f 6c 6c 6f 77 69 6e 67 20 e .** following
0420: 74 79 70 65 2e 20 45 61 63 68 20 6f 62 6a 65 63 type. Each objec
0430: 74 2c 20 69 74 73 20 6b 65 79 20 28 7a 4b 65 79 t, its key (zKey
0440: 5b 5d 29 20 61 6e 64 20 69 74 73 20 63 75 72 72 []) and its curr
0450: 65 6e 74 20 64 61 74 61 0a 2a 2a 20 61 72 65 20 ent data.** are
0460: 73 74 6f 72 65 64 20 69 6e 20 61 20 73 69 6e 67 stored in a sing
0470: 6c 65 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f 63 61 le memory alloca
0480: 74 69 6f 6e 2e 20 54 68 65 20 70 6f 73 69 74 69 tion. The positi
0490: 6f 6e 20 6c 69 73 74 20 64 61 74 61 20 0a 2a 2a on list data .**
04a0: 20 69 6d 6d 65 64 69 61 74 65 6c 79 20 66 6f 6c immediately fol
04b0: 6c 6f 77 73 20 74 68 65 20 6b 65 79 20 64 61 74 lows the key dat
04c0: 61 20 69 6e 20 6d 65 6d 6f 72 79 2e 0a 2a 2a 0a a in memory..**.
04d0: 2a 2a 20 54 68 65 20 64 61 74 61 20 74 68 61 74 ** The data that
04e0: 20 66 6f 6c 6c 6f 77 73 20 74 68 65 20 6b 65 79 follows the key
04f0: 20 69 73 20 69 6e 20 61 20 73 69 6d 69 6c 61 72 is in a similar
0500: 2c 20 62 75 74 20 6e 6f 74 20 69 64 65 6e 74 69 , but not identi
0510: 63 61 6c 20 66 6f 72 6d 61 74 0a 2a 2a 20 74 6f cal format.** to
0520: 20 74 68 65 20 64 6f 63 6c 69 73 74 20 64 61 74 the doclist dat
0530: 61 20 73 74 6f 72 65 64 20 69 6e 20 74 68 65 20 a stored in the
0540: 64 61 74 61 62 61 73 65 2e 20 49 74 20 69 73 3a database. It is:
0550: 0a 2a 2a 0a 2a 2a 20 20 20 2a 20 52 6f 77 69 64 .**.** * Rowid
0560: 2c 20 61 73 20 61 20 76 61 72 69 6e 74 0a 2a 2a , as a varint.**
0570: 20 20 20 2a 20 50 6f 73 69 74 69 6f 6e 20 6c 69 * Position li
0580: 73 74 2c 20 77 69 74 68 6f 75 74 20 30 78 30 30 st, without 0x00
0590: 20 74 65 72 6d 69 6e 61 74 6f 72 2e 0a 2a 2a 20 terminator..**
05a0: 20 20 2a 20 53 69 7a 65 20 6f 66 20 70 72 65 76 * Size of prev
05b0: 69 6f 75 73 20 70 6f 73 69 74 69 6f 6e 20 6c 69 ious position li
05c0: 73 74 20 61 6e 64 20 72 6f 77 69 64 2c 20 61 73 st and rowid, as
05d0: 20 61 20 34 20 62 79 74 65 0a 2a 2a 20 20 20 20 a 4 byte.**
05e0: 20 62 69 67 2d 65 6e 64 69 61 6e 20 69 6e 74 65 big-endian inte
05f0: 67 65 72 2e 0a 2a 2a 0a 2a 2a 20 69 52 6f 77 69 ger..**.** iRowi
0600: 64 4f 66 66 3a 0a 2a 2a 20 20 20 4f 66 66 73 65 dOff:.** Offse
0610: 74 20 6f 66 20 6c 61 73 74 20 72 6f 77 69 64 20 t of last rowid
0620: 77 72 69 74 74 65 6e 20 74 6f 20 64 61 74 61 20 written to data
0630: 61 72 65 61 2e 20 52 65 6c 61 74 69 76 65 20 74 area. Relative t
0640: 6f 20 66 69 72 73 74 20 62 79 74 65 20 6f 66 0a o first byte of.
0650: 2a 2a 20 20 20 73 74 72 75 63 74 75 72 65 2e 0a ** structure..
0660: 2a 2a 0a 2a 2a 20 6e 44 61 74 61 3a 0a 2a 2a 20 **.** nData:.**
0670: 20 20 42 79 74 65 73 20 6f 66 20 64 61 74 61 20 Bytes of data
0680: 77 72 69 74 74 65 6e 20 73 69 6e 63 65 20 69 52 written since iR
0690: 6f 77 69 64 4f 66 66 2e 0a 2a 2f 0a 73 74 72 75 owidOff..*/.stru
06a0: 63 74 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 ct Fts5HashEntry
06b0: 20 7b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 {. Fts5HashEnt
06c0: 72 79 20 2a 70 48 61 73 68 4e 65 78 74 3b 20 20 ry *pHashNext;
06d0: 20 20 20 20 20 2f 2a 20 4e 65 78 74 20 68 61 73 /* Next has
06e0: 68 20 65 6e 74 72 79 20 77 69 74 68 20 73 61 6d h entry with sam
06f0: 65 20 68 61 73 68 2d 6b 65 79 20 2a 2f 0a 20 20 e hash-key */.
0700: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 Fts5HashEntry *p
0710: 53 63 61 6e 4e 65 78 74 3b 20 20 20 20 20 20 20 ScanNext;
0720: 2f 2a 20 4e 65 78 74 20 65 6e 74 72 79 20 69 6e /* Next entry in
0730: 20 73 6f 72 74 65 64 20 6f 72 64 65 72 20 2a 2f sorted order */
0740: 0a 20 20 0a 20 20 69 6e 74 20 6e 41 6c 6c 6f 63 . . int nAlloc
0750: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ;
0760: 20 20 20 20 20 20 2f 2a 20 54 6f 74 61 6c 20 73 /* Total s
0770: 69 7a 65 20 6f 66 20 61 6c 6c 6f 63 61 74 69 6f ize of allocatio
0780: 6e 20 2a 2f 0a 20 20 69 6e 74 20 69 53 7a 50 6f n */. int iSzPo
0790: 73 6c 69 73 74 3b 20 20 20 20 20 20 20 20 20 20 slist;
07a0: 20 20 20 20 20 20 20 2f 2a 20 4f 66 66 73 65 74 /* Offset
07b0: 20 6f 66 20 73 70 61 63 65 20 66 6f 72 20 34 2d of space for 4-
07c0: 62 79 74 65 20 70 6f 73 6c 69 73 74 20 73 69 7a byte poslist siz
07d0: 65 20 2a 2f 0a 20 20 69 6e 74 20 6e 44 61 74 61 e */. int nData
07e0: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ;
07f0: 20 20 20 20 20 20 20 2f 2a 20 54 6f 74 61 6c 20 /* Total
0800: 62 79 74 65 73 20 6f 66 20 64 61 74 61 20 28 69 bytes of data (i
0810: 6e 63 6c 2e 20 73 74 72 75 63 74 75 72 65 29 20 ncl. structure)
0820: 2a 2f 0a 0a 20 20 69 6e 74 20 69 43 6f 6c 3b 20 */.. int iCol;
0830: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
0840: 20 20 20 20 20 20 2f 2a 20 43 6f 6c 75 6d 6e 20 /* Column
0850: 6f 66 20 6c 61 73 74 20 76 61 6c 75 65 20 77 72 of last value wr
0860: 69 74 74 65 6e 20 2a 2f 0a 20 20 69 6e 74 20 69 itten */. int i
0870: 50 6f 73 3b 20 20 20 20 20 20 20 20 20 20 20 20 Pos;
0880: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f /* Po
0890: 73 69 74 69 6f 6e 20 6f 66 20 6c 61 73 74 20 76 sition of last v
08a0: 61 6c 75 65 20 77 72 69 74 74 65 6e 20 2a 2f 0a alue written */.
08b0: 20 20 69 36 34 20 69 52 6f 77 69 64 3b 20 20 20 i64 iRowid;
08c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
08d0: 20 20 2f 2a 20 52 6f 77 69 64 20 6f 66 20 6c 61 /* Rowid of la
08e0: 73 74 20 76 61 6c 75 65 20 77 72 69 74 74 65 6e st value written
08f0: 20 2a 2f 0a 20 20 63 68 61 72 20 7a 4b 65 79 5b */. char zKey[
0900: 30 5d 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 0];
0910: 20 20 20 20 20 20 2f 2a 20 4e 75 6c 2d 74 65 72 /* Nul-ter
0920: 6d 69 6e 61 74 65 64 20 65 6e 74 72 79 20 6b 65 minated entry ke
0930: 79 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 46 y */.};../*.** F
0940: 6f 72 6d 61 74 20 76 61 6c 75 65 20 69 56 61 6c ormat value iVal
0950: 20 61 73 20 61 20 34 2d 62 79 74 65 20 76 61 72 as a 4-byte var
0960: 69 6e 74 20 61 6e 64 20 77 72 69 74 65 20 69 74 int and write it
0970: 20 74 6f 20 62 75 66 66 65 72 20 61 5b 5d 2e 20 to buffer a[].
0980: 34 20 62 79 74 65 73 0a 2a 2a 20 61 72 65 20 75 4 bytes.** are u
0990: 73 65 64 20 65 76 65 6e 20 69 66 20 74 68 65 20 sed even if the
09a0: 76 61 6c 75 65 20 63 6f 75 6c 64 20 66 69 74 20 value could fit
09b0: 69 6e 20 61 20 73 6d 61 6c 6c 65 72 20 61 6d 6f in a smaller amo
09c0: 75 6e 74 20 6f 66 20 73 70 61 63 65 2e 20 0a 2a unt of space. .*
09d0: 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 66 74 /.static void ft
09e0: 73 35 50 75 74 34 42 79 74 65 56 61 72 69 6e 74 s5Put4ByteVarint
09f0: 28 75 38 20 2a 61 2c 20 69 6e 74 20 69 56 61 6c (u8 *a, int iVal
0a00: 29 7b 0a 20 20 61 5b 30 5d 20 3d 20 28 30 78 38 ){. a[0] = (0x8
0a10: 30 20 7c 20 28 75 38 29 28 69 56 61 6c 20 3e 3e 0 | (u8)(iVal >>
0a20: 20 32 31 29 29 3b 0a 20 20 61 5b 31 5d 20 3d 20 21));. a[1] =
0a30: 28 30 78 38 30 20 7c 20 28 75 38 29 28 69 56 61 (0x80 | (u8)(iVa
0a40: 6c 20 3e 3e 20 31 34 29 29 3b 0a 20 20 61 5b 32 l >> 14));. a[2
0a50: 5d 20 3d 20 28 30 78 38 30 20 7c 20 28 75 38 29 ] = (0x80 | (u8)
0a60: 28 69 56 61 6c 20 3e 3e 20 20 37 29 29 3b 0a 20 (iVal >> 7));.
0a70: 20 61 5b 33 5d 20 3d 20 28 30 78 37 46 20 26 20 a[3] = (0x7F &
0a80: 28 75 38 29 28 69 56 61 6c 29 29 3b 0a 7d 0a 0a (u8)(iVal));.}..
0a90: 73 74 61 74 69 63 20 69 6e 74 20 66 74 73 35 47 static int fts5G
0aa0: 65 74 34 42 79 74 65 56 61 72 69 6e 74 28 75 38 et4ByteVarint(u8
0ab0: 20 2a 61 2c 20 69 6e 74 20 2a 70 6e 56 61 72 69 *a, int *pnVari
0ac0: 6e 74 29 7b 0a 20 20 69 6e 74 20 69 52 65 74 20 nt){. int iRet
0ad0: 3d 20 28 28 69 6e 74 29 28 61 5b 30 5d 20 26 20 = ((int)(a[0] &
0ae0: 30 78 37 46 29 20 3c 3c 20 32 31 29 20 2b 20 28 0x7F) << 21) + (
0af0: 28 69 6e 74 29 28 61 5b 31 5d 20 26 20 30 78 37 (int)(a[1] & 0x7
0b00: 46 29 20 3c 3c 20 31 34 29 0a 20 20 20 20 20 20 F) << 14).
0b10: 20 2b 20 28 28 69 6e 74 29 28 61 5b 32 5d 20 26 + ((int)(a[2] &
0b20: 20 30 78 37 46 29 20 3c 3c 20 20 37 29 20 2b 20 0x7F) << 7) +
0b30: 28 28 69 6e 74 29 28 61 5b 33 5d 29 29 3b 0a 20 ((int)(a[3]));.
0b40: 20 2a 70 6e 56 61 72 69 6e 74 20 3d 20 28 0a 20 *pnVarint = (.
0b50: 20 20 20 20 20 28 69 52 65 74 20 26 20 30 78 46 (iRet & 0xF
0b60: 46 46 46 46 46 38 30 29 3d 3d 30 20 3f 20 31 20 FFFFF80)==0 ? 1
0b70: 3a 20 0a 20 20 20 20 20 20 28 69 52 65 74 20 26 : . (iRet &
0b80: 20 30 78 46 46 46 46 43 30 30 30 29 3d 3d 30 20 0xFFFFC000)==0
0b90: 3f 20 32 20 3a 0a 20 20 20 20 20 20 28 69 52 65 ? 2 :. (iRe
0ba0: 74 20 26 20 30 78 46 46 45 30 30 30 30 30 29 3d t & 0xFFE00000)=
0bb0: 3d 30 20 3f 20 33 20 3a 20 34 0a 20 20 29 3b 0a =0 ? 3 : 4. );.
0bc0: 20 20 72 65 74 75 72 6e 20 69 52 65 74 3b 0a 7d return iRet;.}
0bd0: 0a 0a 2f 2a 0a 2a 2a 20 41 6c 6c 6f 63 61 74 65 ../*.** Allocate
0be0: 20 61 20 6e 65 77 20 68 61 73 68 20 74 61 62 6c a new hash tabl
0bf0: 65 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 e..*/.int sqlite
0c00: 33 46 74 73 35 48 61 73 68 4e 65 77 28 46 74 73 3Fts5HashNew(Fts
0c10: 35 48 61 73 68 20 2a 2a 70 70 4e 65 77 2c 20 69 5Hash **ppNew, i
0c20: 6e 74 20 2a 70 6e 42 79 74 65 29 7b 0a 20 20 69 nt *pnByte){. i
0c30: 6e 74 20 72 63 20 3d 20 53 51 4c 49 54 45 5f 4f nt rc = SQLITE_O
0c40: 4b 3b 0a 20 20 46 74 73 35 48 61 73 68 20 2a 70 K;. Fts5Hash *p
0c50: 4e 65 77 3b 0a 0a 20 20 2a 70 70 4e 65 77 20 3d New;.. *ppNew =
0c60: 20 70 4e 65 77 20 3d 20 28 46 74 73 35 48 61 73 pNew = (Fts5Has
0c70: 68 2a 29 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f h*)sqlite3_mallo
0c80: 63 28 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 c(sizeof(Fts5Has
0c90: 68 29 29 3b 0a 20 20 69 66 28 20 70 4e 65 77 3d h));. if( pNew=
0ca0: 3d 30 20 29 7b 0a 20 20 20 20 72 63 20 3d 20 53 =0 ){. rc = S
0cb0: 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 7d QLITE_NOMEM;. }
0cc0: 65 6c 73 65 7b 0a 20 20 20 20 69 6e 74 20 6e 42 else{. int nB
0cd0: 79 74 65 3b 0a 20 20 20 20 6d 65 6d 73 65 74 28 yte;. memset(
0ce0: 70 4e 65 77 2c 20 30 2c 20 73 69 7a 65 6f 66 28 pNew, 0, sizeof(
0cf0: 46 74 73 35 48 61 73 68 29 29 3b 0a 20 20 20 20 Fts5Hash));.
0d00: 70 4e 65 77 2d 3e 70 6e 42 79 74 65 20 3d 20 70 pNew->pnByte = p
0d10: 6e 42 79 74 65 3b 0a 0a 20 20 20 20 70 4e 65 77 nByte;.. pNew
0d20: 2d 3e 6e 53 6c 6f 74 20 3d 20 31 30 32 34 3b 0a ->nSlot = 1024;.
0d30: 20 20 20 20 6e 42 79 74 65 20 3d 20 73 69 7a 65 nByte = size
0d40: 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 of(Fts5HashEntry
0d50: 2a 29 20 2a 20 70 4e 65 77 2d 3e 6e 53 6c 6f 74 *) * pNew->nSlot
0d60: 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 61 53 6c 6f ;. pNew->aSlo
0d70: 74 20 3d 20 28 46 74 73 35 48 61 73 68 45 6e 74 t = (Fts5HashEnt
0d80: 72 79 2a 2a 29 73 71 6c 69 74 65 33 5f 6d 61 6c ry**)sqlite3_mal
0d90: 6c 6f 63 28 6e 42 79 74 65 29 3b 0a 20 20 20 20 loc(nByte);.
0da0: 69 66 28 20 70 4e 65 77 2d 3e 61 53 6c 6f 74 3d if( pNew->aSlot=
0db0: 3d 30 20 29 7b 0a 20 20 20 20 20 20 73 71 6c 69 =0 ){. sqli
0dc0: 74 65 33 5f 66 72 65 65 28 70 4e 65 77 29 3b 0a te3_free(pNew);.
0dd0: 20 20 20 20 20 20 2a 70 70 4e 65 77 20 3d 20 30 *ppNew = 0
0de0: 3b 0a 20 20 20 20 20 20 72 63 20 3d 20 53 51 4c ;. rc = SQL
0df0: 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 7d ITE_NOMEM;. }
0e00: 65 6c 73 65 7b 0a 20 20 20 20 20 20 6d 65 6d 73 else{. mems
0e10: 65 74 28 70 4e 65 77 2d 3e 61 53 6c 6f 74 2c 20 et(pNew->aSlot,
0e20: 30 2c 20 6e 42 79 74 65 29 3b 0a 20 20 20 20 7d 0, nByte);. }
0e30: 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 72 63 . }. return rc
0e40: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 46 72 65 65 20 ;.}../*.** Free
0e50: 61 20 68 61 73 68 20 74 61 62 6c 65 20 6f 62 6a a hash table obj
0e60: 65 63 74 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c ect..*/.void sql
0e70: 69 74 65 33 46 74 73 35 48 61 73 68 46 72 65 65 ite3Fts5HashFree
0e80: 28 46 74 73 35 48 61 73 68 20 2a 70 48 61 73 68 (Fts5Hash *pHash
0e90: 29 7b 0a 20 20 69 66 28 20 70 48 61 73 68 20 29 ){. if( pHash )
0ea0: 7b 0a 20 20 20 20 73 71 6c 69 74 65 33 46 74 73 {. sqlite3Fts
0eb0: 35 48 61 73 68 43 6c 65 61 72 28 70 48 61 73 68 5HashClear(pHash
0ec0: 29 3b 0a 20 20 20 20 73 71 6c 69 74 65 33 5f 66 );. sqlite3_f
0ed0: 72 65 65 28 70 48 61 73 68 2d 3e 61 53 6c 6f 74 ree(pHash->aSlot
0ee0: 29 3b 0a 20 20 20 20 73 71 6c 69 74 65 33 5f 66 );. sqlite3_f
0ef0: 72 65 65 28 70 48 61 73 68 29 3b 0a 20 20 7d 0a ree(pHash);. }.
0f00: 7d 0a 0a 2f 2a 0a 2a 2a 20 45 6d 70 74 79 20 28 }../*.** Empty (
0f10: 62 75 74 20 64 6f 20 6e 6f 74 20 64 65 6c 65 74 but do not delet
0f20: 65 29 20 61 20 68 61 73 68 20 74 61 62 6c 65 2e e) a hash table.
0f30: 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 .*/.void sqlite3
0f40: 46 74 73 35 48 61 73 68 43 6c 65 61 72 28 46 74 Fts5HashClear(Ft
0f50: 73 35 48 61 73 68 20 2a 70 48 61 73 68 29 7b 0a s5Hash *pHash){.
0f60: 20 20 69 6e 74 20 69 3b 0a 20 20 66 6f 72 28 69 int i;. for(i
0f70: 3d 30 3b 20 69 3c 70 48 61 73 68 2d 3e 6e 53 6c =0; i<pHash->nSl
0f80: 6f 74 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 46 74 ot; i++){. Ft
0f90: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 4e 65 s5HashEntry *pNe
0fa0: 78 74 3b 0a 20 20 20 20 46 74 73 35 48 61 73 68 xt;. Fts5Hash
0fb0: 45 6e 74 72 79 20 2a 70 53 6c 6f 74 3b 0a 20 20 Entry *pSlot;.
0fc0: 20 20 66 6f 72 28 70 53 6c 6f 74 3d 70 48 61 73 for(pSlot=pHas
0fd0: 68 2d 3e 61 53 6c 6f 74 5b 69 5d 3b 20 70 53 6c h->aSlot[i]; pSl
0fe0: 6f 74 3b 20 70 53 6c 6f 74 3d 70 4e 65 78 74 29 ot; pSlot=pNext)
0ff0: 7b 0a 20 20 20 20 20 20 70 4e 65 78 74 20 3d 20 {. pNext =
1000: 70 53 6c 6f 74 2d 3e 70 48 61 73 68 4e 65 78 74 pSlot->pHashNext
1010: 3b 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33 5f ;. sqlite3_
1020: 66 72 65 65 28 70 53 6c 6f 74 29 3b 0a 20 20 20 free(pSlot);.
1030: 20 7d 0a 20 20 7d 0a 20 20 6d 65 6d 73 65 74 28 }. }. memset(
1040: 70 48 61 73 68 2d 3e 61 53 6c 6f 74 2c 20 30 2c pHash->aSlot, 0,
1050: 20 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 20 2a 20 pHash->nSlot *
1060: 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 sizeof(Fts5HashE
1070: 6e 74 72 79 2a 29 29 3b 0a 20 20 70 48 61 73 68 ntry*));. pHash
1080: 2d 3e 6e 45 6e 74 72 79 20 3d 20 30 3b 0a 7d 0a ->nEntry = 0;.}.
1090: 0a 73 74 61 74 69 63 20 75 6e 73 69 67 6e 65 64 .static unsigned
10a0: 20 69 6e 74 20 66 74 73 35 48 61 73 68 4b 65 79 int fts5HashKey
10b0: 28 69 6e 74 20 6e 53 6c 6f 74 2c 20 63 6f 6e 73 (int nSlot, cons
10c0: 74 20 63 68 61 72 20 2a 70 2c 20 69 6e 74 20 6e t char *p, int n
10d0: 29 7b 0a 20 20 69 6e 74 20 69 3b 0a 20 20 75 6e ){. int i;. un
10e0: 73 69 67 6e 65 64 20 69 6e 74 20 68 20 3d 20 31 signed int h = 1
10f0: 33 3b 0a 20 20 66 6f 72 28 69 3d 6e 2d 31 3b 20 3;. for(i=n-1;
1100: 69 3e 3d 30 3b 20 69 2d 2d 29 7b 0a 20 20 20 20 i>=0; i--){.
1110: 68 20 3d 20 28 68 20 3c 3c 20 33 29 20 5e 20 68 h = (h << 3) ^ h
1120: 20 5e 20 70 5b 69 5d 3b 0a 20 20 7d 0a 20 20 72 ^ p[i];. }. r
1130: 65 74 75 72 6e 20 28 68 20 25 20 6e 53 6c 6f 74 eturn (h % nSlot
1140: 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 73 69 );.}../*.** Resi
1150: 7a 65 20 74 68 65 20 68 61 73 68 20 74 61 62 6c ze the hash tabl
1160: 65 20 62 79 20 64 6f 75 62 6c 69 6e 67 20 74 68 e by doubling th
1170: 65 20 6e 75 6d 62 65 72 20 6f 66 20 73 6c 6f 74 e number of slot
1180: 73 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 s..*/.static int
1190: 20 66 74 73 35 48 61 73 68 52 65 73 69 7a 65 28 fts5HashResize(
11a0: 46 74 73 35 48 61 73 68 20 2a 70 48 61 73 68 29 Fts5Hash *pHash)
11b0: 7b 0a 20 20 69 6e 74 20 6e 4e 65 77 20 3d 20 70 {. int nNew = p
11c0: 48 61 73 68 2d 3e 6e 53 6c 6f 74 2a 32 3b 0a 20 Hash->nSlot*2;.
11d0: 20 69 6e 74 20 69 3b 0a 20 20 46 74 73 35 48 61 int i;. Fts5Ha
11e0: 73 68 45 6e 74 72 79 20 2a 2a 61 70 4e 65 77 3b shEntry **apNew;
11f0: 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 . Fts5HashEntry
1200: 20 2a 2a 61 70 4f 6c 64 20 3d 20 70 48 61 73 68 **apOld = pHash
1210: 2d 3e 61 53 6c 6f 74 3b 0a 0a 20 20 61 70 4e 65 ->aSlot;.. apNe
1220: 77 20 3d 20 28 46 74 73 35 48 61 73 68 45 6e 74 w = (Fts5HashEnt
1230: 72 79 2a 2a 29 73 71 6c 69 74 65 33 5f 6d 61 6c ry**)sqlite3_mal
1240: 6c 6f 63 28 6e 4e 65 77 2a 73 69 7a 65 6f 66 28 loc(nNew*sizeof(
1250: 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a 29 29 Fts5HashEntry*))
1260: 3b 0a 20 20 69 66 28 20 21 61 70 4e 65 77 20 29 ;. if( !apNew )
1270: 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e return SQLITE_N
1280: 4f 4d 45 4d 3b 0a 20 20 6d 65 6d 73 65 74 28 61 OMEM;. memset(a
1290: 70 4e 65 77 2c 20 30 2c 20 6e 4e 65 77 2a 73 69 pNew, 0, nNew*si
12a0: 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 6e 74 zeof(Fts5HashEnt
12b0: 72 79 2a 29 29 3b 0a 0a 20 20 66 6f 72 28 69 3d ry*));.. for(i=
12c0: 30 3b 20 69 3c 70 48 61 73 68 2d 3e 6e 53 6c 6f 0; i<pHash->nSlo
12d0: 74 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 77 68 69 t; i++){. whi
12e0: 6c 65 28 20 61 70 4f 6c 64 5b 69 5d 20 29 7b 0a le( apOld[i] ){.
12f0: 20 20 20 20 20 20 69 6e 74 20 69 48 61 73 68 3b int iHash;
1300: 0a 20 20 20 20 20 20 46 74 73 35 48 61 73 68 45 . Fts5HashE
1310: 6e 74 72 79 20 2a 70 20 3d 20 61 70 4f 6c 64 5b ntry *p = apOld[
1320: 69 5d 3b 0a 20 20 20 20 20 20 61 70 4f 6c 64 5b i];. apOld[
1330: 69 5d 20 3d 20 70 2d 3e 70 48 61 73 68 4e 65 78 i] = p->pHashNex
1340: 74 3b 0a 20 20 20 20 20 20 69 48 61 73 68 20 3d t;. iHash =
1350: 20 66 74 73 35 48 61 73 68 4b 65 79 28 6e 4e 65 fts5HashKey(nNe
1360: 77 2c 20 70 2d 3e 7a 4b 65 79 2c 20 73 74 72 6c w, p->zKey, strl
1370: 65 6e 28 70 2d 3e 7a 4b 65 79 29 29 3b 0a 20 20 en(p->zKey));.
1380: 20 20 20 20 70 2d 3e 70 48 61 73 68 4e 65 78 74 p->pHashNext
1390: 20 3d 20 61 70 4e 65 77 5b 69 48 61 73 68 5d 3b = apNew[iHash];
13a0: 0a 20 20 20 20 20 20 61 70 4e 65 77 5b 69 48 61 . apNew[iHa
13b0: 73 68 5d 20 3d 20 70 3b 0a 20 20 20 20 7d 0a 20 sh] = p;. }.
13c0: 20 7d 0a 0a 20 20 73 71 6c 69 74 65 33 5f 66 72 }.. sqlite3_fr
13d0: 65 65 28 61 70 4f 6c 64 29 3b 0a 20 20 70 48 61 ee(apOld);. pHa
13e0: 73 68 2d 3e 6e 53 6c 6f 74 20 3d 20 6e 4e 65 77 sh->nSlot = nNew
13f0: 3b 0a 20 20 70 48 61 73 68 2d 3e 61 53 6c 6f 74 ;. pHash->aSlot
1400: 20 3d 20 61 70 4e 65 77 3b 0a 20 20 72 65 74 75 = apNew;. retu
1410: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a rn SQLITE_OK;.}.
1420: 0a 73 74 61 74 69 63 20 76 6f 69 64 20 66 74 73 .static void fts
1430: 35 48 61 73 68 41 64 64 50 6f 73 6c 69 73 74 53 5HashAddPoslistS
1440: 69 7a 65 28 46 74 73 35 48 61 73 68 45 6e 74 72 ize(Fts5HashEntr
1450: 79 20 2a 70 29 7b 0a 20 20 69 66 28 20 70 2d 3e y *p){. if( p->
1460: 69 53 7a 50 6f 73 6c 69 73 74 20 29 7b 0a 20 20 iSzPoslist ){.
1470: 20 20 75 38 20 2a 70 50 74 72 20 3d 20 28 75 38 u8 *pPtr = (u8
1480: 2a 29 70 3b 0a 20 20 20 20 69 6e 74 20 6e 53 7a *)p;. int nSz
1490: 20 3d 20 70 2d 3e 6e 44 61 74 61 20 2d 20 70 2d = p->nData - p-
14a0: 3e 69 53 7a 50 6f 73 6c 69 73 74 20 2d 20 31 3b >iSzPoslist - 1;
14b0: 0a 0a 20 20 20 20 69 66 28 20 6e 53 7a 3c 3d 31 .. if( nSz<=1
14c0: 32 37 20 29 7b 0a 20 20 20 20 20 20 70 50 74 72 27 ){. pPtr
14d0: 5b 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 5d 20 [p->iSzPoslist]
14e0: 3d 20 6e 53 7a 3b 0a 20 20 20 20 7d 65 6c 73 65 = nSz;. }else
14f0: 7b 0a 20 20 20 20 20 20 69 6e 74 20 6e 42 79 74 {. int nByt
1500: 65 20 3d 20 73 71 6c 69 74 65 33 46 74 73 35 47 e = sqlite3Fts5G
1510: 65 74 56 61 72 69 6e 74 4c 65 6e 28 28 75 33 32 etVarintLen((u32
1520: 29 6e 53 7a 29 3b 0a 20 20 20 20 20 20 6d 65 6d )nSz);. mem
1530: 6d 6f 76 65 28 26 70 50 74 72 5b 70 2d 3e 69 53 move(&pPtr[p->iS
1540: 7a 50 6f 73 6c 69 73 74 20 2b 20 6e 42 79 74 65 zPoslist + nByte
1550: 5d 2c 20 26 70 50 74 72 5b 70 2d 3e 69 53 7a 50 ], &pPtr[p->iSzP
1560: 6f 73 6c 69 73 74 20 2b 20 31 5d 2c 20 6e 53 7a oslist + 1], nSz
1570: 29 3b 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33 );. sqlite3
1580: 50 75 74 56 61 72 69 6e 74 28 26 70 50 74 72 5b PutVarint(&pPtr[
1590: 70 2d 3e 69 53 7a 50 6f 73 6c 69 73 74 5d 2c 20 p->iSzPoslist],
15a0: 6e 53 7a 29 3b 0a 20 20 20 20 20 20 70 2d 3e 6e nSz);. p->n
15b0: 44 61 74 61 20 2b 3d 20 28 6e 42 79 74 65 2d 31 Data += (nByte-1
15c0: 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 70 2d 3e );. }. p->
15d0: 69 53 7a 50 6f 73 6c 69 73 74 20 3d 20 30 3b 0a iSzPoslist = 0;.
15e0: 20 20 7d 0a 7d 0a 0a 69 6e 74 20 73 71 6c 69 74 }.}..int sqlit
15f0: 65 33 46 74 73 35 48 61 73 68 57 72 69 74 65 28 e3Fts5HashWrite(
1600: 0a 20 20 46 74 73 35 48 61 73 68 20 2a 70 48 61 . Fts5Hash *pHa
1610: 73 68 2c 0a 20 20 69 36 34 20 69 52 6f 77 69 64 sh,. i64 iRowid
1620: 2c 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ,
1630: 20 20 20 20 20 20 2f 2a 20 52 6f 77 69 64 20 66 /* Rowid f
1640: 6f 72 20 74 68 69 73 20 65 6e 74 72 79 20 2a 2f or this entry */
1650: 0a 20 20 69 6e 74 20 69 43 6f 6c 2c 20 20 20 20 . int iCol,
1660: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1670: 20 20 20 2f 2a 20 43 6f 6c 75 6d 6e 20 74 6f 6b /* Column tok
1680: 65 6e 20 61 70 70 65 61 72 73 20 69 6e 20 28 2d en appears in (-
1690: 76 65 20 2d 3e 20 64 65 6c 65 74 65 29 20 2a 2f ve -> delete) */
16a0: 0a 20 20 69 6e 74 20 69 50 6f 73 2c 20 20 20 20 . int iPos,
16b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
16c0: 20 20 20 2f 2a 20 50 6f 73 69 74 69 6f 6e 20 6f /* Position o
16d0: 66 20 74 6f 6b 65 6e 20 77 69 74 68 69 6e 20 63 f token within c
16e0: 6f 6c 75 6d 6e 20 2a 2f 0a 20 20 63 6f 6e 73 74 olumn */. const
16f0: 20 63 68 61 72 20 2a 70 54 6f 6b 65 6e 2c 20 69 char *pToken, i
1700: 6e 74 20 6e 54 6f 6b 65 6e 20 20 2f 2a 20 54 6f nt nToken /* To
1710: 6b 65 6e 20 74 6f 20 61 64 64 20 6f 72 20 72 65 ken to add or re
1720: 6d 6f 76 65 20 74 6f 20 6f 72 20 66 72 6f 6d 20 move to or from
1730: 69 6e 64 65 78 20 2a 2f 0a 29 7b 0a 20 20 75 6e index */.){. un
1740: 73 69 67 6e 65 64 20 69 6e 74 20 69 48 61 73 68 signed int iHash
1750: 20 3d 20 66 74 73 35 48 61 73 68 4b 65 79 28 70 = fts5HashKey(p
1760: 48 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20 70 54 6f Hash->nSlot, pTo
1770: 6b 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 ken, nToken);.
1780: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 Fts5HashEntry *p
1790: 3b 0a 20 20 75 38 20 2a 70 50 74 72 3b 0a 20 20 ;. u8 *pPtr;.
17a0: 69 6e 74 20 6e 49 6e 63 72 20 3d 20 30 3b 20 20 int nIncr = 0;
17b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
17c0: 2f 2a 20 41 6d 6f 75 6e 74 20 74 6f 20 69 6e 63 /* Amount to inc
17d0: 72 65 6d 65 6e 74 20 28 2a 70 48 61 73 68 2d 3e rement (*pHash->
17e0: 70 6e 42 79 74 65 29 20 62 79 20 2a 2f 0a 0a 20 pnByte) by */..
17f0: 20 2f 2a 20 41 74 74 65 6d 70 74 20 74 6f 20 6c /* Attempt to l
1800: 6f 63 61 74 65 20 61 6e 20 65 78 69 73 74 69 6e ocate an existin
1810: 67 20 68 61 73 68 20 65 6e 74 72 79 20 2a 2f 0a g hash entry */.
1820: 20 20 66 6f 72 28 70 3d 70 48 61 73 68 2d 3e 61 for(p=pHash->a
1830: 53 6c 6f 74 5b 69 48 61 73 68 5d 3b 20 70 3b 20 Slot[iHash]; p;
1840: 70 3d 70 2d 3e 70 48 61 73 68 4e 65 78 74 29 7b p=p->pHashNext){
1850: 0a 20 20 20 20 69 66 28 20 6d 65 6d 63 6d 70 28 . if( memcmp(
1860: 70 2d 3e 7a 4b 65 79 2c 20 70 54 6f 6b 65 6e 2c p->zKey, pToken,
1870: 20 6e 54 6f 6b 65 6e 29 3d 3d 30 20 26 26 20 70 nToken)==0 && p
1880: 2d 3e 7a 4b 65 79 5b 6e 54 6f 6b 65 6e 5d 3d 3d ->zKey[nToken]==
1890: 30 20 29 20 62 72 65 61 6b 3b 0a 20 20 7d 0a 0a 0 ) break;. }..
18a0: 20 20 2f 2a 20 49 66 20 61 6e 20 65 78 69 73 74 /* If an exist
18b0: 69 6e 67 20 68 61 73 68 20 65 6e 74 72 79 20 63 ing hash entry c
18c0: 61 6e 6e 6f 74 20 62 65 20 66 6f 75 6e 64 2c 20 annot be found,
18d0: 63 72 65 61 74 65 20 61 20 6e 65 77 20 6f 6e 65 create a new one
18e0: 2e 20 2a 2f 0a 20 20 69 66 28 20 70 3d 3d 30 20 . */. if( p==0
18f0: 29 7b 0a 20 20 20 20 69 6e 74 20 6e 42 79 74 65 ){. int nByte
1900: 20 3d 20 73 69 7a 65 6f 66 28 46 74 73 35 48 61 = sizeof(Fts5Ha
1910: 73 68 45 6e 74 72 79 29 20 2b 20 6e 54 6f 6b 65 shEntry) + nToke
1920: 6e 20 2b 20 31 20 2b 20 36 34 3b 0a 20 20 20 20 n + 1 + 64;.
1930: 69 66 28 20 6e 42 79 74 65 3c 31 32 38 20 29 20 if( nByte<128 )
1940: 6e 42 79 74 65 20 3d 20 31 32 38 3b 0a 0a 20 20 nByte = 128;..
1950: 20 20 69 66 28 20 28 70 48 61 73 68 2d 3e 6e 45 if( (pHash->nE
1960: 6e 74 72 79 2a 32 29 3e 3d 70 48 61 73 68 2d 3e ntry*2)>=pHash->
1970: 6e 53 6c 6f 74 20 29 7b 0a 20 20 20 20 20 20 69 nSlot ){. i
1980: 6e 74 20 72 63 20 3d 20 66 74 73 35 48 61 73 68 nt rc = fts5Hash
1990: 52 65 73 69 7a 65 28 70 48 61 73 68 29 3b 0a 20 Resize(pHash);.
19a0: 20 20 20 20 20 69 66 28 20 72 63 21 3d 53 51 4c if( rc!=SQL
19b0: 49 54 45 5f 4f 4b 20 29 20 72 65 74 75 72 6e 20 ITE_OK ) return
19c0: 72 63 3b 0a 20 20 20 20 20 20 69 48 61 73 68 20 rc;. iHash
19d0: 3d 20 66 74 73 35 48 61 73 68 4b 65 79 28 70 48 = fts5HashKey(pH
19e0: 61 73 68 2d 3e 6e 53 6c 6f 74 2c 20 70 54 6f 6b ash->nSlot, pTok
19f0: 65 6e 2c 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 20 en, nToken);.
1a00: 20 7d 0a 0a 20 20 20 20 70 20 3d 20 28 46 74 73 }.. p = (Fts
1a10: 35 48 61 73 68 45 6e 74 72 79 2a 29 73 71 6c 69 5HashEntry*)sqli
1a20: 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e 42 79 74 65 te3_malloc(nByte
1a30: 29 3b 0a 20 20 20 20 69 66 28 20 21 70 20 29 20 );. if( !p )
1a40: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f return SQLITE_NO
1a50: 4d 45 4d 3b 0a 20 20 20 20 6d 65 6d 73 65 74 28 MEM;. memset(
1a60: 70 2c 20 30 2c 20 73 69 7a 65 6f 66 28 46 74 73 p, 0, sizeof(Fts
1a70: 35 48 61 73 68 45 6e 74 72 79 29 29 3b 0a 20 20 5HashEntry));.
1a80: 20 20 70 2d 3e 6e 41 6c 6c 6f 63 20 3d 20 6e 42 p->nAlloc = nB
1a90: 79 74 65 3b 0a 20 20 20 20 6d 65 6d 63 70 79 28 yte;. memcpy(
1aa0: 70 2d 3e 7a 4b 65 79 2c 20 70 54 6f 6b 65 6e 2c p->zKey, pToken,
1ab0: 20 6e 54 6f 6b 65 6e 29 3b 0a 20 20 20 20 70 2d nToken);. p-
1ac0: 3e 7a 4b 65 79 5b 6e 54 6f 6b 65 6e 5d 20 3d 20 >zKey[nToken] =
1ad0: 27 5c 30 27 3b 0a 20 20 20 20 70 2d 3e 6e 44 61 '\0';. p->nDa
1ae0: 74 61 20 3d 20 6e 54 6f 6b 65 6e 20 2b 20 31 20 ta = nToken + 1
1af0: 2b 20 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 + sizeof(Fts5Has
1b00: 68 45 6e 74 72 79 29 3b 0a 20 20 20 20 70 2d 3e hEntry);. p->
1b10: 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69 74 65 33 nData += sqlite3
1b20: 50 75 74 56 61 72 69 6e 74 28 26 28 28 75 38 2a PutVarint(&((u8*
1b30: 29 70 29 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20 69 )p)[p->nData], i
1b40: 52 6f 77 69 64 29 3b 0a 20 20 20 20 70 2d 3e 69 Rowid);. p->i
1b50: 53 7a 50 6f 73 6c 69 73 74 20 3d 20 70 2d 3e 6e SzPoslist = p->n
1b60: 44 61 74 61 3b 0a 20 20 20 20 70 2d 3e 6e 44 61 Data;. p->nDa
1b70: 74 61 20 2b 3d 20 31 3b 0a 20 20 20 20 70 2d 3e ta += 1;. p->
1b80: 69 52 6f 77 69 64 20 3d 20 69 52 6f 77 69 64 3b iRowid = iRowid;
1b90: 0a 20 20 20 20 70 2d 3e 70 48 61 73 68 4e 65 78 . p->pHashNex
1ba0: 74 20 3d 20 70 48 61 73 68 2d 3e 61 53 6c 6f 74 t = pHash->aSlot
1bb0: 5b 69 48 61 73 68 5d 3b 0a 20 20 20 20 70 48 61 [iHash];. pHa
1bc0: 73 68 2d 3e 61 53 6c 6f 74 5b 69 48 61 73 68 5d sh->aSlot[iHash]
1bd0: 20 3d 20 70 3b 0a 20 20 20 20 70 48 61 73 68 2d = p;. pHash-
1be0: 3e 6e 45 6e 74 72 79 2b 2b 3b 0a 20 20 20 20 6e >nEntry++;. n
1bf0: 49 6e 63 72 20 2b 3d 20 70 2d 3e 6e 44 61 74 61 Incr += p->nData
1c00: 3b 0a 20 20 7d 0a 0a 20 20 2f 2a 20 43 68 65 63 ;. }.. /* Chec
1c10: 6b 20 74 68 65 72 65 20 69 73 20 65 6e 6f 75 67 k there is enoug
1c20: 68 20 73 70 61 63 65 20 74 6f 20 61 70 70 65 6e h space to appen
1c30: 64 20 61 20 6e 65 77 20 65 6e 74 72 79 2e 20 57 d a new entry. W
1c40: 6f 72 73 74 20 63 61 73 65 20 73 63 65 6e 61 72 orst case scenar
1c50: 69 6f 0a 20 20 2a 2a 20 69 73 3a 0a 20 20 2a 2a io. ** is:. **
1c60: 0a 20 20 2a 2a 20 20 20 20 20 2b 20 39 20 62 79 . ** + 9 by
1c70: 74 65 73 20 66 6f 72 20 61 20 6e 65 77 20 72 6f tes for a new ro
1c80: 77 69 64 2c 0a 20 20 2a 2a 20 20 20 20 20 2b 20 wid,. ** +
1c90: 34 20 62 79 74 65 20 72 65 73 65 72 76 65 64 20 4 byte reserved
1ca0: 66 6f 72 20 74 68 65 20 22 70 6f 73 6c 69 73 74 for the "poslist
1cb0: 20 73 69 7a 65 22 20 76 61 72 69 6e 74 2e 0a 20 size" varint..
1cc0: 20 2a 2a 20 20 20 20 20 2b 20 31 20 62 79 74 65 ** + 1 byte
1cd0: 20 66 6f 72 20 61 20 22 6e 65 77 20 63 6f 6c 75 for a "new colu
1ce0: 6d 6e 22 20 62 79 74 65 2c 0a 20 20 2a 2a 20 20 mn" byte,. **
1cf0: 20 20 20 2b 20 33 20 62 79 74 65 73 20 66 6f 72 + 3 bytes for
1d00: 20 61 20 6e 65 77 20 63 6f 6c 75 6d 6e 20 6e 75 a new column nu
1d10: 6d 62 65 72 20 28 31 36 2d 62 69 74 20 6d 61 78 mber (16-bit max
1d20: 29 20 61 73 20 61 20 76 61 72 69 6e 74 2c 0a 20 ) as a varint,.
1d30: 20 2a 2a 20 20 20 20 20 2b 20 35 20 62 79 74 65 ** + 5 byte
1d40: 73 20 66 6f 72 20 74 68 65 20 6e 65 77 20 70 6f s for the new po
1d50: 73 69 74 69 6f 6e 20 6f 66 66 73 65 74 20 28 33 sition offset (3
1d60: 32 2d 62 69 74 20 6d 61 78 29 2e 0a 20 20 2a 2f 2-bit max).. */
1d70: 0a 20 20 69 66 28 20 28 70 2d 3e 6e 41 6c 6c 6f . if( (p->nAllo
1d80: 63 20 2d 20 70 2d 3e 6e 44 61 74 61 29 20 3c 20 c - p->nData) <
1d90: 28 39 20 2b 20 34 20 2b 20 31 20 2b 20 33 20 2b (9 + 4 + 1 + 3 +
1da0: 20 35 29 20 29 7b 0a 20 20 20 20 69 6e 74 20 6e 5) ){. int n
1db0: 4e 65 77 20 3d 20 70 2d 3e 6e 41 6c 6c 6f 63 20 New = p->nAlloc
1dc0: 2a 20 32 3b 0a 20 20 20 20 46 74 73 35 48 61 73 * 2;. Fts5Has
1dd0: 68 45 6e 74 72 79 20 2a 70 4e 65 77 3b 0a 20 20 hEntry *pNew;.
1de0: 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 Fts5HashEntry
1df0: 2a 2a 70 70 3b 0a 20 20 20 20 70 4e 65 77 20 3d **pp;. pNew =
1e00: 20 28 46 74 73 35 48 61 73 68 45 6e 74 72 79 2a (Fts5HashEntry*
1e10: 29 73 71 6c 69 74 65 33 5f 72 65 61 6c 6c 6f 63 )sqlite3_realloc
1e20: 28 70 2c 20 6e 4e 65 77 29 3b 0a 20 20 20 20 69 (p, nNew);. i
1e30: 66 28 20 70 4e 65 77 3d 3d 30 20 29 20 72 65 74 f( pNew==0 ) ret
1e40: 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d urn SQLITE_NOMEM
1e50: 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 41 6c 6c ;. pNew->nAll
1e60: 6f 63 20 3d 20 6e 4e 65 77 3b 0a 20 20 20 20 66 oc = nNew;. f
1e70: 6f 72 28 70 70 3d 26 70 48 61 73 68 2d 3e 61 53 or(pp=&pHash->aS
1e80: 6c 6f 74 5b 69 48 61 73 68 5d 3b 20 2a 70 70 21 lot[iHash]; *pp!
1e90: 3d 70 3b 20 70 70 3d 26 28 2a 70 70 29 2d 3e 70 =p; pp=&(*pp)->p
1ea0: 48 61 73 68 4e 65 78 74 29 3b 0a 20 20 20 20 2a HashNext);. *
1eb0: 70 70 20 3d 20 70 4e 65 77 3b 0a 20 20 20 20 70 pp = pNew;. p
1ec0: 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 0a 20 20 70 = pNew;. }. p
1ed0: 50 74 72 20 3d 20 28 75 38 2a 29 70 3b 0a 20 20 Ptr = (u8*)p;.
1ee0: 6e 49 6e 63 72 20 2d 3d 20 70 2d 3e 6e 44 61 74 nIncr -= p->nDat
1ef0: 61 3b 0a 0a 20 20 2f 2a 20 49 66 20 74 68 69 73 a;.. /* If this
1f00: 20 69 73 20 61 20 6e 65 77 20 72 6f 77 69 64 2c is a new rowid,
1f10: 20 61 70 70 65 6e 64 20 74 68 65 20 34 2d 62 79 append the 4-by
1f20: 74 65 20 73 69 7a 65 20 66 69 65 6c 64 20 66 6f te size field fo
1f30: 72 20 74 68 65 20 70 72 65 76 69 6f 75 73 0a 20 r the previous.
1f40: 20 2a 2a 20 65 6e 74 72 79 2c 20 61 6e 64 20 74 ** entry, and t
1f50: 68 65 20 6e 65 77 20 72 6f 77 69 64 20 66 6f 72 he new rowid for
1f60: 20 74 68 69 73 20 65 6e 74 72 79 2e 20 20 2a 2f this entry. */
1f70: 0a 20 20 69 66 28 20 69 52 6f 77 69 64 21 3d 70 . if( iRowid!=p
1f80: 2d 3e 69 52 6f 77 69 64 20 29 7b 0a 20 20 20 20 ->iRowid ){.
1f90: 66 74 73 35 48 61 73 68 41 64 64 50 6f 73 6c 69 fts5HashAddPosli
1fa0: 73 74 53 69 7a 65 28 70 29 3b 0a 20 20 20 20 70 stSize(p);. p
1fb0: 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69 74 ->nData += sqlit
1fc0: 65 33 50 75 74 56 61 72 69 6e 74 28 26 70 50 74 e3PutVarint(&pPt
1fd0: 72 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20 69 52 6f r[p->nData], iRo
1fe0: 77 69 64 20 2d 20 70 2d 3e 69 52 6f 77 69 64 29 wid - p->iRowid)
1ff0: 3b 0a 20 20 20 20 70 2d 3e 69 53 7a 50 6f 73 6c ;. p->iSzPosl
2000: 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74 61 3b 0a ist = p->nData;.
2010: 20 20 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 p->nData +=
2020: 31 3b 0a 20 20 20 20 70 2d 3e 69 43 6f 6c 20 3d 1;. p->iCol =
2030: 20 30 3b 0a 20 20 20 20 70 2d 3e 69 50 6f 73 20 0;. p->iPos
2040: 3d 20 30 3b 0a 20 20 20 20 70 2d 3e 69 52 6f 77 = 0;. p->iRow
2050: 69 64 20 3d 20 69 52 6f 77 69 64 3b 0a 20 20 7d id = iRowid;. }
2060: 0a 0a 20 20 69 66 28 20 69 43 6f 6c 3e 3d 30 20 .. if( iCol>=0
2070: 29 7b 0a 20 20 20 20 2f 2a 20 41 70 70 65 6e 64 ){. /* Append
2080: 20 61 20 6e 65 77 20 63 6f 6c 75 6d 6e 20 76 61 a new column va
2090: 6c 75 65 2c 20 69 66 20 6e 65 63 65 73 73 61 72 lue, if necessar
20a0: 79 20 2a 2f 0a 20 20 20 20 61 73 73 65 72 74 28 y */. assert(
20b0: 20 69 43 6f 6c 3e 3d 70 2d 3e 69 43 6f 6c 20 29 iCol>=p->iCol )
20c0: 3b 0a 20 20 20 20 69 66 28 20 69 43 6f 6c 21 3d ;. if( iCol!=
20d0: 70 2d 3e 69 43 6f 6c 20 29 7b 0a 20 20 20 20 20 p->iCol ){.
20e0: 20 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61 2b 2b pPtr[p->nData++
20f0: 5d 20 3d 20 30 78 30 31 3b 0a 20 20 20 20 20 20 ] = 0x01;.
2100: 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71 6c 69 p->nData += sqli
2110: 74 65 33 50 75 74 56 61 72 69 6e 74 28 26 70 50 te3PutVarint(&pP
2120: 74 72 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20 69 43 tr[p->nData], iC
2130: 6f 6c 29 3b 0a 20 20 20 20 20 20 70 2d 3e 69 43 ol);. p->iC
2140: 6f 6c 20 3d 20 69 43 6f 6c 3b 0a 20 20 20 20 20 ol = iCol;.
2150: 20 70 2d 3e 69 50 6f 73 20 3d 20 30 3b 0a 20 20 p->iPos = 0;.
2160: 20 20 7d 0a 0a 20 20 20 20 2f 2a 20 41 70 70 65 }.. /* Appe
2170: 6e 64 20 74 68 65 20 6e 65 77 20 70 6f 73 69 74 nd the new posit
2180: 69 6f 6e 20 6f 66 66 73 65 74 20 2a 2f 0a 20 20 ion offset */.
2190: 20 20 70 2d 3e 6e 44 61 74 61 20 2b 3d 20 73 71 p->nData += sq
21a0: 6c 69 74 65 33 50 75 74 56 61 72 69 6e 74 28 26 lite3PutVarint(&
21b0: 70 50 74 72 5b 70 2d 3e 6e 44 61 74 61 5d 2c 20 pPtr[p->nData],
21c0: 69 50 6f 73 20 2d 20 70 2d 3e 69 50 6f 73 20 2b iPos - p->iPos +
21d0: 20 32 29 3b 0a 20 20 20 20 70 2d 3e 69 50 6f 73 2);. p->iPos
21e0: 20 3d 20 69 50 6f 73 3b 0a 20 20 7d 0a 20 20 6e = iPos;. }. n
21f0: 49 6e 63 72 20 2b 3d 20 70 2d 3e 6e 44 61 74 61 Incr += p->nData
2200: 3b 0a 0a 20 20 2a 70 48 61 73 68 2d 3e 70 6e 42 ;.. *pHash->pnB
2210: 79 74 65 20 2b 3d 20 6e 49 6e 63 72 3b 0a 20 20 yte += nIncr;.
2220: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b return SQLITE_OK
2230: 3b 0a 7d 0a 0a 0a 2f 2a 0a 2a 2a 20 41 72 67 75 ;.}.../*.** Argu
2240: 6d 65 6e 74 73 20 70 4c 65 66 74 20 61 6e 64 20 ments pLeft and
2250: 70 52 69 67 68 74 20 70 6f 69 6e 74 20 74 6f 20 pRight point to
2260: 6c 69 6e 6b 65 64 2d 6c 69 73 74 73 20 6f 66 20 linked-lists of
2270: 68 61 73 68 2d 65 6e 74 72 79 20 6f 62 6a 65 63 hash-entry objec
2280: 74 73 2c 0a 2a 2a 20 65 61 63 68 20 73 6f 72 74 ts,.** each sort
2290: 65 64 20 69 6e 20 6b 65 79 20 6f 72 64 65 72 2e ed in key order.
22a0: 20 54 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 6d This function m
22b0: 65 72 67 65 73 20 74 68 65 20 74 77 6f 20 6c 69 erges the two li
22c0: 73 74 73 20 69 6e 74 6f 20 61 0a 2a 2a 20 73 69 sts into a.** si
22d0: 6e 67 6c 65 20 6c 69 73 74 20 61 6e 64 20 72 65 ngle list and re
22e0: 74 75 72 6e 73 20 61 20 70 6f 69 6e 74 65 72 20 turns a pointer
22f0: 74 6f 20 69 74 73 20 66 69 72 73 74 20 65 6c 65 to its first ele
2300: 6d 65 6e 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 ment..*/.static
2310: 46 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 66 Fts5HashEntry *f
2320: 74 73 35 48 61 73 68 45 6e 74 72 79 4d 65 72 67 ts5HashEntryMerg
2330: 65 28 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 e(. Fts5HashEnt
2340: 72 79 20 2a 70 4c 65 66 74 2c 0a 20 20 46 74 73 ry *pLeft,. Fts
2350: 35 48 61 73 68 45 6e 74 72 79 20 2a 70 52 69 67 5HashEntry *pRig
2360: 68 74 0a 29 7b 0a 20 20 46 74 73 35 48 61 73 68 ht.){. Fts5Hash
2370: 45 6e 74 72 79 20 2a 70 31 20 3d 20 70 4c 65 66 Entry *p1 = pLef
2380: 74 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 t;. Fts5HashEnt
2390: 72 79 20 2a 70 32 20 3d 20 70 52 69 67 68 74 3b ry *p2 = pRight;
23a0: 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 79 . Fts5HashEntry
23b0: 20 2a 70 52 65 74 20 3d 20 30 3b 0a 20 20 46 74 *pRet = 0;. Ft
23c0: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 2a 70 70 s5HashEntry **pp
23d0: 4f 75 74 20 3d 20 26 70 52 65 74 3b 0a 0a 20 20 Out = &pRet;..
23e0: 77 68 69 6c 65 28 20 70 31 20 7c 7c 20 70 32 20 while( p1 || p2
23f0: 29 7b 0a 20 20 20 20 69 66 28 20 70 31 3d 3d 30 ){. if( p1==0
2400: 20 29 7b 0a 20 20 20 20 20 20 2a 70 70 4f 75 74 ){. *ppOut
2410: 20 3d 20 70 32 3b 0a 20 20 20 20 20 20 70 32 20 = p2;. p2
2420: 3d 20 30 3b 0a 20 20 20 20 7d 65 6c 73 65 20 69 = 0;. }else i
2430: 66 28 20 70 32 3d 3d 30 20 29 7b 0a 20 20 20 20 f( p2==0 ){.
2440: 20 20 2a 70 70 4f 75 74 20 3d 20 70 31 3b 0a 20 *ppOut = p1;.
2450: 20 20 20 20 20 70 31 20 3d 20 30 3b 0a 20 20 20 p1 = 0;.
2460: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 69 6e }else{. in
2470: 74 20 69 20 3d 20 30 3b 0a 20 20 20 20 20 20 77 t i = 0;. w
2480: 68 69 6c 65 28 20 70 31 2d 3e 7a 4b 65 79 5b 69 hile( p1->zKey[i
2490: 5d 3d 3d 70 32 2d 3e 7a 4b 65 79 5b 69 5d 20 29 ]==p2->zKey[i] )
24a0: 20 69 2b 2b 3b 0a 0a 20 20 20 20 20 20 69 66 28 i++;.. if(
24b0: 20 28 28 75 38 29 70 31 2d 3e 7a 4b 65 79 5b 69 ((u8)p1->zKey[i
24c0: 5d 29 3e 28 28 75 38 29 70 32 2d 3e 7a 4b 65 79 ])>((u8)p2->zKey
24d0: 5b 69 5d 29 20 29 7b 0a 20 20 20 20 20 20 20 20 [i]) ){.
24e0: 2f 2a 20 70 32 20 69 73 20 73 6d 61 6c 6c 65 72 /* p2 is smaller
24f0: 20 2a 2f 0a 20 20 20 20 20 20 20 20 2a 70 70 4f */. *ppO
2500: 75 74 20 3d 20 70 32 3b 0a 20 20 20 20 20 20 20 ut = p2;.
2510: 20 70 70 4f 75 74 20 3d 20 26 70 32 2d 3e 70 53 ppOut = &p2->pS
2520: 63 61 6e 4e 65 78 74 3b 0a 20 20 20 20 20 20 20 canNext;.
2530: 20 70 32 20 3d 20 70 32 2d 3e 70 53 63 61 6e 4e p2 = p2->pScanN
2540: 65 78 74 3b 0a 20 20 20 20 20 20 7d 65 6c 73 65 ext;. }else
2550: 7b 0a 20 20 20 20 20 20 20 20 2f 2a 20 70 31 20 {. /* p1
2560: 69 73 20 73 6d 61 6c 6c 65 72 20 2a 2f 0a 20 20 is smaller */.
2570: 20 20 20 20 20 20 2a 70 70 4f 75 74 20 3d 20 70 *ppOut = p
2580: 31 3b 0a 20 20 20 20 20 20 20 20 70 70 4f 75 74 1;. ppOut
2590: 20 3d 20 26 70 31 2d 3e 70 53 63 61 6e 4e 65 78 = &p1->pScanNex
25a0: 74 3b 0a 20 20 20 20 20 20 20 20 70 31 20 3d 20 t;. p1 =
25b0: 70 31 2d 3e 70 53 63 61 6e 4e 65 78 74 3b 0a 20 p1->pScanNext;.
25c0: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 2a 70 70 }. *pp
25d0: 4f 75 74 20 3d 20 30 3b 0a 20 20 20 20 7d 0a 20 Out = 0;. }.
25e0: 20 7d 0a 0a 20 20 72 65 74 75 72 6e 20 70 52 65 }.. return pRe
25f0: 74 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 45 78 74 72 t;.}../*.** Extr
2600: 61 63 74 20 61 6c 6c 20 74 6f 6b 65 6e 73 20 66 act all tokens f
2610: 72 6f 6d 20 68 61 73 68 20 74 61 62 6c 65 20 69 rom hash table i
2620: 48 61 73 68 20 61 6e 64 20 6c 69 6e 6b 20 74 68 Hash and link th
2630: 65 6d 20 69 6e 74 6f 20 61 20 6c 69 73 74 0a 2a em into a list.*
2640: 2a 20 69 6e 20 73 6f 72 74 65 64 20 6f 72 64 65 * in sorted orde
2650: 72 2e 20 54 68 65 20 68 61 73 68 20 74 61 62 6c r. The hash tabl
2660: 65 20 69 73 20 63 6c 65 61 72 65 64 20 62 65 66 e is cleared bef
2670: 6f 72 65 20 72 65 74 75 72 6e 69 6e 67 2e 20 49 ore returning. I
2680: 74 20 69 73 0a 2a 2a 20 74 68 65 20 72 65 73 70 t is.** the resp
2690: 6f 6e 73 69 62 69 6c 69 74 79 20 6f 66 20 74 68 onsibility of th
26a0: 65 20 63 61 6c 6c 65 72 20 74 6f 20 66 72 65 65 e caller to free
26b0: 20 74 68 65 20 65 6c 65 6d 65 6e 74 73 20 6f 66 the elements of
26c0: 20 74 68 65 20 72 65 74 75 72 6e 65 64 0a 2a 2a the returned.**
26d0: 20 6c 69 73 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 list..*/.static
26e0: 20 69 6e 74 20 66 74 73 35 48 61 73 68 45 6e 74 int fts5HashEnt
26f0: 72 79 53 6f 72 74 28 0a 20 20 46 74 73 35 48 61 rySort(. Fts5Ha
2700: 73 68 20 2a 70 48 61 73 68 2c 20 0a 20 20 63 6f sh *pHash, . co
2710: 6e 73 74 20 63 68 61 72 20 2a 70 54 65 72 6d 2c nst char *pTerm,
2720: 20 69 6e 74 20 6e 54 65 72 6d 2c 20 20 20 2f 2a int nTerm, /*
2730: 20 51 75 65 72 79 20 70 72 65 66 69 78 2c 20 69 Query prefix, i
2740: 66 20 61 6e 79 20 2a 2f 0a 20 20 46 74 73 35 48 f any */. Fts5H
2750: 61 73 68 45 6e 74 72 79 20 2a 2a 70 70 53 6f 72 ashEntry **ppSor
2760: 74 65 64 0a 29 7b 0a 20 20 63 6f 6e 73 74 20 69 ted.){. const i
2770: 6e 74 20 6e 4d 65 72 67 65 53 6c 6f 74 20 3d 20 nt nMergeSlot =
2780: 33 32 3b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 32;. Fts5HashEn
2790: 74 72 79 20 2a 2a 61 70 3b 0a 20 20 46 74 73 35 try **ap;. Fts5
27a0: 48 61 73 68 45 6e 74 72 79 20 2a 70 4c 69 73 74 HashEntry *pList
27b0: 3b 0a 20 20 69 6e 74 20 69 53 6c 6f 74 3b 0a 20 ;. int iSlot;.
27c0: 20 69 6e 74 20 69 3b 0a 0a 20 20 2a 70 70 53 6f int i;.. *ppSo
27d0: 72 74 65 64 20 3d 20 30 3b 0a 20 20 61 70 20 3d rted = 0;. ap =
27e0: 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 sqlite3_malloc(
27f0: 73 69 7a 65 6f 66 28 46 74 73 35 48 61 73 68 45 sizeof(Fts5HashE
2800: 6e 74 72 79 2a 29 20 2a 20 6e 4d 65 72 67 65 53 ntry*) * nMergeS
2810: 6c 6f 74 29 3b 0a 20 20 69 66 28 20 21 61 70 20 lot);. if( !ap
2820: 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f ) return SQLITE_
2830: 4e 4f 4d 45 4d 3b 0a 20 20 6d 65 6d 73 65 74 28 NOMEM;. memset(
2840: 61 70 2c 20 30 2c 20 73 69 7a 65 6f 66 28 46 74 ap, 0, sizeof(Ft
2850: 73 35 48 61 73 68 45 6e 74 72 79 2a 29 20 2a 20 s5HashEntry*) *
2860: 6e 4d 65 72 67 65 53 6c 6f 74 29 3b 0a 0a 20 20 nMergeSlot);..
2870: 66 6f 72 28 69 53 6c 6f 74 3d 30 3b 20 69 53 6c for(iSlot=0; iSl
2880: 6f 74 3c 70 48 61 73 68 2d 3e 6e 53 6c 6f 74 3b ot<pHash->nSlot;
2890: 20 69 53 6c 6f 74 2b 2b 29 7b 0a 20 20 20 20 46 iSlot++){. F
28a0: 74 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 49 ts5HashEntry *pI
28b0: 74 65 72 3b 0a 20 20 20 20 66 6f 72 28 70 49 74 ter;. for(pIt
28c0: 65 72 3d 70 48 61 73 68 2d 3e 61 53 6c 6f 74 5b er=pHash->aSlot[
28d0: 69 53 6c 6f 74 5d 3b 20 70 49 74 65 72 3b 20 70 iSlot]; pIter; p
28e0: 49 74 65 72 3d 70 49 74 65 72 2d 3e 70 48 61 73 Iter=pIter->pHas
28f0: 68 4e 65 78 74 29 7b 0a 20 20 20 20 20 20 69 66 hNext){. if
2900: 28 20 70 54 65 72 6d 3d 3d 30 20 7c 7c 20 30 3d ( pTerm==0 || 0=
2910: 3d 6d 65 6d 63 6d 70 28 70 49 74 65 72 2d 3e 7a =memcmp(pIter->z
2920: 4b 65 79 2c 20 70 54 65 72 6d 2c 20 6e 54 65 72 Key, pTerm, nTer
2930: 6d 29 20 29 7b 0a 20 20 20 20 20 20 20 20 46 74 m) ){. Ft
2940: 73 35 48 61 73 68 45 6e 74 72 79 20 2a 70 45 6e s5HashEntry *pEn
2950: 74 72 79 20 3d 20 70 49 74 65 72 3b 0a 20 20 20 try = pIter;.
2960: 20 20 20 20 20 70 45 6e 74 72 79 2d 3e 70 53 63 pEntry->pSc
2970: 61 6e 4e 65 78 74 20 3d 20 30 3b 0a 20 20 20 20 anNext = 0;.
2980: 20 20 20 20 66 6f 72 28 69 3d 30 3b 20 61 70 5b for(i=0; ap[
2990: 69 5d 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20 20 i]; i++){.
29a0: 20 20 20 20 70 45 6e 74 72 79 20 3d 20 66 74 73 pEntry = fts
29b0: 35 48 61 73 68 45 6e 74 72 79 4d 65 72 67 65 28 5HashEntryMerge(
29c0: 70 45 6e 74 72 79 2c 20 61 70 5b 69 5d 29 3b 0a pEntry, ap[i]);.
29d0: 20 20 20 20 20 20 20 20 20 20 61 70 5b 69 5d 20 ap[i]
29e0: 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 = 0;. }.
29f0: 20 20 20 20 20 20 20 61 70 5b 69 5d 20 3d 20 70 ap[i] = p
2a00: 45 6e 74 72 79 3b 0a 20 20 20 20 20 20 7d 0a 20 Entry;. }.
2a10: 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 70 4c 69 73 }. }.. pLis
2a20: 74 20 3d 20 30 3b 0a 20 20 66 6f 72 28 69 3d 30 t = 0;. for(i=0
2a30: 3b 20 69 3c 6e 4d 65 72 67 65 53 6c 6f 74 3b 20 ; i<nMergeSlot;
2a40: 69 2b 2b 29 7b 0a 20 20 20 20 70 4c 69 73 74 20 i++){. pList
2a50: 3d 20 66 74 73 35 48 61 73 68 45 6e 74 72 79 4d = fts5HashEntryM
2a60: 65 72 67 65 28 70 4c 69 73 74 2c 20 61 70 5b 69 erge(pList, ap[i
2a70: 5d 29 3b 0a 20 20 7d 0a 0a 20 20 70 48 61 73 68 ]);. }.. pHash
2a80: 2d 3e 6e 45 6e 74 72 79 20 3d 20 30 3b 0a 20 20 ->nEntry = 0;.
2a90: 73 71 6c 69 74 65 33 5f 66 72 65 65 28 61 70 29 sqlite3_free(ap)
2aa0: 3b 0a 20 20 2a 70 70 53 6f 72 74 65 64 20 3d 20 ;. *ppSorted =
2ab0: 70 4c 69 73 74 3b 0a 20 20 72 65 74 75 72 6e 20 pList;. return
2ac0: 53 51 4c 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a SQLITE_OK;.}../*
2ad0: 0a 2a 2a 20 51 75 65 72 79 20 74 68 65 20 68 61 .** Query the ha
2ae0: 73 68 20 74 61 62 6c 65 20 66 6f 72 20 61 20 64 sh table for a d
2af0: 6f 63 6c 69 73 74 20 61 73 73 6f 63 69 61 74 65 oclist associate
2b00: 64 20 77 69 74 68 20 74 65 72 6d 20 70 54 65 72 d with term pTer
2b10: 6d 2f 6e 54 65 72 6d 2e 0a 2a 2f 0a 69 6e 74 20 m/nTerm..*/.int
2b20: 73 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 51 sqlite3Fts5HashQ
2b30: 75 65 72 79 28 0a 20 20 46 74 73 35 48 61 73 68 uery(. Fts5Hash
2b40: 20 2a 70 48 61 73 68 2c 20 20 20 20 20 20 20 20 *pHash,
2b50: 20 20 20 20 20 20 20 20 2f 2a 20 48 61 73 68 20 /* Hash
2b60: 74 61 62 6c 65 20 74 6f 20 71 75 65 72 79 20 2a table to query *
2b70: 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a /. const char *
2b80: 70 54 65 72 6d 2c 20 69 6e 74 20 6e 54 65 72 6d pTerm, int nTerm
2b90: 2c 20 20 20 2f 2a 20 51 75 65 72 79 20 74 65 72 , /* Query ter
2ba0: 6d 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61 m */. const cha
2bb0: 72 20 2a 2a 70 70 44 6f 63 6c 69 73 74 2c 20 20 r **ppDoclist,
2bc0: 20 20 20 20 20 20 20 2f 2a 20 4f 55 54 3a 20 50 /* OUT: P
2bd0: 6f 69 6e 74 65 72 20 74 6f 20 64 6f 63 6c 69 73 ointer to doclis
2be0: 74 20 66 6f 72 20 70 54 65 72 6d 20 2a 2f 0a 20 t for pTerm */.
2bf0: 20 69 6e 74 20 2a 70 6e 44 6f 63 6c 69 73 74 20 int *pnDoclist
2c00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2c10: 20 2f 2a 20 4f 55 54 3a 20 53 69 7a 65 20 6f 66 /* OUT: Size of
2c20: 20 64 6f 63 6c 69 73 74 20 69 6e 20 62 79 74 65 doclist in byte
2c30: 73 20 2a 2f 0a 29 7b 0a 20 20 75 6e 73 69 67 6e s */.){. unsign
2c40: 65 64 20 69 6e 74 20 69 48 61 73 68 20 3d 20 66 ed int iHash = f
2c50: 74 73 35 48 61 73 68 4b 65 79 28 70 48 61 73 68 ts5HashKey(pHash
2c60: 2d 3e 6e 53 6c 6f 74 2c 20 70 54 65 72 6d 2c 20 ->nSlot, pTerm,
2c70: 6e 54 65 72 6d 29 3b 0a 20 20 46 74 73 35 48 61 nTerm);. Fts5Ha
2c80: 73 68 45 6e 74 72 79 20 2a 70 3b 0a 0a 20 20 66 shEntry *p;.. f
2c90: 6f 72 28 70 3d 70 48 61 73 68 2d 3e 61 53 6c 6f or(p=pHash->aSlo
2ca0: 74 5b 69 48 61 73 68 5d 3b 20 70 3b 20 70 3d 70 t[iHash]; p; p=p
2cb0: 2d 3e 70 48 61 73 68 4e 65 78 74 29 7b 0a 20 20 ->pHashNext){.
2cc0: 20 20 69 66 28 20 6d 65 6d 63 6d 70 28 70 2d 3e if( memcmp(p->
2cd0: 7a 4b 65 79 2c 20 70 54 65 72 6d 2c 20 6e 54 65 zKey, pTerm, nTe
2ce0: 72 6d 29 3d 3d 30 20 26 26 20 70 2d 3e 7a 4b 65 rm)==0 && p->zKe
2cf0: 79 5b 6e 54 65 72 6d 5d 3d 3d 30 20 29 20 62 72 y[nTerm]==0 ) br
2d00: 65 61 6b 3b 0a 20 20 7d 0a 0a 20 20 69 66 28 20 eak;. }.. if(
2d10: 70 20 29 7b 0a 20 20 20 20 66 74 73 35 48 61 73 p ){. fts5Has
2d20: 68 41 64 64 50 6f 73 6c 69 73 74 53 69 7a 65 28 hAddPoslistSize(
2d30: 70 29 3b 0a 20 20 20 20 2a 70 70 44 6f 63 6c 69 p);. *ppDocli
2d40: 73 74 20 3d 20 26 70 2d 3e 7a 4b 65 79 5b 6e 54 st = &p->zKey[nT
2d50: 65 72 6d 2b 31 5d 3b 0a 20 20 20 20 2a 70 6e 44 erm+1];. *pnD
2d60: 6f 63 6c 69 73 74 20 3d 20 70 2d 3e 6e 44 61 74 oclist = p->nDat
2d70: 61 20 2d 20 28 73 69 7a 65 6f 66 28 2a 70 29 20 a - (sizeof(*p)
2d80: 2b 20 6e 54 65 72 6d 20 2b 20 31 29 3b 0a 20 20 + nTerm + 1);.
2d90: 7d 65 6c 73 65 7b 0a 20 20 20 20 2a 70 70 44 6f }else{. *ppDo
2da0: 63 6c 69 73 74 20 3d 20 30 3b 0a 20 20 20 20 2a clist = 0;. *
2db0: 70 6e 44 6f 63 6c 69 73 74 20 3d 20 30 3b 0a 20 pnDoclist = 0;.
2dc0: 20 7d 0a 0a 20 20 72 65 74 75 72 6e 20 53 51 4c }.. return SQL
2dd0: 49 54 45 5f 4f 4b 3b 0a 7d 0a 0a 69 6e 74 20 73 ITE_OK;.}..int s
2de0: 71 6c 69 74 65 33 46 74 73 35 48 61 73 68 53 63 qlite3Fts5HashSc
2df0: 61 6e 49 6e 69 74 28 0a 20 20 46 74 73 35 48 61 anInit(. Fts5Ha
2e00: 73 68 20 2a 70 2c 20 20 20 20 20 20 20 20 20 20 sh *p,
2e10: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 48 61 73 /* Has
2e20: 68 20 74 61 62 6c 65 20 74 6f 20 71 75 65 72 79 h table to query
2e30: 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 */. const char
2e40: 20 2a 70 54 65 72 6d 2c 20 69 6e 74 20 6e 54 65 *pTerm, int nTe
2e50: 72 6d 20 20 20 20 2f 2a 20 51 75 65 72 79 20 70 rm /* Query p
2e60: 72 65 66 69 78 20 2a 2f 0a 29 7b 0a 20 20 72 65 refix */.){. re
2e70: 74 75 72 6e 20 66 74 73 35 48 61 73 68 45 6e 74 turn fts5HashEnt
2e80: 72 79 53 6f 72 74 28 70 2c 20 70 54 65 72 6d 2c rySort(p, pTerm,
2e90: 20 6e 54 65 72 6d 2c 20 26 70 2d 3e 70 53 63 61 nTerm, &p->pSca
2ea0: 6e 29 3b 0a 7d 0a 0a 76 6f 69 64 20 73 71 6c 69 n);.}..void sqli
2eb0: 74 65 33 46 74 73 35 48 61 73 68 53 63 61 6e 4e te3Fts5HashScanN
2ec0: 65 78 74 28 46 74 73 35 48 61 73 68 20 2a 70 29 ext(Fts5Hash *p)
2ed0: 7b 0a 20 20 46 74 73 35 48 61 73 68 45 6e 74 72 {. Fts5HashEntr
2ee0: 79 20 2a 70 53 63 61 6e 20 3d 20 70 2d 3e 70 53 y *pScan = p->pS
2ef0: 63 61 6e 3b 0a 20 20 69 66 28 20 70 53 63 61 6e can;. if( pScan
2f00: 20 29 20 70 2d 3e 70 53 63 61 6e 20 3d 20 70 53 ) p->pScan = pS
2f10: 63 61 6e 2d 3e 70 53 63 61 6e 4e 65 78 74 3b 0a can->pScanNext;.
2f20: 7d 0a 0a 69 6e 74 20 73 71 6c 69 74 65 33 46 74 }..int sqlite3Ft
2f30: 73 35 48 61 73 68 53 63 61 6e 45 6f 66 28 46 74 s5HashScanEof(Ft
2f40: 73 35 48 61 73 68 20 2a 70 29 7b 0a 20 20 72 65 s5Hash *p){. re
2f50: 74 75 72 6e 20 28 70 2d 3e 70 53 63 61 6e 3d 3d turn (p->pScan==
2f60: 30 29 3b 0a 7d 0a 0a 76 6f 69 64 20 73 71 6c 69 0);.}..void sqli
2f70: 74 65 33 46 74 73 35 48 61 73 68 53 63 61 6e 45 te3Fts5HashScanE
2f80: 6e 74 72 79 28 0a 20 20 46 74 73 35 48 61 73 68 ntry(. Fts5Hash
2f90: 20 2a 70 48 61 73 68 2c 0a 20 20 63 6f 6e 73 74 *pHash,. const
2fa0: 20 63 68 61 72 20 2a 2a 70 7a 54 65 72 6d 2c 20 char **pzTerm,
2fb0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 55 /* OU
2fc0: 54 3a 20 74 65 72 6d 20 28 6e 75 6c 2d 74 65 72 T: term (nul-ter
2fd0: 6d 69 6e 61 74 65 64 29 20 2a 2f 0a 20 20 63 6f minated) */. co
2fe0: 6e 73 74 20 63 68 61 72 20 2a 2a 70 70 44 6f 63 nst char **ppDoc
2ff0: 6c 69 73 74 2c 20 20 20 20 20 20 20 20 20 2f 2a list, /*
3000: 20 4f 55 54 3a 20 70 6f 69 6e 74 65 72 20 74 6f OUT: pointer to
3010: 20 64 6f 63 6c 69 73 74 20 2a 2f 0a 20 20 69 6e doclist */. in
3020: 74 20 2a 70 6e 44 6f 63 6c 69 73 74 20 20 20 20 t *pnDoclist
3030: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a /*
3040: 20 4f 55 54 3a 20 73 69 7a 65 20 6f 66 20 64 6f OUT: size of do
3050: 63 6c 69 73 74 20 69 6e 20 62 79 74 65 73 20 2a clist in bytes *
3060: 2f 0a 29 7b 0a 20 20 46 74 73 35 48 61 73 68 45 /.){. Fts5HashE
3070: 6e 74 72 79 20 2a 70 3b 0a 20 20 69 66 28 20 28 ntry *p;. if( (
3080: 70 20 3d 20 70 48 61 73 68 2d 3e 70 53 63 61 6e p = pHash->pScan
3090: 29 20 29 7b 0a 20 20 20 20 69 6e 74 20 6e 54 65 ) ){. int nTe
30a0: 72 6d 20 3d 20 73 74 72 6c 65 6e 28 70 2d 3e 7a rm = strlen(p->z
30b0: 4b 65 79 29 3b 0a 20 20 20 20 66 74 73 35 48 61 Key);. fts5Ha
30c0: 73 68 41 64 64 50 6f 73 6c 69 73 74 53 69 7a 65 shAddPoslistSize
30d0: 28 70 29 3b 0a 20 20 20 20 2a 70 7a 54 65 72 6d (p);. *pzTerm
30e0: 20 3d 20 70 2d 3e 7a 4b 65 79 3b 0a 20 20 20 20 = p->zKey;.
30f0: 2a 70 70 44 6f 63 6c 69 73 74 20 3d 20 26 70 2d *ppDoclist = &p-
3100: 3e 7a 4b 65 79 5b 6e 54 65 72 6d 2b 31 5d 3b 0a >zKey[nTerm+1];.
3110: 20 20 20 20 2a 70 6e 44 6f 63 6c 69 73 74 20 3d *pnDoclist =
3120: 20 70 2d 3e 6e 44 61 74 61 20 2d 20 28 73 69 7a p->nData - (siz
3130: 65 6f 66 28 2a 70 29 20 2b 20 6e 54 65 72 6d 20 eof(*p) + nTerm
3140: 2b 20 31 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 + 1);. }else{.
3150: 20 20 20 2a 70 7a 54 65 72 6d 20 3d 20 30 3b 0a *pzTerm = 0;.
3160: 20 20 20 20 2a 70 70 44 6f 63 6c 69 73 74 20 3d *ppDoclist =
3170: 20 30 3b 0a 20 20 20 20 2a 70 6e 44 6f 63 6c 69 0;. *pnDocli
3180: 73 74 20 3d 20 30 3b 0a 20 20 7d 0a 7d 0a 0a st = 0;. }.}..