1 | /* |
2 | * Copyright 2004-2014 H2 Group. Multiple-Licensed under the MPL 2.0, |
3 | * and the EPL 1.0 (http://h2database.com/html/license.html). |
4 | * Initial Developer: H2 Group |
5 | */ |
6 | package org.h2.mvstore; |
7 | |
8 | import java.util.BitSet; |
9 | |
10 | import org.h2.util.MathUtils; |
11 | |
12 | /** |
13 | * A free space bit set. |
14 | */ |
15 | public class FreeSpaceBitSet { |
16 | |
17 | private static final boolean DETAILED_INFO = false; |
18 | |
19 | /** |
20 | * The first usable block. |
21 | */ |
22 | private final int firstFreeBlock; |
23 | |
24 | /** |
25 | * The block size in bytes. |
26 | */ |
27 | private final int blockSize; |
28 | |
29 | /** |
30 | * The bit set. |
31 | */ |
32 | private final BitSet set = new BitSet(); |
33 | |
34 | /** |
35 | * Create a new free space map. |
36 | * |
37 | * @param firstFreeBlock the first free block |
38 | * @param blockSize the block size |
39 | */ |
40 | public FreeSpaceBitSet(int firstFreeBlock, int blockSize) { |
41 | this.firstFreeBlock = firstFreeBlock; |
42 | this.blockSize = blockSize; |
43 | clear(); |
44 | } |
45 | |
46 | /** |
47 | * Reset the list. |
48 | */ |
49 | public void clear() { |
50 | set.clear(); |
51 | set.set(0, firstFreeBlock); |
52 | } |
53 | |
54 | /** |
55 | * Check whether one of the blocks is in use. |
56 | * |
57 | * @param pos the position in bytes |
58 | * @param length the number of bytes |
59 | * @return true if a block is in use |
60 | */ |
61 | public boolean isUsed(long pos, int length) { |
62 | int start = getBlock(pos); |
63 | int blocks = getBlockCount(length); |
64 | for (int i = start; i < start + blocks; i++) { |
65 | if (!set.get(i)) { |
66 | return false; |
67 | } |
68 | } |
69 | return true; |
70 | } |
71 | |
72 | /** |
73 | * Check whether one of the blocks is free. |
74 | * |
75 | * @param pos the position in bytes |
76 | * @param length the number of bytes |
77 | * @return true if a block is free |
78 | */ |
79 | public boolean isFree(long pos, int length) { |
80 | int start = getBlock(pos); |
81 | int blocks = getBlockCount(length); |
82 | for (int i = start; i < start + blocks; i++) { |
83 | if (set.get(i)) { |
84 | return false; |
85 | } |
86 | } |
87 | return true; |
88 | } |
89 | |
90 | /** |
91 | * Allocate a number of blocks and mark them as used. |
92 | * |
93 | * @param length the number of bytes to allocate |
94 | * @return the start position in bytes |
95 | */ |
96 | public long allocate(int length) { |
97 | int blocks = getBlockCount(length); |
98 | for (int i = 0;;) { |
99 | int start = set.nextClearBit(i); |
100 | int end = set.nextSetBit(start + 1); |
101 | if (end < 0 || end - start >= blocks) { |
102 | set.set(start, start + blocks); |
103 | return getPos(start); |
104 | } |
105 | i = end; |
106 | } |
107 | } |
108 | |
109 | /** |
110 | * Mark the space as in use. |
111 | * |
112 | * @param pos the position in bytes |
113 | * @param length the number of bytes |
114 | */ |
115 | public void markUsed(long pos, int length) { |
116 | int start = getBlock(pos); |
117 | int blocks = getBlockCount(length); |
118 | set.set(start, start + blocks); |
119 | } |
120 | |
121 | /** |
122 | * Mark the space as free. |
123 | * |
124 | * @param pos the position in bytes |
125 | * @param length the number of bytes |
126 | */ |
127 | public void free(long pos, int length) { |
128 | int start = getBlock(pos); |
129 | int blocks = getBlockCount(length); |
130 | set.clear(start, start + blocks); |
131 | } |
132 | |
133 | private long getPos(int block) { |
134 | return (long) block * (long) blockSize; |
135 | } |
136 | |
137 | private int getBlock(long pos) { |
138 | return (int) (pos / blockSize); |
139 | } |
140 | |
141 | private int getBlockCount(int length) { |
142 | return MathUtils.roundUpInt(length, blockSize) / blockSize; |
143 | } |
144 | |
145 | /** |
146 | * Get the fill rate of the space in percent. The value 0 means the space is |
147 | * completely free, and 100 means it is completely full. |
148 | * |
149 | * @return the fill rate (0 - 100) |
150 | */ |
151 | public int getFillRate() { |
152 | int total = set.length(), count = 0; |
153 | for (int i = 0; i < total; i++) { |
154 | if (set.get(i)) { |
155 | count++; |
156 | } |
157 | } |
158 | if (count == 0) { |
159 | return 0; |
160 | } |
161 | return Math.max(1, (int) (100L * count / total)); |
162 | } |
163 | |
164 | /** |
165 | * Get the position of the first free space. |
166 | * |
167 | * @return the position. |
168 | */ |
169 | public long getFirstFree() { |
170 | return getPos(set.nextClearBit(0)); |
171 | } |
172 | |
173 | @Override |
174 | public String toString() { |
175 | StringBuilder buff = new StringBuilder(); |
176 | if (DETAILED_INFO) { |
177 | int onCount = 0, offCount = 0; |
178 | int on = 0; |
179 | for (int i = 0; i < set.length(); i++) { |
180 | if (set.get(i)) { |
181 | onCount++; |
182 | on++; |
183 | } else { |
184 | offCount++; |
185 | } |
186 | if ((i & 1023) == 1023) { |
187 | buff.append(String.format("%3x", on)).append(' '); |
188 | on = 0; |
189 | } |
190 | } |
191 | buff.append("\n"); |
192 | buff.append(" on " + onCount + " off " + offCount); |
193 | buff.append(" " + 100 * onCount / (onCount+offCount) + "% used "); |
194 | } |
195 | buff.append('['); |
196 | for (int i = 0;;) { |
197 | if (i > 0) { |
198 | buff.append(", "); |
199 | } |
200 | int start = set.nextClearBit(i); |
201 | buff.append(Integer.toHexString(start)).append('-'); |
202 | int end = set.nextSetBit(start + 1); |
203 | if (end < 0) { |
204 | break; |
205 | } |
206 | buff.append(Integer.toHexString(end - 1)); |
207 | i = end + 1; |
208 | } |
209 | buff.append(']'); |
210 | return buff.toString(); |
211 | } |
212 | |
213 | } |