Header And Logo

PostgreSQL
| The world's most advanced open source database.

tsgistidx.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * tsgistidx.c
00004  *    GiST support functions for tsvector_ops
00005  *
00006  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00007  *
00008  *
00009  * IDENTIFICATION
00010  *    src/backend/utils/adt/tsgistidx.c
00011  *
00012  *-------------------------------------------------------------------------
00013  */
00014 
00015 #include "postgres.h"
00016 
00017 #include "access/gist.h"
00018 #include "access/tuptoaster.h"
00019 #include "tsearch/ts_utils.h"
00020 
00021 
00022 #define SIGLENINT  31           /* >121 => key will toast, so it will not work
00023                                  * !!! */
00024 
00025 #define SIGLEN  ( sizeof(int32) * SIGLENINT )
00026 #define SIGLENBIT (SIGLEN * BITS_PER_BYTE)
00027 
00028 typedef char BITVEC[SIGLEN];
00029 typedef char *BITVECP;
00030 
00031 #define LOOPBYTE \
00032             for(i=0;i<SIGLEN;i++)
00033 
00034 #define GETBYTE(x,i) ( *( (BITVECP)(x) + (int)( (i) / BITS_PER_BYTE ) ) )
00035 #define GETBITBYTE(x,i) ( ((char)(x)) >> (i) & 0x01 )
00036 #define CLRBIT(x,i)   GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITS_PER_BYTE ) )
00037 #define SETBIT(x,i)   GETBYTE(x,i) |=  ( 0x01 << ( (i) % BITS_PER_BYTE ) )
00038 #define GETBIT(x,i) ( (GETBYTE(x,i) >> ( (i) % BITS_PER_BYTE )) & 0x01 )
00039 
00040 #define HASHVAL(val) (((unsigned int)(val)) % SIGLENBIT)
00041 #define HASH(sign, val) SETBIT((sign), HASHVAL(val))
00042 
00043 #define GETENTRY(vec,pos) ((SignTSVector *) DatumGetPointer((vec)->vector[(pos)].key))
00044 
00045 /*
00046  * type of GiST index key
00047  */
00048 
00049 typedef struct
00050 {
00051     int32       vl_len_;        /* varlena header (do not touch directly!) */
00052     int32       flag;
00053     char        data[1];
00054 } SignTSVector;
00055 
00056 #define ARRKEY      0x01
00057 #define SIGNKEY     0x02
00058 #define ALLISTRUE   0x04
00059 
00060 #define ISARRKEY(x) ( ((SignTSVector*)(x))->flag & ARRKEY )
00061 #define ISSIGNKEY(x)    ( ((SignTSVector*)(x))->flag & SIGNKEY )
00062 #define ISALLTRUE(x)    ( ((SignTSVector*)(x))->flag & ALLISTRUE )
00063 
00064 #define GTHDRSIZE   ( VARHDRSZ + sizeof(int32) )
00065 #define CALCGTSIZE(flag, len) ( GTHDRSIZE + ( ( (flag) & ARRKEY ) ? ((len)*sizeof(int32)) : (((flag) & ALLISTRUE) ? 0 : SIGLEN) ) )
00066 
00067 #define GETSIGN(x)  ( (BITVECP)( (char*)(x)+GTHDRSIZE ) )
00068 #define GETARR(x)   ( (int32*)( (char*)(x)+GTHDRSIZE ) )
00069 #define ARRNELEM(x) ( ( VARSIZE(x) - GTHDRSIZE )/sizeof(int32) )
00070 
00071 /* Number of one-bits in an unsigned byte */
00072 static const uint8 number_of_ones[256] = {
00073     0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
00074     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
00075     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
00076     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00077     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
00078     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00079     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00080     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
00081     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
00082     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00083     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00084     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
00085     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
00086     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
00087     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
00088     4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
00089 };
00090 
00091 static int32 sizebitvec(BITVECP sign);
00092 
00093 Datum
00094 gtsvectorin(PG_FUNCTION_ARGS)
00095 {
00096     ereport(ERROR,
00097             (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
00098              errmsg("gtsvector_in not implemented")));
00099     PG_RETURN_DATUM(0);
00100 }
00101 
00102 #define SINGOUTSTR  "%d true bits, %d false bits"
00103 #define ARROUTSTR   "%d unique words"
00104 #define EXTRALEN    ( 2*13 )
00105 
00106 static int  outbuf_maxlen = 0;
00107 
00108 Datum
00109 gtsvectorout(PG_FUNCTION_ARGS)
00110 {
00111     SignTSVector *key = (SignTSVector *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_POINTER(0)));
00112     char       *outbuf;
00113 
00114     if (outbuf_maxlen == 0)
00115         outbuf_maxlen = 2 * EXTRALEN + Max(strlen(SINGOUTSTR), strlen(ARROUTSTR)) + 1;
00116     outbuf = palloc(outbuf_maxlen);
00117 
00118     if (ISARRKEY(key))
00119         sprintf(outbuf, ARROUTSTR, (int) ARRNELEM(key));
00120     else
00121     {
00122         int         cnttrue = (ISALLTRUE(key)) ? SIGLENBIT : sizebitvec(GETSIGN(key));
00123 
00124         sprintf(outbuf, SINGOUTSTR, cnttrue, (int) SIGLENBIT - cnttrue);
00125     }
00126 
00127     PG_FREE_IF_COPY(key, 0);
00128     PG_RETURN_POINTER(outbuf);
00129 }
00130 
00131 static int
00132 compareint(const void *va, const void *vb)
00133 {
00134     int32       a = *((const int32 *) va);
00135     int32       b = *((const int32 *) vb);
00136 
00137     if (a == b)
00138         return 0;
00139     return (a > b) ? 1 : -1;
00140 }
00141 
00142 /*
00143  * Removes duplicates from an array of int32. 'l' is
00144  * size of the input array. Returns the new size of the array.
00145  */
00146 static int
00147 uniqueint(int32 *a, int32 l)
00148 {
00149     int32      *ptr,
00150                *res;
00151 
00152     if (l <= 1)
00153         return l;
00154 
00155     ptr = res = a;
00156 
00157     qsort((void *) a, l, sizeof(int32), compareint);
00158 
00159     while (ptr - a < l)
00160         if (*ptr != *res)
00161             *(++res) = *ptr++;
00162         else
00163             ptr++;
00164     return res + 1 - a;
00165 }
00166 
00167 static void
00168 makesign(BITVECP sign, SignTSVector *a)
00169 {
00170     int32       k,
00171                 len = ARRNELEM(a);
00172     int32      *ptr = GETARR(a);
00173 
00174     MemSet((void *) sign, 0, sizeof(BITVEC));
00175     for (k = 0; k < len; k++)
00176         HASH(sign, ptr[k]);
00177 }
00178 
00179 Datum
00180 gtsvector_compress(PG_FUNCTION_ARGS)
00181 {
00182     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
00183     GISTENTRY  *retval = entry;
00184 
00185     if (entry->leafkey)
00186     {                           /* tsvector */
00187         SignTSVector *res;
00188         TSVector    val = DatumGetTSVector(entry->key);
00189         int32       len;
00190         int32      *arr;
00191         WordEntry  *ptr = ARRPTR(val);
00192         char       *words = STRPTR(val);
00193 
00194         len = CALCGTSIZE(ARRKEY, val->size);
00195         res = (SignTSVector *) palloc(len);
00196         SET_VARSIZE(res, len);
00197         res->flag = ARRKEY;
00198         arr = GETARR(res);
00199         len = val->size;
00200         while (len--)
00201         {
00202             pg_crc32    c;
00203 
00204             INIT_CRC32(c);
00205             COMP_CRC32(c, words + ptr->pos, ptr->len);
00206             FIN_CRC32(c);
00207 
00208             *arr = *(int32 *) &c;
00209             arr++;
00210             ptr++;
00211         }
00212 
00213         len = uniqueint(GETARR(res), val->size);
00214         if (len != val->size)
00215         {
00216             /*
00217              * there is a collision of hash-function; len is always less than
00218              * val->size
00219              */
00220             len = CALCGTSIZE(ARRKEY, len);
00221             res = (SignTSVector *) repalloc((void *) res, len);
00222             SET_VARSIZE(res, len);
00223         }
00224 
00225         /* make signature, if array is too long */
00226         if (VARSIZE(res) > TOAST_INDEX_TARGET)
00227         {
00228             SignTSVector *ressign;
00229 
00230             len = CALCGTSIZE(SIGNKEY, 0);
00231             ressign = (SignTSVector *) palloc(len);
00232             SET_VARSIZE(ressign, len);
00233             ressign->flag = SIGNKEY;
00234             makesign(GETSIGN(ressign), res);
00235             res = ressign;
00236         }
00237 
00238         retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
00239         gistentryinit(*retval, PointerGetDatum(res),
00240                       entry->rel, entry->page,
00241                       entry->offset, FALSE);
00242     }
00243     else if (ISSIGNKEY(DatumGetPointer(entry->key)) &&
00244              !ISALLTRUE(DatumGetPointer(entry->key)))
00245     {
00246         int32       i,
00247                     len;
00248         SignTSVector *res;
00249         BITVECP     sign = GETSIGN(DatumGetPointer(entry->key));
00250 
00251         LOOPBYTE
00252         {
00253             if ((sign[i] & 0xff) != 0xff)
00254                 PG_RETURN_POINTER(retval);
00255         }
00256 
00257         len = CALCGTSIZE(SIGNKEY | ALLISTRUE, 0);
00258         res = (SignTSVector *) palloc(len);
00259         SET_VARSIZE(res, len);
00260         res->flag = SIGNKEY | ALLISTRUE;
00261 
00262         retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
00263         gistentryinit(*retval, PointerGetDatum(res),
00264                       entry->rel, entry->page,
00265                       entry->offset, FALSE);
00266     }
00267     PG_RETURN_POINTER(retval);
00268 }
00269 
00270 Datum
00271 gtsvector_decompress(PG_FUNCTION_ARGS)
00272 {
00273     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
00274     SignTSVector *key = (SignTSVector *) DatumGetPointer(PG_DETOAST_DATUM(entry->key));
00275 
00276     if (key != (SignTSVector *) DatumGetPointer(entry->key))
00277     {
00278         GISTENTRY  *retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
00279 
00280         gistentryinit(*retval, PointerGetDatum(key),
00281                       entry->rel, entry->page,
00282                       entry->offset, FALSE);
00283 
00284         PG_RETURN_POINTER(retval);
00285     }
00286 
00287     PG_RETURN_POINTER(entry);
00288 }
00289 
00290 typedef struct
00291 {
00292     int32      *arrb;
00293     int32      *arre;
00294 } CHKVAL;
00295 
00296 /*
00297  * is there value 'val' in array or not ?
00298  */
00299 static bool
00300 checkcondition_arr(void *checkval, QueryOperand *val)
00301 {
00302     int32      *StopLow = ((CHKVAL *) checkval)->arrb;
00303     int32      *StopHigh = ((CHKVAL *) checkval)->arre;
00304     int32      *StopMiddle;
00305 
00306     /* Loop invariant: StopLow <= val < StopHigh */
00307 
00308     /*
00309      * we are not able to find a a prefix by hash value
00310      */
00311     if (val->prefix)
00312         return true;
00313 
00314     while (StopLow < StopHigh)
00315     {
00316         StopMiddle = StopLow + (StopHigh - StopLow) / 2;
00317         if (*StopMiddle == val->valcrc)
00318             return (true);
00319         else if (*StopMiddle < val->valcrc)
00320             StopLow = StopMiddle + 1;
00321         else
00322             StopHigh = StopMiddle;
00323     }
00324 
00325     return (false);
00326 }
00327 
00328 static bool
00329 checkcondition_bit(void *checkval, QueryOperand *val)
00330 {
00331     /*
00332      * we are not able to find a a prefix in signature tree
00333      */
00334     if (val->prefix)
00335         return true;
00336     return GETBIT(checkval, HASHVAL(val->valcrc));
00337 }
00338 
00339 Datum
00340 gtsvector_consistent(PG_FUNCTION_ARGS)
00341 {
00342     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
00343     TSQuery     query = PG_GETARG_TSQUERY(1);
00344 
00345     /* StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); */
00346     /* Oid      subtype = PG_GETARG_OID(3); */
00347     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
00348     SignTSVector *key = (SignTSVector *) DatumGetPointer(entry->key);
00349 
00350     /* All cases served by this function are inexact */
00351     *recheck = true;
00352 
00353     if (!query->size)
00354         PG_RETURN_BOOL(false);
00355 
00356     if (ISSIGNKEY(key))
00357     {
00358         if (ISALLTRUE(key))
00359             PG_RETURN_BOOL(true);
00360 
00361         PG_RETURN_BOOL(TS_execute(
00362                                   GETQUERY(query),
00363                                   (void *) GETSIGN(key), false,
00364                                   checkcondition_bit
00365                                   ));
00366     }
00367     else
00368     {                           /* only leaf pages */
00369         CHKVAL      chkval;
00370 
00371         chkval.arrb = GETARR(key);
00372         chkval.arre = chkval.arrb + ARRNELEM(key);
00373         PG_RETURN_BOOL(TS_execute(
00374                                   GETQUERY(query),
00375                                   (void *) &chkval, true,
00376                                   checkcondition_arr
00377                                   ));
00378     }
00379 }
00380 
00381 static int32
00382 unionkey(BITVECP sbase, SignTSVector *add)
00383 {
00384     int32       i;
00385 
00386     if (ISSIGNKEY(add))
00387     {
00388         BITVECP     sadd = GETSIGN(add);
00389 
00390         if (ISALLTRUE(add))
00391             return 1;
00392 
00393         LOOPBYTE
00394             sbase[i] |= sadd[i];
00395     }
00396     else
00397     {
00398         int32      *ptr = GETARR(add);
00399 
00400         for (i = 0; i < ARRNELEM(add); i++)
00401             HASH(sbase, ptr[i]);
00402     }
00403     return 0;
00404 }
00405 
00406 
00407 Datum
00408 gtsvector_union(PG_FUNCTION_ARGS)
00409 {
00410     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
00411     int        *size = (int *) PG_GETARG_POINTER(1);
00412     BITVEC      base;
00413     int32       i,
00414                 len;
00415     int32       flag = 0;
00416     SignTSVector *result;
00417 
00418     MemSet((void *) base, 0, sizeof(BITVEC));
00419     for (i = 0; i < entryvec->n; i++)
00420     {
00421         if (unionkey(base, GETENTRY(entryvec, i)))
00422         {
00423             flag = ALLISTRUE;
00424             break;
00425         }
00426     }
00427 
00428     flag |= SIGNKEY;
00429     len = CALCGTSIZE(flag, 0);
00430     result = (SignTSVector *) palloc(len);
00431     *size = len;
00432     SET_VARSIZE(result, len);
00433     result->flag = flag;
00434     if (!ISALLTRUE(result))
00435         memcpy((void *) GETSIGN(result), (void *) base, sizeof(BITVEC));
00436 
00437     PG_RETURN_POINTER(result);
00438 }
00439 
00440 Datum
00441 gtsvector_same(PG_FUNCTION_ARGS)
00442 {
00443     SignTSVector *a = (SignTSVector *) PG_GETARG_POINTER(0);
00444     SignTSVector *b = (SignTSVector *) PG_GETARG_POINTER(1);
00445     bool       *result = (bool *) PG_GETARG_POINTER(2);
00446 
00447     if (ISSIGNKEY(a))
00448     {                           /* then b also ISSIGNKEY */
00449         if (ISALLTRUE(a) && ISALLTRUE(b))
00450             *result = true;
00451         else if (ISALLTRUE(a))
00452             *result = false;
00453         else if (ISALLTRUE(b))
00454             *result = false;
00455         else
00456         {
00457             int32       i;
00458             BITVECP     sa = GETSIGN(a),
00459                         sb = GETSIGN(b);
00460 
00461             *result = true;
00462             LOOPBYTE
00463             {
00464                 if (sa[i] != sb[i])
00465                 {
00466                     *result = false;
00467                     break;
00468                 }
00469             }
00470         }
00471     }
00472     else
00473     {                           /* a and b ISARRKEY */
00474         int32       lena = ARRNELEM(a),
00475                     lenb = ARRNELEM(b);
00476 
00477         if (lena != lenb)
00478             *result = false;
00479         else
00480         {
00481             int32      *ptra = GETARR(a),
00482                        *ptrb = GETARR(b);
00483             int32       i;
00484 
00485             *result = true;
00486             for (i = 0; i < lena; i++)
00487                 if (ptra[i] != ptrb[i])
00488                 {
00489                     *result = false;
00490                     break;
00491                 }
00492         }
00493     }
00494 
00495     PG_RETURN_POINTER(result);
00496 }
00497 
00498 static int32
00499 sizebitvec(BITVECP sign)
00500 {
00501     int32       size = 0,
00502                 i;
00503 
00504     LOOPBYTE
00505         size += number_of_ones[(unsigned char) sign[i]];
00506     return size;
00507 }
00508 
00509 static int
00510 hemdistsign(BITVECP a, BITVECP b)
00511 {
00512     int         i,
00513                 diff,
00514                 dist = 0;
00515 
00516     LOOPBYTE
00517     {
00518         diff = (unsigned char) (a[i] ^ b[i]);
00519         dist += number_of_ones[diff];
00520     }
00521     return dist;
00522 }
00523 
00524 static int
00525 hemdist(SignTSVector *a, SignTSVector *b)
00526 {
00527     if (ISALLTRUE(a))
00528     {
00529         if (ISALLTRUE(b))
00530             return 0;
00531         else
00532             return SIGLENBIT - sizebitvec(GETSIGN(b));
00533     }
00534     else if (ISALLTRUE(b))
00535         return SIGLENBIT - sizebitvec(GETSIGN(a));
00536 
00537     return hemdistsign(GETSIGN(a), GETSIGN(b));
00538 }
00539 
00540 Datum
00541 gtsvector_penalty(PG_FUNCTION_ARGS)
00542 {
00543     GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
00544     GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
00545     float      *penalty = (float *) PG_GETARG_POINTER(2);
00546     SignTSVector *origval = (SignTSVector *) DatumGetPointer(origentry->key);
00547     SignTSVector *newval = (SignTSVector *) DatumGetPointer(newentry->key);
00548     BITVECP     orig = GETSIGN(origval);
00549 
00550     *penalty = 0.0;
00551 
00552     if (ISARRKEY(newval))
00553     {
00554         BITVEC      sign;
00555 
00556         makesign(sign, newval);
00557 
00558         if (ISALLTRUE(origval))
00559             *penalty = ((float) (SIGLENBIT - sizebitvec(sign))) / (float) (SIGLENBIT + 1);
00560         else
00561             *penalty = hemdistsign(sign, orig);
00562     }
00563     else
00564         *penalty = hemdist(origval, newval);
00565     PG_RETURN_POINTER(penalty);
00566 }
00567 
00568 typedef struct
00569 {
00570     bool        allistrue;
00571     BITVEC      sign;
00572 } CACHESIGN;
00573 
00574 static void
00575 fillcache(CACHESIGN *item, SignTSVector *key)
00576 {
00577     item->allistrue = false;
00578     if (ISARRKEY(key))
00579         makesign(item->sign, key);
00580     else if (ISALLTRUE(key))
00581         item->allistrue = true;
00582     else
00583         memcpy((void *) item->sign, (void *) GETSIGN(key), sizeof(BITVEC));
00584 }
00585 
00586 #define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
00587 typedef struct
00588 {
00589     OffsetNumber pos;
00590     int32       cost;
00591 } SPLITCOST;
00592 
00593 static int
00594 comparecost(const void *va, const void *vb)
00595 {
00596     const SPLITCOST *a = (const SPLITCOST *) va;
00597     const SPLITCOST *b = (const SPLITCOST *) vb;
00598 
00599     if (a->cost == b->cost)
00600         return 0;
00601     else
00602         return (a->cost > b->cost) ? 1 : -1;
00603 }
00604 
00605 
00606 static int
00607 hemdistcache(CACHESIGN *a, CACHESIGN *b)
00608 {
00609     if (a->allistrue)
00610     {
00611         if (b->allistrue)
00612             return 0;
00613         else
00614             return SIGLENBIT - sizebitvec(b->sign);
00615     }
00616     else if (b->allistrue)
00617         return SIGLENBIT - sizebitvec(a->sign);
00618 
00619     return hemdistsign(a->sign, b->sign);
00620 }
00621 
00622 Datum
00623 gtsvector_picksplit(PG_FUNCTION_ARGS)
00624 {
00625     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
00626     GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
00627     OffsetNumber k,
00628                 j;
00629     SignTSVector *datum_l,
00630                *datum_r;
00631     BITVECP     union_l,
00632                 union_r;
00633     int32       size_alpha,
00634                 size_beta;
00635     int32       size_waste,
00636                 waste = -1;
00637     int32       nbytes;
00638     OffsetNumber seed_1 = 0,
00639                 seed_2 = 0;
00640     OffsetNumber *left,
00641                *right;
00642     OffsetNumber maxoff;
00643     BITVECP     ptr;
00644     int         i;
00645     CACHESIGN  *cache;
00646     SPLITCOST  *costvector;
00647 
00648     maxoff = entryvec->n - 2;
00649     nbytes = (maxoff + 2) * sizeof(OffsetNumber);
00650     v->spl_left = (OffsetNumber *) palloc(nbytes);
00651     v->spl_right = (OffsetNumber *) palloc(nbytes);
00652 
00653     cache = (CACHESIGN *) palloc(sizeof(CACHESIGN) * (maxoff + 2));
00654     fillcache(&cache[FirstOffsetNumber], GETENTRY(entryvec, FirstOffsetNumber));
00655 
00656     for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
00657     {
00658         for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
00659         {
00660             if (k == FirstOffsetNumber)
00661                 fillcache(&cache[j], GETENTRY(entryvec, j));
00662 
00663             size_waste = hemdistcache(&(cache[j]), &(cache[k]));
00664             if (size_waste > waste)
00665             {
00666                 waste = size_waste;
00667                 seed_1 = k;
00668                 seed_2 = j;
00669             }
00670         }
00671     }
00672 
00673     left = v->spl_left;
00674     v->spl_nleft = 0;
00675     right = v->spl_right;
00676     v->spl_nright = 0;
00677 
00678     if (seed_1 == 0 || seed_2 == 0)
00679     {
00680         seed_1 = 1;
00681         seed_2 = 2;
00682     }
00683 
00684     /* form initial .. */
00685     if (cache[seed_1].allistrue)
00686     {
00687         datum_l = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
00688         SET_VARSIZE(datum_l, CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
00689         datum_l->flag = SIGNKEY | ALLISTRUE;
00690     }
00691     else
00692     {
00693         datum_l = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY, 0));
00694         SET_VARSIZE(datum_l, CALCGTSIZE(SIGNKEY, 0));
00695         datum_l->flag = SIGNKEY;
00696         memcpy((void *) GETSIGN(datum_l), (void *) cache[seed_1].sign, sizeof(BITVEC));
00697     }
00698     if (cache[seed_2].allistrue)
00699     {
00700         datum_r = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
00701         SET_VARSIZE(datum_r, CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
00702         datum_r->flag = SIGNKEY | ALLISTRUE;
00703     }
00704     else
00705     {
00706         datum_r = (SignTSVector *) palloc(CALCGTSIZE(SIGNKEY, 0));
00707         SET_VARSIZE(datum_r, CALCGTSIZE(SIGNKEY, 0));
00708         datum_r->flag = SIGNKEY;
00709         memcpy((void *) GETSIGN(datum_r), (void *) cache[seed_2].sign, sizeof(BITVEC));
00710     }
00711 
00712     union_l = GETSIGN(datum_l);
00713     union_r = GETSIGN(datum_r);
00714     maxoff = OffsetNumberNext(maxoff);
00715     fillcache(&cache[maxoff], GETENTRY(entryvec, maxoff));
00716     /* sort before ... */
00717     costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
00718     for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
00719     {
00720         costvector[j - 1].pos = j;
00721         size_alpha = hemdistcache(&(cache[seed_1]), &(cache[j]));
00722         size_beta = hemdistcache(&(cache[seed_2]), &(cache[j]));
00723         costvector[j - 1].cost = Abs(size_alpha - size_beta);
00724     }
00725     qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
00726 
00727     for (k = 0; k < maxoff; k++)
00728     {
00729         j = costvector[k].pos;
00730         if (j == seed_1)
00731         {
00732             *left++ = j;
00733             v->spl_nleft++;
00734             continue;
00735         }
00736         else if (j == seed_2)
00737         {
00738             *right++ = j;
00739             v->spl_nright++;
00740             continue;
00741         }
00742 
00743         if (ISALLTRUE(datum_l) || cache[j].allistrue)
00744         {
00745             if (ISALLTRUE(datum_l) && cache[j].allistrue)
00746                 size_alpha = 0;
00747             else
00748                 size_alpha = SIGLENBIT - sizebitvec(
00749                                                     (cache[j].allistrue) ? GETSIGN(datum_l) : GETSIGN(cache[j].sign)
00750                     );
00751         }
00752         else
00753             size_alpha = hemdistsign(cache[j].sign, GETSIGN(datum_l));
00754 
00755         if (ISALLTRUE(datum_r) || cache[j].allistrue)
00756         {
00757             if (ISALLTRUE(datum_r) && cache[j].allistrue)
00758                 size_beta = 0;
00759             else
00760                 size_beta = SIGLENBIT - sizebitvec(
00761                                                    (cache[j].allistrue) ? GETSIGN(datum_r) : GETSIGN(cache[j].sign)
00762                     );
00763         }
00764         else
00765             size_beta = hemdistsign(cache[j].sign, GETSIGN(datum_r));
00766 
00767         if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.1))
00768         {
00769             if (ISALLTRUE(datum_l) || cache[j].allistrue)
00770             {
00771                 if (!ISALLTRUE(datum_l))
00772                     MemSet((void *) GETSIGN(datum_l), 0xff, sizeof(BITVEC));
00773             }
00774             else
00775             {
00776                 ptr = cache[j].sign;
00777                 LOOPBYTE
00778                     union_l[i] |= ptr[i];
00779             }
00780             *left++ = j;
00781             v->spl_nleft++;
00782         }
00783         else
00784         {
00785             if (ISALLTRUE(datum_r) || cache[j].allistrue)
00786             {
00787                 if (!ISALLTRUE(datum_r))
00788                     MemSet((void *) GETSIGN(datum_r), 0xff, sizeof(BITVEC));
00789             }
00790             else
00791             {
00792                 ptr = cache[j].sign;
00793                 LOOPBYTE
00794                     union_r[i] |= ptr[i];
00795             }
00796             *right++ = j;
00797             v->spl_nright++;
00798         }
00799     }
00800 
00801     *right = *left = FirstOffsetNumber;
00802     v->spl_ldatum = PointerGetDatum(datum_l);
00803     v->spl_rdatum = PointerGetDatum(datum_r);
00804 
00805     PG_RETURN_POINTER(v);
00806 }