1 /*- 2 * Copyright (c) 1990, 1993, 1994 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Mike Olson. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. Neither the name of the University nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 * 32 * @(#)bt_overflow.c 8.5 (Berkeley) 7/16/94 33 * $DragonFly: src/lib/libc/db/btree/bt_overflow.c,v 1.3 2005/09/19 09:20:37 asmodai Exp $ 34 */ 35 36 #include <sys/param.h> 37 38 #include <stdio.h> 39 #include <stdlib.h> 40 #include <string.h> 41 42 #include <db.h> 43 #include "btree.h" 44 45 /* 46 * Big key/data code. 47 * 48 * Big key and data entries are stored on linked lists of pages. The initial 49 * reference is byte string stored with the key or data and is the page number 50 * and size. The actual record is stored in a chain of pages linked by the 51 * nextpg field of the PAGE header. 52 * 53 * The first page of the chain has a special property. If the record is used 54 * by an internal page, it cannot be deleted and the P_PRESERVE bit will be set 55 * in the header. 56 * 57 * XXX 58 * A single DBT is written to each chain, so a lot of space on the last page 59 * is wasted. This is a fairly major bug for some data sets. 60 */ 61 62 /* 63 * __OVFL_GET -- Get an overflow key/data item. 64 * 65 * Parameters: 66 * t: tree 67 * p: pointer to { pgno_t, u_int32_t } 68 * buf: storage address 69 * bufsz: storage size 70 * 71 * Returns: 72 * RET_ERROR, RET_SUCCESS 73 */ 74 int 75 __ovfl_get(t, p, ssz, buf, bufsz) 76 BTREE *t; 77 void *p; 78 size_t *ssz; 79 void **buf; 80 size_t *bufsz; 81 { 82 PAGE *h; 83 pgno_t pg; 84 size_t nb, plen; 85 u_int32_t sz; 86 87 memmove(&pg, p, sizeof(pgno_t)); 88 memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t)); 89 *ssz = sz; 90 91 #ifdef DEBUG 92 if (pg == P_INVALID || sz == 0) 93 abort(); 94 #endif 95 /* Make the buffer bigger as necessary. */ 96 if (*bufsz < sz) { 97 *buf = (char *)(*buf == NULL ? malloc(sz) : reallocf(*buf, sz)); 98 if (*buf == NULL) 99 return (RET_ERROR); 100 *bufsz = sz; 101 } 102 103 /* 104 * Step through the linked list of pages, copying the data on each one 105 * into the buffer. Never copy more than the data's length. 106 */ 107 plen = t->bt_psize - BTDATAOFF; 108 for (p = *buf;; p = (char *)p + nb, pg = h->nextpg) { 109 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 110 return (RET_ERROR); 111 112 nb = MIN(sz, plen); 113 memmove(p, (char *)h + BTDATAOFF, nb); 114 mpool_put(t->bt_mp, h, 0); 115 116 if ((sz -= nb) == 0) 117 break; 118 } 119 return (RET_SUCCESS); 120 } 121 122 /* 123 * __OVFL_PUT -- Store an overflow key/data item. 124 * 125 * Parameters: 126 * t: tree 127 * data: DBT to store 128 * pgno: storage page number 129 * 130 * Returns: 131 * RET_ERROR, RET_SUCCESS 132 */ 133 int 134 __ovfl_put(t, dbt, pg) 135 BTREE *t; 136 const DBT *dbt; 137 pgno_t *pg; 138 { 139 PAGE *h, *last; 140 void *p; 141 pgno_t npg; 142 size_t nb, plen; 143 u_int32_t sz; 144 145 /* 146 * Allocate pages and copy the key/data record into them. Store the 147 * number of the first page in the chain. 148 */ 149 plen = t->bt_psize - BTDATAOFF; 150 for (last = NULL, p = dbt->data, sz = dbt->size;; 151 p = (char *)p + plen, last = h) { 152 if ((h = __bt_new(t, &npg)) == NULL) 153 return (RET_ERROR); 154 155 h->pgno = npg; 156 h->nextpg = h->prevpg = P_INVALID; 157 h->flags = P_OVERFLOW; 158 h->lower = h->upper = 0; 159 160 nb = MIN(sz, plen); 161 memmove((char *)h + BTDATAOFF, p, nb); 162 163 if (last) { 164 last->nextpg = h->pgno; 165 mpool_put(t->bt_mp, last, MPOOL_DIRTY); 166 } else 167 *pg = h->pgno; 168 169 if ((sz -= nb) == 0) { 170 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 171 break; 172 } 173 } 174 return (RET_SUCCESS); 175 } 176 177 /* 178 * __OVFL_DELETE -- Delete an overflow chain. 179 * 180 * Parameters: 181 * t: tree 182 * p: pointer to { pgno_t, u_int32_t } 183 * 184 * Returns: 185 * RET_ERROR, RET_SUCCESS 186 */ 187 int 188 __ovfl_delete(t, p) 189 BTREE *t; 190 void *p; 191 { 192 PAGE *h; 193 pgno_t pg; 194 size_t plen; 195 u_int32_t sz; 196 197 memmove(&pg, p, sizeof(pgno_t)); 198 memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(u_int32_t)); 199 200 #ifdef DEBUG 201 if (pg == P_INVALID || sz == 0) 202 abort(); 203 #endif 204 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 205 return (RET_ERROR); 206 207 /* Don't delete chains used by internal pages. */ 208 if (h->flags & P_PRESERVE) { 209 mpool_put(t->bt_mp, h, 0); 210 return (RET_SUCCESS); 211 } 212 213 /* Step through the chain, calling the free routine for each page. */ 214 for (plen = t->bt_psize - BTDATAOFF;; sz -= plen) { 215 pg = h->nextpg; 216 __bt_free(t, h); 217 if (sz <= plen) 218 break; 219 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 220 return (RET_ERROR); 221 } 222 return (RET_SUCCESS); 223 } 224