diff options
Diffstat (limited to 'src/backend/access/rtree')
| -rw-r--r-- | src/backend/access/rtree/rtget.c | 544 | ||||
| -rw-r--r-- | src/backend/access/rtree/rtproc.c | 209 | ||||
| -rw-r--r-- | src/backend/access/rtree/rtree.c | 1753 | ||||
| -rw-r--r-- | src/backend/access/rtree/rtscan.c | 626 | ||||
| -rw-r--r-- | src/backend/access/rtree/rtstrat.c | 346 |
5 files changed, 1828 insertions, 1650 deletions
diff --git a/src/backend/access/rtree/rtget.c b/src/backend/access/rtree/rtget.c index 09f10f1aa98..eaf16c1ae9d 100644 --- a/src/backend/access/rtree/rtget.c +++ b/src/backend/access/rtree/rtget.c @@ -1,19 +1,19 @@ /*------------------------------------------------------------------------- * * rtget.c-- - * fetch tuples from an rtree scan. + * fetch tuples from an rtree scan. * * Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/access/rtree/Attic/rtget.c,v 1.7 1996/11/21 06:13:43 vadim Exp $ + * $Header: /cvsroot/pgsql/src/backend/access/rtree/Attic/rtget.c,v 1.8 1997/09/07 04:39:11 momjian Exp $ * *------------------------------------------------------------------------- */ #include <postgres.h> - + #include <storage/bufmgr.h> #include <access/sdir.h> #include <access/relscan.h> @@ -21,14 +21,15 @@ #include <access/rtree.h> #include <storage/bufpage.h> #ifndef HAVE_MEMMOVE -# include <regex/utils.h> +#include <regex/utils.h> #else -# include <string.h> +#include <string.h> #endif -static OffsetNumber findnext(IndexScanDesc s, Page p, OffsetNumber n, - ScanDirection dir); +static OffsetNumber +findnext(IndexScanDesc s, Page p, OffsetNumber n, + ScanDirection dir); static RetrieveIndexResult rtscancache(IndexScanDesc s, ScanDirection dir); static RetrieveIndexResult rtfirst(IndexScanDesc s, ScanDirection dir); static RetrieveIndexResult rtnext(IndexScanDesc s, ScanDirection dir); @@ -38,278 +39,315 @@ static ItemPointer rtheapptr(Relation r, ItemPointer itemp); RetrieveIndexResult rtgettuple(IndexScanDesc s, ScanDirection dir) { - RetrieveIndexResult res; - - /* if we have it cached in the scan desc, just return the value */ - if ((res = rtscancache(s, dir)) != (RetrieveIndexResult) NULL) + RetrieveIndexResult res; + + /* if we have it cached in the scan desc, just return the value */ + if ((res = rtscancache(s, dir)) != (RetrieveIndexResult) NULL) + return (res); + + /* not cached, so we'll have to do some work */ + if (ItemPointerIsValid(&(s->currentItemData))) + { + res = rtnext(s, dir); + } + else + { + res = rtfirst(s, dir); + } return (res); - - /* not cached, so we'll have to do some work */ - if (ItemPointerIsValid(&(s->currentItemData))) { - res = rtnext(s, dir); - } else { - res = rtfirst(s, dir); - } - return (res); } -static RetrieveIndexResult +static RetrieveIndexResult rtfirst(IndexScanDesc s, ScanDirection dir) { - Buffer b; - Page p; - OffsetNumber n; - OffsetNumber maxoff; - RetrieveIndexResult res; - RTreePageOpaque po; - RTreeScanOpaque so; - RTSTACK *stk; - BlockNumber blk; - IndexTuple it; - - b = ReadBuffer(s->relation, P_ROOT); - p = BufferGetPage(b); - po = (RTreePageOpaque) PageGetSpecialPointer(p); - so = (RTreeScanOpaque) s->opaque; - - for (;;) { - maxoff = PageGetMaxOffsetNumber(p); - if (ScanDirectionIsBackward(dir)) - n = findnext(s, p, maxoff, dir); - else - n = findnext(s, p, FirstOffsetNumber, dir); - - while (n < FirstOffsetNumber || n > maxoff) { - - ReleaseBuffer(b); - if (so->s_stack == (RTSTACK *) NULL) - return ((RetrieveIndexResult) NULL); - - stk = so->s_stack; - b = ReadBuffer(s->relation, stk->rts_blk); - p = BufferGetPage(b); - po = (RTreePageOpaque) PageGetSpecialPointer(p); - maxoff = PageGetMaxOffsetNumber(p); - - if (ScanDirectionIsBackward(dir)) { - n = OffsetNumberPrev(stk->rts_child); - } else { - n = OffsetNumberNext(stk->rts_child); - } - so->s_stack = stk->rts_parent; - pfree(stk); - - n = findnext(s, p, n, dir); - } - if (po->flags & F_LEAF) { - ItemPointerSet(&(s->currentItemData), BufferGetBlockNumber(b), n); - - it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); - - res = FormRetrieveIndexResult(&(s->currentItemData), &(it->t_tid)); - - ReleaseBuffer(b); - return (res); - } else { - stk = (RTSTACK *) palloc(sizeof(RTSTACK)); - stk->rts_child = n; - stk->rts_blk = BufferGetBlockNumber(b); - stk->rts_parent = so->s_stack; - so->s_stack = stk; - - it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); - blk = ItemPointerGetBlockNumber(&(it->t_tid)); - - ReleaseBuffer(b); - b = ReadBuffer(s->relation, blk); - p = BufferGetPage(b); - po = (RTreePageOpaque) PageGetSpecialPointer(p); + Buffer b; + Page p; + OffsetNumber n; + OffsetNumber maxoff; + RetrieveIndexResult res; + RTreePageOpaque po; + RTreeScanOpaque so; + RTSTACK *stk; + BlockNumber blk; + IndexTuple it; + + b = ReadBuffer(s->relation, P_ROOT); + p = BufferGetPage(b); + po = (RTreePageOpaque) PageGetSpecialPointer(p); + so = (RTreeScanOpaque) s->opaque; + + for (;;) + { + maxoff = PageGetMaxOffsetNumber(p); + if (ScanDirectionIsBackward(dir)) + n = findnext(s, p, maxoff, dir); + else + n = findnext(s, p, FirstOffsetNumber, dir); + + while (n < FirstOffsetNumber || n > maxoff) + { + + ReleaseBuffer(b); + if (so->s_stack == (RTSTACK *) NULL) + return ((RetrieveIndexResult) NULL); + + stk = so->s_stack; + b = ReadBuffer(s->relation, stk->rts_blk); + p = BufferGetPage(b); + po = (RTreePageOpaque) PageGetSpecialPointer(p); + maxoff = PageGetMaxOffsetNumber(p); + + if (ScanDirectionIsBackward(dir)) + { + n = OffsetNumberPrev(stk->rts_child); + } + else + { + n = OffsetNumberNext(stk->rts_child); + } + so->s_stack = stk->rts_parent; + pfree(stk); + + n = findnext(s, p, n, dir); + } + if (po->flags & F_LEAF) + { + ItemPointerSet(&(s->currentItemData), BufferGetBlockNumber(b), n); + + it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); + + res = FormRetrieveIndexResult(&(s->currentItemData), &(it->t_tid)); + + ReleaseBuffer(b); + return (res); + } + else + { + stk = (RTSTACK *) palloc(sizeof(RTSTACK)); + stk->rts_child = n; + stk->rts_blk = BufferGetBlockNumber(b); + stk->rts_parent = so->s_stack; + so->s_stack = stk; + + it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); + blk = ItemPointerGetBlockNumber(&(it->t_tid)); + + ReleaseBuffer(b); + b = ReadBuffer(s->relation, blk); + p = BufferGetPage(b); + po = (RTreePageOpaque) PageGetSpecialPointer(p); + } } - } } -static RetrieveIndexResult +static RetrieveIndexResult rtnext(IndexScanDesc s, ScanDirection dir) { - Buffer b; - Page p; - OffsetNumber n; - OffsetNumber maxoff; - RetrieveIndexResult res; - RTreePageOpaque po; - RTreeScanOpaque so; - RTSTACK *stk; - BlockNumber blk; - IndexTuple it; - - blk = ItemPointerGetBlockNumber(&(s->currentItemData)); - n = ItemPointerGetOffsetNumber(&(s->currentItemData)); - - if (ScanDirectionIsForward(dir)) { - n = OffsetNumberNext(n); - } else { - n = OffsetNumberPrev(n); - } - - b = ReadBuffer(s->relation, blk); - p = BufferGetPage(b); - po = (RTreePageOpaque) PageGetSpecialPointer(p); - so = (RTreeScanOpaque) s->opaque; - - for (;;) { - maxoff = PageGetMaxOffsetNumber(p); - n = findnext(s, p, n, dir); - - while (n < FirstOffsetNumber || n > maxoff) { - - ReleaseBuffer(b); - if (so->s_stack == (RTSTACK *) NULL) - return ((RetrieveIndexResult) NULL); - - stk = so->s_stack; - b = ReadBuffer(s->relation, stk->rts_blk); - p = BufferGetPage(b); - maxoff = PageGetMaxOffsetNumber(p); - po = (RTreePageOpaque) PageGetSpecialPointer(p); - - if (ScanDirectionIsBackward(dir)) { - n = OffsetNumberPrev(stk->rts_child); - } else { - n = OffsetNumberNext(stk->rts_child); - } - so->s_stack = stk->rts_parent; - pfree(stk); - - n = findnext(s, p, n, dir); + Buffer b; + Page p; + OffsetNumber n; + OffsetNumber maxoff; + RetrieveIndexResult res; + RTreePageOpaque po; + RTreeScanOpaque so; + RTSTACK *stk; + BlockNumber blk; + IndexTuple it; + + blk = ItemPointerGetBlockNumber(&(s->currentItemData)); + n = ItemPointerGetOffsetNumber(&(s->currentItemData)); + + if (ScanDirectionIsForward(dir)) + { + n = OffsetNumberNext(n); + } + else + { + n = OffsetNumberPrev(n); } - if (po->flags & F_LEAF) { - ItemPointerSet(&(s->currentItemData), BufferGetBlockNumber(b), n); - - it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); - - res = FormRetrieveIndexResult(&(s->currentItemData), &(it->t_tid)); - - ReleaseBuffer(b); - return (res); - } else { - stk = (RTSTACK *) palloc(sizeof(RTSTACK)); - stk->rts_child = n; - stk->rts_blk = BufferGetBlockNumber(b); - stk->rts_parent = so->s_stack; - so->s_stack = stk; - - it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); - blk = ItemPointerGetBlockNumber(&(it->t_tid)); - - ReleaseBuffer(b); - b = ReadBuffer(s->relation, blk); - p = BufferGetPage(b); - po = (RTreePageOpaque) PageGetSpecialPointer(p); - - if (ScanDirectionIsBackward(dir)) { - n = PageGetMaxOffsetNumber(p); - } else { - n = FirstOffsetNumber; - } + + b = ReadBuffer(s->relation, blk); + p = BufferGetPage(b); + po = (RTreePageOpaque) PageGetSpecialPointer(p); + so = (RTreeScanOpaque) s->opaque; + + for (;;) + { + maxoff = PageGetMaxOffsetNumber(p); + n = findnext(s, p, n, dir); + + while (n < FirstOffsetNumber || n > maxoff) + { + + ReleaseBuffer(b); + if (so->s_stack == (RTSTACK *) NULL) + return ((RetrieveIndexResult) NULL); + + stk = so->s_stack; + b = ReadBuffer(s->relation, stk->rts_blk); + p = BufferGetPage(b); + maxoff = PageGetMaxOffsetNumber(p); + po = (RTreePageOpaque) PageGetSpecialPointer(p); + + if (ScanDirectionIsBackward(dir)) + { + n = OffsetNumberPrev(stk->rts_child); + } + else + { + n = OffsetNumberNext(stk->rts_child); + } + so->s_stack = stk->rts_parent; + pfree(stk); + + n = findnext(s, p, n, dir); + } + if (po->flags & F_LEAF) + { + ItemPointerSet(&(s->currentItemData), BufferGetBlockNumber(b), n); + + it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); + + res = FormRetrieveIndexResult(&(s->currentItemData), &(it->t_tid)); + + ReleaseBuffer(b); + return (res); + } + else + { + stk = (RTSTACK *) palloc(sizeof(RTSTACK)); + stk->rts_child = n; + stk->rts_blk = BufferGetBlockNumber(b); + stk->rts_parent = so->s_stack; + so->s_stack = stk; + + it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); + blk = ItemPointerGetBlockNumber(&(it->t_tid)); + + ReleaseBuffer(b); + b = ReadBuffer(s->relation, blk); + p = BufferGetPage(b); + po = (RTreePageOpaque) PageGetSpecialPointer(p); + + if (ScanDirectionIsBackward(dir)) + { + n = PageGetMaxOffsetNumber(p); + } + else + { + n = FirstOffsetNumber; + } + } } - } } -static OffsetNumber +static OffsetNumber findnext(IndexScanDesc s, Page p, OffsetNumber n, ScanDirection dir) { - OffsetNumber maxoff; - IndexTuple it; - RTreePageOpaque po; - RTreeScanOpaque so; - - maxoff = PageGetMaxOffsetNumber(p); - po = (RTreePageOpaque) PageGetSpecialPointer(p); - so = (RTreeScanOpaque) s->opaque; - - /* - * If we modified the index during the scan, we may have a pointer to - * a ghost tuple, before the scan. If this is the case, back up one. - */ - - if (so->s_flags & RTS_CURBEFORE) { - so->s_flags &= ~RTS_CURBEFORE; - n = OffsetNumberPrev(n); - } - - while (n >= FirstOffsetNumber && n <= maxoff) { - it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); - if (po->flags & F_LEAF) { - if (index_keytest(it, - RelationGetTupleDescriptor(s->relation), - s->numberOfKeys, s->keyData)) - break; - } else { - if (index_keytest(it, - RelationGetTupleDescriptor(s->relation), - so->s_internalNKey, so->s_internalKey)) - break; + OffsetNumber maxoff; + IndexTuple it; + RTreePageOpaque po; + RTreeScanOpaque so; + + maxoff = PageGetMaxOffsetNumber(p); + po = (RTreePageOpaque) PageGetSpecialPointer(p); + so = (RTreeScanOpaque) s->opaque; + + /* + * If we modified the index during the scan, we may have a pointer to + * a ghost tuple, before the scan. If this is the case, back up one. + */ + + if (so->s_flags & RTS_CURBEFORE) + { + so->s_flags &= ~RTS_CURBEFORE; + n = OffsetNumberPrev(n); } - - if (ScanDirectionIsBackward(dir)) { - n = OffsetNumberPrev(n); - } else { - n = OffsetNumberNext(n); + + while (n >= FirstOffsetNumber && n <= maxoff) + { + it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); + if (po->flags & F_LEAF) + { + if (index_keytest(it, + RelationGetTupleDescriptor(s->relation), + s->numberOfKeys, s->keyData)) + break; + } + else + { + if (index_keytest(it, + RelationGetTupleDescriptor(s->relation), + so->s_internalNKey, so->s_internalKey)) + break; + } + + if (ScanDirectionIsBackward(dir)) + { + n = OffsetNumberPrev(n); + } + else + { + n = OffsetNumberNext(n); + } } - } - - return (n); + + return (n); } -static RetrieveIndexResult +static RetrieveIndexResult rtscancache(IndexScanDesc s, ScanDirection dir) { - RetrieveIndexResult res; - ItemPointer ip; - - if (!(ScanDirectionIsNoMovement(dir) - && ItemPointerIsValid(&(s->currentItemData)))) { - - return ((RetrieveIndexResult) NULL); - } - - ip = rtheapptr(s->relation, &(s->currentItemData)); - - if (ItemPointerIsValid(ip)) - res = FormRetrieveIndexResult(&(s->currentItemData), ip); - else - res = (RetrieveIndexResult) NULL; - - pfree (ip); - - return (res); + RetrieveIndexResult res; + ItemPointer ip; + + if (!(ScanDirectionIsNoMovement(dir) + && ItemPointerIsValid(&(s->currentItemData)))) + { + + return ((RetrieveIndexResult) NULL); + } + + ip = rtheapptr(s->relation, &(s->currentItemData)); + + if (ItemPointerIsValid(ip)) + res = FormRetrieveIndexResult(&(s->currentItemData), ip); + else + res = (RetrieveIndexResult) NULL; + + pfree(ip); + + return (res); } /* - * rtheapptr returns the item pointer to the tuple in the heap relation - * for which itemp is the index relation item pointer. + * rtheapptr returns the item pointer to the tuple in the heap relation + * for which itemp is the index relation item pointer. */ -static ItemPointer +static ItemPointer rtheapptr(Relation r, ItemPointer itemp) { - Buffer b; - Page p; - IndexTuple it; - ItemPointer ip; - OffsetNumber n; - - ip = (ItemPointer) palloc(sizeof(ItemPointerData)); - if (ItemPointerIsValid(itemp)) { - b = ReadBuffer(r, ItemPointerGetBlockNumber(itemp)); - p = BufferGetPage(b); - n = ItemPointerGetOffsetNumber(itemp); - it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); - memmove((char *) ip, (char *) &(it->t_tid), - sizeof(ItemPointerData)); - ReleaseBuffer(b); - } else { - ItemPointerSetInvalid(ip); - } - - return (ip); + Buffer b; + Page p; + IndexTuple it; + ItemPointer ip; + OffsetNumber n; + + ip = (ItemPointer) palloc(sizeof(ItemPointerData)); + if (ItemPointerIsValid(itemp)) + { + b = ReadBuffer(r, ItemPointerGetBlockNumber(itemp)); + p = BufferGetPage(b); + n = ItemPointerGetOffsetNumber(itemp); + it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); + memmove((char *) ip, (char *) &(it->t_tid), + sizeof(ItemPointerData)); + ReleaseBuffer(b); + } + else + { + ItemPointerSetInvalid(ip); + } + + return (ip); } diff --git a/src/backend/access/rtree/rtproc.c b/src/backend/access/rtree/rtproc.c index ac7a3abfecf..4b7a9f2a266 100644 --- a/src/backend/access/rtree/rtproc.c +++ b/src/backend/access/rtree/rtproc.c @@ -1,13 +1,13 @@ /*------------------------------------------------------------------------- * * rtproc.c-- - * pg_amproc entries for rtrees. + * pg_amproc entries for rtrees. * * Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/access/rtree/Attic/rtproc.c,v 1.7 1997/04/22 17:31:23 scrappy Exp $ + * $Header: /cvsroot/pgsql/src/backend/access/rtree/Attic/rtproc.c,v 1.8 1997/09/07 04:39:16 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -17,136 +17,139 @@ #include <utils/builtins.h> #include <utils/geo_decls.h> #ifndef HAVE_MEMMOVE -# include <regex/utils.h> +#include <regex/utils.h> #else -# include <string.h> +#include <string.h> #endif BOX -*rt_box_union(BOX *a, BOX *b) +* rt_box_union(BOX * a, BOX * b) { - BOX *n; - - if ((n = (BOX *) palloc(sizeof (*n))) == (BOX *) NULL) - elog(WARN, "Cannot allocate box for union"); - - n->high.x = Max(a->high.x, b->high.x); - n->high.y = Max(a->high.y, b->high.y); - n->low.x = Min(a->low.x, b->low.x); - n->low.y = Min(a->low.y, b->low.y); - - return (n); + BOX *n; + + if ((n = (BOX *) palloc(sizeof(*n))) == (BOX *) NULL) + elog(WARN, "Cannot allocate box for union"); + + n->high.x = Max(a->high.x, b->high.x); + n->high.y = Max(a->high.y, b->high.y); + n->low.x = Min(a->low.x, b->low.x); + n->low.y = Min(a->low.y, b->low.y); + + return (n); } -BOX * -rt_box_inter(BOX *a, BOX *b) +BOX * +rt_box_inter(BOX * a, BOX * b) { - BOX *n; - - if ((n = (BOX *) palloc(sizeof (*n))) == (BOX *) NULL) - elog(WARN, "Cannot allocate box for union"); - - n->high.x = Min(a->high.x, b->high.x); - n->high.y = Min(a->high.y, b->high.y); - n->low.x = Max(a->low.x, b->low.x); - n->low.y = Max(a->low.y, b->low.y); - - if (n->high.x < n->low.x || n->high.y < n->low.y) { - pfree(n); - return ((BOX *) NULL); - } - - return (n); + BOX *n; + + if ((n = (BOX *) palloc(sizeof(*n))) == (BOX *) NULL) + elog(WARN, "Cannot allocate box for union"); + + n->high.x = Min(a->high.x, b->high.x); + n->high.y = Min(a->high.y, b->high.y); + n->low.x = Max(a->low.x, b->low.x); + n->low.y = Max(a->low.y, b->low.y); + + if (n->high.x < n->low.x || n->high.y < n->low.y) + { + pfree(n); + return ((BOX *) NULL); + } + + return (n); } void -rt_box_size(BOX *a, float *size) +rt_box_size(BOX * a, float *size) { - if (a == (BOX *) NULL || a->high.x <= a->low.x || a->high.y <= a->low.y) - *size = 0.0; - else - *size = (float) ((a->high.x - a->low.x) * (a->high.y - a->low.y)); - - return; + if (a == (BOX *) NULL || a->high.x <= a->low.x || a->high.y <= a->low.y) + *size = 0.0; + else + *size = (float) ((a->high.x - a->low.x) * (a->high.y - a->low.y)); + + return; } /* - * rt_bigbox_size() -- Compute a size for big boxes. + * rt_bigbox_size() -- Compute a size for big boxes. * - * In an earlier release of the system, this routine did something - * different from rt_box_size. We now use floats, rather than ints, - * as the return type for the size routine, so we no longer need to - * have a special return type for big boxes. + * In an earlier release of the system, this routine did something + * different from rt_box_size. We now use floats, rather than ints, + * as the return type for the size routine, so we no longer need to + * have a special return type for big boxes. */ void -rt_bigbox_size(BOX *a, float *size) +rt_bigbox_size(BOX * a, float *size) { - rt_box_size(a, size); + rt_box_size(a, size); } -POLYGON * -rt_poly_union(POLYGON *a, POLYGON *b) +POLYGON * +rt_poly_union(POLYGON * a, POLYGON * b) { - POLYGON *p; - - p = (POLYGON *)PALLOCTYPE(POLYGON); - - if (!PointerIsValid(p)) - elog(WARN, "Cannot allocate polygon for union"); - - memset((char *) p, 0, sizeof(POLYGON)); /* zero any holes */ - p->size = sizeof(POLYGON); - p->npts = 0; - p->boundbox.high.x = Max(a->boundbox.high.x, b->boundbox.high.x); - p->boundbox.high.y = Max(a->boundbox.high.y, b->boundbox.high.y); - p->boundbox.low.x = Min(a->boundbox.low.x, b->boundbox.low.x); - p->boundbox.low.y = Min(a->boundbox.low.y, b->boundbox.low.y); - return p; + POLYGON *p; + + p = (POLYGON *) PALLOCTYPE(POLYGON); + + if (!PointerIsValid(p)) + elog(WARN, "Cannot allocate polygon for union"); + + memset((char *) p, 0, sizeof(POLYGON)); /* zero any holes */ + p->size = sizeof(POLYGON); + p->npts = 0; + p->boundbox.high.x = Max(a->boundbox.high.x, b->boundbox.high.x); + p->boundbox.high.y = Max(a->boundbox.high.y, b->boundbox.high.y); + p->boundbox.low.x = Min(a->boundbox.low.x, b->boundbox.low.x); + p->boundbox.low.y = Min(a->boundbox.low.y, b->boundbox.low.y); + return p; } void -rt_poly_size(POLYGON *a, float *size) +rt_poly_size(POLYGON * a, float *size) { - double xdim, ydim; - - size = (float *) palloc(sizeof(float)); - if (a == (POLYGON *) NULL || - a->boundbox.high.x <= a->boundbox.low.x || - a->boundbox.high.y <= a->boundbox.low.y) - *size = 0.0; - else { - xdim = (a->boundbox.high.x - a->boundbox.low.x); - ydim = (a->boundbox.high.y - a->boundbox.low.y); - - *size = (float) (xdim * ydim); - } - - return; + double xdim, + ydim; + + size = (float *) palloc(sizeof(float)); + if (a == (POLYGON *) NULL || + a->boundbox.high.x <= a->boundbox.low.x || + a->boundbox.high.y <= a->boundbox.low.y) + *size = 0.0; + else + { + xdim = (a->boundbox.high.x - a->boundbox.low.x); + ydim = (a->boundbox.high.y - a->boundbox.low.y); + + *size = (float) (xdim * ydim); + } + + return; } -POLYGON * -rt_poly_inter(POLYGON *a, POLYGON *b) +POLYGON * +rt_poly_inter(POLYGON * a, POLYGON * b) { - POLYGON *p; - - p = (POLYGON *) PALLOCTYPE(POLYGON); - - if (!PointerIsValid(p)) - elog(WARN, "Cannot allocate polygon for intersection"); - - memset((char *) p, 0, sizeof(POLYGON)); /* zero any holes */ - p->size = sizeof(POLYGON); - p->npts = 0; - p->boundbox.high.x = Min(a->boundbox.high.x, b->boundbox.high.x); - p->boundbox.high.y = Min(a->boundbox.high.y, b->boundbox.high.y); - p->boundbox.low.x = Max(a->boundbox.low.x, b->boundbox.low.x); - p->boundbox.low.y = Max(a->boundbox.low.y, b->boundbox.low.y); - - if (p->boundbox.high.x < p->boundbox.low.x || p->boundbox.high.y < p->boundbox.low.y) + POLYGON *p; + + p = (POLYGON *) PALLOCTYPE(POLYGON); + + if (!PointerIsValid(p)) + elog(WARN, "Cannot allocate polygon for intersection"); + + memset((char *) p, 0, sizeof(POLYGON)); /* zero any holes */ + p->size = sizeof(POLYGON); + p->npts = 0; + p->boundbox.high.x = Min(a->boundbox.high.x, b->boundbox.high.x); + p->boundbox.high.y = Min(a->boundbox.high.y, b->boundbox.high.y); + p->boundbox.low.x = Max(a->boundbox.low.x, b->boundbox.low.x); + p->boundbox.low.y = Max(a->boundbox.low.y, b->boundbox.low.y); + + if (p->boundbox.high.x < p->boundbox.low.x || p->boundbox.high.y < p->boundbox.low.y) { - pfree(p); - return ((POLYGON *) NULL); + pfree(p); + return ((POLYGON *) NULL); } - - return (p); + + return (p); } diff --git a/src/backend/access/rtree/rtree.c b/src/backend/access/rtree/rtree.c index 4cd0580c973..ae92ea20136 100644 --- a/src/backend/access/rtree/rtree.c +++ b/src/backend/access/rtree/rtree.c @@ -1,13 +1,13 @@ /*------------------------------------------------------------------------- * * rtree.c-- - * interface routines for the postgres rtree indexed access method. + * interface routines for the postgres rtree indexed access method. * * Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/access/rtree/Attic/rtree.c,v 1.13 1997/08/12 22:51:54 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/access/rtree/Attic/rtree.c,v 1.14 1997/09/07 04:39:22 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -27,886 +27,983 @@ #include <storage/bufpage.h> #ifndef HAVE_MEMMOVE -# include <regex/utils.h> +#include <regex/utils.h> #else -# include <string.h> +#include <string.h> #endif -typedef struct SPLITVEC { - OffsetNumber *spl_left; - int spl_nleft; - char *spl_ldatum; - OffsetNumber *spl_right; - int spl_nright; - char *spl_rdatum; -} SPLITVEC; - -typedef struct RTSTATE { - func_ptr unionFn; /* union function */ - func_ptr sizeFn; /* size function */ - func_ptr interFn; /* intersection function */ -} RTSTATE; +typedef struct SPLITVEC +{ + OffsetNumber *spl_left; + int spl_nleft; + char *spl_ldatum; + OffsetNumber *spl_right; + int spl_nright; + char *spl_rdatum; +} SPLITVEC; + +typedef struct RTSTATE +{ + func_ptr unionFn; /* union function */ + func_ptr sizeFn; /* size function */ + func_ptr interFn; /* intersection function */ +} RTSTATE; /* non-export function prototypes */ -static InsertIndexResult rtdoinsert(Relation r, IndexTuple itup, - RTSTATE *rtstate); -static void rttighten(Relation r, RTSTACK *stk, char *datum, int att_size, - RTSTATE *rtstate); -static InsertIndexResult dosplit(Relation r, Buffer buffer, RTSTACK *stack, - IndexTuple itup, RTSTATE *rtstate); -static void rtintinsert(Relation r, RTSTACK *stk, IndexTuple ltup, - IndexTuple rtup, RTSTATE *rtstate); -static void rtnewroot(Relation r, IndexTuple lt, IndexTuple rt); -static void picksplit(Relation r, Page page, SPLITVEC *v, IndexTuple itup, - RTSTATE *rtstate); -static void RTInitBuffer(Buffer b, uint32 f); -static OffsetNumber choose(Relation r, Page p, IndexTuple it, - RTSTATE *rtstate); -static int nospace(Page p, IndexTuple it); -static void initRtstate(RTSTATE *rtstate, Relation index); +static InsertIndexResult +rtdoinsert(Relation r, IndexTuple itup, + RTSTATE * rtstate); +static void +rttighten(Relation r, RTSTACK * stk, char *datum, int att_size, + RTSTATE * rtstate); +static InsertIndexResult +dosplit(Relation r, Buffer buffer, RTSTACK * stack, + IndexTuple itup, RTSTATE * rtstate); +static void +rtintinsert(Relation r, RTSTACK * stk, IndexTuple ltup, + IndexTuple rtup, RTSTATE * rtstate); +static void rtnewroot(Relation r, IndexTuple lt, IndexTuple rt); +static void +picksplit(Relation r, Page page, SPLITVEC * v, IndexTuple itup, + RTSTATE * rtstate); +static void RTInitBuffer(Buffer b, uint32 f); +static OffsetNumber +choose(Relation r, Page p, IndexTuple it, + RTSTATE * rtstate); +static int nospace(Page p, IndexTuple it); +static void initRtstate(RTSTATE * rtstate, Relation index); void rtbuild(Relation heap, - Relation index, - int natts, - AttrNumber *attnum, - IndexStrategy istrat, - uint16 pcount, - Datum *params, - FuncIndexInfo *finfo, - PredInfo *predInfo) + Relation index, + int natts, + AttrNumber * attnum, + IndexStrategy istrat, + uint16 pcount, + Datum * params, + FuncIndexInfo * finfo, + PredInfo * predInfo) { - HeapScanDesc scan; - Buffer buffer; - AttrNumber i; - HeapTuple htup; - IndexTuple itup; - TupleDesc hd, id; - InsertIndexResult res; - Datum *d; - bool *nulls; - int nb, nh, ni; + HeapScanDesc scan; + Buffer buffer; + AttrNumber i; + HeapTuple htup; + IndexTuple itup; + TupleDesc hd, + id; + InsertIndexResult res; + Datum *d; + bool *nulls; + int nb, + nh, + ni; + #ifndef OMIT_PARTIAL_INDEX - ExprContext *econtext; - TupleTable tupleTable; - TupleTableSlot *slot; + ExprContext *econtext; + TupleTable tupleTable; + TupleTableSlot *slot; + #endif - Oid hrelid, irelid; - Node *pred, *oldPred; - RTSTATE rtState; - - initRtstate(&rtState, index); - - /* rtrees only know how to do stupid locking now */ - RelationSetLockForWrite(index); - - pred = predInfo->pred; - oldPred = predInfo->oldPred; - - /* - * We expect to be called exactly once for any index relation. - * If that's not the case, big trouble's what we have. - */ - - if (oldPred == NULL && (nb = RelationGetNumberOfBlocks(index)) != 0) - elog(WARN, "%s already contains data", index->rd_rel->relname.data); - - /* initialize the root page (if this is a new index) */ - if (oldPred == NULL) { - buffer = ReadBuffer(index, P_NEW); - RTInitBuffer(buffer, F_LEAF); - WriteBuffer(buffer); - } - - /* init the tuple descriptors and get set for a heap scan */ - hd = RelationGetTupleDescriptor(heap); - id = RelationGetTupleDescriptor(index); - d = (Datum *)palloc(natts * sizeof (*d)); - nulls = (bool *)palloc(natts * sizeof (*nulls)); - - /* - * If this is a predicate (partial) index, we will need to evaluate the - * predicate using ExecQual, which requires the current tuple to be in a - * slot of a TupleTable. In addition, ExecQual must have an ExprContext - * referring to that slot. Here, we initialize dummy TupleTable and - * ExprContext objects for this purpose. --Nels, Feb '92 - */ + Oid hrelid, + irelid; + Node *pred, + *oldPred; + RTSTATE rtState; + + initRtstate(&rtState, index); + + /* rtrees only know how to do stupid locking now */ + RelationSetLockForWrite(index); + + pred = predInfo->pred; + oldPred = predInfo->oldPred; + + /* + * We expect to be called exactly once for any index relation. If + * that's not the case, big trouble's what we have. + */ + + if (oldPred == NULL && (nb = RelationGetNumberOfBlocks(index)) != 0) + elog(WARN, "%s already contains data", index->rd_rel->relname.data); + + /* initialize the root page (if this is a new index) */ + if (oldPred == NULL) + { + buffer = ReadBuffer(index, P_NEW); + RTInitBuffer(buffer, F_LEAF); + WriteBuffer(buffer); + } + + /* init the tuple descriptors and get set for a heap scan */ + hd = RelationGetTupleDescriptor(heap); + id = RelationGetTupleDescriptor(index); + d = (Datum *) palloc(natts * sizeof(*d)); + nulls = (bool *) palloc(natts * sizeof(*nulls)); + + /* + * If this is a predicate (partial) index, we will need to evaluate + * the predicate using ExecQual, which requires the current tuple to + * be in a slot of a TupleTable. In addition, ExecQual must have an + * ExprContext referring to that slot. Here, we initialize dummy + * TupleTable and ExprContext objects for this purpose. --Nels, Feb + * '92 + */ #ifndef OMIT_PARTIAL_INDEX - if (pred != NULL || oldPred != NULL) { - tupleTable = ExecCreateTupleTable(1); - slot = ExecAllocTableSlot(tupleTable); - econtext = makeNode(ExprContext); - FillDummyExprContext(econtext, slot, hd, buffer); - } + if (pred != NULL || oldPred != NULL) + { + tupleTable = ExecCreateTupleTable(1); + slot = ExecAllocTableSlot(tupleTable); + econtext = makeNode(ExprContext); + FillDummyExprContext(econtext, slot, hd, buffer); + } else { econtext = NULL; tupleTable = NULL; slot = NULL; } -#endif /* OMIT_PARTIAL_INDEX */ - scan = heap_beginscan(heap, 0, NowTimeQual, 0, (ScanKey) NULL); - htup = heap_getnext(scan, 0, &buffer); - - /* count the tuples as we insert them */ - nh = ni = 0; - - for (; HeapTupleIsValid(htup); htup = heap_getnext(scan, 0, &buffer)) { - - nh++; - - /* - * If oldPred != NULL, this is an EXTEND INDEX command, so skip - * this tuple if it was already in the existing partial index - */ - if (oldPred != NULL) { +#endif /* OMIT_PARTIAL_INDEX */ + scan = heap_beginscan(heap, 0, NowTimeQual, 0, (ScanKey) NULL); + htup = heap_getnext(scan, 0, &buffer); + + /* count the tuples as we insert them */ + nh = ni = 0; + + for (; HeapTupleIsValid(htup); htup = heap_getnext(scan, 0, &buffer)) + { + + nh++; + + /* + * If oldPred != NULL, this is an EXTEND INDEX command, so skip + * this tuple if it was already in the existing partial index + */ + if (oldPred != NULL) + { #ifndef OMIT_PARTIAL_INDEX - /*SetSlotContents(slot, htup); */ - slot->val = htup; - if (ExecQual((List*)oldPred, econtext) == true) { + /* SetSlotContents(slot, htup); */ + slot->val = htup; + if (ExecQual((List *) oldPred, econtext) == true) + { + ni++; + continue; + } +#endif /* OMIT_PARTIAL_INDEX */ + } + + /* + * Skip this tuple if it doesn't satisfy the partial-index + * predicate + */ + if (pred != NULL) + { +#ifndef OMIT_PARTIAL_INDEX + /* SetSlotContents(slot, htup); */ + slot->val = htup; + if (ExecQual((List *) pred, econtext) == false) + continue; +#endif /* OMIT_PARTIAL_INDEX */ + } + ni++; - continue; - } -#endif /* OMIT_PARTIAL_INDEX */ + + /* + * For the current heap tuple, extract all the attributes we use + * in this index, and note which are null. + */ + + for (i = 1; i <= natts; i++) + { + int attoff; + bool attnull; + + /* + * Offsets are from the start of the tuple, and are + * zero-based; indices are one-based. The next call returns i + * - 1. That's data hiding for you. + */ + + attoff = AttrNumberGetAttrOffset(i); + + /* + * d[attoff] = HeapTupleGetAttributeValue(htup, buffer, + */ + d[attoff] = GetIndexValue(htup, + hd, + attoff, + attnum, + finfo, + &attnull, + buffer); + nulls[attoff] = (attnull ? 'n' : ' '); + } + + /* form an index tuple and point it at the heap tuple */ + itup = index_formtuple(id, &d[0], nulls); + itup->t_tid = htup->t_ctid; + + /* + * Since we already have the index relation locked, we call + * rtdoinsert directly. Normal access method calls dispatch + * through rtinsert, which locks the relation for write. This is + * the right thing to do if you're inserting single tups, but not + * when you're initializing the whole index at once. + */ + + res = rtdoinsert(index, itup, &rtState); + pfree(itup); + pfree(res); } - - /* Skip this tuple if it doesn't satisfy the partial-index predicate */ - if (pred != NULL) { + + /* okay, all heap tuples are indexed */ + heap_endscan(scan); + RelationUnsetLockForWrite(index); + + if (pred != NULL || oldPred != NULL) + { #ifndef OMIT_PARTIAL_INDEX - /*SetSlotContents(slot, htup); */ - slot->val = htup; - if (ExecQual((List*)pred, econtext) == false) - continue; -#endif /* OMIT_PARTIAL_INDEX */ + ExecDestroyTupleTable(tupleTable, true); + pfree(econtext); +#endif /* OMIT_PARTIAL_INDEX */ } - - ni++; - + /* - * For the current heap tuple, extract all the attributes - * we use in this index, and note which are null. + * Since we just counted the tuples in the heap, we update its stats + * in pg_relation to guarantee that the planner takes advantage of the + * index we just created. UpdateStats() does a + * CommandCounterIncrement(), which flushes changed entries from the + * system relcache. The act of constructing an index changes these + * heap and index tuples in the system catalogs, so they need to be + * flushed. We close them to guarantee that they will be. */ - - for (i = 1; i <= natts; i++) { - int attoff; - bool attnull; - - /* - * Offsets are from the start of the tuple, and are - * zero-based; indices are one-based. The next call - * returns i - 1. That's data hiding for you. - */ - - attoff = AttrNumberGetAttrOffset(i); - /* - d[attoff] = HeapTupleGetAttributeValue(htup, buffer, - */ - d[attoff] = GetIndexValue(htup, - hd, - attoff, - attnum, - finfo, - &attnull, - buffer); - nulls[attoff] = (attnull ? 'n' : ' '); + + hrelid = heap->rd_id; + irelid = index->rd_id; + heap_close(heap); + index_close(index); + + UpdateStats(hrelid, nh, true); + UpdateStats(irelid, ni, false); + + if (oldPred != NULL) + { + if (ni == nh) + pred = NULL; + UpdateIndexPredicate(irelid, oldPred, pred); } - - /* form an index tuple and point it at the heap tuple */ - itup = index_formtuple(id, &d[0], nulls); - itup->t_tid = htup->t_ctid; - - /* - * Since we already have the index relation locked, we - * call rtdoinsert directly. Normal access method calls - * dispatch through rtinsert, which locks the relation - * for write. This is the right thing to do if you're - * inserting single tups, but not when you're initializing - * the whole index at once. - */ - - res = rtdoinsert(index, itup, &rtState); - pfree(itup); - pfree(res); - } - - /* okay, all heap tuples are indexed */ - heap_endscan(scan); - RelationUnsetLockForWrite(index); - - if (pred != NULL || oldPred != NULL) { -#ifndef OMIT_PARTIAL_INDEX - ExecDestroyTupleTable(tupleTable, true); - pfree(econtext); -#endif /* OMIT_PARTIAL_INDEX */ - } - - /* - * Since we just counted the tuples in the heap, we update its - * stats in pg_relation to guarantee that the planner takes - * advantage of the index we just created. UpdateStats() does a - * CommandCounterIncrement(), which flushes changed entries from - * the system relcache. The act of constructing an index changes - * these heap and index tuples in the system catalogs, so they - * need to be flushed. We close them to guarantee that they - * will be. - */ - - hrelid = heap->rd_id; - irelid = index->rd_id; - heap_close(heap); - index_close(index); - - UpdateStats(hrelid, nh, true); - UpdateStats(irelid, ni, false); - - if (oldPred != NULL) { - if (ni == nh) pred = NULL; - UpdateIndexPredicate(irelid, oldPred, pred); - } - - /* be tidy */ - pfree(nulls); - pfree(d); + + /* be tidy */ + pfree(nulls); + pfree(d); } /* - * rtinsert -- wrapper for rtree tuple insertion. + * rtinsert -- wrapper for rtree tuple insertion. * - * This is the public interface routine for tuple insertion in rtrees. - * It doesn't do any work; just locks the relation and passes the buck. + * This is the public interface routine for tuple insertion in rtrees. + * It doesn't do any work; just locks the relation and passes the buck. */ InsertIndexResult -rtinsert(Relation r, Datum *datum, char *nulls, ItemPointer ht_ctid, Relation heapRel) +rtinsert(Relation r, Datum * datum, char *nulls, ItemPointer ht_ctid, Relation heapRel) { - InsertIndexResult res; - IndexTuple itup; - RTSTATE rtState; - - /* generate an index tuple */ - itup = index_formtuple(RelationGetTupleDescriptor(r), datum, nulls); - itup->t_tid = *ht_ctid; - initRtstate(&rtState, r); - - RelationSetLockForWrite(r); - res = rtdoinsert(r, itup, &rtState); - - /* XXX two-phase locking -- don't unlock the relation until EOT */ - return (res); + InsertIndexResult res; + IndexTuple itup; + RTSTATE rtState; + + /* generate an index tuple */ + itup = index_formtuple(RelationGetTupleDescriptor(r), datum, nulls); + itup->t_tid = *ht_ctid; + initRtstate(&rtState, r); + + RelationSetLockForWrite(r); + res = rtdoinsert(r, itup, &rtState); + + /* XXX two-phase locking -- don't unlock the relation until EOT */ + return (res); } -static InsertIndexResult -rtdoinsert(Relation r, IndexTuple itup, RTSTATE *rtstate) +static InsertIndexResult +rtdoinsert(Relation r, IndexTuple itup, RTSTATE * rtstate) { - Page page; - Buffer buffer; - BlockNumber blk; - IndexTuple which; - OffsetNumber l; - RTSTACK *stack; - InsertIndexResult res; - RTreePageOpaque opaque; - char *datum; - - blk = P_ROOT; - buffer = InvalidBuffer; - stack = (RTSTACK *) NULL; - - do { - /* let go of current buffer before getting next */ - if (buffer != InvalidBuffer) - ReleaseBuffer(buffer); - - /* get next buffer */ - buffer = ReadBuffer(r, blk); - page = (Page) BufferGetPage(buffer); - - opaque = (RTreePageOpaque) PageGetSpecialPointer(page); - if (!(opaque->flags & F_LEAF)) { - RTSTACK *n; - ItemId iid; - - n = (RTSTACK *) palloc(sizeof(RTSTACK)); - n->rts_parent = stack; - n->rts_blk = blk; - n->rts_child = choose(r, page, itup, rtstate); - stack = n; - - iid = PageGetItemId(page, n->rts_child); - which = (IndexTuple) PageGetItem(page, iid); - blk = ItemPointerGetBlockNumber(&(which->t_tid)); + Page page; + Buffer buffer; + BlockNumber blk; + IndexTuple which; + OffsetNumber l; + RTSTACK *stack; + InsertIndexResult res; + RTreePageOpaque opaque; + char *datum; + + blk = P_ROOT; + buffer = InvalidBuffer; + stack = (RTSTACK *) NULL; + + do + { + /* let go of current buffer before getting next */ + if (buffer != InvalidBuffer) + ReleaseBuffer(buffer); + + /* get next buffer */ + buffer = ReadBuffer(r, blk); + page = (Page) BufferGetPage(buffer); + + opaque = (RTreePageOpaque) PageGetSpecialPointer(page); + if (!(opaque->flags & F_LEAF)) + { + RTSTACK *n; + ItemId iid; + + n = (RTSTACK *) palloc(sizeof(RTSTACK)); + n->rts_parent = stack; + n->rts_blk = blk; + n->rts_child = choose(r, page, itup, rtstate); + stack = n; + + iid = PageGetItemId(page, n->rts_child); + which = (IndexTuple) PageGetItem(page, iid); + blk = ItemPointerGetBlockNumber(&(which->t_tid)); + } + } while (!(opaque->flags & F_LEAF)); + + if (nospace(page, itup)) + { + /* need to do a split */ + res = dosplit(r, buffer, stack, itup, rtstate); + freestack(stack); + WriteBuffer(buffer); /* don't forget to release buffer! */ + return (res); + } + + /* add the item and write the buffer */ + if (PageIsEmpty(page)) + { + l = PageAddItem(page, (Item) itup, IndexTupleSize(itup), + FirstOffsetNumber, + LP_USED); } - } while (!(opaque->flags & F_LEAF)); - - if (nospace(page, itup)) { - /* need to do a split */ - res = dosplit(r, buffer, stack, itup, rtstate); + else + { + l = PageAddItem(page, (Item) itup, IndexTupleSize(itup), + OffsetNumberNext(PageGetMaxOffsetNumber(page)), + LP_USED); + } + + WriteBuffer(buffer); + + datum = (((char *) itup) + sizeof(IndexTupleData)); + + /* now expand the page boundary in the parent to include the new child */ + rttighten(r, stack, datum, + (IndexTupleSize(itup) - sizeof(IndexTupleData)), rtstate); freestack(stack); - WriteBuffer(buffer); /* don't forget to release buffer! */ + + /* build and return an InsertIndexResult for this insertion */ + res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData)); + ItemPointerSet(&(res->pointerData), blk, l); + return (res); - } - - /* add the item and write the buffer */ - if (PageIsEmpty(page)) { - l = PageAddItem(page, (Item) itup, IndexTupleSize(itup), - FirstOffsetNumber, - LP_USED); - } else { - l = PageAddItem(page, (Item) itup, IndexTupleSize(itup), - OffsetNumberNext(PageGetMaxOffsetNumber(page)), - LP_USED); - } - - WriteBuffer(buffer); - - datum = (((char *) itup) + sizeof(IndexTupleData)); - - /* now expand the page boundary in the parent to include the new child */ - rttighten(r, stack, datum, - (IndexTupleSize(itup) - sizeof(IndexTupleData)), rtstate); - freestack(stack); - - /* build and return an InsertIndexResult for this insertion */ - res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData)); - ItemPointerSet(&(res->pointerData), blk, l); - - return (res); } static void rttighten(Relation r, - RTSTACK *stk, - char *datum, - int att_size, - RTSTATE *rtstate) + RTSTACK * stk, + char *datum, + int att_size, + RTSTATE * rtstate) { - char *oldud; - char *tdatum; - Page p; - float old_size, newd_size; - Buffer b; - - if (stk == (RTSTACK *) NULL) - return; - - b = ReadBuffer(r, stk->rts_blk); - p = BufferGetPage(b); - - oldud = (char *) PageGetItem(p, PageGetItemId(p, stk->rts_child)); - oldud += sizeof(IndexTupleData); - - (*rtstate->sizeFn)(oldud, &old_size); - datum = (char *) (*rtstate->unionFn)(oldud, datum); - - (*rtstate->sizeFn)(datum, &newd_size); - - if (newd_size != old_size) { - TupleDesc td = RelationGetTupleDescriptor(r); - - if (td->attrs[0]->attlen < 0) { - /* - * This is an internal page, so 'oldud' had better be a - * union (constant-length) key, too. (See comment below.) - */ - Assert(VARSIZE(datum) == VARSIZE(oldud)); - memmove(oldud, datum, VARSIZE(datum)); - } else { - memmove(oldud, datum, att_size); + char *oldud; + char *tdatum; + Page p; + float old_size, + newd_size; + Buffer b; + + if (stk == (RTSTACK *) NULL) + return; + + b = ReadBuffer(r, stk->rts_blk); + p = BufferGetPage(b); + + oldud = (char *) PageGetItem(p, PageGetItemId(p, stk->rts_child)); + oldud += sizeof(IndexTupleData); + + (*rtstate->sizeFn) (oldud, &old_size); + datum = (char *) (*rtstate->unionFn) (oldud, datum); + + (*rtstate->sizeFn) (datum, &newd_size); + + if (newd_size != old_size) + { + TupleDesc td = RelationGetTupleDescriptor(r); + + if (td->attrs[0]->attlen < 0) + { + + /* + * This is an internal page, so 'oldud' had better be a union + * (constant-length) key, too. (See comment below.) + */ + Assert(VARSIZE(datum) == VARSIZE(oldud)); + memmove(oldud, datum, VARSIZE(datum)); + } + else + { + memmove(oldud, datum, att_size); + } + WriteBuffer(b); + + /* + * The user may be defining an index on variable-sized data (like + * polygons). If so, we need to get a constant-sized datum for + * insertion on the internal page. We do this by calling the + * union proc, which is guaranteed to return a rectangle. + */ + + tdatum = (char *) (*rtstate->unionFn) (datum, datum); + rttighten(r, stk->rts_parent, tdatum, att_size, rtstate); + pfree(tdatum); } - WriteBuffer(b); - - /* - * The user may be defining an index on variable-sized data (like - * polygons). If so, we need to get a constant-sized datum for - * insertion on the internal page. We do this by calling the union - * proc, which is guaranteed to return a rectangle. - */ - - tdatum = (char *) (*rtstate->unionFn)(datum, datum); - rttighten(r, stk->rts_parent, tdatum, att_size, rtstate); - pfree(tdatum); - } else { - ReleaseBuffer(b); - } - pfree(datum); + else + { + ReleaseBuffer(b); + } + pfree(datum); } /* - * dosplit -- split a page in the tree. + * dosplit -- split a page in the tree. * - * This is the quadratic-cost split algorithm Guttman describes in - * his paper. The reason we chose it is that you can implement this - * with less information about the data types on which you're operating. + * This is the quadratic-cost split algorithm Guttman describes in + * his paper. The reason we chose it is that you can implement this + * with less information about the data types on which you're operating. */ -static InsertIndexResult +static InsertIndexResult dosplit(Relation r, - Buffer buffer, - RTSTACK *stack, - IndexTuple itup, - RTSTATE *rtstate) + Buffer buffer, + RTSTACK * stack, + IndexTuple itup, + RTSTATE * rtstate) { - Page p; - Buffer leftbuf, rightbuf; - Page left, right; - ItemId itemid; - IndexTuple item; - IndexTuple ltup, rtup; - OffsetNumber maxoff; - OffsetNumber i; - OffsetNumber leftoff, rightoff; - BlockNumber lbknum, rbknum; - BlockNumber bufblock; - RTreePageOpaque opaque; - int blank; - InsertIndexResult res; - char *isnull; - SPLITVEC v; - TupleDesc tupDesc; - - isnull = (char *) palloc(r->rd_rel->relnatts); - for (blank = 0; blank < r->rd_rel->relnatts; blank++) - isnull[blank] = ' '; - p = (Page) BufferGetPage(buffer); - opaque = (RTreePageOpaque) PageGetSpecialPointer(p); - - /* - * The root of the tree is the first block in the relation. If - * we're about to split the root, we need to do some hocus-pocus - * to enforce this guarantee. - */ - - if (BufferGetBlockNumber(buffer) == P_ROOT) { - leftbuf = ReadBuffer(r, P_NEW); - RTInitBuffer(leftbuf, opaque->flags); - lbknum = BufferGetBlockNumber(leftbuf); - left = (Page) BufferGetPage(leftbuf); - } else { - leftbuf = buffer; - IncrBufferRefCount(buffer); - lbknum = BufferGetBlockNumber(buffer); - left = (Page) PageGetTempPage(p, sizeof(RTreePageOpaqueData)); - } - - rightbuf = ReadBuffer(r, P_NEW); - RTInitBuffer(rightbuf, opaque->flags); - rbknum = BufferGetBlockNumber(rightbuf); - right = (Page) BufferGetPage(rightbuf); - - picksplit(r, p, &v, itup, rtstate); - - leftoff = rightoff = FirstOffsetNumber; - maxoff = PageGetMaxOffsetNumber(p); - for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) { - itemid = PageGetItemId(p, i); - item = (IndexTuple) PageGetItem(p, itemid); - - if (i == *(v.spl_left)) { - PageAddItem(left, (Item) item, IndexTupleSize(item), - leftoff, LP_USED); - leftoff = OffsetNumberNext(leftoff); - v.spl_left++; /* advance in left split vector */ - } else { - PageAddItem(right, (Item) item, IndexTupleSize(item), - rightoff, LP_USED); - rightoff = OffsetNumberNext(rightoff); - v.spl_right++; /* advance in right split vector */ + Page p; + Buffer leftbuf, + rightbuf; + Page left, + right; + ItemId itemid; + IndexTuple item; + IndexTuple ltup, + rtup; + OffsetNumber maxoff; + OffsetNumber i; + OffsetNumber leftoff, + rightoff; + BlockNumber lbknum, + rbknum; + BlockNumber bufblock; + RTreePageOpaque opaque; + int blank; + InsertIndexResult res; + char *isnull; + SPLITVEC v; + TupleDesc tupDesc; + + isnull = (char *) palloc(r->rd_rel->relnatts); + for (blank = 0; blank < r->rd_rel->relnatts; blank++) + isnull[blank] = ' '; + p = (Page) BufferGetPage(buffer); + opaque = (RTreePageOpaque) PageGetSpecialPointer(p); + + /* + * The root of the tree is the first block in the relation. If we're + * about to split the root, we need to do some hocus-pocus to enforce + * this guarantee. + */ + + if (BufferGetBlockNumber(buffer) == P_ROOT) + { + leftbuf = ReadBuffer(r, P_NEW); + RTInitBuffer(leftbuf, opaque->flags); + lbknum = BufferGetBlockNumber(leftbuf); + left = (Page) BufferGetPage(leftbuf); } - } - - /* build an InsertIndexResult for this insertion */ - res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData)); - - /* now insert the new index tuple */ - if (*(v.spl_left) != FirstOffsetNumber) { - PageAddItem(left, (Item) itup, IndexTupleSize(itup), - leftoff, LP_USED); - leftoff = OffsetNumberNext(leftoff); - ItemPointerSet(&(res->pointerData), lbknum, leftoff); - } else { - PageAddItem(right, (Item) itup, IndexTupleSize(itup), - rightoff, LP_USED); - rightoff = OffsetNumberNext(rightoff); - ItemPointerSet(&(res->pointerData), rbknum, rightoff); - } - - if ((bufblock = BufferGetBlockNumber(buffer)) != P_ROOT) { - PageRestoreTempPage(left, p); - } - WriteBuffer(leftbuf); - WriteBuffer(rightbuf); - - /* - * Okay, the page is split. We have three things left to do: - * - * 1) Adjust any active scans on this index to cope with changes - * we introduced in its structure by splitting this page. - * - * 2) "Tighten" the bounding box of the pointer to the left - * page in the parent node in the tree, if any. Since we - * moved a bunch of stuff off the left page, we expect it - * to get smaller. This happens in the internal insertion - * routine. - * - * 3) Insert a pointer to the right page in the parent. This - * may cause the parent to split. If it does, we need to - * repeat steps one and two for each split node in the tree. - */ - - /* adjust active scans */ - rtadjscans(r, RTOP_SPLIT, bufblock, FirstOffsetNumber); - - tupDesc = r->rd_att; - ltup = (IndexTuple) index_formtuple(tupDesc, - (Datum *) &(v.spl_ldatum), isnull); - rtup = (IndexTuple) index_formtuple(tupDesc, - (Datum *) &(v.spl_rdatum), isnull); - pfree(isnull); - - /* set pointers to new child pages in the internal index tuples */ - ItemPointerSet(&(ltup->t_tid), lbknum, 1); - ItemPointerSet(&(rtup->t_tid), rbknum, 1); - - rtintinsert(r, stack, ltup, rtup, rtstate); - - pfree(ltup); - pfree(rtup); - - return (res); + else + { + leftbuf = buffer; + IncrBufferRefCount(buffer); + lbknum = BufferGetBlockNumber(buffer); + left = (Page) PageGetTempPage(p, sizeof(RTreePageOpaqueData)); + } + + rightbuf = ReadBuffer(r, P_NEW); + RTInitBuffer(rightbuf, opaque->flags); + rbknum = BufferGetBlockNumber(rightbuf); + right = (Page) BufferGetPage(rightbuf); + + picksplit(r, p, &v, itup, rtstate); + + leftoff = rightoff = FirstOffsetNumber; + maxoff = PageGetMaxOffsetNumber(p); + for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) + { + itemid = PageGetItemId(p, i); + item = (IndexTuple) PageGetItem(p, itemid); + + if (i == *(v.spl_left)) + { + PageAddItem(left, (Item) item, IndexTupleSize(item), + leftoff, LP_USED); + leftoff = OffsetNumberNext(leftoff); + v.spl_left++; /* advance in left split vector */ + } + else + { + PageAddItem(right, (Item) item, IndexTupleSize(item), + rightoff, LP_USED); + rightoff = OffsetNumberNext(rightoff); + v.spl_right++; /* advance in right split vector */ + } + } + + /* build an InsertIndexResult for this insertion */ + res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData)); + + /* now insert the new index tuple */ + if (*(v.spl_left) != FirstOffsetNumber) + { + PageAddItem(left, (Item) itup, IndexTupleSize(itup), + leftoff, LP_USED); + leftoff = OffsetNumberNext(leftoff); + ItemPointerSet(&(res->pointerData), lbknum, leftoff); + } + else + { + PageAddItem(right, (Item) itup, IndexTupleSize(itup), + rightoff, LP_USED); + rightoff = OffsetNumberNext(rightoff); + ItemPointerSet(&(res->pointerData), rbknum, rightoff); + } + + if ((bufblock = BufferGetBlockNumber(buffer)) != P_ROOT) + { + PageRestoreTempPage(left, p); + } + WriteBuffer(leftbuf); + WriteBuffer(rightbuf); + + /* + * Okay, the page is split. We have three things left to do: + * + * 1) Adjust any active scans on this index to cope with changes we + * introduced in its structure by splitting this page. + * + * 2) "Tighten" the bounding box of the pointer to the left page in the + * parent node in the tree, if any. Since we moved a bunch of stuff + * off the left page, we expect it to get smaller. This happens in + * the internal insertion routine. + * + * 3) Insert a pointer to the right page in the parent. This may cause + * the parent to split. If it does, we need to repeat steps one and + * two for each split node in the tree. + */ + + /* adjust active scans */ + rtadjscans(r, RTOP_SPLIT, bufblock, FirstOffsetNumber); + + tupDesc = r->rd_att; + ltup = (IndexTuple) index_formtuple(tupDesc, + (Datum *) & (v.spl_ldatum), isnull); + rtup = (IndexTuple) index_formtuple(tupDesc, + (Datum *) & (v.spl_rdatum), isnull); + pfree(isnull); + + /* set pointers to new child pages in the internal index tuples */ + ItemPointerSet(&(ltup->t_tid), lbknum, 1); + ItemPointerSet(&(rtup->t_tid), rbknum, 1); + + rtintinsert(r, stack, ltup, rtup, rtstate); + + pfree(ltup); + pfree(rtup); + + return (res); } static void rtintinsert(Relation r, - RTSTACK *stk, - IndexTuple ltup, - IndexTuple rtup, - RTSTATE *rtstate) + RTSTACK * stk, + IndexTuple ltup, + IndexTuple rtup, + RTSTATE * rtstate) { - IndexTuple old; - Buffer b; - Page p; - char *ldatum, *rdatum, *newdatum; - InsertIndexResult res; - - if (stk == (RTSTACK *) NULL) { - rtnewroot(r, ltup, rtup); - return; - } - - b = ReadBuffer(r, stk->rts_blk); - p = BufferGetPage(b); - old = (IndexTuple) PageGetItem(p, PageGetItemId(p, stk->rts_child)); - - /* - * This is a hack. Right now, we force rtree keys to be constant size. - * To fix this, need delete the old key and add both left and right - * for the two new pages. The insertion of left may force a split if - * the new left key is bigger than the old key. - */ - - if (IndexTupleSize(old) != IndexTupleSize(ltup)) - elog(WARN, "Variable-length rtree keys are not supported."); - - /* install pointer to left child */ - memmove(old, ltup,IndexTupleSize(ltup)); - - if (nospace(p, rtup)) { - newdatum = (((char *) ltup) + sizeof(IndexTupleData)); - rttighten(r, stk->rts_parent, newdatum, - (IndexTupleSize(ltup) - sizeof(IndexTupleData)), rtstate); - res = dosplit(r, b, stk->rts_parent, rtup, rtstate); - WriteBuffer(b); /* don't forget to release buffer! - 01/31/94 */ - pfree(res); - } else { - PageAddItem(p, (Item) rtup, IndexTupleSize(rtup), - PageGetMaxOffsetNumber(p), LP_USED); - WriteBuffer(b); - ldatum = (((char *) ltup) + sizeof(IndexTupleData)); - rdatum = (((char *) rtup) + sizeof(IndexTupleData)); - newdatum = (char *) (*rtstate->unionFn)(ldatum, rdatum); - - rttighten(r, stk->rts_parent, newdatum, - (IndexTupleSize(rtup) - sizeof(IndexTupleData)), rtstate); - - pfree(newdatum); - } + IndexTuple old; + Buffer b; + Page p; + char *ldatum, + *rdatum, + *newdatum; + InsertIndexResult res; + + if (stk == (RTSTACK *) NULL) + { + rtnewroot(r, ltup, rtup); + return; + } + + b = ReadBuffer(r, stk->rts_blk); + p = BufferGetPage(b); + old = (IndexTuple) PageGetItem(p, PageGetItemId(p, stk->rts_child)); + + /* + * This is a hack. Right now, we force rtree keys to be constant + * size. To fix this, need delete the old key and add both left and + * right for the two new pages. The insertion of left may force a + * split if the new left key is bigger than the old key. + */ + + if (IndexTupleSize(old) != IndexTupleSize(ltup)) + elog(WARN, "Variable-length rtree keys are not supported."); + + /* install pointer to left child */ + memmove(old, ltup, IndexTupleSize(ltup)); + + if (nospace(p, rtup)) + { + newdatum = (((char *) ltup) + sizeof(IndexTupleData)); + rttighten(r, stk->rts_parent, newdatum, + (IndexTupleSize(ltup) - sizeof(IndexTupleData)), rtstate); + res = dosplit(r, b, stk->rts_parent, rtup, rtstate); + WriteBuffer(b); /* don't forget to release buffer! - + * 01/31/94 */ + pfree(res); + } + else + { + PageAddItem(p, (Item) rtup, IndexTupleSize(rtup), + PageGetMaxOffsetNumber(p), LP_USED); + WriteBuffer(b); + ldatum = (((char *) ltup) + sizeof(IndexTupleData)); + rdatum = (((char *) rtup) + sizeof(IndexTupleData)); + newdatum = (char *) (*rtstate->unionFn) (ldatum, rdatum); + + rttighten(r, stk->rts_parent, newdatum, + (IndexTupleSize(rtup) - sizeof(IndexTupleData)), rtstate); + + pfree(newdatum); + } } static void rtnewroot(Relation r, IndexTuple lt, IndexTuple rt) { - Buffer b; - Page p; - - b = ReadBuffer(r, P_ROOT); - RTInitBuffer(b, 0); - p = BufferGetPage(b); - PageAddItem(p, (Item) lt, IndexTupleSize(lt), - FirstOffsetNumber, LP_USED); - PageAddItem(p, (Item) rt, IndexTupleSize(rt), - OffsetNumberNext(FirstOffsetNumber), LP_USED); - WriteBuffer(b); + Buffer b; + Page p; + + b = ReadBuffer(r, P_ROOT); + RTInitBuffer(b, 0); + p = BufferGetPage(b); + PageAddItem(p, (Item) lt, IndexTupleSize(lt), + FirstOffsetNumber, LP_USED); + PageAddItem(p, (Item) rt, IndexTupleSize(rt), + OffsetNumberNext(FirstOffsetNumber), LP_USED); + WriteBuffer(b); } static void picksplit(Relation r, - Page page, - SPLITVEC *v, - IndexTuple itup, - RTSTATE *rtstate) + Page page, + SPLITVEC * v, + IndexTuple itup, + RTSTATE * rtstate) { - OffsetNumber maxoff; - OffsetNumber i, j; - IndexTuple item_1, item_2; - char *datum_alpha, *datum_beta; - char *datum_l, *datum_r; - char *union_d, *union_dl, *union_dr; - char *inter_d; - bool firsttime; - float size_alpha, size_beta, size_union, size_inter; - float size_waste, waste; - float size_l, size_r; - int nbytes; - OffsetNumber seed_1 = 0, seed_2 = 0; - OffsetNumber *left, *right; - - maxoff = PageGetMaxOffsetNumber(page); - - nbytes = (maxoff + 2) * sizeof(OffsetNumber); - v->spl_left = (OffsetNumber *) palloc(nbytes); - v->spl_right = (OffsetNumber *) palloc(nbytes); - - firsttime = true; - waste = 0.0; - - for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i)) { - item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, i)); - datum_alpha = ((char *) item_1) + sizeof(IndexTupleData); - for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j)) { - item_2 = (IndexTuple) PageGetItem(page, PageGetItemId(page, j)); - datum_beta = ((char *) item_2) + sizeof(IndexTupleData); - - /* compute the wasted space by unioning these guys */ - union_d = (char *)(rtstate->unionFn)(datum_alpha, datum_beta); - (rtstate->sizeFn)(union_d, &size_union); - inter_d = (char *)(rtstate->interFn)(datum_alpha, datum_beta); - (rtstate->sizeFn)(inter_d, &size_inter); - size_waste = size_union - size_inter; - - pfree(union_d); - - if (inter_d != (char *) NULL) - pfree(inter_d); - - /* - * are these a more promising split that what we've - * already seen? - */ - - if (size_waste > waste || firsttime) { - waste = size_waste; - seed_1 = i; - seed_2 = j; - firsttime = false; - } + OffsetNumber maxoff; + OffsetNumber i, + j; + IndexTuple item_1, + item_2; + char *datum_alpha, + *datum_beta; + char *datum_l, + *datum_r; + char *union_d, + *union_dl, + *union_dr; + char *inter_d; + bool firsttime; + float size_alpha, + size_beta, + size_union, + size_inter; + float size_waste, + waste; + float size_l, + size_r; + int nbytes; + OffsetNumber seed_1 = 0, + seed_2 = 0; + OffsetNumber *left, + *right; + + maxoff = PageGetMaxOffsetNumber(page); + + nbytes = (maxoff + 2) * sizeof(OffsetNumber); + v->spl_left = (OffsetNumber *) palloc(nbytes); + v->spl_right = (OffsetNumber *) palloc(nbytes); + + firsttime = true; + waste = 0.0; + + for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i)) + { + item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, i)); + datum_alpha = ((char *) item_1) + sizeof(IndexTupleData); + for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j)) + { + item_2 = (IndexTuple) PageGetItem(page, PageGetItemId(page, j)); + datum_beta = ((char *) item_2) + sizeof(IndexTupleData); + + /* compute the wasted space by unioning these guys */ + union_d = (char *) (rtstate->unionFn) (datum_alpha, datum_beta); + (rtstate->sizeFn) (union_d, &size_union); + inter_d = (char *) (rtstate->interFn) (datum_alpha, datum_beta); + (rtstate->sizeFn) (inter_d, &size_inter); + size_waste = size_union - size_inter; + + pfree(union_d); + + if (inter_d != (char *) NULL) + pfree(inter_d); + + /* + * are these a more promising split that what we've already + * seen? + */ + + if (size_waste > waste || firsttime) + { + waste = size_waste; + seed_1 = i; + seed_2 = j; + firsttime = false; + } + } } - } - - left = v->spl_left; - v->spl_nleft = 0; - right = v->spl_right; - v->spl_nright = 0; - - item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, seed_1)); - datum_alpha = ((char *) item_1) + sizeof(IndexTupleData); - datum_l = (char *)(*rtstate->unionFn)(datum_alpha, datum_alpha); - (*rtstate->sizeFn)(datum_l, &size_l); - item_2 = (IndexTuple) PageGetItem(page, PageGetItemId(page, seed_2)); - datum_beta = ((char *) item_2) + sizeof(IndexTupleData); - datum_r = (char *)(*rtstate->unionFn)(datum_beta, datum_beta); - (*rtstate->sizeFn)(datum_r, &size_r); - - /* - * Now split up the regions between the two seeds. An important - * property of this split algorithm is that the split vector v - * has the indices of items to be split in order in its left and - * right vectors. We exploit this property by doing a merge in - * the code that actually splits the page. - * - * For efficiency, we also place the new index tuple in this loop. - * This is handled at the very end, when we have placed all the - * existing tuples and i == maxoff + 1. - */ - - maxoff = OffsetNumberNext(maxoff); - for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) { - + + left = v->spl_left; + v->spl_nleft = 0; + right = v->spl_right; + v->spl_nright = 0; + + item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, seed_1)); + datum_alpha = ((char *) item_1) + sizeof(IndexTupleData); + datum_l = (char *) (*rtstate->unionFn) (datum_alpha, datum_alpha); + (*rtstate->sizeFn) (datum_l, &size_l); + item_2 = (IndexTuple) PageGetItem(page, PageGetItemId(page, seed_2)); + datum_beta = ((char *) item_2) + sizeof(IndexTupleData); + datum_r = (char *) (*rtstate->unionFn) (datum_beta, datum_beta); + (*rtstate->sizeFn) (datum_r, &size_r); + /* - * If we've already decided where to place this item, just - * put it on the right list. Otherwise, we need to figure - * out which page needs the least enlargement in order to - * store the item. + * Now split up the regions between the two seeds. An important + * property of this split algorithm is that the split vector v has the + * indices of items to be split in order in its left and right + * vectors. We exploit this property by doing a merge in the code + * that actually splits the page. + * + * For efficiency, we also place the new index tuple in this loop. This + * is handled at the very end, when we have placed all the existing + * tuples and i == maxoff + 1. */ - - if (i == seed_1) { - *left++ = i; - v->spl_nleft++; - continue; - } else if (i == seed_2) { - *right++ = i; - v->spl_nright++; - continue; - } - - /* okay, which page needs least enlargement? */ - if (i == maxoff) { - item_1 = itup; - } else { - item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, i)); - } - - datum_alpha = ((char *) item_1) + sizeof(IndexTupleData); - union_dl = (char *)(*rtstate->unionFn)(datum_l, datum_alpha); - union_dr = (char *)(*rtstate->unionFn)(datum_r, datum_alpha); - (*rtstate->sizeFn)(union_dl, &size_alpha); - (*rtstate->sizeFn)(union_dr, &size_beta); - - /* pick which page to add it to */ - if (size_alpha - size_l < size_beta - size_r) { - pfree(datum_l); - pfree(union_dr); - datum_l = union_dl; - size_l = size_alpha; - *left++ = i; - v->spl_nleft++; - } else { - pfree(datum_r); - pfree(union_dl); - datum_r = union_dr; - size_r = size_alpha; - *right++ = i; - v->spl_nright++; + + maxoff = OffsetNumberNext(maxoff); + for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) + { + + /* + * If we've already decided where to place this item, just put it + * on the right list. Otherwise, we need to figure out which page + * needs the least enlargement in order to store the item. + */ + + if (i == seed_1) + { + *left++ = i; + v->spl_nleft++; + continue; + } + else if (i == seed_2) + { + *right++ = i; + v->spl_nright++; + continue; + } + + /* okay, which page needs least enlargement? */ + if (i == maxoff) + { + item_1 = itup; + } + else + { + item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, i)); + } + + datum_alpha = ((char *) item_1) + sizeof(IndexTupleData); + union_dl = (char *) (*rtstate->unionFn) (datum_l, datum_alpha); + union_dr = (char *) (*rtstate->unionFn) (datum_r, datum_alpha); + (*rtstate->sizeFn) (union_dl, &size_alpha); + (*rtstate->sizeFn) (union_dr, &size_beta); + + /* pick which page to add it to */ + if (size_alpha - size_l < size_beta - size_r) + { + pfree(datum_l); + pfree(union_dr); + datum_l = union_dl; + size_l = size_alpha; + *left++ = i; + v->spl_nleft++; + } + else + { + pfree(datum_r); + pfree(union_dl); + datum_r = union_dr; + size_r = size_alpha; + *right++ = i; + v->spl_nright++; + } } - } - *left = *right = FirstOffsetNumber; /* sentinel value, see dosplit() */ - - v->spl_ldatum = datum_l; - v->spl_rdatum = datum_r; + *left = *right = FirstOffsetNumber; /* sentinel value, see dosplit() */ + + v->spl_ldatum = datum_l; + v->spl_rdatum = datum_r; } static void RTInitBuffer(Buffer b, uint32 f) { - RTreePageOpaque opaque; - Page page; - Size pageSize; - - pageSize = BufferGetPageSize(b); - - page = BufferGetPage(b); - memset(page, 0, (int) pageSize); - PageInit(page, pageSize, sizeof(RTreePageOpaqueData)); - - opaque = (RTreePageOpaque) PageGetSpecialPointer(page); - opaque->flags = f; + RTreePageOpaque opaque; + Page page; + Size pageSize; + + pageSize = BufferGetPageSize(b); + + page = BufferGetPage(b); + memset(page, 0, (int) pageSize); + PageInit(page, pageSize, sizeof(RTreePageOpaqueData)); + + opaque = (RTreePageOpaque) PageGetSpecialPointer(page); + opaque->flags = f; } -static OffsetNumber -choose(Relation r, Page p, IndexTuple it, RTSTATE *rtstate) +static OffsetNumber +choose(Relation r, Page p, IndexTuple it, RTSTATE * rtstate) { - OffsetNumber maxoff; - OffsetNumber i; - char *ud, *id; - char *datum; - float usize, dsize; - OffsetNumber which; - float which_grow; - - id = ((char *) it) + sizeof(IndexTupleData); - maxoff = PageGetMaxOffsetNumber(p); - which_grow = -1.0; - which = -1; - - for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) { - datum = (char *) PageGetItem(p, PageGetItemId(p, i)); - datum += sizeof(IndexTupleData); - (*rtstate->sizeFn)(datum, &dsize); - ud = (char *) (*rtstate->unionFn)(datum, id); - (*rtstate->sizeFn)(ud, &usize); - pfree(ud); - if (which_grow < 0 || usize - dsize < which_grow) { - which = i; - which_grow = usize - dsize; - if (which_grow == 0) - break; + OffsetNumber maxoff; + OffsetNumber i; + char *ud, + *id; + char *datum; + float usize, + dsize; + OffsetNumber which; + float which_grow; + + id = ((char *) it) + sizeof(IndexTupleData); + maxoff = PageGetMaxOffsetNumber(p); + which_grow = -1.0; + which = -1; + + for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) + { + datum = (char *) PageGetItem(p, PageGetItemId(p, i)); + datum += sizeof(IndexTupleData); + (*rtstate->sizeFn) (datum, &dsize); + ud = (char *) (*rtstate->unionFn) (datum, id); + (*rtstate->sizeFn) (ud, &usize); + pfree(ud); + if (which_grow < 0 || usize - dsize < which_grow) + { + which = i; + which_grow = usize - dsize; + if (which_grow == 0) + break; + } } - } - - return (which); + + return (which); } static int nospace(Page p, IndexTuple it) { - return (PageGetFreeSpace(p) < IndexTupleSize(it)); + return (PageGetFreeSpace(p) < IndexTupleSize(it)); } void -freestack(RTSTACK *s) +freestack(RTSTACK * s) { - RTSTACK *p; - - while (s != (RTSTACK *) NULL) { - p = s->rts_parent; - pfree(s); - s = p; - } + RTSTACK *p; + + while (s != (RTSTACK *) NULL) + { + p = s->rts_parent; + pfree(s); + s = p; + } } -char * +char * rtdelete(Relation r, ItemPointer tid) { - BlockNumber blkno; - OffsetNumber offnum; - Buffer buf; - Page page; - - /* must write-lock on delete */ - RelationSetLockForWrite(r); - - blkno = ItemPointerGetBlockNumber(tid); - offnum = ItemPointerGetOffsetNumber(tid); - - /* adjust any scans that will be affected by this deletion */ - rtadjscans(r, RTOP_DEL, blkno, offnum); - - /* delete the index tuple */ - buf = ReadBuffer(r, blkno); - page = BufferGetPage(buf); - - PageIndexTupleDelete(page, offnum); - - WriteBuffer(buf); - - /* XXX -- two-phase locking, don't release the write lock */ - return ((char *) NULL); + BlockNumber blkno; + OffsetNumber offnum; + Buffer buf; + Page page; + + /* must write-lock on delete */ + RelationSetLockForWrite(r); + + blkno = ItemPointerGetBlockNumber(tid); + offnum = ItemPointerGetOffsetNumber(tid); + + /* adjust any scans that will be affected by this deletion */ + rtadjscans(r, RTOP_DEL, blkno, offnum); + + /* delete the index tuple */ + buf = ReadBuffer(r, blkno); + page = BufferGetPage(buf); + + PageIndexTupleDelete(page, offnum); + + WriteBuffer(buf); + + /* XXX -- two-phase locking, don't release the write lock */ + return ((char *) NULL); } -static void initRtstate(RTSTATE *rtstate, Relation index) +static void +initRtstate(RTSTATE * rtstate, Relation index) { - RegProcedure union_proc, size_proc, inter_proc; - func_ptr user_fn; - int pronargs; - - union_proc = index_getprocid(index, 1, RT_UNION_PROC); - size_proc = index_getprocid(index, 1, RT_SIZE_PROC); - inter_proc = index_getprocid(index, 1, RT_INTER_PROC); - fmgr_info(union_proc, &user_fn, &pronargs); - rtstate->unionFn = user_fn; - fmgr_info(size_proc, &user_fn, &pronargs); - rtstate->sizeFn = user_fn; - fmgr_info(inter_proc, &user_fn, &pronargs); - rtstate->interFn = user_fn; - return; + RegProcedure union_proc, + size_proc, + inter_proc; + func_ptr user_fn; + int pronargs; + + union_proc = index_getprocid(index, 1, RT_UNION_PROC); + size_proc = index_getprocid(index, 1, RT_SIZE_PROC); + inter_proc = index_getprocid(index, 1, RT_INTER_PROC); + fmgr_info(union_proc, &user_fn, &pronargs); + rtstate->unionFn = user_fn; + fmgr_info(size_proc, &user_fn, &pronargs); + rtstate->sizeFn = user_fn; + fmgr_info(inter_proc, &user_fn, &pronargs); + rtstate->interFn = user_fn; + return; } #ifdef RTDEBUG @@ -914,48 +1011,52 @@ static void initRtstate(RTSTATE *rtstate, Relation index) void _rtdump(Relation r) { - Buffer buf; - Page page; - OffsetNumber offnum, maxoff; - BlockNumber blkno; - BlockNumber nblocks; - RTreePageOpaque po; - IndexTuple itup; - BlockNumber itblkno; - OffsetNumber itoffno; - char *datum; - char *itkey; - - nblocks = RelationGetNumberOfBlocks(r); - for (blkno = 0; blkno < nblocks; blkno++) { - buf = ReadBuffer(r, blkno); - page = BufferGetPage(buf); - po = (RTreePageOpaque) PageGetSpecialPointer(page); - maxoff = PageGetMaxOffsetNumber(page); - printf("Page %d maxoff %d <%s>\n", blkno, maxoff, - (po->flags & F_LEAF ? "LEAF" : "INTERNAL")); - - if (PageIsEmpty(page)) { - ReleaseBuffer(buf); - continue; - } - - for (offnum = FirstOffsetNumber; - offnum <= maxoff; - offnum = OffsetNumberNext(offnum)) { - itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum)); - itblkno = ItemPointerGetBlockNumber(&(itup->t_tid)); - itoffno = ItemPointerGetOffsetNumber(&(itup->t_tid)); - datum = ((char *) itup); - datum += sizeof(IndexTupleData); - itkey = (char *) box_out((BOX *) datum); - printf("\t[%d] size %d heap <%d,%d> key:%s\n", - offnum, IndexTupleSize(itup), itblkno, itoffno, itkey); - pfree(itkey); + Buffer buf; + Page page; + OffsetNumber offnum, + maxoff; + BlockNumber blkno; + BlockNumber nblocks; + RTreePageOpaque po; + IndexTuple itup; + BlockNumber itblkno; + OffsetNumber itoffno; + char *datum; + char *itkey; + + nblocks = RelationGetNumberOfBlocks(r); + for (blkno = 0; blkno < nblocks; blkno++) + { + buf = ReadBuffer(r, blkno); + page = BufferGetPage(buf); + po = (RTreePageOpaque) PageGetSpecialPointer(page); + maxoff = PageGetMaxOffsetNumber(page); + printf("Page %d maxoff %d <%s>\n", blkno, maxoff, + (po->flags & F_LEAF ? "LEAF" : "INTERNAL")); + + if (PageIsEmpty(page)) + { + ReleaseBuffer(buf); + continue; + } + + for (offnum = FirstOffsetNumber; + offnum <= maxoff; + offnum = OffsetNumberNext(offnum)) + { + itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum)); + itblkno = ItemPointerGetBlockNumber(&(itup->t_tid)); + itoffno = ItemPointerGetOffsetNumber(&(itup->t_tid)); + datum = ((char *) itup); + datum += sizeof(IndexTupleData); + itkey = (char *) box_out((BOX *) datum); + printf("\t[%d] size %d heap <%d,%d> key:%s\n", + offnum, IndexTupleSize(itup), itblkno, itoffno, itkey); + pfree(itkey); + } + + ReleaseBuffer(buf); } - - ReleaseBuffer(buf); - } } -#endif /* defined RTDEBUG */ +#endif /* defined RTDEBUG */ diff --git a/src/backend/access/rtree/rtscan.c b/src/backend/access/rtree/rtscan.c index bb8e1dcc719..26590059d6c 100644 --- a/src/backend/access/rtree/rtscan.c +++ b/src/backend/access/rtree/rtscan.c @@ -1,19 +1,19 @@ /*------------------------------------------------------------------------- * * rtscan.c-- - * routines to manage scans on index relations + * routines to manage scans on index relations * * Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/access/rtree/Attic/rtscan.c,v 1.10 1997/05/20 10:29:30 vadim Exp $ + * $Header: /cvsroot/pgsql/src/backend/access/rtree/Attic/rtscan.c,v 1.11 1997/09/07 04:39:24 momjian Exp $ * *------------------------------------------------------------------------- */ #include <postgres.h> - + #include <storage/bufmgr.h> #include <access/genam.h> #include <storage/lmgr.h> @@ -21,377 +21,411 @@ #include <access/rtree.h> #include <access/rtstrat.h> #ifndef HAVE_MEMMOVE -# include <regex/utils.h> +#include <regex/utils.h> #else -# include <string.h> +#include <string.h> #endif - + /* routines defined and used here */ -static void rtregscan(IndexScanDesc s); -static void rtdropscan(IndexScanDesc s); -static void rtadjone(IndexScanDesc s, int op, BlockNumber blkno, - OffsetNumber offnum); -static void adjuststack(RTSTACK *stk, BlockNumber blkno, +static void rtregscan(IndexScanDesc s); +static void rtdropscan(IndexScanDesc s); +static void +rtadjone(IndexScanDesc s, int op, BlockNumber blkno, + OffsetNumber offnum); +static void +adjuststack(RTSTACK * stk, BlockNumber blkno, OffsetNumber offnum); -static void adjustiptr(IndexScanDesc s, ItemPointer iptr, - int op, BlockNumber blkno, OffsetNumber offnum); +static void +adjustiptr(IndexScanDesc s, ItemPointer iptr, + int op, BlockNumber blkno, OffsetNumber offnum); /* - * Whenever we start an rtree scan in a backend, we register it in private - * space. Then if the rtree index gets updated, we check all registered - * scans and adjust them if the tuple they point at got moved by the - * update. We only need to do this in private space, because when we update - * an rtree we have a write lock on the tree, so no other process can have - * any locks at all on it. A single transaction can have write and read - * locks on the same object, so that's why we need to handle this case. + * Whenever we start an rtree scan in a backend, we register it in private + * space. Then if the rtree index gets updated, we check all registered + * scans and adjust them if the tuple they point at got moved by the + * update. We only need to do this in private space, because when we update + * an rtree we have a write lock on the tree, so no other process can have + * any locks at all on it. A single transaction can have write and read + * locks on the same object, so that's why we need to handle this case. */ -typedef struct RTScanListData { - IndexScanDesc rtsl_scan; - struct RTScanListData *rtsl_next; -} RTScanListData; +typedef struct RTScanListData +{ + IndexScanDesc rtsl_scan; + struct RTScanListData *rtsl_next; +} RTScanListData; -typedef RTScanListData *RTScanList; +typedef RTScanListData *RTScanList; /* pointer to list of local scans on rtrees */ static RTScanList RTScans = (RTScanList) NULL; - + IndexScanDesc rtbeginscan(Relation r, - bool fromEnd, - uint16 nkeys, - ScanKey key) + bool fromEnd, + uint16 nkeys, + ScanKey key) { - IndexScanDesc s; - - RelationSetLockForRead(r); - s = RelationGetIndexScan(r, fromEnd, nkeys, key); - rtregscan(s); - - return (s); + IndexScanDesc s; + + RelationSetLockForRead(r); + s = RelationGetIndexScan(r, fromEnd, nkeys, key); + rtregscan(s); + + return (s); } void rtrescan(IndexScanDesc s, bool fromEnd, ScanKey key) { - RTreeScanOpaque p; - RegProcedure internal_proc; - int i; - - if (!IndexScanIsValid(s)) { - elog(WARN, "rtrescan: invalid scan."); - return; - } - - /* - * Clear all the pointers. - */ - - ItemPointerSetInvalid(&s->previousItemData); - ItemPointerSetInvalid(&s->currentItemData); - ItemPointerSetInvalid(&s->nextItemData); - ItemPointerSetInvalid(&s->previousMarkData); - ItemPointerSetInvalid(&s->currentMarkData); - ItemPointerSetInvalid(&s->nextMarkData); - - /* - * Set flags. - */ - if (RelationGetNumberOfBlocks(s->relation) == 0) { - s->flags = ScanUnmarked; - } else if (fromEnd) { - s->flags = ScanUnmarked | ScanUncheckedPrevious; - } else { - s->flags = ScanUnmarked | ScanUncheckedNext; - } - - s->scanFromEnd = fromEnd; - - if (s->numberOfKeys > 0) { - memmove(s->keyData, - key, - s->numberOfKeys * sizeof(ScanKeyData)); - } - - p = (RTreeScanOpaque) s->opaque; - if (p != (RTreeScanOpaque) NULL) { - freestack(p->s_stack); - freestack(p->s_markstk); - p->s_stack = p->s_markstk = (RTSTACK *) NULL; - p->s_flags = 0x0; - for (i = 0; i < s->numberOfKeys; i++) + RTreeScanOpaque p; + RegProcedure internal_proc; + int i; + + if (!IndexScanIsValid(s)) + { + elog(WARN, "rtrescan: invalid scan."); + return; + } + + /* + * Clear all the pointers. + */ + + ItemPointerSetInvalid(&s->previousItemData); + ItemPointerSetInvalid(&s->currentItemData); + ItemPointerSetInvalid(&s->nextItemData); + ItemPointerSetInvalid(&s->previousMarkData); + ItemPointerSetInvalid(&s->currentMarkData); + ItemPointerSetInvalid(&s->nextMarkData); + + /* + * Set flags. + */ + if (RelationGetNumberOfBlocks(s->relation) == 0) + { + s->flags = ScanUnmarked; + } + else if (fromEnd) + { + s->flags = ScanUnmarked | ScanUncheckedPrevious; + } + else + { + s->flags = ScanUnmarked | ScanUncheckedNext; + } + + s->scanFromEnd = fromEnd; + + if (s->numberOfKeys > 0) { - p->s_internalKey[i].sk_argument = s->keyData[i].sk_argument; + memmove(s->keyData, + key, + s->numberOfKeys * sizeof(ScanKeyData)); } - } else { - /* initialize opaque data */ - p = (RTreeScanOpaque) palloc(sizeof(RTreeScanOpaqueData)); - p->s_stack = p->s_markstk = (RTSTACK *) NULL; - p->s_internalNKey = s->numberOfKeys; - p->s_flags = 0x0; - s->opaque = p; - if (s->numberOfKeys > 0) { - p->s_internalKey = - (ScanKey) palloc(sizeof(ScanKeyData) * s->numberOfKeys); - - /* - * Scans on internal pages use different operators than they - * do on leaf pages. For example, if the user wants all boxes - * that exactly match (x1,y1,x2,y2), then on internal pages - * we need to find all boxes that contain (x1,y1,x2,y2). - */ - - for (i = 0; i < s->numberOfKeys; i++) { - p->s_internalKey[i].sk_argument = s->keyData[i].sk_argument; - internal_proc = RTMapOperator(s->relation, - s->keyData[i].sk_attno, - s->keyData[i].sk_procedure); - ScanKeyEntryInitialize(&(p->s_internalKey[i]), - s->keyData[i].sk_flags, - s->keyData[i].sk_attno, - internal_proc, - s->keyData[i].sk_argument); - } + + p = (RTreeScanOpaque) s->opaque; + if (p != (RTreeScanOpaque) NULL) + { + freestack(p->s_stack); + freestack(p->s_markstk); + p->s_stack = p->s_markstk = (RTSTACK *) NULL; + p->s_flags = 0x0; + for (i = 0; i < s->numberOfKeys; i++) + { + p->s_internalKey[i].sk_argument = s->keyData[i].sk_argument; + } + } + else + { + /* initialize opaque data */ + p = (RTreeScanOpaque) palloc(sizeof(RTreeScanOpaqueData)); + p->s_stack = p->s_markstk = (RTSTACK *) NULL; + p->s_internalNKey = s->numberOfKeys; + p->s_flags = 0x0; + s->opaque = p; + if (s->numberOfKeys > 0) + { + p->s_internalKey = + (ScanKey) palloc(sizeof(ScanKeyData) * s->numberOfKeys); + + /* + * Scans on internal pages use different operators than they + * do on leaf pages. For example, if the user wants all boxes + * that exactly match (x1,y1,x2,y2), then on internal pages we + * need to find all boxes that contain (x1,y1,x2,y2). + */ + + for (i = 0; i < s->numberOfKeys; i++) + { + p->s_internalKey[i].sk_argument = s->keyData[i].sk_argument; + internal_proc = RTMapOperator(s->relation, + s->keyData[i].sk_attno, + s->keyData[i].sk_procedure); + ScanKeyEntryInitialize(&(p->s_internalKey[i]), + s->keyData[i].sk_flags, + s->keyData[i].sk_attno, + internal_proc, + s->keyData[i].sk_argument); + } + } } - } } void rtmarkpos(IndexScanDesc s) { - RTreeScanOpaque p; - RTSTACK *o, *n, *tmp; - - s->currentMarkData = s->currentItemData; - p = (RTreeScanOpaque) s->opaque; - if (p->s_flags & RTS_CURBEFORE) - p->s_flags |= RTS_MRKBEFORE; - else - p->s_flags &= ~RTS_MRKBEFORE; - - o = (RTSTACK *) NULL; - n = p->s_stack; - - /* copy the parent stack from the current item data */ - while (n != (RTSTACK *) NULL) { - tmp = (RTSTACK *) palloc(sizeof(RTSTACK)); - tmp->rts_child = n->rts_child; - tmp->rts_blk = n->rts_blk; - tmp->rts_parent = o; - o = tmp; - n = n->rts_parent; - } - - freestack(p->s_markstk); - p->s_markstk = o; + RTreeScanOpaque p; + RTSTACK *o, + *n, + *tmp; + + s->currentMarkData = s->currentItemData; + p = (RTreeScanOpaque) s->opaque; + if (p->s_flags & RTS_CURBEFORE) + p->s_flags |= RTS_MRKBEFORE; + else + p->s_flags &= ~RTS_MRKBEFORE; + + o = (RTSTACK *) NULL; + n = p->s_stack; + + /* copy the parent stack from the current item data */ + while (n != (RTSTACK *) NULL) + { + tmp = (RTSTACK *) palloc(sizeof(RTSTACK)); + tmp->rts_child = n->rts_child; + tmp->rts_blk = n->rts_blk; + tmp->rts_parent = o; + o = tmp; + n = n->rts_parent; + } + + freestack(p->s_markstk); + p->s_markstk = o; } void rtrestrpos(IndexScanDesc s) { - RTreeScanOpaque p; - RTSTACK *o, *n, *tmp; - - s->currentItemData = s->currentMarkData; - p = (RTreeScanOpaque) s->opaque; - if (p->s_flags & RTS_MRKBEFORE) - p->s_flags |= RTS_CURBEFORE; - else - p->s_flags &= ~RTS_CURBEFORE; - - o = (RTSTACK *) NULL; - n = p->s_markstk; - - /* copy the parent stack from the current item data */ - while (n != (RTSTACK *) NULL) { - tmp = (RTSTACK *) palloc(sizeof(RTSTACK)); - tmp->rts_child = n->rts_child; - tmp->rts_blk = n->rts_blk; - tmp->rts_parent = o; - o = tmp; - n = n->rts_parent; - } - - freestack(p->s_stack); - p->s_stack = o; + RTreeScanOpaque p; + RTSTACK *o, + *n, + *tmp; + + s->currentItemData = s->currentMarkData; + p = (RTreeScanOpaque) s->opaque; + if (p->s_flags & RTS_MRKBEFORE) + p->s_flags |= RTS_CURBEFORE; + else + p->s_flags &= ~RTS_CURBEFORE; + + o = (RTSTACK *) NULL; + n = p->s_markstk; + + /* copy the parent stack from the current item data */ + while (n != (RTSTACK *) NULL) + { + tmp = (RTSTACK *) palloc(sizeof(RTSTACK)); + tmp->rts_child = n->rts_child; + tmp->rts_blk = n->rts_blk; + tmp->rts_parent = o; + o = tmp; + n = n->rts_parent; + } + + freestack(p->s_stack); + p->s_stack = o; } void rtendscan(IndexScanDesc s) { - RTreeScanOpaque p; - - p = (RTreeScanOpaque) s->opaque; - - if (p != (RTreeScanOpaque) NULL) { - freestack(p->s_stack); - freestack(p->s_markstk); - pfree (s->opaque); - } - - rtdropscan(s); - /* XXX don't unset read lock -- two-phase locking */ + RTreeScanOpaque p; + + p = (RTreeScanOpaque) s->opaque; + + if (p != (RTreeScanOpaque) NULL) + { + freestack(p->s_stack); + freestack(p->s_markstk); + pfree(s->opaque); + } + + rtdropscan(s); + /* XXX don't unset read lock -- two-phase locking */ } static void rtregscan(IndexScanDesc s) { - RTScanList l; - - l = (RTScanList) palloc(sizeof(RTScanListData)); - l->rtsl_scan = s; - l->rtsl_next = RTScans; - RTScans = l; + RTScanList l; + + l = (RTScanList) palloc(sizeof(RTScanListData)); + l->rtsl_scan = s; + l->rtsl_next = RTScans; + RTScans = l; } static void rtdropscan(IndexScanDesc s) { - RTScanList l; - RTScanList prev; - - prev = (RTScanList) NULL; - - for (l = RTScans; - l != (RTScanList) NULL && l->rtsl_scan != s; - l = l->rtsl_next) { - prev = l; - } - - if (l == (RTScanList) NULL) - elog(WARN, "rtree scan list corrupted -- cannot find 0x%lx", s); - - if (prev == (RTScanList) NULL) - RTScans = l->rtsl_next; - else - prev->rtsl_next = l->rtsl_next; - - pfree(l); + RTScanList l; + RTScanList prev; + + prev = (RTScanList) NULL; + + for (l = RTScans; + l != (RTScanList) NULL && l->rtsl_scan != s; + l = l->rtsl_next) + { + prev = l; + } + + if (l == (RTScanList) NULL) + elog(WARN, "rtree scan list corrupted -- cannot find 0x%lx", s); + + if (prev == (RTScanList) NULL) + RTScans = l->rtsl_next; + else + prev->rtsl_next = l->rtsl_next; + + pfree(l); } void rtadjscans(Relation r, int op, BlockNumber blkno, OffsetNumber offnum) { - RTScanList l; - Oid relid; - - relid = r->rd_id; - for (l = RTScans; l != (RTScanList) NULL; l = l->rtsl_next) { - if (l->rtsl_scan->relation->rd_id == relid) - rtadjone(l->rtsl_scan, op, blkno, offnum); - } + RTScanList l; + Oid relid; + + relid = r->rd_id; + for (l = RTScans; l != (RTScanList) NULL; l = l->rtsl_next) + { + if (l->rtsl_scan->relation->rd_id == relid) + rtadjone(l->rtsl_scan, op, blkno, offnum); + } } /* - * rtadjone() -- adjust one scan for update. + * rtadjone() -- adjust one scan for update. * - * By here, the scan passed in is on a modified relation. Op tells - * us what the modification is, and blkno and offind tell us what - * block and offset index were affected. This routine checks the - * current and marked positions, and the current and marked stacks, - * to see if any stored location needs to be changed because of the - * update. If so, we make the change here. + * By here, the scan passed in is on a modified relation. Op tells + * us what the modification is, and blkno and offind tell us what + * block and offset index were affected. This routine checks the + * current and marked positions, and the current and marked stacks, + * to see if any stored location needs to be changed because of the + * update. If so, we make the change here. */ static void rtadjone(IndexScanDesc s, - int op, - BlockNumber blkno, - OffsetNumber offnum) + int op, + BlockNumber blkno, + OffsetNumber offnum) { - RTreeScanOpaque so; - - adjustiptr(s, &(s->currentItemData), op, blkno, offnum); - adjustiptr(s, &(s->currentMarkData), op, blkno, offnum); - - so = (RTreeScanOpaque) s->opaque; - - if (op == RTOP_SPLIT) { - adjuststack(so->s_stack, blkno, offnum); - adjuststack(so->s_markstk, blkno, offnum); - } + RTreeScanOpaque so; + + adjustiptr(s, &(s->currentItemData), op, blkno, offnum); + adjustiptr(s, &(s->currentMarkData), op, blkno, offnum); + + so = (RTreeScanOpaque) s->opaque; + + if (op == RTOP_SPLIT) + { + adjuststack(so->s_stack, blkno, offnum); + adjuststack(so->s_markstk, blkno, offnum); + } } /* - * adjustiptr() -- adjust current and marked item pointers in the scan + * adjustiptr() -- adjust current and marked item pointers in the scan * - * Depending on the type of update and the place it happened, we - * need to do nothing, to back up one record, or to start over on - * the same page. + * Depending on the type of update and the place it happened, we + * need to do nothing, to back up one record, or to start over on + * the same page. */ static void adjustiptr(IndexScanDesc s, - ItemPointer iptr, - int op, - BlockNumber blkno, - OffsetNumber offnum) + ItemPointer iptr, + int op, + BlockNumber blkno, + OffsetNumber offnum) { - OffsetNumber curoff; - RTreeScanOpaque so; - - if (ItemPointerIsValid(iptr)) { - if (ItemPointerGetBlockNumber(iptr) == blkno) { - curoff = ItemPointerGetOffsetNumber(iptr); - so = (RTreeScanOpaque) s->opaque; - - switch (op) { - case RTOP_DEL: - /* back up one if we need to */ - if (curoff >= offnum) { - - if (curoff > FirstOffsetNumber) { - /* just adjust the item pointer */ - ItemPointerSet(iptr, blkno, OffsetNumberPrev(curoff)); - } else { - /* remember that we're before the current tuple */ - ItemPointerSet(iptr, blkno, FirstOffsetNumber); - if (iptr == &(s->currentItemData)) - so->s_flags |= RTS_CURBEFORE; - else - so->s_flags |= RTS_MRKBEFORE; - } + OffsetNumber curoff; + RTreeScanOpaque so; + + if (ItemPointerIsValid(iptr)) + { + if (ItemPointerGetBlockNumber(iptr) == blkno) + { + curoff = ItemPointerGetOffsetNumber(iptr); + so = (RTreeScanOpaque) s->opaque; + + switch (op) + { + case RTOP_DEL: + /* back up one if we need to */ + if (curoff >= offnum) + { + + if (curoff > FirstOffsetNumber) + { + /* just adjust the item pointer */ + ItemPointerSet(iptr, blkno, OffsetNumberPrev(curoff)); + } + else + { + /* remember that we're before the current tuple */ + ItemPointerSet(iptr, blkno, FirstOffsetNumber); + if (iptr == &(s->currentItemData)) + so->s_flags |= RTS_CURBEFORE; + else + so->s_flags |= RTS_MRKBEFORE; + } + } + break; + + case RTOP_SPLIT: + /* back to start of page on split */ + ItemPointerSet(iptr, blkno, FirstOffsetNumber); + if (iptr == &(s->currentItemData)) + so->s_flags &= ~RTS_CURBEFORE; + else + so->s_flags &= ~RTS_MRKBEFORE; + break; + + default: + elog(WARN, "Bad operation in rtree scan adjust: %d", op); + } } - break; - - case RTOP_SPLIT: - /* back to start of page on split */ - ItemPointerSet(iptr, blkno, FirstOffsetNumber); - if (iptr == &(s->currentItemData)) - so->s_flags &= ~RTS_CURBEFORE; - else - so->s_flags &= ~RTS_MRKBEFORE; - break; - - default: - elog(WARN, "Bad operation in rtree scan adjust: %d", op); - } } - } } /* - * adjuststack() -- adjust the supplied stack for a split on a page in - * the index we're scanning. + * adjuststack() -- adjust the supplied stack for a split on a page in + * the index we're scanning. * - * If a page on our parent stack has split, we need to back up to the - * beginning of the page and rescan it. The reason for this is that - * the split algorithm for rtrees doesn't order tuples in any useful - * way on a single page. This means on that a split, we may wind up - * looking at some heap tuples more than once. This is handled in the - * access method update code for heaps; if we've modified the tuple we - * are looking at already in this transaction, we ignore the update - * request. + * If a page on our parent stack has split, we need to back up to the + * beginning of the page and rescan it. The reason for this is that + * the split algorithm for rtrees doesn't order tuples in any useful + * way on a single page. This means on that a split, we may wind up + * looking at some heap tuples more than once. This is handled in the + * access method update code for heaps; if we've modified the tuple we + * are looking at already in this transaction, we ignore the update + * request. */ /*ARGSUSED*/ static void -adjuststack(RTSTACK *stk, - BlockNumber blkno, - OffsetNumber offnum) +adjuststack(RTSTACK * stk, + BlockNumber blkno, + OffsetNumber offnum) { - while (stk != (RTSTACK *) NULL) { - if (stk->rts_blk == blkno) - stk->rts_child = FirstOffsetNumber; - - stk = stk->rts_parent; - } + while (stk != (RTSTACK *) NULL) + { + if (stk->rts_blk == blkno) + stk->rts_child = FirstOffsetNumber; + + stk = stk->rts_parent; + } } diff --git a/src/backend/access/rtree/rtstrat.c b/src/backend/access/rtree/rtstrat.c index 7025a30999d..c71059d3f09 100644 --- a/src/backend/access/rtree/rtstrat.c +++ b/src/backend/access/rtree/rtstrat.c @@ -1,241 +1,243 @@ /*------------------------------------------------------------------------- * * rtstrat.c-- - * strategy map data for rtrees. + * strategy map data for rtrees. * * Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/access/rtree/Attic/rtstrat.c,v 1.6 1997/08/19 21:29:52 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/access/rtree/Attic/rtstrat.c,v 1.7 1997/09/07 04:39:26 momjian Exp $ * *------------------------------------------------------------------------- */ #include <postgres.h> - + #include <utils/rel.h> #include <access/rtree.h> #include <access/istrat.h> -static StrategyNumber RelationGetRTStrategy(Relation r, - AttrNumber attnum, RegProcedure proc); +static StrategyNumber +RelationGetRTStrategy(Relation r, + AttrNumber attnum, RegProcedure proc); /* - * Note: negate, commute, and negatecommute all assume that operators are - * ordered as follows in the strategy map: + * Note: negate, commute, and negatecommute all assume that operators are + * ordered as follows in the strategy map: * - * left, left-or-overlap, overlap, right-or-overlap, right, same, - * contains, contained-by + * left, left-or-overlap, overlap, right-or-overlap, right, same, + * contains, contained-by * - * The negate, commute, and negatecommute arrays are used by the planner - * to plan indexed scans over data that appears in the qualificiation in - * a boolean negation, or whose operands appear in the wrong order. For - * example, if the operator "<%" means "contains", and the user says + * The negate, commute, and negatecommute arrays are used by the planner + * to plan indexed scans over data that appears in the qualificiation in + * a boolean negation, or whose operands appear in the wrong order. For + * example, if the operator "<%" means "contains", and the user says * - * where not rel.box <% "(10,10,20,20)"::box + * where not rel.box <% "(10,10,20,20)"::box * - * the planner can plan an index scan by noting that rtree indices have - * an operator in their operator class for negating <%. + * the planner can plan an index scan by noting that rtree indices have + * an operator in their operator class for negating <%. * - * Similarly, if the user says something like + * Similarly, if the user says something like * - * where "(10,10,20,20)"::box <% rel.box + * where "(10,10,20,20)"::box <% rel.box * - * the planner can see that the rtree index on rel.box has an operator in - * its opclass for commuting <%, and plan the scan using that operator. - * This added complexity in the access methods makes the planner a lot easier - * to write. + * the planner can see that the rtree index on rel.box has an operator in + * its opclass for commuting <%, and plan the scan using that operator. + * This added complexity in the access methods makes the planner a lot easier + * to write. */ /* if a op b, what operator tells us if (not a op b)? */ -static StrategyNumber RTNegate[RTNStrategies] = { - InvalidStrategy, - InvalidStrategy, - InvalidStrategy, - InvalidStrategy, - InvalidStrategy, - InvalidStrategy, - InvalidStrategy, - InvalidStrategy - }; +static StrategyNumber RTNegate[RTNStrategies] = { + InvalidStrategy, + InvalidStrategy, + InvalidStrategy, + InvalidStrategy, + InvalidStrategy, + InvalidStrategy, + InvalidStrategy, + InvalidStrategy +}; /* if a op_1 b, what is the operator op_2 such that b op_2 a? */ -static StrategyNumber RTCommute[RTNStrategies] = { - InvalidStrategy, - InvalidStrategy, - InvalidStrategy, - InvalidStrategy, - InvalidStrategy, - InvalidStrategy, - InvalidStrategy, - InvalidStrategy - }; +static StrategyNumber RTCommute[RTNStrategies] = { + InvalidStrategy, + InvalidStrategy, + InvalidStrategy, + InvalidStrategy, + InvalidStrategy, + InvalidStrategy, + InvalidStrategy, + InvalidStrategy +}; /* if a op_1 b, what is the operator op_2 such that (b !op_2 a)? */ -static StrategyNumber RTNegateCommute[RTNStrategies] = { - InvalidStrategy, - InvalidStrategy, - InvalidStrategy, - InvalidStrategy, - InvalidStrategy, - InvalidStrategy, - InvalidStrategy, - InvalidStrategy - }; +static StrategyNumber RTNegateCommute[RTNStrategies] = { + InvalidStrategy, + InvalidStrategy, + InvalidStrategy, + InvalidStrategy, + InvalidStrategy, + InvalidStrategy, + InvalidStrategy, + InvalidStrategy +}; /* - * Now do the TermData arrays. These exist in case the user doesn't give - * us a full set of operators for a particular operator class. The idea - * is that by making multiple comparisons using any one of the supplied - * operators, we can decide whether two n-dimensional polygons are equal. - * For example, if a contains b and b contains a, we may conclude that - * a and b are equal. - * - * The presence of the TermData arrays in all this is a historical accident. - * Early in the development of the POSTGRES access methods, it was believed - * that writing functions was harder than writing arrays. This is wrong; - * TermData is hard to understand and hard to get right. In general, when - * someone populates a new operator class, the populate it completely. If - * Mike Hirohama had forced Cimarron Taylor to populate the strategy map - * for btree int2_ops completely in 1988, you wouldn't have to deal with - * all this now. Too bad for you. - * - * Since you can't necessarily do this in all cases (for example, you can't - * do it given only "intersects" or "disjoint"), TermData arrays for some - * operators don't appear below. - * - * Note that if you DO supply all the operators required in a given opclass - * by inserting them into the pg_opclass system catalog, you can get away - * without doing all this TermData stuff. Since the rtree code is intended - * to be a reference for access method implementors, I'm doing TermData - * correctly here. - * - * Note on style: these are all actually of type StrategyTermData, but - * since those have variable-length data at the end of the struct we can't - * properly initialize them if we declare them to be what they are. + * Now do the TermData arrays. These exist in case the user doesn't give + * us a full set of operators for a particular operator class. The idea + * is that by making multiple comparisons using any one of the supplied + * operators, we can decide whether two n-dimensional polygons are equal. + * For example, if a contains b and b contains a, we may conclude that + * a and b are equal. + * + * The presence of the TermData arrays in all this is a historical accident. + * Early in the development of the POSTGRES access methods, it was believed + * that writing functions was harder than writing arrays. This is wrong; + * TermData is hard to understand and hard to get right. In general, when + * someone populates a new operator class, the populate it completely. If + * Mike Hirohama had forced Cimarron Taylor to populate the strategy map + * for btree int2_ops completely in 1988, you wouldn't have to deal with + * all this now. Too bad for you. + * + * Since you can't necessarily do this in all cases (for example, you can't + * do it given only "intersects" or "disjoint"), TermData arrays for some + * operators don't appear below. + * + * Note that if you DO supply all the operators required in a given opclass + * by inserting them into the pg_opclass system catalog, you can get away + * without doing all this TermData stuff. Since the rtree code is intended + * to be a reference for access method implementors, I'm doing TermData + * correctly here. + * + * Note on style: these are all actually of type StrategyTermData, but + * since those have variable-length data at the end of the struct we can't + * properly initialize them if we declare them to be what they are. */ /* if you only have "contained-by", how do you determine equality? */ -static uint16 RTContainedByTermData[] = { - 2, /* make two comparisons */ - RTContainedByStrategyNumber, /* use "a contained-by b" */ - 0x0, /* without any magic */ - RTContainedByStrategyNumber, /* then use contained-by, */ - SK_COMMUTE /* swapping a and b */ - }; +static uint16 RTContainedByTermData[] = { + 2, /* make two comparisons */ + RTContainedByStrategyNumber,/* use "a contained-by b" */ + 0x0, /* without any magic */ + RTContainedByStrategyNumber,/* then use contained-by, */ + SK_COMMUTE /* swapping a and b */ +}; /* if you only have "contains", how do you determine equality? */ -static uint16 RTContainsTermData[] = { - 2, /* make two comparisons */ - RTContainsStrategyNumber, /* use "a contains b" */ - 0x0, /* without any magic */ - RTContainsStrategyNumber, /* then use contains again, */ - SK_COMMUTE /* swapping a and b */ - }; +static uint16 RTContainsTermData[] = { + 2, /* make two comparisons */ + RTContainsStrategyNumber, /* use "a contains b" */ + 0x0, /* without any magic */ + RTContainsStrategyNumber, /* then use contains again, */ + SK_COMMUTE /* swapping a and b */ +}; /* now put all that together in one place for the planner */ static StrategyTerm RTEqualExpressionData[] = { - (StrategyTerm) RTContainedByTermData, - (StrategyTerm) RTContainsTermData, - NULL - }; + (StrategyTerm) RTContainedByTermData, + (StrategyTerm) RTContainsTermData, + NULL +}; /* - * If you were sufficiently attentive to detail, you would go through - * the ExpressionData pain above for every one of the seven strategies - * we defined. I am not. Now we declare the StrategyEvaluationData - * structure that gets shipped around to help the planner and the access - * method decide what sort of scan it should do, based on (a) what the - * user asked for, (b) what operators are defined for a particular opclass, - * and (c) the reams of information we supplied above. - * - * The idea of all of this initialized data is to make life easier on the - * user when he defines a new operator class to use this access method. - * By filling in all the data, we let him get away with leaving holes in his - * operator class, and still let him use the index. The added complexity - * in the access methods just isn't worth the trouble, though. + * If you were sufficiently attentive to detail, you would go through + * the ExpressionData pain above for every one of the seven strategies + * we defined. I am not. Now we declare the StrategyEvaluationData + * structure that gets shipped around to help the planner and the access + * method decide what sort of scan it should do, based on (a) what the + * user asked for, (b) what operators are defined for a particular opclass, + * and (c) the reams of information we supplied above. + * + * The idea of all of this initialized data is to make life easier on the + * user when he defines a new operator class to use this access method. + * By filling in all the data, we let him get away with leaving holes in his + * operator class, and still let him use the index. The added complexity + * in the access methods just isn't worth the trouble, though. */ static StrategyEvaluationData RTEvaluationData = { - RTNStrategies, /* # of strategies */ - (StrategyTransformMap) RTNegate, /* how to do (not qual) */ - (StrategyTransformMap) RTCommute, /* how to swap operands */ - (StrategyTransformMap) RTNegateCommute, /* how to do both */ - { - NULL, /* express left */ - NULL, /* express overleft */ - NULL, /* express over */ - NULL, /* express overright */ - NULL, /* express right */ - (StrategyExpression) RTEqualExpressionData, /* express same */ - NULL, /* express contains */ - NULL, /* express contained-by */ - NULL, - NULL, - NULL - } + RTNStrategies, /* # of strategies */ + (StrategyTransformMap) RTNegate, /* how to do (not qual) */ + (StrategyTransformMap) RTCommute, /* how to swap operands */ + (StrategyTransformMap) RTNegateCommute, /* how to do both */ + { + NULL, /* express left */ + NULL, /* express overleft */ + NULL, /* express over */ + NULL, /* express overright */ + NULL, /* express right */ + (StrategyExpression) RTEqualExpressionData, /* express same */ + NULL, /* express contains */ + NULL, /* express contained-by */ + NULL, + NULL, + NULL + } }; /* - * Okay, now something peculiar to rtrees that doesn't apply to most other - * indexing structures: When we're searching a tree for a given value, we - * can't do the same sorts of comparisons on internal node entries as we - * do at leaves. The reason is that if we're looking for (say) all boxes - * that are the same as (0,0,10,10), then we need to find all leaf pages - * that overlap that region. So internally we search for overlap, and at - * the leaf we search for equality. - * - * This array maps leaf search operators to the internal search operators. - * We assume the normal ordering on operators: - * - * left, left-or-overlap, overlap, right-or-overlap, right, same, - * contains, contained-by + * Okay, now something peculiar to rtrees that doesn't apply to most other + * indexing structures: When we're searching a tree for a given value, we + * can't do the same sorts of comparisons on internal node entries as we + * do at leaves. The reason is that if we're looking for (say) all boxes + * that are the same as (0,0,10,10), then we need to find all leaf pages + * that overlap that region. So internally we search for overlap, and at + * the leaf we search for equality. + * + * This array maps leaf search operators to the internal search operators. + * We assume the normal ordering on operators: + * + * left, left-or-overlap, overlap, right-or-overlap, right, same, + * contains, contained-by */ static StrategyNumber RTOperMap[RTNStrategies] = { - RTOverLeftStrategyNumber, - RTOverLeftStrategyNumber, - RTOverlapStrategyNumber, - RTOverRightStrategyNumber, - RTOverRightStrategyNumber, - RTContainsStrategyNumber, - RTContainsStrategyNumber, - RTOverlapStrategyNumber - }; + RTOverLeftStrategyNumber, + RTOverLeftStrategyNumber, + RTOverlapStrategyNumber, + RTOverRightStrategyNumber, + RTOverRightStrategyNumber, + RTContainsStrategyNumber, + RTContainsStrategyNumber, + RTOverlapStrategyNumber +}; -static StrategyNumber +static StrategyNumber RelationGetRTStrategy(Relation r, - AttrNumber attnum, - RegProcedure proc) + AttrNumber attnum, + RegProcedure proc) { - return (RelationGetStrategy(r, attnum, &RTEvaluationData, proc)); + return (RelationGetStrategy(r, attnum, &RTEvaluationData, proc)); } #ifdef NOT_USED bool RelationInvokeRTStrategy(Relation r, - AttrNumber attnum, - StrategyNumber s, - Datum left, - Datum right) + AttrNumber attnum, + StrategyNumber s, + Datum left, + Datum right) { - return (RelationInvokeStrategy(r, &RTEvaluationData, attnum, s, - left, right)); + return (RelationInvokeStrategy(r, &RTEvaluationData, attnum, s, + left, right)); } + #endif RegProcedure RTMapOperator(Relation r, - AttrNumber attnum, - RegProcedure proc) + AttrNumber attnum, + RegProcedure proc) { - StrategyNumber procstrat; - StrategyMap strategyMap; - - procstrat = RelationGetRTStrategy(r, attnum, proc); - strategyMap = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(r), - RTNStrategies, - attnum); - - return (strategyMap->entry[RTOperMap[procstrat - 1] - 1].sk_procedure); + StrategyNumber procstrat; + StrategyMap strategyMap; + + procstrat = RelationGetRTStrategy(r, attnum, proc); + strategyMap = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(r), + RTNStrategies, + attnum); + + return (strategyMap->entry[RTOperMap[procstrat - 1] - 1].sk_procedure); } |