states.c

MPICH是MPI的重要研究,提供了一系列的接口函数,为并行计算的实现提供了编程环境.

}


static int CompareStartTimes( a, b )
  /* all right, who at Sun made this brilliant decision? */
#if !(defined(sparc) || defined(hpux)) || defined(__STDC__)
const
#endif
void *a, *b;
{
  if (ListItem( compareData->list, stateInfo, *(int*)a ).startTime >
      ListItem( compareData->list, stateInfo, *(int*)b ).startTime) {
    return 1;
  } else {
    return -1;
  }
}


static int CompareEndTimes( a, b )
#if !(defined(sparc) || defined(hpux)) || defined(__STDC__)
const
#endif
void *a, *b;
{
  if (ListItem( compareData->list, stateInfo, *(int*)a ).endTime >
      ListItem( compareData->list, stateInfo, *(int*)b ).endTime) {
    return 1;
  } else {
    return -1;
  }
}
#endif
  /* USE_QSORT */



static int SortStart( state_data, a, n )
stateData *state_data;
int *a, n;     /* array and the number of elements in it */
{
#if USE_QSORT

  SetCompareData( state_data );
  qsort( (void*)a, n, sizeof(int), CompareStartTimes );
  return 0;

#else
  register int temp;
  register double time;
  int i, m, c;  /* insertPt, movePt, current */

  for (c=1; c<n-1; c++) {
    temp = a[c];
    time = ListItem( state_data->list, stateInfo, a[c]).startTime;
    for (i=c; i && time < ListItem( state_data->list,
				    stateInfo, a[i-1]).startTime;
	 i--);
    for (m=c-1; m>=i; m--)
      a[m+1] = a[m];
    a[i] = temp;
  }
  return 0;
#endif

}



static int SortEnd( state_data, a, n )
stateData *state_data;
int *a, n;     /* array and the number of elements in it */
{
#if USE_QSORT

  SetCompareData( state_data );
  qsort( (void*)a, n, sizeof(int), CompareEndTimes );
  return 0;

#else
  register int temp;
  register double time;
  int i, m, c;  /* insertPt, movePt, current */

  for (c=1; c<n-1; c++) {
    temp = a[c];
    time = ListItem( state_data->list, stateInfo, a[c]).endTime;
    for (i=c; i && time < ListItem( state_data->list,
				    stateInfo, a[i-1]).endTime;
	 i--);
    for (m=c-1; m>=i; m--)
      a[m+1] = a[m];
    a[i] = temp;
  }
  return 0;
#endif

}




static int PushState( state_data, proc, type, time )
stateData *state_data;
int proc, type;
double time;
{
  register statePost *post, *parentPost;
  int slot, nslots, slotFound;
  statePost newPost;

#if DEBUG>1
  fprintf( stderr, "Pushing state %d on proc %d at %f\n", type, proc, time );
#endif

  newPost.time = time;
  newPost.type = type;
  newPost.parent = -1;
  newPost.children = 0;		/* don't always create the list */
  newPost.hangover = -1;
  newPost.firstChild = -1;
  newPost.am_hangover = 0; 

  /* ListVerify( state_data->stacks[proc], statePost ); */

  /* look for an empty slot */
  slotFound = -1;
  parentPost = 0;
  post = ListHeadPtr( state_data->stacks[proc], statePost );
  nslots = ListSize( state_data->stacks[proc], statePost );
  for (slot=0; slot<nslots; slot++, post++ ) {
#if DEBUG>2
    fprintf( stderr, "On proc %d, slot %d is %d %f %d %d %p\n",
             proc, slot, post->type, post->time, post->parent,
	     post->hangover, (void*)post->children );
#endif
      /* if the slot is empty */
    if (post->type == -1) {
        /* and a slot hasn't been found yet, remember this slot */
      if (slotFound == -1) {
	slotFound = slot;
      }
    } else {
        /* if the slot is not empty, keep track of the latest post */
      if (!parentPost || post->time > parentPost->time) {
	  /* find latest post, it is the parent of this guy */
	parentPost = post;
	  /* save parent's slot, so I can add myself to his
	     child list when I exit */
	newPost.parent = slot;
      }
    }
  }

    /* if a parent was found set overlap level to parent's plus one */
  newPost.overlapLevel = (parentPost) ? parentPost->overlapLevel + 1 : 0;

  if (slotFound == -1) {
      /* add to the end */
    ListAddItem( state_data->stacks[proc], statePost, newPost );
      /* set slotFound to the end of the list */
    slotFound = slot;
  } else {
    ListItem( state_data->stacks[proc], statePost, slotFound ) = newPost;
  }
  
    /* tell my parent who they would be leaving behind should they
       choose to end before me */
  if (parentPost) {
    parentPost->hangover = slotFound;
  }

  /* ListVerify( state_data->stacks[proc], statePost ); */

  return 0;
}




/* 
 * FindMatchingPost 
 *
 * look for a matching start event for this state type
 */

static int FindMatchingPost( state_data, proc, type )
stateData *state_data;
int proc, type;
{
  register statePost *post, *latestPost;
  int i, n, latestIdx;

  /* ListVerify( state_data->stacks[proc], statePost ); */

#if DEBUG>1
  fprintf( stderr, "Find matching post on proc %d of state type %d\n",
	   proc, type );
#endif

  latestPost = 0;
  latestIdx = -1;

    /* find matching end of this state */
  post = ListHeadPtr( state_data->stacks[proc], statePost );
  n = ListSize( state_data->stacks[proc], statePost );
  for (i=0; i<n; i++, post++) {
#if DEBUG>2
    fprintf( stderr, "On proc %d, slot %d is %d %f %d %d %p\n",
             proc, i, post->type, post->time, post->parent,
	     post->hangover, (void*)post->children );
#endif
      /* if the type matches, and either nothing else has been found
	 yet, or the time of this post is later han any other,
	 make a note of where we are */
    if (post->type == type && (!latestPost ||
			       post->time > latestPost->time )) {
      latestIdx = i;
      latestPost = post;
    }
  }

#if DEBUG>1
  fprintf( stderr, "Matching start of state found in slot %d\n",
	   latestIdx );
#endif

  return latestIdx;
}



  /* return information about a post by packing it into a stateInfo struct */

static int GetPostInfo( state_data, proc, slot_no, info )
stateData *state_data;
int proc, slot_no;
stateInfo *info;
{
  statePost *post;

  post = ListHeadPtr( state_data->stacks[proc], statePost ) + slot_no;

  info->startTime = post->time;

    /* if my parent has already exited, they have set my am_hangover
       field to 1, and put their FRP in my parent field. */
  info->parent = (post->am_hangover) ? post->parent : -1;
  info->firstChild = post->firstChild;
  info->overlapLevel = post->overlapLevel;

  return 0;
}




  /* take care of all the kids and stuff */

static int ClosePost( state_data, proc, slot_no, finalRestingPlace )
stateData *state_data;
int proc, slot_no, finalRestingPlace;
{
  statePost *post, *parentPost;
  stateInfo *parentFRP;
  int i, *childIdxPtr;

    /* get pointer to post information */
  post = ListHeadPtr( state_data->stacks[proc], statePost ) + slot_no;

  if (post->am_hangover) {
      /* if my parent has already exited, they have set my am_hangover
	 field to 1, and put their FRP in my parent field. */
      /* check if I am their first child */
    parentFRP = ListHeadPtr( state_data->list, stateInfo ) + post->parent;
    if (parentFRP->firstChild == -1) {
      parentFRP->firstChild = finalRestingPlace;
    }
  } else {
      /* if I have a parent on the stack, add me to its 'children' list */
    if (post->parent != -1) {
        /* set parentPost to point to my parent's post */
      parentPost = ListHeadPtr( state_data->stacks[proc], statePost ) +
	post->parent;

        /* mark this guy as having a parent, but the parent isn't
	   finished yet */
      post->parent = -2;

      parentPost->hangover = -1;
      if (!parentPost->children) {
	ListCreate( parentPost->children, int, 3 );
	  /* if I have to create the children list, I am his first child */
	parentPost->firstChild = finalRestingPlace;
      }
      ListAddItem( parentPost->children, int, finalRestingPlace );
#if DEBUG>2
      fprintf( stderr, "Add me (%d) to parent's child list (parent at %d)\n",
	      finalRestingPlace, post->parent );
#endif
    }
  }

    /* go through my list of children and inform them where I ended up */
  if (post->children) {
    childIdxPtr = ListHeadPtr( post->children, int );
    for (i=0; i<ListSize( post->children, int ); i++,childIdxPtr++) {
      ListItem( state_data->list, stateInfo, *childIdxPtr ).parent
	= finalRestingPlace;
#if DEBUG>2
      fprintf( stderr, "Telling child at %d that I'll be at %d\n",
	       *childIdxPtr, finalRestingPlace );
#endif
    }
    ListDestroy( post->children, int );
  }

  /* check for a child that may be dangling */
  if (post->hangover != -1) {
      /* this kid should remember to check if I got my firstChild set */
    ListItem( state_data->stacks[proc], statePost,
	      post->hangover ).parent = finalRestingPlace;
    ListItem( state_data->stacks[proc], statePost,
	      post->hangover ).am_hangover = 1;
#if DEBUG>2
    fprintf( stderr, "Dangling child at %d told I'm at %d\n",
	     post->hangover, finalRestingPlace );
#endif
  }

  post->type = -1;		/* mark this slot as unused */

  /* ListVerify( state_data->stacks[proc], statePost ); */

  return 1;
}



#if TESTING

int PrintStates( state_data )
stateData *state_data;
{
  int doIndices, nstates, i, *idx, proc;
  stateInfo *info, *masterList;

  doIndices = state_data->idx_start != 0;

  nstates = ListSize( state_data->list, stateInfo );
  masterList = info = ListHeadPtr( state_data->list, stateInfo );

  fprintf( stderr, "Master state instance list:\n" );
  for (i=0; i<nstates; i++,info++) {
    fprintf( stderr, "State %d: from %f to %f, proc %d, type %d, parent %d, firstBorn %d\n",
	    i, info->startTime, info->endTime, info->proc,
	    info->type, info->parent, info->firstChild );
  }

#if TESTING>1
  if (doIndices) {
    fprintf( stderr, "Index by start time:\n" );
    idx = ListHeadPtr( state_data->idx_start, int );
    nstates = ListSize( state_data->idx_start, int );
    for (i=0; i<nstates; i++,idx++) {
      info = masterList + *idx;
      fprintf( stderr,
	       "State %d: from %f to %f, proc %d, type %d, parent %d\n",
	       i, info->startTime, info->endTime, info->proc,
	       info->type, info->parent );
    }

    fprintf( stderr, "Index by end time:\n" );
    idx = ListHeadPtr( state_data->idx_end, int );
    nstates = ListSize( state_data->idx_end, int );
    for (i=0; i<nstates; i++,idx++) {
      info = masterList + *idx;
      fprintf( stderr,
	       "State %d: from %f to %f, proc %d, type %d, parent %d\n",
	       i, info->startTime, info->endTime, info->proc,
	       info->type, info->parent );
    }

    for (proc=0; proc<state_data->np; proc++) {
      fprintf( stderr, "State instances on process %d\n", proc );

      fprintf( stderr, "Index by start time:\n" );
      idx = ListHeadPtr( state_data->idx_proc_start[proc], int );
      nstates = ListSize( state_data->idx_proc_start[proc], int );
      for (i=0; i<nstates; i++,idx++) {
        info = masterList + *idx;
        fprintf( stderr,
  	       "State %d: from %f to %f, proc %d, type %d, parent %d\n",
  	       i, info->startTime, info->endTime, info->proc,
  	       info->type, info->parent );
      }
  
      fprintf( stderr, "Index by end time:\n" );
      idx = ListHeadPtr( state_data->idx_proc_end[proc], int );
      nstates = ListSize( state_data->idx_proc_end[proc], int );
      for (i=0; i<nstates; i++,idx++) {
        info = masterList + *idx;
        fprintf( stderr,
		 "State %d: from %f to %f, proc %d, type %d, parent %d\n",
		 i, info->startTime, info->endTime, info->proc,
		 info->type, info->parent );
      }
    }
  }
#endif

  return 0;
}
#endif



int State_Draw( state_data, idx )
stateData *state_data;
int idx;
{
  drawStateFnList *node;
  stateInfo *info;
  int type, proc, parent, firstChild, overlapLevel;
  double startTime, endTime;

#if DEBUG>1
  fprintf( stderr, "DrawState called\n" );
#endif

  if (!(node = state_data->draw.fn_list)) return 0;

#if DEBUG>1
  fprintf( stderr, "calling some functions, starting with %p\n",
	   (void *)node->fn );
#endif

  if (idx != -1) {
    info	 = ListHeadPtr( state_data->list, stateInfo ) + idx;
    type	 = info->type;
    proc	 = info->proc;
    startTime	 = info->startTime;
    endTime	 = info->endTime;
    parent	 = info->parent;
    firstChild	 = info->firstChild;
    overlapLevel = info->overlapLevel;
  } else {
      /* index -1 signifies that the last of the state events has
	 been sent */
    info = 0;
    type = startTime = endTime = 0;
    proc = parent = firstChild = overlapLevel = -1;
  }
  do {
      /* nonzero return value means to halt immediately */
    if ((*node->fn)( node->data, idx, type, proc,
		     startTime, endTime, parent, firstChild, overlapLevel )) {
      break;
    }
    node = node->next;
  } while (node);
  return 0;
}


void *State_AddDraw( state_data, fn, data )
stateData *state_data;
drawStateFn *fn;
void *data;
{
  drawStateFnList *node;

  node = (drawStateFnList*) malloc( sizeof(drawStateFnList) );

  node->fn = fn;
  node->data = data;
  node->next = state_data->draw.fn_list;
  state_data->draw.fn_list = node;

  return (void*)node;
}


/**********************************************************************\
* Remove a function from the draw() list                               *
* Return 0 if the function pointer was successfully found and removed. *
* Return -1 if the function pointer was not found.                     *
\**********************************************************************/

int State_RmDraw( state_data, token )
stateData *state_data;
void *token;
{
  drawStateFnList *node, *prev, *toDelete;

  toDelete = token;

    /* if null pointer given, or the list is empty, return with error */
  if (!toDelete || !(node = state_data->draw.fn_list)) return -1;

  prev = 0;

  do {
    if (node == toDelete) {
      if (!prev) {
	  /* first item in the list */
	state_data->draw.fn_list = node->next;
	free( node );
	return 0;
      } else {
	prev->next = node->next;
	free( node );
	return 0;
      }
    }
    prev = node;
    node = node->next;
  } while (node);

    /* couldn't find the function */
  return -1;
}

#if 0

int StateOverlapLevel( state_data, idx, vis )
stateData *state_data;
int idx;			/* index of state instance */
Vis *vis;			/* list of visible states */
{
  stateInfo *list;
  int level, next;

  list = ListHeadPtr( state_data->list, stateInfo );
  level = 0;
  
  next = idx;
  while (list[next].parent != -1) {
    next = list[next].parent;
    level++;
  }

#if DEBUG>1
  fprintf( stderr, "Overlap level for state %d is %d\n", idx, level );
#endif

  return level;
}

#endif