From 978c8c6d2f6fceb8ed043a9ad8b09b09a0794eb2 Mon Sep 17 00:00:00 2001 From: Bruce Momjian Date: Sun, 4 Aug 2002 05:02:50 +0000 Subject: [PATCH] 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 --- contrib/ltree/README.ltree | 27 ++++++++++--- contrib/ltree/_ltree_op.c | 26 +++++++++++++ contrib/ltree/ltree.h | 33 ++++++++-------- contrib/ltree/ltree.sql.in | 40 +++++++++++++++++++ contrib/ltree/ltree_io.c | 33 ++++++++-------- contrib/ltree/ltree_op.c | 78 ++++++++++++++++++++++++++++++++++++++ 6 files changed, 199 insertions(+), 38 deletions(-) diff --git a/contrib/ltree/README.ltree b/contrib/ltree/README.ltree index 568704b97f..b11a27bc30 100644 --- a/contrib/ltree/README.ltree +++ b/contrib/ltree/README.ltree @@ -4,7 +4,7 @@ ltree - is a PostgreSQL contrib module which contains implementation of data types, indexed access methods and queries for data organized as a tree-like structures. This module will works for PostgreSQL version 7.3. -(patch for 7.2 version is provided, see INSTALLATION) +(version for 7.2 version is available from http://www.sai.msu.su/~megera/postgres/gist/ltree/ltree-7.2.tar.gz) ------------------------------------------------------------------------------- All work was done by Teodor Sigaev (teodor@stack.net) and Oleg Bartunov (oleg@sai.msu.su). See http://www.sai.msu.su/~megera/postgres/gist for @@ -184,9 +184,21 @@ int4 nlevel nlevel -------- 3 - -Note, that arguments start, end, OFFSET, LEN have meaning of level of the node -! + Note, that arguments start, end, OFFSET, LEN have meaning of level of the + node ! + +ltree lca(ltree,ltree,...) (up to 8 arguments) + ltree lca(ltree[]) + Returns Lowest Common Ancestor (lca) + # select lca('1.2.2.3','1.2.3.4.5.6'); + lca + ----- + 1.2 + # select lca('{la.2.3,1.2.3.4.5.6}') is null; + ?column? + ---------- + f + INSTALLATION @@ -195,8 +207,6 @@ INSTALLATION make install make installcheck -for 7.2 one needs to apply patch ( patch < patch.72) before installation ! - EXAMPLE OF USAGE createdb ltreetest @@ -416,6 +426,11 @@ appreciate your input. So far, below some (rather obvious) results: 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 July 13, 2002 Initial release. diff --git a/contrib/ltree/_ltree_op.c b/contrib/ltree/_ltree_op.c index 3df2d962d4..cc7a16c27e 100644 --- a/contrib/ltree/_ltree_op.c +++ b/contrib/ltree/_ltree_op.c @@ -28,6 +28,8 @@ Datum _ltree_extract_risparent(PG_FUNCTION_ARGS); Datum _ltq_extract_regex(PG_FUNCTION_ARGS); Datum _ltxtq_extract_exec(PG_FUNCTION_ARGS); +PG_FUNCTION_INFO_V1(_lca); +Datum _lca(PG_FUNCTION_ARGS); typedef Datum (*PGCALL2)(PG_FUNCTION_ARGS); #define NEXTVAL(x) ( (ltree*)( (char*)(x) + INTALIGN( VARSIZE(x) ) ) ) @@ -210,3 +212,27 @@ _ltxtq_extract_exec(PG_FUNCTION_ARGS) { PG_RETURN_POINTER(item); } +Datum +_lca(PG_FUNCTION_ARGS) { + ArrayType *la = (ArrayType *)DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(0))); + int num=ArrayGetNItems( ARR_NDIM(la), ARR_DIMS(la)); + ltree *item = (ltree*)ARR_DATA_PTR(la); + ltree **a,*res; + + a=(ltree**)palloc( sizeof(ltree*) * num ); + while( num>0 ) { + num--; + a[num] = item; + item = NEXTVAL(item); + } + res = lca_inner(a, ArrayGetNItems( ARR_NDIM(la), ARR_DIMS(la))); + pfree(a); + + PG_FREE_IF_COPY(la,0); + + if ( res ) + PG_RETURN_POINTER(res); + else + PG_RETURN_NULL(); +} + diff --git a/contrib/ltree/ltree.h b/contrib/ltree/ltree.h index 750802d093..22134befaf 100644 --- a/contrib/ltree/ltree.h +++ b/contrib/ltree/ltree.h @@ -12,7 +12,7 @@ typedef struct { } ltree_level; #define LEVEL_HDRSIZE (sizeof(uint8)) -#define LEVEL_NEXT(x) ( (ltree_level*)( ((char*)(x)) + ((ltree_level*)(x))->len + LEVEL_HDRSIZE ) ) +#define LEVEL_NEXT(x) ( (ltree_level*)( ((char*)(x)) + MAXALIGN(((ltree_level*)(x))->len + LEVEL_HDRSIZE) ) ) typedef struct { int32 len; @@ -20,8 +20,8 @@ typedef struct { char data[1]; } ltree; -#define LTREE_HDRSIZE ( sizeof(int32) + sizeof(uint16) ) -#define LTREE_FIRST(x) ( (ltree_level*)( ((ltree*)(x))->data ) ) +#define LTREE_HDRSIZE MAXALIGN( sizeof(int32) + sizeof(uint16) ) +#define LTREE_FIRST(x) ( (ltree_level*)( ((char*)(x))+LTREE_HDRSIZE ) ) /* lquery */ @@ -33,8 +33,8 @@ typedef struct { char name[1]; } lquery_variant; -#define LVAR_HDRSIZE (sizeof(uint8)*2 + sizeof(int4)) -#define LVAR_NEXT(x) ( (lquery_variant*)( ((char*)(x)) + ((lquery_variant*)(x))->len + LVAR_HDRSIZE ) ) +#define LVAR_HDRSIZE MAXALIGN(sizeof(uint8)*2 + sizeof(int4)) +#define LVAR_NEXT(x) ( (lquery_variant*)( ((char*)(x)) + MAXALIGN(((lquery_variant*)(x))->len) + LVAR_HDRSIZE ) ) #define LVAR_ANYEND 0x01 #define LVAR_INCASE 0x02 @@ -49,9 +49,9 @@ typedef struct { char variants[1]; } lquery_level; -#define LQL_HDRSIZE ( sizeof(uint16)*5 ) -#define LQL_NEXT(x) ( (lquery_level*)( ((char*)(x)) + ((lquery_level*)(x))->totallen ) ) -#define LQL_FIRST(x) ( (lquery_variant*)( ((lquery_level*)(x))->variants ) ) +#define LQL_HDRSIZE MAXALIGN( sizeof(uint16)*5 ) +#define LQL_NEXT(x) ( (lquery_level*)( ((char*)(x)) + MAXALIGN(((lquery_level*)(x))->totallen) ) ) +#define LQL_FIRST(x) ( (lquery_variant*)( ((char*)(x))+LQL_HDRSIZE ) ) #define LQL_NOT 0x10 #ifdef LOWER_NODE @@ -69,8 +69,8 @@ typedef struct { char data[1]; } lquery; -#define LQUERY_HDRSIZE ( sizeof(int32) + 3*sizeof(uint16) ) -#define LQUERY_FIRST(x) ( (lquery_level*)( ((lquery*)(x))->data ) ) +#define LQUERY_HDRSIZE MAXALIGN( sizeof(int32) + 3*sizeof(uint16) ) +#define LQUERY_FIRST(x) ( (lquery_level*)( ((char*)(x))+LQUERY_HDRSIZE ) ) #define LQUERY_HASNOT 0x01 @@ -113,7 +113,7 @@ typedef struct char data[1]; } ltxtquery; -#define HDRSIZEQT ( 2*sizeof(int4) ) +#define HDRSIZEQT MAXALIGN( 2*sizeof(int4) ) #define COMPUTESIZE(size,lenofoperand) ( HDRSIZEQT + size * sizeof(ITEM) + lenofoperand ) #define GETQUERY(x) (ITEM*)( (char*)(x)+HDRSIZEQT ) #define GETOPERAND(x) ( (char*)GETQUERY(x) + ((ltxtquery*)x)->size * sizeof(ITEM) ) @@ -159,6 +159,7 @@ int ltree_compare(const ltree *a, const ltree *b); bool inner_isparent(const ltree *c, const ltree *p); bool compare_subnode( ltree_level *t, char *q, int len, int (*cmpptr)(const char *,const char *,size_t), bool anyend ); +ltree* lca_inner(ltree** a, int len); #define PG_GETARG_LTREE(x) ((ltree*)DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(x)))) #define PG_GETARG_LQUERY(x) ((lquery*)DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(x)))) @@ -212,14 +213,14 @@ typedef struct { #define LTG_ALLTRUE 0x02 #define LTG_NORIGHT 0x04 -#define LTG_HDRSIZE ( sizeof(int4) + sizeof(uint32) ) -#define LTG_SIGN(x) ( (BITVECP)( ((ltree_gist*)(x))->data ) ) -#define LTG_NODE(x) ( (ltree*)( ((ltree_gist*)(x))->data ) ) +#define LTG_HDRSIZE MAXALIGN( sizeof(int4) + sizeof(uint32) ) +#define LTG_SIGN(x) ( (BITVECP)( ((char*)(x))+LTG_HDRSIZE ) ) +#define LTG_NODE(x) ( (ltree*)( ((char*)(x))+LTG_HDRSIZE ) ) #define LTG_ISONENODE(x) ( ((ltree_gist*)(x))->flag & LTG_ONENODE ) #define LTG_ISALLTRUE(x) ( ((ltree_gist*)(x))->flag & LTG_ALLTRUE ) #define LTG_ISNORIGHT(x) ( ((ltree_gist*)(x))->flag & LTG_NORIGHT ) -#define LTG_LNODE(x) ( (ltree*)( ( (char*)( ((ltree_gist*)(x))->data ) ) + ( LTG_ISALLTRUE(x) ? 0 : SIGLEN ) ) ) -#define LTG_RENODE(x) ( (ltree*)( ((char*)LTG_LNODE(x)) + LTG_LNODE(x)->len ) ) +#define LTG_LNODE(x) ( (ltree*)( ( ((char*)(x))+LTG_HDRSIZE ) + ( LTG_ISALLTRUE(x) ? 0 : SIGLEN ) ) ) +#define LTG_RENODE(x) ( (ltree*)( ((char*)LTG_LNODE(x)) + LTG_LNODE(x)->len) ) #define LTG_RNODE(x) ( LTG_ISNORIGHT(x) ? LTG_LNODE(x) : LTG_RENODE(x) ) #define LTG_GETLNODE(x) ( LTG_ISONENODE(x) ? LTG_NODE(x) : LTG_LNODE(x) ) diff --git a/contrib/ltree/ltree.sql.in b/contrib/ltree/ltree.sql.in index abc6d46f52..4e0f52ea1f 100644 --- a/contrib/ltree/ltree.sql.in +++ b/contrib/ltree/ltree.sql.in @@ -117,6 +117,46 @@ RETURNS int4 AS 'MODULE_PATHNAME' LANGUAGE 'c' with (isstrict,iscachable); +CREATE FUNCTION lca(_ltree) +RETURNS ltree +AS 'MODULE_PATHNAME','_lca' +LANGUAGE 'c' with (isstrict,iscachable); + +CREATE FUNCTION lca(ltree,ltree) +RETURNS ltree +AS 'MODULE_PATHNAME' +LANGUAGE 'c' with (isstrict,iscachable); + +CREATE FUNCTION lca(ltree,ltree,ltree) +RETURNS ltree +AS 'MODULE_PATHNAME' +LANGUAGE 'c' with (isstrict,iscachable); + +CREATE FUNCTION lca(ltree,ltree,ltree,ltree) +RETURNS ltree +AS 'MODULE_PATHNAME' +LANGUAGE 'c' with (isstrict,iscachable); + +CREATE FUNCTION lca(ltree,ltree,ltree,ltree,ltree) +RETURNS ltree +AS 'MODULE_PATHNAME' +LANGUAGE 'c' with (isstrict,iscachable); + +CREATE FUNCTION lca(ltree,ltree,ltree,ltree,ltree,ltree) +RETURNS ltree +AS 'MODULE_PATHNAME' +LANGUAGE 'c' with (isstrict,iscachable); + +CREATE FUNCTION lca(ltree,ltree,ltree,ltree,ltree,ltree,ltree) +RETURNS ltree +AS 'MODULE_PATHNAME' +LANGUAGE 'c' with (isstrict,iscachable); + +CREATE FUNCTION lca(ltree,ltree,ltree,ltree,ltree,ltree,ltree,ltree) +RETURNS ltree +AS 'MODULE_PATHNAME' +LANGUAGE 'c' with (isstrict,iscachable); + CREATE FUNCTION ltree_isparent(ltree,ltree) RETURNS bool AS 'MODULE_PATHNAME' diff --git a/contrib/ltree/ltree_io.c b/contrib/ltree/ltree_io.c index 845e61eaa7..0315dca06b 100644 --- a/contrib/ltree/ltree_io.c +++ b/contrib/ltree/ltree_io.c @@ -61,7 +61,7 @@ ltree_in(PG_FUNCTION_ARGS) { if ( lptr->len > 255 ) elog(ERROR,"Name of level is too long (%d, must be < 256) in position %d", lptr->len, lptr->start - buf); - totallen += lptr->len + LEVEL_HDRSIZE; + totallen += MAXALIGN(lptr->len + LEVEL_HDRSIZE); lptr++; state = LTPRS_WAITNAME; } else if ( !ISALNUM(*ptr) ) @@ -76,7 +76,7 @@ ltree_in(PG_FUNCTION_ARGS) { if ( lptr->len > 255 ) elog(ERROR,"Name of level is too long (%d, must be < 256) in position %d", lptr->len, lptr->start - buf); - totallen += lptr->len + LEVEL_HDRSIZE; + totallen += MAXALIGN(lptr->len + LEVEL_HDRSIZE); lptr++; } else if ( ! (state == LTPRS_WAITNAME && lptr == list) ) elog(ERROR,"Unexpected end of line"); @@ -94,7 +94,6 @@ ltree_in(PG_FUNCTION_ARGS) { } pfree(list); - PG_RETURN_POINTER(result); } @@ -134,7 +133,9 @@ ltree_out(PG_FUNCTION_ARGS) { #define LQPRS_WAITVAR 8 -#define GETVAR(x) ( *((nodeitem**)LQL_FIRST(x)) ) +#define GETVAR(x) ( *((nodeitem**)LQL_FIRST(x)) ) +#define ITEMSIZE MAXALIGN(LQL_HDRSIZE+sizeof(nodeitem*)) +#define NEXTLEV(x) ( (lquery_level*)( ((char*)(x)) + ITEMSIZE) ) Datum lquery_in(PG_FUNCTION_ARGS) { @@ -159,8 +160,8 @@ lquery_in(PG_FUNCTION_ARGS) { } num++; - curqlevel = tmpql = (lquery_level*) palloc( ( LQL_HDRSIZE+sizeof(nodeitem*) )*(num) ); - memset((void*)tmpql,0, ( LQL_HDRSIZE+sizeof(nodeitem*) )*(num) ); + curqlevel = tmpql = (lquery_level*) palloc( ITEMSIZE*num ); + memset((void*)tmpql,0, ITEMSIZE*num ); ptr=buf; while( *ptr ) { if ( state==LQPRS_WAITLEVEL ) { @@ -224,7 +225,7 @@ lquery_in(PG_FUNCTION_ARGS) { elog(ERROR,"Name of level is too long (%d, must be < 256) in position %d", lptr->len, lptr->start - buf); state = LQPRS_WAITLEVEL; - curqlevel++; + curqlevel = NEXTLEV(curqlevel); } else if ( ISALNUM(*ptr) ) { if ( lptr->flag ) UNCHAR; @@ -236,7 +237,7 @@ lquery_in(PG_FUNCTION_ARGS) { } else if ( *ptr == '.' ) { curqlevel->low=0; curqlevel->high=0xffff; - curqlevel++; + curqlevel = NEXTLEV(curqlevel); state = LQPRS_WAITLEVEL; } else UNCHAR; @@ -273,7 +274,7 @@ lquery_in(PG_FUNCTION_ARGS) { } else if ( state == LQPRS_WAITEND ) { if ( *ptr == '.' ) { state = LQPRS_WAITLEVEL; - curqlevel++; + curqlevel = NEXTLEV(curqlevel); } else UNCHAR; } else @@ -300,19 +301,19 @@ lquery_in(PG_FUNCTION_ARGS) { curqlevel = tmpql; totallen = LQUERY_HDRSIZE; - while( curqlevel-tmpql < num ) { + while( (char*)curqlevel-(char*)tmpql < num*ITEMSIZE ) { totallen += LQL_HDRSIZE; if ( curqlevel->numvar ) { lptr = GETVAR(curqlevel); while( lptr-GETVAR(curqlevel) < curqlevel->numvar ) { - totallen += LVAR_HDRSIZE + lptr->len; + totallen += MAXALIGN(LVAR_HDRSIZE + lptr->len); lptr++; } } else if ( curqlevel->low > curqlevel->high ) elog(ERROR,"Low limit(%d) is greater than upper(%d)",curqlevel->low,curqlevel->high ); - curqlevel++; + curqlevel = NEXTLEV(curqlevel); } - + result = (lquery*)palloc( totallen ); result->len = totallen; result->numlevel = num; @@ -322,14 +323,14 @@ lquery_in(PG_FUNCTION_ARGS) { result->flag |= LQUERY_HASNOT; cur = LQUERY_FIRST(result); curqlevel = tmpql; - while( curqlevel-tmpql < num ) { + while( (char*)curqlevel-(char*)tmpql < num*ITEMSIZE ) { memcpy(cur,curqlevel,LQL_HDRSIZE); cur->totallen=LQL_HDRSIZE; if ( curqlevel->numvar ) { lrptr = LQL_FIRST(cur); lptr = GETVAR(curqlevel); while( lptr-GETVAR(curqlevel) < curqlevel->numvar ) { - cur->totallen += LVAR_HDRSIZE + lptr->len; + cur->totallen += MAXALIGN(LVAR_HDRSIZE + lptr->len); lrptr->len = lptr->len; lrptr->flag = lptr->flag; lrptr->val = crc32_sz((uint8 *) lptr->start, lptr->len); @@ -344,7 +345,7 @@ lquery_in(PG_FUNCTION_ARGS) { (result->firstgood)++; } else wasbad=true; - curqlevel++; + curqlevel = NEXTLEV(curqlevel); cur = LQL_NEXT(cur); } diff --git a/contrib/ltree/ltree_op.c b/contrib/ltree/ltree_op.c index 6d504713e5..b954908b6c 100644 --- a/contrib/ltree/ltree_op.c +++ b/contrib/ltree/ltree_op.c @@ -22,6 +22,7 @@ PG_FUNCTION_INFO_V1(subpath); PG_FUNCTION_INFO_V1(ltree_addltree); PG_FUNCTION_INFO_V1(ltree_addtext); PG_FUNCTION_INFO_V1(ltree_textadd); +PG_FUNCTION_INFO_V1(lca); Datum ltree_cmp(PG_FUNCTION_ARGS); Datum ltree_lt(PG_FUNCTION_ARGS); Datum ltree_le(PG_FUNCTION_ARGS); @@ -35,6 +36,7 @@ Datum subpath(PG_FUNCTION_ARGS); Datum ltree_addltree(PG_FUNCTION_ARGS); Datum ltree_addtext(PG_FUNCTION_ARGS); Datum ltree_textadd(PG_FUNCTION_ARGS); +Datum lca(PG_FUNCTION_ARGS); int ltree_compare(const ltree *a, const ltree *b) { @@ -308,3 +310,79 @@ ltree_textadd(PG_FUNCTION_ARGS) { PG_FREE_IF_COPY(b,0); PG_RETURN_POINTER(r); } + +ltree* +lca_inner(ltree** a, int len) { + int tmp,num=( (*a)->numlevel ) ? (*a)->numlevel-1 : 0; + ltree **ptr=a+1; + int i,reslen=LTREE_HDRSIZE; + ltree_level *l1, *l2; + ltree *res; + + + if ( (*a)->numlevel == 0 ) + return NULL; + + while( ptr-a < len ) { + if ( (*ptr)->numlevel == 0 ) + return NULL; + else if ( (*ptr)->numlevel == 1 ) + num=0; + else { + l1 = LTREE_FIRST(*a); + l2 = LTREE_FIRST(*ptr); + tmp=num; num=0; + for(i=0;inumlevel-1); i++) { + if ( l1->len == l2->len && strncmp(l1->name,l2->name,l1->len) == 0 ) + num=i+1; + else + break; + l1=LEVEL_NEXT(l1); + l2=LEVEL_NEXT(l2); + } + } + ptr++; + } + + l1 = LTREE_FIRST(*a); + for(i=0;ilen + LEVEL_HDRSIZE); + l1=LEVEL_NEXT(l1); + } + + res=(ltree*)palloc( reslen ); + res->len = reslen; + res->numlevel = num; + + l1 = LTREE_FIRST(*a); + l2 = LTREE_FIRST(res); + + for(i=0;ilen + LEVEL_HDRSIZE)); + l1=LEVEL_NEXT(l1); + l2=LEVEL_NEXT(l2); + } + + return res; +} + +Datum +lca(PG_FUNCTION_ARGS) { + int i; + ltree **a,*res; + + a=(ltree**)palloc( sizeof(ltree*) * fcinfo->nargs ); + for(i=0;inargs;i++) + a[i] = PG_GETARG_LTREE(i); + res = lca_inner(a, (int) fcinfo->nargs); + for(i=0;inargs;i++) + PG_FREE_IF_COPY(a[i],i); + pfree(a); + + if ( res ) + PG_RETURN_POINTER(res); + else + PG_RETURN_NULL(); +} + + -- 2.40.0