Ray: /ray/src/lib/tl/test-btree.cc Source File

00001 /*
00002  * lib/tl/test-btree.cc 
00003  * 
00004  * Test TLBtree implementation. Quick test hack, nothing special but it 
00005  * also demonstrates a possible use of a not purely static operator 
00006  * class (struct MYOP below). 
00007  * 
00008  * Copyright (c) 2004 by Wolfgang Wieser ] wwieser (a) gmx <*> de [ 
00009  * 
00010  * This file may be distributed and/or modified under the terms of the 
00011  * GNU General Public License version 2 as published by the Free Software 
00012  * Foundation. (See COPYING.GPL for details.)
00013  * 
00014  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
00015  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
00016  * 
00017  */
00018 
00019 #define TLIB_DEBUG_BTREE 1
00020 
00021 #if TLIB_DEBUG_BTREE
00022 #include <stdio.h>
00023 #endif
00024 
00025 #include "tlbtree.h"
00026 
00027 #include <stdio.h>
00028 
00029 
00030 char *prg_name="test-btree";
00031 
00032 
00033 template<class T>struct MYOP
00034 {
00035     int ini_calls;
00036     int clr_calls;
00037     
00038     MYOP()  {  ini_calls=0; clr_calls=0;  }
00039     ~MYOP() {}
00040     
00041     static inline bool lt(T const &a,T const &b)  {  return(a<b);   }
00042     static inline bool le(T const &a,T const &b)  {  return(a<=b);  }
00043     static inline bool gt(T const &a,T const &b)  {  return(a>b);   }
00044     static inline bool eq(T const &a,T const &b)  {  return(a==b);  }
00045     static inline bool ne(T const &a,T const &b)  {  return(a!=b);  }
00046     static inline T &ass(T &l,T const &r)  {  return(l=r);  }
00047     static const bool pdt=1;
00048     static inline _constfn_ size_t size()  {  return(sizeof(T));  }
00049     
00050     inline void ini(T *)  { ++ini_calls; }
00051     inline void ini(T *p,T const &a)  {  *p=a;  ++ini_calls;  }
00052     inline void clr(T *)  { ++clr_calls; }
00053     
00054     static inline void *alloc(size_t size)  {  return(ALLOC<char>(size));  }
00055     static inline void *free(void *ptr)  {  return(FREE(ptr));  }
00056 };
00057 
00058 
00059 int main()
00060 {
00061     fprintf(stderr,"Testing TLBtree... (size=%u (%u))\n",
00062         sizeof(TLBTree<int,MYOP<int> >),
00063         sizeof(MYOP<int>));
00064     
00065     int *ini_callsA;
00066     int *clr_callsA;
00067     int *ini_callsB;
00068     int *clr_callsB;
00069     int *ini_callsC;
00070     int *clr_callsC;
00071     int *ini_callsD;
00072     int *clr_callsD;
00073     
00074     do {
00075         TLBTree<int,MYOP<int> > A(10240);
00076         TLBTree<int,MYOP<int> > B(16);
00077         TLBTree<int,MYOP<int> > C(4);
00078         TLBTree<int,MYOP<int> > D(2);
00079 
00080         ini_callsA=&A.OP.ini_calls;
00081         clr_callsA=&A.OP.clr_calls;
00082         ini_callsB=&B.OP.ini_calls;
00083         clr_callsB=&B.OP.clr_calls;
00084         ini_callsC=&C.OP.ini_calls;
00085         clr_callsC=&C.OP.clr_calls;
00086         ini_callsD=&D.OP.ini_calls;
00087         clr_callsD=&D.OP.clr_calls;
00088         
00089         fprintf(stderr,"  Buildup");
00090         int nerr=0,i,modval=10000;
00091         for(i=0; i<5000; i++)
00092         {
00093             int val=rand()%modval;
00094             //fprintf(stderr,"---------<store=%d>----------\n",val);
00095             int rvA=A.store(val,/*allow_update=*/1);
00096             int rvB=B.store(val,/*allow_update=*/1);
00097             int rvC=C.store(val,/*allow_update=*/1);
00098             int rvD=D.store(val,/*allow_update=*/1);
00099             /*D.DumpTree(stderr);
00100             fprintf(stderr,"D: nelem=%d; ini/clr=(%d,%d,%d)\n",
00101                 D.CountElements(),ini_callsD,clr_callsD,ini_callsD-clr_callsD);*/
00102             if(rvA!=rvB || rvA!=rvC || rvA!=rvD)
00103             {
00104                 fprintf(stderr,"OOPS: store(%d): %d %d %d %d\n",
00105                     val,rvA,rvB,rvC,rvD);
00106                 ++nerr;  return(1);
00107             }
00108             
00109             val=rand()%modval;
00110             //D.DumpTree(stderr);
00111             //fprintf(stderr,"---------<remove=%d>----------\n",val);
00112             rvA=A.remove(val);
00113             rvB=B.remove(val);
00114             rvC=C.remove(val);
00115             rvD=D.remove(val);
00116             /*D.DumpTree(stderr);
00117             fprintf(stderr,"D: nelem=%d; ini/clr=(%d,%d,%d)\n",
00118                 D.CountElements(),ini_callsD,clr_callsD,ini_callsD-clr_callsD);*/
00119             if(rvA!=rvB || rvA!=rvC || rvA!=rvD)
00120             {
00121                 fprintf(stderr,"OOPS: remove(%d): %d %d %d %d\n",
00122                     val,rvA,rvB,rvC,rvD);
00123                 ++nerr;  return(1);
00124             }
00125             
00126             #if TLIB_DEBUG_BTREE
00127             int nerrA=A.CheckTree();
00128             int nerrB=B.CheckTree();
00129             int nerrC=C.CheckTree();
00130             int nerrD=D.CheckTree();
00131             if(nerrA || nerrB || nerrC || nerrD)
00132             {
00133                 fprintf(stderr,"OOPS: check=%d,%d,%d,%d\n",
00134                     nerrA,nerrB,nerrC,nerrD);
00135                 ++nerr;  return(1);
00136             }
00137             #endif
00138             
00139             if(!(i%100))
00140             {  fprintf(stderr,".");  }
00141         }
00142         fprintf(stderr,"%d (%d)\n",D.CountElements(),D.CountNodes());
00143         
00144         fprintf(stderr,"  Lookup");
00145         for(int j=0; j<10000; j++)
00146         {
00147             int val=rand()%(modval+100)-50;
00148             int *pA,*nA,*pB,*nB,*pC,*nC,*pD,*nD;
00149             int *rvA=A.SearchNeighbours(val,&pA,&nA);
00150             int *rvB=B.SearchNeighbours(val,&pB,&nB);
00151             int *rvC=C.SearchNeighbours(val,&pC,&nC);
00152             int *rvD=D.SearchNeighbours(val,&pD,&nD);
00153             if(!rvA!=!rvB || !rvA!=!rvC || !rvA!=!rvD || 
00154                !pA!=!pB || !pA!=!pC || !pA!=!pD || 
00155                !nA!=!nB || !nA!=!nC || !nA!=!nD )
00156             {
00157                 fprintf(stderr,
00158                     "OOPS: neigh=%d,%d,%d,%d; %p,%p,%p,%p; %p,%p,%p,%p *****\n",
00159                     rvA,rvB,rvC,rvD,pA,pB,pC,pD,nA,nB,nC,nD);
00160                 ++nerr;  return(1);
00161             }
00162             if((pA && (*pA!=*pB || *pA!=*pC || *pA!=*pD)) || 
00163                (nA && (*nA!=*nB || *nA!=*nC || *nA!=*nD)) || 
00164                (rvA && (*rvA!=*rvB || *rvA!=*rvC || *rvA!=*rvD)) )
00165             {
00166                 fprintf(stderr,"OOPS: neigh2(%d)=%d/%d/%d, %d/%d/%d, "
00167                     "%d/%d/%d, %d/%d/%d\n",
00168                     val,
00169                     pA ? *pA : 0,rvA ? *rvA : 0,nA ? *nA : 0,
00170                     pB ? *pB : 0,rvB ? *rvB : 0,nB ? *nB : 0,
00171                     pC ? *pC : 0,rvC ? *rvC : 0,nC ? *nC : 0,
00172                     pD ? *pD : 0,rvD ? *rvD : 0,nD ? *nD : 0);
00173                 #if TLIB_DEBUG_BTREE
00174                 D.DumpTree(stdout);
00175                 #endif
00176                 ++nerr;  return(1);
00177             }
00178             
00179             if(rvA && *rvA!=val)
00180             {
00181                 fprintf(stderr,"OOPS: neigh(%d): found=%d,%d,%d,%d\n",
00182                     val,*rvA,*rvB,*rvC,*rvD);
00183                 ++nerr;  return(1);
00184             }
00185             
00186             if(rvA)
00187             {
00188                 int *fA=A.search(val);
00189                 int *fB=B.search(val);
00190                 int *fC=C.search(val);
00191                 int *fD=D.search(val);
00192                 if(!fA || !fB || !fC || !fD)
00193                 {
00194                     fprintf(stderr,"OOPS: find(%d)=%p,%p,%p,%p\n",
00195                         fA,fB,fC,fD);
00196                     ++nerr;  return(1);
00197                 }
00198                 if(*fA!=val || *fB!=val || *fC!=val || *fD!=val)
00199                 {
00200                     fprintf(stderr,"OOPS: find(%d)=%d,%d,%d,%d\n",
00201                         *fA,*fB,*fC,*fD);
00202                     ++nerr;  return(1);
00203                 }
00204             }
00205             
00206             if(!(j%500))
00207             {  fprintf(stderr,".");  }
00208         }
00209         fprintf(stderr,"\n");
00210         
00211         fprintf(stderr,"  Remove");
00212         for(;;i++)
00213         {
00214             int val=rand()%modval;
00215             //D.DumpTree(stderr);
00216             //fprintf(stderr,"---------<remove=%d>----------\n",val);
00217             int rvA=A.remove(val);
00218             int rvB=B.remove(val);
00219             int rvC=C.remove(val);
00220             int rvD=D.remove(val);
00221             /*D.DumpTree(stderr);
00222             fprintf(stderr,"D: nelem=%d; ini/clr=(%d,%d,%d)\n",
00223                 D.CountElements(),ini_callsD,clr_callsD,ini_callsD-clr_callsD);*/
00224             if(rvA!=rvB || rvA!=rvC || rvA!=rvD)
00225             {
00226                 fprintf(stderr,"OOPS: remove(%d): %d %d %d %d\n",
00227                     val,rvA,rvB,rvC,rvD);
00228                 ++nerr;  return(1);
00229             }
00230             
00231             #if TLIB_DEBUG_BTREE
00232             if(!rvA || !(i%100))
00233             {
00234                 int nerrA=A.CheckTree();
00235                 int nerrB=B.CheckTree();
00236                 int nerrC=C.CheckTree();
00237                 int nerrD=D.CheckTree();
00238                 if(nerrA || nerrB || nerrC || nerrD)
00239                 {
00240                     fprintf(stderr,"OOPS: check=%d,%d,%d,%d\n",
00241                         nerrA,nerrB,nerrC,nerrD);
00242                     ++nerr;  return(1);
00243                 }
00244             }
00245             #endif
00246             
00247             if(!(i%2000))
00248             {  fprintf(stderr,".");  }
00249             
00250             if(A.IsEmpty()) break;
00251         }
00252         fprintf(stderr,"%d (%d)\n",D.CountElements(),D.CountNodes());
00253         
00254         fprintf(stderr,"  nelem=%d,%d,%d,%d\n  "
00255             "ini/clr=A(%d,%d,%d),B(%d,%d,%d),C(%d,%d,%d),D(%d,%d,%d)\n",
00256             A.CountElements(),B.CountElements(),C.CountElements(),
00257             D.CountElements(),
00258             *ini_callsA,*clr_callsA,*ini_callsA-*clr_callsA,
00259             *ini_callsB,*clr_callsB,*ini_callsB-*clr_callsB,
00260             *ini_callsC,*clr_callsC,*ini_callsC-*clr_callsC,
00261             *ini_callsD,*clr_callsD,*ini_callsD-*clr_callsD );
00262     } while(0);
00263     
00264     fprintf(stderr,"  A: ini_calls=%d, clr_calls=%d, diff=%d\n",
00265         *ini_callsA,*clr_callsA,*ini_callsA-*clr_callsA);
00266     fprintf(stderr,"  B: ini_calls=%d, clr_calls=%d, diff=%d\n",
00267         *ini_callsB,*clr_callsB,*ini_callsB-*clr_callsB);
00268     fprintf(stderr,"  C: ini_calls=%d, clr_calls=%d, diff=%d\n",
00269         *ini_callsC,*clr_callsC,*ini_callsC-*clr_callsC);
00270     fprintf(stderr,"  D: ini_calls=%d, clr_calls=%d, diff=%d\n",
00271         *ini_callsD,*clr_callsD,*ini_callsD-*clr_callsD);
00272     
00273     if(*ini_callsA-*clr_callsA || 
00274        *ini_callsB-*clr_callsB || 
00275        *ini_callsC-*clr_callsC || 
00276        *ini_callsD-*clr_callsD )
00277     {  return(1);  }
00278     
00279     // Allocation debugging: 
00280     LMallocUsage lmu;
00281     LMallocGetUsage(&lmu);
00282     fprintf(stderr,"%s: %sAlloc: %u bytes in %d chunks; Peak: %u by,%d chks; "
00283         "(%u/%u/%u)%s\n",
00284         prg_name,
00285         lmu.curr_used ? "*** " : "",
00286         lmu.curr_used,lmu.used_chunks,lmu.max_used,lmu.max_used_chunks,
00287         lmu.malloc_calls,lmu.realloc_calls,lmu.free_calls,
00288         lmu.curr_used ? " ***" : "");
00289     if(lmu.curr_used)  return(1);
00290     
00291     fprintf(stderr,"TLBTree test SUCCESSFUL.\n");
00292     return(0);
00293 }