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 0 : 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 0 : PG_FUNCTION_INFO_V1(seg_in);
50 0 : PG_FUNCTION_INFO_V1(seg_out);
51 0 : PG_FUNCTION_INFO_V1(seg_size);
52 0 : PG_FUNCTION_INFO_V1(seg_lower);
53 0 : PG_FUNCTION_INFO_V1(seg_upper);
54 0 : PG_FUNCTION_INFO_V1(seg_center);
55 :
56 : /*
57 : ** GiST support methods
58 : */
59 0 : PG_FUNCTION_INFO_V1(gseg_consistent);
60 0 : PG_FUNCTION_INFO_V1(gseg_compress);
61 0 : PG_FUNCTION_INFO_V1(gseg_decompress);
62 0 : PG_FUNCTION_INFO_V1(gseg_picksplit);
63 0 : PG_FUNCTION_INFO_V1(gseg_penalty);
64 0 : PG_FUNCTION_INFO_V1(gseg_union);
65 0 : 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 0 : PG_FUNCTION_INFO_V1(seg_same);
75 0 : PG_FUNCTION_INFO_V1(seg_contains);
76 0 : PG_FUNCTION_INFO_V1(seg_contained);
77 0 : PG_FUNCTION_INFO_V1(seg_overlap);
78 0 : PG_FUNCTION_INFO_V1(seg_left);
79 0 : PG_FUNCTION_INFO_V1(seg_over_left);
80 0 : PG_FUNCTION_INFO_V1(seg_right);
81 0 : PG_FUNCTION_INFO_V1(seg_over_right);
82 0 : PG_FUNCTION_INFO_V1(seg_union);
83 0 : PG_FUNCTION_INFO_V1(seg_inter);
84 : static void rt_seg_size(SEG *a, float *size);
85 :
86 : /*
87 : ** Various operators
88 : */
89 0 : PG_FUNCTION_INFO_V1(seg_cmp);
90 0 : PG_FUNCTION_INFO_V1(seg_lt);
91 0 : PG_FUNCTION_INFO_V1(seg_le);
92 0 : PG_FUNCTION_INFO_V1(seg_gt);
93 0 : PG_FUNCTION_INFO_V1(seg_ge);
94 0 : 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 0 : seg_in(PG_FUNCTION_ARGS)
108 : {
109 0 : char *str = PG_GETARG_CSTRING(0);
110 0 : SEG *result = palloc_object(SEG);
111 0 : yyscan_t scanner;
112 :
113 0 : seg_scanner_init(str, &scanner);
114 :
115 0 : if (seg_yyparse(result, fcinfo->context, scanner) != 0)
116 0 : seg_yyerror(result, fcinfo->context, scanner, "bogus input");
117 :
118 0 : seg_scanner_finish(scanner);
119 :
120 0 : PG_RETURN_POINTER(result);
121 0 : }
122 :
123 : Datum
124 0 : seg_out(PG_FUNCTION_ARGS)
125 : {
126 0 : SEG *seg = PG_GETARG_SEG_P(0);
127 0 : char *result;
128 0 : char *p;
129 :
130 0 : p = result = (char *) palloc(40);
131 :
132 0 : if (seg->l_ext == '>' || seg->l_ext == '<' || seg->l_ext == '~')
133 0 : p += sprintf(p, "%c", seg->l_ext);
134 :
135 0 : 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 0 : p += restore(p, seg->lower, seg->l_sigd);
141 0 : }
142 : else
143 : {
144 0 : if (seg->l_ext != '-')
145 : {
146 : /* print the lower boundary if exists */
147 0 : p += restore(p, seg->lower, seg->l_sigd);
148 0 : p += sprintf(p, " ");
149 0 : }
150 0 : p += sprintf(p, "..");
151 0 : if (seg->u_ext != '-')
152 : {
153 : /* print the upper boundary if exists */
154 0 : p += sprintf(p, " ");
155 0 : if (seg->u_ext == '>' || seg->u_ext == '<' || seg->l_ext == '~')
156 0 : p += sprintf(p, "%c", seg->u_ext);
157 0 : p += restore(p, seg->upper, seg->u_sigd);
158 0 : }
159 : }
160 :
161 0 : PG_RETURN_CSTRING(result);
162 0 : }
163 :
164 : Datum
165 0 : seg_center(PG_FUNCTION_ARGS)
166 : {
167 0 : SEG *seg = PG_GETARG_SEG_P(0);
168 :
169 0 : PG_RETURN_FLOAT4(((float) seg->lower + (float) seg->upper) / 2.0);
170 0 : }
171 :
172 : Datum
173 0 : seg_lower(PG_FUNCTION_ARGS)
174 : {
175 0 : SEG *seg = PG_GETARG_SEG_P(0);
176 :
177 0 : PG_RETURN_FLOAT4(seg->lower);
178 0 : }
179 :
180 : Datum
181 0 : seg_upper(PG_FUNCTION_ARGS)
182 : {
183 0 : SEG *seg = PG_GETARG_SEG_P(0);
184 :
185 0 : PG_RETURN_FLOAT4(seg->upper);
186 0 : }
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 0 : gseg_consistent(PG_FUNCTION_ARGS)
201 : {
202 0 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
203 0 : Datum query = PG_GETARG_DATUM(1);
204 0 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
205 : #ifdef NOT_USED
206 : Oid subtype = PG_GETARG_OID(3);
207 : #endif
208 0 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
209 :
210 : /* All cases served by this function are exact */
211 0 : *recheck = false;
212 :
213 : /*
214 : * if entry is not leaf, use gseg_internal_consistent, else use
215 : * gseg_leaf_consistent
216 : */
217 0 : if (GIST_LEAF(entry))
218 0 : return gseg_leaf_consistent(entry->key, query, strategy);
219 : else
220 0 : return gseg_internal_consistent(entry->key, query, strategy);
221 0 : }
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 0 : gseg_union(PG_FUNCTION_ARGS)
229 : {
230 0 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
231 0 : int *sizep = (int *) PG_GETARG_POINTER(1);
232 0 : int numranges,
233 : i;
234 0 : Datum out = 0;
235 0 : Datum tmp;
236 :
237 : #ifdef GIST_DEBUG
238 : fprintf(stderr, "union\n");
239 : #endif
240 :
241 0 : numranges = entryvec->n;
242 0 : tmp = entryvec->vector[0].key;
243 0 : *sizep = sizeof(SEG);
244 :
245 0 : for (i = 1; i < numranges; i++)
246 : {
247 0 : out = gseg_binary_union(tmp, entryvec->vector[i].key, sizep);
248 0 : tmp = out;
249 0 : }
250 :
251 0 : PG_RETURN_DATUM(out);
252 0 : }
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 0 : gseg_penalty(PG_FUNCTION_ARGS)
276 : {
277 0 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
278 0 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
279 0 : float *result = (float *) PG_GETARG_POINTER(2);
280 0 : SEG *ud;
281 0 : float tmp1,
282 : tmp2;
283 :
284 0 : ud = DatumGetSegP(DirectFunctionCall2(seg_union,
285 : origentry->key,
286 : newentry->key));
287 0 : rt_seg_size(ud, &tmp1);
288 0 : rt_seg_size(DatumGetSegP(origentry->key), &tmp2);
289 0 : *result = tmp1 - tmp2;
290 :
291 : #ifdef GIST_DEBUG
292 : fprintf(stderr, "penalty\n");
293 : fprintf(stderr, "\t%g\n", *result);
294 : #endif
295 :
296 0 : PG_RETURN_POINTER(result);
297 0 : }
298 :
299 : /*
300 : * Compare function for gseg_picksplit_item: sort by center.
301 : */
302 : static int
303 0 : gseg_picksplit_item_cmp(const void *a, const void *b)
304 : {
305 0 : const gseg_picksplit_item *i1 = (const gseg_picksplit_item *) a;
306 0 : const gseg_picksplit_item *i2 = (const gseg_picksplit_item *) b;
307 :
308 0 : if (i1->center < i2->center)
309 0 : return -1;
310 0 : else if (i1->center == i2->center)
311 0 : return 0;
312 : else
313 0 : return 1;
314 0 : }
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 0 : gseg_picksplit(PG_FUNCTION_ARGS)
325 : {
326 0 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
327 0 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
328 0 : int i;
329 0 : SEG *seg,
330 : *seg_l,
331 : *seg_r;
332 0 : gseg_picksplit_item *sort_items;
333 0 : OffsetNumber *left,
334 : *right;
335 0 : OffsetNumber maxoff;
336 0 : 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 0 : maxoff = entryvec->n - 1;
344 :
345 : /*
346 : * Prepare the auxiliary array and sort it.
347 : */
348 0 : sort_items = (gseg_picksplit_item *)
349 0 : palloc(maxoff * sizeof(gseg_picksplit_item));
350 0 : for (i = 1; i <= maxoff; i++)
351 : {
352 0 : seg = DatumGetSegP(entryvec->vector[i].key);
353 : /* center calculation is done this way to avoid possible overflow */
354 0 : sort_items[i - 1].center = seg->lower * 0.5f + seg->upper * 0.5f;
355 0 : sort_items[i - 1].index = i;
356 0 : sort_items[i - 1].data = seg;
357 0 : }
358 0 : 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 0 : firstright = maxoff / 2;
363 :
364 0 : v->spl_left = (OffsetNumber *) palloc(maxoff * sizeof(OffsetNumber));
365 0 : v->spl_right = (OffsetNumber *) palloc(maxoff * sizeof(OffsetNumber));
366 0 : left = v->spl_left;
367 0 : v->spl_nleft = 0;
368 0 : right = v->spl_right;
369 0 : v->spl_nright = 0;
370 :
371 : /*
372 : * Emit segments to the left output page, and compute its bounding box.
373 : */
374 0 : seg_l = palloc_object(SEG);
375 0 : memcpy(seg_l, sort_items[0].data, sizeof(SEG));
376 0 : *left++ = sort_items[0].index;
377 0 : v->spl_nleft++;
378 0 : for (i = 1; i < firstright; i++)
379 : {
380 0 : Datum sortitem = PointerGetDatum(sort_items[i].data);
381 :
382 0 : seg_l = DatumGetSegP(DirectFunctionCall2(seg_union,
383 : PointerGetDatum(seg_l),
384 : sortitem));
385 0 : *left++ = sort_items[i].index;
386 0 : v->spl_nleft++;
387 0 : }
388 :
389 : /*
390 : * Likewise for the right page.
391 : */
392 0 : seg_r = palloc_object(SEG);
393 0 : memcpy(seg_r, sort_items[firstright].data, sizeof(SEG));
394 0 : *right++ = sort_items[firstright].index;
395 0 : v->spl_nright++;
396 0 : for (i = firstright + 1; i < maxoff; i++)
397 : {
398 0 : Datum sortitem = PointerGetDatum(sort_items[i].data);
399 :
400 0 : seg_r = DatumGetSegP(DirectFunctionCall2(seg_union,
401 : PointerGetDatum(seg_r),
402 : sortitem));
403 0 : *right++ = sort_items[i].index;
404 0 : v->spl_nright++;
405 0 : }
406 :
407 0 : v->spl_ldatum = PointerGetDatum(seg_l);
408 0 : v->spl_rdatum = PointerGetDatum(seg_r);
409 :
410 0 : PG_RETURN_POINTER(v);
411 0 : }
412 :
413 : /*
414 : ** Equality methods
415 : */
416 : Datum
417 0 : gseg_same(PG_FUNCTION_ARGS)
418 : {
419 0 : bool *result = (bool *) PG_GETARG_POINTER(2);
420 :
421 0 : if (DatumGetBool(DirectFunctionCall2(seg_same, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1))))
422 0 : *result = true;
423 : else
424 0 : *result = false;
425 :
426 : #ifdef GIST_DEBUG
427 : fprintf(stderr, "same: %s\n", (*result ? "TRUE" : "FALSE"));
428 : #endif
429 :
430 0 : PG_RETURN_POINTER(result);
431 0 : }
432 :
433 : /*
434 : ** SUPPORT ROUTINES
435 : */
436 : static Datum
437 0 : gseg_leaf_consistent(Datum key, Datum query, StrategyNumber strategy)
438 : {
439 0 : Datum retval;
440 :
441 : #ifdef GIST_QUERY_DEBUG
442 : fprintf(stderr, "leaf_consistent, %d\n", strategy);
443 : #endif
444 :
445 0 : switch (strategy)
446 : {
447 : case RTLeftStrategyNumber:
448 0 : retval = DirectFunctionCall2(seg_left, key, query);
449 0 : break;
450 : case RTOverLeftStrategyNumber:
451 0 : retval = DirectFunctionCall2(seg_over_left, key, query);
452 0 : break;
453 : case RTOverlapStrategyNumber:
454 0 : retval = DirectFunctionCall2(seg_overlap, key, query);
455 0 : break;
456 : case RTOverRightStrategyNumber:
457 0 : retval = DirectFunctionCall2(seg_over_right, key, query);
458 0 : break;
459 : case RTRightStrategyNumber:
460 0 : retval = DirectFunctionCall2(seg_right, key, query);
461 0 : break;
462 : case RTSameStrategyNumber:
463 0 : retval = DirectFunctionCall2(seg_same, key, query);
464 0 : break;
465 : case RTContainsStrategyNumber:
466 : case RTOldContainsStrategyNumber:
467 0 : retval = DirectFunctionCall2(seg_contains, key, query);
468 0 : break;
469 : case RTContainedByStrategyNumber:
470 : case RTOldContainedByStrategyNumber:
471 0 : retval = DirectFunctionCall2(seg_contained, key, query);
472 0 : break;
473 : default:
474 0 : retval = BoolGetDatum(false);
475 0 : }
476 :
477 0 : PG_RETURN_DATUM(retval);
478 0 : }
479 :
480 : static Datum
481 0 : gseg_internal_consistent(Datum key, Datum query, StrategyNumber strategy)
482 : {
483 0 : bool retval;
484 :
485 : #ifdef GIST_QUERY_DEBUG
486 : fprintf(stderr, "internal_consistent, %d\n", strategy);
487 : #endif
488 :
489 0 : switch (strategy)
490 : {
491 : case RTLeftStrategyNumber:
492 0 : retval =
493 0 : !DatumGetBool(DirectFunctionCall2(seg_over_right, key, query));
494 0 : break;
495 : case RTOverLeftStrategyNumber:
496 0 : retval =
497 0 : !DatumGetBool(DirectFunctionCall2(seg_right, key, query));
498 0 : break;
499 : case RTOverlapStrategyNumber:
500 0 : retval =
501 0 : DatumGetBool(DirectFunctionCall2(seg_overlap, key, query));
502 0 : break;
503 : case RTOverRightStrategyNumber:
504 0 : retval =
505 0 : !DatumGetBool(DirectFunctionCall2(seg_left, key, query));
506 0 : break;
507 : case RTRightStrategyNumber:
508 0 : retval =
509 0 : !DatumGetBool(DirectFunctionCall2(seg_over_left, key, query));
510 0 : break;
511 : case RTSameStrategyNumber:
512 : case RTContainsStrategyNumber:
513 : case RTOldContainsStrategyNumber:
514 0 : retval =
515 0 : DatumGetBool(DirectFunctionCall2(seg_contains, key, query));
516 0 : break;
517 : case RTContainedByStrategyNumber:
518 : case RTOldContainedByStrategyNumber:
519 0 : retval =
520 0 : DatumGetBool(DirectFunctionCall2(seg_overlap, key, query));
521 0 : break;
522 : default:
523 0 : retval = false;
524 0 : }
525 :
526 0 : PG_RETURN_BOOL(retval);
527 0 : }
528 :
529 : static Datum
530 0 : gseg_binary_union(Datum r1, Datum r2, int *sizep)
531 : {
532 0 : Datum retval;
533 :
534 0 : retval = DirectFunctionCall2(seg_union, r1, r2);
535 0 : *sizep = sizeof(SEG);
536 :
537 0 : return retval;
538 0 : }
539 :
540 :
541 : Datum
542 0 : seg_contains(PG_FUNCTION_ARGS)
543 : {
544 0 : SEG *a = PG_GETARG_SEG_P(0);
545 0 : SEG *b = PG_GETARG_SEG_P(1);
546 :
547 0 : PG_RETURN_BOOL((a->lower <= b->lower) && (a->upper >= b->upper));
548 0 : }
549 :
550 : Datum
551 0 : seg_contained(PG_FUNCTION_ARGS)
552 : {
553 0 : Datum a = PG_GETARG_DATUM(0);
554 0 : Datum b = PG_GETARG_DATUM(1);
555 :
556 0 : PG_RETURN_DATUM(DirectFunctionCall2(seg_contains, b, a));
557 0 : }
558 :
559 : /*****************************************************************************
560 : * Operator class for R-tree indexing
561 : *****************************************************************************/
562 :
563 : Datum
564 0 : seg_same(PG_FUNCTION_ARGS)
565 : {
566 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
567 : PG_GETARG_DATUM(0),
568 : PG_GETARG_DATUM(1)));
569 :
570 0 : PG_RETURN_BOOL(cmp == 0);
571 0 : }
572 :
573 : /* seg_overlap -- does a overlap b?
574 : */
575 : Datum
576 0 : seg_overlap(PG_FUNCTION_ARGS)
577 : {
578 0 : SEG *a = PG_GETARG_SEG_P(0);
579 0 : SEG *b = PG_GETARG_SEG_P(1);
580 :
581 0 : PG_RETURN_BOOL(((a->upper >= b->upper) && (a->lower <= b->upper)) ||
582 : ((b->upper >= a->upper) && (b->lower <= a->upper)));
583 0 : }
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 0 : seg_over_left(PG_FUNCTION_ARGS)
589 : {
590 0 : SEG *a = PG_GETARG_SEG_P(0);
591 0 : SEG *b = PG_GETARG_SEG_P(1);
592 :
593 0 : PG_RETURN_BOOL(a->upper <= b->upper);
594 0 : }
595 :
596 : /* seg_left -- is (a) entirely on the left of (b)?
597 : */
598 : Datum
599 0 : seg_left(PG_FUNCTION_ARGS)
600 : {
601 0 : SEG *a = PG_GETARG_SEG_P(0);
602 0 : SEG *b = PG_GETARG_SEG_P(1);
603 :
604 0 : PG_RETURN_BOOL(a->upper < b->lower);
605 0 : }
606 :
607 : /* seg_right -- is (a) entirely on the right of (b)?
608 : */
609 : Datum
610 0 : seg_right(PG_FUNCTION_ARGS)
611 : {
612 0 : SEG *a = PG_GETARG_SEG_P(0);
613 0 : SEG *b = PG_GETARG_SEG_P(1);
614 :
615 0 : PG_RETURN_BOOL(a->lower > b->upper);
616 0 : }
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 0 : seg_over_right(PG_FUNCTION_ARGS)
622 : {
623 0 : SEG *a = PG_GETARG_SEG_P(0);
624 0 : SEG *b = PG_GETARG_SEG_P(1);
625 :
626 0 : PG_RETURN_BOOL(a->lower >= b->lower);
627 0 : }
628 :
629 : Datum
630 0 : seg_union(PG_FUNCTION_ARGS)
631 : {
632 0 : SEG *a = PG_GETARG_SEG_P(0);
633 0 : SEG *b = PG_GETARG_SEG_P(1);
634 0 : SEG *n;
635 :
636 0 : n = palloc_object(SEG);
637 :
638 : /* take max of upper endpoints */
639 0 : if (a->upper > b->upper)
640 : {
641 0 : n->upper = a->upper;
642 0 : n->u_sigd = a->u_sigd;
643 0 : n->u_ext = a->u_ext;
644 0 : }
645 : else
646 : {
647 0 : n->upper = b->upper;
648 0 : n->u_sigd = b->u_sigd;
649 0 : n->u_ext = b->u_ext;
650 : }
651 :
652 : /* take min of lower endpoints */
653 0 : if (a->lower < b->lower)
654 : {
655 0 : n->lower = a->lower;
656 0 : n->l_sigd = a->l_sigd;
657 0 : n->l_ext = a->l_ext;
658 0 : }
659 : else
660 : {
661 0 : n->lower = b->lower;
662 0 : n->l_sigd = b->l_sigd;
663 0 : n->l_ext = b->l_ext;
664 : }
665 :
666 0 : PG_RETURN_POINTER(n);
667 0 : }
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 0 : 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 0 : }
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 0 : }
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 0 : }
708 :
709 : static void
710 0 : rt_seg_size(SEG *a, float *size)
711 : {
712 0 : if (a == (SEG *) NULL || a->upper <= a->lower)
713 0 : *size = 0.0;
714 : else
715 0 : *size = fabsf(a->upper - a->lower);
716 0 : }
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 0 : }
725 :
726 :
727 : /*****************************************************************************
728 : * Miscellaneous operators
729 : *****************************************************************************/
730 : Datum
731 0 : seg_cmp(PG_FUNCTION_ARGS)
732 : {
733 0 : SEG *a = PG_GETARG_SEG_P(0);
734 0 : SEG *b = PG_GETARG_SEG_P(1);
735 :
736 : /*
737 : * First compare on lower boundary position
738 : */
739 0 : if (a->lower < b->lower)
740 0 : PG_RETURN_INT32(-1);
741 0 : if (a->lower > b->lower)
742 0 : 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 0 : if (a->l_ext != b->l_ext)
752 : {
753 0 : if (a->l_ext == '-')
754 0 : PG_RETURN_INT32(-1);
755 0 : if (b->l_ext == '-')
756 0 : PG_RETURN_INT32(1);
757 0 : if (a->l_ext == '<')
758 0 : PG_RETURN_INT32(-1);
759 0 : if (b->l_ext == '<')
760 0 : PG_RETURN_INT32(1);
761 0 : if (a->l_ext == '>')
762 0 : PG_RETURN_INT32(1);
763 0 : if (b->l_ext == '>')
764 0 : PG_RETURN_INT32(-1);
765 0 : }
766 :
767 : /*
768 : * For other boundary types, consider # of significant digits first.
769 : */
770 0 : if (a->l_sigd < b->l_sigd) /* (a) is blurred and is likely to include (b) */
771 0 : PG_RETURN_INT32(-1);
772 0 : if (a->l_sigd > b->l_sigd) /* (a) is less blurred and is likely to be
773 : * included in (b) */
774 0 : PG_RETURN_INT32(1);
775 :
776 : /*
777 : * For same # of digits, an approximate boundary is more blurred than
778 : * exact.
779 : */
780 0 : 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 0 : }
790 :
791 : /* at this point, the lower boundaries are identical */
792 :
793 : /*
794 : * First compare on upper boundary position
795 : */
796 0 : if (a->upper < b->upper)
797 0 : PG_RETURN_INT32(-1);
798 0 : if (a->upper > b->upper)
799 0 : 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 0 : if (a->u_ext != b->u_ext)
809 : {
810 0 : if (a->u_ext == '-')
811 0 : PG_RETURN_INT32(1);
812 0 : if (b->u_ext == '-')
813 0 : PG_RETURN_INT32(-1);
814 0 : if (a->u_ext == '<')
815 0 : PG_RETURN_INT32(-1);
816 0 : if (b->u_ext == '<')
817 0 : PG_RETURN_INT32(1);
818 0 : if (a->u_ext == '>')
819 0 : PG_RETURN_INT32(1);
820 0 : if (b->u_ext == '>')
821 0 : PG_RETURN_INT32(-1);
822 0 : }
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 0 : if (a->u_sigd < b->u_sigd) /* (a) is blurred and is likely to include (b) */
829 0 : PG_RETURN_INT32(1);
830 0 : if (a->u_sigd > b->u_sigd) /* (a) is less blurred and is likely to be
831 : * included in (b) */
832 0 : 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 0 : 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 0 : }
848 :
849 0 : PG_RETURN_INT32(0);
850 0 : }
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 0 : }
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 0 : }
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 0 : }
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 0 : }
891 :
892 :
893 : Datum
894 0 : seg_different(PG_FUNCTION_ARGS)
895 : {
896 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
897 : PG_GETARG_DATUM(0),
898 : PG_GETARG_DATUM(1)));
899 :
900 0 : PG_RETURN_BOOL(cmp != 0);
901 0 : }
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 0 : restore(char *result, float val, int n)
920 : {
921 0 : 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 0 : char *p;
929 0 : int exp;
930 0 : 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 0 : if (n <= 0)
940 0 : n = FLT_DIG;
941 : else
942 0 : n = Min(n, FLT_DIG);
943 :
944 : /* remember the sign */
945 0 : sign = (val < 0 ? 1 : 0);
946 :
947 : /* print, in %e style to start with */
948 0 : sprintf(result, "%.*e", n - 1, val);
949 :
950 : /* find the exponent */
951 0 : p = strchr(result, 'e');
952 :
953 : /* punt if we have 'inf' or similar */
954 0 : if (p == NULL)
955 0 : return strlen(result);
956 :
957 0 : exp = atoi(p + 1);
958 0 : if (exp == 0)
959 : {
960 : /* just truncate off the 'e+00' */
961 0 : *p = '\0';
962 0 : }
963 : else
964 : {
965 0 : 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 0 : for (p = result + sign, i = 10, dp = 0; *p != 'e'; p++, i++)
972 : {
973 0 : buf[i] = *p;
974 0 : if (*p == '.')
975 : {
976 0 : dp = i--; /* skip the decimal point */
977 0 : }
978 0 : }
979 0 : if (dp == 0)
980 0 : dp = i--; /* no decimal point was found in the above
981 : * for() loop */
982 :
983 0 : if (exp > 0)
984 : {
985 0 : 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 0 : exp = dp - 10 + exp - n;
993 0 : buf[10 + n] = '\0';
994 :
995 : /* insert the decimal point */
996 0 : if (n > 1)
997 : {
998 0 : dp = 11;
999 0 : for (i = 23; i > dp; i--)
1000 0 : buf[i] = buf[i - 1];
1001 0 : buf[dp] = '.';
1002 0 : }
1003 :
1004 : /*
1005 : * adjust the exponent by the number of digits after the
1006 : * decimal point
1007 : */
1008 0 : if (n > 1)
1009 0 : sprintf(&buf[11 + n], "e%d", exp + n - 1);
1010 : else
1011 0 : sprintf(&buf[11], "e%d", exp + n - 1);
1012 :
1013 0 : if (sign)
1014 : {
1015 0 : buf[9] = '-';
1016 0 : strcpy(result, &buf[9]);
1017 0 : }
1018 : else
1019 0 : strcpy(result, &buf[10]);
1020 0 : }
1021 : else
1022 : { /* insert the decimal point */
1023 0 : dp += exp;
1024 0 : for (i = 23; i > dp; i--)
1025 0 : buf[i] = buf[i - 1];
1026 0 : buf[11 + n] = '\0';
1027 0 : buf[dp] = '.';
1028 0 : if (sign)
1029 : {
1030 0 : buf[9] = '-';
1031 0 : strcpy(result, &buf[9]);
1032 0 : }
1033 : else
1034 0 : strcpy(result, &buf[10]);
1035 : }
1036 0 : }
1037 : else
1038 : { /* exp <= 0 */
1039 0 : dp += exp - 1;
1040 0 : buf[10 + n] = '\0';
1041 0 : buf[dp] = '.';
1042 0 : if (sign)
1043 : {
1044 0 : buf[dp - 2] = '-';
1045 0 : strcpy(result, &buf[dp - 2]);
1046 0 : }
1047 : else
1048 0 : strcpy(result, &buf[dp - 1]);
1049 : }
1050 0 : }
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 0 : return strlen(result);
1058 0 : }
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 0 : significant_digits(const char *s)
1070 : {
1071 0 : const char *p = s;
1072 0 : int n,
1073 : c,
1074 : zeroes;
1075 :
1076 0 : zeroes = 1;
1077 : /* skip leading zeroes and sign */
1078 0 : for (c = *p; (c == '0' || c == '+' || c == '-') && c != 0; c = *(++p));
1079 :
1080 : /* skip decimal point and following zeroes */
1081 0 : for (c = *p; (c == '0' || c == '.') && c != 0; c = *(++p))
1082 : {
1083 0 : if (c != '.')
1084 0 : zeroes++;
1085 0 : }
1086 :
1087 : /* count significant digits (n) */
1088 0 : for (c = *p, n = 0; c != 0; c = *(++p))
1089 : {
1090 0 : if (!((c >= '0' && c <= '9') || (c == '.')))
1091 0 : break;
1092 0 : if (c != '.')
1093 0 : n++;
1094 0 : }
1095 :
1096 0 : if (!n)
1097 0 : return zeroes;
1098 :
1099 0 : return n;
1100 0 : }
|
