ascend/compiler/numlist.h

/*
 *  numlist.h
 *  by Ben Allan
 *  December 20, 1997
 *  Part of ASCEND
 *  Version: $Revision: 1.4 $
 *  Version control file: $RCSfile: numlist.h,v $
 *  Date last modified: $Date: 1998/06/16 16:38:44 $
 *  Last modified by: $Author: mthomas $
 *
 *  This file is part of the Ascend Language Interpreter.
 *
 *  Copyright (C) 1998 Carnegie Mellon University
 *
 *  The Ascend Language Interpreter is free software; you can
 *  redistribute it and/or modify it under the terms of the GNU
 *  General Public License as published by the Free Software
 *  Foundation; either version 2 of the License, or (at your option)
 *  any later version.
 *
 *  The Ascend Language Interpreter is distributed in hope that it
 *  will be useful, but WITHOUT ANY WARRANTY; without even the implied
 *  warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 *  See the GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with the program; if not, write to the Free Software
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139 USA.  Check
 *  the file named COPYING.
 */

/** @file
 *  Numlist management routines.
 *  Numlists are lists of integer scalars and ranges.
 *  Valid numbers are 1..GL_INT_MAX.
 *  Numbers are stored in increasing order, and condensed to ranges
 *  where possible.
 *  For storage efficiency, only lists you request to be expandable
 *  are expandable. All others are of a fixed length.
 *  Expandable numlists are noted enlp, and regular cheap ones are just nlp.
 *  <pre>
 *  When #including numlist.h, make sure these files are #included first:
 *         #include "utilities/ascConfig.h"
 *         #include "general/list.h"
 *  </pre>
 *
 *  building with -DNUMPAIRSELFTEST causes numlist to compile a simple main().
 */

#ifndef ASC_NUMPAIR_H
#define ASC_NUMPAIR_H

#include <ascend/utilities/config.h>

/** @addtogroup compiler Compiler
    @{
*/

/**
 *  NUMLISTUSESPOOL == TRUE allows the list module to use pool.[ch] to
 *  manage list memory overhead. Performance is enhanced this way.
 *
 *  NUMLISTUSESPOOL == FALSE removes the pool dependency completely, at
 *  a performance penalty.
 */
#define NUMLISTUSESPOOL TRUE

typedef int nlbool;

/** A numlist pair. */
typedef struct numpair_list *Numlist_p;

/** Function required by the iterator defined for Numlist_p's. */
typedef void (*NPLFunc)(GLint, void *);

/** 
 * <!--  enlp = NumpairExpandableList(enlp,size);                      -->
 * Expands the size of nlp, which must be created
 * with NumpairExpandableList(). If nlp is NULL, creates
 * the list with the size specified.
 * If insufficient memory to create or expand to size
 * required, returns NULL.
 * Size is the total number of separate scalars and
 * ranges that might be desired. 
 */
extern Numlist_p NumpairExpandableList(Numlist_p nlp, GLint size);

/** <!--  NumpairDestroyList(nlp); NumpairDestroyList(enlp);           -->
 * Destroy a list. list may have come from
 * NumpairCopyList or NumpairExpandableList.
 */
extern void NumpairDestroyList(Numlist_p nlp);

/** 
 * <!--  nlp = NumpairElementary(index);                               -->
 * Returns an efficiently allocated numlist containing the
 * scalar with value index. nlp is not expandable.
 */
extern Numlist_p NumpairElementary(GLint indexv);

/** 
 * <!--  nlp2 = NumpairCopyList(nlp);                                  -->
 * <!--  Numlist_p nlp2, nlp;                                          -->
 * Returns an efficiently allocated numpair_list containing the
 * data of the list given. The data in this list may or may not
 * be in a shared allocation, depending on the list size.
 * In either case, it is not expandable.
 */
extern Numlist_p NumpairCopyList(Numlist_p nlp);

/** 
 * <!--  NumpairCalcUnion(enlp1,nlp2,scratchenlp);                     -->
 * <!--  Numlist_p enlp1,nlp2,scratchenlp;                             -->
 * Calculates the union of enlp1, nlp2 and leaves the result in
 * enlp1. scratchenlp is used if needed and is left in an indeterminate
 * state.
 */
extern void NumpairCalcUnion(Numlist_p nlp1,
                             Numlist_p nlp2,
                             Numlist_p scratchenlp);

/**
 * <!--  NumpairCalcIntersection(nlp1,nlp2,enlp3);                     -->
 * <!--  Numlist_p nlp1,nlp2,enlp3;                                    -->
 * Calculates the intersection of nlp1, nlp2 and leaves the result in enlp3.
 */
extern void NumpairCalcIntersection(Numlist_p nlp1,
                                    Numlist_p nlp2,
                                    Numlist_p enlp3);

/** 
 * <!--  nlp = NumpairCombineLists(nlpgl,s1,s2);                       -->
 * <!--  Numlist_p s1,s2;                                              -->
 * <!--  struct gl_list_t *nlpgl;                                      -->
 * <!--  Numlist_p nlp;                                                -->
 * Takes a gl_list of Numlist_p and merges the data
 * from all of them into one list.  The new list is allocated
 * in the efficient fashion of NumpairCopyList().
 * If nlpgl is empty, returns NULL.
 * The arguments s1, s2 must be two numlists created to be
 * expandable with NumpairExpandableList.
 * They are scratch spaces. The data in them on return is
 * unpredictable.
 */
extern Numlist_p NumpairCombineLists(struct gl_list_t *nlpgl,
                                     Numlist_p s1,
                                     Numlist_p s2);

/**
 * <!--  NumpairAppendList(enlp,num);                                  -->
 * Inserts a num to an expandable numlist.
 * typically O(1), sometimes O(len(enlp)).
 */
extern void NumpairAppendList(Numlist_p enlp, GLint num);

/**
 * <!--  GLint NumpairListLen(nlp);                                      -->
 * Returns the number of scalars and ranges currently
 * stored in nlp. List capacity may be larger if nlp is
 * expandable, but you do not need to know that.
 */
extern GLint NumpairListLen(Numlist_p nlp);

/** 
 * <!--  NumpairClearList(enlp);                                       -->
 * Resets the number of elements stored in enlp to 0.
 * List capacity may obviously be larger.
 * enlp must be expandable.
 */
extern void NumpairClearList(Numlist_p enlp);

/** 
 * <!--  NumpairNumberInList(nlp,number);                              -->
 * Returns 1 if number is in list and 0 if it is not.
 * Uses a binary search.
 */
extern nlbool NumpairNumberInList(Numlist_p nlp, GLint number);

/** 
 * <!--  NumpairNumberInListHintedDecreasing(nlp,number,hint);         -->
 * <!--  GLint number, *hint;                                            -->
 * Returns 1 if number is in list at or to the left of
 * hint. hint is ignored for small lists.
 * To initiate a series of searches, call with *hint == -1.
 * Cost O(len) per call worst case, but O(1) if used * properly.
 * Note that if hint value is incorrect, this may lie about
 * whether number is in the list.
 */
extern nlbool NumpairNumberInListHintedDecreasing(Numlist_p nlp,
                                               GLint number,
                                               GLint *hint);

/** 
 * <!--  prev = NumpairPrevNumber(nlp,last,hint);                      -->
 * <!--  GLint *hint;                                                    -->
 * <!--  GLint last;                                                     -->
 * Returns the next lower number in the list preceding
 * last. If last is 0, returns highest
 * number in the list. *hint should be the output from the
 * last call to this function on nlp, or -1.  This function lets
 * you write a list iteration.
 * Remember that 0 is never a valid list element.
 * (0 may be a valid *hint, however.)
 * If last is not found in the list, then returns 0.
 */
extern GLint NumpairPrevNumber(Numlist_p nlp, GLint last, GLint *hint);

/** 
 * <!--  prev = NumpairNextNumber(nlp,last,hint);                      -->
 * <!--  GLint *hint;                                                    -->
 * <!--  GLint last;                                                     -->
 * Returns the next higher number in the list following
 * last. If last is >= end of list, wraps around and returns 0.
 * *hint should be the output from the
 * last call to this function on nlp, or 0.  This function lets
 * you write a list iteration.
 * Remember that 0 is never really a valid list element.
 */
extern GLint NumpairNextNumber(Numlist_p nlp, GLint last, GLint *hint);

/** <!--  NumpairListIterate(nlp,func,userdata);                       -->
 *  Calls func(i,userdata) for every integer i listed in nlp.
 */
extern void NumpairListIterate(Numlist_p nlp, NPLFunc func, void *userdata);

/** 
 * <!--  common = NumpairGTIntersection(nlp1,nlp2,lowlimit);           -->
 * <!--  GLint lowlimit;                                                 -->
 * Returns the first number that is both common to nlp1, nlp2
 * and >= lowlimit.
 * If no number > lowlimit is common, returns 0.
 */
extern GLint NumpairGTIntersection(Numlist_p nlp1, Numlist_p nlp2, GLint lowlimit);

/** 
 * <!--  last = NumpairIntersectionLTHinted(nlp1,&hint1,nlp2,&hint2,highlimit); -->
 * Return the highest intersection of nlp1 and nlp2 with value < highlimit
 * and using hint1, hint2 from previous calls on the same list to simplify
 * the search. On the first call of a series in the same list pair with
 * DECREASING highlimit hint1 and hint2 should be -1 and highlimit
 * should be 0 or INT_MAX. If no intersection is found, returns 0.
 */
extern GLint NumpairIntersectionLTHinted(Numlist_p nlp1,
                                       GLint *hint1,
                                       Numlist_p nlp2,
                                       GLint *hint2,
                                       GLint highlimit);

/**
 * Returns the count of integers represented by the list.
 * Tolerates all sorts of crappy input and returns 0 in those cases.
 */
extern GLint NumpairCardinality(Numlist_p nlp);

/**
 * <!--  NumpairClearPuddle();                                         -->
 * Clears up the internal queue of lists that have room left in
 * them to share with other nonexpandable lists.
 * This should be called before exiting the compiler.
 * Clearing the puddle will not disturb lists still in use,
 * it will merely prevent them from being used as puddle
 * donors.
 */
extern void NumpairClearPuddle(void);

#ifdef NUMLISTEXPORTIO
/**
 * <!--  NLPWrite(fp,nlp);                                             -->
 * Temporarily exported function for debugging.
 * fp may be NULL, --> stderr output.
 */
extern void NLPWrite(FILE *fp, Numlist_p nlp);
#define NLPWRITE 1
#endif

/* @} */

#endif /* ASC_NUMPAIR_H */

1	jds	54	/*
2	aw0a	1	* numlist.h
3			* by Ben Allan
4			* December 20, 1997
5			* Part of ASCEND
6			* Version: $Revision: 1.4 $
7			* Version control file: $RCSfile: numlist.h,v $
8			* Date last modified: $Date: 1998/06/16 16:38:44 $
9			* Last modified by: $Author: mthomas $
10			*
11			* This file is part of the Ascend Language Interpreter.
12			*
13			* Copyright (C) 1998 Carnegie Mellon University
14			*
15			* The Ascend Language Interpreter is free software; you can
16			* redistribute it and/or modify it under the terms of the GNU
17			* General Public License as published by the Free Software
18			* Foundation; either version 2 of the License, or (at your option)
19			* any later version.
20			*
21			* The Ascend Language Interpreter is distributed in hope that it
22			* will be useful, but WITHOUT ANY WARRANTY; without even the implied
23			* warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
24			* See the GNU General Public License for more details.
25			*
26			* You should have received a copy of the GNU General Public License
27			* along with the program; if not, write to the Free Software
28			* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139 USA. Check
29			* the file named COPYING.
30			*/
31
32	jds	54	/** @file
33			* Numlist management routines.
34			* Numlists are lists of integer scalars and ranges.
35	ballan	2036	* Valid numbers are 1..GL_INT_MAX.
36	jds	54	* Numbers are stored in increasing order, and condensed to ranges
37			* where possible.
38			* For storage efficiency, only lists you request to be expandable
39			* are expandable. All others are of a fixed length.
40			* Expandable numlists are noted enlp, and regular cheap ones are just nlp.
41			* <pre>
42			* When #including numlist.h, make sure these files are #included first:
43			* #include "utilities/ascConfig.h"
44			* #include "general/list.h"
45			* </pre>
46			*
47			* building with -DNUMPAIRSELFTEST causes numlist to compile a simple main().
48	aw0a	1	*/
49	jds	54
50	johnpye	1066	#ifndef ASC_NUMPAIR_H
51			#define ASC_NUMPAIR_H
52	aw0a	1
53	jpye	2037	#include <ascend/utilities/config.h>
54
55	johnpye	1067	/** @addtogroup compiler Compiler
56	johnpye	1066	@{
57			*/
58
59	jds	54	/**
60	aw0a	1	* NUMLISTUSESPOOL == TRUE allows the list module to use pool.[ch] to
61			* manage list memory overhead. Performance is enhanced this way.
62			*
63			* NUMLISTUSESPOOL == FALSE removes the pool dependency completely, at
64			* a performance penalty.
65			*/
66			#define NUMLISTUSESPOOL TRUE
67
68	ballan	2036	typedef int nlbool;
69
70	jds	54	/** A numlist pair. */
71	aw0a	1	typedef struct numpair_list *Numlist_p;
72
73	jds	54	/** Function required by the iterator defined for Numlist_p's. */
74	ballan	2036	typedef void (NPLFunc)(GLint, void );
75	aw0a	1
76	ben.allan	33	/**
77	jds	54	* <!-- enlp = NumpairExpandableList(enlp,size); -->
78	aw0a	1	* Expands the size of nlp, which must be created
79	jds	54	* with NumpairExpandableList(). If nlp is NULL, creates
80	aw0a	1	* the list with the size specified.
81			* If insufficient memory to create or expand to size
82			* required, returns NULL.
83			* Size is the total number of separate scalars and
84			* ranges that might be desired.
85			*/
86	ballan	2036	extern Numlist_p NumpairExpandableList(Numlist_p nlp, GLint size);
87	aw0a	1
88	jds	54	/** <!-- NumpairDestroyList(nlp); NumpairDestroyList(enlp); -->
89	aw0a	1	* Destroy a list. list may have come from
90			* NumpairCopyList or NumpairExpandableList.
91			*/
92	jds	54	extern void NumpairDestroyList(Numlist_p nlp);
93	aw0a	1
94	ben.allan	33	/**
95	jds	54	* <!-- nlp = NumpairElementary(index); -->
96	aw0a	1	* Returns an efficiently allocated numlist containing the
97			* scalar with value index. nlp is not expandable.
98			*/
99	ballan	2036	extern Numlist_p NumpairElementary(GLint indexv);
100	aw0a	1
101	ben.allan	33	/**
102	jds	54	* <!-- nlp2 = NumpairCopyList(nlp); -->
103			* <!-- Numlist_p nlp2, nlp; -->
104	aw0a	1	* Returns an efficiently allocated numpair_list containing the
105			* data of the list given. The data in this list may or may not
106			* be in a shared allocation, depending on the list size.
107			* In either case, it is not expandable.
108			*/
109	jds	54	extern Numlist_p NumpairCopyList(Numlist_p nlp);
110	aw0a	1
111	ben.allan	33	/**
112	jds	54	* <!-- NumpairCalcUnion(enlp1,nlp2,scratchenlp); -->
113			* <!-- Numlist_p enlp1,nlp2,scratchenlp; -->
114	aw0a	1	* Calculates the union of enlp1, nlp2 and leaves the result in
115			* enlp1. scratchenlp is used if needed and is left in an indeterminate
116			* state.
117			*/
118	jds	54	extern void NumpairCalcUnion(Numlist_p nlp1,
119			Numlist_p nlp2,
120			Numlist_p scratchenlp);
121	aw0a	1
122	jds	54	/**
123			* <!-- NumpairCalcIntersection(nlp1,nlp2,enlp3); -->
124			* <!-- Numlist_p nlp1,nlp2,enlp3; -->
125			* Calculates the intersection of nlp1, nlp2 and leaves the result in enlp3.
126	aw0a	1	*/
127	jds	54	extern void NumpairCalcIntersection(Numlist_p nlp1,
128			Numlist_p nlp2,
129			Numlist_p enlp3);
130	aw0a	1
131	ben.allan	33	/**
132	jds	54	* <!-- nlp = NumpairCombineLists(nlpgl,s1,s2); -->
133			* <!-- Numlist_p s1,s2; -->
134			* <!-- struct gl_list_t *nlpgl; -->
135			* <!-- Numlist_p nlp; -->
136	aw0a	1	* Takes a gl_list of Numlist_p and merges the data
137	jds	54	* from all of them into one list. The new list is allocated
138			* in the efficient fashion of NumpairCopyList().
139	aw0a	1	* If nlpgl is empty, returns NULL.
140			* The arguments s1, s2 must be two numlists created to be
141			* expandable with NumpairExpandableList.
142			* They are scratch spaces. The data in them on return is
143			* unpredictable.
144			*/
145	jds	54	extern Numlist_p NumpairCombineLists(struct gl_list_t *nlpgl,
146			Numlist_p s1,
147			Numlist_p s2);
148	aw0a	1
149	jds	54	/**
150			* <!-- NumpairAppendList(enlp,num); -->
151	aw0a	1	* Inserts a num to an expandable numlist.
152			* typically O(1), sometimes O(len(enlp)).
153			*/
154	ballan	2036	extern void NumpairAppendList(Numlist_p enlp, GLint num);
155	aw0a	1
156	jds	54	/**
157	ballan	2036	* <!-- GLint NumpairListLen(nlp); -->
158	aw0a	1	* Returns the number of scalars and ranges currently
159			* stored in nlp. List capacity may be larger if nlp is
160			* expandable, but you do not need to know that.
161			*/
162	ballan	2036	extern GLint NumpairListLen(Numlist_p nlp);
163	aw0a	1
164	ben.allan	33	/**
165	jds	54	* <!-- NumpairClearList(enlp); -->
166	aw0a	1	* Resets the number of elements stored in enlp to 0.
167			* List capacity may obviously be larger.
168			* enlp must be expandable.
169			*/
170	jds	54	extern void NumpairClearList(Numlist_p enlp);
171	aw0a	1
172	ben.allan	33	/**
173	jds	54	* <!-- NumpairNumberInList(nlp,number); -->
174	aw0a	1	* Returns 1 if number is in list and 0 if it is not.
175			* Uses a binary search.
176			*/
177	ballan	2036	extern nlbool NumpairNumberInList(Numlist_p nlp, GLint number);
178	aw0a	1
179	ben.allan	33	/**
180	jds	54	* <!-- NumpairNumberInListHintedDecreasing(nlp,number,hint); -->
181	ballan	2036	* <!-- GLint number, *hint; -->
182	aw0a	1	* Returns 1 if number is in list at or to the left of
183	jds	54	* hint. hint is ignored for small lists.
184	aw0a	1	* To initiate a series of searches, call with *hint == -1.
185			* Cost O(len) per call worst case, but O(1) if used * properly.
186	jds	54	* Note that if hint value is incorrect, this may lie about
187	aw0a	1	* whether number is in the list.
188			*/
189	ballan	2036	extern nlbool NumpairNumberInListHintedDecreasing(Numlist_p nlp,
190			GLint number,
191			GLint *hint);
192	aw0a	1
193	ben.allan	33	/**
194	jds	54	* <!-- prev = NumpairPrevNumber(nlp,last,hint); -->
195	ballan	2036	* <!-- GLint *hint; -->
196			* <!-- GLint last; -->
197	aw0a	1	* Returns the next lower number in the list preceding
198			* last. If last is 0, returns highest
199			* number in the list. *hint should be the output from the
200			* last call to this function on nlp, or -1. This function lets
201			* you write a list iteration.
202			* Remember that 0 is never a valid list element.
203			* (0 may be a valid *hint, however.)
204			* If last is not found in the list, then returns 0.
205			*/
206	ballan	2036	extern GLint NumpairPrevNumber(Numlist_p nlp, GLint last, GLint *hint);
207	aw0a	1
208	ben.allan	33	/**
209	jds	54	* <!-- prev = NumpairNextNumber(nlp,last,hint); -->
210	ballan	2036	* <!-- GLint *hint; -->
211			* <!-- GLint last; -->
212	aw0a	1	* Returns the next higher number in the list following
213			* last. If last is >= end of list, wraps around and returns 0.
214			* *hint should be the output from the
215			* last call to this function on nlp, or 0. This function lets
216			* you write a list iteration.
217			* Remember that 0 is never really a valid list element.
218			*/
219	ballan	2036	extern GLint NumpairNextNumber(Numlist_p nlp, GLint last, GLint *hint);
220	aw0a	1
221	jds	54	/** <!-- NumpairListIterate(nlp,func,userdata); -->
222			* Calls func(i,userdata) for every integer i listed in nlp.
223	aw0a	1	*/
224	jds	54	extern void NumpairListIterate(Numlist_p nlp, NPLFunc func, void *userdata);
225	aw0a	1
226	ben.allan	33	/**
227	jds	54	* <!-- common = NumpairGTIntersection(nlp1,nlp2,lowlimit); -->
228	ballan	2036	* <!-- GLint lowlimit; -->
229	aw0a	1	* Returns the first number that is both common to nlp1, nlp2
230			* and >= lowlimit.
231			* If no number > lowlimit is common, returns 0.
232			*/
233	ballan	2036	extern GLint NumpairGTIntersection(Numlist_p nlp1, Numlist_p nlp2, GLint lowlimit);
234	aw0a	1
235	ben.allan	33	/**
236	jds	54	* <!-- last = NumpairIntersectionLTHinted(nlp1,&hint1,nlp2,&hint2,highlimit); -->
237	aw0a	1	* Return the highest intersection of nlp1 and nlp2 with value < highlimit
238			* and using hint1, hint2 from previous calls on the same list to simplify
239			* the search. On the first call of a series in the same list pair with
240			* DECREASING highlimit hint1 and hint2 should be -1 and highlimit
241			* should be 0 or INT_MAX. If no intersection is found, returns 0.
242			*/
243	ballan	2036	extern GLint NumpairIntersectionLTHinted(Numlist_p nlp1,
244			GLint *hint1,
245	jds	54	Numlist_p nlp2,
246	ballan	2036	GLint *hint2,
247			GLint highlimit);
248	aw0a	1
249	jds	54	/**
250	aw0a	1	* Returns the count of integers represented by the list.
251			* Tolerates all sorts of crappy input and returns 0 in those cases.
252			*/
253	ballan	2036	extern GLint NumpairCardinality(Numlist_p nlp);
254	aw0a	1
255	jds	54	/**
256			* <!-- NumpairClearPuddle(); -->
257	aw0a	1	* Clears up the internal queue of lists that have room left in
258			* them to share with other nonexpandable lists.
259			* This should be called before exiting the compiler.
260			* Clearing the puddle will not disturb lists still in use,
261			* it will merely prevent them from being used as puddle
262			* donors.
263			*/
264			extern void NumpairClearPuddle(void);
265
266			#ifdef NUMLISTEXPORTIO
267	jds	54	/**
268			* <!-- NLPWrite(fp,nlp); -->
269			* Temporarily exported function for debugging.
270	aw0a	1	* fp may be NULL, --> stderr output.
271			*/
272	jds	54	extern void NLPWrite(FILE *fp, Numlist_p nlp);
273	aw0a	1	#define NLPWRITE 1
274			#endif
275
276	johnpye	1066	/* @} */
277	jds	54
278	johnpye	1066	#endif /* ASC_NUMPAIR_H */
279