Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Inform the compiler that this included module is written in C instead of C++.
- extern "C" {
- #include "hash_table.h"
- }
- #include "gtest/gtest.h"
- // Use the TEST macro to define your tests.
- //
- // TEST has two parameters: the test case name and the test name.
- // After using the macro, you should define your test logic between a
- // pair of braces. You can use a bunch of macros to indicate the
- // success or failure of a test. EXPECT_TRUE and EXPECT_EQ are
- // examples of such macros. For a complete list, see gtest.h.
- //
- // <TechnicalDetails>
- //
- // In Google Test, tests are grouped into test cases. This is how we
- // keep test code organized. You should put logically related tests
- // into the same test case.
- //
- // The test case name and the test name should both be valid C++
- // identifiers. And you should not use underscore (_) in the names.
- //
- // Google Test guarantees that each test you define is run exactly
- // once, but it makes no guarantee on the order the tests are
- // executed. Therefore, you should write your tests in such a way
- // that their results don't depend on their order.
- //
- // </TechnicalDetails>
- // The #define directive defines a constant value that can be accessed throughout
- // your code. Here it defines the default number of buckets in the hash table.
- // You can change this number, but make sure to update the hash function with
- // the right algorithm to compute the indices for buckets.
- // For example, if the BUCKET_NUM is set to 5, the hash function should map a
- // positive number to an integer between 0 and 4.
- #define BUCKET_NUM 3
- // Dummy value to store in hash table entry
- // Please beware that any type of data (e.g. int, double, struct and etc.) can
- // be stored in hash table for testing your hash table. Only the pointer to
- // the data will be stored in the HashTableEntry.
- struct HTItem {};
- // Helper function for creating a lot of dummy values.
- void make_items(HTItem* result[], unsigned n)
- {
- // Populate the array with pointers to the dummy values.
- while(n--)
- {
- result[n] = (HTItem*) malloc(sizeof(HTItem));
- }
- }
- // A simple hash function that maps a positive number to an integer between 0~(BUCKET_NUM-1).
- unsigned int hash(unsigned int key) {
- return key%BUCKET_NUM;
- }
- ////////////////////////
- // Initialization tests
- ////////////////////////
- TEST(InitTest, CreateDestroyHashTable)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- destroyHashTable(ht);
- }
- ////////////////
- // Access tests
- ////////////////
- TEST(AccessTest, GetKey_TableEmpty)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // Test when table is empty.
- EXPECT_EQ(NULL, getItem(ht, 0));
- EXPECT_EQ(NULL, getItem(ht, 1));
- EXPECT_EQ(NULL, getItem(ht, 2));
- // Test with index greater than the number of buckets.
- EXPECT_EQ(NULL, getItem(ht, 10));
- destroyHashTable(ht);
- }
- TEST(AccessTest, GetSingleKey)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // Create list of items
- size_t num_items = 1;
- HTItem* m[num_items];
- make_items(m, num_items);
- insertItem(ht, 0, m[0]);
- EXPECT_EQ(m[0], getItem(ht, 0));
- destroyHashTable(ht); // dummy item is also freed here
- }
- TEST(AccessTest, GetKey_KeyNotPresent)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // Create a list of items to add to hash table.
- size_t num_items = 1;
- HTItem* m[num_items];
- make_items(m, num_items);
- // Insert one item into the hash table.
- insertItem(ht, 0, m[0]);
- // Test if the hash table returns NULL when the key is not found.
- EXPECT_EQ(NULL, getItem(ht, 1));
- // Destroy the hash table togeter with the inserted values
- destroyHashTable(ht);
- }
- TEST(AccessTest, GetTwoKeys_DifferentBuckets)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // Create a list of items to add to the hash table
- size_t num_items = 2;
- HTItem* m[num_items];
- make_items(m, num_items);
- // Insert both items sequentially into the hash table
- insertItem(ht,0,m[0]);
- insertItem(ht,1,m[1]);
- // Read items from bucket in the same way they were added
- EXPECT_EQ(m[0], getItem(ht,0));
- EXPECT_EQ(m[1], getItem(ht,1));
- // Destroy the hash table together with the inserted values
- destroyHashTable(ht);
- }
- TEST(AccessTest, GetTwoKeys_SameBucket)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // Create a list of items to add to the hash table
- size_t num_items = 2;
- HTItem* m[num_items];
- make_items(m, num_items);
- // Insert both items into the same bucket
- insertItem(ht,0,m[0]);
- insertItem(ht,BUCKET_NUM,m[1]);
- // Read items from the bucket in the same way they were added
- EXPECT_EQ(m[0], getItem(ht,0));
- EXPECT_EQ(m[1], getItem(ht,BUCKET_NUM));
- // Destroy the hash table together with the inserted values
- destroyHashTable(ht);
- }
- TEST(AccessTest, GetMultipleKeys_SameBucket)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // Create a list of items to add to the hash table
- size_t num_items = 10;
- HTItem* m[num_items];
- make_items(m, num_items);
- // Use a for loop to insert the items into the same bucket
- unsigned int i;
- for (i=0; i<num_items; ++i){
- insertItem(ht,i*BUCKET_NUM,m[i]);
- }
- // Read items from the bucket in the opposite way they were added
- for(i=num_items; i<=0; --i){
- EXPECT_EQ(m[i], getItem(ht, i*BUCKET_NUM));
- }
- // Destroy the hash table together with the inserted values
- destroyHashTable(ht);
- }
- ////////////////////////////
- // Removal and delete tests
- ////////////////////////////
- TEST(RemoveTest, SingleValidRemove)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // Create a list of items to add to hash table.
- size_t num_items = 1;
- HTItem* m[num_items];
- make_items(m, num_items);
- // Insert one item into the hash table.
- insertItem(ht, 0, m[0]);
- // After removing an item with a specific key, the data stored in the
- // corresponding entry should be returned. If the key is not present in the
- // hash table, then NULL should be returned.
- void* data = removeItem(ht, 0);
- // Since the key we want to remove is present in the hash table, the correct
- // data should be returned.
- EXPECT_EQ(m[0], data);
- // Free the data
- free(data);
- destroyHashTable(ht);
- }
- TEST(RemoveTest, SingleInvalidRemove)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // When the hash table is empty, the remove funtion should still work.
- EXPECT_EQ(NULL, removeItem(ht, 1));
- destroyHashTable(ht);
- }
- TEST(RemoveTest, RemovefromHead)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // Create a list of items to add to the hash table
- size_t num_items = 3;
- HTItem* m[num_items];
- make_items(m, num_items);
- // Use a for loop to insert the items into the same bucket
- unsigned int i;
- for (i=0; i<num_items; ++i){
- insertItem(ht,i*BUCKET_NUM,m[i]);
- }
- // After removing an item with a specific key, the data stored in the
- // corresponding entry should be returned. If the key is not present in the
- // hash table, then NULL should be returned.
- void* data = removeItem(ht, 0);
- EXPECT_EQ(m[0], data);
- // When trying to get Item with the same key, the item is no longer there
- EXPECT_EQ(NULL, getItem(ht, 0));
- // Use a for loop to ensure that the remaining items are untouched and accessible
- for(i=1; i<num_items; ++i){
- EXPECT_EQ(m[i], getItem(ht, i*BUCKET_NUM));
- }
- // free the data
- free(data);
- destroyHashTable(ht);
- }
- TEST(RemoveTest, RemovefromMiddle)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // Create a list of items to add to the hash table
- size_t num_items = 3;
- HTItem* m[num_items];
- make_items(m, num_items);
- // Use a for loop to insert the items into the same bucket
- unsigned int i;
- for (i=0; i<num_items; ++i){
- insertItem(ht,i*BUCKET_NUM,m[i]);
- }
- // After removing an item with a specific key, the data stored in the
- // corresponding entry should be returned. If the key is not present in the
- // hash table, then NULL should be returned.
- void* data = removeItem(ht, BUCKET_NUM);
- EXPECT_EQ(m[1], data);
- // When trying to get Item with the same key, the item is no longer there
- EXPECT_EQ(NULL, getItem(ht,BUCKET_NUM));
- // Use a for loop to ensure that the remaining items are untouched and accessible
- for(i=0; i<num_items; ++i){
- if (i==1){
- continue;
- }
- EXPECT_EQ(m[i], getItem(ht, i*BUCKET_NUM));
- }
- // free the data
- free(data);
- destroyHashTable(ht);
- }
- TEST(RemoveTest, RemovefromEnd)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // Create a list of items to add to the hash table
- size_t num_items = 3;
- HTItem* m[num_items];
- make_items(m, num_items);
- // Use a for loop to insert the items into the same bucket
- unsigned int i;
- for (i=0; i<num_items; ++i){
- insertItem(ht,i*BUCKET_NUM,m[i]);
- }
- // After removing an item with a specific key, the data stored in the
- // corresponding entry should be returned. If the key is not present in the
- // hash table, then NULL should be returned.
- void* data = removeItem(ht, 2*BUCKET_NUM);
- EXPECT_EQ(m[2], data);
- // When trying to get Item with the same key, the item is no longer there
- EXPECT_EQ(NULL, getItem(ht,2*BUCKET_NUM));
- // Use a for loop to ensure that the remaining items are untouched and accessible
- for(i=0; i<(num_items-1); ++i){
- EXPECT_EQ(m[i], getItem(ht, i*BUCKET_NUM));
- }
- // free the data
- free(data);
- destroyHashTable(ht);
- }
- TEST(DeleteTest, DeletefromHead)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // Create a list of items to add to the hash table
- size_t num_items = 3;
- HTItem* m[num_items];
- make_items(m, num_items);
- // Use a for loop to insert the items into the same bucket
- unsigned int i;
- for (i=0; i<num_items; ++i){
- insertItem(ht,i*BUCKET_NUM,m[i]);
- }
- // delete the item and ensure that it is no longer in the hash table
- deleteItem(ht,0);
- EXPECT_EQ(NULL, getItem(ht,0));
- // Use a for loop to ensure that the remaining items are untouched and accessible
- for(i=1; i<num_items; ++i){
- EXPECT_EQ(m[i], getItem(ht, i*BUCKET_NUM));
- }
- // Destroy the hashtable and the inserted values
- destroyHashTable(ht);
- }
- TEST(DeleteTest, DeletefromMiddle)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // Create a list of items to add to the hash table
- size_t num_items = 3;
- HTItem* m[num_items];
- make_items(m, num_items);
- // Use a for loop to insert the items into the same bucket
- unsigned int i;
- for (i=0; i<num_items; ++i){
- insertItem(ht,i*BUCKET_NUM,m[i]);
- }
- // delete the item and ensure that it is no longer in the hash table
- deleteItem(ht,BUCKET_NUM);
- EXPECT_EQ(NULL, getItem(ht,BUCKET_NUM));
- // Use a for loop to ensure that the remaining items are untouched and accessible
- for(i=0; i<num_items; ++i){
- if (i==1){
- continue;
- }
- EXPECT_EQ(m[i], getItem(ht, i*BUCKET_NUM));
- }
- // Destroy the hashtable and the inserted values
- destroyHashTable(ht);
- }
- TEST(DeleteTest, DeletefromEnd)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // Create a list of items to add to the hash table
- size_t num_items = 3;
- HTItem* m[num_items];
- make_items(m, num_items);
- // Use a for loop to insert the items into the same bucket
- unsigned int i;
- for (i=0; i<num_items; ++i){
- insertItem(ht,i*BUCKET_NUM,m[i]);
- }
- // delete the item and ensure that it is no longer in the hash table
- deleteItem(ht,2*BUCKET_NUM);
- EXPECT_EQ(NULL, getItem(ht,2*BUCKET_NUM));
- // Use a for loop to ensure that the remaining items are untouched and accessible
- for(i=0; i<(num_items-1); ++i){
- EXPECT_EQ(m[i], getItem(ht, i*BUCKET_NUM));
- }
- // Destroy the hashtable and the inserted values
- destroyHashTable(ht);
- }
- ///////////////////
- // Insersion tests
- ///////////////////
- TEST(InsertTest, SingleNoOverwrite){
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // Create a list of items to add to the hash table
- size_t num_items = 1;
- HTItem* m[num_items];
- make_items(m, num_items);
- // When an item is not replaced, the insertItem function should return null
- EXPECT_EQ(NULL, insertItem(ht, 0, m[0]));
- // Ensure that we can access the added value
- EXPECT_EQ(m[0], getItem(ht,0));
- // Destroy the hashtable and the inserted value
- destroyHashTable(ht);
- }
- TEST(InsertTest, InsertAsOverwrite)
- {
- HashTable* ht = createHashTable(hash, BUCKET_NUM);
- // Create list of items to be added to the hash table.
- size_t num_items = 2;
- HTItem* m[num_items];
- make_items(m, num_items);
- // Only insert one item with key=0 into the hash table.
- insertItem(ht, 0, m[0]);
- // When we are inserting a different value with the same key=0, the hash table
- // entry should hold the new value instead. In the test case, the hash table entry
- // corresponding to key=0 will hold m[1] and return m[0] as the return value.
- EXPECT_EQ(m[0], insertItem(ht, 0, m[1]));
- // Now check if the new value m[1] has indeed been stored in hash table with
- // key=0.
- EXPECT_EQ(m[1], getItem(ht,0));
- destroyHashTable(ht);
- free(m[0]); // don't forget to free item 0
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement