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 * 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. All advertising materials mentioning features or use of this software 17 * must display the following acknowledgement: 18 * This product includes software developed by the University of 19 * California, Berkeley and its contributors. 20 * 4. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 */ 36 37 #if defined(LIBC_SCCS) && !defined(lint) 38 static char sccsid[] = "@(#)bt_utils.c 8.1 (Berkeley) 6/4/93"; 39 #endif /* LIBC_SCCS and not lint */ 40 41 #include <sys/param.h> 42 43 #include <stdio.h> 44 #include <stdlib.h> 45 #include <string.h> 46 47 #include <db.h> 48 #include "btree.h" 49 50 /* 51 * __BT_RET -- Build return key/data pair as a result of search or scan. 52 * 53 * Parameters: 54 * t: tree 55 * d: LEAF to be returned to the user. 56 * key: user's key structure (NULL if not to be filled in) 57 * data: user's data structure 58 * 59 * Returns: 60 * RET_SUCCESS, RET_ERROR. 61 */ 62 int 63 __bt_ret(t, e, key, data) 64 BTREE *t; 65 EPG *e; 66 DBT *key, *data; 67 { 68 register BLEAF *bl; 69 register void *p; 70 71 bl = GETBLEAF(e->page, e->index); 72 73 if (bl->flags & P_BIGDATA) { 74 if (__ovfl_get(t, bl->bytes + bl->ksize, 75 &data->size, &t->bt_dbuf, &t->bt_dbufsz)) 76 return (RET_ERROR); 77 } else { 78 /* Use +1 in case the first record retrieved is 0 length. */ 79 if (bl->dsize + 1 > t->bt_dbufsz) { 80 if ((p = realloc(t->bt_dbuf, bl->dsize + 1)) == NULL) 81 return (RET_ERROR); 82 t->bt_dbuf = p; 83 t->bt_dbufsz = bl->dsize + 1; 84 } 85 memmove(t->bt_dbuf, bl->bytes + bl->ksize, bl->dsize); 86 data->size = bl->dsize; 87 } 88 data->data = t->bt_dbuf; 89 90 if (key == NULL) 91 return (RET_SUCCESS); 92 93 if (bl->flags & P_BIGKEY) { 94 if (__ovfl_get(t, bl->bytes, 95 &key->size, &t->bt_kbuf, &t->bt_kbufsz)) 96 return (RET_ERROR); 97 } else { 98 if (bl->ksize > t->bt_kbufsz) { 99 if ((p = realloc(t->bt_kbuf, bl->ksize)) == NULL) 100 return (RET_ERROR); 101 t->bt_kbuf = p; 102 t->bt_kbufsz = bl->ksize; 103 } 104 memmove(t->bt_kbuf, bl->bytes, bl->ksize); 105 key->size = bl->ksize; 106 } 107 key->data = t->bt_kbuf; 108 return (RET_SUCCESS); 109 } 110 111 /* 112 * __BT_CMP -- Compare a key to a given record. 113 * 114 * Parameters: 115 * t: tree 116 * k1: DBT pointer of first arg to comparison 117 * e: pointer to EPG for comparison 118 * 119 * Returns: 120 * < 0 if k1 is < record 121 * = 0 if k1 is = record 122 * > 0 if k1 is > record 123 */ 124 int 125 __bt_cmp(t, k1, e) 126 BTREE *t; 127 const DBT *k1; 128 EPG *e; 129 { 130 BINTERNAL *bi; 131 BLEAF *bl; 132 DBT k2; 133 PAGE *h; 134 void *bigkey; 135 136 /* 137 * The left-most key on internal pages, at any level of the tree, is 138 * guaranteed by the following code to be less than any user key. 139 * This saves us from having to update the leftmost key on an internal 140 * page when the user inserts a new key in the tree smaller than 141 * anything we've yet seen. 142 */ 143 h = e->page; 144 if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF)) 145 return (1); 146 147 bigkey = NULL; 148 if (h->flags & P_BLEAF) { 149 bl = GETBLEAF(h, e->index); 150 if (bl->flags & P_BIGKEY) 151 bigkey = bl->bytes; 152 else { 153 k2.data = bl->bytes; 154 k2.size = bl->ksize; 155 } 156 } else { 157 bi = GETBINTERNAL(h, e->index); 158 if (bi->flags & P_BIGKEY) 159 bigkey = bi->bytes; 160 else { 161 k2.data = bi->bytes; 162 k2.size = bi->ksize; 163 } 164 } 165 166 if (bigkey) { 167 if (__ovfl_get(t, bigkey, 168 &k2.size, &t->bt_dbuf, &t->bt_dbufsz)) 169 return (RET_ERROR); 170 k2.data = t->bt_dbuf; 171 } 172 return ((*t->bt_cmp)(k1, &k2)); 173 } 174 175 /* 176 * __BT_DEFCMP -- Default comparison routine. 177 * 178 * Parameters: 179 * a: DBT #1 180 * b: DBT #2 181 * 182 * Returns: 183 * < 0 if a is < b 184 * = 0 if a is = b 185 * > 0 if a is > b 186 */ 187 int 188 __bt_defcmp(a, b) 189 const DBT *a, *b; 190 { 191 register u_char *p1, *p2; 192 register int diff, len; 193 194 len = MIN(a->size, b->size); 195 for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2) 196 if (diff = *p1 - *p2) 197 return (diff); 198 return (a->size - b->size); 199 } 200 201 /* 202 * __BT_DEFPFX -- Default prefix routine. 203 * 204 * Parameters: 205 * a: DBT #1 206 * b: DBT #2 207 * 208 * Returns: 209 * Number of bytes needed to distinguish b from a. 210 */ 211 int 212 __bt_defpfx(a, b) 213 const DBT *a, *b; 214 { 215 register u_char *p1, *p2; 216 register int len; 217 int cnt; 218 219 cnt = 1; 220 len = MIN(a->size, b->size); 221 for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt) 222 if (*p1 != *p2) 223 return (cnt); 224 225 /* a->size must be <= b->size, or they wouldn't be in this order. */ 226 return (a->size < b->size ? a->size + 1 : a->size); 227 } 228