/ Hex Artifact Content
Login

Artifact 06ad2c36a9c3819c0b9cbffec7b15f58d5d834e0:


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: 28 73 69 7a 65 6f 66 28 76 6f 69 64 2a 29 2a 31  (sizeof(void*)*1
0700: 32 38 29 20 20 2f 2a 20 35 31 32 20 6f 6e 20 33  28)  /* 512 on 3
0710: 32 62 69 74 2e 20 20 31 30 32 34 20 6f 6e 20 36  2bit.  1024 on 6
0720: 34 62 69 74 20 2a 2f 0a 0a 2f 2a 20 52 6f 75 6e  4bit */../* Roun
0730: 64 20 74 68 65 20 75 6e 69 6f 6e 20 73 69 7a 65  d the union size
0740: 20 64 6f 77 6e 20 74 6f 20 74 68 65 20 6e 65 61   down to the nea
0750: 72 65 73 74 20 70 6f 69 6e 74 65 72 20 62 6f 75  rest pointer bou
0760: 6e 64 61 72 79 2c 20 73 69 6e 63 65 20 74 68 61  ndary, since tha
0770: 74 27 73 20 68 6f 77 20 0a 2a 2a 20 69 74 20 77  t's how .** it w
0780: 69 6c 6c 20 62 65 20 61 6c 69 67 6e 65 64 20 77  ill be aligned w
0790: 69 74 68 69 6e 20 74 68 65 20 42 69 74 76 65 63  ithin the Bitvec
07a0: 20 73 74 72 75 63 74 2e 20 2a 2f 0a 23 64 65 66   struct. */.#def
07b0: 69 6e 65 20 42 49 54 56 45 43 5f 55 53 49 5a 45  ine BITVEC_USIZE
07c0: 20 20 20 20 20 28 28 28 42 49 54 56 45 43 5f 53       (((BITVEC_S
07d0: 5a 2d 28 33 2a 73 69 7a 65 6f 66 28 75 33 32 29  Z-(3*sizeof(u32)
07e0: 29 29 2f 73 69 7a 65 6f 66 28 42 69 74 76 65 63  ))/sizeof(Bitvec
07f0: 2a 29 29 2a 73 69 7a 65 6f 66 28 42 69 74 76 65  *))*sizeof(Bitve
0800: 63 2a 29 29 0a 0a 2f 2a 20 54 79 70 65 20 6f 66  c*))../* Type of
0810: 20 74 68 65 20 61 72 72 61 79 20 22 65 6c 65 6d   the array "elem
0820: 65 6e 74 22 20 66 6f 72 20 74 68 65 20 62 69 74  ent" for the bit
0830: 6d 61 70 20 72 65 70 72 65 73 65 6e 74 61 74 69  map representati
0840: 6f 6e 2e 20 0a 2a 2a 20 53 68 6f 75 6c 64 20 62  on. .** Should b
0850: 65 20 61 20 70 6f 77 65 72 20 6f 66 20 32 2c 20  e a power of 2, 
0860: 61 6e 64 20 69 64 65 61 6c 6c 79 2c 20 65 76 65  and ideally, eve
0870: 6e 6c 79 20 64 69 76 69 64 65 20 69 6e 74 6f 20  nly divide into 
0880: 42 49 54 56 45 43 5f 55 53 49 5a 45 2e 20 0a 2a  BITVEC_USIZE. .*
0890: 2a 20 53 65 74 74 69 6e 67 20 74 68 69 73 20 74  * Setting this t
08a0: 6f 20 74 68 65 20 22 6e 61 74 75 72 61 6c 20 77  o the "natural w
08b0: 6f 72 64 22 20 73 69 7a 65 20 6f 66 20 79 6f 75  ord" size of you
08c0: 72 20 43 50 55 20 6d 61 79 20 69 6d 70 72 6f 76  r CPU may improv
08d0: 65 0a 2a 2a 20 70 65 72 66 6f 72 6d 61 6e 63 65  e.** performance
08e0: 2e 20 2a 2f 0a 23 64 65 66 69 6e 65 20 42 49 54  . */.#define BIT
08f0: 56 45 43 5f 54 45 4c 45 4d 20 20 20 20 20 75 38  VEC_TELEM     u8
0900: 0a 2f 2a 20 53 69 7a 65 2c 20 69 6e 20 62 69 74  ./* Size, in bit
0910: 73 2c 20 6f 66 20 74 68 65 20 62 69 74 6d 61 70  s, of the bitmap
0920: 20 65 6c 65 6d 65 6e 74 2e 20 2a 2f 0a 23 64 65   element. */.#de
0930: 66 69 6e 65 20 42 49 54 56 45 43 5f 53 5a 45 4c  fine BITVEC_SZEL
0940: 45 4d 20 20 20 20 38 0a 2f 2a 20 4e 75 6d 62 65  EM    8./* Numbe
0950: 72 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20 69 6e  r of elements in
0960: 20 61 20 62 69 74 6d 61 70 20 61 72 72 61 79 2e   a bitmap array.
0970: 20 2a 2f 0a 23 64 65 66 69 6e 65 20 42 49 54 56   */.#define BITV
0980: 45 43 5f 4e 45 4c 45 4d 20 20 20 20 20 28 42 49  EC_NELEM     (BI
0990: 54 56 45 43 5f 55 53 49 5a 45 2f 73 69 7a 65 6f  TVEC_USIZE/sizeo
09a0: 66 28 42 49 54 56 45 43 5f 54 45 4c 45 4d 29 29  f(BITVEC_TELEM))
09b0: 0a 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 62 69  ./* Number of bi
09c0: 74 73 20 69 6e 20 74 68 65 20 62 69 74 6d 61 70  ts in the bitmap
09d0: 20 61 72 72 61 79 2e 20 2a 2f 0a 23 64 65 66 69   array. */.#defi
09e0: 6e 65 20 42 49 54 56 45 43 5f 4e 42 49 54 20 20  ne BITVEC_NBIT  
09f0: 20 20 20 20 28 42 49 54 56 45 43 5f 4e 45 4c 45      (BITVEC_NELE
0a00: 4d 2a 42 49 54 56 45 43 5f 53 5a 45 4c 45 4d 29  M*BITVEC_SZELEM)
0a10: 0a 0a 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 75  ../* Number of u
0a20: 33 32 20 76 61 6c 75 65 73 20 69 6e 20 68 61 73  32 values in has
0a30: 68 20 74 61 62 6c 65 2e 20 2a 2f 0a 23 64 65 66  h table. */.#def
0a40: 69 6e 65 20 42 49 54 56 45 43 5f 4e 49 4e 54 20  ine BITVEC_NINT 
0a50: 20 20 20 20 20 28 42 49 54 56 45 43 5f 55 53 49       (BITVEC_USI
0a60: 5a 45 2f 73 69 7a 65 6f 66 28 75 33 32 29 29 0a  ZE/sizeof(u32)).
0a70: 2f 2a 20 4d 61 78 69 6d 75 6d 20 6e 75 6d 62 65  /* Maximum numbe
0a80: 72 20 6f 66 20 65 6e 74 72 69 65 73 20 69 6e 20  r of entries in 
0a90: 68 61 73 68 20 74 61 62 6c 65 20 62 65 66 6f 72  hash table befor
0aa0: 65 20 0a 2a 2a 20 73 75 62 2d 64 69 76 69 64 69  e .** sub-dividi
0ab0: 6e 67 20 61 6e 64 20 72 65 2d 68 61 73 68 69 6e  ng and re-hashin
0ac0: 67 2e 20 2a 2f 0a 23 64 65 66 69 6e 65 20 42 49  g. */.#define BI
0ad0: 54 56 45 43 5f 4d 58 48 41 53 48 20 20 20 20 28  TVEC_MXHASH    (
0ae0: 42 49 54 56 45 43 5f 4e 49 4e 54 2f 32 29 0a 2f  BITVEC_NINT/2)./
0af0: 2a 20 48 61 73 68 69 6e 67 20 66 75 6e 63 74 69  * Hashing functi
0b00: 6f 6e 20 66 6f 72 20 74 68 65 20 61 48 61 73 68  on for the aHash
0b10: 20 72 65 70 72 65 73 65 6e 74 61 74 69 6f 6e 2e   representation.
0b20: 0a 2a 2a 20 45 6d 70 69 72 69 63 61 6c 20 74 65  .** Empirical te
0b30: 73 74 69 6e 67 20 73 68 6f 77 65 64 20 74 68 61  sting showed tha
0b40: 74 20 74 68 65 20 2a 33 37 20 6d 75 6c 74 69 70  t the *37 multip
0b50: 6c 69 65 72 20 0a 2a 2a 20 28 61 6e 20 61 72 62  lier .** (an arb
0b60: 69 74 72 61 72 79 20 70 72 69 6d 65 29 69 6e 20  itrary prime)in 
0b70: 74 68 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f  the hash functio
0b80: 6e 20 70 72 6f 76 69 64 65 64 20 0a 2a 2a 20 6e  n provided .** n
0b90: 6f 20 66 65 77 65 72 20 63 6f 6c 6c 69 73 69 6f  o fewer collisio
0ba0: 6e 73 20 74 68 61 6e 20 74 68 65 20 6e 6f 2d 6f  ns than the no-o
0bb0: 70 20 2a 31 2e 20 2a 2f 0a 23 64 65 66 69 6e 65  p *1. */.#define
0bc0: 20 42 49 54 56 45 43 5f 48 41 53 48 28 58 29 20   BITVEC_HASH(X) 
0bd0: 20 20 28 28 28 58 29 2a 31 29 25 42 49 54 56 45    (((X)*1)%BITVE
0be0: 43 5f 4e 49 4e 54 29 0a 0a 23 64 65 66 69 6e 65  C_NINT)..#define
0bf0: 20 42 49 54 56 45 43 5f 4e 50 54 52 20 20 20 20   BITVEC_NPTR    
0c00: 20 20 28 42 49 54 56 45 43 5f 55 53 49 5a 45 2f    (BITVEC_USIZE/
0c10: 73 69 7a 65 6f 66 28 42 69 74 76 65 63 20 2a 29  sizeof(Bitvec *)
0c20: 29 0a 0a 0a 2f 2a 0a 2a 2a 20 41 20 62 69 74 6d  ).../*.** A bitm
0c30: 61 70 20 69 73 20 61 6e 20 69 6e 73 74 61 6e 63  ap is an instanc
0c40: 65 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69  e of the followi
0c50: 6e 67 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2a  ng structure..**
0c60: 0a 2a 2a 20 54 68 69 73 20 62 69 74 6d 61 70 20  .** This bitmap 
0c70: 72 65 63 6f 72 64 73 20 74 68 65 20 65 78 69 73  records the exis
0c80: 74 61 6e 63 65 20 6f 66 20 7a 65 72 6f 20 6f 72  tance of zero or
0c90: 20 6d 6f 72 65 20 62 69 74 73 0a 2a 2a 20 77 69   more bits.** wi
0ca0: 74 68 20 76 61 6c 75 65 73 20 62 65 74 77 65 65  th values betwee
0cb0: 6e 20 31 20 61 6e 64 20 69 53 69 7a 65 2c 20 69  n 1 and iSize, i
0cc0: 6e 63 6c 75 73 69 76 65 2e 0a 2a 2a 0a 2a 2a 20  nclusive..**.** 
0cd0: 54 68 65 72 65 20 61 72 65 20 74 68 72 65 65 20  There are three 
0ce0: 70 6f 73 73 69 62 6c 65 20 72 65 70 72 65 73 65  possible represe
0cf0: 6e 74 61 74 69 6f 6e 73 20 6f 66 20 74 68 65 20  ntations of the 
0d00: 62 69 74 6d 61 70 2e 0a 2a 2a 20 49 66 20 69 53  bitmap..** If iS
0d10: 69 7a 65 3c 3d 42 49 54 56 45 43 5f 4e 42 49 54  ize<=BITVEC_NBIT
0d20: 2c 20 74 68 65 6e 20 42 69 74 76 65 63 2e 75 2e  , then Bitvec.u.
0d30: 61 42 69 74 6d 61 70 5b 5d 20 69 73 20 61 20 73  aBitmap[] is a s
0d40: 74 72 61 69 67 68 74 0a 2a 2a 20 62 69 74 6d 61  traight.** bitma
0d50: 70 2e 20 20 54 68 65 20 6c 65 61 73 74 20 73 69  p.  The least si
0d60: 67 6e 69 66 69 63 61 6e 74 20 62 69 74 20 69 73  gnificant bit is
0d70: 20 62 69 74 20 31 2e 0a 2a 2a 0a 2a 2a 20 49 66   bit 1..**.** If
0d80: 20 69 53 69 7a 65 3e 42 49 54 56 45 43 5f 4e 42   iSize>BITVEC_NB
0d90: 49 54 20 61 6e 64 20 69 44 69 76 69 73 6f 72 3d  IT and iDivisor=
0da0: 3d 30 20 74 68 65 6e 20 42 69 74 76 65 63 2e 75  =0 then Bitvec.u
0db0: 2e 61 48 61 73 68 5b 5d 20 69 73 0a 2a 2a 20 61  .aHash[] is.** a
0dc0: 20 68 61 73 68 20 74 61 62 6c 65 20 74 68 61 74   hash table that
0dd0: 20 77 69 6c 6c 20 68 6f 6c 64 20 75 70 20 74 6f   will hold up to
0de0: 20 42 49 54 56 45 43 5f 4d 58 48 41 53 48 20 64   BITVEC_MXHASH d
0df0: 69 73 74 69 6e 63 74 20 76 61 6c 75 65 73 2e 0a  istinct values..
0e00: 2a 2a 0a 2a 2a 20 4f 74 68 65 72 77 69 73 65 2c  **.** Otherwise,
0e10: 20 74 68 65 20 76 61 6c 75 65 20 69 20 69 73 20   the value i is 
0e20: 72 65 64 69 72 65 63 74 65 64 20 69 6e 74 6f 20  redirected into 
0e30: 6f 6e 65 20 6f 66 20 42 49 54 56 45 43 5f 4e 50  one of BITVEC_NP
0e40: 54 52 0a 2a 2a 20 73 75 62 2d 62 69 74 6d 61 70  TR.** sub-bitmap
0e50: 73 20 70 6f 69 6e 74 65 64 20 74 6f 20 62 79 20  s pointed to by 
0e60: 42 69 74 76 65 63 2e 75 2e 61 70 53 75 62 5b 5d  Bitvec.u.apSub[]
0e70: 2e 20 20 45 61 63 68 20 73 75 62 62 69 74 6d 61  .  Each subbitma
0e80: 70 0a 2a 2a 20 68 61 6e 64 6c 65 73 20 75 70 20  p.** handles up 
0e90: 74 6f 20 69 44 69 76 69 73 6f 72 20 73 65 70 61  to iDivisor sepa
0ea0: 72 61 74 65 20 76 61 6c 75 65 73 20 6f 66 20 69  rate values of i
0eb0: 2e 20 20 61 70 53 75 62 5b 30 5d 20 68 6f 6c 64  .  apSub[0] hold
0ec0: 73 0a 2a 2a 20 76 61 6c 75 65 73 20 62 65 74 77  s.** values betw
0ed0: 65 65 6e 20 31 20 61 6e 64 20 69 44 69 76 69 73  een 1 and iDivis
0ee0: 6f 72 2e 20 20 61 70 53 75 62 5b 31 5d 20 68 6f  or.  apSub[1] ho
0ef0: 6c 64 73 20 76 61 6c 75 65 73 20 62 65 74 77 65  lds values betwe
0f00: 65 6e 0a 2a 2a 20 69 44 69 76 69 73 6f 72 2b 31  en.** iDivisor+1
0f10: 20 61 6e 64 20 32 2a 69 44 69 76 69 73 6f 72 2e   and 2*iDivisor.
0f20: 20 20 61 70 53 75 62 5b 4e 5d 20 68 6f 6c 64 73    apSub[N] holds
0f30: 20 76 61 6c 75 65 73 20 62 65 74 77 65 65 6e 0a   values between.
0f40: 2a 2a 20 4e 2a 69 44 69 76 69 73 6f 72 2b 31 20  ** N*iDivisor+1 
0f50: 61 6e 64 20 28 4e 2b 31 29 2a 69 44 69 76 69 73  and (N+1)*iDivis
0f60: 6f 72 2e 20 20 45 61 63 68 20 73 75 62 62 69 74  or.  Each subbit
0f70: 6d 61 70 20 69 73 20 6e 6f 72 6d 61 6c 69 7a 65  map is normalize
0f80: 64 0a 2a 2a 20 74 6f 20 68 6f 6c 64 20 64 65 61  d.** to hold dea
0f90: 6c 20 77 69 74 68 20 76 61 6c 75 65 73 20 62 65  l with values be
0fa0: 74 77 65 65 6e 20 31 20 61 6e 64 20 69 44 69 76  tween 1 and iDiv
0fb0: 69 73 6f 72 2e 0a 2a 2f 0a 73 74 72 75 63 74 20  isor..*/.struct 
0fc0: 42 69 74 76 65 63 20 7b 0a 20 20 75 33 32 20 69  Bitvec {.  u32 i
0fd0: 53 69 7a 65 3b 20 20 20 20 20 20 2f 2a 20 4d 61  Size;      /* Ma
0fe0: 78 69 6d 75 6d 20 62 69 74 20 69 6e 64 65 78 2e  ximum bit index.
0ff0: 20 20 4d 61 78 20 69 53 69 7a 65 20 69 73 20 34    Max iSize is 4
1000: 2c 32 39 34 2c 39 36 37 2c 32 39 36 2e 20 2a 2f  ,294,967,296. */
1010: 0a 20 20 75 33 32 20 6e 53 65 74 3b 20 20 20 20  .  u32 nSet;    
1020: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
1030: 62 69 74 73 20 74 68 61 74 20 61 72 65 20 73 65  bits that are se
1040: 74 20 2d 20 6f 6e 6c 79 20 76 61 6c 69 64 20 66  t - only valid f
1050: 6f 72 20 61 48 61 73 68 0a 20 20 20 20 20 20 20  or aHash.       
1060: 20 20 20 20 20 20 20 20 20 20 20 2a 2a 20 65 6c             ** el
1070: 65 6d 65 6e 74 2e 20 20 4d 61 78 20 69 73 20 42  ement.  Max is B
1080: 49 54 56 45 43 5f 4e 49 4e 54 2e 20 20 46 6f 72  ITVEC_NINT.  For
1090: 20 42 49 54 56 45 43 5f 53 5a 20 6f 66 20 35 31   BITVEC_SZ of 51
10a0: 32 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  2,.             
10b0: 20 20 20 20 20 2a 2a 20 74 68 69 73 20 77 6f 75       ** this wou
10c0: 6c 64 20 62 65 20 31 32 35 2e 20 2a 2f 0a 20 20  ld be 125. */.  
10d0: 75 33 32 20 69 44 69 76 69 73 6f 72 3b 20 20 20  u32 iDivisor;   
10e0: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 62 69 74  /* Number of bit
10f0: 73 20 68 61 6e 64 6c 65 64 20 62 79 20 65 61 63  s handled by eac
1100: 68 20 61 70 53 75 62 5b 5d 20 65 6e 74 72 79 2e  h apSub[] entry.
1110: 20 2a 2f 0a 20 20 20 20 20 20 20 20 20 20 20 20   */.            
1120: 20 20 20 20 20 20 2f 2a 20 53 68 6f 75 6c 64 20        /* Should 
1130: 3e 3d 30 20 66 6f 72 20 61 70 53 75 62 20 65 6c  >=0 for apSub el
1140: 65 6d 65 6e 74 2e 20 2a 2f 0a 20 20 20 20 20 20  ement. */.      
1150: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4d              /* M
1160: 61 78 20 69 44 69 76 69 73 6f 72 20 69 73 20 6d  ax iDivisor is m
1170: 61 78 28 75 33 32 29 20 2f 20 42 49 54 56 45 43  ax(u32) / BITVEC
1180: 5f 4e 50 54 52 20 2b 20 31 2e 20 20 2a 2f 0a 20  _NPTR + 1.  */. 
1190: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
11a0: 20 2f 2a 20 46 6f 72 20 61 20 42 49 54 56 45 43   /* For a BITVEC
11b0: 5f 53 5a 20 6f 66 20 35 31 32 2c 20 74 68 69 73  _SZ of 512, this
11c0: 20 77 6f 75 6c 64 20 62 65 20 33 34 2c 33 35 39   would be 34,359
11d0: 2c 37 33 39 2e 20 2a 2f 0a 20 20 75 6e 69 6f 6e  ,739. */.  union
11e0: 20 7b 0a 20 20 20 20 42 49 54 56 45 43 5f 54 45   {.    BITVEC_TE
11f0: 4c 45 4d 20 61 42 69 74 6d 61 70 5b 42 49 54 56  LEM aBitmap[BITV
1200: 45 43 5f 4e 45 4c 45 4d 5d 3b 20 20 20 20 2f 2a  EC_NELEM];    /*
1210: 20 42 69 74 6d 61 70 20 72 65 70 72 65 73 65 6e   Bitmap represen
1220: 74 61 74 69 6f 6e 20 2a 2f 0a 20 20 20 20 75 33  tation */.    u3
1230: 32 20 61 48 61 73 68 5b 42 49 54 56 45 43 5f 4e  2 aHash[BITVEC_N
1240: 49 4e 54 5d 3b 20 20 20 20 20 20 2f 2a 20 48 61  INT];      /* Ha
1250: 73 68 20 74 61 62 6c 65 20 72 65 70 72 65 73 65  sh table represe
1260: 6e 74 61 74 69 6f 6e 20 2a 2f 0a 20 20 20 20 42  ntation */.    B
1270: 69 74 76 65 63 20 2a 61 70 53 75 62 5b 42 49 54  itvec *apSub[BIT
1280: 56 45 43 5f 4e 50 54 52 5d 3b 20 20 2f 2a 20 52  VEC_NPTR];  /* R
1290: 65 63 75 72 73 69 76 65 20 72 65 70 72 65 73 65  ecursive represe
12a0: 6e 74 61 74 69 6f 6e 20 2a 2f 0a 20 20 7d 20 75  ntation */.  } u
12b0: 3b 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 43 72 65 61  ;.};../*.** Crea
12c0: 74 65 20 61 20 6e 65 77 20 62 69 74 6d 61 70 20  te a new bitmap 
12d0: 6f 62 6a 65 63 74 20 61 62 6c 65 20 74 6f 20 68  object able to h
12e0: 61 6e 64 6c 65 20 62 69 74 73 20 62 65 74 77 65  andle bits betwe
12f0: 65 6e 20 30 20 61 6e 64 20 69 53 69 7a 65 2c 0a  en 0 and iSize,.
1300: 2a 2a 20 69 6e 63 6c 75 73 69 76 65 2e 20 20 52  ** inclusive.  R
1310: 65 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20  eturn a pointer 
1320: 74 6f 20 74 68 65 20 6e 65 77 20 6f 62 6a 65 63  to the new objec
1330: 74 2e 20 20 52 65 74 75 72 6e 20 4e 55 4c 4c 20  t.  Return NULL 
1340: 69 66 20 0a 2a 2a 20 6d 61 6c 6c 6f 63 20 66 61  if .** malloc fa
1350: 69 6c 73 2e 0a 2a 2f 0a 42 69 74 76 65 63 20 2a  ils..*/.Bitvec *
1360: 73 71 6c 69 74 65 33 42 69 74 76 65 63 43 72 65  sqlite3BitvecCre
1370: 61 74 65 28 75 33 32 20 69 53 69 7a 65 29 7b 0a  ate(u32 iSize){.
1380: 20 20 42 69 74 76 65 63 20 2a 70 3b 0a 20 20 61    Bitvec *p;.  a
1390: 73 73 65 72 74 28 20 73 69 7a 65 6f 66 28 2a 70  ssert( sizeof(*p
13a0: 29 3d 3d 42 49 54 56 45 43 5f 53 5a 20 29 3b 0a  )==BITVEC_SZ );.
13b0: 20 20 70 20 3d 20 73 71 6c 69 74 65 33 4d 61 6c    p = sqlite3Mal
13c0: 6c 6f 63 5a 65 72 6f 28 20 73 69 7a 65 6f 66 28  locZero( sizeof(
13d0: 2a 70 29 20 29 3b 0a 20 20 69 66 28 20 70 20 29  *p) );.  if( p )
13e0: 7b 0a 20 20 20 20 70 2d 3e 69 53 69 7a 65 20 3d  {.    p->iSize =
13f0: 20 69 53 69 7a 65 3b 0a 20 20 7d 0a 20 20 72 65   iSize;.  }.  re
1400: 74 75 72 6e 20 70 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  turn p;.}../*.**
1410: 20 43 68 65 63 6b 20 74 6f 20 73 65 65 20 69 66   Check to see if
1420: 20 74 68 65 20 69 2d 74 68 20 62 69 74 20 69 73   the i-th bit is
1430: 20 73 65 74 2e 20 20 52 65 74 75 72 6e 20 74 72   set.  Return tr
1440: 75 65 20 6f 72 20 66 61 6c 73 65 2e 0a 2a 2a 20  ue or false..** 
1450: 49 66 20 70 20 69 73 20 4e 55 4c 4c 20 28 69 66  If p is NULL (if
1460: 20 74 68 65 20 62 69 74 6d 61 70 20 68 61 73 20   the bitmap has 
1470: 6e 6f 74 20 62 65 65 6e 20 63 72 65 61 74 65 64  not been created
1480: 29 20 6f 72 20 69 66 0a 2a 2a 20 69 20 69 73 20  ) or if.** i is 
1490: 6f 75 74 20 6f 66 20 72 61 6e 67 65 2c 20 74 68  out of range, th
14a0: 65 6e 20 72 65 74 75 72 6e 20 66 61 6c 73 65 2e  en return false.
14b0: 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 42  .*/.int sqlite3B
14c0: 69 74 76 65 63 54 65 73 74 28 42 69 74 76 65 63  itvecTest(Bitvec
14d0: 20 2a 70 2c 20 75 33 32 20 69 29 7b 0a 20 20 69   *p, u32 i){.  i
14e0: 66 28 20 70 3d 3d 30 20 29 20 72 65 74 75 72 6e  f( p==0 ) return
14f0: 20 30 3b 0a 20 20 69 66 28 20 69 3e 70 2d 3e 69   0;.  if( i>p->i
1500: 53 69 7a 65 20 7c 7c 20 69 3d 3d 30 20 29 20 72  Size || i==0 ) r
1510: 65 74 75 72 6e 20 30 3b 0a 20 20 69 2d 2d 3b 0a  eturn 0;.  i--;.
1520: 20 20 77 68 69 6c 65 28 20 70 2d 3e 69 44 69 76    while( p->iDiv
1530: 69 73 6f 72 20 29 7b 0a 20 20 20 20 75 33 32 20  isor ){.    u32 
1540: 62 69 6e 20 3d 20 69 2f 70 2d 3e 69 44 69 76 69  bin = i/p->iDivi
1550: 73 6f 72 3b 0a 20 20 20 20 69 20 3d 20 69 25 70  sor;.    i = i%p
1560: 2d 3e 69 44 69 76 69 73 6f 72 3b 0a 20 20 20 20  ->iDivisor;.    
1570: 70 20 3d 20 70 2d 3e 75 2e 61 70 53 75 62 5b 62  p = p->u.apSub[b
1580: 69 6e 5d 3b 0a 20 20 20 20 69 66 20 28 21 70 29  in];.    if (!p)
1590: 20 7b 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20   {.      return 
15a0: 30 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 69  0;.    }.  }.  i
15b0: 66 28 20 70 2d 3e 69 53 69 7a 65 3c 3d 42 49 54  f( p->iSize<=BIT
15c0: 56 45 43 5f 4e 42 49 54 20 29 7b 0a 20 20 20 20  VEC_NBIT ){.    
15d0: 72 65 74 75 72 6e 20 28 70 2d 3e 75 2e 61 42 69  return (p->u.aBi
15e0: 74 6d 61 70 5b 69 2f 42 49 54 56 45 43 5f 53 5a  tmap[i/BITVEC_SZ
15f0: 45 4c 45 4d 5d 20 26 20 28 31 3c 3c 28 69 26 28  ELEM] & (1<<(i&(
1600: 42 49 54 56 45 43 5f 53 5a 45 4c 45 4d 2d 31 29  BITVEC_SZELEM-1)
1610: 29 29 29 21 3d 30 3b 0a 20 20 7d 20 65 6c 73 65  )))!=0;.  } else
1620: 7b 0a 20 20 20 20 75 33 32 20 68 20 3d 20 42 49  {.    u32 h = BI
1630: 54 56 45 43 5f 48 41 53 48 28 69 2b 2b 29 3b 0a  TVEC_HASH(i++);.
1640: 20 20 20 20 77 68 69 6c 65 28 20 70 2d 3e 75 2e      while( p->u.
1650: 61 48 61 73 68 5b 68 5d 20 29 7b 0a 20 20 20 20  aHash[h] ){.    
1660: 20 20 69 66 28 20 70 2d 3e 75 2e 61 48 61 73 68    if( p->u.aHash
1670: 5b 68 5d 3d 3d 69 20 29 20 72 65 74 75 72 6e 20  [h]==i ) return 
1680: 31 3b 0a 20 20 20 20 20 20 68 20 3d 20 28 68 2b  1;.      h = (h+
1690: 31 29 20 25 20 42 49 54 56 45 43 5f 4e 49 4e 54  1) % BITVEC_NINT
16a0: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72 65 74 75  ;.    }.    retu
16b0: 72 6e 20 30 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 0a  rn 0;.  }.}../*.
16c0: 2a 2a 20 53 65 74 20 74 68 65 20 69 2d 74 68 20  ** Set the i-th 
16d0: 62 69 74 2e 20 20 52 65 74 75 72 6e 20 30 20 6f  bit.  Return 0 o
16e0: 6e 20 73 75 63 63 65 73 73 20 61 6e 64 20 61 6e  n success and an
16f0: 20 65 72 72 6f 72 20 63 6f 64 65 20 69 66 0a 2a   error code if.*
1700: 2a 20 61 6e 79 74 68 69 6e 67 20 67 6f 65 73 20  * anything goes 
1710: 77 72 6f 6e 67 2e 0a 2a 2a 0a 2a 2a 20 54 68 69  wrong..**.** Thi
1720: 73 20 72 6f 75 74 69 6e 65 20 6d 69 67 68 74 20  s routine might 
1730: 63 61 75 73 65 20 73 75 62 2d 62 69 74 6d 61 70  cause sub-bitmap
1740: 73 20 74 6f 20 62 65 20 61 6c 6c 6f 63 61 74 65  s to be allocate
1750: 64 2e 20 20 46 61 69 6c 69 6e 67 0a 2a 2a 20 74  d.  Failing.** t
1760: 6f 20 67 65 74 20 74 68 65 20 6d 65 6d 6f 72 79  o get the memory
1770: 20 6e 65 65 64 65 64 20 74 6f 20 68 6f 6c 64 20   needed to hold 
1780: 74 68 65 20 73 75 62 2d 62 69 74 6d 61 70 20 69  the sub-bitmap i
1790: 73 20 74 68 65 20 6f 6e 6c 79 0a 2a 2a 20 74 68  s the only.** th
17a0: 61 74 20 63 61 6e 20 67 6f 20 77 72 6f 6e 67 20  at can go wrong 
17b0: 77 69 74 68 20 61 6e 20 69 6e 73 65 72 74 2c 20  with an insert, 
17c0: 61 73 73 75 6d 69 6e 67 20 70 20 61 6e 64 20 69  assuming p and i
17d0: 20 61 72 65 20 76 61 6c 69 64 2e 0a 2a 2a 0a 2a   are valid..**.*
17e0: 2a 20 54 68 65 20 63 61 6c 6c 69 6e 67 20 66 75  * The calling fu
17f0: 6e 63 74 69 6f 6e 20 6d 75 73 74 20 65 6e 73 75  nction must ensu
1800: 72 65 20 74 68 61 74 20 70 20 69 73 20 61 20 76  re that p is a v
1810: 61 6c 69 64 20 42 69 74 76 65 63 20 6f 62 6a 65  alid Bitvec obje
1820: 63 74 0a 2a 2a 20 61 6e 64 20 74 68 61 74 20 74  ct.** and that t
1830: 68 65 20 76 61 6c 75 65 20 66 6f 72 20 22 69 22  he value for "i"
1840: 20 69 73 20 77 69 74 68 69 6e 20 72 61 6e 67 65   is within range
1850: 20 6f 66 20 74 68 65 20 42 69 74 76 65 63 20 6f   of the Bitvec o
1860: 62 6a 65 63 74 2e 0a 2a 2a 20 4f 74 68 65 72 77  bject..** Otherw
1870: 69 73 65 20 74 68 65 20 62 65 68 61 76 69 6f 72  ise the behavior
1880: 20 69 73 20 75 6e 64 65 66 69 6e 65 64 2e 0a 2a   is undefined..*
1890: 2f 0a 69 6e 74 20 73 71 6c 69 74 65 33 42 69 74  /.int sqlite3Bit
18a0: 76 65 63 53 65 74 28 42 69 74 76 65 63 20 2a 70  vecSet(Bitvec *p
18b0: 2c 20 75 33 32 20 69 29 7b 0a 20 20 75 33 32 20  , u32 i){.  u32 
18c0: 68 3b 0a 20 20 69 66 28 20 70 3d 3d 30 20 29 20  h;.  if( p==0 ) 
18d0: 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b  return SQLITE_OK
18e0: 3b 0a 20 20 61 73 73 65 72 74 28 20 69 3e 30 20  ;.  assert( i>0 
18f0: 29 3b 0a 20 20 61 73 73 65 72 74 28 20 69 3c 3d  );.  assert( i<=
1900: 70 2d 3e 69 53 69 7a 65 20 29 3b 0a 20 20 69 2d  p->iSize );.  i-
1910: 2d 3b 0a 20 20 77 68 69 6c 65 28 28 70 2d 3e 69  -;.  while((p->i
1920: 53 69 7a 65 20 3e 20 42 49 54 56 45 43 5f 4e 42  Size > BITVEC_NB
1930: 49 54 29 20 26 26 20 70 2d 3e 69 44 69 76 69 73  IT) && p->iDivis
1940: 6f 72 29 20 7b 0a 20 20 20 20 75 33 32 20 62 69  or) {.    u32 bi
1950: 6e 20 3d 20 69 2f 70 2d 3e 69 44 69 76 69 73 6f  n = i/p->iDiviso
1960: 72 3b 0a 20 20 20 20 69 20 3d 20 69 25 70 2d 3e  r;.    i = i%p->
1970: 69 44 69 76 69 73 6f 72 3b 0a 20 20 20 20 69 66  iDivisor;.    if
1980: 28 20 70 2d 3e 75 2e 61 70 53 75 62 5b 62 69 6e  ( p->u.apSub[bin
1990: 5d 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 70 2d  ]==0 ){.      p-
19a0: 3e 75 2e 61 70 53 75 62 5b 62 69 6e 5d 20 3d 20  >u.apSub[bin] = 
19b0: 73 71 6c 69 74 65 33 42 69 74 76 65 63 43 72 65  sqlite3BitvecCre
19c0: 61 74 65 28 20 70 2d 3e 69 44 69 76 69 73 6f 72  ate( p->iDivisor
19d0: 20 29 3b 0a 20 20 20 20 20 20 69 66 28 20 70 2d   );.      if( p-
19e0: 3e 75 2e 61 70 53 75 62 5b 62 69 6e 5d 3d 3d 30  >u.apSub[bin]==0
19f0: 20 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45   ) return SQLITE
1a00: 5f 4e 4f 4d 45 4d 3b 0a 20 20 20 20 7d 0a 20 20  _NOMEM;.    }.  
1a10: 20 20 70 20 3d 20 70 2d 3e 75 2e 61 70 53 75 62    p = p->u.apSub
1a20: 5b 62 69 6e 5d 3b 0a 20 20 7d 0a 20 20 69 66 28  [bin];.  }.  if(
1a30: 20 70 2d 3e 69 53 69 7a 65 3c 3d 42 49 54 56 45   p->iSize<=BITVE
1a40: 43 5f 4e 42 49 54 20 29 7b 0a 20 20 20 20 70 2d  C_NBIT ){.    p-
1a50: 3e 75 2e 61 42 69 74 6d 61 70 5b 69 2f 42 49 54  >u.aBitmap[i/BIT
1a60: 56 45 43 5f 53 5a 45 4c 45 4d 5d 20 7c 3d 20 31  VEC_SZELEM] |= 1
1a70: 20 3c 3c 20 28 69 26 28 42 49 54 56 45 43 5f 53   << (i&(BITVEC_S
1a80: 5a 45 4c 45 4d 2d 31 29 29 3b 0a 20 20 20 20 72  ZELEM-1));.    r
1a90: 65 74 75 72 6e 20 53 51 4c 49 54 45 5f 4f 4b 3b  eturn SQLITE_OK;
1aa0: 0a 20 20 7d 0a 20 20 68 20 3d 20 42 49 54 56 45  .  }.  h = BITVE
1ab0: 43 5f 48 41 53 48 28 69 2b 2b 29 3b 0a 20 20 2f  C_HASH(i++);.  /
1ac0: 2a 20 69 66 20 74 68 65 72 65 20 77 61 73 6e 27  * if there wasn'
1ad0: 74 20 61 20 68 61 73 68 20 63 6f 6c 6c 69 73 69  t a hash collisi
1ae0: 6f 6e 2c 20 61 6e 64 20 74 68 69 73 20 64 6f 65  on, and this doe
1af0: 73 6e 27 74 20 2a 2f 0a 20 20 2f 2a 20 63 6f 6d  sn't */.  /* com
1b00: 70 6c 65 74 65 6c 79 20 66 69 6c 6c 20 74 68 65  pletely fill the
1b10: 20 68 61 73 68 2c 20 74 68 65 6e 20 6a 75 73 74   hash, then just
1b20: 20 61 64 64 20 69 74 20 77 69 74 68 6f 75 74 20   add it without 
1b30: 2a 2f 0a 20 20 2f 2a 20 77 6f 72 72 69 6e 67 20  */.  /* worring 
1b40: 61 62 6f 75 74 20 73 75 62 2d 64 69 76 69 64 69  about sub-dividi
1b50: 6e 67 20 61 6e 64 20 72 65 2d 68 61 73 68 69 6e  ng and re-hashin
1b60: 67 2e 20 2a 2f 0a 20 20 69 66 28 20 21 70 2d 3e  g. */.  if( !p->
1b70: 75 2e 61 48 61 73 68 5b 68 5d 20 29 7b 0a 20 20  u.aHash[h] ){.  
1b80: 20 20 69 66 20 28 70 2d 3e 6e 53 65 74 3c 28 42    if (p->nSet<(B
1b90: 49 54 56 45 43 5f 4e 49 4e 54 2d 31 29 29 20 7b  ITVEC_NINT-1)) {
1ba0: 0a 20 20 20 20 20 20 67 6f 74 6f 20 62 69 74 76  .      goto bitv
1bb0: 65 63 5f 73 65 74 5f 65 6e 64 3b 0a 20 20 20 20  ec_set_end;.    
1bc0: 7d 20 65 6c 73 65 20 7b 0a 20 20 20 20 20 20 67  } else {.      g
1bd0: 6f 74 6f 20 62 69 74 76 65 63 5f 73 65 74 5f 72  oto bitvec_set_r
1be0: 65 68 61 73 68 3b 0a 20 20 20 20 7d 0a 20 20 7d  ehash;.    }.  }
1bf0: 0a 20 20 2f 2a 20 74 68 65 72 65 20 77 61 73 20  .  /* there was 
1c00: 61 20 63 6f 6c 6c 69 73 69 6f 6e 2c 20 63 68 65  a collision, che
1c10: 63 6b 20 74 6f 20 73 65 65 20 69 66 20 69 74 27  ck to see if it'
1c20: 73 20 61 6c 72 65 61 64 79 20 2a 2f 0a 20 20 2f  s already */.  /
1c30: 2a 20 69 6e 20 68 61 73 68 2c 20 69 66 20 6e 6f  * in hash, if no
1c40: 74 2c 20 74 72 79 20 74 6f 20 66 69 6e 64 20 61  t, try to find a
1c50: 20 73 70 6f 74 20 66 6f 72 20 69 74 20 2a 2f 0a   spot for it */.
1c60: 20 20 64 6f 20 7b 0a 20 20 20 20 69 66 28 20 70    do {.    if( p
1c70: 2d 3e 75 2e 61 48 61 73 68 5b 68 5d 3d 3d 69 20  ->u.aHash[h]==i 
1c80: 29 20 72 65 74 75 72 6e 20 53 51 4c 49 54 45 5f  ) return SQLITE_
1c90: 4f 4b 3b 0a 20 20 20 20 68 2b 2b 3b 0a 20 20 20  OK;.    h++;.   
1ca0: 20 69 66 28 20 68 3e 3d 42 49 54 56 45 43 5f 4e   if( h>=BITVEC_N
1cb0: 49 4e 54 20 29 20 68 20 3d 20 30 3b 0a 20 20 7d  INT ) h = 0;.  }
1cc0: 20 77 68 69 6c 65 28 20 70 2d 3e 75 2e 61 48 61   while( p->u.aHa
1cd0: 73 68 5b 68 5d 20 29 3b 0a 20 20 2f 2a 20 77 65  sh[h] );.  /* we
1ce0: 20 64 69 64 6e 27 74 20 66 69 6e 64 20 69 74 20   didn't find it 
1cf0: 69 6e 20 74 68 65 20 68 61 73 68 2e 20 20 68 20  in the hash.  h 
1d00: 70 6f 69 6e 74 73 20 74 6f 20 74 68 65 20 66 69  points to the fi
1d10: 72 73 74 20 2a 2f 0a 20 20 2f 2a 20 61 76 61 69  rst */.  /* avai
1d20: 6c 61 62 6c 65 20 66 72 65 65 20 73 70 6f 74 2e  lable free spot.
1d30: 20 63 68 65 63 6b 20 74 6f 20 73 65 65 20 69 66   check to see if
1d40: 20 74 68 69 73 20 69 73 20 67 6f 69 6e 67 20 74   this is going t
1d50: 6f 20 2a 2f 0a 20 20 2f 2a 20 6d 61 6b 65 20 6f  o */.  /* make o
1d60: 75 72 20 68 61 73 68 20 74 6f 6f 20 22 66 75 6c  ur hash too "ful
1d70: 6c 22 2e 20 20 2a 2f 0a 62 69 74 76 65 63 5f 73  l".  */.bitvec_s
1d80: 65 74 5f 72 65 68 61 73 68 3a 0a 20 20 69 66 28  et_rehash:.  if(
1d90: 20 70 2d 3e 6e 53 65 74 3e 3d 42 49 54 56 45 43   p->nSet>=BITVEC
1da0: 5f 4d 58 48 41 53 48 20 29 7b 0a 20 20 20 20 75  _MXHASH ){.    u
1db0: 6e 73 69 67 6e 65 64 20 69 6e 74 20 6a 3b 0a 20  nsigned int j;. 
1dc0: 20 20 20 69 6e 74 20 72 63 3b 0a 20 20 20 20 75     int rc;.    u
1dd0: 33 32 20 2a 61 69 56 61 6c 75 65 73 20 3d 20 73  32 *aiValues = s
1de0: 71 6c 69 74 65 33 53 74 61 63 6b 41 6c 6c 6f 63  qlite3StackAlloc
1df0: 52 61 77 28 30 2c 20 73 69 7a 65 6f 66 28 70 2d  Raw(0, sizeof(p-
1e00: 3e 75 2e 61 48 61 73 68 29 29 3b 0a 20 20 20 20  >u.aHash));.    
1e10: 69 66 28 20 61 69 56 61 6c 75 65 73 3d 3d 30 20  if( aiValues==0 
1e20: 29 7b 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20  ){.      return 
1e30: 53 51 4c 49 54 45 5f 4e 4f 4d 45 4d 3b 0a 20 20  SQLITE_NOMEM;.  
1e40: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 6d    }else{.      m
1e50: 65 6d 63 70 79 28 61 69 56 61 6c 75 65 73 2c 20  emcpy(aiValues, 
1e60: 70 2d 3e 75 2e 61 48 61 73 68 2c 20 73 69 7a 65  p->u.aHash, size
1e70: 6f 66 28 70 2d 3e 75 2e 61 48 61 73 68 29 29 3b  of(p->u.aHash));
1e80: 0a 20 20 20 20 20 20 6d 65 6d 73 65 74 28 70 2d  .      memset(p-
1e90: 3e 75 2e 61 70 53 75 62 2c 20 30 2c 20 73 69 7a  >u.apSub, 0, siz
1ea0: 65 6f 66 28 70 2d 3e 75 2e 61 70 53 75 62 29 29  eof(p->u.apSub))
1eb0: 3b 0a 20 20 20 20 20 20 70 2d 3e 69 44 69 76 69  ;.      p->iDivi
1ec0: 73 6f 72 20 3d 20 28 70 2d 3e 69 53 69 7a 65 20  sor = (p->iSize 
1ed0: 2b 20 42 49 54 56 45 43 5f 4e 50 54 52 20 2d 20  + BITVEC_NPTR - 
1ee0: 31 29 2f 42 49 54 56 45 43 5f 4e 50 54 52 3b 0a  1)/BITVEC_NPTR;.
1ef0: 20 20 20 20 20 20 72 63 20 3d 20 73 71 6c 69 74        rc = sqlit
1f00: 65 33 42 69 74 76 65 63 53 65 74 28 70 2c 20 69  e3BitvecSet(p, i
1f10: 29 3b 0a 20 20 20 20 20 20 66 6f 72 28 6a 3d 30  );.      for(j=0
1f20: 3b 20 6a 3c 42 49 54 56 45 43 5f 4e 49 4e 54 3b  ; j<BITVEC_NINT;
1f30: 20 6a 2b 2b 29 7b 0a 20 20 20 20 20 20 20 20 69   j++){.        i
1f40: 66 28 20 61 69 56 61 6c 75 65 73 5b 6a 5d 20 29  f( aiValues[j] )
1f50: 20 72 63 20 7c 3d 20 73 71 6c 69 74 65 33 42 69   rc |= sqlite3Bi
1f60: 74 76 65 63 53 65 74 28 70 2c 20 61 69 56 61 6c  tvecSet(p, aiVal
1f70: 75 65 73 5b 6a 5d 29 3b 0a 20 20 20 20 20 20 7d  ues[j]);.      }
1f80: 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33 53 74  .      sqlite3St
1f90: 61 63 6b 46 72 65 65 28 30 2c 20 61 69 56 61 6c  ackFree(0, aiVal
1fa0: 75 65 73 29 3b 0a 20 20 20 20 20 20 72 65 74 75  ues);.      retu
1fb0: 72 6e 20 72 63 3b 0a 20 20 20 20 7d 0a 20 20 7d  rn rc;.    }.  }
1fc0: 0a 62 69 74 76 65 63 5f 73 65 74 5f 65 6e 64 3a  .bitvec_set_end:
1fd0: 0a 20 20 70 2d 3e 6e 53 65 74 2b 2b 3b 0a 20 20  .  p->nSet++;.  
1fe0: 70 2d 3e 75 2e 61 48 61 73 68 5b 68 5d 20 3d 20  p->u.aHash[h] = 
1ff0: 69 3b 0a 20 20 72 65 74 75 72 6e 20 53 51 4c 49  i;.  return SQLI
2000: 54 45 5f 4f 4b 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20  TE_OK;.}../*.** 
2010: 43 6c 65 61 72 20 74 68 65 20 69 2d 74 68 20 62  Clear the i-th b
2020: 69 74 2e 0a 2a 2a 0a 2a 2a 20 70 42 75 66 20 6d  it..**.** pBuf m
2030: 75 73 74 20 62 65 20 61 20 70 6f 69 6e 74 65 72  ust be a pointer
2040: 20 74 6f 20 61 74 20 6c 65 61 73 74 20 42 49 54   to at least BIT
2050: 56 45 43 5f 53 5a 20 62 79 74 65 73 20 6f 66 20  VEC_SZ bytes of 
2060: 74 65 6d 70 6f 72 61 72 79 20 73 74 6f 72 61 67  temporary storag
2070: 65 0a 2a 2a 20 74 68 61 74 20 42 69 74 76 65 63  e.** that Bitvec
2080: 43 6c 65 61 72 20 63 61 6e 20 75 73 65 20 74 6f  Clear can use to
2090: 20 72 65 62 75 69 6c 74 20 69 74 73 20 68 61 73   rebuilt its has
20a0: 68 20 74 61 62 6c 65 2e 0a 2a 2f 0a 76 6f 69 64  h table..*/.void
20b0: 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 43 6c   sqlite3BitvecCl
20c0: 65 61 72 28 42 69 74 76 65 63 20 2a 70 2c 20 75  ear(Bitvec *p, u
20d0: 33 32 20 69 2c 20 76 6f 69 64 20 2a 70 42 75 66  32 i, void *pBuf
20e0: 29 7b 0a 20 20 69 66 28 20 70 3d 3d 30 20 29 20  ){.  if( p==0 ) 
20f0: 72 65 74 75 72 6e 3b 0a 20 20 61 73 73 65 72 74  return;.  assert
2100: 28 20 69 3e 30 20 29 3b 0a 20 20 69 2d 2d 3b 0a  ( i>0 );.  i--;.
2110: 20 20 77 68 69 6c 65 28 20 70 2d 3e 69 44 69 76    while( p->iDiv
2120: 69 73 6f 72 20 29 7b 0a 20 20 20 20 75 33 32 20  isor ){.    u32 
2130: 62 69 6e 20 3d 20 69 2f 70 2d 3e 69 44 69 76 69  bin = i/p->iDivi
2140: 73 6f 72 3b 0a 20 20 20 20 69 20 3d 20 69 25 70  sor;.    i = i%p
2150: 2d 3e 69 44 69 76 69 73 6f 72 3b 0a 20 20 20 20  ->iDivisor;.    
2160: 70 20 3d 20 70 2d 3e 75 2e 61 70 53 75 62 5b 62  p = p->u.apSub[b
2170: 69 6e 5d 3b 0a 20 20 20 20 69 66 20 28 21 70 29  in];.    if (!p)
2180: 20 7b 0a 20 20 20 20 20 20 72 65 74 75 72 6e 3b   {.      return;
2190: 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 69 66 28  .    }.  }.  if(
21a0: 20 70 2d 3e 69 53 69 7a 65 3c 3d 42 49 54 56 45   p->iSize<=BITVE
21b0: 43 5f 4e 42 49 54 20 29 7b 0a 20 20 20 20 70 2d  C_NBIT ){.    p-
21c0: 3e 75 2e 61 42 69 74 6d 61 70 5b 69 2f 42 49 54  >u.aBitmap[i/BIT
21d0: 56 45 43 5f 53 5a 45 4c 45 4d 5d 20 26 3d 20 7e  VEC_SZELEM] &= ~
21e0: 28 31 20 3c 3c 20 28 69 26 28 42 49 54 56 45 43  (1 << (i&(BITVEC
21f0: 5f 53 5a 45 4c 45 4d 2d 31 29 29 29 3b 0a 20 20  _SZELEM-1)));.  
2200: 7d 65 6c 73 65 7b 0a 20 20 20 20 75 6e 73 69 67  }else{.    unsig
2210: 6e 65 64 20 69 6e 74 20 6a 3b 0a 20 20 20 20 75  ned int j;.    u
2220: 33 32 20 2a 61 69 56 61 6c 75 65 73 20 3d 20 70  32 *aiValues = p
2230: 42 75 66 3b 0a 20 20 20 20 6d 65 6d 63 70 79 28  Buf;.    memcpy(
2240: 61 69 56 61 6c 75 65 73 2c 20 70 2d 3e 75 2e 61  aiValues, p->u.a
2250: 48 61 73 68 2c 20 73 69 7a 65 6f 66 28 70 2d 3e  Hash, sizeof(p->
2260: 75 2e 61 48 61 73 68 29 29 3b 0a 20 20 20 20 6d  u.aHash));.    m
2270: 65 6d 73 65 74 28 70 2d 3e 75 2e 61 48 61 73 68  emset(p->u.aHash
2280: 2c 20 30 2c 20 73 69 7a 65 6f 66 28 70 2d 3e 75  , 0, sizeof(p->u
2290: 2e 61 48 61 73 68 29 29 3b 0a 20 20 20 20 70 2d  .aHash));.    p-
22a0: 3e 6e 53 65 74 20 3d 20 30 3b 0a 20 20 20 20 66  >nSet = 0;.    f
22b0: 6f 72 28 6a 3d 30 3b 20 6a 3c 42 49 54 56 45 43  or(j=0; j<BITVEC
22c0: 5f 4e 49 4e 54 3b 20 6a 2b 2b 29 7b 0a 20 20 20  _NINT; j++){.   
22d0: 20 20 20 69 66 28 20 61 69 56 61 6c 75 65 73 5b     if( aiValues[
22e0: 6a 5d 20 26 26 20 61 69 56 61 6c 75 65 73 5b 6a  j] && aiValues[j
22f0: 5d 21 3d 28 69 2b 31 29 20 29 7b 0a 20 20 20 20  ]!=(i+1) ){.    
2300: 20 20 20 20 75 33 32 20 68 20 3d 20 42 49 54 56      u32 h = BITV
2310: 45 43 5f 48 41 53 48 28 61 69 56 61 6c 75 65 73  EC_HASH(aiValues
2320: 5b 6a 5d 2d 31 29 3b 0a 20 20 20 20 20 20 20 20  [j]-1);.        
2330: 70 2d 3e 6e 53 65 74 2b 2b 3b 0a 20 20 20 20 20  p->nSet++;.     
2340: 20 20 20 77 68 69 6c 65 28 20 70 2d 3e 75 2e 61     while( p->u.a
2350: 48 61 73 68 5b 68 5d 20 29 7b 0a 20 20 20 20 20  Hash[h] ){.     
2360: 20 20 20 20 20 68 2b 2b 3b 0a 20 20 20 20 20 20       h++;.      
2370: 20 20 20 20 69 66 28 20 68 3e 3d 42 49 54 56 45      if( h>=BITVE
2380: 43 5f 4e 49 4e 54 20 29 20 68 20 3d 20 30 3b 0a  C_NINT ) h = 0;.
2390: 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20          }.      
23a0: 20 20 70 2d 3e 75 2e 61 48 61 73 68 5b 68 5d 20    p->u.aHash[h] 
23b0: 3d 20 61 69 56 61 6c 75 65 73 5b 6a 5d 3b 0a 20  = aiValues[j];. 
23c0: 20 20 20 20 20 7d 0a 20 20 20 20 7d 0a 20 20 7d       }.    }.  }
23d0: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 44 65 73 74 72 6f  .}../*.** Destro
23e0: 79 20 61 20 62 69 74 6d 61 70 20 6f 62 6a 65 63  y a bitmap objec
23f0: 74 2e 20 20 52 65 63 6c 61 69 6d 20 61 6c 6c 20  t.  Reclaim all 
2400: 6d 65 6d 6f 72 79 20 75 73 65 64 2e 0a 2a 2f 0a  memory used..*/.
2410: 76 6f 69 64 20 73 71 6c 69 74 65 33 42 69 74 76  void sqlite3Bitv
2420: 65 63 44 65 73 74 72 6f 79 28 42 69 74 76 65 63  ecDestroy(Bitvec
2430: 20 2a 70 29 7b 0a 20 20 69 66 28 20 70 3d 3d 30   *p){.  if( p==0
2440: 20 29 20 72 65 74 75 72 6e 3b 0a 20 20 69 66 28   ) return;.  if(
2450: 20 70 2d 3e 69 44 69 76 69 73 6f 72 20 29 7b 0a   p->iDivisor ){.
2460: 20 20 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74      unsigned int
2470: 20 69 3b 0a 20 20 20 20 66 6f 72 28 69 3d 30 3b   i;.    for(i=0;
2480: 20 69 3c 42 49 54 56 45 43 5f 4e 50 54 52 3b 20   i<BITVEC_NPTR; 
2490: 69 2b 2b 29 7b 0a 20 20 20 20 20 20 73 71 6c 69  i++){.      sqli
24a0: 74 65 33 42 69 74 76 65 63 44 65 73 74 72 6f 79  te3BitvecDestroy
24b0: 28 70 2d 3e 75 2e 61 70 53 75 62 5b 69 5d 29 3b  (p->u.apSub[i]);
24c0: 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 73 71 6c  .    }.  }.  sql
24d0: 69 74 65 33 5f 66 72 65 65 28 70 29 3b 0a 7d 0a  ite3_free(p);.}.
24e0: 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e 20 74 68  ./*.** Return th
24f0: 65 20 76 61 6c 75 65 20 6f 66 20 74 68 65 20 69  e value of the i
2500: 53 69 7a 65 20 70 61 72 61 6d 65 74 65 72 20 73  Size parameter s
2510: 70 65 63 69 66 69 65 64 20 77 68 65 6e 20 42 69  pecified when Bi
2520: 74 76 65 63 20 2a 70 0a 2a 2a 20 77 61 73 20 63  tvec *p.** was c
2530: 72 65 61 74 65 64 2e 0a 2a 2f 0a 75 33 32 20 73  reated..*/.u32 s
2540: 71 6c 69 74 65 33 42 69 74 76 65 63 53 69 7a 65  qlite3BitvecSize
2550: 28 42 69 74 76 65 63 20 2a 70 29 7b 0a 20 20 72  (Bitvec *p){.  r
2560: 65 74 75 72 6e 20 70 2d 3e 69 53 69 7a 65 3b 0a  eturn p->iSize;.
2570: 7d 0a 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54  }..#ifndef SQLIT
2580: 45 5f 4f 4d 49 54 5f 42 55 49 4c 54 49 4e 5f 54  E_OMIT_BUILTIN_T
2590: 45 53 54 0a 2f 2a 0a 2a 2a 20 4c 65 74 20 56 5b  EST./*.** Let V[
25a0: 5d 20 62 65 20 61 6e 20 61 72 72 61 79 20 6f 66  ] be an array of
25b0: 20 75 6e 73 69 67 6e 65 64 20 63 68 61 72 61 63   unsigned charac
25c0: 74 65 72 73 20 73 75 66 66 69 63 69 65 6e 74 20  ters sufficient 
25d0: 74 6f 20 68 6f 6c 64 0a 2a 2a 20 75 70 20 74 6f  to hold.** up to
25e0: 20 4e 20 62 69 74 73 2e 20 20 4c 65 74 20 49 20   N bits.  Let I 
25f0: 62 65 20 61 6e 20 69 6e 74 65 67 65 72 20 62 65  be an integer be
2600: 74 77 65 65 6e 20 30 20 61 6e 64 20 4e 2e 20 20  tween 0 and N.  
2610: 30 3c 3d 49 3c 4e 2e 0a 2a 2a 20 54 68 65 6e 20  0<=I<N..** Then 
2620: 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 6d 61  the following ma
2630: 63 72 6f 73 20 63 61 6e 20 62 65 20 75 73 65 64  cros can be used
2640: 20 74 6f 20 73 65 74 2c 20 63 6c 65 61 72 2c 20   to set, clear, 
2650: 6f 72 20 74 65 73 74 0a 2a 2a 20 69 6e 64 69 76  or test.** indiv
2660: 69 64 75 61 6c 20 62 69 74 73 20 77 69 74 68 69  idual bits withi
2670: 6e 20 56 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20  n V..*/.#define 
2680: 53 45 54 42 49 54 28 56 2c 49 29 20 20 20 20 20  SETBIT(V,I)     
2690: 20 56 5b 49 3e 3e 33 5d 20 7c 3d 20 28 31 3c 3c   V[I>>3] |= (1<<
26a0: 28 49 26 37 29 29 0a 23 64 65 66 69 6e 65 20 43  (I&7)).#define C
26b0: 4c 45 41 52 42 49 54 28 56 2c 49 29 20 20 20 20  LEARBIT(V,I)    
26c0: 56 5b 49 3e 3e 33 5d 20 26 3d 20 7e 28 31 3c 3c  V[I>>3] &= ~(1<<
26d0: 28 49 26 37 29 29 0a 23 64 65 66 69 6e 65 20 54  (I&7)).#define T
26e0: 45 53 54 42 49 54 28 56 2c 49 29 20 20 20 20 20  ESTBIT(V,I)     
26f0: 28 56 5b 49 3e 3e 33 5d 26 28 31 3c 3c 28 49 26  (V[I>>3]&(1<<(I&
2700: 37 29 29 29 21 3d 30 0a 0a 2f 2a 0a 2a 2a 20 54  7)))!=0../*.** T
2710: 68 69 73 20 72 6f 75 74 69 6e 65 20 72 75 6e 73  his routine runs
2720: 20 61 6e 20 65 78 74 65 6e 73 69 76 65 20 74 65   an extensive te
2730: 73 74 20 6f 66 20 74 68 65 20 42 69 74 76 65 63  st of the Bitvec
2740: 20 63 6f 64 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65   code..**.** The
2750: 20 69 6e 70 75 74 20 69 73 20 61 6e 20 61 72 72   input is an arr
2760: 61 79 20 6f 66 20 69 6e 74 65 67 65 72 73 20 74  ay of integers t
2770: 68 61 74 20 61 63 74 73 20 61 73 20 61 20 70 72  hat acts as a pr
2780: 6f 67 72 61 6d 0a 2a 2a 20 74 6f 20 74 65 73 74  ogram.** to test
2790: 20 74 68 65 20 42 69 74 76 65 63 2e 20 20 54 68   the Bitvec.  Th
27a0: 65 20 69 6e 74 65 67 65 72 73 20 61 72 65 20 6f  e integers are o
27b0: 70 63 6f 64 65 73 20 66 6f 6c 6c 6f 77 65 64 0a  pcodes followed.
27c0: 2a 2a 20 62 79 20 30 2c 20 31 2c 20 6f 72 20 33  ** by 0, 1, or 3
27d0: 20 6f 70 65 72 61 6e 64 73 2c 20 64 65 70 65 6e   operands, depen
27e0: 64 69 6e 67 20 6f 6e 20 74 68 65 20 6f 70 63 6f  ding on the opco
27f0: 64 65 2e 20 20 41 6e 6f 74 68 65 72 0a 2a 2a 20  de.  Another.** 
2800: 6f 70 63 6f 64 65 20 66 6f 6c 6c 6f 77 73 20 69  opcode follows i
2810: 6d 6d 65 64 69 61 74 65 6c 79 20 61 66 74 65 72  mmediately after
2820: 20 74 68 65 20 6c 61 73 74 20 6f 70 65 72 61 6e   the last operan
2830: 64 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 72 65 20 61  d..**.** There a
2840: 72 65 20 36 20 6f 70 63 6f 64 65 73 20 6e 75 6d  re 6 opcodes num
2850: 62 65 72 65 64 20 66 72 6f 6d 20 30 20 74 68 72  bered from 0 thr
2860: 6f 75 67 68 20 35 2e 20 20 30 20 69 73 20 74 68  ough 5.  0 is th
2870: 65 0a 2a 2a 20 22 68 61 6c 74 22 20 6f 70 63 6f  e.** "halt" opco
2880: 64 65 20 61 6e 64 20 63 61 75 73 65 73 20 74 68  de and causes th
2890: 65 20 74 65 73 74 20 74 6f 20 65 6e 64 2e 0a 2a  e test to end..*
28a0: 2a 0a 2a 2a 20 20 20 20 30 20 20 20 20 20 20 20  *.**    0       
28b0: 20 20 20 48 61 6c 74 20 61 6e 64 20 72 65 74 75     Halt and retu
28c0: 72 6e 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66  rn the number of
28d0: 20 65 72 72 6f 72 73 0a 2a 2a 20 20 20 20 31 20   errors.**    1 
28e0: 4e 20 53 20 58 20 20 20 20 53 65 74 20 4e 20 62  N S X    Set N b
28f0: 69 74 73 20 62 65 67 69 6e 6e 69 6e 67 20 77 69  its beginning wi
2900: 74 68 20 53 20 61 6e 64 20 69 6e 63 72 65 6d 65  th S and increme
2910: 6e 74 69 6e 67 20 62 79 20 58 0a 2a 2a 20 20 20  nting by X.**   
2920: 20 32 20 4e 20 53 20 58 20 20 20 20 43 6c 65 61   2 N S X    Clea
2930: 72 20 4e 20 62 69 74 73 20 62 65 67 69 6e 6e 69  r N bits beginni
2940: 6e 67 20 77 69 74 68 20 53 20 61 6e 64 20 69 6e  ng with S and in
2950: 63 72 65 6d 65 6e 74 69 6e 67 20 62 79 20 58 0a  crementing by X.
2960: 2a 2a 20 20 20 20 33 20 4e 20 20 20 20 20 20 20  **    3 N       
2970: 20 53 65 74 20 4e 20 72 61 6e 64 6f 6d 6c 79 20   Set N randomly 
2980: 63 68 6f 73 65 6e 20 62 69 74 73 0a 2a 2a 20 20  chosen bits.**  
2990: 20 20 34 20 4e 20 20 20 20 20 20 20 20 43 6c 65    4 N        Cle
29a0: 61 72 20 4e 20 72 61 6e 64 6f 6d 6c 79 20 63 68  ar N randomly ch
29b0: 6f 73 65 6e 20 62 69 74 73 0a 2a 2a 20 20 20 20  osen bits.**    
29c0: 35 20 4e 20 53 20 58 20 20 20 20 53 65 74 20 4e  5 N S X    Set N
29d0: 20 62 69 74 73 20 66 72 6f 6d 20 53 20 69 6e 63   bits from S inc
29e0: 72 65 6d 65 6e 74 20 58 20 69 6e 20 61 72 72 61  rement X in arra
29f0: 79 20 6f 6e 6c 79 2c 20 6e 6f 74 20 69 6e 20 62  y only, not in b
2a00: 69 74 76 65 63 0a 2a 2a 0a 2a 2a 20 54 68 65 20  itvec.**.** The 
2a10: 6f 70 63 6f 64 65 73 20 31 20 74 68 72 6f 75 67  opcodes 1 throug
2a20: 68 20 34 20 70 65 72 66 6f 72 6d 20 73 65 74 20  h 4 perform set 
2a30: 61 6e 64 20 63 6c 65 61 72 20 6f 70 65 72 61 74  and clear operat
2a40: 69 6f 6e 73 20 61 72 65 20 70 65 72 66 6f 72 6d  ions are perform
2a50: 65 64 0a 2a 2a 20 6f 6e 20 62 6f 74 68 20 61 20  ed.** on both a 
2a60: 42 69 74 76 65 63 20 6f 62 6a 65 63 74 20 61 6e  Bitvec object an
2a70: 64 20 6f 6e 20 61 20 6c 69 6e 65 61 72 20 61 72  d on a linear ar
2a80: 72 61 79 20 6f 66 20 62 69 74 73 20 6f 62 74 61  ray of bits obta
2a90: 69 6e 65 64 20 66 72 6f 6d 20 6d 61 6c 6c 6f 63  ined from malloc
2aa0: 2e 0a 2a 2a 20 4f 70 63 6f 64 65 20 35 20 77 6f  ..** Opcode 5 wo
2ab0: 72 6b 73 20 6f 6e 20 74 68 65 20 6c 69 6e 65 61  rks on the linea
2ac0: 72 20 61 72 72 61 79 20 6f 6e 6c 79 2c 20 6e 6f  r array only, no
2ad0: 74 20 6f 6e 20 74 68 65 20 42 69 74 76 65 63 2e  t on the Bitvec.
2ae0: 0a 2a 2a 20 4f 70 63 6f 64 65 20 35 20 69 73 20  .** Opcode 5 is 
2af0: 75 73 65 64 20 74 6f 20 64 65 6c 69 62 65 72 61  used to delibera
2b00: 74 65 6c 79 20 69 6e 64 75 63 65 20 61 20 66 61  tely induce a fa
2b10: 75 6c 74 20 69 6e 20 6f 72 64 65 72 20 74 6f 0a  ult in order to.
2b20: 2a 2a 20 63 6f 6e 66 69 72 6d 20 74 68 61 74 20  ** confirm that 
2b30: 65 72 72 6f 72 20 64 65 74 65 63 74 69 6f 6e 20  error detection 
2b40: 77 6f 72 6b 73 2e 0a 2a 2a 0a 2a 2a 20 41 74 20  works..**.** At 
2b50: 74 68 65 20 63 6f 6e 63 6c 75 73 69 6f 6e 20 6f  the conclusion o
2b60: 66 20 74 68 65 20 74 65 73 74 20 74 68 65 20 6c  f the test the l
2b70: 69 6e 65 61 72 20 61 72 72 61 79 20 69 73 20 63  inear array is c
2b80: 6f 6d 70 61 72 65 64 0a 2a 2a 20 61 67 61 69 6e  ompared.** again
2b90: 73 74 20 74 68 65 20 42 69 74 76 65 63 20 6f 62  st the Bitvec ob
2ba0: 6a 65 63 74 2e 20 20 49 66 20 74 68 65 72 65 20  ject.  If there 
2bb0: 61 72 65 20 61 6e 79 20 64 69 66 66 65 72 65 6e  are any differen
2bc0: 63 65 73 2c 0a 2a 2a 20 61 6e 20 65 72 72 6f 72  ces,.** an error
2bd0: 20 69 73 20 72 65 74 75 72 6e 65 64 2e 20 20 49   is returned.  I
2be0: 66 20 74 68 65 79 20 61 72 65 20 74 68 65 20 73  f they are the s
2bf0: 61 6d 65 2c 20 7a 65 72 6f 20 69 73 20 72 65 74  ame, zero is ret
2c00: 75 72 6e 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20  urned..**.** If 
2c10: 61 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f 63 61 74  a memory allocat
2c20: 69 6f 6e 20 65 72 72 6f 72 20 6f 63 63 75 72 73  ion error occurs
2c30: 2c 20 72 65 74 75 72 6e 20 2d 31 2e 0a 2a 2f 0a  , return -1..*/.
2c40: 69 6e 74 20 73 71 6c 69 74 65 33 42 69 74 76 65  int sqlite3Bitve
2c50: 63 42 75 69 6c 74 69 6e 54 65 73 74 28 69 6e 74  cBuiltinTest(int
2c60: 20 73 7a 2c 20 69 6e 74 20 2a 61 4f 70 29 7b 0a   sz, int *aOp){.
2c70: 20 20 42 69 74 76 65 63 20 2a 70 42 69 74 76 65    Bitvec *pBitve
2c80: 63 20 3d 20 30 3b 0a 20 20 75 6e 73 69 67 6e 65  c = 0;.  unsigne
2c90: 64 20 63 68 61 72 20 2a 70 56 20 3d 20 30 3b 0a  d char *pV = 0;.
2ca0: 20 20 69 6e 74 20 72 63 20 3d 20 2d 31 3b 0a 20    int rc = -1;. 
2cb0: 20 69 6e 74 20 69 2c 20 6e 78 2c 20 70 63 2c 20   int i, nx, pc, 
2cc0: 6f 70 3b 0a 20 20 76 6f 69 64 20 2a 70 54 6d 70  op;.  void *pTmp
2cd0: 53 70 61 63 65 3b 0a 0a 20 20 2f 2a 20 41 6c 6c  Space;..  /* All
2ce0: 6f 63 61 74 65 20 74 68 65 20 42 69 74 76 65 63  ocate the Bitvec
2cf0: 20 74 6f 20 62 65 20 74 65 73 74 65 64 20 61 6e   to be tested an
2d00: 64 20 61 20 6c 69 6e 65 61 72 20 61 72 72 61 79  d a linear array
2d10: 20 6f 66 0a 20 20 2a 2a 20 62 69 74 73 20 74 6f   of.  ** bits to
2d20: 20 61 63 74 20 61 73 20 74 68 65 20 72 65 66 65   act as the refe
2d30: 72 65 6e 63 65 20 2a 2f 0a 20 20 70 42 69 74 76  rence */.  pBitv
2d40: 65 63 20 3d 20 73 71 6c 69 74 65 33 42 69 74 76  ec = sqlite3Bitv
2d50: 65 63 43 72 65 61 74 65 28 20 73 7a 20 29 3b 0a  ecCreate( sz );.
2d60: 20 20 70 56 20 3d 20 73 71 6c 69 74 65 33 5f 6d    pV = sqlite3_m
2d70: 61 6c 6c 6f 63 28 20 28 73 7a 2b 37 29 2f 38 20  alloc( (sz+7)/8 
2d80: 2b 20 31 20 29 3b 0a 20 20 70 54 6d 70 53 70 61  + 1 );.  pTmpSpa
2d90: 63 65 20 3d 20 73 71 6c 69 74 65 33 5f 6d 61 6c  ce = sqlite3_mal
2da0: 6c 6f 63 28 42 49 54 56 45 43 5f 53 5a 29 3b 0a  loc(BITVEC_SZ);.
2db0: 20 20 69 66 28 20 70 42 69 74 76 65 63 3d 3d 30    if( pBitvec==0
2dc0: 20 7c 7c 20 70 56 3d 3d 30 20 7c 7c 20 70 54 6d   || pV==0 || pTm
2dd0: 70 53 70 61 63 65 3d 3d 30 20 20 29 20 67 6f 74  pSpace==0  ) got
2de0: 6f 20 62 69 74 76 65 63 5f 65 6e 64 3b 0a 20 20  o bitvec_end;.  
2df0: 6d 65 6d 73 65 74 28 70 56 2c 20 30 2c 20 28 73  memset(pV, 0, (s
2e00: 7a 2b 37 29 2f 38 20 2b 20 31 29 3b 0a 0a 20 20  z+7)/8 + 1);..  
2e10: 2f 2a 20 4e 55 4c 4c 20 70 42 69 74 76 65 63 20  /* NULL pBitvec 
2e20: 74 65 73 74 73 20 2a 2f 0a 20 20 73 71 6c 69 74  tests */.  sqlit
2e30: 65 33 42 69 74 76 65 63 53 65 74 28 30 2c 20 31  e3BitvecSet(0, 1
2e40: 29 3b 0a 20 20 73 71 6c 69 74 65 33 42 69 74 76  );.  sqlite3Bitv
2e50: 65 63 43 6c 65 61 72 28 30 2c 20 31 2c 20 70 54  ecClear(0, 1, pT
2e60: 6d 70 53 70 61 63 65 29 3b 0a 0a 20 20 2f 2a 20  mpSpace);..  /* 
2e70: 52 75 6e 20 74 68 65 20 70 72 6f 67 72 61 6d 20  Run the program 
2e80: 2a 2f 0a 20 20 70 63 20 3d 20 30 3b 0a 20 20 77  */.  pc = 0;.  w
2e90: 68 69 6c 65 28 20 28 6f 70 20 3d 20 61 4f 70 5b  hile( (op = aOp[
2ea0: 70 63 5d 29 21 3d 30 20 29 7b 0a 20 20 20 20 73  pc])!=0 ){.    s
2eb0: 77 69 74 63 68 28 20 6f 70 20 29 7b 0a 20 20 20  witch( op ){.   
2ec0: 20 20 20 63 61 73 65 20 31 3a 0a 20 20 20 20 20     case 1:.     
2ed0: 20 63 61 73 65 20 32 3a 0a 20 20 20 20 20 20 63   case 2:.      c
2ee0: 61 73 65 20 35 3a 20 7b 0a 20 20 20 20 20 20 20  ase 5: {.       
2ef0: 20 6e 78 20 3d 20 34 3b 0a 20 20 20 20 20 20 20   nx = 4;.       
2f00: 20 69 20 3d 20 61 4f 70 5b 70 63 2b 32 5d 20 2d   i = aOp[pc+2] -
2f10: 20 31 3b 0a 20 20 20 20 20 20 20 20 61 4f 70 5b   1;.        aOp[
2f20: 70 63 2b 32 5d 20 2b 3d 20 61 4f 70 5b 70 63 2b  pc+2] += aOp[pc+
2f30: 33 5d 3b 0a 20 20 20 20 20 20 20 20 62 72 65 61  3];.        brea
2f40: 6b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20  k;.      }.     
2f50: 20 63 61 73 65 20 33 3a 0a 20 20 20 20 20 20 63   case 3:.      c
2f60: 61 73 65 20 34 3a 20 0a 20 20 20 20 20 20 64 65  ase 4: .      de
2f70: 66 61 75 6c 74 3a 20 7b 0a 20 20 20 20 20 20 20  fault: {.       
2f80: 20 6e 78 20 3d 20 32 3b 0a 20 20 20 20 20 20 20   nx = 2;.       
2f90: 20 73 71 6c 69 74 65 33 5f 72 61 6e 64 6f 6d 6e   sqlite3_randomn
2fa0: 65 73 73 28 73 69 7a 65 6f 66 28 69 29 2c 20 26  ess(sizeof(i), &
2fb0: 69 29 3b 0a 20 20 20 20 20 20 20 20 62 72 65 61  i);.        brea
2fc0: 6b 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 7d  k;.      }.    }
2fd0: 0a 20 20 20 20 69 66 28 20 28 2d 2d 61 4f 70 5b  .    if( (--aOp[
2fe0: 70 63 2b 31 5d 29 20 3e 20 30 20 29 20 6e 78 20  pc+1]) > 0 ) nx 
2ff0: 3d 20 30 3b 0a 20 20 20 20 70 63 20 2b 3d 20 6e  = 0;.    pc += n
3000: 78 3b 0a 20 20 20 20 69 20 3d 20 28 69 20 26 20  x;.    i = (i & 
3010: 30 78 37 66 66 66 66 66 66 66 29 25 73 7a 3b 0a  0x7fffffff)%sz;.
3020: 20 20 20 20 69 66 28 20 28 6f 70 20 26 20 31 29      if( (op & 1)
3030: 21 3d 30 20 29 7b 0a 20 20 20 20 20 20 53 45 54  !=0 ){.      SET
3040: 42 49 54 28 70 56 2c 20 28 69 2b 31 29 29 3b 0a  BIT(pV, (i+1));.
3050: 20 20 20 20 20 20 69 66 28 20 6f 70 21 3d 35 20        if( op!=5 
3060: 29 7b 0a 20 20 20 20 20 20 20 20 69 66 28 20 73  ){.        if( s
3070: 71 6c 69 74 65 33 42 69 74 76 65 63 53 65 74 28  qlite3BitvecSet(
3080: 70 42 69 74 76 65 63 2c 20 69 2b 31 29 20 29 20  pBitvec, i+1) ) 
3090: 67 6f 74 6f 20 62 69 74 76 65 63 5f 65 6e 64 3b  goto bitvec_end;
30a0: 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 7d 65 6c  .      }.    }el
30b0: 73 65 7b 0a 20 20 20 20 20 20 43 4c 45 41 52 42  se{.      CLEARB
30c0: 49 54 28 70 56 2c 20 28 69 2b 31 29 29 3b 0a 20  IT(pV, (i+1));. 
30d0: 20 20 20 20 20 73 71 6c 69 74 65 33 42 69 74 76       sqlite3Bitv
30e0: 65 63 43 6c 65 61 72 28 70 42 69 74 76 65 63 2c  ecClear(pBitvec,
30f0: 20 69 2b 31 2c 20 70 54 6d 70 53 70 61 63 65 29   i+1, pTmpSpace)
3100: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 2f  ;.    }.  }..  /
3110: 2a 20 54 65 73 74 20 74 6f 20 6d 61 6b 65 20 73  * Test to make s
3120: 75 72 65 20 74 68 65 20 6c 69 6e 65 61 72 20 61  ure the linear a
3130: 72 72 61 79 20 65 78 61 63 74 6c 79 20 6d 61 74  rray exactly mat
3140: 63 68 65 73 20 74 68 65 0a 20 20 2a 2a 20 42 69  ches the.  ** Bi
3150: 74 76 65 63 20 6f 62 6a 65 63 74 2e 20 20 53 74  tvec object.  St
3160: 61 72 74 20 77 69 74 68 20 74 68 65 20 61 73 73  art with the ass
3170: 75 6d 70 74 69 6f 6e 20 74 68 61 74 20 74 68 65  umption that the
3180: 79 20 64 6f 0a 20 20 2a 2a 20 6d 61 74 63 68 20  y do.  ** match 
3190: 28 72 63 3d 3d 30 29 2e 20 20 43 68 61 6e 67 65  (rc==0).  Change
31a0: 20 72 63 20 74 6f 20 6e 6f 6e 2d 7a 65 72 6f 20   rc to non-zero 
31b0: 69 66 20 61 20 64 69 73 63 72 65 70 61 6e 63 79  if a discrepancy
31c0: 0a 20 20 2a 2a 20 69 73 20 66 6f 75 6e 64 2e 0a  .  ** is found..
31d0: 20 20 2a 2f 0a 20 20 72 63 20 3d 20 73 71 6c 69    */.  rc = sqli
31e0: 74 65 33 42 69 74 76 65 63 54 65 73 74 28 30 2c  te3BitvecTest(0,
31f0: 30 29 20 2b 20 73 71 6c 69 74 65 33 42 69 74 76  0) + sqlite3Bitv
3200: 65 63 54 65 73 74 28 70 42 69 74 76 65 63 2c 20  ecTest(pBitvec, 
3210: 73 7a 2b 31 29 0a 20 20 20 20 20 20 20 20 20 20  sz+1).          
3220: 2b 20 73 71 6c 69 74 65 33 42 69 74 76 65 63 54  + sqlite3BitvecT
3230: 65 73 74 28 70 42 69 74 76 65 63 2c 20 30 29 0a  est(pBitvec, 0).
3240: 20 20 20 20 20 20 20 20 20 20 2b 20 28 73 71 6c            + (sql
3250: 69 74 65 33 42 69 74 76 65 63 53 69 7a 65 28 70  ite3BitvecSize(p
3260: 42 69 74 76 65 63 29 20 2d 20 73 7a 29 3b 0a 20  Bitvec) - sz);. 
3270: 20 66 6f 72 28 69 3d 31 3b 20 69 3c 3d 73 7a 3b   for(i=1; i<=sz;
3280: 20 69 2b 2b 29 7b 0a 20 20 20 20 69 66 28 20 20   i++){.    if(  
3290: 28 54 45 53 54 42 49 54 28 70 56 2c 69 29 29 21  (TESTBIT(pV,i))!
32a0: 3d 73 71 6c 69 74 65 33 42 69 74 76 65 63 54 65  =sqlite3BitvecTe
32b0: 73 74 28 70 42 69 74 76 65 63 2c 69 29 20 29 7b  st(pBitvec,i) ){
32c0: 0a 20 20 20 20 20 20 72 63 20 3d 20 69 3b 0a 20  .      rc = i;. 
32d0: 20 20 20 20 20 62 72 65 61 6b 3b 0a 20 20 20 20       break;.    
32e0: 7d 0a 20 20 7d 0a 0a 20 20 2f 2a 20 46 72 65 65  }.  }..  /* Free
32f0: 20 61 6c 6c 6f 63 61 74 65 64 20 73 74 72 75 63   allocated struc
3300: 74 75 72 65 20 2a 2f 0a 62 69 74 76 65 63 5f 65  ture */.bitvec_e
3310: 6e 64 3a 0a 20 20 73 71 6c 69 74 65 33 5f 66 72  nd:.  sqlite3_fr
3320: 65 65 28 70 54 6d 70 53 70 61 63 65 29 3b 0a 20  ee(pTmpSpace);. 
3330: 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70 56   sqlite3_free(pV
3340: 29 3b 0a 20 20 73 71 6c 69 74 65 33 42 69 74 76  );.  sqlite3Bitv
3350: 65 63 44 65 73 74 72 6f 79 28 70 42 69 74 76 65  ecDestroy(pBitve
3360: 63 29 3b 0a 20 20 72 65 74 75 72 6e 20 72 63 3b  c);.  return rc;
3370: 0a 7d 0a 23 65 6e 64 69 66 20 2f 2a 20 53 51 4c  .}.#endif /* SQL
3380: 49 54 45 5f 4f 4d 49 54 5f 42 55 49 4c 54 49 4e  ITE_OMIT_BUILTIN
3390: 5f 54 45 53 54 20 2a 2f 0a                       _TEST */.