home *** CD-ROM | disk | FTP | other *** search
/ Dream 49 / Amiga_Dream_49.iso / beos / utils / mkisofs-1.000 / mkisofs-1.11-beos / hash.c < prev    next >
C/C++ Source or Header  |  1997-04-09  |  6KB  |  227 lines
  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. static char rcsid[] ="$Id: hash.c,v 1.2 1997/02/23 16:11:15 eric Rel $";
  23.  
  24. #include <stdlib.h>
  25. #include "mkisofs.h"
  26.  
  27. #define NR_HASH 1024
  28.  
  29. #define HASH_FN(DEV, INO) ((DEV + INO + (INO >> 2) + (INO << 8)) % NR_HASH)
  30.  
  31. static struct file_hash * hash_table[NR_HASH] = {0,};
  32.  
  33. void FDECL1(add_hash, struct directory_entry *, spnt){
  34.   struct file_hash * s_hash;
  35.   unsigned int hash_number;
  36.  
  37.   if(spnt->size == 0 || spnt->starting_block == 0) 
  38.     if(spnt->size != 0 || spnt->starting_block != 0) {
  39.       fprintf(stderr,"Non zero-length file assigned zero extent.\n");
  40.       exit(1);
  41.     };
  42.  
  43.   if (spnt->dev == (dev_t) UNCACHED_DEVICE || spnt->inode == UNCACHED_INODE) return;
  44.   hash_number = HASH_FN((unsigned int) spnt->dev, (unsigned int) spnt->inode);
  45.  
  46. #if 0
  47.   if (verbose) fprintf(stderr,"%s ",spnt->name);
  48. #endif
  49.   s_hash = (struct file_hash *) e_malloc(sizeof(struct file_hash));
  50.   s_hash->next = hash_table[hash_number];
  51.   s_hash->inode = spnt->inode;
  52.   s_hash->dev = spnt->dev;
  53.   s_hash->starting_block = spnt->starting_block;
  54.   s_hash->size = spnt->size;
  55.   hash_table[hash_number] = s_hash;
  56. }
  57.  
  58. struct file_hash * FDECL2(find_hash, dev_t, dev, ino_t, inode){
  59.   unsigned int hash_number;
  60.   struct file_hash * spnt;
  61.   hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
  62.   if (dev == (dev_t) UNCACHED_DEVICE || inode == UNCACHED_INODE) return NULL;
  63.  
  64.   spnt = hash_table[hash_number];
  65.   while(spnt){
  66.     if(spnt->inode == inode && spnt->dev == dev) return spnt;
  67.     spnt = spnt->next;
  68.   };
  69.   return NULL;
  70. }
  71.  
  72.  
  73. static struct file_hash * directory_hash_table[NR_HASH] = {0,};
  74.  
  75. void FDECL2(add_directory_hash, dev_t, dev, ino_t, inode){
  76.   struct file_hash * s_hash;
  77.   unsigned int hash_number;
  78.  
  79.   if (dev == (dev_t) UNCACHED_DEVICE || inode == UNCACHED_INODE) return;
  80.   hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
  81.  
  82.   s_hash = (struct file_hash *) e_malloc(sizeof(struct file_hash));
  83.   s_hash->next = directory_hash_table[hash_number];
  84.   s_hash->inode = inode;
  85.   s_hash->dev = dev;
  86.   directory_hash_table[hash_number] = s_hash;
  87. }
  88.  
  89. struct file_hash * FDECL2(find_directory_hash, dev_t, dev, ino_t, inode){
  90.   unsigned int hash_number;
  91.   struct file_hash * spnt;
  92.   hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
  93.   if (dev == (dev_t) UNCACHED_DEVICE || inode == UNCACHED_INODE) return NULL;
  94.  
  95.   spnt = directory_hash_table[hash_number];
  96.   while(spnt){
  97.     if(spnt->inode == inode && spnt->dev == dev) return spnt;
  98.     spnt = spnt->next;
  99.   };
  100.   return NULL;
  101. }
  102.  
  103. struct  name_hash
  104. {
  105.   struct name_hash * next;
  106.   struct directory_entry * de;
  107. };
  108.  
  109. #define NR_NAME_HASH 128
  110.  
  111. static struct name_hash * name_hash_table[NR_NAME_HASH] = {0,};
  112.  
  113. /*
  114.  * Find the hash bucket for this name.
  115.  */
  116. static  unsigned int FDECL1(name_hash, const char *, name)
  117. {
  118.   unsigned int hash = 0;
  119.   const char * p;
  120.   
  121.   p = name;
  122.   
  123.   while (*p) 
  124.     {
  125.       /*
  126.        * Don't hash the  iso9660 version number.  This way
  127.        * we can detect duplicates in cases where we have
  128.        * directories (i.e. foo) and non-directories
  129.        * (i.e. foo;1).
  130.        */
  131.       if( *p == ';' )
  132.     {
  133.       break;
  134.     }
  135.       hash = (hash << 15) + (hash << 3) + (hash >> 3) + *p++;
  136.     }
  137.   return hash % NR_NAME_HASH;
  138. }
  139.  
  140. void FDECL1(add_file_hash, struct directory_entry *, de){
  141.     struct name_hash  * new;
  142.     int hash;
  143.  
  144.     new = (struct  name_hash *) e_malloc(sizeof(struct name_hash));
  145.     new->de = de;
  146.     new->next = NULL;
  147.     hash = name_hash(de->isorec.name);
  148.  
  149.     /* Now insert into the hash table */
  150.     new->next = name_hash_table[hash];
  151.     name_hash_table[hash] = new;
  152. }
  153.  
  154. struct directory_entry * FDECL1(find_file_hash, char *, name)
  155. {
  156.   struct name_hash  * nh;
  157.   char            * p1;
  158.   char            * p2;
  159.   
  160.   for(nh = name_hash_table[name_hash(name)]; nh; nh = nh->next)
  161.     {
  162.       p1 = name;
  163.       p2 = nh->de->isorec.name;
  164.  
  165.       /*
  166.        * Look for end of string, or a mismatch.
  167.        */
  168.       while(1==1)
  169.     {
  170.       if(    (*p1 == '\0' || *p1 == ';')
  171.           || (*p2 == '\0' || *p2 == ';')
  172.           || (*p1 != *p2) )
  173.         {
  174.           break;
  175.         }
  176.       p1++;
  177.       p2++;
  178.     }
  179.  
  180.       /*
  181.        * If we are at the end of both strings, then
  182.        * we have a match.
  183.        */
  184.       if(    (*p1 == '\0' || *p1 == ';')
  185.       && (*p2 == '\0' || *p2 == ';') )
  186.     {
  187.       return nh->de;
  188.     }
  189.     }
  190.   return NULL;
  191. }
  192.  
  193. int FDECL1(delete_file_hash, struct directory_entry *, de){
  194.     struct name_hash  * nh, *prev;
  195.     int hash;
  196.  
  197.     prev = NULL;
  198.     hash = name_hash(de->isorec.name);
  199.     for(nh = name_hash_table[hash]; nh; nh = nh->next) {
  200.         if(nh->de == de) break;
  201.         prev = nh;
  202.     }
  203.     if(!nh) return 1;
  204.     if(!prev)
  205.         name_hash_table[hash] = nh->next;
  206.     else
  207.         prev->next = nh->next;
  208.     free(nh);
  209.     return 0;
  210. }
  211.  
  212. void flush_file_hash(){
  213.     struct name_hash  * nh, *nh1;
  214.     int i;
  215.  
  216.     for(i=0; i<NR_NAME_HASH; i++) {
  217.         nh = name_hash_table[i];
  218.         while(nh) {
  219.             nh1 =  nh->next;
  220.             free(nh);
  221.             nh = nh1;
  222.         }
  223.         name_hash_table[i] =  NULL;
  224.         
  225.     }
  226. }
  227.