Improved bitset implementation

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; i<N; i++)
-		if(s.tab[i] != 0)
-		    return i*SCOD + dyadic_val(s.tab[i]);
+		if(s->tab[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; i<N; i++) {
 		cell = (i + h/SCOD + 1) % N;
-		if(s.tab[cell] != 0)
-			return cell*SCOD + dyadic_val(s.tab[cell]);
+		if(s->tab[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 <stdbool.h>
 
 #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