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-2026 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 "gcc-consolidation.h"
26 :
27 : #include <stdbool.h>
28 : # if !defined (PROC_D)
29 : # define PROC_D
30 : typedef void (*PROC_t) (void);
31 : typedef struct { PROC_t proc; } PROC;
32 : # endif
33 :
34 : # if !defined (TRUE)
35 : # define TRUE (1==1)
36 : # endif
37 :
38 : # if !defined (FALSE)
39 : # define FALSE (1==0)
40 : # endif
41 :
42 : # include "GStorage.h"
43 : #if defined(__cplusplus)
44 : # undef NULL
45 : # define NULL 0
46 : #endif
47 : #define _Sets_C
48 :
49 : #include "GSets.h"
50 : # include "GSYSTEM.h"
51 : # include "GSymbolTable.h"
52 : # include "GM2Error.h"
53 : # include "GStorage.h"
54 : # include "Glibc.h"
55 : # include "GM2Printf.h"
56 : # include "GAssertion.h"
57 :
58 : # define BitsetSize sizeof (unsigned int )
59 : # define MaxBitset (31)
60 : # define BitsPerByte (((MaxBitset+1)) / BitsetSize)
61 : # define Debugging false
62 : typedef unsigned char *Sets_PtrToByte;
63 :
64 : typedef struct Sets__T1_r Sets__T1;
65 :
66 : typedef Sets__T1 *Sets_Set__opaque;
67 :
68 : typedef unsigned int *Sets_PtrToBitset;
69 :
70 : struct Sets__T1_r {
71 : unsigned int init;
72 : unsigned int start;
73 : unsigned int end;
74 : Sets_PtrToBitset pb;
75 : unsigned int bytes;
76 : unsigned int elements;
77 : };
78 :
79 :
80 : /*
81 : InitSet - initializes and returns a set. The set will
82 : never contain an element less than, low.
83 : */
84 :
85 : extern "C" Sets_Set Sets_InitSet (unsigned int low);
86 :
87 : /*
88 : KillSet - deallocates Set, s.
89 : */
90 :
91 : extern "C" Sets_Set Sets_KillSet (Sets_Set s);
92 :
93 : /*
94 : DuplicateSet - returns a new duplicated set.
95 : */
96 :
97 : extern "C" Sets_Set Sets_DuplicateSet (Sets_Set s);
98 :
99 : /*
100 : ForeachElementInSetDo - for each element e in, s, call, p(e).
101 : */
102 :
103 : extern "C" void Sets_ForeachElementInSetDo (Sets_Set s, SymbolKey_PerformOperation p);
104 :
105 : /*
106 : IsElementInSet - returns TRUE if element, i, is in set, s.
107 : */
108 :
109 : extern "C" bool Sets_IsElementInSet (Sets_Set s, unsigned int i);
110 :
111 : /*
112 : NoOfElementsInSet - returns the number of elements in a set, s.
113 : */
114 :
115 : extern "C" unsigned int Sets_NoOfElementsInSet (Sets_Set s);
116 :
117 : /*
118 : ExcludeElementFromSet - excludes element, i, from set, s.
119 : */
120 :
121 : extern "C" void Sets_ExcludeElementFromSet (Sets_Set s, unsigned int i);
122 :
123 : /*
124 : IncludeElementIntoSet - includes element, i, into set, s.
125 : */
126 :
127 : extern "C" void Sets_IncludeElementIntoSet (Sets_Set s, unsigned int i);
128 :
129 : /*
130 : EqualSet - return TRUE if left = right.
131 : */
132 :
133 : extern "C" bool Sets_EqualSet (Sets_Set left, Sets_Set right);
134 :
135 : /*
136 : growSet -
137 : */
138 :
139 : static void growSet (unsigned int i, unsigned int bytes);
140 :
141 : /*
142 : checkRange - checks to make sure, i, is within range and
143 : it will extend the set bitmap if required.
144 : */
145 :
146 : static void checkRange (Sets_Set__opaque s, unsigned int i);
147 :
148 : /*
149 : findPos - returns a pointer to the BITSET which will contain, i.
150 : */
151 :
152 : static Sets_PtrToBitset findPos (Sets_PtrToBitset pb, unsigned int i);
153 :
154 :
155 : /*
156 : growSet -
157 : */
158 :
159 0 : static void growSet (unsigned int i, unsigned int bytes)
160 : {
161 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));
162 0 : }
163 :
164 :
165 : /*
166 : checkRange - checks to make sure, i, is within range and
167 : it will extend the set bitmap if required.
168 : */
169 :
170 2317644266 : static void checkRange (Sets_Set__opaque s, unsigned int i)
171 : {
172 2317644266 : unsigned int bits;
173 2317644266 : unsigned int o;
174 2317644266 : unsigned int j;
175 2317644266 : Sets_PtrToBitset b;
176 2317644266 : Sets_PtrToByte v;
177 :
178 2317644266 : if (i < s->init)
179 : {
180 0 : M2Error_InternalError ((const char *) "set element is too low and out of bounds", 40);
181 : }
182 2317644266 : else if (i > (SymbolTable_FinalSymbol ()))
183 : {
184 : /* avoid dangling else. */
185 0 : M2Error_InternalError ((const char *) "set element is too high and out of bounds", 41);
186 : }
187 : else
188 : {
189 : /* avoid dangling else. */
190 2317644266 : j = s->bytes*BitsPerByte;
191 2317644266 : if (i >= j)
192 : {
193 72076571 : o = s->bytes;
194 72076571 : if (Debugging)
195 : {
196 : 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));
197 : }
198 72076571 : if (s->bytes == 0)
199 : {
200 55847320 : s->bytes = BitsetSize;
201 : }
202 335993845 : while (i >= (s->bytes*BitsPerByte))
203 : {
204 263917274 : if (Debugging)
205 : {
206 : growSet (i, s->bytes);
207 : }
208 263917274 : s->bytes = s->bytes*2;
209 : }
210 72076571 : Storage_ALLOCATE (reinterpret_cast <void **> (&b), s->bytes);
211 72076571 : if (Debugging)
212 : {
213 : bits = s->bytes*8;
214 : 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));
215 : if (i > bits)
216 : {
217 : M2Error_InternalError ((const char *) "buffer is too small", 19);
218 : }
219 : }
220 : /* a := memset(b, 0, bytes) ; */
221 72076571 : v = (Sets_PtrToByte) (b);
222 72076571 : v += o;
223 72076571 : Assertion_Assert ((libc_memset (reinterpret_cast <void *> (v), 0, static_cast<size_t> (s->bytes-o))) == v);
224 72076571 : Assertion_Assert ((libc_memcpy (reinterpret_cast <void *> (b), reinterpret_cast <void *> (s->pb), static_cast<size_t> (o))) == b);
225 72076571 : if (Debugging)
226 : {
227 : M2Printf_printf1 ((const char *) "deallocating old bitset size %d bytes\\n", 39, (const unsigned char *) &o, (sizeof (o)-1));
228 : }
229 72076571 : if (o > 0)
230 : {
231 16229251 : Storage_DEALLOCATE (reinterpret_cast <void **> (&s->pb), o);
232 : }
233 72076571 : s->pb = b;
234 : }
235 : }
236 2317644266 : }
237 :
238 :
239 : /*
240 : findPos - returns a pointer to the BITSET which will contain, i.
241 : */
242 :
243 14676448042 : static Sets_PtrToBitset findPos (Sets_PtrToBitset pb, unsigned int i)
244 : {
245 14676448042 : Sets_PtrToByte v;
246 :
247 14676448042 : if (((((i / (MaxBitset+1))*(MaxBitset+1)) / BitsPerByte) % BitsetSize) != 0)
248 : {
249 : M2Error_InternalError ((const char *) "must be a multiple of bitset size", 33);
250 : }
251 14676448042 : v = (Sets_PtrToByte) (pb);
252 14676448042 : v += ((i / (MaxBitset+1))*(MaxBitset+1)) / BitsPerByte;
253 14676448042 : pb = (Sets_PtrToBitset) (v);
254 14676448042 : return pb;
255 : /* static analysis guarentees a RETURN statement will be used before here. */
256 : __builtin_unreachable ();
257 : }
258 :
259 :
260 : /*
261 : InitSet - initializes and returns a set. The set will
262 : never contain an element less than, low.
263 : */
264 :
265 55896055 : extern "C" Sets_Set Sets_InitSet (unsigned int low)
266 : {
267 55896055 : Sets_Set__opaque s;
268 :
269 55896055 : Storage_ALLOCATE ((void **) &s, sizeof (Sets__T1));
270 55896055 : s->init = low;
271 55896055 : s->start = 0;
272 55896055 : s->end = 0;
273 55896055 : s->pb = NULL;
274 55896055 : s->bytes = 0;
275 55896055 : s->elements = 0;
276 55896055 : return static_cast<Sets_Set> (s);
277 : /* static analysis guarentees a RETURN statement will be used before here. */
278 : __builtin_unreachable ();
279 : }
280 :
281 :
282 : /*
283 : KillSet - deallocates Set, s.
284 : */
285 :
286 70664799 : extern "C" Sets_Set Sets_KillSet (Sets_Set s)
287 : {
288 70664799 : if (static_cast<Sets_Set__opaque> (s)->bytes > 0)
289 : {
290 70000106 : Storage_DEALLOCATE (reinterpret_cast <void **> (&static_cast<Sets_Set__opaque> (s)->pb), static_cast<Sets_Set__opaque> (s)->bytes);
291 : }
292 70664799 : Storage_DEALLOCATE ((void **) &s, sizeof (Sets__T1));
293 70664799 : return static_cast<Sets_Set> (NULL);
294 : /* static analysis guarentees a RETURN statement will be used before here. */
295 : __builtin_unreachable ();
296 : }
297 :
298 :
299 : /*
300 : DuplicateSet - returns a new duplicated set.
301 : */
302 :
303 14948840 : extern "C" Sets_Set Sets_DuplicateSet (Sets_Set s)
304 : {
305 14948840 : Sets_Set__opaque t;
306 :
307 14948840 : Storage_ALLOCATE ((void **) &t, sizeof (Sets__T1));
308 14948840 : (*t) = (*static_cast<Sets_Set__opaque> (s));
309 14948840 : Storage_ALLOCATE (reinterpret_cast <void **> (&t->pb), t->bytes);
310 14948840 : Assertion_Assert ((libc_memcpy (reinterpret_cast <void *> (t->pb), reinterpret_cast <void *> (static_cast<Sets_Set__opaque> (s)->pb), static_cast<size_t> (t->bytes))) == t->pb);
311 14948840 : return static_cast<Sets_Set> (t);
312 : /* static analysis guarentees a RETURN statement will be used before here. */
313 : __builtin_unreachable ();
314 : }
315 :
316 :
317 : /*
318 : ForeachElementInSetDo - for each element e in, s, call, p(e).
319 : */
320 :
321 11758947 : extern "C" void Sets_ForeachElementInSetDo (Sets_Set s, SymbolKey_PerformOperation p)
322 : {
323 11758947 : unsigned int i;
324 11758947 : unsigned int j;
325 11758947 : unsigned int c;
326 11758947 : Sets_PtrToBitset b;
327 11758947 : Sets_PtrToByte v;
328 :
329 11758947 : i = static_cast<Sets_Set__opaque> (s)->start;
330 11758947 : c = static_cast<Sets_Set__opaque> (s)->elements;
331 11758947 : b = findPos (static_cast<Sets_Set__opaque> (s)->pb, i);
332 11758947 : j = i % (MaxBitset+1);
333 12062525772 : while ((i <= static_cast<Sets_Set__opaque> (s)->end) && (c > 0))
334 : {
335 12050766825 : if ((((1 << (j)) & ((*b))) != 0))
336 : {
337 151469191 : c -= 1;
338 151469191 : (*p.proc) (i);
339 : }
340 12050766825 : if (j == MaxBitset)
341 : {
342 376435932 : v = (Sets_PtrToByte) (b);
343 376435932 : v += BitsetSize; /* avoid implications of C address arithmetic in mc PtrToByte */
344 376435932 : b = (Sets_PtrToBitset) (v); /* avoid implications of C address arithmetic in mc PtrToByte */
345 376435932 : j = 0;
346 : }
347 : else
348 : {
349 11674330893 : j += 1;
350 : }
351 12050766825 : i += 1;
352 : }
353 11758947 : }
354 :
355 :
356 : /*
357 : IsElementInSet - returns TRUE if element, i, is in set, s.
358 : */
359 :
360 1862177632 : extern "C" bool Sets_IsElementInSet (Sets_Set s, unsigned int i)
361 : {
362 1862177632 : Sets_PtrToBitset b;
363 :
364 1862177632 : checkRange (static_cast<Sets_Set__opaque> (s), i);
365 1862177632 : b = findPos (static_cast<Sets_Set__opaque> (s)->pb, i);
366 1862177632 : return (((1 << (i % (MaxBitset+1))) & ((*b))) != 0);
367 : /* static analysis guarentees a RETURN statement will be used before here. */
368 : __builtin_unreachable ();
369 : }
370 :
371 :
372 : /*
373 : NoOfElementsInSet - returns the number of elements in a set, s.
374 : */
375 :
376 821455 : extern "C" unsigned int Sets_NoOfElementsInSet (Sets_Set s)
377 : {
378 821455 : return static_cast<Sets_Set__opaque> (s)->elements;
379 : /* static analysis guarentees a RETURN statement will be used before here. */
380 : __builtin_unreachable ();
381 : }
382 :
383 :
384 : /*
385 : ExcludeElementFromSet - excludes element, i, from set, s.
386 : */
387 :
388 24038928 : extern "C" void Sets_ExcludeElementFromSet (Sets_Set s, unsigned int i)
389 : {
390 24038928 : Sets_PtrToBitset b;
391 :
392 24038928 : checkRange (static_cast<Sets_Set__opaque> (s), i);
393 24038928 : b = findPos (static_cast<Sets_Set__opaque> (s)->pb, i);
394 24038928 : if ((((1 << (i % (MaxBitset+1))) & ((*b))) != 0))
395 : {
396 4277100 : static_cast<Sets_Set__opaque> (s)->elements -= 1;
397 4277100 : (*b) &= (~(1 << (i % (MaxBitset+1) )));
398 : }
399 24038928 : }
400 :
401 :
402 : /*
403 : IncludeElementIntoSet - includes element, i, into set, s.
404 : */
405 :
406 431427706 : extern "C" void Sets_IncludeElementIntoSet (Sets_Set s, unsigned int i)
407 : {
408 431427706 : Sets_PtrToBitset b;
409 :
410 431427706 : checkRange (static_cast<Sets_Set__opaque> (s), i);
411 431427706 : b = findPos (static_cast<Sets_Set__opaque> (s)->pb, i);
412 431427706 : if (! ((((1 << (i % (MaxBitset+1))) & ((*b))) != 0)))
413 : {
414 430570213 : static_cast<Sets_Set__opaque> (s)->elements += 1;
415 430570213 : (*b) |= (1 << (i % (MaxBitset+1) ));
416 430570213 : if ((static_cast<Sets_Set__opaque> (s)->start == 0) || (static_cast<Sets_Set__opaque> (s)->start > i))
417 : {
418 122298909 : static_cast<Sets_Set__opaque> (s)->start = i;
419 : }
420 430570213 : if ((static_cast<Sets_Set__opaque> (s)->end == 0) || (static_cast<Sets_Set__opaque> (s)->end < i))
421 : {
422 147058492 : static_cast<Sets_Set__opaque> (s)->end = i;
423 : }
424 : }
425 431427706 : }
426 :
427 :
428 : /*
429 : EqualSet - return TRUE if left = right.
430 : */
431 :
432 7115878 : extern "C" bool Sets_EqualSet (Sets_Set left, Sets_Set right)
433 : {
434 7115878 : Sets_PtrToByte v;
435 7115878 : Sets_PtrToBitset lptr;
436 7115878 : Sets_PtrToBitset rptr;
437 7115878 : unsigned int last;
438 7115878 : unsigned int el;
439 :
440 7115878 : if ((((static_cast<Sets_Set__opaque> (left)->init == static_cast<Sets_Set__opaque> (right)->init) && (static_cast<Sets_Set__opaque> (left)->start == static_cast<Sets_Set__opaque> (right)->start)) && (static_cast<Sets_Set__opaque> (left)->end == static_cast<Sets_Set__opaque> (right)->end)) && (static_cast<Sets_Set__opaque> (left)->elements == static_cast<Sets_Set__opaque> (right)->elements))
441 : {
442 : /* Now check contents. */
443 : el = static_cast<Sets_Set__opaque> (left)->start;
444 : last = static_cast<Sets_Set__opaque> (left)->end;
445 12347044829 : while (el <= last)
446 : {
447 12347044829 : lptr = findPos (static_cast<Sets_Set__opaque> (left)->pb, el);
448 12347044829 : rptr = findPos (static_cast<Sets_Set__opaque> (right)->pb, el);
449 12347044829 : if ((el+BitsetSize) < last)
450 : {
451 : /* We can check complete bitset, */
452 12339965693 : if ((*lptr) != (*rptr))
453 : {
454 : return false;
455 : }
456 12339965693 : el += BitsetSize;
457 12339965693 : v = (Sets_PtrToByte) (lptr);
458 12339965693 : v += BitsetSize; /* Avoid implications of C address arithmetic in mc PtrToByte */
459 12339965693 : lptr = (Sets_PtrToBitset) (v); /* Avoid implications of C address arithmetic in mc PtrToByte */
460 12339965693 : v = (Sets_PtrToByte) (rptr);
461 12339965693 : v += BitsetSize; /* Avoid implications of C address arithmetic in mc PtrToByte */
462 12339965693 : rptr = (Sets_PtrToBitset) (v);
463 : }
464 : else
465 : {
466 : /* We must check remaining bits only. */
467 29240987 : while ((el <= last) && (el >= static_cast<Sets_Set__opaque> (left)->init))
468 : {
469 22161851 : if ((Sets_IsElementInSet (left, el)) != (Sets_IsElementInSet (right, el)))
470 : {
471 : return false;
472 : }
473 22161851 : el += 1;
474 : }
475 : return true;
476 : }
477 : }
478 : return true;
479 : }
480 : return false;
481 : /* static analysis guarentees a RETURN statement will be used before here. */
482 : __builtin_unreachable ();
483 : }
484 :
485 14952 : extern "C" void _M2_Sets_init (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
486 : {
487 14952 : }
488 :
489 0 : extern "C" void _M2_Sets_fini (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
490 : {
491 0 : }
|
