pelqhull.cc

Gambit 是一个游戏库理论软件

/* qhull.c - For the Gambit Project

   This file contains the implementation code taken from qhull and 
incorporated into the Gambit source code.  We have placed all qhull
code in qhull.h and qhull.c to avoid adding to the number of files
in Gambit, and, more importantly, to express the idea that, from our
point of view, this is a blackbox.  We are unlikely to be able to 
answer questions concerning this code, and those who wish to modify
it should consider beginning with the version distributed by the 
Geometry Center.
*/

#include "pelqhull.h" 

/*************************************************************************/
/******************* implementation code from mem.c **********************/
/*************************************************************************/

/* 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);
         
   
   uses Quickfit algorithm (freelists for commonly allocated sizes)
   assumes small sizes for freelists (it discards the tail of memory buffers)
   
   see README and mem.h
   see global.c (qh_initbuffers) for an example of using mem.c 
   
   copyright (c) 1993-1994 The Geometry Center
*/

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

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

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

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

/*-------------------------------------------------
-intcompare- 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 */


/*-------------------------------------------------
-memalloc- allocates memory for object from qhmem
returns:
 pointer to allocated memory (errors if insufficient memory)
 outsize= actual size allocated, may be NULL
notes:
  use qh_memalloc_() for inline code for quick allocations
*/
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))) qhull_fatal(1);

	*((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) qhull_fatal(2);

    outsize= insize;
    qhmem .cntlong++;
    qhmem .curlong++;
    qhmem .totlong += outsize;
    if (qhmem.maxlong < qhmem.totlong)
      qhmem.maxlong= qhmem.totlong;

    if (!(object= malloc(outsize))) qhull_fatal(3);

    if (qhmem.IStracing >= 5)
      fprintf (qhmem.ferr, "qh_memalloc long: %d bytes at %x\n", outsize, (int)object);
  }
  return (object);
} /* memalloc */


/*-------------------------------------------------
-memfree- frees memory object (may be NULL)
  size is either insize or outsize from qh_memalloc
  type checking warns if using (void **)object
  qh_memfree_()- in-line code for quick free's
*/
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 %x\n", size, (int)object);
  }
} /* memfree */


/*-------------------------------------------------
-memfreeshort- 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;

  *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);
  }
  memset((char *)&qhmem, 0, sizeof qhmem);  /* every field is 0, FALSE, NULL */
} /* memfreeshort */


/*-------------------------------------------------
-meminit- initialize memory (memalloc errors until memsetup)
*/
void qh_meminit (FILE *ferr) {
  
  memset((char *)&qhmem, 0, sizeof qhmem);  /* every field is 0, FALSE, NULL */
  qhmem.ferr= ferr;

#ifndef __BCC55__
  // This condition is always false under BCC55
  if (sizeof(void*) < sizeof(int)) qhull_fatal(4);
#endif  // __BCC55__
} /* meminit */

/*-------------------------------------------------
-meminitbuffers- initialize memory buffers
*/
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) qhull_fatal(5);

  qhmem.sizetable= (int *) calloc (numsizes, sizeof(int));
  qhmem.freelists= (void **) calloc (numsizes, sizeof(void *));

  if (!qhmem.sizetable || !qhmem.freelists) qhull_fatal(6);

  if (qhmem.IStracing >= 1)
    fprintf (qhmem.ferr, "qh_meminitbuffers: memory initialized with alignment %d\n", alignment);
} /* meminitbuffers */

/*-------------------------------------------------
-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) 
    qhull_fatal(7);

  if (!(qhmem.indextable= (int *)malloc((qhmem.LASTsize+1) * sizeof(int)))) 
    qhull_fatal(8);

  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 */

/*-------------------------------------------------
-memsize- define a free list for this size
*/
void qh_memsize(int size) {
  int k;

  if (qhmem .LASTsize) qhull_fatal(9);

  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 */


/*-------------------------------------------------
-memstatistics-  print out memory statistics
*/
void qh_memstatistics (FILE *fp) {
  int i, count;
  void *object;
  
  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 or on 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,
	   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 */


/*************************************************************************/
/******************* implementation code from set.c **********************/
/*************************************************************************/

/* set.c -- implements set manipulations needed for quickhull 

   see README and set.h
   
   copyright (c) 1993-1994 The Geometry Center        
*/

/*----------- internal macros -------------------
-SETsizeaddr_(set) - return pointer to actual size+1 of set (set CANNOT be NULL!!)
    *SETsizeaddr==NULL or e[*SETsizeaddr-1]==NULL
*/
#define SETsizeaddr_(set) ((int *)(&((set)->e[(set)->maxsize])))

/*============ functions in alphabetical order ===================*/
  
/*----------------------------------------
-setaddnth- adds newelem as n'th element of sorted or unsorted set
  setp and newelem must be defined
  set may be a temp set
  nth=0 is first element
  errors if nth is out of bounds
*/
void qh_setaddnth(setT **setp, int nth, void *newelem) {
  int *sizep, oldsize, i;
  void **oldp, **newp;

  if (!*setp || !*(sizep= SETsizeaddr_(*setp))) {
    qh_setlarger(setp);
    sizep= SETsizeaddr_(*setp);
  }
  oldsize= *sizep - 1;
  if (nth < 0 || nth > oldsize) qhull_fatal(10);

  (*sizep)++;
  oldp= SETelemaddr_(*setp, oldsize, void);   /* NULL */
  newp= oldp+1;
  for (i= oldsize-nth+1; i--; )  /* move at least NULL  */
    *(newp--)= *(oldp--);       /* may overwrite *sizep */
  *newp= newelem;
} /* setaddnth */


/*----------------------------------------
-setaddsorted- adds an element to a sorted set
  setp and newelem must be defined
  set may be a temp set
  nop if newelem already in set
*/
void qh_setaddsorted(setT **setp, void *newelem) {
  int newindex=0;
  void *elem, **elemp;

  FOREACHelem_(*setp) {          /* could use binary search instead */
    if (elem < newelem)
      newindex++;
    else if (elem == newelem)
      return;
    else
      break;
  }
  qh_setaddnth(setp, newindex, newelem);
} /* setaddsorted */


/*----------------------------------------
-setappend- appends an element to a set
  set may be a temp set
  *setp and newelem may be NULL
*/
void qh_setappend(setT **setp, void *newelem) {
  int *sizep;
  void **endp;

  if (!newelem)
    return;
  if (!*setp || !*(sizep= SETsizeaddr_(*setp))) {
    qh_setlarger(setp);
    sizep= SETsizeaddr_(*setp);
  }
  *(endp= &((*setp)->e[(*sizep)++ - 1]))= newelem;
  *(++endp)= NULL;
} /* setappend */

/*----------------------------------------
-setappend_set- appends a set to a set
  *setp and set may be NULL
  setp can not be a temp set
*/
void qh_setappend_set(setT **setp, setT *setA) {
  int *sizep, sizeA, size;
  setT *oldset;

  if (!setA)
    return;
  SETreturnsize_(setA, sizeA);
  if (!*setp)
    *setp= qh_setnew (sizeA);
  sizep= SETsizeaddr_(*setp);
  if (!(size= *sizep))
    size= (*setp)->maxsize;
  else
    size--;
  if (size + sizeA >(int) (*setp)->maxsize) {
    oldset= *setp;
    *setp= qh_setcopy (oldset, sizeA);
    qh_setfree (&oldset);
    sizep= SETsizeaddr_(*setp);
  }
  *sizep= size+sizeA+1;   /* memcpy may overwrite */
  if (sizeA > 0) 
    memcpy((char *)&((*setp)->e[size]), (char *)&(setA->e[0]), SETelemsize *(sizeA+1));
} /* setappend_set */


/*----------------------------------------
-setappend2ndlast- makes newelem the next to the last element in set
  set must have at least one element, newelem must be defined
  set may be a temp set
*/
void qh_setappend2ndlast(setT **setp, void *newelem) {
  int *sizep;
  void **endp, **lastp;
  
  if (!*setp || !*(sizep= SETsizeaddr_(*setp))) {
    qh_setlarger(setp);
    sizep= SETsizeaddr_(*setp);
  }
  endp= SETelemaddr_(*setp, (*sizep)++ -1, void); /* NULL */
  lastp= endp-1;
  *(endp++)= *lastp;
  *endp= NULL;    /* may overwrite *sizep */
  *lastp= newelem;
} /* setappend2ndlast */


/*----------------------------------------
-setcheck- check set for validity
*/
void qh_setcheck(setT *set, char *typenameNEW, int id) {
  int maxsize, size;
  int waserr= 0;

  if (!set)
    return;
  SETreturnsize_(set, size);
  maxsize= set->maxsize;
  if (size > maxsize || !maxsize) {
    fprintf (qhmem.ferr, "qhull internal error (setcheck): actual size %d of %s%d is greater than max size %d\n",
	     size, typenameNEW, id, maxsize);
    waserr= 1;
  }else if (set->e[size]) {
    fprintf (qhmem.ferr, "qhull internal error (setcheck): %s%d (size %d max %d) is not null terminated.\n",
	     typenameNEW, id, maxsize, size-1);
    waserr= 1;
  }
  if (waserr) qhull_fatal(11);

} /* setcheck */