foolhash.c

一款功能很强的光盘镜象制作工具

/*
   Simple HASH routines, for mkisofs optimization

   COMMAN's notes:   

   This file is taken from Redhat 5.2 install program source 
   I'm even too lazy to write a hash lib, faint.
   Slightly motified by me, separating key and user data.
    
*/
#include <stdlib.h>

#include <unistd.h>
#include <stdio.h>
#include <string.h>

#include "foolhash.h"

#define CHUNK 4

struct hash_table *htNewTable(int size)
{
    struct hash_table *res;
    int i = 0;

    res = malloc(sizeof(struct hash_table));
    res->bucket = malloc(sizeof(struct bucket) * size);
    res->size = size;
    res->totalData = 0;
    res->entries = 0;
    res->overHead = sizeof(struct bucket) * size + CHUNK * sizeof(char *);

    while (i < size) {
	res->bucket[i].data = malloc(CHUNK * sizeof(struct keypair *));
	res->bucket[i].allocated = CHUNK;
	res->bucket[i].firstFree = 0;
	i++;
    }
    
    return res;
}

void htFreeHashTable(struct hash_table *ht)
{
    while (ht->size--) {
        // here we got memory leak,faint
        // but it does not matter since mkisofs won't run forever.
        free(ht->bucket[ht->size].data);
    }
    free(ht->bucket);
    free(ht);
}

void htHashStats(struct hash_table *t)
{
    int i = 0;
    int empty = 0;

    while (i < t->size) {
	if (t->bucket[i].firstFree != 0) {
	    /*printf("Bucket %d used %d\n", i, t->bucket[i].firstFree);*/
	} else {
	    empty++;
	}
	i++;
    }

    printf("Total Buckets : %d\n", t->size);
    printf("Empty Buckets : %d\n", empty);
    printf("Total Entries : %d\n", t->entries);
    printf("Total Data    : %d\n", t->totalData);
    printf("Total Overhead: %d\n", t->overHead);
    printf("Avergage Depth: %f\n", (double)t->entries / (double)t->size);
}

static unsigned int htHashString(char *s)
{
    unsigned int res = 0;

    while (*s)
	res = ((res<<1) + (int)(*(s++)));

    return res;
}

static void *in_table_aux(struct hash_table *t, int hash, char *s)
{
    int x;

    x = 0;
    while (x < t->bucket[hash].firstFree) {
	if (! strcmp(t->bucket[hash].data[x]->key, s)) {
	    return t->bucket[hash].data[x]->userdata;
	}
	x++;
    }
    
    return NULL;
}

void *htInTable(struct hash_table *t, char *key)
{
    int hash;

    hash = htHashString(key) % t->size;
    return in_table_aux(t, hash, key);
}

void htAddToTable(struct hash_table *t, char *key, void *userdata)
{
    int hash;

    hash = htHashString(key) % t->size;
    if (in_table_aux(t, hash, key)) {
	return;
    }

    if (t->bucket[hash].firstFree == t->bucket[hash].allocated) {
	t->bucket[hash].allocated += CHUNK;
	t->bucket[hash].data =
	    realloc(t->bucket[hash].data,
		    t->bucket[hash].allocated * sizeof(struct keypair *));
	/*printf("Bucket %d grew to %d\n", hash, t->bucket[hash].allocated);*/
	t->overHead += sizeof(char *) * CHUNK;
    }
    /*printf("In bucket %d, item %d\n", hash, t->bucket[hash].firstFree);*/
    t->bucket[hash].data[t->bucket[hash].firstFree] = malloc(sizeof(struct keypair));
    t->bucket[hash].data[t->bucket[hash].firstFree]->key = strdup(key);
    t->bucket[hash].data[t->bucket[hash].firstFree++]->userdata = userdata;

    t->totalData += strlen(key) + 1;
    t->entries++;
}

int htNumEntries(struct hash_table *t) {
    return t->entries;
}

void htIterStart(htIterator * iter) {
    iter->bucket = 0;
    iter->item = -1;
}

int htIterGetNext(struct hash_table * t, htIterator * iter, char ** s) {
    iter->item++;
    
    while (iter->bucket < t->size) {
	if (iter->item < t->bucket[iter->bucket].firstFree) {
	    *s = t->bucket[iter->bucket].data[iter->item]->userdata;
	    return 1;
	}

	iter->item++;
	if (iter->item >= t->bucket[iter->bucket].firstFree) {
	    iter->bucket++;
	    iter->item = 0;
	}
    }

    return 0;
}