genisoimage/hash.c

   1 /*
   2  * This file has been modified for the cdrkit suite.
   3  *
   4  * The behaviour and appearence of the program code below can differ to a major
   5  * extent from the version distributed by the original author(s).
   6  *
   7  * For details, see Changelog file distributed with the cdrkit package. If you
   8  * received this file from another source then ask the distributing person for
   9  * a log of modifications.
  10  *
  11  */
  12
  13 /* @(#)hash.c   1.18 04/06/18 joerg */
  14 /* @(#)hash.c   1.23 06/10/04 joerg */
  15 /*
  16  * File hash.c - generate hash tables for iso9660 filesystem.
  17  *
  18  * Written by Eric Youngdale (1993).
  19  *
  20  * Copyright 1993 Yggdrasil Computing, Incorporated
  21  * Copyright (c) 1999,2000-2006 J. Schilling
  22  *
  23  * This program is free software; you can redistribute it and/or modify
  24  * it under the terms of the GNU General Public License as published by
  25  * the Free Software Foundation; either version 2, or (at your option)
  26  * any later version.
  27  *
  28  * This program is distributed in the hope that it will be useful,
  29  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  30  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  31  * GNU General Public License for more details.
  32  *
  33  * You should have received a copy of the GNU General Public License
  34  * along with this program; if not, write to the Free Software
  35  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  36  */
  37
  38 /* APPLE_HYB James Pearson j.pearson@ge.ucl.ac.uk 23/2/2000 */
  39
  40 /*
  41  * From jb@danware.dk:
  42  *
  43  * Cygwin fakes inodes by hashing file info, actual collisions observed!
  44  * This is documented in the cygwin source, look at winsup/cygwin/path.cc
  45  * and search for the word 'Hash'.  On NT, cygwin ORs together the
  46  * high and low 32 bits of the 64 bit genuine inode, look at fhandler.cc.
  47  *
  48  * Note:        Other operating systems which support the FAT filesystem may
  49  *              have the same problem because FAT does not use the inode
  50  *              concept.  For NTFS, genuine inode numbers exist, but they are
  51  *              64 bits and available only through an open file handle.
  52  *
  53  * The solution is the new options -no-cache-inodes/-cache-inodes that
  54  * allow to disable the genisoimage inode cache.
  55  */
  56
  57 #include <mconfig.h>
  58 #include "genisoimage.h"
  59 #include <schily.h>
  60
  61 #define NR_HASH (16*1024)
  62
  63 #define HASH_FN(DEV, INO)       ((DEV + INO  + (INO >> 8) + (INO << 16)) % NR_HASH)
  64
  65 static struct file_hash *hash_table[NR_HASH];
  66
  67 void            add_hash(struct directory_entry *spnt);
  68 struct file_hash *find_hash(dev_t dev, ino_t inode);
  69 void            flush_hash(void);
  70 void            add_directory_hash(dev_t dev, ino_t inode);
  71 struct file_hash *find_directory_hash(dev_t dev, ino_t inode);
  72 static  unsigned int    name_hash(const char *name);
  73 void            add_file_hash(struct directory_entry *de);
  74 struct directory_entry *find_file_hash(char *name);
  75 static  BOOL            isoname_endsok(char *name);
  76 int             delete_file_hash(struct directory_entry *de);
  77 void            flush_file_hash(void);
  78
  79 void
  80 add_hash(struct directory_entry *spnt)
  81 {
  82         struct file_hash *s_hash;
  83         unsigned int    hash_number;
  84
  85         if (spnt->size == 0 || spnt->starting_block == 0)
  86                 if (spnt->size != 0 && spnt->starting_block == 0) {
  87                         comerrno(EX_BAD,
  88                         "Non zero-length file '%s' assigned zero extent.\n",
  89                                                         spnt->name);
  90                 };
  91
  92         if (!cache_inodes)
  93                 return;
  94         if (spnt->dev == UNCACHED_DEVICE &&
  95             (spnt->inode == TABLE_INODE || spnt->inode == UNCACHED_INODE)) {
  96                 return;
  97         }
  98         hash_number = HASH_FN((unsigned int) spnt->dev,
  99                                                 (unsigned int) spnt->inode);
 100
 101 #if 0
 102         if (verbose > 1)
 103                 fprintf(stderr, "%s ", spnt->name);
 104 #endif
 105         s_hash = (struct file_hash *) e_malloc(sizeof (struct file_hash));
 106         s_hash->next = hash_table[hash_number];
 107         s_hash->inode = spnt->inode;
 108         s_hash->dev = spnt->dev;
 109         s_hash->nlink = 0;
 110         s_hash->starting_block = spnt->starting_block;
 111         s_hash->size = spnt->size;
 112 #ifdef SORTING
 113         s_hash->de = spnt;
 114 #endif /* SORTING */
 115         hash_table[hash_number] = s_hash;
 116 }
 117
 118 struct file_hash *
 119 find_hash(dev_t dev, ino_t inode)
 120 {
 121         unsigned int    hash_number;
 122         struct file_hash *spnt;
 123
 124         if (!cache_inodes)
 125                 return (NULL);
 126         if (dev == UNCACHED_DEVICE &&
 127             (inode == TABLE_INODE || inode == UNCACHED_INODE))
 128                 return (NULL);
 129
 130         hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
 131         spnt = hash_table[hash_number];
 132         while (spnt) {
 133                 if (spnt->inode == inode && spnt->dev == dev)
 134                         return (spnt);
 135                 spnt = spnt->next;
 136         };
 137         return (NULL);
 138 }
 139
 140 /*
 141  * based on flush_file_hash() below - needed as we want to re-use the
 142  * file hash table.
 143  */
 144 void
 145 flush_hash()
 146 {
 147         struct file_hash        *fh;
 148         struct file_hash        *fh1;
 149         int                     i;
 150
 151         for (i = 0; i < NR_HASH; i++) {
 152                 fh = hash_table[i];
 153                 while (fh) {
 154                         fh1 = fh->next;
 155                         free(fh);
 156                         fh = fh1;
 157                 }
 158                 hash_table[i] = NULL;
 159         }
 160 }
 161
 162 static struct file_hash *directory_hash_table[NR_HASH];
 163
 164 void
 165 add_directory_hash(dev_t dev, ino_t inode)
 166 {
 167         struct file_hash *s_hash;
 168         unsigned int    hash_number;
 169
 170         if (!cache_inodes)
 171                 return;
 172         if (dev == UNCACHED_DEVICE &&
 173             (inode == TABLE_INODE || inode == UNCACHED_INODE))
 174                 return;
 175
 176         hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
 177
 178         s_hash = (struct file_hash *) e_malloc(sizeof (struct file_hash));
 179         s_hash->next = directory_hash_table[hash_number];
 180         s_hash->inode = inode;
 181         s_hash->dev = dev;
 182         s_hash->nlink = 0;
 183         directory_hash_table[hash_number] = s_hash;
 184 }
 185
 186 struct file_hash *
 187 find_directory_hash(dev_t dev, ino_t inode)
 188 {
 189         unsigned int    hash_number;
 190         struct file_hash *spnt;
 191
 192         if (!cache_inodes)
 193                 return (NULL);
 194         if (dev == UNCACHED_DEVICE &&
 195             (inode == TABLE_INODE || inode == UNCACHED_INODE))
 196                 return (NULL);
 197
 198         hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
 199         spnt = directory_hash_table[hash_number];
 200         while (spnt) {
 201                 if (spnt->inode == inode && spnt->dev == dev)
 202                         return (spnt);
 203                 spnt = spnt->next;
 204         };
 205         return (NULL);
 206 }
 207
 208 struct name_hash {
 209         struct name_hash *next;
 210         struct directory_entry *de;
 211         int     sum;
 212 };
 213
 214 #define NR_NAME_HASH    (256*1024)
 215
 216 static struct name_hash *name_hash_table[NR_NAME_HASH] = {0, };
 217
 218 /*
 219  * Find the hash bucket for this name.
 220  */
 221 static unsigned int
 222 name_hash(const char *name)
 223 {
 224         unsigned int    hash = 0;
 225         const char      *p;
 226
 227         p = name;
 228
 229         while (*p) {
 230                 /*
 231                  * Don't hash the  iso9660 version number.
 232                  * This way we can detect duplicates in cases where we have
 233                  * directories (i.e. foo) and non-directories (i.e. foo;1).
 234                  */
 235                 if (*p == ';') {
 236                         break;
 237                 }
 238                 hash = (hash << 15) + (hash << 3) + (hash >> 3) + (*p++ & 0xFF);
 239         }
 240         return (hash % NR_NAME_HASH);
 241 }
 242
 243 void
 244 add_file_hash(struct directory_entry *de)
 245 {
 246         struct name_hash        *new;
 247         int                     hash;
 248         Uchar                   *p;
 249         int                     sum = 0;
 250
 251         new = (struct name_hash *) e_malloc(sizeof (struct name_hash));
 252         new->de = de;
 253         new->next = NULL;
 254         for (p = (Uchar *)de->isorec.name; *p; p++) {
 255                 if (*p == ';')
 256                         break;
 257                 sum += *p & 0xFF;
 258         }
 259         new->sum = sum;
 260         hash = name_hash(de->isorec.name);
 261
 262         /* Now insert into the hash table */
 263         new->next = name_hash_table[hash];
 264         name_hash_table[hash] = new;
 265 }
 266
 267 struct directory_entry *
 268 find_file_hash(register char *name)
 269 {
 270         register char                   *p1;
 271         register char                   *p2;
 272         register struct name_hash       *nh;
 273         register int                    sum = 0;
 274
 275         if (debug > 1)
 276                 fprintf(stderr, "find_hash('%s')\n", name);
 277
 278         for (p1 = name; *p1; p1++) {
 279                 if (*p1 == ';')
 280                         break;
 281                 sum += *p1 & 0xFF;
 282         }
 283
 284         for (nh = name_hash_table[name_hash(name)]; nh; nh = nh->next) {
 285                 if (nh->sum != sum)
 286                         continue;
 287
 288                 p1 = name;
 289                 p2 = nh->de->isorec.name;
 290                 if (debug > 1)
 291                         fprintf(stderr, "Checking name '%s' isorec.name '%s'\n", p1, p2);
 292
 293                 /* Look for end of string, or a mismatch. */
 294                 while (1 == 1) {
 295                         if ((*p1 == '\0' || *p1 == ';') ||
 296                             (*p2 == '\0' || *p2 == ';') ||
 297                             (*p1 != *p2)) {
 298                                 break;
 299                         }
 300                         p1++;
 301                         p2++;
 302                 }
 303                 if (!isoname_endsok(p1) || !isoname_endsok(p2)) {
 304                         if (debug > 1) {
 305                                 if (!isoname_endsok(p1))
 306                                         fprintf(stderr, "'%s' does NOT END OK\n", p1);
 307                                 if (!isoname_endsok(p2))
 308                                         fprintf(stderr, "'%s' does NOT END OK\n", p2);
 309                         }
 310                         /*
 311                          * If one file does not end with a valid version number
 312                          * and the other name ends here, we found a miss match.
 313                          */
 314                         if (*p1 == '\0' || *p2 == '\0')
 315                                 continue;
 316
 317                         if (*p1 == ';' && *p2 == ';') {
 318                                 p1++;
 319                                 p2++;
 320                                 continue;
 321                         }
 322                 }
 323
 324                 /*
 325                  * If we are at the end of both strings, then we have a match.
 326                  */
 327                 if ((*p1 == '\0' || *p1 == ';') &&
 328                     (*p2 == '\0' || *p2 == ';')) {
 329                         return (nh->de);
 330                 }
 331         }
 332         return (NULL);
 333 }
 334
 335 /*
 336  * The macro 'eo' is just an idea on how one might speed up isoname_endsok()
 337  */
 338 #define eo(p)   (((p)[0] == '\0') || \
 339                 ((p)[0] == ';' && (p)[1] == '1' && (p)[2] == '\0') || \
 340                 isoname_endsok(p))
 341
 342 static BOOL
 343 isoname_endsok(char *name)
 344 {
 345         int     i;
 346         char    *p;
 347
 348         if (*name == '\0')
 349                 return (TRUE);
 350         if (*name != ';')
 351                 return (FALSE);
 352
 353         for (p = ++name, i = 0; *p && i < 5; p++, i++) {
 354                 if (*p < '0' || *p > '9')
 355                         return (FALSE);
 356         }
 357         i = atoi(name);
 358         if (i < 1 || i > 32767)
 359                 return (FALSE);
 360         return (TRUE);
 361 }
 362
 363 int
 364 delete_file_hash(struct directory_entry *de)
 365 {
 366         struct name_hash        *nh;
 367         struct name_hash        *prev;
 368         int                     hash;
 369
 370         prev = NULL;
 371         hash = name_hash(de->isorec.name);
 372         for (nh = name_hash_table[hash]; nh; nh = nh->next) {
 373                 if (nh->de == de)
 374                         break;
 375                 prev = nh;
 376         }
 377         if (!nh)
 378                 return (1);
 379         if (!prev)
 380                 name_hash_table[hash] = nh->next;
 381         else
 382                 prev->next = nh->next;
 383         free(nh);
 384         return (0);
 385 }
 386
 387 void
 388 flush_file_hash()
 389 {
 390         struct name_hash        *nh;
 391         struct name_hash        *nh1;
 392         int                     i;
 393
 394         for (i = 0; i < NR_NAME_HASH; i++) {
 395                 nh = name_hash_table[i];
 396                 while (nh) {
 397                         nh1 = nh->next;
 398                         free(nh);
 399                         nh = nh1;
 400                 }
 401                 name_hash_table[i] = NULL;
 402
 403         }
 404 }