view release on metacpan or  search on metacpan

lib/KinoSearch1/Util/BitVector.pm  view on Meta::CPAN

package KinoSearch1::Util::BitVector;
use strict;
use warnings;
use KinoSearch1::Util::ToolSet;
use base qw( KinoSearch1::Util::CClass );

BEGIN {
    __PACKAGE__->init_instance_vars(
        # constructor params
        capacity => 0,
    );
}

1;

__END__

__XS__

MODULE = KinoSearch1    PACKAGE = KinoSearch1::Util::BitVector

void
new(either_sv, ...)
    SV        *either_sv;
PREINIT:
    const char *class;
    HV         *args_hash;
    U32         capacity;
    BitVector  *bit_vec;
PPCODE:
    /* determine the class */
    class = sv_isobject(either_sv) 
        ? sv_reftype(either_sv, 0) 
        : SvPV_nolen(either_sv);

    /* process hash-style params */
    Kino1_Verify_build_args_hash(args_hash, 
        "KinoSearch1::Util::BitVector::instance_vars", 1);
    capacity = (U32)SvUV( Kino1_Verify_extract_arg(args_hash, "capacity", 8) );

    /* build object */
    bit_vec = Kino1_BitVec_new(capacity);
    ST(0)   = sv_newmortal();
    sv_setref_pv(ST(0), class, (void*)bit_vec);
    XSRETURN(1);


=for comment
Return true if the bit indcated by $num has been set, false if it hasn't
(regardless of whether $num lies within the bounds of the object's capacity).

=cut

bool
get(bit_vec, num)
    BitVector *bit_vec;
    U32        num;
CODE:
    RETVAL = Kino1_BitVec_get(bit_vec, num);
OUTPUT: RETVAL

=for comment
Set the bit at $num to 1.

=cut

void
set(bit_vec, ...)
    BitVector *bit_vec;
PREINIT:
    U32 i, num;
PPCODE:
    for (i = 1; i < items; i++) {
        num = (U32)( SvUV( ST(i) ) );
        Kino1_BitVec_set(bit_vec, num);
    }

=for comment
Clear the bit at $num (i.e. set it to 0).

=cut

void
clear(bit_vec, num)
    BitVector *bit_vec;
    U32        num;
PPCODE:
    Kino1_BitVec_clear(bit_vec, num);

=for comment
Set all the bits bounded by $first and $last, inclusive, to 1.

=cut

void
bulk_set(bit_vec, first, last)
    BitVector *bit_vec;
    U32        first;
    U32        last;
PPCODE:
    Kino1_BitVec_bulk_set(bit_vec, first, last);
    
=for comment
Clear all the bits bounded by $first and $last, inclusive.

=cut

void
bulk_clear(bit_vec, first, last)
    BitVector *bit_vec;
    U32        first;
    U32        last;
PPCODE:
    Kino1_BitVec_bulk_clear(bit_vec, first, last);

=for comment
Given $num, return either $num (if it is set), the next set bit above it, or
if no such bit exists, undef (from Perl) or a sentinel (0xFFFFFFFF) from C.

=cut
    
SV*
next_set_bit(bit_vec, num)
    BitVector *bit_vec;
    U32        num;
CODE:
    num    = Kino1_BitVec_next_set_bit(bit_vec, num);
    RETVAL = num == KINO_BITVEC_SENTINEL ? &PL_sv_undef : newSVuv(num);
OUTPUT: RETVAL

=for comment
Given $num, return $num (if it is clear), or the next clear bit above it.
The highest number that next_clear_bit can return is the object's capacity.

=cut

SV*
next_clear_bit(bit_vec, num)
    BitVector *bit_vec;
    U32        num;
CODE:
    num = Kino1_BitVec_next_clear_bit(bit_vec, num);
    RETVAL = num == KINO_BITVEC_SENTINEL ? &PL_sv_undef : newSVuv(num);
OUTPUT: RETVAL

=for comment
Modify the BitVector so that only bits which remain set are those which 1)
were already set in this BitVector, and 2) were also set in the other
BitVector.

=cut

void
logical_and(bit_vec, other)
    BitVector *bit_vec;
    BitVector *other;
PPCODE:
    Kino1_BitVec_logical_and(bit_vec, other);


=for comment
Return a count of the number of set bits in the BitVector.

=cut

U32
count(bit_vec)
    BitVector *bit_vec;
CODE:
    RETVAL = Kino1_BitVec_count(bit_vec);
OUTPUT: RETVAL


=for comment
Return an arrayref of the with each element the number of a set bit.

=cut

void
to_arrayref(bit_vec)
    BitVector *bit_vec;
PREINIT:
    AV *out_av;
PPCODE:
    out_av = Kino1_BitVec_to_array(bit_vec);
    XPUSHs( sv_2mortal(newRV_noinc( (SV*)out_av )) );
    XSRETURN(1);
    

=for comment
Setters and getters.  A quirk: set_bits automatically adjusts capacity
upwards to the appropriate multiple of 8 if necessary.

=cut

SV* 
_set_or_get(bit_vec, ...)
    BitVector *bit_vec;
ALIAS:
    set_capacity = 1
    get_capacity = 2
    set_bits     = 3
    get_bits     = 4
PREINIT:
    STRLEN  len;
    U32     new_capacity;
    char   *new_bits;
CODE:
{
    KINO_START_SET_OR_GET_SWITCH

    case 1:  new_capacity = SvUV(ST(1));
             if (new_capacity < bit_vec->capacity) {
                 Kino1_BitVec_shrink(bit_vec, new_capacity);
             }
             else if (new_capacity > bit_vec->capacity) {
                 Kino1_BitVec_grow(bit_vec, new_capacity);
             }
             /* fall through */
    case 2:  RETVAL = newSVuv(bit_vec->capacity);
             break;

    case 3:  Kino1_Safefree(bit_vec->bits);
             new_bits          = SvPV(ST(1), len);
             bit_vec->bits     = (unsigned char*)Kino1_savepvn(new_bits, len);
             bit_vec->capacity = len << 3;
             /* fall through */
    case 4:  len = ceil(bit_vec->capacity / 8.0);
             RETVAL = newSVpv((char*)bit_vec->bits, len);
             break;

    KINO_END_SET_OR_GET_SWITCH
}
OUTPUT: RETVAL


void
DESTROY(bit_vec)
    BitVector *bit_vec;
PPCODE:
    Kino1_BitVec_destroy(bit_vec);


__H__

#ifndef H_KINO_BIT_VECTOR
#define H_KINO_BIT_VECTOR 1

#include "limits.h"
#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"
#include "KinoSearch1UtilMathUtils.h"
#include "KinoSearch1UtilCarp.h"
#include "KinoSearch1UtilMemManager.h"

#define KINO_BITVEC_SENTINEL 0xFFFFFFFF

typedef struct bitvector {
    U32            capacity;
    unsigned char *bits;
} BitVector;

BitVector* Kino1_BitVec_new(U32);
BitVector* Kino1_BitVec_clone(BitVector*);
void Kino1_BitVec_grow(BitVector*, U32);
void Kino1_BitVec_shrink(BitVector *, U32);
void Kino1_BitVec_set(BitVector*, U32);
void Kino1_BitVec_clear(BitVector*, U32);
void Kino1_BitVec_bulk_set(BitVector*, U32, U32);
void Kino1_BitVec_bulk_clear(BitVector*, U32, U32);
bool Kino1_BitVec_get(BitVector*, U32);
U32  Kino1_BitVec_next_set_bit(BitVector*, U32);
U32  Kino1_BitVec_next_clear_bit(BitVector*, U32);
void Kino1_BitVec_logical_and(BitVector*, BitVector*);
U32  Kino1_BitVec_count(BitVector*);
AV*  Kino1_BitVec_to_array(BitVector*);
void Kino1_BitVec_destroy(BitVector*);

#endif /* include guard */

__C__

#include "KinoSearch1UtilBitVector.h"

static unsigned char bitmasks[] = { 
    0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80,
};

BitVector*
Kino1_BitVec_new(U32 capacity) {
    BitVector *bit_vec;
    Kino1_New(0, bit_vec, 1, BitVector);
    bit_vec->capacity = 0;
    bit_vec->bits = NULL;
    Kino1_BitVec_grow(bit_vec, capacity);
    return bit_vec;
}

BitVector*