hash.c
上传用户:xiejiait
上传日期:2007-01-06
资源大小:881k
文件大小:6k
源码类别:

SCSI/ASPI

开发平台:

MultiPlatform

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