1/*-------------------------------------------------------------------------
2 *
3 * arrayutils.c
4 * This file contains some support routines required for array functions.
5 *
6 * Portions Copyright (c) 1996-2019, 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 "utils/array.h"
20#include "utils/builtins.h"
21#include "utils/memutils.h"
22
23
24/*
25 * Convert subscript list into linear element number (from 0)
26 *
27 * We assume caller has already range-checked the dimensions and subscripts,
28 * so no overflow is possible.
29 */
30int
31ArrayGetOffset(int n, const int *dim, const int *lb, const int *indx)
32{
33 int i,
34 scale = 1,
35 offset = 0;
36
37 for (i = n - 1; i >= 0; i--)
38 {
39 offset += (indx[i] - lb[i]) * scale;
40 scale *= dim[i];
41 }
42 return offset;
43}
44
45/*
46 * Same, but subscripts are assumed 0-based, and use a scale array
47 * instead of raw dimension data (see mda_get_prod to create scale array)
48 */
49int
50ArrayGetOffset0(int n, const int *tup, const int *scale)
51{
52 int i,
53 lin = 0;
54
55 for (i = 0; i < n; i++)
56 lin += tup[i] * scale[i];
57 return lin;
58}
59
60/*
61 * Convert array dimensions into number of elements
62 *
63 * This must do overflow checking, since it is used to validate that a user
64 * dimensionality request doesn't overflow what we can handle.
65 *
66 * We limit array sizes to at most about a quarter billion elements,
67 * so that it's not necessary to check for overflow in quite so many
68 * places --- for instance when palloc'ing Datum arrays.
69 *
70 * The multiplication overflow check only works on machines that have int64
71 * arithmetic, but that is nearly all platforms these days, and doing check
72 * divides for those that don't seems way too expensive.
73 */
74int
75ArrayGetNItems(int ndim, const int *dims)
76{
77 int32 ret;
78 int i;
79
80#define MaxArraySize ((Size) (MaxAllocSize / sizeof(Datum)))
81
82 if (ndim <= 0)
83 return 0;
84 ret = 1;
85 for (i = 0; i < ndim; i++)
86 {
87 int64 prod;
88
89 /* A negative dimension implies that UB-LB overflowed ... */
90 if (dims[i] < 0)
91 ereport(ERROR,
92 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
93 errmsg("array size exceeds the maximum allowed (%d)",
94 (int) MaxArraySize)));
95
96 prod = (int64) ret * (int64) dims[i];
97
98 ret = (int32) prod;
99 if ((int64) ret != prod)
100 ereport(ERROR,
101 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
102 errmsg("array size exceeds the maximum allowed (%d)",
103 (int) MaxArraySize)));
104 }
105 Assert(ret >= 0);
106 if ((Size) ret > MaxArraySize)
107 ereport(ERROR,
108 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
109 errmsg("array size exceeds the maximum allowed (%d)",
110 (int) MaxArraySize)));
111 return (int) ret;
112}
113
114/*
115 * Compute ranges (sub-array dimensions) for an array slice
116 *
117 * We assume caller has validated slice endpoints, so overflow is impossible
118 */
119void
120mda_get_range(int n, int *span, const int *st, const int *endp)
121{
122 int i;
123
124 for (i = 0; i < n; i++)
125 span[i] = endp[i] - st[i] + 1;
126}
127
128/*
129 * Compute products of array dimensions, ie, scale factors for subscripts
130 *
131 * We assume caller has validated dimensions, so overflow is impossible
132 */
133void
134mda_get_prod(int n, const int *range, int *prod)
135{
136 int i;
137
138 prod[n - 1] = 1;
139 for (i = n - 2; i >= 0; i--)
140 prod[i] = prod[i + 1] * range[i + 1];
141}
142
143/*
144 * From products of whole-array dimensions and spans of a sub-array,
145 * compute offset distances needed to step through subarray within array
146 *
147 * We assume caller has validated dimensions, so overflow is impossible
148 */
149void
150mda_get_offset_values(int n, int *dist, const int *prod, const int *span)
151{
152 int i,
153 j;
154
155 dist[n - 1] = 0;
156 for (j = n - 2; j >= 0; j--)
157 {
158 dist[j] = prod[j] - 1;
159 for (i = j + 1; i < n; i++)
160 dist[j] -= (span[i] - 1) * prod[i];
161 }
162}
163
164/*
165 * Generates the tuple that is lexicographically one greater than the current
166 * n-tuple in "curr", with the restriction that the i-th element of "curr" is
167 * less than the i-th element of "span".
168 *
169 * Returns -1 if no next tuple exists, else the subscript position (0..n-1)
170 * corresponding to the dimension to advance along.
171 *
172 * We assume caller has validated dimensions, so overflow is impossible
173 */
174int
175mda_next_tuple(int n, int *curr, const int *span)
176{
177 int i;
178
179 if (n <= 0)
180 return -1;
181
182 curr[n - 1] = (curr[n - 1] + 1) % span[n - 1];
183 for (i = n - 1; i && curr[i] == 0; i--)
184 curr[i - 1] = (curr[i - 1] + 1) % span[i - 1];
185
186 if (i)
187 return i;
188 if (curr[0])
189 return 0;
190
191 return -1;
192}
193
194/*
195 * ArrayGetIntegerTypmods: verify that argument is a 1-D cstring array,
196 * and get the contents converted to integers. Returns a palloc'd array
197 * and places the length at *n.
198 */
199int32 *
200ArrayGetIntegerTypmods(ArrayType *arr, int *n)
201{
202 int32 *result;
203 Datum *elem_values;
204 int i;
205
206 if (ARR_ELEMTYPE(arr) != CSTRINGOID)
207 ereport(ERROR,
208 (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
209 errmsg("typmod array must be type cstring[]")));
210
211 if (ARR_NDIM(arr) != 1)
212 ereport(ERROR,
213 (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
214 errmsg("typmod array must be one-dimensional")));
215
216 if (array_contains_nulls(arr))
217 ereport(ERROR,
218 (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
219 errmsg("typmod array must not contain nulls")));
220
221 /* hardwired knowledge about cstring's representation details here */
222 deconstruct_array(arr, CSTRINGOID,
223 -2, false, 'c',
224 &elem_values, NULL, n);
225
226 result = (int32 *) palloc(*n * sizeof(int32));
227
228 for (i = 0; i < *n; i++)
229 result[i] = pg_strtoint32(DatumGetCString(elem_values[i]));
230
231 pfree(elem_values);
232
233 return result;
234}
235