/* $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 #include #include #include #include #include /* 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; }