hash_bigkey.c

asterisk 一个模拟IPPBX的源代码

		 */
		if (bp[2] == FULL_KEY_DATA &&
		    ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp))))
			break;

		pageno = bp[n - 1];
		bufp = __get_buf(hashp, pageno, bufp, 0);
		if (!bufp)
			return (0);	/* Need to indicate an error! */
		bp = (u_int16_t *)bufp->page;
	}

	*bpp = bufp;
	if (bp[0] > 2)
		return (bp[3]);
	else
		return (0);
}

/*
 * Return the data for the key/data pair that begins on this page at this
 * index (index should always be 1).
 */
extern int
__big_return(hashp, bufp, ndx, val, set_current)
	HTAB *hashp;
	BUFHEAD *bufp;
	int ndx;
	DBT *val;
	int set_current;
{
	BUFHEAD *save_p;
	u_int16_t *bp, len, off, save_addr;
	char *tp;

	bp = (u_int16_t *)bufp->page;
	while (bp[ndx + 1] == PARTIAL_KEY) {
		bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
		if (!bufp)
			return (-1);
		bp = (u_int16_t *)bufp->page;
		ndx = 1;
	}

	if (bp[ndx + 1] == FULL_KEY) {
		bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
		if (!bufp)
			return (-1);
		bp = (u_int16_t *)bufp->page;
		save_p = bufp;
		save_addr = save_p->addr;
		off = bp[1];
		len = 0;
	} else
		if (!FREESPACE(bp)) {
			/*
			 * This is a hack.  We can't distinguish between
			 * FULL_KEY_DATA that contains complete data or
			 * incomplete data, so we require that if the data
			 * is complete, there is at least 1 byte of free
			 * space left.
			 */
			off = bp[bp[0]];
			len = bp[1] - off;
			save_p = bufp;
			save_addr = bufp->addr;
			bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
			if (!bufp)
				return (-1);
			bp = (u_int16_t *)bufp->page;
		} else {
			/* The data is all on one page. */
			tp = (char *)bp;
			off = bp[bp[0]];
			val->data = (u_char *)tp + off;
			val->size = bp[1] - off;
			if (set_current) {
				if (bp[0] == 2) {	/* No more buckets in
							 * chain */
					hashp->cpage = NULL;
					hashp->cbucket++;
					hashp->cndx = 1;
				} else {
					hashp->cpage = __get_buf(hashp,
					    bp[bp[0] - 1], bufp, 0);
					if (!hashp->cpage)
						return (-1);
					hashp->cndx = 1;
					if (!((u_int16_t *)
					    hashp->cpage->page)[0]) {
						hashp->cbucket++;
						hashp->cpage = NULL;
					}
				}
			}
			return (0);
		}

	val->size = collect_data(hashp, bufp, (int)len, set_current);
	if (val->size == (size_t) -1)
		return (-1);
	if (save_p->addr != save_addr) {
		/* We are pretty short on buffers. */
		errno = EINVAL;			/* OUT OF BUFFERS */
		return (-1);
	}
	memmove(hashp->tmp_buf, (save_p->page) + off, len);
	val->data = (u_char *)hashp->tmp_buf;
	return (0);
}
/*
 * Count how big the total datasize is by recursing through the pages.  Then
 * allocate a buffer and copy the data as you recurse up.
 */
static int
collect_data(hashp, bufp, len, set)
	HTAB *hashp;
	BUFHEAD *bufp;
	int len, set;
{
	register u_int16_t *bp;
	register char *p;
	BUFHEAD *xbp;
	u_int16_t save_addr;
	int mylen, totlen;

	p = bufp->page;
	bp = (u_int16_t *)p;
	mylen = hashp->BSIZE - bp[1];
	save_addr = bufp->addr;

	if (bp[2] == FULL_KEY_DATA) {		/* End of Data */
		totlen = len + mylen;
		if (hashp->tmp_buf)
			free(hashp->tmp_buf);
		if ((hashp->tmp_buf = (char *)malloc(totlen)) == NULL)
			return (-1);
		if (set) {
			hashp->cndx = 1;
			if (bp[0] == 2) {	/* No more buckets in chain */
				hashp->cpage = NULL;
				hashp->cbucket++;
			} else {
				hashp->cpage =
				    __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
				if (!hashp->cpage)
					return (-1);
				else if (!((u_int16_t *)hashp->cpage->page)[0]) {
					hashp->cbucket++;
					hashp->cpage = NULL;
				}
			}
		}
	} else {
		xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
		if (!xbp || ((totlen =
		    collect_data(hashp, xbp, len + mylen, set)) < 1))
			return (-1);
	}
	if (bufp->addr != save_addr) {
		errno = EINVAL;			/* Out of buffers. */
		return (-1);
	}
	memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], mylen);
	return (totlen);
}

/*
 * Fill in the key and data for this big pair.
 */
extern int
__big_keydata(hashp, bufp, key, val, set)
	HTAB *hashp;
	BUFHEAD *bufp;
	DBT *key, *val;
	int set;
{
	key->size = collect_key(hashp, bufp, 0, val, set);
	if (key->size == (size_t) -1)
		return (-1);
	key->data = (u_char *)hashp->tmp_key;
	return (0);
}

/*
 * Count how big the total key size is by recursing through the pages.  Then
 * collect the data, allocate a buffer and copy the key as you recurse up.
 */
static int
collect_key(hashp, bufp, len, val, set)
	HTAB *hashp;
	BUFHEAD *bufp;
	int len;
	DBT *val;
	int set;
{
	BUFHEAD *xbp;
	char *p;
	int mylen, totlen;
	u_int16_t *bp, save_addr;

	p = bufp->page;
	bp = (u_int16_t *)p;
	mylen = hashp->BSIZE - bp[1];

	save_addr = bufp->addr;
	totlen = len + mylen;
	if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) {    /* End of Key. */
		if (hashp->tmp_key != NULL)
			free(hashp->tmp_key);
		if ((hashp->tmp_key = (char *)malloc(totlen)) == NULL)
			return (-1);
		if (__big_return(hashp, bufp, 1, val, set))
			return (-1);
	} else {
		xbp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
		if (!xbp || ((totlen =
		    collect_key(hashp, xbp, totlen, val, set)) < 1))
			return (-1);
	}
	if (bufp->addr != save_addr) {
		errno = EINVAL;		/* MIS -- OUT OF BUFFERS */
		return (-1);
	}
	memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], mylen);
	return (totlen);
}

/*
 * Returns:
 *  0 => OK
 * -1 => error
 */
extern int
__big_split(hashp, op, np, big_keyp, addr, obucket, ret)
	HTAB *hashp;
	BUFHEAD *op;	/* Pointer to where to put keys that go in old bucket */
	BUFHEAD *np;	/* Pointer to new bucket page */
			/* Pointer to first page containing the big key/data */
	BUFHEAD *big_keyp;
	int addr;	/* Address of big_keyp */
	u_int32_t   obucket;/* Old Bucket */
	SPLIT_RETURN *ret;
{
	register BUFHEAD *tmpp;
	register u_int16_t *tp;
	BUFHEAD *bp;
	DBT key, val;
	u_int32_t change;
	u_int16_t free_space, n, off;

	bp = big_keyp;

	/* Now figure out where the big key/data goes */
	if (__big_keydata(hashp, big_keyp, &key, &val, 0))
		return (-1);
	change = (__call_hash(hashp, key.data, key.size) != obucket);

	if ((ret->next_addr = __find_last_page(hashp, &big_keyp))) {
		if (!(ret->nextp =
		    __get_buf(hashp, ret->next_addr, big_keyp, 0)))
			return (-1);;
	} else
		ret->nextp = NULL;

	/* Now make one of np/op point to the big key/data pair */
#ifdef DEBUG
	assert(np->ovfl == NULL);
#endif
	if (change)
		tmpp = np;
	else
		tmpp = op;

	tmpp->flags |= BUF_MOD;
#ifdef DEBUG1
	(void)fprintf(stderr,
	    "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,
	    (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0));
#endif
	tmpp->ovfl = bp;	/* one of op/np point to big_keyp */
	tp = (u_int16_t *)tmpp->page;
#ifdef DEBUG
	assert(FREESPACE(tp) >= OVFLSIZE);
#endif
	n = tp[0];
	off = OFFSET(tp);
	free_space = FREESPACE(tp);
	tp[++n] = (u_int16_t)addr;
	tp[++n] = OVFLPAGE;
	tp[0] = n;
	OFFSET(tp) = off;
	FREESPACE(tp) = free_space - OVFLSIZE;

	/*
	 * Finally, set the new and old return values. BIG_KEYP contains a
	 * pointer to the last page of the big key_data pair. Make sure that
	 * big_keyp has no following page (2 elements) or create an empty
	 * following page.
	 */

	ret->newp = np;
	ret->oldp = op;

	tp = (u_int16_t *)big_keyp->page;
	big_keyp->flags |= BUF_MOD;
	if (tp[0] > 2) {
		/*
		 * There may be either one or two offsets on this page.  If
		 * there is one, then the overflow page is linked on normally
		 * and tp[4] is OVFLPAGE.  If there are two, tp[4] contains
		 * the second offset and needs to get stuffed in after the
		 * next overflow page is added.
		 */
		n = tp[4];
		free_space = FREESPACE(tp);
		off = OFFSET(tp);
		tp[0] -= 2;
		FREESPACE(tp) = free_space + OVFLSIZE;
		OFFSET(tp) = off;
		tmpp = __add_ovflpage(hashp, big_keyp);
		if (!tmpp)
			return (-1);
		tp[4] = n;
	} else
		tmpp = big_keyp;

	if (change)
		ret->newp = tmpp;
	else
		ret->oldp = tmpp;
	return (0);
}