zip_hash.c File Reference

#include "zipint.h"
#include <stdlib.h>
#include <string.h>

Go to the source code of this file.

Classes
struct	zip_hash_entry
struct	zip_hash

Macros
#define	HASH_MULTIPLIER   33
#define	HASH_START   5381
#define	HASH_MAX_FILL   .75
#define	HASH_MIN_FILL   .01
#define	HASH_MIN_SIZE   256
#define	HASH_MAX_SIZE   0x80000000ul

Typedefs
typedef struct zip_hash_entry	zip_hash_entry_t

Functions
static void	free_list (zip_hash_entry_t *entry)
static zip_uint32_t	hash_string (const zip_uint8_t *name)
static bool	hash_resize (zip_hash_t *hash, zip_uint32_t new_size, zip_error_t *error)
static zip_uint32_t	size_for_capacity (zip_uint64_t capacity)
zip_hash_t *	_zip_hash_new (zip_error_t *error)
void	_zip_hash_free (zip_hash_t *hash)
bool	_zip_hash_add (zip_hash_t *hash, const zip_uint8_t *name, zip_uint64_t index, zip_flags_t flags, zip_error_t *error)
bool	_zip_hash_delete (zip_hash_t *hash, const zip_uint8_t *name, zip_error_t *error)
zip_int64_t	_zip_hash_lookup (zip_hash_t *hash, const zip_uint8_t *name, zip_flags_t flags, zip_error_t *error)
bool	_zip_hash_reserve_capacity (zip_hash_t *hash, zip_uint64_t capacity, zip_error_t *error)
bool	_zip_hash_revert (zip_hash_t *hash, zip_error_t *error)

Macro Definition Documentation

HASH_MAX_FILL

#define HASH_MAX_FILL   .75

Definition at line 43 of file zip_hash.c.

HASH_MAX_SIZE

#define HASH_MAX_SIZE   0x80000000ul

Definition at line 48 of file zip_hash.c.

HASH_MIN_FILL

#define HASH_MIN_FILL   .01

Definition at line 44 of file zip_hash.c.

HASH_MIN_SIZE

#define HASH_MIN_SIZE   256

Definition at line 47 of file zip_hash.c.

HASH_MULTIPLIER

#define HASH_MULTIPLIER   33

Definition at line 39 of file zip_hash.c.

HASH_START

#define HASH_START   5381

Definition at line 40 of file zip_hash.c.

Typedef Documentation

zip_hash_entry_t

typedef struct zip_hash_entry zip_hash_entry_t

Definition at line 1 of file zip_hash.c.

Function Documentation

_zip_hash_add()

bool _zip_hash_add	(	zip_hash_t *	hash,
		const zip_uint8_t *	name,
		zip_uint64_t	index,
		zip_flags_t	flags,
		zip_error_t *	error
	)

Definition at line 205 of file zip_hash.c.

                                                                                                                    {
    zip_uint32_t hash_value, table_index;
    zip_hash_entry_t *entry;
 
    if (hash == NULL || name == NULL || index > ZIP_INT64_MAX) {
        zip_error_set(error, ZIP_ER_INVAL, 0);
        return false;
    }
 
    if (hash->table_size == 0) {
        if (!hash_resize(hash, HASH_MIN_SIZE, error)) {
            return false;
        }
    }
 
    hash_value = hash_string(name);
    table_index = hash_value % hash->table_size;
 
    for (entry = hash->table[table_index]; entry != NULL; entry = entry->next) {
        if (entry->hash_value == hash_value && strcmp((const char *)name, (const char *)entry->name) == 0) {
            if (((flags & ZIP_FL_UNCHANGED) && entry->orig_index != -1) || entry->current_index != -1) {
                zip_error_set(error, ZIP_ER_EXISTS, 0);
                return false;
            }
            else {
                break;
            }
        }
    }
 
    if (entry == NULL) {
        if ((entry = (zip_hash_entry_t *)malloc(sizeof(zip_hash_entry_t))) == NULL) {
            zip_error_set(error, ZIP_ER_MEMORY, 0);
            return false;
        }
        entry->name = name;
        entry->next = hash->table[table_index];
        hash->table[table_index] = entry;
        entry->hash_value = hash_value;
        entry->orig_index = -1;
        hash->nentries++;
        if (hash->nentries > hash->table_size * HASH_MAX_FILL && hash->table_size < HASH_MAX_SIZE) {
            if (!hash_resize(hash, hash->table_size * 2, error)) {
                return false;
            }
        }
    }
 
    if (flags & ZIP_FL_UNCHANGED) {
        entry->orig_index = (zip_int64_t)index;
    }
    entry->current_index = (zip_int64_t)index;
 
    return true;
}

References error(), flags, HASH_MAX_FILL, HASH_MAX_SIZE, HASH_MIN_SIZE, hash_resize(), hash_string(), malloc(), name, entry::name, zip_hash::nentries, NULL, zip_hash::table, zip_hash::table_size, ZIP_ER_EXISTS, ZIP_ER_INVAL, ZIP_ER_MEMORY, zip_error_set(), ZIP_FL_UNCHANGED, and ZIP_INT64_MAX.

Referenced by _zip_open(), _zip_set_name(), and _zip_unchange().

_zip_hash_delete()

bool _zip_hash_delete	(	zip_hash_t *	hash,
		const zip_uint8_t *	name,
		zip_error_t *	error
	)

Definition at line 264 of file zip_hash.c.

                                                                                {
    zip_uint32_t hash_value, index;
    zip_hash_entry_t *entry, *previous;
 
    if (hash == NULL || name == NULL) {
        zip_error_set(error, ZIP_ER_INVAL, 0);
        return false;
    }
 
    if (hash->nentries > 0) {
        hash_value = hash_string(name);
        index = hash_value % hash->table_size;
        previous = NULL;
        entry = hash->table[index];
        while (entry) {
            if (entry->hash_value == hash_value && strcmp((const char *)name, (const char *)entry->name) == 0) {
                if (entry->orig_index == -1) {
                    if (previous) {
                        previous->next = entry->next;
                    }
                    else {
                        hash->table[index] = entry->next;
                    }
                    free(entry);
                    hash->nentries--;
                    if (hash->nentries < hash->table_size * HASH_MIN_FILL && hash->table_size > HASH_MIN_SIZE) {
                        if (!hash_resize(hash, hash->table_size / 2, error)) {
                            return false;
                        }
                    }
                }
                else {
                    entry->current_index = -1;
                }
                return true;
            }
            previous = entry;
            entry = entry->next;
        }
    }
 
    zip_error_set(error, ZIP_ER_NOENT, 0);
    return false;
}

References error(), free(), HASH_MIN_FILL, HASH_MIN_SIZE, hash_resize(), hash_string(), entry::name, zip_hash::nentries, zip_hash_entry::next, NULL, zip_hash::table, zip_hash::table_size, ZIP_ER_INVAL, ZIP_ER_NOENT, and zip_error_set().

Referenced by _zip_set_name(), _zip_unchange(), and zip_delete().

_zip_hash_free()

void _zip_hash_free

(

zip_hash_t *

hash

)

Definition at line 184 of file zip_hash.c.

                                 {
    zip_uint32_t i;
 
    if (hash == NULL) {
        return;
    }
 
    if (hash->table != NULL) {
        for (i = 0; i < hash->table_size; i++) {
            if (hash->table[i] != NULL) {
                free_list(hash->table[i]);
            }
        }
        free(hash->table);
    }
    free(hash);
}

References free(), free_list(), i, NULL, zip_hash::table, and zip_hash::table_size.

Referenced by zip_discard().

_zip_hash_lookup()

zip_int64_t _zip_hash_lookup	(	zip_hash_t *	hash,
		const zip_uint8_t *	name,
		zip_flags_t	flags,
		zip_error_t *	error
	)

Definition at line 312 of file zip_hash.c.

                                                                                                   {
    zip_uint32_t hash_value, index;
    zip_hash_entry_t *entry;
 
    if (hash == NULL || name == NULL) {
        zip_error_set(error, ZIP_ER_INVAL, 0);
        return -1;
    }
 
    if (hash->nentries > 0) {
        hash_value = hash_string(name);
        index = hash_value % hash->table_size;
        for (entry = hash->table[index]; entry != NULL; entry = entry->next) {
            if (strcmp((const char *)name, (const char *)entry->name) == 0) {
                if (flags & ZIP_FL_UNCHANGED) {
                    if (entry->orig_index != -1) {
                        return entry->orig_index;
                    }
                }
                else {
                    if (entry->current_index != -1) {
                        return entry->current_index;
                    }
                }
                break;
            }
        }
    }
 
    zip_error_set(error, ZIP_ER_NOENT, 0);
    return -1;
}

References error(), flags, hash_string(), entry::name, zip_hash::nentries, NULL, zip_hash::table, zip_hash::table_size, ZIP_ER_INVAL, ZIP_ER_NOENT, zip_error_set(), and ZIP_FL_UNCHANGED.

Referenced by _zip_name_locate().

_zip_hash_new()

zip_hash_t* _zip_hash_new

(

zip_error_t *

error

)

Definition at line 167 of file zip_hash.c.

                                  {
    zip_hash_t *hash;
 
    if ((hash = (zip_hash_t *)malloc(sizeof(zip_hash_t))) == NULL) {
        zip_error_set(error, ZIP_ER_MEMORY, 0);
        return NULL;
    }
 
    hash->table_size = 0;
    hash->nentries = 0;
    hash->table = NULL;
 
    return hash;
}

References error(), malloc(), zip_hash::nentries, NULL, zip_hash::table, zip_hash::table_size, ZIP_ER_MEMORY, and zip_error_set().

Referenced by _zip_new().

_zip_hash_reserve_capacity()

bool _zip_hash_reserve_capacity	(	zip_hash_t *	hash,
		zip_uint64_t	capacity,
		zip_error_t *	error
	)

Definition at line 347 of file zip_hash.c.

                                                                                        {
    zip_uint32_t new_size;
 
    if (capacity == 0) {
        return true;
    }
 
    new_size = size_for_capacity(capacity);
 
    if (new_size <= hash->table_size) {
        return true;
    }
 
    if (!hash_resize(hash, new_size, error)) {
        return false;
    }
 
    return true;
}

References error(), hash_resize(), and size_for_capacity().

Referenced by _zip_open().

_zip_hash_revert()

bool _zip_hash_revert	(	zip_hash_t *	hash,
		zip_error_t *	error
	)

Definition at line 369 of file zip_hash.c.

                                                       {
    zip_uint32_t i;
    zip_hash_entry_t *entry, *previous;
 
    for (i = 0; i < hash->table_size; i++) {
        previous = NULL;
        entry = hash->table[i];
        while (entry) {
            if (entry->orig_index == -1) {
                zip_hash_entry_t *p;
                if (previous) {
                    previous->next = entry->next;
                }
                else {
                    hash->table[i] = entry->next;
                }
                p = entry;
                entry = entry->next;
                /* previous does not change */
                free(p);
                hash->nentries--;
            }
            else {
                entry->current_index = entry->orig_index;
                previous = entry;
                entry = entry->next;
            }
        }
    }
 
    if (hash->nentries < hash->table_size * HASH_MIN_FILL && hash->table_size > HASH_MIN_SIZE) {
        zip_uint32_t new_size = hash->table_size / 2;
        while (hash->nentries < new_size * HASH_MIN_FILL && new_size > HASH_MIN_SIZE) {
            new_size /= 2;
        }
        if (!hash_resize(hash, new_size, error)) {
            return false;
        }
    }
 
    return true;
}

References error(), free(), HASH_MIN_FILL, HASH_MIN_SIZE, hash_resize(), i, zip_hash::nentries, zip_hash_entry::next, NULL, p, zip_hash::table, and zip_hash::table_size.

Referenced by zip_unchange_all().

free_list()

static void free_list ( zip_hash_entry_t *  entry )

static

Definition at line 68 of file zip_hash.c.

                                   {
    while (entry != NULL) {
        zip_hash_entry_t *next = entry->next;
        free(entry);
        entry = next;
    }
}

References free(), and NULL.

Referenced by _zip_hash_free().

hash_resize()

static bool hash_resize ( zip_hash_t *  hash, zip_uint32_t  new_size, zip_error_t *  error  )

static

Definition at line 97 of file zip_hash.c.

                                                                         {
    zip_hash_entry_t **new_table;
 
    if (new_size == hash->table_size) {
        return true;
    }
 
    if ((new_table = (zip_hash_entry_t **)calloc(new_size, sizeof(zip_hash_entry_t *))) == NULL) {
        zip_error_set(error, ZIP_ER_MEMORY, 0);
        return false;
    }
 
    if (hash->nentries > 0) {
        zip_uint32_t i;
 
        for (i = 0; i < hash->table_size; i++) {
            zip_hash_entry_t *entry = hash->table[i];
            while (entry) {
                zip_hash_entry_t *next = entry->next;
 
                zip_uint32_t new_index = entry->hash_value % new_size;
 
                entry->next = new_table[new_index];
                new_table[new_index] = entry;
 
                entry = next;
            }
        }
    }
 
    free(hash->table);
    hash->table = new_table;
    hash->table_size = new_size;
 
    return true;
}

References calloc(), error(), free(), i, zip_hash::nentries, NULL, zip_hash::table, zip_hash::table_size, ZIP_ER_MEMORY, and zip_error_set().

Referenced by _zip_hash_add(), _zip_hash_delete(), _zip_hash_reserve_capacity(), and _zip_hash_revert().

hash_string()

static zip_uint32_t hash_string ( const zip_uint8_t *  name )

static

Definition at line 79 of file zip_hash.c.

                                     {
    zip_uint64_t value = HASH_START;
 
    if (name == NULL) {
        return 0;
    }
 
    while (*name != 0) {
        value = (zip_uint64_t)(((value * HASH_MULTIPLIER) + (zip_uint8_t)*name) % 0x100000000ul);
        name++;
    }
 
    return (zip_uint32_t)value;
}

References HASH_MULTIPLIER, HASH_START, NULL, and value.

Referenced by _zip_hash_add(), _zip_hash_delete(), and _zip_hash_lookup().

size_for_capacity()

static zip_uint32_t size_for_capacity ( zip_uint64_t  capacity )

static

Definition at line 136 of file zip_hash.c.

                                         {
    double needed_size = capacity / HASH_MAX_FILL;
    zip_uint32_t v;
 
    if (needed_size > ZIP_UINT32_MAX) {
        v = ZIP_UINT32_MAX;
    }
    else {
        v = (zip_uint32_t)needed_size;
    }
 
    if (v > HASH_MAX_SIZE) {
        return HASH_MAX_SIZE;
    }
 
    /* From Bit Twiddling Hacks by Sean Eron Anderson <seander@cs.stanford.edu>
     (http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2). */
 
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;
 
    return v;
}

References HASH_MAX_FILL, HASH_MAX_SIZE, v, and ZIP_UINT32_MAX.

Referenced by _zip_hash_reserve_capacity().