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 2825 : seg_in(PG_FUNCTION_ARGS)
108 : {
109 2825 : char *str = PG_GETARG_CSTRING(0);
110 2825 : SEG *result = palloc_object(SEG);
111 : yyscan_t scanner;
112 :
113 2825 : seg_scanner_init(str, &scanner);
114 :
115 2825 : if (seg_yyparse(result, fcinfo->context, scanner) != 0)
116 8 : seg_yyerror(result, fcinfo->context, scanner, "bogus input");
117 :
118 2816 : seg_scanner_finish(scanner);
119 :
120 2816 : PG_RETURN_POINTER(result);
121 : }
122 :
123 : Datum
124 209 : seg_out(PG_FUNCTION_ARGS)
125 : {
126 209 : SEG *seg = PG_GETARG_SEG_P(0);
127 : char *result;
128 : char *p;
129 :
130 209 : p = result = (char *) palloc(40);
131 :
132 209 : if (seg->l_ext == '>' || seg->l_ext == '<' || seg->l_ext == '~')
133 22 : p += sprintf(p, "%c", seg->l_ext);
134 :
135 209 : 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 162 : if (seg->l_ext != '-')
145 : {
146 : /* print the lower boundary if exists */
147 155 : p += restore(p, seg->lower, seg->l_sigd);
148 155 : p += sprintf(p, " ");
149 : }
150 162 : p += sprintf(p, "..");
151 162 : if (seg->u_ext != '-')
152 : {
153 : /* print the upper boundary if exists */
154 123 : p += sprintf(p, " ");
155 123 : if (seg->u_ext == '>' || seg->u_ext == '<' || seg->l_ext == '~')
156 32 : p += sprintf(p, "%c", seg->u_ext);
157 123 : p += restore(p, seg->upper, seg->u_sigd);
158 : }
159 : }
160 :
161 209 : 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 5816 : gseg_consistent(PG_FUNCTION_ARGS)
201 : {
202 5816 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
203 5816 : Datum query = PG_GETARG_DATUM(1);
204 5816 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
205 : #ifdef NOT_USED
206 : Oid subtype = PG_GETARG_OID(3);
207 : #endif
208 5816 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
209 :
210 : /* All cases served by this function are exact */
211 5816 : *recheck = false;
212 :
213 : /*
214 : * if entry is not leaf, use gseg_internal_consistent, else use
215 : * gseg_leaf_consistent
216 : */
217 5816 : if (GIST_LEAF(entry))
218 5744 : return gseg_leaf_consistent(entry->key, query, strategy);
219 : else
220 72 : 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 4911 : gseg_penalty(PG_FUNCTION_ARGS)
276 : {
277 4911 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
278 4911 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
279 4911 : float *result = (float *) PG_GETARG_POINTER(2);
280 : SEG *ud;
281 : float tmp1,
282 : tmp2;
283 :
284 4911 : ud = DatumGetSegP(DirectFunctionCall2(seg_union,
285 : origentry->key,
286 : newentry->key));
287 4911 : rt_seg_size(ud, &tmp1);
288 4911 : rt_seg_size(DatumGetSegP(origentry->key), &tmp2);
289 4911 : *result = tmp1 - tmp2;
290 :
291 : #ifdef GIST_DEBUG
292 : fprintf(stderr, "penalty\n");
293 : fprintf(stderr, "\t%g\n", *result);
294 : #endif
295 :
296 4911 : PG_RETURN_POINTER(result);
297 : }
298 :
299 : /*
300 : * Compare function for gseg_picksplit_item: sort by center.
301 : */
302 : static int
303 28962 : gseg_picksplit_item_cmp(const void *a, const void *b)
304 : {
305 28962 : const gseg_picksplit_item *i1 = (const gseg_picksplit_item *) a;
306 28962 : const gseg_picksplit_item *i2 = (const gseg_picksplit_item *) b;
307 :
308 28962 : if (i1->center < i2->center)
309 12059 : return -1;
310 16903 : else if (i1->center == i2->center)
311 5106 : return 0;
312 : else
313 11797 : 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 17 : gseg_picksplit(PG_FUNCTION_ARGS)
325 : {
326 17 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
327 17 : 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 17 : maxoff = entryvec->n - 1;
344 :
345 : /*
346 : * Prepare the auxiliary array and sort it.
347 : */
348 : sort_items = (gseg_picksplit_item *)
349 17 : palloc(maxoff * sizeof(gseg_picksplit_item));
350 4471 : for (i = 1; i <= maxoff; i++)
351 : {
352 4454 : seg = DatumGetSegP(entryvec->vector[i].key);
353 : /* center calculation is done this way to avoid possible overflow */
354 4454 : sort_items[i - 1].center = seg->lower * 0.5f + seg->upper * 0.5f;
355 4454 : sort_items[i - 1].index = i;
356 4454 : sort_items[i - 1].data = seg;
357 : }
358 17 : qsort(sort_items, maxoff, sizeof(gseg_picksplit_item),
359 : gseg_picksplit_item_cmp);
360 :
361 : /* sort items below "firstright" will go into the left side */
362 17 : firstright = maxoff / 2;
363 :
364 17 : v->spl_left = (OffsetNumber *) palloc(maxoff * sizeof(OffsetNumber));
365 17 : v->spl_right = (OffsetNumber *) palloc(maxoff * sizeof(OffsetNumber));
366 17 : left = v->spl_left;
367 17 : v->spl_nleft = 0;
368 17 : right = v->spl_right;
369 17 : v->spl_nright = 0;
370 :
371 : /*
372 : * Emit segments to the left output page, and compute its bounding box.
373 : */
374 17 : seg_l = palloc_object(SEG);
375 17 : memcpy(seg_l, sort_items[0].data, sizeof(SEG));
376 17 : *left++ = sort_items[0].index;
377 17 : v->spl_nleft++;
378 2227 : for (i = 1; i < firstright; i++)
379 : {
380 2210 : Datum sortitem = PointerGetDatum(sort_items[i].data);
381 :
382 2210 : seg_l = DatumGetSegP(DirectFunctionCall2(seg_union,
383 : PointerGetDatum(seg_l),
384 : sortitem));
385 2210 : *left++ = sort_items[i].index;
386 2210 : v->spl_nleft++;
387 : }
388 :
389 : /*
390 : * Likewise for the right page.
391 : */
392 17 : seg_r = palloc_object(SEG);
393 17 : memcpy(seg_r, sort_items[firstright].data, sizeof(SEG));
394 17 : *right++ = sort_items[firstright].index;
395 17 : v->spl_nright++;
396 2227 : for (i = firstright + 1; i < maxoff; i++)
397 : {
398 2210 : Datum sortitem = PointerGetDatum(sort_items[i].data);
399 :
400 2210 : seg_r = DatumGetSegP(DirectFunctionCall2(seg_union,
401 : PointerGetDatum(seg_r),
402 : sortitem));
403 2210 : *right++ = sort_items[i].index;
404 2210 : v->spl_nright++;
405 : }
406 :
407 17 : v->spl_ldatum = PointerGetDatum(seg_l);
408 17 : v->spl_rdatum = PointerGetDatum(seg_r);
409 :
410 17 : PG_RETURN_POINTER(v);
411 : }
412 :
413 : /*
414 : ** Equality methods
415 : */
416 : Datum
417 2315 : gseg_same(PG_FUNCTION_ARGS)
418 : {
419 2315 : bool *result = (bool *) PG_GETARG_POINTER(2);
420 :
421 2315 : if (DatumGetBool(DirectFunctionCall2(seg_same, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1))))
422 2277 : *result = true;
423 : else
424 38 : *result = false;
425 :
426 : #ifdef GIST_DEBUG
427 : fprintf(stderr, "same: %s\n", (*result ? "TRUE" : "FALSE"));
428 : #endif
429 :
430 2315 : PG_RETURN_POINTER(result);
431 : }
432 :
433 : /*
434 : ** SUPPORT ROUTINES
435 : */
436 : static Datum
437 5744 : gseg_leaf_consistent(Datum key, Datum query, StrategyNumber strategy)
438 : {
439 : Datum retval;
440 :
441 : #ifdef GIST_QUERY_DEBUG
442 : fprintf(stderr, "leaf_consistent, %d\n", strategy);
443 : #endif
444 :
445 5744 : switch (strategy)
446 : {
447 0 : case RTLeftStrategyNumber:
448 0 : retval = DirectFunctionCall2(seg_left, key, query);
449 0 : break;
450 0 : case RTOverLeftStrategyNumber:
451 0 : retval = DirectFunctionCall2(seg_over_left, key, query);
452 0 : break;
453 0 : case RTOverlapStrategyNumber:
454 0 : retval = DirectFunctionCall2(seg_overlap, key, query);
455 0 : break;
456 0 : case RTOverRightStrategyNumber:
457 0 : retval = DirectFunctionCall2(seg_over_right, key, query);
458 0 : break;
459 0 : case RTRightStrategyNumber:
460 0 : retval = DirectFunctionCall2(seg_right, key, query);
461 0 : break;
462 0 : case RTSameStrategyNumber:
463 0 : retval = DirectFunctionCall2(seg_same, key, query);
464 0 : break;
465 5744 : case RTContainsStrategyNumber:
466 : case RTOldContainsStrategyNumber:
467 5744 : retval = DirectFunctionCall2(seg_contains, key, query);
468 5744 : break;
469 0 : case RTContainedByStrategyNumber:
470 : case RTOldContainedByStrategyNumber:
471 0 : retval = DirectFunctionCall2(seg_contained, key, query);
472 0 : break;
473 0 : default:
474 0 : retval = BoolGetDatum(false);
475 : }
476 :
477 5744 : PG_RETURN_DATUM(retval);
478 : }
479 :
480 : static Datum
481 72 : gseg_internal_consistent(Datum key, Datum query, StrategyNumber strategy)
482 : {
483 : bool retval;
484 :
485 : #ifdef GIST_QUERY_DEBUG
486 : fprintf(stderr, "internal_consistent, %d\n", strategy);
487 : #endif
488 :
489 72 : switch (strategy)
490 : {
491 0 : case RTLeftStrategyNumber:
492 0 : retval =
493 0 : !DatumGetBool(DirectFunctionCall2(seg_over_right, key, query));
494 0 : break;
495 0 : case RTOverLeftStrategyNumber:
496 0 : retval =
497 0 : !DatumGetBool(DirectFunctionCall2(seg_right, key, query));
498 0 : break;
499 0 : case RTOverlapStrategyNumber:
500 : retval =
501 0 : DatumGetBool(DirectFunctionCall2(seg_overlap, key, query));
502 0 : break;
503 0 : case RTOverRightStrategyNumber:
504 0 : retval =
505 0 : !DatumGetBool(DirectFunctionCall2(seg_left, key, query));
506 0 : break;
507 0 : case RTRightStrategyNumber:
508 0 : retval =
509 0 : !DatumGetBool(DirectFunctionCall2(seg_over_left, key, query));
510 0 : break;
511 72 : case RTSameStrategyNumber:
512 : case RTContainsStrategyNumber:
513 : case RTOldContainsStrategyNumber:
514 : retval =
515 72 : DatumGetBool(DirectFunctionCall2(seg_contains, key, query));
516 72 : break;
517 0 : case RTContainedByStrategyNumber:
518 : case RTOldContainedByStrategyNumber:
519 : retval =
520 0 : DatumGetBool(DirectFunctionCall2(seg_overlap, key, query));
521 0 : break;
522 0 : default:
523 0 : retval = false;
524 : }
525 :
526 72 : PG_RETURN_BOOL(retval);
527 : }
528 :
529 : static Datum
530 2316 : gseg_binary_union(Datum r1, Datum r2, int *sizep)
531 : {
532 : Datum retval;
533 :
534 2316 : retval = DirectFunctionCall2(seg_union, r1, r2);
535 2316 : *sizep = sizeof(SEG);
536 :
537 2316 : return retval;
538 : }
539 :
540 :
541 : Datum
542 5831 : seg_contains(PG_FUNCTION_ARGS)
543 : {
544 5831 : SEG *a = PG_GETARG_SEG_P(0);
545 5831 : SEG *b = PG_GETARG_SEG_P(1);
546 :
547 5831 : PG_RETURN_BOOL((a->lower <= b->lower) && (a->upper >= b->upper));
548 : }
549 :
550 : Datum
551 14 : seg_contained(PG_FUNCTION_ARGS)
552 : {
553 14 : Datum a = PG_GETARG_DATUM(0);
554 14 : Datum b = PG_GETARG_DATUM(1);
555 :
556 14 : PG_RETURN_DATUM(DirectFunctionCall2(seg_contains, b, a));
557 : }
558 :
559 : /*****************************************************************************
560 : * Operator class for R-tree indexing
561 : *****************************************************************************/
562 :
563 : Datum
564 2459 : seg_same(PG_FUNCTION_ARGS)
565 : {
566 2459 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
567 : PG_GETARG_DATUM(0),
568 : PG_GETARG_DATUM(1)));
569 :
570 2459 : PG_RETURN_BOOL(cmp == 0);
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 : /* seg_over_left -- is the right edge of (a) located at or left of the right edge of (b)?
586 : */
587 : Datum
588 11 : seg_over_left(PG_FUNCTION_ARGS)
589 : {
590 11 : SEG *a = PG_GETARG_SEG_P(0);
591 11 : SEG *b = PG_GETARG_SEG_P(1);
592 :
593 11 : PG_RETURN_BOOL(a->upper <= b->upper);
594 : }
595 :
596 : /* seg_left -- is (a) entirely on the left of (b)?
597 : */
598 : Datum
599 11 : seg_left(PG_FUNCTION_ARGS)
600 : {
601 11 : SEG *a = PG_GETARG_SEG_P(0);
602 11 : SEG *b = PG_GETARG_SEG_P(1);
603 :
604 11 : PG_RETURN_BOOL(a->upper < b->lower);
605 : }
606 :
607 : /* seg_right -- is (a) entirely on the right of (b)?
608 : */
609 : Datum
610 11 : seg_right(PG_FUNCTION_ARGS)
611 : {
612 11 : SEG *a = PG_GETARG_SEG_P(0);
613 11 : SEG *b = PG_GETARG_SEG_P(1);
614 :
615 11 : PG_RETURN_BOOL(a->lower > b->upper);
616 : }
617 :
618 : /* seg_over_right -- is the left edge of (a) located at or right of the left edge of (b)?
619 : */
620 : Datum
621 11 : seg_over_right(PG_FUNCTION_ARGS)
622 : {
623 11 : SEG *a = PG_GETARG_SEG_P(0);
624 11 : SEG *b = PG_GETARG_SEG_P(1);
625 :
626 11 : PG_RETURN_BOOL(a->lower >= b->lower);
627 : }
628 :
629 : Datum
630 11647 : seg_union(PG_FUNCTION_ARGS)
631 : {
632 11647 : SEG *a = PG_GETARG_SEG_P(0);
633 11647 : SEG *b = PG_GETARG_SEG_P(1);
634 : SEG *n;
635 :
636 11647 : n = palloc_object(SEG);
637 :
638 : /* take max of upper endpoints */
639 11647 : if (a->upper > b->upper)
640 : {
641 10516 : n->upper = a->upper;
642 10516 : n->u_sigd = a->u_sigd;
643 10516 : n->u_ext = a->u_ext;
644 : }
645 : else
646 : {
647 1131 : n->upper = b->upper;
648 1131 : n->u_sigd = b->u_sigd;
649 1131 : n->u_ext = b->u_ext;
650 : }
651 :
652 : /* take min of lower endpoints */
653 11647 : if (a->lower < b->lower)
654 : {
655 11259 : n->lower = a->lower;
656 11259 : n->l_sigd = a->l_sigd;
657 11259 : n->l_ext = a->l_ext;
658 : }
659 : else
660 : {
661 388 : n->lower = b->lower;
662 388 : n->l_sigd = b->l_sigd;
663 388 : n->l_ext = b->l_ext;
664 : }
665 :
666 11647 : PG_RETURN_POINTER(n);
667 : }
668 :
669 : Datum
670 0 : seg_inter(PG_FUNCTION_ARGS)
671 : {
672 0 : SEG *a = PG_GETARG_SEG_P(0);
673 0 : SEG *b = PG_GETARG_SEG_P(1);
674 : SEG *n;
675 :
676 0 : n = palloc_object(SEG);
677 :
678 : /* take min of upper endpoints */
679 0 : if (a->upper < b->upper)
680 : {
681 0 : n->upper = a->upper;
682 0 : n->u_sigd = a->u_sigd;
683 0 : n->u_ext = a->u_ext;
684 : }
685 : else
686 : {
687 0 : n->upper = b->upper;
688 0 : n->u_sigd = b->u_sigd;
689 0 : n->u_ext = b->u_ext;
690 : }
691 :
692 : /* take max of lower endpoints */
693 0 : if (a->lower > b->lower)
694 : {
695 0 : n->lower = a->lower;
696 0 : n->l_sigd = a->l_sigd;
697 0 : n->l_ext = a->l_ext;
698 : }
699 : else
700 : {
701 0 : n->lower = b->lower;
702 0 : n->l_sigd = b->l_sigd;
703 0 : n->l_ext = b->l_ext;
704 : }
705 :
706 0 : PG_RETURN_POINTER(n);
707 : }
708 :
709 : static void
710 9822 : rt_seg_size(SEG *a, float *size)
711 : {
712 9822 : if (a == (SEG *) NULL || a->upper <= a->lower)
713 0 : *size = 0.0;
714 : else
715 9822 : *size = fabsf(a->upper - a->lower);
716 9822 : }
717 :
718 : Datum
719 0 : seg_size(PG_FUNCTION_ARGS)
720 : {
721 0 : SEG *seg = PG_GETARG_SEG_P(0);
722 :
723 0 : PG_RETURN_FLOAT4(fabsf(seg->upper - seg->lower));
724 : }
725 :
726 :
727 : /*****************************************************************************
728 : * Miscellaneous operators
729 : *****************************************************************************/
730 : Datum
731 4433 : seg_cmp(PG_FUNCTION_ARGS)
732 : {
733 4433 : SEG *a = PG_GETARG_SEG_P(0);
734 4433 : SEG *b = PG_GETARG_SEG_P(1);
735 :
736 : /*
737 : * First compare on lower boundary position
738 : */
739 4433 : if (a->lower < b->lower)
740 904 : PG_RETURN_INT32(-1);
741 3529 : if (a->lower > b->lower)
742 800 : PG_RETURN_INT32(1);
743 :
744 : /*
745 : * a->lower == b->lower, so consider type of boundary.
746 : *
747 : * A '-' lower bound is < any other kind (this could only be relevant if
748 : * -HUGE_VAL is used as a regular data value). A '<' lower bound is < any
749 : * other kind except '-'. A '>' lower bound is > any other kind.
750 : */
751 2729 : if (a->l_ext != b->l_ext)
752 : {
753 67 : if (a->l_ext == '-')
754 0 : PG_RETURN_INT32(-1);
755 67 : if (b->l_ext == '-')
756 0 : PG_RETURN_INT32(1);
757 67 : if (a->l_ext == '<')
758 27 : PG_RETURN_INT32(-1);
759 40 : if (b->l_ext == '<')
760 21 : PG_RETURN_INT32(1);
761 19 : if (a->l_ext == '>')
762 13 : PG_RETURN_INT32(1);
763 6 : if (b->l_ext == '>')
764 6 : PG_RETURN_INT32(-1);
765 : }
766 :
767 : /*
768 : * For other boundary types, consider # of significant digits first.
769 : */
770 2662 : if (a->l_sigd < b->l_sigd) /* (a) is blurred and is likely to include (b) */
771 19 : PG_RETURN_INT32(-1);
772 2643 : if (a->l_sigd > b->l_sigd) /* (a) is less blurred and is likely to be
773 : * included in (b) */
774 18 : PG_RETURN_INT32(1);
775 :
776 : /*
777 : * For same # of digits, an approximate boundary is more blurred than
778 : * exact.
779 : */
780 2625 : if (a->l_ext != b->l_ext)
781 : {
782 0 : if (a->l_ext == '~') /* (a) is approximate, while (b) is exact */
783 0 : PG_RETURN_INT32(-1);
784 0 : if (b->l_ext == '~')
785 0 : PG_RETURN_INT32(1);
786 : /* can't get here unless data is corrupt */
787 0 : elog(ERROR, "bogus lower boundary types %d %d",
788 : (int) a->l_ext, (int) b->l_ext);
789 : }
790 :
791 : /* at this point, the lower boundaries are identical */
792 :
793 : /*
794 : * First compare on upper boundary position
795 : */
796 2625 : if (a->upper < b->upper)
797 163 : PG_RETURN_INT32(-1);
798 2462 : if (a->upper > b->upper)
799 126 : PG_RETURN_INT32(1);
800 :
801 : /*
802 : * a->upper == b->upper, so consider type of boundary.
803 : *
804 : * A '-' upper bound is > any other kind (this could only be relevant if
805 : * HUGE_VAL is used as a regular data value). A '<' upper bound is < any
806 : * other kind. A '>' upper bound is > any other kind except '-'.
807 : */
808 2336 : if (a->u_ext != b->u_ext)
809 : {
810 48 : if (a->u_ext == '-')
811 0 : PG_RETURN_INT32(1);
812 48 : if (b->u_ext == '-')
813 0 : PG_RETURN_INT32(-1);
814 48 : if (a->u_ext == '<')
815 3 : PG_RETURN_INT32(-1);
816 45 : if (b->u_ext == '<')
817 1 : PG_RETURN_INT32(1);
818 44 : if (a->u_ext == '>')
819 24 : PG_RETURN_INT32(1);
820 20 : if (b->u_ext == '>')
821 20 : PG_RETURN_INT32(-1);
822 : }
823 :
824 : /*
825 : * For other boundary types, consider # of significant digits first. Note
826 : * result here is converse of the lower-boundary case.
827 : */
828 2288 : if (a->u_sigd < b->u_sigd) /* (a) is blurred and is likely to include (b) */
829 2 : PG_RETURN_INT32(1);
830 2286 : if (a->u_sigd > b->u_sigd) /* (a) is less blurred and is likely to be
831 : * included in (b) */
832 7 : PG_RETURN_INT32(-1);
833 :
834 : /*
835 : * For same # of digits, an approximate boundary is more blurred than
836 : * exact. Again, result is converse of lower-boundary case.
837 : */
838 2279 : if (a->u_ext != b->u_ext)
839 : {
840 0 : if (a->u_ext == '~') /* (a) is approximate, while (b) is exact */
841 0 : PG_RETURN_INT32(1);
842 0 : if (b->u_ext == '~')
843 0 : PG_RETURN_INT32(-1);
844 : /* can't get here unless data is corrupt */
845 0 : elog(ERROR, "bogus upper boundary types %d %d",
846 : (int) a->u_ext, (int) b->u_ext);
847 : }
848 :
849 2279 : PG_RETURN_INT32(0);
850 : }
851 :
852 : Datum
853 0 : seg_lt(PG_FUNCTION_ARGS)
854 : {
855 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
856 : PG_GETARG_DATUM(0),
857 : PG_GETARG_DATUM(1)));
858 :
859 0 : PG_RETURN_BOOL(cmp < 0);
860 : }
861 :
862 : Datum
863 0 : seg_le(PG_FUNCTION_ARGS)
864 : {
865 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
866 : PG_GETARG_DATUM(0),
867 : PG_GETARG_DATUM(1)));
868 :
869 0 : PG_RETURN_BOOL(cmp <= 0);
870 : }
871 :
872 : Datum
873 0 : seg_gt(PG_FUNCTION_ARGS)
874 : {
875 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
876 : PG_GETARG_DATUM(0),
877 : PG_GETARG_DATUM(1)));
878 :
879 0 : PG_RETURN_BOOL(cmp > 0);
880 : }
881 :
882 : Datum
883 0 : seg_ge(PG_FUNCTION_ARGS)
884 : {
885 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
886 : PG_GETARG_DATUM(0),
887 : PG_GETARG_DATUM(1)));
888 :
889 0 : PG_RETURN_BOOL(cmp >= 0);
890 : }
891 :
892 :
893 : Datum
894 2 : seg_different(PG_FUNCTION_ARGS)
895 : {
896 2 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
897 : PG_GETARG_DATUM(0),
898 : PG_GETARG_DATUM(1)));
899 :
900 2 : PG_RETURN_BOOL(cmp != 0);
901 : }
902 :
903 :
904 :
905 : /*****************************************************************************
906 : * Auxiliary functions
907 : *****************************************************************************/
908 :
909 : /*
910 : * The purpose of this routine is to print the given floating point
911 : * value with exactly n significant digits. Its behaviour
912 : * is similar to %.ng except it prints 8.00 where %.ng would
913 : * print 8. Returns the length of the string written at "result".
914 : *
915 : * Caller must provide a sufficiently large result buffer; 16 bytes
916 : * should be enough for all known float implementations.
917 : */
918 : static int
919 325 : restore(char *result, float val, int n)
920 : {
921 325 : char buf[25] = {
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 : '0', '0', '0', '0', '\0'
927 : };
928 : char *p;
929 : int exp;
930 : int i,
931 : dp,
932 : sign;
933 :
934 : /*
935 : * Put a cap on the number of significant digits to avoid garbage in the
936 : * output and ensure we don't overrun the result buffer. (n should not be
937 : * negative, but check to protect ourselves against corrupted data.)
938 : */
939 325 : if (n <= 0)
940 0 : n = FLT_DIG;
941 : else
942 325 : n = Min(n, FLT_DIG);
943 :
944 : /* remember the sign */
945 325 : sign = (val < 0 ? 1 : 0);
946 :
947 : /* print, in %e style to start with */
948 325 : sprintf(result, "%.*e", n - 1, val);
949 :
950 : /* find the exponent */
951 325 : p = strchr(result, 'e');
952 :
953 : /* punt if we have 'inf' or similar */
954 325 : if (p == NULL)
955 0 : return strlen(result);
956 :
957 325 : exp = atoi(p + 1);
958 325 : if (exp == 0)
959 : {
960 : /* just truncate off the 'e+00' */
961 169 : *p = '\0';
962 : }
963 : else
964 : {
965 156 : if (abs(exp) <= 4)
966 : {
967 : /*
968 : * remove the decimal point from the mantissa and write the digits
969 : * to the buf array
970 : */
971 637 : for (p = result + sign, i = 10, dp = 0; *p != 'e'; p++, i++)
972 : {
973 499 : buf[i] = *p;
974 499 : if (*p == '.')
975 : {
976 130 : dp = i--; /* skip the decimal point */
977 : }
978 : }
979 138 : if (dp == 0)
980 8 : dp = i--; /* no decimal point was found in the above
981 : * for() loop */
982 :
983 138 : if (exp > 0)
984 : {
985 133 : if (dp - 10 + exp >= n)
986 : {
987 : /*
988 : * the decimal point is behind the last significant digit;
989 : * the digits in between must be converted to the exponent
990 : * and the decimal point placed after the first digit
991 : */
992 43 : exp = dp - 10 + exp - n;
993 43 : buf[10 + n] = '\0';
994 :
995 : /* insert the decimal point */
996 43 : if (n > 1)
997 : {
998 39 : dp = 11;
999 507 : for (i = 23; i > dp; i--)
1000 468 : buf[i] = buf[i - 1];
1001 39 : buf[dp] = '.';
1002 : }
1003 :
1004 : /*
1005 : * adjust the exponent by the number of digits after the
1006 : * decimal point
1007 : */
1008 43 : if (n > 1)
1009 39 : sprintf(&buf[11 + n], "e%d", exp + n - 1);
1010 : else
1011 4 : sprintf(&buf[11], "e%d", exp + n - 1);
1012 :
1013 43 : if (sign)
1014 : {
1015 0 : buf[9] = '-';
1016 0 : strcpy(result, &buf[9]);
1017 : }
1018 : else
1019 43 : strcpy(result, &buf[10]);
1020 : }
1021 : else
1022 : { /* insert the decimal point */
1023 90 : dp += exp;
1024 1080 : for (i = 23; i > dp; i--)
1025 990 : buf[i] = buf[i - 1];
1026 90 : buf[11 + n] = '\0';
1027 90 : buf[dp] = '.';
1028 90 : if (sign)
1029 : {
1030 0 : buf[9] = '-';
1031 0 : strcpy(result, &buf[9]);
1032 : }
1033 : else
1034 90 : strcpy(result, &buf[10]);
1035 : }
1036 : }
1037 : else
1038 : { /* exp <= 0 */
1039 5 : dp += exp - 1;
1040 5 : buf[10 + n] = '\0';
1041 5 : buf[dp] = '.';
1042 5 : if (sign)
1043 : {
1044 0 : buf[dp - 2] = '-';
1045 0 : strcpy(result, &buf[dp - 2]);
1046 : }
1047 : else
1048 5 : strcpy(result, &buf[dp - 1]);
1049 : }
1050 : }
1051 :
1052 : /* do nothing for abs(exp) > 4; %e must be OK */
1053 : /* just get rid of zeroes after [eE]- and +zeroes after [Ee]. */
1054 :
1055 : /* ... this is not done yet. */
1056 : }
1057 325 : return strlen(result);
1058 : }
1059 :
1060 :
1061 : /*
1062 : ** Miscellany
1063 : */
1064 :
1065 : /* find out the number of significant digits in a string representing
1066 : * a floating point number
1067 : */
1068 : int
1069 5191 : significant_digits(const char *s)
1070 : {
1071 5191 : const char *p = s;
1072 : int n,
1073 : c,
1074 : zeroes;
1075 :
1076 5191 : zeroes = 1;
1077 : /* skip leading zeroes and sign */
1078 5330 : for (c = *p; (c == '0' || c == '+' || c == '-') && c != 0; c = *(++p));
1079 :
1080 : /* skip decimal point and following zeroes */
1081 5212 : for (c = *p; (c == '0' || c == '.') && c != 0; c = *(++p))
1082 : {
1083 21 : if (c != '.')
1084 11 : zeroes++;
1085 : }
1086 :
1087 : /* count significant digits (n) */
1088 20353 : for (c = *p, n = 0; c != 0; c = *(++p))
1089 : {
1090 15189 : if (!((c >= '0' && c <= '9') || (c == '.')))
1091 27 : break;
1092 15162 : if (c != '.')
1093 10617 : n++;
1094 : }
1095 :
1096 5191 : if (!n)
1097 98 : return zeroes;
1098 :
1099 5093 : return n;
1100 : }
|
