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_hash *	find_hash (struct directory_entry *spnt)
EXPORT void	flush_hash ()
EXPORT void	add_directory_hash (dev_t dev, ino_t inode)
EXPORT struct file_hash *	find_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_entry *	find_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_hash *	hash_table [NR_HASH]
static struct file_hash *	directory_hash_table [NR_HASH]
static struct name_hash *	name_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))

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]

EXPORT struct directory_entry *find_file_hash __PR

(

(char *name)

)

__PR() [2/6]

LOCAL unsigned int name_hash __PR

(

(const char *name)

)

__PR() [3/6]

EXPORT void add_directory_hash __PR

(

(dev_t dev, ino_t inode)

)

__PR() [4/6]

EXPORT void add_file_hash __PR

(

(struct directory_entry *de)

)

__PR() [5/6]

EXPORT void add_hash __PR

(

(struct directory_entry *spnt)

)

__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.

{
    struct file_hash *s_hash;
    unsigned int    hash_number;
 
    if (!cache_inodes)
        return;
    if (dev == UNCACHED_DEVICE &&
        (inode == TABLE_INODE || inode == UNCACHED_INODE))
        return;
 
    hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
 
    s_hash = (struct file_hash *)e_malloc(sizeof (struct file_hash));
    s_hash->next = directory_hash_table[hash_number];
    s_hash->inode = inode;
    s_hash->dev = dev;
    s_hash->nlink = 0;
    directory_hash_table[hash_number] = s_hash;
}

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.

{
    struct name_hash    *new;
    int         hash;
    Uchar           *p;
    int         sum = 0;
 
    new = (struct name_hash *)e_malloc(sizeof (struct name_hash));
    new->de = de;
    new->next = NULL;
    for (p = (Uchar *)de->isorec.name; *p; p++) {
        if (*p == ';')
            break;
        sum += *p & 0xFF;
    }
    new->sum = sum;
    hash = name_hash(de->isorec.name);
 
    /* Now insert into the hash table */
    new->next = name_hash_table[hash];
    name_hash_table[hash] = new;
}

Referenced by sort_n_finish().

add_hash()

EXPORT void add_hash

(

struct directory_entry *

spnt

)

Definition at line 140 of file hash.c.

{
    struct file_hash *s_hash;
    unsigned int    hash_number = 0;
 
    if (spnt->size == 0 || spnt->starting_block == 0)
        if (spnt->size != 0 && spnt->starting_block == 0) {
            comerrno(EX_BAD,
            _("Non zero-length file '%s' assigned zero extent.\n"),
                            spnt->name);
        };
 
#ifdef  DUPLICATES_ONCE
    if (!cache_inodes && !duplicates_once)
#else
    if (!cache_inodes)
#endif
        return;
    if (spnt->dev == UNCACHED_DEVICE &&
        (spnt->inode == TABLE_INODE || spnt->inode == UNCACHED_INODE)) {
        return;
    }
#ifdef  DUPLICATES_ONCE
    if (cache_inodes)
#endif
        hash_number = HASH_FN((unsigned int) spnt->dev,
                        (unsigned int) spnt->inode);
#ifdef  DUPLICATES_ONCE
    else if (duplicates_once &&
            spnt->size && !(spnt->isorec.flags[0] & ISO_DIRECTORY))
        hash_number = UNIQUE_FILES_HASH_FN((unsigned int) spnt->size);
#endif
 
#if 0
    if (verbose > 1)
        fprintf(stderr, "%s ", spnt->name);
#endif
    s_hash = (struct file_hash *)e_malloc(sizeof (struct file_hash));
    s_hash->next = hash_table[hash_number];
    s_hash->inode = spnt->inode;
    s_hash->dev = spnt->dev;
    s_hash->nlink = 0;
    s_hash->starting_block = spnt->starting_block;
    s_hash->size = spnt->size;
#if defined(SORTING) || defined(DUPLICATES_ONCE)
    s_hash->de = spnt;
#endif /* defined(SORTING) || defined(DUPLICATES_ONCE) */
    hash_table[hash_number] = s_hash;
}

delete_file_hash()

EXPORT int delete_file_hash

(

struct directory_entry *

de

)

Definition at line 559 of file hash.c.

{
    struct name_hash    *nh;
    struct name_hash    *prev;
    int         hash;
 
    prev = NULL;
    hash = name_hash(de->isorec.name);
    for (nh = name_hash_table[hash]; nh; nh = nh->next) {
        if (nh->de == de)
            break;
        prev = nh;
    }
    if (!nh)
        return (1);
    if (!prev)
        name_hash_table[hash] = nh->next;
    else
        prev->next = nh->next;
    free(nh);
    return (0);
}

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.

{
    unsigned int    hash_number;
    struct file_hash *spnt;
 
    if (!cache_inodes)
        return (NULL);
    if (dev == UNCACHED_DEVICE &&
        (inode == TABLE_INODE || inode == UNCACHED_INODE))
        return (NULL);
 
    hash_number = HASH_FN((unsigned int) dev, (unsigned int) inode);
    spnt = directory_hash_table[hash_number];
    while (spnt) {
        if (spnt->inode == inode && spnt->dev == dev)
            return (spnt);
        spnt = spnt->next;
    };
    return (NULL);
}

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.

{
    register char           *p1;
    register char           *p2;
    register struct name_hash   *nh;
    register int            sum = 0;
 
    if (debug > 1)
        error("find_hash('%s')\n", name);
 
    for (p1 = name; *p1; p1++) {
        if (*p1 == ';')
            break;
        sum += *p1 & 0xFF;
    }
 
    for (nh = name_hash_table[name_hash(name)]; nh; nh = nh->next) {
        if (nh->sum != sum)
            continue;
 
        p1 = name;
        p2 = nh->de->isorec.name;
        if (debug > 1)
            error(_("Checking name '%s' isorec.name '%s'\n"), p1, p2);
 
        /* Look for end of string, or a mismatch. */
        while (1 == 1) {
            if ((*p1 == '\0' || *p1 == ';') ||
                (*p2 == '\0' || *p2 == ';') ||
                (*p1 != *p2)) {
                break;
            }
            p1++;
            p2++;
        }
        if (!isoname_endsok(p1) || !isoname_endsok(p2)) {
            if (debug > 1) {
                if (!isoname_endsok(p1))
                    error(_("'%s' does NOT END OK\n"), p1);
                if (!isoname_endsok(p2))
                    error(_("'%s' does NOT END OK\n"), p2);
            }
            /*
             * If one file does not end with a valid version number
             * and the other name ends here, we found a miss match.
             */
            if (*p1 == '\0' || *p2 == '\0')
                continue;
 
            if (*p1 == ';' && *p2 == ';') {
                p1++;
                p2++;
                continue;
            }
        }
 
        /*
         * If we are at the end of both strings, then we have a match.
         */
        if ((*p1 == '\0' || *p1 == ';') &&
            (*p2 == '\0' || *p2 == ';')) {
            return (nh->de);
        }
    }
    return (NULL);
}

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.

{
    unsigned int    hash_number;
    struct file_hash *s_hash;
 
#ifdef  DUPLICATES_ONCE
    if (!cache_inodes && !duplicates_once)
#else
    if (!cache_inodes)
#endif
        return (NULL);
    if (spnt->dev == UNCACHED_DEVICE &&
        (spnt->inode == TABLE_INODE || spnt->inode == UNCACHED_INODE))
        return (NULL);
 
#ifdef  DUPLICATES_ONCE
    if (cache_inodes) {
#endif
        hash_number = HASH_FN((unsigned int) spnt->dev,
                    (unsigned int) spnt->inode);
        s_hash = hash_table[hash_number];
        while (s_hash) {
            if (s_hash->inode == spnt->inode &&
                s_hash->dev == spnt->dev)
                return (s_hash);
            s_hash = s_hash->next;
        }
#ifdef  DUPLICATES_ONCE
    } else if (duplicates_once &&
            spnt->size && !(spnt->isorec.flags[0] & ISO_DIRECTORY)) {
        hash_number = UNIQUE_FILES_HASH_FN((unsigned int) spnt->size);
        s_hash = hash_table[hash_number];
        while (s_hash) {
            if (compare_files(spnt, s_hash->de))
                return (s_hash);
            s_hash = s_hash->next;
        }
    }
#endif
    return (NULL);
}

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.

{
    struct name_hash    *nh;
    struct name_hash    *nh1;
    int         i;
 
    for (i = 0; i < NR_NAME_HASH; i++) {
        nh = name_hash_table[i];
        while (nh) {
            nh1 = nh->next;
            free(nh);
            nh = nh1;
        }
        name_hash_table[i] = NULL;
 
    }
}

Referenced by sort_n_finish().

flush_hash()

EXPORT void flush_hash

(

)

Definition at line 240 of file hash.c.

{
    struct file_hash    *fh;
    struct file_hash    *fh1;
    int         i;
 
    for (i = 0; i < NR_HASH; i++) {
        fh = hash_table[i];
        while (fh) {
            fh1 = fh->next;
            free(fh);
            fh = fh1;
        }
        hash_table[i] = NULL;
    }
}

isoname_endsok()

LOCAL BOOL isoname_endsok

(

char *

name

)

Definition at line 537 of file hash.c.

{
    int i;
    char    *p;
 
    if (*name == '\0')
        return (TRUE);
    if (*name != ';')
        return (FALSE);
 
    for (p = ++name, i = 0; *p && i < 5; p++, i++) {
        if (*p < '0' || *p > '9')
            return (FALSE);
    }
    i = atoi(name);
    if (i < 1 || i > 32767)
        return (FALSE);
    return (TRUE);
}

Referenced by find_file_hash().

name_hash()

LOCAL unsigned int name_hash

(

char *

name

)

const

Definition at line 413 of file hash.c.

{
    unsigned int    hash = 0;
    const char  *p;
 
    p = name;
 
    while (*p) {
        /*
         * Don't hash the  iso9660 version number.
         * This way we can detect duplicates in cases where we have
         * directories (i.e. foo) and non-directories (i.e. foo;1).
         */
        if (*p == ';') {
            break;
        }
        hash = (hash << 15) + (hash << 3) + (hash >> 3) + (*p++ & 0xFF);
    }
    return (hash % NR_NAME_HASH);
}

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

struct file_hash* hash_table[NR_HASH]

static

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.