Fix xslt_process() to ensure that it inserts a NULL terminator after the
[PostgreSQL.git] / contrib / ltree / ltree_gist.c
blob2f69d34b3a645d489b0277a15e9d0250a2dc83c8
1 /*
2 * GiST support for ltree
3 * Teodor Sigaev <teodor@stack.net>
4 * $PostgreSQL$
5 */
6 #include "postgres.h"
8 #include "access/gist.h"
9 #include "access/nbtree.h"
10 #include "access/skey.h"
11 #include "utils/array.h"
12 #include "crc32.h"
13 #include "ltree.h"
15 #define NEXTVAL(x) ( (lquery*)( (char*)(x) + INTALIGN( VARSIZE(x) ) ) )
17 PG_FUNCTION_INFO_V1(ltree_gist_in);
18 Datum ltree_gist_in(PG_FUNCTION_ARGS);
20 PG_FUNCTION_INFO_V1(ltree_gist_out);
21 Datum ltree_gist_out(PG_FUNCTION_ARGS);
23 Datum
24 ltree_gist_in(PG_FUNCTION_ARGS)
26 ereport(ERROR,
27 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
28 errmsg("ltree_gist_in() not implemented")));
29 PG_RETURN_DATUM(0);
32 Datum
33 ltree_gist_out(PG_FUNCTION_ARGS)
35 ereport(ERROR,
36 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
37 errmsg("ltree_gist_out() not implemented")));
38 PG_RETURN_DATUM(0);
41 PG_FUNCTION_INFO_V1(ltree_compress);
42 Datum ltree_compress(PG_FUNCTION_ARGS);
44 PG_FUNCTION_INFO_V1(ltree_decompress);
45 Datum ltree_decompress(PG_FUNCTION_ARGS);
47 PG_FUNCTION_INFO_V1(ltree_same);
48 Datum ltree_same(PG_FUNCTION_ARGS);
50 PG_FUNCTION_INFO_V1(ltree_union);
51 Datum ltree_union(PG_FUNCTION_ARGS);
53 PG_FUNCTION_INFO_V1(ltree_penalty);
54 Datum ltree_penalty(PG_FUNCTION_ARGS);
56 PG_FUNCTION_INFO_V1(ltree_picksplit);
57 Datum ltree_picksplit(PG_FUNCTION_ARGS);
59 PG_FUNCTION_INFO_V1(ltree_consistent);
60 Datum ltree_consistent(PG_FUNCTION_ARGS);
62 #define ISEQ(a,b) ( (a)->numlevel == (b)->numlevel && ltree_compare(a,b)==0 )
63 #define GETENTRY(vec,pos) ((ltree_gist *) DatumGetPointer((vec)->vector[(pos)].key))
65 Datum
66 ltree_compress(PG_FUNCTION_ARGS)
68 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
69 GISTENTRY *retval = entry;
71 if (entry->leafkey)
72 { /* ltree */
73 ltree_gist *key;
74 ltree *val = (ltree *) DatumGetPointer(PG_DETOAST_DATUM(entry->key));
75 int4 len = LTG_HDRSIZE + VARSIZE(val);
77 key = (ltree_gist *) palloc(len);
78 SET_VARSIZE(key, len);
79 key->flag = LTG_ONENODE;
80 memcpy((void *) LTG_NODE(key), (void *) val, VARSIZE(val));
82 retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
83 gistentryinit(*retval, PointerGetDatum(key),
84 entry->rel, entry->page,
85 entry->offset, FALSE);
87 PG_RETURN_POINTER(retval);
90 Datum
91 ltree_decompress(PG_FUNCTION_ARGS)
93 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
94 ltree_gist *key = (ltree_gist *) DatumGetPointer(PG_DETOAST_DATUM(entry->key));
96 if (PointerGetDatum(key) != entry->key)
98 GISTENTRY *retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
100 gistentryinit(*retval, PointerGetDatum(key),
101 entry->rel, entry->page,
102 entry->offset, FALSE);
103 PG_RETURN_POINTER(retval);
105 PG_RETURN_POINTER(entry);
108 Datum
109 ltree_same(PG_FUNCTION_ARGS)
111 ltree_gist *a = (ltree_gist *) PG_GETARG_POINTER(0);
112 ltree_gist *b = (ltree_gist *) PG_GETARG_POINTER(1);
113 bool *result = (bool *) PG_GETARG_POINTER(2);
115 *result = false;
116 if (LTG_ISONENODE(a) != LTG_ISONENODE(b))
117 PG_RETURN_POINTER(result);
119 if (LTG_ISONENODE(a))
120 *result = (ISEQ(LTG_NODE(a), LTG_NODE(b))) ? true : false;
121 else
123 int4 i;
124 BITVECP sa = LTG_SIGN(a),
125 sb = LTG_SIGN(b);
127 if (LTG_ISALLTRUE(a) != LTG_ISALLTRUE(b))
128 PG_RETURN_POINTER(result);
130 if (!ISEQ(LTG_LNODE(a), LTG_LNODE(b)))
131 PG_RETURN_POINTER(result);
132 if (!ISEQ(LTG_RNODE(a), LTG_RNODE(b)))
133 PG_RETURN_POINTER(result);
135 *result = true;
136 if (!LTG_ISALLTRUE(a))
138 LOOPBYTE
140 if (sa[i] != sb[i])
142 *result = false;
143 break;
149 PG_RETURN_POINTER(result);
152 static void
153 hashing(BITVECP sign, ltree *t)
155 int tlen = t->numlevel;
156 ltree_level *cur = LTREE_FIRST(t);
157 int hash;
159 while (tlen > 0)
161 hash = ltree_crc32_sz(cur->name, cur->len);
162 HASH(sign, hash);
163 cur = LEVEL_NEXT(cur);
164 tlen--;
168 Datum
169 ltree_union(PG_FUNCTION_ARGS)
171 GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
172 int *size = (int *) PG_GETARG_POINTER(1);
173 BITVEC base;
174 int4 i,
176 ltree_gist *result,
177 *cur;
178 ltree *left = NULL,
179 *right = NULL,
180 *curtree;
181 bool isalltrue = false;
182 bool isleqr;
184 MemSet((void *) base, 0, sizeof(BITVEC));
185 for (j = 0; j < entryvec->n; j++)
187 cur = GETENTRY(entryvec, j);
188 if (LTG_ISONENODE(cur))
190 curtree = LTG_NODE(cur);
191 hashing(base, curtree);
192 if (!left || ltree_compare(left, curtree) > 0)
193 left = curtree;
194 if (!right || ltree_compare(right, curtree) < 0)
195 right = curtree;
197 else
199 if (isalltrue || LTG_ISALLTRUE(cur))
200 isalltrue = true;
201 else
203 BITVECP sc = LTG_SIGN(cur);
205 LOOPBYTE
206 ((unsigned char *) base)[i] |= sc[i];
209 curtree = LTG_LNODE(cur);
210 if (!left || ltree_compare(left, curtree) > 0)
211 left = curtree;
212 curtree = LTG_RNODE(cur);
213 if (!right || ltree_compare(right, curtree) < 0)
214 right = curtree;
218 if (isalltrue == false)
220 isalltrue = true;
221 LOOPBYTE
223 if (((unsigned char *) base)[i] != 0xff)
225 isalltrue = false;
226 break;
231 isleqr = (left == right || ISEQ(left, right)) ? true : false;
232 *size = LTG_HDRSIZE + ((isalltrue) ? 0 : SIGLEN) + VARSIZE(left) + ((isleqr) ? 0 : VARSIZE(right));
234 result = (ltree_gist *) palloc(*size);
235 SET_VARSIZE(result, *size);
236 result->flag = 0;
238 if (isalltrue)
239 result->flag |= LTG_ALLTRUE;
240 else
241 memcpy((void *) LTG_SIGN(result), base, SIGLEN);
243 memcpy((void *) LTG_LNODE(result), (void *) left, VARSIZE(left));
244 if (isleqr)
245 result->flag |= LTG_NORIGHT;
246 else
247 memcpy((void *) LTG_RNODE(result), (void *) right, VARSIZE(right));
249 PG_RETURN_POINTER(result);
252 Datum
253 ltree_penalty(PG_FUNCTION_ARGS)
255 ltree_gist *origval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(0))->key);
256 ltree_gist *newval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(1))->key);
257 float *penalty = (float *) PG_GETARG_POINTER(2);
258 int4 cmpr,
259 cmpl;
261 cmpl = ltree_compare(LTG_GETLNODE(origval), LTG_GETLNODE(newval));
262 cmpr = ltree_compare(LTG_GETRNODE(newval), LTG_GETRNODE(origval));
264 *penalty = Max(cmpl, 0) + Max(cmpr, 0);
266 PG_RETURN_POINTER(penalty);
269 /* used for sorting */
270 typedef struct rix
272 int index;
273 ltree *r;
274 } RIX;
276 static int
277 treekey_cmp(const void *a, const void *b)
279 return ltree_compare(
280 ((RIX *) a)->r,
281 ((RIX *) b)->r
286 Datum
287 ltree_picksplit(PG_FUNCTION_ARGS)
289 GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
290 GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
291 OffsetNumber j;
292 int4 i;
293 RIX *array;
294 OffsetNumber maxoff;
295 int nbytes;
296 int size;
297 ltree *lu_l,
298 *lu_r,
299 *ru_l,
300 *ru_r;
301 ltree_gist *lu,
302 *ru;
303 BITVEC ls,
305 bool lisat = false,
306 risat = false,
307 isleqr;
309 memset((void *) ls, 0, sizeof(BITVEC));
310 memset((void *) rs, 0, sizeof(BITVEC));
311 maxoff = entryvec->n - 1;
312 nbytes = (maxoff + 2) * sizeof(OffsetNumber);
313 v->spl_left = (OffsetNumber *) palloc(nbytes);
314 v->spl_right = (OffsetNumber *) palloc(nbytes);
315 v->spl_nleft = 0;
316 v->spl_nright = 0;
317 array = (RIX *) palloc(sizeof(RIX) * (maxoff + 1));
319 /* copy the data into RIXes, and sort the RIXes */
320 for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
322 array[j].index = j;
323 lu = GETENTRY(entryvec, j); /* use as tmp val */
324 array[j].r = LTG_GETLNODE(lu);
327 qsort((void *) &array[FirstOffsetNumber], maxoff - FirstOffsetNumber + 1,
328 sizeof(RIX), treekey_cmp);
330 lu_l = lu_r = ru_l = ru_r = NULL;
331 for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
333 lu = GETENTRY(entryvec, array[j].index); /* use as tmp val */
334 if (j <= (maxoff - FirstOffsetNumber + 1) / 2)
336 v->spl_left[v->spl_nleft] = array[j].index;
337 v->spl_nleft++;
338 if (lu_r == NULL || ltree_compare(LTG_GETRNODE(lu), lu_r) > 0)
339 lu_r = LTG_GETRNODE(lu);
340 if (LTG_ISONENODE(lu))
341 hashing(ls, LTG_NODE(lu));
342 else
344 if (lisat || LTG_ISALLTRUE(lu))
345 lisat = true;
346 else
348 BITVECP sc = LTG_SIGN(lu);
350 LOOPBYTE
351 ((unsigned char *) ls)[i] |= sc[i];
355 else
357 v->spl_right[v->spl_nright] = array[j].index;
358 v->spl_nright++;
359 if (ru_r == NULL || ltree_compare(LTG_GETRNODE(lu), ru_r) > 0)
360 ru_r = LTG_GETRNODE(lu);
361 if (LTG_ISONENODE(lu))
362 hashing(rs, LTG_NODE(lu));
363 else
365 if (risat || LTG_ISALLTRUE(lu))
366 risat = true;
367 else
369 BITVECP sc = LTG_SIGN(lu);
371 LOOPBYTE
372 ((unsigned char *) rs)[i] |= sc[i];
378 if (lisat == false)
380 lisat = true;
381 LOOPBYTE
383 if (((unsigned char *) ls)[i] != 0xff)
385 lisat = false;
386 break;
391 if (risat == false)
393 risat = true;
394 LOOPBYTE
396 if (((unsigned char *) rs)[i] != 0xff)
398 risat = false;
399 break;
404 lu_l = LTG_GETLNODE(GETENTRY(entryvec, array[FirstOffsetNumber].index));
405 isleqr = (lu_l == lu_r || ISEQ(lu_l, lu_r)) ? true : false;
406 size = LTG_HDRSIZE + ((lisat) ? 0 : SIGLEN) + VARSIZE(lu_l) + ((isleqr) ? 0 : VARSIZE(lu_r));
407 lu = (ltree_gist *) palloc(size);
408 SET_VARSIZE(lu, size);
409 lu->flag = 0;
410 if (lisat)
411 lu->flag |= LTG_ALLTRUE;
412 else
413 memcpy((void *) LTG_SIGN(lu), ls, SIGLEN);
414 memcpy((void *) LTG_LNODE(lu), (void *) lu_l, VARSIZE(lu_l));
415 if (isleqr)
416 lu->flag |= LTG_NORIGHT;
417 else
418 memcpy((void *) LTG_RNODE(lu), (void *) lu_r, VARSIZE(lu_r));
421 ru_l = LTG_GETLNODE(GETENTRY(entryvec, array[1 + ((maxoff - FirstOffsetNumber + 1) / 2)].index));
422 isleqr = (ru_l == ru_r || ISEQ(ru_l, ru_r)) ? true : false;
423 size = LTG_HDRSIZE + ((risat) ? 0 : SIGLEN) + VARSIZE(ru_l) + ((isleqr) ? 0 : VARSIZE(ru_r));
424 ru = (ltree_gist *) palloc(size);
425 SET_VARSIZE(ru, size);
426 ru->flag = 0;
427 if (risat)
428 ru->flag |= LTG_ALLTRUE;
429 else
430 memcpy((void *) LTG_SIGN(ru), rs, SIGLEN);
431 memcpy((void *) LTG_LNODE(ru), (void *) ru_l, VARSIZE(ru_l));
432 if (isleqr)
433 ru->flag |= LTG_NORIGHT;
434 else
435 memcpy((void *) LTG_RNODE(ru), (void *) ru_r, VARSIZE(ru_r));
437 v->spl_ldatum = PointerGetDatum(lu);
438 v->spl_rdatum = PointerGetDatum(ru);
440 PG_RETURN_POINTER(v);
443 static bool
444 gist_isparent(ltree_gist *key, ltree *query)
446 int4 numlevel = query->numlevel;
447 int i;
449 for (i = query->numlevel; i >= 0; i--)
451 query->numlevel = i;
452 if (ltree_compare(query, LTG_GETLNODE(key)) >= 0 && ltree_compare(query, LTG_GETRNODE(key)) <= 0)
454 query->numlevel = numlevel;
455 return true;
459 query->numlevel = numlevel;
460 return false;
463 static ltree *
464 copy_ltree(ltree *src)
466 ltree *dst = (ltree *) palloc(VARSIZE(src));
468 memcpy(dst, src, VARSIZE(src));
469 return dst;
472 static bool
473 gist_ischild(ltree_gist *key, ltree *query)
475 ltree *left = copy_ltree(LTG_GETLNODE(key));
476 ltree *right = copy_ltree(LTG_GETRNODE(key));
477 bool res = true;
479 if (left->numlevel > query->numlevel)
480 left->numlevel = query->numlevel;
482 if (ltree_compare(query, left) < 0)
483 res = false;
485 if (right->numlevel > query->numlevel)
486 right->numlevel = query->numlevel;
488 if (res && ltree_compare(query, right) > 0)
489 res = false;
491 pfree(left);
492 pfree(right);
494 return res;
497 static bool
498 gist_qe(ltree_gist *key, lquery *query)
500 lquery_level *curq = LQUERY_FIRST(query);
501 BITVECP sign = LTG_SIGN(key);
502 int qlen = query->numlevel;
504 if (LTG_ISALLTRUE(key))
505 return true;
507 while (qlen > 0)
509 if (curq->numvar && LQL_CANLOOKSIGN(curq))
511 bool isexist = false;
512 int vlen = curq->numvar;
513 lquery_variant *curv = LQL_FIRST(curq);
515 while (vlen > 0)
517 if (GETBIT(sign, HASHVAL(curv->val)))
519 isexist = true;
520 break;
522 curv = LVAR_NEXT(curv);
523 vlen--;
525 if (!isexist)
526 return false;
529 curq = LQL_NEXT(curq);
530 qlen--;
533 return true;
536 static int
537 gist_tqcmp(ltree *t, lquery *q)
539 ltree_level *al = LTREE_FIRST(t);
540 lquery_level *ql = LQUERY_FIRST(q);
541 lquery_variant *bl;
542 int an = t->numlevel;
543 int bn = q->firstgood;
544 int res = 0;
546 while (an > 0 && bn > 0)
548 bl = LQL_FIRST(ql);
549 if ((res = strncmp(al->name, bl->name, Min(al->len, bl->len))) == 0)
551 if (al->len != bl->len)
552 return al->len - bl->len;
554 else
555 return res;
556 an--;
557 bn--;
558 al = LEVEL_NEXT(al);
559 ql = LQL_NEXT(ql);
562 return Min(t->numlevel, q->firstgood) - q->firstgood;
565 static bool
566 gist_between(ltree_gist *key, lquery *query)
568 if (query->firstgood == 0)
569 return true;
571 if (gist_tqcmp(LTG_GETLNODE(key), query) > 0)
572 return false;
574 if (gist_tqcmp(LTG_GETRNODE(key), query) < 0)
575 return false;
577 return true;
580 static bool
581 checkcondition_bit(void *checkval, ITEM *val)
583 return (FLG_CANLOOKSIGN(val->flag)) ? GETBIT(checkval, HASHVAL(val->val)) : true;
586 static bool
587 gist_qtxt(ltree_gist *key, ltxtquery *query)
589 if (LTG_ISALLTRUE(key))
590 return true;
592 return ltree_execute(
593 GETQUERY(query),
594 (void *) LTG_SIGN(key), false,
595 checkcondition_bit
599 static bool
600 arrq_cons(ltree_gist *key, ArrayType *_query)
602 lquery *query = (lquery *) ARR_DATA_PTR(_query);
603 int num = ArrayGetNItems(ARR_NDIM(_query), ARR_DIMS(_query));
605 if (ARR_NDIM(_query) != 1)
606 ereport(ERROR,
607 (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
608 errmsg("array must be one-dimensional")));
609 if (ARR_HASNULL(_query))
610 ereport(ERROR,
611 (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
612 errmsg("array must not contain nulls")));
614 while (num > 0)
616 if (gist_qe(key, query) && gist_between(key, query))
617 return true;
618 num--;
619 query = NEXTVAL(query);
621 return false;
624 Datum
625 ltree_consistent(PG_FUNCTION_ARGS)
627 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
628 StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
630 /* Oid subtype = PG_GETARG_OID(3); */
631 bool *recheck = (bool *) PG_GETARG_POINTER(4);
632 ltree_gist *key = (ltree_gist *) DatumGetPointer(entry->key);
633 void *query = NULL;
634 bool res = false;
636 /* All cases served by this function are exact */
637 *recheck = false;
639 switch (strategy)
641 case BTLessStrategyNumber:
642 query = PG_GETARG_LTREE(1);
643 res = (GIST_LEAF(entry)) ?
644 (ltree_compare((ltree *) query, LTG_NODE(key)) > 0)
646 (ltree_compare((ltree *) query, LTG_GETLNODE(key)) >= 0);
647 break;
648 case BTLessEqualStrategyNumber:
649 query = PG_GETARG_LTREE(1);
650 res = (ltree_compare((ltree *) query, LTG_GETLNODE(key)) >= 0);
651 break;
652 case BTEqualStrategyNumber:
653 query = PG_GETARG_LTREE(1);
654 if (GIST_LEAF(entry))
655 res = (ltree_compare((ltree *) query, LTG_NODE(key)) == 0);
656 else
657 res = (
658 ltree_compare((ltree *) query, LTG_GETLNODE(key)) >= 0
660 ltree_compare((ltree *) query, LTG_GETRNODE(key)) <= 0
662 break;
663 case BTGreaterEqualStrategyNumber:
664 query = PG_GETARG_LTREE(1);
665 res = (ltree_compare((ltree *) query, LTG_GETRNODE(key)) <= 0);
666 break;
667 case BTGreaterStrategyNumber:
668 query = PG_GETARG_LTREE(1);
669 res = (GIST_LEAF(entry)) ?
670 (ltree_compare((ltree *) query, LTG_GETRNODE(key)) < 0)
672 (ltree_compare((ltree *) query, LTG_GETRNODE(key)) <= 0);
673 break;
674 case 10:
675 query = PG_GETARG_LTREE_COPY(1);
676 res = (GIST_LEAF(entry)) ?
677 inner_isparent((ltree *) query, LTG_NODE(key))
679 gist_isparent(key, (ltree *) query);
680 break;
681 case 11:
682 query = PG_GETARG_LTREE(1);
683 res = (GIST_LEAF(entry)) ?
684 inner_isparent(LTG_NODE(key), (ltree *) query)
686 gist_ischild(key, (ltree *) query);
687 break;
688 case 12:
689 case 13:
690 query = PG_GETARG_LQUERY(1);
691 if (GIST_LEAF(entry))
692 res = DatumGetBool(DirectFunctionCall2(ltq_regex,
693 PointerGetDatum(LTG_NODE(key)),
694 PointerGetDatum((lquery *) query)
696 else
697 res = (gist_qe(key, (lquery *) query) && gist_between(key, (lquery *) query));
698 break;
699 case 14:
700 case 15:
701 query = PG_GETARG_LQUERY(1);
702 if (GIST_LEAF(entry))
703 res = DatumGetBool(DirectFunctionCall2(ltxtq_exec,
704 PointerGetDatum(LTG_NODE(key)),
705 PointerGetDatum((lquery *) query)
707 else
708 res = gist_qtxt(key, (ltxtquery *) query);
709 break;
710 case 16:
711 case 17:
712 query = DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(1)));
713 if (GIST_LEAF(entry))
714 res = DatumGetBool(DirectFunctionCall2(lt_q_regex,
715 PointerGetDatum(LTG_NODE(key)),
716 PointerGetDatum((ArrayType *) query)
718 else
719 res = arrq_cons(key, (ArrayType *) query);
720 break;
721 default:
722 /* internal error */
723 elog(ERROR, "unrecognized StrategyNumber: %d", strategy);
726 PG_FREE_IF_COPY(query, 1);
727 PG_RETURN_BOOL(res);