clpr/cfloat.m: free list handling

[Fergus Henderson]

[This is in relation to a discussion with Peter Schachte,
it may not be of much interest to anyone else.]

Regarding the following comment in clpr/cfloat.m:
 
/* XXX efficiency could be improved -- we should use a free list here */

Actually the comment is wrong. I considered making that change (see
diff below), but using a free list is likely to be less efficient than
the current doubly-linked list approach.  The doubly-linked list
approach uses slightly more memory, but allocation/deallocation
costs are cheaper in the common case, because there's no need to
unlink the cell from the free list and link it into the choice point
stack or vice versa -- the cell is already correctly linked, all that
needs to be done is to set the current_cp variable.

Hence I won't commit the diff below, instead I'll just delete the
XXX comment.

Index: cfloat.m
===================================================================
RCS file: /home/staff/zs/imp/clpr/cfloat.m,v
retrieving revision 1.2
diff -u -u -c -r1.2 cfloat.m
/usr/local/bin/diff: conflicting specifications of output style
*** 1.2	1997/09/02 13:54:00
--- cfloat.m	1997/09/02 14:29:08
***************
*** 318,324 ****
  **	- the CLP(R) trail
  ** The Mercury trail contains function trail entries which point to
  ** the cfloat.m choice point stack.
! ** The cfloat.m choice point stack is represented a doubly-linked list.
  ** Its entries store the values of the CLP(R) global variables, including
  ** the `trtop' variable, which points to the top of the CLP(R) trail.
  */
--- 318,325 ----
  **	- the CLP(R) trail
  ** The Mercury trail contains function trail entries which point to
  ** the cfloat.m choice point stack.
! ** The cfloat.m choice point stack is represented a singly-linked list,
! ** with a free list used to minimize the cost of memory allocation.
  ** Its entries store the values of the CLP(R) global variables, including
  ** the `trtop' variable, which points to the top of the CLP(R) trail.
  */
***************
*** 327,353 ****
  	int slack_id;
  	int solver_id;
  	int trtop;
- 	struct ML_cfloat_choicepoint *prev;
  	struct ML_cfloat_choicepoint *next;
  } ML_cfloat_choicepoint;
  
  ML_cfloat_choicepoint ML_cfloat_first_choicepoint;
  ML_cfloat_choicepoint * ML_cfloat_current_cp = &ML_cfloat_first_choicepoint;
! 
! /* XXX efficiency could be improved -- we should use a free list here */
  
  #define ML_cfloat_next_choicepoint()					\
! 	( ML_cfloat_current_cp->next == NULL ?				\
! 		(ML_cfloat_current_cp->next = make(ML_cfloat_choicepoint), \
! 		ML_cfloat_current_cp->next->next = NULL,		\
! 		ML_cfloat_current_cp->next->prev = ML_cfloat_current_cp,\
  		ML_cfloat_current_cp = ML_cfloat_current_cp->next)	\
! 	:								\
! 		(ML_cfloat_current_cp = ML_cfloat_current_cp->next)	\
! 	)
! #define ML_cfloat_prev_choicepoint() \
! 	(ML_cfloat_current_cp = ML_cfloat_current_cp->prev)
! 		
  #define ML_cfloat_maybe_trail_solver()				\
  	do {							\
  		if (stamp != MR_current_choicepoint_id()) {	\
--- 328,363 ----
  	int slack_id;
  	int solver_id;
  	int trtop;
  	struct ML_cfloat_choicepoint *next;
  } ML_cfloat_choicepoint;
  
  ML_cfloat_choicepoint ML_cfloat_first_choicepoint;
  ML_cfloat_choicepoint * ML_cfloat_current_cp = &ML_cfloat_first_choicepoint;
! ML_cfloat_choicepoint * ML_cfloat_cp_freelist = NULL;
  
  #define ML_cfloat_next_choicepoint()					\
! 	do {								\
! 		ML_cfloat_choicepoint *tmp;				\
! 		if (ML_cfloat_cp_freelist == NULL) {			\
! 			tmp = make(ML_cfloat_choicepoint);		\
! 			tmp->next = ML_cfloat_current_cp;		\
! 			ML_cfloat_current_cp = tmp;			\
! 		} else {						\
! 			tmp = ML_cfloat_cp_freelist;			\
! 			ML_cfloat_cp_freelist = ML_cfloat_cp_freelist->next;\
! 			tmp->next = ML_cfloat_current_cp;		\
! 			ML_cfloat_current_cp = tmp;			\
! 		}							\
! 	} while (0)
! #define ML_cfloat_prev_choicepoint()					\
! 	do {								\
! 		ML_cfloat_choicepoint *tmp = ML_cfloat_current_cp,	\
  		ML_cfloat_current_cp = ML_cfloat_current_cp->next)	\
! 		tmp->next = ML_cfloat_cp_freelist,			\
! 		ML_cfloat_cp_freelist = tmp,				\
! 		ML_cfloat_current_cp					\
! 	} while (0)
! 
  #define ML_cfloat_maybe_trail_solver()				\
  	do {							\
  		if (stamp != MR_current_choicepoint_id()) {	\
***************
*** 365,371 ****
  :- pragma(c_code, "
  
  void ML_cfloat_trail_solver(void) {
! 	ML_cfloat_choicepoint *choicepoint = ML_cfloat_next_choicepoint();
  	choicepoint->stamp = stamp;
  	choicepoint->slack_id = slack_id;
  	choicepoint->solver_id = solver_id;
--- 375,384 ----
  :- pragma(c_code, "
  
  void ML_cfloat_trail_solver(void) {
! 	ML_cfloat_choicepoint *choicepoint;
! 
! 	ML_cfloat_next_choicepoint();
! 	choicepoint = ML_cfloat_current_cp;
  	choicepoint->stamp = stamp;
  	choicepoint->slack_id = slack_id;
  	choicepoint->solver_id = solver_id;

-- 
Fergus Henderson <fjh at cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3         |     -- the last words of T. S. Garp.