| htable_copy.c |
| #include <stdio.h> #include <stdlib.h> #include "htable.h" #include "mylib.h" #define null NULL struct hashtable { int size; int num_entries; hashing_t method; char **keys; int *freqs; int *stats; }; htable htable_new(int size, hashing_t method){ int i; htable ht = emalloc(sizeof *ht); ht->size = size; ht->method = method; ht->num_entries = 0; ht->keys = emalloc(size * sizeof ht->keys[0]); ht->freqs = emalloc(size * sizeof ht->freqs[0]); ht->stats = emalloc(size * sizeof ht->stats[0]); for(i = 0; i<size; i++){ ht->keys[i] = null; ht->freqs[i] = 0; ht->stats[i] = 0; } return ht; } static unsigned int htable_step(htable h, unsigned int i_key){ return 1 + (i_key % (h->size - 1)); } static unsigned int htable_wtoi(char *word){ unsigned int result = 0; while(*word != '\0') result = (*word++ +31 * result); return result; } static unsigned int htable_hash(htable h, unsigned int i_key){ return i_key % h->size; } int htable_insert(htable h, char *key){ int num_collisions = 0; int i_key = htable_wtoi(key); int pos = htable_hash(h, i_key); int step = 1; while(h->keys[pos]!=null && strcmp(h->keys[pos],key)!=0 && num_collisions < h->size ){ if(h->method == DOUBLE) step = htable_step(h, i_key); /* else if(h->method == LINEAR) */ /* step++; */ pos = (pos + step) % h->size; num_collisions++; } if(h->keys[pos] == null){ h->keys[pos] = emalloc((strlen(key)+1) * sizeof h->keys[0][0]); strcpy(h->keys[pos],key); h->stats[h->num_entries] = num_collisions; h->num_entries++; } if(num_collisions >= h->size) // We must be full, so return zero. return 0; return ++(h->freqs[pos]); } void htable_print(htable h, FILE *stream){ int i; for(i = 0; i<h->size; i++){ if(h->keys[i] != null) fprintf(stream, "num: %d\t\t%d\t%s\n",i, h->freqs[i], h->keys[i]); } } int htable_search(htable h, char *key){ int num_collisions = 0; int i_key = htable_wtoi(key); int pos = htable_hash(h, i_key); int step = 1; while(h->keys[pos]!=null && strcmp(h->keys[pos],key)!=0 && num_collisions < h->size ){ if(h->method == DOUBLE) step = htable_step(h, i_key); /* else */ /* step++; */ pos = (pos + step) % h->size; num_collisions++; } if(num_collisions >= h->size) return 0; else return h->freqs[pos]; } /************************** * * * htable_destroy * * * ************************** i - required to iterate through the hash table. PARAMETERS: h = hashtable to free memory from. RETURN VALUE: none */ void htable_destroy(htable h){ int i; for(i = 0; i<h->size; i++){ if(h->keys[i] != null){ free(h->keys[i]); } } if(h->keys != null){ free(h->keys); } if(h->freqs != null){ free(h->freqs); } free(h); } /************************** * * * print_stats_line * * * ************************** Prints stats for one segment (snap shot) of hash table stats. Which were stored while hash table was being built. Percent At Home - how many keys were placed without a collision occurring. Average Collisions - how many collisions have occurred on average while placing all of the keys so far. Maximum Collisions - the most collisions that have occurred while placing a key. Note: print_stats_line() prints a line of data when given what percent full the hashtable should be as its third parameter. If the hashtable is less full than that, then no data will be printed. PARAMETERS: ht = hashtable to print statistics summary from. stream = where to send output. (use stdout for the assignment) percent_full = the maximum number of statistical snapshots to print. RETURN VALUE: none */ static void print_stats_line(htable ht, FILE *stream, int percent_full) { int current_entries = ht->size * percent_full / 100; double average_collisions = 0.0; int at_home = 0; int max_collisions = 0; int i; if(current_entries > ht->num_entries); else { for (i = 0; i < current_entries; i++) { average_collisions += ht->stats[i]; if(ht->stats[i] == 0) at_home++; if(ht->stats[i] > max_collisions) max_collisions = ht->stats[i]; } /* this line is exact code so your output will be standard */ fprintf(stream, "%4d %10d %10.1f %10.2f %11d\n", percent_full, current_entries, at_home * 100.0 / current_entries, average_collisions / current_entries, max_collisions); } } /************************** * * * htable_print_stats * * * ************************** Prints out a table showing what the following attributes were like at regular intervals (as determined by num_stats) while the hashtable was being built. Percent At Home - how many keys were placed without a collision occurring. Average Collisions - how many collisions have occurred on average while placing all of the keys so far. Maximum Collisions - the most collisions that have occurred while placing a key. Note: print_stats_line() prints a line of data when given what percent full the hashtable should be as its third parameter. If the hashtable is less full than that, then no data will be printed. PARAMETERS: ht = hashtable to print statistics summary from. stream = where to send output. (use stdout for the assignment) num_stats = the maximum number of statistical snapshots to print. RETURN VALUE: none */ void htable_print_stats(htable ht, FILE *stream, int num_stats) { int i; fprintf(stream, "\nUsing %s\n\n", ht->method == LINEAR ? "Linear Probing. " : "Double Hashing."); fprintf(stream, "Percent Current Percent Average Maximum\n"); fprintf(stream, " Full Entries At Home Collisions Collisions\n"); fprintf(stream, "-----------------------------------------------------\n"); for (i = 1; i <= num_stats; i++) { print_stats_line(ht, stream, 100 * i / num_stats); } fprintf(stream, "-----------------------------------------------------\n\n"); } |
| James Little |