home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Spezial / SPEZIAL2_97.zip / SPEZIAL2_97.iso / ANWEND / EDITOR / NVI179B / NVI179B.ZIP / db / btree / bt_utils.c < prev    next >
C/C++ Source or Header  |  1994-07-20  |  7KB  |  261 lines
  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 <sys/param.h>
  42.  
  43. #include <stdio.h>
  44. #include <stdlib.h>
  45. #include <string.h>
  46.  
  47. #include <db.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
  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.  
  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.      */
  83.     if (key == NULL)
  84.         goto dataonly;
  85.  
  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;
  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 {
  104.         key->size = bl->ksize;
  105.         key->data = bl->bytes;
  106.     }
  107.  
  108. dataonly:
  109.     if (data == NULL)
  110.         return (RET_SUCCESS);
  111.  
  112.     if (bl->flags & P_BIGDATA) {
  113.         if (__ovfl_get(t, bl->bytes + bl->ksize,
  114.             &data->size, &rdata->data, &rdata->size))
  115.             return (RET_ERROR);
  116.         data->data = rdata->data;
  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 {
  132.         data->size = bl->dsize;
  133.         data->data = bl->bytes + bl->ksize;
  134.     }
  135.  
  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
  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.      */
  171.     h = e->page;
  172.     if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF))
  173.         return (1);
  174.  
  175.     bigkey = NULL;
  176.     if (h->flags & P_BLEAF) {
  177.         bl = GETBLEAF(h, e->index);
  178.         if (bl->flags & P_BIGKEY)
  179.             bigkey = bl->bytes;
  180.         else {
  181.             k2.data = bl->bytes;
  182.             k2.size = bl->ksize;
  183.         }
  184.     } else {
  185.         bi = GETBINTERNAL(h, e->index);
  186.         if (bi->flags & P_BIGKEY)
  187.             bigkey = bi->bytes;
  188.         else {
  189.             k2.data = bi->bytes;
  190.             k2.size = bi->ksize;
  191.         }
  192.     }
  193.  
  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.     }
  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
  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.      */
  228.     len = MIN(a->size, b->size);
  229.     for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
  230.         if (*p1 != *p2)
  231.             return ((int)*p1 - (int)*p2);
  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
  246. __bt_defpfx(a, b)
  247.     const DBT *a, *b;
  248. {
  249.     register u_char *p1, *p2;
  250.     register size_t cnt, len;
  251.  
  252.     cnt = 1;
  253.     len = MIN(a->size, b->size);
  254.     for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
  255.         if (*p1 != *p2)
  256.             return (cnt);
  257.  
  258.     /* a->size must be <= b->size, or they wouldn't be in this order. */
  259.     return (a->size < b->size ? a->size + 1 : a->size);
  260. }
  261.