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 User Rev File contents
1 kmr 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 kmr 19 Changes for BIOSEG written by Kim Rutherford <kmr@xenu.org.uk>.
11 kmr 1 */
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 kmr 32 #define MIN_LOWER INT_MIN
164 kmr 1 #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 kmr 32 // 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 kmr 1 ereport(ERROR,
213     (errcode(ERRCODE_SYNTAX_ERROR),
214     errmsg("bad bioseg representation"),
215 kmr 44 errdetail("integer %ld at: %s is out of range - must be >= %ld",
216 kmr 32 long_result, *strp, MIN_LOWER)));
217 kmr 1 return 0;
218     }
219    
220     if (long_result > INT_MAX) {
221 kmr 32 // on machines where sizeof(long int) == sizeof(int32) this won't happen
222     // because strtol() will return ERANGE
223 kmr 1 ereport(ERROR,
224     (errcode(ERRCODE_SYNTAX_ERROR),
225     errmsg("bad bioseg representation"),
226 kmr 32 errdetail("integer %ld at: %s is out of range - must be <= %d",
227     long_result, *strp, INT_MAX)));
228 kmr 1 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 kmr 41 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 kmr 44 (long int) lower, MIN_LOWER)));
302 kmr 41 return 0;
303     }
304 kmr 46
305 kmr 1 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 kmr 46 SEG *origrange;
413     SEG *newrange;
414 kmr 1 int32 tmp1;
415     int32 tmp2;
416    
417 kmr 46 origrange = (SEG *) DatumGetPointer(origentry->key);
418     newrange = (SEG *) DatumGetPointer(newentry->key);
419     ud = BIOSEG_PREFIX(_union)(origrange, newrange);
420 kmr 1 BIOSEG_PREFIX(_rt_size)(ud, &tmp1);
421 kmr 46 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 kmr 1
432     #ifdef GIST_DEBUG
433 kmr 46 fprintf(stderr, "Penalty of putting %d..%d into %d..%d is %g\n", newrange->lower, newrange->upper, origrange->lower, origrange->upper, *result);
434 kmr 1 #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 kmr 46 int32 lowest;
452     int32 highest;
453     int32 midpoint;
454     int32 split;
455 kmr 1 int nbytes;
456 kmr 46 int firsttime;
457     long long int midpointsum;
458     int sumcount;
459 kmr 1 OffsetNumber *left;
460     OffsetNumber *right;
461     OffsetNumber maxoff;
462    
463 kmr 46 maxoff = entryvec->n - 1;
464 kmr 1 nbytes = (maxoff + 2) * sizeof(OffsetNumber);
465     v->spl_left = (OffsetNumber *) palloc(nbytes);
466     v->spl_right = (OffsetNumber *) palloc(nbytes);
467    
468 kmr 46 midpointsum = 0;
469     sumcount = 0;
470 kmr 1 firsttime = true;
471 kmr 46 lowest = 0;
472     highest = 0;
473 kmr 1
474 kmr 46 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
475 kmr 1 {
476     datum_alpha = (SEG *) DatumGetPointer(entryvec->vector[i].key);
477 kmr 46 midpoint = datum_alpha->lower + ((datum_alpha->upper - datum_alpha->lower) / 2);
478     midpointsum += midpoint;
479     sumcount++;
480     if (firsttime || (midpoint < lowest))
481 kmr 1 {
482 kmr 46 lowest = midpoint;
483 kmr 1 }
484 kmr 46 if (firsttime || (midpoint > highest))
485     {
486     highest = midpoint;
487     }
488     firsttime = false;
489 kmr 1 }
490    
491 kmr 46 split = midpointsum / sumcount;
492 kmr 1 left = v->spl_left;
493     v->spl_nleft = 0;
494     right = v->spl_right;
495     v->spl_nright = 0;
496    
497 kmr 46 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 kmr 1
504     /*
505 kmr 46 * Now split up the regions between the two seeds.
506 kmr 1 */
507    
508     for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
509     {
510     datum_alpha = (SEG *) DatumGetPointer(entryvec->vector[i].key);
511 kmr 46 midpoint = datum_alpha->lower + ((datum_alpha->upper - datum_alpha->lower) / 2);
512 kmr 1
513     /* pick which page to add it to */
514 kmr 46 if (midpoint <= split)
515 kmr 1 {
516 kmr 46 datum_l = BIOSEG_PREFIX(_union)(datum_l, datum_alpha);
517 kmr 1 *left++ = i;
518     v->spl_nleft++;
519     }
520     else
521     {
522 kmr 46 datum_r = BIOSEG_PREFIX(_union)(datum_r, datum_alpha);
523 kmr 1 *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 kmr 46 #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 kmr 1 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 kmr 46
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 kmr 1 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 kmr 46
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 kmr 1 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 kmr 46 ** These are lower than those in geo_selfuncs.c - found by trail and error.
873 kmr 1 */
874     Datum
875     BIOSEG_PREFIX(_sel)(PG_FUNCTION_ARGS)
876     {
877 kmr 46 PG_RETURN_FLOAT8(2.0e-4);
878 kmr 1 }
879    
880     Datum
881     BIOSEG_PREFIX(_joinsel)(PG_FUNCTION_ARGS)
882     {
883 kmr 46 PG_RETURN_FLOAT8(1.0e-5);
884 kmr 1 }
885    
886     Datum
887     BIOSEG_PREFIX(_contsel)(PG_FUNCTION_ARGS)
888     {
889 kmr 46 PG_RETURN_FLOAT8(1.0e-4);
890 kmr 1 }
891    
892     Datum
893     BIOSEG_PREFIX(_contjoinsel)(PG_FUNCTION_ARGS)
894     {
895 kmr 46 PG_RETURN_FLOAT8(5e-6);
896 kmr 1 }