#include "util.h" #include "bv.h" unsigned int pm[32] = {0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020, 0x00000040, 0x00000080, 0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000, 0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000, 0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000}; unsigned int nm[32] = {0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFB, 0xFFFFFFF7, 0xFFFFFFEF, 0xFFFFFFDF, 0xFFFFFFBF, 0xFFFFFF7F, 0xFFFFFEFF, 0xFFFFFDFF, 0xFFFFFBFF, 0xFFFFF7FF, 0xFFFFEFFF, 0xFFFFDFFF, 0xFFFFBFFF, 0xFFFF7FFF, 0xFFFEFFFF, 0xFFFDFFFF, 0xFFFBFFFF, 0xFFF7FFFF, 0xFFEFFFFF, 0xFFDFFFFF, 0xFFBFFFFF, 0xFF7FFFFF, 0xFEFFFFFF, 0xFDFFFFFF, 0xFBFFFFFF, 0xF7FFFFFF, 0xEFFFFFFF, 0xDFFFFFFF, 0xBFFFFFFF, 0x7FFFFFFF}; BV bv_alloc(n) int n;{ BV b = (BV) MALLOC (sizeof (*b)); n = (n == 0) ? 1 : n; b -> length = n; b -> vector = (unsigned int *) MALLOC (n * sizeof (unsigned int)); return b; } unsigned int * bv_vector_alloc(n) int n; { return (unsigned int *) MALLOC (n * sizeof (unsigned int)); } BV bv_new(n) int n; { REGISTER BV bv; REGISTER int i; n = ITOY(n); bv = bv_alloc(n); n = bv -> length; for (i = 0; i < n; i++) bv->vector[i] = 0; return bv; } BV bv_copy(bv) REGISTER BV bv; { REGISTER BV bvnew; REGISTER UINT i; REGISTER UINT size = bv -> length; bvnew = bv_alloc(size); for (i = 0; i < size; i++) bvnew->vector[i] = bv->vector[i]; return bvnew; } BV bv_assign(bv,bvnew) BV bv,bvnew; { REGISTER UINT size = bv -> length; REGISTER UINT i; REGISTER UINT * v1; REGISTER UINT * v2; if (bvnew -> length < size) /* We'll need to reallocate */ { free (bvnew -> vector); bvnew -> vector = bv_vector_alloc(size); bvnew -> length = size; } v1 = bv -> vector; v2 = bvnew -> vector; for (i = 0; i < size; i++) v2[i] = v1[i]; if (bvnew -> length > size) /* We'll need to clean out the end */ { size = bvnew -> length; for (i = bv -> length; i < size; i++) v2[i] = 0; } return bvnew; } BV bv_and(bv1,bv2) BV bv1; BV bv2; { REGISTER BV bvnew; REGISTER UINT i; REGISTER UINT size = bv1 -> length; REGISTER UINT * v1; REGISTER UINT * v2; REGISTER UINT * v3; if (size > bv2 -> length) size = bv2 -> length; bvnew = bv_alloc(size); v1 = bv1 -> vector; v2 = bv2 -> vector; v3 = bvnew -> vector; for (i = 0; i < size; i++) { v3[i] = v1[i] & v2[i]; } return bvnew; } int bv_intersects(bv1,bv2) REGISTER BV bv1; REGISTER BV bv2; { REGISTER UINT * v_end; REGISTER UINT size = bv1 -> length; REGISTER UINT * v1; REGISTER UINT * v2; if (size > bv2 -> length) size = bv2 -> length; v1 = bv1 -> vector; v2 = bv2 -> vector; v_end = size + v1; while (v1 < v_end) { if (*v1++ & *v2++) return -1; } return 0; } BV bv_andto(bv1,bv2, bvnew) REGISTER BV bv1; REGISTER BV bv2; REGISTER BV bvnew; { REGISTER UINT * v_end; REGISTER UINT size = bv1 -> length; REGISTER UINT * v1; REGISTER UINT * v2; REGISTER UINT * v_to = bvnew -> vector; REGISTER int i; int newlength = bvnew -> length; /* Choose smaller size */ if (size > bv2 -> length) size = bv2 -> length; /* Get these now to avoid aliasing problems */ v1 = bv1 -> vector; v2 = bv2 -> vector; if (size > newlength) { v_to = bv_vector_alloc(size); newlength = size; } for (i = 0; i < size; i ++) v_to[i] = v1[i] & v2[i]; if (newlength > size) /* We'll need to clean out the end */ { REGISTER int larger_size = newlength; REGISTER int i; for (i = size; i < larger_size; i++) v_to[i] = 0; } if (v_to != bvnew -> vector) { free (bvnew -> vector); bvnew -> vector = v_to; bvnew -> length = newlength; } return bvnew; } BV bv_diffto(bv1,bv2, bvnew) BV bv1; BV bv2; BV bvnew; { REGISTER UINT size = bv1 -> length; REGISTER UINT * v1 = bv1 -> vector; REGISTER UINT * v2 = bv2 -> vector; REGISTER UINT * v_to = bvnew -> vector; REGISTER int i; int newlength = bvnew -> length; if (size > newlength) { v_to = bv_vector_alloc(size); newlength = size; } /* Now bvnew is big enough */ for (i = 0; i < size; i ++) { v_to[i] = v1[i] & ~v2[i]; } /* clear out the rest */ size = newlength; for (i = bv1 -> length; i < size; i ++) { v_to[i] = 0; } if (v_to != bvnew -> vector) { free (bvnew -> vector); bvnew -> vector = v_to; bvnew -> length = newlength; } return bvnew; } BV bv_orto(bv1,bv2, bvnew) BV bv1; BV bv2; BV bvnew; { REGISTER UINT size = bv1 -> length; REGISTER UINT * v1; REGISTER UINT * v2; REGISTER UINT * v_to; REGISTER int i; int newlength = bvnew -> length; BV bv_temp; if (size > bv2 -> length) { /* make bv1 shorter */ size = bv2 -> length; bv_temp = bv1; bv1 = bv2; bv2 = bv_temp; } v1 = bv1 -> vector; v2 = bv2 -> vector; if (bv2 -> length > newlength) { v_to = bv_vector_alloc(bv2 -> length); newlength = bv2 -> length; } else v_to = bvnew -> vector; for (i = 0; i < size; i ++) v_to[i] = v1[i] | v2[i]; if (bv2 -> length > bv1 -> length) /* We'll need to clean out the end */ { size = bv2 -> length; for (i = bv1 -> length; i < size; i++) v_to[i] = v2[i]; } if (newlength > bv2 -> length) { size = newlength; for (i = bv2 -> length; i < size; i++) v_to[i] = 0; } if (v_to != bvnew -> vector) { free (bvnew -> vector); bvnew -> vector = v_to; bvnew -> length = newlength; } return bvnew; } bv_eq(bv1,bv2) BV bv1; BV bv2; { REGISTER unsigned int * v1; REGISTER unsigned int * v2; REGISTER int i,size; BV bv_temp; size = bv1 -> length; if (size > bv2 -> length) { size = bv2 -> length; bv_temp = bv1; bv1 = bv2; bv2 = bv_temp; } size = bv2 -> length; v2 = bv2 -> vector; for (i = bv1 -> length; i < size; i ++) { if (v2[i] != 0) return 0; } v1 = bv1 -> vector; size = bv1 -> length; for (i = 0; i < size; i++) { if (v1[i] != v2[i]) return 0; } return -1; } UINT bv_hash(bv) REGISTER BV bv; { REGISTER UINT h = 0; REGISTER UINT * v = bv -> vector; REGISTER UINT * v_end = v + bv -> length; /* Do it from back to front so that all is zero until something interesting happens */ while (v_end > v) h = (h << 5) + (h >> 27) + *(--v_end); return h; } bv_in(bv,i) BV bv; unsigned int i; { unsigned int Y = which_CELL(i); unsigned int B = BIT(i); if (Y >= bv -> length) { return 0; } else return bv -> vector[Y] & pm[B]; } BV bv_insert(bv,i) BV bv; unsigned int i; { unsigned int Y = which_CELL(i); unsigned int B = BIT(i); if (Y >= bv -> length) { unsigned int * v1 = bv_vector_alloc(Y+1); unsigned int * v2 = bv -> vector; REGISTER int i; REGISTER int size = bv -> length; for (i = 0; i < size; i++) v1[i] = v2[i]; for (i = size; i <= Y; i++) v1[i] = 0; bv -> vector = v1; bv -> length = Y + 1; } bv -> vector[Y] |= pm[B]; return bv; } BV bv_remove(bv,i) BV bv; unsigned int i; { unsigned int Y = which_CELL(i); unsigned int B = BIT(i); if (Y >= bv -> length) return bv; bv -> vector[Y] &= nm[B]; return bv; } #ifdef TEST #include bv_p(fd,bv) FILE * fd; BV bv; { UINT size = YTOI(bv -> length); UINT i; for (i = 0; i < size; i++) fprintf(fd, bv_in(bv, i) ? "1" : "0"); } main() { char buffer[256]; int x,y,z,i; int iterating = 1; BV sets[10]; for (i = 0; i < 10; i++) sets[i] = bv_new(1); while (iterating) { printf("And x,y -> z; Or x,y - z; Diff x,y -> z; Eq x,y; \ iNtersects x,y; Insert x to y; Remove x from y; Print x; Quit\n"); scanf("%s", buffer); switch(buffer[0]) { case 'p': case 'P': scanf("%d", &x); if (0 < x && x < 10) { bv_p(stdout, sets[x]); printf("\n"); } else { printf("Something was bogus\n"); } break; case 'i': case 'I': scanf("%d", &x); scanf("%d", &y); if (0 <= x && 0 < y && y < 10 ) { bv_p(stdout, sets[y]); printf(" INSERT \n"); bv_insert(sets[y],x); printf("%d YIELDS\n", x); bv_p(stdout, sets[y]); printf("\n"); } else { printf("Something was bogus\n"); } break; case 'r': case 'R': scanf("%d", &x); scanf("%d", &y); if (0 <= x && 0 < y && y < 10 ) { bv_p(stdout, sets[y]); printf(" REMOVE \n"); bv_remove(sets[y],x); printf("%d YIELDS\n", x); bv_p(stdout, sets[y]); printf("\n"); } else { printf("Something was bogus\n"); } break; case 'n': case 'N': scanf("%d", &x); scanf("%d", &y); if (0 < x && x < 10 && 0 < y && y < 10 ) { i = bv_intersects(sets[x],sets[y]); bv_p(stdout, sets[x]); printf(" INTERSECTS? \n"); bv_p(stdout, sets[y]); printf("\n"); printf("%d\n", i); } else { printf("Something was bogus\n"); } break; case 'e': case 'E': scanf("%d", &x); scanf("%d", &y); if (0 < x && x < 10 && 0 < y && y < 10 ) { i = bv_eq(sets[x],sets[y]); bv_p(stdout, sets[x]); printf(" EQUAL? \n"); bv_p(stdout, sets[y]); printf("\n"); printf("%d\n", i); } else { printf("Something was bogus\n"); } break; case 'a': case 'A': scanf("%d", &x); scanf("%d", &y); scanf("%d", &z); if (0 < x && x < 10 && 0 < y && y < 10 && 0 < z && z < 10 ) { bv_p(stdout, sets[x]); printf(" AND \n"); bv_p(stdout, sets[y]); printf(" YIELDS \n"); bv_andto(sets[x],sets[y],sets[z]); bv_p(stdout, sets[z]); printf("\n"); } else { printf("Something was bogus\n"); } break; case 'o': case 'O': scanf("%d", &x); scanf("%d", &y); scanf("%d", &z); if (0 < x && x < 10 && 0 < y && y < 10 && 0 < z && z < 10 ) { bv_p(stdout, sets[x]); printf(" OR \n"); bv_p(stdout, sets[y]); printf(" YIELDS \n"); bv_orto(sets[x],sets[y],sets[z]); bv_p(stdout, sets[z]); printf("\n"); } else { printf("Something was bogus\n"); } break; case 'd': case 'D': scanf("%d", &x); scanf("%d", &y); scanf("%d", &z); if (0 < x && x < 10 && 0 < y && y < 10 && 0 < z && z < 10 ) { bv_p(stdout, sets[x]); printf(" DIFF \n"); bv_p(stdout, sets[y]); printf(" YIELDS \n"); bv_diffto(sets[x],sets[y],sets[z]); bv_p(stdout, sets[z]); printf("\n"); } else { printf("Something was bogus\n"); } break; case 'q': case 'Q': iterating = 0; break; } } } #endif