ReactOS 0.4.15-dev-8096-ga0eec98
hash.c File Reference
#include <schily/mconfig.h>
#include "mkisofs.h"
#include <schily/schily.h>
#include <schily/sha3.h>
Include dependency graph for hash.c:

Go to the source code of this file.

Classes

struct  name_hash
 

Macros

#define NR_HASH   (16*1024)
 
#define HASH_FN(DEV, INO)   ((DEV + INO + (INO >> 8) + (INO << 16)) % NR_HASH)
 
#define NR_NAME_HASH   128
 
#define eo(p)
 

Functions

EXPORT void add_hash __PR ((struct directory_entry *spnt))
 
EXPORT void flush_hash __PR ((void))
 
EXPORT void add_directory_hash __PR ((dev_t dev, ino_t inode))
 
LOCAL unsigned int name_hash __PR ((const char *name))
 
EXPORT void add_file_hash __PR ((struct directory_entry *de))
 
EXPORT struct directory_entry *find_file_hash __PR ((char *name))
 
EXPORT void add_hash (struct directory_entry *spnt)
 
EXPORT struct file_hashfind_hash (struct directory_entry *spnt)
 
EXPORT void flush_hash ()
 
EXPORT void add_directory_hash (dev_t dev, ino_t inode)
 
EXPORT struct file_hashfind_directory_hash (dev_t dev, ino_t inode)
 
LOCAL unsigned int name_hash (char *name) const
 
EXPORT void add_file_hash (struct directory_entry *de)
 
EXPORT struct directory_entryfind_file_hash (char *name)
 
LOCAL BOOL isoname_endsok (char *name)
 
EXPORT int delete_file_hash (struct directory_entry *de)
 
EXPORT void flush_file_hash ()
 

Variables

static UConst char sccsid []
 
static struct file_hashhash_table [NR_HASH]
 
static struct file_hashdirectory_hash_table [NR_HASH]
 
static struct name_hashname_hash_table [NR_NAME_HASH] = {0, }
 

Macro Definition Documentation

◆ eo

#define eo (   p)
Value:
(((p)[0] == '\0') || \
((p)[0] == ';' && (p)[1] == '1' && (p)[2] == '\0') || \
isoname_endsok(p))
GLfloat GLfloat p
Definition: glext.h:8902

Definition at line 532 of file hash.c.

◆ HASH_FN

#define HASH_FN (   DEV,
  INO 
)    ((DEV + INO + (INO >> 8) + (INO << 16)) % NR_HASH)

Definition at line 58 of file hash.c.

◆ NR_HASH

#define NR_HASH   (16*1024)

Definition at line 56 of file hash.c.

◆ NR_NAME_HASH

#define NR_NAME_HASH   128

Definition at line 405 of file hash.c.

Function Documentation

◆ __PR() [1/6]

◆ __PR() [2/6]

◆ __PR() [3/6]

◆ __PR() [4/6]

◆ __PR() [5/6]

◆ __PR() [6/6]

EXPORT void flush_hash __PR ( (void )

◆ add_directory_hash()

EXPORT void add_directory_hash ( dev_t  dev,
ino_t  inode 
)

Definition at line 346 of file hash.c.

350{
351 struct file_hash *s_hash;
352 unsigned int hash_number;
353
354 if (!cache_inodes)
355 return;
356 if (dev == UNCACHED_DEVICE &&
358 return;
359
360 hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
361
362 s_hash = (struct file_hash *)e_malloc(sizeof (struct file_hash));
363 s_hash->next = directory_hash_table[hash_number];
364 s_hash->inode = inode;
365 s_hash->dev = dev;
366 s_hash->nlink = 0;
367 directory_hash_table[hash_number] = s_hash;
368}
int cache_inodes
Definition: mkisofs.c:141
EXPORT void * e_malloc(size_t size)
Definition: mkisofs.c:3921
#define TABLE_INODE
Definition: mkisofs.h:763
#define UNCACHED_DEVICE
Definition: mkisofs.h:765
#define UNCACHED_INODE
Definition: mkisofs.h:764
static struct file_hash * directory_hash_table[NR_HASH]
Definition: hash.c:339
#define HASH_FN(DEV, INO)
Definition: hash.c:58
dev_t dev
Definition: mkisofs.h:159
ino_t inode
Definition: mkisofs.h:158
nlink_t nlink
Definition: mkisofs.h:160
struct file_hash * next
Definition: mkisofs.h:157
Definition: fs.h:78

Referenced by insert_file_entry(), and main().

◆ add_file_hash()

EXPORT void add_file_hash ( struct directory_entry de)

Definition at line 436 of file hash.c.

438{
439 struct name_hash *new;
440 int hash;
441 Uchar *p;
442 int sum = 0;
443
444 new = (struct name_hash *)e_malloc(sizeof (struct name_hash));
445 new->de = de;
446 new->next = NULL;
447 for (p = (Uchar *)de->isorec.name; *p; p++) {
448 if (*p == ';')
449 break;
450 sum += *p & 0xFF;
451 }
452 new->sum = sum;
453 hash = name_hash(de->isorec.name);
454
455 /* Now insert into the hash table */
456 new->next = name_hash_table[hash];
457 name_hash_table[hash] = new;
458}
#define NULL
Definition: types.h:112
static int sum(int x_, int y_)
Definition: ptr2_test.cpp:35
static struct name_hash * name_hash_table[NR_NAME_HASH]
Definition: hash.c:407
Definition: _hash_fun.h:40
struct directory_entry * de
Definition: hash.c:401
unsigned char Uchar
Definition: utypes.h:45

Referenced by sort_n_finish().

◆ add_hash()

EXPORT void add_hash ( struct directory_entry spnt)

Definition at line 140 of file hash.c.

142{
143 struct file_hash *s_hash;
144 unsigned int hash_number = 0;
145
146 if (spnt->size == 0 || spnt->starting_block == 0)
147 if (spnt->size != 0 && spnt->starting_block == 0) {
149 _("Non zero-length file '%s' assigned zero extent.\n"),
150 spnt->name);
151 };
152
153#ifdef DUPLICATES_ONCE
154 if (!cache_inodes && !duplicates_once)
155#else
156 if (!cache_inodes)
157#endif
158 return;
159 if (spnt->dev == UNCACHED_DEVICE &&
160 (spnt->inode == TABLE_INODE || spnt->inode == UNCACHED_INODE)) {
161 return;
162 }
163#ifdef DUPLICATES_ONCE
164 if (cache_inodes)
165#endif
166 hash_number = HASH_FN((unsigned int) spnt->dev,
167 (unsigned int) spnt->inode);
168#ifdef DUPLICATES_ONCE
169 else if (duplicates_once &&
170 spnt->size && !(spnt->isorec.flags[0] & ISO_DIRECTORY))
171 hash_number = UNIQUE_FILES_HASH_FN((unsigned int) spnt->size);
172#endif
173
174#if 0
175 if (verbose > 1)
176 fprintf(stderr, "%s ", spnt->name);
177#endif
178 s_hash = (struct file_hash *)e_malloc(sizeof (struct file_hash));
179 s_hash->next = hash_table[hash_number];
180 s_hash->inode = spnt->inode;
181 s_hash->dev = spnt->dev;
182 s_hash->nlink = 0;
183 s_hash->starting_block = spnt->starting_block;
184 s_hash->size = spnt->size;
185#if defined(SORTING) || defined(DUPLICATES_ONCE)
186 s_hash->de = spnt;
187#endif /* defined(SORTING) || defined(DUPLICATES_ONCE) */
188 hash_table[hash_number] = s_hash;
189}
EXPORT void comerrno(int err, char *msg, va_alist)
Definition: comerr.c:137
#define _(X)
Definition: i386-dis.c:35
#define stderr
Definition: stdio.h:100
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
#define ISO_DIRECTORY
Definition: iso9660.h:265
#define verbose
Definition: rosglue.h:36
#define EX_BAD
Definition: standard.h:62
dev_t dev
Definition: mkisofs.h:133
unsigned int starting_block
Definition: mkisofs.h:111
off_t size
Definition: mkisofs.h:112
char * name
Definition: mkisofs.h:116
struct iso_directory_record isorec
Definition: mkisofs.h:110
ino_t inode
Definition: mkisofs.h:132
unsigned int starting_block
Definition: mkisofs.h:161
off_t size
Definition: mkisofs.h:162

◆ delete_file_hash()

EXPORT int delete_file_hash ( struct directory_entry de)

Definition at line 559 of file hash.c.

561{
562 struct name_hash *nh;
563 struct name_hash *prev;
564 int hash;
565
566 prev = NULL;
567 hash = name_hash(de->isorec.name);
568 for (nh = name_hash_table[hash]; nh; nh = nh->next) {
569 if (nh->de == de)
570 break;
571 prev = nh;
572 }
573 if (!nh)
574 return (1);
575 if (!prev)
577 else
578 prev->next = nh->next;
579 free(nh);
580 return (0);
581}
#define free
Definition: debug_ros.c:5
struct name_hash * next
Definition: hash.c:400

Referenced by sort_n_finish().

◆ find_directory_hash()

EXPORT struct file_hash * find_directory_hash ( dev_t  dev,
ino_t  inode 
)

Definition at line 375 of file hash.c.

379{
380 unsigned int hash_number;
381 struct file_hash *spnt;
382
383 if (!cache_inodes)
384 return (NULL);
385 if (dev == UNCACHED_DEVICE &&
387 return (NULL);
388
389 hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
390 spnt = directory_hash_table[hash_number];
391 while (spnt) {
392 if (spnt->inode == inode && spnt->dev == dev)
393 return (spnt);
394 spnt = spnt->next;
395 };
396 return (NULL);
397}

Referenced by insert_file_entry().

◆ find_file_hash()

EXPORT struct directory_entry * find_file_hash ( char name)

Definition at line 461 of file hash.c.

463{
464 register char *p1;
465 register char *p2;
466 register struct name_hash *nh;
467 register int sum = 0;
468
469 if (debug > 1)
470 error("find_hash('%s')\n", name);
471
472 for (p1 = name; *p1; p1++) {
473 if (*p1 == ';')
474 break;
475 sum += *p1 & 0xFF;
476 }
477
478 for (nh = name_hash_table[name_hash(name)]; nh; nh = nh->next) {
479 if (nh->sum != sum)
480 continue;
481
482 p1 = name;
483 p2 = nh->de->isorec.name;
484 if (debug > 1)
485 error(_("Checking name '%s' isorec.name '%s'\n"), p1, p2);
486
487 /* Look for end of string, or a mismatch. */
488 while (1 == 1) {
489 if ((*p1 == '\0' || *p1 == ';') ||
490 (*p2 == '\0' || *p2 == ';') ||
491 (*p1 != *p2)) {
492 break;
493 }
494 p1++;
495 p2++;
496 }
497 if (!isoname_endsok(p1) || !isoname_endsok(p2)) {
498 if (debug > 1) {
499 if (!isoname_endsok(p1))
500 error(_("'%s' does NOT END OK\n"), p1);
501 if (!isoname_endsok(p2))
502 error(_("'%s' does NOT END OK\n"), p2);
503 }
504 /*
505 * If one file does not end with a valid version number
506 * and the other name ends here, we found a miss match.
507 */
508 if (*p1 == '\0' || *p2 == '\0')
509 continue;
510
511 if (*p1 == ';' && *p2 == ';') {
512 p1++;
513 p2++;
514 continue;
515 }
516 }
517
518 /*
519 * If we are at the end of both strings, then we have a match.
520 */
521 if ((*p1 == '\0' || *p1 == ';') &&
522 (*p2 == '\0' || *p2 == ';')) {
523 return (nh->de);
524 }
525 }
526 return (NULL);
527}
#define debug(msg)
Definition: key_call.c:71
#define error(str)
Definition: mkdosfs.c:1605
LOCAL BOOL isoname_endsok(char *name)
Definition: hash.c:537
int sum
Definition: hash.c:402
Definition: name.c:39

Referenced by sort_n_finish().

◆ find_hash()

EXPORT struct file_hash * find_hash ( struct directory_entry spnt)

Definition at line 192 of file hash.c.

194{
195 unsigned int hash_number;
196 struct file_hash *s_hash;
197
198#ifdef DUPLICATES_ONCE
199 if (!cache_inodes && !duplicates_once)
200#else
201 if (!cache_inodes)
202#endif
203 return (NULL);
204 if (spnt->dev == UNCACHED_DEVICE &&
205 (spnt->inode == TABLE_INODE || spnt->inode == UNCACHED_INODE))
206 return (NULL);
207
208#ifdef DUPLICATES_ONCE
209 if (cache_inodes) {
210#endif
211 hash_number = HASH_FN((unsigned int) spnt->dev,
212 (unsigned int) spnt->inode);
213 s_hash = hash_table[hash_number];
214 while (s_hash) {
215 if (s_hash->inode == spnt->inode &&
216 s_hash->dev == spnt->dev)
217 return (s_hash);
218 s_hash = s_hash->next;
219 }
220#ifdef DUPLICATES_ONCE
221 } else if (duplicates_once &&
222 spnt->size && !(spnt->isorec.flags[0] & ISO_DIRECTORY)) {
223 hash_number = UNIQUE_FILES_HASH_FN((unsigned int) spnt->size);
224 s_hash = hash_table[hash_number];
225 while (s_hash) {
226 if (compare_files(spnt, s_hash->de))
227 return (s_hash);
228 s_hash = s_hash->next;
229 }
230 }
231#endif
232 return (NULL);
233}
static int compare_files(HANDLE file1, HANDLE file2)
Definition: install.c:2279

Referenced by assign_file_addresses(), assign_inodes(), assign_linkcount(), and compute_linkcount().

◆ flush_file_hash()

EXPORT void flush_file_hash ( )

Definition at line 584 of file hash.c.

585{
586 struct name_hash *nh;
587 struct name_hash *nh1;
588 int i;
589
590 for (i = 0; i < NR_NAME_HASH; i++) {
591 nh = name_hash_table[i];
592 while (nh) {
593 nh1 = nh->next;
594 free(nh);
595 nh = nh1;
596 }
598
599 }
600}
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define NR_NAME_HASH
Definition: hash.c:405

Referenced by sort_n_finish().

◆ flush_hash()

EXPORT void flush_hash ( )

Definition at line 240 of file hash.c.

241{
242 struct file_hash *fh;
243 struct file_hash *fh1;
244 int i;
245
246 for (i = 0; i < NR_HASH; i++) {
247 fh = hash_table[i];
248 while (fh) {
249 fh1 = fh->next;
250 free(fh);
251 fh = fh1;
252 }
253 hash_table[i] = NULL;
254 }
255}
#define NR_HASH
Definition: hash.c:56

◆ isoname_endsok()

LOCAL BOOL isoname_endsok ( char name)

Definition at line 537 of file hash.c.

539{
540 int i;
541 char *p;
542
543 if (*name == '\0')
544 return (TRUE);
545 if (*name != ';')
546 return (FALSE);
547
548 for (p = ++name, i = 0; *p && i < 5; p++, i++) {
549 if (*p < '0' || *p > '9')
550 return (FALSE);
551 }
552 i = atoi(name);
553 if (i < 1 || i > 32767)
554 return (FALSE);
555 return (TRUE);
556}
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
_Check_return_ int __cdecl atoi(_In_z_ const char *_Str)

Referenced by find_file_hash().

◆ name_hash()

LOCAL unsigned int name_hash ( char name) const

Definition at line 413 of file hash.c.

415{
416 unsigned int hash = 0;
417 const char *p;
418
419 p = name;
420
421 while (*p) {
422 /*
423 * Don't hash the iso9660 version number.
424 * This way we can detect duplicates in cases where we have
425 * directories (i.e. foo) and non-directories (i.e. foo;1).
426 */
427 if (*p == ';') {
428 break;
429 }
430 hash = (hash << 15) + (hash << 3) + (hash >> 3) + (*p++ & 0xFF);
431 }
432 return (hash % NR_NAME_HASH);
433}

Variable Documentation

◆ directory_hash_table

struct file_hash* directory_hash_table[NR_HASH]
static

Definition at line 339 of file hash.c.

Referenced by add_directory_hash(), and find_directory_hash().

◆ hash_table

Definition at line 60 of file hash.c.

◆ name_hash_table

struct name_hash* name_hash_table[NR_NAME_HASH] = {0, }
static

Definition at line 407 of file hash.c.

Referenced by add_file_hash(), delete_file_hash(), find_file_hash(), and flush_file_hash().

◆ sccsid

UConst char sccsid[]
static
Initial value:
=
"@(#)hash.c 1.30 16/12/13 joerg"

Definition at line 4 of file hash.c.