Fixed comment
[privoxy.git] / list.c
1 const char list_rcs[] = "$Id: list.c,v 1.7 2001/08/05 16:06:20 jongfoster 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.7  2001/08/05 16:06:20  jongfoster
38  *    Modifiying "struct map" so that there are now separate header and
39  *    "map_entry" structures.  This means that functions which modify a
40  *    map no longer need to return a pointer to the modified map.
41  *    Also, it no longer reverses the order of the entries (which may be
42  *    important with some advanced template substitutions).
43  *
44  *    Revision 1.6  2001/07/31 14:44:51  oes
45  *    list_to_text() now appends empty line at end
46  *
47  *    Revision 1.5  2001/06/29 21:45:41  oes
48  *    Indentation, CRLF->LF, Tab-> Space
49  *
50  *    Revision 1.4  2001/06/29 13:30:22  oes
51  *    - Added Convenience function enlist_unique_header(),
52  *      which takes the Header name and value as separate
53  *      arguments and thus saves the pain of sprintf()ing
54  *      and determining the Header name length to enlist_unique
55  *    - Improved comments
56  *    - Removed logentry from cancelled commit
57  *
58  *    Revision 1.3  2001/06/03 19:12:24  oes
59  *    functions for new struct map, extended enlist_unique
60  *
61  *    Revision 1.2  2001/06/01 18:49:17  jongfoster
62  *    Replaced "list_share" with "list" - the tiny memory gain was not
63  *    worth the extra complexity.
64  *
65  *    Revision 1.1  2001/05/31 21:11:53  jongfoster
66  *    - Moved linked list support to new "list.c" file.
67  *      Structure definitions are still in project.h,
68  *      function prototypes are now in "list.h".
69  *    - Added support for "struct list_share", which is identical
70  *      to "struct list" except it saves memory by not duplicating
71  *      the strings.  Obviously, this only works if there is some
72  *      other way of managing the memory used by the strings.
73  *      (These list_share lists are used for lists which last
74  *      for only 1 request, and where all the list entries are
75  *      just coming directly from entries in the actionsfile.)
76  *      Note that you still need to destroy list_share lists
77  *      properly to free the nodes - it's only the strings
78  *      which are shared.
79  *
80  *
81  *********************************************************************/
82 \f
83
84 #include "config.h"
85
86 #include <stdio.h>
87 #include <sys/types.h>
88 #include <stdlib.h>
89 #include <ctype.h>
90 #include <string.h>
91
92 #include <assert.h>
93
94 #ifndef _WIN32
95 #include <unistd.h>
96 #endif
97
98 #include "project.h"
99 #include "jcc.h"
100 #include "list.h"
101 #include "miscutil.h"
102
103 const char list_h_rcs[] = LIST_H_VERSION;
104
105
106 /*********************************************************************
107  *
108  * Function    :  enlist
109  *
110  * Description :  Append a string into a specified string list.
111  *
112  * Parameters  :
113  *          1  :  header = pointer to list 'dummy' header
114  *          2  :  str = string to add to the list (maybe NULL)
115  *
116  * Returns     :  N/A
117  *
118  *********************************************************************/
119 void enlist(struct list *header, const char *str)
120 {
121    struct list *cur = (struct list *)malloc(sizeof(*cur));
122    struct list *last;
123
124    if (cur)
125    {
126       cur->str  = (str ? strdup(str) : NULL);
127       cur->next = NULL;
128
129       last = header->last;
130       if (last == NULL)
131       {
132          last = header;
133       }
134
135       last->next   = cur;
136       header->last = cur;
137    }
138
139 }
140
141
142 /*********************************************************************
143  *
144  * Function    :  enlist_first
145  *
146  * Description :  Append a string as first element into a specified
147  *                string list.
148  *
149  * Parameters  :
150  *          1  :  header = pointer to list 'dummy' header
151  *          2  :  str = string to add to the list (maybe NULL)
152  *
153  * Returns     :  N/A
154  *
155  *********************************************************************/
156 void enlist_first(struct list *header, const char *str)
157 {
158    struct list *cur = (struct list *)malloc(sizeof(*cur));
159
160    if (cur)
161    {
162       cur->str  = (str ? strdup(str) : NULL);
163       cur->next = header->next;
164
165       header->next = cur;
166       if (header->last == NULL)
167       {
168          header->last = cur;
169       }
170    }
171
172 }
173
174
175 /*********************************************************************
176  *
177  * Function    :  enlist_unique
178  *
179  * Description :  Append a string into a specified string list,
180  *                if & only if it's not there already.
181  *                If the n argument is nonzero, only compare up to
182  *                the nth character. 
183  *
184  * Parameters  :
185  *          1  :  header = pointer to list 'dummy' header
186  *          2  :  str = string to add to the list (maybe NULL)
187  *          3  :  n = number of chars to use for uniqueness test
188  *
189  * Returns     :  N/A
190  *
191  *********************************************************************/
192 void enlist_unique(struct list *header, const char *str, int n)
193 {
194    struct list *last;
195    struct list *cur = header->next;
196
197    while (cur != NULL)
198    {
199       if ((cur->str != NULL) && (
200          (n && (0 == strncmp(str, cur->str, n))) || 
201          (!n && (0 == strcmp(str, cur->str)))))
202       {
203          /* Already there */
204          return;
205       }
206       cur = cur->next;
207    }
208
209    cur = (struct list *)malloc(sizeof(*cur));
210
211    if (cur != NULL)
212    {
213       cur->str  = (str ? strdup(str) : NULL); /* FIXME check retval */
214       cur->next = NULL;
215
216       last = header->last;
217       if (last == NULL)
218       {
219          last = header;
220       }
221       last->next   = cur;
222       header->last = cur;
223    }
224 }
225
226
227 /*********************************************************************
228  *
229  * Function    :  enlist_unique_header
230  *
231  * Description :  Make a HTTP header from the two strings name and value,
232  *                and append the result into a specified string list,
233  *                if & only if there isn't already a header with that name.
234  *
235  * Parameters  :
236  *          1  :  header = pointer to list 'dummy' header
237  *          2  :  name = name of header to be added
238  *          3  :  value = value of header to be added
239  *
240  * Returns     :  N/A
241  *
242  *********************************************************************/
243 void enlist_unique_header(struct list *header, const char *name, const char *value)
244 {
245    struct list *last;
246    struct list *cur = header->next;
247    int length;
248    char *dummy;
249
250    if (name == NULL || value == NULL) return;
251
252    dummy = strdup(name);
253    dummy = strsav(dummy, ": ");
254    length = strlen(dummy);
255
256    while (cur != NULL)
257    {
258       if ((cur->str != NULL) && 
259                 (0 == strncmp(dummy, cur->str, length)))
260       {
261          /* Already there */
262          return;
263       }
264       cur = cur->next;
265    }
266
267    cur = (struct list *)malloc(sizeof(*cur));
268
269    if (cur != NULL)
270    {
271       cur->str  = strsav(dummy, value);
272       cur->next = NULL;
273
274       last = header->last;
275       if (last == NULL)
276       {
277          last = header;
278       }
279       last->next   = cur;
280       header->last = cur;
281    }
282 }
283
284
285 /*********************************************************************
286  *
287  * Function    :  destroy_list
288  *
289  * Description :  Destroy a string list (opposite of enlist)
290  *
291  * Parameters  :
292  *          1  :  header = pointer to list 'dummy' header
293  *
294  * Returns     :  N/A
295  *
296  *********************************************************************/
297 void destroy_list(struct list *header)
298 {
299    struct list *p, *n;
300
301    for (p = header->next; p ; p = n)
302    {
303       n = p->next;
304       freez(p->str);
305       free(p);
306    }
307
308    memset(header, '\0', sizeof(*header));
309
310 }
311
312
313 /*********************************************************************
314  *
315  * Function    :  list_to_text
316  *
317  * Description :  "Flaten" a string list into 1 long \r\n delimited string,
318  *                adding an empty line at the end.
319  *
320  * Parameters  :
321  *          1  :  h = pointer to list 'dummy' header
322  *
323  * Returns     :  NULL on malloc error, else new long string.
324  *
325  *********************************************************************/
326 char *list_to_text(struct list *h)
327 {
328    struct list *p;
329    char *ret = NULL;
330    char *s;
331    int size = 2;
332
333    for (p = h->next; p ; p = p->next)
334    {
335       if (p->str)
336       {
337          size += strlen(p->str) + 2;
338       }
339    }
340
341    if ((ret = (char *)malloc(size + 1)) == NULL)
342    {
343       return(NULL);
344    }
345
346    ret[size] = '\0';
347
348    s = ret;
349
350    for (p = h->next; p ; p = p->next)
351    {
352       if (p->str)
353       {
354          strcpy(s, p->str);
355          s += strlen(s);
356          *s++ = '\r'; *s++ = '\n';
357       }
358    }
359    *s++ = '\r'; *s++ = '\n';
360
361    return(ret);
362
363 }
364
365
366 /*********************************************************************
367  *
368  * Function    :  list_remove_item
369  *
370  * Description :  Remove a string from a specified string list.
371  *
372  * Parameters  :
373  *          1  :  header = pointer to list 'dummy' header
374  *          2  :  str = string to remove from the list
375  *
376  * Returns     :  Number of times it was removed.
377  *
378  *********************************************************************/
379 int list_remove_item(struct list *header, const char *str)
380 {
381    struct list *prev = header;
382    struct list *cur = prev->next;
383    int count = 0;
384
385    while (cur != NULL)
386    {
387       if ((cur->str != NULL) && (0 == strcmp(str, cur->str)))
388       {
389          count++;
390
391          prev->next = cur->next;
392          free(cur->str);
393          free(cur);
394       }
395       else
396       {
397          prev = cur;
398       }
399       cur = prev->next;
400    }
401
402    header->last = prev;
403
404    return count;
405 }
406
407
408 /*********************************************************************
409  *
410  * Function    :  list_remove_list
411  *
412  * Description :  Remove all strings in one list from another list.
413  *                This is currently a brute-force algorithm
414  *                (it compares every pair of strings).
415  *
416  * Parameters  :
417  *          1  :  dest = list to change
418  *          2  :  src = list of strings to remove
419  *
420  * Returns     :  Total number of strings removed.
421  *
422  *********************************************************************/
423 int list_remove_list(struct list *dest, const struct list *src)
424 {
425    struct list *cur = src->next;
426    int count = 0;
427
428    while (cur != NULL)
429    {
430       if (cur->str != NULL)
431       {
432          count += list_remove_item(dest, cur->str);
433       }
434       cur = cur->next;
435    }
436
437    return count;
438 }
439
440
441 /*********************************************************************
442  *
443  * Function    :  list_duplicate
444  *
445  * Description :  Duplicate a string list
446  *
447  * Parameters  :
448  *          1  :  dest = pointer to destination for copy.  Caller allocs.
449  *          2  :  src = pointer to source for copy.
450  *
451  * Returns     :  N/A
452  *
453  *********************************************************************/
454 void list_duplicate(struct list *dest, const struct list *src)
455 {
456    struct list * cur_src = src->next;
457    struct list * cur_dest = dest;
458
459    memset(dest, '\0', sizeof(*dest));
460
461    while (cur_src)
462    {
463       cur_dest = cur_dest->next = (struct list *)zalloc(sizeof(*cur_dest));
464       if (cur_dest == NULL)
465       {
466          return;
467       }
468       cur_dest->str = strdup(cur_src->str);
469       cur_src = cur_src->next;
470    }
471
472    dest->last = cur_dest;
473
474 }
475
476
477 /*********************************************************************
478  *
479  * Function    :  list_append_list_unique
480  *
481  * Description :  Append a string list to another list.
482  *                Duplicate items are not added.
483  *
484  * Parameters  :
485  *          1  :  dest = pointer to destination for merge.  Caller allocs.
486  *          2  :  src = pointer to source for merge.
487  *
488  * Returns     :  N/A
489  *
490  *********************************************************************/
491 void list_append_list_unique(struct list *dest, const struct list *src)
492 {
493    struct list * cur = src->next;
494
495    while (cur)
496    {
497       enlist_unique(dest, cur->str, 0);
498       cur = cur->next;
499    }
500 }
501
502
503 /*********************************************************************
504  *
505  * Function    :  map
506  *
507  * Description :  Add a mapping from given name to given value to a
508  *                given map.
509  *
510  *                Note: Since all strings will be free()d in free_map()
511  *                      later, use the copy flags for constants or
512  *                      strings that will be independantly free()d.
513  *
514  * Parameters  :
515  *          1  :  the_map = map to add to
516  *          2  :  name = name to add
517  *          3  :  nc = flag set if a copy of name should be used
518  *          4  :  value = value to add
519  *          5  :  vc = flag set if a copy of value should be used
520  *
521  * Returns     :  N/A
522  *
523  *********************************************************************/
524 void map(struct map *the_map, const char *name, int nc, const char *value, int vc)
525 {
526    struct map_entry *new_entry;
527
528    if (NULL == (new_entry = zalloc(sizeof(*new_entry))))
529    {
530       return;
531    }
532
533    new_entry->name  = nc ? strdup(name) : name;
534    new_entry->value = vc ? strdup(value) : value;
535    /* new_entry->next = NULL;  - implied by zalloc */
536
537    if (the_map->last)
538    {
539       the_map->last = the_map->last->next = new_entry;
540    }
541    else
542    {
543       the_map->last = the_map->first = new_entry;
544    }
545
546 }
547
548
549 /*********************************************************************
550  *
551  * Function    :  lookup
552  *
553  * Description :  Look up an item with a given name in a map, and
554  *                return its value
555  *
556  * Parameters  :
557  *          1  :  name = name parameter to look for
558  *
559  * Returns     :  the value if found, else the empty string
560  *
561  *********************************************************************/
562 const char *lookup(const struct map *the_map, const char *name)
563 {
564    const struct map_entry *cur_entry = the_map->first;
565
566    while (cur_entry)
567    {
568       if (!strcmp(name, cur_entry->name))
569       {
570          return cur_entry->value;
571       }
572       cur_entry = cur_entry->next;
573    }
574    return "";
575 }
576
577
578 /*********************************************************************
579  *
580  * Function    :  new_nap
581  *
582  * Description :  Create a new, empty map.
583  *
584  * Parameters  :
585  *
586  * Returns     :  A new, empty map, or NULL if out of memory.
587  *
588  *********************************************************************/
589 struct map *new_map(void)
590 {
591    return (struct map *) zalloc(sizeof(struct map));
592 }
593
594
595 /*********************************************************************
596  *
597  * Function    :  free_map
598  *
599  * Description :  Free the memory occupied by a map and its
600  *                depandant strings
601  *
602  * Parameters  :
603  *          1  :  cur_entry = map to be freed.  May be NULL.
604  *
605  * Returns     :  N/A
606  *
607  *********************************************************************/
608 void free_map(struct map *the_map)
609 {
610    struct map_entry *cur_entry;
611    struct map_entry *next_entry;
612
613    if (the_map == NULL)
614    {
615       return;
616    }
617
618    for (cur_entry = the_map->first; cur_entry != NULL; cur_entry = next_entry) 
619    {
620       freez((char *)cur_entry->name);
621       freez((char *)cur_entry->value);
622
623       next_entry = cur_entry->next;
624       free(cur_entry);
625    }
626
627    the_map->first = the_map->last = NULL;
628
629    free(the_map);
630 }
631
632
633 /*
634   Local Variables:
635   tab-width: 3
636   end:
637 */