spiceparser/hash.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 /* hash.c :  Hash table functions for string identifier lookup
  22    Conrad Ziesler
  23 */
  24
  25
  26 #include "debug.h"
  27 #include "hash.h"
  28
  29
  30
  31 unsigned int hash_strhash(int max, void *data, int size)
  32 {
  33   int i;
  34   unsigned int r=0;
  35   char *str=data;
  36
  37   for(i=0;i<size;i++)
  38     {
  39       if(str[0]==0)break;
  40       r+=((unsigned int)(str[0]&0x7f));
  41       r%=max;
  42       str++;
  43     }
  44
  45   assert(r<max);
  46   assert(r>=0);
  47   return r;
  48 }
  49
  50
  51 #define quickhashbin(a,b,c) hash_binhash(a,b,c)
  52
  53 unsigned int hash_binhash(int max, void *data, int size)
  54 {
  55   unsigned int r=0;
  56   int i;
  57   uchar *str=data;
  58
  59   for(i=0;i<size;i++)
  60     {
  61       r+=((unsigned int)(str[0]&0x7f));
  62       r%=max;
  63       str++;
  64     }
  65
  66   assert(r<max);
  67   assert(r>=0);
  68   return r;
  69 }
  70
  71 static hashbin_t *hash_newbin(void *copyfrom, int size)
  72 {
  73   hashbin_t *p;
  74
  75   p=malloc(size+sizeof(hashbin_t));
  76   assert(p!=NULL);
  77
  78   p->size=size;
  79   p->next=NULL;
  80   memcpy(hash_bin2user(p),copyfrom,size);
  81   return p;
  82 }
  83
  84
  85 static hashbin_t *hash_insert(hash_t *h, unsigned int index, hashbin_t *cp)
  86 {
  87   cp->next=h->bins[index];
  88   h->bins[index]=cp;
  89   return cp;
  90 }
  91
  92 #ifdef UNUSED
  93 static hashbin_t *hash_insertsorted(hash_t *h, hashbin_t *head, hashbin_t *cp)
  94 {
  95   hashbin_t *a,*b=NULL;
  96
  97   for(a=head;a!=NULL;a=a->next)
  98     {
  99       if(h->hashcmp(a,cp)>=0)
 100         {
 101           if(b==NULL)
 102             {
 103               cp->next=head;
 104               return cp;
 105             }
 106           else
 107             {
 108               cp->next=a;
 109               b->next=cp;
 110               return head;
 111             }
 112         }
 113       b=a;
 114     }
 115   if(b==NULL)
 116     {
 117       cp->next=NULL;
 118       return cp;
 119     }
 120   else
 121     {
 122       cp->next=NULL;
 123       b->next=cp;
 124       return head;
 125     }
 126 }
 127 #endif
 128
 129 static hashbin_t *hash_findbin(hash_t *h, hashbin_t *start, int ksize, void *key)
 130 {
 131   while(start!=NULL)
 132     {
 133       if(h->hashcmp(ksize,key,start->size,start+1)==0)return start;
 134       start=start->next;
 135     }
 136   return NULL;
 137 }
 138
 139
 140
 141 /******* public functions ********/
 142 void hash_free (hash_t *h)
 143 {
 144   int i;
 145   hashbin_t *p,*np;
 146
 147   if(h!=NULL)
 148     {
 149       for(i=0;i<h->qalloc;i++)
 150         if(h->alloc[i]!=NULL)free(h->alloc[i]);
 151       for(i=0;i<h->qbin;i++)
 152         {
 153           for(p=h->bins[i];p!=NULL;p=np)
 154             {
 155               np=p->next;
 156               free(p);
 157             }
 158         }
 159       free(h);
 160     }
 161 }
 162
 163
 164 hash_t *hash_new    (
 165                      int qbins,
 166                      uint (*hashfunc)(int max, void *data, int size),
 167                      int (*hashcmp)(int sizea, void *a, int sizeb, void *b)
 168                      )
 169 {
 170   hash_t *p;
 171   int i;
 172   if(qbins<=0)qbins=4;
 173   p=malloc(sizeof(hash_t)+(sizeof(hashbin_t *)*qbins) );
 174   assert(p!=NULL);
 175   p->bins=(void *) (((char *)p)+sizeof(hash_t));
 176   p->uniq=0;
 177   p->qbin=qbins;
 178   p->hashfunc=hashfunc;
 179   p->hashcmp=hashcmp;
 180   for(i=0;i<qbins;i++)
 181     p->bins[i]=NULL;
 182   p->qalloc=0;
 183   p->alloc=NULL;
 184   return p;
 185 }
 186
 187
 188 void *hash_find(hash_t *h, void *key, int ksize)
 189 {
 190   unsigned int ukey;
 191   hashbin_t *fbin;
 192
 193   assert(h!=NULL);
 194   ukey=h->hashfunc(h->qbin,key,ksize);
 195   assert(ukey<h->qbin);
 196
 197   fbin=hash_findbin(h,h->bins[ukey],ksize,key);
 198
 199   if(fbin==NULL)return NULL;
 200   return hash_bin2user(fbin);
 201 }
 202
 203 int hash_size(void *user)
 204 {
 205   hashbin_t *bin;
 206   if(user==NULL)return 0;
 207   bin=hash_user2bin(user);
 208   return bin->size;
 209 }
 210
 211 void *hash_add(hash_t *h, void *key, int ksize)
 212 {
 213   unsigned int ukey;
 214   hashbin_t *fbin, *dbin;
 215
 216
 217   assert(h!=NULL);
 218   ukey=h->hashfunc(h->qbin,key,ksize);
 219   assert(ukey<h->qbin);
 220
 221   fbin=hash_findbin(h,h->bins[ukey],ksize,key);
 222   if(fbin==NULL)
 223     {
 224       dbin=hash_newbin(key,ksize);
 225       fbin=hash_insert(h,ukey,dbin);
 226     }
 227   if(fbin!=NULL)
 228     return hash_bin2user(fbin);
 229   else return NULL;
 230 }
 231
 232
 233 uint hclient_ptrflagstr_hash(int max, void *data, int size)
 234 {
 235   return hash_strhash(max, ((char *)data) + sizeof(hclient_ptrflagstr_t) ,size-sizeof(hclient_ptrflagstr_t));
 236 }
 237
 238 int  hclient_ptrflagstr_cmp(hashbin_t *a, hashbin_t *b)
 239 {
 240   if(a==NULL)return 1;
 241   if(b==NULL)return -1;
 242   if(a->size > b->size) return 1;
 243   if(a->size < b->size) return -1;
 244   return strcmp( ((char *) hash_bin2user(a) ) + sizeof(hclient_ptrflagstr_t), ((char *) hash_bin2user(b) ) + sizeof(hclient_ptrflagstr_t) );
 245
 246 }
 247
 248
 249 /* binary object
 250    straight binary comparison and hash
 251 */
 252
 253 uint hclient_bobject_hash(int max, void *data, int size)
 254 {
 255   return quickhashbin(max,data,size);
 256 }
 257
 258 int  hclient_bobject_cmp(int sizea, void *a, int sizeb, void *b)
 259 {
 260   if(a==NULL)return 1;
 261   if(b==NULL)return -1;
 262   if(sizea > sizeb) return 1;
 263   if(sizea < sizeb) return -1;
 264   return memcmp(a,b,sizea);
 265 }
 266
 267