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