htable.c

htable.c

contents ::

  app.c
  htable.c
  htable_copy.c
  htable.h
  mylib.c
  mylib.h

#include <stdio.h>
#include <stdlib.h>
#include "htable.h"
#include "mylib.h"

#define null NULL

struct htablerec {
  int size;
  int num_entries;
  char **keys;
  int *freqs;
};

htable htable_new(int size){
  int i;
  htable ht = emalloc(sizeof *ht);
  ht->size = size;
  ht->num_entries = 0;
  ht->keys = emalloc(size * sizeof ht->keys[0]);
  ht->freqs = emalloc(size * sizeof ht->freqs[0]);

  for(i = 0; i<size; i++){
    ht->keys[i] = null;
    ht->freqs[i] = 0;
  }

  return ht;
}

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);

  while(h->keys[pos]!=null &&
         strcmp(h->keys[pos],key)!=0 &&
         num_collisions < h->size ){
    pos = ++pos % h->size;
    num_collisions++;
  }

  if(num_collisions >= h->size) // We must be full, so return zero.
    return 0;

  if(h->keys[pos] == null){
    h->keys[pos] = emalloc((strlen(key)+1) * sizeof h->keys[0][0]);
    strcpy(h->keys[pos],key);
  }

  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, "%d\t%s\n", 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);

  while(h->keys[pos]!=null &&
         strcmp(h->keys[pos],key)!=0 &&
         num_collisions < h->size ){
    pos = ++pos % h->size;
    num_collisions++;
  }

  if(num_collisions >= h->size)
    return 0;
  else
    return h->freqs[pos];
}

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);
}

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, max_collisions = 0;
  int i;

  if(current_entries < ht->num_entries);
  else {
    for (i = 0; i < current_entries; i++) {
      if(ht->stats[i] == 0)
         at_home++;
      if(ht->stats[i] > max_collisions)
         max_collisions = ht->stats[i];
      average_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