OpenCoverage

bitvec.c

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/sqlite/src/src/bitvec.c
Source codeSwitch to Preprocessed file
LineSourceCount
1/*-
2** 2008 February 16-
3**-
4** The author disclaims copyright to this source code. In place of-
5** a legal notice, here is a blessing:-
6**-
7** May you do good and not evil.-
8** May you find forgiveness for yourself and forgive others.-
9** May you share freely, never taking more than you give.-
10**-
11*************************************************************************-
12** This file implements an object that represents a fixed-length-
13** bitmap. Bits are numbered starting with 1.-
14**-
15** A bitmap is used to record which pages of a database file have been-
16** journalled during a transaction, or which pages have the "dont-write"-
17** property. Usually only a few pages are meet either condition.-
18** So the bitmap is usually sparse and has low cardinality.-
19** But sometimes (for example when during a DROP of a large table) most-
20** or all of the pages in a database can get journalled. In those cases, -
21** the bitmap becomes dense with high cardinality. The algorithm needs -
22** to handle both cases well.-
23**-
24** The size of the bitmap is fixed when the object is created.-
25**-
26** All bits are clear when the bitmap is created. Individual bits-
27** may be set or cleared one at a time.-
28**-
29** Test operations are about 100 times more common that set operations.-
30** Clear operations are exceedingly rare. There are usually between-
31** 5 and 500 set operations per Bitvec object, though the number of sets can-
32** sometimes grow into tens of thousands or larger. The size of the-
33** Bitvec object is the number of pages in the database file at the-
34** start of a transaction, and is thus usually less than a few thousand,-
35** but can be as large as 2 billion for a really big database.-
36*/-
37#include "sqliteInt.h"-
38-
39/* Size of the Bitvec structure in bytes. */-
40#define BITVEC_SZ 512-
41-
42/* Round the union size down to the nearest pointer boundary, since that's how -
43** it will be aligned within the Bitvec struct. */-
44#define BITVEC_USIZE \-
45 (((BITVEC_SZ-(3*sizeof(u32)))/sizeof(Bitvec*))*sizeof(Bitvec*))-
46-
47/* Type of the array "element" for the bitmap representation. -
48** Should be a power of 2, and ideally, evenly divide into BITVEC_USIZE. -
49** Setting this to the "natural word" size of your CPU may improve-
50** performance. */-
51#define BITVEC_TELEM u8-
52/* Size, in bits, of the bitmap element. */-
53#define BITVEC_SZELEM 8-
54/* Number of elements in a bitmap array. */-
55#define BITVEC_NELEM (BITVEC_USIZE/sizeof(BITVEC_TELEM))-
56/* Number of bits in the bitmap array. */-
57#define BITVEC_NBIT (BITVEC_NELEM*BITVEC_SZELEM)-
58-
59/* Number of u32 values in hash table. */-
60#define BITVEC_NINT (BITVEC_USIZE/sizeof(u32))-
61/* Maximum number of entries in hash table before -
62** sub-dividing and re-hashing. */-
63#define BITVEC_MXHASH (BITVEC_NINT/2)-
64/* Hashing function for the aHash representation.-
65** Empirical testing showed that the *37 multiplier -
66** (an arbitrary prime)in the hash function provided -
67** no fewer collisions than the no-op *1. */-
68#define BITVEC_HASH(X) (((X)*1)%BITVEC_NINT)-
69-
70#define BITVEC_NPTR (BITVEC_USIZE/sizeof(Bitvec *))-
71-
72-
73/*-
74** A bitmap is an instance of the following structure.-
75**-
76** This bitmap records the existence of zero or more bits-
77** with values between 1 and iSize, inclusive.-
78**-
79** There are three possible representations of the bitmap.-
80** If iSize<=BITVEC_NBIT, then Bitvec.u.aBitmap[] is a straight-
81** bitmap. The least significant bit is bit 1.-
82**-
83** If iSize>BITVEC_NBIT and iDivisor==0 then Bitvec.u.aHash[] is-
84** a hash table that will hold up to BITVEC_MXHASH distinct values.-
85**-
86** Otherwise, the value i is redirected into one of BITVEC_NPTR-
87** sub-bitmaps pointed to by Bitvec.u.apSub[]. Each subbitmap-
88** handles up to iDivisor separate values of i. apSub[0] holds-
89** values between 1 and iDivisor. apSub[1] holds values between-
90** iDivisor+1 and 2*iDivisor. apSub[N] holds values between-
91** N*iDivisor+1 and (N+1)*iDivisor. Each subbitmap is normalized-
92** to hold deal with values between 1 and iDivisor.-
93*/-
94struct Bitvec {-
95 u32 iSize; /* Maximum bit index. Max iSize is 4,294,967,296. */-
96 u32 nSet; /* Number of bits that are set - only valid for aHash-
97 ** element. Max is BITVEC_NINT. For BITVEC_SZ of 512,-
98 ** this would be 125. */-
99 u32 iDivisor; /* Number of bits handled by each apSub[] entry. */-
100 /* Should >=0 for apSub element. */-
101 /* Max iDivisor is max(u32) / BITVEC_NPTR + 1. */-
102 /* For a BITVEC_SZ of 512, this would be 34,359,739. */-
103 union {-
104 BITVEC_TELEM aBitmap[BITVEC_NELEM]; /* Bitmap representation */-
105 u32 aHash[BITVEC_NINT]; /* Hash table representation */-
106 Bitvec *apSub[BITVEC_NPTR]; /* Recursive representation */-
107 } u;-
108};-
109-
110/*-
111** Create a new bitmap object able to handle bits between 0 and iSize,-
112** inclusive. Return a pointer to the new object. Return NULL if -
113** malloc fails.-
114*/-
115Bitvec *sqlite3BitvecCreate(u32 iSize){-
116 Bitvec *p;-
117 assert( sizeof(*p)==BITVEC_SZ );-
118 p = sqlite3MallocZero( sizeof(*p) );-
119 if( p ){
pDescription
TRUEevaluated 351440 times by 380 tests
Evaluated by:
  • Self test
  • Self test (10)
  • Self test (101)
  • Self test (104)
  • Self test (106)
  • Self test (107)
  • Self test (108)
  • Self test (109)
  • Self test (11)
  • Self test (110)
  • Self test (111)
  • Self test (112)
  • Self test (113)
  • Self test (114)
  • Self test (115)
  • Self test (116)
  • Self test (117)
  • Self test (118)
  • Self test (119)
  • Self test (12)
  • Self test (120)
  • Self test (121)
  • Self test (122)
  • Self test (123)
  • Self test (124)
  • ...
FALSEevaluated 136 times by 1 test
Evaluated by:
  • Self test (438)
136-351440
120 p->iSize = iSize;-
121 }
executed 351440 times by 380 tests: end of block
Executed by:
  • Self test
  • Self test (10)
  • Self test (101)
  • Self test (104)
  • Self test (106)
  • Self test (107)
  • Self test (108)
  • Self test (109)
  • Self test (11)
  • Self test (110)
  • Self test (111)
  • Self test (112)
  • Self test (113)
  • Self test (114)
  • Self test (115)
  • Self test (116)
  • Self test (117)
  • Self test (118)
  • Self test (119)
  • Self test (12)
  • Self test (120)
  • Self test (121)
  • Self test (122)
  • Self test (123)
  • Self test (124)
  • ...
351440
122 return p;
executed 351576 times by 380 tests: return p;
Executed by:
  • Self test
  • Self test (10)
  • Self test (101)
  • Self test (104)
  • Self test (106)
  • Self test (107)
  • Self test (108)
  • Self test (109)
  • Self test (11)
  • Self test (110)
  • Self test (111)
  • Self test (112)
  • Self test (113)
  • Self test (114)
  • Self test (115)
  • Self test (116)
  • Self test (117)
  • Self test (118)
  • Self test (119)
  • Self test (12)
  • Self test (120)
  • Self test (121)
  • Self test (122)
  • Self test (123)
  • Self test (124)
  • ...
351576
123}-
124-
125/*-
126** Check to see if the i-th bit is set. Return true or false.-
127** If p is NULL (if the bitmap has not been created) or if-
128** i is out of range, then return false.-
129*/-
130int sqlite3BitvecTestNotNull(Bitvec *p, u32 i){-
131 assert( p!=0 );-
132 i--;-
133 if( i>=p->iSize ) return 0;
executed 830574 times by 289 tests: return 0;
Executed by:
  • Self test
  • Self test (10)
  • Self test (101)
  • Self test (104)
  • Self test (11)
  • Self test (12)
  • Self test (13)
  • Self test (14)
  • Self test (15)
  • Self test (17)
  • Self test (18)
  • Self test (185)
  • Self test (186)
  • Self test (187)
  • Self test (188)
  • Self test (189)
  • Self test (19)
  • Self test (190)
  • Self test (191)
  • Self test (192)
  • Self test (193)
  • Self test (194)
  • Self test (195)
  • Self test (196)
  • Self test (197)
  • ...
i>=p->iSizeDescription
TRUEevaluated 830574 times by 289 tests
Evaluated by:
  • Self test
  • Self test (10)
  • Self test (101)
  • Self test (104)
  • Self test (11)
  • Self test (12)
  • Self test (13)
  • Self test (14)
  • Self test (15)
  • Self test (17)
  • Self test (18)
  • Self test (185)
  • Self test (186)
  • Self test (187)
  • Self test (188)
  • Self test (189)
  • Self test (19)
  • Self test (190)
  • Self test (191)
  • Self test (192)
  • Self test (193)
  • Self test (194)
  • Self test (195)
  • Self test (196)
  • Self test (197)
  • ...
FALSEevaluated 42788765 times by 377 tests
Evaluated by:
  • Self test
  • Self test (10)
  • Self test (104)
  • Self test (107)
  • Self test (108)
  • Self test (109)
  • Self test (11)
  • Self test (110)
  • Self test (111)
  • Self test (112)
  • Self test (113)
  • Self test (114)
  • Self test (115)
  • Self test (116)
  • Self test (117)
  • Self test (118)
  • Self test (119)
  • Self test (12)
  • Self test (120)
  • Self test (121)
  • Self test (122)
  • Self test (123)
  • Self test (124)
  • Self test (125)
  • Self test (126)
  • ...
830574-42788765
134 while( p->iDivisor ){
p->iDivisorDescription
TRUEevaluated 54979520 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 42393679 times by 377 tests
Evaluated by:
  • Self test
  • Self test (10)
  • Self test (104)
  • Self test (107)
  • Self test (108)
  • Self test (109)
  • Self test (11)
  • Self test (110)
  • Self test (111)
  • Self test (112)
  • Self test (113)
  • Self test (114)
  • Self test (115)
  • Self test (116)
  • Self test (117)
  • Self test (118)
  • Self test (119)
  • Self test (12)
  • Self test (120)
  • Self test (121)
  • Self test (122)
  • Self test (123)
  • Self test (124)
  • Self test (125)
  • Self test (126)
  • ...
42393679-54979520
135 u32 bin = i/p->iDivisor;-
136 i = i%p->iDivisor;-
137 p = p->u.apSub[bin];-
138 if (!p) {
!pDescription
TRUEevaluated 395086 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 54584434 times by 1 test
Evaluated by:
  • Self test (438)
395086-54584434
139 return 0;
executed 395086 times by 1 test: return 0;
Executed by:
  • Self test (438)
395086
140 }-
141 }
executed 54584434 times by 1 test: end of block
Executed by:
  • Self test (438)
54584434
142 if( p->iSize<=BITVEC_NBIT ){
p->iSize<=((((...sizeof(u8))*8)Description
TRUEevaluated 41799885 times by 377 tests
Evaluated by:
  • Self test
  • Self test (10)
  • Self test (104)
  • Self test (107)
  • Self test (108)
  • Self test (109)
  • Self test (11)
  • Self test (110)
  • Self test (111)
  • Self test (112)
  • Self test (113)
  • Self test (114)
  • Self test (115)
  • Self test (116)
  • Self test (117)
  • Self test (118)
  • Self test (119)
  • Self test (12)
  • Self test (120)
  • Self test (121)
  • Self test (122)
  • Self test (123)
  • Self test (124)
  • Self test (125)
  • Self test (126)
  • ...
FALSEevaluated 593794 times by 1 test
Evaluated by:
  • Self test (438)
593794-41799885
143 return (p->u.aBitmap[i/BITVEC_SZELEM] & (1<<(i&(BITVEC_SZELEM-1))))!=0;
executed 41799885 times by 377 tests: return (p->u.aBitmap[i/8] & (1<<(i&(8 -1))))!=0;
Executed by:
  • Self test
  • Self test (10)
  • Self test (104)
  • Self test (107)
  • Self test (108)
  • Self test (109)
  • Self test (11)
  • Self test (110)
  • Self test (111)
  • Self test (112)
  • Self test (113)
  • Self test (114)
  • Self test (115)
  • Self test (116)
  • Self test (117)
  • Self test (118)
  • Self test (119)
  • Self test (12)
  • Self test (120)
  • Self test (121)
  • Self test (122)
  • Self test (123)
  • Self test (124)
  • Self test (125)
  • Self test (126)
  • ...
41799885
144 } else{-
145 u32 h = BITVEC_HASH(i++);-
146 while( p->u.aHash[h] ){
p->u.aHash[h]Description
TRUEevaluated 92777 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 549566 times by 1 test
Evaluated by:
  • Self test (438)
92777-549566
147 if( p->u.aHash[h]==i ) return 1;
executed 44228 times by 1 test: return 1;
Executed by:
  • Self test (438)
p->u.aHash[h]==iDescription
TRUEevaluated 44228 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 48549 times by 1 test
Evaluated by:
  • Self test (438)
44228-48549
148 h = (h+1) % BITVEC_NINT;-
149 }
executed 48549 times by 1 test: end of block
Executed by:
  • Self test (438)
48549
150 return 0;
executed 549566 times by 1 test: return 0;
Executed by:
  • Self test (438)
549566
151 }-
152}-
153int sqlite3BitvecTest(Bitvec *p, u32 i){-
154 return p!=0 && sqlite3BitvecTestNotNull(p,i);
executed 20241311 times by 38 tests: return p!=0 && sqlite3BitvecTestNotNull(p,i);
Executed by:
  • Self test (10)
  • Self test (100)
  • Self test (11)
  • Self test (12)
  • Self test (13)
  • Self test (14)
  • Self test (15)
  • Self test (16)
  • Self test (17)
  • Self test (18)
  • Self test (19)
  • Self test (2)
  • Self test (20)
  • Self test (21)
  • Self test (22)
  • Self test (23)
  • Self test (3)
  • Self test (32)
  • Self test (33)
  • Self test (39)
  • Self test (4)
  • Self test (438)
  • Self test (5)
  • Self test (54)
  • Self test (55)
  • ...
p!=0Description
TRUEevaluated 20139815 times by 26 tests
Evaluated by:
  • Self test (10)
  • Self test (11)
  • Self test (12)
  • Self test (13)
  • Self test (14)
  • Self test (15)
  • Self test (16)
  • Self test (17)
  • Self test (18)
  • Self test (19)
  • Self test (2)
  • Self test (20)
  • Self test (21)
  • Self test (22)
  • Self test (23)
  • Self test (3)
  • Self test (32)
  • Self test (33)
  • Self test (4)
  • Self test (438)
  • Self test (5)
  • Self test (54)
  • Self test (6)
  • Self test (7)
  • Self test (8)
  • ...
FALSEevaluated 101496 times by 26 tests
Evaluated by:
  • Self test (10)
  • Self test (100)
  • Self test (12)
  • Self test (14)
  • Self test (16)
  • Self test (18)
  • Self test (2)
  • Self test (20)
  • Self test (22)
  • Self test (3)
  • Self test (39)
  • Self test (4)
  • Self test (438)
  • Self test (5)
  • Self test (55)
  • Self test (6)
  • Self test (8)
  • Self test (91)
  • Self test (92)
  • Self test (93)
  • Self test (94)
  • Self test (95)
  • Self test (96)
  • Self test (97)
  • Self test (98)
  • ...
sqlite3BitvecTestNotNull(p,i)Description
TRUEevaluated 1231053 times by 13 tests
Evaluated by:
  • Self test (10)
  • Self test (12)
  • Self test (14)
  • Self test (16)
  • Self test (18)
  • Self test (20)
  • Self test (22)
  • Self test (32)
  • Self test (33)
  • Self test (438)
  • Self test (54)
  • Self test (6)
  • Self test (8)
FALSEevaluated 18908762 times by 23 tests
Evaluated by:
  • Self test (10)
  • Self test (11)
  • Self test (12)
  • Self test (13)
  • Self test (14)
  • Self test (15)
  • Self test (16)
  • Self test (17)
  • Self test (18)
  • Self test (19)
  • Self test (2)
  • Self test (20)
  • Self test (21)
  • Self test (22)
  • Self test (23)
  • Self test (3)
  • Self test (4)
  • Self test (438)
  • Self test (5)
  • Self test (6)
  • Self test (7)
  • Self test (8)
  • Self test (9)
101496-20241311
155}-
156-
157/*-
158** Set the i-th bit. Return 0 on success and an error code if-
159** anything goes wrong.-
160**-
161** This routine might cause sub-bitmaps to be allocated. Failing-
162** to get the memory needed to hold the sub-bitmap is the only-
163** that can go wrong with an insert, assuming p and i are valid.-
164**-
165** The calling function must ensure that p is a valid Bitvec object-
166** and that the value for "i" is within range of the Bitvec object.-
167** Otherwise the behavior is undefined.-
168*/-
169int sqlite3BitvecSet(Bitvec *p, u32 i){-
170 u32 h;-
171 if( p==0 ) return SQLITE_OK;
executed 9272 times by 1 test: return 0;
Executed by:
  • Self test (438)
p==0Description
TRUEevaluated 9272 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 38360328 times by 374 tests
Evaluated by:
  • Self test
  • Self test (10)
  • Self test (104)
  • Self test (11)
  • Self test (110)
  • Self test (111)
  • Self test (112)
  • Self test (113)
  • Self test (114)
  • Self test (115)
  • Self test (116)
  • Self test (117)
  • Self test (118)
  • Self test (119)
  • Self test (12)
  • Self test (120)
  • Self test (121)
  • Self test (122)
  • Self test (123)
  • Self test (124)
  • Self test (125)
  • Self test (126)
  • Self test (127)
  • Self test (128)
  • Self test (129)
  • ...
9272-38360328
172 assert( i>0 );-
173 assert( i<=p->iSize );-
174 i--;-
175 while((p->iSize > BITVEC_NBIT) && p->iDivisor) {
(p->iSize > ((...izeof(u8))*8))Description
TRUEevaluated 56666595 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 37827562 times by 374 tests
Evaluated by:
  • Self test
  • Self test (10)
  • Self test (104)
  • Self test (11)
  • Self test (110)
  • Self test (111)
  • Self test (112)
  • Self test (113)
  • Self test (114)
  • Self test (115)
  • Self test (116)
  • Self test (117)
  • Self test (118)
  • Self test (119)
  • Self test (12)
  • Self test (120)
  • Self test (121)
  • Self test (122)
  • Self test (123)
  • Self test (124)
  • Self test (125)
  • Self test (126)
  • Self test (127)
  • Self test (128)
  • Self test (129)
  • ...
p->iDivisorDescription
TRUEevaluated 56133953 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 532642 times by 1 test
Evaluated by:
  • Self test (438)
532642-56666595
176 u32 bin = i/p->iDivisor;-
177 i = i%p->iDivisor;-
178 if( p->u.apSub[bin]==0 ){
p->u.apSub[bin]==0Description
TRUEevaluated 264392 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 55869561 times by 1 test
Evaluated by:
  • Self test (438)
264392-55869561
179 p->u.apSub[bin] = sqlite3BitvecCreate( p->iDivisor );-
180 if( p->u.apSub[bin]==0 ) return SQLITE_NOMEM_BKPT;
executed 124 times by 1 test: return 7;
Executed by:
  • Self test (438)
p->u.apSub[bin]==0Description
TRUEevaluated 124 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 264268 times by 1 test
Evaluated by:
  • Self test (438)
124-264268
181 }
executed 264268 times by 1 test: end of block
Executed by:
  • Self test (438)
264268
182 p = p->u.apSub[bin];-
183 }
executed 56133829 times by 1 test: end of block
Executed by:
  • Self test (438)
56133829
184 if( p->iSize<=BITVEC_NBIT ){
p->iSize<=((((...sizeof(u8))*8)Description
TRUEevaluated 37827562 times by 374 tests
Evaluated by:
  • Self test
  • Self test (10)
  • Self test (104)
  • Self test (11)
  • Self test (110)
  • Self test (111)
  • Self test (112)
  • Self test (113)
  • Self test (114)
  • Self test (115)
  • Self test (116)
  • Self test (117)
  • Self test (118)
  • Self test (119)
  • Self test (12)
  • Self test (120)
  • Self test (121)
  • Self test (122)
  • Self test (123)
  • Self test (124)
  • Self test (125)
  • Self test (126)
  • Self test (127)
  • Self test (128)
  • Self test (129)
  • ...
FALSEevaluated 532642 times by 1 test
Evaluated by:
  • Self test (438)
532642-37827562
185 p->u.aBitmap[i/BITVEC_SZELEM] |= 1 << (i&(BITVEC_SZELEM-1));-
186 return SQLITE_OK;
executed 37827562 times by 374 tests: return 0;
Executed by:
  • Self test
  • Self test (10)
  • Self test (104)
  • Self test (11)
  • Self test (110)
  • Self test (111)
  • Self test (112)
  • Self test (113)
  • Self test (114)
  • Self test (115)
  • Self test (116)
  • Self test (117)
  • Self test (118)
  • Self test (119)
  • Self test (12)
  • Self test (120)
  • Self test (121)
  • Self test (122)
  • Self test (123)
  • Self test (124)
  • Self test (125)
  • Self test (126)
  • Self test (127)
  • Self test (128)
  • Self test (129)
  • ...
37827562
187 }-
188 h = BITVEC_HASH(i++);-
189 /* if there wasn't a hash collision, and this doesn't */-
190 /* completely fill the hash, then just add it without */-
191 /* worring about sub-dividing and re-hashing. */-
192 if( !p->u.aHash[h] ){
!p->u.aHash[h]Description
TRUEevaluated 530515 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 2127 times by 1 test
Evaluated by:
  • Self test (438)
2127-530515
193 if (p->nSet<(BITVEC_NINT-1)) {
p->nSet<(((((5...izeof(u32))-1)Description
TRUEevaluated 526280 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 4235 times by 1 test
Evaluated by:
  • Self test (438)
4235-526280
194 goto bitvec_set_end;
executed 526280 times by 1 test: goto bitvec_set_end;
Executed by:
  • Self test (438)
526280
195 } else {-
196 goto bitvec_set_rehash;
executed 4235 times by 1 test: goto bitvec_set_rehash;
Executed by:
  • Self test (438)
4235
197 }-
198 }-
199 /* there was a collision, check to see if it's already */-
200 /* in hash, if not, try to find a spot for it */-
201 do {-
202 if( p->u.aHash[h]==i ) return SQLITE_OK;
executed 196 times by 1 test: return 0;
Executed by:
  • Self test (438)
p->u.aHash[h]==iDescription
TRUEevaluated 196 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 11449 times by 1 test
Evaluated by:
  • Self test (438)
196-11449
203 h++;-
204 if( h>=BITVEC_NINT ) h = 0;
executed 79 times by 1 test: h = 0;
Executed by:
  • Self test (438)
h>=((((512 -(3...)/sizeof(u32))Description
TRUEevaluated 79 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 11370 times by 1 test
Evaluated by:
  • Self test (438)
79-11370
205 } while( p->u.aHash[h] );
executed 11449 times by 1 test: end of block
Executed by:
  • Self test (438)
p->u.aHash[h]Description
TRUEevaluated 9518 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 1931 times by 1 test
Evaluated by:
  • Self test (438)
1931-11449
206 /* we didn't find it in the hash. h points to the first */-
207 /* available free spot. check to see if this is going to */-
208 /* make our hash too "full". */-
209bitvec_set_rehash:
code before this statement executed 1931 times by 1 test: bitvec_set_rehash:
Executed by:
  • Self test (438)
1931
210 if( p->nSet>=BITVEC_MXHASH ){
p->nSet>=(((((...izeof(u32))/2)Description
TRUEevaluated 4319 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 1847 times by 1 test
Evaluated by:
  • Self test (438)
1847-4319
211 unsigned int j;-
212 int rc;-
213 u32 *aiValues = sqlite3StackAllocRaw(0, sizeof(p->u.aHash));-
214 if( aiValues==0 ){
aiValues==0Description
TRUEevaluated 2 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 4317 times by 1 test
Evaluated by:
  • Self test (438)
2-4317
215 return SQLITE_NOMEM_BKPT;
executed 2 times by 1 test: return 7;
Executed by:
  • Self test (438)
2
216 }else{-
217 memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash));-
218 memset(p->u.apSub, 0, sizeof(p->u.apSub));-
219 p->iDivisor = (p->iSize + BITVEC_NPTR - 1)/BITVEC_NPTR;-
220 rc = sqlite3BitvecSet(p, i);-
221 for(j=0; j<BITVEC_NINT; j++){
j<((((512 -(3*...)/sizeof(u32))Description
TRUEevaluated 535308 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 4317 times by 1 test
Evaluated by:
  • Self test (438)
4317-535308
222 if( aiValues[j] ) rc |= sqlite3BitvecSet(p, aiValues[j]);
executed 526580 times by 1 test: rc |= sqlite3BitvecSet(p, aiValues[j]);
Executed by:
  • Self test (438)
aiValues[j]Description
TRUEevaluated 526580 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 8728 times by 1 test
Evaluated by:
  • Self test (438)
8728-526580
223 }
executed 535308 times by 1 test: end of block
Executed by:
  • Self test (438)
535308
224 sqlite3StackFree(0, aiValues);-
225 return rc;
executed 4317 times by 1 test: return rc;
Executed by:
  • Self test (438)
4317
226 }-
227 }-
228bitvec_set_end:
code before this statement executed 1847 times by 1 test: bitvec_set_end:
Executed by:
  • Self test (438)
1847
229 p->nSet++;-
230 p->u.aHash[h] = i;-
231 return SQLITE_OK;
executed 528127 times by 1 test: return 0;
Executed by:
  • Self test (438)
528127
232}-
233-
234/*-
235** Clear the i-th bit.-
236**-
237** pBuf must be a pointer to at least BITVEC_SZ bytes of temporary storage-
238** that BitvecClear can use to rebuilt its hash table.-
239*/-
240void sqlite3BitvecClear(Bitvec *p, u32 i, void *pBuf){-
241 if( p==0 ) return;
executed 172 times by 1 test: return;
Executed by:
  • Self test (438)
p==0Description
TRUEevaluated 172 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 18465827 times by 1 test
Evaluated by:
  • Self test (438)
172-18465827
242 assert( i>0 );-
243 i--;-
244 while( p->iDivisor ){
p->iDivisorDescription
TRUEevaluated 53123904 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 18070914 times by 1 test
Evaluated by:
  • Self test (438)
18070914-53123904
245 u32 bin = i/p->iDivisor;-
246 i = i%p->iDivisor;-
247 p = p->u.apSub[bin];-
248 if (!p) {
!pDescription
TRUEevaluated 394913 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 52728991 times by 1 test
Evaluated by:
  • Self test (438)
394913-52728991
249 return;
executed 394913 times by 1 test: return;
Executed by:
  • Self test (438)
394913
250 }-
251 }
executed 52728991 times by 1 test: end of block
Executed by:
  • Self test (438)
52728991
252 if( p->iSize<=BITVEC_NBIT ){
p->iSize<=((((...sizeof(u8))*8)Description
TRUEevaluated 17916889 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 154025 times by 1 test
Evaluated by:
  • Self test (438)
154025-17916889
253 p->u.aBitmap[i/BITVEC_SZELEM] &= ~(1 << (i&(BITVEC_SZELEM-1)));-
254 }else{
executed 17916889 times by 1 test: end of block
Executed by:
  • Self test (438)
17916889
255 unsigned int j;-
256 u32 *aiValues = pBuf;-
257 memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash));-
258 memset(p->u.aHash, 0, sizeof(p->u.aHash));-
259 p->nSet = 0;-
260 for(j=0; j<BITVEC_NINT; j++){
j<((((512 -(3*...)/sizeof(u32))Description
TRUEevaluated 19099100 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 154025 times by 1 test
Evaluated by:
  • Self test (438)
154025-19099100
261 if( aiValues[j] && aiValues[j]!=(i+1) ){
aiValues[j]Description
TRUEevaluated 3700904 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 15398196 times by 1 test
Evaluated by:
  • Self test (438)
aiValues[j]!=(i+1)Description
TRUEevaluated 3699809 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 1095 times by 1 test
Evaluated by:
  • Self test (438)
1095-15398196
262 u32 h = BITVEC_HASH(aiValues[j]-1);-
263 p->nSet++;-
264 while( p->u.aHash[h] ){
p->u.aHash[h]Description
TRUEevaluated 12219756 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 3699809 times by 1 test
Evaluated by:
  • Self test (438)
3699809-12219756
265 h++;-
266 if( h>=BITVEC_NINT ) h = 0;
executed 65592 times by 1 test: h = 0;
Executed by:
  • Self test (438)
h>=((((512 -(3...)/sizeof(u32))Description
TRUEevaluated 65592 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 12154164 times by 1 test
Evaluated by:
  • Self test (438)
65592-12154164
267 }
executed 12219756 times by 1 test: end of block
Executed by:
  • Self test (438)
12219756
268 p->u.aHash[h] = aiValues[j];-
269 }
executed 3699809 times by 1 test: end of block
Executed by:
  • Self test (438)
3699809
270 }
executed 19099100 times by 1 test: end of block
Executed by:
  • Self test (438)
19099100
271 }
executed 154025 times by 1 test: end of block
Executed by:
  • Self test (438)
154025
272}-
273-
274/*-
275** Destroy a bitmap object. Reclaim all memory used.-
276*/-
277void sqlite3BitvecDestroy(Bitvec *p){-
278 if( p==0 ) return;
executed 703291 times by 438 tests: return;
Executed by:
  • Self test
  • Self test (10)
  • Self test (100)
  • Self test (101)
  • Self test (102)
  • Self test (103)
  • Self test (104)
  • Self test (105)
  • Self test (106)
  • Self test (107)
  • Self test (108)
  • Self test (109)
  • Self test (11)
  • Self test (110)
  • Self test (111)
  • Self test (112)
  • Self test (113)
  • Self test (114)
  • Self test (115)
  • Self test (116)
  • Self test (117)
  • Self test (118)
  • Self test (119)
  • Self test (12)
  • Self test (120)
  • ...
p==0Description
TRUEevaluated 703291 times by 438 tests
Evaluated by:
  • Self test
  • Self test (10)
  • Self test (100)
  • Self test (101)
  • Self test (102)
  • Self test (103)
  • Self test (104)
  • Self test (105)
  • Self test (106)
  • Self test (107)
  • Self test (108)
  • Self test (109)
  • Self test (11)
  • Self test (110)
  • Self test (111)
  • Self test (112)
  • Self test (113)
  • Self test (114)
  • Self test (115)
  • Self test (116)
  • Self test (117)
  • Self test (118)
  • Self test (119)
  • Self test (12)
  • Self test (120)
  • ...
FALSEevaluated 351079 times by 43 tests
Evaluated by:
  • Self test
  • Self test (10)
  • Self test (101)
  • Self test (104)
  • Self test (11)
  • Self test (12)
  • Self test (14)
  • Self test (15)
  • Self test (16)
  • Self test (18)
  • Self test (19)
  • Self test (2)
  • Self test (20)
  • Self test (22)
  • Self test (23)
  • Self test (24)
  • Self test (26)
  • Self test (27)
  • Self test (28)
  • Self test (3)
  • Self test (31)
  • Self test (32)
  • Self test (33)
  • Self test (34)
  • Self test (38)
  • ...
351079-703291
279 if( p->iDivisor ){
p->iDivisorDescription
TRUEevaluated 4317 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 346762 times by 43 tests
Evaluated by:
  • Self test
  • Self test (10)
  • Self test (101)
  • Self test (104)
  • Self test (11)
  • Self test (12)
  • Self test (14)
  • Self test (15)
  • Self test (16)
  • Self test (18)
  • Self test (19)
  • Self test (2)
  • Self test (20)
  • Self test (22)
  • Self test (23)
  • Self test (24)
  • Self test (26)
  • Self test (27)
  • Self test (28)
  • Self test (3)
  • Self test (31)
  • Self test (32)
  • Self test (33)
  • Self test (34)
  • Self test (38)
  • ...
4317-346762
280 unsigned int i;-
281 for(i=0; i<BITVEC_NPTR; i++){
i<((((512 -(3*...eof(Bitvec *))Description
TRUEevaluated 267654 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 4317 times by 1 test
Evaluated by:
  • Self test (438)
4317-267654
282 sqlite3BitvecDestroy(p->u.apSub[i]);-
283 }
executed 267654 times by 1 test: end of block
Executed by:
  • Self test (438)
267654
284 }
executed 4317 times by 1 test: end of block
Executed by:
  • Self test (438)
4317
285 sqlite3_free(p);-
286}
executed 351079 times by 43 tests: end of block
Executed by:
  • Self test
  • Self test (10)
  • Self test (101)
  • Self test (104)
  • Self test (11)
  • Self test (12)
  • Self test (14)
  • Self test (15)
  • Self test (16)
  • Self test (18)
  • Self test (19)
  • Self test (2)
  • Self test (20)
  • Self test (22)
  • Self test (23)
  • Self test (24)
  • Self test (26)
  • Self test (27)
  • Self test (28)
  • Self test (3)
  • Self test (31)
  • Self test (32)
  • Self test (33)
  • Self test (34)
  • Self test (38)
  • ...
351079
287-
288/*-
289** Return the value of the iSize parameter specified when Bitvec *p-
290** was created.-
291*/-
292u32 sqlite3BitvecSize(Bitvec *p){-
293 return p->iSize;
executed 387681 times by 15 tests: return p->iSize;
Executed by:
  • Self test
  • Self test (14)
  • Self test (16)
  • Self test (18)
  • Self test (20)
  • Self test (22)
  • Self test (32)
  • Self test (33)
  • Self test (34)
  • Self test (438)
  • Self test (54)
  • Self test (57)
  • Self test (58)
  • Self test (6)
  • Self test (8)
387681
294}-
295-
296#ifndef SQLITE_UNTESTABLE-
297/*-
298** Let V[] be an array of unsigned characters sufficient to hold-
299** up to N bits. Let I be an integer between 0 and N. 0<=I<N.-
300** Then the following macros can be used to set, clear, or test-
301** individual bits within V.-
302*/-
303#define SETBIT(V,I) V[I>>3] |= (1<<(I&7))-
304#define CLEARBIT(V,I) V[I>>3] &= ~(1<<(I&7))-
305#define TESTBIT(V,I) (V[I>>3]&(1<<(I&7)))!=0-
306-
307/*-
308** This routine runs an extensive test of the Bitvec code.-
309**-
310** The input is an array of integers that acts as a program-
311** to test the Bitvec. The integers are opcodes followed-
312** by 0, 1, or 3 operands, depending on the opcode. Another-
313** opcode follows immediately after the last operand.-
314**-
315** There are 6 opcodes numbered from 0 through 5. 0 is the-
316** "halt" opcode and causes the test to end.-
317**-
318** 0 Halt and return the number of errors-
319** 1 N S X Set N bits beginning with S and incrementing by X-
320** 2 N S X Clear N bits beginning with S and incrementing by X-
321** 3 N Set N randomly chosen bits-
322** 4 N Clear N randomly chosen bits-
323** 5 N S X Set N bits from S increment X in array only, not in bitvec-
324**-
325** The opcodes 1 through 4 perform set and clear operations are performed-
326** on both a Bitvec object and on a linear array of bits obtained from malloc.-
327** Opcode 5 works on the linear array only, not on the Bitvec.-
328** Opcode 5 is used to deliberately induce a fault in order to-
329** confirm that error detection works.-
330**-
331** At the conclusion of the test the linear array is compared-
332** against the Bitvec object. If there are any differences,-
333** an error is returned. If they are the same, zero is returned.-
334**-
335** If a memory allocation error occurs, return -1.-
336*/-
337int sqlite3BitvecBuiltinTest(int sz, int *aOp){-
338 Bitvec *pBitvec = 0;-
339 unsigned char *pV = 0;-
340 int rc = -1;-
341 int i, nx, pc, op;-
342 void *pTmpSpace;-
343-
344 /* Allocate the Bitvec to be tested and a linear array of-
345 ** bits to act as the reference */-
346 pBitvec = sqlite3BitvecCreate( sz );-
347 pV = sqlite3MallocZero( (sz+7)/8 + 1 );-
348 pTmpSpace = sqlite3_malloc64(BITVEC_SZ);-
349 if( pBitvec==0 || pV==0 || pTmpSpace==0 ) goto bitvec_end;
executed 8 times by 1 test: goto bitvec_end;
Executed by:
  • Self test (438)
pBitvec==0Description
TRUEevaluated 2 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 178 times by 1 test
Evaluated by:
  • Self test (438)
pV==0Description
TRUEevaluated 3 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 175 times by 1 test
Evaluated by:
  • Self test (438)
pTmpSpace==0Description
TRUEevaluated 3 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 172 times by 1 test
Evaluated by:
  • Self test (438)
2-178
350-
351 /* NULL pBitvec tests */-
352 sqlite3BitvecSet(0, 1);-
353 sqlite3BitvecClear(0, 1, pTmpSpace);-
354-
355 /* Run the program */-
356 pc = 0;-
357 while( (op = aOp[pc])!=0 ){
(op = aOp[pc])!=0Description
TRUEevaluated 38841234 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 46 times by 1 test
Evaluated by:
  • Self test (438)
46-38841234
358 switch( op ){-
359 case 1:
executed 20359981 times by 1 test: case 1:
Executed by:
  • Self test (438)
20359981
360 case 2:
executed 18457825 times by 1 test: case 2:
Executed by:
  • Self test (438)
18457825
361 case 5: {
executed 2 times by 1 test: case 5:
Executed by:
  • Self test (438)
2
362 nx = 4;-
363 i = aOp[pc+2] - 1;-
364 aOp[pc+2] += aOp[pc+3];-
365 break;
executed 38817808 times by 1 test: break;
Executed by:
  • Self test (438)
38817808
366 }-
367 case 3:
executed 15426 times by 1 test: case 3:
Executed by:
  • Self test (438)
15426
368 case 4:
executed 8000 times by 1 test: case 4:
Executed by:
  • Self test (438)
8000
369 default: {
never executed: default:
0
370 nx = 2;-
371 sqlite3_randomness(sizeof(i), &i);-
372 break;
executed 23426 times by 1 test: break;
Executed by:
  • Self test (438)
23426
373 }-
374 }-
375 if( (--aOp[pc+1]) > 0 ) nx = 0;
executed 38841135 times by 1 test: nx = 0;
Executed by:
  • Self test (438)
(--aOp[pc+1]) > 0Description
TRUEevaluated 38841135 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 99 times by 1 test
Evaluated by:
  • Self test (438)
99-38841135
376 pc += nx;-
377 i = (i & 0x7fffffff)%sz;-
378 if( (op & 1)!=0 ){
(op & 1)!=0Description
TRUEevaluated 20375409 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 18465825 times by 1 test
Evaluated by:
  • Self test (438)
18465825-20375409
379 SETBIT(pV, (i+1));-
380 if( op!=5 ){
op!=5Description
TRUEevaluated 20375407 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 2 times by 1 test
Evaluated by:
  • Self test (438)
2-20375407
381 if( sqlite3BitvecSet(pBitvec, i+1) ) goto bitvec_end;
executed 126 times by 1 test: goto bitvec_end;
Executed by:
  • Self test (438)
sqlite3BitvecSet(pBitvec, i+1)Description
TRUEevaluated 126 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 20375281 times by 1 test
Evaluated by:
  • Self test (438)
126-20375281
382 }
executed 20375281 times by 1 test: end of block
Executed by:
  • Self test (438)
20375281
383 }else{
executed 20375283 times by 1 test: end of block
Executed by:
  • Self test (438)
20375283
384 CLEARBIT(pV, (i+1));-
385 sqlite3BitvecClear(pBitvec, i+1, pTmpSpace);-
386 }
executed 18465825 times by 1 test: end of block
Executed by:
  • Self test (438)
18465825
387 }-
388-
389 /* Test to make sure the linear array exactly matches the-
390 ** Bitvec object. Start with the assumption that they do-
391 ** match (rc==0). Change rc to non-zero if a discrepancy-
392 ** is found.-
393 */-
394 rc = sqlite3BitvecTest(0,0) + sqlite3BitvecTest(pBitvec, sz+1)-
395 + sqlite3BitvecTest(pBitvec, 0)-
396 + (sqlite3BitvecSize(pBitvec) - sz);-
397 for(i=1; i<=sz; i++){
i<=szDescription
TRUEevaluated 19789835 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 44 times by 1 test
Evaluated by:
  • Self test (438)
44-19789835
398 if( (TESTBIT(pV,i))!=sqlite3BitvecTest(pBitvec,i) ){
((pV[i>>3]&(1<...est(pBitvec,i)Description
TRUEevaluated 2 times by 1 test
Evaluated by:
  • Self test (438)
FALSEevaluated 19789833 times by 1 test
Evaluated by:
  • Self test (438)
2-19789833
399 rc = i;-
400 break;
executed 2 times by 1 test: break;
Executed by:
  • Self test (438)
2
401 }-
402 }
executed 19789833 times by 1 test: end of block
Executed by:
  • Self test (438)
19789833
403-
404 /* Free allocated structure */-
405bitvec_end:
code before this statement executed 46 times by 1 test: bitvec_end:
Executed by:
  • Self test (438)
46
406 sqlite3_free(pTmpSpace);-
407 sqlite3_free(pV);-
408 sqlite3BitvecDestroy(pBitvec);-
409 return rc;
executed 180 times by 1 test: return rc;
Executed by:
  • Self test (438)
180
410}-
411#endif /* SQLITE_UNTESTABLE */-
Source codeSwitch to Preprocessed file
Generated by Squish Coco 4.2.2