/ Hex Artifact Content
Login

Artifact e08f6c1a9551b88081fc737916c6c3fd5029a6cf:


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 37 20 32  itvec.c,v 1.17 2
06b0: 30 30 39 2f 30 37 2f 32 35 20 31 37 3a 33 33 3a  009/07/25 17:33:
06c0: 32 36 20 64 72 68 20 45 78 70 20 24 0a 2a 2f 0a  26 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 20 3d 20 28 68 2b 31 29 20 25 20 42     h = (h+1) % B
16a0: 49 54 56 45 43 5f 4e 49 4e 54 3b 0a 20 20 20 20  ITVEC_NINT;.    
16b0: 7d 0a 20 20 20 20 72 65 74 75 72 6e 20 30 3b 0a  }.    return 0;.
16c0: 20 20 7d 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 53 65 74    }.}../*.** Set
16d0: 20 74 68 65 20 69 2d 74 68 20 62 69 74 2e 20 20   the i-th bit.  
16e0: 52 65 74 75 72 6e 20 30 20 6f 6e 20 73 75 63 63  Return 0 on succ
16f0: 65 73 73 20 61 6e 64 20 61 6e 20 65 72 72 6f 72  ess and an error
1700: 20 63 6f 64 65 20 69 66 0a 2a 2a 20 61 6e 79 74   code if.** anyt
1710: 68 69 6e 67 20 67 6f 65 73 20 77 72 6f 6e 67 2e  hing goes wrong.
1720: 0a 2a 2a 0a 2a 2a 20 54 68 69 73 20 72 6f 75 74  .**.** This rout
1730: 69 6e 65 20 6d 69 67 68 74 20 63 61 75 73 65 20  ine might cause 
1740: 73 75 62 2d 62 69 74 6d 61 70 73 20 74 6f 20 62  sub-bitmaps to b
1750: 65 20 61 6c 6c 6f 63 61 74 65 64 2e 20 20 46 61  e allocated.  Fa
1760: 69 6c 69 6e 67 0a 2a 2a 20 74 6f 20 67 65 74 20  iling.** to get 
1770: 74 68 65 20 6d 65 6d 6f 72 79 20 6e 65 65 64 65  the memory neede
1780: 64 20 74 6f 20 68 6f 6c 64 20 74 68 65 20 73 75  d to hold the su
1790: 62 2d 62 69 74 6d 61 70 20 69 73 20 74 68 65 20  b-bitmap is the 
17a0: 6f 6e 6c 79 0a 2a 2a 20 74 68 61 74 20 63 61 6e  only.** that can
17b0: 20 67 6f 20 77 72 6f 6e 67 20 77 69 74 68 20 61   go wrong with a
17c0: 6e 20 69 6e 73 65 72 74 2c 20 61 73 73 75 6d 69  n insert, assumi
17d0: 6e 67 20 70 20 61 6e 64 20 69 20 61 72 65 20 76  ng p and i are v
17e0: 61 6c 69 64 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20  alid..**.** The 
17f0: 63 61 6c 6c 69 6e 67 20 66 75 6e 63 74 69 6f 6e  calling function
1800: 20 6d 75 73 74 20 65 6e 73 75 72 65 20 74 68 61   must ensure tha
1810: 74 20 70 20 69 73 20 61 20 76 61 6c 69 64 20 42  t p is a valid B
1820: 69 74 76 65 63 20 6f 62 6a 65 63 74 0a 2a 2a 20  itvec object.** 
1830: 61 6e 64 20 74 68 61 74 20 74 68 65 20 76 61 6c  and that the val
1840: 75 65 20 66 6f 72 20 22 69 22 20 69 73 20 77 69  ue for "i" is wi
1850: 74 68 69 6e 20 72 61 6e 67 65 20 6f 66 20 74 68  thin range of th
1860: 65 20 42 69 74 76 65 63 20 6f 62 6a 65 63 74 2e  e Bitvec object.
1870: 0a 2a 2a 20 4f 74 68 65 72 77 69 73 65 20 74 68  .** Otherwise th
1880: 65 20 62 65 68 61 76 69 6f 72 20 69 73 20 75 6e  e behavior is un
1890: 64 65 66 69 6e 65 64 2e 0a 2a 2f 0a 69 6e 74 20  defined..*/.int 
18a0: 73 71 6c 69 74 65 33 42 69 74 76 65 63 53 65 74  sqlite3BitvecSet
18b0: 28 42 69 74 76 65 63 20 2a 70 2c 20 75 33 32 20  (Bitvec *p, u32 
18c0: 69 29 7b 0a 20 20 75 33 32 20 68 3b 0a 20 20 69  i){.  u32 h;.  i
18d0: 66 28 20 70 3d 3d 30 20 29 20 72 65 74 75 72 6e  f( p==0 ) return
18e0: 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 20 20 61 73   SQLITE_OK;.  as
18f0: 73 65 72 74 28 20 69 3e 30 20 29 3b 0a 20 20 61  sert( i>0 );.  a
1900: 73 73 65 72 74 28 20 69 3c 3d 70 2d 3e 69 53 69  ssert( i<=p->iSi
1910: 7a 65 20 29 3b 0a 20 20 69 2d 2d 3b 0a 20 20 77  ze );.  i--;.  w
1920: 68 69 6c 65 28 28 70 2d 3e 69 53 69 7a 65 20 3e  hile((p->iSize >
1930: 20 42 49 54 56 45 43 5f 4e 42 49 54 29 20 26 26   BITVEC_NBIT) &&
1940: 20 70 2d 3e 69 44 69 76 69 73 6f 72 29 20 7b 0a   p->iDivisor) {.
1950: 20 20 20 20 75 33 32 20 62 69 6e 20 3d 20 69 2f      u32 bin = i/
1960: 70 2d 3e 69 44 69 76 69 73 6f 72 3b 0a 20 20 20  p->iDivisor;.   
1970: 20 69 20 3d 20 69 25 70 2d 3e 69 44 69 76 69 73   i = i%p->iDivis
1980: 6f 72 3b 0a 20 20 20 20 69 66 28 20 70 2d 3e 75  or;.    if( p->u
1990: 2e 61 70 53 75 62 5b 62 69 6e 5d 3d 3d 30 20 29  .apSub[bin]==0 )
19a0: 7b 0a 20 20 20 20 20 20 70 2d 3e 75 2e 61 70 53  {.      p->u.apS
19b0: 75 62 5b 62 69 6e 5d 20 3d 20 73 71 6c 69 74 65  ub[bin] = sqlite
19c0: 33 42 69 74 76 65 63 43 72 65 61 74 65 28 20 70  3BitvecCreate( p
19d0: 2d 3e 69 44 69 76 69 73 6f 72 20 29 3b 0a 20 20  ->iDivisor );.  
19e0: 20 20 20 20 69 66 28 20 70 2d 3e 75 2e 61 70 53      if( p->u.apS
19f0: 75 62 5b 62 69 6e 5d 3d 3d 30 20 29 20 72 65 74  ub[bin]==0 ) ret
1a00: 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d  urn SQLITE_NOMEM
1a10: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 70 20 3d 20  ;.    }.    p = 
1a20: 70 2d 3e 75 2e 61 70 53 75 62 5b 62 69 6e 5d 3b  p->u.apSub[bin];
1a30: 0a 20 20 7d 0a 20 20 69 66 28 20 70 2d 3e 69 53  .  }.  if( p->iS
1a40: 69 7a 65 3c 3d 42 49 54 56 45 43 5f 4e 42 49 54  ize<=BITVEC_NBIT
1a50: 20 29 7b 0a 20 20 20 20 70 2d 3e 75 2e 61 42 69   ){.    p->u.aBi
1a60: 74 6d 61 70 5b 69 2f 42 49 54 56 45 43 5f 53 5a  tmap[i/BITVEC_SZ
1a70: 45 4c 45 4d 5d 20 7c 3d 20 31 20 3c 3c 20 28 69  ELEM] |= 1 << (i
1a80: 26 28 42 49 54 56 45 43 5f 53 5a 45 4c 45 4d 2d  &(BITVEC_SZELEM-
1a90: 31 29 29 3b 0a 20 20 20 20 72 65 74 75 72 6e 20  1));.    return 
1aa0: 53 51 4c 49 54 45 5f 4f 4b 3b 0a 20 20 7d 0a 20  SQLITE_OK;.  }. 
1ab0: 20 68 20 3d 20 42 49 54 56 45 43 5f 48 41 53 48   h = BITVEC_HASH
1ac0: 28 69 2b 2b 29 3b 0a 20 20 2f 2a 20 69 66 20 74  (i++);.  /* if t
1ad0: 68 65 72 65 20 77 61 73 6e 27 74 20 61 20 68 61  here wasn't a ha
1ae0: 73 68 20 63 6f 6c 6c 69 73 69 6f 6e 2c 20 61 6e  sh collision, an
1af0: 64 20 74 68 69 73 20 64 6f 65 73 6e 27 74 20 2a  d this doesn't *
1b00: 2f 0a 20 20 2f 2a 20 63 6f 6d 70 6c 65 74 65 6c  /.  /* completel
1b10: 79 20 66 69 6c 6c 20 74 68 65 20 68 61 73 68 2c  y fill the hash,
1b20: 20 74 68 65 6e 20 6a 75 73 74 20 61 64 64 20 69   then just add i
1b30: 74 20 77 69 74 68 6f 75 74 20 2a 2f 0a 20 20 2f  t without */.  /
1b40: 2a 20 77 6f 72 72 69 6e 67 20 61 62 6f 75 74 20  * worring about 
1b50: 73 75 62 2d 64 69 76 69 64 69 6e 67 20 61 6e 64  sub-dividing and
1b60: 20 72 65 2d 68 61 73 68 69 6e 67 2e 20 2a 2f 0a   re-hashing. */.
1b70: 20 20 69 66 28 20 21 70 2d 3e 75 2e 61 48 61 73    if( !p->u.aHas
1b80: 68 5b 68 5d 20 29 7b 0a 20 20 20 20 69 66 20 28  h[h] ){.    if (
1b90: 70 2d 3e 6e 53 65 74 3c 28 42 49 54 56 45 43 5f  p->nSet<(BITVEC_
1ba0: 4e 49 4e 54 2d 31 29 29 20 7b 0a 20 20 20 20 20  NINT-1)) {.     
1bb0: 20 67 6f 74 6f 20 62 69 74 76 65 63 5f 73 65 74   goto bitvec_set
1bc0: 5f 65 6e 64 3b 0a 20 20 20 20 7d 20 65 6c 73 65  _end;.    } else
1bd0: 20 7b 0a 20 20 20 20 20 20 67 6f 74 6f 20 62 69   {.      goto bi
1be0: 74 76 65 63 5f 73 65 74 5f 72 65 68 61 73 68 3b  tvec_set_rehash;
1bf0: 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 2f 2a 20  .    }.  }.  /* 
1c00: 74 68 65 72 65 20 77 61 73 20 61 20 63 6f 6c 6c  there was a coll
1c10: 69 73 69 6f 6e 2c 20 63 68 65 63 6b 20 74 6f 20  ision, check to 
1c20: 73 65 65 20 69 66 20 69 74 27 73 20 61 6c 72 65  see if it's alre
1c30: 61 64 79 20 2a 2f 0a 20 20 2f 2a 20 69 6e 20 68  ady */.  /* in h
1c40: 61 73 68 2c 20 69 66 20 6e 6f 74 2c 20 74 72 79  ash, if not, try
1c50: 20 74 6f 20 66 69 6e 64 20 61 20 73 70 6f 74 20   to find a spot 
1c60: 66 6f 72 20 69 74 20 2a 2f 0a 20 20 64 6f 20 7b  for it */.  do {
1c70: 0a 20 20 20 20 69 66 28 20 70 2d 3e 75 2e 61 48  .    if( p->u.aH
1c80: 61 73 68 5b 68 5d 3d 3d 69 20 29 20 72 65 74 75  ash[h]==i ) retu
1c90: 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 20 20  rn SQLITE_OK;.  
1ca0: 20 20 68 2b 2b 3b 0a 20 20 20 20 69 66 28 20 68    h++;.    if( h
1cb0: 3e 3d 42 49 54 56 45 43 5f 4e 49 4e 54 20 29 20  >=BITVEC_NINT ) 
1cc0: 68 20 3d 20 30 3b 0a 20 20 7d 20 77 68 69 6c 65  h = 0;.  } while
1cd0: 28 20 70 2d 3e 75 2e 61 48 61 73 68 5b 68 5d 20  ( p->u.aHash[h] 
1ce0: 29 3b 0a 20 20 2f 2a 20 77 65 20 64 69 64 6e 27  );.  /* we didn'
1cf0: 74 20 66 69 6e 64 20 69 74 20 69 6e 20 74 68 65  t find it in the
1d00: 20 68 61 73 68 2e 20 20 68 20 70 6f 69 6e 74 73   hash.  h points
1d10: 20 74 6f 20 74 68 65 20 66 69 72 73 74 20 2a 2f   to the first */
1d20: 0a 20 20 2f 2a 20 61 76 61 69 6c 61 62 6c 65 20  .  /* available 
1d30: 66 72 65 65 20 73 70 6f 74 2e 20 63 68 65 63 6b  free spot. check
1d40: 20 74 6f 20 73 65 65 20 69 66 20 74 68 69 73 20   to see if this 
1d50: 69 73 20 67 6f 69 6e 67 20 74 6f 20 2a 2f 0a 20  is going to */. 
1d60: 20 2f 2a 20 6d 61 6b 65 20 6f 75 72 20 68 61 73   /* make our has
1d70: 68 20 74 6f 6f 20 22 66 75 6c 6c 22 2e 20 20 2a  h too "full".  *
1d80: 2f 0a 62 69 74 76 65 63 5f 73 65 74 5f 72 65 68  /.bitvec_set_reh
1d90: 61 73 68 3a 0a 20 20 69 66 28 20 70 2d 3e 6e 53  ash:.  if( p->nS
1da0: 65 74 3e 3d 42 49 54 56 45 43 5f 4d 58 48 41 53  et>=BITVEC_MXHAS
1db0: 48 20 29 7b 0a 20 20 20 20 75 6e 73 69 67 6e 65  H ){.    unsigne
1dc0: 64 20 69 6e 74 20 6a 3b 0a 20 20 20 20 69 6e 74  d int j;.    int
1dd0: 20 72 63 3b 0a 20 20 20 20 75 33 32 20 2a 61 69   rc;.    u32 *ai
1de0: 56 61 6c 75 65 73 20 3d 20 73 71 6c 69 74 65 33  Values = sqlite3
1df0: 53 74 61 63 6b 41 6c 6c 6f 63 52 61 77 28 30 2c  StackAllocRaw(0,
1e00: 20 73 69 7a 65 6f 66 28 70 2d 3e 75 2e 61 48 61   sizeof(p->u.aHa
1e10: 73 68 29 29 3b 0a 20 20 20 20 69 66 28 20 61 69  sh));.    if( ai
1e20: 56 61 6c 75 65 73 3d 3d 30 20 29 7b 0a 20 20 20  Values==0 ){.   
1e30: 20 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45     return SQLITE
1e40: 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 7d 65 6c 73  _NOMEM;.    }els
1e50: 65 7b 0a 20 20 20 20 20 20 6d 65 6d 63 70 79 28  e{.      memcpy(
1e60: 61 69 56 61 6c 75 65 73 2c 20 70 2d 3e 75 2e 61  aiValues, p->u.a
1e70: 48 61 73 68 2c 20 73 69 7a 65 6f 66 28 70 2d 3e  Hash, sizeof(p->
1e80: 75 2e 61 48 61 73 68 29 29 3b 0a 20 20 20 20 20  u.aHash));.     
1e90: 20 6d 65 6d 73 65 74 28 70 2d 3e 75 2e 61 70 53   memset(p->u.apS
1ea0: 75 62 2c 20 30 2c 20 73 69 7a 65 6f 66 28 70 2d  ub, 0, sizeof(p-
1eb0: 3e 75 2e 61 70 53 75 62 29 29 3b 0a 20 20 20 20  >u.apSub));.    
1ec0: 20 20 70 2d 3e 69 44 69 76 69 73 6f 72 20 3d 20    p->iDivisor = 
1ed0: 28 70 2d 3e 69 53 69 7a 65 20 2b 20 42 49 54 56  (p->iSize + BITV
1ee0: 45 43 5f 4e 50 54 52 20 2d 20 31 29 2f 42 49 54  EC_NPTR - 1)/BIT
1ef0: 56 45 43 5f 4e 50 54 52 3b 0a 20 20 20 20 20 20  VEC_NPTR;.      
1f00: 72 63 20 3d 20 73 71 6c 69 74 65 33 42 69 74 76  rc = sqlite3Bitv
1f10: 65 63 53 65 74 28 70 2c 20 69 29 3b 0a 20 20 20  ecSet(p, i);.   
1f20: 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a 3c 42 49     for(j=0; j<BI
1f30: 54 56 45 43 5f 4e 49 4e 54 3b 20 6a 2b 2b 29 7b  TVEC_NINT; j++){
1f40: 0a 20 20 20 20 20 20 20 20 69 66 28 20 61 69 56  .        if( aiV
1f50: 61 6c 75 65 73 5b 6a 5d 20 29 20 72 63 20 7c 3d  alues[j] ) rc |=
1f60: 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 53 65   sqlite3BitvecSe
1f70: 74 28 70 2c 20 61 69 56 61 6c 75 65 73 5b 6a 5d  t(p, aiValues[j]
1f80: 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20  );.      }.     
1f90: 20 73 71 6c 69 74 65 33 53 74 61 63 6b 46 72 65   sqlite3StackFre
1fa0: 65 28 30 2c 20 61 69 56 61 6c 75 65 73 29 3b 0a  e(0, aiValues);.
1fb0: 20 20 20 20 20 20 72 65 74 75 72 6e 20 72 63 3b        return rc;
1fc0: 0a 20 20 20 20 7d 0a 20 20 7d 0a 62 69 74 76 65  .    }.  }.bitve
1fd0: 63 5f 73 65 74 5f 65 6e 64 3a 0a 20 20 70 2d 3e  c_set_end:.  p->
1fe0: 6e 53 65 74 2b 2b 3b 0a 20 20 70 2d 3e 75 2e 61  nSet++;.  p->u.a
1ff0: 48 61 73 68 5b 68 5d 20 3d 20 69 3b 0a 20 20 72  Hash[h] = i;.  r
2000: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b  eturn SQLITE_OK;
2010: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 6c 65 61 72 20  .}../*.** Clear 
2020: 74 68 65 20 69 2d 74 68 20 62 69 74 2e 0a 2a 2a  the i-th bit..**
2030: 0a 2a 2a 20 70 42 75 66 20 6d 75 73 74 20 62 65  .** pBuf must be
2040: 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 74   a pointer to at
2050: 20 6c 65 61 73 74 20 42 49 54 56 45 43 5f 53 5a   least BITVEC_SZ
2060: 20 62 79 74 65 73 20 6f 66 20 74 65 6d 70 6f 72   bytes of tempor
2070: 61 72 79 20 73 74 6f 72 61 67 65 0a 2a 2a 20 74  ary storage.** t
2080: 68 61 74 20 42 69 74 76 65 63 43 6c 65 61 72 20  hat BitvecClear 
2090: 63 61 6e 20 75 73 65 20 74 6f 20 72 65 62 75 69  can use to rebui
20a0: 6c 74 20 69 74 73 20 68 61 73 68 20 74 61 62 6c  lt its hash tabl
20b0: 65 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74  e..*/.void sqlit
20c0: 65 33 42 69 74 76 65 63 43 6c 65 61 72 28 42 69  e3BitvecClear(Bi
20d0: 74 76 65 63 20 2a 70 2c 20 75 33 32 20 69 2c 20  tvec *p, u32 i, 
20e0: 76 6f 69 64 20 2a 70 42 75 66 29 7b 0a 20 20 69  void *pBuf){.  i
20f0: 66 28 20 70 3d 3d 30 20 29 20 72 65 74 75 72 6e  f( p==0 ) return
2100: 3b 0a 20 20 61 73 73 65 72 74 28 20 69 3e 30 20  ;.  assert( i>0 
2110: 29 3b 0a 20 20 69 2d 2d 3b 0a 20 20 77 68 69 6c  );.  i--;.  whil
2120: 65 28 20 70 2d 3e 69 44 69 76 69 73 6f 72 20 29  e( p->iDivisor )
2130: 7b 0a 20 20 20 20 75 33 32 20 62 69 6e 20 3d 20  {.    u32 bin = 
2140: 69 2f 70 2d 3e 69 44 69 76 69 73 6f 72 3b 0a 20  i/p->iDivisor;. 
2150: 20 20 20 69 20 3d 20 69 25 70 2d 3e 69 44 69 76     i = i%p->iDiv
2160: 69 73 6f 72 3b 0a 20 20 20 20 70 20 3d 20 70 2d  isor;.    p = p-
2170: 3e 75 2e 61 70 53 75 62 5b 62 69 6e 5d 3b 0a 20  >u.apSub[bin];. 
2180: 20 20 20 69 66 20 28 21 70 29 20 7b 0a 20 20 20     if (!p) {.   
2190: 20 20 20 72 65 74 75 72 6e 3b 0a 20 20 20 20 7d     return;.    }
21a0: 0a 20 20 7d 0a 20 20 69 66 28 20 70 2d 3e 69 53  .  }.  if( p->iS
21b0: 69 7a 65 3c 3d 42 49 54 56 45 43 5f 4e 42 49 54  ize<=BITVEC_NBIT
21c0: 20 29 7b 0a 20 20 20 20 70 2d 3e 75 2e 61 42 69   ){.    p->u.aBi
21d0: 74 6d 61 70 5b 69 2f 42 49 54 56 45 43 5f 53 5a  tmap[i/BITVEC_SZ
21e0: 45 4c 45 4d 5d 20 26 3d 20 7e 28 31 20 3c 3c 20  ELEM] &= ~(1 << 
21f0: 28 69 26 28 42 49 54 56 45 43 5f 53 5a 45 4c 45  (i&(BITVEC_SZELE
2200: 4d 2d 31 29 29 29 3b 0a 20 20 7d 65 6c 73 65 7b  M-1)));.  }else{
2210: 0a 20 20 20 20 75 6e 73 69 67 6e 65 64 20 69 6e  .    unsigned in
2220: 74 20 6a 3b 0a 20 20 20 20 75 33 32 20 2a 61 69  t j;.    u32 *ai
2230: 56 61 6c 75 65 73 20 3d 20 70 42 75 66 3b 0a 20  Values = pBuf;. 
2240: 20 20 20 6d 65 6d 63 70 79 28 61 69 56 61 6c 75     memcpy(aiValu
2250: 65 73 2c 20 70 2d 3e 75 2e 61 48 61 73 68 2c 20  es, p->u.aHash, 
2260: 73 69 7a 65 6f 66 28 70 2d 3e 75 2e 61 48 61 73  sizeof(p->u.aHas
2270: 68 29 29 3b 0a 20 20 20 20 6d 65 6d 73 65 74 28  h));.    memset(
2280: 70 2d 3e 75 2e 61 48 61 73 68 2c 20 30 2c 20 73  p->u.aHash, 0, s
2290: 69 7a 65 6f 66 28 70 2d 3e 75 2e 61 48 61 73 68  izeof(p->u.aHash
22a0: 29 29 3b 0a 20 20 20 20 70 2d 3e 6e 53 65 74 20  ));.    p->nSet 
22b0: 3d 20 30 3b 0a 20 20 20 20 66 6f 72 28 6a 3d 30  = 0;.    for(j=0
22c0: 3b 20 6a 3c 42 49 54 56 45 43 5f 4e 49 4e 54 3b  ; j<BITVEC_NINT;
22d0: 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 69 66 28   j++){.      if(
22e0: 20 61 69 56 61 6c 75 65 73 5b 6a 5d 20 26 26 20   aiValues[j] && 
22f0: 61 69 56 61 6c 75 65 73 5b 6a 5d 21 3d 28 69 2b  aiValues[j]!=(i+
2300: 31 29 20 29 7b 0a 20 20 20 20 20 20 20 20 75 33  1) ){.        u3
2310: 32 20 68 20 3d 20 42 49 54 56 45 43 5f 48 41 53  2 h = BITVEC_HAS
2320: 48 28 61 69 56 61 6c 75 65 73 5b 6a 5d 2d 31 29  H(aiValues[j]-1)
2330: 3b 0a 20 20 20 20 20 20 20 20 70 2d 3e 6e 53 65  ;.        p->nSe
2340: 74 2b 2b 3b 0a 20 20 20 20 20 20 20 20 77 68 69  t++;.        whi
2350: 6c 65 28 20 70 2d 3e 75 2e 61 48 61 73 68 5b 68  le( p->u.aHash[h
2360: 5d 20 29 7b 0a 20 20 20 20 20 20 20 20 20 20 68  ] ){.          h
2370: 2b 2b 3b 0a 20 20 20 20 20 20 20 20 20 20 69 66  ++;.          if
2380: 28 20 68 3e 3d 42 49 54 56 45 43 5f 4e 49 4e 54  ( h>=BITVEC_NINT
2390: 20 29 20 68 20 3d 20 30 3b 0a 20 20 20 20 20 20   ) h = 0;.      
23a0: 20 20 7d 0a 20 20 20 20 20 20 20 20 70 2d 3e 75    }.        p->u
23b0: 2e 61 48 61 73 68 5b 68 5d 20 3d 20 61 69 56 61  .aHash[h] = aiVa
23c0: 6c 75 65 73 5b 6a 5d 3b 0a 20 20 20 20 20 20 7d  lues[j];.      }
23d0: 0a 20 20 20 20 7d 0a 20 20 7d 0a 7d 0a 0a 2f 2a  .    }.  }.}../*
23e0: 0a 2a 2a 20 44 65 73 74 72 6f 79 20 61 20 62 69  .** Destroy a bi
23f0: 74 6d 61 70 20 6f 62 6a 65 63 74 2e 20 20 52 65  tmap object.  Re
2400: 63 6c 61 69 6d 20 61 6c 6c 20 6d 65 6d 6f 72 79  claim all memory
2410: 20 75 73 65 64 2e 0a 2a 2f 0a 76 6f 69 64 20 73   used..*/.void s
2420: 71 6c 69 74 65 33 42 69 74 76 65 63 44 65 73 74  qlite3BitvecDest
2430: 72 6f 79 28 42 69 74 76 65 63 20 2a 70 29 7b 0a  roy(Bitvec *p){.
2440: 20 20 69 66 28 20 70 3d 3d 30 20 29 20 72 65 74    if( p==0 ) ret
2450: 75 72 6e 3b 0a 20 20 69 66 28 20 70 2d 3e 69 44  urn;.  if( p->iD
2460: 69 76 69 73 6f 72 20 29 7b 0a 20 20 20 20 75 6e  ivisor ){.    un
2470: 73 69 67 6e 65 64 20 69 6e 74 20 69 3b 0a 20 20  signed int i;.  
2480: 20 20 66 6f 72 28 69 3d 30 3b 20 69 3c 42 49 54    for(i=0; i<BIT
2490: 56 45 43 5f 4e 50 54 52 3b 20 69 2b 2b 29 7b 0a  VEC_NPTR; i++){.
24a0: 20 20 20 20 20 20 73 71 6c 69 74 65 33 42 69 74        sqlite3Bit
24b0: 76 65 63 44 65 73 74 72 6f 79 28 70 2d 3e 75 2e  vecDestroy(p->u.
24c0: 61 70 53 75 62 5b 69 5d 29 3b 0a 20 20 20 20 7d  apSub[i]);.    }
24d0: 0a 20 20 7d 0a 20 20 73 71 6c 69 74 65 33 5f 66  .  }.  sqlite3_f
24e0: 72 65 65 28 70 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  ree(p);.}../*.**
24f0: 20 52 65 74 75 72 6e 20 74 68 65 20 76 61 6c 75   Return the valu
2500: 65 20 6f 66 20 74 68 65 20 69 53 69 7a 65 20 70  e of the iSize p
2510: 61 72 61 6d 65 74 65 72 20 73 70 65 63 69 66 69  arameter specifi
2520: 65 64 20 77 68 65 6e 20 42 69 74 76 65 63 20 2a  ed when Bitvec *
2530: 70 0a 2a 2a 20 77 61 73 20 63 72 65 61 74 65 64  p.** was created
2540: 2e 0a 2a 2f 0a 75 33 32 20 73 71 6c 69 74 65 33  ..*/.u32 sqlite3
2550: 42 69 74 76 65 63 53 69 7a 65 28 42 69 74 76 65  BitvecSize(Bitve
2560: 63 20 2a 70 29 7b 0a 20 20 72 65 74 75 72 6e 20  c *p){.  return 
2570: 70 2d 3e 69 53 69 7a 65 3b 0a 7d 0a 0a 23 69 66  p->iSize;.}..#if
2580: 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54  ndef SQLITE_OMIT
2590: 5f 42 55 49 4c 54 49 4e 5f 54 45 53 54 0a 2f 2a  _BUILTIN_TEST./*
25a0: 0a 2a 2a 20 4c 65 74 20 56 5b 5d 20 62 65 20 61  .** Let V[] be a
25b0: 6e 20 61 72 72 61 79 20 6f 66 20 75 6e 73 69 67  n array of unsig
25c0: 6e 65 64 20 63 68 61 72 61 63 74 65 72 73 20 73  ned characters s
25d0: 75 66 66 69 63 69 65 6e 74 20 74 6f 20 68 6f 6c  ufficient to hol
25e0: 64 0a 2a 2a 20 75 70 20 74 6f 20 4e 20 62 69 74  d.** up to N bit
25f0: 73 2e 20 20 4c 65 74 20 49 20 62 65 20 61 6e 20  s.  Let I be an 
2600: 69 6e 74 65 67 65 72 20 62 65 74 77 65 65 6e 20  integer between 
2610: 30 20 61 6e 64 20 4e 2e 20 20 30 3c 3d 49 3c 4e  0 and N.  0<=I<N
2620: 2e 0a 2a 2a 20 54 68 65 6e 20 74 68 65 20 66 6f  ..** Then the fo
2630: 6c 6c 6f 77 69 6e 67 20 6d 61 63 72 6f 73 20 63  llowing macros c
2640: 61 6e 20 62 65 20 75 73 65 64 20 74 6f 20 73 65  an be used to se
2650: 74 2c 20 63 6c 65 61 72 2c 20 6f 72 20 74 65 73  t, clear, or tes
2660: 74 0a 2a 2a 20 69 6e 64 69 76 69 64 75 61 6c 20  t.** individual 
2670: 62 69 74 73 20 77 69 74 68 69 6e 20 56 2e 0a 2a  bits within V..*
2680: 2f 0a 23 64 65 66 69 6e 65 20 53 45 54 42 49 54  /.#define SETBIT
2690: 28 56 2c 49 29 20 20 20 20 20 20 56 5b 49 3e 3e  (V,I)      V[I>>
26a0: 33 5d 20 7c 3d 20 28 31 3c 3c 28 49 26 37 29 29  3] |= (1<<(I&7))
26b0: 0a 23 64 65 66 69 6e 65 20 43 4c 45 41 52 42 49  .#define CLEARBI
26c0: 54 28 56 2c 49 29 20 20 20 20 56 5b 49 3e 3e 33  T(V,I)    V[I>>3
26d0: 5d 20 26 3d 20 7e 28 31 3c 3c 28 49 26 37 29 29  ] &= ~(1<<(I&7))
26e0: 0a 23 64 65 66 69 6e 65 20 54 45 53 54 42 49 54  .#define TESTBIT
26f0: 28 56 2c 49 29 20 20 20 20 20 28 56 5b 49 3e 3e  (V,I)     (V[I>>
2700: 33 5d 26 28 31 3c 3c 28 49 26 37 29 29 29 21 3d  3]&(1<<(I&7)))!=
2710: 30 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20 72 6f  0../*.** This ro
2720: 75 74 69 6e 65 20 72 75 6e 73 20 61 6e 20 65 78  utine runs an ex
2730: 74 65 6e 73 69 76 65 20 74 65 73 74 20 6f 66 20  tensive test of 
2740: 74 68 65 20 42 69 74 76 65 63 20 63 6f 64 65 2e  the Bitvec code.
2750: 0a 2a 2a 0a 2a 2a 20 54 68 65 20 69 6e 70 75 74  .**.** The input
2760: 20 69 73 20 61 6e 20 61 72 72 61 79 20 6f 66 20   is an array of 
2770: 69 6e 74 65 67 65 72 73 20 74 68 61 74 20 61 63  integers that ac
2780: 74 73 20 61 73 20 61 20 70 72 6f 67 72 61 6d 0a  ts as a program.
2790: 2a 2a 20 74 6f 20 74 65 73 74 20 74 68 65 20 42  ** to test the B
27a0: 69 74 76 65 63 2e 20 20 54 68 65 20 69 6e 74 65  itvec.  The inte
27b0: 67 65 72 73 20 61 72 65 20 6f 70 63 6f 64 65 73  gers are opcodes
27c0: 20 66 6f 6c 6c 6f 77 65 64 0a 2a 2a 20 62 79 20   followed.** by 
27d0: 30 2c 20 31 2c 20 6f 72 20 33 20 6f 70 65 72 61  0, 1, or 3 opera
27e0: 6e 64 73 2c 20 64 65 70 65 6e 64 69 6e 67 20 6f  nds, depending o
27f0: 6e 20 74 68 65 20 6f 70 63 6f 64 65 2e 20 20 41  n the opcode.  A
2800: 6e 6f 74 68 65 72 0a 2a 2a 20 6f 70 63 6f 64 65  nother.** opcode
2810: 20 66 6f 6c 6c 6f 77 73 20 69 6d 6d 65 64 69 61   follows immedia
2820: 74 65 6c 79 20 61 66 74 65 72 20 74 68 65 20 6c  tely after the l
2830: 61 73 74 20 6f 70 65 72 61 6e 64 2e 0a 2a 2a 0a  ast operand..**.
2840: 2a 2a 20 54 68 65 72 65 20 61 72 65 20 36 20 6f  ** There are 6 o
2850: 70 63 6f 64 65 73 20 6e 75 6d 62 65 72 65 64 20  pcodes numbered 
2860: 66 72 6f 6d 20 30 20 74 68 72 6f 75 67 68 20 35  from 0 through 5
2870: 2e 20 20 30 20 69 73 20 74 68 65 0a 2a 2a 20 22  .  0 is the.** "
2880: 68 61 6c 74 22 20 6f 70 63 6f 64 65 20 61 6e 64  halt" opcode and
2890: 20 63 61 75 73 65 73 20 74 68 65 20 74 65 73 74   causes the test
28a0: 20 74 6f 20 65 6e 64 2e 0a 2a 2a 0a 2a 2a 20 20   to end..**.**  
28b0: 20 20 30 20 20 20 20 20 20 20 20 20 20 48 61 6c    0          Hal
28c0: 74 20 61 6e 64 20 72 65 74 75 72 6e 20 74 68 65  t and return the
28d0: 20 6e 75 6d 62 65 72 20 6f 66 20 65 72 72 6f 72   number of error
28e0: 73 0a 2a 2a 20 20 20 20 31 20 4e 20 53 20 58 20  s.**    1 N S X 
28f0: 20 20 20 53 65 74 20 4e 20 62 69 74 73 20 62 65     Set N bits be
2900: 67 69 6e 6e 69 6e 67 20 77 69 74 68 20 53 20 61  ginning with S a
2910: 6e 64 20 69 6e 63 72 65 6d 65 6e 74 69 6e 67 20  nd incrementing 
2920: 62 79 20 58 0a 2a 2a 20 20 20 20 32 20 4e 20 53  by X.**    2 N S
2930: 20 58 20 20 20 20 43 6c 65 61 72 20 4e 20 62 69   X    Clear N bi
2940: 74 73 20 62 65 67 69 6e 6e 69 6e 67 20 77 69 74  ts beginning wit
2950: 68 20 53 20 61 6e 64 20 69 6e 63 72 65 6d 65 6e  h S and incremen
2960: 74 69 6e 67 20 62 79 20 58 0a 2a 2a 20 20 20 20  ting by X.**    
2970: 33 20 4e 20 20 20 20 20 20 20 20 53 65 74 20 4e  3 N        Set N
2980: 20 72 61 6e 64 6f 6d 6c 79 20 63 68 6f 73 65 6e   randomly chosen
2990: 20 62 69 74 73 0a 2a 2a 20 20 20 20 34 20 4e 20   bits.**    4 N 
29a0: 20 20 20 20 20 20 20 43 6c 65 61 72 20 4e 20 72         Clear N r
29b0: 61 6e 64 6f 6d 6c 79 20 63 68 6f 73 65 6e 20 62  andomly chosen b
29c0: 69 74 73 0a 2a 2a 20 20 20 20 35 20 4e 20 53 20  its.**    5 N S 
29d0: 58 20 20 20 20 53 65 74 20 4e 20 62 69 74 73 20  X    Set N bits 
29e0: 66 72 6f 6d 20 53 20 69 6e 63 72 65 6d 65 6e 74  from S increment
29f0: 20 58 20 69 6e 20 61 72 72 61 79 20 6f 6e 6c 79   X in array only
2a00: 2c 20 6e 6f 74 20 69 6e 20 62 69 74 76 65 63 0a  , not in bitvec.
2a10: 2a 2a 0a 2a 2a 20 54 68 65 20 6f 70 63 6f 64 65  **.** The opcode
2a20: 73 20 31 20 74 68 72 6f 75 67 68 20 34 20 70 65  s 1 through 4 pe
2a30: 72 66 6f 72 6d 20 73 65 74 20 61 6e 64 20 63 6c  rform set and cl
2a40: 65 61 72 20 6f 70 65 72 61 74 69 6f 6e 73 20 61  ear operations a
2a50: 72 65 20 70 65 72 66 6f 72 6d 65 64 0a 2a 2a 20  re performed.** 
2a60: 6f 6e 20 62 6f 74 68 20 61 20 42 69 74 76 65 63  on both a Bitvec
2a70: 20 6f 62 6a 65 63 74 20 61 6e 64 20 6f 6e 20 61   object and on a
2a80: 20 6c 69 6e 65 61 72 20 61 72 72 61 79 20 6f 66   linear array of
2a90: 20 62 69 74 73 20 6f 62 74 61 69 6e 65 64 20 66   bits obtained f
2aa0: 72 6f 6d 20 6d 61 6c 6c 6f 63 2e 0a 2a 2a 20 4f  rom malloc..** O
2ab0: 70 63 6f 64 65 20 35 20 77 6f 72 6b 73 20 6f 6e  pcode 5 works on
2ac0: 20 74 68 65 20 6c 69 6e 65 61 72 20 61 72 72 61   the linear arra
2ad0: 79 20 6f 6e 6c 79 2c 20 6e 6f 74 20 6f 6e 20 74  y only, not on t
2ae0: 68 65 20 42 69 74 76 65 63 2e 0a 2a 2a 20 4f 70  he Bitvec..** Op
2af0: 63 6f 64 65 20 35 20 69 73 20 75 73 65 64 20 74  code 5 is used t
2b00: 6f 20 64 65 6c 69 62 65 72 61 74 65 6c 79 20 69  o deliberately i
2b10: 6e 64 75 63 65 20 61 20 66 61 75 6c 74 20 69 6e  nduce a fault in
2b20: 20 6f 72 64 65 72 20 74 6f 0a 2a 2a 20 63 6f 6e   order to.** con
2b30: 66 69 72 6d 20 74 68 61 74 20 65 72 72 6f 72 20  firm that error 
2b40: 64 65 74 65 63 74 69 6f 6e 20 77 6f 72 6b 73 2e  detection works.
2b50: 0a 2a 2a 0a 2a 2a 20 41 74 20 74 68 65 20 63 6f  .**.** At the co
2b60: 6e 63 6c 75 73 69 6f 6e 20 6f 66 20 74 68 65 20  nclusion of the 
2b70: 74 65 73 74 20 74 68 65 20 6c 69 6e 65 61 72 20  test the linear 
2b80: 61 72 72 61 79 20 69 73 20 63 6f 6d 70 61 72 65  array is compare
2b90: 64 0a 2a 2a 20 61 67 61 69 6e 73 74 20 74 68 65  d.** against the
2ba0: 20 42 69 74 76 65 63 20 6f 62 6a 65 63 74 2e 20   Bitvec object. 
2bb0: 20 49 66 20 74 68 65 72 65 20 61 72 65 20 61 6e   If there are an
2bc0: 79 20 64 69 66 66 65 72 65 6e 63 65 73 2c 0a 2a  y differences,.*
2bd0: 2a 20 61 6e 20 65 72 72 6f 72 20 69 73 20 72 65  * an error is re
2be0: 74 75 72 6e 65 64 2e 20 20 49 66 20 74 68 65 79  turned.  If they
2bf0: 20 61 72 65 20 74 68 65 20 73 61 6d 65 2c 20 7a   are the same, z
2c00: 65 72 6f 20 69 73 20 72 65 74 75 72 6e 65 64 2e  ero is returned.
2c10: 0a 2a 2a 0a 2a 2a 20 49 66 20 61 20 6d 65 6d 6f  .**.** If a memo
2c20: 72 79 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 65 72  ry allocation er
2c30: 72 6f 72 20 6f 63 63 75 72 73 2c 20 72 65 74 75  ror occurs, retu
2c40: 72 6e 20 2d 31 2e 0a 2a 2f 0a 69 6e 74 20 73 71  rn -1..*/.int sq
2c50: 6c 69 74 65 33 42 69 74 76 65 63 42 75 69 6c 74  lite3BitvecBuilt
2c60: 69 6e 54 65 73 74 28 69 6e 74 20 73 7a 2c 20 69  inTest(int sz, i
2c70: 6e 74 20 2a 61 4f 70 29 7b 0a 20 20 42 69 74 76  nt *aOp){.  Bitv
2c80: 65 63 20 2a 70 42 69 74 76 65 63 20 3d 20 30 3b  ec *pBitvec = 0;
2c90: 0a 20 20 75 6e 73 69 67 6e 65 64 20 63 68 61 72  .  unsigned char
2ca0: 20 2a 70 56 20 3d 20 30 3b 0a 20 20 69 6e 74 20   *pV = 0;.  int 
2cb0: 72 63 20 3d 20 2d 31 3b 0a 20 20 69 6e 74 20 69  rc = -1;.  int i
2cc0: 2c 20 6e 78 2c 20 70 63 2c 20 6f 70 3b 0a 20 20  , nx, pc, op;.  
2cd0: 76 6f 69 64 20 2a 70 54 6d 70 53 70 61 63 65 3b  void *pTmpSpace;
2ce0: 0a 0a 20 20 2f 2a 20 41 6c 6c 6f 63 61 74 65 20  ..  /* Allocate 
2cf0: 74 68 65 20 42 69 74 76 65 63 20 74 6f 20 62 65  the Bitvec to be
2d00: 20 74 65 73 74 65 64 20 61 6e 64 20 61 20 6c 69   tested and a li
2d10: 6e 65 61 72 20 61 72 72 61 79 20 6f 66 0a 20 20  near array of.  
2d20: 2a 2a 20 62 69 74 73 20 74 6f 20 61 63 74 20 61  ** bits to act a
2d30: 73 20 74 68 65 20 72 65 66 65 72 65 6e 63 65 20  s the reference 
2d40: 2a 2f 0a 20 20 70 42 69 74 76 65 63 20 3d 20 73  */.  pBitvec = s
2d50: 71 6c 69 74 65 33 42 69 74 76 65 63 43 72 65 61  qlite3BitvecCrea
2d60: 74 65 28 20 73 7a 20 29 3b 0a 20 20 70 56 20 3d  te( sz );.  pV =
2d70: 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28   sqlite3_malloc(
2d80: 20 28 73 7a 2b 37 29 2f 38 20 2b 20 31 20 29 3b   (sz+7)/8 + 1 );
2d90: 0a 20 20 70 54 6d 70 53 70 61 63 65 20 3d 20 73  .  pTmpSpace = s
2da0: 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 42 49  qlite3_malloc(BI
2db0: 54 56 45 43 5f 53 5a 29 3b 0a 20 20 69 66 28 20  TVEC_SZ);.  if( 
2dc0: 70 42 69 74 76 65 63 3d 3d 30 20 7c 7c 20 70 56  pBitvec==0 || pV
2dd0: 3d 3d 30 20 7c 7c 20 70 54 6d 70 53 70 61 63 65  ==0 || pTmpSpace
2de0: 3d 3d 30 20 20 29 20 67 6f 74 6f 20 62 69 74 76  ==0  ) goto bitv
2df0: 65 63 5f 65 6e 64 3b 0a 20 20 6d 65 6d 73 65 74  ec_end;.  memset
2e00: 28 70 56 2c 20 30 2c 20 28 73 7a 2b 37 29 2f 38  (pV, 0, (sz+7)/8
2e10: 20 2b 20 31 29 3b 0a 0a 20 20 2f 2a 20 4e 55 4c   + 1);..  /* NUL
2e20: 4c 20 70 42 69 74 76 65 63 20 74 65 73 74 73 20  L pBitvec tests 
2e30: 2a 2f 0a 20 20 73 71 6c 69 74 65 33 42 69 74 76  */.  sqlite3Bitv
2e40: 65 63 53 65 74 28 30 2c 20 31 29 3b 0a 20 20 73  ecSet(0, 1);.  s
2e50: 71 6c 69 74 65 33 42 69 74 76 65 63 43 6c 65 61  qlite3BitvecClea
2e60: 72 28 30 2c 20 31 2c 20 70 54 6d 70 53 70 61 63  r(0, 1, pTmpSpac
2e70: 65 29 3b 0a 0a 20 20 2f 2a 20 52 75 6e 20 74 68  e);..  /* Run th
2e80: 65 20 70 72 6f 67 72 61 6d 20 2a 2f 0a 20 20 70  e program */.  p
2e90: 63 20 3d 20 30 3b 0a 20 20 77 68 69 6c 65 28 20  c = 0;.  while( 
2ea0: 28 6f 70 20 3d 20 61 4f 70 5b 70 63 5d 29 21 3d  (op = aOp[pc])!=
2eb0: 30 20 29 7b 0a 20 20 20 20 73 77 69 74 63 68 28  0 ){.    switch(
2ec0: 20 6f 70 20 29 7b 0a 20 20 20 20 20 20 63 61 73   op ){.      cas
2ed0: 65 20 31 3a 0a 20 20 20 20 20 20 63 61 73 65 20  e 1:.      case 
2ee0: 32 3a 0a 20 20 20 20 20 20 63 61 73 65 20 35 3a  2:.      case 5:
2ef0: 20 7b 0a 20 20 20 20 20 20 20 20 6e 78 20 3d 20   {.        nx = 
2f00: 34 3b 0a 20 20 20 20 20 20 20 20 69 20 3d 20 61  4;.        i = a
2f10: 4f 70 5b 70 63 2b 32 5d 20 2d 20 31 3b 0a 20 20  Op[pc+2] - 1;.  
2f20: 20 20 20 20 20 20 61 4f 70 5b 70 63 2b 32 5d 20        aOp[pc+2] 
2f30: 2b 3d 20 61 4f 70 5b 70 63 2b 33 5d 3b 0a 20 20  += aOp[pc+3];.  
2f40: 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20        break;.   
2f50: 20 20 20 7d 0a 20 20 20 20 20 20 63 61 73 65 20     }.      case 
2f60: 33 3a 0a 20 20 20 20 20 20 63 61 73 65 20 34 3a  3:.      case 4:
2f70: 20 0a 20 20 20 20 20 20 64 65 66 61 75 6c 74 3a   .      default:
2f80: 20 7b 0a 20 20 20 20 20 20 20 20 6e 78 20 3d 20   {.        nx = 
2f90: 32 3b 0a 20 20 20 20 20 20 20 20 73 71 6c 69 74  2;.        sqlit
2fa0: 65 33 5f 72 61 6e 64 6f 6d 6e 65 73 73 28 73 69  e3_randomness(si
2fb0: 7a 65 6f 66 28 69 29 2c 20 26 69 29 3b 0a 20 20  zeof(i), &i);.  
2fc0: 20 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20        break;.   
2fd0: 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 20 20 69     }.    }.    i
2fe0: 66 28 20 28 2d 2d 61 4f 70 5b 70 63 2b 31 5d 29  f( (--aOp[pc+1])
2ff0: 20 3e 20 30 20 29 20 6e 78 20 3d 20 30 3b 0a 20   > 0 ) nx = 0;. 
3000: 20 20 20 70 63 20 2b 3d 20 6e 78 3b 0a 20 20 20     pc += nx;.   
3010: 20 69 20 3d 20 28 69 20 26 20 30 78 37 66 66 66   i = (i & 0x7fff
3020: 66 66 66 66 29 25 73 7a 3b 0a 20 20 20 20 69 66  ffff)%sz;.    if
3030: 28 20 28 6f 70 20 26 20 31 29 21 3d 30 20 29 7b  ( (op & 1)!=0 ){
3040: 0a 20 20 20 20 20 20 53 45 54 42 49 54 28 70 56  .      SETBIT(pV
3050: 2c 20 28 69 2b 31 29 29 3b 0a 20 20 20 20 20 20  , (i+1));.      
3060: 69 66 28 20 6f 70 21 3d 35 20 29 7b 0a 20 20 20  if( op!=5 ){.   
3070: 20 20 20 20 20 69 66 28 20 73 71 6c 69 74 65 33       if( sqlite3
3080: 42 69 74 76 65 63 53 65 74 28 70 42 69 74 76 65  BitvecSet(pBitve
3090: 63 2c 20 69 2b 31 29 20 29 20 67 6f 74 6f 20 62  c, i+1) ) goto b
30a0: 69 74 76 65 63 5f 65 6e 64 3b 0a 20 20 20 20 20  itvec_end;.     
30b0: 20 7d 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20   }.    }else{.  
30c0: 20 20 20 20 43 4c 45 41 52 42 49 54 28 70 56 2c      CLEARBIT(pV,
30d0: 20 28 69 2b 31 29 29 3b 0a 20 20 20 20 20 20 73   (i+1));.      s
30e0: 71 6c 69 74 65 33 42 69 74 76 65 63 43 6c 65 61  qlite3BitvecClea
30f0: 72 28 70 42 69 74 76 65 63 2c 20 69 2b 31 2c 20  r(pBitvec, i+1, 
3100: 70 54 6d 70 53 70 61 63 65 29 3b 0a 20 20 20 20  pTmpSpace);.    
3110: 7d 0a 20 20 7d 0a 0a 20 20 2f 2a 20 54 65 73 74  }.  }..  /* Test
3120: 20 74 6f 20 6d 61 6b 65 20 73 75 72 65 20 74 68   to make sure th
3130: 65 20 6c 69 6e 65 61 72 20 61 72 72 61 79 20 65  e linear array e
3140: 78 61 63 74 6c 79 20 6d 61 74 63 68 65 73 20 74  xactly matches t
3150: 68 65 0a 20 20 2a 2a 20 42 69 74 76 65 63 20 6f  he.  ** Bitvec o
3160: 62 6a 65 63 74 2e 20 20 53 74 61 72 74 20 77 69  bject.  Start wi
3170: 74 68 20 74 68 65 20 61 73 73 75 6d 70 74 69 6f  th the assumptio
3180: 6e 20 74 68 61 74 20 74 68 65 79 20 64 6f 0a 20  n that they do. 
3190: 20 2a 2a 20 6d 61 74 63 68 20 28 72 63 3d 3d 30   ** match (rc==0
31a0: 29 2e 20 20 43 68 61 6e 67 65 20 72 63 20 74 6f  ).  Change rc to
31b0: 20 6e 6f 6e 2d 7a 65 72 6f 20 69 66 20 61 20 64   non-zero if a d
31c0: 69 73 63 72 65 70 61 6e 63 79 0a 20 20 2a 2a 20  iscrepancy.  ** 
31d0: 69 73 20 66 6f 75 6e 64 2e 0a 20 20 2a 2f 0a 20  is found..  */. 
31e0: 20 72 63 20 3d 20 73 71 6c 69 74 65 33 42 69 74   rc = sqlite3Bit
31f0: 76 65 63 54 65 73 74 28 30 2c 30 29 20 2b 20 73  vecTest(0,0) + s
3200: 71 6c 69 74 65 33 42 69 74 76 65 63 54 65 73 74  qlite3BitvecTest
3210: 28 70 42 69 74 76 65 63 2c 20 73 7a 2b 31 29 0a  (pBitvec, sz+1).
3220: 20 20 20 20 20 20 20 20 20 20 2b 20 73 71 6c 69            + sqli
3230: 74 65 33 42 69 74 76 65 63 54 65 73 74 28 70 42  te3BitvecTest(pB
3240: 69 74 76 65 63 2c 20 30 29 0a 20 20 20 20 20 20  itvec, 0).      
3250: 20 20 20 20 2b 20 28 73 71 6c 69 74 65 33 42 69      + (sqlite3Bi
3260: 74 76 65 63 53 69 7a 65 28 70 42 69 74 76 65 63  tvecSize(pBitvec
3270: 29 20 2d 20 73 7a 29 3b 0a 20 20 66 6f 72 28 69  ) - sz);.  for(i
3280: 3d 31 3b 20 69 3c 3d 73 7a 3b 20 69 2b 2b 29 7b  =1; i<=sz; i++){
3290: 0a 20 20 20 20 69 66 28 20 20 28 54 45 53 54 42  .    if(  (TESTB
32a0: 49 54 28 70 56 2c 69 29 29 21 3d 73 71 6c 69 74  IT(pV,i))!=sqlit
32b0: 65 33 42 69 74 76 65 63 54 65 73 74 28 70 42 69  e3BitvecTest(pBi
32c0: 74 76 65 63 2c 69 29 20 29 7b 0a 20 20 20 20 20  tvec,i) ){.     
32d0: 20 72 63 20 3d 20 69 3b 0a 20 20 20 20 20 20 62   rc = i;.      b
32e0: 72 65 61 6b 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a  reak;.    }.  }.
32f0: 0a 20 20 2f 2a 20 46 72 65 65 20 61 6c 6c 6f 63  .  /* Free alloc
3300: 61 74 65 64 20 73 74 72 75 63 74 75 72 65 20 2a  ated structure *
3310: 2f 0a 62 69 74 76 65 63 5f 65 6e 64 3a 0a 20 20  /.bitvec_end:.  
3320: 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70 54 6d  sqlite3_free(pTm
3330: 70 53 70 61 63 65 29 3b 0a 20 20 73 71 6c 69 74  pSpace);.  sqlit
3340: 65 33 5f 66 72 65 65 28 70 56 29 3b 0a 20 20 73  e3_free(pV);.  s
3350: 71 6c 69 74 65 33 42 69 74 76 65 63 44 65 73 74  qlite3BitvecDest
3360: 72 6f 79 28 70 42 69 74 76 65 63 29 3b 0a 20 20  roy(pBitvec);.  
3370: 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a 23 65 6e  return rc;.}.#en
3380: 64 69 66 20 2f 2a 20 53 51 4c 49 54 45 5f 4f 4d  dif /* SQLITE_OM
3390: 49 54 5f 42 55 49 4c 54 49 4e 5f 54 45 53 54 20  IT_BUILTIN_TEST 
33a0: 2a 2f 0a                                         */.