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

/** @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	/*
2	* 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	/** @file
33	* Numlist management routines.
34	* Numlists are lists of integer scalars and ranges.
35	* Valid numbers are 1..GL_INT_MAX.
36	* 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	*/
49
50	#ifndef ASC_NUMPAIR_H
51	#define ASC_NUMPAIR_H
52
53	/** @addtogroup compiler Compiler
54	@{
55	*/
56
57	/**
58	* NUMLISTUSESPOOL == TRUE allows the list module to use pool.[ch] to
59	* manage list memory overhead. Performance is enhanced this way.
60	*
61	* NUMLISTUSESPOOL == FALSE removes the pool dependency completely, at
62	* a performance penalty.
63	*/
64	#define NUMLISTUSESPOOL TRUE
65
66	typedef int nlbool;
67
68	/** A numlist pair. */
69	typedef struct numpair_list *Numlist_p;
70
71	/** Function required by the iterator defined for Numlist_p's. */
72	typedef void (NPLFunc)(GLint, void );
73
74	/**
75	* <!-- enlp = NumpairExpandableList(enlp,size); -->
76	* Expands the size of nlp, which must be created
77	* with NumpairExpandableList(). If nlp is NULL, creates
78	* the list with the size specified.
79	* If insufficient memory to create or expand to size
80	* required, returns NULL.
81	* Size is the total number of separate scalars and
82	* ranges that might be desired.
83	*/
84	extern Numlist_p NumpairExpandableList(Numlist_p nlp, GLint size);
85
86	/** <!-- NumpairDestroyList(nlp); NumpairDestroyList(enlp); -->
87	* Destroy a list. list may have come from
88	* NumpairCopyList or NumpairExpandableList.
89	*/
90	extern void NumpairDestroyList(Numlist_p nlp);
91
92	/**
93	* <!-- nlp = NumpairElementary(index); -->
94	* Returns an efficiently allocated numlist containing the
95	* scalar with value index. nlp is not expandable.
96	*/
97	extern Numlist_p NumpairElementary(GLint indexv);
98
99	/**
100	* <!-- nlp2 = NumpairCopyList(nlp); -->
101	* <!-- Numlist_p nlp2, nlp; -->
102	* Returns an efficiently allocated numpair_list containing the
103	* data of the list given. The data in this list may or may not
104	* be in a shared allocation, depending on the list size.
105	* In either case, it is not expandable.
106	*/
107	extern Numlist_p NumpairCopyList(Numlist_p nlp);
108
109	/**
110	* <!-- NumpairCalcUnion(enlp1,nlp2,scratchenlp); -->
111	* <!-- Numlist_p enlp1,nlp2,scratchenlp; -->
112	* Calculates the union of enlp1, nlp2 and leaves the result in
113	* enlp1. scratchenlp is used if needed and is left in an indeterminate
114	* state.
115	*/
116	extern void NumpairCalcUnion(Numlist_p nlp1,
117	Numlist_p nlp2,
118	Numlist_p scratchenlp);
119
120	/**
121	* <!-- NumpairCalcIntersection(nlp1,nlp2,enlp3); -->
122	* <!-- Numlist_p nlp1,nlp2,enlp3; -->
123	* Calculates the intersection of nlp1, nlp2 and leaves the result in enlp3.
124	*/
125	extern void NumpairCalcIntersection(Numlist_p nlp1,
126	Numlist_p nlp2,
127	Numlist_p enlp3);
128
129	/**
130	* <!-- nlp = NumpairCombineLists(nlpgl,s1,s2); -->
131	* <!-- Numlist_p s1,s2; -->
132	* <!-- struct gl_list_t *nlpgl; -->
133	* <!-- Numlist_p nlp; -->
134	* Takes a gl_list of Numlist_p and merges the data
135	* from all of them into one list. The new list is allocated
136	* in the efficient fashion of NumpairCopyList().
137	* If nlpgl is empty, returns NULL.
138	* The arguments s1, s2 must be two numlists created to be
139	* expandable with NumpairExpandableList.
140	* They are scratch spaces. The data in them on return is
141	* unpredictable.
142	*/
143	extern Numlist_p NumpairCombineLists(struct gl_list_t *nlpgl,
144	Numlist_p s1,
145	Numlist_p s2);
146
147	/**
148	* <!-- NumpairAppendList(enlp,num); -->
149	* Inserts a num to an expandable numlist.
150	* typically O(1), sometimes O(len(enlp)).
151	*/
152	extern void NumpairAppendList(Numlist_p enlp, GLint num);
153
154	/**
155	* <!-- GLint NumpairListLen(nlp); -->
156	* Returns the number of scalars and ranges currently
157	* stored in nlp. List capacity may be larger if nlp is
158	* expandable, but you do not need to know that.
159	*/
160	extern GLint NumpairListLen(Numlist_p nlp);
161
162	/**
163	* <!-- NumpairClearList(enlp); -->
164	* Resets the number of elements stored in enlp to 0.
165	* List capacity may obviously be larger.
166	* enlp must be expandable.
167	*/
168	extern void NumpairClearList(Numlist_p enlp);
169
170	/**
171	* <!-- NumpairNumberInList(nlp,number); -->
172	* Returns 1 if number is in list and 0 if it is not.
173	* Uses a binary search.
174	*/
175	extern nlbool NumpairNumberInList(Numlist_p nlp, GLint number);
176
177	/**
178	* <!-- NumpairNumberInListHintedDecreasing(nlp,number,hint); -->
179	* <!-- GLint number, *hint; -->
180	* Returns 1 if number is in list at or to the left of
181	* hint. hint is ignored for small lists.
182	* To initiate a series of searches, call with *hint == -1.
183	* Cost O(len) per call worst case, but O(1) if used * properly.
184	* Note that if hint value is incorrect, this may lie about
185	* whether number is in the list.
186	*/
187	extern nlbool NumpairNumberInListHintedDecreasing(Numlist_p nlp,
188	GLint number,
189	GLint *hint);
190
191	/**
192	* <!-- prev = NumpairPrevNumber(nlp,last,hint); -->
193	* <!-- GLint *hint; -->
194	* <!-- GLint last; -->
195	* Returns the next lower number in the list preceding
196	* last. If last is 0, returns highest
197	* number in the list. *hint should be the output from the
198	* last call to this function on nlp, or -1. This function lets
199	* you write a list iteration.
200	* Remember that 0 is never a valid list element.
201	* (0 may be a valid *hint, however.)
202	* If last is not found in the list, then returns 0.
203	*/
204	extern GLint NumpairPrevNumber(Numlist_p nlp, GLint last, GLint *hint);
205
206	/**
207	* <!-- prev = NumpairNextNumber(nlp,last,hint); -->
208	* <!-- GLint *hint; -->
209	* <!-- GLint last; -->
210	* Returns the next higher number in the list following
211	* last. If last is >= end of list, wraps around and returns 0.
212	* *hint should be the output from the
213	* last call to this function on nlp, or 0. This function lets
214	* you write a list iteration.
215	* Remember that 0 is never really a valid list element.
216	*/
217	extern GLint NumpairNextNumber(Numlist_p nlp, GLint last, GLint *hint);
218
219	/** <!-- NumpairListIterate(nlp,func,userdata); -->
220	* Calls func(i,userdata) for every integer i listed in nlp.
221	*/
222	extern void NumpairListIterate(Numlist_p nlp, NPLFunc func, void *userdata);
223
224	/**
225	* <!-- common = NumpairGTIntersection(nlp1,nlp2,lowlimit); -->
226	* <!-- GLint lowlimit; -->
227	* Returns the first number that is both common to nlp1, nlp2
228	* and >= lowlimit.
229	* If no number > lowlimit is common, returns 0.
230	*/
231	extern GLint NumpairGTIntersection(Numlist_p nlp1, Numlist_p nlp2, GLint lowlimit);
232
233	/**
234	* <!-- last = NumpairIntersectionLTHinted(nlp1,&hint1,nlp2,&hint2,highlimit); -->
235	* Return the highest intersection of nlp1 and nlp2 with value < highlimit
236	* and using hint1, hint2 from previous calls on the same list to simplify
237	* the search. On the first call of a series in the same list pair with
238	* DECREASING highlimit hint1 and hint2 should be -1 and highlimit
239	* should be 0 or INT_MAX. If no intersection is found, returns 0.
240	*/
241	extern GLint NumpairIntersectionLTHinted(Numlist_p nlp1,
242	GLint *hint1,
243	Numlist_p nlp2,
244	GLint *hint2,
245	GLint highlimit);
246
247	/**
248	* Returns the count of integers represented by the list.
249	* Tolerates all sorts of crappy input and returns 0 in those cases.
250	*/
251	extern GLint NumpairCardinality(Numlist_p nlp);
252
253	/**
254	* <!-- NumpairClearPuddle(); -->
255	* Clears up the internal queue of lists that have room left in
256	* them to share with other nonexpandable lists.
257	* This should be called before exiting the compiler.
258	* Clearing the puddle will not disturb lists still in use,
259	* it will merely prevent them from being used as puddle
260	* donors.
261	*/
262	extern void NumpairClearPuddle(void);
263
264	#ifdef NUMLISTEXPORTIO
265	/**
266	* <!-- NLPWrite(fp,nlp); -->
267	* Temporarily exported function for debugging.
268	* fp may be NULL, --> stderr output.
269	*/
270	extern void NLPWrite(FILE *fp, Numlist_p nlp);
271	#define NLPWRITE 1
272	#endif
273
274	/* @} */
275
276	#endif /* ASC_NUMPAIR_H */
277