_ltree_gist.c 12.3 KB
Newer Older
1
/*
Bruce Momjian's avatar
Bruce Momjian committed
2
 * GiST support for ltree[]
3 4 5 6 7
 * Teodor Sigaev <teodor@stack.net>
 */

#include "ltree.h"
#include "access/gist.h"
8
#include "access/skey.h"
9 10 11 12
#include "utils/array.h"

#include "crc32.h"

Bruce Momjian's avatar
Bruce Momjian committed
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
PG_FUNCTION_INFO_V1(_ltree_compress);
Datum		_ltree_compress(PG_FUNCTION_ARGS);

PG_FUNCTION_INFO_V1(_ltree_same);
Datum		_ltree_same(PG_FUNCTION_ARGS);

PG_FUNCTION_INFO_V1(_ltree_union);
Datum		_ltree_union(PG_FUNCTION_ARGS);

PG_FUNCTION_INFO_V1(_ltree_penalty);
Datum		_ltree_penalty(PG_FUNCTION_ARGS);

PG_FUNCTION_INFO_V1(_ltree_picksplit);
Datum		_ltree_picksplit(PG_FUNCTION_ARGS);

PG_FUNCTION_INFO_V1(_ltree_consistent);
Datum		_ltree_consistent(PG_FUNCTION_ARGS);
30

31
#define GETENTRY(vec,pos) ((ltree_gist *) DatumGetPointer((vec)->vector[(pos)].key))
32
#define NEXTVAL(x) ( (ltree*)( (char*)(x) + INTALIGN( VARSIZE(x) ) ) )
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

/* Number of one-bits in an unsigned byte */
static const uint8 number_of_ones[256] = {
	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

54 55
#define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )

56

57
static void
Bruce Momjian's avatar
Bruce Momjian committed
58 59 60
hashing(BITVECP sign, ltree * t)
{
	int			tlen = t->numlevel;
61
	ltree_level *cur = LTREE_FIRST(t);
Bruce Momjian's avatar
Bruce Momjian committed
62
	int			hash;
63

Bruce Momjian's avatar
Bruce Momjian committed
64 65 66 67
	while (tlen > 0)
	{
		hash = ltree_crc32_sz(cur->name, cur->len);
		AHASH(sign, hash);
68 69 70 71 72
		cur = LEVEL_NEXT(cur);
		tlen--;
	}
}

Bruce Momjian's avatar
Bruce Momjian committed
73 74 75 76
Datum
_ltree_compress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
77 78
	GISTENTRY  *retval = entry;

Bruce Momjian's avatar
Bruce Momjian committed
79 80 81 82 83 84 85
	if (entry->leafkey)
	{							/* ltree */
		ltree_gist *key;
		ArrayType  *val = DatumGetArrayTypeP(entry->key);
		int4		len = LTG_HDRSIZE + ASIGLEN;
		int			num = ArrayGetNItems(ARR_NDIM(val), ARR_DIMS(val));
		ltree	   *item = (ltree *) ARR_DATA_PTR(val);
86

Bruce Momjian's avatar
Bruce Momjian committed
87
		if (ARR_NDIM(val) != 1)
88
			ereport(ERROR,
Bruce Momjian's avatar
Bruce Momjian committed
89 90
					(errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
					 errmsg("array must be one-dimensional")));
91 92 93 94
		if (ARR_HASNULL(val))
			ereport(ERROR,
					(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
					 errmsg("array must not contain nulls")));
95

Bruce Momjian's avatar
Bruce Momjian committed
96
		key = (ltree_gist *) palloc(len);
97
		SET_VARSIZE(key, len);
98 99
		key->flag = 0;

Teodor Sigaev's avatar
Teodor Sigaev committed
100
		MemSet(LTG_SIGN(key), 0, ASIGLEN);
Bruce Momjian's avatar
Bruce Momjian committed
101 102
		while (num > 0)
		{
103 104 105 106 107
			hashing(LTG_SIGN(key), item);
			num--;
			item = NEXTVAL(item);
		}

Bruce Momjian's avatar
Bruce Momjian committed
108
		retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
109
		gistentryinit(*retval, PointerGetDatum(key),
Bruce Momjian's avatar
Bruce Momjian committed
110
					  entry->rel, entry->page,
Teodor Sigaev's avatar
Teodor Sigaev committed
111
					  entry->offset, FALSE);
Bruce Momjian's avatar
Bruce Momjian committed
112
	}
Bruce Momjian's avatar
Bruce Momjian committed
113
	else if (!LTG_ISALLTRUE(entry->key))
Bruce Momjian's avatar
Bruce Momjian committed
114 115 116 117
	{
		int4		i,
					len;
		ltree_gist *key;
118

Bruce Momjian's avatar
Bruce Momjian committed
119
		BITVECP		sign = LTG_SIGN(DatumGetPointer(entry->key));
120

121 122 123 124 125
		ALOOPBYTE
		{
			if ((sign[i] & 0xff) != 0xff)
				PG_RETURN_POINTER(retval);
		}
Bruce Momjian's avatar
Bruce Momjian committed
126 127
		len = LTG_HDRSIZE;
		key = (ltree_gist *) palloc(len);
128
		SET_VARSIZE(key, len);
129 130
		key->flag = LTG_ALLTRUE;

Bruce Momjian's avatar
Bruce Momjian committed
131
		retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
132
		gistentryinit(*retval, PointerGetDatum(key),
Bruce Momjian's avatar
Bruce Momjian committed
133
					  entry->rel, entry->page,
Teodor Sigaev's avatar
Teodor Sigaev committed
134
					  entry->offset, FALSE);
135 136 137 138
	}
	PG_RETURN_POINTER(retval);
}

Bruce Momjian's avatar
Bruce Momjian committed
139 140 141 142 143 144
Datum
_ltree_same(PG_FUNCTION_ARGS)
{
	ltree_gist *a = (ltree_gist *) PG_GETARG_POINTER(0);
	ltree_gist *b = (ltree_gist *) PG_GETARG_POINTER(1);
	bool	   *result = (bool *) PG_GETARG_POINTER(2);
145

Bruce Momjian's avatar
Bruce Momjian committed
146
	if (LTG_ISALLTRUE(a) && LTG_ISALLTRUE(b))
147
		*result = true;
Bruce Momjian's avatar
Bruce Momjian committed
148
	else if (LTG_ISALLTRUE(a))
149
		*result = false;
Bruce Momjian's avatar
Bruce Momjian committed
150
	else if (LTG_ISALLTRUE(b))
151
		*result = false;
Bruce Momjian's avatar
Bruce Momjian committed
152 153 154 155 156 157
	else
	{
		int4		i;
		BITVECP		sa = LTG_SIGN(a),
					sb = LTG_SIGN(b);

158
		*result = true;
159 160 161 162 163 164 165
		ALOOPBYTE
		{
			if (sa[i] != sb[i])
			{
				*result = false;
				break;
			}
Bruce Momjian's avatar
Bruce Momjian committed
166 167 168
		}
	}
	PG_RETURN_POINTER(result);
169 170
}

Bruce Momjian's avatar
Bruce Momjian committed
171 172 173 174 175
static int4
unionkey(BITVECP sbase, ltree_gist * add)
{
	int4		i;
	BITVECP		sadd = LTG_SIGN(add);
176

Bruce Momjian's avatar
Bruce Momjian committed
177
	if (LTG_ISALLTRUE(add))
178 179
		return 1;

180 181
	ALOOPBYTE
		sbase[i] |= sadd[i];
182 183 184
	return 0;
}

Bruce Momjian's avatar
Bruce Momjian committed
185 186 187
Datum
_ltree_union(PG_FUNCTION_ARGS)
{
Bruce Momjian's avatar
Bruce Momjian committed
188
	GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
Bruce Momjian's avatar
Bruce Momjian committed
189 190
	int		   *size = (int *) PG_GETARG_POINTER(1);
	ABITVEC		base;
Bruce Momjian's avatar
Bruce Momjian committed
191 192
	int4		i,
				len;
Bruce Momjian's avatar
Bruce Momjian committed
193 194 195 196
	int4		flag = 0;
	ltree_gist *result;

	MemSet((void *) base, 0, sizeof(ABITVEC));
197
	for (i = 0; i < entryvec->n; i++)
Bruce Momjian's avatar
Bruce Momjian committed
198 199 200
	{
		if (unionkey(base, GETENTRY(entryvec, i)))
		{
201 202 203 204 205
			flag = LTG_ALLTRUE;
			break;
		}
	}

Bruce Momjian's avatar
Bruce Momjian committed
206 207
	len = LTG_HDRSIZE + ((flag & LTG_ALLTRUE) ? 0 : ASIGLEN);
	result = (ltree_gist *) palloc(len);
208
	SET_VARSIZE(result, len);
209
	result->flag = flag;
Bruce Momjian's avatar
Bruce Momjian committed
210 211
	if (!LTG_ISALLTRUE(result))
		memcpy((void *) LTG_SIGN(result), (void *) base, sizeof(ABITVEC));
212
	*size = len;
213

Bruce Momjian's avatar
Bruce Momjian committed
214
	PG_RETURN_POINTER(result);
215 216 217
}

static int4
Bruce Momjian's avatar
Bruce Momjian committed
218 219 220 221 222
sizebitvec(BITVECP sign)
{
	int4		size = 0,
				i;

223 224
	ALOOPBYTE
		size += number_of_ones[(unsigned char) sign[i]];
225 226 227
	return size;
}

Bruce Momjian's avatar
Bruce Momjian committed
228 229 230 231
static int
hemdistsign(BITVECP a, BITVECP b)
{
	int			i,
232
				diff,
Bruce Momjian's avatar
Bruce Momjian committed
233 234
				dist = 0;

235 236 237 238 239
	ALOOPBYTE
	{
		diff = (unsigned char) (a[i] ^ b[i]);
		dist += number_of_ones[diff];
	}
Bruce Momjian's avatar
Bruce Momjian committed
240 241 242 243
	return dist;
}

static int
Bruce Momjian's avatar
Bruce Momjian committed
244 245 246 247 248 249 250 251 252 253 254 255 256
hemdist(ltree_gist * a, ltree_gist * b)
{
	if (LTG_ISALLTRUE(a))
	{
		if (LTG_ISALLTRUE(b))
			return 0;
		else
			return ASIGLENBIT - sizebitvec(LTG_SIGN(b));
	}
	else if (LTG_ISALLTRUE(b))
		return ASIGLENBIT - sizebitvec(LTG_SIGN(a));

	return hemdistsign(LTG_SIGN(a), LTG_SIGN(b));
Bruce Momjian's avatar
Bruce Momjian committed
257 258 259
}


Bruce Momjian's avatar
Bruce Momjian committed
260 261 262 263 264 265
Datum
_ltree_penalty(PG_FUNCTION_ARGS)
{
	ltree_gist *origval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(0))->key);
	ltree_gist *newval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(1))->key);
	float	   *penalty = (float *) PG_GETARG_POINTER(2);
266

Bruce Momjian's avatar
Bruce Momjian committed
267
	*penalty = hemdist(origval, newval);
Bruce Momjian's avatar
Bruce Momjian committed
268
	PG_RETURN_POINTER(penalty);
269 270
}

Bruce Momjian's avatar
Bruce Momjian committed
271 272 273 274
typedef struct
{
	OffsetNumber pos;
	int4		cost;
Bruce Momjian's avatar
Bruce Momjian committed
275
}	SPLITCOST;
276 277

static int
Bruce Momjian's avatar
Bruce Momjian committed
278 279 280
comparecost(const void *a, const void *b)
{
	return ((SPLITCOST *) a)->cost - ((SPLITCOST *) b)->cost;
281 282
}

Bruce Momjian's avatar
Bruce Momjian committed
283 284 285
Datum
_ltree_picksplit(PG_FUNCTION_ARGS)
{
Bruce Momjian's avatar
Bruce Momjian committed
286
	GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
Bruce Momjian's avatar
Bruce Momjian committed
287 288 289 290 291
	GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
	OffsetNumber k,
				j;
	ltree_gist *datum_l,
			   *datum_r;
Bruce Momjian's avatar
Bruce Momjian committed
292
	BITVECP		union_l,
Bruce Momjian's avatar
Bruce Momjian committed
293
				union_r;
Bruce Momjian's avatar
Bruce Momjian committed
294 295
	int4		size_alpha,
				size_beta;
Bruce Momjian's avatar
Bruce Momjian committed
296
	int4		size_waste,
Bruce Momjian's avatar
Bruce Momjian committed
297
				waste = -1;
Bruce Momjian's avatar
Bruce Momjian committed
298 299 300 301 302
	int4		nbytes;
	OffsetNumber seed_1 = 0,
				seed_2 = 0;
	OffsetNumber *left,
			   *right;
303
	OffsetNumber maxoff;
Bruce Momjian's avatar
Bruce Momjian committed
304
	BITVECP		ptr;
Bruce Momjian's avatar
Bruce Momjian committed
305 306 307 308
	int			i;
	SPLITCOST  *costvector;
	ltree_gist *_k,
			   *_j;
309

310
	maxoff = entryvec->n - 2;
311 312 313 314
	nbytes = (maxoff + 2) * sizeof(OffsetNumber);
	v->spl_left = (OffsetNumber *) palloc(nbytes);
	v->spl_right = (OffsetNumber *) palloc(nbytes);

Bruce Momjian's avatar
Bruce Momjian committed
315 316
	for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
	{
Bruce Momjian's avatar
Bruce Momjian committed
317
		_k = GETENTRY(entryvec, k);
Bruce Momjian's avatar
Bruce Momjian committed
318 319 320 321 322
		for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
		{
			size_waste = hemdist(_k, GETENTRY(entryvec, j));
			if (size_waste > waste)
			{
323 324 325 326 327 328 329 330 331 332 333 334
				waste = size_waste;
				seed_1 = k;
				seed_2 = j;
			}
		}
	}

	left = v->spl_left;
	v->spl_nleft = 0;
	right = v->spl_right;
	v->spl_nright = 0;

Bruce Momjian's avatar
Bruce Momjian committed
335 336
	if (seed_1 == 0 || seed_2 == 0)
	{
337 338 339 340 341
		seed_1 = 1;
		seed_2 = 2;
	}

	/* form initial .. */
Bruce Momjian's avatar
Bruce Momjian committed
342 343 344
	if (LTG_ISALLTRUE(GETENTRY(entryvec, seed_1)))
	{
		datum_l = (ltree_gist *) palloc(LTG_HDRSIZE);
345
		SET_VARSIZE(datum_l, LTG_HDRSIZE);
Bruce Momjian's avatar
Bruce Momjian committed
346
		datum_l->flag = LTG_ALLTRUE;
347
	}
Bruce Momjian's avatar
Bruce Momjian committed
348 349 350
	else
	{
		datum_l = (ltree_gist *) palloc(LTG_HDRSIZE + ASIGLEN);
351
		SET_VARSIZE(datum_l, LTG_HDRSIZE + ASIGLEN);
Bruce Momjian's avatar
Bruce Momjian committed
352 353 354 355 356 357
		datum_l->flag = 0;
		memcpy((void *) LTG_SIGN(datum_l), (void *) LTG_SIGN(GETENTRY(entryvec, seed_1)), sizeof(ABITVEC));
	}
	if (LTG_ISALLTRUE(GETENTRY(entryvec, seed_2)))
	{
		datum_r = (ltree_gist *) palloc(LTG_HDRSIZE);
358
		SET_VARSIZE(datum_r, LTG_HDRSIZE);
Bruce Momjian's avatar
Bruce Momjian committed
359 360 361 362 363
		datum_r->flag = LTG_ALLTRUE;
	}
	else
	{
		datum_r = (ltree_gist *) palloc(LTG_HDRSIZE + ASIGLEN);
364
		SET_VARSIZE(datum_r, LTG_HDRSIZE + ASIGLEN);
Bruce Momjian's avatar
Bruce Momjian committed
365 366
		datum_r->flag = 0;
		memcpy((void *) LTG_SIGN(datum_r), (void *) LTG_SIGN(GETENTRY(entryvec, seed_2)), sizeof(ABITVEC));
367 368 369 370
	}

	maxoff = OffsetNumberNext(maxoff);
	/* sort before ... */
Bruce Momjian's avatar
Bruce Momjian committed
371 372 373 374 375
	costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * maxoff);
	for (j = FirstOffsetNumber; j <= maxoff; j = OffsetNumberNext(j))
	{
		costvector[j - 1].pos = j;
		_j = GETENTRY(entryvec, j);
Bruce Momjian's avatar
Bruce Momjian committed
376 377
		size_alpha = hemdist(datum_l, _j);
		size_beta = hemdist(datum_r, _j);
378
		costvector[j - 1].cost = Abs(size_alpha - size_beta);
379
	}
Bruce Momjian's avatar
Bruce Momjian committed
380
	qsort((void *) costvector, maxoff, sizeof(SPLITCOST), comparecost);
381

Bruce Momjian's avatar
Bruce Momjian committed
382 383 384
	union_l = LTG_SIGN(datum_l);
	union_r = LTG_SIGN(datum_r);

Bruce Momjian's avatar
Bruce Momjian committed
385 386
	for (k = 0; k < maxoff; k++)
	{
387
		j = costvector[k].pos;
Bruce Momjian's avatar
Bruce Momjian committed
388 389
		if (j == seed_1)
		{
390 391 392
			*left++ = j;
			v->spl_nleft++;
			continue;
Bruce Momjian's avatar
Bruce Momjian committed
393 394 395
		}
		else if (j == seed_2)
		{
396 397 398 399
			*right++ = j;
			v->spl_nright++;
			continue;
		}
Bruce Momjian's avatar
Bruce Momjian committed
400
		_j = GETENTRY(entryvec, j);
Bruce Momjian's avatar
Bruce Momjian committed
401 402
		size_alpha = hemdist(datum_l, _j);
		size_beta = hemdist(datum_r, _j);
403

Bruce Momjian's avatar
Bruce Momjian committed
404
		if (size_alpha < size_beta + WISH_F(v->spl_nleft, v->spl_nright, 0.00001))
Bruce Momjian's avatar
Bruce Momjian committed
405
		{
Bruce Momjian's avatar
Bruce Momjian committed
406 407
			if (LTG_ISALLTRUE(datum_l) || LTG_ISALLTRUE(_j))
			{
Bruce Momjian's avatar
Bruce Momjian committed
408
				if (!LTG_ISALLTRUE(datum_l))
Bruce Momjian's avatar
Bruce Momjian committed
409 410 411 412 413
					MemSet((void *) union_l, 0xff, sizeof(ABITVEC));
			}
			else
			{
				ptr = LTG_SIGN(_j);
414 415
				ALOOPBYTE
					union_l[i] |= ptr[i];
416 417 418
			}
			*left++ = j;
			v->spl_nleft++;
Bruce Momjian's avatar
Bruce Momjian committed
419 420 421
		}
		else
		{
Bruce Momjian's avatar
Bruce Momjian committed
422 423
			if (LTG_ISALLTRUE(datum_r) || LTG_ISALLTRUE(_j))
			{
Bruce Momjian's avatar
Bruce Momjian committed
424
				if (!LTG_ISALLTRUE(datum_r))
Bruce Momjian's avatar
Bruce Momjian committed
425 426 427 428 429
					MemSet((void *) union_r, 0xff, sizeof(ABITVEC));
			}
			else
			{
				ptr = LTG_SIGN(_j);
430 431
				ALOOPBYTE
					union_r[i] |= ptr[i];
432 433 434 435 436 437 438 439 440 441 442
			}
			*right++ = j;
			v->spl_nright++;
		}
	}

	*right = *left = FirstOffsetNumber;

	v->spl_ldatum = PointerGetDatum(datum_l);
	v->spl_rdatum = PointerGetDatum(datum_r);

Bruce Momjian's avatar
Bruce Momjian committed
443
	PG_RETURN_POINTER(v);
444 445 446
}

static bool
Bruce Momjian's avatar
Bruce Momjian committed
447 448 449 450 451
gist_te(ltree_gist * key, ltree * query)
{
	ltree_level *curq = LTREE_FIRST(query);
	BITVECP		sign = LTG_SIGN(key);
	int			qlen = query->numlevel;
452 453
	unsigned int hv;

Bruce Momjian's avatar
Bruce Momjian committed
454
	if (LTG_ISALLTRUE(key))
455 456
		return true;

Bruce Momjian's avatar
Bruce Momjian committed
457 458 459 460 461
	while (qlen > 0)
	{
		hv = ltree_crc32_sz(curq->name, curq->len);
		if (!GETBIT(sign, AHASHVAL(hv)))
			return false;
462 463 464 465 466 467 468 469
		curq = LEVEL_NEXT(curq);
		qlen--;
	}

	return true;
}

static bool
Bruce Momjian's avatar
Bruce Momjian committed
470 471 472
checkcondition_bit(void *checkval, ITEM * val)
{
	return (FLG_CANLOOKSIGN(val->flag)) ? GETBIT(checkval, AHASHVAL(val->val)) : true;
473 474 475
}

static bool
Bruce Momjian's avatar
Bruce Momjian committed
476 477 478
gist_qtxt(ltree_gist * key, ltxtquery * query)
{
	if (LTG_ISALLTRUE(key))
479
		return true;
Bruce Momjian's avatar
Bruce Momjian committed
480

481
	return ltree_execute(
Bruce Momjian's avatar
Bruce Momjian committed
482 483 484 485
						 GETQUERY(query),
						 (void *) LTG_SIGN(key), false,
						 checkcondition_bit
		);
486 487 488
}

static bool
Bruce Momjian's avatar
Bruce Momjian committed
489 490 491 492 493 494 495
gist_qe(ltree_gist * key, lquery * query)
{
	lquery_level *curq = LQUERY_FIRST(query);
	BITVECP		sign = LTG_SIGN(key);
	int			qlen = query->numlevel;

	if (LTG_ISALLTRUE(key))
496
		return true;
Bruce Momjian's avatar
Bruce Momjian committed
497 498 499 500 501 502 503

	while (qlen > 0)
	{
		if (curq->numvar && LQL_CANLOOKSIGN(curq))
		{
			bool		isexist = false;
			int			vlen = curq->numvar;
504
			lquery_variant *curv = LQL_FIRST(curq);
Bruce Momjian's avatar
Bruce Momjian committed
505 506 507 508 509 510

			while (vlen > 0)
			{
				if (GETBIT(sign, AHASHVAL(curv->val)))
				{
					isexist = true;
511 512 513 514 515
					break;
				}
				curv = LVAR_NEXT(curv);
				vlen--;
			}
Bruce Momjian's avatar
Bruce Momjian committed
516
			if (!isexist)
517 518
				return false;
		}
Bruce Momjian's avatar
Bruce Momjian committed
519

520 521 522 523 524 525 526
		curq = LQL_NEXT(curq);
		qlen--;
	}

	return true;
}

527
static bool
Bruce Momjian's avatar
Bruce Momjian committed
528 529 530 531
_arrq_cons(ltree_gist * key, ArrayType *_query)
{
	lquery	   *query = (lquery *) ARR_DATA_PTR(_query);
	int			num = ArrayGetNItems(ARR_NDIM(_query), ARR_DIMS(_query));
532

Bruce Momjian's avatar
Bruce Momjian committed
533 534
	if (ARR_NDIM(_query) != 1)
		ereport(ERROR,
535 536
				(errcode(ERRCODE_ARRAY_SUBSCRIPT_ERROR),
				 errmsg("array must be one-dimensional")));
537 538 539 540
	if (ARR_HASNULL(_query))
		ereport(ERROR,
				(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
				 errmsg("array must not contain nulls")));
541

Bruce Momjian's avatar
Bruce Momjian committed
542 543 544 545 546 547 548 549
	while (num > 0)
	{
		if (gist_qe(key, query))
			return true;
		num--;
		query = (lquery *) NEXTVAL(query);
	}
	return false;
550
}
551

Bruce Momjian's avatar
Bruce Momjian committed
552 553 554 555 556 557
Datum
_ltree_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	char	   *query = (char *) DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(1)));
	ltree_gist *key = (ltree_gist *) DatumGetPointer(entry->key);
558
	StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
Bruce Momjian's avatar
Bruce Momjian committed
559
	bool		res = false;
560

Bruce Momjian's avatar
Bruce Momjian committed
561 562
	switch (strategy)
	{
563 564
		case 10:
		case 11:
Bruce Momjian's avatar
Bruce Momjian committed
565
			res = gist_te(key, (ltree *) query);
566 567 568
			break;
		case 12:
		case 13:
Bruce Momjian's avatar
Bruce Momjian committed
569 570
			res = gist_qe(key, (lquery *) query);
			break;
571 572
		case 14:
		case 15:
Bruce Momjian's avatar
Bruce Momjian committed
573 574
			res = gist_qtxt(key, (ltxtquery *) query);
			break;
575 576 577 578
		case 16:
		case 17:
			res = _arrq_cons(key, (ArrayType *) query);
			break;
579
		default:
580 581
			/* internal error */
			elog(ERROR, "unrecognized StrategyNumber: %d", strategy);
582
	}
Bruce Momjian's avatar
Bruce Momjian committed
583
	PG_FREE_IF_COPY(query, 1);
584 585
	PG_RETURN_BOOL(res);
}