Subversion Repositories Vertical

/* $Id: sorting.c,v 1.1.1.1 2003/11/04 23:34:57 mjames Exp $

 *

 * $Log: sorting.c,v $

 * Revision 1.1.1.1  2003/11/04 23:34:57  mjames

 * Imported into local repositrory

 *

 * Revision 1.14  2002/10/02 18:39:54  MJAMES

 * Stopped copying pin_col to index on every node

 *

 * Revision 1.13  2002/09/16 14:41:43  mjames

 * Merge back pin indexing bug that meant

 * pin AZ12 was indistinguishable from pin Z12 in

 * rename ident/name commands

 *

 * Revision 1.12  2002/09/09 10:10:21  mjames

 * Moved pin remapping function to pin ident editing function from

 * sorting pin name routine.

 *

 * Revision 1.11  2002/09/09 09:53:01  mjames

 * Moved pin remapping function to pin ident editing function from

 * sorting pin name routine.

 *

 * Revision 1.10  2002/08/23 14:13:55  mjames

 * Added legal/illegal pin identifying letters to the header file.

 * Upgraded sort to determine row/column locations of pins identified like

 * 'a1' and '1a' etc or '1' , '2'

 *

 * Revision 1.9  2001/10/31 22:33:27  mjames

 * Suppress diagnostic print

 *

 * Revision 1.8  2001/10/31 22:20:17  mjames

 * Tidying up problematical comments caused by CVS

 * 'intelligent' comment guessing

 *

 * Revision 1.7  2001/10/31 16:15:36  mjames

 * Added a datastructure to hide regular expression information from programs.

 *

 * Revision 1.6  2001/10/22 10:53:50  mjames

 * Added a declaration of the Vertical regular expression compiler

 * which validates and complains about older 'regular expressions'

 * used by Vertical prior to using regexp in the C library

 *

 * Revision 1.5  2001/10/10 20:17:59  mjames

 * Added a vert_regcomp function to compile regular expressions

 * with '^' (match start string) and  '$' (match end string) bracketing

 * this => wildcard must match entire string not just a part of it.

 *

 * Revision 1.4  2001/09/16 20:36:03  mjames

 * Second attempt to modify wire bundles to be connector rather than net

 * centric. Allows more than one connector to carry the same net,

 *

 * Revision 1.3  2001/09/16 19:48:53  mjames

 * Modified sorting algorithm to have sideffect of calculating pin rows and

 * columns for sockets.

 *

 * Revision 1.2  2001/06/06 12:10:17  mjames

 * Move from HPUX

 *

 * Revision 1.1.1.1  2000/10/19 21:58:40  mjames

 * Mike put it here

 *

 *

 * Revision 1.24  2000/10/04  10:37:10  10:37:10  mjames (Mike James)

 * Modified for Vertical2 : support COMPONENTS and SIGNALS

 *

 * Revision 1.24  2000/10/04  10:37:10  10:37:10  mjames (Mike James)

 * Part of Release PSAVAT01

 *

 * Revision 1.23  2000/10/02  11:04:21  11:04:21  mjames (Mike James)

 * new_vhdl

 *

 * Revision 1.22  2000/09/27  14:42:21  14:42:21  mjames (Mike James)

 * Part of Release Sep_27_ST_2000

 *

 * Revision 1.21  2000/09/21  10:15:51  10:15:51  mjames (Mike James)

 * Part of Release Sep21Alpha

 *

 * Revision 1.20  2000/08/25  09:57:16  09:57:16  mjames (Mike James)

 * Part of Release Aug25_alpha

 *

 * Revision 1.19  2000/08/16  08:57:33  08:57:33  mjames (Mike James)

 * Part of Release CD01_Aug2000

 *

 * Revision 1.18  2000/08/14  14:45:13  14:45:13  mjames (Mike James)

 * Part of Release Aug_14_2000

 *

 * Revision 1.17  2000/08/11  08:30:34  08:30:34  mjames (Mike James)

 * Part of Release Aug_11_2000

 *

 * Revision 1.16  2000/08/09  10:31:49  10:31:49  mjames (Mike James)

 * Part of Release Aug__9_2000

 *

 * Revision 1.15  2000/05/31  11:43:00  11:43:00  mjames (Mike James)

 * Part of Release May_31_2000

 *

 * Revision 1.14  2000/05/08  17:01:40  17:01:40  mjames (Mike James)

 * Part of Release May__8_2000

 *

 * Revision 1.13  2000/05/08  16:59:33  16:59:33  mjames (Mike James)

 * Part of Release May__8_2000

 *

 * Revision 1.12  2000/05/08  16:57:10  16:57:10  mjames (Mike James)

 * Part of Release May__8_2000

 *

 * Revision 1.11  2000/03/08  16:19:31  16:19:31  mjames (Mike James)

 * New version including PC

 *

 * Revision 1.8  2000/01/20  15:58:50  15:58:50  mjames (Mike James)

 * Part of Release R22

 *

 * Revision 1.7  99/12/22  11:15:31  11:15:31  mjames (Mike James)

 * Part of Release Dec_22_1999

 *

 * Revision 1.6  99/06/25  14:35:51  14:35:51  mjames (Mike James)

 * Added in reference to expression.h, but no changes made

 * to the function of acfread yet.

 *

 * Revision 1.5  99/05/04  09:52:52  09:52:52  mjames (Mike James)

 * General checkin

 *

 * Revision 1.4  98/02/11  11:27:19  11:27:19  mjames (Mike James)

 * Checked in for version 6.2a

 *

 * Revision 1.3  97/04/23  08:43:25  08:43:25  mjames (Mike James)

 * CHecked in for release rel23041997

 *

 * Revision 1.2  96/12/23  15:17:00  15:17:00  mjames (Mike James)

 * Altered because find_socket takes a reference

 * to the head-of-list-pointer noth the pointer itself.

 *

 * Revision 1.1  96/12/23  10:26:21  10:26:21  mjames (Mike James)

 * Initial revision *  */

#include <ctype.h>

#include <regex.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <sys/types.h>

/* TCL/Tk declarations */

#include "cmdlog.h"

#include "cmdparse.h"

#include "database.h"

#include "expression.h"

#include "generic.h"

#include "routing.h"

#include "sorting.h"

#include "vertcl_main.h"

#ident                                                                                        \

    "@(#)$Header: c:\\cygwin\\cvsroot/Vert03/vertlib/sorting.c,v 1.1.1.1 2003/11/04 23:34:57 mjames Exp $";

/* the comparison function  : requires upgrade for checking :

   A1...A10 then B1..B10 or is it   1a..10a then 1b..10b */

#if defined SORT_ORIGINAL

static int sort_nodes_compar (const void *p, const void *q)

{

        char *s1 = (*(node_t **) p)->identifier;

        char *s2 = (*(node_t **) q)->identifier;

        int l1 = strlen (s1);

        int l2 = strlen (s2);

        if (l1 == l2) /* only call strcmp() for same length strings

                         This makes '2' smaller than '19' */

                return strcmp (s1, s2);

        else

                return l1 - l2; /* if different lengths, use the shorter name */

}

#else

/* this sort works for alpha - numeric strings : A1 A2

   use SWAP command to swap identifiers  */

static int sort_nodes_compar (const void *p, const void *q)

{

        char *s1 = (*(node_t **) p)->id_alpha_chars;

        char *s2 = (*(node_t **) q)->id_alpha_chars;

        int l1 = (*(node_t **) p)->id_alpha_cnt;

        int l2 = (*(node_t **) q)->id_alpha_cnt;

        int diff = 0;

        /*

          printf("cmp p: a %3s[%2d] n %3s[%2d]\n",

           (*(node_t **)p)->id_alpha_chars,

            (*(node_t **)p)->id_alpha_cnt,

            (*(node_t **)p)->id_numeric_chars,

            (*(node_t **)p)->id_numeric_cnt);

          printf("cmp q: a %3s[%2d] n %3s[%2d]\n",

           (*(node_t **)q)->id_alpha_chars,

            (*(node_t **)q)->id_alpha_cnt,

            (*(node_t **)q)->id_numeric_chars,

            (*(node_t **)q)->id_numeric_cnt);

        */

        if (l1 == l2)

        {

                /* only call strcmp() for same length strings */

                diff = strncmp (s1, s2, l1);

                /*

                    printf("alpha cmp (%s,%s,%d) different %d\n",s1,s2,l1,diff);

                */

                if (diff == 0) /* alpha same */

                {

                        /* otherwise check the numeric parts of the strings */

                        /* these have been decoded already */

                        l1 = (*(node_t **) p)->pin_row;

                        l2 = (*(node_t **) q)->pin_row;

                        diff = l1 - l2;

                        /*

                              printf("num different %d\n",diff);

                        */

                }

        }

        else

        {

                diff = l1 - l2; /* if different alpha lengths, use the shorter name */

                                /*

                                    printf("alpha len different %d\n",diff);

                                */

        }

        /*

          printf("diff: %d  string %7s row %2d and %7s row%2d\n",diff,

            (*(node_t **)p)->identifier,

            (*(node_t **)p)->pin_row,

            (*(node_t **)q)->identifier,

            (*(node_t **)q)->pin_row);

        */

        return diff;

}

#endif

/* this function sorts all of the pin references on a chip

   into alphanumeric order, and also generates a unique pin index for each pin

   in the case of alphanumeric pin identifiers : pin A1 or 1A will become index 1 */

#define BIG 1000000

/* mapping table has no letter 'I' or 'O' in it */

static unsigned char illegal_chars[] = PIN_MAP_ILLEGAL_CHARS;

void sort_nodes (socket_t *chip, extract_xy_t mode)

{

        node_t *nodes = chip->nodes;

        node_t **sort_list;

        int alpha_seen = 0;

        int numeric_seen = 0;

        /* Use generics to find out if the user has defined pin row/column

           limits (in the case where top or bottom connector rows are not

           connected at all */

        generic_info_t gen[1];

        /*

          printf("chip %s\n",chip->identifier);

        */

        int nodecnt = 0;

        int max_row = -BIG;

        int min_row = BIG;

        int max_col = -BIG;

        int min_col = BIG;

        while (nodes)

        {

                /* to do  need to identify the pattern of node identifiers */

                /* numeric only ? */

                /* alpha only   ? */

                /* alpha number */

                /* number alpha */

                /* highest pin number ? */

                /* number of different alphas */

                /* assign an ordinal automatically to each node element */

                /* sorting data structure */

                /* the form is 23A */

                if (nodes->identifier)

                {

                        if (isdigit (nodes->identifier[0]))

                        {

                                nodes->id_numeric_chars = nodes->identifier;

                                nodes->id_numeric_cnt =

                                    0; /* the numeric part of the identifier */

                                while (isdigit (nodes->identifier[nodes->id_numeric_cnt]))

                                        nodes->id_numeric_cnt++; /* the number of numeric chars

                                                                    in this part of the

                                                                    identifier */

                                nodes->id_alpha_chars =

                                    nodes->identifier + nodes->id_numeric_cnt;

                                nodes->id_alpha_cnt =

                                    strlen (nodes->identifier) - nodes->id_numeric_cnt;

                        }

                        else

                        {

                                nodes->id_alpha_chars = nodes->identifier;

                                nodes->id_alpha_cnt =

                                    0; /* the numeric part of the identifier */

                                while (isalpha (nodes->identifier[nodes->id_alpha_cnt]))

                                        nodes->id_alpha_cnt++; /* the number of numeric chars

                                                                  in this part of the

                                                                  identifier */

                                nodes->id_numeric_chars =

                                    nodes->identifier + nodes->id_alpha_cnt;

                                nodes->id_numeric_cnt =

                                    strlen (nodes->identifier) - nodes->id_alpha_cnt;

                        }

                        /*

                              printf("node : %s : alpha=%d

                           num=%d\n",nodes->identifier,nodes->id_alpha_cnt,nodes->id_numeric_cnt);

                        */

                }

                else

                {

                        nodes->id_alpha_chars = NULL; /* the numeric part of the identifier */

                        nodes->id_alpha_cnt =

                            0; /* the number of numeric chars in this part of the identifier */

                        nodes->id_numeric_chars = NULL;

                        nodes->id_numeric_cnt = 0;

                }

                /* dont touch the row/col indices unless asked to */

                if (mode == EXTRACT_XY)

                {

                        /* if digits seen these are assigned as row 1..n */

                        if (nodes->id_numeric_cnt)

                        {

                                int index = atoi (nodes->id_numeric_chars);

                                numeric_seen = 1;

                                nodes->pin_row = index;

                                if (index > max_row)

                                {

                                        max_row = index;

                                }

                                else if (index < min_row)

                                {

                                        min_row = index;

                                }

                        }

                        else

                        {

                                /* default is on row 1 */

                                nodes->pin_row = 1;

                        }

                        if (nodes->id_alpha_cnt > 0)

                        {

                                alpha_seen = 1;

                        }

                        /* between 1 and a few letters can be processed */

                        if (nodes->id_alpha_cnt > 0 &&

                            nodes->id_alpha_cnt <= MAX_ID_ALPHA_SORT)

                        {

                                int index;

                                int charcnt;

                                index = 0;

                                for (charcnt = 0; charcnt < nodes->id_alpha_cnt; charcnt++)

                                {

                                        int i;

                                        char c, d;

                                        d = 0;

                                        c = toupper (nodes->id_alpha_chars[charcnt]);

                                        /* work out how many illegal chars are before this one

                                         */

                                        /* this mapping actually collapses I onto J and O onto

                                         * P */

                                        /* I am assuming those two chars dont exist in the pin

                                         * ID .... */

                                        /* flag an error and continue for the present */

                                        /* characters are actually coded as 1..n so that IDs

                                         * like 'AA' look */

                                        /* different to 'A', which they wont be if the leading

                                         * 'A' is coded as 0 */

                                        for (i = 0; i < PIN_MAP_ILLEGAL_CHAR_COUNT; i++)

                                        {

                                                if (c == illegal_chars[i])

                                                {

                                                        Log (

                                                            LOG_GENERAL,

                                                            "-- Warning : illegal pin ident "

                                                            "character in %s(%d)\n",

                                                            chip->identifier,

                                                            nodes->identifier);

                                                }

                                                if (c >= illegal_chars[i])

                                                {

                                                        d++;

                                                }

                                        }

                                        index *= (PIN_MAP_LEGAL_CHAR_COUNT + 1);

                                        index += (c - d - 'A' + 1);

                                }

                                /*

                                      printf("'\n");

                                */

                                nodes->pin_col = index;

                                if (index > max_col)

                                {

                                        max_col = index;

                                }

                                else if (index < min_col)

                                {

                                        min_col = index;

                                }

                        }

                        else

                        {

                                /* default is column zero */

                                nodes->pin_col = 0;

                        }

                }

                nodecnt++;

                nodes = nodes->sktnext;

        }

        chip->max_pin_col = max_col == -BIG ? 0 : max_col;

        chip->min_pin_col = min_col == BIG ? 0 : min_col;

        chip->max_pin_row = max_row == -BIG ? 0 : max_row;

        chip->min_pin_row = min_row == BIG ? 0 : min_row;

        /*

          printf("chip %10s col %3d to %3d , row %3d to

          %3d\n",chip->identifier,max_col,min_col,max_row,min_row);

        */

        /* know the number of nodes now allocate storage for the pointers

           to be used by qsort() */

        sort_list = calloc (nodecnt, sizeof (node_t *));

        /* grab hold of all of the pointers */

        nodes = chip->nodes;

        nodecnt = 0;

        while (nodes)

        {

                sort_list[nodecnt++] = nodes;

                nodes = nodes->sktnext;

        }

        /* sort them */

        if (nodecnt)

        {

                int i;

                qsort ((void *) sort_list, nodecnt, sizeof (node_t *), &sort_nodes_compar);

                /* and now rebuild the list based on the sorted list */

                chip->nodes = sort_list[0];

                chip->lastnode = sort_list[nodecnt - 1];

                /* relink the list */

                for (i = 0; i < (nodecnt - 1); i++)

                {

                        sort_list[i]->sktnext = sort_list[i + 1];

                }

                sort_list[nodecnt - 1]->sktnext = NULL;

        }

        free (sort_list);

        /* check for overrides in case there are missing rows/cols */

        if (get_generic_value (&chip->generics, "min_pin_row", gen) == IS_ATTRIBUTE)

        {

                chip->min_pin_row = eval_expression (gen->expr, &chip->generics);

        }

        if (get_generic_value (&chip->generics, "max_pin_row", gen) == IS_ATTRIBUTE)

        {

                chip->max_pin_row = eval_expression (gen->expr, &chip->generics);

        }

        if (get_generic_value (&chip->generics, "min_pin_col", gen) == IS_ATTRIBUTE)

        {

                chip->min_pin_col = eval_expression (gen->expr, &chip->generics);

        }

        if (get_generic_value (&chip->generics, "max_pin_col", gen) == IS_ATTRIBUTE)

        {

                chip->max_pin_col = eval_expression (gen->expr, &chip->generics);

        }

}

/* we have a pair of pointers to array elements */

static int sort_socket_compar (const void *p, const void *q)

{

        return strcmp ((*(socket_t **) p)->identifier, (*(socket_t **) q)->identifier);

}

/* this function sorts all of  sockets into alphanumeric order */

socket_t *sort_sockets (socket_t **head)

{

        socket_t **sort_list, *chip = *head;

        int sktcnt = 0;

        while (chip)

        {

                sktcnt++;

                chip = chip->next;

        }

        /* know the number of nodes now allocate storage for the pointers

           to be used by qsort() */

        sort_list = calloc (sktcnt, sizeof (socket_t *));

        /* grab hold of all of the pointers */

        chip = *head;

        sktcnt = 0;

        while (chip)

        {

                sort_list[sktcnt++] = chip;

                chip = chip->next;

        }

        /* sort them */

        if (sktcnt)

        {

                int i;

                qsort ((char *) sort_list, sktcnt, sizeof (socket_t *), &sort_socket_compar);

                /* and now rebuild the list based on the sorted list */

                *head = sort_list[0];

                /* relink the list */

                for (i = 0; i < (sktcnt - 1); i++)

                {

                        sort_list[i]->next = sort_list[i + 1];

                }

                sort_list[sktcnt - 1]->next = NULL;

        }

        free (sort_list);

        return *head;

}

/* compile regular expression according

   to Vertical expectations */

/* What is required is a whole string match. In order to

   achieve this, the regular expression is bracketed with

   ^ and $ which mean in this context 'match start of string'

   and 'match end of string' */

int vert_regcomp (vert_regex_t **vert_preg, char *expr)

{

        int rc;

        vert_regex_t *preg;

        /* allocate structure members */

        preg = calloc (1, sizeof (vert_regex_t));

        *vert_preg = preg;

        rc = check_wildcard (expr);

        if (rc != TCL_OK)

        {

                preg->buff = malloc (3);

                strcpy (preg->buff, "^$");

        }

        else

        {

                preg->buff = malloc (strlen (expr) + 3);

                sprintf (preg->buff, "^%s$", expr);

        }

        /*  printf("-- compare '%s'\n",preg->buff); */

        rc = regcomp (preg->preg, preg->buff, REG_EXTENDED | REG_ICASE);

        return rc;

}

/* tidy up */

int vert_regfree (vert_regex_t **vert_preg)

{

        regfree ((*vert_preg)->preg);

        free ((*vert_preg)->buff);

        free (*vert_preg);

        *vert_preg = NULL;

        return 0;

}