Branch data Line data Source code
1 : : /*
2 : : * contrib/seg/seg.c
3 : : *
4 : : *
5 : : * This file contains routines that can be bound to a Postgres backend and
6 : : * called by the backend in the process of processing queries. The calling
7 : : * format for these routines is dictated by Postgres architecture.
8 : : */
9 : :
10 : : #include "postgres.h"
11 : :
12 : : #include <float.h>
13 : : #include <math.h>
14 : :
15 : : #include "access/gist.h"
16 : : #include "access/stratnum.h"
17 : : #include "fmgr.h"
18 : :
19 : : #include "segdata.h"
20 : :
21 : :
22 : : #define DatumGetSegP(X) ((SEG *) DatumGetPointer(X))
23 : : #define PG_GETARG_SEG_P(n) DatumGetSegP(PG_GETARG_DATUM(n))
24 : :
25 : :
26 : : /*
27 : : * #define GIST_DEBUG
28 : : * #define GIST_QUERY_DEBUG
29 : : */
30 : :
31 : 3 : PG_MODULE_MAGIC_EXT(
32 : : .name = "seg",
33 : : .version = PG_VERSION
34 : : );
35 : :
36 : : /*
37 : : * Auxiliary data structure for picksplit method.
38 : : */
39 : : typedef struct
40 : : {
41 : : float center;
42 : : OffsetNumber index;
43 : : SEG *data;
44 : : } gseg_picksplit_item;
45 : :
46 : : /*
47 : : * Input/Output routines
48 : : */
49 : 4 : PG_FUNCTION_INFO_V1(seg_in);
50 : 3 : PG_FUNCTION_INFO_V1(seg_out);
51 : 2 : PG_FUNCTION_INFO_V1(seg_size);
52 : 3 : PG_FUNCTION_INFO_V1(seg_lower);
53 : 3 : PG_FUNCTION_INFO_V1(seg_upper);
54 : 3 : PG_FUNCTION_INFO_V1(seg_center);
55 : :
56 : : /*
57 : : * GiST support methods
58 : : */
59 : 3 : PG_FUNCTION_INFO_V1(gseg_consistent);
60 : 2 : PG_FUNCTION_INFO_V1(gseg_compress);
61 : 2 : PG_FUNCTION_INFO_V1(gseg_decompress);
62 : 3 : PG_FUNCTION_INFO_V1(gseg_picksplit);
63 : 3 : PG_FUNCTION_INFO_V1(gseg_penalty);
64 : 3 : PG_FUNCTION_INFO_V1(gseg_union);
65 : 3 : PG_FUNCTION_INFO_V1(gseg_same);
66 : : static Datum gseg_leaf_consistent(Datum key, Datum query, StrategyNumber strategy);
67 : : static Datum gseg_internal_consistent(Datum key, Datum query, StrategyNumber strategy);
68 : : static Datum gseg_binary_union(Datum r1, Datum r2, int *sizep);
69 : :
70 : :
71 : : /*
72 : : * R-tree support functions
73 : : */
74 : 3 : PG_FUNCTION_INFO_V1(seg_same);
75 : 3 : PG_FUNCTION_INFO_V1(seg_contains);
76 : 3 : PG_FUNCTION_INFO_V1(seg_contained);
77 : 3 : PG_FUNCTION_INFO_V1(seg_overlap);
78 : 3 : PG_FUNCTION_INFO_V1(seg_left);
79 : 3 : PG_FUNCTION_INFO_V1(seg_over_left);
80 : 3 : PG_FUNCTION_INFO_V1(seg_right);
81 : 3 : PG_FUNCTION_INFO_V1(seg_over_right);
82 : 2 : PG_FUNCTION_INFO_V1(seg_union);
83 : 2 : PG_FUNCTION_INFO_V1(seg_inter);
84 : : static void rt_seg_size(SEG *a, float *size);
85 : :
86 : : /*
87 : : * Various operators
88 : : */
89 : 4 : PG_FUNCTION_INFO_V1(seg_cmp);
90 : 2 : PG_FUNCTION_INFO_V1(seg_lt);
91 : 2 : PG_FUNCTION_INFO_V1(seg_le);
92 : 2 : PG_FUNCTION_INFO_V1(seg_gt);
93 : 2 : PG_FUNCTION_INFO_V1(seg_ge);
94 : 3 : PG_FUNCTION_INFO_V1(seg_different);
95 : :
96 : : /*
97 : : * Auxiliary functions
98 : : */
99 : : static int restore(char *result, float val, int n);
100 : :
101 : :
102 : : /*****************************************************************************
103 : : * Input/Output functions
104 : : *****************************************************************************/
105 : :
106 : : Datum
107 : 2832 : seg_in(PG_FUNCTION_ARGS)
108 : : {
109 : 2832 : char *str = PG_GETARG_CSTRING(0);
110 : 2832 : SEG *result = palloc_object(SEG);
111 : : yyscan_t scanner;
112 : :
113 : 2832 : seg_scanner_init(str, &scanner);
114 : :
115 [ + + ]: 2832 : if (seg_yyparse(result, fcinfo->context, scanner) != 0)
116 : 8 : seg_yyerror(result, fcinfo->context, scanner, "bogus input");
117 : :
118 : 2823 : seg_scanner_finish(scanner);
119 : :
120 : 2823 : PG_RETURN_POINTER(result);
121 : : }
122 : :
123 : : Datum
124 : 216 : seg_out(PG_FUNCTION_ARGS)
125 : : {
126 : 216 : SEG *seg = PG_GETARG_SEG_P(0);
127 : : char *result;
128 : : char *p;
129 : :
130 : 216 : p = result = (char *) palloc(40);
131 : :
132 [ + + + + : 216 : if (seg->l_ext == '>' || seg->l_ext == '<' || seg->l_ext == '~')
+ + ]
133 : 26 : p += sprintf(p, "%c", seg->l_ext);
134 : :
135 [ + + + - ]: 216 : if (seg->lower == seg->upper && seg->l_ext == seg->u_ext)
136 : : {
137 : : /*
138 : : * indicates that this interval was built by seg_in off a single point
139 : : */
140 : 47 : p += restore(p, seg->lower, seg->l_sigd);
141 : : }
142 : : else
143 : : {
144 [ + + ]: 169 : if (seg->l_ext != '-')
145 : : {
146 : : /* print the lower boundary if exists */
147 : 162 : p += restore(p, seg->lower, seg->l_sigd);
148 : 162 : p += sprintf(p, " ");
149 : : }
150 : 169 : p += sprintf(p, "..");
151 [ + + ]: 169 : if (seg->u_ext != '-')
152 : : {
153 : : /* print the upper boundary if exists */
154 : 130 : p += sprintf(p, " ");
155 [ + + + + : 130 : if (seg->u_ext == '>' || seg->u_ext == '<' || seg->u_ext == '~')
+ + ]
156 : 36 : p += sprintf(p, "%c", seg->u_ext);
157 : 130 : p += restore(p, seg->upper, seg->u_sigd);
158 : : }
159 : : }
160 : :
161 : 216 : PG_RETURN_CSTRING(result);
162 : : }
163 : :
164 : : Datum
165 : 143 : seg_center(PG_FUNCTION_ARGS)
166 : : {
167 : 143 : SEG *seg = PG_GETARG_SEG_P(0);
168 : :
169 : 143 : PG_RETURN_FLOAT4(((float) seg->lower + (float) seg->upper) / 2.0);
170 : : }
171 : :
172 : : Datum
173 : 143 : seg_lower(PG_FUNCTION_ARGS)
174 : : {
175 : 143 : SEG *seg = PG_GETARG_SEG_P(0);
176 : :
177 : 143 : PG_RETURN_FLOAT4(seg->lower);
178 : : }
179 : :
180 : : Datum
181 : 143 : seg_upper(PG_FUNCTION_ARGS)
182 : : {
183 : 143 : SEG *seg = PG_GETARG_SEG_P(0);
184 : :
185 : 143 : PG_RETURN_FLOAT4(seg->upper);
186 : : }
187 : :
188 : :
189 : : /*****************************************************************************
190 : : * GiST functions
191 : : *****************************************************************************/
192 : :
193 : : /*
194 : : * The GiST Consistent method for segments
195 : : * Should return false if for all data items x below entry,
196 : : * the predicate x op query == false, where op is the oper
197 : : * corresponding to strategy in the pg_amop table.
198 : : */
199 : : Datum
200 : 5788 : gseg_consistent(PG_FUNCTION_ARGS)
201 : : {
202 : 5788 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
203 : 5788 : Datum query = PG_GETARG_DATUM(1);
204 : 5788 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
205 : : #ifdef NOT_USED
206 : : Oid subtype = PG_GETARG_OID(3);
207 : : #endif
208 : 5788 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
209 : :
210 : : /* All cases served by this function are exact */
211 : 5788 : *recheck = false;
212 : :
213 : : /*
214 : : * if entry is not leaf, use gseg_internal_consistent, else use
215 : : * gseg_leaf_consistent
216 : : */
217 [ + + ]: 5788 : if (GIST_LEAF(entry))
218 : 5720 : return gseg_leaf_consistent(entry->key, query, strategy);
219 : : else
220 : 68 : return gseg_internal_consistent(entry->key, query, strategy);
221 : : }
222 : :
223 : : /*
224 : : * The GiST Union method for segments
225 : : * returns the minimal bounding seg that encloses all the entries in entryvec
226 : : */
227 : : Datum
228 : 2316 : gseg_union(PG_FUNCTION_ARGS)
229 : : {
230 : 2316 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
231 : 2316 : int *sizep = (int *) PG_GETARG_POINTER(1);
232 : : int numranges,
233 : : i;
234 : 2316 : Datum out = 0;
235 : : Datum tmp;
236 : :
237 : : #ifdef GIST_DEBUG
238 : : fprintf(stderr, "union\n");
239 : : #endif
240 : :
241 : 2316 : numranges = entryvec->n;
242 : 2316 : tmp = entryvec->vector[0].key;
243 : 2316 : *sizep = sizeof(SEG);
244 : :
245 [ + + ]: 4632 : for (i = 1; i < numranges; i++)
246 : : {
247 : 2316 : out = gseg_binary_union(tmp, entryvec->vector[i].key, sizep);
248 : 2316 : tmp = out;
249 : : }
250 : :
251 : 2316 : PG_RETURN_DATUM(out);
252 : : }
253 : :
254 : : /*
255 : : * GiST Compress and Decompress methods for segments
256 : : * do not do anything.
257 : : */
258 : : Datum
259 : 0 : gseg_compress(PG_FUNCTION_ARGS)
260 : : {
261 : 0 : PG_RETURN_POINTER(PG_GETARG_POINTER(0));
262 : : }
263 : :
264 : : Datum
265 : 0 : gseg_decompress(PG_FUNCTION_ARGS)
266 : : {
267 : 0 : PG_RETURN_POINTER(PG_GETARG_POINTER(0));
268 : : }
269 : :
270 : : /*
271 : : * The GiST Penalty method for segments
272 : : * As in the R-tree paper, we use change in area as our penalty metric
273 : : */
274 : : Datum
275 : 5222 : gseg_penalty(PG_FUNCTION_ARGS)
276 : : {
277 : 5222 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
278 : 5222 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
279 : 5222 : float *result = (float *) PG_GETARG_POINTER(2);
280 : : SEG *ud;
281 : : float tmp1,
282 : : tmp2;
283 : :
284 : 5222 : ud = DatumGetSegP(DirectFunctionCall2(seg_union,
285 : : origentry->key,
286 : : newentry->key));
287 : 5222 : rt_seg_size(ud, &tmp1);
288 : 5222 : rt_seg_size(DatumGetSegP(origentry->key), &tmp2);
289 : 5222 : *result = tmp1 - tmp2;
290 : :
291 : : #ifdef GIST_DEBUG
292 : : fprintf(stderr, "penalty\n");
293 : : fprintf(stderr, "\t%g\n", *result);
294 : : #endif
295 : :
296 : 5222 : PG_RETURN_POINTER(result);
297 : : }
298 : :
299 : : /*
300 : : * Compare function for gseg_picksplit_item: sort by center.
301 : : */
302 : : static int
303 : 27367 : gseg_picksplit_item_cmp(const void *a, const void *b)
304 : : {
305 : 27367 : const gseg_picksplit_item *i1 = (const gseg_picksplit_item *) a;
306 : 27367 : const gseg_picksplit_item *i2 = (const gseg_picksplit_item *) b;
307 : :
308 [ + + ]: 27367 : if (i1->center < i2->center)
309 : 11244 : return -1;
310 [ + + ]: 16123 : else if (i1->center == i2->center)
311 : 4971 : return 0;
312 : : else
313 : 11152 : return 1;
314 : : }
315 : :
316 : : /*
317 : : * The GiST PickSplit method for segments
318 : : *
319 : : * We used to use Guttman's split algorithm here, but since the data is 1-D
320 : : * it's easier and more robust to just sort the segments by center-point and
321 : : * split at the middle.
322 : : */
323 : : Datum
324 : 16 : gseg_picksplit(PG_FUNCTION_ARGS)
325 : : {
326 : 16 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
327 : 16 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
328 : : int i;
329 : : SEG *seg,
330 : : *seg_l,
331 : : *seg_r;
332 : : gseg_picksplit_item *sort_items;
333 : : OffsetNumber *left,
334 : : *right;
335 : : OffsetNumber maxoff;
336 : : OffsetNumber firstright;
337 : :
338 : : #ifdef GIST_DEBUG
339 : : fprintf(stderr, "picksplit\n");
340 : : #endif
341 : :
342 : : /* Valid items in entryvec->vector[] are indexed 1..maxoff */
343 : 16 : maxoff = entryvec->n - 1;
344 : :
345 : : /*
346 : : * Prepare the auxiliary array and sort it.
347 : : */
348 : 16 : sort_items = palloc_array(gseg_picksplit_item, maxoff);
349 [ + + ]: 4208 : for (i = 1; i <= maxoff; i++)
350 : : {
351 : 4192 : seg = DatumGetSegP(entryvec->vector[i].key);
352 : : /* center calculation is done this way to avoid possible overflow */
353 : 4192 : sort_items[i - 1].center = seg->lower * 0.5f + seg->upper * 0.5f;
354 : 4192 : sort_items[i - 1].index = i;
355 : 4192 : sort_items[i - 1].data = seg;
356 : : }
357 : 16 : qsort(sort_items, maxoff, sizeof(gseg_picksplit_item),
358 : : gseg_picksplit_item_cmp);
359 : :
360 : : /* sort items below "firstright" will go into the left side */
361 : 16 : firstright = maxoff / 2;
362 : :
363 : 16 : v->spl_left = palloc_array(OffsetNumber, maxoff);
364 : 16 : v->spl_right = palloc_array(OffsetNumber, maxoff);
365 : 16 : left = v->spl_left;
366 : 16 : v->spl_nleft = 0;
367 : 16 : right = v->spl_right;
368 : 16 : v->spl_nright = 0;
369 : :
370 : : /*
371 : : * Emit segments to the left output page, and compute its bounding box.
372 : : */
373 : 16 : seg_l = palloc_object(SEG);
374 : 16 : memcpy(seg_l, sort_items[0].data, sizeof(SEG));
375 : 16 : *left++ = sort_items[0].index;
376 : 16 : v->spl_nleft++;
377 [ + + ]: 2096 : for (i = 1; i < firstright; i++)
378 : : {
379 : 2080 : Datum sortitem = PointerGetDatum(sort_items[i].data);
380 : :
381 : 2080 : seg_l = DatumGetSegP(DirectFunctionCall2(seg_union,
382 : : PointerGetDatum(seg_l),
383 : : sortitem));
384 : 2080 : *left++ = sort_items[i].index;
385 : 2080 : v->spl_nleft++;
386 : : }
387 : :
388 : : /*
389 : : * Likewise for the right page.
390 : : */
391 : 16 : seg_r = palloc_object(SEG);
392 : 16 : memcpy(seg_r, sort_items[firstright].data, sizeof(SEG));
393 : 16 : *right++ = sort_items[firstright].index;
394 : 16 : v->spl_nright++;
395 [ + + ]: 2096 : for (i = firstright + 1; i < maxoff; i++)
396 : : {
397 : 2080 : Datum sortitem = PointerGetDatum(sort_items[i].data);
398 : :
399 : 2080 : seg_r = DatumGetSegP(DirectFunctionCall2(seg_union,
400 : : PointerGetDatum(seg_r),
401 : : sortitem));
402 : 2080 : *right++ = sort_items[i].index;
403 : 2080 : v->spl_nright++;
404 : : }
405 : :
406 : 16 : v->spl_ldatum = PointerGetDatum(seg_l);
407 : 16 : v->spl_rdatum = PointerGetDatum(seg_r);
408 : :
409 : 16 : PG_RETURN_POINTER(v);
410 : : }
411 : :
412 : : /*
413 : : * Equality methods
414 : : */
415 : : Datum
416 : 2315 : gseg_same(PG_FUNCTION_ARGS)
417 : : {
418 : 2315 : bool *result = (bool *) PG_GETARG_POINTER(2);
419 : :
420 [ + + ]: 2315 : if (DatumGetBool(DirectFunctionCall2(seg_same, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1))))
421 : 2280 : *result = true;
422 : : else
423 : 35 : *result = false;
424 : :
425 : : #ifdef GIST_DEBUG
426 : : fprintf(stderr, "same: %s\n", (*result ? "TRUE" : "FALSE"));
427 : : #endif
428 : :
429 : 2315 : PG_RETURN_POINTER(result);
430 : : }
431 : :
432 : : /*
433 : : * SUPPORT ROUTINES
434 : : */
435 : : static Datum
436 : 5720 : gseg_leaf_consistent(Datum key, Datum query, StrategyNumber strategy)
437 : : {
438 : : Datum retval;
439 : :
440 : : #ifdef GIST_QUERY_DEBUG
441 : : fprintf(stderr, "leaf_consistent, %d\n", strategy);
442 : : #endif
443 : :
444 [ - - - - : 5720 : switch (strategy)
- - + -
- ]
445 : : {
446 : 0 : case RTLeftStrategyNumber:
447 : 0 : retval = DirectFunctionCall2(seg_left, key, query);
448 : 0 : break;
449 : 0 : case RTOverLeftStrategyNumber:
450 : 0 : retval = DirectFunctionCall2(seg_over_left, key, query);
451 : 0 : break;
452 : 0 : case RTOverlapStrategyNumber:
453 : 0 : retval = DirectFunctionCall2(seg_overlap, key, query);
454 : 0 : break;
455 : 0 : case RTOverRightStrategyNumber:
456 : 0 : retval = DirectFunctionCall2(seg_over_right, key, query);
457 : 0 : break;
458 : 0 : case RTRightStrategyNumber:
459 : 0 : retval = DirectFunctionCall2(seg_right, key, query);
460 : 0 : break;
461 : 0 : case RTSameStrategyNumber:
462 : 0 : retval = DirectFunctionCall2(seg_same, key, query);
463 : 0 : break;
464 : 5720 : case RTContainsStrategyNumber:
465 : : case RTOldContainsStrategyNumber:
466 : 5720 : retval = DirectFunctionCall2(seg_contains, key, query);
467 : 5720 : break;
468 : 0 : case RTContainedByStrategyNumber:
469 : : case RTOldContainedByStrategyNumber:
470 : 0 : retval = DirectFunctionCall2(seg_contained, key, query);
471 : 0 : break;
472 : 0 : default:
473 : 0 : retval = BoolGetDatum(false);
474 : : }
475 : :
476 : 5720 : PG_RETURN_DATUM(retval);
477 : : }
478 : :
479 : : static Datum
480 : 68 : gseg_internal_consistent(Datum key, Datum query, StrategyNumber strategy)
481 : : {
482 : : bool retval;
483 : :
484 : : #ifdef GIST_QUERY_DEBUG
485 : : fprintf(stderr, "internal_consistent, %d\n", strategy);
486 : : #endif
487 : :
488 [ - - - - : 68 : switch (strategy)
- + - - ]
489 : : {
490 : 0 : case RTLeftStrategyNumber:
491 : 0 : retval =
492 : 0 : !DatumGetBool(DirectFunctionCall2(seg_over_right, key, query));
493 : 0 : break;
494 : 0 : case RTOverLeftStrategyNumber:
495 : 0 : retval =
496 : 0 : !DatumGetBool(DirectFunctionCall2(seg_right, key, query));
497 : 0 : break;
498 : 0 : case RTOverlapStrategyNumber:
499 : : retval =
500 : 0 : DatumGetBool(DirectFunctionCall2(seg_overlap, key, query));
501 : 0 : break;
502 : 0 : case RTOverRightStrategyNumber:
503 : 0 : retval =
504 : 0 : !DatumGetBool(DirectFunctionCall2(seg_left, key, query));
505 : 0 : break;
506 : 0 : case RTRightStrategyNumber:
507 : 0 : retval =
508 : 0 : !DatumGetBool(DirectFunctionCall2(seg_over_left, key, query));
509 : 0 : break;
510 : 68 : case RTSameStrategyNumber:
511 : : case RTContainsStrategyNumber:
512 : : case RTOldContainsStrategyNumber:
513 : : retval =
514 : 68 : DatumGetBool(DirectFunctionCall2(seg_contains, key, query));
515 : 68 : break;
516 : 0 : case RTContainedByStrategyNumber:
517 : : case RTOldContainedByStrategyNumber:
518 : : retval =
519 : 0 : DatumGetBool(DirectFunctionCall2(seg_overlap, key, query));
520 : 0 : break;
521 : 0 : default:
522 : 0 : retval = false;
523 : : }
524 : :
525 : 68 : PG_RETURN_BOOL(retval);
526 : : }
527 : :
528 : : static Datum
529 : 2316 : gseg_binary_union(Datum r1, Datum r2, int *sizep)
530 : : {
531 : : Datum retval;
532 : :
533 : 2316 : retval = DirectFunctionCall2(seg_union, r1, r2);
534 : 2316 : *sizep = sizeof(SEG);
535 : :
536 : 2316 : return retval;
537 : : }
538 : :
539 : :
540 : : Datum
541 : 5803 : seg_contains(PG_FUNCTION_ARGS)
542 : : {
543 : 5803 : SEG *a = PG_GETARG_SEG_P(0);
544 : 5803 : SEG *b = PG_GETARG_SEG_P(1);
545 : :
546 [ + + + + ]: 5803 : PG_RETURN_BOOL((a->lower <= b->lower) && (a->upper >= b->upper));
547 : : }
548 : :
549 : : Datum
550 : 14 : seg_contained(PG_FUNCTION_ARGS)
551 : : {
552 : 14 : Datum a = PG_GETARG_DATUM(0);
553 : 14 : Datum b = PG_GETARG_DATUM(1);
554 : :
555 : 14 : PG_RETURN_DATUM(DirectFunctionCall2(seg_contains, b, a));
556 : : }
557 : :
558 : : /*****************************************************************************
559 : : * Operator class for R-tree indexing
560 : : *****************************************************************************/
561 : :
562 : : Datum
563 : 2459 : seg_same(PG_FUNCTION_ARGS)
564 : : {
565 : 2459 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
566 : : PG_GETARG_DATUM(0),
567 : : PG_GETARG_DATUM(1)));
568 : :
569 : 2459 : PG_RETURN_BOOL(cmp == 0);
570 : : }
571 : :
572 : : /*
573 : : * seg_overlap -- does a overlap b?
574 : : */
575 : : Datum
576 : 15 : seg_overlap(PG_FUNCTION_ARGS)
577 : : {
578 : 15 : SEG *a = PG_GETARG_SEG_P(0);
579 : 15 : SEG *b = PG_GETARG_SEG_P(1);
580 : :
581 [ + + + + : 15 : PG_RETURN_BOOL(((a->upper >= b->upper) && (a->lower <= b->upper)) ||
+ + + + ]
582 : : ((b->upper >= a->upper) && (b->lower <= a->upper)));
583 : : }
584 : :
585 : : /*
586 : : * seg_over_left -- is the right edge of (a) located at or left of the right edge of (b)?
587 : : */
588 : : Datum
589 : 11 : seg_over_left(PG_FUNCTION_ARGS)
590 : : {
591 : 11 : SEG *a = PG_GETARG_SEG_P(0);
592 : 11 : SEG *b = PG_GETARG_SEG_P(1);
593 : :
594 : 11 : PG_RETURN_BOOL(a->upper <= b->upper);
595 : : }
596 : :
597 : : /*
598 : : * seg_left -- is (a) entirely on the left of (b)?
599 : : */
600 : : Datum
601 : 11 : seg_left(PG_FUNCTION_ARGS)
602 : : {
603 : 11 : SEG *a = PG_GETARG_SEG_P(0);
604 : 11 : SEG *b = PG_GETARG_SEG_P(1);
605 : :
606 : 11 : PG_RETURN_BOOL(a->upper < b->lower);
607 : : }
608 : :
609 : : /*
610 : : * seg_right -- is (a) entirely on the right of (b)?
611 : : */
612 : : Datum
613 : 11 : seg_right(PG_FUNCTION_ARGS)
614 : : {
615 : 11 : SEG *a = PG_GETARG_SEG_P(0);
616 : 11 : SEG *b = PG_GETARG_SEG_P(1);
617 : :
618 : 11 : PG_RETURN_BOOL(a->lower > b->upper);
619 : : }
620 : :
621 : : /*
622 : : * seg_over_right -- is the left edge of (a) located at or right of the left edge of (b)?
623 : : */
624 : : Datum
625 : 11 : seg_over_right(PG_FUNCTION_ARGS)
626 : : {
627 : 11 : SEG *a = PG_GETARG_SEG_P(0);
628 : 11 : SEG *b = PG_GETARG_SEG_P(1);
629 : :
630 : 11 : PG_RETURN_BOOL(a->lower >= b->lower);
631 : : }
632 : :
633 : : Datum
634 : 11698 : seg_union(PG_FUNCTION_ARGS)
635 : : {
636 : 11698 : SEG *a = PG_GETARG_SEG_P(0);
637 : 11698 : SEG *b = PG_GETARG_SEG_P(1);
638 : : SEG *n;
639 : :
640 : 11698 : n = palloc_object(SEG);
641 : :
642 : : /* take max of upper endpoints */
643 [ + + ]: 11698 : if (a->upper > b->upper)
644 : : {
645 : 10272 : n->upper = a->upper;
646 : 10272 : n->u_sigd = a->u_sigd;
647 : 10272 : n->u_ext = a->u_ext;
648 : : }
649 : : else
650 : : {
651 : 1426 : n->upper = b->upper;
652 : 1426 : n->u_sigd = b->u_sigd;
653 : 1426 : n->u_ext = b->u_ext;
654 : : }
655 : :
656 : : /* take min of lower endpoints */
657 [ + + ]: 11698 : if (a->lower < b->lower)
658 : : {
659 : 11404 : n->lower = a->lower;
660 : 11404 : n->l_sigd = a->l_sigd;
661 : 11404 : n->l_ext = a->l_ext;
662 : : }
663 : : else
664 : : {
665 : 294 : n->lower = b->lower;
666 : 294 : n->l_sigd = b->l_sigd;
667 : 294 : n->l_ext = b->l_ext;
668 : : }
669 : :
670 : 11698 : PG_RETURN_POINTER(n);
671 : : }
672 : :
673 : : Datum
674 : 0 : seg_inter(PG_FUNCTION_ARGS)
675 : : {
676 : 0 : SEG *a = PG_GETARG_SEG_P(0);
677 : 0 : SEG *b = PG_GETARG_SEG_P(1);
678 : : SEG *n;
679 : :
680 : 0 : n = palloc_object(SEG);
681 : :
682 : : /* take min of upper endpoints */
683 [ # # ]: 0 : if (a->upper < b->upper)
684 : : {
685 : 0 : n->upper = a->upper;
686 : 0 : n->u_sigd = a->u_sigd;
687 : 0 : n->u_ext = a->u_ext;
688 : : }
689 : : else
690 : : {
691 : 0 : n->upper = b->upper;
692 : 0 : n->u_sigd = b->u_sigd;
693 : 0 : n->u_ext = b->u_ext;
694 : : }
695 : :
696 : : /* take max of lower endpoints */
697 [ # # ]: 0 : if (a->lower > b->lower)
698 : : {
699 : 0 : n->lower = a->lower;
700 : 0 : n->l_sigd = a->l_sigd;
701 : 0 : n->l_ext = a->l_ext;
702 : : }
703 : : else
704 : : {
705 : 0 : n->lower = b->lower;
706 : 0 : n->l_sigd = b->l_sigd;
707 : 0 : n->l_ext = b->l_ext;
708 : : }
709 : :
710 : 0 : PG_RETURN_POINTER(n);
711 : : }
712 : :
713 : : static void
714 : 10444 : rt_seg_size(SEG *a, float *size)
715 : : {
716 [ + - - + ]: 10444 : if (a == (SEG *) NULL || a->upper <= a->lower)
717 : 0 : *size = 0.0;
718 : : else
719 : 10444 : *size = fabsf(a->upper - a->lower);
720 : 10444 : }
721 : :
722 : : Datum
723 : 0 : seg_size(PG_FUNCTION_ARGS)
724 : : {
725 : 0 : SEG *seg = PG_GETARG_SEG_P(0);
726 : :
727 : 0 : PG_RETURN_FLOAT4(fabsf(seg->upper - seg->lower));
728 : : }
729 : :
730 : :
731 : : /*****************************************************************************
732 : : * Miscellaneous operators
733 : : *****************************************************************************/
734 : : Datum
735 : 4433 : seg_cmp(PG_FUNCTION_ARGS)
736 : : {
737 : 4433 : SEG *a = PG_GETARG_SEG_P(0);
738 : 4433 : SEG *b = PG_GETARG_SEG_P(1);
739 : :
740 : : /*
741 : : * First compare on lower boundary position
742 : : */
743 [ + + ]: 4433 : if (a->lower < b->lower)
744 : 904 : PG_RETURN_INT32(-1);
745 [ + + ]: 3529 : if (a->lower > b->lower)
746 : 801 : PG_RETURN_INT32(1);
747 : :
748 : : /*
749 : : * a->lower == b->lower, so consider type of boundary.
750 : : *
751 : : * A '-' lower bound is < any other kind (this could only be relevant if
752 : : * -HUGE_VAL is used as a regular data value). A '<' lower bound is < any
753 : : * other kind except '-'. A '>' lower bound is > any other kind.
754 : : */
755 [ + + ]: 2728 : if (a->l_ext != b->l_ext)
756 : : {
757 [ - + ]: 66 : if (a->l_ext == '-')
758 : 0 : PG_RETURN_INT32(-1);
759 [ - + ]: 66 : if (b->l_ext == '-')
760 : 0 : PG_RETURN_INT32(1);
761 [ + + ]: 66 : if (a->l_ext == '<')
762 : 26 : PG_RETURN_INT32(-1);
763 [ + + ]: 40 : if (b->l_ext == '<')
764 : 21 : PG_RETURN_INT32(1);
765 [ + + ]: 19 : if (a->l_ext == '>')
766 : 13 : PG_RETURN_INT32(1);
767 [ + - ]: 6 : if (b->l_ext == '>')
768 : 6 : PG_RETURN_INT32(-1);
769 : : }
770 : :
771 : : /*
772 : : * For other boundary types, consider # of significant digits first.
773 : : */
774 [ + + ]: 2662 : if (a->l_sigd < b->l_sigd) /* (a) is blurred and is likely to include (b) */
775 : 18 : PG_RETURN_INT32(-1);
776 [ + + ]: 2644 : if (a->l_sigd > b->l_sigd) /* (a) is less blurred and is likely to be
777 : : * included in (b) */
778 : 18 : PG_RETURN_INT32(1);
779 : :
780 : : /*
781 : : * For same # of digits, an approximate boundary is more blurred than
782 : : * exact.
783 : : */
784 [ - + ]: 2626 : if (a->l_ext != b->l_ext)
785 : : {
786 [ # # ]: 0 : if (a->l_ext == '~') /* (a) is approximate, while (b) is exact */
787 : 0 : PG_RETURN_INT32(-1);
788 [ # # ]: 0 : if (b->l_ext == '~')
789 : 0 : PG_RETURN_INT32(1);
790 : : /* can't get here unless data is corrupt */
791 [ # # ]: 0 : elog(ERROR, "bogus lower boundary types %d %d",
792 : : (int) a->l_ext, (int) b->l_ext);
793 : : }
794 : :
795 : : /* at this point, the lower boundaries are identical */
796 : :
797 : : /*
798 : : * First compare on upper boundary position
799 : : */
800 [ + + ]: 2626 : if (a->upper < b->upper)
801 : 162 : PG_RETURN_INT32(-1);
802 [ + + ]: 2464 : if (a->upper > b->upper)
803 : 126 : PG_RETURN_INT32(1);
804 : :
805 : : /*
806 : : * a->upper == b->upper, so consider type of boundary.
807 : : *
808 : : * A '-' upper bound is > any other kind (this could only be relevant if
809 : : * HUGE_VAL is used as a regular data value). A '<' upper bound is < any
810 : : * other kind. A '>' upper bound is > any other kind except '-'.
811 : : */
812 [ + + ]: 2338 : if (a->u_ext != b->u_ext)
813 : : {
814 [ - + ]: 44 : if (a->u_ext == '-')
815 : 0 : PG_RETURN_INT32(1);
816 [ - + ]: 44 : if (b->u_ext == '-')
817 : 0 : PG_RETURN_INT32(-1);
818 [ + + ]: 44 : if (a->u_ext == '<')
819 : 3 : PG_RETURN_INT32(-1);
820 [ + + ]: 41 : if (b->u_ext == '<')
821 : 1 : PG_RETURN_INT32(1);
822 [ + + ]: 40 : if (a->u_ext == '>')
823 : 23 : PG_RETURN_INT32(1);
824 [ + - ]: 17 : if (b->u_ext == '>')
825 : 17 : PG_RETURN_INT32(-1);
826 : : }
827 : :
828 : : /*
829 : : * For other boundary types, consider # of significant digits first. Note
830 : : * result here is converse of the lower-boundary case.
831 : : */
832 [ + + ]: 2294 : if (a->u_sigd < b->u_sigd) /* (a) is blurred and is likely to include (b) */
833 : 6 : PG_RETURN_INT32(1);
834 [ + + ]: 2288 : if (a->u_sigd > b->u_sigd) /* (a) is less blurred and is likely to be
835 : : * included in (b) */
836 : 6 : PG_RETURN_INT32(-1);
837 : :
838 : : /*
839 : : * For same # of digits, an approximate boundary is more blurred than
840 : : * exact. Again, result is converse of lower-boundary case.
841 : : */
842 [ - + ]: 2282 : if (a->u_ext != b->u_ext)
843 : : {
844 [ # # ]: 0 : if (a->u_ext == '~') /* (a) is approximate, while (b) is exact */
845 : 0 : PG_RETURN_INT32(1);
846 [ # # ]: 0 : if (b->u_ext == '~')
847 : 0 : PG_RETURN_INT32(-1);
848 : : /* can't get here unless data is corrupt */
849 [ # # ]: 0 : elog(ERROR, "bogus upper boundary types %d %d",
850 : : (int) a->u_ext, (int) b->u_ext);
851 : : }
852 : :
853 : 2282 : PG_RETURN_INT32(0);
854 : : }
855 : :
856 : : Datum
857 : 0 : seg_lt(PG_FUNCTION_ARGS)
858 : : {
859 : 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
860 : : PG_GETARG_DATUM(0),
861 : : PG_GETARG_DATUM(1)));
862 : :
863 : 0 : PG_RETURN_BOOL(cmp < 0);
864 : : }
865 : :
866 : : Datum
867 : 0 : seg_le(PG_FUNCTION_ARGS)
868 : : {
869 : 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
870 : : PG_GETARG_DATUM(0),
871 : : PG_GETARG_DATUM(1)));
872 : :
873 : 0 : PG_RETURN_BOOL(cmp <= 0);
874 : : }
875 : :
876 : : Datum
877 : 0 : seg_gt(PG_FUNCTION_ARGS)
878 : : {
879 : 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
880 : : PG_GETARG_DATUM(0),
881 : : PG_GETARG_DATUM(1)));
882 : :
883 : 0 : PG_RETURN_BOOL(cmp > 0);
884 : : }
885 : :
886 : : Datum
887 : 0 : seg_ge(PG_FUNCTION_ARGS)
888 : : {
889 : 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
890 : : PG_GETARG_DATUM(0),
891 : : PG_GETARG_DATUM(1)));
892 : :
893 : 0 : PG_RETURN_BOOL(cmp >= 0);
894 : : }
895 : :
896 : :
897 : : Datum
898 : 2 : seg_different(PG_FUNCTION_ARGS)
899 : : {
900 : 2 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
901 : : PG_GETARG_DATUM(0),
902 : : PG_GETARG_DATUM(1)));
903 : :
904 : 2 : PG_RETURN_BOOL(cmp != 0);
905 : : }
906 : :
907 : :
908 : :
909 : : /*****************************************************************************
910 : : * Auxiliary functions
911 : : *****************************************************************************/
912 : :
913 : : /*
914 : : * The purpose of this routine is to print the given floating point
915 : : * value with exactly n significant digits. Its behaviour
916 : : * is similar to %.ng except it prints 8.00 where %.ng would
917 : : * print 8. Returns the length of the string written at "result".
918 : : *
919 : : * Caller must provide a sufficiently large result buffer; 16 bytes
920 : : * should be enough for all known float implementations.
921 : : */
922 : : static int
923 : 339 : restore(char *result, float val, int n)
924 : : {
925 : 339 : char buf[25] = {
926 : : '0', '0', '0', '0', '0',
927 : : '0', '0', '0', '0', '0',
928 : : '0', '0', '0', '0', '0',
929 : : '0', '0', '0', '0', '0',
930 : : '0', '0', '0', '0', '\0'
931 : : };
932 : : char *p;
933 : : int exp;
934 : : int i,
935 : : dp,
936 : : sign;
937 : :
938 : : /*
939 : : * Put a cap on the number of significant digits to avoid garbage in the
940 : : * output and ensure we don't overrun the result buffer. (n should not be
941 : : * negative, but check to protect ourselves against corrupted data.)
942 : : */
943 [ - + ]: 339 : if (n <= 0)
944 : 0 : n = FLT_DIG;
945 : : else
946 : 339 : n = Min(n, FLT_DIG);
947 : :
948 : : /* remember the sign */
949 : 339 : sign = (val < 0 ? 1 : 0);
950 : :
951 : : /* print, in %e style to start with */
952 : 339 : sprintf(result, "%.*e", n - 1, val);
953 : :
954 : : /* find the exponent */
955 : 339 : p = strchr(result, 'e');
956 : :
957 : : /* punt if we have 'inf' or similar */
958 [ - + ]: 339 : if (p == NULL)
959 : 0 : return strlen(result);
960 : :
961 : 339 : exp = atoi(p + 1);
962 [ + + ]: 339 : if (exp == 0)
963 : : {
964 : : /* just truncate off the 'e+00' */
965 : 183 : *p = '\0';
966 : : }
967 : : else
968 : : {
969 [ + + + + ]: 156 : if (abs(exp) <= 4)
970 : : {
971 : : /*
972 : : * remove the decimal point from the mantissa and write the digits
973 : : * to the buf array
974 : : */
975 [ + + ]: 637 : for (p = result + sign, i = 10, dp = 0; *p != 'e'; p++, i++)
976 : : {
977 : 499 : buf[i] = *p;
978 [ + + ]: 499 : if (*p == '.')
979 : : {
980 : 130 : dp = i--; /* skip the decimal point */
981 : : }
982 : : }
983 [ + + ]: 138 : if (dp == 0)
984 : 8 : dp = i--; /* no decimal point was found in the above
985 : : * for() loop */
986 : :
987 [ + + ]: 138 : if (exp > 0)
988 : : {
989 [ + + ]: 133 : if (dp - 10 + exp >= n)
990 : : {
991 : : /*
992 : : * the decimal point is behind the last significant digit;
993 : : * the digits in between must be converted to the exponent
994 : : * and the decimal point placed after the first digit
995 : : */
996 : 43 : exp = dp - 10 + exp - n;
997 : 43 : buf[10 + n] = '\0';
998 : :
999 : : /* insert the decimal point */
1000 [ + + ]: 43 : if (n > 1)
1001 : : {
1002 : 39 : dp = 11;
1003 [ + + ]: 507 : for (i = 23; i > dp; i--)
1004 : 468 : buf[i] = buf[i - 1];
1005 : 39 : buf[dp] = '.';
1006 : : }
1007 : :
1008 : : /*
1009 : : * adjust the exponent by the number of digits after the
1010 : : * decimal point
1011 : : */
1012 [ + + ]: 43 : if (n > 1)
1013 : 39 : sprintf(&buf[11 + n], "e%d", exp + n - 1);
1014 : : else
1015 : 4 : sprintf(&buf[11], "e%d", exp + n - 1);
1016 : :
1017 [ - + ]: 43 : if (sign)
1018 : : {
1019 : 0 : buf[9] = '-';
1020 : 0 : strcpy(result, &buf[9]);
1021 : : }
1022 : : else
1023 : 43 : strcpy(result, &buf[10]);
1024 : : }
1025 : : else
1026 : : { /* insert the decimal point */
1027 : 90 : dp += exp;
1028 [ + + ]: 1080 : for (i = 23; i > dp; i--)
1029 : 990 : buf[i] = buf[i - 1];
1030 : 90 : buf[11 + n] = '\0';
1031 : 90 : buf[dp] = '.';
1032 [ - + ]: 90 : if (sign)
1033 : : {
1034 : 0 : buf[9] = '-';
1035 : 0 : strcpy(result, &buf[9]);
1036 : : }
1037 : : else
1038 : 90 : strcpy(result, &buf[10]);
1039 : : }
1040 : : }
1041 : : else
1042 : : { /* exp <= 0 */
1043 : 5 : dp += exp - 1;
1044 : 5 : buf[10 + n] = '\0';
1045 : 5 : buf[dp] = '.';
1046 [ - + ]: 5 : if (sign)
1047 : : {
1048 : 0 : buf[dp - 2] = '-';
1049 : 0 : strcpy(result, &buf[dp - 2]);
1050 : : }
1051 : : else
1052 : 5 : strcpy(result, &buf[dp - 1]);
1053 : : }
1054 : : }
1055 : :
1056 : : /* do nothing for abs(exp) > 4; %e must be OK */
1057 : : /* just get rid of zeroes after [eE]- and +zeroes after [Ee]. */
1058 : :
1059 : : /* ... this is not done yet. */
1060 : : }
1061 : 339 : return strlen(result);
1062 : : }
1063 : :
1064 : :
1065 : : /*
1066 : : * Miscellany
1067 : : */
1068 : :
1069 : : /*
1070 : : * find out the number of significant digits in a string representing
1071 : : * a floating point number
1072 : : */
1073 : : int
1074 : 5205 : significant_digits(const char *s)
1075 : : {
1076 : 5205 : const char *p = s;
1077 : : int n,
1078 : : c,
1079 : : zeroes;
1080 : :
1081 : 5205 : zeroes = 1;
1082 : : /* skip leading zeroes and sign */
1083 [ + + + - : 5344 : for (c = *p; (c == '0' || c == '+' || c == '-') && c != 0; c = *(++p));
+ + + - ]
1084 : :
1085 : : /* skip decimal point and following zeroes */
1086 [ + + + + : 5226 : for (c = *p; (c == '0' || c == '.') && c != 0; c = *(++p))
+ - ]
1087 : : {
1088 [ + + ]: 21 : if (c != '.')
1089 : 11 : zeroes++;
1090 : : }
1091 : :
1092 : : /* count significant digits (n) */
1093 [ + + ]: 20409 : for (c = *p, n = 0; c != 0; c = *(++p))
1094 : : {
1095 [ + + + + : 15231 : if (!((c >= '0' && c <= '9') || (c == '.')))
+ + ]
1096 : 27 : break;
1097 [ + + ]: 15204 : if (c != '.')
1098 : 10645 : n++;
1099 : : }
1100 : :
1101 [ + + ]: 5205 : if (!n)
1102 : 98 : return zeroes;
1103 : :
1104 : 5107 : return n;
1105 : : }
|
