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.store; |
7 | |
8 | import org.h2.engine.Session; |
9 | import org.h2.util.BitField; |
10 | |
11 | /** |
12 | * The list of free pages of a page store. The format of a free list trunk page |
13 | * is: |
14 | * <ul> |
15 | * <li>page type: byte (0)</li> |
16 | * <li>checksum: short (1-2)</li> |
17 | * <li>data (3-)</li> |
18 | * </ul> |
19 | */ |
20 | public class PageFreeList extends Page { |
21 | |
22 | private static final int DATA_START = 3; |
23 | |
24 | private final PageStore store; |
25 | private final BitField used; |
26 | private final int pageCount; |
27 | private boolean full; |
28 | private Data data; |
29 | |
30 | private PageFreeList(PageStore store, int pageId) { |
31 | // kept in cache, and array list in page store |
32 | setPos(pageId); |
33 | this.store = store; |
34 | pageCount = (store.getPageSize() - DATA_START) * 8; |
35 | used = new BitField(pageCount); |
36 | used.set(0); |
37 | } |
38 | |
39 | /** |
40 | * Read a free-list page. |
41 | * |
42 | * @param store the page store |
43 | * @param data the data |
44 | * @param pageId the page id |
45 | * @return the page |
46 | */ |
47 | static PageFreeList read(PageStore store, Data data, int pageId) { |
48 | PageFreeList p = new PageFreeList(store, pageId); |
49 | p.data = data; |
50 | p.read(); |
51 | return p; |
52 | } |
53 | |
54 | /** |
55 | * Create a new free-list page. |
56 | * |
57 | * @param store the page store |
58 | * @param pageId the page id |
59 | * @return the page |
60 | */ |
61 | static PageFreeList create(PageStore store, int pageId) { |
62 | return new PageFreeList(store, pageId); |
63 | } |
64 | |
65 | /** |
66 | * Allocate a page from the free list. |
67 | * |
68 | * @param exclude the exclude list or null |
69 | * @param first the first page to look for |
70 | * @return the page, or -1 if all pages are used |
71 | */ |
72 | int allocate(BitField exclude, int first) { |
73 | if (full) { |
74 | return -1; |
75 | } |
76 | // TODO cache last result |
77 | int start = Math.max(0, first - getPos()); |
78 | while (true) { |
79 | int free = used.nextClearBit(start); |
80 | if (free >= pageCount) { |
81 | if (start == 0) { |
82 | full = true; |
83 | } |
84 | return -1; |
85 | } |
86 | if (exclude != null && exclude.get(free + getPos())) { |
87 | start = exclude.nextClearBit(free + getPos()) - getPos(); |
88 | if (start >= pageCount) { |
89 | return -1; |
90 | } |
91 | } else { |
92 | // set the bit first, because logUndo can |
93 | // allocate other pages, and we must not |
94 | // return the same page twice |
95 | used.set(free); |
96 | store.logUndo(this, data); |
97 | store.update(this); |
98 | return free + getPos(); |
99 | } |
100 | } |
101 | } |
102 | |
103 | /** |
104 | * Get the first free page starting at the given offset. |
105 | * |
106 | * @param first the page number to start the search |
107 | * @return the page number, or -1 |
108 | */ |
109 | int getFirstFree(int first) { |
110 | if (full) { |
111 | return -1; |
112 | } |
113 | int start = Math.max(0, first - getPos()); |
114 | int free = used.nextClearBit(start); |
115 | if (free >= pageCount) { |
116 | return -1; |
117 | } |
118 | return free + getPos(); |
119 | } |
120 | |
121 | int getLastUsed() { |
122 | int last = used.length() - 1; |
123 | return last <= 0 ? -1 : last + getPos(); |
124 | } |
125 | |
126 | /** |
127 | * Mark a page as used. |
128 | * |
129 | * @param pageId the page id |
130 | */ |
131 | void allocate(int pageId) { |
132 | int idx = pageId - getPos(); |
133 | if (idx >= 0 && !used.get(idx)) { |
134 | // set the bit first, because logUndo can |
135 | // allocate other pages, and we must not |
136 | // return the same page twice |
137 | used.set(idx); |
138 | store.logUndo(this, data); |
139 | store.update(this); |
140 | } |
141 | } |
142 | |
143 | /** |
144 | * Add a page to the free list. |
145 | * |
146 | * @param pageId the page id to add |
147 | */ |
148 | void free(int pageId) { |
149 | full = false; |
150 | store.logUndo(this, data); |
151 | used.clear(pageId - getPos()); |
152 | store.update(this); |
153 | } |
154 | |
155 | /** |
156 | * Read the page from the disk. |
157 | */ |
158 | private void read() { |
159 | data.reset(); |
160 | data.readByte(); |
161 | data.readShortInt(); |
162 | for (int i = 0; i < pageCount; i += 8) { |
163 | int x = data.readByte() & 255; |
164 | used.setByte(i, x); |
165 | } |
166 | full = false; |
167 | } |
168 | |
169 | @Override |
170 | public void write() { |
171 | data = store.createData(); |
172 | data.writeByte((byte) Page.TYPE_FREE_LIST); |
173 | data.writeShortInt(0); |
174 | for (int i = 0; i < pageCount; i += 8) { |
175 | data.writeByte((byte) used.getByte(i)); |
176 | } |
177 | store.writePage(getPos(), data); |
178 | } |
179 | |
180 | /** |
181 | * Get the number of pages that can fit in a free list. |
182 | * |
183 | * @param pageSize the page size |
184 | * @return the number of pages |
185 | */ |
186 | public static int getPagesAddressed(int pageSize) { |
187 | return (pageSize - DATA_START) * 8; |
188 | } |
189 | |
190 | /** |
191 | * Get the estimated memory size. |
192 | * |
193 | * @return number of double words (4 bytes) |
194 | */ |
195 | @Override |
196 | public int getMemory() { |
197 | return store.getPageSize() >> 2; |
198 | } |
199 | |
200 | /** |
201 | * Check if a page is already in use. |
202 | * |
203 | * @param pageId the page to check |
204 | * @return true if it is in use |
205 | */ |
206 | boolean isUsed(int pageId) { |
207 | return used.get(pageId - getPos()); |
208 | } |
209 | |
210 | @Override |
211 | public void moveTo(Session session, int newPos) { |
212 | // the old data does not need to be copied, as free-list pages |
213 | // at the end of the file are not required |
214 | store.free(getPos(), false); |
215 | } |
216 | |
217 | @Override |
218 | public String toString() { |
219 | return "page [" + getPos() + "] freeList" + (full ? "full" : ""); |
220 | } |
221 | |
222 | @Override |
223 | public boolean canRemove() { |
224 | return true; |
225 | } |
226 | |
227 | @Override |
228 | public boolean canMove() { |
229 | return false; |
230 | } |
231 | |
232 | } |