src/QuickHull/mem.c

/*<html><pre>  -<a                             href="qh-mem.htm"
  >-------------------------------</a><a name="TOP">-</a>

  mem.c 
    memory management routines for qhull

  This is a standalone program.
   
  To initialize memory:

    qh_meminit (stderr);  
    qh_meminitbuffers (qh IStracing, qh_MEMalign, 7, qh_MEMbufsize,qh_MEMinitbuf);
    qh_memsize(sizeof(facetT));
    qh_memsize(sizeof(facetT));
    ...
    qh_memsetup();
    
  To free up all memory buffers:
    qh_memfreeshort (&curlong, &totlong);
         
  if qh_NOmem, 
    malloc/free is used instead of mem.c

  notes: 
    uses Quickfit algorithm (freelists for commonly allocated sizes)
    assumes small sizes for freelists (it discards the tail of memory buffers)
   
  see:
    qh-mem.htm and mem.h
    global.c (qh_initbuffers) for an example of using mem.c 
   
  copyright (c) 1993-2003 The Geometry Center
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "config.h"
#include "QuickHull/mem.h"

#ifndef qhDEFqhull
typedef struct ridgeT ridgeT;
typedef struct facetT facetT;
void    qh_errexit(int exitcode, facetT *, ridgeT *);
#endif

/*============ -global data structure ==============
    see mem.h for definition
*/

qhmemT qhmem= {0};     /* remove "= {0}" if this causes a compiler error */

#ifndef qh_NOmem

/*============= internal functions ==============*/
  
static int qh_intcompare(const void *i, const void *j);

/*========== functions in alphabetical order ======== */

/*-<a                             href="qh-mem.htm#TOC"
  >-------------------------------</a><a name="intcompare">-</a>
  
  qh_intcompare( i, j )
    used by qsort and bsearch to compare two integers
*/
static int qh_intcompare(const void *i, const void *j) {
  return(*((int *)i) - *((int *)j));
} /* intcompare */


/*-<a                             href="qh-mem.htm#TOC"
  >--------------------------------</a><a name="memalloc">-</a>
   
  qh_memalloc( insize )  
    returns object of insize bytes
    qhmem is the global memory structure 
    
  returns:
    pointer to allocated memory 
    errors if insufficient memory

  notes:
    please use explicit type conversion to avoid type warnings on some compilers
    actual object may be larger than insize
    please use qh_memalloc_() for inline code for quick allocations
    logs allocations if 'T5'
  
  design:
    if size < qhmem.LASTsize
      if qhmem.freelists[size] non-empty
        return first object on freelist
      else
        round up request to size of qhmem.freelists[size]
        allocate new allocation buffer if necessary
        allocate object from allocation buffer
    else
      allocate object with malloc()
*/
void *qh_memalloc(int insize) {
  void **freelistp, *newbuffer;
  int index, size;
  int outsize, bufsize;
  void *object;

  if ((unsigned) insize <= (unsigned) qhmem.LASTsize) {
    index= qhmem.indextable[insize];
    freelistp= qhmem.freelists+index;
    if ((object= *freelistp)) {
      qhmem.cntquick++;  
      *freelistp= *((void **)*freelistp);  /* replace freelist with next object */
      return (object);
    }else {
      outsize= qhmem.sizetable[index];
      qhmem.cntshort++;
      if (outsize > qhmem .freesize) {
        if (!qhmem.curbuffer)
          bufsize= qhmem.BUFinit;
        else
          bufsize= qhmem.BUFsize;
        qhmem.totshort += bufsize;
        if (!(newbuffer= malloc(bufsize))) {
          fprintf(qhmem.ferr, "qhull error (qh_memalloc): insufficient memory\n");
          qh_errexit(qhmem_ERRmem, NULL, NULL);
        } 
        *((void **)newbuffer)= qhmem.curbuffer;  /* prepend newbuffer to curbuffer 
                                                    list */
        qhmem.curbuffer= newbuffer;
        size= (sizeof(void **) + qhmem.ALIGNmask) & ~qhmem.ALIGNmask;
        qhmem.freemem= (void *)((char *)newbuffer+size);
        qhmem.freesize= bufsize - size;
      }
      object= qhmem.freemem;
      qhmem.freemem= (void *)((char *)qhmem.freemem + outsize);
      qhmem.freesize -= outsize;
      return object;
    }
  }else {                     /* long allocation */
    if (!qhmem.indextable) {
      fprintf (qhmem.ferr, "qhull internal error (qh_memalloc): qhmem has not been initialized.\n");
      qh_errexit(qhmem_ERRqhull, NULL, NULL);
    }
    outsize= insize;
    qhmem .cntlong++;
    qhmem .curlong++;
    qhmem .totlong += outsize;
    if (qhmem.maxlong < qhmem.totlong)
      qhmem.maxlong= qhmem.totlong;
    if (!(object= malloc(outsize))) {
      fprintf(qhmem.ferr, "qhull error (qh_memalloc): insufficient memory\n");
      qh_errexit(qhmem_ERRmem, NULL, NULL);
    }
    if (qhmem.IStracing >= 5)
      fprintf (qhmem.ferr, "qh_memalloc long: %d bytes at %p\n", outsize, object);
  }
  return (object);
} /* memalloc */


/*-<a                             href="qh-mem.htm#TOC"
  >--------------------------------</a><a name="memfree">-</a>
   
  qh_memfree( object, size ) 
    free up an object of size bytes
    size is insize from qh_memalloc

  notes:
    object may be NULL
    type checking warns if using (void **)object
    please use qh_memfree_() for quick free's of small objects
 
  design:
    if size <= qhmem.LASTsize
      append object to corresponding freelist
    else
      call free(object)
*/
void qh_memfree(void *object, int size) {
  void **freelistp;

  if (!object)
    return;
  if (size <= qhmem.LASTsize) {
    qhmem .freeshort++;
    freelistp= qhmem.freelists + qhmem.indextable[size];
    *((void **)object)= *freelistp;
    *freelistp= object;
  }else {
    qhmem .freelong++;
    qhmem .totlong -= size;
    free (object);
    if (qhmem.IStracing >= 5)
      fprintf (qhmem.ferr, "qh_memfree long: %d bytes at %p\n", size, object);
  }
} /* memfree */


/*-<a                             href="qh-mem.htm#TOC"
  >-------------------------------</a><a name="memfreeshort">-</a>
  
  qh_memfreeshort( curlong, totlong )
    frees up all short and qhmem memory allocations

  returns:
    number and size of current long allocations
*/
void qh_memfreeshort (int *curlong, int *totlong) {
  void *buffer, *nextbuffer;
  FILE *ferr;

  *curlong= qhmem .cntlong - qhmem .freelong;
  *totlong= qhmem .totlong;
  for(buffer= qhmem.curbuffer; buffer; buffer= nextbuffer) {
    nextbuffer= *((void **) buffer);
    free(buffer);
  }
  qhmem.curbuffer= NULL;
  if (qhmem .LASTsize) {
    free (qhmem .indextable);
    free (qhmem .freelists);
    free (qhmem .sizetable);
  }
  ferr= qhmem.ferr;
  memset((char *)&qhmem, 0, sizeof qhmem);  /* every field is 0, FALSE, NULL */
  qhmem.ferr= ferr;
} /* memfreeshort */


/*-<a                             href="qh-mem.htm#TOC"
  >--------------------------------</a><a name="meminit">-</a>
   
  qh_meminit( ferr )
    initialize qhmem and test sizeof( void*)
*/
void qh_meminit (FILE *ferr) {
  
  memset((char *)&qhmem, 0, sizeof qhmem);  /* every field is 0, FALSE, NULL */
  qhmem.ferr= ferr;
  if (sizeof(void*) < sizeof(int)) {
    fprintf (ferr, "qhull internal error (qh_meminit): sizeof(void*) < sizeof(int).  qset.c will not work\n");
    exit (1);  /* can not use qh_errexit() */
  }
} /* meminit */

/*-<a                             href="qh-mem.htm#TOC"
  >-------------------------------</a><a name="meminitbuffers">-</a>
  
  qh_meminitbuffers( tracelevel, alignment, numsizes, bufsize, bufinit )
    initialize qhmem
    if tracelevel >= 5, trace memory allocations
    alignment= desired address alignment for memory allocations
    numsizes= number of freelists
    bufsize=  size of additional memory buffers for short allocations
    bufinit=  size of initial memory buffer for short allocations
*/
void qh_meminitbuffers (int tracelevel, int alignment, int numsizes, int bufsize, int bufinit) {

  qhmem.IStracing= tracelevel;
  qhmem.NUMsizes= numsizes;
  qhmem.BUFsize= bufsize;
  qhmem.BUFinit= bufinit;
  qhmem.ALIGNmask= alignment-1;
  if (qhmem.ALIGNmask & ~qhmem.ALIGNmask) {
    fprintf (qhmem.ferr, "qhull internal error (qh_meminit): memory alignment %d is not a power of 2\n", alignment);
    qh_errexit (qhmem_ERRqhull, NULL, NULL);
  }
  qhmem.sizetable= (int *) calloc (numsizes, sizeof(int));
  qhmem.freelists= (void **) calloc (numsizes, sizeof(void *));
  if (!qhmem.sizetable || !qhmem.freelists) {
    fprintf(qhmem.ferr, "qhull error (qh_meminit): insufficient memory\n");
    qh_errexit (qhmem_ERRmem, NULL, NULL);
  }
  if (qhmem.IStracing >= 1)
    fprintf (qhmem.ferr, "qh_meminitbuffers: memory initialized with alignment %d\n", alignment);
} /* meminitbuffers */

/*-<a                             href="qh-mem.htm#TOC"
  >-------------------------------</a><a name="memsetup">-</a>
  
  qh_memsetup()
    set up memory after running memsize()
*/
void qh_memsetup (void) {
  int k,i;

  qsort(qhmem.sizetable, qhmem.TABLEsize, sizeof(int), qh_intcompare);
  qhmem.LASTsize= qhmem.sizetable[qhmem.TABLEsize-1];
  if (qhmem .LASTsize >= qhmem .BUFsize || qhmem.LASTsize >= qhmem .BUFinit) {
    fprintf (qhmem.ferr, "qhull error (qh_memsetup): largest mem size %d is >= buffer size %d or initial buffer size %d\n",
            qhmem .LASTsize, qhmem .BUFsize, qhmem .BUFinit);
    qh_errexit(qhmem_ERRmem, NULL, NULL);
  }
  if (!(qhmem.indextable= (int *)malloc((qhmem.LASTsize+1) * sizeof(int)))) {
    fprintf(qhmem.ferr, "qhull error (qh_memsetup): insufficient memory\n");
    qh_errexit(qhmem_ERRmem, NULL, NULL);
  }
  for(k=qhmem.LASTsize+1; k--; )
    qhmem.indextable[k]= k;
  i= 0;
  for(k= 0; k <= qhmem.LASTsize; k++) {
    if (qhmem.indextable[k] <= qhmem.sizetable[i])
      qhmem.indextable[k]= i;
    else
      qhmem.indextable[k]= ++i;
  }
} /* memsetup */

/*-<a                             href="qh-mem.htm#TOC"
  >-------------------------------</a><a name="memsize">-</a>
  
  qh_memsize( size )
    define a free list for this size
*/
void qh_memsize(int size) {
  int k;

  if (qhmem .LASTsize) {
    fprintf (qhmem .ferr, "qhull error (qh_memsize): called after qhmem_setup\n");
    qh_errexit (qhmem_ERRqhull, NULL, NULL);
  }
  size= (size + qhmem.ALIGNmask) & ~qhmem.ALIGNmask;
  for(k= qhmem.TABLEsize; k--; ) {
    if (qhmem.sizetable[k] == size)
      return;
  }
  if (qhmem.TABLEsize < qhmem.NUMsizes)
    qhmem.sizetable[qhmem.TABLEsize++]= size;
  else
    fprintf(qhmem.ferr, "qhull warning (memsize): free list table has room for only %d sizes\n", qhmem.NUMsizes);
} /* memsize */


/*-<a                             href="qh-mem.htm#TOC"
  >-------------------------------</a><a name="memstatistics">-</a>
  
  qh_memstatistics( fp )
    print out memory statistics

  notes:
    does not account for wasted memory at the end of each block
*/
void qh_memstatistics (FILE *fp) {
  int i, count, totfree= 0;
  void *object;
  
  for (i=0; i < qhmem.TABLEsize; i++) {
    count=0;
    for (object= qhmem .freelists[i]; object; object= *((void **)object))
      count++;
    totfree += qhmem.sizetable[i] * count;
  }
  fprintf (fp, "\nmemory statistics:\n\
%7d quick allocations\n\
%7d short allocations\n\
%7d long allocations\n\
%7d short frees\n\
%7d long frees\n\
%7d bytes of short memory in use\n\
%7d bytes of short memory in freelists\n\
%7d bytes of long memory allocated (except for input)\n\
%7d bytes of long memory in use (in %d pieces)\n\
%7d bytes per memory buffer (initially %d bytes)\n",
           qhmem .cntquick, qhmem.cntshort, qhmem.cntlong,
           qhmem .freeshort, qhmem.freelong, 
           qhmem .totshort - qhmem .freesize - totfree,
           totfree,
           qhmem .maxlong, qhmem .totlong, qhmem .cntlong - qhmem .freelong,
           qhmem .BUFsize, qhmem .BUFinit);
  if (qhmem.cntlarger) {
    fprintf (fp, "%7d calls to qh_setlarger\n%7.2g     average copy size\n",
           qhmem.cntlarger, ((float) qhmem.totlarger)/ qhmem.cntlarger);
    fprintf (fp, "  freelists (bytes->count):");
  }
  for (i=0; i < qhmem.TABLEsize; i++) {
    count=0;
    for (object= qhmem .freelists[i]; object; object= *((void **)object))
      count++;
    fprintf (fp, " %d->%d", qhmem.sizetable[i], count);
  }
  fprintf (fp, "\n\n");
} /* memstatistics */


/*-<a                             href="qh-mem.htm#TOC"
  >-------------------------------</a><a name="NOmem">-</a>
  
  qh_NOmem
    turn off quick-fit memory allocation

  notes:
    uses malloc() and free() instead
*/
#else /* qh_NOmem */

void *qh_memalloc(int insize) {
  void *object;

  if (!(object= malloc(insize))) {
    fprintf(qhmem.ferr, "qhull error (qh_memalloc): insufficient memory\n");
    qh_errexit(qhmem_ERRmem, NULL, NULL);
  }
  if (qhmem.IStracing >= 5)
    fprintf (qhmem.ferr, "qh_memalloc long: %d bytes at %p\n", insize, object);
  return object;
}

void qh_memfree(void *object, int size) {

  if (!object)
    return;
  free (object);
  if (qhmem.IStracing >= 5)
    fprintf (qhmem.ferr, "qh_memfree long: %d bytes at %p\n", size, object);
}

void qh_memfreeshort (int *curlong, int *totlong) {

  memset((char *)&qhmem, 0, sizeof qhmem);  /* every field is 0, FALSE, NULL */
  *curlong= 0;
  *totlong= 0;
}

void qh_meminit (FILE *ferr) {

  memset((char *)&qhmem, 0, sizeof qhmem);  /* every field is 0, FALSE, NULL */
  qhmem.ferr= ferr;
  if (sizeof(void*) < sizeof(int)) {
    fprintf (ferr, "qhull internal error (qh_meminit): sizeof(void*) < sizeof(int).  qset.c will not work\n");
    qh_errexit (qhmem_ERRqhull, NULL, NULL);
  }
}

void qh_meminitbuffers (int tracelevel, int alignment, int numsizes, int bufsize, int bufinit) {

  qhmem.IStracing= tracelevel;

}

void qh_memsetup (void) {

}

void qh_memsize(int size) {

}

void qh_memstatistics (FILE *fp) {

}

#endif /* qh_NOmem */
Revision:	1138
Committed:	Tue May 29 22:51:00 2007 UTC (17 years, 11 months ago) by chuckv
Content type:	text/plain
File size:	13474 byte(s)
Log Message:	Addded QuickHull to cvs.
#	User	Rev	Content
1	chuckv	1138	/*<html><pre> -<a href="qh-mem.htm"
2			>-------------------------------</a><a name="TOP">-</a>
3
4			mem.c
5			memory management routines for qhull
6
7			This is a standalone program.
8
9			To initialize memory:
10
11			qh_meminit (stderr);
12			qh_meminitbuffers (qh IStracing, qh_MEMalign, 7, qh_MEMbufsize,qh_MEMinitbuf);
13			qh_memsize(sizeof(facetT));
14			qh_memsize(sizeof(facetT));
15			...
16			qh_memsetup();
17
18			To free up all memory buffers:
19			qh_memfreeshort (&curlong, &totlong);
20
21			if qh_NOmem,
22			malloc/free is used instead of mem.c
23
24			notes:
25			uses Quickfit algorithm (freelists for commonly allocated sizes)
26			assumes small sizes for freelists (it discards the tail of memory buffers)
27
28			see:
29			qh-mem.htm and mem.h
30			global.c (qh_initbuffers) for an example of using mem.c
31
32			copyright (c) 1993-2003 The Geometry Center
33			*/
34
35			#include <stdio.h>
36			#include <stdlib.h>
37			#include <string.h>
38			#include "config.h"
39			#include "QuickHull/mem.h"
40
41			#ifndef qhDEFqhull
42			typedef struct ridgeT ridgeT;
43			typedef struct facetT facetT;
44			void qh_errexit(int exitcode, facetT , ridgeT );
45			#endif
46
47			/*============ -global data structure ==============
48			see mem.h for definition
49			*/
50
51			qhmemT qhmem= {0}; /* remove "= {0}" if this causes a compiler error */
52
53			#ifndef qh_NOmem
54
55			/============= internal functions ==============/
56
57			static int qh_intcompare(const void i, const void j);
58
59			/========== functions in alphabetical order ======== /
60
61			/*-<a href="qh-mem.htm#TOC"
62			>-------------------------------</a><a name="intcompare">-</a>
63
64			qh_intcompare( i, j )
65			used by qsort and bsearch to compare two integers
66			*/
67			static int qh_intcompare(const void i, const void j) {
68			return(((int )i) - ((int )j));
69			} /* intcompare */
70
71
72			/*-<a href="qh-mem.htm#TOC"
73			>--------------------------------</a><a name="memalloc">-</a>
74
75			qh_memalloc( insize )
76			returns object of insize bytes
77			qhmem is the global memory structure
78
79			returns:
80			pointer to allocated memory
81			errors if insufficient memory
82
83			notes:
84			please use explicit type conversion to avoid type warnings on some compilers
85			actual object may be larger than insize
86			please use qh_memalloc_() for inline code for quick allocations
87			logs allocations if 'T5'
88
89			design:
90			if size < qhmem.LASTsize
91			if qhmem.freelists[size] non-empty
92			return first object on freelist
93			else
94			round up request to size of qhmem.freelists[size]
95			allocate new allocation buffer if necessary
96			allocate object from allocation buffer
97			else
98			allocate object with malloc()
99			*/
100			void *qh_memalloc(int insize) {
101			void *freelistp, newbuffer;
102			int index, size;
103			int outsize, bufsize;
104			void *object;
105
106			if ((unsigned) insize <= (unsigned) qhmem.LASTsize) {
107			index= qhmem.indextable[insize];
108			freelistp= qhmem.freelists+index;
109			if ((object= *freelistp)) {
110			qhmem.cntquick++;
111			freelistp= ((void *)freelistp); /* replace freelist with next object */
112			return (object);
113			}else {
114			outsize= qhmem.sizetable[index];
115			qhmem.cntshort++;
116			if (outsize > qhmem .freesize) {
117			if (!qhmem.curbuffer)
118			bufsize= qhmem.BUFinit;
119			else
120			bufsize= qhmem.BUFsize;
121			qhmem.totshort += bufsize;
122			if (!(newbuffer= malloc(bufsize))) {
123			fprintf(qhmem.ferr, "qhull error (qh_memalloc): insufficient memory\n");
124			qh_errexit(qhmem_ERRmem, NULL, NULL);
125			}
126			((void )newbuffer)= qhmem.curbuffer; / prepend newbuffer to curbuffer
127			list */
128			qhmem.curbuffer= newbuffer;
129			size= (sizeof(void **) + qhmem.ALIGNmask) & ~qhmem.ALIGNmask;
130			qhmem.freemem= (void )((char )newbuffer+size);
131			qhmem.freesize= bufsize - size;
132			}
133			object= qhmem.freemem;
134			qhmem.freemem= (void )((char )qhmem.freemem + outsize);
135			qhmem.freesize -= outsize;
136			return object;
137			}
138			}else { /* long allocation */
139			if (!qhmem.indextable) {
140			fprintf (qhmem.ferr, "qhull internal error (qh_memalloc): qhmem has not been initialized.\n");
141			qh_errexit(qhmem_ERRqhull, NULL, NULL);
142			}
143			outsize= insize;
144			qhmem .cntlong++;
145			qhmem .curlong++;
146			qhmem .totlong += outsize;
147			if (qhmem.maxlong < qhmem.totlong)
148			qhmem.maxlong= qhmem.totlong;
149			if (!(object= malloc(outsize))) {
150			fprintf(qhmem.ferr, "qhull error (qh_memalloc): insufficient memory\n");
151			qh_errexit(qhmem_ERRmem, NULL, NULL);
152			}
153			if (qhmem.IStracing >= 5)
154			fprintf (qhmem.ferr, "qh_memalloc long: %d bytes at %p\n", outsize, object);
155			}
156			return (object);
157			} /* memalloc */
158
159
160			/*-<a href="qh-mem.htm#TOC"
161			>--------------------------------</a><a name="memfree">-</a>
162
163			qh_memfree( object, size )
164			free up an object of size bytes
165			size is insize from qh_memalloc
166
167			notes:
168			object may be NULL
169			type checking warns if using (void **)object
170			please use qh_memfree_() for quick free's of small objects
171
172			design:
173			if size <= qhmem.LASTsize
174			append object to corresponding freelist
175			else
176			call free(object)
177			*/
178			void qh_memfree(void *object, int size) {
179			void **freelistp;
180
181			if (!object)
182			return;
183			if (size <= qhmem.LASTsize) {
184			qhmem .freeshort++;
185			freelistp= qhmem.freelists + qhmem.indextable[size];
186			((void )object)= freelistp;
187			*freelistp= object;
188			}else {
189			qhmem .freelong++;
190			qhmem .totlong -= size;
191			free (object);
192			if (qhmem.IStracing >= 5)
193			fprintf (qhmem.ferr, "qh_memfree long: %d bytes at %p\n", size, object);
194			}
195			} /* memfree */
196
197
198			/*-<a href="qh-mem.htm#TOC"
199			>-------------------------------</a><a name="memfreeshort">-</a>
200
201			qh_memfreeshort( curlong, totlong )
202			frees up all short and qhmem memory allocations
203
204			returns:
205			number and size of current long allocations
206			*/
207			void qh_memfreeshort (int curlong, int totlong) {
208			void buffer, nextbuffer;
209			FILE *ferr;
210
211			*curlong= qhmem .cntlong - qhmem .freelong;
212			*totlong= qhmem .totlong;
213			for(buffer= qhmem.curbuffer; buffer; buffer= nextbuffer) {
214			nextbuffer= ((void *) buffer);
215			free(buffer);
216			}
217			qhmem.curbuffer= NULL;
218			if (qhmem .LASTsize) {
219			free (qhmem .indextable);
220			free (qhmem .freelists);
221			free (qhmem .sizetable);
222			}
223			ferr= qhmem.ferr;
224			memset((char )&qhmem, 0, sizeof qhmem); / every field is 0, FALSE, NULL */
225			qhmem.ferr= ferr;
226			} /* memfreeshort */
227
228
229			/*-<a href="qh-mem.htm#TOC"
230			>--------------------------------</a><a name="meminit">-</a>
231
232			qh_meminit( ferr )
233			initialize qhmem and test sizeof( void*)
234			*/
235			void qh_meminit (FILE *ferr) {
236
237			memset((char )&qhmem, 0, sizeof qhmem); / every field is 0, FALSE, NULL */
238			qhmem.ferr= ferr;
239			if (sizeof(void*) < sizeof(int)) {
240			fprintf (ferr, "qhull internal error (qh_meminit): sizeof(void*) < sizeof(int). qset.c will not work\n");
241			exit (1); /* can not use qh_errexit() */
242			}
243			} /* meminit */
244
245			/*-<a href="qh-mem.htm#TOC"
246			>-------------------------------</a><a name="meminitbuffers">-</a>
247
248			qh_meminitbuffers( tracelevel, alignment, numsizes, bufsize, bufinit )
249			initialize qhmem
250			if tracelevel >= 5, trace memory allocations
251			alignment= desired address alignment for memory allocations
252			numsizes= number of freelists
253			bufsize= size of additional memory buffers for short allocations
254			bufinit= size of initial memory buffer for short allocations
255			*/
256			void qh_meminitbuffers (int tracelevel, int alignment, int numsizes, int bufsize, int bufinit) {
257
258			qhmem.IStracing= tracelevel;
259			qhmem.NUMsizes= numsizes;
260			qhmem.BUFsize= bufsize;
261			qhmem.BUFinit= bufinit;
262			qhmem.ALIGNmask= alignment-1;
263			if (qhmem.ALIGNmask & ~qhmem.ALIGNmask) {
264			fprintf (qhmem.ferr, "qhull internal error (qh_meminit): memory alignment %d is not a power of 2\n", alignment);
265			qh_errexit (qhmem_ERRqhull, NULL, NULL);
266			}
267			qhmem.sizetable= (int *) calloc (numsizes, sizeof(int));
268			qhmem.freelists= (void *) calloc (numsizes, sizeof(void ));
269			if (!qhmem.sizetable \|\| !qhmem.freelists) {
270			fprintf(qhmem.ferr, "qhull error (qh_meminit): insufficient memory\n");
271			qh_errexit (qhmem_ERRmem, NULL, NULL);
272			}
273			if (qhmem.IStracing >= 1)
274			fprintf (qhmem.ferr, "qh_meminitbuffers: memory initialized with alignment %d\n", alignment);
275			} /* meminitbuffers */
276
277			/*-<a href="qh-mem.htm#TOC"
278			>-------------------------------</a><a name="memsetup">-</a>
279
280			qh_memsetup()
281			set up memory after running memsize()
282			*/
283			void qh_memsetup (void) {
284			int k,i;
285
286			qsort(qhmem.sizetable, qhmem.TABLEsize, sizeof(int), qh_intcompare);
287			qhmem.LASTsize= qhmem.sizetable[qhmem.TABLEsize-1];
288			if (qhmem .LASTsize >= qhmem .BUFsize \|\| qhmem.LASTsize >= qhmem .BUFinit) {
289			fprintf (qhmem.ferr, "qhull error (qh_memsetup): largest mem size %d is >= buffer size %d or initial buffer size %d\n",
290			qhmem .LASTsize, qhmem .BUFsize, qhmem .BUFinit);
291			qh_errexit(qhmem_ERRmem, NULL, NULL);
292			}
293			if (!(qhmem.indextable= (int )malloc((qhmem.LASTsize+1) sizeof(int)))) {
294			fprintf(qhmem.ferr, "qhull error (qh_memsetup): insufficient memory\n");
295			qh_errexit(qhmem_ERRmem, NULL, NULL);
296			}
297			for(k=qhmem.LASTsize+1; k--; )
298			qhmem.indextable[k]= k;
299			i= 0;
300			for(k= 0; k <= qhmem.LASTsize; k++) {
301			if (qhmem.indextable[k] <= qhmem.sizetable[i])
302			qhmem.indextable[k]= i;
303			else
304			qhmem.indextable[k]= ++i;
305			}
306			} /* memsetup */
307
308			/*-<a href="qh-mem.htm#TOC"
309			>-------------------------------</a><a name="memsize">-</a>
310
311			qh_memsize( size )
312			define a free list for this size
313			*/
314			void qh_memsize(int size) {
315			int k;
316
317			if (qhmem .LASTsize) {
318			fprintf (qhmem .ferr, "qhull error (qh_memsize): called after qhmem_setup\n");
319			qh_errexit (qhmem_ERRqhull, NULL, NULL);
320			}
321			size= (size + qhmem.ALIGNmask) & ~qhmem.ALIGNmask;
322			for(k= qhmem.TABLEsize; k--; ) {
323			if (qhmem.sizetable[k] == size)
324			return;
325			}
326			if (qhmem.TABLEsize < qhmem.NUMsizes)
327			qhmem.sizetable[qhmem.TABLEsize++]= size;
328			else
329			fprintf(qhmem.ferr, "qhull warning (memsize): free list table has room for only %d sizes\n", qhmem.NUMsizes);
330			} /* memsize */
331
332
333			/*-<a href="qh-mem.htm#TOC"
334			>-------------------------------</a><a name="memstatistics">-</a>
335
336			qh_memstatistics( fp )
337			print out memory statistics
338
339			notes:
340			does not account for wasted memory at the end of each block
341			*/
342			void qh_memstatistics (FILE *fp) {
343			int i, count, totfree= 0;
344			void *object;
345
346			for (i=0; i < qhmem.TABLEsize; i++) {
347			count=0;
348			for (object= qhmem .freelists[i]; object; object= ((void *)object))
349			count++;
350			totfree += qhmem.sizetable[i] * count;
351			}
352			fprintf (fp, "\nmemory statistics:\n\
353			%7d quick allocations\n\
354			%7d short allocations\n\
355			%7d long allocations\n\
356			%7d short frees\n\
357			%7d long frees\n\
358			%7d bytes of short memory in use\n\
359			%7d bytes of short memory in freelists\n\
360			%7d bytes of long memory allocated (except for input)\n\
361			%7d bytes of long memory in use (in %d pieces)\n\
362			%7d bytes per memory buffer (initially %d bytes)\n",
363			qhmem .cntquick, qhmem.cntshort, qhmem.cntlong,
364			qhmem .freeshort, qhmem.freelong,
365			qhmem .totshort - qhmem .freesize - totfree,
366			totfree,
367			qhmem .maxlong, qhmem .totlong, qhmem .cntlong - qhmem .freelong,
368			qhmem .BUFsize, qhmem .BUFinit);
369			if (qhmem.cntlarger) {
370			fprintf (fp, "%7d calls to qh_setlarger\n%7.2g average copy size\n",
371			qhmem.cntlarger, ((float) qhmem.totlarger)/ qhmem.cntlarger);
372			fprintf (fp, " freelists (bytes->count):");
373			}
374			for (i=0; i < qhmem.TABLEsize; i++) {
375			count=0;
376			for (object= qhmem .freelists[i]; object; object= ((void *)object))
377			count++;
378			fprintf (fp, " %d->%d", qhmem.sizetable[i], count);
379			}
380			fprintf (fp, "\n\n");
381			} /* memstatistics */
382
383
384			/*-<a href="qh-mem.htm#TOC"
385			>-------------------------------</a><a name="NOmem">-</a>
386
387			qh_NOmem
388			turn off quick-fit memory allocation
389
390			notes:
391			uses malloc() and free() instead
392			*/
393			#else /* qh_NOmem */
394
395			void *qh_memalloc(int insize) {
396			void *object;
397
398			if (!(object= malloc(insize))) {
399			fprintf(qhmem.ferr, "qhull error (qh_memalloc): insufficient memory\n");
400			qh_errexit(qhmem_ERRmem, NULL, NULL);
401			}
402			if (qhmem.IStracing >= 5)
403			fprintf (qhmem.ferr, "qh_memalloc long: %d bytes at %p\n", insize, object);
404			return object;
405			}
406
407			void qh_memfree(void *object, int size) {
408
409			if (!object)
410			return;
411			free (object);
412			if (qhmem.IStracing >= 5)
413			fprintf (qhmem.ferr, "qh_memfree long: %d bytes at %p\n", size, object);
414			}
415
416			void qh_memfreeshort (int curlong, int totlong) {
417
418			memset((char )&qhmem, 0, sizeof qhmem); / every field is 0, FALSE, NULL */
419			*curlong= 0;
420			*totlong= 0;
421			}
422
423			void qh_meminit (FILE *ferr) {
424
425			memset((char )&qhmem, 0, sizeof qhmem); / every field is 0, FALSE, NULL */
426			qhmem.ferr= ferr;
427			if (sizeof(void*) < sizeof(int)) {
428			fprintf (ferr, "qhull internal error (qh_meminit): sizeof(void*) < sizeof(int). qset.c will not work\n");
429			qh_errexit (qhmem_ERRqhull, NULL, NULL);
430			}
431			}
432
433			void qh_meminitbuffers (int tracelevel, int alignment, int numsizes, int bufsize, int bufinit) {
434
435			qhmem.IStracing= tracelevel;
436
437			}
438
439			void qh_memsetup (void) {
440
441			}
442
443			void qh_memsize(int size) {
444
445			}
446
447			void qh_memstatistics (FILE *fp) {
448
449			}
450
451			#endif /* qh_NOmem */