rdoff/segtab.c

   1 #include "compiler.h"
   2
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include "segtab.h"
   6
   7 struct segtabnode {
   8     int localseg;
   9     int destseg;
  10     int32_t offset;
  11
  12     struct segtabnode *left;
  13     struct segtabnode *right;
  14     /*
  15      * counts of how many are left or right, for use in reorganising
  16      * the tree
  17      */
  18     int leftcount;
  19     int rightcount;
  20 };
  21
  22 /*
  23  * init_seglocations()
  24  * add_seglocation()
  25  * get_seglocation()
  26  * done_seglocation()
  27  *
  28  * functions used by write_output() to manipulate associations
  29  * between segment numbers and locations (which are built up on a per
  30  * module basis, but we only need one module at a time...)
  31  *
  32  * implementation: we build a binary tree.
  33  */
  34
  35 void init_seglocations(segtab * root)
  36 {
  37     *root = NULL;
  38 }
  39
  40 void descend_tree_add(struct segtabnode **node,
  41                       int localseg, int destseg, int32_t offset)
  42 {
  43     struct segtabnode *n;
  44
  45     if (*node == NULL) {
  46         *node = malloc(sizeof(**node));
  47         if (!*node) {
  48             fprintf(stderr, "segment table: out of memory\n");
  49             exit(1);
  50         }
  51         (*node)->localseg = localseg;
  52         (*node)->offset = offset;
  53         (*node)->left = NULL;
  54         (*node)->leftcount = 0;
  55         (*node)->right = NULL;
  56         (*node)->rightcount = 0;
  57         (*node)->destseg = destseg;
  58         return;
  59     }
  60
  61     if (localseg < (*node)->localseg) {
  62         (*node)->leftcount++;
  63         descend_tree_add(&(*node)->left, localseg, destseg, offset);
  64
  65         if ((*node)->leftcount > (*node)->rightcount + 2) {
  66             n = *node;
  67             *node = n->left;
  68             n->left = (*node)->right;
  69             n->leftcount = (*node)->rightcount;
  70             (*node)->right = n;
  71             (*node)->rightcount = n->leftcount + n->rightcount + 1;
  72         }
  73     } else {
  74         (*node)->rightcount++;
  75         descend_tree_add(&(*node)->right, localseg, destseg, offset);
  76
  77         if ((*node)->rightcount > (*node)->leftcount + 2) {
  78             n = *node;
  79             *node = n->right;
  80             n->right = (*node)->left;
  81             n->rightcount = (*node)->leftcount;
  82             (*node)->left = n;
  83             (*node)->leftcount = n->leftcount + n->rightcount + 1;
  84         }
  85     }
  86 }
  87
  88 void add_seglocation(segtab * root, int localseg, int destseg, int32_t offset)
  89 {
  90     descend_tree_add((struct segtabnode **)root, localseg, destseg,
  91                      offset);
  92 }
  93
  94 int get_seglocation(segtab * root, int localseg, int *destseg,
  95                     int32_t *offset)
  96 {
  97     struct segtabnode *n = (struct segtabnode *)*root;
  98
  99     while (n && n->localseg != localseg) {
 100         if (localseg < n->localseg)
 101             n = n->left;
 102         else
 103             n = n->right;
 104     }
 105     if (n) {
 106         *destseg = n->destseg;
 107         *offset = n->offset;
 108         return 1;
 109     } else
 110         return 0;
 111 }
 112
 113 void freenode(struct segtabnode *n)
 114 {
 115     if (!n)
 116         return;
 117     freenode(n->left);
 118     freenode(n->right);
 119     free(n);
 120 }
 121
 122 void done_seglocations(segtab * root)
 123 {
 124     freenode(*root);
 125     *root = NULL;
 126 }
 127
 128 #if 0
 129 void printnode(int i, struct segtabnode *n)
 130 {
 131     if (!n)
 132         return;
 133     printnode(i + 1, n->left);
 134     printf("%*s%d %d %ld\n", i, "", n->localseg, n->destseg, n->offset);
 135     printnode(i + 1, n->right);
 136 }
 137
 138 void printtable()
 139 {
 140     printnode(0, root);
 141 }
 142 #endif