pelutils.cc

Gambit 是一个游戏库理论软件

/*
  This file contains the implementation information that had been in globals.h,
and also the various implementation files that formerly resided in the Utils
subdirectory of the Pelican distribution.  
*/

#include "pelutils.h"


/**************************************************************************/
/*********************** implementations from Mem.c ***********************/
/**************************************************************************/

/*
   **  Mem.c               Created 1-27-95                Birk Huber
   **
   **  Memory Management for Pelican Shell. 
   **  
   **  Maintains storage for the basic unit of storage from which
   **  lists are built.
   ** 
   **  A node consists of left,and right (values,type) combinations, and
   **  a boolean for garbage collection. The values are often pointers to
   **  other structures wich must be freed when nodes are freed.
   **
   ** The Free_Stack is used to store a list of (known) free nodes, 
   ** The Local_Stack points to a list of pointers to nodes
   **                           which are known to be in use.
   **               
   **  Any time a new_node is requested and the Free_Stack is 
   **  empty garbage collection is initiated. Garbage collection 
   **  proceeds by  first marking all nodes accessable from the 
   **  Local_Stack and then putting the rest on the free list.
   **
   **  Any time garbage collection fails node_more_store() is called
   **  to add another block of nodes to the pool of available nodes.
   **
 */

#define BLOCKSIZE 10000
#define YES 0
#define NO 1

#define Node_LT(n) ((n->LT))
#define Node_L(n) ((n->L))
#define Node_RT(n) ((n->RT))
#define Node_R(n) ((n->R))
#define Node_Marked(n) ((n)->Mark)
#define Node_Unset_Mark(n)((n)->Mark=NO)
#define Node_Set_Mark(n)((n)->Mark=YES)

static int node_gc();
/* static int mark(); */
static int node_more_store();
static node node_free(node N);




struct node_t {
    int LT, RT, Mark;
    union {
	void *ptr;
	int ival;
	double dval;
    } L, R;
};

/* 
   ** 
 */
typedef struct node_block_t *node_block;
struct node_block_t {
    struct node_t store[BLOCKSIZE];
    struct node_block_t *next;
};



static int N_MALLOC = 0;	/*number of mallocs called from module */
static int N_FREE = 0;		/*number of frees called from this module */
static node_block Node_Store = 0;	/*beginning of node storage */
static node Free_List = 0;	/*top of free node list */
static local_v Locals_Stack = 0;	/*stack of  declared pointers 
					   into node storage */



node node_set_ptr(node N, void *v, int tp, int side)
{
    if (N == 0)
	bad_error("null node to node_set_ptr");
    if (side == LEFT) {
	N->L.ptr = v;
	N->LT = tp;
    } else if (side == RIGHT) {
	N->R.ptr = v;
	N->RT = tp;
    } else
	bad_error("bad side given in node_set_ptr");
    return N;
}

node node_set_int(node N, int v, int tp, int side)
{
    if (N == 0)
	bad_error("null node to node_set_int");
    if (side == LEFT) {
	N->L.ival = v;
	N->LT = tp;
    } else if (side == RIGHT) {
	N->R.ival = v;
	N->RT = tp;
    } else
	bad_error("bad side given in node_set_int");
    return N;
}


node node_set_double(node N, double v, int tp, int side)
{
    if (N == 0)
	bad_error("null node to node_set_double");
    if (side == LEFT) {
	N->L.dval = v;
	N->LT = tp;
    } else if (side == RIGHT) {
	N->R.dval = v;
	N->RT = tp;
    } else
	bad_error("bad side given in node_set_double");
    return N;
}



int node_get_int(node N, int side)
{
    if (N == 0)
	bad_error("null node to node_get_int");
    if (side == LEFT)
	return N->L.ival;
    else if (side == RIGHT)
	return N->R.ival;
    bad_error("bad side given in node_get_int");
    return 0;
}
double node_get_double(node N, int side)
{
    if (N == 0)
	bad_error("null node to node_get_ptr");
    if (side == LEFT)
	return N->L.dval;
    else if (side == RIGHT)
	return N->R.dval;
    bad_error("bad side given in node_get_double");
    return 0;
}

void *node_get_ptr(node N, int side)
{
    if (N == 0)
	bad_error("null node to node_get_ptr");
    if (side == LEFT)
	return N->L.ptr;
    else if (side == RIGHT)
	return N->R.ptr;
    bad_error("bad side given in node_get_ptr");
    return 0;
}

int node_set_type(node N, int Tp, int side)
{
    if (N == 0)
	bad_error("null node to node_get_type");
    if (side == LEFT)
	return N->LT;
    else if (side == RIGHT)
	return N->RT=Tp;
    bad_error("bad side given in node_get_type");
    return 0;
}
int node_get_type(node N, int side)
{
    if (N == 0)
	bad_error("null node to node_get_type");
    if (side == LEFT)
	return N->LT;
    else if (side == RIGHT)
	return N->RT;
    bad_error("bad side given in node_get_type");
    return 0;
}


node Cons(node N1, node N2)
{
    node Res;
    LOCS(2);
    PUSH_LOC(N1);
    PUSH_LOC(N2);
    Res = node_new();
    node_set_ptr(Res, (void *) N1, NODE, LEFT);
    node_set_ptr(Res, (void *) N2, NODE, RIGHT);
    POP_LOCS();
    return Res;
}

node Car(node N1)
{
    if (N1 == 0)
        return 0;
    return (node) node_get_ptr(N1, LEFT);
}

node Cdr(node N1)
{
    if (N1 == 0)
        return 0;
    return (node) node_get_ptr(N1, RIGHT);
}

int node_atomp(node N1)
{
    
    if ((N1!=0) && (node_get_type(N1, LEFT)) == NODE)
        return FALSE;
    else
        return TRUE;
}

int node_nullp(node N1)
{
    if (N1 == 0)
        return TRUE;
    else
        return FALSE;
}






char *mem_strdup(char *str){
  /*   char *strdup(char *); CAN'T DECLARE BUILTINS UNDER C++ */
  N_MALLOC++;
  return strdup(str);
}
void *mem_malloc(int sz)
{
    N_MALLOC++;
    return (void *) malloc(sz);
}
void mem_free(void *ptr)
{
    N_FREE++;
    free(ptr);
}

static node node_free(node N)
{
    Node_LT(N) = NODE;
    Node_L(N).ptr = 0;
    Node_RT(N) = NODE;
    Node_R(N).ptr = Free_List;
    Free_List = N;
    return N;
}

/* 
   **  storage is stored in blocks of size BLOCKSIZEg. whenever
   **  node_new is called and garbage collection fails to produce 
   **  new nodes (because there is no more free storage) 
   **  node_more_store() is called. 
   **  It is responcible for 
   **     a) claiming another block of nodes with malloc
   **     b) adding this block to the storage list
   **     c) putting all the new blocks on the free list.
   **  finally if this is the first block to be created the locals stack
   **  must be initialized.
 */
static int node_more_store()
{
    int i;
    node_block next_node = 0;
  
    next_node = (node_block) malloc(sizeof(struct node_block_t));
    if (next_node == 0) {
#ifdef LOG_PRINT
	fprintf(stderr, "malloc failing in node_more_store\n")
#endif
;
	return FALSE;
    }
    next_node->next = Node_Store;
    Node_Store = next_node;
    for (i = 0; i < BLOCKSIZE; i++)
	Node_Unset_Mark(node_free(Node_Store->store + i));

    return TRUE;
}


int node_init_store()
{
    if (node_more_store() == FALSE)
	bad_error("node_init_store failing");
    return TRUE;
}



void node_free_store()
{
    int i;
    node_block junk;
    printf("in free_store()\n");

    while (Node_Store != 0) {
	/* free any space held by elements in the block */
	for (i = 0; i < BLOCKSIZE; i++)
	    atom_free(Node_Store->store + i);
	Node_Store = (junk = Node_Store)->next;
	free((char *) junk);
    }
    printf("N_malloc = %d,  N_free=%d;=\n \n", N_MALLOC, N_FREE);
}


/* 
   ** Allocate nodes from free list-- If no nodes available initiate
   ** a garbage collection.  Note: routines which call new-node directly
   ** must protect their arguments, and localvariables themselve rather
   ** than make any assumptions about wheather they have been saved.
 */

node node_new()
{
    node res;
    if (Free_List != 0) {
	res = Free_List;
	Free_List = (node) node_get_ptr(Free_List, RIGHT);
	node_set_ptr(res, (void *) 0, NODE, LEFT);
	node_set_ptr(res, (void *) 0, NODE, RIGHT);
	return res;
    }
    if (node_gc() != 0)
	return node_new();
    if (node_more_store() != FALSE)
	return node_new();
#ifdef LOPG_PRINT  
  fprintf(stderr, "out of nodes: system not giving more memory\n")
#endif
;
    abort();
    return node_new();
}

/*
   ** void node_push_local(node *local)
   **   puts the address of a local variable onto the Locals_Stack stack 
   **   ( of starting points for garbage collection). 
   **
   ** void node_pop_local()
   **     removes one ptr off the Locals_Stack stack.
 */

void print_locals_stack(void)
{
    local_v ptr;
    ptr = Locals_Stack;
    printf("printing local stack \n");
    while (ptr != 0) {
	node_print(*(ptr->val));
	ptr = ptr->next;
    }
    printf(" done \n");
}

void node_push_local(local_v loc, node * val)
{
#ifdef MEM_DEBUG
  if (Locals_Stack == loc)
    bad_error("trying to make circular stack\n");
#endif

    loc->next = Locals_Stack;
    loc->val = val;
    Locals_Stack = loc;
}

void node_pop_local()
{
    if (Locals_Stack == 0)
	bad_error("poping empty local stack");
    Locals_Stack = Locals_Stack->next;
}




/*
   **  Mark all nodes accessable from a node n.
   **  if n is marked Yes then both its subtrees are already 
   **  marked and should be skipped. 
   **  otherwise cal mark on any pointers to nodes stored in the 
   **  node (is_node is used to check this)
 */
static int mark(node n)
{
    if ((n != 0) && (Node_Marked(n) == NO)) {
	Node_Set_Mark(n);
	if (Node_LT(n) == NODE && Node_L(n).ptr != 0)
	    mark((node) Node_L(n).ptr);
	else if (Node_LT(n) == NPTR && Node_L(n).ptr != 0)
	    mark(*((node *) Node_L(n).ptr));
	if (Node_RT(n) == NODE && Node_R(n).ptr != 0)
	    mark((node) Node_R(n).ptr);
	else if (Node_RT(n) == NPTR && Node_R(n).ptr != 0)
	    mark(*((node *) Node_R(n).ptr));
	return 0;
    }
    return 1;
}

/*
   ** Collect garbage
 */
static int node_gc()
{
    int i, free_cnt = 0;
    node_block next_block = Node_Store;
    local_v ptr;
#ifdef LOG_PRINT   
  fprintf(stdout, "Colecting Garbage .. ")
#endif
;
    fflush(stdout);

    /*call mark on variables in local list */
    ptr = Locals_Stack;
    while (ptr != 0) {
	mark(*(ptr->val));
	ptr = ptr->next;
    }

    /* now put anything that is not already marked on the free_list */
    while (next_block != 0) {
	for (i = 0; i < BLOCKSIZE; i++) {
	    if (Node_Marked(next_block->store + i) == YES)
		Node_Unset_Mark(next_block->store + i);
	    else {
		atom_free(next_block->store + i);
		node_free(next_block->store + i);
		free_cnt++;
	    }
	}
	next_block = next_block->next;
    }

#ifdef LOG_PRINT   
 fprintf(stdout, "Done  %d nodes freed\n", free_cnt)
#endif
;
    fflush(stdout);
    return free_cnt;
}


/**************************************************************************/
/********************** implementations from error.c **********************/
/**************************************************************************/

#ifdef GAMBIT_EXCEPTIONS
ErrorInPelican::~ErrorInPelican() { }

gText ErrorInPelican::Description(void) const
{
  return "Error somewhere in Pelican";
}
#endif

void bad_error(char *m)     /* generates an error message and aborts*/
{
#ifdef GAMBIT_EXCEPTIONS
  throw ErrorInPelican();
#endif

 #ifdef LOG_PRINT
       fprintf(stderr /* was Pel_Err */,"%s\n",m)
#endif
;
        exit(1);
}

void warning(char *m){
#ifdef LOG_PRINT
fprintf(stderr /* was Pel_Err */,"Warning:%s\n",m)
#endif
;}


/**************************************************************************/
/*********************** implementations from Rand.c **********************/
/**************************************************************************/

void srand48(long int seedval);

// WARNING: RDM added the following just to get to compile under BCC
//            I have no idea if this is correct!!!  
#ifdef __BORLANDC__
void srand48(long int seedval)
{
  srand(seedval);
}
#endif // __BORLANDC__
/*
** rand_seed  -- seed the random number generator with seedval.
*/
void rand_seed(long int seedval){ srand48(seedval);}

/*
**rand_int  -- return a random integer r with low<=r<=high
**             it produces double between low and high and rounds
**              by adding .5-epsilon and truncating, (if we just add
**              .5 then there is a slight chance we could end up with
**              high+1.)
*/
int rand_int(int low, int high){
      return (int)(low+drand48()*(high-low)+.499999999999); 
}



/*
**rand_double  -- return a random integer r with low<=r<=high
*/