← Back to branch summary

~vcs-imports/mammoth-replicator/trunk

« back to all changes in this revision

Viewing changes to contrib/intarray/_intbig_gist.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/intarray/_intbig_gist.c
 
1
#include "_int.h"
 
2
 
 
3
#define GETENTRY(vec,pos) ((GISTTYPE *) DatumGetPointer((vec)->vector[(pos)].key))
 
4
/*
 
5
** _intbig methods
 
6
*/
 
7
PG_FUNCTION_INFO_V1(g_intbig_consistent);
 
8
PG_FUNCTION_INFO_V1(g_intbig_compress);
 
9
PG_FUNCTION_INFO_V1(g_intbig_decompress);
 
10
PG_FUNCTION_INFO_V1(g_intbig_penalty);
 
11
PG_FUNCTION_INFO_V1(g_intbig_picksplit);
 
12
PG_FUNCTION_INFO_V1(g_intbig_union);
 
13
PG_FUNCTION_INFO_V1(g_intbig_same);
 
14
 
 
15
Datum           g_intbig_consistent(PG_FUNCTION_ARGS);
 
16
Datum           g_intbig_compress(PG_FUNCTION_ARGS);
 
17
Datum           g_intbig_decompress(PG_FUNCTION_ARGS);
 
18
Datum           g_intbig_penalty(PG_FUNCTION_ARGS);
 
19
Datum           g_intbig_picksplit(PG_FUNCTION_ARGS);
 
20
Datum           g_intbig_union(PG_FUNCTION_ARGS);
 
21
Datum           g_intbig_same(PG_FUNCTION_ARGS);
 
22
 
 
23
#define SUMBIT(val) (           \
 
24
                GETBITBYTE((val),0) + \
 
25
                GETBITBYTE((val),1) + \
 
26
                GETBITBYTE((val),2) + \
 
27
                GETBITBYTE((val),3) + \
 
28
                GETBITBYTE((val),4) + \
 
29
                GETBITBYTE((val),5) + \
 
30
                GETBITBYTE((val),6) + \
 
31
                GETBITBYTE((val),7)   \
 
32
)
 
33
 
 
34
PG_FUNCTION_INFO_V1(_intbig_in);
 
35
Datum           _intbig_in(PG_FUNCTION_ARGS);
 
36
 
 
37
PG_FUNCTION_INFO_V1(_intbig_out);
 
38
Datum           _intbig_out(PG_FUNCTION_ARGS);
 
39
 
 
40
 
 
41
Datum
 
42
_intbig_in(PG_FUNCTION_ARGS)
 
43
{
 
44
        ereport(ERROR,
 
45
                        (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 
46
                         errmsg("_intbig_in() not implemented")));
 
47
        PG_RETURN_DATUM(0);
 
48
}
 
49
 
 
50
Datum
 
51
_intbig_out(PG_FUNCTION_ARGS)
 
52
{
 
53
        ereport(ERROR,
 
54
                        (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 
55
                         errmsg("_intbig_out() not implemented")));
 
56
        PG_RETURN_DATUM(0);
 
57
}
 
58
 
 
59
 
 
60
/*********************************************************************
 
61
** intbig functions
 
62
*********************************************************************/
 
63
static bool
 
64
_intbig_overlap(GISTTYPE * a, ArrayType *b)
 
65
{
 
66
        int                     num = ARRNELEMS(b);
 
67
        int4       *ptr = ARRPTR(b);
 
68
 
 
69
        while (num--)
 
70
        {
 
71
                if (GETBIT(GETSIGN(a), HASHVAL(*ptr)))
 
72
                        return true;
 
73
                ptr++;
 
74
        }
 
75
 
 
76
        return false;
 
77
}
 
78
 
 
79
static bool
 
80
_intbig_contains(GISTTYPE * a, ArrayType *b)
 
81
{
 
82
        int                     num = ARRNELEMS(b);
 
83
        int4       *ptr = ARRPTR(b);
 
84
 
 
85
        while (num--)
 
86
        {
 
87
                if (!GETBIT(GETSIGN(a), HASHVAL(*ptr)))
 
88
                        return false;
 
89
                ptr++;
 
90
        }
 
91
 
 
92
        return true;
 
93
}
 
94
 
 
95
Datum
 
96
g_intbig_same(PG_FUNCTION_ARGS)
 
97
{
 
98
        GISTTYPE   *a = (GISTTYPE *) PG_GETARG_POINTER(0);
 
99
        GISTTYPE   *b = (GISTTYPE *) PG_GETARG_POINTER(1);
 
100
        bool       *result = (bool *) PG_GETARG_POINTER(2);
 
101
 
 
102
        if (ISALLTRUE(a) && ISALLTRUE(b))
 
103
                *result = true;
 
104
        else if (ISALLTRUE(a))
 
105
                *result = false;
 
106
        else if (ISALLTRUE(b))
 
107
                *result = false;
 
108
        else
 
109
        {
 
110
                int4            i;
 
111
                BITVECP         sa = GETSIGN(a),
 
112
                                        sb = GETSIGN(b);
 
113
 
 
114
                *result = true;
 
115
                LOOPBYTE(
 
116
                                 if (sa[i] != sb[i])
 
117
                                 {
 
118
                        *result = false;
 
119
                        break;
 
120
                }
 
121
                );
 
122
        }
 
123
        PG_RETURN_POINTER(result);
 
124
}
 
125
 
 
126
Datum
 
127
g_intbig_compress(PG_FUNCTION_ARGS)
 
128
{
 
129
        GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 
130
 
 
131
        if (entry->leafkey)
 
132
        {
 
133
                GISTENTRY  *retval;
 
134
                ArrayType  *in = (ArrayType *) PG_DETOAST_DATUM(entry->key);
 
135
                int4       *ptr;
 
136
                int                     num;
 
137
                GISTTYPE   *res = (GISTTYPE *) palloc(CALCGTSIZE(0));
 
138
 
 
139
                ARRISVOID(in);
 
140
 
 
141
                ptr = ARRPTR(in);
 
142
                num = ARRNELEMS(in);
 
143
                memset(res, 0, CALCGTSIZE(0));
 
144
                res->len = CALCGTSIZE(0);
 
145
 
 
146
                while (num--)
 
147
                {
 
148
                        HASH(GETSIGN(res), *ptr);
 
149
                        ptr++;
 
150
                }
 
151
 
 
152
                retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
 
153
                gistentryinit(*retval, PointerGetDatum(res),
 
154
                                          entry->rel, entry->page,
 
155
                                          entry->offset, res->len, FALSE);
 
156
 
 
157
                if (in != (ArrayType *) PG_DETOAST_DATUM(entry->key))
 
158
                        pfree(in);
 
159
 
 
160
                PG_RETURN_POINTER(retval);
 
161
        }
 
162
        else if (!ISALLTRUE(DatumGetPointer(entry->key)))
 
163
        {
 
164
                GISTENTRY  *retval;
 
165
                int                     i;
 
166
                BITVECP         sign = GETSIGN(DatumGetPointer(entry->key));
 
167
                GISTTYPE   *res;
 
168
 
 
169
                LOOPBYTE(
 
170
                                 if ((sign[i] & 0xff) != 0xff)
 
171
                                 PG_RETURN_POINTER(entry);
 
172
                );
 
173
 
 
174
                res = (GISTTYPE *) palloc(CALCGTSIZE(ALLISTRUE));
 
175
                res->len = CALCGTSIZE(ALLISTRUE);
 
176
                res->flag = ALLISTRUE;
 
177
 
 
178
                retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
 
179
                gistentryinit(*retval, PointerGetDatum(res),
 
180
                                          entry->rel, entry->page,
 
181
                                          entry->offset, res->len, FALSE);
 
182
 
 
183
                PG_RETURN_POINTER(retval);
 
184
        }
 
185
 
 
186
        PG_RETURN_POINTER(entry);
 
187
}
 
188
 
 
189
 
 
190
static int4
 
191
sizebitvec(BITVECP sign)
 
192
{
 
193
        int4            size = 0,
 
194
                                i;
 
195
 
 
196
        LOOPBYTE(
 
197
                         size += SUMBIT(sign);
 
198
        sign = (BITVECP) (((char *) sign) + 1);
 
199
        );
 
200
        return size;
 
201
}
 
202
 
 
203
static int
 
204
hemdistsign(BITVECP a, BITVECP b)
 
205
{
 
206
        int                     i,
 
207
                                dist = 0;
 
208
 
 
209
        LOOPBIT(
 
210
                        if (GETBIT(a, i) != GETBIT(b, i))
 
211
                        dist++;
 
212
        );
 
213
        return dist;
 
214
}
 
215
 
 
216
static int
 
217
hemdist(GISTTYPE * a, GISTTYPE * b)
 
218
{
 
219
        if (ISALLTRUE(a))
 
220
        {
 
221
                if (ISALLTRUE(b))
 
222
                        return 0;
 
223
                else
 
224
                        return SIGLENBIT - sizebitvec(GETSIGN(b));
 
225
        }
 
226
        else if (ISALLTRUE(b))
 
227
                return SIGLENBIT - sizebitvec(GETSIGN(a));
 
228
 
 
229
        return hemdistsign(GETSIGN(a), GETSIGN(b));
 
230
}
 
231
 
 
232
Datum
 
233
g_intbig_decompress(PG_FUNCTION_ARGS)
 
234
{
 
235
        PG_RETURN_DATUM(PG_GETARG_DATUM(0));
 
236
}
 
237
 
 
238
static int4
 
239
unionkey(BITVECP sbase, GISTTYPE * add)
 
240
{
 
241
        int4            i;
 
242
        BITVECP         sadd = GETSIGN(add);
 
243
 
 
244
        if (ISALLTRUE(add))
 
245
                return 1;
 
246
        LOOPBYTE(
 
247
                         sbase[i] |= sadd[i];
 
248
        );
 
249
        return 0;
 
250
}
 
251
 
 
252
Datum
 
253
g_intbig_union(PG_FUNCTION_ARGS)
 
254
{
 
255
        GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 
256
        int                *size = (int *) PG_GETARG_POINTER(1);
 
257
        BITVEC          base;
 
258
        int4            i,
 
259
                                len;
 
260
        int4            flag = 0;
 
261
        GISTTYPE   *result;
 
262
 
 
263
        MemSet((void *) base, 0, sizeof(BITVEC));
 
264
        for (i = 0; i < entryvec->n; i++)
 
265
        {
 
266
                if (unionkey(base, GETENTRY(entryvec, i)))
 
267
                {
 
268
                        flag = ALLISTRUE;
 
269
                        break;
 
270
                }
 
271
        }
 
272
 
 
273
        len = CALCGTSIZE(flag);
 
274
        result = (GISTTYPE *) palloc(len);
 
275
        *size = result->len = len;
 
276
        result->flag = flag;
 
277
        if (!ISALLTRUE(result))
 
278
                memcpy((void *) GETSIGN(result), (void *) base, sizeof(BITVEC));
 
279
 
 
280
        PG_RETURN_POINTER(result);
 
281
}
 
282
 
 
283
Datum
 
284
g_intbig_penalty(PG_FUNCTION_ARGS)
 
285
{
 
286
        GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* always ISSIGNKEY */
 
287
        GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
 
288
        float      *penalty = (float *) PG_GETARG_POINTER(2);
 
289
        GISTTYPE   *origval = (GISTTYPE *) DatumGetPointer(origentry->key);
 
290
        GISTTYPE   *newval = (GISTTYPE *) DatumGetPointer(newentry->key);
 
291
 
 
292
        *penalty = hemdist(origval, newval);
 
293
        PG_RETURN_POINTER(penalty);
 
294
}
 
295
 
 
296
 
 
297
typedef struct
 
298
{
 
299
        OffsetNumber pos;
 
300
        int4            cost;
 
301
} SPLITCOST;
 
302
 
 
303
static int
 
304
comparecost(const void *a, const void *b)
 
305
{
 
306
        return ((SPLITCOST *) a)->cost - ((SPLITCOST *) b)->cost;
 
307
}
 
308
 
 
309
 
 
310
Datum
 
311
g_intbig_picksplit(PG_FUNCTION_ARGS)
 
312
{
 
313
        GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 
314
        GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
 
315
        OffsetNumber k,
 
316
                                j;
 
317
        GISTTYPE   *datum_l,
 
318
                           *datum_r;
 
319
        BITVECP         union_l,
 
320
                                union_r;
 
321
        int4            size_alpha,
 
322
                                size_beta;
 
323
        int4            size_waste,
 
324
                                waste = -1;
 
325
        int4            nbytes;
 
326
        OffsetNumber seed_1 = 0,
 
327
                                seed_2 = 0;
 
328
        OffsetNumber *left,
 
329
                           *right;
 
330
        OffsetNumber maxoff;
 
331
        BITVECP         ptr;
 
332
        int                     i;
 
333
        SPLITCOST  *costvector;
 
334
        GISTTYPE   *_k,
 
335
                           *_j;
 
336
 
 
337
        maxoff = entryvec->n - 2;
 
338
        nbytes = (maxoff + 2) * sizeof(OffsetNumber);
 
339
        v->spl_left = (OffsetNumber *) palloc(nbytes);
 
340
        v->spl_right = (OffsetNumber *) palloc(nbytes);
 
341
 
 
342
        for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
 
343
        {
 
344
                _k = GETENTRY(entryvec, k);
 
345
                for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
 
346
                {
 
347
                        size_waste = hemdist(_k, GETENTRY(entryvec, j));
 
348
                        if (size_waste > waste)
 
349
                        {
 
350
                                waste = size_waste;
 
351
                                seed_1 = k;
 
352
                                seed_2 = j;
 
353
                        }
 
354
                }
 
355
        }
 
356
 
 
357
        left = v->spl_left;
 
358
        v->spl_nleft = 0;
 
359
        right = v->spl_right;
 
360
        v->spl_nright = 0;
 
361
 
 
362
        if (seed_1 == 0 || seed_2 == 0)
 
363
        {
 
364
                seed_1 = 1;
 
365
                seed_2 = 2;
 
366
        }
 
367
 
 
368
        /* form initial .. */
 
369
        if (ISALLTRUE(GETENTRY(entryvec, seed_1)))
 
370
        {
 
371
                datum_l = (GISTTYPE *) palloc(GTHDRSIZE);
 
372
                datum_l->len = GTHDRSIZE;
 
373
                datum_l->flag = ALLISTRUE;
 
374
        }
 
375
        else
 
376
        {
 
377
                datum_l = (GISTTYPE *) palloc(GTHDRSIZE + SIGLEN);
 
378
                datum_l->len = GTHDRSIZE + SIGLEN;
 
379
                datum_l->flag = 0;
 
380
                memcpy((void *) GETSIGN(datum_l), (void *) GETSIGN(GETENTRY(entryvec, seed_1)), sizeof(BITVEC));
 
381
        }
 
382
        if (ISALLTRUE(GETENTRY(entryvec, seed_2)))
 
383
        {
 
384
                datum_r = (GISTTYPE *) palloc(GTHDRSIZE);
 
385
                datum_r->len = GTHDRSIZE;
 
386
                datum_r->flag = ALLISTRUE;
 
387
        }
 
388
        else
 
389
        {
 
390
                datum_r = (GISTTYPE *) palloc(GTHDRSIZE + SIGLEN);
 
391
                datum_r->len = GTHDRSIZE + SIGLEN;
 
392
                datum_r->flag = 0;
 
393
                memcpy((void *) GETSIGN(datum_r), (void *) GETSIGN(GETENTRY(entryvec, seed_2)), sizeof(BITVEC));
 
394
        }
 
395
 
 
396
        maxoff = OffsetNumberNext(maxoff);
 
397
        /* sort before ... */
 
398
        costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
 
399
        for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
 
400
        {
 
401
                costvector[j - 1].pos = j;
 
402
                _j = GETENTRY(entryvec, j);
 
403
                size_alpha = hemdist(datum_l, _j);
 
404
                size_beta = hemdist(datum_r, _j);
 
405
                costvector[j - 1].cost = Abs(size_alpha - size_beta);
 
406
        }
 
407
        qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
 
408
 
 
409
        union_l = GETSIGN(datum_l);
 
410
        union_r = GETSIGN(datum_r);
 
411
 
 
412
        for (k = 0; k < maxoff; k++)
 
413
        {
 
414
                j = costvector[k].pos;
 
415
                if (j == seed_1)
 
416
                {
 
417
                        *left++ = j;
 
418
                        v->spl_nleft++;
 
419
                        continue;
 
420
                }
 
421
                else if (j == seed_2)
 
422
                {
 
423
                        *right++ = j;
 
424
                        v->spl_nright++;
 
425
                        continue;
 
426
                }
 
427
                _j = GETENTRY(entryvec, j);
 
428
                size_alpha = hemdist(datum_l, _j);
 
429
                size_beta = hemdist(datum_r, _j);
 
430
 
 
431
                if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.00001))
 
432
                {
 
433
                        if (ISALLTRUE(datum_l) || ISALLTRUE(_j))
 
434
                        {
 
435
                                if (!ISALLTRUE(datum_l))
 
436
                                        MemSet((void *) union_l, 0xff, sizeof(BITVEC));
 
437
                        }
 
438
                        else
 
439
                        {
 
440
                                ptr = GETSIGN(_j);
 
441
                                LOOPBYTE(
 
442
                                                 union_l[i] |= ptr[i];
 
443
                                );
 
444
                        }
 
445
                        *left++ = j;
 
446
                        v->spl_nleft++;
 
447
                }
 
448
                else
 
449
                {
 
450
                        if (ISALLTRUE(datum_r) || ISALLTRUE(_j))
 
451
                        {
 
452
                                if (!ISALLTRUE(datum_r))
 
453
                                        MemSet((void *) union_r, 0xff, sizeof(BITVEC));
 
454
                        }
 
455
                        else
 
456
                        {
 
457
                                ptr = GETSIGN(_j);
 
458
                                LOOPBYTE(
 
459
                                                 union_r[i] |= ptr[i];
 
460
                                );
 
461
                        }
 
462
                        *right++ = j;
 
463
                        v->spl_nright++;
 
464
                }
 
465
        }
 
466
 
 
467
        *right = *left = FirstOffsetNumber;
 
468
        pfree(costvector);
 
469
 
 
470
        v->spl_ldatum = PointerGetDatum(datum_l);
 
471
        v->spl_rdatum = PointerGetDatum(datum_r);
 
472
 
 
473
        PG_RETURN_POINTER(v);
 
474
}
 
475
 
 
476
Datum
 
477
g_intbig_consistent(PG_FUNCTION_ARGS)
 
478
{
 
479
        GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 
480
        ArrayType  *query = (ArrayType *) PG_GETARG_POINTER(1);
 
481
        StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
 
482
        bool            retval;
 
483
 
 
484
        if (ISALLTRUE(DatumGetPointer(entry->key)))
 
485
                PG_RETURN_BOOL(true);
 
486
 
 
487
        if (strategy == BooleanSearchStrategy)
 
488
        {
 
489
                PG_RETURN_BOOL(signconsistent((QUERYTYPE *) query,
 
490
                                                                        GETSIGN(DatumGetPointer(entry->key)),
 
491
                                                                          false));
 
492
        }
 
493
 
 
494
        /* XXX what about toasted input? */
 
495
        if (ARRISVOID(query))
 
496
                return FALSE;
 
497
 
 
498
        switch (strategy)
 
499
        {
 
500
                case RTOverlapStrategyNumber:
 
501
                        retval = _intbig_overlap((GISTTYPE *) DatumGetPointer(entry->key), query);
 
502
                        break;
 
503
                case RTSameStrategyNumber:
 
504
                        if (GIST_LEAF(entry))
 
505
                        {
 
506
                                int                     i,
 
507
                                                        num = ARRNELEMS(query);
 
508
                                int4       *ptr = ARRPTR(query);
 
509
                                BITVEC          qp;
 
510
                                BITVECP         dq,
 
511
                                                        de;
 
512
 
 
513
                                memset(qp, 0, sizeof(BITVEC));
 
514
 
 
515
                                while (num--)
 
516
                                {
 
517
                                        HASH(qp, *ptr);
 
518
                                        ptr++;
 
519
                                }
 
520
 
 
521
                                de = GETSIGN((GISTTYPE *) DatumGetPointer(entry->key));
 
522
                                dq = qp;
 
523
                                retval = true;
 
524
                                LOOPBYTE(
 
525
                                                 if (de[i] != dq[i])
 
526
                                                 {
 
527
                                        retval = false;
 
528
                                        break;
 
529
                                }
 
530
                                );
 
531
 
 
532
                        }
 
533
                        else
 
534
                                retval = _intbig_contains((GISTTYPE *) DatumGetPointer(entry->key), query);
 
535
                        break;
 
536
                case RTContainsStrategyNumber:
 
537
                        retval = _intbig_contains((GISTTYPE *) DatumGetPointer(entry->key), query);
 
538
                        break;
 
539
                case RTContainedByStrategyNumber:
 
540
                        if (GIST_LEAF(entry))
 
541
                        {
 
542
                                int                     i,
 
543
                                                        num = ARRNELEMS(query);
 
544
                                int4       *ptr = ARRPTR(query);
 
545
                                BITVEC          qp;
 
546
                                BITVECP         dq,
 
547
                                                        de;
 
548
 
 
549
                                memset(qp, 0, sizeof(BITVEC));
 
550
 
 
551
                                while (num--)
 
552
                                {
 
553
                                        HASH(qp, *ptr);
 
554
                                        ptr++;
 
555
                                }
 
556
 
 
557
                                de = GETSIGN((GISTTYPE *) DatumGetPointer(entry->key));
 
558
                                dq = qp;
 
559
                                retval = true;
 
560
                                LOOPBYTE(
 
561
                                                 if (de[i] & ~dq[i])
 
562
                                                 {
 
563
                                        retval = false;
 
564
                                        break;
 
565
                                }
 
566
                                );
 
567
 
 
568
                        }
 
569
                        else
 
570
                                retval = _intbig_overlap((GISTTYPE *) DatumGetPointer(entry->key), query);
 
571
                        break;
 
572
                default:
 
573
                        retval = FALSE;
 
574
        }
 
575
        PG_RETURN_BOOL(retval);
 
576
}