1 | // -*- C++ -*- |
---|
2 | |
---|
3 | /* |
---|
4 | |
---|
5 | Heap Layers: An Extensible Memory Allocation Infrastructure |
---|
6 | |
---|
7 | Copyright (C) 2000-2004 by Emery Berger |
---|
8 | http://www.cs.umass.edu/~emery |
---|
9 | emery@cs.umass.edu |
---|
10 | |
---|
11 | This program is free software; you can redistribute it and/or modify |
---|
12 | it under the terms of the GNU General Public License as published by |
---|
13 | the Free Software Foundation; either version 2 of the License, or |
---|
14 | (at your option) any later version. |
---|
15 | |
---|
16 | This program is distributed in the hope that it will be useful, |
---|
17 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
18 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
---|
19 | GNU General Public License for more details. |
---|
20 | |
---|
21 | You should have received a copy of the GNU General Public License |
---|
22 | along with this program; if not, write to the Free Software |
---|
23 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
---|
24 | |
---|
25 | */ |
---|
26 | |
---|
27 | /** |
---|
28 | * @file bitstring.h |
---|
29 | * @brief A bit string data structure for use in memory allocators. |
---|
30 | * @author Emery Berger <http://www.cs.umass.edu/~emery> |
---|
31 | */ |
---|
32 | |
---|
33 | #ifndef _BITSTRING_H_ |
---|
34 | #define _BITSTRING_H_ |
---|
35 | |
---|
36 | #include <assert.h> |
---|
37 | |
---|
38 | template <int N> |
---|
39 | class BitString { |
---|
40 | public: |
---|
41 | |
---|
42 | BitString (void) { |
---|
43 | clear(); |
---|
44 | } |
---|
45 | |
---|
46 | inline void clear (void) { |
---|
47 | for (int i = 0; i < NUM_ULONGS; i++) { |
---|
48 | B[i] = ALL_ALLOCATED; |
---|
49 | } |
---|
50 | firstPos = 0; |
---|
51 | } |
---|
52 | |
---|
53 | // Bit = 1 == allocated. |
---|
54 | int allocate (int length, int alignment) { |
---|
55 | // Start at the first entry. |
---|
56 | for (int bitPos = firstPos; bitPos < N; ) { |
---|
57 | // If the whole entry here is allocated, |
---|
58 | // skip to the next one. |
---|
59 | if (B[bitPos >> SHIFTS_PER_ULONG] == ALL_ALLOCATED) { |
---|
60 | bitPos = ((bitPos >> SHIFTS_PER_ULONG) + 1) << SHIFTS_PER_ULONG; |
---|
61 | // Adjust for alignment if needed. |
---|
62 | while ((bitPos % alignment) != 0) { |
---|
63 | bitPos++; |
---|
64 | } |
---|
65 | continue; |
---|
66 | } |
---|
67 | // If this bit is set, skip to the next one. |
---|
68 | if (get(bitPos)) { |
---|
69 | bitPos += alignment; |
---|
70 | continue; |
---|
71 | } |
---|
72 | // Got something free -- let's see if we have a run of the requisite length. |
---|
73 | bool gotOne = true; |
---|
74 | for (int j = 0; j < length; j++) { |
---|
75 | if (get(bitPos + j)) { |
---|
76 | gotOne = false; |
---|
77 | bitPos += j; |
---|
78 | // Adjust for alignment if needed. |
---|
79 | while ((bitPos % alignment) != 0) { |
---|
80 | bitPos++; |
---|
81 | } |
---|
82 | break; |
---|
83 | } |
---|
84 | } |
---|
85 | if (gotOne) { |
---|
86 | // We found one - claim it! |
---|
87 | for (int j = 0; j < length; j++) { |
---|
88 | set(bitPos + j); |
---|
89 | } |
---|
90 | return bitPos; |
---|
91 | } |
---|
92 | } |
---|
93 | // Error - none found. |
---|
94 | return -1; |
---|
95 | } |
---|
96 | |
---|
97 | void free (int bitPos, int length) { |
---|
98 | for (int j = bitPos; j < bitPos + length; j++) { |
---|
99 | reset (j); |
---|
100 | } |
---|
101 | } |
---|
102 | |
---|
103 | #if 0 |
---|
104 | inline int first (void) const { |
---|
105 | for (int i = 0; i < NUM_ULONGS; i++) { |
---|
106 | if (B[i] > 0) { |
---|
107 | unsigned long index = 1U << (BITS_PER_ULONG-1); |
---|
108 | for (int j = 0; j < BITS_PER_ULONG; j++) { |
---|
109 | if (B[i] & index) { |
---|
110 | return j + i * BITS_PER_ULONG; |
---|
111 | } |
---|
112 | index >>= 1; |
---|
113 | } |
---|
114 | } |
---|
115 | } |
---|
116 | return -1; |
---|
117 | } |
---|
118 | #endif |
---|
119 | |
---|
120 | inline int firstAfter (const int index) const { |
---|
121 | #if 0 |
---|
122 | for (int i = index; i < N; i++ ) { |
---|
123 | int ind = i >> SHIFTS_PER_ULONG; |
---|
124 | if (B[ind] & (1U << (i & (BITS_PER_ULONG - 1)))) { |
---|
125 | return i; |
---|
126 | } |
---|
127 | } |
---|
128 | return -1; |
---|
129 | #else |
---|
130 | int indmask = index - (index >> SHIFTS_PER_ULONG) * BITS_PER_ULONG; |
---|
131 | for (int i = index >> SHIFTS_PER_ULONG; i < NUM_ULONGS; i++) { |
---|
132 | if (B[i]) { |
---|
133 | unsigned long bitval = B[i]; |
---|
134 | bitval &= ~((1 << (indmask & (BITS_PER_ULONG - 1))) - 1); |
---|
135 | if (bitval) { |
---|
136 | return (i * BITS_PER_ULONG + lsb(bitval)); |
---|
137 | } |
---|
138 | } |
---|
139 | indmask = indmask - BITS_PER_ULONG; |
---|
140 | if (indmask < 0) { |
---|
141 | indmask = 0; |
---|
142 | } |
---|
143 | } |
---|
144 | return -1; |
---|
145 | #endif |
---|
146 | } |
---|
147 | |
---|
148 | inline bool get (const int index) const { |
---|
149 | assert (index >= 0); |
---|
150 | assert (index < N); |
---|
151 | int ind = index >> SHIFTS_PER_ULONG; |
---|
152 | assert (ind >= 0); |
---|
153 | assert (ind < NUM_ULONGS); |
---|
154 | return (B[ind] & (1U << (index & (BITS_PER_ULONG - 1)))); |
---|
155 | } |
---|
156 | |
---|
157 | inline void set (const int index) { |
---|
158 | assert (index >= 0); |
---|
159 | assert (index < N); |
---|
160 | int ind = index >> SHIFTS_PER_ULONG; |
---|
161 | assert (ind >= 0); |
---|
162 | assert (ind < NUM_ULONGS); |
---|
163 | B[ind] |= (1U << (index & (BITS_PER_ULONG - 1))); |
---|
164 | if (index < firstPos) { |
---|
165 | firstPos = index; |
---|
166 | } |
---|
167 | } |
---|
168 | |
---|
169 | inline void reset (const int index) { |
---|
170 | assert (index >= 0); |
---|
171 | assert (index < N); |
---|
172 | int ind = index >> SHIFTS_PER_ULONG; |
---|
173 | assert (ind >= 0); |
---|
174 | assert (ind < NUM_ULONGS); |
---|
175 | B[ind] &= ~(1U << (index & (BITS_PER_ULONG - 1))); |
---|
176 | } |
---|
177 | |
---|
178 | unsigned long operator() (int index) { |
---|
179 | assert (index >= 0); |
---|
180 | assert (index < NUM_ULONGS); |
---|
181 | return B[index]; |
---|
182 | } |
---|
183 | |
---|
184 | |
---|
185 | private: |
---|
186 | |
---|
187 | #if 1 // (sizeof(unsigned long),4) |
---|
188 | enum { BITS_PER_ULONG = 32 }; |
---|
189 | enum { SHIFTS_PER_ULONG = 5 }; |
---|
190 | #else |
---|
191 | enum { BITS_PER_ULONG = 64 }; |
---|
192 | enum { SHIFTS_PER_ULONG = 6 }; |
---|
193 | #endif |
---|
194 | |
---|
195 | enum { ALL_ALLOCATED = (unsigned long) -1 }; |
---|
196 | enum { MAX_BITS = (N + BITS_PER_ULONG - 1) & ~(BITS_PER_ULONG - 1) }; |
---|
197 | enum { NUM_ULONGS = MAX_BITS / BITS_PER_ULONG }; |
---|
198 | |
---|
199 | unsigned long B[NUM_ULONGS]; |
---|
200 | |
---|
201 | /// The first set position. |
---|
202 | int firstPos; |
---|
203 | |
---|
204 | inline static int lsb (unsigned long b) { |
---|
205 | static const int index32[32] = { 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 }; |
---|
206 | const unsigned long debruijn32 = 0x077CB531UL; |
---|
207 | b &= (unsigned long) -((signed long) b); |
---|
208 | b *= debruijn32; |
---|
209 | b >>= 27; |
---|
210 | assert (b >= 0); |
---|
211 | assert (b < 32); |
---|
212 | return index32[b]; |
---|
213 | } |
---|
214 | |
---|
215 | }; |
---|
216 | |
---|
217 | |
---|
218 | #endif |
---|