smallset.c (1942B)
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_tonstr(char *str, size_t n, smallset *s) { 39 int first = 1; 40 int u = snprintf(str, n, "{"); 41 42 size_t i; 43 for (i = 0; i < s->bits; i++) { 44 if (smallset_lookup(s, i)) { 45 if (!first) { 46 u += snprintf(&str[u], n - u, ", %zu", i); 47 } else { 48 u += snprintf(&str[u], n - u, "%zu", i); 49 first = !first; 50 } 51 } 52 } 53 54 snprintf(&str[u], n - u, "}"); 55 } 56 57 uint64_t smallset_getone(smallset *s) { 58 uint64_t i; 59 for (i = 0; i < s->bits; i++) { 60 if (smallset_lookup(s, i)) 61 return i; 62 } 63 64 return SMALLSET_IS_EMPTY; 65 } 66 67 void smallset_empty(smallset *s) { memset(s->data, 0, SIZE(s->bits)); } 68 69 uint64_t smallset_cardinality(smallset *s) { 70 uint64_t a; 71 uint64_t r = 0; 72 size_t i; 73 for (i = 0; i < SIZE(s->bits); i += 8) { 74 __asm__ volatile("POPCNT %1, %0" 75 : "=r"(a) 76 : "r"(*((uint64_t *)&s->data[i])) 77 :); 78 r += a; 79 } 80 81 uint64_t tmp = 0; 82 while (i < SIZE(s->bits)) { 83 tmp = (tmp << 8) ^ ((uint64_t)s->data[i]); 84 i++; 85 } 86 __asm__ volatile("POPCNT %1, %0" : "=r"(a) : "r"(tmp) :); 87 r += a; 88 89 return r; 90 }