Lösung zu Blatt 4 der Systemnahe Software I (WS 97/98)

A Hashtable

#include <stdio.h>
#include <stdlib.h>

#define FALSE 0
#define TRUE 1

typedef int BOOL;

typedef struct node *nodePtr;
struct node {
   int key;
   /* Add your stuff here */
   nodePtr next;
} nodeList;

typedef struct {
   nodePtr p;
} hashtable;

/* Create an empty hash table, allocate memory for pointers to empty lists */
void buildTable(hashtable **p, int m) {
   int i;
   *p = (hashtable*)calloc(m, sizeof(**p));
   if (*p == NULL) { fprintf(stderr, "Cannot allocate memory\n"); exit(1); }
   for (i = 0; i < m; i++) (*p + i)->p = NULL;
}

/* Free memory. For each list of the table, delete all elements */
void delete_all(hashtable *p, int m) {
   nodePtr np, np2;
   int i;
   for (i = 0; i < m; i++) {
      np = (p+i)->p;
      while (np != NULL) {
	 np2 = np;
	 np = np->next;
	 free(np2);
      }
   }
   free(p);
}

/* For each list of the table, print all elements */
void printTable(hashtable *p, int m) {
   nodePtr np;
   int i;
   for (i = 0; i < m; i++) {
      np = (p+i)->p;
      while (np != NULL) {
	 printf("Ele: %d. ", np->key);
	 np = np->next;
      }
      printf("\n");
   }
}

/* Insert a new element */
/* Maybe check for duplicates, not done due to assignment 6 */
void insert(hashtable *p, int m, int k) {
   nodePtr temp = (nodePtr)calloc(1, sizeof(nodeList));
   int pos = k % m;
   if (temp == NULL) { fprintf(stderr, "Cannot allocate memory\n"); exit(2); }
   temp->next = (p + pos)->p;
   temp->key = k;
   (p + pos)->p = temp;
}

/* Simply check the only possilble list for k */
nodePtr search(hashtable *p, int m, int k) {
   nodePtr np = (p + (k % m))->p;
   while (np != NULL) {
      if (np->key == k) return np;
      np = np->next;
   }
   return np;
}

BOOL delete_one(hashtable *p, int m, int k) {
   nodePtr np = (p + (k % m))->p;
   if (search(p, m, k) == NULL) return FALSE; /* no such element */
   if (np->key == k) { /* Is it the very first element of a list? */
      (p + (k % m))->p = np->next;
      free(np);
      return TRUE;
   }
   while (np->next != NULL) { /* A simple "remove one element" task */
      if (np->next->key == k) {
	 nodePtr temp = np->next;
	 np->next = np->next->next;
	 free(temp);
	 return TRUE;
      }
      np = np->next;
   }
   return FALSE;
}

void utilization(hashtable *p, int m) {
   nodePtr np;
   int max = 0, sum = 0, i, j;
   for (i = 0; i < m; i++) {
      np = (p+i)->p;
      for (j = 1; np != NULL; np = np->next, j++) {
	 max = (max < j)?j:max;
	 sum++;
      }
   }
   printf("Avg: %5.2f, Max: %d.\n",(double)sum/m,max);
}

/* Build a new table (insert the old elements), and delete old table */
void rehash(hashtable **p, int m1, int m2) {
   hashtable *newt;
   nodePtr np;
   int i;
   buildTable(&newt, m2);
   for (i = 0; i < m1; i++) {
      np = (*p+i)->p;
      while (np != NULL) {
	 insert(newt, m2, np->key);
	 np = np->next;
      }
   }
   delete_all(*p, m1);
   *p = newt;
}

void main() {
   hashtable *pt;
   nodePtr test;
   int m = 4, m2 = 3;
   buildTable(&pt, m);
   insert(pt,m,1);
   insert(pt,m,2);
   insert(pt,m,9);
   insert(pt,m,17);
   insert(pt,m,8);
   insert(pt,m,6);
   insert(pt,m,5);
   insert(pt,m,13);
   printTable(pt, m);
   utilization(pt,m);
   delete_one(pt,m,13);
   printTable(pt, m);
   delete_one(pt,m,1);
   printTable(pt, m);
   utilization(pt,m);
   delete_one(pt,m,17);
   printTable(pt, m);
   utilization(pt,m);
   rehash(&pt, m, m2);
   printTable(pt, m2);
   utilization(pt,m2);
   printf("\n");
   delete_all(pt, m2);
   exit(0);
}