/* ![[previous]](../icons/n_left.png)
![[next]](../icons/n_right.png)
![[first]](../icons/first.png)
![[last]](../icons/last.png)
![[top]](../icons/n_top.png)
![[bottom]](../icons/bottom.png)
![[index]](../icons/index.png)
![[help]](../icons/help.png)
*/
This source file includes following definitions.
- idset_open
- idset_empty
- idset_add
- idset_contains
- idset_first
- idset_next
- idset_count
- idset_close
1 /*
2 * Copyright (c) 2005, 2006, 2007 Tama Communications Corporation
3 *
4 * This file is part of GNU GLOBAL.
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 3 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, see <http://www.gnu.org/licenses/>.
18 */
19
20 #ifdef HAVE_CONFIG_H
21 #include <config.h>
22 #endif
23 #include <stdlib.h>
24 #ifdef HAVE_LIMITS_H
25 #include <limits.h>
26 #endif
27 #include "checkalloc.h"
28 #include "die.h"
29 #include "idset.h"
30
31 #ifndef CHAR_BIT
32 #define CHAR_BIT 8
33 #endif
34 #undef LONG_BIT
35 /** maybe 32 or 64 */
36 #define LONG_BIT (sizeof(long) * CHAR_BIT)
37
38 /**
39 * @CODE{idset->min} is initialized to #END_OF_ID.
40 * (You may use @CODE{idset->max} instead of @CODE{idset->min}.)
41 */
42 #define IS_EMPTY(idset) ((idset)->min == END_OF_ID ? 1 : 0)
43
44 /** @file
45 Idset: usage and memory status
46
47 @code
48 idset->set
49 []
50
51 idset = idset_open(21) 000000000000000000000___________
52 v
53 idset_add(idset, 1) 010000000000000000000___________
54 v
55 idset_add(idset, 2) 011000000000000000000___________
56 v
57 idset_add(idset, 20) 011000000000000000001___________
58
59 idset_contains(idset, 2) == true
60 idset_contains(idset, 3) == false
61
62 idset_close(idset) []
63 @endcode
64
65 Idset's index always start from 0 according to the custom of C language. <br>
66 I you want to treat 1-20 then you @EMPH{must} invoke idset_open() with a argument 21.
67
68 @code
69 idset = idset_open(21);
70 idset_add(idset, 0); => OK
71 idset_add(idset, 1); => OK
72 ...
73 idset_add(idset, 20); => OK
74 idset_add(idset, 21); => ERROR (idset_add: id is out of range.)
75 @endcode
76
77 The range of value is from 0 to the maximum value expressible by unsigned integer - 1. <br>
78 You should define index as an unsigned integer, and use #END_OF_ID like follows:
79
80 @code
81 unsigned int id;
82 for (id = idset_first(set); id != END_OF_ID; id = idset_next(set))
83 -- processing about an id --
84 @endcode
85 */
86 /**
87 * bit mask table
88 * Prepare all bit mask for performance.
89 */
90 static unsigned long *bit;
91
92 /**
93 * Allocate memory for new idset.
94 */
95 IDSET *
96 idset_open(unsigned int size)
97 {
98 IDSET *idset = (IDSET *)check_malloc(sizeof(IDSET));
99 int i;
100
101 if (bit == NULL) {
102 bit = (unsigned long *)check_calloc(sizeof(unsigned long), LONG_BIT);
103 for (i = 0; i < LONG_BIT; i++)
104 bit[i] = 1UL << i;
105 }
106 idset->set = (unsigned long *)check_calloc(sizeof(unsigned long), (size + LONG_BIT - 1) / LONG_BIT);
107 idset->size = size;
108 /*
109 * Initialize all id expressions using invalid value.
110 * END_OF_ID means 'no value' or 'out of range'.
111 */
112 idset->min = idset->max = idset->lastid = END_OF_ID;
113 return idset;
114 }
115 /**
116 * Return true if @a idset is empty.
117 *
118 * @param[in] idset idset structure
119 * @return 1: empty, 0: not empty
120 */
121 int
122 idset_empty(IDSET *idset)
123 {
124 return IS_EMPTY(idset);
125 }
126 /**
127 * Add @a id to the @a idset.
128 *
129 * @param[in] idset idset structure
130 * @param[in] id id number
131 */
132 void
133 idset_add(IDSET *idset, unsigned int id)
134 {
135 int empty = IS_EMPTY(idset);
136
137 if (id >= idset->size)
138 die("idset_add: id is out of range.");
139 idset->set[id / LONG_BIT] |= bit[id % LONG_BIT];
140 if (empty)
141 idset->max = idset->min = id;
142 else if (id > idset->max)
143 idset->max = id;
144 else if (id < idset->min)
145 idset->min = id;
146 }
147 /**
148 * Whether or not @a idset includes specified @a id.
149 *
150 * @param[in] idset idset structure
151 * @param[in] id id number
152 * @return true: contains, false: doesn't contain
153 */
154 int
155 idset_contains(IDSET *idset, unsigned int id)
156 {
157 if (IS_EMPTY(idset))
158 return 0;
159 if (id < idset->min || id > idset->max)
160 return 0;
161 return (idset->set[id / LONG_BIT] & bit[id % LONG_BIT]) != 0;
162 }
163 /**
164 * Get first id.
165 *
166 * @param[in] idset idset structure
167 * @return id (#END_OF_ID: end of id)
168 *
169 */
170 unsigned int
171 idset_first(IDSET *idset)
172 {
173 /* There is no need to check whether idset is empty
174 because idset->min is initialized with END_OF_ID. */
175 return idset->lastid = idset->min;
176 }
177 /**
178 * Get next id.
179 *
180 * @param[in] idset idset structure
181 * @return id (#END_OF_ID: end of id)
182 *
183 */
184 unsigned int
185 idset_next(IDSET *idset)
186 {
187 unsigned int i, limit;
188 int index0, index1;
189
190 if (IS_EMPTY(idset))
191 return END_OF_ID;
192 if (idset->lastid >= idset->max)
193 return END_OF_ID;
194 limit = idset->max / LONG_BIT + 1;
195 index0 = idset->lastid / LONG_BIT;
196 index1 = idset->lastid % LONG_BIT;
197 for (i = ++index1; i < LONG_BIT; i++)
198 if (bit[i] & idset->set[index0])
199 return idset->lastid = index0 * LONG_BIT + i;
200 index0++;
201 for (i = index0; i < limit && idset->set[i] == 0; i++)
202 ;
203 if (i >= limit)
204 die("idset_next: internal error.");
205 index0 = i;
206 for (i = 0; i < LONG_BIT; i++)
207 if (bit[i] & idset->set[index0])
208 return idset->lastid = index0 * LONG_BIT + i;
209 die("idset_next: internal error.");
210 }
211 /**
212 * Return the number of bits.
213 *
214 * @param[in] idset idset structure
215 * @return number of bits
216 */
217 unsigned int
218 idset_count(IDSET *idset)
219 {
220 unsigned int id, count = 0;
221
222 for (id = idset_first(idset); id != END_OF_ID; id = idset_next(idset))
223 count++;
224 return count;
225 }
226 /**
227 * Free memory for the idset.
228 */
229 void
230 idset_close(IDSET *idset)
231 {
232 free(idset->set);
233 free(idset);
234 }
/* ![[top]](../icons/top.png)
![[bottom]](../icons/n_bottom.png)
*/