001: // You can redistribute this software and/or modify it under the terms of
002: // the Ozone Library License version 1 published by ozone-db.org.
003: //
004: // The original code and portions created by SMB are
005: // Copyright (C) 1997-@year@ by SMB GmbH. All rights reserved.
006: //
007: // $Id: DxDiskSubTable.java,v 1.2 2002/04/10 06:57:25 per_nyfelt Exp $
008:
009: package org.ozoneDB.DxLib;
010:
011: import java.io.*;
012: import java.util.zip.*;
013:
014: /**
015: * @author <a href="http://www.softwarebuero.de/">SMB</a>
016: * @author <a href="http://www.medium.net/">Medium.net</a>
017: */
018: public final class DxDiskSubTable implements Externalizable {
019:
020: final static long serialVersionUID = 2;
021:
022: public static int timeCount = (int) System.currentTimeMillis();
023:
024: private int size;
025: private int bitSize;
026: private int maxDepth;
027:
028: //protected String fileName;
029: protected File file;
030: protected int depth;
031: protected int hashMask;
032: protected DxDiskHashMap grandParent;
033:
034: protected DxDiskHashNode[] table;
035: protected long accessTime = timeCount++;
036: protected boolean dirty;
037: protected int subTableCount = 0;
038:
039: /**
040: * All the items (including subTables) in the local list.
041: */
042: protected int itemCount = 0;
043:
044: public DxDiskSubTable(DxDiskHashMap grandParent) {
045: this .grandParent = grandParent;
046: }
047:
048: public DxDiskSubTable(DxDiskHashMap _grandParent, int _depth,
049: int _bitSize) {
050: bitSize = Math.min(_bitSize, 32 - _depth * _bitSize);
051: size = (int) Math.pow(2, bitSize);
052: depth = _depth;
053: maxDepth = (32 / _bitSize - (32 % bitSize > 0 ? 0 : 1));
054:
055: // System.out.println ("DxDiskSubTable: bitSize=" + bitSize + ", size=" + size + ", depth:" + depth + ", maxDepth:" + maxDepth);
056:
057: int bitNum = (maxDepth - depth) * bitSize;
058: int bitMask = (int) Math.pow(2, bitNum);
059: hashMask = 0;
060: for (int i = 0; i < bitSize; i++) {
061: hashMask = hashMask | bitMask;
062: bitMask *= 2;
063: }
064: // hashMask = ((int)0xff) << ((maxDepth - depth) * bitSize);
065:
066: // System.out.println ("DxDiskSubTable: hashMask: " + hashMask);
067: // System.out.print ("DxDiskSubTable: hashMask: ");
068: // for (int i=31; i>=0; i--)
069: // System.out.print ((hashMask & (int)Math.pow(2, i)) > 0 ? "1" : "0");
070: // System.out.println ("");
071:
072: table = new DxDiskHashNode[size];
073: grandParent = _grandParent;
074: //fileName = grandParent.newSubTableFileName();
075: file = grandParent.newSubTableFile();
076: }
077:
078: /*
079: public String filename() {
080: return fileName;
081: }
082: */
083:
084: public File getFile() {
085: return file;
086: }
087:
088: public DxDiskHashNode[] table() {
089: return table;
090: }
091:
092: public DxDiskHashNode[] fetchedTable() throws Exception {
093: fetchTable();
094: // touch();
095: return table;
096: }
097:
098: public void empty() {
099: table = null;
100: }
101:
102: public int count() {
103: return itemCount;
104: }
105:
106: public void deleteFile() {
107: // System.out.println ("deleteFile()...");
108: //File file = new File( fileName );
109: if (file.exists()) {
110: file.delete();
111: }
112: }
113:
114: public int hashKey(int key) {
115: // return (key & hashMask) >> (depth * bitSize);
116: return (key & hashMask) >> (maxDepth - depth) * bitSize;
117: }
118:
119: protected void fetchTable() throws Exception {
120: grandParent.bufferAccesses++;
121: if (table == null) {
122: synchronized (this ) {
123: grandParent.readRequest(this );
124: readTable();
125: }
126: } else {
127: grandParent.bufferHits++;
128: }
129: }
130:
131: protected synchronized void touch() {
132: accessTime = timeCount++;
133: }
134:
135: public boolean isLeaf() {
136: return subTableCount == 0;
137: }
138:
139: public boolean isDirty() {
140: return dirty;
141: }
142:
143: public synchronized boolean addForKey(Object obj, Object key)
144: throws Exception {
145: fetchTable();
146:
147: boolean answer = true;
148: int localKey = hashKey(key.hashCode());
149: DxDiskHashNode node = table[localKey];
150: if (node != null) {
151: //node ist ein blatt
152: if (node instanceof DxDiskHashNodeLeaf) {
153: DxDiskHashNodeLeaf oldNode = (DxDiskHashNodeLeaf) node;
154: if (depth < maxDepth) {
155: DxDiskHashNodeBranch newNode = grandParent
156: .newNodeBranch();
157: newNode.subTable = new DxDiskSubTable(grandParent,
158: depth + 1, grandParent.tableBitSize);
159: //im alten node kann nur ein element stehen
160: newNode.subTable.addForKey(oldNode.element.data,
161: oldNode.element.key);
162: answer = newNode.subTable.addForKey(obj, key);
163: if (answer) {
164: grandParent.readRequest(newNode.subTable);
165: table[localKey] = newNode;
166: subTableCount++;
167: } else {
168: table[localKey] = oldNode;
169: }
170: } else {
171: //maximale tiefe ist erreicht
172: answer = oldNode.addForKey(obj, key);
173: }
174: } else {
175: //node ist ein branch
176: ((DxDiskHashNodeBranch) node).subTable.addForKey(obj,
177: key);
178: }
179: } else {
180: //node existiert noch nicht
181: DxDiskHashNodeLeaf newNode = grandParent.newNodeLeaf();
182: newNode.addForKey(obj, key);
183: table[localKey] = newNode;
184: itemCount++;
185: }
186: //muss ganz unten stehen, damit abraeumen korrekt ist
187: touch();
188: dirty = true;
189: return answer;
190: }
191:
192: public final Object elementForKey(Object key, int hashCode)
193: throws Exception {
194: fetchTable();
195:
196: int localKey = hashKey(hashCode);
197: Object answer = null;
198: DxDiskHashNode node = table[localKey];
199: if (node != null) {
200: if (node instanceof DxDiskHashNodeLeaf) {
201: answer = ((DxDiskHashNodeLeaf) node).elementForKey(key,
202: hashCode);
203: } else {
204: answer = ((DxDiskHashNodeBranch) node).subTable
205: .elementForKey(key, hashCode);
206: }
207: }
208: //muss ganz unten stehen, damit anraeumen korrekt ist
209: touch();
210: return answer;
211: }
212:
213: protected synchronized void elementDone(DxDiskHashCompatible obj) {
214: }
215:
216: public synchronized Object removeForKey(Object key)
217: throws Exception {
218: fetchTable();
219:
220: Object answer = null;
221: int localKey = hashKey(key.hashCode());
222: DxDiskHashNode node = table[localKey];
223: if (node != null) {
224: if (node instanceof DxDiskHashNodeLeaf) {
225: answer = ((DxDiskHashNodeLeaf) node).removeForKey(key);
226: if (((DxDiskHashNodeLeaf) node).element == null) {
227: table[localKey] = null;
228: itemCount--;
229: }
230: } else {
231: DxDiskHashNodeBranch oldNode = (DxDiskHashNodeBranch) node;
232: answer = oldNode.subTable.removeForKey(key);
233: if (oldNode.subTable.itemCount == 0) {
234: grandParent.deleteRequest(oldNode.subTable);
235: oldNode.subTable.deleteFile();
236: table[localKey] = null;
237: itemCount--;
238: subTableCount--;
239: }
240: }
241: }
242: // System.out.println ("remove: key: " + key + " - depth: " + depth + " - count: " + itemCount);
243:
244: //muss ganz unten stehen, damit anraeumen korrekt ist
245: touch();
246: dirty = true;
247: return answer;
248: }
249:
250: /**
251: * Schreibt nur die representation in einem HashNode aber
252: * nicht die tabelle selber.
253: */
254: public void writeExternal(ObjectOutput out) throws IOException {
255: //out.writeUTF( fileName );
256: out.writeUTF(file.getName());
257: out.writeInt(bitSize);
258: out.writeInt(size);
259: out.writeInt(maxDepth);
260: out.writeInt(depth);
261: out.writeInt(hashMask);
262: out.writeInt(subTableCount);
263: out.writeInt(itemCount);
264: }
265:
266: public void readExternal(ObjectInput in) throws IOException,
267: ClassNotFoundException {
268: String fileName = in.readUTF();
269: bitSize = in.readInt();
270: size = in.readInt();
271: maxDepth = in.readInt();
272: depth = in.readInt();
273: hashMask = in.readInt();
274: subTableCount = in.readInt();
275: itemCount = in.readInt();
276: file = grandParent.getFileForFilename(fileName);
277: // force tabel to be read on next access
278: if (itemCount > 0) {
279: table = null;
280: }
281: accessTime = 0;
282: dirty = false;
283: }
284:
285: /**
286: * Schreibt den inhalt der ganzen tabelle aber nicht die
287: * sub-tabellen. Der name wird aus dem baseFileName und
288: */
289: public void writeTable() throws IOException {
290: // System.out.println ("schreiben: " + fileName);
291: // ObjectOutputStream out = new ObjectOutputStream (new BufferedOutputStream (new FileOutputStream (fileName), 4*1024));
292:
293: OutputStream out = new FileOutputStream(file);
294: out = new GZIPOutputStream(out);
295: out = new BufferedOutputStream(out, 4096);
296: ObjectOutputStream oout = new ObjectOutputStream(out);
297: try {
298: synchronized (table) {
299: oout.writeInt(itemCount);
300: for (int i = 0; i < size; i++) {
301: if (table[i] != null) {
302: oout.writeShort(i);
303: oout
304: .writeByte(table[i] instanceof DxDiskHashNodeLeaf ? 1
305: : 2);
306: table[i].writeExternal(oout);
307: }
308: }
309: }
310: dirty = false;
311: } finally {
312: oout.close();
313: }
314: }
315:
316: public synchronized void readTable() throws IOException,
317: ClassNotFoundException {
318: // System.out.println ("lesen: " + fileName);
319: table = new DxDiskHashNode[size];
320:
321: // ObjectInputStream in = new ObjectInputStream (new BufferedInputStream (new FileInputStream (fileName), 4*1024));
322: InputStream in = new FileInputStream(file);
323: in = new GZIPInputStream(in);
324: in = new BufferedInputStream(in, 4096);
325: ObjectInputStream oin = new ObjectInputStream(in);
326:
327: try {
328: int count = oin.readInt();
329: for (int i = 0; i < count; i++) {
330: short index = oin.readShort();
331:
332: byte nodeType = oin.readByte();
333: if (nodeType == 1) {
334: table[index] = grandParent.newNodeLeaf();
335: } else {
336: table[index] = grandParent.newNodeBranch();
337: }
338: table[index].readExternal(oin);
339: if (nodeType == 2) {
340: ((DxDiskHashNodeBranch) table[index]).subTable.grandParent = grandParent;
341: }
342: }
343: touch();
344: dirty = false;
345: } finally {
346: oin.close();
347: }
348: }
349: }
|