C:/Simulate/Napados/Source/sn.c

Go to the documentation of this file.

/* ** SORT NODES **************************************************************************************************************** */
 
#undef  EXTERN
#define EXTERN extern
 
#include "./napa.h"
#include "./proto.h"
 
 
/* *** In this file: ************************************************************************************************************ */
 
/* void build_node_dependencies(void)                                                                                             */
/* void build_to_be_delayed_node_list(void)                                                                                       */
/* void sort_nodes(void)                                                                                                          */
 
 
/* ****************************************************************************************************************************** */
 
/* "sort_nodes" will rearrange the list of nodes to introduce the necessary path from input to output, including a delay when     */
/* explicitely asked. Delays are sorted first.                                                                                    */
 
/* Nodes are sorted. Checks are done at the end of sorting. Undetermination is caused by faulty loops (no delay, all delays) or   */
/* missing sources.                                                                                                               */
 
/* A node is determined if it is not depending on any other nodes, or if it is depending on determined nodes only.                */
/* It is assumed that no node is determined at the beginning of the process. A pointer is set to the first entry at start.        */
 
/* This process is awfully long as soon as the number of nodes becomes large.                                                     */
/* A thousand of nodes is enough to slow down significantly the sorting process.                                                  */
 
 
/* ****************************************************************************************************************************** */
 
/* Build the list of node dependencies, smash directives if any.                                                                  */
/* Directives are smashed first to detect non obvious dependencies.                                                               */
 
/* List of dependencies is a list of ID corresponding to nodes in the node definition. If a record is detected, check also for    */
/* hidden node dependencies. Records must be expanded before sorting nodes!If inside a drop segment, look after nodes there!      */
 
void build_node_dependencies(void) {
  long in1, in2, out;
  char *str1 = (char*) NULL;
  char *str2 = (char*) NULL;
  char tok[STRLENGTH] = {'\0'};
  char sgn[2]         = {'\0'};
  long num;
  long *p = (long*) NULL;
  for (out = 0L; out < Num_Nodes; out++) {
    num  = 0L;
    str1 = Node_List[out].value;
    for (;;) {                                                                /* count number of nodes in the node definition     */
      str1 = get_sign_and_token(str1, sgn, tok);
      if (ISEMPTY(tok)) {
        break;
      }
      in1 = node_id(tok);
      if (UNDEFINED != in1) {
        num++;
      }
      in1 = record_id(tok);
      if (UNDEFINED != in1) {
        str2 = Record_List[in1].list1;
        for (;;) {                                                            /* count number of nodes in the record definition   */
          str2 = get_sign_and_token(str2, sgn, tok);
          if (ISEMPTY(tok)) {
            break;
          }
          in2 = node_id(tok);
          if (UNDEFINED != in2) {
            num++;
          }
        }
      }
    }                                                                         /* 'num' is the number of nodes in netlist          */
    Node_List[out].depend = (long*) malloc((size_t) ((long) (sizeof (long)) * (num+1L)));
    if ((long*) NULL == Node_List[out].depend) {
      print_error_location("node dependency", Node_List[out].mline, Node_List[out].mfile);
      (void) fprintf(STDERR, " dynamic memory allocation error\n");
      print_error_banner_and_exit();
    }
    p    = Node_List[out].depend;
    str1 = Node_List[out].value;
    for (;;) {
      str1 = get_sign_and_token(str1, sgn, tok);
      if (ISEMPTY(tok)) {
        break;
      }
      in1 = node_id(tok);
      if (UNDEFINED != in1) {
        *p = Node_List[in1].ID;                                               /* add node ID to dependency list                   */
        p++;
      }
      in1 = record_id(tok);
      if (UNDEFINED != in1) {
        str2 = Record_List[in1].list1;
        for (;;) {
          str2 = get_sign_and_token(str2, sgn, tok);
          if (ISEMPTY(tok)) {
            break;
          }
          in2 = node_id(tok);
          if (UNDEFINED != in2) {
            *p = Node_List[in2].ID;                                           /* add node ID to dependency list                   */
            p++;
          }
        }
      }
    }
    *p = -1L;                                                                 /* to terminate the array                           */
  }
  return;
}
 
 
void sort_nodes(void) {
  long in;
  long out, out2;
  long ndel;
  long nseg;
  long determined_ptr;
  long kd;
  long i, k;
  char *str = (char*) NULL;
  long *p   = (long*) NULL;
  int  first, flag, err;
 
  /* ***** First sort the nodes by segment. Qualifier "with" is messing the node list.                                            */
  determined_ptr = 0L;
  for (nseg = 0L; nseg < Num_Segments; nseg++) {
    for (out = 0L; out < Num_Nodes; out++) {
      if (nseg == Node_List[out].segment) {
        swap_nodes(out, determined_ptr);
        out = determined_ptr;
        determined_ptr++;
      }
    }
  }
 
  ndel = Num_Delays;
  determined_ptr = 0L;
 
  /* ***** Sort now the nodes output of DELAYS, all segments.                                                                     */
  for (out = 0L; out < Num_Nodes; out++) {
 
    kd = Node_List[out].kind;
    if ((DELAY1_KIND == kd) || (DELAY2_KIND == kd) || (DELAY3_KIND == kd) || (DELAY_KIND == kd)) {
      in = UNDEFINED;
      for (i = 0L; i < ndel; i++) {                                           /* check if input to some other delay               */
        if (Node_List[out].ID == Delay_Input[i]) {
          in = i;
          break;
        }
      }
      if (UNDEFINED == in) {                                                  /* if not, it can be determined                     */
        Node_List[out].determined = true;
        swap_nodes(out, determined_ptr);
        out = determined_ptr;
        determined_ptr++;
        p = Node_List[out].depend;
        k = *p;
        for (i = 0L; i < ndel; i++) {
          if (Delay_Input[i] == k) {
            ndel--;
            swap_delay_inputs(i, ndel);
            break;
          }
        }
        if (0L == ndel) {                                                     /* all delays are processed                         */
          break;
        }
      }
    }
  }
 
  /* ***** Sort now the other nodes, all segments. Starting from previous location.                                               */
  for (out = determined_ptr; out < Num_Nodes; out++) {
 
    flag  = true;
    first = true;
 
    p = Node_List[out].depend;
 
    for (;;) {                                                                /* check if inputs, one by one, are determined      */
      k = *p;
      if (-1L >= k) {                                                         /* reached end of dependency list                   */
        break;
      }
      flag = false;
      for (i = 0L; i < determined_ptr; i++) {
        if (Node_List[i].ID == k) {
          flag = true;
          break;
        }
      }
      if (!flag) {                                                            /* at least 1 node of dep. list is not determined   */
        if (!first) {                                                         /* move determ. node after undeterm. one (speed up) */
          *p      = *(p-1L);
          *(p-1L) = k;
        }
        break;
      }
      p++;
      first = false;
    }
    if (flag) {
      Node_List[out].determined = true;
      swap_nodes(out, determined_ptr);
      out = determined_ptr;
      determined_ptr++;
    }
  }
 
  /* ***** Verify that all nodes are determined.                                                                                  */
  if ((Num_Nodes - 1L) > determined_ptr) {
    Error_Flag++;
    (void) fprintf(STDERR, "\nNAPA Error:  (static loop)\n");
    (void) fprintf(STDERR, "\n These nodes are involved in one or several static loops:\n");
 
    for (out = determined_ptr; out < Num_Nodes; out++) {                      /* review each undetermined node                    */
      flag = false;
      for (out2 = determined_ptr; out2 < Num_Nodes; out2++) {                 /* check dependency                                 */
        if (out == out2) {
          continue;
        }
        p = Node_List[out2].depend;                                           /* dependencies of out2                             */
        for (;;) {                                                            /* check if node out is in the out2 dependency list */
          k = *p;
          if (-1L >= k) {                                                     /* reached end of dependency list                   */
            break;
          }
          if (Node_List[out].ID == k) {
            flag = true;                                                      /* node is part of the dependency list              */
            break;
          }
          p++;
        }
        if (flag) {
          break;
        }
      }
      if (!flag) {                                                            /* this node does not participate to a loop         */
        swap_nodes(out, determined_ptr);
        determined_ptr++;                                                     /* in this search, we mark it as determined         */
        out = determined_ptr;                                                 /* restart the search                               */
      }
    }
  }
 
  err = false;
  for (nseg = 0L; nseg < Num_Segments; nseg++) {
    flag = true;
    for (out = determined_ptr; out < Num_Nodes; out++) {
      if (Node_List[out].segment == nseg) {
        flag = ((Node_List[out].determined) && (flag)) ? true : false;
      }
    }
    if (!flag) {                                                              /* there is a problem in this segment               */
      (void) fprintf(STDERR, "\n");
      if (1L < Num_Segments) {
        (void) fprintf(STDERR,   " In Segment [%ld]\n", nseg);
      }
      for (out = determined_ptr; out < Num_Nodes; out++) {
        if ((!Node_List[out].determined) && (Node_List[out].segment == nseg)) {
          if ('_' == Node_List[out].name1[0]) {
            str = Node_List[out].name1 + 1;                                   /* suppress underscore in void name                 */
          } else {
            str = Node_List[out].name1;
          }
          (void) fprintf(STDERR, "   -> node  %s\n", str);
        }
      }
      err = true;
    }
  }
 
  if (err) {
    (void) fprintf(STDERR, "\n Your description is not correct. NAPA is not able to sort the nodes of your netlist. \n");
    (void) fprintf(STDERR,   " Check for missing or mispelled nodes or loops of nodes containing no delay or only delays\n\n");
    if (Stuck_Flag) {
      (void) fprintf(STDERR, " You are using 'stuck' instructions. This is generally safe, except if you stuck a node \n");
      (void) fprintf(STDERR, " to another node. In this case, the resulting netlist could be impossible to simulate (loop!).\n");
      (void) fprintf(STDERR, " You could try to remove these particular instructions.\n\n");
    }
  }
  return;
}
 
 
/* ****************************************************************************************************************************** */
/* end of file                                                                                                                    */