]>
Commit | Line | Data |
---|---|---|
71733723 RM |
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_put.c 8.8 (Berkeley) 7/26/94"; | |
39 | #endif /* LIBC_SCCS and not lint */ | |
40 | ||
41 | #include <sys/types.h> | |
42 | ||
43 | #include <errno.h> | |
44 | #include <stdio.h> | |
45 | #include <stdlib.h> | |
46 | #include <string.h> | |
47 | ||
48 | #include <db.h> | |
49 | #include "btree.h" | |
50 | ||
51 | static EPG *bt_fast __P((BTREE *, const DBT *, const DBT *, int *)); | |
52 | ||
53 | /* | |
54 | * __BT_PUT -- Add a btree item to the tree. | |
55 | * | |
56 | * Parameters: | |
57 | * dbp: pointer to access method | |
58 | * key: key | |
59 | * data: data | |
60 | * flag: R_NOOVERWRITE | |
61 | * | |
62 | * Returns: | |
63 | * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key is already in the | |
64 | * tree and R_NOOVERWRITE specified. | |
65 | */ | |
66 | int | |
67 | __bt_put(dbp, key, data, flags) | |
68 | const DB *dbp; | |
69 | DBT *key; | |
70 | const DBT *data; | |
71 | u_int flags; | |
72 | { | |
73 | BTREE *t; | |
74 | DBT tkey, tdata; | |
75 | EPG *e; | |
76 | PAGE *h; | |
77 | indx_t index, nxtindex; | |
78 | pgno_t pg; | |
79 | u_int32_t nbytes; | |
80 | int dflags, exact, status; | |
81 | char *dest, db[NOVFLSIZE], kb[NOVFLSIZE]; | |
82 | ||
83 | t = dbp->internal; | |
84 | ||
85 | /* Toss any page pinned across calls. */ | |
86 | if (t->bt_pinned != NULL) { | |
87 | mpool_put(t->bt_mp, t->bt_pinned, 0); | |
88 | t->bt_pinned = NULL; | |
89 | } | |
90 | ||
91 | /* Check for change to a read-only tree. */ | |
92 | if (F_ISSET(t, B_RDONLY)) { | |
93 | errno = EPERM; | |
94 | return (RET_ERROR); | |
95 | } | |
96 | ||
97 | switch (flags) { | |
98 | case 0: | |
99 | case R_NOOVERWRITE: | |
100 | break; | |
101 | case R_CURSOR: | |
102 | /* | |
103 | * If flags is R_CURSOR, put the cursor. Must already | |
104 | * have started a scan and not have already deleted it. | |
105 | */ | |
106 | if (F_ISSET(&t->bt_cursor, CURS_INIT) && | |
107 | !F_ISSET(&t->bt_cursor, | |
108 | CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE)) | |
109 | break; | |
110 | /* FALLTHROUGH */ | |
111 | default: | |
112 | errno = EINVAL; | |
113 | return (RET_ERROR); | |
114 | } | |
115 | ||
116 | /* | |
117 | * If the key/data pair won't fit on a page, store it on overflow | |
118 | * pages. Only put the key on the overflow page if the pair are | |
119 | * still too big after moving the data to an overflow page. | |
120 | * | |
121 | * XXX | |
122 | * If the insert fails later on, the overflow pages aren't recovered. | |
123 | */ | |
124 | dflags = 0; | |
125 | if (key->size + data->size > t->bt_ovflsize) { | |
126 | if (key->size > t->bt_ovflsize) { | |
127 | storekey: if (__ovfl_put(t, key, &pg) == RET_ERROR) | |
128 | return (RET_ERROR); | |
129 | tkey.data = kb; | |
130 | tkey.size = NOVFLSIZE; | |
131 | memmove(kb, &pg, sizeof(pgno_t)); | |
132 | memmove(kb + sizeof(pgno_t), | |
133 | &key->size, sizeof(u_int32_t)); | |
134 | dflags |= P_BIGKEY; | |
135 | key = &tkey; | |
136 | } | |
137 | if (key->size + data->size > t->bt_ovflsize) { | |
138 | if (__ovfl_put(t, data, &pg) == RET_ERROR) | |
139 | return (RET_ERROR); | |
140 | tdata.data = db; | |
141 | tdata.size = NOVFLSIZE; | |
142 | memmove(db, &pg, sizeof(pgno_t)); | |
143 | memmove(db + sizeof(pgno_t), | |
144 | &data->size, sizeof(u_int32_t)); | |
145 | dflags |= P_BIGDATA; | |
146 | data = &tdata; | |
147 | } | |
148 | if (key->size + data->size > t->bt_ovflsize) | |
149 | goto storekey; | |
150 | } | |
151 | ||
152 | /* Replace the cursor. */ | |
153 | if (flags == R_CURSOR) { | |
154 | if ((h = mpool_get(t->bt_mp, t->bt_cursor.pg.pgno, 0)) == NULL) | |
155 | return (RET_ERROR); | |
156 | index = t->bt_cursor.pg.index; | |
157 | goto delete; | |
158 | } | |
159 | ||
160 | /* | |
161 | * Find the key to delete, or, the location at which to insert. | |
162 | * Bt_fast and __bt_search both pin the returned page. | |
163 | */ | |
164 | if (t->bt_order == NOT || (e = bt_fast(t, key, data, &exact)) == NULL) | |
165 | if ((e = __bt_search(t, key, &exact)) == NULL) | |
166 | return (RET_ERROR); | |
167 | h = e->page; | |
168 | index = e->index; | |
169 | ||
170 | /* | |
171 | * Add the key/data pair to the tree. If an identical key is already | |
172 | * in the tree, and R_NOOVERWRITE is set, an error is returned. If | |
173 | * R_NOOVERWRITE is not set, the key is either added (if duplicates are | |
174 | * permitted) or an error is returned. | |
175 | */ | |
176 | switch (flags) { | |
177 | case R_NOOVERWRITE: | |
178 | if (!exact) | |
179 | break; | |
180 | mpool_put(t->bt_mp, h, 0); | |
181 | return (RET_SPECIAL); | |
182 | default: | |
183 | if (!exact || !F_ISSET(t, B_NODUPS)) | |
184 | break; | |
185 | /* | |
186 | * !!! | |
187 | * Note, the delete may empty the page, so we need to put a | |
188 | * new entry into the page immediately. | |
189 | */ | |
190 | delete: if (__bt_dleaf(t, key, h, index) == RET_ERROR) { | |
191 | mpool_put(t->bt_mp, h, 0); | |
192 | return (RET_ERROR); | |
193 | } | |
194 | break; | |
195 | } | |
196 | ||
197 | /* | |
198 | * If not enough room, or the user has put a ceiling on the number of | |
199 | * keys permitted in the page, split the page. The split code will | |
200 | * insert the key and data and unpin the current page. If inserting | |
201 | * into the offset array, shift the pointers up. | |
202 | */ | |
203 | nbytes = NBLEAFDBT(key->size, data->size); | |
54d79e99 | 204 | if ((u_int32_t) (h->upper - h->lower) < nbytes + sizeof(indx_t)) { |
71733723 RM |
205 | if ((status = __bt_split(t, h, key, |
206 | data, dflags, nbytes, index)) != RET_SUCCESS) | |
207 | return (status); | |
208 | goto success; | |
209 | } | |
210 | ||
211 | if (index < (nxtindex = NEXTINDEX(h))) | |
212 | memmove(h->linp + index + 1, h->linp + index, | |
213 | (nxtindex - index) * sizeof(indx_t)); | |
214 | h->lower += sizeof(indx_t); | |
215 | ||
216 | h->linp[index] = h->upper -= nbytes; | |
217 | dest = (char *)h + h->upper; | |
218 | WR_BLEAF(dest, key, data, dflags); | |
219 | ||
220 | /* If the cursor is on this page, adjust it as necessary. */ | |
221 | if (F_ISSET(&t->bt_cursor, CURS_INIT) && | |
222 | !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && | |
223 | t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index >= index) | |
224 | ++t->bt_cursor.pg.index; | |
225 | ||
226 | if (t->bt_order == NOT) | |
227 | if (h->nextpg == P_INVALID) { | |
228 | if (index == NEXTINDEX(h) - 1) { | |
229 | t->bt_order = FORWARD; | |
230 | t->bt_last.index = index; | |
231 | t->bt_last.pgno = h->pgno; | |
232 | } | |
233 | } else if (h->prevpg == P_INVALID) { | |
234 | if (index == 0) { | |
235 | t->bt_order = BACK; | |
236 | t->bt_last.index = 0; | |
237 | t->bt_last.pgno = h->pgno; | |
238 | } | |
239 | } | |
240 | ||
241 | mpool_put(t->bt_mp, h, MPOOL_DIRTY); | |
242 | ||
243 | success: | |
244 | if (flags == R_SETCURSOR) | |
245 | __bt_setcur(t, e->page->pgno, e->index); | |
246 | ||
247 | F_SET(t, B_MODIFIED); | |
248 | return (RET_SUCCESS); | |
249 | } | |
250 | ||
251 | #ifdef STATISTICS | |
252 | u_long bt_cache_hit, bt_cache_miss; | |
253 | #endif | |
254 | ||
255 | /* | |
256 | * BT_FAST -- Do a quick check for sorted data. | |
257 | * | |
258 | * Parameters: | |
259 | * t: tree | |
260 | * key: key to insert | |
261 | * | |
262 | * Returns: | |
263 | * EPG for new record or NULL if not found. | |
264 | */ | |
265 | static EPG * | |
266 | bt_fast(t, key, data, exactp) | |
267 | BTREE *t; | |
268 | const DBT *key, *data; | |
269 | int *exactp; | |
270 | { | |
271 | PAGE *h; | |
272 | u_int32_t nbytes; | |
273 | int cmp; | |
274 | ||
275 | if ((h = mpool_get(t->bt_mp, t->bt_last.pgno, 0)) == NULL) { | |
276 | t->bt_order = NOT; | |
277 | return (NULL); | |
278 | } | |
279 | t->bt_cur.page = h; | |
280 | t->bt_cur.index = t->bt_last.index; | |
281 | ||
282 | /* | |
283 | * If won't fit in this page or have too many keys in this page, | |
284 | * have to search to get split stack. | |
285 | */ | |
286 | nbytes = NBLEAFDBT(key->size, data->size); | |
54d79e99 | 287 | if ((u_int32_t) (h->upper - h->lower) < nbytes + sizeof(indx_t)) |
71733723 RM |
288 | goto miss; |
289 | ||
290 | if (t->bt_order == FORWARD) { | |
291 | if (t->bt_cur.page->nextpg != P_INVALID) | |
292 | goto miss; | |
293 | if (t->bt_cur.index != NEXTINDEX(h) - 1) | |
294 | goto miss; | |
295 | if ((cmp = __bt_cmp(t, key, &t->bt_cur)) < 0) | |
296 | goto miss; | |
297 | t->bt_last.index = cmp ? ++t->bt_cur.index : t->bt_cur.index; | |
298 | } else { | |
299 | if (t->bt_cur.page->prevpg != P_INVALID) | |
300 | goto miss; | |
301 | if (t->bt_cur.index != 0) | |
302 | goto miss; | |
303 | if ((cmp = __bt_cmp(t, key, &t->bt_cur)) > 0) | |
304 | goto miss; | |
305 | t->bt_last.index = 0; | |
306 | } | |
307 | *exactp = cmp == 0; | |
308 | #ifdef STATISTICS | |
309 | ++bt_cache_hit; | |
310 | #endif | |
311 | return (&t->bt_cur); | |
312 | ||
313 | miss: | |
314 | #ifdef STATISTICS | |
315 | ++bt_cache_miss; | |
316 | #endif | |
317 | t->bt_order = NOT; | |
318 | mpool_put(t->bt_mp, h, 0); | |
319 | return (NULL); | |
320 | } |