contrib/ltree/ltree.h

   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 */
  36         char            name[FLEXIBLE_ARRAY_MEMBER];
  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: */
  47         char            data[FLEXIBLE_ARRAY_MEMBER];
  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 */
  63         char            name[FLEXIBLE_ARRAY_MEMBER];
  64 } lquery_variant;
  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: */
 120         char            data[FLEXIBLE_ARRAY_MEMBER];
 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;
 143         uint8           flag;
 144         /* user-friendly value */
 145         uint8           length;
 146         uint16          distance;
 147 } ITEM;
 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!) */
 156         int32           size;
 157         char            data[FLEXIBLE_ARRAY_MEMBER];
 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 */
 180 PGDLLEXPORT Datum ltree_isparent(PG_FUNCTION_ARGS);
 181 PGDLLEXPORT Datum ltree_risparent(PG_FUNCTION_ARGS);
 182 PGDLLEXPORT Datum ltq_regex(PG_FUNCTION_ARGS);
 183 PGDLLEXPORT Datum ltq_rregex(PG_FUNCTION_ARGS);
 184 PGDLLEXPORT Datum lt_q_regex(PG_FUNCTION_ARGS);
 185 PGDLLEXPORT Datum lt_q_rregex(PG_FUNCTION_ARGS);
 186 PGDLLEXPORT Datum ltxtq_exec(PG_FUNCTION_ARGS);
 187 PGDLLEXPORT Datum ltxtq_rexec(PG_FUNCTION_ARGS);
 188 PGDLLEXPORT Datum _ltq_regex(PG_FUNCTION_ARGS);
 189 PGDLLEXPORT Datum _ltq_rregex(PG_FUNCTION_ARGS);
 190 PGDLLEXPORT Datum _lt_q_regex(PG_FUNCTION_ARGS);
 191 PGDLLEXPORT Datum _lt_q_rregex(PG_FUNCTION_ARGS);
 192 PGDLLEXPORT Datum _ltxtq_exec(PG_FUNCTION_ARGS);
 193 PGDLLEXPORT Datum _ltxtq_rexec(PG_FUNCTION_ARGS);
 194 PGDLLEXPORT Datum _ltree_isparent(PG_FUNCTION_ARGS);
 195 PGDLLEXPORT Datum _ltree_risparent(PG_FUNCTION_ARGS);
 196
 197 /* Concatenation functions */
 198 PGDLLEXPORT Datum ltree_addltree(PG_FUNCTION_ARGS);
 199 PGDLLEXPORT Datum ltree_addtext(PG_FUNCTION_ARGS);
 200 PGDLLEXPORT Datum ltree_textadd(PG_FUNCTION_ARGS);
 201
 202 /* Util function */
 203 PGDLLEXPORT Datum ltree_in(PG_FUNCTION_ARGS);
 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!) */
 269         uint32          flag;
 270         char            data[FLEXIBLE_ARRAY_MEMBER];
 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 */
 313 } LtreeGistOptions;
 314
 315 /* type of key is the same to ltree_gist */
 316
 317 #endif