2 * GiST support for ltree
3 * Teodor Sigaev <teodor@stack.net>
8 #include "access/gist.h"
9 #include "access/nbtree.h"
10 #include "access/skey.h"
11 #include "utils/array.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
);
24 ltree_gist_in(PG_FUNCTION_ARGS
)
27 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED
),
28 errmsg("ltree_gist_in() not implemented")));
33 ltree_gist_out(PG_FUNCTION_ARGS
)
36 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED
),
37 errmsg("ltree_gist_out() not implemented")));
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))
66 ltree_compress(PG_FUNCTION_ARGS
)
68 GISTENTRY
*entry
= (GISTENTRY
*) PG_GETARG_POINTER(0);
69 GISTENTRY
*retval
= entry
;
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
);
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
);
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);
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;
124 BITVECP sa
= LTG_SIGN(a
),
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
);
136 if (!LTG_ISALLTRUE(a
))
149 PG_RETURN_POINTER(result
);
153 hashing(BITVECP sign
, ltree
*t
)
155 int tlen
= t
->numlevel
;
156 ltree_level
*cur
= LTREE_FIRST(t
);
161 hash
= ltree_crc32_sz(cur
->name
, cur
->len
);
163 cur
= LEVEL_NEXT(cur
);
169 ltree_union(PG_FUNCTION_ARGS
)
171 GistEntryVector
*entryvec
= (GistEntryVector
*) PG_GETARG_POINTER(0);
172 int *size
= (int *) PG_GETARG_POINTER(1);
181 bool isalltrue
= false;
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)
194 if (!right
|| ltree_compare(right
, curtree
) < 0)
199 if (isalltrue
|| LTG_ISALLTRUE(cur
))
203 BITVECP sc
= LTG_SIGN(cur
);
206 ((unsigned char *) base
)[i
] |= sc
[i
];
209 curtree
= LTG_LNODE(cur
);
210 if (!left
|| ltree_compare(left
, curtree
) > 0)
212 curtree
= LTG_RNODE(cur
);
213 if (!right
|| ltree_compare(right
, curtree
) < 0)
218 if (isalltrue
== false)
223 if (((unsigned char *) base
)[i
] != 0xff)
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
);
239 result
->flag
|= LTG_ALLTRUE
;
241 memcpy((void *) LTG_SIGN(result
), base
, SIGLEN
);
243 memcpy((void *) LTG_LNODE(result
), (void *) left
, VARSIZE(left
));
245 result
->flag
|= LTG_NORIGHT
;
247 memcpy((void *) LTG_RNODE(result
), (void *) right
, VARSIZE(right
));
249 PG_RETURN_POINTER(result
);
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);
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 */
277 treekey_cmp(const void *a
, const void *b
)
279 return ltree_compare(
287 ltree_picksplit(PG_FUNCTION_ARGS
)
289 GistEntryVector
*entryvec
= (GistEntryVector
*) PG_GETARG_POINTER(0);
290 GIST_SPLITVEC
*v
= (GIST_SPLITVEC
*) PG_GETARG_POINTER(1);
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
);
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
))
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
;
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
));
344 if (lisat
|| LTG_ISALLTRUE(lu
))
348 BITVECP sc
= LTG_SIGN(lu
);
351 ((unsigned char *) ls
)[i
] |= sc
[i
];
357 v
->spl_right
[v
->spl_nright
] = array
[j
].index
;
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
));
365 if (risat
|| LTG_ISALLTRUE(lu
))
369 BITVECP sc
= LTG_SIGN(lu
);
372 ((unsigned char *) rs
)[i
] |= sc
[i
];
383 if (((unsigned char *) ls
)[i
] != 0xff)
396 if (((unsigned char *) rs
)[i
] != 0xff)
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
);
411 lu
->flag
|= LTG_ALLTRUE
;
413 memcpy((void *) LTG_SIGN(lu
), ls
, SIGLEN
);
414 memcpy((void *) LTG_LNODE(lu
), (void *) lu_l
, VARSIZE(lu_l
));
416 lu
->flag
|= LTG_NORIGHT
;
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
);
428 ru
->flag
|= LTG_ALLTRUE
;
430 memcpy((void *) LTG_SIGN(ru
), rs
, SIGLEN
);
431 memcpy((void *) LTG_LNODE(ru
), (void *) ru_l
, VARSIZE(ru_l
));
433 ru
->flag
|= LTG_NORIGHT
;
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
);
444 gist_isparent(ltree_gist
*key
, ltree
*query
)
446 int4 numlevel
= query
->numlevel
;
449 for (i
= query
->numlevel
; i
>= 0; i
--)
452 if (ltree_compare(query
, LTG_GETLNODE(key
)) >= 0 && ltree_compare(query
, LTG_GETRNODE(key
)) <= 0)
454 query
->numlevel
= numlevel
;
459 query
->numlevel
= numlevel
;
464 copy_ltree(ltree
*src
)
466 ltree
*dst
= (ltree
*) palloc(VARSIZE(src
));
468 memcpy(dst
, src
, VARSIZE(src
));
473 gist_ischild(ltree_gist
*key
, ltree
*query
)
475 ltree
*left
= copy_ltree(LTG_GETLNODE(key
));
476 ltree
*right
= copy_ltree(LTG_GETRNODE(key
));
479 if (left
->numlevel
> query
->numlevel
)
480 left
->numlevel
= query
->numlevel
;
482 if (ltree_compare(query
, left
) < 0)
485 if (right
->numlevel
> query
->numlevel
)
486 right
->numlevel
= query
->numlevel
;
488 if (res
&& ltree_compare(query
, right
) > 0)
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
))
509 if (curq
->numvar
&& LQL_CANLOOKSIGN(curq
))
511 bool isexist
= false;
512 int vlen
= curq
->numvar
;
513 lquery_variant
*curv
= LQL_FIRST(curq
);
517 if (GETBIT(sign
, HASHVAL(curv
->val
)))
522 curv
= LVAR_NEXT(curv
);
529 curq
= LQL_NEXT(curq
);
537 gist_tqcmp(ltree
*t
, lquery
*q
)
539 ltree_level
*al
= LTREE_FIRST(t
);
540 lquery_level
*ql
= LQUERY_FIRST(q
);
542 int an
= t
->numlevel
;
543 int bn
= q
->firstgood
;
546 while (an
> 0 && bn
> 0)
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
;
562 return Min(t
->numlevel
, q
->firstgood
) - q
->firstgood
;
566 gist_between(ltree_gist
*key
, lquery
*query
)
568 if (query
->firstgood
== 0)
571 if (gist_tqcmp(LTG_GETLNODE(key
), query
) > 0)
574 if (gist_tqcmp(LTG_GETRNODE(key
), query
) < 0)
581 checkcondition_bit(void *checkval
, ITEM
*val
)
583 return (FLG_CANLOOKSIGN(val
->flag
)) ? GETBIT(checkval
, HASHVAL(val
->val
)) : true;
587 gist_qtxt(ltree_gist
*key
, ltxtquery
*query
)
589 if (LTG_ISALLTRUE(key
))
592 return ltree_execute(
594 (void *) LTG_SIGN(key
), false,
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)
607 (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR
),
608 errmsg("array must be one-dimensional")));
609 if (ARR_HASNULL(_query
))
611 (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED
),
612 errmsg("array must not contain nulls")));
616 if (gist_qe(key
, query
) && gist_between(key
, query
))
619 query
= NEXTVAL(query
);
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
);
636 /* All cases served by this function are exact */
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);
648 case BTLessEqualStrategyNumber
:
649 query
= PG_GETARG_LTREE(1);
650 res
= (ltree_compare((ltree
*) query
, LTG_GETLNODE(key
)) >= 0);
652 case BTEqualStrategyNumber
:
653 query
= PG_GETARG_LTREE(1);
654 if (GIST_LEAF(entry
))
655 res
= (ltree_compare((ltree
*) query
, LTG_NODE(key
)) == 0);
658 ltree_compare((ltree
*) query
, LTG_GETLNODE(key
)) >= 0
660 ltree_compare((ltree
*) query
, LTG_GETRNODE(key
)) <= 0
663 case BTGreaterEqualStrategyNumber
:
664 query
= PG_GETARG_LTREE(1);
665 res
= (ltree_compare((ltree
*) query
, LTG_GETRNODE(key
)) <= 0);
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);
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
);
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
);
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
)
697 res
= (gist_qe(key
, (lquery
*) query
) && gist_between(key
, (lquery
*) query
));
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
)
708 res
= gist_qtxt(key
, (ltxtquery
*) query
);
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
)
719 res
= arrq_cons(key
, (ArrayType
*) query
);
723 elog(ERROR
, "unrecognized StrategyNumber: %d", strategy
);
726 PG_FREE_IF_COPY(query
, 1);