bt_utils.c

Go to the documentation of this file.
00001 /*-
00002  * Copyright (c) 1990, 1993, 1994
00003  * The Regents of the University of California.  All rights reserved.
00004  *
00005  * This code is derived from software contributed to Berkeley by
00006  * Mike Olson.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions
00010  * are met:
00011  * 1. Redistributions of source code must retain the above copyright
00012  *    notice, this list of conditions and the following disclaimer.
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in the
00015  *    documentation and/or other materials provided with the distribution.
00016  * 3. All advertising materials mentioning features or use of this software
00017  *    must display the following acknowledgement:
00018  * This product includes software developed by the University of
00019  * California, Berkeley and its contributors.
00020  * 4. Neither the name of the University nor the names of its contributors
00021  *    may be used to endorse or promote products derived from this software
00022  *    without specific prior written permission.
00023  *
00024  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00025  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00026  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00027  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00028  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00029  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00030  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00031  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00032  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00033  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00034  * SUCH DAMAGE.
00035  */
00036 
00037 #if defined(LIBC_SCCS) && !defined(lint)
00038 static char sccsid[] = "@(#)bt_utils.c 8.8 (Berkeley) 7/20/94";
00039 #endif /* LIBC_SCCS and not lint */
00040 
00041 #include <sys/param.h>
00042 
00043 #include <stdio.h>
00044 #include <stdlib.h>
00045 #include <string.h>
00046 
00047 #include "../include/db.h"
00048 #include "btree.h"
00049 
00050 /*
00051  * __bt_ret --
00052  * Build return key/data pair.
00053  *
00054  * Parameters:
00055  * t: tree
00056  * e: key/data pair to be returned
00057  * key:  user's key structure (NULL if not to be filled in)
00058  * rkey: memory area to hold key
00059  * data: user's data structure (NULL if not to be filled in)
00060  * rdata:   memory area to hold data
00061  *       copy: always copy the key/data item
00062  *
00063  * Returns:
00064  * RET_SUCCESS, RET_ERROR.
00065  */
00066 int
00067 __bt_ret(t, e, key, rkey, data, rdata, copy)
00068    BTREE *t;
00069    EPG *e;
00070    DBT *key, *rkey, *data, *rdata;
00071    int copy;
00072 {
00073    BLEAF *bl;
00074    void *p;
00075 
00076    bl = GETBLEAF(e->page, e->index);
00077 
00078    /*
00079     * We must copy big keys/data to make them contiguous.  Otherwise,
00080     * leave the page pinned and don't copy unless the user specified
00081     * concurrent access.
00082     */
00083    if (key == NULL)
00084       goto dataonly;
00085 
00086    if (bl->flags & P_BIGKEY) {
00087       if (__ovfl_get(t, bl->bytes,
00088           &key->size, &rkey->data, &rkey->size))
00089          return (RET_ERROR);
00090       key->data = rkey->data;
00091    } else if (copy || F_ISSET(t, B_DB_LOCK)) {
00092       if (bl->ksize > rkey->size) {
00093          p = (void *)(rkey->data == NULL ?
00094              malloc(bl->ksize) : realloc(rkey->data, bl->ksize));
00095          if (p == NULL)
00096             return (RET_ERROR);
00097          rkey->data = p;
00098          rkey->size = bl->ksize;
00099       }
00100       memmove(rkey->data, bl->bytes, bl->ksize);
00101       key->size = bl->ksize;
00102       key->data = rkey->data;
00103    } else {
00104       key->size = bl->ksize;
00105       key->data = bl->bytes;
00106    }
00107 
00108 dataonly:
00109    if (data == NULL)
00110       return (RET_SUCCESS);
00111 
00112    if (bl->flags & P_BIGDATA) {
00113       if (__ovfl_get(t, bl->bytes + bl->ksize,
00114           &data->size, &rdata->data, &rdata->size))
00115          return (RET_ERROR);
00116       data->data = rdata->data;
00117    } else if (copy || F_ISSET(t, B_DB_LOCK)) {
00118       /* Use +1 in case the first record retrieved is 0 length. */
00119       if (bl->dsize + 1 > rdata->size) {
00120          p = (void *)(rdata->data == NULL ?
00121              malloc(bl->dsize + 1) :
00122              realloc(rdata->data, bl->dsize + 1));
00123          if (p == NULL)
00124             return (RET_ERROR);
00125          rdata->data = p;
00126          rdata->size = bl->dsize + 1;
00127       }
00128       memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize);
00129       data->size = bl->dsize;
00130       data->data = rdata->data;
00131    } else {
00132       data->size = bl->dsize;
00133       data->data = bl->bytes + bl->ksize;
00134    }
00135 
00136    return (RET_SUCCESS);
00137 }
00138 
00139 /*
00140  * __BT_CMP -- Compare a key to a given record.
00141  *
00142  * Parameters:
00143  * t: tree
00144  * k1:   DBT pointer of first arg to comparison
00145  * e: pointer to EPG for comparison
00146  *
00147  * Returns:
00148  * < 0 if k1 is < record
00149  * = 0 if k1 is = record
00150  * > 0 if k1 is > record
00151  */
00152 int
00153 __bt_cmp(t, k1, e)
00154    BTREE *t;
00155    const DBT *k1;
00156    EPG *e;
00157 {
00158    BINTERNAL *bi;
00159    BLEAF *bl;
00160    DBT k2;
00161    PAGE *h;
00162    void *bigkey;
00163 
00164    /*
00165     * The left-most key on internal pages, at any level of the tree, is
00166     * guaranteed by the following code to be less than any user key.
00167     * This saves us from having to update the leftmost key on an internal
00168     * page when the user inserts a new key in the tree smaller than
00169     * anything we've yet seen.
00170     */
00171    h = e->page;
00172    if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF))
00173       return (1);
00174 
00175    bigkey = NULL;
00176    if (h->flags & P_BLEAF) {
00177       bl = GETBLEAF(h, e->index);
00178       if (bl->flags & P_BIGKEY)
00179          bigkey = bl->bytes;
00180       else {
00181          k2.data = bl->bytes;
00182          k2.size = bl->ksize;
00183       }
00184    } else {
00185       bi = GETBINTERNAL(h, e->index);
00186       if (bi->flags & P_BIGKEY)
00187          bigkey = bi->bytes;
00188       else {
00189          k2.data = bi->bytes;
00190          k2.size = bi->ksize;
00191       }
00192    }
00193 
00194    if (bigkey) {
00195       if (__ovfl_get(t, bigkey,
00196           &k2.size, &t->bt_rdata.data, &t->bt_rdata.size))
00197          return (RET_ERROR);
00198       k2.data = t->bt_rdata.data;
00199    }
00200    return ((*t->bt_cmp)(k1, &k2));
00201 }
00202 
00203 /*
00204  * __BT_DEFCMP -- Default comparison routine.
00205  *
00206  * Parameters:
00207  * a: DBT #1
00208  * b:    DBT #2
00209  *
00210  * Returns:
00211  * < 0 if a is < b
00212  * = 0 if a is = b
00213  * > 0 if a is > b
00214  */
00215 int
00216 __bt_defcmp(a, b)
00217    const DBT *a, *b;
00218 {
00219    register size_t len;
00220    register u_char *p1, *p2;
00221 
00222    /*
00223     * XXX
00224     * If a size_t doesn't fit in an int, this routine can lose.
00225     * What we need is a integral type which is guaranteed to be
00226     * larger than a size_t, and there is no such thing.
00227     */
00228    len = MIN(a->size, b->size);
00229    for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
00230       if (*p1 != *p2)
00231          return ((int)*p1 - (int)*p2);
00232    return ((int)a->size - (int)b->size);
00233 }
00234 
00235 /*
00236  * __BT_DEFPFX -- Default prefix routine.
00237  *
00238  * Parameters:
00239  * a: DBT #1
00240  * b:    DBT #2
00241  *
00242  * Returns:
00243  * Number of bytes needed to distinguish b from a.
00244  */
00245 size_t
00246 __bt_defpfx(a, b)
00247    const DBT *a, *b;
00248 {
00249    register u_char *p1, *p2;
00250    register size_t cnt, len;
00251 
00252    cnt = 1;
00253    len = MIN(a->size, b->size);
00254    for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
00255       if (*p1 != *p2)
00256          return (cnt);
00257 
00258    /* a->size must be <= b->size, or they wouldn't be in this order. */
00259    return (a->size < b->size ? a->size + 1 : a->size);
00260 }

Generated on Thu Apr 16 06:27:16 2015 for Asterisk - The Open Source Telephony Project by  doxygen 1.5.6