Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	lib/libc/db/btree/bt_overflow.c	Lines:	0	52	0.0 %
Date:	2017-11-07	Branches:	0	22	0.0 %


/*	$OpenBSD: bt_overflow.c,v 1.11 2015/01/16 16:48:51 deraadt Exp $	*/

/*-
 * Copyright (c) 1990, 1993, 1994
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Mike Olson.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <db.h>
#include "btree.h"

#define MINIMUM(a, b)	(((a) < (b)) ? (a) : (b))

/*
 * Big key/data code.
 *
 * Big key and data entries are stored on linked lists of pages.  The initial
 * reference is byte string stored with the key or data and is the page number
 * and size.  The actual record is stored in a chain of pages linked by the
 * nextpg field of the PAGE header.
 *
 * The first page of the chain has a special property.  If the record is used
 * by an internal page, it cannot be deleted and the P_PRESERVE bit will be set
 * in the header.
 *
 * XXX
 * A single DBT is written to each chain, so a lot of space on the last page
 * is wasted.  This is a fairly major bug for some data sets.
 */

/*
 * __OVFL_GET -- Get an overflow key/data item.
 *
 * Parameters:
 *	t:	tree
 *	p:	pointer to { pgno_t, u_int32_t }
 *	buf:	storage address
 *	bufsz:	storage size
 *
 * Returns:
 *	RET_ERROR, RET_SUCCESS
 */
int
__ovfl_get(BTREE *t, void *p, size_t *ssz, void **buf, size_t *bufsz)
{
	PAGE *h;
	pgno_t pg;
	size_t nb, plen;
	u_int32_t sz;
	void *tp;

	memmove(&pg, p, sizeof(pgno_t));
	memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t));
	*ssz = sz;

#ifdef DEBUG
	if (pg == P_INVALID || sz == 0)
		abort();
#endif
	/* Make the buffer bigger as necessary. */
	if (*bufsz < sz) {
		tp = realloc(*buf, sz);
		if (tp == NULL)
			return (RET_ERROR);
		*buf = tp;
		*bufsz = sz;
	}

	/*
	 * Step through the linked list of pages, copying the data on each one
	 * into the buffer.  Never copy more than the data's length.
	 */
	plen = t->bt_psize - BTDATAOFF;
	for (p = *buf;; p = (char *)p + nb, pg = h->nextpg) {
		if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
			return (RET_ERROR);

		nb = MINIMUM(sz, plen);
		memmove(p, (char *)h + BTDATAOFF, nb);
		mpool_put(t->bt_mp, h, 0);

		if ((sz -= nb) == 0)
			break;
	}
	return (RET_SUCCESS);
}

/*
 * __OVFL_PUT -- Store an overflow key/data item.
 *
 * Parameters:
 *	t:	tree
 *	data:	DBT to store
 *	pgno:	storage page number
 *
 * Returns:
 *	RET_ERROR, RET_SUCCESS
 */
int
__ovfl_put(BTREE *t, const DBT *dbt, pgno_t *pg)
{
	PAGE *h, *last;
	void *p;
	pgno_t npg;
	size_t nb, plen;
	u_int32_t sz;

	/*
	 * Allocate pages and copy the key/data record into them.  Store the
	 * number of the first page in the chain.
	 */
	plen = t->bt_psize - BTDATAOFF;
	for (last = NULL, p = dbt->data, sz = dbt->size;;
	    p = (char *)p + plen, last = h) {
		if ((h = __bt_new(t, &npg)) == NULL)
			return (RET_ERROR);

		h->pgno = npg;
		h->nextpg = h->prevpg = P_INVALID;
		h->flags = P_OVERFLOW;
		h->lower = h->upper = 0;

		nb = MINIMUM(sz, plen);
		memmove((char *)h + BTDATAOFF, p, nb);

		if (last) {
			last->nextpg = h->pgno;
			mpool_put(t->bt_mp, last, MPOOL_DIRTY);
		} else
			*pg = h->pgno;

		if ((sz -= nb) == 0) {
			mpool_put(t->bt_mp, h, MPOOL_DIRTY);
			break;
		}
	}
	return (RET_SUCCESS);
}

/*
 * __OVFL_DELETE -- Delete an overflow chain.
 *
 * Parameters:
 *	t:	tree
 *	p:	pointer to { pgno_t, u_int32_t }
 *
 * Returns:
 *	RET_ERROR, RET_SUCCESS
 */
int
__ovfl_delete(BTREE *t, void *p)
{
	PAGE *h;
	pgno_t pg;
	size_t plen;
	u_int32_t sz;

	memmove(&pg, p, sizeof(pgno_t));
	memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t));

#ifdef DEBUG
	if (pg == P_INVALID || sz == 0)
		abort();
#endif
	if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
		return (RET_ERROR);

	/* Don't delete chains used by internal pages. */
	if (h->flags & P_PRESERVE) {
		mpool_put(t->bt_mp, h, 0);
		return (RET_SUCCESS);
	}

	/* Step through the chain, calling the free routine for each page. */
	for (plen = t->bt_psize - BTDATAOFF;; sz -= plen) {
		pg = h->nextpg;
		__bt_free(t, h);
		if (sz <= plen)
			break;
		if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
			return (RET_ERROR);
	}
	return (RET_SUCCESS);
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: bt_overflow.c,v 1.11 2015/01/16 16:48:51 deraadt Exp $ */
2
3			/*-
4			* Copyright (c) 1990, 1993, 1994
5			* The Regents of the University of California. All rights reserved.
6			*
7			* This code is derived from software contributed to Berkeley by
8			* Mike Olson.
9			*
10			* Redistribution and use in source and binary forms, with or without
11			* modification, are permitted provided that the following conditions
12			* are met:
13			* 1. Redistributions of source code must retain the above copyright
14			* notice, this list of conditions and the following disclaimer.
15			* 2. Redistributions in binary form must reproduce the above copyright
16			* notice, this list of conditions and the following disclaimer in the
17			* documentation and/or other materials provided with the distribution.
18			* 3. Neither the name of the University nor the names of its contributors
19			* may be used to endorse or promote products derived from this software
20			* without specific prior written permission.
21			*
22			* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23			* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24			* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25			* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26			* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27			* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28			* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29			* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30			* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31			* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32			* SUCH DAMAGE.
33			*/
34
35			#include <stdio.h>
36			#include <stdlib.h>
37			#include <string.h>
38
39			#include <db.h>
40			#include "btree.h"
41
42			#define MINIMUM(a, b) (((a) < (b)) ? (a) : (b))
43
44			/*
45			* Big key/data code.
46			*
47			* Big key and data entries are stored on linked lists of pages. The initial
48			* reference is byte string stored with the key or data and is the page number
49			* and size. The actual record is stored in a chain of pages linked by the
50			* nextpg field of the PAGE header.
51			*
52			* The first page of the chain has a special property. If the record is used
53			* by an internal page, it cannot be deleted and the P_PRESERVE bit will be set
54			* in the header.
55			*
56			* XXX
57			* A single DBT is written to each chain, so a lot of space on the last page
58			* is wasted. This is a fairly major bug for some data sets.
59			*/
60
61			/*
62			* __OVFL_GET -- Get an overflow key/data item.
63			*
64			* Parameters:
65			* t: tree
66			* p: pointer to { pgno_t, u_int32_t }
67			* buf: storage address
68			* bufsz: storage size
69			*
70			* Returns:
71			* RET_ERROR, RET_SUCCESS
72			*/
73			int
74			__ovfl_get(BTREE t, void p, size_t ssz, void buf, size_t bufsz)
75			{
76			PAGE *h;
77			pgno_t pg;
78			size_t nb, plen;
79			u_int32_t sz;
80			void *tp;
81
82			memmove(&pg, p, sizeof(pgno_t));
83			memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t));
84			*ssz = sz;
85
86			#ifdef DEBUG
87			if (pg == P_INVALID \|\| sz == 0)
88			abort();
89			#endif
90			/* Make the buffer bigger as necessary. */
91			if (*bufsz < sz) {
92			tp = realloc(*buf, sz);
93			if (tp == NULL)
94			return (RET_ERROR);
95			*buf = tp;
96			*bufsz = sz;
97			}
98
99			/*
100			* Step through the linked list of pages, copying the data on each one
101			* into the buffer. Never copy more than the data's length.
102			*/
103			plen = t->bt_psize - BTDATAOFF;
104			for (p = buf;; p = (char )p + nb, pg = h->nextpg) {
105			if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
106			return (RET_ERROR);
107
108			nb = MINIMUM(sz, plen);
109			memmove(p, (char *)h + BTDATAOFF, nb);
110			mpool_put(t->bt_mp, h, 0);
111
112			if ((sz -= nb) == 0)
113			break;
114			}
115			return (RET_SUCCESS);
116			}
117
118			/*
119			* __OVFL_PUT -- Store an overflow key/data item.
120			*
121			* Parameters:
122			* t: tree
123			* data: DBT to store
124			* pgno: storage page number
125			*
126			* Returns:
127			* RET_ERROR, RET_SUCCESS
128			*/
129			int
130			__ovfl_put(BTREE t, const DBT dbt, pgno_t *pg)
131			{
132			PAGE h, last;
133			void *p;
134			pgno_t npg;
135			size_t nb, plen;
136			u_int32_t sz;
137
138			/*
139			* Allocate pages and copy the key/data record into them. Store the
140			* number of the first page in the chain.
141			*/
142			plen = t->bt_psize - BTDATAOFF;
143			for (last = NULL, p = dbt->data, sz = dbt->size;;
144			p = (char *)p + plen, last = h) {
145			if ((h = __bt_new(t, &npg)) == NULL)
146			return (RET_ERROR);
147
148			h->pgno = npg;
149			h->nextpg = h->prevpg = P_INVALID;
150			h->flags = P_OVERFLOW;
151			h->lower = h->upper = 0;
152
153			nb = MINIMUM(sz, plen);
154			memmove((char *)h + BTDATAOFF, p, nb);
155
156			if (last) {
157			last->nextpg = h->pgno;
158			mpool_put(t->bt_mp, last, MPOOL_DIRTY);
159			} else
160			*pg = h->pgno;
161
162			if ((sz -= nb) == 0) {
163			mpool_put(t->bt_mp, h, MPOOL_DIRTY);
164			break;
165			}
166			}
167			return (RET_SUCCESS);
168			}
169
170			/*
171			* __OVFL_DELETE -- Delete an overflow chain.
172			*
173			* Parameters:
174			* t: tree
175			* p: pointer to { pgno_t, u_int32_t }
176			*
177			* Returns:
178			* RET_ERROR, RET_SUCCESS
179			*/
180			int
181			__ovfl_delete(BTREE t, void p)
182			{
183			PAGE *h;
184			pgno_t pg;
185			size_t plen;
186			u_int32_t sz;
187
188			memmove(&pg, p, sizeof(pgno_t));
189			memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t));
190
191			#ifdef DEBUG
192			if (pg == P_INVALID \|\| sz == 0)
193			abort();
194			#endif
195			if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
196			return (RET_ERROR);
197
198			/* Don't delete chains used by internal pages. */
199			if (h->flags & P_PRESERVE) {
200			mpool_put(t->bt_mp, h, 0);
201			return (RET_SUCCESS);
202			}
203
204			/* Step through the chain, calling the free routine for each page. */
205			for (plen = t->bt_psize - BTDATAOFF;; sz -= plen) {
206			pg = h->nextpg;
207			__bt_free(t, h);
208			if (sz <= plen)
209			break;
210			if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
211			return (RET_ERROR);
212			}
213			return (RET_SUCCESS);
214			}