Commit | Line | Data |
---|---|---|
10b2618c 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) | |
fb91cf55 | 12 | static char sccsid[] = "@(#)bt_put.c 5.3 (Berkeley) %G%"; |
10b2618c MO |
13 | #endif /* LIBC_SCCS and not lint */ |
14 | ||
15 | #include <sys/types.h> | |
16 | #include <db.h> | |
fb91cf55 KB |
17 | #include <stdlib.h> |
18 | #include <string.h> | |
10b2618c MO |
19 | #include "btree.h" |
20 | ||
21 | /* | |
22 | * _BT_INSERT -- Insert a new user datum in the btree. | |
23 | * | |
24 | * This routine is called by bt_put, the public interface, once the | |
25 | * location for the new item is known. We do the work here, and | |
26 | * handle splits if necessary. | |
27 | * | |
28 | * Parameters: | |
29 | * t -- btree in which to do the insertion. | |
30 | * item -- BTITEM describing location of new datum | |
31 | * key -- key to insert | |
32 | * data -- data associated with key | |
33 | * flag -- magic cookie passed recursively to bt_put if we | |
34 | * have to do a split | |
35 | * | |
36 | * Returns: | |
37 | * RET_SUCCESS, RET_ERROR. | |
38 | */ | |
39 | ||
40 | int | |
41 | _bt_insert(t, item, key, data, flag) | |
42 | BTREE_P t; | |
43 | BTITEM *item; | |
44 | DBT *key; | |
45 | DBT *data; | |
46 | int flag; | |
47 | { | |
48 | index_t index; | |
49 | BTHEADER *h; | |
50 | DATUM *d; | |
51 | int nbytes; | |
52 | int status; | |
53 | pgno_t pgno; | |
54 | int keysize, datasize; | |
55 | int bigkey, bigdata; | |
56 | ||
57 | if (_bt_getpage(t, item->bti_pgno) == RET_ERROR) | |
58 | return (RET_ERROR); | |
59 | h = t->bt_curpage; | |
60 | ||
61 | if (TOOBIG(t, data->size)) { | |
62 | bigdata = TRUE; | |
63 | datasize = sizeof(pgno_t); | |
64 | } else { | |
65 | bigdata = FALSE; | |
66 | datasize = data->size; | |
67 | } | |
68 | ||
69 | if (TOOBIG(t, key->size)) { | |
70 | bigkey = TRUE; | |
71 | keysize = sizeof(pgno_t); | |
72 | } else { | |
73 | bigkey = FALSE; | |
74 | keysize = key->size; | |
75 | } | |
76 | ||
77 | nbytes = keysize + datasize + (sizeof(DATUM) - sizeof(char)); | |
78 | nbytes = LONGALIGN(nbytes) + sizeof(index_t); | |
79 | ||
80 | /* if there's not enough room here, split the page */ | |
81 | if ((h->h_upper - h->h_lower) < nbytes) { | |
82 | if (_bt_split(t) == RET_ERROR) | |
83 | return (RET_ERROR); | |
84 | ||
1a18d2ca MO |
85 | /* okay, try again (empty the stack first, though) */ |
86 | while (_bt_pop((BTREE) t) != P_NONE) | |
87 | continue; | |
88 | ||
10b2618c MO |
89 | return (bt_put((BTREE) t, key, data, flag)); |
90 | } | |
91 | ||
92 | /* put together a leaf page datum from the key/data pair */ | |
93 | index = item->bti_index; | |
94 | nbytes = keysize + datasize + (sizeof(DATUM) - sizeof(char)); | |
95 | ||
96 | if ((d = (DATUM *) malloc((unsigned) nbytes)) == (DATUM *) NULL) | |
97 | return (RET_ERROR); | |
98 | ||
99 | d->d_ksize = keysize; | |
100 | d->d_dsize = datasize; | |
101 | d->d_flags = 0; | |
102 | ||
103 | if (bigkey) { | |
104 | if (_bt_indirect(t, key, &pgno) == RET_ERROR) | |
105 | return (RET_ERROR); | |
106 | (void) bcopy((char *) &pgno, &(d->d_bytes[0]), sizeof(pgno)); | |
107 | d->d_flags |= D_BIGKEY; | |
108 | if (_bt_getpage(t, item->bti_pgno) == RET_ERROR) | |
109 | return (RET_ERROR); | |
110 | } else { | |
111 | if (d->d_ksize > 0) { | |
112 | (void) bcopy((char *) key->data, | |
113 | (char *) &(d->d_bytes[0]), | |
114 | (int) d->d_ksize); | |
115 | } | |
116 | } | |
117 | ||
118 | if (bigdata) { | |
119 | if (_bt_indirect(t, data, &pgno) == RET_ERROR) | |
120 | return (RET_ERROR); | |
121 | (void) bcopy((char *) &pgno, | |
122 | &(d->d_bytes[keysize]), | |
123 | sizeof(pgno)); | |
124 | d->d_flags |= D_BIGDATA; | |
125 | if (_bt_getpage(t, item->bti_pgno) == RET_ERROR) | |
126 | return (RET_ERROR); | |
127 | } else { | |
128 | if (d->d_dsize > 0) { | |
129 | (void) bcopy((char *) data->data, | |
130 | (char *) &(d->d_bytes[keysize]), | |
131 | (int) d->d_dsize); | |
132 | } | |
133 | } | |
134 | ||
135 | /* do the insertion */ | |
136 | status = _bt_insertat(t, (char *) d, index); | |
137 | ||
138 | (void) free((char *) d); | |
139 | ||
140 | return (status); | |
141 | } | |
142 | ||
143 | /* | |
144 | * _BT_INSERTI -- Insert IDATUM on current page in the btree. | |
145 | * | |
146 | * This routine handles insertions to internal pages after splits | |
147 | * lower in the tree. On entry, t->bt_curpage is the page to get | |
148 | * the new IDATUM. We are also given pgno, the page number of the | |
149 | * IDATUM that is immediately left of the new IDATUM's position. | |
150 | * This guarantees that the IDATUM for the right half of the page | |
151 | * after a split goes next to the IDATUM for its left half. | |
152 | * | |
153 | * Parameters: | |
154 | * t -- tree in which to do insertion. | |
155 | * id -- new IDATUM to insert | |
156 | * pgno -- page number of IDATUM left of id's position | |
157 | * | |
158 | * Returns: | |
159 | * RET_SUCCESS, RET_ERROR. | |
160 | */ | |
161 | ||
162 | int | |
163 | _bt_inserti(t, id, pgno) | |
164 | BTREE_P t; | |
165 | IDATUM *id; | |
166 | pgno_t pgno; | |
167 | { | |
168 | BTHEADER *h = t->bt_curpage; | |
169 | index_t next, i; | |
170 | IDATUM *idx; | |
171 | char *key; | |
172 | pgno_t chain; | |
173 | int free_key; | |
174 | int ignore; | |
175 | ||
176 | if (id->i_flags & D_BIGKEY) { | |
177 | free_key = TRUE; | |
178 | bcopy(&(id->i_bytes[0]), (char *) &chain, sizeof(chain)); | |
179 | if (_bt_getbig(t, chain, &key, &ignore) == RET_ERROR) | |
180 | return (RET_ERROR); | |
181 | } else { | |
182 | free_key = FALSE; | |
183 | key = &(id->i_bytes[0]); | |
184 | } | |
185 | i = _bt_binsrch(t, key); | |
186 | ||
187 | next = NEXTINDEX(h); | |
188 | while (i < next && _bt_cmp(t, key, i) >= 0) | |
189 | i++; | |
190 | ||
191 | if (free_key) | |
192 | (void) free(key); | |
193 | ||
194 | /* okay, now we're close; find adjacent IDATUM */ | |
195 | for (;;) { | |
196 | idx = (IDATUM *) GETDATUM(h,i); | |
197 | if (idx->i_pgno == pgno) { | |
198 | i++; | |
199 | break; | |
200 | } | |
201 | --i; | |
202 | } | |
203 | ||
204 | /* correctly positioned, do the insertion */ | |
205 | return (_bt_insertat(t, (char *) id, i)); | |
206 | } | |
207 | ||
208 | /* | |
209 | * _BT_INSERTAT -- Insert a datum at a given location on the current page. | |
210 | * | |
211 | * This routine does insertions on both leaf and internal pages. | |
212 | * | |
213 | * Parameters: | |
214 | * t -- tree in which to do insertion. | |
215 | * p -- DATUM or IDATUM to insert. | |
216 | * index -- index in line pointer array to put this item. | |
217 | * | |
218 | * Returns: | |
219 | * RET_SUCCESS, RET_ERROR. | |
220 | * | |
221 | * Side Effects: | |
222 | * Will rearrange line pointers to make space for the new | |
223 | * entry. This means that any scans currently active are | |
224 | * invalid after this. | |
225 | * | |
226 | * Warnings: | |
227 | * There must be sufficient room for the new item on the page. | |
228 | */ | |
229 | ||
230 | int | |
231 | _bt_insertat(t, p, index) | |
232 | BTREE_P t; | |
233 | char *p; | |
234 | index_t index; | |
235 | { | |
236 | IDATUM *id = (IDATUM *) p; | |
237 | DATUM *d = (DATUM *) p; | |
238 | BTHEADER *h; | |
239 | CURSOR *c; | |
240 | index_t nxtindex; | |
241 | char *src, *dest; | |
242 | int nbytes; | |
243 | ||
244 | /* insertion may confuse an active scan. fix it. */ | |
245 | c = &(t->bt_cursor); | |
246 | if (t->bt_flags & BTF_SEQINIT && t->bt_curpage->h_pgno == c->c_pgno) | |
247 | if (_bt_fixscan(t, index, d, INSERT) == RET_ERROR) | |
248 | return (RET_ERROR); | |
249 | ||
250 | h = t->bt_curpage; | |
251 | nxtindex = (index_t) NEXTINDEX(h); | |
252 | ||
253 | /* | |
254 | * If we're inserting at the middle of the line pointer array, | |
255 | * copy pointers that will follow the new one up on the page. | |
256 | */ | |
257 | ||
258 | if (index < nxtindex) { | |
259 | src = (char *) &(h->h_linp[index]); | |
260 | dest = (char *) &(h->h_linp[index + 1]); | |
261 | nbytes = (h->h_lower - (src - ((char *) h))) | |
262 | + sizeof(h->h_linp[0]); | |
263 | (void) bcopy(src, dest, nbytes); | |
264 | } | |
265 | ||
266 | /* compute size and copy data to page */ | |
267 | if (h->h_flags & F_LEAF) { | |
268 | nbytes = d->d_ksize + d->d_dsize | |
269 | + (sizeof(DATUM) - sizeof(char)); | |
270 | } else { | |
271 | nbytes = id->i_size + (sizeof(IDATUM) - sizeof(char)); | |
272 | } | |
273 | dest = (((char *) h) + h->h_upper) - LONGALIGN(nbytes); | |
274 | (void) bcopy((char *) p, dest, nbytes); | |
275 | ||
276 | /* update statistics */ | |
277 | dest -= (int) h; | |
278 | h->h_linp[index] = (index_t) dest; | |
279 | h->h_upper = (index_t) dest; | |
280 | h->h_lower += sizeof(index_t); | |
281 | ||
282 | /* we're done */ | |
283 | h->h_flags |= F_DIRTY; | |
284 | ||
285 | return (RET_SUCCESS); | |
286 | } |