dynahash.c

关系型数据库 Postgresql 6.5.2

		bucket = bucket & hctl->low_mask;

	return bucket;
}

/*
 * hash_search -- look up key in table and perform action
 *
 * action is one of HASH_FIND/HASH_ENTER/HASH_REMOVE
 *
 * RETURNS: NULL if table is corrupted, a pointer to the element
 *		found/removed/entered if applicable, TRUE otherwise.
 *		foundPtr is TRUE if we found an element in the table
 *		(FALSE if we entered one).
 */
long *
hash_search(HTAB *hashp,
			char *keyPtr,
			HASHACTION action,	/* HASH_FIND / HASH_ENTER / HASH_REMOVE
								 * HASH_FIND_SAVE / HASH_REMOVE_SAVED */
			bool *foundPtr)
{
	uint32		bucket;
	long		segment_num;
	long		segment_ndx;
	SEGMENT		segp;
	ELEMENT    *curr;
	HHDR	   *hctl;
	BUCKET_INDEX currIndex;
	BUCKET_INDEX *prevIndexPtr;
	char	   *destAddr;
	static struct State
	{
		ELEMENT    *currElem;
		BUCKET_INDEX currIndex;
		BUCKET_INDEX *prevIndex;
	}			saveState;

	Assert((hashp && keyPtr));
	Assert((action == HASH_FIND) || (action == HASH_REMOVE) || (action == HASH_ENTER) || (action == HASH_FIND_SAVE) || (action == HASH_REMOVE_SAVED));

	hctl = hashp->hctl;

#if HASH_STATISTICS
	hash_accesses++;
	hashp->hctl->accesses++;
#endif
	if (action == HASH_REMOVE_SAVED)
	{
		curr = saveState.currElem;
		currIndex = saveState.currIndex;
		prevIndexPtr = saveState.prevIndex;

		/*
		 * Try to catch subsequent errors
		 */
		Assert(saveState.currElem && !(saveState.currElem = 0));
	}
	else
	{
		bucket = call_hash(hashp, keyPtr);
		segment_num = bucket >> hctl->sshift;
		segment_ndx = MOD(bucket, hctl->ssize);

		segp = GET_SEG(hashp, segment_num);

		Assert(segp);

		prevIndexPtr = &segp[segment_ndx];
		currIndex = *prevIndexPtr;

		/*
		 * Follow collision chain
		 */
		for (curr = NULL; currIndex != INVALID_INDEX;)
		{
			/* coerce bucket index into a pointer */
			curr = GET_BUCKET(hashp, currIndex);

			if (!memcmp((char *) &(curr->key), keyPtr, hctl->keysize))
				break;
			prevIndexPtr = &(curr->next);
			currIndex = *prevIndexPtr;
#if HASH_STATISTICS
			hash_collisions++;
			hashp->hctl->collisions++;
#endif
		}
	}

	/*
	 * if we found an entry or if we weren't trying to insert, we're done
	 * now.
	 */
	*foundPtr = (bool) (currIndex != INVALID_INDEX);
	switch (action)
	{
		case HASH_ENTER:
			if (currIndex != INVALID_INDEX)
				return &(curr->key);
			break;
		case HASH_REMOVE:
		case HASH_REMOVE_SAVED:
			if (currIndex != INVALID_INDEX)
			{
				Assert(hctl->nkeys > 0);
				hctl->nkeys--;

				/* remove record from hash bucket's chain. */
				*prevIndexPtr = curr->next;

				/* add the record to the freelist for this table.  */
				curr->next = hctl->freeBucketIndex;
				hctl->freeBucketIndex = currIndex;

				/*
				 * better hope the caller is synchronizing access to this
				 * element, because someone else is going to reuse it the
				 * next time something is added to the table
				 */
				return &(curr->key);
			}
			return (long *) TRUE;
		case HASH_FIND:
			if (currIndex != INVALID_INDEX)
				return &(curr->key);
			return (long *) TRUE;
		case HASH_FIND_SAVE:
			if (currIndex != INVALID_INDEX)
			{
				saveState.currElem = curr;
				saveState.prevIndex = prevIndexPtr;
				saveState.currIndex = currIndex;
				return &(curr->key);
			}
			return (long *) TRUE;
		default:
			/* can't get here */
			return NULL;
	}

	/*
	 * If we got here, then we didn't find the element and we have to
	 * insert it into the hash table
	 */
	Assert(currIndex == INVALID_INDEX);

	/* get the next free bucket */
	currIndex = hctl->freeBucketIndex;
	if (currIndex == INVALID_INDEX)
	{
		/* no free elements.  allocate another chunk of buckets */
		if (!bucket_alloc(hashp))
			return NULL;
		currIndex = hctl->freeBucketIndex;
	}
	Assert(currIndex != INVALID_INDEX);

	curr = GET_BUCKET(hashp, currIndex);
	hctl->freeBucketIndex = curr->next;

	/* link into chain */
	*prevIndexPtr = currIndex;

	/* copy key into record */
	destAddr = (char *) &(curr->key);
	memmove(destAddr, keyPtr, hctl->keysize);
	curr->next = INVALID_INDEX;

	/*
	 * let the caller initialize the data field after hash_search returns.
	 */
	/* memmove(destAddr,keyPtr,hctl->keysize+hctl->datasize); */

	/*
	 * Check if it is time to split the segment
	 */
	if (++hctl->nkeys / (hctl->max_bucket + 1) > hctl->ffactor)
	{

		/*
		 * NOTE: failure to expand table is not a fatal error, it just
		 * means we have to run at higher fill factor than we wanted.
		 */
		expand_table(hashp);
	}
	return &(curr->key);
}

/*
 * hash_seq -- sequentially search through hash table and return
 *			   all the elements one by one, return NULL on error and
 *			   return TRUE in the end.
 *
 */
long *
hash_seq(HTAB *hashp)
{
	static uint32 curBucket = 0;
	static BUCKET_INDEX curIndex;
	ELEMENT    *curElem;
	long		segment_num;
	long		segment_ndx;
	SEGMENT		segp;
	HHDR	   *hctl;

	if (hashp == NULL)
	{

		/*
		 * reset static state
		 */
		curBucket = 0;
		curIndex = INVALID_INDEX;
		return (long *) NULL;
	}

	hctl = hashp->hctl;
	while (curBucket <= hctl->max_bucket)
	{
		if (curIndex != INVALID_INDEX)
		{
			curElem = GET_BUCKET(hashp, curIndex);
			curIndex = curElem->next;
			if (curIndex == INVALID_INDEX)		/* end of this bucket */
				++curBucket;
			return &(curElem->key);
		}

		/*
		 * initialize the search within this bucket.
		 */
		segment_num = curBucket >> hctl->sshift;
		segment_ndx = MOD(curBucket, hctl->ssize);

		/*
		 * first find the right segment in the table directory.
		 */
		segp = GET_SEG(hashp, segment_num);
		if (segp == NULL)
			/* this is probably an error */
			return (long *) NULL;

		/*
		 * now find the right index into the segment for the first item in
		 * this bucket's chain.  if the bucket is not empty (its entry in
		 * the dir is valid), we know this must correspond to a valid
		 * element and not a freed element because it came out of the
		 * directory of valid stuff.  if there are elements in the bucket
		 * chains that point to the freelist we're in big trouble.
		 */
		curIndex = segp[segment_ndx];

		if (curIndex == INVALID_INDEX)	/* empty bucket */
			++curBucket;
	}

	return (long *) TRUE;		/* out of buckets */
}


/********************************* UTILITIES ************************/

/*
 * Expand the table by adding one more hash bucket.
 */
static int
expand_table(HTAB *hashp)
{
	HHDR	   *hctl;
	SEGMENT		old_seg,
				new_seg;
	long		old_bucket,
				new_bucket;
	long		new_segnum,
				new_segndx;
	long		old_segnum,
				old_segndx;
	ELEMENT    *chain;
	BUCKET_INDEX *old,
			   *newbi;
	BUCKET_INDEX chainIndex,
				nextIndex;

#ifdef HASH_STATISTICS
	hash_expansions++;
#endif

	hctl = hashp->hctl;

	new_bucket = hctl->max_bucket + 1;
	new_segnum = new_bucket >> hctl->sshift;
	new_segndx = MOD(new_bucket, hctl->ssize);

	if (new_segnum >= hctl->nsegs)
	{
		/* Allocate new segment if necessary -- could fail if dir full */
		if (new_segnum >= hctl->dsize)
			if (!dir_realloc(hashp))
				return 0;
		if (!(hashp->dir[new_segnum] = seg_alloc(hashp)))
			return 0;
		hctl->nsegs++;
	}

	/* OK, we created a new bucket */
	hctl->max_bucket++;

	/*
	 * *Before* changing masks, find old bucket corresponding to same hash
	 * values; values in that bucket may need to be relocated to new bucket.
	 * Note that new_bucket is certainly larger than low_mask at this point,
	 * so we can skip the first step of the regular hash mask calc.
	 */
	old_bucket = (new_bucket & hctl->low_mask);

	/*
	 * If we crossed a power of 2, readjust masks.
	 */
	if (new_bucket > hctl->high_mask)
	{
		hctl->low_mask = hctl->high_mask;
		hctl->high_mask = new_bucket | hctl->low_mask;
	}

	/*
	 * Relocate records to the new bucket.  NOTE: because of the way the
	 * hash masking is done in call_hash, only one old bucket can need to
	 * be split at this point.  With a different way of reducing the hash
	 * value, that might not be true!
	 */
	old_segnum = old_bucket >> hctl->sshift;
	old_segndx = MOD(old_bucket, hctl->ssize);

	old_seg = GET_SEG(hashp, old_segnum);
	new_seg = GET_SEG(hashp, new_segnum);

	old = &old_seg[old_segndx];
	newbi = &new_seg[new_segndx];
	for (chainIndex = *old;
		 chainIndex != INVALID_INDEX;
		 chainIndex = nextIndex)
	{
		chain = GET_BUCKET(hashp, chainIndex);
		nextIndex = chain->next;
		if (call_hash(hashp, (char *) &(chain->key)) == old_bucket)
		{
			*old = chainIndex;
			old = &chain->next;
		}
		else
		{
			*newbi = chainIndex;
			newbi = &chain->next;
		}
	}
	/* don't forget to terminate the rebuilt hash chains... */
	*old = INVALID_INDEX;
	*newbi = INVALID_INDEX;
	return 1;
}


static int
dir_realloc(HTAB *hashp)
{
	char	   *p;
	char	   *old_p;
	long		new_dsize;
	long		old_dirsize;
	long		new_dirsize;

	if (hashp->hctl->max_dsize != NO_MAX_DSIZE)
		return 0;

	/* Reallocate directory */
	new_dsize = hashp->hctl->dsize << 1;
	old_dirsize = hashp->hctl->dsize * sizeof(SEG_OFFSET);
	new_dirsize = new_dsize * sizeof(SEG_OFFSET);

	old_p = (char *) hashp->dir;
	p = (char *) hashp->alloc((unsigned long) new_dirsize);

	if (p != NULL)
	{
		memmove(p, old_p, old_dirsize);
		MemSet(p + old_dirsize, 0, new_dirsize - old_dirsize);
		MEM_FREE((char *) old_p);
		hashp->dir = (SEG_OFFSET *) p;
		hashp->hctl->dsize = new_dsize;
		return 1;
	}
	return 0;
}


static SEG_OFFSET
seg_alloc(HTAB *hashp)
{
	SEGMENT		segp;
	SEG_OFFSET	segOffset;

	segp = (SEGMENT) hashp->alloc((unsigned long)
							  sizeof(BUCKET_INDEX) * hashp->hctl->ssize);

	if (!segp)
		return 0;

	MemSet((char *) segp, 0,
		   (long) sizeof(BUCKET_INDEX) * hashp->hctl->ssize);

	segOffset = MAKE_HASHOFFSET(hashp, segp);
	return segOffset;
}

/*
 * allocate some new buckets and link them into the free list
 */
static int
bucket_alloc(HTAB *hashp)
{
	int			i;
	ELEMENT    *tmpBucket;
	long		bucketSize;
	BUCKET_INDEX tmpIndex,
				lastIndex;

	/* Each bucket has a BUCKET_INDEX header plus user data. */
	bucketSize = sizeof(BUCKET_INDEX) + hashp->hctl->keysize + hashp->hctl->datasize;

	/* make sure its aligned correctly */
	bucketSize = MAXALIGN(bucketSize);

	tmpBucket = (ELEMENT *)
		hashp->alloc((unsigned long) BUCKET_ALLOC_INCR * bucketSize);

	if (!tmpBucket)
		return 0;

	/* tmpIndex is the shmem offset into the first bucket of the array */
	tmpIndex = MAKE_HASHOFFSET(hashp, tmpBucket);

	/* set the freebucket list to point to the first bucket */
	lastIndex = hashp->hctl->freeBucketIndex;
	hashp->hctl->freeBucketIndex = tmpIndex;

	/*
	 * initialize each bucket to point to the one behind it. NOTE: loop
	 * sets last bucket incorrectly; we fix below.
	 */
	for (i = 0; i < BUCKET_ALLOC_INCR; i++)
	{
		tmpBucket = GET_BUCKET(hashp, tmpIndex);
		tmpIndex += bucketSize;
		tmpBucket->next = tmpIndex;
	}

	/*
	 * the last bucket points to the old freelist head (which is probably
	 * invalid or we wouldn't be here)
	 */
	tmpBucket->next = lastIndex;

	return 1;
}

/* calculate ceil(log base 2) of num */
int
my_log2(long num)
{
	int			i;
	long		limit;

	for (i = 0, limit = 1; limit < num; i++, limit <<= 1)
		;
	return i;
}