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 "lib/qunique.h"
11 :
12 : /* arguments are assumed sorted & unique-ified */
13 : bool
14 100784 : inner_int_contains(ArrayType *a, ArrayType *b)
15 : {
16 : int na,
17 : nb;
18 : int i,
19 : j,
20 : n;
21 : int *da,
22 : *db;
23 :
24 100784 : na = ARRNELEMS(a);
25 100784 : nb = ARRNELEMS(b);
26 100784 : da = ARRPTR(a);
27 100784 : db = ARRPTR(b);
28 :
29 100784 : i = j = n = 0;
30 320302 : while (i < na && j < nb)
31 : {
32 214108 : if (da[i] < db[j])
33 113516 : i++;
34 100592 : else if (da[i] == db[j])
35 : {
36 5218 : n++;
37 5218 : i++;
38 5218 : j++;
39 : }
40 : else
41 95374 : break; /* db[j] is not in da */
42 : }
43 :
44 100784 : return (n == nb) ? true : false;
45 : }
46 :
47 : /* arguments are assumed sorted */
48 : bool
49 25404 : inner_int_overlap(ArrayType *a, ArrayType *b)
50 : {
51 : int na,
52 : nb;
53 : int i,
54 : j;
55 : int *da,
56 : *db;
57 :
58 25404 : na = ARRNELEMS(a);
59 25404 : nb = ARRNELEMS(b);
60 25404 : da = ARRPTR(a);
61 25404 : db = ARRPTR(b);
62 :
63 25404 : i = j = 0;
64 138348 : while (i < na && j < nb)
65 : {
66 90098 : if (da[i] < db[j])
67 42388 : i++;
68 47710 : else if (da[i] == db[j])
69 2558 : return true;
70 : else
71 45152 : j++;
72 : }
73 :
74 22846 : return false;
75 : }
76 :
77 : ArrayType *
78 1643528 : inner_int_union(ArrayType *a, ArrayType *b)
79 : {
80 1643528 : ArrayType *r = NULL;
81 :
82 1643528 : CHECKARRVALID(a);
83 1643528 : CHECKARRVALID(b);
84 :
85 1643528 : if (ARRISEMPTY(a) && ARRISEMPTY(b))
86 120 : return new_intArrayType(0);
87 1643408 : if (ARRISEMPTY(a))
88 9384 : r = copy_intArrayType(b);
89 1643408 : if (ARRISEMPTY(b))
90 3394 : r = copy_intArrayType(a);
91 :
92 1643408 : if (!r)
93 : {
94 1630630 : int na = ARRNELEMS(a),
95 1630630 : nb = ARRNELEMS(b);
96 1630630 : int *da = ARRPTR(a),
97 1630630 : *db = ARRPTR(b);
98 : int i,
99 : j,
100 : *dr;
101 :
102 1630630 : r = new_intArrayType(na + nb);
103 1630630 : dr = ARRPTR(r);
104 :
105 : /* union */
106 1630630 : i = j = 0;
107 25359792 : while (i < na && j < nb)
108 : {
109 22098532 : if (da[i] == db[j])
110 : {
111 980156 : *dr++ = da[i++];
112 980156 : j++;
113 : }
114 21118376 : else if (da[i] < db[j])
115 16695776 : *dr++ = da[i++];
116 : else
117 4422600 : *dr++ = db[j++];
118 : }
119 :
120 6547764 : while (i < na)
121 3286504 : *dr++ = da[i++];
122 4753502 : while (j < nb)
123 1492242 : *dr++ = db[j++];
124 :
125 1630630 : r = resize_intArrayType(r, dr - ARRPTR(r));
126 : }
127 :
128 1643408 : if (ARRNELEMS(r) > 1)
129 1643388 : r = _int_unique(r);
130 :
131 1643408 : return r;
132 : }
133 :
134 : ArrayType *
135 1411270 : inner_int_inter(ArrayType *a, ArrayType *b)
136 : {
137 : ArrayType *r;
138 : int na,
139 : nb;
140 : int *da,
141 : *db,
142 : *dr;
143 : int i,
144 : j,
145 : k;
146 :
147 1411270 : if (ARRISEMPTY(a) || ARRISEMPTY(b))
148 12522 : return new_intArrayType(0);
149 :
150 1398748 : na = ARRNELEMS(a);
151 1398748 : nb = ARRNELEMS(b);
152 1398748 : da = ARRPTR(a);
153 1398748 : db = ARRPTR(b);
154 1398748 : r = new_intArrayType(Min(na, nb));
155 1398748 : dr = ARRPTR(r);
156 :
157 1398748 : i = j = k = 0;
158 11512300 : while (i < na && j < nb)
159 : {
160 8714804 : if (da[i] < db[j])
161 4307930 : i++;
162 4406874 : else if (da[i] == db[j])
163 : {
164 432486 : if (k == 0 || dr[k - 1] != db[j])
165 432486 : dr[k++] = db[j];
166 432486 : i++;
167 432486 : j++;
168 : }
169 : else
170 3974388 : j++;
171 : }
172 :
173 1398748 : if (k == 0)
174 : {
175 1124656 : pfree(r);
176 1124656 : return new_intArrayType(0);
177 : }
178 : else
179 274092 : return resize_intArrayType(r, k);
180 : }
181 :
182 : void
183 3202968 : rt__int_size(ArrayType *a, float *size)
184 : {
185 3202968 : *size = (float) ARRNELEMS(a);
186 3202968 : }
187 :
188 : /* qsort_arg comparison function for isort() */
189 : static int
190 28952186 : isort_cmp(const void *a, const void *b, void *arg)
191 : {
192 28952186 : int32 aval = *((const int32 *) a);
193 28952186 : int32 bval = *((const int32 *) b);
194 :
195 28952186 : if (aval < bval)
196 562986 : return -1;
197 28389200 : if (aval > bval)
198 28280450 : return 1;
199 :
200 : /*
201 : * Report if we have any duplicates. If there are equal keys, qsort must
202 : * compare them at some point, else it wouldn't know whether one should go
203 : * before or after the other.
204 : */
205 108750 : *((bool *) arg) = true;
206 108750 : return 0;
207 : }
208 :
209 : /* Sort the given data (len >= 2). Return true if any duplicates found */
210 : bool
211 334620 : isort(int32 *a, int len)
212 : {
213 334620 : bool r = false;
214 :
215 334620 : qsort_arg(a, len, sizeof(int32), isort_cmp, (void *) &r);
216 334620 : return r;
217 : }
218 :
219 : /* Create a new int array with room for "num" elements */
220 : ArrayType *
221 4206966 : new_intArrayType(int num)
222 : {
223 : ArrayType *r;
224 : int nbytes;
225 :
226 : /* if no elements, return a zero-dimensional array */
227 4206966 : if (num <= 0)
228 : {
229 : Assert(num == 0);
230 1137298 : r = construct_empty_array(INT4OID);
231 1137298 : return r;
232 : }
233 :
234 3069668 : nbytes = ARR_OVERHEAD_NONULLS(1) + sizeof(int) * num;
235 :
236 3069668 : r = (ArrayType *) palloc0(nbytes);
237 :
238 3069668 : SET_VARSIZE(r, nbytes);
239 3069668 : ARR_NDIM(r) = 1;
240 3069668 : r->dataoffset = 0; /* marker for no null bitmap */
241 3069668 : ARR_ELEMTYPE(r) = INT4OID;
242 3069668 : ARR_DIMS(r)[0] = num;
243 3069668 : ARR_LBOUND(r)[0] = 1;
244 :
245 3069668 : return r;
246 : }
247 :
248 : ArrayType *
249 3581518 : resize_intArrayType(ArrayType *a, int num)
250 : {
251 : int nbytes;
252 : int i;
253 :
254 : /* if no elements, return a zero-dimensional array */
255 3581518 : if (num <= 0)
256 : {
257 : Assert(num == 0);
258 0 : a = construct_empty_array(INT4OID);
259 0 : return a;
260 : }
261 :
262 3581518 : if (num == ARRNELEMS(a))
263 2818550 : return a;
264 :
265 762968 : nbytes = ARR_DATA_OFFSET(a) + sizeof(int) * num;
266 :
267 762968 : a = (ArrayType *) repalloc(a, nbytes);
268 :
269 762968 : SET_VARSIZE(a, nbytes);
270 : /* usually the array should be 1-D already, but just in case ... */
271 1525936 : for (i = 0; i < ARR_NDIM(a); i++)
272 : {
273 762968 : ARR_DIMS(a)[i] = num;
274 762968 : num = 1;
275 : }
276 762968 : return a;
277 : }
278 :
279 : ArrayType *
280 13118 : copy_intArrayType(ArrayType *a)
281 : {
282 : ArrayType *r;
283 13118 : int n = ARRNELEMS(a);
284 :
285 13118 : r = new_intArrayType(n);
286 13118 : memcpy(ARRPTR(r), ARRPTR(a), n * sizeof(int32));
287 13118 : return r;
288 : }
289 :
290 : /* num for compressed key */
291 : int
292 5102 : internal_size(int *a, int len)
293 : {
294 : int i;
295 5102 : int64 size = 0;
296 :
297 515302 : for (i = 0; i < len; i += 2)
298 : {
299 510200 : if (!i || a[i] != a[i - 1]) /* do not count repeated range */
300 510200 : size += (int64) (a[i + 1]) - (int64) (a[i]) + 1;
301 : }
302 :
303 5102 : if (size > (int64) INT_MAX || size < (int64) INT_MIN)
304 0 : return -1; /* overflow */
305 5102 : return (int) size;
306 : }
307 :
308 : /* unique-ify elements of r in-place ... r must be sorted already */
309 : ArrayType *
310 1676228 : _int_unique(ArrayType *r)
311 : {
312 1676228 : int num = ARRNELEMS(r);
313 : bool duplicates_found; /* not used */
314 :
315 1676228 : num = qunique_arg(ARRPTR(r), num, sizeof(int), isort_cmp,
316 : &duplicates_found);
317 :
318 1676228 : return resize_intArrayType(r, num);
319 : }
320 :
321 : void
322 0 : gensign(BITVEC sign, int *a, int len)
323 : {
324 : int i;
325 :
326 : /* we assume that the sign vector is previously zeroed */
327 0 : for (i = 0; i < len; i++)
328 : {
329 0 : HASH(sign, *a);
330 0 : a++;
331 : }
332 0 : }
333 :
334 : int32
335 2 : intarray_match_first(ArrayType *a, int32 elem)
336 : {
337 : int32 *aa,
338 : c,
339 : i;
340 :
341 2 : CHECKARRVALID(a);
342 2 : c = ARRNELEMS(a);
343 2 : aa = ARRPTR(a);
344 4 : for (i = 0; i < c; i++)
345 4 : if (aa[i] == elem)
346 2 : return (i + 1);
347 0 : return 0;
348 : }
349 :
350 : ArrayType *
351 8 : intarray_add_elem(ArrayType *a, int32 elem)
352 : {
353 : ArrayType *result;
354 : int32 *r;
355 : int32 c;
356 :
357 8 : CHECKARRVALID(a);
358 8 : c = ARRNELEMS(a);
359 8 : result = new_intArrayType(c + 1);
360 8 : r = ARRPTR(result);
361 8 : if (c > 0)
362 8 : memcpy(r, ARRPTR(a), c * sizeof(int32));
363 8 : r[c] = elem;
364 8 : return result;
365 : }
366 :
367 : ArrayType *
368 2 : intarray_concat_arrays(ArrayType *a, ArrayType *b)
369 : {
370 : ArrayType *result;
371 2 : int32 ac = ARRNELEMS(a);
372 2 : int32 bc = ARRNELEMS(b);
373 :
374 2 : CHECKARRVALID(a);
375 2 : CHECKARRVALID(b);
376 2 : result = new_intArrayType(ac + bc);
377 2 : if (ac)
378 2 : memcpy(ARRPTR(result), ARRPTR(a), ac * sizeof(int32));
379 2 : if (bc)
380 2 : memcpy(ARRPTR(result) + ac, ARRPTR(b), bc * sizeof(int32));
381 2 : return result;
382 : }
383 :
384 : ArrayType *
385 2 : int_to_intset(int32 n)
386 : {
387 : ArrayType *result;
388 : int32 *aa;
389 :
390 2 : result = new_intArrayType(1);
391 2 : aa = ARRPTR(result);
392 2 : aa[0] = n;
393 2 : return result;
394 : }
395 :
396 : int
397 26411438 : compASC(const void *a, const void *b)
398 : {
399 26411438 : if (*(const int32 *) a == *(const int32 *) b)
400 101146 : return 0;
401 26310292 : return (*(const int32 *) a > *(const int32 *) b) ? 1 : -1;
402 : }
403 :
404 : int
405 12 : compDESC(const void *a, const void *b)
406 : {
407 12 : if (*(const int32 *) a == *(const int32 *) b)
408 0 : return 0;
409 12 : return (*(const int32 *) a < *(const int32 *) b) ? 1 : -1;
410 : }
|
