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 "lib/qunique.h"
11 :
12 : /* arguments are assumed sorted & unique-ified */
13 : bool
14 CBC 80480 : 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 80480 : na = ARRNELEMS(a);
25 80480 : nb = ARRNELEMS(b);
26 80480 : da = ARRPTR(a);
27 80480 : db = ARRPTR(b);
28 :
29 80480 : i = j = n = 0;
30 182341 : while (i < na && j < nb)
31 : {
32 176877 : if (da[i] < db[j])
33 97379 : i++;
34 79498 : else if (da[i] == db[j])
35 : {
36 4482 : n++;
37 4482 : i++;
38 4482 : j++;
39 : }
40 : else
41 75016 : break; /* db[j] is not in da */
42 : }
43 :
44 80480 : return (n == nb);
45 : }
46 :
47 : /* arguments are assumed sorted */
48 : bool
49 18633 : 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 18633 : na = ARRNELEMS(a);
59 18633 : nb = ARRNELEMS(b);
60 18633 : da = ARRPTR(a);
61 18633 : db = ARRPTR(b);
62 :
63 18633 : i = j = 0;
64 83590 : while (i < na && j < nb)
65 : {
66 67118 : if (da[i] < db[j])
67 32271 : i++;
68 34847 : else if (da[i] == db[j])
69 2161 : return true;
70 : else
71 32686 : j++;
72 : }
73 :
74 16472 : return false;
75 : }
76 :
77 : ArrayType *
78 1598127 : inner_int_union(ArrayType *a, ArrayType *b)
79 : {
80 1598127 : ArrayType *r = NULL;
81 :
82 1598127 : CHECKARRVALID(a);
83 1598127 : CHECKARRVALID(b);
84 :
85 1598127 : if (ARRISEMPTY(a) && ARRISEMPTY(b))
86 132 : return new_intArrayType(0);
87 1597995 : if (ARRISEMPTY(a))
88 10061 : r = copy_intArrayType(b);
89 1597995 : if (ARRISEMPTY(b))
90 3351 : r = copy_intArrayType(a);
91 :
92 1597995 : if (!r)
93 : {
94 1584583 : int na = ARRNELEMS(a),
95 1584583 : nb = ARRNELEMS(b);
96 1584583 : int *da = ARRPTR(a),
97 1584583 : *db = ARRPTR(b);
98 : int i,
99 : j,
100 : *dr;
101 :
102 1584583 : r = new_intArrayType(na + nb);
103 1584583 : dr = ARRPTR(r);
104 :
105 : /* union */
106 1584583 : i = j = 0;
107 24042498 : while (i < na && j < nb)
108 : {
109 22457915 : if (da[i] == db[j])
110 : {
111 1060460 : *dr++ = da[i++];
112 1060460 : j++;
113 : }
114 21397455 : else if (da[i] < db[j])
115 16997536 : *dr++ = da[i++];
116 : else
117 4399919 : *dr++ = db[j++];
118 : }
119 :
120 4886521 : while (i < na)
121 3301938 : *dr++ = da[i++];
122 2999665 : while (j < nb)
123 1415082 : *dr++ = db[j++];
124 :
125 1584583 : r = resize_intArrayType(r, dr - ARRPTR(r));
126 : }
127 :
128 1597995 : if (ARRNELEMS(r) > 1)
129 1597987 : r = _int_unique(r);
130 :
131 1597995 : return r;
132 : }
133 :
134 : ArrayType *
135 1363245 : 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 1363245 : if (ARRISEMPTY(a) || ARRISEMPTY(b))
148 13145 : return new_intArrayType(0);
149 :
150 1350100 : na = ARRNELEMS(a);
151 1350100 : nb = ARRNELEMS(b);
152 1350100 : da = ARRPTR(a);
153 1350100 : db = ARRPTR(b);
154 1350100 : r = new_intArrayType(Min(na, nb));
155 1350100 : dr = ARRPTR(r);
156 :
157 1350100 : i = j = k = 0;
158 9956568 : while (i < na && j < nb)
159 : {
160 8606468 : if (da[i] < db[j])
161 4220111 : i++;
162 4386357 : else if (da[i] == db[j])
163 : {
164 471103 : if (k == 0 || dr[k - 1] != db[j])
165 471103 : dr[k++] = db[j];
166 471103 : i++;
167 471103 : j++;
168 : }
169 : else
170 3915254 : j++;
171 : }
172 :
173 1350100 : if (k == 0)
174 : {
175 1085134 : pfree(r);
176 1085134 : return new_intArrayType(0);
177 : }
178 : else
179 264966 : return resize_intArrayType(r, k);
180 : }
181 :
182 : void
183 3114456 : rt__int_size(ArrayType *a, float *size)
184 : {
185 3114456 : *size = (float) ARRNELEMS(a);
186 3114456 : }
187 :
188 : /* qsort_arg comparison function for isort() */
189 : static int
190 29101541 : isort_cmp(const void *a, const void *b, void *arg)
191 : {
192 29101541 : int32 aval = *((const int32 *) a);
193 29101541 : int32 bval = *((const int32 *) b);
194 :
195 29101541 : if (aval < bval)
196 406238 : return -1;
197 28695303 : if (aval > bval)
198 28589227 : 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 106076 : *((bool *) arg) = true;
206 106076 : return 0;
207 : }
208 :
209 : /* Sort the given data (len >= 2). Return true if any duplicates found */
210 : bool
211 252918 : isort(int32 *a, int len)
212 : {
213 252918 : bool r = false;
214 :
215 GNC 252918 : qsort_arg(a, len, sizeof(int32), isort_cmp, &r);
216 CBC 252918 : return r;
217 : }
218 :
219 : /* Create a new int array with room for "num" elements */
220 : ArrayType *
221 4071931 : new_intArrayType(int num)
222 : {
223 : ArrayType *r;
224 : int nbytes;
225 :
226 : /* if no elements, return a zero-dimensional array */
227 4071931 : if (num <= 0)
228 : {
229 1098411 : Assert(num == 0);
230 1098411 : r = construct_empty_array(INT4OID);
231 1098411 : return r;
232 : }
233 :
234 2973520 : nbytes = ARR_OVERHEAD_NONULLS(1) + sizeof(int) * num;
235 :
236 2973520 : r = (ArrayType *) palloc0(nbytes);
237 :
238 2973520 : SET_VARSIZE(r, nbytes);
239 2973520 : ARR_NDIM(r) = 1;
240 2973520 : r->dataoffset = 0; /* marker for no null bitmap */
241 2973520 : ARR_ELEMTYPE(r) = INT4OID;
242 2973520 : ARR_DIMS(r)[0] = num;
243 2973520 : ARR_LBOUND(r)[0] = 1;
244 :
245 2973520 : return r;
246 : }
247 :
248 : ArrayType *
249 3478290 : resize_intArrayType(ArrayType *a, int num)
250 : {
251 : int nbytes;
252 : int i;
253 :
254 : /* if no elements, return a zero-dimensional array */
255 3478290 : if (num <= 0)
256 : {
257 UBC 0 : Assert(num == 0);
258 0 : a = construct_empty_array(INT4OID);
259 0 : return a;
260 : }
261 :
262 CBC 3478290 : if (num == ARRNELEMS(a))
263 2732704 : return a;
264 :
265 745586 : nbytes = ARR_DATA_OFFSET(a) + sizeof(int) * num;
266 :
267 745586 : a = (ArrayType *) repalloc(a, nbytes);
268 :
269 745586 : SET_VARSIZE(a, nbytes);
270 : /* usually the array should be 1-D already, but just in case ... */
271 1491172 : for (i = 0; i < ARR_NDIM(a); i++)
272 : {
273 745586 : ARR_DIMS(a)[i] = num;
274 745586 : num = 1;
275 : }
276 745586 : return a;
277 : }
278 :
279 : ArrayType *
280 13760 : copy_intArrayType(ArrayType *a)
281 : {
282 : ArrayType *r;
283 13760 : int n = ARRNELEMS(a);
284 :
285 13760 : r = new_intArrayType(n);
286 13760 : memcpy(ARRPTR(r), ARRPTR(a), n * sizeof(int32));
287 13760 : return r;
288 : }
289 :
290 : /* num for compressed key */
291 : int
292 2685 : internal_size(int *a, int len)
293 : {
294 : int i;
295 2685 : int64 size = 0;
296 :
297 271185 : for (i = 0; i < len; i += 2)
298 : {
299 268500 : if (!i || a[i] != a[i - 1]) /* do not count repeated range */
300 268500 : size += (int64) (a[i + 1]) - (int64) (a[i]) + 1;
301 : }
302 :
303 2685 : if (size > (int64) INT_MAX || size < (int64) INT_MIN)
304 UBC 0 : return -1; /* overflow */
305 CBC 2685 : return (int) size;
306 : }
307 :
308 : /* unique-ify elements of r in-place ... r must be sorted already */
309 : ArrayType *
310 1628411 : _int_unique(ArrayType *r)
311 : {
312 1628411 : int num = ARRNELEMS(r);
313 : bool duplicates_found; /* not used */
314 :
315 1628411 : num = qunique_arg(ARRPTR(r), num, sizeof(int), isort_cmp,
316 : &duplicates_found);
317 :
318 1628411 : return resize_intArrayType(r, num);
319 : }
320 :
321 : void
322 UBC 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 CBC 1 : intarray_match_first(ArrayType *a, int32 elem)
336 : {
337 : int32 *aa,
338 : c,
339 : i;
340 :
341 1 : CHECKARRVALID(a);
342 1 : c = ARRNELEMS(a);
343 1 : aa = ARRPTR(a);
344 2 : for (i = 0; i < c; i++)
345 2 : if (aa[i] == elem)
346 1 : return (i + 1);
347 UBC 0 : return 0;
348 : }
349 :
350 : ArrayType *
351 CBC 4 : intarray_add_elem(ArrayType *a, int32 elem)
352 : {
353 : ArrayType *result;
354 : int32 *r;
355 : int32 c;
356 :
357 4 : CHECKARRVALID(a);
358 4 : c = ARRNELEMS(a);
359 4 : result = new_intArrayType(c + 1);
360 4 : r = ARRPTR(result);
361 4 : if (c > 0)
362 4 : memcpy(r, ARRPTR(a), c * sizeof(int32));
363 4 : r[c] = elem;
364 4 : return result;
365 : }
366 :
367 : ArrayType *
368 1 : intarray_concat_arrays(ArrayType *a, ArrayType *b)
369 : {
370 : ArrayType *result;
371 1 : int32 ac = ARRNELEMS(a);
372 1 : int32 bc = ARRNELEMS(b);
373 :
374 1 : CHECKARRVALID(a);
375 1 : CHECKARRVALID(b);
376 1 : result = new_intArrayType(ac + bc);
377 1 : if (ac)
378 1 : memcpy(ARRPTR(result), ARRPTR(a), ac * sizeof(int32));
379 1 : if (bc)
380 1 : memcpy(ARRPTR(result) + ac, ARRPTR(b), bc * sizeof(int32));
381 1 : return result;
382 : }
383 :
384 : ArrayType *
385 GNC 1 : int_to_intset(int32 elem)
386 : {
387 : ArrayType *result;
388 : int32 *aa;
389 :
390 CBC 1 : result = new_intArrayType(1);
391 1 : aa = ARRPTR(result);
392 GNC 1 : aa[0] = elem;
393 CBC 1 : return result;
394 : }
395 :
396 : int
397 27720847 : compASC(const void *a, const void *b)
398 : {
399 27720847 : if (*(const int32 *) a == *(const int32 *) b)
400 104485 : return 0;
401 27616362 : return (*(const int32 *) a > *(const int32 *) b) ? 1 : -1;
402 : }
403 :
404 : int
405 6 : compDESC(const void *a, const void *b)
406 : {
407 6 : if (*(const int32 *) a == *(const int32 *) b)
408 UBC 0 : return 0;
409 CBC 6 : return (*(const int32 *) a < *(const int32 *) b) ? 1 : -1;
410 : }
|
