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