# `given` library
## Team: Group 9 - Invalid Pointer
Members: Samiha Datta, Mer Anderson, Sabrina Jain
GitHub usernames: samihadatta, meranderson, sabrinajain747
Date: March 9th, 2020

## Overview
The `given` library holds useful data structures created to make the algorithm run. It contains the following modules:
* `hashtable` (Hashtable hashes keys to slots (which each contain a set) and stores keys to object pairs in sets).
* `set` (Stores a linked list of key to object pairs).
* `jhash` (Contains a function to hash a string to a constant hashkey).

## Implementation Strategy
#### `hashtable`
We use hashtables to track the avatars moves, store discovered points, and store invalid points.

typedef struct hashtable hashtable_t;
hashtable_t *hashtable_new(const int num_slots);
bool hashtable_insert(hashtable_t *ht, const char *key, void *item);
void *hashtable_find(hashtable_t *ht, const char *key);
void hashtable_print(hashtable_t *ht, FILE *fp, void (*itemprint)(FILE *fp, const char *key, void *item));
void hashtable_iterate(hashtable_t *ht, void *arg, void (*itemfunc)(void *arg, const char *key, void *item));
void hashtable_delete(hashtable_t *ht, void (*itemdelete)(void *item) );

* `hashtable_new` creates a new (empty) hashtable. The caller provides: number of slots to be used for the hashtable (must be > 0). We return: pointer to the new hashtable; return NULL if error. We guarantee: hashtable is initialized empty. Caller is responsible for: later calling hashtable_delete.
* `hashtable_insert` inserts an item, identified by key (string), into the given hashtable. Caller provides: valid pointer to hashtable, valid string for key, valid pointer for item. We return: false if key exists in ht, any parameter is NULL, or error and true iff new item was inserted. Notes: The key string is copied for use by the hashtable; that is, the module is responsible for allocating memory for a copy of the key string, and later deallocating that memory; thus, the caller is free to re-use or deallocate its key string after this call.
* `hashtable_find` returns the item associated with the given key. Caller provides: valid pointer to hashtable, valid string for key. We return: pointer to the item corresponding to the given key, if found; NULL if hashtable is NULL, key is NULL, or key is not found. Notes: the hashtable is unchanged by this operation.
* `hashtable_print` prints the whole table; provide the output file and func to print each item. Caller provides: valid pointer to hashtable, FILE open for writing, itemprint that can print a single (key, item) pair. We print: nothing, if NULL fp. "(null)" if NULL ht. One line per hash slot, with no items, if NULL itemprint. Otherwise, one line per hash slot, listing (key,item) pairs in that slot. Note: the hashtable and its contents are not changed by this function.
* `hashtable_iterate` iterates over all items in the table; in undefined order. Caller provides: valid pointer to hashtable, arbitrary void*arg pointer, itemfunc that can handle a single (key, item) pair. We do: nothing, if ht equals NULL or itemfunc equals NULL. Otherwise, call the itemfunc once for each item, with (arg, key, item). Notes: the order in which hashtable items are handled is undefined. The hashtable and its contents are not changed by this function, but the itemfunc may change the contents of the item.
* `hashtable_delete` deletes the hashtable, calling a delete function on each item. Caller provides: valid hashtable pointer, valid pointer to function that handles one item (may be NULL). We do: if hashtable equals NULL, do nothing. Otherwise, unless itemfunc equals NULL, call the itemfunc on each item. Free all the key strings, and the hashtable itself. Notes: We free the strings that represent key for each item, because this module allocated that memory in hashtable_insert.

#### `jhash`

unsigned long JenkinsHash(const char *str, unsigned long mod);

* `JenkinsHash` is a given function that determines the optimal spot to store an item in a hashtable based on the given key.

#### `set`
Supports hashtable functionality.

typedef struct set set_t;
set_t *set_new(void);
bool set_insert(set_t *set, const char *key, void *item);
void *set_find(set_t *set, const char *key);
void set_print(set_t *set, FILE *fp, void (*itemprint)(FILE *fp, const char *key, void *item));
void set_iterate(set_t *set, void *arg, void (*itemfunc)(void *arg, const char *key, void *item));
void set_delete(set_t *set, void (*itemdelete)(void *item));

* `set_new` returns a pointer to a new set, or NULL if error. We guarantee the set is initialized empty. Caller is responsible for later calling set_delete.
* `set_insert` inserts an item, identified by a key (string), into the given set. The caller provides a valid set pointer, valid string pointer, and pointer to item. We return false if key exists, any parameter is NULL, or error and true iff new item was inserted. The caller is responsible for later calling set_delete to free the memory used by key strings. Notes: The key string is copied for use by the set; that is, the module is responsible for allocating memory for a copy of the key string, and later deallocating that memory; thus, the caller is free to re-use or deallocate its key string after this call.
* `set_find` returns the item associated with the given key. The caller provides a valid set pointer and valid string pointer. We return a pointer to the desired item, if found; NULL if set is NULL, key is NULL, or key is not found. Notes: The item is *not* removed from the set. Thus, the caller should *not* free the pointer that is returned.
* `set_print` prints the whole set; provide the output file and func to print each item. The caller provides: valid set pointer, FILE open for writing, valid pointer to function that prints one item. We print: nothing if NULL fp. Print (null) if NULL set. Print a set with no items if NULL itemprint. Otherwise, print a comma-separated list of items surrounded by {brackets}. Notes: The set and its contents are not changed. The 'itemprint' function is responsible for printing (key,item).
* `set_iterate` iterates over the set, calling a function on each item. Caller provides: valid set pointer, arbitrary argument (pointer) that is passed-through to itemfunc, and valid pointer to function that handles one item. We do: nothing, if set equals NULL or itemfunc equals NULL. Otherwise, call the itemfunc on each item, with (arg, key, item). Notes: the order in which set items are handled is undefined. The set and its contents are not changed by this function, but the itemfunc may change the contents of the item.
* `set_delete` deletes the set, calling a delete function on each item. Caller provides: valid set pointer, valid pointer to function that handles one item (may be NULL). We do: if set equals NULL, do nothing. Otherwise, unless itemfunc equals NULL, call the itemfunc on each item. Free all the key strings, and the set itself. Notes: We free the strings that represent key for each item, because this module allocated that memory in set_insert.

## Compilation

To build, run `make`.

To clean up, run `make clean`.