/ Hex Artifact Content
Login

Artifact fc0edcc2000f7d6faea86adcf9c2b8516882eb5aa2fc821fd2fd264e2cefde95:


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 5c 0a 20  BITVEC_USIZE \. 
0790: 20 20 20 28 28 28 42 49 54 56 45 43 5f 53 5a 2d     (((BITVEC_SZ-
07a0: 28 33 2a 73 69 7a 65 6f 66 28 75 33 32 29 29 29  (3*sizeof(u32)))
07b0: 2f 73 69 7a 65 6f 66 28 42 69 74 76 65 63 2a 29  /sizeof(Bitvec*)
07c0: 29 2a 73 69 7a 65 6f 66 28 42 69 74 76 65 63 2a  )*sizeof(Bitvec*
07d0: 29 29 0a 0a 2f 2a 20 54 79 70 65 20 6f 66 20 74  ))../* Type of t
07e0: 68 65 20 61 72 72 61 79 20 22 65 6c 65 6d 65 6e  he array "elemen
07f0: 74 22 20 66 6f 72 20 74 68 65 20 62 69 74 6d 61  t" for the bitma
0800: 70 20 72 65 70 72 65 73 65 6e 74 61 74 69 6f 6e  p representation
0810: 2e 20 0a 2a 2a 20 53 68 6f 75 6c 64 20 62 65 20  . .** Should be 
0820: 61 20 70 6f 77 65 72 20 6f 66 20 32 2c 20 61 6e  a power of 2, an
0830: 64 20 69 64 65 61 6c 6c 79 2c 20 65 76 65 6e 6c  d ideally, evenl
0840: 79 20 64 69 76 69 64 65 20 69 6e 74 6f 20 42 49  y divide into BI
0850: 54 56 45 43 5f 55 53 49 5a 45 2e 20 0a 2a 2a 20  TVEC_USIZE. .** 
0860: 53 65 74 74 69 6e 67 20 74 68 69 73 20 74 6f 20  Setting this to 
0870: 74 68 65 20 22 6e 61 74 75 72 61 6c 20 77 6f 72  the "natural wor
0880: 64 22 20 73 69 7a 65 20 6f 66 20 79 6f 75 72 20  d" size of your 
0890: 43 50 55 20 6d 61 79 20 69 6d 70 72 6f 76 65 0a  CPU may improve.
08a0: 2a 2a 20 70 65 72 66 6f 72 6d 61 6e 63 65 2e 20  ** performance. 
08b0: 2a 2f 0a 23 64 65 66 69 6e 65 20 42 49 54 56 45  */.#define BITVE
08c0: 43 5f 54 45 4c 45 4d 20 20 20 20 20 75 38 0a 2f  C_TELEM     u8./
08d0: 2a 20 53 69 7a 65 2c 20 69 6e 20 62 69 74 73 2c  * Size, in bits,
08e0: 20 6f 66 20 74 68 65 20 62 69 74 6d 61 70 20 65   of the bitmap e
08f0: 6c 65 6d 65 6e 74 2e 20 2a 2f 0a 23 64 65 66 69  lement. */.#defi
0900: 6e 65 20 42 49 54 56 45 43 5f 53 5a 45 4c 45 4d  ne BITVEC_SZELEM
0910: 20 20 20 20 38 0a 2f 2a 20 4e 75 6d 62 65 72 20      8./* Number 
0920: 6f 66 20 65 6c 65 6d 65 6e 74 73 20 69 6e 20 61  of elements in a
0930: 20 62 69 74 6d 61 70 20 61 72 72 61 79 2e 20 2a   bitmap array. *
0940: 2f 0a 23 64 65 66 69 6e 65 20 42 49 54 56 45 43  /.#define BITVEC
0950: 5f 4e 45 4c 45 4d 20 20 20 20 20 28 42 49 54 56  _NELEM     (BITV
0960: 45 43 5f 55 53 49 5a 45 2f 73 69 7a 65 6f 66 28  EC_USIZE/sizeof(
0970: 42 49 54 56 45 43 5f 54 45 4c 45 4d 29 29 0a 2f  BITVEC_TELEM))./
0980: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 62 69 74 73  * Number of bits
0990: 20 69 6e 20 74 68 65 20 62 69 74 6d 61 70 20 61   in the bitmap a
09a0: 72 72 61 79 2e 20 2a 2f 0a 23 64 65 66 69 6e 65  rray. */.#define
09b0: 20 42 49 54 56 45 43 5f 4e 42 49 54 20 20 20 20   BITVEC_NBIT    
09c0: 20 20 28 42 49 54 56 45 43 5f 4e 45 4c 45 4d 2a    (BITVEC_NELEM*
09d0: 42 49 54 56 45 43 5f 53 5a 45 4c 45 4d 29 0a 0a  BITVEC_SZELEM)..
09e0: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 75 33 32  /* Number of u32
09f0: 20 76 61 6c 75 65 73 20 69 6e 20 68 61 73 68 20   values in hash 
0a00: 74 61 62 6c 65 2e 20 2a 2f 0a 23 64 65 66 69 6e  table. */.#defin
0a10: 65 20 42 49 54 56 45 43 5f 4e 49 4e 54 20 20 20  e BITVEC_NINT   
0a20: 20 20 20 28 42 49 54 56 45 43 5f 55 53 49 5a 45     (BITVEC_USIZE
0a30: 2f 73 69 7a 65 6f 66 28 75 33 32 29 29 0a 2f 2a  /sizeof(u32))./*
0a40: 20 4d 61 78 69 6d 75 6d 20 6e 75 6d 62 65 72 20   Maximum number 
0a50: 6f 66 20 65 6e 74 72 69 65 73 20 69 6e 20 68 61  of entries in ha
0a60: 73 68 20 74 61 62 6c 65 20 62 65 66 6f 72 65 20  sh table before 
0a70: 0a 2a 2a 20 73 75 62 2d 64 69 76 69 64 69 6e 67  .** sub-dividing
0a80: 20 61 6e 64 20 72 65 2d 68 61 73 68 69 6e 67 2e   and re-hashing.
0a90: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 42 49 54 56   */.#define BITV
0aa0: 45 43 5f 4d 58 48 41 53 48 20 20 20 20 28 42 49  EC_MXHASH    (BI
0ab0: 54 56 45 43 5f 4e 49 4e 54 2f 32 29 0a 2f 2a 20  TVEC_NINT/2)./* 
0ac0: 48 61 73 68 69 6e 67 20 66 75 6e 63 74 69 6f 6e  Hashing function
0ad0: 20 66 6f 72 20 74 68 65 20 61 48 61 73 68 20 72   for the aHash r
0ae0: 65 70 72 65 73 65 6e 74 61 74 69 6f 6e 2e 0a 2a  epresentation..*
0af0: 2a 20 45 6d 70 69 72 69 63 61 6c 20 74 65 73 74  * Empirical test
0b00: 69 6e 67 20 73 68 6f 77 65 64 20 74 68 61 74 20  ing showed that 
0b10: 74 68 65 20 2a 33 37 20 6d 75 6c 74 69 70 6c 69  the *37 multipli
0b20: 65 72 20 0a 2a 2a 20 28 61 6e 20 61 72 62 69 74  er .** (an arbit
0b30: 72 61 72 79 20 70 72 69 6d 65 29 69 6e 20 74 68  rary prime)in th
0b40: 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 20  e hash function 
0b50: 70 72 6f 76 69 64 65 64 20 0a 2a 2a 20 6e 6f 20  provided .** no 
0b60: 66 65 77 65 72 20 63 6f 6c 6c 69 73 69 6f 6e 73  fewer collisions
0b70: 20 74 68 61 6e 20 74 68 65 20 6e 6f 2d 6f 70 20   than the no-op 
0b80: 2a 31 2e 20 2a 2f 0a 23 64 65 66 69 6e 65 20 42  *1. */.#define B
0b90: 49 54 56 45 43 5f 48 41 53 48 28 58 29 20 20 20  ITVEC_HASH(X)   
0ba0: 28 28 28 58 29 2a 31 29 25 42 49 54 56 45 43 5f  (((X)*1)%BITVEC_
0bb0: 4e 49 4e 54 29 0a 0a 23 64 65 66 69 6e 65 20 42  NINT)..#define B
0bc0: 49 54 56 45 43 5f 4e 50 54 52 20 20 20 20 20 20  ITVEC_NPTR      
0bd0: 28 42 49 54 56 45 43 5f 55 53 49 5a 45 2f 73 69  (BITVEC_USIZE/si
0be0: 7a 65 6f 66 28 42 69 74 76 65 63 20 2a 29 29 0a  zeof(Bitvec *)).
0bf0: 0a 0a 2f 2a 0a 2a 2a 20 41 20 62 69 74 6d 61 70  ../*.** A bitmap
0c00: 20 69 73 20 61 6e 20 69 6e 73 74 61 6e 63 65 20   is an instance 
0c10: 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67  of the following
0c20: 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2a 0a 2a   structure..**.*
0c30: 2a 20 54 68 69 73 20 62 69 74 6d 61 70 20 72 65  * This bitmap re
0c40: 63 6f 72 64 73 20 74 68 65 20 65 78 69 73 74 65  cords the existe
0c50: 6e 63 65 20 6f 66 20 7a 65 72 6f 20 6f 72 20 6d  nce of zero or m
0c60: 6f 72 65 20 62 69 74 73 0a 2a 2a 20 77 69 74 68  ore bits.** with
0c70: 20 76 61 6c 75 65 73 20 62 65 74 77 65 65 6e 20   values between 
0c80: 31 20 61 6e 64 20 69 53 69 7a 65 2c 20 69 6e 63  1 and iSize, inc
0c90: 6c 75 73 69 76 65 2e 0a 2a 2a 0a 2a 2a 20 54 68  lusive..**.** Th
0ca0: 65 72 65 20 61 72 65 20 74 68 72 65 65 20 70 6f  ere are three po
0cb0: 73 73 69 62 6c 65 20 72 65 70 72 65 73 65 6e 74  ssible represent
0cc0: 61 74 69 6f 6e 73 20 6f 66 20 74 68 65 20 62 69  ations of the bi
0cd0: 74 6d 61 70 2e 0a 2a 2a 20 49 66 20 69 53 69 7a  tmap..** If iSiz
0ce0: 65 3c 3d 42 49 54 56 45 43 5f 4e 42 49 54 2c 20  e<=BITVEC_NBIT, 
0cf0: 74 68 65 6e 20 42 69 74 76 65 63 2e 75 2e 61 42  then Bitvec.u.aB
0d00: 69 74 6d 61 70 5b 5d 20 69 73 20 61 20 73 74 72  itmap[] is a str
0d10: 61 69 67 68 74 0a 2a 2a 20 62 69 74 6d 61 70 2e  aight.** bitmap.
0d20: 20 20 54 68 65 20 6c 65 61 73 74 20 73 69 67 6e    The least sign
0d30: 69 66 69 63 61 6e 74 20 62 69 74 20 69 73 20 62  ificant bit is b
0d40: 69 74 20 31 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 69  it 1..**.** If i
0d50: 53 69 7a 65 3e 42 49 54 56 45 43 5f 4e 42 49 54  Size>BITVEC_NBIT
0d60: 20 61 6e 64 20 69 44 69 76 69 73 6f 72 3d 3d 30   and iDivisor==0
0d70: 20 74 68 65 6e 20 42 69 74 76 65 63 2e 75 2e 61   then Bitvec.u.a
0d80: 48 61 73 68 5b 5d 20 69 73 0a 2a 2a 20 61 20 68  Hash[] is.** a h
0d90: 61 73 68 20 74 61 62 6c 65 20 74 68 61 74 20 77  ash table that w
0da0: 69 6c 6c 20 68 6f 6c 64 20 75 70 20 74 6f 20 42  ill hold up to B
0db0: 49 54 56 45 43 5f 4d 58 48 41 53 48 20 64 69 73  ITVEC_MXHASH dis
0dc0: 74 69 6e 63 74 20 76 61 6c 75 65 73 2e 0a 2a 2a  tinct values..**
0dd0: 0a 2a 2a 20 4f 74 68 65 72 77 69 73 65 2c 20 74  .** Otherwise, t
0de0: 68 65 20 76 61 6c 75 65 20 69 20 69 73 20 72 65  he value i is re
0df0: 64 69 72 65 63 74 65 64 20 69 6e 74 6f 20 6f 6e  directed into on
0e00: 65 20 6f 66 20 42 49 54 56 45 43 5f 4e 50 54 52  e of BITVEC_NPTR
0e10: 0a 2a 2a 20 73 75 62 2d 62 69 74 6d 61 70 73 20  .** sub-bitmaps 
0e20: 70 6f 69 6e 74 65 64 20 74 6f 20 62 79 20 42 69  pointed to by Bi
0e30: 74 76 65 63 2e 75 2e 61 70 53 75 62 5b 5d 2e 20  tvec.u.apSub[]. 
0e40: 20 45 61 63 68 20 73 75 62 62 69 74 6d 61 70 0a   Each subbitmap.
0e50: 2a 2a 20 68 61 6e 64 6c 65 73 20 75 70 20 74 6f  ** handles up to
0e60: 20 69 44 69 76 69 73 6f 72 20 73 65 70 61 72 61   iDivisor separa
0e70: 74 65 20 76 61 6c 75 65 73 20 6f 66 20 69 2e 20  te values of i. 
0e80: 20 61 70 53 75 62 5b 30 5d 20 68 6f 6c 64 73 0a   apSub[0] holds.
0e90: 2a 2a 20 76 61 6c 75 65 73 20 62 65 74 77 65 65  ** values betwee
0ea0: 6e 20 31 20 61 6e 64 20 69 44 69 76 69 73 6f 72  n 1 and iDivisor
0eb0: 2e 20 20 61 70 53 75 62 5b 31 5d 20 68 6f 6c 64  .  apSub[1] hold
0ec0: 73 20 76 61 6c 75 65 73 20 62 65 74 77 65 65 6e  s values between
0ed0: 0a 2a 2a 20 69 44 69 76 69 73 6f 72 2b 31 20 61  .** iDivisor+1 a
0ee0: 6e 64 20 32 2a 69 44 69 76 69 73 6f 72 2e 20 20  nd 2*iDivisor.  
0ef0: 61 70 53 75 62 5b 4e 5d 20 68 6f 6c 64 73 20 76  apSub[N] holds v
0f00: 61 6c 75 65 73 20 62 65 74 77 65 65 6e 0a 2a 2a  alues between.**
0f10: 20 4e 2a 69 44 69 76 69 73 6f 72 2b 31 20 61 6e   N*iDivisor+1 an
0f20: 64 20 28 4e 2b 31 29 2a 69 44 69 76 69 73 6f 72  d (N+1)*iDivisor
0f30: 2e 20 20 45 61 63 68 20 73 75 62 62 69 74 6d 61  .  Each subbitma
0f40: 70 20 69 73 20 6e 6f 72 6d 61 6c 69 7a 65 64 0a  p is normalized.
0f50: 2a 2a 20 74 6f 20 68 6f 6c 64 20 64 65 61 6c 20  ** to hold deal 
0f60: 77 69 74 68 20 76 61 6c 75 65 73 20 62 65 74 77  with values betw
0f70: 65 65 6e 20 31 20 61 6e 64 20 69 44 69 76 69 73  een 1 and iDivis
0f80: 6f 72 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 42 69  or..*/.struct Bi
0f90: 74 76 65 63 20 7b 0a 20 20 75 33 32 20 69 53 69  tvec {.  u32 iSi
0fa0: 7a 65 3b 20 20 20 20 20 20 2f 2a 20 4d 61 78 69  ze;      /* Maxi
0fb0: 6d 75 6d 20 62 69 74 20 69 6e 64 65 78 2e 20 20  mum bit index.  
0fc0: 4d 61 78 20 69 53 69 7a 65 20 69 73 20 34 2c 32  Max iSize is 4,2
0fd0: 39 34 2c 39 36 37 2c 32 39 36 2e 20 2a 2f 0a 20  94,967,296. */. 
0fe0: 20 75 33 32 20 6e 53 65 74 3b 20 20 20 20 20 20   u32 nSet;      
0ff0: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 62 69   /* Number of bi
1000: 74 73 20 74 68 61 74 20 61 72 65 20 73 65 74 20  ts that are set 
1010: 2d 20 6f 6e 6c 79 20 76 61 6c 69 64 20 66 6f 72  - only valid for
1020: 20 61 48 61 73 68 0a 20 20 20 20 20 20 20 20 20   aHash.         
1030: 20 20 20 20 20 20 20 20 20 2a 2a 20 65 6c 65 6d           ** elem
1040: 65 6e 74 2e 20 20 4d 61 78 20 69 73 20 42 49 54  ent.  Max is BIT
1050: 56 45 43 5f 4e 49 4e 54 2e 20 20 46 6f 72 20 42  VEC_NINT.  For B
1060: 49 54 56 45 43 5f 53 5a 20 6f 66 20 35 31 32 2c  ITVEC_SZ of 512,
1070: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1080: 20 20 20 2a 2a 20 74 68 69 73 20 77 6f 75 6c 64     ** this would
1090: 20 62 65 20 31 32 35 2e 20 2a 2f 0a 20 20 75 33   be 125. */.  u3
10a0: 32 20 69 44 69 76 69 73 6f 72 3b 20 20 20 2f 2a  2 iDivisor;   /*
10b0: 20 4e 75 6d 62 65 72 20 6f 66 20 62 69 74 73 20   Number of bits 
10c0: 68 61 6e 64 6c 65 64 20 62 79 20 65 61 63 68 20  handled by each 
10d0: 61 70 53 75 62 5b 5d 20 65 6e 74 72 79 2e 20 2a  apSub[] entry. *
10e0: 2f 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  /.              
10f0: 20 20 20 20 2f 2a 20 53 68 6f 75 6c 64 20 3e 3d      /* Should >=
1100: 30 20 66 6f 72 20 61 70 53 75 62 20 65 6c 65 6d  0 for apSub elem
1110: 65 6e 74 2e 20 2a 2f 0a 20 20 20 20 20 20 20 20  ent. */.        
1120: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4d 61 78            /* Max
1130: 20 69 44 69 76 69 73 6f 72 20 69 73 20 6d 61 78   iDivisor is max
1140: 28 75 33 32 29 20 2f 20 42 49 54 56 45 43 5f 4e  (u32) / BITVEC_N
1150: 50 54 52 20 2b 20 31 2e 20 20 2a 2f 0a 20 20 20  PTR + 1.  */.   
1160: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
1170: 2a 20 46 6f 72 20 61 20 42 49 54 56 45 43 5f 53  * For a BITVEC_S
1180: 5a 20 6f 66 20 35 31 32 2c 20 74 68 69 73 20 77  Z of 512, this w
1190: 6f 75 6c 64 20 62 65 20 33 34 2c 33 35 39 2c 37  ould be 34,359,7
11a0: 33 39 2e 20 2a 2f 0a 20 20 75 6e 69 6f 6e 20 7b  39. */.  union {
11b0: 0a 20 20 20 20 42 49 54 56 45 43 5f 54 45 4c 45  .    BITVEC_TELE
11c0: 4d 20 61 42 69 74 6d 61 70 5b 42 49 54 56 45 43  M aBitmap[BITVEC
11d0: 5f 4e 45 4c 45 4d 5d 3b 20 20 20 20 2f 2a 20 42  _NELEM];    /* B
11e0: 69 74 6d 61 70 20 72 65 70 72 65 73 65 6e 74 61  itmap representa
11f0: 74 69 6f 6e 20 2a 2f 0a 20 20 20 20 75 33 32 20  tion */.    u32 
1200: 61 48 61 73 68 5b 42 49 54 56 45 43 5f 4e 49 4e  aHash[BITVEC_NIN
1210: 54 5d 3b 20 20 20 20 20 20 2f 2a 20 48 61 73 68  T];      /* Hash
1220: 20 74 61 62 6c 65 20 72 65 70 72 65 73 65 6e 74   table represent
1230: 61 74 69 6f 6e 20 2a 2f 0a 20 20 20 20 42 69 74  ation */.    Bit
1240: 76 65 63 20 2a 61 70 53 75 62 5b 42 49 54 56 45  vec *apSub[BITVE
1250: 43 5f 4e 50 54 52 5d 3b 20 20 2f 2a 20 52 65 63  C_NPTR];  /* Rec
1260: 75 72 73 69 76 65 20 72 65 70 72 65 73 65 6e 74  ursive represent
1270: 61 74 69 6f 6e 20 2a 2f 0a 20 20 7d 20 75 3b 0a  ation */.  } u;.
1280: 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 43 72 65 61 74 65  };../*.** Create
1290: 20 61 20 6e 65 77 20 62 69 74 6d 61 70 20 6f 62   a new bitmap ob
12a0: 6a 65 63 74 20 61 62 6c 65 20 74 6f 20 68 61 6e  ject able to han
12b0: 64 6c 65 20 62 69 74 73 20 62 65 74 77 65 65 6e  dle bits between
12c0: 20 30 20 61 6e 64 20 69 53 69 7a 65 2c 0a 2a 2a   0 and iSize,.**
12d0: 20 69 6e 63 6c 75 73 69 76 65 2e 20 20 52 65 74   inclusive.  Ret
12e0: 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f  urn a pointer to
12f0: 20 74 68 65 20 6e 65 77 20 6f 62 6a 65 63 74 2e   the new object.
1300: 20 20 52 65 74 75 72 6e 20 4e 55 4c 4c 20 69 66    Return NULL if
1310: 20 0a 2a 2a 20 6d 61 6c 6c 6f 63 20 66 61 69 6c   .** malloc fail
1320: 73 2e 0a 2a 2f 0a 42 69 74 76 65 63 20 2a 73 71  s..*/.Bitvec *sq
1330: 6c 69 74 65 33 42 69 74 76 65 63 43 72 65 61 74  lite3BitvecCreat
1340: 65 28 75 33 32 20 69 53 69 7a 65 29 7b 0a 20 20  e(u32 iSize){.  
1350: 42 69 74 76 65 63 20 2a 70 3b 0a 20 20 61 73 73  Bitvec *p;.  ass
1360: 65 72 74 28 20 73 69 7a 65 6f 66 28 2a 70 29 3d  ert( sizeof(*p)=
1370: 3d 42 49 54 56 45 43 5f 53 5a 20 29 3b 0a 20 20  =BITVEC_SZ );.  
1380: 70 20 3d 20 73 71 6c 69 74 65 33 4d 61 6c 6c 6f  p = sqlite3Mallo
1390: 63 5a 65 72 6f 28 20 73 69 7a 65 6f 66 28 2a 70  cZero( sizeof(*p
13a0: 29 20 29 3b 0a 20 20 69 66 28 20 70 20 29 7b 0a  ) );.  if( p ){.
13b0: 20 20 20 20 70 2d 3e 69 53 69 7a 65 20 3d 20 69      p->iSize = i
13c0: 53 69 7a 65 3b 0a 20 20 7d 0a 20 20 72 65 74 75  Size;.  }.  retu
13d0: 72 6e 20 70 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43  rn p;.}../*.** C
13e0: 68 65 63 6b 20 74 6f 20 73 65 65 20 69 66 20 74  heck to see if t
13f0: 68 65 20 69 2d 74 68 20 62 69 74 20 69 73 20 73  he i-th bit is s
1400: 65 74 2e 20 20 52 65 74 75 72 6e 20 74 72 75 65  et.  Return true
1410: 20 6f 72 20 66 61 6c 73 65 2e 0a 2a 2a 20 49 66   or false..** If
1420: 20 70 20 69 73 20 4e 55 4c 4c 20 28 69 66 20 74   p is NULL (if t
1430: 68 65 20 62 69 74 6d 61 70 20 68 61 73 20 6e 6f  he bitmap has no
1440: 74 20 62 65 65 6e 20 63 72 65 61 74 65 64 29 20  t been created) 
1450: 6f 72 20 69 66 0a 2a 2a 20 69 20 69 73 20 6f 75  or if.** i is ou
1460: 74 20 6f 66 20 72 61 6e 67 65 2c 20 74 68 65 6e  t of range, then
1470: 20 72 65 74 75 72 6e 20 66 61 6c 73 65 2e 0a 2a   return false..*
1480: 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 42 69 74  /.int sqlite3Bit
1490: 76 65 63 54 65 73 74 4e 6f 74 4e 75 6c 6c 28 42  vecTestNotNull(B
14a0: 69 74 76 65 63 20 2a 70 2c 20 75 33 32 20 69 29  itvec *p, u32 i)
14b0: 7b 0a 20 20 61 73 73 65 72 74 28 20 70 21 3d 30  {.  assert( p!=0
14c0: 20 29 3b 0a 20 20 69 2d 2d 3b 0a 20 20 69 66 28   );.  i--;.  if(
14d0: 20 69 3e 3d 70 2d 3e 69 53 69 7a 65 20 29 20 72   i>=p->iSize ) r
14e0: 65 74 75 72 6e 20 30 3b 0a 20 20 77 68 69 6c 65  eturn 0;.  while
14f0: 28 20 70 2d 3e 69 44 69 76 69 73 6f 72 20 29 7b  ( p->iDivisor ){
1500: 0a 20 20 20 20 75 33 32 20 62 69 6e 20 3d 20 69  .    u32 bin = i
1510: 2f 70 2d 3e 69 44 69 76 69 73 6f 72 3b 0a 20 20  /p->iDivisor;.  
1520: 20 20 69 20 3d 20 69 25 70 2d 3e 69 44 69 76 69    i = i%p->iDivi
1530: 73 6f 72 3b 0a 20 20 20 20 70 20 3d 20 70 2d 3e  sor;.    p = p->
1540: 75 2e 61 70 53 75 62 5b 62 69 6e 5d 3b 0a 20 20  u.apSub[bin];.  
1550: 20 20 69 66 20 28 21 70 29 20 7b 0a 20 20 20 20    if (!p) {.    
1560: 20 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 20 20    return 0;.    
1570: 7d 0a 20 20 7d 0a 20 20 69 66 28 20 70 2d 3e 69  }.  }.  if( p->i
1580: 53 69 7a 65 3c 3d 42 49 54 56 45 43 5f 4e 42 49  Size<=BITVEC_NBI
1590: 54 20 29 7b 0a 20 20 20 20 72 65 74 75 72 6e 20  T ){.    return 
15a0: 28 70 2d 3e 75 2e 61 42 69 74 6d 61 70 5b 69 2f  (p->u.aBitmap[i/
15b0: 42 49 54 56 45 43 5f 53 5a 45 4c 45 4d 5d 20 26  BITVEC_SZELEM] &
15c0: 20 28 31 3c 3c 28 69 26 28 42 49 54 56 45 43 5f   (1<<(i&(BITVEC_
15d0: 53 5a 45 4c 45 4d 2d 31 29 29 29 29 21 3d 30 3b  SZELEM-1))))!=0;
15e0: 0a 20 20 7d 20 65 6c 73 65 7b 0a 20 20 20 20 75  .  } else{.    u
15f0: 33 32 20 68 20 3d 20 42 49 54 56 45 43 5f 48 41  32 h = BITVEC_HA
1600: 53 48 28 69 2b 2b 29 3b 0a 20 20 20 20 77 68 69  SH(i++);.    whi
1610: 6c 65 28 20 70 2d 3e 75 2e 61 48 61 73 68 5b 68  le( p->u.aHash[h
1620: 5d 20 29 7b 0a 20 20 20 20 20 20 69 66 28 20 70  ] ){.      if( p
1630: 2d 3e 75 2e 61 48 61 73 68 5b 68 5d 3d 3d 69 20  ->u.aHash[h]==i 
1640: 29 20 72 65 74 75 72 6e 20 31 3b 0a 20 20 20 20  ) return 1;.    
1650: 20 20 68 20 3d 20 28 68 2b 31 29 20 25 20 42 49    h = (h+1) % BI
1660: 54 56 45 43 5f 4e 49 4e 54 3b 0a 20 20 20 20 7d  TVEC_NINT;.    }
1670: 0a 20 20 20 20 72 65 74 75 72 6e 20 30 3b 0a 20  .    return 0;. 
1680: 20 7d 0a 7d 0a 69 6e 74 20 73 71 6c 69 74 65 33   }.}.int sqlite3
1690: 42 69 74 76 65 63 54 65 73 74 28 42 69 74 76 65  BitvecTest(Bitve
16a0: 63 20 2a 70 2c 20 75 33 32 20 69 29 7b 0a 20 20  c *p, u32 i){.  
16b0: 72 65 74 75 72 6e 20 70 21 3d 30 20 26 26 20 73  return p!=0 && s
16c0: 71 6c 69 74 65 33 42 69 74 76 65 63 54 65 73 74  qlite3BitvecTest
16d0: 4e 6f 74 4e 75 6c 6c 28 70 2c 69 29 3b 0a 7d 0a  NotNull(p,i);.}.
16e0: 0a 2f 2a 0a 2a 2a 20 53 65 74 20 74 68 65 20 69  ./*.** Set the i
16f0: 2d 74 68 20 62 69 74 2e 20 20 52 65 74 75 72 6e  -th bit.  Return
1700: 20 30 20 6f 6e 20 73 75 63 63 65 73 73 20 61 6e   0 on success an
1710: 64 20 61 6e 20 65 72 72 6f 72 20 63 6f 64 65 20  d an error code 
1720: 69 66 0a 2a 2a 20 61 6e 79 74 68 69 6e 67 20 67  if.** anything g
1730: 6f 65 73 20 77 72 6f 6e 67 2e 0a 2a 2a 0a 2a 2a  oes wrong..**.**
1740: 20 54 68 69 73 20 72 6f 75 74 69 6e 65 20 6d 69   This routine mi
1750: 67 68 74 20 63 61 75 73 65 20 73 75 62 2d 62 69  ght cause sub-bi
1760: 74 6d 61 70 73 20 74 6f 20 62 65 20 61 6c 6c 6f  tmaps to be allo
1770: 63 61 74 65 64 2e 20 20 46 61 69 6c 69 6e 67 0a  cated.  Failing.
1780: 2a 2a 20 74 6f 20 67 65 74 20 74 68 65 20 6d 65  ** to get the me
1790: 6d 6f 72 79 20 6e 65 65 64 65 64 20 74 6f 20 68  mory needed to h
17a0: 6f 6c 64 20 74 68 65 20 73 75 62 2d 62 69 74 6d  old the sub-bitm
17b0: 61 70 20 69 73 20 74 68 65 20 6f 6e 6c 79 0a 2a  ap is the only.*
17c0: 2a 20 74 68 61 74 20 63 61 6e 20 67 6f 20 77 72  * that can go wr
17d0: 6f 6e 67 20 77 69 74 68 20 61 6e 20 69 6e 73 65  ong with an inse
17e0: 72 74 2c 20 61 73 73 75 6d 69 6e 67 20 70 20 61  rt, assuming p a
17f0: 6e 64 20 69 20 61 72 65 20 76 61 6c 69 64 2e 0a  nd i are valid..
1800: 2a 2a 0a 2a 2a 20 54 68 65 20 63 61 6c 6c 69 6e  **.** The callin
1810: 67 20 66 75 6e 63 74 69 6f 6e 20 6d 75 73 74 20  g function must 
1820: 65 6e 73 75 72 65 20 74 68 61 74 20 70 20 69 73  ensure that p is
1830: 20 61 20 76 61 6c 69 64 20 42 69 74 76 65 63 20   a valid Bitvec 
1840: 6f 62 6a 65 63 74 0a 2a 2a 20 61 6e 64 20 74 68  object.** and th
1850: 61 74 20 74 68 65 20 76 61 6c 75 65 20 66 6f 72  at the value for
1860: 20 22 69 22 20 69 73 20 77 69 74 68 69 6e 20 72   "i" is within r
1870: 61 6e 67 65 20 6f 66 20 74 68 65 20 42 69 74 76  ange of the Bitv
1880: 65 63 20 6f 62 6a 65 63 74 2e 0a 2a 2a 20 4f 74  ec object..** Ot
1890: 68 65 72 77 69 73 65 20 74 68 65 20 62 65 68 61  herwise the beha
18a0: 76 69 6f 72 20 69 73 20 75 6e 64 65 66 69 6e 65  vior is undefine
18b0: 64 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65  d..*/.int sqlite
18c0: 33 42 69 74 76 65 63 53 65 74 28 42 69 74 76 65  3BitvecSet(Bitve
18d0: 63 20 2a 70 2c 20 75 33 32 20 69 29 7b 0a 20 20  c *p, u32 i){.  
18e0: 75 33 32 20 68 3b 0a 20 20 69 66 28 20 70 3d 3d  u32 h;.  if( p==
18f0: 30 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54  0 ) return SQLIT
1900: 45 5f 4f 4b 3b 0a 20 20 61 73 73 65 72 74 28 20  E_OK;.  assert( 
1910: 69 3e 30 20 29 3b 0a 20 20 2f 2a 20 61 73 73 65  i>0 );.  /* asse
1920: 72 74 28 20 69 3c 3d 70 2d 3e 69 53 69 7a 65 20  rt( i<=p->iSize 
1930: 29 3b 20 2a 2f 0a 20 20 69 66 28 20 69 3e 70 2d  ); */.  if( i>p-
1940: 3e 69 53 69 7a 65 20 29 7b 0a 20 20 20 20 73 71  >iSize ){.    sq
1950: 6c 69 74 65 33 5f 6c 6f 67 28 53 51 4c 49 54 45  lite3_log(SQLITE
1960: 5f 45 52 52 4f 52 2c 20 0a 20 20 20 20 20 20 20  _ERROR, .       
1970: 20 22 42 69 74 76 65 63 3a 20 73 65 74 74 69 6e   "Bitvec: settin
1980: 67 20 62 69 74 20 25 64 20 6f 66 20 62 69 74 76  g bit %d of bitv
1990: 65 63 20 73 69 7a 65 20 25 64 5c 6e 22 2c 20 28  ec size %d\n", (
19a0: 69 6e 74 29 69 2c 20 28 69 6e 74 29 70 2d 3e 69  int)i, (int)p->i
19b0: 53 69 7a 65 0a 20 20 20 20 29 3b 0a 20 20 7d 0a  Size.    );.  }.
19c0: 20 20 69 2d 2d 3b 0a 20 20 77 68 69 6c 65 28 28    i--;.  while((
19d0: 70 2d 3e 69 53 69 7a 65 20 3e 20 42 49 54 56 45  p->iSize > BITVE
19e0: 43 5f 4e 42 49 54 29 20 26 26 20 70 2d 3e 69 44  C_NBIT) && p->iD
19f0: 69 76 69 73 6f 72 29 20 7b 0a 20 20 20 20 75 33  ivisor) {.    u3
1a00: 32 20 62 69 6e 20 3d 20 69 2f 70 2d 3e 69 44 69  2 bin = i/p->iDi
1a10: 76 69 73 6f 72 3b 0a 20 20 20 20 69 20 3d 20 69  visor;.    i = i
1a20: 25 70 2d 3e 69 44 69 76 69 73 6f 72 3b 0a 20 20  %p->iDivisor;.  
1a30: 20 20 69 66 28 20 70 2d 3e 75 2e 61 70 53 75 62    if( p->u.apSub
1a40: 5b 62 69 6e 5d 3d 3d 30 20 29 7b 0a 20 20 20 20  [bin]==0 ){.    
1a50: 20 20 70 2d 3e 75 2e 61 70 53 75 62 5b 62 69 6e    p->u.apSub[bin
1a60: 5d 20 3d 20 73 71 6c 69 74 65 33 42 69 74 76 65  ] = sqlite3Bitve
1a70: 63 43 72 65 61 74 65 28 20 70 2d 3e 69 44 69 76  cCreate( p->iDiv
1a80: 69 73 6f 72 20 29 3b 0a 20 20 20 20 20 20 69 66  isor );.      if
1a90: 28 20 70 2d 3e 75 2e 61 70 53 75 62 5b 62 69 6e  ( p->u.apSub[bin
1aa0: 5d 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 53 51  ]==0 ) return SQ
1ab0: 4c 49 54 45 5f 4e 4f 4d 45 4d 5f 42 4b 50 54 3b  LITE_NOMEM_BKPT;
1ac0: 0a 20 20 20 20 7d 0a 20 20 20 20 70 20 3d 20 70  .    }.    p = p
1ad0: 2d 3e 75 2e 61 70 53 75 62 5b 62 69 6e 5d 3b 0a  ->u.apSub[bin];.
1ae0: 20 20 7d 0a 20 20 69 66 28 20 70 2d 3e 69 53 69    }.  if( p->iSi
1af0: 7a 65 3c 3d 42 49 54 56 45 43 5f 4e 42 49 54 20  ze<=BITVEC_NBIT 
1b00: 29 7b 0a 20 20 20 20 70 2d 3e 75 2e 61 42 69 74  ){.    p->u.aBit
1b10: 6d 61 70 5b 69 2f 42 49 54 56 45 43 5f 53 5a 45  map[i/BITVEC_SZE
1b20: 4c 45 4d 5d 20 7c 3d 20 31 20 3c 3c 20 28 69 26  LEM] |= 1 << (i&
1b30: 28 42 49 54 56 45 43 5f 53 5a 45 4c 45 4d 2d 31  (BITVEC_SZELEM-1
1b40: 29 29 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 53  ));.    return S
1b50: 51 4c 49 54 45 5f 4f 4b 3b 0a 20 20 7d 0a 20 20  QLITE_OK;.  }.  
1b60: 68 20 3d 20 42 49 54 56 45 43 5f 48 41 53 48 28  h = BITVEC_HASH(
1b70: 69 2b 2b 29 3b 0a 20 20 2f 2a 20 69 66 20 74 68  i++);.  /* if th
1b80: 65 72 65 20 77 61 73 6e 27 74 20 61 20 68 61 73  ere wasn't a has
1b90: 68 20 63 6f 6c 6c 69 73 69 6f 6e 2c 20 61 6e 64  h collision, and
1ba0: 20 74 68 69 73 20 64 6f 65 73 6e 27 74 20 2a 2f   this doesn't */
1bb0: 0a 20 20 2f 2a 20 63 6f 6d 70 6c 65 74 65 6c 79  .  /* completely
1bc0: 20 66 69 6c 6c 20 74 68 65 20 68 61 73 68 2c 20   fill the hash, 
1bd0: 74 68 65 6e 20 6a 75 73 74 20 61 64 64 20 69 74  then just add it
1be0: 20 77 69 74 68 6f 75 74 20 2a 2f 0a 20 20 2f 2a   without */.  /*
1bf0: 20 77 6f 72 72 69 6e 67 20 61 62 6f 75 74 20 73   worring about s
1c00: 75 62 2d 64 69 76 69 64 69 6e 67 20 61 6e 64 20  ub-dividing and 
1c10: 72 65 2d 68 61 73 68 69 6e 67 2e 20 2a 2f 0a 20  re-hashing. */. 
1c20: 20 69 66 28 20 21 70 2d 3e 75 2e 61 48 61 73 68   if( !p->u.aHash
1c30: 5b 68 5d 20 29 7b 0a 20 20 20 20 69 66 20 28 70  [h] ){.    if (p
1c40: 2d 3e 6e 53 65 74 3c 28 42 49 54 56 45 43 5f 4e  ->nSet<(BITVEC_N
1c50: 49 4e 54 2d 31 29 29 20 7b 0a 20 20 20 20 20 20  INT-1)) {.      
1c60: 67 6f 74 6f 20 62 69 74 76 65 63 5f 73 65 74 5f  goto bitvec_set_
1c70: 65 6e 64 3b 0a 20 20 20 20 7d 20 65 6c 73 65 20  end;.    } else 
1c80: 7b 0a 20 20 20 20 20 20 67 6f 74 6f 20 62 69 74  {.      goto bit
1c90: 76 65 63 5f 73 65 74 5f 72 65 68 61 73 68 3b 0a  vec_set_rehash;.
1ca0: 20 20 20 20 7d 0a 20 20 7d 0a 20 20 2f 2a 20 74      }.  }.  /* t
1cb0: 68 65 72 65 20 77 61 73 20 61 20 63 6f 6c 6c 69  here was a colli
1cc0: 73 69 6f 6e 2c 20 63 68 65 63 6b 20 74 6f 20 73  sion, check to s
1cd0: 65 65 20 69 66 20 69 74 27 73 20 61 6c 72 65 61  ee if it's alrea
1ce0: 64 79 20 2a 2f 0a 20 20 2f 2a 20 69 6e 20 68 61  dy */.  /* in ha
1cf0: 73 68 2c 20 69 66 20 6e 6f 74 2c 20 74 72 79 20  sh, if not, try 
1d00: 74 6f 20 66 69 6e 64 20 61 20 73 70 6f 74 20 66  to find a spot f
1d10: 6f 72 20 69 74 20 2a 2f 0a 20 20 64 6f 20 7b 0a  or it */.  do {.
1d20: 20 20 20 20 69 66 28 20 70 2d 3e 75 2e 61 48 61      if( p->u.aHa
1d30: 73 68 5b 68 5d 3d 3d 69 20 29 20 72 65 74 75 72  sh[h]==i ) retur
1d40: 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b 0a 20 20 20  n SQLITE_OK;.   
1d50: 20 68 2b 2b 3b 0a 20 20 20 20 69 66 28 20 68 3e   h++;.    if( h>
1d60: 3d 42 49 54 56 45 43 5f 4e 49 4e 54 20 29 20 68  =BITVEC_NINT ) h
1d70: 20 3d 20 30 3b 0a 20 20 7d 20 77 68 69 6c 65 28   = 0;.  } while(
1d80: 20 70 2d 3e 75 2e 61 48 61 73 68 5b 68 5d 20 29   p->u.aHash[h] )
1d90: 3b 0a 20 20 2f 2a 20 77 65 20 64 69 64 6e 27 74  ;.  /* we didn't
1da0: 20 66 69 6e 64 20 69 74 20 69 6e 20 74 68 65 20   find it in the 
1db0: 68 61 73 68 2e 20 20 68 20 70 6f 69 6e 74 73 20  hash.  h points 
1dc0: 74 6f 20 74 68 65 20 66 69 72 73 74 20 2a 2f 0a  to the first */.
1dd0: 20 20 2f 2a 20 61 76 61 69 6c 61 62 6c 65 20 66    /* available f
1de0: 72 65 65 20 73 70 6f 74 2e 20 63 68 65 63 6b 20  ree spot. check 
1df0: 74 6f 20 73 65 65 20 69 66 20 74 68 69 73 20 69  to see if this i
1e00: 73 20 67 6f 69 6e 67 20 74 6f 20 2a 2f 0a 20 20  s going to */.  
1e10: 2f 2a 20 6d 61 6b 65 20 6f 75 72 20 68 61 73 68  /* make our hash
1e20: 20 74 6f 6f 20 22 66 75 6c 6c 22 2e 20 20 2a 2f   too "full".  */
1e30: 0a 62 69 74 76 65 63 5f 73 65 74 5f 72 65 68 61  .bitvec_set_reha
1e40: 73 68 3a 0a 20 20 69 66 28 20 70 2d 3e 6e 53 65  sh:.  if( p->nSe
1e50: 74 3e 3d 42 49 54 56 45 43 5f 4d 58 48 41 53 48  t>=BITVEC_MXHASH
1e60: 20 29 7b 0a 20 20 20 20 75 6e 73 69 67 6e 65 64   ){.    unsigned
1e70: 20 69 6e 74 20 6a 3b 0a 20 20 20 20 69 6e 74 20   int j;.    int 
1e80: 72 63 3b 0a 20 20 20 20 75 33 32 20 2a 61 69 56  rc;.    u32 *aiV
1e90: 61 6c 75 65 73 20 3d 20 73 71 6c 69 74 65 33 53  alues = sqlite3S
1ea0: 74 61 63 6b 41 6c 6c 6f 63 52 61 77 28 30 2c 20  tackAllocRaw(0, 
1eb0: 73 69 7a 65 6f 66 28 70 2d 3e 75 2e 61 48 61 73  sizeof(p->u.aHas
1ec0: 68 29 29 3b 0a 20 20 20 20 69 66 28 20 61 69 56  h));.    if( aiV
1ed0: 61 6c 75 65 73 3d 3d 30 20 29 7b 0a 20 20 20 20  alues==0 ){.    
1ee0: 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f    return SQLITE_
1ef0: 4e 4f 4d 45 4d 5f 42 4b 50 54 3b 0a 20 20 20 20  NOMEM_BKPT;.    
1f00: 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 6d 65 6d  }else{.      mem
1f10: 63 70 79 28 61 69 56 61 6c 75 65 73 2c 20 70 2d  cpy(aiValues, p-
1f20: 3e 75 2e 61 48 61 73 68 2c 20 73 69 7a 65 6f 66  >u.aHash, sizeof
1f30: 28 70 2d 3e 75 2e 61 48 61 73 68 29 29 3b 0a 20  (p->u.aHash));. 
1f40: 20 20 20 20 20 6d 65 6d 73 65 74 28 70 2d 3e 75       memset(p->u
1f50: 2e 61 70 53 75 62 2c 20 30 2c 20 73 69 7a 65 6f  .apSub, 0, sizeo
1f60: 66 28 70 2d 3e 75 2e 61 70 53 75 62 29 29 3b 0a  f(p->u.apSub));.
1f70: 20 20 20 20 20 20 70 2d 3e 69 44 69 76 69 73 6f        p->iDiviso
1f80: 72 20 3d 20 28 70 2d 3e 69 53 69 7a 65 20 2b 20  r = (p->iSize + 
1f90: 42 49 54 56 45 43 5f 4e 50 54 52 20 2d 20 31 29  BITVEC_NPTR - 1)
1fa0: 2f 42 49 54 56 45 43 5f 4e 50 54 52 3b 0a 20 20  /BITVEC_NPTR;.  
1fb0: 20 20 20 20 72 63 20 3d 20 73 71 6c 69 74 65 33      rc = sqlite3
1fc0: 42 69 74 76 65 63 53 65 74 28 70 2c 20 69 29 3b  BitvecSet(p, i);
1fd0: 0a 20 20 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20  .      for(j=0; 
1fe0: 6a 3c 42 49 54 56 45 43 5f 4e 49 4e 54 3b 20 6a  j<BITVEC_NINT; j
1ff0: 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 69 66 28  ++){.        if(
2000: 20 61 69 56 61 6c 75 65 73 5b 6a 5d 20 29 20 72   aiValues[j] ) r
2010: 63 20 7c 3d 20 73 71 6c 69 74 65 33 42 69 74 76  c |= sqlite3Bitv
2020: 65 63 53 65 74 28 70 2c 20 61 69 56 61 6c 75 65  ecSet(p, aiValue
2030: 73 5b 6a 5d 29 3b 0a 20 20 20 20 20 20 7d 0a 20  s[j]);.      }. 
2040: 20 20 20 20 20 73 71 6c 69 74 65 33 53 74 61 63       sqlite3Stac
2050: 6b 46 72 65 65 28 30 2c 20 61 69 56 61 6c 75 65  kFree(0, aiValue
2060: 73 29 3b 0a 20 20 20 20 20 20 72 65 74 75 72 6e  s);.      return
2070: 20 72 63 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 62   rc;.    }.  }.b
2080: 69 74 76 65 63 5f 73 65 74 5f 65 6e 64 3a 0a 20  itvec_set_end:. 
2090: 20 70 2d 3e 6e 53 65 74 2b 2b 3b 0a 20 20 70 2d   p->nSet++;.  p-
20a0: 3e 75 2e 61 48 61 73 68 5b 68 5d 20 3d 20 69 3b  >u.aHash[h] = i;
20b0: 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45  .  return SQLITE
20c0: 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43 6c  _OK;.}../*.** Cl
20d0: 65 61 72 20 74 68 65 20 69 2d 74 68 20 62 69 74  ear the i-th bit
20e0: 2e 0a 2a 2a 0a 2a 2a 20 70 42 75 66 20 6d 75 73  ..**.** pBuf mus
20f0: 74 20 62 65 20 61 20 70 6f 69 6e 74 65 72 20 74  t be a pointer t
2100: 6f 20 61 74 20 6c 65 61 73 74 20 42 49 54 56 45  o at least BITVE
2110: 43 5f 53 5a 20 62 79 74 65 73 20 6f 66 20 74 65  C_SZ bytes of te
2120: 6d 70 6f 72 61 72 79 20 73 74 6f 72 61 67 65 0a  mporary storage.
2130: 2a 2a 20 74 68 61 74 20 42 69 74 76 65 63 43 6c  ** that BitvecCl
2140: 65 61 72 20 63 61 6e 20 75 73 65 20 74 6f 20 72  ear can use to r
2150: 65 62 75 69 6c 74 20 69 74 73 20 68 61 73 68 20  ebuilt its hash 
2160: 74 61 62 6c 65 2e 0a 2a 2f 0a 76 6f 69 64 20 73  table..*/.void s
2170: 71 6c 69 74 65 33 42 69 74 76 65 63 43 6c 65 61  qlite3BitvecClea
2180: 72 28 42 69 74 76 65 63 20 2a 70 2c 20 75 33 32  r(Bitvec *p, u32
2190: 20 69 2c 20 76 6f 69 64 20 2a 70 42 75 66 29 7b   i, void *pBuf){
21a0: 0a 20 20 69 66 28 20 70 3d 3d 30 20 29 20 72 65  .  if( p==0 ) re
21b0: 74 75 72 6e 3b 0a 20 20 61 73 73 65 72 74 28 20  turn;.  assert( 
21c0: 69 3e 30 20 29 3b 0a 20 20 69 2d 2d 3b 0a 20 20  i>0 );.  i--;.  
21d0: 77 68 69 6c 65 28 20 70 2d 3e 69 44 69 76 69 73  while( p->iDivis
21e0: 6f 72 20 29 7b 0a 20 20 20 20 75 33 32 20 62 69  or ){.    u32 bi
21f0: 6e 20 3d 20 69 2f 70 2d 3e 69 44 69 76 69 73 6f  n = i/p->iDiviso
2200: 72 3b 0a 20 20 20 20 69 20 3d 20 69 25 70 2d 3e  r;.    i = i%p->
2210: 69 44 69 76 69 73 6f 72 3b 0a 20 20 20 20 70 20  iDivisor;.    p 
2220: 3d 20 70 2d 3e 75 2e 61 70 53 75 62 5b 62 69 6e  = p->u.apSub[bin
2230: 5d 3b 0a 20 20 20 20 69 66 20 28 21 70 29 20 7b  ];.    if (!p) {
2240: 0a 20 20 20 20 20 20 72 65 74 75 72 6e 3b 0a 20  .      return;. 
2250: 20 20 20 7d 0a 20 20 7d 0a 20 20 69 66 28 20 70     }.  }.  if( p
2260: 2d 3e 69 53 69 7a 65 3c 3d 42 49 54 56 45 43 5f  ->iSize<=BITVEC_
2270: 4e 42 49 54 20 29 7b 0a 20 20 20 20 70 2d 3e 75  NBIT ){.    p->u
2280: 2e 61 42 69 74 6d 61 70 5b 69 2f 42 49 54 56 45  .aBitmap[i/BITVE
2290: 43 5f 53 5a 45 4c 45 4d 5d 20 26 3d 20 7e 28 31  C_SZELEM] &= ~(1
22a0: 20 3c 3c 20 28 69 26 28 42 49 54 56 45 43 5f 53   << (i&(BITVEC_S
22b0: 5a 45 4c 45 4d 2d 31 29 29 29 3b 0a 20 20 7d 65  ZELEM-1)));.  }e
22c0: 6c 73 65 7b 0a 20 20 20 20 75 6e 73 69 67 6e 65  lse{.    unsigne
22d0: 64 20 69 6e 74 20 6a 3b 0a 20 20 20 20 75 33 32  d int j;.    u32
22e0: 20 2a 61 69 56 61 6c 75 65 73 20 3d 20 70 42 75   *aiValues = pBu
22f0: 66 3b 0a 20 20 20 20 6d 65 6d 63 70 79 28 61 69  f;.    memcpy(ai
2300: 56 61 6c 75 65 73 2c 20 70 2d 3e 75 2e 61 48 61  Values, p->u.aHa
2310: 73 68 2c 20 73 69 7a 65 6f 66 28 70 2d 3e 75 2e  sh, sizeof(p->u.
2320: 61 48 61 73 68 29 29 3b 0a 20 20 20 20 6d 65 6d  aHash));.    mem
2330: 73 65 74 28 70 2d 3e 75 2e 61 48 61 73 68 2c 20  set(p->u.aHash, 
2340: 30 2c 20 73 69 7a 65 6f 66 28 70 2d 3e 75 2e 61  0, sizeof(p->u.a
2350: 48 61 73 68 29 29 3b 0a 20 20 20 20 70 2d 3e 6e  Hash));.    p->n
2360: 53 65 74 20 3d 20 30 3b 0a 20 20 20 20 66 6f 72  Set = 0;.    for
2370: 28 6a 3d 30 3b 20 6a 3c 42 49 54 56 45 43 5f 4e  (j=0; j<BITVEC_N
2380: 49 4e 54 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 20  INT; j++){.     
2390: 20 69 66 28 20 61 69 56 61 6c 75 65 73 5b 6a 5d   if( aiValues[j]
23a0: 20 26 26 20 61 69 56 61 6c 75 65 73 5b 6a 5d 21   && aiValues[j]!
23b0: 3d 28 69 2b 31 29 20 29 7b 0a 20 20 20 20 20 20  =(i+1) ){.      
23c0: 20 20 75 33 32 20 68 20 3d 20 42 49 54 56 45 43    u32 h = BITVEC
23d0: 5f 48 41 53 48 28 61 69 56 61 6c 75 65 73 5b 6a  _HASH(aiValues[j
23e0: 5d 2d 31 29 3b 0a 20 20 20 20 20 20 20 20 70 2d  ]-1);.        p-
23f0: 3e 6e 53 65 74 2b 2b 3b 0a 20 20 20 20 20 20 20  >nSet++;.       
2400: 20 77 68 69 6c 65 28 20 70 2d 3e 75 2e 61 48 61   while( p->u.aHa
2410: 73 68 5b 68 5d 20 29 7b 0a 20 20 20 20 20 20 20  sh[h] ){.       
2420: 20 20 20 68 2b 2b 3b 0a 20 20 20 20 20 20 20 20     h++;.        
2430: 20 20 69 66 28 20 68 3e 3d 42 49 54 56 45 43 5f    if( h>=BITVEC_
2440: 4e 49 4e 54 20 29 20 68 20 3d 20 30 3b 0a 20 20  NINT ) h = 0;.  
2450: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 20 20        }.        
2460: 70 2d 3e 75 2e 61 48 61 73 68 5b 68 5d 20 3d 20  p->u.aHash[h] = 
2470: 61 69 56 61 6c 75 65 73 5b 6a 5d 3b 0a 20 20 20  aiValues[j];.   
2480: 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a 7d     }.    }.  }.}
2490: 0a 0a 2f 2a 0a 2a 2a 20 44 65 73 74 72 6f 79 20  ../*.** Destroy 
24a0: 61 20 62 69 74 6d 61 70 20 6f 62 6a 65 63 74 2e  a bitmap object.
24b0: 20 20 52 65 63 6c 61 69 6d 20 61 6c 6c 20 6d 65    Reclaim all me
24c0: 6d 6f 72 79 20 75 73 65 64 2e 0a 2a 2f 0a 76 6f  mory used..*/.vo
24d0: 69 64 20 73 71 6c 69 74 65 33 42 69 74 76 65 63  id sqlite3Bitvec
24e0: 44 65 73 74 72 6f 79 28 42 69 74 76 65 63 20 2a  Destroy(Bitvec *
24f0: 70 29 7b 0a 20 20 69 66 28 20 70 3d 3d 30 20 29  p){.  if( p==0 )
2500: 20 72 65 74 75 72 6e 3b 0a 20 20 69 66 28 20 70   return;.  if( p
2510: 2d 3e 69 44 69 76 69 73 6f 72 20 29 7b 0a 20 20  ->iDivisor ){.  
2520: 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 69    unsigned int i
2530: 3b 0a 20 20 20 20 66 6f 72 28 69 3d 30 3b 20 69  ;.    for(i=0; i
2540: 3c 42 49 54 56 45 43 5f 4e 50 54 52 3b 20 69 2b  <BITVEC_NPTR; i+
2550: 2b 29 7b 0a 20 20 20 20 20 20 73 71 6c 69 74 65  +){.      sqlite
2560: 33 42 69 74 76 65 63 44 65 73 74 72 6f 79 28 70  3BitvecDestroy(p
2570: 2d 3e 75 2e 61 70 53 75 62 5b 69 5d 29 3b 0a 20  ->u.apSub[i]);. 
2580: 20 20 20 7d 0a 20 20 7d 0a 20 20 73 71 6c 69 74     }.  }.  sqlit
2590: 65 33 5f 66 72 65 65 28 70 29 3b 0a 7d 0a 0a 2f  e3_free(p);.}../
25a0: 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 74 68 65 20  *.** Return the 
25b0: 76 61 6c 75 65 20 6f 66 20 74 68 65 20 69 53 69  value of the iSi
25c0: 7a 65 20 70 61 72 61 6d 65 74 65 72 20 73 70 65  ze parameter spe
25d0: 63 69 66 69 65 64 20 77 68 65 6e 20 42 69 74 76  cified when Bitv
25e0: 65 63 20 2a 70 0a 2a 2a 20 77 61 73 20 63 72 65  ec *p.** was cre
25f0: 61 74 65 64 2e 0a 2a 2f 0a 75 33 32 20 73 71 6c  ated..*/.u32 sql
2600: 69 74 65 33 42 69 74 76 65 63 53 69 7a 65 28 42  ite3BitvecSize(B
2610: 69 74 76 65 63 20 2a 70 29 7b 0a 20 20 72 65 74  itvec *p){.  ret
2620: 75 72 6e 20 70 2d 3e 69 53 69 7a 65 3b 0a 7d 0a  urn p->iSize;.}.
2630: 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f  .#ifndef SQLITE_
2640: 55 4e 54 45 53 54 41 42 4c 45 0a 2f 2a 0a 2a 2a  UNTESTABLE./*.**
2650: 20 4c 65 74 20 56 5b 5d 20 62 65 20 61 6e 20 61   Let V[] be an a
2660: 72 72 61 79 20 6f 66 20 75 6e 73 69 67 6e 65 64  rray of unsigned
2670: 20 63 68 61 72 61 63 74 65 72 73 20 73 75 66 66   characters suff
2680: 69 63 69 65 6e 74 20 74 6f 20 68 6f 6c 64 0a 2a  icient to hold.*
2690: 2a 20 75 70 20 74 6f 20 4e 20 62 69 74 73 2e 20  * up to N bits. 
26a0: 20 4c 65 74 20 49 20 62 65 20 61 6e 20 69 6e 74   Let I be an int
26b0: 65 67 65 72 20 62 65 74 77 65 65 6e 20 30 20 61  eger between 0 a
26c0: 6e 64 20 4e 2e 20 20 30 3c 3d 49 3c 4e 2e 0a 2a  nd N.  0<=I<N..*
26d0: 2a 20 54 68 65 6e 20 74 68 65 20 66 6f 6c 6c 6f  * Then the follo
26e0: 77 69 6e 67 20 6d 61 63 72 6f 73 20 63 61 6e 20  wing macros can 
26f0: 62 65 20 75 73 65 64 20 74 6f 20 73 65 74 2c 20  be used to set, 
2700: 63 6c 65 61 72 2c 20 6f 72 20 74 65 73 74 0a 2a  clear, or test.*
2710: 2a 20 69 6e 64 69 76 69 64 75 61 6c 20 62 69 74  * individual bit
2720: 73 20 77 69 74 68 69 6e 20 56 2e 0a 2a 2f 0a 23  s within V..*/.#
2730: 64 65 66 69 6e 65 20 53 45 54 42 49 54 28 56 2c  define SETBIT(V,
2740: 49 29 20 20 20 20 20 20 56 5b 49 3e 3e 33 5d 20  I)      V[I>>3] 
2750: 7c 3d 20 28 31 3c 3c 28 49 26 37 29 29 0a 23 64  |= (1<<(I&7)).#d
2760: 65 66 69 6e 65 20 43 4c 45 41 52 42 49 54 28 56  efine CLEARBIT(V
2770: 2c 49 29 20 20 20 20 56 5b 49 3e 3e 33 5d 20 26  ,I)    V[I>>3] &
2780: 3d 20 7e 28 31 3c 3c 28 49 26 37 29 29 0a 23 64  = ~(1<<(I&7)).#d
2790: 65 66 69 6e 65 20 54 45 53 54 42 49 54 28 56 2c  efine TESTBIT(V,
27a0: 49 29 20 20 20 20 20 28 56 5b 49 3e 3e 33 5d 26  I)     (V[I>>3]&
27b0: 28 31 3c 3c 28 49 26 37 29 29 29 21 3d 30 0a 0a  (1<<(I&7)))!=0..
27c0: 2f 2a 0a 2a 2a 20 54 68 69 73 20 72 6f 75 74 69  /*.** This routi
27d0: 6e 65 20 72 75 6e 73 20 61 6e 20 65 78 74 65 6e  ne runs an exten
27e0: 73 69 76 65 20 74 65 73 74 20 6f 66 20 74 68 65  sive test of the
27f0: 20 42 69 74 76 65 63 20 63 6f 64 65 2e 0a 2a 2a   Bitvec code..**
2800: 0a 2a 2a 20 54 68 65 20 69 6e 70 75 74 20 69 73  .** The input is
2810: 20 61 6e 20 61 72 72 61 79 20 6f 66 20 69 6e 74   an array of int
2820: 65 67 65 72 73 20 74 68 61 74 20 61 63 74 73 20  egers that acts 
2830: 61 73 20 61 20 70 72 6f 67 72 61 6d 0a 2a 2a 20  as a program.** 
2840: 74 6f 20 74 65 73 74 20 74 68 65 20 42 69 74 76  to test the Bitv
2850: 65 63 2e 20 20 54 68 65 20 69 6e 74 65 67 65 72  ec.  The integer
2860: 73 20 61 72 65 20 6f 70 63 6f 64 65 73 20 66 6f  s are opcodes fo
2870: 6c 6c 6f 77 65 64 0a 2a 2a 20 62 79 20 30 2c 20  llowed.** by 0, 
2880: 31 2c 20 6f 72 20 33 20 6f 70 65 72 61 6e 64 73  1, or 3 operands
2890: 2c 20 64 65 70 65 6e 64 69 6e 67 20 6f 6e 20 74  , depending on t
28a0: 68 65 20 6f 70 63 6f 64 65 2e 20 20 41 6e 6f 74  he opcode.  Anot
28b0: 68 65 72 0a 2a 2a 20 6f 70 63 6f 64 65 20 66 6f  her.** opcode fo
28c0: 6c 6c 6f 77 73 20 69 6d 6d 65 64 69 61 74 65 6c  llows immediatel
28d0: 79 20 61 66 74 65 72 20 74 68 65 20 6c 61 73 74  y after the last
28e0: 20 6f 70 65 72 61 6e 64 2e 0a 2a 2a 0a 2a 2a 20   operand..**.** 
28f0: 54 68 65 72 65 20 61 72 65 20 36 20 6f 70 63 6f  There are 6 opco
2900: 64 65 73 20 6e 75 6d 62 65 72 65 64 20 66 72 6f  des numbered fro
2910: 6d 20 30 20 74 68 72 6f 75 67 68 20 35 2e 20 20  m 0 through 5.  
2920: 30 20 69 73 20 74 68 65 0a 2a 2a 20 22 68 61 6c  0 is the.** "hal
2930: 74 22 20 6f 70 63 6f 64 65 20 61 6e 64 20 63 61  t" opcode and ca
2940: 75 73 65 73 20 74 68 65 20 74 65 73 74 20 74 6f  uses the test to
2950: 20 65 6e 64 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 30   end..**.**    0
2960: 20 20 20 20 20 20 20 20 20 20 48 61 6c 74 20 61            Halt a
2970: 6e 64 20 72 65 74 75 72 6e 20 74 68 65 20 6e 75  nd return the nu
2980: 6d 62 65 72 20 6f 66 20 65 72 72 6f 72 73 0a 2a  mber of errors.*
2990: 2a 20 20 20 20 31 20 4e 20 53 20 58 20 20 20 20  *    1 N S X    
29a0: 53 65 74 20 4e 20 62 69 74 73 20 62 65 67 69 6e  Set N bits begin
29b0: 6e 69 6e 67 20 77 69 74 68 20 53 20 61 6e 64 20  ning with S and 
29c0: 69 6e 63 72 65 6d 65 6e 74 69 6e 67 20 62 79 20  incrementing by 
29d0: 58 0a 2a 2a 20 20 20 20 32 20 4e 20 53 20 58 20  X.**    2 N S X 
29e0: 20 20 20 43 6c 65 61 72 20 4e 20 62 69 74 73 20     Clear N bits 
29f0: 62 65 67 69 6e 6e 69 6e 67 20 77 69 74 68 20 53  beginning with S
2a00: 20 61 6e 64 20 69 6e 63 72 65 6d 65 6e 74 69 6e   and incrementin
2a10: 67 20 62 79 20 58 0a 2a 2a 20 20 20 20 33 20 4e  g by X.**    3 N
2a20: 20 20 20 20 20 20 20 20 53 65 74 20 4e 20 72 61          Set N ra
2a30: 6e 64 6f 6d 6c 79 20 63 68 6f 73 65 6e 20 62 69  ndomly chosen bi
2a40: 74 73 0a 2a 2a 20 20 20 20 34 20 4e 20 20 20 20  ts.**    4 N    
2a50: 20 20 20 20 43 6c 65 61 72 20 4e 20 72 61 6e 64      Clear N rand
2a60: 6f 6d 6c 79 20 63 68 6f 73 65 6e 20 62 69 74 73  omly chosen bits
2a70: 0a 2a 2a 20 20 20 20 35 20 4e 20 53 20 58 20 20  .**    5 N S X  
2a80: 20 20 53 65 74 20 4e 20 62 69 74 73 20 66 72 6f    Set N bits fro
2a90: 6d 20 53 20 69 6e 63 72 65 6d 65 6e 74 20 58 20  m S increment X 
2aa0: 69 6e 20 61 72 72 61 79 20 6f 6e 6c 79 2c 20 6e  in array only, n
2ab0: 6f 74 20 69 6e 20 62 69 74 76 65 63 0a 2a 2a 0a  ot in bitvec.**.
2ac0: 2a 2a 20 54 68 65 20 6f 70 63 6f 64 65 73 20 31  ** The opcodes 1
2ad0: 20 74 68 72 6f 75 67 68 20 34 20 70 65 72 66 6f   through 4 perfo
2ae0: 72 6d 20 73 65 74 20 61 6e 64 20 63 6c 65 61 72  rm set and clear
2af0: 20 6f 70 65 72 61 74 69 6f 6e 73 20 61 72 65 20   operations are 
2b00: 70 65 72 66 6f 72 6d 65 64 0a 2a 2a 20 6f 6e 20  performed.** on 
2b10: 62 6f 74 68 20 61 20 42 69 74 76 65 63 20 6f 62  both a Bitvec ob
2b20: 6a 65 63 74 20 61 6e 64 20 6f 6e 20 61 20 6c 69  ject and on a li
2b30: 6e 65 61 72 20 61 72 72 61 79 20 6f 66 20 62 69  near array of bi
2b40: 74 73 20 6f 62 74 61 69 6e 65 64 20 66 72 6f 6d  ts obtained from
2b50: 20 6d 61 6c 6c 6f 63 2e 0a 2a 2a 20 4f 70 63 6f   malloc..** Opco
2b60: 64 65 20 35 20 77 6f 72 6b 73 20 6f 6e 20 74 68  de 5 works on th
2b70: 65 20 6c 69 6e 65 61 72 20 61 72 72 61 79 20 6f  e linear array o
2b80: 6e 6c 79 2c 20 6e 6f 74 20 6f 6e 20 74 68 65 20  nly, not on the 
2b90: 42 69 74 76 65 63 2e 0a 2a 2a 20 4f 70 63 6f 64  Bitvec..** Opcod
2ba0: 65 20 35 20 69 73 20 75 73 65 64 20 74 6f 20 64  e 5 is used to d
2bb0: 65 6c 69 62 65 72 61 74 65 6c 79 20 69 6e 64 75  eliberately indu
2bc0: 63 65 20 61 20 66 61 75 6c 74 20 69 6e 20 6f 72  ce a fault in or
2bd0: 64 65 72 20 74 6f 0a 2a 2a 20 63 6f 6e 66 69 72  der to.** confir
2be0: 6d 20 74 68 61 74 20 65 72 72 6f 72 20 64 65 74  m that error det
2bf0: 65 63 74 69 6f 6e 20 77 6f 72 6b 73 2e 0a 2a 2a  ection works..**
2c00: 0a 2a 2a 20 41 74 20 74 68 65 20 63 6f 6e 63 6c  .** At the concl
2c10: 75 73 69 6f 6e 20 6f 66 20 74 68 65 20 74 65 73  usion of the tes
2c20: 74 20 74 68 65 20 6c 69 6e 65 61 72 20 61 72 72  t the linear arr
2c30: 61 79 20 69 73 20 63 6f 6d 70 61 72 65 64 0a 2a  ay is compared.*
2c40: 2a 20 61 67 61 69 6e 73 74 20 74 68 65 20 42 69  * against the Bi
2c50: 74 76 65 63 20 6f 62 6a 65 63 74 2e 20 20 49 66  tvec object.  If
2c60: 20 74 68 65 72 65 20 61 72 65 20 61 6e 79 20 64   there are any d
2c70: 69 66 66 65 72 65 6e 63 65 73 2c 0a 2a 2a 20 61  ifferences,.** a
2c80: 6e 20 65 72 72 6f 72 20 69 73 20 72 65 74 75 72  n error is retur
2c90: 6e 65 64 2e 20 20 49 66 20 74 68 65 79 20 61 72  ned.  If they ar
2ca0: 65 20 74 68 65 20 73 61 6d 65 2c 20 7a 65 72 6f  e the same, zero
2cb0: 20 69 73 20 72 65 74 75 72 6e 65 64 2e 0a 2a 2a   is returned..**
2cc0: 0a 2a 2a 20 49 66 20 61 20 6d 65 6d 6f 72 79 20  .** If a memory 
2cd0: 61 6c 6c 6f 63 61 74 69 6f 6e 20 65 72 72 6f 72  allocation error
2ce0: 20 6f 63 63 75 72 73 2c 20 72 65 74 75 72 6e 20   occurs, return 
2cf0: 2d 31 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74  -1..*/.int sqlit
2d00: 65 33 42 69 74 76 65 63 42 75 69 6c 74 69 6e 54  e3BitvecBuiltinT
2d10: 65 73 74 28 69 6e 74 20 73 7a 2c 20 69 6e 74 20  est(int sz, int 
2d20: 2a 61 4f 70 29 7b 0a 20 20 42 69 74 76 65 63 20  *aOp){.  Bitvec 
2d30: 2a 70 42 69 74 76 65 63 20 3d 20 30 3b 0a 20 20  *pBitvec = 0;.  
2d40: 75 6e 73 69 67 6e 65 64 20 63 68 61 72 20 2a 70  unsigned char *p
2d50: 56 20 3d 20 30 3b 0a 20 20 69 6e 74 20 72 63 20  V = 0;.  int rc 
2d60: 3d 20 2d 31 3b 0a 20 20 69 6e 74 20 69 2c 20 6e  = -1;.  int i, n
2d70: 78 2c 20 70 63 2c 20 6f 70 3b 0a 20 20 76 6f 69  x, pc, op;.  voi
2d80: 64 20 2a 70 54 6d 70 53 70 61 63 65 3b 0a 0a 20  d *pTmpSpace;.. 
2d90: 20 2f 2a 20 41 6c 6c 6f 63 61 74 65 20 74 68 65   /* Allocate the
2da0: 20 42 69 74 76 65 63 20 74 6f 20 62 65 20 74 65   Bitvec to be te
2db0: 73 74 65 64 20 61 6e 64 20 61 20 6c 69 6e 65 61  sted and a linea
2dc0: 72 20 61 72 72 61 79 20 6f 66 0a 20 20 2a 2a 20  r array of.  ** 
2dd0: 62 69 74 73 20 74 6f 20 61 63 74 20 61 73 20 74  bits to act as t
2de0: 68 65 20 72 65 66 65 72 65 6e 63 65 20 2a 2f 0a  he reference */.
2df0: 20 20 70 42 69 74 76 65 63 20 3d 20 73 71 6c 69    pBitvec = sqli
2e00: 74 65 33 42 69 74 76 65 63 43 72 65 61 74 65 28  te3BitvecCreate(
2e10: 20 73 7a 20 29 3b 0a 20 20 70 56 20 3d 20 73 71   sz );.  pV = sq
2e20: 6c 69 74 65 33 4d 61 6c 6c 6f 63 5a 65 72 6f 28  lite3MallocZero(
2e30: 20 28 73 7a 2b 37 29 2f 38 20 2b 20 31 20 29 3b   (sz+7)/8 + 1 );
2e40: 0a 20 20 70 54 6d 70 53 70 61 63 65 20 3d 20 73  .  pTmpSpace = s
2e50: 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 36 34 28  qlite3_malloc64(
2e60: 42 49 54 56 45 43 5f 53 5a 29 3b 0a 20 20 69 66  BITVEC_SZ);.  if
2e70: 28 20 70 42 69 74 76 65 63 3d 3d 30 20 7c 7c 20  ( pBitvec==0 || 
2e80: 70 56 3d 3d 30 20 7c 7c 20 70 54 6d 70 53 70 61  pV==0 || pTmpSpa
2e90: 63 65 3d 3d 30 20 20 29 20 67 6f 74 6f 20 62 69  ce==0  ) goto bi
2ea0: 74 76 65 63 5f 65 6e 64 3b 0a 0a 20 20 2f 2a 20  tvec_end;..  /* 
2eb0: 4e 55 4c 4c 20 70 42 69 74 76 65 63 20 74 65 73  NULL pBitvec tes
2ec0: 74 73 20 2a 2f 0a 20 20 73 71 6c 69 74 65 33 42  ts */.  sqlite3B
2ed0: 69 74 76 65 63 53 65 74 28 30 2c 20 31 29 3b 0a  itvecSet(0, 1);.
2ee0: 20 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 43    sqlite3BitvecC
2ef0: 6c 65 61 72 28 30 2c 20 31 2c 20 70 54 6d 70 53  lear(0, 1, pTmpS
2f00: 70 61 63 65 29 3b 0a 0a 20 20 2f 2a 20 52 75 6e  pace);..  /* Run
2f10: 20 74 68 65 20 70 72 6f 67 72 61 6d 20 2a 2f 0a   the program */.
2f20: 20 20 70 63 20 3d 20 30 3b 0a 20 20 77 68 69 6c    pc = 0;.  whil
2f30: 65 28 20 28 6f 70 20 3d 20 61 4f 70 5b 70 63 5d  e( (op = aOp[pc]
2f40: 29 21 3d 30 20 29 7b 0a 20 20 20 20 73 77 69 74  )!=0 ){.    swit
2f50: 63 68 28 20 6f 70 20 29 7b 0a 20 20 20 20 20 20  ch( op ){.      
2f60: 63 61 73 65 20 31 3a 0a 20 20 20 20 20 20 63 61  case 1:.      ca
2f70: 73 65 20 32 3a 0a 20 20 20 20 20 20 63 61 73 65  se 2:.      case
2f80: 20 35 3a 20 7b 0a 20 20 20 20 20 20 20 20 6e 78   5: {.        nx
2f90: 20 3d 20 34 3b 0a 20 20 20 20 20 20 20 20 69 20   = 4;.        i 
2fa0: 3d 20 61 4f 70 5b 70 63 2b 32 5d 20 2d 20 31 3b  = aOp[pc+2] - 1;
2fb0: 0a 20 20 20 20 20 20 20 20 61 4f 70 5b 70 63 2b  .        aOp[pc+
2fc0: 32 5d 20 2b 3d 20 61 4f 70 5b 70 63 2b 33 5d 3b  2] += aOp[pc+3];
2fd0: 0a 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a  .        break;.
2fe0: 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 63 61        }.      ca
2ff0: 73 65 20 33 3a 0a 20 20 20 20 20 20 63 61 73 65  se 3:.      case
3000: 20 34 3a 20 0a 20 20 20 20 20 20 64 65 66 61 75   4: .      defau
3010: 6c 74 3a 20 7b 0a 20 20 20 20 20 20 20 20 6e 78  lt: {.        nx
3020: 20 3d 20 32 3b 0a 20 20 20 20 20 20 20 20 73 71   = 2;.        sq
3030: 6c 69 74 65 33 5f 72 61 6e 64 6f 6d 6e 65 73 73  lite3_randomness
3040: 28 73 69 7a 65 6f 66 28 69 29 2c 20 26 69 29 3b  (sizeof(i), &i);
3050: 0a 20 20 20 20 20 20 20 20 62 72 65 61 6b 3b 0a  .        break;.
3060: 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20        }.    }.  
3070: 20 20 69 66 28 20 28 2d 2d 61 4f 70 5b 70 63 2b    if( (--aOp[pc+
3080: 31 5d 29 20 3e 20 30 20 29 20 6e 78 20 3d 20 30  1]) > 0 ) nx = 0
3090: 3b 0a 20 20 20 20 70 63 20 2b 3d 20 6e 78 3b 0a  ;.    pc += nx;.
30a0: 20 20 20 20 69 20 3d 20 28 69 20 26 20 30 78 37      i = (i & 0x7
30b0: 66 66 66 66 66 66 66 29 25 73 7a 3b 0a 20 20 20  fffffff)%sz;.   
30c0: 20 69 66 28 20 28 6f 70 20 26 20 31 29 21 3d 30   if( (op & 1)!=0
30d0: 20 29 7b 0a 20 20 20 20 20 20 53 45 54 42 49 54   ){.      SETBIT
30e0: 28 70 56 2c 20 28 69 2b 31 29 29 3b 0a 20 20 20  (pV, (i+1));.   
30f0: 20 20 20 69 66 28 20 6f 70 21 3d 35 20 29 7b 0a     if( op!=5 ){.
3100: 20 20 20 20 20 20 20 20 69 66 28 20 73 71 6c 69          if( sqli
3110: 74 65 33 42 69 74 76 65 63 53 65 74 28 70 42 69  te3BitvecSet(pBi
3120: 74 76 65 63 2c 20 69 2b 31 29 20 29 20 67 6f 74  tvec, i+1) ) got
3130: 6f 20 62 69 74 76 65 63 5f 65 6e 64 3b 0a 20 20  o bitvec_end;.  
3140: 20 20 20 20 7d 0a 20 20 20 20 7d 65 6c 73 65 7b      }.    }else{
3150: 0a 20 20 20 20 20 20 43 4c 45 41 52 42 49 54 28  .      CLEARBIT(
3160: 70 56 2c 20 28 69 2b 31 29 29 3b 0a 20 20 20 20  pV, (i+1));.    
3170: 20 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 43    sqlite3BitvecC
3180: 6c 65 61 72 28 70 42 69 74 76 65 63 2c 20 69 2b  lear(pBitvec, i+
3190: 31 2c 20 70 54 6d 70 53 70 61 63 65 29 3b 0a 20  1, pTmpSpace);. 
31a0: 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 2f 2a 20 54     }.  }..  /* T
31b0: 65 73 74 20 74 6f 20 6d 61 6b 65 20 73 75 72 65  est to make sure
31c0: 20 74 68 65 20 6c 69 6e 65 61 72 20 61 72 72 61   the linear arra
31d0: 79 20 65 78 61 63 74 6c 79 20 6d 61 74 63 68 65  y exactly matche
31e0: 73 20 74 68 65 0a 20 20 2a 2a 20 42 69 74 76 65  s the.  ** Bitve
31f0: 63 20 6f 62 6a 65 63 74 2e 20 20 53 74 61 72 74  c object.  Start
3200: 20 77 69 74 68 20 74 68 65 20 61 73 73 75 6d 70   with the assump
3210: 74 69 6f 6e 20 74 68 61 74 20 74 68 65 79 20 64  tion that they d
3220: 6f 0a 20 20 2a 2a 20 6d 61 74 63 68 20 28 72 63  o.  ** match (rc
3230: 3d 3d 30 29 2e 20 20 43 68 61 6e 67 65 20 72 63  ==0).  Change rc
3240: 20 74 6f 20 6e 6f 6e 2d 7a 65 72 6f 20 69 66 20   to non-zero if 
3250: 61 20 64 69 73 63 72 65 70 61 6e 63 79 0a 20 20  a discrepancy.  
3260: 2a 2a 20 69 73 20 66 6f 75 6e 64 2e 0a 20 20 2a  ** is found..  *
3270: 2f 0a 20 20 72 63 20 3d 20 73 71 6c 69 74 65 33  /.  rc = sqlite3
3280: 42 69 74 76 65 63 54 65 73 74 28 30 2c 30 29 20  BitvecTest(0,0) 
3290: 2b 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 54  + sqlite3BitvecT
32a0: 65 73 74 28 70 42 69 74 76 65 63 2c 20 73 7a 2b  est(pBitvec, sz+
32b0: 31 29 0a 20 20 20 20 20 20 20 20 20 20 2b 20 73  1).          + s
32c0: 71 6c 69 74 65 33 42 69 74 76 65 63 54 65 73 74  qlite3BitvecTest
32d0: 28 70 42 69 74 76 65 63 2c 20 30 29 0a 20 20 20  (pBitvec, 0).   
32e0: 20 20 20 20 20 20 20 2b 20 28 73 71 6c 69 74 65         + (sqlite
32f0: 33 42 69 74 76 65 63 53 69 7a 65 28 70 42 69 74  3BitvecSize(pBit
3300: 76 65 63 29 20 2d 20 73 7a 29 3b 0a 20 20 66 6f  vec) - sz);.  fo
3310: 72 28 69 3d 31 3b 20 69 3c 3d 73 7a 3b 20 69 2b  r(i=1; i<=sz; i+
3320: 2b 29 7b 0a 20 20 20 20 69 66 28 20 20 28 54 45  +){.    if(  (TE
3330: 53 54 42 49 54 28 70 56 2c 69 29 29 21 3d 73 71  STBIT(pV,i))!=sq
3340: 6c 69 74 65 33 42 69 74 76 65 63 54 65 73 74 28  lite3BitvecTest(
3350: 70 42 69 74 76 65 63 2c 69 29 20 29 7b 0a 20 20  pBitvec,i) ){.  
3360: 20 20 20 20 72 63 20 3d 20 69 3b 0a 20 20 20 20      rc = i;.    
3370: 20 20 62 72 65 61 6b 3b 0a 20 20 20 20 7d 0a 20    break;.    }. 
3380: 20 7d 0a 0a 20 20 2f 2a 20 46 72 65 65 20 61 6c   }..  /* Free al
3390: 6c 6f 63 61 74 65 64 20 73 74 72 75 63 74 75 72  located structur
33a0: 65 20 2a 2f 0a 62 69 74 76 65 63 5f 65 6e 64 3a  e */.bitvec_end:
33b0: 0a 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28  .  sqlite3_free(
33c0: 70 54 6d 70 53 70 61 63 65 29 3b 0a 20 20 73 71  pTmpSpace);.  sq
33d0: 6c 69 74 65 33 5f 66 72 65 65 28 70 56 29 3b 0a  lite3_free(pV);.
33e0: 20 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 44    sqlite3BitvecD
33f0: 65 73 74 72 6f 79 28 70 42 69 74 76 65 63 29 3b  estroy(pBitvec);
3400: 0a 20 20 72 65 74 75 72 6e 20 72 63 3b 0a 7d 0a  .  return rc;.}.
3410: 23 65 6e 64 69 66 20 2f 2a 20 53 51 4c 49 54 45  #endif /* SQLITE
3420: 5f 55 4e 54 45 53 54 41 42 4c 45 20 2a 2f 0a     _UNTESTABLE */.