blob: cfd1cd2811164a2c08d95440595535f8d3bf82f7 [file] [log] [blame]
// Copyright 2013 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
#include <u.h>
#include <libc.h>
#include "go.h"
enum {
WORDSIZE = sizeof(uint32),
WORDBITS = 32,
WORDMASK = WORDBITS - 1,
WORDSHIFT = 5,
};
static uintptr
bvsize(uintptr n)
{
return ((n + WORDBITS - 1) / WORDBITS) * WORDSIZE;
}
int32
bvbits(Bvec *bv)
{
return bv->n;
}
int32
bvwords(Bvec *bv)
{
return (bv->n + WORDBITS - 1) / WORDBITS;
}
Bvec*
bvalloc(int32 n)
{
Bvec *bv;
uintptr nbytes;
if(n < 0)
fatal("bvalloc: initial size is negative\n");
nbytes = sizeof(Bvec) + bvsize(n);
bv = malloc(nbytes);
if(bv == nil)
fatal("bvalloc: malloc failed\n");
memset(bv, 0, nbytes);
bv->n = n;
return bv;
}
/* difference */
void
bvandnot(Bvec *dst, Bvec *src1, Bvec *src2)
{
int32 i, w;
if(dst->n != src1->n || dst->n != src2->n)
fatal("bvand: lengths %d, %d, and %d are not equal", dst->n, src1->n, src2->n);
for(i = 0, w = 0; i < dst->n; i += WORDBITS, w++)
dst->b[w] = src1->b[w] & ~src2->b[w];
}
int
bvcmp(Bvec *bv1, Bvec *bv2)
{
uintptr nbytes;
if(bv1->n != bv2->n)
fatal("bvequal: lengths %d and %d are not equal", bv1->n, bv2->n);
nbytes = bvsize(bv1->n);
return memcmp(bv1->b, bv2->b, nbytes);
}
void
bvcopy(Bvec *dst, Bvec *src)
{
memmove(dst->b, src->b, bvsize(dst->n));
}
Bvec*
bvconcat(Bvec *src1, Bvec *src2)
{
Bvec *dst;
int32 i;
dst = bvalloc(src1->n + src2->n);
for(i = 0; i < src1->n; i++)
if(bvget(src1, i))
bvset(dst, i);
for(i = 0; i < src2->n; i++)
if(bvget(src2, i))
bvset(dst, i + src1->n);
return dst;
}
int
bvget(Bvec *bv, int32 i)
{
if(i < 0 || i >= bv->n)
fatal("bvget: index %d is out of bounds with length %d\n", i, bv->n);
return (bv->b[i>>WORDSHIFT] >> (i&WORDMASK)) & 1;
}
// bvnext returns the smallest index >= i for which bvget(bv, i) == 1.
// If there is no such index, bvnext returns -1.
int
bvnext(Bvec *bv, int32 i)
{
uint32 w;
if(i >= bv->n)
return -1;
// Jump i ahead to next word with bits.
if((bv->b[i>>WORDSHIFT]>>(i&WORDMASK)) == 0) {
i &= ~WORDMASK;
i += WORDBITS;
while(i < bv->n && bv->b[i>>WORDSHIFT] == 0)
i += WORDBITS;
}
if(i >= bv->n)
return -1;
// Find 1 bit.
w = bv->b[i>>WORDSHIFT]>>(i&WORDMASK);
while((w&1) == 0) {
w>>=1;
i++;
}
return i;
}
int
bvisempty(Bvec *bv)
{
int32 i;
for(i = 0; i < bv->n; i += WORDBITS)
if(bv->b[i>>WORDSHIFT] != 0)
return 0;
return 1;
}
void
bvnot(Bvec *bv)
{
int32 i, w;
for(i = 0, w = 0; i < bv->n; i += WORDBITS, w++)
bv->b[w] = ~bv->b[w];
}
/* union */
void
bvor(Bvec *dst, Bvec *src1, Bvec *src2)
{
int32 i, w;
if(dst->n != src1->n || dst->n != src2->n)
fatal("bvor: lengths %d, %d, and %d are not equal", dst->n, src1->n, src2->n);
for(i = 0, w = 0; i < dst->n; i += WORDBITS, w++)
dst->b[w] = src1->b[w] | src2->b[w];
}
/* intersection */
void
bvand(Bvec *dst, Bvec *src1, Bvec *src2)
{
int32 i, w;
if(dst->n != src1->n || dst->n != src2->n)
fatal("bvor: lengths %d, %d, and %d are not equal", dst->n, src1->n, src2->n);
for(i = 0, w = 0; i < dst->n; i += WORDBITS, w++)
dst->b[w] = src1->b[w] & src2->b[w];
}
void
bvprint(Bvec *bv)
{
int32 i;
print("#*");
for(i = 0; i < bv->n; i++)
print("%d", bvget(bv, i));
}
void
bvreset(Bvec *bv, int32 i)
{
uint32 mask;
if(i < 0 || i >= bv->n)
fatal("bvreset: index %d is out of bounds with length %d\n", i, bv->n);
mask = ~(1 << (i % WORDBITS));
bv->b[i / WORDBITS] &= mask;
}
void
bvresetall(Bvec *bv)
{
memset(bv->b, 0x00, bvsize(bv->n));
}
void
bvset(Bvec *bv, int32 i)
{
uint32 mask;
if(i < 0 || i >= bv->n)
fatal("bvset: index %d is out of bounds with length %d\n", i, bv->n);
mask = 1U << (i % WORDBITS);
bv->b[i / WORDBITS] |= mask;
}