[unix-history] / usr / src / lib / libc / db / btree / bt_utils.c

/*-
 * Copyright (c) 1990 The Regents of the University of California.
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Mike Olson.
 *
 * %sccs.include.redist.c%
 */

#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid[] = "@(#)bt_utils.c	5.3 (Berkeley) %G%";
#endif /* LIBC_SCCS and not lint */

#include <sys/types.h>
#include <db.h>
#include <stdlib.h>
#include <string.h>
#include "btree.h"

/*
 *  _BT_BUILDRET -- Build return key/data pair as a result of search or scan.
 *
 *	This routine manages the statically allocated buffers in which we
 *	return data to the user.
 *
 *	Parameters:
 *		t -- btree from which to return datum
 *		d -- DATUM to be returned to the user.
 *		data -- data argument supplied by user for return
 *		key -- key argument supplied by user for return
 *
 *	Returns:
 *		RET_SUCCESS, RET_ERROR.
 *
 *	Side Effects:
 *		May free and reallocate static buffers, if the data
 *		we want to return is bigger than the space we have to
 *		do so.
 */

int
_bt_buildret(t, d, data, key)
	BTREE_P t;
	DATUM *d;
	DBT *data;
	DBT *key;
{
	static int _data_s = 0;
	static int _key_s = 0;
	static char *_data = (char *) NULL;
	static char *_key = (char *) NULL;
	pgno_t chain;

	if (d->d_flags & D_BIGKEY) {
		if (_key != (char *) NULL)
			(void) free(_key);
		(void) bcopy((char *) &(d->d_bytes[0]),
		      	     (char *) &chain,
		      	     sizeof(chain));
		if (_bt_getbig(t, chain, &_key, &_key_s) == RET_ERROR)
			return (RET_ERROR);
		key->data = (u_char *)_key;
		key->size = _key_s;
	} else {
		/* need more space for key? */
		if (d->d_ksize > _key_s) {
			if (_key != (char *) NULL)
				(void) free (_key);
			if ((_key = (char *) malloc((unsigned) d->d_ksize))
			    == (char *) NULL)
				return (RET_ERROR);
			_key_s = d->d_ksize;
		}

		key->data = (u_char *)_key;
		if ((key->size = d->d_ksize) > 0)
			(void) bcopy(&(d->d_bytes[0]),
				     _key,
				     (int) d->d_ksize);
	}

	if (d->d_flags & D_BIGDATA) {
		if (_data != (char *) NULL)
			(void) free(_data);
		(void) bcopy(&(d->d_bytes[d->d_ksize]),
		      	     (char *) &chain,
		      	     sizeof(chain));
		if (_bt_getbig(t, chain, &_data, &_data_s) == RET_ERROR)
			return (RET_ERROR);
		data->data = (u_char *)_data;
		data->size = _data_s;
	} else {
		/* need more space for data? */
		if (d->d_dsize > _data_s) {
			if (_data != (char *) NULL)
				(void) free (_data);
			if ((_data = (char *) malloc((unsigned) d->d_dsize))
			    == (char *) NULL)
				return (RET_ERROR);
			_data_s = d->d_dsize;
		}

		data->data = (u_char *)_data;

		if ((data->size = d->d_dsize) > 0)
			(void) bcopy(&(d->d_bytes[d->d_ksize]),
				      _data,
				      (size_t) (d->d_dsize));
	}

	return (RET_SUCCESS);
}

/*
 *  _BT_CMP -- Compare a key to a given item on the current page.
 *
 *	This routine is a wrapper for the user's comparison function.
 *
 *	Parameters:
 *		t -- tree in which to do comparison
 *		p -- pointer to one argument for the comparison function
 *		n -- index of item to supply second arg to comparison function
 *
 *	Returns:
 *		< 0 if p is < item at n
 *		= 0 if p is = item at n
 *		> 0 if p is > item at n
 */

int
_bt_cmp(t, p, n)
	BTREE_P t;
	char *p;
	index_t n;
{
	BTHEADER *h;
	IDATUM *id;
	DATUM *d;
	char *arg;
	int ignore;
	int free_arg;
	pgno_t chain;
	int r;

	h = t->bt_curpage;

	/*
	 *  The left-most key at any level of the tree on internal pages
	 *  is guaranteed (artificially, by the code here) to be less than
	 *  any user key.  This saves us from having to update the leftmost
	 *  key when the user inserts a new key in the tree smaller than
	 *  anything we've seen yet.
	 */

	if (h->h_prevpg == P_NONE && !(h->h_flags & F_LEAF) && n == 0)
		return (1);

	if (h->h_flags & F_LEAF) {
		d = (DATUM *) GETDATUM(h,n);
		if (d->d_flags & D_BIGKEY) {
			free_arg = TRUE;
			bcopy(&(d->d_bytes[0]), (char *) &chain, sizeof(chain));
			if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR)
				return (RET_ERROR);
		} else {
			free_arg = FALSE;
			arg = &(d->d_bytes[0]);
		}
	} else {
		id = (IDATUM *) GETDATUM(h,n);
		if (id->i_flags & D_BIGKEY) {
			free_arg = TRUE;
			bcopy(&(id->i_bytes[0]),
			      (char *) &chain,
			      sizeof(chain));
			if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR)
				return (RET_ERROR);
		} else {
			free_arg = FALSE;
			arg = &(id->i_bytes[0]);
		}
	}
	r = (*(t->bt_compare))(p, arg);

	if (free_arg)
		(void) free(arg);

	return (r);
}

/*
 *  _BT_PUSH/_BT_POP -- Push/pop a parent page number on the parent stack.
 *
 *	When we descend the tree, we keep track of parent pages in order
 *	to handle splits on insertions.
 *
 *	Parameters:
 *		t -- tree for which to push parent
 *		pgno -- page number to push (_bt_push only)
 *
 *	Returns:
 *		RET_SUCCESS, RET_ERROR.
 */

int
_bt_push(t, pgno)
	BTREE_P t;
	pgno_t pgno;
{
	BTSTACK *new;

	if ((new = (BTSTACK *) malloc((unsigned) sizeof(BTSTACK)))
	    ==  (BTSTACK *) NULL)
		return (RET_ERROR);
	new->bts_pgno = pgno;
	new->bts_next = t->bt_stack;
	t->bt_stack = new;

	return (RET_SUCCESS);
}

pgno_t
_bt_pop(t)
	BTREE_P t;
{
	BTSTACK *s;
	pgno_t p = P_NONE;

	if ((s = t->bt_stack) != (BTSTACK *) NULL) {
		p = s->bts_pgno;
		t->bt_stack = s->bts_next;
		(void) free ((char *) s);
	}
	return (p);
}

#ifdef DEBUG
void
_btdump(tree)
	BTREE tree;
{
	BTREE_P t = (BTREE_P) tree;
	DATUM *d;
	IDATUM *id;
	BTHEADER *h;
	pgno_t npages;
	pgno_t i;
	index_t cur, top;

	npages = t->bt_npages;
	(void) printf("\"%s\" fd %d pgsz %d curpg %d @ 0x%lx",
		t->bt_fname, t->bt_s.bt_d.d_fd,
		t->bt_psize, t->bt_curpage);
	(void) printf("npg %d cmp 0x%lx flags=(", npages, t->bt_compare);
	if (t->bt_flags & BTF_SEQINIT)
		(void) printf("BTF_SEQINIT");
	(void) printf(")\n");

	for (i = P_ROOT; i <= npages; i++) {
		if (_bt_getpage(t, i) == RET_ERROR)
			_punt();
		h = t->bt_curpage;
		top = NEXTINDEX(h);
		(void) printf("    page %d:\n", i);
		(void) printf("\tpgno %d prev %d next %d\n",
			h->h_pgno, h->h_prevpg, h->h_nextpg);
		(void) printf("\tlower %d upper %d nextind %d flags (",
			h->h_lower, h->h_upper, top);
		if (h->h_flags & F_LEAF)
			(void) printf("F_LEAF");
		else
			(void) printf("<internal>");
		if (h->h_flags & F_DIRTY)
			(void) printf("|F_DIRTY");
		if (h->h_flags & F_PRESERVE)
			(void) printf("|F_PRESERVE");
		if (h->h_flags & F_CONT) {
			(void) printf("|F_CONT)");
			if (h->h_prevpg == P_NONE) {
				size_t longsz;
				(void) bcopy((char *) &(h->h_linp[0]),
					      (char *) &longsz,
					      sizeof(longsz));
				printf("\n\t\t(chain start, data length %ld)",
					longsz);
			}
			printf("\n");
			continue;
		}
		(void) printf(")\n");
		for (cur = 0; cur < top; cur++) {
			(void) printf("\t  [%d] off %d ", cur, h->h_linp[cur]);
			if (h->h_flags & F_LEAF) {
				d = (DATUM *) GETDATUM(h,cur);
				(void) printf("ksize %d", d->d_ksize);
				if (d->d_flags & D_BIGKEY)
					(void) printf(" (indirect)");
				(void) printf("; dsize %d", d->d_dsize);
				if (d->d_flags & D_BIGDATA)
					(void) printf(" (indirect)");
			} else {
				id = (IDATUM *) GETDATUM(h,cur);
				(void) printf("size %d pgno %d",
					id->i_size, id->i_pgno);
				if (id->i_flags & D_BIGKEY)
					(void) printf(" (indirect)");
			}
			(void) printf("\n");
		}
		(void) printf("\n");
	}
}
#endif /* DEBUG */

#ifdef DEBUG
_punt()
{
	int pid;

	pid = getpid();
	(void) kill(pid, SIGILL);
}
#endif /* DEBUG */
Commit	Line	Data
fb5357d5 MO	1	/*-
	2	* Copyright (c) 1990 The Regents of the University of California.
	3	* All rights reserved.
	4	*
	5	* This code is derived from software contributed to Berkeley by
	6	* Mike Olson.
	7	*
	8	* %sccs.include.redist.c%
	9	*/
	10
	11	#if defined(LIBC_SCCS) && !defined(lint)
7d2840f6	12	static char sccsid[] = "@(#)bt_utils.c 5.3 (Berkeley) %G%";
fb5357d5 MO	13	#endif /* LIBC_SCCS and not lint */
	14
	15	#include <sys/types.h>
	16	#include <db.h>
fb91cf55 KB	17	#include <stdlib.h>
fb91cf55 KB	18	#include <string.h>
fb5357d5 MO	19	#include "btree.h"
	20
	21	/*
	22	* _BT_BUILDRET -- Build return key/data pair as a result of search or scan.
	23	*
	24	* This routine manages the statically allocated buffers in which we
	25	* return data to the user.
	26	*
	27	* Parameters:
	28	* t -- btree from which to return datum
	29	* d -- DATUM to be returned to the user.
	30	* data -- data argument supplied by user for return
	31	* key -- key argument supplied by user for return
	32	*
	33	* Returns:
	34	* RET_SUCCESS, RET_ERROR.
	35	*
	36	* Side Effects:
	37	* May free and reallocate static buffers, if the data
	38	* we want to return is bigger than the space we have to
	39	* do so.
	40	*/
	41
	42	int
	43	_bt_buildret(t, d, data, key)
	44	BTREE_P t;
	45	DATUM *d;
	46	DBT *data;
	47	DBT *key;
	48	{
	49	static int _data_s = 0;
	50	static int _key_s = 0;
	51	static char _data = (char ) NULL;
	52	static char _key = (char ) NULL;
	53	pgno_t chain;
	54
	55	if (d->d_flags & D_BIGKEY) {
	56	if (_key != (char *) NULL)
	57	(void) free(_key);
	58	(void) bcopy((char *) &(d->d_bytes[0]),
	59	(char *) &chain,
	60	sizeof(chain));
	61	if (_bt_getbig(t, chain, &_key, &_key_s) == RET_ERROR)
	62	return (RET_ERROR);
7d2840f6	63	key->data = (u_char *)_key;
fb5357d5 MO	64	key->size = _key_s;
	65	} else {
	66	/* need more space for key? */
	67	if (d->d_ksize > _key_s) {
	68	if (_key != (char *) NULL)
	69	(void) free (_key);
	70	if ((_key = (char *) malloc((unsigned) d->d_ksize))
	71	== (char *) NULL)
	72	return (RET_ERROR);
	73	_key_s = d->d_ksize;
	74	}
	75
7d2840f6	76	key->data = (u_char *)_key;
fb5357d5 MO	77	if ((key->size = d->d_ksize) > 0)
	78	(void) bcopy(&(d->d_bytes[0]),
	79	_key,
	80	(int) d->d_ksize);
	81	}
	82
	83	if (d->d_flags & D_BIGDATA) {
	84	if (_data != (char *) NULL)
	85	(void) free(_data);
	86	(void) bcopy(&(d->d_bytes[d->d_ksize]),
	87	(char *) &chain,
	88	sizeof(chain));
	89	if (_bt_getbig(t, chain, &_data, &_data_s) == RET_ERROR)
	90	return (RET_ERROR);
7d2840f6	91	data->data = (u_char *)_data;
fb5357d5 MO	92	data->size = _data_s;
	93	} else {
	94	/* need more space for data? */
	95	if (d->d_dsize > _data_s) {
	96	if (_data != (char *) NULL)
	97	(void) free (_data);
	98	if ((_data = (char *) malloc((unsigned) d->d_dsize))
	99	== (char *) NULL)
	100	return (RET_ERROR);
	101	_data_s = d->d_dsize;
	102	}
	103
7d2840f6	104	data->data = (u_char *)_data;
fb5357d5 MO	105
	106	if ((data->size = d->d_dsize) > 0)
	107	(void) bcopy(&(d->d_bytes[d->d_ksize]),
	108	_data,
	109	(size_t) (d->d_dsize));
	110	}
	111
	112	return (RET_SUCCESS);
	113	}
	114
	115	/*
	116	* _BT_CMP -- Compare a key to a given item on the current page.
	117	*
	118	* This routine is a wrapper for the user's comparison function.
	119	*
	120	* Parameters:
	121	* t -- tree in which to do comparison
	122	* p -- pointer to one argument for the comparison function
	123	* n -- index of item to supply second arg to comparison function
	124	*
	125	* Returns:
	126	* < 0 if p is < item at n
	127	* = 0 if p is = item at n
	128	* > 0 if p is > item at n
	129	*/
	130
	131	int
	132	_bt_cmp(t, p, n)
	133	BTREE_P t;
	134	char *p;
	135	index_t n;
	136	{
	137	BTHEADER *h;
	138	IDATUM *id;
	139	DATUM *d;
	140	char *arg;
	141	int ignore;
	142	int free_arg;
	143	pgno_t chain;
	144	int r;
	145
	146	h = t->bt_curpage;
	147
	148	/*
	149	* The left-most key at any level of the tree on internal pages
	150	* is guaranteed (artificially, by the code here) to be less than
	151	* any user key. This saves us from having to update the leftmost
	152	* key when the user inserts a new key in the tree smaller than
	153	* anything we've seen yet.
	154	*/
	155
	156	if (h->h_prevpg == P_NONE && !(h->h_flags & F_LEAF) && n == 0)
	157	return (1);
	158
	159	if (h->h_flags & F_LEAF) {
	160	d = (DATUM *) GETDATUM(h,n);
	161	if (d->d_flags & D_BIGKEY) {
	162	free_arg = TRUE;
	163	bcopy(&(d->d_bytes[0]), (char *) &chain, sizeof(chain));
	164	if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR)
	165	return (RET_ERROR);
	166	} else {
	167	free_arg = FALSE;
	168	arg = &(d->d_bytes[0]);
169	}
170	} else {
171	id = (IDATUM *) GETDATUM(h,n);
172	if (id->i_flags & D_BIGKEY) {
173	free_arg = TRUE;
174	bcopy(&(id->i_bytes[0]),
175	(char *) &chain,
176	sizeof(chain));
177	if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR)
178	return (RET_ERROR);
179	} else {
180	free_arg = FALSE;
181	arg = &(id->i_bytes[0]);
182	}
183	}
184	r = (*(t->bt_compare))(p, arg);
185
186	if (free_arg)
187	(void) free(arg);
188
189	return (r);
190	}
191
192	/*
193	* _BT_PUSH/_BT_POP -- Push/pop a parent page number on the parent stack.
194	*
195	* When we descend the tree, we keep track of parent pages in order
196	* to handle splits on insertions.
197	*
198	* Parameters:
199	* t -- tree for which to push parent
200	* pgno -- page number to push (_bt_push only)
201	*
202	* Returns:
203	* RET_SUCCESS, RET_ERROR.
204	*/
205
206	int
207	_bt_push(t, pgno)
208	BTREE_P t;
209	pgno_t pgno;
210	{
211	BTSTACK *new;
212
213	if ((new = (BTSTACK *) malloc((unsigned) sizeof(BTSTACK)))
214	== (BTSTACK *) NULL)
215	return (RET_ERROR);
216	new->bts_pgno = pgno;
217	new->bts_next = t->bt_stack;
218	t->bt_stack = new;
219
220	return (RET_SUCCESS);
221	}
222
223	pgno_t
224	_bt_pop(t)
225	BTREE_P t;
226	{
227	BTSTACK *s;
228	pgno_t p = P_NONE;
229
230	if ((s = t->bt_stack) != (BTSTACK *) NULL) {
231	p = s->bts_pgno;
232	t->bt_stack = s->bts_next;
233	(void) free ((char *) s);
234	}
235	return (p);
236	}
237
238	#ifdef DEBUG
239	void
240	_btdump(tree)
241	BTREE tree;
242	{
243	BTREE_P t = (BTREE_P) tree;
244	DATUM *d;
245	IDATUM *id;
246	BTHEADER *h;
247	pgno_t npages;
248	pgno_t i;
249	index_t cur, top;
250
251	npages = t->bt_npages;
252	(void) printf("\"%s\" fd %d pgsz %d curpg %d @ 0x%lx",
253	t->bt_fname, t->bt_s.bt_d.d_fd,
254	t->bt_psize, t->bt_curpage);
255	(void) printf("npg %d cmp 0x%lx flags=(", npages, t->bt_compare);
256	if (t->bt_flags & BTF_SEQINIT)
257	(void) printf("BTF_SEQINIT");
258	(void) printf(")\n");
259
260	for (i = P_ROOT; i <= npages; i++) {
261	if (_bt_getpage(t, i) == RET_ERROR)
262	_punt();
263	h = t->bt_curpage;
264	top = NEXTINDEX(h);
265	(void) printf(" page %d:\n", i);
266	(void) printf("\tpgno %d prev %d next %d\n",
267	h->h_pgno, h->h_prevpg, h->h_nextpg);
268	(void) printf("\tlower %d upper %d nextind %d flags (",
269	h->h_lower, h->h_upper, top);
270	if (h->h_flags & F_LEAF)
271	(void) printf("F_LEAF");
272	else
273	(void) printf("<internal>");
274	if (h->h_flags & F_DIRTY)
275	(void) printf("\|F_DIRTY");
276	if (h->h_flags & F_PRESERVE)
277	(void) printf("\|F_PRESERVE");
278	if (h->h_flags & F_CONT) {
279	(void) printf("\|F_CONT)");
280	if (h->h_prevpg == P_NONE) {
281	size_t longsz;
282	(void) bcopy((char *) &(h->h_linp[0]),
283	(char *) &longsz,
284	sizeof(longsz));
285	printf("\n\t\t(chain start, data length %ld)",
286	longsz);
287	}
288	printf("\n");
289	continue;
290	}
291	(void) printf(")\n");
292	for (cur = 0; cur < top; cur++) {
293	(void) printf("\t [%d] off %d ", cur, h->h_linp[cur]);
294	if (h->h_flags & F_LEAF) {
295	d = (DATUM *) GETDATUM(h,cur);
296	(void) printf("ksize %d", d->d_ksize);
297	if (d->d_flags & D_BIGKEY)
298	(void) printf(" (indirect)");
299	(void) printf("; dsize %d", d->d_dsize);
300	if (d->d_flags & D_BIGDATA)
301	(void) printf(" (indirect)");
302	} else {
303	id = (IDATUM *) GETDATUM(h,cur);
304	(void) printf("size %d pgno %d",
305	id->i_size, id->i_pgno);
306	if (id->i_flags & D_BIGKEY)
307	(void) printf(" (indirect)");
308	}
309	(void) printf("\n");
310	}
311	(void) printf("\n");
312	}
313	}
314	#endif /* DEBUG */
315
316	#ifdef DEBUG
317	_punt()
318	{
319	int pid;
320
321	pid = getpid();
322	(void) kill(pid, SIGILL);
323	}
324	#endif /* DEBUG */