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 165308 : 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 165308 : na = ARRNELEMS(a);
25 165308 : nb = ARRNELEMS(b);
26 165308 : da = ARRPTR(a);
27 165308 : db = ARRPTR(b);
28 :
29 165308 : i = j = n = 0;
30 374864 : while (i < na && j < nb)
31 : {
32 363730 : if (da[i] < db[j])
33 200360 : i++;
34 163370 : else if (da[i] == db[j])
35 : {
36 9196 : n++;
37 9196 : i++;
38 9196 : j++;
39 : }
40 : else
41 154174 : break; /* db[j] is not in da */
42 : }
43 :
44 165308 : return (n == nb);
45 : }
46 :
47 : /* arguments are assumed sorted */
48 : bool
49 37952 : 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 37952 : na = ARRNELEMS(a);
59 37952 : nb = ARRNELEMS(b);
60 37952 : da = ARRPTR(a);
61 37952 : db = ARRPTR(b);
62 :
63 37952 : i = j = 0;
64 170348 : while (i < na && j < nb)
65 : {
66 136744 : if (da[i] < db[j])
67 65696 : i++;
68 71048 : else if (da[i] == db[j])
69 4348 : return true;
70 : else
71 66700 : j++;
72 : }
73 :
74 33604 : return false;
75 : }
76 :
77 : ArrayType *
78 3254916 : inner_int_union(ArrayType *a, ArrayType *b)
79 : {
80 3254916 : ArrayType *r = NULL;
81 :
82 3254916 : CHECKARRVALID(a);
83 3254916 : CHECKARRVALID(b);
84 :
85 3254916 : if (ARRISEMPTY(a) && ARRISEMPTY(b))
86 246 : return new_intArrayType(0);
87 3254670 : if (ARRISEMPTY(a))
88 19174 : r = copy_intArrayType(b);
89 3254670 : if (ARRISEMPTY(b))
90 6588 : r = copy_intArrayType(a);
91 :
92 3254670 : if (!r)
93 : {
94 3228908 : int na = ARRNELEMS(a),
95 3228908 : nb = ARRNELEMS(b);
96 3228908 : int *da = ARRPTR(a),
97 3228908 : *db = ARRPTR(b);
98 : int i,
99 : j,
100 : *dr;
101 :
102 3228908 : r = new_intArrayType(na + nb);
103 3228908 : dr = ARRPTR(r);
104 :
105 : /* union */
106 3228908 : i = j = 0;
107 50718138 : while (i < na && j < nb)
108 : {
109 47489230 : if (da[i] == db[j])
110 : {
111 2397562 : *dr++ = da[i++];
112 2397562 : j++;
113 : }
114 45091668 : else if (da[i] < db[j])
115 35909804 : *dr++ = da[i++];
116 : else
117 9181864 : *dr++ = db[j++];
118 : }
119 :
120 9988832 : while (i < na)
121 6759924 : *dr++ = da[i++];
122 6183926 : while (j < nb)
123 2955018 : *dr++ = db[j++];
124 :
125 3228908 : r = resize_intArrayType(r, dr - ARRPTR(r));
126 : }
127 :
128 3254670 : if (ARRNELEMS(r) > 1)
129 3254650 : r = _int_unique(r);
130 :
131 3254670 : return r;
132 : }
133 :
134 : ArrayType *
135 2764462 : 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 2764462 : if (ARRISEMPTY(a) || ARRISEMPTY(b))
148 25244 : return new_intArrayType(0);
149 :
150 2739218 : na = ARRNELEMS(a);
151 2739218 : nb = ARRNELEMS(b);
152 2739218 : da = ARRPTR(a);
153 2739218 : db = ARRPTR(b);
154 2739218 : r = new_intArrayType(Min(na, nb));
155 2739218 : dr = ARRPTR(r);
156 :
157 2739218 : i = j = k = 0;
158 20627838 : while (i < na && j < nb)
159 : {
160 17888620 : if (da[i] < db[j])
161 8694970 : i++;
162 9193650 : else if (da[i] == db[j])
163 : {
164 1085002 : if (k == 0 || dr[k - 1] != db[j])
165 1085002 : dr[k++] = db[j];
166 1085002 : i++;
167 1085002 : j++;
168 : }
169 : else
170 8108648 : j++;
171 : }
172 :
173 2739218 : if (k == 0)
174 : {
175 2202908 : pfree(r);
176 2202908 : return new_intArrayType(0);
177 : }
178 : else
179 536310 : return resize_intArrayType(r, k);
180 : }
181 :
182 : void
183 6342484 : rt__int_size(ArrayType *a, float *size)
184 : {
185 6342484 : *size = (float) ARRNELEMS(a);
186 6342484 : }
187 :
188 : /* qsort_arg comparison function for isort() */
189 : static int
190 61407062 : isort_cmp(const void *a, const void *b, void *arg)
191 : {
192 61407062 : int32 aval = *((const int32 *) a);
193 61407062 : int32 bval = *((const int32 *) b);
194 :
195 61407062 : if (aval < bval)
196 817510 : return -1;
197 60589552 : if (aval > bval)
198 60368002 : 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 221550 : *((bool *) arg) = true;
206 221550 : return 0;
207 : }
208 :
209 : /* Sort the given data (len >= 2). Return true if any duplicates found */
210 : bool
211 510774 : isort(int32 *a, int len)
212 : {
213 510774 : bool r = false;
214 :
215 510774 : qsort_arg(a, len, sizeof(int32), isort_cmp, (void *) &r);
216 510774 : return r;
217 : }
218 :
219 : /* Create a new int array with room for "num" elements */
220 : ArrayType *
221 8275748 : new_intArrayType(int num)
222 : {
223 : ArrayType *r;
224 : int nbytes;
225 :
226 : /* if no elements, return a zero-dimensional array */
227 8275748 : if (num <= 0)
228 : {
229 : Assert(num == 0);
230 2228398 : r = construct_empty_array(INT4OID);
231 2228398 : return r;
232 : }
233 :
234 6047350 : nbytes = ARR_OVERHEAD_NONULLS(1) + sizeof(int) * num;
235 :
236 6047350 : r = (ArrayType *) palloc0(nbytes);
237 :
238 6047350 : SET_VARSIZE(r, nbytes);
239 6047350 : ARR_NDIM(r) = 1;
240 6047350 : r->dataoffset = 0; /* marker for no null bitmap */
241 6047350 : ARR_ELEMTYPE(r) = INT4OID;
242 6047350 : ARR_DIMS(r)[0] = num;
243 6047350 : ARR_LBOUND(r)[0] = 1;
244 :
245 6047350 : return r;
246 : }
247 :
248 : ArrayType *
249 7082766 : resize_intArrayType(ArrayType *a, int num)
250 : {
251 : int nbytes;
252 : int i;
253 :
254 : /* if no elements, return a zero-dimensional array */
255 7082766 : if (num <= 0)
256 : {
257 : Assert(num == 0);
258 0 : a = construct_empty_array(INT4OID);
259 0 : return a;
260 : }
261 :
262 7082766 : if (num == ARRNELEMS(a))
263 5562110 : return a;
264 :
265 1520656 : nbytes = ARR_DATA_OFFSET(a) + sizeof(int) * num;
266 :
267 1520656 : a = (ArrayType *) repalloc(a, nbytes);
268 :
269 1520656 : SET_VARSIZE(a, nbytes);
270 : /* usually the array should be 1-D already, but just in case ... */
271 3041312 : for (i = 0; i < ARR_NDIM(a); i++)
272 : {
273 1520656 : ARR_DIMS(a)[i] = num;
274 1520656 : num = 1;
275 : }
276 1520656 : return a;
277 : }
278 :
279 : ArrayType *
280 26522 : copy_intArrayType(ArrayType *a)
281 : {
282 : ArrayType *r;
283 26522 : int n = ARRNELEMS(a);
284 :
285 26522 : r = new_intArrayType(n);
286 26522 : memcpy(ARRPTR(r), ARRPTR(a), n * sizeof(int32));
287 26522 : return r;
288 : }
289 :
290 : /* num for compressed key */
291 : int
292 6324 : internal_size(int *a, int len)
293 : {
294 : int i;
295 6324 : int64 size = 0;
296 :
297 638724 : for (i = 0; i < len; i += 2)
298 : {
299 632400 : if (!i || a[i] != a[i - 1]) /* do not count repeated range */
300 632400 : size += (int64) (a[i + 1]) - (int64) (a[i]) + 1;
301 : }
302 :
303 6324 : if (size > (int64) INT_MAX || size < (int64) INT_MIN)
304 0 : return -1; /* overflow */
305 6324 : return (int) size;
306 : }
307 :
308 : /* unique-ify elements of r in-place ... r must be sorted already */
309 : ArrayType *
310 3317024 : _int_unique(ArrayType *r)
311 : {
312 3317024 : int num = ARRNELEMS(r);
313 : bool duplicates_found; /* not used */
314 :
315 3317024 : num = qunique_arg(ARRPTR(r), num, sizeof(int), isort_cmp,
316 : &duplicates_found);
317 :
318 3317024 : 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 61665208 : compASC(const void *a, const void *b)
398 : {
399 61665208 : if (*(const int32 *) a == *(const int32 *) b)
400 219974 : return 0;
401 61445234 : 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 : }
|
