/*->c.xsym  */


#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <signal.h>
#include <ctype.h>
#include <time.h>
#include <locale.h>



#include "h.os"
#include "h.wimp"
#include "h.sprite"
#include "h.werr"
#include "h.wimpt"
#include "h.bbc"
#include "h.akbd"
#include "h.flex"
#include "h.Drawlevel0"

#include "h.wos"


#include "h.pr"
#include "h.file"
#include "h.main"


#include "h.strdef"
#include "h.serialdev"
#include "h.serial"
#include "h.script"
#include "h.dir"
#include "h.batch"
#include "h.rxfax"
#include "h.txfax"
#include "h.config"
#include "h.vx"
#include "h.ftpglue"
#include "h.ser"
#include "h.con"
#include "h.log"
#include "h.replay"
#include "h.state"
#include "h.ident"


#include "h.xext"
#include "h.xint"



/*****************************************************************************/

static int symtablesize;


/*****************************************************************************/
/* x symbol table manager */




char    * xsymheap;      /* heap used to store symbol table        */
static int       xheapsize;     /* pointer to first free location in heap */
static symstk  * xsyms;  /* list of pointers to first entry in each stage */
int       xnsyms;        /* number of stages */




#define NIL_NODE     -1    /* ptr for empty (sub)trees */

typedef int DIR;                      /* type for indexing siblings */

#define        L       ((DIR) 0)
#define        R       ((DIR) 1)

#define        LEFT    sibls[L]       /* left sibling pointer NODE field */
#define        RIGHT   sibls[R]       /* right sibling pointer NODE field */


/*
 * Direction gives direction in which child NODE c is under parent NODE p.
 */

#define        direction(p,c) ((DIR) ((p)->RIGHT==(c)))

/*
 * Cmp_dir gives direction corresponding with compare value v (R iff v > 0).
 */

#define        cmp_dir(v)      ((DIR) ((v) > 0))

/*
 * Siblingp yields ptr to left (d == L) or right (d == R) child of NODE n.
 */

#define        siblingp(n, d)  ((xptr((n))->sibls) + (d))

#define        sibling(n, d)  ((n)->sibls + (d))

/*
 * Parentp yields ptr to parent's ptr to NODE n, or root ptr r if n is 0.
 */


/*

#define        parentp(r, n)   ((xptr((n))->parent) == NIL_NODE ? (r) : \
               siblingp((xptr((n))->parent), direction((xptr((n))->parent), (n))))

 */



/*
 * Dir_bal yields balance value corresponding to DIR d.
 */

#define        dir_bal(d)      ((d) == L ? -1 : 1)








static int * parentp(int * rootp,int sb)
{
 symstr * p;
 int    * q;
 int      pa;

 p=xptr(sb);
 pa=p->parent;

 if(pa==NIL_NODE) return(rootp);

 q=siblingp(pa,direction(xptr(pa),sb));

 return(q);
}



/*
 * Balance the subtree rooted at sb that has become to heavy on side d
 * by single rotation of sb and sb_next.
 * Also adjusts sibling pointer of the parent of sb, or *rootp if sb is
 * the top of the entire tree.
 *
 *             sb              sb_next         Single rotation: Adding x or
 *            /  \            /       \        deleting under 3 caused
 *     sb_next    3          1         sb      rotation.  Same holds for mirror
 *     /       \             |        /  \     image.  Single_rotation returns
 *    1                2       ==>   x       2    3    top of new balanced tree.
 *    |                |                     |
 *    x                y                     y
 */

static int single_rotation(int * rootp,int sb,int sb_next,DIR d)
{
 *siblingp(sb,d)=*siblingp(sb_next,!d);
 *siblingp(sb_next,!d)=sb;

 xptr(sb)->balance-=xptr(sb_next)->balance;
 xptr(sb_next)->balance=-xptr(sb)->balance;

 *parentp(rootp,sb)=sb_next;
 xptr(sb_next)->parent=xptr(sb)->parent;
 xptr(sb)->parent=sb_next;
 if(*siblingp(sb,d)!=NIL_NODE)
 xptr((*siblingp(sb,d)))->parent=sb;

 return(sb_next);
}




/*
 * Balance the subtree rooted at sb that has become to heavy on side d
 * by double rotation of sb and sb_next.
 * Also adjusts sibling pointer of the parent of sb, or *rootp if sb is
 * the top of the entire tree.
 *
 *             sb                  sb_next2       Double rotation: Adding x or
 *            /  \                /        \      x', or deleting under 4
 *     sb_next    \            sb_next      sb    caused rotation. Same holds
 *     /       \    \         /       \    /  \   for the mirror image.
 *    1   sb_next2   4  ==>  1         2  3    4  Double_rotation returns top
 *       /        \                    |  |       of new balanced tree.
 *      2          3                   x  x'
 *      |         |
 *      x         x'
 */

static int double_rotation(int * rootp,int sb,int sb_next,DIR d)
{
 int      sb_next2;
 symstr * sb_n2p;
 symstr * sb_np;
 symstr * sbp;

 sb_np=xptr(sb_next);
 sb_next2=*sibling(sb_np,!d);
 sb_n2p=xptr(sb_next2);
 sbp=xptr(sb);

 *sibling(sb_np,!d)=*sibling(sb_n2p,d);
 *sibling(sbp,d)    =*sibling(sb_n2p,!d);
 *sibling(sb_n2p,d)=sb_next;
 *sibling(sb_n2p,!d)=sb;

 if(sb_n2p->balance==sb_np->balance) sb_np->balance=-sb_np->balance;
 else                                sb_np->balance=0;

 if(sb_n2p->balance==sbp->balance)   sbp->balance=-sbp->balance;
 else                                sbp->balance=0;

 sb_n2p->balance=0;

 *parentp(rootp,sb)=sb_next2;
 sb_n2p->parent=sbp->parent;
 sbp->parent=sb_np->parent=sb_next2;

 if(*sibling(sb_np,!d)!=NIL_NODE)
               xptr(*sibling(sb_np,!d))->parent=sb_next;

 if(*sibling(sbp, d) != NIL_NODE)
               xptr(*sibling(sbp,d))->parent=sb;

 return(sb_next2);
}








/*
 * Balance the subtree rooted at sb that has become to heavy on side d.
 * Also adjusts sibling pointer of the parent of sb, or *rootp if sb is
 * the top of the entire tree.
 */

static int balance(int * rootp,int sb,DIR d)
{
 int sb_next=*siblingp(sb,d);

 if(xptr(sb_next)->balance==-dir_bal(d))
               return(double_rotation(rootp,sb,sb_next,d));
 else
               return(single_rotation(rootp,sb,sb_next,d));
}









/*
 * Tsearch adds node key to tree rooted by *rootp, using compar for
 * comparing elements.  It returns the pointer to the NODE in which
 * the (possibly already existing) key pointer resides.
 */


static int tsearch(int newnode,int * rootp)
{
 int parent;
 int child;
 DIR d;
 int cmp;
 symstr * childp;
 symstr * nnode;
 symstr * pp;

 nnode=xptr(newnode);

 if(rootp==0) return(NIL_NODE);

 /* find place where key should go */

 parent=NIL_NODE;
 child=*rootp;
 while(child!=NIL_NODE)
 {
  childp=xptr(child);
  if((cmp=strcmp(nnode->key,childp->key))==0) return(child);
  parent=child;
  child=*sibling(childp,cmp_dir(cmp));
 }

 /* create new node and set its parent's sibling pointer */

 nnode->balance=0;
 nnode->parent=parent;
 nnode->LEFT=nnode->RIGHT=NIL_NODE;
 if(parent==NIL_NODE)
 {
  *rootp=newnode;
  return(newnode);                   /* just created tree */
 }

 *siblingp(parent,cmp_dir(cmp))=newnode;
 child=newnode;

 /*
  * Back up until tree is balanced.  This is achieved when either
  * the tree is balanced by rotation or a node's balance becomes 0.
  */

 do
 {
  pp=xptr(parent);
  d=direction(pp,child);
  if(pp->balance==dir_bal(d))
  {
   balance(rootp,parent,d);
   return(newnode);
  }
  else
  if((pp->balance+=dir_bal(d))==0) return(newnode);
  child=parent;
  parent=pp->parent;
 } while(parent!=NIL_NODE);

 return(newnode);
}





/*
 * Tfind searches node key in the tree rooted by *rootp, using compar for
 * comparing elements.  It returns the pointer to the NODE in which
 * the key pointer resides, or 0 if key is not present.
 */


static int tfind(char *  key,int rootp)
{
 symstr * nodep;
 int      node;
 int      cmp;

 if(rootp==-1) return(NIL_NODE);

 node=rootp;
 while(node!=NIL_NODE)
 {
  nodep=xptr(node);
  if((cmp=strcmp(key,nodep->key))==0) return(node);
  node=*sibling(nodep,cmp_dir(cmp));
 }

 return(NIL_NODE);
}







/* given a name, add it to table, return offset */

int xadd(char * name,int val,int type,int mode)
{
 symstr * p;
 int      len;
 int      node;

 len=strlen(name)+sizeof(symstr);
 if(len & 0x3) len+=4-(len & 0x3);

 flex_chunk((flex_ptr)&xsymheap,xheapsize+len,XHEAPCHUNK);
 node=xheapsize;
 p=xptr(xheapsize);
 xheapsize+=len;

 strcpy(p->key,name);
 p->type=type;
 p->val=val;
 p->mode=mode;
 p->args=0;
 p->argc=0;

 tsearch(node,&xsyms[xnsyms-1].root);

 return(node);
}





/* given a name, return symbol table offset, or -1 if it does not exist */

int xfind(char * name)
{
 int     stage;
 int     hit;
 int     lo;
 int     hi;
 int     probe;
 int     code;

 for(stage=xnsyms-1;stage>=0;stage--)
  if((hit=tfind(name,xsyms[stage].root))!=-1) return(hit);

 lo=0;
 hi=symtablesize-1;
 while(1)
 {
  probe=(lo+hi)/2;
  code=strcmp(fntable[probe].name,name);
  if(!code)  return(-(probe+1));
  if(code>0) hi=probe-1;
  else       lo=probe+1;
  if(lo>hi) break;
 }
 return(XSNOTFOUND);
}



/* given a name, return symbol table offset, or -1 if it does not exist */
/* only one stage */

int xfinds(char * name,int stage)
{
 int hit;

 hit=tfind(name,xsyms[stage-1].root);

 return(hit==-1?XSNOTFOUND:hit);
}




/*removes 'stage', and any newer stages too */

void xremstage(int stage)
{
 xnsyms=stage-1;
 xheapsize=xsyms[xnsyms].heap;
 flex_chunk((flex_ptr)&xsyms,xnsyms*sizeof(int),XSYMCHUNK);
 flex_chunk((flex_ptr)&xsymheap,xheapsize,XHEAPCHUNK);
}




/* adds another stage to the symbol table */
/* notice first stage is number 1 */

int xaddstage(void)
{
 xnsyms++;
 flex_chunk((flex_ptr)&xsyms,xnsyms*sizeof(int),XSYMCHUNK);
 xsyms[xnsyms-1].heap=xheapsize;
 xsyms[xnsyms-1].root=NIL_NODE;
 return(xnsyms);
}



static int fncmp(const void * p1,const void * p2)
{
 return(strcmp(((fndefn *)p1)->name,((fndefn *)p2)->name));
}


/* called once boots symbol table */

void xsymstart(void)
{
 xnsyms=0;
 flex_alloc((flex_ptr)&xsymheap,0);
 flex_alloc((flex_ptr)&xsyms,0);
 xheapsize=0;

 symtablesize=xsymtablestart();
}



int symfntype(int argc,int sym,int * mode)
{
 int args;
 int c;

 if(sym<0)
 {
  c=fntable[-(sym+1)].args[argc];

  if(c=='R') 
  {
   *mode=PREF;
   return(PSTR);
  }
  else
  {
   *mode=0;
   if(c=='S') return(PSTR);
   else       return(PINT);
  }
 }
 else
 {
  args=xptr(sym)->args;
  args=(args>>(argc*2)) & 0x3;

/*  dprintf(0,"read argc=%d type=%d\n",argc,args); */

  *mode=((args & 0x2)>>1)+1;
  return((args & 0x1)+1);
 }
}


void setsymfntype(int argc,int sym,int type,int mode)
{
 symstr * sx;
 int      args;

 sx=xptr(sym);
 args=sx->args;

 argc*=2;
 args&=~(3<<argc);
 args|=(((type-1)+((mode-1)<<1))<<argc);

/*  dprintf(0,"set argc=%d type=%d mode=%d\n",argc/2,type,mode); */

 xptr(sym)->args=args;
}


