bitvec.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407
  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. /* Size of the Bitvec structure in bytes. */
  39. #define BITVEC_SZ 512
  40. /* Round the union size down to the nearest pointer boundary, since that's how
  41. ** it will be aligned within the Bitvec struct. */
  42. #define BITVEC_USIZE (((BITVEC_SZ-(3*sizeof(u32)))/sizeof(Bitvec*))*sizeof(Bitvec*))
  43. /* Type of the array "element" for the bitmap representation.
  44. ** Should be a power of 2, and ideally, evenly divide into BITVEC_USIZE.
  45. ** Setting this to the "natural word" size of your CPU may improve
  46. ** performance. */
  47. #define BITVEC_TELEM u8
  48. /* Size, in bits, of the bitmap element. */
  49. #define BITVEC_SZELEM 8
  50. /* Number of elements in a bitmap array. */
  51. #define BITVEC_NELEM (BITVEC_USIZE/sizeof(BITVEC_TELEM))
  52. /* Number of bits in the bitmap array. */
  53. #define BITVEC_NBIT (BITVEC_NELEM*BITVEC_SZELEM)
  54. /* Number of u32 values in hash table. */
  55. #define BITVEC_NINT (BITVEC_USIZE/sizeof(u32))
  56. /* Maximum number of entries in hash table before
  57. ** sub-dividing and re-hashing. */
  58. #define BITVEC_MXHASH (BITVEC_NINT/2)
  59. /* Hashing function for the aHash representation.
  60. ** Empirical testing showed that the *37 multiplier
  61. ** (an arbitrary prime)in the hash function provided
  62. ** no fewer collisions than the no-op *1. */
  63. #define BITVEC_HASH(X) (((X)*1)%BITVEC_NINT)
  64. #define BITVEC_NPTR (BITVEC_USIZE/sizeof(Bitvec *))
  65. /*
  66. ** A bitmap is an instance of the following structure.
  67. **
  68. ** This bitmap records the existence of zero or more bits
  69. ** with values between 1 and iSize, inclusive.
  70. **
  71. ** There are three possible representations of the bitmap.
  72. ** If iSize<=BITVEC_NBIT, then Bitvec.u.aBitmap[] is a straight
  73. ** bitmap. The least significant bit is bit 1.
  74. **
  75. ** If iSize>BITVEC_NBIT and iDivisor==0 then Bitvec.u.aHash[] is
  76. ** a hash table that will hold up to BITVEC_MXHASH distinct values.
  77. **
  78. ** Otherwise, the value i is redirected into one of BITVEC_NPTR
  79. ** sub-bitmaps pointed to by Bitvec.u.apSub[]. Each subbitmap
  80. ** handles up to iDivisor separate values of i. apSub[0] holds
  81. ** values between 1 and iDivisor. apSub[1] holds values between
  82. ** iDivisor+1 and 2*iDivisor. apSub[N] holds values between
  83. ** N*iDivisor+1 and (N+1)*iDivisor. Each subbitmap is normalized
  84. ** to hold deal with values between 1 and iDivisor.
  85. */
  86. struct Bitvec {
  87. u32 iSize; /* Maximum bit index. Max iSize is 4,294,967,296. */
  88. u32 nSet; /* Number of bits that are set - only valid for aHash
  89. ** element. Max is BITVEC_NINT. For BITVEC_SZ of 512,
  90. ** this would be 125. */
  91. u32 iDivisor; /* Number of bits handled by each apSub[] entry. */
  92. /* Should >=0 for apSub element. */
  93. /* Max iDivisor is max(u32) / BITVEC_NPTR + 1. */
  94. /* For a BITVEC_SZ of 512, this would be 34,359,739. */
  95. union {
  96. BITVEC_TELEM aBitmap[BITVEC_NELEM]; /* Bitmap representation */
  97. u32 aHash[BITVEC_NINT]; /* Hash table representation */
  98. Bitvec *apSub[BITVEC_NPTR]; /* Recursive representation */
  99. } u;
  100. };
  101. /*
  102. ** Create a new bitmap object able to handle bits between 0 and iSize,
  103. ** inclusive. Return a pointer to the new object. Return NULL if
  104. ** malloc fails.
  105. */
  106. Bitvec *sqlite3BitvecCreate(u32 iSize){
  107. Bitvec *p;
  108. assert( sizeof(*p)==BITVEC_SZ );
  109. p = sqlite3MallocZero( sizeof(*p) );
  110. if( p ){
  111. p->iSize = iSize;
  112. }
  113. return p;
  114. }
  115. /*
  116. ** Check to see if the i-th bit is set. Return true or false.
  117. ** If p is NULL (if the bitmap has not been created) or if
  118. ** i is out of range, then return false.
  119. */
  120. int sqlite3BitvecTest(Bitvec *p, u32 i){
  121. if( p==0 ) return 0;
  122. if( i>p->iSize || i==0 ) return 0;
  123. i--;
  124. while( p->iDivisor ){
  125. u32 bin = i/p->iDivisor;
  126. i = i%p->iDivisor;
  127. p = p->u.apSub[bin];
  128. if (!p) {
  129. return 0;
  130. }
  131. }
  132. if( p->iSize<=BITVEC_NBIT ){
  133. return (p->u.aBitmap[i/BITVEC_SZELEM] & (1<<(i&(BITVEC_SZELEM-1))))!=0;
  134. } else{
  135. u32 h = BITVEC_HASH(i++);
  136. while( p->u.aHash[h] ){
  137. if( p->u.aHash[h]==i ) return 1;
  138. h = (h+1) % BITVEC_NINT;
  139. }
  140. return 0;
  141. }
  142. }
  143. /*
  144. ** Set the i-th bit. Return 0 on success and an error code if
  145. ** anything goes wrong.
  146. **
  147. ** This routine might cause sub-bitmaps to be allocated. Failing
  148. ** to get the memory needed to hold the sub-bitmap is the only
  149. ** that can go wrong with an insert, assuming p and i are valid.
  150. **
  151. ** The calling function must ensure that p is a valid Bitvec object
  152. ** and that the value for "i" is within range of the Bitvec object.
  153. ** Otherwise the behavior is undefined.
  154. */
  155. int sqlite3BitvecSet(Bitvec *p, u32 i){
  156. u32 h;
  157. if( p==0 ) return SQLITE_OK;
  158. assert( i>0 );
  159. assert( i<=p->iSize );
  160. i--;
  161. while((p->iSize > BITVEC_NBIT) && p->iDivisor) {
  162. u32 bin = i/p->iDivisor;
  163. i = i%p->iDivisor;
  164. if( p->u.apSub[bin]==0 ){
  165. p->u.apSub[bin] = sqlite3BitvecCreate( p->iDivisor );
  166. if( p->u.apSub[bin]==0 ) return SQLITE_NOMEM;
  167. }
  168. p = p->u.apSub[bin];
  169. }
  170. if( p->iSize<=BITVEC_NBIT ){
  171. p->u.aBitmap[i/BITVEC_SZELEM] |= 1 << (i&(BITVEC_SZELEM-1));
  172. return SQLITE_OK;
  173. }
  174. h = BITVEC_HASH(i++);
  175. /* if there wasn't a hash collision, and this doesn't */
  176. /* completely fill the hash, then just add it without */
  177. /* worring about sub-dividing and re-hashing. */
  178. if( !p->u.aHash[h] ){
  179. if (p->nSet<(BITVEC_NINT-1)) {
  180. goto bitvec_set_end;
  181. } else {
  182. goto bitvec_set_rehash;
  183. }
  184. }
  185. /* there was a collision, check to see if it's already */
  186. /* in hash, if not, try to find a spot for it */
  187. do {
  188. if( p->u.aHash[h]==i ) return SQLITE_OK;
  189. h++;
  190. if( h>=BITVEC_NINT ) h = 0;
  191. } while( p->u.aHash[h] );
  192. /* we didn't find it in the hash. h points to the first */
  193. /* available free spot. check to see if this is going to */
  194. /* make our hash too "full". */
  195. bitvec_set_rehash:
  196. if( p->nSet>=BITVEC_MXHASH ){
  197. unsigned int j;
  198. int rc;
  199. u32 *aiValues = sqlite3StackAllocRaw(0, sizeof(p->u.aHash));
  200. if( aiValues==0 ){
  201. return SQLITE_NOMEM;
  202. }else{
  203. memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash));
  204. memset(p->u.apSub, 0, sizeof(p->u.apSub));
  205. p->iDivisor = (p->iSize + BITVEC_NPTR - 1)/BITVEC_NPTR;
  206. rc = sqlite3BitvecSet(p, i);
  207. for(j=0; j<BITVEC_NINT; j++){
  208. if( aiValues[j] ) rc |= sqlite3BitvecSet(p, aiValues[j]);
  209. }
  210. sqlite3StackFree(0, aiValues);
  211. return rc;
  212. }
  213. }
  214. bitvec_set_end:
  215. p->nSet++;
  216. p->u.aHash[h] = i;
  217. return SQLITE_OK;
  218. }
  219. /*
  220. ** Clear the i-th bit.
  221. **
  222. ** pBuf must be a pointer to at least BITVEC_SZ bytes of temporary storage
  223. ** that BitvecClear can use to rebuilt its hash table.
  224. */
  225. void sqlite3BitvecClear(Bitvec *p, u32 i, void *pBuf){
  226. if( p==0 ) return;
  227. assert( i>0 );
  228. i--;
  229. while( p->iDivisor ){
  230. u32 bin = i/p->iDivisor;
  231. i = i%p->iDivisor;
  232. p = p->u.apSub[bin];
  233. if (!p) {
  234. return;
  235. }
  236. }
  237. if( p->iSize<=BITVEC_NBIT ){
  238. p->u.aBitmap[i/BITVEC_SZELEM] &= ~(1 << (i&(BITVEC_SZELEM-1)));
  239. }else{
  240. unsigned int j;
  241. u32 *aiValues = pBuf;
  242. memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash));
  243. memset(p->u.aHash, 0, sizeof(p->u.aHash));
  244. p->nSet = 0;
  245. for(j=0; j<BITVEC_NINT; j++){
  246. if( aiValues[j] && aiValues[j]!=(i+1) ){
  247. u32 h = BITVEC_HASH(aiValues[j]-1);
  248. p->nSet++;
  249. while( p->u.aHash[h] ){
  250. h++;
  251. if( h>=BITVEC_NINT ) h = 0;
  252. }
  253. p->u.aHash[h] = aiValues[j];
  254. }
  255. }
  256. }
  257. }
  258. /*
  259. ** Destroy a bitmap object. Reclaim all memory used.
  260. */
  261. void sqlite3BitvecDestroy(Bitvec *p){
  262. if( p==0 ) return;
  263. if( p->iDivisor ){
  264. unsigned int i;
  265. for(i=0; i<BITVEC_NPTR; i++){
  266. sqlite3BitvecDestroy(p->u.apSub[i]);
  267. }
  268. }
  269. sqlite3_free(p);
  270. }
  271. /*
  272. ** Return the value of the iSize parameter specified when Bitvec *p
  273. ** was created.
  274. */
  275. u32 sqlite3BitvecSize(Bitvec *p){
  276. return p->iSize;
  277. }
  278. #ifndef SQLITE_OMIT_BUILTIN_TEST
  279. /*
  280. ** Let V[] be an array of unsigned characters sufficient to hold
  281. ** up to N bits. Let I be an integer between 0 and N. 0<=I<N.
  282. ** Then the following macros can be used to set, clear, or test
  283. ** individual bits within V.
  284. */
  285. #define SETBIT(V,I) V[I>>3] |= (1<<(I&7))
  286. #define CLEARBIT(V,I) V[I>>3] &= ~(1<<(I&7))
  287. #define TESTBIT(V,I) (V[I>>3]&(1<<(I&7)))!=0
  288. /*
  289. ** This routine runs an extensive test of the Bitvec code.
  290. **
  291. ** The input is an array of integers that acts as a program
  292. ** to test the Bitvec. The integers are opcodes followed
  293. ** by 0, 1, or 3 operands, depending on the opcode. Another
  294. ** opcode follows immediately after the last operand.
  295. **
  296. ** There are 6 opcodes numbered from 0 through 5. 0 is the
  297. ** "halt" opcode and causes the test to end.
  298. **
  299. ** 0 Halt and return the number of errors
  300. ** 1 N S X Set N bits beginning with S and incrementing by X
  301. ** 2 N S X Clear N bits beginning with S and incrementing by X
  302. ** 3 N Set N randomly chosen bits
  303. ** 4 N Clear N randomly chosen bits
  304. ** 5 N S X Set N bits from S increment X in array only, not in bitvec
  305. **
  306. ** The opcodes 1 through 4 perform set and clear operations are performed
  307. ** on both a Bitvec object and on a linear array of bits obtained from malloc.
  308. ** Opcode 5 works on the linear array only, not on the Bitvec.
  309. ** Opcode 5 is used to deliberately induce a fault in order to
  310. ** confirm that error detection works.
  311. **
  312. ** At the conclusion of the test the linear array is compared
  313. ** against the Bitvec object. If there are any differences,
  314. ** an error is returned. If they are the same, zero is returned.
  315. **
  316. ** If a memory allocation error occurs, return -1.
  317. */
  318. int sqlite3BitvecBuiltinTest(int sz, int *aOp){
  319. Bitvec *pBitvec = 0;
  320. unsigned char *pV = 0;
  321. int rc = -1;
  322. int i, nx, pc, op;
  323. void *pTmpSpace;
  324. /* Allocate the Bitvec to be tested and a linear array of
  325. ** bits to act as the reference */
  326. pBitvec = sqlite3BitvecCreate( sz );
  327. pV = sqlite3MallocZero( (sz+7)/8 + 1 );
  328. pTmpSpace = sqlite3_malloc(BITVEC_SZ);
  329. if( pBitvec==0 || pV==0 || pTmpSpace==0 ) goto bitvec_end;
  330. /* NULL pBitvec tests */
  331. sqlite3BitvecSet(0, 1);
  332. sqlite3BitvecClear(0, 1, pTmpSpace);
  333. /* Run the program */
  334. pc = 0;
  335. while( (op = aOp[pc])!=0 ){
  336. switch( op ){
  337. case 1:
  338. case 2:
  339. case 5: {
  340. nx = 4;
  341. i = aOp[pc+2] - 1;
  342. aOp[pc+2] += aOp[pc+3];
  343. break;
  344. }
  345. case 3:
  346. case 4:
  347. default: {
  348. nx = 2;
  349. sqlite3_randomness(sizeof(i), &i);
  350. break;
  351. }
  352. }
  353. if( (--aOp[pc+1]) > 0 ) nx = 0;
  354. pc += nx;
  355. i = (i & 0x7fffffff)%sz;
  356. if( (op & 1)!=0 ){
  357. SETBIT(pV, (i+1));
  358. if( op!=5 ){
  359. if( sqlite3BitvecSet(pBitvec, i+1) ) goto bitvec_end;
  360. }
  361. }else{
  362. CLEARBIT(pV, (i+1));
  363. sqlite3BitvecClear(pBitvec, i+1, pTmpSpace);
  364. }
  365. }
  366. /* Test to make sure the linear array exactly matches the
  367. ** Bitvec object. Start with the assumption that they do
  368. ** match (rc==0). Change rc to non-zero if a discrepancy
  369. ** is found.
  370. */
  371. rc = sqlite3BitvecTest(0,0) + sqlite3BitvecTest(pBitvec, sz+1)
  372. + sqlite3BitvecTest(pBitvec, 0)
  373. + (sqlite3BitvecSize(pBitvec) - sz);
  374. for(i=1; i<=sz; i++){
  375. if( (TESTBIT(pV,i))!=sqlite3BitvecTest(pBitvec,i) ){
  376. rc = i;
  377. break;
  378. }
  379. }
  380. /* Free allocated structure */
  381. bitvec_end:
  382. sqlite3_free(pTmpSpace);
  383. sqlite3_free(pV);
  384. sqlite3BitvecDestroy(pBitvec);
  385. return rc;
  386. }
  387. #endif /* SQLITE_OMIT_BUILTIN_TEST */