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 23 #include <stdlib.h> 24 #include "config.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 > 1) 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 #ifdef APPLE_HYB 73 /* based on flush_file_hash() below - needed as we wnat to re-use the 74 file hash table */ 75 void flush_hash(){ 76 struct file_hash * fh, *fh1; 77 int i; 78 79 for(i=0; i<NR_HASH; i++) { 80 fh = hash_table[i]; 81 while(fh) { 82 fh1 = fh->next; 83 free(fh); 84 fh = fh1; 85 } 86 hash_table[i] = NULL; 87 } 88 } 89 #endif /* APPLE_HYB */ 90 91 static struct file_hash * directory_hash_table[NR_HASH] = {0,}; 92 93 void FDECL2(add_directory_hash, dev_t, dev, ino_t, inode){ 94 struct file_hash * s_hash; 95 unsigned int hash_number; 96 97 if (dev == (dev_t) UNCACHED_DEVICE || inode == UNCACHED_INODE) return; 98 hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode); 99 100 s_hash = (struct file_hash *) e_malloc(sizeof(struct file_hash)); 101 s_hash->next = directory_hash_table[hash_number]; 102 s_hash->inode = inode; 103 s_hash->dev = dev; 104 directory_hash_table[hash_number] = s_hash; 105 } 106 107 struct file_hash * FDECL2(find_directory_hash, dev_t, dev, ino_t, inode){ 108 unsigned int hash_number; 109 struct file_hash * spnt; 110 hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode); 111 if (dev == (dev_t) UNCACHED_DEVICE || inode == UNCACHED_INODE) return NULL; 112 113 spnt = directory_hash_table[hash_number]; 114 while(spnt){ 115 if(spnt->inode == inode && spnt->dev == dev) return spnt; 116 spnt = spnt->next; 117 }; 118 return NULL; 119 } 120 121 struct name_hash 122 { 123 struct name_hash * next; 124 struct directory_entry * de; 125 }; 126 127 #define NR_NAME_HASH 128 128 129 static struct name_hash * name_hash_table[NR_NAME_HASH] = {0,}; 130 131 /* 132 * Find the hash bucket for this name. 133 */ 134 static unsigned int FDECL1(name_hash, const char *, name) 135 { 136 unsigned int hash = 0; 137 const char * p; 138 139 p = name; 140 141 while (*p) 142 { 143 /* 144 * Don't hash the iso9660 version number. This way 145 * we can detect duplicates in cases where we have 146 * directories (i.e. foo) and non-directories 147 * (i.e. foo;1). 148 */ 149 if( *p == ';' ) 150 { 151 break; 152 } 153 hash = (hash << 15) + (hash << 3) + (hash >> 3) + *p++; 154 } 155 return hash % NR_NAME_HASH; 156 } 157 158 void FDECL1(add_file_hash, struct directory_entry *, de){ 159 struct name_hash * new; 160 int hash; 161 162 new = (struct name_hash *) e_malloc(sizeof(struct name_hash)); 163 new->de = de; 164 new->next = NULL; 165 hash = name_hash(de->isorec.name); 166 167 /* Now insert into the hash table */ 168 new->next = name_hash_table[hash]; 169 name_hash_table[hash] = new; 170 } 171 172 struct directory_entry * FDECL1(find_file_hash, char *, name) 173 { 174 struct name_hash * nh; 175 char * p1; 176 char * p2; 177 178 for(nh = name_hash_table[name_hash(name)]; nh; nh = nh->next) 179 { 180 p1 = name; 181 p2 = nh->de->isorec.name; 182 183 /* 184 * Look for end of string, or a mismatch. 185 */ 186 while(1==1) 187 { 188 if( (*p1 == '\0' || *p1 == ';') 189 || (*p2 == '\0' || *p2 == ';') 190 || (*p1 != *p2) ) 191 { 192 break; 193 } 194 p1++; 195 p2++; 196 } 197 198 /* 199 * If we are at the end of both strings, then 200 * we have a match. 201 */ 202 if( (*p1 == '\0' || *p1 == ';') 203 && (*p2 == '\0' || *p2 == ';') ) 204 { 205 return nh->de; 206 } 207 } 208 return NULL; 209 } 210 211 int FDECL1(delete_file_hash, struct directory_entry *, de){ 212 struct name_hash * nh, *prev; 213 int hash; 214 215 prev = NULL; 216 hash = name_hash(de->isorec.name); 217 for(nh = name_hash_table[hash]; nh; nh = nh->next) { 218 if(nh->de == de) break; 219 prev = nh; 220 } 221 if(!nh) return 1; 222 if(!prev) 223 name_hash_table[hash] = nh->next; 224 else 225 prev->next = nh->next; 226 free(nh); 227 return 0; 228 } 229 230 void flush_file_hash(){ 231 struct name_hash * nh, *nh1; 232 int i; 233 234 for(i=0; i<NR_NAME_HASH; i++) { 235 nh = name_hash_table[i]; 236 while(nh) { 237 nh1 = nh->next; 238 free(nh); 239 nh = nh1; 240 } 241 name_hash_table[i] = NULL; 242 243 } 244 } 245