Java > Open Source Codes > org > objectweb > jalisto > se > storage > raf > RecordsFile


1 /*
2  * Jalisto - JAva LIght STOrage
3  * Copyright (C) 2000-2005 Xcalia http://www.xcalia.com
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
18  *
19  * Xcalia
20  * 71, rue Desnouettes
21  * 75014 Paris - France
22  * http://www.xcalia.com
23  */
24 package org.objectweb.jalisto.se.storage.raf;
25
26 import org.objectweb.jalisto.se.impl.trace.Trace;
27 import org.objectweb.jalisto.se.impl.util.JalistoUtils;
28
29 import java.io.File ;
30 import java.io.IOException ;
31 import java.io.RandomAccessFile ;
32 import java.util.*;
33
34 public class RecordsFile {
35     // Total length in bytes of the global database headers.
36 protected static final int FILE_HEADERS_REGION_LENGTH = 16;
37
38     // Number of bytes in the record header.
39 protected static final int RECORD_HEADER_LENGTH = 16;
40
41     // File pointer to the num records header.
42 protected static final long NUM_RECORDS_HEADER_LOCATION = 0;
43
44     // File pointer to the data start pointer header.
45 protected static final long DATA_START_HEADER_LOCATION = 4;
46
47     protected double additionalSpace;
48
49     // The total length of one index entry - the key length plus the record header length.
50 protected int indexEntryLength;
51
52     // The length of a key in the index. default = 64
53 protected int maxKeyLength;
54
55     // Current file pointer to the start of the record data.
56 protected long dataStartPtr;
57
58     protected Trace trace;
59
60     // The underlying file.
61 protected RandomAccessFile file;
62
63     /**
64      * Hashtable which holds the in-memory index. For efficiency, the entire index
65      * is cached in memory. The hashtable maps a key of type String to a RecordHeader.
66      */
67     protected HashMap memIndex;
68
69
70     /**
71      * Creates a new database file. The initialSize parameter determines the
72      * amount of space which is allocated for the index. The index can grow
73      * dynamically, but the parameter is provide to increase
74      * efficiency.
75      */
76     public RecordsFile(String dbPath)
77             throws IOException , RecordsFileException {
78         File f = new File (dbPath);
79         if (f.exists()) {
80             throw new RecordsFileException("Database already exits: " + dbPath);
81         }
82         file = new RandomAccessFile (f, "rw");
83     }
84
85     /**
86      * Opens an existing database file and initializes the dataStartPtr. The accessFlags
87      * parameter can be "r" or "rw" -- as defined in RandomAccessFile.
88      * Initialize the in-memory index.
89      */
90     public RecordsFile(String dbPath, String accessFlags)
91             throws IOException , RecordsFileException {
92         File f = new File (dbPath);
93         if (!f.exists()) {
94             throw new RecordsFileException("Database not found: " + dbPath);
95         }
96         file = new RandomAccessFile (f, accessFlags);
97     }
98
99     public void initNewStorage(int initialSize, int maxKeyLength, int additionalSpace)
100             throws IOException , RecordsFileException {
101         this.maxKeyLength = maxKeyLength; // to have string size == maxKeyLength
102 this.additionalSpace = (((double) additionalSpace) / 100) + 1;
103         this.indexEntryLength = maxKeyLength + RECORD_HEADER_LENGTH;
104         this.dataStartPtr = indexPositionToKeyFp(initialSize); // Record Data Region starts were the (i+1)th index entry would start.
105 setFileLength(dataStartPtr);
106         writeNumRecordsHeader(0);
107         writeDataStartPtrHeader(dataStartPtr);
108         memIndex = new HashMap(initialSize);
109     }
110
111     public void initExistingStorage(int maxKeyLength, int additionalSpace)
112             throws IOException , RecordsFileException {
113         this.maxKeyLength = maxKeyLength; // to have string size == maxKeyLength
114 this.additionalSpace = (((double) additionalSpace) / 100) + 1;
115         this.indexEntryLength = maxKeyLength + RECORD_HEADER_LENGTH;
116         this.dataStartPtr = readDataStartHeader();
117         readHeadersInMemIndex();
118     }
119
120     public synchronized void close() throws IOException , RecordsFileException {
121         try {
122             file.close();
123         } finally {
124             memIndex.clear();
125             memIndex = null;
126             file = null;
127         }
128     }
129
130     /**
131      * *********************************************************************************************
132      */
133
134     public synchronized void insertRecord(RecordWriter rw) throws RecordsFileException, IOException {
135         String key = rw.getKey();
136         if (recordExists(key)) {
137             throw new RecordsFileException("Key exists: " + key);
138         }
139         insureIndexSpace(getNumRecords() + 1);
140         int length = (new Double (rw.getDataLength() * additionalSpace)).intValue();
141         RecordHeader newRecord = allocateRecord(key, length);
142         writeRecordData(newRecord, rw);
143         addEntryToIndex(key, newRecord, getNumRecords());
144     }
145
146     public synchronized RecordReader readRecord(String key) throws RecordsFileException, IOException {
147         byte[] data = readRecordData(key);
148         return new RecordReader(key, data);
149     }
150
151     /**
152      * Updates an existing record. If the new contents do not fit in the original record,
153      * then the update is handled by deleting the old record and adding the new.
154      */
155     public synchronized void updateRecord(RecordWriter rw)
156             throws RecordsFileException, IOException {
157         RecordHeader header = keyToRecordHeader(rw.getKey());
158
159         if (rw.getDataLength() > header.getDataCapacity()) {
160             deleteRecord(rw.getKey());
161             insertRecord(rw);
162         } else {
163             writeRecordData(header, rw);
164             writeRecordHeaderToIndex(header);
165         }
166     }
167
168     public synchronized void deleteRecord(String key) throws RecordsFileException, IOException {
169         RecordHeader delRec = keyToRecordHeader(key);
170         int currentNumRecords = getNumRecords();
171
172         if (getFileLength() == (delRec.getDataPointer() + delRec.getDataCapacity())) {
173             // shrink file since this is the last record in the file
174 setFileLength(delRec.getDataPointer());
175         } else {
176             RecordHeader previous = getRecordAt(delRec.getDataPointer() - 1);
177
178             if (previous != null) {
179                 // append space of deleted record onto previous record
180 previous.setDataCapacity(previous.getDataCapacity() + delRec.getDataCapacity());
181                 writeRecordHeaderToIndex(previous);
182             } else {
183                 // target record is first in the file and is deleted by adding its space to
184 // the second record.
185 RecordHeader secondRecord = getRecordAt(delRec.getDataPointer() + (long) delRec.getDataCapacity());
186                 byte[] data = readRecordData(secondRecord);
187                 secondRecord.setDataPointer(delRec.getDataPointer());
188                 secondRecord.setDataCapacity(secondRecord.getDataCapacity() + delRec.getDataCapacity());
189                 writeRecordData(secondRecord, data);
190                 writeRecordHeaderToIndex(secondRecord);
191             }
192         }
193         deleteEntryFromIndex(key, delRec, currentNumRecords);
194     }
195
196
197     protected void setFileLength(long l) throws IOException {
198         file.setLength(l);
199     }
200
201     protected long getFileLength() throws IOException {
202         return file.length();
203     }
204
205     /**
206      * Appends an entry to end of index. Assumes that insureIndexSpace() has already been called.
207      */
208     protected void addEntryToIndex(String key, RecordHeader newRecord, int currentNumRecords)
209             throws IOException , RecordsFileException {
210         DbByteArrayOutputStream temp = DbByteArrayOutputStream.getInstance();
211         temp.getOutput().writeUTF(key);
212
213         if (temp.size() > maxKeyLength) {
214             throw new RecordsFileException("Key " + key + " of size " + temp.size() +
215                                            " is larger than permitted size of " +
216                                            maxKeyLength + " bytes");
217         }
218
219         writeOutputStream(indexPositionToKeyFp(currentNumRecords), temp);
220         temp.reset();
221         writeRecordHeader(indexPositionToRecordHeaderFp(currentNumRecords), newRecord);
222         newRecord.setIndexPosition(currentNumRecords);
223         writeNumRecordsHeader(currentNumRecords + 1);
224
225         synchronized (memIndex) {
226             memIndex.put(key, newRecord);
227         }
228     }
229
230     /**
231      * Removes the record from the index. Replaces the target with the entry at the
232      * end of the index.
233      */
234     protected void deleteEntryFromIndex(String key, RecordHeader header, int currentNumRecords)
235             throws IOException , RecordsFileException {
236         if (header.getIndexPosition() != (currentNumRecords - 1)) {
237             String lastKey = readKeyFromIndex(currentNumRecords - 1);
238             RecordHeader last = keyToRecordHeader(lastKey);
239             last.setIndexPosition(header.getIndexPosition());
240             writeUTF(indexPositionToKeyFp(last.getIndexPosition()), lastKey);
241             writeRecordHeader(indexPositionToRecordHeaderFp(last.getIndexPosition()), last);
242         }
243         writeNumRecordsHeader(currentNumRecords - 1);
244         synchronized (memIndex) {
245             memIndex.remove(key);
246         }
247     }
248
249     public Collection getKeysStartingWith(String filter) {
250         Collection result = new ArrayList();
251         synchronized (memIndex) {
252             Iterator keys = memIndex.keySet().iterator();
253             while (keys.hasNext()) {
254                 String key = (String ) keys.next();
255                 if (key.startsWith(filter)) {
256                     result.add(key);
257                 }
258             }
259         }
260         return result;
261     }
262
263
264     // Checks to see if there is space for and additional index entry. If
265 // not, space is created by moving records to the end of the file.
266 protected void insureIndexSpace(int requiredNumRecords)
267             throws RecordsFileException, IOException {
268         int originalFirstDataCapacity;
269         int currentNumRecords = getNumRecords();
270         long endIndexPtr = indexPositionToKeyFp(requiredNumRecords);
271
272         if ((endIndexPtr > getFileLength()) && (currentNumRecords == 0)) {
273             setFileLength(endIndexPtr);
274             dataStartPtr = endIndexPtr;
275             writeDataStartPtrHeader(dataStartPtr);
276
277             return;
278         }
279
280         while (endIndexPtr > dataStartPtr) {
281             RecordHeader first = getRecordAt(dataStartPtr);
282             byte[] data = readRecordData(first);
283             first.setDataPointer(getFileLength());
284
285             // If first.dataCapacity is set to the actual data count BEFORE resetting dataStartPtr,
286 // and there is free space in 'first', then dataStartPtr will not be reset to the start
287 // of the second record. Capture the capacity first and use it to perform the reset.
288 originalFirstDataCapacity = first.getDataCapacity();
289             first.setDataCapacity(data.length);
290             setFileLength(first.getDataPointer() + data.length);
291             writeRecordData(first, data);
292             writeRecordHeaderToIndex(first);
293             dataStartPtr += originalFirstDataCapacity;
294             writeDataStartPtrHeader(dataStartPtr);
295         }
296     }
297
298     /**
299      * Returns a file pointer in the index pointing to the first byte
300      * in the key located at the given index position.
301      */
302     protected long indexPositionToKeyFp(int pos) {
303         return FILE_HEADERS_REGION_LENGTH + (indexEntryLength * pos);
304     }
305
306     protected long readDataStartHeader() throws IOException {
307         file.seek(DATA_START_HEADER_LOCATION);
308         return file.readLong();
309     }
310
311     protected int readNumRecordsHeader() throws IOException {
312         file.seek(NUM_RECORDS_HEADER_LOCATION);
313         return file.readInt();
314     }
315
316     protected byte[] readRecordData(String key) throws IOException , RecordsFileException {
317         return readRecordData(keyToRecordHeader(key));
318     }
319
320     protected byte[] readRecordData(RecordHeader header) throws IOException {
321         byte[] buf = new byte[header.getDataCount()];
322         file.seek(header.getDataPointer());
323         file.readFully(buf);
324         return buf;
325     }
326
327     protected void writeDataStartPtrHeader(long dataStartPtr) throws IOException {
328         writeLong(DATA_START_HEADER_LOCATION, dataStartPtr);
329     }
330
331     protected void writeNumRecordsHeader(int numRecords) throws IOException {
332         writeInt(NUM_RECORDS_HEADER_LOCATION, numRecords);
333     }
334
335     /**
336      * Updates the contents of the given record. A RecordsFileException is thrown if the new data does not
337      * fit in the space allocated to the record. The header's data count is updated, but not
338      * written to the file.
339      */
340     protected void writeRecordData(RecordHeader header, RecordWriter rw) throws IOException , RecordsFileException {
341         if (rw.getDataLength() > header.getDataCapacity()) {
342             throw new RecordsFileException("Record data does not fit");
343         }
344         header.setDataCount(rw.getDataLength());
345         writeRecordWriter(header, rw);
346     }
347
348     /**
349      * Updates the contents of the given record. A RecordsFileException is thrown if the new data does not
350      * fit in the space allocated to the record. The header's data count is updated, but not
351      * written to the file.
352      */
353     protected void writeRecordData(RecordHeader header, byte[] data)
354             throws IOException , RecordsFileException {
355         if (data.length > header.getDataCapacity()) {
356             throw new RecordsFileException("Record data does not fit");
357         }
358         header.setDataCount(data.length);
359         writeByteArray(header.getDataPointer(), data);
360     }
361
362     protected void writeRecordHeaderToIndex(RecordHeader header) throws IOException {
363         writeRecordHeader(indexPositionToRecordHeaderFp(header.getIndexPosition()), header);
364         synchronized (memIndex) {
365             memIndex.put(readKeyFromIndex(header.getIndexPosition()), header);
366         }
367     }
368
369     /**
370      * Returns a file pointer in the index pointing to the first byte
371      * in the record pointer located at the given index position.
372      */
373     long indexPositionToRecordHeaderFp(int pos) {
374         return indexPositionToKeyFp(pos) + maxKeyLength;
375     }
376
377     /**
378      * Reads the ith key from the index.
379      */
380     protected String readKeyFromIndex(int position) throws IOException {
381         file.seek(indexPositionToKeyFp(position));
382         return file.readUTF();
383     }
384
385     /**
386      * Reads the ith record header from the index.
387      */
388     protected RecordHeader readRecordHeaderFromIndex(int position) throws IOException {
389         file.seek(indexPositionToRecordHeaderFp(position));
390         return RecordHeader.readHeader(file);
391     }
392
393
394     public synchronized void reorganize() throws IOException , RecordsFileException {
395         long length = file.length();
396         long moveAddress = dataStartPtr;
397         long nextTargetAddress = dataStartPtr;
398         while (length > nextTargetAddress) {
399             RecordHeader header = getRecordAt(nextTargetAddress);
400             nextTargetAddress = header.getDataPointer() + header.getDataCapacity();
401             moveAddress = moveDataBack(header, moveAddress);
402         }
403         setFileLength(moveAddress);
404     }
405
406     // return next address to move data
407 private synchronized long moveDataBack(RecordHeader header, long moveAddress) throws IOException , RecordsFileException {
408         if (header.getDataPointer() > moveAddress) {
409             byte[] buf = readRecordData(header);
410             long maxAddress = header.getDataPointer() + header.getDataCapacity();
411             int size = (new Double (buf.length * additionalSpace)).intValue();
412
413             if ((moveAddress + size) > maxAddress) {
414                 size = (int) (maxAddress - moveAddress);
415             }
416
417             RecordHeader newHeader = new RecordHeader(moveAddress, size);
418             writeRecordData(newHeader, buf);
419             newHeader.setIndexPosition(header.getIndexPosition());
420             writeRecordHeaderToIndex(newHeader);
421             return newHeader.getDataPointer() + newHeader.getDataCapacity();
422
423             // no move, just resize
424 } else if (header.getDataPointer() == moveAddress) {
425             int size = (new Double (header.getDataCount() * additionalSpace)).intValue();
426             if (size > header.getDataCapacity()) {
427                 size = header.getDataCapacity();
428             }
429             header.setDataCapacity(size);
430             writeRecordHeaderToIndex(header);
431             return (header.getDataPointer() + header.getDataCapacity());
432         } else {
433             throw new RecordsFileException("moveDataBack address error");
434         }
435     }
436
437     public void setTrace(Trace trace) {
438         this.trace = trace;
439     }
440
441
442     /**
443      * ******************************************* LOGGING ************************************************
444      */
445
446     protected void writeByteArray(long position, byte[] datas) throws IOException {
447         file.seek(position);
448         file.write(datas);
449     }
450
451     protected void writeOutputStream(long position, DbByteArrayOutputStream outputStream) throws IOException {
452         file.seek(position);
453         outputStream.writeTo(file);
454     }
455
456     protected void writeRecordWriter(RecordHeader header, RecordWriter recordWriter) throws IOException {
457         file.seek(header.getDataPointer());
458         recordWriter.writeTo(file);
459     }
460
461     protected void writeRecordHeader(long position, RecordHeader recordHeader) throws IOException {
462         file.seek(position);
463         recordHeader.write(file);
464     }
465
466     protected void writeInt(long position, int i) throws IOException {
467         file.seek(position);
468         file.writeInt(i);
469     }
470
471     protected void writeLong(long position, long l) throws IOException {
472         file.seek(position);
473         file.writeLong(l);
474     }
475
476     protected void writeUTF(long position, String s) throws IOException {
477         file.seek(position);
478         file.writeUTF(s);
479     }
480
481
482     /**
483      * ****************************** ABSTRACT *****************************************
484      */
485
486
487     public synchronized int getNumRecords() {
488         return memIndex.size();
489     }
490
491     public synchronized Iterator enumerateKeys() {
492         return memIndex.keySet().iterator();
493     }
494
495     public synchronized boolean recordExists(String key) {
496         return memIndex.containsKey(key);
497     }
498
499     /**
500      * Returns the record to which the target file pointer belongs - meaning the specified location
501      * in the file is part of the record data of the RecordHeader which is returned. Returns null if
502      * the location is not part of a record. (O(n) mem accesses)
503      */
504     protected RecordHeader getRecordAt(long targetFp) {
505         Iterator elements = memIndex.values().iterator();
506         while (elements.hasNext()) {
507             RecordHeader next = (RecordHeader) elements.next();
508             if ((targetFp >= next.getDataPointer()) &&
509                 (targetFp < (next.getDataPointer() +
510                              (long) next.getDataCapacity()))) {
511                 return next;
512             }
513         }
514         return null;
515     }
516
517     /**
518      * This method searches the file for free space and then returns a RecordHeader
519      * which uses the space. (O(n) memory accesses)
520      */
521     protected RecordHeader allocateRecord(String key, int dataLength)
522             throws RecordsFileException, IOException {
523         // search for empty space
524 RecordHeader newRecord = null;
525         Iterator elements = memIndex.values().iterator();
526         while (elements.hasNext()) {
527             RecordHeader next = (RecordHeader) elements.next();
528             if (dataLength <= next.getFreeSpace()) {
529                 newRecord = next.split();
530                 writeRecordHeaderToIndex(next);
531                 break;
532             }
533         }
534         if (newRecord == null) {
535             // append record to end of file - grows file to allocate space
536 long fp = getFileLength();
537             setFileLength(fp + dataLength);
538             newRecord = new RecordHeader(fp, dataLength);
539         }
540         return newRecord;
541     }
542
543     /**
544      * Maps a key to a record header by looking it up in the in-memory index.
545      */
546     protected RecordHeader keyToRecordHeader(String key) throws RecordsFileException {
547         RecordHeader h = (RecordHeader) memIndex.get(key);
548         if (h == null) {
549             throw new RecordsFileException("Key not found: " + key);
550         }
551         return h;
552     }
553
554     protected void readHeadersInMemIndex() throws IOException {
555         int numRecords = readNumRecordsHeader();
556         memIndex = new HashMap(numRecords);
557
558         synchronized (memIndex) {
559             for (int i = 0; i < numRecords; i++) {
560                 String key = readKeyFromIndex(i);
561                 RecordHeader header = readRecordHeaderFromIndex(i);
562                 header.setIndexPosition(i);
563                 memIndex.put(key, header);
564             }
565         }
566     }
567
568     /**
569      * ***************************************************************************************************
570      */
571
572     public boolean equals(Object object) {
573         RecordsFile candidate;
574         try {
575             candidate = (RecordsFile) object;
576         } catch (ClassCastException cce) {
577             System.out.println("RecordsFile equals : candidate is not a RecordsFile instance");
578             return false;
579         }
580
581         if (memIndex.size() != candidate.memIndex.size()) {
582             System.out.println("RecordsFile equals : not the same number of key");
583             return false;
584         }
585
586         Iterator keys = memIndex.keySet().iterator();
587         while (keys.hasNext()) {
588             String key = (String ) keys.next();
589             if (!candidate.memIndex.containsKey(key)) {
590                 System.out.println("RecordsFile equals : one contains a key, other don't");
591                 return false;
592             }
593             RecordHeader rh = (RecordHeader) memIndex.get(key);
594             RecordHeader crh = (RecordHeader) candidate.memIndex.get(key);
595             if (!rh.equals(crh)) {
596                 System.out.println("RecordsFile equals : recordHeader not equal for key " + key);
597                 System.out.println(rh.toString());
598                 System.out.println(crh.toString());
599                 return false;
600             }
601             try {
602                 if (!JalistoUtils.areEquals(readRecordData(rh), candidate.readRecordData(crh))) {
603                     System.out.println("RecordsFile equals : datas not equals for key " + key);
604                     return false;
605                 }
606             } catch (IOException ioe) {
607                 ioe.printStackTrace();
608                 return false;
609             }
610         }
611
612         return true;
613     }
614 }
615

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags