summaryrefslogtreecommitdiffstats
path: root/common/unqlite/bitvec.c
diff options
context:
space:
mode:
Diffstat (limited to 'common/unqlite/bitvec.c')
-rw-r--r--common/unqlite/bitvec.c222
1 files changed, 222 insertions, 0 deletions
diff --git a/common/unqlite/bitvec.c b/common/unqlite/bitvec.c
new file mode 100644
index 0000000..5b78430
--- /dev/null
+++ b/common/unqlite/bitvec.c
@@ -0,0 +1,222 @@
1/*
2 * Symisc unQLite: An Embeddable NoSQL (Post Modern) Database Engine.
3 * Copyright (C) 2012-2013, Symisc Systems http://unqlite.org/
4 * Version 1.1.6
5 * For information on licensing, redistribution of this file, and for a DISCLAIMER OF ALL WARRANTIES
6 * please contact Symisc Systems via:
7 * legal@symisc.net
8 * licensing@symisc.net
9 * contact@symisc.net
10 * or visit:
11 * http://unqlite.org/licensing.html
12 */
13 /* $SymiscID: bitvec.c v1.0 Win7 2013-02-27 15:16 stable <chm@symisc.net> $ */
14#ifndef UNQLITE_AMALGAMATION
15#include "unqliteInt.h"
16#endif
17
18/** This file implements an object that represents a dynmaic
19** bitmap.
20**
21** A bitmap is used to record which pages of a database file have been
22** journalled during a transaction, or which pages have the "dont-write"
23** property. Usually only a few pages are meet either condition.
24** So the bitmap is usually sparse and has low cardinality.
25*/
26/*
27 * Actually, this is not a bitmap but a simple hashtable where page
28 * number (64-bit unsigned integers) are used as the lookup keys.
29 */
30typedef struct bitvec_rec bitvec_rec;
31struct bitvec_rec
32{
33 pgno iPage; /* Page number */
34 bitvec_rec *pNext,*pNextCol; /* Collison link */
35};
36struct Bitvec
37{
38 SyMemBackend *pAlloc; /* Memory allocator */
39 sxu32 nRec; /* Total number of records */
40 sxu32 nSize; /* Table size */
41 bitvec_rec **apRec; /* Record table */
42 bitvec_rec *pList; /* List of records */
43};
44/*
45 * Allocate a new bitvec instance.
46*/
47UNQLITE_PRIVATE Bitvec * unqliteBitvecCreate(SyMemBackend *pAlloc,pgno iSize)
48{
49 bitvec_rec **apNew;
50 Bitvec *p;
51
52 p = (Bitvec *)SyMemBackendAlloc(pAlloc,sizeof(*p) );
53 if( p == 0 ){
54 SXUNUSED(iSize); /* cc warning */
55 return 0;
56 }
57 /* Zero the structure */
58 SyZero(p,sizeof(Bitvec));
59 /* Allocate a new table */
60 p->nSize = 64; /* Must be a power of two */
61 apNew = (bitvec_rec **)SyMemBackendAlloc(pAlloc,p->nSize * sizeof(bitvec_rec *));
62 if( apNew == 0 ){
63 SyMemBackendFree(pAlloc,p);
64 return 0;
65 }
66 /* Zero the new table */
67 SyZero((void *)apNew,p->nSize * sizeof(bitvec_rec *));
68 /* Fill-in */
69 p->apRec = apNew;
70 p->pAlloc = pAlloc;
71 return p;
72}
73/*
74 * Check if the given page number is already installed in the table.
75 * Return true if installed. False otherwise.
76 */
77UNQLITE_PRIVATE int unqliteBitvecTest(Bitvec *p,pgno i)
78{
79 bitvec_rec *pRec;
80 /* Point to the desired bucket */
81 pRec = p->apRec[i & (p->nSize - 1)];
82 for(;;){
83 if( pRec == 0 ){ break; }
84 if( pRec->iPage == i ){
85 /* Page found */
86 return 1;
87 }
88 /* Point to the next entry */
89 pRec = pRec->pNextCol;
90
91 if( pRec == 0 ){ break; }
92 if( pRec->iPage == i ){
93 /* Page found */
94 return 1;
95 }
96 /* Point to the next entry */
97 pRec = pRec->pNextCol;
98
99
100 if( pRec == 0 ){ break; }
101 if( pRec->iPage == i ){
102 /* Page found */
103 return 1;
104 }
105 /* Point to the next entry */
106 pRec = pRec->pNextCol;
107
108
109 if( pRec == 0 ){ break; }
110 if( pRec->iPage == i ){
111 /* Page found */
112 return 1;
113 }
114 /* Point to the next entry */
115 pRec = pRec->pNextCol;
116 }
117 /* No such entry */
118 return 0;
119}
120/*
121 * Install a given page number in our bitmap (Actually, our hashtable).
122 */
123UNQLITE_PRIVATE int unqliteBitvecSet(Bitvec *p,pgno i)
124{
125 bitvec_rec *pRec;
126 sxi32 iBuck;
127 /* Allocate a new instance */
128 pRec = (bitvec_rec *)SyMemBackendPoolAlloc(p->pAlloc,sizeof(bitvec_rec));
129 if( pRec == 0 ){
130 return UNQLITE_NOMEM;
131 }
132 /* Zero the structure */
133 SyZero(pRec,sizeof(bitvec_rec));
134 /* Fill-in */
135 pRec->iPage = i;
136 iBuck = i & (p->nSize - 1);
137 pRec->pNextCol = p->apRec[iBuck];
138 p->apRec[iBuck] = pRec;
139 pRec->pNext = p->pList;
140 p->pList = pRec;
141 p->nRec++;
142 if( p->nRec >= (p->nSize * 3) && p->nRec < 100000 ){
143 /* Grow the hashtable */
144 sxu32 nNewSize = p->nSize << 1;
145 bitvec_rec *pEntry,**apNew;
146 sxu32 n;
147 apNew = (bitvec_rec **)SyMemBackendAlloc(p->pAlloc, nNewSize * sizeof(bitvec_rec *));
148 if( apNew ){
149 sxu32 iBucket;
150 /* Zero the new table */
151 SyZero((void *)apNew, nNewSize * sizeof(bitvec_rec *));
152 /* Rehash all entries */
153 n = 0;
154 pEntry = p->pList;
155 for(;;){
156 /* Loop one */
157 if( n >= p->nRec ){
158 break;
159 }
160 pEntry->pNextCol = 0;
161 /* Install in the new bucket */
162 iBucket = pEntry->iPage & (nNewSize - 1);
163 pEntry->pNextCol = apNew[iBucket];
164 apNew[iBucket] = pEntry;
165 /* Point to the next entry */
166 pEntry = pEntry->pNext;
167 n++;
168 }
169 /* Release the old table and reflect the change */
170 SyMemBackendFree(p->pAlloc,(void *)p->apRec);
171 p->apRec = apNew;
172 p->nSize = nNewSize;
173 }
174 }
175 return UNQLITE_OK;
176}
177/*
178 * Destroy a bitvec instance. Reclaim all memory used.
179 */
180UNQLITE_PRIVATE void unqliteBitvecDestroy(Bitvec *p)
181{
182 bitvec_rec *pNext,*pRec = p->pList;
183 SyMemBackend *pAlloc = p->pAlloc;
184
185 for(;;){
186 if( p->nRec < 1 ){
187 break;
188 }
189 pNext = pRec->pNext;
190 SyMemBackendPoolFree(pAlloc,(void *)pRec);
191 pRec = pNext;
192 p->nRec--;
193
194 if( p->nRec < 1 ){
195 break;
196 }
197 pNext = pRec->pNext;
198 SyMemBackendPoolFree(pAlloc,(void *)pRec);
199 pRec = pNext;
200 p->nRec--;
201
202
203 if( p->nRec < 1 ){
204 break;
205 }
206 pNext = pRec->pNext;
207 SyMemBackendPoolFree(pAlloc,(void *)pRec);
208 pRec = pNext;
209 p->nRec--;
210
211
212 if( p->nRec < 1 ){
213 break;
214 }
215 pNext = pRec->pNext;
216 SyMemBackendPoolFree(pAlloc,(void *)pRec);
217 pRec = pNext;
218 p->nRec--;
219 }
220 SyMemBackendFree(pAlloc,(void *)p->apRec);
221 SyMemBackendFree(pAlloc,p);
222}
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-30 10:22:33 +0000