1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
# encoding: utf-8
module AMQ
# Very minimalistic, pure Ruby implementation of bit set. Inspired by java.util.BitSet,
# although significantly smaller in scope.
#
# Originally part of amqp gem. Extracted to make it possible for Bunny to use it.
class BitSet
attr_reader :words_in_use
#
# API
#
ADDRESS_BITS_PER_WORD = 6
BITS_PER_WORD = (1 << ADDRESS_BITS_PER_WORD)
WORD_MASK = 0xffffffffffffffff
# @param [Integer] Number of bits in the set
# @api public
def initialize(nbits)
@nbits = nbits
self.init_words(nbits)
end # initialize(nbits)
# Sets (flags) given bit. This method allows bits to be set more than once in a row, no exception will be raised.
#
# @param [Integer] A bit to set
# @api public
def set(i)
check_range(i)
w = self.word_index(i)
result = @words[w] |= (1 << (i % BITS_PER_WORD))
result
end # set(i)
# Fetches flag value for given bit.
#
# @param [Integer] A bit to fetch
# @return [Boolean] true if given bit is set, false otherwise
# @api public
def get(i)
check_range(i)
w = self.word_index(i)
(@words[w] & (1 << i % BITS_PER_WORD)) != 0
end # get(i)
alias [] get
# Unsets (unflags) given bit. This method allows bits to be unset more than once in a row, no exception will be raised.
#
# @param [Integer] A bit to unset
# @api public
def unset(i)
check_range(i)
w = self.word_index(i)
return if w.nil?
result = @words[w] &= ~(1 << i % BITS_PER_WORD)
result
end # unset(i)
# Clears all bits in the set
# @api public
def clear
self.init_words(@nbits)
end # clear
def next_clear_bit()
@words.each_with_index do |word, i|
if word == WORD_MASK
next
end
return i * BITS_PER_WORD + BitSet.number_of_trailing_ones(word)
end
-1
end # next_clear_bit
def to_s
result = ""
@words.each do |w|
result += w.to_s(2).rjust(BITS_PER_WORD,'0') + ":"
end
result
end # to_s
#
# Implementation
#
# @private
def self.number_of_trailing_ones(num)
0.upto(BITS_PER_WORD) do |bit|
return bit if num[bit] == 0
end
BITS_PER_WORD
end # number_of_trailing_ones
# @private
def word_index(i)
i >> ADDRESS_BITS_PER_WORD
end # word_index
protected
# @private
def init_words(nbits)
n = word_index(nbits-1) + 1
@words = Array.new(n) { 0 }
end # init_words
def check_range(i)
if i < 0 || i >= @nbits
raise IndexError.new("Cannot access bit #{i} from a BitSet with #{@nbits} bits")
end
end # check_range
end # BitSet
end # AMQ
|
