PostgreSQL Source Code  git master
arrayutils.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * arrayutils.c
4  * This file contains some support routines required for array functions.
5  *
6  * Portions Copyright (c) 1996-2021, 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 "common/int.h"
20 #include "utils/array.h"
21 #include "utils/builtins.h"
22 #include "utils/memutils.h"
23 
24 
25 /*
26  * Convert subscript list into linear element number (from 0)
27  *
28  * We assume caller has already range-checked the dimensions and subscripts,
29  * so no overflow is possible.
30  */
31 int
32 ArrayGetOffset(int n, const int *dim, const int *lb, const int *indx)
33 {
34  int i,
35  scale = 1,
36  offset = 0;
37 
38  for (i = n - 1; i >= 0; i--)
39  {
40  offset += (indx[i] - lb[i]) * scale;
41  scale *= dim[i];
42  }
43  return offset;
44 }
45 
46 /*
47  * Same, but subscripts are assumed 0-based, and use a scale array
48  * instead of raw dimension data (see mda_get_prod to create scale array)
49  */
50 int
51 ArrayGetOffset0(int n, const int *tup, const int *scale)
52 {
53  int i,
54  lin = 0;
55 
56  for (i = 0; i < n; i++)
57  lin += tup[i] * scale[i];
58  return lin;
59 }
60 
61 /*
62  * Convert array dimensions into number of elements
63  *
64  * This must do overflow checking, since it is used to validate that a user
65  * dimensionality request doesn't overflow what we can handle.
66  *
67  * We limit array sizes to at most about a quarter billion elements,
68  * so that it's not necessary to check for overflow in quite so many
69  * places --- for instance when palloc'ing Datum arrays.
70  *
71  * The multiplication overflow check only works on machines that have int64
72  * arithmetic, but that is nearly all platforms these days, and doing check
73  * divides for those that don't seems way too expensive.
74  */
75 int
76 ArrayGetNItems(int ndim, const int *dims)
77 {
78  int32 ret;
79  int i;
80 
81 #define MaxArraySize ((Size) (MaxAllocSize / sizeof(Datum)))
82 
83  if (ndim <= 0)
84  return 0;
85  ret = 1;
86  for (i = 0; i < ndim; i++)
87  {
88  int64 prod;
89 
90  /* A negative dimension implies that UB-LB overflowed ... */
91  if (dims[i] < 0)
92  ereport(ERROR,
93  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
94  errmsg("array size exceeds the maximum allowed (%d)",
95  (int) MaxArraySize)));
96 
97  prod = (int64) ret * (int64) dims[i];
98 
99  ret = (int32) prod;
100  if ((int64) ret != prod)
101  ereport(ERROR,
102  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
103  errmsg("array size exceeds the maximum allowed (%d)",
104  (int) MaxArraySize)));
105  }
106  Assert(ret >= 0);
107  if ((Size) ret > MaxArraySize)
108  ereport(ERROR,
109  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
110  errmsg("array size exceeds the maximum allowed (%d)",
111  (int) MaxArraySize)));
112  return (int) ret;
113 }
114 
115 /*
116  * Verify sanity of proposed lower-bound values for an array
117  *
118  * The lower-bound values must not be so large as to cause overflow when
119  * calculating subscripts, e.g. lower bound 2147483640 with length 10
120  * must be disallowed. We actually insist that dims[i] + lb[i] be
121  * computable without overflow, meaning that an array with last subscript
122  * equal to INT_MAX will be disallowed.
123  *
124  * It is assumed that the caller already called ArrayGetNItems, so that
125  * overflowed (negative) dims[] values have been eliminated.
126  */
127 void
128 ArrayCheckBounds(int ndim, const int *dims, const int *lb)
129 {
130  int i;
131 
132  for (i = 0; i < ndim; i++)
133  {
134  /* PG_USED_FOR_ASSERTS_ONLY prevents variable-isn't-read warnings */
136 
137  if (pg_add_s32_overflow(dims[i], lb[i], &sum))
138  ereport(ERROR,
139  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
140  errmsg("array lower bound is too large: %d",
141  lb[i])));
142  }
143 }
144 
145 /*
146  * Compute ranges (sub-array dimensions) for an array slice
147  *
148  * We assume caller has validated slice endpoints, so overflow is impossible
149  */
150 void
151 mda_get_range(int n, int *span, const int *st, const int *endp)
152 {
153  int i;
154 
155  for (i = 0; i < n; i++)
156  span[i] = endp[i] - st[i] + 1;
157 }
158 
159 /*
160  * Compute products of array dimensions, ie, scale factors for subscripts
161  *
162  * We assume caller has validated dimensions, so overflow is impossible
163  */
164 void
165 mda_get_prod(int n, const int *range, int *prod)
166 {
167  int i;
168 
169  prod[n - 1] = 1;
170  for (i = n - 2; i >= 0; i--)
171  prod[i] = prod[i + 1] * range[i + 1];
172 }
173 
174 /*
175  * From products of whole-array dimensions and spans of a sub-array,
176  * compute offset distances needed to step through subarray within array
177  *
178  * We assume caller has validated dimensions, so overflow is impossible
179  */
180 void
181 mda_get_offset_values(int n, int *dist, const int *prod, const int *span)
182 {
183  int i,
184  j;
185 
186  dist[n - 1] = 0;
187  for (j = n - 2; j >= 0; j--)
188  {
189  dist[j] = prod[j] - 1;
190  for (i = j + 1; i < n; i++)
191  dist[j] -= (span[i] - 1) * prod[i];
192  }
193 }
194 
195 /*
196  * Generates the tuple that is lexicographically one greater than the current
197  * n-tuple in "curr", with the restriction that the i-th element of "curr" is
198  * less than the i-th element of "span".
199  *
200  * Returns -1 if no next tuple exists, else the subscript position (0..n-1)
201  * corresponding to the dimension to advance along.
202  *
203  * We assume caller has validated dimensions, so overflow is impossible
204  */
205 int
206 mda_next_tuple(int n, int *curr, const int *span)
207 {
208  int i;
209 
210  if (n <= 0)
211  return -1;
212 
213  curr[n - 1] = (curr[n - 1] + 1) % span[n - 1];
214  for (i = n - 1; i && curr[i] == 0; i--)
215  curr[i - 1] = (curr[i - 1] + 1) % span[i - 1];
216 
217  if (i)
218  return i;
219  if (curr[0])
220  return 0;
221 
222  return -1;
223 }
224 
225 /*
226  * ArrayGetIntegerTypmods: verify that argument is a 1-D cstring array,
227  * and get the contents converted to integers. Returns a palloc'd array
228  * and places the length at *n.
229  */
230 int32 *
232 {
233  int32 *result;
234  Datum *elem_values;
235  int i;
236 
237  if (ARR_ELEMTYPE(arr) != CSTRINGOID)
238  ereport(ERROR,
239  (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
240  errmsg("typmod array must be type cstring[]")));
241 
242  if (ARR_NDIM(arr) != 1)
243  ereport(ERROR,
244  (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
245  errmsg("typmod array must be one-dimensional")));
246 
247  if (array_contains_nulls(arr))
248  ereport(ERROR,
249  (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
250  errmsg("typmod array must not contain nulls")));
251 
252  /* hardwired knowledge about cstring's representation details here */
253  deconstruct_array(arr, CSTRINGOID,
254  -2, false, TYPALIGN_CHAR,
255  &elem_values, NULL, n);
256 
257  result = (int32 *) palloc(*n * sizeof(int32));
258 
259  for (i = 0; i < *n; i++)
260  result[i] = pg_strtoint32(DatumGetCString(elem_values[i]));
261 
262  pfree(elem_values);
263 
264  return result;
265 }
int ArrayGetOffset(int n, const int *dim, const int *lb, const int *indx)
Definition: arrayutils.c:32
void mda_get_prod(int n, const int *range, int *prod)
Definition: arrayutils.c:165
int32 * ArrayGetIntegerTypmods(ArrayType *arr, int *n)
Definition: arrayutils.c:231
int ArrayGetNItems(int ndim, const int *dims)
Definition: arrayutils.c:76
#define MaxArraySize
int errcode(int sqlerrcode)
Definition: elog.c:698
int scale
Definition: pgbench.c:191
signed int int32
Definition: c.h:429
void pfree(void *pointer)
Definition: mcxt.c:1169
#define ERROR
Definition: elog.h:46
#define DatumGetCString(X)
Definition: postgres.h:610
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:412
void mda_get_offset_values(int n, int *dist, const int *prod, const int *span)
Definition: arrayutils.c:181
void ArrayCheckBounds(int ndim, const int *dims, const int *lb)
Definition: arrayutils.c:128
uintptr_t Datum
Definition: postgres.h:411
void mda_get_range(int n, int *span, const int *st, const int *endp)
Definition: arrayutils.c:151
#define ereport(elevel,...)
Definition: elog.h:157
#define Assert(condition)
Definition: c.h:804
static bool pg_add_s32_overflow(int32 a, int32 b, int32 *result)
Definition: int.h:104
size_t Size
Definition: c.h:540
#define ARR_NDIM(a)
Definition: array.h:283
int32 pg_strtoint32(const char *s)
Definition: numutils.c:263
void deconstruct_array(ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)
Definition: arrayfuncs.c:3491
int mda_next_tuple(int n, int *curr, const int *span)
Definition: arrayutils.c:206
void * palloc(Size size)
Definition: mcxt.c:1062
int errmsg(const char *fmt,...)
Definition: elog.c:909
int i
bool array_contains_nulls(ArrayType *array)
Definition: arrayfuncs.c:3558
#define ARR_ELEMTYPE(a)
Definition: array.h:285
int ArrayGetOffset0(int n, const int *tup, const int *scale)
Definition: arrayutils.c:51
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:155