GCC Code Coverage Report

Directory: ./
File: Geometry/Tools/hashtable.cpp
Date: 2024-04-14 07:32:34
Exec Total Coverage
Lines: 88 112 78.6%
Branches: 78 136 57.4%
Line Branch Exec Source
1 // ______ ______ _ _ _____ ______
2 // | ____| ____| | (_)/ ____| | ____|
3 // | |__ | |__ | | _| (___ ___| |__
4 // | __| | __| | | | |\___ \ / __| __|
5 // | | | |____| |____| |____) | (__| |____
6 // |_| |______|______|_|_____/ \___|______|
7 // Finite Elements for Life Sciences and Engineering
8 //
9 // License: LGL2.1 License
10 // FELiScE default license: LICENSE in root folder
11 //
12 // Main authors:
13 //
14
15 // System includes
16 #include <algorithm>
17
18 // External includes
19
20 // Project includes
21 #include "Core/felisceParam.hpp"
22 #include "Geometry/Tools/hashtable.hpp"
23
24 namespace felisce
25 {
26
27 17 HashTable::HashTable(GeometricMeshRegion* mesh, std::size_t size, BoundingBox* bbox) :
28 17 m_mesh(mesh), m_bbox(bbox), m_size(size)
29 {
30
31
3/4
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 15 times.
✓ Branch 4 taken 2 times.
 17 if ( FelisceParam::verbose() > 3 )
32
2/4
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 15 times.
✗ Branch 5 not taken.
 15 std::cout << "HashTable: initialization in progress." << std::endl;
33
34 // Set maximum "key" value : "key" ranges form 0 to m_size^dim-1 included
35 17 m_maxKey = static_cast<std::size_t>(std::pow(m_size,mesh->spatialDim()));
36
37 // Memory allocation
38
2/4
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
✓ Branch 4 taken 17 times.
✗ Branch 5 not taken.
 17 m_head = new felInt[ m_maxKey ];
39
2/2
✓ Branch 0 taken 134784 times.
✓ Branch 1 taken 17 times.
 134801 for(std::size_t i = 0; i < m_maxKey; ++i)
40 134784 m_head[i] = -1;
41
42
2/4
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 17 times.
✗ Branch 6 not taken.
 17 m_link = new felInt[m_mesh->numPoints()];
43
2/2
✓ Branch 1 taken 4258 times.
✓ Branch 2 taken 17 times.
 4275 for(felInt i = 0; i < m_mesh->numPoints(); ++i)
44 4258 m_link[i] = -1;
45
46 // Insert vertices in hashtable
47 Point pnt;
48 felInt key;
49 17 std::array<felInt,3> index{0, 0, 0};
50 17 const Point delta = m_bbox->delta();
51 17 const Point min = m_bbox->min();
52
53
2/2
✓ Branch 1 taken 4258 times.
✓ Branch 2 taken 17 times.
 4275 for (felInt k = 0; k < m_mesh->numPoints(); ++k) {
54
55 // Scale point and compute hash key
56
1/2
✓ Branch 2 taken 4258 times.
✗ Branch 3 not taken.
 4258 pnt = m_size * (m_mesh->listPoint(k) - min);
57
2/2
✓ Branch 1 taken 8572 times.
✓ Branch 2 taken 4258 times.
 12830 for (int i = 0; i < m_mesh->numCoor(); ++i){
58 8572 pnt[i] /= delta[i];
59
60 8572 index[i] = std::max( 0, static_cast<felInt>( pnt[i] - EPS * delta[i] ) );
61 }
62 4258 key = ( index[2] * m_size + index[1] ) * m_size + index[0];
63
64
1/2
✓ Branch 0 taken 4258 times.
✗ Branch 1 not taken.
 4258 if ( m_head[key] < 0 ) {
65 4258 m_head[key] = k;
66 } else {
67 ✗ m_link[k] = m_head[key];
68 ✗ m_head[key] = k;
69 }
70 }
71
72 // Fill m_seed and m_type
73 17 int numPntElm = 0;
74 ElementType eltType;
75 17 std::vector<felInt> elem;
76
77
2/4
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 17 times.
✗ Branch 6 not taken.
 17 m_seed = new felInt[m_mesh->numPoints()];
78
2/4
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 17 times.
✗ Branch 6 not taken.
 17 m_type = new ElementType[m_mesh->numPoints()];
79
80 // Loop over element type
81
2/2
✓ Branch 2 taken 17 times.
✓ Branch 3 taken 17 times.
 34 for (std::size_t i = 0; i < m_mesh->bagElementTypeDomain().size(); ++i) {
82 17 eltType = m_mesh->bagElementTypeDomain()[i];
83 17 numPntElm = m_mesh->numPtsPerElement(eltType);
84
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 elem.resize(numPntElm, 0);
85
86 // Initialize arrays
87
2/2
✓ Branch 1 taken 7884 times.
✓ Branch 2 taken 17 times.
 7901 for (felInt k = 0; k < m_mesh->numElements(eltType); ++k) {
88
89 // get element vertices
90
1/2
✓ Branch 1 taken 7884 times.
✗ Branch 2 not taken.
 7884 m_mesh->getOneElement(eltType, k, elem, 0);
91
92 // set seed for every vertex
93
2/2
✓ Branch 0 taken 23690 times.
✓ Branch 1 taken 7884 times.
 31574 for (int iPnt = 0; iPnt < numPntElm; ++iPnt) {
94 23690 m_type[ elem[iPnt] ] = eltType;
95 23690 m_seed[ elem[iPnt] ] = k;
96 }
97 }
98 }
99
100
3/4
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 15 times.
✓ Branch 4 taken 2 times.
 17 if ( FelisceParam::verbose() > 3 )
101
2/4
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 15 times.
✗ Branch 5 not taken.
 15 std::cout << "HashTable: initialization completed." << std::endl;
102 17 }
103
104 /***********************************************************************************/
105 /***********************************************************************************/
106
107 17 HashTable::~HashTable()
108 {
109
1/2
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
 17 if( m_head ) {
110
1/2
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
 17 delete [] m_head;
111 17 m_head = nullptr;
112 }
113
114
1/2
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
 17 if( m_link ) {
115
1/2
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
 17 delete [] m_link;
116 17 m_link = nullptr;
117 }
118
119
1/2
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
 17 if ( m_seed ) {
120
1/2
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
 17 delete [] m_seed;
121 17 m_seed = nullptr;
122 }
123
124
1/2
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
 17 if ( m_type ) {
125
1/2
✓ Branch 0 taken 17 times.
✗ Branch 1 not taken.
 17 delete [] m_type;
126 17 m_type = nullptr;
127 }
128 17 }
129
130 /***********************************************************************************/
131 /***********************************************************************************/
132
133 1788 HashTable::seedElement HashTable::findSeed(Point pntIn) const
134 {
135
1/2
✓ Branch 2 taken 1788 times.
✗ Branch 3 not taken.
 1788 const felInt iVer = closestVertex(pntIn);
136
137 1788 return HashTable::seedElement{m_type[iVer], m_seed[iVer]};
138 }
139
140 /***********************************************************************************/
141 /***********************************************************************************/
142
143 1788 felInt HashTable::closestVertex(Point pntIn) const
144 {
145 Point pnt;
146 felInt iPrv, iNxt;
147 double dPrv, dNxt;
148 1788 std::array<felInt,3> index{0, 0, 0};
149
150 1788 Point delta = m_bbox->delta();
151
152 // Scale point
153
1/2
✓ Branch 2 taken 1788 times.
✗ Branch 3 not taken.
 1788 pntIn = m_size * (pntIn - m_bbox->min());
154
2/2
✓ Branch 1 taken 3595 times.
✓ Branch 2 taken 1788 times.
 5383 for (int i = 0; i < m_mesh->numCoor(); ++i) {
155 3595 pntIn[i] /= delta[i];
156
157 3595 index[i] = std::max( 0, static_cast<felInt>( pntIn[i] - EPS * delta[i] ) );
158 }
159 1788 felInt key = ( index[2] * m_size + index[1] ) * m_size + index[0];
160
161 // The provided point must be inside the bounding box
162
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 1788 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 1788 FEL_ASSERT( key < static_cast<felInt>(m_maxKey) );
163
164 // Check current cell
165
2/2
✓ Branch 0 taken 349 times.
✓ Branch 1 taken 1439 times.
 1788 if ( m_head[key] >= 0 ) {
166 349 iPrv = m_head[key];
167
168 // Get point
169 349 pnt = m_mesh->listPoint(iPrv);
170
171 // Compute distance^2
172 349 dPrv = std::pow( pnt.dist(pntIn), 2);
173
174 // All the points with the same hash key
175 349 iNxt = iPrv;
176
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 349 times.
 349 while ( m_link[iNxt] >= 0 ) {
177 ✗ iNxt = m_link[iNxt];
178
179 // Get point
180 ✗ pnt = m_mesh->listPoint(iNxt);
181
182 // Compute distance^2
183 ✗ dNxt = std::pow( pnt.dist(pntIn), 2);
184
185 // If Nxt closer than Prv -> update
186 ✗ if ( dNxt < dPrv ) {
187 ✗ iPrv = iNxt;
188 ✗ dPrv = dNxt;
189 }
190 }
191
192
3/4
✓ Branch 1 taken 349 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 19 times.
✓ Branch 4 taken 330 times.
 349 if ( FelisceParam::verbose() > 3 )
193
4/8
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 19 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 19 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 19 times.
✗ Branch 11 not taken.
 19 std::cout << "HashTable: germ vertex is " << iPrv << "." << std::endl;
194
195 349 return iPrv;
196 }
197
198 // if the previous tests have failed, check into the neighbors
199 1439 std::array<std::array<felInt, 2>,3> indexMinMax = {{ {{0, 0}}, {{0, 0}}, {{0, 0}} }};
200 1439 felInt d = 1;
201 do {
202
2/2
✓ Branch 1 taken 5732 times.
✓ Branch 2 taken 2854 times.
 8586 for (int i = 0; i < m_mesh->numCoor(); ++i)
203 5732 indexMinMax[i] = { std::max( 0, index[i] - d ), std::min( index[i] + d, m_size-1 ) };
204
205 // Windows of neighbour nodes
206
2/2
✓ Branch 4 taken 2886 times.
✓ Branch 5 taken 1415 times.
 4301 for (felInt k = indexMinMax[2][0]; k <= indexMinMax[2][1]; ++k)
207
2/2
✓ Branch 4 taken 8288 times.
✓ Branch 5 taken 1447 times.
 9735 for (felInt j = indexMinMax[1][0]; j <= indexMinMax[1][1]; ++j)
208
2/2
✓ Branch 4 taken 27813 times.
✓ Branch 5 taken 6849 times.
 34662 for (felInt i = indexMinMax[0][0]; i <= indexMinMax[0][1]; ++i) {
209
210 // Get neighbor key
211 27813 key = ( k * m_size + j ) * m_size + i;
212
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 27813 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 27813 FEL_ASSERT( key < static_cast<felInt>(m_maxKey) );
213
214 // Check neighbor cell
215 27813 iPrv = m_head[key];
216
2/2
✓ Branch 0 taken 26374 times.
✓ Branch 1 taken 1439 times.
 27813 if ( iPrv < 0 ) continue;
217
218
3/4
✓ Branch 1 taken 1439 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 19 times.
✓ Branch 4 taken 1420 times.
 1439 if ( FelisceParam::verbose() > 3 )
219
4/8
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 19 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 19 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 19 times.
✗ Branch 11 not taken.
 19 std::cout << "HashTable: germ vertex is " << iPrv << "." << std::endl;
220
221 1439 return iPrv;
222 }
223
1/2
✓ Branch 0 taken 1415 times.
✗ Branch 1 not taken.
 1415 } while ( ++d < m_size );
224
225 ✗ FEL_ERROR("HashTable: cannot find closest vertex!");
226
227 ✗ return -1;
228 }
229
230 /***********************************************************************************/
231 /***********************************************************************************/
232
233 ✗ void HashTable::print()
234 {
235 felInt iPnt;
236
237 ✗ for (std::size_t key = 0; key < m_maxKey; ++key) {
238
239 // Get first hashed point
240 ✗ iPnt = m_head[key];
241 ✗ if ( iPnt < 0 )
242 ✗ continue;
243
244 // Print all the points with the same hash key
245 ✗ std::cout <<"Key = " << key << std::endl;
246 ✗ std::cout <<"List of points: " << iPnt;
247
248 ✗ iPnt = m_link[iPnt];
249 ✗ while ( iPnt >= 0 ) {
250 ✗ std::cout << " " << iPnt;
251
252 // Get next point
253 ✗ iPnt = m_link[iPnt];
254 }
255 ✗ std::cout << std::endl << std::endl;
256 }
257
258 ✗ for (felInt k = 0; k < m_mesh->numPoints(); ++k)
259 ✗ std::cout <<"Seed of vertex " << k << " is element: " << GeometricMeshRegion::eltEnumToFelNameGeoEle[m_type[k]].first << " " << m_seed[k] << std::endl;
260 }
261
262 }
263
264