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