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