开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数据库系统 > 查看源码
rtree.c
资源名称：postgresql-6.5.2.tar.gz　[点击查看]
上传用户：blenddy
上传日期：2007-01-07
资源大小：6495k
文件大小：25k
源码类别：

数据库系统

开发平台：

Unix_Linux

rtree.c：源码内容
  1. /*-------------------------------------------------------------------------
  2.  *
  3.  * rtree.c
  4.  *   interface routines for the postgres rtree indexed access method.
  5.  *
  6.  * Copyright (c) 1994, Regents of the University of California
  7.  *
  8.  *
  9.  * IDENTIFICATION
  10.  *   $Header: /usr/local/cvsroot/pgsql/src/backend/access/rtree/rtree.c,v 1.32.2.1 1999/08/02 05:24:44 scrappy Exp $
  11.  *
  12.  *-------------------------------------------------------------------------
  13.  */
  15. #include "postgres.h"
  17. #include "access/genam.h"
  18. #include "access/heapam.h"
  19. #include "access/rtree.h"
  20. #include "catalog/index.h"
  21. #include "executor/executor.h"
  22. #include "utils/geo_decls.h"
  25. typedef struct SPLITVEC
  26. {
  27. OffsetNumber *spl_left;
  28. int spl_nleft;
  29. char    *spl_ldatum;
  30. OffsetNumber *spl_right;
  31. int spl_nright;
  32. char    *spl_rdatum;
  33. } SPLITVEC;
  35. typedef struct RTSTATE
  36. {
  37. FmgrInfo unionFn; /* union function */
  38. FmgrInfo sizeFn; /* size function */
  39. FmgrInfo interFn; /* intersection function */
  40. } RTSTATE;
  42. /* non-export function prototypes */
  43. static InsertIndexResult rtdoinsert(Relation r, IndexTuple itup,
  44.    RTSTATE *rtstate);
  45. static void rttighten(Relation r, RTSTACK *stk, char *datum, int att_size,
  46.   RTSTATE *rtstate);
  47. static InsertIndexResult dosplit(Relation r, Buffer buffer, RTSTACK *stack,
  48. IndexTuple itup, RTSTATE *rtstate);
  49. static void rtintinsert(Relation r, RTSTACK *stk, IndexTuple ltup,
  50. IndexTuple rtup, RTSTATE *rtstate);
  51. static void rtnewroot(Relation r, IndexTuple lt, IndexTuple rt);
  52. static void picksplit(Relation r, Page page, SPLITVEC *v, IndexTuple itup,
  53.   RTSTATE *rtstate);
  54. static void RTInitBuffer(Buffer b, uint32 f);
  55. static OffsetNumber choose(Relation r, Page p, IndexTuple it,
  56.    RTSTATE *rtstate);
  57. static int nospace(Page p, IndexTuple it);
  58. static void initRtstate(RTSTATE *rtstate, Relation index);
  61. void
  62. rtbuild(Relation heap,
  63. Relation index,
  64. int natts,
  65. AttrNumber *attnum,
  66. IndexStrategy istrat,
  67. uint16 pcount,
  68. Datum *params,
  69. FuncIndexInfo *finfo,
  70. PredInfo *predInfo)
  71. {
  72. HeapScanDesc scan;
  73. AttrNumber i;
  74. HeapTuple htup;
  75. IndexTuple itup;
  76. TupleDesc hd,
  77. id;
  78. InsertIndexResult res;
  79. Datum    *d;
  80. bool    *nulls;
  81. Buffer buffer = InvalidBuffer;
  82. int nb,
  83. nh,
  84. ni;
  86. #ifndef OMIT_PARTIAL_INDEX
  87. ExprContext *econtext;
  88. TupleTable tupleTable;
  89. TupleTableSlot *slot;
  91. #endif
  92. Oid hrelid,
  93. irelid;
  94. Node    *pred,
  95.    *oldPred;
  96. RTSTATE rtState;
  98. initRtstate(&rtState, index);
  100. pred = predInfo->pred;
  101. oldPred = predInfo->oldPred;
  103. /*
  104.  * We expect to be called exactly once for any index relation. If
  105.  * that's not the case, big trouble's what we have.
  106.  */
  108. if (oldPred == NULL && (nb = RelationGetNumberOfBlocks(index)) != 0)
  109. elog(ERROR, "%s already contains data", index->rd_rel->relname.data);
  111. /* initialize the root page (if this is a new index) */
  112. if (oldPred == NULL)
  113. {
  114. buffer = ReadBuffer(index, P_NEW);
  115. RTInitBuffer(buffer, F_LEAF);
  116. WriteBuffer(buffer);
  117. }
  119. /* init the tuple descriptors and get set for a heap scan */
  120. hd = RelationGetDescr(heap);
  121. id = RelationGetDescr(index);
  122. d = (Datum *) palloc(natts * sizeof(*d));
  123. nulls = (bool *) palloc(natts * sizeof(*nulls));
  125. /*
  126.  * If this is a predicate (partial) index, we will need to evaluate
  127.  * the predicate using ExecQual, which requires the current tuple to
  128.  * be in a slot of a TupleTable.  In addition, ExecQual must have an
  129.  * ExprContext referring to that slot. Here, we initialize dummy
  130.  * TupleTable and ExprContext objects for this purpose. --Nels, Feb
  131.  * '92
  132.  */
  133. #ifndef OMIT_PARTIAL_INDEX
  134. if (pred != NULL || oldPred != NULL)
  135. {
  136. tupleTable = ExecCreateTupleTable(1);
  137. slot = ExecAllocTableSlot(tupleTable);
  138. econtext = makeNode(ExprContext);
  139. FillDummyExprContext(econtext, slot, hd, buffer);
  140. }
  141. else
  142. {
  143. econtext = NULL;
  144. tupleTable = NULL;
  145. slot = NULL;
  146. }
  147. #endif  /* OMIT_PARTIAL_INDEX */
  149. /* count the tuples as we insert them */
  150. nh = ni = 0;
  152. scan = heap_beginscan(heap, 0, SnapshotNow, 0, (ScanKey) NULL);
  154. while (HeapTupleIsValid(htup = heap_getnext(scan, 0)))
  155. {
  156. nh++;
  158. /*
  159.  * If oldPred != NULL, this is an EXTEND INDEX command, so skip
  160.  * this tuple if it was already in the existing partial index
  161.  */
  162. if (oldPred != NULL)
  163. {
  164. #ifndef OMIT_PARTIAL_INDEX
  165. /* SetSlotContents(slot, htup); */
  166. slot->val = htup;
  167. if (ExecQual((List *) oldPred, econtext) == true)
  168. {
  169. ni++;
  170. continue;
  171. }
  172. #endif  /* OMIT_PARTIAL_INDEX */
  173. }
  175. /*
  176.  * Skip this tuple if it doesn't satisfy the partial-index
  177.  * predicate
  178.  */
  179. if (pred != NULL)
  180. {
  181. #ifndef OMIT_PARTIAL_INDEX
  182. /* SetSlotContents(slot, htup); */
  183. slot->val = htup;
  184. if (ExecQual((List *) pred, econtext) == false)
  185. continue;
  186. #endif  /* OMIT_PARTIAL_INDEX */
  187. }
  189. ni++;
  191. /*
  192.  * For the current heap tuple, extract all the attributes we use
  193.  * in this index, and note which are null.
  194.  */
  196. for (i = 1; i <= natts; i++)
  197. {
  198. int attoff;
  199. bool attnull;
  201. /*
  202.  * Offsets are from the start of the tuple, and are
  203.  * zero-based; indices are one-based.  The next call returns i
  204.  * - 1.  That's data hiding for you.
  205.  */
  207. attoff = AttrNumberGetAttrOffset(i);
  209. /*
  210.  * d[attoff] = HeapTupleGetAttributeValue(htup, buffer,
  211.  */
  212. d[attoff] = GetIndexValue(htup,
  213.   hd,
  214.   attoff,
  215.   attnum,
  216.   finfo,
  217.   &attnull);
  218. nulls[attoff] = (attnull ? 'n' : ' ');
  219. }
  221. /* form an index tuple and point it at the heap tuple */
  222. itup = index_formtuple(id, &d[0], nulls);
  223. itup->t_tid = htup->t_self;
  225. /*
  226.  * Since we already have the index relation locked, we call
  227.  * rtdoinsert directly.  Normal access method calls dispatch
  228.  * through rtinsert, which locks the relation for write.  This is
  229.  * the right thing to do if you're inserting single tups, but not
  230.  * when you're initializing the whole index at once.
  231.  */
  233. res = rtdoinsert(index, itup, &rtState);
  234. pfree(itup);
  235. pfree(res);
  236. }
  238. /* okay, all heap tuples are indexed */
  239. heap_endscan(scan);
  241. if (pred != NULL || oldPred != NULL)
  242. {
  243. #ifndef OMIT_PARTIAL_INDEX
  244. ExecDestroyTupleTable(tupleTable, true);
  245. pfree(econtext);
  246. #endif  /* OMIT_PARTIAL_INDEX */
  247. }
  249. /*
  250.  * Since we just counted the tuples in the heap, we update its stats
  251.  * in pg_relation to guarantee that the planner takes advantage of the
  252.  * index we just created.  UpdateStats() does a
  253.  * CommandCounterIncrement(), which flushes changed entries from the
  254.  * system relcache.  The act of constructing an index changes these
  255.  * heap and index tuples in the system catalogs, so they need to be
  256.  * flushed.  We close them to guarantee that they will be.
  257.  */
  259. hrelid = RelationGetRelid(heap);
  260. irelid = RelationGetRelid(index);
  261. heap_close(heap);
  262. index_close(index);
  264. UpdateStats(hrelid, nh, true);
  265. UpdateStats(irelid, ni, false);
  267. if (oldPred != NULL)
  268. {
  269. if (ni == nh)
  270. pred = NULL;
  271. UpdateIndexPredicate(irelid, oldPred, pred);
  272. }
  274. /* be tidy */
  275. pfree(nulls);
  276. pfree(d);
  277. }
  279. /*
  280.  * rtinsert -- wrapper for rtree tuple insertion.
  281.  *
  282.  *   This is the public interface routine for tuple insertion in rtrees.
  283.  *   It doesn't do any work; just locks the relation and passes the buck.
  284.  */
  285. InsertIndexResult
  286. rtinsert(Relation r, Datum *datum, char *nulls, ItemPointer ht_ctid, Relation heapRel)
  287. {
  288. InsertIndexResult res;
  289. IndexTuple itup;
  290. RTSTATE rtState;
  292. /* generate an index tuple */
  293. itup = index_formtuple(RelationGetDescr(r), datum, nulls);
  294. itup->t_tid = *ht_ctid;
  295. initRtstate(&rtState, r);
  297. /*
  298.  * Notes in ExecUtils:ExecOpenIndices()
  299.  *
  300.  * RelationSetLockForWrite(r);
  301.  */
  303. res = rtdoinsert(r, itup, &rtState);
  305. return res;
  306. }
  308. static InsertIndexResult
  309. rtdoinsert(Relation r, IndexTuple itup, RTSTATE *rtstate)
  310. {
  311. Page page;
  312. Buffer buffer;
  313. BlockNumber blk;
  314. IndexTuple which;
  315. OffsetNumber l;
  316. RTSTACK    *stack;
  317. InsertIndexResult res;
  318. RTreePageOpaque opaque;
  319. char    *datum;
  321. blk = P_ROOT;
  322. buffer = InvalidBuffer;
  323. stack = (RTSTACK *) NULL;
  325. do
  326. {
  327. /* let go of current buffer before getting next */
  328. if (buffer != InvalidBuffer)
  329. ReleaseBuffer(buffer);
  331. /* get next buffer */
  332. buffer = ReadBuffer(r, blk);
  333. page = (Page) BufferGetPage(buffer);
  335. opaque = (RTreePageOpaque) PageGetSpecialPointer(page);
  336. if (!(opaque->flags & F_LEAF))
  337. {
  338. RTSTACK    *n;
  339. ItemId iid;
  341. n = (RTSTACK *) palloc(sizeof(RTSTACK));
  342. n->rts_parent = stack;
  343. n->rts_blk = blk;
  344. n->rts_child = choose(r, page, itup, rtstate);
  345. stack = n;
  347. iid = PageGetItemId(page, n->rts_child);
  348. which = (IndexTuple) PageGetItem(page, iid);
  349. blk = ItemPointerGetBlockNumber(&(which->t_tid));
  350. }
  351. } while (!(opaque->flags & F_LEAF));
  353. if (nospace(page, itup))
  354. {
  355. /* need to do a split */
  356. res = dosplit(r, buffer, stack, itup, rtstate);
  357. freestack(stack);
  358. WriteBuffer(buffer); /* don't forget to release buffer! */
  359. return res;
  360. }
  362. /* add the item and write the buffer */
  363. if (PageIsEmpty(page))
  364. {
  365. l = PageAddItem(page, (Item) itup, IndexTupleSize(itup),
  366. FirstOffsetNumber,
  367. LP_USED);
  368. }
  369. else
  370. {
  371. l = PageAddItem(page, (Item) itup, IndexTupleSize(itup),
  372. OffsetNumberNext(PageGetMaxOffsetNumber(page)),
  373. LP_USED);
  374. }
  376. WriteBuffer(buffer);
  378. datum = (((char *) itup) + sizeof(IndexTupleData));
  380. /* now expand the page boundary in the parent to include the new child */
  381. rttighten(r, stack, datum,
  382.   (IndexTupleSize(itup) - sizeof(IndexTupleData)), rtstate);
  383. freestack(stack);
  385. /* build and return an InsertIndexResult for this insertion */
  386. res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
  387. ItemPointerSet(&(res->pointerData), blk, l);
  389. return res;
  390. }
  392. static void
  393. rttighten(Relation r,
  394.   RTSTACK *stk,
  395.   char *datum,
  396.   int att_size,
  397.   RTSTATE *rtstate)
  398. {
  399. char    *oldud;
  400. char    *tdatum;
  401. Page p;
  402. float old_size,
  403. newd_size;
  404. Buffer b;
  406. if (stk == (RTSTACK *) NULL)
  407. return;
  409. b = ReadBuffer(r, stk->rts_blk);
  410. p = BufferGetPage(b);
  412. oldud = (char *) PageGetItem(p, PageGetItemId(p, stk->rts_child));
  413. oldud += sizeof(IndexTupleData);
  415. (*fmgr_faddr(&rtstate->sizeFn)) (oldud, &old_size);
  416. datum = (char *) (*fmgr_faddr(&rtstate->unionFn)) (oldud, datum);
  418. (*fmgr_faddr(&rtstate->sizeFn)) (datum, &newd_size);
  420. if (newd_size != old_size)
  421. {
  422. TupleDesc td = RelationGetDescr(r);
  424. if (td->attrs[0]->attlen < 0)
  425. {
  427. /*
  428.  * This is an internal page, so 'oldud' had better be a union
  429.  * (constant-length) key, too. (See comment below.)
  430.  */
  431. Assert(VARSIZE(datum) == VARSIZE(oldud));
  432. memmove(oldud, datum, VARSIZE(datum));
  433. }
  434. else
  435. memmove(oldud, datum, att_size);
  436. WriteBuffer(b);
  438. /*
  439.  * The user may be defining an index on variable-sized data (like
  440.  * polygons).  If so, we need to get a constant-sized datum for
  441.  * insertion on the internal page. We do this by calling the
  442.  * union proc, which is guaranteed to return a rectangle.
  443.  */
  445. tdatum = (char *) (*fmgr_faddr(&rtstate->unionFn)) (datum, datum);
  446. rttighten(r, stk->rts_parent, tdatum, att_size, rtstate);
  447. pfree(tdatum);
  448. }
  449. else
  450. ReleaseBuffer(b);
  451. pfree(datum);
  452. }
  454. /*
  455.  * dosplit -- split a page in the tree.
  456.  *
  457.  *   This is the quadratic-cost split algorithm Guttman describes in
  458.  *   his paper.  The reason we chose it is that you can implement this
  459.  *   with less information about the data types on which you're operating.
  460.  */
  461. static InsertIndexResult
  462. dosplit(Relation r,
  463. Buffer buffer,
  464. RTSTACK *stack,
  465. IndexTuple itup,
  466. RTSTATE *rtstate)
  467. {
  468. Page p;
  469. Buffer leftbuf,
  470. rightbuf;
  471. Page left,
  472. right;
  473. ItemId itemid;
  474. IndexTuple item;
  475. IndexTuple ltup,
  476. rtup;
  477. OffsetNumber maxoff;
  478. OffsetNumber i;
  479. OffsetNumber leftoff,
  480. rightoff;
  481. BlockNumber lbknum,
  482. rbknum;
  483. BlockNumber bufblock;
  484. RTreePageOpaque opaque;
  485. int blank;
  486. InsertIndexResult res;
  487. char    *isnull;
  488. SPLITVEC v;
  489. TupleDesc tupDesc;
  491. isnull = (char *) palloc(r->rd_rel->relnatts);
  492. for (blank = 0; blank < r->rd_rel->relnatts; blank++)
  493. isnull[blank] = ' ';
  494. p = (Page) BufferGetPage(buffer);
  495. opaque = (RTreePageOpaque) PageGetSpecialPointer(p);
  497. /*
  498.  * The root of the tree is the first block in the relation.  If we're
  499.  * about to split the root, we need to do some hocus-pocus to enforce
  500.  * this guarantee.
  501.  */
  503. if (BufferGetBlockNumber(buffer) == P_ROOT)
  504. {
  505. leftbuf = ReadBuffer(r, P_NEW);
  506. RTInitBuffer(leftbuf, opaque->flags);
  507. lbknum = BufferGetBlockNumber(leftbuf);
  508. left = (Page) BufferGetPage(leftbuf);
  509. }
  510. else
  511. {
  512. leftbuf = buffer;
  513. IncrBufferRefCount(buffer);
  514. lbknum = BufferGetBlockNumber(buffer);
  515. left = (Page) PageGetTempPage(p, sizeof(RTreePageOpaqueData));
  516. }
  518. rightbuf = ReadBuffer(r, P_NEW);
  519. RTInitBuffer(rightbuf, opaque->flags);
  520. rbknum = BufferGetBlockNumber(rightbuf);
  521. right = (Page) BufferGetPage(rightbuf);
  523. picksplit(r, p, &v, itup, rtstate);
  525. leftoff = rightoff = FirstOffsetNumber;
  526. maxoff = PageGetMaxOffsetNumber(p);
  527. for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
  528. {
  529. itemid = PageGetItemId(p, i);
  530. item = (IndexTuple) PageGetItem(p, itemid);
  532. if (i == *(v.spl_left))
  533. {
  534. PageAddItem(left, (Item) item, IndexTupleSize(item),
  535. leftoff, LP_USED);
  536. leftoff = OffsetNumberNext(leftoff);
  537. v.spl_left++; /* advance in left split vector */
  538. }
  539. else
  540. {
  541. PageAddItem(right, (Item) item, IndexTupleSize(item),
  542. rightoff, LP_USED);
  543. rightoff = OffsetNumberNext(rightoff);
  544. v.spl_right++; /* advance in right split vector */
  545. }
  546. }
  548. /* build an InsertIndexResult for this insertion */
  549. res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
  551. /* now insert the new index tuple */
  552. if (*(v.spl_left) != FirstOffsetNumber)
  553. {
  554. PageAddItem(left, (Item) itup, IndexTupleSize(itup),
  555. leftoff, LP_USED);
  556. leftoff = OffsetNumberNext(leftoff);
  557. ItemPointerSet(&(res->pointerData), lbknum, leftoff);
  558. }
  559. else
  560. {
  561. PageAddItem(right, (Item) itup, IndexTupleSize(itup),
  562. rightoff, LP_USED);
  563. rightoff = OffsetNumberNext(rightoff);
  564. ItemPointerSet(&(res->pointerData), rbknum, rightoff);
  565. }
  567. if ((bufblock = BufferGetBlockNumber(buffer)) != P_ROOT)
  568. PageRestoreTempPage(left, p);
  569. WriteBuffer(leftbuf);
  570. WriteBuffer(rightbuf);
  572. /*
  573.  * Okay, the page is split.  We have three things left to do:
  574.  *
  575.  * 1)  Adjust any active scans on this index to cope with changes we
  576.  * introduced in its structure by splitting this page.
  577.  *
  578.  * 2)  "Tighten" the bounding box of the pointer to the left page in the
  579.  * parent node in the tree, if any.  Since we moved a bunch of stuff
  580.  * off the left page, we expect it to get smaller. This happens in
  581.  * the internal insertion routine.
  582.  *
  583.  * 3)  Insert a pointer to the right page in the parent.  This may cause
  584.  * the parent to split.  If it does, we need to repeat steps one and
  585.  * two for each split node in the tree.
  586.  */
  588. /* adjust active scans */
  589. rtadjscans(r, RTOP_SPLIT, bufblock, FirstOffsetNumber);
  591. tupDesc = r->rd_att;
  592. ltup = (IndexTuple) index_formtuple(tupDesc,
  593.   (Datum *) &(v.spl_ldatum), isnull);
  594. rtup = (IndexTuple) index_formtuple(tupDesc,
  595.   (Datum *) &(v.spl_rdatum), isnull);
  596. pfree(isnull);
  598. /* set pointers to new child pages in the internal index tuples */
  599. ItemPointerSet(&(ltup->t_tid), lbknum, 1);
  600. ItemPointerSet(&(rtup->t_tid), rbknum, 1);
  602. rtintinsert(r, stack, ltup, rtup, rtstate);
  604. pfree(ltup);
  605. pfree(rtup);
  607. return res;
  608. }
  610. static void
  611. rtintinsert(Relation r,
  612. RTSTACK *stk,
  613. IndexTuple ltup,
  614. IndexTuple rtup,
  615. RTSTATE *rtstate)
  616. {
  617. IndexTuple old;
  618. Buffer b;
  619. Page p;
  620. char    *ldatum,
  621.    *rdatum,
  622.    *newdatum;
  623. InsertIndexResult res;
  625. if (stk == (RTSTACK *) NULL)
  626. {
  627. rtnewroot(r, ltup, rtup);
  628. return;
  629. }
  631. b = ReadBuffer(r, stk->rts_blk);
  632. p = BufferGetPage(b);
  633. old = (IndexTuple) PageGetItem(p, PageGetItemId(p, stk->rts_child));
  635. /*
  636.  * This is a hack. Right now, we force rtree keys to be constant
  637.  * size. To fix this, need delete the old key and add both left and
  638.  * right for the two new pages.  The insertion of left may force a
  639.  * split if the new left key is bigger than the old key.
  640.  */
  642. if (IndexTupleSize(old) != IndexTupleSize(ltup))
  643. elog(ERROR, "Variable-length rtree keys are not supported.");
  645. /* install pointer to left child */
  646. memmove(old, ltup, IndexTupleSize(ltup));
  648. if (nospace(p, rtup))
  649. {
  650. newdatum = (((char *) ltup) + sizeof(IndexTupleData));
  651. rttighten(r, stk->rts_parent, newdatum,
  652.    (IndexTupleSize(ltup) - sizeof(IndexTupleData)), rtstate);
  653. res = dosplit(r, b, stk->rts_parent, rtup, rtstate);
  654. WriteBuffer(b); /* don't forget to release buffer!  -
  655.  * 01/31/94 */
  656. pfree(res);
  657. }
  658. else
  659. {
  660. PageAddItem(p, (Item) rtup, IndexTupleSize(rtup),
  661. PageGetMaxOffsetNumber(p), LP_USED);
  662. WriteBuffer(b);
  663. ldatum = (((char *) ltup) + sizeof(IndexTupleData));
  664. rdatum = (((char *) rtup) + sizeof(IndexTupleData));
  665. newdatum = (char *) (*fmgr_faddr(&rtstate->unionFn)) (ldatum, rdatum);
  667. rttighten(r, stk->rts_parent, newdatum,
  668.    (IndexTupleSize(rtup) - sizeof(IndexTupleData)), rtstate);
  670. pfree(newdatum);
  671. }
  672. }
  674. static void
  675. rtnewroot(Relation r, IndexTuple lt, IndexTuple rt)
  676. {
  677. Buffer b;
  678. Page p;
  680. b = ReadBuffer(r, P_ROOT);
  681. RTInitBuffer(b, 0);
  682. p = BufferGetPage(b);
  683. PageAddItem(p, (Item) lt, IndexTupleSize(lt),
  684. FirstOffsetNumber, LP_USED);
  685. PageAddItem(p, (Item) rt, IndexTupleSize(rt),
  686. OffsetNumberNext(FirstOffsetNumber), LP_USED);
  687. WriteBuffer(b);
  688. }
  690. static void
  691. picksplit(Relation r,
  692.   Page page,
  693.   SPLITVEC *v,
  694.   IndexTuple itup,
  695.   RTSTATE *rtstate)
  696. {
  697. OffsetNumber maxoff;
  698. OffsetNumber i,
  699. j;
  700. IndexTuple item_1,
  701. item_2;
  702. char    *datum_alpha,
  703.    *datum_beta;
  704. char    *datum_l,
  705.    *datum_r;
  706. char    *union_d,
  707.    *union_dl,
  708.    *union_dr;
  709. char    *inter_d;
  710. bool firsttime;
  711. float size_alpha,
  712. size_beta,
  713. size_union,
  714. size_inter;
  715. float size_waste,
  716. waste;
  717. float size_l,
  718. size_r;
  719. int nbytes;
  720. OffsetNumber seed_1 = 0,
  721. seed_2 = 0;
  722. OffsetNumber *left,
  723.    *right;
  725. maxoff = PageGetMaxOffsetNumber(page);
  727. nbytes = (maxoff + 2) * sizeof(OffsetNumber);
  728. v->spl_left = (OffsetNumber *) palloc(nbytes);
  729. v->spl_right = (OffsetNumber *) palloc(nbytes);
  731. firsttime = true;
  732. waste = 0.0;
  734. for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i))
  735. {
  736. item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, i));
  737. datum_alpha = ((char *) item_1) + sizeof(IndexTupleData);
  738. for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j))
  739. {
  740. item_2 = (IndexTuple) PageGetItem(page, PageGetItemId(page, j));
  741. datum_beta = ((char *) item_2) + sizeof(IndexTupleData);
  743. /* compute the wasted space by unioning these guys */
  744. union_d = (char *) (*fmgr_faddr(&rtstate->unionFn)) (datum_alpha, datum_beta);
  745. (*fmgr_faddr(&rtstate->sizeFn)) (union_d, &size_union);
  746. inter_d = (char *) (*fmgr_faddr(&rtstate->interFn)) (datum_alpha, datum_beta);
  747. (*fmgr_faddr(&rtstate->sizeFn)) (inter_d, &size_inter);
  748. size_waste = size_union - size_inter;
  750. pfree(union_d);
  752. if (inter_d != (char *) NULL)
  753. pfree(inter_d);
  755. /*
  756.  * are these a more promising split that what we've already
  757.  * seen?
  758.  */
  760. if (size_waste > waste || firsttime)
  761. {
  762. waste = size_waste;
  763. seed_1 = i;
  764. seed_2 = j;
  765. firsttime = false;
  766. }
  767. }
  768. }
  770. left = v->spl_left;
  771. v->spl_nleft = 0;
  772. right = v->spl_right;
  773. v->spl_nright = 0;
  775. item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, seed_1));
  776. datum_alpha = ((char *) item_1) + sizeof(IndexTupleData);
  777. datum_l = (char *) (*fmgr_faddr(&rtstate->unionFn)) (datum_alpha, datum_alpha);
  778. (*fmgr_faddr(&rtstate->sizeFn)) (datum_l, &size_l);
  779. item_2 = (IndexTuple) PageGetItem(page, PageGetItemId(page, seed_2));
  780. datum_beta = ((char *) item_2) + sizeof(IndexTupleData);
  781. datum_r = (char *) (*fmgr_faddr(&rtstate->unionFn)) (datum_beta, datum_beta);
  782. (*fmgr_faddr(&rtstate->sizeFn)) (datum_r, &size_r);
  784. /*
  785.  * Now split up the regions between the two seeds. An important
  786.  * property of this split algorithm is that the split vector v has the
  787.  * indices of items to be split in order in its left and right
  788.  * vectors.  We exploit this property by doing a merge in the code
  789.  * that actually splits the page.
  790.  *
  791.  * For efficiency, we also place the new index tuple in this loop. This
  792.  * is handled at the very end, when we have placed all the existing
  793.  * tuples and i == maxoff + 1.
  794.  */
  796. maxoff = OffsetNumberNext(maxoff);
  797. for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
  798. {
  800. /*
  801.  * If we've already decided where to place this item, just put it
  802.  * on the right list.  Otherwise, we need to figure out which page
  803.  * needs the least enlargement in order to store the item.
  804.  */
  806. if (i == seed_1)
  807. {
  808. *left++ = i;
  809. v->spl_nleft++;
  810. continue;
  811. }
  812. else if (i == seed_2)
  813. {
  814. *right++ = i;
  815. v->spl_nright++;
  816. continue;
  817. }
  819. /* okay, which page needs least enlargement? */
  820. if (i == maxoff)
  821. item_1 = itup;
  822. else
  823. item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, i));
  825. datum_alpha = ((char *) item_1) + sizeof(IndexTupleData);
  826. union_dl = (char *) (*fmgr_faddr(&rtstate->unionFn)) (datum_l, datum_alpha);
  827. union_dr = (char *) (*fmgr_faddr(&rtstate->unionFn)) (datum_r, datum_alpha);
  828. (*fmgr_faddr(&rtstate->sizeFn)) (union_dl, &size_alpha);
  829. (*fmgr_faddr(&rtstate->sizeFn)) (union_dr, &size_beta);
  831. /* pick which page to add it to */
  832. if (size_alpha - size_l < size_beta - size_r)
  833. {
  834. pfree(datum_l);
  835. pfree(union_dr);
  836. datum_l = union_dl;
  837. size_l = size_alpha;
  838. *left++ = i;
  839. v->spl_nleft++;
  840. }
  841. else
  842. {
  843. pfree(datum_r);
  844. pfree(union_dl);
  845. datum_r = union_dr;
  846. size_r = size_alpha;
  847. *right++ = i;
  848. v->spl_nright++;
  849. }
  850. }
  851. *left = *right = FirstOffsetNumber; /* sentinel value, see dosplit() */
  853. v->spl_ldatum = datum_l;
  854. v->spl_rdatum = datum_r;
  855. }
  857. static void
  858. RTInitBuffer(Buffer b, uint32 f)
  859. {
  860. RTreePageOpaque opaque;
  861. Page page;
  862. Size pageSize;
  864. pageSize = BufferGetPageSize(b);
  866. page = BufferGetPage(b);
  867. MemSet(page, 0, (int) pageSize);
  868. PageInit(page, pageSize, sizeof(RTreePageOpaqueData));
  870. opaque = (RTreePageOpaque) PageGetSpecialPointer(page);
  871. opaque->flags = f;
  872. }
  874. static OffsetNumber
  875. choose(Relation r, Page p, IndexTuple it, RTSTATE *rtstate)
  876. {
  877. OffsetNumber maxoff;
  878. OffsetNumber i;
  879. char    *ud,
  880.    *id;
  881. char    *datum;
  882. float usize,
  883. dsize;
  884. OffsetNumber which;
  885. float which_grow;
  887. id = ((char *) it) + sizeof(IndexTupleData);
  888. maxoff = PageGetMaxOffsetNumber(p);
  889. which_grow = -1.0;
  890. which = -1;
  892. for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
  893. {
  894. datum = (char *) PageGetItem(p, PageGetItemId(p, i));
  895. datum += sizeof(IndexTupleData);
  896. (*fmgr_faddr(&rtstate->sizeFn)) (datum, &dsize);
  897. ud = (char *) (*fmgr_faddr(&rtstate->unionFn)) (datum, id);
  898. (*fmgr_faddr(&rtstate->sizeFn)) (ud, &usize);
  899. pfree(ud);
  900. if (which_grow < 0 || usize - dsize < which_grow)
  901. {
  902. which = i;
  903. which_grow = usize - dsize;
  904. if (which_grow == 0)
  905. break;
  906. }
  907. }
  909. return which;
  910. }
  912. static int
  913. nospace(Page p, IndexTuple it)
  914. {
  915. return PageGetFreeSpace(p) < IndexTupleSize(it);
  916. }
  918. void
  919. freestack(RTSTACK *s)
  920. {
  921. RTSTACK    *p;
  923. while (s != (RTSTACK *) NULL)
  924. {
  925. p = s->rts_parent;
  926. pfree(s);
  927. s = p;
  928. }
  929. }
  931. char *
  932. rtdelete(Relation r, ItemPointer tid)
  933. {
  934. BlockNumber blkno;
  935. OffsetNumber offnum;
  936. Buffer buf;
  937. Page page;
  939. /*
  940.  * Notes in ExecUtils:ExecOpenIndices() Also note that only vacuum
  941.  * deletes index tuples now...
  942.  *
  943.  * RelationSetLockForWrite(r);
  944.  */
  946. blkno = ItemPointerGetBlockNumber(tid);
  947. offnum = ItemPointerGetOffsetNumber(tid);
  949. /* adjust any scans that will be affected by this deletion */
  950. rtadjscans(r, RTOP_DEL, blkno, offnum);
  952. /* delete the index tuple */
  953. buf = ReadBuffer(r, blkno);
  954. page = BufferGetPage(buf);
  956. PageIndexTupleDelete(page, offnum);
  958. WriteBuffer(buf);
  960. return (char *) NULL;
  961. }
  963. static void
  964. initRtstate(RTSTATE *rtstate, Relation index)
  965. {
  966. RegProcedure union_proc,
  967. size_proc,
  968. inter_proc;
  970. union_proc = index_getprocid(index, 1, RT_UNION_PROC);
  971. size_proc = index_getprocid(index, 1, RT_SIZE_PROC);
  972. inter_proc = index_getprocid(index, 1, RT_INTER_PROC);
  973. fmgr_info(union_proc, &rtstate->unionFn);
  974. fmgr_info(size_proc, &rtstate->sizeFn);
  975. fmgr_info(inter_proc, &rtstate->interFn);
  976. return;
  977. }
  979. #ifdef RTDEBUG
  981. void
  982. _rtdump(Relation r)
  983. {
  984. Buffer buf;
  985. Page page;
  986. OffsetNumber offnum,
  987. maxoff;
  988. BlockNumber blkno;
  989. BlockNumber nblocks;
  990. RTreePageOpaque po;
  991. IndexTuple itup;
  992. BlockNumber itblkno;
  993. OffsetNumber itoffno;
  994. char    *datum;
  995. char    *itkey;
  997. nblocks = RelationGetNumberOfBlocks(r);
  998. for (blkno = 0; blkno < nblocks; blkno++)
  999. {
  1000. buf = ReadBuffer(r, blkno);
  1001. page = BufferGetPage(buf);
  1002. po = (RTreePageOpaque) PageGetSpecialPointer(page);
  1003. maxoff = PageGetMaxOffsetNumber(page);
  1004. printf("Page %d maxoff %d <%s>n", blkno, maxoff,
  1005.    (po->flags & F_LEAF ? "LEAF" : "INTERNAL"));
  1007. if (PageIsEmpty(page))
  1008. {
  1009. ReleaseBuffer(buf);
  1010. continue;
  1011. }
  1013. for (offnum = FirstOffsetNumber;
  1014.  offnum <= maxoff;
  1015.  offnum = OffsetNumberNext(offnum))
  1016. {
  1017. itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
  1018. itblkno = ItemPointerGetBlockNumber(&(itup->t_tid));
  1019. itoffno = ItemPointerGetOffsetNumber(&(itup->t_tid));
  1020. datum = ((char *) itup);
  1021. datum += sizeof(IndexTupleData);
  1022. itkey = (char *) box_out((BOX *) datum);
  1023. printf("t[%d] size %d heap <%d,%d> key:%sn",
  1024.    offnum, IndexTupleSize(itup), itblkno, itoffno, itkey);
  1025. pfree(itkey);
  1026. }
  1028. ReleaseBuffer(buf);
  1029. }
  1030. }
  1032. #endif  /* defined RTDEBUG */