From 2d90303258536094a9f6e54b1b63bd889de321b4 Mon Sep 17 00:00:00 2001 From: Alex AUVOLAT Date: Sun, 8 Dec 2013 18:35:49 +0100 Subject: Improved bitset implementation --- set_bitsets.c | 122 +++++++++++++++++++++++++++++----------------------------- sets.h | 6 +-- 2 files changed, 65 insertions(+), 63 deletions(-) diff --git a/set_bitsets.c b/set_bitsets.c index bbfd095..01a3cf4 100644 --- a/set_bitsets.c +++ b/set_bitsets.c @@ -40,102 +40,104 @@ int nb_one(unsigned long long x) { //the hamming weight of x } int set_size(const set s){ - return *(s.size); + return s->size; } set empty_set(int n){ assert(n > 0); - set res; int i; - res.N = n; - res.size = malloc(sizeof(int)); - *(res.size) = 0; int NC = nbCells(n); - res.tab = malloc((SCOD*NC)/8); + + char *p = malloc(sizeof(struct bitset_descriptor) + (SCOD * NC) / 8); + set res = (struct bitset_descriptor*)p; + + res->tab = (unsigned long long*)((char*)(p + sizeof(struct bitset_descriptor))); + res->N = n; + res->size = 0; + for(i = 0; i < NC; i++) - res.tab[i] = (unsigned long long) (0); + res->tab[i] = (unsigned long long) (0); return res; } set copy_set(const set s){ - set res = empty_set(s.N); - *(res.size) = *(s.size); - int NC = nbCells(s.N), i; + set res = empty_set(s->N); + res->size = s->size; + int NC = nbCells(s->N), i; for(i = 0; i < NC; i++) - res.tab[i] = s.tab[i]; + res->tab[i] = s->tab[i]; return res; } void delete_set(set a){ - free(a.tab); - free(a.size); + free(a); } void set_union_ip(set a, const set b){ - if(a.N != b.N){ + if(a->N != b->N){ printf("Union failed : the sets don't have the same size\n"); - assert(a.N == b.N); + assert(a->N == b->N); } - int NC = nbCells(a.N), i; - *(a.size)=0; + int NC = nbCells(a->N), i; + a->size=0; for(i = 0; i < NC; i++) { - a.tab[i] = a.tab[i]|b.tab[i]; - *(a.size) += nb_one(a.tab[i]); + a->tab[i] = a->tab[i]|b->tab[i]; + a->size += nb_one(a->tab[i]); } } void set_inter_ip(set a, const set b){ - if(a.N != b.N){ + if(a->N != b->N){ printf("Intersection failed : the sets don't have the same size\n"); - assert(a.N == b.N); + assert(a->N == b->N); } - int NC = nbCells(a.N), i; - *(a.size)=0; + int NC = nbCells(a->N), i; + a->size=0; for(i = 0; i < NC; i++){ - a.tab[i] = a.tab[i]&b.tab[i]; - *(a.size) += nb_one(a.tab[i]); + a->tab[i] = a->tab[i]&b->tab[i]; + a->size += nb_one(a->tab[i]); } - assert((a.N%SCOD == 0) || (a.tab[NC-1]>>(a.N%SCOD)) == 0); + assert((a->N%SCOD == 0) || (a->tab[NC-1]>>(a->N%SCOD)) == 0); } void set_diff_ip(set a, const set b){ - if(a.N != b.N){ + if(a->N != b->N){ printf("Difference failed : the sets don't have the same size\n"); - assert(a.N == b.N); + assert(a->N == b->N); } - int NC = nbCells(a.N), i; - *(a.size)=0; + int NC = nbCells(a->N), i; + a->size = 0; for(i = 0; i < NC; i++) { - a.tab[i] = a.tab[i] & (~b.tab[i]); - *(a.size) += nb_one(a.tab[i]); + a->tab[i] = a->tab[i] & (~b->tab[i]); + a->size += nb_one(a->tab[i]); } - assert((a.N%SCOD == 0) || (a.tab[NC-1]>>(a.N%SCOD)) == 0); + assert((a->N%SCOD == 0) || (a->tab[NC-1]>>(a->N%SCOD)) == 0); } bool is_set_empty(const set s){ - return (*(s.size) == 0); + return (s->size == 0); } bool sets_equal(const set a, const set b){ - if(a.N != b.N) + if(a->N != b->N) return false; - int i, NC = nbCells(a.N); + int i, NC = nbCells(a->N); for(i = 0; i < NC; i++){ - if(a.tab[i] != b.tab[i]) + if(a->tab[i] != b->tab[i]) return false; } - assert(*(a.size) == *(b.size)); + assert(a->size == b->size); return true; } inline bool set_mem(int x, const set s){ unsigned long long ux = x; - if (!(x < s.N && x >= 0)) { + if (!(x < s->N && x >= 0)) { printf("Invalid argument for set_mem : %d\n", x); - assert(x < s.N && x >= 0); + assert(x < s->N && x >= 0); } - return (s.tab[ux/SCOD]>>(ux%SCOD))&1; + return (s->tab[ux/SCOD]>>(ux%SCOD))&1; } int dyadic_val(unsigned long long x){ @@ -149,10 +151,10 @@ int dyadic_val(unsigned long long x){ } int elt_of_set(const set s){ - int N=nbCells(s.N), i; + int N=nbCells(s->N), i; for(i=0; itab[i] != 0) + return i*SCOD + dyadic_val(s->tab[i]); printf("No element in an empty set!\n"); dump_set(s); @@ -160,15 +162,15 @@ int elt_of_set(const set s){ } int elt_of_set_heur(const set s, int h){ - int N=nbCells(s.N), i, cell; + int N=nbCells(s->N), i, cell; - if(s.tab[h/SCOD]>>(h%SCOD) !=0) - return h + dyadic_val(s.tab[h/SCOD]>>(h%SCOD)) ; + if(s->tab[h/SCOD]>>(h%SCOD) !=0) + return h + dyadic_val(s->tab[h/SCOD]>>(h%SCOD)) ; for(i=0; itab[cell] != 0) + return cell*SCOD + dyadic_val(s->tab[cell]); } printf("No element in an empty set!\n"); @@ -177,39 +179,39 @@ int elt_of_set_heur(const set s, int h){ } void set_add_ip(int x, set s){ - assert(x < s.N); + assert(x < s->N); unsigned long long ux = x; if(! set_mem(ux, s)){ - s.tab[ux/SCOD] = s.tab[ux/SCOD] | (unsigned long long)(1)<<(ux%SCOD); - *(s.size) = *(s.size)+1; + s->tab[ux/SCOD] = s->tab[ux/SCOD] | (unsigned long long)(1)<<(ux%SCOD); + s->size = s->size+1; } } void set_remove_ip(int x, set s){ unsigned long long ux = x; if(set_mem(ux, s) ) { - s.tab[ux/SCOD] = s.tab[ux/SCOD] & (~((unsigned long long)(1)<<(ux%SCOD))); - *(s.size) = *(s.size)-1; + s->tab[ux/SCOD] = s->tab[ux/SCOD] & (~((unsigned long long)(1)<<(ux%SCOD))); + s->size = s->size-1; } } void dump_set(const set s){ int i=0; printf("["); - for(i=0; i < s.N; i++) + for(i=0; i < s->N; i++) if(set_mem(i, s)) printf(" %d ", i); - printf("] (%d)\n", *(s.size)); + printf("] (%d)\n", s->size); } set full_set(int n) { set r = empty_set(n); - *(r.size) = n; + r->size = n; int NC=nbCells(n), i; for(i=0; i< NC; i++) - r.tab[i]=0xFFFFFFFFFFFFFFFF; - r.tab[NC-1] = ( r.tab[NC-1]>>( (SCOD-(n%SCOD))%SCOD ) ); - assert((n%SCOD == 0) || (r.tab[NC-1]>>(n%SCOD)) == 0); + r->tab[i]=0xFFFFFFFFFFFFFFFF; + r->tab[NC-1] = ( r->tab[NC-1]>>( (SCOD-(n%SCOD))%SCOD ) ); + assert((n%SCOD == 0) || (r->tab[NC-1]>>(n%SCOD)) == 0); return r; } diff --git a/sets.h b/sets.h index c161e03..9082ae2 100644 --- a/sets.h +++ b/sets.h @@ -13,11 +13,11 @@ #include #ifdef BITSETS -typedef struct { +typedef struct bitset_descriptor { int N; // Capacity of set (range of possible elements : 0..N-1) - int *size; // Number of elements actually in the set + int size; // Number of elements actually in the set unsigned long long* tab; -} set; +} *set; #endif #ifdef LINKEDLISTS -- cgit v1.2.3