insns.dat: copied over from master
[nasm.git] / rdoff / segtab.c
blob4a4c5b807e917b7d211ec9fdffacff6067fbac4f
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.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following
9 * conditions are met:
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.
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.
32 * ----------------------------------------------------------------------- */
34 #include "compiler.h"
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include "segtab.h"
40 struct segtabnode {
41 int localseg;
42 int destseg;
43 int32_t offset;
45 struct segtabnode *left;
46 struct segtabnode *right;
48 * counts of how many are left or right, for use in reorganising
49 * the tree
51 int leftcount;
52 int rightcount;
56 * init_seglocations()
57 * add_seglocation()
58 * get_seglocation()
59 * done_seglocation()
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...)
65 * implementation: we build a binary tree.
68 void init_seglocations(segtab * root)
70 *root = NULL;
73 void descend_tree_add(struct segtabnode **node,
74 int localseg, int destseg, int32_t offset)
76 struct segtabnode *n;
78 if (*node == NULL) {
79 *node = malloc(sizeof(**node));
80 if (!*node) {
81 fprintf(stderr, "segment table: out of memory\n");
82 exit(1);
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;
94 if (localseg < (*node)->localseg) {
95 (*node)->leftcount++;
96 descend_tree_add(&(*node)->left, localseg, destseg, offset);
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;
106 } else {
107 (*node)->rightcount++;
108 descend_tree_add(&(*node)->right, localseg, destseg, offset);
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;
121 void add_seglocation(segtab * root, int localseg, int destseg, int32_t offset)
123 descend_tree_add((struct segtabnode **)root, localseg, destseg,
124 offset);
127 int get_seglocation(segtab * root, int localseg, int *destseg,
128 int32_t *offset)
130 struct segtabnode *n = (struct segtabnode *)*root;
132 while (n && n->localseg != localseg) {
133 if (localseg < n->localseg)
134 n = n->left;
135 else
136 n = n->right;
138 if (n) {
139 *destseg = n->destseg;
140 *offset = n->offset;
141 return 1;
142 } else
143 return 0;
146 void freenode(struct segtabnode *n)
148 if (!n)
149 return;
150 freenode(n->left);
151 freenode(n->right);
152 free(n);
155 void done_seglocations(segtab * root)
157 freenode(*root);
158 *root = NULL;
161 #if 0
162 void printnode(int i, struct segtabnode *n)
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);
171 void printtable()
173 printnode(0, root);
175 #endif