0000: 2f 2a 0a 2a 2a 20 32 30 30 38 20 46 65 62 72 75 /*.** 2008 Febru
0010: 61 72 79 20 31 36 0a 2a 2a 0a 2a 2a 20 54 68 65 ary 16.**.** The
0020: 20 61 75 74 68 6f 72 20 64 69 73 63 6c 61 69 6d author disclaim
0030: 73 20 63 6f 70 79 72 69 67 68 74 20 74 6f 20 74 s copyright to t
0040: 68 69 73 20 73 6f 75 72 63 65 20 63 6f 64 65 2e his source code.
0050: 20 20 49 6e 20 70 6c 61 63 65 20 6f 66 0a 2a 2a In place of.**
0060: 20 61 20 6c 65 67 61 6c 20 6e 6f 74 69 63 65 2c a legal notice,
0070: 20 68 65 72 65 20 69 73 20 61 20 62 6c 65 73 73 here is a bless
0080: 69 6e 67 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 4d 61 ing:.**.** Ma
0090: 79 20 79 6f 75 20 64 6f 20 67 6f 6f 64 20 61 6e y you do good an
00a0: 64 20 6e 6f 74 20 65 76 69 6c 2e 0a 2a 2a 20 20 d not evil..**
00b0: 20 20 4d 61 79 20 79 6f 75 20 66 69 6e 64 20 66 May you find f
00c0: 6f 72 67 69 76 65 6e 65 73 73 20 66 6f 72 20 79 orgiveness for y
00d0: 6f 75 72 73 65 6c 66 20 61 6e 64 20 66 6f 72 67 ourself and forg
00e0: 69 76 65 20 6f 74 68 65 72 73 2e 0a 2a 2a 20 20 ive others..**
00f0: 20 20 4d 61 79 20 79 6f 75 20 73 68 61 72 65 20 May you share
0100: 66 72 65 65 6c 79 2c 20 6e 65 76 65 72 20 74 61 freely, never ta
0110: 6b 69 6e 67 20 6d 6f 72 65 20 74 68 61 6e 20 79 king more than y
0120: 6f 75 20 67 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a 2a ou 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 0a 2a 2a 20 54 68 69 73 20 66 69 *****.** This fi
0180: 6c 65 20 69 6d 70 6c 65 6d 65 6e 74 73 20 61 6e le implements an
0190: 20 6f 62 6a 65 63 74 20 74 68 61 74 20 72 65 70 object that rep
01a0: 72 65 73 65 6e 74 73 20 61 20 66 69 78 65 64 2d resents a fixed-
01b0: 6c 65 6e 67 74 68 0a 2a 2a 20 62 69 74 6d 61 70 length.** bitmap
01c0: 2e 20 20 42 69 74 73 20 61 72 65 20 6e 75 6d 62 . Bits are numb
01d0: 65 72 65 64 20 73 74 61 72 74 69 6e 67 20 77 69 ered starting wi
01e0: 74 68 20 31 2e 0a 2a 2a 0a 2a 2a 20 41 20 62 69 th 1..**.** A bi
01f0: 74 6d 61 70 20 69 73 20 75 73 65 64 20 74 6f 20 tmap is used to
0200: 72 65 63 6f 72 64 20 77 68 69 63 68 20 70 61 67 record which pag
0210: 65 73 20 6f 66 20 61 20 64 61 74 61 62 61 73 65 es of a database
0220: 20 66 69 6c 65 20 68 61 76 65 20 62 65 65 6e 0a file have been.
0230: 2a 2a 20 6a 6f 75 72 6e 61 6c 6c 65 64 20 64 75 ** journalled du
0240: 72 69 6e 67 20 61 20 74 72 61 6e 73 61 63 74 69 ring a transacti
0250: 6f 6e 2c 20 6f 72 20 77 68 69 63 68 20 70 61 67 on, or which pag
0260: 65 73 20 68 61 76 65 20 74 68 65 20 22 64 6f 6e es have the "don
0270: 74 2d 77 72 69 74 65 22 0a 2a 2a 20 70 72 6f 70 t-write".** prop
0280: 65 72 74 79 2e 20 20 55 73 75 61 6c 6c 79 20 6f erty. Usually o
0290: 6e 6c 79 20 61 20 66 65 77 20 70 61 67 65 73 20 nly a few pages
02a0: 61 72 65 20 6d 65 65 74 20 65 69 74 68 65 72 20 are meet either
02b0: 63 6f 6e 64 69 74 69 6f 6e 2e 0a 2a 2a 20 53 6f condition..** So
02c0: 20 74 68 65 20 62 69 74 6d 61 70 20 69 73 20 75 the bitmap is u
02d0: 73 75 61 6c 6c 79 20 73 70 61 72 73 65 20 61 6e sually sparse an
02e0: 64 20 68 61 73 20 6c 6f 77 20 63 61 72 64 69 6e d has low cardin
02f0: 61 6c 69 74 79 2e 0a 2a 2a 20 42 75 74 20 73 6f ality..** But so
0300: 6d 65 74 69 6d 65 73 20 28 66 6f 72 20 65 78 61 metimes (for exa
0310: 6d 70 6c 65 20 77 68 65 6e 20 64 75 72 69 6e 67 mple when during
0320: 20 61 20 44 52 4f 50 20 6f 66 20 61 20 6c 61 72 a DROP of a lar
0330: 67 65 20 74 61 62 6c 65 29 20 6d 6f 73 74 0a 2a ge table) most.*
0340: 2a 20 6f 72 20 61 6c 6c 20 6f 66 20 74 68 65 20 * or all of the
0350: 70 61 67 65 73 20 69 6e 20 61 20 64 61 74 61 62 pages in a datab
0360: 61 73 65 20 63 61 6e 20 67 65 74 20 6a 6f 75 72 ase can get jour
0370: 6e 61 6c 6c 65 64 2e 20 20 49 6e 20 74 68 6f 73 nalled. In thos
0380: 65 20 63 61 73 65 73 2c 20 0a 2a 2a 20 74 68 65 e cases, .** the
0390: 20 62 69 74 6d 61 70 20 62 65 63 6f 6d 65 73 20 bitmap becomes
03a0: 64 65 6e 73 65 20 77 69 74 68 20 68 69 67 68 20 dense with high
03b0: 63 61 72 64 69 6e 61 6c 69 74 79 2e 20 20 54 68 cardinality. Th
03c0: 65 20 61 6c 67 6f 72 69 74 68 6d 20 6e 65 65 64 e algorithm need
03d0: 73 20 0a 2a 2a 20 74 6f 20 68 61 6e 64 6c 65 20 s .** to handle
03e0: 62 6f 74 68 20 63 61 73 65 73 20 77 65 6c 6c 2e both cases well.
03f0: 0a 2a 2a 0a 2a 2a 20 54 68 65 20 73 69 7a 65 20 .**.** The size
0400: 6f 66 20 74 68 65 20 62 69 74 6d 61 70 20 69 73 of the bitmap is
0410: 20 66 69 78 65 64 20 77 68 65 6e 20 74 68 65 20 fixed when the
0420: 6f 62 6a 65 63 74 20 69 73 20 63 72 65 61 74 65 object is create
0430: 64 2e 0a 2a 2a 0a 2a 2a 20 41 6c 6c 20 62 69 74 d..**.** All bit
0440: 73 20 61 72 65 20 63 6c 65 61 72 20 77 68 65 6e s are clear when
0450: 20 74 68 65 20 62 69 74 6d 61 70 20 69 73 20 63 the bitmap is c
0460: 72 65 61 74 65 64 2e 20 20 49 6e 64 69 76 69 64 reated. Individ
0470: 75 61 6c 20 62 69 74 73 0a 2a 2a 20 6d 61 79 20 ual bits.** may
0480: 62 65 20 73 65 74 20 6f 72 20 63 6c 65 61 72 65 be set or cleare
0490: 64 20 6f 6e 65 20 61 74 20 61 20 74 69 6d 65 2e d one at a time.
04a0: 0a 2a 2a 0a 2a 2a 20 54 65 73 74 20 6f 70 65 72 .**.** Test oper
04b0: 61 74 69 6f 6e 73 20 61 72 65 20 61 62 6f 75 74 ations are about
04c0: 20 31 30 30 20 74 69 6d 65 73 20 6d 6f 72 65 20 100 times more
04d0: 63 6f 6d 6d 6f 6e 20 74 68 61 74 20 73 65 74 20 common that set
04e0: 6f 70 65 72 61 74 69 6f 6e 73 2e 0a 2a 2a 20 43 operations..** C
04f0: 6c 65 61 72 20 6f 70 65 72 61 74 69 6f 6e 73 20 lear operations
0500: 61 72 65 20 65 78 63 65 65 64 69 6e 67 6c 79 20 are exceedingly
0510: 72 61 72 65 2e 20 20 54 68 65 72 65 20 61 72 65 rare. There are
0520: 20 75 73 75 61 6c 6c 79 20 62 65 74 77 65 65 6e usually between
0530: 0a 2a 2a 20 35 20 61 6e 64 20 35 30 30 20 73 65 .** 5 and 500 se
0540: 74 20 6f 70 65 72 61 74 69 6f 6e 73 20 70 65 72 t operations per
0550: 20 42 69 74 76 65 63 20 6f 62 6a 65 63 74 2c 20 Bitvec object,
0560: 74 68 6f 75 67 68 20 74 68 65 20 6e 75 6d 62 65 though the numbe
0570: 72 20 6f 66 20 73 65 74 73 20 63 61 6e 0a 2a 2a r of sets can.**
0580: 20 73 6f 6d 65 74 69 6d 65 73 20 67 72 6f 77 20 sometimes grow
0590: 69 6e 74 6f 20 74 65 6e 73 20 6f 66 20 74 68 6f into tens of tho
05a0: 75 73 61 6e 64 73 20 6f 72 20 6c 61 72 67 65 72 usands or larger
05b0: 2e 20 20 54 68 65 20 73 69 7a 65 20 6f 66 20 74 . The size of t
05c0: 68 65 0a 2a 2a 20 42 69 74 76 65 63 20 6f 62 6a he.** Bitvec obj
05d0: 65 63 74 20 69 73 20 74 68 65 20 6e 75 6d 62 65 ect is the numbe
05e0: 72 20 6f 66 20 70 61 67 65 73 20 69 6e 20 74 68 r of pages in th
05f0: 65 20 64 61 74 61 62 61 73 65 20 66 69 6c 65 20 e database file
0600: 61 74 20 74 68 65 0a 2a 2a 20 73 74 61 72 74 20 at the.** start
0610: 6f 66 20 61 20 74 72 61 6e 73 61 63 74 69 6f 6e of a transaction
0620: 2c 20 61 6e 64 20 69 73 20 74 68 75 73 20 75 73 , and is thus us
0630: 75 61 6c 6c 79 20 6c 65 73 73 20 74 68 61 6e 20 ually less than
0640: 61 20 66 65 77 20 74 68 6f 75 73 61 6e 64 2c 0a a few thousand,.
0650: 2a 2a 20 62 75 74 20 63 61 6e 20 62 65 20 61 73 ** but can be as
0660: 20 6c 61 72 67 65 20 61 73 20 32 20 62 69 6c 6c large as 2 bill
0670: 69 6f 6e 20 66 6f 72 20 61 20 72 65 61 6c 6c 79 ion for a really
0680: 20 62 69 67 20 64 61 74 61 62 61 73 65 2e 0a 2a big database..*
0690: 2a 0a 2a 2a 20 40 28 23 29 20 24 49 64 3a 20 62 *.** @(#) $Id: b
06a0: 69 74 76 65 63 2e 63 2c 76 20 31 2e 31 35 20 32 itvec.c,v 1.15 2
06b0: 30 30 39 2f 30 36 2f 30 32 20 32 31 3a 33 31 3a 009/06/02 21:31:
06c0: 33 39 20 64 72 68 20 45 78 70 20 24 0a 2a 2f 0a 39 drh Exp $.*/.
06d0: 23 69 6e 63 6c 75 64 65 20 22 73 71 6c 69 74 65 #include "sqlite
06e0: 49 6e 74 2e 68 22 0a 0a 2f 2a 20 53 69 7a 65 20 Int.h"../* Size
06f0: 6f 66 20 74 68 65 20 42 69 74 76 65 63 20 73 74 of the Bitvec st
0700: 72 75 63 74 75 72 65 20 69 6e 20 62 79 74 65 73 ructure in bytes
0710: 2e 20 2a 2f 0a 23 64 65 66 69 6e 65 20 42 49 54 . */.#define BIT
0720: 56 45 43 5f 53 5a 20 20 20 20 20 20 20 20 35 31 VEC_SZ 51
0730: 32 0a 0a 2f 2a 20 52 6f 75 6e 64 20 74 68 65 20 2../* Round the
0740: 75 6e 69 6f 6e 20 73 69 7a 65 20 64 6f 77 6e 20 union size down
0750: 74 6f 20 74 68 65 20 6e 65 61 72 65 73 74 20 70 to the nearest p
0760: 6f 69 6e 74 65 72 20 62 6f 75 6e 64 61 72 79 2c ointer boundary,
0770: 20 73 69 6e 63 65 20 74 68 61 74 27 73 20 68 6f since that's ho
0780: 77 20 0a 2a 2a 20 69 74 20 77 69 6c 6c 20 62 65 w .** it will be
0790: 20 61 6c 69 67 6e 65 64 20 77 69 74 68 69 6e 20 aligned within
07a0: 74 68 65 20 42 69 74 76 65 63 20 73 74 72 75 63 the Bitvec struc
07b0: 74 2e 20 2a 2f 0a 23 64 65 66 69 6e 65 20 42 49 t. */.#define BI
07c0: 54 56 45 43 5f 55 53 49 5a 45 20 20 20 20 20 28 TVEC_USIZE (
07d0: 28 28 42 49 54 56 45 43 5f 53 5a 2d 28 33 2a 73 ((BITVEC_SZ-(3*s
07e0: 69 7a 65 6f 66 28 75 33 32 29 29 29 2f 73 69 7a izeof(u32)))/siz
07f0: 65 6f 66 28 42 69 74 76 65 63 2a 29 29 2a 73 69 eof(Bitvec*))*si
0800: 7a 65 6f 66 28 42 69 74 76 65 63 2a 29 29 0a 0a zeof(Bitvec*))..
0810: 2f 2a 20 54 79 70 65 20 6f 66 20 74 68 65 20 61 /* Type of the a
0820: 72 72 61 79 20 22 65 6c 65 6d 65 6e 74 22 20 66 rray "element" f
0830: 6f 72 20 74 68 65 20 62 69 74 6d 61 70 20 72 65 or the bitmap re
0840: 70 72 65 73 65 6e 74 61 74 69 6f 6e 2e 20 0a 2a presentation. .*
0850: 2a 20 53 68 6f 75 6c 64 20 62 65 20 61 20 70 6f * Should be a po
0860: 77 65 72 20 6f 66 20 32 2c 20 61 6e 64 20 69 64 wer of 2, and id
0870: 65 61 6c 6c 79 2c 20 65 76 65 6e 6c 79 20 64 69 eally, evenly di
0880: 76 69 64 65 20 69 6e 74 6f 20 42 49 54 56 45 43 vide into BITVEC
0890: 5f 55 53 49 5a 45 2e 20 0a 2a 2a 20 53 65 74 74 _USIZE. .** Sett
08a0: 69 6e 67 20 74 68 69 73 20 74 6f 20 74 68 65 20 ing this to the
08b0: 22 6e 61 74 75 72 61 6c 20 77 6f 72 64 22 20 73 "natural word" s
08c0: 69 7a 65 20 6f 66 20 79 6f 75 72 20 43 50 55 20 ize of your CPU
08d0: 6d 61 79 20 69 6d 70 72 6f 76 65 0a 2a 2a 20 70 may improve.** p
08e0: 65 72 66 6f 72 6d 61 6e 63 65 2e 20 2a 2f 0a 23 erformance. */.#
08f0: 64 65 66 69 6e 65 20 42 49 54 56 45 43 5f 54 45 define BITVEC_TE
0900: 4c 45 4d 20 20 20 20 20 75 38 0a 2f 2a 20 53 69 LEM u8./* Si
0910: 7a 65 2c 20 69 6e 20 62 69 74 73 2c 20 6f 66 20 ze, in bits, of
0920: 74 68 65 20 62 69 74 6d 61 70 20 65 6c 65 6d 65 the bitmap eleme
0930: 6e 74 2e 20 2a 2f 0a 23 64 65 66 69 6e 65 20 42 nt. */.#define B
0940: 49 54 56 45 43 5f 53 5a 45 4c 45 4d 20 20 20 20 ITVEC_SZELEM
0950: 38 0a 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65 8./* Number of e
0960: 6c 65 6d 65 6e 74 73 20 69 6e 20 61 20 62 69 74 lements in a bit
0970: 6d 61 70 20 61 72 72 61 79 2e 20 2a 2f 0a 23 64 map array. */.#d
0980: 65 66 69 6e 65 20 42 49 54 56 45 43 5f 4e 45 4c efine BITVEC_NEL
0990: 45 4d 20 20 20 20 20 28 42 49 54 56 45 43 5f 55 EM (BITVEC_U
09a0: 53 49 5a 45 2f 73 69 7a 65 6f 66 28 42 49 54 56 SIZE/sizeof(BITV
09b0: 45 43 5f 54 45 4c 45 4d 29 29 0a 2f 2a 20 4e 75 EC_TELEM))./* Nu
09c0: 6d 62 65 72 20 6f 66 20 62 69 74 73 20 69 6e 20 mber of bits in
09d0: 74 68 65 20 62 69 74 6d 61 70 20 61 72 72 61 79 the bitmap array
09e0: 2e 20 2a 2f 0a 23 64 65 66 69 6e 65 20 42 49 54 . */.#define BIT
09f0: 56 45 43 5f 4e 42 49 54 20 20 20 20 20 20 28 42 VEC_NBIT (B
0a00: 49 54 56 45 43 5f 4e 45 4c 45 4d 2a 42 49 54 56 ITVEC_NELEM*BITV
0a10: 45 43 5f 53 5a 45 4c 45 4d 29 0a 0a 2f 2a 20 4e EC_SZELEM)../* N
0a20: 75 6d 62 65 72 20 6f 66 20 75 33 32 20 76 61 6c umber of u32 val
0a30: 75 65 73 20 69 6e 20 68 61 73 68 20 74 61 62 6c ues in hash tabl
0a40: 65 2e 20 2a 2f 0a 23 64 65 66 69 6e 65 20 42 49 e. */.#define BI
0a50: 54 56 45 43 5f 4e 49 4e 54 20 20 20 20 20 20 28 TVEC_NINT (
0a60: 42 49 54 56 45 43 5f 55 53 49 5a 45 2f 73 69 7a BITVEC_USIZE/siz
0a70: 65 6f 66 28 75 33 32 29 29 0a 2f 2a 20 4d 61 78 eof(u32))./* Max
0a80: 69 6d 75 6d 20 6e 75 6d 62 65 72 20 6f 66 20 65 imum number of e
0a90: 6e 74 72 69 65 73 20 69 6e 20 68 61 73 68 20 74 ntries in hash t
0aa0: 61 62 6c 65 20 62 65 66 6f 72 65 20 0a 2a 2a 20 able before .**
0ab0: 73 75 62 2d 64 69 76 69 64 69 6e 67 20 61 6e 64 sub-dividing and
0ac0: 20 72 65 2d 68 61 73 68 69 6e 67 2e 20 2a 2f 0a re-hashing. */.
0ad0: 23 64 65 66 69 6e 65 20 42 49 54 56 45 43 5f 4d #define BITVEC_M
0ae0: 58 48 41 53 48 20 20 20 20 28 42 49 54 56 45 43 XHASH (BITVEC
0af0: 5f 4e 49 4e 54 2f 32 29 0a 2f 2a 20 48 61 73 68 _NINT/2)./* Hash
0b00: 69 6e 67 20 66 75 6e 63 74 69 6f 6e 20 66 6f 72 ing function for
0b10: 20 74 68 65 20 61 48 61 73 68 20 72 65 70 72 65 the aHash repre
0b20: 73 65 6e 74 61 74 69 6f 6e 2e 0a 2a 2a 20 45 6d sentation..** Em
0b30: 70 69 72 69 63 61 6c 20 74 65 73 74 69 6e 67 20 pirical testing
0b40: 73 68 6f 77 65 64 20 74 68 61 74 20 74 68 65 20 showed that the
0b50: 2a 33 37 20 6d 75 6c 74 69 70 6c 69 65 72 20 0a *37 multiplier .
0b60: 2a 2a 20 28 61 6e 20 61 72 62 69 74 72 61 72 79 ** (an arbitrary
0b70: 20 70 72 69 6d 65 29 69 6e 20 74 68 65 20 68 61 prime)in the ha
0b80: 73 68 20 66 75 6e 63 74 69 6f 6e 20 70 72 6f 76 sh function prov
0b90: 69 64 65 64 20 0a 2a 2a 20 6e 6f 20 66 65 77 65 ided .** no fewe
0ba0: 72 20 63 6f 6c 6c 69 73 69 6f 6e 73 20 74 68 61 r collisions tha
0bb0: 6e 20 74 68 65 20 6e 6f 2d 6f 70 20 2a 31 2e 20 n the no-op *1.
0bc0: 2a 2f 0a 23 64 65 66 69 6e 65 20 42 49 54 56 45 */.#define BITVE
0bd0: 43 5f 48 41 53 48 28 58 29 20 20 20 28 28 28 58 C_HASH(X) (((X
0be0: 29 2a 31 29 25 42 49 54 56 45 43 5f 4e 49 4e 54 )*1)%BITVEC_NINT
0bf0: 29 0a 0a 23 64 65 66 69 6e 65 20 42 49 54 56 45 )..#define BITVE
0c00: 43 5f 4e 50 54 52 20 20 20 20 20 20 28 42 49 54 C_NPTR (BIT
0c10: 56 45 43 5f 55 53 49 5a 45 2f 73 69 7a 65 6f 66 VEC_USIZE/sizeof
0c20: 28 42 69 74 76 65 63 20 2a 29 29 0a 0a 0a 2f 2a (Bitvec *)).../*
0c30: 0a 2a 2a 20 41 20 62 69 74 6d 61 70 20 69 73 20 .** A bitmap is
0c40: 61 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 an instance of t
0c50: 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 73 74 72 he following str
0c60: 75 63 74 75 72 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 ucture..**.** Th
0c70: 69 73 20 62 69 74 6d 61 70 20 72 65 63 6f 72 64 is bitmap record
0c80: 73 20 74 68 65 20 65 78 69 73 74 61 6e 63 65 20 s the existance
0c90: 6f 66 20 7a 65 72 6f 20 6f 72 20 6d 6f 72 65 20 of zero or more
0ca0: 62 69 74 73 0a 2a 2a 20 77 69 74 68 20 76 61 6c bits.** with val
0cb0: 75 65 73 20 62 65 74 77 65 65 6e 20 31 20 61 6e ues between 1 an
0cc0: 64 20 69 53 69 7a 65 2c 20 69 6e 63 6c 75 73 69 d iSize, inclusi
0cd0: 76 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 72 65 20 ve..**.** There
0ce0: 61 72 65 20 74 68 72 65 65 20 70 6f 73 73 69 62 are three possib
0cf0: 6c 65 20 72 65 70 72 65 73 65 6e 74 61 74 69 6f le representatio
0d00: 6e 73 20 6f 66 20 74 68 65 20 62 69 74 6d 61 70 ns of the bitmap
0d10: 2e 0a 2a 2a 20 49 66 20 69 53 69 7a 65 3c 3d 42 ..** If iSize<=B
0d20: 49 54 56 45 43 5f 4e 42 49 54 2c 20 74 68 65 6e ITVEC_NBIT, then
0d30: 20 42 69 74 76 65 63 2e 75 2e 61 42 69 74 6d 61 Bitvec.u.aBitma
0d40: 70 5b 5d 20 69 73 20 61 20 73 74 72 61 69 67 68 p[] is a straigh
0d50: 74 0a 2a 2a 20 62 69 74 6d 61 70 2e 20 20 54 68 t.** bitmap. Th
0d60: 65 20 6c 65 61 73 74 20 73 69 67 6e 69 66 69 63 e least signific
0d70: 61 6e 74 20 62 69 74 20 69 73 20 62 69 74 20 31 ant bit is bit 1
0d80: 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 69 53 69 7a 65 ..**.** If iSize
0d90: 3e 42 49 54 56 45 43 5f 4e 42 49 54 20 61 6e 64 >BITVEC_NBIT and
0da0: 20 69 44 69 76 69 73 6f 72 3d 3d 30 20 74 68 65 iDivisor==0 the
0db0: 6e 20 42 69 74 76 65 63 2e 75 2e 61 48 61 73 68 n Bitvec.u.aHash
0dc0: 5b 5d 20 69 73 0a 2a 2a 20 61 20 68 61 73 68 20 [] is.** a hash
0dd0: 74 61 62 6c 65 20 74 68 61 74 20 77 69 6c 6c 20 table that will
0de0: 68 6f 6c 64 20 75 70 20 74 6f 20 42 49 54 56 45 hold up to BITVE
0df0: 43 5f 4d 58 48 41 53 48 20 64 69 73 74 69 6e 63 C_MXHASH distinc
0e00: 74 20 76 61 6c 75 65 73 2e 0a 2a 2a 0a 2a 2a 20 t values..**.**
0e10: 4f 74 68 65 72 77 69 73 65 2c 20 74 68 65 20 76 Otherwise, the v
0e20: 61 6c 75 65 20 69 20 69 73 20 72 65 64 69 72 65 alue i is redire
0e30: 63 74 65 64 20 69 6e 74 6f 20 6f 6e 65 20 6f 66 cted into one of
0e40: 20 42 49 54 56 45 43 5f 4e 50 54 52 0a 2a 2a 20 BITVEC_NPTR.**
0e50: 73 75 62 2d 62 69 74 6d 61 70 73 20 70 6f 69 6e sub-bitmaps poin
0e60: 74 65 64 20 74 6f 20 62 79 20 42 69 74 76 65 63 ted to by Bitvec
0e70: 2e 75 2e 61 70 53 75 62 5b 5d 2e 20 20 45 61 63 .u.apSub[]. Eac
0e80: 68 20 73 75 62 62 69 74 6d 61 70 0a 2a 2a 20 68 h subbitmap.** h
0e90: 61 6e 64 6c 65 73 20 75 70 20 74 6f 20 69 44 69 andles up to iDi
0ea0: 76 69 73 6f 72 20 73 65 70 61 72 61 74 65 20 76 visor separate v
0eb0: 61 6c 75 65 73 20 6f 66 20 69 2e 20 20 61 70 53 alues of i. apS
0ec0: 75 62 5b 30 5d 20 68 6f 6c 64 73 0a 2a 2a 20 76 ub[0] holds.** v
0ed0: 61 6c 75 65 73 20 62 65 74 77 65 65 6e 20 31 20 alues between 1
0ee0: 61 6e 64 20 69 44 69 76 69 73 6f 72 2e 20 20 61 and iDivisor. a
0ef0: 70 53 75 62 5b 31 5d 20 68 6f 6c 64 73 20 76 61 pSub[1] holds va
0f00: 6c 75 65 73 20 62 65 74 77 65 65 6e 0a 2a 2a 20 lues between.**
0f10: 69 44 69 76 69 73 6f 72 2b 31 20 61 6e 64 20 32 iDivisor+1 and 2
0f20: 2a 69 44 69 76 69 73 6f 72 2e 20 20 61 70 53 75 *iDivisor. apSu
0f30: 62 5b 4e 5d 20 68 6f 6c 64 73 20 76 61 6c 75 65 b[N] holds value
0f40: 73 20 62 65 74 77 65 65 6e 0a 2a 2a 20 4e 2a 69 s between.** N*i
0f50: 44 69 76 69 73 6f 72 2b 31 20 61 6e 64 20 28 4e Divisor+1 and (N
0f60: 2b 31 29 2a 69 44 69 76 69 73 6f 72 2e 20 20 45 +1)*iDivisor. E
0f70: 61 63 68 20 73 75 62 62 69 74 6d 61 70 20 69 73 ach subbitmap is
0f80: 20 6e 6f 72 6d 61 6c 69 7a 65 64 0a 2a 2a 20 74 normalized.** t
0f90: 6f 20 68 6f 6c 64 20 64 65 61 6c 20 77 69 74 68 o hold deal with
0fa0: 20 76 61 6c 75 65 73 20 62 65 74 77 65 65 6e 20 values between
0fb0: 31 20 61 6e 64 20 69 44 69 76 69 73 6f 72 2e 0a 1 and iDivisor..
0fc0: 2a 2f 0a 73 74 72 75 63 74 20 42 69 74 76 65 63 */.struct Bitvec
0fd0: 20 7b 0a 20 20 75 33 32 20 69 53 69 7a 65 3b 20 {. u32 iSize;
0fe0: 20 20 20 20 20 2f 2a 20 4d 61 78 69 6d 75 6d 20 /* Maximum
0ff0: 62 69 74 20 69 6e 64 65 78 2e 20 20 4d 61 78 20 bit index. Max
1000: 69 53 69 7a 65 20 69 73 20 34 2c 32 39 34 2c 39 iSize is 4,294,9
1010: 36 37 2c 32 39 36 2e 20 2a 2f 0a 20 20 75 33 32 67,296. */. u32
1020: 20 6e 53 65 74 3b 20 20 20 20 20 20 20 2f 2a 20 nSet; /*
1030: 4e 75 6d 62 65 72 20 6f 66 20 62 69 74 73 20 74 Number of bits t
1040: 68 61 74 20 61 72 65 20 73 65 74 20 2d 20 6f 6e hat are set - on
1050: 6c 79 20 76 61 6c 69 64 20 66 6f 72 20 61 48 61 ly valid for aHa
1060: 73 68 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 sh.
1070: 20 20 20 20 20 2a 2a 20 65 6c 65 6d 65 6e 74 2e ** element.
1080: 20 20 4d 61 78 20 69 73 20 42 49 54 56 45 43 5f Max is BITVEC_
1090: 4e 49 4e 54 2e 20 20 46 6f 72 20 42 49 54 56 45 NINT. For BITVE
10a0: 43 5f 53 5a 20 6f 66 20 35 31 32 2c 0a 20 20 20 C_SZ of 512,.
10b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2a *
10c0: 2a 20 74 68 69 73 20 77 6f 75 6c 64 20 62 65 20 * this would be
10d0: 31 32 35 2e 20 2a 2f 0a 20 20 75 33 32 20 69 44 125. */. u32 iD
10e0: 69 76 69 73 6f 72 3b 20 20 20 2f 2a 20 4e 75 6d ivisor; /* Num
10f0: 62 65 72 20 6f 66 20 62 69 74 73 20 68 61 6e 64 ber of bits hand
1100: 6c 65 64 20 62 79 20 65 61 63 68 20 61 70 53 75 led by each apSu
1110: 62 5b 5d 20 65 6e 74 72 79 2e 20 2a 2f 0a 20 20 b[] entry. */.
1120: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
1130: 2f 2a 20 53 68 6f 75 6c 64 20 3e 3d 30 20 66 6f /* Should >=0 fo
1140: 72 20 61 70 53 75 62 20 65 6c 65 6d 65 6e 74 2e r apSub element.
1150: 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 20 20 */.
1160: 20 20 20 20 20 20 2f 2a 20 4d 61 78 20 69 44 69 /* Max iDi
1170: 76 69 73 6f 72 20 69 73 20 6d 61 78 28 75 33 32 visor is max(u32
1180: 29 20 2f 20 42 49 54 56 45 43 5f 4e 50 54 52 20 ) / BITVEC_NPTR
1190: 2b 20 31 2e 20 20 2a 2f 0a 20 20 20 20 20 20 20 + 1. */.
11a0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 46 6f /* Fo
11b0: 72 20 61 20 42 49 54 56 45 43 5f 53 5a 20 6f 66 r a BITVEC_SZ of
11c0: 20 35 31 32 2c 20 74 68 69 73 20 77 6f 75 6c 64 512, this would
11d0: 20 62 65 20 33 34 2c 33 35 39 2c 37 33 39 2e 20 be 34,359,739.
11e0: 2a 2f 0a 20 20 75 6e 69 6f 6e 20 7b 0a 20 20 20 */. union {.
11f0: 20 42 49 54 56 45 43 5f 54 45 4c 45 4d 20 61 42 BITVEC_TELEM aB
1200: 69 74 6d 61 70 5b 42 49 54 56 45 43 5f 4e 45 4c itmap[BITVEC_NEL
1210: 45 4d 5d 3b 20 20 20 20 2f 2a 20 42 69 74 6d 61 EM]; /* Bitma
1220: 70 20 72 65 70 72 65 73 65 6e 74 61 74 69 6f 6e p representation
1230: 20 2a 2f 0a 20 20 20 20 75 33 32 20 61 48 61 73 */. u32 aHas
1240: 68 5b 42 49 54 56 45 43 5f 4e 49 4e 54 5d 3b 20 h[BITVEC_NINT];
1250: 20 20 20 20 20 2f 2a 20 48 61 73 68 20 74 61 62 /* Hash tab
1260: 6c 65 20 72 65 70 72 65 73 65 6e 74 61 74 69 6f le representatio
1270: 6e 20 2a 2f 0a 20 20 20 20 42 69 74 76 65 63 20 n */. Bitvec
1280: 2a 61 70 53 75 62 5b 42 49 54 56 45 43 5f 4e 50 *apSub[BITVEC_NP
1290: 54 52 5d 3b 20 20 2f 2a 20 52 65 63 75 72 73 69 TR]; /* Recursi
12a0: 76 65 20 72 65 70 72 65 73 65 6e 74 61 74 69 6f ve representatio
12b0: 6e 20 2a 2f 0a 20 20 7d 20 75 3b 0a 7d 3b 0a 0a n */. } u;.};..
12c0: 2f 2a 0a 2a 2a 20 43 72 65 61 74 65 20 61 20 6e /*.** Create a n
12d0: 65 77 20 62 69 74 6d 61 70 20 6f 62 6a 65 63 74 ew bitmap object
12e0: 20 61 62 6c 65 20 74 6f 20 68 61 6e 64 6c 65 20 able to handle
12f0: 62 69 74 73 20 62 65 74 77 65 65 6e 20 30 20 61 bits between 0 a
1300: 6e 64 20 69 53 69 7a 65 2c 0a 2a 2a 20 69 6e 63 nd iSize,.** inc
1310: 6c 75 73 69 76 65 2e 20 20 52 65 74 75 72 6e 20 lusive. Return
1320: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 a pointer to the
1330: 20 6e 65 77 20 6f 62 6a 65 63 74 2e 20 20 52 65 new object. Re
1340: 74 75 72 6e 20 4e 55 4c 4c 20 69 66 20 0a 2a 2a turn NULL if .**
1350: 20 6d 61 6c 6c 6f 63 20 66 61 69 6c 73 2e 0a 2a malloc fails..*
1360: 2f 0a 42 69 74 76 65 63 20 2a 73 71 6c 69 74 65 /.Bitvec *sqlite
1370: 33 42 69 74 76 65 63 43 72 65 61 74 65 28 75 33 3BitvecCreate(u3
1380: 32 20 69 53 69 7a 65 29 7b 0a 20 20 42 69 74 76 2 iSize){. Bitv
1390: 65 63 20 2a 70 3b 0a 20 20 61 73 73 65 72 74 28 ec *p;. assert(
13a0: 20 73 69 7a 65 6f 66 28 2a 70 29 3d 3d 42 49 54 sizeof(*p)==BIT
13b0: 56 45 43 5f 53 5a 20 29 3b 0a 20 20 70 20 3d 20 VEC_SZ );. p =
13c0: 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 5a 65 72 sqlite3MallocZer
13d0: 6f 28 20 73 69 7a 65 6f 66 28 2a 70 29 20 29 3b o( sizeof(*p) );
13e0: 0a 20 20 69 66 28 20 70 20 29 7b 0a 20 20 20 20 . if( p ){.
13f0: 70 2d 3e 69 53 69 7a 65 20 3d 20 69 53 69 7a 65 p->iSize = iSize
1400: 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 70 ;. }. return p
1410: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 68 65 63 6b ;.}../*.** Check
1420: 20 74 6f 20 73 65 65 20 69 66 20 74 68 65 20 69 to see if the i
1430: 2d 74 68 20 62 69 74 20 69 73 20 73 65 74 2e 20 -th bit is set.
1440: 20 52 65 74 75 72 6e 20 74 72 75 65 20 6f 72 20 Return true or
1450: 66 61 6c 73 65 2e 0a 2a 2a 20 49 66 20 70 20 69 false..** If p i
1460: 73 20 4e 55 4c 4c 20 28 69 66 20 74 68 65 20 62 s NULL (if the b
1470: 69 74 6d 61 70 20 68 61 73 20 6e 6f 74 20 62 65 itmap has not be
1480: 65 6e 20 63 72 65 61 74 65 64 29 20 6f 72 20 69 en created) or i
1490: 66 0a 2a 2a 20 69 20 69 73 20 6f 75 74 20 6f 66 f.** i is out of
14a0: 20 72 61 6e 67 65 2c 20 74 68 65 6e 20 72 65 74 range, then ret
14b0: 75 72 6e 20 66 61 6c 73 65 2e 0a 2a 2f 0a 69 6e urn false..*/.in
14c0: 74 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 54 t sqlite3BitvecT
14d0: 65 73 74 28 42 69 74 76 65 63 20 2a 70 2c 20 75 est(Bitvec *p, u
14e0: 33 32 20 69 29 7b 0a 20 20 69 66 28 20 70 3d 3d 32 i){. if( p==
14f0: 30 20 29 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 0 ) return 0;.
1500: 69 66 28 20 69 3e 70 2d 3e 69 53 69 7a 65 20 7c if( i>p->iSize |
1510: 7c 20 69 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 | i==0 ) return
1520: 30 3b 0a 20 20 69 2d 2d 3b 0a 20 20 77 68 69 6c 0;. i--;. whil
1530: 65 28 20 70 2d 3e 69 44 69 76 69 73 6f 72 20 29 e( p->iDivisor )
1540: 7b 0a 20 20 20 20 75 33 32 20 62 69 6e 20 3d 20 {. u32 bin =
1550: 69 2f 70 2d 3e 69 44 69 76 69 73 6f 72 3b 0a 20 i/p->iDivisor;.
1560: 20 20 20 69 20 3d 20 69 25 70 2d 3e 69 44 69 76 i = i%p->iDiv
1570: 69 73 6f 72 3b 0a 20 20 20 20 70 20 3d 20 70 2d isor;. p = p-
1580: 3e 75 2e 61 70 53 75 62 5b 62 69 6e 5d 3b 0a 20 >u.apSub[bin];.
1590: 20 20 20 69 66 20 28 21 70 29 20 7b 0a 20 20 20 if (!p) {.
15a0: 20 20 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 20 return 0;.
15b0: 20 7d 0a 20 20 7d 0a 20 20 69 66 28 20 70 2d 3e }. }. if( p->
15c0: 69 53 69 7a 65 3c 3d 42 49 54 56 45 43 5f 4e 42 iSize<=BITVEC_NB
15d0: 49 54 20 29 7b 0a 20 20 20 20 72 65 74 75 72 6e IT ){. return
15e0: 20 28 70 2d 3e 75 2e 61 42 69 74 6d 61 70 5b 69 (p->u.aBitmap[i
15f0: 2f 42 49 54 56 45 43 5f 53 5a 45 4c 45 4d 5d 20 /BITVEC_SZELEM]
1600: 26 20 28 31 3c 3c 28 69 26 28 42 49 54 56 45 43 & (1<<(i&(BITVEC
1610: 5f 53 5a 45 4c 45 4d 2d 31 29 29 29 29 21 3d 30 _SZELEM-1))))!=0
1620: 3b 0a 20 20 7d 20 65 6c 73 65 7b 0a 20 20 20 20 ;. } else{.
1630: 75 33 32 20 68 20 3d 20 42 49 54 56 45 43 5f 48 u32 h = BITVEC_H
1640: 41 53 48 28 69 2b 2b 29 3b 0a 20 20 20 20 77 68 ASH(i++);. wh
1650: 69 6c 65 28 20 70 2d 3e 75 2e 61 48 61 73 68 5b ile( p->u.aHash[
1660: 68 5d 20 29 7b 0a 20 20 20 20 20 20 69 66 28 20 h] ){. if(
1670: 70 2d 3e 75 2e 61 48 61 73 68 5b 68 5d 3d 3d 69 p->u.aHash[h]==i
1680: 20 29 20 72 65 74 75 72 6e 20 31 3b 0a 20 20 20 ) return 1;.
1690: 20 20 20 68 2b 2b 3b 0a 20 20 20 20 20 20 69 66 h++;. if
16a0: 28 20 68 3e 3d 42 49 54 56 45 43 5f 4e 49 4e 54 ( h>=BITVEC_NINT
16b0: 20 29 20 68 20 3d 20 30 3b 0a 20 20 20 20 7d 0a ) h = 0;. }.
16c0: 20 20 20 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 return 0;.
16d0: 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 53 65 74 20 74 }.}../*.** Set t
16e0: 68 65 20 69 2d 74 68 20 62 69 74 2e 20 20 52 65 he i-th bit. Re
16f0: 74 75 72 6e 20 30 20 6f 6e 20 73 75 63 63 65 73 turn 0 on succes
1700: 73 20 61 6e 64 20 61 6e 20 65 72 72 6f 72 20 63 s and an error c
1710: 6f 64 65 20 69 66 0a 2a 2a 20 61 6e 79 74 68 69 ode if.** anythi
1720: 6e 67 20 67 6f 65 73 20 77 72 6f 6e 67 2e 0a 2a ng goes wrong..*
1730: 2a 0a 2a 2a 20 54 68 69 73 20 72 6f 75 74 69 6e *.** This routin
1740: 65 20 6d 69 67 68 74 20 63 61 75 73 65 20 73 75 e might cause su
1750: 62 2d 62 69 74 6d 61 70 73 20 74 6f 20 62 65 20 b-bitmaps to be
1760: 61 6c 6c 6f 63 61 74 65 64 2e 20 20 46 61 69 6c allocated. Fail
1770: 69 6e 67 0a 2a 2a 20 74 6f 20 67 65 74 20 74 68 ing.** to get th
1780: 65 20 6d 65 6d 6f 72 79 20 6e 65 65 64 65 64 20 e memory needed
1790: 74 6f 20 68 6f 6c 64 20 74 68 65 20 73 75 62 2d to hold the sub-
17a0: 62 69 74 6d 61 70 20 69 73 20 74 68 65 20 6f 6e bitmap is the on
17b0: 6c 79 0a 2a 2a 20 74 68 61 74 20 63 61 6e 20 67 ly.** that can g
17c0: 6f 20 77 72 6f 6e 67 20 77 69 74 68 20 61 6e 20 o wrong with an
17d0: 69 6e 73 65 72 74 2c 20 61 73 73 75 6d 69 6e 67 insert, assuming
17e0: 20 70 20 61 6e 64 20 69 20 61 72 65 20 76 61 6c p and i are val
17f0: 69 64 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 63 61 id..**.** The ca
1800: 6c 6c 69 6e 67 20 66 75 6e 63 74 69 6f 6e 20 6d lling function m
1810: 75 73 74 20 65 6e 73 75 72 65 20 74 68 61 74 20 ust ensure that
1820: 70 20 69 73 20 61 20 76 61 6c 69 64 20 42 69 74 p is a valid Bit
1830: 76 65 63 20 6f 62 6a 65 63 74 0a 2a 2a 20 61 6e vec object.** an
1840: 64 20 74 68 61 74 20 74 68 65 20 76 61 6c 75 65 d that the value
1850: 20 66 6f 72 20 22 69 22 20 69 73 20 77 69 74 68 for "i" is with
1860: 69 6e 20 72 61 6e 67 65 20 6f 66 20 74 68 65 20 in range of the
1870: 42 69 74 76 65 63 20 6f 62 6a 65 63 74 2e 0a 2a Bitvec object..*
1880: 2a 20 4f 74 68 65 72 77 69 73 65 20 74 68 65 20 * Otherwise the
1890: 62 65 68 61 76 69 6f 72 20 69 73 20 75 6e 64 65 behavior is unde
18a0: 66 69 6e 65 64 2e 0a 2a 2f 0a 69 6e 74 20 73 71 fined..*/.int sq
18b0: 6c 69 74 65 33 42 69 74 76 65 63 53 65 74 28 42 lite3BitvecSet(B
18c0: 69 74 76 65 63 20 2a 70 2c 20 75 33 32 20 69 29 itvec *p, u32 i)
18d0: 7b 0a 20 20 75 33 32 20 68 3b 0a 20 20 61 73 73 {. u32 h;. ass
18e0: 65 72 74 28 20 70 21 3d 30 20 29 3b 0a 20 20 61 ert( p!=0 );. a
18f0: 73 73 65 72 74 28 20 69 3e 30 20 29 3b 0a 20 20 ssert( i>0 );.
1900: 61 73 73 65 72 74 28 20 69 3c 3d 70 2d 3e 69 53 assert( i<=p->iS
1910: 69 7a 65 20 29 3b 0a 20 20 69 2d 2d 3b 0a 20 20 ize );. i--;.
1920: 77 68 69 6c 65 28 28 70 2d 3e 69 53 69 7a 65 20 while((p->iSize
1930: 3e 20 42 49 54 56 45 43 5f 4e 42 49 54 29 20 26 > BITVEC_NBIT) &
1940: 26 20 70 2d 3e 69 44 69 76 69 73 6f 72 29 20 7b & p->iDivisor) {
1950: 0a 20 20 20 20 75 33 32 20 62 69 6e 20 3d 20 69 . u32 bin = i
1960: 2f 70 2d 3e 69 44 69 76 69 73 6f 72 3b 0a 20 20 /p->iDivisor;.
1970: 20 20 69 20 3d 20 69 25 70 2d 3e 69 44 69 76 69 i = i%p->iDivi
1980: 73 6f 72 3b 0a 20 20 20 20 69 66 28 20 70 2d 3e sor;. if( p->
1990: 75 2e 61 70 53 75 62 5b 62 69 6e 5d 3d 3d 30 20 u.apSub[bin]==0
19a0: 29 7b 0a 20 20 20 20 20 20 70 2d 3e 75 2e 61 70 ){. p->u.ap
19b0: 53 75 62 5b 62 69 6e 5d 20 3d 20 73 71 6c 69 74 Sub[bin] = sqlit
19c0: 65 33 42 69 74 76 65 63 43 72 65 61 74 65 28 20 e3BitvecCreate(
19d0: 70 2d 3e 69 44 69 76 69 73 6f 72 20 29 3b 0a 20 p->iDivisor );.
19e0: 20 20 20 20 20 69 66 28 20 70 2d 3e 75 2e 61 70 if( p->u.ap
19f0: 53 75 62 5b 62 69 6e 5d 3d 3d 30 20 29 20 72 65 Sub[bin]==0 ) re
1a00: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 turn SQLITE_NOME
1a10: 4d 3b 0a 20 20 20 20 7d 0a 20 20 20 20 70 20 3d M;. }. p =
1a20: 20 70 2d 3e 75 2e 61 70 53 75 62 5b 62 69 6e 5d p->u.apSub[bin]
1a30: 3b 0a 20 20 7d 0a 20 20 69 66 28 20 70 2d 3e 69 ;. }. if( p->i
1a40: 53 69 7a 65 3c 3d 42 49 54 56 45 43 5f 4e 42 49 Size<=BITVEC_NBI
1a50: 54 20 29 7b 0a 20 20 20 20 70 2d 3e 75 2e 61 42 T ){. p->u.aB
1a60: 69 74 6d 61 70 5b 69 2f 42 49 54 56 45 43 5f 53 itmap[i/BITVEC_S
1a70: 5a 45 4c 45 4d 5d 20 7c 3d 20 31 20 3c 3c 20 28 ZELEM] |= 1 << (
1a80: 69 26 28 42 49 54 56 45 43 5f 53 5a 45 4c 45 4d i&(BITVEC_SZELEM
1a90: 2d 31 29 29 3b 0a 20 20 20 20 72 65 74 75 72 6e -1));. return
1aa0: 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 20 20 7d 0a SQLITE_OK;. }.
1ab0: 20 20 68 20 3d 20 42 49 54 56 45 43 5f 48 41 53 h = BITVEC_HAS
1ac0: 48 28 69 2b 2b 29 3b 0a 20 20 2f 2a 20 69 66 20 H(i++);. /* if
1ad0: 74 68 65 72 65 20 77 61 73 6e 27 74 20 61 20 68 there wasn't a h
1ae0: 61 73 68 20 63 6f 6c 6c 69 73 69 6f 6e 2c 20 61 ash collision, a
1af0: 6e 64 20 74 68 69 73 20 64 6f 65 73 6e 27 74 20 nd this doesn't
1b00: 2a 2f 0a 20 20 2f 2a 20 63 6f 6d 70 6c 65 74 65 */. /* complete
1b10: 6c 79 20 66 69 6c 6c 20 74 68 65 20 68 61 73 68 ly fill the hash
1b20: 2c 20 74 68 65 6e 20 6a 75 73 74 20 61 64 64 20 , then just add
1b30: 69 74 20 77 69 74 68 6f 75 74 20 2a 2f 0a 20 20 it without */.
1b40: 2f 2a 20 77 6f 72 72 69 6e 67 20 61 62 6f 75 74 /* worring about
1b50: 20 73 75 62 2d 64 69 76 69 64 69 6e 67 20 61 6e sub-dividing an
1b60: 64 20 72 65 2d 68 61 73 68 69 6e 67 2e 20 2a 2f d re-hashing. */
1b70: 0a 20 20 69 66 28 20 21 70 2d 3e 75 2e 61 48 61 . if( !p->u.aHa
1b80: 73 68 5b 68 5d 20 29 7b 0a 20 20 20 20 69 66 20 sh[h] ){. if
1b90: 28 70 2d 3e 6e 53 65 74 3c 28 42 49 54 56 45 43 (p->nSet<(BITVEC
1ba0: 5f 4e 49 4e 54 2d 31 29 29 20 7b 0a 20 20 20 20 _NINT-1)) {.
1bb0: 20 20 67 6f 74 6f 20 62 69 74 76 65 63 5f 73 65 goto bitvec_se
1bc0: 74 5f 65 6e 64 3b 0a 20 20 20 20 7d 20 65 6c 73 t_end;. } els
1bd0: 65 20 7b 0a 20 20 20 20 20 20 67 6f 74 6f 20 62 e {. goto b
1be0: 69 74 76 65 63 5f 73 65 74 5f 72 65 68 61 73 68 itvec_set_rehash
1bf0: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 2f 2a ;. }. }. /*
1c00: 20 74 68 65 72 65 20 77 61 73 20 61 20 63 6f 6c there was a col
1c10: 6c 69 73 69 6f 6e 2c 20 63 68 65 63 6b 20 74 6f lision, check to
1c20: 20 73 65 65 20 69 66 20 69 74 27 73 20 61 6c 72 see if it's alr
1c30: 65 61 64 79 20 2a 2f 0a 20 20 2f 2a 20 69 6e 20 eady */. /* in
1c40: 68 61 73 68 2c 20 69 66 20 6e 6f 74 2c 20 74 72 hash, if not, tr
1c50: 79 20 74 6f 20 66 69 6e 64 20 61 20 73 70 6f 74 y to find a spot
1c60: 20 66 6f 72 20 69 74 20 2a 2f 0a 20 20 64 6f 20 for it */. do
1c70: 7b 0a 20 20 20 20 69 66 28 20 70 2d 3e 75 2e 61 {. if( p->u.a
1c80: 48 61 73 68 5b 68 5d 3d 3d 69 20 29 20 72 65 74 Hash[h]==i ) ret
1c90: 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 20 urn SQLITE_OK;.
1ca0: 20 20 20 68 2b 2b 3b 0a 20 20 20 20 69 66 28 20 h++;. if(
1cb0: 68 3e 3d 42 49 54 56 45 43 5f 4e 49 4e 54 20 29 h>=BITVEC_NINT )
1cc0: 20 68 20 3d 20 30 3b 0a 20 20 7d 20 77 68 69 6c h = 0;. } whil
1cd0: 65 28 20 70 2d 3e 75 2e 61 48 61 73 68 5b 68 5d e( p->u.aHash[h]
1ce0: 20 29 3b 0a 20 20 2f 2a 20 77 65 20 64 69 64 6e );. /* we didn
1cf0: 27 74 20 66 69 6e 64 20 69 74 20 69 6e 20 74 68 't find it in th
1d00: 65 20 68 61 73 68 2e 20 20 68 20 70 6f 69 6e 74 e hash. h point
1d10: 73 20 74 6f 20 74 68 65 20 66 69 72 73 74 20 2a s to the first *
1d20: 2f 0a 20 20 2f 2a 20 61 76 61 69 6c 61 62 6c 65 /. /* available
1d30: 20 66 72 65 65 20 73 70 6f 74 2e 20 63 68 65 63 free spot. chec
1d40: 6b 20 74 6f 20 73 65 65 20 69 66 20 74 68 69 73 k to see if this
1d50: 20 69 73 20 67 6f 69 6e 67 20 74 6f 20 2a 2f 0a is going to */.
1d60: 20 20 2f 2a 20 6d 61 6b 65 20 6f 75 72 20 68 61 /* make our ha
1d70: 73 68 20 74 6f 6f 20 22 66 75 6c 6c 22 2e 20 20 sh too "full".
1d80: 2a 2f 0a 62 69 74 76 65 63 5f 73 65 74 5f 72 65 */.bitvec_set_re
1d90: 68 61 73 68 3a 0a 20 20 69 66 28 20 70 2d 3e 6e hash:. if( p->n
1da0: 53 65 74 3e 3d 42 49 54 56 45 43 5f 4d 58 48 41 Set>=BITVEC_MXHA
1db0: 53 48 20 29 7b 0a 20 20 20 20 75 6e 73 69 67 6e SH ){. unsign
1dc0: 65 64 20 69 6e 74 20 6a 3b 0a 20 20 20 20 69 6e ed int j;. in
1dd0: 74 20 72 63 3b 0a 20 20 20 20 75 33 32 20 2a 61 t rc;. u32 *a
1de0: 69 56 61 6c 75 65 73 20 3d 20 73 71 6c 69 74 65 iValues = sqlite
1df0: 33 53 74 61 63 6b 41 6c 6c 6f 63 52 61 77 28 30 3StackAllocRaw(0
1e00: 2c 20 73 69 7a 65 6f 66 28 70 2d 3e 75 2e 61 48 , sizeof(p->u.aH
1e10: 61 73 68 29 29 3b 0a 20 20 20 20 69 66 28 20 61 ash));. if( a
1e20: 69 56 61 6c 75 65 73 3d 3d 30 20 29 7b 0a 20 20 iValues==0 ){.
1e30: 20 20 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 return SQLIT
1e40: 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 7d 65 6c E_NOMEM;. }el
1e50: 73 65 7b 0a 20 20 20 20 20 20 6d 65 6d 63 70 79 se{. memcpy
1e60: 28 61 69 56 61 6c 75 65 73 2c 20 70 2d 3e 75 2e (aiValues, p->u.
1e70: 61 48 61 73 68 2c 20 73 69 7a 65 6f 66 28 70 2d aHash, sizeof(p-
1e80: 3e 75 2e 61 48 61 73 68 29 29 3b 0a 20 20 20 20 >u.aHash));.
1e90: 20 20 6d 65 6d 73 65 74 28 70 2d 3e 75 2e 61 70 memset(p->u.ap
1ea0: 53 75 62 2c 20 30 2c 20 73 69 7a 65 6f 66 28 70 Sub, 0, sizeof(p
1eb0: 2d 3e 75 2e 61 70 53 75 62 29 29 3b 0a 20 20 20 ->u.apSub));.
1ec0: 20 20 20 70 2d 3e 69 44 69 76 69 73 6f 72 20 3d p->iDivisor =
1ed0: 20 28 70 2d 3e 69 53 69 7a 65 20 2b 20 42 49 54 (p->iSize + BIT
1ee0: 56 45 43 5f 4e 50 54 52 20 2d 20 31 29 2f 42 49 VEC_NPTR - 1)/BI
1ef0: 54 56 45 43 5f 4e 50 54 52 3b 0a 20 20 20 20 20 TVEC_NPTR;.
1f00: 20 72 63 20 3d 20 73 71 6c 69 74 65 33 42 69 74 rc = sqlite3Bit
1f10: 76 65 63 53 65 74 28 70 2c 20 69 29 3b 0a 20 20 vecSet(p, i);.
1f20: 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a 3c 42 for(j=0; j<B
1f30: 49 54 56 45 43 5f 4e 49 4e 54 3b 20 6a 2b 2b 29 ITVEC_NINT; j++)
1f40: 7b 0a 20 20 20 20 20 20 20 20 69 66 28 20 61 69 {. if( ai
1f50: 56 61 6c 75 65 73 5b 6a 5d 20 29 20 72 63 20 7c Values[j] ) rc |
1f60: 3d 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 53 = sqlite3BitvecS
1f70: 65 74 28 70 2c 20 61 69 56 61 6c 75 65 73 5b 6a et(p, aiValues[j
1f80: 5d 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 ]);. }.
1f90: 20 20 73 71 6c 69 74 65 33 53 74 61 63 6b 46 72 sqlite3StackFr
1fa0: 65 65 28 30 2c 20 61 69 56 61 6c 75 65 73 29 3b ee(0, aiValues);
1fb0: 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 72 63 . return rc
1fc0: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 62 69 74 76 ;. }. }.bitv
1fd0: 65 63 5f 73 65 74 5f 65 6e 64 3a 0a 20 20 70 2d ec_set_end:. p-
1fe0: 3e 6e 53 65 74 2b 2b 3b 0a 20 20 70 2d 3e 75 2e >nSet++;. p->u.
1ff0: 61 48 61 73 68 5b 68 5d 20 3d 20 69 3b 0a 20 20 aHash[h] = i;.
2000: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b return SQLITE_OK
2010: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 6c 65 61 72 ;.}../*.** Clear
2020: 20 74 68 65 20 69 2d 74 68 20 62 69 74 2e 0a 2a the i-th bit..*
2030: 2a 0a 2a 2a 20 70 42 75 66 20 6d 75 73 74 20 62 *.** pBuf must b
2040: 65 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 e a pointer to a
2050: 74 20 6c 65 61 73 74 20 42 49 54 56 45 43 5f 53 t least BITVEC_S
2060: 5a 20 62 79 74 65 73 20 6f 66 20 74 65 6d 70 6f Z bytes of tempo
2070: 72 61 72 79 20 73 74 6f 72 61 67 65 0a 2a 2a 20 rary storage.**
2080: 74 68 61 74 20 42 69 74 76 65 63 43 6c 65 61 72 that BitvecClear
2090: 20 63 61 6e 20 75 73 65 20 74 6f 20 72 65 62 75 can use to rebu
20a0: 69 6c 74 20 69 74 73 20 68 61 73 68 20 74 61 62 ilt its hash tab
20b0: 6c 65 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 le..*/.void sqli
20c0: 74 65 33 42 69 74 76 65 63 43 6c 65 61 72 28 42 te3BitvecClear(B
20d0: 69 74 76 65 63 20 2a 70 2c 20 75 33 32 20 69 2c itvec *p, u32 i,
20e0: 20 76 6f 69 64 20 2a 70 42 75 66 29 7b 0a 20 20 void *pBuf){.
20f0: 61 73 73 65 72 74 28 20 70 21 3d 30 20 29 3b 0a assert( p!=0 );.
2100: 20 20 61 73 73 65 72 74 28 20 69 3e 30 20 29 3b assert( i>0 );
2110: 0a 20 20 69 2d 2d 3b 0a 20 20 77 68 69 6c 65 28 . i--;. while(
2120: 20 70 2d 3e 69 44 69 76 69 73 6f 72 20 29 7b 0a p->iDivisor ){.
2130: 20 20 20 20 75 33 32 20 62 69 6e 20 3d 20 69 2f u32 bin = i/
2140: 70 2d 3e 69 44 69 76 69 73 6f 72 3b 0a 20 20 20 p->iDivisor;.
2150: 20 69 20 3d 20 69 25 70 2d 3e 69 44 69 76 69 73 i = i%p->iDivis
2160: 6f 72 3b 0a 20 20 20 20 70 20 3d 20 70 2d 3e 75 or;. p = p->u
2170: 2e 61 70 53 75 62 5b 62 69 6e 5d 3b 0a 20 20 20 .apSub[bin];.
2180: 20 69 66 20 28 21 70 29 20 7b 0a 20 20 20 20 20 if (!p) {.
2190: 20 72 65 74 75 72 6e 3b 0a 20 20 20 20 7d 0a 20 return;. }.
21a0: 20 7d 0a 20 20 69 66 28 20 70 2d 3e 69 53 69 7a }. if( p->iSiz
21b0: 65 3c 3d 42 49 54 56 45 43 5f 4e 42 49 54 20 29 e<=BITVEC_NBIT )
21c0: 7b 0a 20 20 20 20 70 2d 3e 75 2e 61 42 69 74 6d {. p->u.aBitm
21d0: 61 70 5b 69 2f 42 49 54 56 45 43 5f 53 5a 45 4c ap[i/BITVEC_SZEL
21e0: 45 4d 5d 20 26 3d 20 7e 28 31 20 3c 3c 20 28 69 EM] &= ~(1 << (i
21f0: 26 28 42 49 54 56 45 43 5f 53 5a 45 4c 45 4d 2d &(BITVEC_SZELEM-
2200: 31 29 29 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 1)));. }else{.
2210: 20 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 unsigned int
2220: 6a 3b 0a 20 20 20 20 75 33 32 20 2a 61 69 56 61 j;. u32 *aiVa
2230: 6c 75 65 73 20 3d 20 70 42 75 66 3b 0a 20 20 20 lues = pBuf;.
2240: 20 6d 65 6d 63 70 79 28 61 69 56 61 6c 75 65 73 memcpy(aiValues
2250: 2c 20 70 2d 3e 75 2e 61 48 61 73 68 2c 20 73 69 , p->u.aHash, si
2260: 7a 65 6f 66 28 70 2d 3e 75 2e 61 48 61 73 68 29 zeof(p->u.aHash)
2270: 29 3b 0a 20 20 20 20 6d 65 6d 73 65 74 28 70 2d );. memset(p-
2280: 3e 75 2e 61 48 61 73 68 2c 20 30 2c 20 73 69 7a >u.aHash, 0, siz
2290: 65 6f 66 28 70 2d 3e 75 2e 61 48 61 73 68 29 29 eof(p->u.aHash))
22a0: 3b 0a 20 20 20 20 70 2d 3e 6e 53 65 74 20 3d 20 ;. p->nSet =
22b0: 30 3b 0a 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 0;. for(j=0;
22c0: 6a 3c 42 49 54 56 45 43 5f 4e 49 4e 54 3b 20 6a j<BITVEC_NINT; j
22d0: 2b 2b 29 7b 0a 20 20 20 20 20 20 69 66 28 20 61 ++){. if( a
22e0: 69 56 61 6c 75 65 73 5b 6a 5d 20 26 26 20 61 69 iValues[j] && ai
22f0: 56 61 6c 75 65 73 5b 6a 5d 21 3d 28 69 2b 31 29 Values[j]!=(i+1)
2300: 20 29 7b 0a 20 20 20 20 20 20 20 20 75 33 32 20 ){. u32
2310: 68 20 3d 20 42 49 54 56 45 43 5f 48 41 53 48 28 h = BITVEC_HASH(
2320: 61 69 56 61 6c 75 65 73 5b 6a 5d 2d 31 29 3b 0a aiValues[j]-1);.
2330: 20 20 20 20 20 20 20 20 70 2d 3e 6e 53 65 74 2b p->nSet+
2340: 2b 3b 0a 20 20 20 20 20 20 20 20 77 68 69 6c 65 +;. while
2350: 28 20 70 2d 3e 75 2e 61 48 61 73 68 5b 68 5d 20 ( p->u.aHash[h]
2360: 29 7b 0a 20 20 20 20 20 20 20 20 20 20 68 2b 2b ){. h++
2370: 3b 0a 20 20 20 20 20 20 20 20 20 20 69 66 28 20 ;. if(
2380: 68 3e 3d 42 49 54 56 45 43 5f 4e 49 4e 54 20 29 h>=BITVEC_NINT )
2390: 20 68 20 3d 20 30 3b 0a 20 20 20 20 20 20 20 20 h = 0;.
23a0: 7d 0a 20 20 20 20 20 20 20 20 70 2d 3e 75 2e 61 }. p->u.a
23b0: 48 61 73 68 5b 68 5d 20 3d 20 61 69 56 61 6c 75 Hash[h] = aiValu
23c0: 65 73 5b 6a 5d 3b 0a 20 20 20 20 20 20 7d 0a 20 es[j];. }.
23d0: 20 20 20 7d 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a }. }.}../*.*
23e0: 2a 20 44 65 73 74 72 6f 79 20 61 20 62 69 74 6d * Destroy a bitm
23f0: 61 70 20 6f 62 6a 65 63 74 2e 20 20 52 65 63 6c ap object. Recl
2400: 61 69 6d 20 61 6c 6c 20 6d 65 6d 6f 72 79 20 75 aim all memory u
2410: 73 65 64 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c sed..*/.void sql
2420: 69 74 65 33 42 69 74 76 65 63 44 65 73 74 72 6f ite3BitvecDestro
2430: 79 28 42 69 74 76 65 63 20 2a 70 29 7b 0a 20 20 y(Bitvec *p){.
2440: 69 66 28 20 70 3d 3d 30 20 29 20 72 65 74 75 72 if( p==0 ) retur
2450: 6e 3b 0a 20 20 69 66 28 20 70 2d 3e 69 44 69 76 n;. if( p->iDiv
2460: 69 73 6f 72 20 29 7b 0a 20 20 20 20 75 6e 73 69 isor ){. unsi
2470: 67 6e 65 64 20 69 6e 74 20 69 3b 0a 20 20 20 20 gned int i;.
2480: 66 6f 72 28 69 3d 30 3b 20 69 3c 42 49 54 56 45 for(i=0; i<BITVE
2490: 43 5f 4e 50 54 52 3b 20 69 2b 2b 29 7b 0a 20 20 C_NPTR; i++){.
24a0: 20 20 20 20 73 71 6c 69 74 65 33 42 69 74 76 65 sqlite3Bitve
24b0: 63 44 65 73 74 72 6f 79 28 70 2d 3e 75 2e 61 70 cDestroy(p->u.ap
24c0: 53 75 62 5b 69 5d 29 3b 0a 20 20 20 20 7d 0a 20 Sub[i]);. }.
24d0: 20 7d 0a 20 20 73 71 6c 69 74 65 33 5f 66 72 65 }. sqlite3_fre
24e0: 65 28 70 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 e(p);.}../*.** R
24f0: 65 74 75 72 6e 20 74 68 65 20 76 61 6c 75 65 20 eturn the value
2500: 6f 66 20 74 68 65 20 69 53 69 7a 65 20 70 61 72 of the iSize par
2510: 61 6d 65 74 65 72 20 73 70 65 63 69 66 69 65 64 ameter specified
2520: 20 77 68 65 6e 20 42 69 74 76 65 63 20 2a 70 0a when Bitvec *p.
2530: 2a 2a 20 77 61 73 20 63 72 65 61 74 65 64 2e 0a ** was created..
2540: 2a 2f 0a 75 33 32 20 73 71 6c 69 74 65 33 42 69 */.u32 sqlite3Bi
2550: 74 76 65 63 53 69 7a 65 28 42 69 74 76 65 63 20 tvecSize(Bitvec
2560: 2a 70 29 7b 0a 20 20 72 65 74 75 72 6e 20 70 2d *p){. return p-
2570: 3e 69 53 69 7a 65 3b 0a 7d 0a 0a 23 69 66 6e 64 >iSize;.}..#ifnd
2580: 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 42 ef SQLITE_OMIT_B
2590: 55 49 4c 54 49 4e 5f 54 45 53 54 0a 2f 2a 0a 2a UILTIN_TEST./*.*
25a0: 2a 20 4c 65 74 20 56 5b 5d 20 62 65 20 61 6e 20 * Let V[] be an
25b0: 61 72 72 61 79 20 6f 66 20 75 6e 73 69 67 6e 65 array of unsigne
25c0: 64 20 63 68 61 72 61 63 74 65 72 73 20 73 75 66 d characters suf
25d0: 66 69 63 69 65 6e 74 20 74 6f 20 68 6f 6c 64 0a ficient to hold.
25e0: 2a 2a 20 75 70 20 74 6f 20 4e 20 62 69 74 73 2e ** up to N bits.
25f0: 20 20 4c 65 74 20 49 20 62 65 20 61 6e 20 69 6e Let I be an in
2600: 74 65 67 65 72 20 62 65 74 77 65 65 6e 20 30 20 teger between 0
2610: 61 6e 64 20 4e 2e 20 20 30 3c 3d 49 3c 4e 2e 0a and N. 0<=I<N..
2620: 2a 2a 20 54 68 65 6e 20 74 68 65 20 66 6f 6c 6c ** Then the foll
2630: 6f 77 69 6e 67 20 6d 61 63 72 6f 73 20 63 61 6e owing macros can
2640: 20 62 65 20 75 73 65 64 20 74 6f 20 73 65 74 2c be used to set,
2650: 20 63 6c 65 61 72 2c 20 6f 72 20 74 65 73 74 0a clear, or test.
2660: 2a 2a 20 69 6e 64 69 76 69 64 75 61 6c 20 62 69 ** individual bi
2670: 74 73 20 77 69 74 68 69 6e 20 56 2e 0a 2a 2f 0a ts within V..*/.
2680: 23 64 65 66 69 6e 65 20 53 45 54 42 49 54 28 56 #define SETBIT(V
2690: 2c 49 29 20 20 20 20 20 20 56 5b 49 3e 3e 33 5d ,I) V[I>>3]
26a0: 20 7c 3d 20 28 31 3c 3c 28 49 26 37 29 29 0a 23 |= (1<<(I&7)).#
26b0: 64 65 66 69 6e 65 20 43 4c 45 41 52 42 49 54 28 define CLEARBIT(
26c0: 56 2c 49 29 20 20 20 20 56 5b 49 3e 3e 33 5d 20 V,I) V[I>>3]
26d0: 26 3d 20 7e 28 31 3c 3c 28 49 26 37 29 29 0a 23 &= ~(1<<(I&7)).#
26e0: 64 65 66 69 6e 65 20 54 45 53 54 42 49 54 28 56 define TESTBIT(V
26f0: 2c 49 29 20 20 20 20 20 28 56 5b 49 3e 3e 33 5d ,I) (V[I>>3]
2700: 26 28 31 3c 3c 28 49 26 37 29 29 29 21 3d 30 0a &(1<<(I&7)))!=0.
2710: 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20 72 6f 75 74 ./*.** This rout
2720: 69 6e 65 20 72 75 6e 73 20 61 6e 20 65 78 74 65 ine runs an exte
2730: 6e 73 69 76 65 20 74 65 73 74 20 6f 66 20 74 68 nsive test of th
2740: 65 20 42 69 74 76 65 63 20 63 6f 64 65 2e 0a 2a e Bitvec code..*
2750: 2a 0a 2a 2a 20 54 68 65 20 69 6e 70 75 74 20 69 *.** The input i
2760: 73 20 61 6e 20 61 72 72 61 79 20 6f 66 20 69 6e s an array of in
2770: 74 65 67 65 72 73 20 74 68 61 74 20 61 63 74 73 tegers that acts
2780: 20 61 73 20 61 20 70 72 6f 67 72 61 6d 0a 2a 2a as a program.**
2790: 20 74 6f 20 74 65 73 74 20 74 68 65 20 42 69 74 to test the Bit
27a0: 76 65 63 2e 20 20 54 68 65 20 69 6e 74 65 67 65 vec. The intege
27b0: 72 73 20 61 72 65 20 6f 70 63 6f 64 65 73 20 66 rs are opcodes f
27c0: 6f 6c 6c 6f 77 65 64 0a 2a 2a 20 62 79 20 30 2c ollowed.** by 0,
27d0: 20 31 2c 20 6f 72 20 33 20 6f 70 65 72 61 6e 64 1, or 3 operand
27e0: 73 2c 20 64 65 70 65 6e 64 69 6e 67 20 6f 6e 20 s, depending on
27f0: 74 68 65 20 6f 70 63 6f 64 65 2e 20 20 41 6e 6f the opcode. Ano
2800: 74 68 65 72 0a 2a 2a 20 6f 70 63 6f 64 65 20 66 ther.** opcode f
2810: 6f 6c 6c 6f 77 73 20 69 6d 6d 65 64 69 61 74 65 ollows immediate
2820: 6c 79 20 61 66 74 65 72 20 74 68 65 20 6c 61 73 ly after the las
2830: 74 20 6f 70 65 72 61 6e 64 2e 0a 2a 2a 0a 2a 2a t operand..**.**
2840: 20 54 68 65 72 65 20 61 72 65 20 36 20 6f 70 63 There are 6 opc
2850: 6f 64 65 73 20 6e 75 6d 62 65 72 65 64 20 66 72 odes numbered fr
2860: 6f 6d 20 30 20 74 68 72 6f 75 67 68 20 35 2e 20 om 0 through 5.
2870: 20 30 20 69 73 20 74 68 65 0a 2a 2a 20 22 68 61 0 is the.** "ha
2880: 6c 74 22 20 6f 70 63 6f 64 65 20 61 6e 64 20 63 lt" opcode and c
2890: 61 75 73 65 73 20 74 68 65 20 74 65 73 74 20 74 auses the test t
28a0: 6f 20 65 6e 64 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 o end..**.**
28b0: 30 20 20 20 20 20 20 20 20 20 20 48 61 6c 74 20 0 Halt
28c0: 61 6e 64 20 72 65 74 75 72 6e 20 74 68 65 20 6e and return the n
28d0: 75 6d 62 65 72 20 6f 66 20 65 72 72 6f 72 73 0a umber of errors.
28e0: 2a 2a 20 20 20 20 31 20 4e 20 53 20 58 20 20 20 ** 1 N S X
28f0: 20 53 65 74 20 4e 20 62 69 74 73 20 62 65 67 69 Set N bits begi
2900: 6e 6e 69 6e 67 20 77 69 74 68 20 53 20 61 6e 64 nning with S and
2910: 20 69 6e 63 72 65 6d 65 6e 74 69 6e 67 20 62 79 incrementing by
2920: 20 58 0a 2a 2a 20 20 20 20 32 20 4e 20 53 20 58 X.** 2 N S X
2930: 20 20 20 20 43 6c 65 61 72 20 4e 20 62 69 74 73 Clear N bits
2940: 20 62 65 67 69 6e 6e 69 6e 67 20 77 69 74 68 20 beginning with
2950: 53 20 61 6e 64 20 69 6e 63 72 65 6d 65 6e 74 69 S and incrementi
2960: 6e 67 20 62 79 20 58 0a 2a 2a 20 20 20 20 33 20 ng by X.** 3
2970: 4e 20 20 20 20 20 20 20 20 53 65 74 20 4e 20 72 N Set N r
2980: 61 6e 64 6f 6d 6c 79 20 63 68 6f 73 65 6e 20 62 andomly chosen b
2990: 69 74 73 0a 2a 2a 20 20 20 20 34 20 4e 20 20 20 its.** 4 N
29a0: 20 20 20 20 20 43 6c 65 61 72 20 4e 20 72 61 6e Clear N ran
29b0: 64 6f 6d 6c 79 20 63 68 6f 73 65 6e 20 62 69 74 domly chosen bit
29c0: 73 0a 2a 2a 20 20 20 20 35 20 4e 20 53 20 58 20 s.** 5 N S X
29d0: 20 20 20 53 65 74 20 4e 20 62 69 74 73 20 66 72 Set N bits fr
29e0: 6f 6d 20 53 20 69 6e 63 72 65 6d 65 6e 74 20 58 om S increment X
29f0: 20 69 6e 20 61 72 72 61 79 20 6f 6e 6c 79 2c 20 in array only,
2a00: 6e 6f 74 20 69 6e 20 62 69 74 76 65 63 0a 2a 2a not in bitvec.**
2a10: 0a 2a 2a 20 54 68 65 20 6f 70 63 6f 64 65 73 20 .** The opcodes
2a20: 31 20 74 68 72 6f 75 67 68 20 34 20 70 65 72 66 1 through 4 perf
2a30: 6f 72 6d 20 73 65 74 20 61 6e 64 20 63 6c 65 61 orm set and clea
2a40: 72 20 6f 70 65 72 61 74 69 6f 6e 73 20 61 72 65 r operations are
2a50: 20 70 65 72 66 6f 72 6d 65 64 0a 2a 2a 20 6f 6e performed.** on
2a60: 20 62 6f 74 68 20 61 20 42 69 74 76 65 63 20 6f both a Bitvec o
2a70: 62 6a 65 63 74 20 61 6e 64 20 6f 6e 20 61 20 6c bject and on a l
2a80: 69 6e 65 61 72 20 61 72 72 61 79 20 6f 66 20 62 inear array of b
2a90: 69 74 73 20 6f 62 74 61 69 6e 65 64 20 66 72 6f its obtained fro
2aa0: 6d 20 6d 61 6c 6c 6f 63 2e 0a 2a 2a 20 4f 70 63 m malloc..** Opc
2ab0: 6f 64 65 20 35 20 77 6f 72 6b 73 20 6f 6e 20 74 ode 5 works on t
2ac0: 68 65 20 6c 69 6e 65 61 72 20 61 72 72 61 79 20 he linear array
2ad0: 6f 6e 6c 79 2c 20 6e 6f 74 20 6f 6e 20 74 68 65 only, not on the
2ae0: 20 42 69 74 76 65 63 2e 0a 2a 2a 20 4f 70 63 6f Bitvec..** Opco
2af0: 64 65 20 35 20 69 73 20 75 73 65 64 20 74 6f 20 de 5 is used to
2b00: 64 65 6c 69 62 65 72 61 74 65 6c 79 20 69 6e 64 deliberately ind
2b10: 75 63 65 20 61 20 66 61 75 6c 74 20 69 6e 20 6f uce a fault in o
2b20: 72 64 65 72 20 74 6f 0a 2a 2a 20 63 6f 6e 66 69 rder to.** confi
2b30: 72 6d 20 74 68 61 74 20 65 72 72 6f 72 20 64 65 rm that error de
2b40: 74 65 63 74 69 6f 6e 20 77 6f 72 6b 73 2e 0a 2a tection works..*
2b50: 2a 0a 2a 2a 20 41 74 20 74 68 65 20 63 6f 6e 63 *.** At the conc
2b60: 6c 75 73 69 6f 6e 20 6f 66 20 74 68 65 20 74 65 lusion of the te
2b70: 73 74 20 74 68 65 20 6c 69 6e 65 61 72 20 61 72 st the linear ar
2b80: 72 61 79 20 69 73 20 63 6f 6d 70 61 72 65 64 0a ray is compared.
2b90: 2a 2a 20 61 67 61 69 6e 73 74 20 74 68 65 20 42 ** against the B
2ba0: 69 74 76 65 63 20 6f 62 6a 65 63 74 2e 20 20 49 itvec object. I
2bb0: 66 20 74 68 65 72 65 20 61 72 65 20 61 6e 79 20 f there are any
2bc0: 64 69 66 66 65 72 65 6e 63 65 73 2c 0a 2a 2a 20 differences,.**
2bd0: 61 6e 20 65 72 72 6f 72 20 69 73 20 72 65 74 75 an error is retu
2be0: 72 6e 65 64 2e 20 20 49 66 20 74 68 65 79 20 61 rned. If they a
2bf0: 72 65 20 74 68 65 20 73 61 6d 65 2c 20 7a 65 72 re the same, zer
2c00: 6f 20 69 73 20 72 65 74 75 72 6e 65 64 2e 0a 2a o is returned..*
2c10: 2a 0a 2a 2a 20 49 66 20 61 20 6d 65 6d 6f 72 79 *.** If a memory
2c20: 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 65 72 72 6f allocation erro
2c30: 72 20 6f 63 63 75 72 73 2c 20 72 65 74 75 72 6e r occurs, return
2c40: 20 2d 31 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 -1..*/.int sqli
2c50: 74 65 33 42 69 74 76 65 63 42 75 69 6c 74 69 6e te3BitvecBuiltin
2c60: 54 65 73 74 28 69 6e 74 20 73 7a 2c 20 69 6e 74 Test(int sz, int
2c70: 20 2a 61 4f 70 29 7b 0a 20 20 42 69 74 76 65 63 *aOp){. Bitvec
2c80: 20 2a 70 42 69 74 76 65 63 20 3d 20 30 3b 0a 20 *pBitvec = 0;.
2c90: 20 75 6e 73 69 67 6e 65 64 20 63 68 61 72 20 2a unsigned char *
2ca0: 70 56 20 3d 20 30 3b 0a 20 20 69 6e 74 20 72 63 pV = 0;. int rc
2cb0: 20 3d 20 2d 31 3b 0a 20 20 69 6e 74 20 69 2c 20 = -1;. int i,
2cc0: 6e 78 2c 20 70 63 2c 20 6f 70 3b 0a 20 20 76 6f nx, pc, op;. vo
2cd0: 69 64 20 2a 70 54 6d 70 53 70 61 63 65 3b 0a 0a id *pTmpSpace;..
2ce0: 20 20 2f 2a 20 41 6c 6c 6f 63 61 74 65 20 74 68 /* Allocate th
2cf0: 65 20 42 69 74 76 65 63 20 74 6f 20 62 65 20 74 e Bitvec to be t
2d00: 65 73 74 65 64 20 61 6e 64 20 61 20 6c 69 6e 65 ested and a line
2d10: 61 72 20 61 72 72 61 79 20 6f 66 0a 20 20 2a 2a ar array of. **
2d20: 20 62 69 74 73 20 74 6f 20 61 63 74 20 61 73 20 bits to act as
2d30: 74 68 65 20 72 65 66 65 72 65 6e 63 65 20 2a 2f the reference */
2d40: 0a 20 20 70 42 69 74 76 65 63 20 3d 20 73 71 6c . pBitvec = sql
2d50: 69 74 65 33 42 69 74 76 65 63 43 72 65 61 74 65 ite3BitvecCreate
2d60: 28 20 73 7a 20 29 3b 0a 20 20 70 56 20 3d 20 73 ( sz );. pV = s
2d70: 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 20 28 qlite3_malloc( (
2d80: 73 7a 2b 37 29 2f 38 20 2b 20 31 20 29 3b 0a 20 sz+7)/8 + 1 );.
2d90: 20 70 54 6d 70 53 70 61 63 65 20 3d 20 73 71 6c pTmpSpace = sql
2da0: 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 42 49 54 56 ite3_malloc(BITV
2db0: 45 43 5f 53 5a 29 3b 0a 20 20 69 66 28 20 70 42 EC_SZ);. if( pB
2dc0: 69 74 76 65 63 3d 3d 30 20 7c 7c 20 70 56 3d 3d itvec==0 || pV==
2dd0: 30 20 7c 7c 20 70 54 6d 70 53 70 61 63 65 3d 3d 0 || pTmpSpace==
2de0: 30 20 20 29 20 67 6f 74 6f 20 62 69 74 76 65 63 0 ) goto bitvec
2df0: 5f 65 6e 64 3b 0a 20 20 6d 65 6d 73 65 74 28 70 _end;. memset(p
2e00: 56 2c 20 30 2c 20 28 73 7a 2b 37 29 2f 38 20 2b V, 0, (sz+7)/8 +
2e10: 20 31 29 3b 0a 0a 20 20 2f 2a 20 52 75 6e 20 74 1);.. /* Run t
2e20: 68 65 20 70 72 6f 67 72 61 6d 20 2a 2f 0a 20 20 he program */.
2e30: 70 63 20 3d 20 30 3b 0a 20 20 77 68 69 6c 65 28 pc = 0;. while(
2e40: 20 28 6f 70 20 3d 20 61 4f 70 5b 70 63 5d 29 21 (op = aOp[pc])!
2e50: 3d 30 20 29 7b 0a 20 20 20 20 73 77 69 74 63 68 =0 ){. switch
2e60: 28 20 6f 70 20 29 7b 0a 20 20 20 20 20 20 63 61 ( op ){. ca
2e70: 73 65 20 31 3a 0a 20 20 20 20 20 20 63 61 73 65 se 1:. case
2e80: 20 32 3a 0a 20 20 20 20 20 20 63 61 73 65 20 35 2:. case 5
2e90: 3a 20 7b 0a 20 20 20 20 20 20 20 20 6e 78 20 3d : {. nx =
2ea0: 20 34 3b 0a 20 20 20 20 20 20 20 20 69 20 3d 20 4;. i =
2eb0: 61 4f 70 5b 70 63 2b 32 5d 20 2d 20 31 3b 0a 20 aOp[pc+2] - 1;.
2ec0: 20 20 20 20 20 20 20 61 4f 70 5b 70 63 2b 32 5d aOp[pc+2]
2ed0: 20 2b 3d 20 61 4f 70 5b 70 63 2b 33 5d 3b 0a 20 += aOp[pc+3];.
2ee0: 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 break;.
2ef0: 20 20 20 20 7d 0a 20 20 20 20 20 20 63 61 73 65 }. case
2f00: 20 33 3a 0a 20 20 20 20 20 20 63 61 73 65 20 34 3:. case 4
2f10: 3a 20 0a 20 20 20 20 20 20 64 65 66 61 75 6c 74 : . default
2f20: 3a 20 7b 0a 20 20 20 20 20 20 20 20 6e 78 20 3d : {. nx =
2f30: 20 32 3b 0a 20 20 20 20 20 20 20 20 73 71 6c 69 2;. sqli
2f40: 74 65 33 5f 72 61 6e 64 6f 6d 6e 65 73 73 28 73 te3_randomness(s
2f50: 69 7a 65 6f 66 28 69 29 2c 20 26 69 29 3b 0a 20 izeof(i), &i);.
2f60: 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 break;.
2f70: 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 20 20 }. }.
2f80: 69 66 28 20 28 2d 2d 61 4f 70 5b 70 63 2b 31 5d if( (--aOp[pc+1]
2f90: 29 20 3e 20 30 20 29 20 6e 78 20 3d 20 30 3b 0a ) > 0 ) nx = 0;.
2fa0: 20 20 20 20 70 63 20 2b 3d 20 6e 78 3b 0a 20 20 pc += nx;.
2fb0: 20 20 69 20 3d 20 28 69 20 26 20 30 78 37 66 66 i = (i & 0x7ff
2fc0: 66 66 66 66 66 29 25 73 7a 3b 0a 20 20 20 20 69 fffff)%sz;. i
2fd0: 66 28 20 28 6f 70 20 26 20 31 29 21 3d 30 20 29 f( (op & 1)!=0 )
2fe0: 7b 0a 20 20 20 20 20 20 53 45 54 42 49 54 28 70 {. SETBIT(p
2ff0: 56 2c 20 28 69 2b 31 29 29 3b 0a 20 20 20 20 20 V, (i+1));.
3000: 20 69 66 28 20 6f 70 21 3d 35 20 29 7b 0a 20 20 if( op!=5 ){.
3010: 20 20 20 20 20 20 69 66 28 20 73 71 6c 69 74 65 if( sqlite
3020: 33 42 69 74 76 65 63 53 65 74 28 70 42 69 74 76 3BitvecSet(pBitv
3030: 65 63 2c 20 69 2b 31 29 20 29 20 67 6f 74 6f 20 ec, i+1) ) goto
3040: 62 69 74 76 65 63 5f 65 6e 64 3b 0a 20 20 20 20 bitvec_end;.
3050: 20 20 7d 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 }. }else{.
3060: 20 20 20 20 20 43 4c 45 41 52 42 49 54 28 70 56 CLEARBIT(pV
3070: 2c 20 28 69 2b 31 29 29 3b 0a 20 20 20 20 20 20 , (i+1));.
3080: 73 71 6c 69 74 65 33 42 69 74 76 65 63 43 6c 65 sqlite3BitvecCle
3090: 61 72 28 70 42 69 74 76 65 63 2c 20 69 2b 31 2c ar(pBitvec, i+1,
30a0: 20 70 54 6d 70 53 70 61 63 65 29 3b 0a 20 20 20 pTmpSpace);.
30b0: 20 7d 0a 20 20 7d 0a 0a 20 20 2f 2a 20 54 65 73 }. }.. /* Tes
30c0: 74 20 74 6f 20 6d 61 6b 65 20 73 75 72 65 20 74 t to make sure t
30d0: 68 65 20 6c 69 6e 65 61 72 20 61 72 72 61 79 20 he linear array
30e0: 65 78 61 63 74 6c 79 20 6d 61 74 63 68 65 73 20 exactly matches
30f0: 74 68 65 0a 20 20 2a 2a 20 42 69 74 76 65 63 20 the. ** Bitvec
3100: 6f 62 6a 65 63 74 2e 20 20 53 74 61 72 74 20 77 object. Start w
3110: 69 74 68 20 74 68 65 20 61 73 73 75 6d 70 74 69 ith the assumpti
3120: 6f 6e 20 74 68 61 74 20 74 68 65 79 20 64 6f 0a on that they do.
3130: 20 20 2a 2a 20 6d 61 74 63 68 20 28 72 63 3d 3d ** match (rc==
3140: 30 29 2e 20 20 43 68 61 6e 67 65 20 72 63 20 74 0). Change rc t
3150: 6f 20 6e 6f 6e 2d 7a 65 72 6f 20 69 66 20 61 20 o non-zero if a
3160: 64 69 73 63 72 65 70 61 6e 63 79 0a 20 20 2a 2a discrepancy. **
3170: 20 69 73 20 66 6f 75 6e 64 2e 0a 20 20 2a 2f 0a is found.. */.
3180: 20 20 72 63 20 3d 20 73 71 6c 69 74 65 33 42 69 rc = sqlite3Bi
3190: 74 76 65 63 54 65 73 74 28 30 2c 30 29 20 2b 20 tvecTest(0,0) +
31a0: 73 71 6c 69 74 65 33 42 69 74 76 65 63 54 65 73 sqlite3BitvecTes
31b0: 74 28 70 42 69 74 76 65 63 2c 20 73 7a 2b 31 29 t(pBitvec, sz+1)
31c0: 0a 20 20 20 20 20 20 20 20 20 20 2b 20 73 71 6c . + sql
31d0: 69 74 65 33 42 69 74 76 65 63 54 65 73 74 28 70 ite3BitvecTest(p
31e0: 42 69 74 76 65 63 2c 20 30 29 0a 20 20 20 20 20 Bitvec, 0).
31f0: 20 20 20 20 20 2b 20 28 73 71 6c 69 74 65 33 42 + (sqlite3B
3200: 69 74 76 65 63 53 69 7a 65 28 70 42 69 74 76 65 itvecSize(pBitve
3210: 63 29 20 2d 20 73 7a 29 3b 0a 20 20 66 6f 72 28 c) - sz);. for(
3220: 69 3d 31 3b 20 69 3c 3d 73 7a 3b 20 69 2b 2b 29 i=1; i<=sz; i++)
3230: 7b 0a 20 20 20 20 69 66 28 20 20 28 54 45 53 54 {. if( (TEST
3240: 42 49 54 28 70 56 2c 69 29 29 21 3d 73 71 6c 69 BIT(pV,i))!=sqli
3250: 74 65 33 42 69 74 76 65 63 54 65 73 74 28 70 42 te3BitvecTest(pB
3260: 69 74 76 65 63 2c 69 29 20 29 7b 0a 20 20 20 20 itvec,i) ){.
3270: 20 20 72 63 20 3d 20 69 3b 0a 20 20 20 20 20 20 rc = i;.
3280: 62 72 65 61 6b 3b 0a 20 20 20 20 7d 0a 20 20 7d break;. }. }
3290: 0a 0a 20 20 2f 2a 20 46 72 65 65 20 61 6c 6c 6f .. /* Free allo
32a0: 63 61 74 65 64 20 73 74 72 75 63 74 75 72 65 20 cated structure
32b0: 2a 2f 0a 62 69 74 76 65 63 5f 65 6e 64 3a 0a 20 */.bitvec_end:.
32c0: 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70 54 sqlite3_free(pT
32d0: 6d 70 53 70 61 63 65 29 3b 0a 20 20 73 71 6c 69 mpSpace);. sqli
32e0: 74 65 33 5f 66 72 65 65 28 70 56 29 3b 0a 20 20 te3_free(pV);.
32f0: 73 71 6c 69 74 65 33 42 69 74 76 65 63 44 65 73 sqlite3BitvecDes
3300: 74 72 6f 79 28 70 42 69 74 76 65 63 29 3b 0a 20 troy(pBitvec);.
3310: 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 23 65 return rc;.}.#e
3320: 6e 64 69 66 20 2f 2a 20 53 51 4c 49 54 45 5f 4f ndif /* SQLITE_O
3330: 4d 49 54 5f 42 55 49 4c 54 49 4e 5f 54 45 53 54 MIT_BUILTIN_TEST
3340: 20 2a 2f 0a */.