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 (18 years, 5 months ago) by chuckv
Content type:	text/plain
File size:	13474 byte(s)
Log Message:	Addded QuickHull to cvs.
#	Content
1	/*<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 */