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 __NUMPAIR_H_SEEN__
#define __NUMPAIR_H_SEEN__

/**
 *  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 /* __NUMPAIR_H_SEEN__ */

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