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 133102 : 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 133102 : na = ARRNELEMS(a);
25 133102 : nb = ARRNELEMS(b);
26 133102 : da = ARRPTR(a);
27 133102 : db = ARRPTR(b);
28 :
29 133102 : i = j = n = 0;
30 305904 : while (i < na && j < nb)
31 : {
32 297942 : if (da[i] < db[j])
33 164712 : i++;
34 133230 : else if (da[i] == db[j])
35 : {
36 8090 : n++;
37 8090 : i++;
38 8090 : j++;
39 : }
40 : else
41 125140 : break; /* db[j] is not in da */
42 : }
43 :
44 133102 : return (n == nb) ? true : false;
45 : }
46 :
47 : /* arguments are assumed sorted */
48 : bool
49 36910 : 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 36910 : na = ARRNELEMS(a);
59 36910 : nb = ARRNELEMS(b);
60 36910 : da = ARRPTR(a);
61 36910 : db = ARRPTR(b);
62 :
63 36910 : i = j = 0;
64 164690 : while (i < na && j < nb)
65 : {
66 132108 : if (da[i] < db[j])
67 63102 : i++;
68 69006 : else if (da[i] == db[j])
69 4328 : return true;
70 : else
71 64678 : j++;
72 : }
73 :
74 32582 : return false;
75 : }
76 :
77 : ArrayType *
78 3250392 : inner_int_union(ArrayType *a, ArrayType *b)
79 : {
80 3250392 : ArrayType *r = NULL;
81 :
82 3250392 : CHECKARRVALID(a);
83 3250392 : CHECKARRVALID(b);
84 :
85 3250392 : if (ARRISEMPTY(a) && ARRISEMPTY(b))
86 268 : return new_intArrayType(0);
87 3250124 : if (ARRISEMPTY(a))
88 19290 : r = copy_intArrayType(b);
89 3250124 : if (ARRISEMPTY(b))
90 6500 : r = copy_intArrayType(a);
91 :
92 3250124 : if (!r)
93 : {
94 3224334 : int na = ARRNELEMS(a),
95 3224334 : nb = ARRNELEMS(b);
96 3224334 : int *da = ARRPTR(a),
97 3224334 : *db = ARRPTR(b);
98 : int i,
99 : j,
100 : *dr;
101 :
102 3224334 : r = new_intArrayType(na + nb);
103 3224334 : dr = ARRPTR(r);
104 :
105 : /* union */
106 3224334 : i = j = 0;
107 49219742 : while (i < na && j < nb)
108 : {
109 45995408 : if (da[i] == db[j])
110 : {
111 2201062 : *dr++ = da[i++];
112 2201062 : j++;
113 : }
114 43794346 : else if (da[i] < db[j])
115 34752746 : *dr++ = da[i++];
116 : else
117 9041600 : *dr++ = db[j++];
118 : }
119 :
120 9879388 : while (i < na)
121 6655054 : *dr++ = da[i++];
122 6142974 : while (j < nb)
123 2918640 : *dr++ = db[j++];
124 :
125 3224334 : r = resize_intArrayType(r, dr - ARRPTR(r));
126 : }
127 :
128 3250124 : if (ARRNELEMS(r) > 1)
129 3250110 : r = _int_unique(r);
130 :
131 3250124 : return r;
132 : }
133 :
134 : ArrayType *
135 2776220 : 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 2776220 : if (ARRISEMPTY(a) || ARRISEMPTY(b))
148 25294 : return new_intArrayType(0);
149 :
150 2750926 : na = ARRNELEMS(a);
151 2750926 : nb = ARRNELEMS(b);
152 2750926 : da = ARRPTR(a);
153 2750926 : db = ARRPTR(b);
154 2750926 : r = new_intArrayType(Min(na, nb));
155 2750926 : dr = ARRPTR(r);
156 :
157 2750926 : i = j = k = 0;
158 20428482 : while (i < na && j < nb)
159 : {
160 17677556 : if (da[i] < db[j])
161 8654350 : i++;
162 9023206 : else if (da[i] == db[j])
163 : {
164 979030 : if (k == 0 || dr[k - 1] != db[j])
165 979030 : dr[k++] = db[j];
166 979030 : i++;
167 979030 : j++;
168 : }
169 : else
170 8044176 : j++;
171 : }
172 :
173 2750926 : if (k == 0)
174 : {
175 2210768 : pfree(r);
176 2210768 : return new_intArrayType(0);
177 : }
178 : else
179 540158 : return resize_intArrayType(r, k);
180 : }
181 :
182 : void
183 6333768 : rt__int_size(ArrayType *a, float *size)
184 : {
185 6333768 : *size = (float) ARRNELEMS(a);
186 6333768 : }
187 :
188 : /* qsort_arg comparison function for isort() */
189 : static int
190 59072220 : isort_cmp(const void *a, const void *b, void *arg)
191 : {
192 59072220 : int32 aval = *((const int32 *) a);
193 59072220 : int32 bval = *((const int32 *) b);
194 :
195 59072220 : if (aval < bval)
196 689190 : return -1;
197 58383030 : if (aval > bval)
198 58172282 : 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 210748 : *((bool *) arg) = true;
206 210748 : return 0;
207 : }
208 :
209 : /* Sort the given data (len >= 2). Return true if any duplicates found */
210 : bool
211 423964 : isort(int32 *a, int len)
212 : {
213 423964 : bool r = false;
214 :
215 423964 : qsort_arg(a, len, sizeof(int32), isort_cmp, (void *) &r);
216 423964 : return r;
217 : }
218 :
219 : /* Create a new int array with room for "num" elements */
220 : ArrayType *
221 8289016 : new_intArrayType(int num)
222 : {
223 : ArrayType *r;
224 : int nbytes;
225 :
226 : /* if no elements, return a zero-dimensional array */
227 8289016 : if (num <= 0)
228 : {
229 : Assert(num == 0);
230 2236330 : r = construct_empty_array(INT4OID);
231 2236330 : return r;
232 : }
233 :
234 6052686 : nbytes = ARR_OVERHEAD_NONULLS(1) + sizeof(int) * num;
235 :
236 6052686 : r = (ArrayType *) palloc0(nbytes);
237 :
238 6052686 : SET_VARSIZE(r, nbytes);
239 6052686 : ARR_NDIM(r) = 1;
240 6052686 : r->dataoffset = 0; /* marker for no null bitmap */
241 6052686 : ARR_ELEMTYPE(r) = INT4OID;
242 6052686 : ARR_DIMS(r)[0] = num;
243 6052686 : ARR_LBOUND(r)[0] = 1;
244 :
245 6052686 : return r;
246 : }
247 :
248 : ArrayType *
249 7073318 : resize_intArrayType(ArrayType *a, int num)
250 : {
251 : int nbytes;
252 : int i;
253 :
254 : /* if no elements, return a zero-dimensional array */
255 7073318 : if (num <= 0)
256 : {
257 : Assert(num == 0);
258 0 : a = construct_empty_array(INT4OID);
259 0 : return a;
260 : }
261 :
262 7073318 : if (num == ARRNELEMS(a))
263 5560208 : return a;
264 :
265 1513110 : nbytes = ARR_DATA_OFFSET(a) + sizeof(int) * num;
266 :
267 1513110 : a = (ArrayType *) repalloc(a, nbytes);
268 :
269 1513110 : SET_VARSIZE(a, nbytes);
270 : /* usually the array should be 1-D already, but just in case ... */
271 3026220 : for (i = 0; i < ARR_NDIM(a); i++)
272 : {
273 1513110 : ARR_DIMS(a)[i] = num;
274 1513110 : num = 1;
275 : }
276 1513110 : return a;
277 : }
278 :
279 : ArrayType *
280 26514 : copy_intArrayType(ArrayType *a)
281 : {
282 : ArrayType *r;
283 26514 : int n = ARRNELEMS(a);
284 :
285 26514 : r = new_intArrayType(n);
286 26514 : memcpy(ARRPTR(r), ARRPTR(a), n * sizeof(int32));
287 26514 : return r;
288 : }
289 :
290 : /* num for compressed key */
291 : int
292 5682 : internal_size(int *a, int len)
293 : {
294 : int i;
295 5682 : int64 size = 0;
296 :
297 573882 : for (i = 0; i < len; i += 2)
298 : {
299 568200 : if (!i || a[i] != a[i - 1]) /* do not count repeated range */
300 568200 : size += (int64) (a[i + 1]) - (int64) (a[i]) + 1;
301 : }
302 :
303 5682 : if (size > (int64) INT_MAX || size < (int64) INT_MIN)
304 0 : return -1; /* overflow */
305 5682 : return (int) size;
306 : }
307 :
308 : /* unique-ify elements of r in-place ... r must be sorted already */
309 : ArrayType *
310 3308346 : _int_unique(ArrayType *r)
311 : {
312 3308346 : int num = ARRNELEMS(r);
313 : bool duplicates_found; /* not used */
314 :
315 3308346 : num = qunique_arg(ARRPTR(r), num, sizeof(int), isort_cmp,
316 : &duplicates_found);
317 :
318 3308346 : return resize_intArrayType(r, num);
319 : }
320 :
321 : void
322 0 : gensign(BITVECP sign, int *a, int len, int siglen)
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, siglen);
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 56458478 : compASC(const void *a, const void *b)
398 : {
399 56458478 : if (*(const int32 *) a == *(const int32 *) b)
400 214420 : return 0;
401 56244058 : 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 : }
|
