Subversion Repositories Vertical

Rev

Go to most recent revision | 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 <ctype.h>
  135. #include <regex.h>
  136. #include <stdio.h>
  137. #include <stdlib.h>
  138. #include <string.h>
  139. #include <sys/types.h>
  140.  
  141. /* TCL/Tk declarations */
  142. #include "cmdlog.h"
  143. #include "cmdparse.h"
  144. #include "database.h"
  145. #include "expression.h"
  146. #include "generic.h"
  147. #include "routing.h"
  148. #include "sorting.h"
  149. #include "vertcl_main.h"
  150.  
  151. #ident                                                                                        \
  152.     "@(#)$Header: c:\\cygwin\\cvsroot/Vert03/vertlib/sorting.c,v 1.1.1.1 2003/11/04 23:34:57 mjames Exp $";
  153.  
  154. /* the comparison function  : requires upgrade for checking :
  155.    A1...A10 then B1..B10 or is it   1a..10a then 1b..10b */
  156. #if defined SORT_ORIGINAL
  157. static int sort_nodes_compar (const void *p, const void *q)
  158. {
  159.         char *s1 = (*(node_t **) p)->identifier;
  160.         char *s2 = (*(node_t **) q)->identifier;
  161.  
  162.         int l1 = strlen (s1);
  163.         int l2 = strlen (s2);
  164.         if (l1 == l2) /* only call strcmp() for same length strings
  165.                          This makes '2' smaller than '19' */
  166.                 return strcmp (s1, s2);
  167.         else
  168.                 return l1 - l2; /* if different lengths, use the shorter name */
  169. }
  170. #else
  171.  
  172. /* this sort works for alpha - numeric strings : A1 A2
  173.    use SWAP command to swap identifiers  */
  174. static int sort_nodes_compar (const void *p, const void *q)
  175. {
  176.         char *s1 = (*(node_t **) p)->id_alpha_chars;
  177.         char *s2 = (*(node_t **) q)->id_alpha_chars;
  178.  
  179.         int l1 = (*(node_t **) p)->id_alpha_cnt;
  180.         int l2 = (*(node_t **) q)->id_alpha_cnt;
  181.         int diff = 0;
  182.         /*
  183.           printf("cmp p: a %3s[%2d] n %3s[%2d]\n",
  184.            (*(node_t **)p)->id_alpha_chars,
  185.             (*(node_t **)p)->id_alpha_cnt,
  186.             (*(node_t **)p)->id_numeric_chars,
  187.             (*(node_t **)p)->id_numeric_cnt);
  188.           printf("cmp q: a %3s[%2d] n %3s[%2d]\n",
  189.            (*(node_t **)q)->id_alpha_chars,
  190.             (*(node_t **)q)->id_alpha_cnt,
  191.             (*(node_t **)q)->id_numeric_chars,
  192.             (*(node_t **)q)->id_numeric_cnt);
  193.         */
  194.  
  195.         if (l1 == l2)
  196.         {
  197.                 /* only call strcmp() for same length strings */
  198.                 diff = strncmp (s1, s2, l1);
  199.                 /*
  200.                     printf("alpha cmp (%s,%s,%d) different %d\n",s1,s2,l1,diff);
  201.                 */
  202.                 if (diff == 0) /* alpha same */
  203.                 {
  204.                         /* otherwise check the numeric parts of the strings */
  205.                         /* these have been decoded already */
  206.                         l1 = (*(node_t **) p)->pin_row;
  207.                         l2 = (*(node_t **) q)->pin_row;
  208.                         diff = l1 - l2;
  209.                         /*
  210.                               printf("num different %d\n",diff);
  211.                         */
  212.                 }
  213.         }
  214.         else
  215.         {
  216.                 diff = l1 - l2; /* if different alpha lengths, use the shorter name */
  217.                                 /*
  218.                                     printf("alpha len different %d\n",diff);
  219.                                 */
  220.         }
  221.         /*
  222.           printf("diff: %d  string %7s row %2d and %7s row%2d\n",diff,
  223.             (*(node_t **)p)->identifier,
  224.             (*(node_t **)p)->pin_row,
  225.             (*(node_t **)q)->identifier,
  226.             (*(node_t **)q)->pin_row);
  227.         */
  228.         return diff;
  229. }
  230.  
  231. #endif
  232.  
  233. /* this function sorts all of the pin references on a chip
  234.    into alphanumeric order, and also generates a unique pin index for each pin
  235.    in the case of alphanumeric pin identifiers : pin A1 or 1A will become index 1 */
  236. #define BIG 1000000
  237.  
  238. /* mapping table has no letter 'I' or 'O' in it */
  239. static unsigned char illegal_chars[] = PIN_MAP_ILLEGAL_CHARS;
  240.  
  241. void sort_nodes (socket_t *chip, extract_xy_t mode)
  242. {
  243.         node_t *nodes = chip->nodes;
  244.         node_t **sort_list;
  245.  
  246.         int alpha_seen = 0;
  247.         int numeric_seen = 0;
  248.         /* Use generics to find out if the user has defined pin row/column
  249.            limits (in the case where top or bottom connector rows are not
  250.            connected at all */
  251.  
  252.         generic_info_t gen[1];
  253.  
  254.         /*
  255.           printf("chip %s\n",chip->identifier);
  256.         */
  257.         int nodecnt = 0;
  258.  
  259.         int max_row = -BIG;
  260.         int min_row = BIG;
  261.         int max_col = -BIG;
  262.         int min_col = BIG;
  263.  
  264.         while (nodes)
  265.         {
  266.                 /* to do  need to identify the pattern of node identifiers */
  267.                 /* numeric only ? */
  268.                 /* alpha only   ? */
  269.                 /* alpha number */
  270.                 /* number alpha */
  271.                 /* highest pin number ? */
  272.                 /* number of different alphas */
  273.                 /* assign an ordinal automatically to each node element */
  274.  
  275.                 /* sorting data structure */
  276.                 /* the form is 23A */
  277.                 if (nodes->identifier)
  278.                 {
  279.                         if (isdigit (nodes->identifier[0]))
  280.                         {
  281.                                 nodes->id_numeric_chars = nodes->identifier;
  282.                                 nodes->id_numeric_cnt =
  283.                                     0; /* the numeric part of the identifier */
  284.                                 while (isdigit (nodes->identifier[nodes->id_numeric_cnt]))
  285.                                         nodes->id_numeric_cnt++; /* the number of numeric chars
  286.                                                                     in this part of the
  287.                                                                     identifier */
  288.                                 nodes->id_alpha_chars =
  289.                                     nodes->identifier + nodes->id_numeric_cnt;
  290.                                 nodes->id_alpha_cnt =
  291.                                     strlen (nodes->identifier) - nodes->id_numeric_cnt;
  292.                         }
  293.                         else
  294.                         {
  295.                                 nodes->id_alpha_chars = nodes->identifier;
  296.                                 nodes->id_alpha_cnt =
  297.                                     0; /* the numeric part of the identifier */
  298.                                 while (isalpha (nodes->identifier[nodes->id_alpha_cnt]))
  299.                                         nodes->id_alpha_cnt++; /* the number of numeric chars
  300.                                                                   in this part of the
  301.                                                                   identifier */
  302.                                 nodes->id_numeric_chars =
  303.                                     nodes->identifier + nodes->id_alpha_cnt;
  304.                                 nodes->id_numeric_cnt =
  305.                                     strlen (nodes->identifier) - nodes->id_alpha_cnt;
  306.                         }
  307.  
  308.                         /*
  309.                               printf("node : %s : alpha=%d
  310.                            num=%d\n",nodes->identifier,nodes->id_alpha_cnt,nodes->id_numeric_cnt);
  311.                         */
  312.                 }
  313.                 else
  314.                 {
  315.                         nodes->id_alpha_chars = NULL; /* the numeric part of the identifier */
  316.                         nodes->id_alpha_cnt =
  317.                             0; /* the number of numeric chars in this part of the identifier */
  318.                         nodes->id_numeric_chars = NULL;
  319.                         nodes->id_numeric_cnt = 0;
  320.                 }
  321.  
  322.                 /* dont touch the row/col indices unless asked to */
  323.                 if (mode == EXTRACT_XY)
  324.                 {
  325.                         /* if digits seen these are assigned as row 1..n */
  326.                         if (nodes->id_numeric_cnt)
  327.                         {
  328.                                 int index = atoi (nodes->id_numeric_chars);
  329.                                 numeric_seen = 1;
  330.                                 nodes->pin_row = index;
  331.                                 if (index > max_row)
  332.                                 {
  333.                                         max_row = index;
  334.                                 }
  335.                                 else if (index < min_row)
  336.                                 {
  337.                                         min_row = index;
  338.                                 }
  339.                         }
  340.                         else
  341.                         {
  342.                                 /* default is on row 1 */
  343.                                 nodes->pin_row = 1;
  344.                         }
  345.                         if (nodes->id_alpha_cnt > 0)
  346.                         {
  347.                                 alpha_seen = 1;
  348.                         }
  349.  
  350.                         /* between 1 and a few letters can be processed */
  351.                         if (nodes->id_alpha_cnt > 0 &&
  352.                             nodes->id_alpha_cnt <= MAX_ID_ALPHA_SORT)
  353.                         {
  354.                                 int index;
  355.                                 int charcnt;
  356.                                 index = 0;
  357.                                 for (charcnt = 0; charcnt < nodes->id_alpha_cnt; charcnt++)
  358.                                 {
  359.                                         int i;
  360.                                         char c, d;
  361.                                         d = 0;
  362.                                         c = toupper (nodes->id_alpha_chars[charcnt]);
  363.                                         /* work out how many illegal chars are before this one
  364.                                          */
  365.                                         /* this mapping actually collapses I onto J and O onto
  366.                                          * P */
  367.                                         /* I am assuming those two chars dont exist in the pin
  368.                                          * ID .... */
  369.                                         /* flag an error and continue for the present */
  370.                                         /* characters are actually coded as 1..n so that IDs
  371.                                          * like 'AA' look */
  372.                                         /* different to 'A', which they wont be if the leading
  373.                                          * 'A' is coded as 0 */
  374.                                         for (i = 0; i < PIN_MAP_ILLEGAL_CHAR_COUNT; i++)
  375.                                         {
  376.                                                 if (c == illegal_chars[i])
  377.                                                 {
  378.                                                         Log (
  379.                                                             LOG_GENERAL,
  380.                                                             "-- Warning : illegal pin ident "
  381.                                                             "character in %s(%d)\n",
  382.                                                             chip->identifier,
  383.                                                             nodes->identifier);
  384.                                                 }
  385.                                                 if (c >= illegal_chars[i])
  386.                                                 {
  387.                                                         d++;
  388.                                                 }
  389.                                         }
  390.                                         index *= (PIN_MAP_LEGAL_CHAR_COUNT + 1);
  391.                                         index += (c - d - 'A' + 1);
  392.                                 }
  393.                                 /*
  394.                                       printf("'\n");
  395.                                 */
  396.                                 nodes->pin_col = index;
  397.                                 if (index > max_col)
  398.                                 {
  399.                                         max_col = index;
  400.                                 }
  401.                                 else if (index < min_col)
  402.                                 {
  403.                                         min_col = index;
  404.                                 }
  405.                         }
  406.                         else
  407.                         {
  408.                                 /* default is column zero */
  409.                                 nodes->pin_col = 0;
  410.                         }
  411.                 }
  412.                 nodecnt++;
  413.                 nodes = nodes->sktnext;
  414.         }
  415.  
  416.         chip->max_pin_col = max_col == -BIG ? 0 : max_col;
  417.         chip->min_pin_col = min_col == BIG ? 0 : min_col;
  418.         chip->max_pin_row = max_row == -BIG ? 0 : max_row;
  419.         chip->min_pin_row = min_row == BIG ? 0 : min_row;
  420.         /*
  421.           printf("chip %10s col %3d to %3d , row %3d to
  422.           %3d\n",chip->identifier,max_col,min_col,max_row,min_row);
  423.         */
  424.         /* know the number of nodes now allocate storage for the pointers
  425.            to be used by qsort() */
  426.  
  427.         sort_list = calloc (nodecnt, sizeof (node_t *));
  428.  
  429.         /* grab hold of all of the pointers */
  430.         nodes = chip->nodes;
  431.         nodecnt = 0;
  432.         while (nodes)
  433.         {
  434.                 sort_list[nodecnt++] = nodes;
  435.                 nodes = nodes->sktnext;
  436.         }
  437.  
  438.         /* sort them */
  439.  
  440.         if (nodecnt)
  441.         {
  442.                 int i;
  443.  
  444.                 qsort ((void *) sort_list, nodecnt, sizeof (node_t *), &sort_nodes_compar);
  445.  
  446.                 /* and now rebuild the list based on the sorted list */
  447.                 chip->nodes = sort_list[0];
  448.                 chip->lastnode = sort_list[nodecnt - 1];
  449.  
  450.                 /* relink the list */
  451.                 for (i = 0; i < (nodecnt - 1); i++)
  452.                 {
  453.                         sort_list[i]->sktnext = sort_list[i + 1];
  454.                 }
  455.                 sort_list[nodecnt - 1]->sktnext = NULL;
  456.         }
  457.  
  458.         free (sort_list);
  459.  
  460.         /* check for overrides in case there are missing rows/cols */
  461.  
  462.         if (get_generic_value (&chip->generics, "min_pin_row", gen) == IS_ATTRIBUTE)
  463.         {
  464.                 chip->min_pin_row = eval_expression (gen->expr, &chip->generics);
  465.         }
  466.         if (get_generic_value (&chip->generics, "max_pin_row", gen) == IS_ATTRIBUTE)
  467.         {
  468.                 chip->max_pin_row = eval_expression (gen->expr, &chip->generics);
  469.         }
  470.         if (get_generic_value (&chip->generics, "min_pin_col", gen) == IS_ATTRIBUTE)
  471.         {
  472.                 chip->min_pin_col = eval_expression (gen->expr, &chip->generics);
  473.         }
  474.         if (get_generic_value (&chip->generics, "max_pin_col", gen) == IS_ATTRIBUTE)
  475.         {
  476.                 chip->max_pin_col = eval_expression (gen->expr, &chip->generics);
  477.         }
  478. }
  479.  
  480. /* we have a pair of pointers to array elements */
  481.  
  482. static int sort_socket_compar (const void *p, const void *q)
  483. {
  484.         return strcmp ((*(socket_t **) p)->identifier, (*(socket_t **) q)->identifier);
  485. }
  486.  
  487. /* this function sorts all of  sockets into alphanumeric order */
  488.  
  489. socket_t *sort_sockets (socket_t **head)
  490. {
  491.         socket_t **sort_list, *chip = *head;
  492.         int sktcnt = 0;
  493.  
  494.         while (chip)
  495.         {
  496.                 sktcnt++;
  497.                 chip = chip->next;
  498.         }
  499.         /* know the number of nodes now allocate storage for the pointers
  500.            to be used by qsort() */
  501.         sort_list = calloc (sktcnt, sizeof (socket_t *));
  502.  
  503.         /* grab hold of all of the pointers */
  504.         chip = *head;
  505.         sktcnt = 0;
  506.         while (chip)
  507.         {
  508.                 sort_list[sktcnt++] = chip;
  509.                 chip = chip->next;
  510.         }
  511.  
  512.         /* sort them */
  513.  
  514.         if (sktcnt)
  515.         {
  516.                 int i;
  517.                 qsort ((char *) sort_list, sktcnt, sizeof (socket_t *), &sort_socket_compar);
  518.  
  519.                 /* and now rebuild the list based on the sorted list */
  520.                 *head = sort_list[0];
  521.  
  522.                 /* relink the list */
  523.                 for (i = 0; i < (sktcnt - 1); i++)
  524.                 {
  525.                         sort_list[i]->next = sort_list[i + 1];
  526.                 }
  527.                 sort_list[sktcnt - 1]->next = NULL;
  528.         }
  529.         free (sort_list);
  530.         return *head;
  531. }
  532.  
  533. /* compile regular expression according
  534.    to Vertical expectations */
  535. /* What is required is a whole string match. In order to
  536.    achieve this, the regular expression is bracketed with
  537.    ^ and $ which mean in this context 'match start of string'
  538.    and 'match end of string' */
  539.  
  540. int vert_regcomp (vert_regex_t **vert_preg, char *expr)
  541. {
  542.         int rc;
  543.         vert_regex_t *preg;
  544.         /* allocate structure members */
  545.         preg = calloc (1, sizeof (vert_regex_t));
  546.         *vert_preg = preg;
  547.         rc = check_wildcard (expr);
  548.         if (rc != TCL_OK)
  549.         {
  550.                 preg->buff = malloc (3);
  551.                 strcpy (preg->buff, "^$");
  552.         }
  553.         else
  554.         {
  555.                 preg->buff = malloc (strlen (expr) + 3);
  556.                 sprintf (preg->buff, "^%s$", expr);
  557.         }
  558.         /*  printf("-- compare '%s'\n",preg->buff); */
  559.         rc = regcomp (preg->preg, preg->buff, REG_EXTENDED | REG_ICASE);
  560.         return rc;
  561. }
  562.  
  563. /* tidy up */
  564. int vert_regfree (vert_regex_t **vert_preg)
  565. {
  566.         regfree ((*vert_preg)->preg);
  567.         free ((*vert_preg)->buff);
  568.         free (*vert_preg);
  569.         *vert_preg = NULL;
  570.         return 0;
  571. }
  572.