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-2017, 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 : */
30 : int
31 24314 : ArrayGetOffset(int n, const int *dim, const int *lb, const int *indx)
32 : {
33 : int i,
34 24314 : scale = 1,
35 24314 : offset = 0;
36 :
37 48680 : for (i = n - 1; i >= 0; i--)
38 : {
39 24366 : offset += (indx[i] - lb[i]) * scale;
40 24366 : scale *= dim[i];
41 : }
42 24314 : 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 : */
49 : int
50 6579 : ArrayGetOffset0(int n, const int *tup, const int *scale)
51 : {
52 : int i,
53 6579 : lin = 0;
54 :
55 13493 : for (i = 0; i < n; i++)
56 6914 : lin += tup[i] * scale[i];
57 6579 : 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 : */
74 : int
75 230063 : ArrayGetNItems(int ndim, const int *dims)
76 : {
77 : int32 ret;
78 : int i;
79 :
80 : #define MaxArraySize ((Size) (MaxAllocSize / sizeof(Datum)))
81 :
82 230063 : if (ndim <= 0)
83 1765 : return 0;
84 228298 : ret = 1;
85 457028 : for (i = 0; i < ndim; i++)
86 : {
87 : int64 prod;
88 :
89 : /* A negative dimension implies that UB-LB overflowed ... */
90 228730 : if (dims[i] < 0)
91 0 : ereport(ERROR,
92 : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
93 : errmsg("array size exceeds the maximum allowed (%d)",
94 : (int) MaxArraySize)));
95 :
96 228730 : prod = (int64) ret * (int64) dims[i];
97 :
98 228730 : ret = (int32) prod;
99 228730 : if ((int64) ret != prod)
100 0 : ereport(ERROR,
101 : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
102 : errmsg("array size exceeds the maximum allowed (%d)",
103 : (int) MaxArraySize)));
104 : }
105 228298 : Assert(ret >= 0);
106 228298 : if ((Size) ret > MaxArraySize)
107 0 : ereport(ERROR,
108 : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
109 : errmsg("array size exceeds the maximum allowed (%d)",
110 : (int) MaxArraySize)));
111 228298 : 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 : */
119 : void
120 139 : mda_get_range(int n, int *span, const int *st, const int *endp)
121 : {
122 : int i;
123 :
124 362 : for (i = 0; i < n; i++)
125 223 : span[i] = endp[i] - st[i] + 1;
126 139 : }
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 : */
133 : void
134 2092 : mda_get_prod(int n, const int *range, int *prod)
135 : {
136 : int i;
137 :
138 2092 : prod[n - 1] = 1;
139 2182 : for (i = n - 2; i >= 0; i--)
140 90 : prod[i] = prod[i + 1] * range[i + 1];
141 2092 : }
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 : */
149 : void
150 44 : mda_get_offset_values(int n, int *dist, const int *prod, const int *span)
151 : {
152 : int i,
153 : j;
154 :
155 44 : dist[n - 1] = 0;
156 79 : for (j = n - 2; j >= 0; j--)
157 : {
158 35 : dist[j] = prod[j] - 1;
159 75 : for (i = j + 1; i < n; i++)
160 40 : dist[j] -= (span[i] - 1) * prod[i];
161 : }
162 44 : }
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 : */
174 : int
175 138 : mda_next_tuple(int n, int *curr, const int *span)
176 : {
177 : int i;
178 :
179 138 : if (n <= 0)
180 0 : return -1;
181 :
182 138 : curr[n - 1] = (curr[n - 1] + 1) % span[n - 1];
183 189 : for (i = n - 1; i && curr[i] == 0; i--)
184 51 : curr[i - 1] = (curr[i - 1] + 1) % span[i - 1];
185 :
186 138 : if (i)
187 53 : return i;
188 85 : if (curr[0])
189 41 : return 0;
190 :
191 44 : 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 : */
199 : int32 *
200 635 : ArrayGetIntegerTypmods(ArrayType *arr, int *n)
201 : {
202 : int32 *result;
203 : Datum *elem_values;
204 : int i;
205 :
206 635 : if (ARR_ELEMTYPE(arr) != CSTRINGOID)
207 0 : ereport(ERROR,
208 : (errcode(ERRCODE_ARRAY_ELEMENT_ERROR),
209 : errmsg("typmod array must be type cstring[]")));
210 :
211 635 : if (ARR_NDIM(arr) != 1)
212 0 : ereport(ERROR,
213 : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
214 : errmsg("typmod array must be one-dimensional")));
215 :
216 635 : if (array_contains_nulls(arr))
217 0 : 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 635 : deconstruct_array(arr, CSTRINGOID,
223 : -2, false, 'c',
224 : &elem_values, NULL, n);
225 :
226 635 : result = (int32 *) palloc(*n * sizeof(int32));
227 :
228 1349 : for (i = 0; i < *n; i++)
229 714 : result[i] = pg_atoi(DatumGetCString(elem_values[i]),
230 : sizeof(int32), '\0');
231 :
232 635 : pfree(elem_values);
233 :
234 635 : return result;
235 : }
|
