0001: /*
0002: This source file is part of Smyle, a database library.
0003: For up-to-date information, see http://www.drjava.de/smyle
0004: Copyright (C) 2001 Stefan Reich (doc@drjava.de)
0005:
0006: This library is free software; you can redistribute it and/or
0007: modify it under the terms of the GNU Lesser General Public
0008: License as published by the Free Software Foundation; either
0009: version 2.1 of the License, or (at your option) any later version.
0010:
0011: This library is distributed in the hope that it will be useful,
0012: but WITHOUT ANY WARRANTY; without even the implied warranty of
0013: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0014: Lesser General Public License for more details.
0015:
0016: You should have received a copy of the GNU Lesser General Public
0017: License along with this library; if not, write to the Free Software
0018: Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
0019:
0020: For full license text, see doc/license/lgpl.txt in this distribution
0021: */
0022:
0023: package drjava.smyle.core;
0024:
0025: import java.io.*;
0026: import java.util.*;
0027: import java.lang.Object;
0028: import java.lang.ref.*;
0029: import org.artsProject.mcop.*;
0030: import org.artsProject.mcop.core.*;
0031: import org.artsProject.util.*;
0032: import drjava.gjutil.*;
0033: import drjava.smyle.*;
0034: import drjava.smyle.meta.*;
0035: import drjava.smyle.core.indexing.*;
0036:
0037: public final class TableImpl<T extends Struct<T>> implements Table<T>,
0038: UntypedTable {
0039: final SnapshotImpl snapshot;
0040: final ChunkManager chunkManager;
0041: ChunkRef schemaChunk = ChunkManager.NULLCHUNK;
0042: FastIntVector elements = new FastIntVector();
0043: Demarshaller<T> demarshaller;
0044: StructInfo<T> type;
0045: FunctionMarDemar<T> fmd;
0046: int id;
0047: boolean mutable = true, dirty = false;
0048: String whyImmutable;
0049: transient int modCount = 0;
0050:
0051: int maxKeyLength = 16;
0052: UniversalKey maxKey;
0053: ArrayList<Index<T>> indexes = new ArrayList<Index<T>>();
0054: IndexAdvisor<Pair<IndexProfile, Function>> indexAdvisor = null;
0055:
0056: Field<T, Integer> autoincField = null;
0057: int autoincCounter = 0;
0058:
0059: /** maximum size of an index tree leaf */
0060: static final int INDEX_M = 20;
0061:
0062: static final boolean debug = false, profiling = false;
0063:
0064: static final StructInfo UNTYPED = new StructInfo(null, null, null,
0065: null);
0066:
0067: private <U extends Struct<U>> Demarshaller<U> constructCustomDemarshaller(
0068: StructInfo existingType,
0069: StructInfo<U> type,
0070: HashMap<Pair<StructInfo, StructInfo>, FieldBasedDemarshaller> catalog)
0071: throws SchemaChangeException {
0072: Pair<StructInfo, StructInfo> catalogKey = new Pair<StructInfo, StructInfo>(
0073: existingType, type);
0074: FieldBasedDemarshaller<U> demarshaller = catalog
0075: .get(catalogKey);
0076: if (demarshaller != null)
0077: return demarshaller;
0078:
0079: demarshaller = new FieldBasedDemarshaller<U>(type);
0080: catalog.put(catalogKey, demarshaller);
0081:
0082: int removedFields = 0;
0083: for (int i = 0; i < existingType.typeDef.contents.size(); i++) {
0084: TypeComponent c = existingType.typeDef.contents.get(i);
0085: int iNew = type.findTypeComponent(c.name);
0086: if (iNew < 0) {
0087: mutable = false;
0088: if (whyImmutable != null)
0089: whyImmutable += ", " + c.name;
0090: else
0091: whyImmutable = "Missing field(s): " + c.name;
0092: ++removedFields;
0093: } else {
0094: TypeComponent cNew = type.typeDef.contents.get(iNew);
0095: if (!cNew.type.equals(c.type)) {
0096: if (existingType.fieldTypes[i] != null) {
0097: /*if (debug) {
0098: System.out.println("Demarshaller field "+existingType.fieldTypes[i].typeDef+" -> "+(type.fieldTypes[iNew] != null ? type.fieldTypes[iNew].typeDef : null));
0099: System.out.println("New type: "+cNew.type);
0100: }*/
0101: Demarshaller d = constructCustomDemarshaller(
0102: existingType.fieldTypes[i],
0103: type.fieldTypes[iNew], catalog);
0104: if (cNew.type.startsWith("*"))
0105: demarshaller.addSequenceField(iNew, d);
0106: else
0107: demarshaller.addDemarshallerField(iNew, d);
0108: continue;
0109: }
0110: throw new SchemaChangeException("Field " + c.name
0111: + " had type " + c.type + "; now "
0112: + cNew.type + "\n" + "Old schema: "
0113: + existingType.typeDef + "\n"
0114: + "New schema: " + type.typeDef);
0115: }
0116: }
0117:
0118: if (c.type.equals("long"))
0119: demarshaller.addLongField(iNew);
0120: else if (c.type.equals("long long"))
0121: demarshaller.addLongLongField(iNew);
0122: else if (c.type.equals("boolean"))
0123: demarshaller.addBooleanField(iNew);
0124: else if (c.type.equals("string"))
0125: demarshaller.addStringField(iNew);
0126: else if (c.type.startsWith("*"))
0127: if (type.fieldTypes[iNew] != null)
0128: demarshaller.addSequenceField(iNew,
0129: type.fieldTypes[iNew].demarshaller);
0130: else if (c.type.equals("*string"))
0131: demarshaller.addStringSequenceField(iNew);
0132: else if (c.type.equals("*byte"))
0133: demarshaller.addByteSequenceField(iNew);
0134: else if (c.type.equals("*long"))
0135: demarshaller.addLongSequenceField(iNew);
0136: else
0137: throw new RuntimeException("TODO: " + c.type);
0138: else if (type.fieldTypes[iNew] == null)
0139: demarshaller.addLongField(iNew); // enum
0140: else
0141: demarshaller
0142: .addStructField(iNew, type.fieldTypes[iNew]);
0143: }
0144:
0145: // adding and removing fields at the same time is not allowed
0146: if (removedFields != 0
0147: && type.typeDef.contents.size() != existingType.typeDef.contents
0148: .size()
0149: - removedFields) {
0150: throw new SchemaChangeException(
0151: "Adding and removing fields at the same time is not allowed");
0152: }
0153:
0154: return demarshaller;
0155: }
0156:
0157: /** create an untyped table */
0158: TableImpl(SnapshotImpl snapshot, int id, ChunkRef tableChunk,
0159: String name) {
0160: this (snapshot, UNTYPED, id, tableChunk, name);
0161: }
0162:
0163: /** create a typed table */
0164: TableImpl(SnapshotImpl snapshot, StructInfo<T> type, int id,
0165: ChunkRef tableChunk, String name) {
0166: this .snapshot = snapshot;
0167: chunkManager = snapshot.store.chunkManager;
0168: int version = snapshot.store.version;
0169: this .type = type;
0170: fmd = new FunctionMarDemar<T>(type);
0171: this .demarshaller = type.demarshaller;
0172: TypeDef schema = type.typeDef;
0173: this .id = id;
0174:
0175: setMaxKeyLength(maxKeyLength);
0176:
0177: // read elements file
0178:
0179: try {
0180: //if (debug) System.out.println("tableChunk: "+tableChunk.id);
0181: if (tableChunk.index != 0) {
0182: Buffer b = chunkManager.readChunk(tableChunk);
0183: if (version >= 2)
0184: schemaChunk = new ChunkRef(b);
0185: elements.read(b);
0186:
0187: // load index
0188:
0189: if (version >= 281) {
0190: // load autoincrement field
0191:
0192: if (version >= 27) {
0193: int fieldNr = b.readLong();
0194: if (fieldNr >= 0) {
0195: autoincField = (Field) new FunctionMarDemar(
0196: type).getField(fieldNr);
0197: autoincCounter = b.readLong();
0198: }
0199: }
0200:
0201: if (version >= 890) {
0202: int numIndexes = b.readLong();
0203: for (int i = 0; i < numIndexes; i++)
0204: indexes.add(new Index(this , b));
0205: }
0206: }
0207: }
0208:
0209: StructInfo existingType = loadType();
0210: TypeDef existingSchema = existingType != null ? existingType.typeDef
0211: : null;
0212: //if (debug) System.out.println("version: "+version+", schema: "+existingSchema+", new schema: "+schema);
0213:
0214: // convert to new chunk manager
0215: if (chunkManager != snapshot.newChunkManager) {
0216: schemaChunk = snapshot.reStoreChunk(schemaChunk);
0217: for (int i = 0; i < elements.size(); i++) {
0218: elements.set(i, snapshot.reStoreChunk(new ChunkRef(
0219: elements.get(i))).index);
0220: if (i % 100 == 0 && i != 0)
0221: log(getName() + ": " + i
0222: + " elements converted");
0223: }
0224: }
0225:
0226: // Check for compatibility
0227: // TODO: this is a mess - refactor!
0228: boolean schemaChange = existingType != null && type != null
0229: && existingType.typeDef != null
0230: && type.typeDef != null
0231: && !existingType.equals(type);
0232: /*if (schemaChange) {
0233: System.out.println("old schema: "+(existingType != null ? existingType.typeDef : null));
0234: System.out.println("new schema: "+(type != null ? type.typeDef : null));
0235: }*/
0236: if (elements.size() != 0 && schemaChange) {
0237: // throws SchemaChangeException if it fails
0238: demarshaller = constructCustomDemarshaller(
0239: existingType,
0240: type,
0241: new HashMap<Pair<StructInfo, StructInfo>, FieldBasedDemarshaller>());
0242:
0243: clearIndexes();
0244:
0245: // convert table to new schema
0246: for (int i = 0; i < elements.size(); i++) {
0247: T t = loadElement(i);
0248: //if (debug) System.out.println("Element read: "+t);
0249: saveElement(t, i);
0250: }
0251:
0252: // use new schema's native demarshaller from now on
0253: demarshaller = type.demarshaller;
0254: }
0255:
0256: if (schema != null
0257: && (existingSchema == null || schemaChange)) {
0258: saveSchema();
0259: if (debug)
0260: System.out.println("Saved schema: " + schemaChunk);
0261: }
0262:
0263: // for untyped case
0264: if (this .type == null || this .type.typeDef == null)
0265: this .type = existingType;
0266:
0267: //if (debug) System.out.println("Final schema: "+(this.type != null ? this.type.typeDef : null));
0268:
0269: indexAdvisor = snapshot.store.getIndexAdvisor(name, type);
0270: buildIndexIfAdvised(); // this must be done somewhere
0271: } catch (MCOPException e) {
0272: e.printStackTrace();
0273: throw new InternalSmyleError(e);
0274: }
0275: }
0276:
0277: void flush() {
0278: synchronized (snapshot) {
0279: try {
0280: enter("flush");
0281: //System.out.println("Table "+id+".flush: dirty="+dirty);
0282: if (dirty) {
0283: // write table chunk
0284: Buffer b = new Buffer();
0285: schemaChunk.writeType(b);
0286: elements.marshal(b);
0287:
0288: // save autoincrement field
0289:
0290: if (autoincField != null) {
0291: b.writeLong(autoincField.nr());
0292: b.writeLong(autoincCounter);
0293: } else
0294: b.writeLong(-1);
0295:
0296: // save index
0297:
0298: MCOP.writeSeq(b, indexes);
0299:
0300: ChunkRef chunk = snapshot.newChunkManager
0301: .createChunk(b);
0302: //if (debug) System.out.println("Wrote "+elements.size()+" elements to chunk "+chunk+", schemaChunk="+schemaChunk);
0303: snapshot.setTableChunk(id, chunk);
0304: dirty = false;
0305: }
0306: } finally {
0307: leave();
0308: }
0309: }
0310: }
0311:
0312: private void assertMutable() {
0313: snapshot.assertMutable();
0314: if (!mutable)
0315: throw new ImmutableTableException(whyImmutable);
0316: }
0317:
0318: public boolean add(T t) {
0319: synchronized (snapshot) {
0320: try {
0321: enter("add");
0322: assertMutable();
0323: ++modCount;
0324: int chunk = saveElement(t);
0325: elements.add(chunk);
0326: return true;
0327: } finally {
0328: leave();
0329: }
0330: }
0331: }
0332:
0333: public void add(int index, T t) {
0334: synchronized (snapshot) {
0335: try {
0336: enter("add");
0337: assertMutable();
0338: ++modCount;
0339: elements.add(index, 0);
0340: saveElement(t, index);
0341: } finally {
0342: leave();
0343: }
0344: }
0345: }
0346:
0347: private void saveElement(T t, int index) {
0348: elements.set(index, saveElement(t));
0349: }
0350:
0351: private int saveElement(T t) {
0352: // check element type
0353:
0354: if (!type.structClass.isInstance(t)) {
0355: if (t == null)
0356: throw new NullPointerException(
0357: "Null elements are not allowed");
0358: throw new ClassCastException("Bad element type: "
0359: + t.getClass().getName() + ", expected "
0360: + type.structClass.getName());
0361: }
0362:
0363: // auto increment handling
0364:
0365: if (autoincField != null) {
0366: int value = autoincField.of(t).intValue();
0367: if (value == 0)
0368: autoincField.set(t, new Integer(++autoincCounter));
0369: else
0370: autoincCounter = Math.max(autoincCounter, value);
0371: }
0372:
0373: // save to chunk
0374:
0375: ChunkRef chunk = snapshot.newChunkManager.createChunk(t);
0376: addToIndex(t, chunk);
0377: dirty = true;
0378: return chunk.index;
0379: }
0380:
0381: public boolean addAll(Collection<T> c) {
0382: synchronized (snapshot) {
0383: try {
0384: enter("addAll");
0385: return addAll(elements.size(), c);
0386: } finally {
0387: leave();
0388: }
0389: }
0390: }
0391:
0392: public boolean addAll(int index, Collection<T> c) {
0393: synchronized (snapshot) {
0394: try {
0395: enter("addAll");
0396: assertMutable();
0397: boolean changed = false;
0398: for (Iterator<T> i = c.iterator(); i.hasNext();) {
0399: changed = true;
0400: add(index++, i.next());
0401: }
0402: return changed;
0403: } finally {
0404: leave();
0405: }
0406: }
0407: }
0408:
0409: public boolean isEmpty() {
0410: synchronized (snapshot) {
0411: try {
0412: enter("isEmpty");
0413: return size() == 0;
0414: } finally {
0415: leave();
0416: }
0417: }
0418: }
0419:
0420: public T loadElement(int i) {
0421: synchronized (snapshot) {
0422: try {
0423: enter("loadElement");
0424: try {
0425: int chunk = elements.get(i);
0426: //if (debug) System.out.println("loadElement #"+i+" fr="+fr.id);
0427: return demarshaller.read(chunkManager
0428: .readChunk(chunk));
0429: } catch (MCOPException e) {
0430: throw new InternalSmyleError(e);
0431: }
0432: } finally {
0433: leave();
0434: }
0435: }
0436: }
0437:
0438: public T loadElement(ChunkRef chunk) {
0439: synchronized (snapshot) {
0440: try {
0441: enter("loadElement");
0442: return loadElementChunk(chunk.index);
0443: } finally {
0444: leave();
0445: }
0446: }
0447: }
0448:
0449: public T loadElementChunk(int chunk) {
0450: synchronized (snapshot) {
0451: try {
0452: enter("loadElementChunk");
0453: try {
0454: return demarshaller.read(chunkManager
0455: .readChunk(chunk));
0456: } catch (MCOPException e) {
0457: System.err.println("chunk=" + chunk);
0458: throw new InternalSmyleError(e);
0459: }
0460: } finally {
0461: leave();
0462: }
0463: }
0464: }
0465:
0466: public T first() {
0467: synchronized (snapshot) {
0468: try {
0469: enter("first");
0470: if (elements.isEmpty())
0471: return null;
0472: return loadElement(0);
0473: } finally {
0474: leave();
0475: }
0476: }
0477: }
0478:
0479: public T get(int nr) {
0480: synchronized (snapshot) {
0481: try {
0482: enter("get(int)");
0483: return loadElement(nr);
0484: } finally {
0485: leave();
0486: }
0487: }
0488: }
0489:
0490: public int size() {
0491: synchronized (snapshot) {
0492: try {
0493: enter("size");
0494: return elements.size();
0495: } finally {
0496: leave();
0497: }
0498: }
0499: }
0500:
0501: public void clear() {
0502: synchronized (snapshot) {
0503: try {
0504: enter("clear");
0505: assertMutable();
0506: elements.clear();
0507: clearIndexes();
0508: ++modCount;
0509: dirty = true;
0510: } finally {
0511: leave();
0512: }
0513: }
0514: }
0515:
0516: public void removeAll(Filter<T> filter) {
0517: synchronized (snapshot) {
0518: try {
0519: enter("removeAll");
0520: assertMutable();
0521: ArrayList<ChunkRef> list = new ArrayList<ChunkRef>();
0522:
0523: TableIterator<T> it = iteratorImpl(filter);
0524: while (it.hasNext())
0525: list.add(it.nextChunk());
0526:
0527: //System.out.println("ChunkRefs for "+clause.getValue()+": "+list);
0528: for (int i = 0; i < list.size(); i++)
0529: removeChunk(list.get(i).index);
0530:
0531: buildIndexIfAdvised();
0532: } finally {
0533: leave();
0534: }
0535: }
0536: }
0537:
0538: UniversalKey cutKey(UniversalKey key) {
0539: return key.cut(maxKeyLength);
0540: }
0541:
0542: public boolean contains(Filter<T> filter) {
0543: synchronized (snapshot) {
0544: try {
0545: enter("contains(Filter)");
0546: return iterator(filter).hasNext();
0547: } finally {
0548: leave();
0549: }
0550: }
0551: }
0552:
0553: public boolean contains(T t) {
0554: synchronized (snapshot) {
0555: try {
0556: enter("contains(T)");
0557: return iterator(elementToFilter(t)).hasNext();
0558: } finally {
0559: leave();
0560: }
0561: }
0562: }
0563:
0564: public int count(Filter<T> filter) {
0565: synchronized (snapshot) {
0566: try {
0567: enter("count");
0568: int count = 0;
0569: for (TableIterator<T> i = iteratorImpl(filter); i
0570: .hasNext();) {
0571: i.nextChunk();
0572: ++count;
0573: }
0574: return count;
0575: } finally {
0576: leave();
0577: }
0578: }
0579: }
0580:
0581: public int indexOf(Filter<T> filter) {
0582: synchronized (snapshot) {
0583: try {
0584: enter("indexOf(Filter)");
0585: TableIterator<T> i = iteratorImpl(filter);
0586: if (!i.hasNext())
0587: return -1;
0588: int result = Integer.MAX_VALUE;
0589: do {
0590: ChunkRef cr = i.nextChunk();
0591: int idx = elements.indexOf(cr.index);
0592: if (idx < result)
0593: result = idx;
0594: } while (i.hasNext());
0595: return result;
0596: } finally {
0597: leave();
0598: }
0599: }
0600: }
0601:
0602: public T get(Filter<T> filter) {
0603: synchronized (snapshot) {
0604: try {
0605: enter("get(Filter)");
0606: Iterator<T> i = iterator(filter);
0607: return i.hasNext() ? i.next() : null;
0608: } finally {
0609: leave();
0610: }
0611: }
0612: }
0613:
0614: public T getOrCreate(Filter<T> filter) {
0615: synchronized (snapshot) {
0616: try {
0617: enter("getOrCreate");
0618: T t = get(filter);
0619: return t != null ? t : filter._createMatchingElement();
0620: } finally {
0621: leave();
0622: }
0623: }
0624: }
0625:
0626: public void put(Filter<T> filter, T t) {
0627: synchronized (snapshot) {
0628: try {
0629: enter("put");
0630: int idx = indexOf(filter);
0631: if (idx >= 0)
0632: set(idx, t);
0633: else
0634: add(t);
0635: } finally {
0636: leave();
0637: }
0638: }
0639: }
0640:
0641: public List<T> subList(Filter<T> filter) {
0642: synchronized (snapshot) {
0643: try {
0644: enter("subList");
0645: ArrayList<ChunkRef> chunks = new ArrayList<ChunkRef>();
0646: for (TableIterator<T> i = iteratorImpl(filter); i
0647: .hasNext();)
0648: chunks.add(i.nextChunk());
0649: buildIndexIfAdvised();
0650: return new SubList<T>(this , chunks);
0651: } finally {
0652: leave();
0653: }
0654: }
0655: }
0656:
0657: private <A> void addIfIndexable(ArrayList<Function> v,
0658: Function<T, A> f) {
0659: if (isIndexable(f) && !v.contains(f))
0660: v.add(f);
0661: }
0662:
0663: private <A> boolean isIndexable(Function<T, A> f) {
0664: if (f instanceof Field) {
0665: Field field = (Field) f;
0666:
0667: // indexable type?
0668: String t = type.typeDef.contents.get(field.nr()).type;
0669: if (t.equals("long") || t.equals("long long")
0670: || t.equals("boolean") || t.equals("string"))
0671: return true;
0672: } else if (f instanceof Cascade
0673: && ((Cascade) f).g() instanceof ToLowerCase) {
0674: //if (debug) System.out.println("indexable cascade: "+f);
0675: return true;
0676: }
0677: return false;
0678: }
0679:
0680: public Iterator<T> iterator(Filter<T> filter) {
0681: synchronized (snapshot) {
0682: try {
0683: enter("iterator");
0684: return iteratorImpl(filter);
0685: } finally {
0686: leave();
0687: }
0688: }
0689: }
0690:
0691: private TableIterator<T> iteratorImpl(Filter<T> filter) {
0692: // no filter at all => table scan
0693: if (filter == null)
0694: return new TableScan<T>(this , filter);
0695:
0696: // gather some information agbout the filter
0697: IndexProfile profile = QueryOptimizer.createProfile(filter);
0698: boolean ordered = !filter._getOrder().isEmpty();
0699:
0700: // find best fitting index
0701: int bestScore = 0;
0702: Index<T> bestIndex = null;
0703:
0704: for (int i = 0; i < indexes.size(); i++) {
0705: Index<T> idx = indexes.get(i);
0706: int score = QueryOptimizer.indexScore(profile, idx.fields);
0707: if (score > bestScore) {
0708: bestScore = score;
0709: bestIndex = idx;
0710: }
0711: }
0712:
0713: //System.out.println("bestIndex: "+bestIndex);
0714: if (bestIndex == null) {
0715: // No matching index, table scan
0716:
0717: if (ordered) {
0718: // sorted table scan, inform index advisor
0719: if (indexAdvisor != null) {
0720: if (debug)
0721: System.out
0722: .println("Informing index advisor, profile="
0723: + profile
0724: + ", field="
0725: + filter._getOrder().get(0));
0726: indexAdvisor
0727: .queryPerformed(
0728: new Pair<IndexProfile, Function>[] { new Pair<IndexProfile, Function>(
0729: profile, filter._getOrder()
0730: .get(0)) }, size());
0731: buildIndexIfAdvised();
0732: }
0733:
0734: try {
0735: enter("sorted table scan");
0736: if (debug)
0737: System.out.println("sorted table scan over "
0738: + getName() + " (profile=" + profile
0739: + ")");
0740: return new SortedIterator<T>(this ,
0741: new TableScan<T>(this , filter), filter);
0742: } finally {
0743: leave();
0744: }
0745: } else {
0746: try {
0747: enter("simple table scan");
0748: return new TableScan<T>(this , filter);
0749: } finally {
0750: leave();
0751: }
0752: }
0753: }
0754:
0755: // We found a matching index; generate key prefix
0756:
0757: UniversalKey keyPrefix = bestIndex.makeKeyPrefix(filter);
0758: KeySet<UniversalKey> keySet = new PrefixKeySet(keyPrefix);
0759: TableIterator<T> iterator;
0760:
0761: try {
0762: enter("new IndexScan");
0763: iterator = new IndexScan<T>(this , filter, bestIndex, keySet);
0764: } finally {
0765: leave();
0766: }
0767: /*int idx;
0768: if (filter._getOrder().size() == 1 && (idx = indexedFields.indexOf(filter._getOrder().get(0))) >= 0) {
0769: try { enter("sortByIndexField");
0770: iterator = is.sortByIndexField(idx);
0771: } finally { leave(); }
0772: } else*/
0773: if (ordered)
0774: try {
0775: enter("ordered");
0776: iterator = new SortedIterator<T>(this , iterator, filter);
0777: } finally {
0778: leave();
0779: }
0780: return iterator;
0781: }
0782:
0783: public Iterator<T> iterator() {
0784: synchronized (snapshot) {
0785: try {
0786: enter("iterator");
0787: return iterator(null);
0788: } finally {
0789: leave();
0790: }
0791: }
0792: }
0793:
0794: public Iterator<T> iterator(final Filter<T> filter,
0795: final BTree<UniversalKey, ChunkRef> index) {
0796: synchronized (snapshot) {
0797: try {
0798: enter("iterator");
0799: class I implements Iterator<T> {
0800: Iterator<ChunkRef> i;
0801:
0802: I() {
0803: i = index.iterate();
0804: }
0805:
0806: public boolean hasNext() {
0807: return i.hasNext();
0808: }
0809:
0810: public T next() {
0811: return loadElement(i.next());
0812: }
0813:
0814: public void remove() {
0815: throw new RuntimeException("TODO");
0816: }
0817: }
0818: ;
0819: return new I();
0820: } finally {
0821: leave();
0822: }
0823: }
0824: }
0825:
0826: public boolean remove(T t) {
0827: synchronized (snapshot) {
0828: try {
0829: enter("remove");
0830: assertMutable();
0831: int i = indexOf(t);
0832: if (i >= 0) {
0833: remove(i);
0834: return true;
0835: }
0836: return false;
0837: } finally {
0838: leave();
0839: }
0840: }
0841: }
0842:
0843: public T remove(int index) {
0844: synchronized (snapshot) {
0845: try {
0846: enter("remove");
0847: assertMutable();
0848: T t = loadElement(index);
0849: removeFromIndex(t, elements.get(index));
0850: elements.remove(index);
0851: ++modCount;
0852: dirty = true;
0853: return t;
0854: } finally {
0855: leave();
0856: }
0857: }
0858: }
0859:
0860: void removeChunk(int chunk) {
0861: synchronized (snapshot) {
0862: try {
0863: enter("removeChunk");
0864: assertMutable();
0865: if (!elements.removeElement(chunk))
0866: throw new InternalSmyleError("removeChunk: Chunk "
0867: + chunk + " isn't part of table ("
0868: + "size=" + elements.size() + ")");
0869: ++modCount;
0870: dirty = true;
0871: if (!indexes.isEmpty())
0872: removeFromIndex(loadElementChunk(chunk), chunk);
0873: } finally {
0874: leave();
0875: }
0876: }
0877: }
0878:
0879: void collectChunks(BitSet whiteList) {
0880: synchronized (snapshot) {
0881: try {
0882: enter("collectChunks");
0883: whiteList.set(schemaChunk.index);
0884: for (int i = 0; i < elements.size(); i++)
0885: whiteList.set(elements.get(i));
0886: for (int i = 0; i < indexes.size(); i++)
0887: indexes.get(i).collectChunks(whiteList);
0888: //if (debug) System.out.println("Adding "+elements.size()+" elements to whitelist (total now "+whiteList.size()+")");
0889: } finally {
0890: leave();
0891: }
0892: }
0893: }
0894:
0895: void saveSchema() {
0896: if (type == null || type.typeDef == null) {
0897: schemaChunk = ChunkManager.NULLCHUNK;
0898: } else {
0899: Buffer b = new Buffer();
0900: type.writeRecursive(b);
0901: schemaChunk = snapshot.newChunkManager.createChunk(b);
0902: }
0903: dirty = true;
0904: }
0905:
0906: public TypeDef getSchema() {
0907: synchronized (snapshot) {
0908: try {
0909: enter("getSchema");
0910: return type.typeDef;
0911: } finally {
0912: leave();
0913: }
0914: }
0915: }
0916:
0917: public IntVector getUniqueValues(Function<T, Integer> function) {
0918: synchronized (snapshot) {
0919: try {
0920: enter("getUniqueValues");
0921: IntVector v = new IntVector();
0922: for (int i = 0; i < elements.size(); i++) {
0923: int value = function.of(loadElement(i)).intValue();
0924: if (!v.contains(value))
0925: v.add(value);
0926: }
0927: return v;
0928: } finally {
0929: leave();
0930: }
0931: }
0932: }
0933:
0934: public <A> Map<A, Integer> getUniqueValueCounts(
0935: Function<T, A> function) {
0936: return getUniqueValueCounts(function, null);
0937: }
0938:
0939: public <A> Map<A, Integer> getUniqueValueCounts(
0940: Function<T, A> function, Filter<T> filter) {
0941: synchronized (snapshot) {
0942: try {
0943: enter("getUniqueValueCounts");
0944: HashMap<A, Integer> map = new HashMap<A, Integer>();
0945:
0946: for (Iterator<T> i = iterator(filter); i.hasNext();) {
0947: A value = function.of(i.next());
0948: Integer c = map.get(value);
0949: if (c == null)
0950: c = new Integer(1);
0951: else
0952: c = new Integer(c.intValue() + 1);
0953: map.put(value, c);
0954: }
0955: return map;
0956: } finally {
0957: leave();
0958: }
0959: }
0960: }
0961:
0962: public int indexOf(T t) {
0963: synchronized (snapshot) {
0964: try {
0965: enter("indexOf(T)");
0966: return indexOf(elementToFilter(t));
0967: } finally {
0968: leave();
0969: }
0970: }
0971: }
0972:
0973: public int indexOf(T t, int startIndex) {
0974: synchronized (snapshot) {
0975: try {
0976: enter("indexOf(T,int)");
0977: for (int i = startIndex; i < elements.size(); i++) {
0978: if (t.equals(loadElement(i)))
0979: return i;
0980: }
0981: return -1;
0982: } finally {
0983: leave();
0984: }
0985: }
0986: }
0987:
0988: public int lastIndexOf(T t) {
0989: synchronized (snapshot) {
0990: try {
0991: enter("lastIndexOf(T)");
0992: return lastIndexOf(t, elements.size() - 1);
0993: } finally {
0994: leave();
0995: }
0996: }
0997: }
0998:
0999: public int lastIndexOf(T t, int startIndex) {
1000: synchronized (snapshot) {
1001: try {
1002: enter("lastIndexOf(T,int)");
1003: for (int i = startIndex; i >= 0; i--) {
1004: if (t.equals(loadElement(i)))
1005: return i;
1006: }
1007: return -1;
1008: } finally {
1009: leave();
1010: }
1011: }
1012: }
1013:
1014: public T set(int index, T t) {
1015: synchronized (snapshot) {
1016: try {
1017: enter("set(int,T)");
1018: assertMutable();
1019: T old = loadElement(index);
1020: removeFromIndex(old, elements.get(index));
1021: saveElement(t, index);
1022: return old;
1023: } finally {
1024: leave();
1025: }
1026: }
1027: }
1028:
1029: // TODO: test all following methods
1030:
1031: public Object[] toArray(Object[] array) {
1032: synchronized (snapshot) {
1033: try {
1034: enter("toArray");
1035: for (int i = 0; i < elements.size(); i++)
1036: array[i] = loadElement(i);
1037: for (int i = elements.size(); i < array.length; i++)
1038: array[i] = null;
1039: return array;
1040: } finally {
1041: leave();
1042: }
1043: }
1044: }
1045:
1046: public Object[] toArray() {
1047: synchronized (snapshot) {
1048: try {
1049: enter("toArray");
1050: Object[] array = new Object[size()];
1051: for (int i = 0; i < elements.size(); i++)
1052: array[i] = loadElement(i);
1053: return array;
1054: } finally {
1055: leave();
1056: }
1057: }
1058: }
1059:
1060: public boolean containsAll(Collection<T> c) {
1061: synchronized (snapshot) {
1062: try {
1063: enter("containsAll");
1064: for (Iterator<T> i = c.iterator(); i.hasNext();)
1065: if (!contains(i.next()))
1066: return false;
1067: return true;
1068: } finally {
1069: leave();
1070: }
1071: }
1072: }
1073:
1074: public boolean removeAll(Collection<T> c) {
1075: synchronized (snapshot) {
1076: try {
1077: enter("removeAll(Collection)");
1078: assertMutable();
1079: boolean changed = false;
1080: for (int i = 0; i < elements.size(); i++) {
1081: if (c.contains(loadElement(i))) {
1082: remove(i--);
1083: changed = true;
1084: }
1085: }
1086: return changed;
1087: } finally {
1088: leave();
1089: }
1090: }
1091: }
1092:
1093: public boolean retainAll(Collection<T> c) {
1094: synchronized (snapshot) {
1095: try {
1096: enter("retainAll");
1097: assertMutable();
1098: boolean changed = false;
1099: for (int i = 0; i < elements.size(); i++) {
1100: if (!c.contains(loadElement(i))) {
1101: remove(i--);
1102: changed = true;
1103: }
1104: }
1105: return changed;
1106: } finally {
1107: leave();
1108: }
1109: }
1110: }
1111:
1112: /*public void removeRange(int startIndex, int endIndex) { synchronized(snapshot) {
1113: assertMutable();
1114: ++modCount;
1115: elements.removeRange(startIndex, endIndex);
1116: }}*/
1117:
1118: public ListIterator<T> listIterator() {
1119: synchronized (snapshot) {
1120: try {
1121: enter("listIterator");
1122: throw new RuntimeException("TODO");
1123: } finally {
1124: leave();
1125: }
1126: }
1127: }
1128:
1129: public ListIterator<T> listIterator(int index) {
1130: synchronized (snapshot) {
1131: try {
1132: enter("listIterator");
1133: throw new RuntimeException("TODO");
1134: } finally {
1135: leave();
1136: }
1137: }
1138: }
1139:
1140: public List<T> subList(int startIndex, int endIndex) {
1141: synchronized (snapshot) {
1142: try {
1143: enter("subList");
1144: throw new RuntimeException("TODO");
1145: } finally {
1146: leave();
1147: }
1148: }
1149: }
1150:
1151: private void addToIndex(T t, ChunkRef chunk) {
1152: for (int i = 0; i < indexes.size(); i++)
1153: indexes.get(i).add(t, chunk);
1154: }
1155:
1156: private void removeFromIndex(T t, int chunk) {
1157: for (int i = 0; i < indexes.size(); i++)
1158: indexes.get(i).remove(t, new ChunkRef(chunk));
1159: }
1160:
1161: public IndexAdvisor<Pair<IndexProfile, Function>> getIndexAdvisor() {
1162: synchronized (snapshot) {
1163: try {
1164: enter("getIndexAdvisor");
1165: return indexAdvisor;
1166: } finally {
1167: leave();
1168: }
1169: }
1170: }
1171:
1172: public int numIndexes() {
1173: return indexes.size();
1174: }
1175:
1176: public Index<T> getIndex(int i) {
1177: return indexes.get(i);
1178: }
1179:
1180: boolean matches(Filter<T> filter, T t) {
1181: synchronized (snapshot) {
1182: try {
1183: enter("matches");
1184: if (filter.matches(t))
1185: return true;
1186: else {
1187: if (indexAdvisor != null) {
1188: IndexProfile profile = null;
1189: for (int i = 0; i < filter._numClauses(); i++) {
1190: Filter<T>.Clause clause = filter
1191: ._getClause(i);
1192: if (clause.matches(t))
1193: // If clause matches, it wouldn't help to index it
1194: // (since the whole filter doesn't match)
1195: continue;
1196:
1197: if (isIndexable(clause.getFunction())) {
1198: if (profile == null) // TODO: cache profile
1199: profile = QueryOptimizer
1200: .createProfile(filter);
1201: indexAdvisor
1202: .queryPerformed(
1203: new Pair<IndexProfile, Function>[] { new Pair<IndexProfile, Function>(
1204: profile,
1205: clause
1206: .getFunction()) },
1207: 1);
1208: }
1209: }
1210: }
1211: return false;
1212: }
1213: } finally {
1214: leave();
1215: }
1216: }
1217: }
1218:
1219: void buildIndexIfAdvised() {
1220: if (indexAdvisor == null || !snapshot.mutable || !typed())
1221: return;
1222: Pair<IndexProfile, Function> pair = indexAdvisor.fieldToIndex();
1223: if (pair == null)
1224: return;
1225: IndexProfile profile = pair.a();
1226: Function f = pair.b();
1227:
1228: if (debug)
1229: System.out.println("field to index: " + profile + " " + f
1230: + " (advisor: " + indexAdvisor + ")");
1231:
1232: int bestScore1 = 0, bestScore2 = 0;
1233: Index<T> bestIndex = null;
1234:
1235: for (int i = 0; i < indexes.size(); i++) {
1236: Index<T> idx = indexes.get(i);
1237: if (idx.fields.contains(f))
1238: continue;
1239: int score1 = QueryOptimizer.indexScore(profile, idx.fields);
1240: ArrayList<Function> fieldsPlusF = new ArrayList<Function>(
1241: idx.fields);
1242: fieldsPlusF.add(f);
1243: int score2 = QueryOptimizer
1244: .indexScore(profile, fieldsPlusF);
1245: if (debug)
1246: System.out.println("score1=" + score1 + ", score2="
1247: + score2);
1248: if (score2 > bestScore2) {
1249: bestScore2 = score2;
1250: bestScore1 = score1;
1251: bestIndex = idx;
1252: }
1253: }
1254:
1255: ArrayList<Function> newFields;
1256:
1257: if (bestIndex != null) {
1258: if (bestScore2 == bestScore1)
1259: return; // no improvement possible
1260: newFields = new ArrayList<Function>(bestIndex.fields);
1261: } else {
1262: newFields = new ArrayList<Function>();
1263: }
1264:
1265: newFields.add(f);
1266: if (alreadyIndexed(newFields))
1267: return;
1268:
1269: long startTime = System.currentTimeMillis();
1270: if (bestIndex == null)
1271: indexes.add(new Index(this , newFields));
1272: else
1273: bestIndex.addField(f);
1274: long endTime = System.currentTimeMillis();
1275: log("Indexed " + profile + " " + f + " (elements: "
1276: + elements.size() + "), number of indexes now: "
1277: + indexes.size() + "; " + (endTime - startTime) + " ms");
1278: }
1279:
1280: public void addIndex(ArrayList<Function> fields) {
1281: indexes.add(new Index(this , fields));
1282: }
1283:
1284: private boolean alreadyIndexed(ArrayList<Function> fields) {
1285: for (int i = 0; i < indexes.size(); i++)
1286: if (startsWith(indexes.get(i).fields, fields))
1287: return true;
1288: return false;
1289: }
1290:
1291: private static boolean startsWith(List<Function> a, List<Function> b) {
1292: if (a.size() < b.size())
1293: return false;
1294: for (int i = 0; i < b.size(); i++)
1295: if (!a.get(i).equals(b.get(i)))
1296: return false;
1297: return true;
1298: }
1299:
1300: public void setAutoIncrementField(Field<T, Integer> field) {
1301: synchronized (snapshot) {
1302: try {
1303: enter("setAutoIncrementField");
1304: if (autoincField != field) {
1305: autoincField = field;
1306:
1307: // set counter to max value
1308:
1309: Filter<T> filter = new Filter<T>();
1310: filter._orderBy(field);
1311: filter._setReverse(true);
1312: Iterator<T> it = iterator(filter);
1313: if (it.hasNext())
1314: autoincCounter = Math.max(0, field
1315: .of(it.next()).intValue());
1316: else
1317: autoincCounter = 0;
1318:
1319: // assign an id to all records with field value 0
1320:
1321: for (int i = 0; i < size(); i++) {
1322: T t = get(i);
1323: if (field.of(t).intValue() == 0) {
1324: field.set(t, new Integer(++autoincCounter));
1325: set(i, t);
1326: }
1327: }
1328: }
1329: } finally {
1330: leave();
1331: }
1332: }
1333: }
1334:
1335: public boolean typed() {
1336: synchronized (snapshot) {
1337: try {
1338: enter("typed");
1339: return demarshaller != null;
1340: } finally {
1341: leave();
1342: }
1343: }
1344: }
1345:
1346: protected StructInfo<T> loadType() {
1347: if (schemaChunk.index != 0) {
1348: Buffer b = chunkManager.readChunk(schemaChunk);
1349: return snapshot.store.version < 292 ? new StructInfo(b)
1350: : StructInfo.readRecursive(b);
1351: } else
1352: return null;
1353: }
1354:
1355: ChunkRef getElementChunkRef(int index) {
1356: synchronized (snapshot) {
1357: try {
1358: enter("getElementChunkRef");
1359: return new ChunkRef(elements.get(index));
1360: } finally {
1361: leave();
1362: }
1363: }
1364: }
1365:
1366: private Filter<T> elementToFilter(T t) {
1367: DynFilter<T> filter = new DynFilter<T>();
1368: for (int i = 0; i < type.typeDef.contents.size(); i++) {
1369: TypeComponent tc = type.typeDef.contents.get(i);
1370: Field f = fmd.getField(i);
1371: filter.functionEquals(f, f.of(t));
1372: }
1373: return filter;
1374: }
1375:
1376: /** only call this before an index is created! */
1377: public void setMaxKeyLength(int l) {
1378: maxKeyLength = l;
1379: maxKey = UniversalKey.max(l);
1380: }
1381:
1382: private void log(String msg) {
1383: snapshot.store.log(msg);
1384: }
1385:
1386: public Object[] untypedElementAt(int i) {
1387: synchronized (snapshot) {
1388: try {
1389: enter("untypedElementAt");
1390: StructInfo<Record> info = new StructInfo<Record>(
1391: type.typeDef, null, Record.class, null);
1392: int chunk = elements.get(i);
1393: return constructCustomDemarshaller(
1394: type,
1395: info,
1396: new HashMap<Pair<StructInfo, StructInfo>, FieldBasedDemarshaller>())
1397: .read(chunkManager.readChunk(chunk)).getArray();
1398: } finally {
1399: leave();
1400: }
1401: }
1402: }
1403:
1404: private void enter(String function) {
1405: if (profiling) {
1406: if (snapshot.recCount++ == 0) {
1407: snapshot.workingSince = System.currentTimeMillis();
1408: snapshot.currentThread = Thread.currentThread();
1409: snapshot.currentFunctions = new String[20];
1410: }
1411: snapshot.currentFunctions[snapshot.recCount - 1] = function;
1412: }
1413: }
1414:
1415: private void leave() {
1416: if (profiling) {
1417: snapshot.currentFunctions[snapshot.recCount - 1] = null;
1418: if (--snapshot.recCount == 0) {
1419: snapshot.currentThread = null;
1420: snapshot.currentFunctions = null;
1421: }
1422: }
1423: }
1424:
1425: public void clearIndexes() {
1426: for (int i = 0; i < indexes.size(); i++)
1427: indexes.get(i).clear();
1428: }
1429:
1430: public String getName() {
1431: return snapshot.tableNames.get(id);
1432: }
1433: }
|