1 /********************
2 This file is part of the software library CADLIB written by Conrad Ziesler
3 Copyright 2003, Conrad Ziesler, all rights reserved.
4
5 *************************
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19
20 ******************/
21 /* bitlist.c, routines for bit arrays
22
23 Conrad Ziesler
24
25 */
26
27 #include "debug.h"
28 #include "bitlist.h"
29
30
31
32
bitlist_new(int qty)33 bitlist_t * bitlist_new(int qty)
34 {
35 bitlist_t *bl;
36 int qbytes;
37 qbytes=(qty>>3)+1;
38
39 bl= malloc(sizeof(bitlist_t)+qbytes);
40 assert(bl!=NULL);
41 memset(bl,0,sizeof(bitlist_t)+qbytes);
42 bl->qty=qty;
43 bl->qbytes=qbytes;
44
45 return bl;
46 }
47
bitlist_free(bitlist_t * bl)48 void bitlist_free(bitlist_t *bl)
49 {
50 if(bl!=NULL)
51 free(bl);
52 }
53
bitlist_setall(bitlist_t * bl)54 void bitlist_setall(bitlist_t *bl)
55 {
56 memset(bl->data,0xff,bl->qbytes);
57 }
58
bitlist_clearall(bitlist_t * bl)59 void bitlist_clearall(bitlist_t *bl)
60 {
61 memset(bl->data,0,bl->qbytes);
62 }
63
64
bitlist_set(bitlist_t * bl,int index)65 int bitlist_set(bitlist_t *bl, int index)
66 {
67 int byte,bit,r=0;
68 if(index<0) return 0;
69 byte=index>>3;
70 bit=index-(byte<<3);
71 assert(byte<bl->qbytes);
72 if((bl->data[byte]&(1<<bit))!=0)r=1;
73 bl->data[byte]|=(1<<bit);
74 return r;
75 }
76
bitlist_test(bitlist_t * bl,int index)77 int bitlist_test(bitlist_t *bl, int index)
78 {
79 int byte,bit;
80 if(index<0) return 0;
81 byte=index>>3;
82 bit=index-(byte<<3);
83 assert(byte<bl->qbytes);
84 if((bl->data[byte]&(1<<bit))!=0)return 1;
85 return 0;
86 }
87
88
bitlist_clear(bitlist_t * bl,int index)89 int bitlist_clear(bitlist_t *bl, int index)
90 {
91 int byte,bit,r=0;
92 if(index<0) return 0;
93 byte=index>>3;
94 bit=index-(byte<<3);
95 assert(byte<bl->qbytes);
96 if((bl->data[byte]&(1<<bit))!=0)r=1;
97 bl->data[byte]&=~(1<<bit);
98 return 0;
99 }
100
101 /* realloc bitlist */
bitlist_resize(bitlist_t * bl,int qty)102 bitlist_t *bitlist_resize(bitlist_t *bl, int qty)
103 {
104 int oldqty;
105 int qbytes;
106 qbytes=(qty>>3)+1;
107 oldqty=bl->qty;
108
109 bl=realloc(bl,sizeof(bitlist_t)+qbytes);
110 assert(bl!=NULL);
111 if( (oldqty>>3) < (qbytes-(oldqty>>3)) )
112 memset(bl->data+(oldqty>>3),0,qbytes-(oldqty>>3));
113
114 bl->qty=qty;
115 bl->qbytes=qbytes;
116 return bl;
117 }
118
119
120 /* returns the index of the first bit set or cleared
121 from dir
122 */
123
bitlist_scan(bitlist_t * bl,int flags)124 int bitlist_scan(bitlist_t *bl, int flags)
125 {
126 int i,j;
127 assert(bl!=NULL);
128 switch(flags)
129 {
130 case (SCAN_FORWARD|SCAN_SET):
131 for(i=0;i<(bl->qbytes-1);i++)
132 {
133 if(bl->data[i]!=0)
134 {
135 for(j=(i<<3);j<bl->qty;j++)
136 if(bitlist_test(bl,j))return j;
137 }
138 }
139 break;
140 case (SCAN_FORWARD|SCAN_CLEAR):
141 for(i=0;i<(bl->qbytes-1);i++)
142 {
143 if( (bl->data[i])< ((unsigned char)0x00ff))
144 {
145
146 for(j=(i<<3);j<bl->qty;j++)
147 if(!bitlist_test(bl,j))return j;
148 }
149 }
150 break;
151
152 default:
153 assert(0);
154 }
155 return -1;
156 }
157
158
159
bitlist_copyhead(bitlist_t * dest,bitlist_t * src,int length)160 int bitlist_copyhead(bitlist_t *dest, bitlist_t *src, int length)
161 {
162 int i;
163 int finalbyte;
164 int finalbitoffset;
165 unsigned char a,b;
166 if(length>src->qty)length=src->qty;
167 if(length>dest->qty)length=dest->qty;
168
169 finalbyte=length>>3;
170 finalbitoffset=length-(finalbyte<<3);
171
172 for(i=0;i<finalbyte;i++)
173 dest->data[i]=src->data[i];
174
175 a=dest->data[finalbyte];
176 b=src->data[finalbyte];
177
178 for(i=0;i<finalbitoffset;i++)
179 a= (a & (~(1<<i)) ) | ((1<<i)&b) ;
180
181 dest->data[finalbyte]=a;
182 return length;
183 }
184