/*
 * hash.cpp -- skeleton (chained) hash table code
 *  (c) 2001-2002        Murat Deligonul
 *
 ***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ****************************************************************************/

#include "autoconf.h"

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

#include "debug.h"
#include "hash.h"

__htbl::__htbl(int buckets)
{
    this->buckets = buckets;
    size = 0;
    lookups = hits = 0;

    table = new struct hashlist[buckets];
    assert(table);
    memset(table, 0, sizeof(struct hashlist) * buckets);

    DEBUG("Initialized hash table %p with %d buckets\n", this, buckets);
}


__htbl::~__htbl(void)
{
    for (int i = 0; i < buckets; i++)
        list_destroy(&table[i]);
    delete[] table;
}


int __htbl::list_add(struct hashlist * h, void * data)
{
    if (!h->head)
    {
        h->head = new node;
        h->head->data = data;
        h->head->next = 0;
        h->size++;
    } else {
        struct node * n;
        for (n = h->head; n->next ; n = n->next)
            ;
        n->next = new node;
        n->next->data = data;
        n->next->next = 0;
        h->size++;
    }

    return 1;
}

int __htbl::list_remove(struct hashlist * h, void * data)
{
    struct node * n = h->head;
    if (n->data == data)
    {
        h->head = n->next;
        delete n;
        h->size --;
        return 1;
    }

    for (; n; n = n->next)
    {
        if (n->next && n->next->data == data)
        {
            n->next = n->next->next;
            break;
            delete n->next;
            h->size--;
            return 1;
        }
    }
    return 0;
}

int __htbl::list_destroy(struct hashlist * h)
{
    struct node * n = h->head, * n2;
    while (n)
    {
        n2 = n->next;
        delete n;
        n = n2;
    }
    h->head = 0;
    h->size = 0;
    return 1;
}

/* Stolen from an O'reilly book */
int hash(const char *key)
{
    const char *ptr;
    int val;

    val = 0;
    ptr = key;

    while (*ptr != '\0') {
       int tmp;
       val = (val << 4) + (*ptr);

       if ((tmp = (val & 0xf0000000))) {
          val = val ^ (tmp >> 24);
          val = val ^ tmp;
       }
       ptr++;
    }

    return abs(val);
}

int __htbl::stat(struct __htbl::hash_stat_t * ht)
{
    assert(ht);
    ht->buckets = buckets;
    ht->hits = hits;
    ht->lookups = lookups;

    /* Now figure how big the buckets are */
    for (int n = 0; n < buckets; n++)
    {
        if (table[n].size < 5)
            ht->sizes[table[n].size]++;
        else if (table[n].size > 4)
            ht->sizes[4]++;
    }

    ht->size = ht->sizes[1] + ht->sizes[2] + ht->sizes[3] + ht->sizes[4];
    return 1;
}