PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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
33typedef struct
34{
35 uint16 len; /* label string length in bytes */
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
42typedef 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 */
58typedef 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 */
88typedef 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];
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
113typedef 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 */
138typedef 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 */
153typedef 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
205bool ltree_execute(ITEM *curitem, void *checkval,
206 bool calcnot, bool (*chkcond) (void *checkval, ITEM *val));
207
208int ltree_compare(const ltree *a, const ltree *b);
209bool inner_isparent(const ltree *c, const ltree *p);
210bool compare_subnode(ltree_level *t, char *qn, int len,
211 int (*cmpptr) (const char *, const char *, size_t), bool anyend);
212ltree *lca_inner(ltree **a, int len);
213int 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
241typedef 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
266typedef 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
290extern 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 */
309typedef 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
uint8_t uint8
Definition: c.h:486
#define PGDLLEXPORT
Definition: c.h:1292
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:420
int16_t int16
Definition: c.h:483
int32_t int32
Definition: c.h:484
uint16_t uint16
Definition: c.h:487
uint32_t uint32
Definition: c.h:488
#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
ltree * lca_inner(ltree **a, int len)
Definition: ltree_op.c:493
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
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
PGDLLEXPORT Datum _lt_q_rregex(PG_FUNCTION_ARGS)
Definition: _ltree_op.c:169
ltree_gist * ltree_gist_alloc(bool isalltrue, BITVECP sign, int siglen, ltree *left, ltree *right)
Definition: ltree_gist.c:42
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:69
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