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-2025 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 : 641814286 : static void checkRange (Sets_Set__opaque s, unsigned int i)
171 : : {
172 : 641814286 : unsigned int bits;
173 : 641814286 : unsigned int o;
174 : 641814286 : unsigned int j;
175 : 641814286 : Sets_PtrToBitset b;
176 : 641814286 : Sets_PtrToByte v;
177 : :
178 : 641814286 : if (i < s->init)
179 : : {
180 : 0 : M2Error_InternalError ((const char *) "set element is too low and out of bounds", 40);
181 : : }
182 : 641814286 : 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 : 641814286 : j = s->bytes*BitsPerByte;
191 : 641814286 : if (i >= j)
192 : : {
193 : 22624467 : o = s->bytes;
194 : 22624467 : 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 : 22624467 : if (s->bytes == 0)
199 : : {
200 : 19960186 : s->bytes = BitsetSize;
201 : : }
202 : 116916492 : while (i >= (s->bytes*BitsPerByte))
203 : : {
204 : 94292025 : if (Debugging)
205 : : {
206 : : growSet (i, s->bytes);
207 : : }
208 : 94292025 : s->bytes = s->bytes*2;
209 : : }
210 : 22624467 : Storage_ALLOCATE (reinterpret_cast <void **> (&b), s->bytes);
211 : 22624467 : 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 : 22624467 : v = (Sets_PtrToByte) (b);
222 : 22624467 : v += o;
223 : 22624467 : Assertion_Assert ((libc_memset (reinterpret_cast <void *> (v), 0, static_cast<size_t> (s->bytes-o))) == v);
224 : 22624467 : Assertion_Assert ((libc_memcpy (reinterpret_cast <void *> (b), reinterpret_cast <void *> (s->pb), static_cast<size_t> (o))) == b);
225 : 22624467 : 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 : 22624467 : if (o > 0)
230 : : {
231 : 2664281 : Storage_DEALLOCATE (reinterpret_cast <void **> (&s->pb), o);
232 : : }
233 : 22624467 : s->pb = b;
234 : : }
235 : : }
236 : 641814286 : }
237 : :
238 : :
239 : : /*
240 : : findPos - returns a pointer to the BITSET which will contain, i.
241 : : */
242 : :
243 : 6012229492 : static Sets_PtrToBitset findPos (Sets_PtrToBitset pb, unsigned int i)
244 : : {
245 : 6012229492 : Sets_PtrToByte v;
246 : :
247 : 6012229492 : 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 : 6012229492 : v = (Sets_PtrToByte) (pb);
252 : 6012229492 : v += ((i / (MaxBitset+1))*(MaxBitset+1)) / BitsPerByte;
253 : 6012229492 : pb = (Sets_PtrToBitset) (v);
254 : 6012229492 : 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 : 20013181 : extern "C" Sets_Set Sets_InitSet (unsigned int low)
266 : : {
267 : 20013181 : Sets_Set__opaque s;
268 : :
269 : 20013181 : Storage_ALLOCATE ((void **) &s, sizeof (Sets__T1));
270 : 20013181 : s->init = low;
271 : 20013181 : s->start = 0;
272 : 20013181 : s->end = 0;
273 : 20013181 : s->pb = NULL;
274 : 20013181 : s->bytes = 0;
275 : 20013181 : s->elements = 0;
276 : 20013181 : 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 : 31827069 : extern "C" Sets_Set Sets_KillSet (Sets_Set s)
287 : : {
288 : 31827069 : if (static_cast<Sets_Set__opaque> (s)->bytes > 0)
289 : : {
290 : 30169914 : Storage_DEALLOCATE (reinterpret_cast <void **> (&static_cast<Sets_Set__opaque> (s)->pb), static_cast<Sets_Set__opaque> (s)->bytes);
291 : : }
292 : 31827069 : Storage_DEALLOCATE ((void **) &s, sizeof (Sets__T1));
293 : 31827069 : 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 : 11997680 : extern "C" Sets_Set Sets_DuplicateSet (Sets_Set s)
304 : : {
305 : 11997680 : Sets_Set__opaque t;
306 : :
307 : 11997680 : Storage_ALLOCATE ((void **) &t, sizeof (Sets__T1));
308 : 11997680 : (*t) = (*static_cast<Sets_Set__opaque> (s));
309 : 11997680 : Storage_ALLOCATE (reinterpret_cast <void **> (&t->pb), t->bytes);
310 : 11997680 : 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 : 11997680 : 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 : 7916430 : extern "C" void Sets_ForeachElementInSetDo (Sets_Set s, SymbolKey_PerformOperation p)
322 : : {
323 : 7916430 : unsigned int i;
324 : 7916430 : unsigned int j;
325 : 7916430 : unsigned int c;
326 : 7916430 : Sets_PtrToBitset b;
327 : 7916430 : Sets_PtrToByte v;
328 : :
329 : 7916430 : i = static_cast<Sets_Set__opaque> (s)->start;
330 : 7916430 : c = static_cast<Sets_Set__opaque> (s)->elements;
331 : 7916430 : b = findPos (static_cast<Sets_Set__opaque> (s)->pb, i);
332 : 7916430 : j = i % (MaxBitset+1);
333 : 3874393233 : while ((i <= static_cast<Sets_Set__opaque> (s)->end) && (c > 0))
334 : : {
335 : 3866476803 : if ((((1 << (j)) & ((*b))) != 0))
336 : : {
337 : 62542570 : c -= 1;
338 : 62542570 : (*p.proc) (i);
339 : : }
340 : 3866476803 : if (j == MaxBitset)
341 : : {
342 : 120726569 : v = (Sets_PtrToByte) (b);
343 : 120726569 : v += BitsetSize; /* avoid implications of C address arithmetic in mc PtrToByte */
344 : 120726569 : b = (Sets_PtrToBitset) (v); /* avoid implications of C address arithmetic in mc PtrToByte */
345 : 120726569 : j = 0;
346 : : }
347 : : else
348 : : {
349 : 3745750234 : j += 1;
350 : : }
351 : 3866476803 : i += 1;
352 : : }
353 : 7916430 : }
354 : :
355 : :
356 : : /*
357 : : IsElementInSet - returns TRUE if element, i, is in set, s.
358 : : */
359 : :
360 : 508883261 : extern "C" bool Sets_IsElementInSet (Sets_Set s, unsigned int i)
361 : : {
362 : 508883261 : Sets_PtrToBitset b;
363 : :
364 : 508883261 : checkRange (static_cast<Sets_Set__opaque> (s), i);
365 : 508883261 : b = findPos (static_cast<Sets_Set__opaque> (s)->pb, i);
366 : 508883261 : 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 : 645529 : extern "C" unsigned int Sets_NoOfElementsInSet (Sets_Set s)
377 : : {
378 : 645529 : 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 : 16444720 : extern "C" void Sets_ExcludeElementFromSet (Sets_Set s, unsigned int i)
389 : : {
390 : 16444720 : Sets_PtrToBitset b;
391 : :
392 : 16444720 : checkRange (static_cast<Sets_Set__opaque> (s), i);
393 : 16444720 : b = findPos (static_cast<Sets_Set__opaque> (s)->pb, i);
394 : 16444720 : if ((((1 << (i % (MaxBitset+1))) & ((*b))) != 0))
395 : : {
396 : 3334992 : static_cast<Sets_Set__opaque> (s)->elements -= 1;
397 : 3334992 : (*b) &= (~(1 << (i % (MaxBitset+1) )));
398 : : }
399 : 16444720 : }
400 : :
401 : :
402 : : /*
403 : : IncludeElementIntoSet - includes element, i, into set, s.
404 : : */
405 : :
406 : 116486305 : extern "C" void Sets_IncludeElementIntoSet (Sets_Set s, unsigned int i)
407 : : {
408 : 116486305 : Sets_PtrToBitset b;
409 : :
410 : 116486305 : checkRange (static_cast<Sets_Set__opaque> (s), i);
411 : 116486305 : b = findPos (static_cast<Sets_Set__opaque> (s)->pb, i);
412 : 116486305 : if (! ((((1 << (i % (MaxBitset+1))) & ((*b))) != 0)))
413 : : {
414 : 115961582 : static_cast<Sets_Set__opaque> (s)->elements += 1;
415 : 115961582 : (*b) |= (1 << (i % (MaxBitset+1) ));
416 : 115961582 : if ((static_cast<Sets_Set__opaque> (s)->start == 0) || (static_cast<Sets_Set__opaque> (s)->start > i))
417 : : {
418 : 42135823 : static_cast<Sets_Set__opaque> (s)->start = i;
419 : : }
420 : 115961582 : if ((static_cast<Sets_Set__opaque> (s)->end == 0) || (static_cast<Sets_Set__opaque> (s)->end < i))
421 : : {
422 : 39941635 : static_cast<Sets_Set__opaque> (s)->end = i;
423 : : }
424 : : }
425 : 116486305 : }
426 : :
427 : :
428 : : /*
429 : : EqualSet - return TRUE if left = right.
430 : : */
431 : :
432 : 5640743 : extern "C" bool Sets_EqualSet (Sets_Set left, Sets_Set right)
433 : : {
434 : 5640743 : Sets_PtrToByte v;
435 : 5640743 : Sets_PtrToBitset lptr;
436 : 5640743 : Sets_PtrToBitset rptr;
437 : 5640743 : unsigned int last;
438 : 5640743 : unsigned int el;
439 : :
440 : 5640743 : 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 : 5362498776 : while (el <= last)
446 : : {
447 : 5362498776 : lptr = findPos (static_cast<Sets_Set__opaque> (left)->pb, el);
448 : 5362498776 : rptr = findPos (static_cast<Sets_Set__opaque> (right)->pb, el);
449 : 5362498776 : if ((el+BitsetSize) < last)
450 : : {
451 : : /* We can check complete bitset, */
452 : 5356897184 : if ((*lptr) != (*rptr))
453 : : {
454 : : return false;
455 : : }
456 : 5356897184 : el += BitsetSize;
457 : 5356897184 : v = (Sets_PtrToByte) (lptr);
458 : 5356897184 : v += BitsetSize; /* Avoid implications of C address arithmetic in mc PtrToByte */
459 : 5356897184 : lptr = (Sets_PtrToBitset) (v); /* Avoid implications of C address arithmetic in mc PtrToByte */
460 : 5356897184 : v = (Sets_PtrToByte) (rptr);
461 : 5356897184 : v += BitsetSize; /* Avoid implications of C address arithmetic in mc PtrToByte */
462 : 5356897184 : rptr = (Sets_PtrToBitset) (v);
463 : : }
464 : : else
465 : : {
466 : : /* We must check remaining bits only. */
467 : 22189056 : while ((el <= last) && (el >= static_cast<Sets_Set__opaque> (left)->init))
468 : : {
469 : 16587464 : if ((Sets_IsElementInSet (left, el)) != (Sets_IsElementInSet (right, el)))
470 : : {
471 : : return false;
472 : : }
473 : 16587464 : 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 : 15260 : extern "C" void _M2_Sets_init (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
486 : : {
487 : 15260 : }
488 : :
489 : 0 : extern "C" void _M2_Sets_fini (__attribute__((unused)) int argc, __attribute__((unused)) char *argv[], __attribute__((unused)) char *envp[])
490 : : {
491 : 0 : }
|
