lhash.cc

这是一款很好用的工具包

/*
 * LHash.cc --
 *	Linear search hash table implementation
 *
 */

#ifndef _LHash_cc_
#define _LHash_cc_

#ifndef lint
static char LHash_Copyright[] = "Copyright (c) 1995-2006 SRI International.  All Rights Reserved.";
static char LHash_RcsId[] = "@(#)$Header: /home/srilm/devel/dstruct/src/RCS/LHash.cc,v 1.49 2006/01/09 18:11:12 stolcke Exp $";
#endif

#include <new>
#include <iostream>
using namespace std;
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "LHash.h"

#undef INSTANTIATE_LHASH
#define INSTANTIATE_LHASH(KeyT, DataT) \
	template <> DataT *LHash< KeyT, DataT >::removedData = 0; \
	template class LHash< KeyT, DataT >; \
	template class LHashIter< KeyT, DataT >

#ifndef __GNUG__
template <class KeyT, class DataT>
DataT *LHash<KeyT,DataT>::removedData = 0;
#endif /* __GNUG__ */

const unsigned minHashBits = 3;		/* minimum no. bits for hashing
					 * tables smaller than this use linear
					 * search to save space */
const float fillRatio = 0.8f;		/* fill ration at which the table is
					 * expanded and rehashed */

#define BODY(b)	((LHashBody<KeyT,DataT> *)b)



static
int (*LHash_thisKeyCompare)(void);		/* used by LHashIter() to communicate
										* with compareIndex() */
static
void *LHash_thisBody;			/* ditto */



/*
 * Dump the entire hash array to cerr.  Unused slots are printed as "FREE".
 */
template <class KeyT, class DataT>
void
LHash<KeyT,DataT>::dump() const
{
    if (body) {
	unsigned maxEntries = hashSize(BODY(body)->maxBits);
	unsigned i;

	for (i = 0; i < maxEntries; i++) {
	    cerr << " " << i << ": ";
	    if (Map_noKeyP(BODY(body)->data[i].key)) {
		cerr << "FREE";
	    } else {
		cerr << BODY(body)->data[i].key
#ifdef DUMP_VALUES
			/* 
			 * Only certain types can be printed.
			 */
		     << "->" << BODY(body)->data[i].value
#endif /* DUMP_VALUES */
		     ;
	    }
	}
    } else {
	cerr << "EMPTY";
    }
    cerr << endl;
}

template <class KeyT, class DataT>
void
LHash<KeyT,DataT>::memStats(MemStats &stats) const
{
    stats.total += sizeof(*this);
    if (body) {
        unsigned maxEntries = hashSize(BODY(body)->maxBits);

	stats.total += sizeof(*BODY(body)) +
			sizeof(BODY(body)->data[0]) *
				(maxEntries - 1);
	stats.wasted += sizeof(BODY(body)->data[0]) *
				(maxEntries - BODY(body)->nEntries);
    }
}

/*
 * Compute the actual minimum size required for a given number of entries
 */
static inline unsigned
roundSize(unsigned size)
{
    if (size < (unsigned)hashSize(minHashBits)) {
	return size;
    } else {
	return (unsigned)((size + 1)/ fillRatio);
    }
}

template <class KeyT, class DataT>
void
LHash<KeyT,DataT>::alloc(unsigned size)
{
    unsigned maxBits, maxEntries;
    unsigned i;

    /*
     * round up to power of two
     */
    maxBits = 0;
    while ((unsigned)(hashSize(maxBits)) < size) {
	assert(maxBits < LHash_maxBitLimit);
	maxBits++;
    }

    maxEntries = hashSize(maxBits);

    //cerr << "LHash::alloc: current " << (body ? BODY(body)->nEntries : 0)
    //	 << ", requested " << size 
    //	 << ", allocating " << maxEntries << " (" << maxBits << ")\n";

    body = (LHashBody<KeyT,DataT> *)malloc(sizeof(*BODY(body)) +
			       (maxEntries - 1) * sizeof(BODY(body)->data[0]));
    assert(body != 0);

    BODY(body)->maxBits = maxBits;
    BODY(body)->nEntries = 0;

    for (i = 0; i < maxEntries; i++) {
	Map_noKey(BODY(body)->data[i].key);
    }
    //cerr << "memory for header = " <<
    //		((void *)&(BODY(body)->data[0]) - (void *)BODY(body)) << endl;
    //cerr << "memory per entry = " <<
    //		((void *)&(BODY(body)->data[3]) - (void *)&(BODY(body)->data[2])) << endl;
}

template <class KeyT, class DataT>
LHash<KeyT,DataT>::LHash(unsigned size)
    : body(0)
{
    if (size != 0) {
	/*
	 * determine actual initial size
	 */
	alloc(roundSize(size));
    }
}

template <class KeyT, class DataT>
void
LHash<KeyT,DataT>::clear(unsigned size)
{
    if (body) {
	unsigned maxEntries = hashSize(BODY(body)->maxBits);
	unsigned i;

	for (i = 0; i < maxEntries; i++) {
	    if (! Map_noKeyP(BODY(body)->data[i].key)) {
		Map_freeKey(BODY(body)->data[i].key);
	    }
	}
	free(body);
	body = 0;
    }
    if (size != 0) {
	alloc(roundSize(size));
    }
}

template <class KeyT, class DataT>
LHash<KeyT,DataT>::~LHash()
{
    clear(0);
}

template <class KeyT, class DataT>
LHash<KeyT,DataT>::LHash(const LHash<KeyT,DataT> &source)
    : body(0)
{
#ifdef DEBUG
    cerr << "warning: LHash copy constructor called\n";
#endif
    *this = source;
}

template <class KeyT, class DataT>
LHash<KeyT,DataT> &
LHash<KeyT,DataT>::operator= (const LHash<KeyT,DataT> &other)
{
#ifdef DEBUG
    cerr << "warning: LHash::operator= called\n";
#endif

    if (&other == this) {
	return *this;
    }

    /*
     * copy hash entries from old to new 
     */
    if (other.body) {
	unsigned maxEntries = hashSize(BODY(other.body)->maxBits);
	/*
	 * ensure we have exactly the same size as source table
	 */
	clear(0);
	alloc(maxEntries);

	for (unsigned i = 0; i < maxEntries; i++) {
	    KeyT thisKey = BODY(other.body)->data[i].key;

	    if (!Map_noKeyP(thisKey)) {
		/*
		 * Copy key
		 */
		BODY(body)->data[i].key = Map_copyKey(thisKey);

		/*
		 * Initialize data, required for = operator
		 */
		new (&(BODY(body)->data[i].value)) DataT;

		/*
		 * Copy data
		 */
		BODY(body)->data[i].value = BODY(other.body)->data[i].value;
	    }
	}
	BODY(body)->nEntries = BODY(other.body)->nEntries;
    } else {
	clear(0);
    }

    return *this;
}

/*
 * Returns index into data array that has the key which is either
 * equal to key, or indicates the place where key would be placed if it
 * occurred in the array.
 */
template <class KeyT, class DataT>
Boolean
LHash<KeyT,DataT>::locate(KeyT key, unsigned &index) const
{
    assert(!Map_noKeyP(key));

    if (body) {
	unsigned maxBits = BODY(body)->maxBits;
    	register MapEntry<KeyT,DataT> *data = BODY(body)->data;

	if (maxBits < minHashBits) {
	    /*
	     * Do a linear search
	     */
	    unsigned nEntries = BODY(body)->nEntries;
	    register unsigned i;

	    for (i = 0; i < nEntries; i++) {
		if (LHash_equalKey(data[i].key, key)) {
		    index = i;
		    return true;
		}
	    }
	    index = i;
	    return false;
	} else {
	    /*
	     * Do a hashed search
	     */
	    unsigned hash = LHash_hashKey(key, maxBits);
	    unsigned i; 

	    for (i = hash; ; i = (i + 1) & hashMask(maxBits))
	    {
		if (Map_noKeyP(data[i].key)) {
		    index = i;
		    return false;
		} else if (LHash_equalKey(data[i].key, key)) {
		    index = i;
		    return true;
		}
	    }
	}
    } else {
	return false;
    }
}

template <class KeyT, class DataT>
DataT *
LHash<KeyT,DataT>::find(KeyT key, Boolean &foundP) const
{
    unsigned index;

    if (foundP = locate(key, index)) {
	return &(BODY(body)->data[index].value);
    } else {
	return 0;
    }
}

template <class KeyT, class DataT>
KeyT
LHash<KeyT,DataT>::getInternalKey(KeyT key, Boolean &foundP) const
{
    unsigned index;
    static KeyT zeroKey;

    if (foundP = locate(key, index)) {
	return BODY(body)->data[index].key;
    } else {
	return zeroKey;
    }
}

template <class KeyT, class DataT>
DataT *
LHash<KeyT,DataT>::insert(KeyT key, Boolean &foundP)
{
    unsigned index;

    assert(!(Map_noKeyP(key)));

    /*
     * Make sure there is room for at least one entry
     */