package simpledb.index.btree;import simpledb.file.Block;import simpledb.tx.Transaction;import simpledb.record.TableInfo;import simpledb.query.Constant;/** * A B-tree directory block. * @author Edward Sciore */public class BTreeDir {	private TableInfo md;	private Transaction tx;	private String filename;	private BTreePage contents;	/**	 * Creates an object to hold the contents of the specified	 * B-tree block.	 * @param blk a reference to the specified B-tree block	 * @param md the metadata of the B-tree directory file	 * @param tx the calling transaction	 */	BTreeDir(Block blk, TableInfo md, Transaction tx) {		this.md = md;		this.tx = tx;		filename = blk.fileName();		contents = new BTreePage(blk, md, tx);	}	/**	 * Closes the directory page.	 */	public void close() {		contents.close();	}	/**	 * Returns the block number of the B-tree leaf block	 * that contains the specified search key.	 * @param searchkey the search key value	 * @return the block number of the leaf block containing that search key	 */	public int search(Constant searchkey) {		Block childblk = findChildBlock(searchkey);		while (contents.getFlag() > 0) {			contents.close();			contents = new BTreePage(childblk, md, tx);			childblk = findChildBlock(searchkey);		}		return childblk.number();	}	/**	 * Creates a new root block for the B-tree.	 * The new root will have two children:	 * the old root, and the specified block.	 * @param e the directory entry to be added as a child of the new root	 */	public void makeNewRoot(DirEntry e) {		Constant firstval = contents.getDataVal(0);		int level = contents.getFlag();		Block newblk = contents.appendNew(filename, level);		contents.moveTo(newblk);		DirEntry oldroot = new DirEntry(firstval, newblk.number());		insertEntry(oldroot);		insertEntry(e);		contents.setFlag(level+1);	}	/**	 * Inserts a new directory entry into the B-tree block.	 * If the block is at level 0, then the entry is inserted there.	 * Otherwise, the entry is inserted into the appropriate	 * child node, and the return value is examined.	 * A non-null return value indicates that the child node	 * split, and so the returned entry is inserted into 	 * this block.	 * If this block splits, then the method similarly returns	 * the entry information of the new block to its caller;	 * otherwise, the method returns null.	 * @param e the directory entry to be inserted	 * @return the directory entry of the newly-split block, if one exists; otherwise, null	 */	public DirEntry insert(DirEntry e) {		if (contents.getFlag() == 0)			return insertEntry(e);		Block childblk = findChildBlock(e.dataVal());		BTreeDir child = new BTreeDir(childblk, md, tx);		DirEntry myentry = child.insert(e);		child.close();		return (myentry != null) ? insertEntry(myentry) : null;	}	private DirEntry insertEntry(DirEntry e) {		int newslot = 1 + contents.findSlotBefore(e.dataVal());		contents.insertDir(newslot, e.dataVal(), e.blockNumber());		if (!contents.isFull())			return null;		// else page is full, so split it		int level = contents.getFlag();		Block newblk = contents.appendNew(filename, level);		BTreePage newpage = new BTreePage(newblk, md, tx);		Constant splitval = contents.split(newpage);		newpage.close();		return new DirEntry(splitval, newblk.number());	}	private Block findChildBlock(Constant searchkey) {		int slot = contents.findSlotBefore(searchkey);		if (contents.getDataVal(slot+1).equals(searchkey))			slot++;		int blknum = contents.getChildNum(slot);		return new Block(filename, blknum);	}}