Debian Codegraph @

3rdparty/mshmet/src/sourceslib/hash.c

raw
1 #include "mshmet.h"
2
3 #define KA 31
4 #define KB 57
5 #define KC 79
6
7 #define KTA 7
8 #define KTB 11
9
10 static int idirt[7] = {0,1,2,3,0,1,2};
11
12
13 /* hash mesh edges */
14 pHash hashEdge_3d(pMesh mesh) {
15 pTetra pt;
16 hedge *ph;
17 pHash hash;
18 int i,j,k,ia,ib,mins,maxs,key;
19
20 /* adjust hash table params */
21 hash = malloc(1*sizeof(Hash));
22 assert(hash);
23 hash->item = (hedge*)calloc(9*mesh->np,sizeof(hedge));
24 assert(hash->item);
25 hash->size = mesh->np;
26 hash->nhmax = 9*mesh->np - 1;
27 hash->hnxt = mesh->np;
28 memset(hash->item,0,hash->nhmax*sizeof(hedge));
29 for (k=mesh->np; k<hash->nhmax; k++)
30 hash->item[k].nxt = k+1;
31
32 /* scan tetra edges */
33 for (k=1; k<=mesh->ne; k++) {
34 pt = &mesh->tetra[k];
35 for (i=0; i<4; i++) {
36 ia = pt->v[i];
37 for (j=i+1; j<4; j++) {
38 ib = pt->v[j];
39 mins = ia;
40 maxs = ib;
41 if ( ia > ib ) {
42 mins = ib;
43 maxs = ia;
44 }
45 key = (KA*mins + KB*maxs) % hash->size;
46 ph = &hash->item[key];
47
48 if ( !ph->min ) {
49 ph->min = mins;
50 ph->max = maxs;
51 ph->nxt = 0;
52 }
53 else {
54 while ( ph->nxt && ph->nxt < hash->nhmax ) {
55 if ( ph->min == mins && ph->max == maxs ) break;
56 ph = &hash->item[ph->nxt];
57 }
58 if ( ph->min == mins && ph->max == maxs ) continue;
59 ph->nxt = hash->hnxt;
60 ph = &hash->item[hash->hnxt];
61 ph->min = mins;
62 ph->max = maxs;
63 ph->nxt = 0;
64 ++hash->hnxt;
65 assert(hash->hnxt < hash->nhmax );
66 }
67 }
68 }
69 }
70
71 return(hash);
72 }
73
74
75 /* hash mesh edges */
76 pHash hashEdge_2d(pMesh mesh) {
77 pTria pt;
78 hedge *ph;
79 pHash hash;
80 int i,j,k,ia,ib,mins,maxs,key;
81
82 /* adjust hash table params */
83 hash = malloc(1*sizeof(Hash));
84 assert(hash);
85 hash->item = (hedge*)calloc(4*mesh->np,sizeof(hedge));
86 assert(hash->item);
87 hash->size = mesh->np;
88 hash->nhmax = 4*mesh->np - 1;
89 hash->hnxt = mesh->np;
90 memset(hash->item,0,hash->nhmax*sizeof(hedge));
91 for (k=mesh->np; k<hash->nhmax; k++)
92 hash->item[k].nxt = k+1;
93
94 /* scan tetra edges */
95 for (k=1; k<=mesh->nt; k++) {
96 pt = &mesh->tria[k];
97 for (i=0; i<3; i++) {
98 ia = pt->v[i];
99 for (j=i+1; j<3; j++) {
100 ib = pt->v[j];
101 mins = ia;
102 maxs = ib;
103 if ( ia > ib ) {
104 mins = ib;
105 maxs = ia;
106 }
107 key = (KA*mins + KB*maxs) % hash->size;
108 ph = &hash->item[key];
109
110 if ( !ph->min ) {
111 ph->min = mins;
112 ph->max = maxs;
113 ph->nxt = 0;
114 }
115 else {
116 while ( ph->nxt && ph->nxt < hash->nhmax ) {
117 if ( ph->min == mins && ph->max == maxs ) break;
118 ph = &hash->item[ph->nxt];
119 }
120 if ( ph->min == mins && ph->max == maxs ) continue;
121 ph->nxt = hash->hnxt;
122 ph = &hash->item[hash->hnxt];
123 ph->min = mins;
124 ph->max = maxs;
125 ph->nxt = 0;
126 ++hash->hnxt;
127 assert(hash->hnxt < hash->nhmax );
128 }
129 }
130 }
131 }
132
133 return(hash);
134 }
135
136
137 int hashel_3d(pMesh mesh) {
138 pTetra pt,pt1;
139 pPoint ppt;
140 int k,kk,pp,l,ll,mins,mins1,maxs,maxs1,sum,sum1,iadr;
141 int *hcode,*link,*adja,inival,hsize;
142 unsigned char i,ii,i1,i2,i3;
143 unsigned int key;
144
145 /* memory alloc */
146 hcode = (int*)M_calloc(mesh->ne+1,sizeof(int),"hash");
147 assert(hcode);
148 link = mesh->adja;
149 hsize = mesh->ne;
150
151 /* init */
152 inival = 2147483647;
153 for (k=0; k<=mesh->ne; k++)
154 hcode[k] = -inival;
155
156 /* build hash table */
157 for (k=1; k<=mesh->ne; k++) {
158 pt = &mesh->tetra[k];
159 if ( !pt->v[0] ) continue;
160 for (i=0; i<4; i++) {
161 i1 = idirt[i+1];
162 i2 = idirt[i+2];
163 i3 = idirt[i+3];
164 mins = MS_MIN(pt->v[i1],pt->v[i2]);
165 mins = MS_MIN(mins,pt->v[i3]);
166 maxs = MS_MAX(pt->v[i1],pt->v[i2]);
167 maxs = MS_MAX(maxs,pt->v[i3]);
168
169 /* compute key */
170 sum = pt->v[i1] + pt->v[i2] + pt->v[i3];
171 key = KA*mins + KB*maxs + KC*sum;
172 key = key % hsize + 1;
173
174 /* insert */
175 iadr = 4*(k-1) + i+1;
176 link[iadr] = hcode[key];
177 hcode[key] = -iadr;
178 }
179 }
180
181 /* set adjacency */
182 for (l=4*mesh->ne; l>0; l--) {
183 if ( link[l] >= 0 ) continue;
184 k = (l-1) / 4 + 1;
185 i = (l-1) % 4;
186 i1 = idirt[i+1];
187 i2 = idirt[i+2];
188 i3 = idirt[i+3];
189 pt = &mesh->tetra[k];
190
191 sum = pt->v[i1] + pt->v[i2] + pt->v[i3];
192 mins = MS_MIN(pt->v[i1],pt->v[i2]);
193 mins = MS_MIN(mins,pt->v[i3]);
194 maxs = MS_MAX(pt->v[i1],pt->v[i2]);
195 maxs = MS_MAX(maxs,pt->v[i3]);
196
197 /* accross link */
198 ll = -link[l];
199 pp = 0;
200 link[l] = 0;
201 while ( ll != inival ) {
202 kk = (ll-1) / 4 + 1;
203 ii = (ll-1) % 4;
204 i1 = idirt[ii+1];
205 i2 = idirt[ii+2];
206 i3 = idirt[ii+3];
207 pt1 = &mesh->tetra[kk];
208 sum1 = pt1->v[i1] + pt1->v[i2] + pt1->v[i3];
209 if ( sum1 == sum ) {
210 mins1 = MS_MIN(pt1->v[i1],pt1->v[i2]);
211 mins1 = MS_MIN(mins1,pt1->v[i3]);
212 if ( mins1 == mins ) {
213 maxs1 = MS_MAX(pt1->v[i1],pt1->v[i2]);
214 maxs1 = MS_MAX(maxs1,pt1->v[i3]);
215 if ( maxs1 == maxs ) {
216 /* adjacent found */
217 if ( pp != 0 ) link[pp] = link[ll];
218 link[l] = 4*kk + ii;
219 link[ll]= 4*k + i;
220 break;
221 }
222 }
223 }
224 pp = ll;
225 ll = -link[ll];
226 }
227 }
228 M_free(hcode);
229
230 /* set seed */
231 for (k=1; k<=mesh->ne; k++) {
232 pt = &mesh->tetra[k];
233 iadr = 4*(k-1)+1;
234 adja = &mesh->adja[iadr];
235 if ( !adja[0] ) mesh->point[pt->v[1]].s = k;
236 if ( !adja[1] ) mesh->point[pt->v[2]].s = k;
237 if ( !adja[2] ) mesh->point[pt->v[3]].s = k;
238 if ( !adja[3] ) mesh->point[pt->v[0]].s = k;
239 }
240
241 for (k=1; k<=mesh->ne; k++) {
242 pt = &mesh->tetra[k];
243 for (i=0; i<4; i++) {
244 ppt = &mesh->point[pt->v[i]];
245 if ( !ppt->s ) ppt->s = k;
246 }
247 }
248
249 return(1);
250 }
251
252
253 int hashel_2d(pMesh mesh) {
254 pTria pt,pt1;
255 int k,kk,pp,l,ll,mins,mins1,maxs,maxs1,iadr;
256 int *hcode,*link,*adj,inival,hsize,iad;
257 unsigned char *hvoy,i,ii,i1,i2;
258 unsigned int key;
259
260 if ( !mesh->nt ) return(0);
261
262 /* memory alloc */
263 hcode = (int*)M_calloc(mesh->nt+1,sizeof(int),"hash");
264 assert(hcode);
265 link = mesh->adja;
266 hsize = mesh->nt;
267 hvoy = (unsigned char*)hcode;
268
269 /* init */
270 inival = 2147483647;
271 for (k=0; k<=mesh->nt; k++)
272 hcode[k] = -inival;
273
274 /* build hash table */
275 for (k=1; k<=mesh->nt; k++) {
276 pt = &mesh->tria[k];
277 if ( !pt->v[0] ) continue;
278 for (i=0; i<3; i++) {
279 i1 = idir[i+1];
280 i2 = idir[i+2];
281 if ( pt->v[i1] < pt->v[i2] ) {
282 mins = pt->v[i1];
283 maxs = pt->v[i2];
284 }
285 else {
286 mins = pt->v[i2];
287 maxs = pt->v[i1];
288 }
289
290 /* compute key */
291 key = KTA*mins + KTB*maxs;
292 key = key % hsize + 1;
293
294 /* insert */
295 iadr = 3*(k-1) + i+1;
296 link[iadr] = hcode[key];
297 hcode[key] = -iadr;
298 }
299 }
300
301 /* set adjacency */
302 for (l=3*mesh->nt; l>0; l--) {
303 if ( link[l] >= 0 ) continue;
304 k = (l-1) / 3 + 1;
305 i = (l-1) % 3;
306 i1 = idir[i+1];
307 i2 = idir[i+2];
308 pt = &mesh->tria[k];
309
310 mins = MS_MIN(pt->v[i1],pt->v[i2]);
311 maxs = MS_MAX(pt->v[i1],pt->v[i2]);
312
313 /* accross link */
314 ll = -link[l];
315 pp = 0;
316 link[l] = 0;
317 hvoy[l] = 0;
318 while ( ll != inival ) {
319 kk = (ll-1) / 3 + 1;
320 ii = (ll-1) % 3;
321 i1 = idir[ii+1];
322 i2 = idir[ii+2];
323 pt1 = &mesh->tria[kk];
324 if ( pt1->v[i1] < pt1->v[i2] ) {
325 mins1 = pt1->v[i1];
326 maxs1 = pt1->v[i2];
327 }
328 else {
329 mins1 = pt1->v[i2];
330 maxs1 = pt1->v[i1];
331 }
332
333 if ( mins1 == mins && maxs1 == maxs ) {
334 /* adjacent found */
335 if ( pp != 0 ) link[pp] = link[ll];
336 link[l] = 3*kk + ii;
337 link[ll]= 3*k + i;
338 break;
339 }
340 pp = ll;
341 ll = -link[ll];
342 }
343 }
344 M_free(hcode);
345
346 for (k=1; k<=mesh->nt; k++) {
347 pt = &mesh->tria[k];
348 iad = 3*(k-1)+1;
349 adj = &mesh->adja[iad];
350 if ( !adj[0] ) mesh->point[pt->v[1]].s = k;
351 if ( !adj[1] ) mesh->point[pt->v[2]].s = k;
352 if ( !adj[2] ) mesh->point[pt->v[0]].s = k;
353 }
354
355 return(1);
356 }
357