summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--set_bitsets.c122
-rw-r--r--sets.h6
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
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 12:26:25 +0000