Minibase Assignment #2: Heap File Page
Assigned on Wednesday, April 17.
Due on Wednesday, May 1.
Introduction
In this assignment, you will implement the page structure for the Heap File layer.
You will be given libraries for the lower layers (Buffer Manager and Disk Space
Manager), and some driver routines to test the code.
Preliminary Work
Begin by reading the description of Heap Files in section 7.5.1 of the text
book, and the description of page formats in section 7.6. A HeapFile is
seen as a collection of records. Internally, records are stored on a
collection of pages. The pages are HFPage objects.
You will be implementing the HFPage class: a slotted page class that stores
variable length records. The rest of the HeapFile code will be given to
you. Read the description in the text of how variable length records can
be stored on a slotted page, and follow this page organization.
Getting Started
Create a directory for the assignment, and change to that directory. Copy the
file /usr/local/mini_hwk/assign/HFPage/src/Makefile to your current
directory. To obtain the rest of the files that you will need, type make
setup. If you make the project, it should create an executable
named hfpage. You will need to provide the definition of the HFPage
class in the file hfpage.C.
Sample output of a correct implementation is available in
sample_output.
Design Overview and Implementation Details
Take a look at the file hfpage.h. It contains the interfaces for the
HFPage class. This class implements a "heap-file page" object. Note that the protected
data members of the class are given to you. All you need to do is implement the
public member functions. You should put all your code into the file hfpage.C.
A Note on the Slot Directory
In the description in the text, the slot directory is located at the
end of the page, and grows toward the beginning. This has confused
students in the past, since it means that negative offsets into the slot
directory have to be used. The current definition of HFPage has the slot
directory at the beginning of the page, after a few fixed member
fields, and growing toward the end. This does mean, however, that you will
need to write the code so the records themselves are placed beginning at
the end of the page. Be very careful with your pointer arithmetic.
Also note that in order to add a record to a page, there has to be room for
the record itself in the data area, and there also has to be room for a new
slot for this record in the slot directory (unless there happens to be a
pre-allocated slot that is empty).
Error Reporting in the Code
Please follow the Minibase
Error Protocol, in the same fashion that you did for the first Minibase assignment.
Note that this layer of the code is referred to in error reporting as HEAPFILE
(like BUFMGR was in the last assignment).
Methods to be Implemented
-
void HFPage::init(PageId pageNo)
This member function is used to initialize a new heap file page with page
number pageNo. It should set the following data members to reasonable
defaults: nextPage, prevPage, slotCnt, curPage, usedPtr, freeSpace. You
will find the definitions of these data members in hfpage.h. The
nextPage and prevPage data members are used for keeping track of pages in a
HeapFile.
A good default unknown value for a PageId is INVALID_PAGE, as defined in
page.h. Note that usedPtr is an offset into the data array, not a pointer.
-
PageId HFPage::getNextPage()
This member function should return the page id stored in the nextPage data
member.
-
PageId HFPage::getPrevPage()
This member function should return the page id stored in the prevPage data
member.
-
void HFPage::setNextPage(PageId pageNo)
This member function sets the nextPage data member.
-
void HFPage::setPrevPage(PageId pageNo)
This member function sets the prevPage data member.
-
Status HFPage::insertRecord(char* recPtr, int reclen, RID& rid)
This member function should add a new record to the page. It returns OK if
everything went OK, and DONE if sufficient space does not exist on the page
for the new record. If it returns OK, it should set rid to be the RID of
the new record (otherwise it can leave rid untouched.) Please note in the
parameter list recPtr is a char pointer and RID& denotes pass
by reference.
The Status enumeration type is defined in new_error.h. You may want to
look that file over and handle errors in a more informative manner than
suggested here.
The RID struct is defined as follows:
Struct RID {
PageID pageNo;
int slotNo;
int operator == (const RID rid) const
{ return (pageNo == rid.pageNo) && (slotNo == rid.slotNo); };
int operator != (const RID rid) const
{ return (pageNo != rid.pageNo) || (slotNo != rid.slotNo); };
friend ostream& operator << (ostream& out, const struct RID rid);
};
The pageNo identifies a physical page number (something that the buffer
manager and the DB layers understand) in the file. The slotNo specifies an
entry in the slot array on the page.
-
Status HFPage::deleteRecord(const RID& rid)
This member function deletes the record with the given RID from the page,
compacting the hole created. Compacting the hole, in turn, requires that
all the offsets (in the slot array) of all records after the hole be
adjusted by the size of the hole, because you are moving these records to
"fill" the hole. You should leave a "hole" in the slot array for the slot
which pointed to the deleted record, if necessary, to make sure that the
rids of the remaining records do not change. The slot array can be
compacted only if the record corresponding to the last slot is being
deleted. This function returns OK if everything goes OK, or FAIL
otherwise.
-
Status HFPage::firstRecord(RID& firstRid)
This routine should set firstRid to be the rid of the "first" record on the
page. The order in which you return records from a page is entirely up to
you. If you find a first record, return OK, else return DONE.
-
Status HFPage::nextRecord(RID curRid, RID& nextRid)
Given a valid current RID, curRid, this member function stores the
next RID on the page in the nextRid variable. Again, the order of your
return records is up to you, but do make sure you return each record
exactly once if someone continually calls nextRecord. Don't worry about
changes to the page between successive calls (e.g. records inserted to or
deleted from the page). If you find a next RID, return OK, else return
DONE. In case of an error, return FAIL.
-
Status HFPage::getRecord(RID rid, char * recPtr, int& recLen)
Given a rid, this routine copies the associated record into the memory
starting at address recPtr. You may assume that the memory pointed by
recPtr has been allocated by the caller. RecLen is set to the number of
bytes that the record occupies. If all goes well, return OK, else return
FAIL.
-
Status HFPage::returnRecord(RID rid, char*& recPtr, int& recLen)
This routine is very similar to HFPage::getRecord, except in this case you
do not copy the record into a caller-provided pointer, but instead you set
the caller's recPtr to point directly to the record on the page. Again,
return either OK or FAIL.
DONE is a special code for non-errors that are nonetheless not "OK": it
generally means "finished" or "not found." FAIL is for errors that happen
outside the bounds of a subsystem.
-
int HFPage::available_space(void)
This routine should return the amount of space available for a new record
that is left on the page. For instance, if all slots are full and there
are 100 bytes of free space on the page, this method should return (100 -
sizeof(slot_t)) bytes. This accounts for the fact that sizeof(slot_t)
bytes must be reserved for a new slot and cannot be used by a new record.
-
bool HFPage::empty(void)
Returns true if the page has no records in it, and false otherwise.
Handing in Your Code
Use hsp to hand in the entire directory containing your code. Do not submit
the individual files, but rather submit the directory as a whole. For example,
if I am sitting in the directory above BufMgr, I would execute the following
command:
hsp musicant CS395 HFPage
Good luck!