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 100894 : 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 100894 : na = ARRNELEMS(a);
25 100894 : nb = ARRNELEMS(b);
26 100894 : da = ARRPTR(a);
27 100894 : db = ARRPTR(b);
28 :
29 100894 : i = j = n = 0;
30 221406 : while (i < na && j < nb)
31 : {
32 215752 : if (da[i] < db[j])
33 115092 : i++;
34 100660 : else if (da[i] == db[j])
35 : {
36 5420 : n++;
37 5420 : i++;
38 5420 : j++;
39 : }
40 : else
41 95240 : break; /* db[j] is not in da */
42 : }
43 :
44 100894 : return (n == nb) ? true : false;
45 : }
46 :
47 : /* arguments are assumed sorted */
48 : bool
49 25902 : 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 25902 : na = ARRNELEMS(a);
59 25902 : nb = ARRNELEMS(b);
60 25902 : da = ARRPTR(a);
61 25902 : db = ARRPTR(b);
62 :
63 25902 : i = j = 0;
64 115840 : while (i < na && j < nb)
65 : {
66 92512 : if (da[i] < db[j])
67 43770 : i++;
68 48742 : else if (da[i] == db[j])
69 2574 : return true;
70 : else
71 46168 : j++;
72 : }
73 :
74 23328 : return false;
75 : }
76 :
77 : ArrayType *
78 1618884 : inner_int_union(ArrayType *a, ArrayType *b)
79 : {
80 1618884 : ArrayType *r = NULL;
81 :
82 1618884 : CHECKARRVALID(a);
83 1618884 : CHECKARRVALID(b);
84 :
85 1618884 : if (ARRISEMPTY(a) && ARRISEMPTY(b))
86 120 : return new_intArrayType(0);
87 1618764 : if (ARRISEMPTY(a))
88 9402 : r = copy_intArrayType(b);
89 1618764 : if (ARRISEMPTY(b))
90 3124 : r = copy_intArrayType(a);
91 :
92 1618764 : if (!r)
93 : {
94 1606238 : int na = ARRNELEMS(a),
95 1606238 : nb = ARRNELEMS(b);
96 1606238 : int *da = ARRPTR(a),
97 1606238 : *db = ARRPTR(b);
98 : int i,
99 : j,
100 : *dr;
101 :
102 1606238 : r = new_intArrayType(na + nb);
103 1606238 : dr = ARRPTR(r);
104 :
105 : /* union */
106 1606238 : i = j = 0;
107 24490330 : while (i < na && j < nb)
108 : {
109 22884092 : if (da[i] == db[j])
110 : {
111 1097822 : *dr++ = da[i++];
112 1097822 : j++;
113 : }
114 21786270 : else if (da[i] < db[j])
115 17295906 : *dr++ = da[i++];
116 : else
117 4490364 : *dr++ = db[j++];
118 : }
119 :
120 5003668 : while (i < na)
121 3397430 : *dr++ = da[i++];
122 3047186 : while (j < nb)
123 1440948 : *dr++ = db[j++];
124 :
125 1606238 : r = resize_intArrayType(r, dr - ARRPTR(r));
126 : }
127 :
128 1618764 : if (ARRNELEMS(r) > 1)
129 1618764 : r = _int_unique(r);
130 :
131 1618764 : return r;
132 : }
133 :
134 : ArrayType *
135 1384924 : 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 1384924 : if (ARRISEMPTY(a) || ARRISEMPTY(b))
148 12276 : return new_intArrayType(0);
149 :
150 1372648 : na = ARRNELEMS(a);
151 1372648 : nb = ARRNELEMS(b);
152 1372648 : da = ARRPTR(a);
153 1372648 : db = ARRPTR(b);
154 1372648 : r = new_intArrayType(Min(na, nb));
155 1372648 : dr = ARRPTR(r);
156 :
157 1372648 : i = j = k = 0;
158 10197348 : while (i < na && j < nb)
159 : {
160 8824700 : if (da[i] < db[j])
161 4339668 : i++;
162 4485032 : else if (da[i] == db[j])
163 : {
164 487446 : if (k == 0 || dr[k - 1] != db[j])
165 487446 : dr[k++] = db[j];
166 487446 : i++;
167 487446 : j++;
168 : }
169 : else
170 3997586 : j++;
171 : }
172 :
173 1372648 : if (k == 0)
174 : {
175 1101520 : pfree(r);
176 1101520 : return new_intArrayType(0);
177 : }
178 : else
179 271128 : return resize_intArrayType(r, k);
180 : }
181 :
182 : void
183 3154428 : rt__int_size(ArrayType *a, float *size)
184 : {
185 3154428 : *size = (float) ARRNELEMS(a);
186 3154428 : }
187 :
188 : /* qsort_arg comparison function for isort() */
189 : static int
190 29998058 : isort_cmp(const void *a, const void *b, void *arg)
191 : {
192 29998058 : int32 aval = *((const int32 *) a);
193 29998058 : int32 bval = *((const int32 *) b);
194 :
195 29998058 : if (aval < bval)
196 563604 : return -1;
197 29434454 : if (aval > bval)
198 29318908 : 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 115546 : *((bool *) arg) = true;
206 115546 : return 0;
207 : }
208 :
209 : /* Sort the given data (len >= 2). Return true if any duplicates found */
210 : bool
211 336126 : isort(int32 *a, int len)
212 : {
213 336126 : bool r = false;
214 :
215 336126 : qsort_arg(a, len, sizeof(int32), isort_cmp, (void *) &r);
216 336126 : return r;
217 : }
218 :
219 : /* Create a new int array with room for "num" elements */
220 : ArrayType *
221 4134430 : new_intArrayType(int num)
222 : {
223 : ArrayType *r;
224 : int nbytes;
225 :
226 : /* if no elements, return a zero-dimensional array */
227 4134430 : if (num <= 0)
228 : {
229 : Assert(num == 0);
230 1113916 : r = construct_empty_array(INT4OID);
231 1113916 : return r;
232 : }
233 :
234 3020514 : nbytes = ARR_OVERHEAD_NONULLS(1) + sizeof(int) * num;
235 :
236 3020514 : r = (ArrayType *) palloc0(nbytes);
237 :
238 3020514 : SET_VARSIZE(r, nbytes);
239 3020514 : ARR_NDIM(r) = 1;
240 3020514 : r->dataoffset = 0; /* marker for no null bitmap */
241 3020514 : ARR_ELEMTYPE(r) = INT4OID;
242 3020514 : ARR_DIMS(r)[0] = num;
243 3020514 : ARR_LBOUND(r)[0] = 1;
244 :
245 3020514 : return r;
246 : }
247 :
248 : ArrayType *
249 3530166 : resize_intArrayType(ArrayType *a, int num)
250 : {
251 : int nbytes;
252 : int i;
253 :
254 : /* if no elements, return a zero-dimensional array */
255 3530166 : if (num <= 0)
256 : {
257 : Assert(num == 0);
258 0 : a = construct_empty_array(INT4OID);
259 0 : return a;
260 : }
261 :
262 3530166 : if (num == ARRNELEMS(a))
263 2767858 : return a;
264 :
265 762308 : nbytes = ARR_DATA_OFFSET(a) + sizeof(int) * num;
266 :
267 762308 : a = (ArrayType *) repalloc(a, nbytes);
268 :
269 762308 : SET_VARSIZE(a, nbytes);
270 : /* usually the array should be 1-D already, but just in case ... */
271 1524616 : for (i = 0; i < ARR_NDIM(a); i++)
272 : {
273 762308 : ARR_DIMS(a)[i] = num;
274 762308 : num = 1;
275 : }
276 762308 : return a;
277 : }
278 :
279 : ArrayType *
280 12886 : copy_intArrayType(ArrayType *a)
281 : {
282 : ArrayType *r;
283 12886 : int n = ARRNELEMS(a);
284 :
285 12886 : r = new_intArrayType(n);
286 12886 : memcpy(ARRPTR(r), ARRPTR(a), n * sizeof(int32));
287 12886 : return r;
288 : }
289 :
290 : /* num for compressed key */
291 : int
292 5924 : internal_size(int *a, int len)
293 : {
294 : int i;
295 5924 : int64 size = 0;
296 :
297 598324 : for (i = 0; i < len; i += 2)
298 : {
299 592400 : if (!i || a[i] != a[i - 1]) /* do not count repeated range */
300 592400 : size += (int64) (a[i + 1]) - (int64) (a[i]) + 1;
301 : }
302 :
303 5924 : if (size > (int64) INT_MAX || size < (int64) INT_MIN)
304 0 : return -1; /* overflow */
305 5924 : return (int) size;
306 : }
307 :
308 : /* unique-ify elements of r in-place ... r must be sorted already */
309 : ArrayType *
310 1652312 : _int_unique(ArrayType *r)
311 : {
312 1652312 : int num = ARRNELEMS(r);
313 : bool duplicates_found; /* not used */
314 :
315 1652312 : num = qunique_arg(ARRPTR(r), num, sizeof(int), isort_cmp,
316 : &duplicates_found);
317 :
318 1652312 : 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 28904668 : compASC(const void *a, const void *b)
398 : {
399 28904668 : if (*(const int32 *) a == *(const int32 *) b)
400 108440 : return 0;
401 28796228 : 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 : }
|
