25 src/main/java/org/basex/index/path/PathNode.java
View file
@@ -17,7 +17,6 @@
*
* @author BaseX Team 2005-12, BSD License
* @author Christian Gruen
* @author Andreas Weiler
*/
public final class PathNode {
/** Tag/attribute name id. */
@@ -29,7 +28,14 @@ public final class PathNode {
/** Children. */
public PathNode[] ch;
/** Node kind. */
public Stats stats;
public final Stats stats;

/**
* Empty constructor.
*/
PathNode() {
this(0, Data.DOC, null, 0);
}

/**
* Default constructor.
@@ -38,12 +44,23 @@ public final class PathNode {
* @param p parent node
*/
PathNode(final int n, final byte k, final PathNode p) {
this(n, k, p, 1);
}

/**
* Default constructor.
* @param n node name
* @param k node kind
* @param p parent node
* @param c counter
*/
PathNode(final int n, final byte k, final PathNode p, final int c) {
ch = new PathNode[0];
name = (short) n;
kind = k;
par = p;
stats = new Stats();
stats.count = 1;
stats.count = c;
}

/**
@@ -171,7 +188,7 @@ public int level() {
}

/**
* Prints a path summary node.
* Returns a string representation of a path summary node.
* @param data data reference
* @param l level
* @return string representation
22 src/main/java/org/basex/index/path/PathSummary.java
View file
@@ -34,6 +34,7 @@ public final class PathSummary implements Index {
*/
public PathSummary(final Data d) {
data = d;
init();
}

/**
@@ -43,7 +44,7 @@ public PathSummary(final Data d) {
* @throws IOException I/O exception
*/
public PathSummary(final Data d, final DataInput in) throws IOException {
if(in.readBool()) root = new PathNode(in, null);
root = in.readBool() ? new PathNode(in, null) : new PathNode();
data = d;
}

@@ -66,15 +67,20 @@ public void finish(final Data d) {
}

@Override
public void close() {
root = null;
public void init() {
root = new PathNode();
stack.clear();
stack.add(root);
}

@Override
public void close() { }

// Build Index ==============================================================

/**
* Adds an entry.
* @param n name reference
* @param n name reference (0 for nodes other than element and attributes)
* @param k node kind
* @param l current level
*/
@@ -84,7 +90,7 @@ public void index(final int n, final byte k, final int l) {

/**
* Adds an entry, including its value.
* @param n name reference
* @param n name reference (0 for nodes other than element and attributes)
* @param k node kind
* @param l current level
* @param v value
@@ -93,11 +99,7 @@ public void index(final int n, final byte k, final int l) {
public void index(final int n, final byte k, final int l, final byte[] v,
final MetaData md) {

if(root == null) {
root = new PathNode(n, k, null);
stack.clear();
stack.add(root);
} else if(l == 0) {
if(l == 0) {
if(v != null) root.stats.add(v, md);
root.stats.count++;
} else {
1 src/main/java/org/basex/index/resource/Docs.java
View file
@@ -75,7 +75,6 @@ synchronized void init() {

/**
* Returns the {@code pre} values of all document nodes.
* A single dummy node is returned if the database is empty.
* @return document nodes
*/
synchronized IntList docs() {
5 src/main/java/org/basex/index/resource/Resources.java
View file
@@ -52,16 +52,13 @@ public void write(final DataOutput out) throws IOException {

/**
* Returns the {@code pre} values of all document nodes.
* A single dummy node is returned if the database is empty.
* @return document nodes
*/
public synchronized IntList docs() {
return docs.docs();
}

/**
* Initializes the index.
*/
@Override
public synchronized void init() {
docs.init();
}
3 src/main/java/org/basex/index/value/DiskValues.java
View file
@@ -64,6 +64,9 @@ protected DiskValues(final Data d, final boolean txt, final String pref)
size = idxl.read4();
}

@Override
public synchronized void init() { }

@Override
public synchronized byte[] info() {
final TokenBuilder tb = new TokenBuilder();
3 src/main/java/org/basex/index/value/MemValues.java
View file
@@ -35,6 +35,9 @@ public MemValues(final Data d) {
data = d;
}

@Override
public synchronized void init() { }

@Override
public IndexIterator iter(final IndexToken tok) {
final byte k = tok.type() == IndexType.TEXT ? Data.TEXT : Data.ATTR;
8 src/main/java/org/basex/io/IO.java
View file
@@ -60,13 +60,13 @@ public abstract class IO {
public static final String[] TXTSUFFIXES = {
".txt", ".text", ".ini", ".conf" };

/** Disk block/page size (default: 4096). */
/** Disk block/page size (4096). */
public static final int BLOCKSIZE = 1 << 12;
/** Table node size power (default: 4). */
/** Table node size power (4). */
public static final int NODEPOWER = 4;
/** Table node size power (default: 4). */
/** Table node size power (16). */
public static final int NODESIZE = 1 << NODEPOWER;
/** Entries per block (default: 256). */
/** Entries per block (256). */
public static final int ENTRIES = BLOCKSIZE >>> NODEPOWER;

/** Maximum number of attributes (see bit layout in {@link Data} class). */
25 src/main/java/org/basex/io/out/TableOutput.java
View file
@@ -17,9 +17,9 @@ public final class TableOutput extends OutputStream {
/** Buffer. */
private final byte[] buffer = new byte[IO.BLOCKSIZE];
/** Index entries. */
private final IntList firstPres = new IntList();
private final IntList fpres = new IntList();
/** Index entries. */
private final IntList blocks = new IntList();
private final IntList pages = new IntList();

/** The underlying output stream. */
private final OutputStream os;
@@ -30,8 +30,6 @@ public final class TableOutput extends OutputStream {

/** Position inside buffer. */
private int pos;
/** Block count. */
private int bcount;
/** First pre value of current block. */
private int fpre;

@@ -58,26 +56,27 @@ public void write(final int b) throws IOException {
public void flush() throws IOException {
if(pos == 0) return;
os.write(buffer);
firstPres.add(fpre);
blocks.add(bcount++);
fpres.add(fpre);
pages.add(pages.size());
fpre += pos >>> IO.NODEPOWER;
pos = 0;
}

@Override
public void close() throws IOException {
final boolean empty = fpre + pos == 0;
if(empty) pos++;
flush();
os.close();

DataOutput dt = null;
final DataOutput out = new DataOutput(meta.dbfile(file + 'i'));
try {
dt = new DataOutput(meta.dbfile(file + 'i'));
dt.writeNum(bcount);
dt.writeNum(bcount);
dt.writeNums(firstPres.toArray());
dt.writeNums(blocks.toArray());
out.writeNum(pages.size());
out.writeNum(empty ? 0 : pages.size());
out.writeNums(fpres.toArray());
out.writeNums(pages.toArray());
} finally {
if(dt != null) try { dt.close(); } catch(final IOException ex) { }
out.close();
}
}
}
7 src/main/java/org/basex/io/random/TableAccess.java
View file
@@ -115,9 +115,7 @@ public abstract class TableAccess {
* @param entries new entries
* @param sub size of the subtree that is replaced
*/
public final void replace(final int pre, final byte[] entries,
final int sub) {

public final void replace(final int pre, final byte[] entries, final int sub) {
dirty = true;
final int nsize = entries.length >>> IO.NODEPOWER;
final int diff = sub - nsize;
@@ -153,8 +151,7 @@ public final void set(final int pre, final byte[] entries) {
* @param pre first target pre value
* @param last last pre value
*/
protected abstract void copy(final byte[] entries, final int pre,
final int last);
protected abstract void copy(final byte[] entries, final int pre, final int last);

/**
* Deletes the specified number of entries from the database.
159 src/main/java/org/basex/io/random/TableDiskAccess.java
View file
@@ -28,9 +28,9 @@ public final class TableDiskAccess extends TableAccess {
/** File lock. */
private FileLock fl;

/** FirstPre values (sorted ascending; length={@link #allBlocks}). */
/** FirstPre values (sorted ascending; length: {@link #blocks}). */
private int[] fpres;
/** Index array storing BlockNumbers (length={@link #allBlocks}). */
/** Page index (length: {@link #blocks}). */
private int[] pages;
/** Bitmap storing free (=0) and occupied (=1) pages. */
private final BitArray pagemap;
@@ -40,10 +40,10 @@ public final class TableDiskAccess extends TableAccess {
/** First pre value of the next block. */
private int npre = -1;

/** Number of blocks in the data file (including unused). */
private int allBlocks;
/** Number of entries in the index (used blocks). */
/** Total number of blocks. */
private int blocks;
/** Number of used blocks. */
private int used;
/** Index of the current block number in the {@link #pages} array. */
private int index = -1;

@@ -58,20 +58,20 @@ public TableDiskAccess(final MetaData md, final boolean lock) throws IOException

// read meta and index data
final DataInput in = new DataInput(meta.dbfile(DATATBL + 'i'));
allBlocks = in.readNum();
blocks = in.readNum();
fpres = in.readNums();
pages = in.readNums();
blocks = in.readNum();
used = in.readNum();
fpres = in.readNums();
pages = in.readNums();

final int psize = in.readNum();
// check if the page map has been stored
if(psize == 0) {
// init the map with empty pages
pagemap = new BitArray(allBlocks);
pagemap = new BitArray(blocks);
for(final int p : pages) pagemap.set(p);
dirty = true;
} else {
pagemap = new BitArray(in.readLongs(psize), allBlocks);
pagemap = new BitArray(in.readLongs(psize), blocks);
}
in.close();

@@ -80,8 +80,6 @@ public TableDiskAccess(final MetaData md, final boolean lock) throws IOException
if(lock) exclusiveLock();
else sharedLock();
if(fl == null) throw new BaseXException(Text.DB_PINNED_X, md.name);

readIndex(0);
}

/**
@@ -115,15 +113,16 @@ public static boolean locked(final String db, final Context ctx) {
public synchronized void flush() throws IOException {
for(final Buffer b : bm.all()) if(b.dirty) writeBlock(b);
if(!dirty) return;

final DataOutput out = new DataOutput(meta.dbfile(DATATBL + 'i'));
out.writeNum(allBlocks);
out.writeNum(blocks);
out.writeNum(used);

// due to legacy issues, allBlocks is written several times
out.writeNum(allBlocks);
for(int a = 0; a < allBlocks; a++) out.writeNum(fpres[a]);
out.writeNum(allBlocks);
for(int a = 0; a < allBlocks; a++) out.writeNum(pages[a]);
// due to legacy issues, number of blocks is written several times
out.writeNum(blocks);
for(int a = 0; a < blocks; a++) out.writeNum(fpres[a]);
out.writeNum(blocks);
for(int a = 0; a < blocks; a++) out.writeNum(pages[a]);

out.writeLongs(pagemap.toArray());
out.close();
@@ -291,10 +290,10 @@ public void delete(final int pre, final int nr) {
// mark the block as empty
pagemap.clear(pages[index]);

Array.move(fpres, index + 1, -1, blocks - index - 1);
Array.move(pages, index + 1, -1, blocks - index - 1);
Array.move(fpres, index + 1, -1, used - index - 1);
Array.move(pages, index + 1, -1, used - index - 1);

--blocks;
--used;
readIndex(index);
}
return;
@@ -321,7 +320,7 @@ public void delete(final int pre, final int nr) {
if(npre == last) {
pagemap.clear((int) bf.pos);
++unused;
if(index < blocks - 1) readIndex(index + 1);
if(index < used - 1) readIndex(index + 1);
else ++index;
} else {
// delete entries at beginning of current (last) block
@@ -330,9 +329,9 @@ public void delete(final int pre, final int nr) {

// now remove them from the index
if(unused > 0) {
Array.move(fpres, index, -unused, blocks - index);
Array.move(pages, index, -unused, blocks - index);
blocks -= unused;
Array.move(fpres, index, -unused, used - index);
Array.move(pages, index, -unused, used - index);
used -= unused;
index -= unused;
}

@@ -344,15 +343,23 @@ public void delete(final int pre, final int nr) {

@Override
public void insert(final int pre, final byte[] entries) {
if(entries.length == 0) return;
final int nnew = entries.length;
if(nnew == 0) return;
dirty = true;

// number of records to be inserted
final int nr = nnew >>> IO.NODEPOWER;

// go to the block and find the offset within the block where the new
// records will be inserted
final int split = cursor(pre - 1) + IO.NODESIZE;

// number of records to be inserted
final int nr = entries.length >>> IO.NODEPOWER;
final int split;
if(pre == 0) {
readIndex(0);
used++;
split = 0;
} else {
split = cursor(pre - 1) + IO.NODESIZE;
}

// number of bytes occupied by old records in the current block
final int nold = npre - fpre << IO.NODEPOWER;
@@ -361,13 +368,13 @@ public void insert(final int pre, final byte[] entries) {

// special case: all entries fit in the current block
Buffer bf = bm.current();
if(nold + entries.length <= IO.BLOCKSIZE) {
System.arraycopy(bf.data, split, bf.data, split + entries.length, moved);
System.arraycopy(entries, 0, bf.data, split, entries.length);
if(nold + nnew <= IO.BLOCKSIZE) {
Array.move(bf.data, split, nnew, moved);
System.arraycopy(entries, 0, bf.data, split, nnew);
bf.dirty = true;

// increment first pre-values of blocks after the last modified block
for(int i = index + 1; i < blocks; ++i) fpres[i] += nr;
for(int i = index + 1; i < used; ++i) fpres[i] += nr;
// update cached variables (fpre is not changed)
npre += nr;
meta.size += nr;
@@ -376,25 +383,26 @@ public void insert(final int pre, final byte[] entries) {

// append old entries at the end of the new entries
// [DP] Storage: the following can be optimized to avoid copying arrays
final byte[] all = new byte[entries.length + moved];
System.arraycopy(entries, 0, all, 0, entries.length);
System.arraycopy(bf.data, split, all, entries.length, moved);
final byte[] all = new byte[nnew + moved];
System.arraycopy(entries, 0, all, 0, nnew);
System.arraycopy(bf.data, split, all, nnew, moved);

// fill in the current block with new entries
// number of bytes which can fit in the first block
int n = bf.data.length - split;
if(n > 0) {
System.arraycopy(all, 0, bf.data, split, n);
// number of bytes which fit in the first block
int nrem = IO.BLOCKSIZE - split;
if(nrem > 0) {
System.arraycopy(all, 0, bf.data, split, nrem);
bf.dirty = true;
}

int neededBlocks = (all.length - n) / IO.BLOCKSIZE;
// number of bytes which don't fill one block completely
final int remain = (all.length - n) % IO.BLOCKSIZE;
// number of new required blocks and remaining bytes
final int req = all.length - nrem;
int needed = req / IO.BLOCKSIZE;
final int remain = req % IO.BLOCKSIZE;

if(remain > 0) {
// check if the last entries can fit in the block after the current one
if(index + 1 < blocks) {
if(index + 1 < used) {
final int o = occSpace(index + 1) << IO.NODEPOWER;
if(remain <= IO.BLOCKSIZE - o) {
// copy the last records
@@ -409,61 +417,59 @@ public void insert(final int pre, final byte[] entries) {
readIndex(index - 1);
} else {
// there is not enough space in the block - allocate a new one
++neededBlocks;
++needed;
}
} else {
// this is the last block - allocate a new one
++neededBlocks;
++needed;
}
}

// number of expected blocks:
// existing blocks + needed block - empty blocks
final int expBlocks = allBlocks + neededBlocks - (allBlocks - blocks);
if(expBlocks > fpres.length) {
// number of expected blocks: existing blocks + needed block - empty blocks
final int exp = blocks + needed - (blocks - used);
if(exp > fpres.length) {
// resize directory arrays if existing ones are too small
final int ns = Math.max(fpres.length << 1, expBlocks);
final int ns = Math.max(fpres.length << 1, exp);
fpres = Arrays.copyOf(fpres, ns);
pages = Arrays.copyOf(pages, ns);
}

// make place for the blocks where the new entries will be written
Array.move(fpres, index + 1, neededBlocks, blocks - index - 1);
Array.move(pages, index + 1, neededBlocks, blocks - index - 1);
Array.move(fpres, index + 1, needed, used - index - 1);
Array.move(pages, index + 1, needed, used - index - 1);

// write the all remaining entries
while(neededBlocks-- > 0) {
while(needed-- > 0) {
freeBlock();
n += write(all, n);
nrem += write(all, nrem);
fpres[index] = fpres[index - 1] + IO.ENTRIES;
pages[index] = (int) bm.current().pos;
}

// increment first pre-values of blocks after the last modified block
for(int i = index + 1; i < blocks; ++i) fpres[i] += nr;
for(int i = index + 1; i < used; ++i) fpres[i] += nr;

meta.size += nr;

// update cached variables
fpre = fpres[index];
npre = index + 1 < blocks && fpres[index + 1] < meta.size ?
npre = index + 1 < used && fpres[index + 1] < meta.size ?
fpres[index + 1] : meta.size;
}

// PRIVATE METHODS ==========================================================

/**
* Searches for the block containing the entry for that pre. then it
* reads the block and returns it's offset inside the block.
* Searches for the block containing the entry for the specified pre value.
* Reads the block and returns its offset inside the block.
* @param pre pre of the entry to search for
* @return offset of the entry in currentBlock
* @return offset of the entry in the block
*/
private int cursor(final int pre) {
int fp = fpre;
int np = npre;

if(pre < fp || pre >= np) {
final int last = blocks - 1;
final int last = used - 1;
int l = 0;
int h = last;
int m = index;
@@ -475,9 +481,12 @@ private int cursor(final int pre) {
fp = fpres[m];
np = m == last ? meta.size : fpres[m + 1];
}
if(l > h) Util.notexpected("Data Access out of bounds [pre:" + pre +
", indexSize:" + blocks + ", access:" + l + " > " + h + ']');

if(l > h) Util.notexpected(
"Data Access out of bounds:" +
"\n- pre value: " + pre +
"\n- #used blocks: " + used +
"\n- #total locks: " + blocks +
"\n- access: " + m + " (" + l + " > " + h + ']');
readIndex(m);
}
return pre - fpre << IO.NODEPOWER;
@@ -490,7 +499,7 @@ private int cursor(final int pre) {
private void setIndex(final int i) {
index = i;
fpre = fpres[i];
npre = i + 1 >= blocks ? meta.size : fpres[i + 1];
npre = i + 1 >= used ? meta.size : fpres[i + 1];
}

/**
@@ -513,8 +522,8 @@ private void readBlock(final int b) {
try {
if(bf.dirty) writeBlock(bf);
bf.pos = b;
if(b >= allBlocks) {
allBlocks = b + 1;
if(b >= blocks) {
blocks = b + 1;
} else {
file.seek(bf.pos * IO.BLOCKSIZE);
file.readFully(bf.data);
@@ -531,7 +540,7 @@ private void freeBlock() {
final int b = pagemap.nextClearBit(0);
pagemap.set(b);
readBlock(b);
++blocks;
++used;
++index;
}

@@ -552,9 +561,9 @@ private void writeBlock(final Buffer bf) throws IOException {
*/
private void updatePre(final int nr) {
// update index entries for all following blocks and reduce counter
for(int i = index + 1; i < blocks; ++i) fpres[i] -= nr;
for(int i = index + 1; i < used; ++i) fpres[i] -= nr;
meta.size -= nr;
npre = index + 1 < blocks && fpres[index + 1] < meta.size ? fpres[index + 1] :
npre = index + 1 < used && fpres[index + 1] < meta.size ? fpres[index + 1] :
meta.size;
}

@@ -582,7 +591,7 @@ private void copy(final byte[] s, final int sp, final byte[] d,
*/
private int write(final byte[] s, final int o) {
final Buffer bf = bm.current();
final int len = Math.min(bf.data.length, s.length - o);
final int len = Math.min(IO.BLOCKSIZE, s.length - o);
System.arraycopy(s, o, bf.data, 0, len);
bf.dirty = true;
return len;
@@ -594,6 +603,6 @@ private int write(final byte[] s, final int o) {
* @return occupied space in number of records
*/
private int occSpace(final int i) {
return (i + 1 < blocks ? fpres[i + 1] : meta.size) - fpres[i];
return (i + 1 < used ? fpres[i + 1] : meta.size) - fpres[i];
}
}
17 src/main/java/org/basex/io/random/TableMemAccess.java
View file
@@ -5,6 +5,7 @@

import org.basex.data.*;
import org.basex.io.*;
import org.basex.util.list.*;

/**
* This class allows main memory access to the database table representation.
@@ -14,9 +15,9 @@
*/
public final class TableMemAccess extends TableAccess {
/** Long buffer array. */
private long[] buf1 = new long[16];
private long[] buf1 = new long[ElementList.CAP];
/** Long buffer array. */
private long[] buf2 = new long[16];
private long[] buf2 = new long[ElementList.CAP];

/**
* Stores the table in long arrays.
@@ -39,26 +40,22 @@ public boolean lock(final boolean lock) {

@Override
public int read1(final int p, final int o) {
return (int) ((o < 8 ? buf1 : buf2)[p] >>
((o < 8 ? 7 : 15) - o << 3) & 0xFF);
return (int) ((o < 8 ? buf1 : buf2)[p] >> ((o < 8 ? 7 : 15) - o << 3) & 0xFF);
}

@Override
public int read2(final int p, final int o) {
return (int) ((o < 8 ? buf1 : buf2)[p] >>
((o < 8 ? 6 : 14) - o << 3) & 0xFFFF);
return (int) ((o < 8 ? buf1 : buf2)[p] >> ((o < 8 ? 6 : 14) - o << 3) & 0xFFFF);
}

@Override
public int read4(final int p, final int o) {
return (int) ((o < 8 ? buf1 : buf2)[p] >>
((o < 8 ? 4 : 12) - o << 3));
return (int) ((o < 8 ? buf1 : buf2)[p] >> ((o < 8 ? 4 : 12) - o << 3));
}

@Override
public long read5(final int p, final int o) {
return (o < 8 ? buf1 : buf2)[p] >>
((o < 8 ? 3 : 11) - o << 3) & 0xFFFFFFFFFFL;
return (o < 8 ? buf1 : buf2)[p] >> ((o < 8 ? 3 : 11) - o << 3) & 0xFFFFFFFFFFL;
}

@Override
3 src/main/java/org/basex/util/Array.java
View file
@@ -86,8 +86,7 @@ public static int[] add(final int[] ar, final int e) {
* @param off move offset
* @param l length
*/
public static void move(final Object ar, final int pos, final int off,
final int l) {
public static void move(final Object ar, final int pos, final int off, final int l) {
System.arraycopy(ar, pos, ar, pos + off, l);
}

30 src/test/java/org/basex/test/data/DiskTableTest.java
View file
@@ -49,18 +49,15 @@ public static void setUpBeforeClass() {

/**
* Loads the JUnitTest database.
* @throws Exception exception
*/
@Before
public void setUp() {
try {
final Parser parser = Parser.xmlParser(IO.get(TESTFILE), context.prop);
data = new DiskBuilder(NAME, parser, context).build();
size = data.meta.size;
data.close();
tda = new TableDiskAccess(data.meta, true);
} catch(final Exception ex) {
Util.stack(ex);
}
public void setUp() throws Exception {
final Parser parser = Parser.xmlParser(IO.get(TESTFILE), context.prop);
data = new DiskBuilder(NAME, parser, context).build();
size = data.meta.size;
data.close();
tda = new TableDiskAccess(data.meta, true);

final int bc = size * (1 << IO.NODEPOWER);
storage = new byte[bc];
@@ -73,15 +70,12 @@ public void setUp() {

/**
* Drops the JUnitTest database.
* @throws Exception exception
*/
@After
public void tearDown() {
try {
if(tda != null) tda.close();
DropDB.drop(NAME, context);
} catch(final Exception ex) {
Util.stack(ex);
}
public void tearDown() throws Exception {
if(tda != null) tda.close();
DropDB.drop(NAME, context);
}

/**
@@ -156,7 +150,7 @@ private int tdaSize() {
*/
private int tdaBlocks() {
try {
final Field f = tda.getClass().getDeclaredField("blocks");
final Field f = tda.getClass().getDeclaredField("used");
f.setAccessible(true);
return f.getInt(tda);
} catch(final Exception ex) {