doc: Fix section of functions age(xid) and mxid_age(xid)
[pgsql.git] / contrib / ltree / ltree_gist.c
blob932f69bff2d180a58239db80023c68ebeec6429f
1 /*
2 * GiST support for ltree
3 * Teodor Sigaev <teodor@stack.net>
4 * contrib/ltree/ltree_gist.c
5 */
6 #include "postgres.h"
8 #include "access/gist.h"
9 #include "access/reloptions.h"
10 #include "access/stratnum.h"
11 #include "crc32.h"
12 #include "ltree.h"
13 #include "utils/array.h"
15 #define NEXTVAL(x) ( (lquery*)( (char*)(x) + INTALIGN( VARSIZE(x) ) ) )
16 #define ISEQ(a,b) ( (a)->numlevel == (b)->numlevel && ltree_compare(a,b)==0 )
18 PG_FUNCTION_INFO_V1(ltree_gist_in);
19 PG_FUNCTION_INFO_V1(ltree_gist_out);
21 Datum
22 ltree_gist_in(PG_FUNCTION_ARGS)
24 ereport(ERROR,
25 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
26 errmsg("cannot accept a value of type %s", "ltree_gist")));
28 PG_RETURN_VOID(); /* keep compiler quiet */
31 Datum
32 ltree_gist_out(PG_FUNCTION_ARGS)
34 ereport(ERROR,
35 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
36 errmsg("cannot display a value of type %s", "ltree_gist")));
38 PG_RETURN_VOID(); /* keep compiler quiet */
41 ltree_gist *
42 ltree_gist_alloc(bool isalltrue, BITVECP sign, int siglen,
43 ltree *left, ltree *right)
45 int32 size = LTG_HDRSIZE + (isalltrue ? 0 : siglen) +
46 (left ? VARSIZE(left) + (right ? VARSIZE(right) : 0) : 0);
47 ltree_gist *result = palloc(size);
49 SET_VARSIZE(result, size);
51 if (siglen)
53 result->flag = 0;
55 if (isalltrue)
56 result->flag |= LTG_ALLTRUE;
57 else if (sign)
58 memcpy(LTG_SIGN(result), sign, siglen);
59 else
60 memset(LTG_SIGN(result), 0, siglen);
62 if (left)
64 memcpy(LTG_LNODE(result, siglen), left, VARSIZE(left));
66 if (!right || left == right || ISEQ(left, right))
67 result->flag |= LTG_NORIGHT;
68 else
69 memcpy(LTG_RNODE(result, siglen), right, VARSIZE(right));
72 else
74 Assert(left);
75 result->flag = LTG_ONENODE;
76 memcpy(LTG_NODE(result), left, VARSIZE(left));
79 return result;
82 PG_FUNCTION_INFO_V1(ltree_compress);
83 PG_FUNCTION_INFO_V1(ltree_decompress);
84 PG_FUNCTION_INFO_V1(ltree_same);
85 PG_FUNCTION_INFO_V1(ltree_union);
86 PG_FUNCTION_INFO_V1(ltree_penalty);
87 PG_FUNCTION_INFO_V1(ltree_picksplit);
88 PG_FUNCTION_INFO_V1(ltree_consistent);
89 PG_FUNCTION_INFO_V1(ltree_gist_options);
91 #define GETENTRY(vec,pos) ((ltree_gist *) DatumGetPointer((vec)->vector[(pos)].key))
93 Datum
94 ltree_compress(PG_FUNCTION_ARGS)
96 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
97 GISTENTRY *retval = entry;
99 if (entry->leafkey)
100 { /* ltree */
101 ltree *val = DatumGetLtreeP(entry->key);
102 ltree_gist *key = ltree_gist_alloc(false, NULL, 0, val, 0);
104 retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
105 gistentryinit(*retval, PointerGetDatum(key),
106 entry->rel, entry->page,
107 entry->offset, false);
109 PG_RETURN_POINTER(retval);
112 Datum
113 ltree_decompress(PG_FUNCTION_ARGS)
115 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
116 ltree_gist *key = (ltree_gist *) PG_DETOAST_DATUM(entry->key);
118 if (PointerGetDatum(key) != entry->key)
120 GISTENTRY *retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
122 gistentryinit(*retval, PointerGetDatum(key),
123 entry->rel, entry->page,
124 entry->offset, false);
125 PG_RETURN_POINTER(retval);
127 PG_RETURN_POINTER(entry);
130 Datum
131 ltree_same(PG_FUNCTION_ARGS)
133 ltree_gist *a = (ltree_gist *) PG_GETARG_POINTER(0);
134 ltree_gist *b = (ltree_gist *) PG_GETARG_POINTER(1);
135 bool *result = (bool *) PG_GETARG_POINTER(2);
136 int siglen = LTREE_GET_SIGLEN();
138 *result = false;
139 if (LTG_ISONENODE(a) != LTG_ISONENODE(b))
140 PG_RETURN_POINTER(result);
142 if (LTG_ISONENODE(a))
143 *result = ISEQ(LTG_NODE(a), LTG_NODE(b));
144 else
146 int32 i;
147 BITVECP sa = LTG_SIGN(a),
148 sb = LTG_SIGN(b);
150 if (LTG_ISALLTRUE(a) != LTG_ISALLTRUE(b))
151 PG_RETURN_POINTER(result);
153 if (!ISEQ(LTG_LNODE(a, siglen), LTG_LNODE(b, siglen)))
154 PG_RETURN_POINTER(result);
155 if (!ISEQ(LTG_RNODE(a, siglen), LTG_RNODE(b, siglen)))
156 PG_RETURN_POINTER(result);
158 *result = true;
159 if (!LTG_ISALLTRUE(a))
161 LOOPBYTE(siglen)
163 if (sa[i] != sb[i])
165 *result = false;
166 break;
172 PG_RETURN_POINTER(result);
175 static void
176 hashing(BITVECP sign, ltree *t, int siglen)
178 int tlen = t->numlevel;
179 ltree_level *cur = LTREE_FIRST(t);
180 int hash;
182 while (tlen > 0)
184 hash = ltree_crc32_sz(cur->name, cur->len);
185 HASH(sign, hash, siglen);
186 cur = LEVEL_NEXT(cur);
187 tlen--;
191 Datum
192 ltree_union(PG_FUNCTION_ARGS)
194 GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
195 int *size = (int *) PG_GETARG_POINTER(1);
196 int siglen = LTREE_GET_SIGLEN();
197 BITVECP base = palloc0(siglen);
198 int32 i,
200 ltree_gist *result,
201 *cur;
202 ltree *left = NULL,
203 *right = NULL,
204 *curtree;
205 bool isalltrue = false;
207 for (j = 0; j < entryvec->n; j++)
209 cur = GETENTRY(entryvec, j);
210 if (LTG_ISONENODE(cur))
212 curtree = LTG_NODE(cur);
213 hashing(base, curtree, siglen);
214 if (!left || ltree_compare(left, curtree) > 0)
215 left = curtree;
216 if (!right || ltree_compare(right, curtree) < 0)
217 right = curtree;
219 else
221 if (isalltrue || LTG_ISALLTRUE(cur))
222 isalltrue = true;
223 else
225 BITVECP sc = LTG_SIGN(cur);
227 LOOPBYTE(siglen)
228 ((unsigned char *) base)[i] |= sc[i];
231 curtree = LTG_LNODE(cur, siglen);
232 if (!left || ltree_compare(left, curtree) > 0)
233 left = curtree;
234 curtree = LTG_RNODE(cur, siglen);
235 if (!right || ltree_compare(right, curtree) < 0)
236 right = curtree;
240 if (isalltrue == false)
242 isalltrue = true;
243 LOOPBYTE(siglen)
245 if (((unsigned char *) base)[i] != 0xff)
247 isalltrue = false;
248 break;
253 result = ltree_gist_alloc(isalltrue, base, siglen, left, right);
255 *size = VARSIZE(result);
257 PG_RETURN_POINTER(result);
260 Datum
261 ltree_penalty(PG_FUNCTION_ARGS)
263 ltree_gist *origval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(0))->key);
264 ltree_gist *newval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(1))->key);
265 float *penalty = (float *) PG_GETARG_POINTER(2);
266 int siglen = LTREE_GET_SIGLEN();
267 int32 cmpr,
268 cmpl;
270 cmpl = ltree_compare(LTG_GETLNODE(origval, siglen), LTG_GETLNODE(newval, siglen));
271 cmpr = ltree_compare(LTG_GETRNODE(newval, siglen), LTG_GETRNODE(origval, siglen));
273 *penalty = Max(cmpl, 0) + Max(cmpr, 0);
275 PG_RETURN_POINTER(penalty);
278 /* used for sorting */
279 typedef struct rix
281 int index;
282 ltree *r;
283 } RIX;
285 static int
286 treekey_cmp(const void *a, const void *b)
288 return ltree_compare(((const RIX *) a)->r,
289 ((const RIX *) b)->r);
293 Datum
294 ltree_picksplit(PG_FUNCTION_ARGS)
296 GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
297 GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
298 int siglen = LTREE_GET_SIGLEN();
299 OffsetNumber j;
300 int32 i;
301 RIX *array;
302 OffsetNumber maxoff;
303 int nbytes;
304 ltree *lu_l,
305 *lu_r,
306 *ru_l,
307 *ru_r;
308 ltree_gist *lu,
309 *ru;
310 BITVECP ls = palloc0(siglen),
311 rs = palloc0(siglen);
312 bool lisat = false,
313 risat = false;
315 maxoff = entryvec->n - 1;
316 nbytes = (maxoff + 2) * sizeof(OffsetNumber);
317 v->spl_left = (OffsetNumber *) palloc(nbytes);
318 v->spl_right = (OffsetNumber *) palloc(nbytes);
319 v->spl_nleft = 0;
320 v->spl_nright = 0;
321 array = (RIX *) palloc(sizeof(RIX) * (maxoff + 1));
323 /* copy the data into RIXes, and sort the RIXes */
324 for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
326 array[j].index = j;
327 lu = GETENTRY(entryvec, j); /* use as tmp val */
328 array[j].r = LTG_GETLNODE(lu, siglen);
331 qsort(&array[FirstOffsetNumber], maxoff - FirstOffsetNumber + 1,
332 sizeof(RIX), treekey_cmp);
334 lu_l = lu_r = ru_l = ru_r = NULL;
335 for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
337 lu = GETENTRY(entryvec, array[j].index); /* use as tmp val */
338 if (j <= (maxoff - FirstOffsetNumber + 1) / 2)
340 v->spl_left[v->spl_nleft] = array[j].index;
341 v->spl_nleft++;
342 if (lu_r == NULL || ltree_compare(LTG_GETRNODE(lu, siglen), lu_r) > 0)
343 lu_r = LTG_GETRNODE(lu, siglen);
344 if (LTG_ISONENODE(lu))
345 hashing(ls, LTG_NODE(lu), siglen);
346 else
348 if (lisat || LTG_ISALLTRUE(lu))
349 lisat = true;
350 else
352 BITVECP sc = LTG_SIGN(lu);
354 LOOPBYTE(siglen)
355 ((unsigned char *) ls)[i] |= sc[i];
359 else
361 v->spl_right[v->spl_nright] = array[j].index;
362 v->spl_nright++;
363 if (ru_r == NULL || ltree_compare(LTG_GETRNODE(lu, siglen), ru_r) > 0)
364 ru_r = LTG_GETRNODE(lu, siglen);
365 if (LTG_ISONENODE(lu))
366 hashing(rs, LTG_NODE(lu), siglen);
367 else
369 if (risat || LTG_ISALLTRUE(lu))
370 risat = true;
371 else
373 BITVECP sc = LTG_SIGN(lu);
375 LOOPBYTE(siglen)
376 ((unsigned char *) rs)[i] |= sc[i];
382 if (lisat == false)
384 lisat = true;
385 LOOPBYTE(siglen)
387 if (((unsigned char *) ls)[i] != 0xff)
389 lisat = false;
390 break;
395 if (risat == false)
397 risat = true;
398 LOOPBYTE(siglen)
400 if (((unsigned char *) rs)[i] != 0xff)
402 risat = false;
403 break;
408 lu_l = LTG_GETLNODE(GETENTRY(entryvec, array[FirstOffsetNumber].index), siglen);
409 lu = ltree_gist_alloc(lisat, ls, siglen, lu_l, lu_r);
411 ru_l = LTG_GETLNODE(GETENTRY(entryvec, array[1 + ((maxoff - FirstOffsetNumber + 1) / 2)].index), siglen);
412 ru = ltree_gist_alloc(risat, rs, siglen, ru_l, ru_r);
414 pfree(ls);
415 pfree(rs);
417 v->spl_ldatum = PointerGetDatum(lu);
418 v->spl_rdatum = PointerGetDatum(ru);
420 PG_RETURN_POINTER(v);
423 static bool
424 gist_isparent(ltree_gist *key, ltree *query, int siglen)
426 int32 numlevel = query->numlevel;
427 int i;
429 for (i = query->numlevel; i >= 0; i--)
431 query->numlevel = i;
432 if (ltree_compare(query, LTG_GETLNODE(key, siglen)) >= 0 &&
433 ltree_compare(query, LTG_GETRNODE(key, siglen)) <= 0)
435 query->numlevel = numlevel;
436 return true;
440 query->numlevel = numlevel;
441 return false;
444 static ltree *
445 copy_ltree(ltree *src)
447 ltree *dst = (ltree *) palloc0(VARSIZE(src));
449 memcpy(dst, src, VARSIZE(src));
450 return dst;
453 static bool
454 gist_ischild(ltree_gist *key, ltree *query, int siglen)
456 ltree *left = copy_ltree(LTG_GETLNODE(key, siglen));
457 ltree *right = copy_ltree(LTG_GETRNODE(key, siglen));
458 bool res = true;
460 if (left->numlevel > query->numlevel)
461 left->numlevel = query->numlevel;
463 if (ltree_compare(query, left) < 0)
464 res = false;
466 if (right->numlevel > query->numlevel)
467 right->numlevel = query->numlevel;
469 if (res && ltree_compare(query, right) > 0)
470 res = false;
472 pfree(left);
473 pfree(right);
475 return res;
478 static bool
479 gist_qe(ltree_gist *key, lquery *query, int siglen)
481 lquery_level *curq = LQUERY_FIRST(query);
482 BITVECP sign = LTG_SIGN(key);
483 int qlen = query->numlevel;
485 if (LTG_ISALLTRUE(key))
486 return true;
488 while (qlen > 0)
490 if (curq->numvar && LQL_CANLOOKSIGN(curq))
492 bool isexist = false;
493 int vlen = curq->numvar;
494 lquery_variant *curv = LQL_FIRST(curq);
496 while (vlen > 0)
498 if (GETBIT(sign, HASHVAL(curv->val, siglen)))
500 isexist = true;
501 break;
503 curv = LVAR_NEXT(curv);
504 vlen--;
506 if (!isexist)
507 return false;
510 curq = LQL_NEXT(curq);
511 qlen--;
514 return true;
517 static int
518 gist_tqcmp(ltree *t, lquery *q)
520 ltree_level *al = LTREE_FIRST(t);
521 lquery_level *ql = LQUERY_FIRST(q);
522 lquery_variant *bl;
523 int an = t->numlevel;
524 int bn = q->firstgood;
525 int res = 0;
527 while (an > 0 && bn > 0)
529 bl = LQL_FIRST(ql);
530 if ((res = memcmp(al->name, bl->name, Min(al->len, bl->len))) == 0)
532 if (al->len != bl->len)
533 return al->len - bl->len;
535 else
536 return res;
537 an--;
538 bn--;
539 al = LEVEL_NEXT(al);
540 ql = LQL_NEXT(ql);
543 return Min(t->numlevel, q->firstgood) - q->firstgood;
546 static bool
547 gist_between(ltree_gist *key, lquery *query, int siglen)
549 if (query->firstgood == 0)
550 return true;
552 if (gist_tqcmp(LTG_GETLNODE(key, siglen), query) > 0)
553 return false;
555 if (gist_tqcmp(LTG_GETRNODE(key, siglen), query) < 0)
556 return false;
558 return true;
561 typedef struct LtreeSignature
563 BITVECP sign;
564 int siglen;
565 } LtreeSignature;
567 static bool
568 checkcondition_bit(void *cxt, ITEM *val)
570 LtreeSignature *sig = cxt;
572 return (FLG_CANLOOKSIGN(val->flag)) ? GETBIT(sig->sign, HASHVAL(val->val, sig->siglen)) : true;
575 static bool
576 gist_qtxt(ltree_gist *key, ltxtquery *query, int siglen)
578 LtreeSignature sig;
580 if (LTG_ISALLTRUE(key))
581 return true;
583 sig.sign = LTG_SIGN(key);
584 sig.siglen = siglen;
586 return ltree_execute(GETQUERY(query),
587 &sig, false,
588 checkcondition_bit);
591 static bool
592 arrq_cons(ltree_gist *key, ArrayType *_query, int siglen)
594 lquery *query = (lquery *) ARR_DATA_PTR(_query);
595 int num = ArrayGetNItems(ARR_NDIM(_query), ARR_DIMS(_query));
597 if (ARR_NDIM(_query) > 1)
598 ereport(ERROR,
599 (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
600 errmsg("array must be one-dimensional")));
601 if (array_contains_nulls(_query))
602 ereport(ERROR,
603 (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
604 errmsg("array must not contain nulls")));
606 while (num > 0)
608 if (gist_qe(key, query, siglen) && gist_between(key, query, siglen))
609 return true;
610 num--;
611 query = NEXTVAL(query);
613 return false;
616 Datum
617 ltree_consistent(PG_FUNCTION_ARGS)
619 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
620 StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
622 /* Oid subtype = PG_GETARG_OID(3); */
623 bool *recheck = (bool *) PG_GETARG_POINTER(4);
624 int siglen = LTREE_GET_SIGLEN();
625 ltree_gist *key = (ltree_gist *) DatumGetPointer(entry->key);
626 void *query = NULL;
627 bool res = false;
629 /* All cases served by this function are exact */
630 *recheck = false;
632 switch (strategy)
634 case BTLessStrategyNumber:
635 query = PG_GETARG_LTREE_P(1);
636 res = (GIST_LEAF(entry)) ?
637 (ltree_compare((ltree *) query, LTG_NODE(key)) > 0)
639 (ltree_compare((ltree *) query, LTG_GETLNODE(key, siglen)) >= 0);
640 break;
641 case BTLessEqualStrategyNumber:
642 query = PG_GETARG_LTREE_P(1);
643 res = (ltree_compare((ltree *) query, LTG_GETLNODE(key, siglen)) >= 0);
644 break;
645 case BTEqualStrategyNumber:
646 query = PG_GETARG_LTREE_P(1);
647 if (GIST_LEAF(entry))
648 res = (ltree_compare((ltree *) query, LTG_NODE(key)) == 0);
649 else
650 res = (ltree_compare((ltree *) query, LTG_GETLNODE(key, siglen)) >= 0
652 ltree_compare((ltree *) query, LTG_GETRNODE(key, siglen)) <= 0);
653 break;
654 case BTGreaterEqualStrategyNumber:
655 query = PG_GETARG_LTREE_P(1);
656 res = (ltree_compare((ltree *) query, LTG_GETRNODE(key, siglen)) <= 0);
657 break;
658 case BTGreaterStrategyNumber:
659 query = PG_GETARG_LTREE_P(1);
660 res = (GIST_LEAF(entry)) ?
661 (ltree_compare((ltree *) query, LTG_GETRNODE(key, siglen)) < 0)
663 (ltree_compare((ltree *) query, LTG_GETRNODE(key, siglen)) <= 0);
664 break;
665 case 10:
666 query = PG_GETARG_LTREE_P_COPY(1);
667 res = (GIST_LEAF(entry)) ?
668 inner_isparent((ltree *) query, LTG_NODE(key))
670 gist_isparent(key, (ltree *) query, siglen);
671 break;
672 case 11:
673 query = PG_GETARG_LTREE_P(1);
674 res = (GIST_LEAF(entry)) ?
675 inner_isparent(LTG_NODE(key), (ltree *) query)
677 gist_ischild(key, (ltree *) query, siglen);
678 break;
679 case 12:
680 case 13:
681 query = PG_GETARG_LQUERY_P(1);
682 if (GIST_LEAF(entry))
683 res = DatumGetBool(DirectFunctionCall2(ltq_regex,
684 PointerGetDatum(LTG_NODE(key)),
685 PointerGetDatum((lquery *) query)
687 else
688 res = (gist_qe(key, (lquery *) query, siglen) &&
689 gist_between(key, (lquery *) query, siglen));
690 break;
691 case 14:
692 case 15:
693 query = PG_GETARG_LTXTQUERY_P(1);
694 if (GIST_LEAF(entry))
695 res = DatumGetBool(DirectFunctionCall2(ltxtq_exec,
696 PointerGetDatum(LTG_NODE(key)),
697 PointerGetDatum((ltxtquery *) query)
699 else
700 res = gist_qtxt(key, (ltxtquery *) query, siglen);
701 break;
702 case 16:
703 case 17:
704 query = PG_GETARG_ARRAYTYPE_P(1);
705 if (GIST_LEAF(entry))
706 res = DatumGetBool(DirectFunctionCall2(lt_q_regex,
707 PointerGetDatum(LTG_NODE(key)),
708 PointerGetDatum((ArrayType *) query)
710 else
711 res = arrq_cons(key, (ArrayType *) query, siglen);
712 break;
713 default:
714 /* internal error */
715 elog(ERROR, "unrecognized StrategyNumber: %d", strategy);
718 PG_FREE_IF_COPY(query, 1);
719 PG_RETURN_BOOL(res);
722 static void
723 ltree_gist_relopts_validator(void *parsed_options, relopt_value *vals,
724 int nvals)
726 LtreeGistOptions *options = (LtreeGistOptions *) parsed_options;
728 if (options->siglen != INTALIGN(options->siglen))
729 ereport(ERROR,
730 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
731 errmsg("siglen value must be a multiple of %d", ALIGNOF_INT)));
734 Datum
735 ltree_gist_options(PG_FUNCTION_ARGS)
737 local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
739 init_local_reloptions(relopts, sizeof(LtreeGistOptions));
740 add_local_int_reloption(relopts, "siglen",
741 "signature length in bytes",
742 LTREE_SIGLEN_DEFAULT,
743 INTALIGN(1),
744 LTREE_SIGLEN_MAX,
745 offsetof(LtreeGistOptions, siglen));
746 register_reloptions_validator(relopts, ltree_gist_relopts_validator);
748 PG_RETURN_VOID();