rdoff/segtab.c

   1 /* ----------------------------------------------------------------------- *
   2  *
   3  *   Copyright 1996-2009 The NASM Authors - All Rights Reserved
   4  *   See the file AUTHORS included with the NASM distribution for
   5  *   the specific copyright holders.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following
   9  *   conditions are met:
  10  *
  11  *   * Redistributions of source code must retain the above copyright
  12  *     notice, this list of conditions and the following disclaimer.
  13  *   * Redistributions in binary form must reproduce the above
  14  *     copyright notice, this list of conditions and the following
  15  *     disclaimer in the documentation and/or other materials provided
  16  *     with the distribution.
  17  *
  18  *     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  19  *     CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  20  *     INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  21  *     MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22  *     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  23  *     CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  *     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  25  *     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  26  *     LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  *     HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  28  *     CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  29  *     OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
  30  *     EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  *
  32  * ----------------------------------------------------------------------- */
  33
  34 #include "compiler.h"
  35
  36 #include <stdio.h>
  37 #include <stdlib.h>
  38 #include "segtab.h"
  39
  40 struct segtabnode {
  41     int localseg;
  42     int destseg;
  43     int32_t offset;
  44
  45     struct segtabnode *left;
  46     struct segtabnode *right;
  47     /*
  48      * counts of how many are left or right, for use in reorganising
  49      * the tree
  50      */
  51     int leftcount;
  52     int rightcount;
  53 };
  54
  55 /*
  56  * init_seglocations()
  57  * add_seglocation()
  58  * get_seglocation()
  59  * done_seglocation()
  60  *
  61  * functions used by write_output() to manipulate associations
  62  * between segment numbers and locations (which are built up on a per
  63  * module basis, but we only need one module at a time...)
  64  *
  65  * implementation: we build a binary tree.
  66  */
  67
  68 void init_seglocations(segtab * root)
  69 {
  70     *root = NULL;
  71 }
  72
  73 void descend_tree_add(struct segtabnode **node,
  74                       int localseg, int destseg, int32_t offset)
  75 {
  76     struct segtabnode *n;
  77
  78     if (*node == NULL) {
  79         *node = malloc(sizeof(**node));
  80         if (!*node) {
  81             fprintf(stderr, "segment table: out of memory\n");
  82             exit(1);
  83         }
  84         (*node)->localseg = localseg;
  85         (*node)->offset = offset;
  86         (*node)->left = NULL;
  87         (*node)->leftcount = 0;
  88         (*node)->right = NULL;
  89         (*node)->rightcount = 0;
  90         (*node)->destseg = destseg;
  91         return;
  92     }
  93
  94     if (localseg < (*node)->localseg) {
  95         (*node)->leftcount++;
  96         descend_tree_add(&(*node)->left, localseg, destseg, offset);
  97
  98         if ((*node)->leftcount > (*node)->rightcount + 2) {
  99             n = *node;
 100             *node = n->left;
 101             n->left = (*node)->right;
 102             n->leftcount = (*node)->rightcount;
 103             (*node)->right = n;
 104             (*node)->rightcount = n->leftcount + n->rightcount + 1;
 105         }
 106     } else {
 107         (*node)->rightcount++;
 108         descend_tree_add(&(*node)->right, localseg, destseg, offset);
 109
 110         if ((*node)->rightcount > (*node)->leftcount + 2) {
 111             n = *node;
 112             *node = n->right;
 113             n->right = (*node)->left;
 114             n->rightcount = (*node)->leftcount;
 115             (*node)->left = n;
 116             (*node)->leftcount = n->leftcount + n->rightcount + 1;
 117         }
 118     }
 119 }
 120
 121 void add_seglocation(segtab * root, int localseg, int destseg, int32_t offset)
 122 {
 123     descend_tree_add((struct segtabnode **)root, localseg, destseg,
 124                      offset);
 125 }
 126
 127 int get_seglocation(segtab * root, int localseg, int *destseg,
 128                     int32_t *offset)
 129 {
 130     struct segtabnode *n = (struct segtabnode *)*root;
 131
 132     while (n && n->localseg != localseg) {
 133         if (localseg < n->localseg)
 134             n = n->left;
 135         else
 136             n = n->right;
 137     }
 138     if (n) {
 139         *destseg = n->destseg;
 140         *offset = n->offset;
 141         return 1;
 142     } else
 143         return 0;
 144 }
 145
 146 void freenode(struct segtabnode *n)
 147 {
 148     if (!n)
 149         return;
 150     freenode(n->left);
 151     freenode(n->right);
 152     free(n);
 153 }
 154
 155 void done_seglocations(segtab * root)
 156 {
 157     freenode(*root);
 158     *root = NULL;
 159 }
 160
 161 #if 0
 162 void printnode(int i, struct segtabnode *n)
 163 {
 164     if (!n)
 165         return;
 166     printnode(i + 1, n->left);
 167     printf("%*s%d %d %ld\n", i, "", n->localseg, n->destseg, n->offset);
 168     printnode(i + 1, n->right);
 169 }
 170
 171 void printtable()
 172 {
 173     printnode(0, root);
 174 }
 175 #endif