/* ----------------------------------------------------------------------- *
 *
 *   Copyright 1996-2014 The NASM Authors - All Rights Reserved
 *   See the file AUTHORS included with the NASM distribution for
 *   the specific copyright holders.
 *
 *   Redistribution and use in source and binary forms, with or without
 *   modification, are permitted provided that the following
 *   conditions are met:
 *
 *   * Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above
 *     copyright notice, this list of conditions and the following
 *     disclaimer in the documentation and/or other materials provided
 *     with the distribution.
 *
 *     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 *     CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 *     INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 *     MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 *     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 *     CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 *     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 *     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 *     LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 *     HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 *     CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 *     OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 *     EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * ----------------------------------------------------------------------- */

#include "rdfutils.h"
#include "segtab.h"

struct segtabnode {
    int localseg;
    int destseg;
    int32_t offset;

    struct segtabnode *left;
    struct segtabnode *right;
    /*
     * counts of how many are left or right, for use in reorganising
     * the tree
     */
    int leftcount;
    int rightcount;
};

/*
 * init_seglocations()
 * add_seglocation()
 * get_seglocation()
 * done_seglocation()
 *
 * functions used by write_output() to manipulate associations
 * between segment numbers and locations (which are built up on a per
 * module basis, but we only need one module at a time...)
 *
 * implementation: we build a binary tree.
 */

void init_seglocations(segtab * root)
{
    *root = NULL;
}

static void descend_tree_add(struct segtabnode **node,
                      int localseg, int destseg, int32_t offset)
{
    struct segtabnode *n;

    if (*node == NULL) {
        *node = nasm_malloc(sizeof(**node));
        if (!*node) {
            fprintf(stderr, "segment table: out of memory\n");
            exit(1);
        }
        (*node)->localseg = localseg;
        (*node)->offset = offset;
        (*node)->left = NULL;
        (*node)->leftcount = 0;
        (*node)->right = NULL;
        (*node)->rightcount = 0;
        (*node)->destseg = destseg;
        return;
    }

    if (localseg < (*node)->localseg) {
        (*node)->leftcount++;
        descend_tree_add(&(*node)->left, localseg, destseg, offset);

        if ((*node)->leftcount > (*node)->rightcount + 2) {
            n = *node;
            *node = n->left;
            n->left = (*node)->right;
            n->leftcount = (*node)->rightcount;
            (*node)->right = n;
            (*node)->rightcount = n->leftcount + n->rightcount + 1;
        }
    } else {
        (*node)->rightcount++;
        descend_tree_add(&(*node)->right, localseg, destseg, offset);

        if ((*node)->rightcount > (*node)->leftcount + 2) {
            n = *node;
            *node = n->right;
            n->right = (*node)->left;
            n->rightcount = (*node)->leftcount;
            (*node)->left = n;
            (*node)->leftcount = n->leftcount + n->rightcount + 1;
        }
    }
}

void add_seglocation(segtab * root, int localseg, int destseg, int32_t offset)
{
    descend_tree_add((struct segtabnode **)root, localseg, destseg,
                     offset);
}

int get_seglocation(segtab * root, int localseg, int *destseg,
                    int32_t *offset)
{
    struct segtabnode *n = (struct segtabnode *)*root;

    while (n && n->localseg != localseg) {
        if (localseg < n->localseg)
            n = n->left;
        else
            n = n->right;
    }
    if (n) {
        *destseg = n->destseg;
        *offset = n->offset;
        return 1;
    } else
        return 0;
}

static void freenode(struct segtabnode *n)
{
    if (!n)
        return;
    freenode(n->left);
    freenode(n->right);
    nasm_free(n);
}

void done_seglocations(segtab * root)
{
    freenode(*root);
    *root = NULL;
}

#if 0
void printnode(int i, struct segtabnode *n)
{
    if (!n)
        return;
    printnode(i + 1, n->left);
    printf("%*s%d %d %ld\n", i, "", n->localseg, n->destseg, n->offset);
    printnode(i + 1, n->right);
}

void printtable()
{
    printnode(0, root);
}
#endif