Age Owner TLA Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * arrayutils.c
4 : * This file contains some support routines required for array functions.
5 : *
6 : * Portions Copyright (c) 1996-2023, 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
6352 tgl 32 CBC 346148 : ArrayGetOffset(int n, const int *dim, const int *lb, const int *indx)
33 : {
34 : int i,
8296 35 346148 : scale = 1,
36 346148 : offset = 0;
37 :
38 692455 : for (i = n - 1; i >= 0; i--)
39 : {
9345 bruce 40 346307 : offset += (indx[i] - lb[i]) * scale;
8296 tgl 41 346307 : scale *= dim[i];
42 : }
9345 bruce 43 346148 : 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
6352 tgl 51 889351 : ArrayGetOffset0(int n, const int *tup, const int *scale)
52 : {
53 : int i,
8296 54 889351 : lin = 0;
55 :
56 1780047 : for (i = 0; i < n; i++)
57 890696 : lin += tup[i] * scale[i];
58 889351 : 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
6352 76 41421889 : ArrayGetNItems(int ndim, const int *dims)
77 : {
121 tgl 78 GNC 41421889 : return ArrayGetNItemsSafe(ndim, dims, NULL);
79 : }
80 :
81 : /*
82 : * This entry point can return the error into an ErrorSaveContext
83 : * instead of throwing an exception. -1 is returned after an error.
84 : */
85 : int
86 41604181 : ArrayGetNItemsSafe(int ndim, const int *dims, struct Node *escontext)
87 : {
6352 tgl 88 ECB : int32 ret;
89 : int i;
90 :
91 : #define MaxArraySize ((Size) (MaxAllocSize / sizeof(Datum)))
92 :
6779 neilc 93 GIC 41604181 : if (ndim <= 0)
8296 tgl 94 1189582 : return 0;
95 40414599 : ret = 1;
6779 neilc 96 CBC 80831331 : for (i = 0; i < ndim; i++)
97 : {
98 : int64 prod;
99 :
100 : /* A negative dimension implies that UB-LB overflowed ... */
6352 tgl 101 GIC 40416732 : if (dims[i] < 0)
121 tgl 102 UNC 0 : ereturn(escontext, -1,
6352 tgl 103 ECB : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
104 : errmsg("array size exceeds the maximum allowed (%d)",
105 : (int) MaxArraySize)));
106 :
2118 tgl 107 GIC 40416732 : prod = (int64) ret * (int64) dims[i];
108 :
6352 109 40416732 : ret = (int32) prod;
110 40416732 : if ((int64) ret != prod)
121 tgl 111 UNC 0 : ereturn(escontext, -1,
6352 tgl 112 EUB : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
113 : errmsg("array size exceeds the maximum allowed (%d)",
114 : (int) MaxArraySize)));
115 : }
6352 tgl 116 GIC 40414599 : Assert(ret >= 0);
6352 tgl 117 CBC 40414599 : if ((Size) ret > MaxArraySize)
121 tgl 118 UNC 0 : ereturn(escontext, -1,
6352 tgl 119 ECB : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
120 : errmsg("array size exceeds the maximum allowed (%d)",
6352 tgl 121 EUB : (int) MaxArraySize)));
6352 tgl 122 GIC 40414599 : return (int) ret;
123 : }
124 :
125 : /*
699 tgl 126 ECB : * Verify sanity of proposed lower-bound values for an array
127 : *
699 tgl 128 EUB : * The lower-bound values must not be so large as to cause overflow when
129 : * calculating subscripts, e.g. lower bound 2147483640 with length 10
130 : * must be disallowed. We actually insist that dims[i] + lb[i] be
131 : * computable without overflow, meaning that an array with last subscript
699 tgl 132 ECB : * equal to INT_MAX will be disallowed.
133 : *
134 : * It is assumed that the caller already called ArrayGetNItems, so that
135 : * overflowed (negative) dims[] values have been eliminated.
136 : */
137 : void
699 tgl 138 GIC 1005046 : ArrayCheckBounds(int ndim, const int *dims, const int *lb)
139 : {
121 tgl 140 GNC 1005046 : (void) ArrayCheckBoundsSafe(ndim, dims, lb, NULL);
141 1005046 : }
142 :
143 : /*
144 : * This entry point can return the error into an ErrorSaveContext
145 : * instead of throwing an exception.
146 : */
147 : bool
148 1187338 : ArrayCheckBoundsSafe(int ndim, const int *dims, const int *lb,
149 : struct Node *escontext)
150 : {
151 : int i;
152 :
699 tgl 153 GIC 2353478 : for (i = 0; i < ndim; i++)
154 : {
155 : /* PG_USED_FOR_ASSERTS_ONLY prevents variable-isn't-read warnings */
156 : int32 sum PG_USED_FOR_ASSERTS_ONLY;
157 :
158 1166140 : if (pg_add_s32_overflow(dims[i], lb[i], &sum))
121 tgl 159 UNC 0 : ereturn(escontext, false,
160 : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
699 tgl 161 ECB : errmsg("array lower bound is too large: %d",
162 : lb[i])));
163 : }
164 :
121 tgl 165 GNC 1187338 : return true;
166 : }
167 :
168 : /*
169 : * Compute ranges (sub-array dimensions) for an array slice
170 : *
6352 tgl 171 ECB : * We assume caller has validated slice endpoints, so overflow is impossible
172 : */
173 : void
6352 tgl 174 GIC 508 : mda_get_range(int n, int *span, const int *st, const int *endp)
175 : {
9344 bruce 176 ECB : int i;
177 :
9345 bruce 178 GIC 1277 : for (i = 0; i < n; i++)
179 769 : span[i] = endp[i] - st[i] + 1;
180 508 : }
9770 scrappy 181 ECB :
6352 tgl 182 EUB : /*
183 : * Compute products of array dimensions, ie, scale factors for subscripts
184 : *
185 : * We assume caller has validated dimensions, so overflow is impossible
186 : */
187 : void
6352 tgl 188 CBC 178929 : mda_get_prod(int n, const int *range, int *prod)
189 : {
190 : int i;
191 :
8296 tgl 192 GIC 178929 : prod[n - 1] = 1;
193 179245 : for (i = n - 2; i >= 0; i--)
194 316 : prod[i] = prod[i + 1] * range[i + 1];
9345 bruce 195 178929 : }
196 :
6352 tgl 197 ECB : /*
198 : * From products of whole-array dimensions and spans of a sub-array,
199 : * compute offset distances needed to step through subarray within array
200 : *
201 : * We assume caller has validated dimensions, so overflow is impossible
8296 202 : */
9770 scrappy 203 : void
6352 tgl 204 GIC 180 : mda_get_offset_values(int n, int *dist, const int *prod, const int *span)
205 : {
206 : int i,
207 : j;
208 :
8296 209 180 : dist[n - 1] = 0;
210 288 : for (j = n - 2; j >= 0; j--)
8296 tgl 211 ECB : {
8296 tgl 212 GIC 108 : dist[j] = prod[j] - 1;
213 231 : for (i = j + 1; i < n; i++)
214 123 : dist[j] -= (span[i] - 1) * prod[i];
8296 tgl 215 ECB : }
9770 scrappy 216 CBC 180 : }
9770 scrappy 217 ECB :
6352 tgl 218 : /*
219 : * Generates the tuple that is lexicographically one greater than the current
220 : * n-tuple in "curr", with the restriction that the i-th element of "curr" is
221 : * less than the i-th element of "span".
222 : *
223 : * Returns -1 if no next tuple exists, else the subscript position (0..n-1)
224 : * corresponding to the dimension to advance along.
225 : *
226 : * We assume caller has validated dimensions, so overflow is impossible
227 : */
228 : int
6352 tgl 229 GIC 645 : mda_next_tuple(int n, int *curr, const int *span)
230 : {
231 : int i;
9770 scrappy 232 ECB :
8296 tgl 233 CBC 645 : if (n <= 0)
8986 bruce 234 UIC 0 : return -1;
8296 tgl 235 ECB :
9345 bruce 236 CBC 645 : curr[n - 1] = (curr[n - 1] + 1) % span[n - 1];
8296 tgl 237 804 : for (i = n - 1; i && curr[i] == 0; i--)
9345 bruce 238 GIC 159 : curr[i - 1] = (curr[i - 1] + 1) % span[i - 1];
9345 bruce 239 ECB :
9345 bruce 240 GIC 645 : if (i)
8986 241 165 : return i;
9345 242 480 : if (curr[0])
8986 243 300 : return 0;
244 :
245 180 : return -1;
246 : }
247 :
248 : /*
249 : * ArrayGetIntegerTypmods: verify that argument is a 1-D cstring array,
250 : * and get the contents converted to integers. Returns a palloc'd array
251 : * and places the length at *n.
5944 tgl 252 ECB : */
253 : int32 *
5777 tgl 254 GIC 4378 : ArrayGetIntegerTypmods(ArrayType *arr, int *n)
255 : {
5777 tgl 256 ECB : int32 *result;
5777 tgl 257 EUB : Datum *elem_values;
258 : int i;
5777 tgl 259 ECB :
5777 tgl 260 CBC 4378 : if (ARR_ELEMTYPE(arr) != CSTRINGOID)
5944 tgl 261 LBC 0 : ereport(ERROR,
262 : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
5777 tgl 263 ECB : errmsg("typmod array must be type cstring[]")));
5944 264 :
5944 tgl 265 CBC 4378 : if (ARR_NDIM(arr) != 1)
5944 tgl 266 LBC 0 : ereport(ERROR,
267 : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
5944 tgl 268 ECB : errmsg("typmod array must be one-dimensional")));
269 :
4473 tgl 270 GIC 4378 : if (array_contains_nulls(arr))
5944 tgl 271 UIC 0 : ereport(ERROR,
272 : (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
273 : errmsg("typmod array must not contain nulls")));
274 :
282 peter 275 GNC 4378 : deconstruct_array_builtin(arr, CSTRINGOID, &elem_values, NULL, n);
276 :
5777 tgl 277 GIC 4378 : result = (int32 *) palloc(*n * sizeof(int32));
278 :
279 9713 : for (i = 0; i < *n; i++)
1722 andres 280 CBC 5335 : result[i] = pg_strtoint32(DatumGetCString(elem_values[i]));
5777 tgl 281 EUB :
5777 tgl 282 GIC 4378 : pfree(elem_values);
283 :
284 4378 : return result;
5944 tgl 285 ECB : }
|
