Debian Codegraph @

libkmer/positionDB.H

raw
1 #ifndef POSITIONDB_H
2 #define POSITIONDB_H
3
4 #include <stdio.h>
5 #include "bio++.H"
6 #include "merStream.H"
7
8 // The two existDB inputs can be either forward or canonical. If
9 // canonical, we are smart enough to search exist/only with the
10 // canonical mer.
11
12 // Returns position in posn, resizing it if needed. Space is
13 // allocated if none supplied. The following is valid:
14 //
15 // uint64 *posn = 0L;
16 // uint64 posnMax = 0;
17 // uint64 posnLen = 0;
18 // if (get(somemer, posn, posnMax, posnLen)) {
19 // do something with the positions
20 // }
21 //
22 // exists() returns T/F if mer exists or not
23 // count() returns the number of times that mer is present
24
25 // Define this to use an uncompressed hash table when the width is 32
26 // bits or less. Doing so is A LOT faster in mismatch lookups, but
27 // does use more memory.
28 #undef UNCOMPRESS_HASH_TABLE
29
30 // Define this to leave out references to getTime(), speedCounter()
31 // and make the positionDB build very quietly.
32 #undef SILENTPOSITIONDB
33
34 // Define these to enable some debugging methods
35 #undef DEBUGPOSDB
36 #undef DEBUGREBUILD
37
38 class existDB;
39 class merylStreamReader;
40
41 class positionDB {
42 public:
43 positionDB(char const *filename,
44 uint32 merSize,
45 uint32 merSkip,
46 uint32 maxMismatch,
47 bool loadData=true);
48
49 positionDB(merStream *MS,
50 uint32 merSize,
51 uint32 merSkip,
52 existDB *mask,
53 existDB *only,
54 merylStreamReader *counts,
55 uint32 minCount,
56 uint32 maxCount,
57 uint32 maxMismatch,
58 uint32 maxMemory,
59 bool beVerbose);
60
61 ~positionDB();
62
63 private:
64 void build(merStream *MS,
65 existDB *mask,
66 existDB *only,
67 merylStreamReader *counts,
68 uint32 minCount,
69 uint32 maxCount,
70 bool beVerbose);
71
72 private:
73 void reallocateSpace(uint64*& posn,
74 uint64& posnMax,
75 uint64& posnLen,
76 uint64 len);
77
78 void loadPositions(uint64 v,
79 uint64*& posn,
80 uint64& posnMax,
81 uint64& posnLen,
82 uint64& count);
83
84 public:
85 bool getExact(uint64 mer,
86 uint64*& posn,
87 uint64& posnMax,
88 uint64& posnLen,
89 uint64& count);
90 bool existsExact(uint64 mer);
91 uint64 countExact(uint64 mer);
92
93 public:
94 void filter(uint64 lo, uint64 hi);
95
96 private:
97 double setUpMismatchMatcher(uint32 nErrorsAllowed, uint64 approxMers);
98 public:
99 bool getUpToNMismatches(uint64 mer,
100 uint32 maxMismatches,
101 uint64*& posn,
102 uint64& posnMax,
103 uint64& posnLen);
104 private:
105 uint64 setCount(uint64 mer, uint64 count);
106
107 // Save or load a built table
108 //
109 public:
110 void saveState(char const *filename);
111 bool loadState(char const *filename, bool beNoisy=false, bool loadData=true);
112
113 void printState(FILE *stream);
114
115 // Only really useful for debugging. Don't use.
116 //
117 void dump(char *name);
118
119
120 bool checkREBUILD(uint64 m) {
121 #define DEBUGREBUILD
122 #ifdef DEBUGREBUILD
123 uint64 h = HASH(m);
124 uint64 c = CHECK(m);
125 uint64 r = REBUILD(h, c);
126 if (r != m) {
127 fprintf(stderr, "shift1 = "uint32FMT"\n", _shift1);
128 fprintf(stderr, "shift2 = "uint32FMT"\n", _shift2);
129 fprintf(stderr, "M = "uint64HEX"\n", m);
130 fprintf(stderr, "H = "uint64HEX"\n", h);
131 fprintf(stderr, "C = "uint64HEX"\n", c);
132 fprintf(stderr, "R = "uint64HEX"\n", r);
133 return(false);
134 }
135 return(true);
136 #else
137 return(REBUILD(HASH(m), CHECK(m)) == m);
138 #endif
139 };
140
141 private:
142
143 uint64 HASH(uint64 k) {
144 return(((k >> _shift1) ^ (k >> _shift2) ^ k) & _mask1);
145 };
146
147 uint64 CHECK(uint64 k) {
148 return(k & _mask2);
149 };
150
151 uint64 REBUILD(uint64 h, uint64 c) {
152 // Decode a HASH and a CHECK to get back the mer. You'd better
153 // bloody PRAY you don't break this (test/test-rebuild.C). It
154 // was a headache++ to write.
155
156 uint64 sha = _shift1 - _shift2;
157 uint64 msk = uint64MASK(sha);
158
159 // The check is exactly the mer....just not all there.
160 uint64 mer = c;
161
162 uint64 shf = sha - (_tableSizeInBits % 2);
163 uint64 shg = 0;
164 uint64 shh = _shift1;
165
166 // Unrolling this is troublesome - we still need the tests,
167 // bizarre merSize, tblSize combinations use lots of iterations
168 // (when the merSize and tblSize are about the same, the CHECK is
169 // small, and so we need to do lots of iterations).
170
171 //fprintf(stderr, "shf="uint64FMTW(2)" shg="uint64FMTW(2)" shh="uint64FMTW(2)" mer="uint64HEX"\n", shf, shg, shh, mer);
172
173 do {
174 mer |= (((h >> shg) ^ (mer >> shg) ^ (mer >> shf)) & msk) << shh;
175 //fprintf(stderr, "shf="uint64FMTW(2)" shg="uint64FMTW(2)" shh="uint64FMTW(2)" mer="uint64HEX"\n", shf, shg, shh, mer);
176
177 shf += sha;
178 shg += sha;
179 shh += sha;
180 } while ((shf < _merSizeInBits) && (shh < 64));
181
182 mer &= uint64MASK(_merSizeInBits);
183
184 return(mer);
185 };
186
187 void sortAndRepackBucket(uint64 b);
188
189 uint32 *_bucketSizes;
190 uint64 *_countingBuckets;
191 uint64 *_hashTable_BP; // Bit packed
192 uint32 *_hashTable_FW; // Full width
193 uint64 *_buckets;
194
195 uint64 *_positions;
196
197 uint32 _merSizeInBases;
198 uint32 _merSizeInBits;
199
200 uint32 _merSkipInBases;
201
202 uint64 _tableSizeInEntries;
203 uint32 _tableSizeInBits;
204
205 uint32 _hashWidth; // Hash bith
206 uint32 _chckWidth; // Check bits
207 uint32 _posnWidth; // Positions in the sequence
208 uint32 _pptrWidth; // Pointers to positions
209 uint32 _sizeWidth; // Extra number in the table
210
211 uint64 _hashMask;
212
213 uint32 _wCnt;
214 uint32 _wFin;
215
216 uint32 _shift1;
217 uint32 _shift2;
218 uint64 _mask1;
219 uint64 _mask2;
220
221 uint64 _numberOfMers;
222 uint64 _numberOfPositions;
223 uint64 _numberOfDistinct;
224 uint64 _numberOfUnique;
225 uint64 _numberOfEntries;
226 uint64 _maximumEntries;
227
228 // For sorting the mers
229 //
230 uint32 _sortedMax;
231 uint64 *_sortedChck;
232 uint64 *_sortedPosn;
233
234 // For the mismatch matcher
235 uint32 _nErrorsAllowed;
236 uint32 _hashedErrorsLen;
237 uint32 _hashedErrorsMax;
238 uint64 *_hashedErrors;
239 };
240
241 #endif // POSITIONDB_H