Logo Search packages:      
Sourcecode: nasm version File versions  Download package

segtab.c

#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

Generated by  Doxygen 1.6.0   Back to index