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) 12 static char sccsid[] = "@(#)bt_put.c 5.3 (Berkeley) 02/22/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <sys/types.h> 16 #include <db.h> 17 #include <stdlib.h> 18 #include <string.h> 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 85 /* okay, try again (empty the stack first, though) */ 86 while (_bt_pop((BTREE) t) != P_NONE) 87 continue; 88 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 } 287