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-2022, 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 634442 : ArrayGetOffset(int n, const int *dim, const int *lb, const int *indx)
33 : {
34 : int i,
35 634442 : scale = 1,
36 634442 : offset = 0;
37 :
38 1269202 : for (i = n - 1; i >= 0; i--)
39 : {
40 634760 : offset += (indx[i] - lb[i]) * scale;
41 634760 : scale *= dim[i];
42 : }
43 634442 : 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 1535342 : ArrayGetOffset0(int n, const int *tup, const int *scale)
52 : {
53 : int i,
54 1535342 : lin = 0;
55 :
56 3072990 : for (i = 0; i < n; i++)
57 1537648 : lin += tup[i] * scale[i];
58 1535342 : 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 76526150 : ArrayGetNItems(int ndim, const int *dims)
77 : {
78 : int32 ret;
79 : int i;
80 :
81 : #define MaxArraySize ((Size) (MaxAllocSize / sizeof(Datum)))
82 :
83 76526150 : if (ndim <= 0)
84 2332078 : return 0;
85 74194072 : ret = 1;
86 148392062 : for (i = 0; i < ndim; i++)
87 : {
88 : int64 prod;
89 :
90 : /* A negative dimension implies that UB-LB overflowed ... */
91 74197990 : if (dims[i] < 0)
92 0 : ereport(ERROR,
93 : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
94 : errmsg("array size exceeds the maximum allowed (%d)",
95 : (int) MaxArraySize)));
96 :
97 74197990 : prod = (int64) ret * (int64) dims[i];
98 :
99 74197990 : ret = (int32) prod;
100 74197990 : if ((int64) ret != prod)
101 0 : 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 74194072 : if ((Size) ret > MaxArraySize)
108 0 : ereport(ERROR,
109 : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
110 : errmsg("array size exceeds the maximum allowed (%d)",
111 : (int) MaxArraySize)));
112 74194072 : 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 2100866 : ArrayCheckBounds(int ndim, const int *dims, const int *lb)
129 : {
130 : int i;
131 :
132 4161372 : for (i = 0; i < ndim; i++)
133 : {
134 : /* PG_USED_FOR_ASSERTS_ONLY prevents variable-isn't-read warnings */
135 : int32 sum PG_USED_FOR_ASSERTS_ONLY;
136 :
137 2060506 : if (pg_add_s32_overflow(dims[i], lb[i], &sum))
138 0 : ereport(ERROR,
139 : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
140 : errmsg("array lower bound is too large: %d",
141 : lb[i])));
142 : }
143 2100866 : }
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 1016 : mda_get_range(int n, int *span, const int *st, const int *endp)
152 : {
153 : int i;
154 :
155 2554 : for (i = 0; i < n; i++)
156 1538 : span[i] = endp[i] - st[i] + 1;
157 1016 : }
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 320786 : mda_get_prod(int n, const int *range, int *prod)
166 : {
167 : int i;
168 :
169 320786 : prod[n - 1] = 1;
170 321382 : for (i = n - 2; i >= 0; i--)
171 596 : prod[i] = prod[i + 1] * range[i + 1];
172 320786 : }
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 360 : mda_get_offset_values(int n, int *dist, const int *prod, const int *span)
182 : {
183 : int i,
184 : j;
185 :
186 360 : dist[n - 1] = 0;
187 576 : for (j = n - 2; j >= 0; j--)
188 : {
189 216 : dist[j] = prod[j] - 1;
190 462 : for (i = j + 1; i < n; i++)
191 246 : dist[j] -= (span[i] - 1) * prod[i];
192 : }
193 360 : }
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 1290 : mda_next_tuple(int n, int *curr, const int *span)
207 : {
208 : int i;
209 :
210 1290 : if (n <= 0)
211 0 : return -1;
212 :
213 1290 : curr[n - 1] = (curr[n - 1] + 1) % span[n - 1];
214 1608 : for (i = n - 1; i && curr[i] == 0; i--)
215 318 : curr[i - 1] = (curr[i - 1] + 1) % span[i - 1];
216 :
217 1290 : if (i)
218 330 : return i;
219 960 : if (curr[0])
220 600 : return 0;
221 :
222 360 : 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 *
231 8492 : ArrayGetIntegerTypmods(ArrayType *arr, int *n)
232 : {
233 : int32 *result;
234 : Datum *elem_values;
235 : int i;
236 :
237 8492 : if (ARR_ELEMTYPE(arr) != CSTRINGOID)
238 0 : ereport(ERROR,
239 : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
240 : errmsg("typmod array must be type cstring[]")));
241 :
242 8492 : if (ARR_NDIM(arr) != 1)
243 0 : ereport(ERROR,
244 : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
245 : errmsg("typmod array must be one-dimensional")));
246 :
247 8492 : if (array_contains_nulls(arr))
248 0 : 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 8492 : deconstruct_array(arr, CSTRINGOID,
254 : -2, false, TYPALIGN_CHAR,
255 : &elem_values, NULL, n);
256 :
257 8492 : result = (int32 *) palloc(*n * sizeof(int32));
258 :
259 18872 : for (i = 0; i < *n; i++)
260 10380 : result[i] = pg_strtoint32(DatumGetCString(elem_values[i]));
261 :
262 8492 : pfree(elem_values);
263 :
264 8492 : return result;
265 : }
|
