TLA Line data Source code
1 : /*
2 : * contrib/intarray/_int_gist.c
3 : */
4 : #include "postgres.h"
5 :
6 : #include <limits.h>
7 : #include <math.h>
8 :
9 : #include "_int.h"
10 : #include "access/gist.h"
11 : #include "access/reloptions.h"
12 : #include "access/stratnum.h"
13 :
14 : #define GETENTRY(vec,pos) ((ArrayType *) DatumGetPointer((vec)->vector[(pos)].key))
15 :
16 : /*
17 : * Control the maximum sparseness of compressed keys.
18 : *
19 : * The upper safe bound for this limit is half the maximum allocatable array
20 : * size. A lower bound would give more guarantees that pathological data
21 : * wouldn't eat excessive CPU and memory, but at the expense of breaking
22 : * possibly working (after a fashion) indexes.
23 : */
24 : #define MAXNUMELTS (Min((MaxAllocSize / sizeof(Datum)),((MaxAllocSize - ARR_OVERHEAD_NONULLS(1)) / sizeof(int)))/2)
25 : /* or: #define MAXNUMELTS 1000000 */
26 :
27 : /*
28 : ** GiST support methods
29 : */
30 GIC 2 : PG_FUNCTION_INFO_V1(g_int_consistent);
31 CBC 2 : PG_FUNCTION_INFO_V1(g_int_compress);
32 2 : PG_FUNCTION_INFO_V1(g_int_decompress);
33 2 : PG_FUNCTION_INFO_V1(g_int_penalty);
34 2 : PG_FUNCTION_INFO_V1(g_int_picksplit);
35 2 : PG_FUNCTION_INFO_V1(g_int_union);
36 2 : PG_FUNCTION_INFO_V1(g_int_same);
37 2 : PG_FUNCTION_INFO_V1(g_int_options);
38 ECB :
39 :
40 : /*
41 : ** The GiST Consistent method for _intments
42 : ** Should return false if for all data items x below entry,
43 : ** the predicate x op query == false, where op is the oper
44 : ** corresponding to strategy in the pg_amop table.
45 : */
46 : Datum
47 GIC 88504 : g_int_consistent(PG_FUNCTION_ARGS)
48 ECB : {
49 GIC 88504 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
50 CBC 88504 : ArrayType *query = PG_GETARG_ARRAYTYPE_P_COPY(1);
51 88504 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
52 ECB :
53 : /* Oid subtype = PG_GETARG_OID(3); */
54 GIC 88504 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
55 GNC 88504 : bool retval = false; /* silence compiler warning */
56 ECB :
57 : /* this is exact except for RTSameStrategyNumber */
58 GIC 88504 : *recheck = (strategy == RTSameStrategyNumber);
59 ECB :
60 GIC 88504 : if (strategy == BooleanSearchStrategy)
61 ECB : {
62 GIC 55498 : retval = execconsistent((QUERYTYPE *) query,
63 CBC 55498 : (ArrayType *) DatumGetPointer(entry->key),
64 55498 : GIST_LEAF(entry));
65 ECB :
66 GIC 55498 : pfree(query);
67 CBC 55498 : PG_RETURN_BOOL(retval);
68 ECB : }
69 :
70 : /* sort query for fast search, key is already sorted */
71 GIC 33006 : CHECKARRVALID(query);
72 CBC 33006 : PREPAREARR(query);
73 ECB :
74 GIC 33006 : switch (strategy)
75 ECB : {
76 GIC 11080 : case RTOverlapStrategyNumber:
77 CBC 11080 : retval = inner_int_overlap((ArrayType *) DatumGetPointer(entry->key),
78 ECB : query);
79 GIC 11080 : break;
80 CBC 3125 : case RTSameStrategyNumber:
81 3125 : if (GIST_LEAF(entry))
82 2964 : DirectFunctionCall3(g_int_same,
83 ECB : entry->key,
84 : PointerGetDatum(query),
85 : PointerGetDatum(&retval));
86 : else
87 GIC 161 : retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
88 ECB : query);
89 GIC 3125 : break;
90 CBC 18801 : case RTContainsStrategyNumber:
91 ECB : case RTOldContainsStrategyNumber:
92 GIC 18801 : retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
93 ECB : query);
94 GIC 18801 : break;
95 LBC 0 : case RTContainedByStrategyNumber:
96 EUB : case RTOldContainedByStrategyNumber:
97 :
98 : /*
99 : * This code is unreachable as of intarray 1.4, because the <@
100 : * operator has been removed from the opclass. We keep it for now
101 : * to support older versions of the SQL definitions.
102 : */
103 UIC 0 : if (GIST_LEAF(entry))
104 UBC 0 : retval = inner_int_contains(query,
105 0 : (ArrayType *) DatumGetPointer(entry->key));
106 EUB : else
107 : {
108 : /*
109 : * Unfortunately, because empty arrays could be anywhere in
110 : * the index, we must search the whole tree.
111 : */
112 UIC 0 : retval = true;
113 EUB : }
114 UIC 0 : break;
115 UBC 0 : default:
116 0 : retval = false;
117 EUB : }
118 GIC 33006 : pfree(query);
119 CBC 33006 : PG_RETURN_BOOL(retval);
120 ECB : }
121 :
122 : Datum
123 GIC 22546 : g_int_union(PG_FUNCTION_ARGS)
124 ECB : {
125 GIC 22546 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
126 CBC 22546 : int *size = (int *) PG_GETARG_POINTER(1);
127 ECB : int32 i,
128 : *ptr;
129 : ArrayType *res;
130 GIC 22546 : int totlen = 0;
131 ECB :
132 GIC 67967 : for (i = 0; i < entryvec->n; i++)
133 ECB : {
134 GIC 45421 : ArrayType *ent = GETENTRY(entryvec, i);
135 ECB :
136 GIC 45421 : CHECKARRVALID(ent);
137 CBC 45421 : totlen += ARRNELEMS(ent);
138 ECB : }
139 :
140 GIC 22546 : res = new_intArrayType(totlen);
141 CBC 22546 : ptr = ARRPTR(res);
142 ECB :
143 GIC 67967 : for (i = 0; i < entryvec->n; i++)
144 ECB : {
145 GIC 45421 : ArrayType *ent = GETENTRY(entryvec, i);
146 ECB : int nel;
147 :
148 GIC 45421 : nel = ARRNELEMS(ent);
149 CBC 45421 : memcpy(ptr, ARRPTR(ent), nel * sizeof(int32));
150 45421 : ptr += nel;
151 ECB : }
152 :
153 GIC 22546 : QSORT(res, 1);
154 CBC 22546 : res = _int_unique(res);
155 22546 : *size = VARSIZE(res);
156 22546 : PG_RETURN_POINTER(res);
157 ECB : }
158 :
159 : /*
160 : ** GiST Compress and Decompress methods
161 : */
162 : Datum
163 GIC 17912 : g_int_compress(PG_FUNCTION_ARGS)
164 ECB : {
165 GIC 17912 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
166 ECB : GISTENTRY *retval;
167 : ArrayType *r;
168 GIC 17912 : int num_ranges = G_INT_GET_NUMRANGES();
169 ECB : int len,
170 : lenr;
171 : int *dr;
172 : int i,
173 : j,
174 : cand;
175 : int64 min;
176 :
177 GIC 17912 : if (entry->leafkey)
178 ECB : {
179 GIC 13512 : r = DatumGetArrayTypePCopy(entry->key);
180 CBC 13512 : CHECKARRVALID(r);
181 13512 : PREPAREARR(r);
182 ECB :
183 GIC 13512 : if (ARRNELEMS(r) >= 2 * num_ranges)
184 LBC 0 : elog(NOTICE, "input array is too big (%d maximum allowed, %d current), use gist__intbig_ops opclass instead",
185 EUB : 2 * num_ranges - 1, ARRNELEMS(r));
186 :
187 GIC 13512 : retval = palloc(sizeof(GISTENTRY));
188 CBC 13512 : gistentryinit(*retval, PointerGetDatum(r),
189 ECB : entry->rel, entry->page, entry->offset, false);
190 :
191 GIC 13512 : PG_RETURN_POINTER(retval);
192 ECB : }
193 :
194 : /*
195 : * leaf entries never compress one more time, only when entry->leafkey
196 : * ==true, so now we work only with internal keys
197 : */
198 :
199 GIC 4400 : r = DatumGetArrayTypeP(entry->key);
200 CBC 4400 : CHECKARRVALID(r);
201 4400 : if (ARRISEMPTY(r))
202 ECB : {
203 UIC 0 : if (r != (ArrayType *) DatumGetPointer(entry->key))
204 UBC 0 : pfree(r);
205 0 : PG_RETURN_POINTER(entry);
206 EUB : }
207 :
208 GIC 4400 : if ((len = ARRNELEMS(r)) >= 2 * num_ranges)
209 ECB : { /* compress */
210 GIC 164 : if (r == (ArrayType *) DatumGetPointer(entry->key))
211 CBC 164 : r = DatumGetArrayTypePCopy(entry->key);
212 164 : r = resize_intArrayType(r, 2 * (len));
213 ECB :
214 GIC 164 : dr = ARRPTR(r);
215 ECB :
216 : /*
217 : * "len" at this point is the number of ranges we will construct.
218 : * "lenr" is the number of ranges we must eventually remove by
219 : * merging, we must be careful to remove no more than this number.
220 : */
221 GIC 164 : lenr = len - num_ranges;
222 ECB :
223 : /*
224 : * Initially assume we can merge consecutive ints into a range. but we
225 : * must count every value removed and stop when lenr runs out
226 : */
227 GIC 4771 : for (j = i = len - 1; i > 0 && lenr > 0; i--, j--)
228 ECB : {
229 GIC 4607 : int r_end = dr[i];
230 CBC 4607 : int r_start = r_end;
231 ECB :
232 GIC 28468 : while (i > 0 && lenr > 0 && dr[i - 1] == r_start - 1)
233 CBC 23861 : --r_start, --i, --lenr;
234 4607 : dr[2 * j] = r_start;
235 4607 : dr[2 * j + 1] = r_end;
236 ECB : }
237 : /* just copy the rest, if any, as trivial ranges */
238 GIC 11957 : for (; i >= 0; i--, j--)
239 CBC 11793 : dr[2 * j] = dr[2 * j + 1] = dr[i];
240 ECB :
241 GIC 164 : if (++j)
242 ECB : {
243 : /*
244 : * shunt everything down to start at the right place
245 : */
246 GNC 164 : memmove(&dr[0], &dr[2 * j], 2 * (len - j) * sizeof(int32));
247 ECB : }
248 :
249 : /*
250 : * make "len" be number of array elements, not ranges
251 : */
252 GIC 164 : len = 2 * (len - j);
253 CBC 164 : cand = 1;
254 164 : while (len > num_ranges * 2)
255 ECB : {
256 UIC 0 : min = PG_INT64_MAX;
257 UBC 0 : for (i = 2; i < len; i += 2)
258 0 : if (min > ((int64) dr[i] - (int64) dr[i - 1]))
259 EUB : {
260 UIC 0 : min = ((int64) dr[i] - (int64) dr[i - 1]);
261 UBC 0 : cand = i;
262 EUB : }
263 UNC 0 : memmove(&dr[cand - 1], &dr[cand + 1], (len - cand - 1) * sizeof(int32));
264 UBC 0 : len -= 2;
265 EUB : }
266 :
267 : /*
268 : * check sparseness of result
269 : */
270 GIC 164 : lenr = internal_size(dr, len);
271 CBC 164 : if (lenr < 0 || lenr > MAXNUMELTS)
272 LBC 0 : ereport(ERROR,
273 EUB : (errmsg("data is too sparse, recreate index using gist__intbig_ops opclass instead")));
274 :
275 GIC 164 : r = resize_intArrayType(r, len);
276 CBC 164 : retval = palloc(sizeof(GISTENTRY));
277 164 : gistentryinit(*retval, PointerGetDatum(r),
278 ECB : entry->rel, entry->page, entry->offset, false);
279 GIC 164 : PG_RETURN_POINTER(retval);
280 ECB : }
281 : else
282 GIC 4236 : PG_RETURN_POINTER(entry);
283 ECB : }
284 :
285 : Datum
286 GIC 332114 : g_int_decompress(PG_FUNCTION_ARGS)
287 ECB : {
288 GIC 332114 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
289 ECB : GISTENTRY *retval;
290 : ArrayType *r;
291 GIC 332114 : int num_ranges = G_INT_GET_NUMRANGES();
292 ECB : int *dr,
293 : lenr;
294 : ArrayType *in;
295 : int lenin;
296 : int *din;
297 : int i,
298 : j;
299 :
300 GIC 332114 : in = DatumGetArrayTypeP(entry->key);
301 ECB :
302 GIC 332114 : CHECKARRVALID(in);
303 CBC 332114 : if (ARRISEMPTY(in))
304 ECB : {
305 GIC 258 : if (in != (ArrayType *) DatumGetPointer(entry->key))
306 ECB : {
307 GIC 258 : retval = palloc(sizeof(GISTENTRY));
308 CBC 258 : gistentryinit(*retval, PointerGetDatum(in),
309 ECB : entry->rel, entry->page, entry->offset, false);
310 GIC 258 : PG_RETURN_POINTER(retval);
311 ECB : }
312 :
313 UIC 0 : PG_RETURN_POINTER(entry);
314 EUB : }
315 :
316 GIC 331856 : lenin = ARRNELEMS(in);
317 ECB :
318 GIC 331856 : if (lenin < 2 * num_ranges)
319 ECB : { /* not compressed value */
320 GIC 329335 : if (in != (ArrayType *) DatumGetPointer(entry->key))
321 ECB : {
322 GIC 152062 : retval = palloc(sizeof(GISTENTRY));
323 CBC 152062 : gistentryinit(*retval, PointerGetDatum(in),
324 ECB : entry->rel, entry->page, entry->offset, false);
325 :
326 GIC 152062 : PG_RETURN_POINTER(retval);
327 ECB : }
328 GIC 177273 : PG_RETURN_POINTER(entry);
329 ECB : }
330 :
331 GIC 2521 : din = ARRPTR(in);
332 CBC 2521 : lenr = internal_size(din, lenin);
333 2521 : if (lenr < 0 || lenr > MAXNUMELTS)
334 LBC 0 : ereport(ERROR,
335 EUB : (errmsg("compressed array is too big, recreate index using gist__intbig_ops opclass instead")));
336 :
337 GIC 2521 : r = new_intArrayType(lenr);
338 CBC 2521 : dr = ARRPTR(r);
339 ECB :
340 GIC 254621 : for (i = 0; i < lenin; i += 2)
341 CBC 891392 : for (j = din[i]; j <= din[i + 1]; j++)
342 639292 : if ((!i) || *(dr - 1) != j)
343 639292 : *dr++ = j;
344 ECB :
345 GIC 2521 : if (in != (ArrayType *) DatumGetPointer(entry->key))
346 CBC 2521 : pfree(in);
347 2521 : retval = palloc(sizeof(GISTENTRY));
348 2521 : gistentryinit(*retval, PointerGetDatum(r),
349 ECB : entry->rel, entry->page, entry->offset, false);
350 :
351 GIC 2521 : PG_RETURN_POINTER(retval);
352 ECB : }
353 :
354 : /*
355 : ** The GiST Penalty method for _intments
356 : */
357 : Datum
358 GIC 152743 : g_int_penalty(PG_FUNCTION_ARGS)
359 ECB : {
360 GIC 152743 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
361 CBC 152743 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
362 152743 : float *result = (float *) PG_GETARG_POINTER(2);
363 ECB : ArrayType *ud;
364 : float tmp1,
365 : tmp2;
366 :
367 GIC 152743 : ud = inner_int_union((ArrayType *) DatumGetPointer(origentry->key),
368 CBC 152743 : (ArrayType *) DatumGetPointer(newentry->key));
369 152743 : rt__int_size(ud, &tmp1);
370 152743 : rt__int_size((ArrayType *) DatumGetPointer(origentry->key), &tmp2);
371 152743 : *result = tmp1 - tmp2;
372 152743 : pfree(ud);
373 ECB :
374 GIC 152743 : PG_RETURN_POINTER(result);
375 ECB : }
376 :
377 :
378 :
379 : Datum
380 GIC 25501 : g_int_same(PG_FUNCTION_ARGS)
381 ECB : {
382 GIC 25501 : ArrayType *a = PG_GETARG_ARRAYTYPE_P(0);
383 CBC 25501 : ArrayType *b = PG_GETARG_ARRAYTYPE_P(1);
384 25501 : bool *result = (bool *) PG_GETARG_POINTER(2);
385 25501 : int32 n = ARRNELEMS(a);
386 ECB : int32 *da,
387 : *db;
388 :
389 GIC 25501 : CHECKARRVALID(a);
390 CBC 25501 : CHECKARRVALID(b);
391 ECB :
392 GIC 25501 : if (n != ARRNELEMS(b))
393 ECB : {
394 GIC 6411 : *result = false;
395 CBC 6411 : PG_RETURN_POINTER(result);
396 ECB : }
397 GIC 19090 : *result = true;
398 CBC 19090 : da = ARRPTR(a);
399 19090 : db = ARRPTR(b);
400 2023059 : while (n--)
401 ECB : {
402 GIC 2004567 : if (*da++ != *db++)
403 ECB : {
404 GIC 598 : *result = false;
405 CBC 598 : break;
406 ECB : }
407 : }
408 :
409 GIC 19090 : PG_RETURN_POINTER(result);
410 ECB : }
411 :
412 : /*****************************************************************
413 : ** Common GiST Method
414 : *****************************************************************/
415 :
416 : typedef struct
417 : {
418 : OffsetNumber pos;
419 : float cost;
420 : } SPLITCOST;
421 :
422 : static int
423 GIC 37571 : comparecost(const void *a, const void *b)
424 ECB : {
425 GIC 37571 : if (((const SPLITCOST *) a)->cost == ((const SPLITCOST *) b)->cost)
426 CBC 22188 : return 0;
427 ECB : else
428 GIC 15383 : return (((const SPLITCOST *) a)->cost > ((const SPLITCOST *) b)->cost) ? 1 : -1;
429 ECB : }
430 :
431 : /*
432 : ** The GiST PickSplit method for _intments
433 : ** We use Guttman's poly time split algorithm
434 : */
435 : Datum
436 GIC 174 : g_int_picksplit(PG_FUNCTION_ARGS)
437 ECB : {
438 GIC 174 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
439 CBC 174 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
440 ECB : OffsetNumber i,
441 : j;
442 : ArrayType *datum_alpha,
443 : *datum_beta;
444 : ArrayType *datum_l,
445 : *datum_r;
446 : ArrayType *union_d,
447 : *union_dl,
448 : *union_dr;
449 : ArrayType *inter_d;
450 : bool firsttime;
451 : float size_alpha,
452 : size_beta,
453 : size_union,
454 : size_inter;
455 : float size_waste,
456 : waste;
457 : float size_l,
458 : size_r;
459 : int nbytes;
460 GIC 174 : OffsetNumber seed_1 = 0,
461 CBC 174 : seed_2 = 0;
462 ECB : OffsetNumber *left,
463 : *right;
464 : OffsetNumber maxoff;
465 : SPLITCOST *costvector;
466 :
467 : #ifdef GIST_DEBUG
468 : elog(DEBUG3, "--------picksplit %d", entryvec->n);
469 : #endif
470 :
471 GIC 174 : maxoff = entryvec->n - 2;
472 CBC 174 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
473 174 : v->spl_left = (OffsetNumber *) palloc(nbytes);
474 174 : v->spl_right = (OffsetNumber *) palloc(nbytes);
475 ECB :
476 GIC 174 : firsttime = true;
477 CBC 174 : waste = 0.0;
478 20536 : for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i))
479 ECB : {
480 GIC 20362 : datum_alpha = GETENTRY(entryvec, i);
481 CBC 1383601 : for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j))
482 ECB : {
483 GIC 1363239 : datum_beta = GETENTRY(entryvec, j);
484 ECB :
485 : /* compute the wasted space by unioning these guys */
486 : /* size_waste = size_union - size_inter; */
487 GIC 1363239 : union_d = inner_int_union(datum_alpha, datum_beta);
488 CBC 1363239 : rt__int_size(union_d, &size_union);
489 1363239 : inter_d = inner_int_inter(datum_alpha, datum_beta);
490 1363239 : rt__int_size(inter_d, &size_inter);
491 1363239 : size_waste = size_union - size_inter;
492 ECB :
493 GIC 1363239 : pfree(union_d);
494 CBC 1363239 : pfree(inter_d);
495 ECB :
496 : /*
497 : * are these a more promising split that what we've already seen?
498 : */
499 :
500 GIC 1363239 : if (size_waste > waste || firsttime)
501 ECB : {
502 GIC 974 : waste = size_waste;
503 CBC 974 : seed_1 = i;
504 974 : seed_2 = j;
505 974 : firsttime = false;
506 ECB : }
507 : }
508 : }
509 :
510 GIC 174 : left = v->spl_left;
511 CBC 174 : v->spl_nleft = 0;
512 174 : right = v->spl_right;
513 174 : v->spl_nright = 0;
514 174 : if (seed_1 == 0 || seed_2 == 0)
515 ECB : {
516 UIC 0 : seed_1 = 1;
517 UBC 0 : seed_2 = 2;
518 EUB : }
519 :
520 GIC 174 : datum_alpha = GETENTRY(entryvec, seed_1);
521 CBC 174 : datum_l = copy_intArrayType(datum_alpha);
522 174 : rt__int_size(datum_l, &size_l);
523 174 : datum_beta = GETENTRY(entryvec, seed_2);
524 174 : datum_r = copy_intArrayType(datum_beta);
525 174 : rt__int_size(datum_r, &size_r);
526 ECB :
527 GIC 174 : maxoff = OffsetNumberNext(maxoff);
528 ECB :
529 : /*
530 : * sort entries
531 : */
532 GIC 174 : costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
533 CBC 20884 : for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
534 ECB : {
535 GIC 20710 : costvector[i - 1].pos = i;
536 CBC 20710 : datum_alpha = GETENTRY(entryvec, i);
537 20710 : union_d = inner_int_union(datum_l, datum_alpha);
538 20710 : rt__int_size(union_d, &size_alpha);
539 20710 : pfree(union_d);
540 20710 : union_d = inner_int_union(datum_r, datum_alpha);
541 20710 : rt__int_size(union_d, &size_beta);
542 20710 : pfree(union_d);
543 GNC 20710 : costvector[i - 1].cost = fabsf((size_alpha - size_l) - (size_beta - size_r));
544 ECB : }
545 GNC 174 : qsort(costvector, maxoff, sizeof(SPLITCOST), comparecost);
546 ECB :
547 : /*
548 : * Now split up the regions between the two seeds. An important property
549 : * of this split algorithm is that the split vector v has the indices of
550 : * items to be split in order in its left and right vectors. We exploit
551 : * this property by doing a merge in the code that actually splits the
552 : * page.
553 : *
554 : * For efficiency, we also place the new index tuple in this loop. This is
555 : * handled at the very end, when we have placed all the existing tuples
556 : * and i == maxoff + 1.
557 : */
558 :
559 :
560 GIC 20884 : for (j = 0; j < maxoff; j++)
561 ECB : {
562 GIC 20710 : i = costvector[j].pos;
563 ECB :
564 : /*
565 : * If we've already decided where to place this item, just put it on
566 : * the right list. Otherwise, we need to figure out which page needs
567 : * the least enlargement in order to store the item.
568 : */
569 :
570 GIC 20710 : if (i == seed_1)
571 ECB : {
572 GIC 174 : *left++ = i;
573 CBC 174 : v->spl_nleft++;
574 174 : continue;
575 ECB : }
576 GIC 20536 : else if (i == seed_2)
577 ECB : {
578 GIC 174 : *right++ = i;
579 CBC 174 : v->spl_nright++;
580 174 : continue;
581 ECB : }
582 :
583 : /* okay, which page needs least enlargement? */
584 GIC 20362 : datum_alpha = GETENTRY(entryvec, i);
585 CBC 20362 : union_dl = inner_int_union(datum_l, datum_alpha);
586 20362 : union_dr = inner_int_union(datum_r, datum_alpha);
587 20362 : rt__int_size(union_dl, &size_alpha);
588 20362 : rt__int_size(union_dr, &size_beta);
589 ECB :
590 : /* pick which page to add it to */
591 GIC 20362 : if (size_alpha - size_l < size_beta - size_r + WISH_F(v->spl_nleft, v->spl_nright, 0.01))
592 ECB : {
593 GIC 10071 : pfree(datum_l);
594 CBC 10071 : pfree(union_dr);
595 10071 : datum_l = union_dl;
596 10071 : size_l = size_alpha;
597 10071 : *left++ = i;
598 10071 : v->spl_nleft++;
599 ECB : }
600 : else
601 : {
602 GIC 10291 : pfree(datum_r);
603 CBC 10291 : pfree(union_dl);
604 10291 : datum_r = union_dr;
605 10291 : size_r = size_beta;
606 10291 : *right++ = i;
607 10291 : v->spl_nright++;
608 ECB : }
609 : }
610 GIC 174 : pfree(costvector);
611 CBC 174 : *right = *left = FirstOffsetNumber;
612 ECB :
613 GIC 174 : v->spl_ldatum = PointerGetDatum(datum_l);
614 CBC 174 : v->spl_rdatum = PointerGetDatum(datum_r);
615 ECB :
616 GIC 174 : PG_RETURN_POINTER(v);
617 ECB : }
618 :
619 : Datum
620 GIC 9 : g_int_options(PG_FUNCTION_ARGS)
621 ECB : {
622 GIC 9 : local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
623 ECB :
624 GIC 9 : init_local_reloptions(relopts, sizeof(GISTIntArrayOptions));
625 CBC 9 : add_local_int_reloption(relopts, "numranges",
626 ECB : "number of ranges for compression",
627 : G_INT_NUMRANGES_DEFAULT, 1, G_INT_NUMRANGES_MAX,
628 : offsetof(GISTIntArrayOptions, num_ranges));
629 :
630 GIC 9 : PG_RETURN_VOID();
631 ECB : }
|
