util/mkisofs/hash.c

   1 /*
   2  * File hash.c - generate hash tables for iso9660 filesystem.
   3
   4    Written by Eric Youngdale (1993).
   5
   6    Copyright 1993 Yggdrasil Computing, Incorporated
   7
   8    This program is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2, or (at your option)
  11    any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  21
  22 #include <stdlib.h>
  23 #include "config.h"
  24 #include "mkisofs.h"
  25
  26 #define NR_HASH 1024
  27
  28 #define HASH_FN(DEV, INO) ((DEV + INO + (INO >> 2) + (INO << 8)) % NR_HASH)
  29
  30 static struct file_hash * hash_table[NR_HASH] = {0,};
  31
  32 void FDECL1(add_hash, struct directory_entry *, spnt){
  33   struct file_hash * s_hash;
  34   unsigned int hash_number;
  35
  36   if(spnt->size == 0 || spnt->starting_block == 0)
  37     if(spnt->size != 0 || spnt->starting_block != 0) {
  38       fprintf(stderr,"Non zero-length file assigned zero extent.\n");
  39       exit(1);
  40     };
  41
  42   if (spnt->dev == (dev_t) UNCACHED_DEVICE || spnt->inode == UNCACHED_INODE) return;
  43   hash_number = HASH_FN((unsigned int) spnt->dev, (unsigned int) spnt->inode);
  44
  45 #if 0
  46   if (verbose > 1) fprintf(stderr,"%s ",spnt->name);
  47 #endif
  48   s_hash = (struct file_hash *) e_malloc(sizeof(struct file_hash));
  49   s_hash->next = hash_table[hash_number];
  50   s_hash->inode = spnt->inode;
  51   s_hash->dev = spnt->dev;
  52   s_hash->starting_block = spnt->starting_block;
  53   s_hash->size = spnt->size;
  54   hash_table[hash_number] = s_hash;
  55 }
  56
  57 struct file_hash * FDECL2(find_hash, dev_t, dev, ino_t, inode){
  58   unsigned int hash_number;
  59   struct file_hash * spnt;
  60   hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
  61   if (dev == (dev_t) UNCACHED_DEVICE || inode == UNCACHED_INODE) return NULL;
  62
  63   spnt = hash_table[hash_number];
  64   while(spnt){
  65     if(spnt->inode == inode && spnt->dev == dev) return spnt;
  66     spnt = spnt->next;
  67   };
  68   return NULL;
  69 }
  70
  71
  72 static struct file_hash * directory_hash_table[NR_HASH] = {0,};
  73
  74 void FDECL2(add_directory_hash, dev_t, dev, ino_t, inode){
  75   struct file_hash * s_hash;
  76   unsigned int hash_number;
  77
  78   if (dev == (dev_t) UNCACHED_DEVICE || inode == UNCACHED_INODE) return;
  79   hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
  80
  81   s_hash = (struct file_hash *) e_malloc(sizeof(struct file_hash));
  82   s_hash->next = directory_hash_table[hash_number];
  83   s_hash->inode = inode;
  84   s_hash->dev = dev;
  85   directory_hash_table[hash_number] = s_hash;
  86 }
  87
  88 struct file_hash * FDECL2(find_directory_hash, dev_t, dev, ino_t, inode){
  89   unsigned int hash_number;
  90   struct file_hash * spnt;
  91   hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
  92   if (dev == (dev_t) UNCACHED_DEVICE || inode == UNCACHED_INODE) return NULL;
  93
  94   spnt = directory_hash_table[hash_number];
  95   while(spnt){
  96     if(spnt->inode == inode && spnt->dev == dev) return spnt;
  97     spnt = spnt->next;
  98   };
  99   return NULL;
 100 }
 101
 102 struct  name_hash
 103 {
 104   struct name_hash * next;
 105   struct directory_entry * de;
 106 };
 107
 108 #define NR_NAME_HASH 128
 109
 110 static struct name_hash * name_hash_table[NR_NAME_HASH] = {0,};
 111
 112 /*
 113  * Find the hash bucket for this name.
 114  */
 115 static  unsigned int FDECL1(name_hash, const char *, name)
 116 {
 117   unsigned int hash = 0;
 118   const char * p;
 119
 120   p = name;
 121
 122   while (*p)
 123     {
 124       /*
 125        * Don't hash the  iso9660 version number.  This way
 126        * we can detect duplicates in cases where we have
 127        * directories (i.e. foo) and non-directories
 128        * (i.e. foo;1).
 129        */
 130       if( *p == ';' )
 131         {
 132           break;
 133         }
 134       hash = (hash << 15) + (hash << 3) + (hash >> 3) + *p++;
 135     }
 136   return hash % NR_NAME_HASH;
 137 }
 138
 139 void FDECL1(add_file_hash, struct directory_entry *, de){
 140         struct name_hash  * new;
 141         int hash;
 142
 143         new = (struct  name_hash *) e_malloc(sizeof(struct name_hash));
 144         new->de = de;
 145         new->next = NULL;
 146         hash = name_hash(de->isorec.name);
 147
 148         /* Now insert into the hash table */
 149         new->next = name_hash_table[hash];
 150         name_hash_table[hash] = new;
 151 }
 152
 153 struct directory_entry * FDECL1(find_file_hash, char *, name)
 154 {
 155   struct name_hash  * nh;
 156   char              * p1;
 157   char              * p2;
 158
 159   for(nh = name_hash_table[name_hash(name)]; nh; nh = nh->next)
 160     {
 161       p1 = name;
 162       p2 = nh->de->isorec.name;
 163
 164       /*
 165        * Look for end of string, or a mismatch.
 166        */
 167       while(1==1)
 168         {
 169           if(    (*p1 == '\0' || *p1 == ';')
 170               || (*p2 == '\0' || *p2 == ';')
 171               || (*p1 != *p2) )
 172             {
 173               break;
 174             }
 175           p1++;
 176           p2++;
 177         }
 178
 179       /*
 180        * If we are at the end of both strings, then
 181        * we have a match.
 182        */
 183       if(    (*p1 == '\0' || *p1 == ';')
 184           && (*p2 == '\0' || *p2 == ';') )
 185         {
 186           return nh->de;
 187         }
 188     }
 189   return NULL;
 190 }
 191
 192 int FDECL1(delete_file_hash, struct directory_entry *, de){
 193         struct name_hash  * nh, *prev;
 194         int hash;
 195
 196         prev = NULL;
 197         hash = name_hash(de->isorec.name);
 198         for(nh = name_hash_table[hash]; nh; nh = nh->next) {
 199                 if(nh->de == de) break;
 200                 prev = nh;
 201         }
 202         if(!nh) return 1;
 203         if(!prev)
 204                 name_hash_table[hash] = nh->next;
 205         else
 206                 prev->next = nh->next;
 207         free(nh);
 208         return 0;
 209 }
 210
 211 void flush_file_hash(){
 212         struct name_hash  * nh, *nh1;
 213         int i;
 214
 215         for(i=0; i<NR_NAME_HASH; i++) {
 216                 nh = name_hash_table[i];
 217                 while(nh) {
 218                         nh1 =  nh->next;
 219                         free(nh);
 220                         nh = nh1;
 221                 }
 222                 name_hash_table[i] =  NULL;
 223
 224         }
 225 }