File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\store\PageFreeList.java.html

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