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