Commits

James Taylor  committed aa96179

Binned bitsets now use two sentinals, ALL_ONE for bins containing all ones and ALL_ZERO for bins containing all zeros. Boolean operations (and, or, not) implemented (with tests).

  • Participants
  • Parent commits a6a797a

Comments (0)

Files changed (4)

File bx/bitset.pyx

     int binBitsCountRange( BinBits *bb, int start, int size )
     int binBitsFindSet( BinBits *bb, int start )
     int binBitsFindClear( BinBits *bb, int start )
-
+    void binBitsAnd( BinBits *bb1, BinBits *bb2 )
+    void binBitsOr( BinBits *bb1, BinBits *bb2 )
+    void binBitsNot( BinBits *bb )
 
 cdef class BitSet:
     cdef Bits * bits
     def ior( self, BitSet other ): 
         bitOr( self.bits, other.bits, self.bitCount )
 
-    def bitXor( self, BitSet other ): 
+    def ixor( self, BitSet other ): 
         bitXor( self.bits, other.bits, self.bitCount )
 
     def invert( self ):
     property size:
         def __get__( self ):
             return self.bb.size
+    def iand( self, BinnedBitSet other ):
+        binBitsAnd( self.bb, other.bb )
+    def ior( self, BinnedBitSet other ):
+        binBitsOr( self.bb, other.bb )
+    def invert( self ):
+        binBitsNot( self.bb )

File bx/bitset_tests.py

         self.assertEquals( bits.next_clear( 11 ), 14 )
         self.assertEquals( bits.next_clear( 20 ), 75 )
         self.assertEquals( bits.next_clear( 92 ), 100 )
-       
+
+    def test_and( self ):
+        bits1 = self.new_bits( 100 )
+        bits2 = self.new_bits( 100 )
+        bits1.set_range( 20, 40 )
+        bits2.set_range( 50, 25 )
+        bits1.iand( bits2 )
+        l = [0]*100
+        for i in range( 50, 60 ): l[i] = 1
+        self.assert_bits( bits1, l )
+    
+    def test_or( self ):
+        bits1 = self.new_bits( 100 )
+        bits2 = self.new_bits( 100 )
+        bits1.set_range( 20, 40 )
+        bits2.set_range( 50, 25 )
+        bits1.ior( bits2 )
+        l = [0]*100
+        for i in range( 20, 75 ): l[i] = 1
+        self.assert_bits( bits1, l )
+        
+    def test_not( self ):
+        bits = self.new_bits( 100 )
+        bits.set_range( 20, 40 )
+        bits.invert()
+        l = [1]*100
+        for i in range( 20, 60 ): l[i] = 0
+        self.assert_bits( bits, l )
+        
 class BitsetTests( AbstractTests ):
     def new_bits( self, size ):
         return bx.bitset.BitSet( size ) 

File src/binBits.c

 #include "bits.h"
 #include "binBits.h"
 
+static Bits * ALL_ZERO = NULL;
+static Bits * ALL_ONE = ( Bits * ) &"ONE";
+
 struct BinBits* binBitsAlloc( int size, int granularity )
 {
     struct BinBits * bb;
 
 void binBitsFree( struct BinBits *bb )
 {
-  int i;
-  for ( i = 0; i < bb->nbins; i++ )
-  {
-      if ( bb->bins[i] != NULL )
-      {
-          bitFree( bb->bins[i] );
-      }
-      freeMem( bb );
-  }
+    int i;
+    for ( i = 0; i < bb->nbins; i++ )
+    {
+        if ( ( bb->bins[i] != ALL_ZERO ) && ( bb->bins[i] != ALL_ONE ) )
+        {
+            bitFree( &(bb->bins[i]) );
+        }
+    }
+    freeMem( bb );
 }
     
 inline int binBitsGetBin( struct BinBits * bb, int pos )
 boolean binBitsReadOne( struct BinBits * bb, int pos )
 {
     int bin = binBitsGetBin( bb, pos );
-    if ( bb->bins[bin] )
+    
+    if ( bb->bins[bin] == ALL_ZERO )
     {
-        return bitReadOne( bb->bins[bin], binBitsGetOffset( bb, pos ) );
+        return 0;
+    }
+    else if ( bb->bins[bin] == ALL_ONE )
+    {
+        return 1;
     }
     else
     {
-        return 0;
+        return bitReadOne( bb->bins[bin], binBitsGetOffset( bb, pos ) );
     }
 }
 
 {
     int bin = binBitsGetBin( bb, pos );  
     int offset = binBitsGetOffset( bb, pos );
-    if ( bb->bins[bin] == NULL )
+    if ( bb->bins[bin] == ALL_ONE )
+    {
+        return;
+    }
+    if ( bb->bins[bin] == ALL_ZERO )
     {
         bb->bins[bin] = bitAlloc( bb->bin_size );
     }
 {
     int bin = binBitsGetBin( bb, pos );  
     int offset = binBitsGetOffset( bb, pos );
-    if ( bb->bins[bin] != NULL )
+    if ( bb->bins[bin] == ALL_ZERO )
     {
-        bitClearOne( bb->bins[bin], offset );
+        return;
     }
+    if ( bb->bins[bin] == ALL_ONE )
+    {
+        bb->bins[bin] = bitAlloc( bb->bin_size );
+        bitSetRange( bb->bins[bin], 0, bb->bin_size );
+    }
+    bitClearOne( bb->bins[bin], offset );
 }
 
 void binBitsSetRange( struct BinBits *bb, int start, int size )
     int bin, offset, delta;
     while ( size > 0 )
     {
-        int bin = binBitsGetBin( bb, start );  
-        int offset = binBitsGetOffset( bb, start );
-        if ( bb->bins[bin] == NULL )
+        bin = binBitsGetBin( bb, start );  
+        offset = binBitsGetOffset( bb, start );
+        if ( bb->bins[bin] == ALL_ZERO )
         {
             bb->bins[bin] = bitAlloc( bb->bin_size );   
         }
+        else if ( bb->bins[bin] == ALL_ONE )
+        {
+            bb->bins[bin] = bitAlloc( bb->bin_size );
+            bitSetRange( bb->bins[bin], 0, bb->bin_size );
+        }
         delta = bb->bin_size - offset;
         if ( delta < size )
         {
         int bin = binBitsGetBin( bb, start );  
         int offset = binBitsGetOffset( bb, start );
         delta = bb->bin_size - offset;
-        if ( bb->bins[bin] == NULL )
+        if ( bb->bins[bin] == ALL_ZERO )
         {
             if ( delta < size )
             {
                 size = 0;
             }
         }
+        else if ( bb->bins[bin] == ALL_ONE )
+        {
+            if ( delta < size )
+            {
+                count += ( delta - offset );
+                size -= delta;
+                start += delta;
+            }
+            else
+            {
+                count += ( size - offset );
+                size = 0;
+            }
+        }
         else if ( delta < size )
         {
             count += bitCountRange( bb->bins[bin], offset, delta );
     int offset = binBitsGetOffset( bb, start );
     while ( bin < bb->nbins )
     {
-        if ( bb->bins[bin] != NULL )
+        if ( bb->bins[bin] == ALL_ONE )
+        {
+            return bin * bb->bin_size + offset;
+        }
+        else if ( bb->bins[bin] != ALL_ZERO )
         {
             ns = bitFindSet( bb->bins[bin], offset, bb->bin_size );
             if ( ns < bb->bin_size )
     int offset = binBitsGetOffset( bb, start );
     while ( bin < bb->nbins )
     {
-        if ( bb->bins[bin] == NULL )
+        if ( bb->bins[bin] == ALL_ZERO )
         {
-            return bin*bb->bin_size;
+            return bin*bb->bin_size + offset;
         }
-        else
+        else if ( bb->bins[bin] != ALL_ONE )
         {
             ns = bitFindClear( bb->bins[bin], offset, bb->bin_size );
             if ( ns < bb->bin_size )
     }
     return bb->size;
 }
+
+void binBitsAnd( struct BinBits *bb1, struct BinBits *bb2 )
+{
+    int i;    
+    assert( bb1->bin_size == bb2->bin_size && bb1->nbins == bb2->nbins && bb1->size == bb2->size );
+
+    for ( i = 0; i < bb1->nbins; i++ )
+    {
+        if ( bb1->bins[i] == ALL_ZERO )
+        {
+            // Do nothing
+        }
+        else if ( bb2->bins[i] == ALL_ZERO )
+        {
+            bitFree( &bb1->bins[i] );
+            bb1->bins[i] = ALL_ZERO;
+        }
+        else if ( bb1->bins[i] == ALL_ONE )
+        {
+            if ( bb2->bins[i] == ALL_ONE )
+            {
+                // Do nothing
+            }
+            else if ( bb2->bins[i] == ALL_ZERO )
+            {
+                bb1->bins[i] = ALL_ZERO;
+            }
+            else
+            {
+                bb1->bins[i] = bitClone( bb2->bins[i], bb1->bin_size );
+            }
+        }
+        else
+        {
+            bitAnd( bb1->bins[i], bb2->bins[i], bb1->bin_size );
+        }
+    }
+}
+
+void binBitsOr( struct BinBits *bb1, struct BinBits *bb2 )
+{
+    int i;    
+    assert( bb1->bin_size == bb2->bin_size && bb1->nbins == bb2->nbins && bb1->size == bb2->size );
+
+    for ( i = 0; i < bb1->nbins; i++ )
+    {
+        if ( bb1->bins[i] == ALL_ONE )
+        {
+            // Do nothing
+        }
+        else if ( bb2->bins[i] == ALL_ONE )
+        {
+            bitFree( &bb1->bins[i] );
+            bb1->bins[i] = ALL_ONE;
+        }
+        else if ( bb1->bins[i] == ALL_ZERO )
+        {
+            if ( bb2->bins[i] == ALL_ZERO )
+            {
+                // Do nothing
+            }
+            else if ( bb2->bins[i] == ALL_ONE )
+            {
+                bb1->bins[i] = ALL_ONE;
+            }
+            else
+            {
+                bb1->bins[i] = bitClone( bb2->bins[i], bb1->bin_size );
+            }
+        }
+        else
+        {
+            bitOr( bb1->bins[i], bb2->bins[i], bb1->bin_size );
+        }
+    }
+}
+
+void binBitsNot( struct BinBits *bb )
+{
+    int i;    
+
+    for ( i = 0; i < bb->nbins; i++ )
+    {
+        if ( bb->bins[i] == ALL_ONE )
+        {
+            bb->bins[i] = ALL_ZERO;
+        }
+        else if ( bb->bins[i] == ALL_ZERO )
+        {
+            bb->bins[i] = ALL_ONE;
+        }
+        else
+        {
+            bitNot( bb->bins[i], bb->bin_size );
+        }
+    }
+}

File src/binBits.h

 int binBitsCountRange( struct BinBits *bb, int start, int size );
 int binBitsFindSet( struct BinBits *bb, int start );
 int binBitsFindClear( struct BinBits *bb, int start );
+void binBitsAnd( struct BinBits *bb1, struct BinBits *bb2 );
+void binBitsOr( struct BinBits *bb1, struct BinBits *bb2 );
+void binBitsNot( struct BinBits *bb );
 
 #endif