hash.c

压缩包里面的都是精致的基本C语言小程序

#include <stdio.h>
#include <stdlib.h>
#include "linkedList.h"
#include "mystdlib.h"
#include "dot.h"
#include "str.h"
#include "nat.h"
#include "tuple.h"
#include "error.h"
#include "commonInter.h"
#include "hash.h"

#define initSize 32
#define initMask 0xf
#define initLoadFactor 40.0

struct hash
{
  linkedList *buckets;
  int numItems;
  long size;
  long mask;
  double loadFactor;
};

hash newHash ()
{
  hash h = checkedMalloc (sizeof (*h));
  h->buckets = checkedMalloc (initSize * sizeof (*(h->buckets)));
  
  for (int i=0; i<initSize; i++)
  {
    *(h->buckets + i) = newLinkedList ();
  }
  h->numItems = 0;
  h->size = initSize;
  h->mask = initMask;
  h->loadFactor = initLoadFactor;
  
  return h;
}

hash newHash2 (double load)
{
  hash h = checkedMalloc (sizeof (*h));
  h->buckets = checkedMalloc (initSize * sizeof (*(h->buckets)));
  
  for (int i=0; i<initSize; i++)
  {
    *(h->buckets + i) = newLinkedList ();
  }
  h->numItems = 0;
  h->size = initSize;
  h->mask = initMask;
  h->loadFactor = load;
  
  return h;
}

hash newHash3 (int size, double load)
{
  hash h = checkedMalloc (sizeof (*h));
  h->buckets = checkedMalloc (size * sizeof (*(h->buckets)));
  
  for (int i=0; i<size; i++)
  {
    *(h->buckets + i) = newLinkedList ();
  }
  h->numItems = 0;
  h->size = size;
  h->mask = size-1;
  h->loadFactor = load;
  
  return h;
}

void hashInsert (hash h, poly key, poly value)
{
  int hashCode = getVft (key) -> hashCode (key);
  hashCode &= h->mask;
  
  tuple t = newTuple (key, value);
  
  linkedListInsertHead (*(h->buckets + hashCode), t);
  h->numItems++;
  
  if (hashLoadFactor (h) >= h->loadFactor)
  {
    hash newH = newHash3 (2*h->size, h->loadFactor);
    
    for (int i=0; i<h->size; i++)
    {
      linkedList temp, list;
      temp = ((linkedList)*(h->buckets+i));
      list = temp->next;
    
      while (list)
      {
        tuple t = (tuple)(list->data);
        poly key = tupleFirst (t);
        poly value = tupleSecond (t);
      
        hashInsert (newH, key, value);
        list = list->next;
      }
      
      linkedListDestroy (temp); 
    }

    checkedFree (h->buckets);
    
    h->buckets = newH->buckets;
    h->size = newH->size;
    h->mask = newH->mask;
  }
  return;
}

double hashLoadFactor (hash h)
{
  return (h->numItems)*1.0/(h->size);  
}

void hashToJpg (char *fname, hash h)
{
  dot d = newDot ();
  
  printf ("to dot hash\n");
  
  str s1, s2, s;
  nat n1, n2;
  
  s = newStr ("B");
  str info = newStr ("");
  
  for (int i=0; i<h->size-1; i++)
  {
    n1 = newNat (i);
    s1 = strConcat (s, natToString (n1));
    
    n2 = newNat (i+1);
    s2= strConcat (s, natToString (n2));
    
    dotInsert (s1, s2, info, d);
  }
  
  printf ("loop in the first\n");
  for (int i=0; i<h->size; i++)
  {
    linkedList list = (linkedList)(*(h->buckets + i))->next;
    
    
    if (list)
    {
      s = newStr ("B");
      n1 = newNat (i);
      s1 = strConcat (s, natToString (n1));
      
      s2 = getVft (list->data) ->toString (list->data);
      
      str info = newStr ("");
      
      dotInsert (s1, s2, info, d);
      
      while (list->next)
      {
        str s3 = getVft (list->next->data)->toString (list->next->data);
        
        dotInsert (s2, s3, info, d);
        s2 = s3;        
        list = list->next;
      }
    }
  }
  
  printf ("just before output\n");
  
  dotToJpg (d, fname);
  
  return;
}

int longestChain (hash h)
{
  int max = 0;
  int current;
  
  for (int i=0; i<h->size; i++)
  {
    current = linkedListSize (*(h->buckets+i));
    if (current > max)
      max = current;
  }
  
  return max;
}

struct A
{
  long empty;
  long ne;
};

struct A numEmptyBuckets (hash h)
{
  long empty = 0;
  long ne = 0;
  
  for (int i=0; i<h->size; i++)
  {
    int current;
    current = linkedListSize (*(h->buckets+i));
    if (!current)
      empty++;
    else
      ne++;
  }
  
  struct A a;
  a.empty = empty;
  a.ne = ne;
  return a;
}

void hashStatus (hash h)
{  
  struct A a;
  a = numEmptyBuckets (h);
  printf ("number of items are: %d\n", h->numItems);
  printf ("number of buckets: %ld\n", h->size);
  printf ("number of empty buckets: %ld\n", a.empty);
  printf ("number of not empty buckets: %ld\n", a.ne);
  printf ("size of longest chain is: %d\n", longestChain (h));
  printf ("load factor: %lf\n", hashLoadFactor (h));
  printf ("default load factor: %lf\n", h->loadFactor);
  
  return;
}

poly hashLookup (hash h, poly key)
{
  tyHashCode hashFn = getVft(key)->hashCode;
  int i = hashFn (key);
  i &= h->mask;
  
  linkedList list = ((linkedList)(*(h->buckets + i)))->next;
  
  while (list)
  {
    tuple t = (tuple)(list->data);
    
    poly first = tupleFirst (t);
    poly second = tupleSecond (t);
    
    int eqx = getVft (first) ->equals (key, first);
    if (eqx)
      return second;
    
    list = list->next;
  }
  return NULL;
}

int hashSize (hash h)
{
  return h->size;
}

int hashNumItems (hash h)
{
  return h->numItems;
}

linkedList hashChain (hash h, int i)
{
  if (i<0 || i>= h->size)
    exception ("index out of bound: hash.c\n");
    
  linkedList l = *(h->buckets+i);
  return l;
}