dagify.c

// Convert a tree into a dag
// Author: John Wickerson
//
// Instructions:
//   gcc dagify.c
//   ./a.out

#include <stdlib.h> // for NULL
#include <stdio.h>  // for printf

typedef struct node_ {
  int contents;
  struct node_ *left;
  struct node_ *right;
} node;

typedef struct map_entry_ {
  node key;
  node *value;
} map_entry;

#define MAP_MAX_SIZE 100
map_entry map[MAP_MAX_SIZE];
int map_size = 0;

node *lookup(node key) {
  for (int i = 0; i < map_size; i++)
    if (map[i].key.contents == key.contents
	&& map[i].key.left == key.left
	&& map[i].key.right == key.right)
      return map[i].value;
  return NULL;
}

void put(node key, node *value) {
  map[map_size].key = key;
  map[map_size].value = value;
  map_size++;
}

node *dagify(node *n) {
  if (n == NULL) return n;
  n->left = dagify(n->left);
  n->right = dagify(n->right);
  node *result = lookup(*n);
  if (result == NULL) {
    put(*n, n);
    result = n;
  } 
  return result;
}

node *mkNode(int contents, node *left, node *right) {
  node *result = malloc(sizeof(node));
  result->contents = contents;
  result->left = left;
  result->right = right;
  return result;
}

void printNode(node *n) {
  printf ("%p |-> (%d, %p, %p)\n",
	  n, n->contents, n->left, n->right);
}

void printTree(node *n) {
  if (n == NULL) return;
  printNode(n);
  printTree(n->left);
  printTree(n->right);
}

void printDag() {
  for (int i = 0; i < map_size; i++) 
    printNode(map[i].value);
}

int main() {

  // Example tree:
  node *a = mkNode(10, NULL, NULL); // literal 10
  node *b = mkNode(1, a, NULL);     // neg, perhaps
  node *c = mkNode(10, NULL, NULL); // literal 10
  node *d = mkNode(2, c, b);        // mult, perhaps

  printf("\nInitial tree:\n");
  printTree(d);
  
  d = dagify(d);

  printf("\nFinal dag:\n");
  printDag();
  
  
}