[176] | 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 |
---|