]>
Commit | Line | Data |
---|---|---|
e9ce8d39 A |
1 | /* |
2 | * Copyright (c) 1999 Apple Computer, Inc. All rights reserved. | |
3 | * | |
4 | * @APPLE_LICENSE_HEADER_START@ | |
5 | * | |
6 | * The contents of this file constitute Original Code as defined in and | |
7 | * are subject to the Apple Public Source License Version 1.1 (the | |
8 | * "License"). You may not use this file except in compliance with the | |
9 | * License. Please obtain a copy of the License at | |
10 | * http://www.apple.com/publicsource and read it before using this file. | |
11 | * | |
12 | * This Original Code and all software distributed under the License are | |
13 | * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER | |
14 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, | |
15 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, | |
16 | * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the | |
17 | * License for the specific language governing rights and limitations | |
18 | * under the License. | |
19 | * | |
20 | * @APPLE_LICENSE_HEADER_END@ | |
21 | */ | |
22 | /* | |
23 | * Copyright (c) 1990, 1993 | |
24 | * The Regents of the University of California. All rights reserved. | |
25 | * | |
26 | * This code is derived from software contributed to Berkeley by | |
27 | * Mike Olson. | |
28 | * | |
29 | * Redistribution and use in source and binary forms, with or without | |
30 | * modification, are permitted provided that the following conditions | |
31 | * are met: | |
32 | * 1. Redistributions of source code must retain the above copyright | |
33 | * notice, this list of conditions and the following disclaimer. | |
34 | * 2. Redistributions in binary form must reproduce the above copyright | |
35 | * notice, this list of conditions and the following disclaimer in the | |
36 | * documentation and/or other materials provided with the distribution. | |
37 | * 3. All advertising materials mentioning features or use of this software | |
38 | * must display the following acknowledgement: | |
39 | * This product includes software developed by the University of | |
40 | * California, Berkeley and its contributors. | |
41 | * 4. Neither the name of the University nor the names of its contributors | |
42 | * may be used to endorse or promote products derived from this software | |
43 | * without specific prior written permission. | |
44 | * | |
45 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | |
46 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
47 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
48 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
49 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
50 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
51 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
52 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
53 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
54 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
55 | * SUCH DAMAGE. | |
56 | */ | |
57 | ||
58 | ||
59 | #include <sys/types.h> | |
60 | ||
61 | #include <errno.h> | |
62 | #include <stdio.h> | |
63 | #include <stdlib.h> | |
64 | #include <string.h> | |
65 | ||
66 | #include <db.h> | |
67 | #include "btree.h" | |
68 | ||
69 | static EPG *bt_fast __P((BTREE *, const DBT *, const DBT *, int *)); | |
70 | ||
71 | /* | |
72 | * __BT_PUT -- Add a btree item to the tree. | |
73 | * | |
74 | * Parameters: | |
75 | * dbp: pointer to access method | |
76 | * key: key | |
77 | * data: data | |
78 | * flag: R_NOOVERWRITE | |
79 | * | |
80 | * Returns: | |
81 | * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key is already in the | |
82 | * tree and R_NOOVERWRITE specified. | |
83 | */ | |
84 | int | |
85 | __bt_put(dbp, key, data, flags) | |
86 | const DB *dbp; | |
87 | DBT *key; | |
88 | const DBT *data; | |
89 | u_int flags; | |
90 | { | |
91 | BTREE *t; | |
92 | DBT tkey, tdata; | |
93 | EPG *e; | |
94 | PAGE *h; | |
95 | indx_t index, nxtindex; | |
96 | pgno_t pg; | |
97 | size_t nbytes; | |
98 | int dflags, exact, status; | |
99 | char *dest, db[NOVFLSIZE], kb[NOVFLSIZE]; | |
100 | ||
101 | t = dbp->internal; | |
102 | ||
103 | /* Toss any page pinned across calls. */ | |
104 | if (t->bt_pinned != NULL) { | |
105 | mpool_put(t->bt_mp, t->bt_pinned, 0); | |
106 | t->bt_pinned = NULL; | |
107 | } | |
108 | ||
109 | switch (flags) { | |
110 | case R_CURSOR: | |
111 | if (!ISSET(t, B_SEQINIT)) | |
112 | goto einval; | |
113 | if (ISSET(t, B_DELCRSR)) | |
114 | goto einval; | |
115 | break; | |
116 | case 0: | |
117 | case R_NOOVERWRITE: | |
118 | break; | |
119 | default: | |
120 | einval: errno = EINVAL; | |
121 | return (RET_ERROR); | |
122 | } | |
123 | ||
124 | if (ISSET(t, B_RDONLY)) { | |
125 | errno = EPERM; | |
126 | return (RET_ERROR); | |
127 | } | |
128 | ||
129 | /* | |
130 | * If the key/data won't fit on a page, store it on indirect pages. | |
131 | * Only store the key on the overflow page if it's too big after the | |
132 | * data is on an overflow page. | |
133 | * | |
134 | * XXX | |
135 | * If the insert fails later on, these pages aren't recovered. | |
136 | */ | |
137 | dflags = 0; | |
138 | if (key->size + data->size > t->bt_ovflsize) { | |
139 | if (key->size > t->bt_ovflsize) { | |
140 | storekey: if (__ovfl_put(t, key, &pg) == RET_ERROR) | |
141 | return (RET_ERROR); | |
142 | tkey.data = kb; | |
143 | tkey.size = NOVFLSIZE; | |
144 | memmove(kb, &pg, sizeof(pgno_t)); | |
145 | memmove(kb + sizeof(pgno_t), | |
146 | &key->size, sizeof(size_t)); | |
147 | dflags |= P_BIGKEY; | |
148 | key = &tkey; | |
149 | } | |
150 | if (key->size + data->size > t->bt_ovflsize) { | |
151 | if (__ovfl_put(t, data, &pg) == RET_ERROR) | |
152 | return (RET_ERROR); | |
153 | tdata.data = db; | |
154 | tdata.size = NOVFLSIZE; | |
155 | memmove(db, &pg, sizeof(pgno_t)); | |
156 | memmove(db + sizeof(pgno_t), | |
157 | &data->size, sizeof(size_t)); | |
158 | dflags |= P_BIGDATA; | |
159 | data = &tdata; | |
160 | } | |
161 | if (key->size + data->size > t->bt_ovflsize) | |
162 | goto storekey; | |
163 | } | |
164 | ||
165 | /* Replace the cursor. */ | |
166 | if (flags == R_CURSOR) { | |
167 | if ((h = mpool_get(t->bt_mp, t->bt_bcursor.pgno, 0)) == NULL) | |
168 | return (RET_ERROR); | |
169 | index = t->bt_bcursor.index; | |
170 | goto delete; | |
171 | } | |
172 | ||
173 | /* | |
174 | * Find the key to delete, or, the location at which to insert. Bt_fast | |
175 | * and __bt_search pin the returned page. | |
176 | */ | |
177 | if (t->bt_order == NOT || (e = bt_fast(t, key, data, &exact)) == NULL) | |
178 | if ((e = __bt_search(t, key, &exact)) == NULL) | |
179 | return (RET_ERROR); | |
180 | h = e->page; | |
181 | index = e->index; | |
182 | ||
183 | /* | |
184 | * Add the specified key/data pair to the tree. If an identical key | |
185 | * is already in the tree, and R_NOOVERWRITE is set, an error is | |
186 | * returned. If R_NOOVERWRITE is not set, the key is either added (if | |
187 | * duplicates are permitted) or an error is returned. | |
188 | * | |
189 | * Pages are split as required. | |
190 | */ | |
191 | switch (flags) { | |
192 | case R_NOOVERWRITE: | |
193 | if (!exact) | |
194 | break; | |
195 | /* | |
196 | * One special case is if the cursor references the record and | |
197 | * it's been flagged for deletion. Then, we delete the record, | |
198 | * leaving the cursor there -- this means that the inserted | |
199 | * record will not be seen in a cursor scan. | |
200 | */ | |
201 | if (ISSET(t, B_DELCRSR) && t->bt_bcursor.pgno == h->pgno && | |
202 | t->bt_bcursor.index == index) { | |
203 | CLR(t, B_DELCRSR); | |
204 | goto delete; | |
205 | } | |
206 | mpool_put(t->bt_mp, h, 0); | |
207 | return (RET_SPECIAL); | |
208 | default: | |
209 | if (!exact || !ISSET(t, B_NODUPS)) | |
210 | break; | |
211 | delete: if (__bt_dleaf(t, h, index) == RET_ERROR) { | |
212 | mpool_put(t->bt_mp, h, 0); | |
213 | return (RET_ERROR); | |
214 | } | |
215 | break; | |
216 | } | |
217 | ||
218 | /* | |
219 | * If not enough room, or the user has put a ceiling on the number of | |
220 | * keys permitted in the page, split the page. The split code will | |
221 | * insert the key and data and unpin the current page. If inserting | |
222 | * into the offset array, shift the pointers up. | |
223 | */ | |
224 | nbytes = NBLEAFDBT(key->size, data->size); | |
225 | if (h->upper - h->lower < nbytes + sizeof(indx_t)) { | |
226 | if ((status = __bt_split(t, h, key, | |
227 | data, dflags, nbytes, index)) != RET_SUCCESS) | |
228 | return (status); | |
229 | goto success; | |
230 | } | |
231 | ||
232 | if (index < (nxtindex = NEXTINDEX(h))) | |
233 | memmove(h->linp + index + 1, h->linp + index, | |
234 | (nxtindex - index) * sizeof(indx_t)); | |
235 | h->lower += sizeof(indx_t); | |
236 | ||
237 | h->linp[index] = h->upper -= nbytes; | |
238 | dest = (char *)h + h->upper; | |
239 | WR_BLEAF(dest, key, data, dflags); | |
240 | ||
241 | if (t->bt_order == NOT) | |
242 | if (h->nextpg == P_INVALID) { | |
243 | if (index == NEXTINDEX(h) - 1) { | |
244 | t->bt_order = FORWARD; | |
245 | t->bt_last.index = index; | |
246 | t->bt_last.pgno = h->pgno; | |
247 | } | |
248 | } else if (h->prevpg == P_INVALID) { | |
249 | if (index == 0) { | |
250 | t->bt_order = BACK; | |
251 | t->bt_last.index = 0; | |
252 | t->bt_last.pgno = h->pgno; | |
253 | } | |
254 | } | |
255 | ||
256 | mpool_put(t->bt_mp, h, MPOOL_DIRTY); | |
257 | ||
258 | success: | |
259 | if (flags == R_SETCURSOR) { | |
260 | t->bt_bcursor.pgno = e->page->pgno; | |
261 | t->bt_bcursor.index = e->index; | |
262 | } | |
263 | SET(t, B_MODIFIED); | |
264 | return (RET_SUCCESS); | |
265 | } | |
266 | ||
267 | #ifdef STATISTICS | |
268 | u_long bt_cache_hit, bt_cache_miss; | |
269 | #endif | |
270 | ||
271 | /* | |
272 | * BT_FAST -- Do a quick check for sorted data. | |
273 | * | |
274 | * Parameters: | |
275 | * t: tree | |
276 | * key: key to insert | |
277 | * | |
278 | * Returns: | |
279 | * EPG for new record or NULL if not found. | |
280 | */ | |
281 | static EPG * | |
282 | bt_fast(t, key, data, exactp) | |
283 | BTREE *t; | |
284 | const DBT *key, *data; | |
285 | int *exactp; | |
286 | { | |
287 | PAGE *h; | |
288 | size_t nbytes; | |
289 | int cmp; | |
290 | ||
291 | if ((h = mpool_get(t->bt_mp, t->bt_last.pgno, 0)) == NULL) { | |
292 | t->bt_order = NOT; | |
293 | return (NULL); | |
294 | } | |
295 | t->bt_cur.page = h; | |
296 | t->bt_cur.index = t->bt_last.index; | |
297 | ||
298 | /* | |
299 | * If won't fit in this page or have too many keys in this page, have | |
300 | * to search to get split stack. | |
301 | */ | |
302 | nbytes = NBLEAFDBT(key->size, data->size); | |
303 | if (h->upper - h->lower < nbytes + sizeof(indx_t)) | |
304 | goto miss; | |
305 | ||
306 | if (t->bt_order == FORWARD) { | |
307 | if (t->bt_cur.page->nextpg != P_INVALID) | |
308 | goto miss; | |
309 | if (t->bt_cur.index != NEXTINDEX(h) - 1) | |
310 | goto miss; | |
311 | if ((cmp = __bt_cmp(t, key, &t->bt_cur)) < 0) | |
312 | goto miss; | |
313 | t->bt_last.index = cmp ? ++t->bt_cur.index : t->bt_cur.index; | |
314 | } else { | |
315 | if (t->bt_cur.page->prevpg != P_INVALID) | |
316 | goto miss; | |
317 | if (t->bt_cur.index != 0) | |
318 | goto miss; | |
319 | if ((cmp = __bt_cmp(t, key, &t->bt_cur)) > 0) | |
320 | goto miss; | |
321 | t->bt_last.index = 0; | |
322 | } | |
323 | *exactp = cmp == 0; | |
324 | #ifdef STATISTICS | |
325 | ++bt_cache_hit; | |
326 | #endif | |
327 | return (&t->bt_cur); | |
328 | ||
329 | miss: | |
330 | #ifdef STATISTICS | |
331 | ++bt_cache_miss; | |
332 | #endif | |
333 | t->bt_order = NOT; | |
334 | mpool_put(t->bt_mp, h, 0); | |
335 | return (NULL); | |
336 | } |