generic/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..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

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

/** Function required by the iterator defined for Numlist_p's. */
typedef void (*NPLFunc)(int, 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, int 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(int 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, int num);

/**
 * <!--  int 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 int 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 int NumpairNumberInList(Numlist_p nlp, int number);

/** 
 * <!--  NumpairNumberInListHintedDecreasing(nlp,number,hint);         -->
 * <!--  int 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 int NumpairNumberInListHintedDecreasing(Numlist_p nlp,
                                               int number,
                                               int *hint);

/** 
 * <!--  prev = NumpairPrevNumber(nlp,last,hint);                      -->
 * <!--  int *hint;                                                    -->
 * <!--  int 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 int NumpairPrevNumber(Numlist_p nlp, int last, int *hint);

/** 
 * <!--  prev = NumpairNextNumber(nlp,last,hint);                      -->
 * <!--  int *hint;                                                    -->
 * <!--  int 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 int NumpairNextNumber(Numlist_p nlp, int last, int *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);           -->
 * <!--  int lowlimit;                                                 -->
 * Returns the first number that is both common to nlp1, nlp2
 * and >= lowlimit.
 * If no number > lowlimit is common, returns 0.
 */
extern int NumpairGTIntersection(Numlist_p nlp1, Numlist_p nlp2, int 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 int NumpairIntersectionLTHinted(Numlist_p nlp1,
                                       int *hint1,
                                       Numlist_p nlp2,
                                       int *hint2,
                                       int highlimit);

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