1 /* ----------------------------------------------------------------------- *
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
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 * ----------------------------------------------------------------------- */
45 struct segtabnode
*left
;
46 struct segtabnode
*right
;
48 * counts of how many are left or right, for use in reorganising
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
)
73 void descend_tree_add(struct segtabnode
**node
,
74 int localseg
, int destseg
, int32_t offset
)
79 *node
= malloc(sizeof(**node
));
81 fprintf(stderr
, "segment table: out of memory\n");
84 (*node
)->localseg
= localseg
;
85 (*node
)->offset
= offset
;
87 (*node
)->leftcount
= 0;
88 (*node
)->right
= NULL
;
89 (*node
)->rightcount
= 0;
90 (*node
)->destseg
= destseg
;
94 if (localseg
< (*node
)->localseg
) {
96 descend_tree_add(&(*node
)->left
, localseg
, destseg
, offset
);
98 if ((*node
)->leftcount
> (*node
)->rightcount
+ 2) {
101 n
->left
= (*node
)->right
;
102 n
->leftcount
= (*node
)->rightcount
;
104 (*node
)->rightcount
= n
->leftcount
+ n
->rightcount
+ 1;
107 (*node
)->rightcount
++;
108 descend_tree_add(&(*node
)->right
, localseg
, destseg
, offset
);
110 if ((*node
)->rightcount
> (*node
)->leftcount
+ 2) {
113 n
->right
= (*node
)->left
;
114 n
->rightcount
= (*node
)->leftcount
;
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
,
127 int get_seglocation(segtab
* root
, int localseg
, int *destseg
,
130 struct segtabnode
*n
= (struct segtabnode
*)*root
;
132 while (n
&& n
->localseg
!= localseg
) {
133 if (localseg
< n
->localseg
)
139 *destseg
= n
->destseg
;
146 void freenode(struct segtabnode
*n
)
155 void done_seglocations(segtab
* root
)
162 void printnode(int i
, struct segtabnode
*n
)
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
);