distrib/sources/yagle/fcl/fcl_partition.c

   1 /****************************************************************************/
   2 /*                                                                          */
   3 /*                      Chaine de CAO & VLSI   Alliance                     */
   4 /*                                                                          */
   5 /*    Produit : FCL  v1.02                                                  */
   6 /*    Fichier : fcl_partition.c                                             */
   7 /*                                                                          */
   8 /*    (c) copyright 1996 Laboratoire MASI equipe CAO & VLSI                 */
   9 /*    Tous droits reserves                                                  */
  10 /*    Support : e-mail alliance-support@asim.lip6.fr                        */
  11 /*                                                                          */
  12 /*                                                                          */
  13 /****************************************************************************/
  14
  15 #include "fcl_headers.h"
  16
  17
  18 /*
  19   ####====================================================================####
  20   ##                                                                        ##
  21   ##                           add_partition()                              ##
  22   ##                                                                        ##
  23   ## Ajoute un element dans une partition, si cette partition n'existe pas  ##
  24   ## elle est alors creee                                                   ##
  25   ##                                                                        ##
  26   ####====================================================================####
  27   ##  entree : pointeur sur la liste des partitions                         ##
  28   ##         : pointeur sur la structure de l'element ajoute                ##
  29   ##         : valeur du label de l'element                                 ##
  30   ##         : type de l'element (TRS ou SIG)                               ##
  31   ##  sortie : un pointeur sur le debut des partitions                      ##
  32   ####====================================================================####
  33 */
  34 partition_list *
  35 addpartition(ptpartition, ptdata, valeur, type)
  36     partition_list *ptpartition;
  37     void           *ptdata;
  38     fcl_label       valeur;
  39     char            type;
  40 {
  41     partition_list *pt;
  42
  43     pt = getpartition(ptpartition, valeur, type);
  44
  45     if (pt == (partition_list *) NULL) {
  46         pt = (partition_list *) mbkalloc(sizeof(partition_list));
  47
  48         pt->NEXT = ptpartition;
  49         pt->LABEL = valeur;
  50         pt->NBELEM = 0;
  51         pt->TYPE = type;
  52         pt->DATA = (void *) NULL;
  53         ptpartition = pt;
  54     }
  55
  56     pt->DATA = (void *) addchain((chain_list *) pt->DATA, ptdata);
  57     pt->NBELEM++;
  58
  59     return ptpartition;
  60 }
  61
  62
  63 /*
  64   ####====================================================================####
  65   ##                                                                        ##
  66   ##                         small_partition()                              ##
  67   ##                                                                        ##
  68   ## renvoie un pointeur sur la partition ayant le moins d'elements         ##
  69   ## Les autres partitions sont detruites                                   ##
  70   ##                                                                        ##
  71   ####====================================================================####
  72   ##  entree : pointeur sur la liste des partitions                         ##
  73   ##  sortie : un pointeur sur le debut des partitions                      ##
  74   ####====================================================================####
  75 */
  76 partition_list *
  77 smallestpartition(ptpartition)
  78     partition_list *ptpartition;
  79 {
  80     for (; ptpartition->NEXT;) {
  81         if (ptpartition->NEXT->NBELEM < ptpartition->NBELEM) {
  82             ptpartition = delpartition(ptpartition, ptpartition->LABEL, ptpartition->TYPE);
  83         }
  84         else {
  85             ptpartition = delpartition(ptpartition, ptpartition->NEXT->LABEL, ptpartition->NEXT->TYPE);
  86         }
  87     }
  88
  89     return ptpartition;
  90 }
  91
  92 /*
  93   ####====================================================================####
  94   ##                                                                        ##
  95   ##                           get_partition()                              ##
  96   ##                                                                        ##
  97   ## Recherche une partition suivant un label partitculier                  ##
  98   ##                                                                        ##
  99   ####====================================================================####
 100   ##  entree : pointeur sur la liste des partitions                         ##
 101   ##         : valeur du label de l'element                                 ##
 102   ##         : type de l'element (TRS ou SIG)                               ##
 103   ##  sortie : un pointeur sur la partition                                 ##
 104   ####====================================================================####
 105 */
 106 partition_list *
 107 getpartition(ptpartition, valeur, type)
 108     partition_list *ptpartition;
 109     fcl_label       valeur;
 110     char            type;
 111 {
 112     partition_list *pt;
 113
 114     for (pt = ptpartition; pt; pt = pt->NEXT)
 115         if (pt->LABEL == valeur && pt->TYPE == type)
 116             return pt;
 117
 118     return (partition_list *) NULL;
 119 }
 120
 121 /*
 122   ####====================================================================####
 123   ##                                                                        ##
 124   ##                           delpartition()                               ##
 125   ##                                                                        ##
 126   ## Supprime  une partition suivant un label partitculier                  ##
 127   ##                                                                        ##
 128   ####====================================================================####
 129   ##  entree : pointeur sur la liste des partitions                         ##
 130   ##         : valeur du label de l'element                                 ##
 131   ##         : type de l'element (TRS ou SIG)                               ##
 132   ##  sortie : un pointeur sur la tete des partitions                       ##
 133   ####====================================================================####
 134 */
 135 partition_list *
 136 delpartition(ptpartition, valeur, type)
 137     partition_list *ptpartition;
 138     fcl_label       valeur;
 139     char            type;
 140 {
 141     partition_list *pt;
 142     partition_list *pt_before = ptpartition;
 143
 144     for (pt = ptpartition; pt; pt_before = pt, pt = pt->NEXT) {
 145         if (pt->LABEL == valeur && pt->TYPE == type) {
 146             if (pt_before == pt)
 147                 /* On veut enlever l'element de tete */
 148                 ptpartition = pt->NEXT;
 149             else
 150                 pt_before->NEXT = pt->NEXT;
 151
 152             freechain((chain_list *) pt->DATA);
 153
 154             mbkfree(pt);
 155             return ptpartition;
 156         }
 157     }
 158     return ptpartition;
 159 }
 160
 161 /*
 162   ####====================================================================####
 163   ##                                                                        ##
 164   ##                         removepartitionelement()                       ##
 165   ##                                                                        ##
 166   ## Supprime un element dans une partition, si cette partition est vide    ##
 167   ## elle est alors detruite                                                ##
 168   ##                                                                        ##
 169   ####====================================================================####
 170   ##  entree : pointeur sur la liste des partitions                         ##
 171   ##         : pointeur sur la structure de l'element enleve                ##
 172   ##         : valeur du label de l'element                                 ##
 173   ##         : type de l'element (TRS ou SIG)                               ##
 174   ##  sortie : un pointeur sur le debut des partitions                      ##
 175   ####====================================================================####
 176 */
 177 partition_list *
 178 removepartitionelement(ptpartition, valeur, type)
 179     partition_list *ptpartition;
 180     fcl_label       valeur;
 181     char            type;
 182 {
 183     partition_list *pt;
 184
 185     pt = getpartition(ptpartition, valeur, type);
 186     if (!--pt->NBELEM) ptpartition = delpartition(ptpartition, valeur, type);
 187
 188     return ptpartition;
 189 }
 190
 191
 192 /*
 193   ####====================================================================####
 194   ##                                                                        ##
 195   ##                        comparepartition()                              ##
 196   ##                                                                        ##
 197   ## Compare les deux listes de partitions (model, circuit)                 ##
 198   ## Les partitions du circuit qui n'existent pas dans le model sont        ##
 199   ## supprime; Verifie qu'a chaque partition du model correspond une        ##
 200   ## partition dans le circuit                                              ##
 201   ##                                                                        ##
 202   ####====================================================================####
 203   ##  entree : pointeur sur la liste des partitions                         ##
 204   ##         : pointeur sur la structure de l'element enleve                ##
 205   ##         : valeur du label de l'element                                 ##
 206   ##         : type de l'element (TRS ou SIG)                               ##
 207   ##  sortie : un pointeur sur le debut des partitions                      ##
 208   ####====================================================================####
 209 */
 210 partition_list *
 211 comparepartition(ptpartition_c, ptpartition_m)
 212     partition_list *ptpartition_c;
 213     partition_list *ptpartition_m;
 214 {
 215     partition_list *pt;
 216     partition_list *ptcandidat;
 217     partition_list *ptnext;
 218     chain_list     *ptchain;
 219     losig_list     *ptlosig;
 220
 221     /* Supprimer toutes les partitions du circuit pour lesquelles */
 222     /* des partitions de poids identiques n'existent pas dans le  */
 223     /* graphe de la cellule memoire                               */
 224     /* Marquer corrompu les signaux  ou les transitors de ces     */
 225     /* partitions supprimees                                      */
 226
 227     for (pt = ptpartition_c; pt; pt = ptnext) {
 228         if ((ptcandidat = getpartition(ptpartition_m, pt->LABEL, pt->TYPE)) == NULL || pt->LABEL == 0) {
 229             ptnext = pt->NEXT;
 230             ptpartition_c = delpartition(ptpartition_c, pt->LABEL, pt->TYPE);
 231         }
 232         else ptnext = pt->NEXT;
 233     }
 234
 235     /* Verifie qu'a chaque partition du sous-graphe   */
 236     /* il existe une partition de taille au moins     */
 237     /* egale dans le graphe                           */
 238     for (pt = ptpartition_m; pt; pt = pt->NEXT) {
 239         if (pt->LABEL == 0 && pt->TYPE == 'S') {
 240             for (ptchain = pt->DATA; ptchain; ptchain = ptchain->NEXT) {
 241                 ptlosig = (losig_list *) (ptchain->DATA);
 242                 fclCorruptLosig(ptlosig);
 243             }
 244         }
 245         else if ((ptcandidat = getpartition(ptpartition_c, pt->LABEL, pt->TYPE)) == NULL || ptcandidat->NBELEM < pt->NBELEM) {
 246             /* Pas d'isomorphisme                      */
 247             if (FCL_TRACE_LEVEL > 1) {
 248                 printf("*** FCL Match Failed as partition label '%d' in model has no correspondance\n", pt->LABEL);
 249                 displaypartition(pt);
 250             }
 251
 252             while (ptpartition_c) {
 253                 ptpartition_c = delpartition(ptpartition_c, ptpartition_c->LABEL, ptpartition_c->TYPE);
 254             }
 255             break;
 256         }
 257     }
 258
 259     return ptpartition_c;
 260 }
 261
 262
 263 void
 264 printpartition(ptpartition)
 265     partition_list *ptpartition;
 266 {
 267     partition_list *pt;
 268
 269     for (pt = ptpartition; pt; pt = pt->NEXT) {
 270         printf("Partition Type=%c label=%d nb elements=%d\n", pt->TYPE, pt->LABEL, pt->NBELEM);
 271     }
 272 }
 273
 274 void
 275 displaypartition(ptpartition)
 276     partition_list *ptpartition;
 277 {
 278     losig_list     *ptsig;
 279     chain_list     *ptchain;
 280
 281     if (ptpartition->TYPE == 'T')
 282         for (ptchain = ptpartition->DATA; ptchain; ptchain = ptchain->NEXT) {
 283             ptsig = ((lotrs_list *) ptchain->DATA)->GRID->SIG;
 284             if (ptsig->NAMECHAIN == NULL)
 285                 printf("#### Vecteur candidat G : %ld\n", ptsig->INDEX);
 286             else
 287                 printf("#### Vecteur candidat G : %s\n",
 288                        (char *) ptsig->NAMECHAIN->DATA);
 289
 290             ptsig = ((lotrs_list *) ptchain->DATA)->SOURCE->SIG;
 291             if (ptsig->NAMECHAIN == NULL)
 292                 printf("#### Vecteur candidat S : %ld\n", ptsig->INDEX);
 293             else
 294                 printf("#### Vecteur candidat S : %s\n",
 295                        (char *) ptsig->NAMECHAIN->DATA);
 296
 297             ptsig = ((lotrs_list *) ptchain->DATA)->DRAIN->SIG;
 298             if (ptsig->NAMECHAIN == NULL)
 299                 printf("#### Vecteur candidat D : %ld\n", ptsig->INDEX);
 300             else
 301                 printf("#### Vecteur candidat D : %s\n",
 302                        (char *) ptsig->NAMECHAIN->DATA);
 303         }
 304     else {
 305         for (ptchain = ptpartition->DATA; ptchain; ptchain = ptchain->NEXT) {
 306             ptsig = (losig_list *) ptchain->DATA;
 307             if (ptsig->NAMECHAIN == NULL)
 308                 printf("#### Vecteur candidat : %ld\n", ptsig->INDEX);
 309             else
 310                 printf("#### Vecteur candidat : %s\n",
 311                        (char *) ptsig->NAMECHAIN->DATA);
 312         }
 313     }
 314
 315 }