Logo Search packages:      
Sourcecode: libkarma version File versions  Download package

hash.c

/*
 * libkarma/hash.c
 *
 * Copyright (c) Michael R. Elkins <me@mutt.org> 1996-2000
 *           (c) Frank Zschockelt <libkarma@freakysoft.de> 2004
 *
 * You may distribute and modify this program under the terms of 
 * the GNU GPL, version 2 or later.
 *
 */

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

#include "hash.h"

#define SOMEPRIME 149711

#define STRCMP(a,b) strcmp(a?a:"", b?b:"")

int hash_string(const unsigned char *s, int n)
{
    int h = 0;

    while(*s)
        h += (h << 7) + *s++;
    h = (h * SOMEPRIME) % n;
    h = (h >= 0) ? h : h + n;

    return (h % n);
}

HASH *hash_create(int nelem)
{
    HASH *table = malloc(sizeof(HASH));
    if(nelem == 0)
        nelem = 2;
    table->nelem = nelem;
    table->table = calloc(nelem, sizeof(struct hash_elem *));
    return table;
}

int hash_count(HASH * table)
{
    int count, i;
    struct hash_elem *tmp;

    for (i = 0, count = 0; i < table->nelem; i++) {
        tmp = table->table[i];
        while(tmp) {
            tmp = tmp->next;
            count++;
        }
    }
    return count;
}

void hash_iterate(HASH * table, int index, const char **key, void **data)
{
    int i;
    struct hash_elem *tmp = NULL;

    i = 0;
    while(index) {
        tmp = table->table[i];
        while(tmp && --index)
            tmp = tmp->next;
        i++;
    }
    *key = tmp->key;
    *data = tmp->data;
}

void hash_walker(HASH * table, void (*fn) (const char *key, void *data))
{
    int i;
    struct hash_elem *tmp;

    for (i = 0; i < table->nelem; i++) {
        tmp = table->table[i];
        while(tmp) {
            fn(tmp->key, tmp->data);
            tmp = tmp->next;
        }
    }
}

/* table        hash table to update
 * key          key to hash on
 * data         data to associate with `key'
 */
int hash_insert(HASH * table, const char *key, void *data)
{
    struct hash_elem *ptr;
    int h;
    struct hash_elem *tmp, *last;
    int r;

    ptr = (struct hash_elem *)malloc(sizeof(struct hash_elem));
    h = hash_string((unsigned char *)key, table->nelem);
    ptr->key = key;
    ptr->data = data;

    for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next) {
        r = STRCMP(tmp->key, key);
        if(r == 0) {
            free(tmp->data);
            tmp->data = ptr->data;
            free((char *)tmp->key);
            tmp->key = ptr->key;
            free(ptr);
            return h;
        }
        if(r > 0)
            break;
    }
    if(last)
        last->next = ptr;
    else
        table->table[h] = ptr;
    ptr->next = tmp;
    return h;
}

void *hash_find_hash(const HASH * table, int hash, const char *key)
{
    struct hash_elem *ptr = table->table[hash];
    for (; ptr; ptr = ptr->next) {
        if(STRCMP(key, ptr->key) == 0)
            return ptr->data;
    }
    return NULL;
}

void hash_delete_hash(HASH * table, int hash, const char *key, const void *data)
{
    struct hash_elem *ptr = table->table[hash];
    struct hash_elem **last = &table->table[hash];

    for (; ptr; last = &ptr->next, ptr = ptr->next) {
        /* if `data' is given, look for a matching ->data member.
         * This is required for the case where we have multiple
         * entries with the same key
         */
        if((data == ptr->data) || (!data && STRCMP(ptr->key, key) == 0)) {
            *last = ptr->next;
            free((char *)ptr->key);
            free(ptr->data);
            free(ptr);
            return;
        }
    }
}

/* ptr        pointer to the hash table to be freed
 */
void hash_destroy(HASH ** ptr)
{
    int i;
    HASH *pptr = *ptr;
    struct hash_elem *elem, *tmp;

    for (i = 0; i < pptr->nelem; i++) {
        for (elem = pptr->table[i]; elem;) {
            tmp = elem;
            elem = elem->next;
            free((char *)tmp->key);
            free(tmp->data);
            free(tmp);
        }
    }
    free(pptr->table);
    free(*ptr);
}

Generated by  Doxygen 1.6.0   Back to index