Something went wrong. Try again.
the hito embeddable programming language
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219#include "bitset.h"#include <stdlib.h>#include <string.h>#include <stdio.h>#include "util.h"struct bitset { size_t nwords; /* allocated */ uint64_t *words; /* array of 64-bit chunks */};
#define BITWORD(i) ((i) >> 6) /* divide by 64 */#define BITMASK(i) (1ULL << ((i) & 63))
bitset_t *bitset_alloc(void) { bitset_t *bs = calloc(1, sizeof(bitset_t)); if (bs == NULL) { die("Out of memory: cannot allocate bitset"); } return bs;}
void bitset_free(bitset_t *bs) { if (!bs) return; free(bs->words); free(bs);}
void bitset_reserve(bitset_t *bs, size_t maxbit) { size_t need_words = BITWORD(maxbit) + 1; if (need_words <= bs->nwords) return;
size_t new_words = bs->nwords ? bs->nwords : 1; while (new_words < need_words) new_words *= 2;
uint64_t *new = calloc(new_words, sizeof(uint64_t)); if (new == NULL) { die("Out of memory: cannot enlarge bitset"); } if (bs->words) { memcpy(new, bs->words, bs->nwords * sizeof(uint64_t)); free(bs->words); } bs->words = new; bs->nwords = new_words;}
void bitset_set(bitset_t *bs, size_t bit) { bitset_reserve(bs, bit); bs->words[BITWORD(bit)] |= BITMASK(bit);}
void bitset_clear(bitset_t *bs, size_t bit) { size_t w = BITWORD(bit); if (w >= bs->nwords) return; bs->words[w] &= ~BITMASK(bit);}
bool bitset_get(const bitset_t *bs, size_t bit) { size_t w = BITWORD(bit); if (w >= bs->nwords) return false; return (bs->words[w] & BITMASK(bit)) != 0;}
void bitset_reset(bitset_t *bs) { memset(bs->words, 0, bs->nwords * sizeof(uint64_t));}
size_t bitset_count(const bitset_t *bs) { size_t count = 0; for (size_t i = 0; i < bs->nwords; i++) count += __builtin_popcountll(bs->words[i]); return count;}
size_t bitset_max(const bitset_t *bs) { for (size_t w = bs->nwords; w > 0; w--) { uint64_t x = bs->words[w - 1]; if (x != 0) { return ((w - 1) << 6) + (63 - __builtin_clzll(x)); } } return 0;}
void bitset_shift_up(bitset_t *bs, size_t n) { if (n == 0) return;
size_t word_shift = n / 64; size_t bit_shift = n % 64;
size_t old_max = bitset_max(bs); bitset_reserve(bs, old_max + n - 1); // ensure enough space
size_t old_nwords = bs->nwords;
// shift words from end to start to avoid overwriting for (ssize_t i = old_nwords - 1; i >= 0; i--) { uint64_t w = bs->words[i]; uint64_t upper = (bit_shift != 0 && i > 0) ? bs->words[i - 1] >> (64 - bit_shift) : 0; bs->words[i + word_shift] = (w << bit_shift) | upper; }
// zero out lower words for (size_t i = 0; i < word_shift; i++) bs->words[i] = 0;}
void bitset_shift_down(bitset_t *bs, size_t n) { if (n == 0) return;
size_t word_shift = n / 64; size_t bit_shift = n % 64;
if (word_shift >= bs->nwords) { // all bits are discarded bitset_reset(bs); return; }
// shift words from start to end for (size_t i = 0; i + word_shift < bs->nwords; i++) { uint64_t w = bs->words[i + word_shift]; uint64_t lower = (bit_shift != 0 && i + word_shift + 1 < bs->nwords) ? bs->words[i + word_shift + 1] << (64 - bit_shift) : 0; bs->words[i] = (w >> bit_shift) | lower; }
// zero out top words for (size_t i = bs->nwords - word_shift; i < bs->nwords; i++) bs->words[i] = 0;}
void bitset_union_with_offset(bitset_t *bs1, const bitset_t *bs2, size_t skip) { size_t total_bits = bs2->nwords * 64; if (skip >= total_bits) return; // nothing to merge
// ensure bs1 can hold all bits bitset_reserve(bs1, total_bits - skip - 1);
size_t start_word = skip / 64; size_t start_bit = skip % 64;
uint64_t carry = 0; for (size_t i = start_word; i < bs2->nwords; i++) { uint64_t w = bs2->words[i]; if (i == start_word && start_bit != 0) { // mask out the first 'start_bit' bits in the first word w &= ~((1ULL << start_bit) - 1); }
uint64_t new_w = (w >> start_bit) | carry; carry = (start_bit != 0) ? (w << (64 - start_bit)) : 0;
size_t dest_word = i - start_word; bs1->words[dest_word] |= new_w; }
if (carry) { size_t dest_word = bs2->nwords - start_word; if (dest_word >= bs1->nwords) { bitset_reserve(bs1, dest_word * 64 + 63); } bs1->words[dest_word] |= carry; }}
void bitset_union(bitset_t *bs1, const bitset_t *bs2) { if (bs2->nwords > bs1->nwords) bitset_reserve(bs1, (bs2->nwords * 64) - 1);
for (size_t i = 0; i < bs2->nwords; i++) bs1->words[i] |= bs2->words[i];}
void bitset_dump(const bitset_t *bs) { size_t start = 0; size_t bit; printf("{"); bool isStart = 1; while ((bit = bitset_next(bs, &start)) != (size_t)-1) { if (!isStart) printf(", "); printf("%zu", bit); isStart = 0; } printf("}");}
size_t bitset_next(const bitset_t *bs, size_t *start) { size_t i = *start; while (1) { size_t w = BITWORD(i); if (w >= bs->nwords) { *start = (size_t)-1; return (size_t)-1; } uint64_t word = bs->words[w];
uint64_t mask = ~0ULL << (i & 63); uint64_t rem = word & mask;
if (rem) { int bit = __builtin_ctzll(rem); size_t result = (w << 6) + bit; *start = result + 1; return result; }
i = (w + 1) << 6; }}