12 struct segtabnode *left;
13 struct segtabnode *right;
15 * counts of how many are left or right, for use in reorganising
28 * functions used by write_output() to manipulate associations
29 * between segment numbers and locations (which are built up on a per
30 * module basis, but we only need one module at a time...)
32 * implementation: we build a binary tree.
35 void init_seglocations(segtab * root)
40 void descend_tree_add(struct segtabnode **node,
41 int localseg, int destseg, int32_t offset)
46 *node = malloc(sizeof(**node));
48 fprintf(stderr, "segment table: out of memory\n");
51 (*node)->localseg = localseg;
52 (*node)->offset = offset;
54 (*node)->leftcount = 0;
55 (*node)->right = NULL;
56 (*node)->rightcount = 0;
57 (*node)->destseg = destseg;
61 if (localseg < (*node)->localseg) {
63 descend_tree_add(&(*node)->left, localseg, destseg, offset);
65 if ((*node)->leftcount > (*node)->rightcount + 2) {
68 n->left = (*node)->right;
69 n->leftcount = (*node)->rightcount;
71 (*node)->rightcount = n->leftcount + n->rightcount + 1;
74 (*node)->rightcount++;
75 descend_tree_add(&(*node)->right, localseg, destseg, offset);
77 if ((*node)->rightcount > (*node)->leftcount + 2) {
80 n->right = (*node)->left;
81 n->rightcount = (*node)->leftcount;
83 (*node)->leftcount = n->leftcount + n->rightcount + 1;
88 void add_seglocation(segtab * root, int localseg, int destseg, int32_t offset)
90 descend_tree_add((struct segtabnode **)root, localseg, destseg,
94 int get_seglocation(segtab * root, int localseg, int *destseg,
97 struct segtabnode *n = (struct segtabnode *)*root;
99 while (n && n->localseg != localseg) {
100 if (localseg < n->localseg)
106 *destseg = n->destseg;
113 void freenode(struct segtabnode *n)
122 void done_seglocations(segtab * root)
129 void printnode(int i, struct segtabnode *n)
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);