TLA 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 GIC 1 : PG_MODULE_MAGIC;
32 ECB :
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 GIC 2 : PG_FUNCTION_INFO_V1(seg_in);
47 CBC 2 : PG_FUNCTION_INFO_V1(seg_out);
48 1 : PG_FUNCTION_INFO_V1(seg_size);
49 2 : PG_FUNCTION_INFO_V1(seg_lower);
50 2 : PG_FUNCTION_INFO_V1(seg_upper);
51 2 : PG_FUNCTION_INFO_V1(seg_center);
52 ECB :
53 : /*
54 : ** GiST support methods
55 : */
56 GIC 2 : PG_FUNCTION_INFO_V1(gseg_consistent);
57 CBC 1 : PG_FUNCTION_INFO_V1(gseg_compress);
58 1 : PG_FUNCTION_INFO_V1(gseg_decompress);
59 2 : PG_FUNCTION_INFO_V1(gseg_picksplit);
60 2 : PG_FUNCTION_INFO_V1(gseg_penalty);
61 2 : PG_FUNCTION_INFO_V1(gseg_union);
62 2 : PG_FUNCTION_INFO_V1(gseg_same);
63 ECB : 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 GIC 2 : PG_FUNCTION_INFO_V1(seg_same);
72 CBC 2 : PG_FUNCTION_INFO_V1(seg_contains);
73 2 : PG_FUNCTION_INFO_V1(seg_contained);
74 2 : PG_FUNCTION_INFO_V1(seg_overlap);
75 2 : PG_FUNCTION_INFO_V1(seg_left);
76 2 : PG_FUNCTION_INFO_V1(seg_over_left);
77 2 : PG_FUNCTION_INFO_V1(seg_right);
78 2 : PG_FUNCTION_INFO_V1(seg_over_right);
79 1 : PG_FUNCTION_INFO_V1(seg_union);
80 1 : PG_FUNCTION_INFO_V1(seg_inter);
81 ECB : static void rt_seg_size(SEG *a, float *size);
82 :
83 : /*
84 : ** Various operators
85 : */
86 GIC 2 : PG_FUNCTION_INFO_V1(seg_cmp);
87 CBC 1 : PG_FUNCTION_INFO_V1(seg_lt);
88 1 : PG_FUNCTION_INFO_V1(seg_le);
89 1 : PG_FUNCTION_INFO_V1(seg_gt);
90 1 : PG_FUNCTION_INFO_V1(seg_ge);
91 2 : PG_FUNCTION_INFO_V1(seg_different);
92 ECB :
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 GIC 2823 : seg_in(PG_FUNCTION_ARGS)
105 ECB : {
106 GIC 2823 : char *str = PG_GETARG_CSTRING(0);
107 CBC 2823 : SEG *result = palloc(sizeof(SEG));
108 ECB :
109 GIC 2823 : seg_scanner_init(str);
110 ECB :
111 GNC 2823 : if (seg_yyparse(result, fcinfo->context) != 0)
112 8 : seg_yyerror(result, fcinfo->context, "bogus input");
113 ECB :
114 GIC 2814 : seg_scanner_finish();
115 ECB :
116 GIC 2814 : PG_RETURN_POINTER(result);
117 ECB : }
118 :
119 : Datum
120 GIC 209 : seg_out(PG_FUNCTION_ARGS)
121 ECB : {
122 GIC 209 : SEG *seg = PG_GETARG_SEG_P(0);
123 ECB : char *result;
124 : char *p;
125 :
126 GIC 209 : p = result = (char *) palloc(40);
127 ECB :
128 GIC 209 : if (seg->l_ext == '>' || seg->l_ext == '<' || seg->l_ext == '~')
129 CBC 22 : p += sprintf(p, "%c", seg->l_ext);
130 ECB :
131 GIC 209 : if (seg->lower == seg->upper && seg->l_ext == seg->u_ext)
132 ECB : {
133 : /*
134 : * indicates that this interval was built by seg_in off a single point
135 : */
136 GIC 47 : p += restore(p, seg->lower, seg->l_sigd);
137 ECB : }
138 : else
139 : {
140 GIC 162 : if (seg->l_ext != '-')
141 ECB : {
142 : /* print the lower boundary if exists */
143 GIC 155 : p += restore(p, seg->lower, seg->l_sigd);
144 CBC 155 : p += sprintf(p, " ");
145 ECB : }
146 GIC 162 : p += sprintf(p, "..");
147 CBC 162 : if (seg->u_ext != '-')
148 ECB : {
149 : /* print the upper boundary if exists */
150 GIC 123 : p += sprintf(p, " ");
151 CBC 123 : if (seg->u_ext == '>' || seg->u_ext == '<' || seg->l_ext == '~')
152 32 : p += sprintf(p, "%c", seg->u_ext);
153 123 : p += restore(p, seg->upper, seg->u_sigd);
154 ECB : }
155 : }
156 :
157 GIC 209 : PG_RETURN_CSTRING(result);
158 ECB : }
159 :
160 : Datum
161 GIC 143 : seg_center(PG_FUNCTION_ARGS)
162 ECB : {
163 GIC 143 : SEG *seg = PG_GETARG_SEG_P(0);
164 ECB :
165 GIC 143 : PG_RETURN_FLOAT4(((float) seg->lower + (float) seg->upper) / 2.0);
166 ECB : }
167 :
168 : Datum
169 GIC 143 : seg_lower(PG_FUNCTION_ARGS)
170 ECB : {
171 GIC 143 : SEG *seg = PG_GETARG_SEG_P(0);
172 ECB :
173 GIC 143 : PG_RETURN_FLOAT4(seg->lower);
174 ECB : }
175 :
176 : Datum
177 GIC 143 : seg_upper(PG_FUNCTION_ARGS)
178 ECB : {
179 GIC 143 : SEG *seg = PG_GETARG_SEG_P(0);
180 ECB :
181 GIC 143 : PG_RETURN_FLOAT4(seg->upper);
182 ECB : }
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 GIC 5892 : gseg_consistent(PG_FUNCTION_ARGS)
197 ECB : {
198 GIC 5892 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
199 CBC 5892 : Datum query = PG_GETARG_DATUM(1);
200 5892 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
201 ECB :
202 : /* Oid subtype = PG_GETARG_OID(3); */
203 GIC 5892 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
204 ECB :
205 : /* All cases served by this function are exact */
206 GIC 5892 : *recheck = false;
207 ECB :
208 : /*
209 : * if entry is not leaf, use gseg_internal_consistent, else use
210 : * gseg_leaf_consistent
211 : */
212 GIC 5892 : if (GIST_LEAF(entry))
213 CBC 5820 : return gseg_leaf_consistent(entry->key, query, strategy);
214 ECB : else
215 GIC 72 : return gseg_internal_consistent(entry->key, query, strategy);
216 ECB : }
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 GIC 2316 : gseg_union(PG_FUNCTION_ARGS)
224 ECB : {
225 GIC 2316 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
226 CBC 2316 : int *sizep = (int *) PG_GETARG_POINTER(1);
227 ECB : int numranges,
228 : i;
229 GIC 2316 : Datum out = 0;
230 ECB : Datum tmp;
231 :
232 : #ifdef GIST_DEBUG
233 : fprintf(stderr, "union\n");
234 : #endif
235 :
236 GIC 2316 : numranges = entryvec->n;
237 CBC 2316 : tmp = entryvec->vector[0].key;
238 2316 : *sizep = sizeof(SEG);
239 ECB :
240 GIC 4632 : for (i = 1; i < numranges; i++)
241 ECB : {
242 GIC 2316 : out = gseg_binary_union(tmp, entryvec->vector[i].key, sizep);
243 CBC 2316 : tmp = out;
244 ECB : }
245 :
246 GIC 2316 : PG_RETURN_DATUM(out);
247 ECB : }
248 :
249 : /*
250 : ** GiST Compress and Decompress methods for segments
251 : ** do not do anything.
252 : */
253 : Datum
254 UIC 0 : gseg_compress(PG_FUNCTION_ARGS)
255 EUB : {
256 UIC 0 : PG_RETURN_POINTER(PG_GETARG_POINTER(0));
257 EUB : }
258 :
259 : Datum
260 UIC 0 : gseg_decompress(PG_FUNCTION_ARGS)
261 EUB : {
262 UIC 0 : PG_RETURN_POINTER(PG_GETARG_POINTER(0));
263 EUB : }
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 GIC 5157 : gseg_penalty(PG_FUNCTION_ARGS)
271 ECB : {
272 GIC 5157 : GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
273 CBC 5157 : GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
274 5157 : float *result = (float *) PG_GETARG_POINTER(2);
275 ECB : SEG *ud;
276 : float tmp1,
277 : tmp2;
278 :
279 GIC 5157 : ud = DatumGetSegP(DirectFunctionCall2(seg_union,
280 ECB : origentry->key,
281 : newentry->key));
282 GIC 5157 : rt_seg_size(ud, &tmp1);
283 CBC 5157 : rt_seg_size(DatumGetSegP(origentry->key), &tmp2);
284 5157 : *result = tmp1 - tmp2;
285 ECB :
286 : #ifdef GIST_DEBUG
287 : fprintf(stderr, "penalty\n");
288 : fprintf(stderr, "\t%g\n", *result);
289 : #endif
290 :
291 GIC 5157 : PG_RETURN_POINTER(result);
292 ECB : }
293 :
294 : /*
295 : * Compare function for gseg_picksplit_item: sort by center.
296 : */
297 : static int
298 GIC 29102 : gseg_picksplit_item_cmp(const void *a, const void *b)
299 ECB : {
300 GIC 29102 : const gseg_picksplit_item *i1 = (const gseg_picksplit_item *) a;
301 CBC 29102 : const gseg_picksplit_item *i2 = (const gseg_picksplit_item *) b;
302 ECB :
303 GIC 29102 : if (i1->center < i2->center)
304 CBC 11931 : return -1;
305 17171 : else if (i1->center == i2->center)
306 5238 : return 0;
307 ECB : else
308 GIC 11933 : return 1;
309 ECB : }
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 GIC 17 : gseg_picksplit(PG_FUNCTION_ARGS)
320 ECB : {
321 GIC 17 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
322 CBC 17 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
323 ECB : 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 GIC 17 : maxoff = entryvec->n - 1;
339 ECB :
340 : /*
341 : * Prepare the auxiliary array and sort it.
342 : */
343 : sort_items = (gseg_picksplit_item *)
344 GIC 17 : palloc(maxoff * sizeof(gseg_picksplit_item));
345 CBC 4471 : for (i = 1; i <= maxoff; i++)
346 ECB : {
347 GIC 4454 : seg = DatumGetSegP(entryvec->vector[i].key);
348 ECB : /* center calculation is done this way to avoid possible overflow */
349 GIC 4454 : sort_items[i - 1].center = seg->lower * 0.5f + seg->upper * 0.5f;
350 CBC 4454 : sort_items[i - 1].index = i;
351 4454 : sort_items[i - 1].data = seg;
352 ECB : }
353 GIC 17 : qsort(sort_items, maxoff, sizeof(gseg_picksplit_item),
354 ECB : gseg_picksplit_item_cmp);
355 :
356 : /* sort items below "firstright" will go into the left side */
357 GIC 17 : firstright = maxoff / 2;
358 ECB :
359 GIC 17 : v->spl_left = (OffsetNumber *) palloc(maxoff * sizeof(OffsetNumber));
360 CBC 17 : v->spl_right = (OffsetNumber *) palloc(maxoff * sizeof(OffsetNumber));
361 17 : left = v->spl_left;
362 17 : v->spl_nleft = 0;
363 17 : right = v->spl_right;
364 17 : v->spl_nright = 0;
365 ECB :
366 : /*
367 : * Emit segments to the left output page, and compute its bounding box.
368 : */
369 GIC 17 : seg_l = (SEG *) palloc(sizeof(SEG));
370 CBC 17 : memcpy(seg_l, sort_items[0].data, sizeof(SEG));
371 17 : *left++ = sort_items[0].index;
372 17 : v->spl_nleft++;
373 2227 : for (i = 1; i < firstright; i++)
374 ECB : {
375 GIC 2210 : Datum sortitem = PointerGetDatum(sort_items[i].data);
376 ECB :
377 GIC 2210 : seg_l = DatumGetSegP(DirectFunctionCall2(seg_union,
378 ECB : PointerGetDatum(seg_l),
379 : sortitem));
380 GIC 2210 : *left++ = sort_items[i].index;
381 CBC 2210 : v->spl_nleft++;
382 ECB : }
383 :
384 : /*
385 : * Likewise for the right page.
386 : */
387 GIC 17 : seg_r = (SEG *) palloc(sizeof(SEG));
388 CBC 17 : memcpy(seg_r, sort_items[firstright].data, sizeof(SEG));
389 17 : *right++ = sort_items[firstright].index;
390 17 : v->spl_nright++;
391 2227 : for (i = firstright + 1; i < maxoff; i++)
392 ECB : {
393 GIC 2210 : Datum sortitem = PointerGetDatum(sort_items[i].data);
394 ECB :
395 GIC 2210 : seg_r = DatumGetSegP(DirectFunctionCall2(seg_union,
396 ECB : PointerGetDatum(seg_r),
397 : sortitem));
398 GIC 2210 : *right++ = sort_items[i].index;
399 CBC 2210 : v->spl_nright++;
400 ECB : }
401 :
402 GIC 17 : v->spl_ldatum = PointerGetDatum(seg_l);
403 CBC 17 : v->spl_rdatum = PointerGetDatum(seg_r);
404 ECB :
405 GIC 17 : PG_RETURN_POINTER(v);
406 ECB : }
407 :
408 : /*
409 : ** Equality methods
410 : */
411 : Datum
412 GIC 2315 : gseg_same(PG_FUNCTION_ARGS)
413 ECB : {
414 GIC 2315 : bool *result = (bool *) PG_GETARG_POINTER(2);
415 ECB :
416 GIC 2315 : if (DirectFunctionCall2(seg_same, PG_GETARG_DATUM(0), PG_GETARG_DATUM(1)))
417 CBC 2286 : *result = true;
418 ECB : else
419 GIC 29 : *result = false;
420 ECB :
421 : #ifdef GIST_DEBUG
422 : fprintf(stderr, "same: %s\n", (*result ? "TRUE" : "FALSE"));
423 : #endif
424 :
425 GIC 2315 : PG_RETURN_POINTER(result);
426 ECB : }
427 :
428 : /*
429 : ** SUPPORT ROUTINES
430 : */
431 : static Datum
432 GIC 5820 : gseg_leaf_consistent(Datum key, Datum query, StrategyNumber strategy)
433 ECB : {
434 : Datum retval;
435 :
436 : #ifdef GIST_QUERY_DEBUG
437 : fprintf(stderr, "leaf_consistent, %d\n", strategy);
438 : #endif
439 :
440 GIC 5820 : switch (strategy)
441 ECB : {
442 UIC 0 : case RTLeftStrategyNumber:
443 UBC 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 GBC 5820 : case RTContainsStrategyNumber:
461 ECB : case RTOldContainsStrategyNumber:
462 GIC 5820 : retval = DirectFunctionCall2(seg_contains, key, query);
463 CBC 5820 : break;
464 LBC 0 : case RTContainedByStrategyNumber:
465 EUB : case RTOldContainedByStrategyNumber:
466 UIC 0 : retval = DirectFunctionCall2(seg_contained, key, query);
467 UBC 0 : break;
468 0 : default:
469 0 : retval = false;
470 EUB : }
471 :
472 GIC 5820 : PG_RETURN_DATUM(retval);
473 ECB : }
474 :
475 : static Datum
476 GIC 72 : gseg_internal_consistent(Datum key, Datum query, StrategyNumber strategy)
477 ECB : {
478 : bool retval;
479 :
480 : #ifdef GIST_QUERY_DEBUG
481 : fprintf(stderr, "internal_consistent, %d\n", strategy);
482 : #endif
483 :
484 GIC 72 : switch (strategy)
485 ECB : {
486 UIC 0 : case RTLeftStrategyNumber:
487 UBC 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 EUB : retval =
496 UIC 0 : DatumGetBool(DirectFunctionCall2(seg_overlap, key, query));
497 UBC 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 GBC 72 : case RTSameStrategyNumber:
507 ECB : case RTContainsStrategyNumber:
508 : case RTOldContainsStrategyNumber:
509 : retval =
510 GIC 72 : DatumGetBool(DirectFunctionCall2(seg_contains, key, query));
511 CBC 72 : break;
512 LBC 0 : case RTContainedByStrategyNumber:
513 EUB : case RTOldContainedByStrategyNumber:
514 : retval =
515 UIC 0 : DatumGetBool(DirectFunctionCall2(seg_overlap, key, query));
516 UBC 0 : break;
517 0 : default:
518 0 : retval = false;
519 EUB : }
520 :
521 GIC 72 : PG_RETURN_BOOL(retval);
522 ECB : }
523 :
524 : static Datum
525 GIC 2316 : gseg_binary_union(Datum r1, Datum r2, int *sizep)
526 ECB : {
527 : Datum retval;
528 :
529 GIC 2316 : retval = DirectFunctionCall2(seg_union, r1, r2);
530 CBC 2316 : *sizep = sizeof(SEG);
531 ECB :
532 GIC 2316 : return retval;
533 ECB : }
534 :
535 :
536 : Datum
537 GIC 5907 : seg_contains(PG_FUNCTION_ARGS)
538 ECB : {
539 GIC 5907 : SEG *a = PG_GETARG_SEG_P(0);
540 CBC 5907 : SEG *b = PG_GETARG_SEG_P(1);
541 ECB :
542 GIC 5907 : PG_RETURN_BOOL((a->lower <= b->lower) && (a->upper >= b->upper));
543 ECB : }
544 :
545 : Datum
546 GIC 14 : seg_contained(PG_FUNCTION_ARGS)
547 ECB : {
548 GIC 14 : Datum a = PG_GETARG_DATUM(0);
549 CBC 14 : Datum b = PG_GETARG_DATUM(1);
550 ECB :
551 GIC 14 : PG_RETURN_DATUM(DirectFunctionCall2(seg_contains, b, a));
552 ECB : }
553 :
554 : /*****************************************************************************
555 : * Operator class for R-tree indexing
556 : *****************************************************************************/
557 :
558 : Datum
559 GIC 2459 : seg_same(PG_FUNCTION_ARGS)
560 ECB : {
561 GIC 2459 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
562 ECB : PG_GETARG_DATUM(0),
563 : PG_GETARG_DATUM(1)));
564 :
565 GIC 2459 : PG_RETURN_BOOL(cmp == 0);
566 ECB : }
567 :
568 : /* seg_overlap -- does a overlap b?
569 : */
570 : Datum
571 GIC 15 : seg_overlap(PG_FUNCTION_ARGS)
572 ECB : {
573 GIC 15 : SEG *a = PG_GETARG_SEG_P(0);
574 CBC 15 : SEG *b = PG_GETARG_SEG_P(1);
575 ECB :
576 GIC 15 : PG_RETURN_BOOL(((a->upper >= b->upper) && (a->lower <= b->upper)) ||
577 ECB : ((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 GIC 11 : seg_over_left(PG_FUNCTION_ARGS)
584 ECB : {
585 GIC 11 : SEG *a = PG_GETARG_SEG_P(0);
586 CBC 11 : SEG *b = PG_GETARG_SEG_P(1);
587 ECB :
588 GIC 11 : PG_RETURN_BOOL(a->upper <= b->upper);
589 ECB : }
590 :
591 : /* seg_left -- is (a) entirely on the left of (b)?
592 : */
593 : Datum
594 GIC 11 : seg_left(PG_FUNCTION_ARGS)
595 ECB : {
596 GIC 11 : SEG *a = PG_GETARG_SEG_P(0);
597 CBC 11 : SEG *b = PG_GETARG_SEG_P(1);
598 ECB :
599 GIC 11 : PG_RETURN_BOOL(a->upper < b->lower);
600 ECB : }
601 :
602 : /* seg_right -- is (a) entirely on the right of (b)?
603 : */
604 : Datum
605 GIC 11 : seg_right(PG_FUNCTION_ARGS)
606 ECB : {
607 GIC 11 : SEG *a = PG_GETARG_SEG_P(0);
608 CBC 11 : SEG *b = PG_GETARG_SEG_P(1);
609 ECB :
610 GIC 11 : PG_RETURN_BOOL(a->lower > b->upper);
611 ECB : }
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 GIC 11 : seg_over_right(PG_FUNCTION_ARGS)
617 ECB : {
618 GIC 11 : SEG *a = PG_GETARG_SEG_P(0);
619 CBC 11 : SEG *b = PG_GETARG_SEG_P(1);
620 ECB :
621 GIC 11 : PG_RETURN_BOOL(a->lower >= b->lower);
622 ECB : }
623 :
624 : Datum
625 GIC 11893 : seg_union(PG_FUNCTION_ARGS)
626 ECB : {
627 GIC 11893 : SEG *a = PG_GETARG_SEG_P(0);
628 CBC 11893 : SEG *b = PG_GETARG_SEG_P(1);
629 ECB : SEG *n;
630 :
631 GIC 11893 : n = (SEG *) palloc(sizeof(*n));
632 ECB :
633 : /* take max of upper endpoints */
634 GIC 11893 : if (a->upper > b->upper)
635 ECB : {
636 GIC 10498 : n->upper = a->upper;
637 CBC 10498 : n->u_sigd = a->u_sigd;
638 10498 : n->u_ext = a->u_ext;
639 ECB : }
640 : else
641 : {
642 GIC 1395 : n->upper = b->upper;
643 CBC 1395 : n->u_sigd = b->u_sigd;
644 1395 : n->u_ext = b->u_ext;
645 ECB : }
646 :
647 : /* take min of lower endpoints */
648 GIC 11893 : if (a->lower < b->lower)
649 ECB : {
650 GIC 11597 : n->lower = a->lower;
651 CBC 11597 : n->l_sigd = a->l_sigd;
652 11597 : n->l_ext = a->l_ext;
653 ECB : }
654 : else
655 : {
656 GIC 296 : n->lower = b->lower;
657 CBC 296 : n->l_sigd = b->l_sigd;
658 296 : n->l_ext = b->l_ext;
659 ECB : }
660 :
661 GIC 11893 : PG_RETURN_POINTER(n);
662 ECB : }
663 :
664 : Datum
665 UIC 0 : seg_inter(PG_FUNCTION_ARGS)
666 EUB : {
667 UIC 0 : SEG *a = PG_GETARG_SEG_P(0);
668 UBC 0 : SEG *b = PG_GETARG_SEG_P(1);
669 EUB : SEG *n;
670 :
671 UIC 0 : n = (SEG *) palloc(sizeof(*n));
672 EUB :
673 : /* take min of upper endpoints */
674 UIC 0 : if (a->upper < b->upper)
675 EUB : {
676 UIC 0 : n->upper = a->upper;
677 UBC 0 : n->u_sigd = a->u_sigd;
678 0 : n->u_ext = a->u_ext;
679 EUB : }
680 : else
681 : {
682 UIC 0 : n->upper = b->upper;
683 UBC 0 : n->u_sigd = b->u_sigd;
684 0 : n->u_ext = b->u_ext;
685 EUB : }
686 :
687 : /* take max of lower endpoints */
688 UIC 0 : if (a->lower > b->lower)
689 EUB : {
690 UIC 0 : n->lower = a->lower;
691 UBC 0 : n->l_sigd = a->l_sigd;
692 0 : n->l_ext = a->l_ext;
693 EUB : }
694 : else
695 : {
696 UIC 0 : n->lower = b->lower;
697 UBC 0 : n->l_sigd = b->l_sigd;
698 0 : n->l_ext = b->l_ext;
699 EUB : }
700 :
701 UIC 0 : PG_RETURN_POINTER(n);
702 EUB : }
703 :
704 : static void
705 GIC 10314 : rt_seg_size(SEG *a, float *size)
706 ECB : {
707 GIC 10314 : if (a == (SEG *) NULL || a->upper <= a->lower)
708 LBC 0 : *size = 0.0;
709 EUB : else
710 GNC 10314 : *size = fabsf(a->upper - a->lower);
711 CBC 10314 : }
712 ECB :
713 : Datum
714 UIC 0 : seg_size(PG_FUNCTION_ARGS)
715 EUB : {
716 UIC 0 : SEG *seg = PG_GETARG_SEG_P(0);
717 EUB :
718 UNC 0 : PG_RETURN_FLOAT4(fabsf(seg->upper - seg->lower));
719 EUB : }
720 :
721 :
722 : /*****************************************************************************
723 : * Miscellaneous operators
724 : *****************************************************************************/
725 : Datum
726 GIC 4433 : seg_cmp(PG_FUNCTION_ARGS)
727 ECB : {
728 GIC 4433 : SEG *a = PG_GETARG_SEG_P(0);
729 CBC 4433 : SEG *b = PG_GETARG_SEG_P(1);
730 ECB :
731 : /*
732 : * First compare on lower boundary position
733 : */
734 GIC 4433 : if (a->lower < b->lower)
735 CBC 904 : PG_RETURN_INT32(-1);
736 3529 : if (a->lower > b->lower)
737 801 : PG_RETURN_INT32(1);
738 ECB :
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 GIC 2728 : if (a->l_ext != b->l_ext)
747 ECB : {
748 GIC 66 : if (a->l_ext == '-')
749 LBC 0 : PG_RETURN_INT32(-1);
750 GBC 66 : if (b->l_ext == '-')
751 LBC 0 : PG_RETURN_INT32(1);
752 GBC 66 : if (a->l_ext == '<')
753 CBC 26 : PG_RETURN_INT32(-1);
754 40 : if (b->l_ext == '<')
755 21 : PG_RETURN_INT32(1);
756 19 : if (a->l_ext == '>')
757 13 : PG_RETURN_INT32(1);
758 6 : if (b->l_ext == '>')
759 6 : PG_RETURN_INT32(-1);
760 ECB : }
761 :
762 : /*
763 : * For other boundary types, consider # of significant digits first.
764 : */
765 GIC 2662 : if (a->l_sigd < b->l_sigd) /* (a) is blurred and is likely to include (b) */
766 CBC 18 : PG_RETURN_INT32(-1);
767 2644 : if (a->l_sigd > b->l_sigd) /* (a) is less blurred and is likely to be
768 ECB : * included in (b) */
769 GIC 18 : PG_RETURN_INT32(1);
770 ECB :
771 : /*
772 : * For same # of digits, an approximate boundary is more blurred than
773 : * exact.
774 : */
775 GIC 2626 : if (a->l_ext != b->l_ext)
776 ECB : {
777 UIC 0 : if (a->l_ext == '~') /* (a) is approximate, while (b) is exact */
778 UBC 0 : PG_RETURN_INT32(-1);
779 0 : if (b->l_ext == '~')
780 0 : PG_RETURN_INT32(1);
781 EUB : /* can't get here unless data is corrupt */
782 UIC 0 : elog(ERROR, "bogus lower boundary types %d %d",
783 EUB : (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 GIC 2626 : if (a->upper < b->upper)
792 CBC 164 : PG_RETURN_INT32(-1);
793 2462 : if (a->upper > b->upper)
794 126 : PG_RETURN_INT32(1);
795 ECB :
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 GIC 2336 : if (a->u_ext != b->u_ext)
804 ECB : {
805 GIC 39 : if (a->u_ext == '-')
806 LBC 0 : PG_RETURN_INT32(1);
807 GBC 39 : if (b->u_ext == '-')
808 LBC 0 : PG_RETURN_INT32(-1);
809 GBC 39 : if (a->u_ext == '<')
810 CBC 3 : PG_RETURN_INT32(-1);
811 36 : if (b->u_ext == '<')
812 1 : PG_RETURN_INT32(1);
813 35 : if (a->u_ext == '>')
814 18 : PG_RETURN_INT32(1);
815 17 : if (b->u_ext == '>')
816 17 : PG_RETURN_INT32(-1);
817 ECB : }
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 GIC 2297 : if (a->u_sigd < b->u_sigd) /* (a) is blurred and is likely to include (b) */
824 CBC 5 : PG_RETURN_INT32(1);
825 2292 : if (a->u_sigd > b->u_sigd) /* (a) is less blurred and is likely to be
826 ECB : * included in (b) */
827 GIC 4 : PG_RETURN_INT32(-1);
828 ECB :
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 GIC 2288 : if (a->u_ext != b->u_ext)
834 ECB : {
835 UIC 0 : if (a->u_ext == '~') /* (a) is approximate, while (b) is exact */
836 UBC 0 : PG_RETURN_INT32(1);
837 0 : if (b->u_ext == '~')
838 0 : PG_RETURN_INT32(-1);
839 EUB : /* can't get here unless data is corrupt */
840 UIC 0 : elog(ERROR, "bogus upper boundary types %d %d",
841 EUB : (int) a->u_ext, (int) b->u_ext);
842 : }
843 :
844 GIC 2288 : PG_RETURN_INT32(0);
845 ECB : }
846 :
847 : Datum
848 UIC 0 : seg_lt(PG_FUNCTION_ARGS)
849 EUB : {
850 UIC 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
851 EUB : PG_GETARG_DATUM(0),
852 : PG_GETARG_DATUM(1)));
853 :
854 UIC 0 : PG_RETURN_BOOL(cmp < 0);
855 EUB : }
856 :
857 : Datum
858 UIC 0 : seg_le(PG_FUNCTION_ARGS)
859 EUB : {
860 UIC 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
861 EUB : PG_GETARG_DATUM(0),
862 : PG_GETARG_DATUM(1)));
863 :
864 UIC 0 : PG_RETURN_BOOL(cmp <= 0);
865 EUB : }
866 :
867 : Datum
868 UIC 0 : seg_gt(PG_FUNCTION_ARGS)
869 EUB : {
870 UIC 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
871 EUB : PG_GETARG_DATUM(0),
872 : PG_GETARG_DATUM(1)));
873 :
874 UIC 0 : PG_RETURN_BOOL(cmp > 0);
875 EUB : }
876 :
877 : Datum
878 UIC 0 : seg_ge(PG_FUNCTION_ARGS)
879 EUB : {
880 UIC 0 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
881 EUB : PG_GETARG_DATUM(0),
882 : PG_GETARG_DATUM(1)));
883 :
884 UIC 0 : PG_RETURN_BOOL(cmp >= 0);
885 EUB : }
886 :
887 :
888 : Datum
889 GIC 2 : seg_different(PG_FUNCTION_ARGS)
890 ECB : {
891 GIC 2 : int cmp = DatumGetInt32(DirectFunctionCall2(seg_cmp,
892 ECB : PG_GETARG_DATUM(0),
893 : PG_GETARG_DATUM(1)));
894 :
895 GIC 2 : PG_RETURN_BOOL(cmp != 0);
896 ECB : }
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 GIC 325 : restore(char *result, float val, int n)
915 ECB : {
916 GIC 325 : char buf[25] = {
917 ECB : '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 GIC 325 : if (n <= 0)
935 LBC 0 : n = FLT_DIG;
936 EUB : else
937 GIC 325 : n = Min(n, FLT_DIG);
938 ECB :
939 : /* remember the sign */
940 GIC 325 : sign = (val < 0 ? 1 : 0);
941 ECB :
942 : /* print, in %e style to start with */
943 GIC 325 : sprintf(result, "%.*e", n - 1, val);
944 ECB :
945 : /* find the exponent */
946 GIC 325 : p = strchr(result, 'e');
947 ECB :
948 : /* punt if we have 'inf' or similar */
949 GIC 325 : if (p == NULL)
950 LBC 0 : return strlen(result);
951 EUB :
952 GIC 325 : exp = atoi(p + 1);
953 CBC 325 : if (exp == 0)
954 ECB : {
955 : /* just truncate off the 'e+00' */
956 GIC 169 : *p = '\0';
957 ECB : }
958 : else
959 : {
960 GNC 156 : if (abs(exp) <= 4)
961 ECB : {
962 : /*
963 : * remove the decimal point from the mantissa and write the digits
964 : * to the buf array
965 : */
966 GIC 637 : for (p = result + sign, i = 10, dp = 0; *p != 'e'; p++, i++)
967 ECB : {
968 GIC 499 : buf[i] = *p;
969 CBC 499 : if (*p == '.')
970 ECB : {
971 GIC 130 : dp = i--; /* skip the decimal point */
972 ECB : }
973 : }
974 GIC 138 : if (dp == 0)
975 CBC 8 : dp = i--; /* no decimal point was found in the above
976 ECB : * for() loop */
977 :
978 GIC 138 : if (exp > 0)
979 ECB : {
980 GIC 133 : if (dp - 10 + exp >= n)
981 ECB : {
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 GIC 43 : exp = dp - 10 + exp - n;
988 CBC 43 : buf[10 + n] = '\0';
989 ECB :
990 : /* insert the decimal point */
991 GIC 43 : if (n > 1)
992 ECB : {
993 GIC 39 : dp = 11;
994 CBC 507 : for (i = 23; i > dp; i--)
995 468 : buf[i] = buf[i - 1];
996 39 : buf[dp] = '.';
997 ECB : }
998 :
999 : /*
1000 : * adjust the exponent by the number of digits after the
1001 : * decimal point
1002 : */
1003 GIC 43 : if (n > 1)
1004 CBC 39 : sprintf(&buf[11 + n], "e%d", exp + n - 1);
1005 ECB : else
1006 GIC 4 : sprintf(&buf[11], "e%d", exp + n - 1);
1007 ECB :
1008 GIC 43 : if (sign)
1009 ECB : {
1010 UIC 0 : buf[9] = '-';
1011 UBC 0 : strcpy(result, &buf[9]);
1012 EUB : }
1013 : else
1014 GIC 43 : strcpy(result, &buf[10]);
1015 ECB : }
1016 : else
1017 : { /* insert the decimal point */
1018 GIC 90 : dp += exp;
1019 CBC 1080 : for (i = 23; i > dp; i--)
1020 990 : buf[i] = buf[i - 1];
1021 90 : buf[11 + n] = '\0';
1022 90 : buf[dp] = '.';
1023 90 : if (sign)
1024 ECB : {
1025 UIC 0 : buf[9] = '-';
1026 UBC 0 : strcpy(result, &buf[9]);
1027 EUB : }
1028 : else
1029 GIC 90 : strcpy(result, &buf[10]);
1030 ECB : }
1031 : }
1032 : else
1033 : { /* exp <= 0 */
1034 GIC 5 : dp += exp - 1;
1035 CBC 5 : buf[10 + n] = '\0';
1036 5 : buf[dp] = '.';
1037 5 : if (sign)
1038 ECB : {
1039 UIC 0 : buf[dp - 2] = '-';
1040 UBC 0 : strcpy(result, &buf[dp - 2]);
1041 EUB : }
1042 : else
1043 GIC 5 : strcpy(result, &buf[dp - 1]);
1044 ECB : }
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 GIC 325 : return strlen(result);
1053 ECB : }
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 GIC 5187 : significant_digits(const char *s)
1065 ECB : {
1066 GIC 5187 : const char *p = s;
1067 ECB : int n,
1068 : c,
1069 : zeroes;
1070 :
1071 GIC 5187 : zeroes = 1;
1072 ECB : /* skip leading zeroes and sign */
1073 GIC 5324 : for (c = *p; (c == '0' || c == '+' || c == '-') && c != 0; c = *(++p));
1074 ECB :
1075 : /* skip decimal point and following zeroes */
1076 GIC 5208 : for (c = *p; (c == '0' || c == '.') && c != 0; c = *(++p))
1077 ECB : {
1078 GIC 21 : if (c != '.')
1079 CBC 11 : zeroes++;
1080 ECB : }
1081 :
1082 : /* count significant digits (n) */
1083 GIC 20346 : for (c = *p, n = 0; c != 0; c = *(++p))
1084 ECB : {
1085 GIC 15186 : if (!((c >= '0' && c <= '9') || (c == '.')))
1086 CBC 27 : break;
1087 15159 : if (c != '.')
1088 10614 : n++;
1089 ECB : }
1090 :
1091 GIC 5187 : if (!n)
1092 CBC 97 : return zeroes;
1093 ECB :
1094 GIC 5090 : return n;
1095 ECB : }
|
