Branch data Line data Source code
1 : : /* do not edit automatically generated by mc from Sets. */
2 : : /* Sets.mod provides a dynamic set module.
3 : :
4 : : Copyright (C) 2009-2024 Free Software Foundation, Inc.
5 : : Contributed by Gaius Mulley <gaius.mulley@southwales.ac.uk>.
6 : :
7 : : This file is part of GNU Modula-2.
8 : :
9 : : GNU Modula-2 is free software; you can redistribute it and/or modify
10 : : it under the terms of the GNU General Public License as published by
11 : : the Free Software Foundation; either version 3, or (at your option)
12 : : any later version.
13 : :
14 : : GNU Modula-2 is distributed in the hope that it will be useful, but
15 : : WITHOUT ANY WARRANTY; without even the implied warranty of
16 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 : : General Public License for more details.
18 : :
19 : : You should have received a copy of the GNU General Public License
20 : : along with GNU Modula-2; see the file COPYING3. If not see
21 : : <http://www.gnu.org/licenses/>. */
22 : :
23 : : #include "config.h"
24 : : #include "system.h"
25 : : #include <stdbool.h>
26 : : # if !defined (PROC_D)
27 : : # define PROC_D
28 : : typedef void (*PROC_t) (void);
29 : : typedef struct { PROC_t proc; } PROC;
30 : : # endif
31 : :
32 : : # if !defined (TRUE)
33 : : # define TRUE (1==1)
34 : : # endif
35 : :
36 : : # if !defined (FALSE)
37 : : # define FALSE (1==0)
38 : : # endif
39 : :
40 : : # include "GStorage.h"
41 : : #if defined(__cplusplus)
42 : : # undef NULL
43 : : # define NULL 0
44 : : #endif
45 : : #define _Sets_H
46 : : #define _Sets_C
47 : :
48 : : # include "GSYSTEM.h"
49 : : # include "GSymbolTable.h"
50 : : # include "GM2Error.h"
51 : : # include "GStorage.h"
52 : : # include "Glibc.h"
53 : : # include "GM2Printf.h"
54 : : # include "GAssertion.h"
55 : :
56 : : # define BitsetSize sizeof (unsigned int )
57 : : # define MaxBitset (31)
58 : : # define BitsPerByte (((MaxBitset+1)) / BitsetSize)
59 : : # define Debugging false
60 : : typedef unsigned char *Sets_PtrToByte;
61 : :
62 : : typedef struct Sets__T1_r Sets__T1;
63 : :
64 : : typedef Sets__T1 *Sets_Set;
65 : :
66 : : typedef unsigned int *Sets_PtrToBitset;
67 : :
68 : : struct Sets__T1_r {
69 : : unsigned int init;
70 : : unsigned int start;
71 : : unsigned int end;
72 : : Sets_PtrToBitset pb;
73 : : unsigned int bytes;
74 : : unsigned int elements;
75 : : };
76 : :
77 : :
78 : : /*
79 : : InitSet - initializes and returns a set. The set will
80 : : never contain an element less than, low.
81 : : */
82 : :
83 : : extern "C" Sets_Set Sets_InitSet (unsigned int low);
84 : :
85 : : /*
86 : : KillSet - deallocates Set, s.
87 : : */
88 : :
89 : : extern "C" Sets_Set Sets_KillSet (Sets_Set s);
90 : :
91 : : /*
92 : : DuplicateSet - returns a new duplicated set.
93 : : */
94 : :
95 : : extern "C" Sets_Set Sets_DuplicateSet (Sets_Set s);
96 : :
97 : : /*
98 : : ForeachElementInSetDo - for each element e in, s, call, p(e).
99 : : */
100 : :
101 : : extern "C" void Sets_ForeachElementInSetDo (Sets_Set s, SymbolKey_PerformOperation p);
102 : :
103 : : /*
104 : : IsElementInSet - returns TRUE if element, i, is in set, s.
105 : : */
106 : :
107 : : extern "C" bool Sets_IsElementInSet (Sets_Set s, unsigned int i);
108 : :
109 : : /*
110 : : NoOfElementsInSet - returns the number of elements in a set, s.
111 : : */
112 : :
113 : : extern "C" unsigned int Sets_NoOfElementsInSet (Sets_Set s);
114 : :
115 : : /*
116 : : ExcludeElementFromSet - excludes element, i, from set, s.
117 : : */
118 : :
119 : : extern "C" void Sets_ExcludeElementFromSet (Sets_Set s, unsigned int i);
120 : :
121 : : /*
122 : : IncludeElementIntoSet - includes element, i, into set, s.
123 : : */
124 : :
125 : : extern "C" void Sets_IncludeElementIntoSet (Sets_Set s, unsigned int i);
126 : :
127 : : /*
128 : : EqualSet - return TRUE if left = right.
129 : : */
130 : :
131 : : extern "C" bool Sets_EqualSet (Sets_Set left, Sets_Set right);
132 : :
133 : : /*
134 : : growSet -
135 : : */
136 : :
137 : : static void growSet (unsigned int i, unsigned int bytes);
138 : :
139 : : /*
140 : : checkRange - checks to make sure, i, is within range and
141 : : it will extend the set bitmap if required.
142 : : */
143 : :
144 : : static void checkRange (Sets_Set s, unsigned int i);
145 : :
146 : : /*
147 : : findPos - returns a pointer to the BITSET which will contain, i.
148 : : */
149 : :
150 : : static Sets_PtrToBitset findPos (Sets_PtrToBitset pb, unsigned int i);
151 : :
152 : :
153 : : /*
154 : : growSet -
155 : : */
156 : :
157 : 0 : static void growSet (unsigned int i, unsigned int bytes)
158 : : {
159 : 0 : M2Printf_printf2 ((const char *) "i = %d, bytes = %d\\n", 21, (const unsigned char *) &i, (sizeof (i)-1), (const unsigned char *) &bytes, (sizeof (bytes)-1));
160 : 0 : }
161 : :
162 : :
163 : : /*
164 : : checkRange - checks to make sure, i, is within range and
165 : : it will extend the set bitmap if required.
166 : : */
167 : :
168 : 513890731 : static void checkRange (Sets_Set s, unsigned int i)
169 : : {
170 : 513890731 : unsigned int bits;
171 : 513890731 : unsigned int o;
172 : 513890731 : unsigned int j;
173 : 513890731 : Sets_PtrToBitset b;
174 : 513890731 : Sets_PtrToByte v;
175 : :
176 : 513890731 : if (i < s->init)
177 : : {
178 : 0 : M2Error_InternalError ((const char *) "set element is too low and out of bounds", 40);
179 : : }
180 : 513890731 : else if (i > (SymbolTable_FinalSymbol ()))
181 : : {
182 : : /* avoid dangling else. */
183 : 0 : M2Error_InternalError ((const char *) "set element is too high and out of bounds", 41);
184 : : }
185 : : else
186 : : {
187 : : /* avoid dangling else. */
188 : 513890731 : j = s->bytes*BitsPerByte;
189 : 513890731 : if (i >= j)
190 : : {
191 : 15236643 : o = s->bytes;
192 : 15236643 : if (Debugging)
193 : : {
194 : : M2Printf_printf2 ((const char *) "previous bitset size %d bytes, need %d bits\\n", 45, (const unsigned char *) &o, (sizeof (o)-1), (const unsigned char *) &i, (sizeof (i)-1));
195 : : }
196 : 15236643 : if (s->bytes == 0)
197 : : {
198 : 13160629 : s->bytes = BitsetSize;
199 : : }
200 : 67267950 : while (i >= (s->bytes*BitsPerByte))
201 : : {
202 : 52031307 : if (Debugging)
203 : : {
204 : : growSet (i, s->bytes);
205 : : }
206 : 52031307 : s->bytes = s->bytes*2;
207 : : }
208 : 15236643 : Storage_ALLOCATE (reinterpret_cast<void **> (&b), s->bytes);
209 : 15236643 : if (Debugging)
210 : : {
211 : : bits = s->bytes*8;
212 : : M2Printf_printf2 ((const char *) "new allocated bitset size %d bytes, holds %d bits\\n", 51, (const unsigned char *) &s->bytes, (sizeof (s->bytes)-1), (const unsigned char *) &bits, (sizeof (bits)-1));
213 : : if (i > bits)
214 : : {
215 : : M2Error_InternalError ((const char *) "buffer is too small", 19);
216 : : }
217 : : }
218 : : /* a := memset(b, 0, bytes) ; */
219 : 15236643 : v = (Sets_PtrToByte) (b);
220 : 15236643 : v += o;
221 : 15236643 : Assertion_Assert ((libc_memset (reinterpret_cast<void *> (v), 0, static_cast<size_t> (s->bytes-o))) == v);
222 : 15236643 : Assertion_Assert ((libc_memcpy (reinterpret_cast<void *> (b), reinterpret_cast<void *> (s->pb), static_cast<size_t> (o))) == b);
223 : 15236643 : if (Debugging)
224 : : {
225 : : M2Printf_printf1 ((const char *) "deallocating old bitset size %d bytes\\n", 39, (const unsigned char *) &o, (sizeof (o)-1));
226 : : }
227 : 15236643 : if (o > 0)
228 : : {
229 : 2076014 : Storage_DEALLOCATE (reinterpret_cast<void **> (&s->pb), o);
230 : : }
231 : 15236643 : s->pb = b;
232 : : }
233 : : }
234 : 513890731 : }
235 : :
236 : :
237 : : /*
238 : : findPos - returns a pointer to the BITSET which will contain, i.
239 : : */
240 : :
241 : 4523532028 : static Sets_PtrToBitset findPos (Sets_PtrToBitset pb, unsigned int i)
242 : : {
243 : 4523532028 : Sets_PtrToByte v;
244 : :
245 : 4523532028 : if (((((i / (MaxBitset+1))*(MaxBitset+1)) / BitsPerByte) % BitsetSize) != 0)
246 : : {
247 : : M2Error_InternalError ((const char *) "must be a multiple of bitset size", 33);
248 : : }
249 : 4523532028 : v = (Sets_PtrToByte) (pb);
250 : 4523532028 : v += ((i / (MaxBitset+1))*(MaxBitset+1)) / BitsPerByte;
251 : 4523532028 : pb = (Sets_PtrToBitset) (v);
252 : 4523532028 : return pb;
253 : : /* static analysis guarentees a RETURN statement will be used before here. */
254 : : __builtin_unreachable ();
255 : : }
256 : :
257 : :
258 : : /*
259 : : InitSet - initializes and returns a set. The set will
260 : : never contain an element less than, low.
261 : : */
262 : :
263 : 13190342 : extern "C" Sets_Set Sets_InitSet (unsigned int low)
264 : : {
265 : 13190342 : Sets_Set s;
266 : :
267 : 13190342 : Storage_ALLOCATE ((void **) &s, sizeof (Sets__T1));
268 : 13190342 : s->init = low;
269 : 13190342 : s->start = 0;
270 : 13190342 : s->end = 0;
271 : 13190342 : s->pb = NULL;
272 : 13190342 : s->bytes = 0;
273 : 13190342 : s->elements = 0;
274 : 13190342 : return s;
275 : : /* static analysis guarentees a RETURN statement will be used before here. */
276 : : __builtin_unreachable ();
277 : : }
278 : :
279 : :
280 : : /*
281 : : KillSet - deallocates Set, s.
282 : : */
283 : :
284 : 26248629 : extern "C" Sets_Set Sets_KillSet (Sets_Set s)
285 : : {
286 : 26248629 : if (s->bytes > 0)
287 : : {
288 : 24461229 : Storage_DEALLOCATE (reinterpret_cast<void **> (&s->pb), s->bytes);
289 : : }
290 : 26248629 : Storage_DEALLOCATE ((void **) &s, sizeof (Sets__T1));
291 : 26248629 : return NULL;
292 : : /* static analysis guarentees a RETURN statement will be used before here. */
293 : : __builtin_unreachable ();
294 : : }
295 : :
296 : :
297 : : /*
298 : : DuplicateSet - returns a new duplicated set.
299 : : */
300 : :
301 : 13201744 : extern "C" Sets_Set Sets_DuplicateSet (Sets_Set s)
302 : : {
303 : 13201744 : Sets_Set t;
304 : :
305 : 13201744 : Storage_ALLOCATE ((void **) &t, sizeof (Sets__T1));
306 : 13201744 : (*t) = (*s);
307 : 13201744 : Storage_ALLOCATE (reinterpret_cast<void **> (&t->pb), t->bytes);
308 : 13201744 : Assertion_Assert ((libc_memcpy (reinterpret_cast<void *> (t->pb), reinterpret_cast<void *> (s->pb), static_cast<size_t> (t->bytes))) == t->pb);
309 : 13201744 : return t;
310 : : /* static analysis guarentees a RETURN statement will be used before here. */
311 : : __builtin_unreachable ();
312 : : }
313 : :
314 : :
315 : : /*
316 : : ForeachElementInSetDo - for each element e in, s, call, p(e).
317 : : */
318 : :
319 : 8817641 : extern "C" void Sets_ForeachElementInSetDo (Sets_Set s, SymbolKey_PerformOperation p)
320 : : {
321 : 8817641 : unsigned int i;
322 : 8817641 : unsigned int j;
323 : 8817641 : unsigned int c;
324 : 8817641 : Sets_PtrToBitset b;
325 : 8817641 : Sets_PtrToByte v;
326 : :
327 : 8817641 : i = s->start;
328 : 8817641 : c = s->elements;
329 : 8817641 : b = findPos (s->pb, i);
330 : 8817641 : j = i % (MaxBitset+1);
331 : 9161371631 : while ((i <= s->end) && (c > 0))
332 : : {
333 : 9152553990 : if ((((1 << (j)) & ((*b))) != 0))
334 : : {
335 : 73812981 : c -= 1;
336 : 73812981 : (*p.proc) (i);
337 : : }
338 : 9152553990 : if (j == MaxBitset)
339 : : {
340 : 286710378 : v = (Sets_PtrToByte) (b);
341 : 286710378 : v += BitsetSize; /* avoid implications of C address arithmetic in mc PtrToByte */
342 : 286710378 : b = (Sets_PtrToBitset) (v); /* avoid implications of C address arithmetic in mc PtrToByte */
343 : 286710378 : j = 0;
344 : : }
345 : : else
346 : : {
347 : 8865843612 : j += 1;
348 : : }
349 : 9152553990 : i += 1;
350 : : }
351 : 8817641 : }
352 : :
353 : :
354 : : /*
355 : : IsElementInSet - returns TRUE if element, i, is in set, s.
356 : : */
357 : :
358 : 408278103 : extern "C" bool Sets_IsElementInSet (Sets_Set s, unsigned int i)
359 : : {
360 : 408278103 : Sets_PtrToBitset b;
361 : :
362 : 408278103 : checkRange (s, i);
363 : 408278103 : b = findPos (s->pb, i);
364 : 408278103 : return (((1 << (i % (MaxBitset+1))) & ((*b))) != 0);
365 : : /* static analysis guarentees a RETURN statement will be used before here. */
366 : : __builtin_unreachable ();
367 : : }
368 : :
369 : :
370 : : /*
371 : : NoOfElementsInSet - returns the number of elements in a set, s.
372 : : */
373 : :
374 : 725480 : extern "C" unsigned int Sets_NoOfElementsInSet (Sets_Set s)
375 : : {
376 : 725480 : return s->elements;
377 : : /* static analysis guarentees a RETURN statement will be used before here. */
378 : : __builtin_unreachable ();
379 : : }
380 : :
381 : :
382 : : /*
383 : : ExcludeElementFromSet - excludes element, i, from set, s.
384 : : */
385 : :
386 : 14585412 : extern "C" void Sets_ExcludeElementFromSet (Sets_Set s, unsigned int i)
387 : : {
388 : 14585412 : Sets_PtrToBitset b;
389 : :
390 : 14585412 : checkRange (s, i);
391 : 14585412 : b = findPos (s->pb, i);
392 : 14585412 : if ((((1 << (i % (MaxBitset+1))) & ((*b))) != 0))
393 : : {
394 : 2816046 : s->elements -= 1;
395 : 2816046 : (*b) &= (~(1 << (i % (MaxBitset+1) )));
396 : : }
397 : 14585412 : }
398 : :
399 : :
400 : : /*
401 : : IncludeElementIntoSet - includes element, i, into set, s.
402 : : */
403 : :
404 : 91027216 : extern "C" void Sets_IncludeElementIntoSet (Sets_Set s, unsigned int i)
405 : : {
406 : 91027216 : Sets_PtrToBitset b;
407 : :
408 : 91027216 : checkRange (s, i);
409 : 91027216 : b = findPos (s->pb, i);
410 : 91027216 : if (! ((((1 << (i % (MaxBitset+1))) & ((*b))) != 0)))
411 : : {
412 : 90314056 : s->elements += 1;
413 : 90314056 : (*b) |= (1 << (i % (MaxBitset+1) ));
414 : 90314056 : if ((s->start == 0) || (s->start > i))
415 : : {
416 : 28086931 : s->start = i;
417 : : }
418 : 90314056 : if ((s->end == 0) || (s->end < i))
419 : : {
420 : 28179330 : s->end = i;
421 : : }
422 : : }
423 : 91027216 : }
424 : :
425 : :
426 : : /*
427 : : EqualSet - return TRUE if left = right.
428 : : */
429 : :
430 : 5867237 : extern "C" bool Sets_EqualSet (Sets_Set left, Sets_Set right)
431 : : {
432 : 5867237 : Sets_PtrToByte v;
433 : 5867237 : Sets_PtrToBitset lptr;
434 : 5867237 : Sets_PtrToBitset rptr;
435 : 5867237 : unsigned int last;
436 : 5867237 : unsigned int el;
437 : :
438 : 5867237 : if ((((left->init == right->init) && (left->start == right->start)) && (left->end == right->end)) && (left->elements == right->elements))
439 : : {
440 : : /* Now check contents. */
441 : 5760872 : el = left->start;
442 : 5760872 : last = left->end;
443 : 4000823656 : while (el <= last)
444 : : {
445 : 4000823656 : lptr = findPos (left->pb, el);
446 : 4000823656 : rptr = findPos (right->pb, el);
447 : 4000823656 : if ((el+BitsetSize) < last)
448 : : {
449 : : /* We can check complete bitset, */
450 : 3995062784 : if ((*lptr) != (*rptr))
451 : : {
452 : : return false;
453 : : }
454 : 3995062784 : el += BitsetSize;
455 : 3995062784 : v = (Sets_PtrToByte) (lptr);
456 : 3995062784 : v += BitsetSize; /* Avoid implications of C address arithmetic in mc PtrToByte */
457 : 3995062784 : lptr = (Sets_PtrToBitset) (v); /* Avoid implications of C address arithmetic in mc PtrToByte */
458 : 3995062784 : v = (Sets_PtrToByte) (rptr);
459 : 3995062784 : v += BitsetSize; /* Avoid implications of C address arithmetic in mc PtrToByte */
460 : 3995062784 : rptr = (Sets_PtrToBitset) (v);
461 : : }
462 : : else
463 : : {
464 : : /* We must check remaining bits only. */
465 : 21529175 : while ((el <= last) && (el >= left->init))
466 : : {
467 : 15768303 : if ((Sets_IsElementInSet (left, el)) != (Sets_IsElementInSet (right, el)))
468 : : {
469 : : return false;
470 : : }
471 : 15768303 : el += 1;
472 : : }
473 : : return true;
474 : : }
475 : : }
476 : : return true;
477 : : }
478 : : return false;
479 : : /* static analysis guarentees a RETURN statement will be used before here. */
480 : : __builtin_unreachable ();
481 : : }
482 : :
483 : 12963 : extern "C" void _M2_Sets_init (__attribute__((unused)) int argc,__attribute__((unused)) char *argv[],__attribute__((unused)) char *envp[])
484 : : {
485 : 12963 : }
486 : :
487 : 0 : extern "C" void _M2_Sets_fini (__attribute__((unused)) int argc,__attribute__((unused)) char *argv[],__attribute__((unused)) char *envp[])
488 : : {
489 : 0 : }
|
