ref: dfdd1961a70d071736ccdc9741cfc58380674241
dir: /bitvector.c/
/*
bit vector primitives
todo:
* reverse
* nreverse
(- rotate left/right)
* shl_to
* not
- shr_row, shl_row
These routines are the back end supporting bit matrices. Many operations
on bit matrices are slow (such as accessing or setting a single element!)
but certain operations are privileged and lend themselves to extremely
efficient implementation due to the bit-vector nature of machine integers.
These are:
done:
& | $ ~ copy reverse fill sum prod
todo:
shift trans rowswap
would be nice:
channel interleave
Important note:
Out-of-place functions always assume dest and source have the same amount
of space available.
shr_to, shl_to, not_to, and reverse_to assume source and dest don't overlap
and_to, or_to, and xor_to allow overlap.
*/
#include "llt.h"
uint32_t *
bitvector_resize(uint32_t *b, uint64_t oldsz, uint64_t newsz, int initzero)
{
uint32_t *p;
size_t sz = ((newsz+31)>>5) * sizeof(uint32_t);
p = LLT_REALLOC(b, sz);
if(p == nil)
return nil;
if(initzero && newsz>oldsz){
size_t osz = ((oldsz+31)>>5) * sizeof(uint32_t);
memset(&p[osz/sizeof(uint32_t)], 0, sz-osz);
}
return p;
}
uint32_t *
bitvector_new(uint64_t n, int initzero)
{
return bitvector_resize(nil, 0, n, initzero);
}
size_t
bitvector_nwords(uint64_t nbits)
{
return (nbits+31)>>5;
}
void
bitvector_set(uint32_t *b, uint64_t n, uint32_t c)
{
if(c)
b[n>>5] |= 1<<(n&31);
else
b[n>>5] &= ~(1<<(n&31));
}
uint32_t
bitvector_get(uint32_t *b, uint64_t n)
{
return b[n>>5] & (1<<(n&31));
}