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

struct segtabnode {
    int localseg;
    int destseg;
    long offset;

    struct segtabnode * left;
    struct segtabnode * right;
    /* 
     * counts of how many are left or right, for use in reorganising
     * the tree
     */
    int leftcount;
    int rightcount;
};

/*
 * init_seglocations()
 * add_seglocation()
 * get_seglocation()
 * done_seglocation()
 *
 * functions used by write_output() to manipulate associations
 * between segment numbers and locations (which are built up on a per
 * module basis, but we only need one module at a time...)
 *
 * implementation: we build a binary tree.
 */


void init_seglocations(segtab * root)
{
    *root = NULL;
}

void descend_tree_add(struct segtabnode * * node,
		      int localseg, int destseg, long offset)
{
    struct segtabnode * n;

    if (*node == NULL) {
	*node = malloc (sizeof (**node));
	if (!*node) {
	    fprintf(stderr, "segment table: out of memory\n");
	    exit(1);
	}
	(*node)->localseg = localseg;
	(*node)->offset = offset;
	(*node)->left = NULL;
	(*node)->leftcount = 0;
	(*node)->right = NULL;
	(*node)->rightcount = 0;
	(*node)->destseg = destseg;
	return;
    }

    if (localseg < (*node)->localseg)
    {
	(*node)->leftcount++;
	descend_tree_add(&(*node)->left, localseg, destseg, offset);

	if ((*node)->leftcount > (*node)->rightcount + 2) {
	    n = * node;
	    *node = n->left;
	    n->left = (*node)->right;
	    n->leftcount = (*node)->rightcount;
	    (*node)->right = n;
	    (*node)->rightcount = n->leftcount + n->rightcount + 1;
	}
    }
    else
    {
	(*node)->rightcount++;
	descend_tree_add(&(*node)->right, localseg, destseg, offset);

	if ((*node)->rightcount > (*node)->leftcount + 2) {
	    n = * node;
	    *node = n->right;
	    n->right= (*node)->left;
	    n->rightcount = (*node)->leftcount;
	    (*node)->left = n;
	    (*node)->leftcount = n->leftcount + n->rightcount + 1;
	}
    }
}

void add_seglocation(segtab * root, int localseg, int destseg, long offset)
{
    descend_tree_add((struct segtabnode **) root, localseg, destseg, offset);
}

int get_seglocation(segtab * root, int localseg, int * destseg, long * offset)
{
    struct segtabnode * n = (struct segtabnode *) *root;
    
    while (n && n->localseg != localseg)
    {
	if (localseg < n->localseg) 
	    n = n->left;
	else
	    n = n->right;
    }
    if (n) {
	*destseg = n->destseg;
	*offset = n->offset;
	return 1;
    }
    else
	return 0;
}

void freenode(struct segtabnode * n)
{
    if (!n) return;
    freenode (n->left);
    freenode (n->right);
    free(n);
}

void done_seglocations(segtab * root)
{
    freenode(*root);
    *root = NULL;
}

#if 0
void printnode(int i, struct segtabnode * n)
{
    if (!n) return;
    printnode(i + 1, n->left);
    printf ("%*s%d %d %ld\n", i, "", n->localseg, n->destseg, n->offset);
    printnode(i + 1, n->right);
}

void printtable()
{
    printnode(0,root);
}
#endif