Skip to content

Commit 978c8c6

Browse files
bmomjianbmomjian
committed
please find attached patch to current CVS ( contrib/ltree )
Changes: July 31, 2002 Now works on 64-bit platforms. Added function lca - lowest common ancestor Version for 7.2 is distributed as separate package - http://www.sai.msu.su/~megera/postgres/gist/ltree/ltree-7.2.tar.gz Oleg Bartunov
1 parent 6495f4e commit 978c8c6

File tree

6 files changed

+199
-38
lines changed

6 files changed

+199
-38
lines changed

‎contrib/ltree/README.ltree

Lines changed: 21 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@ ltree - is a PostgreSQL contrib module which contains implementation of data
44
types, indexed access methods and queries for data organized as a tree-like
55
structures.
66
This module will works for PostgreSQL version 7.3.
7-
(patch for 7.2 version is provided, see INSTALLATION)
7+
(version for 7.2 version is available from http://www.sai.msu.su/~megera/postgres/gist/ltree/ltree-7.2.tar.gz)
88
-------------------------------------------------------------------------------
99
All work was done by Teodor Sigaev (teodor@stack.net) and Oleg Bartunov
1010
(oleg@sai.msu.su). See http://www.sai.msu.su/~megera/postgres/gist for
@@ -184,9 +184,21 @@ int4 nlevel
184184
nlevel
185185
--------
186186
3
187-
188-
Note, that arguments start, end, OFFSET, LEN have meaning of level of the node
189-
!
187+
Note, that arguments start, end, OFFSET, LEN have meaning of level of the
188+
node !
189+
190+
ltree lca(ltree,ltree,...) (up to 8 arguments)
191+
ltree lca(ltree[])
192+
Returns Lowest Common Ancestor (lca)
193+
# select lca('1.2.2.3','1.2.3.4.5.6');
194+
lca
195+
-----
196+
1.2
197+
# select lca('{la.2.3,1.2.3.4.5.6}') is null;
198+
?column?
199+
----------
200+
f
201+
190202

191203
INSTALLATION
192204

@@ -195,8 +207,6 @@ INSTALLATION
195207
make install
196208
make installcheck
197209

198-
for 7.2 one needs to apply patch ( patch < patch.72) before installation !
199-
200210
EXAMPLE OF USAGE
201211

202212
createdb ltreetest
@@ -416,6 +426,11 @@ appreciate your input. So far, below some (rather obvious) results:
416426

417427
CHANGES
418428

429+
July 31, 2002
430+
Now works on 64-bit platforms.
431+
Added function lca - lowest common ancestor
432+
Version for 7.2 is distributed as separate package -
433+
http://www.sai.msu.su/~megera/postgres/gist/ltree/ltree-7.2.tar.gz
419434
July 13, 2002
420435
Initial release.
421436

‎contrib/ltree/_ltree_op.c

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,8 @@ Datum _ltree_extract_risparent(PG_FUNCTION_ARGS);
2828
Datum _ltq_extract_regex(PG_FUNCTION_ARGS);
2929
Datum _ltxtq_extract_exec(PG_FUNCTION_ARGS);
3030

31+
PG_FUNCTION_INFO_V1(_lca);
32+
Datum _lca(PG_FUNCTION_ARGS);
3133

3234
typedef Datum (*PGCALL2)(PG_FUNCTION_ARGS);
3335
#define NEXTVAL(x) ( (ltree*)( (char*)(x) + INTALIGN( VARSIZE(x) ) ) )
@@ -210,3 +212,27 @@ _ltxtq_extract_exec(PG_FUNCTION_ARGS) {
210212
PG_RETURN_POINTER(item);
211213
}
212214

215+
Datum
216+
_lca(PG_FUNCTION_ARGS) {
217+
ArrayType *la = (ArrayType *)DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(0)));
218+
int num=ArrayGetNItems( ARR_NDIM(la), ARR_DIMS(la));
219+
ltree *item = (ltree*)ARR_DATA_PTR(la);
220+
ltree **a,*res;
221+
222+
a=(ltree**)palloc( sizeof(ltree*) * num );
223+
while( num>0 ) {
224+
num--;
225+
a[num] = item;
226+
item = NEXTVAL(item);
227+
}
228+
res = lca_inner(a, ArrayGetNItems( ARR_NDIM(la), ARR_DIMS(la)));
229+
pfree(a);
230+
231+
PG_FREE_IF_COPY(la,0);
232+
233+
if ( res )
234+
PG_RETURN_POINTER(res);
235+
else
236+
PG_RETURN_NULL();
237+
}
238+

‎contrib/ltree/ltree.h

Lines changed: 17 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -12,16 +12,16 @@ typedef struct {
1212
} ltree_level;
1313

1414
#define LEVEL_HDRSIZE (sizeof(uint8))
15-
#define LEVEL_NEXT(x) ( (ltree_level*)( ((char*)(x)) + ((ltree_level*)(x))->len + LEVEL_HDRSIZE ) )
15+
#define LEVEL_NEXT(x) ( (ltree_level*)( ((char*)(x)) + MAXALIGN(((ltree_level*)(x))->len + LEVEL_HDRSIZE) ) )
1616

1717
typedef struct {
1818
int32 len;
1919
uint16 numlevel;
2020
char data[1];
2121
} ltree;
2222

23-
#define LTREE_HDRSIZE ( sizeof(int32) + sizeof(uint16) )
24-
#define LTREE_FIRST(x) ( (ltree_level*)( ((ltree*)(x))->data ) )
23+
#define LTREE_HDRSIZE MAXALIGN( sizeof(int32) + sizeof(uint16) )
24+
#define LTREE_FIRST(x) ( (ltree_level*)( ((char*)(x))+LTREE_HDRSIZE ) )
2525

2626

2727
/* lquery */
@@ -33,8 +33,8 @@ typedef struct {
3333
char name[1];
3434
} lquery_variant;
3535

36-
#define LVAR_HDRSIZE (sizeof(uint8)*2 + sizeof(int4))
37-
#define LVAR_NEXT(x) ( (lquery_variant*)( ((char*)(x)) + ((lquery_variant*)(x))->len + LVAR_HDRSIZE ) )
36+
#define LVAR_HDRSIZE MAXALIGN(sizeof(uint8)*2 + sizeof(int4))
37+
#define LVAR_NEXT(x) ( (lquery_variant*)( ((char*)(x)) + MAXALIGN(((lquery_variant*)(x))->len) + LVAR_HDRSIZE ) )
3838

3939
#define LVAR_ANYEND 0x01
4040
#define LVAR_INCASE 0x02
@@ -49,9 +49,9 @@ typedef struct {
4949
char variants[1];
5050
} lquery_level;
5151

52-
#define LQL_HDRSIZE ( sizeof(uint16)*5 )
53-
#define LQL_NEXT(x) ( (lquery_level*)( ((char*)(x)) + ((lquery_level*)(x))->totallen ) )
54-
#define LQL_FIRST(x) ( (lquery_variant*)( ((lquery_level*)(x))->variants ) )
52+
#define LQL_HDRSIZE MAXALIGN( sizeof(uint16)*5 )
53+
#define LQL_NEXT(x) ( (lquery_level*)( ((char*)(x)) + MAXALIGN(((lquery_level*)(x))->totallen) ) )
54+
#define LQL_FIRST(x) ( (lquery_variant*)( ((char*)(x))+LQL_HDRSIZE ) )
5555

5656
#define LQL_NOT 0x10
5757
#ifdef LOWER_NODE
@@ -69,8 +69,8 @@ typedef struct {
6969
char data[1];
7070
} lquery;
7171

72-
#define LQUERY_HDRSIZE ( sizeof(int32) + 3*sizeof(uint16) )
73-
#define LQUERY_FIRST(x) ( (lquery_level*)( ((lquery*)(x))->data ) )
72+
#define LQUERY_HDRSIZE MAXALIGN( sizeof(int32) + 3*sizeof(uint16) )
73+
#define LQUERY_FIRST(x) ( (lquery_level*)( ((char*)(x))+LQUERY_HDRSIZE ) )
7474

7575
#define LQUERY_HASNOT 0x01
7676

@@ -113,7 +113,7 @@ typedef struct
113113
char data[1];
114114
} ltxtquery;
115115

116-
#define HDRSIZEQT ( 2*sizeof(int4) )
116+
#define HDRSIZEQT MAXALIGN( 2*sizeof(int4) )
117117
#define COMPUTESIZE(size,lenofoperand) ( HDRSIZEQT + size * sizeof(ITEM) + lenofoperand )
118118
#define GETQUERY(x) (ITEM*)( (char*)(x)+HDRSIZEQT )
119119
#define GETOPERAND(x) ( (char*)GETQUERY(x) + ((ltxtquery*)x)->size * sizeof(ITEM) )
@@ -159,6 +159,7 @@ int ltree_compare(const ltree *a, const ltree *b);
159159
bool inner_isparent(const ltree *c, const ltree *p);
160160
bool compare_subnode( ltree_level *t, char *q, int len,
161161
int (*cmpptr)(const char *,const char *,size_t), bool anyend );
162+
ltree* lca_inner(ltree** a, int len);
162163

163164
#define PG_GETARG_LTREE(x) ((ltree*)DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(x))))
164165
#define PG_GETARG_LQUERY(x) ((lquery*)DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(x))))
@@ -212,14 +213,14 @@ typedef struct {
212213
#define LTG_ALLTRUE 0x02
213214
#define LTG_NORIGHT 0x04
214215

215-
#define LTG_HDRSIZE ( sizeof(int4) + sizeof(uint32) )
216-
#define LTG_SIGN(x) ( (BITVECP)( ((ltree_gist*)(x))->data ) )
217-
#define LTG_NODE(x) ( (ltree*)( ((ltree_gist*)(x))->data ) )
216+
#define LTG_HDRSIZE MAXALIGN( sizeof(int4) + sizeof(uint32) )
217+
#define LTG_SIGN(x) ( (BITVECP)( ((char*)(x))+LTG_HDRSIZE ) )
218+
#define LTG_NODE(x) ( (ltree*)( ((char*)(x))+LTG_HDRSIZE ) )
218219
#define LTG_ISONENODE(x) ( ((ltree_gist*)(x))->flag & LTG_ONENODE )
219220
#define LTG_ISALLTRUE(x) ( ((ltree_gist*)(x))->flag & LTG_ALLTRUE )
220221
#define LTG_ISNORIGHT(x) ( ((ltree_gist*)(x))->flag & LTG_NORIGHT )
221-
#define LTG_LNODE(x) ( (ltree*)( ( (char*)( ((ltree_gist*)(x))->data ) ) + ( LTG_ISALLTRUE(x) ? 0 : SIGLEN ) ) )
222-
#define LTG_RENODE(x) ( (ltree*)( ((char*)LTG_LNODE(x)) + LTG_LNODE(x)->len ) )
222+
#define LTG_LNODE(x) ( (ltree*)( ( ((char*)(x))+LTG_HDRSIZE ) + ( LTG_ISALLTRUE(x) ? 0 : SIGLEN ) ) )
223+
#define LTG_RENODE(x) ( (ltree*)( ((char*)LTG_LNODE(x)) + LTG_LNODE(x)->len) )
223224
#define LTG_RNODE(x) ( LTG_ISNORIGHT(x) ? LTG_LNODE(x) : LTG_RENODE(x) )
224225

225226
#define LTG_GETLNODE(x) ( LTG_ISONENODE(x) ? LTG_NODE(x) : LTG_LNODE(x) )

‎contrib/ltree/ltree.sql.in

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -117,6 +117,46 @@ RETURNS int4
117117
AS 'MODULE_PATHNAME'
118118
LANGUAGE 'c' with (isstrict,iscachable);
119119

120+
CREATE FUNCTION lca(_ltree)
121+
RETURNS ltree
122+
AS 'MODULE_PATHNAME','_lca'
123+
LANGUAGE 'c' with (isstrict,iscachable);
124+
125+
CREATE FUNCTION lca(ltree,ltree)
126+
RETURNS ltree
127+
AS 'MODULE_PATHNAME'
128+
LANGUAGE 'c' with (isstrict,iscachable);
129+
130+
CREATE FUNCTION lca(ltree,ltree,ltree)
131+
RETURNS ltree
132+
AS 'MODULE_PATHNAME'
133+
LANGUAGE 'c' with (isstrict,iscachable);
134+
135+
CREATE FUNCTION lca(ltree,ltree,ltree,ltree)
136+
RETURNS ltree
137+
AS 'MODULE_PATHNAME'
138+
LANGUAGE 'c' with (isstrict,iscachable);
139+
140+
CREATE FUNCTION lca(ltree,ltree,ltree,ltree,ltree)
141+
RETURNS ltree
142+
AS 'MODULE_PATHNAME'
143+
LANGUAGE 'c' with (isstrict,iscachable);
144+
145+
CREATE FUNCTION lca(ltree,ltree,ltree,ltree,ltree,ltree)
146+
RETURNS ltree
147+
AS 'MODULE_PATHNAME'
148+
LANGUAGE 'c' with (isstrict,iscachable);
149+
150+
CREATE FUNCTION lca(ltree,ltree,ltree,ltree,ltree,ltree,ltree)
151+
RETURNS ltree
152+
AS 'MODULE_PATHNAME'
153+
LANGUAGE 'c' with (isstrict,iscachable);
154+
155+
CREATE FUNCTION lca(ltree,ltree,ltree,ltree,ltree,ltree,ltree,ltree)
156+
RETURNS ltree
157+
AS 'MODULE_PATHNAME'
158+
LANGUAGE 'c' with (isstrict,iscachable);
159+
120160
CREATE FUNCTION ltree_isparent(ltree,ltree)
121161
RETURNS bool
122162
AS 'MODULE_PATHNAME'

‎contrib/ltree/ltree_io.c

Lines changed: 17 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -61,7 +61,7 @@ ltree_in(PG_FUNCTION_ARGS) {
6161
if ( lptr->len > 255 )
6262
elog(ERROR,"Name of level is too long (%d, must be < 256) in position %d",
6363
lptr->len, lptr->start - buf);
64-
totallen += lptr->len + LEVEL_HDRSIZE;
64+
totallen += MAXALIGN(lptr->len + LEVEL_HDRSIZE);
6565
lptr++;
6666
state = LTPRS_WAITNAME;
6767
} else if ( !ISALNUM(*ptr) )
@@ -76,7 +76,7 @@ ltree_in(PG_FUNCTION_ARGS) {
7676
if ( lptr->len > 255 )
7777
elog(ERROR,"Name of level is too long (%d, must be < 256) in position %d",
7878
lptr->len, lptr->start - buf);
79-
totallen += lptr->len + LEVEL_HDRSIZE;
79+
totallen += MAXALIGN(lptr->len + LEVEL_HDRSIZE);
8080
lptr++;
8181
} else if ( ! (state == LTPRS_WAITNAME && lptr == list) )
8282
elog(ERROR,"Unexpected end of line");
@@ -94,7 +94,6 @@ ltree_in(PG_FUNCTION_ARGS) {
9494
}
9595

9696
pfree(list);
97-
9897
PG_RETURN_POINTER(result);
9998
}
10099

@@ -134,7 +133,9 @@ ltree_out(PG_FUNCTION_ARGS) {
134133
#define LQPRS_WAITVAR 8
135134

136135

137-
#define GETVAR(x) ( *((nodeitem**)LQL_FIRST(x)) )
136+
#define GETVAR(x) ( *((nodeitem**)LQL_FIRST(x)) )
137+
#define ITEMSIZE MAXALIGN(LQL_HDRSIZE+sizeof(nodeitem*))
138+
#define NEXTLEV(x) ( (lquery_level*)( ((char*)(x)) + ITEMSIZE) )
138139

139140
Datum
140141
lquery_in(PG_FUNCTION_ARGS) {
@@ -159,8 +160,8 @@ lquery_in(PG_FUNCTION_ARGS) {
159160
}
160161

161162
num++;
162-
curqlevel = tmpql = (lquery_level*) palloc( ( LQL_HDRSIZE+sizeof(nodeitem*) )*(num) );
163-
memset((void*)tmpql,0, ( LQL_HDRSIZE+sizeof(nodeitem*) )*(num) );
163+
curqlevel = tmpql = (lquery_level*) palloc( ITEMSIZE*num );
164+
memset((void*)tmpql,0, ITEMSIZE*num );
164165
ptr=buf;
165166
while( *ptr ) {
166167
if ( state==LQPRS_WAITLEVEL ) {
@@ -224,7 +225,7 @@ lquery_in(PG_FUNCTION_ARGS) {
224225
elog(ERROR,"Name of level is too long (%d, must be < 256) in position %d",
225226
lptr->len, lptr->start - buf);
226227
state = LQPRS_WAITLEVEL;
227-
curqlevel++;
228+
curqlevel = NEXTLEV(curqlevel);
228229
} else if ( ISALNUM(*ptr) ) {
229230
if ( lptr->flag )
230231
UNCHAR;
@@ -236,7 +237,7 @@ lquery_in(PG_FUNCTION_ARGS) {
236237
} else if ( *ptr == '.' ) {
237238
curqlevel->low=0;
238239
curqlevel->high=0xffff;
239-
curqlevel++;
240+
curqlevel = NEXTLEV(curqlevel);
240241
state = LQPRS_WAITLEVEL;
241242
} else
242243
UNCHAR;
@@ -273,7 +274,7 @@ lquery_in(PG_FUNCTION_ARGS) {
273274
} else if ( state == LQPRS_WAITEND ) {
274275
if ( *ptr == '.' ) {
275276
state = LQPRS_WAITLEVEL;
276-
curqlevel++;
277+
curqlevel = NEXTLEV(curqlevel);
277278
} else
278279
UNCHAR;
279280
} else
@@ -300,19 +301,19 @@ lquery_in(PG_FUNCTION_ARGS) {
300301

301302
curqlevel = tmpql;
302303
totallen = LQUERY_HDRSIZE;
303-
while( curqlevel-tmpql < num ) {
304+
while( (char*)curqlevel-(char*)tmpql < num*ITEMSIZE ) {
304305
totallen += LQL_HDRSIZE;
305306
if ( curqlevel->numvar ) {
306307
lptr = GETVAR(curqlevel);
307308
while( lptr-GETVAR(curqlevel) < curqlevel->numvar ) {
308-
totallen += LVAR_HDRSIZE + lptr->len;
309+
totallen += MAXALIGN(LVAR_HDRSIZE + lptr->len);
309310
lptr++;
310311
}
311312
} else if ( curqlevel->low > curqlevel->high )
312313
elog(ERROR,"Low limit(%d) is greater than upper(%d)",curqlevel->low,curqlevel->high );
313-
curqlevel++;
314+
curqlevel = NEXTLEV(curqlevel);
314315
}
315-
316+
316317
result = (lquery*)palloc( totallen );
317318
result->len = totallen;
318319
result->numlevel = num;
@@ -322,14 +323,14 @@ lquery_in(PG_FUNCTION_ARGS) {
322323
result->flag |= LQUERY_HASNOT;
323324
cur = LQUERY_FIRST(result);
324325
curqlevel = tmpql;
325-
while( curqlevel-tmpql < num ) {
326+
while( (char*)curqlevel-(char*)tmpql < num*ITEMSIZE ) {
326327
memcpy(cur,curqlevel,LQL_HDRSIZE);
327328
cur->totallen=LQL_HDRSIZE;
328329
if ( curqlevel->numvar ) {
329330
lrptr = LQL_FIRST(cur);
330331
lptr = GETVAR(curqlevel);
331332
while( lptr-GETVAR(curqlevel) < curqlevel->numvar ) {
332-
cur->totallen += LVAR_HDRSIZE + lptr->len;
333+
cur->totallen += MAXALIGN(LVAR_HDRSIZE + lptr->len);
333334
lrptr->len = lptr->len;
334335
lrptr->flag = lptr->flag;
335336
lrptr->val = crc32_sz((uint8 *) lptr->start, lptr->len);
@@ -344,7 +345,7 @@ lquery_in(PG_FUNCTION_ARGS) {
344345
(result->firstgood)++;
345346
} else
346347
wasbad=true;
347-
curqlevel++;
348+
curqlevel = NEXTLEV(curqlevel);
348349
cur = LQL_NEXT(cur);
349350
}
350351

0 commit comments

Comments
 (0)