001: /**
002: * com.mckoi.database.MasterTableJournal 19 Nov 2000
003: *
004: * Mckoi SQL Database ( http://www.mckoi.com/database )
005: * Copyright (C) 2000, 2001, 2002 Diehl and Associates, Inc.
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License
009: * Version 2 as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
014: * GNU General Public License Version 2 for more details.
015: *
016: * You should have received a copy of the GNU General Public License
017: * Version 2 along with this program; if not, write to the Free Software
018: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
019: *
020: * Change Log:
021: *
022: *
023: */package com.mckoi.database;
024:
025: import com.mckoi.util.IntegerVector;
026: import java.io.*;
027:
028: /**
029: * A journal of changes that occured to a table in a data conglomerate during
030: * a transaction.
031: *
032: * @author Tobias Downer
033: */
034:
035: final class MasterTableJournal {
036:
037: /**
038: * Journal commands.
039: */
040: final static byte TABLE_ADD = 1; // Add a row to a table.
041: // (params: table_id, row_index)
042: final static byte TABLE_REMOVE = 2; // Remove a row from a table.
043: // (params: table_id, row_index)
044: final static byte TABLE_UPDATE_ADD = 5; // Add a row from an update.
045: final static byte TABLE_UPDATE_REMOVE = 6; // Remove a row from an update.
046:
047: /**
048: * The commit id given to this change when it is committed. This is only
049: * set when the journal is a committed change to the database.
050: */
051: private long commit_id;
052:
053: /**
054: * The master table id.
055: */
056: private int table_id;
057:
058: /**
059: * The number of entries in this journal.
060: */
061: private int journal_entries;
062:
063: /**
064: * A byte[] array that represents the set of commands a transaction
065: * performed on this table.
066: */
067: private byte[] command_journal;
068:
069: /**
070: * An IntegerVector that is filled with parameters from the command journal.
071: * For example, a 'TABLE_ADD' journal log will have as parameters the
072: * row_index that was added to this table.
073: */
074: private IntegerVector command_parameters;
075:
076: /**
077: * Constructs the master table journal.
078: */
079: MasterTableJournal(int table_id) {
080: this .table_id = table_id;
081: command_journal = new byte[16];
082: command_parameters = new IntegerVector(32);
083: }
084:
085: MasterTableJournal() {
086: this (-1);
087: }
088:
089: /**
090: * Sets the 'commit_id'. This is only set when this change becomes a
091: * committed change to the database.
092: */
093: void setCommitID(long commit_id) {
094: this .commit_id = commit_id;
095: }
096:
097: /**
098: * Returns true if the given command is an addition command.
099: */
100: static boolean isAddCommand(byte command) {
101: return ((command & 0x03) == TABLE_ADD);
102: }
103:
104: /**
105: * Returns true if the given command is a removal command.
106: */
107: static boolean isRemoveCommand(byte command) {
108: return ((command & 0x03) == TABLE_REMOVE);
109: }
110:
111: /**
112: * Adds a command to the journal.
113: */
114: private void addCommand(byte command) {
115: if (journal_entries >= command_journal.length) {
116: // Resize command array.
117: int grow_size = Math.min(4000, journal_entries);
118: grow_size = Math.max(4, grow_size);
119: byte[] new_command_journal = new byte[journal_entries
120: + grow_size];
121: System.arraycopy(command_journal, 0, new_command_journal,
122: 0, journal_entries);
123: command_journal = new_command_journal;
124: }
125:
126: command_journal[journal_entries] = command;
127: ++journal_entries;
128: }
129:
130: /**
131: * Adds a parameter to the journal command parameters.
132: */
133: private void addParameter(int param) {
134: command_parameters.addInt(param);
135: }
136:
137: /**
138: * Removes the top n entries from the journal.
139: */
140: private void removeTopEntries(int n) {
141: journal_entries = journal_entries - n;
142: command_parameters.crop(0, command_parameters.size() - n);
143: }
144:
145: /**
146: * Adds a new command to this journal.
147: */
148: void addEntry(byte command, int row_index) {
149: addCommand(command);
150: addParameter(row_index);
151: }
152:
153: // ---------- Getters ----------
154: // These methods assume the journal has been setup and no more entries
155: // will be made.
156:
157: /**
158: * Returns the commit_id that has been set for this journal.
159: */
160: long getCommitID() {
161: return commit_id;
162: }
163:
164: /**
165: * Returns the table id of the master table this journal is for.
166: */
167: int getTableID() {
168: return table_id;
169: }
170:
171: /**
172: * Returns the total number of journal entries.
173: */
174: int entries() {
175: return journal_entries;
176: }
177:
178: /**
179: * Returns the command of the nth entry in the journal.
180: */
181: byte getCommand(int n) {
182: return command_journal[n];
183: }
184:
185: /**
186: * Returns the row index of the nth entry in the journal.
187: */
188: int getRowIndex(int n) {
189: return command_parameters.intAt(n);
190: }
191:
192: /**
193: * Returns a normalized list of all rows that were added in this journal,
194: * but not including those rows also removed. For example, if rows
195: * 1, 2, and 3 were added and 2 was removed, this will return a list of
196: * 1 and 3.
197: */
198: int[] normalizedAddedRows() {
199: IntegerVector list = new IntegerVector();
200: int size = entries();
201: for (int i = 0; i < size; ++i) {
202: byte tc = getCommand(i);
203: if (tc == TABLE_ADD || tc == TABLE_UPDATE_ADD) {
204: int row_index = getRowIndex(i);
205: // If row added, add to list
206: list.addInt(row_index);
207: } else if (tc == TABLE_REMOVE || tc == TABLE_UPDATE_REMOVE) {
208: // If row removed, if the row is already in the list
209: // it's removed from the list, otherwise we leave as is.
210: int row_index = getRowIndex(i);
211: int found_at = list.indexOf(row_index);
212: if (found_at != -1) {
213: list.removeIntAt(found_at);
214: }
215: } else {
216: throw new Error("Unknown command in journal.");
217: }
218: }
219:
220: return list.toIntArray();
221: }
222:
223: /**
224: * Returns a normalized list of all rows that were removed from this
225: * journal.
226: */
227: int[] normalizedRemovedRows() {
228: IntegerVector list = new IntegerVector();
229: int size = entries();
230: for (int i = 0; i < size; ++i) {
231: byte tc = getCommand(i);
232: if (tc == TABLE_REMOVE || tc == TABLE_UPDATE_REMOVE) {
233: // If removed add to the list.
234: int row_index = getRowIndex(i);
235: list.addInt(row_index);
236: }
237: }
238: return list.toIntArray();
239: }
240:
241: /**
242: * Returns three lists - a list of all rows that were inserted, a list of all
243: * rows that were deleted, and a list of all updates. All the lists are
244: * ordered by the order of the command. The update list contains two
245: * entries per 'update', the row that was removed and the row that was
246: * added with the updated info.
247: * <p>
248: * This method is useful for collecting all modification information on the
249: * table.
250: */
251: IntegerVector[] allChangeInformation() {
252: IntegerVector[] lists = new IntegerVector[3];
253: for (int i = 0; i < 3; ++i) {
254: lists[i] = new IntegerVector();
255: }
256: int size = entries();
257: for (int i = 0; i < size; ++i) {
258: byte tc = getCommand(i);
259: int row_index = getRowIndex(i);
260: if (tc == TABLE_ADD) {
261: lists[0].addInt(row_index);
262: } else if (tc == TABLE_REMOVE) {
263: lists[1].addInt(row_index);
264: } else if (tc == TABLE_UPDATE_ADD
265: || tc == TABLE_UPDATE_REMOVE) {
266: lists[2].addInt(row_index);
267: } else {
268: throw new RuntimeException(
269: "Don't understand journal command.");
270: }
271: }
272: return lists;
273: }
274:
275: /**
276: * Rolls back the last n entries of this journal. This method takes into
277: * account the transient nature of rows (all added rows in the journal are
278: * exclusively referenced by this journal). The algorithm works as follows;
279: * any rows added are deleted, and rows deleted (that weren't added) are
280: * removed from the journal.
281: */
282: void rollbackEntries(int n) {
283: if (n > journal_entries) {
284: throw new RuntimeException(
285: "Trying to roll back more journal entries than are in the journal.");
286: }
287:
288: IntegerVector to_add = new IntegerVector();
289:
290: // Find all entries and added new rows to the table
291: int size = entries();
292: for (int i = size - n; i < size; ++i) {
293: byte tc = getCommand(i);
294: if (tc == TABLE_ADD || tc == TABLE_UPDATE_ADD) {
295: to_add.addInt(getRowIndex(i));
296: }
297: }
298:
299: // Delete the top entries
300: removeTopEntries(n);
301: // Mark all added entries to deleted.
302: for (int i = 0; i < to_add.size(); ++i) {
303: addEntry(TABLE_ADD, to_add.intAt(i));
304: addEntry(TABLE_REMOVE, to_add.intAt(i));
305: }
306:
307: }
308:
309: // ---------- Testing methods ----------
310:
311: /**
312: * Throws a transaction clash exception if it detects a clash between
313: * journal entries. It assumes that this journal is the journal that is
314: * attempting to be compatible with the given journal. A journal clashes
315: * when they both contain a row that is deleted.
316: */
317: void testCommitClash(DataTableDef table_def,
318: MasterTableJournal journal) throws TransactionException {
319: // Very nasty search here...
320: // int cost = entries() * journal.entries();
321: // System.out.print(" CLASH COST = " + cost + " ");
322:
323: for (int i = 0; i < entries(); ++i) {
324: byte tc = getCommand(i);
325: if (isRemoveCommand(tc)) { // command - row remove
326: int row_index = getRowIndex(i);
327: // System.out.println("* " + row_index);
328: for (int n = 0; n < journal.entries(); ++n) {
329: // System.out.print(" " + journal.getRowIndex(n));
330: if (isRemoveCommand(journal.getCommand(n))
331: && journal.getRowIndex(n) == row_index) {
332: throw new TransactionException(
333: TransactionException.ROW_REMOVE_CLASH,
334: "Concurrent Serializable Transaction Conflict(1): "
335: + "Current row remove clash ( row: "
336: + row_index + ", table: "
337: + table_def.getTableName()
338: + " )");
339: }
340: }
341: // System.out.println();
342: }
343: }
344: }
345:
346: // ---------- Stream serialization methods ----------
347:
348: /**
349: * Reads the journal entries from the given DataInputStream to this object.
350: * <p>
351: * This method is only around because we might need it to convert a
352: * 0.91 era database that stored index data as journals in the file system.
353: */
354: void readFrom(DataInputStream din) throws IOException {
355: commit_id = din.readInt();
356: table_id = din.readInt();
357:
358: journal_entries = din.readInt();
359: command_journal = new byte[journal_entries];
360: din.readFully(command_journal, 0, journal_entries);
361: int size = din.readInt();
362: for (int i = 0; i < size; ++i) {
363: command_parameters.addInt(din.readInt());
364: }
365: }
366:
367: /**
368: * Debugging.
369: */
370: public String toString() {
371: StringBuffer buf = new StringBuffer();
372: buf.append("[MasterTableJournal] [");
373: buf.append(commit_id);
374: buf.append("] (");
375: for (int i = 0; i < entries(); ++i) {
376: byte c = getCommand(i);
377: int row_index = getRowIndex(i);
378: buf.append("(");
379: buf.append(c);
380: buf.append(")");
381: buf.append(row_index);
382: buf.append(" ");
383: }
384: buf.append(")");
385: return new String(buf);
386: }
387:
388: }
|