Debian Codegraph @

libkmer/positionDB-access.C

raw
1 #include "bio++.H"
2 #include "positionDB.H"
3
4
5 void
6 positionDB::reallocateSpace(uint64*& posn,
7 uint64& posnMax,
8 uint64& posnLen,
9 uint64 len) {
10
11 if (posnMax < posnLen + len) {
12 uint64 *pp;
13
14 posnMax = posnLen + len + (len >> 2);
15
16 if (posnMax == 0)
17 posnMax = 16384;
18
19 try {
20 pp = new uint64 [posnMax];
21 } catch (...) {
22 fprintf(stderr, "positionDB::get()-- Can't allocate space for more positions, requested "uint64FMT" uint64's.\n", posnMax);
23 abort();
24 }
25
26 memcpy(pp, posn, sizeof(uint64) * posnLen);
27
28 delete [] posn;
29 posn = pp;
30 }
31 }
32
33
34
35 void
36 positionDB::loadPositions(uint64 J,
37 uint64*& posn,
38 uint64& posnMax,
39 uint64& posnLen,
40 uint64& count) {
41
42 uint64 sizs[3] = {_pptrWidth, 1, _sizeWidth};
43 uint64 vals[3] = {0, 0, 1};
44
45 getDecodedValues(_buckets, J + _chckWidth, (_sizeWidth == 0) ? 2 : 3, sizs, vals);
46
47 // If the size is stored, the count is updated to the correct
48 // thing. If it's not stored, the count is set to 1 by the default
49 // value of vals[2], and reset after we get the number of positions
50 // stored.
51 //
52 count = vals[2];
53
54 if (vals[1]) {
55 reallocateSpace(posn, posnMax, posnLen, 64);
56 posn[posnLen++] = vals[0];
57 } else {
58 uint64 ptr = vals[0] * _posnWidth;
59 uint64 len = getDecodedValue(_positions, ptr, _posnWidth);
60
61 if (_sizeWidth == 0)
62 count = len;
63
64 reallocateSpace(posn, posnMax, posnLen, len + 64);
65
66 for (ptr += _posnWidth; len > 0; ptr += _posnWidth, len--)
67 posn[posnLen++] = getDecodedValue(_positions, ptr, _posnWidth);
68 }
69 }
70
71
72
73 bool
74 positionDB::getExact(uint64 mer,
75 uint64*& posn,
76 uint64& posnMax,
77 uint64& posnLen,
78 uint64& count) {
79 uint64 h = HASH(mer);
80 uint64 c = CHECK(mer);
81 uint64 st, ed;
82
83 if (_hashTable_BP) {
84 st = getDecodedValue(_hashTable_BP, h * _hashWidth, _hashWidth);
85 ed = getDecodedValue(_hashTable_BP, h * _hashWidth + _hashWidth, _hashWidth);
86 } else {
87 st = _hashTable_FW[h];
88 ed = _hashTable_FW[h+1];
89 }
90
91 posnLen = 0;
92
93 if (st == ed)
94 return(false);
95
96 for (uint64 i=st, J=st * _wFin; i<ed; i++, J += _wFin) {
97 if (c == getDecodedValue(_buckets, J, _chckWidth)) {
98 loadPositions(J, posn, posnMax, posnLen, count);
99 return(true);
100 }
101 }
102
103 return(false);
104 }
105
106
107 bool
108 positionDB::existsExact(uint64 mer) {
109 uint64 h = HASH(mer);
110 uint64 c = CHECK(mer);
111 uint64 st, ed;
112
113 if (_hashTable_BP) {
114 st = getDecodedValue(_hashTable_BP, h * _hashWidth, _hashWidth);
115 ed = getDecodedValue(_hashTable_BP, h * _hashWidth + _hashWidth, _hashWidth);
116 } else {
117 st = _hashTable_FW[h];
118 ed = _hashTable_FW[h+1];
119 }
120
121 if (st == ed)
122 return(false);
123
124 for (uint64 i=st, J=st * _wFin; i<ed; i++, J += _wFin)
125 if (c == getDecodedValue(_buckets, J, _chckWidth))
126 return(true);
127
128 return(false);
129 }
130
131
132 uint64
133 positionDB::countExact(uint64 mer) {
134 uint64 h = HASH(mer);
135 uint64 c = CHECK(mer);
136 uint64 st, ed;
137
138 if (_hashTable_BP) {
139 st = getDecodedValue(_hashTable_BP, h * _hashWidth, _hashWidth);
140 ed = getDecodedValue(_hashTable_BP, h * _hashWidth + _hashWidth, _hashWidth);
141 } else {
142 st = _hashTable_FW[h];
143 ed = _hashTable_FW[h+1];
144 }
145
146 if (st == ed)
147 return(0);
148
149 for (uint64 i=st, J=st * _wFin; i<ed; i++, J += _wFin) {
150 if (c == getDecodedValue(_buckets, J, _chckWidth)) {
151 uint64 sizs[3] = {_pptrWidth, 1, _sizeWidth};
152 uint64 vals[3] = {0};
153
154 getDecodedValues(_buckets, J + _chckWidth, 3, sizs, vals);
155
156 if (_sizeWidth > 0)
157 return(vals[2]);
158
159 if (vals[1])
160 return(1);
161
162 return(getDecodedValue(_positions, vals[0] * _posnWidth, _posnWidth));
163 }
164 }
165
166 return(0);
167 }
168
169
170 uint64
171 positionDB::setCount(uint64 mer, uint64 count) {
172 uint64 h = HASH(mer);
173 uint64 c = CHECK(mer);
174 uint64 st, ed;
175
176 if (_hashTable_BP) {
177 st = getDecodedValue(_hashTable_BP, h * _hashWidth, _hashWidth);
178 ed = getDecodedValue(_hashTable_BP, h * _hashWidth + _hashWidth, _hashWidth);
179 } else {
180 st = _hashTable_FW[h];
181 ed = _hashTable_FW[h+1];
182 }
183
184 if (st == ed)
185 return(0);
186
187 for (uint64 i=st, J=st * _wFin; i<ed; i++, J += _wFin)
188 if (c == getDecodedValue(_buckets, J, _chckWidth)) {
189 setDecodedValue(_buckets, J + _chckWidth + _pptrWidth + 1, _sizeWidth, count);
190 return(count);
191 }
192
193 return(0);
194 }
195
196
197
198 void
199 positionDB::filter(uint64 lo,
200 uint64 hi) {
201 uint64 st=0, ed=0; // iteration through buckets
202 uint64 nb=0; // bit position of the current (read) bucket and next (write) bucket
203 uint64 np=0; // bit position of the current (read) position and next (write) position
204 uint64 vv;
205
206 uint64 loCount = 0;
207 uint64 okCount = 0;
208 uint64 hiCount = 0;
209
210 uint64 sizs[4] = {_chckWidth, _pptrWidth, 1, _sizeWidth};
211 uint64 vals[4] = {0, 0, 0, 0};
212
213 //dump("posDB.before");
214
215 fprintf(stderr, "positionDB::filter()-- Filtering out kmers less than "uint64FMT" and more than "uint64FMT"\n", lo, hi);
216
217 if (_sizeWidth == 0) {
218 // Single copy mers in a table without counts can be multi-copy
219 // when combined with their reverse-complement mer.
220 fprintf(stderr, "positionDB::filter()-- ERROR!\n");
221 fprintf(stderr, "positionDB::filter()-- ERROR! No count information; filtering will break canonical assumptions.\n");
222 fprintf(stderr, "positionDB::filter()-- ERROR!\n");
223 exit(1);
224 }
225
226 // Grab the start of the first (current) bucket. We reset the
227 // hashTable at the end of the loop, forcing us to keep st
228 // up-to-date, instead of grabbing it anew each iteration.
229 //
230 if (_hashTable_BP)
231 st = getDecodedValue(_hashTable_BP, 0, _hashWidth);
232 else
233 st = _hashTable_FW[0];
234
235 // Over all buckets
236 //
237 for (uint64 h=0; h<_tableSizeInEntries; h++) {
238
239 // Grab the end of this bucket - the end is always for the
240 // current structure. This gets reset at the end of the loop.
241 //
242 if (_hashTable_BP)
243 ed = getDecodedValue(_hashTable_BP, h * _hashWidth + _hashWidth, _hashWidth);
244 else
245 ed = _hashTable_FW[h+1];
246
247 // Over all entries in the bucket
248 //
249 while (st < ed) {
250 uint64 cb = st * _wFin;
251
252 getDecodedValues(_buckets, cb, (_sizeWidth == 0) ? 3 : 4, sizs, vals);
253
254 // Argh. Tricky. We need to grab the count stored in the
255 // table, but if it's a single mer, there is no count.
256
257 uint64 count = 1; // Real count over the whole data set
258 uint64 len = 1; // Number of times the mer occurs in this subset
259 uint64 cp = ~uint64ZERO; // current position pointer, used to copy position information
260
261 // If not a unique mer in this table, len and cp are defined.
262 if (vals[2] == 0) {
263 cp = vals[1] * _posnWidth;
264 len = getDecodedValue(_positions, cp, _posnWidth);
265 count = len;
266 }
267
268 // The size stored in the bucket is to be believed
269 if (_sizeWidth > 0)
270 count = vals[3];
271
272 // What happened here: By default, the count is 1. If it is
273 // NOT a unique mer in the table, we reset the count to the
274 // number of entries in the table. Then, if there is a count
275 // stored in the table, we reset the count again.
276
277 // Move on to copying the data, if in the correct range.
278
279 if (vals[2] == 1) {
280 // Is a single mer in our table. Copy if the actual count is
281 // acceptable.
282 if ((lo <= count) && (count < hi)) {
283 okCount++;
284 setDecodedValues(_buckets, nb, (_sizeWidth == 0) ? 3 : 4, sizs, vals);
285 nb += _wFin;
286 } else {
287 _numberOfDistinct--;
288 _numberOfMers--;
289 loCount++;
290 }
291 } else {
292 // Mer has more than one location in the table. Copy all
293 // locations if the count is acceptable.
294 if ((lo <= count) && (count < hi)) {
295 okCount++;
296
297 // Copy the bucket
298 vals[1] = np / _posnWidth;
299 setDecodedValues(_buckets, nb, (_sizeWidth == 0) ? 3 : 4, sizs, vals);
300 nb += _wFin;
301
302 // Copy length of the positions
303 if (cp != np)
304 setDecodedValue(_positions, np, _posnWidth, len);
305 np += _posnWidth;
306 cp += _posnWidth;
307
308 // Copy positions
309 while (len > 0) {
310 if (cp != np)
311 setDecodedValue(_positions, np, _posnWidth,
312 getDecodedValue(_positions, cp, _posnWidth));
313 np += _posnWidth;
314 cp += _posnWidth;
315 len--;
316 }
317 } else {
318 // Not acceptable count
319 _numberOfDistinct--;
320 _numberOfEntries -= len;
321 if (count < lo) loCount++;
322 if (count > hi) hiCount++;
323 }
324 }
325
326 // Move to the next entry
327 st++;
328 cb += _wFin;
329 } // Over all entries in the bucket
330
331 // Update the end position of this bucket
332 if (_hashTable_BP)
333 setDecodedValue(_hashTable_BP, h * _hashWidth + _hashWidth, _hashWidth, nb / _wFin);
334 else
335 _hashTable_FW[h+1] = nb / _wFin;
336
337 } // Over all buckets
338
339 fprintf(stderr, "positionDB::filter()-- Filtered "uint64FMT" kmers less than "uint64FMT"\n", loCount, lo);
340 fprintf(stderr, "positionDB::filter()-- Filtered "uint64FMT" kmers more than "uint64FMT"\n", hiCount, hi);
341 fprintf(stderr, "positionDB::filter()-- Saved "uint64FMT" kmers with acceptable count\n", okCount);
342
343 //dump("posDB.after");
344 }