ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/bioseg/trunk/bioseg.c
Revision: 40
Committed: Thu Aug 21 23:25:50 2008 UTC (11 years, 3 months ago) by kmr
File size: 23220 byte(s)
Log Message:
Comment fix.

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