home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / ixemul-45.0-src.tgz / tar.out / contrib / ixemul / db / btree / bt_utils.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  7KB  |  257 lines
  1. /*    $NetBSD: bt_utils.c,v 1.6 1995/02/27 13:21:04 cgd Exp $    */
  2.  
  3. /*-
  4.  * Copyright (c) 1990, 1993, 1994
  5.  *    The Regents of the University of California.  All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Mike Olson.
  9.  *
  10.  * Redistribution and use in source and binary forms, with or without
  11.  * modification, are permitted provided that the following conditions
  12.  * are met:
  13.  * 1. Redistributions of source code must retain the above copyright
  14.  *    notice, this list of conditions and the following disclaimer.
  15.  * 2. Redistributions in binary form must reproduce the above copyright
  16.  *    notice, this list of conditions and the following disclaimer in the
  17.  *    documentation and/or other materials provided with the distribution.
  18.  * 3. All advertising materials mentioning features or use of this software
  19.  *    must display the following acknowledgement:
  20.  *    This product includes software developed by the University of
  21.  *    California, Berkeley and its contributors.
  22.  * 4. Neither the name of the University nor the names of its contributors
  23.  *    may be used to endorse or promote products derived from this software
  24.  *    without specific prior written permission.
  25.  *
  26.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36.  * SUCH DAMAGE.
  37.  */
  38.  
  39. #if defined(LIBC_SCCS) && !defined(lint)
  40. #if 0
  41. static char sccsid[] = "@(#)bt_utils.c    8.5 (Berkeley) 6/20/94";
  42. #else
  43. static char rcsid[] = "$NetBSD: bt_utils.c,v 1.6 1995/02/27 13:21:04 cgd Exp $";
  44. #endif
  45. #endif /* LIBC_SCCS and not lint */
  46.  
  47. #include <sys/param.h>
  48.  
  49. #include <stdio.h>
  50. #include <stdlib.h>
  51. #include <string.h>
  52.  
  53. #include <db.h>
  54. #include "btree.h"
  55.  
  56. /*
  57.  * __BT_RET -- Build return key/data pair as a result of search or scan.
  58.  *
  59.  * Parameters:
  60.  *    t:    tree
  61.  *    d:    LEAF to be returned to the user.
  62.  *    key:    user's key structure (NULL if not to be filled in)
  63.  *    data:    user's data structure
  64.  *
  65.  * Returns:
  66.  *    RET_SUCCESS, RET_ERROR.
  67.  */
  68. int
  69. __bt_ret(t, e, key, data)
  70.     BTREE *t;
  71.     EPG *e;
  72.     DBT *key, *data;
  73. {
  74.     register BLEAF *bl;
  75.     register void *p;
  76.  
  77.     bl = GETBLEAF(e->page, e->index);
  78.  
  79.     /*
  80.      * We always copy big keys/data to make them contigous.  Otherwise,
  81.      * we leave the page pinned and don't copy unless the user specified
  82.      * concurrent access.
  83.      */
  84.     if (bl->flags & P_BIGDATA) {
  85.         if (__ovfl_get(t, bl->bytes + bl->ksize,
  86.             &data->size, &t->bt_dbuf, &t->bt_dbufsz))
  87.             return (RET_ERROR);
  88.         data->data = t->bt_dbuf;
  89.     } else if (ISSET(t, B_DB_LOCK)) {
  90.         /* Use +1 in case the first record retrieved is 0 length. */
  91.         if (bl->dsize + 1 > t->bt_dbufsz) {
  92.             p = (void *)(t->bt_dbuf == NULL ?
  93.                 malloc(bl->dsize + 1) :
  94.                 realloc(t->bt_dbuf, bl->dsize + 1));
  95.             if (p == NULL)
  96.                 return (RET_ERROR);
  97.             t->bt_dbuf = p;
  98.             t->bt_dbufsz = bl->dsize + 1;
  99.         }
  100.         memmove(t->bt_dbuf, bl->bytes + bl->ksize, bl->dsize);
  101.         data->size = bl->dsize;
  102.         data->data = t->bt_dbuf;
  103.     } else {
  104.         data->size = bl->dsize;
  105.         data->data = bl->bytes + bl->ksize;
  106.     }
  107.  
  108.     if (key == NULL)
  109.         return (RET_SUCCESS);
  110.  
  111.     if (bl->flags & P_BIGKEY) {
  112.         if (__ovfl_get(t, bl->bytes,
  113.             &key->size, &t->bt_kbuf, &t->bt_kbufsz))
  114.             return (RET_ERROR);
  115.         key->data = t->bt_kbuf;
  116.     } else if (ISSET(t, B_DB_LOCK)) {
  117.         if (bl->ksize > t->bt_kbufsz) {
  118.             p = (void *)(t->bt_kbuf == NULL ?
  119.                 malloc(bl->ksize) : realloc(t->bt_kbuf, bl->ksize));
  120.             if (p == NULL)
  121.                 return (RET_ERROR);
  122.             t->bt_kbuf = p;
  123.             t->bt_kbufsz = bl->ksize;
  124.         }
  125.         memmove(t->bt_kbuf, bl->bytes, bl->ksize);
  126.         key->size = bl->ksize;
  127.         key->data = t->bt_kbuf;
  128.     } else {
  129.         key->size = bl->ksize;
  130.         key->data = bl->bytes;
  131.     }
  132.     return (RET_SUCCESS);
  133. }
  134.  
  135. /*
  136.  * __BT_CMP -- Compare a key to a given record.
  137.  *
  138.  * Parameters:
  139.  *    t:    tree
  140.  *    k1:    DBT pointer of first arg to comparison
  141.  *    e:    pointer to EPG for comparison
  142.  *
  143.  * Returns:
  144.  *    < 0 if k1 is < record
  145.  *    = 0 if k1 is = record
  146.  *    > 0 if k1 is > record
  147.  */
  148. int
  149. __bt_cmp(t, k1, e)
  150.     BTREE *t;
  151.     const DBT *k1;
  152.     EPG *e;
  153. {
  154.     BINTERNAL *bi;
  155.     BLEAF *bl;
  156.     DBT k2;
  157.     PAGE *h;
  158.     void *bigkey;
  159.  
  160.     /*
  161.      * The left-most key on internal pages, at any level of the tree, is
  162.      * guaranteed by the following code to be less than any user key.
  163.      * This saves us from having to update the leftmost key on an internal
  164.      * page when the user inserts a new key in the tree smaller than
  165.      * anything we've yet seen.
  166.      */
  167.     h = e->page;
  168.     if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF))
  169.         return (1);
  170.  
  171.     bigkey = NULL;
  172.     if (h->flags & P_BLEAF) {
  173.         bl = GETBLEAF(h, e->index);
  174.         if (bl->flags & P_BIGKEY)
  175.             bigkey = bl->bytes;
  176.         else {
  177.             k2.data = bl->bytes;
  178.             k2.size = bl->ksize;
  179.         }
  180.     } else {
  181.         bi = GETBINTERNAL(h, e->index);
  182.         if (bi->flags & P_BIGKEY)
  183.             bigkey = bi->bytes;
  184.         else {
  185.             k2.data = bi->bytes;
  186.             k2.size = bi->ksize;
  187.         }
  188.     }
  189.  
  190.     if (bigkey) {
  191.         if (__ovfl_get(t, bigkey,
  192.             &k2.size, &t->bt_dbuf, &t->bt_dbufsz))
  193.             return (RET_ERROR);
  194.         k2.data = t->bt_dbuf;
  195.     }
  196.     return ((*t->bt_cmp)(k1, &k2));
  197. }
  198.  
  199. /*
  200.  * __BT_DEFCMP -- Default comparison routine.
  201.  *
  202.  * Parameters:
  203.  *    a:    DBT #1
  204.  *    b:     DBT #2
  205.  *
  206.  * Returns:
  207.  *    < 0 if a is < b
  208.  *    = 0 if a is = b
  209.  *    > 0 if a is > b
  210.  */
  211. int
  212. __bt_defcmp(a, b)
  213.     const DBT *a, *b;
  214. {
  215.     register size_t len;
  216.     register u_char *p1, *p2;
  217.  
  218.     /*
  219.      * XXX
  220.      * If a size_t doesn't fit in an int, this routine can lose.
  221.      * What we need is a integral type which is guaranteed to be
  222.      * larger than a size_t, and there is no such thing.
  223.      */
  224.     len = MIN(a->size, b->size);
  225.     for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
  226.         if (*p1 != *p2)
  227.             return ((int)*p1 - (int)*p2);
  228.     return ((int)a->size - (int)b->size);
  229. }
  230.  
  231. /*
  232.  * __BT_DEFPFX -- Default prefix routine.
  233.  *
  234.  * Parameters:
  235.  *    a:    DBT #1
  236.  *    b:     DBT #2
  237.  *
  238.  * Returns:
  239.  *    Number of bytes needed to distinguish b from a.
  240.  */
  241. size_t
  242. __bt_defpfx(a, b)
  243.     const DBT *a, *b;
  244. {
  245.     register u_char *p1, *p2;
  246.     register size_t cnt, len;
  247.  
  248.     cnt = 1;
  249.     len = MIN(a->size, b->size);
  250.     for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
  251.         if (*p1 != *p2)
  252.             return (cnt);
  253.  
  254.     /* a->size must be <= b->size, or they wouldn't be in this order. */
  255.     return (a->size < b->size ? a->size + 1 : a->size);
  256. }
  257.