package simpledb;

import simpledb.*;
import java.util.*;
import java.io.*;

/**
 * BufferPool manages the reading and writing of pages into memory from
 * disk. Access methods call into it to retrieve pages, and it fetches
 * pages from the appropriate location.
 * <p>
 * The BufferPool is also responsible for locking;  when a transaction fetches
 * a page, BufferPool which check that the transaction has the appropriate
 * locks to read/write the page.
 */
public class BufferPool {
    /** Bytes per page, excluding header. */
    public static final int PAGE_SIZE = 4096;  
    private static final int NUM_PAGES = 16;
 
    static BufferPool createBufferPool() {
	return new BufferPool(NUM_PAGES);
    }

    /**
     * Constructor.
     *
     * @param numPages number of pages in this buffer pool 
     */
    private BufferPool(int numPages) {
        numSlots = numPages;
        slots = new ArrayList();
        slotIndex = new HashMap();

        for (int i = 0; i < numPages; i++) {
            slots.add(null);
        }
        
        emptySlotHint = 0;
    }

    /**
     * Retrieve the specified page with the associated permissions.
     * Will acquire a lock and may block if that lock is held by another
     * transaction.
     *
     * @param tid the ID of the transaction requesting the page
     * @param pid the ID of the requested page
     * @param perm the requested permissions on the page
     */
    public synchronized Page getPage(TransactionId tid, PageId pid,
                                     Permissions perm)
	throws TransactionAbortedException, DbException {
        // XXX Ignore tid and perms for now.

        PageSlot slot;

        // See if the page is already loaded.
        slot = findPage(pid);
        if (slot == null) {
            // Didn't find it; load it
            slot = loadPage(pid);
        }

        slot.recentlyReferenced = true;
        
        return slot.page;
    }

    /**
     * Releases the lock on a page.
     * Calling this is very risky, and may result in wrong behavior. Think hard
     * about who needs to call this and why, and why they can run the risk of
     * calling it.
     *
     * @param tid the ID of the transaction requesting the unlock
     * @param pid the ID of the page to unlock
     */
    public synchronized void releasePage(TransactionId tid, PageId pid) {
	// some code goes here
	// not necessary for lab1|lab2
    }

    /**
     * Release all locks associated with a given transaction.
     *
     * @param tid the ID of the transaction requesting the unlock
     */
    public synchronized void transactionComplete(TransactionId tid) throws IOException {
	// some code goes here
	// not necessary for lab1|lab2
    }

    /** Return true if the specified transaction has a lock on the specified page */
    public  synchronized boolean holdsLock(TransactionId tid, PageId p) {
	// some code goes here
	// not necessary for lab1|lab2
	return false;
    }

    /**
     * Commit or abort a given transaction; release all locks associated to
     * the transaction.
     *
     * @param tid the ID of the transaction requesting the unlock
     * @param commit a flag indicating whether we should commit or abort
     */
    public  synchronized void transactionComplete(TransactionId tid, boolean commit) 
	throws IOException {
	// some code goes here
	// not necessary for lab1|lab2
    }

    /**
     * Add a tuple to the specified table behalf of transaction tid.  Will
     * acquire a write lock on the page the tuple is added to. May block if
     * the lock cannot be acquired.
     *
     * @param tid the transaction adding the tuple
     * @param tableId the table to add the tuple to
     * @param t the tuple to add
     */
    public synchronized void insertTuple(TransactionId tid, int tableId, Tuple t)
	throws DbException, IOException, TransactionAbortedException {
	// some code goes here
	// not necessary for lab1
    }

    /**
     * Remove the specified tuple from the buffer pool.
     * Will acquire a write lock on the page the tuple is added to. May block if
     * the lock cannot be acquired.
     *
     * @param tid the transaction adding the tuple.
     * @param t the tuple to add
     */
    public synchronized void deleteTuple(TransactionId tid, Tuple t) 
	throws DbException, TransactionAbortedException {
	// some code goes here
	// not necessary for lab1
    }

    /**
     * Flush all dirty pages to disk.
     * NB: Be careful using this routine -- it writes dirty data to disk so will
     *     break simpledb if running in NO STEAL mode.
     */
    public synchronized void flushAllPages() throws IOException {
        for (int i = 0; i < numSlots; i++) {
            flushPage(i);
        }
    }
    
    /** Remove the specific page id from the buffer pool.
	Needed by the recovery manager to ensure that the
	buffer pool doesn't keep a rolled back page in its
	cache.
    */
    public synchronized void discardPage(PageId pid) {
	// some code goes here
	// only necessary for lab4
    }

    /**
     * Flushes a certain page to disk
     * @param slotNumber number of the page to flush
     */
    private synchronized void flushPage(int slotNum) throws IOException {
        PageSlot slot = slots.get(slotNum);
        if (slot == null) {
            return;
        }

        if (slot.page.isDirty() != null) {
            DbFile file = Database.getCatalog().getDbFile(slot.id.tableid());
            file.writePage(slot.page);
        }

        slots.set(slotNum, null);
        slotIndex.remove(slot.id);
        emptySlotHint = slotNum;
    }

    /** Write all pages of the specified transaction to disk.
     */
    public synchronized  void flushPages(TransactionId tid) throws IOException {
	// some code goes here
	// not necessary for lab1|lab2
    }
  
    /**
     * Discards a page from the buffer pool. Returns the index of the
     * now-empty slot.
     */
    private synchronized int evictPage() throws DbException {
        try {
            int newHand = clockHand;
            int ret = -1;
            int firstCleared = -1;
            

            // Starting at the current hand position, walk through the
            // list of slots clearing any recentlyReferenced bits that
            // are set, until we find an entry where the bits isn't
            // set.
            do {
                newHand++;
                if (newHand == slots.size()) {
                    newHand = 0;
                }

                if (slots.get(newHand) == null) {
                    // We found a free slot. This is a bug, since we
                    // shouldn't be evicting if a slot is free!
                    throw new RuntimeException("performing unnecessary eviction");
                }

                // XXX Check if page is evictable here. Not necessary
                // yet since pages are never pinned, but could become
                // necessary after transactions are implemented.

                if (slots.get(newHand).recentlyReferenced) {
                    // Flag is set; clear it
                    slots.get(newHand).recentlyReferenced = false;
                    if (firstCleared == -1) {
                        firstCleared = newHand;
                    }
                } else {
                    // Flag not set; return this one.
                    ret = newHand;
                    break;
                }
            } while (newHand != clockHand);

            if (ret == -1) {
                // We went completely around without finding a page to
                // evict. If we cleared any recentlyReferenced bits,
                // return the first one. Otherwise, there's nothing to
                // evict.
                if (firstCleared != -1) {
                    clockHand = firstCleared;
                    ret = firstCleared;
                } else {
                    // No evictable slots. This currently can't
                    // happen.
                    throw new RuntimeException("no evictable slots");
                }
            } else {
                clockHand = newHand;
            }

            // Flush the page we selected and return the index.
            flushPage(ret);
            return ret;
            
        } catch (IOException e) {
            throw new DbException("I/O error on page flushing");
        }
    }

    private synchronized PageSlot findPage(PageId pid)
        throws DbException {
        return slotIndex.get(pid);
    }
    
    private synchronized PageSlot loadPage(PageId pid)
        throws DbException {
        int slotNum = -1;

        // Find an empty slot.
        // First, try the hint.
        if ((emptySlotHint != -1) &&
            (slots.get(emptySlotHint) == null)) {
            slotNum = emptySlotHint;
            emptySlotHint = -1;
        } else {
            // Next, see if there's an empty slot.
            for (int i = 0; i < numSlots; i++) {
                if (slots.get(i) == null) {
                    slotNum = i;
                    break;
                }
            }
        }

        if (slotNum == -1) {
            // No empty slots found. Evict one
            slotNum = evictPage();
        }


        // Load the page
        DbFile file = Database.getCatalog().getDbFile(pid.tableid());
        Page page = file.readPage(pid);
        PageSlot pageSlot = new PageSlot(page, pid);
        
        slots.set(slotNum, pageSlot);

        return pageSlot;
    }

    private int numSlots;

    /**
     * Associates a cached page with its id and other relevant
     * information.
     */
    private class PageSlot {
        Page page;
        PageId id;
        boolean recentlyReferenced; // for clock pseudo-LRU

        PageSlot(Page page, PageId id) {
            this.page = page;
            this.id = id;
        }
    }
    
    /**
     * Array of page slots (size numSlots). May be null to indicate
     * that the slot is currently unused.
     */
    private List<PageSlot> slots;

    /**
     * Hint for locating an empty slot, an optimization to prevent
     * walking the full list of slots. This specifies an index that
     * into the slots list that may be empty (but is not required to
     * be), or -1 if no such hint exists.
     */
    private int emptySlotHint = -1;

    /**
     * Index into the slots list representing the slot that the "clock
     * hand" for the pseudo-LRU replacement policy is pointing at.
     */
    private int clockHand = 0;

    /**
     * Index of the currently-in-use slots. Maps page ID to the slot
     * that currently contains it.
     */
    private Map<PageId, PageSlot> slotIndex;
}