1 /*
2 * sid_list.h: Part of GNU CSSC.
3 *
4 *
5 * Copyright (C) 1997, 2001, 2007, 2008, 2009, 2010, 2011, 2014, 2019
6 * Free Software Foundation, Inc.
7 *
8 * This program is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program. If not, see <http://www.gnu.org/licenses/>.
20 *
21 * CSSC was originally Based on MySC, by Ross Ridge, which was
22 * placed in the Public Domain.
23 *
24 *
25 * Defines the template range_list.
26 */
27
28 #ifndef CSSC__SID_LIST_H__
29 #define CSSC__SID_LIST_H__
30
31 #include <cstdio>
32 #include <cstring>
33
34 #include "quit.h"
35
36
37 template <class TYPE>
38 struct range
39 {
40 TYPE from;
41 TYPE to;
42 range<TYPE> *next;
43 };
44
45 template <class TYPE>
46 class range_list
47 {
48 public:
49 // constructors & destructors.
50 ~range_list();
51 range_list();
52 range_list(const char *list);
53 range_list(range_list const &list);
54 range_list &operator =(range_list const &list);
55
56 // query functions.
57 int valid() const;
58 int empty() const;
59 int member(TYPE id) const;
60
61 // manipulation.
62 void invalidate();
63 range_list &merge (range_list const &list);
64 range_list &remove (range_list const &list);
65
66 // output.
67 int print(FILE *out) const;
68
69 private:
70 // Data members.
71 range<TYPE> *head;
72 int valid_flag;
73
74 // Implementation.
75 void destroy();
76 static range<TYPE> *do_copy_list(range<TYPE> *);
77
78 int clean(); // clean the range list eliminating overlaps etc.
79 };
80
81
range_list(const char * list)82 template <class TYPE> range_list<TYPE>::range_list(const char *list)
83 : head(NULL), valid_flag(1)
84 {
85 const char *s = list;
86 if (s == NULL || *s == '\0')
87 {
88 return;
89 }
90
91 do
92 {
93 size_t len;
94 const char *comma = strchr(s, ',');
95 if (comma == NULL)
96 {
97 len = strlen(s);
98 comma = s + len;
99 }
100 else
101 {
102 len = static_cast<size_t>(comma - s);
103 }
104
105 char buf[64];
106 if ((len+1u) > sizeof(buf))
107 {
108 ctor_fail(-1, "Range in list too long: '%s'", list);
109 }
110 else if (len)
111 {
112 /* SourceForge bug number #438857:
113 * ranges like "1.1.1.2," cause an assertion
114 * failure while SCCS just ignores the empty list item.
115 * Hence we introduce the conditional surrounding this
116 * block.
117 */
118 memcpy(buf, s, len);
119 buf[len] = '\0';
120
121 char *dash = strchr(buf, '-');
122 range<TYPE> *p = new range<TYPE>;
123
124 if (dash == NULL)
125 {
126 p->to = p->from = TYPE(buf);
127 }
128 else
129 {
130 *dash++ = '\0';
131 p->from = TYPE(buf);
132 p->to = TYPE(dash);
133 }
134
135 p->next = head;
136 head = p;
137 }
138 s = comma;
139 } while(*s++ != '\0');
140
141 if (clean()) // returns invalid flag.
142 {
143 destroy();
144 head = NULL;
145 invalidate();
146 }
147 else
148 {
149 ASSERT(valid());
150 }
151 }
152
153 template <class TYPE>
154 int
clean()155 range_list<TYPE>::clean()
156 {
157 if (!valid())
158 return 1;
159
160 range<TYPE> *sp = head;
161 range<TYPE> *new_head = NULL;
162 while (sp != NULL)
163 {
164 range<TYPE> *next_sp = sp->next;
165
166 if (sp->from <= sp->to)
167 {
168 range<TYPE> *dp = new_head;
169 range<TYPE> *pdp = NULL;
170
171 TYPE sp_to_1 = sp->to;
172 TYPE sp_from_1 = sp->from;
173 ++sp_to_1;
174 --sp_from_1;
175
176 while (dp != NULL && dp->to < sp_from_1)
177 {
178 pdp = dp;
179 dp = dp->next;
180 }
181
182 while (dp != NULL && dp->from <= sp_to_1)
183 {
184 /* While sp overlaps dp, merge dp into sp. */
185 if (dp->to > sp->to)
186 {
187 sp_to_1 = sp->to = dp->to;
188 ++sp_to_1;
189 }
190 if (dp->from < sp->from)
191 {
192 sp->from = dp->from;
193 }
194
195 range<TYPE> *next_dp = dp->next;
196 delete dp;
197 dp = next_dp;
198 if (pdp == NULL)
199 {
200 new_head = dp;
201 }
202 else
203 {
204 pdp->next = dp;
205 }
206 }
207 if (pdp == NULL)
208 {
209 sp->next = new_head;
210 new_head = sp;
211 }
212 else
213 {
214 sp->next = pdp->next;
215 pdp->next = sp;
216 }
217 }
218 else
219 {
220 invalidate();
221 delete sp;
222 }
223 sp = next_sp;
224 }
225 head = new_head;
226 return !valid_flag;
227 }
228
229 template <class TYPE>
230 int
member(TYPE id)231 range_list<TYPE>::member(TYPE id) const
232 {
233 const range<TYPE> *p = head;
234
235 while (p)
236 {
237 if (p->from <= id && id <= p->to)
238 {
239 return 1; // yes
240 }
241 p = p->next;
242 }
243 return 0; // no
244 }
245
246 template <class TYPE>
247 void
destroy()248 range_list<TYPE>::destroy()
249 {
250 if (!valid())
251 return;
252
253 range<TYPE> *p = head;
254
255 while(p != NULL)
256 {
257 range<TYPE> *np = p->next;
258 delete p;
259 p = np;
260 }
261 head = NULL;
262 }
263
264 template <class TYPE>
265 range<TYPE> *
do_copy_list(range<TYPE> * p)266 range_list<TYPE>::do_copy_list(range<TYPE> *p) // static member.
267 {
268 if (p == NULL)
269 {
270 return NULL;
271 }
272 range<TYPE> *copy_head = new range<TYPE>;
273 range<TYPE> *np = copy_head;
274
275 while(1)
276 {
277 np->from = p->from;
278 np->to = p->to;
279
280 p = p->next;
281 if (p == NULL)
282 {
283 break;
284 }
285
286 np = np->next = new range<TYPE>;
287 }
288
289 np->next = NULL;
290 return copy_head;
291 }
292
293 template <class TYPE>
range_list(range_list const & list)294 range_list<TYPE>::range_list(range_list const &list)
295 {
296 valid_flag = 1;
297 ASSERT(list.valid());
298 head = do_copy_list(list.head);
299 ASSERT(valid());
300 }
301
302 template <class TYPE>
303 range_list<TYPE> &
304 range_list<TYPE>::operator =(range_list<TYPE> const &list)
305 {
306 ASSERT(valid());
307 ASSERT(list.valid());
308
309 range<TYPE> *p = do_copy_list(list.head);
310 destroy();
311 head = p;
312
313 ASSERT(valid());
314 return *this;
315 }
316
317
318 template <class TYPE>
range_list()319 range_list<TYPE>::range_list(): head(0), valid_flag(1)
320 {
321 }
322
323 template <class TYPE>
324 int
valid()325 range_list<TYPE>::valid() const
326 {
327 return valid_flag;
328 }
329
330 template <class TYPE>
331 int
empty()332 range_list<TYPE>::empty() const
333 {
334 return head ? 0 : 1;
335 }
336
337 template <class TYPE>
338 void
invalidate()339 range_list<TYPE>::invalidate()
340 {
341 valid_flag = 0;
342 }
343
344 template <class TYPE>
~range_list()345 range_list<TYPE>::~range_list()
346 {
347 destroy();
348 invalidate();
349 }
350
351 template <class TYPE>
352 int
print(FILE * out)353 range_list<TYPE>::print(FILE *out) const
354 {
355 if (empty() || !valid())
356 {
357 return 0;
358 }
359
360
361 range<TYPE> *p = head;
362 while (1)
363 {
364 if (p->from.print(out))
365 {
366 return 1;
367 }
368 if (p->to != p->from
369 && (putc('-', out) == EOF
370 || p->to.print(out)))
371 {
372 return 1;
373 }
374
375 p = p->next;
376 if (p == NULL)
377 {
378 return 0;
379 }
380
381 if (putc(',', out) == EOF)
382 {
383 return 1;
384 }
385 }
386 }
387
388 #endif /* __SID_LIST_H__ */
389
390 /* Local variables: */
391 /* mode: c++ */
392 /* End: */
393