/* * File: functab_tree.c * * Description: This module contains functions related to managing * a binary search tree for an object's function table. The purpose * is to improve function search times from O(n) (linear search) * to O(lg n) (binary search). * * Please direct inquiries regarding this code to apang@mindlink.bc.ca * * Note(s): * The tree insertion function is loosely based on Paul Vixie's * public domain implementation of an AVL tree package, posted to * comp.sources.unix, circa 1987. For more information on * AVL trees in general, I refer you to: * * Knuth, D. "The Art of Computer Programming". Addison-Wesley. * Volume 3. 1973. * Wirth, N. "Algorithms and Data Structures". Prentice-Hall. * 1986 * * You must #define OPTIMIZE_FUNCTION_TABLE_SEARCH in options.h * in order to enable this driver feature. * * Amylaar did not write this. :^) */ /* * minimal includes here, in case this module isn't used */ #include "std.h" #include "lpc_incl.h" #include "simulate.h" #ifdef OPTIMIZE_FUNCTION_TABLE_SEARCH #include "functab_tree.h" #include "program.h" /* * The function table tree is accomplished by augmenting the function * structure with fields for the left, right, and balance fields required * for AVL trees. (See "program.h".) The actual function data in a slot * is not moved, rather only the branch information is changed. Thus, the * table can still be searched linearly. Also, F_CALL_FUNCTION_BY_ADDRESS * calls don't have to be patched. * * By using indices instead of using real addresses for the left and right * branches, the storage overhead for the tree information is lower. In * addition, the tree information is location independent (ie relocatable). * The tradeoff is added CPU time to dereference the function table and * compute the actual address. (This may be rectified in a later version.) * * The function table slot is preallocated and filled before it gets here. * Thus, this code does not call malloc(). This also means we never * have to delete the tree or any individual node explicity, as this is * free()'d when the program itself is free()'d. * * The function table tree has to be rebuilt when binaries are loaded * since string pointers (as opposed to the contents) have likely changed. * On the up side, the function table tree isn't stored in saved binaries, * where it can increase your disk usage. */ /* * Prototypes for local functions */ static void functab_tree_add(function_t *, unsigned short *, int, SIGNED short *); /* * The address comparison routine. * * Since we're using shared strings for function names, comparing only * the address (vs the contents) speeds up the search. */ #define compare_addrs(x,y) (x < y ? -1 : (x > y ? 1 : 0)) /* * Perform a binary tree search in specified function table * for the named function. Returns index into function table. * * Example of usage: * fnum = lookup_function(prog->p.i.functions, prog->p.i.tree_r, name); */ int lookup_function P3(function_t *, functab, /* function table to search */ int, f_index, /* initially, functab tree's root */ char *, funcname) /* name of function */ { SIGNED int i; unsigned short index; index = (unsigned short) (f_index & 0xffff); while ((unsigned short) ~index) { i = compare_addrs(funcname, functab[index].name); if (i < 0) { index = functab[index].tree_l; continue; } if (i > 0) { index = functab[index].tree_r; continue; } /* * We have a match! */ return (int) index; } return -1; } /* * Entry stub to functab_tree_add() where the real work is done. * * Example of usage: * add_function(prog->p.i.functions, &prog->p.i.tree_r, fnum); */ void add_function P3(function_t *, functab, /* function table */ unsigned short *, root, /* functab tree's root */ int, newfunc) { SIGNED short balance = 0; functab[newfunc].tree_l = (unsigned short) 0xffff; functab[newfunc].tree_r = (unsigned short) 0xffff; functab[newfunc].tree_b = 0; functab_tree_add(functab, root, newfunc, &balance); return; } /* * Do the real work of inserting node and rebalancing tree... */ static void functab_tree_add P4(function_t *, functab, unsigned short *, root, int, newfunc, SIGNED short *, balance) { SIGNED int i; unsigned short p1, p2; /* temporary "pointers" */ DEBUG_CHECK(*balance < -1 || *balance > 1, "Balance is garbage.\n"); DEBUG_CHECK(!balance || !root || !functab, "Null pointer in functab_tree.\n"); /* * Are we at an insertion point? If so, add new node here, rebalance, and * exit. */ if ((unsigned short) ~(*root) == 0) { *root = (unsigned short) (newfunc & 0xffff); *balance = 1; return; } /* * Compare data */ i = compare_addrs(functab[newfunc].name, functab[*root].name); if (i < 0) { functab_tree_add(functab, &functab[*root].tree_l, newfunc, balance); if (*balance) { /* * left branch has grown */ switch (functab[*root].tree_b) { case 1: /* * right branch WAS longer; balance is ok now */ functab[*root].tree_b = 0; *balance = 0; break; case 0: /* * balance WAS okay; now left branch longer */ functab[*root].tree_b = -1; break; case -1: /* * left branch was already too long; rebalance */ p1 = functab[*root].tree_l; if (functab[p1].tree_b == -1) { /* * LL */ functab[*root].tree_l = functab[p1].tree_r; functab[p1].tree_r = *root; functab[*root].tree_b = 0; *root = p1; } else { /* * double LR */ p2 = functab[p1].tree_r; functab[p1].tree_r = functab[p2].tree_l; functab[p2].tree_l = p1; functab[*root].tree_l = functab[p2].tree_r; functab[p2].tree_r = *root; if (functab[p2].tree_b == -1) functab[*root].tree_b = 1; else functab[*root].tree_b = 0; if (functab[p2].tree_b == 1) functab[p1].tree_b = -1; else functab[p1].tree_b = 0; *root = p2; } functab[*root].tree_b = 0; *balance = 0; } } return; } if (i > 0) { functab_tree_add(functab, &functab[*root].tree_r, newfunc, balance); if (*balance) { /* * right branch has grown */ switch (functab[*root].tree_b) { case -1: /* * left branch WAS longer; balance is ok now */ functab[*root].tree_b = 0; *balance = 0; break; case 0: /* * balance WAS okay; now right branch longer */ functab[*root].tree_b = 1; break; case 1: /* * right branch was already too long; rebalance */ p1 = functab[*root].tree_r; if (functab[p1].tree_b == 1) { /* * RR */ functab[*root].tree_r = functab[p1].tree_l; functab[p1].tree_l = *root; functab[*root].tree_b = 0; *root = p1; } else { /* * double RL */ p2 = functab[p1].tree_l; functab[p1].tree_l = functab[p2].tree_r; functab[p2].tree_r = p1; functab[*root].tree_r = functab[p2].tree_l; functab[p2].tree_l = *root; if (functab[p2].tree_b == 1) functab[*root].tree_b = -1; else functab[*root].tree_b = 0; if (functab[p2].tree_b == -1) functab[p1].tree_b = 1; else functab[p1].tree_b = 0; *root = p2; } functab[*root].tree_b = 0; *balance = 0; } } return; } /* * Oh...oh. This is the same key! This is not good... */ *balance = 0; IF_DEBUG(fatal("Duplicate entry in function table tree [%s].\n", functab[newfunc].name)); return; } #endif /* OPTIMIZE_FUNCTION_TABLE_SEARCH */