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

00001 /*
00002  * lib/tl/test-heap.cc 
00003  * 
00004  * Test TLArrayHeap implementation. Based on test-btree.cc. 
00005  * 
00006  * Copyright (c) 2004 by Wolfgang Wieser ] wwieser (a) gmx <*> de [ 
00007  * 
00008  * This file may be distributed and/or modified under the terms of the 
00009  * GNU General Public License version 2 as published by the Free Software 
00010  * Foundation. (See COPYING.GPL for details.)
00011  * 
00012  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
00013  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
00014  * 
00015  */
00016 
00017 #include "tlarrayheap.h"
00018 
00019 #include <stdio.h>
00020 
00021 
00022 char *prg_name="test-heap";
00023 
00024 
00025 template<class T>struct MYOP
00026 {
00027     int ini_calls;
00028     int clr_calls;
00029     
00030     MYOP()  {  ini_calls=0; clr_calls=0;  }
00031     ~MYOP() {}
00032     
00033     static inline bool lt(T const &a,T const &b)  {  return(a<b);   }
00034     static inline bool le(T const &a,T const &b)  {  return(a<=b);  }
00035     static inline bool gt(T const &a,T const &b)  {  return(a>b);   }
00036     static inline bool ge(T const &a,T const &b)  {  return(a>=b);   }
00037     static inline bool eq(T const &a,T const &b)  {  return(a==b);  }
00038     static inline bool ne(T const &a,T const &b)  {  return(a!=b);  }
00039     static inline T &ass(T &l,T const &r)  {  return(l=r);  }
00040     static const bool pdt=1;
00041     static inline _constfn_ size_t size()  {  return(sizeof(T));  }
00042     
00043     inline void ini(T *)  { ++ini_calls; }
00044     inline void ini(T *p,T const &a)  {  *p=a;  ++ini_calls;  }
00045     inline void clr(T *)  { ++clr_calls; }
00046     
00047     static inline void *alloc(size_t size)  {  return(ALLOC<char>(size));  }
00048     static inline void *realloc(void *ptr,size_t size)
00049         {  return(REALLOC((char*)ptr,size));  }
00050     static inline void *free(void *ptr)  {  return(FREE(ptr));  }
00051 };
00052 
00053 
00054 int main()
00055 {
00056     fprintf(stderr,"Testing TLArrayHeap... (size=%u (%u))\n",
00057         sizeof(TLArrayHeap<int,MYOP<int> >),
00058         sizeof(MYOP<int>));
00059     
00060     int *ini_callsA;
00061     int *clr_callsA;
00062     int *ini_callsB;
00063     int *clr_callsB;
00064     
00065     do {
00066         TLArrayHeap<int,MYOP<int> > A;
00067         TLArrayHeap<int,MYOP<int> > B;
00068         
00069         ini_callsA=&A.OP.ini_calls;
00070         clr_callsA=&A.OP.clr_calls;
00071         ini_callsB=&B.OP.ini_calls;
00072         clr_callsB=&B.OP.clr_calls;
00073         
00074         fprintf(stderr,"  Buildup");
00075         int i,modval=10000;
00076         for(i=0; i<5000; i++)
00077         {
00078             int val=rand()%modval;
00079             //fprintf(stderr,"---------<store=%d>----------\n",val);
00080             A.insert(val);
00081             B.insert(val);
00082             
00083             CritAssert(!A.CheckHeap());
00084             CritAssert(!B.CheckHeap());
00085             
00086             if(!(i%100))
00087             {  fprintf(stderr,".");  }
00088         }
00089         
00090         CritAssert(A.NElem()==size_t(i));
00091         CritAssert(B.NElem()==size_t(i));
00092         fprintf(stderr,"%d\n",i);
00093         
00094         fprintf(stderr,"  Lookup");
00095         for(int j=0; j<20000; j++)
00096         {
00097             int val=rand()%(modval+100)-50;
00098             ssize_t idxAL=A.LinSearch(val);
00099             ssize_t idxBL=B.LinSearch(val);
00100             CritAssert(idxAL==idxBL);
00101             
00102             if(j<1000)  // this is really slow...
00103             {
00104                 ssize_t idxAR=A.RecSearch(val);
00105                 ssize_t idxBR=B.RecSearch(val);
00106                 CritAssert(idxAR==idxBR);
00107                 if(idxAL<0 || idxAR<0)
00108                 {  CritAssert(idxAL==idxAR);  }
00109                 else
00110                 {  CritAssert(A[idxAL]==A[idxAR]);  }
00111             }
00112             
00113             if(idxAL>=0)
00114             {
00115                 //fprintf(stderr,"A[%d]=%d (%d) ",idxAL,A[idxAL],val);
00116                 CritAssert(A[idxAL]==val);
00117             }
00118             
00119             if(!(rand()%6))
00120             {
00121                 int vA=0,vB=0;
00122                 int rvA=A.remove(val,&vA);
00123                 int rvB=B.remove(val,&vB);
00124                 CritAssert(rvA==rvB);
00125                 CritAssert(vA==vB);
00126                 
00127                 CritAssert(!A.CheckHeap());
00128                 CritAssert(!B.CheckHeap());
00129             }
00130             if(idxAL>=0 && !(rand()%4))
00131             {
00132                 int vA=0,vB=0;
00133                 int rvA=A.RemoveIdx(idxAL,&vA);
00134                 int rvB=B.RemoveIdx(idxAL,&vB);
00135                 CritAssert(rvA==rvB);
00136                 CritAssert(vA==vB);
00137                 
00138                 CritAssert(!A.CheckHeap());
00139                 CritAssert(!B.CheckHeap());
00140             }
00141             if(!(rand()%5) && val>=0)
00142             {
00143                 A.insert(val);
00144                 B.insert(val);
00145                 
00146                 CritAssert(!A.CheckHeap());
00147                 CritAssert(!B.CheckHeap());
00148             }
00149             if(idxAL>=0 && !(rand()%8))
00150             {
00151                 int new_val=rand()%modval;
00152                 A.ReplaceIdx(idxAL,new_val);
00153                 B.ReplaceIdx(idxAL,new_val);
00154                 
00155                 CritAssert(!A.CheckHeap());
00156                 CritAssert(!B.CheckHeap());
00157             }
00158             if(!(rand()%10))
00159             {
00160                 int rvA=0,rvB=0;
00161                 A.PopFirst(&rvA);
00162                 B.PopFirst(&rvB);
00163                 CritAssert(rvA==rvB);
00164                 
00165                 CritAssert(!A.CheckHeap());
00166                 CritAssert(!B.CheckHeap());
00167             }
00168             
00169             if(!(j%500))
00170             {  fprintf(stderr,".");  }
00171         }
00172         CritAssert(A.NElem()==B.NElem());
00173         fprintf(stderr,"(%d)\n",A.NElem());
00174         
00175         fprintf(stderr,"  Pop");
00176         int prev=-999;
00177         for(;;i++)
00178         {
00179             int vA=0,vB=0;
00180             int rvA=A.PopFirst(&vA);
00181             int rvB=B.PopFirst(&vB);
00182             //fprintf(stderr,"%d ",vA);
00183             CritAssert(rvA==rvB);
00184             CritAssert(vA==vB);
00185             if(prev!=-999)
00186             {  CritAssert(vA<=prev);  }
00187             prev=vA;
00188             
00189             CritAssert(!A.CheckHeap());
00190             CritAssert(!B.CheckHeap());
00191             
00192             if(!(i%100))
00193             {  fprintf(stderr,".");  }
00194             
00195             if(rvA==1)  break;  // heap empty
00196         }
00197         fprintf(stderr,"OK\n");
00198         
00199         fprintf(stderr,
00200             "ini/clr=A(%d,%d,%d),B(%d,%d,%d)\n",
00201             *ini_callsA,*clr_callsA,*ini_callsA-*clr_callsA,
00202             *ini_callsB,*clr_callsB,*ini_callsB-*clr_callsB );
00203     } while(0);
00204     
00205     fprintf(stderr,"  A: ini_calls=%d, clr_calls=%d, diff=%d\n",
00206         *ini_callsA,*clr_callsA,*ini_callsA-*clr_callsA);
00207     fprintf(stderr,"  B: ini_calls=%d, clr_calls=%d, diff=%d\n",
00208         *ini_callsB,*clr_callsB,*ini_callsB-*clr_callsB);
00209     
00210     if(*ini_callsA-*clr_callsA || 
00211        *ini_callsB-*clr_callsB )
00212     {  return(1);  }
00213     
00214     // Allocation debugging: 
00215     LMallocUsage lmu;
00216     LMallocGetUsage(&lmu);
00217     fprintf(stderr,"%s: %sAlloc: %u bytes in %d chunks; Peak: %u by,%d chks; "
00218         "(%u/%u/%u)%s\n",
00219         prg_name,
00220         lmu.curr_used ? "*** " : "",
00221         lmu.curr_used,lmu.used_chunks,lmu.max_used,lmu.max_used_chunks,
00222         lmu.malloc_calls,lmu.realloc_calls,lmu.free_calls,
00223         lmu.curr_used ? " ***" : "");
00224     if(lmu.curr_used)  return(1);
00225     
00226     fprintf(stderr,"TLArrayHeap test SUCCESSFUL.\n");
00227     return(0);
00228 }