1. Due Date

Complete lab: Due by 11:59 p.m., Saturday, October 31, 2020.

Checkpoint: Wednesday, October 21 by noon.

Your lab partner for Lab 3 is listed here: Lab 3 lab partners

Our guidelines for working with partners: working with partners, etiquette and expectations

2. Overview

In this lab you will implement the SwatDB HeapPage class for storing a page of variable-sized records. This is a part of the File Management layer of SwatDB implements that the abstraction of heap file (an unordered collection of records). For this lab you will implement a HeapPage for storing one page of records in a heap file.

The primary goal of the SwatDB lab assignments is to gain an understanding of the details of how a relational DBMS works by implementing and testing parts of a relational DBMS. The SwatDB code base is quite extensive and will require significant reading of the documentation (see Section 3).

2.1. Lab Goals

The main goals of the SwatDB Heap Page Lab are:

  • Understanding the structure of a page of a DBMS heap file, and details of implementing its interface for records on the page.

  • Managing variable-length records.

  • Learning to manage and manipulate low-level data structures in C++, and mapping types onto raw bytes of memory.

  • Developing a thorough testing methodology for a large system.

  • Understanding the role of abstraction in large systems.

  • Practice working with part of a large code base, much of which you have access to only through its interface definition (i.e., .h files and generated interface documentation).

2.2. Starting Point Code

Find your git repo for this lab assignment off the GitHub server for our class: cs44-f20

Here are some detailed instructions on using git for CS44 labs.

Clone your git repo (Lab3-userID1-userID2) containing starting point files into your labs directory:

cd ~/cs44/labs
git clone [the ssh url to your your repo]
cd Lab3-userID1-userID2

If all was successful, you should see the following files (highlighted files require modification):

Lab 3 Files

  • Makefile - pre-defined. You may edit this file to add extra source files or execution commands.

  • README.md - some directions about how to compile and run test programs for the HeapPage.

  • heappage.h - the SwatDB HeapPage class, and related classes and structs. You should not add any new data members to these classes or public methods. You can add private helper methods for good modular code design.

  • heappagescanner.h - the SwatDB HeapPageScanner class. Defines an object for scanning (or iterating) over records on a HeapPage. Its main method is getNext.

  • heappage.cpp - the SwatDB HeapPage class implementation. Most of the code you implement will be in this file. All methods defined in heappage.h should be implemented here. Make sure to include good function comments in the this file too (function comments in .h files alone is not sufficient). For any missing functions, start by copying and pasting function comments from the .h file into here. Then, modify the comments to provide information to a reader of the C++ implementation).

  • heappagescanner.cpp - the SwatDB HeapPageScanner class implementation. You will implement some methods of this class in this file.

  • unittest.cpp - unit testing code for HeapPage. We are not giving you many unit tests with this lab. Instead, use this file as a starting point for adding more testing of your implementation. Use the design of the tests in this file as an example for how to add others.

  • checkpt.cpp - unit testing code for passing the checkpoint.

  • sandbox.cpp - another way to test your code. This is a more application code style vs. using the unit-test infrastructure. You can use this to add your own testing code. This is meant to complement the unit tests to help with implementation, debugging, or designing new tests.

2.3. Deliverables

The following will be evaluated for your lab grade:

  • The HeapPage class in in heappage.cpp file. This is the primary file in which you will add code. The class and struct definitions to implement are defined in the heappage.h file.

  • The HeapPageScanner class in in heappagescanner.cpp file. This class implements a scanner object (or iterator) over the records on a HeapPage. You will implement some of this class' methods. The class and struct definitions to implement are defined in heappagescanner.h.

  • The class definition in heappage.h. Only add private helper methods to class definitions to support good modular design of your solution. Do not add public methods or data members to any classes or structs defined in this file.

  • The class definition in heappagescanner.h. Only add private helper methods to class definitions to support good modular design of your solution. Do not add public methods or data members to the class definition.

  • The sandbox.cpp and unittests.cpp are two programs for testing the HeapPage implementation.

    You must add code to one or both to fully test your solution. Code you add should be well commented, clearly explaining the specific HeapPage functionality it tests.

  • checkpt.cpp contains the set of unit tests for the checkpoint.

  • Your Lab 3 Questionnaire to be completed individually (This will open on the due date and close after 3 days)

2.4. Checkpoint

Before the checkpoint due date, you should complete HeapPage functionality to pass all the unit tests in the checkpt program. While we recommend dealing with exceptions as you implement the methods, we will not require that all exceptions are implemented for the checkpoint.

The checkpoint functionality includes:

  • Much of insertRecord functionality.

  • All other HeapPage methods fully implemented except for deleteRecord and updateRecord.

Much of the functionality of insertRecord should be implemented for the checkpoint. However, because delete and update are not part of the checkpoint, you only need handle the case when the inserted record adds a new slot to the end of the slot directory (there will be no unused slot in the slot directory because there are not deletes or updates from the page).

3. SwatDB

In this assignment you will implement just the HeapPage part of a heap file, implemented by the File Management layer of SwatDB. Because the HeapPage is one page of a larger heap file, this lab assignment does not require interacting with other layers of SwatDB — it is all contained within the File Management layer.

For information about SwatDB, including a link to its on-line code documentation, see this page:

SwatDB documentation that will be particularly helpful for this lab includes:

  • The Page Class defines that base class for all pages in the system.

    • Its getData method provides access to the raw page data: the PAGE_SIZE bytes of memory space for a page.

    • The HeapPage class is a subclass of Page class.

    • All derived classes of Page map their specific structure on top of the page data. All pages in the system must be PAGE_SIZE bytes. This means that no derived class of Page can add additional data methods, they can only map structure on top of the raw page data.

  • The Data class is a simple structure that we will use to store record values. Many HeapPage methods use this class for their parameters; understand its method functions to know how to access information about a record to insert, or how to set information for a record to copy off the page.

  • Type and constant definitions in swatdb_types.h

  • The Exceptions classes defined at the HeapFile, BufferManager and DiskManger layers in exceptions.h that you may need to catch or throw. Check the method function comments in heappage.h and heappagescanner.h to see if a particular method needs to throw an exception(s). Look at the SwatDB documentation for the exception classes, and look at the SwatDB info page for examples of how to throw and catch exceptions.

4. Lab Details

The HeapPage class is defined in the heappage.h header file and the HeapPageScanner class is defined in the heappagescanner.h header file. Both are part of the starting point code with your lab repo. Open these files in an editor to read their contents:

vim heappage.h
vim heappagescanner.h

If you prefer, you can access this information using SwatDB on-line documentation: heappage.h, and heappagescanner.h, Note: there may be some extra features in the online documentation that you are not responsible for implementing. The .h versions with the starting point code are the versions you are responsible for implementing.

4.1. Implementation Overview

You will implement the heap page part of a heap file in SwatDB. This entails completing the implementations of the HeapPage and HeapPageScanner classes. You will also implement many more tests in unittests.cpp than in the previous lab. These tests should test your solution for both correctness and robust error handling. The testing part is described in more detail in the Testing your code section.

The heap page supports variable length records. Its structure is very similar to the one we talked about in class for storing variable length records, except that the slot directory and the compacted records are at opposite ends of the page, as shown in this figure:

heappage
heappage linear
Figure 1. Two equivalent views of the Heap Page layout. Top: meta data at the top, then slot directory grows into free space on the page from the top down. Compacted records at the bottom of the page grow into free space from the bottom up. Bottom: linear view showing the meta data at the beginning of the data array, then the slot directory (growing right) and compact records at the end of the array (growing left).

The HeapPage class is derived from the SwatDB Page Class. The Page class is the common unit of storage in the system (as seen with the Buffer Manager and Disk Manager from Lab 2): every file and index consists of a set of Page data and metadata. The Page class implements a thin class interface around the raw page-sized shunk of storage space, declared as an array of PAGE_SIZE bytes:

char data[PAGE_SIZE];

4.1.1. Slides from Wednesday lab week 6

Here are the slides from Week 6 lab about type casting

type casting HeapPage structure on top of Page data

4.2. HeapPage and type re-casting

HeapPage, like all type-specific pages in SwatDB, is a subclass of the Page base class. It adds heap page structure on top of the bytes of raw data inherited from Page and adds heap-specific methods. However, it must not add additional data members to the Page base class; any additional data members would increase the total number of bytes in the derived class, but every Page in the system must have exactly the same number of bytes (the number of bytes declared in the Page class’s data array).

You’ve used re-casting when reading and writing bytes from a binary file into program memory space. In this lab, you will do something similar, but you will be recasting struct types into the page-sized chunk of memory space (the data array). Section 7 shows some examples of this kind of type casting. We provide two functions implementations (_getPageHeader, and _getSlotDirectory) that do some of the re-casting that you will need, but you may need to add similar code in other parts of your solution: (more details about both in Section 4.3).

4.3. HeapPage Class

In heappage.h are two struct definitions that define HeapPage meta data and slot directory entries. These are the heap page-specific metadata structure that is mapped onto the underlying Page data bytes for a heap page.

The heap page (shown in [HeapPageFig]) is organized so that:

  1. at the very beginning of the page is the meta data about the heap page contents, that are stored in a struct HeapPageHeader (mapped into the start of the Page data)

  2. immediately following this is the slot directory, which is a contiguous series of struct SlotInfo elements (or, equivalently, an array of SlotInfo elements). The number of entries in the slot directory grows and shrinks as the result of record inserts and deletes.

  3. record data are compacted at the end of the Page and is filled in from back to front. So that the very first record inserted at the page fills the very last bytes of the Page data.

  4. the current free space on a pages is between the last allocated slot in the slot directory and the start of the compacted records at the bottom of the page.

4.3.1. Type mapping methods

In heappage.cpp we give you the following implemented private HeapPage methods that do some of the recasting of struct types onto the heap page data:

  • _getPageHeader: returns a pointer to the HeapPageHeader part of the page (returns a HeapPageHeader *).

  • _getSlotDirectory: returns a pointer to the start of the slot directory in the page (returns a SlotInfo * to the first slot).

4.3.2. HeapPage interface methods

You need to implement the following methods that are interface functions to a HeapPage:

  • initializeHeader: called when a new heap page is allocated in the file. The method should initialize the header part of the HeapPage to initial values indicating an empty page.

  • setNext: sets the next_page field in the header part of the heap page to the passed PageNum value.

  • setPrev: sets the prev_page field in to the passed PageNum value.

  • getNext, getPrev: returns the PageNum value of the next_page or prev_page in the header part of the heap page.

  • getFreeSpace: returns the total amount of free space i.e., the total number of bytes of available space for storing record data. If the slot directory would need to grow to insert a record, then the space for growing the slot directory (sizeof(SlotInfo)) should be subtracted from the amount of free space returned (to account for extra space occupied by a new slot if another record is added). If there is not enough free space to add a new slot in this case, then the function should return 0.

  • isFull: returns true if the page is full (i.e. no additional record of any positive size could be inserted).

  • isEmpty: returns true if the page is empty (there are no records) and false otherwise.

  • insertRecord inserts the passed record record on the page. It throws an InsufficientSpaceHeapPage exception if the there is not enough space on the page to insert the record. A successful insert will leave all records on the page compacted at the end, and will reduce the expanse of free space on the page.

    See the the Data Class documentation, for how to access information about the record to insert, including it size and contents. The getData and getSize methods may be particularly useful.

    To copy the data from the record into the page data, the memcpy function may be useful. See the Section 7 for more information about memcpy.

    The record data to insert is passed by pointer to this function through a Data object. The bytes of the record data to insert are in its data field, and should be copied into the page ensuring that the result leaves all records on the page compacted at the end of the page. If the passed size of the data object is 0, this method throws an EmptyDataHeapPage exception.

    To successfully insert a record on the page, there needs to be enough space to insert the record. In some cases the record can be inserted without growing the slot directory, and in others a new slot entry needs to be added to insert the record data. If the record cannot be inserted, but sure that the page is being left in a consistent state before throwing the exception.

    This is a non-trivial method to implement. We encourage you to start by applying some top-down-design, to come up with steps and cases to consider. You also may want to add some private helper functions to ensure good modular design. Here is a start of some of the steps to take:

    1. Determine if the passed record data are non-zero in length or not.

    2. Determine if there is enough space to insert the record data.

    3. If there is enough space to insert the record data, then find a slot into which the record will be inserted (it may be an unused existing slot, or you may need to grow the slot directory by one slot to insert this record).

    4. Determine where into the Page the record data need to be copied to ensure that the insert leaves all records compacted.

    5. Copy the record data from the record_data into the page.

    6. Update state in the Page’s HeapPageHeader and slot directory of SlotInfo structs to reflect that this page has been inserted.

    The last three steps should be performed by a helper function _insertRecord

  • _insertRecord: this is a helper function to insertRecord and updateRecord. It takes a SlotId value into which to add the record on the page and a pointer to the record Data to insert. The caller needs to make sure the slot is a valid slot in the slot directory (possibly growing the slot map to create a new one before calling this method). This method:

    1. inserts the record data on the page in the given slot number,

    2. updates the Page’s freespace to reflect the insert.

    3. updates the record’s slot map entry to reflect the insert.

  • getRecord: get the record indicated by the passed SlotId value. If the SlotId is invalid or out of range, this method throws an exception. If the slotId is valid, the Data object passed by pointer to this method should be set to the requested record data and size. This method needs to copy the record data from the page into the passed Data object’s data field. See the the Data Class documentation, The getData and setSize and getCapacity methods may be particularly useful.

  • deleteRecord: if the passed SlotId value is a valid record on the page, delete the record from the page. If not, throw an InvalidSlotIdHeapPage exception. A successful delete will grow the total expanse of free space on the page, and will leave all remaining records compacted at the bottom of the page. The slot directory may shrink on a delete, and multiple fields in the page’s HeapPageHeader are updated; which fields, and how many, depend on where the deleted record was in the set of compacted records on the page.

    Here are some of the big steps deleteRecord must take (you need to refine these):

    1. Determine if the passed SlotId is valid or not.

    2. Compact all records on the page by moving all of those that are between the current end of the free space and the the removed record; this should fill in the fragment of free space the "deletion" leaves. For each of these records:

      1. move the record data over to fill in the space left by "removing" the deleted record data from the page.

      2. update its slot directory entry appropriately to reflect its new location in the page.

    3. Update the free space on the page.

    4. Update all metadata on the page that needs to be updated, including making sure that the deleted record’s entry in the slot directory is set to INVALID_SLOT_OFFSET.

    5. Determine if the slot directory can shrink, and shrink it by the amount that it can. Recall from lecture that if there are unused slots at the end of the slot directory, we should shrink the slot directory so there is more free space.

    This is the most difficult method to implement. The core of this method, the main deletion and compaction parts, should be performed by a helper method _deleteRecord described below. _deleteRecord should be called after the slot id is verified as correct. It performs most of delete, including the record compation, except it doesn’t perform the final step of possibly shrinking the slot directory.

    The most difficult part to get correct is the compaction (that you will implement in _deleteRecord). Read through its details below. Also, implement and test delete incrementally—​first make sure it works for the case when no compaction is needed, then add in compaction.

  • _deleteRecord: this is a helper function to deleteRecord and updateRecord. It takes a SlotId value of the record to delete. The caller needs to make sure the slot is a valid slot in the slot directory. _deleteRecord does not shrink the slot directory.

    This method:

    1. deletes the record from the page

    2. compacts remaining records on the page

    3. updates the free space to reflect the deletion.

    4. updates the record’s slot entry to reflect the delete (sets its offset to INVALID_SLOT_OFFSET.

    This is the most complicated method to implement. We advise you apply some top-down design first to come up with an algorithm for delete, then implement it and test it in parts (or cases). Also, read the _deleteRecord method function comments closely too.

    The most difficult part to get correct is the compaction. It is important that you move remaining records to their new position on the page in the correct order so that you do not overwrite, and lose, valid record data in the process. We encourage you to start by working this out on paper drawing some examples, then writing up the detailed pseudo code steps, then coding.

    Records must all be compacted at the bottom of the heap page. If the deleted record is not the very first record following the extent of free space on the page, the remaining records between the current free space and this deleted record need to be compacted (moved to later on the page). Compacting records involves copying record contents from one location to another on the page, and updating the record’s slot entry.

    The memmove function may be useful. See the Section 7 and the man page for this function for more information.

    Implement and test functionality incrementally: first make sure you have delete working for the case when no compaction is needed, then add in compaction.

  • updateRecord: updates the record identified by the passed SlotId value.

    In general, an update changes the size of the resulting record. Thus, it can fail if the page cannot store the size of the updated version of the record. In this case, the update should fail with an exception and not modify the page contents (the original record should remain on the page as it was).

    If there is enough space for the updated record on the page, then you should always implement an update as:

    1. delete the old version of the record from the page without shrinking the slot directory (call _deleteRecord to do all/most of this for you).

    2. then insert the new version of the record on the page in its same slot (call _insertRecord to do all/most of this for you).

While this method may seem complicated, properly following the modularity requirements above (in particular, with _insertRecord and _deleteRecord) will greatly assist in keeping your implementation simple. Note that if done properly, update may result in the new version of the record being in a different location on the page than the original. However, the SlotId of the record should be the same before and after the update.

4.3.3. HeapPage debugging methods

There are several methods already implemented that you can use for debugging purposes only. See the sandbox.cpp file for some examples of their use, you can also call these from gdb or use them in debugging printout in unittest.cpp.

Search for THIS METHOD IS FOR DEBUGGING ONLY in their comments to find them in the file.

4.4. HeapPageScanner Class

HeapPageScanner is a friend class of HeapPage, meaning it can directly access its private data members and methods.

It implements methods to scan, or iterate, over the valid records in a HeapPage. It scans in slot number order, starting with the record in slot 0. It is defined in heappagescanner.h, and you will complete its implementation in heappagescanner.cpp.

Its constructor takes a HeapPage to scan, and it has two methods that implement scanning functionality over the records of the page. You will implement its two main methods:

  1. getNext returns the SlotId of the next valid record on the page, or INVALID_SLOT_ID if the end of the page has been reached.

  2. reset resets the scanner to the passed HeapPage, it should start the scan of this page at slot 0. The passed page could be the same one it is currently scanning or a different page. This method does not need to do anything differently in these two cases.

4.5. Exceptions

For information about how to throw and catch different SwatDB exception objects, look at the Exceptions Section of the SwatDB information page. You will need to think carefully about the cause of these exceptions in order to know how to handle them. Use the method function comments @throw as a guide for which exceptions methods may need to throw or pass through, and to help you think about some of the error conditions your code may need to check for and handle appropriately.

5. Lab Requirements

In addition to completing the implementation of the HeapPage class and adding many more tests to unittest.cpp, you should also:

  • Declare and use variables of the types defined in swatdb_types.h as opposed to their underlying type definition. Also use constants and enum types defined in this file - they help make the code more readable. For example, if a method returns a FrameId, declare a variable of type FrameId rather than std:uint32_t or int to store its return value:

    FrameId frame_num;
PageId  pg_id;

//get returns a FrameId, storing it as an int compiles but loses valuable
// information about the purpose of frame_num
frame_num = buf_map->get(pg_id);

  • Write good C++ code design, and good modular design in your solution. This includes using defined constants and types.

  • Ensure you code is robust to errors, in particular, be sure to test for error handling for exceptions that should be thrown and caught by the buffer manager.

  • Ensure your code is free of valgrind errors.

  • Make sure your code is well-commented, and there is no line wrapping. (See our C++ Style guide link from the Handy Links section).

  • Your submitted code should have all of our TODO comments removed…​as you implement a TODO, remove it. These are also helpful to find parts of the given code that you need to implement.

6. Testing your code

There are three test files in the starting point code:

  • checkpt.cpp: unit tests for the checkpoint

# run all of the checkpt test suites
./checkpt
# or you can run individual test suites alone using -s testSuiteName
./checkpt -s X    # run just the X test suite
# to list the test suites names run with -h
./checkpt -h

  • sandbox.cpp: some heappage test code written in a more programatic way than the unittest framework.

  • unittest.cpp: the start of a set of unit tests for the heap page. You are required as part of this lab to develop more unit tests that you must add in this file

You may use any or all of these to start your HeapPage implementation, but you will need to use all of them to verify you program is working correctly. sandbox.cpp and checkpt.cpp are useful for testing early on.

6.1. Required Unit Tests

The unittest.cpp implements some Heap Page test code using the unit tests framework from CS35 (as does checkpt.cpp). You must add additional tests to unittest.cpp by following the code examples in this file to help you structure your code.

unittest.cpp contains a very incomplete set of test functions. Use this file to add tests beyond those tested by the checkpt.cpp. In particular:

  1. tests for deleteRecord

  2. tests for updateRecord

  3. tests for complete insertRecord

  4. stress testing exceptions

  5. tests for really testing correctness of insert and delete (think about edge cases here)

In unittest.cpp are two empty test suites into which you can add your test code:

/*
 * An empty SUITE for to add some heappage tests.
 */
SUITE(studentTests1){
  //TODO: add tests
}
/*
 * An second empty SUITE to add additional tests.
 */
SUITE(studentTests2){
  //TODO: add tests
}

You are welcome to add additional test suites beyond these two, and it will make your testing easier if you do. Follow the same structure as these and the other test SUITES in this file to do so.

sandbox test program

sandbox.cpp is a more programatic way of designing test code. It includes an example of calling some of the HeapPage debugging functions that are already implemented for you in the starting point of heappage.cpp. Read the code in this file to understand what it is doing, and add your own tests that follow this model to test a sequence of operations on your buffer manager.

cleaning up corrupted files SwatDB maintains several files to allow for persistent storage of data. While that is not a central feature of this lab, a consequence of a program crash is that temporary files do not get properly cleaned up since the DBMS did not shutdown cleanly. This can cause problems when you try to rerun the program, so you will need to clean this up. Use the two options below:

./cleanup.sh

make clean     # or make clean also runs cleanup.sh then just re-build
make

7. Tips and Hints

The following are some tips to help you implement the HeapPage:

  • Run checkpt and unittests often to see which tests you are passing and which fail. This will help you find missing functionality in your code, and some missing cases. NOTE: unlike the previous lab, these tests are nowhere near complete. You are required to develop more tests as part of this lab.

  • Implement and test incrementally. Here is a suggestion for an order in which to implement HeapPage functionality:

    1. initializeHeader

    2. setNext, setPrev, getNext, getPrev

    3. getFreeSpace

    4. isFull, isEmpty

    5. insertRecord for the case when the newly inserted record is always inserted by adding a new slot to the slot directory (i.e. there are no deleteRecords)

    6. getRecord

    7. HeapPageScanner: getNext and reset

    8. deleteRecord for the case when no compaction is needed

    9. insertRecord after a delete record

    10. deleteRecord with compaction

    11. updateRecord

    12. really stress test lots of insert, delete and update cases

  • Refer to Wednesday in-lab code examples for C++, gdb, and valgrind reminders.

  • Copying the some bytes of memory from one location to another. Bytes of memory can be copied one at a time from one location to another using a for loop. For example, to copy size bytes from the middle of buffer of char to the end you could do something like the following:

    char buffer[10];
for(int i = 0; i < 5; i++) {
   buffer[i] = buffer[i+5];
}

    or similarly using pointers:

    char buffer[10], *src, *dest;
src = &(buffer[5]);   // src gets address of the 5th bucket
dest = &(buffer[0]);  // src gets address of the 0th bucket
for(int i = 0; i < 5; i++) {
   *dest = *src;   // an aside: this is equivalent to dest[i] = src[i]
   dest++;    // make dest point to the next char storage location
   src++;
}

    (and the source and destination don’t have to be within the same array like this example)

    You can also do this using C string library (string.h) functions that perform this type of byte by byte memory copy. The memcpy, memmove functions are useful for copying the contents of memory of from some source location to another. Both take the source address, destination address, and the number of bytes to copy (or move) from the source location to the destination location:

    memcpy(void *dest, const void *src, size_t n);
memmove(void *dest, const void *src, size_t n);

    A call to these functions, using the example variables initialed from above, might look like this:

      memcpy(&(buffer[0]), &(buffer[5]), 5);
  // or (this does same copy as above)
  memcpy(dest, src, 5);

  // can recast argument's type to (void *) if compiler gives warning
  // about their type being (char *) and not (void *)
  memcpy((void *)(&buffer[0]), (void *)(&buffer[5]), 5);
  memcpy((void *)(dest), (void *)(src), 5);

    See the man page for more information about both functions:

    man 3posix memcpy
man 3posix memmove

  • Remember the & operator returns the address of its argument (this is C-style operator, not & used to specify reference parameter types in C++). Its argument must be an lvalue (a storage location, such as the name of a variable or an array bucket). For example, to get the address of the 3rd bucket in and array of ints:

    int array[20];

    you would use the & operator like this (in this example I’m assigning its value to an int * variable):

    int *ptr;
ptr = &(array[3]);

  • Recasting types on top of memory space. As in Lab 1, you will need to manage raw memory (i.e., char arrays) directly using type casting. We have provided two HeapPage with examples of how this is done for the HeapPage data: _getPageHeader() and _getSlotDirectory(). You should understand what these methods are doing as you may need to do something similar in other methods that you are implementing. These methods are recasting types on top of char arrays, similar to how you cast types onto files for Lab 1.

    As a simpler example of the kind of type casting you may need to do, consider the following struct type definition and variable declarations from some program:

    struct Point {
   int x;  // the x-coordinate
   int y;  // the y-coordinate
};

int main() {

  char buffer[100];
  struct Point my_point, *ptr;
  int x_val;

    Assume that we want to map a bunch of struct Points on top of the buffer. Then to add Point value (30, 50) as the 3rd Point in the buffer, we could do this:

       ptr = (struct Point *)(buffer + sizeof(struct Point)*2)
   // buffer: base address of the buffer array in memory
   // sizeof(struct Point)*2): offset from buffer start is 2 struct Points
   // (struct Point *): re-cast the address to be a pointer to a Point

   // ptr is address of 3rd Point object in buffer.  We treat ptr as a Point,
   // not a char. Dereference this location to store values:
   ptr->x = 30;
   ptr->y = 50;

    If we want to get the value of the fifth Point in buffer, we could do this:

       // pointer to the offset into buffer where the start of
   // the 5th Point maps:
   ptr = (struct Point *)(buffer + sizeof(struct Point)*4);

   // dereference ptr to get the x and y values
   x_val = ptr->x;

8. Submitting your lab

Review the lab deliverables to ensure you have completed all of your work. Before the due date, push your solution to github from one of your local repos to the GitHub remote repo.

From your local repo (in your ~/cs44/labs/Lab3-userID1-userID2 subdirectory)

make clean
git add *.h *.cpp
git commit -m "my correct and well commented solution for grading"
git push

Verify that the results appear (e.g., by viewing the the repository on cs44-f20). You will receive deductions for submitting code that does not run or repos with merge conflicts. Also note that the time stamp of your final submission is used to verify late days, so please do not update your repo until after the late period has ended.

If that doesn’t work, take a look at the "Troubleshooting" section of the Using git for CS44 labs and the Using git pages. At this point, you should submit the required Lab 3 Questionnaire (each lab partner must do this).

9. Handy References