aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--contrib/intarray/_int.h175
-rw-r--r--contrib/intarray/_int_bool.c735
-rw-r--r--contrib/intarray/_int_gist.c504
-rw-r--r--contrib/intarray/_int_op.c444
-rw-r--r--contrib/intarray/_int_tool.c370
-rw-r--r--contrib/intarray/_intbig_gist.c522
6 files changed, 2750 insertions, 0 deletions
diff --git a/contrib/intarray/_int.h b/contrib/intarray/_int.h
new file mode 100644
index 00000000000..102d9b7903b
--- /dev/null
+++ b/contrib/intarray/_int.h
@@ -0,0 +1,175 @@
+#include "postgres.h"
+
+#include <float.h>
+
+#include "access/gist.h"
+#include "access/itup.h"
+#include "access/rtree.h"
+#include "catalog/pg_type.h"
+#include "utils/elog.h"
+#include "utils/palloc.h"
+#include "utils/array.h"
+#include "utils/builtins.h"
+#include "storage/bufpage.h"
+#include "lib/stringinfo.h"
+
+/* number ranges for compression */
+#define MAXNUMRANGE 100
+
+#define max(a,b) ((a) > (b) ? (a) : (b))
+#define min(a,b) ((a) <= (b) ? (a) : (b))
+#define abs(a) ((a) < (0) ? -(a) : (a))
+
+/* dimension of array */
+#define NDIM 1
+
+/*
+ * flags for gist__int_ops, use ArrayType->flags
+ * which is unused (see array.h)
+ */
+#define LEAFKEY (1<<31)
+#define ISLEAFKEY(x) ( ((ArrayType*)(x))->flags & LEAFKEY )
+
+/* useful macros for accessing int4 arrays */
+#define ARRPTR(x) ( (int4 *) ARR_DATA_PTR(x) )
+#define ARRNELEMS(x) ArrayGetNItems( ARR_NDIM(x), ARR_DIMS(x))
+
+#define ARRISVOID(x) ( (x) ? ( ( ARR_NDIM(x) == NDIM ) ? ( ( ARRNELEMS( x ) ) ? 0 : 1 ) : ( ( ARR_NDIM(x) ) ? (elog(ERROR,"Array is not one-dimensional: %d dimensions",ARRNELEMS( x )),1) : 0 ) ) : 0 )
+
+#define SORT(x) \
+ do { \
+ if ( ARRNELEMS( x ) > 1 ) \
+ isort( ARRPTR( x ), ARRNELEMS( x ) ); \
+ } while(0)
+
+#define PREPAREARR(x) \
+ do { \
+ if ( ARRNELEMS( x ) > 1 ) \
+ if ( isort( ARRPTR( x ), ARRNELEMS( x ) ) ) \
+ x = _int_unique( x ); \
+ } while(0)
+
+/* "wish" function */
+#define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
+
+
+/* bigint defines */
+#define BITBYTE 8
+#define SIGLENINT 63 /* >122 => key will toast, so very slow!!! */
+#define SIGLEN ( sizeof(int)*SIGLENINT )
+#define SIGLENBIT (SIGLEN*BITBYTE)
+
+typedef char BITVEC[SIGLEN];
+typedef char *BITVECP;
+
+#define SIGPTR(x) ( (BITVECP) ARR_DATA_PTR(x) )
+
+
+#define LOOPBYTE(a) \
+ for(i=0;i<SIGLEN;i++) {\
+ a;\
+ }
+
+#define LOOPBIT(a) \
+ for(i=0;i<SIGLENBIT;i++) {\
+ a;\
+ }
+
+/* beware of multiple evaluation of arguments to these macros! */
+#define GETBYTE(x,i) ( *( (BITVECP)(x) + (int)( (i) / BITBYTE ) ) )
+#define GETBITBYTE(x,i) ( (*((char*)(x)) >> (i)) & 0x01 )
+#define CLRBIT(x,i) GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITBYTE ) )
+#define SETBIT(x,i) GETBYTE(x,i) |= ( 0x01 << ( (i) % BITBYTE ) )
+#define GETBIT(x,i) ( (GETBYTE(x,i) >> ( (i) % BITBYTE )) & 0x01 )
+#define HASHVAL(val) (((unsigned int)(val)) % SIGLENBIT)
+#define HASH(sign, val) SETBIT((sign), HASHVAL(val))
+
+/*
+ * type of index key
+ */
+typedef struct
+{
+ int4 len;
+ int4 flag;
+ char data[1];
+} GISTTYPE;
+
+#define ALLISTRUE 0x04
+
+#define ISALLTRUE(x) ( ((GISTTYPE*)x)->flag & ALLISTRUE )
+
+#define GTHDRSIZE ( sizeof(int4)*2 )
+#define CALCGTSIZE(flag) ( GTHDRSIZE+(((flag) & ALLISTRUE) ? 0 : SIGLEN) )
+
+#define GETSIGN(x) ( (BITVECP)( (char*)x+GTHDRSIZE ) )
+
+/*
+** types for functions
+*/
+typedef ArrayType *(*formarray) (ArrayType *, ArrayType *);
+typedef void (*formfloat) (ArrayType *, float *);
+
+/*
+** useful function
+*/
+bool isort(int4 *a, const int len);
+ArrayType *new_intArrayType(int num);
+ArrayType *copy_intArrayType(ArrayType *a);
+ArrayType *resize_intArrayType(ArrayType *a, int num);
+int internal_size(int *a, int len);
+ArrayType *_int_unique(ArrayType *a);
+int32 intarray_match_first(ArrayType *a, int32 elem);
+ArrayType *intarray_add_elem(ArrayType *a, int32 elem);
+ArrayType *intarray_concat_arrays(ArrayType *a, ArrayType *b);
+ArrayType *int_to_intset(int32 elem);
+bool inner_int_overlap(ArrayType *a, ArrayType *b);
+bool inner_int_contains(ArrayType *a, ArrayType *b);
+ArrayType * inner_int_union(ArrayType *a, ArrayType *b);
+ArrayType * inner_int_inter(ArrayType *a, ArrayType *b);
+void rt__int_size(ArrayType *a, float *size);
+void gensign(BITVEC sign, int *a, int len);
+
+
+/*****************************************************************************
+ * Boolean Search
+ *****************************************************************************/
+
+#define BooleanSearchStrategy 20
+
+/*
+ * item in polish notation with back link
+ * to left operand
+ */
+typedef struct ITEM
+{
+ int2 type;
+ int2 left;
+ int4 val;
+} ITEM;
+
+typedef struct
+{
+ int4 len;
+ int4 size;
+ char data[1];
+} QUERYTYPE;
+
+#define HDRSIZEQT ( 2*sizeof(int4) )
+#define COMPUTESIZE(size) ( HDRSIZEQT + size * sizeof(ITEM) )
+#define GETQUERY(x) (ITEM*)( (char*)(x)+HDRSIZEQT )
+
+bool signconsistent(QUERYTYPE * query, BITVEC sign, bool calcnot);
+bool execconsistent(QUERYTYPE * query, ArrayType *array, bool calcnot);
+
+
+
+int compASC(const void *a, const void *b);
+
+int compDESC(const void *a, const void *b);
+
+#define QSORT(a, direction) \
+if (ARRNELEMS(a) > 1) \
+ qsort((void*)ARRPTR(a), ARRNELEMS(a),sizeof(int4), \
+ (direction) ? compASC : compDESC )
+
+
diff --git a/contrib/intarray/_int_bool.c b/contrib/intarray/_int_bool.c
new file mode 100644
index 00000000000..3e8cfd9342c
--- /dev/null
+++ b/contrib/intarray/_int_bool.c
@@ -0,0 +1,735 @@
+#include "_int.h"
+
+PG_FUNCTION_INFO_V1(bqarr_in);
+PG_FUNCTION_INFO_V1(bqarr_out);
+Datum bqarr_in(PG_FUNCTION_ARGS);
+Datum bqarr_out(PG_FUNCTION_ARGS);
+
+PG_FUNCTION_INFO_V1(boolop);
+Datum boolop(PG_FUNCTION_ARGS);
+
+PG_FUNCTION_INFO_V1(rboolop);
+Datum rboolop(PG_FUNCTION_ARGS);
+
+PG_FUNCTION_INFO_V1(querytree);
+Datum querytree(PG_FUNCTION_ARGS);
+
+
+#define END 0
+#define ERR 1
+#define VAL 2
+#define OPR 3
+#define OPEN 4
+#define CLOSE 5
+
+/* parser's states */
+#define WAITOPERAND 1
+#define WAITENDOPERAND 2
+#define WAITOPERATOR 3
+
+/*
+ * node of query tree, also used
+ * for storing polish notation in parser
+ */
+typedef struct NODE
+{
+ int4 type;
+ int4 val;
+ struct NODE *next;
+} NODE;
+
+typedef struct
+{
+ char *buf;
+ int4 state;
+ int4 count;
+ /* reverse polish notation in list (for temporary usage) */
+ NODE *str;
+ /* number in str */
+ int4 num;
+} WORKSTATE;
+
+/*
+ * get token from query string
+ */
+static int4
+gettoken(WORKSTATE * state, int4 *val)
+{
+ char nnn[16],
+ *curnnn;
+
+ curnnn = nnn;
+ while (1)
+ {
+ switch (state->state)
+ {
+ case WAITOPERAND:
+ curnnn = nnn;
+ if ((*(state->buf) >= '0' && *(state->buf) <= '9') ||
+ *(state->buf) == '-')
+ {
+ state->state = WAITENDOPERAND;
+ *curnnn = *(state->buf);
+ curnnn++;
+ }
+ else if (*(state->buf) == '!')
+ {
+ (state->buf)++;
+ *val = (int4) '!';
+ return OPR;
+ }
+ else if (*(state->buf) == '(')
+ {
+ state->count++;
+ (state->buf)++;
+ return OPEN;
+ }
+ else if (*(state->buf) != ' ')
+ return ERR;
+ break;
+ case WAITENDOPERAND:
+ if (*(state->buf) >= '0' && *(state->buf) <= '9')
+ {
+ *curnnn = *(state->buf);
+ curnnn++;
+ }
+ else
+ {
+ *curnnn = '\0';
+ *val = (int4) atoi(nnn);
+ state->state = WAITOPERATOR;
+ return (state->count && *(state->buf) == '\0')
+ ? ERR : VAL;
+ }
+ break;
+ case WAITOPERATOR:
+ if (*(state->buf) == '&' || *(state->buf) == '|')
+ {
+ state->state = WAITOPERAND;
+ *val = (int4) *(state->buf);
+ (state->buf)++;
+ return OPR;
+ }
+ else if (*(state->buf) == ')')
+ {
+ (state->buf)++;
+ state->count--;
+ return (state->count < 0) ? ERR : CLOSE;
+ }
+ else if (*(state->buf) == '\0')
+ return (state->count) ? ERR : END;
+ else if (*(state->buf) != ' ')
+ return ERR;
+ break;
+ default:
+ return ERR;
+ break;
+ }
+ (state->buf)++;
+ }
+ return END;
+}
+
+/*
+ * push new one in polish notation reverse view
+ */
+static void
+pushquery(WORKSTATE * state, int4 type, int4 val)
+{
+ NODE *tmp = (NODE *) palloc(sizeof(NODE));
+
+ tmp->type = type;
+ tmp->val = val;
+ tmp->next = state->str;
+ state->str = tmp;
+ state->num++;
+}
+
+#define STACKDEPTH 16
+
+/*
+ * make polish notation of query
+ */
+static int4
+makepol(WORKSTATE * state)
+{
+ int4 val,
+ type;
+ int4 stack[STACKDEPTH];
+ int4 lenstack = 0;
+
+ while ((type = gettoken(state, &val)) != END)
+ {
+ switch (type)
+ {
+ case VAL:
+ pushquery(state, type, val);
+ while (lenstack && (stack[lenstack - 1] == (int4) '&' ||
+ stack[lenstack - 1] == (int4) '!'))
+ {
+ lenstack--;
+ pushquery(state, OPR, stack[lenstack]);
+ }
+ break;
+ case OPR:
+ if (lenstack && val == (int4) '|')
+ pushquery(state, OPR, val);
+ else
+ {
+ if (lenstack == STACKDEPTH)
+ elog(ERROR, "Stack too short");
+ stack[lenstack] = val;
+ lenstack++;
+ }
+ break;
+ case OPEN:
+ if (makepol(state) == ERR)
+ return ERR;
+ if (lenstack && (stack[lenstack - 1] == (int4) '&' ||
+ stack[lenstack - 1] == (int4) '!'))
+ {
+ lenstack--;
+ pushquery(state, OPR, stack[lenstack]);
+ }
+ break;
+ case CLOSE:
+ while (lenstack)
+ {
+ lenstack--;
+ pushquery(state, OPR, stack[lenstack]);
+ };
+ return END;
+ break;
+ case ERR:
+ default:
+ elog(ERROR, "Syntax error");
+ return ERR;
+
+ }
+ }
+
+ while (lenstack)
+ {
+ lenstack--;
+ pushquery(state, OPR, stack[lenstack]);
+ };
+ return END;
+}
+
+typedef struct
+{
+ int4 *arrb;
+ int4 *arre;
+} CHKVAL;
+
+/*
+ * is there value 'val' in array or not ?
+ */
+static bool
+checkcondition_arr(void *checkval, int4 val)
+{
+ int4 *StopLow = ((CHKVAL *) checkval)->arrb;
+ int4 *StopHigh = ((CHKVAL *) checkval)->arre;
+ int4 *StopMiddle;
+
+ /* Loop invariant: StopLow <= val < StopHigh */
+
+ while (StopLow < StopHigh)
+ {
+ StopMiddle = StopLow + (StopHigh - StopLow) / 2;
+ if (*StopMiddle == val)
+ return (true);
+ else if (*StopMiddle < val)
+ StopLow = StopMiddle + 1;
+ else
+ StopHigh = StopMiddle;
+ }
+ return false;
+}
+
+static bool
+checkcondition_bit(void *checkval, int4 val)
+{
+ return GETBIT(checkval, HASHVAL(val));
+}
+
+/*
+ * check for boolean condition
+ */
+static bool
+execute(ITEM * curitem, void *checkval, bool calcnot, bool (*chkcond) (void *checkval, int4 val))
+{
+
+ if (curitem->type == VAL)
+ return (*chkcond) (checkval, curitem->val);
+ else if (curitem->val == (int4) '!')
+ {
+ return (calcnot) ?
+ ((execute(curitem - 1, checkval, calcnot, chkcond)) ? false : true)
+ : true;
+ }
+ else if (curitem->val == (int4) '&')
+ {
+ if (execute(curitem + curitem->left, checkval, calcnot, chkcond))
+ return execute(curitem - 1, checkval, calcnot, chkcond);
+ else
+ return false;
+ }
+ else
+ { /* |-operator */
+ if (execute(curitem + curitem->left, checkval, calcnot, chkcond))
+ return true;
+ else
+ return execute(curitem - 1, checkval, calcnot, chkcond);
+ }
+ return false;
+}
+
+/*
+ * signconsistent & execconsistent called by *_consistent
+ */
+bool
+signconsistent(QUERYTYPE * query, BITVEC sign, bool calcnot)
+{
+ return execute(
+ GETQUERY(query) + query->size - 1,
+ (void *) sign, calcnot,
+ checkcondition_bit
+ );
+}
+
+bool
+execconsistent(QUERYTYPE * query, ArrayType *array, bool calcnot)
+{
+ CHKVAL chkval;
+
+ chkval.arrb = ARRPTR(array);
+ chkval.arre = chkval.arrb + ARRNELEMS(array);
+ return execute(
+ GETQUERY(query) + query->size - 1,
+ (void *) &chkval, calcnot,
+ checkcondition_arr
+ );
+}
+
+/*
+ * boolean operations
+ */
+Datum
+rboolop(PG_FUNCTION_ARGS)
+{
+ return DirectFunctionCall2(
+ boolop,
+ PG_GETARG_DATUM(1),
+ PG_GETARG_DATUM(0)
+ );
+}
+
+Datum
+boolop(PG_FUNCTION_ARGS)
+{
+ ArrayType *val = (ArrayType *) PG_DETOAST_DATUM_COPY(PG_GETARG_POINTER(0));
+ QUERYTYPE *query = (QUERYTYPE *) PG_DETOAST_DATUM(PG_GETARG_POINTER(1));
+ CHKVAL chkval;
+ bool result;
+
+ if (ARRISVOID(val))
+ {
+ pfree(val);
+ PG_FREE_IF_COPY(query, 1);
+ PG_RETURN_BOOL(false);
+ }
+
+ PREPAREARR(val);
+ chkval.arrb = ARRPTR(val);
+ chkval.arre = chkval.arrb + ARRNELEMS(val);
+ result = execute(
+ GETQUERY(query) + query->size - 1,
+ &chkval, true,
+ checkcondition_arr
+ );
+ pfree(val);
+
+ PG_FREE_IF_COPY(query, 1);
+ PG_RETURN_BOOL(result);
+}
+
+static void
+findoprnd(ITEM * ptr, int4 *pos)
+{
+#ifdef BS_DEBUG
+ elog(DEBUG3, (ptr[*pos].type == OPR) ?
+ "%d %c" : "%d %d ", *pos, ptr[*pos].val);
+#endif
+ if (ptr[*pos].type == VAL)
+ {
+ ptr[*pos].left = 0;
+ (*pos)--;
+ }
+ else if (ptr[*pos].val == (int4) '!')
+ {
+ ptr[*pos].left = -1;
+ (*pos)--;
+ findoprnd(ptr, pos);
+ }
+ else
+ {
+ ITEM *curitem = &ptr[*pos];
+ int4 tmp = *pos;
+
+ (*pos)--;
+ findoprnd(ptr, pos);
+ curitem->left = *pos - tmp;
+ findoprnd(ptr, pos);
+ }
+}
+
+
+/*
+ * input
+ */
+Datum
+bqarr_in(PG_FUNCTION_ARGS)
+{
+ char *buf = (char *) PG_GETARG_POINTER(0);
+ WORKSTATE state;
+ int4 i;
+ QUERYTYPE *query;
+ int4 commonlen;
+ ITEM *ptr;
+ NODE *tmp;
+ int4 pos = 0;
+
+#ifdef BS_DEBUG
+ StringInfoData pbuf;
+#endif
+
+ state.buf = buf;
+ state.state = WAITOPERAND;
+ state.count = 0;
+ state.num = 0;
+ state.str = NULL;
+
+ /* make polish notation (postfix, but in reverse order) */
+ makepol(&state);
+ if (!state.num)
+ elog(ERROR, "Empty query");
+
+ commonlen = COMPUTESIZE(state.num);
+ query = (QUERYTYPE *) palloc(commonlen);
+ query->len = commonlen;
+ query->size = state.num;
+ ptr = GETQUERY(query);
+
+ for (i = state.num - 1; i >= 0; i--)
+ {
+ ptr[i].type = state.str->type;
+ ptr[i].val = state.str->val;
+ tmp = state.str->next;
+ pfree(state.str);
+ state.str = tmp;
+ }
+
+ pos = query->size - 1;
+ findoprnd(ptr, &pos);
+#ifdef BS_DEBUG
+ initStringInfo(&pbuf);
+ for (i = 0; i < query->size; i++)
+ {
+ if (ptr[i].type == OPR)
+ appendStringInfo(&pbuf, "%c(%d) ", ptr[i].val, ptr[i].left);
+ else
+ appendStringInfo(&pbuf, "%d ", ptr[i].val);
+ }
+ elog(DEBUG3, "POR: %s", pbuf.data);
+ pfree(pbuf.data);
+#endif
+
+ PG_RETURN_POINTER(query);
+}
+
+
+/*
+ * out function
+ */
+typedef struct
+{
+ ITEM *curpol;
+ char *buf;
+ char *cur;
+ int4 buflen;
+} INFIX;
+
+#define RESIZEBUF(inf,addsize) while( ( inf->cur - inf->buf ) + addsize + 1 >= inf->buflen ) { \
+ int4 len = inf->cur - inf->buf; \
+ inf->buflen *= 2; \
+ inf->buf = (char*) repalloc( (void*)inf->buf, inf->buflen ); \
+ inf->cur = inf->buf + len; \
+}
+
+static void
+infix(INFIX * in, bool first)
+{
+ if (in->curpol->type == VAL)
+ {
+ RESIZEBUF(in, 11);
+ sprintf(in->cur, "%d", in->curpol->val);
+ in->cur = strchr(in->cur, '\0');
+ in->curpol--;
+ }
+ else if (in->curpol->val == (int4) '!')
+ {
+ bool isopr = false;
+
+ RESIZEBUF(in, 1);
+ *(in->cur) = '!';
+ in->cur++;
+ *(in->cur) = '\0';
+ in->curpol--;
+ if (in->curpol->type == OPR)
+ {
+ isopr = true;
+ RESIZEBUF(in, 2);
+ sprintf(in->cur, "( ");
+ in->cur = strchr(in->cur, '\0');
+ }
+ infix(in, isopr);
+ if (isopr)
+ {
+ RESIZEBUF(in, 2);
+ sprintf(in->cur, " )");
+ in->cur = strchr(in->cur, '\0');
+ }
+ }
+ else
+ {
+ int4 op = in->curpol->val;
+ INFIX nrm;
+
+ in->curpol--;
+ if (op == (int4) '|' && !first)
+ {
+ RESIZEBUF(in, 2);
+ sprintf(in->cur, "( ");
+ in->cur = strchr(in->cur, '\0');
+ }
+
+ nrm.curpol = in->curpol;
+ nrm.buflen = 16;
+ nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);
+
+ /* get right operand */
+ infix(&nrm, false);
+
+ /* get & print left operand */
+ in->curpol = nrm.curpol;
+ infix(in, false);
+
+ /* print operator & right operand */
+ RESIZEBUF(in, 3 + (nrm.cur - nrm.buf));
+ sprintf(in->cur, " %c %s", op, nrm.buf);
+ in->cur = strchr(in->cur, '\0');
+ pfree(nrm.buf);
+
+ if (op == (int4) '|' && !first)
+ {
+ RESIZEBUF(in, 2);
+ sprintf(in->cur, " )");
+ in->cur = strchr(in->cur, '\0');
+ }
+ }
+}
+
+
+Datum
+bqarr_out(PG_FUNCTION_ARGS)
+{
+ QUERYTYPE *query = (QUERYTYPE *) PG_DETOAST_DATUM(PG_GETARG_POINTER(0));
+ INFIX nrm;
+
+ if (query->size == 0)
+ elog(ERROR, "Empty");
+ nrm.curpol = GETQUERY(query) + query->size - 1;
+ nrm.buflen = 32;
+ nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);
+ *(nrm.cur) = '\0';
+ infix(&nrm, true);
+
+ PG_FREE_IF_COPY(query, 0);
+ PG_RETURN_POINTER(nrm.buf);
+}
+
+static int4
+countdroptree(ITEM * q, int4 pos)
+{
+ if (q[pos].type == VAL)
+ return 1;
+ else if (q[pos].val == (int4) '!')
+ return 1 + countdroptree(q, pos - 1);
+ else
+ return 1 + countdroptree(q, pos - 1) + countdroptree(q, pos + q[pos].left);
+}
+
+/*
+ * common algorithm:
+ * result of all '!' will be = 'true', so
+ * we can modify query tree for clearing
+ */
+static int4
+shorterquery(ITEM * q, int4 len)
+{
+ int4 index,
+ posnot,
+ poscor;
+ bool notisleft = false;
+ int4 drop,
+ i;
+
+ /* out all '!' */
+ do
+ {
+ index = 0;
+ drop = 0;
+ /* find ! */
+ for (posnot = 0; posnot < len; posnot++)
+ if (q[posnot].type == OPR && q[posnot].val == (int4) '!')
+ {
+ index = 1;
+ break;
+ }
+
+ if (posnot == len)
+ return len;
+
+ /* last operator is ! */
+ if (posnot == len - 1)
+ return 0;
+
+ /* find operator for this operand */
+ for (poscor = posnot + 1; poscor < len; poscor++)
+ {
+ if (q[poscor].type == OPR)
+ {
+ if (poscor == posnot + 1)
+ {
+ notisleft = false;
+ break;
+ }
+ else if (q[poscor].left + poscor == posnot)
+ {
+ notisleft = true;
+ break;
+ }
+ }
+ }
+ if (q[poscor].val == (int4) '!')
+ {
+ drop = countdroptree(q, poscor);
+ q[poscor - 1].type = VAL;
+ for (i = poscor + 1; i < len; i++)
+ if (q[i].type == OPR && q[i].left + i <= poscor)
+ q[i].left += drop - 2;
+ memcpy((void *) &q[poscor - drop + 1],
+ (void *) &q[poscor - 1],
+ sizeof(ITEM) * (len - (poscor - 1)));
+ len -= drop - 2;
+ }
+ else if (q[poscor].val == (int4) '|')
+ {
+ drop = countdroptree(q, poscor);
+ q[poscor - 1].type = VAL;
+ q[poscor].val = (int4) '!';
+ q[poscor].left = -1;
+ for (i = poscor + 1; i < len; i++)
+ if (q[i].type == OPR && q[i].left + i < poscor)
+ q[i].left += drop - 2;
+ memcpy((void *) &q[poscor - drop + 1],
+ (void *) &q[poscor - 1],
+ sizeof(ITEM) * (len - (poscor - 1)));
+ len -= drop - 2;
+ }
+ else
+ { /* &-operator */
+ if (
+ (notisleft && q[poscor - 1].type == OPR &&
+ q[poscor - 1].val == (int4) '!') ||
+ (!notisleft && q[poscor + q[poscor].left].type == OPR &&
+ q[poscor + q[poscor].left].val == (int4) '!')
+ )
+ { /* drop subtree */
+ drop = countdroptree(q, poscor);
+ q[poscor - 1].type = VAL;
+ q[poscor].val = (int4) '!';
+ q[poscor].left = -1;
+ for (i = poscor + 1; i < len; i++)
+ if (q[i].type == OPR && q[i].left + i < poscor)
+ q[i].left += drop - 2;
+ memcpy((void *) &q[poscor - drop + 1],
+ (void *) &q[poscor - 1],
+ sizeof(ITEM) * (len - (poscor - 1)));
+ len -= drop - 2;
+ }
+ else
+ { /* drop only operator */
+ int4 subtreepos = (notisleft) ?
+ poscor - 1 : poscor + q[poscor].left;
+ int4 subtreelen = countdroptree(q, subtreepos);
+
+ drop = countdroptree(q, poscor);
+ for (i = poscor + 1; i < len; i++)
+ if (q[i].type == OPR && q[i].left + i < poscor)
+ q[i].left += drop - subtreelen;
+ memcpy((void *) &q[subtreepos + 1],
+ (void *) &q[poscor + 1],
+ sizeof(ITEM) * (len - (poscor - 1)));
+ memcpy((void *) &q[poscor - drop + 1],
+ (void *) &q[subtreepos - subtreelen + 1],
+ sizeof(ITEM) * (len - (drop - subtreelen)));
+ len -= drop - subtreelen;
+ }
+ }
+ } while (index);
+ return len;
+}
+
+
+Datum
+querytree(PG_FUNCTION_ARGS)
+{
+ QUERYTYPE *query = (QUERYTYPE *) PG_DETOAST_DATUM(PG_GETARG_POINTER(0));
+ INFIX nrm;
+ text *res;
+ ITEM *q;
+ int4 len;
+
+ if (query->size == 0)
+ elog(ERROR, "Empty");
+
+ q = (ITEM *) palloc(sizeof(ITEM) * query->size);
+ memcpy((void *) q, GETQUERY(query), sizeof(ITEM) * query->size);
+ len = shorterquery(q, query->size);
+ PG_FREE_IF_COPY(query, 0);
+
+ if (len == 0)
+ {
+ res = (text *) palloc(1 + VARHDRSZ);
+ VARATT_SIZEP(res) = 1 + VARHDRSZ;
+ *((char *) VARDATA(res)) = 'T';
+ }
+ else
+ {
+ nrm.curpol = q + len - 1;
+ nrm.buflen = 32;
+ nrm.cur = nrm.buf = (char *) palloc(sizeof(char) * nrm.buflen);
+ *(nrm.cur) = '\0';
+ infix(&nrm, true);
+
+ res = (text *) palloc(nrm.cur - nrm.buf + VARHDRSZ);
+ VARATT_SIZEP(res) = nrm.cur - nrm.buf + VARHDRSZ;
+ strncpy(VARDATA(res), nrm.buf, nrm.cur - nrm.buf);
+ }
+ pfree(q);
+
+ PG_RETURN_POINTER(res);
+}
+
diff --git a/contrib/intarray/_int_gist.c b/contrib/intarray/_int_gist.c
new file mode 100644
index 00000000000..fa6d502e891
--- /dev/null
+++ b/contrib/intarray/_int_gist.c
@@ -0,0 +1,504 @@
+#include "_int.h"
+
+#define GETENTRY(vec,pos) ((ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(vec))[(pos)].key))
+
+/*
+** GiST support methods
+*/
+PG_FUNCTION_INFO_V1(g_int_consistent);
+PG_FUNCTION_INFO_V1(g_int_compress);
+PG_FUNCTION_INFO_V1(g_int_decompress);
+PG_FUNCTION_INFO_V1(g_int_penalty);
+PG_FUNCTION_INFO_V1(g_int_picksplit);
+PG_FUNCTION_INFO_V1(g_int_union);
+PG_FUNCTION_INFO_V1(g_int_same);
+
+Datum g_int_consistent(PG_FUNCTION_ARGS);
+Datum g_int_compress(PG_FUNCTION_ARGS);
+Datum g_int_decompress(PG_FUNCTION_ARGS);
+Datum g_int_penalty(PG_FUNCTION_ARGS);
+Datum g_int_picksplit(PG_FUNCTION_ARGS);
+Datum g_int_union(PG_FUNCTION_ARGS);
+Datum g_int_same(PG_FUNCTION_ARGS);
+
+
+/*
+** The GiST Consistent method for _intments
+** Should return false if for all data items x below entry,
+** the predicate x op query == FALSE, where op is the oper
+** corresponding to strategy in the pg_amop table.
+*/
+Datum
+g_int_consistent(PG_FUNCTION_ARGS)
+{
+ GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
+ ArrayType *query = (ArrayType *) PG_GETARG_POINTER(1);
+ StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
+ bool retval;
+
+ if (strategy == BooleanSearchStrategy)
+ PG_RETURN_BOOL(execconsistent((QUERYTYPE *) query,
+ (ArrayType *) DatumGetPointer(entry->key),
+ ISLEAFKEY((ArrayType *) DatumGetPointer(entry->key))));
+
+ /* XXX are we sure it's safe to scribble on the query object here? */
+ /* XXX what about toasted input? */
+ /* sort query for fast search, key is already sorted */
+ if (ARRISVOID(query))
+ PG_RETURN_BOOL(false);
+ PREPAREARR(query);
+
+ switch (strategy)
+ {
+ case RTOverlapStrategyNumber:
+ retval = inner_int_overlap((ArrayType *) DatumGetPointer(entry->key),
+ query);
+ break;
+ case RTSameStrategyNumber:
+ if (GIST_LEAF(entry))
+ DirectFunctionCall3(
+ g_int_same,
+ entry->key,
+ PointerGetDatum(query),
+ PointerGetDatum(&retval)
+ );
+ else
+ retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
+ query);
+ break;
+ case RTContainsStrategyNumber:
+ retval = inner_int_contains((ArrayType *) DatumGetPointer(entry->key),
+ query);
+ break;
+ case RTContainedByStrategyNumber:
+ if (GIST_LEAF(entry))
+ retval = inner_int_contains(query,
+ (ArrayType *) DatumGetPointer(entry->key));
+ else
+ retval = inner_int_overlap((ArrayType *) DatumGetPointer(entry->key),
+ query);
+ break;
+ default:
+ retval = FALSE;
+ }
+ PG_RETURN_BOOL(retval);
+}
+
+Datum
+g_int_union(PG_FUNCTION_ARGS) {
+ bytea *entryvec = (bytea *) PG_GETARG_POINTER(0);
+ int *size = (int *) PG_GETARG_POINTER(1);
+ int4 i,len = (VARSIZE(entryvec) - VARHDRSZ) / sizeof(GISTENTRY);
+ ArrayType *res;
+ int totlen=0,*ptr;
+
+ for (i = 0; i < len; i++)
+ totlen+=ARRNELEMS( GETENTRY(entryvec,i) );
+
+ res=new_intArrayType(totlen);
+ ptr=ARRPTR(res);
+
+ for (i = 0; i < len; i++) {
+ memcpy(ptr, ARRPTR( GETENTRY(entryvec,i) ), ARRNELEMS( GETENTRY(entryvec,i) )*sizeof(int4) );
+ ptr+=ARRNELEMS( GETENTRY(entryvec,i) );
+ }
+
+ QSORT(res,1);
+ res=_int_unique(res);
+ *size = VARSIZE(res);
+ PG_RETURN_POINTER(res);
+}
+
+/*
+** GiST Compress and Decompress methods
+*/
+Datum
+g_int_compress(PG_FUNCTION_ARGS)
+{
+ GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
+ GISTENTRY *retval;
+ ArrayType *r;
+ int len;
+ int *dr;
+ int i,
+ min,
+ cand;
+
+ if (entry->leafkey)
+ {
+ r = (ArrayType *) PG_DETOAST_DATUM_COPY(entry->key);
+ PREPAREARR(r);
+ r->flags |= LEAFKEY;
+ retval = palloc(sizeof(GISTENTRY));
+ gistentryinit(*retval, PointerGetDatum(r),
+ entry->rel, entry->page, entry->offset, VARSIZE(r), FALSE);
+
+ PG_RETURN_POINTER(retval);
+ }
+
+ r = (ArrayType *) PG_DETOAST_DATUM(entry->key);
+ if (ISLEAFKEY(r) || ARRISVOID(r))
+ {
+ if (r != (ArrayType *) DatumGetPointer(entry->key))
+ pfree(r);
+ PG_RETURN_POINTER(entry);
+ }
+
+ if ((len = ARRNELEMS(r)) >= 2 * MAXNUMRANGE)
+ { /* compress */
+ if (r == (ArrayType *) DatumGetPointer(entry->key))
+ r = (ArrayType *) PG_DETOAST_DATUM_COPY(entry->key);
+ r = resize_intArrayType(r, 2 * (len));
+
+ dr = ARRPTR(r);
+
+ for (i = len - 1; i >= 0; i--)
+ dr[2 * i] = dr[2 * i + 1] = dr[i];
+
+ len *= 2;
+ cand = 1;
+ while (len > MAXNUMRANGE * 2)
+ {
+ min = 0x7fffffff;
+ for (i = 2; i < len; i += 2)
+ if (min > (dr[i] - dr[i - 1]))
+ {
+ min = (dr[i] - dr[i - 1]);
+ cand = i;
+ }
+ memmove((void *) &dr[cand - 1], (void *) &dr[cand + 1], (len - cand - 1) * sizeof(int));
+ len -= 2;
+ }
+ r = resize_intArrayType(r, len);
+ retval = palloc(sizeof(GISTENTRY));
+ gistentryinit(*retval, PointerGetDatum(r),
+ entry->rel, entry->page, entry->offset, VARSIZE(r), FALSE);
+ PG_RETURN_POINTER(retval);
+ }
+ else
+ PG_RETURN_POINTER(entry);
+
+ PG_RETURN_POINTER(entry);
+}
+
+Datum
+g_int_decompress(PG_FUNCTION_ARGS)
+{
+ GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
+ GISTENTRY *retval;
+ ArrayType *r;
+ int *dr,
+ lenr;
+ ArrayType *in;
+ int lenin;
+ int *din;
+ int i,
+ j;
+
+ in = (ArrayType *) PG_DETOAST_DATUM(entry->key);
+
+ if (ARRISVOID(in))
+ PG_RETURN_POINTER(entry);
+
+ lenin = ARRNELEMS(in);
+
+ if (lenin < 2 * MAXNUMRANGE || ISLEAFKEY(in))
+ { /* not compressed value */
+ if (in != (ArrayType *) DatumGetPointer(entry->key))
+ {
+ retval = palloc(sizeof(GISTENTRY));
+ gistentryinit(*retval, PointerGetDatum(in),
+ entry->rel, entry->page, entry->offset, VARSIZE(in), FALSE);
+
+ PG_RETURN_POINTER(retval);
+ }
+ PG_RETURN_POINTER(entry);
+ }
+
+ din = ARRPTR(in);
+ lenr = internal_size(din, lenin);
+
+ r = new_intArrayType(lenr);
+ dr = ARRPTR(r);
+
+ for (i = 0; i < lenin; i += 2)
+ for (j = din[i]; j <= din[i + 1]; j++)
+ if ((!i) || *(dr - 1) != j)
+ *dr++ = j;
+
+ if (in != (ArrayType *) DatumGetPointer(entry->key))
+ pfree(in);
+ retval = palloc(sizeof(GISTENTRY));
+ gistentryinit(*retval, PointerGetDatum(r),
+ entry->rel, entry->page, entry->offset, VARSIZE(r), FALSE);
+
+ PG_RETURN_POINTER(retval);
+}
+
+/*
+** The GiST Penalty method for _intments
+*/
+Datum
+g_int_penalty(PG_FUNCTION_ARGS) {
+ GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
+ GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
+ float *result = (float *) PG_GETARG_POINTER(2);
+ ArrayType *ud;
+ float tmp1,
+ tmp2;
+
+ ud = inner_int_union((ArrayType *) DatumGetPointer(origentry->key),
+ (ArrayType *) DatumGetPointer(newentry->key));
+ rt__int_size(ud, &tmp1);
+ rt__int_size((ArrayType *) DatumGetPointer(origentry->key), &tmp2);
+ *result = tmp1 - tmp2;
+ pfree(ud);
+
+ PG_RETURN_POINTER (result);
+}
+
+
+
+Datum
+g_int_same(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) PointerGetDatum(PG_GETARG_POINTER(0));
+ ArrayType *b = (ArrayType *) PointerGetDatum(PG_GETARG_POINTER(1));
+ bool *result = (bool *) PG_GETARG_POINTER(2);
+ int4 n = ARRNELEMS(a);
+ int4 *da,
+ *db;
+
+ if (n != ARRNELEMS(b))
+ {
+ *result = false;
+ PG_RETURN_POINTER(result);
+ }
+ *result = TRUE;
+ da = ARRPTR(a);
+ db = ARRPTR(b);
+ while (n--)
+ if (*da++ != *db++)
+ {
+ *result = FALSE;
+ break;
+ }
+
+ PG_RETURN_POINTER(result);
+}
+
+/*****************************************************************
+** Common GiST Method
+*****************************************************************/
+
+typedef struct
+{
+ OffsetNumber pos;
+ float cost;
+} SPLITCOST;
+
+static int
+comparecost(const void *a, const void *b)
+{
+ if (((SPLITCOST *) a)->cost == ((SPLITCOST *) b)->cost)
+ return 0;
+ else
+ return (((SPLITCOST *) a)->cost > ((SPLITCOST *) b)->cost) ? 1 : -1;
+}
+
+/*
+** The GiST PickSplit method for _intments
+** We use Guttman's poly time split algorithm
+*/
+Datum
+g_int_picksplit(PG_FUNCTION_ARGS) {
+ bytea *entryvec = (bytea *) PG_GETARG_POINTER(0);
+ GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
+ OffsetNumber i,
+ j;
+ ArrayType *datum_alpha,
+ *datum_beta;
+ ArrayType *datum_l,
+ *datum_r;
+ ArrayType *union_d,
+ *union_dl,
+ *union_dr;
+ ArrayType *inter_d;
+ bool firsttime;
+ float size_alpha,
+ size_beta,
+ size_union,
+ size_inter;
+ float size_waste,
+ waste;
+ float size_l,
+ size_r;
+ int nbytes;
+ OffsetNumber seed_1 = 0,
+ seed_2 = 0;
+ OffsetNumber *left,
+ *right;
+ OffsetNumber maxoff;
+ SPLITCOST *costvector;
+
+#ifdef GIST_DEBUG
+ elog(DEBUG3, "--------picksplit %d", (VARSIZE(entryvec) - VARHDRSZ) / sizeof(GISTENTRY));
+#endif
+
+ maxoff = ((VARSIZE(entryvec) - VARHDRSZ) / sizeof(GISTENTRY)) - 2;
+ nbytes = (maxoff + 2) * sizeof(OffsetNumber);
+ v->spl_left = (OffsetNumber *) palloc(nbytes);
+ v->spl_right = (OffsetNumber *) palloc(nbytes);
+
+ firsttime = true;
+ waste = 0.0;
+ for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i))
+ {
+ datum_alpha = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[i].key);
+ for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j))
+ {
+ datum_beta = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[j].key);
+
+ /* compute the wasted space by unioning these guys */
+ /* size_waste = size_union - size_inter; */
+ union_d = inner_int_union(datum_alpha, datum_beta);
+ rt__int_size(union_d, &size_union);
+ inter_d = inner_int_inter(datum_alpha, datum_beta);
+ rt__int_size(inter_d, &size_inter);
+ size_waste = size_union - size_inter;
+
+ pfree(union_d);
+
+ if (inter_d != (ArrayType *) NULL)
+ pfree(inter_d);
+
+ /*
+ * are these a more promising split that what we've already
+ * seen?
+ */
+
+ if (size_waste > waste || firsttime)
+ {
+ waste = size_waste;
+ seed_1 = i;
+ seed_2 = j;
+ firsttime = false;
+ }
+ }
+ }
+
+ left = v->spl_left;
+ v->spl_nleft = 0;
+ right = v->spl_right;
+ v->spl_nright = 0;
+ if (seed_1 == 0 || seed_2 == 0)
+ {
+ seed_1 = 1;
+ seed_2 = 2;
+ }
+
+ datum_alpha = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[seed_1].key);
+ datum_l = copy_intArrayType(datum_alpha);
+ rt__int_size(datum_l, &size_l);
+ datum_beta = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[seed_2].key);
+ datum_r = copy_intArrayType(datum_beta);
+ rt__int_size(datum_r, &size_r);
+
+ maxoff = OffsetNumberNext(maxoff);
+
+ /*
+ * sort entries
+ */
+ costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
+ for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
+ {
+ costvector[i - 1].pos = i;
+ datum_alpha = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[i].key);
+ union_d = inner_int_union(datum_l, datum_alpha);
+ rt__int_size(union_d, &size_alpha);
+ pfree(union_d);
+ union_d = inner_int_union(datum_r, datum_alpha);
+ rt__int_size(union_d, &size_beta);
+ pfree(union_d);
+ costvector[i - 1].cost = abs((size_alpha - size_l) - (size_beta - size_r));
+ }
+ qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
+
+ /*
+ * Now split up the regions between the two seeds. An important
+ * property of this split algorithm is that the split vector v has the
+ * indices of items to be split in order in its left and right
+ * vectors. We exploit this property by doing a merge in the code
+ * that actually splits the page.
+ *
+ * For efficiency, we also place the new index tuple in this loop. This
+ * is handled at the very end, when we have placed all the existing
+ * tuples and i == maxoff + 1.
+ */
+
+
+ for (j = 0; j < maxoff; j++)
+ {
+ i = costvector[j].pos;
+
+ /*
+ * If we've already decided where to place this item, just put it
+ * on the right list. Otherwise, we need to figure out which page
+ * needs the least enlargement in order to store the item.
+ */
+
+ if (i == seed_1)
+ {
+ *left++ = i;
+ v->spl_nleft++;
+ continue;
+ }
+ else if (i == seed_2)
+ {
+ *right++ = i;
+ v->spl_nright++;
+ continue;
+ }
+
+ /* okay, which page needs least enlargement? */
+ datum_alpha = (ArrayType *) DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[i].key);
+ union_dl = inner_int_union(datum_l, datum_alpha);
+ union_dr = inner_int_union(datum_r, datum_alpha);
+ rt__int_size(union_dl, &size_alpha);
+ rt__int_size(union_dr, &size_beta);
+
+ /* pick which page to add it to */
+ if (size_alpha - size_l < size_beta - size_r + WISH_F(v->spl_nleft, v->spl_nright, 0.01))
+ {
+ if (datum_l)
+ pfree(datum_l);
+ if (union_dr)
+ pfree(union_dr);
+ datum_l = union_dl;
+ size_l = size_alpha;
+ *left++ = i;
+ v->spl_nleft++;
+ }
+ else
+ {
+ if (datum_r)
+ pfree(datum_r);
+ if (union_dl)
+ pfree(union_dl);
+ datum_r = union_dr;
+ size_r = size_beta;
+ *right++ = i;
+ v->spl_nright++;
+ }
+ }
+ pfree(costvector);
+ *right = *left = FirstOffsetNumber;
+
+ datum_l->flags &= ~LEAFKEY;
+ datum_r->flags &= ~LEAFKEY;
+ v->spl_ldatum = PointerGetDatum(datum_l);
+ v->spl_rdatum = PointerGetDatum(datum_r);
+
+ PG_RETURN_POINTER(v);
+}
+
diff --git a/contrib/intarray/_int_op.c b/contrib/intarray/_int_op.c
new file mode 100644
index 00000000000..5aa27f039d1
--- /dev/null
+++ b/contrib/intarray/_int_op.c
@@ -0,0 +1,444 @@
+#include "_int.h"
+
+#include "lib/stringinfo.h"
+
+PG_FUNCTION_INFO_V1(_int_different);
+PG_FUNCTION_INFO_V1(_int_same);
+PG_FUNCTION_INFO_V1(_int_contains);
+PG_FUNCTION_INFO_V1(_int_contained);
+PG_FUNCTION_INFO_V1(_int_overlap);
+PG_FUNCTION_INFO_V1(_int_union);
+PG_FUNCTION_INFO_V1(_int_inter);
+
+Datum _int_different(PG_FUNCTION_ARGS);
+Datum _int_same(PG_FUNCTION_ARGS);
+Datum _int_contains(PG_FUNCTION_ARGS);
+Datum _int_contained(PG_FUNCTION_ARGS);
+Datum _int_overlap(PG_FUNCTION_ARGS);
+Datum _int_union(PG_FUNCTION_ARGS);
+Datum _int_inter(PG_FUNCTION_ARGS);
+
+Datum
+_int_contained(PG_FUNCTION_ARGS)
+{
+ PG_RETURN_BOOL(DatumGetBool(
+ DirectFunctionCall2(
+ _int_contains,
+ PointerGetDatum(PG_GETARG_POINTER(1)),
+ PointerGetDatum(PG_GETARG_POINTER(0))
+ )
+ ));
+}
+
+Datum
+_int_contains(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
+ ArrayType *b = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1)));
+ bool res;
+
+ if (ARRISVOID(a) || ARRISVOID(b))
+ return FALSE;
+
+ PREPAREARR(a);
+ PREPAREARR(b);
+ res = inner_int_contains(a, b);
+ pfree(a);
+ pfree(b);
+ PG_RETURN_BOOL(res);
+}
+
+Datum
+_int_different(PG_FUNCTION_ARGS)
+{
+ PG_RETURN_BOOL(!DatumGetBool(
+ DirectFunctionCall2(
+ _int_same,
+ PointerGetDatum(PG_GETARG_POINTER(0)),
+ PointerGetDatum(PG_GETARG_POINTER(1))
+ )
+ ));
+}
+
+Datum
+_int_same(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
+ ArrayType *b = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1)));
+ int na,
+ nb;
+ int n;
+ int *da,
+ *db;
+ bool result;
+ bool avoid = ARRISVOID(a);
+ bool bvoid = ARRISVOID(b);
+
+ if (avoid || bvoid)
+ return (avoid && bvoid) ? TRUE : FALSE;
+
+ SORT(a);
+ SORT(b);
+ na = ARRNELEMS(a);
+ nb = ARRNELEMS(b);
+ da = ARRPTR(a);
+ db = ARRPTR(b);
+
+ result = FALSE;
+
+ if (na == nb)
+ {
+ result = TRUE;
+ for (n = 0; n < na; n++)
+ if (da[n] != db[n])
+ {
+ result = FALSE;
+ break;
+ }
+ }
+
+ pfree(a);
+ pfree(b);
+
+ PG_RETURN_BOOL(result);
+}
+
+/* _int_overlap -- does a overlap b?
+ */
+Datum
+_int_overlap(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
+ ArrayType *b = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1)));
+ bool result;
+
+ if (ARRISVOID(a) || ARRISVOID(b))
+ return FALSE;
+
+ SORT(a);
+ SORT(b);
+
+ result = inner_int_overlap(a, b);
+
+ pfree(a);
+ pfree(b);
+
+ PG_RETURN_BOOL(result);
+}
+
+Datum
+_int_union(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
+ ArrayType *b = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1)));
+ ArrayType *result;
+
+ if (!ARRISVOID(a))
+ SORT(a);
+ if (!ARRISVOID(b))
+ SORT(b);
+
+ result = inner_int_union(a, b);
+
+ if (a)
+ pfree(a);
+ if (b)
+ pfree(b);
+
+ PG_RETURN_POINTER(result);
+}
+
+Datum
+_int_inter(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
+ ArrayType *b = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1)));
+ ArrayType *result;
+
+ if (ARRISVOID(a) || ARRISVOID(b))
+ PG_RETURN_POINTER(new_intArrayType(0));
+
+ SORT(a);
+ SORT(b);
+
+ result = inner_int_inter(a, b);
+
+ pfree(a);
+ pfree(b);
+
+ PG_RETURN_POINTER(result);
+}
+
+
+PG_FUNCTION_INFO_V1(intset);
+PG_FUNCTION_INFO_V1(icount);
+PG_FUNCTION_INFO_V1(sort);
+PG_FUNCTION_INFO_V1(sort_asc);
+PG_FUNCTION_INFO_V1(sort_desc);
+PG_FUNCTION_INFO_V1(uniq);
+PG_FUNCTION_INFO_V1(idx);
+PG_FUNCTION_INFO_V1(subarray);
+PG_FUNCTION_INFO_V1(intarray_push_elem);
+PG_FUNCTION_INFO_V1(intarray_push_array);
+PG_FUNCTION_INFO_V1(intarray_del_elem);
+PG_FUNCTION_INFO_V1(intset_union_elem);
+PG_FUNCTION_INFO_V1(intset_subtract);
+Datum intset(PG_FUNCTION_ARGS);
+Datum icount(PG_FUNCTION_ARGS);
+Datum sort(PG_FUNCTION_ARGS);
+Datum sort_asc(PG_FUNCTION_ARGS);
+Datum sort_desc(PG_FUNCTION_ARGS);
+Datum uniq(PG_FUNCTION_ARGS);
+Datum idx(PG_FUNCTION_ARGS);
+Datum subarray(PG_FUNCTION_ARGS);
+Datum intarray_push_elem(PG_FUNCTION_ARGS);
+Datum intarray_push_array(PG_FUNCTION_ARGS);
+Datum intarray_del_elem(PG_FUNCTION_ARGS);
+Datum intset_union_elem(PG_FUNCTION_ARGS);
+Datum intset_subtract(PG_FUNCTION_ARGS);
+
+#define QSORT(a, direction) \
+if (ARRNELEMS(a) > 1) \
+ qsort((void*)ARRPTR(a), ARRNELEMS(a),sizeof(int4), \
+ (direction) ? compASC : compDESC )
+
+
+Datum
+intset(PG_FUNCTION_ARGS)
+{
+ PG_RETURN_POINTER(int_to_intset(PG_GETARG_INT32(0)));
+}
+
+Datum
+icount(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(0)));
+ int32 count = (ARRISVOID(a)) ? 0 : ARRNELEMS(a);
+
+ PG_FREE_IF_COPY(a, 0);
+ PG_RETURN_INT32(count);
+}
+
+Datum
+sort(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
+ text *dirstr = (fcinfo->nargs == 2) ? PG_GETARG_TEXT_P(1) : NULL;
+ int32 dc = (dirstr) ? VARSIZE(dirstr) - VARHDRSZ : 0;
+ char *d = (dirstr) ? VARDATA(dirstr) : NULL;
+ int dir = -1;
+
+ if (ARRISVOID(a) || ARRNELEMS(a) < 2)
+ PG_RETURN_POINTER(a);
+
+ if (dirstr == NULL || (dc == 3
+ && (d[0] == 'A' || d[0] == 'a')
+ && (d[1] == 'S' || d[1] == 's')
+ && (d[2] == 'C' || d[2] == 'c')))
+ dir = 1;
+ else if (dc == 4
+ && (d[0] == 'D' || d[0] == 'd')
+ && (d[1] == 'E' || d[1] == 'e')
+ && (d[2] == 'S' || d[2] == 's')
+ && (d[3] == 'C' || d[3] == 'c'))
+ dir = 0;
+ if (dir == -1)
+ elog(ERROR, "Invalid second parameter in function sort. It must be 'ASC' or 'DESC'.");
+ QSORT(a, dir);
+ PG_RETURN_POINTER(a);
+}
+
+Datum
+sort_asc(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
+
+ if (ARRISVOID(a))
+ PG_RETURN_POINTER(a);
+ QSORT(a, 1);
+ PG_RETURN_POINTER(a);
+}
+
+Datum
+sort_desc(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
+
+ if (ARRISVOID(a))
+ PG_RETURN_POINTER(a);
+ QSORT(a, 0);
+ PG_RETURN_POINTER(a);
+}
+
+Datum
+uniq(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
+
+ if (ARRISVOID(a) || ARRNELEMS(a) < 2)
+ PG_RETURN_POINTER(a);
+ a = _int_unique(a);
+ PG_RETURN_POINTER(a);
+}
+
+Datum
+idx(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(0)));
+ int32 result = (ARRISVOID(a)) ? 0 : ARRNELEMS(a);
+
+ if (result)
+ result = intarray_match_first(a, PG_GETARG_INT32(1));
+ PG_FREE_IF_COPY(a, 0);
+ PG_RETURN_INT32(result);
+}
+
+Datum
+subarray(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(0)));
+ ArrayType *result;
+ int32 start = (PG_GETARG_INT32(1) > 0) ? PG_GETARG_INT32(1) - 1 : PG_GETARG_INT32(1);
+ int32 len = (fcinfo->nargs == 3) ? PG_GETARG_INT32(2) : 0;
+ int32 end = 0;
+ int32 c;
+
+ if (ARRISVOID(a))
+ {
+ PG_FREE_IF_COPY(a, 0);
+ PG_RETURN_POINTER(new_intArrayType(0));
+ }
+
+ c = ARRNELEMS(a);
+
+ if (start < 0)
+ start = c + start;
+
+ if (len < 0)
+ end = c + len;
+ else if (len == 0)
+ end = c;
+ else
+ end = start + len;
+
+ if (end > c)
+ end = c;
+
+ if (start < 0)
+ start = 0;
+
+ if (start >= end || end <= 0)
+ {
+ PG_FREE_IF_COPY(a, 0);
+ PG_RETURN_POINTER(new_intArrayType(0));
+ }
+
+
+ result = new_intArrayType(end - start);
+ if (end - start > 0)
+ memcpy(ARRPTR(result), ARRPTR(a) + start, (end - start) * sizeof(int32));
+ PG_FREE_IF_COPY(a, 0);
+ PG_RETURN_POINTER(result);
+}
+
+Datum
+intarray_push_elem(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(0)));
+ ArrayType *result;
+
+ result = intarray_add_elem(a, PG_GETARG_INT32(1));
+ PG_FREE_IF_COPY(a, 0);
+ PG_RETURN_POINTER(result);
+}
+
+Datum
+intarray_push_array(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(0)));
+ ArrayType *b = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(1)));
+ ArrayType *result;
+
+ result = intarray_concat_arrays(a, b);
+ PG_FREE_IF_COPY(a, 0);
+ PG_FREE_IF_COPY(b, 1);
+ PG_RETURN_POINTER(result);
+}
+
+Datum
+intarray_del_elem(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
+ int32 c = (ARRISVOID(a)) ? 0 : ARRNELEMS(a);
+ int32 *aa = ARRPTR(a);
+ int32 n = 0,
+ i;
+ int32 elem = PG_GETARG_INT32(1);
+
+ for (i = 0; i < c; i++)
+ if (aa[i] != elem)
+ {
+ if (i > n)
+ aa[n++] = aa[i];
+ else
+ n++;
+ }
+ if (c > 0)
+ a = resize_intArrayType(a, n);
+ PG_RETURN_POINTER(a);
+}
+
+Datum
+intset_union_elem(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(0)));
+ ArrayType *result;
+
+ result = intarray_add_elem(a, PG_GETARG_INT32(1));
+ PG_FREE_IF_COPY(a, 0);
+ QSORT(result, 1);
+ PG_RETURN_POINTER(_int_unique(result));
+}
+
+Datum
+intset_subtract(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(0)));
+ ArrayType *b = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1)));
+ ArrayType *result;
+ int32 ca = ARRISVOID(a);
+ int32 cb = ARRISVOID(b);
+ int32 *aa,
+ *bb,
+ *r;
+ int32 n = 0,
+ i = 0,
+ k = 0;
+
+ QSORT(a, 1);
+ a = _int_unique(a);
+ ca = ARRNELEMS(a);
+ QSORT(b, 1);
+ b = _int_unique(b);
+ cb = ARRNELEMS(b);
+ result = new_intArrayType(ca);
+ aa = ARRPTR(a);
+ bb = ARRPTR(b);
+ r = ARRPTR(result);
+ while (i < ca)
+ {
+ if (k == cb || aa[i] < bb[k])
+ r[n++] = aa[i++];
+ else if (aa[i] == bb[k])
+ {
+ i++;
+ k++;
+ }
+ else
+ k++;
+ }
+ result = resize_intArrayType(result, n);
+ pfree(a);
+ pfree(b);
+ PG_RETURN_POINTER(result);
+}
diff --git a/contrib/intarray/_int_tool.c b/contrib/intarray/_int_tool.c
new file mode 100644
index 00000000000..04ff5e436b6
--- /dev/null
+++ b/contrib/intarray/_int_tool.c
@@ -0,0 +1,370 @@
+#include "_int.h"
+
+
+bool
+inner_int_contains(ArrayType *a, ArrayType *b)
+{
+ int na,
+ nb;
+ int i,
+ j,
+ n;
+ int *da,
+ *db;
+
+ if (ARRISVOID(a) || ARRISVOID(b))
+ return FALSE;
+
+ na = ARRNELEMS(a);
+ nb = ARRNELEMS(b);
+ da = ARRPTR(a);
+ db = ARRPTR(b);
+
+ i = j = n = 0;
+ while (i < na && j < nb)
+ if (da[i] < db[j])
+ i++;
+ else if (da[i] == db[j])
+ {
+ n++;
+ i++;
+ j++;
+ }
+ else
+ j++;
+
+ return (n == nb) ? TRUE : FALSE;
+}
+
+bool
+inner_int_overlap(ArrayType *a, ArrayType *b)
+{
+ int na,
+ nb;
+ int i,
+ j;
+ int *da,
+ *db;
+
+ if (ARRISVOID(a) || ARRISVOID(b))
+ return FALSE;
+
+ na = ARRNELEMS(a);
+ nb = ARRNELEMS(b);
+ da = ARRPTR(a);
+ db = ARRPTR(b);
+
+ i = j = 0;
+ while (i < na && j < nb)
+ if (da[i] < db[j])
+ i++;
+ else if (da[i] == db[j])
+ return TRUE;
+ else
+ j++;
+
+ return FALSE;
+}
+
+ArrayType *
+inner_int_union(ArrayType *a, ArrayType *b)
+{
+ ArrayType *r = NULL;
+ int na,
+ nb;
+ int *da,
+ *db,
+ *dr;
+ int i,
+ j;
+
+ if (ARRISVOID(a) && ARRISVOID(b))
+ return new_intArrayType(0);
+ if (ARRISVOID(a))
+ r = copy_intArrayType(b);
+ if (ARRISVOID(b))
+ r = copy_intArrayType(a);
+
+ if (r)
+ dr = ARRPTR(r);
+ else
+ {
+ na = ARRNELEMS(a);
+ nb = ARRNELEMS(b);
+ da = ARRPTR(a);
+ db = ARRPTR(b);
+
+ r = new_intArrayType(na + nb);
+ dr = ARRPTR(r);
+
+ /* union */
+ i = j = 0;
+ while (i < na && j < nb)
+ if (da[i] < db[j])
+ *dr++ = da[i++];
+ else
+ *dr++ = db[j++];
+
+ while (i < na)
+ *dr++ = da[i++];
+ while (j < nb)
+ *dr++ = db[j++];
+
+ }
+
+ if (ARRNELEMS(r) > 1)
+ r = _int_unique(r);
+
+ return r;
+}
+
+ArrayType *
+inner_int_inter(ArrayType *a, ArrayType *b)
+{
+ ArrayType *r;
+ int na,
+ nb;
+ int *da,
+ *db,
+ *dr;
+ int i,
+ j;
+
+ if (ARRISVOID(a) || ARRISVOID(b))
+ return new_intArrayType(0);
+
+ na = ARRNELEMS(a);
+ nb = ARRNELEMS(b);
+ da = ARRPTR(a);
+ db = ARRPTR(b);
+ r = new_intArrayType(min(na, nb));
+ dr = ARRPTR(r);
+
+ i = j = 0;
+ while (i < na && j < nb)
+ if (da[i] < db[j])
+ i++;
+ else if (da[i] == db[j])
+ {
+ if (i + j == 0 || (i + j > 0 && *(dr - 1) != db[j]))
+ *dr++ = db[j];
+ i++;
+ j++;
+ }
+ else
+ j++;
+
+ if ((dr - ARRPTR(r)) == 0)
+ {
+ pfree(r);
+ return new_intArrayType(0);
+ }
+ else
+ return resize_intArrayType(r, dr - ARRPTR(r));
+}
+
+void
+rt__int_size(ArrayType *a, float *size)
+{
+ *size = (float) ARRNELEMS(a);
+
+ return;
+}
+
+
+/* len >= 2 */
+bool
+isort(int4 *a, int len)
+{
+ int4 tmp,
+ index;
+ int4 *cur,
+ *end;
+ bool r = FALSE;
+
+ end = a + len;
+ do
+ {
+ index = 0;
+ cur = a + 1;
+ while (cur < end)
+ {
+ if (*(cur - 1) > *cur)
+ {
+ tmp = *(cur - 1);
+ *(cur - 1) = *cur;
+ *cur = tmp;
+ index = 1;
+ }
+ else if (!r && *(cur - 1) == *cur)
+ r = TRUE;
+ cur++;
+ }
+ } while (index);
+ return r;
+}
+
+ArrayType *
+new_intArrayType(int num)
+{
+ ArrayType *r;
+ int nbytes = ARR_OVERHEAD(NDIM) + sizeof(int) * num;
+
+ r = (ArrayType *) palloc0(nbytes);
+
+ ARR_SIZE(r) = nbytes;
+ ARR_NDIM(r) = NDIM;
+ ARR_ELEMTYPE(r) = INT4OID;
+ r->flags &= ~LEAFKEY;
+ *((int *) ARR_DIMS(r)) = num;
+ *((int *) ARR_LBOUND(r)) = 1;
+
+ return r;
+}
+
+ArrayType *
+resize_intArrayType(ArrayType *a, int num)
+{
+ int nbytes = ARR_OVERHEAD(NDIM) + sizeof(int) * num;
+
+ if (num == ARRNELEMS(a))
+ return a;
+
+ a = (ArrayType *) repalloc(a, nbytes);
+
+ a->size = nbytes;
+ *((int *) ARR_DIMS(a)) = num;
+ return a;
+}
+
+ArrayType *
+copy_intArrayType(ArrayType *a)
+{
+ ArrayType *r;
+
+ r = new_intArrayType(ARRNELEMS(a));
+ memmove(r, a, VARSIZE(a));
+ return r;
+}
+
+/* num for compressed key */
+int
+internal_size(int *a, int len)
+{
+ int i,
+ size = 0;
+
+ for (i = 0; i < len; i += 2)
+ if (!i || a[i] != a[i - 1]) /* do not count repeated range */
+ size += a[i + 1] - a[i] + 1;
+
+ return size;
+}
+
+/* r is sorted and size of r > 1 */
+ArrayType *
+_int_unique(ArrayType *r)
+{
+ int *tmp,
+ *dr,
+ *data;
+ int num = ARRNELEMS(r);
+
+ if ( num<2 )
+ return r;
+
+ data = tmp = dr = ARRPTR(r);
+ while (tmp - data < num)
+ if (*tmp != *dr)
+ *(++dr) = *tmp++;
+ else
+ tmp++;
+ return resize_intArrayType(r, dr + 1 - ARRPTR(r));
+}
+
+void
+gensign(BITVEC sign, int *a, int len)
+{
+ int i;
+
+ /* we assume that the sign vector is previously zeroed */
+ for (i = 0; i < len; i++)
+ {
+ HASH(sign, *a);
+ a++;
+ }
+}
+
+int32
+intarray_match_first(ArrayType *a, int32 elem)
+{
+ int32 *aa,
+ c,
+ i;
+
+ c = (ARRISVOID(a)) ? 0 : ARRNELEMS(a);
+ aa = ARRPTR(a);
+ for (i = 0; i < c; i++)
+ if (aa[i] == elem)
+ return (i + 1);
+ return 0;
+}
+
+ArrayType *
+intarray_add_elem(ArrayType *a, int32 elem)
+{
+ ArrayType *result;
+ int32 *r;
+ int32 c = (ARRISVOID(a)) ? 0 : ARRNELEMS(a);
+
+ result = new_intArrayType(c + 1);
+ r = ARRPTR(result);
+ if (c > 0)
+ memcpy(r, ARRPTR(a), c * sizeof(int32));
+ r[c] = elem;
+ return result;
+}
+
+ArrayType *
+intarray_concat_arrays(ArrayType *a, ArrayType *b)
+{
+ ArrayType *result;
+ int32 ac = (ARRISVOID(a)) ? 0 : ARRNELEMS(a);
+ int32 bc = (ARRISVOID(b)) ? 0 : ARRNELEMS(b);
+
+ result = new_intArrayType(ac + bc);
+ if (ac)
+ memcpy(ARRPTR(result), ARRPTR(a), ac * sizeof(int32));
+ if (bc)
+ memcpy(ARRPTR(result) + ac, ARRPTR(b), bc * sizeof(int32));
+ return result;
+}
+
+ArrayType *
+int_to_intset(int32 n)
+{
+ ArrayType *result;
+ int32 *aa;
+
+ result = new_intArrayType(1);
+ aa = ARRPTR(result);
+ aa[0] = n;
+ return result;
+}
+
+int
+compASC(const void *a, const void *b)
+{
+ if (*(int4 *) a == *(int4 *) b)
+ return 0;
+ return (*(int4 *) a > *(int4 *) b) ? 1 : -1;
+}
+
+int
+compDESC(const void *a, const void *b)
+{
+ if (*(int4 *) a == *(int4 *) b)
+ return 0;
+ return (*(int4 *) a < *(int4 *) b) ? 1 : -1;
+}
+
diff --git a/contrib/intarray/_intbig_gist.c b/contrib/intarray/_intbig_gist.c
new file mode 100644
index 00000000000..ad1279ced3e
--- /dev/null
+++ b/contrib/intarray/_intbig_gist.c
@@ -0,0 +1,522 @@
+#include "_int.h"
+
+#define GETENTRY(vec,pos) ((GISTTYPE *) DatumGetPointer(((GISTENTRY *) VARDATA(vec))[(pos)].key))
+/*
+** _intbig methods
+*/
+PG_FUNCTION_INFO_V1(g_intbig_consistent);
+PG_FUNCTION_INFO_V1(g_intbig_compress);
+PG_FUNCTION_INFO_V1(g_intbig_decompress);
+PG_FUNCTION_INFO_V1(g_intbig_penalty);
+PG_FUNCTION_INFO_V1(g_intbig_picksplit);
+PG_FUNCTION_INFO_V1(g_intbig_union);
+PG_FUNCTION_INFO_V1(g_intbig_same);
+
+Datum g_intbig_consistent(PG_FUNCTION_ARGS);
+Datum g_intbig_compress(PG_FUNCTION_ARGS);
+Datum g_intbig_decompress(PG_FUNCTION_ARGS);
+Datum g_intbig_penalty(PG_FUNCTION_ARGS);
+Datum g_intbig_picksplit(PG_FUNCTION_ARGS);
+Datum g_intbig_union(PG_FUNCTION_ARGS);
+Datum g_intbig_same(PG_FUNCTION_ARGS);
+
+#define SUMBIT(val) ( \
+ GETBITBYTE((val),0) + \
+ GETBITBYTE((val),1) + \
+ GETBITBYTE((val),2) + \
+ GETBITBYTE((val),3) + \
+ GETBITBYTE((val),4) + \
+ GETBITBYTE((val),5) + \
+ GETBITBYTE((val),6) + \
+ GETBITBYTE((val),7) \
+)
+
+PG_FUNCTION_INFO_V1(_intbig_in);
+Datum _intbig_in(PG_FUNCTION_ARGS);
+
+PG_FUNCTION_INFO_V1(_intbig_out);
+Datum _intbig_out(PG_FUNCTION_ARGS);
+
+
+Datum
+_intbig_in(PG_FUNCTION_ARGS) {
+ elog(ERROR, "Not implemented");
+ PG_RETURN_DATUM(0);
+}
+
+Datum
+_intbig_out(PG_FUNCTION_ARGS) {
+ elog(ERROR, "Not implemented");
+ PG_RETURN_DATUM(0);
+}
+
+
+/*********************************************************************
+** intbig functions
+*********************************************************************/
+static bool
+_intbig_overlap(GISTTYPE *a, ArrayType *b)
+{
+ int num=ARRNELEMS(b);
+ int4 *ptr=ARRPTR(b);
+
+ while(num--) {
+ if (GETBIT(GETSIGN(a),HASHVAL(*ptr)))
+ return true;
+ ptr++;
+ }
+
+ return false;
+}
+
+static bool
+_intbig_contains(GISTTYPE *a, ArrayType *b)
+{
+ int num=ARRNELEMS(b);
+ int4 *ptr=ARRPTR(b);
+
+ while(num--) {
+ if (!GETBIT(GETSIGN(a),HASHVAL(*ptr)))
+ return false;
+ ptr++;
+ }
+
+ return true;
+}
+
+Datum
+g_intbig_same(PG_FUNCTION_ARGS) {
+ GISTTYPE *a = (GISTTYPE *) PG_GETARG_POINTER(0);
+ GISTTYPE *b = (GISTTYPE *) PG_GETARG_POINTER(1);
+ bool *result = (bool *) PG_GETARG_POINTER(2);
+
+ if (ISALLTRUE(a) && ISALLTRUE(b))
+ *result = true;
+ else if (ISALLTRUE(a))
+ *result = false;
+ else if (ISALLTRUE(b))
+ *result = false;
+ else {
+ int4 i;
+ BITVECP sa = GETSIGN(a),
+ sb = GETSIGN(b);
+ *result = true;
+ LOOPBYTE(
+ if (sa[i] != sb[i]) {
+ *result = false;
+ break;
+ }
+ );
+ }
+ PG_RETURN_POINTER(result);
+}
+
+Datum
+g_intbig_compress(PG_FUNCTION_ARGS)
+{
+ GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
+
+ if (entry->leafkey) {
+ GISTENTRY *retval;
+ ArrayType *in = (ArrayType *) PG_DETOAST_DATUM(entry->key);
+ int4 *ptr;
+ int num;
+ GISTTYPE *res=(GISTTYPE*)palloc(CALCGTSIZE(0));
+
+ ARRISVOID(in);
+
+ ptr=ARRPTR(in);
+ num=ARRNELEMS(in);
+ memset(res,0,CALCGTSIZE(0));
+ res->len=CALCGTSIZE(0);
+
+ while(num--) {
+ HASH(GETSIGN(res),*ptr);
+ ptr++;
+ }
+
+ retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
+ gistentryinit(*retval, PointerGetDatum(res),
+ entry->rel, entry->page,
+ entry->offset, res->len, FALSE);
+
+ if ( in!=(ArrayType *) PG_DETOAST_DATUM(entry->key) )
+ pfree(in);
+
+ PG_RETURN_POINTER(retval);
+ } else if ( !ISALLTRUE(DatumGetPointer(entry->key)) ) {
+ GISTENTRY *retval;
+ int i;
+ BITVECP sign = GETSIGN(DatumGetPointer(entry->key));
+ GISTTYPE *res;
+
+ LOOPBYTE(
+ if ((sign[i] & 0xff) != 0xff)
+ PG_RETURN_POINTER(entry);
+ );
+
+ res=(GISTTYPE*)palloc(CALCGTSIZE(ALLISTRUE));
+ res->len=CALCGTSIZE(ALLISTRUE);
+ res->flag = ALLISTRUE;
+
+ retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
+ gistentryinit(*retval, PointerGetDatum(res),
+ entry->rel, entry->page,
+ entry->offset, res->len, FALSE);
+
+ PG_RETURN_POINTER(retval);
+ }
+
+ PG_RETURN_POINTER(entry);
+}
+
+
+static int4
+sizebitvec(BITVECP sign) {
+ int4 size = 0, i;
+ LOOPBYTE(
+ size += SUMBIT(sign);
+ sign = (BITVECP) (((char *) sign) + 1);
+ );
+ return size;
+}
+
+static int
+hemdistsign(BITVECP a, BITVECP b) {
+ int i,dist=0;
+
+ LOOPBIT(
+ if ( GETBIT(a,i) != GETBIT(b,i) )
+ dist++;
+ );
+ return dist;
+}
+
+static int
+hemdist(GISTTYPE *a, GISTTYPE *b) {
+ if ( ISALLTRUE(a) ) {
+ if (ISALLTRUE(b))
+ return 0;
+ else
+ return SIGLENBIT-sizebitvec(GETSIGN(b));
+ } else if (ISALLTRUE(b))
+ return SIGLENBIT-sizebitvec(GETSIGN(a));
+
+ return hemdistsign( GETSIGN(a), GETSIGN(b) );
+}
+
+Datum
+g_intbig_decompress(PG_FUNCTION_ARGS)
+{
+ PG_RETURN_DATUM(PG_GETARG_DATUM(0));
+}
+
+static int4
+unionkey(BITVECP sbase, GISTTYPE * add)
+{
+ int4 i;
+ BITVECP sadd = GETSIGN(add);
+
+ if (ISALLTRUE(add))
+ return 1;
+ LOOPBYTE(
+ sbase[i] |= sadd[i];
+ );
+ return 0;
+}
+
+Datum
+g_intbig_union(PG_FUNCTION_ARGS) {
+ bytea *entryvec = (bytea *) PG_GETARG_POINTER(0);
+ int *size = (int *) PG_GETARG_POINTER(1);
+ BITVEC base;
+ int4 len = (VARSIZE(entryvec) - VARHDRSZ) / sizeof(GISTENTRY);
+ int4 i;
+ int4 flag = 0;
+ GISTTYPE *result;
+
+ MemSet((void *) base, 0, sizeof(BITVEC));
+ for (i = 0; i < len; i++) {
+ if (unionkey(base, GETENTRY(entryvec, i))) {
+ flag = ALLISTRUE;
+ break;
+ }
+ }
+
+ len = CALCGTSIZE(flag);
+ result = (GISTTYPE *) palloc(len);
+ *size = result->len = len;
+ result->flag = flag;
+ if (!ISALLTRUE(result))
+ memcpy((void *) GETSIGN(result), (void *) base, sizeof(BITVEC));
+
+ PG_RETURN_POINTER(result);
+}
+
+Datum
+g_intbig_penalty(PG_FUNCTION_ARGS) {
+ GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
+ GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
+ float *penalty = (float *) PG_GETARG_POINTER(2);
+ GISTTYPE *origval = (GISTTYPE *) DatumGetPointer(origentry->key);
+ GISTTYPE *newval = (GISTTYPE *) DatumGetPointer(newentry->key);
+
+ *penalty=hemdist(origval,newval);
+ PG_RETURN_POINTER(penalty);
+}
+
+
+typedef struct {
+ OffsetNumber pos;
+ int4 cost;
+} SPLITCOST;
+
+static int
+comparecost(const void *a, const void *b) {
+ return ((SPLITCOST *) a)->cost - ((SPLITCOST *) b)->cost;
+}
+
+
+Datum
+g_intbig_picksplit(PG_FUNCTION_ARGS) {
+ bytea *entryvec = (bytea *) PG_GETARG_POINTER(0);
+ GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
+ OffsetNumber k,
+ j;
+ GISTTYPE *datum_l,
+ *datum_r;
+ BITVECP union_l,
+ union_r;
+ int4 size_alpha, size_beta;
+ int4 size_waste,
+ waste = -1;
+ int4 nbytes;
+ OffsetNumber seed_1 = 0,
+ seed_2 = 0;
+ OffsetNumber *left,
+ *right;
+ OffsetNumber maxoff;
+ BITVECP ptr;
+ int i;
+ SPLITCOST *costvector;
+ GISTTYPE *_k,
+ *_j;
+
+ maxoff = ((VARSIZE(entryvec) - VARHDRSZ) / sizeof(GISTENTRY)) - 2;
+ nbytes = (maxoff + 2) * sizeof(OffsetNumber);
+ v->spl_left = (OffsetNumber *) palloc(nbytes);
+ v->spl_right = (OffsetNumber *) palloc(nbytes);
+
+ for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k)) {
+ _k = GETENTRY(entryvec, k);
+ for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j)) {
+ size_waste=hemdist(_k, GETENTRY(entryvec, j));
+ if (size_waste > waste ) {
+ waste = size_waste;
+ seed_1 = k;
+ seed_2 = j;
+ }
+ }
+ }
+
+ left = v->spl_left;
+ v->spl_nleft = 0;
+ right = v->spl_right;
+ v->spl_nright = 0;
+
+ if (seed_1 == 0 || seed_2 == 0)
+ {
+ seed_1 = 1;
+ seed_2 = 2;
+ }
+
+ /* form initial .. */
+ if (ISALLTRUE(GETENTRY(entryvec, seed_1)))
+ {
+ datum_l = (GISTTYPE *) palloc(GTHDRSIZE);
+ datum_l->len = GTHDRSIZE;
+ datum_l->flag = ALLISTRUE;
+ }
+ else
+ {
+ datum_l = (GISTTYPE *) palloc(GTHDRSIZE + SIGLEN);
+ datum_l->len = GTHDRSIZE + SIGLEN;
+ datum_l->flag = 0;
+ memcpy((void *) GETSIGN(datum_l), (void *) GETSIGN(GETENTRY(entryvec, seed_1)), sizeof(BITVEC));
+ }
+ if (ISALLTRUE(GETENTRY(entryvec, seed_2)))
+ {
+ datum_r = (GISTTYPE *) palloc(GTHDRSIZE);
+ datum_r->len = GTHDRSIZE;
+ datum_r->flag = ALLISTRUE;
+ }
+ else
+ {
+ datum_r = (GISTTYPE *) palloc(GTHDRSIZE + SIGLEN);
+ datum_r->len = GTHDRSIZE + SIGLEN;
+ datum_r->flag = 0;
+ memcpy((void *) GETSIGN(datum_r), (void *) GETSIGN(GETENTRY(entryvec, seed_2)), sizeof(BITVEC));
+ }
+
+ maxoff = OffsetNumberNext(maxoff);
+ /* sort before ... */
+ costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
+ for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
+ {
+ costvector[j - 1].pos = j;
+ _j = GETENTRY(entryvec, j);
+ size_alpha = hemdist(datum_l,_j);
+ size_beta = hemdist(datum_r,_j);
+ costvector[j - 1].cost = abs(size_alpha - size_beta);
+ }
+ qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
+
+ union_l=GETSIGN(datum_l);
+ union_r=GETSIGN(datum_r);
+
+ for (k = 0; k < maxoff; k++)
+ {
+ j = costvector[k].pos;
+ if (j == seed_1)
+ {
+ *left++ = j;
+ v->spl_nleft++;
+ continue;
+ }
+ else if (j == seed_2)
+ {
+ *right++ = j;
+ v->spl_nright++;
+ continue;
+ }
+ _j = GETENTRY(entryvec, j);
+ size_alpha = hemdist(datum_l,_j);
+ size_beta = hemdist(datum_r,_j);
+
+ if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.00001))
+ {
+ if (ISALLTRUE(datum_l) || ISALLTRUE(_j) ) {
+ if (!ISALLTRUE(datum_l))
+ MemSet((void *) union_l, 0xff, sizeof(BITVEC));
+ } else {
+ ptr=GETSIGN(_j);
+ LOOPBYTE(
+ union_l[i] |= ptr[i];
+ );
+ }
+ *left++ = j;
+ v->spl_nleft++;
+ }
+ else
+ {
+ if (ISALLTRUE(datum_r) || ISALLTRUE(_j) ) {
+ if (!ISALLTRUE(datum_r))
+ MemSet((void *) union_r, 0xff, sizeof(BITVEC));
+ } else {
+ ptr=GETSIGN(_j);
+ LOOPBYTE(
+ union_r[i] |= ptr[i];
+ );
+ }
+ *right++ = j;
+ v->spl_nright++;
+ }
+ }
+
+ *right = *left = FirstOffsetNumber;
+ pfree(costvector);
+
+ v->spl_ldatum = PointerGetDatum(datum_l);
+ v->spl_rdatum = PointerGetDatum(datum_r);
+
+ PG_RETURN_POINTER(v);
+}
+
+Datum
+g_intbig_consistent(PG_FUNCTION_ARGS)
+{
+ GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
+ ArrayType *query = (ArrayType *) PG_GETARG_POINTER(1);
+ StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
+ bool retval;
+
+ if ( ISALLTRUE(DatumGetPointer(entry->key)) )
+ PG_RETURN_BOOL(true);
+
+ if (strategy == BooleanSearchStrategy) {
+ PG_RETURN_BOOL(signconsistent((QUERYTYPE *) query,
+ GETSIGN(DatumGetPointer(entry->key)),
+ false));
+ }
+
+ /* XXX what about toasted input? */
+ if (ARRISVOID(query))
+ return FALSE;
+
+ switch (strategy)
+ {
+ case RTOverlapStrategyNumber:
+ retval = _intbig_overlap((GISTTYPE *) DatumGetPointer(entry->key), query);
+ break;
+ case RTSameStrategyNumber:
+ if (GIST_LEAF(entry)) {
+ int i,num=ARRNELEMS(query);
+ int4 *ptr=ARRPTR(query);
+ BITVEC qp;
+ BITVECP dq, de;
+ memset(qp,0,sizeof(BITVEC));
+
+ while(num--) {
+ HASH(qp, *ptr);
+ ptr++;
+ }
+
+ de=GETSIGN((GISTTYPE *) DatumGetPointer(entry->key));
+ dq=qp;
+ retval=true;
+ LOOPBYTE(
+ if ( de[i] != dq[i] ) {
+ retval=false;
+ break;
+ }
+ );
+
+ } else
+ retval = _intbig_contains((GISTTYPE *) DatumGetPointer(entry->key), query);
+ break;
+ case RTContainsStrategyNumber:
+ retval = _intbig_contains((GISTTYPE *) DatumGetPointer(entry->key), query);
+ break;
+ case RTContainedByStrategyNumber:
+ if (GIST_LEAF(entry)) {
+ int i,num=ARRNELEMS(query);
+ int4 *ptr=ARRPTR(query);
+ BITVEC qp;
+ BITVECP dq, de;
+ memset(qp,0,sizeof(BITVEC));
+
+ while(num--) {
+ HASH(qp, *ptr);
+ ptr++;
+ }
+
+ de=GETSIGN((GISTTYPE *) DatumGetPointer(entry->key));
+ dq=qp;
+ retval=true;
+ LOOPBYTE(
+ if ( de[i] & ~dq[i] ) {
+ retval=false;
+ break;
+ }
+ );
+
+ } else
+ retval = _intbig_overlap((GISTTYPE *) DatumGetPointer(entry->key), query);
+ break;
+ default:
+ retval = FALSE;
+ }
+ PG_RETURN_BOOL(retval);
+}
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-20 17:07:51 +0000