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