NNTPGrab

/* 

 * $Id: linkhash.c,v 1.2 2004/07/21 01:24:33 mclark Exp $

 *

 * Copyright Metaparadigm Pte. Ltd. 2004.

 * Michael Clark 

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public (LGPL)

 * License as published by the Free Software Foundation; either

 * version 2.1 of the License, or (at your option) any later version.

 *

 * This library is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * Lesser General Public License for more details: https://www.gnu.org/

 *

 */

#include 

#include 

#include 

#include 

#include "linkhash.h"

void lh_abort(const char *msg, ...)

{

        va_list ap;

        va_start(ap, msg);

        vprintf(msg, ap);

        exit(1);

}

#pragma GCC diagnostic push

#pragma GCC diagnostic ignored "-Wpointer-to-int-cast"

unsigned long lh_ptr_hash(void *k)

{

        return ((long)k * LH_PRIME) >> 4;

}

#pragma GCC diagnostic pop

int lh_ptr_equal(void *k1, void *k2)

{

        return (k1 == k2);

}

unsigned long lh_char_hash(void *k)

{

        unsigned int h = 0;

        const char* data = k;

        while( *data!=0 ) h = h*129 + (unsigned int)(*data++) + LH_PRIME;

        return h;

}

int lh_char_equal(void *k1, void *k2)

{

        return (strcmp((char*)k1, (char*)k2) == 0);

}

struct lh_table* lh_table_new(int size, char *name,

                              lh_entry_free_fn *free_fn,

                              lh_hash_fn *hash_fn,

                              lh_equal_fn *equal_fn)

{

        int i;

        struct lh_table *t;

        t = calloc(1, sizeof(struct lh_table));

        if(!t) lh_abort("lh_table_new: calloc failed\n");

        t->count = 0;

        t->size = size;

        t->name = name;

        t->table = calloc(size, sizeof(struct lh_entry));

        if(!t->table) lh_abort("lh_table_new: calloc failed\n");

        t->free_fn = free_fn;

        t->hash_fn = hash_fn;

        t->equal_fn = equal_fn;

        for(i = 0; i < size; i++) t->table[i].k = LH_EMPTY;

        return t;

}

struct lh_table* lh_kchar_table_new(int size, char *name,

                                    lh_entry_free_fn *free_fn)

{

        return lh_table_new(size, name, free_fn, lh_char_hash, lh_char_equal);

}

struct lh_table* lh_kptr_table_new(int size, char *name,

                                   lh_entry_free_fn *free_fn)

{

        return lh_table_new(size, name, free_fn, lh_ptr_hash, lh_ptr_equal);

}

void lh_table_resize(struct lh_table *t, int new_size)

{

        struct lh_table *new_t;

        struct lh_entry *ent;

        new_t = lh_table_new(new_size, t->name, NULL, t->hash_fn, t->equal_fn);

        ent = t->head;

        while(ent) {

                lh_table_insert(new_t, ent->k, ent->v);

                ent = ent->next;

        }

        free(t->table);

        t->table = new_t->table;

        t->size = new_size;

        t->head = new_t->head;

        t->tail = new_t->tail;

        t->resizes++;

        free(new_t);

}

void lh_table_free(struct lh_table *t)

{

        struct lh_entry *c;

        for(c = t->head; c != NULL; c = c->next) {

                if(t->free_fn) {

                        t->free_fn(c);

                }

        }

        free(t->table);

        free(t);

}

int lh_table_insert(struct lh_table *t, void *k, void *v)

{

        unsigned long h, n;

        t->inserts++;

        if(t->count > t->size * 0.66) lh_table_resize(t, t->size * 2);

        h = t->hash_fn(k);

        n = h % t->size;

        while( 1 ) {

                if(t->table[n].k == LH_EMPTY || t->table[n].k == LH_FREED) break;

                t->collisions++;

                if(++n == t->size) n = 0;

        }

        t->table[n].k = k;

        t->table[n].v = v;

        t->count++;

        if(t->head == NULL) {

                t->head = t->tail = &t->table[n];

                t->table[n].next = t->table[n].prev = NULL;

        } else {

                t->tail->next = &t->table[n];

                t->table[n].prev = t->tail;

                t->table[n].next = NULL;

                t->tail = &t->table[n];

        }

        return 0;

}

struct lh_entry* lh_table_lookup_entry(struct lh_table *t, void *k)

{

        unsigned long h = t->hash_fn(k);

        unsigned long n = h % t->size;

        t->lookups++;

        while( 1 ) {

                if(t->table[n].k == LH_EMPTY) return NULL;

                if(t->table[n].k != LH_FREED &&

                   t->equal_fn(t->table[n].k, k)) return &t->table[n];

                if(++n == t->size) n = 0;

        }

        return NULL;

}

void* lh_table_lookup(struct lh_table *t, void *k)

{

        struct lh_entry *e = lh_table_lookup_entry(t, k);

        if(e) return e->v;

        return NULL;

}

int lh_table_delete_entry(struct lh_table *t, struct lh_entry *e)

{

        int n = e - t->table;

        if(t->table[n].k == LH_EMPTY || t->table[n].k == LH_FREED) return -1;

        t->count--;

        if(t->free_fn) t->free_fn(e);

        t->table[n].v = NULL;

        t->table[n].k = LH_FREED;

        if(t->tail == &t->table[n] && t->head == &t->table[n]) {

                t->head = t->tail = NULL;

        } else if (t->head == &t->table[n]) {

                t->head->next->prev = NULL;

                t->head = t->head->next;

        } else if (t->tail == &t->table[n]) {

                t->tail->prev->next = NULL;

                t->tail = t->tail->prev;

        } else {

                t->table[n].prev->next = t->table[n].next;

                t->table[n].next->prev = t->table[n].prev;

        }

        t->table[n].next = t->table[n].prev = NULL;

        return 0;

}

int lh_table_delete(struct lh_table *t, void *k)

{

        struct lh_entry *e = lh_table_lookup_entry(t, k);

        if(!e) return -1;

        return lh_table_delete_entry(t, e);

}