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-2024, 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  * Convert array dimensions into number of elements
48  *
49  * This must do overflow checking, since it is used to validate that a user
50  * dimensionality request doesn't overflow what we can handle.
51  *
52  * The multiplication overflow check only works on machines that have int64
53  * arithmetic, but that is nearly all platforms these days, and doing check
54  * divides for those that don't seems way too expensive.
55  */
56 int
57 ArrayGetNItems(int ndim, const int *dims)
58 {
59  return ArrayGetNItemsSafe(ndim, dims, NULL);
60 }
61 
62 /*
63  * This entry point can return the error into an ErrorSaveContext
64  * instead of throwing an exception. -1 is returned after an error.
65  */
66 int
67 ArrayGetNItemsSafe(int ndim, const int *dims, struct Node *escontext)
68 {
69  int32 ret;
70  int i;
71 
72  if (ndim <= 0)
73  return 0;
74  ret = 1;
75  for (i = 0; i < ndim; i++)
76  {
77  int64 prod;
78 
79  /* A negative dimension implies that UB-LB overflowed ... */
80  if (dims[i] < 0)
81  ereturn(escontext, -1,
82  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
83  errmsg("array size exceeds the maximum allowed (%d)",
84  (int) MaxArraySize)));
85 
86  prod = (int64) ret * (int64) dims[i];
87 
88  ret = (int32) prod;
89  if ((int64) ret != prod)
90  ereturn(escontext, -1,
91  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
92  errmsg("array size exceeds the maximum allowed (%d)",
93  (int) MaxArraySize)));
94  }
95  Assert(ret >= 0);
96  if ((Size) ret > MaxArraySize)
97  ereturn(escontext, -1,
98  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
99  errmsg("array size exceeds the maximum allowed (%d)",
100  (int) MaxArraySize)));
101  return (int) ret;
102 }
103 
104 /*
105  * Verify sanity of proposed lower-bound values for an array
106  *
107  * The lower-bound values must not be so large as to cause overflow when
108  * calculating subscripts, e.g. lower bound 2147483640 with length 10
109  * must be disallowed. We actually insist that dims[i] + lb[i] be
110  * computable without overflow, meaning that an array with last subscript
111  * equal to INT_MAX will be disallowed.
112  *
113  * It is assumed that the caller already called ArrayGetNItems, so that
114  * overflowed (negative) dims[] values have been eliminated.
115  */
116 void
117 ArrayCheckBounds(int ndim, const int *dims, const int *lb)
118 {
119  (void) ArrayCheckBoundsSafe(ndim, dims, lb, NULL);
120 }
121 
122 /*
123  * This entry point can return the error into an ErrorSaveContext
124  * instead of throwing an exception.
125  */
126 bool
127 ArrayCheckBoundsSafe(int ndim, const int *dims, const int *lb,
128  struct Node *escontext)
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  ereturn(escontext, false,
139  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
140  errmsg("array lower bound is too large: %d",
141  lb[i])));
142  }
143 
144  return true;
145 }
146 
147 /*
148  * Compute ranges (sub-array dimensions) for an array slice
149  *
150  * We assume caller has validated slice endpoints, so overflow is impossible
151  */
152 void
153 mda_get_range(int n, int *span, const int *st, const int *endp)
154 {
155  int i;
156 
157  for (i = 0; i < n; i++)
158  span[i] = endp[i] - st[i] + 1;
159 }
160 
161 /*
162  * Compute products of array dimensions, ie, scale factors for subscripts
163  *
164  * We assume caller has validated dimensions, so overflow is impossible
165  */
166 void
167 mda_get_prod(int n, const int *range, int *prod)
168 {
169  int i;
170 
171  prod[n - 1] = 1;
172  for (i = n - 2; i >= 0; i--)
173  prod[i] = prod[i + 1] * range[i + 1];
174 }
175 
176 /*
177  * From products of whole-array dimensions and spans of a sub-array,
178  * compute offset distances needed to step through subarray within array
179  *
180  * We assume caller has validated dimensions, so overflow is impossible
181  */
182 void
183 mda_get_offset_values(int n, int *dist, const int *prod, const int *span)
184 {
185  int i,
186  j;
187 
188  dist[n - 1] = 0;
189  for (j = n - 2; j >= 0; j--)
190  {
191  dist[j] = prod[j] - 1;
192  for (i = j + 1; i < n; i++)
193  dist[j] -= (span[i] - 1) * prod[i];
194  }
195 }
196 
197 /*
198  * Generates the tuple that is lexicographically one greater than the current
199  * n-tuple in "curr", with the restriction that the i-th element of "curr" is
200  * less than the i-th element of "span".
201  *
202  * Returns -1 if no next tuple exists, else the subscript position (0..n-1)
203  * corresponding to the dimension to advance along.
204  *
205  * We assume caller has validated dimensions, so overflow is impossible
206  */
207 int
208 mda_next_tuple(int n, int *curr, const int *span)
209 {
210  int i;
211 
212  if (n <= 0)
213  return -1;
214 
215  curr[n - 1] = (curr[n - 1] + 1) % span[n - 1];
216  for (i = n - 1; i && curr[i] == 0; i--)
217  curr[i - 1] = (curr[i - 1] + 1) % span[i - 1];
218 
219  if (i)
220  return i;
221  if (curr[0])
222  return 0;
223 
224  return -1;
225 }
226 
227 /*
228  * ArrayGetIntegerTypmods: verify that argument is a 1-D cstring array,
229  * and get the contents converted to integers. Returns a palloc'd array
230  * and places the length at *n.
231  */
232 int32 *
234 {
235  int32 *result;
236  Datum *elem_values;
237  int i;
238 
239  if (ARR_ELEMTYPE(arr) != CSTRINGOID)
240  ereport(ERROR,
241  (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
242  errmsg("typmod array must be type cstring[]")));
243 
244  if (ARR_NDIM(arr) != 1)
245  ereport(ERROR,
246  (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
247  errmsg("typmod array must be one-dimensional")));
248 
249  if (array_contains_nulls(arr))
250  ereport(ERROR,
251  (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
252  errmsg("typmod array must not contain nulls")));
253 
254  deconstruct_array_builtin(arr, CSTRINGOID, &elem_values, NULL, n);
255 
256  result = (int32 *) palloc(*n * sizeof(int32));
257 
258  for (i = 0; i < *n; i++)
259  result[i] = pg_strtoint32(DatumGetCString(elem_values[i]));
260 
261  pfree(elem_values);
262 
263  return result;
264 }
#define ARR_NDIM(a)
Definition: array.h:290
#define MaxArraySize
Definition: array.h:82
#define ARR_ELEMTYPE(a)
Definition: array.h:292
bool array_contains_nulls(ArrayType *array)
Definition: arrayfuncs.c:3749
void deconstruct_array_builtin(ArrayType *array, Oid elmtype, Datum **elemsp, bool **nullsp, int *nelemsp)
Definition: arrayfuncs.c:3679
void mda_get_offset_values(int n, int *dist, const int *prod, const int *span)
Definition: arrayutils.c:183
int ArrayGetNItemsSafe(int ndim, const int *dims, struct Node *escontext)
Definition: arrayutils.c:67
bool ArrayCheckBoundsSafe(int ndim, const int *dims, const int *lb, struct Node *escontext)
Definition: arrayutils.c:127
int ArrayGetOffset(int n, const int *dim, const int *lb, const int *indx)
Definition: arrayutils.c:32
void mda_get_range(int n, int *span, const int *st, const int *endp)
Definition: arrayutils.c:153
int ArrayGetNItems(int ndim, const int *dims)
Definition: arrayutils.c:57
void mda_get_prod(int n, const int *range, int *prod)
Definition: arrayutils.c:167
void ArrayCheckBounds(int ndim, const int *dims, const int *lb)
Definition: arrayutils.c:117
int mda_next_tuple(int n, int *curr, const int *span)
Definition: arrayutils.c:208
int32 * ArrayGetIntegerTypmods(ArrayType *arr, int *n)
Definition: arrayutils.c:233
signed int int32
Definition: c.h:483
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:171
size_t Size
Definition: c.h:594
int errcode(int sqlerrcode)
Definition: elog.c:860
int errmsg(const char *fmt,...)
Definition: elog.c:1075
#define ereturn(context, dummy_value,...)
Definition: elog.h:276
#define ERROR
Definition: elog.h:39
#define ereport(elevel,...)
Definition: elog.h:149
static bool pg_add_s32_overflow(int32 a, int32 b, int32 *result)
Definition: int.h:104
int j
Definition: isn.c:74
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
void pfree(void *pointer)
Definition: mcxt.c:1431
void * palloc(Size size)
Definition: mcxt.c:1201
int32 pg_strtoint32(const char *s)
Definition: numutils.c:384
int scale
Definition: pgbench.c:181
static char * DatumGetCString(Datum X)
Definition: postgres.h:335
uintptr_t Datum
Definition: postgres.h:64
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:412
Definition: nodes.h:129