0.3. Project 1¶
0.3.1. General Project Rules¶
You must use Eclipse IDE, and you must use it to submit to Web-CAT. We won’t accept submissions any other way.
There are 4 projects during the semester, each has a 3-4 week lifecyle.
Each has three milestones, so about one/week.
P1’s first milestone is really easy (make minor changes to the starter kit and submit to Web-CAT), and is due at 11pm on Wednesday, January 28.
A major part of the project score is based on correctness, as defined by passing the reference tests at Web-CAT. We won’t tell you a lot of detail about what is in the reference tests.
The “correctness” score is adjusted by the quality of your own test suite (as defined by Mutation Testing coverage — we will discuss this in detail later).
0.3.2. Project 1: Songs Database¶
Background:
You are implementing a database of Song Title/Artist pairs.
Each song title is a string, each artist is a string.
There are separate hash tables for the song titles and the strings.
The hash table does not actually store strings. Strings are stored in a memory manager.
You will implement:
A hash table (we give you the hash function)
A memory manager (using the buddy method)
Communications between them (a Handle)
0.3.3. What We Give You: The Starter Kit (1)¶
Starter kit is accessed through Eclipse Project -> Download Assignment
We specify the class name for the project (SongsProj), an interface that you must implement (Songs), and the name of a class that implements the Songs interface (SongsDB).
This lets us write reference test cases for grading that make calls to the interface.
Our reference tests do not write to System.out, nor check the contents of System.out.
We give you the hash function to use in the starter kit.
0.3.4. What We Give You: The Starter Kit (2)¶
We give you some initial tests (SongsTest) that are meant to demonstrate all the requirements related to formatting the interface method return values.
Note: The starter kit does not pass those tests.
If we get questions indicating that we left something ambiguous, we will update the example tests for you to see.
Important service: We will check any tests added to SongsTest.java against the reference implementation. This lets you verify that your tests are correct (meaning, that you have no misconceptions about the project requirements — if your tests are thorough).
0.3.5. Design Issues¶
In all projects, a major part of the design is handling proper information encapsulation and flow
The hash table does not store strings. The memory manager does.
How do the hash table and memory manager communicate?
Through a Handle.
The Handle encapsulates what the memory manager needs to know to recover a string out of its memory.
The hash table stores the handle in a given slot. Whenever there is a reason to know what the associated string is, the hash table passes that to the memory manager.
0.3.6. What you need to know about Hash Tables¶
You should briefly skim Chapter 10 for now (we will cover this chapter in detail later in the semester). Focus on the following three things:
Insertion is pretty standard. You will be hashing a string (song or artist name). You will use the hash function we give you in the Starter Kit (see 10.3.3 String Folding).
You will use Quadratic Probing for collision resolution. See 10.7.3.
You will use Tombstones on deletion. See 10.9.
0.3.7. Insert/Delete¶
Warning: This example is NOT using quadratic probing!
0.3.8. Quadratic Probing¶
0.3.9. What you need to know about memory management¶
You should briefly skim Chapter 11 for now (we will cover this chapter in more detail later in the semester).
Carefully read 11.1.
Read 11.9.1.1 Buddy Methods. This is what you will implement.
0.3.10. Memory Management¶
Problem: Records (of various lengths) need to be stored.
Model: A big array of space to store them, managed by a memory manager.
Like a coat-check stand, give them your coat, get back a ticket. Later, return the ticket for your coat.
We call the ticket a handle.
0.3.11. Memory Manager ADT¶
You do NOT necessarily implement exactly this interface! This is just meant to get the idea across.
// Memory Manager abstract class
interface MemManager {
// Store a record and return a handle to it
public MemHandle insert(byte[] info);
// Release the space associated with a record
public void release(MemHandle h);
// Get back a copy of a stored record
public byte[] getRecord(MemHandle h);
}
0.3.12. Implementation Issues¶
The client doesn’t know what is in the handle.
The memory manager doesn’t know what is in the message. It should not even know that it is a string!
Multiple clients can share a memory manager. (The two hash tables do in this project.)
The client decides what gets stored
The memory manager decides where things get stored
0.3.13. Buddy Method¶
The memory pool is a power of 2 in size
Memory allocations are always the smallest power of 2 equal to or bigger than the request
Free (and allocated) blocks are therefore always a power of 2
Keep a list for each block size
Easy to merge freed blocks (that is the point to the buddy method)
This is done by matching the bits in the start address, buddies are identical other than the bit for their size.
