granicus.if.org Git - postgresql/blob - src/backend/utils/adt/arrayutils.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * arrayutils.c
   4  *        This file contains some support routines required for array functions.
   5  *
   6  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        src/backend/utils/adt/arrayutils.c
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #include "catalog/pg_type.h"
  19 #include "utils/array.h"
  20 #include "utils/builtins.h"
  21 #include "utils/memutils.h"
  22
  23
  24 /*
  25  * Convert subscript list into linear element number (from 0)
  26  *
  27  * We assume caller has already range-checked the dimensions and subscripts,
  28  * so no overflow is possible.
  29  */
  30 int
  31 ArrayGetOffset(int n, const int *dim, const int *lb, const int *indx)
  32 {
  33         int                     i,
  34                                 scale = 1,
  35                                 offset = 0;
  36
  37         for (i = n - 1; i >= 0; i--)
  38         {
  39                 offset += (indx[i] - lb[i]) * scale;
  40                 scale *= dim[i];
  41         }
  42         return offset;
  43 }
  44
  45 /*
  46  * Same, but subscripts are assumed 0-based, and use a scale array
  47  * instead of raw dimension data (see mda_get_prod to create scale array)
  48  */
  49 int
  50 ArrayGetOffset0(int n, const int *tup, const int *scale)
  51 {
  52         int                     i,
  53                                 lin = 0;
  54
  55         for (i = 0; i < n; i++)
  56                 lin += tup[i] * scale[i];
  57         return lin;
  58 }
  59
  60 /*
  61  * Convert array dimensions into number of elements
  62  *
  63  * This must do overflow checking, since it is used to validate that a user
  64  * dimensionality request doesn't overflow what we can handle.
  65  *
  66  * We limit array sizes to at most about a quarter billion elements,
  67  * so that it's not necessary to check for overflow in quite so many
  68  * places --- for instance when palloc'ing Datum arrays.
  69  *
  70  * The multiplication overflow check only works on machines that have int64
  71  * arithmetic, but that is nearly all platforms these days, and doing check
  72  * divides for those that don't seems way too expensive.
  73  */
  74 int
  75 ArrayGetNItems(int ndim, const int *dims)
  76 {
  77         int32           ret;
  78         int                     i;
  79
  80 #define MaxArraySize ((Size) (MaxAllocSize / sizeof(Datum)))
  81
  82         if (ndim <= 0)
  83                 return 0;
  84         ret = 1;
  85         for (i = 0; i < ndim; i++)
  86         {
  87                 int64           prod;
  88
  89                 /* A negative dimension implies that UB-LB overflowed ... */
  90                 if (dims[i] < 0)
  91                         ereport(ERROR,
  92                                         (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
  93                                          errmsg("array size exceeds the maximum allowed (%d)",
  94                                                         (int) MaxArraySize)));
  95
  96                 prod = (int64) ret *(int64) dims[i];
  97
  98                 ret = (int32) prod;
  99                 if ((int64) ret != prod)
 100                         ereport(ERROR,
 101                                         (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
 102                                          errmsg("array size exceeds the maximum allowed (%d)",
 103                                                         (int) MaxArraySize)));
 104         }
 105         Assert(ret >= 0);
 106         if ((Size) ret > MaxArraySize)
 107                 ereport(ERROR,
 108                                 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
 109                                  errmsg("array size exceeds the maximum allowed (%d)",
 110                                                 (int) MaxArraySize)));
 111         return (int) ret;
 112 }
 113
 114 /*
 115  * Compute ranges (sub-array dimensions) for an array slice
 116  *
 117  * We assume caller has validated slice endpoints, so overflow is impossible
 118  */
 119 void
 120 mda_get_range(int n, int *span, const int *st, const int *endp)
 121 {
 122         int                     i;
 123
 124         for (i = 0; i < n; i++)
 125                 span[i] = endp[i] - st[i] + 1;
 126 }
 127
 128 /*
 129  * Compute products of array dimensions, ie, scale factors for subscripts
 130  *
 131  * We assume caller has validated dimensions, so overflow is impossible
 132  */
 133 void
 134 mda_get_prod(int n, const int *range, int *prod)
 135 {
 136         int                     i;
 137
 138         prod[n - 1] = 1;
 139         for (i = n - 2; i >= 0; i--)
 140                 prod[i] = prod[i + 1] * range[i + 1];
 141 }
 142
 143 /*
 144  * From products of whole-array dimensions and spans of a sub-array,
 145  * compute offset distances needed to step through subarray within array
 146  *
 147  * We assume caller has validated dimensions, so overflow is impossible
 148  */
 149 void
 150 mda_get_offset_values(int n, int *dist, const int *prod, const int *span)
 151 {
 152         int                     i,
 153                                 j;
 154
 155         dist[n - 1] = 0;
 156         for (j = n - 2; j >= 0; j--)
 157         {
 158                 dist[j] = prod[j] - 1;
 159                 for (i = j + 1; i < n; i++)
 160                         dist[j] -= (span[i] - 1) * prod[i];
 161         }
 162 }
 163
 164 /*
 165  * Generates the tuple that is lexicographically one greater than the current
 166  * n-tuple in "curr", with the restriction that the i-th element of "curr" is
 167  * less than the i-th element of "span".
 168  *
 169  * Returns -1 if no next tuple exists, else the subscript position (0..n-1)
 170  * corresponding to the dimension to advance along.
 171  *
 172  * We assume caller has validated dimensions, so overflow is impossible
 173  */
 174 int
 175 mda_next_tuple(int n, int *curr, const int *span)
 176 {
 177         int                     i;
 178
 179         if (n <= 0)
 180                 return -1;
 181
 182         curr[n - 1] = (curr[n - 1] + 1) % span[n - 1];
 183         for (i = n - 1; i && curr[i] == 0; i--)
 184                 curr[i - 1] = (curr[i - 1] + 1) % span[i - 1];
 185
 186         if (i)
 187                 return i;
 188         if (curr[0])
 189                 return 0;
 190
 191         return -1;
 192 }
 193
 194 /*
 195  * ArrayGetIntegerTypmods: verify that argument is a 1-D cstring array,
 196  * and get the contents converted to integers.  Returns a palloc'd array
 197  * and places the length at *n.
 198  */
 199 int32 *
 200 ArrayGetIntegerTypmods(ArrayType *arr, int *n)
 201 {
 202         int32      *result;
 203         Datum      *elem_values;
 204         int                     i;
 205
 206         if (ARR_ELEMTYPE(arr) != CSTRINGOID)
 207                 ereport(ERROR,
 208                                 (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
 209                                  errmsg("typmod array must be type cstring[]")));
 210
 211         if (ARR_NDIM(arr) != 1)
 212                 ereport(ERROR,
 213                                 (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
 214                                  errmsg("typmod array must be one-dimensional")));
 215
 216         if (array_contains_nulls(arr))
 217                 ereport(ERROR,
 218                                 (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
 219                                  errmsg("typmod array must not contain nulls")));
 220
 221         /* hardwired knowledge about cstring's representation details here */
 222         deconstruct_array(arr, CSTRINGOID,
 223                                           -2, false, 'c',
 224                                           &elem_values, NULL, n);
 225
 226         result = (int32 *) palloc(*n * sizeof(int32));
 227
 228         for (i = 0; i < *n; i++)
 229                 result[i] = pg_atoi(DatumGetCString(elem_values[i]),
 230                                                         sizeof(int32), '\0');
 231
 232         pfree(elem_values);
 233
 234         return result;
 235 }