1 /*-------------------------------------------------------------------------
2 *
3 * arrayutils.c
4 * This file contains some support routines required for array functions.
5 *
6 * Portions Copyright (c) 1996-2018, 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
ArrayGetOffset(int n,const int * dim,const int * lb,const int * indx)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
ArrayGetOffset0(int n,const int * tup,const int * scale)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
ArrayGetNItems(int ndim,const int * dims)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
ArrayCheckBounds(int ndim,const int * dims,const int * lb)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 */
135 int32 sum PG_USED_FOR_ASSERTS_ONLY;
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
mda_get_range(int n,int * span,const int * st,const int * endp)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
mda_get_prod(int n,const int * range,int * prod)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
mda_get_offset_values(int n,int * dist,const int * prod,const int * span)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
mda_next_tuple(int n,int * curr,const int * span)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 *
ArrayGetIntegerTypmods(ArrayType * arr,int * n)231 ArrayGetIntegerTypmods(ArrayType *arr, int *n)
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, 'c',
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_atoi(DatumGetCString(elem_values[i]),
261 sizeof(int32), '\0');
262
263 pfree(elem_values);
264
265 return result;
266 }
267