001: // kelondroFlexTable.java
002: // (C) 2006 by Michael Peter Christen; mc@anomic.de, Frankfurt a. M., Germany
003: // first published 01.06.2006 on http://www.anomic.de
004: //
005: // $LastChangedDate: 2006-04-02 22:40:07 +0200 (So, 02 Apr 2006) $
006: // $LastChangedRevision: 1986 $
007: // $LastChangedBy: orbiter $
008: //
009: // LICENSE
010: //
011: // This program is free software; you can redistribute it and/or modify
012: // it under the terms of the GNU General Public License as published by
013: // the Free Software Foundation; either version 2 of the License, or
014: // (at your option) any later version.
015: //
016: // This program is distributed in the hope that it will be useful,
017: // but WITHOUT ANY WARRANTY; without even the implied warranty of
018: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
019: // GNU General Public License for more details.
020: //
021: // You should have received a copy of the GNU General Public License
022: // along with this program; if not, write to the Free Software
023: // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
024:
025: package de.anomic.kelondro;
026:
027: import java.io.File;
028: import java.io.IOException;
029: import java.util.ArrayList;
030: import java.util.Date;
031: import java.util.HashMap;
032: import java.util.Iterator;
033: import java.util.List;
034: import java.util.Map;
035: import java.util.TreeMap;
036: import java.util.TreeSet;
037:
038: import de.anomic.server.serverMemory;
039: import de.anomic.server.logging.serverLog;
040:
041: public class kelondroFlexTable extends kelondroFlexWidthArray implements
042: kelondroIndex {
043:
044: // static tracker objects
045: private static TreeMap<String, kelondroFlexTable> tableTracker = new TreeMap<String, kelondroFlexTable>();
046:
047: // class objects
048: protected kelondroBytesIntMap index;
049: private boolean RAMIndex;
050:
051: public kelondroFlexTable(File path, String tablename,
052: long preloadTime, kelondroRow rowdef, int minimumSpace,
053: boolean resetOnFail) {
054: // the buffersize applies to a possible load of the ram-index
055: // the minimumSpace is a initial allocation space for the index; names the number of index slots
056: // if the ram is not sufficient, a tree file is generated
057: // if, and only if a tree file exists, the preload time is applied
058: super (path, tablename, rowdef, resetOnFail);
059: if ((super .col[0].size() < 0) && (resetOnFail))
060: try {
061: super .reset();
062: } catch (IOException e2) {
063: e2.printStackTrace();
064: throw new kelondroException(e2.getMessage());
065: }
066: minimumSpace = Math.max(minimumSpace, super .size());
067: try {
068: long neededRAM = 10 * 1024 * 104 + (long) ((super .row()
069: .column(0).cellwidth + 4)
070: * minimumSpace * kelondroRowCollection.growfactor);
071:
072: File newpath = new File(path, tablename);
073: File indexfile = new File(newpath, "col.000.index");
074: String description = "";
075: description = new String(this .col[0].getDescription());
076: int p = description.indexOf(';', 4);
077: long stt = (p > 0) ? Long.parseLong(description.substring(
078: 4, p)) : 0;
079: System.out.println("*** Last Startup time: " + stt
080: + " milliseconds");
081: long start = System.currentTimeMillis();
082:
083: if (serverMemory.request(neededRAM, false)) {
084: // we can use a RAM index
085: if (indexfile.exists()) {
086: // delete existing index file
087: System.out.println("*** Delete File index "
088: + indexfile);
089: indexfile.delete();
090: }
091:
092: // fill the index
093: System.out.print("*** Loading RAM index for " + size()
094: + " entries from " + newpath
095: + "; available RAM = "
096: + (serverMemory.available() >> 20)
097: + " MB, allocating " + (neededRAM >> 20)
098: + " MB for index.");
099: index = initializeRamIndex(minimumSpace);
100:
101: System.out.println(" -done-");
102: System.out.println(index.size()
103: + " index entries initialized and sorted from "
104: + super .col[0].size() + " keys.");
105: RAMIndex = true;
106: tableTracker.put(this .filename(), this );
107: } else {
108: // too less ram for a ram index
109: kelondroIndex ki;
110: if (indexfile.exists()) {
111: // use existing index file
112: System.out.println("*** Using File index "
113: + indexfile);
114: ki = new kelondroCache(kelondroTree.open(indexfile,
115: true, preloadTime, treeIndexRow(rowdef
116: .width(0), rowdef.objectOrder), 2,
117: 80));
118: RAMIndex = false;
119: } else {
120: // generate new index file
121: System.out.println("*** Generating File index for "
122: + size() + " entries from " + indexfile);
123: System.out.println("*** Cause: too less RAM ("
124: + serverMemory.available()
125: + " Bytes) configured. Assign at least "
126: + (neededRAM / 1024 / 1024)
127: + " MB more RAM to enable a RAM index.");
128: ki = initializeTreeIndex(indexfile, preloadTime,
129: rowdef.objectOrder);
130:
131: System.out.println(" -done-");
132: System.out.println(ki.size()
133: + " entries indexed from "
134: + super .col[0].size() + " keys.");
135: RAMIndex = false;
136: }
137: index = new kelondroBytesIntMap(ki);
138: assert this .size() == index.size() : "content.size() = "
139: + this .size()
140: + ", index.size() = "
141: + index.size();
142: }
143:
144: // check consistency
145: ArrayList<Integer[]> doubles = index.removeDoubles();
146: if (doubles.size() > 0) {
147: System.out.println("DEBUG: WARNING - FlexTable "
148: + newpath.toString() + " has " + doubles.size()
149: + " doubles");
150: }
151:
152: // assign index to wrapper
153: description = "stt="
154: + Long.toString(System.currentTimeMillis() - start)
155: + ";";
156: super .col[0].setDescription(description.getBytes());
157: } catch (IOException e) {
158: if (resetOnFail) {
159: RAMIndex = true;
160: index = new kelondroBytesIntMap(
161: super .row().column(0).cellwidth,
162: super .rowdef.objectOrder, 0);
163: } else {
164: throw new kelondroException(e.getMessage());
165: }
166: }
167: }
168:
169: public void reset() throws IOException {
170: super .reset();
171: RAMIndex = true;
172: index = new kelondroBytesIntMap(
173: super .row().column(0).cellwidth,
174: super .rowdef.objectOrder, 0);
175: }
176:
177: public static int staticSize(File path, String tablename) {
178: return kelondroFlexWidthArray.staticsize(path, tablename);
179: }
180:
181: public static int staticRAMIndexNeed(File path, String tablename,
182: kelondroRow rowdef) {
183: return (int) ((rowdef.column(0).cellwidth + 4)
184: * staticSize(path, tablename) * kelondroRowSet.growfactor);
185: }
186:
187: public boolean hasRAMIndex() {
188: return RAMIndex;
189: }
190:
191: public synchronized boolean has(byte[] key) throws IOException {
192: // it is not recommended to implement or use a has predicate unless
193: // it can be ensured that it causes no IO
194: if ((kelondroAbstractRecords.debugmode) && (RAMIndex != true))
195: serverLog.logWarning("kelondroFlexTable",
196: "RAM index warning in file " + super .tablename);
197: assert this .size() == index.size() : "content.size() = "
198: + this .size() + ", index.size() = " + index.size();
199: return index.geti(key) >= 0;
200: }
201:
202: private kelondroBytesIntMap initializeRamIndex(int initialSpace) {
203: int space = Math.max(super .col[0].size(), initialSpace) + 1;
204: if (space < 0)
205: throw new kelondroException("wrong space: " + space);
206: kelondroBytesIntMap ri = new kelondroBytesIntMap(super .row()
207: .column(0).cellwidth, super .rowdef.objectOrder, space);
208: Iterator<kelondroNode> content = super .col[0].contentNodes(-1);
209: kelondroNode node;
210: int i;
211: byte[] key;
212: while (content.hasNext()) {
213: node = content.next();
214: i = node.handle().hashCode();
215: key = node.getKey();
216: assert (key != null) : "DEBUG: empty key in initializeRamIndex"; // should not happen; if it does, it is an error of the condentNodes iterator
217: //System.out.println("ENTRY: " + serverLog.arrayList(indexentry.bytes(), 0, indexentry.objectsize()));
218: try {
219: ri.addi(key, i);
220: } catch (IOException e) {
221: } // no IOException can happen here
222: if ((i % 10000) == 0) {
223: System.out.print('.');
224: System.out.flush();
225: }
226: }
227: System.out.print(" -ordering- ");
228: System.out.flush();
229: return ri;
230: }
231:
232: private kelondroIndex initializeTreeIndex(File indexfile,
233: long preloadTime, kelondroByteOrder objectOrder)
234: throws IOException {
235: kelondroIndex treeindex = new kelondroCache(new kelondroTree(
236: indexfile, true, preloadTime, treeIndexRow(
237: rowdef.primaryKeyLength, objectOrder), 2, 80));
238: Iterator<kelondroNode> content = super .col[0].contentNodes(-1);
239: kelondroNode node;
240: kelondroRow.Entry indexentry;
241: int i, c = 0, all = super .col[0].size();
242: long start = System.currentTimeMillis();
243: long last = start;
244: while (content.hasNext()) {
245: node = content.next();
246: i = node.handle().hashCode();
247: indexentry = treeindex.row().newEntry();
248: indexentry.setCol(0, node.getValueRow());
249: indexentry.setCol(1, i);
250: treeindex.addUnique(indexentry);
251: c++;
252: if (System.currentTimeMillis() - last > 30000) {
253: System.out.println(".. generated "
254: + c
255: + "/"
256: + all
257: + " entries, "
258: + ((System.currentTimeMillis() - start) / c
259: * (all - c) / 60000)
260: + " minutes remaining");
261: System.out.flush();
262: last = System.currentTimeMillis();
263: }
264: }
265: return treeindex;
266: }
267:
268: private static final kelondroRow treeIndexRow(int keywidth,
269: kelondroByteOrder objectOrder) {
270: return new kelondroRow("byte[] key-" + keywidth
271: + ", int reference-4 {b256}", objectOrder, 0);
272: }
273:
274: public synchronized kelondroRow.Entry get(byte[] key)
275: throws IOException {
276: if (index == null)
277: return null; // case may happen during shutdown
278: int pos = index.geti(key);
279: assert this .size() == index.size() : "content.size() = "
280: + this .size() + ", index.size() = " + index.size();
281: if (pos < 0)
282: return null;
283: // pos may be greater than this.size(), because this table may have deleted entries
284: // the deleted entries are subtracted from the 'real' tablesize,
285: // so the size may be smaller than an index to a row entry
286: /*if (kelondroAbstractRecords.debugmode) {
287: kelondroRow.Entry result = super.get(pos);
288: assert result != null;
289: assert rowdef.objectOrder.compare(result.getPrimaryKeyBytes(), key) == 0 : "key and row does not match; key = " + serverLog.arrayList(key, 0, key.length) + " row.key = " + serverLog.arrayList(result.getPrimaryKeyBytes(), 0, rowdef.primaryKeyLength);
290: return result;
291: } else {*/
292: // assume that the column for the primary key is 0,
293: // and the column 0 is stored in a file only for that column
294: // then we don't need to lookup from that file, because we already know the value (it's the key)
295: kelondroRow.Entry result = super .getOmitCol0(pos, key);
296: assert result != null;
297: return result;
298: //}
299: }
300:
301: public synchronized void putMultiple(List<kelondroRow.Entry> rows)
302: throws IOException {
303: // put a list of entries in a ordered way.
304: // this should save R/W head positioning time
305: Iterator<kelondroRow.Entry> i = rows.iterator();
306: kelondroRow.Entry row;
307: int pos;
308: byte[] key;
309: TreeMap<Integer, kelondroRow.Entry> old_rows_ordered = new TreeMap<Integer, kelondroRow.Entry>();
310: ArrayList<kelondroRow.Entry> new_rows_sequential = new ArrayList<kelondroRow.Entry>();
311: assert this .size() == index.size() : "content.size() = "
312: + this .size() + ", index.size() = " + index.size();
313: while (i.hasNext()) {
314: row = i.next();
315: key = row.getColBytes(0);
316: pos = index.geti(key);
317: if (pos < 0) {
318: new_rows_sequential.add(row);
319: } else {
320: old_rows_ordered.put(new Integer(pos), row);
321: }
322: }
323: // overwrite existing entries in index
324: super .setMultiple(old_rows_ordered);
325:
326: // write new entries to index
327: addUniqueMultiple(new_rows_sequential);
328: assert this .size() == index.size() : "content.size() = "
329: + this .size() + ", index.size() = " + index.size();
330: }
331:
332: public synchronized kelondroRow.Entry put(kelondroRow.Entry row,
333: Date entryDate) throws IOException {
334: assert this .size() == index.size() : "content.size() = "
335: + this .size() + ", index.size() = " + index.size();
336: return put(row);
337: }
338:
339: public synchronized kelondroRow.Entry put(kelondroRow.Entry row)
340: throws IOException {
341: assert (row != null);
342: assert (!(serverLog.allZero(row.getColBytes(0))));
343: assert row.objectsize() <= this .rowdef.objectsize;
344: byte[] key = row.getColBytes(0);
345: if (index == null)
346: return null; // case may appear during shutdown
347: int pos = index.geti(key);
348: if (pos < 0) {
349: pos = super .add(row);
350: index.puti(key, pos);
351: assert this .size() == index.size() : "content.size() = "
352: + this .size() + ", index.size() = " + index.size();
353: return null;
354: }
355: //System.out.println("row.key=" + serverLog.arrayList(row.bytes(), 0, row.objectsize()));
356: kelondroRow.Entry oldentry = super .get(pos);
357: assert this .size() == index.size() : "content.size() = "
358: + this .size() + ", index.size() = " + index.size();
359: if (oldentry == null) {
360: serverLog
361: .logSevere(
362: "kelondroFlexTable",
363: "put(): index failure; the index pointed to a cell which is empty. content.size() = "
364: + this .size()
365: + ", index.size() = "
366: + ((index == null) ? 0 : index
367: .size()));
368: // patch bug ***** FIND CAUSE! (see also: remove)
369: int oldindex = index.removei(key);
370: assert oldindex >= 0;
371: assert index.geti(key) == -1;
372: // here is this.size() > index.size() because of remove operation above
373: index.puti(key, super .add(row));
374: assert this .size() == index.size() : "content.size() = "
375: + this .size() + ", index.size() = " + index.size();
376: return null;
377: }
378: assert oldentry != null : "overwrite of empty position " + pos
379: + ", index management must have failed before";
380: assert rowdef.objectOrder.compare(
381: oldentry.getPrimaryKeyBytes(), key) == 0 : "key and row does not match; key = "
382: + serverLog.arrayList(key, 0, key.length)
383: + " row.key = "
384: + serverLog.arrayList(oldentry.getPrimaryKeyBytes(), 0,
385: rowdef.primaryKeyLength);
386: super .set(pos, row);
387: assert this .size() == index.size() : "content.size() = "
388: + this .size() + ", index.size() = " + index.size();
389: return oldentry;
390: }
391:
392: public synchronized void addUnique(kelondroRow.Entry row)
393: throws IOException {
394: assert row.objectsize() == this .rowdef.objectsize;
395: assert this .size() == index.size() : "content.size() = "
396: + this .size() + ", index.size() = " + index.size();
397: index.addi(row.getColBytes(0), super .add(row));
398: }
399:
400: public synchronized void addUniqueMultiple(
401: List<kelondroRow.Entry> rows) throws IOException {
402: // add a list of entries in a ordered way.
403: // this should save R/W head positioning time
404: TreeMap<Integer, byte[]> indexed_result = super
405: .addMultiple(rows);
406: // indexed_result is a Integer/byte[] relation
407: // that is used here to store the index
408: Iterator<Map.Entry<Integer, byte[]>> i = indexed_result
409: .entrySet().iterator();
410: Map.Entry<Integer, byte[]> entry;
411: while (i.hasNext()) {
412: entry = i.next();
413: index.puti(entry.getValue(), entry.getKey().intValue());
414: }
415: assert this .size() == index.size() : "content.size() = "
416: + this .size() + ", index.size() = " + index.size();
417:
418: }
419:
420: public synchronized ArrayList<kelondroRowSet> removeDoubles()
421: throws IOException {
422: ArrayList<Integer[]> indexreport = index.removeDoubles();
423: ArrayList<kelondroRowSet> report = new ArrayList<kelondroRowSet>();
424: Iterator<Integer[]> i = indexreport.iterator();
425: Integer[] is;
426: kelondroRowSet rows;
427: TreeSet<Integer> d = new TreeSet<Integer>();
428: while (i.hasNext()) {
429: is = i.next();
430: rows = new kelondroRowSet(this .rowdef, is.length);
431: for (int j = 0; j < is.length; j++) {
432: d.add(is[j]);
433: rows.addUnique(this .get(is[j].intValue()));
434: }
435: report.add(rows);
436: }
437: // finally delete the affected rows, but start with largest id first, othervise we overwrite wrong entries
438: Integer s;
439: while (d.size() > 0) {
440: s = d.last();
441: d.remove(s);
442: this .remove(s.intValue());
443: }
444: return report;
445: }
446:
447: public synchronized kelondroRow.Entry remove(byte[] key,
448: boolean keepOrder) throws IOException {
449: assert keepOrder == false; // the underlying data structure is a file, where the order cannot be maintained. Gaps are filled with new values.
450: int i = index.removei(key);
451: assert (index.geti(key) < 0); // must be deleted
452: if (i < 0) {
453: assert this .size() == index.size() : "content.size() = "
454: + this .size() + ", index.size() = " + index.size();
455: return null;
456: }
457: kelondroRow.Entry r = super .getOmitCol0(i, key);
458: if (r == null) {
459: serverLog
460: .logSevere(
461: "kelondroFlexTable",
462: "remove(): index failure; the index pointed to a cell which is empty. content.size() = "
463: + this .size()
464: + ", index.size() = "
465: + ((index == null) ? 0 : index
466: .size()));
467: // patch bug ***** FIND CAUSE! (see also: put)
468: assert this .size() == index.size() : "content.size() = "
469: + this .size() + ", index.size() = " + index.size();
470: return null;
471: }
472: assert r != null : "r == null"; // should be avoided with path above
473: assert rowdef.objectOrder.compare(r.getPrimaryKeyBytes(), key) == 0 : "key and row does not match; key = "
474: + serverLog.arrayList(key, 0, key.length)
475: + " row.key = "
476: + serverLog.arrayList(r.getPrimaryKeyBytes(), 0,
477: rowdef.primaryKeyLength);
478: super .remove(i);
479: assert super .get(i) == null : "i = " + i + ", get(i) = "
480: + serverLog.arrayList(super .get(i).bytes(), 0, 12);
481: assert this .size() == index.size() : "content.size() = "
482: + this .size() + ", index.size() = " + index.size();
483: return r;
484: }
485:
486: public synchronized kelondroRow.Entry removeOne()
487: throws IOException {
488: int i = index.removeonei();
489: if (i < 0)
490: return null;
491: kelondroRow.Entry r;
492: r = super .get(i);
493: super .remove(i);
494: assert this .size() == index.size() : "content.size() = "
495: + this .size() + ", index.size() = " + index.size();
496: return r;
497: }
498:
499: public synchronized kelondroCloneableIterator<byte[]> keys(
500: boolean up, byte[] firstKey) throws IOException {
501: return index.keys(up, firstKey);
502: }
503:
504: public synchronized kelondroCloneableIterator<kelondroRow.Entry> rows(
505: boolean up, byte[] firstKey) throws IOException {
506: if (index == null)
507: return new rowIterator(index, up, firstKey);
508: assert this .size() == index.size() : "content.size() = "
509: + this .size() + ", index.size() = " + index.size();
510: return new rowIterator(index, up, firstKey);
511: }
512:
513: public class rowIterator implements
514: kelondroCloneableIterator<kelondroRow.Entry> {
515:
516: kelondroCloneableIterator<kelondroRow.Entry> indexIterator;
517: kelondroBytesIntMap index;
518: boolean up;
519:
520: public rowIterator(kelondroBytesIntMap index, boolean up,
521: byte[] firstKey) throws IOException {
522: this .index = index;
523: this .up = up;
524: indexIterator = index.rows(up, firstKey);
525: }
526:
527: public rowIterator clone(Object modifier) {
528: try {
529: return new rowIterator(index, up, (byte[]) modifier);
530: } catch (IOException e) {
531: return null;
532: }
533: }
534:
535: public boolean hasNext() {
536: return indexIterator.hasNext();
537: }
538:
539: public kelondroRow.Entry next() {
540: kelondroRow.Entry idxEntry = null;
541: while ((indexIterator.hasNext()) && (idxEntry == null)) {
542: idxEntry = (kelondroRow.Entry) indexIterator.next();
543: }
544: if (idxEntry == null) {
545: serverLog.logSevere("kelondroFlexTable.rowIterator: "
546: + tablename, "indexIterator returned null");
547: return null;
548: }
549: int idx = (int) idxEntry.getColLong(1);
550: try {
551: return get(idx);
552: } catch (IOException e) {
553: e.printStackTrace();
554: return null;
555: }
556: }
557:
558: public void remove() {
559: indexIterator.remove();
560: }
561:
562: }
563:
564: public kelondroProfile profile() {
565: return index.profile();
566: }
567:
568: public static final Iterator<String> filenames() {
569: // iterates string objects; all file names from record tracker
570: return tableTracker.keySet().iterator();
571: }
572:
573: public static final kelondroProfile profileStats(String filename) {
574: // returns a map for each file in the tracker;
575: // the map represents properties for each record oobjects,
576: // i.e. for cache memory allocation
577: kelondroFlexTable theFlexTable = (kelondroFlexTable) tableTracker
578: .get(filename);
579: return theFlexTable.profile();
580: }
581:
582: public static final Map<String, String> memoryStats(String filename) {
583: // returns a map for each file in the tracker;
584: // the map represents properties for each record objects,
585: // i.e. for cache memory allocation
586: kelondroFlexTable theFlexTable = (kelondroFlexTable) tableTracker
587: .get(filename);
588: return theFlexTable.memoryStats();
589: }
590:
591: private final Map<String, String> memoryStats() {
592: // returns statistical data about this object
593: HashMap<String, String> map = new HashMap<String, String>();
594: map.put("tableIndexChunkSize", (!RAMIndex) ? "0" : Integer
595: .toString(index.row().objectsize));
596: map.put("tableIndexCount", (!RAMIndex) ? "0" : Integer
597: .toString(index.size()));
598: map
599: .put(
600: "tableIndexMem",
601: (!RAMIndex) ? "0"
602: : Integer
603: .toString((int) (index.row().objectsize
604: * index.size() * kelondroRowCollection.growfactor)));
605: return map;
606: }
607:
608: public synchronized void close() {
609: if (tableTracker.remove(this .filename) == null) {
610: serverLog.logWarning("kelondroFlexTable", "close(): file '"
611: + this .filename
612: + "' was not tracked with record tracker.");
613: }
614: if ((index != null)
615: && (this .size() != ((index == null) ? 0 : index.size()))) {
616: serverLog.logSevere("kelondroFlexTable",
617: "close(): inconsistent content/index size. content.size() = "
618: + this .size() + ", index.size() = "
619: + ((index == null) ? 0 : index.size()));
620: }
621:
622: if (index != null) {
623: index.close();
624: index = null;
625: }
626: super .close();
627: }
628:
629: public static void main(String[] args) {
630: // open a file, add one entry and exit
631: File f = new File(args[0]);
632: String name = args[1];
633: kelondroRow row = new kelondroRow(
634: "Cardinal key-4 {b256}, byte[] x-64",
635: kelondroNaturalOrder.naturalOrder, 0);
636: try {
637: kelondroFlexTable t = new kelondroFlexTable(f, name, 0,
638: row, 0, true);
639: kelondroRow.Entry entry = row.newEntry();
640: entry.setCol(0, System.currentTimeMillis());
641: entry.setCol(1, "dummy".getBytes());
642: t.put(entry);
643: t.close();
644: } catch (IOException e) {
645: e.printStackTrace();
646: }
647: }
648:
649: }
|