PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
arrayutils.c
Go to the documentation of this file.
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 ArrayGetOffset(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  */
49 int
50 ArrayGetOffset0(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  */
74 int
75 ArrayGetNItems(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  */
119 void
120 mda_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  */
133 void
134 mda_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  */
149 void
150 mda_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  */
174 int
175 mda_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  */
199 int32 *
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 */
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_atoi(DatumGetCString(elem_values[i]),
230  sizeof(int32), '\0');
231 
232  pfree(elem_values);
233 
234  return result;
235 }
int ArrayGetOffset(int n, const int *dim, const int *lb, const int *indx)
Definition: arrayutils.c:31
void mda_get_prod(int n, const int *range, int *prod)
Definition: arrayutils.c:134
int32 * ArrayGetIntegerTypmods(ArrayType *arr, int *n)
Definition: arrayutils.c:200
int ArrayGetNItems(int ndim, const int *dims)
Definition: arrayutils.c:75
#define MaxArraySize
int errcode(int sqlerrcode)
Definition: elog.c:575
int scale
Definition: pgbench.c:106
signed int int32
Definition: c.h:253
void pfree(void *pointer)
Definition: mcxt.c:992
#define ERROR
Definition: elog.h:43
#define DatumGetCString(X)
Definition: postgres.h:574
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:416
#define ereport(elevel, rest)
Definition: elog.h:122
void mda_get_offset_values(int n, int *dist, const int *prod, const int *span)
Definition: arrayutils.c:150
uintptr_t Datum
Definition: postgres.h:374
void mda_get_range(int n, int *span, const int *st, const int *endp)
Definition: arrayutils.c:120
#define NULL
Definition: c.h:226
#define CSTRINGOID
Definition: pg_type.h:672
#define Assert(condition)
Definition: c.h:670
size_t Size
Definition: c.h:352
#define ARR_NDIM(a)
Definition: array.h:271
void deconstruct_array(ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)
Definition: arrayfuncs.c:3475
int mda_next_tuple(int n, int *curr, const int *span)
Definition: arrayutils.c:175
void * palloc(Size size)
Definition: mcxt.c:891
int errmsg(const char *fmt,...)
Definition: elog.c:797
int i
bool array_contains_nulls(ArrayType *array)
Definition: arrayfuncs.c:3542
#define ARR_ELEMTYPE(a)
Definition: array.h:273
int32 pg_atoi(const char *s, int size, int c)
Definition: numutils.c:37
int ArrayGetOffset0(int n, const int *tup, const int *scale)
Definition: arrayutils.c:50