home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / access / nbtree / nbtutils.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  9.2 KB  |  392 lines
  1. /*
  2.  *  btutils.c -- Utility code for Postgres btree implementation.
  3.  */
  4.  
  5. #include "tmp/c.h"
  6. #include "tmp/postgres.h"
  7.  
  8. #include "storage/bufmgr.h"
  9. #include "storage/bufpage.h"
  10. #include "storage/page.h"
  11.  
  12. #include "utils/log.h"
  13. #include "utils/rel.h"
  14. #include "utils/excid.h"
  15.  
  16. #include "access/heapam.h"
  17. #include "access/genam.h"
  18. #include "access/iqual.h"
  19. #include "access/ftup.h"
  20. #include "access/nbtree.h"
  21.  
  22. RcsId("$Header: /private/postgres/src/access/nbtree/RCS/nbtutils.c,v 1.19 1992/05/27 16:30:48 mao Exp $");
  23.  
  24. ScanKey
  25. _bt_mkscankey(rel, itup)
  26.     Relation rel;
  27.     IndexTuple itup;
  28. {
  29.     ScanKey skey;
  30.     TupleDescriptor itupdesc;
  31.     int natts;
  32.     int i;
  33.     Datum arg;
  34.     RegProcedure proc;
  35.     Boolean null;
  36.  
  37.     natts = rel->rd_rel->relnatts;
  38.     itupdesc = RelationGetTupleDescriptor(rel);
  39.  
  40.     skey = (ScanKey) palloc(natts * sizeof(ScanKeyEntryData));
  41.  
  42.     for (i = 0; i < natts; i++) {
  43.     arg = (Datum) index_getattr(itup, i + 1, itupdesc, &null);
  44.     proc = index_getprocid(rel, i + 1, BTORDER_PROC);
  45.     ScanKeyEntryInitialize((ScanKeyEntry) &(skey->data[i]),
  46.                            0x0, (AttributeNumber) (i + 1), proc, arg);
  47.     }
  48.  
  49.     return (skey);
  50. }
  51.  
  52. void
  53. _bt_freeskey(skey)
  54.     ScanKey skey;
  55. {
  56.     pfree (skey);
  57. }
  58.  
  59. void
  60. _bt_freestack(stack)
  61.     BTStack stack;
  62. {
  63.     BTStack ostack;
  64.  
  65.     while (stack != (BTStack) NULL) {
  66.     ostack = stack;
  67.     stack = stack->bts_parent;
  68.     pfree(ostack->bts_btitem);
  69.     pfree(ostack);
  70.     }
  71. }
  72.  
  73. /*
  74.  *  _bt_orderkeys() -- Put keys in a sensible order for conjunctive quals.
  75.  *
  76.  *    The order of the keys in the qual match the ordering imposed by
  77.  *    the index.  This routine only needs to be called if there are
  78.  *    more than one qual clauses using this index.
  79.  */
  80.  
  81. void
  82. _bt_orderkeys(relation, numberOfKeys, key)
  83.     Relation relation;
  84.     uint16 *numberOfKeys;
  85.     ScanKey key;
  86. {
  87.     ScanKey xform;
  88.     ScanKeyEntryData *cur;
  89.     StrategyMap map;
  90.     int nbytes;
  91.     int test;
  92.     int i, j;
  93.     int init[BTMaxStrategyNumber+1];
  94.  
  95.     /* haven't looked at any strategies yet */
  96.     for (i = 0; i <= BTMaxStrategyNumber; i++)
  97.     init[i] = 0;
  98.  
  99.     /* get space for the modified array of keys */
  100.     nbytes = BTMaxStrategyNumber * sizeof (ScanKeyEntryData);
  101.     xform = (ScanKey) palloc(nbytes);
  102.     bzero(xform, nbytes);
  103.  
  104.     /* get the strategy map for this index/attribute pair */
  105.     /*
  106.      *  XXX
  107.      *  When we support multiple keys in a single index, this is what
  108.      *  we'll want to do.  At present, the planner is hosed, so we
  109.      *  hard-wire the attribute number below.  Postgres only does single-
  110.      *  key indices...
  111.      * map = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(relation),
  112.      *                     BTMaxStrategyNumber,
  113.      *                     key->data[0].attributeNumber);
  114.      */
  115.      map = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(relation),
  116.                     BTMaxStrategyNumber,
  117.                     1 /* XXX */ );
  118.  
  119.     /* check each key passed in */
  120.     for (i = *numberOfKeys; --i >= 0; ) {
  121.     cur = &(key->data[i]);
  122.     for (j = BTMaxStrategyNumber; --j >= 0; ) {
  123.         if (cur->procedure == map->entry[j].procedure)
  124.             break;
  125.     }
  126.  
  127.     /* have we seen one of these before? */
  128.     if (init[j]) {
  129.         /* yup, use the appropriate value */
  130.         test = (int) (*(cur->func))(cur->argument,
  131.                         xform->data[j].argument);
  132.         if (test)
  133.         xform->data[j].argument = cur->argument;
  134.     } else {
  135.         /* nope, use this value */
  136.         bcopy(cur, &xform->data[j], sizeof (*cur));
  137.         init[j] = 1;
  138.     }
  139.     }
  140.  
  141.     /* if = has been specified, no other key will be used */
  142.     if (init[BTEqualStrategyNumber - 1]) {
  143.     init[BTLessStrategyNumber - 1] = 0;
  144.     init[BTLessEqualStrategyNumber - 1] = 0;
  145.     init[BTGreaterEqualStrategyNumber - 1] = 0;
  146.     init[BTGreaterStrategyNumber - 1] = 0;
  147.     }
  148.  
  149.     /* only one of <, <= */
  150.     if (init[BTLessStrategyNumber - 1]
  151.     && init[BTLessEqualStrategyNumber - 1]) {
  152.  
  153.     ScanKeyEntryData *lt, *le;
  154.  
  155.     lt = &xform->data[BTLessStrategyNumber - 1];
  156.     le = &xform->data[BTLessEqualStrategyNumber - 1];
  157.  
  158.     /*
  159.      *  DO NOT use the cached function stuff here -- this is key
  160.      *  ordering, happens only when the user expresses a hokey
  161.      *  qualification, and gets executed only once, anyway.  The
  162.      *  transform maps are hard-coded, and can't be initialized
  163.      *  in the correct way.
  164.      */
  165.  
  166.     test = (int) fmgr(le->procedure, le->argument, lt->argument);
  167.  
  168.     if (test)
  169.         init[BTLessEqualStrategyNumber - 1] = 0;
  170.     else
  171.         init[BTLessStrategyNumber - 1] = 0;
  172.     }
  173.  
  174.     /* only one of >, >= */
  175.     if (init[BTGreaterStrategyNumber - 1]
  176.     && init[BTGreaterEqualStrategyNumber - 1]) {
  177.  
  178.     ScanKeyEntryData *gt, *ge;
  179.  
  180.     gt = &xform->data[BTGreaterStrategyNumber - 1];
  181.     ge = &xform->data[BTGreaterEqualStrategyNumber - 1];
  182.  
  183.     /* see note above on function cache */
  184.     test = (int) fmgr(ge->procedure, gt->argument, gt->argument);
  185.  
  186.     if (test)
  187.         init[BTGreaterStrategyNumber - 1] = 0;
  188.     else
  189.         init[BTGreaterEqualStrategyNumber - 1] = 0;
  190.     }
  191.  
  192.     /* okay, reorder and count */
  193.     j = 0;
  194.  
  195.     for (i = BTMaxStrategyNumber; --i >= 0; )
  196.     if (init[i])
  197.         key->data[j++] = xform->data[i];
  198.  
  199.     *numberOfKeys = j;
  200.  
  201.     pfree (xform);
  202. }
  203.  
  204. #include <stdio.h>
  205.  
  206. _bt_dump(rel)
  207.     Relation rel;
  208. {
  209.     Buffer buf;
  210.     Page page;
  211.     BTPageOpaque opaque;
  212.     ItemId itemid;
  213.     BTItem item;
  214.     OffsetIndex offind, maxoff, start;
  215.     BlockNumber nxtbuf;
  216.     TupleDescriptor itupdesc;
  217.     IndexTuple itup;
  218.     Boolean isnull;
  219.     Datum keyvalue;
  220.     uint16 flags;
  221.     BlockNumber i, nblocks;
  222.  
  223.     printf("----------------------- tree dump --------------------------\n");
  224.     nblocks = RelationGetNumberOfBlocks(rel);
  225.     itupdesc = RelationGetTupleDescriptor(rel);
  226.  
  227.     for (i = 1; i < nblocks; i++) {
  228.     buf = _bt_getbuf(rel, i, BT_READ);
  229.     page = BufferGetPage(buf, 0);
  230.     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  231.  
  232.     printf("page %d prev %d next %d", BufferGetBlockNumber(buf),
  233.         opaque->btpo_prev, opaque->btpo_next);
  234.  
  235.     flags = opaque->btpo_flags;
  236.  
  237.     if (flags & BTP_ROOT)
  238.         printf (" <root>");
  239.     if (flags & BTP_LEAF)
  240.         printf (" <leaf>");
  241.     if (flags & BTP_FREE)
  242.         printf (" <free>");
  243.  
  244.     printf("\n");
  245.  
  246.     if (opaque->btpo_next != P_NONE) {
  247.         printf("    high key:");
  248.         _bt_dumptup(rel, itupdesc, page, 0);
  249.         start = 1;
  250.     } else {
  251.         printf(" no high key\n");
  252.         start = 0;
  253.     }
  254.  
  255.     maxoff = PageGetMaxOffsetIndex(page);
  256.     if (!PageIsEmpty(page) &&
  257.          (opaque->btpo_next == P_NONE || maxoff != start)) {
  258.         for (offind = start; offind <= maxoff; offind++) {
  259.         printf("\t{%d} ", offind + 1);
  260.         _bt_dumptup(rel, itupdesc, page, offind);
  261.         }
  262.     }
  263.     _bt_relbuf(rel, buf, BT_READ);
  264.     }
  265. }
  266.  
  267. _bt_dumppg(rel, page)
  268.     Relation rel;
  269.     Page page;
  270. {
  271.     BTPageOpaque opaque;
  272.     ItemId itemid;
  273.     BTItem item;
  274.     OffsetIndex offind, maxoff, start;
  275.     BlockNumber nxtbuf;
  276.     TupleDescriptor itupdesc;
  277.     IndexTuple itup;
  278.     Boolean isnull;
  279.     Datum keyvalue;
  280.     uint16 flags;
  281.  
  282.     itupdesc = RelationGetTupleDescriptor(rel);
  283.  
  284.     opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  285.  
  286.     printf("prev %d next %d", opaque->btpo_prev, opaque->btpo_next);
  287.  
  288.     flags = opaque->btpo_flags;
  289.  
  290.     if (flags & BTP_ROOT)
  291.     printf (" <root>");
  292.     if (flags & BTP_LEAF)
  293.     printf (" <leaf>");
  294.     if (flags & BTP_FREE)
  295.     printf (" <free>");
  296.  
  297.     printf("\n");
  298.  
  299.     if (opaque->btpo_next != P_NONE) {
  300.     printf("    high key:");
  301.     _bt_dumptup(rel, itupdesc, page, 0);
  302.     start = 1;
  303.     } else {
  304.     printf(" no high key\n");
  305.     start = 0;
  306.     }
  307.  
  308.     maxoff = PageGetMaxOffsetIndex(page);
  309.     if (!PageIsEmpty(page) &&
  310.      (opaque->btpo_next == P_NONE || maxoff != start)) {
  311.     for (offind = start; offind <= maxoff; offind++) {
  312.         printf("\t{%d} ", offind + 1);
  313.         _bt_dumptup(rel, itupdesc, page, offind);
  314.     }
  315.     }
  316. }
  317.  
  318. #include "tmp/datum.h"
  319.  
  320. _bt_dumptup(rel, itupdesc, page, offind)
  321.     Relation rel;
  322.     TupleDescriptor itupdesc;
  323.     Page page;
  324.     OffsetIndex offind;
  325. {
  326.     ItemId itemid;
  327.     Size itemsz;
  328.     BTItem btitem;
  329.     IndexTuple itup;
  330.     Size tuplen;
  331.     ItemPointer iptr;
  332.     BlockNumber blkno;
  333.     PageNumber pgno;
  334.     OffsetNumber offno;
  335.     Datum idatum;
  336.     int16 tmpkey;
  337.     Boolean null;
  338.  
  339.     itemid = PageGetItemId(page, offind);
  340.     itemsz = ItemIdGetLength(itemid);
  341.     btitem = (BTItem) PageGetItem(page, itemid);
  342.     itup = &(btitem->bti_itup);
  343.     tuplen = IndexTupleSize(itup);
  344.     iptr = &(itup->t_tid);
  345.     blkno = (iptr->blockData.data[0] << 16) + (uint16) iptr->blockData.data[1];
  346.     pgno = 0;
  347.     offno = (OffsetNumber) (iptr->positionData & 0xffff);
  348.  
  349.     idatum = IndexTupleGetAttributeValue(itup, 1, itupdesc, &null);
  350.     tmpkey = DatumGetInt32(idatum);
  351.  
  352.     printf("[%d/%d bytes] <%d,%d,%d> %ld (oid %ld)\n", itemsz, tuplen,
  353.         blkno, pgno, offno, tmpkey, btitem->bti_oid);
  354. }
  355.  
  356. bool
  357. _bt_checkqual(scan, itup)
  358.     IndexScanDesc scan;
  359.     IndexTuple itup;
  360. {
  361.     if (scan->numberOfKeys > 0)
  362.     return (ikeytest(itup, scan->relation,
  363.              scan->numberOfKeys, &(scan->keyData)));
  364.     else
  365.     return (true);
  366. }
  367.  
  368. BTItem
  369. _bt_formitem(itup)
  370.     IndexTuple itup;
  371. {
  372.     int nbytes_btitem;
  373.     BTItem btitem;
  374.     Size tuplen;
  375.     extern OID newoid();
  376.  
  377.     /* disallow nulls in btree keys */
  378.     if (itup->t_info & INDEX_NULL_MASK)
  379.     elog(WARN, "btree indices cannot include null keys");
  380.  
  381.     /* make a copy of the index tuple with room for the sequence number */
  382.     tuplen = IndexTupleSize(itup);
  383.     nbytes_btitem = tuplen +
  384.             (sizeof(BTItemData) - sizeof(IndexTupleData));
  385.  
  386.     btitem = (BTItem) palloc(nbytes_btitem);
  387.     bcopy((char *) itup, (char *) &(btitem->bti_itup), tuplen);
  388.  
  389.     btitem->bti_oid = newoid();
  390.     return (btitem);
  391. }
  392.