← Back to branch summary

~vcs-imports/mammoth-replicator/trunk

« back to all changes in this revision

Viewing changes to contrib/tsearch/gistidx.c

  • Committer: alvherre
  • Date: 2005-12-16 21:24:52 UTC
  • Revision ID: svn-v4:db760fc0-0f08-0410-9d63-cc6633f64896:trunk:1
Initial import of the REL8_0_3 sources from the Pgsql CVS repository.

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/tsearch/gistidx.c
 
1
#include "postgres.h"
 
2
 
 
3
#include <float.h>
 
4
 
 
5
#include "access/gist.h"
 
6
#include "access/itup.h"
 
7
#include "access/rtree.h"
 
8
#include "utils/array.h"
 
9
#include "utils/builtins.h"
 
10
#include "storage/bufpage.h"
 
11
#include "access/tuptoaster.h"
 
12
 
 
13
#include "txtidx.h"
 
14
#include "query.h"
 
15
#include "gistidx.h"
 
16
#include "crc32.h"
 
17
 
 
18
PG_FUNCTION_INFO_V1(gtxtidx_in);
 
19
Datum           gtxtidx_in(PG_FUNCTION_ARGS);
 
20
 
 
21
PG_FUNCTION_INFO_V1(gtxtidx_out);
 
22
Datum           gtxtidx_out(PG_FUNCTION_ARGS);
 
23
 
 
24
PG_FUNCTION_INFO_V1(gtxtidx_compress);
 
25
Datum           gtxtidx_compress(PG_FUNCTION_ARGS);
 
26
 
 
27
PG_FUNCTION_INFO_V1(gtxtidx_decompress);
 
28
Datum           gtxtidx_decompress(PG_FUNCTION_ARGS);
 
29
 
 
30
PG_FUNCTION_INFO_V1(gtxtidx_consistent);
 
31
Datum           gtxtidx_consistent(PG_FUNCTION_ARGS);
 
32
 
 
33
PG_FUNCTION_INFO_V1(gtxtidx_union);
 
34
Datum           gtxtidx_union(PG_FUNCTION_ARGS);
 
35
 
 
36
PG_FUNCTION_INFO_V1(gtxtidx_same);
 
37
Datum           gtxtidx_same(PG_FUNCTION_ARGS);
 
38
 
 
39
PG_FUNCTION_INFO_V1(gtxtidx_penalty);
 
40
Datum           gtxtidx_penalty(PG_FUNCTION_ARGS);
 
41
 
 
42
PG_FUNCTION_INFO_V1(gtxtidx_picksplit);
 
43
Datum           gtxtidx_picksplit(PG_FUNCTION_ARGS);
 
44
 
 
45
#define GETENTRY(vec,pos) ((GISTTYPE *) DatumGetPointer((vec)->vector[(pos)].key))
 
46
#define SUMBIT(val) (            \
 
47
        GETBITBYTE(val,0) + \
 
48
        GETBITBYTE(val,1) + \
 
49
        GETBITBYTE(val,2) + \
 
50
        GETBITBYTE(val,3) + \
 
51
        GETBITBYTE(val,4) + \
 
52
        GETBITBYTE(val,5) + \
 
53
        GETBITBYTE(val,6) + \
 
54
        GETBITBYTE(val,7)       \
 
55
)
 
56
 
 
57
 
 
58
Datum
 
59
gtxtidx_in(PG_FUNCTION_ARGS)
 
60
{
 
61
        ereport(ERROR,
 
62
                        (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 
63
                         errmsg("gtxtidx_in not implemented")));
 
64
        PG_RETURN_DATUM(0);
 
65
}
 
66
 
 
67
Datum
 
68
gtxtidx_out(PG_FUNCTION_ARGS)
 
69
{
 
70
        ereport(ERROR,
 
71
                        (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 
72
                         errmsg("gtxtidx_out not implemented")));
 
73
        PG_RETURN_DATUM(0);
 
74
}
 
75
 
 
76
static int
 
77
compareint(const void *a, const void *b)
 
78
{
 
79
        if (*((int4 *) a) == *((int4 *) b))
 
80
                return 0;
 
81
        return (*((int4 *) a) > *((int4 *) b)) ? 1 : -1;
 
82
}
 
83
 
 
84
static int
 
85
uniqueint(int4 *a, int4 l)
 
86
{
 
87
        int4       *ptr,
 
88
                           *res;
 
89
 
 
90
        if (l == 1)
 
91
                return l;
 
92
 
 
93
        ptr = res = a;
 
94
 
 
95
        qsort((void *) a, l, sizeof(int4), compareint);
 
96
 
 
97
        while (ptr - a < l)
 
98
                if (*ptr != *res)
 
99
                        *(++res) = *ptr++;
 
100
                else
 
101
                        ptr++;
 
102
        return res + 1 - a;
 
103
}
 
104
 
 
105
static void
 
106
makesign(BITVECP sign, GISTTYPE * a)
 
107
{
 
108
        int4            k,
 
109
                                len = ARRNELEM(a);
 
110
        int4       *ptr = GETARR(a);
 
111
 
 
112
        MemSet((void *) sign, 0, sizeof(BITVEC));
 
113
        for (k = 0; k < len; k++)
 
114
                HASH(sign, ptr[k]);
 
115
}
 
116
 
 
117
Datum
 
118
gtxtidx_compress(PG_FUNCTION_ARGS)
 
119
{
 
120
        GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 
121
        GISTENTRY  *retval = entry;
 
122
 
 
123
        if (entry->leafkey)
 
124
        {                                                       /* txtidx */
 
125
                GISTTYPE   *res;
 
126
                txtidx     *toastedval = (txtidx *) DatumGetPointer(entry->key);
 
127
                txtidx     *val = (txtidx *) DatumGetPointer(PG_DETOAST_DATUM(entry->key));
 
128
                int4            len;
 
129
                int4       *arr;
 
130
                WordEntry  *ptr = ARRPTR(val);
 
131
                char       *words = STRPTR(val);
 
132
 
 
133
                len = CALCGTSIZE(ARRKEY, val->size);
 
134
                res = (GISTTYPE *) palloc(len);
 
135
                res->len = len;
 
136
                res->flag = ARRKEY;
 
137
                arr = GETARR(res);
 
138
                len = val->size;
 
139
                while (len--)
 
140
                {
 
141
                        *arr = crc32_sz((uint8 *) &words[ptr->pos], ptr->len);
 
142
                        arr++;
 
143
                        ptr++;
 
144
                }
 
145
 
 
146
                len = uniqueint(GETARR(res), val->size);
 
147
                if (len != val->size)
 
148
                {
 
149
                        /*
 
150
                         * there is a collision of hash-function; len is always less
 
151
                         * than val->size
 
152
                         */
 
153
                        len = CALCGTSIZE(ARRKEY, len);
 
154
                        res = (GISTTYPE *) repalloc((void *) res, len);
 
155
                        res->len = len;
 
156
                }
 
157
                if (val != toastedval)
 
158
                        pfree(val);
 
159
 
 
160
                /* make signature, if array is too long */
 
161
                if (res->len > TOAST_INDEX_TARGET)
 
162
                {
 
163
                        GISTTYPE   *ressign;
 
164
 
 
165
                        len = CALCGTSIZE(SIGNKEY, 0);
 
166
                        ressign = (GISTTYPE *) palloc(len);
 
167
                        ressign->len = len;
 
168
                        ressign->flag = SIGNKEY;
 
169
                        makesign(GETSIGN(ressign), res);
 
170
                        pfree(res);
 
171
                        res = ressign;
 
172
                }
 
173
 
 
174
                retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
 
175
                gistentryinit(*retval, PointerGetDatum(res),
 
176
                                          entry->rel, entry->page,
 
177
                                          entry->offset, res->len, FALSE);
 
178
        }
 
179
        else if (ISSIGNKEY(DatumGetPointer(entry->key)) &&
 
180
                         !ISALLTRUE(DatumGetPointer(entry->key)))
 
181
        {
 
182
                int4            i,
 
183
                                        len;
 
184
                GISTTYPE   *res;
 
185
                BITVECP         sign = GETSIGN(DatumGetPointer(entry->key));
 
186
 
 
187
                LOOPBYTE(
 
188
                                 if ((sign[i] & 0xff) != 0xff)
 
189
                                 PG_RETURN_POINTER(retval);
 
190
                );
 
191
 
 
192
                len = CALCGTSIZE(SIGNKEY | ALLISTRUE, 0);
 
193
                res = (GISTTYPE *) palloc(len);
 
194
                res->len = len;
 
195
                res->flag = SIGNKEY | ALLISTRUE;
 
196
 
 
197
                retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
 
198
                gistentryinit(*retval, PointerGetDatum(res),
 
199
                                          entry->rel, entry->page,
 
200
                                          entry->offset, res->len, FALSE);
 
201
        }
 
202
        PG_RETURN_POINTER(retval);
 
203
}
 
204
 
 
205
Datum
 
206
gtxtidx_decompress(PG_FUNCTION_ARGS)
 
207
{
 
208
        GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 
209
        GISTTYPE   *key = (GISTTYPE *) DatumGetPointer(PG_DETOAST_DATUM(entry->key));
 
210
 
 
211
        if (key != (GISTTYPE *) DatumGetPointer(entry->key))
 
212
        {
 
213
                GISTENTRY  *retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
 
214
 
 
215
                gistentryinit(*retval, PointerGetDatum(key),
 
216
                                          entry->rel, entry->page,
 
217
                                          entry->offset, key->len, FALSE);
 
218
 
 
219
                PG_RETURN_POINTER(retval);
 
220
        }
 
221
 
 
222
        PG_RETURN_POINTER(entry);
 
223
}
 
224
 
 
225
typedef struct
 
226
{
 
227
        int4       *arrb;
 
228
        int4       *arre;
 
229
}       CHKVAL;
 
230
 
 
231
/*
 
232
 * is there value 'val' in array or not ?
 
233
 */
 
234
static bool
 
235
checkcondition_arr(void *checkval, ITEM * val)
 
236
{
 
237
        int4       *StopLow = ((CHKVAL *) checkval)->arrb;
 
238
        int4       *StopHigh = ((CHKVAL *) checkval)->arre;
 
239
        int4       *StopMiddle;
 
240
 
 
241
        /* Loop invariant: StopLow <= val < StopHigh */
 
242
 
 
243
        while (StopLow < StopHigh)
 
244
        {
 
245
                StopMiddle = StopLow + (StopHigh - StopLow) / 2;
 
246
                if (*StopMiddle == val->val)
 
247
                        return (true);
 
248
                else if (*StopMiddle < val->val)
 
249
                        StopLow = StopMiddle + 1;
 
250
                else
 
251
                        StopHigh = StopMiddle;
 
252
        }
 
253
 
 
254
        return (false);
 
255
}
 
256
 
 
257
static bool
 
258
checkcondition_bit(void *checkval, ITEM * val)
 
259
{
 
260
        return GETBIT(checkval, HASHVAL(val->val));
 
261
}
 
262
 
 
263
Datum
 
264
gtxtidx_consistent(PG_FUNCTION_ARGS)
 
265
{
 
266
        QUERYTYPE  *query = (QUERYTYPE *) PG_GETARG_POINTER(1);
 
267
        GISTTYPE   *key = (GISTTYPE *) DatumGetPointer(
 
268
                                                                ((GISTENTRY *) PG_GETARG_POINTER(0))->key
 
269
        );
 
270
 
 
271
        if (!query->size)
 
272
                PG_RETURN_BOOL(false);
 
273
 
 
274
        if (ISSIGNKEY(key))
 
275
        {
 
276
                if (ISALLTRUE(key))
 
277
                        PG_RETURN_BOOL(true);
 
278
 
 
279
                PG_RETURN_BOOL(execute(
 
280
                                                           GETQUERY(query),
 
281
                                                           (void *) GETSIGN(key), false,
 
282
                                                           checkcondition_bit
 
283
                                                           ));
 
284
        }
 
285
        else
 
286
        {                                                       /* only leaf pages */
 
287
                CHKVAL          chkval;
 
288
 
 
289
                chkval.arrb = GETARR(key);
 
290
                chkval.arre = chkval.arrb + ARRNELEM(key);
 
291
                PG_RETURN_BOOL(execute(
 
292
                                                           GETQUERY(query),
 
293
                                                           (void *) &chkval, true,
 
294
                                                           checkcondition_arr
 
295
                                                           ));
 
296
        }
 
297
}
 
298
 
 
299
static int4
 
300
unionkey(BITVECP sbase, GISTTYPE * add)
 
301
{
 
302
        int4            i;
 
303
 
 
304
        if (ISSIGNKEY(add))
 
305
        {
 
306
                BITVECP         sadd = GETSIGN(add);
 
307
 
 
308
                if (ISALLTRUE(add))
 
309
                        return 1;
 
310
 
 
311
                LOOPBYTE(
 
312
                                 sbase[i] |= sadd[i];
 
313
                );
 
314
        }
 
315
        else
 
316
        {
 
317
                int4       *ptr = GETARR(add);
 
318
 
 
319
                for (i = 0; i < ARRNELEM(add); i++)
 
320
                        HASH(sbase, ptr[i]);
 
321
        }
 
322
        return 0;
 
323
}
 
324
 
 
325
 
 
326
Datum
 
327
gtxtidx_union(PG_FUNCTION_ARGS)
 
328
{
 
329
        GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 
330
        int                *size = (int *) PG_GETARG_POINTER(1);
 
331
        BITVEC          base;
 
332
        int4            i,
 
333
                                len;
 
334
        int4            flag = 0;
 
335
        GISTTYPE   *result;
 
336
 
 
337
        MemSet((void *) base, 0, sizeof(BITVEC));
 
338
        for (i = 0; i < entryvec->n; i++)
 
339
        {
 
340
                if (unionkey(base, GETENTRY(entryvec, i)))
 
341
                {
 
342
                        flag = ALLISTRUE;
 
343
                        break;
 
344
                }
 
345
        }
 
346
 
 
347
        flag |= SIGNKEY;
 
348
        len = CALCGTSIZE(flag, 0);
 
349
        result = (GISTTYPE *) palloc(len);
 
350
        *size = result->len = len;
 
351
        result->flag = flag;
 
352
        if (!ISALLTRUE(result))
 
353
                memcpy((void *) GETSIGN(result), (void *) base, sizeof(BITVEC));
 
354
 
 
355
        PG_RETURN_POINTER(result);
 
356
}
 
357
 
 
358
Datum
 
359
gtxtidx_same(PG_FUNCTION_ARGS)
 
360
{
 
361
        GISTTYPE   *a = (GISTTYPE *) PG_GETARG_POINTER(0);
 
362
        GISTTYPE   *b = (GISTTYPE *) PG_GETARG_POINTER(1);
 
363
        bool       *result = (bool *) PG_GETARG_POINTER(2);
 
364
 
 
365
        if (ISSIGNKEY(a))
 
366
        {                                                       /* then b also ISSIGNKEY */
 
367
                if (ISALLTRUE(a) && ISALLTRUE(b))
 
368
                        *result = true;
 
369
                else if (ISALLTRUE(a))
 
370
                        *result = false;
 
371
                else if (ISALLTRUE(b))
 
372
                        *result = false;
 
373
                else
 
374
                {
 
375
                        int4            i;
 
376
                        BITVECP         sa = GETSIGN(a),
 
377
                                                sb = GETSIGN(b);
 
378
 
 
379
                        *result = true;
 
380
                        LOOPBYTE(
 
381
                                         if (sa[i] != sb[i])
 
382
                                         {
 
383
                                *result = false;
 
384
                                break;
 
385
                        }
 
386
                        );
 
387
                }
 
388
        }
 
389
        else
 
390
        {                                                       /* a and b ISARRKEY */
 
391
                int4            lena = ARRNELEM(a),
 
392
                                        lenb = ARRNELEM(b);
 
393
 
 
394
                if (lena != lenb)
 
395
                        *result = false;
 
396
                else
 
397
                {
 
398
                        int4       *ptra = GETARR(a),
 
399
                                           *ptrb = GETARR(b);
 
400
                        int4            i;
 
401
 
 
402
                        *result = true;
 
403
                        for (i = 0; i < lena; i++)
 
404
                                if (ptra[i] != ptrb[i])
 
405
                                {
 
406
                                        *result = false;
 
407
                                        break;
 
408
                                }
 
409
                }
 
410
        }
 
411
 
 
412
        PG_RETURN_POINTER(result);
 
413
}
 
414
 
 
415
static int4
 
416
sizebitvec(BITVECP sign)
 
417
{
 
418
        int4            size = 0,
 
419
                                i;
 
420
 
 
421
        LOOPBYTE(
 
422
                         size += SUMBIT(*(char *) sign);
 
423
        sign = (BITVECP) (((char *) sign) + 1);
 
424
        );
 
425
        return size;
 
426
}
 
427
 
 
428
Datum
 
429
gtxtidx_penalty(PG_FUNCTION_ARGS)
 
430
{
 
431
        GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
 
432
        GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
 
433
        float      *penalty = (float *) PG_GETARG_POINTER(2);
 
434
        GISTTYPE   *origval = (GISTTYPE *) DatumGetPointer(origentry->key);
 
435
        GISTTYPE   *newval = (GISTTYPE *) DatumGetPointer(newentry->key);
 
436
        int4            unionsize = 0;
 
437
        BITVECP         orig = GETSIGN(origval);
 
438
 
 
439
        if (ISALLTRUE(origval))
 
440
        {
 
441
                *penalty = 0.0;
 
442
                PG_RETURN_POINTER(penalty);
 
443
        }
 
444
 
 
445
        if (ISARRKEY(newval))
 
446
        {
 
447
                int4       *ptr = GETARR(newval),
 
448
                                        n = ARRNELEM(newval);
 
449
 
 
450
                while (n--)
 
451
                {
 
452
                        if (GETBIT(orig, HASHVAL(*ptr)) == 0)
 
453
                                unionsize++;
 
454
                        ptr++;
 
455
                }
 
456
                *penalty = (float) unionsize;
 
457
        }
 
458
        else
 
459
        {
 
460
                if (ISALLTRUE(newval))
 
461
                        *penalty = (float) (SIGLENBIT - sizebitvec(orig));
 
462
                else
 
463
                {
 
464
                        char            valtmp;
 
465
                        BITVECP         nval = GETSIGN(newval);
 
466
                        int4            i;
 
467
 
 
468
                        LOOPBYTE(
 
469
                                         valtmp = nval[i] | orig[i];
 
470
                        unionsize += SUMBIT(valtmp) - SUMBIT(orig[i]);
 
471
                        );
 
472
                        *penalty = (float) unionsize;
 
473
                }
 
474
        }
 
475
 
 
476
        PG_RETURN_POINTER(penalty);
 
477
}
 
478
 
 
479
typedef struct
 
480
{
 
481
        bool            allistrue;
 
482
        BITVEC          sign;
 
483
}       CACHESIGN;
 
484
 
 
485
static void
 
486
fillcache(CACHESIGN * item, GISTTYPE * key)
 
487
{
 
488
        item->allistrue = false;
 
489
        if (ISARRKEY(key))
 
490
                makesign(item->sign, key);
 
491
        else if (ISALLTRUE(key))
 
492
                item->allistrue = true;
 
493
        else
 
494
                memcpy((void *) item->sign, (void *) GETSIGN(key), sizeof(BITVEC));
 
495
}
 
496
 
 
497
#define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
 
498
typedef struct
 
499
{
 
500
        OffsetNumber pos;
 
501
        int4            cost;
 
502
} SPLITCOST;
 
503
 
 
504
static int
 
505
comparecost(const void *a, const void *b)
 
506
{
 
507
        if (((SPLITCOST *) a)->cost == ((SPLITCOST *) b)->cost)
 
508
                return 0;
 
509
        else
 
510
                return (((SPLITCOST *) a)->cost > ((SPLITCOST *) b)->cost) ? 1 : -1;
 
511
}
 
512
 
 
513
Datum
 
514
gtxtidx_picksplit(PG_FUNCTION_ARGS)
 
515
{
 
516
        GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 
517
        GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
 
518
        OffsetNumber k,
 
519
                                j;
 
520
        GISTTYPE   *datum_l,
 
521
                           *datum_r;
 
522
        BITVEC          union_l,
 
523
                                union_r;
 
524
        bool            firsttime = true;
 
525
        int4            size_alpha,
 
526
                                size_beta,
 
527
                                sizeu,
 
528
                                sizei;
 
529
        int4            size_waste,
 
530
                                waste = 0.0;
 
531
        int4            size_l,
 
532
                                size_r;
 
533
        int4            nbytes;
 
534
        OffsetNumber seed_1 = 0,
 
535
                                seed_2 = 0;
 
536
        OffsetNumber *left,
 
537
                           *right;
 
538
        OffsetNumber maxoff;
 
539
        BITVECP         ptra,
 
540
                                ptrb,
 
541
                                ptrc;
 
542
        int                     i;
 
543
        CACHESIGN  *cache;
 
544
        char            valtmp;
 
545
        SPLITCOST  *costvector;
 
546
 
 
547
        maxoff = entryvec->n - 2;
 
548
        nbytes = (maxoff + 2) * sizeof(OffsetNumber);
 
549
        v->spl_left = (OffsetNumber *) palloc(nbytes);
 
550
        v->spl_right = (OffsetNumber *) palloc(nbytes);
 
551
 
 
552
        cache = (CACHESIGN *) palloc(sizeof(CACHESIGN) * (maxoff + 2));
 
553
        fillcache(&cache[FirstOffsetNumber], GETENTRY(entryvec, FirstOffsetNumber));
 
554
 
 
555
        for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
 
556
        {
 
557
                for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
 
558
                {
 
559
                        if (k == FirstOffsetNumber)
 
560
                                fillcache(&cache[j], GETENTRY(entryvec, j));
 
561
 
 
562
                        if (cache[k].allistrue || cache[j].allistrue)
 
563
                        {
 
564
                                sizeu = SIGLENBIT;
 
565
                                if (cache[k].allistrue && cache[j].allistrue)
 
566
                                        sizei = SIGLENBIT;
 
567
                                else
 
568
                                        sizei = (cache[k].allistrue) ?
 
569
                                                sizebitvec(cache[j].sign) : sizebitvec(cache[k].sign);
 
570
                        }
 
571
                        else
 
572
                        {
 
573
                                sizeu = sizei = 0;
 
574
                                ptra = cache[j].sign;
 
575
                                ptrb = cache[k].sign;
 
576
                                /* critical section for bench !!! */
 
577
 
 
578
#define COUNT(pos) do { \
 
579
        if ( GETBITBYTE(*(char*)ptra,pos) ) { \
 
580
                sizeu++; \
 
581
                if ( GETBITBYTE(*(char*)ptrb, pos) ) \
 
582
                        sizei++; \
 
583
        } else if ( GETBITBYTE(*(char*)ptrb, pos) ) \
 
584
                sizeu++; \
 
585
} while(0)
 
586
                                LOOPBYTE(
 
587
                                                 COUNT(0);
 
588
                                COUNT(1);
 
589
                                COUNT(2);
 
590
                                COUNT(3);
 
591
                                COUNT(4);
 
592
                                COUNT(5);
 
593
                                COUNT(6);
 
594
                                COUNT(7);
 
595
                                ptra = (BITVECP) (((char *) ptra) + 1);
 
596
                                ptrb = (BITVECP) (((char *) ptrb) + 1);
 
597
                                );
 
598
 
 
599
                        }
 
600
                        size_waste = sizeu - sizei;
 
601
                        if (size_waste > waste || firsttime)
 
602
                        {
 
603
                                waste = size_waste;
 
604
                                seed_1 = k;
 
605
                                seed_2 = j;
 
606
                                firsttime = false;
 
607
                        }
 
608
                }
 
609
        }
 
610
 
 
611
        left = v->spl_left;
 
612
        v->spl_nleft = 0;
 
613
        right = v->spl_right;
 
614
        v->spl_nright = 0;
 
615
 
 
616
        if (seed_1 == 0 || seed_2 == 0)
 
617
        {
 
618
                seed_1 = 1;
 
619
                seed_2 = 2;
 
620
        }
 
621
 
 
622
        /* form initial .. */
 
623
        if (cache[seed_1].allistrue)
 
624
        {
 
625
                datum_l = (GISTTYPE *) palloc(CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
 
626
                datum_l->len = CALCGTSIZE(SIGNKEY | ALLISTRUE, 0);
 
627
                datum_l->flag = SIGNKEY | ALLISTRUE;
 
628
                size_l = SIGLENBIT;
 
629
        }
 
630
        else
 
631
        {
 
632
                datum_l = (GISTTYPE *) palloc(CALCGTSIZE(SIGNKEY, 0));
 
633
                datum_l->len = CALCGTSIZE(SIGNKEY, 0);
 
634
                datum_l->flag = SIGNKEY;
 
635
                memcpy((void *) GETSIGN(datum_l), (void *) cache[seed_1].sign, sizeof(BITVEC));
 
636
                size_l = sizebitvec(GETSIGN(datum_l));
 
637
        }
 
638
        if (cache[seed_2].allistrue)
 
639
        {
 
640
                datum_r = (GISTTYPE *) palloc(CALCGTSIZE(SIGNKEY | ALLISTRUE, 0));
 
641
                datum_r->len = CALCGTSIZE(SIGNKEY | ALLISTRUE, 0);
 
642
                datum_r->flag = SIGNKEY | ALLISTRUE;
 
643
                size_r = SIGLENBIT;
 
644
        }
 
645
        else
 
646
        {
 
647
                datum_r = (GISTTYPE *) palloc(CALCGTSIZE(SIGNKEY, 0));
 
648
                datum_r->len = CALCGTSIZE(SIGNKEY, 0);
 
649
                datum_r->flag = SIGNKEY;
 
650
                memcpy((void *) GETSIGN(datum_r), (void *) cache[seed_2].sign, sizeof(BITVEC));
 
651
                size_r = sizebitvec(GETSIGN(datum_r));
 
652
        }
 
653
 
 
654
        maxoff = OffsetNumberNext(maxoff);
 
655
        fillcache(&cache[maxoff], GETENTRY(entryvec, maxoff));
 
656
        /* sort before ... */
 
657
        costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
 
658
        for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
 
659
        {
 
660
                costvector[j - 1].pos = j;
 
661
                if (cache[j].allistrue)
 
662
                {
 
663
                        size_alpha = SIGLENBIT - size_l;
 
664
                        size_beta = SIGLENBIT - size_r;
 
665
                }
 
666
                else
 
667
                {
 
668
                        ptra = cache[seed_1].sign;
 
669
                        ptrb = cache[seed_2].sign;
 
670
                        ptrc = cache[j].sign;
 
671
                        size_beta = size_alpha = 0;
 
672
                        if (cache[seed_1].allistrue)
 
673
                        {
 
674
                                if (!cache[seed_2].allistrue)
 
675
                                {
 
676
                                        LOOPBIT(
 
677
                                                        if (GETBIT(ptrc, i) && !GETBIT(ptrb, i))
 
678
                                                        size_beta++;
 
679
                                        );
 
680
                                }
 
681
                        }
 
682
                        else if (cache[seed_2].allistrue)
 
683
                        {
 
684
                                if (!cache[seed_1].allistrue)
 
685
                                {
 
686
                                        LOOPBIT(
 
687
                                                        if (GETBIT(ptrc, i) && !GETBIT(ptra, i))
 
688
                                                        size_alpha++;
 
689
                                        );
 
690
                                }
 
691
                        }
 
692
                        else
 
693
                        {
 
694
                                LOOPBIT(
 
695
                                                if (GETBIT(ptrc, i) && !GETBIT(ptra, i))
 
696
                                                size_alpha++;
 
697
                                if (GETBIT(ptrc, i) && !GETBIT(ptrb, i))
 
698
                                        size_beta++;
 
699
                                );
 
700
                        }
 
701
 
 
702
                }
 
703
                costvector[j - 1].cost = Abs(size_alpha - size_beta);
 
704
        }
 
705
        qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
 
706
 
 
707
        for (k = 0; k < maxoff; k++)
 
708
        {
 
709
                j = costvector[k].pos;
 
710
                if (j == seed_1)
 
711
                {
 
712
                        *left++ = j;
 
713
                        v->spl_nleft++;
 
714
                        continue;
 
715
                }
 
716
                else if (j == seed_2)
 
717
                {
 
718
                        *right++ = j;
 
719
                        v->spl_nright++;
 
720
                        continue;
 
721
                }
 
722
 
 
723
                if (ISALLTRUE(datum_l) || cache[j].allistrue)
 
724
                        size_alpha = SIGLENBIT;
 
725
                else
 
726
                {
 
727
                        ptra = cache[j].sign;
 
728
                        ptrb = GETSIGN(datum_l);
 
729
                        size_alpha = 0;
 
730
                        LOOPBYTE(
 
731
                                         valtmp = union_l[i] = ptra[i] | ptrb[i];
 
732
                        size_alpha += SUMBIT(valtmp);
 
733
                        );
 
734
                }
 
735
                if (ISALLTRUE(datum_r) || cache[j].allistrue)
 
736
                        size_beta = SIGLENBIT;
 
737
                else
 
738
                {
 
739
                        ptra = cache[j].sign;
 
740
                        ptrb = GETSIGN(datum_r);
 
741
                        size_beta = 0;
 
742
                        LOOPBYTE(
 
743
                                         valtmp = union_r[i] = ptra[i] | ptrb[i];
 
744
                        size_beta += SUMBIT(valtmp);
 
745
                        );
 
746
                }
 
747
 
 
748
                if (size_alpha - size_l < size_beta - size_r + WISH_F(v->spl_nleft, v->spl_nright, 0.1))
 
749
                {
 
750
                        if (!ISALLTRUE(datum_l))
 
751
                        {
 
752
                                if (size_alpha == SIGLENBIT)
 
753
                                {
 
754
                                        if (size_alpha != size_l)
 
755
                                                MemSet((void *) GETSIGN(datum_l), 0xff, sizeof(BITVEC));
 
756
                                }
 
757
                                else
 
758
                                        memcpy((void *) GETSIGN(datum_l), (void *) union_l, sizeof(BITVEC));
 
759
                        }
 
760
                        size_l = size_alpha;
 
761
                        *left++ = j;
 
762
                        v->spl_nleft++;
 
763
                }
 
764
                else
 
765
                {
 
766
                        if (!ISALLTRUE(datum_r))
 
767
                        {
 
768
                                if (size_beta == SIGLENBIT)
 
769
                                {
 
770
                                        if (size_beta != size_r)
 
771
                                                MemSet((void *) GETSIGN(datum_r), 0xff, sizeof(BITVEC));
 
772
                                }
 
773
                                else
 
774
                                        memcpy((void *) GETSIGN(datum_r), (void *) union_r, sizeof(BITVEC));
 
775
                        }
 
776
                        size_r = size_beta;
 
777
                        *right++ = j;
 
778
                        v->spl_nright++;
 
779
                }
 
780
        }
 
781
 
 
782
        *right = *left = FirstOffsetNumber;
 
783
        pfree(costvector);
 
784
        pfree(cache);
 
785
        v->spl_ldatum = PointerGetDatum(datum_l);
 
786
        v->spl_rdatum = PointerGetDatum(datum_r);
 
787
 
 
788
        PG_RETURN_POINTER(v);
 
789
}