// A bit field is an important data structure in computer science, major uses include memory allocators and Bloom filters.
// The code is in the form of a header file and an implementation file.
1
2 <bitfield.h>
3 // This class is a code snippet, it can be freely used and distributed.
4 // Author: irfan[dot]hamid[at]gmail[dot]com
5 //
6 // Bit fields are a widely used mechanism in computing applications.
7 // Typical applications include memory allocators and Bloom filters. This class
8 // provides a generic bit field implementation for an arbitrary number of bits.
9 //
10 // Implementation notes:
11 // The use of C++ allows the clean separation of the data structure from the
12 // interface. The bit field is implemented as a vector of unsigned int that is
13 // allocated at object creation.
14 //
15 // field: The vector that represents the bit field itself
16 // bit_count: The total number of bits in the bit field
17
18
19
20
21
22
23 class Bitfield
24 {
25 protected:
26 unsigned int *field;
27 unsigned int bit_count;
28
29 public:
30 Bitfield (int bc);
31 ~Bitfield ();
32
33 int set (int bit);
34 int get (int bit);
35 int reset (int bit);
36 };
37
38
39 </bitfield.h>
40
41 <bitfield.cpp>
42
43
44
45 // The constructor takes an int param which gives the number of bits in this
46 // bit field.
47 Bitfield::Bitfield (int bc)
48 {
49 bit_count = bc;
50
51 // E.g, ceil(257/32*8) = 65, 64 ints fully used, last one partially used
52 field = (unsigned int*) malloc(((int) ceil(bc/SZ_UINT*8)));
53 }
54
55 Bitfield::~Bitfield ()
56 {
57 if (field)
58 free(field);
59 }
60
61 // This function sets the corresponding bit in the field equal to 1.
62 //
63 // Returns: 0 on success, -1 on error.
64 int Bitfield::set (int bit)
65 {
66 // Sanity check
67 if (bit >= bit_count || !field)
68 return -1;
69
70 // The correct index into the vector will be given by bit/SZ_UNIT. The
71 // index into the correct vector element is given by bit%SZ_UNIT, to
72 // achieve this, simply left shift 0x01 the appropriate number of times.
73 field[bit/SZ_UINT] |= (0x00000001 << (bit%(SZ_UINT*8)-1));
74 return 0;
75 }
76
77 // This function sets the corresponding bit in the field equal to 0.
78 //
79 // Returns: 0 on success, -1 on error.
80 int Bitfield::reset (int bit)
81 {
82 if (bit >= bit_count || !field)
83 return -1;
84 field[bit/SZ_UINT] &= ~(0x00000001 << (bit%(SZ_UINT*8)-1));
85 return 0;
86 }
87
88 // This function returns the value of the corresponding bit.
89 //
90 // Returns: The value of the bit, if the field is initialized and bit index is
91 // within bounds, -1 otherwise.
92 int Bitfield::get (int bit)
93 {
94 if (bit >= bit_count || !field)
95 return -1;
96 return (field[bit/SZ_UINT] & (0x00000001 << (bit%(SZ_UINT*8)-1)) ? 1 : 0);
97 }
98 </bitfield.cpp>
