Class: BitField

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/evasion-db/vendor/bitfield.rb

Overview

NAME: BitField

   AUTHOR: Peter Cooper
  LICENSE: MIT ( http://www.opensource.org/licenses/mit-license.php )
COPYRIGHT: (c) 2007 Peter Cooper (http://www.petercooper.co.uk/)
  VERSION: v4
  HISTORY: v4 (fixed bug where setting 0 bits to 0 caused a set to 1)
           v3 (supports dynamic bitwidths for array elements.. now doing 32 bit widths default)
           v2 (now uses 1 << y, rather than 2 ** y .. it's 21.8 times faster!)
           v1 (first release)

DESCRIPTION: Basic, pure Ruby bit field. Pretty fast (for what it is) and memory efficient.

I've written a pretty intensive test suite for it and it passes great. 
Works well for Bloom filters (the reason I wrote it).

Create a bit field 1000 bits wide
  bf = BitField.new(1000)

Setting and reading bits
  bf[100] = 1
  bf[100]    .. => 1
  bf[100] = 0

More
  bf.to_s = "10101000101010101"  (example)
  bf.total_set         .. => 10  (example - 10 bits are set to "1")

Constant Summary collapse

ELEMENT_WIDTH = 
32

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(size) ⇒ BitField

Returns a new instance of BitField.



32
33
34
35
 
# File 'lib/evasion-db/vendor/bitfield.rb', line 32

def initialize(size)
  @size = size
  @field = Array.new(((size - 1) / ELEMENT_WIDTH) + 1, 0)
end

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



27
28
29
 
# File 'lib/evasion-db/vendor/bitfield.rb', line 27

def size
  @size
end

Instance Method Details

#[](position) ⇒ Object

Read a bit (1/0)



47
48
49
 
# File 'lib/evasion-db/vendor/bitfield.rb', line 47

def [](position)
  @field[position / ELEMENT_WIDTH] & 1 << (position % ELEMENT_WIDTH) > 0 ? 1 : 0
end

#[]=(position, value) ⇒ Object

Set a bit (1/0)



38
39
40
41
42
43
44
 
# File 'lib/evasion-db/vendor/bitfield.rb', line 38

def []=(position, value)
  if value == 1
    @field[position / ELEMENT_WIDTH] |= 1 << (position % ELEMENT_WIDTH)
  elsif (@field[position / ELEMENT_WIDTH]) & (1 << (position % ELEMENT_WIDTH)) != 0
    @field[position / ELEMENT_WIDTH] ^= 1 << (position % ELEMENT_WIDTH)
  end
end

#each(&block) ⇒ Object

Iterate over each bit



52
53
54
 
# File 'lib/evasion-db/vendor/bitfield.rb', line 52

def each(&block)
  @size.times { |position| yield self[position] }
end

#to_s ⇒ Object

Returns the field as a string like “0101010100111100,” etc.



57
58
59
 
# File 'lib/evasion-db/vendor/bitfield.rb', line 57

def to_s
  inject("") { |a, b| a + b.to_s }
end

#total_set ⇒ Object

Returns the total number of bits that are set (The technique used here is about 6 times faster than using each or inject direct on the bitfield)



63
64
65
 
# File 'lib/evasion-db/vendor/bitfield.rb', line 63

def total_set
  @field.inject(0) { |a, byte| a += byte & 1 and byte >>= 1 until byte == 0; a }
end