|
1
14
15 package org.apache.activemq.kaha.impl.index.tree;
16
17 import java.io.File  ;
18 import java.io.IOException ;
19 import java.io.RandomAccessFile ;
20 import java.util.concurrent.atomic.AtomicBoolean ;
21 import org.apache.activemq.kaha.Marshaller;
22 import org.apache.activemq.kaha.StoreEntry;
23 import org.apache.activemq.kaha.impl.index.Index;
24 import org.apache.activemq.kaha.impl.index.IndexManager;
25 import org.apache.activemq.util.DataByteArrayInputStream;
26 import org.apache.activemq.util.DataByteArrayOutputStream;
27 import org.apache.activemq.util.LRUCache;
28 import org.apache.commons.logging.Log;
29 import org.apache.commons.logging.LogFactory;
30
31
36 public class TreeIndex implements Index{
37
38 private static final String NAME_PREFIX="tree-index-";
39 private static final int DEFAULT_PAGE_SIZE;
40 private static final int DEFAULT_KEY_SIZE;
41 private static final Log log=LogFactory.getLog(TreeIndex.class);
42 private final String name;
43 private File directory;
44 private File file;
45 private RandomAccessFile indexFile;
46 private IndexManager indexManager;
47 private int pageSize=DEFAULT_PAGE_SIZE;
48 private int keySize=DEFAULT_KEY_SIZE;
49 private int keysPerPage=pageSize/keySize;
50 private TreePage root;
51 private LRUCache<Long ,TreePage> pageCache;
52 private DataByteArrayInputStream dataIn;
53 private DataByteArrayOutputStream dataOut;
54 private byte[] readBuffer;
55 private Marshaller keyMarshaller;
56 private long length=0;
57 private TreePage firstFree;
58 private TreePage lastFree;
59 private AtomicBoolean loaded=new AtomicBoolean ();
60 private boolean enablePageCaching=true;
61 private int pageCacheSize=10;
62
63
71 public TreeIndex(File directory,String name,IndexManager indexManager) throws IOException {
72 this.directory=directory;
73 this.name=name;
74 this.indexManager=indexManager;
75 pageCache=new LRUCache<Long ,TreePage>(pageCacheSize,pageCacheSize,0.75f,true);
76 openIndexFile();
77 }
78
79
84 public void setKeyMarshaller(Marshaller marshaller){
85 if(loaded.get()){
86 throw new RuntimeException ("Pages already loaded - can't set marshaller now");
87 }
88 this.keyMarshaller=marshaller;
89 }
90
91
94 public int getKeySize(){
95 return this.keySize;
96 }
97
98
101 public void setKeySize(int keySize){
102 this.keySize=keySize;
103 if(loaded.get()){
104 throw new RuntimeException ("Pages already loaded - can't reset key size");
105 }
106 }
107
108
111 public int getPageSize(){
112 return this.pageSize;
113 }
114
115
118 public void setPageSize(int pageSize){
119 if(loaded.get()&&pageSize!=this.pageSize){
120 throw new RuntimeException ("Pages already loaded - can't reset page size");
121 }
122 this.pageSize=pageSize;
123 }
124
125 public boolean isTransient(){
126 return false;
127 }
128
129
132 public boolean isEnablePageCaching(){
133 return this.enablePageCaching;
134 }
135
136
139 public void setEnablePageCaching(boolean enablePageCaching){
140 this.enablePageCaching=enablePageCaching;
141 }
142
143
146 public int getPageCacheSize(){
147 return this.pageCacheSize;
148 }
149
150
153 public void setPageCacheSize(int pageCacheSize){
154 this.pageCacheSize=pageCacheSize;
155 pageCache.setMaxCacheSize(pageCacheSize);
156 }
157
158 public void load(){
159 if(loaded.compareAndSet(false,true)){
160 keysPerPage=pageSize/keySize;
161 dataIn=new DataByteArrayInputStream();
162 dataOut=new DataByteArrayOutputStream(pageSize);
163 readBuffer=new byte[pageSize];
164 try{
165 openIndexFile();
166 long offset=0;
167 while((offset+pageSize)<=indexFile.length()){
168 indexFile.seek(offset);
169 indexFile.readFully(readBuffer,0,TreePage.PAGE_HEADER_SIZE);
170 dataIn.restart(readBuffer);
171 TreePage page=new TreePage(keysPerPage);
172 page.setTree(this);
173 page.setId(offset);
174 page.readHeader(dataIn);
175 if(!page.isActive()){
176 if(lastFree!=null){
177 lastFree.setNextFreePageId(offset);
178 indexFile.seek(lastFree.getId());
179 dataOut.reset();
180 lastFree.writeHeader(dataOut);
181 indexFile.write(dataOut.getData(),0,TreePage.PAGE_HEADER_SIZE);
182 lastFree=page;
183 }else{
184 lastFree=firstFree=page;
185 }
186 }else if(root==null&&page.isRoot()){
187 root=getFullPage(offset);
188 }
189 offset+=pageSize;
190 }
191 length=offset;
192 if(root==null){
193 root=createRoot();
194 }
195 }catch(IOException e){
196 log.error("Failed to load index ",e);
197 throw new RuntimeException (e);
198 }
199 }
200 }
201
202 public void unload() throws IOException {
203 if(loaded.compareAndSet(true,false)){
204 if(indexFile!=null){
205 indexFile.close();
206 indexFile=null;
207 pageCache.clear();
208 root=null;
209 firstFree=lastFree=null;
210 }
211 }
212 }
213
214 public void store(Object key,StoreEntry value) throws IOException {
215 TreeEntry entry=new TreeEntry();
216 entry.setKey((Comparable )key);
217 entry.setIndexOffset(value.getOffset());
218 root.put(entry);
219 }
220
221 public StoreEntry get(Object key) throws IOException {
222 TreeEntry entry=new TreeEntry();
223 entry.setKey((Comparable )key);
224 TreeEntry result=root.find(entry);
225 return result!=null?indexManager.getIndex(result.getIndexOffset()):null;
226 }
227
228 public StoreEntry remove(Object key) throws IOException {
229 TreeEntry entry=new TreeEntry();
230 entry.setKey((Comparable )key);
231 TreeEntry result = root.remove(entry);
232 return result!=null?indexManager.getIndex(result.getIndexOffset()):null;
233 }
234
235 public boolean containsKey(Object key) throws IOException {
236 TreeEntry entry=new TreeEntry();
237 entry.setKey((Comparable )key);
238 return root.find(entry)!=null;
239 }
240
241 public void clear() throws IOException {
242 unload();
243 delete();
244 openIndexFile();
245 load();
246 }
247
248 public void delete() throws IOException {
249 unload();
250 if(file.exists()){
251 boolean result=file.delete();
252 }
253 length=0;
254 }
255
256
259 TreePage getRoot(){
260 return this.root;
261 }
262
263
264 TreePage lookupPage(long pageId) throws IOException {
265 TreePage result=null;
266 if(pageId>=0){
267 if(root!=null&&root.getId()==pageId){
268 result=root;
269 }else{
270 result=getFromCache(pageId);
271 }
272 if(result==null){
273 result=getFullPage(pageId);
274 if(result!=null){
275 if(result.isActive()){
276 addToCache(result);
277 }else{
278 throw new IllegalStateException ("Trying to access an inactive page: "+pageId+" root is "+root);
279 }
280 }
281 }
282 }
283 return result;
284 }
285
286 TreePage createRoot() throws IOException {
287 TreePage result=createPage(-1);
288 root=result;
289 return result;
290 }
291
292 TreePage createPage(long parentId) throws IOException {
293 TreePage result=getNextFreePage();
294 if(result==null){
295 result=new TreePage(keysPerPage);
297 result.setId(length);
298 result.setTree(this);
299 result.setParentId(parentId);
300 writePage(result);
301 length+=pageSize;
302 indexFile.seek(length);
303 indexFile.write(TreeEntry.NOT_SET);
304 }
305 addToCache(result);
306 return result;
307 }
308
309 void releasePage(TreePage page) throws IOException {
310 removeFromCache(page);
311 page.reset();
312 page.setActive(false);
313 if(lastFree==null){
314 firstFree=lastFree=page;
315 }else{
316 lastFree.setNextFreePageId(page.getId());
317 writePage(lastFree);
318 }
319 writePage(page);
320 }
321
322 private TreePage getNextFreePage() throws IOException {
323 TreePage result=null;
324 if(firstFree!=null){
325 if(firstFree.equals(lastFree)){
326 result=firstFree;
327 firstFree=lastFree=null;
328 }else{
329 result=firstFree;
330 firstFree=getPage(firstFree.getNextFreePageId());
331 if(firstFree==null){
332 lastFree=null;
333 }
334 }
335 result.setActive(true);
336 result.reset();
337 result.saveHeader();
338 }
339 return result;
340 }
341
342 void writeFullPage(TreePage page) throws IOException {
343 dataOut.reset();
344 page.write(keyMarshaller,dataOut);
345 if(dataOut.size()>pageSize){
346 throw new IOException ("Page Size overflow: pageSize is "+pageSize+" trying to write "+dataOut.size());
347 }
348 indexFile.seek(page.getId());
349 indexFile.write(dataOut.getData(),0,dataOut.size());
350 }
351
352 void writePage(TreePage page) throws IOException {
353 dataOut.reset();
354 page.writeHeader(dataOut);
355 indexFile.seek(page.getId());
356 indexFile.write(dataOut.getData(),0,TreePage.PAGE_HEADER_SIZE);
357 }
358
359 TreePage getFullPage(long id) throws IOException {
360 indexFile.seek(id);
361 indexFile.readFully(readBuffer,0,pageSize);
362 dataIn.restart(readBuffer);
363 TreePage page=new TreePage(keysPerPage);
364 page.setId(id);
365 page.setTree(this);
366 page.read(keyMarshaller,dataIn);
367 return page;
368 }
369
370 TreePage getPage(long id) throws IOException {
371 indexFile.seek(id);
372 indexFile.readFully(readBuffer,0,TreePage.PAGE_HEADER_SIZE);
373 dataIn.restart(readBuffer);
374 TreePage page=new TreePage(keysPerPage);
375 page.setId(id);
376 page.setTree(this);
377 page.readHeader(dataIn);
378 return page;
379 }
380
381
382
383 private TreePage getFromCache(long pageId){
384 TreePage result=null;
385 if(enablePageCaching){
386 result=pageCache.get(pageId);
387 }
388 return result;
389 }
390
391 private void addToCache(TreePage page){
392 if(enablePageCaching){
393 pageCache.put(page.getId(),page);
394 }
395 }
396
397 private void removeFromCache(TreePage page){
398 if(enablePageCaching){
399 pageCache.remove(page.getId());
400 }
401 }
402
403 protected void openIndexFile() throws IOException {
404 if(indexFile==null){
405 file=new File (directory,NAME_PREFIX+name);
406 indexFile=new RandomAccessFile (file,"rw");
407 }
408 }
409 static{
410 DEFAULT_PAGE_SIZE=Integer.parseInt(System.getProperty("defaultPageSize","16384"));
411 DEFAULT_KEY_SIZE=Integer.parseInt(System.getProperty("defaultKeySize","96"));
412 }
413 }
414 |
Popular Tags |
Java API By Example, From Geeks To Geeks.