00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037 #include "mem.h"
00038 #include <string.h>
00039 #include <stdio.h>
00040 #include <stdlib.h>
00041
00042 #ifndef qhDEFlibqhull
00043 typedef struct ridgeT ridgeT;
00044 typedef struct facetT facetT;
00045 #ifdef _MSC_VER
00046 #pragma warning( disable : 4127)
00047 #pragma warning( disable : 4706)
00048 #endif
00049 void qh_errexit(int exitcode, facetT *, ridgeT *);
00050 void qh_exit(int exitcode);
00051 void qh_fprintf(FILE *fp, int msgcode, const char *fmt, ... );
00052 void qh_free(void *mem);
00053 void *qh_malloc(size_t size);
00054 #endif
00055
00056
00057
00058
00059
00060 qhmemT qhmem= {0,0,0,0,0,0,0,0,0,0,0,
00061 0,0,0,0,0,0,0,0,0,0,0,
00062 0,0,0,0,0,0,0};
00063
00064 #ifndef qh_NOmem
00065
00066
00067
00068 static int qh_intcompare(const void *i, const void *j);
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078 static int qh_intcompare(const void *i, const void *j) {
00079 return(*((const int *)i) - *((const int *)j));
00080 }
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111 void *qh_memalloc(int insize) {
00112 void **freelistp, *newbuffer;
00113 int idx, size, n;
00114 int outsize, bufsize;
00115 void *object;
00116
00117 if (insize<0) {
00118 qh_fprintf(qhmem.ferr, 6235, "qhull error (qh_memalloc): negative request size (%d). Did int overflow due to high-D?\n", insize);
00119 qh_errexit(qhmem_ERRmem, NULL, NULL);
00120 }
00121 if (insize>=0 && insize <= qhmem.LASTsize) {
00122 idx= qhmem.indextable[insize];
00123 outsize= qhmem.sizetable[idx];
00124 qhmem.totshort += outsize;
00125 freelistp= qhmem.freelists+idx;
00126 if ((object= *freelistp)) {
00127 qhmem.cntquick++;
00128 qhmem.totfree -= outsize;
00129 *freelistp= *((void **)*freelistp);
00130 #ifdef qh_TRACEshort
00131 n= qhmem.cntshort+qhmem.cntquick+qhmem.freeshort;
00132 if (qhmem.IStracing >= 5)
00133 qh_fprintf(qhmem.ferr, 8141, "qh_mem %p n %8d alloc quick: %d bytes (tot %d cnt %d)\n", object, n, outsize, qhmem.totshort, qhmem.cntshort+qhmem.cntquick-qhmem.freeshort);
00134 #endif
00135 return(object);
00136 }else {
00137 qhmem.cntshort++;
00138 if (outsize > qhmem .freesize) {
00139 qhmem .totdropped += qhmem .freesize;
00140 if (!qhmem.curbuffer)
00141 bufsize= qhmem.BUFinit;
00142 else
00143 bufsize= qhmem.BUFsize;
00144 if (!(newbuffer= qh_malloc((size_t)bufsize))) {
00145 qh_fprintf(qhmem.ferr, 6080, "qhull error (qh_memalloc): insufficient memory to allocate short memory buffer (%d bytes)\n", bufsize);
00146 qh_errexit(qhmem_ERRmem, NULL, NULL);
00147 }
00148 *((void **)newbuffer)= qhmem.curbuffer;
00149
00150 qhmem.curbuffer= newbuffer;
00151 size= (sizeof(void **) + qhmem.ALIGNmask) & ~qhmem.ALIGNmask;
00152 qhmem.freemem= (void *)((char *)newbuffer+size);
00153 qhmem.freesize= bufsize - size;
00154 qhmem.totbuffer += bufsize - size;
00155
00156 n = qhmem.totshort + qhmem.totfree + qhmem.totdropped + qhmem.freesize - outsize;
00157 if (qhmem.totbuffer != n) {
00158 qh_fprintf(qhmem.ferr, 6212, "qh_memalloc internal error: short totbuffer %d != totshort+totfree... %d\n", qhmem.totbuffer, n);
00159 qh_errexit(qhmem_ERRmem, NULL, NULL);
00160 }
00161 }
00162 object= qhmem.freemem;
00163 qhmem.freemem= (void *)((char *)qhmem.freemem + outsize);
00164 qhmem.freesize -= outsize;
00165 qhmem.totunused += outsize - insize;
00166 #ifdef qh_TRACEshort
00167 n= qhmem.cntshort+qhmem.cntquick+qhmem.freeshort;
00168 if (qhmem.IStracing >= 5)
00169 qh_fprintf(qhmem.ferr, 8140, "qh_mem %p n %8d alloc short: %d bytes (tot %d cnt %d)\n", object, n, outsize, qhmem.totshort, qhmem.cntshort+qhmem.cntquick-qhmem.freeshort);
00170 #endif
00171 return object;
00172 }
00173 }else {
00174 if (!qhmem.indextable) {
00175 qh_fprintf(qhmem.ferr, 6081, "qhull internal error (qh_memalloc): qhmem has not been initialized.\n");
00176 qh_errexit(qhmem_ERRqhull, NULL, NULL);
00177 }
00178 outsize= insize;
00179 qhmem .cntlong++;
00180 qhmem .totlong += outsize;
00181 if (qhmem.maxlong < qhmem.totlong)
00182 qhmem.maxlong= qhmem.totlong;
00183 if (!(object= qh_malloc((size_t)outsize))) {
00184 qh_fprintf(qhmem.ferr, 6082, "qhull error (qh_memalloc): insufficient memory to allocate %d bytes\n", outsize);
00185 qh_errexit(qhmem_ERRmem, NULL, NULL);
00186 }
00187 if (qhmem.IStracing >= 5)
00188 qh_fprintf(qhmem.ferr, 8057, "qh_mem %p n %8d alloc long: %d bytes (tot %d cnt %d)\n", object, qhmem.cntlong+qhmem.freelong, outsize, qhmem.totlong, qhmem.cntlong-qhmem.freelong);
00189 }
00190 return(object);
00191 }
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211
00212 void qh_memfree(void *object, int insize) {
00213 void **freelistp;
00214 int idx, outsize;
00215
00216 if (!object)
00217 return;
00218 if (insize <= qhmem.LASTsize) {
00219 qhmem .freeshort++;
00220 idx= qhmem.indextable[insize];
00221 outsize= qhmem.sizetable[idx];
00222 qhmem .totfree += outsize;
00223 qhmem .totshort -= outsize;
00224 freelistp= qhmem.freelists + idx;
00225 *((void **)object)= *freelistp;
00226 *freelistp= object;
00227 #ifdef qh_TRACEshort
00228 idx= qhmem.cntshort+qhmem.cntquick+qhmem.freeshort;
00229 if (qhmem.IStracing >= 5)
00230 qh_fprintf(qhmem.ferr, 8142, "qh_mem %p n %8d free short: %d bytes (tot %d cnt %d)\n", object, idx, outsize, qhmem.totshort, qhmem.cntshort+qhmem.cntquick-qhmem.freeshort);
00231 #endif
00232 }else {
00233 qhmem .freelong++;
00234 qhmem .totlong -= insize;
00235 qh_free(object);
00236 if (qhmem.IStracing >= 5)
00237 qh_fprintf(qhmem.ferr, 8058, "qh_mem %p n %8d free long: %d bytes (tot %d cnt %d)\n", object, qhmem.cntlong+qhmem.freelong, insize, qhmem.totlong, qhmem.cntlong-qhmem.freelong);
00238 }
00239 }
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251
00252
00253
00254
00255 void qh_memfreeshort(int *curlong, int *totlong) {
00256 void *buffer, *nextbuffer;
00257 FILE *ferr;
00258
00259 *curlong= qhmem .cntlong - qhmem .freelong;
00260 *totlong= qhmem .totlong;
00261 for (buffer= qhmem.curbuffer; buffer; buffer= nextbuffer) {
00262 nextbuffer= *((void **) buffer);
00263 qh_free(buffer);
00264 }
00265 qhmem.curbuffer= NULL;
00266 if (qhmem .LASTsize) {
00267 qh_free(qhmem .indextable);
00268 qh_free(qhmem .freelists);
00269 qh_free(qhmem .sizetable);
00270 }
00271 ferr= qhmem.ferr;
00272 memset((char *)&qhmem, 0, sizeof(qhmem));
00273 qhmem.ferr= ferr;
00274 }
00275
00276
00277
00278
00279
00280
00281
00282
00283 void qh_meminit(FILE *ferr) {
00284
00285 memset((char *)&qhmem, 0, sizeof(qhmem));
00286 qhmem.ferr= ferr;
00287 if (sizeof(void*) < sizeof(int)) {
00288 qh_fprintf(ferr, 6083, "qhull internal error (qh_meminit): sizeof(void*) %d < sizeof(int) %d. qset.c will not work\n", (int)sizeof(void*), (int)sizeof(int));
00289 qh_exit(qhmem_ERRqhull);
00290 }
00291 if (sizeof(void*) > sizeof(ptr_intT)) {
00292 qh_fprintf(ferr, 6084, "qhull internal error (qh_meminit): sizeof(void*) %d > sizeof(ptr_intT) %d. Change ptr_intT in mem.h to 'long long'\n", (int)sizeof(void*), (int)sizeof(ptr_intT));
00293 qh_exit(qhmem_ERRqhull);
00294 }
00295 }
00296
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307
00308 void qh_meminitbuffers(int tracelevel, int alignment, int numsizes, int bufsize, int bufinit) {
00309
00310 qhmem.IStracing= tracelevel;
00311 qhmem.NUMsizes= numsizes;
00312 qhmem.BUFsize= bufsize;
00313 qhmem.BUFinit= bufinit;
00314 qhmem.ALIGNmask= alignment-1;
00315 if (qhmem.ALIGNmask & ~qhmem.ALIGNmask) {
00316 qh_fprintf(qhmem.ferr, 6085, "qhull internal error (qh_meminit): memory alignment %d is not a power of 2\n", alignment);
00317 qh_errexit(qhmem_ERRqhull, NULL, NULL);
00318 }
00319 qhmem.sizetable= (int *) calloc((size_t)numsizes, sizeof(int));
00320 qhmem.freelists= (void **) calloc((size_t)numsizes, sizeof(void *));
00321 if (!qhmem.sizetable || !qhmem.freelists) {
00322 qh_fprintf(qhmem.ferr, 6086, "qhull error (qh_meminit): insufficient memory\n");
00323 qh_errexit(qhmem_ERRmem, NULL, NULL);
00324 }
00325 if (qhmem.IStracing >= 1)
00326 qh_fprintf(qhmem.ferr, 8059, "qh_meminitbuffers: memory initialized with alignment %d\n", alignment);
00327 }
00328
00329
00330
00331
00332
00333
00334
00335 void qh_memsetup(void) {
00336 int k,i;
00337
00338 qsort(qhmem.sizetable, (size_t)qhmem.TABLEsize, sizeof(int), qh_intcompare);
00339 qhmem.LASTsize= qhmem.sizetable[qhmem.TABLEsize-1];
00340 if (qhmem .LASTsize >= qhmem .BUFsize || qhmem.LASTsize >= qhmem .BUFinit) {
00341 qh_fprintf(qhmem.ferr, 6087, "qhull error (qh_memsetup): largest mem size %d is >= buffer size %d or initial buffer size %d\n",
00342 qhmem .LASTsize, qhmem .BUFsize, qhmem .BUFinit);
00343 qh_errexit(qhmem_ERRmem, NULL, NULL);
00344 }
00345 if (!(qhmem.indextable= (int *)qh_malloc((qhmem.LASTsize+1) * sizeof(int)))) {
00346 qh_fprintf(qhmem.ferr, 6088, "qhull error (qh_memsetup): insufficient memory\n");
00347 qh_errexit(qhmem_ERRmem, NULL, NULL);
00348 }
00349 for (k=qhmem.LASTsize+1; k--; )
00350 qhmem.indextable[k]= k;
00351 i= 0;
00352 for (k=0; k <= qhmem.LASTsize; k++) {
00353 if (qhmem.indextable[k] <= qhmem.sizetable[i])
00354 qhmem.indextable[k]= i;
00355 else
00356 qhmem.indextable[k]= ++i;
00357 }
00358 }
00359
00360
00361
00362
00363
00364
00365
00366 void qh_memsize(int size) {
00367 int k;
00368
00369 if (qhmem .LASTsize) {
00370 qh_fprintf(qhmem.ferr, 6089, "qhull error (qh_memsize): called after qhmem_setup\n");
00371 qh_errexit(qhmem_ERRqhull, NULL, NULL);
00372 }
00373 size= (size + qhmem.ALIGNmask) & ~qhmem.ALIGNmask;
00374 for (k=qhmem.TABLEsize; k--; ) {
00375 if (qhmem.sizetable[k] == size)
00376 return;
00377 }
00378 if (qhmem.TABLEsize < qhmem.NUMsizes)
00379 qhmem.sizetable[qhmem.TABLEsize++]= size;
00380 else
00381 qh_fprintf(qhmem.ferr, 7060, "qhull warning (memsize): free list table has room for only %d sizes\n", qhmem.NUMsizes);
00382 }
00383
00384
00385
00386
00387
00388
00389
00390
00391
00392
00393 void qh_memstatistics(FILE *fp) {
00394 int i, count, totfree= 0;
00395 void *object;
00396
00397 for (i=0; i < qhmem.TABLEsize; i++) {
00398 count=0;
00399 for (object= qhmem .freelists[i]; object; object= *((void **)object))
00400 count++;
00401 totfree += qhmem.sizetable[i] * count;
00402 }
00403 if (totfree != qhmem .totfree) {
00404 qh_fprintf(qhmem.ferr, 6211, "qh_memstatistics internal error: totfree %d not equal to freelist total %d\n", qhmem.totfree, totfree);
00405 qh_errexit(qhmem_ERRqhull, NULL, NULL);
00406 }
00407 qh_fprintf(fp, 9278, "\nmemory statistics:\n\
00408 %7d quick allocations\n\
00409 %7d short allocations\n\
00410 %7d long allocations\n\
00411 %7d short frees\n\
00412 %7d long frees\n\
00413 %7d bytes of short memory in use\n\
00414 %7d bytes of short memory in freelists\n\
00415 %7d bytes of dropped short memory\n\
00416 %7d bytes of unused short memory (estimated)\n\
00417 %7d bytes of long memory allocated (max, except for input)\n\
00418 %7d bytes of long memory in use (in %d pieces)\n\
00419 %7d bytes of short memory buffers (minus links)\n\
00420 %7d bytes per short memory buffer (initially %d bytes)\n",
00421 qhmem .cntquick, qhmem .cntshort, qhmem .cntlong,
00422 qhmem .freeshort, qhmem .freelong,
00423 qhmem .totshort, qhmem .totfree,
00424 qhmem .totdropped + qhmem .freesize, qhmem .totunused,
00425 qhmem .maxlong, qhmem .totlong, qhmem .cntlong - qhmem .freelong,
00426 qhmem .totbuffer, qhmem .BUFsize, qhmem .BUFinit);
00427 if (qhmem.cntlarger) {
00428 qh_fprintf(fp, 9279, "%7d calls to qh_setlarger\n%7.2g average copy size\n",
00429 qhmem.cntlarger, ((float)qhmem.totlarger)/(float)qhmem.cntlarger);
00430 qh_fprintf(fp, 9280, " freelists(bytes->count):");
00431 }
00432 for (i=0; i < qhmem.TABLEsize; i++) {
00433 count=0;
00434 for (object= qhmem .freelists[i]; object; object= *((void **)object))
00435 count++;
00436 qh_fprintf(fp, 9281, " %d->%d", qhmem.sizetable[i], count);
00437 }
00438 qh_fprintf(fp, 9282, "\n\n");
00439 }
00440
00441
00442
00443
00444
00445
00446
00447
00448
00449
00450
00451 #else
00452
00453 void *qh_memalloc(int insize) {
00454 void *object;
00455
00456 if (!(object= qh_malloc((size_t)insize))) {
00457 qh_fprintf(qhmem.ferr, 6090, "qhull error (qh_memalloc): insufficient memory\n");
00458 qh_errexit(qhmem_ERRmem, NULL, NULL);
00459 }
00460 qhmem .cntlong++;
00461 qhmem .totlong += insize;
00462 if (qhmem.maxlong < qhmem.totlong)
00463 qhmem.maxlong= qhmem.totlong;
00464 if (qhmem.IStracing >= 5)
00465 qh_fprintf(qhmem.ferr, 8060, "qh_mem %p n %8d alloc long: %d bytes (tot %d cnt %d)\n", object, qhmem.cntlong+qhmem.freelong, insize, qhmem.totlong, qhmem.cntlong-qhmem.freelong);
00466 return object;
00467 }
00468
00469 void qh_memfree(void *object, int insize) {
00470
00471 if (!object)
00472 return;
00473 qh_free(object);
00474 qhmem .freelong++;
00475 qhmem .totlong -= insize;
00476 if (qhmem.IStracing >= 5)
00477 qh_fprintf(qhmem.ferr, 8061, "qh_mem %p n %8d free long: %d bytes (tot %d cnt %d)\n", object, qhmem.cntlong+qhmem.freelong, insize, qhmem.totlong, qhmem.cntlong-qhmem.freelong);
00478 }
00479
00480 void qh_memfreeshort(int *curlong, int *totlong) {
00481 *totlong= qhmem .totlong;
00482 *curlong= qhmem .cntlong - qhmem .freelong;
00483 memset((char *)&qhmem, 0, sizeof(qhmem));
00484 }
00485
00486 void qh_meminit(FILE *ferr) {
00487
00488 memset((char *)&qhmem, 0, sizeof(qhmem));
00489 qhmem.ferr= ferr;
00490 if (sizeof(void*) < sizeof(int)) {
00491 qh_fprintf(ferr, 6091, "qhull internal error (qh_meminit): sizeof(void*) %d < sizeof(int) %d. qset.c will not work\n", (int)sizeof(void*), (int)sizeof(int));
00492 qh_errexit(qhmem_ERRqhull, NULL, NULL);
00493 }
00494 }
00495
00496 void qh_meminitbuffers(int tracelevel, int alignment, int numsizes, int bufsize, int bufinit) {
00497
00498 qhmem.IStracing= tracelevel;
00499 }
00500
00501 void qh_memsetup(void) {
00502
00503 }
00504
00505 void qh_memsize(int size) {
00506
00507 }
00508
00509 void qh_memstatistics(FILE *fp) {
00510
00511 qh_fprintf(fp, 9409, "\nmemory statistics:\n\
00512 %7d long allocations\n\
00513 %7d long frees\n\
00514 %7d bytes of long memory allocated (max, except for input)\n\
00515 %7d bytes of long memory in use (in %d pieces)\n",
00516 qhmem .cntlong,
00517 qhmem .freelong,
00518 qhmem .maxlong, qhmem .totlong, qhmem .cntlong - qhmem .freelong);
00519 }
00520
00521 #endif
00522
00523
00524
00525
00526
00527
00528
00529
00530
00531
00532
00533
00534
00535 void qh_memtotal(int *totlong, int *curlong, int *totshort, int *curshort, int *maxlong, int *totbuffer) {
00536 *totlong= qhmem .totlong;
00537 *curlong= qhmem .cntlong - qhmem .freelong;
00538 *totshort= qhmem .totshort;
00539 *curshort= qhmem .cntshort + qhmem .cntquick - qhmem .freeshort;
00540 *maxlong= qhmem .maxlong;
00541 *totbuffer= qhmem .totbuffer;
00542 }
00543