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