Subject: R-tree bug, patches included.

From: "Schenkelaars.V.F" <[email-masked]>
Date: Fri, 11 Sep 92 16:37:36 MET DST

Dear Postgres Group,

During my attempt to add a new access method to Postgres, I encountered a
strange decision of the R-tree implementor. The rt_box_size function does
return a int type. This is very strange since the box coordinates are
doubles. The return type can never have the required accuracy. In my
opinion this function should at least return a float. I`m aware that
floats are returned by reference rather than by value.

Since my access method "The Reactive-tree" is quite similar to the
R-tree I needed the size function in the same way. I have changed the
int type into a float pointer type. This change has to be done in
two functions. I have made these changes and tested them. It works ok on
a sparc station. Below are the patches for fixing this bug.

Mike,

I`ve almost finished the Reactive-tree. I'll let you know when it
is "bullet-proof". I`m intending to write a "How to add a new
access method to Postgres" manual. Since it seems that there
are more people strugling with this material, and since it looks as if 
I am the only one outside the Postgres group who has (almost) managed to
add a new access method, It seems a good idea to me to share my 
experience with other users. Of course this manual shall be available for
all Postgres users. The same counts for the Reactive-tree code.

Greetings,

     ____________________
 \  / . _   _  _   _  |
  \/ ( ( \ (_ (-' ( \ |

P.S.
  
Postgres has proven to be open, although one will need a good guide
to explore some of it's mazes.
--------------------------------------------------------------------------------
Vincent F. Schenkelaars				|
Company: FEL-TNO                                | Private:
Email  : [email-masked]	|
address: Oude Waalsdorperweg 63			| Groenhovenstraat 12
         Postbus 96864				|
         2509 JG  Den Haag			| 2311 BT  Leiden
         The Netherlands			| The Netherlands
Phone  : Holland 070-3264221			| Holland 071-125576
Fax    : Holland 070-3280961			|
--------------------------------------------------------------------------------

rtree.c patch
---------- CUT HERE -------------------------
*** rtree.c	Fri Sep 11 14:57:11 1992
--- rtree.c.fixed	Fri Sep 11 15:16:44 1992
***************
*** 313,319 ****
  {
      char *oldud;
      Page p;
!     int old_size, newd_size;
      RegProcedure union_proc, size_proc;
      Buffer b;
  
--- 313,319 ----
  {
      char *oldud;
      Page p;
!     float *old_size, *newd_size;
      RegProcedure union_proc, size_proc;
      Buffer b;
  
***************
*** 329,341 ****
      oldud = (char *) PageGetItem(p, PageGetItemId(p, stk->rts_child));
      oldud += sizeof(IndexTupleData);
  
!     old_size = (int) fmgr(size_proc, oldud);
      datum = (char *) fmgr(union_proc, oldud, datum);
  
!     newd_size = (int) fmgr(size_proc, datum);
  
      /* XXX assume constant-size data items here */
!     if (newd_size != old_size) {
  	bcopy(datum, oldud, att_size);
  	WriteBuffer(b);
  	rttighten(r, stk->rts_parent, datum, att_size);
--- 329,341 ----
      oldud = (char *) PageGetItem(p, PageGetItemId(p, stk->rts_child));
      oldud += sizeof(IndexTupleData);
  
!     old_size = (float *) fmgr(size_proc, oldud);
      datum = (char *) fmgr(union_proc, oldud, datum);
  
!     newd_size = (float *) fmgr(size_proc, datum);
  
      /* XXX assume constant-size data items here */
!     if (*newd_size != *old_size) {
  	bcopy(datum, oldud, att_size);
  	WriteBuffer(b);
  	rttighten(r, stk->rts_parent, datum, att_size);
***************
*** 740,753 ****
      int i;
      char *ud, *id;
      char *datum;
!     int isize, usize, dsize;
!     int which, which_grow;
      RegProcedure union_proc, size_proc;
  
      union_proc = index_getprocid(r, 1, RT_UNION_PROC);
      size_proc = index_getprocid(r, 1, RT_SIZE_PROC);
      id = ((char *) it) + sizeof(IndexTupleData);
!     isize = (int) fmgr(size_proc, id);
      maxoff = PageGetMaxOffsetIndex(p);
      which_grow = -1;
      which = -1;
--- 740,753 ----
      int i;
      char *ud, *id;
      char *datum;
!     float *isize, *usize, *dsize, which_grow;
!     int which;
      RegProcedure union_proc, size_proc;
  
      union_proc = index_getprocid(r, 1, RT_UNION_PROC);
      size_proc = index_getprocid(r, 1, RT_SIZE_PROC);
      id = ((char *) it) + sizeof(IndexTupleData);
!     isize = (float *) fmgr(size_proc, id);
      maxoff = PageGetMaxOffsetIndex(p);
      which_grow = -1;
      which = -1;
***************
*** 755,771 ****
      for (i = 0; i <= maxoff; i++) {
  	datum = (char *) PageGetItem(p, PageGetItemId(p, i));
  	datum += sizeof(IndexTupleData);
! 	dsize = (int) fmgr(size_proc, datum);
  	ud = (char *) fmgr(union_proc, datum, id);
! 	usize = (int) fmgr(size_proc, ud);
  	pfree(ud);
! 	if (which_grow < 0 || usize - dsize < which_grow) {
  	    which = i;
! 	    which_grow = usize - dsize;
  	    if (which_grow == 0)
  		break;
  	}
      }
      return (which);
  }
  
--- 755,774 ----
      for (i = 0; i <= maxoff; i++) {
  	datum = (char *) PageGetItem(p, PageGetItemId(p, i));
  	datum += sizeof(IndexTupleData);
! 	dsize = (float *) fmgr(size_proc, datum);
  	ud = (char *) fmgr(union_proc, datum, id);
! 	usize = (float *) fmgr(size_proc, ud);
  	pfree(ud);
! 	if (which_grow < 0 || *usize - *dsize < which_grow) {
  	    which = i;
! 	    which_grow = *usize - *dsize;
  	    if (which_grow == 0)
  		break;
  	}
      }
+     pfree(dsize);
+     pfree(usize);
+     pfree(isize);
      return (which);
  }
  
---------- CUT HERE -------------------------

rtproc.c patch
---------- CUT HERE -------------------------
-------------------------------------------------------------
*** rtproc.c	Fri Sep 11 15:18:36 1992
--- rtproc.c.fixed	Fri Sep 11 15:24:28 1992
***************
*** 52,67 ****
  	return (n);
  }
  
! int
  rt_box_size(a)
  	BOX *a;
  {
! 	int size;
  
  	if (a == (BOX *) NULL || a->xh <= a->xl || a->yh <= a->yl)
  		return (0);
  
! 	size = (int) (fabs(a->xh - a->xl) * fabs(a->yh - a->yl));
  
  	return (size);
  }
--- 52,68 ----
  	return (n);
  }
  
! float *
  rt_box_size(a)
  	BOX *a;
  {
! 	float *size;
  
+ 	size = (float *) palloc (sizeof(float));
  	if (a == (BOX *) NULL || a->xh <= a->xl || a->yh <= a->yl)
  		return (0);
  
! 	*size = (float) (fabs(a->xh - a->xl) * fabs(a->yh - a->yl));
  
  	return (size);
  }

---------- CUT HERE -------------------------