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 6360 : gseg_consistent(PG_FUNCTION_ARGS)
201 : {
202 6360 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
203 6360 : Datum query = PG_GETARG_DATUM(1);
204 6360 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
205 : #ifdef NOT_USED
206 : Oid subtype = PG_GETARG_OID(3);
207 : #endif
208 6360 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
209 :
210 : /* All cases served by this function are exact */
211 6360 : *recheck = false;
212 :
213 : /*
214 : * if entry is not leaf, use gseg_internal_consistent, else use
215 : * gseg_leaf_consistent
216 : */
217 6360 : if (GIST_LEAF(entry))
218 6288 : 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 4823 : gseg_penalty(PG_FUNCTION_ARGS)
276 : {
277 4823 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
278 4823 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
279 4823 : float *result = (float *) PG_GETARG_POINTER(2);
280 : SEG *ud;
281 : float tmp1,
282 : tmp2;
283 :
284 4823 : ud = DatumGetSegP(DirectFunctionCall2(seg_union,
285 : origentry->key,
286 : newentry->key));
287 4823 : rt_seg_size(ud, &tmp1);
288 4823 : rt_seg_size(DatumGetSegP(origentry->key), &tmp2);
289 4823 : *result = tmp1 - tmp2;
290 :
291 : #ifdef GIST_DEBUG
292 : fprintf(stderr, "penalty\n");
293 : fprintf(stderr, "\t%g\n", *result);
294 : #endif
295 :
296 4823 : PG_RETURN_POINTER(result);
297 : }
298 :
299 : /*
300 : * Compare function for gseg_picksplit_item: sort by center.
301 : */
302 : static int
303 29251 : gseg_picksplit_item_cmp(const void *a, const void *b)
304 : {
305 29251 : const gseg_picksplit_item *i1 = (const gseg_picksplit_item *) a;
306 29251 : const gseg_picksplit_item *i2 = (const gseg_picksplit_item *) b;
307 :
308 29251 : if (i1->center < i2->center)
309 12165 : return -1;
310 17086 : else if (i1->center == i2->center)
311 5244 : return 0;
312 : else
313 11842 : 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 2281 : *result = true;
423 : else
424 34 : *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 6288 : 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 6288 : 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 6288 : case RTContainsStrategyNumber:
466 : case RTOldContainsStrategyNumber:
467 6288 : retval = DirectFunctionCall2(seg_contains, key, query);
468 6288 : 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 6288 : 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 6375 : seg_contains(PG_FUNCTION_ARGS)
543 : {
544 6375 : SEG *a = PG_GETARG_SEG_P(0);
545 6375 : SEG *b = PG_GETARG_SEG_P(1);
546 :
547 6375 : 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 : /*
574 : * seg_overlap -- does a overlap b?
575 : */
576 : Datum
577 15 : seg_overlap(PG_FUNCTION_ARGS)
578 : {
579 15 : SEG *a = PG_GETARG_SEG_P(0);
580 15 : SEG *b = PG_GETARG_SEG_P(1);
581 :
582 15 : PG_RETURN_BOOL(((a->upper >= b->upper) && (a->lower <= b->upper)) ||
583 : ((b->upper >= a->upper) && (b->lower <= a->upper)));
584 : }
585 :
586 : /*
587 : * seg_over_left -- is the right edge of (a) located at or left of the right edge of (b)?
588 : */
589 : Datum
590 11 : seg_over_left(PG_FUNCTION_ARGS)
591 : {
592 11 : SEG *a = PG_GETARG_SEG_P(0);
593 11 : SEG *b = PG_GETARG_SEG_P(1);
594 :
595 11 : PG_RETURN_BOOL(a->upper <= b->upper);
596 : }
597 :
598 : /*
599 : * seg_left -- is (a) entirely on the left of (b)?
600 : */
601 : Datum
602 11 : seg_left(PG_FUNCTION_ARGS)
603 : {
604 11 : SEG *a = PG_GETARG_SEG_P(0);
605 11 : SEG *b = PG_GETARG_SEG_P(1);
606 :
607 11 : PG_RETURN_BOOL(a->upper < b->lower);
608 : }
609 :
610 : /*
611 : * seg_right -- is (a) entirely on the right of (b)?
612 : */
613 : Datum
614 11 : seg_right(PG_FUNCTION_ARGS)
615 : {
616 11 : SEG *a = PG_GETARG_SEG_P(0);
617 11 : SEG *b = PG_GETARG_SEG_P(1);
618 :
619 11 : PG_RETURN_BOOL(a->lower > b->upper);
620 : }
621 :
622 : /*
623 : * seg_over_right -- is the left edge of (a) located at or right of the left edge of (b)?
624 : */
625 : Datum
626 11 : seg_over_right(PG_FUNCTION_ARGS)
627 : {
628 11 : SEG *a = PG_GETARG_SEG_P(0);
629 11 : SEG *b = PG_GETARG_SEG_P(1);
630 :
631 11 : PG_RETURN_BOOL(a->lower >= b->lower);
632 : }
633 :
634 : Datum
635 11559 : seg_union(PG_FUNCTION_ARGS)
636 : {
637 11559 : SEG *a = PG_GETARG_SEG_P(0);
638 11559 : SEG *b = PG_GETARG_SEG_P(1);
639 : SEG *n;
640 :
641 11559 : n = palloc_object(SEG);
642 :
643 : /* take max of upper endpoints */
644 11559 : if (a->upper > b->upper)
645 : {
646 10480 : n->upper = a->upper;
647 10480 : n->u_sigd = a->u_sigd;
648 10480 : n->u_ext = a->u_ext;
649 : }
650 : else
651 : {
652 1079 : n->upper = b->upper;
653 1079 : n->u_sigd = b->u_sigd;
654 1079 : n->u_ext = b->u_ext;
655 : }
656 :
657 : /* take min of lower endpoints */
658 11559 : if (a->lower < b->lower)
659 : {
660 11212 : n->lower = a->lower;
661 11212 : n->l_sigd = a->l_sigd;
662 11212 : n->l_ext = a->l_ext;
663 : }
664 : else
665 : {
666 347 : n->lower = b->lower;
667 347 : n->l_sigd = b->l_sigd;
668 347 : n->l_ext = b->l_ext;
669 : }
670 :
671 11559 : PG_RETURN_POINTER(n);
672 : }
673 :
674 : Datum
675 0 : seg_inter(PG_FUNCTION_ARGS)
676 : {
677 0 : SEG *a = PG_GETARG_SEG_P(0);
678 0 : SEG *b = PG_GETARG_SEG_P(1);
679 : SEG *n;
680 :
681 0 : n = palloc_object(SEG);
682 :
683 : /* take min of upper endpoints */
684 0 : if (a->upper < b->upper)
685 : {
686 0 : n->upper = a->upper;
687 0 : n->u_sigd = a->u_sigd;
688 0 : n->u_ext = a->u_ext;
689 : }
690 : else
691 : {
692 0 : n->upper = b->upper;
693 0 : n->u_sigd = b->u_sigd;
694 0 : n->u_ext = b->u_ext;
695 : }
696 :
697 : /* take max of lower endpoints */
698 0 : if (a->lower > b->lower)
699 : {
700 0 : n->lower = a->lower;
701 0 : n->l_sigd = a->l_sigd;
702 0 : n->l_ext = a->l_ext;
703 : }
704 : else
705 : {
706 0 : n->lower = b->lower;
707 0 : n->l_sigd = b->l_sigd;
708 0 : n->l_ext = b->l_ext;
709 : }
710 :
711 0 : PG_RETURN_POINTER(n);
712 : }
713 :
714 : static void
715 9646 : rt_seg_size(SEG *a, float *size)
716 : {
717 9646 : if (a == (SEG *) NULL || a->upper <= a->lower)
718 0 : *size = 0.0;
719 : else
720 9646 : *size = fabsf(a->upper - a->lower);
721 9646 : }
722 :
723 : Datum
724 0 : seg_size(PG_FUNCTION_ARGS)
725 : {
726 0 : SEG *seg = PG_GETARG_SEG_P(0);
727 :
728 0 : PG_RETURN_FLOAT4(fabsf(seg->upper - seg->lower));
729 : }
730 :
731 :
732 : /*****************************************************************************
733 : * Miscellaneous operators
734 : *****************************************************************************/
735 : Datum
736 4433 : seg_cmp(PG_FUNCTION_ARGS)
737 : {
738 4433 : SEG *a = PG_GETARG_SEG_P(0);
739 4433 : SEG *b = PG_GETARG_SEG_P(1);
740 :
741 : /*
742 : * First compare on lower boundary position
743 : */
744 4433 : if (a->lower < b->lower)
745 904 : PG_RETURN_INT32(-1);
746 3529 : if (a->lower > b->lower)
747 800 : PG_RETURN_INT32(1);
748 :
749 : /*
750 : * a->lower == b->lower, so consider type of boundary.
751 : *
752 : * A '-' lower bound is < any other kind (this could only be relevant if
753 : * -HUGE_VAL is used as a regular data value). A '<' lower bound is < any
754 : * other kind except '-'. A '>' lower bound is > any other kind.
755 : */
756 2729 : if (a->l_ext != b->l_ext)
757 : {
758 66 : if (a->l_ext == '-')
759 0 : PG_RETURN_INT32(-1);
760 66 : if (b->l_ext == '-')
761 0 : PG_RETURN_INT32(1);
762 66 : if (a->l_ext == '<')
763 26 : PG_RETURN_INT32(-1);
764 40 : if (b->l_ext == '<')
765 21 : PG_RETURN_INT32(1);
766 19 : if (a->l_ext == '>')
767 13 : PG_RETURN_INT32(1);
768 6 : if (b->l_ext == '>')
769 6 : PG_RETURN_INT32(-1);
770 : }
771 :
772 : /*
773 : * For other boundary types, consider # of significant digits first.
774 : */
775 2663 : if (a->l_sigd < b->l_sigd) /* (a) is blurred and is likely to include (b) */
776 18 : PG_RETURN_INT32(-1);
777 2645 : if (a->l_sigd > b->l_sigd) /* (a) is less blurred and is likely to be
778 : * included in (b) */
779 18 : PG_RETURN_INT32(1);
780 :
781 : /*
782 : * For same # of digits, an approximate boundary is more blurred than
783 : * exact.
784 : */
785 2627 : if (a->l_ext != b->l_ext)
786 : {
787 0 : if (a->l_ext == '~') /* (a) is approximate, while (b) is exact */
788 0 : PG_RETURN_INT32(-1);
789 0 : if (b->l_ext == '~')
790 0 : PG_RETURN_INT32(1);
791 : /* can't get here unless data is corrupt */
792 0 : elog(ERROR, "bogus lower boundary types %d %d",
793 : (int) a->l_ext, (int) b->l_ext);
794 : }
795 :
796 : /* at this point, the lower boundaries are identical */
797 :
798 : /*
799 : * First compare on upper boundary position
800 : */
801 2627 : if (a->upper < b->upper)
802 162 : PG_RETURN_INT32(-1);
803 2465 : if (a->upper > b->upper)
804 126 : PG_RETURN_INT32(1);
805 :
806 : /*
807 : * a->upper == b->upper, so consider type of boundary.
808 : *
809 : * A '-' upper bound is > any other kind (this could only be relevant if
810 : * HUGE_VAL is used as a regular data value). A '<' upper bound is < any
811 : * other kind. A '>' upper bound is > any other kind except '-'.
812 : */
813 2339 : if (a->u_ext != b->u_ext)
814 : {
815 42 : if (a->u_ext == '-')
816 0 : PG_RETURN_INT32(1);
817 42 : if (b->u_ext == '-')
818 0 : PG_RETURN_INT32(-1);
819 42 : if (a->u_ext == '<')
820 3 : PG_RETURN_INT32(-1);
821 39 : if (b->u_ext == '<')
822 1 : PG_RETURN_INT32(1);
823 38 : if (a->u_ext == '>')
824 21 : PG_RETURN_INT32(1);
825 17 : if (b->u_ext == '>')
826 17 : PG_RETURN_INT32(-1);
827 : }
828 :
829 : /*
830 : * For other boundary types, consider # of significant digits first. Note
831 : * result here is converse of the lower-boundary case.
832 : */
833 2297 : if (a->u_sigd < b->u_sigd) /* (a) is blurred and is likely to include (b) */
834 8 : PG_RETURN_INT32(1);
835 2289 : if (a->u_sigd > b->u_sigd) /* (a) is less blurred and is likely to be
836 : * included in (b) */
837 6 : PG_RETURN_INT32(-1);
838 :
839 : /*
840 : * For same # of digits, an approximate boundary is more blurred than
841 : * exact. Again, result is converse of lower-boundary case.
842 : */
843 2283 : if (a->u_ext != b->u_ext)
844 : {
845 0 : if (a->u_ext == '~') /* (a) is approximate, while (b) is exact */
846 0 : PG_RETURN_INT32(1);
847 0 : if (b->u_ext == '~')
848 0 : PG_RETURN_INT32(-1);
849 : /* can't get here unless data is corrupt */
850 0 : elog(ERROR, "bogus upper boundary types %d %d",
851 : (int) a->u_ext, (int) b->u_ext);
852 : }
853 :
854 2283 : PG_RETURN_INT32(0);
855 : }
856 :
857 : Datum
858 0 : seg_lt(PG_FUNCTION_ARGS)
859 : {
860 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
861 : PG_GETARG_DATUM(0),
862 : PG_GETARG_DATUM(1)));
863 :
864 0 : PG_RETURN_BOOL(cmp < 0);
865 : }
866 :
867 : Datum
868 0 : seg_le(PG_FUNCTION_ARGS)
869 : {
870 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
871 : PG_GETARG_DATUM(0),
872 : PG_GETARG_DATUM(1)));
873 :
874 0 : PG_RETURN_BOOL(cmp <= 0);
875 : }
876 :
877 : Datum
878 0 : seg_gt(PG_FUNCTION_ARGS)
879 : {
880 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
881 : PG_GETARG_DATUM(0),
882 : PG_GETARG_DATUM(1)));
883 :
884 0 : PG_RETURN_BOOL(cmp > 0);
885 : }
886 :
887 : Datum
888 0 : seg_ge(PG_FUNCTION_ARGS)
889 : {
890 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
891 : PG_GETARG_DATUM(0),
892 : PG_GETARG_DATUM(1)));
893 :
894 0 : PG_RETURN_BOOL(cmp >= 0);
895 : }
896 :
897 :
898 : Datum
899 2 : seg_different(PG_FUNCTION_ARGS)
900 : {
901 2 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
902 : PG_GETARG_DATUM(0),
903 : PG_GETARG_DATUM(1)));
904 :
905 2 : PG_RETURN_BOOL(cmp != 0);
906 : }
907 :
908 :
909 :
910 : /*****************************************************************************
911 : * Auxiliary functions
912 : *****************************************************************************/
913 :
914 : /*
915 : * The purpose of this routine is to print the given floating point
916 : * value with exactly n significant digits. Its behaviour
917 : * is similar to %.ng except it prints 8.00 where %.ng would
918 : * print 8. Returns the length of the string written at "result".
919 : *
920 : * Caller must provide a sufficiently large result buffer; 16 bytes
921 : * should be enough for all known float implementations.
922 : */
923 : static int
924 325 : restore(char *result, float val, int n)
925 : {
926 325 : char buf[25] = {
927 : '0', '0', '0', '0', '0',
928 : '0', '0', '0', '0', '0',
929 : '0', '0', '0', '0', '0',
930 : '0', '0', '0', '0', '0',
931 : '0', '0', '0', '0', '\0'
932 : };
933 : char *p;
934 : int exp;
935 : int i,
936 : dp,
937 : sign;
938 :
939 : /*
940 : * Put a cap on the number of significant digits to avoid garbage in the
941 : * output and ensure we don't overrun the result buffer. (n should not be
942 : * negative, but check to protect ourselves against corrupted data.)
943 : */
944 325 : if (n <= 0)
945 0 : n = FLT_DIG;
946 : else
947 325 : n = Min(n, FLT_DIG);
948 :
949 : /* remember the sign */
950 325 : sign = (val < 0 ? 1 : 0);
951 :
952 : /* print, in %e style to start with */
953 325 : sprintf(result, "%.*e", n - 1, val);
954 :
955 : /* find the exponent */
956 325 : p = strchr(result, 'e');
957 :
958 : /* punt if we have 'inf' or similar */
959 325 : if (p == NULL)
960 0 : return strlen(result);
961 :
962 325 : exp = atoi(p + 1);
963 325 : if (exp == 0)
964 : {
965 : /* just truncate off the 'e+00' */
966 169 : *p = '\0';
967 : }
968 : else
969 : {
970 156 : if (abs(exp) <= 4)
971 : {
972 : /*
973 : * remove the decimal point from the mantissa and write the digits
974 : * to the buf array
975 : */
976 637 : for (p = result + sign, i = 10, dp = 0; *p != 'e'; p++, i++)
977 : {
978 499 : buf[i] = *p;
979 499 : if (*p == '.')
980 : {
981 130 : dp = i--; /* skip the decimal point */
982 : }
983 : }
984 138 : if (dp == 0)
985 8 : dp = i--; /* no decimal point was found in the above
986 : * for() loop */
987 :
988 138 : if (exp > 0)
989 : {
990 133 : if (dp - 10 + exp >= n)
991 : {
992 : /*
993 : * the decimal point is behind the last significant digit;
994 : * the digits in between must be converted to the exponent
995 : * and the decimal point placed after the first digit
996 : */
997 43 : exp = dp - 10 + exp - n;
998 43 : buf[10 + n] = '\0';
999 :
1000 : /* insert the decimal point */
1001 43 : if (n > 1)
1002 : {
1003 39 : dp = 11;
1004 507 : for (i = 23; i > dp; i--)
1005 468 : buf[i] = buf[i - 1];
1006 39 : buf[dp] = '.';
1007 : }
1008 :
1009 : /*
1010 : * adjust the exponent by the number of digits after the
1011 : * decimal point
1012 : */
1013 43 : if (n > 1)
1014 39 : sprintf(&buf[11 + n], "e%d", exp + n - 1);
1015 : else
1016 4 : sprintf(&buf[11], "e%d", exp + n - 1);
1017 :
1018 43 : if (sign)
1019 : {
1020 0 : buf[9] = '-';
1021 0 : strcpy(result, &buf[9]);
1022 : }
1023 : else
1024 43 : strcpy(result, &buf[10]);
1025 : }
1026 : else
1027 : { /* insert the decimal point */
1028 90 : dp += exp;
1029 1080 : for (i = 23; i > dp; i--)
1030 990 : buf[i] = buf[i - 1];
1031 90 : buf[11 + n] = '\0';
1032 90 : buf[dp] = '.';
1033 90 : if (sign)
1034 : {
1035 0 : buf[9] = '-';
1036 0 : strcpy(result, &buf[9]);
1037 : }
1038 : else
1039 90 : strcpy(result, &buf[10]);
1040 : }
1041 : }
1042 : else
1043 : { /* exp <= 0 */
1044 5 : dp += exp - 1;
1045 5 : buf[10 + n] = '\0';
1046 5 : buf[dp] = '.';
1047 5 : if (sign)
1048 : {
1049 0 : buf[dp - 2] = '-';
1050 0 : strcpy(result, &buf[dp - 2]);
1051 : }
1052 : else
1053 5 : strcpy(result, &buf[dp - 1]);
1054 : }
1055 : }
1056 :
1057 : /* do nothing for abs(exp) > 4; %e must be OK */
1058 : /* just get rid of zeroes after [eE]- and +zeroes after [Ee]. */
1059 :
1060 : /* ... this is not done yet. */
1061 : }
1062 325 : return strlen(result);
1063 : }
1064 :
1065 :
1066 : /*
1067 : * Miscellany
1068 : */
1069 :
1070 : /*
1071 : * find out the number of significant digits in a string representing
1072 : * a floating point number
1073 : */
1074 : int
1075 5191 : significant_digits(const char *s)
1076 : {
1077 5191 : const char *p = s;
1078 : int n,
1079 : c,
1080 : zeroes;
1081 :
1082 5191 : zeroes = 1;
1083 : /* skip leading zeroes and sign */
1084 5330 : for (c = *p; (c == '0' || c == '+' || c == '-') && c != 0; c = *(++p));
1085 :
1086 : /* skip decimal point and following zeroes */
1087 5212 : for (c = *p; (c == '0' || c == '.') && c != 0; c = *(++p))
1088 : {
1089 21 : if (c != '.')
1090 11 : zeroes++;
1091 : }
1092 :
1093 : /* count significant digits (n) */
1094 20353 : for (c = *p, n = 0; c != 0; c = *(++p))
1095 : {
1096 15189 : if (!((c >= '0' && c <= '9') || (c == '.')))
1097 27 : break;
1098 15162 : if (c != '.')
1099 10617 : n++;
1100 : }
1101 :
1102 5191 : if (!n)
1103 98 : return zeroes;
1104 :
1105 5093 : return n;
1106 : }
|
