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     long 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
  34 void init_seglocations(segtab * root)
  35 {
  36     *root = NULL;
  37 }
  38
  39 void descend_tree_add(struct segtabnode * * node,
  40                       int localseg, int destseg, long offset)
  41 {
  42     struct segtabnode * n;
  43
  44     if (*node == NULL) {
  45         *node = malloc (sizeof (**node));
  46         if (!*node) {
  47             fprintf(stderr, "segment table: out of memory\n");
  48             exit(1);
  49         }
  50         (*node)->localseg = localseg;
  51         (*node)->offset = offset;
  52         (*node)->left = NULL;
  53         (*node)->leftcount = 0;
  54         (*node)->right = NULL;
  55         (*node)->rightcount = 0;
  56         (*node)->destseg = destseg;
  57         return;
  58     }
  59
  60     if (localseg < (*node)->localseg)
  61     {
  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     }
  74     else
  75     {
  76         (*node)->rightcount++;
  77         descend_tree_add(&(*node)->right, localseg, destseg, offset);
  78
  79         if ((*node)->rightcount > (*node)->leftcount + 2) {
  80             n = * node;
  81             *node = n->right;
  82             n->right= (*node)->left;
  83             n->rightcount = (*node)->leftcount;
  84             (*node)->left = n;
  85             (*node)->leftcount = n->leftcount + n->rightcount + 1;
  86         }
  87     }
  88 }
  89
  90 void add_seglocation(segtab * root, int localseg, int destseg, long offset)
  91 {
  92     descend_tree_add((struct segtabnode **) root, localseg, destseg, offset);
  93 }
  94
  95 int get_seglocation(segtab * root, int localseg, int * destseg, long * offset)
  96 {
  97     struct segtabnode * n = (struct segtabnode *) *root;
  98
  99     while (n && n->localseg != localseg)
 100     {
 101         if (localseg < n->localseg)
 102             n = n->left;
 103         else
 104             n = n->right;
 105     }
 106     if (n) {
 107         *destseg = n->destseg;
 108         *offset = n->offset;
 109         return 1;
 110     }
 111     else
 112         return 0;
 113 }
 114
 115 void freenode(struct segtabnode * n)
 116 {
 117     if (!n) return;
 118     freenode (n->left);
 119     freenode (n->right);
 120     free(n);
 121 }
 122
 123 void done_seglocations(segtab * root)
 124 {
 125     freenode(*root);
 126     *root = NULL;
 127 }
 128
 129 #if 0
 130 void printnode(int i, struct segtabnode * n)
 131 {
 132     if (!n) 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