#include <u.h>#include <libc.h>#include <bio.h>#include "dat.h"#include "fns.h" BitSet *bsnew(int max){ int n; BitSet *b; n = max + 31 >> 5; b = emalloc(sizeof(BitSet) + n * 4); b->n = n; return b;} BitSet *bsgrow(BitSet *b, int n){ if(b == nil) return bsnew(n); n = n + 31 >> 5; b = realloc(b, sizeof(BitSet) + n * 4); if(n > b->n) memset(b->p + n, 0, n - b->n); return b;} BitSet *bsdup(BitSet *b){ BitSet *c; c = bsnew(b->n << 5); bscopy(c, b); return c;} voidbsreset(BitSet *b){ int i; for(i = 0; i < b->n; i++) b->p[i] = 0;} voidbscopy(BitSet *d, BitSet *s){ int i; for(i = 0; i < d->n; i++) d->p[i] = s->p[i];} intbsadd(BitSet *b, int i){ u32int c, r; c = 1 << (i & 31); r = b->p[i / 32] & c; b->p[i / 32] |= c; return r;} intbsrem(BitSet *b, int i){ u32int c, r; c = 1 << (i & 31); r = b->p[i / 32] & c; b->p[i / 32] &= ~c; return r;} intbstest(BitSet *b, int i){ return (b->p[i / 32] & 1<<(i & 31)) != 0;} intbscmp(BitSet *b, BitSet *c){ int i; if(b->n != c->n) return 1; for(i = 0; i < b->n; i++) if(b->p[i] != c->p[i]) return 1; return 0;} voidbsunion(BitSet *r, BitSet *a, BitSet *b){ int i; assert(r->n == a->n && a->n == b->n); for(i = 0; i < r->n; i++) r->p[i] = a->p[i] | b->p[i];} voidbsminus(BitSet *r, BitSet *a, BitSet *b){ int i; assert(r->n == a->n && a->n == b->n); for(i = 0; i < r->n; i++) r->p[i] = a->p[i] & ~b->p[i];} voidbsinter(BitSet *r, BitSet *a, BitSet *b){ int i; assert(r->n == a->n && a->n == b->n); for(i = 0; i < r->n; i++) r->p[i] = a->p[i] & b->p[i];} intpopcnt(u32int v){ v = v - ((v >> 1) & 0x55555555); v = (v & 0x33333333) + ((v >> 2) & 0x33333333); v = (v + (v >> 4)) & 0x0f0f0f0f; v = v + (v >> 8); v = v + (v >> 16); return v & 0x3f;} intscanset(u32int v){ return 32 - popcnt(v | -v);} intbsiter(BitSet *b, int i){ u32int v, j; i++; j = i >> 5; i = i & 31; if(j >= b->n) return -1; v = b->p[j] & -(1 << i); while(v == 0){ if(++j >= b->n) return -1; v = b->p[j]; } return 32 - popcnt(v | -v) | j << 5;} intbscnt(BitSet *b){ int i, n; for(i = n = 0; i < b->n; i++) n += popcnt(b->p[i]); return n;} voidbscntgr(BitSet *b, BitSet *a, int *yp, int *np){ int i, y, n; assert(b->n == a->n); for(i = n = y = 0; i < b->n; i++){ y += popcnt(b->p[i] & a->p[i]); n += popcnt(b->p[i] & ~a->p[i]); } *yp = y; *np = n;} intsetfmt(Fmt *f){ int rc, k, fi, s; BitSet *b; b = va_arg(f->args, BitSet *); rc = fmtrune(f, '('); fi = 0; s = f->flags & FmtSign; for(k = -1; (k = bsiter(b, k)) >= 0; ){ if(fi++ != 0) rc += fmtrune(f, ','); if(s) rc += fmtprint(f, "%J", targs[k]); else rc += fmtprint(f, "%d", k); } rc += fmtrune(f, ')'); return rc;}
#include <u.h>
#include <libc.h>
#include <bio.h>
#include "dat.h"
#include "fns.h"
BitSet *
bsnew(int max)
{
int n;
BitSet *b;
n = max + 31 >> 5;
b = emalloc(sizeof(BitSet) + n * 4);
b->n = n;
return b;
}
BitSet *
bsgrow(BitSet *b, int n)
{
if(b == nil)
return bsnew(n);
n = n + 31 >> 5;
b = realloc(b, sizeof(BitSet) + n * 4);
if(n > b->n)
memset(b->p + n, 0, n - b->n);
return b;
}
BitSet *
bsdup(BitSet *b)
{
BitSet *c;
c = bsnew(b->n << 5);
bscopy(c, b);
return c;
}
void
bsreset(BitSet *b)
{
int i;
for(i = 0; i < b->n; i++)
b->p[i] = 0;
}
void
bscopy(BitSet *d, BitSet *s)
{
int i;
for(i = 0; i < d->n; i++)
d->p[i] = s->p[i];
}
int
bsadd(BitSet *b, int i)
{
u32int c, r;
c = 1 << (i & 31);
r = b->p[i / 32] & c;
b->p[i / 32] |= c;
return r;
}
int
bsrem(BitSet *b, int i)
{
u32int c, r;
c = 1 << (i & 31);
r = b->p[i / 32] & c;
b->p[i / 32] &= ~c;
return r;
}
int
bstest(BitSet *b, int i)
{
return (b->p[i / 32] & 1<<(i & 31)) != 0;
}
int
bscmp(BitSet *b, BitSet *c)
{
int i;
if(b->n != c->n)
return 1;
for(i = 0; i < b->n; i++)
if(b->p[i] != c->p[i])
return 1;
return 0;
}
void
bsunion(BitSet *r, BitSet *a, BitSet *b)
{
int i;
assert(r->n == a->n && a->n == b->n);
for(i = 0; i < r->n; i++)
r->p[i] = a->p[i] | b->p[i];
}
void
bsminus(BitSet *r, BitSet *a, BitSet *b)
{
int i;
assert(r->n == a->n && a->n == b->n);
for(i = 0; i < r->n; i++)
r->p[i] = a->p[i] & ~b->p[i];
}
void
bsinter(BitSet *r, BitSet *a, BitSet *b)
{
int i;
assert(r->n == a->n && a->n == b->n);
for(i = 0; i < r->n; i++)
r->p[i] = a->p[i] & b->p[i];
}
int
popcnt(u32int v)
{
v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
v = (v + (v >> 4)) & 0x0f0f0f0f;
v = v + (v >> 8);
v = v + (v >> 16);
return v & 0x3f;
}
int
scanset(u32int v)
{
return 32 - popcnt(v | -v);
}
int
bsiter(BitSet *b, int i)
{
u32int v, j;
i++;
j = i >> 5;
i = i & 31;
if(j >= b->n)
return -1;
v = b->p[j] & -(1 << i);
while(v == 0){
if(++j >= b->n)
return -1;
v = b->p[j];
}
return 32 - popcnt(v | -v) | j << 5;
}
int
bscnt(BitSet *b)
{
int i, n;
for(i = n = 0; i < b->n; i++)
n += popcnt(b->p[i]);
return n;
}
void
bscntgr(BitSet *b, BitSet *a, int *yp, int *np)
{
int i, y, n;
assert(b->n == a->n);
for(i = n = y = 0; i < b->n; i++){
y += popcnt(b->p[i] & a->p[i]);
n += popcnt(b->p[i] & ~a->p[i]);
}
*yp = y;
*np = n;
}
int
setfmt(Fmt *f)
{
int rc, k, fi, s;
BitSet *b;
b = va_arg(f->args, BitSet *);
rc = fmtrune(f, '(');
fi = 0;
s = f->flags & FmtSign;
for(k = -1; (k = bsiter(b, k)) >= 0; ){
if(fi++ != 0)
rc += fmtrune(f, ',');
if(s)
rc += fmtprint(f, "%J", targs[k]);
else
rc += fmtprint(f, "%d", k);
}
rc += fmtrune(f, ')');
return rc;
}