rdoff/segtab.c

   1 /* ----------------------------------------------------------------------- *
   2  *
   3  *   Copyright 1996-2014 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 "rdfutils.h"
  35 #include "segtab.h"
  36
  37 struct segtabnode {
  38     int localseg;
  39     int destseg;
  40     int32_t offset;
  41
  42     struct segtabnode *left;
  43     struct segtabnode *right;
  44     /*
  45      * counts of how many are left or right, for use in reorganising
  46      * the tree
  47      */
  48     int leftcount;
  49     int rightcount;
  50 };
  51
  52 /*
  53  * init_seglocations()
  54  * add_seglocation()
  55  * get_seglocation()
  56  * done_seglocation()
  57  *
  58  * functions used by write_output() to manipulate associations
  59  * between segment numbers and locations (which are built up on a per
  60  * module basis, but we only need one module at a time...)
  61  *
  62  * implementation: we build a binary tree.
  63  */
  64
  65 void init_seglocations(segtab * root)
  66 {
  67     *root = NULL;
  68 }
  69
  70 static void descend_tree_add(struct segtabnode **node,
  71                       int localseg, int destseg, int32_t offset)
  72 {
  73     struct segtabnode *n;
  74
  75     if (*node == NULL) {
  76         *node = nasm_malloc(sizeof(**node));
  77         if (!*node) {
  78             fprintf(stderr, "segment table: out of memory\n");
  79             exit(1);
  80         }
  81         (*node)->localseg = localseg;
  82         (*node)->offset = offset;
  83         (*node)->left = NULL;
  84         (*node)->leftcount = 0;
  85         (*node)->right = NULL;
  86         (*node)->rightcount = 0;
  87         (*node)->destseg = destseg;
  88         return;
  89     }
  90
  91     if (localseg < (*node)->localseg) {
  92         (*node)->leftcount++;
  93         descend_tree_add(&(*node)->left, localseg, destseg, offset);
  94
  95         if ((*node)->leftcount > (*node)->rightcount + 2) {
  96             n = *node;
  97             *node = n->left;
  98             n->left = (*node)->right;
  99             n->leftcount = (*node)->rightcount;
 100             (*node)->right = n;
 101             (*node)->rightcount = n->leftcount + n->rightcount + 1;
 102         }
 103     } else {
 104         (*node)->rightcount++;
 105         descend_tree_add(&(*node)->right, localseg, destseg, offset);
 106
 107         if ((*node)->rightcount > (*node)->leftcount + 2) {
 108             n = *node;
 109             *node = n->right;
 110             n->right = (*node)->left;
 111             n->rightcount = (*node)->leftcount;
 112             (*node)->left = n;
 113             (*node)->leftcount = n->leftcount + n->rightcount + 1;
 114         }
 115     }
 116 }
 117
 118 void add_seglocation(segtab * root, int localseg, int destseg, int32_t offset)
 119 {
 120     descend_tree_add((struct segtabnode **)root, localseg, destseg,
 121                      offset);
 122 }
 123
 124 int get_seglocation(segtab * root, int localseg, int *destseg,
 125                     int32_t *offset)
 126 {
 127     struct segtabnode *n = (struct segtabnode *)*root;
 128
 129     while (n && n->localseg != localseg) {
 130         if (localseg < n->localseg)
 131             n = n->left;
 132         else
 133             n = n->right;
 134     }
 135     if (n) {
 136         *destseg = n->destseg;
 137         *offset = n->offset;
 138         return 1;
 139     } else
 140         return 0;
 141 }
 142
 143 static void freenode(struct segtabnode *n)
 144 {
 145     if (!n)
 146         return;
 147     freenode(n->left);
 148     freenode(n->right);
 149     nasm_free(n);
 150 }
 151
 152 void done_seglocations(segtab * root)
 153 {
 154     freenode(*root);
 155     *root = NULL;
 156 }
 157
 158 #if 0
 159 void printnode(int i, struct segtabnode *n)
 160 {
 161     if (!n)
 162         return;
 163     printnode(i + 1, n->left);
 164     printf("%*s%d %d %ld\n", i, "", n->localseg, n->destseg, n->offset);
 165     printnode(i + 1, n->right);
 166 }
 167
 168 void printtable()
 169 {
 170     printnode(0, root);
 171 }
 172 #endif