hashtable.c

mobile ip 在linux下的一种实现

/* $Id: hashtable.c,v 1.27 2000/04/06 07:26:53 jm Exp $
 * This file defines the interface of hashtable.
 *
 * Dynamic hierarchial IP tunnel
 * Copyright (C) 1998-2000, Dynamics group
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation. See README and COPYING for
 * more details.
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "owntypes.h"
#include "hashtable.h"
#include "list.h"
#include "debug.h"

/* defines */

#ifndef TRUE
#define TRUE 1
#endif

#ifndef FALSE
#define FALSE 0
#endif

#define DEBUG_FLAG 'h'

#define ASSERT assert

/* Test cases */

/* #define HASHTABLE_TEST_CASE_M03 */

/* NOTE! The internal structure of the hashtable is an array that has
 * pointers to collision lists. */

/*
 * The idea is to give a freedom to use any hashfunction.
 *
 * We do not make any assumptions about the data to be added, but as
 * this module is using the list module to store the values, the
 * pointer must point to a node structure. Read more information about
 * how to use the nodes and lists from the list module.
 *
 * All the hashtable module functions begin with the word 'hashtable_'.
 */

/* "Ixx" are test case IDs to help in the design of the test module */

/* hashtable_init allocates the memory for the structures and lists.
 * It also initializes the lists.
 *
 * INPUT VALUES:
 *
 * M01) size is zero
 * M02) size is negative
 * M03) not enough memory for struct hashtable
 *      - requires changes in code, will be tested manually
 * M04) size is too large for malloc to succeed (not enough memory)
 * M05) realistic values
 *
 */

/**
 * hashtable_init:
 * @size: size of the table
 * 
 * Allocate the memory for the structures and lists.
 * It also initializes the lists.
 * 
 * Returns: Pointer to table, or NULL if failed
 */
struct hashtable *hashtable_init(int size)
{
	int i;
	struct hashtable *table;

	DEBUG(DEBUG_FLAG, "Initializing hashtable!\n");
	if (size < 1) {
		fprintf(stderr, "hashtable_init: Size must be at least 1\n");
		return NULL;
	}
#ifdef HASHTABLE_TEST_CASE_M03
	table = malloc((unsigned int) -1);
#else
	table = malloc(sizeof(struct hashtable)); 
#endif
	if (table == NULL) {
		fprintf(stderr, "hashtable_init: Not enough memory!\n");
		return NULL;
	}

	/* Initialize the array and lists. */

	table->hasharray = malloc(sizeof(struct list) * size);
	if (table->hasharray == NULL) {
		fprintf(stderr,
			"hashtable_init: Not enough memory for hasharray!\n");
		free(table);
		return NULL;
	}

	DEBUG(DEBUG_FLAG, "hashtable_init: Initializing collision lists.\n");
	for (i = 0; i < size; i++) {
		list_init(&table->hasharray[i]);
	}

	table->hashtablesize = size;
	ASSERT(table->hashtablesize == size);
	return table;
}

/*
 * INPUT VALUES:
 *
 * M06) table is not empty
 * M07) table is empty
 *    ) table is NULL
 *
 */
/**
 * hashtable_destroy:
 * @table: 
 * 
 * The user should remove all nodes before destroying the hash table object.
 * This can't do it, because it has no way to know how the memory was
 * allocated to the entry. This removed the entries from the list and returns
 * FALSE as a warning that there was something in the hashtable.
 * Even though FALSE is returned, it's just a warning and the hashtable has
 * already been destroyed.
 *
 * We start destroying the hashtable from inside:
 * - the list nodes
 * - the hasharray
 * - the hashtable structure
 *
 * Returns: 
 */
int hashtable_destroy(struct hashtable *table)
{
	int i, status;

	DEBUG(DEBUG_FLAG, "hashtable_destroy: Destroying hashtable!\n");
	ASSERT(table != NULL);
	status = TRUE;
	for (i = 0; i < table->hashtablesize; i++) {
		while(list_remove_first(&table->hasharray[i]) != NULL) {
			fprintf(stderr,
				"hashtable_destroy: Warning! Removing node "
				"from list at index %d\n", i);
			status = FALSE;
		}
	}
	free(table->hasharray);
	free(table);
	return status;
}

/* INPUT VALUES:
 *
 * M08) hash function is invalid
 * M09) hash function is valid
 *    ) table is NULL
 *    ) hashfunc is NULL
 *    ) entry is NULL
 *
 */
/**
 * hashtable_add:
 * @table: pointer to the hashtable structure 
 * @hashfunc: function that returns the hash value
 * @key: key input to the hash function
 * @entry: node to be added to the list
 *
 * Add entry to hash table.
 * Care must be taken that the same node isn't added twice! 
 *
 * Returns: TRUE if completed successfully, otherwise FALSE
 */
int hashtable_add(struct hashtable *table,
		  int (*hashfunc)(void *key, const int hashsize),
		  void *key,
		  struct node *entry)
{
	int hashvalue;

	DEBUG(DEBUG_FLAG,
	      "hashtable_add: Adding entry to the hashtable.\n");
	ASSERT(table != NULL);
	ASSERT(hashfunc != NULL);
	ASSERT(entry != NULL);
	hashvalue = (*hashfunc)(key, table->hashtablesize);
	if (hashvalue < 0 || hashvalue >= table->hashtablesize) {
		fprintf(stderr,
			"hashtable_add: invalid hash function, "
			"returned %d that is out of the range [0,%d]\n",
			hashvalue, table->hashtablesize - 1);
		return FALSE;
	}
	list_add_tail(&table->hasharray[hashvalue], entry);
	return TRUE;
}


/* INPUT VALUES:
 *
 * M10) hash function is invalid
 * M11) node is found
 * M12) node is not found
 *    ) table is NULL
 *    ) hashfunc is NULL
 *    ) cmpfunc is NULL
 *    ) cmpfunc is invalid
 *
 */
/**
 * hashtable_fetch:
 * @table:
 * @hashfunc:
 * @key:
 * @cmpfunc:
 *
 * Fetch entry from hashtable.
 *
 * Returns: A pointer to the found nodem or NULL if nothing is found.
 */
struct node *hashtable_fetch(struct hashtable *table,
			     int (*hashfunc)(void *key, const int hashsize),
			     void *key,
			     int (*cmpfunc)(void *key, struct node *cmprd))
{
	int hashvalue;
	struct node *node;

	ASSERT(table != NULL);
	ASSERT(hashfunc != NULL);
	ASSERT(cmpfunc != NULL);
	hashvalue = (*hashfunc)(key, table->hashtablesize);
	if (hashvalue < 0 || hashvalue >= table->hashtablesize) {
		fprintf(stderr,
			"hashtable_fetch: invalid hash function, "
			"returned %d that is out of range [0,%d]\n",
			hashvalue, table->hashtablesize - 1);
		return NULL;
	}
	node = list_get_first(&table->hasharray[hashvalue]);
	while(node != NULL) {
		if ((*cmpfunc)(key, node) == TRUE) break;
		node = list_get_next(node);
	}
	return node;
}


/* INPUT VALUES:
 *
 * M13) entry is valid
 *    ) entry is NULL
 *    ) entry is invalid (cannot be checked)
 *
 */
/**
 * hashtable_remove:
 * @entry:
 * 
 * Remove entry from hashtable
 */
void hashtable_remove(struct node *entry)
{
	ASSERT(entry != NULL);
	list_remove(entry);
}


/* INPUT VALUES:
 *
 * M14) entry is found
 * M15) entry is not found
 *    ) table is NULL
 *    ) entry is NULL
 *    ) entry is invalid (cannot be checked)
 *
 */

/**
 * hashtable_find_and_remove:
 * @table:
 * @hashfunc:
 * @key:
 * @cmpfunc:
 *
 * Find and remove entry from hashtable.
 * 
 * Returns: TRUE if entry is found, else FALSE
 */
int hashtable_find_and_remove(struct hashtable *table,
			      int (*hashfunc)(void *key, const int hashsize),
			      void *key,
			      int (*cmpfunc)(void *key, struct node *cmprd))
{
	struct node *node;

	ASSERT(table != NULL);
	ASSERT(hashfunc != NULL);
	ASSERT(cmpfunc != NULL);
	node = hashtable_fetch(table, hashfunc, key, cmpfunc);
	if (node == NULL) return FALSE;
	list_remove(node);
	return TRUE;
}

/*
 * INPUT VALUES:
 *
 * iterator function returning TRUE:
 * M16) hashtable is empty
 * M17) hashtable is not empty
 * M18) hashtable is not empty and remove nodes in iterfunc
 * iterator function returning FALSE:
 * M19) hashtable is empty
 * M20) hashtable is not empty
 * M21) hashtable is not empty and remove nodes in iterfunc
 * M28) verify that data is passed to iterfunc
 *    ) table is NULL
 *    ) iterfunc is NULL
 *
 */

/**
 * hashtable_iterator:
 * @table:
 * @iterfunc:
 * @data:
 *
 * Go through every entry in the hashtable until the iterator function returns
 * FALSE or the hashtable has no more entries.
 * Data is passed to @iterfunc to allow any user-specified data to be used
 * in that function.
 *
 * Returns: TRUE if the iteration was not stopped by iterator function
 * and FALSE if it was stopped.
 */ 
int hashtable_iterator(struct hashtable *table,
		       int (*iterfunc)(struct node *node, void *data),
		       void *data)
{
	int i;
	struct node *node, *next;

	for (i = 0; i < table->hashtablesize; i++) {
		node = list_get_first(&table->hasharray[i]);
		while (node != NULL) {
			next = list_get_next(node);
			if ((*iterfunc)(node, data) != TRUE) {
				return FALSE;
			}
			node = next;
		}
	}
	return TRUE;
}


/* Can't be used to get larger primes than about 2^30.
 *
 * M22) n is less than zero
 * M23) n is zero
 * M24) n is 1, 2 or 3
 * M25) n is prime
 * M26) n is not prime
 * M27) n is large (2^30 + 10)
 *
 */

/**
 * hashtable_find_prime:
 * @n: prime starting point
 * 
 * Find a prime that is next higher (or equal) to the given starting point @n.
 * Can't be used to get larger primes than about 2^30.
 * 
 * Returns: the prime or zero on failure.
 */
int hashtable_find_prime(int n)
{
	int i;

	if (n <= 0) {
		fprintf(stderr,
			"hashtable_find_prime: starting value must be higher "
			"than one (was %d)\n",
                        n);
		return 0;
	}
	if (n == 1) return 2;
	if (n <= 3) return n;
	if ( (n & 1) == 0) n++;
	for(;;) {
		
		if (n > 1 << 29) break; /* make sure int won't be overflown */
		i = 2;
		while(n % i != 0) {
			if (i * i > n) return n;
			i++;
		}
		n += 2;
	}
	fprintf(stderr,
		"hashtable_find_prime: value of n is too high\n");
	return 0;
}