all_hash.c

fortran并行计算包

/* -*- Mode: C; c-basic-offset:4 ; -*- */
/*
 *  (C) 2001 by Argonne National Laboratory.
 *      See COPYRIGHT in top-level directory.
 */

/*
 * Copyright (c) 2001-2002 The Trustees of Indiana University.
 *                         All rights reserved.
 * Copyright (c) 1998-2001 University of Notre Dame.
 *                         All rights reserved.
 * Copyright (c) 1994-1998 The Ohio State University.
 *                         All rights reserved.
 *
 * Parts of this file were part of the LAM/MPI software package.  For license
 * information, see the LICENSE-LAM file in .. (one directory up).
 *
 *      Software for Humanity
 *      RBD
 *
 *      This program is freely 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.
 *
 *      Original file by Brian Barrett but slightly modified here.
 *
 *      Function:       - generic hash table management code
 *                      - fully dynamic version
 *                      - table entry must have int4 key as first field
 */

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

#include "all_hash.h"
#include "typical.h"

static int is_prime(int4 n);
static int4 next_prime(int4 n);

/*
 *	ah_init
 *
 *	Function:	- create a hash table
 *	Accepts:	- size of hash table
 *			- size of hash table element
 *			- value of the null hash key
 *			- operation mode
 *	Returns:	- ptr to hash table descriptor or NULL
 */
HASH * 
ah_init(int4 size, int4 elemsize, int4 nullkey, int4 mode)
{
	HASH		*ahd;
	int4		i;		/* favourite counter */
	int4		*p;		/* favourite pointer */
	int		temp_errno;	/* temporary errno storage */
/* 
 * Handle the trivial cases.
 * The element must be big enough to hold the int4 key.
 */
	if ( (size <= 0) || (elemsize < sizeof(int4)) ) {
		errno = EINVAL;
		return((HASH *) 0);
	}
/*
 * Allocate the hash table descriptor.
 */
	if ((ahd = (HASH *) malloc(sizeof(HASH))) == 0) {
		return((HASH *) 0);
	}

	ahd->ah_maxnelem = size;
	ahd->ah_elemsize = elemsize;
	ahd->ah_nelem = 0;
	ahd->ah_nullkey = nullkey;
	ahd->ah_mode = mode;
	ahd->ah_cmp = 0;
/*
 * Allocate the hash table array.
 */
	ahd->ah_table = (void *) malloc((uint4) size * elemsize);
	if (ahd->ah_table == 0) {
		temp_errno = errno;
		free((char *) ahd);
		errno = temp_errno;
		return((HASH *) 0);
	}
/*
 * Allocate the table of LRU counters if required.
 */
	if ((mode & AHLRU) == AHLRU) {
		ahd->ah_lru = (int4 *) malloc((uint4) size * sizeof(int4));
		if (ahd->ah_lru == (int4 *) 0) {
			temp_errno = errno;
			free((char *) ahd->ah_table);
			free((char *) ahd);
			errno = temp_errno;
			return((HASH *) 0);
		}
	}
	else {
		ahd->ah_lru = 0;
	}
/*
 * Initialize the hash table if AHNOINIT is not specified.
 * Reset all LRU counters if AHLRU is specified.
 */
	if ((mode & AHNOINIT) != AHNOINIT) {
		for (i = 0, p = (int4 *) ahd->ah_table; i < size; i++) {
			*p = nullkey;
			p = (int4 *) ((char *) p + elemsize);
		}
	}

	if ((mode & AHLRU) == AHLRU) {
		for (i = 0; i < size; i++) {
			ahd->ah_lru[i] = INT4_NIL;
		}
	}

	return(ahd);
}


/*
 *	ah_setcmp
 *
 *	Function:	- set the compare function
 *	Accepts:	- ptr to hash table descriptor
 *			- compare function
 */
void
ah_setcmp(HASH *ahd, int (*cmp)())
{
	ahd->ah_cmp = cmp;
}


/*
 *	ah_free
 *
 *	Function:	- free a hash table
 *			- hash table must have been created with ah_init()
 *	Accepts:	- ptr to hash table descriptor
 */
void
ah_free(HASH *ahd)
{
	if (ahd) {
		if (ahd->ah_table) free((char *) ahd->ah_table);

		if ((ahd->ah_mode & AHLRU) && (ahd->ah_lru)) {
			free((char *) ahd->ah_lru);
		}

		free((char *) ahd);
	}
}

/*
 *	ah_insert
 *
 *	Function:	- insert an element in the given hash table
 *			- the first int4 entry of the element is
 *			  taken to be the hash key
 *	Accepts:	- ptr to hash table descriptor
 *			- ptr to the element
 *	Returns:	- 0 or LAMERROR
 */
int
ah_insert(HASH *ahd, void *elem)
{
	int4		key;		/* element key to hash */
	int4		i;		/* favourite index */
	int4		start;		/* starting index position */
	int4		*p;		/* favourite pointer */

	key = *((int4 *) elem);
	if (key == ahd->ah_nullkey) {
		errno = EINVAL;
		return(LAMERROR);
	}

	start = i = abs(key) % ahd->ah_maxnelem;
/*
 * From that starting point, loop looking for the first empty location.
 */
	do {
		p = (int4 *) ((char *) ahd->ah_table + (i * ahd->ah_elemsize));
		if (*p == ahd->ah_nullkey) {
/*
 * Found an empty slot.  Fill it with the new element.
 * Update the number of elements in the hash table.
 */
			memcpy((char *) p, (char *) elem, ahd->ah_elemsize);
			(ahd->ah_nelem)++;
			return(0);
		}

		i = (i + 1) % ahd->ah_maxnelem;
	} while (i != start);
/* 
 * No empty slots found.
 */
	errno = EFULL;
	return (LAMERROR);
}

/* 
 *  this hash insert will expand if out of slots
 */
int
ah_insert_with_expand(HASH *ahd, void *elem) {

  int result, newsize;
  result = ah_insert(ahd, elem);

  if(errno == EFULL) {
    newsize = ah_size(ahd);
    newsize = next_prime(newsize + newsize);
    if(ah_expand(ahd, newsize))
      return (LAMERROR);
    
    /* try again */
    result = ah_insert(ahd, elem);
  } 

  return result;

}


/*
 *	ah_find
 *
 *	Function:	- find an element in the hash table by key
 *			- increment the LRU counters if they exist
 *	Accepts:	- ptr to hash table descriptor
 *			- key of element to locate
 *	Returns:	- ptr to element or NULL
 */
void *
ah_find(HASH *ahd, int4 key)
{
	int4		i;		/* favourite index */
	int4		start;		/* starting index position */
	int4		*p;		/* favourite pointer */

	if (key == ahd->ah_nullkey) {
		errno = EINVAL;
		return((void *) 0);
	}

	start = i = abs(key) % ahd->ah_maxnelem;
/*
 * From starting point, loop searching for first element having the key. 
 */
	do {
		p = (int4 *) ((char *) ahd->ah_table + (i * ahd->ah_elemsize));
		if (*p == key) {
/*
 * Found an element.  Increment the elements' LRU counter if used and
 * return a pointer to the element.
 */
			if ((ahd->ah_mode & AHLRU) &&
				((ahd->ah_lru)[i] < INT4_MAX)) {
				
				(ahd->ah_lru)[i]++;
			}
			return((void *) p);
		}

		i = (i + 1) % ahd->ah_maxnelem;
	} while (i != start);
/*
 * Not such element was found.
 */
	errno = EINVAL;
	return((void *) 0);
}

/*
 *	ah_find_elm
 *
 *	Function:	- find entry in hash table that compares to element
 *			- the first int4 element entry is the hash key
 *			- uses compare func. to distinguish same-key elements
 *	Accepts:	- ptr to hash table descriptor
 *			- ptr to comparable entry
 *	Returns:	- ptr to element or NULL
 */
void *
ah_find_elem(HASH *ahd, void *celem)
{
	void		*pfirst;	/* ptr first element found */
	void		*p;		/* favourite pointer */
	int		i;		/* favourite index */

	pfirst = ah_find(ahd, *((int4 *) celem));

	if ((pfirst == 0) || (ahd->ah_cmp == 0) ||
			((*(ahd->ah_cmp))(pfirst, celem) == 0)) {
		return(pfirst);
	}
/*
 * The element found doesn't match, though it has the same key.
 * If LRU is enabled, decrement the element's count.
 */
	if (ahd->ah_mode & AHLRU) {
		i = ((int) ((char *) pfirst - (char *) ahd->ah_table)) /
						ahd->ah_elemsize;
		--(ahd->ah_lru)[i];
	}
/*
 * Loop finding the matching element further in the table.
 */
	p = ah_next(ahd, pfirst);
	if (p == 0) p = ah_top(ahd);

	for ( ; p != pfirst; p = ah_next(ahd, p)) {

		if (p == 0) p = ah_top(ahd);
/*
 * If a matching element is found, increment its LRU count if used.
 */
		if ((*(ahd->ah_cmp))(p, celem) == 0) {

			if (ahd->ah_mode & AHLRU) {
				i = ((int) ((char *) p -
					(char *) ahd->ah_table)) /
						ahd->ah_elemsize;
				--(ahd->ah_lru)[i];
			}

			return(p);
		}
	}
/*