sds_tree.c

This Source-Navigator, an IDE for C/C++/Fortran/Java/Tcl/PHP/Python and a host of other languages.

/* $Header: /cvsroot/sourcenav/src/snavigator/demo/c++_demo/sds/sds_tree.c,v 1.1.1.1 2002/04/18 23:35:34 mdejong Exp $ */


#include "Sds/sdsgen.h"
#include "Sds/sds_externs.h"
#include "Sds/sds_tree.h"
#include "Sds/sds_object.h"
#include <string.h>
#include <time.h>
#include <values.h>
#if defined(__MSDOS__)
#include <alloc.h>
#else
#include <malloc.h>
#endif

#define SDS_INITIAL_TNODE 0x01

/********** forward declarations **********/
#if defined (__STDC__)
sds_tnode       * look_on_row(sds_tnode *, char *,int);
char            * nextname(char **);
void              printdesc(sds_tnode *,int,int);
void              printinst(sds_tnode *,int,int);
sds_tnode       * sds_find(int,sds_tnode *, char *,int);
void              printres(sds_tnode *, int);
int               countstruct(sds_tnode *);
struct type_list* maketlist(int);
sds_code          makestruct(sds_tnode *,int *,
                             struct type_list *, struct direc *, int);
int               sds_gnt(void);
sds_tnode *       sds_dup_down(int, sds_tnode *, sds_tnode *);

#else
sds_tnode       * look_on_row();
char            * nextname();
void              printdesc();
void              printinst();
sds_tnode       * sds_find();
void              printres();
struct type_list* maketlist();
sds_code          makestruct();
int               sds_gnt();
sds_tnode *       sds_dup_down();

#endif

int 
sds_tree_handle(sds)
sds_handle sds;
{
  struct sds_control_p *scp = sds_control(sds);
  return scp->tree;
}

int
sds_new_tree(data)
void *data;
{
  sds_treecon *stc = sds_treec();
  int ntree = sds_gnt();
  stc->top[ntree] = sds_new_tnode(data);
  stc->top[ntree]->top = stc->top[ntree];
  stc->top[ntree]->head = stc->top[ntree];
  stc->top[ntree]->ntree = ntree;
  stc->tpos[ntree].ntnodes = 1;
  return ntree + 1;
}

int 
sds_gnt(VOIDDEF)
{
  sds_treecon *stc = sds_treec();
  int i = 0;
  while (i < stc->next_tree && stc->top[i] != 0)
    i++;
  if (i == stc->next_tree)
    stc->next_tree++;
  if (stc->next_tree > sds_max())
  {
    sds_push_error(SDS_NO_SPC, SDS_WARNING," No tree space left");
    return -1;
  }
  return i;
}

sds_tnode *
sds_get_top(itree)
int itree;
{ 
  sds_treecon *stc = sds_treec();
  return itree?stc->top[itree - 1]:0;
}

sds_tnode *
sds_down_tnode(tnode, data)
sds_tnode *tnode;
void *data;
{
  sds_tnode *ndown;
  sds_treecon *stc = sds_treec();
  if (tnode == 0)
  {
    sds_push_error(SDS_NO_SUCH_OBJ,SDS_WARNING,"Down node is null");
    return 0;
  }
  ndown = tnode->down;
  tnode->down = sds_new_tnode(data);
  tnode->down->top = tnode;
  tnode->down->head = tnode->down;
  tnode->down->ntree = tnode->ntree;
  tnode->down->down = ndown;
  stc->tpos[tnode->ntree].ntnodes++;
  return  tnode->down;
}

sds_tnode *
sds_next_tnode(tnode, data)
sds_tnode *tnode;
void *data;
{
  sds_treecon *stc = sds_treec();
  sds_tnode *nnext;
  if (tnode == 0)
  {
    sds_push_error(SDS_NO_SUCH_OBJ,SDS_WARNING,"Next node is null");
    return 0;
  }
  nnext = tnode->next;
  tnode->next = sds_new_tnode(data);
  tnode->next->top = tnode->top;
  tnode->next->head = tnode->head;
  tnode->next->ntree = tnode->ntree;
  tnode->next->next = nnext;
  stc->tpos[tnode->ntree].ntnodes++;
  return  tnode->next;
}

sds_tnode *
sds_new_tnode(data)
void *data;
{
  sds_tnode *n = (sds_tnode *)malloc(sizeof(sds_tnode));
  n->data = data;
  n->next = 0;
  n->down = 0;
  n->top = 0;
  return n;
}

void
sds_start_tree(itree, tnode)
int itree;
sds_tnode *tnode;
{
  if (itree)
  {
    sds_treecon *stc = sds_treec();
    stc->trav[itree-1] = tnode;
    stc->tpos[itree-1].width = 
    stc->tpos[itree-1].depth = (short)0;
    if (!tnode)
    {
      stc->tpos[itree-1].flag = 0;
      stc->tpos[itree-1].top = stc->top[itree-1];
    }
    else
    {
      stc->tpos[itree-1].flag |= SDS_INITIAL_TNODE;
      stc->tpos[itree-1].top = tnode;
    }
  }
  else
    sds_push_error(SDS_NO_SUCH_OBJ,SDS_ERROR,"Illegal tree handle");
}

tree_pos *
sds_get_pos(itree)
int itree;
{ 
  sds_treecon *stc = sds_treec();
  return itree?&stc->tpos[itree-1]:0; 
}

sds_tnode *
sds_dup_down(itree, ttnode, dtnode)
int itree;
sds_tnode *ttnode, *dtnode;
{
  sds_desc *td,*d = (sds_desc *)malloc(sizeof(sds_desc));
  sds_tnode *t,*n, *end;
  if (itree < 0 ) /* sds_trav_tree is not re-entrant, so must signal
                     the first entry       
                   */
  {
    itree = -itree;
  }
  else
  {
    sds_start_tree(itree, ttnode);
    t = sds_trav_tree(itree);
  }
  end = ttnode->next;
  t = sds_trav_tree(itree);
  memcpy((char *)d, (char *)t->data, sizeof(sds_desc));
  n = sds_down_tnode(dtnode,d);
  while ((t = sds_trav_tree(itree)) != end)
  {
    td = (sds_desc *)t->data;
    if (td->type & SDS_INDLIST)
    {
      t = sds_dup_down(-itree,t,n);
      td = (sds_desc *)t->data;
    }
    if (t != end)
    {
      d = (sds_desc *)malloc(sizeof(sds_desc));
      memcpy((char *)d, (char *)td, sizeof(sds_desc));
      n = sds_next_tnode(n, d);
    } 
  }
  return t;
}

sds_tnode *
sds_trav_tree(itree)
int itree;
{
  sds_tnode *n,*next;
  sds_treecon *stc = sds_treec();

  if (!itree) return 0;

  n = stc->trav[itree-1];
  next = 0;
  if (stc->tpos[itree-1].flag & SDS_INITIAL_TNODE)
  {
    stc->tpos[itree-1].flag &= ~SDS_INITIAL_TNODE;
    next = n;
  }
  else if (!n)
  {
    next = stc->top[itree-1];
    stc->tpos[itree-1].width = stc->tpos[itree-1].depth = 0;
  }
  else if (n->down)
  {
    next = n->down;
    stc->tpos[itree-1].width = 0;
    stc->tpos[itree-1].depth++;
  }
  else if (n->next)
  {
    next = n->next;
    stc->tpos[itree-1].width++;
  }
  else if (n->head == stc->tpos[itree-1].top)
    next = 0;
  else
  {
    while ((next = n->top->next) == 0)
    {
      n = n->top;
      stc->tpos[itree-1].depth--;
      if (!stc->tpos[itree-1].depth)
      {
        next = 0;
        stc->tpos[itree-1].depth++;
        break;
      }
    }
    stc->tpos[itree-1].depth--;
  }
  stc->trav[itree-1] = next;
  return next;
}

void 
sds_delete_tree(itree,stnode, truefalse)
int itree,truefalse;
sds_tnode *stnode;
{
  sds_tnode *n,**N;
  sds_treecon *stc = sds_treec();
  int i = 0,count = 0;;

  if (!itree) return;

  N = (sds_tnode **)
             malloc(stc->tpos[itree-1].ntnodes * sizeof(sds_tnode *));
  sds_start_tree(itree, stnode);
  while ((n = sds_trav_tree(itree)) != 0)
  {
    N[i++] = n;  
    count++;
  }
  for (i=0;i<count;i++)
  {
    if (truefalse)
    {
      if (itree == stc->inst_tree)
      {
        sds_inst *in = (sds_inst *)(N[i]->data);
        if (!(--in->refcount))
          free(N[i]->data);
      }
      else
      {
        sds_desc *d = (sds_desc *)(N[i]->data);
        if (!(--d->refcount))
          free(N[i]->data);
      }
    }
    free(N[i]);
  }
  if (count != stc->tpos[itree-1].ntnodes)
    sds_push_error(SDS_NO_SPC,SDS_ERROR,
                           "Tree nodes not accounted for in delete");
  stc->top[itree-1] = 0;
  free(N);
}

sds_tnode *
sds_res(itree)
int itree;
{
  sds_tnode *p,*n,*next;
  sds_desc *d;
  sds_treecon *stc = sds_treec();

  if (!itree) return 0;
  n = stc->trav[itree-1];
  next = 0;

  if (n) /* Current node loaded */
    d = (sds_desc *)n->data;
  if (!n) /* Starting the tree; initialise the structure counters */
  {
    while ((p = sds_trav_tree(itree)) != 0)
    {
     d = (sds_desc *)p->data;
     if (d->type & SDS_INDLIST)
       d->mark = d->nelems;
    }
    next = stc->top[itree-1];
  }
  else if (n->down) /* Go down if possible */
    next = n->down;
  else if (n->next) /* or get the next in the list */
    next = n->next;
  else if (n->head == stc->tpos[itree-1].top) /* exit if we're at the top */
    next = 0;
  else if (((sds_desc *)(n->top->data))->mark) /* or get the next structure */
    next = n->top;
  else /* We've done all the structures, keep going up */
  {
    ((sds_desc *)(n->top->data))->mark = ((sds_desc *)(n->top->data))->nelems;
    while ((next = n->top->next) == 0)
    {
      n = n->top;
      if (n == stc->top[itree-1])
      {
        next = 0;
        break;
      }
    }
  }
  stc->trav[itree-1] = next;
  if (next)
  {
    d = (sds_desc *)next->data;
    if (d->type & SDS_INDLIST)
      d->mark--;
  }
  return next;
}

sds_tnode * 
sds_check_sizes(itree)
int itree;
{
  sds_tnode *n;
  sds_desc *d;
  int fp = 1;
  long start = 0L;

  sds_start_tree(itree, 0);
  while ((n = sds_trav_tree(itree)) != 0)
  {
    d = (sds_desc *)n->data;
    if (fp)
    {
      fp = 0;
      if (d->type != SDS_SDS)
        start = d->offset;
    }
    printf("%s [%d] sizes %x %x, align %d %d, addrs %x %x\n",d->name,
             d->nelems, d->size, d->ssize,
             (int)d->align & 0xff,(int)d->salign & 0xff,
             (int)d->offset - start, (int)d->soffset);
  }
  return 0;
}

sds_inst * 
sds_new_inst(nelems, name, type)
sds_code nelems,type;
char *name;
{
  sds_inst *i = (sds_inst *)malloc(sizeof(sds_inst));
	i->name = name;
	i->number = nelems;
	i->pointer = 0;
	i->def = 0;
	i->was_allocated = 0;
	i->refcount = 0;
	return i;
}

sds_desc *
sds_new_desc(nelems, name, type)
sds_code nelems,type;
char *name;
{
  sds_desc *d = (sds_desc *)malloc(sizeof(sds_desc));
  d->nelems = nelems;
  d->name = name;
  d->type = type;
  d->size = 0L;
  d->ssize = 0L;
  d->offset = 0L;
  d->soffset = 0L;
  d->align = (char)0;
  d->salign = (char)0;
  d->mark = 0L;
  d->refcount = (char)1;
  return d;
}

void 
sds_print_tree(itree,values)
int itree,values;
{
  sds_treecon *stc = sds_treec();
  tree_pos * pos = sds_get_pos(itree);
  sds_tnode *n;

  if (itree == stc->inst_tree)
    while ((n = sds_trav_tree(itree)) != 0)
      printinst(n, (int)pos->depth, values);
	else
    while ((n = sds_trav_tree(itree)) != 0)
      printdesc(n, (int)pos->depth, values);
}

void
sds_makeaddr(itree,nstart,sstart)
int itree;
void * nstart,* sstart;
{
  sds_tnode *n;
  sds_desc *d;
  long off = (long)nstart,soff = (long)sstart;

  while ((n = sds_trav_tree(itree)) != 0)
  {
    d = (sds_desc *)n->data;
    off += align_delta(off, d->align);
    soff += align_delta(soff, d->salign);
    d->offset = off;
    d->soffset = soff;
    if (!(d->type & SDS_INDLIST) && (d->type != SDS_BITFIELD))
    {
      off += d->size * d->nelems;
      soff += d->ssize * d->nelems;
    }
  }
}

void
printres(n,arc)
sds_tnode *n;
int arc;
{
  sds_desc *d = (sds_desc *)n->data;
  if (d->type < NPRIMITIVES && d->type != SDS_SDS)
    printf("%d %s, %d bytes on %d at %x: on %d\n",d->nelems,
                     type_name[d->type],
                     d->size,
                     (int)d->align & 0xff,
                     d->offset,
                     (int)sds_arc_palign(arc, d->type) & 0xff);
}

void
printinst(n, depth, values)
sds_tnode *n;
int depth;
int values;
{
  sds_inst *i;

  pindent(depth);
  i = (sds_inst *)n->data;
	printf("Object %s, multiplicity %d at %x,",i->name,i->number,i->pointer);
	if (i->was_allocated)
		printf("allocated,");
  printf("refcount %d\n",i->refcount);
	if (i->def)
		printdesc(i->def,depth,values);
  else
	{
    pindent(depth);
		printf("Primitive %s, %d\n",type_name[i->code],i->number);
	}
}

void
printdesc(n, depth, values)
sds_tnode *n;
int depth;
int values;
{
  sds_desc *d;

  pindent(depth);