root / hw / hw2 / MyStuff / gist_private.h

Revision 54, 10.5 kB (checked in by joeh, 4 years ago)

Better comments!

Line 
1/*-------------------------------------------------------------------------
2 *
3 * gist_private.h
4 *        private declarations for GiST -- declarations related to the
5 *        internal implementation of GiST, not the public API
6 *
7 * Portions Copyright (c) 1996-2006, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
9 *
10 * $PostgreSQL: pgsql/src/include/access/gist_private.h,v 1.24 2006/10/04 00:30:07 momjian Exp $
11 *
12 *-------------------------------------------------------------------------
13 */
14#ifndef GIST_PRIVATE_H
15#define GIST_PRIVATE_H
16
17#include "access/gist.h"
18#include "access/itup.h"
19#include "access/xlog.h"
20#include "access/xlogdefs.h"
21#include "fmgr.h"
22
23#define GIST_UNLOCK BUFFER_LOCK_UNLOCK
24#define GIST_SHARE      BUFFER_LOCK_SHARE
25#define GIST_EXCLUSIVE  BUFFER_LOCK_EXCLUSIVE
26
27
28/*
29 * XXX old comment!!!
30 * When we descend a tree, we keep a stack of parent pointers. This
31 * allows us to follow a chain of internal node points until we reach
32 * a leaf node, and then back up the stack to re-examine the internal
33 * nodes.
34 *
35 * 'parent' is the previous stack entry -- i.e. the node we arrived
36 * from. 'block' is the node's block number. 'offset' is the offset in
37 * the node's page that we stopped at (i.e. we followed the child
38 * pointer located at the specified offset).
39 */
40typedef struct GISTSearchStack
41{
42        struct GISTSearchStack *next;
43        BlockNumber block;
44        /* to identify page changed */
45        GistNSN         lsn;
46        /* to recognize split occured */
47        GistNSN         parentlsn;
48} GISTSearchStack;
49
50
51/*
52 * GiST priority queue for search traversal.  Priority is defined by a
53 * user-specified mindist metric.  For now, a naive linked-list
54 * implementation, should be replaced with a smarter heap
55*/
56typedef struct GISTPQ
57{
58  /* CS186 HW2: fill me in! */
59} GISTPQ;
60
61typedef struct GISTSTATE
62{
63        FmgrInfo        consistentFn[INDEX_MAX_KEYS];
64        FmgrInfo        unionFn[INDEX_MAX_KEYS];
65        FmgrInfo        compressFn[INDEX_MAX_KEYS];
66        FmgrInfo        decompressFn[INDEX_MAX_KEYS];
67        FmgrInfo        penaltyFn[INDEX_MAX_KEYS];
68        FmgrInfo        picksplitFn[INDEX_MAX_KEYS];
69        FmgrInfo        equalFn[INDEX_MAX_KEYS];
70  FmgrInfo  distanceFn[INDEX_MAX_KEYS];
71
72        TupleDesc       tupdesc;
73} GISTSTATE;
74
75/*
76 *      When we're doing a scan, we need to keep track of the parent stack
77 *      for the marked and current items.
78 */
79typedef struct GISTScanOpaqueData
80{
81        GISTSearchStack *stack;
82        GISTSearchStack *markstk;
83        uint16          flags;
84        GISTSTATE  *giststate;
85        MemoryContext tempCxt;
86        Buffer          curbuf;
87        Buffer          markbuf;
88        GISTPQ      *pq;
89} GISTScanOpaqueData;
90
91typedef GISTScanOpaqueData *GISTScanOpaque;
92
93/* XLog stuff */
94extern const XLogRecPtr XLogRecPtrForTemp;
95
96#define XLOG_GIST_PAGE_UPDATE           0x00
97#define XLOG_GIST_NEW_ROOT                      0x20
98#define XLOG_GIST_PAGE_SPLIT            0x30
99#define XLOG_GIST_INSERT_COMPLETE       0x40
100#define XLOG_GIST_CREATE_INDEX          0x50
101#define XLOG_GIST_PAGE_DELETE           0x60
102
103typedef struct gistxlogPageUpdate
104{
105        RelFileNode node;
106        BlockNumber blkno;
107
108        /*
109         * It used to identify completeness of insert. Sets to leaf itup
110         */
111        ItemPointerData key;
112
113        /* number of deleted offsets */
114        uint16          ntodelete;
115
116        /*
117         * follow: 1. todelete OffsetNumbers 2. tuples to insert
118         */
119} gistxlogPageUpdate;
120
121typedef struct gistxlogPageSplit
122{
123        RelFileNode node;
124        BlockNumber origblkno;          /* splitted page */
125        bool            origleaf;               /* was splitted page a leaf page? */
126        uint16          npage;
127
128        /* see comments on gistxlogPageUpdate */
129        ItemPointerData key;
130
131        /*
132         * follow: 1. gistxlogPage and array of IndexTupleData per page
133         */
134} gistxlogPageSplit;
135
136typedef struct gistxlogPage
137{
138        BlockNumber blkno;
139        int                     num;                    /* number of index tuples following */
140} gistxlogPage;
141
142typedef struct gistxlogInsertComplete
143{
144        RelFileNode node;
145        /* follows ItemPointerData key to clean */
146} gistxlogInsertComplete;
147
148typedef struct gistxlogPageDelete
149{
150        RelFileNode node;
151        BlockNumber blkno;
152} gistxlogPageDelete;
153
154/* SplitedPageLayout - gistSplit function result */
155typedef struct SplitedPageLayout
156{
157        gistxlogPage block;
158        IndexTupleData *list;
159        int                     lenlist;
160        IndexTuple      itup;                   /* union key for page */
161        Page            page;                   /* to operate */
162        Buffer          buffer;                 /* to write after all proceed */
163
164        struct SplitedPageLayout *next;
165} SplitedPageLayout;
166
167/*
168 * GISTInsertStack used for locking buffers and transfer arguments during
169 * insertion
170 */
171
172typedef struct GISTInsertStack
173{
174        /* current page */
175        BlockNumber blkno;
176        Buffer          buffer;
177        Page            page;
178
179        /*
180         * log sequence number from page->lsn to recognize page update  and
181         * compare it with page's nsn to recognize page split
182         */
183        GistNSN         lsn;
184
185        /* child's offset */
186        OffsetNumber childoffnum;
187
188        /* pointer to parent and child */
189        struct GISTInsertStack *parent;
190        struct GISTInsertStack *child;
191
192        /* for gistFindPath */
193        struct GISTInsertStack *next;
194} GISTInsertStack;
195
196typedef struct GistSplitVector
197{
198        GIST_SPLITVEC splitVector;      /* to/from PickSplit method */
199
200        Datum           spl_lattr[INDEX_MAX_KEYS];              /* Union of subkeys in
201                                                                                                 * spl_left */
202        bool            spl_lisnull[INDEX_MAX_KEYS];
203        bool            spl_leftvalid;
204
205        Datum           spl_rattr[INDEX_MAX_KEYS];              /* Union of subkeys in
206                                                                                                 * spl_right */
207        bool            spl_risnull[INDEX_MAX_KEYS];
208        bool            spl_rightvalid;
209
210        bool       *spl_equiv;          /* equivalent tuples which can be freely
211                                                                 * distributed between left and right pages */
212} GistSplitVector;
213
214#define XLogRecPtrIsInvalid( r )        ( (r).xlogid == 0 && (r).xrecoff == 0 )
215
216typedef struct
217{
218        Relation        r;
219        IndexTuple *itup;                       /* in/out, points to compressed entry */
220        int                     ituplen;                /* length of itup */
221        Size            freespace;              /* free space to be left */
222        GISTInsertStack *stack;
223        bool            needInsertComplete;
224
225        /* pointer to heap tuple */
226        ItemPointerData key;
227} GISTInsertState;
228
229/*
230 * When we're doing a scan and updating a tree at the same time, the
231 * updates may affect the scan.  We use the flags entry of the scan's
232 * opaque space to record our actual position in response to updates
233 * that we can't handle simply by adjusting pointers.
234 */
235#define GS_CURBEFORE    ((uint16) (1 << 0))
236#define GS_MRKBEFORE    ((uint16) (1 << 1))
237
238/* root page of a gist index */
239#define GIST_ROOT_BLKNO                         0
240
241/*
242 * mark tuples on inner pages during recovery
243 */
244#define TUPLE_IS_VALID          0xffff
245#define TUPLE_IS_INVALID        0xfffe
246
247#define  GistTupleIsInvalid(itup)       ( ItemPointerGetOffsetNumber( &((itup)->t_tid) ) == TUPLE_IS_INVALID )
248#define  GistTupleSetValid(itup)        ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_VALID )
249#define  GistTupleSetInvalid(itup)      ItemPointerSetOffsetNumber( &((itup)->t_tid), TUPLE_IS_INVALID )
250
251/* gist.c */
252extern Datum gistbuild(PG_FUNCTION_ARGS);
253extern Datum gistinsert(PG_FUNCTION_ARGS);
254extern MemoryContext createTempGistContext(void);
255extern void initGISTstate(GISTSTATE *giststate, Relation index);
256extern void freeGISTstate(GISTSTATE *giststate);
257extern void gistmakedeal(GISTInsertState *state, GISTSTATE *giststate);
258extern void gistnewroot(Relation r, Buffer buffer, IndexTuple *itup, int len, ItemPointer key);
259
260extern SplitedPageLayout *gistSplit(Relation r, Page page, IndexTuple *itup,
261                  int len, GISTSTATE *giststate);
262
263extern GISTInsertStack *gistFindPath(Relation r, BlockNumber child);
264
265/* gistxlog.c */
266extern void gist_redo(XLogRecPtr lsn, XLogRecord *record);
267extern void gist_desc(StringInfo buf, uint8 xl_info, char *rec);
268extern void gist_xlog_startup(void);
269extern void gist_xlog_cleanup(void);
270extern bool gist_safe_restartpoint(void);
271extern IndexTuple gist_form_invalid_tuple(BlockNumber blkno);
272
273extern XLogRecData *formUpdateRdata(RelFileNode node, Buffer buffer,
274                                OffsetNumber *todelete, int ntodelete,
275                                IndexTuple *itup, int ituplen, ItemPointer key);
276
277extern XLogRecData *formSplitRdata(RelFileNode node,
278                           BlockNumber blkno, bool page_is_leaf,
279                           ItemPointer key, SplitedPageLayout *dist);
280
281extern XLogRecPtr gistxlogInsertCompletion(RelFileNode node, ItemPointerData *keys, int len);
282
283/* gistget.c */
284extern Datum gistgettuple(PG_FUNCTION_ARGS);
285extern Datum gistgetmulti(PG_FUNCTION_ARGS);
286
287/* gistscan.c */
288extern void gistfreestack(GISTSearchStack *s);
289extern GISTSearchStack *gistcopystack(GISTSearchStack *s);
290
291/* gistutil.c */
292
293#define GiSTPageSize   \
294        ( BLCKSZ - SizeOfPageHeaderData - MAXALIGN(sizeof(GISTPageOpaqueData)) )
295
296#define GIST_MIN_FILLFACTOR                     10
297#define GIST_DEFAULT_FILLFACTOR         90
298
299extern Datum gistoptions(PG_FUNCTION_ARGS);
300extern bool gistfitpage(IndexTuple *itvec, int len);
301extern bool gistnospace(Page page, IndexTuple *itvec, int len, OffsetNumber todelete, Size freespace);
302extern void gistcheckpage(Relation rel, Buffer buf);
303extern Buffer gistNewBuffer(Relation r);
304extern OffsetNumber gistfillbuffer(Relation r, Page page, IndexTuple *itup,
305                           int len, OffsetNumber off);
306extern IndexTuple *gistextractpage(Page page, int *len /* out */ );
307extern IndexTuple *gistjoinvector(
308                           IndexTuple *itvec, int *len,
309                           IndexTuple *additvec, int addlen);
310extern IndexTupleData *gistfillitupvec(IndexTuple *vec, int veclen, int *memlen);
311
312extern IndexTuple gistunion(Relation r, IndexTuple *itvec,
313                  int len, GISTSTATE *giststate);
314extern IndexTuple gistgetadjusted(Relation r,
315                                IndexTuple oldtup,
316                                IndexTuple addtup,
317                                GISTSTATE *giststate);
318extern IndexTuple gistFormTuple(GISTSTATE *giststate,
319                          Relation r, Datum *attdata, bool *isnull, bool newValues);
320
321extern OffsetNumber gistchoose(Relation r, Page p,
322                   IndexTuple it,
323                   GISTSTATE *giststate);
324extern void gistcentryinit(GISTSTATE *giststate, int nkey,
325                           GISTENTRY *e, Datum k,
326                           Relation r, Page pg,
327                           OffsetNumber o, bool l, bool isNull);
328
329extern void GISTInitBuffer(Buffer b, uint32 f);
330extern void gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e,
331                           Datum k, Relation r, Page pg, OffsetNumber o,
332                           bool l, bool isNull);
333
334extern float gistpenalty(GISTSTATE *giststate, int attno,
335                        GISTENTRY *key1, bool isNull1,
336                        GISTENTRY *key2, bool isNull2);
337extern bool gistMakeUnionItVec(GISTSTATE *giststate, IndexTuple *itvec, int len, int startkey,
338                                   Datum *attr, bool *isnull);
339extern bool gistKeyIsEQ(GISTSTATE *giststate, int attno, Datum a, Datum b);
340extern void gistDeCompressAtt(GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p,
341                                  OffsetNumber o, GISTENTRY *attdata, bool *isnull);
342
343extern void gistMakeUnionKey(GISTSTATE *giststate, int attno,
344                                 GISTENTRY *entry1, bool isnull1,
345                                 GISTENTRY *entry2, bool isnull2,
346                                 Datum *dst, bool *dstisnull);
347
348/* gistvacuum.c */
349extern Datum gistbulkdelete(PG_FUNCTION_ARGS);
350extern Datum gistvacuumcleanup(PG_FUNCTION_ARGS);
351
352/* gistsplit.c */
353extern void gistSplitByKey(Relation r, Page page, IndexTuple *itup,
354                           int len, GISTSTATE *giststate,
355                           GistSplitVector *v, GistEntryVector *entryvec,
356                           int attno);
357
358#endif   /* GIST_PRIVATE_H */
Note: See TracBrowser for help on using the browser.