lib/libc/db/btree/utils.c

   1 /*-
   2  * Copyright (c) 1990 The Regents of the University of California.
   3  * 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[] = "@(#)utils.c     5.3 (Berkeley) 3/3/91";
  39 #endif /* LIBC_SCCS and not lint */
  40
  41 #include <sys/types.h>
  42 #include <db.h>
  43 #include <stdlib.h>
  44 #include <string.h>
  45 #include "btree.h"
  46
  47 /*
  48  *  _BT_BUILDRET -- Build return key/data pair as a result of search or scan.
  49  *
  50  *      This routine manages the statically allocated buffers in which we
  51  *      return data to the user.
  52  *
  53  *      Parameters:
  54  *              t -- btree from which to return datum
  55  *              d -- DATUM to be returned to the user.
  56  *              data -- data argument supplied by user for return
  57  *              key -- key argument supplied by user for return
  58  *
  59  *      Returns:
  60  *              RET_SUCCESS, RET_ERROR.
  61  *
  62  *      Side Effects:
  63  *              May free and reallocate static buffers, if the data
  64  *              we want to return is bigger than the space we have to
  65  *              do so.
  66  */
  67
  68 int
  69 _bt_buildret(t, d, data, key)
  70         BTREE_P t;
  71         DATUM *d;
  72         DBT *data;
  73         DBT *key;
  74 {
  75         static int _data_s = 0;
  76         static int _key_s = 0;
  77         static char *_data = (char *) NULL;
  78         static char *_key = (char *) NULL;
  79         pgno_t chain;
  80
  81         if (d->d_flags & D_BIGKEY) {
  82                 if (_key != (char *) NULL)
  83                         (void) free(_key);
  84                 (void) bcopy((char *) &(d->d_bytes[0]),
  85                              (char *) &chain,
  86                              sizeof(chain));
  87                 if (_bt_getbig(t, chain, &_key, &_key_s) == RET_ERROR)
  88                         return (RET_ERROR);
  89                 key->data = (u_char *)_key;
  90                 key->size = _key_s;
  91         } else {
  92                 /* need more space for key? */
  93                 if (d->d_ksize > _key_s) {
  94                         if (_key != (char *) NULL)
  95                                 (void) free (_key);
  96                         if ((_key = (char *) malloc((unsigned) d->d_ksize))
  97                             == (char *) NULL)
  98                                 return (RET_ERROR);
  99                         _key_s = d->d_ksize;
 100                 }
 101
 102                 key->data = (u_char *)_key;
 103                 if ((key->size = d->d_ksize) > 0)
 104                         (void) bcopy(&(d->d_bytes[0]),
 105                                      _key,
 106                                      (int) d->d_ksize);
 107         }
 108
 109         if (d->d_flags & D_BIGDATA) {
 110                 if (_data != (char *) NULL)
 111                         (void) free(_data);
 112                 (void) bcopy(&(d->d_bytes[d->d_ksize]),
 113                              (char *) &chain,
 114                              sizeof(chain));
 115                 if (_bt_getbig(t, chain, &_data, &_data_s) == RET_ERROR)
 116                         return (RET_ERROR);
 117                 data->data = (u_char *)_data;
 118                 data->size = _data_s;
 119         } else {
 120                 /* need more space for data? */
 121                 if (d->d_dsize > _data_s) {
 122                         if (_data != (char *) NULL)
 123                                 (void) free (_data);
 124                         if ((_data = (char *) malloc((unsigned) d->d_dsize))
 125                             == (char *) NULL)
 126                                 return (RET_ERROR);
 127                         _data_s = d->d_dsize;
 128                 }
 129
 130                 data->data = (u_char *)_data;
 131
 132                 if ((data->size = d->d_dsize) > 0)
 133                         (void) bcopy(&(d->d_bytes[d->d_ksize]),
 134                                       _data,
 135                                       (size_t) (d->d_dsize));
 136         }
 137
 138         return (RET_SUCCESS);
 139 }
 140
 141 /*
 142  *  _BT_CMP -- Compare a key to a given item on the current page.
 143  *
 144  *      This routine is a wrapper for the user's comparison function.
 145  *
 146  *      Parameters:
 147  *              t -- tree in which to do comparison
 148  *              p -- pointer to one argument for the comparison function
 149  *              n -- index of item to supply second arg to comparison function
 150  *
 151  *      Returns:
 152  *              < 0 if p is < item at n
 153  *              = 0 if p is = item at n
 154  *              > 0 if p is > item at n
 155  */
 156
 157 int
 158 _bt_cmp(t, p, n)
 159         BTREE_P t;
 160         char *p;
 161         index_t n;
 162 {
 163         BTHEADER *h;
 164         IDATUM *id;
 165         DATUM *d;
 166         char *arg;
 167         int ignore;
 168         int free_arg;
 169         pgno_t chain;
 170         int r;
 171
 172         h = t->bt_curpage;
 173
 174         /*
 175          *  The left-most key at any level of the tree on internal pages
 176          *  is guaranteed (artificially, by the code here) to be less than
 177          *  any user key.  This saves us from having to update the leftmost
 178          *  key when the user inserts a new key in the tree smaller than
 179          *  anything we've seen yet.
 180          */
 181
 182         if (h->h_prevpg == P_NONE && !(h->h_flags & F_LEAF) && n == 0)
 183                 return (1);
 184
 185         if (h->h_flags & F_LEAF) {
 186                 d = (DATUM *) GETDATUM(h,n);
 187                 if (d->d_flags & D_BIGKEY) {
 188                         free_arg = TRUE;
 189                         bcopy(&(d->d_bytes[0]), (char *) &chain, sizeof(chain));
 190                         if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR)
 191                                 return (RET_ERROR);
 192                 } else {
 193                         free_arg = FALSE;
 194                         arg = &(d->d_bytes[0]);
 195                 }
 196         } else {
 197                 id = (IDATUM *) GETDATUM(h,n);
 198                 if (id->i_flags & D_BIGKEY) {
 199                         free_arg = TRUE;
 200                         bcopy(&(id->i_bytes[0]),
 201                               (char *) &chain,
 202                               sizeof(chain));
 203                         if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR)
 204                                 return (RET_ERROR);
 205                 } else {
 206                         free_arg = FALSE;
 207                         arg = &(id->i_bytes[0]);
 208                 }
 209         }
 210         r = (*(t->bt_compare))(p, arg);
 211
 212         if (free_arg)
 213                 (void) free(arg);
 214
 215         return (r);
 216 }
 217
 218 /*
 219  *  _BT_PUSH/_BT_POP -- Push/pop a parent page number on the parent stack.
 220  *
 221  *      When we descend the tree, we keep track of parent pages in order
 222  *      to handle splits on insertions.
 223  *
 224  *      Parameters:
 225  *              t -- tree for which to push parent
 226  *              pgno -- page number to push (_bt_push only)
 227  *
 228  *      Returns:
 229  *              RET_SUCCESS, RET_ERROR.
 230  */
 231
 232 int
 233 _bt_push(t, pgno)
 234         BTREE_P t;
 235         pgno_t pgno;
 236 {
 237         BTSTACK *new;
 238
 239         if ((new = (BTSTACK *) malloc((unsigned) sizeof(BTSTACK)))
 240             ==  (BTSTACK *) NULL)
 241                 return (RET_ERROR);
 242         new->bts_pgno = pgno;
 243         new->bts_next = t->bt_stack;
 244         t->bt_stack = new;
 245
 246         return (RET_SUCCESS);
 247 }
 248
 249 pgno_t
 250 _bt_pop(t)
 251         BTREE_P t;
 252 {
 253         BTSTACK *s;
 254         pgno_t p = P_NONE;
 255
 256         if ((s = t->bt_stack) != (BTSTACK *) NULL) {
 257                 p = s->bts_pgno;
 258                 t->bt_stack = s->bts_next;
 259                 (void) free ((char *) s);
 260         }
 261         return (p);
 262 }
 263
 264 #ifdef DEBUG
 265 void
 266 _btdump(tree)
 267         BTREE tree;
 268 {
 269         BTREE_P t = (BTREE_P) tree;
 270         DATUM *d;
 271         IDATUM *id;
 272         BTHEADER *h;
 273         pgno_t npages;
 274         pgno_t i;
 275         index_t cur, top;
 276
 277         npages = t->bt_npages;
 278         (void) printf("\"%s\" fd %d pgsz %d curpg %d @ 0x%lx",
 279                 t->bt_fname, t->bt_s.bt_d.d_fd,
 280                 t->bt_psize, t->bt_curpage);
 281         (void) printf("npg %d cmp 0x%lx flags=(", npages, t->bt_compare);
 282         if (t->bt_flags & BTF_SEQINIT)
 283                 (void) printf("BTF_SEQINIT");
 284         (void) printf(")\n");
 285
 286         for (i = P_ROOT; i <= npages; i++) {
 287                 if (_bt_getpage(t, i) == RET_ERROR)
 288                         _punt();
 289                 h = t->bt_curpage;
 290                 top = NEXTINDEX(h);
 291                 (void) printf("    page %d:\n", i);
 292                 (void) printf("\tpgno %d prev %d next %d\n",
 293                         h->h_pgno, h->h_prevpg, h->h_nextpg);
 294                 (void) printf("\tlower %d upper %d nextind %d flags (",
 295                         h->h_lower, h->h_upper, top);
 296                 if (h->h_flags & F_LEAF)
 297                         (void) printf("F_LEAF");
 298                 else
 299                         (void) printf("<internal>");
 300                 if (h->h_flags & F_DIRTY)
 301                         (void) printf("|F_DIRTY");
 302                 if (h->h_flags & F_PRESERVE)
 303                         (void) printf("|F_PRESERVE");
 304                 if (h->h_flags & F_CONT) {
 305                         (void) printf("|F_CONT)");
 306                         if (h->h_prevpg == P_NONE) {
 307                                 size_t longsz;
 308                                 (void) bcopy((char *) &(h->h_linp[0]),
 309                                               (char *) &longsz,
 310                                               sizeof(longsz));
 311                                 printf("\n\t\t(chain start, data length %ld)",
 312                                         longsz);
 313                         }
 314                         printf("\n");
 315                         continue;
 316                 }
 317                 (void) printf(")\n");
 318                 for (cur = 0; cur < top; cur++) {
 319                         (void) printf("\t  [%d] off %d ", cur, h->h_linp[cur]);
 320                         if (h->h_flags & F_LEAF) {
 321                                 d = (DATUM *) GETDATUM(h,cur);
 322                                 (void) printf("ksize %d", d->d_ksize);
 323                                 if (d->d_flags & D_BIGKEY)
 324                                         (void) printf(" (indirect)");
 325                                 (void) printf("; dsize %d", d->d_dsize);
 326                                 if (d->d_flags & D_BIGDATA)
 327                                         (void) printf(" (indirect)");
 328                         } else {
 329                                 id = (IDATUM *) GETDATUM(h,cur);
 330                                 (void) printf("size %d pgno %d",
 331                                         id->i_size, id->i_pgno);
 332                                 if (id->i_flags & D_BIGKEY)
 333                                         (void) printf(" (indirect)");
 334                         }
 335                         (void) printf("\n");
 336                 }
 337                 (void) printf("\n");
 338         }
 339 }
 340 #endif /* DEBUG */
 341
 342 #ifdef DEBUG
 343 _punt()
 344 {
 345         int pid;
 346
 347         pid = getpid();
 348         (void) kill(pid, SIGILL);
 349 }
 350 #endif /* DEBUG */