Age Owner Branch data 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-2025, 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
7233 tgl@sss.pgh.pa.us 32 :CBC 401258 : ArrayGetOffset(int n, const int *dim, const int *lb, const int *indx)
33 : : {
34 : : int i,
9177 35 : 401258 : scale = 1,
36 : 401258 : offset = 0;
37 : :
38 [ + + ]: 802681 : for (i = n - 1; i >= 0; i--)
39 : : {
10226 bruce@momjian.us 40 : 401423 : offset += (indx[i] - lb[i]) * scale;
9177 tgl@sss.pgh.pa.us 41 : 401423 : scale *= dim[i];
42 : : }
10226 bruce@momjian.us 43 : 401258 : 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
7233 tgl@sss.pgh.pa.us 57 : 48317499 : ArrayGetNItems(int ndim, const int *dims)
58 : : {
1002 59 : 48317499 : 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 : 48317499 : ArrayGetNItemsSafe(int ndim, const int *dims, struct Node *escontext)
68 : : {
69 : : int32 ret;
70 : : int i;
71 : :
7660 neilc@samurai.com 72 [ + + ]: 48317499 : if (ndim <= 0)
9177 tgl@sss.pgh.pa.us 73 : 1515969 : return 0;
74 : 46801530 : ret = 1;
7660 neilc@samurai.com 75 [ + + ]: 93605096 : for (i = 0; i < ndim; i++)
76 : : {
77 : : int64 prod;
78 : :
79 : : /* A negative dimension implies that UB-LB overflowed ... */
7233 tgl@sss.pgh.pa.us 80 [ - + ]: 46803566 : if (dims[i] < 0)
1002 tgl@sss.pgh.pa.us 81 [ # # ]:UBC 0 : ereturn(escontext, -1,
82 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
83 : : errmsg("array size exceeds the maximum allowed (%d)",
84 : : (int) MaxArraySize)));
85 : :
2999 tgl@sss.pgh.pa.us 86 :CBC 46803566 : prod = (int64) ret * (int64) dims[i];
87 : :
7233 88 : 46803566 : ret = (int32) prod;
89 [ - + ]: 46803566 : if ((int64) ret != prod)
1002 tgl@sss.pgh.pa.us 90 [ # # ]:UBC 0 : ereturn(escontext, -1,
91 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
92 : : errmsg("array size exceeds the maximum allowed (%d)",
93 : : (int) MaxArraySize)));
94 : : }
7233 tgl@sss.pgh.pa.us 95 [ - + ]:CBC 46801530 : Assert(ret >= 0);
96 [ - + ]: 46801530 : if ((Size) ret > MaxArraySize)
1002 tgl@sss.pgh.pa.us 97 [ # # ]:UBC 0 : ereturn(escontext, -1,
98 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
99 : : errmsg("array size exceeds the maximum allowed (%d)",
100 : : (int) MaxArraySize)));
7233 tgl@sss.pgh.pa.us 101 :CBC 46801530 : 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
1580 117 : 797853 : ArrayCheckBounds(int ndim, const int *dims, const int *lb)
118 : : {
1002 119 : 797853 : (void) ArrayCheckBoundsSafe(ndim, dims, lb, NULL);
120 : 797853 : }
121 : :
122 : : /*
123 : : * This entry point can return the error into an ErrorSaveContext
124 : : * instead of throwing an exception.
125 : : */
126 : : bool
127 : 797853 : ArrayCheckBoundsSafe(int ndim, const int *dims, const int *lb,
128 : : struct Node *escontext)
129 : : {
130 : : int i;
131 : :
1580 132 [ + + ]: 1569682 : 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 [ - + ]: 771829 : if (pg_add_s32_overflow(dims[i], lb[i], &sum))
1002 tgl@sss.pgh.pa.us 138 [ # # ]:UBC 0 : ereturn(escontext, false,
139 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
140 : : errmsg("array lower bound is too large: %d",
141 : : lb[i])));
142 : : }
143 : :
1002 tgl@sss.pgh.pa.us 144 :CBC 797853 : 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
7233 153 : 526 : mda_get_range(int n, int *span, const int *st, const int *endp)
154 : : {
155 : : int i;
156 : :
10226 bruce@momjian.us 157 [ + + ]: 1331 : for (i = 0; i < n; i++)
158 : 805 : span[i] = endp[i] - st[i] + 1;
159 : 526 : }
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
7233 tgl@sss.pgh.pa.us 167 : 186 : mda_get_prod(int n, const int *range, int *prod)
168 : : {
169 : : int i;
170 : :
9177 171 : 186 : prod[n - 1] = 1;
172 [ + + ]: 300 : for (i = n - 2; i >= 0; i--)
173 : 114 : prod[i] = prod[i + 1] * range[i + 1];
10226 bruce@momjian.us 174 : 186 : }
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
7233 tgl@sss.pgh.pa.us 183 : 186 : mda_get_offset_values(int n, int *dist, const int *prod, const int *span)
184 : : {
185 : : int i,
186 : : j;
187 : :
9177 188 : 186 : dist[n - 1] = 0;
189 [ + + ]: 300 : for (j = n - 2; j >= 0; j--)
190 : : {
191 : 114 : dist[j] = prod[j] - 1;
192 [ + + ]: 243 : for (i = j + 1; i < n; i++)
193 : 129 : dist[j] -= (span[i] - 1) * prod[i];
194 : : }
10651 scrappy@hub.org 195 : 186 : }
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
7233 tgl@sss.pgh.pa.us 208 : 663 : mda_next_tuple(int n, int *curr, const int *span)
209 : : {
210 : : int i;
211 : :
9177 212 [ - + ]: 663 : if (n <= 0)
9867 bruce@momjian.us 213 :UBC 0 : return -1;
214 : :
10226 bruce@momjian.us 215 :CBC 663 : curr[n - 1] = (curr[n - 1] + 1) % span[n - 1];
9177 tgl@sss.pgh.pa.us 216 [ + + + + ]: 834 : for (i = n - 1; i && curr[i] == 0; i--)
10226 bruce@momjian.us 217 : 171 : curr[i - 1] = (curr[i - 1] + 1) % span[i - 1];
218 : :
219 [ + + ]: 663 : if (i)
9867 220 : 171 : return i;
10226 221 [ + + ]: 492 : if (curr[0])
9867 222 : 306 : return 0;
223 : :
224 : 186 : 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 *
6658 tgl@sss.pgh.pa.us 233 : 3869 : ArrayGetIntegerTypmods(ArrayType *arr, int *n)
234 : : {
235 : : int32 *result;
236 : : Datum *elem_values;
237 : : int i;
238 : :
239 [ - + ]: 3869 : if (ARR_ELEMTYPE(arr) != CSTRINGOID)
6825 tgl@sss.pgh.pa.us 240 [ # # ]:UBC 0 : ereport(ERROR,
241 : : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
242 : : errmsg("typmod array must be type cstring[]")));
243 : :
6825 tgl@sss.pgh.pa.us 244 [ - + ]:CBC 3869 : if (ARR_NDIM(arr) != 1)
6825 tgl@sss.pgh.pa.us 245 [ # # ]:UBC 0 : ereport(ERROR,
246 : : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
247 : : errmsg("typmod array must be one-dimensional")));
248 : :
5354 tgl@sss.pgh.pa.us 249 [ - + ]:CBC 3869 : if (array_contains_nulls(arr))
6825 tgl@sss.pgh.pa.us 250 [ # # ]:UBC 0 : ereport(ERROR,
251 : : (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
252 : : errmsg("typmod array must not contain nulls")));
253 : :
1163 peter@eisentraut.org 254 :CBC 3869 : deconstruct_array_builtin(arr, CSTRINGOID, &elem_values, NULL, n);
255 : :
6658 tgl@sss.pgh.pa.us 256 : 3869 : result = (int32 *) palloc(*n * sizeof(int32));
257 : :
258 [ + + ]: 8750 : for (i = 0; i < *n; i++)
2603 andres@anarazel.de 259 : 4881 : result[i] = pg_strtoint32(DatumGetCString(elem_values[i]));
260 : :
6658 tgl@sss.pgh.pa.us 261 : 3869 : pfree(elem_values);
262 : :
263 : 3869 : return result;
264 : : }
|
