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