rdoff/segtab.c

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