Debian Codegraph @

Source/Utilities/Container/CDynamicReferenceBucket.cpp

raw
1 /*
2 * Copyright (C) 2013-2015, 2019 by the Konclude Developer Team.
3 *
4 * This file is part of the reasoning system Konclude.
5 * For details and support, see <http://konclude.com/>.
6 *
7 * Konclude is free software: you can redistribute it and/or modify
8 * it under the terms of version 3 of the GNU Lesser General Public
9 * License (LGPLv3) as published by the Free Software Foundation.
10 *
11 * Konclude is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU (Lesser) General Public License for more details.
15 *
16 * You should have received a copy of the GNU (Lesser) General Public
17 * License along with Konclude. If not, see <http://www.gnu.org/licenses/>.
18 *
19 */
20
21 #ifndef KONCLUDE_UTILITIES_CONTAINER_CDYNAMICREFERENCEBUCKET_CPP
22 #define KONCLUDE_UTILITIES_CONTAINER_CDYNAMICREFERENCEBUCKET_CPP
23
24
25 #include "CDynamicReferenceBucket.h"
26
27
28 namespace Konclude {
29
30 namespace Utilities {
31
32 namespace Container {
33
34 template<class T, cint64 bucket2Size>
35 CDynamicReferenceBucketBase<T,bucket2Size>::CDynamicReferenceBucketBase(CContext* context) : mContext(context) {
36 mMemMan = CContext::getMemoryAllocationManager(mContext);
37 }
38
39
40 template<class T, cint64 bucket2Size>
41 CDynamicReferenceBucketBase<T,bucket2Size>::~CDynamicReferenceBucketBase() {
42 }
43
44
45 template<class T, cint64 bucket2Size>
46 CDynamicReferenceBucketBase<T,bucket2Size>* CDynamicReferenceBucketBase<T,bucket2Size>::getRelevantReferenceBucket(CDynamicReferenceBucketBase<T,bucket2Size>* bucket) {
47 CDynamicReferenceBucketBase<T,bucket2Size>* relevantBucket = bucket;
48 while (relevantBucket->mVec == nullptr) {
49 relevantBucket = relevantBucket->mReferenceBucket;
50 }
51 return relevantBucket;
52 }
53
54
55 template<class T, cint64 bucket2Size>
56 CDynamicReferenceBucketBase<T,bucket2Size>* CDynamicReferenceBucketBase<T,bucket2Size>::getUpdatedRelevantReferenceBucket(CDynamicReferenceBucketBase<T,bucket2Size>* bucket) {
57 CDynamicReferenceBucketBase<T,bucket2Size>* relevantBucket = bucket;
58 if (bucket) {
59 while (relevantBucket && relevantBucket->mVec == nullptr) {
60 relevantBucket = relevantBucket->mReferenceBucket;
61 }
62 bucket->mReferenceBucket = relevantBucket;
63 }
64 return relevantBucket;
65 }
66
67
68 template<class T, cint64 bucket2Size>
69 void CDynamicReferenceBucketBase<T,bucket2Size>::installBucket(cint64 index, CDynamicReferenceBucketBase<T,bucket2Size>* bucket) {
70 cint64 bucketIndex = getBucketIndex(index,this);
71 if (mVec == nullptr) {
72 bool isBaseBucket = mBucketDepth == 0;
73 CDynamicReferenceBucketBase<T,bucket2Size>* refBucket = nullptr;
74 refBucket = getUpdatedRelevantReferenceBucket(this);
75 mVec = createBucketVector(refBucket,isBaseBucket);
76 }
77 CReferenceBucketDataPair* referenceBucketPair = &mVec[bucketIndex];
78 referenceBucketPair->mReferenced = false;
79 referenceBucketPair->mUninitialized = false;
80 referenceBucketPair->mBucketData.mBucket = bucket;
81 }
82
83
84 template<class T, cint64 bucket2Size>
85 bool CDynamicReferenceBucketBase<T,bucket2Size>::hasLocalData(cint64 index) {
86 CDynamicReferenceBucketBase<T,bucket2Size>* nextBucket = this;
87 while (nextBucket) {
88 if (nextBucket->mVec == nullptr) {
89 return false;
90 }
91 cint64 bucketIndex = getBucketIndex(index,nextBucket);
92 CReferenceBucketDataPair* referenceBucketPair = &nextBucket->mVec[bucketIndex];
93 if (referenceBucketPair->mReferenced) {
94 return false;
95 }
96 bool isBaseBucket = nextBucket->mBucketDepth == 0;
97 if (isBaseBucket) {
98 return !referenceBucketPair->mUninitialized;
99 }
100 nextBucket = referenceBucketPair->mBucketData.mBucket;
101 }
102 return false;
103 }
104
105 template<class T, cint64 bucket2Size>
106 bool CDynamicReferenceBucketBase<T,bucket2Size>::hasReferencedData(cint64 index) {
107 CDynamicReferenceBucketBase<T,bucket2Size>* nextBucket = this;
108 bool isReferenced = false;
109 while (nextBucket) {
110 if (nextBucket->mVec == nullptr) {
111 nextBucket = getUpdatedRelevantReferenceBucket(nextBucket);
112 if (nextBucket == nullptr) {
113 return false;
114 }
115 isReferenced = true;
116 }
117 cint64 bucketIndex = getBucketIndex(index,nextBucket);
118 CReferenceBucketDataPair* referenceBucketPair = &nextBucket->mVec[bucketIndex];
119 bool isBaseBucket = nextBucket->mBucketDepth == 0;
120 if (isBaseBucket) {
121 isReferenced |= referenceBucketPair->mReferenced;
122 if (isReferenced) {
123 return !referenceBucketPair->mUninitialized;
124 } else {
125 return false;
126 }
127 }
128 if (referenceBucketPair->mReferenced) {
129 // bucket is referenced
130 isReferenced = true;
131 // update reference
132 nextBucket = referenceBucketPair->mBucketData.mBucket;
133 nextBucket = getUpdatedRelevantReferenceBucket(nextBucket);
134 referenceBucketPair->mBucketData.mBucket = nextBucket;
135 } else {
136 nextBucket = referenceBucketPair->mBucketData.mBucket;
137 }
138 }
139 return false;
140 }
141
142
143
144 template<class T, cint64 bucket2Size>
145 const T CDynamicReferenceBucketBase<T,bucket2Size>::getData(cint64 index, const T& defaultValue, bool* localFlag) {
146 CDynamicReferenceBucketBase<T,bucket2Size>* nextBucket = this;
147 bool isReferenced = false;
148 while (nextBucket) {
149 if (nextBucket->mVec == nullptr) {
150 nextBucket = getUpdatedRelevantReferenceBucket(nextBucket);
151 if (nextBucket == nullptr) {
152 return defaultValue;
153 }
154 isReferenced = true;
155 }
156 cint64 bucketIndex = getBucketIndex(index,nextBucket);
157 CReferenceBucketDataPair* referenceBucketPair = &nextBucket->mVec[bucketIndex];
158 bool isBaseBucket = nextBucket->mBucketDepth == 0;
159 if (isBaseBucket) {
160 isReferenced |= referenceBucketPair->mReferenced;
161 if (referenceBucketPair->mUninitialized) {
162 return defaultValue;
163 } else {
164 if (localFlag) {
165 *localFlag = !isReferenced;
166 }
167 return referenceBucketPair->mBucketData.mData;
168 }
169 }
170 if (referenceBucketPair->mReferenced) {
171 // bucket is referenced
172 isReferenced = true;
173 // update reference
174 nextBucket = referenceBucketPair->mBucketData.mBucket;
175 nextBucket = getUpdatedRelevantReferenceBucket(nextBucket);
176 referenceBucketPair->mBucketData.mBucket = nextBucket;
177 } else {
178 nextBucket = referenceBucketPair->mBucketData.mBucket;
179 }
180 }
181 return defaultValue;
182 }
183
184
185
186 template<class T, cint64 bucket2Size>
187 bool CDynamicReferenceBucketBase<T,bucket2Size>::hasData(cint64 index) {
188 CDynamicReferenceBucketBase<T,bucket2Size>* nextBucket = this;
189 while (nextBucket) {
190 if (nextBucket->mVec == nullptr) {
191 nextBucket = getUpdatedRelevantReferenceBucket(nextBucket);
192 if (nextBucket == nullptr) {
193 return false;
194 }
195 }
196 cint64 bucketIndex = getBucketIndex(index,nextBucket);
197 CReferenceBucketDataPair* referenceBucketPair = &nextBucket->mVec[bucketIndex];
198 bool isBaseBucket = nextBucket->mBucketDepth == 0;
199 if (isBaseBucket) {
200 return !referenceBucketPair->mUninitialized;
201 }
202 if (referenceBucketPair->mReferenced) {
203 // bucket is referenced
204 // update reference
205 nextBucket = referenceBucketPair->mBucketData.mBucket;
206 nextBucket = getUpdatedRelevantReferenceBucket(nextBucket);
207 referenceBucketPair->mBucketData.mBucket = nextBucket;
208 } else {
209 nextBucket = referenceBucketPair->mBucketData.mBucket;
210 }
211 }
212 return false;
213 }
214
215 template<class T, cint64 bucket2Size>
216 const T CDynamicReferenceBucketBase<T,bucket2Size>::getData(cint64 index, const T& defaultValue) {
217 CDynamicReferenceBucketBase<T,bucket2Size>* nextBucket = this;
218 while (nextBucket) {
219 if (nextBucket->mVec == nullptr) {
220 nextBucket = getUpdatedRelevantReferenceBucket(nextBucket);
221 if (nextBucket == nullptr) {
222 return defaultValue;
223 }
224 }
225 cint64 bucketIndex = getBucketIndex(index,nextBucket);
226 CReferenceBucketDataPair* referenceBucketPair = &nextBucket->mVec[bucketIndex];
227 bool isBaseBucket = nextBucket->mBucketDepth == 0;
228 if (isBaseBucket) {
229 if (referenceBucketPair->mUninitialized) {
230 return defaultValue;
231 } else {
232 return referenceBucketPair->mBucketData.mData;
233 }
234 }
235 if (referenceBucketPair->mReferenced) {
236 // bucket is referenced
237 // update reference
238 nextBucket = referenceBucketPair->mBucketData.mBucket;
239 nextBucket = getUpdatedRelevantReferenceBucket(nextBucket);
240 referenceBucketPair->mBucketData.mBucket = nextBucket;
241 } else {
242 nextBucket = referenceBucketPair->mBucketData.mBucket;
243 }
244 }
245 return defaultValue;
246 }
247
248
249 template<class T, cint64 bucket2Size>
250 cint64 CDynamicReferenceBucketBase<T,bucket2Size>::getBucketIndex(cint64 index) {
251 cint64 bucketIndex = (index & (BUCKETINDEXMASK << mBucketDepth)) >> mBucketDepth;
252 return bucketIndex;
253 }
254
255
256 template<class T, cint64 bucket2Size>
257 cint64 CDynamicReferenceBucketBase<T,bucket2Size>::getBucketIndex(cint64 index, CDynamicReferenceBucketBase<T,bucket2Size>* bucket) {
258 cint64 bucketDepth = bucket->mBucketDepth;
259 cint64 bucketIndex = (index & (BUCKETINDEXMASK << bucketDepth)) >> bucketDepth;
260 return bucketIndex;
261 }
262
263
264 template<class T, cint64 bucket2Size>
265 const T CDynamicReferenceBucketBase<T,bucket2Size>::getLocalData(cint64 index, const T& defaultValue) {
266 CDynamicReferenceBucketBase<T,bucket2Size>* nextBucket = this;
267 while (nextBucket) {
268 if (nextBucket->mVec == nullptr) {
269 return defaultValue;
270 }
271 cint64 bucketIndex = getBucketIndex(index,nextBucket);
272 CReferenceBucketDataPair* referenceBucketPair = &nextBucket->mVec[bucketIndex];
273 if (referenceBucketPair->mReferenced) {
274 return defaultValue;
275 }
276 bool isBaseBucket = nextBucket->mBucketDepth == 0;
277 if (isBaseBucket) {
278 if (!referenceBucketPair->mUninitialized) {
279 return referenceBucketPair->mBucketData.mData;
280 } else {
281 return defaultValue;
282 }
283 }
284 nextBucket = referenceBucketPair->mBucketData.mBucket;
285 }
286 return defaultValue;
287 }
288
289 template<class T, cint64 bucket2Size>
290 const T CDynamicReferenceBucketBase<T,bucket2Size>::getReferenceData(cint64 index, const T& defaultValue) {
291 CDynamicReferenceBucketBase<T,bucket2Size>* nextBucket = this;
292 bool isReferenced = false;
293 while (nextBucket) {
294 if (!isReferenced && nextBucket->mReferenceBucket) {
295 nextBucket = nextBucket->mReferenceBucket;
296 isReferenced = true;
297 }
298 if (nextBucket->mVec == nullptr) {
299 nextBucket = getUpdatedRelevantReferenceBucket(nextBucket);
300 if (nextBucket == nullptr) {
301 return defaultValue;
302 }
303 isReferenced = true;
304 }
305 cint64 bucketIndex = getBucketIndex(index,nextBucket);
306 CReferenceBucketDataPair* referenceBucketPair = &nextBucket->mVec[bucketIndex];
307 bool isBaseBucket = nextBucket->mBucketDepth == 0;
308 if (isBaseBucket) {
309 isReferenced |= referenceBucketPair->mReferenced;
310 if (isReferenced && !referenceBucketPair->mUninitialized) {
311 return referenceBucketPair->mBucketData.mData;
312 } else {
313 return defaultValue;
314 }
315 }
316 if (referenceBucketPair->mReferenced) {
317 // bucket is referenced
318 isReferenced = true;
319 // update reference
320 nextBucket = referenceBucketPair->mBucketData.mBucket;
321 nextBucket = getUpdatedRelevantReferenceBucket(nextBucket);
322 referenceBucketPair->mBucketData.mBucket = nextBucket;
323 } else {
324 nextBucket = referenceBucketPair->mBucketData.mBucket;
325 }
326 }
327 return defaultValue;
328 }
329
330
331 template<class T, cint64 bucket2Size>
332 void CDynamicReferenceBucketBase<T,bucket2Size>::setLocalData(cint64 index, const T& data) {
333 CDynamicReferenceBucketBase<T,bucket2Size>* nextBucket = this;
334 while (nextBucket) {
335 bool isBaseBucket = nextBucket->mBucketDepth == 0;
336 if (nextBucket->mVec == nullptr) {
337 CDynamicReferenceBucketBase<T,bucket2Size>* refBucket = nullptr;
338 refBucket = getUpdatedRelevantReferenceBucket(nextBucket);
339 nextBucket->mVec = createBucketVector(refBucket,isBaseBucket);
340 }
341 cint64 bucketIndex = getBucketIndex(index,nextBucket);
342 CReferenceBucketDataPair* referenceBucketPair = &nextBucket->mVec[bucketIndex];
343 if (isBaseBucket) {
344 referenceBucketPair->mBucketData.mData = data;
345 referenceBucketPair->mReferenced = false;
346 referenceBucketPair->mUninitialized = false;
347 return;
348 }
349 if (referenceBucketPair->mReferenced || !referenceBucketPair->mBucketData.mBucket) {
350 nextBucket = createBucket(nextBucket->mBucketDepth-(bucket2Size+1),referenceBucketPair);
351 }
352 CDynamicReferenceBucketBase<T,bucket2Size>* possNextBucket = referenceBucketPair->mBucketData.mBucket;
353 if (!possNextBucket) {
354 possNextBucket = createBucket(nextBucket->mBucketDepth-bucket2Size,referenceBucketPair);
355 }
356 nextBucket = possNextBucket;
357 }
358 }
359
360 template<class T, cint64 bucket2Size>
361 void CDynamicReferenceBucketBase<T,bucket2Size>::setData(cint64 index, const T& data) {
362 setLocalData(index,data);
363 }
364
365
366 template<class T, cint64 bucket2Size>
367 void CDynamicReferenceBucketBase<T,bucket2Size>::initBucket(cint64 bucketDepth, CDynamicReferenceBucketBase<T,bucket2Size>* referenceBucket) {
368 mBucketDepth = bucketDepth;
369 mReferenceBucket = referenceBucket;
370 mVec = nullptr;
371 }
372
373
374 template<class T, cint64 bucket2Size>
375 CDynamicReferenceBucketBase<T,bucket2Size>* CDynamicReferenceBucketBase<T,bucket2Size>::createBucket(cint64 bucketDepth, CReferenceBucketDataPair* bucketPos) {
376 CDynamicReferenceBucketBase<T,bucket2Size>* refBucket = nullptr;
377 if (bucketPos && bucketPos->mReferenced) {
378 refBucket = bucketPos->mBucketData.mBucket;
379 }
380 CDynamicReferenceBucketBase<T,bucket2Size>* bucket = CObjectParameterizingAllocator< CDynamicReferenceBucketBase<T,bucket2Size>,CContext* >::allocateAndConstructAndParameterize(mMemMan,mContext);
381 bucket->initBucket(bucketDepth,refBucket);
382 bucketPos->mReferenced = false;
383 bucketPos->mUninitialized = false;
384 bucketPos->mBucketData.mBucket = bucket;
385 return bucket;
386 }
387
388
389
390
391
392 }; // end namespace Container
393
394 }; // end namespace Utilities
395
396 }; // end namespace Konclude
397
398 #endif // KONCLUDE_UTILITIES_CONTAINER_CDYNAMICREFERENCEBUCKET_CPP