chiark - git - mdw - ssr/blob - StraySrc/SDLS/cdll/c/hashtable

   1 /*
   2  * hashtable.c
   3  *
   4  * Hash table handling for strings
   5  *
   6  * © 1994-1998 Straylight
   7  */
   8
   9 /*----- Licensing note ----------------------------------------------------*
  10  *
  11  * This file is part of Straylight's Dynamic Linking System (SDLS)
  12  *
  13  * SDLS is free software; you can redistribute it and/or modify
  14  * it under the terms of the GNU General Public License as published by
  15  * the Free Software Foundation; either version 2, or (at your option)
  16  * any later version.
  17  *
  18  * SDLS is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU General Public License for more details.
  22  *
  23  * You should have received a copy of the GNU General Public License
  24  * along with SDLS.  If not, write to the Free Software Foundation,
  25  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  26  */
  27
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30 #include <string.h>
  31
  32 #include "hashtable.h"
  33 #include "crc32.h"
  34
  35 /*----- Constants ---------------------------------------------------------*/
  36
  37 #define hash__SIZE 512                  /* A respectable size table     */
  38                                         /* Note: must be power of 2     */
  39
  40 /*----- Some good ol' data structures -------------------------------------*/
  41
  42 typedef struct hash__link
  43 {
  44   struct hash__link *next;              /* Link in hash table bucket    */
  45   struct hash__link *left;              /* Link in ordinal tree         */
  46   struct hash__link *right;             /* Link in ordinal tree         */
  47   unsigned int ord;                     /* Ordinal value                */
  48   char string[1];                       /* String (unsized array)       */
  49 }
  50 hash__link;
  51
  52 typedef struct hash__table
  53 {
  54   hash__link *tbl[hash__SIZE];          /* The actual hash table        */
  55   hash__link *root;                     /* The ordinal tree root        */
  56 }
  57 hash__table;
  58
  59 /*----- Private code ------------------------------------------------------*/
  60
  61 #define hash__hash(s) (crc32(0,s,strlen(s),1) & (hash__SIZE - 1))
  62
  63 static int hash__addToTree(hash__link **root,hash__link *l)
  64 {
  65   if (*root)
  66   {
  67     if ((*root)->ord > l->ord)
  68       return (hash__addToTree(&(*root)->left,l));
  69     else if ((*root)->ord < l->ord || l->ord == 0xFFFFFFFF)
  70       return (hash__addToTree(&(*root)->right,l));
  71     else
  72       return (1);
  73   }
  74   else
  75   {
  76     *root=l;
  77     return (0);
  78   }
  79 }
  80
  81 static void hash__traverse(hash__link *l,
  82                            void (*func)(char *string,
  83                                         unsigned int ord,
  84                                         void *handle),
  85                            void *handle)
  86 {
  87   if (l)
  88   {
  89     hash__traverse(l->left,func,handle);
  90     func(l->string,l->ord,handle);
  91     hash__traverse(l->right,func,handle);
  92   }
  93 }
  94
  95 static void hash__dump(char *string,unsigned int ord,void *handle)
  96 {
  97   handle=handle;
  98   printf(" ** %s (%08x)\n",string,ord);
  99 }
 100
 101 /*----- Public code -------------------------------------------------------*/
 102
 103 hashtable hash_create(void)
 104 {
 105   return (calloc(1,sizeof(hash__table)));
 106 }
 107
 108 int hash_find(hashtable h,char *string)
 109 {
 110   int sh=hash__hash(string);
 111   hash__link *l;
 112   for (l=h->tbl[sh];l;l=l->next)
 113   {
 114     if (!strcmp(l->string,string))
 115       return (1);
 116   }
 117   return (0);
 118 }
 119
 120 int hash_add(hashtable h,char *string)
 121 {
 122   return (hash_addWithOrd(h,string,0xFFFFFFFF));
 123 }
 124
 125 int hash_addWithOrd(hashtable h,char *string,unsigned int ord)
 126 {
 127   int sh=hash__hash(string);
 128   hash__link *l;
 129   if (hash_find(h,string))
 130     return (1);
 131   if (l=malloc(sizeof(hash__link)+strlen(string)),!l)
 132     return (0);
 133   strcpy(l->string,string);
 134   l->ord=ord;
 135   l->next=h->tbl[sh];
 136   h->tbl[sh]=l;
 137   l->left=l->right=0;
 138   if (hash__addToTree(&h->root,l))
 139   {
 140     l->ord=0xFFFFFFFF;
 141     hash__addToTree(&h->root,l);
 142   }
 143   return (1);
 144 }
 145
 146 void hash_delete(hashtable h)
 147 {
 148   hash__link *l;
 149   hash__link *n;
 150   int i;
 151   for (i=0;i<hash__SIZE;i++)
 152   {
 153     for (l=h->tbl[i];l;l=n)
 154     {
 155       n=l->next;
 156       free(l);
 157     }
 158   }
 159   free(h);
 160 }
 161
 162 int hash_subset(hashtable super,
 163                 hashtable sub,
 164                 void (*proc)(char *p))
 165 {
 166   hash__link *l;
 167   int i;
 168   int s=1;
 169   for (i=0;i<hash__SIZE;i++)
 170   {
 171     for (l=sub->tbl[i];l;l=l->next)
 172     {
 173       if (!hash_find(super,l->string))
 174       {
 175         s=0;
 176         proc(l->string);
 177       }
 178     }
 179   }
 180   return (s);
 181 }
 182
 183 void hash_dump(hashtable h)
 184 {
 185   hash_enumOrdered(h,hash__dump,0);
 186 }
 187 void hash_enumerate(hashtable h,
 188                     void (*func)(char *string,void *handle),
 189                     void *handle)
 190 {
 191   hash__link *l;
 192   int i;
 193   for (i=0;i<hash__SIZE;i++)
 194   {
 195     for (l=h->tbl[i];l;l=l->next)
 196       func(l->string,handle);
 197   }
 198 }
 199
 200 void hash_enumOrdered(hashtable h,
 201                       void (*func)(char *string,
 202                                    unsigned int ord,
 203                                    void *handle),
 204                       void *handle)
 205 {
 206   hash__traverse(h->root,func,handle);
 207 }
 208
 209 int hash_count(hashtable h)
 210 {
 211   int count=0;
 212   hash__link *l;
 213   int i;
 214   for (i=0;i<hash__SIZE;i++)
 215   {
 216     for (l=h->tbl[i];l;l=l->next)
 217       count++;
 218   }
 219   return (count);
 220 }