wasCSharpSQLite – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 using System;
2 using System.Diagnostics;
3 using System.Runtime.InteropServices;
4  
5 using Pgno = System.UInt32;
6 using i64 = System.Int64;
7 using u32 = System.UInt32;
8 using BITVEC_TELEM = System.Byte;
9  
10 namespace Community.CsharpSqlite
11 {
12  
13 public partial class Sqlite3
14 {
15 /*
16 ** 2008 February 16
17 **
18 ** The author disclaims copyright to this source code. In place of
19 ** a legal notice, here is a blessing:
20 **
21 ** May you do good and not evil.
22 ** May you find forgiveness for yourself and forgive others.
23 ** May you share freely, never taking more than you give.
24 **
25 *************************************************************************
26 ** This file implements an object that represents a fixed-length
27 ** bitmap. Bits are numbered starting with 1.
28 **
29 ** A bitmap is used to record which pages of a database file have been
30 ** journalled during a transaction, or which pages have the "dont-write"
31 ** property. Usually only a few pages are meet either condition.
32 ** So the bitmap is usually sparse and has low cardinality.
33 ** But sometimes (for example when during a DROP of a large table) most
34 ** or all of the pages in a database can get journalled. In those cases,
35 ** the bitmap becomes dense with high cardinality. The algorithm needs
36 ** to handle both cases well.
37 **
38 ** The size of the bitmap is fixed when the object is created.
39 **
40 ** All bits are clear when the bitmap is created. Individual bits
41 ** may be set or cleared one at a time.
42 **
43 ** Test operations are about 100 times more common that set operations.
44 ** Clear operations are exceedingly rare. There are usually between
45 ** 5 and 500 set operations per Bitvec object, though the number of sets can
46 ** sometimes grow into tens of thousands or larger. The size of the
47 ** Bitvec object is the number of pages in the database file at the
48 ** start of a transaction, and is thus usually less than a few thousand,
49 ** but can be as large as 2 billion for a really big database.
50 *************************************************************************
51 ** Included in SQLite3 port to C#-SQLite; 2008 Noah B Hart
52 ** C#-SQLite is an independent reimplementation of the SQLite software library
53 **
54 ** SQLITE_SOURCE_ID: 2010-08-23 18:52:01 42537b60566f288167f1b5864a5435986838e3a3
55 **
56 *************************************************************************
57 */
58 //#include "sqliteInt.h"
59  
60 /* Size of the Bitvec structure in bytes. */
61 static int BITVEC_SZ = 512;
62  
63  
64 /* Round the union size down to the nearest pointer boundary, since that's how
65 ** it will be aligned within the Bitvec struct. */
66 //#define BITVEC_USIZE (((BITVEC_SZ-(3*sizeof(u32)))/sizeof(Bitvec*))*sizeof(Bitvec*))
67 static int BITVEC_USIZE = ( ( ( BITVEC_SZ - ( 3 * sizeof( u32 ) ) ) / 4 ) * 4 );
68  
69 /* Type of the array "element" for the bitmap representation.
70 ** Should be a power of 2, and ideally, evenly divide into BITVEC_USIZE.
71 ** Setting this to the "natural word" size of your CPU may improve
72 ** performance. */
73 //#define BITVEC_TELEM u8
74 //using BITVEC_TELEM = System.Byte;
75  
76 /* Size, in bits, of the bitmap element. */
77 //#define BITVEC_SZELEM 8
78 const int BITVEC_SZELEM = 8;
79  
80 /* Number of elements in a bitmap array. */
81 //#define BITVEC_NELEM (BITVEC_USIZE/sizeof(BITVEC_TELEM))
82 static int BITVEC_NELEM = (int)( BITVEC_USIZE / sizeof( BITVEC_TELEM ) );
83  
84 /* Number of bits in the bitmap array. */
85 //#define BITVEC_NBIT (BITVEC_NELEM*BITVEC_SZELEM)
86 static int BITVEC_NBIT = ( BITVEC_NELEM * BITVEC_SZELEM );
87  
88 /* Number of u32 values in hash table. */
89 //#define BITVEC_NINT (BITVEC_USIZE/sizeof(u32))
90 static u32 BITVEC_NINT = (u32)( BITVEC_USIZE / sizeof( u32 ) );
91  
92 /* Maximum number of entries in hash table before
93 ** sub-dividing and re-hashing. */
94 //#define BITVEC_MXHASH (BITVEC_NINT/2)
95 static int BITVEC_MXHASH = (int)( BITVEC_NINT / 2 );
96  
97 /* Hashing function for the aHash representation.
98 ** Empirical testing showed that the *37 multiplier
99 ** (an arbitrary prime)in the hash function provided
100 ** no fewer collisions than the no-op *1. */
101 //#define BITVEC_HASH(X) (((X)*1)%BITVEC_NINT)
102 static u32 BITVEC_HASH( u32 X )
103 {
104 return (u32)( ( ( X ) * 1 ) % BITVEC_NINT );
105 }
106  
107 static int BITVEC_NPTR = (int)( BITVEC_USIZE / 4 );//sizeof(Bitvec *));
108  
109  
110 /*
111 ** A bitmap is an instance of the following structure.
112 **
113 ** This bitmap records the existence of zero or more bits
114 ** with values between 1 and iSize, inclusive.
115 **
116 ** There are three possible representations of the bitmap.
117 ** If iSize<=BITVEC_NBIT, then Bitvec.u.aBitmap[] is a straight
118 ** bitmap. The least significant bit is bit 1.
119 **
120 ** If iSize>BITVEC_NBIT and iDivisor==0 then Bitvec.u.aHash[] is
121 ** a hash table that will hold up to BITVEC_MXHASH distinct values.
122 **
123 ** Otherwise, the value i is redirected into one of BITVEC_NPTR
124 ** sub-bitmaps pointed to by Bitvec.u.apSub[]. Each subbitmap
125 ** handles up to iDivisor separate values of i. apSub[0] holds
126 ** values between 1 and iDivisor. apSub[1] holds values between
127 ** iDivisor+1 and 2*iDivisor. apSub[N] holds values between
128 ** N*iDivisor+1 and (N+1)*iDivisor. Each subbitmap is normalized
129 ** to hold deal with values between 1 and iDivisor.
130 */
131 public class _u
132 {
133 public BITVEC_TELEM[] aBitmap = new byte[BITVEC_NELEM]; /* Bitmap representation */
134 public u32[] aHash = new u32[BITVEC_NINT]; /* Hash table representation */
135 public Bitvec[] apSub = new Bitvec[BITVEC_NPTR]; /* Recursive representation */
136 }
137 public class Bitvec
138 {
139 public u32 iSize; /* Maximum bit index. Max iSize is 4,294,967,296. */
140 public u32 nSet; /* Number of bits that are set - only valid for aHash
141 ** element. Max is BITVEC_NINT. For BITVEC_SZ of 512,
142 ** this would be 125. */
143 public u32 iDivisor; /* Number of bits handled by each apSub[] entry. */
144 /* Should >=0 for apSub element. */
145 /* Max iDivisor is max(u32) / BITVEC_NPTR + 1. */
146 /* For a BITVEC_SZ of 512, this would be 34,359,739. */
147 public _u u = new _u();
148  
149 public static implicit operator bool( Bitvec b )
150 {
151 return ( b != null );
152 }
153 };
154  
155 /*
156 ** Create a new bitmap object able to handle bits between 0 and iSize,
157 ** inclusive. Return a pointer to the new object. Return NULL if
158 ** malloc fails.
159 */
160 static Bitvec sqlite3BitvecCreate( u32 iSize )
161 {
162 Bitvec p;
163 //Debug.Assert( sizeof(p)==BITVEC_SZ );
164 p = new Bitvec();//sqlite3MallocZero( sizeof(p) );
165 if ( p != null )
166 {
167 p.iSize = iSize;
168 }
169 return p;
170 }
171  
172 /*
173 ** Check to see if the i-th bit is set. Return true or false.
174 ** If p is NULL (if the bitmap has not been created) or if
175 ** i is out of range, then return false.
176 */
177 static int sqlite3BitvecTest( Bitvec p, u32 i )
178 {
179 if ( p == null || i == 0 )
180 return 0;
181 if ( i > p.iSize )
182 return 0;
183 i--;
184 while ( p.iDivisor != 0 )
185 {
186 u32 bin = i / p.iDivisor;
187 i = i % p.iDivisor;
188 p = p.u.apSub[bin];
189 if ( null == p )
190 {
191 return 0;
192 }
193 }
194 if ( p.iSize <= BITVEC_NBIT )
195 {
196 return ( ( p.u.aBitmap[i / BITVEC_SZELEM] & ( 1 << (int)( i & ( BITVEC_SZELEM - 1 ) ) ) ) != 0 ) ? 1 : 0;
197 }
198 else
199 {
200 u32 h = BITVEC_HASH( i++ );
201 while ( p.u.aHash[h] != 0 )
202 {
203 if ( p.u.aHash[h] == i )
204 return 1;
205 h = ( h + 1 ) % BITVEC_NINT;
206 }
207 return 0;
208 }
209 }
210  
211 /*
212 ** Set the i-th bit. Return 0 on success and an error code if
213 ** anything goes wrong.
214 **
215 ** This routine might cause sub-bitmaps to be allocated. Failing
216 ** to get the memory needed to hold the sub-bitmap is the only
217 ** that can go wrong with an insert, assuming p and i are valid.
218 **
219 ** The calling function must ensure that p is a valid Bitvec object
220 ** and that the value for "i" is within range of the Bitvec object.
221 ** Otherwise the behavior is undefined.
222 */
223 static int sqlite3BitvecSet( Bitvec p, u32 i )
224 {
225 u32 h;
226 if ( p == null )
227 return SQLITE_OK;
228 Debug.Assert( i > 0 );
229 Debug.Assert( i <= p.iSize );
230 i--;
231 while ( ( p.iSize > BITVEC_NBIT ) && p.iDivisor != 0 )
232 {
233 u32 bin = i / p.iDivisor;
234 i = i % p.iDivisor;
235 if ( p.u.apSub[bin] == null )
236 {
237 p.u.apSub[bin] = sqlite3BitvecCreate( p.iDivisor );
238 //if ( p.u.apSub[bin] == null )
239 // return SQLITE_NOMEM;
240 }
241 p = p.u.apSub[bin];
242 }
243 if ( p.iSize <= BITVEC_NBIT )
244 {
245 p.u.aBitmap[i / BITVEC_SZELEM] |= (byte)( 1 << (int)( i & ( BITVEC_SZELEM - 1 ) ) );
246 return SQLITE_OK;
247 }
248 h = BITVEC_HASH( i++ );
249 /* if there wasn't a hash collision, and this doesn't */
250 /* completely fill the hash, then just add it without */
251 /* worring about sub-dividing and re-hashing. */
252 if ( 0 == p.u.aHash[h] )
253 {
254 if ( p.nSet < ( BITVEC_NINT - 1 ) )
255 {
256 goto bitvec_set_end;
257 }
258 else
259 {
260 goto bitvec_set_rehash;
261 }
262 }
263 /* there was a collision, check to see if it's already */
264 /* in hash, if not, try to find a spot for it */
265 do
266 {
267 if ( p.u.aHash[h] == i )
268 return SQLITE_OK;
269 h++;
270 if ( h >= BITVEC_NINT )
271 h = 0;
272 } while ( p.u.aHash[h] != 0 );
273 /* we didn't find it in the hash. h points to the first */
274 /* available free spot. check to see if this is going to */
275 /* make our hash too "full". */
276 bitvec_set_rehash:
277 if ( p.nSet >= BITVEC_MXHASH )
278 {
279 u32 j;
280 int rc;
281 u32[] aiValues = new u32[BITVEC_NINT];// = sqlite3StackAllocRaw(0, sizeof(p->u.aHash));
282 //if ( aiValues == null )
283 //{
284 // return SQLITE_NOMEM;
285 //}
286 //else
287 {
288  
289 Buffer.BlockCopy( p.u.aHash, 0, aiValues, 0, aiValues.Length * ( sizeof( u32 ) ) );// memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash));
290 p.u.apSub = new Bitvec[BITVEC_NPTR];//memset(p->u.apSub, 0, sizeof(p->u.apSub));
291 p.iDivisor = (u32)( ( p.iSize + BITVEC_NPTR - 1 ) / BITVEC_NPTR );
292 rc = sqlite3BitvecSet( p, i );
293 for ( j = 0; j < BITVEC_NINT; j++ )
294 {
295 if ( aiValues[j] != 0 )
296 rc |= sqlite3BitvecSet( p, aiValues[j] );
297 }
298 //sqlite3StackFree( null, aiValues );
299 return rc;
300 }
301 }
302 bitvec_set_end:
303 p.nSet++;
304 p.u.aHash[h] = i;
305 return SQLITE_OK;
306 }
307  
308 /*
309 ** Clear the i-th bit.
310 **
311 ** pBuf must be a pointer to at least BITVEC_SZ bytes of temporary storage
312 ** that BitvecClear can use to rebuilt its hash table.
313 */
314 static void sqlite3BitvecClear( Bitvec p, u32 i, u32[] pBuf )
315 {
316 if ( p == null )
317 return;
318 Debug.Assert( i > 0 );
319 i--;
320 while ( p.iDivisor != 0 )
321 {
322 u32 bin = i / p.iDivisor;
323 i = i % p.iDivisor;
324 p = p.u.apSub[bin];
325 if ( null == p )
326 {
327 return;
328 }
329 }
330 if ( p.iSize <= BITVEC_NBIT )
331 {
332 p.u.aBitmap[i / BITVEC_SZELEM] &= (byte)~( ( 1 << (int)( i & ( BITVEC_SZELEM - 1 ) ) ) );
333 }
334 else
335 {
336 u32 j;
337 u32[] aiValues = pBuf;
338 Array.Copy( p.u.aHash, aiValues, p.u.aHash.Length );//memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash));
339 p.u.aHash = new u32[aiValues.Length];// memset(p->u.aHash, 0, sizeof(p->u.aHash));
340 p.nSet = 0;
341 for ( j = 0; j < BITVEC_NINT; j++ )
342 {
343 if ( aiValues[j] != 0 && aiValues[j] != ( i + 1 ) )
344 {
345 u32 h = BITVEC_HASH( aiValues[j] - 1 );
346 p.nSet++;
347 while ( p.u.aHash[h] != 0 )
348 {
349 h++;
350 if ( h >= BITVEC_NINT )
351 h = 0;
352 }
353 p.u.aHash[h] = aiValues[j];
354 }
355 }
356 }
357 }
358  
359 /*
360 ** Destroy a bitmap object. Reclaim all memory used.
361 */
362 static void sqlite3BitvecDestroy( ref Bitvec p )
363 {
364 if ( p == null )
365 return;
366 if ( p.iDivisor != 0 )
367 {
368 u32 i;
369 for ( i = 0; i < BITVEC_NPTR; i++ )
370 {
371 sqlite3BitvecDestroy( ref p.u.apSub[i] );
372 }
373 }
374 //sqlite3_free( ref p );
375 }
376  
377 /*
378 ** Return the value of the iSize parameter specified when Bitvec *p
379 ** was created.
380 */
381 static u32 sqlite3BitvecSize( Bitvec p )
382 {
383 return p.iSize;
384 }
385  
386 #if !SQLITE_OMIT_BUILTIN_TEST
387 /*
388 ** Let V[] be an array of unsigned characters sufficient to hold
389 ** up to N bits. Let I be an integer between 0 and N. 0<=I<N.
390 ** Then the following macros can be used to set, clear, or test
391 ** individual bits within V.
392 */
393 //#define SETBIT(V,I) V[I>>3] |= (1<<(I&7))
394 static void SETBIT( byte[] V, int I )
395 {
396 V[I >> 3] |= (byte)( 1 << ( I & 7 ) );
397 }
398  
399 //#define CLEARBIT(V,I) V[I>>3] &= ~(1<<(I&7))
400 static void CLEARBIT( byte[] V, int I )
401 {
402 V[I >> 3] &= (byte)~( 1 << ( I & 7 ) );
403 }
404  
405 //#define TESTBIT(V,I) (V[I>>3]&(1<<(I&7)))!=0
406 static int TESTBIT( byte[] V, int I )
407 {
408 return ( V[I >> 3] & ( 1 << ( I & 7 ) ) ) != 0 ? 1 : 0;
409 }
410  
411 /*
412 ** This routine runs an extensive test of the Bitvec code.
413 **
414 ** The input is an array of integers that acts as a program
415 ** to test the Bitvec. The integers are opcodes followed
416 ** by 0, 1, or 3 operands, depending on the opcode. Another
417 ** opcode follows immediately after the last operand.
418 **
419 ** There are 6 opcodes numbered from 0 through 5. 0 is the
420 ** "halt" opcode and causes the test to end.
421 **
422 ** 0 Halt and return the number of errors
423 ** 1 N S X Set N bits beginning with S and incrementing by X
424 ** 2 N S X Clear N bits beginning with S and incrementing by X
425 ** 3 N Set N randomly chosen bits
426 ** 4 N Clear N randomly chosen bits
427 ** 5 N S X Set N bits from S increment X in array only, not in bitvec
428 **
429 ** The opcodes 1 through 4 perform set and clear operations are performed
430 ** on both a Bitvec object and on a linear array of bits obtained from malloc.
431 ** Opcode 5 works on the linear array only, not on the Bitvec.
432 ** Opcode 5 is used to deliberately induce a fault in order to
433 ** confirm that error detection works.
434 **
435 ** At the conclusion of the test the linear array is compared
436 ** against the Bitvec object. If there are any differences,
437 ** an error is returned. If they are the same, zero is returned.
438 **
439 ** If a memory allocation error occurs, return -1.
440 */
441 static int sqlite3BitvecBuiltinTest( u32 sz, int[] aOp )
442 {
443 Bitvec pBitvec = null;
444 byte[] pV = null;
445 int rc = -1;
446 int i, nx, pc, op;
447 u32[] pTmpSpace;
448  
449 /* Allocate the Bitvec to be tested and a linear array of
450 ** bits to act as the reference */
451 pBitvec = sqlite3BitvecCreate( sz );
452 pV = sqlite3_malloc( (int)( sz + 7 ) / 8 + 1 );
453 pTmpSpace = new u32[BITVEC_SZ];// sqlite3_malloc( BITVEC_SZ );
454 if ( pBitvec == null || pV == null || pTmpSpace == null )
455 goto bitvec_end;
456 Array.Clear( pV, 0, (int)( sz + 7 ) / 8 + 1 );// memset( pV, 0, ( sz + 7 ) / 8 + 1 );
457  
458 /* NULL pBitvec tests */
459 sqlite3BitvecSet( null, (u32)1 );
460 sqlite3BitvecClear( null, 1, pTmpSpace );
461  
462 /* Run the program */
463 pc = 0;
464 while ( ( op = aOp[pc] ) != 0 )
465 {
466 switch ( op )
467 {
468 case 1:
469 case 2:
470 case 5:
471 {
472 nx = 4;
473 i = aOp[pc + 2] - 1;
474 aOp[pc + 2] += aOp[pc + 3];
475 break;
476 }
477 case 3:
478 case 4:
479 default:
480 {
481 nx = 2;
482 i64 i64Temp = 0;
483 sqlite3_randomness( sizeof( i64 ), ref i64Temp );
484 i = (int)i64Temp;
485 break;
486 }
487 }
488 if ( ( --aOp[pc + 1] ) > 0 )
489 nx = 0;
490 pc += nx;
491 i = (int)( ( i & 0x7fffffff ) % sz );
492 if ( ( op & 1 ) != 0 )
493 {
494 SETBIT( pV, ( i + 1 ) );
495 if ( op != 5 )
496 {
497 if ( sqlite3BitvecSet( pBitvec, (u32)i + 1 ) != 0 )
498 goto bitvec_end;
499 }
500 }
501 else
502 {
503 CLEARBIT( pV, ( i + 1 ) );
504 sqlite3BitvecClear( pBitvec, (u32)i + 1, pTmpSpace );
505 }
506 }
507  
508 /* Test to make sure the linear array exactly matches the
509 ** Bitvec object. Start with the assumption that they do
510 ** match (rc==0). Change rc to non-zero if a discrepancy
511 ** is found.
512 */
513 rc = sqlite3BitvecTest( null, 0 ) + sqlite3BitvecTest( pBitvec, sz + 1 )
514 + sqlite3BitvecTest( pBitvec, 0 )
515 + (int)( sqlite3BitvecSize( pBitvec ) - sz );
516 for ( i = 1; i <= sz; i++ )
517 {
518 if ( ( TESTBIT( pV, i ) ) != sqlite3BitvecTest( pBitvec, (u32)i ) )
519 {
520 rc = i;
521 break;
522 }
523 }
524  
525 /* Free allocated structure */
526 bitvec_end:
527 //sqlite3_free( ref pTmpSpace );
528 //sqlite3_free( ref pV );
529 sqlite3BitvecDestroy( ref pBitvec );
530 return rc;
531 }
532 #endif //* SQLITE_OMIT_BUILTIN_TEST */
533 }
534 }