/ Hex Artifact Content
Login

Artifact af50f1c8c0ff54d6bdb7a80e2fceca5a93670bef:


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: 2f 0a 23 69 6e 63 6c 75 64 65 20 22 73 71 6c 69  /.#include "sqli
06a0: 74 65 49 6e 74 2e 68 22 0a 0a 2f 2a 20 53 69 7a  teInt.h"../* Siz
06b0: 65 20 6f 66 20 74 68 65 20 42 69 74 76 65 63 20  e of the Bitvec 
06c0: 73 74 72 75 63 74 75 72 65 20 69 6e 20 62 79 74  structure in byt
06d0: 65 73 2e 20 2a 2f 0a 23 64 65 66 69 6e 65 20 42  es. */.#define B
06e0: 49 54 56 45 43 5f 53 5a 20 20 20 20 20 20 20 20  ITVEC_SZ        
06f0: 35 31 32 0a 0a 2f 2a 20 52 6f 75 6e 64 20 74 68  512../* Round th
0700: 65 20 75 6e 69 6f 6e 20 73 69 7a 65 20 64 6f 77  e union size dow
0710: 6e 20 74 6f 20 74 68 65 20 6e 65 61 72 65 73 74  n to the nearest
0720: 20 70 6f 69 6e 74 65 72 20 62 6f 75 6e 64 61 72   pointer boundar
0730: 79 2c 20 73 69 6e 63 65 20 74 68 61 74 27 73 20  y, since that's 
0740: 68 6f 77 20 0a 2a 2a 20 69 74 20 77 69 6c 6c 20  how .** it will 
0750: 62 65 20 61 6c 69 67 6e 65 64 20 77 69 74 68 69  be aligned withi
0760: 6e 20 74 68 65 20 42 69 74 76 65 63 20 73 74 72  n the Bitvec str
0770: 75 63 74 2e 20 2a 2f 0a 23 64 65 66 69 6e 65 20  uct. */.#define 
0780: 42 49 54 56 45 43 5f 55 53 49 5a 45 20 20 20 20  BITVEC_USIZE    
0790: 20 28 28 28 42 49 54 56 45 43 5f 53 5a 2d 28 33   (((BITVEC_SZ-(3
07a0: 2a 73 69 7a 65 6f 66 28 75 33 32 29 29 29 2f 73  *sizeof(u32)))/s
07b0: 69 7a 65 6f 66 28 42 69 74 76 65 63 2a 29 29 2a  izeof(Bitvec*))*
07c0: 73 69 7a 65 6f 66 28 42 69 74 76 65 63 2a 29 29  sizeof(Bitvec*))
07d0: 0a 0a 2f 2a 20 54 79 70 65 20 6f 66 20 74 68 65  ../* Type of the
07e0: 20 61 72 72 61 79 20 22 65 6c 65 6d 65 6e 74 22   array "element"
07f0: 20 66 6f 72 20 74 68 65 20 62 69 74 6d 61 70 20   for the bitmap 
0800: 72 65 70 72 65 73 65 6e 74 61 74 69 6f 6e 2e 20  representation. 
0810: 0a 2a 2a 20 53 68 6f 75 6c 64 20 62 65 20 61 20  .** Should be a 
0820: 70 6f 77 65 72 20 6f 66 20 32 2c 20 61 6e 64 20  power of 2, and 
0830: 69 64 65 61 6c 6c 79 2c 20 65 76 65 6e 6c 79 20  ideally, evenly 
0840: 64 69 76 69 64 65 20 69 6e 74 6f 20 42 49 54 56  divide into BITV
0850: 45 43 5f 55 53 49 5a 45 2e 20 0a 2a 2a 20 53 65  EC_USIZE. .** Se
0860: 74 74 69 6e 67 20 74 68 69 73 20 74 6f 20 74 68  tting this to th
0870: 65 20 22 6e 61 74 75 72 61 6c 20 77 6f 72 64 22  e "natural word"
0880: 20 73 69 7a 65 20 6f 66 20 79 6f 75 72 20 43 50   size of your CP
0890: 55 20 6d 61 79 20 69 6d 70 72 6f 76 65 0a 2a 2a  U may improve.**
08a0: 20 70 65 72 66 6f 72 6d 61 6e 63 65 2e 20 2a 2f   performance. */
08b0: 0a 23 64 65 66 69 6e 65 20 42 49 54 56 45 43 5f  .#define BITVEC_
08c0: 54 45 4c 45 4d 20 20 20 20 20 75 38 0a 2f 2a 20  TELEM     u8./* 
08d0: 53 69 7a 65 2c 20 69 6e 20 62 69 74 73 2c 20 6f  Size, in bits, o
08e0: 66 20 74 68 65 20 62 69 74 6d 61 70 20 65 6c 65  f the bitmap ele
08f0: 6d 65 6e 74 2e 20 2a 2f 0a 23 64 65 66 69 6e 65  ment. */.#define
0900: 20 42 49 54 56 45 43 5f 53 5a 45 4c 45 4d 20 20   BITVEC_SZELEM  
0910: 20 20 38 0a 2f 2a 20 4e 75 6d 62 65 72 20 6f 66    8./* Number of
0920: 20 65 6c 65 6d 65 6e 74 73 20 69 6e 20 61 20 62   elements in a b
0930: 69 74 6d 61 70 20 61 72 72 61 79 2e 20 2a 2f 0a  itmap array. */.
0940: 23 64 65 66 69 6e 65 20 42 49 54 56 45 43 5f 4e  #define BITVEC_N
0950: 45 4c 45 4d 20 20 20 20 20 28 42 49 54 56 45 43  ELEM     (BITVEC
0960: 5f 55 53 49 5a 45 2f 73 69 7a 65 6f 66 28 42 49  _USIZE/sizeof(BI
0970: 54 56 45 43 5f 54 45 4c 45 4d 29 29 0a 2f 2a 20  TVEC_TELEM))./* 
0980: 4e 75 6d 62 65 72 20 6f 66 20 62 69 74 73 20 69  Number of bits i
0990: 6e 20 74 68 65 20 62 69 74 6d 61 70 20 61 72 72  n the bitmap arr
09a0: 61 79 2e 20 2a 2f 0a 23 64 65 66 69 6e 65 20 42  ay. */.#define B
09b0: 49 54 56 45 43 5f 4e 42 49 54 20 20 20 20 20 20  ITVEC_NBIT      
09c0: 28 42 49 54 56 45 43 5f 4e 45 4c 45 4d 2a 42 49  (BITVEC_NELEM*BI
09d0: 54 56 45 43 5f 53 5a 45 4c 45 4d 29 0a 0a 2f 2a  TVEC_SZELEM)../*
09e0: 20 4e 75 6d 62 65 72 20 6f 66 20 75 33 32 20 76   Number of u32 v
09f0: 61 6c 75 65 73 20 69 6e 20 68 61 73 68 20 74 61  alues in hash ta
0a00: 62 6c 65 2e 20 2a 2f 0a 23 64 65 66 69 6e 65 20  ble. */.#define 
0a10: 42 49 54 56 45 43 5f 4e 49 4e 54 20 20 20 20 20  BITVEC_NINT     
0a20: 20 28 42 49 54 56 45 43 5f 55 53 49 5a 45 2f 73   (BITVEC_USIZE/s
0a30: 69 7a 65 6f 66 28 75 33 32 29 29 0a 2f 2a 20 4d  izeof(u32))./* M
0a40: 61 78 69 6d 75 6d 20 6e 75 6d 62 65 72 20 6f 66  aximum number of
0a50: 20 65 6e 74 72 69 65 73 20 69 6e 20 68 61 73 68   entries in hash
0a60: 20 74 61 62 6c 65 20 62 65 66 6f 72 65 20 0a 2a   table before .*
0a70: 2a 20 73 75 62 2d 64 69 76 69 64 69 6e 67 20 61  * sub-dividing a
0a80: 6e 64 20 72 65 2d 68 61 73 68 69 6e 67 2e 20 2a  nd re-hashing. *
0a90: 2f 0a 23 64 65 66 69 6e 65 20 42 49 54 56 45 43  /.#define BITVEC
0aa0: 5f 4d 58 48 41 53 48 20 20 20 20 28 42 49 54 56  _MXHASH    (BITV
0ab0: 45 43 5f 4e 49 4e 54 2f 32 29 0a 2f 2a 20 48 61  EC_NINT/2)./* Ha
0ac0: 73 68 69 6e 67 20 66 75 6e 63 74 69 6f 6e 20 66  shing function f
0ad0: 6f 72 20 74 68 65 20 61 48 61 73 68 20 72 65 70  or the aHash rep
0ae0: 72 65 73 65 6e 74 61 74 69 6f 6e 2e 0a 2a 2a 20  resentation..** 
0af0: 45 6d 70 69 72 69 63 61 6c 20 74 65 73 74 69 6e  Empirical testin
0b00: 67 20 73 68 6f 77 65 64 20 74 68 61 74 20 74 68  g showed that th
0b10: 65 20 2a 33 37 20 6d 75 6c 74 69 70 6c 69 65 72  e *37 multiplier
0b20: 20 0a 2a 2a 20 28 61 6e 20 61 72 62 69 74 72 61   .** (an arbitra
0b30: 72 79 20 70 72 69 6d 65 29 69 6e 20 74 68 65 20  ry prime)in the 
0b40: 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 70 72  hash function pr
0b50: 6f 76 69 64 65 64 20 0a 2a 2a 20 6e 6f 20 66 65  ovided .** no fe
0b60: 77 65 72 20 63 6f 6c 6c 69 73 69 6f 6e 73 20 74  wer collisions t
0b70: 68 61 6e 20 74 68 65 20 6e 6f 2d 6f 70 20 2a 31  han the no-op *1
0b80: 2e 20 2a 2f 0a 23 64 65 66 69 6e 65 20 42 49 54  . */.#define BIT
0b90: 56 45 43 5f 48 41 53 48 28 58 29 20 20 20 28 28  VEC_HASH(X)   ((
0ba0: 28 58 29 2a 31 29 25 42 49 54 56 45 43 5f 4e 49  (X)*1)%BITVEC_NI
0bb0: 4e 54 29 0a 0a 23 64 65 66 69 6e 65 20 42 49 54  NT)..#define BIT
0bc0: 56 45 43 5f 4e 50 54 52 20 20 20 20 20 20 28 42  VEC_NPTR      (B
0bd0: 49 54 56 45 43 5f 55 53 49 5a 45 2f 73 69 7a 65  ITVEC_USIZE/size
0be0: 6f 66 28 42 69 74 76 65 63 20 2a 29 29 0a 0a 0a  of(Bitvec *))...
0bf0: 2f 2a 0a 2a 2a 20 41 20 62 69 74 6d 61 70 20 69  /*.** A bitmap i
0c00: 73 20 61 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66  s an instance of
0c10: 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 73   the following s
0c20: 74 72 75 63 74 75 72 65 2e 0a 2a 2a 0a 2a 2a 20  tructure..**.** 
0c30: 54 68 69 73 20 62 69 74 6d 61 70 20 72 65 63 6f  This bitmap reco
0c40: 72 64 73 20 74 68 65 20 65 78 69 73 74 61 6e 63  rds the existanc
0c50: 65 20 6f 66 20 7a 65 72 6f 20 6f 72 20 6d 6f 72  e of zero or mor
0c60: 65 20 62 69 74 73 0a 2a 2a 20 77 69 74 68 20 76  e bits.** with v
0c70: 61 6c 75 65 73 20 62 65 74 77 65 65 6e 20 31 20  alues between 1 
0c80: 61 6e 64 20 69 53 69 7a 65 2c 20 69 6e 63 6c 75  and iSize, inclu
0c90: 73 69 76 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 72  sive..**.** Ther
0ca0: 65 20 61 72 65 20 74 68 72 65 65 20 70 6f 73 73  e are three poss
0cb0: 69 62 6c 65 20 72 65 70 72 65 73 65 6e 74 61 74  ible representat
0cc0: 69 6f 6e 73 20 6f 66 20 74 68 65 20 62 69 74 6d  ions of the bitm
0cd0: 61 70 2e 0a 2a 2a 20 49 66 20 69 53 69 7a 65 3c  ap..** If iSize<
0ce0: 3d 42 49 54 56 45 43 5f 4e 42 49 54 2c 20 74 68  =BITVEC_NBIT, th
0cf0: 65 6e 20 42 69 74 76 65 63 2e 75 2e 61 42 69 74  en Bitvec.u.aBit
0d00: 6d 61 70 5b 5d 20 69 73 20 61 20 73 74 72 61 69  map[] is a strai
0d10: 67 68 74 0a 2a 2a 20 62 69 74 6d 61 70 2e 20 20  ght.** bitmap.  
0d20: 54 68 65 20 6c 65 61 73 74 20 73 69 67 6e 69 66  The least signif
0d30: 69 63 61 6e 74 20 62 69 74 20 69 73 20 62 69 74  icant bit is bit
0d40: 20 31 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 69 53 69   1..**.** If iSi
0d50: 7a 65 3e 42 49 54 56 45 43 5f 4e 42 49 54 20 61  ze>BITVEC_NBIT a
0d60: 6e 64 20 69 44 69 76 69 73 6f 72 3d 3d 30 20 74  nd iDivisor==0 t
0d70: 68 65 6e 20 42 69 74 76 65 63 2e 75 2e 61 48 61  hen Bitvec.u.aHa
0d80: 73 68 5b 5d 20 69 73 0a 2a 2a 20 61 20 68 61 73  sh[] is.** a has
0d90: 68 20 74 61 62 6c 65 20 74 68 61 74 20 77 69 6c  h table that wil
0da0: 6c 20 68 6f 6c 64 20 75 70 20 74 6f 20 42 49 54  l hold up to BIT
0db0: 56 45 43 5f 4d 58 48 41 53 48 20 64 69 73 74 69  VEC_MXHASH disti
0dc0: 6e 63 74 20 76 61 6c 75 65 73 2e 0a 2a 2a 0a 2a  nct values..**.*
0dd0: 2a 20 4f 74 68 65 72 77 69 73 65 2c 20 74 68 65  * Otherwise, the
0de0: 20 76 61 6c 75 65 20 69 20 69 73 20 72 65 64 69   value i is redi
0df0: 72 65 63 74 65 64 20 69 6e 74 6f 20 6f 6e 65 20  rected into one 
0e00: 6f 66 20 42 49 54 56 45 43 5f 4e 50 54 52 0a 2a  of BITVEC_NPTR.*
0e10: 2a 20 73 75 62 2d 62 69 74 6d 61 70 73 20 70 6f  * sub-bitmaps po
0e20: 69 6e 74 65 64 20 74 6f 20 62 79 20 42 69 74 76  inted to by Bitv
0e30: 65 63 2e 75 2e 61 70 53 75 62 5b 5d 2e 20 20 45  ec.u.apSub[].  E
0e40: 61 63 68 20 73 75 62 62 69 74 6d 61 70 0a 2a 2a  ach subbitmap.**
0e50: 20 68 61 6e 64 6c 65 73 20 75 70 20 74 6f 20 69   handles up to i
0e60: 44 69 76 69 73 6f 72 20 73 65 70 61 72 61 74 65  Divisor separate
0e70: 20 76 61 6c 75 65 73 20 6f 66 20 69 2e 20 20 61   values of i.  a
0e80: 70 53 75 62 5b 30 5d 20 68 6f 6c 64 73 0a 2a 2a  pSub[0] holds.**
0e90: 20 76 61 6c 75 65 73 20 62 65 74 77 65 65 6e 20   values between 
0ea0: 31 20 61 6e 64 20 69 44 69 76 69 73 6f 72 2e 20  1 and iDivisor. 
0eb0: 20 61 70 53 75 62 5b 31 5d 20 68 6f 6c 64 73 20   apSub[1] holds 
0ec0: 76 61 6c 75 65 73 20 62 65 74 77 65 65 6e 0a 2a  values between.*
0ed0: 2a 20 69 44 69 76 69 73 6f 72 2b 31 20 61 6e 64  * iDivisor+1 and
0ee0: 20 32 2a 69 44 69 76 69 73 6f 72 2e 20 20 61 70   2*iDivisor.  ap
0ef0: 53 75 62 5b 4e 5d 20 68 6f 6c 64 73 20 76 61 6c  Sub[N] holds val
0f00: 75 65 73 20 62 65 74 77 65 65 6e 0a 2a 2a 20 4e  ues between.** N
0f10: 2a 69 44 69 76 69 73 6f 72 2b 31 20 61 6e 64 20  *iDivisor+1 and 
0f20: 28 4e 2b 31 29 2a 69 44 69 76 69 73 6f 72 2e 20  (N+1)*iDivisor. 
0f30: 20 45 61 63 68 20 73 75 62 62 69 74 6d 61 70 20   Each subbitmap 
0f40: 69 73 20 6e 6f 72 6d 61 6c 69 7a 65 64 0a 2a 2a  is normalized.**
0f50: 20 74 6f 20 68 6f 6c 64 20 64 65 61 6c 20 77 69   to hold deal wi
0f60: 74 68 20 76 61 6c 75 65 73 20 62 65 74 77 65 65  th values betwee
0f70: 6e 20 31 20 61 6e 64 20 69 44 69 76 69 73 6f 72  n 1 and iDivisor
0f80: 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 42 69 74 76  ..*/.struct Bitv
0f90: 65 63 20 7b 0a 20 20 75 33 32 20 69 53 69 7a 65  ec {.  u32 iSize
0fa0: 3b 20 20 20 20 20 20 2f 2a 20 4d 61 78 69 6d 75  ;      /* Maximu
0fb0: 6d 20 62 69 74 20 69 6e 64 65 78 2e 20 20 4d 61  m bit index.  Ma
0fc0: 78 20 69 53 69 7a 65 20 69 73 20 34 2c 32 39 34  x iSize is 4,294
0fd0: 2c 39 36 37 2c 32 39 36 2e 20 2a 2f 0a 20 20 75  ,967,296. */.  u
0fe0: 33 32 20 6e 53 65 74 3b 20 20 20 20 20 20 20 2f  32 nSet;       /
0ff0: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 62 69 74 73  * Number of bits
1000: 20 74 68 61 74 20 61 72 65 20 73 65 74 20 2d 20   that are set - 
1010: 6f 6e 6c 79 20 76 61 6c 69 64 20 66 6f 72 20 61  only valid for a
1020: 48 61 73 68 0a 20 20 20 20 20 20 20 20 20 20 20  Hash.           
1030: 20 20 20 20 20 20 20 2a 2a 20 65 6c 65 6d 65 6e         ** elemen
1040: 74 2e 20 20 4d 61 78 20 69 73 20 42 49 54 56 45  t.  Max is BITVE
1050: 43 5f 4e 49 4e 54 2e 20 20 46 6f 72 20 42 49 54  C_NINT.  For BIT
1060: 56 45 43 5f 53 5a 20 6f 66 20 35 31 32 2c 0a 20  VEC_SZ of 512,. 
1070: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1080: 20 2a 2a 20 74 68 69 73 20 77 6f 75 6c 64 20 62   ** this would b
1090: 65 20 31 32 35 2e 20 2a 2f 0a 20 20 75 33 32 20  e 125. */.  u32 
10a0: 69 44 69 76 69 73 6f 72 3b 20 20 20 2f 2a 20 4e  iDivisor;   /* N
10b0: 75 6d 62 65 72 20 6f 66 20 62 69 74 73 20 68 61  umber of bits ha
10c0: 6e 64 6c 65 64 20 62 79 20 65 61 63 68 20 61 70  ndled by each ap
10d0: 53 75 62 5b 5d 20 65 6e 74 72 79 2e 20 2a 2f 0a  Sub[] entry. */.
10e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
10f0: 20 20 2f 2a 20 53 68 6f 75 6c 64 20 3e 3d 30 20    /* Should >=0 
1100: 66 6f 72 20 61 70 53 75 62 20 65 6c 65 6d 65 6e  for apSub elemen
1110: 74 2e 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20  t. */.          
1120: 20 20 20 20 20 20 20 20 2f 2a 20 4d 61 78 20 69          /* Max i
1130: 44 69 76 69 73 6f 72 20 69 73 20 6d 61 78 28 75  Divisor is max(u
1140: 33 32 29 20 2f 20 42 49 54 56 45 43 5f 4e 50 54  32) / BITVEC_NPT
1150: 52 20 2b 20 31 2e 20 20 2a 2f 0a 20 20 20 20 20  R + 1.  */.     
1160: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
1170: 46 6f 72 20 61 20 42 49 54 56 45 43 5f 53 5a 20  For a BITVEC_SZ 
1180: 6f 66 20 35 31 32 2c 20 74 68 69 73 20 77 6f 75  of 512, this wou
1190: 6c 64 20 62 65 20 33 34 2c 33 35 39 2c 37 33 39  ld be 34,359,739
11a0: 2e 20 2a 2f 0a 20 20 75 6e 69 6f 6e 20 7b 0a 20  . */.  union {. 
11b0: 20 20 20 42 49 54 56 45 43 5f 54 45 4c 45 4d 20     BITVEC_TELEM 
11c0: 61 42 69 74 6d 61 70 5b 42 49 54 56 45 43 5f 4e  aBitmap[BITVEC_N
11d0: 45 4c 45 4d 5d 3b 20 20 20 20 2f 2a 20 42 69 74  ELEM];    /* Bit
11e0: 6d 61 70 20 72 65 70 72 65 73 65 6e 74 61 74 69  map representati
11f0: 6f 6e 20 2a 2f 0a 20 20 20 20 75 33 32 20 61 48  on */.    u32 aH
1200: 61 73 68 5b 42 49 54 56 45 43 5f 4e 49 4e 54 5d  ash[BITVEC_NINT]
1210: 3b 20 20 20 20 20 20 2f 2a 20 48 61 73 68 20 74  ;      /* Hash t
1220: 61 62 6c 65 20 72 65 70 72 65 73 65 6e 74 61 74  able representat
1230: 69 6f 6e 20 2a 2f 0a 20 20 20 20 42 69 74 76 65  ion */.    Bitve
1240: 63 20 2a 61 70 53 75 62 5b 42 49 54 56 45 43 5f  c *apSub[BITVEC_
1250: 4e 50 54 52 5d 3b 20 20 2f 2a 20 52 65 63 75 72  NPTR];  /* Recur
1260: 73 69 76 65 20 72 65 70 72 65 73 65 6e 74 61 74  sive representat
1270: 69 6f 6e 20 2a 2f 0a 20 20 7d 20 75 3b 0a 7d 3b  ion */.  } u;.};
1280: 0a 0a 2f 2a 0a 2a 2a 20 43 72 65 61 74 65 20 61  ../*.** Create a
1290: 20 6e 65 77 20 62 69 74 6d 61 70 20 6f 62 6a 65   new bitmap obje
12a0: 63 74 20 61 62 6c 65 20 74 6f 20 68 61 6e 64 6c  ct able to handl
12b0: 65 20 62 69 74 73 20 62 65 74 77 65 65 6e 20 30  e bits between 0
12c0: 20 61 6e 64 20 69 53 69 7a 65 2c 0a 2a 2a 20 69   and iSize,.** i
12d0: 6e 63 6c 75 73 69 76 65 2e 20 20 52 65 74 75 72  nclusive.  Retur
12e0: 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74  n a pointer to t
12f0: 68 65 20 6e 65 77 20 6f 62 6a 65 63 74 2e 20 20  he new object.  
1300: 52 65 74 75 72 6e 20 4e 55 4c 4c 20 69 66 20 0a  Return NULL if .
1310: 2a 2a 20 6d 61 6c 6c 6f 63 20 66 61 69 6c 73 2e  ** malloc fails.
1320: 0a 2a 2f 0a 42 69 74 76 65 63 20 2a 73 71 6c 69  .*/.Bitvec *sqli
1330: 74 65 33 42 69 74 76 65 63 43 72 65 61 74 65 28  te3BitvecCreate(
1340: 75 33 32 20 69 53 69 7a 65 29 7b 0a 20 20 42 69  u32 iSize){.  Bi
1350: 74 76 65 63 20 2a 70 3b 0a 20 20 61 73 73 65 72  tvec *p;.  asser
1360: 74 28 20 73 69 7a 65 6f 66 28 2a 70 29 3d 3d 42  t( sizeof(*p)==B
1370: 49 54 56 45 43 5f 53 5a 20 29 3b 0a 20 20 70 20  ITVEC_SZ );.  p 
1380: 3d 20 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 5a  = sqlite3MallocZ
1390: 65 72 6f 28 20 73 69 7a 65 6f 66 28 2a 70 29 20  ero( sizeof(*p) 
13a0: 29 3b 0a 20 20 69 66 28 20 70 20 29 7b 0a 20 20  );.  if( p ){.  
13b0: 20 20 70 2d 3e 69 53 69 7a 65 20 3d 20 69 53 69    p->iSize = iSi
13c0: 7a 65 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e  ze;.  }.  return
13d0: 20 70 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 68 65   p;.}../*.** Che
13e0: 63 6b 20 74 6f 20 73 65 65 20 69 66 20 74 68 65  ck to see if the
13f0: 20 69 2d 74 68 20 62 69 74 20 69 73 20 73 65 74   i-th bit is set
1400: 2e 20 20 52 65 74 75 72 6e 20 74 72 75 65 20 6f  .  Return true o
1410: 72 20 66 61 6c 73 65 2e 0a 2a 2a 20 49 66 20 70  r false..** If p
1420: 20 69 73 20 4e 55 4c 4c 20 28 69 66 20 74 68 65   is NULL (if the
1430: 20 62 69 74 6d 61 70 20 68 61 73 20 6e 6f 74 20   bitmap has not 
1440: 62 65 65 6e 20 63 72 65 61 74 65 64 29 20 6f 72  been created) or
1450: 20 69 66 0a 2a 2a 20 69 20 69 73 20 6f 75 74 20   if.** i is out 
1460: 6f 66 20 72 61 6e 67 65 2c 20 74 68 65 6e 20 72  of range, then r
1470: 65 74 75 72 6e 20 66 61 6c 73 65 2e 0a 2a 2f 0a  eturn false..*/.
1480: 69 6e 74 20 73 71 6c 69 74 65 33 42 69 74 76 65  int sqlite3Bitve
1490: 63 54 65 73 74 28 42 69 74 76 65 63 20 2a 70 2c  cTest(Bitvec *p,
14a0: 20 75 33 32 20 69 29 7b 0a 20 20 69 66 28 20 70   u32 i){.  if( p
14b0: 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 30 3b 0a  ==0 ) return 0;.
14c0: 20 20 69 66 28 20 69 3e 70 2d 3e 69 53 69 7a 65    if( i>p->iSize
14d0: 20 7c 7c 20 69 3d 3d 30 20 29 20 72 65 74 75 72   || i==0 ) retur
14e0: 6e 20 30 3b 0a 20 20 69 2d 2d 3b 0a 20 20 77 68  n 0;.  i--;.  wh
14f0: 69 6c 65 28 20 70 2d 3e 69 44 69 76 69 73 6f 72  ile( p->iDivisor
1500: 20 29 7b 0a 20 20 20 20 75 33 32 20 62 69 6e 20   ){.    u32 bin 
1510: 3d 20 69 2f 70 2d 3e 69 44 69 76 69 73 6f 72 3b  = i/p->iDivisor;
1520: 0a 20 20 20 20 69 20 3d 20 69 25 70 2d 3e 69 44  .    i = i%p->iD
1530: 69 76 69 73 6f 72 3b 0a 20 20 20 20 70 20 3d 20  ivisor;.    p = 
1540: 70 2d 3e 75 2e 61 70 53 75 62 5b 62 69 6e 5d 3b  p->u.apSub[bin];
1550: 0a 20 20 20 20 69 66 20 28 21 70 29 20 7b 0a 20  .    if (!p) {. 
1560: 20 20 20 20 20 72 65 74 75 72 6e 20 30 3b 0a 20       return 0;. 
1570: 20 20 20 7d 0a 20 20 7d 0a 20 20 69 66 28 20 70     }.  }.  if( p
1580: 2d 3e 69 53 69 7a 65 3c 3d 42 49 54 56 45 43 5f  ->iSize<=BITVEC_
1590: 4e 42 49 54 20 29 7b 0a 20 20 20 20 72 65 74 75  NBIT ){.    retu
15a0: 72 6e 20 28 70 2d 3e 75 2e 61 42 69 74 6d 61 70  rn (p->u.aBitmap
15b0: 5b 69 2f 42 49 54 56 45 43 5f 53 5a 45 4c 45 4d  [i/BITVEC_SZELEM
15c0: 5d 20 26 20 28 31 3c 3c 28 69 26 28 42 49 54 56  ] & (1<<(i&(BITV
15d0: 45 43 5f 53 5a 45 4c 45 4d 2d 31 29 29 29 29 21  EC_SZELEM-1))))!
15e0: 3d 30 3b 0a 20 20 7d 20 65 6c 73 65 7b 0a 20 20  =0;.  } else{.  
15f0: 20 20 75 33 32 20 68 20 3d 20 42 49 54 56 45 43    u32 h = BITVEC
1600: 5f 48 41 53 48 28 69 2b 2b 29 3b 0a 20 20 20 20  _HASH(i++);.    
1610: 77 68 69 6c 65 28 20 70 2d 3e 75 2e 61 48 61 73  while( p->u.aHas
1620: 68 5b 68 5d 20 29 7b 0a 20 20 20 20 20 20 69 66  h[h] ){.      if
1630: 28 20 70 2d 3e 75 2e 61 48 61 73 68 5b 68 5d 3d  ( p->u.aHash[h]=
1640: 3d 69 20 29 20 72 65 74 75 72 6e 20 31 3b 0a 20  =i ) return 1;. 
1650: 20 20 20 20 20 68 20 3d 20 28 68 2b 31 29 20 25       h = (h+1) %
1660: 20 42 49 54 56 45 43 5f 4e 49 4e 54 3b 0a 20 20   BITVEC_NINT;.  
1670: 20 20 7d 0a 20 20 20 20 72 65 74 75 72 6e 20 30    }.    return 0
1680: 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 53  ;.  }.}../*.** S
1690: 65 74 20 74 68 65 20 69 2d 74 68 20 62 69 74 2e  et the i-th bit.
16a0: 20 20 52 65 74 75 72 6e 20 30 20 6f 6e 20 73 75    Return 0 on su
16b0: 63 63 65 73 73 20 61 6e 64 20 61 6e 20 65 72 72  ccess and an err
16c0: 6f 72 20 63 6f 64 65 20 69 66 0a 2a 2a 20 61 6e  or code if.** an
16d0: 79 74 68 69 6e 67 20 67 6f 65 73 20 77 72 6f 6e  ything goes wron
16e0: 67 2e 0a 2a 2a 0a 2a 2a 20 54 68 69 73 20 72 6f  g..**.** This ro
16f0: 75 74 69 6e 65 20 6d 69 67 68 74 20 63 61 75 73  utine might caus
1700: 65 20 73 75 62 2d 62 69 74 6d 61 70 73 20 74 6f  e sub-bitmaps to
1710: 20 62 65 20 61 6c 6c 6f 63 61 74 65 64 2e 20 20   be allocated.  
1720: 46 61 69 6c 69 6e 67 0a 2a 2a 20 74 6f 20 67 65  Failing.** to ge
1730: 74 20 74 68 65 20 6d 65 6d 6f 72 79 20 6e 65 65  t the memory nee
1740: 64 65 64 20 74 6f 20 68 6f 6c 64 20 74 68 65 20  ded to hold the 
1750: 73 75 62 2d 62 69 74 6d 61 70 20 69 73 20 74 68  sub-bitmap is th
1760: 65 20 6f 6e 6c 79 0a 2a 2a 20 74 68 61 74 20 63  e only.** that c
1770: 61 6e 20 67 6f 20 77 72 6f 6e 67 20 77 69 74 68  an go wrong with
1780: 20 61 6e 20 69 6e 73 65 72 74 2c 20 61 73 73 75   an insert, assu
1790: 6d 69 6e 67 20 70 20 61 6e 64 20 69 20 61 72 65  ming p and i are
17a0: 20 76 61 6c 69 64 2e 0a 2a 2a 0a 2a 2a 20 54 68   valid..**.** Th
17b0: 65 20 63 61 6c 6c 69 6e 67 20 66 75 6e 63 74 69  e calling functi
17c0: 6f 6e 20 6d 75 73 74 20 65 6e 73 75 72 65 20 74  on must ensure t
17d0: 68 61 74 20 70 20 69 73 20 61 20 76 61 6c 69 64  hat p is a valid
17e0: 20 42 69 74 76 65 63 20 6f 62 6a 65 63 74 0a 2a   Bitvec object.*
17f0: 2a 20 61 6e 64 20 74 68 61 74 20 74 68 65 20 76  * and that the v
1800: 61 6c 75 65 20 66 6f 72 20 22 69 22 20 69 73 20  alue for "i" is 
1810: 77 69 74 68 69 6e 20 72 61 6e 67 65 20 6f 66 20  within range of 
1820: 74 68 65 20 42 69 74 76 65 63 20 6f 62 6a 65 63  the Bitvec objec
1830: 74 2e 0a 2a 2a 20 4f 74 68 65 72 77 69 73 65 20  t..** Otherwise 
1840: 74 68 65 20 62 65 68 61 76 69 6f 72 20 69 73 20  the behavior is 
1850: 75 6e 64 65 66 69 6e 65 64 2e 0a 2a 2f 0a 69 6e  undefined..*/.in
1860: 74 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 53  t sqlite3BitvecS
1870: 65 74 28 42 69 74 76 65 63 20 2a 70 2c 20 75 33  et(Bitvec *p, u3
1880: 32 20 69 29 7b 0a 20 20 75 33 32 20 68 3b 0a 20  2 i){.  u32 h;. 
1890: 20 69 66 28 20 70 3d 3d 30 20 29 20 72 65 74 75   if( p==0 ) retu
18a0: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 20 20  rn SQLITE_OK;.  
18b0: 61 73 73 65 72 74 28 20 69 3e 30 20 29 3b 0a 20  assert( i>0 );. 
18c0: 20 61 73 73 65 72 74 28 20 69 3c 3d 70 2d 3e 69   assert( i<=p->i
18d0: 53 69 7a 65 20 29 3b 0a 20 20 69 2d 2d 3b 0a 20  Size );.  i--;. 
18e0: 20 77 68 69 6c 65 28 28 70 2d 3e 69 53 69 7a 65   while((p->iSize
18f0: 20 3e 20 42 49 54 56 45 43 5f 4e 42 49 54 29 20   > BITVEC_NBIT) 
1900: 26 26 20 70 2d 3e 69 44 69 76 69 73 6f 72 29 20  && p->iDivisor) 
1910: 7b 0a 20 20 20 20 75 33 32 20 62 69 6e 20 3d 20  {.    u32 bin = 
1920: 69 2f 70 2d 3e 69 44 69 76 69 73 6f 72 3b 0a 20  i/p->iDivisor;. 
1930: 20 20 20 69 20 3d 20 69 25 70 2d 3e 69 44 69 76     i = i%p->iDiv
1940: 69 73 6f 72 3b 0a 20 20 20 20 69 66 28 20 70 2d  isor;.    if( p-
1950: 3e 75 2e 61 70 53 75 62 5b 62 69 6e 5d 3d 3d 30  >u.apSub[bin]==0
1960: 20 29 7b 0a 20 20 20 20 20 20 70 2d 3e 75 2e 61   ){.      p->u.a
1970: 70 53 75 62 5b 62 69 6e 5d 20 3d 20 73 71 6c 69  pSub[bin] = sqli
1980: 74 65 33 42 69 74 76 65 63 43 72 65 61 74 65 28  te3BitvecCreate(
1990: 20 70 2d 3e 69 44 69 76 69 73 6f 72 20 29 3b 0a   p->iDivisor );.
19a0: 20 20 20 20 20 20 69 66 28 20 70 2d 3e 75 2e 61        if( p->u.a
19b0: 70 53 75 62 5b 62 69 6e 5d 3d 3d 30 20 29 20 72  pSub[bin]==0 ) r
19c0: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d  eturn SQLITE_NOM
19d0: 45 4d 3b 0a 20 20 20 20 7d 0a 20 20 20 20 70 20  EM;.    }.    p 
19e0: 3d 20 70 2d 3e 75 2e 61 70 53 75 62 5b 62 69 6e  = p->u.apSub[bin
19f0: 5d 3b 0a 20 20 7d 0a 20 20 69 66 28 20 70 2d 3e  ];.  }.  if( p->
1a00: 69 53 69 7a 65 3c 3d 42 49 54 56 45 43 5f 4e 42  iSize<=BITVEC_NB
1a10: 49 54 20 29 7b 0a 20 20 20 20 70 2d 3e 75 2e 61  IT ){.    p->u.a
1a20: 42 69 74 6d 61 70 5b 69 2f 42 49 54 56 45 43 5f  Bitmap[i/BITVEC_
1a30: 53 5a 45 4c 45 4d 5d 20 7c 3d 20 31 20 3c 3c 20  SZELEM] |= 1 << 
1a40: 28 69 26 28 42 49 54 56 45 43 5f 53 5a 45 4c 45  (i&(BITVEC_SZELE
1a50: 4d 2d 31 29 29 3b 0a 20 20 20 20 72 65 74 75 72  M-1));.    retur
1a60: 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 20 20 7d  n SQLITE_OK;.  }
1a70: 0a 20 20 68 20 3d 20 42 49 54 56 45 43 5f 48 41  .  h = BITVEC_HA
1a80: 53 48 28 69 2b 2b 29 3b 0a 20 20 2f 2a 20 69 66  SH(i++);.  /* if
1a90: 20 74 68 65 72 65 20 77 61 73 6e 27 74 20 61 20   there wasn't a 
1aa0: 68 61 73 68 20 63 6f 6c 6c 69 73 69 6f 6e 2c 20  hash collision, 
1ab0: 61 6e 64 20 74 68 69 73 20 64 6f 65 73 6e 27 74  and this doesn't
1ac0: 20 2a 2f 0a 20 20 2f 2a 20 63 6f 6d 70 6c 65 74   */.  /* complet
1ad0: 65 6c 79 20 66 69 6c 6c 20 74 68 65 20 68 61 73  ely fill the has
1ae0: 68 2c 20 74 68 65 6e 20 6a 75 73 74 20 61 64 64  h, then just add
1af0: 20 69 74 20 77 69 74 68 6f 75 74 20 2a 2f 0a 20   it without */. 
1b00: 20 2f 2a 20 77 6f 72 72 69 6e 67 20 61 62 6f 75   /* worring abou
1b10: 74 20 73 75 62 2d 64 69 76 69 64 69 6e 67 20 61  t sub-dividing a
1b20: 6e 64 20 72 65 2d 68 61 73 68 69 6e 67 2e 20 2a  nd re-hashing. *
1b30: 2f 0a 20 20 69 66 28 20 21 70 2d 3e 75 2e 61 48  /.  if( !p->u.aH
1b40: 61 73 68 5b 68 5d 20 29 7b 0a 20 20 20 20 69 66  ash[h] ){.    if
1b50: 20 28 70 2d 3e 6e 53 65 74 3c 28 42 49 54 56 45   (p->nSet<(BITVE
1b60: 43 5f 4e 49 4e 54 2d 31 29 29 20 7b 0a 20 20 20  C_NINT-1)) {.   
1b70: 20 20 20 67 6f 74 6f 20 62 69 74 76 65 63 5f 73     goto bitvec_s
1b80: 65 74 5f 65 6e 64 3b 0a 20 20 20 20 7d 20 65 6c  et_end;.    } el
1b90: 73 65 20 7b 0a 20 20 20 20 20 20 67 6f 74 6f 20  se {.      goto 
1ba0: 62 69 74 76 65 63 5f 73 65 74 5f 72 65 68 61 73  bitvec_set_rehas
1bb0: 68 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 2f  h;.    }.  }.  /
1bc0: 2a 20 74 68 65 72 65 20 77 61 73 20 61 20 63 6f  * there was a co
1bd0: 6c 6c 69 73 69 6f 6e 2c 20 63 68 65 63 6b 20 74  llision, check t
1be0: 6f 20 73 65 65 20 69 66 20 69 74 27 73 20 61 6c  o see if it's al
1bf0: 72 65 61 64 79 20 2a 2f 0a 20 20 2f 2a 20 69 6e  ready */.  /* in
1c00: 20 68 61 73 68 2c 20 69 66 20 6e 6f 74 2c 20 74   hash, if not, t
1c10: 72 79 20 74 6f 20 66 69 6e 64 20 61 20 73 70 6f  ry to find a spo
1c20: 74 20 66 6f 72 20 69 74 20 2a 2f 0a 20 20 64 6f  t for it */.  do
1c30: 20 7b 0a 20 20 20 20 69 66 28 20 70 2d 3e 75 2e   {.    if( p->u.
1c40: 61 48 61 73 68 5b 68 5d 3d 3d 69 20 29 20 72 65  aHash[h]==i ) re
1c50: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a  turn SQLITE_OK;.
1c60: 20 20 20 20 68 2b 2b 3b 0a 20 20 20 20 69 66 28      h++;.    if(
1c70: 20 68 3e 3d 42 49 54 56 45 43 5f 4e 49 4e 54 20   h>=BITVEC_NINT 
1c80: 29 20 68 20 3d 20 30 3b 0a 20 20 7d 20 77 68 69  ) h = 0;.  } whi
1c90: 6c 65 28 20 70 2d 3e 75 2e 61 48 61 73 68 5b 68  le( p->u.aHash[h
1ca0: 5d 20 29 3b 0a 20 20 2f 2a 20 77 65 20 64 69 64  ] );.  /* we did
1cb0: 6e 27 74 20 66 69 6e 64 20 69 74 20 69 6e 20 74  n't find it in t
1cc0: 68 65 20 68 61 73 68 2e 20 20 68 20 70 6f 69 6e  he hash.  h poin
1cd0: 74 73 20 74 6f 20 74 68 65 20 66 69 72 73 74 20  ts to the first 
1ce0: 2a 2f 0a 20 20 2f 2a 20 61 76 61 69 6c 61 62 6c  */.  /* availabl
1cf0: 65 20 66 72 65 65 20 73 70 6f 74 2e 20 63 68 65  e free spot. che
1d00: 63 6b 20 74 6f 20 73 65 65 20 69 66 20 74 68 69  ck to see if thi
1d10: 73 20 69 73 20 67 6f 69 6e 67 20 74 6f 20 2a 2f  s is going to */
1d20: 0a 20 20 2f 2a 20 6d 61 6b 65 20 6f 75 72 20 68  .  /* make our h
1d30: 61 73 68 20 74 6f 6f 20 22 66 75 6c 6c 22 2e 20  ash too "full". 
1d40: 20 2a 2f 0a 62 69 74 76 65 63 5f 73 65 74 5f 72   */.bitvec_set_r
1d50: 65 68 61 73 68 3a 0a 20 20 69 66 28 20 70 2d 3e  ehash:.  if( p->
1d60: 6e 53 65 74 3e 3d 42 49 54 56 45 43 5f 4d 58 48  nSet>=BITVEC_MXH
1d70: 41 53 48 20 29 7b 0a 20 20 20 20 75 6e 73 69 67  ASH ){.    unsig
1d80: 6e 65 64 20 69 6e 74 20 6a 3b 0a 20 20 20 20 69  ned int j;.    i
1d90: 6e 74 20 72 63 3b 0a 20 20 20 20 75 33 32 20 2a  nt rc;.    u32 *
1da0: 61 69 56 61 6c 75 65 73 20 3d 20 73 71 6c 69 74  aiValues = sqlit
1db0: 65 33 53 74 61 63 6b 41 6c 6c 6f 63 52 61 77 28  e3StackAllocRaw(
1dc0: 30 2c 20 73 69 7a 65 6f 66 28 70 2d 3e 75 2e 61  0, sizeof(p->u.a
1dd0: 48 61 73 68 29 29 3b 0a 20 20 20 20 69 66 28 20  Hash));.    if( 
1de0: 61 69 56 61 6c 75 65 73 3d 3d 30 20 29 7b 0a 20  aiValues==0 ){. 
1df0: 20 20 20 20 20 72 65 74 75 72 6e 20 53 51 4c 49       return SQLI
1e00: 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 7d 65  TE_NOMEM;.    }e
1e10: 6c 73 65 7b 0a 20 20 20 20 20 20 6d 65 6d 63 70  lse{.      memcp
1e20: 79 28 61 69 56 61 6c 75 65 73 2c 20 70 2d 3e 75  y(aiValues, p->u
1e30: 2e 61 48 61 73 68 2c 20 73 69 7a 65 6f 66 28 70  .aHash, sizeof(p
1e40: 2d 3e 75 2e 61 48 61 73 68 29 29 3b 0a 20 20 20  ->u.aHash));.   
1e50: 20 20 20 6d 65 6d 73 65 74 28 70 2d 3e 75 2e 61     memset(p->u.a
1e60: 70 53 75 62 2c 20 30 2c 20 73 69 7a 65 6f 66 28  pSub, 0, sizeof(
1e70: 70 2d 3e 75 2e 61 70 53 75 62 29 29 3b 0a 20 20  p->u.apSub));.  
1e80: 20 20 20 20 70 2d 3e 69 44 69 76 69 73 6f 72 20      p->iDivisor 
1e90: 3d 20 28 70 2d 3e 69 53 69 7a 65 20 2b 20 42 49  = (p->iSize + BI
1ea0: 54 56 45 43 5f 4e 50 54 52 20 2d 20 31 29 2f 42  TVEC_NPTR - 1)/B
1eb0: 49 54 56 45 43 5f 4e 50 54 52 3b 0a 20 20 20 20  ITVEC_NPTR;.    
1ec0: 20 20 72 63 20 3d 20 73 71 6c 69 74 65 33 42 69    rc = sqlite3Bi
1ed0: 74 76 65 63 53 65 74 28 70 2c 20 69 29 3b 0a 20  tvecSet(p, i);. 
1ee0: 20 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a 3c       for(j=0; j<
1ef0: 42 49 54 56 45 43 5f 4e 49 4e 54 3b 20 6a 2b 2b  BITVEC_NINT; j++
1f00: 29 7b 0a 20 20 20 20 20 20 20 20 69 66 28 20 61  ){.        if( a
1f10: 69 56 61 6c 75 65 73 5b 6a 5d 20 29 20 72 63 20  iValues[j] ) rc 
1f20: 7c 3d 20 73 71 6c 69 74 65 33 42 69 74 76 65 63  |= sqlite3Bitvec
1f30: 53 65 74 28 70 2c 20 61 69 56 61 6c 75 65 73 5b  Set(p, aiValues[
1f40: 6a 5d 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20  j]);.      }.   
1f50: 20 20 20 73 71 6c 69 74 65 33 53 74 61 63 6b 46     sqlite3StackF
1f60: 72 65 65 28 30 2c 20 61 69 56 61 6c 75 65 73 29  ree(0, aiValues)
1f70: 3b 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 72  ;.      return r
1f80: 63 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 62 69 74  c;.    }.  }.bit
1f90: 76 65 63 5f 73 65 74 5f 65 6e 64 3a 0a 20 20 70  vec_set_end:.  p
1fa0: 2d 3e 6e 53 65 74 2b 2b 3b 0a 20 20 70 2d 3e 75  ->nSet++;.  p->u
1fb0: 2e 61 48 61 73 68 5b 68 5d 20 3d 20 69 3b 0a 20  .aHash[h] = i;. 
1fc0: 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f   return SQLITE_O
1fd0: 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 6c 65 61  K;.}../*.** Clea
1fe0: 72 20 74 68 65 20 69 2d 74 68 20 62 69 74 2e 0a  r the i-th bit..
1ff0: 2a 2a 0a 2a 2a 20 70 42 75 66 20 6d 75 73 74 20  **.** pBuf must 
2000: 62 65 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20  be a pointer to 
2010: 61 74 20 6c 65 61 73 74 20 42 49 54 56 45 43 5f  at least BITVEC_
2020: 53 5a 20 62 79 74 65 73 20 6f 66 20 74 65 6d 70  SZ bytes of temp
2030: 6f 72 61 72 79 20 73 74 6f 72 61 67 65 0a 2a 2a  orary storage.**
2040: 20 74 68 61 74 20 42 69 74 76 65 63 43 6c 65 61   that BitvecClea
2050: 72 20 63 61 6e 20 75 73 65 20 74 6f 20 72 65 62  r can use to reb
2060: 75 69 6c 74 20 69 74 73 20 68 61 73 68 20 74 61  uilt its hash ta
2070: 62 6c 65 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c  ble..*/.void sql
2080: 69 74 65 33 42 69 74 76 65 63 43 6c 65 61 72 28  ite3BitvecClear(
2090: 42 69 74 76 65 63 20 2a 70 2c 20 75 33 32 20 69  Bitvec *p, u32 i
20a0: 2c 20 76 6f 69 64 20 2a 70 42 75 66 29 7b 0a 20  , void *pBuf){. 
20b0: 20 69 66 28 20 70 3d 3d 30 20 29 20 72 65 74 75   if( p==0 ) retu
20c0: 72 6e 3b 0a 20 20 61 73 73 65 72 74 28 20 69 3e  rn;.  assert( i>
20d0: 30 20 29 3b 0a 20 20 69 2d 2d 3b 0a 20 20 77 68  0 );.  i--;.  wh
20e0: 69 6c 65 28 20 70 2d 3e 69 44 69 76 69 73 6f 72  ile( p->iDivisor
20f0: 20 29 7b 0a 20 20 20 20 75 33 32 20 62 69 6e 20   ){.    u32 bin 
2100: 3d 20 69 2f 70 2d 3e 69 44 69 76 69 73 6f 72 3b  = i/p->iDivisor;
2110: 0a 20 20 20 20 69 20 3d 20 69 25 70 2d 3e 69 44  .    i = i%p->iD
2120: 69 76 69 73 6f 72 3b 0a 20 20 20 20 70 20 3d 20  ivisor;.    p = 
2130: 70 2d 3e 75 2e 61 70 53 75 62 5b 62 69 6e 5d 3b  p->u.apSub[bin];
2140: 0a 20 20 20 20 69 66 20 28 21 70 29 20 7b 0a 20  .    if (!p) {. 
2150: 20 20 20 20 20 72 65 74 75 72 6e 3b 0a 20 20 20       return;.   
2160: 20 7d 0a 20 20 7d 0a 20 20 69 66 28 20 70 2d 3e   }.  }.  if( p->
2170: 69 53 69 7a 65 3c 3d 42 49 54 56 45 43 5f 4e 42  iSize<=BITVEC_NB
2180: 49 54 20 29 7b 0a 20 20 20 20 70 2d 3e 75 2e 61  IT ){.    p->u.a
2190: 42 69 74 6d 61 70 5b 69 2f 42 49 54 56 45 43 5f  Bitmap[i/BITVEC_
21a0: 53 5a 45 4c 45 4d 5d 20 26 3d 20 7e 28 31 20 3c  SZELEM] &= ~(1 <
21b0: 3c 20 28 69 26 28 42 49 54 56 45 43 5f 53 5a 45  < (i&(BITVEC_SZE
21c0: 4c 45 4d 2d 31 29 29 29 3b 0a 20 20 7d 65 6c 73  LEM-1)));.  }els
21d0: 65 7b 0a 20 20 20 20 75 6e 73 69 67 6e 65 64 20  e{.    unsigned 
21e0: 69 6e 74 20 6a 3b 0a 20 20 20 20 75 33 32 20 2a  int j;.    u32 *
21f0: 61 69 56 61 6c 75 65 73 20 3d 20 70 42 75 66 3b  aiValues = pBuf;
2200: 0a 20 20 20 20 6d 65 6d 63 70 79 28 61 69 56 61  .    memcpy(aiVa
2210: 6c 75 65 73 2c 20 70 2d 3e 75 2e 61 48 61 73 68  lues, p->u.aHash
2220: 2c 20 73 69 7a 65 6f 66 28 70 2d 3e 75 2e 61 48  , sizeof(p->u.aH
2230: 61 73 68 29 29 3b 0a 20 20 20 20 6d 65 6d 73 65  ash));.    memse
2240: 74 28 70 2d 3e 75 2e 61 48 61 73 68 2c 20 30 2c  t(p->u.aHash, 0,
2250: 20 73 69 7a 65 6f 66 28 70 2d 3e 75 2e 61 48 61   sizeof(p->u.aHa
2260: 73 68 29 29 3b 0a 20 20 20 20 70 2d 3e 6e 53 65  sh));.    p->nSe
2270: 74 20 3d 20 30 3b 0a 20 20 20 20 66 6f 72 28 6a  t = 0;.    for(j
2280: 3d 30 3b 20 6a 3c 42 49 54 56 45 43 5f 4e 49 4e  =0; j<BITVEC_NIN
2290: 54 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 69  T; j++){.      i
22a0: 66 28 20 61 69 56 61 6c 75 65 73 5b 6a 5d 20 26  f( aiValues[j] &
22b0: 26 20 61 69 56 61 6c 75 65 73 5b 6a 5d 21 3d 28  & aiValues[j]!=(
22c0: 69 2b 31 29 20 29 7b 0a 20 20 20 20 20 20 20 20  i+1) ){.        
22d0: 75 33 32 20 68 20 3d 20 42 49 54 56 45 43 5f 48  u32 h = BITVEC_H
22e0: 41 53 48 28 61 69 56 61 6c 75 65 73 5b 6a 5d 2d  ASH(aiValues[j]-
22f0: 31 29 3b 0a 20 20 20 20 20 20 20 20 70 2d 3e 6e  1);.        p->n
2300: 53 65 74 2b 2b 3b 0a 20 20 20 20 20 20 20 20 77  Set++;.        w
2310: 68 69 6c 65 28 20 70 2d 3e 75 2e 61 48 61 73 68  hile( p->u.aHash
2320: 5b 68 5d 20 29 7b 0a 20 20 20 20 20 20 20 20 20  [h] ){.         
2330: 20 68 2b 2b 3b 0a 20 20 20 20 20 20 20 20 20 20   h++;.          
2340: 69 66 28 20 68 3e 3d 42 49 54 56 45 43 5f 4e 49  if( h>=BITVEC_NI
2350: 4e 54 20 29 20 68 20 3d 20 30 3b 0a 20 20 20 20  NT ) h = 0;.    
2360: 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20 70 2d      }.        p-
2370: 3e 75 2e 61 48 61 73 68 5b 68 5d 20 3d 20 61 69  >u.aHash[h] = ai
2380: 56 61 6c 75 65 73 5b 6a 5d 3b 0a 20 20 20 20 20  Values[j];.     
2390: 20 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a 7d 0a 0a   }.    }.  }.}..
23a0: 2f 2a 0a 2a 2a 20 44 65 73 74 72 6f 79 20 61 20  /*.** Destroy a 
23b0: 62 69 74 6d 61 70 20 6f 62 6a 65 63 74 2e 20 20  bitmap object.  
23c0: 52 65 63 6c 61 69 6d 20 61 6c 6c 20 6d 65 6d 6f  Reclaim all memo
23d0: 72 79 20 75 73 65 64 2e 0a 2a 2f 0a 76 6f 69 64  ry used..*/.void
23e0: 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 44 65   sqlite3BitvecDe
23f0: 73 74 72 6f 79 28 42 69 74 76 65 63 20 2a 70 29  stroy(Bitvec *p)
2400: 7b 0a 20 20 69 66 28 20 70 3d 3d 30 20 29 20 72  {.  if( p==0 ) r
2410: 65 74 75 72 6e 3b 0a 20 20 69 66 28 20 70 2d 3e  eturn;.  if( p->
2420: 69 44 69 76 69 73 6f 72 20 29 7b 0a 20 20 20 20  iDivisor ){.    
2430: 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 69 3b 0a  unsigned int i;.
2440: 20 20 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 42      for(i=0; i<B
2450: 49 54 56 45 43 5f 4e 50 54 52 3b 20 69 2b 2b 29  ITVEC_NPTR; i++)
2460: 7b 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33 42  {.      sqlite3B
2470: 69 74 76 65 63 44 65 73 74 72 6f 79 28 70 2d 3e  itvecDestroy(p->
2480: 75 2e 61 70 53 75 62 5b 69 5d 29 3b 0a 20 20 20  u.apSub[i]);.   
2490: 20 7d 0a 20 20 7d 0a 20 20 73 71 6c 69 74 65 33   }.  }.  sqlite3
24a0: 5f 66 72 65 65 28 70 29 3b 0a 7d 0a 0a 2f 2a 0a  _free(p);.}../*.
24b0: 2a 2a 20 52 65 74 75 72 6e 20 74 68 65 20 76 61  ** Return the va
24c0: 6c 75 65 20 6f 66 20 74 68 65 20 69 53 69 7a 65  lue of the iSize
24d0: 20 70 61 72 61 6d 65 74 65 72 20 73 70 65 63 69   parameter speci
24e0: 66 69 65 64 20 77 68 65 6e 20 42 69 74 76 65 63  fied when Bitvec
24f0: 20 2a 70 0a 2a 2a 20 77 61 73 20 63 72 65 61 74   *p.** was creat
2500: 65 64 2e 0a 2a 2f 0a 75 33 32 20 73 71 6c 69 74  ed..*/.u32 sqlit
2510: 65 33 42 69 74 76 65 63 53 69 7a 65 28 42 69 74  e3BitvecSize(Bit
2520: 76 65 63 20 2a 70 29 7b 0a 20 20 72 65 74 75 72  vec *p){.  retur
2530: 6e 20 70 2d 3e 69 53 69 7a 65 3b 0a 7d 0a 0a 23  n p->iSize;.}..#
2540: 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d  ifndef SQLITE_OM
2550: 49 54 5f 42 55 49 4c 54 49 4e 5f 54 45 53 54 0a  IT_BUILTIN_TEST.
2560: 2f 2a 0a 2a 2a 20 4c 65 74 20 56 5b 5d 20 62 65  /*.** Let V[] be
2570: 20 61 6e 20 61 72 72 61 79 20 6f 66 20 75 6e 73   an array of uns
2580: 69 67 6e 65 64 20 63 68 61 72 61 63 74 65 72 73  igned characters
2590: 20 73 75 66 66 69 63 69 65 6e 74 20 74 6f 20 68   sufficient to h
25a0: 6f 6c 64 0a 2a 2a 20 75 70 20 74 6f 20 4e 20 62  old.** up to N b
25b0: 69 74 73 2e 20 20 4c 65 74 20 49 20 62 65 20 61  its.  Let I be a
25c0: 6e 20 69 6e 74 65 67 65 72 20 62 65 74 77 65 65  n integer betwee
25d0: 6e 20 30 20 61 6e 64 20 4e 2e 20 20 30 3c 3d 49  n 0 and N.  0<=I
25e0: 3c 4e 2e 0a 2a 2a 20 54 68 65 6e 20 74 68 65 20  <N..** Then the 
25f0: 66 6f 6c 6c 6f 77 69 6e 67 20 6d 61 63 72 6f 73  following macros
2600: 20 63 61 6e 20 62 65 20 75 73 65 64 20 74 6f 20   can be used to 
2610: 73 65 74 2c 20 63 6c 65 61 72 2c 20 6f 72 20 74  set, clear, or t
2620: 65 73 74 0a 2a 2a 20 69 6e 64 69 76 69 64 75 61  est.** individua
2630: 6c 20 62 69 74 73 20 77 69 74 68 69 6e 20 56 2e  l bits within V.
2640: 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 53 45 54 42  .*/.#define SETB
2650: 49 54 28 56 2c 49 29 20 20 20 20 20 20 56 5b 49  IT(V,I)      V[I
2660: 3e 3e 33 5d 20 7c 3d 20 28 31 3c 3c 28 49 26 37  >>3] |= (1<<(I&7
2670: 29 29 0a 23 64 65 66 69 6e 65 20 43 4c 45 41 52  )).#define CLEAR
2680: 42 49 54 28 56 2c 49 29 20 20 20 20 56 5b 49 3e  BIT(V,I)    V[I>
2690: 3e 33 5d 20 26 3d 20 7e 28 31 3c 3c 28 49 26 37  >3] &= ~(1<<(I&7
26a0: 29 29 0a 23 64 65 66 69 6e 65 20 54 45 53 54 42  )).#define TESTB
26b0: 49 54 28 56 2c 49 29 20 20 20 20 20 28 56 5b 49  IT(V,I)     (V[I
26c0: 3e 3e 33 5d 26 28 31 3c 3c 28 49 26 37 29 29 29  >>3]&(1<<(I&7)))
26d0: 21 3d 30 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20  !=0../*.** This 
26e0: 72 6f 75 74 69 6e 65 20 72 75 6e 73 20 61 6e 20  routine runs an 
26f0: 65 78 74 65 6e 73 69 76 65 20 74 65 73 74 20 6f  extensive test o
2700: 66 20 74 68 65 20 42 69 74 76 65 63 20 63 6f 64  f the Bitvec cod
2710: 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 69 6e 70  e..**.** The inp
2720: 75 74 20 69 73 20 61 6e 20 61 72 72 61 79 20 6f  ut is an array o
2730: 66 20 69 6e 74 65 67 65 72 73 20 74 68 61 74 20  f integers that 
2740: 61 63 74 73 20 61 73 20 61 20 70 72 6f 67 72 61  acts as a progra
2750: 6d 0a 2a 2a 20 74 6f 20 74 65 73 74 20 74 68 65  m.** to test the
2760: 20 42 69 74 76 65 63 2e 20 20 54 68 65 20 69 6e   Bitvec.  The in
2770: 74 65 67 65 72 73 20 61 72 65 20 6f 70 63 6f 64  tegers are opcod
2780: 65 73 20 66 6f 6c 6c 6f 77 65 64 0a 2a 2a 20 62  es followed.** b
2790: 79 20 30 2c 20 31 2c 20 6f 72 20 33 20 6f 70 65  y 0, 1, or 3 ope
27a0: 72 61 6e 64 73 2c 20 64 65 70 65 6e 64 69 6e 67  rands, depending
27b0: 20 6f 6e 20 74 68 65 20 6f 70 63 6f 64 65 2e 20   on the opcode. 
27c0: 20 41 6e 6f 74 68 65 72 0a 2a 2a 20 6f 70 63 6f   Another.** opco
27d0: 64 65 20 66 6f 6c 6c 6f 77 73 20 69 6d 6d 65 64  de follows immed
27e0: 69 61 74 65 6c 79 20 61 66 74 65 72 20 74 68 65  iately after the
27f0: 20 6c 61 73 74 20 6f 70 65 72 61 6e 64 2e 0a 2a   last operand..*
2800: 2a 0a 2a 2a 20 54 68 65 72 65 20 61 72 65 20 36  *.** There are 6
2810: 20 6f 70 63 6f 64 65 73 20 6e 75 6d 62 65 72 65   opcodes numbere
2820: 64 20 66 72 6f 6d 20 30 20 74 68 72 6f 75 67 68  d from 0 through
2830: 20 35 2e 20 20 30 20 69 73 20 74 68 65 0a 2a 2a   5.  0 is the.**
2840: 20 22 68 61 6c 74 22 20 6f 70 63 6f 64 65 20 61   "halt" opcode a
2850: 6e 64 20 63 61 75 73 65 73 20 74 68 65 20 74 65  nd causes the te
2860: 73 74 20 74 6f 20 65 6e 64 2e 0a 2a 2a 0a 2a 2a  st to end..**.**
2870: 20 20 20 20 30 20 20 20 20 20 20 20 20 20 20 48      0          H
2880: 61 6c 74 20 61 6e 64 20 72 65 74 75 72 6e 20 74  alt and return t
2890: 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 65 72 72  he number of err
28a0: 6f 72 73 0a 2a 2a 20 20 20 20 31 20 4e 20 53 20  ors.**    1 N S 
28b0: 58 20 20 20 20 53 65 74 20 4e 20 62 69 74 73 20  X    Set N bits 
28c0: 62 65 67 69 6e 6e 69 6e 67 20 77 69 74 68 20 53  beginning with S
28d0: 20 61 6e 64 20 69 6e 63 72 65 6d 65 6e 74 69 6e   and incrementin
28e0: 67 20 62 79 20 58 0a 2a 2a 20 20 20 20 32 20 4e  g by X.**    2 N
28f0: 20 53 20 58 20 20 20 20 43 6c 65 61 72 20 4e 20   S X    Clear N 
2900: 62 69 74 73 20 62 65 67 69 6e 6e 69 6e 67 20 77  bits beginning w
2910: 69 74 68 20 53 20 61 6e 64 20 69 6e 63 72 65 6d  ith S and increm
2920: 65 6e 74 69 6e 67 20 62 79 20 58 0a 2a 2a 20 20  enting by X.**  
2930: 20 20 33 20 4e 20 20 20 20 20 20 20 20 53 65 74    3 N        Set
2940: 20 4e 20 72 61 6e 64 6f 6d 6c 79 20 63 68 6f 73   N randomly chos
2950: 65 6e 20 62 69 74 73 0a 2a 2a 20 20 20 20 34 20  en bits.**    4 
2960: 4e 20 20 20 20 20 20 20 20 43 6c 65 61 72 20 4e  N        Clear N
2970: 20 72 61 6e 64 6f 6d 6c 79 20 63 68 6f 73 65 6e   randomly chosen
2980: 20 62 69 74 73 0a 2a 2a 20 20 20 20 35 20 4e 20   bits.**    5 N 
2990: 53 20 58 20 20 20 20 53 65 74 20 4e 20 62 69 74  S X    Set N bit
29a0: 73 20 66 72 6f 6d 20 53 20 69 6e 63 72 65 6d 65  s from S increme
29b0: 6e 74 20 58 20 69 6e 20 61 72 72 61 79 20 6f 6e  nt X in array on
29c0: 6c 79 2c 20 6e 6f 74 20 69 6e 20 62 69 74 76 65  ly, not in bitve
29d0: 63 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6f 70 63 6f  c.**.** The opco
29e0: 64 65 73 20 31 20 74 68 72 6f 75 67 68 20 34 20  des 1 through 4 
29f0: 70 65 72 66 6f 72 6d 20 73 65 74 20 61 6e 64 20  perform set and 
2a00: 63 6c 65 61 72 20 6f 70 65 72 61 74 69 6f 6e 73  clear operations
2a10: 20 61 72 65 20 70 65 72 66 6f 72 6d 65 64 0a 2a   are performed.*
2a20: 2a 20 6f 6e 20 62 6f 74 68 20 61 20 42 69 74 76  * on both a Bitv
2a30: 65 63 20 6f 62 6a 65 63 74 20 61 6e 64 20 6f 6e  ec object and on
2a40: 20 61 20 6c 69 6e 65 61 72 20 61 72 72 61 79 20   a linear array 
2a50: 6f 66 20 62 69 74 73 20 6f 62 74 61 69 6e 65 64  of bits obtained
2a60: 20 66 72 6f 6d 20 6d 61 6c 6c 6f 63 2e 0a 2a 2a   from malloc..**
2a70: 20 4f 70 63 6f 64 65 20 35 20 77 6f 72 6b 73 20   Opcode 5 works 
2a80: 6f 6e 20 74 68 65 20 6c 69 6e 65 61 72 20 61 72  on the linear ar
2a90: 72 61 79 20 6f 6e 6c 79 2c 20 6e 6f 74 20 6f 6e  ray only, not on
2aa0: 20 74 68 65 20 42 69 74 76 65 63 2e 0a 2a 2a 20   the Bitvec..** 
2ab0: 4f 70 63 6f 64 65 20 35 20 69 73 20 75 73 65 64  Opcode 5 is used
2ac0: 20 74 6f 20 64 65 6c 69 62 65 72 61 74 65 6c 79   to deliberately
2ad0: 20 69 6e 64 75 63 65 20 61 20 66 61 75 6c 74 20   induce a fault 
2ae0: 69 6e 20 6f 72 64 65 72 20 74 6f 0a 2a 2a 20 63  in order to.** c
2af0: 6f 6e 66 69 72 6d 20 74 68 61 74 20 65 72 72 6f  onfirm that erro
2b00: 72 20 64 65 74 65 63 74 69 6f 6e 20 77 6f 72 6b  r detection work
2b10: 73 2e 0a 2a 2a 0a 2a 2a 20 41 74 20 74 68 65 20  s..**.** At the 
2b20: 63 6f 6e 63 6c 75 73 69 6f 6e 20 6f 66 20 74 68  conclusion of th
2b30: 65 20 74 65 73 74 20 74 68 65 20 6c 69 6e 65 61  e test the linea
2b40: 72 20 61 72 72 61 79 20 69 73 20 63 6f 6d 70 61  r array is compa
2b50: 72 65 64 0a 2a 2a 20 61 67 61 69 6e 73 74 20 74  red.** against t
2b60: 68 65 20 42 69 74 76 65 63 20 6f 62 6a 65 63 74  he Bitvec object
2b70: 2e 20 20 49 66 20 74 68 65 72 65 20 61 72 65 20  .  If there are 
2b80: 61 6e 79 20 64 69 66 66 65 72 65 6e 63 65 73 2c  any differences,
2b90: 0a 2a 2a 20 61 6e 20 65 72 72 6f 72 20 69 73 20  .** an error is 
2ba0: 72 65 74 75 72 6e 65 64 2e 20 20 49 66 20 74 68  returned.  If th
2bb0: 65 79 20 61 72 65 20 74 68 65 20 73 61 6d 65 2c  ey are the same,
2bc0: 20 7a 65 72 6f 20 69 73 20 72 65 74 75 72 6e 65   zero is returne
2bd0: 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 61 20 6d 65  d..**.** If a me
2be0: 6d 6f 72 79 20 61 6c 6c 6f 63 61 74 69 6f 6e 20  mory allocation 
2bf0: 65 72 72 6f 72 20 6f 63 63 75 72 73 2c 20 72 65  error occurs, re
2c00: 74 75 72 6e 20 2d 31 2e 0a 2a 2f 0a 69 6e 74 20  turn -1..*/.int 
2c10: 73 71 6c 69 74 65 33 42 69 74 76 65 63 42 75 69  sqlite3BitvecBui
2c20: 6c 74 69 6e 54 65 73 74 28 69 6e 74 20 73 7a 2c  ltinTest(int sz,
2c30: 20 69 6e 74 20 2a 61 4f 70 29 7b 0a 20 20 42 69   int *aOp){.  Bi
2c40: 74 76 65 63 20 2a 70 42 69 74 76 65 63 20 3d 20  tvec *pBitvec = 
2c50: 30 3b 0a 20 20 75 6e 73 69 67 6e 65 64 20 63 68  0;.  unsigned ch
2c60: 61 72 20 2a 70 56 20 3d 20 30 3b 0a 20 20 69 6e  ar *pV = 0;.  in
2c70: 74 20 72 63 20 3d 20 2d 31 3b 0a 20 20 69 6e 74  t rc = -1;.  int
2c80: 20 69 2c 20 6e 78 2c 20 70 63 2c 20 6f 70 3b 0a   i, nx, pc, op;.
2c90: 20 20 76 6f 69 64 20 2a 70 54 6d 70 53 70 61 63    void *pTmpSpac
2ca0: 65 3b 0a 0a 20 20 2f 2a 20 41 6c 6c 6f 63 61 74  e;..  /* Allocat
2cb0: 65 20 74 68 65 20 42 69 74 76 65 63 20 74 6f 20  e the Bitvec to 
2cc0: 62 65 20 74 65 73 74 65 64 20 61 6e 64 20 61 20  be tested and a 
2cd0: 6c 69 6e 65 61 72 20 61 72 72 61 79 20 6f 66 0a  linear array of.
2ce0: 20 20 2a 2a 20 62 69 74 73 20 74 6f 20 61 63 74    ** bits to act
2cf0: 20 61 73 20 74 68 65 20 72 65 66 65 72 65 6e 63   as the referenc
2d00: 65 20 2a 2f 0a 20 20 70 42 69 74 76 65 63 20 3d  e */.  pBitvec =
2d10: 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 43 72   sqlite3BitvecCr
2d20: 65 61 74 65 28 20 73 7a 20 29 3b 0a 20 20 70 56  eate( sz );.  pV
2d30: 20 3d 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f   = sqlite3_mallo
2d40: 63 28 20 28 73 7a 2b 37 29 2f 38 20 2b 20 31 20  c( (sz+7)/8 + 1 
2d50: 29 3b 0a 20 20 70 54 6d 70 53 70 61 63 65 20 3d  );.  pTmpSpace =
2d60: 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28   sqlite3_malloc(
2d70: 42 49 54 56 45 43 5f 53 5a 29 3b 0a 20 20 69 66  BITVEC_SZ);.  if
2d80: 28 20 70 42 69 74 76 65 63 3d 3d 30 20 7c 7c 20  ( pBitvec==0 || 
2d90: 70 56 3d 3d 30 20 7c 7c 20 70 54 6d 70 53 70 61  pV==0 || pTmpSpa
2da0: 63 65 3d 3d 30 20 20 29 20 67 6f 74 6f 20 62 69  ce==0  ) goto bi
2db0: 74 76 65 63 5f 65 6e 64 3b 0a 20 20 6d 65 6d 73  tvec_end;.  mems
2dc0: 65 74 28 70 56 2c 20 30 2c 20 28 73 7a 2b 37 29  et(pV, 0, (sz+7)
2dd0: 2f 38 20 2b 20 31 29 3b 0a 0a 20 20 2f 2a 20 4e  /8 + 1);..  /* N
2de0: 55 4c 4c 20 70 42 69 74 76 65 63 20 74 65 73 74  ULL pBitvec test
2df0: 73 20 2a 2f 0a 20 20 73 71 6c 69 74 65 33 42 69  s */.  sqlite3Bi
2e00: 74 76 65 63 53 65 74 28 30 2c 20 31 29 3b 0a 20  tvecSet(0, 1);. 
2e10: 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 43 6c   sqlite3BitvecCl
2e20: 65 61 72 28 30 2c 20 31 2c 20 70 54 6d 70 53 70  ear(0, 1, pTmpSp
2e30: 61 63 65 29 3b 0a 0a 20 20 2f 2a 20 52 75 6e 20  ace);..  /* Run 
2e40: 74 68 65 20 70 72 6f 67 72 61 6d 20 2a 2f 0a 20  the program */. 
2e50: 20 70 63 20 3d 20 30 3b 0a 20 20 77 68 69 6c 65   pc = 0;.  while
2e60: 28 20 28 6f 70 20 3d 20 61 4f 70 5b 70 63 5d 29  ( (op = aOp[pc])
2e70: 21 3d 30 20 29 7b 0a 20 20 20 20 73 77 69 74 63  !=0 ){.    switc
2e80: 68 28 20 6f 70 20 29 7b 0a 20 20 20 20 20 20 63  h( op ){.      c
2e90: 61 73 65 20 31 3a 0a 20 20 20 20 20 20 63 61 73  ase 1:.      cas
2ea0: 65 20 32 3a 0a 20 20 20 20 20 20 63 61 73 65 20  e 2:.      case 
2eb0: 35 3a 20 7b 0a 20 20 20 20 20 20 20 20 6e 78 20  5: {.        nx 
2ec0: 3d 20 34 3b 0a 20 20 20 20 20 20 20 20 69 20 3d  = 4;.        i =
2ed0: 20 61 4f 70 5b 70 63 2b 32 5d 20 2d 20 31 3b 0a   aOp[pc+2] - 1;.
2ee0: 20 20 20 20 20 20 20 20 61 4f 70 5b 70 63 2b 32          aOp[pc+2
2ef0: 5d 20 2b 3d 20 61 4f 70 5b 70 63 2b 33 5d 3b 0a  ] += aOp[pc+3];.
2f00: 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20          break;. 
2f10: 20 20 20 20 20 7d 0a 20 20 20 20 20 20 63 61 73       }.      cas
2f20: 65 20 33 3a 0a 20 20 20 20 20 20 63 61 73 65 20  e 3:.      case 
2f30: 34 3a 20 0a 20 20 20 20 20 20 64 65 66 61 75 6c  4: .      defaul
2f40: 74 3a 20 7b 0a 20 20 20 20 20 20 20 20 6e 78 20  t: {.        nx 
2f50: 3d 20 32 3b 0a 20 20 20 20 20 20 20 20 73 71 6c  = 2;.        sql
2f60: 69 74 65 33 5f 72 61 6e 64 6f 6d 6e 65 73 73 28  ite3_randomness(
2f70: 73 69 7a 65 6f 66 28 69 29 2c 20 26 69 29 3b 0a  sizeof(i), &i);.
2f80: 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20          break;. 
2f90: 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 20       }.    }.   
2fa0: 20 69 66 28 20 28 2d 2d 61 4f 70 5b 70 63 2b 31   if( (--aOp[pc+1
2fb0: 5d 29 20 3e 20 30 20 29 20 6e 78 20 3d 20 30 3b  ]) > 0 ) nx = 0;
2fc0: 0a 20 20 20 20 70 63 20 2b 3d 20 6e 78 3b 0a 20  .    pc += nx;. 
2fd0: 20 20 20 69 20 3d 20 28 69 20 26 20 30 78 37 66     i = (i & 0x7f
2fe0: 66 66 66 66 66 66 29 25 73 7a 3b 0a 20 20 20 20  ffffff)%sz;.    
2ff0: 69 66 28 20 28 6f 70 20 26 20 31 29 21 3d 30 20  if( (op & 1)!=0 
3000: 29 7b 0a 20 20 20 20 20 20 53 45 54 42 49 54 28  ){.      SETBIT(
3010: 70 56 2c 20 28 69 2b 31 29 29 3b 0a 20 20 20 20  pV, (i+1));.    
3020: 20 20 69 66 28 20 6f 70 21 3d 35 20 29 7b 0a 20    if( op!=5 ){. 
3030: 20 20 20 20 20 20 20 69 66 28 20 73 71 6c 69 74         if( sqlit
3040: 65 33 42 69 74 76 65 63 53 65 74 28 70 42 69 74  e3BitvecSet(pBit
3050: 76 65 63 2c 20 69 2b 31 29 20 29 20 67 6f 74 6f  vec, i+1) ) goto
3060: 20 62 69 74 76 65 63 5f 65 6e 64 3b 0a 20 20 20   bitvec_end;.   
3070: 20 20 20 7d 0a 20 20 20 20 7d 65 6c 73 65 7b 0a     }.    }else{.
3080: 20 20 20 20 20 20 43 4c 45 41 52 42 49 54 28 70        CLEARBIT(p
3090: 56 2c 20 28 69 2b 31 29 29 3b 0a 20 20 20 20 20  V, (i+1));.     
30a0: 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 43 6c   sqlite3BitvecCl
30b0: 65 61 72 28 70 42 69 74 76 65 63 2c 20 69 2b 31  ear(pBitvec, i+1
30c0: 2c 20 70 54 6d 70 53 70 61 63 65 29 3b 0a 20 20  , pTmpSpace);.  
30d0: 20 20 7d 0a 20 20 7d 0a 0a 20 20 2f 2a 20 54 65    }.  }..  /* Te
30e0: 73 74 20 74 6f 20 6d 61 6b 65 20 73 75 72 65 20  st to make sure 
30f0: 74 68 65 20 6c 69 6e 65 61 72 20 61 72 72 61 79  the linear array
3100: 20 65 78 61 63 74 6c 79 20 6d 61 74 63 68 65 73   exactly matches
3110: 20 74 68 65 0a 20 20 2a 2a 20 42 69 74 76 65 63   the.  ** Bitvec
3120: 20 6f 62 6a 65 63 74 2e 20 20 53 74 61 72 74 20   object.  Start 
3130: 77 69 74 68 20 74 68 65 20 61 73 73 75 6d 70 74  with the assumpt
3140: 69 6f 6e 20 74 68 61 74 20 74 68 65 79 20 64 6f  ion that they do
3150: 0a 20 20 2a 2a 20 6d 61 74 63 68 20 28 72 63 3d  .  ** match (rc=
3160: 3d 30 29 2e 20 20 43 68 61 6e 67 65 20 72 63 20  =0).  Change rc 
3170: 74 6f 20 6e 6f 6e 2d 7a 65 72 6f 20 69 66 20 61  to non-zero if a
3180: 20 64 69 73 63 72 65 70 61 6e 63 79 0a 20 20 2a   discrepancy.  *
3190: 2a 20 69 73 20 66 6f 75 6e 64 2e 0a 20 20 2a 2f  * is found..  */
31a0: 0a 20 20 72 63 20 3d 20 73 71 6c 69 74 65 33 42  .  rc = sqlite3B
31b0: 69 74 76 65 63 54 65 73 74 28 30 2c 30 29 20 2b  itvecTest(0,0) +
31c0: 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 54 65   sqlite3BitvecTe
31d0: 73 74 28 70 42 69 74 76 65 63 2c 20 73 7a 2b 31  st(pBitvec, sz+1
31e0: 29 0a 20 20 20 20 20 20 20 20 20 20 2b 20 73 71  ).          + sq
31f0: 6c 69 74 65 33 42 69 74 76 65 63 54 65 73 74 28  lite3BitvecTest(
3200: 70 42 69 74 76 65 63 2c 20 30 29 0a 20 20 20 20  pBitvec, 0).    
3210: 20 20 20 20 20 20 2b 20 28 73 71 6c 69 74 65 33        + (sqlite3
3220: 42 69 74 76 65 63 53 69 7a 65 28 70 42 69 74 76  BitvecSize(pBitv
3230: 65 63 29 20 2d 20 73 7a 29 3b 0a 20 20 66 6f 72  ec) - sz);.  for
3240: 28 69 3d 31 3b 20 69 3c 3d 73 7a 3b 20 69 2b 2b  (i=1; i<=sz; i++
3250: 29 7b 0a 20 20 20 20 69 66 28 20 20 28 54 45 53  ){.    if(  (TES
3260: 54 42 49 54 28 70 56 2c 69 29 29 21 3d 73 71 6c  TBIT(pV,i))!=sql
3270: 69 74 65 33 42 69 74 76 65 63 54 65 73 74 28 70  ite3BitvecTest(p
3280: 42 69 74 76 65 63 2c 69 29 20 29 7b 0a 20 20 20  Bitvec,i) ){.   
3290: 20 20 20 72 63 20 3d 20 69 3b 0a 20 20 20 20 20     rc = i;.     
32a0: 20 62 72 65 61 6b 3b 0a 20 20 20 20 7d 0a 20 20   break;.    }.  
32b0: 7d 0a 0a 20 20 2f 2a 20 46 72 65 65 20 61 6c 6c  }..  /* Free all
32c0: 6f 63 61 74 65 64 20 73 74 72 75 63 74 75 72 65  ocated structure
32d0: 20 2a 2f 0a 62 69 74 76 65 63 5f 65 6e 64 3a 0a   */.bitvec_end:.
32e0: 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70    sqlite3_free(p
32f0: 54 6d 70 53 70 61 63 65 29 3b 0a 20 20 73 71 6c  TmpSpace);.  sql
3300: 69 74 65 33 5f 66 72 65 65 28 70 56 29 3b 0a 20  ite3_free(pV);. 
3310: 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 44 65   sqlite3BitvecDe
3320: 73 74 72 6f 79 28 70 42 69 74 76 65 63 29 3b 0a  stroy(pBitvec);.
3330: 20 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 23    return rc;.}.#
3340: 65 6e 64 69 66 20 2f 2a 20 53 51 4c 49 54 45 5f  endif /* SQLITE_
3350: 4f 4d 49 54 5f 42 55 49 4c 54 49 4e 5f 54 45 53  OMIT_BUILTIN_TES
3360: 54 20 2a 2f 0a                                   T */.