- Added Convenience function enlist_unique_header(),
[privoxy.git] / list.c
1 const char list_rcs[] = "$Id: list.c,v 1.3 2001/06/03 19:12:24 oes Exp $";
2 /*********************************************************************
3  *
4  * File        :  $Source: /cvsroot/ijbswa/current/list.c,v $
5  *
6  * Purpose     :  Declares functions to handle lists.
7  *                Functions declared include:
8  *                   `destroy_list', `enlist' and `list_to_text'
9  *
10  * Copyright   :  Written by and Copyright (C) 2001 the SourceForge
11  *                IJBSWA team.  http://ijbswa.sourceforge.net
12  *
13  *                Based on the Internet Junkbuster originally written
14  *                by and Copyright (C) 1997 Anonymous Coders and 
15  *                Junkbusters Corporation.  http://www.junkbusters.com
16  *
17  *                This program is free software; you can redistribute it 
18  *                and/or modify it under the terms of the GNU General
19  *                Public License as published by the Free Software
20  *                Foundation; either version 2 of the License, or (at
21  *                your option) any later version.
22  *
23  *                This program is distributed in the hope that it will
24  *                be useful, but WITHOUT ANY WARRANTY; without even the
25  *                implied warranty of MERCHANTABILITY or FITNESS FOR A
26  *                PARTICULAR PURPOSE.  See the GNU General Public
27  *                License for more details.
28  *
29  *                The GNU General Public License should be included with
30  *                this file.  If not, you can view it at
31  *                http://www.gnu.org/copyleft/gpl.html
32  *                or write to the Free Software Foundation, Inc., 59
33  *                Temple Place - Suite 330, Boston, MA  02111-1307, USA.
34  *
35  * Revisions   :
36  *    $Log: list.c,v $
37  *    Revision 1.3  2001/06/03 19:12:24  oes
38  *    functions for new struct map, extended enlist_unique
39  *
40  *    Revision 1.2  2001/06/01 18:49:17  jongfoster
41  *    Replaced "list_share" with "list" - the tiny memory gain was not
42  *    worth the extra complexity.
43  *
44  *    Revision 1.1  2001/05/31 21:11:53  jongfoster
45  *    - Moved linked list support to new "list.c" file.
46  *      Structure definitions are still in project.h,
47  *      function prototypes are now in "list.h".
48  *    - Added support for "struct list_share", which is identical
49  *      to "struct list" except it saves memory by not duplicating
50  *      the strings.  Obviously, this only works if there is some
51  *      other way of managing the memory used by the strings.
52  *      (These list_share lists are used for lists which last
53  *      for only 1 request, and where all the list entries are
54  *      just coming directly from entries in the actionsfile.)
55  *      Note that you still need to destroy list_share lists
56  *      properly to free the nodes - it's only the strings
57  *      which are shared.
58  *
59  *
60  *********************************************************************/
61 \f
62
63 #include "config.h"
64
65 #include <stdio.h>
66 #include <sys/types.h>
67 #include <stdlib.h>
68 #include <ctype.h>
69 #include <string.h>
70
71 #ifndef _WIN32
72 #include <unistd.h>
73 #endif
74
75 #include "project.h"
76 #include "jcc.h"
77 #include "list.h"
78 #include "miscutil.h"
79
80 const char list_h_rcs[] = LIST_H_VERSION;
81
82 /*********************************************************************
83  *
84  * Function    :  enlist
85  *
86  * Description :  Append a string into a specified string list.
87  *
88  * Parameters  :
89  *          1  :  header = pointer to list 'dummy' header
90  *          2  :  str = string to add to the list (maybe NULL)
91  *
92  * Returns     :  N/A
93  *
94  *********************************************************************/
95 void enlist(struct list *header, const char *str)
96 {
97    struct list *cur = (struct list *)malloc(sizeof(*cur));
98    struct list *last;
99
100    if (cur)
101    {
102       cur->str  = (str ? strdup(str) : NULL);
103       cur->next = NULL;
104
105       last = header->last;
106       if (last == NULL)
107       {
108          last = header;
109       }
110
111       last->next   = cur;
112       header->last = cur;
113    }
114
115 }
116
117
118 /*********************************************************************
119  *
120  * Function    :  enlist_first
121  *
122  * Description :  Append a string as first element into a specified
123  *                string list.
124  *
125  * Parameters  :
126  *          1  :  header = pointer to list 'dummy' header
127  *          2  :  str = string to add to the list (maybe NULL)
128  *
129  * Returns     :  N/A
130  *
131  *********************************************************************/
132 void enlist_first(struct list *header, const char *str)
133 {
134    struct list *cur = (struct list *)malloc(sizeof(*cur));
135
136    if (cur)
137    {
138       cur->str  = (str ? strdup(str) : NULL);
139       cur->next = header->next;
140
141       header->next = cur;
142       if (header->last == NULL)
143       {
144          header->last = cur;
145       }
146    }
147
148 }
149
150
151 /*********************************************************************
152  *
153  * Function    :  enlist_unique
154  *
155  * Description :  Append a string into a specified string list,
156  *                if & only if it's not there already.
157  *                If the n argument is nonzero, only compare up to
158  *                the nth character. 
159  *
160  * Parameters  :
161  *          1  :  header = pointer to list 'dummy' header
162  *          2  :  str = string to add to the list (maybe NULL)
163  *          3  :  n = number of chars to use for uniqueness test
164  *
165  * Returns     :  N/A
166  *
167  *********************************************************************/
168 void enlist_unique(struct list *header, const char *str, int n)
169 {
170    struct list *last;
171    struct list *cur = header->next;
172
173    while (cur != NULL)
174    {
175       if ((cur->str != NULL) && (
176          (n && (0 == strncmp(str, cur->str, n))) || 
177          (!n && (0 == strcmp(str, cur->str)))))
178       {
179          /* Already there */
180          return;
181       }
182       cur = cur->next;
183    }
184
185    cur = (struct list *)malloc(sizeof(*cur));
186
187    if (cur != NULL)
188    {
189       cur->str  = (str ? strdup(str) : NULL); /* FIXME check retval */
190       cur->next = NULL;
191
192       last = header->last;
193       if (last == NULL)
194       {
195          last = header;
196       }
197       last->next   = cur;
198       header->last = cur;
199    }
200 }
201
202
203 /*********************************************************************
204  *
205  * Function    :  enlist_unique_header
206  *
207  * Description :  Make a HTTP header from the two strings name and value,
208  *                and append the result into a specified string list,
209  *                if & only if there isn't already a header with that name.
210  *
211  * Parameters  :
212  *          1  :  header = pointer to list 'dummy' header
213  *          2  :  first = first string to add to the list (maybe NULL)
214  *          3  :  second = number of chars to use for uniqueness test
215  *
216  * Returns     :  N/A
217  *
218  *********************************************************************/
219 void enlist_unique_header(struct list *header, const char *name, const char *value)
220 {
221    struct list *last;
222    struct list *cur = header->next;
223    int length;
224    char *dummy;
225
226    if (name == NULL || value == NULL) return;
227
228    dummy = strdup(name);
229         dummy = strsav(dummy, ": ");
230    length = strlen(dummy);
231
232    while (cur != NULL)
233    {
234       if ((cur->str != NULL) && 
235                         (0 == strncmp(dummy, cur->str, length)))
236       {
237          /* Already there */
238          return;
239       }
240       cur = cur->next;
241    }
242
243    cur = (struct list *)malloc(sizeof(*cur));
244
245    if (cur != NULL)
246    {
247            cur->str  = strsav(dummy, value);
248       cur->next = NULL;
249
250       last = header->last;
251       if (last == NULL)
252       {
253          last = header;
254       }
255       last->next   = cur;
256       header->last = cur;
257    }
258 }
259
260
261 /*********************************************************************
262  *
263  * Function    :  destroy_list
264  *
265  * Description :  Destroy a string list (opposite of enlist)
266  *
267  * Parameters  :
268  *          1  :  header = pointer to list 'dummy' header
269  *
270  * Returns     :  N/A
271  *
272  *********************************************************************/
273 void destroy_list(struct list *header)
274 {
275    struct list *p, *n;
276
277    for (p = header->next; p ; p = n)
278    {
279       n = p->next;
280       freez(p->str);
281       free(p);
282    }
283
284    memset(header, '\0', sizeof(*header));
285
286 }
287
288
289 /*********************************************************************
290  *
291  * Function    :  list_to_text
292  *
293  * Description :  "Flaten" a string list into 1 long \r\n delimited string.
294  *
295  * Parameters  :
296  *          1  :  h = pointer to list 'dummy' header
297  *
298  * Returns     :  NULL on malloc error, else new long string.
299  *
300  *********************************************************************/
301 char *list_to_text(struct list *h)
302 {
303    struct list *p;
304    char *ret = NULL;
305    char *s;
306    int size;
307
308    size = 0;
309
310    for (p = h->next; p ; p = p->next)
311    {
312       if (p->str)
313       {
314          size += strlen(p->str) + 2;
315       }
316    }
317
318    if ((ret = (char *)malloc(size + 1)) == NULL)
319    {
320       return(NULL);
321    }
322
323    ret[size] = '\0';
324
325    s = ret;
326
327    for (p = h->next; p ; p = p->next)
328    {
329       if (p->str)
330       {
331          strcpy(s, p->str);
332          s += strlen(s);
333          *s++ = '\r'; *s++ = '\n';
334       }
335    }
336
337    return(ret);
338
339 }
340
341
342 /*********************************************************************
343  *
344  * Function    :  list_remove_item
345  *
346  * Description :  Remove a string from a specified string list.
347  *
348  * Parameters  :
349  *          1  :  header = pointer to list 'dummy' header
350  *          2  :  str = string to remove from the list
351  *
352  * Returns     :  Number of times it was removed.
353  *
354  *********************************************************************/
355 int list_remove_item(struct list *header, const char *str)
356 {
357    struct list *prev = header;
358    struct list *cur = prev->next;
359    int count = 0;
360
361    while (cur != NULL)
362    {
363       if ((cur->str != NULL) && (0 == strcmp(str, cur->str)))
364       {
365          count++;
366
367          prev->next = cur->next;
368          free(cur->str);
369          free(cur);
370       }
371       else
372       {
373          prev = cur;
374       }
375       cur = prev->next;
376    }
377
378    header->last = prev;
379
380    return count;
381 }
382
383
384 /*********************************************************************
385  *
386  * Function    :  list_remove_list
387  *
388  * Description :  Remove all strings in one list from another list.
389  *                This is currently a brute-force algorithm
390  *                (it compares every pair of strings).
391  *
392  * Parameters  :
393  *          1  :  dest = list to change
394  *          2  :  src = list of strings to remove
395  *
396  * Returns     :  Total number of strings removed.
397  *
398  *********************************************************************/
399 int list_remove_list(struct list *dest, const struct list *src)
400 {
401    struct list *cur = src->next;
402    int count = 0;
403
404    while (cur != NULL)
405    {
406       if (cur->str != NULL)
407       {
408          count += list_remove_item(dest, cur->str);
409       }
410       cur = cur->next;
411    }
412
413    return count;
414 }
415
416
417 /*********************************************************************
418  *
419  * Function    :  list_duplicate
420  *
421  * Description :  Duplicate a string list
422  *
423  * Parameters  :
424  *          1  :  dest = pointer to destination for copy.  Caller allocs.
425  *          2  :  src = pointer to source for copy.
426  *
427  * Returns     :  N/A
428  *
429  *********************************************************************/
430 void list_duplicate(struct list *dest, const struct list *src)
431 {
432    struct list * cur_src = src->next;
433    struct list * cur_dest = dest;
434
435    memset(dest, '\0', sizeof(*dest));
436
437    while (cur_src)
438    {
439       cur_dest = cur_dest->next = (struct list *)zalloc(sizeof(*cur_dest));
440       if (cur_dest == NULL)
441       {
442          return;
443       }
444       cur_dest->str = strdup(cur_src->str);
445       cur_src = cur_src->next;
446    }
447
448    dest->last = cur_dest;
449
450 }
451
452
453 /*********************************************************************
454  *
455  * Function    :  list_append_list_unique
456  *
457  * Description :  Append a string list to another list.
458  *                Duplicate items are not added.
459  *
460  * Parameters  :
461  *          1  :  dest = pointer to destination for merge.  Caller allocs.
462  *          2  :  src = pointer to source for merge.
463  *
464  * Returns     :  N/A
465  *
466  *********************************************************************/
467 void list_append_list_unique(struct list *dest, const struct list *src)
468 {
469    struct list * cur = src->next;
470
471    while (cur)
472    {
473       enlist_unique(dest, cur->str, 0);
474       cur = cur->next;
475    }
476 }
477
478
479 /*********************************************************************
480  *
481  * Function    :  map
482  *
483  * Description :  Add a mapping from given name to given value to a
484  *                given map.
485  *
486  *                Note: Since all strings will be free()d in free_map()
487  *                      later, use the copy flags for constants or
488  *                      strings that will be independantly free()d.
489  *
490  * Parameters  :
491  *          1  :  map = map to add to
492  *          2  :  name = name to add
493  *          3  :  nc = flag set if a copy of name should be used
494  *          4  :  value = value to add
495  *          5  :  vc = flag set if a copy of value should be used
496  *
497  * Returns     :  pointer to extended map, or NULL if failiure
498  *
499  *********************************************************************/
500 struct map *map(struct map *map, char *name, int nc, char *value, int vc)
501 {
502    struct map *cur;
503
504    if (NULL == (cur = zalloc(sizeof(*cur))))
505    {
506       return(NULL);
507    }
508
509    cur->name  = nc ? strdup(name) : name;
510    cur->value = vc ? strdup(value) : value;
511    cur->next = map;
512
513    return(cur);
514
515 }
516
517
518 /*********************************************************************
519  *
520  * Function    :  lookup
521  *
522  * Description :  Look up an item with a given name in a map, and
523  *                return its value
524  *
525  * Parameters  :
526  *          1  :  name = name parameter to look for
527  *
528  * Returns     :  the value if found, else the empty string
529  *
530  *********************************************************************/
531 char *lookup(struct map *map, char *name)
532 {
533    struct map *p = map;
534
535    while (p)
536    {
537       if (!strcmp(name, p->name))
538       {
539          return p->value;
540       }
541       p = p->next;
542    }
543    return "";
544 }
545
546
547 /*********************************************************************
548  *
549  * Function    :  free_map
550  *
551  * Description :  Free the memory occupied by a map and its
552  *                depandant strings
553  *
554  * Parameters  :
555  *          1  :  list = list to bee freed
556  *
557  * Returns     :  N/A
558  *
559  *********************************************************************/
560 void free_map(struct map *map)
561 {
562    struct map *p = map;
563
564    while (p)
565    {
566       free(p->name);
567       free(p->value);
568
569       map = p->next;
570       free(p);
571       p = map;
572    }
573
574 }
575
576
577 /*
578   Local Variables:
579   tab-width: 3
580   end:
581 */