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