spiceparser/names.c

   1 /********************
   2     This file is part of the software library CADLIB written by Conrad Ziesler
   3     Copyright 2003, Conrad Ziesler, all rights reserved.
   4
   5 *************************
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19
  20 ******************/
  21 /* names.c,  efficient string table support
  22  Conrad Ziesler
  23 */
  24
  25
  26
  27 #include <stdio.h>
  28 #include "debug.h"
  29
  30 #define __NAMES_PRIVATE__
  31 #include "names.h"
  32
  33 static namehash_t *names_newhash(names_t *nt, int refp, const char *str)
  34 {
  35   namehash_t *b;
  36   int q=strlen(str);
  37   b=malloc(sizeof(namehash_t)+q);
  38   assert(b!=NULL);
  39   b->refp=refp;
  40   b->magic=NAME_MAGIC;
  41   strcpy(b->str,str);
  42   nt->bytesalloc+=sizeof(namehash_t)+q;
  43   nt->namebytes+=q;
  44   nt->qtynames++;
  45
  46   return b;
  47 }
  48
  49
  50 static unsigned int names_ptrhash(names_t *nt, int refp)
  51 {
  52   unsigned q=nt->qtybins;
  53   unsigned int v,  r=0;
  54
  55   v=(unsigned)refp;
  56   /*
  57   v>>=2;
  58   r= ((v%(7*q+(q/3)+5))^v) % q;
  59   */
  60   r= v ^ (v>>3) ^ ((v/3)>>15) ^ ((~v)>>11);
  61   return r%q;
  62 }
  63
  64 static unsigned int names_strhash(names_t *nt, const char *str)
  65 {
  66   unsigned q=nt->qtybins;
  67   unsigned int r=0;
  68
  69   while(*str!=0)
  70     {
  71       r+= (str[0]^(r%q));
  72       r%=q;
  73       str++;
  74     }
  75
  76   return r%q;
  77 }
  78
  79
  80 char *names_lookup(names_t *nt, int refp)
  81 {
  82   unsigned int id;
  83   namehash_t *nh;
  84   int i=0;
  85
  86   id=names_ptrhash(nt,refp);
  87
  88   for(nh=nt->cref[id];nh!=NULL;nh=nh->cref,i++)
  89     {
  90       assert(nh->magic==NAME_MAGIC);
  91       if(refp==nh->refp){ return nh->str; }
  92     }
  93
  94   return NULL;
  95 }
  96
  97 int names_check(names_t *nt, const char *name)
  98 {
  99   unsigned int id;
 100   namehash_t *nh;
 101   int i=0;
 102
 103   id=names_strhash(nt,name);
 104
 105   for(nh=nt->cstr[id];nh!=NULL;nh=nh->cstr,i++)
 106     {
 107       assert(nh->magic==NAME_MAGIC);
 108       if(strcmp(name,nh->str)==0){ return nh->refp; }
 109     }
 110   return -1;
 111 }
 112
 113
 114
 115 void  names_add(names_t *nt, int refp, const char *name)
 116 {
 117   unsigned int idn,idr,id;
 118   namehash_t *nh,*nhref=NULL,*nhstr=NULL;
 119   int i=0;
 120
 121   if(nt->qtynames>((5*nt->qtybins)/4)) /* double table size each time we outgrow old table */
 122     names_rehash(nt, (2*nt->qtynames) );
 123
 124   idn=names_strhash(nt,name);
 125   idr=names_ptrhash(nt,refp);
 126
 127   for(nh=nt->cref[idr];nh!=NULL;nh=nh->cref,i++)
 128     {
 129       assert(nh->magic==NAME_MAGIC);
 130       if(refp==nh->refp){ nt->avg_refl=(nt->avg_refl+i)/2; nhref=nh; break; }
 131     }
 132
 133   for(nh=nt->cstr[idn];nh!=NULL;nh=nh->cstr,i++)
 134     {
 135       assert(nh->magic==NAME_MAGIC);
 136       if(strcmp(name,nh->str)==0){ nt->avg_strl=(nt->avg_strl+i)/2; nhstr=nh; break; }
 137     }
 138
 139   if(nhstr==NULL) /* adding new name entry */
 140     {
 141       if(nhref!=NULL) /* but refp was the same */
 142         {
 143           fprintf(stderr,"**** DUPLICATE KEY NAME ****\n");
 144           if(1)assert(0&&"duplicate key in names");
 145         }
 146
 147       nh=names_newhash(nt, refp, name);
 148       nh->cstr=nt->cstr[idn];
 149       nt->cstr[idn]=nh;
 150       nh->cref=nt->cref[idr];
 151       nt->cref[idr]=nh;
 152     }
 153   else  /* replacing old name entry */
 154     {
 155       namehash_t *prev=NULL;
 156       assert(0 && "Replacing strings in names has a bug. do not use");
 157       /* lookup refp of old name and unlink */
 158       id=names_ptrhash(nt,nhstr->refp);
 159       for(nh=nt->cref[id];nh!=NULL;prev=nh,nh=nh->cref,i++)
 160         if(nhstr->refp==nh->refp)
 161           {
 162             if(prev==NULL)nt->cref[id]=nh->cref;
 163             else prev->cref=nh->cref;
 164             break;
 165           }
 166       /* relink new name, refp */
 167       nhstr->refp=refp;
 168       nhstr->cref=nt->cref[idr];
 169       nt->cref[idr]=nhstr;
 170     }
 171 }
 172
 173 char * names_stats(names_t *nt)
 174 {
 175   static char buf[1024];
 176   int i,qs=0,qp=0,ms=0,mp=0,j,ks=0,kp=0;
 177   namehash_t *nh;
 178
 179   for(i=0;i<nt->qtybins;i++)
 180     {
 181
 182       for(j=0,nh=nt->cstr[i];nh!=NULL;nh=nh->cstr,j++)        assert(nh->magic==NAME_MAGIC);
 183       if(j>0)ks++;
 184       if(ms<j)ms=j;
 185       qs+=j;
 186       for(j=0,nh=nt->cref[i];nh!=NULL;nh=nh->cref,j++)        assert(nh->magic==NAME_MAGIC);
 187       if(mp<j)mp=j;
 188       if(j>0)kp++;
 189       qp+=j;
 190     }
 191
 192   qp/=kp;
 193   qs/=ks;
 194
 195   sprintf(buf,"names: %i bins (%i totaling %i) , alloc %i, avg: %i %i max: %i %i",nt->qtybins,nt->qtynames,nt->namebytes,nt->bytesalloc,qp,qs,mp,ms);
 196
 197   return buf;
 198 }
 199
 200
 201
 202 /* this should optimize our hash table for memory usage */
 203 void names_rehash(names_t *nt, int newbins)
 204 {
 205   int i;
 206   int oldqty;
 207   namehash_t *hp;
 208
 209   oldqty=nt->qtybins;
 210   nt->qtybins=newbins;
 211
 212   nt->bytesalloc+= ( (newbins-oldqty)*sizeof(void *)*2 );
 213   /* do cref first, using cstr */
 214   if(nt->cref!=NULL)
 215     free(nt->cref);
 216   nt->cref=malloc(sizeof(void *)*(nt->qtybins+1));
 217   assert(nt->cref!=NULL);
 218   memset(nt->cref,0,sizeof(void*)*nt->qtybins);
 219
 220   /* iterate through list of string hashes, adding to ref hashes */
 221   for(i=0;i<oldqty;i++)
 222     for(hp=nt->cstr[i];hp!=NULL;hp=hp->cstr)
 223       {
 224         unsigned id;
 225         id=names_ptrhash(nt,hp->refp);
 226         hp->cref=nt->cref[id];
 227         nt->cref[id]=hp;
 228       }
 229
 230   /* next do cstr, using new cref */
 231   if(nt->cstr!=NULL)
 232     free(nt->cstr);
 233   nt->cstr=malloc(sizeof(void *)*(nt->qtybins+1));
 234   assert(nt->cstr!=NULL);
 235   memset(nt->cstr,0,sizeof(void*)*nt->qtybins);
 236
 237   for(i=0;i<nt->qtybins;i++)
 238     for(hp=nt->cref[i];hp!=NULL;hp=hp->cref)
 239       {
 240         unsigned id;
 241         id=names_strhash(nt,hp->str);
 242         hp->cstr=nt->cstr[id];
 243         nt->cstr[id]=hp;
 244       }
 245 }
 246
 247
 248
 249 names_t   *names_new(void)
 250 {
 251   names_t *p;
 252   p=malloc(sizeof(names_t));
 253   assert(p!=NULL);
 254   memset(p,0,sizeof(names_t));
 255   p->bytesalloc=sizeof(names_t);
 256   p->namebytes=0;
 257   p->qtynames=0;
 258   p->avg_strl=0;
 259   p->avg_refl=0;
 260
 261   p->qtybins=0;
 262   p->cstr=NULL;
 263   p->cref=NULL;
 264   names_rehash(p,13); /* start small, grow bigger */
 265   return p;
 266 }
 267
 268 void names_free(names_t *nt)
 269 {
 270   int i;
 271   namehash_t *nh,*next;
 272   if(nt!=NULL)
 273     {
 274       for(i=0;i<nt->qtybins;i++)
 275         {
 276           for(nh=nt->cstr[i];nh!=NULL;nh=next)
 277             {
 278               assert(nh->magic==NAME_MAGIC);
 279               next=nh->cstr;
 280               free(nh);
 281             }
 282         }
 283       free(nt->cstr);
 284       free(nt->cref);
 285       free(nt);
 286     }
 287 }