src/include/access/spgist_private.h

   1 /*-------------------------------------------------------------------------
   2  *
   3  * spgist_private.h
   4  *        Private declarations for SP-GiST access method.
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * src/include/access/spgist_private.h
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #ifndef SPGIST_PRIVATE_H
  15 #define SPGIST_PRIVATE_H
  16
  17 #include "access/itup.h"
  18 #include "access/spgist.h"
  19 #include "catalog/pg_am_d.h"
  20 #include "nodes/tidbitmap.h"
  21 #include "storage/buf.h"
  22 #include "utils/geo_decls.h"
  23 #include "utils/relcache.h"
  24
  25
  26 typedef struct SpGistOptions
  27 {
  28         int32           varlena_header_;        /* varlena header (do not touch directly!) */
  29         int                     fillfactor;             /* page fill factor in percent (0..100) */
  30 } SpGistOptions;
  31
  32 #define SpGistGetFillFactor(relation) \
  33         (AssertMacro(relation->rd_rel->relkind == RELKIND_INDEX && \
  34                                  relation->rd_rel->relam == SPGIST_AM_OID), \
  35          (relation)->rd_options ? \
  36          ((SpGistOptions *) (relation)->rd_options)->fillfactor : \
  37          SPGIST_DEFAULT_FILLFACTOR)
  38 #define SpGistGetTargetPageFreeSpace(relation) \
  39         (BLCKSZ * (100 - SpGistGetFillFactor(relation)) / 100)
  40
  41
  42 /* SPGiST leaf tuples have one key column, optionally have included columns */
  43 #define spgKeyColumn 0
  44 #define spgFirstIncludeColumn 1
  45
  46 /* Page numbers of fixed-location pages */
  47 #define SPGIST_METAPAGE_BLKNO    (0)    /* metapage */
  48 #define SPGIST_ROOT_BLKNO                (1)    /* root for normal entries */
  49 #define SPGIST_NULL_BLKNO                (2)    /* root for null-value entries */
  50 #define SPGIST_LAST_FIXED_BLKNO  SPGIST_NULL_BLKNO
  51
  52 #define SpGistBlockIsRoot(blkno) \
  53         ((blkno) == SPGIST_ROOT_BLKNO || (blkno) == SPGIST_NULL_BLKNO)
  54 #define SpGistBlockIsFixed(blkno) \
  55         ((BlockNumber) (blkno) <= (BlockNumber) SPGIST_LAST_FIXED_BLKNO)
  56
  57 /*
  58  * Contents of page special space on SPGiST index pages
  59  */
  60 typedef struct SpGistPageOpaqueData
  61 {
  62         uint16          flags;                  /* see bit definitions below */
  63         uint16          nRedirection;   /* number of redirection tuples on page */
  64         uint16          nPlaceholder;   /* number of placeholder tuples on page */
  65         /* note there's no count of either LIVE or DEAD tuples ... */
  66         uint16          spgist_page_id; /* for identification of SP-GiST indexes */
  67 } SpGistPageOpaqueData;
  68
  69 typedef SpGistPageOpaqueData *SpGistPageOpaque;
  70
  71 /* Flag bits in page special space */
  72 #define SPGIST_META                     (1<<0)
  73 #define SPGIST_DELETED          (1<<1)  /* never set, but keep for backwards
  74                                                                          * compatibility */
  75 #define SPGIST_LEAF                     (1<<2)
  76 #define SPGIST_NULLS            (1<<3)
  77
  78 #define SpGistPageGetOpaque(page) ((SpGistPageOpaque) PageGetSpecialPointer(page))
  79 #define SpGistPageIsMeta(page) (SpGistPageGetOpaque(page)->flags & SPGIST_META)
  80 #define SpGistPageIsDeleted(page) (SpGistPageGetOpaque(page)->flags & SPGIST_DELETED)
  81 #define SpGistPageIsLeaf(page) (SpGistPageGetOpaque(page)->flags & SPGIST_LEAF)
  82 #define SpGistPageStoresNulls(page) (SpGistPageGetOpaque(page)->flags & SPGIST_NULLS)
  83
  84 /*
  85  * The page ID is for the convenience of pg_filedump and similar utilities,
  86  * which otherwise would have a hard time telling pages of different index
  87  * types apart.  It should be the last 2 bytes on the page.  This is more or
  88  * less "free" due to alignment considerations.
  89  *
  90  * See comments above GinPageOpaqueData.
  91  */
  92 #define SPGIST_PAGE_ID          0xFF82
  93
  94 /*
  95  * Each backend keeps a cache of last-used page info in its index->rd_amcache
  96  * area.  This is initialized from, and occasionally written back to,
  97  * shared storage in the index metapage.
  98  */
  99 typedef struct SpGistLastUsedPage
 100 {
 101         BlockNumber blkno;                      /* block number, or InvalidBlockNumber */
 102         int                     freeSpace;              /* page's free space (could be obsolete!) */
 103 } SpGistLastUsedPage;
 104
 105 /* Note: indexes in cachedPage[] match flag assignments for SpGistGetBuffer */
 106 #define SPGIST_CACHED_PAGES 8
 107
 108 typedef struct SpGistLUPCache
 109 {
 110         SpGistLastUsedPage cachedPage[SPGIST_CACHED_PAGES];
 111 } SpGistLUPCache;
 112
 113 /*
 114  * metapage
 115  */
 116 typedef struct SpGistMetaPageData
 117 {
 118         uint32          magicNumber;    /* for identity cross-check */
 119         SpGistLUPCache lastUsedPages;   /* shared storage of last-used info */
 120 } SpGistMetaPageData;
 121
 122 #define SPGIST_MAGIC_NUMBER (0xBA0BABEE)
 123
 124 #define SpGistPageGetMeta(p) \
 125         ((SpGistMetaPageData *) PageGetContents(p))
 126
 127 /*
 128  * Private state of index AM.  SpGistState is common to both insert and
 129  * search code; SpGistScanOpaque is for searches only.
 130  */
 131
 132 typedef struct SpGistLeafTupleData *SpGistLeafTuple;    /* forward reference */
 133
 134 /* Per-datatype info needed in SpGistState */
 135 typedef struct SpGistTypeDesc
 136 {
 137         Oid                     type;
 138         int16           attlen;
 139         bool            attbyval;
 140         char            attalign;
 141         char            attstorage;
 142 } SpGistTypeDesc;
 143
 144 typedef struct SpGistState
 145 {
 146         Relation        index;                  /* index we're working with */
 147
 148         spgConfigOut config;            /* filled in by opclass config method */
 149
 150         SpGistTypeDesc attType;         /* type of values to be indexed/restored */
 151         SpGistTypeDesc attLeafType; /* type of leaf-tuple values */
 152         SpGistTypeDesc attPrefixType;   /* type of inner-tuple prefix values */
 153         SpGistTypeDesc attLabelType;    /* type of node label values */
 154
 155         /* leafTupDesc typically points to index's tupdesc, but not always */
 156         TupleDesc       leafTupDesc;    /* descriptor for leaf-level tuples */
 157
 158         char       *deadTupleStorage;   /* workspace for spgFormDeadTuple */
 159
 160         TransactionId myXid;            /* XID to use when creating a redirect tuple */
 161         bool            isBuild;                /* true if doing index build */
 162 } SpGistState;
 163
 164 /* Item to be re-examined later during a search */
 165 typedef struct SpGistSearchItem
 166 {
 167         pairingheap_node phNode;        /* pairing heap node */
 168         Datum           value;                  /* value reconstructed from parent, or
 169                                                                  * leafValue if isLeaf */
 170         SpGistLeafTuple leafTuple;      /* whole leaf tuple, if needed */
 171         void       *traversalValue; /* opclass-specific traverse value */
 172         int                     level;                  /* level of items on this page */
 173         ItemPointerData heapPtr;        /* heap info, if heap tuple */
 174         bool            isNull;                 /* SearchItem is NULL item */
 175         bool            isLeaf;                 /* SearchItem is heap item */
 176         bool            recheck;                /* qual recheck is needed */
 177         bool            recheckDistances;       /* distance recheck is needed */
 178
 179         /* array with numberOfOrderBys entries */
 180         double          distances[FLEXIBLE_ARRAY_MEMBER];
 181 } SpGistSearchItem;
 182
 183 #define SizeOfSpGistSearchItem(n_distances) \
 184         (offsetof(SpGistSearchItem, distances) + sizeof(double) * (n_distances))
 185
 186 /*
 187  * Private state of an index scan
 188  */
 189 typedef struct SpGistScanOpaqueData
 190 {
 191         SpGistState state;                      /* see above */
 192         pairingheap *scanQueue;         /* queue of to be visited items */
 193         MemoryContext tempCxt;          /* short-lived memory context */
 194         MemoryContext traversalCxt; /* single scan lifetime memory context */
 195
 196         /* Control flags showing whether to search nulls and/or non-nulls */
 197         bool            searchNulls;    /* scan matches (all) null entries */
 198         bool            searchNonNulls; /* scan matches (some) non-null entries */
 199
 200         /* Index quals to be passed to opclass (null-related quals removed) */
 201         int                     numberOfKeys;   /* number of index qualifier conditions */
 202         ScanKey         keyData;                /* array of index qualifier descriptors */
 203         int                     numberOfOrderBys;       /* number of ordering operators */
 204         int                     numberOfNonNullOrderBys;        /* number of ordering operators
 205                                                                                          * with non-NULL arguments */
 206         ScanKey         orderByData;    /* array of ordering op descriptors */
 207         Oid                *orderByTypes;       /* array of ordering op return types */
 208         int                *nonNullOrderByOffsets;      /* array of offset of non-NULL
 209                                                                                  * ordering keys in the original array */
 210         Oid                     indexCollation; /* collation of index column */
 211
 212         /* Opclass defined functions: */
 213         FmgrInfo        innerConsistentFn;
 214         FmgrInfo        leafConsistentFn;
 215
 216         /* Pre-allocated workspace arrays: */
 217         double     *zeroDistances;
 218         double     *infDistances;
 219
 220         /* These fields are only used in amgetbitmap scans: */
 221         TIDBitmap  *tbm;                        /* bitmap being filled */
 222         int64           ntids;                  /* number of TIDs passed to bitmap */
 223
 224         /* These fields are only used in amgettuple scans: */
 225         bool            want_itup;              /* are we reconstructing tuples? */
 226         TupleDesc       reconTupDesc;   /* if so, descriptor for reconstructed tuples */
 227         int                     nPtrs;                  /* number of TIDs found on current page */
 228         int                     iPtr;                   /* index for scanning through same */
 229         ItemPointerData heapPtrs[MaxIndexTuplesPerPage];        /* TIDs from cur page */
 230         bool            recheck[MaxIndexTuplesPerPage]; /* their recheck flags */
 231         bool            recheckDistances[MaxIndexTuplesPerPage];        /* distance recheck
 232                                                                                                                          * flags */
 233         HeapTuple       reconTups[MaxIndexTuplesPerPage];       /* reconstructed tuples */
 234
 235         /* distances (for recheck) */
 236         IndexOrderByDistance *distances[MaxIndexTuplesPerPage];
 237
 238         /*
 239          * Note: using MaxIndexTuplesPerPage above is a bit hokey since
 240          * SpGistLeafTuples aren't exactly IndexTuples; however, they are larger,
 241          * so this is safe.
 242          */
 243 } SpGistScanOpaqueData;
 244
 245 typedef SpGistScanOpaqueData *SpGistScanOpaque;
 246
 247 /*
 248  * This struct is what we actually keep in index->rd_amcache.  It includes
 249  * static configuration information as well as the lastUsedPages cache.
 250  */
 251 typedef struct SpGistCache
 252 {
 253         spgConfigOut config;            /* filled in by opclass config method */
 254
 255         SpGistTypeDesc attType;         /* type of values to be indexed/restored */
 256         SpGistTypeDesc attLeafType; /* type of leaf-tuple values */
 257         SpGistTypeDesc attPrefixType;   /* type of inner-tuple prefix values */
 258         SpGistTypeDesc attLabelType;    /* type of node label values */
 259
 260         SpGistLUPCache lastUsedPages;   /* local storage of last-used info */
 261 } SpGistCache;
 262
 263
 264 /*
 265  * SPGiST tuple types.  Note: inner, leaf, and dead tuple structs
 266  * must have the same tupstate field in the same position!      Real inner and
 267  * leaf tuples always have tupstate = LIVE; if the state is something else,
 268  * use the SpGistDeadTuple struct to inspect the tuple.
 269  */
 270
 271 /* values of tupstate (see README for more info) */
 272 #define SPGIST_LIVE                     0       /* normal live tuple (either inner or leaf) */
 273 #define SPGIST_REDIRECT         1       /* temporary redirection placeholder */
 274 #define SPGIST_DEAD                     2       /* dead, cannot be removed because of links */
 275 #define SPGIST_PLACEHOLDER      3       /* placeholder, used to preserve offsets */
 276
 277 /*
 278  * SPGiST inner tuple: list of "nodes" that subdivide a set of tuples
 279  *
 280  * Inner tuple layout:
 281  * header/optional prefix/array of nodes, which are SpGistNodeTuples
 282  *
 283  * size and prefixSize must be multiples of MAXALIGN
 284  *
 285  * If the prefix datum is of a pass-by-value type, it is stored in its
 286  * Datum representation, that is its on-disk representation is of length
 287  * sizeof(Datum).  This is a fairly unfortunate choice, because in no other
 288  * place does Postgres use Datum as an on-disk representation; it creates
 289  * an unnecessary incompatibility between 32-bit and 64-bit builds.  But the
 290  * compatibility loss is mostly theoretical since MAXIMUM_ALIGNOF typically
 291  * differs between such builds, too.  Anyway we're stuck with it now.
 292  */
 293 typedef struct SpGistInnerTupleData
 294 {
 295         unsigned int tupstate:2,        /* LIVE/REDIRECT/DEAD/PLACEHOLDER */
 296                                 allTheSame:1,   /* all nodes in tuple are equivalent */
 297                                 nNodes:13,              /* number of nodes within inner tuple */
 298                                 prefixSize:16;  /* size of prefix, or 0 if none */
 299         uint16          size;                   /* total size of inner tuple */
 300         /* On most machines there will be a couple of wasted bytes here */
 301         /* prefix datum follows, then nodes */
 302 } SpGistInnerTupleData;
 303
 304 typedef SpGistInnerTupleData *SpGistInnerTuple;
 305
 306 /* these must match largest values that fit in bit fields declared above */
 307 #define SGITMAXNNODES           0x1FFF
 308 #define SGITMAXPREFIXSIZE       0xFFFF
 309 #define SGITMAXSIZE                     0xFFFF
 310
 311 #define SGITHDRSZ                       MAXALIGN(sizeof(SpGistInnerTupleData))
 312 #define _SGITDATA(x)            (((char *) (x)) + SGITHDRSZ)
 313 #define SGITDATAPTR(x)          ((x)->prefixSize ? _SGITDATA(x) : NULL)
 314 #define SGITDATUM(x, s)         ((x)->prefixSize ? \
 315                                                          ((s)->attPrefixType.attbyval ? \
 316                                                           *(Datum *) _SGITDATA(x) : \
 317                                                           PointerGetDatum(_SGITDATA(x))) \
 318                                                          : (Datum) 0)
 319 #define SGITNODEPTR(x)          ((SpGistNodeTuple) (_SGITDATA(x) + (x)->prefixSize))
 320
 321 /* Macro for iterating through the nodes of an inner tuple */
 322 #define SGITITERATE(x, i, nt)   \
 323         for ((i) = 0, (nt) = SGITNODEPTR(x); \
 324                  (i) < (x)->nNodes; \
 325                  (i)++, (nt) = (SpGistNodeTuple) (((char *) (nt)) + IndexTupleSize(nt)))
 326
 327 /*
 328  * SPGiST node tuple: one node within an inner tuple
 329  *
 330  * Node tuples use the same header as ordinary Postgres IndexTuples, but
 331  * we do not use a null bitmap, because we know there is only one column
 332  * so the INDEX_NULL_MASK bit suffices.  Also, pass-by-value datums are
 333  * stored in Datum form, the same convention as for inner tuple prefixes.
 334  */
 335
 336 typedef IndexTupleData SpGistNodeTupleData;
 337
 338 typedef SpGistNodeTupleData *SpGistNodeTuple;
 339
 340 #define SGNTHDRSZ                       MAXALIGN(sizeof(SpGistNodeTupleData))
 341 #define SGNTDATAPTR(x)          (((char *) (x)) + SGNTHDRSZ)
 342 #define SGNTDATUM(x, s)         ((s)->attLabelType.attbyval ? \
 343                                                          *(Datum *) SGNTDATAPTR(x) : \
 344                                                          PointerGetDatum(SGNTDATAPTR(x)))
 345
 346 /*
 347  * SPGiST leaf tuple: carries a leaf datum and a heap tuple TID,
 348  * and optionally some "included" columns.
 349  *
 350  * In the simplest case, the leaf datum is the same as the indexed value;
 351  * but it could also be a suffix or some other sort of delta that permits
 352  * reconstruction given knowledge of the prefix path traversed to get here.
 353  * Any included columns are stored without modification.
 354  *
 355  * A nulls bitmap is present if there are included columns AND any of the
 356  * datums are NULL.  We do not need a nulls bitmap for the case of a null
 357  * leaf datum without included columns, as we can infer whether the leaf
 358  * datum is null from whether the tuple is stored on a nulls page.  (This
 359  * provision is mostly for backwards compatibility, but it does save space
 360  * on 32-bit machines.)  As with other PG index tuple designs, if the nulls
 361  * bitmap exists then it's of size INDEX_MAX_KEYS bits regardless of the
 362  * actual number of attributes.  For the usual choice of INDEX_MAX_KEYS,
 363  * this costs nothing because of alignment considerations.
 364  *
 365  * The size field is wider than could possibly be needed for an on-disk leaf
 366  * tuple, but this allows us to form leaf tuples even when the datum is too
 367  * wide to be stored immediately, and it costs nothing because of alignment
 368  * considerations.
 369  *
 370  * t_info holds the nextOffset field (14 bits wide, enough for supported
 371  * page sizes) plus the has-nulls-bitmap flag bit; another flag bit is free.
 372  *
 373  * Normally, nextOffset links to the next tuple belonging to the same parent
 374  * node (which must be on the same page), or it's 0 if there is no next tuple.
 375  * But when the root page is a leaf page, we don't chain its tuples,
 376  * so nextOffset is always 0 on the root.
 377  *
 378  * size must be a multiple of MAXALIGN; also, it must be at least SGDTSIZE
 379  * so that the tuple can be converted to REDIRECT status later.  (This
 380  * restriction only adds bytes for a NULL leaf datum stored on a 32-bit
 381  * machine; otherwise alignment restrictions force it anyway.)
 382  */
 383 typedef struct SpGistLeafTupleData
 384 {
 385         unsigned int tupstate:2,        /* LIVE/REDIRECT/DEAD/PLACEHOLDER */
 386                                 size:30;                /* large enough for any palloc'able value */
 387         uint16          t_info;                 /* nextOffset, which links to the next tuple
 388                                                                  * in chain, plus two flag bits */
 389         ItemPointerData heapPtr;        /* TID of represented heap tuple */
 390         /* nulls bitmap follows if the flag bit for it is set */
 391         /* leaf datum, then any included datums, follows on a MAXALIGN boundary */
 392 } SpGistLeafTupleData;
 393
 394 /* Macros to access nextOffset and bit fields inside t_info */
 395 #define SGLT_GET_NEXTOFFSET(spgLeafTuple) \
 396         ((spgLeafTuple)->t_info & 0x3FFF)
 397 #define SGLT_GET_HASNULLMASK(spgLeafTuple) \
 398         (((spgLeafTuple)->t_info & 0x8000) ? true : false)
 399 #define SGLT_SET_NEXTOFFSET(spgLeafTuple, offsetNumber) \
 400         ((spgLeafTuple)->t_info = \
 401          ((spgLeafTuple)->t_info & 0xC000) | ((offsetNumber) & 0x3FFF))
 402 #define SGLT_SET_HASNULLMASK(spgLeafTuple, hasnulls) \
 403         ((spgLeafTuple)->t_info = \
 404          ((spgLeafTuple)->t_info & 0x7FFF) | ((hasnulls) ? 0x8000 : 0))
 405
 406 #define SGLTHDRSZ(hasnulls) \
 407         ((hasnulls) ? MAXALIGN(sizeof(SpGistLeafTupleData) + \
 408                                                    sizeof(IndexAttributeBitMapData)) : \
 409          MAXALIGN(sizeof(SpGistLeafTupleData)))
 410 #define SGLTDATAPTR(x)          (((char *) (x)) + SGLTHDRSZ(SGLT_GET_HASNULLMASK(x)))
 411 #define SGLTDATUM(x, s)         fetch_att(SGLTDATAPTR(x), \
 412                                                                           (s)->attLeafType.attbyval, \
 413                                                                           (s)->attLeafType.attlen)
 414
 415 /*
 416  * SPGiST dead tuple: declaration for examining non-live tuples
 417  *
 418  * The tupstate field of this struct must match those of regular inner and
 419  * leaf tuples, and its size field must match a leaf tuple's.
 420  * Also, the pointer field must be in the same place as a leaf tuple's heapPtr
 421  * field, to satisfy some Asserts that we make when replacing a leaf tuple
 422  * with a dead tuple.
 423  * We don't use t_info, but it's needed to align the pointer field.
 424  * pointer and xid are only valid when tupstate = REDIRECT.
 425  */
 426 typedef struct SpGistDeadTupleData
 427 {
 428         unsigned int tupstate:2,        /* LIVE/REDIRECT/DEAD/PLACEHOLDER */
 429                                 size:30;
 430         uint16          t_info;                 /* not used in dead tuples */
 431         ItemPointerData pointer;        /* redirection inside index */
 432         TransactionId xid;                      /* ID of xact that inserted this tuple */
 433 } SpGistDeadTupleData;
 434
 435 typedef SpGistDeadTupleData *SpGistDeadTuple;
 436
 437 #define SGDTSIZE                MAXALIGN(sizeof(SpGistDeadTupleData))
 438
 439 /*
 440  * Macros for doing free-space calculations.  Note that when adding up the
 441  * space needed for tuples, we always consider each tuple to need the tuple's
 442  * size plus sizeof(ItemIdData) (for the line pointer).  This works correctly
 443  * so long as tuple sizes are always maxaligned.
 444  */
 445
 446 /* Page capacity after allowing for fixed header and special space */
 447 #define SPGIST_PAGE_CAPACITY  \
 448         MAXALIGN_DOWN(BLCKSZ - \
 449                                   SizeOfPageHeaderData - \
 450                                   MAXALIGN(sizeof(SpGistPageOpaqueData)))
 451
 452 /*
 453  * Compute free space on page, assuming that up to n placeholders can be
 454  * recycled if present (n should be the number of tuples to be inserted)
 455  */
 456 #define SpGistPageGetFreeSpace(p, n) \
 457         (PageGetExactFreeSpace(p) + \
 458          Min(SpGistPageGetOpaque(p)->nPlaceholder, n) * \
 459          (SGDTSIZE + sizeof(ItemIdData)))
 460
 461 /*
 462  * XLOG stuff
 463  */
 464
 465 #define STORE_STATE(s, d)  \
 466         do { \
 467                 (d).myXid = (s)->myXid; \
 468                 (d).isBuild = (s)->isBuild; \
 469         } while(0)
 470
 471 /*
 472  * The "flags" argument for SpGistGetBuffer should be either GBUF_LEAF to
 473  * get a leaf page, or GBUF_INNER_PARITY(blockNumber) to get an inner
 474  * page in the same triple-parity group as the specified block number.
 475  * (Typically, this should be GBUF_INNER_PARITY(parentBlockNumber + 1)
 476  * to follow the rule described in spgist/README.)
 477  * In addition, GBUF_NULLS can be OR'd in to get a page for storage of
 478  * null-valued tuples.
 479  *
 480  * Note: these flag values are used as indexes into lastUsedPages.
 481  */
 482 #define GBUF_LEAF                               0x03
 483 #define GBUF_INNER_PARITY(x)    ((x) % 3)
 484 #define GBUF_NULLS                              0x04
 485
 486 #define GBUF_PARITY_MASK                0x03
 487 #define GBUF_REQ_LEAF(flags)    (((flags) & GBUF_PARITY_MASK) == GBUF_LEAF)
 488 #define GBUF_REQ_NULLS(flags)   ((flags) & GBUF_NULLS)
 489
 490 /* spgutils.c */
 491
 492 /* reloption parameters */
 493 #define SPGIST_MIN_FILLFACTOR                   10
 494 #define SPGIST_DEFAULT_FILLFACTOR               80
 495
 496 extern SpGistCache *spgGetCache(Relation index);
 497 extern TupleDesc getSpGistTupleDesc(Relation index, SpGistTypeDesc *keyType);
 498 extern void initSpGistState(SpGistState *state, Relation index);
 499 extern Buffer SpGistNewBuffer(Relation index);
 500 extern void SpGistUpdateMetaPage(Relation index);
 501 extern Buffer SpGistGetBuffer(Relation index, int flags,
 502                                                           int needSpace, bool *isNew);
 503 extern void SpGistSetLastUsedPage(Relation index, Buffer buffer);
 504 extern void SpGistInitPage(Page page, uint16 f);
 505 extern void SpGistInitBuffer(Buffer b, uint16 f);
 506 extern void SpGistInitMetapage(Page page);
 507 extern unsigned int SpGistGetInnerTypeSize(SpGistTypeDesc *att, Datum datum);
 508 extern Size SpGistGetLeafTupleSize(TupleDesc tupleDescriptor,
 509                                                                    Datum *datums, bool *isnulls);
 510 extern SpGistLeafTuple spgFormLeafTuple(SpGistState *state,
 511                                                                                 ItemPointer heapPtr,
 512                                                                                 Datum *datums, bool *isnulls);
 513 extern SpGistNodeTuple spgFormNodeTuple(SpGistState *state,
 514                                                                                 Datum label, bool isnull);
 515 extern SpGistInnerTuple spgFormInnerTuple(SpGistState *state,
 516                                                                                   bool hasPrefix, Datum prefix,
 517                                                                                   int nNodes, SpGistNodeTuple *nodes);
 518 extern SpGistDeadTuple spgFormDeadTuple(SpGistState *state, int tupstate,
 519                                                                                 BlockNumber blkno, OffsetNumber offnum);
 520 extern void spgDeformLeafTuple(SpGistLeafTuple tup, TupleDesc tupleDescriptor,
 521                                                            Datum *datums, bool *isnulls,
 522                                                            bool keyColumnIsNull);
 523 extern Datum *spgExtractNodeLabels(SpGistState *state,
 524                                                                    SpGistInnerTuple innerTuple);
 525 extern OffsetNumber SpGistPageAddNewItem(SpGistState *state, Page page,
 526                                                                                  Item item, Size size,
 527                                                                                  OffsetNumber *startOffset,
 528                                                                                  bool errorOK);
 529 extern bool spgproperty(Oid index_oid, int attno,
 530                                                 IndexAMProperty prop, const char *propname,
 531                                                 bool *res, bool *isnull);
 532
 533 /* spgdoinsert.c */
 534 extern void spgUpdateNodeLink(SpGistInnerTuple tup, int nodeN,
 535                                                           BlockNumber blkno, OffsetNumber offset);
 536 extern void spgPageIndexMultiDelete(SpGistState *state, Page page,
 537                                                                         OffsetNumber *itemnos, int nitems,
 538                                                                         int firststate, int reststate,
 539                                                                         BlockNumber blkno, OffsetNumber offnum);
 540 extern bool spgdoinsert(Relation index, SpGistState *state,
 541                                                 ItemPointer heapPtr, Datum *datums, bool *isnulls);
 542
 543 /* spgproc.c */
 544 extern double *spg_key_orderbys_distances(Datum key, bool isLeaf,
 545                                                                                   ScanKey orderbys, int norderbys);
 546 extern BOX *box_copy(BOX *orig);
 547
 548 #endif                                                  /* SPGIST_PRIVATE_H */