ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/bioseg/trunk/bioseg.c
Revision: 46
Committed: Wed Apr 22 15:34:48 2009 UTC (10 years, 7 months ago) by kmr
File size: 21847 byte(s)
Log Message:
Performance fixes by Matthew Wakeling.

Line File contents
1 /*
2 This file contains the implementation of the BIOSEG PostgreSQL type. The
3 implementation is a copy of the SEG type from the contrib directory in the
4 PostgreSQL source, which has been changed to represent ranges of integers.
5 The anticipated use of this type is to represent contiguous intervals of a
6 biological sequence.
7
8 SEG code written Gene Selkov, Jr.
9
10 Changes for BIOSEG written by Kim Rutherford <kmr@xenu.org.uk>.
11 */
12
13 #include "postgres.h"
14
15 #include <stdlib.h>
16 #include <errno.h>
17 #include <limits.h>
18
19 #include "access/gist.h"
20 #include "access/skey.h"
21 #include "utils/builtins.h"
22
23 #include "biosegdata.h"
24
25 #ifdef INTERBASE_COORDS
26 #define BIOSEG bioseg0
27 #define BIOSEG_PREFIX(x) bioseg0 ## x
28 #else
29 #define BIOSEG bioseg
30 #define BIOSEG_PREFIX(x) bioseg ## x
31 #endif
32
33 PG_MODULE_MAGIC;
34
35 extern int BIOSEG_PREFIX(_yyparse)();
36 extern void BIOSEG_PREFIX(_yyerror)(const char *message);
37 extern void BIOSEG_PREFIX(_scanner_init)(const char *str);
38 extern void BIOSEG_PREFIX(_scanner_finish)(void);
39
40 /*
41 ** Input/Output routines
42 */
43 SEG *BIOSEG_PREFIX(_in)(char *str);
44 char *BIOSEG_PREFIX(_out)(SEG * seg);
45 SEG *BIOSEG_PREFIX(_create)(int32 lower, int32 upper);
46 int32 BIOSEG_PREFIX(_lower)(SEG * seg);
47 int32 BIOSEG_PREFIX(_upper)(SEG * seg);
48 int32 BIOSEG_PREFIX(_center)(SEG * seg);
49
50 /*
51 ** GiST support methods
52 */
53 bool BIOSEG_PREFIX(_gist_consistent)(GISTENTRY *entry, SEG * query, StrategyNumber strategy);
54 GISTENTRY *BIOSEG_PREFIX(_gist_compress)(GISTENTRY *entry);
55 GISTENTRY *BIOSEG_PREFIX(_gist_decompress)(GISTENTRY *entry);
56 float *BIOSEG_PREFIX(_gist_penalty)(GISTENTRY *origentry, GISTENTRY *newentry, float *result);
57 GIST_SPLITVEC *BIOSEG_PREFIX(_gist_picksplit)(GistEntryVector *entryvec, GIST_SPLITVEC *v);
58 bool BIOSEG_PREFIX(_gist_leaf_consistent)(SEG * key, SEG * query, StrategyNumber strategy);
59 bool BIOSEG_PREFIX(_gist_internal_consistent)(SEG * key, SEG * query, StrategyNumber strategy);
60 SEG *BIOSEG_PREFIX(_gist_union)(GistEntryVector *entryvec, int *sizep);
61 SEG *BIOSEG_PREFIX(_gist_binary_union)(SEG * r1, SEG * r2, int *sizep);
62 bool *BIOSEG_PREFIX(_gist_same)(SEG * b1, SEG * b2, bool *result);
63
64
65 /*
66 ** R-tree support functions
67 */
68 bool BIOSEG_PREFIX(_same)(SEG * a, SEG * b);
69 bool BIOSEG_PREFIX(_contains_int)(SEG * a, int *b);
70 bool BIOSEG_PREFIX(_contains)(SEG * a, SEG * b);
71 bool BIOSEG_PREFIX(_contained)(SEG * a, SEG * b);
72 bool BIOSEG_PREFIX(_overlap)(SEG * a, SEG * b);
73 bool BIOSEG_PREFIX(_left)(SEG * a, SEG * b);
74 bool BIOSEG_PREFIX(_over_left)(SEG * a, SEG * b);
75 bool BIOSEG_PREFIX(_right)(SEG * a, SEG * b);
76 bool BIOSEG_PREFIX(_over_right)(SEG * a, SEG * b);
77 void BIOSEG_PREFIX(_rt_size)(SEG * a, int32 *sz);
78 int32 BIOSEG_PREFIX(_size)(SEG * a);
79
80 static SEG *BIOSEG_PREFIX(_union)(SEG * a, SEG * b);
81
82 /*
83 ** Various operators
84 */
85 int32 BIOSEG_PREFIX(_cmp)(SEG * a, SEG * b);
86 bool BIOSEG_PREFIX(_lt)(SEG * a, SEG * b);
87 bool BIOSEG_PREFIX(_le)(SEG * a, SEG * b);
88 bool BIOSEG_PREFIX(_gt)(SEG * a, SEG * b);
89 bool BIOSEG_PREFIX(_ge)(SEG * a, SEG * b);
90 bool BIOSEG_PREFIX(_different)(SEG * a, SEG * b);
91 Datum BIOSEG_PREFIX(_joinsel)(PG_FUNCTION_ARGS);
92 Datum BIOSEG_PREFIX(_sel)(PG_FUNCTION_ARGS);
93 Datum BIOSEG_PREFIX(_contsel)(PG_FUNCTION_ARGS);
94 Datum BIOSEG_PREFIX(_contjoinsel)(PG_FUNCTION_ARGS);
95
96
97 static int get_dots(char **str);
98 static int get_int(char **str, int32 *result);
99
100
101 /*****************************************************************************
102 * Input/Output functions
103 *****************************************************************************/
104
105 int MAX_DIGITS = 10;
106
107 SEG *
108 BIOSEG_PREFIX(_in)(char *str)
109 {
110 int32 lower;
111 int32 upper;
112
113 if (!get_int(&str, &lower)) {
114 return NULL;
115 }
116
117 if (str[0] == 0) {
118 upper = lower;
119 } else {
120 if (!get_dots(&str)) {
121 ereport(ERROR,
122 (errcode(ERRCODE_SYNTAX_ERROR),
123 errmsg("bad bioseg representation"),
124 errdetail("number followed by something other than ..: %s", str)));
125 return NULL;
126 }
127
128 if (!get_int(&str, &upper)) {
129 ereport(ERROR,
130 (errcode(ERRCODE_SYNTAX_ERROR),
131 errmsg("bad bioseg representation"),
132 errdetail("number\"..\" followed by something other than a number: %s", str)));
133 return NULL;
134 }
135
136 if (lower > upper) {
137 ereport(ERROR,
138 (errcode(ERRCODE_SYNTAX_ERROR),
139 errmsg("bad bioseg representation"),
140 errdetail("lower limit of range greater than upper")));
141 return NULL;
142 }
143
144 if (str[0] != 0) {
145 ereport(ERROR,
146 (errcode(ERRCODE_SYNTAX_ERROR),
147 errmsg("bad bioseg representation"),
148 errdetail("garbage at end of string: %s", str)));
149 return NULL;
150 }
151 }
152
153 {
154 SEG *result = palloc(sizeof(SEG));
155
156 result->lower = lower;
157 result->upper = upper;
158 return result;
159 }
160 }
161
162 #ifdef INTERBASE_COORDS
163 #define MIN_LOWER INT_MIN
164 #else
165 #define MIN_LOWER 1l
166 #endif
167
168 int get_int(char **strp, int32 *result) {
169 char *return_pos;
170 long int long_result = -1;
171
172 if (!(*strp)[0]) {
173 ereport(ERROR,
174 (errcode(ERRCODE_SYNTAX_ERROR),
175 errmsg("bad bioseg representation"),
176 errdetail("end of string found when expecting an integer")));
177 return 0;
178 }
179
180 errno = 0;
181
182 long_result = strtol(*strp, &return_pos, 0);
183
184 if (errno == ERANGE && (long_result == LONG_MAX || long_result == LONG_MIN)) {
185 ereport(ERROR,
186 (errcode(ERRCODE_SYNTAX_ERROR),
187 errmsg("bad bioseg representation"),
188 errdetail("integer at: %s is out of range", *strp)));
189 return 0;
190 }
191
192 if (errno != 0 && long_result == 0) {
193 ereport(ERROR,
194 (errcode(ERRCODE_SYNTAX_ERROR),
195 errmsg("bad bioseg representation"),
196 errdetail("unable to read an integer: %s", strerror(errno))));
197 return 0;
198 }
199
200 if (*strp == return_pos) {
201 ereport(ERROR,
202 (errcode(ERRCODE_SYNTAX_ERROR),
203 errmsg("bad bioseg representation"),
204 errdetail("no integer found at: %s", *strp)));
205 return 0;
206 }
207
208 if (long_result < MIN_LOWER) {
209 // when INTERBASE_COORDS is set, on machines where
210 // sizeof(long int) == sizeof(int32) this block won't be executed because
211 // strtol() will return ERANGE
212 ereport(ERROR,
213 (errcode(ERRCODE_SYNTAX_ERROR),
214 errmsg("bad bioseg representation"),
215 errdetail("integer %ld at: %s is out of range - must be >= %ld",
216 long_result, *strp, MIN_LOWER)));
217 return 0;
218 }
219
220 if (long_result > INT_MAX) {
221 // on machines where sizeof(long int) == sizeof(int32) this won't happen
222 // because strtol() will return ERANGE
223 ereport(ERROR,
224 (errcode(ERRCODE_SYNTAX_ERROR),
225 errmsg("bad bioseg representation"),
226 errdetail("integer %ld at: %s is out of range - must be <= %d",
227 long_result, *strp, INT_MAX)));
228 return 0;
229 }
230
231 *strp = return_pos;
232 *result = long_result;
233
234 return 1;
235 }
236
237 int
238 get_dots(char **strp)
239 {
240 if ((*strp)[0] == '.') {
241 (*strp)++;
242 if ((*strp)[0] == '.') {
243 (*strp)++;
244 if ((*strp)[0] == '.') {
245 // allow for "10...20"
246 (*strp)++;
247 }
248 return 1;
249 } else {
250 return 0;
251 }
252 } else {
253 return 0;
254 }
255 }
256
257 char *
258 BIOSEG_PREFIX(_out)(SEG * bioseg)
259 {
260 char *result;
261 char *p;
262
263 if (bioseg == NULL)
264 return (NULL);
265
266 p = result = (char *) palloc(40);
267
268 if (bioseg->lower == bioseg->upper)
269 {
270 /*
271 * indicates that this interval was built by bioseg_in off a single point
272 */
273 sprintf(p, "%d", bioseg->lower);
274 }
275 else
276 {
277 sprintf(p, "%d..%d", bioseg->lower, bioseg->upper);
278 }
279
280 return (result);
281 }
282
283 SEG *
284 BIOSEG_PREFIX(_create)(int32 lower, int32 upper)
285 {
286 SEG *result = palloc(sizeof(SEG));
287
288 if (lower > upper) {
289 ereport(ERROR,
290 (errcode(ERRCODE_SYNTAX_ERROR),
291 errmsg("bad bioseg representation"),
292 errdetail("lower limit of range greater than upper")));
293 return NULL;
294 }
295
296 if (lower < MIN_LOWER) {
297 ereport(ERROR,
298 (errcode(ERRCODE_SYNTAX_ERROR),
299 errmsg("bad bioseg representation"),
300 errdetail("lower bound (%ld) must be >= %ld",
301 (long int) lower, MIN_LOWER)));
302 return 0;
303 }
304
305 result->lower = lower;
306 result->upper = upper;
307
308 return result;
309 }
310
311
312
313 int32
314 BIOSEG_PREFIX(_center)(SEG * bioseg)
315 {
316 return ((int32) bioseg->lower + (int32) bioseg->upper) / 2;
317 }
318
319 int32
320 BIOSEG_PREFIX(_lower)(SEG * bioseg)
321 {
322 return bioseg->lower;
323 }
324
325 int32
326 BIOSEG_PREFIX(_upper)(SEG * bioseg)
327 {
328 return bioseg->upper;
329 }
330
331
332 /*****************************************************************************
333 * GiST functions
334 *****************************************************************************/
335
336 /*
337 ** The GiST Consistent method for biosegments
338 ** Should return false if for all data items x below entry,
339 ** the predicate x op query == FALSE, where op is the oper
340 ** corresponding to strategy in the pg_amop table.
341 */
342 bool
343 BIOSEG_PREFIX(_gist_consistent)(GISTENTRY *entry,
344 SEG * query,
345 StrategyNumber strategy)
346 {
347 /*
348 * if entry is not leaf, use bioseg_gist_internal_consistent, else use
349 * bioseg_gist_leaf_consistent
350 */
351 if (GIST_LEAF(entry))
352 return (BIOSEG_PREFIX(_gist_leaf_consistent)((SEG *) DatumGetPointer(entry->key), query, strategy));
353 else
354 return (BIOSEG_PREFIX(_gist_internal_consistent)((SEG *) DatumGetPointer(entry->key), query, strategy));
355 }
356
357 /*
358 ** The GiST Union method for biosegments
359 ** returns the minimal bounding bioseg that encloses all the entries in entryvec
360 */
361 SEG *
362 BIOSEG_PREFIX(_gist_union)(GistEntryVector *entryvec, int *sizep)
363 {
364 int numranges;
365 int i;
366 SEG *out = (SEG *) NULL;
367 SEG *tmp;
368
369 #ifdef GIST_DEBUG
370 fprintf(stderr, "union\n");
371 #endif
372
373 numranges = entryvec->n;
374 tmp = (SEG *) DatumGetPointer(entryvec->vector[0].key);
375 *sizep = sizeof(SEG);
376
377 for (i = 1; i < numranges; i++)
378 {
379 out = BIOSEG_PREFIX(_gist_binary_union)(tmp, (SEG *)
380 DatumGetPointer(entryvec->vector[i].key),
381 sizep);
382 tmp = out;
383 }
384
385 return (out);
386 }
387
388 /*
389 ** GiST Compress and Decompress methods for biosegments
390 ** do not do anything.
391 */
392 GISTENTRY *
393 BIOSEG_PREFIX(_gist_compress)(GISTENTRY *entry)
394 {
395 return (entry);
396 }
397
398 GISTENTRY *
399 BIOSEG_PREFIX(_gist_decompress)(GISTENTRY *entry)
400 {
401 return (entry);
402 }
403
404 /*
405 ** The GiST Penalty method for biosegments
406 ** As in the R-tree paper, we use change in area as our penalty metric
407 */
408 float *
409 BIOSEG_PREFIX(_gist_penalty)(GISTENTRY *origentry, GISTENTRY *newentry, float *result)
410 {
411 SEG *ud;
412 SEG *origrange;
413 SEG *newrange;
414 int32 tmp1;
415 int32 tmp2;
416
417 origrange = (SEG *) DatumGetPointer(origentry->key);
418 newrange = (SEG *) DatumGetPointer(newentry->key);
419 ud = BIOSEG_PREFIX(_union)(origrange, newrange);
420 BIOSEG_PREFIX(_rt_size)(ud, &tmp1);
421 BIOSEG_PREFIX(_rt_size)(origrange, &tmp2);
422 if (tmp1 == tmp2)
423 {
424 BIOSEG_PREFIX(_rt_size)(newrange, &tmp1);
425 *result = ((tmp2 - tmp1) * 100000.0) / tmp2;
426 }
427 else
428 {
429 *result = tmp1 - tmp2 + 100000.0;
430 }
431
432 #ifdef GIST_DEBUG
433 fprintf(stderr, "Penalty of putting %d..%d into %d..%d is %g\n", newrange->lower, newrange->upper, origrange->lower, origrange->upper, *result);
434 #endif
435
436 return (result);
437 }
438
439
440 /*
441 ** The GiST PickSplit method for segments
442 */
443 GIST_SPLITVEC *
444 BIOSEG_PREFIX(_gist_picksplit)(GistEntryVector *entryvec,
445 GIST_SPLITVEC *v)
446 {
447 OffsetNumber i;
448 SEG *datum_alpha;
449 SEG *datum_l;
450 SEG *datum_r;
451 int32 lowest;
452 int32 highest;
453 int32 midpoint;
454 int32 split;
455 int nbytes;
456 int firsttime;
457 long long int midpointsum;
458 int sumcount;
459 OffsetNumber *left;
460 OffsetNumber *right;
461 OffsetNumber maxoff;
462
463 maxoff = entryvec->n - 1;
464 nbytes = (maxoff + 2) * sizeof(OffsetNumber);
465 v->spl_left = (OffsetNumber *) palloc(nbytes);
466 v->spl_right = (OffsetNumber *) palloc(nbytes);
467
468 midpointsum = 0;
469 sumcount = 0;
470 firsttime = true;
471 lowest = 0;
472 highest = 0;
473
474 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
475 {
476 datum_alpha = (SEG *) DatumGetPointer(entryvec->vector[i].key);
477 midpoint = datum_alpha->lower + ((datum_alpha->upper - datum_alpha->lower) / 2);
478 midpointsum += midpoint;
479 sumcount++;
480 if (firsttime || (midpoint < lowest))
481 {
482 lowest = midpoint;
483 }
484 if (firsttime || (midpoint > highest))
485 {
486 highest = midpoint;
487 }
488 firsttime = false;
489 }
490
491 split = midpointsum / sumcount;
492 left = v->spl_left;
493 v->spl_nleft = 0;
494 right = v->spl_right;
495 v->spl_nright = 0;
496
497 datum_l = (SEG *) palloc(sizeof(*datum_l));
498 datum_l->lower = lowest;
499 datum_l->upper = lowest;
500 datum_r = (SEG *) palloc(sizeof(*datum_r));
501 datum_r->lower = highest;
502 datum_r->upper = highest;
503
504 /*
505 * Now split up the regions between the two seeds.
506 */
507
508 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
509 {
510 datum_alpha = (SEG *) DatumGetPointer(entryvec->vector[i].key);
511 midpoint = datum_alpha->lower + ((datum_alpha->upper - datum_alpha->lower) / 2);
512
513 /* pick which page to add it to */
514 if (midpoint <= split)
515 {
516 datum_l = BIOSEG_PREFIX(_union)(datum_l, datum_alpha);
517 *left++ = i;
518 v->spl_nleft++;
519 }
520 else
521 {
522 datum_r = BIOSEG_PREFIX(_union)(datum_r, datum_alpha);
523 *right++ = i;
524 v->spl_nright++;
525 }
526 }
527 *left = *right = FirstOffsetNumber; /* sentinel value, see dosplit() */
528
529 v->spl_ldatum = PointerGetDatum(datum_l);
530 v->spl_rdatum = PointerGetDatum(datum_r);
531
532 #ifdef GIST_DEBUG
533 fprintf(stderr, "Picksplit summary to %d..%d (%d locations) and %d..%d (%d locations), with pivot %d\n", datum_l->lower, datum_l->upper, v->spl_nleft,
534 datum_r->lower, datum_r->upper, v->spl_nright, split);
535 #endif
536
537 return v;
538 }
539
540 /*
541 ** Equality methods
542 */
543 bool *
544 BIOSEG_PREFIX(_gist_same)(SEG * b1, SEG * b2, bool *result)
545 {
546 if (BIOSEG_PREFIX(_same)(b1, b2))
547 *result = TRUE;
548 else
549 *result = FALSE;
550
551 #ifdef GIST_DEBUG
552 fprintf(stderr, "same: %s\n", (*result ? "TRUE" : "FALSE"));
553 #endif
554
555 return (result);
556 }
557
558 /*
559 ** SUPPORT ROUTINES
560 */
561 bool
562 BIOSEG_PREFIX(_gist_leaf_consistent)(SEG * key,
563 SEG * query,
564 StrategyNumber strategy)
565 {
566 bool retval;
567
568 switch (strategy)
569 {
570 case RTLeftStrategyNumber:
571 retval = (bool) BIOSEG_PREFIX(_left)(key, query);
572 break;
573 case RTOverLeftStrategyNumber:
574 retval = (bool) BIOSEG_PREFIX(_over_left)(key, query);
575 break;
576 case RTOverlapStrategyNumber:
577 retval = (bool) BIOSEG_PREFIX(_overlap)(key, query);
578 break;
579 case RTOverRightStrategyNumber:
580 retval = (bool) BIOSEG_PREFIX(_over_right)(key, query);
581 break;
582 case RTRightStrategyNumber:
583 retval = (bool) BIOSEG_PREFIX(_right)(key, query);
584 break;
585 case RTSameStrategyNumber:
586 retval = (bool) BIOSEG_PREFIX(_same)(key, query);
587 break;
588 case RTContainsStrategyNumber:
589 case RTOldContainsStrategyNumber:
590 retval = (bool) BIOSEG_PREFIX(_contains)(key, query);
591 break;
592 case RTContainedByStrategyNumber:
593 case RTOldContainedByStrategyNumber:
594 retval = (bool) BIOSEG_PREFIX(_contained)(key, query);
595 break;
596 default:
597 retval = FALSE;
598 }
599
600 #ifdef GIST_QUERY_DEBUG
601 if (retval)
602 {
603 fprintf(stderr, "leaf_consistent, %d..%d %d %d..%d matches\n", query->lower, query->upper, strategy, key->lower, key->upper);
604 }
605 else
606 {
607 fprintf(stderr, "leaf_consistent, %d..%d %d %d..%d\n", query->lower, query->upper, strategy, key->lower, key->upper);
608 }
609 #endif
610
611 return (retval);
612 }
613
614 bool
615 BIOSEG_PREFIX(_gist_internal_consistent)(SEG * key,
616 SEG * query,
617 StrategyNumber strategy)
618 {
619 bool retval;
620
621 switch (strategy)
622 {
623 case RTLeftStrategyNumber:
624 retval = (bool) !BIOSEG_PREFIX(_over_right)(key, query);
625 break;
626 case RTOverLeftStrategyNumber:
627 retval = (bool) !BIOSEG_PREFIX(_right)(key, query);
628 break;
629 case RTOverlapStrategyNumber:
630 retval = (bool) BIOSEG_PREFIX(_overlap)(key, query);
631 break;
632 case RTOverRightStrategyNumber:
633 retval = (bool) !BIOSEG_PREFIX(_left)(key, query);
634 break;
635 case RTRightStrategyNumber:
636 retval = (bool) !BIOSEG_PREFIX(_over_left)(key, query);
637 break;
638 case RTSameStrategyNumber:
639 case RTContainsStrategyNumber:
640 case RTOldContainsStrategyNumber:
641 retval = (bool) BIOSEG_PREFIX(_contains)(key, query);
642 break;
643 case RTContainedByStrategyNumber:
644 case RTOldContainedByStrategyNumber:
645 retval = (bool) BIOSEG_PREFIX(_overlap)(key, query);
646 break;
647 default:
648 retval = FALSE;
649 }
650
651 #ifdef GIST_QUERY_DEBUG
652 if (retval)
653 {
654 fprintf(stderr, "internal_consistent, %d..%d %d %d..%d matches\n", query->lower, query->upper, strategy, key->lower, key->upper);
655 }
656 else
657 {
658 fprintf(stderr, "internal_consistent, %d..%d %d %d..%d\n", query->lower, query->upper, strategy, key->lower, key->upper);
659 }
660 #endif
661
662 return (retval);
663 }
664
665 SEG *
666 BIOSEG_PREFIX(_gist_binary_union)(SEG * r1, SEG * r2, int *sizep)
667 {
668 SEG *retval;
669
670 retval = BIOSEG_PREFIX(_union)(r1, r2);
671 *sizep = sizeof(SEG);
672
673 return (retval);
674 }
675
676
677 bool
678 BIOSEG_PREFIX(_contains)(SEG * a, SEG * b)
679 {
680 #ifdef INTERBASE_COORDS
681 return ((a->lower <= b->lower) && (a->upper >= b->upper) &&
682 a->lower != b->upper && a->upper != b->lower);
683 #else
684 return ((a->lower <= b->lower) && (a->upper >= b->upper));
685 #endif
686 }
687
688 bool
689 BIOSEG_PREFIX(_contained)(SEG * a, SEG * b)
690 {
691 return (BIOSEG_PREFIX(_contains)(b, a));
692 }
693
694 /*****************************************************************************
695 * Operator class for R-tree indexing
696 *****************************************************************************/
697
698 bool
699 BIOSEG_PREFIX(_same)(SEG * a, SEG * b)
700 {
701 return BIOSEG_PREFIX(_cmp)(a, b) == 0;
702 }
703
704 /* bioseg_overlap -- does a overlap b?
705 */
706 bool
707 BIOSEG_PREFIX(_overlap)(SEG * a, SEG * b)
708 {
709 #ifdef INTERBASE_COORDS
710 return (
711 ((a->upper >= b->upper) && (a->lower < b->upper) &&
712 b->lower != a->upper)
713 ||
714 ((b->upper >= a->upper) && (b->lower < a->upper) &&
715 a->lower != b->upper)
716 );
717 #else
718 return
719 ((a->upper >= b->upper) && (a->lower <= b->upper))
720 ||
721 ((b->upper >= a->upper) && (b->lower <= a->upper));
722 #endif
723 }
724
725 /* bioseg_overleft -- is the right edge of (a) located at or left of the right edge of (b)?
726 */
727 bool
728 BIOSEG_PREFIX(_over_left)(SEG * a, SEG * b)
729 {
730 return (a->upper <= b->upper);
731 }
732
733 /* bioseg_left -- is (a) entirely on the left of (b)?
734 */
735 bool
736 BIOSEG_PREFIX(_left)(SEG * a, SEG * b)
737 {
738 return (a->upper < b->lower);
739 }
740
741 /* bioseg_right -- is (a) entirely on the right of (b)?
742 */
743 bool
744 BIOSEG_PREFIX(_right)(SEG * a, SEG * b)
745 {
746 return (a->lower > b->upper);
747 }
748
749 /* bioseg_overright -- is the left edge of (a) located at or right of the left edge of (b)?
750 */
751 bool
752 BIOSEG_PREFIX(_over_right)(SEG * a, SEG * b)
753 {
754 return (a->lower >= b->lower);
755 }
756
757
758 static SEG *
759 BIOSEG_PREFIX(_union)(SEG * a, SEG * b)
760 {
761 SEG *n;
762
763 n = (SEG *) palloc(sizeof(*n));
764
765 /* take max of upper endpoints */
766 if (a->upper > b->upper)
767 {
768 n->upper = a->upper;
769 }
770 else
771 {
772 n->upper = b->upper;
773 }
774
775 /* take min of lower endpoints */
776 if (a->lower < b->lower)
777 {
778 n->lower = a->lower;
779 }
780 else
781 {
782 n->lower = b->lower;
783 }
784
785 return (n);
786 }
787
788 void
789 BIOSEG_PREFIX(_rt_size)(SEG * a, int32 *size)
790 {
791 if (a == (SEG *) NULL)
792 *size = 0;
793 else
794 #ifdef INTERBASE_COORDS
795 *size = (int32) (a->upper - a->lower);
796 #else
797 *size = (int32) (a->upper - a->lower + 1);
798 #endif
799 }
800
801 int32
802 BIOSEG_PREFIX(_size)(SEG * a)
803 {
804 #ifdef INTERBASE_COORDS
805 return a->upper - a->lower;
806 #else
807 return a->upper - a->lower + 1;
808 #endif
809 }
810
811
812 /*****************************************************************************
813 * Miscellaneous operators
814 *****************************************************************************/
815 int32
816 BIOSEG_PREFIX(_cmp)(SEG * a, SEG * b)
817 {
818 if (a->lower < b->lower)
819 return -1;
820 if (a->lower > b->lower)
821 return 1;
822
823 if (a->upper < b->upper)
824 return -1;
825 if (a->upper > b->upper)
826 return 1;
827
828 return 0;
829 }
830
831 bool
832 BIOSEG_PREFIX(_lt)(SEG * a, SEG * b)
833 {
834 return BIOSEG_PREFIX(_cmp)(a, b) < 0;
835 }
836
837 bool
838 BIOSEG_PREFIX(_le)(SEG * a, SEG * b)
839 {
840 return BIOSEG_PREFIX(_cmp)(a, b) <= 0;
841 }
842
843 bool
844 BIOSEG_PREFIX(_gt)(SEG * a, SEG * b)
845 {
846 return BIOSEG_PREFIX(_cmp)(a, b) > 0;
847 }
848
849 bool
850 BIOSEG_PREFIX(_ge)(SEG * a, SEG * b)
851 {
852 return BIOSEG_PREFIX(_cmp)(a, b) >= 0;
853 }
854
855 bool
856 BIOSEG_PREFIX(_different)(SEG * a, SEG * b)
857 {
858 return BIOSEG_PREFIX(_cmp)(a, b) != 0;
859 }
860
861 bool
862 BIOSEG_PREFIX(_contains_int)(SEG * a, int *b)
863 {
864 #ifdef INTERBASE_COORDS
865 return ((a->lower < *b) && (a->upper > *b));
866 #else
867 return ((a->lower <= *b) && (a->upper >= *b));
868 #endif
869 }
870
871 /*
872 ** These are lower than those in geo_selfuncs.c - found by trail and error.
873 */
874 Datum
875 BIOSEG_PREFIX(_sel)(PG_FUNCTION_ARGS)
876 {
877 PG_RETURN_FLOAT8(2.0e-4);
878 }
879
880 Datum
881 BIOSEG_PREFIX(_joinsel)(PG_FUNCTION_ARGS)
882 {
883 PG_RETURN_FLOAT8(1.0e-5);
884 }
885
886 Datum
887 BIOSEG_PREFIX(_contsel)(PG_FUNCTION_ARGS)
888 {
889 PG_RETURN_FLOAT8(1.0e-4);
890 }
891
892 Datum
893 BIOSEG_PREFIX(_contjoinsel)(PG_FUNCTION_ARGS)
894 {
895 PG_RETURN_FLOAT8(5e-6);
896 }