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 <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

#include <sys/types.h>

#include <regex.h>

/* TCL/Tk declarations */

#include "vertcl_main.h" 

#include "expression.h"

#include "generic.h"

#include "database.h"

#include "routing.h"

#include "cmdparse.h"

#include "cmdlog.h"

#include "sorting.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;

   }