System.Data.SQLite
Hex Artifact Content
Not logged in

Artifact e75ba549dc3fea861025291f9dc03169f6b97825:


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 61 74 20 70 61 67 65  record what page
0210: 73 20 61 20 64 61 74 61 62 61 73 65 20 66 69 6c  s a database fil
0220: 65 20 68 61 76 65 20 62 65 65 6e 0a 2a 2a 20 6a  e have been.** j
0230: 6f 75 72 6e 61 6c 6c 65 64 20 64 75 72 69 6e 67  ournalled during
0240: 20 61 20 74 72 61 6e 73 61 63 74 69 6f 6e 2e 20   a transaction. 
0250: 20 55 73 75 61 6c 6c 79 20 6f 6e 6c 79 20 61 20   Usually only a 
0260: 66 65 77 20 70 61 67 65 73 20 61 72 65 0a 2a 2a  few pages are.**
0270: 20 6a 6f 75 72 6e 61 6c 6c 65 64 2e 20 20 53 6f   journalled.  So
0280: 20 74 68 65 20 62 69 74 6d 61 70 20 69 73 20 75   the bitmap is u
0290: 73 75 61 6c 6c 79 20 73 70 61 72 73 65 20 61 6e  sually sparse an
02a0: 64 20 68 61 73 20 6c 6f 77 20 63 61 72 64 69 6e  d has low cardin
02b0: 61 6c 69 74 79 2e 0a 2a 2a 20 42 75 74 20 73 6f  ality..** But so
02c0: 6d 65 74 69 6d 65 73 20 28 66 6f 72 20 65 78 61  metimes (for exa
02d0: 6d 70 6c 65 20 77 68 65 6e 20 64 75 72 69 6e 67  mple when during
02e0: 20 61 20 44 52 4f 50 20 6f 66 20 61 20 6c 61 72   a DROP of a lar
02f0: 67 65 20 74 61 62 6c 65 29 20 6d 6f 73 74 0a 2a  ge table) most.*
0300: 2a 20 6f 72 20 61 6c 6c 20 6f 66 20 74 68 65 20  * or all of the 
0310: 70 61 67 65 73 20 67 65 74 20 6a 6f 75 72 6e 61  pages get journa
0320: 6c 6c 65 64 2e 20 20 49 6e 20 74 68 6f 73 65 20  lled.  In those 
0330: 63 61 73 65 73 2c 20 74 68 65 20 62 69 74 6d 61  cases, the bitma
0340: 70 20 62 65 63 6f 6d 65 73 0a 2a 2a 20 64 65 6e  p becomes.** den
0350: 73 65 2e 20 20 54 68 65 20 61 6c 67 6f 72 69 74  se.  The algorit
0360: 68 6d 20 6e 65 65 64 73 20 74 6f 20 68 61 6e 64  hm needs to hand
0370: 6c 65 20 62 6f 74 68 20 63 61 73 65 73 20 77 65  le both cases we
0380: 6c 6c 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 73 69  ll..**.** The si
0390: 7a 65 20 6f 66 20 74 68 65 20 62 69 74 6d 61 70  ze of the bitmap
03a0: 20 69 73 20 66 69 78 65 64 20 77 68 65 6e 20 74   is fixed when t
03b0: 68 65 20 6f 62 6a 65 63 74 20 69 73 20 63 72 65  he object is cre
03c0: 61 74 65 64 2e 0a 2a 2a 0a 2a 2a 20 41 6c 6c 20  ated..**.** All 
03d0: 62 69 74 73 20 61 72 65 20 63 6c 65 61 72 20 77  bits are clear w
03e0: 68 65 6e 20 74 68 65 20 62 69 74 6d 61 70 20 69  hen the bitmap i
03f0: 73 20 63 72 65 61 74 65 64 2e 20 20 49 6e 64 69  s created.  Indi
0400: 76 69 64 75 61 6c 20 62 69 74 73 0a 2a 2a 20 6d  vidual bits.** m
0410: 61 79 20 62 65 20 73 65 74 20 6f 72 20 63 6c 65  ay be set or cle
0420: 61 72 65 64 20 6f 6e 65 20 61 74 20 61 20 74 69  ared one at a ti
0430: 6d 65 2e 0a 2a 2a 0a 2a 2a 20 54 65 73 74 20 6f  me..**.** Test o
0440: 70 65 72 61 74 69 6f 6e 73 20 61 72 65 20 61 62  perations are ab
0450: 6f 75 74 20 31 30 30 20 74 69 6d 65 73 20 6d 6f  out 100 times mo
0460: 72 65 20 63 6f 6d 6d 6f 6e 20 74 68 61 74 20 73  re common that s
0470: 65 74 20 6f 70 65 72 61 74 69 6f 6e 73 2e 0a 2a  et operations..*
0480: 2a 20 43 6c 65 61 72 20 6f 70 65 72 61 74 69 6f  * Clear operatio
0490: 6e 73 20 61 72 65 20 65 78 63 65 65 64 69 6e 67  ns are exceeding
04a0: 6c 79 20 72 61 72 65 2e 20 20 54 68 65 72 65 20  ly rare.  There 
04b0: 61 72 65 20 75 73 75 61 6c 6c 79 20 62 65 74 77  are usually betw
04c0: 65 65 6e 0a 2a 2a 20 35 20 61 6e 64 20 35 30 30  een.** 5 and 500
04d0: 20 73 65 74 20 6f 70 65 72 61 74 69 6f 6e 73 20   set operations 
04e0: 70 65 72 20 42 69 74 76 65 63 20 6f 62 6a 65 63  per Bitvec objec
04f0: 74 2c 20 74 68 6f 75 67 68 20 74 68 65 20 6e 75  t, though the nu
0500: 6d 62 65 72 20 6f 66 20 73 65 74 73 20 63 61 6e  mber of sets can
0510: 0a 2a 2a 20 73 6f 6d 65 74 69 6d 65 73 20 67 72  .** sometimes gr
0520: 6f 77 20 69 6e 74 6f 20 74 65 6e 73 20 6f 66 20  ow into tens of 
0530: 74 68 6f 75 73 61 6e 64 73 20 6f 72 20 6c 61 72  thousands or lar
0540: 67 65 72 2e 20 20 54 68 65 20 73 69 7a 65 20 6f  ger.  The size o
0550: 66 20 74 68 65 0a 2a 2a 20 42 69 74 76 65 63 20  f the.** Bitvec 
0560: 6f 62 6a 65 63 74 20 69 73 20 74 68 65 20 6e 75  object is the nu
0570: 6d 62 65 72 20 6f 66 20 70 61 67 65 73 20 69 6e  mber of pages in
0580: 20 74 68 65 20 64 61 74 61 62 61 73 65 20 66 69   the database fi
0590: 6c 65 20 61 74 20 74 68 65 0a 2a 2a 20 73 74 61  le at the.** sta
05a0: 72 74 20 6f 66 20 61 20 74 72 61 6e 73 61 63 74  rt of a transact
05b0: 69 6f 6e 2c 20 61 6e 64 20 69 73 20 74 68 75 73  ion, and is thus
05c0: 20 75 73 75 61 6c 6c 79 20 6c 65 73 73 20 74 68   usually less th
05d0: 61 6e 20 61 20 66 65 77 20 74 68 6f 75 73 61 6e  an a few thousan
05e0: 64 2c 0a 2a 2a 20 62 75 74 20 63 61 6e 20 62 65  d,.** but can be
05f0: 20 61 73 20 6c 61 72 67 65 20 61 73 20 32 20 62   as large as 2 b
0600: 69 6c 6c 69 6f 6e 20 66 6f 72 20 61 20 72 65 61  illion for a rea
0610: 6c 6c 79 20 62 69 67 20 64 61 74 61 62 61 73 65  lly big database
0620: 2e 0a 2a 2a 0a 2a 2a 20 40 28 23 29 20 24 49 64  ..**.** @(#) $Id
0630: 3a 20 62 69 74 76 65 63 2e 63 2c 76 20 31 2e 31  : bitvec.c,v 1.1
0640: 20 32 30 30 38 2f 30 38 2f 30 36 20 32 31 3a 34   2008/08/06 21:4
0650: 38 3a 30 36 20 72 6d 73 69 6d 70 73 6f 6e 20 45  8:06 rmsimpson E
0660: 78 70 20 24 0a 2a 2f 0a 23 69 6e 63 6c 75 64 65  xp $.*/.#include
0670: 20 22 73 71 6c 69 74 65 49 6e 74 2e 68 22 0a 0a   "sqliteInt.h"..
0680: 23 64 65 66 69 6e 65 20 42 49 54 56 45 43 5f 53  #define BITVEC_S
0690: 5a 20 20 20 20 20 20 20 20 35 31 32 0a 2f 2a 20  Z        512./* 
06a0: 52 6f 75 6e 64 20 74 68 65 20 75 6e 69 6f 6e 20  Round the union 
06b0: 73 69 7a 65 20 64 6f 77 6e 20 74 6f 20 74 68 65  size down to the
06c0: 20 6e 65 61 72 65 73 74 20 70 6f 69 6e 74 65 72   nearest pointer
06d0: 20 62 6f 75 6e 64 61 72 79 2c 20 73 69 6e 63 65   boundary, since
06e0: 20 74 68 61 74 27 73 20 68 6f 77 20 0a 2a 2a 20   that's how .** 
06f0: 69 74 20 77 69 6c 6c 20 62 65 20 61 6c 69 67 6e  it will be align
0700: 65 64 20 77 69 74 68 69 6e 20 74 68 65 20 42 69  ed within the Bi
0710: 74 76 65 63 20 73 74 72 75 63 74 2e 20 2a 2f 0a  tvec struct. */.
0720: 23 64 65 66 69 6e 65 20 42 49 54 56 45 43 5f 55  #define BITVEC_U
0730: 53 49 5a 45 20 20 20 20 20 28 28 28 42 49 54 56  SIZE     (((BITV
0740: 45 43 5f 53 5a 2d 31 32 29 2f 73 69 7a 65 6f 66  EC_SZ-12)/sizeof
0750: 28 42 69 74 76 65 63 2a 29 29 2a 73 69 7a 65 6f  (Bitvec*))*sizeo
0760: 66 28 42 69 74 76 65 63 2a 29 29 0a 23 64 65 66  f(Bitvec*)).#def
0770: 69 6e 65 20 42 49 54 56 45 43 5f 4e 43 48 41 52  ine BITVEC_NCHAR
0780: 20 20 20 20 20 42 49 54 56 45 43 5f 55 53 49 5a       BITVEC_USIZ
0790: 45 0a 23 64 65 66 69 6e 65 20 42 49 54 56 45 43  E.#define BITVEC
07a0: 5f 4e 42 49 54 20 20 20 20 20 20 28 42 49 54 56  _NBIT      (BITV
07b0: 45 43 5f 4e 43 48 41 52 2a 38 29 0a 23 64 65 66  EC_NCHAR*8).#def
07c0: 69 6e 65 20 42 49 54 56 45 43 5f 4e 49 4e 54 20  ine BITVEC_NINT 
07d0: 20 20 20 20 20 28 42 49 54 56 45 43 5f 55 53 49       (BITVEC_USI
07e0: 5a 45 2f 34 29 0a 23 64 65 66 69 6e 65 20 42 49  ZE/4).#define BI
07f0: 54 56 45 43 5f 4d 58 48 41 53 48 20 20 20 20 28  TVEC_MXHASH    (
0800: 42 49 54 56 45 43 5f 4e 49 4e 54 2f 32 29 0a 23  BITVEC_NINT/2).#
0810: 64 65 66 69 6e 65 20 42 49 54 56 45 43 5f 4e 50  define BITVEC_NP
0820: 54 52 20 20 20 20 20 20 28 42 49 54 56 45 43 5f  TR      (BITVEC_
0830: 55 53 49 5a 45 2f 73 69 7a 65 6f 66 28 42 69 74  USIZE/sizeof(Bit
0840: 76 65 63 20 2a 29 29 0a 0a 23 64 65 66 69 6e 65  vec *))..#define
0850: 20 42 49 54 56 45 43 5f 48 41 53 48 28 58 29 20   BITVEC_HASH(X) 
0860: 20 20 28 28 28 58 29 2a 33 37 29 25 42 49 54 56    (((X)*37)%BITV
0870: 45 43 5f 4e 49 4e 54 29 0a 0a 2f 2a 0a 2a 2a 20  EC_NINT)../*.** 
0880: 41 20 62 69 74 6d 61 70 20 69 73 20 61 6e 20 69  A bitmap is an i
0890: 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 65 20 66  nstance of the f
08a0: 6f 6c 6c 6f 77 69 6e 67 20 73 74 72 75 63 74 75  ollowing structu
08b0: 72 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 69 73 20 62  re..**.** This b
08c0: 69 74 6d 61 70 20 72 65 63 6f 72 64 73 20 74 68  itmap records th
08d0: 65 20 65 78 69 73 74 61 6e 63 65 20 6f 66 20 7a  e existance of z
08e0: 65 72 6f 20 6f 72 20 6d 6f 72 65 20 62 69 74 73  ero or more bits
08f0: 0a 2a 2a 20 77 69 74 68 20 76 61 6c 75 65 73 20  .** with values 
0900: 62 65 74 77 65 65 6e 20 31 20 61 6e 64 20 69 53  between 1 and iS
0910: 69 7a 65 2c 20 69 6e 63 6c 75 73 69 76 65 2e 0a  ize, inclusive..
0920: 2a 2a 0a 2a 2a 20 54 68 65 72 65 20 61 72 65 20  **.** There are 
0930: 74 68 72 65 65 20 70 6f 73 73 69 62 6c 65 20 72  three possible r
0940: 65 70 72 65 73 65 6e 74 61 74 69 6f 6e 73 20 6f  epresentations o
0950: 66 20 74 68 65 20 62 69 74 6d 61 70 2e 0a 2a 2a  f the bitmap..**
0960: 20 49 66 20 69 53 69 7a 65 3c 3d 42 49 54 56 45   If iSize<=BITVE
0970: 43 5f 4e 42 49 54 2c 20 74 68 65 6e 20 42 69 74  C_NBIT, then Bit
0980: 76 65 63 2e 75 2e 61 42 69 74 6d 61 70 5b 5d 20  vec.u.aBitmap[] 
0990: 69 73 20 61 20 73 74 72 61 69 67 68 74 0a 2a 2a  is a straight.**
09a0: 20 62 69 74 6d 61 70 2e 20 20 54 68 65 20 6c 65   bitmap.  The le
09b0: 61 73 74 20 73 69 67 6e 69 66 69 63 61 6e 74 20  ast significant 
09c0: 62 69 74 20 69 73 20 62 69 74 20 31 2e 0a 2a 2a  bit is bit 1..**
09d0: 0a 2a 2a 20 49 66 20 69 53 69 7a 65 3e 42 49 54  .** If iSize>BIT
09e0: 56 45 43 5f 4e 42 49 54 20 61 6e 64 20 69 44 69  VEC_NBIT and iDi
09f0: 76 69 73 6f 72 3d 3d 30 20 74 68 65 6e 20 42 69  visor==0 then Bi
0a00: 74 76 65 63 2e 75 2e 61 48 61 73 68 5b 5d 20 69  tvec.u.aHash[] i
0a10: 73 0a 2a 2a 20 61 20 68 61 73 68 20 74 61 62 6c  s.** a hash tabl
0a20: 65 20 74 68 61 74 20 77 69 6c 6c 20 68 6f 6c 64  e that will hold
0a30: 20 75 70 20 74 6f 20 42 49 54 56 45 43 5f 4d 58   up to BITVEC_MX
0a40: 48 41 53 48 20 64 69 73 74 69 6e 63 74 20 76 61  HASH distinct va
0a50: 6c 75 65 73 2e 0a 2a 2a 0a 2a 2a 20 4f 74 68 65  lues..**.** Othe
0a60: 72 77 69 73 65 2c 20 74 68 65 20 76 61 6c 75 65  rwise, the value
0a70: 20 69 20 69 73 20 72 65 64 69 72 65 63 74 65 64   i is redirected
0a80: 20 69 6e 74 6f 20 6f 6e 65 20 6f 66 20 42 49 54   into one of BIT
0a90: 56 45 43 5f 4e 50 54 52 0a 2a 2a 20 73 75 62 2d  VEC_NPTR.** sub-
0aa0: 62 69 74 6d 61 70 73 20 70 6f 69 6e 74 65 64 20  bitmaps pointed 
0ab0: 74 6f 20 62 79 20 42 69 74 76 65 63 2e 75 2e 61  to by Bitvec.u.a
0ac0: 70 53 75 62 5b 5d 2e 20 20 45 61 63 68 20 73 75  pSub[].  Each su
0ad0: 62 62 69 74 6d 61 70 0a 2a 2a 20 68 61 6e 64 6c  bbitmap.** handl
0ae0: 65 73 20 75 70 20 74 6f 20 69 44 69 76 69 73 6f  es up to iDiviso
0af0: 72 20 73 65 70 61 72 61 74 65 20 76 61 6c 75 65  r separate value
0b00: 73 20 6f 66 20 69 2e 20 20 61 70 53 75 62 5b 30  s of i.  apSub[0
0b10: 5d 20 68 6f 6c 64 73 0a 2a 2a 20 76 61 6c 75 65  ] holds.** value
0b20: 73 20 62 65 74 77 65 65 6e 20 31 20 61 6e 64 20  s between 1 and 
0b30: 69 44 69 76 69 73 6f 72 2e 20 20 61 70 53 75 62  iDivisor.  apSub
0b40: 5b 31 5d 20 68 6f 6c 64 73 20 76 61 6c 75 65 73  [1] holds values
0b50: 20 62 65 74 77 65 65 6e 0a 2a 2a 20 69 44 69 76   between.** iDiv
0b60: 69 73 6f 72 2b 31 20 61 6e 64 20 32 2a 69 44 69  isor+1 and 2*iDi
0b70: 76 69 73 6f 72 2e 20 20 61 70 53 75 62 5b 4e 5d  visor.  apSub[N]
0b80: 20 68 6f 6c 64 73 20 76 61 6c 75 65 73 20 62 65   holds values be
0b90: 74 77 65 65 6e 0a 2a 2a 20 4e 2a 69 44 69 76 69  tween.** N*iDivi
0ba0: 73 6f 72 2b 31 20 61 6e 64 20 28 4e 2b 31 29 2a  sor+1 and (N+1)*
0bb0: 69 44 69 76 69 73 6f 72 2e 20 20 45 61 63 68 20  iDivisor.  Each 
0bc0: 73 75 62 62 69 74 6d 61 70 20 69 73 20 6e 6f 72  subbitmap is nor
0bd0: 6d 61 6c 69 7a 65 64 0a 2a 2a 20 74 6f 20 68 6f  malized.** to ho
0be0: 6c 64 20 64 65 61 6c 20 77 69 74 68 20 76 61 6c  ld deal with val
0bf0: 75 65 73 20 62 65 74 77 65 65 6e 20 31 20 61 6e  ues between 1 an
0c00: 64 20 69 44 69 76 69 73 6f 72 2e 0a 2a 2f 0a 73  d iDivisor..*/.s
0c10: 74 72 75 63 74 20 42 69 74 76 65 63 20 7b 0a 20  truct Bitvec {. 
0c20: 20 75 33 32 20 69 53 69 7a 65 3b 20 20 20 20 20   u32 iSize;     
0c30: 20 2f 2a 20 4d 61 78 69 6d 75 6d 20 62 69 74 20   /* Maximum bit 
0c40: 69 6e 64 65 78 20 2a 2f 0a 20 20 75 33 32 20 6e  index */.  u32 n
0c50: 53 65 74 3b 20 20 20 20 20 20 20 2f 2a 20 4e 75  Set;       /* Nu
0c60: 6d 62 65 72 20 6f 66 20 62 69 74 73 20 74 68 61  mber of bits tha
0c70: 74 20 61 72 65 20 73 65 74 20 2a 2f 0a 20 20 75  t are set */.  u
0c80: 33 32 20 69 44 69 76 69 73 6f 72 3b 20 20 20 2f  32 iDivisor;   /
0c90: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 62 69 74 73  * Number of bits
0ca0: 20 68 61 6e 64 6c 65 64 20 62 79 20 65 61 63 68   handled by each
0cb0: 20 61 70 53 75 62 5b 5d 20 65 6e 74 72 79 20 2a   apSub[] entry *
0cc0: 2f 0a 20 20 75 6e 69 6f 6e 20 7b 0a 20 20 20 20  /.  union {.    
0cd0: 75 38 20 61 42 69 74 6d 61 70 5b 42 49 54 56 45  u8 aBitmap[BITVE
0ce0: 43 5f 4e 43 48 41 52 5d 3b 20 20 20 20 2f 2a 20  C_NCHAR];    /* 
0cf0: 42 69 74 6d 61 70 20 72 65 70 72 65 73 65 6e 74  Bitmap represent
0d00: 61 74 69 6f 6e 20 2a 2f 0a 20 20 20 20 75 33 32  ation */.    u32
0d10: 20 61 48 61 73 68 5b 42 49 54 56 45 43 5f 4e 49   aHash[BITVEC_NI
0d20: 4e 54 5d 3b 20 20 20 20 20 20 2f 2a 20 48 61 73  NT];      /* Has
0d30: 68 20 74 61 62 6c 65 20 72 65 70 72 65 73 65 6e  h table represen
0d40: 74 61 74 69 6f 6e 20 2a 2f 0a 20 20 20 20 42 69  tation */.    Bi
0d50: 74 76 65 63 20 2a 61 70 53 75 62 5b 42 49 54 56  tvec *apSub[BITV
0d60: 45 43 5f 4e 50 54 52 5d 3b 20 20 2f 2a 20 52 65  EC_NPTR];  /* Re
0d70: 63 75 72 73 69 76 65 20 72 65 70 72 65 73 65 6e  cursive represen
0d80: 74 61 74 69 6f 6e 20 2a 2f 0a 20 20 7d 20 75 3b  tation */.  } u;
0d90: 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 43 72 65 61 74  .};../*.** Creat
0da0: 65 20 61 20 6e 65 77 20 62 69 74 6d 61 70 20 6f  e a new bitmap o
0db0: 62 6a 65 63 74 20 61 62 6c 65 20 74 6f 20 68 61  bject able to ha
0dc0: 6e 64 6c 65 20 62 69 74 73 20 62 65 74 77 65 65  ndle bits betwee
0dd0: 6e 20 30 20 61 6e 64 20 69 53 69 7a 65 2c 0a 2a  n 0 and iSize,.*
0de0: 2a 20 69 6e 63 6c 75 73 69 76 65 2e 20 20 52 65  * inclusive.  Re
0df0: 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20 74  turn a pointer t
0e00: 6f 20 74 68 65 20 6e 65 77 20 6f 62 6a 65 63 74  o the new object
0e10: 2e 20 20 52 65 74 75 72 6e 20 4e 55 4c 4c 20 69  .  Return NULL i
0e20: 66 20 0a 2a 2a 20 6d 61 6c 6c 6f 63 20 66 61 69  f .** malloc fai
0e30: 6c 73 2e 0a 2a 2f 0a 42 69 74 76 65 63 20 2a 73  ls..*/.Bitvec *s
0e40: 71 6c 69 74 65 33 42 69 74 76 65 63 43 72 65 61  qlite3BitvecCrea
0e50: 74 65 28 75 33 32 20 69 53 69 7a 65 29 7b 0a 20  te(u32 iSize){. 
0e60: 20 42 69 74 76 65 63 20 2a 70 3b 0a 20 20 61 73   Bitvec *p;.  as
0e70: 73 65 72 74 28 20 73 69 7a 65 6f 66 28 2a 70 29  sert( sizeof(*p)
0e80: 3d 3d 42 49 54 56 45 43 5f 53 5a 20 29 3b 0a 20  ==BITVEC_SZ );. 
0e90: 20 70 20 3d 20 73 71 6c 69 74 65 33 4d 61 6c 6c   p = sqlite3Mall
0ea0: 6f 63 5a 65 72 6f 28 20 73 69 7a 65 6f 66 28 2a  ocZero( sizeof(*
0eb0: 70 29 20 29 3b 0a 20 20 69 66 28 20 70 20 29 7b  p) );.  if( p ){
0ec0: 0a 20 20 20 20 70 2d 3e 69 53 69 7a 65 20 3d 20  .    p->iSize = 
0ed0: 69 53 69 7a 65 3b 0a 20 20 7d 0a 20 20 72 65 74  iSize;.  }.  ret
0ee0: 75 72 6e 20 70 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20  urn p;.}../*.** 
0ef0: 43 68 65 63 6b 20 74 6f 20 73 65 65 20 69 66 20  Check to see if 
0f00: 74 68 65 20 69 2d 74 68 20 62 69 74 20 69 73 20  the i-th bit is 
0f10: 73 65 74 2e 20 20 52 65 74 75 72 6e 20 74 72 75  set.  Return tru
0f20: 65 20 6f 72 20 66 61 6c 73 65 2e 0a 2a 2a 20 49  e or false..** I
0f30: 66 20 70 20 69 73 20 4e 55 4c 4c 20 28 69 66 20  f p is NULL (if 
0f40: 74 68 65 20 62 69 74 6d 61 70 20 68 61 73 20 6e  the bitmap has n
0f50: 6f 74 20 62 65 65 6e 20 63 72 65 61 74 65 64 29  ot been created)
0f60: 20 6f 72 20 69 66 0a 2a 2a 20 69 20 69 73 20 6f   or if.** i is o
0f70: 75 74 20 6f 66 20 72 61 6e 67 65 2c 20 74 68 65  ut of range, the
0f80: 6e 20 72 65 74 75 72 6e 20 66 61 6c 73 65 2e 0a  n return false..
0f90: 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 42 69  */.int sqlite3Bi
0fa0: 74 76 65 63 54 65 73 74 28 42 69 74 76 65 63 20  tvecTest(Bitvec 
0fb0: 2a 70 2c 20 75 33 32 20 69 29 7b 0a 20 20 69 66  *p, u32 i){.  if
0fc0: 28 20 70 3d 3d 30 20 29 20 72 65 74 75 72 6e 20  ( p==0 ) return 
0fd0: 30 3b 0a 20 20 69 66 28 20 69 3e 70 2d 3e 69 53  0;.  if( i>p->iS
0fe0: 69 7a 65 20 7c 7c 20 69 3d 3d 30 20 29 20 72 65  ize || i==0 ) re
0ff0: 74 75 72 6e 20 30 3b 0a 20 20 69 66 28 20 70 2d  turn 0;.  if( p-
1000: 3e 69 53 69 7a 65 3c 3d 42 49 54 56 45 43 5f 4e  >iSize<=BITVEC_N
1010: 42 49 54 20 29 7b 0a 20 20 20 20 69 2d 2d 3b 0a  BIT ){.    i--;.
1020: 20 20 20 20 72 65 74 75 72 6e 20 28 70 2d 3e 75      return (p->u
1030: 2e 61 42 69 74 6d 61 70 5b 69 2f 38 5d 20 26 20  .aBitmap[i/8] & 
1040: 28 31 3c 3c 28 69 26 37 29 29 29 21 3d 30 3b 0a  (1<<(i&7)))!=0;.
1050: 20 20 7d 0a 20 20 69 66 28 20 70 2d 3e 69 44 69    }.  if( p->iDi
1060: 76 69 73 6f 72 3e 30 20 29 7b 0a 20 20 20 20 75  visor>0 ){.    u
1070: 33 32 20 62 69 6e 20 3d 20 28 69 2d 31 29 2f 70  32 bin = (i-1)/p
1080: 2d 3e 69 44 69 76 69 73 6f 72 3b 0a 20 20 20 20  ->iDivisor;.    
1090: 69 20 3d 20 28 69 2d 31 29 25 70 2d 3e 69 44 69  i = (i-1)%p->iDi
10a0: 76 69 73 6f 72 20 2b 20 31 3b 0a 20 20 20 20 72  visor + 1;.    r
10b0: 65 74 75 72 6e 20 73 71 6c 69 74 65 33 42 69 74  eturn sqlite3Bit
10c0: 76 65 63 54 65 73 74 28 70 2d 3e 75 2e 61 70 53  vecTest(p->u.apS
10d0: 75 62 5b 62 69 6e 5d 2c 20 69 29 3b 0a 20 20 7d  ub[bin], i);.  }
10e0: 65 6c 73 65 7b 0a 20 20 20 20 75 33 32 20 68 20  else{.    u32 h 
10f0: 3d 20 42 49 54 56 45 43 5f 48 41 53 48 28 69 29  = BITVEC_HASH(i)
1100: 3b 0a 20 20 20 20 77 68 69 6c 65 28 20 70 2d 3e  ;.    while( p->
1110: 75 2e 61 48 61 73 68 5b 68 5d 20 29 7b 0a 20 20  u.aHash[h] ){.  
1120: 20 20 20 20 69 66 28 20 70 2d 3e 75 2e 61 48 61      if( p->u.aHa
1130: 73 68 5b 68 5d 3d 3d 69 20 29 20 72 65 74 75 72  sh[h]==i ) retur
1140: 6e 20 31 3b 0a 20 20 20 20 20 20 68 2b 2b 3b 0a  n 1;.      h++;.
1150: 20 20 20 20 20 20 69 66 28 20 68 3e 3d 42 49 54        if( h>=BIT
1160: 56 45 43 5f 4e 49 4e 54 20 29 20 68 20 3d 20 30  VEC_NINT ) h = 0
1170: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72 65 74 75  ;.    }.    retu
1180: 72 6e 20 30 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a  rn 0;.  }.}../*.
1190: 2a 2a 20 53 65 74 20 74 68 65 20 69 2d 74 68 20  ** Set the i-th 
11a0: 62 69 74 2e 20 20 52 65 74 75 72 6e 20 30 20 6f  bit.  Return 0 o
11b0: 6e 20 73 75 63 63 65 73 73 20 61 6e 64 20 61 6e  n success and an
11c0: 20 65 72 72 6f 72 20 63 6f 64 65 20 69 66 0a 2a   error code if.*
11d0: 2a 20 61 6e 79 74 68 69 6e 67 20 67 6f 65 73 20  * anything goes 
11e0: 77 72 6f 6e 67 2e 0a 2a 2f 0a 69 6e 74 20 73 71  wrong..*/.int sq
11f0: 6c 69 74 65 33 42 69 74 76 65 63 53 65 74 28 42  lite3BitvecSet(B
1200: 69 74 76 65 63 20 2a 70 2c 20 75 33 32 20 69 29  itvec *p, u32 i)
1210: 7b 0a 20 20 75 33 32 20 68 3b 0a 20 20 61 73 73  {.  u32 h;.  ass
1220: 65 72 74 28 20 70 21 3d 30 20 29 3b 0a 20 20 61  ert( p!=0 );.  a
1230: 73 73 65 72 74 28 20 69 3e 30 20 29 3b 0a 20 20  ssert( i>0 );.  
1240: 61 73 73 65 72 74 28 20 69 3c 3d 70 2d 3e 69 53  assert( i<=p->iS
1250: 69 7a 65 20 29 3b 0a 20 20 69 66 28 20 70 2d 3e  ize );.  if( p->
1260: 69 53 69 7a 65 3c 3d 42 49 54 56 45 43 5f 4e 42  iSize<=BITVEC_NB
1270: 49 54 20 29 7b 0a 20 20 20 20 69 2d 2d 3b 0a 20  IT ){.    i--;. 
1280: 20 20 20 70 2d 3e 75 2e 61 42 69 74 6d 61 70 5b     p->u.aBitmap[
1290: 69 2f 38 5d 20 7c 3d 20 31 20 3c 3c 20 28 69 26  i/8] |= 1 << (i&
12a0: 37 29 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 53  7);.    return S
12b0: 51 4c 49 54 45 5f 4f 4b 3b 0a 20 20 7d 0a 20 20  QLITE_OK;.  }.  
12c0: 69 66 28 20 70 2d 3e 69 44 69 76 69 73 6f 72 20  if( p->iDivisor 
12d0: 29 7b 0a 20 20 20 20 75 33 32 20 62 69 6e 20 3d  ){.    u32 bin =
12e0: 20 28 69 2d 31 29 2f 70 2d 3e 69 44 69 76 69 73   (i-1)/p->iDivis
12f0: 6f 72 3b 0a 20 20 20 20 69 20 3d 20 28 69 2d 31  or;.    i = (i-1
1300: 29 25 70 2d 3e 69 44 69 76 69 73 6f 72 20 2b 20  )%p->iDivisor + 
1310: 31 3b 0a 20 20 20 20 69 66 28 20 70 2d 3e 75 2e  1;.    if( p->u.
1320: 61 70 53 75 62 5b 62 69 6e 5d 3d 3d 30 20 29 7b  apSub[bin]==0 ){
1330: 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33 42 65  .      sqlite3Be
1340: 67 69 6e 42 65 6e 69 67 6e 4d 61 6c 6c 6f 63 28  ginBenignMalloc(
1350: 29 3b 0a 20 20 20 20 20 20 70 2d 3e 75 2e 61 70  );.      p->u.ap
1360: 53 75 62 5b 62 69 6e 5d 20 3d 20 73 71 6c 69 74  Sub[bin] = sqlit
1370: 65 33 42 69 74 76 65 63 43 72 65 61 74 65 28 20  e3BitvecCreate( 
1380: 70 2d 3e 69 44 69 76 69 73 6f 72 20 29 3b 0a 20  p->iDivisor );. 
1390: 20 20 20 20 20 73 71 6c 69 74 65 33 45 6e 64 42       sqlite3EndB
13a0: 65 6e 69 67 6e 4d 61 6c 6c 6f 63 28 29 3b 0a 20  enignMalloc();. 
13b0: 20 20 20 20 20 69 66 28 20 70 2d 3e 75 2e 61 70       if( p->u.ap
13c0: 53 75 62 5b 62 69 6e 5d 3d 3d 30 20 29 20 72 65  Sub[bin]==0 ) re
13d0: 74 75 72 6e 20 53 51 4c 49 54 45 5f 4e 4f 4d 45  turn SQLITE_NOME
13e0: 4d 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72 65 74  M;.    }.    ret
13f0: 75 72 6e 20 73 71 6c 69 74 65 33 42 69 74 76 65  urn sqlite3Bitve
1400: 63 53 65 74 28 70 2d 3e 75 2e 61 70 53 75 62 5b  cSet(p->u.apSub[
1410: 62 69 6e 5d 2c 20 69 29 3b 0a 20 20 7d 0a 20 20  bin], i);.  }.  
1420: 68 20 3d 20 42 49 54 56 45 43 5f 48 41 53 48 28  h = BITVEC_HASH(
1430: 69 29 3b 0a 20 20 77 68 69 6c 65 28 20 70 2d 3e  i);.  while( p->
1440: 75 2e 61 48 61 73 68 5b 68 5d 20 29 7b 0a 20 20  u.aHash[h] ){.  
1450: 20 20 69 66 28 20 70 2d 3e 75 2e 61 48 61 73 68    if( p->u.aHash
1460: 5b 68 5d 3d 3d 69 20 29 20 72 65 74 75 72 6e 20  [h]==i ) return 
1470: 53 51 4c 49 54 45 5f 4f 4b 3b 0a 20 20 20 20 68  SQLITE_OK;.    h
1480: 2b 2b 3b 0a 20 20 20 20 69 66 28 20 68 3d 3d 42  ++;.    if( h==B
1490: 49 54 56 45 43 5f 4e 49 4e 54 20 29 20 68 20 3d  ITVEC_NINT ) h =
14a0: 20 30 3b 0a 20 20 7d 0a 20 20 70 2d 3e 6e 53 65   0;.  }.  p->nSe
14b0: 74 2b 2b 3b 0a 20 20 69 66 28 20 70 2d 3e 6e 53  t++;.  if( p->nS
14c0: 65 74 3e 3d 42 49 54 56 45 43 5f 4d 58 48 41 53  et>=BITVEC_MXHAS
14d0: 48 20 29 7b 0a 20 20 20 20 69 6e 74 20 6a 2c 20  H ){.    int j, 
14e0: 72 63 3b 0a 20 20 20 20 75 33 32 20 61 69 56 61  rc;.    u32 aiVa
14f0: 6c 75 65 73 5b 42 49 54 56 45 43 5f 4e 49 4e 54  lues[BITVEC_NINT
1500: 5d 3b 0a 20 20 20 20 6d 65 6d 63 70 79 28 61 69  ];.    memcpy(ai
1510: 56 61 6c 75 65 73 2c 20 70 2d 3e 75 2e 61 48 61  Values, p->u.aHa
1520: 73 68 2c 20 73 69 7a 65 6f 66 28 61 69 56 61 6c  sh, sizeof(aiVal
1530: 75 65 73 29 29 3b 0a 20 20 20 20 6d 65 6d 73 65  ues));.    memse
1540: 74 28 70 2d 3e 75 2e 61 70 53 75 62 2c 20 30 2c  t(p->u.apSub, 0,
1550: 20 73 69 7a 65 6f 66 28 70 2d 3e 75 2e 61 70 53   sizeof(p->u.apS
1560: 75 62 5b 30 5d 29 2a 42 49 54 56 45 43 5f 4e 50  ub[0])*BITVEC_NP
1570: 54 52 29 3b 0a 20 20 20 20 70 2d 3e 69 44 69 76  TR);.    p->iDiv
1580: 69 73 6f 72 20 3d 20 28 70 2d 3e 69 53 69 7a 65  isor = (p->iSize
1590: 20 2b 20 42 49 54 56 45 43 5f 4e 50 54 52 20 2d   + BITVEC_NPTR -
15a0: 20 31 29 2f 42 49 54 56 45 43 5f 4e 50 54 52 3b   1)/BITVEC_NPTR;
15b0: 0a 20 20 20 20 72 63 20 3d 20 73 71 6c 69 74 65  .    rc = sqlite
15c0: 33 42 69 74 76 65 63 53 65 74 28 70 2c 20 69 29  3BitvecSet(p, i)
15d0: 3b 0a 20 20 20 20 66 6f 72 28 6a 3d 30 3b 20 6a  ;.    for(j=0; j
15e0: 3c 42 49 54 56 45 43 5f 4e 49 4e 54 3b 20 6a 2b  <BITVEC_NINT; j+
15f0: 2b 29 7b 0a 20 20 20 20 20 20 69 66 28 20 61 69  +){.      if( ai
1600: 56 61 6c 75 65 73 5b 6a 5d 20 29 20 72 63 20 7c  Values[j] ) rc |
1610: 3d 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 53  = sqlite3BitvecS
1620: 65 74 28 70 2c 20 61 69 56 61 6c 75 65 73 5b 6a  et(p, aiValues[j
1630: 5d 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72 65  ]);.    }.    re
1640: 74 75 72 6e 20 72 63 3b 0a 20 20 7d 0a 20 20 70  turn rc;.  }.  p
1650: 2d 3e 75 2e 61 48 61 73 68 5b 68 5d 20 3d 20 69  ->u.aHash[h] = i
1660: 3b 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49 54  ;.  return SQLIT
1670: 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 43  E_OK;.}../*.** C
1680: 6c 65 61 72 20 74 68 65 20 69 2d 74 68 20 62 69  lear the i-th bi
1690: 74 2e 20 20 52 65 74 75 72 6e 20 30 20 6f 6e 20  t.  Return 0 on 
16a0: 73 75 63 63 65 73 73 20 61 6e 64 20 61 6e 20 65  success and an e
16b0: 72 72 6f 72 20 63 6f 64 65 20 69 66 0a 2a 2a 20  rror code if.** 
16c0: 61 6e 79 74 68 69 6e 67 20 67 6f 65 73 20 77 72  anything goes wr
16d0: 6f 6e 67 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c  ong..*/.void sql
16e0: 69 74 65 33 42 69 74 76 65 63 43 6c 65 61 72 28  ite3BitvecClear(
16f0: 42 69 74 76 65 63 20 2a 70 2c 20 75 33 32 20 69  Bitvec *p, u32 i
1700: 29 7b 0a 20 20 61 73 73 65 72 74 28 20 70 21 3d  ){.  assert( p!=
1710: 30 20 29 3b 0a 20 20 61 73 73 65 72 74 28 20 69  0 );.  assert( i
1720: 3e 30 20 29 3b 0a 20 20 69 66 28 20 70 2d 3e 69  >0 );.  if( p->i
1730: 53 69 7a 65 3c 3d 42 49 54 56 45 43 5f 4e 42 49  Size<=BITVEC_NBI
1740: 54 20 29 7b 0a 20 20 20 20 69 2d 2d 3b 0a 20 20  T ){.    i--;.  
1750: 20 20 70 2d 3e 75 2e 61 42 69 74 6d 61 70 5b 69    p->u.aBitmap[i
1760: 2f 38 5d 20 26 3d 20 7e 28 31 20 3c 3c 20 28 69  /8] &= ~(1 << (i
1770: 26 37 29 29 3b 0a 20 20 7d 65 6c 73 65 20 69 66  &7));.  }else if
1780: 28 20 70 2d 3e 69 44 69 76 69 73 6f 72 20 29 7b  ( p->iDivisor ){
1790: 0a 20 20 20 20 75 33 32 20 62 69 6e 20 3d 20 28  .    u32 bin = (
17a0: 69 2d 31 29 2f 70 2d 3e 69 44 69 76 69 73 6f 72  i-1)/p->iDivisor
17b0: 3b 0a 20 20 20 20 69 20 3d 20 28 69 2d 31 29 25  ;.    i = (i-1)%
17c0: 70 2d 3e 69 44 69 76 69 73 6f 72 20 2b 20 31 3b  p->iDivisor + 1;
17d0: 0a 20 20 20 20 69 66 28 20 70 2d 3e 75 2e 61 70  .    if( p->u.ap
17e0: 53 75 62 5b 62 69 6e 5d 20 29 7b 0a 20 20 20 20  Sub[bin] ){.    
17f0: 20 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 43    sqlite3BitvecC
1800: 6c 65 61 72 28 70 2d 3e 75 2e 61 70 53 75 62 5b  lear(p->u.apSub[
1810: 62 69 6e 5d 2c 20 69 29 3b 0a 20 20 20 20 7d 0a  bin], i);.    }.
1820: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 69 6e 74    }else{.    int
1830: 20 6a 3b 0a 20 20 20 20 75 33 32 20 61 69 56 61   j;.    u32 aiVa
1840: 6c 75 65 73 5b 42 49 54 56 45 43 5f 4e 49 4e 54  lues[BITVEC_NINT
1850: 5d 3b 0a 20 20 20 20 6d 65 6d 63 70 79 28 61 69  ];.    memcpy(ai
1860: 56 61 6c 75 65 73 2c 20 70 2d 3e 75 2e 61 48 61  Values, p->u.aHa
1870: 73 68 2c 20 73 69 7a 65 6f 66 28 61 69 56 61 6c  sh, sizeof(aiVal
1880: 75 65 73 29 29 3b 0a 20 20 20 20 6d 65 6d 73 65  ues));.    memse
1890: 74 28 70 2d 3e 75 2e 61 48 61 73 68 2c 20 30 2c  t(p->u.aHash, 0,
18a0: 20 73 69 7a 65 6f 66 28 70 2d 3e 75 2e 61 48 61   sizeof(p->u.aHa
18b0: 73 68 5b 30 5d 29 2a 42 49 54 56 45 43 5f 4e 49  sh[0])*BITVEC_NI
18c0: 4e 54 29 3b 0a 20 20 20 20 70 2d 3e 6e 53 65 74  NT);.    p->nSet
18d0: 20 3d 20 30 3b 0a 20 20 20 20 66 6f 72 28 6a 3d   = 0;.    for(j=
18e0: 30 3b 20 6a 3c 42 49 54 56 45 43 5f 4e 49 4e 54  0; j<BITVEC_NINT
18f0: 3b 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 69 66  ; j++){.      if
1900: 28 20 61 69 56 61 6c 75 65 73 5b 6a 5d 20 26 26  ( aiValues[j] &&
1910: 20 61 69 56 61 6c 75 65 73 5b 6a 5d 21 3d 69 20   aiValues[j]!=i 
1920: 29 7b 0a 20 20 20 20 20 20 20 20 73 71 6c 69 74  ){.        sqlit
1930: 65 33 42 69 74 76 65 63 53 65 74 28 70 2c 20 61  e3BitvecSet(p, a
1940: 69 56 61 6c 75 65 73 5b 6a 5d 29 3b 0a 20 20 20  iValues[j]);.   
1950: 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a 7d     }.    }.  }.}
1960: 0a 0a 2f 2a 0a 2a 2a 20 44 65 73 74 72 6f 79 20  ../*.** Destroy 
1970: 61 20 62 69 74 6d 61 70 20 6f 62 6a 65 63 74 2e  a bitmap object.
1980: 20 20 52 65 63 6c 61 69 6d 20 61 6c 6c 20 6d 65    Reclaim all me
1990: 6d 6f 72 79 20 75 73 65 64 2e 0a 2a 2f 0a 76 6f  mory used..*/.vo
19a0: 69 64 20 73 71 6c 69 74 65 33 42 69 74 76 65 63  id sqlite3Bitvec
19b0: 44 65 73 74 72 6f 79 28 42 69 74 76 65 63 20 2a  Destroy(Bitvec *
19c0: 70 29 7b 0a 20 20 69 66 28 20 70 3d 3d 30 20 29  p){.  if( p==0 )
19d0: 20 72 65 74 75 72 6e 3b 0a 20 20 69 66 28 20 70   return;.  if( p
19e0: 2d 3e 69 44 69 76 69 73 6f 72 20 29 7b 0a 20 20  ->iDivisor ){.  
19f0: 20 20 69 6e 74 20 69 3b 0a 20 20 20 20 66 6f 72    int i;.    for
1a00: 28 69 3d 30 3b 20 69 3c 42 49 54 56 45 43 5f 4e  (i=0; i<BITVEC_N
1a10: 50 54 52 3b 20 69 2b 2b 29 7b 0a 20 20 20 20 20  PTR; i++){.     
1a20: 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 44 65   sqlite3BitvecDe
1a30: 73 74 72 6f 79 28 70 2d 3e 75 2e 61 70 53 75 62  stroy(p->u.apSub
1a40: 5b 69 5d 29 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a  [i]);.    }.  }.
1a50: 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70    sqlite3_free(p
1a60: 29 3b 0a 7d 0a 0a 23 69 66 6e 64 65 66 20 53 51  );.}..#ifndef SQ
1a70: 4c 49 54 45 5f 4f 4d 49 54 5f 42 55 49 4c 54 49  LITE_OMIT_BUILTI
1a80: 4e 5f 54 45 53 54 0a 2f 2a 0a 2a 2a 20 4c 65 74  N_TEST./*.** Let
1a90: 20 56 5b 5d 20 62 65 20 61 6e 20 61 72 72 61 79   V[] be an array
1aa0: 20 6f 66 20 75 6e 73 69 67 6e 65 64 20 63 68 61   of unsigned cha
1ab0: 72 61 63 74 65 72 73 20 73 75 66 66 69 63 69 65  racters sufficie
1ac0: 6e 74 20 74 6f 20 68 6f 6c 64 0a 2a 2a 20 75 70  nt to hold.** up
1ad0: 20 74 6f 20 4e 20 62 69 74 73 2e 20 20 4c 65 74   to N bits.  Let
1ae0: 20 49 20 62 65 20 61 6e 20 69 6e 74 65 67 65 72   I be an integer
1af0: 20 62 65 74 77 65 65 6e 20 30 20 61 6e 64 20 4e   between 0 and N
1b00: 2e 20 20 30 3c 3d 49 3c 4e 2e 0a 2a 2a 20 54 68  .  0<=I<N..** Th
1b10: 65 6e 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67  en the following
1b20: 20 6d 61 63 72 6f 73 20 63 61 6e 20 62 65 20 75   macros can be u
1b30: 73 65 64 20 74 6f 20 73 65 74 2c 20 63 6c 65 61  sed to set, clea
1b40: 72 2c 20 6f 72 20 74 65 73 74 0a 2a 2a 20 69 6e  r, or test.** in
1b50: 64 69 76 69 64 75 61 6c 20 62 69 74 73 20 77 69  dividual bits wi
1b60: 74 68 69 6e 20 56 2e 0a 2a 2f 0a 23 64 65 66 69  thin V..*/.#defi
1b70: 6e 65 20 53 45 54 42 49 54 28 56 2c 49 29 20 20  ne SETBIT(V,I)  
1b80: 20 20 20 20 56 5b 49 3e 3e 33 5d 20 7c 3d 20 28      V[I>>3] |= (
1b90: 31 3c 3c 28 49 26 37 29 29 0a 23 64 65 66 69 6e  1<<(I&7)).#defin
1ba0: 65 20 43 4c 45 41 52 42 49 54 28 56 2c 49 29 20  e CLEARBIT(V,I) 
1bb0: 20 20 20 56 5b 49 3e 3e 33 5d 20 26 3d 20 7e 28     V[I>>3] &= ~(
1bc0: 31 3c 3c 28 49 26 37 29 29 0a 23 64 65 66 69 6e  1<<(I&7)).#defin
1bd0: 65 20 54 45 53 54 42 49 54 28 56 2c 49 29 20 20  e TESTBIT(V,I)  
1be0: 20 20 20 28 56 5b 49 3e 3e 33 5d 26 28 31 3c 3c     (V[I>>3]&(1<<
1bf0: 28 49 26 37 29 29 29 21 3d 30 0a 0a 2f 2a 0a 2a  (I&7)))!=0../*.*
1c00: 2a 20 54 68 69 73 20 72 6f 75 74 69 6e 65 20 72  * This routine r
1c10: 75 6e 73 20 61 6e 20 65 78 74 65 6e 73 69 76 65  uns an extensive
1c20: 20 74 65 73 74 20 6f 66 20 74 68 65 20 42 69 74   test of the Bit
1c30: 76 65 63 20 63 6f 64 65 2e 0a 2a 2a 0a 2a 2a 20  vec code..**.** 
1c40: 54 68 65 20 69 6e 70 75 74 20 69 73 20 61 6e 20  The input is an 
1c50: 61 72 72 61 79 20 6f 66 20 69 6e 74 65 67 65 72  array of integer
1c60: 73 20 74 68 61 74 20 61 63 74 73 20 61 73 20 61  s that acts as a
1c70: 20 70 72 6f 67 72 61 6d 0a 2a 2a 20 74 6f 20 74   program.** to t
1c80: 65 73 74 20 74 68 65 20 42 69 74 76 65 63 2e 20  est the Bitvec. 
1c90: 20 54 68 65 20 69 6e 74 65 67 65 72 73 20 61 72   The integers ar
1ca0: 65 20 6f 70 63 6f 64 65 73 20 66 6f 6c 6c 6f 77  e opcodes follow
1cb0: 65 64 0a 2a 2a 20 62 79 20 30 2c 20 31 2c 20 6f  ed.** by 0, 1, o
1cc0: 72 20 33 20 6f 70 65 72 61 6e 64 73 2c 20 64 65  r 3 operands, de
1cd0: 70 65 6e 64 69 6e 67 20 6f 6e 20 74 68 65 20 6f  pending on the o
1ce0: 70 63 6f 64 65 2e 20 20 41 6e 6f 74 68 65 72 0a  pcode.  Another.
1cf0: 2a 2a 20 6f 70 63 6f 64 65 20 66 6f 6c 6c 6f 77  ** opcode follow
1d00: 73 20 69 6d 6d 65 64 69 61 74 65 6c 79 20 61 66  s immediately af
1d10: 74 65 72 20 74 68 65 20 6c 61 73 74 20 6f 70 65  ter the last ope
1d20: 72 61 6e 64 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 72  rand..**.** Ther
1d30: 65 20 61 72 65 20 36 20 6f 70 63 6f 64 65 73 20  e are 6 opcodes 
1d40: 6e 75 6d 62 65 72 65 64 20 66 72 6f 6d 20 30 20  numbered from 0 
1d50: 74 68 72 6f 75 67 68 20 35 2e 20 20 30 20 69 73  through 5.  0 is
1d60: 20 74 68 65 0a 2a 2a 20 22 68 61 6c 74 22 20 6f   the.** "halt" o
1d70: 70 63 6f 64 65 20 61 6e 64 20 63 61 75 73 65 73  pcode and causes
1d80: 20 74 68 65 20 74 65 73 74 20 74 6f 20 65 6e 64   the test to end
1d90: 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 30 20 20 20 20  ..**.**    0    
1da0: 20 20 20 20 20 20 48 61 6c 74 20 61 6e 64 20 72        Halt and r
1db0: 65 74 75 72 6e 20 74 68 65 20 6e 75 6d 62 65 72  eturn the number
1dc0: 20 6f 66 20 65 72 72 6f 72 73 0a 2a 2a 20 20 20   of errors.**   
1dd0: 20 31 20 4e 20 53 20 58 20 20 20 20 53 65 74 20   1 N S X    Set 
1de0: 4e 20 62 69 74 73 20 62 65 67 69 6e 6e 69 6e 67  N bits beginning
1df0: 20 77 69 74 68 20 53 20 61 6e 64 20 69 6e 63 72   with S and incr
1e00: 65 6d 65 6e 74 69 6e 67 20 62 79 20 58 0a 2a 2a  ementing by X.**
1e10: 20 20 20 20 32 20 4e 20 53 20 58 20 20 20 20 43      2 N S X    C
1e20: 6c 65 61 72 20 4e 20 62 69 74 73 20 62 65 67 69  lear N bits begi
1e30: 6e 6e 69 6e 67 20 77 69 74 68 20 53 20 61 6e 64  nning with S and
1e40: 20 69 6e 63 72 65 6d 65 6e 74 69 6e 67 20 62 79   incrementing by
1e50: 20 58 0a 2a 2a 20 20 20 20 33 20 4e 20 20 20 20   X.**    3 N    
1e60: 20 20 20 20 53 65 74 20 4e 20 72 61 6e 64 6f 6d      Set N random
1e70: 6c 79 20 63 68 6f 73 65 6e 20 62 69 74 73 0a 2a  ly chosen bits.*
1e80: 2a 20 20 20 20 34 20 4e 20 20 20 20 20 20 20 20  *    4 N        
1e90: 43 6c 65 61 72 20 4e 20 72 61 6e 64 6f 6d 6c 79  Clear N randomly
1ea0: 20 63 68 6f 73 65 6e 20 62 69 74 73 0a 2a 2a 20   chosen bits.** 
1eb0: 20 20 20 35 20 4e 20 53 20 58 20 20 20 20 53 65     5 N S X    Se
1ec0: 74 20 4e 20 62 69 74 73 20 66 72 6f 6d 20 53 20  t N bits from S 
1ed0: 69 6e 63 72 65 6d 65 6e 74 20 58 20 69 6e 20 61  increment X in a
1ee0: 72 72 61 79 20 6f 6e 6c 79 2c 20 6e 6f 74 20 69  rray only, not i
1ef0: 6e 20 62 69 74 76 65 63 0a 2a 2a 0a 2a 2a 20 54  n bitvec.**.** T
1f00: 68 65 20 6f 70 63 6f 64 65 73 20 31 20 74 68 72  he opcodes 1 thr
1f10: 6f 75 67 68 20 34 20 70 65 72 66 6f 72 6d 20 73  ough 4 perform s
1f20: 65 74 20 61 6e 64 20 63 6c 65 61 72 20 6f 70 65  et and clear ope
1f30: 72 61 74 69 6f 6e 73 20 61 72 65 20 70 65 72 66  rations are perf
1f40: 6f 72 6d 65 64 0a 2a 2a 20 6f 6e 20 62 6f 74 68  ormed.** on both
1f50: 20 61 20 42 69 74 76 65 63 20 6f 62 6a 65 63 74   a Bitvec object
1f60: 20 61 6e 64 20 6f 6e 20 61 20 6c 69 6e 65 61 72   and on a linear
1f70: 20 61 72 72 61 79 20 6f 66 20 62 69 74 73 20 6f   array of bits o
1f80: 62 74 61 69 6e 65 64 20 66 72 6f 6d 20 6d 61 6c  btained from mal
1f90: 6c 6f 63 2e 0a 2a 2a 20 4f 70 63 6f 64 65 20 35  loc..** Opcode 5
1fa0: 20 77 6f 72 6b 73 20 6f 6e 20 74 68 65 20 6c 69   works on the li
1fb0: 6e 65 61 72 20 61 72 72 61 79 20 6f 6e 6c 79 2c  near array only,
1fc0: 20 6e 6f 74 20 6f 6e 20 74 68 65 20 42 69 74 76   not on the Bitv
1fd0: 65 63 2e 0a 2a 2a 20 4f 70 63 6f 64 65 20 35 20  ec..** Opcode 5 
1fe0: 69 73 20 75 73 65 64 20 74 6f 20 64 65 6c 69 62  is used to delib
1ff0: 65 72 61 74 65 6c 79 20 69 6e 64 75 63 65 20 61  erately induce a
2000: 20 66 61 75 6c 74 20 69 6e 20 6f 72 64 65 72 20   fault in order 
2010: 74 6f 0a 2a 2a 20 63 6f 6e 66 69 72 6d 20 74 68  to.** confirm th
2020: 61 74 20 65 72 72 6f 72 20 64 65 74 65 63 74 69  at error detecti
2030: 6f 6e 20 77 6f 72 6b 73 2e 0a 2a 2a 0a 2a 2a 20  on works..**.** 
2040: 41 74 20 74 68 65 20 63 6f 6e 63 6c 75 73 69 6f  At the conclusio
2050: 6e 20 6f 66 20 74 68 65 20 74 65 73 74 20 74 68  n of the test th
2060: 65 20 6c 69 6e 65 61 72 20 61 72 72 61 79 20 69  e linear array i
2070: 73 20 63 6f 6d 70 61 72 65 64 0a 2a 2a 20 61 67  s compared.** ag
2080: 61 69 6e 73 74 20 74 68 65 20 42 69 74 76 65 63  ainst the Bitvec
2090: 20 6f 62 6a 65 63 74 2e 20 20 49 66 20 74 68 65   object.  If the
20a0: 72 65 20 61 72 65 20 61 6e 79 20 64 69 66 66 65  re are any diffe
20b0: 72 65 6e 63 65 73 2c 0a 2a 2a 20 61 6e 20 65 72  rences,.** an er
20c0: 72 6f 72 20 69 73 20 72 65 74 75 72 6e 65 64 2e  ror is returned.
20d0: 20 20 49 66 20 74 68 65 79 20 61 72 65 20 74 68    If they are th
20e0: 65 20 73 61 6d 65 2c 20 7a 65 72 6f 20 69 73 20  e same, zero is 
20f0: 72 65 74 75 72 6e 65 64 2e 0a 2a 2a 0a 2a 2a 20  returned..**.** 
2100: 49 66 20 61 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f  If a memory allo
2110: 63 61 74 69 6f 6e 20 65 72 72 6f 72 20 6f 63 63  cation error occ
2120: 75 72 73 2c 20 72 65 74 75 72 6e 20 2d 31 2e 0a  urs, return -1..
2130: 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 42 69  */.int sqlite3Bi
2140: 74 76 65 63 42 75 69 6c 74 69 6e 54 65 73 74 28  tvecBuiltinTest(
2150: 69 6e 74 20 73 7a 2c 20 69 6e 74 20 2a 61 4f 70  int sz, int *aOp
2160: 29 7b 0a 20 20 42 69 74 76 65 63 20 2a 70 42 69  ){.  Bitvec *pBi
2170: 74 76 65 63 20 3d 20 30 3b 0a 20 20 75 6e 73 69  tvec = 0;.  unsi
2180: 67 6e 65 64 20 63 68 61 72 20 2a 70 56 20 3d 20  gned char *pV = 
2190: 30 3b 0a 20 20 69 6e 74 20 72 63 20 3d 20 2d 31  0;.  int rc = -1
21a0: 3b 0a 20 20 69 6e 74 20 69 2c 20 6e 78 2c 20 70  ;.  int i, nx, p
21b0: 63 2c 20 6f 70 3b 0a 0a 20 20 2f 2a 20 41 6c 6c  c, op;..  /* All
21c0: 6f 63 61 74 65 20 74 68 65 20 42 69 74 76 65 63  ocate the Bitvec
21d0: 20 74 6f 20 62 65 20 74 65 73 74 65 64 20 61 6e   to be tested an
21e0: 64 20 61 20 6c 69 6e 65 61 72 20 61 72 72 61 79  d a linear array
21f0: 20 6f 66 0a 20 20 2a 2a 20 62 69 74 73 20 74 6f   of.  ** bits to
2200: 20 61 63 74 20 61 73 20 74 68 65 20 72 65 66 65   act as the refe
2210: 72 65 6e 63 65 20 2a 2f 0a 20 20 70 42 69 74 76  rence */.  pBitv
2220: 65 63 20 3d 20 73 71 6c 69 74 65 33 42 69 74 76  ec = sqlite3Bitv
2230: 65 63 43 72 65 61 74 65 28 20 73 7a 20 29 3b 0a  ecCreate( sz );.
2240: 20 20 70 56 20 3d 20 73 71 6c 69 74 65 33 5f 6d    pV = sqlite3_m
2250: 61 6c 6c 6f 63 28 20 28 73 7a 2b 37 29 2f 38 20  alloc( (sz+7)/8 
2260: 2b 20 31 20 29 3b 0a 20 20 69 66 28 20 70 42 69  + 1 );.  if( pBi
2270: 74 76 65 63 3d 3d 30 20 7c 7c 20 70 56 3d 3d 30  tvec==0 || pV==0
2280: 20 29 20 67 6f 74 6f 20 62 69 74 76 65 63 5f 65   ) goto bitvec_e
2290: 6e 64 3b 0a 20 20 6d 65 6d 73 65 74 28 70 56 2c  nd;.  memset(pV,
22a0: 20 30 2c 20 28 73 7a 2b 37 29 2f 38 20 2b 20 31   0, (sz+7)/8 + 1
22b0: 29 3b 0a 0a 20 20 2f 2a 20 52 75 6e 20 74 68 65  );..  /* Run the
22c0: 20 70 72 6f 67 72 61 6d 20 2a 2f 0a 20 20 70 63   program */.  pc
22d0: 20 3d 20 30 3b 0a 20 20 77 68 69 6c 65 28 20 28   = 0;.  while( (
22e0: 6f 70 20 3d 20 61 4f 70 5b 70 63 5d 29 21 3d 30  op = aOp[pc])!=0
22f0: 20 29 7b 0a 20 20 20 20 73 77 69 74 63 68 28 20   ){.    switch( 
2300: 6f 70 20 29 7b 0a 20 20 20 20 20 20 63 61 73 65  op ){.      case
2310: 20 31 3a 0a 20 20 20 20 20 20 63 61 73 65 20 32   1:.      case 2
2320: 3a 0a 20 20 20 20 20 20 63 61 73 65 20 35 3a 20  :.      case 5: 
2330: 7b 0a 20 20 20 20 20 20 20 20 6e 78 20 3d 20 34  {.        nx = 4
2340: 3b 0a 20 20 20 20 20 20 20 20 69 20 3d 20 61 4f  ;.        i = aO
2350: 70 5b 70 63 2b 32 5d 20 2d 20 31 3b 0a 20 20 20  p[pc+2] - 1;.   
2360: 20 20 20 20 20 61 4f 70 5b 70 63 2b 32 5d 20 2b       aOp[pc+2] +
2370: 3d 20 61 4f 70 5b 70 63 2b 33 5d 3b 0a 20 20 20  = aOp[pc+3];.   
2380: 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20       break;.    
2390: 20 20 7d 0a 20 20 20 20 20 20 63 61 73 65 20 33    }.      case 3
23a0: 3a 0a 20 20 20 20 20 20 63 61 73 65 20 34 3a 20  :.      case 4: 
23b0: 0a 20 20 20 20 20 20 64 65 66 61 75 6c 74 3a 20  .      default: 
23c0: 7b 0a 20 20 20 20 20 20 20 20 6e 78 20 3d 20 32  {.        nx = 2
23d0: 3b 0a 20 20 20 20 20 20 20 20 73 71 6c 69 74 65  ;.        sqlite
23e0: 33 5f 72 61 6e 64 6f 6d 6e 65 73 73 28 73 69 7a  3_randomness(siz
23f0: 65 6f 66 28 69 29 2c 20 26 69 29 3b 0a 20 20 20  eof(i), &i);.   
2400: 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20       break;.    
2410: 20 20 7d 0a 20 20 20 20 7d 0a 20 20 20 20 69 66    }.    }.    if
2420: 28 20 28 2d 2d 61 4f 70 5b 70 63 2b 31 5d 29 20  ( (--aOp[pc+1]) 
2430: 3e 20 30 20 29 20 6e 78 20 3d 20 30 3b 0a 20 20  > 0 ) nx = 0;.  
2440: 20 20 70 63 20 2b 3d 20 6e 78 3b 0a 20 20 20 20    pc += nx;.    
2450: 69 20 3d 20 28 69 20 26 20 30 78 37 66 66 66 66  i = (i & 0x7ffff
2460: 66 66 66 29 25 73 7a 3b 0a 20 20 20 20 69 66 28  fff)%sz;.    if(
2470: 20 28 6f 70 20 26 20 31 29 21 3d 30 20 29 7b 0a   (op & 1)!=0 ){.
2480: 20 20 20 20 20 20 53 45 54 42 49 54 28 70 56 2c        SETBIT(pV,
2490: 20 28 69 2b 31 29 29 3b 0a 20 20 20 20 20 20 69   (i+1));.      i
24a0: 66 28 20 6f 70 21 3d 35 20 29 7b 0a 20 20 20 20  f( op!=5 ){.    
24b0: 20 20 20 20 69 66 28 20 73 71 6c 69 74 65 33 42      if( sqlite3B
24c0: 69 74 76 65 63 53 65 74 28 70 42 69 74 76 65 63  itvecSet(pBitvec
24d0: 2c 20 69 2b 31 29 20 29 20 67 6f 74 6f 20 62 69  , i+1) ) goto bi
24e0: 74 76 65 63 5f 65 6e 64 3b 0a 20 20 20 20 20 20  tvec_end;.      
24f0: 7d 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20  }.    }else{.   
2500: 20 20 20 43 4c 45 41 52 42 49 54 28 70 56 2c 20     CLEARBIT(pV, 
2510: 28 69 2b 31 29 29 3b 0a 20 20 20 20 20 20 73 71  (i+1));.      sq
2520: 6c 69 74 65 33 42 69 74 76 65 63 43 6c 65 61 72  lite3BitvecClear
2530: 28 70 42 69 74 76 65 63 2c 20 69 2b 31 29 3b 0a  (pBitvec, i+1);.
2540: 20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 2f 2a 20      }.  }..  /* 
2550: 54 65 73 74 20 74 6f 20 6d 61 6b 65 20 73 75 72  Test to make sur
2560: 65 20 74 68 65 20 6c 69 6e 65 61 72 20 61 72 72  e the linear arr
2570: 61 79 20 65 78 61 63 74 6c 79 20 6d 61 74 63 68  ay exactly match
2580: 65 73 20 74 68 65 0a 20 20 2a 2a 20 42 69 74 76  es the.  ** Bitv
2590: 65 63 20 6f 62 6a 65 63 74 2e 20 20 53 74 61 72  ec object.  Star
25a0: 74 20 77 69 74 68 20 74 68 65 20 61 73 73 75 6d  t with the assum
25b0: 70 74 69 6f 6e 20 74 68 61 74 20 74 68 65 79 20  ption that they 
25c0: 64 6f 0a 20 20 2a 2a 20 6d 61 74 63 68 20 28 72  do.  ** match (r
25d0: 63 3d 3d 30 29 2e 20 20 43 68 61 6e 67 65 20 72  c==0).  Change r
25e0: 63 20 74 6f 20 6e 6f 6e 2d 7a 65 72 6f 20 69 66  c to non-zero if
25f0: 20 61 20 64 69 73 63 72 65 70 61 6e 63 79 0a 20   a discrepancy. 
2600: 20 2a 2a 20 69 73 20 66 6f 75 6e 64 2e 0a 20 20   ** is found..  
2610: 2a 2f 0a 20 20 72 63 20 3d 20 73 71 6c 69 74 65  */.  rc = sqlite
2620: 33 42 69 74 76 65 63 54 65 73 74 28 30 2c 30 29  3BitvecTest(0,0)
2630: 20 2b 20 73 71 6c 69 74 65 33 42 69 74 76 65 63   + sqlite3Bitvec
2640: 54 65 73 74 28 70 42 69 74 76 65 63 2c 20 73 7a  Test(pBitvec, sz
2650: 2b 31 29 0a 20 20 20 20 20 20 20 20 20 20 2b 20  +1).          + 
2660: 73 71 6c 69 74 65 33 42 69 74 76 65 63 54 65 73  sqlite3BitvecTes
2670: 74 28 70 42 69 74 76 65 63 2c 20 30 29 3b 0a 20  t(pBitvec, 0);. 
2680: 20 66 6f 72 28 69 3d 31 3b 20 69 3c 3d 73 7a 3b   for(i=1; i<=sz;
2690: 20 69 2b 2b 29 7b 0a 20 20 20 20 69 66 28 20 20   i++){.    if(  
26a0: 28 54 45 53 54 42 49 54 28 70 56 2c 69 29 29 21  (TESTBIT(pV,i))!
26b0: 3d 73 71 6c 69 74 65 33 42 69 74 76 65 63 54 65  =sqlite3BitvecTe
26c0: 73 74 28 70 42 69 74 76 65 63 2c 69 29 20 29 7b  st(pBitvec,i) ){
26d0: 0a 20 20 20 20 20 20 72 63 20 3d 20 69 3b 0a 20  .      rc = i;. 
26e0: 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20       break;.    
26f0: 7d 0a 20 20 7d 0a 0a 20 20 2f 2a 20 46 72 65 65  }.  }..  /* Free
2700: 20 61 6c 6c 6f 63 61 74 65 64 20 73 74 72 75 63   allocated struc
2710: 74 75 72 65 20 2a 2f 0a 62 69 74 76 65 63 5f 65  ture */.bitvec_e
2720: 6e 64 3a 0a 20 20 73 71 6c 69 74 65 33 5f 66 72  nd:.  sqlite3_fr
2730: 65 65 28 70 56 29 3b 0a 20 20 73 71 6c 69 74 65  ee(pV);.  sqlite
2740: 33 42 69 74 76 65 63 44 65 73 74 72 6f 79 28 70  3BitvecDestroy(p
2750: 42 69 74 76 65 63 29 3b 0a 20 20 72 65 74 75 72  Bitvec);.  retur
2760: 6e 20 72 63 3b 0a 7d 0a 23 65 6e 64 69 66 20 2f  n rc;.}.#endif /
2770: 2a 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 42 55  * SQLITE_OMIT_BU
2780: 49 4c 54 49 4e 5f 54 45 53 54 20 2a 2f 0a        ILTIN_TEST */.