/[ascend]/trunk/base/generic/utilities/set.h
ViewVC logotype

Contents of /trunk/base/generic/utilities/set.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 593 - (show annotations) (download) (as text)
Fri May 12 10:03:59 2006 UTC (13 years, 10 months ago) by johnpye
File MIME type: text/x-chdr
File size: 10513 byte(s)
Bumped version to 0.9.5.91.
Changed WITH_CUNIT_TESTS to WITH_CUNIT.
Added GCOV scons option.
Fixed up 'test' target for SCons.
Added lots of export symbols to libascend.so.

1 /*
2 * Set module
3 * by Karl Westerberg
4 * Created: 6/90
5 * Version: $Revision: 1.4 $
6 * Version control file: $RCSfile: set.h,v $
7 * Date last modified: $Date: 1997/07/18 12:04:30 $
8 * Last modified by: $Author: mthomas $
9 *
10 * This file is part of the Ascend Language Interpreter.
11 *
12 * Copyright (C) 1997 Carnegie Mellon University
13 *
14 * The Ascend Language Interpreter is free software; you can redistribute
15 * it and/or modify it under the terms of the GNU General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
18 *
19 * The Ascend Language Interpreter is distributed in hope that it will be
20 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
22 * General Public License for more details.
23 *
24 * You should have received a copy of the GNU General Public License
25 * along with the program; if not, write to the Free Software Foundation,
26 * Inc., 675 Mass Ave, Cambridge, MA 02139 USA. Check the file named
27 * COPYING. COPYING is in ../compiler.
28 */
29
30 /*
31 * Contents: Set module
32 *
33 * Authors: Karl Westerberg
34 *
35 * Dates: 06/90 - original version
36 *
37 * Description: This module is responsible for primitive manipulation
38 * of sets of integers (using a binary bit map technique).
39 * In particular, the set variables have domain
40 * {k in N | k < n}, where n is a fixed constant, which
41 * we will call the (bit-)size of the set. The sets are
42 * actually arrays of unsigned of appropriate length,
43 * and pointers to such arrays can actually be used in
44 * place of pointers returned by set_create() (although
45 * one must be careful not to destroy such sets with
46 * set_destroy()).
47 */
48
49 /** @file
50 * Integer set module.
51 * This module supports primitive manipulation of sets of positive
52 * integers. It provides functions for creating, adding to, removing
53 * from, querying, and destroying such sets. Note that much of the
54 * module's functionality is not used by ASCEND and is deprecated.
55 * <pre>
56 * Requires: #include "utilities/ascConfig.h"
57 * #include "utilities/ascMalloc.h"
58 * </pre>
59 */
60
61 #ifndef _set_h_seen
62 #define _set_h_seen
63
64 #define set_size(n) \
65 (((n)+((int)WORDSIZE-1))/(int)WORDSIZE)
66 /**<
67 * Returns the number of unsigned ints required to store a set of n bits.
68 * WORDSIZE is computed in ascConfig.h. Clients should not need to use
69 * this function directly. It is needed for other macro definitions in
70 * this file.
71 *
72 * @param n int, the number of bits (or ints) to store.
73 * @return The number of unsigned ints needed as an int.
74 */
75
76 #define set_create(n) \
77 (set_size(n)>0?((unsigned *)ascmalloc(sizeof(unsigned)*set_size(n))):NULL)
78 /**<
79 * Creates a new set of size n.
80 * The size indicates the maximum integer that the set can hold.
81 * The initial contents are garbage. The caller is responsible for
82 * deallocating the returned set using set_destroy().
83 *
84 * @param n int, the size for the new set.
85 * @return A pointer to the newly-created set (as an unsigned *), or NULL
86 * if (n <= 0) or memory could not be allocated.
87 */
88
89 #define set_destroy(set) \
90 (ascfree((POINTER)set))
91 /**<
92 * Destroys a set.
93 * The set should have been created using set_create().
94 *
95 * @param set unsigned *, the set to destroy.
96 * @return No return value.
97 */
98
99 #define set_ndx(k) \
100 ((k)/(int)WORDSIZE)
101 /**<
102 * Index into array of unsigned where element k's status is found.
103 * Clients should not need to use this function directly. It is
104 * needed for other macro definitions in this file.
105 *
106 * @param k int, the element whose index is needed.
107 * @return The index of k as an int.
108 */
109
110 /*
111 * previous definition: trying to get rid of mask.h
112 *
113 *#define set_mask(k) \
114 * mask_I_E((k)%WORDSIZE)
115 */
116 #define set_mask(k) \
117 (((unsigned)1) << ((k)%WORDSIZE))
118 /**<
119 * Returns an integer with the bit corresponding to element k turned on.
120 * Clients should not need to use this function directly. It is
121 * needed for other macro definitions in this file.
122 *
123 * @param k int, the element for which to turn on a bit.
124 * @return The bitmask for k as an unsigned int.
125 */
126
127 #define set_is_member(set,k) \
128 ((set[set_ndx(k)] & set_mask(k)) != 0)
129 /**<
130 * Tests whether element k belongs to a given set.
131 * It is assumed that 0 <= k < n, where n is the size of the set.
132 *
133 * @param set unsigned *, the set to check for k.
134 * @param k int, the element to evaluate.
135 * @return TRUE if k belongs to the given set, FALSE otherwise.
136 */
137
138 #define set_chk_is_member(set,k,n) \
139 ((k)>=0 && (k)<(n) && set_is_member(set,k))
140 /**<
141 * Tests whether element k belongs to a given set with validation.
142 * This is the same as set_is_member(), except that validation is
143 * first done to ensure k is within the range of set.
144 *
145 * @param set unsigned *, the set to check for k (non-NULL).
146 * @param k int, the element to validate and evaluate.
147 * @param n int, the size of the set.
148 * @return TRUE if k belongs to the given set, FALSE otherwise.
149 */
150
151 ASC_DLLSPEC(unsigned int *) set_null(unsigned int *set, int n);
152 /**<
153 * Clears a set so that it has no elements.
154 * The size of the set must be indicated.
155 * set may not be NULL (checked by assertion).
156 *
157 * @param set The set to clear (non-NULL).
158 * @param n The size of the set.
159 * @return Returns a pointer to the set.
160 */
161
162 ASC_DLLSPEC(void ) set_change_member(unsigned int *set, int k, boolean value);
163 /**<
164 * Adds or removes an element from a set.
165 * If value==TRUE, then k is added to the set. Otherwise k
166 * is taken out of the set. It is assumed that 0 <= k < n.
167 * set may not be NULL (checked by assertion).
168 *
169 * @param set The set to modify (non-NULL).
170 * @param k The element to add or remove.
171 * @param value Flag for action: TRUE -> k is added, FALSE -> k is removed.
172 */
173
174 #ifdef THIS_IS_DEAD_CODE
175
176 extern unsigned int *set_copy(unsigned int *set, unsigned int *target,
177 int n, int n2);
178 /**<
179 * <!-- set_copy(set,target,n,n2) -->
180 * <!-- unsigned *set, *target; -->
181 * <!-- int n,n2; -->
182 *
183 * Copies one set to another. The bit size of the source and
184 * target must be given. If the size of the target is less
185 * than the source, then the set is truncated. If the size of
186 * the target is more than the source, then the set is extended
187 * with 0's. It is assumed that the target has already been
188 * created. Returns the pointer to target.
189 * @deprecated This function is not in use or supported.
190 */
191
192 extern void set_change_member_rng(unsigned int *set,
193 int k1, int k2, boolean value);
194 /**<
195 * <!-- set_change_member_rng(set,k1,k2,value) -->
196 * <!-- unsigned *set; -->
197 * <!-- int k1, k2; -->
198 * <!-- boolean value; -->
199 *
200 * Changes the membership status for all elements
201 * in k1..k2 (see set_change_member). It is assumed
202 * that 0 <= k1,k2 < n.
203 * @deprecated This function is not in use or supported.
204 */
205
206 extern int set_find_next(unsigned int *set, int k, int n);
207 /**<
208 * <!-- next = set_find_next(set,k,n) -->
209 * <!-- int next; -->
210 * <!-- unsigned *set; -->
211 * <!-- int k, n; -->
212 *
213 * Returns the first member of set greater than k.
214 * If k=-1 upon entering, the minimum of the set is
215 * returned. If return>=n upon exiting, then there is no
216 * member in the set greater than k.
217 * @deprecated This function is not in use or supported.
218 */
219
220 extern int set_count(unsigned int *set, int n);
221 /**<
222 * <!-- count = set_count(set,n) -->
223 * <!-- int count; -->
224 * <!-- unsigned *set; -->
225 * <!-- int n; -->
226 *
227 * Returns the cardinality of the set.
228 * @deprecated This function is not in use or supported.
229 */
230
231 extern unsigned *set_complement(unsigned int *set, int n);
232 /**<
233 * <!-- set_complement(set,n) -->
234 * <!-- unsigned *set; -->
235 * <!-- int n; -->
236 *
237 * Removes all elements which are currently in the
238 * set and adds all elements which were not.
239 * Returns pointer to set.
240 * @deprecated This function is not in use or supported.
241 */
242
243 extern unsigned *set_intersect(unsigned int *set1,
244 unsigned int *set2,
245 int n, int n2);
246 /**<
247 * <!-- set_intersect(set,set2,n,n2) -->
248 * <!-- unsigned *set, *set2; -->
249 * <!-- int n,n2; -->
250 *
251 * Replaces set with the intersection of set and set2.
252 * The bit-sizes of each set must be given (if they are
253 * different, then set2 is effectively extended or truncated
254 * for purposes of computing intersection, although the
255 * size change does not actually occur).
256 * Returns the pointer to set, which has been modified.
257 * @deprecated This function is not in use or supported.
258 */
259
260 extern unsigned *set_union(unsigned int *set,
261 unsigned int *set2,
262 int n, int n2);
263 /**<
264 * <!-- set_union(set,set2,n,n2) -->
265 * <!-- unsigned *set, *set2; -->
266 * <!-- int n,n2; -->
267 *
268 * Replaces set with the union of set and set2.
269 * Size mismatch handled as for intersection.
270 * Returns the pointer to set, which has been modified.
271 * @deprecated This function is not in use or supported.
272 */
273
274 #endif /* THIS_IS_DEAD_CODE */
275
276 #endif /* _set_h_seen */
277

john.pye@anu.edu.au
ViewVC Help
Powered by ViewVC 1.1.22