Age Owner Branch data TLA Line data Source code
1 : : /*
2 : : * contrib/intarray/_int_tool.c
3 : : */
4 : : #include "postgres.h"
5 : :
6 : : #include <limits.h>
7 : :
8 : : #include "_int.h"
9 : : #include "catalog/pg_type.h"
10 : : #include "common/int.h"
11 : : #include "lib/qunique.h"
12 : :
13 : : /* arguments are assumed sorted & unique-ified */
14 : : bool
7613 bruce@momjian.us 15 :CBC 95569 : inner_int_contains(ArrayType *a, ArrayType *b)
16 : : {
17 : : int na,
18 : : nb;
19 : : int i,
20 : : j,
21 : : n;
22 : : int *da,
23 : : *db;
24 : :
25 : 95569 : na = ARRNELEMS(a);
26 : 95569 : nb = ARRNELEMS(b);
27 [ - + ]: 95569 : da = ARRPTR(a);
28 [ - + ]: 95569 : db = ARRPTR(b);
29 : :
30 : 95569 : i = j = n = 0;
31 [ + + + + ]: 233811 : while (i < na && j < nb)
32 : : {
33 [ + + ]: 226987 : if (da[i] < db[j])
34 : 131650 : i++;
35 [ + + ]: 95337 : else if (da[i] == db[j])
36 : : {
37 : 6592 : n++;
38 : 6592 : i++;
39 : 6592 : j++;
40 : : }
41 : : else
4844 tgl@sss.pgh.pa.us 42 : 88745 : break; /* db[j] is not in da */
43 : : }
44 : :
949 michael@paquier.xyz 45 : 95569 : return (n == nb);
46 : : }
47 : :
48 : : /* arguments are assumed sorted */
49 : : bool
7613 bruce@momjian.us 50 : 23910 : inner_int_overlap(ArrayType *a, ArrayType *b)
51 : : {
52 : : int na,
53 : : nb;
54 : : int i,
55 : : j;
56 : : int *da,
57 : : *db;
58 : :
59 : 23910 : na = ARRNELEMS(a);
60 : 23910 : nb = ARRNELEMS(b);
61 [ - + ]: 23910 : da = ARRPTR(a);
62 [ - + ]: 23910 : db = ARRPTR(b);
63 : :
64 : 23910 : i = j = 0;
65 [ + + + + ]: 111914 : while (i < na && j < nb)
66 : : {
67 [ + + ]: 90886 : if (da[i] < db[j])
68 : 45904 : i++;
69 [ + + ]: 44982 : else if (da[i] == db[j])
2433 peter_e@gmx.net 70 : 2882 : return true;
71 : : else
7613 bruce@momjian.us 72 : 42100 : j++;
73 : : }
74 : :
2433 peter_e@gmx.net 75 : 21028 : return false;
76 : : }
77 : :
78 : : ArrayType *
7613 bruce@momjian.us 79 : 2209839 : inner_int_union(ArrayType *a, ArrayType *b)
80 : : {
81 : 2209839 : ArrayType *r = NULL;
82 : :
6721 tgl@sss.pgh.pa.us 83 [ - + - - : 2209839 : CHECKARRVALID(a);
- - ]
84 [ - + - - : 2209839 : CHECKARRVALID(b);
- - ]
85 : :
4844 86 [ + + + + ]: 2209839 : if (ARRISEMPTY(a) && ARRISEMPTY(b))
7613 bruce@momjian.us 87 : 149 : return new_intArrayType(0);
4844 tgl@sss.pgh.pa.us 88 [ + + ]: 2209690 : if (ARRISEMPTY(a))
7613 bruce@momjian.us 89 : 13099 : r = copy_intArrayType(b);
4844 tgl@sss.pgh.pa.us 90 [ + + ]: 2209690 : if (ARRISEMPTY(b))
7613 bruce@momjian.us 91 : 4269 : r = copy_intArrayType(a);
92 : :
6549 teodor@sigaev.ru 93 [ + + ]: 2209690 : if (!r)
94 : : {
6402 bruce@momjian.us 95 : 2192322 : int na = ARRNELEMS(a),
96 : 2192322 : nb = ARRNELEMS(b);
97 [ - + ]: 2192322 : int *da = ARRPTR(a),
98 [ - + ]: 2192322 : *db = ARRPTR(b);
99 : : int i,
100 : : j,
101 : : *dr;
102 : :
7613 103 : 2192322 : r = new_intArrayType(na + nb);
104 [ - + ]: 2192322 : dr = ARRPTR(r);
105 : :
106 : : /* union */
107 : 2192322 : i = j = 0;
6402 108 [ + + + + ]: 81601549 : while (i < na && j < nb)
109 : : {
110 [ + + ]: 79409227 : if (da[i] == db[j])
111 : : {
6549 teodor@sigaev.ru 112 : 4938326 : *dr++ = da[i++];
113 : 4938326 : j++;
114 : : }
6402 bruce@momjian.us 115 [ + + ]: 74470901 : else if (da[i] < db[j])
7613 116 : 62993109 : *dr++ = da[i++];
117 : : else
118 : 11477792 : *dr++ = db[j++];
119 : : }
120 : :
121 [ + + ]: 7639289 : while (i < na)
122 : 5446967 : *dr++ = da[i++];
123 [ + + ]: 4181558 : while (j < nb)
124 : 1989236 : *dr++ = db[j++];
125 : :
6402 126 [ - + ]: 2192322 : r = resize_intArrayType(r, dr - ARRPTR(r));
127 : : }
128 : :
7613 129 [ + + ]: 2209690 : if (ARRNELEMS(r) > 1)
130 : 2209684 : r = _int_unique(r);
131 : :
132 : 2209690 : return r;
133 : : }
134 : :
135 : : ArrayType *
136 : 1769066 : inner_int_inter(ArrayType *a, ArrayType *b)
137 : : {
138 : : ArrayType *r;
139 : : int na,
140 : : nb;
141 : : int *da,
142 : : *db,
143 : : *dr;
144 : : int i,
145 : : j,
146 : : k;
147 : :
4844 tgl@sss.pgh.pa.us 148 [ + + + + ]: 1769066 : if (ARRISEMPTY(a) || ARRISEMPTY(b))
7613 bruce@momjian.us 149 : 16933 : return new_intArrayType(0);
150 : :
151 : 1752133 : na = ARRNELEMS(a);
152 : 1752133 : nb = ARRNELEMS(b);
153 [ - + ]: 1752133 : da = ARRPTR(a);
154 [ - + ]: 1752133 : db = ARRPTR(b);
7115 tgl@sss.pgh.pa.us 155 : 1752133 : r = new_intArrayType(Min(na, nb));
7613 bruce@momjian.us 156 [ - + ]: 1752133 : dr = ARRPTR(r);
157 : :
4441 tgl@sss.pgh.pa.us 158 : 1752133 : i = j = k = 0;
7613 bruce@momjian.us 159 [ + + + + ]: 21520067 : while (i < na && j < nb)
160 : : {
161 [ + + ]: 19767934 : if (da[i] < db[j])
162 : 9121455 : i++;
163 [ + + ]: 10646479 : else if (da[i] == db[j])
164 : : {
4441 tgl@sss.pgh.pa.us 165 [ + + + - ]: 1707534 : if (k == 0 || dr[k - 1] != db[j])
166 : 1707534 : dr[k++] = db[j];
7613 bruce@momjian.us 167 : 1707534 : i++;
168 : 1707534 : j++;
169 : : }
170 : : else
171 : 8938945 : j++;
172 : : }
173 : :
4441 tgl@sss.pgh.pa.us 174 [ + + ]: 1752133 : if (k == 0)
175 : : {
7613 bruce@momjian.us 176 : 1390325 : pfree(r);
177 : 1390325 : return new_intArrayType(0);
178 : : }
179 : : else
4441 tgl@sss.pgh.pa.us 180 : 361808 : return resize_intArrayType(r, k);
181 : : }
182 : :
183 : : void
7613 bruce@momjian.us 184 : 4291292 : rt__int_size(ArrayType *a, float *size)
185 : : {
186 : 4291292 : *size = (float) ARRNELEMS(a);
187 : 4291292 : }
188 : :
189 : : /* qsort_arg comparison function for isort() */
190 : : static int
3318 tgl@sss.pgh.pa.us 191 : 103295701 : isort_cmp(const void *a, const void *b, void *arg)
192 : : {
193 : 103295701 : int32 aval = *((const int32 *) a);
194 : 103295701 : int32 bval = *((const int32 *) b);
195 : :
196 [ + + ]: 103295701 : if (aval < bval)
197 : 623733 : return -1;
198 [ + + ]: 102671968 : if (aval > bval)
199 : 102154396 : return 1;
200 : :
201 : : /*
202 : : * Report if we have any duplicates. If there are equal keys, qsort must
203 : : * compare them at some point, else it wouldn't know whether one should go
204 : : * before or after the other.
205 : : */
206 : 517572 : *((bool *) arg) = true;
207 : 517572 : return 0;
208 : : }
209 : :
210 : : /* Sort the given data (len >= 2). Return true if any duplicates found */
211 : : bool
4311 peter_e@gmx.net 212 : 286820 : isort(int32 *a, int len)
213 : : {
3318 tgl@sss.pgh.pa.us 214 : 286820 : bool r = false;
215 : :
432 peter@eisentraut.org 216 : 286820 : qsort_arg(a, len, sizeof(int32), isort_cmp, &r);
7613 bruce@momjian.us 217 : 286820 : return r;
218 : : }
219 : :
220 : : /* Create a new int array with room for "num" elements */
221 : : ArrayType *
222 : 5454543 : new_intArrayType(int num)
223 : : {
224 : : ArrayType *r;
225 : : int nbytes;
226 : :
227 : : /* if no elements, return a zero-dimensional array */
2106 tgl@sss.pgh.pa.us 228 [ + + ]: 5454543 : if (num <= 0)
229 : : {
1969 rhodiumtoad@postgres 230 [ - + ]: 1407407 : Assert(num == 0);
2106 tgl@sss.pgh.pa.us 231 : 1407407 : r = construct_empty_array(INT4OID);
232 : 1407407 : return r;
233 : : }
234 : :
235 : 4047136 : nbytes = ARR_OVERHEAD_NONULLS(1) + sizeof(int) * num;
236 : :
7613 bruce@momjian.us 237 : 4047136 : r = (ArrayType *) palloc0(nbytes);
238 : :
6256 tgl@sss.pgh.pa.us 239 : 4047136 : SET_VARSIZE(r, nbytes);
4844 240 : 4047136 : ARR_NDIM(r) = 1;
6723 241 : 4047136 : r->dataoffset = 0; /* marker for no null bitmap */
7613 bruce@momjian.us 242 : 4047136 : ARR_ELEMTYPE(r) = INT4OID;
4844 tgl@sss.pgh.pa.us 243 : 4047136 : ARR_DIMS(r)[0] = num;
244 : 4047136 : ARR_LBOUND(r)[0] = 1;
245 : :
7613 bruce@momjian.us 246 : 4047136 : return r;
247 : : }
248 : :
249 : : ArrayType *
250 : 4832123 : resize_intArrayType(ArrayType *a, int num)
251 : : {
252 : : int nbytes;
253 : : int i;
254 : :
255 : : /* if no elements, return a zero-dimensional array */
2106 tgl@sss.pgh.pa.us 256 [ - + ]: 4832123 : if (num <= 0)
257 : : {
1969 rhodiumtoad@postgres 258 [ # # ]:UBC 0 : Assert(num == 0);
1713 tgl@sss.pgh.pa.us 259 : 0 : a = construct_empty_array(INT4OID);
3872 bruce@momjian.us 260 : 0 : return a;
261 : : }
262 : :
7613 bruce@momjian.us 263 [ + + ]:CBC 4832123 : if (num == ARRNELEMS(a))
264 : 3689086 : return a;
265 : :
2106 tgl@sss.pgh.pa.us 266 [ - + ]: 1143037 : nbytes = ARR_DATA_OFFSET(a) + sizeof(int) * num;
267 : :
7613 bruce@momjian.us 268 : 1143037 : a = (ArrayType *) repalloc(a, nbytes);
269 : :
6256 tgl@sss.pgh.pa.us 270 : 1143037 : SET_VARSIZE(a, nbytes);
271 : : /* usually the array should be 1-D already, but just in case ... */
4844 272 [ + + ]: 2286074 : for (i = 0; i < ARR_NDIM(a); i++)
273 : : {
274 : 1143037 : ARR_DIMS(a)[i] = num;
275 : 1143037 : num = 1;
276 : : }
7613 bruce@momjian.us 277 : 1143037 : return a;
278 : : }
279 : :
280 : : ArrayType *
281 : 18556 : copy_intArrayType(ArrayType *a)
282 : : {
283 : : ArrayType *r;
4844 tgl@sss.pgh.pa.us 284 : 18556 : int n = ARRNELEMS(a);
285 : :
286 : 18556 : r = new_intArrayType(n);
4311 peter_e@gmx.net 287 [ - + - + ]: 18556 : memcpy(ARRPTR(r), ARRPTR(a), n * sizeof(int32));
7613 bruce@momjian.us 288 : 18556 : return r;
289 : : }
290 : :
291 : : /* num for compressed key */
292 : : int
293 : 28475 : internal_size(int *a, int len)
294 : : {
295 : : int i;
1969 rhodiumtoad@postgres 296 : 28475 : int64 size = 0;
297 : :
7613 bruce@momjian.us 298 [ + + ]: 6706071 : for (i = 0; i < len; i += 2)
299 : : {
2489 tgl@sss.pgh.pa.us 300 [ + + + - ]: 6677596 : if (!i || a[i] != a[i - 1]) /* do not count repeated range */
1789 301 : 6677596 : size += (int64) (a[i + 1]) - (int64) (a[i]) + 1;
302 : : }
303 : :
304 [ + - - + ]: 28475 : if (size > (int64) INT_MAX || size < (int64) INT_MIN)
1969 rhodiumtoad@postgres 305 :UBC 0 : return -1; /* overflow */
1969 rhodiumtoad@postgres 306 :CBC 28475 : return (int) size;
307 : : }
308 : :
309 : : /* unique-ify elements of r in-place ... r must be sorted already */
310 : : ArrayType *
7613 bruce@momjian.us 311 : 2275293 : _int_unique(ArrayType *r)
312 : : {
313 : 2275293 : int num = ARRNELEMS(r);
314 : : bool duplicates_found; /* not used */
315 : :
1620 tmunro@postgresql.or 316 [ - + ]: 2275293 : num = qunique_arg(ARRPTR(r), num, sizeof(int), isort_cmp,
317 : : &duplicates_found);
318 : :
319 : 2275293 : return resize_intArrayType(r, num);
320 : : }
321 : :
322 : : void
1476 akorotkov@postgresql 323 :UBC 0 : gensign(BITVECP sign, int *a, int len, int siglen)
324 : : {
325 : : int i;
326 : :
327 : : /* we assume that the sign vector is previously zeroed */
7613 bruce@momjian.us 328 [ # # ]: 0 : for (i = 0; i < len; i++)
329 : : {
1476 akorotkov@postgresql 330 : 0 : HASH(sign, *a, siglen);
7613 bruce@momjian.us 331 : 0 : a++;
332 : : }
333 : 0 : }
334 : :
335 : : int32
7613 bruce@momjian.us 336 :CBC 1 : intarray_match_first(ArrayType *a, int32 elem)
337 : : {
338 : : int32 *aa,
339 : : c,
340 : : i;
341 : :
6721 tgl@sss.pgh.pa.us 342 [ - + - - : 1 : CHECKARRVALID(a);
- - ]
343 : 1 : c = ARRNELEMS(a);
7613 bruce@momjian.us 344 [ - + ]: 1 : aa = ARRPTR(a);
345 [ + - ]: 2 : for (i = 0; i < c; i++)
346 [ + + ]: 2 : if (aa[i] == elem)
347 : 1 : return (i + 1);
7613 bruce@momjian.us 348 :UBC 0 : return 0;
349 : : }
350 : :
351 : : ArrayType *
7613 bruce@momjian.us 352 :CBC 4 : intarray_add_elem(ArrayType *a, int32 elem)
353 : : {
354 : : ArrayType *result;
355 : : int32 *r;
356 : : int32 c;
357 : :
6721 tgl@sss.pgh.pa.us 358 [ - + - - : 4 : CHECKARRVALID(a);
- - ]
4844 359 : 4 : c = ARRNELEMS(a);
7613 bruce@momjian.us 360 : 4 : result = new_intArrayType(c + 1);
361 [ - + ]: 4 : r = ARRPTR(result);
362 [ + - ]: 4 : if (c > 0)
363 [ - + ]: 4 : memcpy(r, ARRPTR(a), c * sizeof(int32));
364 : 4 : r[c] = elem;
365 : 4 : return result;
366 : : }
367 : :
368 : : ArrayType *
369 : 1 : intarray_concat_arrays(ArrayType *a, ArrayType *b)
370 : : {
371 : : ArrayType *result;
4844 tgl@sss.pgh.pa.us 372 : 1 : int32 ac = ARRNELEMS(a);
373 : 1 : int32 bc = ARRNELEMS(b);
374 : :
6721 375 [ - + - - : 1 : CHECKARRVALID(a);
- - ]
376 [ - + - - : 1 : CHECKARRVALID(b);
- - ]
7613 bruce@momjian.us 377 : 1 : result = new_intArrayType(ac + bc);
378 [ + - ]: 1 : if (ac)
379 [ - + - + ]: 1 : memcpy(ARRPTR(result), ARRPTR(a), ac * sizeof(int32));
380 [ + - ]: 1 : if (bc)
381 [ - + - + ]: 1 : memcpy(ARRPTR(result) + ac, ARRPTR(b), bc * sizeof(int32));
382 : 1 : return result;
383 : : }
384 : :
385 : : ArrayType *
570 pg@bowt.ie 386 : 1 : int_to_intset(int32 elem)
387 : : {
388 : : ArrayType *result;
389 : : int32 *aa;
390 : :
7613 bruce@momjian.us 391 : 1 : result = new_intArrayType(1);
392 [ - + ]: 1 : aa = ARRPTR(result);
570 pg@bowt.ie 393 : 1 : aa[0] = elem;
7613 bruce@momjian.us 394 : 1 : return result;
395 : : }
396 : :
397 : : int
398 : 234025880 : compASC(const void *a, const void *b)
399 : : {
58 nathan@postgresql.or 400 :GNC 234025880 : return pg_cmp_s32(*(const int32 *) a, *(const int32 *) b);
401 : : }
402 : :
403 : : int
7613 bruce@momjian.us 404 :CBC 6 : compDESC(const void *a, const void *b)
405 : : {
58 nathan@postgresql.or 406 :GNC 6 : return pg_cmp_s32(*(const int32 *) b, *(const int32 *) a);
407 : : }
|
