The heapfile component uses the buffer manager to read and write pages. It also directly accesses the directory service offered by the space manager. The methods provided the lock manager are used for regulating the accesses by concurrent users of the heapfile. Crash recovery is ensured through the physical logging of updates to pages, using the recovery manager.
class HeapFile { friend class Scan; public: HeapFile(char* name,Status& returnStatus); ~HeapFile(); Status insertRecord(char* recPtr, int recLen, RID& outRid); Status deleteRecord(const RID& rid); Status updateRecord(const RID& rid, char* recPtr, int reclen); int getRecCnt(); Status getRecord(const RID& rid, char* recPtr, int& recLen); Scan* openScan(Status& status); Status deleteFile(); }
The class HeapFile provides the abstraction of an unordered set of records. The records are a sequence of bytes and no field structure is assumed. The methods return a status that indicates whether the operation was successful or not (refer global_error).
The constructor takes the name as an input parameter. If a heapfile with the name already exists in the database, it is opened. If not, a heapfile is created with this name. The destructor closes the heapfile.
Each record in the heapfile has a unique identifier of type RID. insertRecord() inserts the specified record into the heapfile and returns the rid corresponding to the record. deleteRecord() takes the record identifier and deletes the corresponding record from the heapfile. If the specified record identifier does not correspond to an actual record, an error is flagged. The method updateRecord() modifies the contents of the specified record without changing its rid. In the current implementation, there is a restriction that the length of the new record should not exceed that of the old record.
getRecCnt() returns the number of records that are currently stored in the heapfile. A specific record can be retrieved by passing its record identifier to getRecord(). deleteFile() removes the heapfile from the database. A sequential scan of the heapfile can be initiated through openScan(). This method returns an object of type Scan, which is discussed in the next section.
class Scan { public: ~Scan(); Status getNext(RID& rid, char* recPtr, int& recLen); }
The Scan class supports the sequential scan of a heapfile. No conditions can be applied on the scan and thus, all the records in the heapfile are retrieved in turn. Objects of this type can only be constructed by openScan() method of the HeapFile class and hence, the constructor of this class is not public to the users of the heapfile component.
getNext() fetches the next record in the heapfile. It also returns the record identifier of the retrieved record. This method returns DONE when there are no more records to be fetched.
The header page of the heapfile is different from the other pages of the heapfile. The header page does not store any records. The structure of the header page is as follows.
struct HeaderPage { char fileName[MAX_NAME]; // name of file PageId firstPage; // pageNo of first data page PageId lastPage; // pageNo of last data page int pageCnt; // number of pages int recCnt; // record count };
The firstPage and lastPage fields are used in the method for inserting records.
Each of the data pages of the heapfile share a common structure. The class HFPage provides the abstraction for a data page of the heapfile.
// slot structure struct slot_t { short offset; short length; // equals -1 if slot is not in use }; const int DPFIXED= sizeof(lsn_t)+sizeof(slot_t)+4*sizeof(short)+ 3*sizeof(int); const int DATASIZE = PAGESIZE - sizeof(lsn_t); class HFPage { private: char data[DATASIZE - DPFIXED]; slot_t slot[1]; // first element of slot array short slotCnt; // number of slots in use; short freePtr; // offset of first free byte in data[] short freeSpace; // number of bytes free in data[] short dummy; // for alignment purposes PageId prevPage; // backward pointer to data page PageId nextPage; // forward pointer to data page PageId curPage; // page number of current pointer public: void init(PageId pageNo); // initialize a new page void dumpPage(); // dump contents of a page PageId getNextPage(); // returns value of nextPage PageId getPrevPage(); // returns value of prevPage void setNextPage(PageId pageNo); // sets value of nextPage void setPrevPage(PageId pageNo); // sets value of prevPage // inserts a new record pointed to by recPtr with length // recLen onto the page, returns RID of record Status insertRecord(char* recPtr, int recLen, RID& rid); // delete the record with the specified rid Status deleteRecord(const RID& rid); // returns RID of first record on page // returns NORECORDS if page contains no records. // Else, returns OK Status firstRecord(RID& firstRid); // returns RID of next record on the page // returns ENDOFPAGE if no more records exist on the page Status nextRecord (RID curRid, RID& nextRid); // copies out record with RID rid into recPtr Status getRecord(RID rid, char* recPtr, int& recLen); // returns a pointer to the record with RID rid Status returnRecord(RID rid, char*& recPtr, int& recLen); }
The HFPage class uses a slotted page approach for organizing
variable sized records. The records are stored one after another
starting at byte 0 of the page while the slot array grows from the
rear of the page towards the front. As the records are deleted, the
resulting hole is compacted. However, since records are addressed via
a RID (consisting of the
The methods of HFPage provide the primitives for all operations on
a single page. insertRecord() tries to insert the specified
record into the page. It returns a error if there is not sufficient
free space on the page. deleteRecord() deletes the specified
record and compacts the hole created. This requires that all the
offsets in the slot array, of all the records to the right of the hole
be adjusted by the size of the hole. firstRecord() and
nextRecord() are used to fetch records off a page. The
getRecord() method copies out the specified record, while the
returnRecord() method returns a pointer to the record. The latter
function is used by the updateRecord method of HeapFile.
The methods in the HeapFile class invoke suitable methods of the
HFPage class. insertRecord first determines the page where the
record insertion is attempted. In the current implementation, the last
page of the heapfile is the only page considered for insertion. If
there is not enough space on the last page, a new page is created and
the record inserted there. An alternative implementation could involve
maintaining a list of pages that have some free space in
them. However, due to variable sized records, this strategy might
degenerate to an entire scan on insert, in the worst case.
deleteRecord() simply calls the function with the same name on the
appropriate data page. updateRecord() first obtains a pointer to
the record on the page and then modifies its contents.
deleteFile() deallocates the pages belonging to the heapfile and also
deletes the file entry from the directory.
openScan() returns a Scan object. The Scan class maintains the
RID of the last record that has been returned by it. Thus a call to
getNext() searches for the record following the current rid and
returns it. If no such record is found i.e. the last record on the
last page has already been returned, the scan is done.
The page level locking primitives provided by the lock manager are
used for concurrency control. A page that is read is locked in the
shared mode and any that is modified is locked in exclusive mode. A
finer granularity of locking could have improved the concurrency of
operations on the heapfile immensely.
Updates to pages belonging to the heapfile are logged using the method
provided by the recovery manager. Physical logging is performed and
the before and after images of the affected portions of the page are
logged.
Ravi Murthy
Sriram Narasimhan