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 1000 characters (not bytes), while using
16  * uint16 fields to hold the byte length.
17  */
18 #define LTREE_LABEL_MAX_CHARS 1000
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_upgrade.
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 /* valid label chars are alphanumerics, underscores and hyphens */
130 #define ISLABEL(x) ( t_isalnum(x) || t_iseq(x, '_') || t_iseq(x, '-') )
131 
132 /* full text query */
133 
134 /*
135  * item in polish notation with back link
136  * to left operand
137  */
138 typedef struct ITEM
139 {
140  int16 type;
141  int16 left;
142  int32 val;
144  /* user-friendly value */
148 
149 /*
150  *Storage:
151  * (len)(size)(array of ITEM)(array of operand in user-friendly form)
152  */
153 typedef struct
154 {
155  int32 vl_len_; /* varlena header (do not touch directly!) */
158 } ltxtquery;
159 
160 #define HDRSIZEQT MAXALIGN(VARHDRSZ + sizeof(int32))
161 #define COMPUTESIZE(size,lenofoperand) ( HDRSIZEQT + (size) * sizeof(ITEM) + (lenofoperand) )
162 #define LTXTQUERY_TOO_BIG(size,lenofoperand) \
163  ((size) > (MaxAllocSize - HDRSIZEQT - (lenofoperand)) / sizeof(ITEM))
164 #define GETQUERY(x) (ITEM*)( (char*)(x)+HDRSIZEQT )
165 #define GETOPERAND(x) ( (char*)GETQUERY(x) + ((ltxtquery*)x)->size * sizeof(ITEM) )
166 
167 #define ISOPERATOR(x) ( (x)=='!' || (x)=='&' || (x)=='|' || (x)=='(' || (x)==')' )
168 
169 #define END 0
170 #define ERR 1
171 #define VAL 2
172 #define OPR 3
173 #define OPEN 4
174 #define CLOSE 5
175 #define VALTRUE 6 /* for stop words */
176 #define VALFALSE 7
177 
178 
179 /* use in array iterator */
196 
197 /* Concatenation functions */
201 
202 /* Util function */
204 
205 bool ltree_execute(ITEM *curitem, void *checkval,
206  bool calcnot, bool (*chkcond) (void *checkval, ITEM *val));
207 
208 int ltree_compare(const ltree *a, const ltree *b);
209 bool inner_isparent(const ltree *c, const ltree *p);
210 bool compare_subnode(ltree_level *t, char *qn, int len,
211  int (*cmpptr) (const char *, const char *, size_t), bool anyend);
212 ltree *lca_inner(ltree **a, int len);
213 int ltree_strncasecmp(const char *a, const char *b, size_t s);
214 
215 /* fmgr macros for ltree objects */
216 #define DatumGetLtreeP(X) ((ltree *) PG_DETOAST_DATUM(X))
217 #define DatumGetLtreePCopy(X) ((ltree *) PG_DETOAST_DATUM_COPY(X))
218 #define PG_GETARG_LTREE_P(n) DatumGetLtreeP(PG_GETARG_DATUM(n))
219 #define PG_GETARG_LTREE_P_COPY(n) DatumGetLtreePCopy(PG_GETARG_DATUM(n))
220 
221 #define DatumGetLqueryP(X) ((lquery *) PG_DETOAST_DATUM(X))
222 #define DatumGetLqueryPCopy(X) ((lquery *) PG_DETOAST_DATUM_COPY(X))
223 #define PG_GETARG_LQUERY_P(n) DatumGetLqueryP(PG_GETARG_DATUM(n))
224 #define PG_GETARG_LQUERY_P_COPY(n) DatumGetLqueryPCopy(PG_GETARG_DATUM(n))
225 
226 #define DatumGetLtxtqueryP(X) ((ltxtquery *) PG_DETOAST_DATUM(X))
227 #define DatumGetLtxtqueryPCopy(X) ((ltxtquery *) PG_DETOAST_DATUM_COPY(X))
228 #define PG_GETARG_LTXTQUERY_P(n) DatumGetLtxtqueryP(PG_GETARG_DATUM(n))
229 #define PG_GETARG_LTXTQUERY_P_COPY(n) DatumGetLtxtqueryPCopy(PG_GETARG_DATUM(n))
230 
231 /* GiST support for ltree */
232 
233 #define BITBYTE 8
234 #define SIGLENBIT(siglen) ((siglen) * BITBYTE)
235 #define LTREE_SIGLEN_DEFAULT (2 * sizeof(int32))
236 #define LTREE_SIGLEN_MAX GISTMaxIndexKeySize
237 #define LTREE_GET_SIGLEN() (PG_HAS_OPCLASS_OPTIONS() ? \
238  ((LtreeGistOptions *) PG_GET_OPCLASS_OPTIONS())->siglen : \
239  LTREE_SIGLEN_DEFAULT)
240 
241 typedef unsigned char *BITVECP;
242 
243 #define LOOPBYTE(siglen) \
244  for(i = 0; i < (siglen); i++)
245 
246 #define GETBYTE(x,i) ( *( (BITVECP)(x) + (int)( (i) / BITBYTE ) ) )
247 #define GETBITBYTE(x,i) ( ((unsigned char)(x)) >> i & 0x01 )
248 #define CLRBIT(x,i) GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITBYTE ) )
249 #define SETBIT(x,i) GETBYTE(x,i) |= ( 0x01 << ( (i) % BITBYTE ) )
250 #define GETBIT(x,i) ( (GETBYTE(x,i) >> ( (i) % BITBYTE )) & 0x01 )
251 
252 #define HASHVAL(val, siglen) (((unsigned int)(val)) % SIGLENBIT(siglen))
253 #define HASH(sign, val, siglen) SETBIT((sign), HASHVAL(val, siglen))
254 
255 /*
256  * type of index key for ltree. Tree are combined B-Tree and R-Tree
257  * Storage:
258  * Leaf pages
259  * (len)(flag)(ltree)
260  * Non-Leaf
261  * (len)(flag)(sign)(left_ltree)(right_ltree)
262  * ALLTRUE: (len)(flag)(left_ltree)(right_ltree)
263  *
264  */
265 
266 typedef struct
267 {
268  int32 vl_len_; /* varlena header (do not touch directly!) */
271 } ltree_gist;
272 
273 #define LTG_ONENODE 0x01
274 #define LTG_ALLTRUE 0x02
275 #define LTG_NORIGHT 0x04
276 
277 #define LTG_HDRSIZE MAXALIGN(VARHDRSZ + sizeof(uint32))
278 #define LTG_SIGN(x) ( (BITVECP)( ((char*)(x))+LTG_HDRSIZE ) )
279 #define LTG_NODE(x) ( (ltree*)( ((char*)(x))+LTG_HDRSIZE ) )
280 #define LTG_ISONENODE(x) ( ((ltree_gist*)(x))->flag & LTG_ONENODE )
281 #define LTG_ISALLTRUE(x) ( ((ltree_gist*)(x))->flag & LTG_ALLTRUE )
282 #define LTG_ISNORIGHT(x) ( ((ltree_gist*)(x))->flag & LTG_NORIGHT )
283 #define LTG_LNODE(x, siglen) ( (ltree*)( ( ((char*)(x))+LTG_HDRSIZE ) + ( LTG_ISALLTRUE(x) ? 0 : (siglen) ) ) )
284 #define LTG_RENODE(x, siglen) ( (ltree*)( ((char*)LTG_LNODE(x, siglen)) + VARSIZE(LTG_LNODE(x, siglen))) )
285 #define LTG_RNODE(x, siglen) ( LTG_ISNORIGHT(x) ? LTG_LNODE(x, siglen) : LTG_RENODE(x, siglen) )
286 
287 #define LTG_GETLNODE(x, siglen) ( LTG_ISONENODE(x) ? LTG_NODE(x) : LTG_LNODE(x, siglen) )
288 #define LTG_GETRNODE(x, siglen) ( LTG_ISONENODE(x) ? LTG_NODE(x) : LTG_RNODE(x, siglen) )
289 
290 extern ltree_gist *ltree_gist_alloc(bool isalltrue, BITVECP sign, int siglen,
291  ltree *left, ltree *right);
292 
293 /* GiST support for ltree[] */
294 
295 #define LTREE_ASIGLEN_DEFAULT (7 * sizeof(int32))
296 #define LTREE_ASIGLEN_MAX GISTMaxIndexKeySize
297 #define LTREE_GET_ASIGLEN() (PG_HAS_OPCLASS_OPTIONS() ? \
298  ((LtreeGistOptions *) PG_GET_OPCLASS_OPTIONS())->siglen : \
299  LTREE_ASIGLEN_DEFAULT)
300 #define ASIGLENBIT(siglen) ((siglen) * BITBYTE)
301 
302 #define ALOOPBYTE(siglen) \
303  for (i = 0; i < (siglen); i++)
304 
305 #define AHASHVAL(val, siglen) (((unsigned int)(val)) % ASIGLENBIT(siglen))
306 #define AHASH(sign, val, siglen) SETBIT((sign), AHASHVAL(val, siglen))
307 
308 /* gist_ltree_ops and gist__ltree_ops opclass options */
309 typedef struct
310 {
311  int32 vl_len_; /* varlena header (do not touch directly!) */
312  int siglen; /* signature length in bytes */
314 
315 /* type of key is the same to ltree_gist */
316 
317 #endif
unsigned short uint16
Definition: c.h:491
unsigned int uint32
Definition: c.h:492
signed short int16
Definition: c.h:481
signed int int32
Definition: c.h:482
#define PGDLLEXPORT
Definition: c.h:1310
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:413
unsigned char uint8
Definition: c.h:490
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
char * BITVECP
Definition: hstore_gist.c:31
long val
Definition: informix.c:689
char sign
Definition: informix.c:693
int b
Definition: isn.c:69
int a
Definition: isn.c:68
bool inner_isparent(const ltree *c, const ltree *p)
Definition: ltree_op.c:210
PGDLLEXPORT Datum ltree_addtext(PG_FUNCTION_ARGS)
Definition: ltree_op.c:377
PGDLLEXPORT Datum ltree_addltree(PG_FUNCTION_ARGS)
Definition: ltree_op.c:364
PGDLLEXPORT Datum ltxtq_exec(PG_FUNCTION_ARGS)
Definition: ltxtquery_op.c:84
PGDLLEXPORT Datum ltxtq_rexec(PG_FUNCTION_ARGS)
Definition: ltxtquery_op.c:105
PGDLLEXPORT Datum ltq_rregex(PG_FUNCTION_ARGS)
Definition: lquery_op.c:230
struct ITEM ITEM
int ltree_compare(const ltree *a, const ltree *b)
Definition: ltree_op.c:43
PGDLLEXPORT Datum _ltq_rregex(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:126
bool compare_subnode(ltree_level *t, char *qn, int len, int(*cmpptr)(const char *, const char *, size_t), bool anyend)
Definition: lquery_op.c:44
PGDLLEXPORT Datum _ltree_isparent(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:72
ltree_gist * ltree_gist_alloc(bool isalltrue, BITVECP sign, int siglen, ltree *left, ltree *right)
Definition: ltree_gist.c:42
PGDLLEXPORT Datum lt_q_rregex(PG_FUNCTION_ARGS)
Definition: lquery_op.c:275
PGDLLEXPORT Datum ltree_risparent(PG_FUNCTION_ARGS)
Definition: ltree_op.c:246
PGDLLEXPORT Datum ltree_isparent(PG_FUNCTION_ARGS)
Definition: ltree_op.c:234
PGDLLEXPORT Datum ltq_regex(PG_FUNCTION_ARGS)
Definition: lquery_op.c:215
PGDLLEXPORT Datum ltree_textadd(PG_FUNCTION_ARGS)
Definition: ltree_op.c:462
PGDLLEXPORT Datum _ltree_risparent(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:93
int ltree_strncasecmp(const char *a, const char *b, size_t s)
Definition: lquery_op.c:78
PGDLLEXPORT Datum lt_q_regex(PG_FUNCTION_ARGS)
Definition: lquery_op.c:239
bool ltree_execute(ITEM *curitem, void *checkval, bool calcnot, bool(*chkcond)(void *checkval, ITEM *val))
Definition: ltxtquery_op.c:20
unsigned char * BITVECP
Definition: ltree.h:241
PGDLLEXPORT Datum _lt_q_regex(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:135
PGDLLEXPORT Datum _ltq_regex(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:114
PGDLLEXPORT Datum _ltxtq_exec(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:179
PGDLLEXPORT Datum _ltxtq_rexec(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:191
ltree * lca_inner(ltree **a, int len)
Definition: ltree_op.c:493
PGDLLEXPORT Datum _lt_q_rregex(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:169
PGDLLEXPORT Datum ltree_in(PG_FUNCTION_ARGS)
Definition: ltree_io.c:174
const void size_t len
const void * data
uintptr_t Datum
Definition: postgres.h:64
char * c
Definition: _int.h:141
uint16 distance
Definition: ltree.h:146
int16 left
Definition: _int.h:143
uint8 flag
Definition: ltree.h:143
int32 val
Definition: _int.h:144
int16 type
Definition: _int.h:142
uint8 length
Definition: ltree.h:145
int32 vl_len_
Definition: ltree.h:311
uint16 numvar
Definition: ltree.h:92
uint16 high
Definition: ltree.h:94
uint16 flag
Definition: ltree.h:91
uint16 low
Definition: ltree.h:93
uint16 totallen
Definition: ltree.h:90
uint8 flag
Definition: ltree.h:62
int32 val
Definition: ltree.h:60
uint16 len
Definition: ltree.h:61
Definition: ltree.h:114
int32 vl_len_
Definition: ltree.h:115
uint16 firstgood
Definition: ltree.h:117
uint16 numlevel
Definition: ltree.h:116
uint16 flag
Definition: ltree.h:118
uint32 flag
Definition: ltree.h:269
int32 vl_len_
Definition: ltree.h:268
uint16 len
Definition: ltree.h:35
Definition: ltree.h:43
int32 vl_len_
Definition: ltree.h:44
uint16 numlevel
Definition: ltree.h:45
int32 vl_len_
Definition: ltree.h:155
int32 size
Definition: ltree.h:156
const char * name