PostgreSQL Source Code  git master
ltree.h
Go to the documentation of this file.
1 /* contrib/ltree/ltree.h */
2 
3 #ifndef __LTREE_H__
4 #define __LTREE_H__
5 
6 #include "fmgr.h"
7 #include "tsearch/ts_locale.h"
8 #include "utils/memutils.h"
9 
10 
11 /* ltree */
12 
13 /*
14  * We want the maximum length of a label to be encoding-independent, so
15  * set it somewhat arbitrarily at 255 characters (not bytes), while using
16  * uint16 fields to hold the byte length.
17  */
18 #define LTREE_LABEL_MAX_CHARS 255
19 
20 typedef struct
21 {
22  uint16 len; /* label string length in bytes */
24 } ltree_level;
25 
26 #define LEVEL_HDRSIZE (offsetof(ltree_level,name))
27 #define LEVEL_NEXT(x) ( (ltree_level*)( ((char*)(x)) + MAXALIGN(((ltree_level*)(x))->len + LEVEL_HDRSIZE) ) )
28 
29 typedef struct
30 {
31  int32 vl_len_; /* varlena header (do not touch directly!) */
32  uint16 numlevel; /* number of labels */
33  /* Array of maxalign'd ltree_level structs follows: */
35 } ltree;
36 
37 #define LTREE_HDRSIZE MAXALIGN( offsetof(ltree, data) )
38 #define LTREE_FIRST(x) ( (ltree_level*)( ((char*)(x))+LTREE_HDRSIZE ) )
39 #define LTREE_MAX_LEVELS PG_UINT16_MAX /* ltree.numlevel is uint16 */
40 
41 
42 /* lquery */
43 
44 /* lquery_variant: one branch of some OR'ed alternatives */
45 typedef struct
46 {
47  int32 val; /* CRC of label string */
48  uint16 len; /* label string length in bytes */
49  uint8 flag; /* see LVAR_xxx flags below */
52 
53 /*
54  * Note: these macros contain too many MAXALIGN calls and so will sometimes
55  * overestimate the space needed for an lquery_variant. However, we can't
56  * change it without breaking on-disk compatibility for lquery.
57  */
58 #define LVAR_HDRSIZE MAXALIGN(offsetof(lquery_variant, name))
59 #define LVAR_NEXT(x) ( (lquery_variant*)( ((char*)(x)) + MAXALIGN(((lquery_variant*)(x))->len) + LVAR_HDRSIZE ) )
60 
61 #define LVAR_ANYEND 0x01 /* '*' flag: prefix match */
62 #define LVAR_INCASE 0x02 /* '@' flag: case-insensitive match */
63 #define LVAR_SUBLEXEME 0x04 /* '%' flag: word-wise match */
64 
65 /*
66  * In an lquery_level, "flag" contains the union of the variants' flags
67  * along with possible LQL_xxx flags; so those bit sets can't overlap.
68  *
69  * "low" and "high" are nominally the minimum and maximum number of matches.
70  * However, for backwards compatibility with pre-v13 on-disk lqueries,
71  * non-'*' levels (those with numvar > 0) only have valid low/high if the
72  * LQL_COUNT flag is set; otherwise those fields are zero, but the behavior
73  * is as if they were both 1.
74  */
75 typedef struct
76 {
77  uint16 totallen; /* total length of this level, in bytes */
78  uint16 flag; /* see LQL_xxx and LVAR_xxx flags */
79  uint16 numvar; /* number of variants; 0 means '*' */
80  uint16 low; /* minimum repeat count */
81  uint16 high; /* maximum repeat count */
82  /* Array of maxalign'd lquery_variant structs follows: */
83  char variants[FLEXIBLE_ARRAY_MEMBER];
84 } lquery_level;
85 
86 #define LQL_HDRSIZE MAXALIGN( offsetof(lquery_level,variants) )
87 #define LQL_NEXT(x) ( (lquery_level*)( ((char*)(x)) + MAXALIGN(((lquery_level*)(x))->totallen) ) )
88 #define LQL_FIRST(x) ( (lquery_variant*)( ((char*)(x))+LQL_HDRSIZE ) )
89 
90 #define LQL_NOT 0x10 /* level has '!' (NOT) prefix */
91 #define LQL_COUNT 0x20 /* level is non-'*' and has repeat counts */
92 
93 #ifdef LOWER_NODE
94 #define FLG_CANLOOKSIGN(x) ( ( (x) & ( LQL_NOT | LVAR_ANYEND | LVAR_SUBLEXEME ) ) == 0 )
95 #else
96 #define FLG_CANLOOKSIGN(x) ( ( (x) & ( LQL_NOT | LVAR_ANYEND | LVAR_SUBLEXEME | LVAR_INCASE ) ) == 0 )
97 #endif
98 #define LQL_CANLOOKSIGN(x) FLG_CANLOOKSIGN( ((lquery_level*)(x))->flag )
99 
100 typedef struct
101 {
102  int32 vl_len_; /* varlena header (do not touch directly!) */
103  uint16 numlevel; /* number of lquery_levels */
104  uint16 firstgood; /* number of leading simple-match levels */
105  uint16 flag; /* see LQUERY_xxx flags below */
106  /* Array of maxalign'd lquery_level structs follows: */
108 } lquery;
109 
110 #define LQUERY_HDRSIZE MAXALIGN( offsetof(lquery, data) )
111 #define LQUERY_FIRST(x) ( (lquery_level*)( ((char*)(x))+LQUERY_HDRSIZE ) )
112 #define LQUERY_MAX_LEVELS PG_UINT16_MAX /* lquery.numlevel is uint16 */
113 
114 #define LQUERY_HASNOT 0x01
115 
116 #define ISALNUM(x) ( t_isalpha(x) || t_isdigit(x) || ( pg_mblen(x) == 1 && t_iseq((x), '_') ) )
117 
118 /* full text query */
119 
120 /*
121  * item in polish notation with back link
122  * to left operand
123  */
124 typedef struct ITEM
125 {
126  int16 type;
127  int16 left;
128  int32 val;
130  /* user-friendly value */
133 } ITEM;
134 
135 /*
136  *Storage:
137  * (len)(size)(array of ITEM)(array of operand in user-friendly form)
138  */
139 typedef struct
140 {
141  int32 vl_len_; /* varlena header (do not touch directly!) */
144 } ltxtquery;
145 
146 #define HDRSIZEQT MAXALIGN(VARHDRSZ + sizeof(int32))
147 #define COMPUTESIZE(size,lenofoperand) ( HDRSIZEQT + (size) * sizeof(ITEM) + (lenofoperand) )
148 #define LTXTQUERY_TOO_BIG(size,lenofoperand) \
149  ((size) > (MaxAllocSize - HDRSIZEQT - (lenofoperand)) / sizeof(ITEM))
150 #define GETQUERY(x) (ITEM*)( (char*)(x)+HDRSIZEQT )
151 #define GETOPERAND(x) ( (char*)GETQUERY(x) + ((ltxtquery*)x)->size * sizeof(ITEM) )
152 
153 #define ISOPERATOR(x) ( (x)=='!' || (x)=='&' || (x)=='|' || (x)=='(' || (x)==')' )
154 
155 #define END 0
156 #define ERR 1
157 #define VAL 2
158 #define OPR 3
159 #define OPEN 4
160 #define CLOSE 5
161 #define VALTRUE 6 /* for stop words */
162 #define VALFALSE 7
163 
164 
165 /* use in array iterator */
182 
183 /* Concatenation functions */
187 
188 /* Util function */
190 
191 bool ltree_execute(ITEM *curitem, void *checkval,
192  bool calcnot, bool (*chkcond) (void *checkval, ITEM *val));
193 
194 int ltree_compare(const ltree *a, const ltree *b);
195 bool inner_isparent(const ltree *c, const ltree *p);
196 bool compare_subnode(ltree_level *t, char *q, int len,
197  int (*cmpptr) (const char *, const char *, size_t), bool anyend);
198 ltree *lca_inner(ltree **a, int len);
199 int ltree_strncasecmp(const char *a, const char *b, size_t s);
200 
201 /* fmgr macros for ltree objects */
202 #define DatumGetLtreeP(X) ((ltree *) PG_DETOAST_DATUM(X))
203 #define DatumGetLtreePCopy(X) ((ltree *) PG_DETOAST_DATUM_COPY(X))
204 #define PG_GETARG_LTREE_P(n) DatumGetLtreeP(PG_GETARG_DATUM(n))
205 #define PG_GETARG_LTREE_P_COPY(n) DatumGetLtreePCopy(PG_GETARG_DATUM(n))
206 
207 #define DatumGetLqueryP(X) ((lquery *) PG_DETOAST_DATUM(X))
208 #define DatumGetLqueryPCopy(X) ((lquery *) PG_DETOAST_DATUM_COPY(X))
209 #define PG_GETARG_LQUERY_P(n) DatumGetLqueryP(PG_GETARG_DATUM(n))
210 #define PG_GETARG_LQUERY_P_COPY(n) DatumGetLqueryPCopy(PG_GETARG_DATUM(n))
211 
212 #define DatumGetLtxtqueryP(X) ((ltxtquery *) PG_DETOAST_DATUM(X))
213 #define DatumGetLtxtqueryPCopy(X) ((ltxtquery *) PG_DETOAST_DATUM_COPY(X))
214 #define PG_GETARG_LTXTQUERY_P(n) DatumGetLtxtqueryP(PG_GETARG_DATUM(n))
215 #define PG_GETARG_LTXTQUERY_P_COPY(n) DatumGetLtxtqueryPCopy(PG_GETARG_DATUM(n))
216 
217 /* GiST support for ltree */
218 
219 #define SIGLEN_MAX GISTMaxIndexKeySize
220 #define SIGLEN_DEFAULT (2 * sizeof(int32))
221 #define BITBYTE 8
222 #define SIGLEN (sizeof(int32) * SIGLENINT)
223 #define SIGLENBIT(siglen) ((siglen) * BITBYTE)
224 
225 typedef unsigned char *BITVECP;
226 
227 #define LOOPBYTE(siglen) \
228  for(i = 0; i < (siglen); i++)
229 
230 #define GETBYTE(x,i) ( *( (BITVECP)(x) + (int)( (i) / BITBYTE ) ) )
231 #define GETBITBYTE(x,i) ( ((unsigned char)(x)) >> i & 0x01 )
232 #define CLRBIT(x,i) GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITBYTE ) )
233 #define SETBIT(x,i) GETBYTE(x,i) |= ( 0x01 << ( (i) % BITBYTE ) )
234 #define GETBIT(x,i) ( (GETBYTE(x,i) >> ( (i) % BITBYTE )) & 0x01 )
235 
236 #define HASHVAL(val, siglen) (((unsigned int)(val)) % SIGLENBIT(siglen))
237 #define HASH(sign, val, siglen) SETBIT((sign), HASHVAL(val, siglen))
238 
239 /*
240  * type of index key for ltree. Tree are combined B-Tree and R-Tree
241  * Storage:
242  * Leaf pages
243  * (len)(flag)(ltree)
244  * Non-Leaf
245  * (len)(flag)(sign)(left_ltree)(right_ltree)
246  * ALLTRUE: (len)(flag)(left_ltree)(right_ltree)
247  *
248  */
249 
250 typedef struct
251 {
252  int32 vl_len_; /* varlena header (do not touch directly!) */
255 } ltree_gist;
256 
257 #define LTG_ONENODE 0x01
258 #define LTG_ALLTRUE 0x02
259 #define LTG_NORIGHT 0x04
260 
261 #define LTG_HDRSIZE MAXALIGN(VARHDRSZ + sizeof(uint32))
262 #define LTG_SIGN(x) ( (BITVECP)( ((char*)(x))+LTG_HDRSIZE ) )
263 #define LTG_NODE(x) ( (ltree*)( ((char*)(x))+LTG_HDRSIZE ) )
264 #define LTG_ISONENODE(x) ( ((ltree_gist*)(x))->flag & LTG_ONENODE )
265 #define LTG_ISALLTRUE(x) ( ((ltree_gist*)(x))->flag & LTG_ALLTRUE )
266 #define LTG_ISNORIGHT(x) ( ((ltree_gist*)(x))->flag & LTG_NORIGHT )
267 #define LTG_LNODE(x, siglen) ( (ltree*)( ( ((char*)(x))+LTG_HDRSIZE ) + ( LTG_ISALLTRUE(x) ? 0 : (siglen) ) ) )
268 #define LTG_RENODE(x, siglen) ( (ltree*)( ((char*)LTG_LNODE(x, siglen)) + VARSIZE(LTG_LNODE(x, siglen))) )
269 #define LTG_RNODE(x, siglen) ( LTG_ISNORIGHT(x) ? LTG_LNODE(x, siglen) : LTG_RENODE(x, siglen) )
270 
271 #define LTG_GETLNODE(x, siglen) ( LTG_ISONENODE(x) ? LTG_NODE(x) : LTG_LNODE(x, siglen) )
272 #define LTG_GETRNODE(x, siglen) ( LTG_ISONENODE(x) ? LTG_NODE(x) : LTG_RNODE(x, siglen) )
273 
274 extern ltree_gist *ltree_gist_alloc(bool isalltrue, BITVECP sign, int siglen,
275  ltree *left, ltree *right);
276 
277 /* GiST support for ltree[] */
278 
279 #define LTREE_ASIGLEN_DEFAULT (7 * sizeof(int32))
280 #define LTREE_ASIGLEN_MAX GISTMaxIndexKeySize
281 #define LTREE_GET_ASIGLEN() (PG_HAS_OPCLASS_OPTIONS() ? \
282  ((LtreeGistOptions *) PG_GET_OPCLASS_OPTIONS())->siglen : \
283  LTREE_ASIGLEN_DEFAULT)
284 #define ASIGLENBIT(siglen) ((siglen) * BITBYTE)
285 
286 #define ALOOPBYTE(siglen) \
287  for (i = 0; i < (siglen); i++)
288 
289 #define AHASHVAL(val, siglen) (((unsigned int)(val)) % ASIGLENBIT(siglen))
290 #define AHASH(sign, val, siglen) SETBIT((sign), AHASHVAL(val, siglen))
291 
292 /* gist_ltree_ops and gist__ltree_ops opclass options */
293 typedef struct
294 {
295  int32 vl_len_; /* varlena header (do not touch directly!) */
296  int siglen; /* signature length in bytes */
298 
299 /* type of key is the same to ltree_gist */
300 
301 #endif
uint16 firstgood
Definition: ltree.h:104
signed short int16
Definition: c.h:362
Definition: _int.h:140
int32 vl_len_
Definition: ltree.h:102
Datum _ltxtq_exec(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:178
uint8 flag
Definition: ltree.h:49
Datum _ltxtq_rexec(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:190
Datum _ltree_isparent(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:71
Datum _lt_q_rregex(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:168
int32 vl_len_
Definition: ltree.h:252
uint16 low
Definition: ltree.h:80
int32 size
Definition: ltree.h:142
uint16 len
Definition: ltree.h:48
uint16 len
Definition: ltree.h:22
Datum lt_q_regex(PG_FUNCTION_ARGS)
Definition: lquery_op.c:239
bool inner_isparent(const ltree *c, const ltree *p)
Definition: ltree_op.c:143
Definition: ltree.h:100
uint8 length
Definition: ltree.h:131
Datum ltq_rregex(PG_FUNCTION_ARGS)
Definition: lquery_op.c:230
uint32 flag
Definition: ltree.h:253
Datum ltree_risparent(PG_FUNCTION_ARGS)
Definition: ltree_op.c:179
unsigned char uint8
Definition: c.h:373
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:284
bool compare_subnode(ltree_level *t, char *q, int len, int(*cmpptr)(const char *, const char *, size_t), bool anyend)
Definition: lquery_op.c:44
uint16 flag
Definition: ltree.h:105
uint16 totallen
Definition: ltree.h:77
uint8 flag
Definition: ltree.h:129
int32 vl_len_
Definition: ltree.h:141
int ltree_strncasecmp(const char *a, const char *b, size_t s)
Definition: lquery_op.c:78
Datum ltree_in(PG_FUNCTION_ARGS)
Definition: ltree_io.c:172
Datum _ltq_regex(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:113
signed int int32
Definition: c.h:363
bool ltree_execute(ITEM *curitem, void *checkval, bool calcnot, bool(*chkcond)(void *checkval, ITEM *val))
Definition: ltxtquery_op.c:20
Datum ltree_textadd(PG_FUNCTION_ARGS)
Definition: ltree_op.c:395
int16 type
Definition: _int.h:142
unsigned short uint16
Definition: c.h:374
uint16 flag
Definition: ltree.h:78
ltree * lca_inner(ltree **a, int len)
Definition: ltree_op.c:426
Datum ltq_regex(PG_FUNCTION_ARGS)
Definition: lquery_op.c:215
char sign
Definition: informix.c:668
unsigned char * BITVECP
Definition: ltree.h:225
Datum _lt_q_regex(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:134
char * c
int32 val
Definition: _int.h:144
unsigned int uint32
Definition: c.h:375
ltree_gist * ltree_gist_alloc(bool isalltrue, BITVECP sign, int siglen, ltree *left, ltree *right)
Definition: ltree_gist.c:39
Datum _ltree_risparent(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:92
Definition: ltree.h:29
Datum ltree_isparent(PG_FUNCTION_ARGS)
Definition: ltree_op.c:167
struct ITEM ITEM
uint16 numlevel
Definition: ltree.h:32
uintptr_t Datum
Definition: postgres.h:367
Datum ltree_addltree(PG_FUNCTION_ARGS)
Definition: ltree_op.c:297
int16 left
Definition: _int.h:143
int32 val
Definition: ltree.h:47
uint16 numlevel
Definition: ltree.h:103
Datum ltxtq_exec(PG_FUNCTION_ARGS)
Definition: ltxtquery_op.c:84
uint16 numvar
Definition: ltree.h:79
const char * name
Definition: encode.c:561
Datum _ltq_rregex(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:125
Datum lt_q_rregex(PG_FUNCTION_ARGS)
Definition: lquery_op.c:275
int32 vl_len_
Definition: ltree.h:295
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
int ltree_compare(const ltree *a, const ltree *b)
Definition: ltree_op.c:42
int32 vl_len_
Definition: ltree.h:31
uint16 distance
Definition: ltree.h:132
uint16 high
Definition: ltree.h:81
Datum ltxtq_rexec(PG_FUNCTION_ARGS)
Definition: ltxtquery_op.c:105
Datum ltree_addtext(PG_FUNCTION_ARGS)
Definition: ltree_op.c:310