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 "common/int.h" 20 #include "utils/array.h" 21 #include "utils/builtins.h" 22 #include "utils/memutils.h" 23 command_query_expand(grn_ctx * ctx,int nargs,grn_obj ** args,grn_user_data * user_data)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 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 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 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)", grn_proc_init_query_expand(grn_ctx * ctx)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 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 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 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 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 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 * 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_strtoint32(DatumGetCString(elem_values[i])); 261 262 pfree(elem_values); 263 264 return result; 265 } 266