← Back to branch summary

~hamo/ubuntu/precise/grub2/grub2.hi_res

« back to all changes in this revision

Viewing changes to util/mkisofs/hash.c

  • Committer: Bazaar Package Importer
  • Author(s): Colin Watson, Colin Watson, Robert Millan, Updated translations
  • Date: 2010-11-22 12:24:56 UTC
  • mfrom: (1.26.4 upstream) (17.3.36 sid)
  • mto: (17.3.43 sid)
  • mto: This revision was merged to the branch mainline in revision 89.
  • Revision ID: james.westby@ubuntu.com-20101122122456-y82z3sfb7k4zfdcc
Tags: 1.99~20101122-1
http://bugs.debian.org/550658
http://bugs.debian.org/550702
http://bugs.debian.org/591416
http://bugs.debian.org/593347
http://bugs.debian.org/551627
http://bugs.debian.org/589325
http://bugs.debian.org/543924
http://bugs.debian.org/603354
http://bugs.debian.org/604003
http://bugs.debian.org/604102
[ Colin Watson ]
* New Bazaar snapshot.  Too many changes to list in full, but some of the
  more user-visible ones are as follows:
  - GRUB script:
    + Function parameters, "break", "continue", "shift", "setparams",
      "return", and "!".
    + "export" command supports multiple variable names.
    + Multi-line quoted strings support.
    + Wildcard expansion.
  - sendkey support.
  - USB hotunplugging and USB serial support.
  - Rename CD-ROM to cd on BIOS.
  - Add new --boot-directory option to grub-install, grub-reboot, and
    grub-set-default; the old --root-directory option is still accepted
    but was often confusing.
  - Basic btrfs detection/UUID support (but no file reading yet).
  - bash-completion for utilities.
  - If a device is listed in device.map, always assume that it is
    BIOS-visible rather than using extra layers such as LVM or RAID.
  - Add grub-mknetdir script (closes: #550658).
  - Remove deprecated "root" command.
  - Handle RAID devices containing virtio components.
  - GRUB Legacy configuration file support (via grub-menulst2cfg).
  - Keyboard layout support (via grub-mklayout and grub-kbdcomp).
  - Check generated grub.cfg for syntax errors before saving.
  - Pause execution for at most ten seconds if any errors are displayed,
    so that the user has a chance to see them.
  - Support submenus.
  - Write embedding zone using Reed-Solomon, so that it's robust against
    being partially overwritten (closes: #550702, #591416, #593347).
  - GRUB_DISABLE_LINUX_RECOVERY and GRUB_DISABLE_NETBSD_RECOVERY merged
    into a single GRUB_DISABLE_RECOVERY variable.
  - Fix loader memory allocation failure (closes: #551627).
  - Don't call savedefault on recovery entries (closes: #589325).
  - Support triple-indirect blocks on ext2 (closes: #543924).
  - Recognise DDF1 fake RAID (closes: #603354).

[ Robert Millan ]
* Use dpkg architecture wildcards.

[ Updated translations ]
* Slovenian (Vanja Cvelbar).  Closes: #604003
* Dzongkha (dawa pemo via Tenzin Dendup).  Closes: #604102

Show diffs side-by-side

added added

removed removed

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