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.1 (Berkeley) 01/23/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 */ 84 return (bt_put((BTREE) t, key, data, flag)); 85 } 86 87 /* put together a leaf page datum from the key/data pair */ 88 index = item->bti_index; 89 nbytes = keysize + datasize + (sizeof(DATUM) - sizeof(char)); 90 91 if ((d = (DATUM *) malloc((unsigned) nbytes)) == (DATUM *) NULL) 92 return (RET_ERROR); 93 94 d->d_ksize = keysize; 95 d->d_dsize = datasize; 96 d->d_flags = 0; 97 98 if (bigkey) { 99 if (_bt_indirect(t, key, &pgno) == RET_ERROR) 100 return (RET_ERROR); 101 (void) bcopy((char *) &pgno, &(d->d_bytes[0]), sizeof(pgno)); 102 d->d_flags |= D_BIGKEY; 103 if (_bt_getpage(t, item->bti_pgno) == RET_ERROR) 104 return (RET_ERROR); 105 } else { 106 if (d->d_ksize > 0) { 107 (void) bcopy((char *) key->data, 108 (char *) &(d->d_bytes[0]), 109 (int) d->d_ksize); 110 } 111 } 112 113 if (bigdata) { 114 if (_bt_indirect(t, data, &pgno) == RET_ERROR) 115 return (RET_ERROR); 116 (void) bcopy((char *) &pgno, 117 &(d->d_bytes[keysize]), 118 sizeof(pgno)); 119 d->d_flags |= D_BIGDATA; 120 if (_bt_getpage(t, item->bti_pgno) == RET_ERROR) 121 return (RET_ERROR); 122 } else { 123 if (d->d_dsize > 0) { 124 (void) bcopy((char *) data->data, 125 (char *) &(d->d_bytes[keysize]), 126 (int) d->d_dsize); 127 } 128 } 129 130 /* do the insertion */ 131 status = _bt_insertat(t, (char *) d, index); 132 133 (void) free((char *) d); 134 135 return (status); 136 } 137 138 /* 139 * _BT_INSERTI -- Insert IDATUM on current page in the btree. 140 * 141 * This routine handles insertions to internal pages after splits 142 * lower in the tree. On entry, t->bt_curpage is the page to get 143 * the new IDATUM. We are also given pgno, the page number of the 144 * IDATUM that is immediately left of the new IDATUM's position. 145 * This guarantees that the IDATUM for the right half of the page 146 * after a split goes next to the IDATUM for its left half. 147 * 148 * Parameters: 149 * t -- tree in which to do insertion. 150 * id -- new IDATUM to insert 151 * pgno -- page number of IDATUM left of id's position 152 * 153 * Returns: 154 * RET_SUCCESS, RET_ERROR. 155 */ 156 157 int 158 _bt_inserti(t, id, pgno) 159 BTREE_P t; 160 IDATUM *id; 161 pgno_t pgno; 162 { 163 BTHEADER *h = t->bt_curpage; 164 index_t next, i; 165 IDATUM *idx; 166 char *key; 167 pgno_t chain; 168 int free_key; 169 int ignore; 170 171 if (id->i_flags & D_BIGKEY) { 172 free_key = TRUE; 173 bcopy(&(id->i_bytes[0]), (char *) &chain, sizeof(chain)); 174 if (_bt_getbig(t, chain, &key, &ignore) == RET_ERROR) 175 return (RET_ERROR); 176 } else { 177 free_key = FALSE; 178 key = &(id->i_bytes[0]); 179 } 180 i = _bt_binsrch(t, key); 181 182 next = NEXTINDEX(h); 183 while (i < next && _bt_cmp(t, key, i) >= 0) 184 i++; 185 186 if (free_key) 187 (void) free(key); 188 189 /* okay, now we're close; find adjacent IDATUM */ 190 for (;;) { 191 idx = (IDATUM *) GETDATUM(h,i); 192 if (idx->i_pgno == pgno) { 193 i++; 194 break; 195 } 196 --i; 197 } 198 199 /* correctly positioned, do the insertion */ 200 return (_bt_insertat(t, (char *) id, i)); 201 } 202 203 /* 204 * _BT_INSERTAT -- Insert a datum at a given location on the current page. 205 * 206 * This routine does insertions on both leaf and internal pages. 207 * 208 * Parameters: 209 * t -- tree in which to do insertion. 210 * p -- DATUM or IDATUM to insert. 211 * index -- index in line pointer array to put this item. 212 * 213 * Returns: 214 * RET_SUCCESS, RET_ERROR. 215 * 216 * Side Effects: 217 * Will rearrange line pointers to make space for the new 218 * entry. This means that any scans currently active are 219 * invalid after this. 220 * 221 * Warnings: 222 * There must be sufficient room for the new item on the page. 223 */ 224 225 int 226 _bt_insertat(t, p, index) 227 BTREE_P t; 228 char *p; 229 index_t index; 230 { 231 IDATUM *id = (IDATUM *) p; 232 DATUM *d = (DATUM *) p; 233 BTHEADER *h; 234 CURSOR *c; 235 index_t nxtindex; 236 char *src, *dest; 237 int nbytes; 238 239 /* insertion may confuse an active scan. fix it. */ 240 c = &(t->bt_cursor); 241 if (t->bt_flags & BTF_SEQINIT && t->bt_curpage->h_pgno == c->c_pgno) 242 if (_bt_fixscan(t, index, d, INSERT) == RET_ERROR) 243 return (RET_ERROR); 244 245 h = t->bt_curpage; 246 nxtindex = (index_t) NEXTINDEX(h); 247 248 /* 249 * If we're inserting at the middle of the line pointer array, 250 * copy pointers that will follow the new one up on the page. 251 */ 252 253 if (index < nxtindex) { 254 src = (char *) &(h->h_linp[index]); 255 dest = (char *) &(h->h_linp[index + 1]); 256 nbytes = (h->h_lower - (src - ((char *) h))) 257 + sizeof(h->h_linp[0]); 258 (void) bcopy(src, dest, nbytes); 259 } 260 261 /* compute size and copy data to page */ 262 if (h->h_flags & F_LEAF) { 263 nbytes = d->d_ksize + d->d_dsize 264 + (sizeof(DATUM) - sizeof(char)); 265 } else { 266 nbytes = id->i_size + (sizeof(IDATUM) - sizeof(char)); 267 } 268 dest = (((char *) h) + h->h_upper) - LONGALIGN(nbytes); 269 (void) bcopy((char *) p, dest, nbytes); 270 271 /* update statistics */ 272 dest -= (int) h; 273 h->h_linp[index] = (index_t) dest; 274 h->h_upper = (index_t) dest; 275 h->h_lower += sizeof(index_t); 276 277 /* we're done */ 278 h->h_flags |= F_DIRTY; 279 280 return (RET_SUCCESS); 281 } 282