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