distrib/sources/bdd/log_thashbdd.c

   1 /*
   2  * This file is part of the Alliance CAD System
   3  * Copyright (C) Laboratoire LIP6 - Département ASIM
   4  * Universite Pierre et Marie Curie
   5  *
   6  * Home page          : http://www-asim.lip6.fr/alliance/
   7  * E-mail support     : mailto:alliance-support@asim.lip6.fr
   8  *
   9  * This progam is  free software; you can redistribute it  and/or modify it
  10  * under the  terms of the GNU  General Public License as  published by the
  11  * Free Software Foundation;  either version 2 of the License,  or (at your
  12  * option) any later version.
  13  *
  14  * Alliance VLSI  CAD System  is distributed  in the hope  that it  will be
  15  * useful, but WITHOUT  ANY WARRANTY; without even the  implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
  17  * Public License for more details.
  18  *
  19  * You should have received a copy  of the GNU General Public License along
  20  * with the GNU C Library; see the  file COPYING. If not, write to the Free
  21  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  22  */
  23
  24 /*
  25  * Tool    : ABL, BDD, HT Librarie
  26  * Date    : 1991,92
  27  * Author  : Luc Burgun
  28  * Modified by Czo <Olivier.Sirol@lip6.fr> 1996,97
  29  */
  30
  31
  32
  33 #ident "$Id: log_thashbdd.c,v 1.5 2006/03/20 10:44:20 fabrice Exp $"
  34
  35 /*--------------------------------------------------------------------------
  36    la table de hachage des BDD
  37    la version du 10.12.90
  38   -------------------------------------------------------------------------- */
  39
  40 #include <stdlib.h>
  41 #include  MUT_H
  42 #include LOG_H
  43 #include AVT_H
  44
  45 #undef NB_APPEL_MAX
  46 #define NB_APPEL_MAX 50
  47
  48 /* les fonction de l'utilisateurs :
  49    ------------------------------
  50
  51    initialisation au depart des pointeurs de vertex a NULL.
  52    un pointeur de Vertex desalloue est mis a BDDDELETE.
  53    Les fonctions qui utilisent le hachage peuvent renvoye BDDTABLE_PLEINE
  54    si la table est trop remplie.
  55
  56    a. creation de table
  57
  58    pTableBdd createTableBdd(len)
  59    int len;
  60
  61    b. destruction de la table
  62
  63    destroyTableBdd(pTab)
  64    pTableBdd pTab;
  65
  66    c. re-allocation d'une table de hachage
  67
  68    reAllocTableBdd(pTab)
  69    pTableBdd pTab;
  70
  71    d. recherche d'un element
  72
  73    pNode searchTableBdd(pTab,index,high,low)
  74    pTableBdd pTab;
  75    int index;
  76    pNode high,low;
  77
  78    e. ajout d'un element
  79
  80    int addTableBdd(pTab,pBdd)
  81    pTableBdd pTab;
  82    pNode pBdd;
  83
  84    f. destruction d'un element
  85
  86    int deleteTableBdd(pTab,key)
  87    pTableBdd pTab;
  88    pNode pBdd;
  89
  90    g. affichage total d'une table
  91
  92    void displayBdd(pTab)
  93    pTableBdd pTab;
  94
  95    h. le garbage collector d'une table de hachage
  96
  97    void gcTableBdd(pTab);
  98    pTableBdd pTab;
  99
 100
 101  */
 102
 103 /*-------------------- la fonction de hachage ---------------------------- */
 104
 105 long
 106 hashBdd (index, high, low)
 107      int index;
 108      pNode high, low;
 109 {
 110   return (abs (index + ((long) high << 1) + (long) low +
 111                ((long) high >> 4) + ((long) low >> 5)));
 112 }
 113
 114 /*--------------- la fonction de changement de cle ------------------------- */
 115
 116 long
 117 newKeyBdd (index, high, low)
 118      int index;
 119      pNode high, low;
 120 {
 121   return (index + (index << 2) + (long) high + ((long) low << 1));
 122 }
 123
 124 /*--------------- La table de hachage pour des BDD ------------ */
 125
 126 /* la fonction de creation de table de hachage pour les BDD .
 127    On alloue en premier lieu une structure TABLE, puis une table
 128    qui n'est rien d'autre qu'un tableau de pointeurs de BDD. Il est
 129    donc possible de travailler avec plusieurs tables a la fois. */
 130
 131 pTableBdd
 132 createTableBdd (len)
 133      int len;
 134 {
 135   pTableBdd pTab;
 136   pNode *pBdd;
 137   int i;
 138
 139   if (!(pTab = (pTableBdd) mbkalloc (sizeof (struct tableBdd))))
 140     {
 141       avt_errmsg(LOG_ERRMSG,"000",AVT_FATAL,"160");
 142 //      printf ("impossible allocation\n");
 143 //      EXIT (-1);
 144     }
 145   pTab->lenTableBdd = len;
 146
 147   if (!(pBdd = (pNode *) mbkalloc (len * sizeof (pNode))))
 148     {
 149       avt_errmsg(LOG_ERRMSG,"000",AVT_FATAL,"161");
 150 //      printf ("impossible allocation\n");
 151 //      EXIT (-1);
 152     }
 153   pTab->pBdd = pBdd;
 154   for (i = 0; i < len; i++)
 155     {
 156       *pBdd = NULL;
 157       pBdd++;
 158     }
 159   pTab->compteur = 0;
 160   return (pTab);
 161 }
 162
 163    /* destruction d'une table de hachage */
 164
 165 void
 166 destroyTableBdd (pTab)
 167      pTableBdd pTab;
 168 {
 169   pNode *pBdd;
 170
 171   pBdd = pTab->pBdd;
 172   mbkfree (pBdd);
 173   mbkfree (pTab);
 174 }
 175
 176 /*------------------------------------------------------------------------------
 177 markBddLst          :met a jour les marques de l'ensemble des graphes de LstGdb.
 178 -------------------------------------------------------
 179 parametres          :une liste LstGdb.
 180 -------------------------------------------------------
 181 return                  :rien.
 182 ------------------------------------------------------------------------------*/
 183 /*
 184    void markBddLst(pC,value)
 185    pCircuit pC;
 186    int value;
 187    {
 188    pNode pBdd;
 189
 190    pEl = (pC->pTO)->pElemT ;
 191
 192    for (i =0 ; i < (pC->pTO)->lenTable; i++)
 193    {
 194    if(pEl->value != VIDE && pEl->value != DELETE)
 195    markBdd((pNode)pEl->value) ;
 196    pEl++ ;
 197    }
 198    }
 199  */
 200
 201   /* re-allocation d'une table de hachage devenue trop petite... */
 202
 203 pTableBdd
 204 reAllocTableBdd (pTab)
 205      pTableBdd pTab;
 206 {
 207   int i;
 208   pNode *pBdd;
 209   pTableBdd pTabBis;
 210
 211   if (pTab->lenTableBdd > MAX_SIZE_BDD)
 212     {
 213       avt_errmsg(LOG_ERRMSG,"002",AVT_FATAL);
 214 //      printf ("BDD's system : not enough memory...\n");
 215 //      EXIT (-1);
 216     }
 217   pTabBis = createTableBdd (pTab->lenTableBdd * 3);        /* trois fois plus grande */
 218   pBdd = pTab->pBdd;
 219   for (i = 0; i < pTab->lenTableBdd; i++)
 220     {
 221       if (*pBdd != NULL && *pBdd != BDDDELETE)        /* la recopie */
 222         addTableBdd (pTabBis, *pBdd);
 223       pBdd++;
 224     }
 225   destroyTableBdd (pTab);
 226   return (pTabBis);
 227 }
 228
 229   /* recherche d'un element dans la table
 230      renvoie NULL si la recherche echoue. */
 231
 232 pNode
 233 searchTableBdd (pTab, index, high, low)
 234      pTableBdd pTab;
 235      int index;
 236      pNode high, low;
 237 {
 238   int co = 0;
 239   pNode pBddCur;
 240   int key = index;
 241   int indice;
 242
 243   do
 244     {
 245       if (co++ > NB_APPEL_MAX)
 246         return (BDDTABLE_PLEINE);
 247       indice = hashBdd (key, high, low) % pTab->lenTableBdd;
 248       pBddCur = *((pTab->pBdd) + indice);
 249       if (pBddCur != NULL && pBddCur != BDDDELETE)
 250         if (high == pBddCur->high &&
 251             low == pBddCur->low &&
 252             index == pBddCur->index)
 253           return (pBddCur);
 254       key = newKeyBdd (key, high, low);
 255     }
 256   while (pBddCur != NULL);
 257   return (NULL);
 258 }
 259
 260  /* ajout d'un element a la table */
 261
 262
 263 long
 264 addTableBdd (pTab, pBdd)
 265      pTableBdd pTab;
 266      pNode pBdd;
 267 {
 268   int co = 0;
 269   pNode *pBddCur;
 270   int index = pBdd->index;
 271   pNode high = pBdd->high;
 272   pNode low = pBdd->low;
 273   int key = index;
 274   long indice;
 275
 276   if (pTab->compteur++ > (pTab->lenTableBdd) * 8 / 10)        /* remplissage au 8/10 */
 277     return (TABLE_PLEINE);
 278   do
 279     {
 280       if (co++ > NB_APPEL_MAX)
 281         return (TABLE_PLEINE);
 282       indice = hashBdd (key, high, low) % pTab->lenTableBdd;
 283       pBddCur = ((pTab->pBdd) + indice);
 284       if (*pBddCur == NULL || *pBddCur == BDDDELETE)
 285         {
 286           *pBddCur = pBdd;
 287           return (indice);        /* retourne la place utilisee */
 288         }
 289       key = newKeyBdd (key, high, low);
 290     }
 291   while (1);
 292 }
 293
 294
 295    /* elimination d'un element de la table */
 296
 297
 298 long
 299 deleteTableBdd (pTab, pBdd)
 300      pTableBdd pTab;
 301      pNode pBdd;
 302 {
 303   int co = 0;
 304   pNode *pBddCur;
 305   pNode high = pBdd->high;
 306   pNode low = pBdd->low;
 307   int key = pBdd->index;
 308   int indice;
 309
 310   do
 311     {
 312       if (co++ > NB_APPEL_MAX)
 313         return (TABLE_PLEINE);
 314       indice = hashBdd (key, high, low) % pTab->lenTableBdd;
 315       pBddCur = (pTab->pBdd) + indice;
 316       if (*pBddCur != NULL && *pBddCur != BDDDELETE)
 317         {
 318           if (pBdd == *pBddCur)
 319             {
 320               *pBddCur = BDDDELETE;
 321               return (DELETE);
 322             }
 323         }
 324       key = newKeyBdd (key, high, low);
 325     }
 326   while (pBddCur != NULL);
 327   return ((long) NULL);
 328 }
 329
 330 /* affichage des elements de la table */
 331
 332 void
 333 displayHashBdd (pTab)
 334      pTableBdd pTab;
 335 {
 336   int i;
 337   int co = 0;
 338   pNode *pBdd;
 339
 340   pBdd = pTab->pBdd;
 341   {
 342     printf ("\n---------------------------------------------------------------");
 343     printf ("---------\n               AFFICHAGE DE LA TABLE DE HACHAGE\n\n");
 344   }
 345   for (i = 0; i < pTab->lenTableBdd; i++)
 346     {
 347       if (*pBdd != NULL && *pBdd != BDDDELETE)
 348         {
 349           co++;
 350           printf ("****** indice %d ****** \n", i);
 351           displayBdd (*pBdd , FALSE);
 352           printf ("\n");
 353         }
 354       pBdd++;
 355     }
 356   printf ("\n****** Nombre de noeuds dans la table  = %d\n", co);
 357 }