1 /* -*- mode: C; mode: fold; -*- */
2 /*
3 This file is part of SLRN.
4
5 Copyright (c) 2003-2006 Thomas Schultz <tststs@gmx.de>
6
7 partly based on code by John E. Davis:
8 Copyright (c) 1994, 1999, 2007-2016 John E. Davis <jed@jedsoft.org>
9
10 This program is free software; you can redistribute it and/or modify it
11 under the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 2 of the License, or (at your option)
13 any later version.
14
15 This program is distributed in the hope that it will be useful, but WITHOUT
16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
18 more details.
19
20 You should have received a copy of the GNU General Public License along
21 with this program; if not, write to the Free Software Foundation, Inc.,
22 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
23 */
24
25 /*{{{ include files */
26 #include "config.h"
27 #include "slrnfeat.h"
28
29 #include <string.h>
30 #ifdef HAVE_STDLIB_H
31 # include <stdlib.h>
32 #endif
33
34 #include <slang.h>
35 #include "ranges.h"
36 #include "util.h"
37 #include "strutil.h"
38 /*}}}*/
39
40 /* line is expected to contain newsrc-style integer ranges. They are put
41 * into a range list which is returned.
42 */
slrn_ranges_from_newsrc_line(char * line)43 Slrn_Range_Type *slrn_ranges_from_newsrc_line (char *line) /*{{{*/
44 {
45 Slrn_Range_Type *retval=NULL;
46
47 while (1)
48 {
49 int min, max;
50 char ch;
51 /* skip white space and delimiters */
52 while (((ch = *line) != 0) && ((ch <= ' ') || (ch == ','))) line++;
53 if ((ch < '0') || (ch > '9')) break;
54 min = atoi (line++);
55 while (((ch = *line) != 0) && (ch >= '0') && (ch <= '9')) line++;
56 if (ch == '-')
57 {
58 line++;
59 max = atoi (line);
60 while (((ch = *line) != 0) && (ch >= '0') && (ch <= '9')) line++;
61 }
62 else max = min;
63
64 retval = slrn_ranges_add (retval, min, max);
65 }
66
67 return retval;
68 }
69 /*}}}*/
70
71 /* Writes the range list r to the file fp in newsrc format.
72 * If max is non-zero, no numbers larger than max are written.
73 * Returns 0 on success, -1 otherwise.
74 */
slrn_ranges_to_newsrc_file(Slrn_Range_Type * r,NNTP_Artnum_Type max,FILE * fp)75 int slrn_ranges_to_newsrc_file (Slrn_Range_Type *r, NNTP_Artnum_Type max, FILE* fp) /*{{{*/
76 {
77 while ((r != NULL) && ((max<=0) || (r->min <= max)))
78 {
79 NNTP_Artnum_Type minmax = r->max;
80 if ((max>0) && (minmax > max))
81 minmax = max;
82
83 if (r->min != minmax)
84 {
85 if (fprintf (fp, NNTP_FMT_ARTRANGE, r->min, minmax) < 0)
86 return -1;
87 }
88 else if (fprintf (fp, NNTP_FMT_ARTNUM, r->min) < 0)
89 return -1;
90
91 r = r->next;
92 if ((r != NULL) && (EOF == putc (',', fp)))
93 return -1;
94 }
95 return 0;
96 }
97 /*}}}*/
98
99 /* Adds the range [min, max] to the given ranges structure r
100 * Note: does not allocate a new list, but changes r; the function still
101 * returns a pointer in case the first element of the list changes.
102 * (r==NULL) is allowed; in this case, a new list is created
103 */
slrn_ranges_add(Slrn_Range_Type * r,NNTP_Artnum_Type min,NNTP_Artnum_Type max)104 Slrn_Range_Type *slrn_ranges_add (Slrn_Range_Type *r, NNTP_Artnum_Type min, NNTP_Artnum_Type max) /*{{{*/
105 {
106 Slrn_Range_Type *head = r;
107
108 if (min>max) return head;
109
110 /* Do we need to insert at the beginning of the list? */
111 if ((r==NULL) || (max+1 < r->min))
112 {
113 head = (Slrn_Range_Type *) slrn_safe_malloc (sizeof(Slrn_Range_Type));
114 head->min = min;
115 head->max = max;
116 head->next = r;
117 head->prev = NULL;
118 if (r!=NULL)
119 r->prev = head;
120
121 return head;
122 }
123
124 /* Skip ranges below min */
125 while ((r->next!=NULL) && (r->max+1 < min))
126 r = r->next;
127
128 /* Do we need to append a new range? */
129 if (min > r->max+1)
130 {
131 Slrn_Range_Type *n;
132 n = (Slrn_Range_Type *) slrn_safe_malloc (sizeof(Slrn_Range_Type));
133 n->min = min;
134 n->max = max;
135 n->next = NULL;
136 n->prev = r;
137 r->next = n;
138
139 return head;
140 }
141
142 /* Do we need to insert a new range? */
143 if (max+1 < r->min)
144 {
145 Slrn_Range_Type *n;
146 n = (Slrn_Range_Type *) slrn_safe_malloc (sizeof(Slrn_Range_Type));
147 n->min = min;
148 n->max = max;
149 n->next = r;
150 n->prev = r->prev;
151 n->prev->next = n;
152 r->prev = n;
153
154 return head;
155 }
156
157 /* Update min / max values */
158 if (min < r->min)
159 r->min = min;
160 if (max > r->max)
161 r->max = max;
162
163 /* Clean up successive ranges */
164 while ((r->next != NULL) &&
165 (r->next->min <= r->max+1))
166 {
167 Slrn_Range_Type *next = r->next;
168 if (next->max > r->max)
169 r->max = next->max;
170
171 r->next = next->next;
172 if (r->next != NULL)
173 r->next->prev = r;
174 SLFREE (next);
175 }
176
177 return head;
178 }
179 /*}}}*/
180
181 /* Removes the range [min, max] from the given ranges structure r
182 * Note: does not allocate a new list, but changes r; the function still
183 * returns a pointer in case the first element of the list gets deleted.
184 */
slrn_ranges_remove(Slrn_Range_Type * r,NNTP_Artnum_Type min,NNTP_Artnum_Type max)185 Slrn_Range_Type *slrn_ranges_remove (Slrn_Range_Type *r, NNTP_Artnum_Type min, NNTP_Artnum_Type max) /*{{{*/
186 {
187 Slrn_Range_Type *head = r;
188
189 if ((min>max) || (r==NULL))
190 return head;
191
192 /* Skip ranges below min */
193 while ((r->next != NULL) && (r->max < min))
194 r = r->next;
195
196 /* Do we need to split the current range? */
197 if ((r->min < min) && (r->max > max))
198 {
199 Slrn_Range_Type *n;
200 n = (Slrn_Range_Type *) slrn_safe_malloc (sizeof(Slrn_Range_Type));
201 n->min = max+1;
202 n->max = r->max;
203 r->max = min-1;
204 n->next = r->next;
205 if (n->next != NULL)
206 n->next->prev = n;
207 n->prev = r;
208 r->next = n;
209
210 return head;
211 }
212
213 /* Change or delete successive nodes */
214 while (r->next != NULL)
215 {
216 if (r->next->max <= max)
217 {
218 Slrn_Range_Type *next = r->next;
219 if (next->next != NULL)
220 next->next->prev = r;
221 r->next = next->next;
222
223 SLFREE (next);
224 }
225 else
226 {
227 if (r->next->min <= max)
228 r->next->min = max+1;
229 break;
230 }
231 }
232
233 if ((min <= r->max) && (max >= r->min))
234 {
235 if (max < r->max) /* Change this node */
236 r->min = max+1;
237 else if (min > r->min)
238 r->max = min-1;
239 else /* Delete this node */
240 {
241 Slrn_Range_Type *next = r->next;
242 if (next != NULL)
243 next->prev = r->prev;
244 if (r->prev != NULL)
245 r->prev->next = next;
246 else
247 head = next;
248
249 SLFREE (r);
250 }
251 }
252
253 return head;
254 }
255 /*}}}*/
256
257 /* Merges two range lists a and b and returns the result
258 * Note: does not allocate a new list, but changes a
259 */
slrn_ranges_merge(Slrn_Range_Type * a,Slrn_Range_Type * b)260 Slrn_Range_Type *slrn_ranges_merge (Slrn_Range_Type *a, Slrn_Range_Type *b) /*{{{*/
261 {
262 Slrn_Range_Type *retval = a;
263
264 while (b != NULL)
265 {
266 retval = slrn_ranges_add (retval, b->min, b->max);
267 b = b->next;
268 }
269
270 return retval;
271 }
272 /*}}}*/
273
274 /* Creates a new range list that contains only the numbers that are
275 * both in a and b and returns it; a and b remain untouched.
276 */
slrn_ranges_intersect(Slrn_Range_Type * a,Slrn_Range_Type * b)277 Slrn_Range_Type *slrn_ranges_intersect (Slrn_Range_Type *a, Slrn_Range_Type *b) /*{{{*/
278 {
279 Slrn_Range_Type *retval=NULL, *r=NULL, *n;
280 do
281 {
282 /* skip ranges that don't intersect at all */
283 do
284 {
285 if (b != NULL)
286 while ((a != NULL) && (a->max < b->min))
287 a = a->next;
288
289 if (a != NULL)
290 while ((b != NULL) && (b->max < a->min))
291 b = b->next;
292 }
293 while ((a!=NULL) && (b!=NULL) && (a->max < b->min));
294
295 /* append a range containing the next intersection */
296 if ((a!=NULL) && (b!=NULL))
297 {
298 n = (Slrn_Range_Type *) slrn_safe_malloc (sizeof(Slrn_Range_Type));
299 n->next = NULL;
300 if (retval==NULL)
301 {
302 n->prev = NULL;
303 r = retval = n;
304 }
305 else
306 {
307 n->prev = r;
308 r->next = n;
309 r = n;
310 }
311 n->min = (a->min < b->min) ? b->min : a->min;
312 n->max = (a->max > b->max) ? b->max : a->max;
313
314 if (n->max == a->max)
315 a = a->next;
316 else
317 b = b->next;
318 }
319 }
320 while ((a!=NULL) && (b!=NULL));
321 return retval;
322 }
323 /*}}}*/
324
325 /* Checks if n is in r; returns 1 if true, 0 if false. */
slrn_ranges_is_member(Slrn_Range_Type * r,NNTP_Artnum_Type n)326 int slrn_ranges_is_member (Slrn_Range_Type *r, NNTP_Artnum_Type n) /*{{{*/
327 {
328 while (r != NULL)
329 {
330 if ((r->min <= n) && (r->max >= n))
331 return 1;
332 if (n <= r->max)
333 return 0;
334 r = r->next;
335 }
336 return 0;
337 }
338 /*}}}*/
339
340 /* Makes a copy of the range list r and returns it (exits if out of memory!) */
slrn_ranges_clone(Slrn_Range_Type * r)341 Slrn_Range_Type *slrn_ranges_clone (Slrn_Range_Type *r) /*{{{*/
342 {
343 Slrn_Range_Type *retval=NULL, *c, *n;
344
345 if (r==NULL) return NULL;
346
347 retval = (Slrn_Range_Type *) slrn_safe_malloc (sizeof(Slrn_Range_Type));
348 retval->prev = NULL;
349 c = retval;
350
351 while (r != NULL)
352 {
353 c->min = r->min;
354 c->max = r->max;
355 r = r->next;
356 if (r != NULL)
357 {
358 n = (Slrn_Range_Type *) slrn_safe_malloc (sizeof(Slrn_Range_Type));
359 c->next = n;
360 n->prev = c;
361 c = n;
362 }
363 }
364 c->next = NULL;
365
366 return retval;
367 }
368 /*}}}*/
369
370 /* Compares two range lists and returns 0 if they are equal */
slrn_ranges_compare(Slrn_Range_Type * a,Slrn_Range_Type * b)371 int slrn_ranges_compare (Slrn_Range_Type *a, Slrn_Range_Type *b) /*{{{*/
372 {
373 while ((a != NULL) && (b != NULL)
374 && (a->min == b->min)
375 && (a->max == b->max))
376 {
377 a = a->next;
378 b = b->next;
379 }
380
381 return ((a == NULL) && (b == NULL)) ? 0 : 1;
382 }
383 /*}}}*/
384
385 /* Frees the memory used by the range list r */
slrn_ranges_free(Slrn_Range_Type * r)386 void slrn_ranges_free (Slrn_Range_Type *r) /*{{{*/
387 {
388 Slrn_Range_Type *next;
389
390 while (r != NULL)
391 {
392 next = r->next;
393 SLFREE (r);
394 r = next;
395 }
396 }
397 /*}}}*/
398