-: 0:Source:bt_utils.c -: 0:Graph:/var/tsitkova/Sources/v10/trunk/src/plugins/kdb/db2/libdb2/btree/bt_utils.so.gcno -: 0:Data:/var/tsitkova/Sources/v10/trunk/src/plugins/kdb/db2/libdb2/btree/bt_utils.so.gcda -: 0:Runs:1656 -: 0:Programs:2 -: 1:/*- -: 2: * Copyright (c) 1990, 1993, 1994 -: 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.8 (Berkeley) 7/20/94"; -: 39:#endif /* LIBC_SCCS and not lint */ -: 40: -: 41:#include -: 42: -: 43:#include -: 44:#include -: 45:#include -: 46: -: 47:#include "db-int.h" -: 48:#include "btree.h" -: 49: -: 50:/* -: 51: * __bt_ret -- -: 52: * Build return key/data pair. -: 53: * -: 54: * Parameters: -: 55: * t: tree -: 56: * e: key/data pair to be returned -: 57: * key: user's key structure (NULL if not to be filled in) -: 58: * rkey: memory area to hold key -: 59: * data: user's data structure (NULL if not to be filled in) -: 60: * rdata: memory area to hold data -: 61: * copy: always copy the key/data item -: 62: * -: 63: * Returns: -: 64: * RET_SUCCESS, RET_ERROR. -: 65: */ -: 66:int 76029: 67:__bt_ret(t, e, key, rkey, data, rdata, copy) -: 68: BTREE *t; -: 69: EPG *e; -: 70: DBT *key, *rkey, *data, *rdata; -: 71: int copy; -: 72:{ -: 73: BLEAF *bl; -: 74: void *p; -: 75: 76029: 76: bl = GETBLEAF(e->page, e->index); -: 77: -: 78: /* -: 79: * We must copy big keys/data to make them contigous. Otherwise, -: 80: * leave the page pinned and don't copy unless the user specified -: 81: * concurrent access. -: 82: */ 76029: 83: if (key == NULL) 68055: 84: goto dataonly; -: 85: 7974: 86: if (bl->flags & P_BIGKEY) { #####: 87: if (__ovfl_get(t, bl->bytes, -: 88: &key->size, &rkey->data, &rkey->size)) #####: 89: return (RET_ERROR); #####: 90: key->data = rkey->data; 7974: 91: } else if (copy || F_ISSET(t, B_DB_LOCK)) { #####: 92: if (bl->ksize > rkey->size) { #####: 93: p = (void *)(rkey->data == NULL ? #####: 94: malloc(bl->ksize) : realloc(rkey->data, bl->ksize)); #####: 95: if (p == NULL) #####: 96: return (RET_ERROR); #####: 97: rkey->data = p; #####: 98: rkey->size = bl->ksize; -: 99: } #####: 100: memmove(rkey->data, bl->bytes, bl->ksize); #####: 101: key->size = bl->ksize; #####: 102: key->data = rkey->data; -: 103: } else { 7974: 104: key->size = bl->ksize; 7974: 105: key->data = bl->bytes; -: 106: } -: 107: -: 108:dataonly: 76029: 109: if (data == NULL) #####: 110: return (RET_SUCCESS); -: 111: 76029: 112: if (bl->flags & P_BIGDATA) { 3642: 113: if (__ovfl_get(t, bl->bytes + bl->ksize, -: 114: &data->size, &rdata->data, &rdata->size)) #####: 115: return (RET_ERROR); 3642: 116: data->data = rdata->data; 72387: 117: } else if (copy || F_ISSET(t, B_DB_LOCK)) { -: 118: /* Use +1 in case the first record retrieved is 0 length. */ #####: 119: if (bl->dsize + 1 > rdata->size) { #####: 120: p = (void *)(rdata->data == NULL ? #####: 121: malloc(bl->dsize + 1) : #####: 122: realloc(rdata->data, bl->dsize + 1)); #####: 123: if (p == NULL) #####: 124: return (RET_ERROR); #####: 125: rdata->data = p; #####: 126: rdata->size = bl->dsize + 1; -: 127: } #####: 128: memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize); #####: 129: data->size = bl->dsize; #####: 130: data->data = rdata->data; -: 131: } else { 72387: 132: data->size = bl->dsize; 72387: 133: data->data = bl->bytes + bl->ksize; -: 134: } -: 135: 76029: 136: return (RET_SUCCESS); -: 137:} -: 138: -: 139:/* -: 140: * __BT_CMP -- Compare a key to a given record. -: 141: * -: 142: * Parameters: -: 143: * t: tree -: 144: * k1: DBT pointer of first arg to comparison -: 145: * e: pointer to EPG for comparison -: 146: * -: 147: * Returns: -: 148: * < 0 if k1 is < record -: 149: * = 0 if k1 is = record -: 150: * > 0 if k1 is > record -: 151: */ -: 152:int 1670496: 153:__bt_cmp(t, k1, e) -: 154: BTREE *t; -: 155: const DBT *k1; -: 156: EPG *e; -: 157:{ -: 158: BINTERNAL *bi; -: 159: BLEAF *bl; -: 160: DBT k2; -: 161: PAGE *h; -: 162: void *bigkey; -: 163: -: 164: /* -: 165: * The left-most key on internal pages, at any level of the tree, is -: 166: * guaranteed by the following code to be less than any user key. -: 167: * This saves us from having to update the leftmost key on an internal -: 168: * page when the user inserts a new key in the tree smaller than -: 169: * anything we've yet seen. -: 170: */ 1670496: 171: h = e->page; 1670496: 172: if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF)) 35737: 173: return (1); -: 174: 1634759: 175: bigkey = NULL; 1634759: 176: if (h->flags & P_BLEAF) { 384990: 177: bl = GETBLEAF(h, e->index); 384990: 178: if (bl->flags & P_BIGKEY) #####: 179: bigkey = bl->bytes; -: 180: else { 384990: 181: k2.data = bl->bytes; 384990: 182: k2.size = bl->ksize; -: 183: } -: 184: } else { 1249769: 185: bi = GETBINTERNAL(h, e->index); 1249769: 186: if (bi->flags & P_BIGKEY) #####: 187: bigkey = bi->bytes; -: 188: else { 1249769: 189: k2.data = bi->bytes; 1249769: 190: k2.size = bi->ksize; -: 191: } -: 192: } -: 193: 1634759: 194: if (bigkey) { #####: 195: if (__ovfl_get(t, bigkey, -: 196: &k2.size, &t->bt_rdata.data, &t->bt_rdata.size)) #####: 197: return (RET_ERROR); #####: 198: k2.data = t->bt_rdata.data; -: 199: } 1634759: 200: return ((*t->bt_cmp)(k1, &k2)); -: 201:} -: 202: -: 203:/* -: 204: * __BT_DEFCMP -- Default comparison routine. -: 205: * -: 206: * Parameters: -: 207: * a: DBT #1 -: 208: * b: DBT #2 -: 209: * -: 210: * Returns: -: 211: * < 0 if a is < b -: 212: * = 0 if a is = b -: 213: * > 0 if a is > b -: 214: */ -: 215:int 1634759: 216:__bt_defcmp(a, b) -: 217: const DBT *a, *b; -: 218:{ -: 219: register size_t len; -: 220: register u_char *p1, *p2; -: 221: -: 222: /* -: 223: * XXX -: 224: * If a size_t doesn't fit in an int, this routine can lose. -: 225: * What we need is a integral type which is guaranteed to be -: 226: * larger than a size_t, and there is no such thing. -: 227: */ 1634759: 228: len = MIN(a->size, b->size); 5917169: 229: for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2) 5787202: 230: if (*p1 != *p2) 1504792: 231: return ((int)*p1 - (int)*p2); 129967: 232: return ((int)a->size - (int)b->size); -: 233:} -: 234: -: 235:/* -: 236: * __BT_DEFPFX -- Default prefix routine. -: 237: * -: 238: * Parameters: -: 239: * a: DBT #1 -: 240: * b: DBT #2 -: 241: * -: 242: * Returns: -: 243: * Number of bytes needed to distinguish b from a. -: 244: */ -: 245:size_t 8758: 246:__bt_defpfx(a, b) -: 247: const DBT *a, *b; -: 248:{ -: 249: register u_char *p1, *p2; -: 250: register size_t cnt, len; -: 251: 8758: 252: cnt = 1; 8758: 253: len = MIN(a->size, b->size); 45448: 254: for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt) 45412: 255: if (*p1 != *p2) 8722: 256: return (cnt); -: 257: -: 258: /* a->size must be <= b->size, or they wouldn't be in this order. */ 36: 259: return (a->size < b->size ? a->size + 1 : a->size); -: 260:}