#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "table.h"

/* 
	A symbol table is an ordered linked list of table elements.
	Each element contains the name of the symbol, the line number at which
	it was defined (-1 if no definition has yet been processed), and the
	sequence of line numbers in which the symbol was used.
*/

struct useNode {
  int pos;
  struct useNode *next;
};

struct useNode *add_useNode (struct useNode *head, int pos) {
  struct useNode *t = head;
  struct useNode *n = malloc(sizeof(struct useNode));
  n->pos = pos;
  n->next = NULL;
  if (t == NULL) return n;	/* new entry is entire list */
  while (t->next) t = t->next;	/* add entry to the end of the list */
  t->next = n;
  return head;
};

struct tableElement {
  char *symbolName;
  int defPos;
  struct useNode *uses;
  struct tableElement *next;
};

struct table {
  struct tableElement * head;
};

/*
	Returns an empty table.
*/
struct table * initTable ( ) {
  struct table *rtn = malloc (sizeof (struct table));
  rtn->head = NULL;
  return rtn;
}

struct tableElement *newElement(char *symbol, int def, struct tableElement *next) {
  struct tableElement *n = malloc (sizeof (struct tableElement));
  n->symbolName = (char *) malloc (strlen (symbol) + 1);
  strcpy (n->symbolName, symbol);
  n->defPos = def;
  n->uses = NULL;;
  n->next = next;
  return n;
}

/*
	Returns the result of adding a definition for the given symbol
	in the line with the given number to the table.
*/
struct table *addDef (char * symbol, int lineNum, struct table *symbols) {
  struct tableElement *n;
  struct tableElement *prev = NULL;
  struct tableElement *p = symbols->head;
  if (p == NULL) {		/* Start new list */
    n = newElement(symbol,lineNum,p);
    symbols->head = n;
  } else {			/* Locate point before insertion */
    while (p && (strcmp(symbol,p->symbolName)>0)) {
      prev = p;
      p = p->next;
    }
    if (p && (strcmp(symbol,p->symbolName)==0)) p->defPos = lineNum;
    else {
      n = newElement(symbol,lineNum,p);
      n->next = p;
      if (prev) prev->next = n;
      else symbols->head = n;
    }
  }
  return symbols;
}

/* returns the result of adding a use of the given table in the line
   with the given number to the table */
struct table *addUse (char * symbol, int lineNum, struct table *symbols) {
  struct tableElement *n;
  struct tableElement *prev = NULL;
  struct tableElement *p = symbols->head;
  /* Find point of insertion or update */
  while (p && (strcmp(symbol,p->symbolName)>0)) {
    prev = p;
    p = p->next;
  }

  if (p && (strcmp(symbol,p->symbolName)==0)) /* Already defined */
    p->uses = add_useNode(p->uses, lineNum);      /* Add use */
  else {
    n = newElement(symbol, -1, p); /* Create undef entry */
    n->uses = add_useNode (n->uses, lineNum);
    n->next = p;
    if (prev) prev->next = n;
    else symbols->head = n;
  }
  return symbols;
}

void printTableElem (struct tableElement * elem, FILE * out) {
  struct useNode *u = elem->uses;
  fprintf (out, "%s\t%d", elem->symbolName, elem->defPos);
  while (u) {
    fprintf (out, "\t%d", u->pos);
    u = u->next;
  }
  fprintf (out, "\n");
}

void printTable (struct table *symbols, FILE * out) {
  struct tableElement *p = symbols->head;
  while (p) {
    printTableElem (p, out);
    p = p->next;
  }
}