2 * GiST support for ltree
3 * Teodor Sigaev <teodor@stack.net>
4 * contrib/ltree/ltree_gist.c
8 #include "access/gist.h"
9 #include "access/reloptions.h"
10 #include "access/stratnum.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
);
22 ltree_gist_in(PG_FUNCTION_ARGS
)
25 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED
),
26 errmsg("cannot accept a value of type %s", "ltree_gist")));
28 PG_RETURN_VOID(); /* keep compiler quiet */
32 ltree_gist_out(PG_FUNCTION_ARGS
)
35 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED
),
36 errmsg("cannot display a value of type %s", "ltree_gist")));
38 PG_RETURN_VOID(); /* keep compiler quiet */
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
);
56 result
->flag
|= LTG_ALLTRUE
;
58 memcpy(LTG_SIGN(result
), sign
, siglen
);
60 memset(LTG_SIGN(result
), 0, siglen
);
64 memcpy(LTG_LNODE(result
, siglen
), left
, VARSIZE(left
));
66 if (!right
|| left
== right
|| ISEQ(left
, right
))
67 result
->flag
|= LTG_NORIGHT
;
69 memcpy(LTG_RNODE(result
, siglen
), right
, VARSIZE(right
));
75 result
->flag
= LTG_ONENODE
;
76 memcpy(LTG_NODE(result
), left
, VARSIZE(left
));
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))
94 ltree_compress(PG_FUNCTION_ARGS
)
96 GISTENTRY
*entry
= (GISTENTRY
*) PG_GETARG_POINTER(0);
97 GISTENTRY
*retval
= entry
;
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
);
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
);
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();
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
));
147 BITVECP sa
= LTG_SIGN(a
),
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
);
159 if (!LTG_ISALLTRUE(a
))
172 PG_RETURN_POINTER(result
);
176 hashing(BITVECP sign
, ltree
*t
, int siglen
)
178 int tlen
= t
->numlevel
;
179 ltree_level
*cur
= LTREE_FIRST(t
);
184 hash
= ltree_crc32_sz(cur
->name
, cur
->len
);
185 HASH(sign
, hash
, siglen
);
186 cur
= LEVEL_NEXT(cur
);
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
);
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)
216 if (!right
|| ltree_compare(right
, curtree
) < 0)
221 if (isalltrue
|| LTG_ISALLTRUE(cur
))
225 BITVECP sc
= LTG_SIGN(cur
);
228 ((unsigned char *) base
)[i
] |= sc
[i
];
231 curtree
= LTG_LNODE(cur
, siglen
);
232 if (!left
|| ltree_compare(left
, curtree
) > 0)
234 curtree
= LTG_RNODE(cur
, siglen
);
235 if (!right
|| ltree_compare(right
, curtree
) < 0)
240 if (isalltrue
== false)
245 if (((unsigned char *) base
)[i
] != 0xff)
253 result
= ltree_gist_alloc(isalltrue
, base
, siglen
, left
, right
);
255 *size
= VARSIZE(result
);
257 PG_RETURN_POINTER(result
);
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();
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 */
286 treekey_cmp(const void *a
, const void *b
)
288 return ltree_compare(((const RIX
*) a
)->r
,
289 ((const RIX
*) b
)->r
);
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();
310 BITVECP ls
= palloc0(siglen
),
311 rs
= palloc0(siglen
);
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
);
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
))
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
;
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
);
348 if (lisat
|| LTG_ISALLTRUE(lu
))
352 BITVECP sc
= LTG_SIGN(lu
);
355 ((unsigned char *) ls
)[i
] |= sc
[i
];
361 v
->spl_right
[v
->spl_nright
] = array
[j
].index
;
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
);
369 if (risat
|| LTG_ISALLTRUE(lu
))
373 BITVECP sc
= LTG_SIGN(lu
);
376 ((unsigned char *) rs
)[i
] |= sc
[i
];
387 if (((unsigned char *) ls
)[i
] != 0xff)
400 if (((unsigned char *) rs
)[i
] != 0xff)
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
);
417 v
->spl_ldatum
= PointerGetDatum(lu
);
418 v
->spl_rdatum
= PointerGetDatum(ru
);
420 PG_RETURN_POINTER(v
);
424 gist_isparent(ltree_gist
*key
, ltree
*query
, int siglen
)
426 int32 numlevel
= query
->numlevel
;
429 for (i
= query
->numlevel
; i
>= 0; i
--)
432 if (ltree_compare(query
, LTG_GETLNODE(key
, siglen
)) >= 0 &&
433 ltree_compare(query
, LTG_GETRNODE(key
, siglen
)) <= 0)
435 query
->numlevel
= numlevel
;
440 query
->numlevel
= numlevel
;
445 copy_ltree(ltree
*src
)
447 ltree
*dst
= (ltree
*) palloc0(VARSIZE(src
));
449 memcpy(dst
, src
, VARSIZE(src
));
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
));
460 if (left
->numlevel
> query
->numlevel
)
461 left
->numlevel
= query
->numlevel
;
463 if (ltree_compare(query
, left
) < 0)
466 if (right
->numlevel
> query
->numlevel
)
467 right
->numlevel
= query
->numlevel
;
469 if (res
&& ltree_compare(query
, right
) > 0)
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
))
490 if (curq
->numvar
&& LQL_CANLOOKSIGN(curq
))
492 bool isexist
= false;
493 int vlen
= curq
->numvar
;
494 lquery_variant
*curv
= LQL_FIRST(curq
);
498 if (GETBIT(sign
, HASHVAL(curv
->val
, siglen
)))
503 curv
= LVAR_NEXT(curv
);
510 curq
= LQL_NEXT(curq
);
518 gist_tqcmp(ltree
*t
, lquery
*q
)
520 ltree_level
*al
= LTREE_FIRST(t
);
521 lquery_level
*ql
= LQUERY_FIRST(q
);
523 int an
= t
->numlevel
;
524 int bn
= q
->firstgood
;
527 while (an
> 0 && bn
> 0)
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
;
543 return Min(t
->numlevel
, q
->firstgood
) - q
->firstgood
;
547 gist_between(ltree_gist
*key
, lquery
*query
, int siglen
)
549 if (query
->firstgood
== 0)
552 if (gist_tqcmp(LTG_GETLNODE(key
, siglen
), query
) > 0)
555 if (gist_tqcmp(LTG_GETRNODE(key
, siglen
), query
) < 0)
561 typedef struct LtreeSignature
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;
576 gist_qtxt(ltree_gist
*key
, ltxtquery
*query
, int siglen
)
580 if (LTG_ISALLTRUE(key
))
583 sig
.sign
= LTG_SIGN(key
);
586 return ltree_execute(GETQUERY(query
),
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)
599 (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR
),
600 errmsg("array must be one-dimensional")));
601 if (array_contains_nulls(_query
))
603 (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED
),
604 errmsg("array must not contain nulls")));
608 if (gist_qe(key
, query
, siglen
) && gist_between(key
, query
, siglen
))
611 query
= NEXTVAL(query
);
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
);
629 /* All cases served by this function are exact */
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);
641 case BTLessEqualStrategyNumber
:
642 query
= PG_GETARG_LTREE_P(1);
643 res
= (ltree_compare((ltree
*) query
, LTG_GETLNODE(key
, siglen
)) >= 0);
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);
650 res
= (ltree_compare((ltree
*) query
, LTG_GETLNODE(key
, siglen
)) >= 0
652 ltree_compare((ltree
*) query
, LTG_GETRNODE(key
, siglen
)) <= 0);
654 case BTGreaterEqualStrategyNumber
:
655 query
= PG_GETARG_LTREE_P(1);
656 res
= (ltree_compare((ltree
*) query
, LTG_GETRNODE(key
, siglen
)) <= 0);
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);
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
);
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
);
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
)
688 res
= (gist_qe(key
, (lquery
*) query
, siglen
) &&
689 gist_between(key
, (lquery
*) query
, siglen
));
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
)
700 res
= gist_qtxt(key
, (ltxtquery
*) query
, siglen
);
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
)
711 res
= arrq_cons(key
, (ArrayType
*) query
, siglen
);
715 elog(ERROR
, "unrecognized StrategyNumber: %d", strategy
);
718 PG_FREE_IF_COPY(query
, 1);
723 ltree_gist_relopts_validator(void *parsed_options
, relopt_value
*vals
,
726 LtreeGistOptions
*options
= (LtreeGistOptions
*) parsed_options
;
728 if (options
->siglen
!= INTALIGN(options
->siglen
))
730 (errcode(ERRCODE_INVALID_PARAMETER_VALUE
),
731 errmsg("siglen value must be a multiple of %d", ALIGNOF_INT
)));
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
,
745 offsetof(LtreeGistOptions
, siglen
));
746 register_reloptions_validator(relopts
, ltree_gist_relopts_validator
);