graspit: /opt/ros/diamondback/stacks/graspit_simulator/graspit/graspit

00001 /*<html><pre>  -<a                             href="qh-c.htm"
00002   >-------------------------------</a><a name="TOP">-</a>
00003 
00004   mem.c 
00005     memory management routines for qhull
00006 
00007   This is a standalone program.
00008    
00009   To initialize memory:
00010 
00011     qh_meminit (stderr);  
00012     qh_meminitbuffers (qh IStracing, qh_MEMalign, 7, qh_MEMbufsize,qh_MEMinitbuf);
00013     qh_memsize(sizeof(facetT));
00014     qh_memsize(sizeof(facetT));
00015     ...
00016     qh_memsetup();
00017     
00018   To free up all memory buffers:
00019     qh_memfreeshort (&curlong, &totlong);
00020          
00021   if qh_NOmem, 
00022     malloc/free is used instead of mem.c
00023 
00024   notes: 
00025     uses Quickfit algorithm (freelists for commonly allocated sizes)
00026     assumes small sizes for freelists (it discards the tail of memory buffers)
00027    
00028   see:
00029     qh-c.htm and mem.h
00030     global.c (qh_initbuffers) for an example of using mem.c 
00031    
00032   copyright (c) 1993-1998 The Geometry Center
00033 */
00034 
00035 #include <stdio.h>
00036 #include <stdlib.h>
00037 #include <string.h>
00038 #include "mem.h"
00039 
00040 #ifdef USE_DMALLOC
00041 #include "dmalloc.h"
00042 #endif
00043 
00044 #ifndef qhDEFqhull
00045 typedef struct ridgeT ridgeT;
00046 typedef struct facetT facetT;
00047 void    qh_errexit(int exitcode, facetT *, ridgeT *);
00048 #endif
00049 
00050 /*============ -global data structure ==============
00051     see mem.h for definition
00052 */
00053 
00054 qhmemT qhmem= {0};     /* remove "= {0}" if this causes a compiler error */
00055 
00056 #ifndef qh_NOmem
00057 
00058 /*============= internal functions ==============*/
00059   
00060 static int qh_intcompare(const void *i, const void *j);
00061 
00062 /*========== functions in alphabetical order ======== */
00063 
00064 /*-<a                             href="qh-c.htm#mem"
00065   >-------------------------------</a><a name="intcompare">-</a>
00066   
00067   qh_intcompare( i, j )
00068     used by qsort and bsearch to compare two integers
00069 */
00070 static int qh_intcompare(const void *i, const void *j) {
00071   return(*((int *)i) - *((int *)j));
00072 } /* intcompare */
00073 
00074 
00075 /*-<a                             href="qh-c.htm#mem"
00076   >--------------------------------</a><a name="memalloc">-</a>
00077    
00078   qh_memalloc( insize )  
00079     returns object of insize bytes
00080     qhmem is the global memory structure 
00081     
00082   returns:
00083     pointer to allocated memory 
00084     errors if insufficient memory
00085 
00086   notes:
00087     use explicit type conversion to avoid type warnings on some compilers
00088     actual object may be larger than insize
00089     use qh_memalloc_() for inline code for quick allocations
00090     logs allocations if 'T5'
00091   
00092   design:
00093     if size < qhmem.LASTsize
00094       if qhmem.freelists[size] non-empty
00095         return first object on freelist
00096       else
00097         round up request to size of qhmem.freelists[size]
00098         allocate new allocation buffer if necessary
00099         allocate object from allocation buffer
00100     else
00101       allocate object with malloc()
00102 */
00103 void *qh_memalloc(int insize) {
00104   void **freelistp, *newbuffer;
00105   int index, size;
00106   int outsize, bufsize;
00107   void *object;
00108 
00109   if ((unsigned) insize <= (unsigned) qhmem.LASTsize) {
00110     index= qhmem.indextable[insize];
00111     freelistp= qhmem.freelists+index;
00112     if ((object= *freelistp)) {
00113       qhmem.cntquick++;  
00114       *freelistp= *((void **)*freelistp);  /* replace freelist with next object */
00115       return (object);
00116     }else {
00117       outsize= qhmem.sizetable[index];
00118       qhmem.cntshort++;
00119       if (outsize > qhmem .freesize) {
00120         if (!qhmem.curbuffer)
00121           bufsize= qhmem.BUFinit;
00122         else
00123           bufsize= qhmem.BUFsize;
00124         qhmem.totshort += bufsize;
00125         if (!(newbuffer= malloc(bufsize))) {
00126           fprintf(qhmem.ferr, "qhull error (qh_memalloc): insufficient memory\n");
00127           qh_errexit(qhmem_ERRmem, NULL, NULL);
00128         } 
00129         *((void **)newbuffer)= qhmem.curbuffer;  /* prepend newbuffer to curbuffer 
00130                                                     list */
00131         qhmem.curbuffer= newbuffer;
00132         size= (sizeof(void **) + qhmem.ALIGNmask) & ~qhmem.ALIGNmask;
00133         qhmem.freemem= (void *)((char *)newbuffer+size);
00134         qhmem.freesize= bufsize - size;
00135       }
00136       object= qhmem.freemem;
00137       qhmem.freemem= (void *)((char *)qhmem.freemem + outsize);
00138       qhmem.freesize -= outsize;
00139       return object;
00140     }
00141   }else {                     /* long allocation */
00142     if (!qhmem.indextable) {
00143       fprintf (qhmem.ferr, "qhull internal error (qh_memalloc): qhmem has not been initialized.\n");
00144       qh_errexit(qhmem_ERRqhull, NULL, NULL);
00145     }
00146     outsize= insize;
00147     qhmem .cntlong++;
00148     qhmem .curlong++;
00149     qhmem .totlong += outsize;
00150     if (qhmem.maxlong < qhmem.totlong)
00151       qhmem.maxlong= qhmem.totlong;
00152     if (!(object= malloc(outsize))) {
00153       fprintf(qhmem.ferr, "qhull error (qh_memalloc): insufficient memory\n");
00154       qh_errexit(qhmem_ERRmem, NULL, NULL);
00155     }
00156     if (qhmem.IStracing >= 5)
00157       fprintf (qhmem.ferr, "qh_memalloc long: %d bytes at %p\n", outsize, object);
00158   }
00159   return (object);
00160 } /* memalloc */
00161 
00162 
00163 /*-<a                             href="qh-c.htm#mem"
00164   >--------------------------------</a><a name="memfree">-</a>
00165    
00166   qh_memfree( object, size ) 
00167     free up an object of size bytes
00168     size is insize from qh_memalloc
00169 
00170   notes:
00171     object may be NULL
00172     type checking warns if using (void **)object
00173     use qh_memfree_() for quick free's of small objects
00174  
00175   design:
00176     if size <= qhmem.LASTsize
00177       append object to corresponding freelist
00178     else
00179       call free(object)
00180 */
00181 void qh_memfree(void *object, int size) {
00182   void **freelistp;
00183 
00184   if (!object)
00185     return;
00186   if (size <= qhmem.LASTsize) {
00187     qhmem .freeshort++;
00188     freelistp= qhmem.freelists + qhmem.indextable[size];
00189     *((void **)object)= *freelistp;
00190     *freelistp= object;
00191   }else {
00192     qhmem .freelong++;
00193     qhmem .totlong -= size;
00194     free (object);
00195     if (qhmem.IStracing >= 5)
00196       fprintf (qhmem.ferr, "qh_memfree long: %d bytes at %p\n", size, object);
00197   }
00198 } /* memfree */
00199 
00200 
00201 /*-<a                             href="qh-c.htm#mem"
00202   >-------------------------------</a><a name="memfreeshort">-</a>
00203   
00204   qh_memfreeshort( curlong, totlong )
00205     frees up all short and qhmem memory allocations
00206 
00207   returns:
00208     number and size of current long allocations
00209 */
00210 void qh_memfreeshort (int *curlong, int *totlong) {
00211   void *buffer, *nextbuffer;
00212 
00213   *curlong= qhmem .cntlong - qhmem .freelong;
00214   *totlong= qhmem .totlong;
00215   for(buffer= qhmem.curbuffer; buffer; buffer= nextbuffer) {
00216     nextbuffer= *((void **) buffer);
00217     free(buffer);
00218   }
00219   qhmem.curbuffer= NULL;
00220   if (qhmem .LASTsize) {
00221     free (qhmem .indextable);
00222     free (qhmem .freelists);
00223     free (qhmem .sizetable);
00224   }
00225   memset((char *)&qhmem, 0, sizeof qhmem);  /* every field is 0, FALSE, NULL */
00226 } /* memfreeshort */
00227 
00228 
00229 /*-<a                             href="qh-c.htm#mem"
00230   >--------------------------------</a><a name="meminit">-</a>
00231    
00232   qh_meminit( ferr )
00233     initialize qhmem and test sizeof( void*)
00234 */
00235 void qh_meminit (FILE *ferr) {
00236   
00237   memset((char *)&qhmem, 0, sizeof qhmem);  /* every field is 0, FALSE, NULL */
00238   qhmem.ferr= ferr;
00239   if (sizeof(void*) < sizeof(int)) {
00240     fprintf (ferr, "qhull internal error (qh_meminit): sizeof(void*) < sizeof(int).  set.c will not work\n");
00241     exit (1);  /* can not use qh_errexit() */
00242   }
00243 } /* meminit */
00244 
00245 /*-<a                             href="qh-c.htm#mem"
00246   >-------------------------------</a><a name="meminitbuffers">-</a>
00247   
00248   qh_meminitbuffers( tracelevel, alignment, numsizes, bufsize, bufinit )
00249     initialize qhmem
00250     if tracelevel >= 5, trace memory allocations
00251     alignment= desired address alignment for memory allocations
00252     numsizes= number of freelists
00253     bufsize=  size of additional memory buffers for short allocations
00254     bufinit=  size of initial memory buffer for short allocations
00255 */
00256 void qh_meminitbuffers (int tracelevel, int alignment, int numsizes, int bufsize, int bufinit) {
00257 
00258   qhmem.IStracing= tracelevel;
00259   qhmem.NUMsizes= numsizes;
00260   qhmem.BUFsize= bufsize;
00261   qhmem.BUFinit= bufinit;
00262   qhmem.ALIGNmask= alignment-1;
00263   if (qhmem.ALIGNmask & ~qhmem.ALIGNmask) {
00264     fprintf (qhmem.ferr, "qhull internal error (qh_meminit): memory alignment %d is not a power of 2\n", alignment);
00265     qh_errexit (qhmem_ERRqhull, NULL, NULL);
00266   }
00267   qhmem.sizetable= (int *) calloc (numsizes, sizeof(int));
00268   qhmem.freelists= (void **) calloc (numsizes, sizeof(void *));
00269   if (!qhmem.sizetable || !qhmem.freelists) {
00270     fprintf(qhmem.ferr, "qhull error (qh_meminit): insufficient memory\n");
00271     qh_errexit (qhmem_ERRmem, NULL, NULL);
00272   }
00273   if (qhmem.IStracing >= 1)
00274     fprintf (qhmem.ferr, "qh_meminitbuffers: memory initialized with alignment %d\n", alignment);
00275 } /* meminitbuffers */
00276 
00277 /*-<a                             href="qh-c.htm#mem"
00278   >-------------------------------</a><a name="memsetup">-</a>
00279   
00280   qh_memsetup()
00281     set up memory after running memsize()
00282 */
00283 void qh_memsetup (void) {
00284   int k,i;
00285 
00286   qsort(qhmem.sizetable, qhmem.TABLEsize, sizeof(int), qh_intcompare);
00287   qhmem.LASTsize= qhmem.sizetable[qhmem.TABLEsize-1];
00288   if (qhmem .LASTsize >= qhmem .BUFsize || qhmem.LASTsize >= qhmem .BUFinit) {
00289     fprintf (qhmem.ferr, "qhull error (qh_memsetup): largest mem size %d is >= buffer size %d or initial buffer size %d\n",
00290             qhmem .LASTsize, qhmem .BUFsize, qhmem .BUFinit);
00291     qh_errexit(qhmem_ERRmem, NULL, NULL);
00292   }
00293   if (!(qhmem.indextable= (int *)malloc((qhmem.LASTsize+1) * sizeof(int)))) {
00294     fprintf(qhmem.ferr, "qhull error (qh_memsetup): insufficient memory\n");
00295     qh_errexit(qhmem_ERRmem, NULL, NULL);
00296   }
00297   for(k=qhmem.LASTsize+1; k--; )
00298     qhmem.indextable[k]= k;
00299   i= 0;
00300   for(k= 0; k <= qhmem.LASTsize; k++) {
00301     if (qhmem.indextable[k] <= qhmem.sizetable[i])
00302       qhmem.indextable[k]= i;
00303     else
00304       qhmem.indextable[k]= ++i;
00305   }
00306 } /* memsetup */
00307 
00308 /*-<a                             href="qh-c.htm#mem"
00309   >-------------------------------</a><a name="memsize">-</a>
00310   
00311   qh_memsize( size )
00312     define a free list for this size
00313 */
00314 void qh_memsize(int size) {
00315   int k;
00316 
00317   if (qhmem .LASTsize) {
00318     fprintf (qhmem .ferr, "qhull error (qh_memsize): called after qhmem_setup\n");
00319     qh_errexit (qhmem_ERRqhull, NULL, NULL);
00320   }
00321   size= (size + qhmem.ALIGNmask) & ~qhmem.ALIGNmask;
00322   for(k= qhmem.TABLEsize; k--; ) {
00323     if (qhmem.sizetable[k] == size)
00324       return;
00325   }
00326   if (qhmem.TABLEsize < qhmem.NUMsizes)
00327     qhmem.sizetable[qhmem.TABLEsize++]= size;
00328   else
00329     fprintf(qhmem.ferr, "qhull warning (memsize): free list table has room for only %d sizes\n", qhmem.NUMsizes);
00330 } /* memsize */
00331 
00332 
00333 /*-<a                             href="qh-c.htm#mem"
00334   >-------------------------------</a><a name="memstatistics">-</a>
00335   
00336   qh_memstatistics( fp )
00337     print out memory statistics
00338 
00339   notes:
00340     does not account for wasted memory at the end of each block
00341 */
00342 void qh_memstatistics (FILE *fp) {
00343   int i, count, totfree= 0;
00344   void *object;
00345   
00346   for (i=0; i < qhmem.TABLEsize; i++) {
00347     count=0;
00348     for (object= qhmem .freelists[i]; object; object= *((void **)object))
00349       count++;
00350     totfree += qhmem.sizetable[i] * count;
00351   }
00352   fprintf (fp, "\nmemory statistics:\n\
00353 %7d quick allocations\n\
00354 %7d short allocations\n\
00355 %7d long allocations\n\
00356 %7d short frees\n\
00357 %7d long frees\n\
00358 %7d bytes of short memory in use\n\
00359 %7d bytes of short memory in freelists\n\
00360 %7d bytes of long memory allocated (except for input)\n\
00361 %7d bytes of long memory in use (in %d pieces)\n\
00362 %7d bytes per memory buffer (initially %d bytes)\n",
00363            qhmem .cntquick, qhmem.cntshort, qhmem.cntlong,
00364            qhmem .freeshort, qhmem.freelong, 
00365            qhmem .totshort - qhmem .freesize - totfree,
00366            totfree,
00367            qhmem .maxlong, qhmem .totlong, qhmem .cntlong - qhmem .freelong,
00368            qhmem .BUFsize, qhmem .BUFinit);
00369   if (qhmem.cntlarger) {
00370     fprintf (fp, "%7d calls to qh_setlarger\n%7.2g     average copy size\n",
00371            qhmem.cntlarger, ((float) qhmem.totlarger)/ qhmem.cntlarger);
00372     fprintf (fp, "  freelists (bytes->count):");
00373   }
00374   for (i=0; i < qhmem.TABLEsize; i++) {
00375     count=0;
00376     for (object= qhmem .freelists[i]; object; object= *((void **)object))
00377       count++;
00378     fprintf (fp, " %d->%d", qhmem.sizetable[i], count);
00379   }
00380   fprintf (fp, "\n\n");
00381 } /* memstatistics */
00382 
00383 
00384 /*-<a                             href="qh-c.htm#mem"
00385   >-------------------------------</a><a name="NOmem">-</a>
00386   
00387   qh_NOmem
00388     turn off quick-fit memory allocation
00389 
00390   notes:
00391     uses malloc() and free() instead
00392 */
00393 #else /* qh_NOmem */
00394 
00395 void *qh_memalloc(int insize) {
00396   void *object;
00397 
00398   if (!(object= malloc(insize))) {
00399     fprintf(qhmem.ferr, "qhull error (qh_memalloc): insufficient memory\n");
00400     qh_errexit(qhmem_ERRmem, NULL, NULL);
00401   }
00402   if (qhmem.IStracing >= 5)
00403     fprintf (qhmem.ferr, "qh_memalloc long: %d bytes at %p\n", insize, object);
00404   return object;
00405 }
00406 
00407 void qh_memfree(void *object, int size) {
00408 
00409   if (!object)
00410     return;
00411   free (object);
00412   if (qhmem.IStracing >= 5)
00413     fprintf (qhmem.ferr, "qh_memfree long: %d bytes at %p\n", size, object);
00414 }
00415 
00416 void qh_memfreeshort (int *curlong, int *totlong) {
00417 
00418   memset((char *)&qhmem, 0, sizeof qhmem);  /* every field is 0, FALSE, NULL */
00419   *curlong= 0;
00420   *totlong= 0;
00421 }
00422 
00423 void qh_meminit (FILE *ferr) {
00424 
00425   memset((char *)&qhmem, 0, sizeof qhmem);  /* every field is 0, FALSE, NULL */
00426   qhmem.ferr= ferr;
00427   if (sizeof(void*) < sizeof(int)) {
00428     fprintf (ferr, "qhull internal error (qh_meminit): sizeof(void*) < sizeof(int).  set.c will not work\n");
00429     qh_errexit (qhmem_ERRqhull, NULL, NULL);
00430   }
00431 }
00432 
00433 void qh_meminitbuffers (int tracelevel, int alignment, int numsizes, int bufsize, int bufinit) {
00434 
00435   qhmem.IStracing= tracelevel;
00436 
00437 }
00438 
00439 void qh_memsetup (void) {
00440 
00441 }
00442 
00443 void qh_memsize(int size) {
00444 
00445 }
00446 
00447 void qh_memstatistics (FILE *fp) {
00448 
00449 }
00450 
00451 #endif /* qh_NOmem */
/opt/ros/diamondback/stacks/graspit_simulator/graspit/graspit_source/qhull/mem.c
