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

10 Klein aber fein

Adv_hash.h

#include "basic_hash.h"

void utilization(hashtable *p, int m);
void rehash(hashtable **p, int m1, int m2);

Basic_hash.h

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

#ifndef BASIC_HASH
#define BASIC_HASH

#define MIN(a,b) ((a) < (b) ? (a) : (b))

typedef struct {
   nodePtr p;
} hashtable;

void buildTable(hashtable **p, int m);
void delete_all(hashtable *p, int m);
void printTable(hashtable *p, int m);
void insert(hashtable *p, int m, data x);
nodePtr search(hashtable *p, int m, data x);
BOOL delete_one(hashtable *p, int m, data x);
#endif

Userdata.h

#ifndef USERDATA
#define USERDATA
#include <stdio.h>

#define FALSE 0
#define TRUE 1

typedef short int BOOL;

typedef struct {
   short int board[4][5];
} data;

typedef struct node *nodePtr;
struct node {
   data userStuff;
   nodePtr next;
} nodeList;

BOOL isEqual(data x, data y);
int data2key(data userStuff, int m);
void printData(data x);
#endif

bishop_new.h

BOOL isPossible(data pos);
BOOL isMove(int x0, int y0, int x1, int y1, data actual);
BOOL testIt(hashtable **p, int m, data actual);

Adv_hash.c

#include "adv_hash.h"

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

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->userStuff);
	 np = np->next;
      }
   }
   delete_all(*p, m1);
   *p = newt;
}

Basic_hash.c

#include "basic_hash.h"
#include "userdata.h"

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

/* To free used memory */
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);
}

void printTable(hashtable *p, int m) {
   nodePtr np;
   int i;
   for (i = 0; i < m; i++) {
      np = (p+i)->p;
      while (np != NULL) {
	 printData(np->userStuff);
	 np = np->next;
      }
      printf("\n");
   }
}

/* insert one element into table p */
void insert(hashtable *p, int m, data x) {
   int pos = data2key(x, m);
   nodePtr temp = (nodePtr)calloc(1, sizeof(nodeList));
   if (temp == NULL) { fprintf(stderr, "Cannot allocate memory\n"); exit(2); }
   temp->next = (p + pos)->p;
   temp->userStuff = x;
   (p + pos)->p = temp;
}

/* check if x is in table p which is of size m */
nodePtr search(hashtable *p, int m, data x) {
   nodePtr np = (p + (data2key(x, m)))->p;
   while (np != NULL) {
      if (isEqual(x, np->userStuff)) return np;
      np = np->next;
   }
   return np;
}

BOOL delete_one(hashtable *p, int m, data x) {
   nodePtr np = (p + (data2key(x, m)))->p;
   if (search(p, m, x) == NULL) return FALSE; /* no such element */
   if (isEqual(x, np->userStuff)) {
      (p + (data2key(x, m)))->p = np->next;
      free(np);
      return TRUE;
   }
   while (np->next != NULL) {
      if (isEqual(x, np->next->userStuff)) {
	 nodePtr temp = np->next;
	 np->next = np->next->next;
	 free(temp);
	 return TRUE;
      }
      np = np->next;
   }
   return FALSE;
}

Userdata.c

#include "userdata.h"

data end;

/* compare two board configurations */
BOOL isEqual(data x, data y) {
   int i, j;
   for (i = 0; i < 4; i++)
      for (j = 0; j < 5; j++)
	 if (x.board[i][j] != y.board[i][j]) return FALSE;
   return TRUE;
}

/* Just read the board as a 20 digit base 3 number */
int data2key(data userStuff, int m) {
   int i, j, res = 0;
   for (i = 0; i < 4; i++)
      for (j = 0; j < 5; j++)
	 res = (res * 3 + userStuff.board[i][j]) % m;
   return res;
}

/* Mainly for debugging */
void printData(data x) {
   int i, j;
   for (j = 0; j < 5; j++) {
      for (i = 0; i < 4; i++)
	 printf("%d ", x.board[i][j]);
      printf(" ");
   }
   printf("\n");
}

Bishop_new.c

#include "basic_hash.h"
#include "adv_hash.h"
#include "bishop_new.h"

data end;

/* Check if pos is an allowed configuration */
/* In other words: are two different bishops facing each other */
BOOL isPossible(data pos) {
   int i, x, y, or;
   for (i = 0; i < 8; i++) {
      or = 0;
      for (y = MIN(i,4), x = i - MIN(i,4); (y >= 0) && (x < 4); y--, x++)
	 or |= pos.board[x][y]; 
      if (or == 3) return FALSE;
      or = 0;
      for (y = 4 - MIN(i,4), x = i - MIN(i,4); (y < 5) && (x < 4); y++, x++)
	 or |= pos.board[x][y]; 
      if (or == 3) return FALSE;
   }
   /* printf("Is possible: "); printData(pos); */
   return TRUE;
}

/* check if a move from (x0, y0) to (x1, y1) is legal */
BOOL isMove(int x0, int y0, int x1, int y1, data actual) {
   int i, j, di, dj;
   if (actual.board[x0][y0]) return FALSE;
   if (x0 == x1) return FALSE;
   di = (x1 > x0)?1:-1;
   dj = (y1 > y0)?1:-1;
   for (i = x0 + di, j = y0 + dj; i != x1; i += di, j += dj)
      if (actual.board[i][j]) return FALSE;
   return TRUE;
}

BOOL testIt(hashtable **p, int m, data actual) {
   int i, j, x, y;
   if (!isEqual(actual, end)) { /* goal not reached */
      if (search(*p, m, actual)) printf("Bug\n"); /* error in hash table */
      insert(*p, m, actual);
      for (i = 0; i < 4; i++)
	 for (j = 0; j < 5; j++)
	    if (actual.board[i][j]) { /* a bishop on tested field */
	       for (x = i - MIN(i,j), y = j - MIN(i,j); (x < 4) && (y < 5);
		  x++, y++) {
		  if (isMove(x, y, i, j, actual)) {
		     actual.board[x][y] = actual.board[i][j];
		     actual.board[i][j] = 0;
		     if(!search(*p, m, actual) && isPossible(actual))
			if (testIt(p, m, actual)) {
			   actual.board[i][j] = actual.board[x][y];
			   actual.board[x][y] = 0;
			   printf("Von (%d,%d) nach (%d,%d).\n", x, y, i, j);
			   return TRUE;
			}
		     actual.board[i][j] = actual.board[x][y];
		     actual.board[x][y] = 0;
		  }
	       }
	       for (x = i - MIN(i,4-j), y = j + MIN(i,4-j); (x < 4) && (y >= 0);
		  x++, y--) {
		  if (isMove(x, y, i, j, actual)) {
		     actual.board[x][y] = actual.board[i][j];
		     actual.board[i][j] = 0;
		     if(!search(*p, m, actual) && isPossible(actual))
			if (testIt(p, m, actual)) {
			   actual.board[i][j] = actual.board[x][y];
			   actual.board[x][y] = 0;
			   printf("Von (%d,%d) nach (%d,%d).\n", x, y, i, j);
			   return TRUE;
			}
		     actual.board[i][j] = actual.board[x][y];
		     actual.board[x][y] = 0;
		  }
	       }
	    }
   } else {
      return TRUE;
   }
   return FALSE;
}

void main() {
   hashtable *pt;
   int m = 997, i, j; /* 101 is good, too */
   data actual;
   for (i = 0; i < 4; i++)
      for (j = 0; j < 5; j++) {
	 actual.board[i][j] = end.board[i][j] = 0;
	 if (j == 0)  { actual.board[i][j] = 1; end.board[i][j] = 2; }
	 if (j == 4)  { actual.board[i][j] = 2; end.board[i][j] = 1; }
      }
   /*buildTable(&pt, m);
   testIt(&pt, m, actual);
   utilization(pt, m);
   delete_all(pt, m); */

   for (i = 0; i < 4; i++)
      for (j = 0; j < 5; j++)
	 actual.board[i][j] = end.board[i][j] = 0;
   actual.board[0][0] = end.board[2][0] = 1;
   actual.board[0][4] = end.board[2][4] = 2;
   buildTable(&pt, m);
   testIt(&pt, m, actual);
   delete_all(pt, m);
   for (i = 0; i < 4; i++)
      for (j = 4; j >= 0; j--) {
	 actual.board[i][j] = end.board[i][j] = 0;
	 if ((!j) && (i & 1))  { 
	    actual.board[i][0] = 1; end.board[i][0] = 2;
	    actual.board[i][4] = 2; end.board[i][4] = 1;
	 }
      }
   buildTable(&pt, m);
   testIt(&pt, m, actual);
   delete_all(pt, m);

   exit(0);
}

Makefile

# Makefile Bishop_new

MAIN=bishop_new
CC=gcc -Wall

OBJ=$(MAIN).o userdata.o basic_hash.o adv_hash.o

main:	$(OBJ)
	$(CC) -o $(MAIN) $(OBJ)

main.o:	$(MAIN).h userdata.h basic_hash.h adv_hash.h
	$(CC) -c $(MAIN).c

clean:
	rm -f $(OBJ) core