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