lhash.cc

这是一款很好用的工具包

    if (body == 0) {
	alloc(1);
    }

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

	/*
	 * Rehash table if necessary
	 */
	unsigned minSize = roundSize(nEntries + 1);

	if (minSize > maxEntries) {
	    LHashBody<KeyT,DataT> *oldBody = BODY(body);
	    unsigned i;

	    /*
	     * Since LHash_maxEntriesLimit is a power of two minus 1
	     * we need to check this only when the array is enlarged
	     */
	    assert(nEntries < LHash_maxEntriesLimit);

	    alloc(minSize);
	    BODY(body)->nEntries = nEntries;

	    if (BODY(body)->maxBits < minHashBits) {
		/*
		 * Just copy old entries to new storage, no reindexing
		 * required.
		 */
		memcpy(BODY(body)->data, oldBody->data,
			sizeof(oldBody->data[0]) * nEntries);
	    } else {
		/*
		 * Rehash
		 */
		for (i = 0; i < maxEntries; i++) {
		    KeyT key = oldBody->data[i].key;

		    if (! Map_noKeyP(key)) {
			(void)locate(key, index);
			memcpy(&(BODY(body)->data[index]), &(oldBody->data[i]),
							sizeof(oldBody->data[0]));
		    }
		}
	    }
	    free(oldBody);

	    /*
	     * Entries have been moved, so have to re-locate key
	     */
	    (void)locate(key, index);
	}

	BODY(body)->data[index].key = Map_copyKey(key);

	/*
	 * Initialize data to zero, but also call constructors, if any
	 */
	memset(&(BODY(body)->data[index].value), 0,
			sizeof(BODY(body)->data[index].value));
	new (&(BODY(body)->data[index].value)) DataT;

	BODY(body)->nEntries++;

	return &(BODY(body)->data[index].value);
    }
}

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

    /*
     * Allocate pseudo-static memory for removed objects (returned by
     * remove()). We cannot make this static because otherwise 
     * the destructor for DataT would be called on it at program exit.
     */
    if (removedData == 0) {
	removedData = (DataT *)malloc(sizeof(DataT));
	assert(removedData != 0);
    }

    if (foundP = locate(key, index)) {
	Map_freeKey(BODY(body)->data[index].key);
	Map_noKey(BODY(body)->data[index].key);
	memcpy(removedData, &BODY(body)->data[index].value, sizeof(DataT));

	if (BODY(body)->maxBits < minHashBits) {
	    /*
	     * Linear search mode -- Just move all entries above the
	     * the one removed to fill the gap.
	     */
	    unsigned nEntries = BODY(body)->nEntries;

	    memmove(&BODY(body)->data[index],
		    &BODY(body)->data[index+1],
		    (nEntries - index - 1) * sizeof(BODY(body)->data[0]));
	    Map_noKey(BODY(body)->data[nEntries - 1].key);
	} else {
	    /*
	     * The entry after the one being deleted could actually
	     * belong to a prior spot in the table, but was bounced forward due
	     * to a collision.   The invariant used in lookup is that
	     * all locations between the hash index and the actual index are
	     * filled.  Hence we examine all entries between the deleted
	     * position and the next free position as whether they need to
	     * be moved backward.
	     */
	    while (1) {
		unsigned newIndex;

		index = (index + 1) & hashMask(BODY(body)->maxBits);

		if (Map_noKeyP(BODY(body)->data[index].key)) {
		    break;
		}

		/* 
		 * If find returns false that means the deletion has
		 * introduced a hole in the table that would prevent
		 * us from finding the next entry. Luckily, find 
		 * also tells us where the hole is.  We move the 
		 * entry to its rightful place and continue filling
		 * the hole created by this move.
		 */
		if (!locate(BODY(body)->data[index].key, newIndex)) {
		    memcpy(&(BODY(body)->data[newIndex]),
			   &(BODY(body)->data[index]),
			   sizeof(BODY(body)->data[0]));
		    Map_noKey(BODY(body)->data[index].key);
		}
	    }
	}
	BODY(body)->nEntries--;
	return removedData;
    } else {
	return 0;
    }
}


template <class KeyT, class DataT>
void
LHashIter<KeyT,DataT>::sortKeys()
{
    /*
     * Store keys away and sort them to the user's orders.
     */
    unsigned maxEntries = hashSize(myLHashBody->maxBits);

    unsigned *sortedIndex = new unsigned[numEntries];
    assert(sortedIndex != 0);

    unsigned i;

    unsigned j = 0;
    for (i = 0; i < maxEntries; i++) {
	if (!Map_noKeyP(myLHashBody->data[i].key)) {
	    sortedIndex[j++] = i;
	}
    }
    assert(j == numEntries);

    /*
     * Due to the limitations of the qsort interface we have to 
     * pass extra information to compareIndex in these global
     * variables - yuck. 
     */
    LHash_thisKeyCompare = (int(*)())sortFunction;
    LHash_thisBody = myLHashBody;
    qsort(sortedIndex, numEntries, sizeof(*sortedIndex), compareIndex);

    /*
     * Save the keys for enumeration.  The reason we save the keys,
     * not the indices, is that indices may change during enumeration
     * due to deletions.
     */
    sortedKeys = new KeyT[numEntries];
    assert(sortedKeys != 0);

    for (i = 0; i < numEntries; i++) {
	sortedKeys[i] = myLHashBody->data[sortedIndex[i]].key;
    }

    delete [] sortedIndex;
}

template <class KeyT, class DataT>
LHashIter<KeyT,DataT>::LHashIter(const LHash<KeyT,DataT> &lhash,
				    int (*keyCompare)(KeyT, KeyT))
    : myLHashBody(BODY(lhash.body)), current(0),
      numEntries(lhash.numEntries()), sortFunction(keyCompare)
{
    /*
     * Note: we access the underlying LHash through the body pointer,
     * not the top-level LHash itself.  This allows the top-level object
     * to be moved without affecting an ongoing iteration.
     * XXX: This only works because
     * - it is illegal to insert while iterating
     * - deletions don't cause reallocation of the data
     */
    if (sortFunction && myLHashBody) {
	sortKeys();
    } else {
	sortedKeys = 0;
    }
}

/*
 * This is the callback function passed to qsort for comparing array
 * entries. It is passed the indices into the data array, which are
 * compared according to the user-supplied function applied to the 
 * keys found at those locations.
 */
template <class KeyT, class DataT>
int
LHashIter<KeyT,DataT>::compareIndex(const void *idx1, const void *idx2)
{
    return (*(compFnType)LHash_thisKeyCompare)
		    (BODY(LHash_thisBody)->data[*(unsigned *)idx1].key,
		     BODY(LHash_thisBody)->data[*(unsigned *)idx2].key);
}

template <class KeyT, class DataT>
LHashIter<KeyT,DataT>::~LHashIter()
{
    delete [] sortedKeys;
}


template <class KeyT, class DataT>
void 
LHashIter<KeyT,DataT>::init()
{
    delete [] sortedKeys;

    current = 0;

    {
	/*
	 * XXX: fake LHash object to access numEntries()
	 */
	LHash<KeyT,DataT> myLHash(0);

	myLHash.body = myLHashBody;
	numEntries = myLHash.numEntries();
	myLHash.body = 0;
    }

    if (sortFunction && myLHashBody) {
	sortKeys();
    } else {
	sortedKeys = 0;
    }
}

template <class KeyT, class DataT>
DataT *
LHashIter<KeyT,DataT>::next(KeyT &key)
{

    if (myLHashBody == 0) {
	return 0;
    } else {
	unsigned index;

	if (sortedKeys) {
	    /*
	     * Sorted enumeration -- advance to next key in sorted list
	     */
	    if (current == numEntries) {
		return 0;
	    }

	    /*
	     * XXX: fake LHash object to access locate()
	     */
	    LHash<KeyT,DataT> myLHash(0);

	    myLHash.body = myLHashBody;
	    myLHash.locate(sortedKeys[current++], index);
	    myLHash.body = 0;;
	} else {
	    /*
	     * Detect deletions by comparing old and current number of 
	     * entries.
	     * A legal deletion can only affect the current entry, so
	     * adjust the current position to reflect the next entry was
	     * moved.
	     */
	    if (myLHashBody->nEntries != numEntries) {
		assert(myLHashBody->nEntries == numEntries - 1);

		numEntries --;
		current --;
	    }

	    /*
	     * Random enumeration mode
	     */
	    unsigned maxBits = myLHashBody->maxBits;

	    if (maxBits < minHashBits) {
		/*
		 * Linear search mode - advance one to the next entry
		 */
		if (current == numEntries) {
		    return 0;
		}
	    } else {
		unsigned maxEntries = hashSize(maxBits);

		while (current < maxEntries &&
		       Map_noKeyP(myLHashBody->data[current].key))
		{
		    current++;
		}

		if (current == maxEntries) {
		    return 0;
		}
	    }

	    index = current ++;
	}

	key = myLHashBody->data[index].key;
	return &(myLHashBody->data[index].value);
    }
}

#undef BODY

#endif /* _LHash_cc_ */