oskit/oskit-20020317/linux/fs/hashtab.c

/*
 * Copyright (c) 1997-2000 University of Utah and the Flux Group.
 * All rights reserved.
 * 
 * This file is part of the Flux OSKit.  The OSKit is free software, also known
 * as "open source;" you can redistribute it and/or modify it under the terms
 * of the GNU General Public License (GPL), version 2, as published by the Free
 * Software Foundation (FSF).  To explore alternate licensing terms, contact
 * the University of Utah at csl-dist@cs.utah.edu or +1-801-585-3271.
 * 
 * The OSKit 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 GPL for more details.  You should have
 * received a copy of the GPL along with the OSKit; see the file COPYING.  If
 * not, write to the FSF, 59 Temple Place #330, Boston, MA 02111-1307, USA.
 */

/*
   hashtab.c

   Implementation of a generic hash table type.
*/

#define NULL ((void *) 0)

#include "hashtab.h"
#include <linux/fs.h>
#include <linux/malloc.h>

#define MALLOC(ptr, type, size, d, e) \
	(ptr) = (type) kmalloc((size), GFP_KERNEL)
#define FREE(addr, type) \
	kfree((addr))

#define HASHTAB_DEBUG 0

hashtab_t hashtab_create(unsigned int (*hash_value)(hashtab_key_t key),
		         int (*keycmp)(hashtab_key_t key1, hashtab_key_t key2),
		         unsigned int size)
{
    hashtab_t p;
    int i;


    MALLOC(p, hashtab_t, sizeof(hashtab_val_t), M_TEMP, M_WAITOK);
    if (p == NULL)
	    return p;

    p->size = size;
    p->hash_value = hash_value;
    p->keycmp = keycmp;
    MALLOC(p->htable, hashtab_ptr_t *, sizeof(hashtab_ptr_t)*size, M_TEMP,M_WAITOK);
    if (p->htable == NULL)
    {
	FREE(p, M_TEMP);
	return NULL;
    }

    for (i = 0; i < size; i++)
	    p->htable[i] = (hashtab_ptr_t) NULL;

    return p;
}


int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
{
    int hvalue;
    hashtab_ptr_t current, newnode;


    if (!h)
	    return HASHTAB_OVERFLOW;

    hvalue = h->hash_value(key);
    current = h->htable[hvalue];
    while (current != NULL && h->keycmp(current->key, key) != 0)
	    current = current->next;

    if (current != NULL)
	    return HASHTAB_PRESENT;

    MALLOC(newnode, hashtab_ptr_t, sizeof(struct hashtab_node_t), M_TEMP, M_WAITOK);
    if (newnode == NULL)
	    return HASHTAB_OVERFLOW;
    newnode->key = key;
    newnode->datum = datum;
    newnode->next = h->htable[hvalue];
    h->htable[hvalue] = newnode;
    return HASHTAB_SUCCESS;
}

int hashtab_remove(hashtab_t h, hashtab_key_t key,
		   void (*destroy)(hashtab_key_t, hashtab_datum_t, void *),
		   void *args)
{
    int hvalue;
    hashtab_ptr_t current, last;


    if (!h)
	    return HASHTAB_MISSING;

    hvalue = h->hash_value(key);
    last = NULL;
    current = h->htable[hvalue];
    while (current != NULL && h->keycmp(current->key, key))
    {
	last = current;
	current = current->next;
    }

    if (current == NULL)
	    return HASHTAB_MISSING;

    if (last == NULL)
	    h->htable[hvalue] = current->next;
    else
	    last->next = current->next;

    if (destroy)
	    destroy(current->key,current->datum,args);
    FREE(current, M_TEMP);
    return HASHTAB_SUCCESS;
}

hashtab_datum_t hashtab_search(hashtab_t h, hashtab_key_t key)
{
    int hvalue;
    hashtab_ptr_t current;


    if (!h)
	    return NULL;

    hvalue = h->hash_value(key);
    current = h->htable[hvalue];
    while (current != NULL && h->keycmp(current->key, key))
	    current = current->next;

    if (current == NULL)
	    return NULL;

    return current->datum;
}

void hashtab_destroy(hashtab_t h)
{
    int i;
    hashtab_ptr_t current, temp;


    if (!h)
	    return;

    for (i = 0; i < h->size; i++)
	{
	    current = h->htable[i];
	    while (current != NULL)
	    {
		temp = current;
		current = current->next;
		FREE(temp, M_TEMP);
	    }
	}

    FREE(h->htable, M_TEMP);

    FREE(h, M_TEMP);
}

int hashtab_map(hashtab_t h, int (*f)(hashtab_key_t, hashtab_datum_t,void*), void *p)
{
    int i, ret;
    hashtab_ptr_t current;


    if (!h)
	    return HASHTAB_SUCCESS;

    for (i = 0; i < h->size; i++)
	{
	    current = h->htable[i];
#if HASHTAB_DEBUG
	    if (current != NULL)
		    printf("\nchecking slot %d of %d.\n", i, h->size);
#endif
	    while (current != NULL)
	    {
		ret = f(current->key, current->datum, p);
		if (ret)
			return ret;
		current = current->next;
	    }
	}
    return HASHTAB_SUCCESS;
}

void hashtab_map_remove_on_error(hashtab_t h,
				int (*f)(hashtab_key_t,hashtab_datum_t,void*),
				void (*g)(hashtab_key_t,hashtab_datum_t,void*),
				void *p)
{
    int i, ret;
    hashtab_ptr_t last, current, temp;


    if (!h)
	    return;

    for (i = 0; i < h->size; i++)
	{
	    last = NULL;
	    current = h->htable[i];
#if HASHTAB_DEBUG
	    if (current != NULL)
		    printf("\nchecking slot %d of %d.\n", i, h->size);
#endif
	    while (current != NULL)
	    {
		ret = f(current->key, current->datum, p);
		if (ret)
		{
		    if (last)
		    {
			last->next = current->next;
		    }
		    else
		    {
			h->htable[i] = current->next;
		    }

		    temp = current;
		    current = current->next;
		    g(temp->key, temp->datum, p);
		    FREE(temp, M_TEMP);
		}
		else
		{
		    last = current;
		    current = current->next;
		}
	    }
	}

    return;
}