Subversion Repositories Vertical

Rev

Rev 2 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /* $Id: sorting.c,v 1.1.1.1 2003/11/04 23:34:57 mjames Exp $
  2.  *
  3.  * $Log: sorting.c,v $
  4.  * Revision 1.1.1.1  2003/11/04 23:34:57  mjames
  5.  * Imported into local repositrory
  6.  *
  7.  * Revision 1.14  2002/10/02 18:39:54  MJAMES
  8.  * Stopped copying pin_col to index on every node
  9.  *
  10.  * Revision 1.13  2002/09/16 14:41:43  mjames
  11.  * Merge back pin indexing bug that meant
  12.  * pin AZ12 was indistinguishable from pin Z12 in
  13.  * rename ident/name commands
  14.  *
  15.  * Revision 1.12  2002/09/09 10:10:21  mjames
  16.  * Moved pin remapping function to pin ident editing function from
  17.  * sorting pin name routine.
  18.  *
  19.  * Revision 1.11  2002/09/09 09:53:01  mjames
  20.  * Moved pin remapping function to pin ident editing function from
  21.  * sorting pin name routine.
  22.  *
  23.  * Revision 1.10  2002/08/23 14:13:55  mjames
  24.  * Added legal/illegal pin identifying letters to the header file.
  25.  * Upgraded sort to determine row/column locations of pins identified like
  26.  * 'a1' and '1a' etc or '1' , '2'
  27.  *
  28.  * Revision 1.9  2001/10/31 22:33:27  mjames
  29.  * Suppress diagnostic print
  30.  *
  31.  * Revision 1.8  2001/10/31 22:20:17  mjames
  32.  * Tidying up problematical comments caused by CVS
  33.  * 'intelligent' comment guessing
  34.  *
  35.  * Revision 1.7  2001/10/31 16:15:36  mjames
  36.  * Added a datastructure to hide regular expression information from programs.
  37.  *
  38.  * Revision 1.6  2001/10/22 10:53:50  mjames
  39.  * Added a declaration of the Vertical regular expression compiler
  40.  * which validates and complains about older 'regular expressions'
  41.  * used by Vertical prior to using regexp in the C library
  42.  *
  43.  * Revision 1.5  2001/10/10 20:17:59  mjames
  44.  * Added a vert_regcomp function to compile regular expressions
  45.  * with '^' (match start string) and  '$' (match end string) bracketing
  46.  * this => wildcard must match entire string not just a part of it.
  47.  *
  48.  * Revision 1.4  2001/09/16 20:36:03  mjames
  49.  * Second attempt to modify wire bundles to be connector rather than net
  50.  * centric. Allows more than one connector to carry the same net,
  51.  *
  52.  * Revision 1.3  2001/09/16 19:48:53  mjames
  53.  * Modified sorting algorithm to have sideffect of calculating pin rows and
  54.  * columns for sockets.
  55.  *
  56.  * Revision 1.2  2001/06/06 12:10:17  mjames
  57.  * Move from HPUX
  58.  *
  59.  * Revision 1.1.1.1  2000/10/19 21:58:40  mjames
  60.  * Mike put it here
  61.  *
  62.  *
  63.  * Revision 1.24  2000/10/04  10:37:10  10:37:10  mjames (Mike James)
  64.  * Modified for Vertical2 : support COMPONENTS and SIGNALS
  65.  *
  66.  * Revision 1.24  2000/10/04  10:37:10  10:37:10  mjames (Mike James)
  67.  * Part of Release PSAVAT01
  68.  *
  69.  * Revision 1.23  2000/10/02  11:04:21  11:04:21  mjames (Mike James)
  70.  * new_vhdl
  71.  *
  72.  * Revision 1.22  2000/09/27  14:42:21  14:42:21  mjames (Mike James)
  73.  * Part of Release Sep_27_ST_2000
  74.  *
  75.  * Revision 1.21  2000/09/21  10:15:51  10:15:51  mjames (Mike James)
  76.  * Part of Release Sep21Alpha
  77.  *
  78.  * Revision 1.20  2000/08/25  09:57:16  09:57:16  mjames (Mike James)
  79.  * Part of Release Aug25_alpha
  80.  *
  81.  * Revision 1.19  2000/08/16  08:57:33  08:57:33  mjames (Mike James)
  82.  * Part of Release CD01_Aug2000
  83.  *
  84.  * Revision 1.18  2000/08/14  14:45:13  14:45:13  mjames (Mike James)
  85.  * Part of Release Aug_14_2000
  86.  *
  87.  * Revision 1.17  2000/08/11  08:30:34  08:30:34  mjames (Mike James)
  88.  * Part of Release Aug_11_2000
  89.  *
  90.  * Revision 1.16  2000/08/09  10:31:49  10:31:49  mjames (Mike James)
  91.  * Part of Release Aug__9_2000
  92.  *
  93.  * Revision 1.15  2000/05/31  11:43:00  11:43:00  mjames (Mike James)
  94.  * Part of Release May_31_2000
  95.  *
  96.  * Revision 1.14  2000/05/08  17:01:40  17:01:40  mjames (Mike James)
  97.  * Part of Release May__8_2000
  98.  *
  99.  * Revision 1.13  2000/05/08  16:59:33  16:59:33  mjames (Mike James)
  100.  * Part of Release May__8_2000
  101.  *
  102.  * Revision 1.12  2000/05/08  16:57:10  16:57:10  mjames (Mike James)
  103.  * Part of Release May__8_2000
  104.  *
  105.  * Revision 1.11  2000/03/08  16:19:31  16:19:31  mjames (Mike James)
  106.  * New version including PC
  107.  *
  108.  * Revision 1.8  2000/01/20  15:58:50  15:58:50  mjames (Mike James)
  109.  * Part of Release R22
  110.  *
  111.  * Revision 1.7  99/12/22  11:15:31  11:15:31  mjames (Mike James)
  112.  * Part of Release Dec_22_1999
  113.  *
  114.  * Revision 1.6  99/06/25  14:35:51  14:35:51  mjames (Mike James)
  115.  * Added in reference to expression.h, but no changes made
  116.  * to the function of acfread yet.
  117.  *
  118.  * Revision 1.5  99/05/04  09:52:52  09:52:52  mjames (Mike James)
  119.  * General checkin
  120.  *
  121.  * Revision 1.4  98/02/11  11:27:19  11:27:19  mjames (Mike James)
  122.  * Checked in for version 6.2a
  123.  *
  124.  * Revision 1.3  97/04/23  08:43:25  08:43:25  mjames (Mike James)
  125.  * CHecked in for release rel23041997
  126.  *
  127.  * Revision 1.2  96/12/23  15:17:00  15:17:00  mjames (Mike James)
  128.  * Altered because find_socket takes a reference
  129.  * to the head-of-list-pointer noth the pointer itself.
  130.  *
  131.  * Revision 1.1  96/12/23  10:26:21  10:26:21  mjames (Mike James)
  132.  * Initial revision *  */
  133.  
  134. #include <stdio.h>
  135. #include <string.h>
  136. #include <stdlib.h>
  137. #include <ctype.h>
  138.  
  139. #include <sys/types.h>
  140. #include <regex.h>
  141.  
  142. /* TCL/Tk declarations */
  143. #include "vertcl_main.h"
  144. #include "expression.h"
  145. #include "generic.h"
  146. #include "database.h"
  147. #include "routing.h"
  148. #include "cmdparse.h"
  149. #include "cmdlog.h"
  150. #include "sorting.h"
  151.  
  152.  
  153. #ident "@(#)$Header: c:\\cygwin\\cvsroot/Vert03/vertlib/sorting.c,v 1.1.1.1 2003/11/04 23:34:57 mjames Exp $";
  154.  
  155.  
  156. /* the comparison function  : requires upgrade for checking :
  157.    A1...A10 then B1..B10 or is it   1a..10a then 1b..10b */
  158. #if defined SORT_ORIGINAL
  159. static int sort_nodes_compar(const void * p,const void * q)
  160. { char * s1 = (*(node_t **)p)->identifier;
  161.   char * s2 = (*(node_t **)q)->identifier;
  162.  
  163.   int l1 = strlen(s1);
  164.   int l2 = strlen(s2);
  165.   if(l1==l2) /* only call strcmp() for same length strings
  166.                 This makes '2' smaller than '19' */
  167.     return strcmp(s1,s2);
  168.   else
  169.     return l1-l2; /* if different lengths, use the shorter name */
  170. }
  171. #else
  172.  
  173.  
  174. /* this sort works for alpha - numeric strings : A1 A2
  175.    use SWAP command to swap identifiers  */
  176. static int sort_nodes_compar(const void * p,const void * q)
  177. {
  178.   char * s1 = (*(node_t **)p)->id_alpha_chars;
  179.   char * s2 = (*(node_t **)q)->id_alpha_chars;
  180.  
  181.   int l1    = (*(node_t **)p)->id_alpha_cnt;
  182.   int l2    = (*(node_t **)q)->id_alpha_cnt;
  183.   int diff = 0;
  184. /*
  185.   printf("cmp p: a %3s[%2d] n %3s[%2d]\n",
  186.    (*(node_t **)p)->id_alpha_chars,
  187.     (*(node_t **)p)->id_alpha_cnt,
  188.     (*(node_t **)p)->id_numeric_chars,
  189.     (*(node_t **)p)->id_numeric_cnt);
  190.   printf("cmp q: a %3s[%2d] n %3s[%2d]\n",
  191.    (*(node_t **)q)->id_alpha_chars,
  192.     (*(node_t **)q)->id_alpha_cnt,
  193.     (*(node_t **)q)->id_numeric_chars,
  194.     (*(node_t **)q)->id_numeric_cnt);
  195. */
  196.  
  197.   if(l1==l2)
  198.     {
  199.     /* only call strcmp() for same length strings */
  200.     diff = strncmp(s1,s2,l1);
  201. /*
  202.     printf("alpha cmp (%s,%s,%d) different %d\n",s1,s2,l1,diff);
  203. */
  204.     if (diff==0) /* alpha same */
  205.       {
  206.       /* otherwise check the numeric parts of the strings */
  207.       /* these have been decoded already */
  208.       l1    = (*(node_t **)p)->pin_row;
  209.       l2    = (*(node_t **)q)->pin_row;
  210.       diff  = l1-l2;
  211. /*
  212.       printf("num different %d\n",diff);
  213. */
  214.       }
  215.     }
  216.   else
  217.     {
  218.     diff = l1-l2; /* if different alpha lengths, use the shorter name */
  219. /*
  220.     printf("alpha len different %d\n",diff);
  221. */
  222.     }
  223. /*
  224.   printf("diff: %d  string %7s row %2d and %7s row%2d\n",diff,
  225.     (*(node_t **)p)->identifier,
  226.     (*(node_t **)p)->pin_row,
  227.     (*(node_t **)q)->identifier,
  228.     (*(node_t **)q)->pin_row);
  229. */
  230.   return diff;
  231.   }
  232.  
  233. #endif
  234.  
  235.  
  236.  
  237.  
  238.  
  239. /* this function sorts all of the pin references on a chip
  240.    into alphanumeric order, and also generates a unique pin index for each pin
  241.    in the case of alphanumeric pin identifiers : pin A1 or 1A will become index 1 */
  242. #define BIG 1000000
  243.  
  244. /* mapping table has no letter 'I' or 'O' in it */
  245. static unsigned char illegal_chars[] = PIN_MAP_ILLEGAL_CHARS;
  246.  
  247. void sort_nodes(socket_t * chip,extract_xy_t mode) {
  248.   node_t * nodes = chip-> nodes;
  249.   node_t ** sort_list;
  250.  
  251.   int alpha_seen = 0;
  252.   int numeric_seen = 0;
  253. /* Use generics to find out if the user has defined pin row/column
  254.    limits (in the case where top or bottom connector rows are not
  255.    connected at all */
  256.  
  257.   generic_info_t gen[1];
  258.  
  259.  
  260. /*
  261.   printf("chip %s\n",chip->identifier);
  262. */
  263.   int nodecnt = 0;
  264.  
  265.   int max_row = -BIG;
  266.   int min_row =  BIG;
  267.   int max_col = -BIG;
  268.   int min_col =  BIG;
  269.  
  270.   while(nodes) {
  271. /* to do  need to identify the pattern of node identifiers */
  272. /* numeric only ? */
  273. /* alpha only   ? */
  274. /* alpha number */
  275. /* number alpha */
  276. /* highest pin number ? */
  277. /* number of different alphas */
  278. /* assign an ordinal automatically to each node element */
  279.  
  280. /* sorting data structure */
  281. /* the form is 23A */
  282.     if (nodes->identifier)
  283.       {
  284.       if (isdigit(nodes->identifier[0]))
  285.         {
  286.         nodes->id_numeric_chars  = nodes->identifier;
  287.         nodes->id_numeric_cnt    = 0;              /* the numeric part of the identifier */
  288.         while(isdigit(nodes->identifier[nodes->id_numeric_cnt]))
  289.           nodes->id_numeric_cnt++;  /* the number of numeric chars in this part of the identifier */
  290.         nodes->id_alpha_chars    = nodes->identifier+nodes->id_numeric_cnt;
  291.         nodes->id_alpha_cnt      = strlen(nodes->identifier)-nodes->id_numeric_cnt;
  292.         }
  293.       else
  294.         {
  295.         nodes->id_alpha_chars  = nodes->identifier;
  296.         nodes->id_alpha_cnt    = 0;              /* the numeric part of the identifier */
  297.         while(isalpha (nodes->identifier[nodes->id_alpha_cnt]))
  298.           nodes->id_alpha_cnt++;  /* the number of numeric chars in this part of the identifier */
  299.         nodes->id_numeric_chars    = nodes->identifier+nodes->id_alpha_cnt;
  300.         nodes->id_numeric_cnt      = strlen(nodes->identifier)-nodes->id_alpha_cnt;
  301.         }
  302.    
  303. /*
  304.       printf("node : %s : alpha=%d num=%d\n",nodes->identifier,nodes->id_alpha_cnt,nodes->id_numeric_cnt);
  305. */
  306.       }
  307.     else
  308.       {
  309.       nodes->id_alpha_chars  = NULL;              /* the numeric part of the identifier */
  310.       nodes->id_alpha_cnt    = 0;  /* the number of numeric chars in this part of the identifier */
  311.       nodes->id_numeric_chars= NULL;
  312.       nodes->id_numeric_cnt  = 0;
  313.       }
  314.  
  315. /* dont touch the row/col indices unless asked to */
  316.    if(mode == EXTRACT_XY)
  317.      {
  318. /* if digits seen these are assigned as row 1..n */
  319.     if(nodes->id_numeric_cnt)
  320.       {
  321.       int index = atoi(nodes->id_numeric_chars);
  322.       numeric_seen = 1;
  323.       nodes->pin_row = index;
  324.       if(index > max_row)
  325.         {
  326.         max_row=index;
  327.         }
  328.       else if(index < min_row)    
  329.         {
  330.         min_row=index;
  331.         }
  332.       }
  333.     else
  334.       {
  335. /* default is on row 1 */
  336.       nodes->pin_row = 1;
  337.       }
  338.     if(nodes->id_alpha_cnt > 0)
  339.       {
  340.       alpha_seen = 1;
  341.       }
  342.    
  343.     /* between 1 and a few letters can be processed */
  344.     if(nodes->id_alpha_cnt > 0 && nodes->id_alpha_cnt <= MAX_ID_ALPHA_SORT )
  345.       {
  346.       int index;
  347.       int charcnt;
  348.       index = 0;
  349.       for (charcnt=0;charcnt<nodes->id_alpha_cnt;charcnt++)
  350.         {
  351.         int  i;
  352.         char c,d;
  353.         d = 0;
  354.         c = toupper(nodes->id_alpha_chars[charcnt]);
  355.         /* work out how many illegal chars are before this one */
  356.         /* this mapping actually collapses I onto J and O onto P */
  357.         /* I am assuming those two chars dont exist in the pin ID .... */
  358.         /* flag an error and continue for the present */
  359.         /* characters are actually coded as 1..n so that IDs like 'AA' look */
  360.         /* different to 'A', which they wont be if the leading 'A' is coded as 0 */
  361.         for (i=0;i< PIN_MAP_ILLEGAL_CHAR_COUNT; i++)
  362.           {
  363.           if(c==illegal_chars[i])
  364.             {
  365.             Log(LOG_GENERAL,"-- Warning : illegal pin ident character in %s(%d)\n",
  366.                chip->identifier,nodes->identifier);
  367.             }
  368.           if(c>=illegal_chars[i])
  369.             {
  370.             d++;
  371.             }
  372.           }
  373.         index *= (PIN_MAP_LEGAL_CHAR_COUNT+1);
  374.         index +=  (c-d-'A'+1);
  375.        
  376.         }
  377. /*
  378.       printf("'\n");
  379. */      nodes->pin_col = index;
  380.       if(index > max_col)
  381.         {
  382.         max_col=index;
  383.         }
  384.       else if(index < min_col)    
  385.         {
  386.         min_col=index;
  387.         }
  388.       }
  389.     else
  390.       {
  391. /* default is column zero */
  392.       nodes->pin_col = 0;    
  393.       }
  394.      }
  395.     nodecnt++;
  396.     nodes=nodes->sktnext;
  397.     }
  398.  
  399.  
  400.   chip-> max_pin_col = max_col== -BIG ? 0 : max_col;
  401.   chip-> min_pin_col = min_col==  BIG ? 0 : min_col;
  402.   chip-> max_pin_row = max_row== -BIG ? 0 : max_row;
  403.   chip-> min_pin_row = min_row==  BIG ? 0 : min_row;
  404. /*
  405.   printf("chip %10s col %3d to %3d , row %3d to %3d\n",chip->identifier,max_col,min_col,max_row,min_row);
  406. */
  407.   /* know the number of nodes now allocate storage for the pointers
  408.      to be used by qsort() */
  409.      
  410.   sort_list = calloc(nodecnt,sizeof(node_t *));
  411.  
  412.  
  413.   /* grab hold of all of the pointers */
  414.   nodes = chip-> nodes;
  415.   nodecnt = 0;
  416.   while(nodes) {
  417.     sort_list[nodecnt++]=nodes;
  418.     nodes=nodes->sktnext;
  419.     }
  420.    
  421.   /* sort them */
  422.  
  423.   if(nodecnt) {
  424.     int i;
  425.  
  426.     qsort((void *)sort_list,
  427.           nodecnt,sizeof(node_t *),&sort_nodes_compar);
  428.    
  429.     /* and now rebuild the list based on the sorted list */  
  430.     chip->nodes    = sort_list[0];
  431.     chip->lastnode = sort_list[nodecnt-1];
  432.    
  433.     /* relink the list */
  434.     for(i=0;i<(nodecnt-1);i++) {
  435.       sort_list[i]->sktnext = sort_list[i+1];
  436.       }
  437.     sort_list[nodecnt-1]->sktnext = NULL;
  438.    
  439.     }
  440.  
  441.   free(sort_list);
  442.  
  443.   /* check for overrides in case there are missing rows/cols */
  444.  
  445.   if (get_generic_value(&chip->generics, "min_pin_row",gen) == IS_ATTRIBUTE)
  446.     {
  447.     chip->min_pin_row = eval_expression(gen->expr, &chip->generics);
  448.     }
  449.   if (get_generic_value(&chip->generics, "max_pin_row",gen) == IS_ATTRIBUTE)
  450.     {
  451.     chip->max_pin_row = eval_expression(gen->expr, &chip->generics );
  452.     }
  453.   if (get_generic_value(&chip->generics, "min_pin_col",gen) == IS_ATTRIBUTE)
  454.     {
  455.     chip->min_pin_col = eval_expression(gen->expr, &chip->generics );
  456.     }
  457.   if (get_generic_value(&chip->generics, "max_pin_col",gen) == IS_ATTRIBUTE)
  458.     {
  459.     chip->max_pin_col = eval_expression(gen->expr, &chip->generics );
  460.     }
  461. }
  462.    
  463. /* we have a pair of pointers to array elements */
  464.    
  465. static int sort_socket_compar(const void * p,const void * q)
  466. {
  467.   return strcmp((*(socket_t **)p)->identifier,(*(socket_t **)q)->identifier);
  468. }
  469.  
  470.  
  471. /* this function sorts all of  sockets into alphanumeric order */
  472.  
  473. socket_t * sort_sockets(socket_t ** head) {
  474.   socket_t ** sort_list,* chip= *head;
  475.   int sktcnt = 0;
  476.  
  477.   while(chip) {
  478.     sktcnt++;
  479.     chip=chip->next;
  480.     }
  481.   /* know the number of nodes now allocate storage for the pointers
  482.      to be used by qsort() */
  483.   sort_list = calloc(sktcnt,sizeof(socket_t *));
  484.  
  485.   /* grab hold of all of the pointers */
  486.   chip = *head;
  487.   sktcnt = 0;
  488.   while(chip) {
  489.     sort_list[sktcnt++]=chip;
  490.     chip=chip->next;
  491.     }
  492.    
  493.   /* sort them */
  494.  
  495.   if(sktcnt) {
  496.     int i;
  497.     qsort((char *)sort_list,
  498.           sktcnt,
  499.           sizeof(socket_t *),
  500.           &sort_socket_compar);
  501.    
  502.     /* and now rebuild the list based on the sorted list */  
  503.     *head    = sort_list[0];
  504.    
  505.     /* relink the list */
  506.     for(i=0;i<(sktcnt-1);i++)  {
  507.       sort_list[i]->next = sort_list[i+1];
  508.       }
  509.     sort_list[sktcnt-1]->next = NULL;
  510.    
  511.     }
  512.   free(sort_list);
  513.   return * head;
  514. }
  515.  
  516.  
  517.  
  518. /* compile regular expression according
  519.    to Vertical expectations */
  520. /* What is required is a whole string match. In order to
  521.    achieve this, the regular expression is bracketed with
  522.    ^ and $ which mean in this context 'match start of string'
  523.    and 'match end of string' */
  524.  
  525.  
  526. int vert_regcomp(vert_regex_t ** vert_preg,char * expr)
  527.   {    
  528.   int rc;  
  529.   vert_regex_t * preg;
  530. /* allocate structure members */
  531.   preg          = calloc(1,sizeof(vert_regex_t));
  532.   *vert_preg    = preg;
  533.   rc = check_wildcard(expr);
  534.   if (rc!=TCL_OK)
  535.     {
  536.     preg->buff = malloc(3);
  537.     strcpy(preg->buff,"^$");
  538.     }
  539.   else
  540.     {
  541.     preg->buff = malloc(strlen(expr)+3);
  542.     sprintf(preg->buff,"^%s$",expr);
  543.     }
  544. /*  printf("-- compare '%s'\n",preg->buff); */
  545.   rc = regcomp(preg->preg,preg->buff,REG_EXTENDED | REG_ICASE);
  546.   return rc;
  547.   }
  548.  
  549. /* tidy up */
  550. int vert_regfree(vert_regex_t ** vert_preg)
  551.    {
  552.    regfree((*vert_preg)->preg);
  553.    free((*vert_preg)->buff);
  554.    free(*vert_preg);
  555.    *vert_preg = NULL;
  556.    return 0;
  557.    }
  558.