compilers/imcc/sets.c

   1 /*
   2  * $Id$
   3  * Copyright (C) 2002-2009, Parrot Foundation.
   4  */
   5
   6 /*
   7
   8 =head1 NAME
   9
  10 compilers/imcc/sets.c
  11
  12 =head1 DESCRIPTION
  13
  14 An implementation of sets -- used for tracking register usage.
  15
  16 =head2 Functions
  17
  18 =over 4
  19
  20 =cut
  21
  22 */
  23
  24 #include "imc.h"
  25 #include "sets.h"
  26
  27 /* HEADERIZER HFILE: compilers/imcc/sets.h */
  28
  29 /* XXX */
  30 #define fatal(e, s1, s2) do { \
  31     fprintf(stderr, "%s: %s", (s1), (s2)); \
  32     exit(e); \
  33 } while (0)
  34
  35 #define NUM_BYTES(length)    (((length) / 8) + 1)
  36 #define BYTE_IN_SET(element) ((element) >> 3)
  37 #define BIT_IN_BYTE(element) (1 << ((element) & 7))
  38
  39 /*
  40
  41 =item C<Set* set_make(PARROT_INTERP, unsigned int length)>
  42
  43 Creates a new Set object.
  44
  45 =cut
  46
  47 */
  48
  49 PARROT_MALLOC
  50 PARROT_CANNOT_RETURN_NULL
  51 Set*
  52 set_make(PARROT_INTERP, unsigned int length)
  53 {
  54     ASSERT_ARGS(set_make)
  55     Set * const s = mem_gc_allocate_zeroed_typed(interp, Set);
  56     s->length     = length;
  57     s->bmp        = mem_gc_allocate_n_zeroed_typed(interp,
  58                             NUM_BYTES(length), unsigned char);
  59
  60     return s;
  61 }
  62
  63
  64 /*
  65
  66 =item C<Set* set_make_full(PARROT_INTERP, unsigned int length)>
  67
  68 Creates a new Set object of C<length> items, setting them all to full.
  69
  70 =cut
  71
  72 */
  73
  74 PARROT_MALLOC
  75 PARROT_CANNOT_RETURN_NULL
  76 Set*
  77 set_make_full(PARROT_INTERP, unsigned int length)
  78 {
  79     ASSERT_ARGS(set_make_full)
  80     Set * const s      = set_make(interp, length);
  81     const size_t bytes = NUM_BYTES(length);
  82
  83     if (bytes)
  84         memset(s->bmp, 0xff, bytes);
  85
  86     return s;
  87 }
  88
  89
  90 /*
  91
  92 =item C<void set_free(Set *s)>
  93
  94 Frees the given Set and its allocated memory.
  95
  96 =cut
  97
  98 */
  99
 100 void
 101 set_free(ARGMOD(Set *s))
 102 {
 103     ASSERT_ARGS(set_free)
 104     if (s->bmp)
 105         mem_sys_free(s->bmp);
 106
 107     mem_sys_free(s);
 108 }
 109
 110
 111 /*
 112
 113 =item C<void set_clear(Set *s)>
 114
 115 Clears all bits in the Set.
 116
 117 =cut
 118
 119 */
 120
 121 void
 122 set_clear(ARGMOD(Set *s))
 123 {
 124     ASSERT_ARGS(set_clear)
 125     memset(s->bmp, 0, NUM_BYTES(s->length));
 126 }
 127
 128
 129 /*
 130
 131 =item C<Set* set_copy(PARROT_INTERP, const Set *s)>
 132
 133 Copies the set C<s>, returning a new set pointer.
 134
 135 =cut
 136
 137 */
 138
 139 PARROT_MALLOC
 140 PARROT_CANNOT_RETURN_NULL
 141 Set*
 142 set_copy(PARROT_INTERP, ARGIN(const Set *s))
 143 {
 144     ASSERT_ARGS(set_copy)
 145     Set * const d = set_make(interp, s->length);
 146
 147     memcpy(d->bmp, s->bmp, NUM_BYTES(d->length));
 148     return d;
 149 }
 150
 151
 152 /*
 153
 154 =item C<int set_equal(const Set *s1, const Set *s2)>
 155
 156 Compares two sets for equality; sets are equal if they contain the same
 157 elements.
 158
 159 Raises a fatal error if the two Sets have different lengths.
 160
 161 =cut
 162
 163 */
 164
 165 int
 166 set_equal(ARGIN(const Set *s1), ARGIN(const Set *s2))
 167 {
 168     ASSERT_ARGS(set_equal)
 169     int          mask;
 170     const size_t bytes = s1->length / 8;
 171
 172     if (s1->length != s2->length)
 173         fatal(1, "set_equal", "Sets don't have the same length\n");
 174
 175     if (bytes)
 176         if (memcmp(s1->bmp, s2->bmp, bytes) != 0)
 177             return 0;
 178
 179     if (s1->length % 8 == 0)
 180         return 1;
 181
 182     mask = (1 << (s1->length % 8)) - 1;
 183
 184     if ((s1->bmp[bytes] & mask) != (s2->bmp[bytes] & mask))
 185         return 0;
 186
 187     return 1;
 188 }
 189
 190
 191 /*
 192
 193 =item C<void set_add(Set *s, unsigned int element)>
 194
 195 Adds to set C<s> the element C<element>.
 196
 197 =cut
 198
 199 */
 200
 201 void
 202 set_add(ARGMOD(Set *s), unsigned int element)
 203 {
 204     ASSERT_ARGS(set_add)
 205     const int elem_byte_in_set = BYTE_IN_SET(element);
 206     const int bytes_in_set     = BYTE_IN_SET(s->length);
 207
 208     if (bytes_in_set < elem_byte_in_set) {
 209         s->bmp = (unsigned char *)mem_sys_realloc_zeroed(s->bmp,
 210             NUM_BYTES(element), NUM_BYTES(s->length));
 211         s->length += 8;
 212     }
 213
 214     s->bmp[elem_byte_in_set] |= BIT_IN_BYTE(element);
 215 }
 216
 217
 218 /*
 219
 220 =item C<unsigned int set_first_zero(const Set *s)>
 221
 222 Sets the first unused item in the set.
 223
 224 =cut
 225
 226 */
 227
 228 PARROT_WARN_UNUSED_RESULT
 229 PARROT_PURE_FUNCTION
 230 unsigned int
 231 set_first_zero(ARGIN(const Set *s))
 232 {
 233     ASSERT_ARGS(set_first_zero)
 234     unsigned int i;
 235
 236
 237     for (i = 0; i < NUM_BYTES(s->length); ++i) {
 238         const int set_byte = s->bmp[i];
 239         int j;
 240
 241         if (set_byte == 0xFF)
 242             continue;
 243
 244         for (j = 0; j < 8; ++j) {
 245             unsigned int element = i * 8 + j;
 246
 247             if (!set_contains(s, element))
 248                 return element;
 249         }
 250     }
 251
 252     return s->length;
 253 }
 254
 255
 256 /*
 257
 258 =item C<int set_contains(const Set *s, unsigned int element)>
 259
 260 Checks whether the specified element is present in the specified Set argument.
 261 Returns 1 if it is, 0 otherwise.
 262
 263 =cut
 264
 265 */
 266
 267 PARROT_WARN_UNUSED_RESULT
 268 PARROT_PURE_FUNCTION
 269 int
 270 set_contains(ARGIN(const Set *s), unsigned int element)
 271 {
 272     ASSERT_ARGS(set_contains)
 273
 274     if (element > s->length)
 275         return 0;
 276     else {
 277         /* workaround for another lcc bug.. */
 278         const int byte_in_set = element >> 3;
 279         const int pos_in_byte = BIT_IN_BYTE(element);
 280
 281
 282         return s->bmp[byte_in_set] & pos_in_byte;
 283     }
 284 }
 285
 286
 287 /*
 288
 289 =item C<Set * set_union(PARROT_INTERP, const Set *s1, const Set *s2)>
 290
 291 Computes the union of the two Set arguments, returning it as a new Set.
 292
 293 Raises a fatal error if the two Sets have different lengths.
 294
 295 =cut
 296
 297 */
 298
 299 PARROT_MALLOC
 300 PARROT_CANNOT_RETURN_NULL
 301 Set *
 302 set_union(PARROT_INTERP, ARGIN(const Set *s1), ARGIN(const Set *s2))
 303 {
 304     ASSERT_ARGS(set_union)
 305     unsigned int i;
 306     Set * const s = set_make(interp, s1->length);
 307
 308     if (s1->length != s2->length)
 309         fatal(1, "set_union", "Sets don't have the same length\n");
 310
 311     for (i = 0; i < BYTE_IN_SET(s1->length); i++) {
 312         s->bmp[i] = s1->bmp[i] | s2->bmp[i];
 313     }
 314
 315     return s;
 316 }
 317
 318
 319 /*
 320
 321 =item C<Set * set_intersec(PARROT_INTERP, const Set *s1, const Set *s2)>
 322
 323 Creates a new Set object that is the intersection of the Set arguments (defined
 324 through the binary C<and> operator.)
 325
 326 Raises a fatal error if the two Sets have different lengths.
 327
 328 =cut
 329
 330 */
 331
 332 PARROT_MALLOC
 333 PARROT_CANNOT_RETURN_NULL
 334 Set *
 335 set_intersec(PARROT_INTERP, ARGIN(const Set *s1), ARGIN(const Set *s2))
 336 {
 337     ASSERT_ARGS(set_intersec)
 338     unsigned int i;
 339     Set * const  s = set_make(interp, s1->length);
 340
 341     if (s1->length != s2->length)
 342         fatal(1, "set_intersec", "Sets don't have the same length\n");
 343
 344     for (i = 0; i < BYTE_IN_SET(s1->length); i++) {
 345         s->bmp[i] = s1->bmp[i] & s2->bmp[i];
 346     }
 347
 348     return s;
 349 }
 350
 351
 352 /*
 353
 354 =item C<void set_intersec_inplace(Set *s1, const Set *s2)>
 355
 356 Performs a set intersection in place -- the first Set argument changes to
 357 contain the result.
 358
 359 =cut
 360
 361 */
 362
 363 void
 364 set_intersec_inplace(ARGMOD(Set *s1), ARGIN(const Set *s2))
 365 {
 366     ASSERT_ARGS(set_intersec_inplace)
 367     unsigned int i;
 368
 369     if (s1->length != s2->length)
 370         fatal(1, "set_intersec_inplace", "Sets don't have the same length\n");
 371
 372     for (i = 0; i < BYTE_IN_SET(s1->length); i++) {
 373         s1->bmp[i] &= s2->bmp[i];
 374     }
 375 }
 376
 377 /*
 378
 379 =back
 380
 381 =cut
 382
 383 */
 384
 385 /*
 386  * Local variables:
 387  *   c-file-style: "parrot"
 388  * End:
 389  * vim: expandtab shiftwidth=4:
 390  */