src/include/utils/array.h

   1 /*-------------------------------------------------------------------------
   2  *
   3  * array.h
   4  *        Declarations for Postgres arrays.
   5  *
   6  * A standard varlena array has the following internal structure:
   7  *        <vl_len_>             - standard varlena header word
   8  *        <ndim>                - number of dimensions of the array
   9  *        <dataoffset>  - offset to stored data, or 0 if no nulls bitmap
  10  *        <elemtype>    - element type OID
  11  *        <dimensions>  - length of each array axis (C array of int)
  12  *        <lower bnds>  - lower boundary of each dimension (C array of int)
  13  *        <null bitmap> - bitmap showing locations of nulls (OPTIONAL)
  14  *        <actual data> - whatever is the stored data
  15  *
  16  * The <dimensions> and <lower bnds> arrays each have ndim elements.
  17  *
  18  * The <null bitmap> may be omitted if the array contains no NULL elements.
  19  * If it is absent, the <dataoffset> field is zero and the offset to the
  20  * stored data must be computed on-the-fly.  If the bitmap is present,
  21  * <dataoffset> is nonzero and is equal to the offset from the array start
  22  * to the first data element (including any alignment padding).  The bitmap
  23  * follows the same conventions as tuple null bitmaps, ie, a 1 indicates
  24  * a non-null entry and the LSB of each bitmap byte is used first.
  25  *
  26  * The actual data starts on a MAXALIGN boundary.  Individual items in the
  27  * array are aligned as specified by the array element type.  They are
  28  * stored in row-major order (last subscript varies most rapidly).
  29  *
  30  * NOTE: it is important that array elements of toastable datatypes NOT be
  31  * toasted, since the tupletoaster won't know they are there.  (We could
  32  * support compressed toasted items; only out-of-line items are dangerous.
  33  * However, it seems preferable to store such items uncompressed and allow
  34  * the toaster to compress the whole array as one input.)
  35  *
  36  *
  37  * The OIDVECTOR and INT2VECTOR datatypes are storage-compatible with
  38  * generic arrays, but they support only one-dimensional arrays with no
  39  * nulls (and no null bitmap).  They don't support being toasted, either.
  40  *
  41  * There are also some "fixed-length array" datatypes, such as NAME and
  42  * POINT.  These are simply a sequence of a fixed number of items each
  43  * of a fixed-length datatype, with no overhead; the item size must be
  44  * a multiple of its alignment requirement, because we do no padding.
  45  * We support subscripting on these types, but array_in() and array_out()
  46  * only work with varlena arrays.
  47  *
  48  * In addition, arrays are a major user of the "expanded object" TOAST
  49  * infrastructure.  This allows a varlena array to be converted to a
  50  * separate representation that may include "deconstructed" Datum/isnull
  51  * arrays holding the elements.
  52  *
  53  *
  54  * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
  55  * Portions Copyright (c) 1994, Regents of the University of California
  56  *
  57  * src/include/utils/array.h
  58  *
  59  *-------------------------------------------------------------------------
  60  */
  61 #ifndef ARRAY_H
  62 #define ARRAY_H
  63
  64 #include "fmgr.h"
  65 #include "utils/expandeddatum.h"
  66
  67 /* avoid including execnodes.h here */
  68 struct ExprState;
  69 struct ExprContext;
  70
  71
  72 /*
  73  * Maximum number of array subscripts (arbitrary limit)
  74  */
  75 #define MAXDIM 6
  76
  77 /*
  78  * Arrays are varlena objects, so must meet the varlena convention that
  79  * the first int32 of the object contains the total object size in bytes.
  80  * Be sure to use VARSIZE() and SET_VARSIZE() to access it, though!
  81  *
  82  * CAUTION: if you change the header for ordinary arrays you will also
  83  * need to change the headers for oidvector and int2vector!
  84  */
  85 typedef struct ArrayType
  86 {
  87         int32           vl_len_;                /* varlena header (do not touch directly!) */
  88         int                     ndim;                   /* # of dimensions */
  89         int32           dataoffset;             /* offset to data, or 0 if no bitmap */
  90         Oid                     elemtype;               /* element type OID */
  91 } ArrayType;
  92
  93 /*
  94  * An expanded array is contained within a private memory context (as
  95  * all expanded objects must be) and has a control structure as below.
  96  *
  97  * The expanded array might contain a regular "flat" array if that was the
  98  * original input and we've not modified it significantly.  Otherwise, the
  99  * contents are represented by Datum/isnull arrays plus dimensionality and
 100  * type information.  We could also have both forms, if we've deconstructed
 101  * the original array for access purposes but not yet changed it.  For pass-
 102  * by-reference element types, the Datums would point into the flat array in
 103  * this situation.  Once we start modifying array elements, new pass-by-ref
 104  * elements are separately palloc'd within the memory context.
 105  */
 106 #define EA_MAGIC 689375833              /* ID for debugging crosschecks */
 107
 108 typedef struct ExpandedArrayHeader
 109 {
 110         /* Standard header for expanded objects */
 111         ExpandedObjectHeader hdr;
 112
 113         /* Magic value identifying an expanded array (for debugging only) */
 114         int                     ea_magic;
 115
 116         /* Dimensionality info (always valid) */
 117         int                     ndims;                  /* # of dimensions */
 118         int                *dims;                       /* array dimensions */
 119         int                *lbound;                     /* index lower bounds for each dimension */
 120
 121         /* Element type info (always valid) */
 122         Oid                     element_type;   /* element type OID */
 123         int16           typlen;                 /* needed info about element datatype */
 124         bool            typbyval;
 125         char            typalign;
 126
 127         /*
 128          * If we have a Datum-array representation of the array, it's kept here;
 129          * else dvalues/dnulls are NULL.  The dvalues and dnulls arrays are always
 130          * palloc'd within the object private context, but may change size from
 131          * time to time.  For pass-by-ref element types, dvalues entries might
 132          * point either into the fstartptr..fendptr area, or to separately
 133          * palloc'd chunks.  Elements should always be fully detoasted, as they
 134          * are in the standard flat representation.
 135          *
 136          * Even when dvalues is valid, dnulls can be NULL if there are no null
 137          * elements.
 138          */
 139         Datum      *dvalues;            /* array of Datums */
 140         bool       *dnulls;                     /* array of is-null flags for Datums */
 141         int                     dvalueslen;             /* allocated length of above arrays */
 142         int                     nelems;                 /* number of valid entries in above arrays */
 143
 144         /*
 145          * flat_size is the current space requirement for the flat equivalent of
 146          * the expanded array, if known; otherwise it's 0.  We store this to make
 147          * consecutive calls of get_flat_size cheap.
 148          */
 149         Size            flat_size;
 150
 151         /*
 152          * fvalue points to the flat representation if it is valid, else it is
 153          * NULL.  If we have or ever had a flat representation then
 154          * fstartptr/fendptr point to the start and end+1 of its data area; this
 155          * is so that we can tell which Datum pointers point into the flat
 156          * representation rather than being pointers to separately palloc'd data.
 157          */
 158         ArrayType  *fvalue;                     /* must be a fully detoasted array */
 159         char       *fstartptr;          /* start of its data area */
 160         char       *fendptr;            /* end+1 of its data area */
 161 } ExpandedArrayHeader;
 162
 163 /*
 164  * Functions that can handle either a "flat" varlena array or an expanded
 165  * array use this union to work with their input.  Don't refer to "flt";
 166  * instead, cast to ArrayType.  This struct nominally requires 8-byte
 167  * alignment on 64-bit, but it's often used for an ArrayType having 4-byte
 168  * alignment.  UBSan complains about referencing "flt" in such cases.
 169  */
 170 typedef union AnyArrayType
 171 {
 172         ArrayType       flt;
 173         ExpandedArrayHeader xpn;
 174 } AnyArrayType;
 175
 176 /*
 177  * working state for accumArrayResult() and friends
 178  * note that the input must be scalars (legal array elements)
 179  */
 180 typedef struct ArrayBuildState
 181 {
 182         MemoryContext mcontext;         /* where all the temp stuff is kept */
 183         Datum      *dvalues;            /* array of accumulated Datums */
 184         bool       *dnulls;                     /* array of is-null flags for Datums */
 185         int                     alen;                   /* allocated length of above arrays */
 186         int                     nelems;                 /* number of valid entries in above arrays */
 187         Oid                     element_type;   /* data type of the Datums */
 188         int16           typlen;                 /* needed info about datatype */
 189         bool            typbyval;
 190         char            typalign;
 191         bool            private_cxt;    /* use private memory context */
 192 } ArrayBuildState;
 193
 194 /*
 195  * working state for accumArrayResultArr() and friends
 196  * note that the input must be arrays, and the same array type is returned
 197  */
 198 typedef struct ArrayBuildStateArr
 199 {
 200         MemoryContext mcontext;         /* where all the temp stuff is kept */
 201         char       *data;                       /* accumulated data */
 202         bits8      *nullbitmap;         /* bitmap of is-null flags, or NULL if none */
 203         int                     abytes;                 /* allocated length of "data" */
 204         int                     nbytes;                 /* number of bytes used so far */
 205         int                     aitems;                 /* allocated length of bitmap (in elements) */
 206         int                     nitems;                 /* total number of elements in result */
 207         int                     ndims;                  /* current dimensions of result */
 208         int                     dims[MAXDIM];
 209         int                     lbs[MAXDIM];
 210         Oid                     array_type;             /* data type of the arrays */
 211         Oid                     element_type;   /* data type of the array elements */
 212         bool            private_cxt;    /* use private memory context */
 213 } ArrayBuildStateArr;
 214
 215 /*
 216  * working state for accumArrayResultAny() and friends
 217  * these functions handle both cases
 218  */
 219 typedef struct ArrayBuildStateAny
 220 {
 221         /* Exactly one of these is not NULL: */
 222         ArrayBuildState *scalarstate;
 223         ArrayBuildStateArr *arraystate;
 224 } ArrayBuildStateAny;
 225
 226 /*
 227  * structure to cache type metadata needed for array manipulation
 228  */
 229 typedef struct ArrayMetaState
 230 {
 231         Oid                     element_type;
 232         int16           typlen;
 233         bool            typbyval;
 234         char            typalign;
 235         char            typdelim;
 236         Oid                     typioparam;
 237         Oid                     typiofunc;
 238         FmgrInfo        proc;
 239 } ArrayMetaState;
 240
 241 /*
 242  * private state needed by array_map (here because caller must provide it)
 243  */
 244 typedef struct ArrayMapState
 245 {
 246         ArrayMetaState inp_extra;
 247         ArrayMetaState ret_extra;
 248 } ArrayMapState;
 249
 250 /* ArrayIteratorData is private in arrayfuncs.c */
 251 typedef struct ArrayIteratorData *ArrayIterator;
 252
 253 /* fmgr macros for regular varlena array objects */
 254 #define DatumGetArrayTypeP(X)             ((ArrayType *) PG_DETOAST_DATUM(X))
 255 #define DatumGetArrayTypePCopy(X)         ((ArrayType *) PG_DETOAST_DATUM_COPY(X))
 256 #define PG_GETARG_ARRAYTYPE_P(n)          DatumGetArrayTypeP(PG_GETARG_DATUM(n))
 257 #define PG_GETARG_ARRAYTYPE_P_COPY(n) DatumGetArrayTypePCopy(PG_GETARG_DATUM(n))
 258 #define PG_RETURN_ARRAYTYPE_P(x)          PG_RETURN_POINTER(x)
 259
 260 /* fmgr macros for expanded array objects */
 261 #define PG_GETARG_EXPANDED_ARRAY(n)  DatumGetExpandedArray(PG_GETARG_DATUM(n))
 262 #define PG_GETARG_EXPANDED_ARRAYX(n, metacache) \
 263         DatumGetExpandedArrayX(PG_GETARG_DATUM(n), metacache)
 264 #define PG_RETURN_EXPANDED_ARRAY(x)  PG_RETURN_DATUM(EOHPGetRWDatum(&(x)->hdr))
 265
 266 /* fmgr macros for AnyArrayType (ie, get either varlena or expanded form) */
 267 #define PG_GETARG_ANY_ARRAY_P(n)        DatumGetAnyArrayP(PG_GETARG_DATUM(n))
 268
 269 /*
 270  * Access macros for varlena array header fields.
 271  *
 272  * ARR_DIMS returns a pointer to an array of array dimensions (number of
 273  * elements along the various array axes).
 274  *
 275  * ARR_LBOUND returns a pointer to an array of array lower bounds.
 276  *
 277  * That is: if the third axis of an array has elements 5 through 8, then
 278  * ARR_DIMS(a)[2] == 4 and ARR_LBOUND(a)[2] == 5.
 279  *
 280  * Unlike C, the default lower bound is 1.
 281  */
 282 #define ARR_SIZE(a)                             VARSIZE(a)
 283 #define ARR_NDIM(a)                             ((a)->ndim)
 284 #define ARR_HASNULL(a)                  ((a)->dataoffset != 0)
 285 #define ARR_ELEMTYPE(a)                 ((a)->elemtype)
 286
 287 #define ARR_DIMS(a) \
 288                 ((int *) (((char *) (a)) + sizeof(ArrayType)))
 289 #define ARR_LBOUND(a) \
 290                 ((int *) (((char *) (a)) + sizeof(ArrayType) + \
 291                                   sizeof(int) * ARR_NDIM(a)))
 292
 293 #define ARR_NULLBITMAP(a) \
 294                 (ARR_HASNULL(a) ? \
 295                  (bits8 *) (((char *) (a)) + sizeof(ArrayType) + \
 296                                         2 * sizeof(int) * ARR_NDIM(a)) \
 297                  : (bits8 *) NULL)
 298
 299 /*
 300  * The total array header size (in bytes) for an array with the specified
 301  * number of dimensions and total number of items.
 302  */
 303 #define ARR_OVERHEAD_NONULLS(ndims) \
 304                 MAXALIGN(sizeof(ArrayType) + 2 * sizeof(int) * (ndims))
 305 #define ARR_OVERHEAD_WITHNULLS(ndims, nitems) \
 306                 MAXALIGN(sizeof(ArrayType) + 2 * sizeof(int) * (ndims) + \
 307                                  ((nitems) + 7) / 8)
 308
 309 #define ARR_DATA_OFFSET(a) \
 310                 (ARR_HASNULL(a) ? (a)->dataoffset : ARR_OVERHEAD_NONULLS(ARR_NDIM(a)))
 311
 312 /*
 313  * Returns a pointer to the actual array data.
 314  */
 315 #define ARR_DATA_PTR(a) \
 316                 (((char *) (a)) + ARR_DATA_OFFSET(a))
 317
 318 /*
 319  * Macros for working with AnyArrayType inputs.  Beware multiple references!
 320  */
 321 #define AARR_NDIM(a) \
 322         (VARATT_IS_EXPANDED_HEADER(a) ? \
 323          (a)->xpn.ndims : ARR_NDIM((ArrayType *) (a)))
 324 #define AARR_HASNULL(a) \
 325         (VARATT_IS_EXPANDED_HEADER(a) ? \
 326          ((a)->xpn.dvalues != NULL ? (a)->xpn.dnulls != NULL : ARR_HASNULL((a)->xpn.fvalue)) : \
 327          ARR_HASNULL((ArrayType *) (a)))
 328 #define AARR_ELEMTYPE(a) \
 329         (VARATT_IS_EXPANDED_HEADER(a) ? \
 330          (a)->xpn.element_type : ARR_ELEMTYPE((ArrayType *) (a)))
 331 #define AARR_DIMS(a) \
 332         (VARATT_IS_EXPANDED_HEADER(a) ? \
 333          (a)->xpn.dims : ARR_DIMS((ArrayType *) (a)))
 334 #define AARR_LBOUND(a) \
 335         (VARATT_IS_EXPANDED_HEADER(a) ? \
 336          (a)->xpn.lbound : ARR_LBOUND((ArrayType *) (a)))
 337
 338
 339 /*
 340  * GUC parameter
 341  */
 342 extern PGDLLIMPORT bool Array_nulls;
 343
 344 /*
 345  * prototypes for functions defined in arrayfuncs.c
 346  */
 347 extern void CopyArrayEls(ArrayType *array,
 348                                                  Datum *values,
 349                                                  bool *nulls,
 350                                                  int nitems,
 351                                                  int typlen,
 352                                                  bool typbyval,
 353                                                  char typalign,
 354                                                  bool freedata);
 355
 356 extern Datum array_get_element(Datum arraydatum, int nSubscripts, int *indx,
 357                                                            int arraytyplen, int elmlen, bool elmbyval, char elmalign,
 358                                                            bool *isNull);
 359 extern Datum array_set_element(Datum arraydatum, int nSubscripts, int *indx,
 360                                                            Datum dataValue, bool isNull,
 361                                                            int arraytyplen, int elmlen, bool elmbyval, char elmalign);
 362 extern Datum array_get_slice(Datum arraydatum, int nSubscripts,
 363                                                          int *upperIndx, int *lowerIndx,
 364                                                          bool *upperProvided, bool *lowerProvided,
 365                                                          int arraytyplen, int elmlen, bool elmbyval, char elmalign);
 366 extern Datum array_set_slice(Datum arraydatum, int nSubscripts,
 367                                                          int *upperIndx, int *lowerIndx,
 368                                                          bool *upperProvided, bool *lowerProvided,
 369                                                          Datum srcArrayDatum, bool isNull,
 370                                                          int arraytyplen, int elmlen, bool elmbyval, char elmalign);
 371
 372 extern Datum array_ref(ArrayType *array, int nSubscripts, int *indx,
 373                                            int arraytyplen, int elmlen, bool elmbyval, char elmalign,
 374                                            bool *isNull);
 375 extern ArrayType *array_set(ArrayType *array, int nSubscripts, int *indx,
 376                                                         Datum dataValue, bool isNull,
 377                                                         int arraytyplen, int elmlen, bool elmbyval, char elmalign);
 378
 379 extern Datum array_map(Datum arrayd,
 380                                            struct ExprState *exprstate, struct ExprContext *econtext,
 381                                            Oid retType, ArrayMapState *amstate);
 382
 383 extern void array_bitmap_copy(bits8 *destbitmap, int destoffset,
 384                                                           const bits8 *srcbitmap, int srcoffset,
 385                                                           int nitems);
 386
 387 extern ArrayType *construct_array(Datum *elems, int nelems,
 388                                                                   Oid elmtype,
 389                                                                   int elmlen, bool elmbyval, char elmalign);
 390 extern ArrayType *construct_array_builtin(Datum *elems, int nelems, Oid elmtype);
 391 extern ArrayType *construct_md_array(Datum *elems,
 392                                                                          bool *nulls,
 393                                                                          int ndims,
 394                                                                          int *dims,
 395                                                                          int *lbs,
 396                                                                          Oid elmtype, int elmlen, bool elmbyval, char elmalign);
 397 extern ArrayType *construct_empty_array(Oid elmtype);
 398 extern ExpandedArrayHeader *construct_empty_expanded_array(Oid element_type,
 399                                                                                                                    MemoryContext parentcontext,
 400                                                                                                                    ArrayMetaState *metacache);
 401 extern void deconstruct_array(ArrayType *array,
 402                                                           Oid elmtype,
 403                                                           int elmlen, bool elmbyval, char elmalign,
 404                                                           Datum **elemsp, bool **nullsp, int *nelemsp);
 405 extern void deconstruct_array_builtin(ArrayType *array,
 406                                                                           Oid elmtype,
 407                                                                           Datum **elemsp, bool **nullsp, int *nelemsp);
 408 extern bool array_contains_nulls(ArrayType *array);
 409
 410 extern ArrayBuildState *initArrayResult(Oid element_type,
 411                                                                                 MemoryContext rcontext, bool subcontext);
 412 extern ArrayBuildState *initArrayResultWithSize(Oid element_type,
 413                                                                                                 MemoryContext rcontext,
 414                                                                                                 bool subcontext, int initsize);
 415 extern ArrayBuildState *accumArrayResult(ArrayBuildState *astate,
 416                                                                                  Datum dvalue, bool disnull,
 417                                                                                  Oid element_type,
 418                                                                                  MemoryContext rcontext);
 419 extern Datum makeArrayResult(ArrayBuildState *astate,
 420                                                          MemoryContext rcontext);
 421 extern Datum makeMdArrayResult(ArrayBuildState *astate, int ndims,
 422                                                            int *dims, int *lbs, MemoryContext rcontext, bool release);
 423
 424 extern ArrayBuildStateArr *initArrayResultArr(Oid array_type, Oid element_type,
 425                                                                                           MemoryContext rcontext, bool subcontext);
 426 extern ArrayBuildStateArr *accumArrayResultArr(ArrayBuildStateArr *astate,
 427                                                                                            Datum dvalue, bool disnull,
 428                                                                                            Oid array_type,
 429                                                                                            MemoryContext rcontext);
 430 extern Datum makeArrayResultArr(ArrayBuildStateArr *astate,
 431                                                                 MemoryContext rcontext, bool release);
 432
 433 extern ArrayBuildStateAny *initArrayResultAny(Oid input_type,
 434                                                                                           MemoryContext rcontext, bool subcontext);
 435 extern ArrayBuildStateAny *accumArrayResultAny(ArrayBuildStateAny *astate,
 436                                                                                            Datum dvalue, bool disnull,
 437                                                                                            Oid input_type,
 438                                                                                            MemoryContext rcontext);
 439 extern Datum makeArrayResultAny(ArrayBuildStateAny *astate,
 440                                                                 MemoryContext rcontext, bool release);
 441
 442 extern ArrayIterator array_create_iterator(ArrayType *arr, int slice_ndim, ArrayMetaState *mstate);
 443 extern bool array_iterate(ArrayIterator iterator, Datum *value, bool *isnull);
 444 extern void array_free_iterator(ArrayIterator iterator);
 445
 446 /*
 447  * prototypes for functions defined in arrayutils.c
 448  */
 449
 450 extern int      ArrayGetOffset(int n, const int *dim, const int *lb, const int *indx);
 451 extern int      ArrayGetOffset0(int n, const int *tup, const int *scale);
 452 extern int      ArrayGetNItems(int ndim, const int *dims);
 453 extern int      ArrayGetNItemsSafe(int ndim, const int *dims,
 454                                                            struct Node *escontext);
 455 extern void ArrayCheckBounds(int ndim, const int *dims, const int *lb);
 456 extern bool ArrayCheckBoundsSafe(int ndim, const int *dims, const int *lb,
 457                                                                  struct Node *escontext);
 458 extern void mda_get_range(int n, int *span, const int *st, const int *endp);
 459 extern void mda_get_prod(int n, const int *range, int *prod);
 460 extern void mda_get_offset_values(int n, int *dist, const int *prod, const int *span);
 461 extern int      mda_next_tuple(int n, int *curr, const int *span);
 462 extern int32 *ArrayGetIntegerTypmods(ArrayType *arr, int *n);
 463
 464 /*
 465  * prototypes for functions defined in array_expanded.c
 466  */
 467 extern Datum expand_array(Datum arraydatum, MemoryContext parentcontext,
 468                                                   ArrayMetaState *metacache);
 469 extern ExpandedArrayHeader *DatumGetExpandedArray(Datum d);
 470 extern ExpandedArrayHeader *DatumGetExpandedArrayX(Datum d,
 471                                                                                                    ArrayMetaState *metacache);
 472 extern AnyArrayType *DatumGetAnyArrayP(Datum d);
 473 extern void deconstruct_expanded_array(ExpandedArrayHeader *eah);
 474
 475 #endif                                                  /* ARRAY_H */