Quadcap Embeddable Database

com.quadcap.sql.index.Btree Class Reference

Inheritance diagram for com.quadcap.sql.index.Btree:

com.quadcap.sql.index.BIndex List of all members.

Detailed Description

A Btree implementation.

Most of the real work happens in the Bnode class.

Author:
Stan Bailes

Definition at line 59 of file Btree.java.

Public Member Functions

 Btree (BlockFile file, Comparator compare, long rootBlock, boolean create) throws IOException
 Open a btree index.

 Btree (BlockFile file, long rootBlock, boolean create) throws IOException
 Open a btree index.

int size () throws IOException
int get (byte[] key, int klen, byte[] data) throws IOException
 Get the data bytes for the specified key.

byte[] get (byte[] key) throws IOException
boolean delete (byte[] key) throws IOException
 Delete the specified key.

boolean deleteObs (byte[] key) throws IOException
void set (byte[] key, byte[] val) throws IOException
void insert (byte[] key, int klen, byte[] val, int off, int len) throws IOException
 Add a new key.

void update (byte[] key, int klen, byte[] val, int off, int len) throws IOException
 Update the data value for an existing key.

boolean set (byte[] key, int klen, byte[] val, int off, int len) throws IOException
 Set the key/data pair, replacing any any value it may present in a unique index, inserting a new values, whatever.

long getRootBlock ()
BlockFile getFile ()
 Return a reference to the underlying BlockFile</code.

Comparator getComparator ()
 Return the comparator used to collate keys.

BCursor getCursor () throws IOException
 Get a cursor.

BCursor getCursor (boolean skipSetup) throws IOException
 Get a cursor.

void releaseCursor (BCursor c)
void notifyUpdate (BCursor notMe)
void free () throws IOException
 Destroy this tree and free all of its resources.

String toString ()
void display (PrintWriter w) throws IOException

Package Functions

Bnode getNode (long ref)
Bnode getRoot ()
void setRoot (long ref)

Package Attributes

BlockFile file
Comparator compare
long rootBlock
Bnode root
Object lock
byte[] tbuf = new byte[16]
Set activeCursors = new HashSet()

Private Member Functions

final BCursor getMyCursor () throws IOException

Constructor & Destructor Documentation

com.quadcap.sql.index.Btree.Btree (  BlockFile  file,
Comparator  compare,
long  rootBlock,
boolean  create
)  throws IOException
 

Open a btree index.

Fetch the root block and create an empty tree if the block is zero, open the existing tree otherwise.

Parameters:
file the (already opened) blockfile
compare the compare function for key ordering
rootBlock the block number of the root block of this tree
create if true, initialize the rootblock to be empty.
Exceptions:
IOException if an I/O error occurs opening or accessing the file.

Definition at line 79 of file Btree.java.

References com.quadcap.sql.index.Bnode.checkMagic(), com.quadcap.sql.index.Btree.compare, com.quadcap.sql.index.Btree.file, com.quadcap.sql.index.Btree.getNode(), com.quadcap.sql.index.Bnode.init(), com.quadcap.sql.index.Btree.root, and com.quadcap.sql.index.Btree.rootBlock.

com.quadcap.sql.index.Btree.Btree (  BlockFile  file,
long  rootBlock,
boolean  create
)  throws IOException
 

Open a btree index.

Fetch the root block and create an empty tree if the block is zero, open the existing tree otherwise.

Parameters:
file the (already opened) blockfile
rootBlock the block number of the root block of this tree
create if true, initialize the rootblock to be empty.
Exceptions:
IOException if an I/O error occurs opening or accessing the file.

Definition at line 112 of file Btree.java.

References com.quadcap.sql.index.Btree.file, and com.quadcap.sql.index.Btree.rootBlock.

Member Function Documentation

boolean com.quadcap.sql.index.Btree.delete (  byte[]  key  )  throws IOException
 

Delete the specified key.

Return true if the key was deleted.

Implements com.quadcap.sql.index.BIndex.

Definition at line 162 of file Btree.java.

References com.quadcap.sql.index.BCursor.delete(), com.quadcap.sql.index.Btree.getMyCursor(), com.quadcap.sql.index.Btree.lock, com.quadcap.sql.index.BCursor.release(), and com.quadcap.sql.index.BCursor.seek().

Referenced by com.quadcap.sql.DeleteIndexEntry.redo(), and com.quadcap.sql.AddIndexEntry.undo().

boolean com.quadcap.sql.index.Btree.deleteObs (  byte[]  key  )  throws IOException
 

Definition at line 175 of file Btree.java.

References com.quadcap.sql.index.Bnode.delete(), com.quadcap.sql.index.Btree.deleteObs(), com.quadcap.sql.index.Btree.getRoot(), com.quadcap.sql.index.Btree.lock, and com.quadcap.sql.index.Btree.rootBlock.

Referenced by com.quadcap.sql.index.Btree.deleteObs().

void com.quadcap.sql.index.Btree.display (  PrintWriter  w  )  throws IOException
 

Definition at line 332 of file Btree.java.

References com.quadcap.sql.index.Btree.display(), com.quadcap.sql.index.Btree.getCursor(), com.quadcap.sql.index.BCursor.getKey(), com.quadcap.sql.index.BCursor.getVal(), com.quadcap.sql.index.BCursor.next(), and com.quadcap.sql.index.BCursor.release().

Referenced by com.quadcap.sql.index.Btree.display().

void com.quadcap.sql.index.Btree.free (   )  throws IOException
 

Destroy this tree and free all of its resources.

Implements com.quadcap.sql.index.BIndex.

Definition at line 304 of file Btree.java.

References com.quadcap.sql.index.Btree.activeCursors, com.quadcap.sql.index.Bnode.free(), com.quadcap.sql.index.Btree.getRoot(), com.quadcap.sql.index.BtreeCursor.release(), and com.quadcap.sql.index.Btree.rootBlock.

Referenced by com.quadcap.sql.UpdateIndex.finish(), and com.quadcap.sql.UnaryExpression.uniqueValue().

byte [] com.quadcap.sql.index.Btree.get (  byte[]  key  )  throws IOException
 

Definition at line 145 of file Btree.java.

References com.quadcap.sql.index.Btree.getMyCursor(), com.quadcap.sql.index.BCursor.getVal(), com.quadcap.sql.index.BCursor.getValLen(), com.quadcap.sql.index.Btree.lock, com.quadcap.sql.index.BCursor.release(), and com.quadcap.sql.index.BCursor.seek().

int com.quadcap.sql.index.Btree.get (  byte[]  key,
int  klen,
byte[]  data
)  throws IOException
 

Get the data bytes for the specified key.

If the key is found, return the length of the data portion and place as many bytes as will fit in the data array. If the key isn't found, return -1.

Implements com.quadcap.sql.index.BIndex.

Definition at line 133 of file Btree.java.

References com.quadcap.sql.index.Btree.get(), com.quadcap.sql.index.Btree.getMyCursor(), com.quadcap.sql.index.BCursor.getVal(), com.quadcap.sql.index.Btree.lock, com.quadcap.sql.index.BCursor.release(), and com.quadcap.sql.index.BCursor.seek().

Referenced by com.quadcap.sql.UpdateIndex.addEntry(), com.quadcap.sql.UniqueConstraint.checkInsert(), com.quadcap.sql.UpdateIndex.finish(), com.quadcap.sql.index.Btree.get(), com.quadcap.sql.TempTableMerge.getData(), and com.quadcap.sql.DeleteIndexEntry.prepare().

Comparator com.quadcap.sql.index.Btree.getComparator (   ) 
 

Return the comparator used to collate keys.

Implements com.quadcap.sql.index.BIndex.

Definition at line 259 of file Btree.java.

References com.quadcap.sql.index.Btree.compare.

BCursor com.quadcap.sql.index.Btree.getCursor (  boolean  skipSetup  )  throws IOException
 

Get a cursor.

Implements com.quadcap.sql.index.BIndex.

Definition at line 275 of file Btree.java.

References com.quadcap.sql.index.Btree.activeCursors, and com.quadcap.sql.index.Btree.lock.

BCursor com.quadcap.sql.index.Btree.getCursor (   )  throws IOException
 

Get a cursor.

Definition at line 266 of file Btree.java.

Referenced by com.quadcap.sql.TempTableMerge.addRows(), com.quadcap.sql.ExportedKeyConstraint.checkKeyRemoval(), com.quadcap.sql.StmtDropTable.deleteRows(), com.quadcap.sql.index.Btree.display(), com.quadcap.sql.StmtDropColumn.execute(), com.quadcap.sql.StmtAddColumn.execute(), com.quadcap.sql.UpdateIndex.finish(), com.quadcap.sql.index.BtreeCursor.main(), and com.quadcap.sql.UnaryExpression.uniqueValue().

BlockFile com.quadcap.sql.index.Btree.getFile (   ) 
 

Return a reference to the underlying BlockFile</code.

Definition at line 254 of file Btree.java.

References com.quadcap.sql.index.Btree.file.

Referenced by com.quadcap.sql.index.BtreeCursor.id().

final BCursor com.quadcap.sql.index.Btree.getMyCursor (   )  throws IOException [private]
 

Definition at line 122 of file Btree.java.

Referenced by com.quadcap.sql.index.Btree.delete(), and com.quadcap.sql.index.Btree.get().

Bnode com.quadcap.sql.index.Btree.getNode (  long  ref  )  [package]
 

Definition at line 237 of file Btree.java.

References com.quadcap.sql.index.Btree.getNode().

Referenced by com.quadcap.sql.index.Btree.Btree(), com.quadcap.sql.index.Btree.getNode(), com.quadcap.sql.index.Bnode.newLow(), and com.quadcap.sql.index.Bnode.propogateSplit().

Bnode com.quadcap.sql.index.Btree.getRoot (   )  [package]
 

Definition at line 241 of file Btree.java.

References com.quadcap.sql.index.Btree.root.

Referenced by com.quadcap.sql.index.BtreeCursor.beforeFirst(), com.quadcap.sql.index.Btree.deleteObs(), com.quadcap.sql.index.Btree.free(), com.quadcap.sql.index.Btree.insert(), com.quadcap.sql.index.Btree.set(), com.quadcap.sql.index.BtreeCursor.setup(), com.quadcap.sql.index.Btree.size(), and com.quadcap.sql.index.Btree.update().

long com.quadcap.sql.index.Btree.getRootBlock (   ) 
 

Definition at line 243 of file Btree.java.

References com.quadcap.sql.index.Btree.rootBlock.

Referenced by com.quadcap.sql.index.BtreeCursor.id().

void com.quadcap.sql.index.Btree.insert (  byte[]  key,
int  klen,
byte[]  val,
int  off,
int  len
)  throws IOException
 

Add a new key.

If the index is a UNIQUE index, then the new key/data pair will only be added if the key does not already exist, otherwise, insert will do nothing and return false The existing value must not exist or an IOException will be thrown. Otherwise, the new key/data pair is added regardless.

Implements com.quadcap.sql.index.BIndex.

Definition at line 191 of file Btree.java.

References com.quadcap.sql.index.Btree.getRoot(), com.quadcap.sql.index.Btree.insert(), com.quadcap.sql.index.Btree.lock, com.quadcap.sql.index.Btree.notifyUpdate(), com.quadcap.sql.index.Btree.rootBlock, and com.quadcap.sql.index.Bnode.set().

Referenced by com.quadcap.sql.index.Btree.insert().

void com.quadcap.sql.index.Btree.notifyUpdate (  BCursor  notMe  ) 
 

Definition at line 293 of file Btree.java.

References com.quadcap.sql.index.Btree.activeCursors, com.quadcap.sql.index.Btree.notifyUpdate(), and com.quadcap.sql.index.BtreeCursor.unsetup().

Referenced by com.quadcap.sql.index.BtreeCursor.delete(), com.quadcap.sql.index.BtreeCursor.insert(), com.quadcap.sql.index.Btree.insert(), com.quadcap.sql.index.Btree.notifyUpdate(), com.quadcap.sql.index.BtreeCursor.replace(), com.quadcap.sql.index.Btree.set(), and com.quadcap.sql.index.Btree.update().

void com.quadcap.sql.index.Btree.releaseCursor (  BCursor  c  ) 
 

Definition at line 284 of file Btree.java.

References com.quadcap.sql.index.Btree.activeCursors, com.quadcap.sql.index.BCursor.close(), com.quadcap.sql.index.Btree.lock, and com.quadcap.sql.index.Btree.releaseCursor().

Referenced by com.quadcap.sql.index.BtreeCursor.release(), and com.quadcap.sql.index.Btree.releaseCursor().

boolean com.quadcap.sql.index.Btree.set (  byte[]  key,
int  klen,
byte[]  val,
int  off,
int  len
)  throws IOException
 

Set the key/data pair, replacing any any value it may present in a unique index, inserting a new values, whatever.

Return true if the key already existed before this operation.

Implements com.quadcap.sql.index.BIndex.

Definition at line 221 of file Btree.java.

References com.quadcap.sql.index.Btree.getRoot(), com.quadcap.sql.index.Btree.lock, com.quadcap.sql.index.Btree.notifyUpdate(), com.quadcap.sql.index.Btree.rootBlock, and com.quadcap.sql.index.Bnode.set().

void com.quadcap.sql.index.Btree.set (  byte[]  key,
byte[]  val
)  throws IOException
 

Definition at line 187 of file Btree.java.

References com.quadcap.sql.index.Btree.set().

Referenced by com.quadcap.sql.UpdateIndex.addEntry(), com.quadcap.sql.AddIndexEntry.redo(), com.quadcap.sql.index.Btree.set(), com.quadcap.sql.DeleteIndexEntry.undo(), and com.quadcap.sql.AggregateExpression.updateAggregate().

void com.quadcap.sql.index.Btree.setRoot (  long  ref  )  [package]
 

Definition at line 247 of file Btree.java.

References com.quadcap.sql.index.Btree.root, com.quadcap.sql.index.Btree.rootBlock, and com.quadcap.sql.index.Btree.setRoot().

Referenced by com.quadcap.sql.index.Btree.setRoot().

int com.quadcap.sql.index.Btree.size (   )  throws IOException
 

Definition at line 118 of file Btree.java.

References com.quadcap.sql.index.Btree.getRoot(), and com.quadcap.sql.index.Bnode.size().

String com.quadcap.sql.index.Btree.toString (   ) 
 

Definition at line 328 of file Btree.java.

References com.quadcap.sql.index.Btree.rootBlock.

void com.quadcap.sql.index.Btree.update (  byte[]  key,
int  klen,
byte[]  val,
int  off,
int  len
)  throws IOException
 

Update the data value for an existing key.

This only works for UNIQUE indexes, and only if the specified key already exists.

Exceptions:
IOException may be thrown.

Implements com.quadcap.sql.index.BIndex.

Definition at line 206 of file Btree.java.

References com.quadcap.sql.index.Btree.getRoot(), com.quadcap.sql.index.Btree.lock, com.quadcap.sql.index.Btree.notifyUpdate(), com.quadcap.sql.index.Btree.rootBlock, com.quadcap.sql.index.Bnode.set(), and com.quadcap.sql.index.Btree.update().

Referenced by com.quadcap.sql.index.Btree.update().

Member Data Documentation

Set com.quadcap.sql.index.Btree.activeCursors = new HashSet() [package]
 

Definition at line 270 of file Btree.java.

Referenced by com.quadcap.sql.index.Btree.free(), com.quadcap.sql.index.Btree.getCursor(), com.quadcap.sql.index.Btree.notifyUpdate(), and com.quadcap.sql.index.Btree.releaseCursor().

Comparator com.quadcap.sql.index.Btree.compare [package]
 

Definition at line 61 of file Btree.java.

Referenced by com.quadcap.sql.index.BtreeCursor.beforeFirst(), com.quadcap.sql.index.Bnode.bsearch(), com.quadcap.sql.index.Btree.Btree(), com.quadcap.sql.index.Bnode.checkBlock(), com.quadcap.sql.index.Bnode.display(), com.quadcap.sql.index.Btree.getComparator(), com.quadcap.sql.index.BtreeCursor.k(), com.quadcap.sql.index.Bnode.setKey(), and com.quadcap.sql.index.BtreeCursor.setup().

BlockFile com.quadcap.sql.index.Btree.file [package]
 

Definition at line 60 of file Btree.java.

Referenced by com.quadcap.sql.index.Bnode.Bnode(), com.quadcap.sql.index.Btree.Btree(), and com.quadcap.sql.index.Btree.getFile().

Object com.quadcap.sql.index.Btree.lock [package]
 

Definition at line 64 of file Btree.java.

Referenced by com.quadcap.sql.index.Btree.delete(), com.quadcap.sql.index.Btree.deleteObs(), com.quadcap.sql.index.BtreeCursor.get(), com.quadcap.sql.index.Btree.get(), com.quadcap.sql.index.Btree.getCursor(), com.quadcap.sql.index.BtreeCursor.init(), com.quadcap.sql.index.Btree.insert(), com.quadcap.sql.index.Btree.releaseCursor(), com.quadcap.sql.index.Btree.set(), and com.quadcap.sql.index.Btree.update().

Bnode com.quadcap.sql.index.Btree.root [package]
 

Definition at line 63 of file Btree.java.

Referenced by com.quadcap.sql.index.Btree.Btree(), com.quadcap.sql.index.Btree.getRoot(), and com.quadcap.sql.index.Btree.setRoot().

long com.quadcap.sql.index.Btree.rootBlock [package]
 

Definition at line 62 of file Btree.java.

Referenced by com.quadcap.sql.index.Btree.Btree(), com.quadcap.sql.index.Btree.deleteObs(), com.quadcap.sql.index.Btree.free(), com.quadcap.sql.index.Btree.getRootBlock(), com.quadcap.sql.index.Btree.insert(), com.quadcap.sql.index.Btree.set(), com.quadcap.sql.index.Btree.setRoot(), com.quadcap.sql.index.Btree.toString(), and com.quadcap.sql.index.Btree.update().

byte [] com.quadcap.sql.index.Btree.tbuf = new byte[16] [package]
 

Definition at line 65 of file Btree.java.