distrib/sources/bdd/log_thashloc.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_thashloc.c,v 1.4 2005/05/03 08:26:33 antony Exp $"
  34
  35 /*--------------------------------------------------------------------------
  36    la table de hachage local
  37    la version du 14.12.90
  38   -------------------------------------------------------------------------- */
  39 #include <stdlib.h>
  40 #include  MUT_H
  41 #include LOG_H
  42 #include AVT_H
  43
  44
  45 /* les fonction de l'utilisateurs :
  46    ------------------------------
  47
  48    initialisation au depart des pointeurs de vertex a NULL.
  49    Les fonctions qui utilisent le hachage peuvent renvoye DDBTABLE_PLEINE
  50    si la table est trop remplie.
  51    Il n'y a pas de destruction possible d'un element.
  52
  53    a. creation de table
  54
  55    pTableLoc createTabLoc(len)
  56    int len;
  57
  58    b. destruction de la table
  59
  60    void destroyTabLoc(pTab)
  61    pTableLoc pTab;
  62
  63    c. re-allocation d'une table de hachage
  64
  65    reAllocTabLoc(pTab)
  66    pTableLoc pTab;
  67
  68    d. recherche d'un element
  69
  70    pNode searchTabLoc(pTab,high,low)
  71    pTableLoc pTab;
  72    pVertexLoc high,low;
  73
  74    e. ajout d'un element
  75
  76    int addTabLoc(pTab,pLoc)
  77    pTableLoc pTab;
  78    pVertexLoc pLoc;
  79
  80    f. affichage total d'une table
  81
  82    void displayLoc(pTab)
  83    pTableLoc pTab;
  84
  85
  86  */
  87
  88 /*-------------------- la fonction de hachage ---------------------------- */
  89
  90 long
  91 hashLoc (high, low)
  92      pNode high, low;
  93 {
  94   return (abs (high->index + low->index +
  95                (((long) high) >> 4) + (((long) low) >> 5) +
  96                (long) high + (long) low));
  97 }
  98
  99 /*--------------- La table de hachage pour des LOC ------------ */
 100
 101 /* la fonction de creation de table de hachage pour les LOC .
 102    On alloue en premier lieu une structure TABLE, puis une table
 103    qui n'est rien d'autre qu'un tableau de pointeurs de LOC. Il est
 104    donc possible de travailler avec plusieurs table a la fois. */
 105
 106 pTableLoc
 107 createTabLoc (len)
 108      int len;
 109 {
 110   pTableLoc pTab;
 111   pVertexLoc pLoc;
 112   int i;
 113
 114   if (!(pTab = (pTableLoc) mbkalloc (sizeof (struct tableLoc))))
 115     {
 116       avt_errmsg(LOG_ERRMSG,"000",AVT_FATAL,"158");
 117 //      printf ("allocation impossible\n");
 118 //      EXIT (-1);
 119     }
 120   pTab->lenTabLoc = len;
 121
 122   if (!(pLoc = (pVertexLoc) mbkalloc (len * sizeof (struct vertexLoc))))
 123     {
 124       avt_errmsg(LOG_ERRMSG,"000",AVT_FATAL,"159");
 125 //      printf ("allocation impossible\n");
 126 //      EXIT (-1);
 127     }
 128   pTab->pLoc = pLoc;
 129   for (i = 0; i < len; i++)
 130     {
 131       pLoc->oper = EMPTYTH;     /* -1 */
 132       pLoc++;
 133     }
 134   return (pTab);
 135 }
 136
 137    /* destruction d'une table de hachage */
 138
 139 void
 140 destroyTabLoc (pTab)
 141      pTableLoc pTab;
 142 {
 143   mbkfree (pTab->pLoc);
 144   mbkfree (pTab);
 145 }
 146
 147   /* recherche d'un element dans la table
 148      renvoie NULL si la recherche echoue. */
 149
 150 pNode
 151 searchTabLoc (pTab, high, low, oper)
 152      pTableLoc pTab;
 153      pNode high, low;
 154      short oper;
 155 {
 156   pVertexLoc pLoc;
 157   int indice;
 158
 159   /* un seul acces permis */
 160
 161   indice = hashLoc (high, low) % pTab->lenTabLoc;
 162   pLoc = pTab->pLoc;
 163   if (pLoc[indice].oper == oper)
 164     if (high == pLoc[indice].high && low == pLoc[indice].low)
 165       return (pLoc[indice].father);
 166   return (NULL);
 167 }
 168
 169  /* ajout d'un element a la table */
 170
 171
 172 long
 173 addTabLoc (pTab, high, low, father, oper)
 174      pTableLoc pTab;
 175      pNode high, low, father;
 176      short oper;
 177 {
 178   pVertexLoc pLoc;
 179   long indice;
 180
 181   /* un seul acces permis */
 182
 183   indice = hashLoc (high, low) % pTab->lenTabLoc;
 184   pLoc = pTab->pLoc;
 185   pLoc[indice].oper = oper;
 186   pLoc[indice].high = high;
 187   pLoc[indice].low = low;
 188   pLoc[indice].father = father;
 189   return (indice);              /* retourne la place utilisee */
 190 }
 191
 192
 193 /* affichage des elements de la table */
 194
 195 void
 196 displayLoc (pTab)
 197      pTableLoc pTab;
 198 {
 199   int i;
 200   int co = 0;
 201   pVertexLoc pLoc;
 202
 203   pLoc = pTab->pLoc;
 204
 205   printf ("\n---------------------------------------------------------------");
 206   printf ("---------\n               AFFICHAGE DE LA TABLE DE HACHAGE\n\n");
 207
 208   for (i = 0; i < pTab->lenTabLoc; i++)
 209     {
 210       if (pLoc[i].oper != EMPTYTH)
 211         {
 212           co++;
 213           printf ("****** indice %d ****** \n", i);
 214           printf ("HIGH %ld LOW %ld FATHER %ld\n", (long) pLoc[i].high, (long) pLoc[i].low, (long) pLoc[i].father);
 215           printf ("\n");
 216         }
 217     }
 218   printf ("\n****** Nombre de noeuds dans la table  = %d\n", co);
 219 }
 220
 221
 222
 223 /*------------------------------------------------------------------------------
 224 videTabLoc       :vide une table de hachage locale.
 225 -------------------------------------------------------
 226 parametres       :une table de hashage locale.
 227 -------------------------------------------------------
 228 return           :rien.
 229 ------------------------------------------------------------------------------*/
 230
 231 void
 232 videTabLoc (pTab)
 233      pTableLoc pTab;
 234 {
 235   pVertexLoc pLoc;
 236   int i;
 237
 238   pLoc = pTab->pLoc;
 239
 240
 241   for (i = 0; i < pTab->lenTabLoc; i++)
 242     {
 243       pLoc[i].oper = EMPTYTH;
 244     }
 245 }