Age Owner TLA Line data Source code
1 : /*
2 : * GiST support for ltree
3 : * Teodor Sigaev <teodor@stack.net>
4 : * contrib/ltree/ltree_gist.c
5 : */
6 : #include "postgres.h"
7 :
8 : #include "access/gist.h"
9 : #include "access/reloptions.h"
10 : #include "access/stratnum.h"
11 : #include "crc32.h"
12 : #include "ltree.h"
13 : #include "utils/array.h"
14 :
15 : #define NEXTVAL(x) ( (lquery*)( (char*)(x) + INTALIGN( VARSIZE(x) ) ) )
16 : #define ISEQ(a,b) ( (a)->numlevel == (b)->numlevel && ltree_compare(a,b)==0 )
17 :
7522 bruce 18 GIC 2 : PG_FUNCTION_INFO_V1(ltree_gist_in);
7522 bruce 19 CBC 2 : PG_FUNCTION_INFO_V1(ltree_gist_out);
7558 bruce 20 ECB :
21 : Datum
7522 bruce 22 UIC 0 : ltree_gist_in(PG_FUNCTION_ARGS)
7522 bruce 23 EUB : {
7199 tgl 24 UIC 0 : ereport(ERROR,
7199 tgl 25 EUB : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
26 : errmsg("cannot accept a value of type %s", "ltree_gist")));
27 :
28 : PG_RETURN_VOID(); /* keep compiler quiet */
29 : }
30 :
31 : Datum
7522 bruce 32 UIC 0 : ltree_gist_out(PG_FUNCTION_ARGS)
33 : {
7199 tgl 34 UBC 0 : ereport(ERROR,
35 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
36 : errmsg("cannot display a value of type %s", "ltree_gist")));
37 :
38 : PG_RETURN_VOID(); /* keep compiler quiet */
39 : }
40 :
41 : ltree_gist *
1105 akorotkov 42 GIC 17171 : ltree_gist_alloc(bool isalltrue, BITVECP sign, int siglen,
43 : ltree *left, ltree *right)
44 : {
1105 akorotkov 45 CBC 22448 : int32 size = LTG_HDRSIZE + (isalltrue ? 0 : siglen) +
1060 tgl 46 GIC 5277 : (left ? VARSIZE(left) + (right ? VARSIZE(right) : 0) : 0);
1105 akorotkov 47 17171 : ltree_gist *result = palloc(size);
1105 akorotkov 48 ECB :
1105 akorotkov 49 CBC 17171 : SET_VARSIZE(result, size);
1105 akorotkov 50 ECB :
1105 akorotkov 51 GIC 17171 : if (siglen)
1105 akorotkov 52 ECB : {
1105 akorotkov 53 GIC 15159 : result->flag = 0;
1105 akorotkov 54 ECB :
1105 akorotkov 55 GIC 15159 : if (isalltrue)
1105 akorotkov 56 LBC 0 : result->flag |= LTG_ALLTRUE;
1105 akorotkov 57 GIC 15159 : else if (sign)
1105 akorotkov 58 CBC 5135 : memcpy(LTG_SIGN(result), sign, siglen);
1105 akorotkov 59 EUB : else
1105 akorotkov 60 CBC 10024 : memset(LTG_SIGN(result), 0, siglen);
1105 akorotkov 61 ECB :
1105 akorotkov 62 GIC 15159 : if (left)
1105 akorotkov 63 ECB : {
1105 akorotkov 64 GIC 3265 : memcpy(LTG_LNODE(result, siglen), left, VARSIZE(left));
1105 akorotkov 65 ECB :
1105 akorotkov 66 GIC 3265 : if (!right || left == right || ISEQ(left, right))
1105 akorotkov 67 LBC 0 : result->flag |= LTG_NORIGHT;
68 : else
1105 akorotkov 69 CBC 3265 : memcpy(LTG_RNODE(result, siglen), right, VARSIZE(right));
1105 akorotkov 70 EUB : }
71 : }
1105 akorotkov 72 ECB : else
73 : {
1105 akorotkov 74 GIC 2012 : Assert(left);
75 2012 : result->flag = LTG_ONENODE;
76 2012 : memcpy(LTG_NODE(result), left, VARSIZE(left));
1105 akorotkov 77 ECB : }
78 :
1105 akorotkov 79 CBC 17171 : return result;
80 : }
81 :
7522 bruce 82 3 : PG_FUNCTION_INFO_V1(ltree_compress);
7522 bruce 83 GIC 3 : PG_FUNCTION_INFO_V1(ltree_decompress);
84 3 : PG_FUNCTION_INFO_V1(ltree_same);
7522 bruce 85 CBC 3 : PG_FUNCTION_INFO_V1(ltree_union);
86 3 : PG_FUNCTION_INFO_V1(ltree_penalty);
87 3 : PG_FUNCTION_INFO_V1(ltree_picksplit);
88 3 : PG_FUNCTION_INFO_V1(ltree_consistent);
1105 akorotkov 89 3 : PG_FUNCTION_INFO_V1(ltree_gist_options);
7558 bruce 90 ECB :
6949 teodor 91 : #define GETENTRY(vec,pos) ((ltree_gist *) DatumGetPointer((vec)->vector[(pos)].key))
7558 bruce 92 :
93 : Datum
7522 bruce 94 GIC 2097 : ltree_compress(PG_FUNCTION_ARGS)
95 : {
96 2097 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
7558 bruce 97 CBC 2097 : GISTENTRY *retval = entry;
98 :
7522 99 2097 : if (entry->leafkey)
7522 bruce 100 ECB : { /* ltree */
2029 tgl 101 GIC 2012 : ltree *val = DatumGetLtreeP(entry->key);
1105 akorotkov 102 CBC 2012 : ltree_gist *key = ltree_gist_alloc(false, NULL, 0, val, 0);
103 :
7522 bruce 104 2012 : retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
7558 105 2012 : gistentryinit(*retval, PointerGetDatum(key),
106 : entry->rel, entry->page,
2062 peter_e 107 ECB : entry->offset, false);
7558 bruce 108 : }
7558 bruce 109 GIC 2097 : PG_RETURN_POINTER(retval);
110 : }
111 :
7522 bruce 112 ECB : Datum
7522 bruce 113 GIC 101442 : ltree_decompress(PG_FUNCTION_ARGS)
114 : {
115 101442 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
2029 tgl 116 CBC 101442 : ltree_gist *key = (ltree_gist *) PG_DETOAST_DATUM(entry->key);
117 :
7522 bruce 118 101442 : if (PointerGetDatum(key) != entry->key)
7522 bruce 119 ECB : {
7522 bruce 120 UIC 0 : GISTENTRY *retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
7558 bruce 121 ECB :
7558 bruce 122 UIC 0 : gistentryinit(*retval, PointerGetDatum(key),
7522 bruce 123 EUB : entry->rel, entry->page,
124 : entry->offset, false);
7558 bruce 125 UBC 0 : PG_RETURN_POINTER(retval);
126 : }
7522 bruce 127 GIC 101442 : PG_RETURN_POINTER(entry);
7558 bruce 128 EUB : }
129 :
7522 bruce 130 ECB : Datum
7522 bruce 131 GIC 3199 : ltree_same(PG_FUNCTION_ARGS)
132 : {
133 3199 : ltree_gist *a = (ltree_gist *) PG_GETARG_POINTER(0);
7522 bruce 134 CBC 3199 : ltree_gist *b = (ltree_gist *) PG_GETARG_POINTER(1);
7522 bruce 135 GIC 3199 : bool *result = (bool *) PG_GETARG_POINTER(2);
389 akorotkov 136 CBC 3199 : int siglen = LTREE_GET_SIGLEN();
7558 bruce 137 ECB :
7558 bruce 138 CBC 3199 : *result = false;
7522 139 3199 : if (LTG_ISONENODE(a) != LTG_ISONENODE(b))
7522 bruce 140 UIC 0 : PG_RETURN_POINTER(result);
7522 bruce 141 ECB :
7522 bruce 142 CBC 3199 : if (LTG_ISONENODE(a))
578 michael 143 UBC 0 : *result = ISEQ(LTG_NODE(a), LTG_NODE(b));
144 : else
7522 bruce 145 ECB : {
3940 peter_e 146 EUB : int32 i;
7522 bruce 147 GIC 3199 : BITVECP sa = LTG_SIGN(a),
148 3199 : sb = LTG_SIGN(b);
149 :
7522 bruce 150 CBC 3199 : if (LTG_ISALLTRUE(a) != LTG_ISALLTRUE(b))
7522 bruce 151 LBC 0 : PG_RETURN_POINTER(result);
152 :
1105 akorotkov 153 CBC 3199 : if (!ISEQ(LTG_LNODE(a, siglen), LTG_LNODE(b, siglen)))
7522 bruce 154 GBC 9 : PG_RETURN_POINTER(result);
1105 akorotkov 155 GIC 3190 : if (!ISEQ(LTG_RNODE(a, siglen), LTG_RNODE(b, siglen)))
7558 bruce 156 CBC 8 : PG_RETURN_POINTER(result);
7558 bruce 157 ECB :
7558 bruce 158 CBC 3182 : *result = true;
7522 159 3182 : if (!LTG_ISALLTRUE(a))
160 : {
1105 akorotkov 161 4618882 : LOOPBYTE(siglen)
5623 bruce 162 ECB : {
5623 bruce 163 GIC 4615702 : if (sa[i] != sb[i])
5623 bruce 164 ECB : {
5623 bruce 165 GIC 2 : *result = false;
5623 bruce 166 CBC 2 : break;
167 : }
7522 bruce 168 ECB : }
5623 169 : }
170 : }
171 :
7522 bruce 172 GIC 3182 : PG_RETURN_POINTER(result);
173 : }
174 :
7558 bruce 175 ECB : static void
1105 akorotkov 176 GIC 5686 : hashing(BITVECP sign, ltree *t, int siglen)
177 : {
7522 bruce 178 5686 : int tlen = t->numlevel;
7558 bruce 179 CBC 5686 : ltree_level *cur = LTREE_FIRST(t);
180 : int hash;
7558 bruce 181 ECB :
7522 bruce 182 CBC 42954 : while (tlen > 0)
183 : {
7522 bruce 184 GIC 37268 : hash = ltree_crc32_sz(cur->name, cur->len);
1105 akorotkov 185 CBC 37268 : HASH(sign, hash, siglen);
7558 bruce 186 GIC 37268 : cur = LEVEL_NEXT(cur);
7558 bruce 187 CBC 37268 : tlen--;
7558 bruce 188 ECB : }
7558 bruce 189 CBC 5686 : }
7558 bruce 190 ECB :
191 : Datum
7522 bruce 192 CBC 3199 : ltree_union(PG_FUNCTION_ARGS)
193 : {
6797 bruce 194 GIC 3199 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
7522 bruce 195 CBC 3199 : int *size = (int *) PG_GETARG_POINTER(1);
389 akorotkov 196 GIC 3199 : int siglen = LTREE_GET_SIGLEN();
1105 akorotkov 197 CBC 3199 : BITVECP base = palloc0(siglen);
3940 peter_e 198 ECB : int32 i,
7522 bruce 199 : j;
200 : ltree_gist *result,
201 : *cur;
7522 bruce 202 GIC 3199 : ltree *left = NULL,
203 3199 : *right = NULL,
204 : *curtree;
7522 bruce 205 CBC 3199 : bool isalltrue = false;
7522 bruce 206 ECB :
6949 teodor 207 GIC 9597 : for (j = 0; j < entryvec->n; j++)
7522 bruce 208 ECB : {
7558 bruce 209 GIC 6398 : cur = GETENTRY(entryvec, j);
7522 bruce 210 CBC 6398 : if (LTG_ISONENODE(cur))
211 : {
7558 212 3199 : curtree = LTG_NODE(cur);
1105 akorotkov 213 3199 : hashing(base, curtree, siglen);
7522 bruce 214 GIC 3199 : if (!left || ltree_compare(left, curtree) > 0)
7522 bruce 215 CBC 9 : left = curtree;
216 3199 : if (!right || ltree_compare(right, curtree) < 0)
7558 217 8 : right = curtree;
7522 bruce 218 ECB : }
219 : else
220 : {
7522 bruce 221 GIC 3199 : if (isalltrue || LTG_ISALLTRUE(cur))
7558 bruce 222 UIC 0 : isalltrue = true;
223 : else
7522 bruce 224 ECB : {
7522 bruce 225 GBC 3199 : BITVECP sc = LTG_SIGN(cur);
226 :
1105 akorotkov 227 GIC 4641399 : LOOPBYTE(siglen)
5623 bruce 228 CBC 4638200 : ((unsigned char *) base)[i] |= sc[i];
229 : }
7558 bruce 230 ECB :
1105 akorotkov 231 CBC 3199 : curtree = LTG_LNODE(cur, siglen);
7522 bruce 232 GIC 3199 : if (!left || ltree_compare(left, curtree) > 0)
233 3199 : left = curtree;
1105 akorotkov 234 CBC 3199 : curtree = LTG_RNODE(cur, siglen);
7522 bruce 235 3199 : if (!right || ltree_compare(right, curtree) < 0)
7558 236 3199 : right = curtree;
7522 bruce 237 ECB : }
7558 238 : }
7522 239 :
7522 bruce 240 GIC 3199 : if (isalltrue == false)
241 : {
7558 242 3199 : isalltrue = true;
1105 akorotkov 243 CBC 3199 : LOOPBYTE(siglen)
244 : {
5623 bruce 245 3199 : if (((unsigned char *) base)[i] != 0xff)
5623 bruce 246 ECB : {
5623 bruce 247 GIC 3199 : isalltrue = false;
5623 bruce 248 CBC 3199 : break;
249 : }
7522 bruce 250 ECB : }
7558 251 : }
252 :
1105 akorotkov 253 GIC 3199 : result = ltree_gist_alloc(isalltrue, base, siglen, left, right);
254 :
255 3199 : *size = VARSIZE(result);
7558 bruce 256 ECB :
7522 bruce 257 GIC 3199 : PG_RETURN_POINTER(result);
7558 bruce 258 ECB : }
259 :
7522 260 : Datum
7522 bruce 261 GIC 9860 : ltree_penalty(PG_FUNCTION_ARGS)
262 : {
263 9860 : ltree_gist *origval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(0))->key);
7522 bruce 264 CBC 9860 : ltree_gist *newval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(1))->key);
7522 bruce 265 GIC 9860 : float *penalty = (float *) PG_GETARG_POINTER(2);
389 akorotkov 266 CBC 9860 : int siglen = LTREE_GET_SIGLEN();
3940 peter_e 267 ECB : int32 cmpr,
7522 bruce 268 : cmpl;
7558 269 :
1105 akorotkov 270 GIC 9860 : cmpl = ltree_compare(LTG_GETLNODE(origval, siglen), LTG_GETLNODE(newval, siglen));
271 9860 : cmpr = ltree_compare(LTG_GETRNODE(newval, siglen), LTG_GETRNODE(origval, siglen));
272 :
6744 tgl 273 CBC 9860 : *penalty = Max(cmpl, 0) + Max(cmpr, 0);
7558 bruce 274 ECB :
7558 bruce 275 GIC 9860 : PG_RETURN_POINTER(penalty);
7558 bruce 276 ECB : }
277 :
278 : /* used for sorting */
279 : typedef struct rix
280 : {
281 : int index;
282 : ltree *r;
283 : } RIX;
284 :
285 : static int
7522 bruce 286 GIC 17603 : treekey_cmp(const void *a, const void *b)
287 : {
1165 alvherre 288 35206 : return ltree_compare(((const RIX *) a)->r,
1165 alvherre 289 CBC 17603 : ((const RIX *) b)->r);
290 : }
7558 bruce 291 ECB :
292 :
293 : Datum
7522 bruce 294 GIC 33 : ltree_picksplit(PG_FUNCTION_ARGS)
295 : {
6797 296 33 : GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
7522 bruce 297 CBC 33 : GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
389 akorotkov 298 GIC 33 : int siglen = LTREE_GET_SIGLEN();
7558 bruce 299 ECB : OffsetNumber j;
3940 peter_e 300 : int32 i;
7522 bruce 301 : RIX *array;
302 : OffsetNumber maxoff;
303 : int nbytes;
304 : ltree *lu_l,
305 : *lu_r,
306 : *ru_l,
307 : *ru_r;
308 : ltree_gist *lu,
309 : *ru;
1105 akorotkov 310 GIC 33 : BITVECP ls = palloc0(siglen),
311 33 : rs = palloc0(siglen);
7522 bruce 312 33 : bool lisat = false,
1105 akorotkov 313 CBC 33 : risat = false;
7522 bruce 314 ECB :
6949 teodor 315 CBC 33 : maxoff = entryvec->n - 1;
7558 bruce 316 33 : nbytes = (maxoff + 2) * sizeof(OffsetNumber);
7558 bruce 317 GIC 33 : v->spl_left = (OffsetNumber *) palloc(nbytes);
7558 bruce 318 CBC 33 : v->spl_right = (OffsetNumber *) palloc(nbytes);
319 33 : v->spl_nleft = 0;
320 33 : v->spl_nright = 0;
321 33 : array = (RIX *) palloc(sizeof(RIX) * (maxoff + 1));
7522 bruce 322 ECB :
7558 323 : /* copy the data into RIXes, and sort the RIXes */
7522 bruce 324 CBC 2544 : for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
325 : {
7558 bruce 326 GIC 2511 : array[j].index = j;
2118 tgl 327 CBC 2511 : lu = GETENTRY(entryvec, j); /* use as tmp val */
1105 akorotkov 328 GIC 2511 : array[j].r = LTG_GETLNODE(lu, siglen);
7558 bruce 329 ECB : }
330 :
61 peter 331 GNC 33 : qsort(&array[FirstOffsetNumber], maxoff - FirstOffsetNumber + 1,
332 : sizeof(RIX), treekey_cmp);
333 :
7558 bruce 334 CBC 33 : lu_l = lu_r = ru_l = ru_r = NULL;
7522 bruce 335 GIC 2544 : for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
336 : {
2118 tgl 337 CBC 2511 : lu = GETENTRY(entryvec, array[j].index); /* use as tmp val */
7522 bruce 338 2511 : if (j <= (maxoff - FirstOffsetNumber + 1) / 2)
339 : {
7558 340 1249 : v->spl_left[v->spl_nleft] = array[j].index;
341 1249 : v->spl_nleft++;
1105 akorotkov 342 GIC 1249 : if (lu_r == NULL || ltree_compare(LTG_GETRNODE(lu, siglen), lu_r) > 0)
1105 akorotkov 343 CBC 1248 : lu_r = LTG_GETRNODE(lu, siglen);
7522 bruce 344 1249 : if (LTG_ISONENODE(lu))
1105 akorotkov 345 1237 : hashing(ls, LTG_NODE(lu), siglen);
7522 bruce 346 ECB : else
347 : {
7522 bruce 348 CBC 12 : if (lisat || LTG_ISALLTRUE(lu))
7558 bruce 349 UIC 0 : lisat = true;
350 : else
7522 bruce 351 ECB : {
7522 bruce 352 GBC 12 : BITVECP sc = LTG_SIGN(lu);
353 :
1105 akorotkov 354 GIC 24300 : LOOPBYTE(siglen)
5623 bruce 355 CBC 24288 : ((unsigned char *) ls)[i] |= sc[i];
356 : }
7558 bruce 357 ECB : }
7522 358 : }
359 : else
360 : {
7558 bruce 361 GIC 1262 : v->spl_right[v->spl_nright] = array[j].index;
362 1262 : v->spl_nright++;
1105 akorotkov 363 1262 : if (ru_r == NULL || ltree_compare(LTG_GETRNODE(lu, siglen), ru_r) > 0)
1105 akorotkov 364 CBC 1261 : ru_r = LTG_GETRNODE(lu, siglen);
7522 bruce 365 1262 : if (LTG_ISONENODE(lu))
1105 akorotkov 366 1250 : hashing(rs, LTG_NODE(lu), siglen);
7522 bruce 367 ECB : else
368 : {
7522 bruce 369 CBC 12 : if (risat || LTG_ISALLTRUE(lu))
7558 bruce 370 UIC 0 : risat = true;
371 : else
7522 bruce 372 ECB : {
7522 bruce 373 GBC 12 : BITVECP sc = LTG_SIGN(lu);
374 :
1105 akorotkov 375 GIC 24300 : LOOPBYTE(siglen)
5623 bruce 376 CBC 24288 : ((unsigned char *) rs)[i] |= sc[i];
377 : }
7558 bruce 378 ECB : }
379 : }
380 : }
381 :
7522 bruce 382 GIC 33 : if (lisat == false)
383 : {
7558 384 33 : lisat = true;
1105 akorotkov 385 CBC 33 : LOOPBYTE(siglen)
386 : {
5623 bruce 387 33 : if (((unsigned char *) ls)[i] != 0xff)
5623 bruce 388 ECB : {
5623 bruce 389 GIC 33 : lisat = false;
5623 bruce 390 CBC 33 : break;
391 : }
7522 bruce 392 ECB : }
7558 393 : }
394 :
7522 bruce 395 GIC 33 : if (risat == false)
396 : {
7558 397 33 : risat = true;
1105 akorotkov 398 CBC 33 : LOOPBYTE(siglen)
399 : {
5623 bruce 400 33 : if (((unsigned char *) rs)[i] != 0xff)
5623 bruce 401 ECB : {
5623 bruce 402 GIC 33 : risat = false;
5623 bruce 403 CBC 33 : break;
404 : }
7522 bruce 405 ECB : }
7558 406 : }
407 :
1105 akorotkov 408 GIC 33 : lu_l = LTG_GETLNODE(GETENTRY(entryvec, array[FirstOffsetNumber].index), siglen);
409 33 : lu = ltree_gist_alloc(lisat, ls, siglen, lu_l, lu_r);
410 :
1105 akorotkov 411 CBC 33 : ru_l = LTG_GETLNODE(GETENTRY(entryvec, array[1 + ((maxoff - FirstOffsetNumber + 1) / 2)].index), siglen);
412 33 : ru = ltree_gist_alloc(risat, rs, siglen, ru_l, ru_r);
413 :
414 33 : pfree(ls);
415 33 : pfree(rs);
416 :
7558 bruce 417 33 : v->spl_ldatum = PointerGetDatum(lu);
418 33 : v->spl_rdatum = PointerGetDatum(ru);
419 :
420 33 : PG_RETURN_POINTER(v);
7558 bruce 421 ECB : }
422 :
423 : static bool
1105 akorotkov 424 GIC 22 : gist_isparent(ltree_gist *key, ltree *query, int siglen)
425 : {
3940 peter_e 426 22 : int32 numlevel = query->numlevel;
7522 bruce 427 ECB : int i;
428 :
7522 bruce 429 CBC 94 : for (i = query->numlevel; i >= 0; i--)
430 : {
7522 bruce 431 GIC 76 : query->numlevel = i;
1105 akorotkov 432 CBC 80 : if (ltree_compare(query, LTG_GETLNODE(key, siglen)) >= 0 &&
1105 akorotkov 433 GIC 4 : ltree_compare(query, LTG_GETRNODE(key, siglen)) <= 0)
7522 bruce 434 ECB : {
7558 bruce 435 CBC 4 : query->numlevel = numlevel;
436 4 : return true;
437 : }
7558 bruce 438 ECB : }
439 :
7558 bruce 440 GIC 18 : query->numlevel = numlevel;
441 18 : return false;
442 : }
7558 bruce 443 ECB :
6088 teodor 444 : static ltree *
5050 bruce 445 GIC 44 : copy_ltree(ltree *src)
446 : {
2588 andres 447 44 : ltree *dst = (ltree *) palloc0(VARSIZE(src));
6031 bruce 448 ECB :
5884 tgl 449 GIC 44 : memcpy(dst, src, VARSIZE(src));
6088 teodor 450 CBC 44 : return dst;
451 : }
6088 teodor 452 ECB :
7558 bruce 453 : static bool
1105 akorotkov 454 GIC 22 : gist_ischild(ltree_gist *key, ltree *query, int siglen)
455 : {
456 22 : ltree *left = copy_ltree(LTG_GETLNODE(key, siglen));
1105 akorotkov 457 CBC 22 : ltree *right = copy_ltree(LTG_GETRNODE(key, siglen));
6031 bruce 458 GIC 22 : bool res = true;
6088 teodor 459 ECB :
6088 teodor 460 CBC 22 : if (left->numlevel > query->numlevel)
461 14 : left->numlevel = query->numlevel;
462 :
463 22 : if (ltree_compare(query, left) < 0)
464 18 : res = false;
465 :
466 22 : if (right->numlevel > query->numlevel)
467 21 : right->numlevel = query->numlevel;
468 :
469 22 : if (res && ltree_compare(query, right) > 0)
6088 teodor 470 LBC 0 : res = false;
471 :
6088 teodor 472 CBC 22 : pfree(left);
6088 teodor 473 GBC 22 : pfree(right);
474 :
6088 teodor 475 CBC 22 : return res;
7558 bruce 476 ECB : }
477 :
478 : static bool
1105 akorotkov 479 GIC 196 : gist_qe(ltree_gist *key, lquery *query, int siglen)
480 : {
7522 bruce 481 196 : lquery_level *curq = LQUERY_FIRST(query);
7522 bruce 482 CBC 196 : BITVECP sign = LTG_SIGN(key);
7522 bruce 483 GIC 196 : int qlen = query->numlevel;
7558 bruce 484 ECB :
7522 bruce 485 CBC 196 : if (LTG_ISALLTRUE(key))
7558 bruce 486 LBC 0 : return true;
487 :
7522 bruce 488 CBC 769 : while (qlen > 0)
7522 bruce 489 EUB : {
7522 bruce 490 GIC 573 : if (curq->numvar && LQL_CANLOOKSIGN(curq))
7522 bruce 491 ECB : {
7522 bruce 492 GIC 377 : bool isexist = false;
7522 bruce 493 CBC 377 : int vlen = curq->numvar;
7558 bruce 494 GIC 377 : lquery_variant *curv = LQL_FIRST(curq);
7522 bruce 495 ECB :
7522 bruce 496 CBC 377 : while (vlen > 0)
7522 bruce 497 ECB : {
1105 akorotkov 498 GIC 377 : if (GETBIT(sign, HASHVAL(curv->val, siglen)))
7522 bruce 499 ECB : {
7522 bruce 500 GIC 377 : isexist = true;
7558 bruce 501 CBC 377 : break;
502 : }
7558 bruce 503 LBC 0 : curv = LVAR_NEXT(curv);
504 0 : vlen--;
505 : }
7522 bruce 506 GBC 377 : if (!isexist)
7522 bruce 507 UBC 0 : return false;
508 : }
7558 bruce 509 ECB :
7558 bruce 510 GBC 573 : curq = LQL_NEXT(curq);
7558 bruce 511 GIC 573 : qlen--;
512 : }
7558 bruce 513 ECB :
7558 bruce 514 CBC 196 : return true;
515 : }
516 :
7558 bruce 517 ECB : static int
5050 bruce 518 GIC 260 : gist_tqcmp(ltree *t, lquery *q)
519 : {
7558 520 260 : ltree_level *al = LTREE_FIRST(t);
7558 bruce 521 CBC 260 : lquery_level *ql = LQUERY_FIRST(q);
522 : lquery_variant *bl;
7522 523 260 : int an = t->numlevel;
524 260 : int bn = q->firstgood;
7522 bruce 525 GIC 260 : int res = 0;
7558 bruce 526 ECB :
7522 bruce 527 CBC 308 : while (an > 0 && bn > 0)
7522 bruce 528 ECB : {
7558 bruce 529 GIC 242 : bl = LQL_FIRST(ql);
4492 rhaas 530 CBC 242 : if ((res = memcmp(al->name, bl->name, Min(al->len, bl->len))) == 0)
531 : {
7522 bruce 532 83 : if (al->len != bl->len)
7558 533 35 : return al->len - bl->len;
534 : }
7522 bruce 535 ECB : else
7558 bruce 536 CBC 159 : return res;
7522 bruce 537 GIC 48 : an--;
538 48 : bn--;
7558 bruce 539 CBC 48 : al = LEVEL_NEXT(al);
540 48 : ql = LQL_NEXT(ql);
7558 bruce 541 ECB : }
542 :
6089 teodor 543 CBC 66 : return Min(t->numlevel, q->firstgood) - q->firstgood;
544 : }
545 :
7558 bruce 546 ECB : static bool
1105 akorotkov 547 GIC 196 : gist_between(ltree_gist *key, lquery *query, int siglen)
548 : {
7522 bruce 549 196 : if (query->firstgood == 0)
7558 bruce 550 CBC 37 : return true;
551 :
1105 akorotkov 552 159 : if (gist_tqcmp(LTG_GETLNODE(key, siglen), query) > 0)
6089 teodor 553 58 : return false;
554 :
1105 akorotkov 555 101 : if (gist_tqcmp(LTG_GETRNODE(key, siglen), query) < 0)
6089 teodor 556 45 : return false;
557 :
558 56 : return true;
7558 bruce 559 ECB : }
560 :
1105 akorotkov 561 : typedef struct LtreeSignature
562 : {
563 : BITVECP sign;
564 : int siglen;
565 : } LtreeSignature;
566 :
567 : static bool
1105 akorotkov 568 GIC 74 : checkcondition_bit(void *cxt, ITEM *val)
569 : {
570 74 : LtreeSignature *sig = cxt;
1105 akorotkov 571 ECB :
1105 akorotkov 572 GIC 74 : return (FLG_CANLOOKSIGN(val->flag)) ? GETBIT(sig->sign, HASHVAL(val->val, sig->siglen)) : true;
7558 bruce 573 ECB : }
574 :
575 : static bool
1105 akorotkov 576 GIC 37 : gist_qtxt(ltree_gist *key, ltxtquery *query, int siglen)
577 : {
578 : LtreeSignature sig;
1105 akorotkov 579 ECB :
7522 bruce 580 GIC 37 : if (LTG_ISALLTRUE(key))
7558 bruce 581 UIC 0 : return true;
582 :
1105 akorotkov 583 CBC 37 : sig.sign = LTG_SIGN(key);
1105 akorotkov 584 GBC 37 : sig.siglen = siglen;
585 :
1165 alvherre 586 CBC 37 : return ltree_execute(GETQUERY(query),
1105 akorotkov 587 ECB : &sig, false,
588 : checkcondition_bit);
7558 bruce 589 : }
590 :
591 : static bool
1105 akorotkov 592 GIC 30 : arrq_cons(ltree_gist *key, ArrayType *_query, int siglen)
593 : {
6797 bruce 594 30 : lquery *query = (lquery *) ARR_DATA_PTR(_query);
6797 bruce 595 CBC 30 : int num = ArrayGetNItems(ARR_NDIM(_query), ARR_DIMS(_query));
596 :
4792 tgl 597 30 : if (ARR_NDIM(_query) > 1)
6797 bruce 598 LBC 0 : ereport(ERROR,
599 : (errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
7199 tgl 600 ECB : errmsg("array must be one-dimensional")));
4473 tgl 601 GBC 30 : if (array_contains_nulls(_query))
6350 tgl 602 UIC 0 : ereport(ERROR,
603 : (errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
6350 tgl 604 ECB : errmsg("array must not contain nulls")));
7354 bruce 605 EUB :
6797 bruce 606 GIC 64 : while (num > 0)
607 : {
1105 akorotkov 608 47 : if (gist_qe(key, query, siglen) && gist_between(key, query, siglen))
6797 bruce 609 CBC 13 : return true;
6797 bruce 610 GIC 34 : num--;
6797 bruce 611 CBC 34 : query = NEXTVAL(query);
6797 bruce 612 ECB : }
7354 bruce 613 CBC 17 : return false;
7354 bruce 614 ECB : }
615 :
7522 616 : Datum
7522 bruce 617 GIC 12123 : ltree_consistent(PG_FUNCTION_ARGS)
618 : {
619 12123 : GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
7558 bruce 620 CBC 12123 : StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
621 :
5473 tgl 622 ECB : /* Oid subtype = PG_GETARG_OID(3); */
5473 tgl 623 CBC 12123 : bool *recheck = (bool *) PG_GETARG_POINTER(4);
389 akorotkov 624 GIC 12123 : int siglen = LTREE_GET_SIGLEN();
5473 tgl 625 12123 : ltree_gist *key = (ltree_gist *) DatumGetPointer(entry->key);
5473 tgl 626 CBC 12123 : void *query = NULL;
7522 bruce 627 12123 : bool res = false;
7558 bruce 628 ECB :
5473 tgl 629 : /* All cases served by this function are exact */
5473 tgl 630 CBC 12123 : *recheck = false;
631 :
7522 bruce 632 GIC 12123 : switch (strategy)
7522 bruce 633 ECB : {
7558 bruce 634 GIC 459 : case BTLessStrategyNumber:
2029 tgl 635 CBC 459 : query = PG_GETARG_LTREE_P(1);
7522 bruce 636 GIC 459 : res = (GIST_LEAF(entry)) ?
7522 bruce 637 CBC 437 : (ltree_compare((ltree *) query, LTG_NODE(key)) > 0)
7558 638 918 : :
1105 akorotkov 639 22 : (ltree_compare((ltree *) query, LTG_GETLNODE(key, siglen)) >= 0);
7558 bruce 640 459 : break;
641 459 : case BTLessEqualStrategyNumber:
2029 tgl 642 459 : query = PG_GETARG_LTREE_P(1);
1105 akorotkov 643 459 : res = (ltree_compare((ltree *) query, LTG_GETLNODE(key, siglen)) >= 0);
7558 bruce 644 459 : break;
645 294 : case BTEqualStrategyNumber:
2029 tgl 646 294 : query = PG_GETARG_LTREE_P(1);
7522 bruce 647 294 : if (GIST_LEAF(entry))
648 272 : res = (ltree_compare((ltree *) query, LTG_NODE(key)) == 0);
7558 bruce 649 ECB : else
1105 akorotkov 650 CBC 44 : res = (ltree_compare((ltree *) query, LTG_GETLNODE(key, siglen)) >= 0
7522 bruce 651 30 : &&
1105 akorotkov 652 GIC 8 : ltree_compare((ltree *) query, LTG_GETRNODE(key, siglen)) <= 0);
7558 bruce 653 CBC 294 : break;
654 1884 : case BTGreaterEqualStrategyNumber:
2029 tgl 655 1884 : query = PG_GETARG_LTREE_P(1);
1105 akorotkov 656 1884 : res = (ltree_compare((ltree *) query, LTG_GETRNODE(key, siglen)) <= 0);
7558 bruce 657 1884 : break;
658 1884 : case BTGreaterStrategyNumber:
2029 tgl 659 1884 : query = PG_GETARG_LTREE_P(1);
7522 bruce 660 1884 : res = (GIST_LEAF(entry)) ?
1105 akorotkov 661 1847 : (ltree_compare((ltree *) query, LTG_GETRNODE(key, siglen)) < 0)
7558 bruce 662 3768 : :
1105 akorotkov 663 37 : (ltree_compare((ltree *) query, LTG_GETRNODE(key, siglen)) <= 0);
7558 bruce 664 1884 : break;
665 187 : case 10:
2029 tgl 666 187 : query = PG_GETARG_LTREE_P_COPY(1);
7522 bruce 667 187 : res = (GIST_LEAF(entry)) ?
668 165 : inner_isparent((ltree *) query, LTG_NODE(key))
7558 669 352 : :
1105 akorotkov 670 22 : gist_isparent(key, (ltree *) query, siglen);
7558 bruce 671 187 : break;
672 187 : case 11:
2029 tgl 673 187 : query = PG_GETARG_LTREE_P(1);
7522 bruce 674 187 : res = (GIST_LEAF(entry)) ?
675 165 : inner_isparent(LTG_NODE(key), (ltree *) query)
7558 676 352 : :
1105 akorotkov 677 22 : gist_ischild(key, (ltree *) query, siglen);
7558 bruce 678 187 : break;
679 4099 : case 12:
7558 bruce 680 ECB : case 13:
2029 tgl 681 CBC 4099 : query = PG_GETARG_LQUERY_P(1);
7522 bruce 682 4099 : if (GIST_LEAF(entry))
7522 bruce 683 GIC 3950 : res = DatumGetBool(DirectFunctionCall2(ltq_regex,
2118 tgl 684 ECB : PointerGetDatum(LTG_NODE(key)),
685 : PointerGetDatum((lquery *) query)
7522 bruce 686 : ));
687 : else
1105 akorotkov 688 GIC 298 : res = (gist_qe(key, (lquery *) query, siglen) &&
689 149 : gist_between(key, (lquery *) query, siglen));
7522 bruce 690 4099 : break;
7558 bruce 691 CBC 2049 : case 14:
7558 bruce 692 ECB : case 15:
2029 tgl 693 CBC 2049 : query = PG_GETARG_LTXTQUERY_P(1);
7522 bruce 694 2049 : if (GIST_LEAF(entry))
7522 bruce 695 GIC 2012 : res = DatumGetBool(DirectFunctionCall2(ltxtq_exec,
2118 tgl 696 ECB : PointerGetDatum(LTG_NODE(key)),
2029 697 : PointerGetDatum((ltxtquery *) query)
7522 bruce 698 : ));
699 : else
1105 akorotkov 700 GIC 37 : res = gist_qtxt(key, (ltxtquery *) query, siglen);
7522 bruce 701 2049 : break;
7354 702 621 : case 16:
7354 bruce 703 ECB : case 17:
2029 tgl 704 CBC 621 : query = PG_GETARG_ARRAYTYPE_P(1);
7354 bruce 705 621 : if (GIST_LEAF(entry))
7354 bruce 706 GIC 591 : res = DatumGetBool(DirectFunctionCall2(lt_q_regex,
2118 tgl 707 ECB : PointerGetDatum(LTG_NODE(key)),
708 : PointerGetDatum((ArrayType *) query)
7354 bruce 709 : ));
710 : else
1105 akorotkov 711 GIC 30 : res = arrq_cons(key, (ArrayType *) query, siglen);
7354 bruce 712 621 : break;
7558 bruce 713 UIC 0 : default:
7199 tgl 714 ECB : /* internal error */
7199 tgl 715 LBC 0 : elog(ERROR, "unrecognized StrategyNumber: %d", strategy);
7558 bruce 716 EUB : }
717 :
6031 bruce 718 GBC 12123 : PG_FREE_IF_COPY(query, 1);
7558 bruce 719 GIC 12123 : PG_RETURN_BOOL(res);
720 : }
1105 akorotkov 721 ECB :
722 : Datum
1105 akorotkov 723 GIC 9 : ltree_gist_options(PG_FUNCTION_ARGS)
724 : {
725 9 : local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
1105 akorotkov 726 ECB :
1105 akorotkov 727 GIC 9 : init_local_reloptions(relopts, sizeof(LtreeGistOptions));
1105 akorotkov 728 CBC 9 : add_local_int_reloption(relopts, "siglen",
729 : "signature length in bytes",
389 akorotkov 730 ECB : LTREE_SIGLEN_DEFAULT, 1, LTREE_SIGLEN_MAX,
1105 731 : offsetof(LtreeGistOptions, siglen));
732 :
1105 akorotkov 733 GIC 9 : PG_RETURN_VOID();
734 : }
|
