The total grade for this assignment is 100 points.  The deadline for this assignment is 11:59 PM,  February  20,  2023.   Submissions  after  this  deadline  will  not  be  accepted.   Students are required to enter the UAlbany Blackboard system and then upload a .zip file (in the form of [first name] [last name].zip) that contains the Eclipse project directory and a short document describing:

• any missing or incomplete elements of the code

• any changes made to the original API

• the amount of time spent for this assignment

• suggestions or comments if any

Please note that the above document and the comments in your source code will account for 5 points out of the 100 points.

In this programming assignment, you need to implement a storage manager that maintains a series of data objects in each data file. You first need to install and run Eclipse on your machine and import the“storage manager”project (see Appendix A). Please generate an API document (see Appendix B) and then take a look at that document as well as the source code to familiarize yourself with this assignment.  This assignment provides you with a set of incomplete classes (in particular, see SlottedPage, FileManager, and BufferedFileManager which contain methods currently throwing an UnsupportedOperationException).  You will need to write code for these classes. Your code will be graded by running a set of unit tests and then examining your code (see SlottedPageTest and FileManagerTest which use JUnit1, as well as BufferedFileManagerTest which produces output messages). For details of running these tests, refer to Appendix A. Note that passing unit tests does NOT necessarily guarantee that your implementation is correct and efficient. Please make sure that your code will not cause any problem in other cases not covered by the unit tests. If you have questions, please contact the TA(s) or the instructor ([email protected]). The remainder of this document describes the components that you need to implement.

Part 1. The Slotted Page Structure (65 points)

The slotted page structure allows a storage manager to store variable-length records  (data objects) within a fixed size page (an in-memory copy of a disk block).  Each page is essentially a byte array that stores a header (at the beginning) and data objects (at the end).  The header of a page consists of (1) a 4-byte integer representing the number of entries in the page (one entry for each data object), and (2) a series of 4-byte integers each representing the location where the corresponding data object is stored within the page. Each page has, between its header and data objects, a free space where more data objects and header entries can be added. For further details of the slotted page structure, refer to Section 13.2.2 of the textbook.  Upon a request to delete a data object from a page, the corresponding header entry (for storing the location of that data object within the page) is simply set to -1 to indicate that there is no associated data object (the actual object is NOT necessarily removed from the page).

data[0…3]   data[4…2043]                                                                                     data[2044…2047]

Figure 1: An Empty SlottedPage

data[0…3]   data[4…7]   data[8…2033]                                                        data[2034…2043]    data[2044…2047]

Figure 2: After add("123")

data[0…3]   data[4…7]   data[8…11] data[12…2023]                                                  data[2024…2033]            data[2034…2043]    data[2044…2047]

Figure 3: After add("456")

In this part, you need to implement the following methods (your code needs to pass all of the 5 tests in SlottedPageTest):

• add(Object  o): (20 points) adds the specified object o in a SlottedPage when this method is invoked on that SlottedPage. This method must first save the object o in the free space of the SlottedPage by calling the save(Object  o) method. This save(Object  o) method returns an int value indicating the location at which the object o is saved in the SlottedPage. That int value must be stored at the correct header entry of the SlottedPage so that the saved object o can be accessed in the future. For example, assume that object“123”is saved at location 2034 in the byte array of an empty SlottedPage (Figure 2). Then, the first 4 bytes of the byte array (i.e., the beginning of the header) must store an int value 1 to indicate that there is only one entry in the header (in response to the addition of object“123”). The next

4 bytes of the byte array (i.e., the 0th entry in the header) must store 2034 (i.e., the location at which“123”is saved). When an additional object“456”is saved at location 2024 in the byte array (Figure 3), the first 4 bytes of the header must store 2 (to indicate that there are two entries in the header) and the 1st entry (i.e., the entry after the 0th entry) in the header must store 2024 (i.e., the location at which“456”is saved).  To find the number of entries that the SlottedPage currently has, use the entryCount() method.  To set the number of entries in the header to an int value, use the setEntryCount(int  count) method. To save location loc at the ith entry in the header, call saveLocation(i,  loc).

• get(int  index):  (20 points) returns the object at the specified index in a SlottedPage when this method is invoked on that SlottedPage. For example, get(0) returns the object at index 0 (i.e., the object whose location is stored at the 0th entry in the header) and get(1) returns the object at index 1. Given the SlottedPage in Figure 3, get(0) and get(1) need to return“123”and“456”, respectively. This method must first find the location of the object at the specified index by calling the getLocation(int  index) method. This getLocation(int index) method returns the int value stored at the header entry specified by index (i.e., the index-th header entry).  If that location is -1, meaning that the object was removed from the SlottedPage, then the get(int  index) method needs to return null (e.g., in Figure 5, get(0) needs to return null).  Otherwise, get(int  index) needs to obtain the object by calling the toObject(byte[]  b,  int  offset) method (with offset set to the return value of getLocation(int  index)) and then return that obtained object. If the given index cannot match any of the entries in the SlottedPage (e.g., get(-1)), the method needs to throw an IndexOutOfBoundsException.

data[0…3]   data[4…7]   data[8…11]data[12…15] data[16…2013]               data[2014…2023]            data[2024…2033]            data[2034…2043]    data[2044…2047]

Figure 4: After add("789")

data[0…3]   data[4…7]   data[8…11]data[12…15] data[16…2013]               data[2014…2023]            data[2024…2033]            data[2034…2043]    data[2044…2047]

Figure 5: After remove(0)

• remove(int  index): (10 points) removes the object at the specified index from a SlottedPage when this method is invoked on that SlottedPage.  This method must save -1 at the ap- propriate entry in the header (Figures 4 and 5).  This method must also return the object removed (i.e., the object previously stored at the specified index).  This method must NOT change the first 4 bytes in the header of the SlottedPage. These 4 bytes represent the num- ber of entries in the header (including those containing -1 indicating object removal), not the number of objects remaining in the SlottedPage.

•  iterator(): (10 points) returns an iterator over the objects (excluding those removed) stored  in a SlottedPage when this method is invoked on that SlottedPage. To find the number of entries in the current SlottedPage, use entryCount(). To get the object at each index, call  get(int  index). Note that get(int  index) returns null if there is currently no object at  the specified index due to the deletion of the previous object.  The iterator must skip such  null values.  For example, suppose that objects“123”,“456”, and“789”are added to a  SlottedPage and then object“123”is removed from that SlottedPage (Figure 5).  In this  case, an iterator obtained from that SlottedPage must iterator over only two objects (“456” and“789”). Feel free to add an auxiliary class or data structure for this iterator() method.

•  compact(): (5 points) reorganizes the SlottedPage on which the method is invoked (in order to maximize the free space of that SlottedPage). This method is used by the save(Object

o) method when the object to save cannot fit into the current free space of the SlottedPage. This method needs to move objects at the end of the SlottedPage in a manner that eliminates the space wasted by the objects removed from the SlottedPage (e.g., in Figure 5, the wasted space storing“123”).

Please make sure that your code passes all of the tests in SlottedPageTest.

Part 2. The Basic Storage Manager Implementation (25 points)

In this part, you need to implement, in FileManager .java,  a basic storage manager that maintains a series of data objects in each data file without buffering (i.e., by directly reading/writing SlottedPages from/to data files).  The methods to complete are as follows (your code needs to pass all of the 4 tests in FileManagerTest):

• put(int  fileID,  Long  location,  Object  o): (10 points) puts object o at location location in the file specified by fileID. Here, location has a long-type value, whose first half (4 bytes   corresponding to an integer) represents the ID of the page (e.g., page 0, page 1, etc.)  and   the second half represents the index within the page. For example, put(10,  0x00000001L,

o) stores object o in page 0 of the file whose ID is 10 (i.e., the first disk block in the file) at index 1 within the page.  On the other hand, put(10,  0x00010000L,  o) stores object o in page 1 of the file whose ID is 10 (i.e., the second disk block in the file) at index 0 within the page. Given a long-type argument location, use first(location) to get the ID of the page and second(location) to get the index within the page. After finding an appropriate page p, call put(int  index,  Object  o) on p to put the object in that page and then call the updated(p,  fileID) method of FileManager to indicate that the page p is updated (then the updated(p,  fileID) method of FileManager automatically writes the page to the appropriate data file). If the location argument has an inappropriate value (e.g., its first half refers to page -1), then put(int  fileID,  Long  location,  Object  o) needs to throw an InvalidLocationException.

• get(int  fileID,  Long  location):  (5 points) returns the object at location location in the file specified by fileID.

• remove(int  fileID,  Long  location): (5 points) removes the object at location location from the file specified by fileID.

•  iterator(int  fileID): (5 points) returns an iterator over all objects stored in the the file     specified by fileID. This method needs to use page(int  fileID,  int  pageID) of FileManager and iterator() of SlottedPage. Make sure this method efficiently uses the memory (e.g.,     should NOT put all of the objects in the memory first thereby incurring high space overhead     and then return an iterator over these objects).

Please verify your code using the tests in FileManagerTest.

Part 3. Buffer Management (5 points)

The FileManager class implemented in Part 2 directly accesses data files (i.e., no buffering), causing disk seeks frequently. In this part, you need to implement the BufferedFileManager class so that it extends the functionalities of FileManager in a manner that benefits from buffering (i.e., frequently used pages are kept in memory, making fast read and write operations possible). Furthermore, you need to implement a page eviction policy for the cases where there are too many pages to keep in the main memory. The choice of eviction policy is up to you. It is not necessary to do something sophisticated. Describe your policy in the document that you submit.

When BufferedFileManager is implemented correctly, BufferedFileManagerTest will pro- duce some output as follows (the exact number of reads and writes may vary depending on the buffering strategy; however, there should in general be less reads and writes as the buffer size increases):

buffer   size :   4  pages

1000   additions  %  [{ name : table0 . dat ,   reads :0 ,   writes :38}]

10   removals  %  [{ name : table0 . dat ,   reads :10 ,   writes :48}]

iteration   over   990   elements  %  [{name : table0 . dat ,   reads :52 ,   writes :52}]

shut   down  %  [{ name : table0 . dat ,   reads :52 ,   writes :52}]

buffer   size :   16  pages

1000   additions  %  [{ name : table0 . dat ,   reads :0 ,   writes :26}]

10   removals  %  [{ name : table0 . dat ,   reads :9 ,   writes :35}]

iteration   over   990   elements  %  [{name : table0 . dat ,   reads :48 ,   writes :51}]

shut   down  %  [{ name : table0 . dat ,   reads :48 ,   writes :51}]

buffer   size :   64  pages

1000   additions  %  [{ name : table0 . dat ,   reads :0 ,   writes : 0 } ]

10   removals  %  [{ name : table0 . dat ,   reads :0 ,   writes : 0 } ]

iteration   over   990   elements  %  [{ name : table0 . dat ,   reads :0 ,   writes : 0 } ]

shut   down  %  [{ name : table0 . dat ,   reads :0 ,   writes :42}]

Figure 6: Eclipse

Appendix A. Installing Eclipse and Importing a Java Project

1. Visit:

http://www.eclipse.org/downloads/

2. From the web site, download the eclipse installer (those for Linux, Windows, and Mac OS X are available) and then choose “Eclipse IDE for Java Developers” and install it.

3. After finishing installation, start Eclipse.

4. When Eclipse runs for the first time, it asks the user to choose the workspace location. You may use the default location.

5. In the menu bar, choose “File” and then “Import”.  Next, select “General” and “Existing         Projects into Workspace”. Then, click the “Browse”button and select the“storage manager .zip” file contained in this assignment package.

6. Once the project is imported, you can choose one among SlottedPageTest.java, FileManagerTest.java, and BufferedFileManagerTest.java in the storage .test package and then run it by click-

ing the icon highlighted in Figure 6.