source: trunk/third/rpm/python/hash.c @ 17931

/** \ingroup python
 * \file python/hash.c
 */

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

#include "hash.h"

#define CHUNK 1

struct filePath {
    char * dir;
    char * base;
} ;

struct bucket {
    struct filePath * data;
    int allocated;
    int firstFree; /* as in data[firstFree] */
};

struct hash_table {
    int size;
    int entries;
    int overHead;
    struct bucket *bucket;
};

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->entries = 0;
    res->overHead = sizeof(struct bucket) * size + CHUNK * sizeof(char *);

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

void htFreeHashTable(struct hash_table *ht)
{
    struct bucket * b;
    int item;

    b = ht->bucket;
    while (ht->size--) {
        for (item = 0; item < b->firstFree; item++) {
            free(b->data[item].dir);
            free(b->data[item].base);
        }
        free(b->data);
        b++;
    }
    free(ht->bucket);
    free(ht);
}

void htHashStats(const 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 Overhead: %d\n", t->overHead);
    printf("Avergage Depth: %f\n", (double)t->entries / (double)t->size);
}

static unsigned int htHashStrings(const char * s, const char * t)
{
    unsigned int res = 0;

    while (*s != '\0')
        res = ((res<<1) + (int)(*(s++)));
    while (*t != '\0')
        res = ((res<<1) + (int)(*(t++)));

    return res;
}

/* returns bucket # containing item, or -1 */
static int in_table_aux(struct hash_table *t, int hash, const char * dir, 
                        const char * base)
{
    int x;

    x = 0;
    while (x < t->bucket[hash].firstFree) {
        if (! strcmp(t->bucket[hash].data[x].dir, dir) &&
            ! strcmp(t->bucket[hash].data[x].base, base)) {
            return x;
        }
        x++;
    }
    
    return -1;
}

int htInTable(struct hash_table *t,  const char * dir, const char * base)
{
    int hash;

    hash = htHashStrings(dir, base) % t->size;

    if (in_table_aux(t, hash, dir, base) == -1)
        return 0;
    return 1;
}

void htAddToTable(struct hash_table *t, const char * dir, const char * base)
{
    static int hash = 1;

    if (!dir || !base)
        return;
    
    hash = htHashStrings(dir, base) % t->size;
    if (in_table_aux(t, hash, dir, base) != -1)
        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(*(t->bucket->data)));
        /*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].dir = strdup(dir);
    t->bucket[hash].data[t->bucket[hash].firstFree++].base = strdup(base);
    t->entries++;
}

void htRemoveFromTable(struct hash_table *t, const char * dir, 
                       const char * base) {
    int hash;
    int item;
    int last;

    hash = htHashStrings(dir, base) % t->size;
    if ((item = in_table_aux(t, hash, dir, base)) == -1) {
        return;
    }

    free(t->bucket[hash].data[item].dir);
    free(t->bucket[hash].data[item].base);

    last = --t->bucket[hash].firstFree;
    t->bucket[hash].data[item] = t->bucket[hash].data[last];
}

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, 
                  const char ** dir, const char ** base) {
    iter->item++;
    
    while (iter->bucket < t->size) {
        if (iter->item < t->bucket[iter->bucket].firstFree) {
            *dir = t->bucket[iter->bucket].data[iter->item].dir;
            *base = t->bucket[iter->bucket].data[iter->item].base;

            return 1;
        }

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

    return 0;
}