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