Doxygen Source Code Documentation

Main Page Alphabetical List Data Structures File List Data Fields Globals Search
mem.c

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

Sections

Personal tools

Navigation

Doxygen Source Code Documentation

mem.c
