aocc23

Advent of Code 2023
git clone git://www.tkruger.se/aocc23.git
Log | Files | Refs | README

smallset.c (2192B)

      1 #include "smallset.h"
      2 
      3 #define BIDX(x) (x / 8)
      4 #define BMSK(x) (0x80 >> (x % 8))
      5 #define SIZE(b) ((b + 7) >> 3)
      6 
      7 void smallset_init(smallset *s, const size_t bits) {
      8   s->bits = bits;
      9   s->data = calloc(SIZE(bits), sizeof(*s->data));
     10   assert(sizeof(*s->data) == 1);
     11 }
     12 
     13 void smallset_clear(smallset *s) {
     14   s->bits = 0;
     15   free(s->data);
     16 }
     17 
     18 void smallset_insert(smallset *s, const uint64_t x) {
     19   assert(x < s->bits);
     20   s->data[BIDX(x)] |= BMSK(x);
     21 }
     22 
     23 int smallset_lookup(smallset *s, const uint64_t x) {
     24   assert(x < s->bits);
     25   return s->data[BIDX(x)] & BMSK(x);
     26 }
     27 
     28 void smallset_intersection(smallset *out, smallset *a, smallset *b) {
     29   assert(a->bits == b->bits);
     30   assert(out->bits == a->bits);
     31 
     32   size_t i;
     33   for (i = 0; i < SIZE(out->bits); i++) {
     34     out->data[i] = a->data[i] & b->data[i];
     35   }
     36 }
     37 
     38 void smallset_minus(smallset *out, smallset *a, smallset *b) {
     39   assert(a->bits == b->bits);
     40   assert(out->bits == a->bits);
     41 
     42   size_t i;
     43   for (i = 0; i < SIZE(out->bits); i++) {
     44     out->data[i] = a->data[i] - (a->data[i] & b->data[i]);
     45   }
     46 }
     47 
     48 void smallset_tonstr(char *str, size_t n, smallset *s) {
     49   int first = 1;
     50   int u = snprintf(str, n, "{");
     51 
     52   size_t i;
     53   for (i = 0; i < s->bits; i++) {
     54     if (smallset_lookup(s, i)) {
     55       if (!first) {
     56         u += snprintf(&str[u], n - u, ", %zu", i);
     57       } else {
     58         u += snprintf(&str[u], n - u, "%zu", i);
     59         first = !first;
     60       }
     61     }
     62   }
     63 
     64   snprintf(&str[u], n - u, "}");
     65 }
     66 
     67 uint64_t smallset_getone(smallset *s) {
     68   uint64_t i;
     69   for (i = 0; i < s->bits; i++) {
     70     if (smallset_lookup(s, i))
     71       return i;
     72   }
     73 
     74   return SMALLSET_IS_EMPTY;
     75 }
     76 
     77 void smallset_empty(smallset *s) { memset(s->data, 0, SIZE(s->bits)); }
     78 
     79 uint64_t smallset_cardinality(smallset *s) {
     80   uint64_t a;
     81   uint64_t r = 0;
     82   size_t i;
     83   for (i = 0; i < SIZE(s->bits) - 8; i += 8) {
     84     __asm__ volatile("POPCNT %1, %0"
     85                      : "=r"(a)
     86                      : "r"(*((uint64_t *)&s->data[i]))
     87                      :);
     88     r += a;
     89   }
     90 
     91   uint64_t tmp = 0;
     92   while (i < SIZE(s->bits)) {
     93     tmp = (tmp << 8) ^ ((uint64_t)s->data[i]);
     94     i++;
     95   }
     96   __asm__ volatile("POPCNT %1, %0" : "=r"(a) : "r"(tmp) :);
     97   r += a;
     98 
     99   return r;
    100 }