1 /*- 2 * Copyright (c) 1990, 1993 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 * %sccs.include.redist.c% 9 */ 10 11 #if defined(LIBC_SCCS) && !defined(lint) 12 static char sccsid[] = "@(#)bt_overflow.c 8.1 (Berkeley) 06/04/93"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <sys/param.h> 16 17 #include <stdio.h> 18 #include <stdlib.h> 19 #include <string.h> 20 21 #include <db.h> 22 #include "btree.h" 23 24 /* 25 * Big key/data code. 26 * 27 * Big key and data entries are stored on linked lists of pages. The initial 28 * reference is byte string stored with the key or data and is the page number 29 * and size. The actual record is stored in a chain of pages linked by the 30 * nextpg field of the PAGE header. 31 * 32 * The first page of the chain has a special property. If the record is used 33 * by an internal page, it cannot be deleted and the P_PRESERVE bit will be set 34 * in the header. 35 * 36 * XXX 37 * A single DBT is written to each chain, so a lot of space on the last page 38 * is wasted. This is a fairly major bug for some data sets. 39 */ 40 41 /* 42 * __OVFL_GET -- Get an overflow key/data item. 43 * 44 * Parameters: 45 * t: tree 46 * p: pointer to { pgno_t, size_t } 47 * buf: storage address 48 * bufsz: storage size 49 * 50 * Returns: 51 * RET_ERROR, RET_SUCCESS 52 */ 53 int 54 __ovfl_get(t, p, ssz, buf, bufsz) 55 BTREE *t; 56 void *p; 57 size_t *ssz; 58 char **buf; 59 size_t *bufsz; 60 { 61 PAGE *h; 62 pgno_t pg; 63 size_t nb, plen, sz; 64 65 memmove(&pg, p, sizeof(pgno_t)); 66 memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(size_t)); 67 *ssz = sz; 68 69 #ifdef DEBUG 70 if (pg == P_INVALID || sz == 0) 71 abort(); 72 #endif 73 /* Make the buffer bigger as necessary. */ 74 if (*bufsz < sz) { 75 if ((*buf = realloc(*buf, sz)) == NULL) 76 return (RET_ERROR); 77 *bufsz = sz; 78 } 79 80 /* 81 * Step through the linked list of pages, copying the data on each one 82 * into the buffer. Never copy more than the data's length. 83 */ 84 plen = t->bt_psize - BTDATAOFF; 85 for (p = *buf;; p = (char *)p + nb, pg = h->nextpg) { 86 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 87 return (RET_ERROR); 88 89 nb = MIN(sz, plen); 90 memmove(p, (char *)h + BTDATAOFF, nb); 91 mpool_put(t->bt_mp, h, 0); 92 93 if ((sz -= nb) == 0) 94 break; 95 } 96 return (RET_SUCCESS); 97 } 98 99 /* 100 * __OVFL_PUT -- Store an overflow key/data item. 101 * 102 * Parameters: 103 * t: tree 104 * data: DBT to store 105 * pgno: storage page number 106 * 107 * Returns: 108 * RET_ERROR, RET_SUCCESS 109 */ 110 int 111 __ovfl_put(t, dbt, pg) 112 BTREE *t; 113 const DBT *dbt; 114 pgno_t *pg; 115 { 116 PAGE *h, *last; 117 void *p; 118 pgno_t npg; 119 size_t nb, plen, sz; 120 121 /* 122 * Allocate pages and copy the key/data record into them. Store the 123 * number of the first page in the chain. 124 */ 125 plen = t->bt_psize - BTDATAOFF; 126 for (last = NULL, p = dbt->data, sz = dbt->size;; 127 p = (char *)p + plen, last = h) { 128 if ((h = __bt_new(t, &npg)) == NULL) 129 return (RET_ERROR); 130 131 h->pgno = npg; 132 h->nextpg = h->prevpg = P_INVALID; 133 h->flags = P_OVERFLOW; 134 h->lower = h->upper = 0; 135 136 nb = MIN(sz, plen); 137 memmove((char *)h + BTDATAOFF, p, nb); 138 139 if (last) { 140 last->nextpg = h->pgno; 141 mpool_put(t->bt_mp, last, MPOOL_DIRTY); 142 } else 143 *pg = h->pgno; 144 145 if ((sz -= nb) == 0) { 146 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 147 break; 148 } 149 } 150 return (RET_SUCCESS); 151 } 152 153 /* 154 * __OVFL_DELETE -- Delete an overflow chain. 155 * 156 * Parameters: 157 * t: tree 158 * p: pointer to { pgno_t, size_t } 159 * 160 * Returns: 161 * RET_ERROR, RET_SUCCESS 162 */ 163 int 164 __ovfl_delete(t, p) 165 BTREE *t; 166 void *p; 167 { 168 PAGE *h; 169 pgno_t pg; 170 size_t plen, sz; 171 172 memmove(&pg, p, sizeof(pgno_t)); 173 memmove(&sz, (char *)p + sizeof(pgno_t), sizeof(size_t)); 174 175 #ifdef DEBUG 176 if (pg == P_INVALID || sz == 0) 177 abort(); 178 #endif 179 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 180 return (RET_ERROR); 181 182 /* Don't delete chains used by internal pages. */ 183 if (h->flags & P_PRESERVE) { 184 mpool_put(t->bt_mp, h, 0); 185 return (RET_SUCCESS); 186 } 187 188 /* Step through the chain, calling the free routine for each page. */ 189 for (plen = t->bt_psize - BTDATAOFF;; sz -= plen) { 190 pg = h->nextpg; 191 __bt_free(t, h); 192 if (sz <= plen) 193 break; 194 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) 195 return (RET_ERROR); 196 } 197 return (RET_SUCCESS); 198 } 199