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_object(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 9384 : gseg_consistent(PG_FUNCTION_ARGS)
201 : {
202 9384 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
203 9384 : Datum query = PG_GETARG_DATUM(1);
204 9384 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
205 : #ifdef NOT_USED
206 : Oid subtype = PG_GETARG_OID(3);
207 : #endif
208 9384 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
209 :
210 : /* All cases served by this function are exact */
211 9384 : *recheck = false;
212 :
213 : /*
214 : * if entry is not leaf, use gseg_internal_consistent, else use
215 : * gseg_leaf_consistent
216 : */
217 9384 : if (GIST_LEAF(entry))
218 9248 : return gseg_leaf_consistent(entry->key, query, strategy);
219 : else
220 136 : 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 4632 : gseg_union(PG_FUNCTION_ARGS)
229 : {
230 4632 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
231 4632 : int *sizep = (int *) PG_GETARG_POINTER(1);
232 : int numranges,
233 : i;
234 4632 : Datum out = 0;
235 : Datum tmp;
236 :
237 : #ifdef GIST_DEBUG
238 : fprintf(stderr, "union\n");
239 : #endif
240 :
241 4632 : numranges = entryvec->n;
242 4632 : tmp = entryvec->vector[0].key;
243 4632 : *sizep = sizeof(SEG);
244 :
245 9264 : for (i = 1; i < numranges; i++)
246 : {
247 4632 : out = gseg_binary_union(tmp, entryvec->vector[i].key, sizep);
248 4632 : tmp = out;
249 : }
250 :
251 4632 : 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 10680 : gseg_penalty(PG_FUNCTION_ARGS)
276 : {
277 10680 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
278 10680 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
279 10680 : float *result = (float *) PG_GETARG_POINTER(2);
280 : SEG *ud;
281 : float tmp1,
282 : tmp2;
283 :
284 10680 : ud = DatumGetSegP(DirectFunctionCall2(seg_union,
285 : origentry->key,
286 : newentry->key));
287 10680 : rt_seg_size(ud, &tmp1);
288 10680 : rt_seg_size(DatumGetSegP(origentry->key), &tmp2);
289 10680 : *result = tmp1 - tmp2;
290 :
291 : #ifdef GIST_DEBUG
292 : fprintf(stderr, "penalty\n");
293 : fprintf(stderr, "\t%g\n", *result);
294 : #endif
295 :
296 10680 : PG_RETURN_POINTER(result);
297 : }
298 :
299 : /*
300 : * Compare function for gseg_picksplit_item: sort by center.
301 : */
302 : static int
303 55686 : gseg_picksplit_item_cmp(const void *a, const void *b)
304 : {
305 55686 : const gseg_picksplit_item *i1 = (const gseg_picksplit_item *) a;
306 55686 : const gseg_picksplit_item *i2 = (const gseg_picksplit_item *) b;
307 :
308 55686 : if (i1->center < i2->center)
309 22450 : return -1;
310 33236 : else if (i1->center == i2->center)
311 10086 : return 0;
312 : else
313 23150 : 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 32 : gseg_picksplit(PG_FUNCTION_ARGS)
325 : {
326 32 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
327 32 : 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 32 : maxoff = entryvec->n - 1;
344 :
345 : /*
346 : * Prepare the auxiliary array and sort it.
347 : */
348 : sort_items = (gseg_picksplit_item *)
349 32 : palloc(maxoff * sizeof(gseg_picksplit_item));
350 8416 : for (i = 1; i <= maxoff; i++)
351 : {
352 8384 : seg = DatumGetSegP(entryvec->vector[i].key);
353 : /* center calculation is done this way to avoid possible overflow */
354 8384 : sort_items[i - 1].center = seg->lower * 0.5f + seg->upper * 0.5f;
355 8384 : sort_items[i - 1].index = i;
356 8384 : sort_items[i - 1].data = seg;
357 : }
358 32 : 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 32 : firstright = maxoff / 2;
363 :
364 32 : v->spl_left = (OffsetNumber *) palloc(maxoff * sizeof(OffsetNumber));
365 32 : v->spl_right = (OffsetNumber *) palloc(maxoff * sizeof(OffsetNumber));
366 32 : left = v->spl_left;
367 32 : v->spl_nleft = 0;
368 32 : right = v->spl_right;
369 32 : v->spl_nright = 0;
370 :
371 : /*
372 : * Emit segments to the left output page, and compute its bounding box.
373 : */
374 32 : seg_l = palloc_object(SEG);
375 32 : memcpy(seg_l, sort_items[0].data, sizeof(SEG));
376 32 : *left++ = sort_items[0].index;
377 32 : v->spl_nleft++;
378 4192 : for (i = 1; i < firstright; i++)
379 : {
380 4160 : Datum sortitem = PointerGetDatum(sort_items[i].data);
381 :
382 4160 : seg_l = DatumGetSegP(DirectFunctionCall2(seg_union,
383 : PointerGetDatum(seg_l),
384 : sortitem));
385 4160 : *left++ = sort_items[i].index;
386 4160 : v->spl_nleft++;
387 : }
388 :
389 : /*
390 : * Likewise for the right page.
391 : */
392 32 : seg_r = palloc_object(SEG);
393 32 : memcpy(seg_r, sort_items[firstright].data, sizeof(SEG));
394 32 : *right++ = sort_items[firstright].index;
395 32 : v->spl_nright++;
396 4192 : for (i = firstright + 1; i < maxoff; i++)
397 : {
398 4160 : Datum sortitem = PointerGetDatum(sort_items[i].data);
399 :
400 4160 : seg_r = DatumGetSegP(DirectFunctionCall2(seg_union,
401 : PointerGetDatum(seg_r),
402 : sortitem));
403 4160 : *right++ = sort_items[i].index;
404 4160 : v->spl_nright++;
405 : }
406 :
407 32 : v->spl_ldatum = PointerGetDatum(seg_l);
408 32 : v->spl_rdatum = PointerGetDatum(seg_r);
409 :
410 32 : PG_RETURN_POINTER(v);
411 : }
412 :
413 : /*
414 : ** Equality methods
415 : */
416 : Datum
417 4630 : gseg_same(PG_FUNCTION_ARGS)
418 : {
419 4630 : bool *result = (bool *) PG_GETARG_POINTER(2);
420 :
421 4630 : if (DatumGetBool(DirectFunctionCall2(seg_same, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1))))
422 4520 : *result = true;
423 : else
424 110 : *result = false;
425 :
426 : #ifdef GIST_DEBUG
427 : fprintf(stderr, "same: %s\n", (*result ? "TRUE" : "FALSE"));
428 : #endif
429 :
430 4630 : PG_RETURN_POINTER(result);
431 : }
432 :
433 : /*
434 : ** SUPPORT ROUTINES
435 : */
436 : static Datum
437 9248 : 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 9248 : 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 9248 : case RTContainsStrategyNumber:
466 : case RTOldContainsStrategyNumber:
467 9248 : retval = DirectFunctionCall2(seg_contains, key, query);
468 9248 : 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 9248 : PG_RETURN_DATUM(retval);
478 : }
479 :
480 : static Datum
481 136 : 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 136 : 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 136 : case RTSameStrategyNumber:
512 : case RTContainsStrategyNumber:
513 : case RTOldContainsStrategyNumber:
514 : retval =
515 136 : DatumGetBool(DirectFunctionCall2(seg_contains, key, query));
516 136 : 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 136 : PG_RETURN_BOOL(retval);
527 : }
528 :
529 : static Datum
530 4632 : gseg_binary_union(Datum r1, Datum r2, int *sizep)
531 : {
532 : Datum retval;
533 :
534 4632 : retval = DirectFunctionCall2(seg_union, r1, r2);
535 4632 : *sizep = sizeof(SEG);
536 :
537 4632 : return retval;
538 : }
539 :
540 :
541 : Datum
542 9414 : seg_contains(PG_FUNCTION_ARGS)
543 : {
544 9414 : SEG *a = PG_GETARG_SEG_P(0);
545 9414 : SEG *b = PG_GETARG_SEG_P(1);
546 :
547 9414 : PG_RETURN_BOOL((a->lower <= b->lower) && (a->upper >= b->upper));
548 : }
549 :
550 : Datum
551 28 : seg_contained(PG_FUNCTION_ARGS)
552 : {
553 28 : Datum a = PG_GETARG_DATUM(0);
554 28 : Datum b = PG_GETARG_DATUM(1);
555 :
556 28 : PG_RETURN_DATUM(DirectFunctionCall2(seg_contains, b, a));
557 : }
558 :
559 : /*****************************************************************************
560 : * Operator class for R-tree indexing
561 : *****************************************************************************/
562 :
563 : Datum
564 4918 : seg_same(PG_FUNCTION_ARGS)
565 : {
566 4918 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
567 : PG_GETARG_DATUM(0),
568 : PG_GETARG_DATUM(1)));
569 :
570 4918 : PG_RETURN_BOOL(cmp == 0);
571 : }
572 :
573 : /* seg_overlap -- does a overlap b?
574 : */
575 : Datum
576 30 : seg_overlap(PG_FUNCTION_ARGS)
577 : {
578 30 : SEG *a = PG_GETARG_SEG_P(0);
579 30 : SEG *b = PG_GETARG_SEG_P(1);
580 :
581 30 : 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 22 : seg_over_left(PG_FUNCTION_ARGS)
589 : {
590 22 : SEG *a = PG_GETARG_SEG_P(0);
591 22 : SEG *b = PG_GETARG_SEG_P(1);
592 :
593 22 : PG_RETURN_BOOL(a->upper <= b->upper);
594 : }
595 :
596 : /* seg_left -- is (a) entirely on the left of (b)?
597 : */
598 : Datum
599 22 : seg_left(PG_FUNCTION_ARGS)
600 : {
601 22 : SEG *a = PG_GETARG_SEG_P(0);
602 22 : SEG *b = PG_GETARG_SEG_P(1);
603 :
604 22 : PG_RETURN_BOOL(a->upper < b->lower);
605 : }
606 :
607 : /* seg_right -- is (a) entirely on the right of (b)?
608 : */
609 : Datum
610 22 : seg_right(PG_FUNCTION_ARGS)
611 : {
612 22 : SEG *a = PG_GETARG_SEG_P(0);
613 22 : SEG *b = PG_GETARG_SEG_P(1);
614 :
615 22 : 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 22 : seg_over_right(PG_FUNCTION_ARGS)
622 : {
623 22 : SEG *a = PG_GETARG_SEG_P(0);
624 22 : SEG *b = PG_GETARG_SEG_P(1);
625 :
626 22 : PG_RETURN_BOOL(a->lower >= b->lower);
627 : }
628 :
629 : Datum
630 23632 : seg_union(PG_FUNCTION_ARGS)
631 : {
632 23632 : SEG *a = PG_GETARG_SEG_P(0);
633 23632 : SEG *b = PG_GETARG_SEG_P(1);
634 : SEG *n;
635 :
636 23632 : n = palloc_object(SEG);
637 :
638 : /* take max of upper endpoints */
639 23632 : if (a->upper > b->upper)
640 : {
641 20396 : n->upper = a->upper;
642 20396 : n->u_sigd = a->u_sigd;
643 20396 : n->u_ext = a->u_ext;
644 : }
645 : else
646 : {
647 3236 : n->upper = b->upper;
648 3236 : n->u_sigd = b->u_sigd;
649 3236 : n->u_ext = b->u_ext;
650 : }
651 :
652 : /* take min of lower endpoints */
653 23632 : if (a->lower < b->lower)
654 : {
655 23020 : n->lower = a->lower;
656 23020 : n->l_sigd = a->l_sigd;
657 23020 : n->l_ext = a->l_ext;
658 : }
659 : else
660 : {
661 612 : n->lower = b->lower;
662 612 : n->l_sigd = b->l_sigd;
663 612 : n->l_ext = b->l_ext;
664 : }
665 :
666 23632 : 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 21360 : rt_seg_size(SEG *a, float *size)
711 : {
712 21360 : if (a == (SEG *) NULL || a->upper <= a->lower)
713 0 : *size = 0.0;
714 : else
715 21360 : *size = fabsf(a->upper - a->lower);
716 21360 : }
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 8866 : seg_cmp(PG_FUNCTION_ARGS)
732 : {
733 8866 : SEG *a = PG_GETARG_SEG_P(0);
734 8866 : SEG *b = PG_GETARG_SEG_P(1);
735 :
736 : /*
737 : * First compare on lower boundary position
738 : */
739 8866 : if (a->lower < b->lower)
740 1808 : PG_RETURN_INT32(-1);
741 7058 : if (a->lower > b->lower)
742 1600 : 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 5458 : if (a->l_ext != b->l_ext)
752 : {
753 130 : if (a->l_ext == '-')
754 0 : PG_RETURN_INT32(-1);
755 130 : if (b->l_ext == '-')
756 0 : PG_RETURN_INT32(1);
757 130 : if (a->l_ext == '<')
758 50 : PG_RETURN_INT32(-1);
759 80 : if (b->l_ext == '<')
760 42 : PG_RETURN_INT32(1);
761 38 : if (a->l_ext == '>')
762 26 : PG_RETURN_INT32(1);
763 12 : if (b->l_ext == '>')
764 12 : PG_RETURN_INT32(-1);
765 : }
766 :
767 : /*
768 : * For other boundary types, consider # of significant digits first.
769 : */
770 5328 : if (a->l_sigd < b->l_sigd) /* (a) is blurred and is likely to include (b) */
771 36 : PG_RETURN_INT32(-1);
772 5292 : if (a->l_sigd > b->l_sigd) /* (a) is less blurred and is likely to be
773 : * included in (b) */
774 36 : PG_RETURN_INT32(1);
775 :
776 : /*
777 : * For same # of digits, an approximate boundary is more blurred than
778 : * exact.
779 : */
780 5256 : 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 5256 : if (a->upper < b->upper)
797 326 : PG_RETURN_INT32(-1);
798 4930 : if (a->upper > b->upper)
799 252 : 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 4678 : if (a->u_ext != b->u_ext)
809 : {
810 120 : if (a->u_ext == '-')
811 0 : PG_RETURN_INT32(1);
812 120 : if (b->u_ext == '-')
813 0 : PG_RETURN_INT32(-1);
814 120 : if (a->u_ext == '<')
815 6 : PG_RETURN_INT32(-1);
816 114 : if (b->u_ext == '<')
817 2 : PG_RETURN_INT32(1);
818 112 : if (a->u_ext == '>')
819 62 : PG_RETURN_INT32(1);
820 50 : if (b->u_ext == '>')
821 50 : 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 4558 : if (a->u_sigd < b->u_sigd) /* (a) is blurred and is likely to include (b) */
829 18 : PG_RETURN_INT32(1);
830 4540 : if (a->u_sigd > b->u_sigd) /* (a) is less blurred and is likely to be
831 : * included in (b) */
832 16 : 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 4524 : 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 4524 : 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 4 : seg_different(PG_FUNCTION_ARGS)
895 : {
896 4 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
897 : PG_GETARG_DATUM(0),
898 : PG_GETARG_DATUM(1)));
899 :
900 4 : 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 650 : restore(char *result, float val, int n)
920 : {
921 650 : 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 650 : if (n <= 0)
940 0 : n = FLT_DIG;
941 : else
942 650 : n = Min(n, FLT_DIG);
943 :
944 : /* remember the sign */
945 650 : sign = (val < 0 ? 1 : 0);
946 :
947 : /* print, in %e style to start with */
948 650 : sprintf(result, "%.*e", n - 1, val);
949 :
950 : /* find the exponent */
951 650 : p = strchr(result, 'e');
952 :
953 : /* punt if we have 'inf' or similar */
954 650 : if (p == NULL)
955 0 : return strlen(result);
956 :
957 650 : exp = atoi(p + 1);
958 650 : if (exp == 0)
959 : {
960 : /* just truncate off the 'e+00' */
961 338 : *p = '\0';
962 : }
963 : else
964 : {
965 312 : 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 1274 : for (p = result + sign, i = 10, dp = 0; *p != 'e'; p++, i++)
972 : {
973 998 : buf[i] = *p;
974 998 : if (*p == '.')
975 : {
976 260 : dp = i--; /* skip the decimal point */
977 : }
978 : }
979 276 : if (dp == 0)
980 16 : dp = i--; /* no decimal point was found in the above
981 : * for() loop */
982 :
983 276 : if (exp > 0)
984 : {
985 266 : 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 86 : exp = dp - 10 + exp - n;
993 86 : buf[10 + n] = '\0';
994 :
995 : /* insert the decimal point */
996 86 : if (n > 1)
997 : {
998 78 : dp = 11;
999 1014 : for (i = 23; i > dp; i--)
1000 936 : buf[i] = buf[i - 1];
1001 78 : buf[dp] = '.';
1002 : }
1003 :
1004 : /*
1005 : * adjust the exponent by the number of digits after the
1006 : * decimal point
1007 : */
1008 86 : if (n > 1)
1009 78 : sprintf(&buf[11 + n], "e%d", exp + n - 1);
1010 : else
1011 8 : sprintf(&buf[11], "e%d", exp + n - 1);
1012 :
1013 86 : if (sign)
1014 : {
1015 0 : buf[9] = '-';
1016 0 : strcpy(result, &buf[9]);
1017 : }
1018 : else
1019 86 : strcpy(result, &buf[10]);
1020 : }
1021 : else
1022 : { /* insert the decimal point */
1023 180 : dp += exp;
1024 2160 : for (i = 23; i > dp; i--)
1025 1980 : buf[i] = buf[i - 1];
1026 180 : buf[11 + n] = '\0';
1027 180 : buf[dp] = '.';
1028 180 : if (sign)
1029 : {
1030 0 : buf[9] = '-';
1031 0 : strcpy(result, &buf[9]);
1032 : }
1033 : else
1034 180 : strcpy(result, &buf[10]);
1035 : }
1036 : }
1037 : else
1038 : { /* exp <= 0 */
1039 10 : dp += exp - 1;
1040 10 : buf[10 + n] = '\0';
1041 10 : buf[dp] = '.';
1042 10 : if (sign)
1043 : {
1044 0 : buf[dp - 2] = '-';
1045 0 : strcpy(result, &buf[dp - 2]);
1046 : }
1047 : else
1048 10 : 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 650 : 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 10382 : significant_digits(const char *s)
1070 : {
1071 10382 : const char *p = s;
1072 : int n,
1073 : c,
1074 : zeroes;
1075 :
1076 10382 : zeroes = 1;
1077 : /* skip leading zeroes and sign */
1078 10660 : for (c = *p; (c == '0' || c == '+' || c == '-') && c != 0; c = *(++p));
1079 :
1080 : /* skip decimal point and following zeroes */
1081 10424 : for (c = *p; (c == '0' || c == '.') && c != 0; c = *(++p))
1082 : {
1083 42 : if (c != '.')
1084 22 : zeroes++;
1085 : }
1086 :
1087 : /* count significant digits (n) */
1088 40706 : for (c = *p, n = 0; c != 0; c = *(++p))
1089 : {
1090 30378 : if (!((c >= '0' && c <= '9') || (c == '.')))
1091 54 : break;
1092 30324 : if (c != '.')
1093 21234 : n++;
1094 : }
1095 :
1096 10382 : if (!n)
1097 196 : return zeroes;
1098 :
1099 10186 : return n;
1100 : }
|
