Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdlib.h>
- #include <stdio.h>
- #include <string.h>
- #include "Dictionary.h"
- const int tableSize = 101;
- typedef struct NodeObj* Node;
- typedef struct NodeObj{
- char* key;
- char* value;
- struct NodeObj* next;
- } NodeObj;
- Node newNode(char* k, char* v){
- Node N = malloc(sizeof(NodeObj));
- N->key = k;
- N->value = v;
- N->next = NULL;
- return N;
- }
- void freeNode(Node* pN){
- if(pN != NULL && *pN != NULL){
- free(*pN);
- *pN = NULL;
- }
- }
- void freeAllNodes(Node H){
- if(H != NULL){
- freeAllNodes(H->next);
- freeNode(&H);
- }
- }
- // Dictionary
- typedef struct DictionaryObj* Dictionary;
- typedef struct DictionaryObj{
- Node* table;
- int size;
- } DictionaryObj;
- // Constructors-Destructors ---------------------------------------------------
- // newDictionary()
- // Constructor for the Dictionary ADT.
- Dictionary newDictionary(){
- Dictionary D = malloc(sizeof(DictionaryObj));
- D->table = calloc(tableSize, sizeof(Node));
- D->size = 0;
- return D;
- }
- // freeDictionary()
- // Destructor for the Dictionary ADT.
- void freeDictionary(Dictionary* pD){
- Node* H = (*pD)->table;
- if(pD != NULL && *pD != NULL){
- makeEmpty(*pD);
- free(H);
- free(*pD);
- *pD = NULL;
- }
- }
- // ADT operations -------------------------------------------------------------
- // rotate_left()
- // rotate the bits in an unsigned int
- unsigned int rotate_left(unsigned int value, int shift) {
- int sizeInBits = 8 * sizeof(unsigned int);
- shift = shift & (sizeInBits - 1);
- if(shift == 0){
- return value;
- }
- return (value << shift) || (value >> (sizeInBits - shift));
- }
- // pre_hash()
- // turn a string into an unsigned int
- unsigned int pre_hash(char* input) {
- unsigned int result = 0xBAE86554;
- while(*input){
- result ^= *input++;
- result = rotate_left(result, 5);
- }
- return result;
- }
- // hash()
- // turns a string into an int in the range 0 to tableSize-1
- int hash(char* key){
- return pre_hash(key) % tableSize;
- }
- // size()
- // Return the number of (key, value) pairs in Dictionary D.
- int size(Dictionary D){
- if(D == NULL){
- fprintf(stderr, "Dictionary Error: size() called on a NULL Dictionary reference\n");
- exit(EXIT_FAILURE);
- }
- return D->size;
- }
- //returns the node that has the matching key
- Node findKey(Dictionary D, char* k){
- Node* H = D->table;
- Node N = H[hash(k)];
- while(N != NULL){
- if(strcmp(N->key, k) == 0){
- return N;
- break;
- }
- N = N->next;
- }
- return NULL;
- }
- // lookup()
- // If D contains a pair whose key matches argument k, then return the
- // corresponding value, otherwise return NULL.
- char* lookup(Dictionary D, char* k){
- Node* H;
- Node N;
- if(D == NULL){
- fprintf(stderr, "Dictionary Error: lookup() called on a NULL Dictionary reference\n");
- exit(EXIT_FAILURE);
- }
- H = D->table;
- N = findKey(D, k);
- if(N != NULL){
- return N->value;
- }
- else{
- return NULL;
- }/*
- if(H[hash(k)] != NULL){
- N = H[hash(k)];
- while(N != NULL){
- if(strcmp(N->key, k) == 0){
- return N->value;
- }
- N = N->next;
- }
- }
- return NULL;*/
- }
- // insert()
- // Insert the pair (k,v) into D.
- // Pre: lookup(D, k)==NULL (D does not contain a pair whose first member is k.)
- void insert(Dictionary D, char* k, char* v){
- Node* H;
- Node N, M;
- if(lookup(D, k) != NULL){
- fprintf(stderr, "Dictionary Error: cannot insert() duplicate key: \"%s\"\n", k);
- exit(EXIT_FAILURE);
- }
- H = D->table;
- N = newNode(k, v);
- if(H[hash(k)] == NULL){ //node does not have any keys yet
- H[hash(k)] = N;
- }
- else{ //node already has keys
- //M = H[hash(k)];
- N->next = H[hash(k)];
- H[hash(k)] = N;
- }
- D->size++;
- }
- // delete()
- // Remove pair whose first member is the argument k from D.
- // Pre: lookup(D,k)!=NULL (D contains a pair whose first member is k.)
- void delete(Dictionary D, char* k){
- Node* H;
- Node N, M;
- if(D == NULL){
- fprintf(stderr, "Dictionary Error: delete() called on a NULL Dictionary reference\n");
- exit(EXIT_FAILURE);
- }
- if(lookup(D, k) == NULL){
- fprintf(stderr, "Dictionary Error: cannot delete() non-existent key: \"%s\"\n", k);
- exit(EXIT_FAILURE);
- }
- H = D->table;
- M = H[hash(k)];
- N = findKey(D, k);
- if(strcmp(M->key, k) == 0){ //if node only has one key
- N = H[hash(k)];
- H[hash(k)] = H[hash(k)]->next;
- }
- else{
- while(M != NULL){
- if(M->next == N){
- M->next = N->next;
- break;
- }
- else{
- M = M->next;
- }
- }
- }
- //N->next = NULL;
- freeNode(&N);
- D->size--;
- }
- // makeEmpty()
- // Reset D to the empty state, the empty set of pairs.
- void makeEmpty(Dictionary D){
- //Node* H;
- if(D == NULL){
- fprintf(stderr, "Dictionary Error: makeEmpty() called on a NULL Dictionary reference\n");
- exit(EXIT_FAILURE);
- }
- //H = D->table;
- for(int i = 0; i < tableSize; i++){
- freeAllNodes(D->table[i]);
- D->table[i] = NULL;
- }
- D->size = 0;
- }
- //return number of characters in a node
- int countChars(Dictionary D){
- Node* H = D->table;
- Node N;
- int count = 0;
- for(int i = 0; i < tableSize; i++){
- if(H[i] != NULL){
- N = H[i];
- while(N != NULL){
- count += strlen(N->key);
- count++;
- count += strlen(N->value);
- count++;
- N = N->next;
- }
- }
- }
- return count;
- }
- // Other Operations -----------------------------------------------------------
- // DictionaryToString()
- // Determines a text representation of the current state of Dictionary D. Each
- // (key, value) pair is represented as the chars in key, followed by a space,
- // followed by the chars in value, followed by a newline '\n' char. The pairs
- // occur in alphabetical order by key. The function returns a pointer to a char
- // array, allocated from heap memory, containing the text representation
- // described above, followed by a terminating null '\0' char. It is the
- // responsibility of the calling function to free this memory.
- char* DictionaryToString(Dictionary D){
- Node* H;
- Node N;
- char* str;
- int count;
- if(D == NULL){
- fprintf(stderr, "Dictionary Error: DictionaryToString() called on a NULL Dictionary reference\n");
- exit(EXIT_FAILURE);
- }
- count = countChars(D);
- str = calloc(count + 1, sizeof(char));
- H = D->table;
- for(int i = 0; i < tableSize; i++){
- if(H[i] != NULL){
- N = H[i];
- while(N != NULL){
- strcat(str, N->key);
- strcat(str, " ");
- strcat(str, N->value);
- strcat(str, "\n");
- N = N->next;
- }
- }
- }
- //str[count] = '\0';
- return str;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement