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