/[ascend]/trunk/ascend/compiler/bit.c
ViewVC logotype

Contents of /trunk/ascend/compiler/bit.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2316 - (show annotations) (download) (as text)
Tue Dec 14 05:42:21 2010 UTC (8 years, 7 months ago) by jpye
File MIME type: text/x-csrc
File size: 9081 byte(s)
Documentation refactoring; trying to make the doxygen documentation generated for libascend a little more
navigable.
1 /*
2 * Bit List Manipulation Routines
3 * by Tom Epperly
4 * Version: $Revision: 1.8 $
5 * Version control file: $RCSfile: bit.c,v $
6 * Date last modified: $Date: 1997/09/08 18:07:31 $
7 * Last modified by: $Author: ballan $
8 *
9 * This file is part of the Ascend Language Interpreter.
10 *
11 * Copyright (C) 1990, 1993, 1994 Thomas Guthrie Epperly
12 *
13 * The Ascend Language Interpreter is free software; you can redistribute
14 * it and/or modify it under the terms of the GNU General Public License as
15 * published by the Free Software Foundation; either version 2 of the
16 * License, or (at your option) any later version.
17 *
18 * The Ascend Language Interpreter is distributed in hope that it will be
19 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 * General Public License for more details.
22 *
23 * You should have received a copy of the GNU General Public License along with
24 * the program; if not, write to the Free Software Foundation, Inc., 675
25 * Mass Ave, Cambridge, MA 02139 USA. Check the file named COPYING.
26 */
27
28 #include "bit.h"
29
30 #include <stdio.h>
31 #include <assert.h>
32 #include <ascend/utilities/ascConfig.h>
33
34 #include <ascend/utilities/ascMalloc.h>
35 #include <ascend/utilities/ascPanic.h>
36
37 #define BLENGTH(bl) ((bl)->length)
38
39 typedef unsigned char byte;
40
41 struct BitList *CreateBList(unsigned long int len)
42 {
43 register struct BitList *result;
44 register unsigned long num_bytes;
45 register char *ptr;
46 num_bytes = len >> 3; /* divide by 8 */
47 if (len & 0x07) num_bytes++;
48 result =
49 (struct BitList *)ascmalloc((unsigned)(sizeof(struct BitList)+num_bytes));
50 result->length = len;
51 /* clear the memory */
52 ptr = (char *)((unsigned long)result+(unsigned long)sizeof(struct BitList));
53 ascbzero(ptr,(int)num_bytes);
54 AssertAllocatedMemory((char *)result,sizeof(struct BitList)+num_bytes);
55 return result;
56 }
57
58 struct BitList *CreateFBList(unsigned long int len)
59 {
60 register struct BitList *result;
61 register unsigned long c;
62 result = CreateBList(len);
63 AssertContainedMemory(result,sizeof(struct BitList));
64 /* the following should be memset, plus cleanup of unused bits */
65 for(c=0;c<len;SetBit(result,c++));
66 return result;
67 }
68
69 struct BitList *ExpandBList(struct BitList *bl, unsigned long int len)
70 {
71 register unsigned orig_len,old_bytes,new_bytes;
72 register struct BitList *result;
73 AssertContainedMemory(bl,sizeof(struct BitList));
74 orig_len = BLength(bl);
75 assert(len>=orig_len);
76 old_bytes = orig_len >> 3;
77 if (orig_len & 0x07) old_bytes++;
78 new_bytes = len >> 3;
79 if (len & 0x07) new_bytes++;
80 if (new_bytes > old_bytes) {
81 result =
82 (struct BitList *)
83 ascrealloc((char *)bl,(unsigned)(new_bytes+sizeof(struct BitList)));
84 ascbzero((char *)((unsigned long)result+sizeof(struct BitList)+
85 (unsigned long)old_bytes),(int)(new_bytes-old_bytes));
86 }
87 else result = bl;
88 AssertAllocatedMemory(result,sizeof(struct BitList)+new_bytes);
89 result->length = len;
90 return result;
91 }
92
93 struct BitList *ExpandFBList(struct BitList *bl, unsigned long int len)
94 {
95 register unsigned long oldlen;
96 AssertContainedMemory(bl,sizeof(struct BitList));
97 oldlen = BLength(bl);
98 bl = ExpandBList(bl,len);
99 while(oldlen<len) SetBit(bl,oldlen++);
100 AssertContainedMemory(bl,sizeof(struct BitList));
101 return bl;
102 }
103
104 void DestroyBList(struct BitList *bl)
105 {
106 AssertContainedMemory(bl,sizeof(struct BitList));
107 bl->length = 0;
108 ascfree((char *)bl);
109 }
110
111 struct BitList *CopyBList(CONST struct BitList *bl)
112 {
113 register struct BitList *copy;
114 register unsigned long num_bytes;
115 num_bytes = BLENGTH(bl) >> 3; /* divide by 8 */
116 if (BLENGTH(bl) & 0x07) num_bytes++;
117 AssertAllocatedMemory(bl,sizeof(struct BitList)+num_bytes);
118 copy =
119 (struct BitList *)ascmalloc((unsigned)(sizeof(struct BitList)+num_bytes));
120 ascbcopy((char *)bl,(char *)copy,(int)(sizeof(struct BitList)+num_bytes));
121 AssertAllocatedMemory(bl,sizeof(struct BitList)+num_bytes);
122 return copy;
123 }
124
125 void OverwriteBList(CONST struct BitList *bl, struct BitList *target)
126 {
127 register unsigned long num_bytes;
128
129 assert(bl!=target);
130 assert(bl!=NULL);
131 assert(target!=NULL);
132
133 if (BLENGTH(bl) != BLENGTH(target)) {
134 ASC_PANIC("src and target bitlists of uneven size");
135 }
136 num_bytes = BLENGTH(bl) >> 3; /* divide by 8- the assumed bits/char */
137 if (BLENGTH(bl) & 0x07) num_bytes++;
138
139 AssertAllocatedMemory(bl,sizeof(struct BitList)+num_bytes);
140 AssertAllocatedMemory(target,sizeof(struct BitList)+num_bytes);
141
142 ascbcopy((char *)bl,(char *)target,(int)(sizeof(struct BitList)+num_bytes));
143 }
144
145 unsigned long BitListBytes(CONST struct BitList *bl)
146 {
147 register unsigned long num_bytes;
148 if (bl==NULL) return 0;
149 num_bytes = BLENGTH(bl) >> 3; /* divide by 8 */
150 if (BLENGTH(bl) & 0x07) num_bytes++;
151 return (sizeof(struct BitList)+num_bytes);
152 }
153
154 void SetBit(struct BitList *bl, unsigned long int pos)
155 {
156 register byte *ptr;
157 register unsigned bit;
158 AssertContainedMemory(bl,sizeof(struct BitList));
159 ptr = (byte *)((unsigned long)bl+sizeof(struct BitList)+(pos >> 3));
160 AssertContainedIn(bl,ptr);
161 bit = pos & 0x07;
162 *ptr = *ptr | (byte)(1 << bit);
163 }
164
165 void ClearBit(struct BitList *bl, unsigned long int pos)
166 {
167 register byte *ptr;
168 register unsigned bit;
169 AssertContainedMemory(bl,sizeof(struct BitList));
170 ptr = (byte *)((unsigned long)bl+sizeof(struct BitList)+(pos >> 3));
171 AssertContainedIn(bl,ptr);
172 bit = pos & 0x07;
173 *ptr = *ptr & (byte)(~(1 << bit));
174 }
175
176 void CondSetBit(struct BitList *bl, unsigned long int pos, int cond)
177 {
178 register byte *ptr;
179 register unsigned bit;
180 AssertContainedMemory(bl,sizeof(struct BitList));
181 ptr = (byte *)((unsigned long)bl+sizeof(struct BitList)+(pos >> 3));
182 AssertContainedIn(bl,ptr);
183 bit = pos & 0x07;
184 if (cond)
185 *ptr = *ptr | (byte)(1 << bit);
186 else
187 *ptr = *ptr & (byte)(~(1 << bit));
188 }
189
190 int ReadBit(CONST struct BitList *bl, unsigned long int pos)
191 {
192 register byte *ptr;
193 register unsigned bit;
194 AssertContainedMemory(bl,sizeof(struct BitList));
195 ptr = (byte *)((unsigned long)bl+sizeof(struct BitList)+(pos >> 3));
196 AssertContainedIn(bl,ptr);
197 bit = pos & 0x07;
198 return (*ptr & (1 << bit));
199 }
200
201 void IntersectBLists(struct BitList *bl1, CONST struct BitList *bl2)
202 {
203 register byte *ptr1;
204 register CONST byte *ptr2;
205 register unsigned long num_bytes;
206 AssertContainedMemory(bl1,sizeof(struct BitList));
207 AssertContainedMemory(bl2,sizeof(struct BitList));
208 if (BLENGTH(bl1)!=BLENGTH(bl2)) {
209 FPRINTF(ASCERR,"Bad bit list intersection\n");
210 return;
211 }
212 ptr1 = (byte *)((unsigned long)bl1+sizeof(struct BitList));
213 ptr2 = (byte *)((unsigned long)bl2+sizeof(struct BitList));
214 num_bytes = BLENGTH(bl1) >> 3; /* divided by 8 */
215 if (BLENGTH(bl1) & 0x07) num_bytes++;
216 while(num_bytes-->0) {
217 AssertContainedIn(bl1,ptr1);
218 AssertContainedIn(bl2,ptr2);
219 *ptr1 = *ptr1 & *ptr2;
220 ptr1++;
221 ptr2++;
222 }
223 }
224
225 void UnionBLists(struct BitList *bl1, CONST struct BitList *bl2)
226 {
227 register byte *ptr1;
228 register CONST byte *ptr2;
229 register unsigned long num_bytes;
230 AssertContainedMemory(bl1,sizeof(struct BitList));
231 AssertContainedMemory(bl2,sizeof(struct BitList));
232 if (BLENGTH(bl1)!=BLENGTH(bl2)) {
233 FPRINTF(ASCERR,"Bad bit list union\n");
234 return;
235 }
236 ptr1 = (byte *)((unsigned long)bl1+sizeof(struct BitList));
237 ptr2 = (byte *)((unsigned long)bl2+sizeof(struct BitList));
238 num_bytes = BLENGTH(bl1) >> 3; /* divided by 8 */
239 if (BLENGTH(bl1) & 0x07) num_bytes++;
240 while(num_bytes-->0) {
241 *ptr1 = *ptr1 | *ptr2;
242 AssertContainedIn(bl1,ptr1);
243 AssertContainedIn(bl2,ptr2);
244 ptr1++;
245 ptr2++;
246 }
247 }
248
249 unsigned long BLengthF(CONST struct BitList *bl)
250 {
251 AssertContainedMemory(bl,sizeof(struct BitList));
252 return bl->length;
253 }
254
255 int BitListEmpty(CONST struct BitList *bl)
256 {
257 register unsigned long num_bytes;
258 register unsigned char *ptr;
259 AssertContainedMemory(bl,sizeof(struct BitList));
260 num_bytes = bl->length >> 3;
261 if (bl->length & 0x07) num_bytes++;
262 ptr = (unsigned char *)((unsigned long)bl+
263 (unsigned long)sizeof(struct BitList));
264 while(num_bytes--){
265 AssertContainedIn(bl,ptr);
266 if (*(ptr++)) return 0;
267 }
268 return 1;
269 }
270
271 int CompBList(struct BitList *b1, struct BitList *b2)
272 {
273 unsigned long c,len;
274 len = BLength(b1);
275 for (c=1;c<=len;c++){
276 if (ReadBit(b1,c)!=ReadBit(b2,c)) {
277 return 0;
278 }
279 }
280 return 1;
281 }
282
283
284 unsigned long FirstNonZeroBit(CONST struct BitList *bl)
285 {
286 register unsigned long num_bytes,c;
287 register unsigned char *ptr,ch;
288 num_bytes = bl->length >> 3;
289 if (bl->length & 0x07) num_bytes++;
290 AssertAllocatedMemory(bl,sizeof(struct BitList)+num_bytes);
291 ptr = (unsigned char *)((unsigned long)bl+
292 (unsigned long)sizeof(struct BitList));
293 c = num_bytes;
294 while ((!(*ptr))&&(num_bytes)) {
295 AssertContainedIn(bl,ptr);
296 ptr++;
297 num_bytes--;
298 }
299 if (num_bytes==0) return bl->length+1;
300 c -= num_bytes;
301 c <<= 3; /* multiply by 8 */
302 ch = *ptr;
303 AssertContainedIn(bl,ptr);
304 while (!(ch & 1)) {
305 ch >>= 1;
306 c++;
307 }
308 return c;
309 }

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