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_utils.c 8.4 (Berkeley) 02/21/94"; 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 * __BT_RET -- Build return key/data pair as a result of search or scan. 26 * 27 * Parameters: 28 * t: tree 29 * d: LEAF to be returned to the user. 30 * key: user's key structure (NULL if not to be filled in) 31 * data: user's data structure 32 * 33 * Returns: 34 * RET_SUCCESS, RET_ERROR. 35 */ 36 int 37 __bt_ret(t, e, key, data) 38 BTREE *t; 39 EPG *e; 40 DBT *key, *data; 41 { 42 register BLEAF *bl; 43 register void *p; 44 45 bl = GETBLEAF(e->page, e->index); 46 47 /* 48 * We always copy big keys/data to make them contigous. Otherwise, 49 * we leave the page pinned and don't copy unless the user specified 50 * concurrent access. 51 */ 52 if (bl->flags & P_BIGDATA) { 53 if (__ovfl_get(t, bl->bytes + bl->ksize, 54 &data->size, &t->bt_dbuf, &t->bt_dbufsz)) 55 return (RET_ERROR); 56 data->data = t->bt_dbuf; 57 } else if (ISSET(t, B_DB_LOCK)) { 58 /* Use +1 in case the first record retrieved is 0 length. */ 59 if (bl->dsize + 1 > t->bt_dbufsz) { 60 if ((p = 61 (void *)realloc(t->bt_dbuf, bl->dsize + 1)) == NULL) 62 return (RET_ERROR); 63 t->bt_dbuf = p; 64 t->bt_dbufsz = bl->dsize + 1; 65 } 66 memmove(t->bt_dbuf, bl->bytes + bl->ksize, bl->dsize); 67 data->size = bl->dsize; 68 data->data = t->bt_dbuf; 69 } else { 70 data->size = bl->dsize; 71 data->data = bl->bytes + bl->ksize; 72 } 73 74 if (key == NULL) 75 return (RET_SUCCESS); 76 77 if (bl->flags & P_BIGKEY) { 78 if (__ovfl_get(t, bl->bytes, 79 &key->size, &t->bt_kbuf, &t->bt_kbufsz)) 80 return (RET_ERROR); 81 key->data = t->bt_kbuf; 82 } else if (ISSET(t, B_DB_LOCK)) { 83 if (bl->ksize > t->bt_kbufsz) { 84 if ((p = 85 (void *)realloc(t->bt_kbuf, bl->ksize)) == NULL) 86 return (RET_ERROR); 87 t->bt_kbuf = p; 88 t->bt_kbufsz = bl->ksize; 89 } 90 memmove(t->bt_kbuf, bl->bytes, bl->ksize); 91 key->size = bl->ksize; 92 key->data = t->bt_kbuf; 93 } else { 94 key->size = bl->ksize; 95 key->data = bl->bytes; 96 } 97 return (RET_SUCCESS); 98 } 99 100 /* 101 * __BT_CMP -- Compare a key to a given record. 102 * 103 * Parameters: 104 * t: tree 105 * k1: DBT pointer of first arg to comparison 106 * e: pointer to EPG for comparison 107 * 108 * Returns: 109 * < 0 if k1 is < record 110 * = 0 if k1 is = record 111 * > 0 if k1 is > record 112 */ 113 int 114 __bt_cmp(t, k1, e) 115 BTREE *t; 116 const DBT *k1; 117 EPG *e; 118 { 119 BINTERNAL *bi; 120 BLEAF *bl; 121 DBT k2; 122 PAGE *h; 123 void *bigkey; 124 125 /* 126 * The left-most key on internal pages, at any level of the tree, is 127 * guaranteed by the following code to be less than any user key. 128 * This saves us from having to update the leftmost key on an internal 129 * page when the user inserts a new key in the tree smaller than 130 * anything we've yet seen. 131 */ 132 h = e->page; 133 if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF)) 134 return (1); 135 136 bigkey = NULL; 137 if (h->flags & P_BLEAF) { 138 bl = GETBLEAF(h, e->index); 139 if (bl->flags & P_BIGKEY) 140 bigkey = bl->bytes; 141 else { 142 k2.data = bl->bytes; 143 k2.size = bl->ksize; 144 } 145 } else { 146 bi = GETBINTERNAL(h, e->index); 147 if (bi->flags & P_BIGKEY) 148 bigkey = bi->bytes; 149 else { 150 k2.data = bi->bytes; 151 k2.size = bi->ksize; 152 } 153 } 154 155 if (bigkey) { 156 if (__ovfl_get(t, bigkey, 157 &k2.size, &t->bt_dbuf, &t->bt_dbufsz)) 158 return (RET_ERROR); 159 k2.data = t->bt_dbuf; 160 } 161 return ((*t->bt_cmp)(k1, &k2)); 162 } 163 164 /* 165 * __BT_DEFCMP -- Default comparison routine. 166 * 167 * Parameters: 168 * a: DBT #1 169 * b: DBT #2 170 * 171 * Returns: 172 * < 0 if a is < b 173 * = 0 if a is = b 174 * > 0 if a is > b 175 */ 176 int 177 __bt_defcmp(a, b) 178 const DBT *a, *b; 179 { 180 register size_t len; 181 register u_char *p1, *p2; 182 183 /* 184 * XXX 185 * If a size_t doesn't fit in an int, this routine can lose. 186 * What we need is a integral type which is guaranteed to be 187 * larger than a size_t, and there is no such thing. 188 */ 189 len = MIN(a->size, b->size); 190 for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2) 191 if (*p1 != *p2) 192 return ((int)*p1 - (int)*p2); 193 return ((int)a->size - (int)b->size); 194 } 195 196 /* 197 * __BT_DEFPFX -- Default prefix routine. 198 * 199 * Parameters: 200 * a: DBT #1 201 * b: DBT #2 202 * 203 * Returns: 204 * Number of bytes needed to distinguish b from a. 205 */ 206 size_t 207 __bt_defpfx(a, b) 208 const DBT *a, *b; 209 { 210 register u_char *p1, *p2; 211 register size_t cnt, len; 212 213 cnt = 1; 214 len = MIN(a->size, b->size); 215 for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt) 216 if (*p1 != *p2) 217 return (cnt); 218 219 /* a->size must be <= b->size, or they wouldn't be in this order. */ 220 return (a->size < b->size ? a->size + 1 : a->size); 221 } 222