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
31static struct file_hash * hash_table[NR_HASH] = {0,};
32
33void 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
58struct 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 */
75void flush_hash(void){
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
91static struct file_hash * directory_hash_table[NR_HASH] = {0,};
92
93void 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
107struct 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
121struct  name_hash
122{
123  struct name_hash * next;
124  struct directory_entry * de;
125};
126
127#define NR_NAME_HASH 128
128
129static struct name_hash * name_hash_table[NR_NAME_HASH] = {0,};
130
131/*
132 * Find the hash bucket for this name.
133 */
134static  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
158void 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
172struct 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
211int 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
230void 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