home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / online / source / c / compilers / Tickle-4.0.sit.hqx / Tickle-4.0 / cbtree / src / utils.c < prev    next >
Text File  |  1993-05-22  |  8KB  |  410 lines
  1.  
  2. #include <types.h>
  3. #include <fcntl.h>
  4. #include <ioctl.h>
  5. #include "db.h"
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <string.h>
  9. #include "btree.h"
  10.  
  11. /*
  12.  *  _BT_BUILDRET -- Build return key/data pair as a result of search or scan.
  13.  *
  14.  *    This routine manages the statically allocated buffers in which we
  15.  *    return data to the user.
  16.  *
  17.  *    Parameters:
  18.  *        t -- btree from which to return datum
  19.  *        d -- DATUM to be returned to the user.
  20.  *        data -- data argument supplied by user for return
  21.  *        key -- key argument supplied by user for return
  22.  *
  23.  *    Returns:
  24.  *        RET_SUCCESS, RET_ERROR.
  25.  *
  26.  *    Side Effects:
  27.  *        May free and reallocate static buffers, if the data
  28.  *        we want to return is bigger than the space we have to
  29.  *        do so.
  30.  */
  31.  
  32. static int _data_s = 0;
  33. static int _key_s = 0;
  34. static char *_data = (char *) NULL;
  35. static char *_key = (char *) NULL;
  36.  
  37. _bt_free_ret()
  38.     {
  39.     if (_key != (char *) NULL)
  40.         FREE(_key);
  41.     if (_data != (char *) NULL)
  42.         FREE(_data);
  43.     
  44.     _data_s = 0;
  45.     _key_s = 0;
  46.     }
  47.  
  48. int
  49. _bt_buildret(t, d, data, key)
  50.     BTREE_P t;
  51.     DATUM *d;
  52.     DBT *data;
  53.     DBT *key;
  54. {
  55.     pgno_t chain;
  56.  
  57.     if (d->d_flags & D_BIGKEY) {
  58.         if (_key != (char *) NULL)
  59.             FREE(_key);
  60.         bcopy((char *) &(d->d_bytes[0]),
  61.                        (char *) &chain,
  62.                        sizeof(chain));
  63.         if (_bt_getbig(t, chain, &_key, &_key_s) == RET_ERROR)
  64.             return (RET_ERROR);
  65.         key->data = (u_char *)_key;
  66.         key->size = _key_s;
  67.     } else {
  68.         /* need more space for key? */
  69.         if (d->d_ksize > _key_s) {
  70.             if (_key != (char *) NULL)
  71.                 FREE(_key);
  72.             if ((_key = (char *) cbMALLOC((unsigned) d->d_ksize))
  73.                 == (char *) NULL)
  74.                 return (RET_ERROR);
  75.             _key_s = d->d_ksize;
  76.         }
  77.  
  78.         key->data = (u_char *)_key;
  79.         if ((key->size = d->d_ksize) > 0)
  80.             bcopy(&(d->d_bytes[0]),
  81.                      _key,
  82.                      (int) d->d_ksize);
  83.     }
  84.  
  85.     if (d->d_flags & D_BIGDATA) {
  86.         if (_data != (char *) NULL)
  87.             FREE(_data);
  88.         bcopy(&(d->d_bytes[d->d_ksize]),
  89.                        (char *) &chain,
  90.                        sizeof(chain));
  91.         if (_bt_getbig(t, chain, &_data, &_data_s) == RET_ERROR)
  92.             return (RET_ERROR);
  93.         data->data = (u_char *)_data;
  94.         data->size = _data_s;
  95.     } else {
  96.         /* need more space for data? */
  97.         if (d->d_dsize > _data_s) {
  98.             if (_data != (char *) NULL)
  99.                 FREE (_data);
  100.             if ((_data = (char *) cbMALLOC((unsigned) d->d_dsize))
  101.                 == (char *) NULL)
  102.                 return (RET_ERROR);
  103.             _data_s = d->d_dsize;
  104.         }
  105.  
  106.         data->data = (u_char *)_data;
  107.  
  108.         if ((data->size = d->d_dsize) > 0)
  109.             bcopy(&(d->d_bytes[d->d_ksize]),
  110.                       _data,
  111.                       (size_t) (d->d_dsize));
  112.     }
  113.  
  114.     return (RET_SUCCESS);
  115. }
  116.  
  117. /*
  118.  *  _BT_CMP -- Compare a key to a given item on the current page.
  119.  *
  120.  *    This routine is a wrapper for the user's comparison function.
  121.  *
  122.  *    Parameters:
  123.  *        t -- tree in which to do comparison
  124.  *        p -- pointer to one argument for the comparison function
  125.  *        n -- index of item to supply second arg to comparison function
  126.  *
  127.  *    Returns:
  128.  *        < 0 if p is < item at n
  129.  *        = 0 if p is = item at n
  130.  *        > 0 if p is > item at n
  131.  */
  132.  
  133. int
  134. _bt_cmp(t, p, n)
  135.     BTREE_P t;
  136.     char *p;
  137.     index_t n;
  138. {
  139.     BTHEADER *h;
  140.     IDATUM *id;
  141.     DATUM *d;
  142.     char *arg;
  143.     int ignore;
  144.     int free_arg;
  145.     pgno_t chain;
  146.     int r;
  147.  
  148.     h = t->bt_curpage;
  149.  
  150.     /*
  151.      *  The left-most key at any level of the tree on internal pages
  152.      *  is guaranteed (artificially, by the code here) to be less than
  153.      *  any user key.  This saves us from having to update the leftmost
  154.      *  key when the user inserts a new key in the tree smaller than
  155.      *  anything we've seen yet.
  156.      */
  157.  
  158.     if (h->h_prevpg == P_NONE && !(h->h_flags & F_LEAF) && n == 0)
  159.         return (1);
  160.  
  161.     if (h->h_flags & F_LEAF) {
  162.         d = (DATUM *) GETDATUM(h,n);
  163.         if (d->d_flags & D_BIGKEY) {
  164.             free_arg = TRUE;
  165.             bcopy(&(d->d_bytes[0]), (char *) &chain, sizeof(chain));
  166.             if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR)
  167.                 return (RET_ERROR);
  168.         } else {
  169.             free_arg = FALSE;
  170.             arg = &(d->d_bytes[0]);
  171.         }
  172.     } else {
  173.         id = (IDATUM *) GETDATUM(h,n);
  174.         if (id->i_flags & D_BIGKEY) {
  175.             free_arg = TRUE;
  176.             bcopy(&(id->i_bytes[0]),
  177.                   (char *) &chain,
  178.                   sizeof(chain));
  179.             if (_bt_getbig(t, chain, &arg, &ignore) == RET_ERROR)
  180.                 return (RET_ERROR);
  181.         } else {
  182.             free_arg = FALSE;
  183.             arg = &(id->i_bytes[0]);
  184.         }
  185.     }
  186.     r = (*(t->bt_compare))(p, arg);
  187.  
  188.     if (free_arg)
  189.         FREE(arg);
  190.  
  191.     return (r);
  192. }
  193.  
  194. /*
  195.  *  _BT_PUSH/_BT_POP -- Push/pop a parent page number on the parent stack.
  196.  *
  197.  *    When we descend the tree, we keep track of parent pages in order
  198.  *    to handle splits on insertions.
  199.  *
  200.  *    Parameters:
  201.  *        t -- tree for which to push parent
  202.  *        pgno -- page number to push (_bt_push only)
  203.  *
  204.  *    Returns:
  205.  *        RET_SUCCESS, RET_ERROR.
  206.  */
  207.  
  208. int
  209. _bt_push(t, pgno)
  210.     BTREE_P t;
  211.     pgno_t pgno;
  212. {
  213.     BTSTACK *new;
  214.  
  215.     if ((new = (BTSTACK *) cbMALLOC((unsigned) sizeof(BTSTACK)))
  216.             == (BTSTACK *) NULL)
  217.         return (RET_ERROR);
  218.     
  219.     new->bts_pgno = pgno;
  220.     new->bts_next = t->bt_stack;
  221.     t->bt_stack = new;
  222.  
  223.     return (RET_SUCCESS);
  224. }
  225.  
  226. pgno_t
  227. _bt_pop(t)
  228.     BTREE_P t;
  229. {
  230.     BTSTACK *s;
  231.     pgno_t p = P_NONE;
  232.  
  233.     if ((s = t->bt_stack) != (BTSTACK *) NULL) {
  234.         p = s->bts_pgno;
  235.         t->bt_stack = s->bts_next;
  236.         FREE((char *) s);
  237.         }
  238.     
  239.     return (p);
  240.     }
  241.  
  242. /* TGE - entire function is mine! */
  243. _bt_clear_stack(t)
  244.     BTREE_P t;
  245. {
  246.     BTSTACK *s, *n;
  247.  
  248.     for (s = t->bt_stack ; s != (BTSTACK *) NULL ; )
  249.         {
  250.         n = s->bts_next;
  251.         FREE((char *) s);
  252.         s = n;
  253.         }
  254.     }
  255.  
  256. #ifdef DEBUG
  257. void
  258. _btdump(tree)
  259.     BTREE tree;
  260. {
  261.     BTREE_P t = (BTREE_P) tree;
  262.     DATUM *d;
  263.     IDATUM *id;
  264.     BTHEADER *h;
  265.     pgno_t npages;
  266.     pgno_t i;
  267.     index_t cur, top;
  268.  
  269.     npages = t->bt_npages;
  270.     printf("\"%s\" fd %d pgsz %d curpg %d @ 0x%lx",
  271.         t->bt_fname, t->bt_s.bt_d.d_fd,
  272.         t->bt_psize, t->bt_curpage);
  273.     printf("npg %d cmp 0x%lx flags=(", npages, t->bt_compare);
  274.     if (t->bt_flags & BTF_SEQINIT)
  275.         printf("BTF_SEQINIT");
  276.     printf(")\n");
  277.  
  278.     for (i = P_ROOT; i <= npages; i++) {
  279.         if (_bt_getpage(t, i) == RET_ERROR)
  280.             _punt();
  281.         h = t->bt_curpage;
  282.         top = NEXTINDEX(h);
  283.         printf("    page %d:\n", i);
  284.         printf("\tpgno %d prev %d next %d\n",
  285.             h->h_pgno, h->h_prevpg, h->h_nextpg);
  286.         printf("\tlower %d upper %d nextind %d flags (",
  287.             h->h_lower, h->h_upper, top);
  288.         if (h->h_flags & F_LEAF)
  289.             printf("F_LEAF");
  290.         else
  291.             printf("<internal>");
  292.         if (h->h_flags & F_DIRTY)
  293.             printf("|F_DIRTY");
  294.         if (h->h_flags & F_PRESERVE)
  295.             printf("|F_PRESERVE");
  296.         if (h->h_flags & F_CONT) {
  297.             printf("|F_CONT)");
  298.             if (h->h_prevpg == P_NONE) {
  299.                 size_t longsz;
  300.                 bcopy((char *) &(h->h_linp[0]),
  301.                           (char *) &longsz,
  302.                           sizeof(longsz));
  303.                 printf("\n\t\t(chain start, data length %ld)",
  304.                     longsz);
  305.             }
  306.             printf("\n");
  307.             continue;
  308.         }
  309.         printf(")\n");
  310.         for (cur = 0; cur < top; cur++) {
  311.             printf("\t  [%d] off %d ", cur, h->h_linp[cur]);
  312.             if (h->h_flags & F_LEAF) {
  313.                 d = (DATUM *) GETDATUM(h,cur);
  314.                 printf("ksize %d", d->d_ksize);
  315.                 if (d->d_flags & D_BIGKEY)
  316.                     printf(" (indirect)");
  317.                 printf("; dsize %d", d->d_dsize);
  318.                 if (d->d_flags & D_BIGDATA)
  319.                     printf(" (indirect)");
  320.             } else {
  321.                 id = (IDATUM *) GETDATUM(h,cur);
  322.                 printf("size %d pgno %d",
  323.                     id->i_size, id->i_pgno);
  324.                 if (id->i_flags & D_BIGKEY)
  325.                     printf(" (indirect)");
  326.             }
  327.             printf("\n");
  328.         }
  329.         printf("\n");
  330.     }
  331. }
  332. #endif /* DEBUG */
  333.  
  334. #ifdef DEBUG
  335. _punt()
  336. {
  337.     int pid;
  338.  
  339.     pid = getpid();
  340.     kill(pid, SIGILL);
  341. }
  342. #endif /* DEBUG */
  343.  
  344.  
  345.  
  346.  
  347. /* TGE --> Macintosh */
  348.  
  349. bcopy(from, to, n)
  350. char    *from, *to;
  351. int        n;
  352.     {
  353.     memmove(to, from, n);
  354.     }
  355.  
  356. bzero(ptr, n)
  357. char    *ptr;
  358. int        n;
  359.     {
  360.     memset(ptr, 0, n);
  361.     }
  362.  
  363. getpagesize()
  364.     {
  365.     return 512;
  366.     }
  367.  
  368. static char        zbuf[256];
  369.  
  370. ck_lseek(fd, pos, seek)
  371. int        fd;
  372. long    pos;
  373. int        seek;
  374.     {
  375.     int        myerr, bytes;
  376.     long    save_seek, eof_seek;
  377.     
  378.     if (seek == SEEK_SET)
  379.         {
  380.         save_seek = lseek(fd, 0, SEEK_CUR);
  381.         eof_seek = lseek(fd, 0, SEEK_END);
  382.         if (eof_seek < pos)
  383.             {
  384.             // fprintf(stderr, "***** NDBM: EXPAND FILE %d --> %d *****\n",
  385.             //        eof_seek, pos);
  386.         
  387.             memset(zbuf, 0, 256);
  388.             
  389.             for ( ; eof_seek < pos ; )
  390.                 {
  391.                 bytes = (pos - eof_seek);
  392.                 bytes = (bytes > 256 ? 256 : bytes);
  393.                 write(fd, zbuf, bytes);
  394.                 eof_seek += bytes;
  395.                 }
  396.             
  397.             myerr = ioctl(fd, FIOSETEOF, (long *)pos);
  398.             if (myerr == -1)
  399.                 {
  400.                 extern int errno;
  401.                 return -1;
  402.                 }
  403.             }
  404.         lseek(fd, save_seek, SEEK_SET);
  405.         }
  406.     
  407.     return lseek(fd, pos, seek);
  408.     }
  409.  
  410.