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